mal.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298
  1. /* $Header$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. #include "param.h"
  7. #include "impl.h"
  8. #include "check.h"
  9. #include "log.h"
  10. #include "phys.h"
  11. /* Malloc space is traversed by N doubly-linked lists of chunks, each
  12. containing a couple of house-keeping data addressed as a
  13. 'mallink' and a piece of useful space, called the block.
  14. The N lists are accessed through their starting pointers in
  15. free_list[]. Free_list[n] points to a list of chunks between
  16. 2**(n+LOG_MIN_SIZE) and 2**(n+LOG_MIN_SIZE+1)-1, which means
  17. that the smallest chunk is 2**LOG_MIN_SIZE (== MIN_SIZE).
  18. */
  19. #ifdef SYSTEM
  20. #include <system.h>
  21. #define SBRK sys_break
  22. #else
  23. #define SBRK sbrk
  24. #define ILL_BREAK (char *)(-1) /* funny failure value */
  25. #endif
  26. extern char *SBRK();
  27. #ifdef STORE
  28. #define MAX_STORE 32
  29. private do_free(), sell_out();
  30. privatedata mallink *store[MAX_STORE];
  31. #endif STORE
  32. char *
  33. malloc(n)
  34. register unsigned int n;
  35. {check_mallinks("malloc entry");{
  36. register mallink *ml;
  37. register int min_class;
  38. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  39. #ifdef STORE
  40. if (n <= MAX_STORE*MIN_SIZE) {
  41. /* look in the store first */
  42. register mallink **stp = &store[(n >> LOG_MIN_SIZE) - 1];
  43. if (ml = *stp) {
  44. *stp = log_next_of(ml);
  45. check_mallinks("malloc fast exit");
  46. return block_of_mallink(ml);
  47. }
  48. }
  49. #endif STORE
  50. check_work_empty("malloc, entry");
  51. /* Acquire a chunk of at least size n if at all possible;
  52. Try everything.
  53. */
  54. {
  55. /* Inline substitution of "smallest".
  56. */
  57. register unsigned int n1 = n;
  58. assert(n1 < (1 << LOG_MAX_SIZE));
  59. min_class = 0;
  60. while (n1 >= MIN_SIZE) {
  61. n1 >>= 1;
  62. min_class++;
  63. }
  64. }
  65. if (min_class >= MAX_FLIST)
  66. return (char *) 0; /* we don't deal in blocks that big */
  67. ml = first_present(min_class);
  68. if (ml == MAL_NULL) {
  69. /* Try and extend */
  70. register char *p;
  71. #define GRABSIZE 4096 /* Power of 2 */
  72. register unsigned int req =
  73. (n+mallink_size()+GRABSIZE-1)&~(GRABSIZE-1);
  74. if (!ml_last) {
  75. /* first align SBRK() */
  76. p = SBRK(0);
  77. SBRK((int) (align((size_type) p) - (size_type) p));
  78. }
  79. p = SBRK((int)req);
  80. if (p == ILL_BREAK) {
  81. /* Now this is bad. The system will not give us
  82. more memory. We can only liquidate our store
  83. and hope it helps.
  84. */
  85. #ifdef STORE
  86. sell_out();
  87. ml = first_present(min_class);
  88. if (ml == MAL_NULL) {
  89. #endif STORE
  90. /* In this emergency we try to locate a suitable
  91. chunk in the free_list just below the safe
  92. one; some of these chunks may fit the job.
  93. */
  94. ml = search_free_list(min_class - 1, n);
  95. if (!ml) /* really out of space */
  96. return (char *) 0;
  97. started_working_on(ml);
  98. unlink_free_chunk(ml);
  99. check_mallinks("suitable_chunk, forced");
  100. #ifdef STORE
  101. }
  102. else started_working_on(ml);
  103. #endif STORE
  104. }
  105. else {
  106. ml = create_chunk(p, req);
  107. }
  108. check_mallinks("suitable_chunk, extended");
  109. }
  110. else started_working_on(ml);
  111. /* we have a chunk */
  112. set_free(ml, 0);
  113. calc_checksum(ml);
  114. check_mallinks("suitable_chunk, removed");
  115. n += mallink_size();
  116. if (n + MIN_SIZE <= size_of(ml)) {
  117. truncate(ml, n);
  118. }
  119. stopped_working_on(ml);
  120. check_mallinks("malloc exit");
  121. check_work_empty("malloc exit");
  122. return block_of_mallink(ml);
  123. }}
  124. free(addr)
  125. char *addr;
  126. {check_mallinks("free entry");{
  127. register mallink *ml = mallink_of_block(addr);
  128. #ifdef STORE
  129. if (free_of(ml))
  130. return; /* user frees free block */
  131. if (size_of(ml) <= MAX_STORE*MIN_SIZE) {
  132. /* return to store */
  133. mallink **stp = &store[(size_of(ml) >> LOG_MIN_SIZE) - 1];
  134. set_log_next(ml, *stp);
  135. *stp = ml;
  136. check_mallinks("free fast exit");
  137. }
  138. else {
  139. do_free(ml);
  140. check_mallinks("free exit");
  141. }
  142. }}
  143. private
  144. do_free(ml)
  145. register mallink *ml;
  146. {{
  147. #endif
  148. #ifndef STORE
  149. if (free_of(ml)) return;
  150. #endif STORE
  151. started_working_on(ml);
  152. set_free(ml, 1);
  153. calc_checksum(ml);
  154. if (! last_mallink(ml)) {
  155. register mallink *next = phys_next_of(ml);
  156. if (free_of(next)) coalesce_forw(ml, next);
  157. }
  158. if (! first_mallink(ml)) {
  159. register mallink *prev = phys_prev_of(ml);
  160. if (free_of(prev)) {
  161. coalesce_backw(ml, prev);
  162. ml = prev;
  163. }
  164. }
  165. link_free_chunk(ml);
  166. stopped_working_on(ml);
  167. check_work_empty("free");
  168. /* Compile-time checks on param.h */
  169. switch (0) {
  170. case MIN_SIZE < OFF_SET * sizeof(mallink): break;
  171. case 1: break;
  172. /* If this statement does not compile due to duplicate case
  173. entry, the minimum size block cannot hold the links for
  174. the free blocks. Either raise LOG_MIN_SIZE or switch
  175. off NON_STANDARD.
  176. */
  177. }
  178. switch(0) {
  179. case sizeof(char *) != sizeof(size_type): break;
  180. case 1: break;
  181. /* If this statement does not compile due to duplicate
  182. case entry, size_type is not defined correctly.
  183. Redefine and compile again.
  184. */
  185. }
  186. }}
  187. char *
  188. realloc(addr, n)
  189. char *addr;
  190. register unsigned int n;
  191. {check_mallinks("realloc entry");{
  192. register mallink *ml = mallink_of_block(addr), *ph_next;
  193. register unsigned int size;
  194. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  195. if (free_of(ml)) {
  196. unlink_free_chunk(ml);
  197. set_free(ml, 0); /* user reallocs free block */
  198. }
  199. started_working_on(ml);
  200. size = size_of(ml);
  201. if ( /* we can simplify the problem by adding the next chunk: */
  202. n > size &&
  203. !last_mallink(ml) &&
  204. (ph_next = phys_next_of(ml), free_of(ph_next)) &&
  205. n <= size + mallink_size() + size_of(ph_next)
  206. ) {
  207. /* add in the physically next chunk */
  208. unlink_free_chunk(ph_next);
  209. combine_chunks(ml, ph_next);
  210. size = size_of(ml);
  211. check_mallinks("realloc, combining");
  212. }
  213. if (n > size) { /* this didn't help */
  214. char *new;
  215. register char *l1, *l2 = addr;
  216. stopped_working_on(ml);
  217. if (!(new = l1 = malloc(n))) return (char *) 0; /* no way */
  218. while (size--) *l1++ = *l2++;
  219. free(addr);
  220. check_work_empty("mv_realloc");
  221. return new;
  222. }
  223. /* it helped, but maybe too well */
  224. n += mallink_size();
  225. if (n + MIN_SIZE <= size_of(ml)) {
  226. truncate(ml, n);
  227. }
  228. stopped_working_on(ml);
  229. check_mallinks("realloc exit");
  230. check_work_empty("realloc");
  231. return addr;
  232. }}
  233. /* Auxiliary routines */
  234. #ifdef STORE
  235. private
  236. sell_out() {
  237. /* Frees all block in store.
  238. */
  239. register mallink **stp;
  240. for (stp = &store[0]; stp < &store[MAX_STORE]; stp++) {
  241. register mallink *ml = *stp;
  242. while (ml) {
  243. *stp = log_next_of(ml);
  244. do_free(ml);
  245. ml = *stp;
  246. }
  247. }
  248. }
  249. #endif STORE
  250. #ifdef ASSERT
  251. public
  252. m_assert(fn, ln)
  253. char *fn;
  254. {
  255. char ch;
  256. while (*fn)
  257. write(2, fn++, 1);
  258. write(2, ": malloc assert failed in line ", 31);
  259. ch = (ln / 100) + '0'; write(2, &ch, 1); ln %= 100;
  260. ch = (ln / 10) + '0'; write(2, &ch, 1); ln %= 10;
  261. ch = (ln / 1) + '0'; write(2, &ch, 1);
  262. write(2, "\n", 1);
  263. maldump(1);
  264. }
  265. #endif ASSERT