mal.c 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361
  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. #define MAX_SZ_IN_STORE (MAX_STORE*ALIGNMENT)
  30. private do_free(), sell_out();
  31. privatedata mallink *store[MAX_STORE];
  32. #endif /* STORE */
  33. char *
  34. malloc(n)
  35. register unsigned int n;
  36. {check_mallinks("malloc entry");{
  37. register mallink *ml;
  38. register int min_class;
  39. if (n == 0) {
  40. return 0;
  41. }
  42. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  43. #ifdef STORE
  44. if (n <= MAX_SZ_IN_STORE) {
  45. /* look in the store first */
  46. register mallink **stp = &store[(n >> LOG_ALIGNMENT) - 1];
  47. if (ml = *stp) {
  48. *stp = log_next_of(ml);
  49. set_store(ml, 0);
  50. check_mallinks("malloc fast exit");
  51. assert(! in_store(ml));
  52. return block_of_mallink(ml);
  53. }
  54. }
  55. #endif /* STORE */
  56. check_work_empty("malloc, entry");
  57. /* Acquire a chunk of at least size n if at all possible;
  58. Try everything.
  59. */
  60. {
  61. /* Inline substitution of "smallest".
  62. */
  63. register unsigned int n1 = n;
  64. assert(n1 < (1L << LOG_MAX_SIZE));
  65. min_class = 0;
  66. do {
  67. n1 >>= 1;
  68. min_class++;
  69. } while (n1 >= MIN_SIZE);
  70. }
  71. if (min_class >= MAX_FLIST)
  72. return (char *) 0; /* we don't deal in blocks that big */
  73. ml = first_present(min_class);
  74. if (ml == MAL_NULL) {
  75. /* Try and extend */
  76. register char *p;
  77. #define GRABSIZE 4096 /* Power of 2 */
  78. register unsigned int req =
  79. ((MIN_SIZE<<min_class)+ mallink_size() + GRABSIZE - 1) &
  80. ~(GRABSIZE-1);
  81. if (!ml_last) {
  82. /* first align SBRK() */
  83. p = SBRK(0);
  84. SBRK((int) (align((size_type) p) - (size_type) p));
  85. }
  86. /* SBRK takes an int; sorry ... */
  87. if ((int) req < 0) {
  88. p = ILL_BREAK;
  89. }
  90. else {
  91. p = SBRK((int)req);
  92. }
  93. if (p == ILL_BREAK) {
  94. req = n + mallink_size();
  95. if ((int) req >= 0) p = SBRK((int)req);
  96. }
  97. if (p == ILL_BREAK) {
  98. /* Now this is bad. The system will not give us
  99. more memory. We can only liquidate our store
  100. and hope it helps.
  101. */
  102. #ifdef STORE
  103. sell_out();
  104. ml = first_present(min_class);
  105. if (ml == MAL_NULL) {
  106. #endif /* STORE */
  107. /* In this emergency we try to locate a suitable
  108. chunk in the free_list just below the safe
  109. one; some of these chunks may fit the job.
  110. */
  111. ml = search_free_list(min_class - 1, n);
  112. if (!ml) /* really out of space */
  113. return (char *) 0;
  114. started_working_on(ml);
  115. unlink_free_chunk(ml);
  116. check_mallinks("suitable_chunk, forced");
  117. #ifdef STORE
  118. }
  119. else started_working_on(ml);
  120. #endif /* STORE */
  121. }
  122. else {
  123. assert((size_type)p == align((size_type)p));
  124. ml = create_chunk(p, req);
  125. }
  126. check_mallinks("suitable_chunk, extended");
  127. }
  128. else started_working_on(ml);
  129. /* we have a chunk */
  130. set_free(ml, 0);
  131. calc_checksum(ml);
  132. check_mallinks("suitable_chunk, removed");
  133. n += mallink_size();
  134. if (n + MIN_SIZE <= size_of(ml)) {
  135. truncate(ml, n);
  136. }
  137. stopped_working_on(ml);
  138. check_mallinks("malloc exit");
  139. check_work_empty("malloc exit");
  140. #ifdef STORE
  141. assert(! in_store(ml));
  142. #endif
  143. return block_of_mallink(ml);
  144. }}
  145. free(addr)
  146. char *addr;
  147. {check_mallinks("free entry");{
  148. register mallink *ml;
  149. if (addr == 0) {
  150. check_mallinks("free(0) very fast exit");
  151. return;
  152. }
  153. ml = mallink_of_block(addr);
  154. #ifdef STORE
  155. if (free_of(ml) || in_store(ml))
  156. return; /* user frees free block */
  157. if (size_of(ml) <= MAX_SZ_IN_STORE) {
  158. /* return to store */
  159. mallink **stp = &store[(size_of(ml) >> LOG_ALIGNMENT) - 1];
  160. set_log_next(ml, *stp);
  161. *stp = ml;
  162. set_store(ml, 1);
  163. calc_checksum(ml);
  164. check_mallinks("free fast exit");
  165. }
  166. else {
  167. do_free(ml);
  168. check_mallinks("free exit");
  169. }
  170. }}
  171. private
  172. do_free(ml)
  173. register mallink *ml;
  174. {{
  175. #endif
  176. #ifndef STORE
  177. if (free_of(ml)) return;
  178. #endif /* STORE */
  179. started_working_on(ml);
  180. set_free(ml, 1);
  181. calc_checksum(ml);
  182. if (! last_mallink(ml)) {
  183. register mallink *next = phys_next_of(ml);
  184. if (free_of(next)) coalesce_forw(ml, next);
  185. }
  186. if (! first_mallink(ml)) {
  187. register mallink *prev = phys_prev_of(ml);
  188. if (free_of(prev)) {
  189. coalesce_backw(ml, prev);
  190. ml = prev;
  191. }
  192. }
  193. link_free_chunk(ml);
  194. stopped_working_on(ml);
  195. check_work_empty("free");
  196. /* Compile-time checks on param.h */
  197. switch (0) {
  198. case MIN_SIZE < OFF_SET * sizeof(mallink): break;
  199. case 1: break;
  200. /* If this statement does not compile due to duplicate case
  201. entry, the minimum size block cannot hold the links for
  202. the free blocks. Either raise LOG_MIN_SIZE or switch
  203. off NON_STANDARD.
  204. */
  205. }
  206. switch(0) {
  207. case sizeof(char *) != sizeof(size_type): break;
  208. case 1: break;
  209. /* If this statement does not compile due to duplicate
  210. case entry, size_type is not defined correctly.
  211. Redefine and compile again.
  212. */
  213. }
  214. }}
  215. char *
  216. realloc(addr, n)
  217. char *addr;
  218. register unsigned int n;
  219. {check_mallinks("realloc entry");{
  220. register mallink *ml, *ph_next;
  221. register size_type size;
  222. if (addr == 0) {
  223. /* Behave like most Unix realloc's when handed a
  224. null-pointer
  225. */
  226. return malloc(n);
  227. }
  228. if (n == 0) {
  229. free(addr);
  230. return 0;
  231. }
  232. ml = mallink_of_block(addr);
  233. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  234. #ifdef STORE
  235. if (in_store(ml)) {
  236. register mallink *stp = store[(size_of(ml) >> LOG_ALIGNMENT) - 1];
  237. mallink *stp1 = 0;
  238. while (ml != stp) {
  239. stp1 = stp;
  240. stp = log_next_of(stp);
  241. }
  242. stp = log_next_of(stp);
  243. if (! stp1) store[(size_of(ml) >> LOG_MIN_SIZE) - 1] = stp;
  244. else set_log_next(stp1, stp);
  245. set_store(ml, 0);
  246. calc_checksum(ml);
  247. }
  248. #endif
  249. if (free_of(ml)) {
  250. unlink_free_chunk(ml);
  251. set_free(ml, 0); /* user reallocs free block */
  252. }
  253. started_working_on(ml);
  254. size = size_of(ml);
  255. if ( /* we can simplify the problem by adding the next chunk: */
  256. n > size &&
  257. !last_mallink(ml) &&
  258. (ph_next = phys_next_of(ml), free_of(ph_next)) &&
  259. n <= size + mallink_size() + size_of(ph_next)
  260. ) {
  261. /* add in the physically next chunk */
  262. unlink_free_chunk(ph_next);
  263. combine_chunks(ml, ph_next);
  264. size = size_of(ml);
  265. check_mallinks("realloc, combining");
  266. }
  267. if (n > size) { /* this didn't help */
  268. char *new;
  269. register char *l1, *l2 = addr;
  270. stopped_working_on(ml);
  271. if (!(new = l1 = malloc(n))) return (char *) 0; /* no way */
  272. while (size--) *l1++ = *l2++;
  273. free(addr);
  274. check_work_empty("mv_realloc");
  275. #ifdef STORE
  276. assert(! in_store(mallink_of_block(new)));
  277. #endif
  278. return new;
  279. }
  280. /* it helped, but maybe too well */
  281. n += mallink_size();
  282. if (n + MIN_SIZE <= size_of(ml)) {
  283. truncate(ml, n);
  284. }
  285. stopped_working_on(ml);
  286. check_mallinks("realloc exit");
  287. check_work_empty("realloc");
  288. #ifdef STORE
  289. assert(! in_store(ml));
  290. #endif
  291. return addr;
  292. }}
  293. /* Auxiliary routines */
  294. #ifdef STORE
  295. private
  296. sell_out() {
  297. /* Frees all block in store.
  298. */
  299. register mallink **stp;
  300. for (stp = &store[0]; stp < &store[MAX_STORE]; stp++) {
  301. register mallink *ml = *stp;
  302. while (ml) {
  303. *stp = log_next_of(ml);
  304. set_store(ml, 0);
  305. do_free(ml);
  306. ml = *stp;
  307. }
  308. }
  309. }
  310. #endif /* STORE */
  311. #ifdef ASSERT
  312. public
  313. m_assert(fn, ln)
  314. char *fn;
  315. {
  316. char ch;
  317. while (*fn)
  318. write(2, fn++, 1);
  319. write(2, ": malloc assert failed in line ", 31);
  320. ch = (ln / 100) + '0'; write(2, &ch, 1); ln %= 100;
  321. ch = (ln / 10) + '0'; write(2, &ch, 1); ln %= 10;
  322. ch = (ln / 1) + '0'; write(2, &ch, 1);
  323. write(2, "\n", 1);
  324. maldump(1);
  325. }
  326. #endif /* ASSERT */