I'm currently recoding my own version of malloc(), I'm currently only using sbrk() and would like to implement a version with mmap() later on.
Here's the block metadata structure:
typedef struct MV_BLOCK_S {
uint32_t magic;
struct MV_BLOCK_S *prev;
uint64_t size;
uint8_t state; // First bit: 0 = block free, 1 = block used, second bit: 0 = sbrk() 1 = mmap()
void *data;
struct MV_BLOCK_S *next;
} mv_block_t;
Some of the macros I use:
#define MV_ALIGN(x) (((((x) - 1) >> 3) << 3) + 8)
#define MV_BLOCK_T_SIZE MV_ALIGN(sizeof(mv_block_t))
#define MV_BLOCK_T_END_OFFSET MV_BLOCK_T_SIZE - sizeof(mv_block_t)
#define MV_MAGIC 213213213
#define MV_MMAP_THRESHOLD 4096 // WIP if size > 4096, use mmap()
#define MV_FREE_BIT(x) (x & 0x01)
#define MV_ALLOC_BIT(x) ((x >> 1) & 0x01)
For the moment, only the malloc() function is implemented:
static void *mv_heap = NULL;
static mv_block_t *end_heap = NULL;
static mv_block_t *last_block = NULL;
static size_t last_size = 0;
static void *mv_search_block(size_t size)
{
mv_block_t *block = NULL;
if (last_block == NULL && last_size < size) {
block = mv_heap;
} else {
block = last_block;
}
while (block != NULL) {
if (block->size >= size && MV_FREE_BIT(block->state) == 0)
break;
block = block->next;
}
if (block != NULL) {
if (mv_split_block(block, size) == 0) {
end_heap = block->next;
}
block->state = 0x02;
} else {
if (sbrk(size) == (void *)-1)
return (NULL);
block = sbrk(0);
block->magic = MV_MAGIC;
block->prev = end_heap;
block->size = size - MV_BLOCK_T_SIZE;
block->state = 0x02;
block->data = (unsigned char *)block + MV_BLOCK_T_SIZE;
block->next = NULL;
end_heap = block;
}
last_block = block;
last_size = size;
return (block->data);
}
static void *init_heap_sbrk(size_t size)
{
mv_heap = sbrk(size);
if (mv_heap == (void *)-1)
return (NULL);
mv_block_t *block = mv_heap;
block->magic = MV_MAGIC;
block->prev = NULL;
block->size = size - MV_BLOCK_T_SIZE;
block->state = 0x01;
block->data = (unsigned char *)mv_heap + MV_BLOCK_T_SIZE;
block->next = NULL;
end_heap = block;
return (block->data);
}
void *malloc(size_t size)
{
if (size == 0)
size = MV_BLOCK_T_SIZE;
else
size = MV_ALIGN(size) + MV_BLOCK_T_SIZE;
if (size >= PTRDIFF_MAX)
return (NULL);
if (mv_heap == NULL)
return init_heap_sbrk(size);
return (mv_search_block(size));
}
To manage memory fragmentation (merge / block release / split) :
int mv_merge_block(mv_block_t *current)
{
mv_block_t *prev = current->prev;
mv_block_t *next = current->next;
if (prev != NULL && MV_FREE_BIT(prev->state) == 0) {
prev->size += current->size + MV_BLOCK_T_SIZE;
prev->next = next;
current = prev;
}
if (next != NULL && MV_FREE_BIT(next->state) == 0) {
if (next->next != NULL) {
current->size += next->size + MV_BLOCK_T_SIZE;
current->next = next->next;
} else {
current->next = NULL;
if (sbrk(-(next->size + MV_BLOCK_T_SIZE)) == (void *)-1)
return (-1);
}
}
return (0);
}
int mv_suppress_block(mv_block_t *block)
{
if (block == NULL)
return (-1);
if (MV_FREE_BIT(block->state) == 0 && block->next == NULL) {
if (block->prev != NULL) {
block->prev->next = NULL;
}
if (sbrk(-(block->size + MV_BLOCK_T_SIZE)) == (void *)-1)
return (-1);
return (0);
}
return (-1);
}
int mv_split_block(mv_block_t *block, size_t size)
{
size_t new_block_size = block->size - size;
mv_block_t *new_block = NULL;
if (new_block_size < MV_BLOCK_T_SIZE)
return (-1);
if (mv_suppress_block(block->next) == 0) {
return (-1);
}
new_block = (mv_block_t *)(unsigned char *)block + size;
new_block->magic = MV_MAGIC;
new_block->prev = block;
new_block->size = new_block_size - MV_BLOCK_T_SIZE;
new_block->state = 0x00;
new_block->data = (unsigned char *)new_block + MV_BLOCK_T_SIZE;
new_block->next = block->next;
block->size = size;
block->next = new_block;
return (0);
}
To be able to view my blocks, I've coded functions that are supposed to display useful information:
void mv_dump_block(mv_block_t *block)
{
uint8_t usage_bit = block->state & 0x01;
uint8_t allocation_method_bit = (block->state >> 1) & 0x01;
printf("========================================\n");
printf("Block : %p\n", (void *)block);
printf("Magic : %d\n", block->magic);
printf("Prev : %p\n", (void *)block->prev);
printf("Size : %ld\n", block->size);
printf("State of block : %s\n", (usage_bit == 0) ? "Available" : "Busy");
printf("Allocation's type : %s\n", (allocation_method_bit == 0) ? "sbrk" : "mmap");
printf("Data : %p\n", block->data);
printf("Next : %p\n", (void *)block->next);
printf("========================================\n");
}
void mv_dump_heap(void *ptr)
{
mv_block_t *block = mv_get_block(ptr);
while (block != NULL && block->prev != NULL)
block = block->prev;
while (block != NULL) {
mv_dump_block(block);
block = block->next;
}
}
mv_block_t *mv_get_block(void *ptr)
{
mv_block_t *block = (mv_block_t *)((unsigned char *)ptr - MV_BLOCK_T_SIZE);
if (block->magic != MV_MAGIC)
return (NULL);
return (block);
}
Here is my main() test function:
int main(void)
{
char *ptr = malloc(10);
char *ptr2 = malloc(4096);
mv_dump_heap(ptr);
(void)ptr2;
return (0);
}
And here's the gdb report:
Program received signal SIGSEGV, Segmentation fault.
0x00005555555557f2 in mv_split_block (block=0x55555555a070, size=1072) at src/fragmentation.c:52
52 new_block->magic = MV_MAGIC;
For the moment, I'm compiling with GLIBC and the following flags: -m64 -fPIC -pedantic -Wall -Wextra -Werror -ggdb3
Can you help me solve this, I guess the new_block variable is misaligned during the split.
UPDATE
Since my test with malloc(0) is apparently disturbing in the comments, I've replaced it with 10 and the same result. For those of you who have misread, I have for the moment implemented ONLY malloc().
I've also added my Makefile :
CC = gcc
CFLAGS = -m64 -fPIC -pedantic -Wall -Wextra -Werror -ggdb3
LFLAGS = -I./include
SRC = $(shell find src/ -type f -name '*.c')
OBJ = $(SRC:.c=.o)
NAME = test/vlibc_malloc_test
all: $(NAME)
$(NAME): $(OBJ)
@$(CC) $(CFLAGS) $(OBJ) -o $(NAME) $(LFLAGS)
%.o: %.c
@$(CC) $(CFLAGS) $(LFLAGS) -c $< -o $@
clean:
@rm -f $(OBJ)
fclean: clean
@rm -f $(NAME)
re: fclean all
.PHONY: clean fclean re
Reproducible code set
The complete code is here : Online GDB
The problem may come from the incompatibility between your malloc function and the one from the C library: the printf function directly or indirectly uses malloc to allocate some memory for internal use and the blocks thus allocated are freed with free. You replaced malloc so printf and/or the FILE handling functions use your malloc but the free function cannot handle the blocks allocated by your malloc function and this leads to undefined behavior and a segmentation fault.
You should use different names for your malloc clone and implement all the allocation functions: malloc, calloc, realloc, aligned_alloc free, strdup... and possibly some other ones, and test these thoroughly before you change the names to use the standard names.
Note also these remarks:
[major]: in function mv_split_block, new_block is computed as new_block = (mv_block_t *)(unsigned char *)block + size;, which is incorrect. You should use:
new_block = (mv_block_t *)((unsigned char *)block + size);
[major]: you must parenthesize macro arguments in the definitions to avoid potential operator precedence problems at the expansion sites. For example:
#define MV_BLOCK_T_END_OFFSET (MV_BLOCK_T_SIZE - sizeof(mv_block_t))
#define MV_FREE_BIT(x) ((x) & 0x01)
#define MV_ALLOC_BIT(x) (((x) >> 1) & 0x01)
[minor]: the macro MV_FREE_BIT is error prone as it evaluates to 0 for available blocks and non zero for blocks in use. You should either change the bit value or change the macro name to MV_BUSY_BIT.
[minor]: you should try and minimize the occurrence of padding in the header structure:
typedef struct MV_BLOCK_S {
uint32_t magic;
uint32_t state; // First bit: 0 = block free, 1 = block used, second bit: 0 = sbrk() 1 = mmap()
uint64_t size;
struct MV_BLOCK_S *prev;
void *data;
struct MV_BLOCK_S *next;
} mv_block_t;
[remark]: there is actually no need for the data member as the data associated with the header is right after the structure, ie: (void *)(block + 1).
[remark]: the size member is also redundant except for the first and last blocks: you could use (uint64_t)((unsigned char *)block->next - (unsigned char *)block->prev - MV_BLOCK_T_SIZE).
[minor]: in mv_split_block, in case if (new_block_size < MV_BLOCK_T_SIZE) you should return 0 as the block is not large enough to be split but large enough to accommodate the allocation request.
[remark]: function mv_dump_heap should not need an argument: it should dump the heap pointed to by global variable mv_heap.