File PageHeap.h

↰ Parent directory (ADS/memory)

The heap of pages of size classes under PoolResource [see File PoolAllocator.h] and ConcurrentPoolResource [see File ConcurrentPool.h], beyond the book: slots of :math:` ( c + 1 ) g ` bytes, :math:` g = 8 , for the classes :math: c = 0 , dots , C - 1 `, with the free lists sharded by page.

Definition (ADS/memory/PageHeap.h)

Detailed Description

The heap takes segments of :math:` 2^{21} ` bytes, aligned to their size and advised for the huge pages [see File HugePageAllocator.h], and cuts them into pages of :math:` 2^{16} ` bytes; a page holds the slots of one class after a header of 64 bytes, so that the page of a slot p is :math:` p wedge neg ( 2^{16} - 1 ) `. Each page has a free list of its own, and the slots never given yet are cut from it in the order of their addresses. A class allocates from its current page, the pop of its free list or the bump of its pointer; when the page is exhausted, the class moves to the next page of its list of the pages with free slots, or to a new page, and the exhausted page leaves the list until a slot of it is freed, which puts it back. A free is the push on the list of the page of the slot, plus the test of a flag.

So the objects made one after another come from one page, even after frees in a scrambled order: a single free list, as that of ObjectPool [see File ObjectPool.h], gives back the slots in the order of the frees, scattered over all the memory, while the lists by page give them back a page at a time, so that the nodes of a container built again are close to each other and the walks over them miss the cache less. The memory goes back to the system only with the heap.

The contracts [see File Contract.h]: a slot freed belongs to the heap and is freed once. The operations are defined at the end of the header.

  1. Leijen, B. Zorn, L. de Moura, Mimalloc: free list sharding in action, Programming Languages and Systems (APLAS 2019), Lecture Notes in Computer Science 11893, 244-265, 2019, doi:10.1007/978-3-030-34175-6_13 (the free lists by page, the page of a pointer by masking)

  1. Bonwick, The slab allocator: an object-caching kernel memory allocator, Proceedings of the USENIX Summer 1994 Technical Conference, 1994, www.usenix.org/publications/library/proceedings/bos94/bonwick.html (the slabs of one size with their own free lists, the list of the slabs partly free)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces