> 1. Find the `start_level` from the `target_order`. (for example,
> target_order = 10, start_level = 4)
> 2. The path from the root down to the level above `start_level` is
> fixed (index 0 at each of these levels).
> 3. At `start_level`, the index is also fixed, by (1 << (63 -
> PAGE_SHIFT - order)) in a 9 bit slice.
> 4. Then, for all levels *below* `order_level`, the walker iterates
> through all 512 table entries, until the bitmap level.
You don't need any special logic like that, that is my point, the
whole thing is very simple:
static int get_index(unsigned int level, u64 pos)
{
return (pos / (level * ITEMS_PER_TABLE * ITEMS_PER_BITMAP)) %
ITEMS_PER_TABLE;
}
walk_table(u64 *table, unsigned int level, u64 start, u64 last)
{
unsigned int index = get_index(level, start);
unsigned int last_index = get_index(level, last);
do {
if (table[index]) {
u64 *next_table = phys_to_virt(table[index]);
if (level == 1)
walk_bitmap(next_table);
else
walk_table(next_table, level - 1, start, last);
}
index++;
} while (index <= last_index);
}
insert_table(u64 *table, unsigned int level, u64 pos)
{
unsigned int index = get_index(level, start);
u64 *next_table;
if (!table[index]) {
// allocate table[index]
}
else
next_table = phys_to_virt(table[index]);
if (level == 1)
insert_bitmap(next_table, pos);
else
insert_table(next_table, level - 1, pos);
}
That's it.. No special cases requried.
The above is very limited, it only works with certain formulations
of start/last:
start has only one bit set
start & last == true,
last ^ start has bits 0 -> N set N > log2(ITEMS_PER_BITMAP)
Which align to my suggestion for encoding.
Jason
