memory allocator - Hiroshi123/bin_tools GitHub Wiki

Memory allocator

brief architecture

malloc is implemented on top of memory map.

The reason is

  1. Acquire always contigious memory.
  2. Initialize always as 0.

Memory will be acquired per page unit. When you allocate a page for a memory to store something, corresponding meta information is put on another page. This is called Bin.

One Bin is capable of managing one page.

The struct is below.

struct _Bin {
  uint32_t bin[8];
  Bin* next;
  size_t page_addr;
};

Think about uint32_t as bit array which holds 32bit. 1Page(0x1000byte) can be represented as 32 * 8 = 256bit, that is why Bin holds an array of 32bit which holds 8 elements.

32bit as uint32_t indicates row.
8 indicates column on below matrix.

-----bitmap-----:8d3c0000(8d3bf000-8d3bffff)
0b11111111111111111111111111111111
0b11111111111111111111111111111111
0b11111111111111111111111111111111
0b11111111111111111111111111111111
0b11111111111111111111111111111111
0b11111111111111111111111111111111
0b00000000000000000000011111111111
0b00000000000000000000000000000000

If some elements on a page is freed, the bit which corresponds to element of the bin will be set off. Next time, when you allocate something, it always checks if Bin holds consecutive non-set elements on its bit array. If it exceeds than the required size, it will lend you the range.

Consideration about size of chunk

One question is when you free, how does the bin knows the end of the original allocated data? Obviously, free does not provide data size provided by malloc data. To keep the length record, Bin will store the length of data just before the given memory.

For instance, if you allocate with malloc, and step back 1byte, you will know the byte that you have allocated.

uint8_t* mem01 = malloc(2);
uint8_t length = *(mem01 - 1); # should be 2.

Of course, you must keep it in your memory so as not to overwrite the memory which puts the length. As long as you exceed the provided range of malloc, it will not give you the memory. If you violate the rule, it will get in the way of what free does.

From the perspective of memory allocation, it requires to allocate 1 extra byte prior to actual allocation. And, you should always return the address which are aligned at least 0x8 or ideally 0x10 byte. 1byte is enough to store the length of malloc as it always less than number of elements of bins array, 256 (0x1000 / 0x10).
But, considering the alignment of return address, you need to fill padding in between last allocation and length of next allocation.
Besides, first chunk on a page should not start from beginning of page as it must hold the length of chunk just 1 byte before the allocation.
If you allocate empty 0x10 bytes before mapping, and make use of last byte as length of first chunk, it seems to be ok. Downside here is when you allocate maximum allocation on a page, e.g. 0x1000 - 1, you cannot allocate 0x10 byte as padding and length. In this case, this is almost applied as the same situation where allocation surpasses page size as every element of bins array belongs to same chunk. If you decide the rule that if returned address from malloc is page aligned, the free of the address will free every bins on the page no matter what.

Consideration about contigurency

If you allocate any chunk in a page, and another page over the last leftover but less than a page, the leftover is kept untouched, and the overall next is on new page.


uint8_t* a = malloc(0xf00);
# returned address should start from 0x10 bytes after page alignment.
printf("returned address : %p\n", a); 

uint8_t* b = malloc(0xf00);
# returned address should start from 0x10 bytes after page alignment.
# note there is still some unused leftover chunks on previous page.
printf("returned address : %p\n", b); 

uint8_t* c = malloc(0x10);
# returned address should start from either on a previously allocated page.
# This is because required length of chunk can be allocated on leftover.
printf("returned address : %p\n", c);

If you allocate more than 1 page. It ignores semi-allocated any pages, instead allocate with mmap. These map will be connected of the bin's chain by its next field and its leftover might be used later on.