thread-safe-lru icon indicating copy to clipboard operation
thread-safe-lru copied to clipboard

Incorrect `m_size` update

Open jy5275 opened this issue 3 years ago • 0 comments

Any thread reach https://github.com/tstarling/thread-safe-lru/blob/master/thread-safe-lru/lru-cache.h#L378 is an error, since that branch doesn't evict a node, and leads to m_size not following the actual size of the list. But in current code this error might happen. If the cache state is as follow (with three inserting threads):

m_maxSize = 3 msize = 3 Thread 1 execution - https://github.com/tstarling/thread-safe-lru/blob/master/thread-safe-lru/lru-cache.h#L301 (insert) Thread 2 execution - https://github.com/tstarling/thread-safe-lru/blob/master/thread-safe-lru/lru-cache.h#L301 (insert) Thread 3 execution - https://github.com/tstarling/thread-safe-lru/blob/master/thread-safe-lru/lru-cache.h#L301 (insert) List is empty

This state is possible, if the cache already has 3 items, then each of the 3 inserting threads find the exceeding size, then evicts one node, but yet has't insert its own node into list.

At this time, if another thread comes and tries to evict, it will find the list is empty then go to https://github.com/tstarling/thread-safe-lru/blob/master/thread-safe-lru/lru-cache.h#L378.

jy5275 avatar Mar 12 '22 09:03 jy5275