malloc.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880
  1. /*
  2. malloc - heap manager based on heavy use of virtual memory management.
  3. Copyright (C) 1998 Valery Shchedrin
  4. This library is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU Library General Public
  6. License as published by the Free Software Foundation; either
  7. version 2 of the License, or (at your option) any later version.
  8. This library is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. Library General Public License for more details.
  12. You should have received a copy of the GNU Library General Public
  13. License along with this library; if not, write to the Free
  14. Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  15. MA 02111-1307, USA
  16. Public Functions:
  17. void *malloc(size_t size);
  18. Allocates `size` bytes
  19. returns NULL if no free memory available
  20. void *calloc(size_t unit, size_t quantity);
  21. Allocates `quantity*unit` zeroed bytes via internal malloc call
  22. void *realloc(void *ptr, size_t size);
  23. Reallocates already allocated block `ptr`, if `ptr` is not valid block
  24. then it works as malloc. NULL is returned if no free memory available
  25. void *_realloc_no_move(void *ptr, size_t size);
  26. Reallocates already allocated block `ptr`, if `ptr` is not valid block
  27. or if reallocation can't be done with shrinking/expanding already
  28. allocated block NULL is returned
  29. void free(void *ptr);
  30. Frees already allocated block, if `ptr` is incorrect one nothing will
  31. happen.
  32. */
  33. /*
  34. * Manuel Novoa III Jan 2001
  35. *
  36. * Modified to decrease object sizes.
  37. * Broke into independent object files.
  38. * Converted INIT_BLOCK() and FREE_MEM_DEL_BLOCK() from macros to functions.
  39. */
  40. #include <features.h>
  41. #ifndef _XOPEN_SOURCE
  42. #define _XOPEN_SOURCE
  43. #endif
  44. #include <sys/types.h>
  45. #include <unistd.h>
  46. #include <limits.h>
  47. #include <sys/time.h>
  48. #include <asm/page.h>
  49. #include <unistd.h>
  50. #include <sys/mman.h>
  51. #include <string.h>
  52. #include "malloc.h"
  53. #include <stdio.h>
  54. #define M_DOTRIMMING 1
  55. #define M_MULTITHREADED 0
  56. #define VALLOC_MSTART ((void*)0x1c000000)
  57. #define LARGE_MSTART ((void*)0x19000000)
  58. #define HUNK_MSTART ((void*)0x18000000)
  59. #define HUNK_MSIZE M_PAGESIZE
  60. #define HUNK_ID 0x99171713
  61. /* alignment of allocations > HUNK_THRESHOLD */
  62. #define MALLOC_ALIGN 4
  63. /* allocations < HUNK_THRESHOLD will not be aligned */
  64. #define HUNK_THRESHOLD 4
  65. /*up to HUNK_MAXSIZE blocks will be joined together to decrease memory waste*/
  66. #define HUNK_MAXSIZE 128
  67. /* returns value not less than size, aligned to MALLOC_ALIGN */
  68. #define ALIGN(size) (((size)+(MALLOC_ALIGN)-1)&(~((MALLOC_ALIGN)-1)))
  69. /* aligns s or p to page boundaries */
  70. #define PAGE_ALIGN(s) (((s)+M_PAGESIZE-1)&(~(M_PAGESIZE-1)))
  71. #define PAGE_ALIGNP(p) ((char*)PAGE_ALIGN((unsigned)(p)))
  72. #define PAGE_DOWNALIGNP(p) ((char*)(((unsigned)(p))&(~(M_PAGESIZE-1))))
  73. /* returns v * 2 for your machine (speed-up) */
  74. #define MUL2(v) ((v)*2)
  75. /* does v *= 8 for your machine (speed-up) */
  76. #define EMUL8(v) v*=8
  77. /* does v/8 for your machind (speed-up) */
  78. #define DIV8(v) ((v)/8)
  79. #if M_MULTITHREADED
  80. #error This version does not support threads
  81. #else
  82. typedef int mutex_t;
  83. #define mutex_lock(x)
  84. #define mutex_unlock(x)
  85. #define mutex_init(x)
  86. #define MUTEX_INITIALIZER 0
  87. //static mutex_t malloc_lock = MUTEX_INITIALIZER;
  88. #endif
  89. extern int __malloc_initialized;
  90. #ifdef L__malloc_init
  91. int __malloc_initialized = -1;
  92. /* -1 == uninitialized, 0 == initializing, 1 == initialized */
  93. #endif
  94. #ifndef MAP_FAILED
  95. #define MAP_FAILED ((void*)-1)
  96. #endif
  97. #if defined(MAP_ANONYMOUS) && !defined(MAP_ANON)
  98. #define MAP_ANON MAP_ANONYMOUS
  99. #endif
  100. #ifndef NULL
  101. #define NULL ((void*)0)
  102. #endif
  103. /* guess pagesize */
  104. #define M_PAGESIZE getpagesize()
  105. /* HUNK MANAGER */
  106. typedef struct Hunk_s Hunk_t;
  107. struct Hunk_s { /* Hunked block - 8 byte overhead */
  108. int id; /* unique id */
  109. unsigned int total:12, used:12, size:8;
  110. Hunk_t *next; /* next free in __free_h */
  111. };
  112. #define usagemap(h) (((unsigned char *)(h))+sizeof(Hunk_t))
  113. #define hunk_ptr(h) (((char*)(h))+sizeof(Hunk_t)+ALIGN(DIV8(h->total+7)))
  114. #define hunk(h) ((Hunk_t*)(h))
  115. extern Hunk_t *__free_h[HUNK_MAXSIZE + 1];
  116. extern int __total_h[HUNK_MAXSIZE + 1];
  117. #ifdef L__malloc_init
  118. Hunk_t *__free_h[HUNK_MAXSIZE + 1]; /* free hash */
  119. int __total_h[HUNK_MAXSIZE + 1]; /* Hunk_t's `total` member */
  120. #endif
  121. extern void *__hunk_alloc(int size);
  122. #ifdef L_malloc
  123. /* __hunk_alloc allocates <= HUNK_MAXSIZE blocks */
  124. void *__hunk_alloc(int size)
  125. {
  126. Hunk_t *p;
  127. unsigned long *cpl;
  128. int i, c;
  129. // if (size >= HUNK_THRESHOLD)
  130. size = ALIGN(size);
  131. /* Look for already allocated hunkblocks */
  132. if ((p = __free_h[size]) == NULL) {
  133. if (
  134. (p =
  135. (Hunk_t *) mmap(HUNK_MSTART, HUNK_MSIZE,
  136. PROT_READ | PROT_WRITE,
  137. #ifdef __UCLIBC_HAS_MMU__
  138. MAP_PRIVATE | MAP_ANONYMOUS
  139. #else
  140. MAP_SHARED | MAP_ANONYMOUS
  141. #endif
  142. , 0, 0)) == (Hunk_t *) MAP_FAILED)
  143. // {
  144. // printf("hunk_alloc failed: %d, %d\n", size, errno);
  145. return NULL;
  146. // }
  147. memset(p, 0, HUNK_MSIZE);
  148. p->id = HUNK_ID;
  149. p->total = __total_h[size];
  150. /* p->used = 0; */
  151. p->size = size;
  152. /* p->next = (Hunk_t*)NULL; */
  153. /* memset(usagemap(p), 0, bound); */
  154. __free_h[size] = p;
  155. }
  156. /* Locate free point in usagemap */
  157. /* First find a word where not all the bits are set */
  158. for (cpl = (unsigned long *) usagemap(p); *cpl == 0xFFFFFFFF; cpl++);
  159. /* Remember the byte position of that word */
  160. i = ((unsigned char *) cpl) - usagemap(p);
  161. /* Now find find a free bit in the word using binary search */
  162. if (*(unsigned short *) cpl != 0xFFFF) {
  163. if (*(unsigned char *) cpl == 0xFF) {
  164. c = *(((unsigned char *) cpl) + 1);
  165. i++;
  166. }
  167. else
  168. {
  169. c = *(unsigned char *) cpl;
  170. }
  171. } else {
  172. i += 2;
  173. c = *(((unsigned char *) cpl) + 2);
  174. if (c == 0xFF) {
  175. c = *(((unsigned char *) cpl) + 3);
  176. i++;
  177. }
  178. }
  179. /*
  180. * Multiply i by 8 for the bit position
  181. * Further down, we divide by 8 again to find the byte position
  182. */
  183. EMUL8(i);
  184. /* If bottom nibble is set, shift down the top nibble */
  185. if ((c & 0xF) == 0xF) {
  186. c >>= 4;
  187. i += 4;
  188. }
  189. /* If bottom 2 bits are set, shift down the top two */
  190. if ((c & 0x3) == 0x3) {
  191. c >>= 2;
  192. i += 2;
  193. }
  194. /* Check which one of the two bits is set */
  195. if (c & 1)
  196. i++;
  197. usagemap(p)[DIV8(i)] |= (1 << (i & 7)); /* set bit */
  198. /* Increment counter and update hashes */
  199. if (++p->used == p->total) {
  200. __free_h[p->size] = p->next;
  201. p->next = NULL;
  202. }
  203. // fprintf(stderr, "hunk_alloc: i=%d, p->size=%d, p=%p\n", i, p->size, p);
  204. return hunk_ptr(p) + i * p->size;
  205. }
  206. #endif /* L_malloc */
  207. extern void __hunk_free(char *ptr);
  208. #ifdef L__free_support
  209. /* __hunk_free frees blocks allocated by __hunk_alloc */
  210. void __hunk_free(char *ptr)
  211. {
  212. unsigned char *up;
  213. int i, v;
  214. Hunk_t *h;
  215. if (!ptr)
  216. return;
  217. h = (Hunk_t *) PAGE_DOWNALIGNP(ptr);
  218. /* Validate `ptr` */
  219. if (h->id != HUNK_ID)
  220. return;
  221. v = ptr - hunk_ptr(h);
  222. i = v / h->size;
  223. if (v % h->size != 0 || i < 0 || i >= h->total)
  224. return;
  225. /* Update `usagemap` */
  226. up = &(usagemap(h)[DIV8(i)]);
  227. i = 1 << (i & 7);
  228. if (!(*up & i))
  229. return;
  230. *up ^= i;
  231. /* Update hunk counters */
  232. if (h->used == h->total) {
  233. if (--h->used) { /* insert into __free_h */
  234. h->next = __free_h[h->size];
  235. __free_h[h->size] = h;
  236. } /* else - it will be unmapped */
  237. } else {
  238. if (!--h->used) { /* delete from __free_h - will be __bl_freed */
  239. Hunk_t *p, *pp;
  240. for (p = __free_h[h->size], pp = NULL; p != h;
  241. pp = p, p = p->next);
  242. if (!pp)
  243. __free_h[h->size] = p->next;
  244. else
  245. pp->next = p->next;
  246. }
  247. }
  248. /* Unmap empty Hunk_t */
  249. if (!h->used)
  250. munmap((void *) h, HUNK_MSIZE);
  251. }
  252. #endif /* L__free_support */
  253. /* BLOCK MANAGER */
  254. typedef struct Block_s Block_t;
  255. struct Block_s { /* 32-bytes long control structure (if 4-byte aligned) */
  256. char *ptr; /* pointer to related data */
  257. Block_t *next; /* next in free_mem list */
  258. Block_t *l_free_mem, *r_free_mem; /* left & right subtrees of <free_mem> */
  259. Block_t *l_ptrs, *r_ptrs; /* left & right subtrees of <ptrs> */
  260. size_t size; /* size - divided by align */
  261. /* packed 4-byte attributes */
  262. /* { */
  263. signed char bal_free_mem:8; /* balance of <free_mem> subtree */
  264. signed char bal_ptrs:8; /* balance of <ptrs> subtree */
  265. unsigned int used:1; /* used/free state of the block */
  266. unsigned int broken:1; /* 1 if previous block can't be merged with it */
  267. /* } */
  268. };
  269. extern Block_t *__bl_last; /* last mmapped block */
  270. #ifdef L__malloc_init
  271. Block_t *__bl_last; /* last mmapped block */
  272. #endif
  273. #define bl_get() __hunk_alloc(sizeof(Block_t))
  274. #define bl_rel(p) __hunk_free((char*)p)
  275. extern Block_t *__Avl_Block_tfree_mem_tree;
  276. extern Block_t *__free_mem_ins(Block_t * data);
  277. extern void __free_mem_del(Block_t * data);
  278. extern void __free_mem_replace(Block_t * data);
  279. extern Block_t *__Avl_Block_tptrs_tree;
  280. extern Block_t *__ptrs_ins(Block_t * data);
  281. extern void __ptrs_del(Block_t * data);
  282. extern void __bl_uncommit(Block_t * b);
  283. extern void __bl_free(Block_t * b);
  284. /* like C++ templates ;-) */
  285. #include "avlmacro.h"
  286. #define FREE_MEM_COMPARE(i,a,b) \
  287. { \
  288. if ( (a)->size < (b)->size ) { \
  289. i = -1; \
  290. } else if ( (a)->size > (b)->size ) { \
  291. i = 1; \
  292. } else { \
  293. i = 0; \
  294. } \
  295. }
  296. #define PTRS_COMPARE(i,a,b) \
  297. { \
  298. if ( (a)->ptr < (b)->ptr ) { \
  299. i = -1; \
  300. } else if ( (a)->ptr > (b)->ptr ) { \
  301. i = 1; \
  302. } else { \
  303. i = 0; \
  304. } \
  305. }
  306. #ifdef L__avl_support
  307. Avl_Tree(free_mem, Block_t, free_mem, FREE_MEM_COMPARE)
  308. Avl_Tree_no_replace(ptrs, Block_t, ptrs, PTRS_COMPARE)
  309. #endif
  310. #define free_mem_root Avl_Root(Block_t, free_mem)
  311. #define ptrs_root Avl_Root(Block_t, ptrs)
  312. /* pp is freed block */
  313. #define FREE_MEM_DEL_BLOCK(pp,p) {p = __free_mem_del_block(pp,p);}
  314. extern Block_t *__free_mem_del_block(Block_t * pp, Block_t * p);
  315. #ifdef L_malloc
  316. Block_t *__free_mem_del_block(Block_t * pp, Block_t * p)
  317. {
  318. for (p = free_mem_root;;)
  319. if (p->size > pp->size)
  320. p = p->l_free_mem;
  321. else if (p->size < pp->size)
  322. p = p->r_free_mem;
  323. else
  324. break;
  325. if (p == pp) {
  326. if (pp->next)
  327. __free_mem_replace(pp->next);
  328. else
  329. __free_mem_del(pp);
  330. } else {
  331. for (; p->next != pp; p = p->next);
  332. p->next = pp->next;
  333. }
  334. return p;
  335. }
  336. #endif /* L_malloc */
  337. #define FREE_MEM_INS_BLOCK(pp) \
  338. { \
  339. if ((p = __free_mem_ins(pp)) != NULL)\
  340. {\
  341. pp->next = p->next;\
  342. p->next = pp;\
  343. }\
  344. else pp->next = NULL; \
  345. }
  346. /* `b` is current block, `pp` is next block */
  347. #define COMBINE_BLOCKS(b,pp) \
  348. {\
  349. __ptrs_del(pp); \
  350. b->size += pp->size; \
  351. if (pp == __bl_last) __bl_last = b; \
  352. bl_rel(pp); \
  353. }
  354. /* initializes new block b */
  355. #define INIT_BLOCK(b, pppp, sz) { p = __init_block(b, pppp, sz); }
  356. extern Block_t *__init_block(Block_t * b, char *pppp, size_t sz);
  357. #ifdef L_malloc
  358. Block_t *__init_block(Block_t * b, char *pppp, size_t sz)
  359. {
  360. Block_t *p;
  361. memset(b, 0, sizeof(Block_t));
  362. b->ptr = pppp;
  363. b->size = sz;
  364. __ptrs_ins(b);
  365. FREE_MEM_INS_BLOCK(b);
  366. return p;
  367. }
  368. #endif /* L_malloc */
  369. /* `b` is current block, `sz` its new size */
  370. /* block `b` will be splitted to one busy & one free block */
  371. #define SPLIT_BLOCK(b,sz) \
  372. {\
  373. Block_t *bt; \
  374. bt = bl_get(); \
  375. INIT_BLOCK(bt, b->ptr + sz, b->size - sz); \
  376. b->size = sz; \
  377. if (__bl_last == b) __bl_last = bt; \
  378. __bl_uncommit(bt);\
  379. }
  380. /* `b` is current block, `pp` is next free block, `sz` is needed size */
  381. #define SHRINK_BLOCK(b,pp,sz) \
  382. {\
  383. FREE_MEM_DEL_BLOCK(pp,p); \
  384. pp->ptr = b->ptr + sz; \
  385. pp->size += b->size - sz; \
  386. b->size = sz; \
  387. FREE_MEM_INS_BLOCK(pp); \
  388. __bl_uncommit(pp); \
  389. }
  390. #ifdef L_malloc
  391. static Block_t *bl_mapnew(size_t size)
  392. {
  393. size_t map_size;
  394. Block_t *pp, *p;
  395. void *pt;
  396. map_size = PAGE_ALIGN(size);
  397. pt = mmap(LARGE_MSTART, map_size, PROT_READ | PROT_WRITE | PROT_EXEC,
  398. #ifdef __UCLIBC_HAS_MMU__
  399. MAP_PRIVATE | MAP_ANONYMOUS
  400. #else
  401. MAP_SHARED | MAP_ANONYMOUS
  402. #endif
  403. , 0, 0);
  404. if (pt == MAP_FAILED)
  405. return (Block_t *) NULL;
  406. __bl_last = pp = bl_get();
  407. INIT_BLOCK(pp, (char *) pt, map_size);
  408. pp->broken = 1;
  409. return pp;
  410. }
  411. void __bl_uncommit(Block_t * b)
  412. {
  413. char *u_start, *u_end;
  414. u_start = PAGE_ALIGNP(b->ptr);
  415. u_end = PAGE_DOWNALIGNP(b->ptr + b->size);
  416. if (u_end <= u_start)
  417. return;
  418. #if M_DOTRIMMING
  419. mmap(u_start, u_end - u_start, PROT_READ | PROT_WRITE | PROT_EXEC,
  420. #ifdef __UCLIBC_HAS_MMU__
  421. MAP_PRIVATE | MAP_ANONYMOUS |MAP_FIXED
  422. #else
  423. MAP_SHARED | MAP_ANONYMOUS |MAP_FIXED
  424. #endif
  425. , 0, 0);
  426. #endif
  427. }
  428. /* requested size must be aligned to ALIGNMENT */
  429. static Block_t *bl_alloc(size_t size)
  430. {
  431. Block_t *p, *pp;
  432. /* try to find needed space in existing memory */
  433. for (p = free_mem_root, pp = NULL; p;) {
  434. if (p->size > size) {
  435. pp = p;
  436. p = p->l_free_mem;
  437. } else if (p->size < size)
  438. p = p->r_free_mem;
  439. else {
  440. pp = p;
  441. break;
  442. }
  443. }
  444. if (!pp) { /* map some memory */
  445. if (!__bl_last) { /* just do initial mmap */
  446. pp = bl_mapnew(size);
  447. if (!pp)
  448. return NULL;
  449. } else if (!__bl_last->used) { /* try growing last unused */
  450. if (mremap(PAGE_DOWNALIGNP(__bl_last->ptr),
  451. PAGE_ALIGNP(__bl_last->ptr + __bl_last->size) -
  452. PAGE_DOWNALIGNP(__bl_last->ptr),
  453. PAGE_ALIGNP(__bl_last->ptr + size) -
  454. PAGE_DOWNALIGNP(__bl_last->ptr), 0) == MAP_FAILED) { /* unable to grow -- initiate new block */
  455. pp = bl_mapnew(size);
  456. if (!pp)
  457. return NULL;
  458. } else {
  459. pp = __bl_last;
  460. FREE_MEM_DEL_BLOCK(pp, p);
  461. pp->size = PAGE_ALIGNP(pp->ptr + size) - pp->ptr;
  462. FREE_MEM_INS_BLOCK(pp);
  463. }
  464. } else { /* __bl_last is used block */
  465. if (mremap(PAGE_DOWNALIGNP(__bl_last->ptr),
  466. PAGE_ALIGNP(__bl_last->ptr + __bl_last->size) -
  467. PAGE_DOWNALIGNP(__bl_last->ptr),
  468. PAGE_ALIGNP(__bl_last->ptr + __bl_last->size +
  469. size) - PAGE_DOWNALIGNP(__bl_last->ptr),
  470. 0) == MAP_FAILED) {
  471. pp = bl_mapnew(size);
  472. if (!pp)
  473. return NULL;
  474. } else {
  475. pp = bl_get();
  476. INIT_BLOCK(pp, __bl_last->ptr + __bl_last->size,
  477. PAGE_ALIGNP(__bl_last->ptr + __bl_last->size +
  478. size) - __bl_last->ptr -
  479. __bl_last->size);
  480. __bl_last = pp;
  481. }
  482. }
  483. }
  484. /* just delete this node from free_mem tree */
  485. if (pp->next)
  486. __free_mem_replace(pp->next);
  487. else
  488. __free_mem_del(pp);
  489. pp->used = 1;
  490. if (pp->size - size > MALLOC_ALIGN) { /* this block can be splitted (it is unused,not_broken) */
  491. SPLIT_BLOCK(pp, size);
  492. }
  493. return pp;
  494. }
  495. #endif /* L_malloc */
  496. #ifdef L__free_support
  497. void __bl_free(Block_t * b)
  498. {
  499. Block_t *p, *bl_next, *bl_prev;
  500. /* Look for blocks before & after `b` */
  501. for (p = ptrs_root, bl_next = NULL, bl_prev = NULL; p;) {
  502. if (p->ptr > b->ptr) {
  503. bl_next = p;
  504. p = p->l_ptrs;
  505. } else if (p->ptr < b->ptr) {
  506. bl_prev = p;
  507. p = p->r_ptrs;
  508. } else
  509. break;
  510. }
  511. if (b->l_ptrs)
  512. for (bl_prev = b->l_ptrs; bl_prev->r_ptrs;
  513. bl_prev = bl_prev->r_ptrs);
  514. if (b->r_ptrs)
  515. for (bl_next = b->r_ptrs; bl_next->l_ptrs;
  516. bl_next = bl_next->l_ptrs);
  517. if (bl_next && !bl_next->broken && !bl_next->used) {
  518. FREE_MEM_DEL_BLOCK(bl_next, p)
  519. COMBINE_BLOCKS(b, bl_next)
  520. }
  521. if (bl_prev && !b->broken && !bl_prev->used) {
  522. FREE_MEM_DEL_BLOCK(bl_prev, p)
  523. COMBINE_BLOCKS(bl_prev, b)
  524. b = bl_prev;
  525. }
  526. b->used = 0;
  527. FREE_MEM_INS_BLOCK(b)
  528. __bl_uncommit(b);
  529. }
  530. #endif /* L__free_support */
  531. extern void __malloc_init(void);
  532. #ifdef L__malloc_init
  533. void __malloc_init(void)
  534. {
  535. int i, mapsize, x, old_x, gcount;
  536. mapsize = M_PAGESIZE;
  537. __malloc_initialized = 0;
  538. __bl_last = NULL;
  539. free_mem_root = NULL;
  540. ptrs_root = NULL;
  541. mapsize -= sizeof(Hunk_t);
  542. for (i = 1; i <= HUNK_MAXSIZE; i++) {
  543. __free_h[i] = (Hunk_t *) NULL;
  544. for (x = mapsize / i, gcount = 0, old_x = 0; old_x != x;) {
  545. old_x = x;
  546. x = (mapsize - ALIGN(DIV8(old_x + 7))) / i;
  547. if (gcount > 1 && x * i + ALIGN(DIV8(x + 7)) <= mapsize)
  548. break;
  549. if (x * i + ALIGN(DIV8(x + 7)) > mapsize)
  550. gcount++;
  551. }
  552. __total_h[i] = x;
  553. }
  554. mutex_init(&malloc_lock);
  555. __malloc_initialized = 1;
  556. // fprintf(stderr, "malloc_init: hunk_t=%d\n", sizeof(Hunk_t));
  557. }
  558. #endif /* L__malloc_init */
  559. #ifdef L_malloc
  560. void *malloc(size_t size)
  561. {
  562. void *p;
  563. if (size == 0)
  564. return NULL;
  565. if (__malloc_initialized < 0)
  566. __malloc_init();
  567. if (__malloc_initialized)
  568. mutex_lock(&malloc_lock);
  569. if (size <= HUNK_MAXSIZE)
  570. p = __hunk_alloc(size);
  571. else {
  572. if ((p = bl_alloc(ALIGN(size))) != NULL)
  573. p = ((Block_t *) p)->ptr;
  574. }
  575. if (__malloc_initialized)
  576. mutex_unlock(&malloc_lock);
  577. // fprintf(stderr, "malloc returning: s=%d, p=%p\n", size, p);
  578. return p;
  579. }
  580. #endif /* L_malloc */
  581. #ifdef L_free
  582. void free(void *ptr)
  583. {
  584. Block_t *p, *best;
  585. if (__malloc_initialized < 0)
  586. return;
  587. if (__malloc_initialized)
  588. mutex_lock(&malloc_lock);
  589. for (p = ptrs_root, best = NULL; p;) {
  590. if (p->ptr > (char *) ptr)
  591. p = p->l_ptrs;
  592. else {
  593. best = p;
  594. p = p->r_ptrs;
  595. }
  596. }
  597. if (!best || !best->used || best->ptr != (char *) ptr) {
  598. __hunk_free(ptr);
  599. if (__malloc_initialized)
  600. mutex_unlock(&malloc_lock);
  601. return;
  602. }
  603. __bl_free(best);
  604. if (__malloc_initialized)
  605. mutex_unlock(&malloc_lock);
  606. }
  607. #endif /* L_free */
  608. extern void *_realloc_no_move(void *ptr, size_t size);
  609. #ifdef L__realloc_no_move
  610. void *_realloc_no_move(void *ptr, size_t size)
  611. {
  612. Block_t *p, *best, *next;
  613. if (size <= HUNK_MAXSIZE)
  614. return NULL;
  615. if (__malloc_initialized <= 0)
  616. return malloc(size);
  617. mutex_lock(&malloc_lock);
  618. /* Locate block */
  619. for (p = ptrs_root, best = NULL; p;) {
  620. if (p->ptr > (char *) ptr)
  621. p = p->l_ptrs;
  622. else {
  623. best = p;
  624. p = p->r_ptrs;
  625. }
  626. }
  627. if (!best || !best->used || best->ptr != (char *) ptr) {
  628. mutex_unlock(&malloc_lock);
  629. return NULL;
  630. }
  631. size = ALIGN(size);
  632. if (size == best->size) {
  633. mutex_unlock(&malloc_lock);
  634. return ptr;
  635. }
  636. if (best->r_ptrs) /* get block just after */
  637. for (next = best->r_ptrs; next->l_ptrs; next = next->l_ptrs);
  638. else
  639. for (p = ptrs_root, next = NULL; p;) {
  640. if (p->ptr > best->ptr) {
  641. next = p;
  642. p = p->l_ptrs;
  643. } else if (p->ptr < best->ptr)
  644. p = p->r_ptrs;
  645. else
  646. break;
  647. }
  648. if (size < best->size) { /* shrink block */
  649. if (!next || next->used || next->broken) {
  650. if (best->size - size > MALLOC_ALIGN) { /* do split */
  651. SPLIT_BLOCK(best, size);
  652. }
  653. } else { /* just move border of next block */
  654. SHRINK_BLOCK(best, next, size);
  655. }
  656. } else if (next && !next->broken && !next->used) { /* can expand */
  657. if (best->size + next->size > size + HUNK_MAXSIZE) { /* shrink next free block */
  658. SHRINK_BLOCK(best, next, size);
  659. } else if (best->size + next->size >= size) { /* combine blocks (eat next one) */
  660. FREE_MEM_DEL_BLOCK(next, p);
  661. COMBINE_BLOCKS(best, next);
  662. } else { /* not enough memory in next block */
  663. mutex_unlock(&malloc_lock);
  664. return NULL;
  665. }
  666. } else { /* no next block */
  667. mutex_unlock(&malloc_lock);
  668. return NULL;
  669. }
  670. mutex_unlock(&malloc_lock);
  671. return best->ptr;
  672. }
  673. #endif /* L__realloc_no_move */
  674. #ifdef L_realloc
  675. void *realloc(void *ptr, size_t size)
  676. {
  677. void *tmp;
  678. tmp = _realloc_no_move(ptr, size);
  679. if (!tmp) {
  680. Block_t *p, *best;
  681. mutex_lock(&malloc_lock);
  682. for (p = ptrs_root, best = NULL; p;) {
  683. if (p->ptr > (char *) ptr)
  684. p = p->l_ptrs;
  685. else {
  686. best = p;
  687. p = p->r_ptrs;
  688. }
  689. }
  690. if (!best || !best->used || best->ptr != (char *) ptr) {
  691. if (ptr) {
  692. Hunk_t *h;
  693. h = (Hunk_t *) PAGE_DOWNALIGNP(ptr);
  694. if (h->id == HUNK_ID) {
  695. mutex_unlock(&malloc_lock);
  696. if ((size >= HUNK_THRESHOLD && ALIGN(size) == h->size)
  697. || size == h->size)
  698. return ptr;
  699. if ((tmp = malloc(size)) == NULL)
  700. return NULL;
  701. mutex_lock(&malloc_lock);
  702. memcpy(tmp, ptr, ((size < h->size) ? size : h->size));
  703. __hunk_free(ptr);
  704. mutex_unlock(&malloc_lock);
  705. return tmp;
  706. }
  707. }
  708. mutex_unlock(&malloc_lock);
  709. return malloc(size);
  710. }
  711. mutex_unlock(&malloc_lock);
  712. /* copy whole block */
  713. if ((tmp = malloc(size)) == NULL)
  714. return NULL;
  715. memcpy(tmp, ptr, ((size < best->size) ? size : best->size));
  716. mutex_lock(&malloc_lock);
  717. __bl_free(best);
  718. mutex_unlock(&malloc_lock);
  719. }
  720. return tmp;
  721. }
  722. #endif /* L_realloc */
  723. #ifdef L_calloc
  724. void *calloc(size_t unit, size_t quantity)
  725. {
  726. void *p;
  727. unit *= quantity;
  728. if ((p = malloc(unit)) == NULL)
  729. return NULL;
  730. memset(p, 0, unit);
  731. return p;
  732. }
  733. #endif /* L_calloc */