Updates bytes
to take care of alignments, etc.
Checks if av
is NULL or not.
In the case of absence of usable arena (when av
is NULL), calls sysmalloc
to obtain chunk using mmap. If successful, calls alloc_perturb
. Returns the pointer.
If size falls in the fastbin range: 1. Get index into the fastbin array to access an appropriate bin according to the request size. 2. Removes the first chunk in that bin and make victim
point to it. 3. If victim
is NULL, move on to the next case (smallbin). 4. If victim
is not NULL, check the size of the chunk to ensure that it belongs to that particular bin. An error ("malloc(): memory corruption (fast)") is thrown otherwise. 5. Calls alloc_perturb
and then returns the pointer.
If size falls in the smallbin range: 1. Get index into the smallbin array to access an appropriate bin according to the request size. 2. If there are no chunks in this bin, move on to the next case. This is checked by comparing the pointers bin
and bin->bk
. 3. victim
is made equal to bin->bk
(the last chunk in the bin). If it is NULL (happens during initialization
), call malloc_consolidate
and skip this complete step of checking into different bins. 4. Otherwise, when victim
is non NULL, check if victim->bk->fd
and victim
are equal or not. If they are not equal, an error ("malloc(): smallbin double linked list corrupted") is thrown. 5. Sets the PREV_INSUSE bit for the next chunk (in memory, not in the doubly linked list) for victim
. 6. Remove this chunk from the bin list. 7. Set the appropriate arena bit for this chunk depending on av
. 8. Calls alloc_perturb
and then returns the pointer.
If size does not fall in the smallbin range: 1. Get index into the largebin array to access an appropriate bin according to the request size. 2. See if av
has fastchunks or not. This is done by checking the FASTCHUNKS_BIT
in av->flags
. If so, call malloc_consolidate
on av
.
If no pointer has yet been returned, this signifies one or more of the following cases: 1. Size falls into 'fastbin' range but no fastchunk is available. 2. Size falls into 'smallbin' range but no smallchunk is available (calls malloc_consolidate
during initialization). 3. Size falls into 'largbin' range.
Next, unsorted chunks are checked and traversed chunks are placed into bins. This is the only place where chunks are placed into bins. Iterate the unsorted bin from the 'TAIL'. 1. victim
points to the current chunk being considered. 2. Check if victim
's chunk size is within minimum (2*SIZE_SZ
) and maximum (av->system_mem
) range. Throw an error ("malloc(): memory corruption") otherwise. 3. If (size of requested chunk falls in smallbin range) and (victim
is the last remainder chunk) and (it is the only chunk in the unsorted bin) and (the chunks size >= the one requested): Break the chunk into 2 chunks:
The first chunk matches the size requested and is returned.
Left over chunk becomes the new last remainder chunk. It is inserted back into the unsorted bin.
Set chunk_size
and chunk_prev_size
fields appropriately for both chunks.
The first chunk is returned after calling alloc_perturb
.
If the above condition is false, control reaches here. Remove victim
from the unsorted bin. If the size of victim
matches the size requested exactly, return this chunk after calling alloc_perturb
.
If victim
's size falls in smallbin range, add the chunk in the appropriate smallbin at the HEAD
.
Else insert into appropriate largebin while maintaining sorted order:
First checks the last chunk (smallest). If victim
is smaller than the last chunk, insert it at the last.
Otherwise, loop to find a chunk with size >= size of victim
. If size is exactly same, always insert in the second position.
Repeat this whole step a maximum of MAX_ITERS
(10000) times or till all chunks in unsorted bin get exhausted.
After checking unsorted chunks, check if requested size does not fall in the smallbin range, if so then check largebins. 1. Get index into largebin array to access an appropriate bin according to the request size. 2. If the size of the largest chunk (the first chunk in the bin) is greater than the size requested: 1. Iterate from 'TAIL' to find a chunk (victim
) with the smallest size >= the requested size. 2. Call unlink
to remove the victim
chunk from the bin. 3. Calculate remainder_size
for the victim
's chunk (this will be victim
's chunk size - requested size). 4. If this remainder_size
>= MINSIZE
(the minimum chunk size including the headers), split the chunk into two chunks. Otherwise, the entire victim
chunk will be returned. Insert the remainder chunk in the unsorted bin (at the 'TAIL' end). A check is made in unsorted bin whether unsorted_chunks(av)->fd->bk == unsorted_chunks(av)
. An error is thrown otherwise ("malloc(): corrupted unsorted chunks"). 5. Return the victim
chunk after calling alloc_perturb
.
Till now, we have checked unsorted bin and also the respective fast, small or large bin. Note that a single bin (fast or small) was checked using the exact size of the requested chunk. Repeat the following steps till all bins are exhausted: 1. The index into bin array is incremented to check the next bin. 2. Use av->binmap
map to skip over bins that are empty. 3. victim
is pointed to the 'TAIL' of the current bin. 4. Using the binmap ensures that if a bin is skipped (in the above 2nd step), it is definitely empty. However, it does not ensure that all empty bins will be skipped. Check if the victim is empty or not. If empty, again skip the bin and repeat the above process (or 'continue' this loop) till we arrive at a nonempty bin. 5. Split the chunk (victim
points to the last chunk of a nonempty bin) into two chunks. Insert the remainder chunk in unsorted bin (at the 'TAIL' end). A check is made in the unsorted bin whether unsorted_chunks(av)->fd->bk == unsorted_chunks(av)
. An error is thrown otherwise ("malloc(): corrupted unsorted chunks 2"). 6. Return the victim
chunk after calling alloc_perturb
.
If still no empty bin is found, 'top' chunk will be used to service the request: 1. victim
points to av->top
. 2. If size of 'top' chunk >= 'requested size' + MINSIZE
, split it into two chunks. In this case, the remainder chunk becomes the new 'top' chunk and the other chunk is returned to the user after calling alloc_perturb
. 3. See if av
has fastchunks or not. This is done by checking the FASTCHUNKS_BIT
in av->flags
. If so, call malloc_consolidate
on av
. Return to step 6 (where we check unsorted bin). 4. If av
does not have fastchunks, call sysmalloc
and return the pointer obtained after calling alloc_perturb
.
Calls arena_get
to get an mstate
pointer.
Calls _int_malloc
with the arena pointer and the size.
Unlocks the arena.
Before returning the pointer to the chunk, one of the following should be true:
Returned pointer is NULL
Chunk is MMAPPED
Arena for chunk is the same as the one found in 1.
Check whether p
is before p + chunksize(p)
in the memory (to avoid wrapping). An error ("free(): invalid pointer") is thrown otherwise.
Check whether the chunk is at least of size MINSIZE
or a multiple of MALLOC_ALIGNMENT
. An error ("free(): invalid size") is thrown otherwise.
If the chunk's size falls in fastbin list:
Check if next chunk's size is between minimum and maximum size (av->system_mem
), throw an error ("free(): invalid next size (fast)") otherwise.
Calls free_perturb
on the chunk.
Set FASTCHUNKS_BIT
for av
.
Get index into fastbin array according to chunk size.
Check if the top of the bin is not the chunk we are going to add. Otherwise, throw an error ("double free or corruption (fasttop)").
Check if the size of the fastbin chunk at the top is the same as the chunk we are adding. Otherwise, throw an error ("invalid fastbin entry (free)").
Insert the chunk at the top of the fastbin list and return.
If the chunk is not mmapped:
Check if the chunk is the top chunk or not. If yes, an error ("double free or corruption (top)") is thrown.
Check whether next chunk (by memory) is within the boundaries of the arena. If not, an error ("double free or corruption (out)") is thrown.
Check whether next chunk's (by memory) previous in use bit is marked or not. If not, an error ("double free or corruption (!prev)") is thrown.
Check whether the size of next chunk is between the minimum and maximum size (av->system_mem
). If not, an error ("free(): invalid next size (normal)") is thrown.
Call free_perturb
on the chunk.
If previous chunk (by memory) is not in use, call unlink
on the previous chunk.
If next chunk (by memory) is not top chunk:
If next chunk is not in use, call unlink
on the next chunk.
Merge the chunk with previous, next (by memory), if any is free and add it to the head of unsorted bin. Before inserting, check whether unsorted_chunks(av)->fd->bk == unsorted_chunks(av)
or not. If not, an error ("free(): corrupted unsorted chunks") is thrown.
If next chunk (by memory) was a top chunk, merge the chunks appropriately into a single top chunk.
If the chunk was mmapped, call munmap_chunk
.
Return if mem
is NULL.
If the corresponding chunk is mmapped, call munmap_chunk
if the dynamic brk/mmap threshold needs adjusting.
Get arena pointer for that corresponding chunk.
Call _int_free
.