malloc.cpp 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511
  1. /*
  2. * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Debug.h>
  7. #include <AK/ScopedValueRollback.h>
  8. #include <AK/Vector.h>
  9. #include <LibELF/AuxiliaryVector.h>
  10. #include <LibThreading/Lock.h>
  11. #include <assert.h>
  12. #include <errno.h>
  13. #include <mallocdefs.h>
  14. #include <serenity.h>
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <sys/internals.h>
  19. #include <sys/mman.h>
  20. #include <syscall.h>
  21. // FIXME: Thread safety.
  22. #define RECYCLE_BIG_ALLOCATIONS
  23. static Threading::Lock& malloc_lock()
  24. {
  25. alignas(Threading::Lock) static u8 lock_storage[sizeof(Threading::Lock)];
  26. return *reinterpret_cast<Threading::Lock*>(lock_storage);
  27. }
  28. constexpr size_t number_of_hot_chunked_blocks_to_keep_around = 16;
  29. constexpr size_t number_of_cold_chunked_blocks_to_keep_around = 16;
  30. constexpr size_t number_of_big_blocks_to_keep_around_per_size_class = 8;
  31. static bool s_log_malloc = false;
  32. static bool s_scrub_malloc = true;
  33. static bool s_scrub_free = true;
  34. static bool s_profiling = false;
  35. static bool s_in_userspace_emulator = false;
  36. ALWAYS_INLINE static void ue_notify_malloc(const void* ptr, size_t size)
  37. {
  38. if (s_in_userspace_emulator)
  39. syscall(SC_emuctl, 1, size, (FlatPtr)ptr);
  40. }
  41. ALWAYS_INLINE static void ue_notify_free(const void* ptr)
  42. {
  43. if (s_in_userspace_emulator)
  44. syscall(SC_emuctl, 2, (FlatPtr)ptr, 0);
  45. }
  46. ALWAYS_INLINE static void ue_notify_realloc(const void* ptr, size_t size)
  47. {
  48. if (s_in_userspace_emulator)
  49. syscall(SC_emuctl, 3, size, (FlatPtr)ptr);
  50. }
  51. ALWAYS_INLINE static void ue_notify_chunk_size_changed(const void* block, size_t chunk_size)
  52. {
  53. if (s_in_userspace_emulator)
  54. syscall(SC_emuctl, 4, chunk_size, (FlatPtr)block);
  55. }
  56. struct MallocStats {
  57. size_t number_of_malloc_calls;
  58. size_t number_of_big_allocator_hits;
  59. size_t number_of_big_allocator_purge_hits;
  60. size_t number_of_big_allocs;
  61. size_t number_of_hot_empty_block_hits;
  62. size_t number_of_cold_empty_block_hits;
  63. size_t number_of_cold_empty_block_purge_hits;
  64. size_t number_of_block_allocs;
  65. size_t number_of_blocks_full;
  66. size_t number_of_free_calls;
  67. size_t number_of_big_allocator_keeps;
  68. size_t number_of_big_allocator_frees;
  69. size_t number_of_freed_full_blocks;
  70. size_t number_of_hot_keeps;
  71. size_t number_of_cold_keeps;
  72. size_t number_of_frees;
  73. };
  74. static MallocStats g_malloc_stats = {};
  75. static size_t s_hot_empty_block_count { 0 };
  76. static ChunkedBlock* s_hot_empty_blocks[number_of_hot_chunked_blocks_to_keep_around] { nullptr };
  77. static size_t s_cold_empty_block_count { 0 };
  78. static ChunkedBlock* s_cold_empty_blocks[number_of_cold_chunked_blocks_to_keep_around] { nullptr };
  79. struct Allocator {
  80. size_t size { 0 };
  81. size_t block_count { 0 };
  82. ChunkedBlock::List usable_blocks;
  83. ChunkedBlock::List full_blocks;
  84. };
  85. struct BigAllocator {
  86. Vector<BigAllocationBlock*, number_of_big_blocks_to_keep_around_per_size_class> blocks;
  87. };
  88. // Allocators will be initialized in __malloc_init.
  89. // We can not rely on global constructors to initialize them,
  90. // because they must be initialized before other global constructors
  91. // are run. Similarly, we can not allow global destructors to destruct
  92. // them. We could have used AK::NeverDestoyed to prevent the latter,
  93. // but it would have not helped with the former.
  94. alignas(Allocator) static u8 g_allocators_storage[sizeof(Allocator) * num_size_classes];
  95. alignas(BigAllocator) static u8 g_big_allocators_storage[sizeof(BigAllocator)];
  96. static inline Allocator (&allocators())[num_size_classes]
  97. {
  98. return reinterpret_cast<Allocator(&)[num_size_classes]>(g_allocators_storage);
  99. }
  100. static inline BigAllocator (&big_allocators())[1]
  101. {
  102. return reinterpret_cast<BigAllocator(&)[1]>(g_big_allocators_storage);
  103. }
  104. static Allocator* allocator_for_size(size_t size, size_t& good_size)
  105. {
  106. for (size_t i = 0; size_classes[i]; ++i) {
  107. if (size <= size_classes[i]) {
  108. good_size = size_classes[i];
  109. return &allocators()[i];
  110. }
  111. }
  112. good_size = PAGE_ROUND_UP(size);
  113. return nullptr;
  114. }
  115. #ifdef RECYCLE_BIG_ALLOCATIONS
  116. static BigAllocator* big_allocator_for_size(size_t size)
  117. {
  118. if (size == 65536)
  119. return &big_allocators()[0];
  120. return nullptr;
  121. }
  122. #endif
  123. extern "C" {
  124. static void* os_alloc(size_t size, const char* name)
  125. {
  126. auto* ptr = serenity_mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0, ChunkedBlock::block_size, name);
  127. VERIFY(ptr != MAP_FAILED);
  128. return ptr;
  129. }
  130. static void os_free(void* ptr, size_t size)
  131. {
  132. int rc = munmap(ptr, size);
  133. assert(rc == 0);
  134. }
  135. enum class CallerWillInitializeMemory {
  136. No,
  137. Yes,
  138. };
  139. static void* malloc_impl(size_t size, CallerWillInitializeMemory caller_will_initialize_memory)
  140. {
  141. Threading::Locker locker(malloc_lock());
  142. if (s_log_malloc)
  143. dbgln("LibC: malloc({})", size);
  144. if (!size) {
  145. // Legally we could just return a null pointer here, but this is more
  146. // compatible with existing software.
  147. size = 1;
  148. }
  149. g_malloc_stats.number_of_malloc_calls++;
  150. size_t good_size;
  151. auto* allocator = allocator_for_size(size, good_size);
  152. if (!allocator) {
  153. size_t real_size = round_up_to_power_of_two(sizeof(BigAllocationBlock) + size, ChunkedBlock::block_size);
  154. #ifdef RECYCLE_BIG_ALLOCATIONS
  155. if (auto* allocator = big_allocator_for_size(real_size)) {
  156. if (!allocator->blocks.is_empty()) {
  157. g_malloc_stats.number_of_big_allocator_hits++;
  158. auto* block = allocator->blocks.take_last();
  159. int rc = madvise(block, real_size, MADV_SET_NONVOLATILE);
  160. bool this_block_was_purged = rc == 1;
  161. if (rc < 0) {
  162. perror("madvise");
  163. VERIFY_NOT_REACHED();
  164. }
  165. if (mprotect(block, real_size, PROT_READ | PROT_WRITE) < 0) {
  166. perror("mprotect");
  167. VERIFY_NOT_REACHED();
  168. }
  169. if (this_block_was_purged) {
  170. g_malloc_stats.number_of_big_allocator_purge_hits++;
  171. new (block) BigAllocationBlock(real_size);
  172. }
  173. ue_notify_malloc(&block->m_slot[0], size);
  174. return &block->m_slot[0];
  175. }
  176. }
  177. #endif
  178. g_malloc_stats.number_of_big_allocs++;
  179. auto* block = (BigAllocationBlock*)os_alloc(real_size, "malloc: BigAllocationBlock");
  180. new (block) BigAllocationBlock(real_size);
  181. ue_notify_malloc(&block->m_slot[0], size);
  182. return &block->m_slot[0];
  183. }
  184. ChunkedBlock* block = nullptr;
  185. for (auto& current : allocator->usable_blocks) {
  186. if (current.free_chunks()) {
  187. block = &current;
  188. break;
  189. }
  190. }
  191. if (!block && s_hot_empty_block_count) {
  192. g_malloc_stats.number_of_hot_empty_block_hits++;
  193. block = s_hot_empty_blocks[--s_hot_empty_block_count];
  194. if (block->m_size != good_size) {
  195. new (block) ChunkedBlock(good_size);
  196. ue_notify_chunk_size_changed(block, good_size);
  197. char buffer[64];
  198. snprintf(buffer, sizeof(buffer), "malloc: ChunkedBlock(%zu)", good_size);
  199. set_mmap_name(block, ChunkedBlock::block_size, buffer);
  200. }
  201. allocator->usable_blocks.append(*block);
  202. }
  203. if (!block && s_cold_empty_block_count) {
  204. g_malloc_stats.number_of_cold_empty_block_hits++;
  205. block = s_cold_empty_blocks[--s_cold_empty_block_count];
  206. int rc = madvise(block, ChunkedBlock::block_size, MADV_SET_NONVOLATILE);
  207. bool this_block_was_purged = rc == 1;
  208. if (rc < 0) {
  209. perror("madvise");
  210. VERIFY_NOT_REACHED();
  211. }
  212. rc = mprotect(block, ChunkedBlock::block_size, PROT_READ | PROT_WRITE);
  213. if (rc < 0) {
  214. perror("mprotect");
  215. VERIFY_NOT_REACHED();
  216. }
  217. if (this_block_was_purged || block->m_size != good_size) {
  218. if (this_block_was_purged)
  219. g_malloc_stats.number_of_cold_empty_block_purge_hits++;
  220. new (block) ChunkedBlock(good_size);
  221. ue_notify_chunk_size_changed(block, good_size);
  222. }
  223. allocator->usable_blocks.append(*block);
  224. }
  225. if (!block) {
  226. g_malloc_stats.number_of_block_allocs++;
  227. char buffer[64];
  228. snprintf(buffer, sizeof(buffer), "malloc: ChunkedBlock(%zu)", good_size);
  229. block = (ChunkedBlock*)os_alloc(ChunkedBlock::block_size, buffer);
  230. new (block) ChunkedBlock(good_size);
  231. allocator->usable_blocks.append(*block);
  232. ++allocator->block_count;
  233. }
  234. --block->m_free_chunks;
  235. void* ptr = block->m_freelist;
  236. if (ptr) {
  237. block->m_freelist = block->m_freelist->next;
  238. } else {
  239. ptr = block->m_slot + block->m_next_lazy_freelist_index * block->m_size;
  240. block->m_next_lazy_freelist_index++;
  241. }
  242. VERIFY(ptr);
  243. if (block->is_full()) {
  244. g_malloc_stats.number_of_blocks_full++;
  245. dbgln_if(MALLOC_DEBUG, "Block {:p} is now full in size class {}", block, good_size);
  246. allocator->usable_blocks.remove(*block);
  247. allocator->full_blocks.append(*block);
  248. }
  249. dbgln_if(MALLOC_DEBUG, "LibC: allocated {:p} (chunk in block {:p}, size {})", ptr, block, block->bytes_per_chunk());
  250. if (s_scrub_malloc && caller_will_initialize_memory == CallerWillInitializeMemory::No)
  251. memset(ptr, MALLOC_SCRUB_BYTE, block->m_size);
  252. ue_notify_malloc(ptr, size);
  253. return ptr;
  254. }
  255. static void free_impl(void* ptr)
  256. {
  257. ScopedValueRollback rollback(errno);
  258. if (!ptr)
  259. return;
  260. g_malloc_stats.number_of_free_calls++;
  261. Threading::Locker locker(malloc_lock());
  262. void* block_base = (void*)((FlatPtr)ptr & ChunkedBlock::ChunkedBlock::block_mask);
  263. size_t magic = *(size_t*)block_base;
  264. if (magic == MAGIC_BIGALLOC_HEADER) {
  265. auto* block = (BigAllocationBlock*)block_base;
  266. #ifdef RECYCLE_BIG_ALLOCATIONS
  267. if (auto* allocator = big_allocator_for_size(block->m_size)) {
  268. if (allocator->blocks.size() < number_of_big_blocks_to_keep_around_per_size_class) {
  269. g_malloc_stats.number_of_big_allocator_keeps++;
  270. allocator->blocks.append(block);
  271. size_t this_block_size = block->m_size;
  272. if (mprotect(block, this_block_size, PROT_NONE) < 0) {
  273. perror("mprotect");
  274. VERIFY_NOT_REACHED();
  275. }
  276. if (madvise(block, this_block_size, MADV_SET_VOLATILE) != 0) {
  277. perror("madvise");
  278. VERIFY_NOT_REACHED();
  279. }
  280. return;
  281. }
  282. }
  283. #endif
  284. g_malloc_stats.number_of_big_allocator_frees++;
  285. os_free(block, block->m_size);
  286. return;
  287. }
  288. assert(magic == MAGIC_PAGE_HEADER);
  289. auto* block = (ChunkedBlock*)block_base;
  290. dbgln_if(MALLOC_DEBUG, "LibC: freeing {:p} in allocator {:p} (size={}, used={})", ptr, block, block->bytes_per_chunk(), block->used_chunks());
  291. if (s_scrub_free)
  292. memset(ptr, FREE_SCRUB_BYTE, block->bytes_per_chunk());
  293. auto* entry = (FreelistEntry*)ptr;
  294. entry->next = block->m_freelist;
  295. block->m_freelist = entry;
  296. if (block->is_full()) {
  297. size_t good_size;
  298. auto* allocator = allocator_for_size(block->m_size, good_size);
  299. dbgln_if(MALLOC_DEBUG, "Block {:p} no longer full in size class {}", block, good_size);
  300. g_malloc_stats.number_of_freed_full_blocks++;
  301. allocator->full_blocks.remove(*block);
  302. allocator->usable_blocks.prepend(*block);
  303. }
  304. ++block->m_free_chunks;
  305. if (!block->used_chunks()) {
  306. size_t good_size;
  307. auto* allocator = allocator_for_size(block->m_size, good_size);
  308. if (s_hot_empty_block_count < number_of_hot_chunked_blocks_to_keep_around) {
  309. dbgln_if(MALLOC_DEBUG, "Keeping hot block {:p} around", block);
  310. g_malloc_stats.number_of_hot_keeps++;
  311. allocator->usable_blocks.remove(*block);
  312. s_hot_empty_blocks[s_hot_empty_block_count++] = block;
  313. return;
  314. }
  315. if (s_cold_empty_block_count < number_of_cold_chunked_blocks_to_keep_around) {
  316. dbgln_if(MALLOC_DEBUG, "Keeping cold block {:p} around", block);
  317. g_malloc_stats.number_of_cold_keeps++;
  318. allocator->usable_blocks.remove(*block);
  319. s_cold_empty_blocks[s_cold_empty_block_count++] = block;
  320. mprotect(block, ChunkedBlock::block_size, PROT_NONE);
  321. madvise(block, ChunkedBlock::block_size, MADV_SET_VOLATILE);
  322. return;
  323. }
  324. dbgln_if(MALLOC_DEBUG, "Releasing block {:p} for size class {}", block, good_size);
  325. g_malloc_stats.number_of_frees++;
  326. allocator->usable_blocks.remove(*block);
  327. --allocator->block_count;
  328. os_free(block, ChunkedBlock::block_size);
  329. }
  330. }
  331. [[gnu::flatten]] void* malloc(size_t size)
  332. {
  333. void* ptr = malloc_impl(size, CallerWillInitializeMemory::No);
  334. if (s_profiling)
  335. perf_event(PERF_EVENT_MALLOC, size, reinterpret_cast<FlatPtr>(ptr));
  336. return ptr;
  337. }
  338. [[gnu::flatten]] void free(void* ptr)
  339. {
  340. if (s_profiling)
  341. perf_event(PERF_EVENT_FREE, reinterpret_cast<FlatPtr>(ptr), 0);
  342. ue_notify_free(ptr);
  343. free_impl(ptr);
  344. }
  345. void* calloc(size_t count, size_t size)
  346. {
  347. size_t new_size = count * size;
  348. auto* ptr = malloc_impl(new_size, CallerWillInitializeMemory::Yes);
  349. if (ptr)
  350. memset(ptr, 0, new_size);
  351. return ptr;
  352. }
  353. size_t malloc_size(void* ptr)
  354. {
  355. if (!ptr)
  356. return 0;
  357. Threading::Locker locker(malloc_lock());
  358. void* page_base = (void*)((FlatPtr)ptr & ChunkedBlock::block_mask);
  359. auto* header = (const CommonHeader*)page_base;
  360. auto size = header->m_size;
  361. if (header->m_magic == MAGIC_BIGALLOC_HEADER)
  362. size -= sizeof(CommonHeader);
  363. else
  364. VERIFY(header->m_magic == MAGIC_PAGE_HEADER);
  365. return size;
  366. }
  367. size_t malloc_good_size(size_t size)
  368. {
  369. size_t good_size;
  370. allocator_for_size(size, good_size);
  371. return good_size;
  372. }
  373. void* realloc(void* ptr, size_t size)
  374. {
  375. if (!ptr)
  376. return malloc(size);
  377. if (!size) {
  378. free(ptr);
  379. return nullptr;
  380. }
  381. Threading::Locker locker(malloc_lock());
  382. auto existing_allocation_size = malloc_size(ptr);
  383. if (size <= existing_allocation_size) {
  384. ue_notify_realloc(ptr, size);
  385. return ptr;
  386. }
  387. auto* new_ptr = malloc(size);
  388. if (new_ptr) {
  389. memcpy(new_ptr, ptr, min(existing_allocation_size, size));
  390. free(ptr);
  391. }
  392. return new_ptr;
  393. }
  394. void __malloc_init()
  395. {
  396. new (&malloc_lock()) Threading::Lock();
  397. s_in_userspace_emulator = (int)syscall(SC_emuctl, 0) != -ENOSYS;
  398. if (s_in_userspace_emulator) {
  399. // Don't bother scrubbing memory if we're running in UE since it
  400. // keeps track of heap memory anyway.
  401. s_scrub_malloc = false;
  402. s_scrub_free = false;
  403. }
  404. if (secure_getenv("LIBC_NOSCRUB_MALLOC"))
  405. s_scrub_malloc = false;
  406. if (secure_getenv("LIBC_NOSCRUB_FREE"))
  407. s_scrub_free = false;
  408. if (secure_getenv("LIBC_LOG_MALLOC"))
  409. s_log_malloc = true;
  410. if (secure_getenv("LIBC_PROFILE_MALLOC"))
  411. s_profiling = true;
  412. for (size_t i = 0; i < num_size_classes; ++i) {
  413. new (&allocators()[i]) Allocator();
  414. allocators()[i].size = size_classes[i];
  415. }
  416. new (&big_allocators()[0])(BigAllocator);
  417. }
  418. void serenity_dump_malloc_stats()
  419. {
  420. dbgln("# malloc() calls: {}", g_malloc_stats.number_of_malloc_calls);
  421. dbgln();
  422. dbgln("big alloc hits: {}", g_malloc_stats.number_of_big_allocator_hits);
  423. dbgln("big alloc hits that were purged: {}", g_malloc_stats.number_of_big_allocator_purge_hits);
  424. dbgln("big allocs: {}", g_malloc_stats.number_of_big_allocs);
  425. dbgln();
  426. dbgln("empty hot block hits: {}", g_malloc_stats.number_of_hot_empty_block_hits);
  427. dbgln("empty cold block hits: {}", g_malloc_stats.number_of_cold_empty_block_hits);
  428. dbgln("empty cold block hits that were purged: {}", g_malloc_stats.number_of_cold_empty_block_purge_hits);
  429. dbgln("block allocs: {}", g_malloc_stats.number_of_block_allocs);
  430. dbgln("filled blocks: {}", g_malloc_stats.number_of_blocks_full);
  431. dbgln();
  432. dbgln("# free() calls: {}", g_malloc_stats.number_of_free_calls);
  433. dbgln();
  434. dbgln("big alloc keeps: {}", g_malloc_stats.number_of_big_allocator_keeps);
  435. dbgln("big alloc frees: {}", g_malloc_stats.number_of_big_allocator_frees);
  436. dbgln();
  437. dbgln("full block frees: {}", g_malloc_stats.number_of_freed_full_blocks);
  438. dbgln("number of hot keeps: {}", g_malloc_stats.number_of_hot_keeps);
  439. dbgln("number of cold keeps: {}", g_malloc_stats.number_of_cold_keeps);
  440. dbgln("number of frees: {}", g_malloc_stats.number_of_frees);
  441. }
  442. }