[RFC v1 1/4] kho: Introduce KHO page table data structures

[Jason Gunthorpe]

>   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