Change LruCache.map to hold a pointer, rather than owned LruEntry.

[emilHof]

This is meant as more of rough proposal, and I do not expect this to be merged in its current form. The aim of this pull request is to showcase a potential fix to an miri error that is inherent to the existing design.

Running the current master branch against cargo-miri, miri detects potential UB from an attempted retag of a SharedReadOnly pointer. The specific error follows:

Undefined Behavior: trying to retag from <237127> for SharedReadOnly permission at alloc100277[0x0],
but that tag does not exist in the borrow stack for this location

In particular, this results from the combination of the Hash trait implementation of KeyRef<K> which holds a *const K. In the case of LruEntry it acutally holds the key that *const K points to. The problem is that this pointer is created before the owned Box<LruEntry> is inserted into the map as KeyRef<K> is inserted alongside with it. This invalidates the SharedReadOnly borrow through *const K, as passing an owned value is a Unique retag. See also miri-docs.

To curb this issue, one possibility is saving *mut LruEntry's in map, rather than owned ones, which are constructed through Box::into_raw(Box::new(LruEntry::new(k, v))). To prevent memory leaks, pointers are turned back into Box<LruEntry> when popping entries. The Drop implementation follows a similar pattern.

When the original owned implementation is benched against the one that uses a *mut these are the results:

test tests::bench_owned_impl ... bench:     244,931 ns/iter (+/- 8,760)
test tests::bench_pointer_impl ... bench:     243,170 ns/iter (+/- 11,395)

This is of course a huge change and maybe one that is too drastic, considering this only fixes an experimental miri error. There may also be much simpler and cleaner fixes that I am not aware of with my limited knowledge. I am still a bit new to OS Rust, so general feedback and tips for improvement would already be much more than I could ask for!

[jeromefroe]

Hi @emilHof 👋 This is an interesting proposal and I think it could be worth it if it makes the code safer since the module has a fair bit of unsafe code which makes working on it more difficult.

[emilHof]

Hey @jeromefroe, thank you for taking your time to look over it! You are right, if it makes it safer and reduces unsafe, especially the one that could be unsound, then that would be ideal. Of course much of the reasoning for this change comes from miri which should probably be taken with a grain of salt.

The code has actually changed a slight bit since this pull request and now uses NonNull<LruEntry> to get some of the compiler optimizations that *mut LruEntry would probably miss out on!

Should I merge this change into the pull request, as it likely also contributes to more soundness in the overall code?

[jeromefroe]

Hey @emilHof! Thanks for updating the PR and sorry for the delayed response. The code looks good to me, especially with the use of NonNull. It looks there's a lint error on line 349 that is causing CI to fail though. The warning looks like a false positive to me since we're swapping two different values so I think we just need to add an allow attribute to disable the lint.

[emilHof]

Hi @jeromefroe, no worries at all, I am quite sure you are busy and this pull request really is not the most urgent thing haha! the lint error should be fixed now! :D

[jeromefroe]

This is awesome! Thanks for the contribution @emilHof!

[emilHof]

Of course ! thank you for taking time to look over it!! :D