Messages in this thread Patch in this message | | | Subject | Re: [PATCH][FAT] FAT dirent scan with hin take #3 | From | OGAWA Hirofumi <> | Date | Fri, 02 Sep 2005 02:48:51 +0900 |
| |
"Machida, Hiroyuki" <machida@sm.sony.co.jp> writes:
> Once concern about global URL in general, it tends to be occupied > by specific pattern, like accesses from one process or to on dir. > It prevents to realize locality. > > I think it's better to have limitations like; > entries for same process would be limited to 2/3 > entries for same dir would be limited to 1/3
[...]
> Does this mean for each process recording last recent 16 > accesses to FAT file system ? If true, pid would be eliminated. > > I guess it's better to record nr_slots for this entry.
The fat_lookup_hint is one per task. And fat_lookup_hint is tracking the task's access. If access is sequential, it returns the hint, and if not, it returns 0. I made the dirty patch just for explaining what I said.
However, these lookup-hint approaches seems the hack after all.... Hhmmm... -- OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>
Signed-off-by: OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> ---
fs/fat/dir.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-- fs/fat/inode.c | 2 2 files changed, 164 insertions(+), 4 deletions(-)
diff -puN fs/fat/dir.c~fat_lookup-hint fs/fat/dir.c --- linux-2.6.13/fs/fat/dir.c~fat_lookup-hint 2005-09-02 01:04:47.000000000 +0900 +++ linux-2.6.13-hirofumi/fs/fat/dir.c 2005-09-02 01:06:50.000000000 +0900 @@ -22,6 +22,148 @@ #include <linux/buffer_head.h> #include <asm/uaccess.h> +#define FAT_LOOKUP_HINT_MAX 16 + +struct fat_lookup_hint { + struct list_head lru_list; + pid_t pid; + struct super_block *sb; + struct inode *dir; + loff_t last_pos; +#define HINT_STATE_RANDOM 1 + int state; +}; + +static spinlock_t fat_lookup_hint_lock = SPIN_LOCK_UNLOCKED; +static LIST_HEAD(fat_lookup_hint_head); +static int fat_lookup_hint_count; + +#if 0 +static int fat_lkup_hint_init(void) +{ + /* replace with kmem_cache */ + return 0; +} +#endif + +static inline struct fat_lookup_hint *fat_lkup_hint_alloc(void) +{ + struct fat_lookup_hint *hint; + + /* replace with kmem_cache */ + hint = kmalloc(sizeof(*hint), GFP_KERNEL); + if (hint) { + INIT_LIST_HEAD(&hint->lru_list); + hint->pid = 0; + hint->sb = NULL; + hint->dir = NULL; + hint->last_pos = 0; + } + return hint; +} + +static inline void fat_lkup_hint_free(struct fat_lookup_hint *hint) +{ + /* replace with kmem_cache */ + BUG_ON(!list_empty(&hint->lru_list)); + kfree(hint); +} + +void fat_lkup_hint_inval(struct inode *dir) +{ + struct super_block *sb = dir->i_sb; + struct fat_lookup_hint *hint, *n; + + spin_lock(&fat_lookup_hint_lock); + list_for_each_entry_safe(hint, n, &fat_lookup_hint_head, lru_list) { + if (hint->sb == sb && hint->dir == dir) { + list_del_init(&hint->lru_list); + fat_lkup_hint_free(hint); + fat_lookup_hint_count--; + } + } + spin_unlock(&fat_lookup_hint_lock); +} + +#define WIN_TOP (2 * MSDOS_SLOTS * sizeof(struct msdos_dir_entry)) +#define WIN_BOTTOM (5 * MSDOS_SLOTS * sizeof(struct msdos_dir_entry)) +static loff_t fat_lkup_hint_get(struct inode *dir) +{ + struct super_block *sb = dir->i_sb; + struct fat_lookup_hint *hint; + loff_t pos = 0; + + spin_lock(&fat_lookup_hint_lock); + list_for_each_entry(hint, &fat_lookup_hint_head, lru_list) { + if (hint->pid == current->pid && + hint->sb == sb && + hint->dir == dir) { + if (!(hint->state & HINT_STATE_RANDOM)) + pos = hint->last_pos; + break; + } + } + spin_unlock(&fat_lookup_hint_lock); + return max(0LL, pos - WIN_TOP); +} + +/* caller must hold dir->i_sem */ +static void fat_lkup_hint_add(struct inode *dir, loff_t pos) +{ + struct super_block *sb = dir->i_sb; + struct fat_lookup_hint *p, *hint = NULL; + loff_t win_start, win_end; + + spin_lock(&fat_lookup_hint_lock); + list_for_each_entry(p, &fat_lookup_hint_head, lru_list) { + if (p->pid == current->pid) { + hint = p; + break; + } + } + if (hint == NULL) { + if (fat_lookup_hint_count < FAT_LOOKUP_HINT_MAX) { + fat_lookup_hint_count++; + spin_unlock(&fat_lookup_hint_lock); + + hint = fat_lkup_hint_alloc(); + if (hint == NULL) + return; + spin_lock(&fat_lookup_hint_lock); + /* don't need to recheck hint */ + } else { + struct list_head *p = fat_lookup_hint_head.prev; + hint = list_entry(p, struct fat_lookup_hint, lru_list); + } + hint->pid = current->pid; + hint->sb = sb; + hint->dir = dir; + } + + if (hint->sb != sb || hint->dir != dir) { + hint->sb = sb; + hint->dir = dir; + hint->state |= HINT_STATE_RANDOM; + } else { + win_start = hint->last_pos - WIN_TOP; + win_end = hint->last_pos + WIN_BOTTOM; + if (win_start <= pos && pos <= win_end) { + hint->state &= ~HINT_STATE_RANDOM; + hint->last_pos = pos; + } else { + /* seems random access */ + hint->last_pos = pos; + hint->state |= HINT_STATE_RANDOM; + } + } + hint->last_pos = pos; + + /* update LRU */ + list_del(&hint->lru_list); + list_add(&hint->lru_list, &fat_lookup_hint_head); + spin_unlock(&fat_lookup_hint_lock); +} + static inline loff_t fat_make_i_pos(struct super_block *sb, struct buffer_head *bh, struct msdos_dir_entry *de) @@ -243,13 +385,23 @@ int fat_search_long(struct inode *inode, int utf8 = sbi->options.utf8; int anycase = (sbi->options.name_check != 's'); unsigned short opt_shortname = sbi->options.shortname; - loff_t cpos = 0; int chl, i, j, last_u, err; + loff_t cpos, start_off; + int reach_bottom = 0; + start_off = cpos = fat_lkup_hint_get(inode); err = -ENOENT; while(1) { - if (fat_get_entry(inode, &cpos, &bh, &de) == -1) +top: + if (reach_bottom && cpos >= start_off) goto EODir; + if (fat_get_entry(inode, &cpos, &bh, &de) == -1) { + if (!start_off) + goto EODir; + reach_bottom++; + cpos = 0; + continue; + } parse_record: nr_slots = 0; if (de->name[0] == DELETED_FLAG) @@ -298,8 +450,13 @@ parse_long: if (ds->id & 0x40) { unicode[offset + 13] = 0; } - if (fat_get_entry(inode, &cpos, &bh, &de) < 0) - goto EODir; + if (fat_get_entry(inode, &cpos, &bh, &de) < 0) { + if (!start_off) + goto EODir; + reach_bottom++; + cpos = 0; + goto top; + } if (slot == 0) break; ds = (struct msdos_dir_slot *) de; @@ -385,6 +542,7 @@ Found: sinfo->de = de; sinfo->bh = bh; sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de); + fat_lkup_hint_add(inode, sinfo->slot_off); err = 0; EODir: if (unicode) diff -puN fs/fat/inode.c~fat_lookup-hint fs/fat/inode.c --- linux-2.6.13/fs/fat/inode.c~fat_lookup-hint 2005-09-02 01:04:47.000000000 +0900 +++ linux-2.6.13-hirofumi/fs/fat/inode.c 2005-09-02 01:04:47.000000000 +0900 @@ -342,6 +342,7 @@ static void fat_delete_inode(struct inod clear_inode(inode); } +extern void fat_lkup_hint_inval(struct inode*); static void fat_clear_inode(struct inode *inode) { struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb); @@ -349,6 +350,7 @@ static void fat_clear_inode(struct inode if (is_bad_inode(inode)) return; lock_kernel(); + fat_lkup_hint_inval(inode); spin_lock(&sbi->inode_hash_lock); fat_cache_inval_inode(inode); hlist_del_init(&MSDOS_I(inode)->i_fat_hash); _ | |