THE HEAP

so , i do not understand these yet , and this is exactly why I'm writing this , to understand along with you , my dear reader, you might take a glimpse of my genuine craziness in the process .
also , we'll be understanding the glibc implementation , others should be fairly similar.

so first , what are heaps ?

  • heaps are fundamentally complete trees that satisfy the heap property , we'll get to what the fuck is that in a second, now , because I want to understand binary heaps , they are the main type I'm referring to with the word heap in this article , other types have similar structures .
  • heap property ? , yeah this is described as :"In a max heap, for any given node C, if P is the parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C."

what does this have to do with the heaps in memory layout of a program ?

  • absolutely nothing , you see , the UNIX system only provides two functions to deal with the heap , brk(void end_data_segment) and sbrk(intptr_t increment)* , the first sets the program break at the address specified by end_data_segment , the second increases the program break by the value specified by increment , as you can see , those fucking suck in the point of view of you average programmer who just wants to get some memory for his stuff . at this point malloc and its family steps into play , we all know how the work at a basic usage level so i'm not going into that here , if you dont , I suggest you get the fuck out and learn C .
  • malloc uses sbrk to allocate block , but how does free work ? how does it know how much memory to free when we pass a pointer to it ? .
  • in the libc implementation of free(),free blocks are kept in a data structures called bins , we'll get to those in a sec , in some implementations a spray tree is used along with bins , not libc though .

bins ? where your chunks chill

  • bins are linked lists or doubly linked lists depending on which type we are talking , yes there is types , four of them and they are distributed a cross an array of 126 bin:
    1. unsorted bins (one bin of index bins[1] ): they hold in the second latest freed blocks of arbitrary sizes
    2. fast bins (one bin)bins[0] : they hold small chunks, this is done to facilitate the allocation of small chunks and avoid unnecessary splits and fragmentation as the blocks in this bin are never merged with other blocks as is the case with small and large bins.
    3. small bins (there are 62 of them , from 2 to 63 indexes): size of chunks in those range from the fast bins max all the way to 1080 bytes , each bin of those hold chunks of similar types (in a 16 bytes range to be precise or 8 bytes if the system is 32 bit) , this is due to the way newly freed chunks are indexed , which consists of dividing them using binary operation , specifically shifting , how that works ? see bitwise operations , the thing is that we divide the chunk size by 8-16 for 32-64 architectures , and in that process the index is determined but the residue , which is under 8-16 is lost in the process and the chunk is indexed there anyways, so between a bin and the next the minimum size differs by 16-8 .
    4. large bins (there are 63 of them , indexes from 64 to 126 ): this hold the chunks bigger than 1028 bytes and the difference between the minimum sized in consecutive bins increases with the index because it has to hold up to any size , it follows similar index deciding technique as small bins . "According to the preceding definition, the size of the chunk linked list in a large bin does not increase by degrees. On a 64-bit platform, the chunk size of the first 32 large bins is increased by 64 bytes, that is, the chunk size of the first large bin ranges from 1,024 bytes to 1,087 bytes and the chunk size of the second large bin ranges from 1,088 bytes to 1,151 bytes... The chunk size of bins 33 to 48 is increased by 512 bytes. The chunk size of bins 49 to 56 is increased by 4,096 bytes. The chunk size of bins 57 to 60 is increased by 32,768 bytes. The chunk size of bins 61 and 62 is increased by 262,144 bytes. The rest chunks are stored in the last large bin. The chunk size in a large bin may be different. Therefore, to speed up memory allocation and release, all chunks in the large bin are arranged in descending order of chunk size. The largest chunk is stored at the head of the linked list, and the smallest chunk is stored at the end of the linked list."
    • in small and large bins , consecutive free blocks are merged into one larger block and then replaced into adequate bin .
    • free merges consecutive block to form larger ones, it can do that because block have flag bytes right in the beginning of the header containing the metadata of the block , and there is usually three flags , the one that interests us is the one that tells if the previous block is in use (0 means not in use and 1 in use). so when free finds a free block that also sets the flag in the next block to indicate that the previous block is free , so that free knows that it can merge them.

