memheap.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355
  1. /*
  2. * File : memheap.c
  3. * This file is part of RT-Thread RTOS
  4. * COPYRIGHT (C) 2012, RT-Thread Development Team
  5. *
  6. * The license and distribution terms for this file may be
  7. * found in the file LICENSE in this distribution or at
  8. * http://www.rt-thread.org/license/LICENSE
  9. *
  10. * Change Logs:
  11. * Date Author Notes
  12. * 2012-04-10 Bernard first implementation
  13. * 2012-10-16 Bernard add the mutex lock for heap object.
  14. */
  15. #include <rtthread.h>
  16. #ifdef RT_USING_MEMHEAP
  17. /* dynamic pool magic and mask */
  18. #define RT_MEMHEAP_MAGIC 0x1ea01ea0
  19. #define RT_MEMHEAP_MASK 0xfffffffe
  20. #define RT_MEMHEAP_USED 0x01
  21. #define RT_MEMHEAP_FREED 0x00
  22. #define RT_MEMHEAP_IS_USED(i) ((i)->magic & RT_MEMHEAP_USED)
  23. #define RT_MEMHEAP_MINIALLOC 12
  24. #define RT_MEMHEAP_SIZE RT_ALIGN(sizeof(struct rt_memheap_item), RT_ALIGN_SIZE)
  25. /*
  26. * The initialized memory pool will be:
  27. * +-----------------------------------+--------------------------+
  28. * | whole freed memory block | Used Memory Block Tailer |
  29. * +-----------------------------------+--------------------------+
  30. *
  31. * block_list --> whole freed memory block
  32. *
  33. * The length of Used Memory Block Tailer is 0, which is prevents block merging across list
  34. */
  35. rt_err_t rt_memheap_init(struct rt_memheap *memheap, const char *name,
  36. void *start_addr,
  37. rt_uint32_t size)
  38. {
  39. struct rt_memheap_item *item;
  40. RT_ASSERT(memheap != RT_NULL);
  41. /* initialize pool object */
  42. rt_object_init(&(memheap->parent), RT_Object_Class_MemHeap, name);
  43. memheap->start_addr = start_addr;
  44. memheap->pool_size = RT_ALIGN_DOWN(size, RT_ALIGN_SIZE);
  45. memheap->available_size = memheap->pool_size - (2 * RT_MEMHEAP_SIZE);
  46. /* initialize the free list header */
  47. item = &(memheap->free_header);
  48. item->magic = RT_MEMHEAP_MAGIC;
  49. item->pool_ptr = memheap;
  50. item->next = RT_NULL;
  51. item->prev = RT_NULL;
  52. item->next_free = item;
  53. item->prev_free = item;
  54. /* set the free list to free list header */
  55. memheap->free_list = item;
  56. /* initialize the first big memory block */
  57. item = (struct rt_memheap_item *)start_addr;
  58. item->magic = RT_MEMHEAP_MAGIC;
  59. item->pool_ptr = memheap;
  60. item->next = RT_NULL;
  61. item->prev = RT_NULL;
  62. item->next_free = item;
  63. item->prev_free = item;
  64. item->next = (struct rt_memheap_item *)
  65. ((rt_uint8_t *)item + memheap->available_size + RT_MEMHEAP_SIZE);
  66. item->prev = item->next;
  67. /* block list header */
  68. memheap->block_list = item;
  69. /* place the big memory block to free list */
  70. item->next_free = memheap->free_list->next_free;
  71. item->prev_free = memheap->free_list;
  72. memheap->free_list->next_free->prev_free = item;
  73. memheap->free_list->next_free = item;
  74. /* move to the end of memory pool to build a small tailer block, which prevents block merging */
  75. item = item->next;
  76. /* it's a used memory block */
  77. item->magic = RT_MEMHEAP_MAGIC | RT_MEMHEAP_USED;
  78. item->pool_ptr = memheap;
  79. item->next = (struct rt_memheap_item *)start_addr;
  80. item->prev = (struct rt_memheap_item *)start_addr;
  81. /* not in free list */
  82. item->next_free = item->prev_free = RT_NULL;
  83. /* initialize mutex lock */
  84. rt_mutex_init(&(memheap->lock), name, RT_IPC_FLAG_FIFO);
  85. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  86. ("memory heap: start addr 0x%08x, size %d, free list header 0x%08x",
  87. start_addr, size, &(memheap->free_header)));
  88. return RT_EOK;
  89. }
  90. RTM_EXPORT(rt_memheap_init);
  91. rt_err_t rt_memheap_detach(struct rt_memheap *heap)
  92. {
  93. RT_ASSERT(heap);
  94. rt_object_detach(&(heap->lock.parent.parent));
  95. rt_object_detach(&(heap->parent));
  96. /* Return a successful completion. */
  97. return RT_EOK;
  98. }
  99. RTM_EXPORT(rt_memheap_detach);
  100. void *rt_memheap_alloc(struct rt_memheap *heap, rt_uint32_t size)
  101. {
  102. rt_err_t result;
  103. rt_uint32_t free_size;
  104. struct rt_memheap_item *header_ptr;
  105. RT_ASSERT(heap != RT_NULL);
  106. /* align allocated size */
  107. size = RT_ALIGN(size, RT_ALIGN_SIZE);
  108. if (size < RT_MEMHEAP_MINIALLOC)
  109. size = RT_MEMHEAP_MINIALLOC;
  110. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("allocate %d", size));
  111. if (size < heap->available_size)
  112. {
  113. /* search on free list */
  114. free_size = 0;
  115. /* lock memheap */
  116. result = rt_mutex_take(&(heap->lock), RT_WAITING_FOREVER);
  117. if (result != RT_EOK)
  118. {
  119. rt_set_errno(result);
  120. return RT_NULL;
  121. }
  122. /* get the first free memory block */
  123. header_ptr = heap->free_list->next_free;
  124. while (header_ptr != heap->free_list && free_size < size)
  125. {
  126. /* get current freed memory block size */
  127. free_size = (rt_uint32_t)(header_ptr->next) - (rt_uint32_t)header_ptr - RT_MEMHEAP_SIZE;
  128. if (free_size < size)
  129. {
  130. /* move to next free memory block */
  131. header_ptr = header_ptr->next_free;
  132. }
  133. }
  134. /* determine if the memory is available. */
  135. if (free_size >= size)
  136. {
  137. /* a block that satisfies the request has been found. */
  138. /* determine if the block needs to be split. */
  139. if (free_size >= (size + RT_MEMHEAP_SIZE + RT_MEMHEAP_MINIALLOC))
  140. {
  141. struct rt_memheap_item *new_ptr;
  142. /* split the block. */
  143. new_ptr = (struct rt_memheap_item *)(((rt_uint8_t *)header_ptr) + size + RT_MEMHEAP_SIZE);
  144. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  145. ("split: h[0x%08x] nm[0x%08x] pm[0x%08x] to n[0x%08x]",
  146. header_ptr,
  147. header_ptr->next,
  148. header_ptr->prev,
  149. new_ptr));
  150. /* mark the new block as a memory block and freed. */
  151. new_ptr->magic = RT_MEMHEAP_MAGIC;
  152. /* put the pool pointer into the new block. */
  153. new_ptr->pool_ptr = heap;
  154. /* break down the block list */
  155. new_ptr->prev = header_ptr;
  156. new_ptr->next = header_ptr->next;
  157. header_ptr->next->prev = new_ptr;
  158. header_ptr->next = new_ptr;
  159. /* remove header ptr from free list */
  160. header_ptr->next_free->prev_free = header_ptr->prev_free;
  161. header_ptr->prev_free->next_free = header_ptr->next_free;
  162. header_ptr->next_free = RT_NULL;
  163. header_ptr->prev_free = RT_NULL;
  164. /* insert new_ptr to free list */
  165. new_ptr->next_free = heap->free_list->next_free;
  166. new_ptr->prev_free = heap->free_list;
  167. heap->free_list->next_free->prev_free = new_ptr;
  168. heap->free_list->next_free = new_ptr;
  169. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("new ptr: nf 0x%08x, pf 0x%08x",
  170. new_ptr->next_free,
  171. new_ptr->prev_free));
  172. /* decrement the available byte count. */
  173. heap->available_size = heap->available_size - size - RT_MEMHEAP_SIZE;
  174. }
  175. else
  176. {
  177. /* decrement the entire free size from the available bytes count. */
  178. heap->available_size = heap->available_size - free_size;
  179. /* remove header_ptr from free list */
  180. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  181. ("one block: h[0x%08x], nf 0x%08x, pf 0x%08x",
  182. header_ptr,
  183. header_ptr->next_free,
  184. header_ptr->prev_free));
  185. header_ptr->next_free->prev_free = header_ptr->prev_free;
  186. header_ptr->prev_free->next_free = header_ptr->next_free;
  187. header_ptr->next_free = RT_NULL;
  188. header_ptr->prev_free = RT_NULL;
  189. }
  190. /* release lock */
  191. rt_mutex_release(&(heap->lock));
  192. /* Mark the allocated block as not available. */
  193. header_ptr->magic |= RT_MEMHEAP_USED;
  194. /* Return a memory address to the caller. */
  195. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  196. ("am: m[0x%08x], h[0x%08x], size: %d",
  197. (void *)((rt_uint8_t *)header_ptr + RT_MEMHEAP_SIZE),
  198. header_ptr,
  199. size);
  200. return (void *)((rt_uint8_t *)header_ptr + RT_MEMHEAP_SIZE));
  201. }
  202. /* release lock */
  203. rt_mutex_release(&(heap->lock));
  204. }
  205. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("allocate memory: failed\n"));
  206. /* Return the completion status. */
  207. return RT_NULL;
  208. }
  209. RTM_EXPORT(rt_memheap_alloc);
  210. void rt_memheap_free(void *ptr)
  211. {
  212. rt_err_t result;
  213. struct rt_memheap *heap;
  214. struct rt_memheap_item *header_ptr, *new_ptr;
  215. rt_uint32_t insert_header;
  216. /* set initial status as OK */
  217. insert_header = 1;
  218. new_ptr = RT_NULL;
  219. header_ptr = (struct rt_memheap_item *)((rt_uint8_t *)ptr - RT_MEMHEAP_SIZE);
  220. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("free memory: m[0x%08x], h[0x%08x]",
  221. ptr, header_ptr));
  222. /* check magic */
  223. RT_ASSERT((header_ptr->magic & RT_MEMHEAP_MASK) == RT_MEMHEAP_MAGIC);
  224. /* get pool ptr */
  225. heap = header_ptr->pool_ptr;
  226. /* lock memheap */
  227. result = rt_mutex_take(&(heap->lock), RT_WAITING_FOREVER);
  228. if (result != RT_EOK)
  229. {
  230. rt_set_errno(result);
  231. return ;
  232. }
  233. /* Mark the memory as available. */
  234. header_ptr->magic &= ~RT_MEMHEAP_USED;
  235. /* Adjust the available number of bytes. */
  236. heap->available_size = heap->available_size +
  237. ((rt_uint32_t)(header_ptr->next) -
  238. (rt_uint32_t)header_ptr) - RT_MEMHEAP_SIZE;
  239. /* Determine if the block can be merged with the previous neighbor. */
  240. if (!RT_MEMHEAP_IS_USED(header_ptr->prev))
  241. {
  242. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP, ("merge: left node 0x%08x",
  243. header_ptr->prev));
  244. /* adjust the available number of bytes. */
  245. heap->available_size = heap->available_size + RT_MEMHEAP_SIZE;
  246. /* yes, merge block with previous neighbor. */
  247. (header_ptr->prev)->next = header_ptr->next;
  248. (header_ptr->next)->prev = header_ptr->prev;
  249. /* move header pointer to previous. */
  250. header_ptr = header_ptr->prev;
  251. /* don't insert header to free list */
  252. insert_header = 0;
  253. }
  254. /* determine if the block can be merged with the next neighbor. */
  255. if (!RT_MEMHEAP_IS_USED(header_ptr->next))
  256. {
  257. /* adjust the available number of bytes. */
  258. heap->available_size = heap->available_size + RT_MEMHEAP_SIZE;
  259. /* merge block with next neighbor. */
  260. new_ptr = header_ptr->next;
  261. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  262. ("merge: right node 0x%08x, nf 0x%08x, pf 0x%08x",
  263. new_ptr, new_ptr->next_free, new_ptr->prev_free));
  264. new_ptr->next->prev = header_ptr;
  265. header_ptr->next = new_ptr->next;
  266. /* remove new ptr from free list */
  267. new_ptr->next_free->prev_free = new_ptr->prev_free;
  268. new_ptr->prev_free->next_free = new_ptr->next_free;
  269. }
  270. if (insert_header)
  271. {
  272. /* no left merge, insert to free list */
  273. header_ptr->next_free = heap->free_list->next_free;
  274. header_ptr->prev_free = heap->free_list;
  275. heap->free_list->next_free->prev_free = header_ptr;
  276. heap->free_list->next_free = header_ptr;
  277. RT_DEBUG_LOG(RT_DEBUG_MEMHEAP,
  278. ("insert to free list: nf 0x%08x, pf 0x%08x",
  279. header_ptr->next_free, header_ptr->prev_free));
  280. }
  281. /* release lock */
  282. rt_mutex_release(&(heap->lock));
  283. }
  284. RTM_EXPORT(rt_memheap_free);
  285. #endif