Ariane van der Steldt


pmemrange: the physical memory allocator

vmmap: the virtual memory allocator

64-bit and jit

Physical memory

Before pmemrange

Physical memory was a list of pages.

This caused high fragmentation.

Fragmentation is bad for devices.

Before pmemrange - it gets worse

ISA and PCI devices could become starved.

ISA and PCI device can no longer make progress.


A new physical memory allocator:




Memory ranges

Memory allocation

Pmemrange turned out to be faster than the original code!


VM map

VMmap: mapping Virtual Memory

Original VMmap

Address Space Layout Randomization tacked on without adapting the underlying algorithm.

Original address selection


First replacement

Best-fit allocator.

The good:

First replacement failed

The bad:

The ugly:

How did this break random?

Investigating what went wrong.

Implementation bugs made this worse.

Randomization did add gaps, but was too predictable in which memory was used.

Browsers, java & mono breakage

They all use JIT (Just In Time) compilation.

PIC - Position Independant Code

PIC - Position Independant Code

PIC makes code agnostic to position.

Offset is a 32-bit value.

JIT - pointer clipping

Aw, Snap!

JIT - workarounds

Smart and dumb software

Good software is boring:

VMmap additional requirements

Split mapping and allocation

vm_map - allocation in VMmap

vm_unmap - unmapping in VMmap

Compatibility for JIT

mmap(addr, size, ...)

Posix says: "A non-zero value of addr is taken to be a suggestion of a process address near which the mapping should be placed"

Allows us to fix browsers.

Functionality implemented in hint selector.

Better random algorithm

Introducing pivot allocator

Pivot algorithm

16 active pivots

Common case: O(1)

Pivot creation: O(log n)

Low fragmentation, hard to predict

Wrapping it up