diren scan profiling report

@@ -255,6 +255,8 @@ struct msdos_inode_info {
 	/* for avoiding the race between fat_free() and fat_get_cluster() */
 	unsigned int cache_valid_id;
 
+	struct semaphore *scan_lock;	/* lock for dirscan hints */
+	loff_t *scan_hints;	/* dirscan hints */
 	loff_t mmu_private;
 	int i_start;		/* first cluster or 0 */
 	int i_logstart;		/* logical first cluster */

175 lines not on this page · raw message

@@ -242,6 +242,8 @@ static int fat_fill_inode(struct inode *
 	inode->i_version++;
 	inode->i_generation = get_seconds();
 
+	init_MUTEX(&(MSDOS_I(inode)->scan_lock);
+	MSDOS_I(inode)->scan_hints = 0;
 	if ((de->attr & ATTR_DIR) && !IS_FREE(de->name)) {
 		inode->i_generation &= ~1;
 		inode->i_mode = MSDOS_MKMODE(de->attr,

@@ -345,6 +347,15 @@ static void fat_delete_inode(struct inod
 static void fat_clear_inode(struct inode *inode)
 {
 	struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
+	void *hints;
+
+	down(&(MSDOS_I(inode)->scan_lock);
+	hints = (void *)(MSDOS_I(inode)->scan_hints);
+	if (hints) {
+		MSDOS_I(inode)->scan_hints = 0;
+	}
+	up(&(MSDOS_I(inode)->scan_lock);
+	if (hints) kfree(hints);
 
 	if (is_bad_inode(inode))
 		return;

@@ -1011,6 +1022,8 @@ static int fat_read_root(struct inode *i
 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
 	int error;
 
+	init_MUTEX(&(MSDOS_I(inode)->scan_lock);
+	MSDOS_I(inode)->scan_hints = 0;
 	MSDOS_I(inode)->i_pos = 0;
 	inode->i_uid = sbi->options.fs_uid;
 	inode->i_gid = sbi->options.fs_gid;

@@ -201,6 +201,88 @@ fat_shortname2uni(struct nls_table *nls,
  * Return values: negative -> error, 0 -> not found, positive -> found,
  * value is the total amount of slots, including the shortname entry.
  */
+
+#define FAT_SCAN_SHIFT	4			/* 2x8 way scan hints  */
+#define FAT_SCAN_NWAY	(1<<FAT_SCAN_SHIFT)
+
+inline
+static int hint_allocate(struct inode *dir)
+{
+	loff_t *hints;
+	int err = 0;
+
+	if (!MSDOS_I(dir)->scan_hints) {
+		hints = kcalloc(FAT_SCAN_NWAY, sizeof(loff_t), GFP_KERNEL);
+		if (!hints) 
+			err = -ENOMEM;
+
+		down(&MSDOS_I(dir)->scan_lock);
+		if (MSDOS_I(dir)->scan_hints)
+			err = -EINVAL;
+		if (!err)
+			MSDOS_I(dir)->scan_hints = hints;
+		up(&MSDOS_I(dir)->scan_lock);
+		if (err == -EINVAL) {
+			kfree(hints);
+			err = 0;
+		}
+	}
+	return err;
+}
+
+
+inline
+static void hint_record(struct inode *dir, struct fat_slot_info *sinfo, 
+			  int hindex)
+{
+	loff_t under_scan_off, nent;
+
+	nent = (dir->i_size > PAGE_SIZE ? dir->i_size : PAGE_SIZE)
+		/ sizeof(struct msdos_dir_entry);
+
+	/* educational guess; try to cover 1/4 previous range */
+	nent >>= (FAT_SCAN_SHIFT + 2);
+	under_scan_off = nent * sizeof(struct msdos_dir_entry);
+
+	if (sinfo->slot_off > under_scan_off) 
+		MSDOS_I(dir)->scan_hints[hindex] =
+			sinfo->slot_off - under_scan_off;  
+	else
+		MSDOS_I(dir)->scan_hints[hindex] = 0;  
+}
+
+
+inline 
+static int hint_index_body(const unsigned char *name, int name_len, int check_null)
+{
+	int i;
+	int val = 0;
+	unsigned char *p = (unsigned char *) name;
+	int id = current->pid;
+	
+	for (i=0; i<name_len; i++) {
+		if (check_null && !*p) break;
+		val = ((val << 1) & 0xfe) | ((val & 0x80) ? 1 : 0);
+		val ^= *p;
+		p ++;
+	}
+	id = ((id >> 8) & 0xf) ^ (id & 0xf);
+	val = (val << 1) | (id & 1);
+	return val & (FAT_SCAN_NWAY-1);
+}
+
+inline 
+static int lfn_hint_index(const unsigned char *name, int name_len)
+{
+	return hint_index_body(name, name_len, 0);
+}
+
+inline 
+static int hint_index(const unsigned char *name)
+{
+	return hint_index_body(name, MSDOS_NAME, 1);
+}
+
 int fat_search_long(struct inode *inode, const unsigned char *name,
 		    int name_len, struct fat_slot_info *sinfo)
 {

@@ -218,13 +300,26 @@ 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;
+	int hindex;
+	int ret;
+
+	ret = hint_allocate(inode); 
+	if (ret < 0) return ret;
+	hindex = lfn_hint_index(name, name_len);
+	start_off = cpos =  MSDOS_I(inode)->scan_hints[hindex];
 
 	err = -ENOENT;
 	while(1) {
-		if (fat_get_entry(inode, &cpos, &bh, &de) == -1)
-			goto EODir;
+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)

@@ -274,8 +369,11 @@ 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;

@@ -363,6 +461,7 @@ Found:
 	sinfo->de = de;
 	sinfo->bh = bh;
 	sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de);
+	hint_record(inode, sinfo, hindex);
 	err = 0;
 EODir:
 	if (unicode)

@@ -838,17 +937,32 @@ int fat_scan(struct inode *dir, const un
 	     struct fat_slot_info *sinfo)
 {
 	struct super_block *sb = dir->i_sb;
+	loff_t	start_off;
+	int	hindex;
+	int	ret;
+	int reach_bottom = 0;
+
+	ret = hint_allocate(dir); 
+	if (ret < 0) return ret;
+	hindex = hint_index(name);
 
-	sinfo->slot_off = 0;
+	sinfo->slot_off = start_off = MSDOS_I(dir)->scan_hints[hindex];
 	sinfo->bh = NULL;
-	while (fat_get_short_entry(dir, &sinfo->slot_off, &sinfo->bh,
-				   &sinfo->de) >= 0) {
+	while (1) {
+		if (fat_get_short_entry(dir, &sinfo->slot_off, 
+				        &sinfo->bh, &sinfo->de) <0 ) { 
+			if (!start_off) break;
+			sinfo->slot_off = 0LL; reach_bottom ++;
+			continue;
+		}
 		if (!strncmp(sinfo->de->name, name, MSDOS_NAME)) {
 			sinfo->slot_off -= sizeof(*sinfo->de);
 			sinfo->nr_slots = 1;
 			sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de);
+			hint_record(dir, sinfo, hindex);
 			return 0;
 		}
+		if (reach_bottom && (start_off <= sinfo->slot_off)) break;
 	}
 	return -ENOENT;
 }

@@ -242,6 +242,8 @@ static int fat_fill_inode(struct inode *
 	inode->i_version++;
 	inode->i_generation = get_seconds();
 
+	init_MUTEX(&MSDOS_I(inode)->scan_lock);
+	MSDOS_I(inode)->scan_hints = 0;
 	if ((de->attr & ATTR_DIR) && !IS_FREE(de->name)) {
 		inode->i_generation &= ~1;
 		inode->i_mode = MSDOS_MKMODE(de->attr,

@@ -345,6 +347,15 @@ static void fat_delete_inode(struct inod
 static void fat_clear_inode(struct inode *inode)
 {
 	struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
+	loff_t *hints;
+
+	down(&MSDOS_I(inode)->scan_lock);
+	hints = (MSDOS_I(inode)->scan_hints);
+	if (hints) {
+		MSDOS_I(inode)->scan_hints = NULL;
+	}
+	up(&MSDOS_I(inode)->scan_lock);
+	kfree(hints);
 
 	if (is_bad_inode(inode))
 		return;

@@ -1011,6 +1022,8 @@ static int fat_read_root(struct inode *i
 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
 	int error;
 
+	init_MUTEX(&MSDOS_I(inode)->scan_lock);
+	MSDOS_I(inode)->scan_hints = 0;
 	MSDOS_I(inode)->i_pos = 0;
 	inode->i_uid = sbi->options.fs_uid;
 	inode->i_gid = sbi->options.fs_gid;

@@ -255,6 +255,8 @@ struct msdos_inode_info {
 	/* for avoiding the race between fat_free() and fat_get_cluster() */
 	unsigned int cache_valid_id;
 
+	struct semaphore scan_lock;	/* lock for dirscan hints */
+	loff_t *scan_hints;	/* dirscan hints */
 	loff_t mmu_private;
 	int i_start;		/* first cluster or 0 */
 	int i_logstart;		/* logical first cluster */

diff -puN fs/fat/dir.c~fat_lookup-hint fs/fat/dir.c
@@ -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
@@ -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);

diff -r -up linux-2.6.13/fs/fat/dir.c linux-2.6.13-scan2/fs/fat/dir.c
@@ -22,6 +22,185 @@
 #include <linux/buffer_head.h>
 #include <asm/uaccess.h>
 
+void fat_lkup_hint_init_sb(struct super_block *sb)
+{
+	struct msdos_sb_info *sbi = MSDOS_SB(sb);
+
+	sbi->lkup_hint_lock = SPIN_LOCK_UNLOCKED;
+	INIT_LIST_HEAD(&sbi->lkup_hint_head);
+	sbi->lkup_hint_freemap = 0;
+	sbi->lkup_hint_freemap = ~sbi->lkup_hint_freemap;
+}
+
+void fat_lkup_hint_inval(struct inode *dir)
+{
+	struct super_block *sb = dir->i_sb;
+	struct msdos_sb_info *sbi = MSDOS_SB(sb);
+	struct fat_lookup_hint *hint, *n;
+	int i;
+
+	spin_lock(&sbi->lkup_hint_lock);
+	list_for_each_entry_safe(hint, n, &sbi->lkup_hint_head, lru_list) {
+		if (hint->dir == dir) {
+			list_del_init(&hint->lru_list);
+			i = hint - &(sbi->lkup_hint[0]);
+			sbi->lkup_hint_freemap |= (1 << i);
+		}
+	}
+	spin_unlock(&sbi->lkup_hint_lock);
+}
+
+/* 
+ * AVG_MSDOS_SLOTS is selected so that it can store 48 chars file name length.
+ *
+ * According raugh observation, most files in Linux installed system have 
+ * less than or equal to 48 chars file name length. 
+ *
+ * Following is one of statistic information;
+ *
+ *	total # of files(*1) 			9193
+ *	max length of file name			52 chars
+ *
+ *	# of files over 48 chars name length	36
+ *	  % covered by 48 chars name length	 99.6%
+ *
+ *	# of files over 32 chars name length	517
+ *	  % covered by 32 chars name length	 94.3%
+ *
+ *	*1) # of file, dir and symlink which has over 2 chars 
+ *	file name length.
+ * 
+ */
+#define AVG_MSDOS_SLOTS	(8+1)
+#define WIN_LFN_TOP	(3 * AVG_MSDOS_SLOTS * sizeof(struct msdos_dir_entry))
+#define WIN_LFN_BOTTOM	(5 * AVG_MSDOS_SLOTS * sizeof(struct msdos_dir_entry))
+
+#define WIN_TOP		(3 * sizeof(struct msdos_dir_entry))
+#define WIN_BOTTOM	(5 * sizeof(struct msdos_dir_entry))
+
+static inline
+loff_t get_syswide_hint(loff_t pos, struct fat_lookup_hint *hint)
+{
+	/* 
+	 * NOTE: If you don't expect locality beyond process, 
+	 * make this return 0 always, instead of following.
+	 */
+	return  (pos == 0) ? hint->last_pos : pos;
+}
+
+static loff_t fat_lkup_hint_get(struct inode *dir, int is_lfn)
+{
+	struct super_block *sb = dir->i_sb;
+	struct fat_lookup_hint *hint;
+	struct msdos_sb_info *sbi = MSDOS_SB(sb);
+	loff_t win_top;
+	unsigned int rnd_flg;
+	loff_t pos = 0;
+
+	if (is_lfn) {
+		rnd_flg = FAT_LKUP_ST_LFN_RANDOM;
+		win_top = WIN_LFN_TOP;
+	} else {
+		rnd_flg = FAT_LKUP_ST_RANDOM;
+		win_top = WIN_TOP;
+	}
+
+	spin_lock(&sbi->lkup_hint_lock);
+	list_for_each_entry(hint, &sbi->lkup_hint_head, lru_list) {
+		if (hint->dir == dir) {
+			if (!(hint->state & rnd_flg)) {
+				if (hint->pid == current->pid)  {
+					pos = hint->last_pos;
+					break;
+				}
+				/* expect locality beyond process */
+				pos = get_syswide_hint(pos, hint);
+			}
+		}
+	}
+	spin_unlock(&sbi->lkup_hint_lock);
+	return max(0LL, pos - win_top);
+}
+
+/* 
+ * NOTE: If you don't want multiple entries for 
+ * same pid, set this to 1.
+ */
+#define LKUP_MULTIENT_MAX	(FAT_LKUP_HINT_MAX/4-1)
+
+
+/* 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;
+	struct msdos_sb_info *sbi = MSDOS_SB(sb);
+	int nr_pid_match = 0;
+	unsigned int state;
+
+	spin_lock(&sbi->lkup_hint_lock);
+	/* find out same pid entry */
+	list_for_each_entry(p, &sbi->lkup_hint_head, lru_list) {
+		if (p->pid == current->pid) {
+			nr_pid_match ++;
+			if (p->dir == dir) {
+				hint = p;
+				goto match;
+			}
+			if (!hint) 
+				hint = p;
+		}
+	}
+
+	if (nr_pid_match < LKUP_MULTIENT_MAX)
+		hint = NULL;
+
+	if (hint == NULL) {
+		int free_hint;
+		free_hint = ffs(sbi->lkup_hint_freemap);
+		if (free_hint) {
+			/* add the new entry */
+			free_hint --;
+			sbi->lkup_hint_freemap &= ~ (1<<(free_hint));
+			hint = &sbi->lkup_hint[free_hint];
+			INIT_LIST_HEAD(&hint->lru_list);
+			/* don't need to recheck hint */
+		} else {
+			/* replace the last entry */
+			struct list_head *p = sbi->lkup_hint_head.prev;
+			hint = list_entry(p, struct fat_lookup_hint, lru_list);
+		}
+		hint->pid = current->pid;
+		hint->dir = dir;
+		hint->last_pos = 0;
+	}
+
+match:
+	state = (FAT_LKUP_ST_RANDOM | FAT_LKUP_ST_LFN_RANDOM);
+	hint->last_pos = pos;
+	if (hint->dir != dir) {
+		hint->dir = dir;
+	} else {
+		win_start = hint->last_pos - WIN_TOP;
+		win_end = hint->last_pos + WIN_BOTTOM;
+		if (win_start <= pos && pos <= win_end) {
+			state &= ~FAT_LKUP_ST_RANDOM;
+		}
+		win_start = hint->last_pos - WIN_LFN_TOP;
+		win_end = hint->last_pos + WIN_LFN_BOTTOM;
+		if (win_start <= pos && pos <= win_end) {
+			state &= ~FAT_LKUP_ST_LFN_RANDOM;
+		}
+	}
+	hint->state = state;
+
+	/* update LRU list */
+	list_del(&hint->lru_list);
+	list_add(&hint->lru_list, &sbi->lkup_hint_head);	/* put hint to head */
+	spin_unlock(&sbi->lkup_hint_lock);
+}
+
 static inline loff_t fat_make_i_pos(struct super_block *sb,
 				    struct buffer_head *bh,
 				    struct msdos_dir_entry *de)

@@ -218,13 +397,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, 1);
 	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 || reach_bottom)
+				goto EODir;
+			reach_bottom++;
+			cpos = 0;
+			continue;
+		}
 parse_record:
 		nr_slots = 0;
 		if (de->name[0] == DELETED_FLAG)

@@ -274,8 +463,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 || reach_bottom)
+						goto EODir;
+					reach_bottom++;
+					cpos = 0;
+					goto top;
+				}
 				if (slot == 0)
 					break;
 				ds = (struct msdos_dir_slot *) de;

@@ -363,6 +557,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)

@@ -838,16 +1033,29 @@ int fat_scan(struct inode *dir, const un
 	     struct fat_slot_info *sinfo)
 {
 	struct super_block *sb = dir->i_sb;
+	int reach_bottom = 0;
+	loff_t start_off;
 
-	sinfo->slot_off = 0;
+	start_off = sinfo->slot_off = fat_lkup_hint_get(dir, 0);
 	sinfo->bh = NULL;
-	while (fat_get_short_entry(dir, &sinfo->slot_off, &sinfo->bh,
-				   &sinfo->de) >= 0) {
-		if (!strncmp(sinfo->de->name, name, MSDOS_NAME)) {
-			sinfo->slot_off -= sizeof(*sinfo->de);
-			sinfo->nr_slots = 1;
-			sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de);
-			return 0;
+	while (1) {
+		if  (fat_get_short_entry(dir, &sinfo->slot_off, &sinfo->bh,
+				         &sinfo->de) >= 0) {
+			if (!strncmp(sinfo->de->name, name, MSDOS_NAME)) {
+				sinfo->slot_off -= sizeof(*sinfo->de);
+				sinfo->nr_slots = 1;
+				sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, 
+							      sinfo->de);
+				fat_lkup_hint_add(dir, sinfo->slot_off);
+				return 0;
+			}
+			if (reach_bottom && (start_off <= sinfo->slot_off)) 
+				break;
+		} else {
+			if (!start_off || reach_bottom)
+				break;
+			reach_bottom ++;
+			sinfo->slot_off = 0;
 		}
 	}
 	return -ENOENT;

diff -r -up linux-2.6.13/fs/fat/inode.c linux-2.6.13-scan2/fs/fat/inode.c
@@ -342,6 +342,8 @@ 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 +351,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);

@@ -1042,6 +1045,8 @@ static int fat_read_root(struct inode *i
 	return 0;
 }
 
+extern void fat_lkup_hint_init_sb(struct super_block *sb);
+
 /*
  * Read the super block of an MS-DOS FS.
  */

@@ -1302,6 +1307,8 @@ int fat_fill_super(struct super_block *s
 		goto out_fail;
 	}
 
+	fat_lkup_hint_init_sb(sb);
+
 	return 0;
 
 out_invalid:

diff -r -up linux-2.6.13/include/linux/msdos_fs.h linux-2.6.13-scan2/include/linux/msdos_fs.h
@@ -185,6 +185,19 @@ struct fat_slot_info {
 #include <linux/nls.h>
 #include <linux/fs.h>
 
+#define FAT_LKUP_HINT_MAX     16
+/* assume FAT_LKUP_HINT_MAX <= sizeof(long)*8 */
+
+struct fat_lookup_hint {
+	struct list_head lru_list;
+	pid_t pid;
+	struct inode *dir;
+	loff_t last_pos;
+#define FAT_LKUP_ST_RANDOM       1
+#define FAT_LKUP_ST_LFN_RANDOM       2
+	unsigned int state;
+};
+
 struct fat_mount_options {
 	uid_t fs_uid;
 	gid_t fs_gid;

@@ -241,6 +254,12 @@ struct msdos_sb_info {
 
 	spinlock_t inode_hash_lock;
 	struct hlist_head inode_hashtable[FAT_HASH_SIZE];
+
+	/* dirent lookup hints */
+	spinlock_t lkup_hint_lock;
+	struct list_head lkup_hint_head;
+	struct fat_lookup_hint lkup_hint[FAT_LKUP_HINT_MAX];
+	unsigned lkup_hint_freemap:FAT_LKUP_HINT_MAX;
 };
 
 #define FAT_CACHE_VALID	0	/* special case for valid cache */