jeromefroe / lru-rs Goto Github PK

cargo build --features nightly
   Compiling lru v0.7.6 (/Users/tianyizhuang/Projects/lru-rs)
error[E0277]: the trait bound `K: NotKeyRef` is not satisfied
    --> src/lib.rs:481:38
     |
481  |         if let Some(node) = self.map.get_mut(&k) {
     |                                      ^^^^^^^ the trait `NotKeyRef` is not implemented for `K`
     |
note: required because of the requirements on the impl of `Borrow<K>` for `KeyRef<K>`
    --> src/lib.rs:116:12
     |
116  | impl<K, D> Borrow<D> for KeyRef<K>
     |            ^^^^^^^^^     ^^^^^^^^^
note: required by a bound in `HashMap::<K, V, S, A>::get_mut`
    --> /Users/tianyizhuang/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.11.2/src/map.rs:1080:12
     |
1080 |         K: Borrow<Q>,
     |            ^^^^^^^^^ required by this bound in `HashMap::<K, V, S, A>::get_mut`
help: consider further restricting this bound
     |
224  | impl<K: Hash + Eq + NotKeyRef, V, S: BuildHasher> LruCache<K, V, S> {
     |                   +++++++++++

For more information about this error, try `rustc --explain E0277`.
error: could not compile `lru` due to previous error

Is the feature still working? Should we remove it? I'd like to submit a PR.

I'm trying to implement LRU cache in Iron with persistent. It seems that LruCache type doesn't implement Send and Sync traits. Is there any way to implement this?

The current implementation boxes every key/value pair to obtain a stable address with which to construct an intrusive linked list. While investigating new designs following #70, I realized that this indirection and the associated reduction in locality can, in principle, be avoided.

The payload of a HashMap is already heap-allocated, and only moves when the container's capacity grows and it's rehashed. An intrusive linked list could therefore be soundly maintained by the HashMap implementation itself by including the links in the underlying raw table and rewriting them when copying them over in the course of a resize.

Unfortunately, I can't think of a way to implement this without this crate containing its own full hash table implementation; even hashbrown's RawTable API does not expose a way to customize the rehashing procedure, and I don't see a way to do it as a second pass. Maybe worth reaching out to @Amanieu or someone to see if there's a way hashbrown could enable this so an effective fork, and the resulting maintenance headache, isn't necessary?

The recent safety fix #128 is missing from the changelog.

Also, since it's a safety issue I'd argue the 0.7.3 should ideally be yanked and reported to RustSec.

Hello, not sure if this is an issue, or it is intended to work like this, or it's just my fault (I'm quite new to Rust), but I can't make lru work within a RwLock.

Here's a sample test I wrote:

#[test]
fn readLockTest(){
    let mut cache: LruCache<String,String> = LruCache::new(100);
    cache.put("test".to_string(), "test_value".to_string());
    let lock_cache = RwLock::new(cache);
    let rc = lock_cache.read();
    let res = rc.unwrap().get("test");
    assert_eq!(res.unwrap().as_str(), "test_value");
}

This fails to compile with this message:

error[E0596]: cannot borrow data in a dereference of `RwLockReadGuard<'_, LruCache<String, String>>` as mutable
   --> tests/cache_test.rs:295:15
    |
295 |     let res = rc.unwrap().get("test");
    |               ^^^^^^^^^^^ cannot borrow as mutable
    |
    = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `RwLockReadGuard<'_, LruCache<String, String>>`

Am I missing something?
Thank you

For a library I am working on I need to be able to create an LRU cache that allows me to use a modified FNV with better spatial locality for specifically Z-order curves for pointcloud data. This would require exposing the Hasher template parameter to the HashMap for the purposes of using with_hasher and the impl Default.

All this would require is adding another (defaulted) template parameter which is forwarded to the underlying HashMap and exposing some extra traits with the same bounds as the underlying HashMap. Would you be interested in me contributing this upstream?

Hi, I just wanted to update to 0.4.4, but realized that it introduced a severe issue, most probably due to #74. With this simple test program you can reproduce it (I tested it on a Mac):

cargo init lru_regression
cd lru_regression

src/main.rs:

fn main() -> std::io::Result<()> {
    loop {
        lru::LruCache::new(1).put(0, std::fs::File::open("Cargo.toml")?);
    }
}

Cargo.toml:

[package]
name = "lru_regression"
version = "0.1.0"
edition = "2018"

[dependencies]
lru = "=0.4.4"

cargo build --release
target/release/lru_regression

With lru = "=0.4.3" the program will basically run forever, with lru = "=0.4.4" you will run into Error: Os { code: 24, kind: Other, message: "Too many open files" } pretty soon. So it seems there is an issue in the new dropping code.

Hello @jeromefroe and sorry to bother you!

I have been looking for an LRU cache with O(1) operations and found your crate but decided as an exercise to implement my own: https://github.com/marmeladema/clru-rs

I wonder if you could take a quick look and tell me what you think of it?

As outlined in the README, the main differences are:

• Smaller amount of unsafe code.
• API closer to the standard HashMap collection which allows to lookup with Borrow-ed version of the key.

Technically, it might address some issues opened in this crate, while certainly introducing a lot new ones :-)
Namely:

