On Tue, Sep 09, 2025 at 04:44:21PM +0200, Pratyush Yadav wrote:
> The KHO Array is a data structure that behaves like a sparse array of
> pointers. It is designed to be preserved and restored over Kexec
> Handover (KHO), and targets only 64-bit platforms. It can store 8-byte
> aligned pointers. It can also store integers between 0 and LONG_MAX. It
> supports sparse indices, though it performs best with densely clustered
> indices.
That is a bit of an understatement, it looks like worst case cost is
4k per entry. I would expect better efficiency than this if we are
serious about supporting sparsity..
I think you need to encode the start pos within the entries in some
way so worst case cost is bounded to more like 16/24 byte per entry.
For instance if the page was broken up into an array of structs like
struct entries_block {
u64 flags:1;
u64 num_entries:13
u64 pos_increment:50;
u64 entries[]; // contiguous pos
};
And if a high 64 bit pos can't be represented with pos_increment then
you'd have flags = X and entries[0] == pos instead.
Jason
