drcachesim LRU implementation fails to increment counters properly

Created by: EagleEyeKestreI

Describe the bug Hi all, I read https://github.com/DynamoRIO/dynamorio/blob/master/clients/drcachesim/simulator/cache_lru.cpp , and find LRU implement here doesn't match my knowledge...

Consider this scene, there is a four-associativity cache line, at first the counters of four lines are all 0: (the number following invalid means variable counter_ invalid 0 invalid 0 invalid 0 invalid 0 Then, cache line a enters, according to the logic in cache_lru.cpp, then it becomes: a 0 invalid 1 invalid 1 invalid 1 Then cache line b enters: a 1 b 0 invalid 2 invalid 2 Then comes a again, resulting a hit: (invalid counter is still 2 because https://github.com/DynamoRIO/dynamorio/blob/master/clients/drcachesim/simulator/cache_lru.cpp#L49 says if <= cnt then counter++) a 0 b 1 invalid 2 invalid 2 Then comes two other lines c and d, then the set becomes: a 2 b 2 c 1 d 0 Then comes line e, it will replace line a according code logic(a and b counter are both 2, and a line index is before b). But the last visit of line a is after line b in this scene, which obeys LRU

is this a bug or there's something I get wrong... Thx very much !

To Reproduce pass

Expected behavior I think in such case b should be replaced?

Screenshots or Pasted Text pass

Versions

• What version of DynamoRIO are you using? newest
• Does the latest build from https://github.com/DynamoRIO/dynamorio/releases solve the problem? no
• What operating system version are you running on? ("Windows 10" is not sufficient: give the release number.) doesn't matter, macOD
• Is your application 32-bit or 64-bit? 64-bit