Full_Name: Howard Chu Version: HEAD OS: URL: ftp://ftp.openldap.org/incoming/hyc-20070116.txt Submission from: (NULL) (76.168.84.21) Submitted by: hyc
This is a rough implementation of the CLOCK-Pro cache replacement algorithm for back-bdb. It's based on the paper published here
http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs05-3.html
Currently the performance is not very good; the algorithm can invoke multiple scans of the Clock list and our lock overhead for those scans is too high. I'm not planning to do any more with this at the moment, just wanted to post it so it doesn't get lost, in case someone else is interested. I didn't want to commit it behind #ifdef's because that would get too messy.
This implementation deviates from the paper in two major respects: 1) it's possible for an EntryInfo node to get its Reference bit set even when the entry is not Resident. This happens very frequently, in cache_find_ndn. As such, EntryInfo nodes without an Entry, but that have been Referenced, do not get flushed by HANDtest.
2) Nodes can get their Reference bit cleared at many points during the Clock-Pro processing, so the bit is not a good indication of whether a node is currently in use and may be safely freed. So, elaborate lock checks are used at each point where the original algorithm would simply free a node (HANDcold, HANDtest).
It would be nice if our locking setup could be simplified. If someone else wants to jump in and clean it up, it may be worth committing down the road.