I just finished looking at the code and came to the same conclusion Cliff. The patch looks like it would work correctly, but the extra multiplication by -1 was bothering me. The optimizer may remove it as a performance issue, but it is still confusing when looking at the code. I'd vote for your version below (foo_algo just sets it to the negated value and returns the value as is rather than negating the returns). I'd also add a comment in foo_algo where the negated value is stored to explain why it is negated.
Cliff Woolley wrote:
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
-- Paul J. Reder ----------------------------------------------------------- "The strength of the Constitution lies entirely in the determination of each citizen to defend it. Only if every single citizen feels duty bound to do his share in this defense are the constitutional rights secure." -- Albert Einstein
