Hash table with interior mutability

[KernelMC]

I'm working on a userspace filesystem implementation. The code is organized around a table of inodes which is implemented using the type Arc<RwLock<HashMap<u64, Arc<RwLock<TableValue>>>>>, where TableValue is a struct with information I need for each inode. There are two levels of locking so I can support mutation of individual table values without blocking concurrent access to others. When I first implemented this I was focused on supporting the FUSE API, so I had to lock the table on each access and lookup an entry based on the inode in the request from the kernel.

I'm now trying to design an API for other Rust code in the same process to access the filesystem. I don't want consumers of the API to incur the locking and hash table lookup overhead on every filesystem access. I'd like to given them a handle when they open a file and have subsequent operations use this handle. But, I need to make sure that the same filesystem instance can be concurrently accessed via FUSE. Note that I can't use owned guards from the table and value locks to implement this, because if I put a table read lock guard in the handle I pass back to consumers, then no new files could be opened until it is dropped.

The crux of this problem appears to be the use of a lock for the entire table. If that could be eliminated then the lock guard for a table value could be put in a handle and new files could still be opened. I think this could be implemented if the hash table had a fixed size and internally used locking of its entries to synchronize access.

Is there already a crate which implements a type like this? Or, taking a step back, is there a better way to solve this problem?

[jessa0]

I have a couple suggestions which may or may not be applicable:

1. Clone the Arc<RwLock<TableValue>> to return a handle to a table value without holding a lock to the table. This might introduce a race where stale table values get used after they're removed or replaced in the table, however.

2. Use an ArcSwap<HashMap<...>> or similar and have writes clone the table, update it, and compare_and_swap it back into place.

[Michael-F-Bryan]

Have you thought about using a concurrent HashMap implementation instead of manually locking your maps? I know the dashmap crate is very popular.

dashmap

[KernelMC]

Something like dashmap is what I had in mind. But after reading through the code, it looks like dashmap not a good fit for my project because of it uses of blocking locks and the fact that deadlocks would be probable given my use-case.

You did point me in the right direction though. When I started searching for "concurrent hash maps" I found the leapfrog crate which contains a hash map which is lock-free when the size and alignment of both the hash table key and value types are powers of two and no greater than 8 bytes (on stable, see ::atomic::ops::match_atomic for more details). Since these requirements are satisfied in my case, this type will probably work really well for my application.

Thanks for the help!