use radix_tree for non-resident page tracking
Hi Rik,
The CLOCK-Pro page replacement is quite appealing, and I'd like to contribute an idea: How about store bookkeeping info of dropped pages in-place in radix_tree?
The slots in radix_tree_node can be used for bookkeeping data when the corresponding pages are dropped. When all pages in a radix_tree_node have been dropped, it is registered in an array/list for delayed reclaim.
It would be fast and simple:
- no cache-line pollution
- no extra lock (with Nick Piggin's great RCU improvement)
- ready to use lookup code
The memory footprint should be roughly the same, though with a whole word of space for each page ;)
It can not cover the swap space, which should be handled differently anyway, I guess.
Regards,
Wu Fengguang
Quoted 5 lines · WU Fengguang
Hi Rik,
The CLOCK-Pro page replacement is quite appealing, and I'd like to contribute an idea: How about store bookkeeping info of dropped pages in-place inradix_tree?
Quoted 8 lines
The slots in
radix_tree_nodecan be used for bookkeeping data when the corresponding pages are dropped. When all pages in aradix_tree_nodehave been dropped, it is registered in an array/list for delayed reclaim.It would be fast and simple:
- no cache-line pollution
- no extra lock (with Nick Piggin's great RCU improvement)
Just a note if you are looking into this - the last version of the radix-tree lockless readside patches I made public IIRC had some bugs in them which I have since fixed.
Thanks,
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 3 lines · WU Fengguang
The CLOCK-Pro page replacement is quite appealing, and I'd like to contribute an idea: How about store bookkeeping info of dropped pages in-place in
radix_tree?
How are you going to get the inter-reference distance this way?
I do not see how the radix tree provides you with the refault distance, which is needed to estimate the inter-reference distance.
Signature · 1 line
All Rights Reversed
Quoted 6 lines · Rik van Riel
How are you going to get the inter-reference distance this way?
I do not see how the radix tree provides you with the refault distance, which is needed to estimate the inter-reference distance.
How about taking down the current sum of `pgfree' in the slot?
Signature · 4 lines
WU Fengguang Dept. of Automation University of Science and Technology of China Hefei, Anhui
Re: [RFC] use radix_tree for non-resident page tracking\
Quoted 8 lines · WU Fengguang
Quoted 6 lines · Rik van Riel
How are you going to get the inter-reference distance this way?
I do not see how the radix tree provides you with the refault distance, which is needed to estimate the inter-reference distance.
How about taking down the current sum of `pgfree' in the slot?
Check this radix implementation
http://marc.theaimsgroup.com/?l=linux-mm&m=112387857203221&w=2
Using a hashtable is much faster though, needs measurement.
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 6 lines · Rik van Riel
Quoted 4 lines
Quoted 2 lines
How are you going to get the inter-reference distance this way?
How about taking down the current sum of `pgfree' in the slot?
Sounds like a good idea to me. Definately worth a try!
Thanks.
I now realized that counters in struct zone should be better candidates.
And the slots may be used to calculate the real inter-reference distances for dropped pages. For the present pages, we can either add entries to each page, or to radix_tree_node. I suspect the latter is enough because it should work well with sequential reads and sequential reads are the majority of page activities and the main source of flushing.
Signature · 4 lines
WU Fengguang Dept. of Automation University of Science and Technology of China Hefei, Anhui
Quoted 1 line · WU Fengguang
I now realized that counters in struct zone should be better candidates.
Probably not, since a logical page could be swapped out from one memory zone and paged back in to another.
Signature · 1 line
All Rights Reversed
Quoted 6 lines · Rik van Riel
Quoted 1 line · WU Fengguang
I now realized that counters in struct zone should be better candidates.
Probably not, since a logical page could be swapped out from one memory zone and paged back in to another.
I managed to keep the page aging of each zone balanced in the patch:
http://marc.theaimsgroup.com/?l=linux-kernel&m=112856866504476&w=2
Zones in nearby nodes are also made balanced somewhat.
The ages are currently measured by accumulated number of pages pushed into lru. I wonder that has the side effect of making other activities of each zone roughly balanced, too. It needs some testing. If so, we can just sum up counters of each zone in the current node.
Signature · 4 lines
WU Fengguang Dept. of Automation University of Science and Technology of China Hefei, Anhui