• #72: only the key are put into an Rc and nothing else is boxed
• #85: the API being similar to HashMap it should be possible to use a &str to fetch a value with a String key

On the implementation side, it relies on a regular HashMap and a linked-list stored in a vector.

I understand its quite an unusual way to contact people, please forgive me.

Thank you in advance!

run this test

    #[test]
    fn test_lru_no_leaks(){

        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);

        struct DropCounter;

        impl Drop for DropCounter {
            fn drop(&mut self) {
                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
            }
        }

        let mut lru = LruCache::new(100);
        for i in 0..100 {
            lru.put(i,DropCounter{});
        }
        lru.clear();
        assert_eq!(100, DROP_COUNT.load(Ordering::SeqCst));

    }

result:

thread 'tests::test_lru_no_leaks' panicked at 'assertion failed: `(left == right)`:
Left:  100
Right: 0

When inserting structs with different keys with LruCache::put, after the capacity is exceeded the least recently used objects are forgotten rather than dropped which causes a memory leak for e.g. boxed structs. Manually calling pop_lru if len() == cap() before every put() works as a workaround.

Here's a minimal example demonstrating the broken behaviour (and it working as intended for same-key replacement):

use std::cell::*;
use lru::LruCache;

struct DropCounted<'c> {
    counter: &'c Cell<i32>,
    id: i32
}

impl<'c> Drop for DropCounted<'c> {
    fn drop(&mut self) {
        println!(" dropping #{}", self.id);
        let cnt = self.counter.get();
        self.counter.set(cnt + 1);
    }
}

fn main() {
    println!("Different key test");
    let counter = Cell::new(0);
    {
        let mut cache = LruCache::new(2);
        cache.put(1, DropCounted{counter: &counter, id: 0});println!("put 0 done");
        cache.put(2, DropCounted{counter: &counter, id: 1});println!("put 1 done");
        cache.put(3, DropCounted{counter: &counter, id: 2});println!("put 2 done");
        cache.put(4, DropCounted{counter: &counter, id: 3});println!("put 3 done");
        println!("Different keys: Drop count should be 2, is {}", counter.get());
    }
    println!("Different keys: Drop count should be 4, is {}", counter.get());
    println!("Same key test");
    counter.set(0);
    {
        let mut cache = LruCache::new(2);
        cache.put(1, DropCounted{counter: &counter, id: 0});println!("put 0 done");
        cache.put(1, DropCounted{counter: &counter, id: 1});println!("put 1 done");
        cache.put(1, DropCounted{counter: &counter, id: 2});println!("put 2 done");
        cache.put(1, DropCounted{counter: &counter, id: 3});println!("put 3 done");
        println!("Equal keys: Drop count should be 3, is {}", counter.get());
    }
    println!("Equal keys: Drop count should be 4, is {}", counter.get());
}

