(ITS#4807) CLOCK-Pro cache replacement

[hyc@OpenLDAP.org]

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.