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,
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | |U| | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
|U| | | | | | | | | |U| | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
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.
Calculate the index for chunk of pages
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).