arenas ? don't you touch my heap.

  • when a program starts it has the main heap that it can control with brk and that works fine for single threaded programs , however when we enter the realm of multi-threading , we run into problems because of memory locks , that is when a process is accessing some memory , other processes must wait for it before the can access that exact memory , this wastes resources .
  • for that reason , whenever a new thread is created , and arena is created for it using mmap() , this creates a heap for that thread that is separate from the memory of the main process and other threads .
  • each thread has its own bins and tchaches in its arena
  • a thread can request multiple heaps using mmap which are then added to its arena , an arena contains at least one heap .
  • when the thread terminates or calls munmap , the heap is returned to the system .
  • the main process can access the main arena (its own) and the arenas of all sub-threads , but sub-threads can only access their own arena
  • arenas are usually allocated in higher memory addresses than the heap , means the main heap grows upwards in memory towards the memory allocated by mmap , but if the heap grows too much to cross over the arenas the kernel wont allow it and an ENOMEM error is returned .
  • this is an approximate of how arenas are laid out in memory:
Low Addresses
+----------------------+  <-- .text (program code)
|        Code         |
+----------------------+  <-- .data (initialized global variables)
|        Data         |
+----------------------+  <-- .bss (uninitialized globals)
|        BSS          |
+----------------------+  <-- Heap (grows upward via `sbrk()`)
|        Heap         |  <--- You are here when increasing `sbrk()`
|        ...          |
|        ...          |
+----------------------+  <-- mmap() allocations (TLS, arenas, etc.)
|        Mapped       |  <--- Other arenas live here
|        Memory       |
+----------------------+
|        Stack        |  <-- Grows downward
+----------------------+
High Addresses

tcache , where your block dont chill

  • to quote chatgpt:
    memory management, specifically in the context of glibc's malloc() and free() implementations, tcache stands for Thread-Cache. It is a mechanism designed to improve performance and reduce contention for memory allocations in multi-threaded programs.
  • The main goal of tcache is to speed up memory allocation and deallocation by providing fast access to recently freed memory. Instead of going through the entire heap or arena, tcache maintains a small, local cache of recently freed memory chunks for each thread.

what happens when a block is freed?

  • when a block is freed it is put in the tcache , if there is place the that's just what is done (the tchach capacity is specified by Tcache_MAX ) , if tchache is full it is put into one of the bins.
  • after a chunk is dropped from the tcache , it's put into one of the bins at a specific index depending on it's size .

what happens when malloc wants to allocate a block?

  • it looks for it in this order:
  • Thread Cache (tcache):
    • Description: A per-thread cache introduced in glibc 2.26 to improve performance by reducing contention in multithreaded programs.
    • Operation: Each thread maintains its own cache of recently freed chunks. If a suitable chunk is found in the tcache, it's allocated immediately.
  • Fast Bins:
    • Description: Singly linked lists that store freed chunks of small sizes for quick allocation and deallocation.
    • Operation: If the tcache doesn't have a suitable chunk, malloc checks the fast bins next. These bins allow for rapid allocations but are not consolidated immediately to prevent fragmentation.
  • Unsorted Bin:
    • Description: A temporary holding bin for freed chunks before they're sorted into small or large bins.
    • Operation: Chunks that don't fit into fast bins are placed here upon being freed. During allocation, malloc scans the unsorted bin to find a suitable chunk before moving them to their respective bins.
  • Small Bins:
    • Description: Bins that store chunks of fixed sizes, typically less than 512 bytes on 32-bit systems or 1,024 bytes on 64-bit systems.
    • Operation: If no suitable chunk is found in the unsorted bin, malloc checks the small bins corresponding to the requested size.
  • Large Bins:
    • Description: Bins that store larger chunks, with sizes equal to or greater than 512 bytes on 32-bit systems or 1,024 bytes on 64-bit systems.
    • Operation: For large memory requests, malloc searches the large bins for a suitable chunk. If an exact match isn't found, a larger chunk may be split to satisfy the request.
  • one thing that should be noted is that the uppermost block of an arena is not put in any bin and is treated specially , when malloc doesn't find a suitable block in any of the bins it checks that uppermost block , if it is larger it splits it and takes returns a block of adequate size to the user , if not it increases it's size using sbrk and then does the same.
