malloc() and free() for Linux with system calls
up vote
11
down vote
favorite
I have written an implementation of malloc()
and free()
for Linux using the sbrk()
system call.
When memory is requested, it checks if there is a large enough chunk available already, if there is then that gets returned to the user, otherwise a new block of memory will be requested from the kernel. When memory is free'd the block is marked as such and kept for later, and adjacent free blocks of memory are merged together. If there is a free block at the end of the heap that is larger than the size of a page then the largest possible multiple of page size bytes is returned to the kernel.
This is the first version of this code and my first time working with system calls, as such I have kept things fairly simple and not included padding or a realloc()
implementation. Both of these will feature in the next version along with any improvements suggested here.
malloc.h
#ifndef _MALLOC_H
#define _MALLOC_H
#include <stdbool.h>
#define PAGE_SIZE 4096
typedef struct mem_header mem_header;
struct mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
void * _malloc(size_t size);
void _free(void * ptr);
#endif
malloc.c
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include "malloc.h"
static inline void eat_next_block(mem_header * header_ptr);
mem_header * head_ptr = NULL;
mem_header * tail_ptr = NULL;
void * _malloc(size_t size)
{
if(!size)
return NULL;
bool heap_empty = false;
size_t additional_space = 0;
if(!head_ptr) {
/* Try and get the base pointer for the heap, as it is defined sbrk(0) could suprisingly fail */
if((head_ptr = tail_ptr = sbrk(0)) == (void *) -1)
return NULL;
heap_empty = true;
} else {
/* Try and find enough free space to give the user */
for(mem_header * heap_ptr = head_ptr; heap_ptr; heap_ptr = heap_ptr->next) {
if(heap_ptr->free && heap_ptr->size >= size + sizeof(mem_header)) {
/* Set up free block, if there is space for one */
if(heap_ptr->size > size + 2 * sizeof(mem_header)) {
mem_header * next_block = (mem_header *)((char *) heap_ptr + size + sizeof(mem_header));
next_block->size = heap_ptr->size - size - sizeof(mem_header);
next_block->free = true;
next_block->prev = heap_ptr;
next_block->next = heap_ptr->next;
heap_ptr->next = next_block;
} else {
size = heap_ptr->size;
}
/* Configure newly allocated block */
heap_ptr->size = size;
heap_ptr->free = false;
if((tail_ptr == heap_ptr) && heap_ptr->next)
tail_ptr = heap_ptr->next;
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
}
}
/* If we have a free block at the end that isn't large enough we can subtract its size from our allocation requirement */
if(tail_ptr->free)
additional_space = tail_ptr->size + sizeof(mem_header);
}
/* Determine how much we need to grow the heap by, alligned to a multiple of PAGE_SIZE bytes */
size_t block_size = size + sizeof(mem_header) - additional_space;
if(block_size % PAGE_SIZE != 0)
block_size += PAGE_SIZE - (block_size % PAGE_SIZE);
/* Grow the heap */
if(sbrk(block_size) == (void *) -1)
return NULL;
/* Configure the memory block to be returned */
if(heap_empty) {
tail_ptr->prev = NULL;
} else if(!tail_ptr->free) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + tail_ptr->size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->prev = tail_ptr_temp;
}
tail_ptr->next = NULL;
tail_ptr->free = false;
tail_ptr->size = size;
/* Configure any free space at the top of the heap */
void * return_ptr = (void *)((char *) tail_ptr + sizeof(mem_header));
size_t leftover = block_size + additional_space - (size + sizeof(mem_header));
if(leftover > sizeof(mem_header)) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->free = true;
tail_ptr->prev = tail_ptr_temp;
tail_ptr->next = NULL;
tail_ptr->size = leftover - sizeof(mem_header);
} else {
tail_ptr->size += leftover;
}
return return_ptr;
}
void _free(void * ptr)
{
if(!ptr)
return;
mem_header * header_ptr = (mem_header *) ptr;
header_ptr--;
if(header_ptr->free)
return;
header_ptr->free = true;
/* If there is a free block in front then consume it */
if(header_ptr->next && header_ptr->next->free)
eat_next_block(header_ptr);
/* If there is a free block directly behind then jump to it and consume the block infront */
if(header_ptr->prev && header_ptr->prev->free) {
header_ptr = header_ptr->prev;
eat_next_block(header_ptr);
}
/* If there is a sufficient amount of memory at the end of the heap, return it to the kernel */
if(!header_ptr->next && header_ptr->size + sizeof(mem_header) >= PAGE_SIZE) {
size_t leftover = (header_ptr->size + sizeof(mem_header)) % PAGE_SIZE;
size_t excess = header_ptr->size + sizeof(mem_header) - leftover;
if(!header_ptr->prev) {
head_ptr = tail_ptr = NULL;
} else {
header_ptr->prev->size += leftover;
header_ptr->prev->next = NULL;
}
sbrk(-excess);
}
return;
}
static inline void eat_next_block(mem_header * header_ptr)
{
header_ptr->size += header_ptr->next->size + sizeof(mem_header);
header_ptr->next = header_ptr->next->next;
if(header_ptr->next)
header_ptr->next->prev = header_ptr;
return;
}
malloc_test.c
#include <unistd.h>
#include <stdio.h>
#include "malloc.h"
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))
int main()
{
char * mem_block[4];
char * initial_break = sbrk(0);
size_t alloc_size[4] = { 8192, 16384, 405, 32768 };
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++) {
if(!(mem_block[i] = _malloc(alloc_size[i] * sizeof(char)))) {
fprintf(stderr, "Error: Could not allocate memory!n");
return -1;
}
}
char * final_malloc_break = sbrk(0);
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++)
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
_free(mem_block[1]);
_free(mem_block[0]);
_free(mem_block[3]);
_free(mem_block[2]);
char * final_free_break = sbrk(0);
size_t total_allocated = (size_t) final_malloc_break - (size_t) initial_break;
size_t excess_pages = ((size_t) final_free_break - (size_t) initial_break) / PAGE_SIZE;
printf("ntHeap Break PositionsnnInitial break:tt%pnFinal allocation break:t%pnFinal free break:t%pnn", initial_break, final_malloc_break, final_free_break);
if(excess_pages)
printf("Error: %zu pages were not free'dn", excess_pages);
else
printf("All allocated pages free'dn");
printf("Allocated %zu bytes (%zu pages)n", total_allocated, total_allocated / PAGE_SIZE);
return 0;
}
All code was compiled with gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) and tested on Debian GNU/Linux 9.5 (stretch) with the command gcc malloc.c malloc_test.c -o malloc -Wall -Wextra -Wpedantic
Note: This code was designed to fulfill a specification for one of my classes, which included a page size of 4096 bytes and function names starting with underscores. I was unaware about the portability concerns arising from these and even though it wasn't a tag, portability is something I definitely want to know about
performance c memory-management linux portability
add a comment |
up vote
11
down vote
favorite
I have written an implementation of malloc()
and free()
for Linux using the sbrk()
system call.
When memory is requested, it checks if there is a large enough chunk available already, if there is then that gets returned to the user, otherwise a new block of memory will be requested from the kernel. When memory is free'd the block is marked as such and kept for later, and adjacent free blocks of memory are merged together. If there is a free block at the end of the heap that is larger than the size of a page then the largest possible multiple of page size bytes is returned to the kernel.
This is the first version of this code and my first time working with system calls, as such I have kept things fairly simple and not included padding or a realloc()
implementation. Both of these will feature in the next version along with any improvements suggested here.
malloc.h
#ifndef _MALLOC_H
#define _MALLOC_H
#include <stdbool.h>
#define PAGE_SIZE 4096
typedef struct mem_header mem_header;
struct mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
void * _malloc(size_t size);
void _free(void * ptr);
#endif
malloc.c
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include "malloc.h"
static inline void eat_next_block(mem_header * header_ptr);
mem_header * head_ptr = NULL;
mem_header * tail_ptr = NULL;
void * _malloc(size_t size)
{
if(!size)
return NULL;
bool heap_empty = false;
size_t additional_space = 0;
if(!head_ptr) {
/* Try and get the base pointer for the heap, as it is defined sbrk(0) could suprisingly fail */
if((head_ptr = tail_ptr = sbrk(0)) == (void *) -1)
return NULL;
heap_empty = true;
} else {
/* Try and find enough free space to give the user */
for(mem_header * heap_ptr = head_ptr; heap_ptr; heap_ptr = heap_ptr->next) {
if(heap_ptr->free && heap_ptr->size >= size + sizeof(mem_header)) {
/* Set up free block, if there is space for one */
if(heap_ptr->size > size + 2 * sizeof(mem_header)) {
mem_header * next_block = (mem_header *)((char *) heap_ptr + size + sizeof(mem_header));
next_block->size = heap_ptr->size - size - sizeof(mem_header);
next_block->free = true;
next_block->prev = heap_ptr;
next_block->next = heap_ptr->next;
heap_ptr->next = next_block;
} else {
size = heap_ptr->size;
}
/* Configure newly allocated block */
heap_ptr->size = size;
heap_ptr->free = false;
if((tail_ptr == heap_ptr) && heap_ptr->next)
tail_ptr = heap_ptr->next;
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
}
}
/* If we have a free block at the end that isn't large enough we can subtract its size from our allocation requirement */
if(tail_ptr->free)
additional_space = tail_ptr->size + sizeof(mem_header);
}
/* Determine how much we need to grow the heap by, alligned to a multiple of PAGE_SIZE bytes */
size_t block_size = size + sizeof(mem_header) - additional_space;
if(block_size % PAGE_SIZE != 0)
block_size += PAGE_SIZE - (block_size % PAGE_SIZE);
/* Grow the heap */
if(sbrk(block_size) == (void *) -1)
return NULL;
/* Configure the memory block to be returned */
if(heap_empty) {
tail_ptr->prev = NULL;
} else if(!tail_ptr->free) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + tail_ptr->size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->prev = tail_ptr_temp;
}
tail_ptr->next = NULL;
tail_ptr->free = false;
tail_ptr->size = size;
/* Configure any free space at the top of the heap */
void * return_ptr = (void *)((char *) tail_ptr + sizeof(mem_header));
size_t leftover = block_size + additional_space - (size + sizeof(mem_header));
if(leftover > sizeof(mem_header)) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->free = true;
tail_ptr->prev = tail_ptr_temp;
tail_ptr->next = NULL;
tail_ptr->size = leftover - sizeof(mem_header);
} else {
tail_ptr->size += leftover;
}
return return_ptr;
}
void _free(void * ptr)
{
if(!ptr)
return;
mem_header * header_ptr = (mem_header *) ptr;
header_ptr--;
if(header_ptr->free)
return;
header_ptr->free = true;
/* If there is a free block in front then consume it */
if(header_ptr->next && header_ptr->next->free)
eat_next_block(header_ptr);
/* If there is a free block directly behind then jump to it and consume the block infront */
if(header_ptr->prev && header_ptr->prev->free) {
header_ptr = header_ptr->prev;
eat_next_block(header_ptr);
}
/* If there is a sufficient amount of memory at the end of the heap, return it to the kernel */
if(!header_ptr->next && header_ptr->size + sizeof(mem_header) >= PAGE_SIZE) {
size_t leftover = (header_ptr->size + sizeof(mem_header)) % PAGE_SIZE;
size_t excess = header_ptr->size + sizeof(mem_header) - leftover;
if(!header_ptr->prev) {
head_ptr = tail_ptr = NULL;
} else {
header_ptr->prev->size += leftover;
header_ptr->prev->next = NULL;
}
sbrk(-excess);
}
return;
}
static inline void eat_next_block(mem_header * header_ptr)
{
header_ptr->size += header_ptr->next->size + sizeof(mem_header);
header_ptr->next = header_ptr->next->next;
if(header_ptr->next)
header_ptr->next->prev = header_ptr;
return;
}
malloc_test.c
#include <unistd.h>
#include <stdio.h>
#include "malloc.h"
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))
int main()
{
char * mem_block[4];
char * initial_break = sbrk(0);
size_t alloc_size[4] = { 8192, 16384, 405, 32768 };
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++) {
if(!(mem_block[i] = _malloc(alloc_size[i] * sizeof(char)))) {
fprintf(stderr, "Error: Could not allocate memory!n");
return -1;
}
}
char * final_malloc_break = sbrk(0);
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++)
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
_free(mem_block[1]);
_free(mem_block[0]);
_free(mem_block[3]);
_free(mem_block[2]);
char * final_free_break = sbrk(0);
size_t total_allocated = (size_t) final_malloc_break - (size_t) initial_break;
size_t excess_pages = ((size_t) final_free_break - (size_t) initial_break) / PAGE_SIZE;
printf("ntHeap Break PositionsnnInitial break:tt%pnFinal allocation break:t%pnFinal free break:t%pnn", initial_break, final_malloc_break, final_free_break);
if(excess_pages)
printf("Error: %zu pages were not free'dn", excess_pages);
else
printf("All allocated pages free'dn");
printf("Allocated %zu bytes (%zu pages)n", total_allocated, total_allocated / PAGE_SIZE);
return 0;
}
All code was compiled with gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) and tested on Debian GNU/Linux 9.5 (stretch) with the command gcc malloc.c malloc_test.c -o malloc -Wall -Wextra -Wpedantic
Note: This code was designed to fulfill a specification for one of my classes, which included a page size of 4096 bytes and function names starting with underscores. I was unaware about the portability concerns arising from these and even though it wasn't a tag, portability is something I definitely want to know about
performance c memory-management linux portability
add a comment |
up vote
11
down vote
favorite
up vote
11
down vote
favorite
I have written an implementation of malloc()
and free()
for Linux using the sbrk()
system call.
When memory is requested, it checks if there is a large enough chunk available already, if there is then that gets returned to the user, otherwise a new block of memory will be requested from the kernel. When memory is free'd the block is marked as such and kept for later, and adjacent free blocks of memory are merged together. If there is a free block at the end of the heap that is larger than the size of a page then the largest possible multiple of page size bytes is returned to the kernel.
This is the first version of this code and my first time working with system calls, as such I have kept things fairly simple and not included padding or a realloc()
implementation. Both of these will feature in the next version along with any improvements suggested here.
malloc.h
#ifndef _MALLOC_H
#define _MALLOC_H
#include <stdbool.h>
#define PAGE_SIZE 4096
typedef struct mem_header mem_header;
struct mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
void * _malloc(size_t size);
void _free(void * ptr);
#endif
malloc.c
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include "malloc.h"
static inline void eat_next_block(mem_header * header_ptr);
mem_header * head_ptr = NULL;
mem_header * tail_ptr = NULL;
void * _malloc(size_t size)
{
if(!size)
return NULL;
bool heap_empty = false;
size_t additional_space = 0;
if(!head_ptr) {
/* Try and get the base pointer for the heap, as it is defined sbrk(0) could suprisingly fail */
if((head_ptr = tail_ptr = sbrk(0)) == (void *) -1)
return NULL;
heap_empty = true;
} else {
/* Try and find enough free space to give the user */
for(mem_header * heap_ptr = head_ptr; heap_ptr; heap_ptr = heap_ptr->next) {
if(heap_ptr->free && heap_ptr->size >= size + sizeof(mem_header)) {
/* Set up free block, if there is space for one */
if(heap_ptr->size > size + 2 * sizeof(mem_header)) {
mem_header * next_block = (mem_header *)((char *) heap_ptr + size + sizeof(mem_header));
next_block->size = heap_ptr->size - size - sizeof(mem_header);
next_block->free = true;
next_block->prev = heap_ptr;
next_block->next = heap_ptr->next;
heap_ptr->next = next_block;
} else {
size = heap_ptr->size;
}
/* Configure newly allocated block */
heap_ptr->size = size;
heap_ptr->free = false;
if((tail_ptr == heap_ptr) && heap_ptr->next)
tail_ptr = heap_ptr->next;
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
}
}
/* If we have a free block at the end that isn't large enough we can subtract its size from our allocation requirement */
if(tail_ptr->free)
additional_space = tail_ptr->size + sizeof(mem_header);
}
/* Determine how much we need to grow the heap by, alligned to a multiple of PAGE_SIZE bytes */
size_t block_size = size + sizeof(mem_header) - additional_space;
if(block_size % PAGE_SIZE != 0)
block_size += PAGE_SIZE - (block_size % PAGE_SIZE);
/* Grow the heap */
if(sbrk(block_size) == (void *) -1)
return NULL;
/* Configure the memory block to be returned */
if(heap_empty) {
tail_ptr->prev = NULL;
} else if(!tail_ptr->free) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + tail_ptr->size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->prev = tail_ptr_temp;
}
tail_ptr->next = NULL;
tail_ptr->free = false;
tail_ptr->size = size;
/* Configure any free space at the top of the heap */
void * return_ptr = (void *)((char *) tail_ptr + sizeof(mem_header));
size_t leftover = block_size + additional_space - (size + sizeof(mem_header));
if(leftover > sizeof(mem_header)) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->free = true;
tail_ptr->prev = tail_ptr_temp;
tail_ptr->next = NULL;
tail_ptr->size = leftover - sizeof(mem_header);
} else {
tail_ptr->size += leftover;
}
return return_ptr;
}
void _free(void * ptr)
{
if(!ptr)
return;
mem_header * header_ptr = (mem_header *) ptr;
header_ptr--;
if(header_ptr->free)
return;
header_ptr->free = true;
/* If there is a free block in front then consume it */
if(header_ptr->next && header_ptr->next->free)
eat_next_block(header_ptr);
/* If there is a free block directly behind then jump to it and consume the block infront */
if(header_ptr->prev && header_ptr->prev->free) {
header_ptr = header_ptr->prev;
eat_next_block(header_ptr);
}
/* If there is a sufficient amount of memory at the end of the heap, return it to the kernel */
if(!header_ptr->next && header_ptr->size + sizeof(mem_header) >= PAGE_SIZE) {
size_t leftover = (header_ptr->size + sizeof(mem_header)) % PAGE_SIZE;
size_t excess = header_ptr->size + sizeof(mem_header) - leftover;
if(!header_ptr->prev) {
head_ptr = tail_ptr = NULL;
} else {
header_ptr->prev->size += leftover;
header_ptr->prev->next = NULL;
}
sbrk(-excess);
}
return;
}
static inline void eat_next_block(mem_header * header_ptr)
{
header_ptr->size += header_ptr->next->size + sizeof(mem_header);
header_ptr->next = header_ptr->next->next;
if(header_ptr->next)
header_ptr->next->prev = header_ptr;
return;
}
malloc_test.c
#include <unistd.h>
#include <stdio.h>
#include "malloc.h"
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))
int main()
{
char * mem_block[4];
char * initial_break = sbrk(0);
size_t alloc_size[4] = { 8192, 16384, 405, 32768 };
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++) {
if(!(mem_block[i] = _malloc(alloc_size[i] * sizeof(char)))) {
fprintf(stderr, "Error: Could not allocate memory!n");
return -1;
}
}
char * final_malloc_break = sbrk(0);
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++)
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
_free(mem_block[1]);
_free(mem_block[0]);
_free(mem_block[3]);
_free(mem_block[2]);
char * final_free_break = sbrk(0);
size_t total_allocated = (size_t) final_malloc_break - (size_t) initial_break;
size_t excess_pages = ((size_t) final_free_break - (size_t) initial_break) / PAGE_SIZE;
printf("ntHeap Break PositionsnnInitial break:tt%pnFinal allocation break:t%pnFinal free break:t%pnn", initial_break, final_malloc_break, final_free_break);
if(excess_pages)
printf("Error: %zu pages were not free'dn", excess_pages);
else
printf("All allocated pages free'dn");
printf("Allocated %zu bytes (%zu pages)n", total_allocated, total_allocated / PAGE_SIZE);
return 0;
}
All code was compiled with gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) and tested on Debian GNU/Linux 9.5 (stretch) with the command gcc malloc.c malloc_test.c -o malloc -Wall -Wextra -Wpedantic
Note: This code was designed to fulfill a specification for one of my classes, which included a page size of 4096 bytes and function names starting with underscores. I was unaware about the portability concerns arising from these and even though it wasn't a tag, portability is something I definitely want to know about
performance c memory-management linux portability
I have written an implementation of malloc()
and free()
for Linux using the sbrk()
system call.
When memory is requested, it checks if there is a large enough chunk available already, if there is then that gets returned to the user, otherwise a new block of memory will be requested from the kernel. When memory is free'd the block is marked as such and kept for later, and adjacent free blocks of memory are merged together. If there is a free block at the end of the heap that is larger than the size of a page then the largest possible multiple of page size bytes is returned to the kernel.
This is the first version of this code and my first time working with system calls, as such I have kept things fairly simple and not included padding or a realloc()
implementation. Both of these will feature in the next version along with any improvements suggested here.
malloc.h
#ifndef _MALLOC_H
#define _MALLOC_H
#include <stdbool.h>
#define PAGE_SIZE 4096
typedef struct mem_header mem_header;
struct mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
void * _malloc(size_t size);
void _free(void * ptr);
#endif
malloc.c
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include "malloc.h"
static inline void eat_next_block(mem_header * header_ptr);
mem_header * head_ptr = NULL;
mem_header * tail_ptr = NULL;
void * _malloc(size_t size)
{
if(!size)
return NULL;
bool heap_empty = false;
size_t additional_space = 0;
if(!head_ptr) {
/* Try and get the base pointer for the heap, as it is defined sbrk(0) could suprisingly fail */
if((head_ptr = tail_ptr = sbrk(0)) == (void *) -1)
return NULL;
heap_empty = true;
} else {
/* Try and find enough free space to give the user */
for(mem_header * heap_ptr = head_ptr; heap_ptr; heap_ptr = heap_ptr->next) {
if(heap_ptr->free && heap_ptr->size >= size + sizeof(mem_header)) {
/* Set up free block, if there is space for one */
if(heap_ptr->size > size + 2 * sizeof(mem_header)) {
mem_header * next_block = (mem_header *)((char *) heap_ptr + size + sizeof(mem_header));
next_block->size = heap_ptr->size - size - sizeof(mem_header);
next_block->free = true;
next_block->prev = heap_ptr;
next_block->next = heap_ptr->next;
heap_ptr->next = next_block;
} else {
size = heap_ptr->size;
}
/* Configure newly allocated block */
heap_ptr->size = size;
heap_ptr->free = false;
if((tail_ptr == heap_ptr) && heap_ptr->next)
tail_ptr = heap_ptr->next;
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
}
}
/* If we have a free block at the end that isn't large enough we can subtract its size from our allocation requirement */
if(tail_ptr->free)
additional_space = tail_ptr->size + sizeof(mem_header);
}
/* Determine how much we need to grow the heap by, alligned to a multiple of PAGE_SIZE bytes */
size_t block_size = size + sizeof(mem_header) - additional_space;
if(block_size % PAGE_SIZE != 0)
block_size += PAGE_SIZE - (block_size % PAGE_SIZE);
/* Grow the heap */
if(sbrk(block_size) == (void *) -1)
return NULL;
/* Configure the memory block to be returned */
if(heap_empty) {
tail_ptr->prev = NULL;
} else if(!tail_ptr->free) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + tail_ptr->size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->prev = tail_ptr_temp;
}
tail_ptr->next = NULL;
tail_ptr->free = false;
tail_ptr->size = size;
/* Configure any free space at the top of the heap */
void * return_ptr = (void *)((char *) tail_ptr + sizeof(mem_header));
size_t leftover = block_size + additional_space - (size + sizeof(mem_header));
if(leftover > sizeof(mem_header)) {
mem_header * tail_ptr_temp = tail_ptr;
tail_ptr->next = (mem_header *)((char *) tail_ptr + size + sizeof(mem_header));
tail_ptr = tail_ptr->next;
tail_ptr->free = true;
tail_ptr->prev = tail_ptr_temp;
tail_ptr->next = NULL;
tail_ptr->size = leftover - sizeof(mem_header);
} else {
tail_ptr->size += leftover;
}
return return_ptr;
}
void _free(void * ptr)
{
if(!ptr)
return;
mem_header * header_ptr = (mem_header *) ptr;
header_ptr--;
if(header_ptr->free)
return;
header_ptr->free = true;
/* If there is a free block in front then consume it */
if(header_ptr->next && header_ptr->next->free)
eat_next_block(header_ptr);
/* If there is a free block directly behind then jump to it and consume the block infront */
if(header_ptr->prev && header_ptr->prev->free) {
header_ptr = header_ptr->prev;
eat_next_block(header_ptr);
}
/* If there is a sufficient amount of memory at the end of the heap, return it to the kernel */
if(!header_ptr->next && header_ptr->size + sizeof(mem_header) >= PAGE_SIZE) {
size_t leftover = (header_ptr->size + sizeof(mem_header)) % PAGE_SIZE;
size_t excess = header_ptr->size + sizeof(mem_header) - leftover;
if(!header_ptr->prev) {
head_ptr = tail_ptr = NULL;
} else {
header_ptr->prev->size += leftover;
header_ptr->prev->next = NULL;
}
sbrk(-excess);
}
return;
}
static inline void eat_next_block(mem_header * header_ptr)
{
header_ptr->size += header_ptr->next->size + sizeof(mem_header);
header_ptr->next = header_ptr->next->next;
if(header_ptr->next)
header_ptr->next->prev = header_ptr;
return;
}
malloc_test.c
#include <unistd.h>
#include <stdio.h>
#include "malloc.h"
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))
int main()
{
char * mem_block[4];
char * initial_break = sbrk(0);
size_t alloc_size[4] = { 8192, 16384, 405, 32768 };
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++) {
if(!(mem_block[i] = _malloc(alloc_size[i] * sizeof(char)))) {
fprintf(stderr, "Error: Could not allocate memory!n");
return -1;
}
}
char * final_malloc_break = sbrk(0);
for(size_t i = 0; i < ARRAY_SIZE(mem_block); i++)
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
_free(mem_block[1]);
_free(mem_block[0]);
_free(mem_block[3]);
_free(mem_block[2]);
char * final_free_break = sbrk(0);
size_t total_allocated = (size_t) final_malloc_break - (size_t) initial_break;
size_t excess_pages = ((size_t) final_free_break - (size_t) initial_break) / PAGE_SIZE;
printf("ntHeap Break PositionsnnInitial break:tt%pnFinal allocation break:t%pnFinal free break:t%pnn", initial_break, final_malloc_break, final_free_break);
if(excess_pages)
printf("Error: %zu pages were not free'dn", excess_pages);
else
printf("All allocated pages free'dn");
printf("Allocated %zu bytes (%zu pages)n", total_allocated, total_allocated / PAGE_SIZE);
return 0;
}
All code was compiled with gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1) and tested on Debian GNU/Linux 9.5 (stretch) with the command gcc malloc.c malloc_test.c -o malloc -Wall -Wextra -Wpedantic
Note: This code was designed to fulfill a specification for one of my classes, which included a page size of 4096 bytes and function names starting with underscores. I was unaware about the portability concerns arising from these and even though it wasn't a tag, portability is something I definitely want to know about
performance c memory-management linux portability
performance c memory-management linux portability
edited Nov 6 at 19:25
asked Nov 5 at 15:18
psychedelic_alex
507419
507419
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
15
down vote
Names beginning with _
are reserved for the implementation; I'm surprised that -Wpedantic
doesn't help with this!
Include what you use - it helps if your implementation and test program include malloc.h
before any standard headers. In this case, it's depending on <stddef.h>
(or one of the other headers which define size_t
).
With -Wconversion
, I get a couple of warnings:
206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
if(sbrk(block_size) == (void *) -1)
^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
sbrk(-excess);
^~~~~~~
The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:
sbrk(-(intptr_t)excess);
#define PAGE_SIZE 4096
Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:
#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif
I don't see any attention to alignment - you do need to ensure that the result of malloc()
is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.
The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.
There's no need for the (void*)
cast here:
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
Since all pointers convert implicitly to void*
, that becomes simply
/* Add enough bytes for a header */
return (char*)heap_ptr + sizeof (mem_header);
You might even get away with
/* Advance pointer beyond the header before passing to user */
return heap_ptr + 1;
Similarly,
void * return_ptr = tail_ptr + 1;
In the case where we called sbrk()
to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc()
(which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.
It may be necessary to call eat_next_block
to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.
Some minor bits in the test program:
sizeof (char)
is always 1, since results are in units ofchar
. So multiplying by that is pointless.- We can use
ptrdiff_t
for the result of pointer subtraction, instead of casting tosize_t
first (whereintptr_t
would be safer).
This is a convoluted way to write
memset(mem_block[i], 'a', alloc_size[i])
:
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
(But thank you for sharing the test program - it really makes reviewing easier).
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
I generally use-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).
– Toby Speight
Nov 5 at 18:15
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration ofsize_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.
– Toby Speight
Nov 5 at 18:18
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that<unistd.h>
or<limits.h>
might definePAGESIZE
for you, though. (Usingsysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the% PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, withpagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.
– Peter Cordes
Nov 6 at 1:49
2
re: alignment: the requiredmalloc
alignment isalignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?
– Peter Cordes
Nov 6 at 1:53
|
show 4 more comments
up vote
1
down vote
size + sizeof(mem_header)
assumes correct alignment
Memory management functions
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1
The returned pointer from _malloc()
needs to meet the fundamental alignment requirement and it is not known the struct mem_header
meets that. So possibly sizeof(mem_header) + something_more + size
is needed. Then (char *) heap_ptr + sizeof(mem_header)
will work per the C spec. @Peter Cordes
With C11, this is easy with _Alignas
and max_align_t
to insure struct mem_header
is aligned well.
An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the
_Alignas
keyword. §6.2.8 1
struct _Alignas(max_align_t) mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
A pre-C11 approach. Align for the widest base types. The may cause super alignment.
union my_wide_union {
int (*foo)();
void *v;
double d;
long l;
// for C99
long double ld;
uintmax_t um;
long double _Complex z; // for select C99 or later
};
union mem_header {
union my_wide_union dummy;
struct {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
}
};
Another alignment issue
The size
requested also needs to be a multiple of sizeof(max_align_t)
. Recommend
size_t padding = size % sizeof(max_align_t);
if (padding) size += sizeof(max_align_t) - padding;
Prevent overflow
//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
return NULL;
}
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
15
down vote
Names beginning with _
are reserved for the implementation; I'm surprised that -Wpedantic
doesn't help with this!
Include what you use - it helps if your implementation and test program include malloc.h
before any standard headers. In this case, it's depending on <stddef.h>
(or one of the other headers which define size_t
).
With -Wconversion
, I get a couple of warnings:
206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
if(sbrk(block_size) == (void *) -1)
^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
sbrk(-excess);
^~~~~~~
The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:
sbrk(-(intptr_t)excess);
#define PAGE_SIZE 4096
Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:
#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif
I don't see any attention to alignment - you do need to ensure that the result of malloc()
is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.
The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.
There's no need for the (void*)
cast here:
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
Since all pointers convert implicitly to void*
, that becomes simply
/* Add enough bytes for a header */
return (char*)heap_ptr + sizeof (mem_header);
You might even get away with
/* Advance pointer beyond the header before passing to user */
return heap_ptr + 1;
Similarly,
void * return_ptr = tail_ptr + 1;
In the case where we called sbrk()
to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc()
(which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.
It may be necessary to call eat_next_block
to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.
Some minor bits in the test program:
sizeof (char)
is always 1, since results are in units ofchar
. So multiplying by that is pointless.- We can use
ptrdiff_t
for the result of pointer subtraction, instead of casting tosize_t
first (whereintptr_t
would be safer).
This is a convoluted way to write
memset(mem_block[i], 'a', alloc_size[i])
:
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
(But thank you for sharing the test program - it really makes reviewing easier).
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
I generally use-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).
– Toby Speight
Nov 5 at 18:15
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration ofsize_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.
– Toby Speight
Nov 5 at 18:18
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that<unistd.h>
or<limits.h>
might definePAGESIZE
for you, though. (Usingsysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the% PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, withpagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.
– Peter Cordes
Nov 6 at 1:49
2
re: alignment: the requiredmalloc
alignment isalignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?
– Peter Cordes
Nov 6 at 1:53
|
show 4 more comments
up vote
15
down vote
Names beginning with _
are reserved for the implementation; I'm surprised that -Wpedantic
doesn't help with this!
Include what you use - it helps if your implementation and test program include malloc.h
before any standard headers. In this case, it's depending on <stddef.h>
(or one of the other headers which define size_t
).
With -Wconversion
, I get a couple of warnings:
206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
if(sbrk(block_size) == (void *) -1)
^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
sbrk(-excess);
^~~~~~~
The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:
sbrk(-(intptr_t)excess);
#define PAGE_SIZE 4096
Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:
#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif
I don't see any attention to alignment - you do need to ensure that the result of malloc()
is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.
The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.
There's no need for the (void*)
cast here:
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
Since all pointers convert implicitly to void*
, that becomes simply
/* Add enough bytes for a header */
return (char*)heap_ptr + sizeof (mem_header);
You might even get away with
/* Advance pointer beyond the header before passing to user */
return heap_ptr + 1;
Similarly,
void * return_ptr = tail_ptr + 1;
In the case where we called sbrk()
to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc()
(which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.
It may be necessary to call eat_next_block
to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.
Some minor bits in the test program:
sizeof (char)
is always 1, since results are in units ofchar
. So multiplying by that is pointless.- We can use
ptrdiff_t
for the result of pointer subtraction, instead of casting tosize_t
first (whereintptr_t
would be safer).
This is a convoluted way to write
memset(mem_block[i], 'a', alloc_size[i])
:
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
(But thank you for sharing the test program - it really makes reviewing easier).
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
I generally use-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).
– Toby Speight
Nov 5 at 18:15
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration ofsize_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.
– Toby Speight
Nov 5 at 18:18
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that<unistd.h>
or<limits.h>
might definePAGESIZE
for you, though. (Usingsysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the% PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, withpagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.
– Peter Cordes
Nov 6 at 1:49
2
re: alignment: the requiredmalloc
alignment isalignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?
– Peter Cordes
Nov 6 at 1:53
|
show 4 more comments
up vote
15
down vote
up vote
15
down vote
Names beginning with _
are reserved for the implementation; I'm surprised that -Wpedantic
doesn't help with this!
Include what you use - it helps if your implementation and test program include malloc.h
before any standard headers. In this case, it's depending on <stddef.h>
(or one of the other headers which define size_t
).
With -Wconversion
, I get a couple of warnings:
206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
if(sbrk(block_size) == (void *) -1)
^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
sbrk(-excess);
^~~~~~~
The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:
sbrk(-(intptr_t)excess);
#define PAGE_SIZE 4096
Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:
#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif
I don't see any attention to alignment - you do need to ensure that the result of malloc()
is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.
The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.
There's no need for the (void*)
cast here:
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
Since all pointers convert implicitly to void*
, that becomes simply
/* Add enough bytes for a header */
return (char*)heap_ptr + sizeof (mem_header);
You might even get away with
/* Advance pointer beyond the header before passing to user */
return heap_ptr + 1;
Similarly,
void * return_ptr = tail_ptr + 1;
In the case where we called sbrk()
to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc()
(which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.
It may be necessary to call eat_next_block
to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.
Some minor bits in the test program:
sizeof (char)
is always 1, since results are in units ofchar
. So multiplying by that is pointless.- We can use
ptrdiff_t
for the result of pointer subtraction, instead of casting tosize_t
first (whereintptr_t
would be safer).
This is a convoluted way to write
memset(mem_block[i], 'a', alloc_size[i])
:
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
(But thank you for sharing the test program - it really makes reviewing easier).
Names beginning with _
are reserved for the implementation; I'm surprised that -Wpedantic
doesn't help with this!
Include what you use - it helps if your implementation and test program include malloc.h
before any standard headers. In this case, it's depending on <stddef.h>
(or one of the other headers which define size_t
).
With -Wconversion
, I get a couple of warnings:
206988.c:92:13: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
if(sbrk(block_size) == (void *) -1)
^~~~~~~~~~
206988.c: In function ‘_free’:
206988.c:169:14: warning: conversion to ‘intptr_t’ {aka ‘long int’} from ‘size_t’ {aka ‘long unsigned int’} may change the sign of the result [-Wsign-conversion]
sbrk(-excess);
^~~~~~~
The first warrants an explicit cast to draw attention. The second of these could be an error; we want to cast before negating:
sbrk(-(intptr_t)excess);
#define PAGE_SIZE 4096
Although that's a common page size, this assumption does make your code less portable. You might be able to find it available in system headers (I can't remember where, if so); it certainly makes sense to guard it so it can be overridden from the compile command:
#ifndef PAGE_SIZE
#define PAGE_SIZE 4096
#endif
I don't see any attention to alignment - you do need to ensure that the result of malloc()
is suitably aligned for all types. You might be testing on a platform that compensates for unaligned access with just a performance drop - on other systems, you might get a bus error or simply unexpected results.
The linear search is going to be very inefficient after a few allocations. Real implementations have several lists, holding different size blocks.
There's no need for the (void*)
cast here:
/* Cast heap_ptr as char * since we're doing byte level arithmetic, then convert to void * before returning */
return (void *)((char *) heap_ptr + sizeof(mem_header));
Since all pointers convert implicitly to void*
, that becomes simply
/* Add enough bytes for a header */
return (char*)heap_ptr + sizeof (mem_header);
You might even get away with
/* Advance pointer beyond the header before passing to user */
return heap_ptr + 1;
Similarly,
void * return_ptr = tail_ptr + 1;
In the case where we called sbrk()
to create more memory, it might make sense to simply add the new memory to the start of free list and immediately re-enter malloc()
(which of course will now be able to satisfy the request). That way, there's a single path for successful allocations, which might be handy if you want to "colour" the memory according to its status, for debugging.
It may be necessary to call eat_next_block
to join a final free block with newly-created address space; I couldn't quite see how this is done at present, and the test code doesn't exercise that path.
Some minor bits in the test program:
sizeof (char)
is always 1, since results are in units ofchar
. So multiplying by that is pointless.- We can use
ptrdiff_t
for the result of pointer subtraction, instead of casting tosize_t
first (whereintptr_t
would be safer).
This is a convoluted way to write
memset(mem_block[i], 'a', alloc_size[i])
:
for(size_t j = 0; j < alloc_size[i]; j++)
mem_block[i][j] = 'a';
(But thank you for sharing the test program - it really makes reviewing easier).
answered Nov 5 at 17:58
Toby Speight
21.7k536107
21.7k536107
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
I generally use-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).
– Toby Speight
Nov 5 at 18:15
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration ofsize_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.
– Toby Speight
Nov 5 at 18:18
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that<unistd.h>
or<limits.h>
might definePAGESIZE
for you, though. (Usingsysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the% PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, withpagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.
– Peter Cordes
Nov 6 at 1:49
2
re: alignment: the requiredmalloc
alignment isalignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?
– Peter Cordes
Nov 6 at 1:53
|
show 4 more comments
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
I generally use-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).
– Toby Speight
Nov 5 at 18:15
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration ofsize_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.
– Toby Speight
Nov 5 at 18:18
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that<unistd.h>
or<limits.h>
might definePAGESIZE
for you, though. (Usingsysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the% PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, withpagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.
– Peter Cordes
Nov 6 at 1:49
2
re: alignment: the requiredmalloc
alignment isalignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?
– Peter Cordes
Nov 6 at 1:53
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
Thanks you for your reply! I had no idea that -Wextra and -Wpedantic wouldn't catch every possible warning, what other flags would I need for a comprehensive warning list??
– psychedelic_alex
Nov 5 at 18:07
4
4
I generally use
-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).– Toby Speight
Nov 5 at 18:15
I generally use
-Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion
(in my default CR Makefile).– Toby Speight
Nov 5 at 18:15
6
6
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration of
size_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.– Toby Speight
Nov 5 at 18:18
I (as a user) expect to be able to include your header anywhere without error. If I include it before I've included any standard headers, I can't compile (because there's no declaration of
size_t
in scope). By including your own headers first in your implementation (and test code), you get to spot that problem before your users do.– Toby Speight
Nov 5 at 18:18
1
1
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that
<unistd.h>
or <limits.h>
might define PAGESIZE
for you, though. (Using sysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the % PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, with pagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.– Peter Cordes
Nov 6 at 1:49
+1 for still recommending a compile-time-constant for page size. man7.org/linux/man-pages/man3/sysconf.3.html says that
<unistd.h>
or <limits.h>
might define PAGESIZE
for you, though. (Using sysconf(_SC_PAGESIZE)
sucks, though: the compiler won't know it's a power of 2. You don't want the % PAGE_SIZE
to compile to actual hardware division, instead of an AND. You could assume it's a power of 2 and create a mask, though, with pagesize-1
.) I might write this up as an answer, but for now I'll just comment here for @psychedelic_alex to see.– Peter Cordes
Nov 6 at 1:49
2
2
re: alignment: the required
malloc
alignment is alignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?– Peter Cordes
Nov 6 at 1:53
re: alignment: the required
malloc
alignment is alignof(maxalign_t)
. (Or for smaller allocations, less alignment is required: ISO C requires that malloced memory can be used to hold any standard type that fits in it.) Also, fun fact: misaligned memory can cause faults even on x86 when gcc auto-vectorizes and assumes that some number of elements will reach an alignment boundary: Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?– Peter Cordes
Nov 6 at 1:53
|
show 4 more comments
up vote
1
down vote
size + sizeof(mem_header)
assumes correct alignment
Memory management functions
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1
The returned pointer from _malloc()
needs to meet the fundamental alignment requirement and it is not known the struct mem_header
meets that. So possibly sizeof(mem_header) + something_more + size
is needed. Then (char *) heap_ptr + sizeof(mem_header)
will work per the C spec. @Peter Cordes
With C11, this is easy with _Alignas
and max_align_t
to insure struct mem_header
is aligned well.
An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the
_Alignas
keyword. §6.2.8 1
struct _Alignas(max_align_t) mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
A pre-C11 approach. Align for the widest base types. The may cause super alignment.
union my_wide_union {
int (*foo)();
void *v;
double d;
long l;
// for C99
long double ld;
uintmax_t um;
long double _Complex z; // for select C99 or later
};
union mem_header {
union my_wide_union dummy;
struct {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
}
};
Another alignment issue
The size
requested also needs to be a multiple of sizeof(max_align_t)
. Recommend
size_t padding = size % sizeof(max_align_t);
if (padding) size += sizeof(max_align_t) - padding;
Prevent overflow
//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
return NULL;
}
add a comment |
up vote
1
down vote
size + sizeof(mem_header)
assumes correct alignment
Memory management functions
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1
The returned pointer from _malloc()
needs to meet the fundamental alignment requirement and it is not known the struct mem_header
meets that. So possibly sizeof(mem_header) + something_more + size
is needed. Then (char *) heap_ptr + sizeof(mem_header)
will work per the C spec. @Peter Cordes
With C11, this is easy with _Alignas
and max_align_t
to insure struct mem_header
is aligned well.
An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the
_Alignas
keyword. §6.2.8 1
struct _Alignas(max_align_t) mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
A pre-C11 approach. Align for the widest base types. The may cause super alignment.
union my_wide_union {
int (*foo)();
void *v;
double d;
long l;
// for C99
long double ld;
uintmax_t um;
long double _Complex z; // for select C99 or later
};
union mem_header {
union my_wide_union dummy;
struct {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
}
};
Another alignment issue
The size
requested also needs to be a multiple of sizeof(max_align_t)
. Recommend
size_t padding = size % sizeof(max_align_t);
if (padding) size += sizeof(max_align_t) - padding;
Prevent overflow
//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
return NULL;
}
add a comment |
up vote
1
down vote
up vote
1
down vote
size + sizeof(mem_header)
assumes correct alignment
Memory management functions
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1
The returned pointer from _malloc()
needs to meet the fundamental alignment requirement and it is not known the struct mem_header
meets that. So possibly sizeof(mem_header) + something_more + size
is needed. Then (char *) heap_ptr + sizeof(mem_header)
will work per the C spec. @Peter Cordes
With C11, this is easy with _Alignas
and max_align_t
to insure struct mem_header
is aligned well.
An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the
_Alignas
keyword. §6.2.8 1
struct _Alignas(max_align_t) mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
A pre-C11 approach. Align for the widest base types. The may cause super alignment.
union my_wide_union {
int (*foo)();
void *v;
double d;
long l;
// for C99
long double ld;
uintmax_t um;
long double _Complex z; // for select C99 or later
};
union mem_header {
union my_wide_union dummy;
struct {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
}
};
Another alignment issue
The size
requested also needs to be a multiple of sizeof(max_align_t)
. Recommend
size_t padding = size % sizeof(max_align_t);
if (padding) size += sizeof(max_align_t) - padding;
Prevent overflow
//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
return NULL;
}
size + sizeof(mem_header)
assumes correct alignment
Memory management functions
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement C11 §7.22.3 1
The returned pointer from _malloc()
needs to meet the fundamental alignment requirement and it is not known the struct mem_header
meets that. So possibly sizeof(mem_header) + something_more + size
is needed. Then (char *) heap_ptr + sizeof(mem_header)
will work per the C spec. @Peter Cordes
With C11, this is easy with _Alignas
and max_align_t
to insure struct mem_header
is aligned well.
An object type imposes an alignment requirement on every object of that type: stricter alignment can be requested using the
_Alignas
keyword. §6.2.8 1
struct _Alignas(max_align_t) mem_header {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
};
A pre-C11 approach. Align for the widest base types. The may cause super alignment.
union my_wide_union {
int (*foo)();
void *v;
double d;
long l;
// for C99
long double ld;
uintmax_t um;
long double _Complex z; // for select C99 or later
};
union mem_header {
union my_wide_union dummy;
struct {
size_t size;
bool free;
mem_header * prev;
mem_header * next;
}
};
Another alignment issue
The size
requested also needs to be a multiple of sizeof(max_align_t)
. Recommend
size_t padding = size % sizeof(max_align_t);
if (padding) size += sizeof(max_align_t) - padding;
Prevent overflow
//if(!size)
if(size == 0 || size > SIZE_MAX - sizeof(struct mem_header)) {
return NULL;
}
edited Nov 7 at 0:05
answered Nov 6 at 22:59
chux
12.2k11342
12.2k11342
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206988%2fmalloc-and-free-for-linux-with-system-calls%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password