Idea: bitmaps for mailbox wait entries instead of linked lists?

[Jeehoon Kang]

Hi all,

In the current version of Hafnium, mailbox wait entries (`wait_entry`) are maintained in linked lists.  Each VM (say "vm1") has a "waiter_list" that tracks those VMs waiting for vm1 to be writable, and has a "ready_list" that tracks those VMs that are writable by vm1.

But I don't think it's strictly necessary to maintain the wait entries in linked list.  I guess just plain bitmaps are enough to implement the current functionality.  I'm wondering (1) whether I understand it correctly, (1) why you're using linked list, and (2) whether it's plausible to replace linked lists with bitmaps.

Thanks,

Jeehoon

[Andrew Scull]

The most significant difference I can think of is that the linked lists provide an order whereas the bitmaps don't. It's not obvious to me how important this is off hand; there could be a problem with progress or bias but I don't know how to analyse that properly. Might be worth asking Wedson who will have thought about this the most.

Would I be correct in guessing that you are asking this question because building this kind of list from scattered nodes isn't idiomatic Rust? Or do you foresee a difficulty with formal analysis? If there is an expectation that the analysis will assume a restricted memory model then it is something we should discuss at an early stage to help guide implementation choices.

--
You received this message because you are subscribed to the Google Groups "Hafnium" group.
To unsubscribe from this group and stop receiving emails from it, send an email to hafnium-discu...@googlegroups.com.
To post to this group, send email to hafnium...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/hafnium-discuss/8bfe4781-e17a-4757-afd4-f6679acf18c6%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.