malloc.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189
  1. /* replace undef by define */
  2. #undef DEBUG /* check assertions */
  3. #undef SLOWDEBUG /* some extra test loops (requires DEBUG) */
  4. #ifdef DEBUG
  5. #define ASSERT(b) if (!(b)) assert_failed();
  6. #else
  7. #define ASSERT(b) /* empty */
  8. #endif
  9. #if _EM_WSIZE == _EM_PSIZE
  10. #define ptrint int
  11. #else
  12. #define ptrint long
  13. #endif
  14. #if _EM_PSIZE == 2
  15. #define BRKSIZE 1024
  16. #else
  17. #define BRKSIZE 4096
  18. #endif
  19. #define PTRSIZE sizeof(char *)
  20. #define Align(x,a) (((x) + (a - 1)) & ~(ptrint)(a - 1))
  21. #define NextSlot(p) (* (char **) ((p) - PTRSIZE))
  22. #define NextFree(p) (* (char **) (p))
  23. /*
  24. * A short explanation of the data structure and algorithms.
  25. * An area returned by malloc() is called a slot. Each slot
  26. * contains the number of bytes requested, but preceeded by
  27. * an extra pointer to the next the slot in memory.
  28. * '_bottom' and '_top' point to the first/last slot.
  29. * More memory is asked for using brk() and appended to top.
  30. * The list of free slots is maintained to keep malloc() fast.
  31. * '_empty' points the the first free slot. Free slots are
  32. * linked together by a pointer at the start of the
  33. * user visable part, so just after the next-slot pointer.
  34. * Free slots are merged together by free().
  35. */
  36. extern char *sbrk(), *brk();
  37. static char *_bottom, *_top, *_empty;
  38. static grow(len)
  39. unsigned len;
  40. {
  41. register char *p;
  42. ASSERT(NextSlot(_top) == 0);
  43. p = (char *) Align((ptrint)_top + len, BRKSIZE);
  44. if (p < _top || brk(p) != 0)
  45. return(0);
  46. NextSlot(_top) = p;
  47. NextSlot(p) = 0;
  48. free(_top);
  49. _top = p;
  50. return(1);
  51. }
  52. char *malloc(size)
  53. unsigned size;
  54. {
  55. register char *prev, *p, *next, *new;
  56. register unsigned len, ntries;
  57. if (size == 0)
  58. size = PTRSIZE; /* avoid slots less that 2*PTRSIZE */
  59. for (ntries = 0; ntries < 2; ntries++) {
  60. len = Align(size, PTRSIZE) + PTRSIZE;
  61. if (_bottom == 0) {
  62. p = sbrk(2 * PTRSIZE);
  63. p = (char *) Align((ptrint)p, PTRSIZE);
  64. p += PTRSIZE;
  65. _top = _bottom = p;
  66. NextSlot(p) = 0;
  67. }
  68. #ifdef SLOWDEBUG
  69. for (p = _bottom; (next = NextSlot(p)) != 0; p = next)
  70. ASSERT(next > p);
  71. ASSERT(p == _top);
  72. #endif
  73. for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
  74. next = NextSlot(p);
  75. new = p + len;
  76. if (new > next)
  77. continue; /* too small */
  78. if (new + PTRSIZE < next) { /* too big, so split */
  79. /* + PTRSIZE avoids tiny slots on free list */
  80. NextSlot(new) = next;
  81. NextSlot(p) = new;
  82. NextFree(new) = NextFree(p);
  83. NextFree(p) = new;
  84. }
  85. if (prev)
  86. NextFree(prev) = NextFree(p);
  87. else
  88. _empty = NextFree(p);
  89. return(p);
  90. }
  91. if (grow(len) == 0)
  92. break;
  93. }
  94. ASSERT(ntries != 2);
  95. return(0);
  96. }
  97. char *realloc(old, size)
  98. char *old;
  99. unsigned size;
  100. {
  101. register char *prev, *p, *next, *new;
  102. register unsigned len, n;
  103. len = Align(size, PTRSIZE) + PTRSIZE;
  104. next = NextSlot(old);
  105. n = (int)(next - old); /* old length */
  106. /*
  107. * extend old if there is any free space just behind it
  108. */
  109. for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
  110. if (p > next)
  111. break;
  112. if (p == next) { /* 'next' is a free slot: merge */
  113. NextSlot(old) = NextSlot(p);
  114. if (prev)
  115. NextFree(prev) = NextFree(p);
  116. else
  117. _empty = NextFree(p);
  118. next = NextSlot(old);
  119. break;
  120. }
  121. }
  122. new = old + len;
  123. /*
  124. * Can we use the old, possibly extended slot?
  125. */
  126. if (new <= next) { /* it does fit */
  127. if (new + PTRSIZE < next) { /* too big, so split */
  128. /* + PTRSIZE avoids tiny slots on free list */
  129. NextSlot(new) = next;
  130. NextSlot(old) = new;
  131. free(new);
  132. }
  133. return(old);
  134. }
  135. if ((new = malloc(size)) == 0) /* it didn't fit */
  136. return(0);
  137. bcopy(old, new, n); /* n < size */
  138. free(old);
  139. return(new);
  140. }
  141. free(p)
  142. char *p;
  143. {
  144. register char *prev, *next;
  145. ASSERT(NextSlot(p) > p);
  146. for (prev = 0, next = _empty; next != 0; prev = next, next = NextFree(next))
  147. if (p < next)
  148. break;
  149. NextFree(p) = next;
  150. if (prev)
  151. NextFree(prev) = p;
  152. else
  153. _empty = p;
  154. if (next) {
  155. ASSERT(NextSlot(p) <= next);
  156. if (NextSlot(p) == next) { /* merge p and next */
  157. NextSlot(p) = NextSlot(next);
  158. NextFree(p) = NextFree(next);
  159. }
  160. }
  161. if (prev) {
  162. ASSERT(NextSlot(prev) <= p);
  163. if (NextSlot(prev) == p) { /* merge prev and p */
  164. NextSlot(prev) = NextSlot(p);
  165. NextFree(prev) = NextFree(p);
  166. }
  167. }
  168. }
  169. #ifdef DEBUG
  170. static assert_failed()
  171. {
  172. write(2, "assert failed in lib/malloc.c\n", 30);
  173. abort();
  174. }
  175. #endif