Linux has a bitmap for the piar of chunk of pages which have the same size.

This bitmap has the value 0 when both of pair is free or when both of pair

is partially or fully used.

The value has 1 when one of both is partilally or fully used,

and the other is free.

In this case, this pair of chunk of pages can be merged and

made to doubled chunk of pages.

For example,

0 1 2 3 4 5 6 7 +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ |U| | | | | | | | | |U| | | | | +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-++-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ | | | | |U| | | | | | | | | | | +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ 8 9 10 11 12 13 14 15

U means the page is used.

In this example, pitmaps for each order of page chunk is as following.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 order 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | order 1 | 1 | 1 | 1 | 0 | order 2 | 0 | 1 | order 3 | 0 |

i)

When one page is needed, page 1 is allocated and remove from free list

or order 0 and bitmap for order 0 becomes 0 because both of pages

this bit represent are used.

ii)

On the other hand, when page 0 is freed, the system put page 0 into

the free list of order 0 and looks at the bit corresponding this page.

The bit(0) is 1. page 0 and 1 can be merged.

System remove page 0 and 1 from the free list of order 0 and put these

into free list of order1.

Next, look at bit corresponding page 0 of the bitmap for order 1.

This bit represents pair of 0-1 pages and 2-3 pages.

This bit has 1, mergable. then look at 2-3 pages and they are free,

four pages (0,1,2,3) is merged up to order 2 and this bit is clear to 0.

Then up to order 2, corresponding bit is 0. And another chunk of pages

(4,5,6,7) is partially used, this bit is set to 1.

At this point, operation will be stopped.

iii)

When two page is requested, the system looks at the bitmap of order 1.

And bit 0 has 1, which means either of page 0-1 or page 2-3 is free.

This time, page 2-3 is free. The system remove these two page from

free list of order 1 and set bit0 to 1 because page 0-1 is partially used

and page 2-3 is fully used.

iv)

When page 5 is freed, corresponding bit has 1. page 4 is free and

these two page is mergable. The system remove page 4-5 from free list

of order 0 and bit3 (of bitmap for order 0) is set to 0.

And page 4-5 is appended into order 1 free list and corresponding bit of

the bitmap for order 1 has 1, which specifies pages are mergable again.

Pages 4-5 and 6-7 are merged and bit1 of bitmap for order 1 is set to 0.

pages 4-7 are free and pages 0-3 is partially used, So bit0 of bitmap

for order 2 is reset to 1.

But for bitmap for order 3, pages 0-7 and 8-9 are both partially used,

first bit of this bitmap is still 0.

The starting page frame number for order n is

(from now order means 2^order)

0 order 2*order 3*order .... n*order ....

And pair of chunk of pages is represented by

2n*order and (2n + 1)*order

The difference is order. So, addition or subtraction of 2^order

gives each other.

As the chunk size is 2^order, this operation is to be done with bit operation.

If (1 << order) bit is set, this chunk is upper one and subtraction 2^order

is the same operation with clearing this bit to 0.

If (1 << order) bit is not set, this chunk is lower one and addtion 2^order

is the same operation with setting this bit to 1.

In result, these operation is summed up to the "exclusive or" operation at

(1 << order) bit.

The pair of chunk of pages should be merged up to doubled chunk by

putting togather lower chunk and upper chunk.

So, the index for the double sized chunk of pages (level of order + 1)

starts at index of lower chunk of pages for level of order.

This index should be get by clearing the bit (1 << order) and this

operation is done and-ed index of lower chunk with ^(1 << order).