malloc.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. /*
  2. * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands.
  3. *
  4. * This product is part of the Amsterdam Compiler Kit.
  5. *
  6. * Permission to use, sell, duplicate or disclose this software must be
  7. * obtained in writing. Requests for such permissions may be sent to
  8. *
  9. * Dr. Andrew S. Tanenbaum
  10. * Wiskundig Seminarium
  11. * Vrije Universiteit
  12. * Postbox 7161
  13. * 1007 MC Amsterdam
  14. * The Netherlands
  15. *
  16. */
  17. #include "ack.h"
  18. #ifdef DEBUG
  19. #define ASSERT(p) if(!(p))botch("p");else
  20. botch(s)
  21. char *s;
  22. {
  23. printf("malloc/free botched: %s\n",s);
  24. abort();
  25. }
  26. #else
  27. #define ASSERT(p)
  28. #endif
  29. #ifndef NORCSID
  30. static char rcs_id[] = "$Header$" ;
  31. #endif
  32. /* avoid break bug */
  33. #ifdef pdp11
  34. #define GRANULE 64
  35. #else
  36. #define GRANULE 0
  37. #endif
  38. /* C storage allocator
  39. * circular first-fit strategy
  40. * works with noncontiguous, but monotonically linked, arena
  41. * each block is preceded by a ptr to the (pointer of)
  42. * the next following block
  43. * blocks are exact number of words long
  44. * aligned to the data type requirements of ALIGN
  45. * pointers to blocks must have BUSY bit 0
  46. * bit in ptr is 1 for busy, 0 for idle
  47. * gaps in arena are merely noted as busy blocks
  48. * last block of arena (pointed to by alloct) is empty and
  49. * has a pointer to first
  50. * idle blocks are coalesced during space search
  51. *
  52. * a different implementation may need to redefine
  53. * ALIGN, NALIGN, BLOCK, BUSY, INT
  54. * where INT is integer type to which a pointer can be cast
  55. */
  56. #define INT int
  57. #define ALIGN int
  58. #define NALIGN 1
  59. #define WORD sizeof(union store)
  60. #define BLOCK 1024 /* a multiple of WORD*/
  61. #define BUSY 1
  62. #define NULL 0
  63. #define testbusy(p) ((INT)(p)&BUSY)
  64. #define setbusy(p) (union store *)((INT)(p)|BUSY)
  65. #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  66. union store { union store *ptr;
  67. ALIGN dummy[NALIGN];
  68. int calloc; /*calloc clears an array of integers*/
  69. };
  70. static union store allocs[2]; /*initial arena*/
  71. static union store *allocp; /*search ptr*/
  72. static union store *alloct; /*arena top*/
  73. static union store *allocx; /*for benefit of realloc*/
  74. char *sbrk();
  75. char *
  76. malloc(nbytes)
  77. unsigned nbytes;
  78. {
  79. register union store *p, *q;
  80. register nw;
  81. static temp; /*coroutines assume no auto*/
  82. if(allocs[0].ptr==0) { /*first time*/
  83. allocs[0].ptr = setbusy(&allocs[1]);
  84. allocs[1].ptr = setbusy(&allocs[0]);
  85. alloct = &allocs[1];
  86. allocp = &allocs[0];
  87. }
  88. nw = (nbytes+WORD+WORD-1)/WORD;
  89. ASSERT(allocp>=allocs && allocp<=alloct);
  90. ASSERT(allock());
  91. for(p=allocp; ; ) {
  92. for(temp=0; ; ) {
  93. if(!testbusy(p->ptr)) {
  94. while(!testbusy((q=p->ptr)->ptr)) {
  95. ASSERT(q>p&&q<alloct);
  96. p->ptr = q->ptr;
  97. }
  98. if(q>=p+nw && p+nw>=p)
  99. goto found;
  100. }
  101. q = p;
  102. p = clearbusy(p->ptr);
  103. if(p>q)
  104. ASSERT(p<=alloct);
  105. else if(q!=alloct || p!=allocs) {
  106. ASSERT(q==alloct&&p==allocs);
  107. return(NULL);
  108. } else if(++temp>1)
  109. break;
  110. }
  111. temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
  112. q = (union store *)sbrk(0);
  113. if(q+temp+GRANULE < q) {
  114. return(NULL);
  115. }
  116. q = (union store *)sbrk(temp*WORD);
  117. if((INT)q == -1) {
  118. return(NULL);
  119. }
  120. ASSERT(q>alloct);
  121. alloct->ptr = q;
  122. if(q!=alloct+1)
  123. alloct->ptr = setbusy(alloct->ptr);
  124. alloct = q->ptr = q+temp-1;
  125. alloct->ptr = setbusy(allocs);
  126. }
  127. found:
  128. allocp = p + nw;
  129. ASSERT(allocp<=alloct);
  130. if(q>allocp) {
  131. allocx = allocp->ptr;
  132. allocp->ptr = p->ptr;
  133. }
  134. p->ptr = setbusy(allocp);
  135. return((char *)(p+1));
  136. }
  137. /* freeing strategy tuned for LIFO allocation
  138. */
  139. free(ap)
  140. register char *ap;
  141. {
  142. register union store *p = (union store *)ap;
  143. ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
  144. ASSERT(allock());
  145. allocp = --p;
  146. ASSERT(testbusy(p->ptr));
  147. p->ptr = clearbusy(p->ptr);
  148. ASSERT(p->ptr > allocp && p->ptr <= alloct);
  149. }
  150. /* realloc(p, nbytes) reallocates a block obtained from malloc()
  151. * and freed since last call of malloc()
  152. * to have new size nbytes, and old content
  153. * returns new location, or 0 on failure
  154. */
  155. char *
  156. realloc(p, nbytes)
  157. register union store *p;
  158. unsigned nbytes;
  159. {
  160. register union store *q;
  161. union store *s, *t;
  162. register unsigned nw;
  163. unsigned onw;
  164. if(testbusy(p[-1].ptr))
  165. free((char *)p);
  166. onw = p[-1].ptr - p;
  167. q = (union store *)malloc(nbytes);
  168. if(q==NULL || q==p)
  169. return((char *)q);
  170. s = p;
  171. t = q;
  172. nw = (nbytes+WORD-1)/WORD;
  173. if(nw<onw)
  174. onw = nw;
  175. while(onw--!=0)
  176. *t++ = *s++;
  177. if(q<p && q+nw>=p)
  178. (q+(q+nw-p))->ptr = allocx;
  179. return((char *)q);
  180. }
  181. #ifdef DEBUG
  182. allock()
  183. {
  184. #ifdef DEBUG
  185. register union store *p;
  186. int x;
  187. x = 0;
  188. for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
  189. if(p==allocp)
  190. x++;
  191. }
  192. ASSERT(p==alloct);
  193. return(x==1|p==allocp);
  194. #else
  195. return(1);
  196. #endif
  197. }
  198. #endif