malloc.cpp 17 KB

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