heap.md

Notes made while learning more about Heap (https://azeria-labs.com/ and https://sploitfun.wordpress.com/)

Memory Chunks:

Whenever someone demands for space in heap (let' say 20bytes), heap managers returns a pointer to some address which is slightly more in size then 20 bytes as it needs to store other metadata. Then the Heap Manager marks this chunk Allocated.

CHUNK ALLOCATION:

• If there is some previously freed chunk which is fullfills the demands of the programmer, then the heap manager will use that chuck for the new allocation.
• If there is space available at the top of the heap (higher address) then the heap manager will allocate that space.
• If there is no space left at the top of the heap then the heap manager would ask kernel to add at the end of the heap and then allocate the new chunk.
• If none of them worked then the result would be null.

Allocation from free'd chunks:

If some chunk if free'd from the process then heap manager track them in linked lists called bins. When a new allocation request is made then heap managers searches these bins for the chunk which fulfills the demands and marks it allocated.

Allocation from top of the stack:

If there is no free'd space that can service our needs then the heap manager looks at the top of the heap if there is space available and if found then the heap manager allocates the space to the chunk.

Asking Kernel for more memory:

Once the initial heap is all covered up, heap manager would ask kernel to add more memory at the end of the heap.On the initial heap, the heap manager asks the kernel to allocate more memory at the end of the heap by calling sbrk. On most Linux-based systems this function internally uses a system call called “brk”. As the system call is made by the heap manager, it would allocate more memory at the end of the initial heap.

Calls made to brk can sometimes fail as the heap can grow so large that it can collide with other memory mapping such as shared library, function stacks. Once the heap reaches this point, the heap manager will resort to attaching new non-contiguous memory to the initial program heap using calls to mmap.

Off Heap allocation (MMAP):

Where the initial heap grew using sbrk, the heap manager emulates “growing” the subheap into this reserved address range by manually invoking mprotect to change pages in the region from PROT_NONE to PROT_READ | PROT_WRITE. This causes the kernel to attach physical memory to those addresses, in effect causing the subheap to slowly grow until the whole mmap region is full. Once the entire subheap is exhausted, the arena just allocates another subheap. This allows the secondary arenas to keep growing almost indefinitely, only eventually failing when the kernel runs out of memory, or when the process runs out of address space.

*By default, the maximum size of a subheap–and therefore the region of memory reserved for the subheap to grow into–is 1MB on 32-bit processes and 64MB on 64-bit systems.

When large allocation requests are encountered, then the allocation is done off-heap using call to mmap. When these chunks are passed to free then the memory is returned to system.

By default this threshold is 128KB up to 512KB on 32-bit systems and 32MB on 64-bit systems, however this threshold can also dynamically increase if the heap manager detects that these large allocations are being used transiently.

Arenas:

On multithreaded applications, the heap manager requires secondary location for such threads which are known as arenas. Each arena is entirely different heap and manages it own bins and chunk allocation separately.

With each new thread that joins the process, the heap manager tries to find an arena that no other thread is using and attaches the arena to that thread. Once all available arenas are in use by other threads, the heap manager creates a new one, up to the maximum number of arenas of 2x cpu-cores in 32-bit processes and 8x cpu-cores in 64-bit processes. Once that limit is finally reached, the heap manager gives up and multiple threads will have to share an arena and run the risk that performing heap operations will require one of those threads to wait for the other.

SubHeaps:

Where the initial heap grew using sbrk, the heap manager emulates “growing” the subheap into this reserved address range by manually invoking mprotect to change pages in the region from PROT_NONE to PROT_READ | PROT_WRITE. This causes the kernel to attach physical memory to those addresses, in effect causing the subheap to slowly grow until the whole mmap region is full. Once the entire subheap is exhausted, the arena just allocates another subheap. This allows the secondary arenas to keep growing almost indefinitely, only eventually failing when the kernel runs out of memory, or when the process runs out of address space.

*By default, the maximum size of a subheap–and therefore the region of memory reserved for the subheap to grow into–is 1MB on 32-bit processes and 64MB on 64-bit systems.

Multiple Heaps:

heap_info - Heap Header – A single thread arena can have multiple heaps. Each heap has its own header. Why multiple heaps needed? To begin with every thread arena contains ONLY one heap, but when this heap segment runs out of space, new heap (non contiguous region) gets mmap’d to this arena.

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

malloc_state - Arena Header – A single thread arena can have multiple heaps, but for all those heaps only a single arena header exists. Arena header contains information about bins, top chunk, last remainder chunk.

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

malloc_chunk – Chunk Header – A heap is divided into many chunks based on user requests. Each of those chunks has its own chunk header.

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

• Main arena dont have multiple heaps and hence no heap_info structure. When main arena runs out of space, sbrk’d heap segment is extended (contiguous region) until it bumps into memory mapping segment.

• Unlike thread arena, main arena’s arena header isnt part of sbrk’d heap segment. Its a global variable and hence its found in libc.so’s data segment.

Chunks:

They can be of the following types:

• Allocated chunk
• Free chunk
• Top chunk
• Last Remainder chunk

Allocated chunk:

prev_size : If the previous chunk is free, this field contains the size of previous chunk. Else if previous chunk is allocated, this field contains previous chunk’s user data.

size : This field contains the size of this allocated chunk. Last 3 bits of this field contains flag information.

• PREV_INUSE (P) – This bit is set when previous chunk is allocated.
• IS_MMAPPED (M) – This bit is set when chunk is mmap’d.
• NON_MAIN_ARENA (N) – This bit is set when this chunk belongs to a thread arena.

NOTE:

• Other fields of malloc_chunk (like fd, bk) is NOT used for allocated chunk. Hence in place of these fields user data is stored.
• User requested size is converted into usable size (internal representation size) since some extra space is needed for storing malloc_chunk and also for alignment purposes. Conversion takes place in such a way that last 3 bits of usable size is never set and hence its used for storing flag information.

Free Chunk:

prev_size : No two free chunks can be adjacent together. When both the chunks are free, its gets combined into one single free chunk. Hence always previous chunk to this freed chunk would be allocated and therefore prev_size contains previous chunk’s user data.

size : This field contains the size of this free chunk.

fd : Forward pointer – Points to next chunk in the same bin (and NOT to the next chunk present in physical memory).

bk : Backward pointer – Points to previous chunk in the same bin (and NOT to the previous chunk present in physical memory).