per-page SLAB freeing (only dcache for now)
Subsystems (3)
PATCH 1/1 per-page SLAB freeing (only dcache for now)
Hi,
The SLAB reclaiming process works on per-object basis, out of pseudo-LRU ordering in the case of inode and dentry caches.
In a recent thread named "VM balancing issues on 2.6.13: dentry cache not getting shrunk enough" folks suggested that the SLAB reclaiming process should be changed to aim at entire SLAB containers, not single objects. This has been suggested several times in the past.
The following patch is an experimental attempt to do it for the dentry cache.
It works by checking all objects of a given SLAB once a single object is pruned in prune_dcache(). Once it has been confirmed that all objects on the target SLAB are freeable, proceeds to free them all.
Few issues with the patch:
a) Locking needs further verification to confirm correctness.
b) The addition of "i_am_alive" flag might not be necessary: I believe its possible to use kmembufctl to known about usage of objects within SLAB containers.
c) Freeing functions needs to be moved out of mm/slab.c in a proper place.
d) General beautification.
I don't see any fundamental problems with this approach, are there any? I'll clean it up and proceed to write the inode cache equivalent if there aren't.
Andrew commented about the requirement of a global lock for this reverse reclaiming - it seems to me that all that is necessary is correct synchronization between users and the reclaiming path (not necessarily a global lock though).
Or maybe I just dont get what he's talking about.
Anyway, dbench testing with 18 threads on 256Mb UP machine shows noticeable improvement (results in Mb/s):
1st run 2nd run avg stock 2.6.13 15.11 14.9 15.00 2.6.13+slabreclaim 16.22 15.5 15.86
Comments?
fs/dcache.c +18 -5
@@ -44,7 +44,8 @@ static seqlock_t rename_lock __cachelineEXPORT_SYMBOL (dcache_lock); -static kmem_cache_t *dentry_cache; +kmem_cache_t *dentry_cache; +#define DNAME_INLINE_LEN (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
@@ -84,6 +85,7 @@ static void d_callback(struct rcu_head **/ static void d_free (struct dentry *dentry) { + dentry->i_am_alive =0 ;if (dentry->d_op && dentry->d_op->d_release) dentry->d_op->d_release (dentry);call_rcu (&dentry->d_rcu, d_callback);
@@ -363,7 +365,7 @@ restart:* removed. * Called with dcache_lock, drops it and then regains. */ -static inline void prune_one_dentry (struct dentry * dentry) +inline void prune_one_dentry (struct dentry * dentry) {struct dentry * parent;
@@ -390,8 +392,11 @@ static inline void prune_one_dentry(stru* This function may fail to free any resources if * all the dentries are in use. */ + +int check_slab_page (void *); +int free_slab_page (void *); -static void prune_dcache(int count) +static void __prune_dcache(int count, int page_scan) spin_lock(&dcache_lock);for (; count ; count--) {
@@ -427,10 +432,17 @@ static void prune_dcache(int count)continue ; }prune_one_dentry (dentry); +if (page_scan &&check_slab_page (dentry)) +free_slab_page (dentry); }spin_unlock (&dcache_lock); } +static void prune_dcache (int count) +{ +__prune_dcache (count,1 ); +} +/* * Shrink the dcache for the specified super block. * This allows us to unmount a device without disturbing
@@ -642,7 +654,7 @@ void shrink_dcache_parent(struct dentryint found;while ((found =select_parent (parent)) !=0 ) -prune_dcache (found); +__prune_dcache (found,0 ); }/**
@@ -680,7 +692,7 @@ void shrink_dcache_anon(struct hlist_hea } }spin_unlock (&dcache_lock); -prune_dcache (found); +__prune_dcache (found,0 ); }while (found); }
@@ -755,6 +767,7 @@ struct dentry *d_alloc(struct dentry * pINIT_LIST_HEAD (&dentry->d_lru);INIT_LIST_HEAD (&dentry->d_subdirs);INIT_LIST_HEAD (&dentry->d_alias); + dentry->i_am_alive =0xdeadbeef ;if (parent) { dentry->d_parent =dget (parent);
fs/inode.c +1 -1
@@ -97,7 +97,7 @@ DECLARE_MUTEX(iprune_sem);*/ struct inodes_stat_t inodes_stat; -static kmem_cache_t * inode_cachep; +kmem_cache_t * inode_cachep;static struct inode *alloc_inode (struct super_block *sb) {
include/linux/dcache.h +1 -0
@@ -106,6 +106,7 @@ struct dentry {struct hlist_node d_hash;/* lookup hash list */ int d_mounted;unsigned char d_iname[DNAME_INLINE_LEN_MIN ];/* small names */ +int i_am_alive; };struct dentry_operations {
mm/slab.c +255 -0
267 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 3 lines · Marcelo
I don't see any fundamental problems with this approach, are there any? I'll clean it up and proceed to write the inode cache equivalent if there aren't.
Hmm. I think this needs to be some generic functionality in the slab allocator. If the allocator determines that the number of entries in a page become reasonably low then call a special function provided at slab creation time to try to free up the leftover entries.
Something like
int slab_try_free(void *);
?
return true/false depending on success of attempt to free the entry.
This method may also be useful to attempt to migrate slab pages to different nodes. If such a method is available then one can try to free all entries in a page relying on their recreation on another node if they are needed again.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 11 lines · Christoph Lameter
Quoted 3 lines · Marcelo
I don't see any fundamental problems with this approach, are there any? I'll clean it up and proceed to write the inode cache equivalent if there aren't.
Hmm. I think this needs to be some generic functionality in the slab allocator. If the allocator determines that the number of entries in a page become reasonably low then call a special function provided at slab creation time to try to free up the leftover entries.
Quoted 7 lines
Something like
int
slab_try_free(void *);?
return true/false depending on success of attempt to free the entry.
I thought about having a mini-API for this such as "struct slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.
Problem is that locking involved into looking at the SLAB elements is cache specific (eg dcache_lock for the dcache, inode_lock for the icache, and so on), so making a generic function seems pretty tricky, ie. you need cache specific information in the generic function which is not so easily "generifiable", if there's such a word.
Quoted 4 lines
This method may also be useful to attempt to migrate slab pages to different nodes. If such a method is available then one can try to free all entries in a page relying on their recreation on another node if they are needed again.
Yep, haven't thought of that before, but it might be interesting to have NUMA migration of cache elements.
Additionaly one can try to migrate recently referenced elements, instead of freeing them, moving them to some partially used SLAB free slot (Martin suggested that on IRC).
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 8 lines · Marcelo
I thought about having a mini-API for this such as "struct
slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.Problem is that locking involved into looking at the SLAB elements is cache specific (eg
dcache_lockfor the dcache,inode_lockfor the icache, and so on), so making a generic function seems pretty tricky, ie. you need cache specific information in the generic function which is not so easily "generifiable", if there's such a word.
The locking could be done by the cache specific free function. If it cannot lock it can simply indicate tha the entry is not freeable.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 8 lines · Christoph Lameter
Quoted 4 lines · Marcelo
I thought about having a mini-API for this such as "struct
slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.
Which functions would be needed?
- lock_cache(): No more alive/dead changes
- objp_is_alive()
- objp_is_killable()
- objp_kill()
I think it would be simpler if the caller must mark the objects as alive/dead before/after calling kmem_cache_alloc/free: I don't think it's a good idea to add special case code and branches to the normal kmem_cache_alloc codepath. And especially: It would mean that kmem_cache_alloc must perform a slab lookup in each alloc call, this could be slow. The slab users could store the alive status somewhere in the object. And they could set the flag early, e.g. disable alive as soon as an object is put on the rcu aging list.
The tricky part is lock_cache: is it actually possible to really lock the dentry cache, or could RCU cause changes at any time.
--
Manfred
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Hi Manfred,
Quoted 12 lines · Manfred Spraul
Quoted 10 lines · Christoph Lameter
Quoted 6 lines · Marcelo
I thought about having a mini-API for this such as "struct
slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.
Quoted 5 lines
Which functions would be needed?
-lock_cache(): No more alive/dead changes
-objp_is_alive()
-objp_is_killable()
-objp_kill()
Yep something along that line. I'll come up with something more precise tomorrow.
Quoted 9 lines
I think it would be simpler if the caller must mark the objects as alive/dead before/after calling kmem_cache_alloc/free: I don't think it's a good idea to add special case code and branches to the normal
kmem_cache_alloccodepath. And especially: It would mean thatkmem_cache_allocmust perform a slab lookup in each alloc call, this could be slow.
The slab users could store the alive status somewhere in the object. And they could set the flag early, e.g. disable alive as soon as an object is put on the rcu aging list.
The "i_am_alive" flag purpose at the moment is to avoid interpreting uninitialized data (in the dentry cache, the reference counter is bogus in such case). It was just a quick hack to watch it work, it seemed to me it could be done within SLAB code.
This information ("liveness" of objects) is managed inside the SLAB generic code, and it seems to be available already through the kmembufctl array which is part of the management data, right?
Suppose there's no need for the cache specific functions to be aware of liveness, ie. its SLAB specific information.
Another issue is synchronization between multiple threads in this level of the reclaim path. Can be dealt with PageLock: if the bit is set, don't bother checking the page, someone else is already doing so.
You mention
Quoted 1 line
-
lock_cache(): No more alive/dead changes
With the PageLock bit, you can instruct kmem_cache_alloc() to skip partial but Locked pages (thus avoiding any object allocations within that page). Hum, what about higher order SLABs?
Well, kmem_cache_alloc() can be a little bit smarter at this point, since its already a slow path, no? Its refill time, per-CPU cache is exhausted...
As for dead changes (object deletion), they should only happen with the object specific lock held (dentry->d_lock in dcache's case). Looks safe.
Quoted 2 lines
The tricky part is
lock_cache: is it actually possible to really lock the dentry cache, or could RCU cause changes at any time.
dentry->d_lock is a per-object lock guaranteeing synch. between lookups and deletion. Lookup of dentries is lockfree, but not acquision of reference:
struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
{
...
rcu_read_lock();
hlist_for_each_rcu(node, head) {
struct dentry *dentry;
struct qstr *qstr;
dentry = hlist_entry(node, struct dentry, d_hash);
if (dentry->d_name.hash != hash)
continue;
if (dentry->d_parent != parent)
continue;
spin_lock(&dentry->d_lock);
/*
* Recheck the dentry after taking the lock - d_move may have
* changed things. Don't bother checking the hash because we're
* about to compare the whole name anyway.
*/
if (dentry->d_parent != parent)
goto next;Finding dependencies of "pinned" objects, walking the tree downwards in children's direction in dcache's case, is protected by dcache_lock at the moment. The inode cache might want to delete the dentry which pins the inode in memory.
Finally, I fail to see the requirement for a global lock as Andrew mentions, even though locking is tricky and must be carefully checked.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 39 lines · Marcelo Tosatti
Hi Manfred,
Quoted 16 lines · Manfred Spraul
Quoted 6 lines · Christoph Lameter
On Sat, 1 Oct 2005, Marcelo wrote:
Quoted 6 lines
Quoted 6 lines
I thought about having a mini-API for this such as "struct
slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.Quoted 7 lines
Which functions would be needed?
-lock_cache(): No more alive/dead changes
-objp_is_alive()
-objp_is_killable()
-objp_kill()Yep something along that line. I'll come up with something more precise tomorrow.
Quoted 4 lines
I think it would be simpler if the caller must mark the objects as alive/dead before/after calling kmem_cache_alloc/free: I don't think it's a good idea to add special case code and branches to the normal
kmem_cache_alloccodepath. And especially: It would mean thatkmem_cache_allocmust perform a slab lookup in each alloc call, this could be slow. The slab users could store the alive status somewhere in the object. And they could set the flag early, e.g. disable alive as soon as an object is put on the rcu aging list.
Quoted 11 lines
The "
i_am_alive" flag purpose at the moment is to avoid interpreting uninitialized data (in the dentry cache, the reference counter is bogus in such case). It was just a quick hack to watch it work, it seemed to me it could be done within SLAB code.This information ("liveness" of objects) is managed inside the SLAB generic code, and it seems to be available already through the kmembufctl array which is part of the management data, right?
Not really. The array is only updated when the free status reaches the slab structure, which is quite late.
kmem_cache_free
- puts the object into a per-cpu array. No locking at all, each cpu can only read it's own array.
- when that array is full, then it's put into a global array (->shared).
- when the global array is full, then the object is marked as free in the slab structure.
- when add objects from a slab are free, then the slab is placed on the free slab list
- when there is memory pressure, then the pages from the free slab list are reclaimed.
Quoted 5 lines
Suppose there's no need for the cache specific functions to be aware of liveness, ie. its SLAB specific information.
What about RCU? We have dying objects: Still alive, because someone might have a pointer to it, but already on the rcu list and will be released after the next quiescent state. slab can't know that.
Quoted 8 lines
Another issue is synchronization between multiple threads in this level of the reclaim path. Can be dealt with PageLock: if the bit is set, don't bother checking the page, someone else is already doing
so.You mention
Quoted 10 lines
Quoted 3 lines
-
lock_cache(): No more alive/dead changesWith the PageLock bit, you can instruct
kmem_cache_alloc()to skip partial but Locked pages (thus avoiding any object allocations within that page). Hum, what about higher order SLABs?
You have misunderstood my question: I was thinking about object dead/alive changes.
There are two questions: First figure out how many objects from a certain slab are alive. Then, if it's below a threshold, try to free them. With this approach, you need lock(), is_objp_alive(), release_objp().
Quoted 4 lines
Well,
kmem_cache_alloc()can be a little bit smarter at this point, since its already a slow path, no? Its refill time, per-CPU cache is exhausted...
Definitively. Fast path is only kmem_cache_alloc and kmem_cache_free. No global cache line writes in these functions. They were down to 1 conditional branch and 2-3 cachelines, One of them read-only, the other(s) are read/write, but per-cpu. I'm not sure how much changed with the NUMA patches, but the non-numa case should try to remain simple. And e.g. looking up the bufctl means an integer division. Just that instruction could nearly double the runtime of kmem_cache_free(). The shared_array part from cache_flusharray and cache_alloc_refill are partially fast path: If we slow that down, then it will affect packet routing. The rest is slow path.
--
Manfred
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 55 lines · Manfred Spraul
Quoted 53 lines · Marcelo Tosatti
Hi Manfred,
Quoted 18 lines · Manfred Spraul
Quoted 6 lines · Christoph Lameter
On Sat, 1 Oct 2005, Marcelo wrote:
Quoted 8 lines
Quoted 8 lines
I thought about having a mini-API for this such as "struct
slab_reclaim_ops" implemented by each reclaimable cache, invoked by a generic SLAB function.Quoted 7 lines
Which functions would be needed?
-lock_cache(): No more alive/dead changes
-objp_is_alive()
-objp_is_killable()
-objp_kill()Yep something along that line. I'll come up with something more precise tomorrow.
Quoted 11 lines
I think it would be simpler if the caller must mark the objects as alive/dead before/after calling kmem_cache_alloc/free: I don't think it's a good idea to add special case code and branches to the normal
kmem_cache_alloccodepath. And especially: It would mean thatkmem_cache_allocmust perform a slab lookup in each alloc call, this could be slow.
The slab users could store the alive status somewhere in the object. And they could set the flag early, e.g. disable alive as soon as an object is put on the rcu aging list.The "
i_am_alive" flag purpose at the moment is to avoid interpreting uninitialized data (in the dentry cache, the reference counter is bogus in such case). It was just a quick hack to watch it work, it seemed to me it could be done within SLAB code.
Quoted 8 lines
Quoted 6 lines
This information ("liveness" of objects) is managed inside the SLAB generic code, and it seems to be available already through the kmembufctl array which is part of the management data, right?
Not really. The array is only updated when the free status reaches the slab structure, which is quite late.
Thats fine, the usage information inside the array is only going to be used to avoid interpretation of uninitialized objects. Its safe to say that unallocated objects will have their corresponding kmembufctl array entry consistent (marked as freed) at all times, right?
Actual per-object live/dead information must reside inside the objp itself as you suggest, with guaranteed synchronization.
For the dcache its possible to use the D_UNHASHED flag (or some other field which describes validity).
Quoted 11 lines
kmem_cache_free
- puts the object into a per-cpu array. No locking at all, each cpu can only read it's own array.
- when that array is full, then it's put into a global array (->shared).
- when the global array is full, then the object is marked as free in the slab structure.
- when add objects from a slab are free, then the slab is placed on the free slab list
- when there is memory pressure, then the pages from the free slab list are reclaimed.
Quoted 8 lines
Quoted 5 lines
Suppose there's no need for the cache specific functions to be aware of liveness, ie. its SLAB specific information.
What about RCU? We have dying objects: Still alive, because someone might have a pointer to it, but already on the rcu list and will be released after the next quiescent state. slab can't know that.
Objects waiting for the next RCU quiescent state cannot have references attached, and can't be reused either. When they reach the RCU list they are already invalid (DCACHE_UNHASHED in dcache's case).
The only references they can have at this point is against the list_head fields.
Quoted 19 lines
Quoted 9 lines
Another issue is synchronization between multiple threads in this level of the reclaim path. Can be dealt with PageLock: if the bit is set, don't bother checking the page, someone else is already doing so.
You mention
Quoted 10 lines
Quoted 3 lines
-
lock_cache(): No more alive/dead changesWith the PageLock bit, you can instruct
kmem_cache_alloc()to skip partial but Locked pages (thus avoiding any object allocations within that page). Hum, what about higher order SLABs?
Quoted 5 lines
You have misunderstood my question: I was thinking about object dead/alive changes.
There are two questions: First figure out how many objects from a certain slab are alive. Then, if it's below a threshold, try to free them. With this approach, you needlock(),is_objp_alive(),release_objp().
I'm thinking over this, will be sending something soon.
Quoted 5 lines
Quoted 5 lines
Well,
kmem_cache_alloc()can be a little bit smarter at this point, since its already a slow path, no? Its refill time, per-CPU cache is exhausted...
Quoted 10 lines
Definitively. Fast path is only
kmem_cache_allocandkmem_cache_free. No global cache line writes in these functions. They were down to 1 conditional branch and 2-3 cachelines, One of them read-only, the other(s) are read/write, but per-cpu. I'm not sure how much changed with the NUMA patches, but the non-numa case should try to remain simple. And e.g. looking up the bufctl means an integer division. Just that instruction could nearly double the runtime ofkmem_cache_free(). Theshared_arraypart fromcache_flusharrayandcache_alloc_refillare partially fast path: If we slow that down, then it will affect packet routing. The rest is slow path.
OK fine, thanks for all your help up to now!
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Took it a while more than "tomorrow" but I have something.
Quoted 1 line
I'm thinking over this, will be sending something soon.
I'm testing the following which implements "slab_reclaim_ops" and dcache methods as discussed (inode, dquot, etc should follow).
It also addresses some problems Al Viro pointed with reference to the dcache.
Doing a battery of tests on it - need to come up with more detailed statistics (hit ratio on the caches and "freed objects/freed pages" ratios with different interesting workloads).
Comments?
fs/dcache.c +241 -6
@@ -44,7 +44,8 @@ static seqlock_t rename_lock __cachelineEXPORT_SYMBOL (dcache_lock); -static kmem_cache_t *dentry_cache; +kmem_cache_t *dentry_cache; +#define DNAME_INLINE_LEN (sizeof(struct dentry)-offsetof(struct dentry,d_iname))
@@ -84,6 +85,7 @@ static void d_callback(struct rcu_head **/ static void d_free (struct dentry *dentry) { + dentry->d_flags =0 ;if (dentry->d_op && dentry->d_op->d_release) dentry->d_op->d_release (dentry);call_rcu (&dentry->d_rcu, d_callback);
@@ -363,7 +365,7 @@ restart:* removed. * Called with dcache_lock, drops it and then regains. */ -static inline void prune_one_dentry (struct dentry * dentry) +inline void prune_one_dentry (struct dentry * dentry) {struct dentry * parent;
@@ -390,13 +392,17 @@ static inline void prune_one_dentry(stru* This function may fail to free any resources if * all the dentries are in use. */ + +unsigned long long check_slab_page (void *); +int free_slab_page (void *objp,unsigned long long bitmap); -static void prune_dcache (int count) +static void __prune_dcache (int count,int page_scan) {spin_lock (&dcache_lock);for (; count ; count--) {struct dentry *dentry;struct list_head *tmp; +unsigned long long bitmap;cond_resched_lock (&dcache_lock);
@@ -426,11 +432,238 @@ static void prune_dcache(int count)spin_unlock (&dentry->d_lock);continue ; } + +if (page_scan) { +/*XXX: dcache_lock guarantees dentry won't vanish?*/ +spin_unlock (&dentry->d_lock); +if ((bitmap =check_slab_page (dentry))) { +if (free_slab_page (dentry, bitmap)) +continue ; + } +spin_lock (&dentry->d_lock); +if (atomic_read (&dentry->d_count)) { +/* keep it off the dentry_unused list. */ +spin_unlock (&dentry->d_lock); +continue ; + } +/* if the aggregate freeing fails we proceed +* to free the single dentry as usual. +*/ + } +prune_one_dentry (dentry); }spin_unlock (&dcache_lock); } +static void prune_dcache (int count) +{ +__prune_dcache (count,1 ); +} + +static inline int dentry_negative (struct dentry *dentry) +{ +return (dentry->d_inode ==NULL ); +} + +#define MAX_CHILD_REAP 32 + +int dir_check_freeable (struct dentry *parent) +{ +struct dentry *this_parent = parent; +struct list_head *next; +unsigned int int_array[32 ]; +unsigned int *int_array_ptr = (unsigned int *)&int_array; +unsigned int nr_children, ret; + + ret = nr_children =0 ; +memset (&int_array,0 ,sizeof (int_array)); + +if (list_empty (&this_parent->d_subdirs)) +BUG (); +repeat: + next = this_parent->d_subdirs.next; +resume: +while (next != &this_parent->d_subdirs) { +struct list_head *tmp = next; + struct dentry *dentry = list_entry(tmp, struct dentry, d_child); + +if (!(virt_addr_valid (next))) +BUG (); + + next = tmp->next; + +if (!list_empty (&dentry->d_subdirs)) { + this_parent = dentry; +/* increase the counter */ + *int_array_ptr = *int_array_ptr+1 ; +/* move to next array position */ + int_array_ptr++; +if (int_array_ptr >= (unsigned int *)&int_array+(sizeof (int_array)/sizeof (int ))) +BUG (); + *int_array_ptr =0 ; + nr_children++; + goto repeat; + } +/* Pinned or negative dentry? */ +if (!atomic_read (&dentry->d_count) && !dentry_negative (dentry)) { + *int_array_ptr = *int_array_ptr+1 ; + nr_children++; + }else +/* unfreeable dentry, bail out */ + goto out; + } + +/* +* All done at this level ... ascend and resume the search. +*/ +if (this_parent != parent) { +unsigned int val = *int_array_ptr; +/* does this directory have any additional ref? */ +if (atomic_read (&this_parent->d_count) != val) +return 0 ; + int_array_ptr--; +if (int_array_ptr < (unsigned int *)&int_array) +BUG (); + + next = this_parent->d_child.next; + this_parent = this_parent->d_parent; + goto resume; + } + +if (int_array_ptr != (unsigned int *)&int_array) { +printk ("int array pointer differs: ptr:%p - &array:%p\n" , + int_array_ptr, &int_array); +BUG (); + } + +if (nr_children <MAX_CHILD_REAP ) +if (atomic_read (&parent->d_count) == *int_array_ptr) + ret =1 ; +out: +return ret; +} + +/* +* XXX: what are the consequences of acquiring the lock of +* a free object? Can some other codepath race and try to +* use the dentry assuming it is free while we "hold" the +* lock here? +* +* Since the reading of protected dentry->d_flags is performed +* locklessly, we might be reading stale data. +* +* Does it need a memory barrier to synchronize with d_free()'s +* DCACHE_INUSE assignment? +* +*/ +int dcache_objp_lock (void *obj) +{ +struct dentry *dentry = (struct dentry *)obj; + +if (((dentry->d_flags &DCACHE_INUSE ) ==DCACHE_INUSE )) { +spin_lock (&dentry->d_lock); +return 1 ; + } +return 0 ; +} + +int dcache_objp_unlock (void *obj) +{ +struct dentry *dentry = (struct dentry *)obj; +spin_unlock (&dentry->d_lock); +return 1 ; +} + +/* +* dcache_lock guarantees that dentry and children will not +* vanish under us. +*/ +int dcache_objp_is_freeable (void *obj) +{ +int ret =1 ; +struct dentry *dentry = (struct dentry *)obj; + +if (dentry->d_flags & (DCACHE_UNHASHED |DCACHE_DISCONNECTED )) +return 0 ; + +if (!((dentry->d_flags &DCACHE_INUSE ) ==DCACHE_INUSE )) +return 0 ; + +if (dentry_negative (dentry)) +return 0 ; + +if (atomic_read (&dentry->d_count)) { + ret =0 ; +if (!list_empty (&dentry->d_subdirs)) + ret =dir_check_freeable (dentry); + } +return ret; +} + +/* +* dentry_free_child - attempt to free children of a given dentry. +* Caller holds an additional reference to it which is released here. +*/ +int dentry_free_child (struct dentry *dentry) +{ +int ret =1 ; + +if (dentry->d_inode ==NULL ) +BUG (); + +if (!list_empty (&dentry->d_subdirs)) { +spin_unlock (&dcache_lock); +shrink_dcache_parent (dentry); +spin_lock (&dcache_lock); + } + +spin_lock (&dentry->d_lock); +atomic_dec (&dentry->d_count); +if (atomic_read (&dentry->d_count)) + ret =0 ; +return ret; +} + +int dcache_objp_release (void *obj) +{ +struct dentry *dentry = (struct dentry *)obj; +int ret =0 ; + +/* no additional references? nuke it */ +if (!atomic_read (&dentry->d_count) ) { +if (!list_empty (&dentry->d_lru)) { + dentry_stat.nr_unused--; +list_del_init (&dentry->d_lru); + } + ret =1 ; +prune_one_dentry (dentry); +/* otherwise attempt to free children */ + }else if (!list_empty (&dentry->d_subdirs)) { +/* grab a reference to guarantee dir won't vanish */ +/* XXX: Confirm it is OK to grab an additional ref. here. */ +atomic_inc (&dentry->d_count); +spin_unlock (&dentry->d_lock); +if (dentry_free_child (dentry)) { +if (!list_empty (&dentry->d_lru)) { + dentry_stat.nr_unused--; +list_del_init (&dentry->d_lru); + } + ret =1 ; +prune_one_dentry (dentry); + }else +spin_unlock (&dentry->d_lock); + } +return ret; +} + +struct slab_reclaim_ops dcache_reclaim_ops = { + .objp_is_freeable = dcache_objp_is_freeable, + .objp_release = dcache_objp_release, + .objp_lock = dcache_objp_lock, + .objp_unlock = dcache_objp_unlock, +}; +/* * Shrink the dcache for the specified super block. * This allows us to unmount a device without disturbing
@@ -642,7 +875,7 @@ void shrink_dcache_parent(struct dentryint found;while ((found =select_parent (parent)) !=0 ) -prune_dcache (found); +__prune_dcache (found,0 ); }/**
@@ -680,7 +913,7 @@ void shrink_dcache_anon(struct hlist_hea } }spin_unlock (&dcache_lock); -prune_dcache (found); +__prune_dcache (found,0 ); }while (found); }
@@ -742,7 +975,7 @@ struct dentry *d_alloc(struct dentry * p dname[name->len] =0 ;atomic_set (&dentry->d_count,1 ); - dentry->d_flags =DCACHE_UNHASHED ; + dentry->d_flags =DCACHE_UNHASHED |DCACHE_INUSE ;spin_lock_init (&dentry->d_lock); dentry->d_inode =NULL ; dentry->d_parent =NULL ;
@@ -1689,6 +1922,8 @@ static void __init dcache_init(unsignedset_shrinker (DEFAULT_SEEKS , shrink_dcache_memory); +slab_set_reclaim_ops (dentry_cache, &dcache_reclaim_ops); +/* Hash may have been set up in dcache_init_early */ if (!hashdist)return ;
fs/inode.c +1 -1
@@ -97,7 +97,7 @@ DECLARE_MUTEX(iprune_sem);*/ struct inodes_stat_t inodes_stat; -static kmem_cache_t * inode_cachep; +kmem_cache_t * inode_cachep;static struct inode *alloc_inode (struct super_block *sb) {
include/linux/dcache.h +1 -0
@@ -155,6 +155,7 @@ d_iput: no no no yes#define DCACHE_REFERENCED 0x0008/* Recently used, don't discard. */ #define DCACHE_UNHASHED 0x0010 +#define DCACHE_INUSE 0xdbca0000extern spinlock_t dcache_lock;
include/linux/slab.h +8 -0
@@ -76,6 +76,14 @@ struct cache_sizes {extern struct cache_sizes malloc_sizes[];extern void *__kmalloc (size_t ,unsigned int __nocast ); +struct slab_reclaim_ops { +int (*objp_is_freeable)(void *objp); +int (*objp_release)(void *objp); +int (*objp_lock)(void *objp); +int (*objp_unlock)(void *objp); +}; +extern int slab_set_reclaim_ops (kmem_cache_t *,struct slab_reclaim_ops *); +static inline void *kmalloc (size_t size,unsigned int __nocast flags) {if (__builtin_constant_p (size)) {
mm/slab.c +270 -13
335 lines not on this page · raw message
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 9 lines · Marcelo Tosatti
...
mm/slab.c +7
-0+unsigned long long slab_free_status (kmem_cache_t *cachep,struct slab *slabp) +{ +unsigned long long bitmap =0 ; +int i; + +if (cachep->num >sizeof (unsigned long long )*8 ) +BUG ();
mm/slab.c static void free_block(kmem_cache_t* cac · line 621
Quoted 10 lines
mm/slab.c +10
-0+ +spin_lock_irq (&cachep->spinlock); +for (i=0 ; i < cachep->num ; i++) { +if (slab_bufctl (slabp)[i] ==BUFCTL_INUSE ) +set_bit (i, (unsigned long *)&bitmap); + } +spin_unlock_irq (&cachep->spinlock); + +return bitmap; +}
What if there are more than 64 objects per page?
mm/slab.c static void free_block(kmem_cache_t* cac · line 659
Quoted 9 lines
mm/slab.c +9
-0+if (!ops) +BUG (); +if (!PageSlab (page)) +BUG (); +if (slabp->s_mem != (page_address (page) + slabp->colouroff)) +BUG (); + +if (PageLocked (page)) +return 0 ;
There's quite a lot of whitespace breakage btw.
It all seems rather complex.
What about simply compacting the cache by copying freeable dentries? Something like, in prune_one_dentry():
if (dcache occupancy < 90%) {
new_dentry = alloc_dentry()
*new_dentry = *dentry;
<fix stuff up>
free(dentry);
} else {
free(dentry)
}?
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 14 lines · Andrew Morton
Quoted 13 lines · Marcelo Tosatti
...
mm/slab.c +11
-0+unsigned long long slab_free_status (kmem_cache_t *cachep,struct slab *slabp) +{ +unsigned long long bitmap =0 ; +int i; + +if (cachep->num >sizeof (unsigned long long )*8 ) +BUG (); + +spin_lock_irq (&cachep->spinlock); +for (i=0 ; i < cachep->num ; i++) { +if (slab_bufctl (slabp)[i] ==BUFCTL_INUSE )
Quoted 8 lines
mm/slab.c static void free_block(kmem_cache_t* cac · line 621
Quoted 6 lines
mm/slab.c +6
-0+set_bit (i, (unsigned long *)&bitmap); + } +spin_unlock_irq (&cachep->spinlock); + +return bitmap; +}What if there are more than 64 objects per page?
the bitops usually work on bigger than wordsize things though..
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 14 lines · Andrew Morton
Quoted 13 lines · Marcelo Tosatti
...
mm/slab.c +11
-0+unsigned long long slab_free_status (kmem_cache_t *cachep,struct slab *slabp) +{ +unsigned long long bitmap =0 ; +int i; + +if (cachep->num >sizeof (unsigned long long )*8 ) +BUG (); + +spin_lock_irq (&cachep->spinlock); +for (i=0 ; i < cachep->num ; i++) { +if (slab_bufctl (slabp)[i] ==BUFCTL_INUSE )
Quoted 8 lines
mm/slab.c static void free_block(kmem_cache_t* cac · line 621
Quoted 6 lines
mm/slab.c +6
-0+set_bit (i, (unsigned long *)&bitmap); + } +spin_unlock_irq (&cachep->spinlock); + +return bitmap; +}What if there are more than 64 objects per page?
The current worst case is 16k pagesize (IA64) and one cacheline sized objects (128 bytes) (hmm.. could even be smaller if the arch does overrride SLAB_HWCACHE_ALIGN) yielding a maximum of 128 entries per page.
There are been versions of Linux for IA64 out there with 64k pagesize on IA64 and there is the possibility that we need to switch to 64k as a standard next year when we may have single OS images running with more than 16TB Ram.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
ia64 page size (was Re: [PATCH] per-page SLAB freeing (only dcache for now))
Quoted 4 lines · Christoph Lameter
There are been versions of Linux for IA64 out there with 64k pagesize on IA64 and there is the possibility that we need to switch to 64k as a standard next year when we may have single OS images running with more than 16TB Ram.
it's a kernel config option, and it has to remain that way; the pagesize is a userspace visible property and although apps aren't supposed to care.. some do. So Distros that use 16kb right now (the RH ones) will need to keep 16Kb pagesize...
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 4 lines · Christoph Lameter
The current worst case is 16k pagesize (IA64) and one cacheline sized objects (128 bytes) (hmm.. could even be smaller if the arch does overrride
SLAB_HWCACHE_ALIGN) yielding a maximum of 128 entries per page.
What about biovec-1? On i386 and 2.6.13 from Fedora, it contains 226 entries. And revoke_table contains 290 entries.
--
Manfred
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 10 lines · Manfred Spraul
Quoted 6 lines · Christoph Lameter
The current worst case is 16k pagesize (IA64) and one cacheline sized objects (128 bytes) (hmm.. could even be smaller if the arch does overrride
SLAB_HWCACHE_ALIGN) yielding a maximum of 128 entries per page.What about biovec-1? On i386 and 2.6.13 from Fedora, it contains 226 entries. And
revoke_tablecontains 290 entries.
Neither are reclaimable however, right:
[marcelo@logos linux-2.6.13]$ find . -type f -exec grep -l set_shrinker {} \; ./fs/dcache.c./fs/dquot.c./fs/inode.c./fs/mbcache.c./fs/xfs/linux-2.6/kmem.h
If the size of the bitmap for caching the slabbufctl data (which contains dead/alive information) ends up being a problem, its possible to:
- increase the bitmap size somehow
- drop the bitmap, acquiring the cache's spinlock and checking directly
Or as a last resort drop the slabbufctl optimization completly, using cache internal information to obtain dead/alive status.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Hi Andrew!
Quoted 14 lines · Andrew Morton
Quoted 13 lines · Marcelo Tosatti
...
mm/slab.c +11
-0+unsigned long long slab_free_status (kmem_cache_t *cachep,struct slab *slabp) +{ +unsigned long long bitmap =0 ; +int i; + +if (cachep->num >sizeof (unsigned long long )*8 ) +BUG (); + +spin_lock_irq (&cachep->spinlock); +for (i=0 ; i < cachep->num ; i++) { +if (slab_bufctl (slabp)[i] ==BUFCTL_INUSE )
Quoted 8 lines
mm/slab.c static void free_block(kmem_cache_t* cac · line 621
Quoted 6 lines
mm/slab.c +6
-0+set_bit (i, (unsigned long *)&bitmap); + } +spin_unlock_irq (&cachep->spinlock); + +return bitmap; +}What if there are more than 64 objects per page?
I don't think there are reclaimable caches with more than 64 objects per page at the moment, but if that happens to be the case we just need to use an appropriately larger bitmap as Arjan mentioned.
Quoted 11 lines
mm/slab.c static void free_block(kmem_cache_t* cac · line 659
Quoted 9 lines
mm/slab.c +9
-0+if (!ops) +BUG (); +if (!PageSlab (page)) +BUG (); +if (slabp->s_mem != (page_address (page) + slabp->colouroff)) +BUG (); + +if (PageLocked (page)) +return 0 ;There's quite a lot of whitespace breakage btw.
Sorry about that! Silly.
Quoted 1 line
It all seems rather complex.
Hiding the locking behind an API does not sound very pleasant to me, but other than that it seems quite straightforward...
What worries you?
Quoted 12 lines
What about simply compacting the cache by copying freeable dentries? Something like, in
prune_one_dentry():if (dcache occupancy < 90%) { new_dentry = alloc_dentry() *new_dentry = *dentry; <fix stuff up> free(dentry); } else { free(dentry) }
Quoted 1 line
?
Compacting the dcache sounds like a good thing to be done to help reducing fragmentation (and simpler), but it is complementary to the aggregate freeing of pages proposed.
The major issue I believe this patch tries to attack is that of unused list ordering. Sequential objects in the unused list are not necessarily ordered by their page container (actually, it is easy to come up with several reasons for them _not_ to be optimally ordered for reclaim, eg. multi-user/multi-task workloads).
Under such scenarios in which the unused list ordering is not close to "page container order", the VM might have to reclaim larger amounts of dentries "dumbfully" in the hope to make progress by freeing full pages. It completly lacks the knowledge that to make progress full pages are required.
Recently David Chinner reported a case on a very large mem box in which demonstrates the issue very clearly:
http://marc.theaimsgroup.com/?l=linux-mm&m=112674700612691&w=2
While compacting the cache as you suggest would certainly help his specific, the most effective measure seems to be free full pages immediately.
I will proceed with some testing this week, suggestions are welcome.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>