malloc.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437
  1. /* malloc.c - C standard library routine.
  2. Copyright (c) 1989, 1993 Michael J. Haertel
  3. You may redistribute this library under the terms of the
  4. GNU Library General Public License (version 2 or any later
  5. version) as published by the Free Software Foundation.
  6. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED
  7. WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR
  8. WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS
  9. SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */
  10. #define _GNU_SOURCE
  11. #include <features.h>
  12. #include <limits.h>
  13. #include <stddef.h>
  14. #include <stdlib.h>
  15. #include <string.h>
  16. #include <unistd.h>
  17. #include "malloc.h"
  18. #ifdef __UCLIBC_HAS_THREADS__
  19. #include <pthread.h>
  20. pthread_mutex_t __malloclock = PTHREAD_MUTEX_INITIALIZER;
  21. # define LOCK pthread_mutex_lock(&__malloclock)
  22. # define UNLOCK pthread_mutex_unlock(&__malloclock);
  23. #else
  24. # define LOCK
  25. # define UNLOCK
  26. #endif
  27. /* Stuff that is shared across .o files */
  28. /* Pointer to the base of the first block. */
  29. char *_heapbase;
  30. /* Block information table. */
  31. union info *_heapinfo;
  32. /* Search index in the info table. */
  33. size_t _heapindex;
  34. /* Limit of valid info table indices. */
  35. size_t _heaplimit;
  36. /* List of blocks allocated with memalign or valloc */
  37. struct alignlist *_aligned_blocks;
  38. /* Stuff that is local to this .o file only */
  39. /* How to really get more memory. */
  40. static void * __morecore(long size);
  41. /* Number of info entries. */
  42. static size_t heapsize;
  43. /* Count of large blocks allocated for each fragment size. */
  44. static size_t _fragblocks[BLOCKLOG];
  45. /* Free lists for each fragment size. */
  46. static struct list _fraghead[BLOCKLOG];
  47. /* Are we experienced? */
  48. static int initialized;
  49. /* Aligned allocation.
  50. * Called within the lock in initialize() and morecore(),
  51. * so no explicit locking needed... */
  52. static void * align(size_t size)
  53. {
  54. void *result;
  55. unsigned int adj;
  56. result = __morecore(size);
  57. adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
  58. if (adj != 0) {
  59. __morecore(adj = BLOCKSIZE - adj);
  60. result = (char *) result + adj;
  61. }
  62. return result;
  63. }
  64. /* Set everything up and remember that we have.
  65. * Called within the lock in malloc(), so no
  66. * explicit locking needed... */
  67. static int initialize(void)
  68. {
  69. heapsize = HEAP / BLOCKSIZE;
  70. _heapinfo = align(heapsize * sizeof (union info));
  71. if (!_heapinfo) {
  72. return 0;
  73. }
  74. memset(_heapinfo, 0, heapsize * sizeof (union info));
  75. _heapinfo[0].free.size = 0;
  76. _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
  77. _heapindex = 0;
  78. _heapbase = (char *) _heapinfo;
  79. initialized = 1;
  80. return 1;
  81. }
  82. /* Get neatly aligned memory, initializing or growing the
  83. * heap info table as necessary.
  84. * Called within a lock in malloc() and free(),
  85. * so no explicit locking needed... */
  86. static void * morecore(size_t size)
  87. {
  88. void *result;
  89. union info *newinfo, *oldinfo;
  90. size_t newsize;
  91. result = align(size);
  92. if (!result)
  93. return NULL;
  94. /* Check if we need to grow the info table. */
  95. if (BLOCK((char *) result + size) > heapsize) {
  96. newsize = heapsize;
  97. while (BLOCK((char *) result + size) > newsize)
  98. newsize *= 2;
  99. newinfo = align(newsize * sizeof (union info));
  100. if (!newinfo) {
  101. __morecore(-size);
  102. return NULL;
  103. }
  104. memset(newinfo, 0, newsize * sizeof (union info));
  105. memcpy(newinfo, _heapinfo, heapsize * sizeof (union info));
  106. oldinfo = _heapinfo;
  107. newinfo[BLOCK(oldinfo)].busy.type = 0;
  108. newinfo[BLOCK(oldinfo)].busy.info.size
  109. = BLOCKIFY(heapsize * sizeof (union info));
  110. _heapinfo = newinfo;
  111. __free_unlocked(oldinfo);
  112. heapsize = newsize;
  113. }
  114. _heaplimit = BLOCK((char *) result + size);
  115. return result;
  116. }
  117. /* Note that morecore has to take a signed argument so
  118. that negative values can return memory to the system. */
  119. static void * __morecore(long size)
  120. {
  121. void *result;
  122. result = sbrk(size);
  123. if (result == (void *) -1)
  124. return NULL;
  125. return result;
  126. }
  127. /* Allocate memory from the heap. */
  128. void * malloc (size_t size)
  129. {
  130. void * ptr;
  131. LOCK;
  132. ptr = __malloc_unlocked(size);
  133. UNLOCK;
  134. return(ptr);
  135. }
  136. void * __malloc_unlocked (size_t size)
  137. {
  138. void *result;
  139. size_t log, block, blocks, i, lastblocks, start;
  140. struct list *next;
  141. #if defined(__MALLOC_GLIBC_COMPAT__)
  142. if (size == 0)
  143. size++;
  144. #else
  145. /* Some programs will call malloc (0). Lets be strict and return NULL */
  146. if (size == 0)
  147. return NULL;
  148. #endif
  149. if (size < sizeof (struct list))
  150. size = sizeof (struct list);
  151. if (!initialized && !initialize()) {
  152. return NULL;
  153. }
  154. /* Determine the allocation policy based on the request size. */
  155. if (size <= BLOCKSIZE / 2) {
  156. /* Small allocation to receive a fragment of a block. Determine
  157. the logarithm to base two of the fragment size. */
  158. --size;
  159. for (log = 1; (size >>= 1) != 0; ++log)
  160. ;
  161. /* Look in the fragment lists for a free fragment of the
  162. desired size. */
  163. if ((next = _fraghead[log].next) != 0) {
  164. /* There are free fragments of this size. Pop a fragment
  165. out of the fragment list and return it. Update the block's
  166. nfree and first counters. */
  167. result = next;
  168. next->prev->next = next->next;
  169. if (next->next)
  170. next->next->prev = next->prev;
  171. block = BLOCK(result);
  172. if (--_heapinfo[block].busy.info.frag.nfree)
  173. _heapinfo[block].busy.info.frag.first
  174. = (unsigned int) ((char *) next->next - (char *) NULL)
  175. % BLOCKSIZE >> log;
  176. } else {
  177. /* No free fragments of the desired size, so get a new block
  178. and break it into fragments, returning the first. */
  179. result = __malloc_unlocked(BLOCKSIZE);
  180. if (!result) {
  181. return NULL;
  182. }
  183. ++_fragblocks[log];
  184. /* Link all fragments but the first into the free list. */
  185. next = (struct list *) ((char *) result + (1 << log));
  186. next->next = 0;
  187. next->prev = &_fraghead[log];
  188. _fraghead[log].next = next;
  189. for (i = 2; i < BLOCKSIZE >> log; ++i) {
  190. next = (struct list *) ((char *) result + (i << log));
  191. next->next = _fraghead[log].next;
  192. next->prev = &_fraghead[log];
  193. next->prev->next = next;
  194. next->next->prev = next;
  195. }
  196. /* Initialize the nfree and first counters for this block. */
  197. block = BLOCK(result);
  198. _heapinfo[block].busy.type = log;
  199. _heapinfo[block].busy.info.frag.nfree = i - 1;
  200. _heapinfo[block].busy.info.frag.first = i - 1;
  201. }
  202. } else {
  203. /* Large allocation to receive one or more blocks. Search
  204. the free list in a circle starting at the last place visited.
  205. If we loop completely around without finding a large enough
  206. space we will have to get more memory from the system. */
  207. blocks = BLOCKIFY(size);
  208. start = block = _heapindex;
  209. while (_heapinfo[block].free.size < blocks) {
  210. block = _heapinfo[block].free.next;
  211. if (block == start) {
  212. /* Need to get more from the system. Check to see if
  213. the new core will be contiguous with the final free
  214. block; if so we don't need to get as much. */
  215. block = _heapinfo[0].free.prev;
  216. lastblocks = _heapinfo[block].free.size;
  217. if (_heaplimit && block + lastblocks == _heaplimit
  218. && __morecore(0) == ADDRESS(block + lastblocks)
  219. && morecore((blocks - lastblocks) * BLOCKSIZE)) {
  220. /* Note that morecore() can change the location of
  221. the final block if it moves the info table and the
  222. old one gets coalesced into the final block. */
  223. block = _heapinfo[0].free.prev;
  224. _heapinfo[block].free.size += blocks - lastblocks;
  225. continue;
  226. }
  227. result = morecore(blocks * BLOCKSIZE);
  228. if (!result) {
  229. return NULL;
  230. }
  231. block = BLOCK(result);
  232. _heapinfo[block].busy.type = 0;
  233. _heapinfo[block].busy.info.size = blocks;
  234. return result;
  235. }
  236. }
  237. /* At this point we have found a suitable free list entry.
  238. Figure out how to remove what we need from the list. */
  239. result = ADDRESS(block);
  240. if (_heapinfo[block].free.size > blocks) {
  241. /* The block we found has a bit left over, so relink the
  242. tail end back into the free list. */
  243. _heapinfo[block + blocks].free.size
  244. = _heapinfo[block].free.size - blocks;
  245. _heapinfo[block + blocks].free.next
  246. = _heapinfo[block].free.next;
  247. _heapinfo[block + blocks].free.prev
  248. = _heapinfo[block].free.prev;
  249. _heapinfo[_heapinfo[block].free.prev].free.next
  250. = _heapinfo[_heapinfo[block].free.next].free.prev
  251. = _heapindex = block + blocks;
  252. } else {
  253. /* The block exactly matches our requirements, so
  254. just remove it from the list. */
  255. _heapinfo[_heapinfo[block].free.next].free.prev
  256. = _heapinfo[block].free.prev;
  257. _heapinfo[_heapinfo[block].free.prev].free.next
  258. = _heapindex = _heapinfo[block].free.next;
  259. }
  260. _heapinfo[block].busy.type = 0;
  261. _heapinfo[block].busy.info.size = blocks;
  262. }
  263. return result;
  264. }
  265. /* Return memory to the heap. */
  266. void free(void *ptr)
  267. {
  268. struct alignlist *l;
  269. if (ptr == NULL)
  270. return;
  271. LOCK;
  272. for (l = _aligned_blocks; l != NULL; l = l->next) {
  273. if (l->aligned == ptr) {
  274. /* Mark the block as free */
  275. l->aligned = NULL;
  276. ptr = l->exact;
  277. break;
  278. }
  279. }
  280. __free_unlocked(ptr);
  281. UNLOCK;
  282. }
  283. void __free_unlocked(void *ptr)
  284. {
  285. int block, blocks, i, type;
  286. struct list *prev, *next;
  287. if (ptr == NULL)
  288. return;
  289. block = BLOCK(ptr);
  290. switch (type = _heapinfo[block].busy.type) {
  291. case 0:
  292. /* Find the free cluster previous to this one in the free list.
  293. Start searching at the last block referenced; this may benefit
  294. programs with locality of allocation. */
  295. i = _heapindex;
  296. if (i > block)
  297. while (i > block)
  298. i = _heapinfo[i].free.prev;
  299. else {
  300. do
  301. i = _heapinfo[i].free.next;
  302. while (i > 0 && i < block);
  303. i = _heapinfo[i].free.prev;
  304. }
  305. /* Determine how to link this block into the free list. */
  306. if (block == i + _heapinfo[i].free.size) {
  307. /* Coalesce this block with its predecessor. */
  308. _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
  309. block = i;
  310. } else {
  311. /* Really link this block back into the free list. */
  312. _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
  313. _heapinfo[block].free.next = _heapinfo[i].free.next;
  314. _heapinfo[block].free.prev = i;
  315. _heapinfo[i].free.next = block;
  316. _heapinfo[_heapinfo[block].free.next].free.prev = block;
  317. }
  318. /* Now that the block is linked in, see if we can coalesce it
  319. with its successor (by deleting its successor from the list
  320. and adding in its size). */
  321. if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) {
  322. _heapinfo[block].free.size
  323. += _heapinfo[_heapinfo[block].free.next].free.size;
  324. _heapinfo[block].free.next
  325. = _heapinfo[_heapinfo[block].free.next].free.next;
  326. _heapinfo[_heapinfo[block].free.next].free.prev = block;
  327. }
  328. /* Now see if we can return stuff to the system. */
  329. blocks = _heapinfo[block].free.size;
  330. if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
  331. && __morecore(0) == ADDRESS(block + blocks)) {
  332. _heaplimit -= blocks;
  333. __morecore(-blocks * BLOCKSIZE);
  334. _heapinfo[_heapinfo[block].free.prev].free.next
  335. = _heapinfo[block].free.next;
  336. _heapinfo[_heapinfo[block].free.next].free.prev
  337. = _heapinfo[block].free.prev;
  338. block = _heapinfo[block].free.prev;
  339. }
  340. /* Set the next search to begin at this block. */
  341. _heapindex = block;
  342. break;
  343. default:
  344. /* Get the address of the first free fragment in this block. */
  345. prev = (struct list *) ((char *) ADDRESS(block)
  346. + (_heapinfo[block].busy.info.frag.first
  347. << type));
  348. if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1
  349. && _fragblocks[type] > 1) {
  350. /* If all fragments of this block are free, remove them
  351. from the fragment list and free the whole block. */
  352. --_fragblocks[type];
  353. for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i)
  354. next = next->next;
  355. prev->prev->next = next;
  356. if (next)
  357. next->prev = prev->prev;
  358. _heapinfo[block].busy.type = 0;
  359. _heapinfo[block].busy.info.size = 1;
  360. __free_unlocked(ADDRESS(block));
  361. } else if (_heapinfo[block].busy.info.frag.nfree) {
  362. /* If some fragments of this block are free, link this fragment
  363. into the fragment list after the first free fragment of
  364. this block. */
  365. next = ptr;
  366. next->next = prev->next;
  367. next->prev = prev;
  368. prev->next = next;
  369. if (next->next)
  370. next->next->prev = next;
  371. ++_heapinfo[block].busy.info.frag.nfree;
  372. } else {
  373. /* No fragments of this block are free, so link this fragment
  374. into the fragment list and announce that it is the first
  375. free fragment of this block. */
  376. prev = (struct list *) ptr;
  377. _heapinfo[block].busy.info.frag.nfree = 1;
  378. _heapinfo[block].busy.info.frag.first
  379. = (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE
  380. >> type;
  381. prev->next = _fraghead[type].next;
  382. prev->prev = &_fraghead[type];
  383. prev->prev->next = prev;
  384. if (prev->next)
  385. prev->next->prev = prev;
  386. }
  387. break;
  388. }
  389. }