mal.c 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385
  1. /* $Id$ */
  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 <limits.h>
  7. #include <stdlib.h>
  8. #include "param.h"
  9. #include "impl.h"
  10. #include "check.h"
  11. #include "log.h"
  12. #include "phys.h"
  13. /* Malloc space is traversed by N doubly-linked lists of chunks, each
  14. containing a couple of house-keeping data addressed as a
  15. 'mallink' and a piece of useful space, called the block.
  16. The N lists are accessed through their starting pointers in
  17. free_list[]. Free_list[n] points to a list of chunks between
  18. 2**(n+LOG_MIN_SIZE) and 2**(n+LOG_MIN_SIZE+1)-1, which means
  19. that the smallest chunk is 2**LOG_MIN_SIZE (== MIN_SIZE).
  20. */
  21. #ifdef SYSTEM
  22. #include <system.h>
  23. #define SBRK sys_break
  24. extern void *SBRK(int incr);
  25. #else
  26. #include <unistd.h>
  27. #define SBRK sbrk
  28. #define ILL_BREAK (void *)(-1) /* funny failure value */
  29. #endif
  30. #ifdef STORE
  31. #define MAX_STORE 32
  32. private do_free(mallink *ml), sell_out(void);
  33. privatedata mallink *store[MAX_STORE];
  34. #endif /* STORE */
  35. void *
  36. malloc(register size_t n)
  37. {check_mallinks("malloc entry");{
  38. register mallink *ml;
  39. register int min_class;
  40. if (n == 0) {
  41. return NULL;
  42. }
  43. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  44. #ifdef STORE
  45. if (n <= MAX_STORE*MIN_SIZE) {
  46. /* look in the store first */
  47. register mallink **stp = &store[(n >> LOG_MIN_SIZE) - 1];
  48. if (ml = *stp) {
  49. *stp = log_next_of(ml);
  50. set_store(ml, 0);
  51. check_mallinks("malloc fast exit");
  52. assert(! in_store(ml));
  53. return block_of_mallink(ml);
  54. }
  55. }
  56. #endif /* STORE */
  57. check_work_empty("malloc, entry");
  58. /* Acquire a chunk of at least size n if at all possible;
  59. Try everything.
  60. */
  61. {
  62. /* Inline substitution of "smallest".
  63. */
  64. register size_t n1 = n;
  65. assert(n1 < (1L << LOG_MAX_SIZE));
  66. min_class = 0;
  67. do {
  68. n1 >>= 1;
  69. min_class++;
  70. } while (n1 >= MIN_SIZE);
  71. }
  72. if (min_class >= MAX_FLIST)
  73. return NULL; /* we don't deal in blocks that big */
  74. ml = first_present(min_class);
  75. if (ml == MAL_NULL) {
  76. /* Try and extend */
  77. register void *p;
  78. #define GRABSIZE 4096 /* Power of 2 */
  79. register size_t req =
  80. ((MIN_SIZE<<min_class)+ mallink_size() + GRABSIZE - 1) &
  81. ~(GRABSIZE-1);
  82. if (!ml_last) {
  83. /* first align SBRK() */
  84. p = SBRK(0);
  85. SBRK((int) (align((size_type) p) - (size_type) p));
  86. }
  87. /* SBRK takes an int; sorry ... */
  88. if ((int) req < 0) {
  89. p = ILL_BREAK;
  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 NULL;
  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. void
  146. free(void *addr)
  147. {check_mallinks("free entry");{
  148. register mallink *ml;
  149. if (addr == NULL) {
  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_STORE*MIN_SIZE) {
  158. /* return to store */
  159. mallink **stp = &store[(size_of(ml) >> LOG_MIN_SIZE) - 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(register mallink *ml)
  173. {{
  174. #endif
  175. #ifndef STORE
  176. if (free_of(ml)) return;
  177. #endif /* STORE */
  178. started_working_on(ml);
  179. set_free(ml, 1);
  180. calc_checksum(ml);
  181. if (! last_mallink(ml)) {
  182. register mallink *next = phys_next_of(ml);
  183. if (free_of(next)) coalesce_forw(ml, next);
  184. }
  185. if (! first_mallink(ml)) {
  186. register mallink *prev = phys_prev_of(ml);
  187. if (free_of(prev)) {
  188. coalesce_backw(ml, prev);
  189. ml = prev;
  190. }
  191. }
  192. link_free_chunk(ml);
  193. stopped_working_on(ml);
  194. check_work_empty("free");
  195. /* Compile-time checks on param.h */
  196. switch (0) {
  197. case MIN_SIZE < OFF_SET * sizeof(mallink): break;
  198. case 1: break;
  199. /* If this statement does not compile due to duplicate case
  200. entry, the minimum size block cannot hold the links for
  201. the free blocks. Either raise LOG_MIN_SIZE or switch
  202. off NON_STANDARD.
  203. */
  204. }
  205. switch(0) {
  206. case sizeof(void *) != sizeof(size_type): break;
  207. case 1: break;
  208. /* If this statement does not compile due to duplicate
  209. case entry, size_type is not defined correctly.
  210. Redefine and compile again.
  211. */
  212. }
  213. }}
  214. void *
  215. realloc(void *addr, register size_t n)
  216. {check_mallinks("realloc entry");{
  217. register mallink *ml, *ph_next;
  218. register size_type size;
  219. if (addr == NULL) {
  220. /* Behave like most Unix realloc's when handed a
  221. null-pointer
  222. */
  223. return malloc(n);
  224. }
  225. if (n == 0) {
  226. free(addr);
  227. return NULL;
  228. }
  229. ml = mallink_of_block(addr);
  230. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  231. #ifdef STORE
  232. if (in_store(ml)) {
  233. register mallink *stp = store[(size_of(ml) >> LOG_MIN_SIZE) - 1];
  234. mallink *stp1 = NULL;
  235. while (ml != stp) {
  236. stp1 = stp;
  237. stp = log_next_of(stp);
  238. }
  239. stp = log_next_of(stp);
  240. if (! stp1) store[(size_of(ml) >> LOG_MIN_SIZE) - 1] = stp;
  241. else set_log_next(stp1, stp);
  242. set_store(ml, 0);
  243. calc_checksum(ml);
  244. }
  245. #endif
  246. if (free_of(ml)) {
  247. unlink_free_chunk(ml);
  248. set_free(ml, 0); /* user reallocs free block */
  249. }
  250. started_working_on(ml);
  251. size = size_of(ml);
  252. if ( /* we can simplify the problem by adding the next chunk: */
  253. n > size &&
  254. !last_mallink(ml) &&
  255. (ph_next = phys_next_of(ml), free_of(ph_next)) &&
  256. n <= size + mallink_size() + size_of(ph_next)
  257. ) {
  258. /* add in the physically next chunk */
  259. unlink_free_chunk(ph_next);
  260. combine_chunks(ml, ph_next);
  261. size = size_of(ml);
  262. check_mallinks("realloc, combining");
  263. }
  264. if (n > size) { /* this didn't help */
  265. void *new;
  266. register char *l1, *l2 = addr;
  267. stopped_working_on(ml);
  268. if (!(new = l1 = malloc(n))) return NULL; /* no way */
  269. while (size--) *l1++ = *l2++;
  270. free(addr);
  271. check_work_empty("mv_realloc");
  272. #ifdef STORE
  273. assert(! in_store(mallink_of_block(new)));
  274. #endif
  275. return new;
  276. }
  277. /* it helped, but maybe too well */
  278. n += mallink_size();
  279. if (n + MIN_SIZE <= size_of(ml)) {
  280. truncate(ml, n);
  281. }
  282. stopped_working_on(ml);
  283. check_mallinks("realloc exit");
  284. check_work_empty("realloc");
  285. #ifdef STORE
  286. assert(! in_store(ml));
  287. #endif
  288. return addr;
  289. }}
  290. void *
  291. calloc(size_t nmemb, size_t size)
  292. {check_mallinks("calloc entry");{
  293. long *l1, *l2;
  294. size_t n;
  295. if (size == 0) return NULL;
  296. if (nmemb == 0) return NULL;
  297. /* Check for overflow on the multiplication. The peephole-optimizer
  298. * will eliminate all but one of the possibilities.
  299. */
  300. if (sizeof(size_t) == sizeof(int)) {
  301. if (UINT_MAX / size < nmemb) return NULL;
  302. } else if (sizeof(size_t) == sizeof(long)) {
  303. if (ULONG_MAX / size < nmemb) return NULL;
  304. } else return NULL; /* can't happen, can it ? */
  305. n = size * nmemb;
  306. if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  307. if (n >= (1L << LOG_MAX_SIZE)) return NULL;
  308. l1 = (long *) malloc(n);
  309. l2 = l1 + (n / sizeof(long)); /* n is at least long aligned */
  310. while ( l2 != l1 ) *--l2 = 0;
  311. check_mallinks("calloc exit");
  312. check_work_empty("calloc exit");
  313. return (void *)l1;
  314. }}
  315. /* Auxiliary routines */
  316. #ifdef STORE
  317. private
  318. sell_out(void) {
  319. /* Frees all block in store.
  320. */
  321. register mallink **stp;
  322. for (stp = &store[0]; stp < &store[MAX_STORE]; stp++) {
  323. register mallink *ml = *stp;
  324. while (ml) {
  325. *stp = log_next_of(ml);
  326. set_store(ml, 0);
  327. do_free(ml);
  328. ml = *stp;
  329. }
  330. }
  331. }
  332. #endif /* STORE */
  333. #ifdef ASSERT
  334. public
  335. m_assert(const char *fn, int ln)
  336. {
  337. char ch;
  338. while (*fn)
  339. write(2, fn++, 1);
  340. write(2, ": malloc assert failed in line ", 31);
  341. ch = (ln / 100) + '0'; write(2, &ch, 1); ln %= 100;
  342. ch = (ln / 10) + '0'; write(2, &ch, 1); ln %= 10;
  343. ch = (ln / 1) + '0'; write(2, &ch, 1);
  344. write(2, "\n", 1);
  345. maldump(1);
  346. }
  347. #endif /* ASSERT */