This code outputs the following with version 0.5 of this crate:

Different key test
put 0 done
put 1 done
put 2 done<<<<<<< 0 should be dropped here
put 3 done<<<<<<< 1 should be dropped here
Different keys: Drop count should be 2, is 0
 dropping #3
 dropping #2
Different keys: Drop count should be 4, is 2
Same key test
put 0 done
 dropping #0
put 1 done
 dropping #1
put 2 done
 dropping #2 << drop working as intended
put 3 done
Equal keys: Drop count should be 3, is 3
 dropping #3
Equal keys: Drop count should be 4, is 4

Today, the core data structure is a hash-map of LruEntries keyed by key refs

struct LruEntry<K, V> {
    key: mem::MaybeUninit<K>,
    val: mem::MaybeUninit<V>,
    prev: *mut LruEntry<K, V>,
    next: *mut LruEntry<K, V>,
}

struct Lru {
  map: HashMap<KeyRef<K>, Box<LruEntry<K, V>>, S>,
}

Essentially, the data strored here has this shape: HashMap<&K, (K, V)>. That is, it's a hash map which stores objects, where the key is the part of the object itself. THe current implementation is less efficient than it could have been, because we effectively store the K twice (once as a part of (K, V), and once as a &K). A more efficient impl would be HashSet<Entry<K, V>>, where entry is defined as follows:

struct Entry<K, V> { key: K, value: V}
impl<K, V> Borrow<K> for Entry<K, V> {}

Here's a playground that shows the pattern: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=bc60814a14a353784d3ba8c89c2cc109

LruCache isn't quite a drop-in replacement for HashMap for me, as I'm using HashMap<String, i64>. For this type, .get("some &str") works. This avoids the copy/allocation of to_string().

For LruCache, you instead get this error:

    |
103 |     if let Some(id) = cache.get(val) {
    |                                 ^^^ expected struct `std::string::String`, found str
    |
    = note: expected type `&std::string::String`
               found type `&str`

I had a go at changing the code to be more like HashMap's (and take a Borrow), but I got lost. Here's my thoughts: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0e81344c5da15c2b7c5f24e3135e7551

The issue is the KeyRef, where a KeyRef<String> isn't similar enough to a KeyRef<str>. I believe a String is only similar-enough to a str due to pointer abuse, eventually inside:

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
    &*(v as *const [u8] as *const str)
}

The same construct appears inside e.g. PathBuf -> Path's implementation. 😱

Can anyone think of a way to make this work?

use mem::MaybeUninit instead to make miri happy.

Currently, get_or_insert expects a Fn, but only calls it once (as expected). I have a case where if an item isn't found in the cache, it gets read from a file. Reading requires mutation (of the cursor), but lru-rs currently restricts closures to Fn, blocking functions that take a &mut self. Is there any reason for this? Can this be turned into FnMut or even FnOnce?

I created a Lru instance with size of 1M and set 5M records. I was able to dump 4.9M+ keys using iterators.

1. Does this implementation restrict the number of elements based on the initial size?
2. Does iterator retrieve expired records as well?
3. When we iterate over all key/val, what order does it return? MRU or LRU ?

It seems it's not possible to call .get with a &str if the cache is of type LruCache<String, T>.

Right now the only thing I was able to use to get it working is to call to_string for the &str parameter, then call .get with the reference of this string value.

Is there some trick that would allow me to use .get with &str if the key type is String?

Version: 0.5.1

It would be good to have the ability to export keys so the cache can be warmup at startup.
I am using iter to get all the keys from LRU but requires an extended period of mutex lock which would impact clients.

Is there any way to export keys with minimal locking duration?

I'm using a shared LRU cache in my crate, and I ran into this weird issue. I'm not sure if I'm stupid, Rust is stupid, or there is some error with the crate.

I would expect this code to either error out, panic, or work. But it just hangs.

let my_arc = Arc::new(Mutex::new(lru::LruCache::new(1024)));

