malloc.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450
  1. /* Ring-3 heap allocator: boundary-tag blocks with first-fit free lists.
  2. *
  3. * The heap lives in the process's single SYS_MEM_* arena at USER_HEAP_BASE.
  4. * It is mapped lazily (64 KB at first use) and grows in page-granular steps
  5. * with a small slack, so a large image arena does not reserve the whole
  6. * 64 MB window. heap_reset() unmaps everything for page-scoped programs.
  7. *
  8. * There are no threads in ring 3 and the arena is private to the process, so
  9. * no locking is needed. malloc() returns 16-byte aligned memory; calloc()
  10. * zeroes, malloc() does not (grown pages are not zeroed by the kernel).
  11. *
  12. * Block layout:
  13. *
  14. * +0 size total block size, low bit = free
  15. * +4 prev_size size of the preceding physical block (0 at the base)
  16. * +8 magic ALLOC_MAGIC or FREE_MAGIC (double-free guard)
  17. * +12 reserved
  18. * +16 payload
  19. *
  20. * Free blocks keep their next/prev links in the first 8 payload bytes. The
  21. * minimum block is therefore 32 bytes.
  22. */
  23. #include <stddef.h>
  24. #include <stdlib.h>
  25. #include <string.h>
  26. #include <ucmd_heap.h>
  27. #define HEAP_INIT_BYTES (64u * 1024u)
  28. #define HEAP_MAX_BYTES (64u * 1024u * 1024u)
  29. #define HEAP_GROW_SLACK (64u * 1024u)
  30. #define HEAP_ALIGN 16u
  31. #define HDR_SIZE 16u
  32. #define MIN_BLOCK 32u
  33. #define FREE_BIT 1u
  34. #define ALLOC_MAGIC 0x4B424C4Eu /* "NBLK" */
  35. #define FREE_MAGIC 0x45455246u /* "FREE" */
  36. struct blk {
  37. unsigned int size;
  38. unsigned int prev_size;
  39. unsigned int magic;
  40. unsigned int reserved;
  41. };
  42. struct freelink {
  43. struct blk *next;
  44. struct blk *prev;
  45. };
  46. /* Implemented by libc/ucmd_mem.c (target) or the host test backend. */
  47. void *__heap_map(unsigned int bytes);
  48. int __heap_grow(unsigned int total_bytes);
  49. void __heap_unmap(void);
  50. static unsigned char *heap_base;
  51. static unsigned int heap_bytes; /* mapped bytes */
  52. static unsigned int heap_end; /* end of the top block */
  53. static struct blk *top_blk;
  54. static struct blk *free_head;
  55. static int heap_ready;
  56. static unsigned int align_up(unsigned int n)
  57. {
  58. return (n + (HEAP_ALIGN - 1u)) & ~(HEAP_ALIGN - 1u);
  59. }
  60. static unsigned int blk_size(const struct blk *b)
  61. {
  62. return b->size & ~FREE_BIT;
  63. }
  64. static int blk_is_free(const struct blk *b)
  65. {
  66. return (b->size & FREE_BIT) != 0;
  67. }
  68. static struct blk *blk_at(unsigned int off)
  69. {
  70. return (struct blk *)(void *)(heap_base + off);
  71. }
  72. static unsigned int blk_off(const struct blk *b)
  73. {
  74. return (unsigned int)((const unsigned char *)b - heap_base);
  75. }
  76. static struct blk *blk_next(struct blk *b)
  77. {
  78. unsigned int off = blk_off(b) + blk_size(b);
  79. if (off >= heap_end)
  80. return 0;
  81. return blk_at(off);
  82. }
  83. static struct freelink *blk_link(struct blk *b)
  84. {
  85. return (struct freelink *)(void *)((unsigned char *)b + HDR_SIZE);
  86. }
  87. static void free_list_insert(struct blk *b)
  88. {
  89. struct freelink *f = blk_link(b);
  90. f->prev = 0;
  91. f->next = free_head;
  92. if (free_head)
  93. blk_link(free_head)->prev = b;
  94. free_head = b;
  95. }
  96. static void free_list_remove(struct blk *b)
  97. {
  98. struct freelink *f = blk_link(b);
  99. if (f->prev)
  100. blk_link(f->prev)->next = f->next;
  101. else
  102. free_head = f->next;
  103. if (f->next)
  104. blk_link(f->next)->prev = f->prev;
  105. }
  106. /* Split an allocated block so that it is exactly `need` bytes. If the
  107. * remainder is too small to form a block, keep the whole block. */
  108. static void split_allocated(struct blk *b, unsigned int need)
  109. {
  110. unsigned int old = blk_size(b);
  111. struct blk *rest;
  112. struct blk *after;
  113. if (old - need >= MIN_BLOCK) {
  114. rest = (struct blk *)(void *)((unsigned char *)b + need);
  115. rest->size = (old - need) | FREE_BIT;
  116. rest->prev_size = need;
  117. rest->magic = FREE_MAGIC;
  118. rest->reserved = 0;
  119. b->size = need;
  120. b->magic = ALLOC_MAGIC;
  121. after = blk_next(rest);
  122. if (after)
  123. after->prev_size = blk_size(rest);
  124. if (b == top_blk)
  125. top_blk = rest;
  126. free_list_insert(rest);
  127. } else {
  128. b->size = old;
  129. b->magic = ALLOC_MAGIC;
  130. }
  131. }
  132. /* Free `b`, merging it with a free predecessor and successor when possible. */
  133. static void free_block(struct blk *b)
  134. {
  135. struct blk *prev;
  136. struct blk *next;
  137. struct blk *after;
  138. unsigned int merged;
  139. b->size |= FREE_BIT;
  140. b->magic = FREE_MAGIC;
  141. if (b->prev_size) {
  142. prev = (struct blk *)(void *)((unsigned char *)b - b->prev_size);
  143. if (blk_is_free(prev)) {
  144. free_list_remove(prev);
  145. merged = blk_size(prev) + blk_size(b);
  146. prev->size = merged | FREE_BIT;
  147. prev->magic = FREE_MAGIC;
  148. if (b == top_blk)
  149. top_blk = prev;
  150. after = blk_next(prev);
  151. if (after)
  152. after->prev_size = merged;
  153. b = prev;
  154. }
  155. }
  156. next = blk_next(b);
  157. if (next && blk_is_free(next)) {
  158. free_list_remove(next);
  159. merged = blk_size(b) + blk_size(next);
  160. b->size = merged | FREE_BIT;
  161. b->magic = FREE_MAGIC;
  162. if (next == top_blk)
  163. top_blk = b;
  164. after = blk_next(b);
  165. if (after)
  166. after->prev_size = merged;
  167. }
  168. free_list_insert(b);
  169. }
  170. /* Extend the mapped arena so that the top block ends at or past
  171. * `need_total`, then merge the new region into the top block. */
  172. static int heap_extend(unsigned int need_total)
  173. {
  174. unsigned int old = heap_bytes;
  175. unsigned int target;
  176. struct blk *b;
  177. if (need_total > HEAP_MAX_BYTES)
  178. return -1;
  179. target = need_total;
  180. if (target < old + HEAP_GROW_SLACK)
  181. target = old + HEAP_GROW_SLACK;
  182. if (target > HEAP_MAX_BYTES)
  183. target = HEAP_MAX_BYTES;
  184. target = (target + 4095u) & ~4095u;
  185. if (target > HEAP_MAX_BYTES)
  186. target = HEAP_MAX_BYTES;
  187. if (target < need_total || target <= old)
  188. return -1;
  189. if (__heap_grow(target) != 0)
  190. return -1;
  191. heap_bytes = target;
  192. if (top_blk && blk_is_free(top_blk)) {
  193. /* The top block already reaches `old`; extend it in place. */
  194. free_list_remove(top_blk);
  195. top_blk->size = (blk_size(top_blk) + (target - old)) | FREE_BIT;
  196. top_blk->magic = FREE_MAGIC;
  197. free_list_insert(top_blk);
  198. } else {
  199. b = blk_at(old);
  200. b->size = (target - old) | FREE_BIT;
  201. b->prev_size = top_blk ? blk_size(top_blk) : 0;
  202. b->magic = FREE_MAGIC;
  203. b->reserved = 0;
  204. free_list_insert(b);
  205. top_blk = b;
  206. }
  207. heap_end = target;
  208. return 0;
  209. }
  210. static int heap_init(void)
  211. {
  212. struct blk *b;
  213. void *base;
  214. if (heap_ready)
  215. return 0;
  216. base = __heap_map(HEAP_INIT_BYTES);
  217. if (!base)
  218. return -1;
  219. if ((unsigned long)base & (HEAP_ALIGN - 1u)) {
  220. __heap_unmap();
  221. return -1;
  222. }
  223. heap_base = (unsigned char *)base;
  224. heap_bytes = HEAP_INIT_BYTES;
  225. heap_end = HEAP_INIT_BYTES;
  226. free_head = 0;
  227. b = blk_at(0);
  228. b->size = HEAP_INIT_BYTES | FREE_BIT;
  229. b->prev_size = 0;
  230. b->magic = FREE_MAGIC;
  231. b->reserved = 0;
  232. top_blk = b;
  233. free_list_insert(b);
  234. heap_ready = 1;
  235. return 0;
  236. }
  237. static void *alloc_block(unsigned int need)
  238. {
  239. struct blk *b = free_head;
  240. void *payload;
  241. while (b && blk_size(b) < need)
  242. b = blk_link(b)->next;
  243. if (!b) {
  244. if (heap_extend(heap_end + need) != 0)
  245. return 0;
  246. b = free_head;
  247. while (b && blk_size(b) < need)
  248. b = blk_link(b)->next;
  249. if (!b)
  250. return 0;
  251. }
  252. free_list_remove(b);
  253. payload = (void *)((unsigned char *)b + HDR_SIZE);
  254. split_allocated(b, need);
  255. return payload;
  256. }
  257. void *malloc(size_t size)
  258. {
  259. unsigned int need;
  260. if (size == 0 || size > HEAP_MAX_BYTES)
  261. return 0;
  262. if (size > (size_t)(HEAP_MAX_BYTES - HDR_SIZE))
  263. return 0;
  264. if (!heap_ready && heap_init() != 0)
  265. return 0;
  266. need = align_up(HDR_SIZE + (unsigned int)size);
  267. if (need < MIN_BLOCK)
  268. need = MIN_BLOCK;
  269. if (need > HEAP_MAX_BYTES)
  270. return 0;
  271. return alloc_block(need);
  272. }
  273. static struct blk *block_from_ptr(void *ptr)
  274. {
  275. unsigned char *p = (unsigned char *)ptr;
  276. struct blk *b;
  277. unsigned int size;
  278. if (!heap_ready || !ptr)
  279. return 0;
  280. if (p < heap_base + HDR_SIZE || p >= heap_base + heap_bytes)
  281. return 0;
  282. b = (struct blk *)(void *)(p - HDR_SIZE);
  283. if (b->magic != ALLOC_MAGIC)
  284. return 0;
  285. size = blk_size(b);
  286. if (size < MIN_BLOCK || (unsigned char *)b + size > heap_base + heap_bytes)
  287. return 0;
  288. return b;
  289. }
  290. void free(void *ptr)
  291. {
  292. struct blk *b = block_from_ptr(ptr);
  293. if (b)
  294. free_block(b);
  295. }
  296. /* Payload bytes of an allocated block (QuickJS's memory accounting). */
  297. size_t malloc_usable_size(void *ptr)
  298. {
  299. struct blk *b = block_from_ptr(ptr);
  300. return b ? blk_size(b) - HDR_SIZE : 0;
  301. }
  302. void *calloc(size_t nmemb, size_t size)
  303. {
  304. size_t total;
  305. void *p;
  306. if (nmemb == 0 || size == 0)
  307. return 0;
  308. if (nmemb > (size_t)-1 / size)
  309. return 0;
  310. total = nmemb * size;
  311. if (total > HEAP_MAX_BYTES)
  312. return 0;
  313. p = malloc(total);
  314. if (p)
  315. memset(p, 0, total);
  316. return p;
  317. }
  318. void *realloc(void *ptr, size_t size)
  319. {
  320. struct blk *b;
  321. struct blk *next;
  322. unsigned int old;
  323. unsigned int need;
  324. unsigned int merged;
  325. unsigned int copy;
  326. if (!ptr)
  327. return malloc(size);
  328. if (size == 0) {
  329. free(ptr);
  330. return 0;
  331. }
  332. if (size > HEAP_MAX_BYTES ||
  333. size > (size_t)(HEAP_MAX_BYTES - HDR_SIZE))
  334. return 0;
  335. b = block_from_ptr(ptr);
  336. if (!b)
  337. return 0;
  338. need = align_up(HDR_SIZE + (unsigned int)size);
  339. if (need < MIN_BLOCK)
  340. need = MIN_BLOCK;
  341. old = blk_size(b);
  342. if (need <= old) {
  343. split_allocated(b, need);
  344. return ptr;
  345. }
  346. next = blk_next(b);
  347. if (next && blk_is_free(next) && old + blk_size(next) >= need) {
  348. free_list_remove(next);
  349. merged = old + blk_size(next);
  350. b->size = merged;
  351. b->magic = ALLOC_MAGIC;
  352. if (next == top_blk) {
  353. top_blk = b;
  354. } else {
  355. struct blk *after = blk_next(b);
  356. if (after)
  357. after->prev_size = merged;
  358. }
  359. split_allocated(b, need);
  360. return ptr;
  361. }
  362. {
  363. void *np = malloc(size);
  364. if (!np)
  365. return 0;
  366. copy = old - HDR_SIZE;
  367. if (copy > size)
  368. copy = (unsigned int)size;
  369. memcpy(np, ptr, copy);
  370. free(ptr);
  371. return np;
  372. }
  373. }
  374. void heap_reset(void)
  375. {
  376. if (!heap_ready)
  377. return;
  378. __heap_unmap();
  379. heap_base = 0;
  380. heap_bytes = 0;
  381. heap_end = 0;
  382. top_blk = 0;
  383. free_head = 0;
  384. heap_ready = 0;
  385. }