Implementation

Structure explanations

Things to keep in mind

• Fragmentation

  • Even if there is enough unused memory in total, the blocks could be divided into small pieces not allowing a large allocation

• Space-efficiency

  • Adding extra metadata such as header and footer for each allocation will reduce the space efficiency

Basic structure

zone

• zone: All allocations are categorized into 3 zones by their size. Tiny, Small, and Large.

Tiny and Small

• magazine: Each zone has a magazine that contains metadata for each zone.
• region: Each magazine has one region at initialization and it allocates new regions as needed.
• quantum: Allocation unit in each zone. Block size (including header) is always multiples of quantum size.

zone	quantum
tiny	16B
small	512B

Large

• allocations(list): Keeps track of all large allocations. Just used for debugging purposes such as in the function show_alloc_mem()

[Compare with OSX]

• OSX malloc has a rack for each zone
• In a rack, there are multiple magazines: one magazine per physical core.
• more details: The macOS/iOS default heap

Zones

• Increase the chance of accessing the best-matched freed block.
• Decrease the fragmentation by setting a minimum block size for each zone.

How is the zone size defined

• Zone needs to be identifiable by the allocated block.

  • block size is not enough for the zone identification because the allocated block size is not the same as the allocation demanded. Alignment and the addition of a header change the final block size, and also, the initial size demanded will not be recorded inside blocks.

• Zones are divided to maximize the use of freelist.

[Compare with OSX]

• OSX malloc uses the address of the block to check if it is in a range of a region that belongs to a zone.
• It uses a hash table to avoid looping through all the regions in each zone.
• ex) hash_lookup_region_no_lock

Freelist (Manage unused blocks)

To allow O(1) access to unused blocks, create a list of freed blocks

• empty until free is called for the first time
• after each free, store the freed block in a list
• tiny zone and small zone each has a single freelist in its magazine just to simplify each function call. However, this freelist is structured to allow using a single freelist for all the allocation.