let local_arc = my_arc.clone()

let data = local_arc.lock().unwrap().get("my_key".to_string());

My guess is that local_arc.lock().unwrap() is returning a non mutable reference, and Rust is not seeing that it should be and freaks out. Converting the above code to the following works:

let my_arc = Arc::new(Mutex::new(lru::LruCache::new(1024)));

let local_arc = my_arc.clone()

let mut handle = local_arc.lock().unwrap();
let data = handle.get("my_key".to_string());

I assume I should have done .get_mut() vs .lock() but I am still wondering if the lack of compiler freakout is the result of Rust being stupid, or something your crate is not doing. I looked at your code and it looks fine, so I'm not sure.

This commit (2663a80) included in the latest 0.6.6 release bumps the version of hashbrown from 0.9 to 0.11, which bumps the version of ahash from 0.4 to 0.7, which in turn adds a dependency on libc for linux targets by pulling in getrandom.

The x86_64-unknown-linux-sgx target (created by teaclave) has a custom version of libc called sgx_libc and just replacing the package that ahash uses doesn't resolve the issue as they are different versions of libc which are incompatible (it looks like ahash is trying to use symbols that are not available in sgx_libc).

I understand that you are not the developer of these dependencies, but the commit linked above means that i cannot use that latest version of lru-rs in my project. I think that adding a few feature flags to ahash and hashbrown can help resolve this issue.

Thank you for your time if you look into it!

A common operation for a cache is to search for an element and insert it if it's missing before returning a reference to the element. This shouldn't require hashing the key twice three times.

Can we pass the key as a reference and copy/clone if needed?

Looking at the below code, if a key already exists, we override the value. We don't have to clone the key which will save copying of the key data.

https://github.com/jeromefroe/lru-rs/blob/master/src/lib.rs#L195

https://github.com/jeromefroe/lru-rs/blob/master/src/lib.rs#L222-L223 uses MaybeUninit in a way that is exactly equivalent to the old mem::uninitialized which was deprecated for being practically always unsound. The correct way to use MaybeUninit is to never call assume_init until you have written a legal value to it. In the linked section of code, values of type K and V are obtained from uninitialized memory; these values might have types like &'static [u8] or ! for which this operation is insta-UB, for example.

Hi, do you think it would be possible to change the capacity of the cache at runtime?

Sort of like HashMap::remove_entry.

v0.7x had better ergonomics if you want to optionally disable the cache. That's not possible anymore with NonZeroUsize, now you would need extra code for that use case.

I need a LRU cache that limits the number of items by memory usage. Since I'm storing just Vec items, I'm planning a simple wrapper around LruCache to solve my problem on the short term.

But then I started thinking about creating a more generic solution, and started thinking about a special trait to calculate the size of the object. Then I thought "this may already exist", and voila, I found this crate: https://crates.io/crates/memory-lru

Reading their code gave me the insight that we must think what to do when a value in the cache is modified (since its size may change), which they solved by providing a function which gets another function as argument in which the value is modified, so that they can know when the values was mutated and its size needs to be recalculated.

I also found this issue discussing something similar: #32

But I think we can do better. I thought about creating some sort of "Lock" object returned on the "get" function which would trigger a recalculation of the value's size when dropped, that way we can safely access and mutate values in the cache.

I also thought that the "MemorySize" trait could be implemented for primitives and common std structs (like Vec), and we could also provide a macro to derive this trait for structs containing values that already have the MemorySize trait.

Anyway, I'm thinking about creating a pull request implementing these features, would that be a welcomed feature?

One thing I'm still not sure about is: should we create a wrapper around LruCache, or try to implement this directly for LruCache (which I'm not even sure is possible without breaking compatibility with how it works right now)? I'm leaning toward creating a wrapper (like the crate I mentioned above).

lru-rs is quite fast compared to many other LRU cache implementation. Is there any way to optimize in multi-threaded access? Maybe a read-write lock or reducing the locking scope.

