diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | README.md | 55 | ||||
| -rw-r--r-- | inc/malloc_internal.h | 45 | ||||
| -rw-r--r-- | src/malloc.c | 43 | ||||
| -rw-r--r-- | src/zone.c | 42 |
5 files changed, 181 insertions, 6 deletions
@@ -16,7 +16,7 @@ LIBFT = $(LIBFT_DIR)/lib/libft.a NAME = $(LIBDIR)/libft_malloc_$(HOSTTYPE).so LINK = $(LIBDIR)/libft_malloc.so -SRCS = malloc.c free.c realloc.c +SRCS = malloc.c free.c realloc.c zone.c OBJS = $(SRCS:%.c=$(OBJDIR)/%.o) diff --git a/README.md b/README.md new file mode 100644 index 0000000..ef21ed7 --- /dev/null +++ b/README.md @@ -0,0 +1,55 @@ +# ft_malloc + +Custom dynamic memory allocator implementing `malloc`, `free`, and `realloc` as a shared library (`libft_malloc_$HOSTTYPE.so`). + +42 School project. + +## Build + +```bash +make # build lib/libft_malloc_$HOSTTYPE.so + symlink +make test # build & run tests +make clean # remove object files +make fclean # full clean (library, Libft, tests) +make re # fclean + all +``` + +## Usage + +The library is loaded at runtime via `LD_PRELOAD`, which instructs the Linux +dynamic linker to load the specified shared library **before** any other, +including libc. Any symbols it exports (such as `malloc`, `free`, `realloc`) +override the default ones. This makes it a drop-in replacement with no +recompilation needed: + +```bash +LD_PRELOAD=./lib/libft_malloc.so ./my_program +``` + +Every call to `malloc`, `free`, or `realloc` inside `my_program` (and any +library it uses) will go through `ft_malloc` instead of the system allocator. + +## API + +| Function | Description | +|---|---| +| `void *malloc(size_t size)` | Allocate `size` bytes | +| `void free(void *ptr)` | Release a previously allocated block | +| `void *realloc(void *ptr, size_t size)` | Resize a block to `size` bytes | +| `void show_alloc_mem(void)` | Print all zones and allocations to stdout | + +## Architecture + +Allocations are divided into three categories: + +| Category | Size range | Strategy | +|---|---|---| +| TINY | 1 -- 128 bytes | Pre-allocated zone (fits 100+ allocations) | +| SMALL | 129 -- 1024 bytes | Pre-allocated zone (fits 100+ allocations) | +| LARGE | 1025+ bytes | Individual `mmap` per allocation | + +TINY and SMALL zones are page-aligned regions obtained via `mmap`. New zones +are allocated on demand when the current one is full. LARGE allocations each +get their own `mmap` region and are released individually via `munmap`. + +All returned pointers are 16-byte aligned. diff --git a/inc/malloc_internal.h b/inc/malloc_internal.h new file mode 100644 index 0000000..fe275e3 --- /dev/null +++ b/inc/malloc_internal.h @@ -0,0 +1,45 @@ +/** + * @file malloc_internal.h + * @brief Internal data structures and macros for the ft_malloc allocator. + */ + +#ifndef MALLOC_INTERNAL_H +#define MALLOC_INTERNAL_H + +#include <stddef.h> + +#define TINY_MAX 128 +#define SMALL_MAX 1024 +#define ALIGNMENT 16 +/* Round x up to the nearest multiple of ALIGNMENT. */ +#define ALIGN(x) (((x) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1)) +#define MIN_ALLOC_COUNT 100 + +/* Header embedded before each allocation block inside a zone. */ +typedef struct s_chunk +{ + size_t size; + struct s_chunk *next; + int is_free; +} t_chunk; + +/* Header at the start of each mmap'd region. */ +typedef struct s_zone +{ + struct s_zone *next; + size_t size; +} t_zone; + +/* Global state: one linked list per zone category. */ +typedef struct s_heap +{ + t_zone *tiny; + t_zone *small; + t_zone *large; +} t_heap; + +extern t_heap g_heap; + +t_zone *zone_new (size_t alloc_max); + +#endif diff --git a/src/malloc.c b/src/malloc.c index 8982de0..268e0d1 100644 --- a/src/malloc.c +++ b/src/malloc.c @@ -1,15 +1,48 @@ /** * @file malloc.c - * @brief Stub implementation of malloc. + * @brief malloc implementation. */ #include "malloc.h" -#include "libft.h" +#include "malloc_internal.h" + +t_heap g_heap = { 0 }; void * malloc (size_t size) { - (void)size; - ft_putendl_fd ("MALLOC", 1); - return (NULL); + t_zone **zone_list; + t_zone *zone; + t_chunk *chunk; + size_t alloc_max; + + if (size == 0) + size = 1; + if (size <= TINY_MAX) + { + zone_list = &g_heap.tiny; + alloc_max = TINY_MAX; + } + else if (size <= SMALL_MAX) + { + zone_list = &g_heap.small; + alloc_max = SMALL_MAX; + } + else + { + zone_list = &g_heap.large; + alloc_max = size; + } + if (*zone_list == NULL) + { + zone = zone_new (alloc_max); + if (zone == NULL) + return (NULL); + *zone_list = zone; + } + else + zone = *zone_list; + chunk = (t_chunk *)((char *)zone + ALIGN (sizeof (t_zone))); + chunk->is_free = 0; + return ((char *)chunk + ALIGN (sizeof (t_chunk))); } diff --git a/src/zone.c b/src/zone.c new file mode 100644 index 0000000..724237b --- /dev/null +++ b/src/zone.c @@ -0,0 +1,42 @@ +/** + * @file zone.c + * @brief Zone allocation via mmap. + */ + +#include "malloc_internal.h" +#include <sys/mman.h> +#include <unistd.h> + +static size_t +_s_zone_size (size_t alloc_max) +{ + size_t chunk_size; + size_t total; + size_t page_size; + + chunk_size = ALIGN (sizeof (t_chunk)) + ALIGN (alloc_max); + total = ALIGN (sizeof (t_zone)) + MIN_ALLOC_COUNT * chunk_size; + page_size = (size_t)getpagesize (); + return ((total + page_size - 1) & ~(page_size - 1)); +} + +t_zone * +zone_new (size_t alloc_max) +{ + size_t zone_size; + t_zone *zone; + t_chunk *chunk; + + zone_size = _s_zone_size (alloc_max); + zone = mmap (NULL, zone_size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if (zone == MAP_FAILED) + return (NULL); + zone->next = NULL; + zone->size = zone_size; + chunk = (t_chunk *)((char *)zone + ALIGN (sizeof (t_zone))); + chunk->size = zone_size - ALIGN (sizeof (t_zone)) - ALIGN (sizeof (t_chunk)); + chunk->next = NULL; + chunk->is_free = 1; + return (zone); +} |