• MatthewWilcox
• NaturallyAlignedOrder

In Linux, pages of memory are allocated using a buddy allocator. This has the effect of naturally aligning allocations; eg an allocation of 1MB always starts at a multiple of 1MB. That means that it's a relatively common thing to want to communicate both a location and an order (eg order of 8 at location of 19MB).

This is an encoding scheme that allows us to describe an offset and an order with a single extra bit. While this sounds like black magic, it's even relatively efficient to encode/decode.

To start with a toy example, imagine we have four pages numbered 0-3. We have eight possible allocations to describe, each of the four pages of order 0 (size 1); pages 0 and 2 of order 1 (size 2); page 0 of order 2 (size 4) and no page. Clearly we can encode eight things in 3 bits, so we need one extra bit beyond the two bits we need to describe the four pages.

OK, so how do we encode this information in a regular fashion? There are a few different ways to do this (eg inverting all the bits, or using top bits instead of low bits), but here's the one I like:

• If all bits are zero, there is no object.
• If bit 0 is set, the described allocation is order 0, and bits 1-N are the offset.
• If the bottom two bits are 10b, the allocation is order 1. Bits 2-N multiplied by two are the offset.
• If the bottom three bits are 100b, the allocation is order 2. Bits 3-N multiplied by four are the offset.
• ... and so on.

Example (bold highlights the bits used for order)

int decode_order(unsigned long data)
{
    return ffsl(data) - 1;
}

unsigned long decode_offset(unsigned long data)
{
    return (data & (data - 1)) / 2;
}

unsigned long encode_offset_order(int order, unsigned long offset)
{
    assert(offset & ((1UL << order) - 1) == 0);
    assert((long)offset >= 0);
    return (1UL << order) | (offset * 2);
}

decode_order() will return -1 for the "no allocation" case. Or you can test for that explicitly before calling these functions. encode_offset_order() cannot return "no allocation"; you would set that up yourself.