From: Balbir Singh Subject: Re: [PATCH] Per-superblock unused dentry LRU lists. Date: Wed, 24 May 2006 10:32:14 +0530 Message-ID: <20060524050214.GB9639@in.ibm.com> References: <20060524012412.GB7412499@melbourne.sgi.com> Reply-To: balbir@in.ibm.com Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Return-path: Received: from e5.ny.us.ibm.com ([32.97.182.145]:34520 "EHLO e5.ny.us.ibm.com") by vger.kernel.org with ESMTP id S932589AbWEXFGb (ORCPT ); Wed, 24 May 2006 01:06:31 -0400 To: David Chinner Content-Disposition: inline In-Reply-To: <20060524012412.GB7412499@melbourne.sgi.com> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org On Wed, May 24, 2006 at 11:24:12AM +1000, David Chinner wrote: >=20 > As originally described in: >=20 > http://marc.theaimsgroup.com/?l=3Dlinux-kernel&m=3D114491661527656&w=3D= 2 >=20 > shrink_dcache_sb() becomes a severe bottleneck when the unused dentry > list becomes long and mounts and unmounts occur frequently on the > machine. >=20 > My initial attempt to solve the problem using per-node LRUs > (http://marc.theaimsgroup.com/?l=3Dlinux-kernel&m=3D114537118504917&w= =3D2) > fell apart under the complexity of locking required. This approach ca= n > probably be made to work in the long term, but we need a robust fix=20 > for now.... >=20 > The patch attached below is based on the suggestion made by Andrew > Morton here: >=20 > http://marc.theaimsgroup.com/?l=3Dlinux-fsdevel&m=3D114499224412427&w= =3D2 >=20 > This approach does not change any of the locking required, so avoids > the locking problems of the per-node lru implementation. >=20 > I've attempted to make reclaim fair by keeping track of the last supe= rblock > we pruned, and starting from the next on in the list each time. >=20 > Signed-off-by: Dave Chinner >=20 > --- > The patch has been stress tested on single and multiple filesystems, > using dbench, postmark and parallel create/unlink load tests. It has = also > been running on the problem server since last Saturday which currentl= y > has ~11 million cached dentries, and a dentry_cache slab size of ~27 = million > objects. I like the patch already :) > +static void > +dentry_lru_add(struct dentry *dentry) > +{ > + list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru); > + dentry_stat.nr_unused++; > +} > + > +static void > +dentry_lru_add_tail(struct dentry *dentry) > +{ > + list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru); > + dentry_stat.nr_unused++; > +} > + > +static void > +dentry_lru_del(struct dentry *dentry) > +{ > + if (!list_empty(&dentry->d_lru)) { > + list_del(&dentry->d_lru); > + dentry_stat.nr_unused--; > + } > +} > + > +static void > +dentry_lru_del_init(struct dentry *dentry) > +{ > + if (likely(!list_empty(&dentry->d_lru))) { > + list_del_init(&dentry->d_lru); > + dentry_stat.nr_unused--; > + } > +} > + I wonder if there should be per-sb count of number of used dentries. Th= is will help us while unmounting. Instead of passing count as NULL, the nu= mber of dentries in the super block can be passed. May be we should have per-dentry stats along with global statistics. > =20 > +/* > + * Shrink the dentry LRU on =C3=A6 given superblock. > + */ > +static void > +__shrink_dcache_sb(struct super_block *sb, int *count, int flags) > +{ > + struct dentry *dentry; > + int cnt =3D (count =3D=3D NULL) ? -1 : *count; This code seems hacky. Some comments please. Negative counters are gene= rally not good IMHO. This can be avoided by per-sb dentry stats (please see the comment above) > + > + spin_lock(&dcache_lock); > + while (!list_empty(&sb->s_dentry_lru) && cnt--) { > + dentry =3D list_entry(sb->s_dentry_lru.prev, > + struct dentry, d_lru); > + dentry_lru_del_init(dentry); > + BUG_ON(dentry->d_sb !=3D sb); > + prefetch(sb->s_dentry_lru.prev); > + > + spin_lock(&dentry->d_lock); > + /* > + * We found an inuse dentry which was not removed from > + * the LRU because of laziness during lookup. Do not free > + * it - just keep it off the LRU list. > + */ > + if (atomic_read(&dentry->d_count)) { > + spin_unlock(&dentry->d_lock); > + continue; > + } > + /* If the dentry matches the flags passed in, don't free it. > + * clear the flags and put it back on the LRU */ The comment does not follow coding style conventions. What do these fla= gs typically contain - DCACHE_REFERENCED? Could you clean up this comment please. > + if (flags && (dentry->d_flags & flags)) { > + dentry->d_flags &=3D ~flags; > + dentry_lru_add(dentry); > + spin_unlock(&dentry->d_lock); > + continue; > + } > + prune_one_dentry(dentry); > + } > + spin_unlock(&dcache_lock); > + if (count) > + *count =3D cnt; > +} > + > /** > * prune_dcache - shrink the dcache > * @count: number of entries to try and free > @@ -392,42 +456,44 @@ static inline void prune_one_dentry(stru > =20 > static void prune_dcache(int count) > { > - spin_lock(&dcache_lock); > - for (; count ; count--) { > - struct dentry *dentry; > - struct list_head *tmp; > - > - cond_resched_lock(&dcache_lock); > + struct super_block *sb; > + static struct super_block *sb_hand =3D NULL; > + int work_done =3D 0; > + > + spin_lock(&sb_lock); > + if (sb_hand =3D=3D NULL) > + sb_hand =3D sb_entry(super_blocks.next); > +restart: > + list_for_each_entry(sb, &super_blocks, s_list) { > + if (sb !=3D sb_hand) > + continue; > + /* Found the next superblock to work on. > + * Move the hand forwards so that parallel > + * pruners will work on a different sb */ > + work_done++; > + sb_hand =3D sb_entry(sb->s_list.next); > + sb->s_count++; > + spin_unlock(&sb_lock); > + > + /* we don't take the s_umount lock here because > + * because we can be called already holding a > + * write lock on a superblock */ You can use trylock. Please see the patches in -mm to fix the umount race. > + if (!list_empty(&sb->s_dentry_lru)) > + __shrink_dcache_sb(sb, &count, DCACHE_REFERENCED); > =20 > - tmp =3D dentry_unused.prev; > - if (tmp =3D=3D &dentry_unused) > + spin_lock(&sb_lock); > + if (__put_super_and_need_restart(sb) && count) > + goto restart; Comment please. > + if (count <=3D 0) > break; > - list_del_init(tmp); > - prefetch(dentry_unused.prev); > - dentry_stat.nr_unused--; > - dentry =3D list_entry(tmp, struct dentry, d_lru); > - > - spin_lock(&dentry->d_lock); > - /* > - * We found an inuse dentry which was not removed from > - * dentry_unused because of laziness during lookup. Do not free > - * it - just keep it off the dentry_unused list. > - */ > - if (atomic_read(&dentry->d_count)) { > - spin_unlock(&dentry->d_lock); > - continue; > - } > - /* If the dentry was recently referenced, don't free it. */ > - if (dentry->d_flags & DCACHE_REFERENCED) { > - dentry->d_flags &=3D ~DCACHE_REFERENCED; > - list_add(&dentry->d_lru, &dentry_unused); > - dentry_stat.nr_unused++; > - spin_unlock(&dentry->d_lock); > - continue; > - } > - prune_one_dentry(dentry); > } > - spin_unlock(&dcache_lock); > + if (!work_done) { > + /* sb_hand is stale. Start and the beginning of the > + * list again. */ Please fix the comment style > + sb_hand =3D sb_entry(super_blocks.next); > + goto restart; > + } > + spin_unlock(&sb_lock); > } > =20 > /* > @@ -454,41 +520,7 @@ static void prune_dcache(int count) > =20 > void shrink_dcache_sb(struct super_block * sb) > { > - struct list_head *tmp, *next; > - struct dentry *dentry; > - > - /* > - * Pass one ... move the dentries for the specified > - * superblock to the most recent end of the unused list. > - */ > - spin_lock(&dcache_lock); > - list_for_each_safe(tmp, next, &dentry_unused) { > - dentry =3D list_entry(tmp, struct dentry, d_lru); > - if (dentry->d_sb !=3D sb) > - continue; > - list_del(tmp); > - list_add(tmp, &dentry_unused); > - } > - > - /* > - * Pass two ... free the dentries for this superblock. > - */ > -repeat: > - list_for_each_safe(tmp, next, &dentry_unused) { > - dentry =3D list_entry(tmp, struct dentry, d_lru); > - if (dentry->d_sb !=3D sb) > - continue; > - dentry_stat.nr_unused--; > - list_del_init(tmp); > - spin_lock(&dentry->d_lock); > - if (atomic_read(&dentry->d_count)) { > - spin_unlock(&dentry->d_lock); > - continue; > - } > - prune_one_dentry(dentry); > - goto repeat; > - } > - spin_unlock(&dcache_lock); > + __shrink_dcache_sb(sb, NULL, 0); > } > =20 > /* > @@ -572,17 +604,13 @@ resume: > struct dentry *dentry =3D list_entry(tmp, struct dentry, d_u.d_chi= ld); > next =3D tmp->next; > =20 > - if (!list_empty(&dentry->d_lru)) { > - dentry_stat.nr_unused--; > - list_del_init(&dentry->d_lru); > - } > + dentry_lru_del_init(dentry); > /*=20 > * move only zero ref count dentries to the end=20 > * of the unused list for prune_dcache > */ > if (!atomic_read(&dentry->d_count)) { > - list_add(&dentry->d_lru, dentry_unused.prev); > - dentry_stat.nr_unused++; > + dentry_lru_add_tail(dentry); > found++; > } This should not be required with per super-block dentries. The only reason, I think we moved dentries to the tail is to club all entries from the sb together (to free them all at once). > =20 > @@ -657,18 +685,14 @@ void shrink_dcache_anon(struct hlist_hea > spin_lock(&dcache_lock); > hlist_for_each(lp, head) { > struct dentry *this =3D hlist_entry(lp, struct dentry, d_hash); > - if (!list_empty(&this->d_lru)) { > - dentry_stat.nr_unused--; > - list_del_init(&this->d_lru); > - } > =20 > + dentry_lru_del_init(this); > /*=20 > * move only zero ref count dentries to the end=20 > * of the unused list for prune_dcache > */ > if (!atomic_read(&this->d_count)) { > - list_add_tail(&this->d_lru, &dentry_unused); > - dentry_stat.nr_unused++; > + dentry_lru_add_tail(this); > found++; > } > } This might still be required. Do you want to split out the anonymous dc= ache entries as well? I am not sure what their superblock points to. Balbir Singh, Linux Technology Center, IBM Software Labs - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel= " in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html