Maybe something like CHashmap : https://docs.rs/chashmap/2.2.0/chashmap/

get and put takes mutable self so compiler forcers to use mutex lock in a multi-threaded environment even though Send and Sync are implemented.

cargo 1.50.0-nightly (d274fcf86 2020-12-07)

--> /Users/xxx/.cargo/registry/src/github.com-1ecc6299db9ec823/lru-0.6.1/src/lib.rs:60:58
|
60 | #![cfg_attr(feature = "nightly", feature(negative_impls, optin_builtin_traits))]
| ^^^^^^^^^^^^^^^^^^^^ feature has been removed
|
= note: renamed to auto_traits

error[E0658]: auto traits are experimental and possibly buggy
--> /Users/xxx/.cargo/registry/src/github.com-1ecc6299db9ec823/lru-0.6.1/src/lib.rs:110:1
|
110 | pub auto trait NotKeyRef {}
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: see issue #13231 rust-lang/rust#13231 for more information
= help: add #![feature(auto_traits)] to the crate attributes to enable

After running cargo update for a crate that I'm working on, I encountered a build failure due to the changes included in 0.1.18. This issue does not exist in 0.1.17. Patch updates should not be breaking API changes according to semver.

error[E0277]: the trait bound `lru::KeyRef<uuid::Uuid>: std::borrow::Borrow<&uuid::Uuid>` is not satisfied

1220 |         match cache.get_mut(&id) {
     |                     ^^^^^^^ the trait `std::borrow::Borrow<&uuid::Uuid>` is not implemented for `lru::KeyRef<uuid::Uuid>`
     |
     = help: the following implementations were found:
               <lru::KeyRef<K> as std::borrow::Borrow<K>>

error: aborting due to previous error

Hi, I'm very interested in this crate. I refactored the get and get_mut method after reading the code and submitted a PR ([#47]). Please help me review it if anyone has time.

Thanks!

Right now if I do cache.put("", ""), I have no idea if the key existed already and was updated. This information is available, and it would be easy to return the previous value to the caller if the key had already existed.

It enables this pattern:

if let Some(_) = cache.put("key", "value") {
  // the key was already in there
}

Whereas you would currently have to do this:

let value = cache.get("key");
if value.is_some() {
  // the key was already in there
}
cache.put("key", "value");

Which is pretty useful for anyone using this cache as a lookup table for things like duplication, etc.

Hi there,

I was using LruCache in a project that I regularly scan with Miri and I recieved the following report:

error: Undefined Behavior: type validation failed: encountered undefined pointer at .value.prev
    --> /home/william/.rustup/toolchains/nightly-2020-03-29-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/mem/maybe_uninit.rs:502:34
     |
502  |         ManuallyDrop::into_inner(self.value)
     |                                  ^^^^^^^^^^ type validation failed: encountered undefined pointer at .value.prev
     |
     = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
     = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
     = note: inside call to `std::mem::MaybeUninit::<lru::LruEntry<usize, usize>>::assume_init` at /home/william/.cargo/registry/src/github.com-1ecc6299db9ec823/lru-0.4.3/src/lib.rs:222:51
     = note: inside call to `lru::LruCache::<usize, usize>::construct` at /home/william/.cargo/registry/src/github.com-1ecc6299db9ec823/lru-0.4.3/src/lib.rs:183:9
note: inside call to `lru::LruCache::<usize, usize>::new` at src/cache/arc/mod.rs:391:21
    --> src/cache/arc/mod.rs:391:21
     |
391  |             tlocal: LruCache::new(self.read_max),
     |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

I'm wondering if this is an issue that you are aware of?

Thanks!

It would be nice to add a retain method, similar to what std::collection::HashMap and std::vec::Vec have.

I don't known why but it looks like get requires the argument has the same lifetime as it's key.

use lru::LruCache;
use std::collections::HashMap;

struct Store<'a> {
    index: HashMap<&'a str, String>,
    cache: LruCache<&'a str, String>,
}