+-------------------------------+  0x00000000
| NULL Page (Unmapped)          |
+-------------------------------+
| Program Code (.text)          |  ⬅ Executable Instructions
| Program Data (.data, .bss)    |  ⬅ Global & Static Variables
+-------------------------------+
| Shared Libraries (`libc.so`)  |  ⬅ Dynamically Loaded Libraries
+-------------------------------+
| Thread Stack (Main)           |  ⬅ Stack of Main Thread (Grows Down)
| ...                           |
| Stack Guard Page              |  ⬅ Prevents Stack Overflow
+-------------------------------+
| Thread Stack (Thread 1)       |  ⬅ Each Thread Has Its Own Stack
| ...                           |
+-------------------------------+
| Thread Stack (Thread N)       |
| ...                           |
+-------------------------------+
| Main Heap (sbrk region)       |  ⬅ Managed by `malloc`, uses bins
| ├── Fast Bins (Fixed Sizes)   |  ⬅ Quick allocations (Size < 64B)
| ├── Small Bins (Sorted Lists) |  ⬅ Sizes from 64B to 512B
| ├── Large Bins (Sorted Lists) |  ⬅ Sizes above 512B
| ├── Unsorted Bin              |  ⬅ Newly freed chunks before sorting
| ├── Tcache (Per Thread Cache) |  ⬅ Fast per-thread allocations
+-------------------------------+
| Arena 1 (Main Thread)         |  ⬅ First Arena, contains the main heap
| ├── Heap 1                    |  ⬅ Initial heap (from `sbrk`)
| ├── Heap 2 (via mmap)         |  ⬅ Additional heap chunks (if needed)
+-------------------------------+
| Arena 2 (Thread 1)            |  ⬅ Each thread gets its own arena
| ├── Heap 1                    |  ⬅ Created with `mmap`
| ├── Heap 2                    |  ⬅ Additional heap space
+-------------------------------+
| Arena N (Thread N)            |  ⬅ More threads, more arenas
| ├── Heap 1                    |
| ├── Heap 2                    |
+-------------------------------+
| Memory Mapped Regions (mmap)  |  ⬅ Large allocations bypass heap (e.g. `mmap`)
| ├── Shared Memory             |  ⬅ `mmap(MAP_SHARED)`
| ├── Anonymous Memory          |  ⬅ `mmap(MAP_ANONYMOUS)`
+-------------------------------+
| Kernel Space (Unmapped)       |  ⬅ OS Controlled Memory
+-------------------------------+  0xFFFFFFFF (x86) / 0x7FFFFFFFFFFF (x86_64)

anatomy of heap chunks

  • as we said before briefly , each memory chunk has a header that contains metadata , we're gonna see how that works , first and most important , the chunk data structure is like this :

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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;
};
  • as you can see each blocks header has information on the next chunks backwards and forwards , namely fd_nextsize and bk_nextsize , those are used solely when the block is in a bin of course ,as they do not point to neighboring chunks in but rather in a list , also mchuck_prev_size which indicated the size of the previous chunk and that is used in case of when both blocks are free and ought to be merged , if the previous block is not free , this variable is not valid .
  • but how do we know if the previous block is free? you see, the last three bits of mchunk_size are always unused are are there for alignement reasons , so they are used as flags :
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

end

  • and this is it , the heap in a nutshell.