On Tue, Jun 25, 2024 at 10:17:57PM +0100, Matthew Wilcox (Oracle) wrote:
> Rosebush is a resizing hash table. See
> Docuemntation/core-api/rosebush.rst for details.
What about "Document Rosebush hash table - overview, implementation details/internals, and API
docs"?
> +Overview
> +========
> +
> +Rosebush is a hashtable, different from the rhashtable. It is scalable
> +(one spinlock per bucket), resizing in two dimensions (number and size
> +of buckets), and concurrent (can be iterated under the RCU read lock).
> +It is designed to minimise dependent cache misses, which can stall a
> +modern CPU for thousands of instructions.
> +
> +Objects stored in a rosebush do not have an embedded linked list.
> +They can therefore be placed into the same rosebush multiple times and
> +be placed in multiple rosebushes. It is also possible to store pointers
> +which have special meaning like ERR_PTR(). It is not possible to store
> +a NULL pointer in a rosebush, as this is the return value that indicates
"..., however, as this ..."
> +the iteration has finished.
> +
> +The user of the rosebush is responsible for calculating their own hash.
> +A high quality hash is desirable to keep the scalable properties of
> +the rosebush, but a hash with poor distribution in the lower bits will
> +not lead to a catastrophic breakdown. It may lead to excessive memory
"..., but rather it may lead to ..."
What does catastrophic breakdown mean anyway?
> +consumption and a lot of CPU time spent during lookup.
> +
> +Rosebush is not yet IRQ or BH safe. It can be iterated in interrupt
"This means that ..."
> +context, but not modified.
> +
> <snipped>...
> +IRQ / BH safety
> +---------------
> +
> +If we decide to make the rosebush modifiable in IRQ context, we need
> +to take the locks in an irq-safe way; we need to figure out how to
> +allocate the top level table without vmalloc(), and we need to manage
> +without kvfree_rcu_mightsleep(). These all have solutions, but those
> +solutions have a cost that isn't worth paying until we have users.
Use cases?
Thanks.
--
An old man doll... just what I always wanted! - Clara
Attachment:
signature.asc
Description: PGP signature