impl<'a> Store<'a> {
    // can compile
    fn foo(&mut self, key: String) -> String {
        self.index.get(&key.as_str()).unwrap().to_owned()
    }
    // cannot compile
    fn bar(&mut self, key: String) -> String {
        self.cache.get(&key.as_str()).unwrap().to_owned()
    }
}

How can I get the method bar to compile?

Hey guys, I am thinking of forking egui (a pure reactive immediate gui library) to implement some caching capabilities.

See if I move the slider, everything has to update, even the Click each year button (where the red arrow is pointing to) which is a waste of CPU usage. What I wanted to do instead is if I move the slider, the slider only gets updated/redrawn, all the other elements don't redraw and remain static/cached.

I was wondering if I forked egui, would lru-rs crate would be appropriate for such use?

It would be good to have support to retrieve all the keys. My use-case is to persist all the keys so at startup, read the keys from DB and warm up the cache.

Is there any specific reason why LrUCache does not provide a peek_mut method?

We already have get, get_mut and peek, it would be nice to add the equivalent peek_mut method to return the mutable reference corresponding to the key in the cache or None if it is not present in the cache, without having to update the LRU list.

Please add a get_mut method, for getting mutable values out of the cache.

Hello,
Is there any way to restrict the max memory usage for LRU? E.g. I am expecting 100M key/value pair but value length varies and ends up killing the process when it exceeds available memory.

Is there any way to enforce configurable max memory usage even though LRU capacity is not filled?

May be allocator counter: https://doc.rust-lang.org/beta/std/alloc/struct.System.html

It would be nice with a LruCache::clear() that would remove all elements from it. Since there is no way to get a list of all keys in the cache there is no way to empty it except dropping it and creating a new cache.

Hi,

I am using this crate now and I think it performs really well. However, I am using it in a concurrent server, and I currently have to wrap in Arc<RwLock<..>>. It would be great if it was possible to plug in dashmap to make the LRU thread-safe. The best would be if it would be generic over key-value store, then even remote stores could be used. This would probably involve implementing a K-V trait for a few selected collections, or newtype for users who wish to use un-implemented external structures. What do you think?

Related to #21

I am running valgrind with a full leak check :

valgrind --leak-check=full --show-leak-kinds=all myExecutable

It reports reachable bytes that seem linked to the usage of LruCache:

==9046== 8 bytes in 1 blocks are still reachable in loss record 2 of 6
==9046==    at 0x483C855: malloc (vg_replace_malloc.c:380)
==9046==    by 0x19004C: once_cell::race::once_box::OnceBox<T>::get_or_init (in /mnt/c/Users/nhanus/dev/git/native/src/simulator/target/release/deps/checkpointing_test-279e8b44c56500c1)
==9046==    by 0x18F12F: lru::LruCache<K,V>::new (in /mnt/c/Users/nhanus/dev/git/native/src/simulator/target/release/deps/checkpointing_test-279e8b44c56500c1)

And

==9160== 64 bytes in 1 blocks are still reachable in loss record 4 of 6
==9160==    at 0x483C855: malloc (vg_replace_malloc.c:380)
==9160==    by 0x1954A4: <ahash::random_state::DefaultRandomSource as ahash::random_state::RandomSource>::get_fixed_seeds (in /mnt/c/Users/nhanus/dev/git/native/src/simulator/target/release/deps/checkpointing_test-279e8b44c56500c1)
==9160==    by 0x18F13C: lru::LruCache<K,V>::new (in /mnt/c/Users/nhanus/dev/git/native/src/simulator/target/release/deps/checkpointing_test-279e8b44c56500c1)

Could you please advise if I'm doing a misuse of the cache, or if there a real issue ? Thx

