Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

malloc implementation?

I'm trying to implement malloc and free for C, and I am not sure how to reuse memory. I currently have a struct that looks like this:

typedef struct _mem_dictionary {     void *addr;     size_t size;     int freed; } mem_dictionary; 

My malloc looks like this:

void *malloc(size_t size) {     void *return_ptr = sbrk(size);     if (dictionary == NULL)          dictionary = sbrk(1024 * sizeof(mem_dictionary));      dictionary[dictionary_ct].addr = return_ptr;     dictionary[dictionary_ct].size = size;     dictionary[dictionary_ct].freed = 1;     dictionary_ct++;      return return_ptr; } 

When I free memory, I would just mark the address as 0 (that would indicate that it is free). In my malloc, I would then use a for loop to look for any value in the array to equal 0 and then allocate memory to that address. I'm kind of confused how to implement this.

like image 277
user675257 Avatar asked Mar 24 '11 16:03

user675257


People also ask

How do you implement malloc function?

The easiest way to do it is to keep a linked list of free block. In malloc , if the list is not empty, you search for a block large enough to satisfy the request and return it. If the list is empty or if no such block can be found, you call sbrk to allocate some memory from the operating system.

How malloc is implemented internally?

When one calls malloc , memory is taken from the large heap cell, which is returned by malloc . The rest is formed into a new heap cell that consists of all the rest of the memory. When one frees memory, the heap cell is added to the end of the heap's free list.

What algorithm does malloc use?

Malloc Algorithm In a nutshell, malloc works like this: If there is a suitable (exact match only) chunk in the tcache, it is returned to the caller. No attempt is made to use an available chunk from a larger-sized bin. If the request is large enough, mmap() is used to request memory directly from the operating system.

What is the function of malloc ()?

The malloc() function stands for memory allocation, that allocate a block of memory dynamically. It reserves the memory space for a specified size and returns the null pointer, which points to the memory location.


1 Answers

The easiest way to do it is to keep a linked list of free block. In malloc, if the list is not empty, you search for a block large enough to satisfy the request and return it. If the list is empty or if no such block can be found, you call sbrk to allocate some memory from the operating system. in free, you simply add the memory chunk to the list of free block. As bonus, you can try to merge contiguous freed block, and you can change the policy for choosing the block to return (first fit, best fit, ...). You can also choose to split the block if it is larger than the request.

Some sample implementation (it is not tested, and is obviously not thread-safe, use at your own risk):

typedef struct free_block {     size_t size;     struct free_block* next; } free_block;  static free_block free_block_list_head = { 0, 0 }; static const size_t overhead = sizeof(size_t); static const size_t align_to = 16;  void* malloc(size_t size) {     size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);     free_block* block = free_block_list_head.next;     free_block** head = &(free_block_list_head.next);     while (block != 0) {         if (block->size >= size) {             *head = block->next;             return ((char*)block) + sizeof(size_t);         }         head = &(block->next);         block = block->next;     }      block = (free_block*)sbrk(size);     block->size = size;      return ((char*)block) + sizeof(size_t); }  void free(void* ptr) {     free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));     block->next = free_block_list_head.next;     free_block_list_head.next = block; } 

Note: (n + align_to - 1) & ~ (align_to - 1) is a trick to round n to the nearest multiple of align_to that is larger than n. This only works when align_to is a power of two and depends on the binary representation of numbers.

When align_to is a power of two, it only has one bit set, and thus align_to - 1 has all the lowest bit sets (ie. align_to is of the form 000...010...0, and align_to - 1 is of the form 000...001...1). This means that ~ (align_to - 1) has all the high bit set, and the low bit unset (ie. it is of the form 111...110...0). So x & ~ (align_to - 1) will set to zero all the low bits of x and round it down to the nearest multiple of align_to.

Finally, adding align_to - 1 to size ensure that we round-up to the nearest multiple of align_to (unless size is already a multiple of align_to in which case we want to get size).

like image 75
Sylvain Defresne Avatar answered Sep 17 '22 03:09

Sylvain Defresne