I think we may be able to fix that one without making the
counter larger, it's silly overhead for such an extreme
case IMHO.
Perhaps it might be possible to just make the counter stick at it's
maximum, and when it's there we have an rbtree of external "large"
counters, keyed by page struct address.
So basically externalize counters that go over the maximally
representable value. In this way only the idiotic cases pay
the price.
On Sat, May 19, 2007 at 03:26:49PM -0700, David Miller wrote:
> I think we may be able to fix that one without making the
> counter larger, it's silly overhead for such an extreme
> case IMHO.
> Perhaps it might be possible to just make the counter stick at it's
> maximum, and when it's there we have an rbtree of external "large"
> counters, keyed by page struct address.
> So basically externalize counters that go over the maximally
> representable value. In this way only the idiotic cases pay
> the price.
This could be awkward with allocation requirements. How about an
open-addressed hash table? It can be made so large as to never
need to expand in advance with a very small constant factor space
overhead.
-- wli
From: William Lee Irwin III <[email protected]>
Date: Mon, 21 May 2007 04:37:47 -0700
> This could be awkward with allocation requirements. How about an
> open-addressed hash table? It can be made so large as to never
> need to expand in advance with a very small constant factor space
> overhead.
I was just thinking of a normal hash table with entries that
looked simply like:
struct page_big_count_hash {
struct page_big_count_hash *next; /* or list_head or hlist_head etc. */
struct page *key;
atomic64_t count;
};
> From: William Lee Irwin III <[email protected]>
> Date: Mon, 21 May 2007 04:37:47 -0700
>> This could be awkward with allocation requirements. How about an
>> open-addressed hash table? It can be made so large as to never
>> need to expand in advance with a very small constant factor space
>> overhead.
On Mon, May 21, 2007 at 04:50:31AM -0700, David Miller wrote:
> I was just thinking of a normal hash table with entries that
> looked simply like:
> struct page_big_count_hash {
> struct page_big_count_hash *next; /* or list_head or hlist_head etc. */
> struct page *key;
> atomic64_t count;
> };
I guess that could work with a static pool of hashtable elements like
mm/highmem.c uses, but the pointer links seem like such a waste of space.
It'll work, so no big deal. Maybe converting mm/highmem.c to hashing by
open addressing would be a simplification. Not worth disturbing working
code, though.
-- wli