You should probably yank the accidentally-breaking 0.1.18 from crates.io. (:

Adding support for const new so that we can statically initialize the cache using a Mutex/Etc: Mutex::new(LruCache::new());

Use case:

let mut lru = LruCache::<String, String>::new(16);
let _ = lru.get("foo");

The compiler complains: the trait bound KeyRef<std::string::String>: Borrow<str> is not satisfied.

I'm using lru = "0.6"

I think I discovered use after free bug in lru crate. Code looked complicated for my skill level so better give you what I have before spending more time trying to understand everything. I tested this with both release 0.6.6 and git master (commit 09f68c6, same as 0.7.0 release?).

Consider this piece of code:

extern crate lru;

use lru::LruCache;

fn main() {
    let mut cache = LruCache::new(100);

    cache.put(1, String::from("Hello world"));
    cache.put(2, String::from("How are you?"));
    cache.put(3, String::from("It's a great day!"));

    for (key, value) in cache.iter() {
        cache.pop(key);
        println!("{}", value);
    }
}

This compiles fine, but when ran (in macOS) it crashed with segmentation fault:

% cargo run -q --example use-after-free
zsh: segmentation fault  cargo run -q --example use-after-free

The reason probably being that iterator gives us references to key and value, pop might remove and free the value, and then println tries to access the reference of value which is already dropped. However, I didn't take deep dive into lru source code yet so I'm not sure what pop actually does.

I ran this with Address Sanitizer (using git master) and got the following report:

% RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --example use-after-free
   Compiling libc v0.2.102
   Compiling version_check v0.9.3
   Compiling cfg-if v1.0.0
   Compiling once_cell v1.8.0
   Compiling stats_alloc v0.1.8
   Compiling scoped_threadpool v0.1.9
   Compiling ahash v0.7.4
   Compiling getrandom v0.2.3
   Compiling hashbrown v0.11.2
   Compiling lru v0.7.0 (/Users/oherrala/rust/lru-rs)
    Finished dev [unoptimized + debuginfo] target(s) in 9.21s
     Running `/tmp/rust/target/debug/examples/use-after-free`
=================================================================
==31235==ERROR: AddressSanitizer: heap-use-after-free on address 0x604000000490 at pc 0x00010c700792 bp 0x7ffee35376d0 sp 0x7ffee35376c8
READ of size 8 at 0x604000000490 thread T0
    #0 0x10c700791 in alloc::raw_vec::RawVec$LT$T$C$A$GT$::ptr::h5b52a5e22cadae0b+0x31 (use-after-free:x86_64+0x100039791)
    #1 0x10c7006c0 in alloc::vec::Vec$LT$T$C$A$GT$::as_ptr::ha2d9c9e7d714e8da+0x10 (use-after-free:x86_64+0x1000396c0)
    #2 0x10c7006f4 in _$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..ops..deref..Deref$GT$::deref::h6bb849d264bca999+0x14 (use-after-free:x86_64+0x1000396f4)
    #3 0x10c6f0ff0 in _$LT$alloc..string..String$u20$as$u20$core..ops..deref..Deref$GT$::deref::h7755ec760d24422c string.rs:2322
    #4 0x10c6f0fa8 in _$LT$alloc..string..String$u20$as$u20$core..fmt..Display$GT$::fmt::hca63d28c3617b69f string.rs:2137
    #5 0x10c6fb59b in _$LT$$RF$T$u20$as$u20$core..fmt..Display$GT$::fmt::haea6ded2ffff63ce mod.rs:2087
    #6 0x10c743e4a in core::fmt::write::h2d5ecb4b9764759c+0x1ca (use-after-free:x86_64+0x10007ce4a)
    #7 0x10c72caa2 in _$LT$$RF$std..io..stdio..Stdout$u20$as$u20$std..io..Write$GT$::write_fmt::hae817ec54eda9acf+0x72 (use-after-free:x86_64+0x100065aa2)
    #8 0x10c72d09d in std::io::stdio::_print::h47ad1a1323ba12e2+0x15d (use-after-free:x86_64+0x10006609d)
    #9 0x10c6f7359 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:14
    #10 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #11 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #12 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #13 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #14 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #15 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #16 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

0x604000000490 is located 0 bytes inside of 48-byte region [0x604000000490,0x6040000004c0)
freed by thread T0 here:
    #0 0x10c80eec9 in wrap_free+0xa9 (librustc-nightly_rt.asan.dylib:x86_64+0x46ec9)
    #1 0x10c6db87c in alloc::alloc::dealloc::hac7cca683dc65791 alloc.rs:105
    #2 0x10c6dba98 in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::deallocate::hdd1265caf1c71abf alloc.rs:242
    #3 0x10c6ed875 in alloc::alloc::box_free::h5953255913b50392 alloc.rs:336
    #4 0x10c6d7b8b in lru::LruCache$LT$K$C$V$C$S$GT$::pop::ha15bc84e57123038 lib.rs:547
    #5 0x10c6f71f7 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:13
    #6 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #7 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #8 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #9 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #10 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #11 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #12 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

previously allocated by thread T0 here:
    #0 0x10c80ed80 in wrap_malloc+0xa0 (librustc-nightly_rt.asan.dylib:x86_64+0x46d80)
    #1 0x10c6db05b in alloc::alloc::alloc::h0f9b323acc874539 alloc.rs:87
    #2 0x10c6db328 in alloc::alloc::Global::alloc_impl::ha5c4a44f32d2adaf alloc.rs:169
    #3 0x10c6dbdb1 in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::allocate::h402423fe20c59713 alloc.rs:229
    #4 0x10c6dad31 in alloc::alloc::exchange_malloc::ha89e8e0f96da4557 alloc.rs:318
    #5 0x10c6d8b36 in lru::LruCache$LT$K$C$V$C$S$GT$::put::h1d91d7e9e745a7be lib.rs:326
    #6 0x10c6f6f86 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:10
    #7 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #8 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #9 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #10 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #11 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #12 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #13 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

SUMMARY: AddressSanitizer: heap-use-after-free (use-after-free:x86_64+0x100039791) in alloc::raw_vec::RawVec$LT$T$C$A$GT$::ptr::h5b52a5e22cadae0b+0x31
Shadow bytes around the buggy address:
  0x1c0800000040: fa fa 00 00 00 00 00 07 fa fa 00 00 00 00 00 00
  0x1c0800000050: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
  0x1c0800000060: fa fa 00 00 00 00 00 05 fa fa 00 00 00 00 00 00
  0x1c0800000070: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
  0x1c0800000080: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
=>0x1c0800000090: fa fa[fd]fd fd fd fd fd fa fa fa fa fa fa fa fa
  0x1c08000000a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==31235==ABORTING
zsh: abort      RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --example use-after-free

I'd like to be able to wrap the LRU and implement a custom eviction policy, that will protect certain elements from removal but still make them part of the LRU ordering.
For that I need something like a peek_lru method, that behaves like a peek for the least-recently used element (consistent with existing peek and pop_lru methods).
Then I can implement updates to the LRU by checking if we are at capacity, if so peek if the key is not in the LRU cache and check if the LRU element is protected, if so error out, otherwise proceed with setting.

Basically I want to use LruCache with infinite capacity and unit values just to govern cache eviction policy, and use a criterion other than element count to decide when to/how many elements to remove. This requires a constructor that initializes with cap: usize::MAX and HashMap::default() and a method like this:

    pub fn pop_lru(&mut self) -> Option<(K, V)> {
        let key = KeyRef {
            k: unsafe { &(*(*self.tail).prev).key },
        };
        let mut node = self.map.remove(&key)?;

        let node_ptr: *mut LruEntry<K, V> = &mut *node;
        self.detach(node_ptr);

        // Required because of https://github.com/rust-lang/rust/issues/28536
        let node = *node;
        let LruEntry { key, val, .. } = node;
        Some((key, val))
    }

My unsafe Rust is not super strong, so this might be off.

For now I just copied the lib into my project but I'll add some tests and doc comments and make a pull request at some point if you think this is worth merging.

Hey!

Anyway you can show me how to use this cache with lazy_static? I'd like to access it from multiple threads. A working example would be amazing! Thank you