malloc.c 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254
  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. #include <limits.h>
  11. #include <stddef.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include "malloc.h"
  15. /* How to really get more memory. */
  16. void *(*__morecore)(long) = __default_morecore_init;
  17. /* Pointer to the base of the first block. */
  18. char *_heapbase;
  19. /* Block information table. */
  20. union info *_heapinfo;
  21. /* Number of info entries. */
  22. static int heapsize;
  23. /* Search index in the info table. */
  24. int _heapindex;
  25. /* Limit of valid info table indices. */
  26. int _heaplimit;
  27. /* Count of large blocks allocated for each fragment size. */
  28. int _fragblocks[BLOCKLOG];
  29. /* Free lists for each fragment size. */
  30. struct list _fraghead[BLOCKLOG];
  31. /* Are we experienced? */
  32. static int initialized;
  33. /* Aligned allocation. */
  34. static void *
  35. align(size_t size)
  36. {
  37. void *result;
  38. unsigned int adj;
  39. result = (*__morecore)(size);
  40. adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
  41. if (adj != 0) {
  42. (*__morecore)(adj = BLOCKSIZE - adj);
  43. result = (char *) result + adj;
  44. }
  45. return result;
  46. }
  47. /* Set everything up and remember that we have. */
  48. static int
  49. initialize(void)
  50. {
  51. heapsize = HEAP / BLOCKSIZE;
  52. _heapinfo = align(heapsize * sizeof (union info));
  53. if (!_heapinfo)
  54. return 0;
  55. memset(_heapinfo, 0, heapsize * sizeof (union info));
  56. _heapinfo[0].free.size = 0;
  57. _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
  58. _heapindex = 0;
  59. _heapbase = (char *) _heapinfo;
  60. initialized = 1;
  61. return 1;
  62. }
  63. /* Get neatly aligned memory, initializing or growing the
  64. heap info table as necessary. */
  65. static void *
  66. morecore(size_t size)
  67. {
  68. void *result;
  69. union info *newinfo, *oldinfo;
  70. int newsize;
  71. result = align(size);
  72. if (!result)
  73. return NULL;
  74. /* Check if we need to grow the info table. */
  75. if (BLOCK((char *) result + size) > heapsize) {
  76. newsize = heapsize;
  77. while (BLOCK((char *) result + size) > newsize)
  78. newsize *= 2;
  79. newinfo = align(newsize * sizeof (union info));
  80. if (!newinfo) {
  81. (*__morecore)(-size);
  82. return NULL;
  83. }
  84. memset(newinfo, 0, newsize * sizeof (union info));
  85. memcpy(newinfo, _heapinfo, heapsize * sizeof (union info));
  86. oldinfo = _heapinfo;
  87. newinfo[BLOCK(oldinfo)].busy.type = 0;
  88. newinfo[BLOCK(oldinfo)].busy.info.size
  89. = BLOCKIFY(heapsize * sizeof (union info));
  90. _heapinfo = newinfo;
  91. #if 0
  92. free(oldinfo);
  93. #else
  94. _free_internal (oldinfo);
  95. #endif
  96. heapsize = newsize;
  97. }
  98. _heaplimit = BLOCK((char *) result + size);
  99. return result;
  100. }
  101. /* Allocate memory from the heap. */
  102. void *
  103. malloc (size_t size)
  104. {
  105. void *result;
  106. int log, block, blocks, i, lastblocks, start;
  107. struct list *next;
  108. if (!initialized && !initialize())
  109. return NULL;
  110. #if 1
  111. /* Some programs will call malloc (0). Lets be strict and return NULL */
  112. if (size == 0)
  113. return NULL;
  114. #endif
  115. if (size < sizeof (struct list))
  116. size = sizeof (struct list);
  117. /* Determine the allocation policy based on the request size. */
  118. if (size <= BLOCKSIZE / 2) {
  119. /* Small allocation to receive a fragment of a block. Determine
  120. the logarithm to base two of the fragment size. */
  121. --size;
  122. for (log = 1; (size >>= 1) != 0; ++log)
  123. ;
  124. /* Look in the fragment lists for a free fragment of the
  125. desired size. */
  126. if ((next = _fraghead[log].next) != 0) {
  127. /* There are free fragments of this size. Pop a fragment
  128. out of the fragment list and return it. Update the block's
  129. nfree and first counters. */
  130. result = next;
  131. next->prev->next = next->next;
  132. if (next->next)
  133. next->next->prev = next->prev;
  134. block = BLOCK(result);
  135. if (--_heapinfo[block].busy.info.frag.nfree)
  136. _heapinfo[block].busy.info.frag.first
  137. = (unsigned int) ((char *) next->next - (char *) NULL)
  138. % BLOCKSIZE >> log;
  139. } else {
  140. /* No free fragments of the desired size, so get a new block
  141. and break it into fragments, returning the first. */
  142. result = malloc(BLOCKSIZE);
  143. if (!result)
  144. return NULL;
  145. ++_fragblocks[log];
  146. /* Link all fragments but the first into the free list. */
  147. next = (struct list *) ((char *) result + (1 << log));
  148. next->next = 0;
  149. next->prev = &_fraghead[log];
  150. _fraghead[log].next = next;
  151. for (i = 2; i < BLOCKSIZE >> log; ++i) {
  152. next = (struct list *) ((char *) result + (i << log));
  153. next->next = _fraghead[log].next;
  154. next->prev = &_fraghead[log];
  155. next->prev->next = next;
  156. next->next->prev = next;
  157. }
  158. /* Initialize the nfree and first counters for this block. */
  159. block = BLOCK(result);
  160. _heapinfo[block].busy.type = log;
  161. _heapinfo[block].busy.info.frag.nfree = i - 1;
  162. _heapinfo[block].busy.info.frag.first = i - 1;
  163. }
  164. } else {
  165. /* Large allocation to receive one or more blocks. Search
  166. the free list in a circle starting at the last place visited.
  167. If we loop completely around without finding a large enough
  168. space we will have to get more memory from the system. */
  169. blocks = BLOCKIFY(size);
  170. start = block = _heapindex;
  171. while (_heapinfo[block].free.size < blocks) {
  172. block = _heapinfo[block].free.next;
  173. if (block == start) {
  174. /* Need to get more from the system. Check to see if
  175. the new core will be contiguous with the final free
  176. block; if so we don't need to get as much. */
  177. block = _heapinfo[0].free.prev;
  178. lastblocks = _heapinfo[block].free.size;
  179. if (_heaplimit && block + lastblocks == _heaplimit
  180. && (*__morecore)(0) == ADDRESS(block + lastblocks)
  181. && morecore((blocks - lastblocks) * BLOCKSIZE)) {
  182. /* Note that morecore() can change the location of
  183. the final block if it moves the info table and the
  184. old one gets coalesced into the final block. */
  185. block = _heapinfo[0].free.prev;
  186. _heapinfo[block].free.size += blocks - lastblocks;
  187. continue;
  188. }
  189. result = morecore(blocks * BLOCKSIZE);
  190. if (!result)
  191. return NULL;
  192. block = BLOCK(result);
  193. _heapinfo[block].busy.type = 0;
  194. _heapinfo[block].busy.info.size = blocks;
  195. return result;
  196. }
  197. }
  198. /* At this point we have found a suitable free list entry.
  199. Figure out how to remove what we need from the list. */
  200. result = ADDRESS(block);
  201. if (_heapinfo[block].free.size > blocks) {
  202. /* The block we found has a bit left over, so relink the
  203. tail end back into the free list. */
  204. _heapinfo[block + blocks].free.size
  205. = _heapinfo[block].free.size - blocks;
  206. _heapinfo[block + blocks].free.next
  207. = _heapinfo[block].free.next;
  208. _heapinfo[block + blocks].free.prev
  209. = _heapinfo[block].free.prev;
  210. _heapinfo[_heapinfo[block].free.prev].free.next
  211. = _heapinfo[_heapinfo[block].free.next].free.prev
  212. = _heapindex = block + blocks;
  213. } else {
  214. /* The block exactly matches our requirements, so
  215. just remove it from the list. */
  216. _heapinfo[_heapinfo[block].free.next].free.prev
  217. = _heapinfo[block].free.prev;
  218. _heapinfo[_heapinfo[block].free.prev].free.next
  219. = _heapindex = _heapinfo[block].free.next;
  220. }
  221. _heapinfo[block].busy.type = 0;
  222. _heapinfo[block].busy.info.size = blocks;
  223. }
  224. return result;
  225. }