diff options
Diffstat (limited to 'LibC')
| -rw-r--r-- | LibC/Makefile | 3 | ||||
| -rw-r--r-- | LibC/malloc.cpp | 228 | ||||
| -rw-r--r-- | LibC/stdlib.cpp | 172 |
3 files changed, 230 insertions, 173 deletions
diff --git a/LibC/Makefile b/LibC/Makefile index 0a0190ff26..2deb7b5a35 100644 --- a/LibC/Makefile +++ b/LibC/Makefile @@ -17,6 +17,7 @@ LIBC_OBJS = \ strings.o \ mman.o \ dirent.o \ + malloc.o \ stdlib.o \ time.o \ utsname.o \ @@ -84,4 +85,4 @@ install: $(LIBRARY) cp $(LIBRARY) ../Base/usr/lib cp crt0.o ../Base/usr/lib/ cp crti.ao ../Base/usr/lib/crti.o - cp crtn.ao ../Base/usr/lib/crtn.o
\ No newline at end of file + cp crtn.ao ../Base/usr/lib/crtn.o diff --git a/LibC/malloc.cpp b/LibC/malloc.cpp new file mode 100644 index 0000000000..ade854eb4a --- /dev/null +++ b/LibC/malloc.cpp @@ -0,0 +1,228 @@ +#include <AK/Bitmap.h> +#include <AK/InlineLinkedList.h> +#include <sys/mman.h> +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <serenity.h> + +// FIXME: Thread safety. + +//#define MALLOC_DEBUG +#define MALLOC_SCRUB_BYTE 0x85 +#define FREE_SCRUB_BYTE 0x82 +#define MAGIC_PAGE_HEADER 0x42657274 +#define MAGIC_BIGALLOC_HEADER 0x42697267 +#define PAGE_ROUND_UP(x) ((((size_t)(x)) + PAGE_SIZE-1) & (~(PAGE_SIZE-1))) + +static bool s_log_malloc = false; +static bool s_scrub_malloc = true; +static bool s_scrub_free = true; +static unsigned short size_classes[] = { 8, 16, 32, 64, 128, 252, 508, 1016, 2036, 0 }; +static constexpr size_t num_size_classes = sizeof(size_classes) / sizeof(unsigned short); + +struct CommonHeader { + size_t m_magic; + size_t m_size; +}; + +struct BigAllocationBlock : public CommonHeader { + BigAllocationBlock(size_t size) + { + m_magic = MAGIC_BIGALLOC_HEADER; + m_size = size; + } + unsigned char* m_slot[0]; +}; + +struct FreelistEntry { + FreelistEntry* next; +}; + +struct ChunkedBlock : public CommonHeader, public InlineLinkedListNode<ChunkedBlock> { + ChunkedBlock(size_t bytes_per_chunk) + { + m_magic = MAGIC_PAGE_HEADER; + m_size = bytes_per_chunk; + m_free_chunks = chunk_capacity(); + m_freelist = (FreelistEntry*)chunk(0); + for (size_t i = 0; i < chunk_capacity(); ++i) { + auto* entry = (FreelistEntry*)chunk(i); + if (i != chunk_capacity() - 1) + entry->next = (FreelistEntry*)chunk(i + 1); + else + entry->next = nullptr; + } + + } + + ChunkedBlock* m_prev { nullptr }; + ChunkedBlock* m_next { nullptr }; + FreelistEntry* m_freelist { nullptr }; + + unsigned short m_free_chunks { 0 }; + + unsigned char m_slot[0]; + + void* chunk(int index) + { + return &m_slot[index * m_size]; + } + size_t bytes_per_chunk() const { return m_size; } + size_t free_chunks() const { return m_free_chunks; } + size_t used_chunks() const { return chunk_capacity() - m_free_chunks; } + size_t chunk_capacity() const { return (PAGE_SIZE - sizeof(ChunkedBlock)) / m_size; } +}; + +static InlineLinkedList<ChunkedBlock> g_allocators[num_size_classes]; + +static InlineLinkedList<ChunkedBlock>* allocator_for_size(size_t size, size_t& good_size) +{ + for (int i = 0; size_classes[i]; ++i) { + if (size <= size_classes[i]) { + good_size = size_classes[i]; + return &g_allocators[i]; + } + } + good_size = PAGE_ROUND_UP(size); + return nullptr; +} + +extern "C" { + +size_t malloc_good_size(size_t size) +{ + for (int i = 0; size_classes[i]; ++i) { + if (size < size_classes[i]) + return size_classes[i]; + } + return PAGE_ROUND_UP(size); +} + +static void* os_alloc(size_t size) +{ + return mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0); +} + +static void os_free(void* ptr, size_t size) +{ + int rc = munmap(ptr, size); + assert(rc == 0); +} + +void* malloc(size_t size) +{ + if (s_log_malloc) + dbgprintf("LibC: malloc(%u)\n", size); + + if (!size) + return nullptr; + + size_t good_size; + auto* allocator = allocator_for_size(size, good_size); + + if (!allocator) { + size_t real_size = sizeof(BigAllocationBlock) + size; + void* page_ptr = os_alloc(real_size); + BigAllocationBlock* bigalloc_header = new (page_ptr) BigAllocationBlock(real_size); + return &bigalloc_header->m_slot[0]; + } + assert(allocator); + + ChunkedBlock* block = nullptr; + for (block = allocator->head(); block; block = block->next()) { + if (block->free_chunks()) + break; + } + + if (!block) { + block = (ChunkedBlock*)os_alloc(PAGE_SIZE); + char buffer[64]; + snprintf(buffer, sizeof(buffer), "malloc() page (%u)", good_size); + set_mmap_name(block, PAGE_SIZE, buffer); + new (block) ChunkedBlock(good_size); + allocator->append(block); + } + + --block->m_free_chunks; + void* ptr = block->m_freelist; + block->m_freelist = block->m_freelist->next; +#ifdef MALLOC_DEBUG + dbgprintf("LibC: allocated %p (chunk %d in allocator %p, size %u)\n", ptr, index, page, page->bytes_per_chunk()); +#endif + if (s_scrub_malloc) + memset(ptr, MALLOC_SCRUB_BYTE, block->m_size); + return ptr; + + ASSERT_NOT_REACHED(); +} + +void free(void* ptr) +{ + if (!ptr) + return; + + void* page_base = (void*)((uintptr_t)ptr & (uintptr_t)~0xfff); + size_t magic = *(size_t*)page_base; + + if (magic == MAGIC_BIGALLOC_HEADER) { + auto* header = (BigAllocationBlock*)page_base; + os_free(header, header->m_size); + return; + } + + assert(magic == MAGIC_PAGE_HEADER); + auto* page = (ChunkedBlock*)page_base; + +#ifdef MALLOC_DEBUG + dbgprintf("LibC: freeing %p in allocator %p (size=%u, used=%u)\n", ptr, page, page->bytes_per_chunk(), page->used_chunks()); +#endif + + if (s_scrub_free) + memset(ptr, FREE_SCRUB_BYTE, page->bytes_per_chunk()); + + auto* entry = (FreelistEntry*)ptr; + entry->next = page->m_freelist; + page->m_freelist = entry; + + ++page->m_free_chunks; +} + +void* calloc(size_t count, size_t size) +{ + size_t new_size = count * size; + auto* ptr = malloc(new_size); + memset(ptr, 0, new_size); + return ptr; +} + +void* realloc(void* ptr, size_t size) +{ + if (!ptr) + return malloc(size); + + size_t old_size = 0; + void* page_base = (void*)((uintptr_t)ptr & (uintptr_t)~0xfff); + auto* header = (const CommonHeader*)page_base; + old_size = header->m_size; + + if (size == old_size) + return ptr; + auto* new_ptr = malloc(size); + memcpy(new_ptr, ptr, min(old_size, size)); + free(ptr); + return new_ptr; +} + +void __malloc_init() +{ + if (getenv("LIBC_NOSCRUB_MALLOC")) + s_scrub_malloc = false; + if (getenv("LIBC_NOSCRUB_FREE")) + s_scrub_free = false; + if (getenv("LIBC_LOG_MALLOC")) + s_log_malloc = true; +} + +} + diff --git a/LibC/stdlib.cpp b/LibC/stdlib.cpp index 656bd91ca7..17486f7c25 100644 --- a/LibC/stdlib.cpp +++ b/LibC/stdlib.cpp @@ -16,178 +16,6 @@ extern "C" { -#define MALLOC_SCRUB_BYTE 0x85 -#define FREE_SCRUB_BYTE 0x82 - -struct MallocHeader { - uint16_t first_chunk_index; - uint16_t chunk_count : 15; - bool is_mmap : 1; - size_t size; -}; - -#define CHUNK_SIZE 32 -#define POOL_SIZE 4 * 1048576 - -static const size_t malloc_budget = POOL_SIZE; -static byte s_malloc_map[POOL_SIZE / CHUNK_SIZE / 8]; -static byte* s_malloc_pool; - -static uint32_t s_malloc_sum_alloc = 0; -static uint32_t s_malloc_sum_free = POOL_SIZE; - -static bool s_log_malloc = false; -static bool s_scrub_malloc = true; -static bool s_scrub_free = true; - -void* malloc(size_t size) -{ - if (s_log_malloc) - dbgprintf("LibC: malloc(%u)\n", size); - - if (size == 0) - return nullptr; - - // We need space for the MallocHeader structure at the head of the block. - size_t real_size = size + sizeof(MallocHeader); - - if (real_size >= PAGE_SIZE) { - auto* memory = mmap(nullptr, real_size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0); - if (memory == MAP_FAILED) { - fprintf(stderr, "malloc() failed to mmap() for a %u-byte allocation: %s", size, strerror(errno)); - volatile char* crashme = (char*)0xf007d00d; - *crashme = 0; - return nullptr; - } - auto* header = (MallocHeader*)(memory); - byte* ptr = ((byte*)header) + sizeof(MallocHeader); - header->chunk_count = 0; - header->first_chunk_index = 0; - header->size = real_size; - header->is_mmap = true; - return ptr; - } - - if (s_malloc_sum_free < real_size) { - fprintf(stderr, "malloc(): Out of memory\ns_malloc_sum_free=%u, real_size=%u\n", s_malloc_sum_free, real_size); - ASSERT_NOT_REACHED(); - } - - size_t chunks_needed = real_size / CHUNK_SIZE; - if (real_size % CHUNK_SIZE) - chunks_needed++; - - size_t chunks_here = 0; - size_t first_chunk = 0; - - for (unsigned i = 0; i < (POOL_SIZE / CHUNK_SIZE / 8); ++i) { - if (s_malloc_map[i] == 0xff) { - // Skip over completely full bucket. - chunks_here = 0; - continue; - } - - // FIXME: This scan can be optimized further with TZCNT. - for (unsigned j = 0; j < 8; ++j) { - if ((s_malloc_map[i] & (1<<j))) { - // This is in use, so restart chunks_here counter. - chunks_here = 0; - continue; - } - if (chunks_here == 0) { - // Mark where potential allocation starts. - first_chunk = i * 8 + j; - } - - ++chunks_here; - - if (chunks_here == chunks_needed) { - auto* header = (MallocHeader*)(s_malloc_pool + (first_chunk * CHUNK_SIZE)); - byte* ptr = ((byte*)header) + sizeof(MallocHeader); - header->chunk_count = chunks_needed; - header->first_chunk_index = first_chunk; - header->is_mmap = false; - header->size = size; - - for (size_t k = first_chunk; k < (first_chunk + chunks_needed); ++k) - s_malloc_map[k / 8] |= 1 << (k % 8); - - s_malloc_sum_alloc += header->chunk_count * CHUNK_SIZE; - s_malloc_sum_free -= header->chunk_count * CHUNK_SIZE; - - if (s_scrub_malloc) - memset(ptr, MALLOC_SCRUB_BYTE, (header->chunk_count * CHUNK_SIZE) - sizeof(MallocHeader)); - return ptr; - } - } - } - - fprintf(stderr, "malloc(): Out of memory (no consecutive chunks found for size %u)\n", size); - volatile char* crashme = (char*)0xc007d00d; - *crashme = 0; - return nullptr; -} - -void free(void* ptr) -{ - if (!ptr) - return; - - auto* header = (MallocHeader*)((((byte*)ptr) - sizeof(MallocHeader))); - if (header->is_mmap) { - int rc = munmap(header, header->size); - if (rc < 0) - fprintf(stderr, "free(): munmap(%p) for allocation %p with size %u failed: %s\n", header, ptr, header->size, strerror(errno)); - return; - } - - for (int i = header->first_chunk_index; i < (header->first_chunk_index + header->chunk_count); ++i) - s_malloc_map[i / 8] &= ~(1 << (i % 8)); - - s_malloc_sum_alloc -= header->chunk_count * CHUNK_SIZE; - s_malloc_sum_free += header->chunk_count * CHUNK_SIZE; - - if (s_scrub_free) - memset(header, FREE_SCRUB_BYTE, header->chunk_count * CHUNK_SIZE); -} - -void __malloc_init() -{ - s_malloc_pool = (byte*)mmap(nullptr, malloc_budget, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0); - int rc = set_mmap_name(s_malloc_pool, malloc_budget, "malloc pool"); - if (rc < 0) - perror("set_mmap_name failed"); - - if (getenv("LIBC_NOSCRUB_MALLOC")) - s_scrub_malloc = false; - if (getenv("LIBC_NOSCRUB_FREE")) - s_scrub_free = false; - if (getenv("LIBC_LOG_MALLOC")) - s_log_malloc = true; -} - -void* calloc(size_t count, size_t size) -{ - size_t new_size = count * size; - auto* ptr = malloc(new_size); - memset(ptr, 0, new_size); - return ptr; -} - -void* realloc(void *ptr, size_t size) -{ - if (!ptr) - return malloc(size); - auto* header = (MallocHeader*)((((byte*)ptr) - sizeof(MallocHeader))); - size_t old_size = header->size; - if (size == old_size) - return ptr; - auto* new_ptr = malloc(size); - memcpy(new_ptr, ptr, min(old_size, size)); - free(ptr); - return new_ptr; -} - typedef void(*__atexit_handler)(); static int __atexit_handler_count = 0; static __atexit_handler __atexit_handlers[32]; |