"Machida, Hiroyuki" <[email protected]> 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 <[email protected]>
Signed-off-by: OGAWA Hirofumi <[email protected]>
---
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);
_
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
| |
 |