On Wed, 19 Nov 2003, Jean-Jacques Clar wrote:
> The heap in cache_pqueue is a max head, it always keep the object with
> the highest priority in its root position. The object with the highest
> priority is the one that is ejected when a new element has to be
> inserted when the cache is full (max nb of entities or size reached).
Right.
We could easily change cache_pqueue to be a minheap as you say, but then I
still don't think this would all be self-consistent, AND we'd then have a
priority queue where the item with the SMALLEST priority was the first one
to be dequeued, which I don't think makes sense.
> The return value of the set priority functions in mod_mem_cache.c:
> memcache_lru_algorithm(), memcache_gdsf_algorithm() and the
> get_priority() function have to be consistent to make sure the heap is
> bubbling and percolating correctly.
I think this is the ultimate problem. memcache_foo_algorithm() sets the
->priority to a positive value but then returns the negative of that
value. This means that cache_update() in cache_cache.c will think the old
and new priorities are negative, as they should be, and thus
cache_pq_change_priority() will correctly select the
bubble_up/percolate_down *direction*. But then when you get down into
those functions, they'll look up the priorities of the moving item and its
parents/children, which will be positive because the foo_algorithm
functions stored them that way and get_priority returns them without
negating them, and thus the bubble/percolate will never move the moving
item up or down at all. This is bad.
I think your patch will work, but wouldn't it be easier to just have the
memcache_foo_algorithm() functions set the ->priority to a negative value
and then return the value they actually stored, rather than setting it to
a positive value and then returning its negative?
Then anybody who either called get_priority() or just looked at the
->priority field would get the same answer.
Eg, we could do this:
----------------
static long memcache_lru_algorithm(long queue_clock, void *a)
{
cache_object_t *obj = (cache_object_t *)a;
mem_cache_object_t *mobj = obj->vobj;
if (mobj->priority == 0)
mobj->priority = -((long)(queue_clock + mobj->total_refs));
/*
* a 'proper' LRU function would just be
* mobj->priority = mobj->total_refs;
*/
return mobj->priority;
}
----------------
Instead of this:
----------------
static long memcache_lru_algorithm(long queue_clock, void *a)
{
cache_object_t *obj = (cache_object_t *)a;
mem_cache_object_t *mobj = obj->vobj;
if (mobj->priority == 0)
mobj->priority = ((long)(queue_clock + mobj->total_refs));
/*
* a 'proper' LRU function would just be
* mobj->priority = mobj->total_refs;
*/
return -1*mobj->priority;
}
----------------
Thoughts?
--Cliff
