Memory Allocation Flashcards
Tcache bins
Thread specific.
Stack.
Singly Linked.
Heads are in thread local storage.
It has chunks of fixed size s_i.
Arenas
Division of the heap.
Access requires synchronization.
At most, one thread can allocate.
Metadata is stored in a struct malloc_state.
Fastbins
Every arena has N_f fastbins of equally sized chunks.
Thread locks the arena when accessing it.
Stack.
Singly Linked.
Heads are found in malloc_state of the arena.
Has chunks of fixed size sf_i.
Smallbins
Every arena has N_s smallbins of equally sized chunks.
Queue.
Doubly-Linked.
Heads are found in malloc_state.
Has chunks of fized sizes ss_i.
Unsorted Bin
Every arena has one unsorted bin
with chunks of any size.
Queue.
Doubly-Linked.
Head in malloc_state.
Chunks of any size.
Large Bins
Every arena has N_l large bins with chunks in a certain size interval.
Stack.
Doubly-Linked list of Doubly-Linked lists of fixed size chunks.
Heads in malloc_state.
Chunk sizes in certain interval.
Malloc procedure
Check bins in the following order until we find chunk of exact size and if not, split the next larger chunk:
1. tcache bin
2. fastbin (refill tcache)
3. smallbin (refill tcache)
4. unsorted bin
- exact match (refill tcache)
- sort into small and large bins
5. largebin
6. anybin
7. re-check fastbins
8. top chunk
9. grow arena
Free procedure
If chunk fits, push into:
1. tcache bin
2. fastbin
3. unsorted bin (consolidate chunk if possible)
4. if treshold is surpassed, clean up fastbin and shrink arena
Invariant
A chunk in the unsorted bin, smallbins or largebins never borders another chunk in those bins or the top chunk.
How is the invariant upheld?
By performing consolidation of chunks that are moved into the unsorted bin.
Allocated Chunk
.
next chunk
|
v
———————————————————————————————————
prev. size or prev. user data | size | AMP | user data | size | AMP |
———————————————————————————————————
[ metadata = 16 bytes ]
Free chunk: unsorted, small, large bin
metadata| fwd.ptr| bkwd.ptr | nxt.size.ptr | prev.size.ptr | size | AMP |
———————————————————————————————————
prev. size or prev. user data | size | AMP |
————————————————————-
[ metadata = 16 bytes ]
*nxt.size.ptr and prev.size.ptr only used for chunks in large bin that are the first in their size
Free chunk: tcache, fastbin
metadata | next ptr| tcache key | junk | --------------------------------------------------------------------------------------------------------- [ metadata = 16 bytes ]
*tcache key only for tcache:
process-wide random cookie used to detect double frees
Safe Linking
Next pointer for tcache and fastbins gets xored with the page they are stored before being written into the chunk.
Circumvent Safe Linking
Leak a pointer in the program and it can be used to reverse the xor operation.
