lkml.org 
[lkml]   [1997]   [Nov]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subjectsecond attempt at shrink_dcache_parent
    I've put together a new implementation of a shrink_dcache_parent()
    routine that's more than twice as fast as the first attempt. The
    increased efficiency is made possible by using the d_reftime field (as
    added by my dcache management patch) as a marker for the selected child
    dentries. This avoids having to check parentage twice.

    The code also tracks the latest dentry not selected in the first pass,
    and relies on the time ordering of the unused dentries so that it can
    stop scanning early. This should speed up the most common case of
    trimming a few dentries from one directory.

    The recent problems uncovered in nfs and msdos fs due to unpruned child
    dentries have made it more important that we have a prune_child_dentry
    operation, even if it's not optimally efficient. I think this patch is
    a reasonable approach given the current data structures, and if things
    change in the future we can just replace it.

    Regards,
    Bill--- fs/dcache.c.old Fri Oct 31 00:26:07 1997
    +++ fs/dcache.c Mon Nov 3 14:48:03 1997
    @@ -338,6 +349,120 @@
    }

    /*
    + * Check whether a dentry is a child of the parent.
    + */
    +static int d_is_child(struct dentry * dentry, struct dentry * parent)
    +{
    + int is_child = 1;
    + for ( ;; ) {
    + if (dentry == parent)
    + break;
    + if (dentry != dentry->d_parent) {
    + dentry = dentry->d_parent;
    + continue;
    + }
    + is_child = 0;
    + break;
    + }
    + return is_child;
    +}
    +
    +/*
    + * Prune the dcache to remove children of the parent dentry.
    + * The super block provides a quick no-go parenthood test.
    + *
    + * This implementation is similar to shrink_dcache_sb, but
    + * marks selected dentries to avoid repeating the costly
    + * parenthood test. In addition, it tracks the most recently
    + * unused dentry _not_ selected, to allow early termination.
    + *
    + * Subtle note: any dentries renamed to _become_ children of
    + * this parent after the selection pass will have d_reftime
    + * equal or later than max_time. (If they're on the unused
    + * list at all.)
    + */
    +void shrink_dcache_parent(struct dentry * parent)
    +{
    + struct list_head *tmp, *next;
    + struct super_block *sb = parent->d_sb;
    + struct dentry *dentry;
    + unsigned long max_time = 0;
    + int found = 0;
    +
    + /*
    + * Pass one ... move the dentries for the specified
    + * parent to the most recent end of the unused list,
    + * and mark them with a special value in d_reftime.
    + */
    + next = dentry_unused.next;
    + while (next != &dentry_unused) {
    + tmp = next;
    + next = tmp->next;
    + dentry = list_entry(tmp, struct dentry, d_lru);
    + if (dentry->d_sb != sb)
    + continue;
    + if (dentry->d_count)
    + continue;
    + if (!d_is_child(dentry, parent)) {
    + if (dentry->d_reftime > max_time)
    + max_time = dentry->d_reftime;
    + continue;
    + }
    + /*
    + * Mark the dentry with a special value in d_reftime.
    + */
    + dentry->d_reftime = 0;
    + list_del(tmp);
    + list_add(tmp, &dentry_unused);
    + found++;
    + }
    +#ifdef DCACHE_DEBUG
    +printk("shrink_dcache_parent: %s/%s found %d, max=%lu\n",
    +parent->d_parent->d_name.name, parent->d_name.name, found, max_time);
    +#endif
    + if (!found)
    + goto out;
    +
    + /*
    + * Pass two ... free the dentries for this parent.
    + * We don't need to retest dentries marked with the
    + * special time or those earlier than max_time.
    + */
    +repeat:
    + next = dentry_unused.next;
    + while (next != &dentry_unused) {
    + tmp = next;
    + next = tmp->next;
    + dentry = list_entry(tmp, struct dentry, d_lru);
    + if (dentry->d_sb != sb)
    + continue;
    + if (dentry->d_count)
    + continue;
    + /*
    + * If d_reftime is non-zero, we have to check parenthood.
    + * But if it's strictly earlier than max_time, we're done.
    + */
    + if (dentry->d_reftime != 0) {
    + if (dentry->d_reftime < max_time) {
    +#ifdef DCACHE_DEBUG
    +printk("shrink_dcache_parent: %s/%s time %lu < %lu\n",
    +dentry->d_parent->d_name.name,dentry->d_name.name,dentry->d_reftime,max_time);
    +#endif
    + break;
    + }
    + if (!d_is_child(dentry, parent))
    + continue;
    + }
    + dentry_stat.nr_unused--;
    + list_del(tmp);
    + INIT_LIST_HEAD(tmp);
    + prune_one_dentry(dentry);
    + goto repeat;
    + }
    +out:
    + return;
    +}
    +/*
    * This is called from do_try_to_free_page() to indicate
    * that we should reduce the dcache and inode cache memory.
    */
    \
     
     \ /
      Last update: 2005-03-22 13:40    [W:0.033 / U:148.776 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site