Re: [PATCH][FAT] FAT dirent scan with hin take #3

[OGAWA Hirofumi]

"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.0 +0900
+++ linux-2.6.13-hirofumi/fs/fat/dir.c	2005-09-02 01:06:50.0 +0900
@@ -22,6 +22,148 @@
 #include 
 #include 
 
+#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(>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(>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(_lookup_hint_lock);
+	list_for_each_entry_safe(hint, n, _lookup_hint_head, lru_list) {
+		if (hint->sb == sb && hint->dir == dir) {
+			list_del_init(>lru_list);
+			fat_lkup_hint_free(hint);
+			fat_lookup_hint_count--;
+		}
+	}
+	spin_unlock(_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(_lookup_hint_lock);
+	list_for_each_entry(hint, _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(_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(_lookup_hint_lock);
+	list_for_each_entry(p, _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(_lookup_hint_lock);
+
+			hint = fat_lkup_hint_alloc();
+			if (hint == NULL)
+return;
+			spin_lock(_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(>lru_list);
+	list_add(>lru_list, _lookup_hint_head);
+	spin_unlock(_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 

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Machida, Hiroyuki wrote:

OGAWA Hirofumi wrote:


"Machida, Hiroyuki" <[EMAIL PROTECTED]> writes:



Right, it looks like TLB, which holds cache "Physical addres"
correponding to "Logical address". In this case, PID and file name
to be looked up, perform role of "Logical address".




But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?



Sounds interesting...

Once concern about global URL in general, it tends to be occupied

^^^
sorry, LRU not URL.


by specific pattern, like accesses from one process or to on dir.

one 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



e.g.

#define FAT_LOOKUP_HINT_MAX16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*int state;*/
};



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.

As implementation issue, if number of entires is small enough,
we can use an array, not a list.



static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, 
loff_t);

static int fat_lkup_hint_init(void);



I think super_block can be retrieved from inode, any other intention do
you have?


In addtion, we can do follwoing to check the exact match case;

0. Record hash value of file name in struct fat_lookup_hint

1. Check hash value to find exact match case,
1-1. If matched entry is found, check if file name and
 file name retieved from dirent corresponding
1-2. We found the entry

2. Get hint value, if there seem to have locality
2-1. Check locality of access pattern for this PID and this
 DIR.
2-2. If we relize access locality, return hit value so that
 it covers a potential working set.
2-3. Use hint value as start position of dirscan.




--
Hiroyuki Machida
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Machida, Hiroyuki wrote:

OGAWA Hirofumi wrote:


Machida, Hiroyuki [EMAIL PROTECTED] writes:



Right, it looks like TLB, which holds cache Physical addres
correponding to Logical address. In this case, PID and file name
to be looked up, perform role of Logical address.




But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?



Sounds interesting...

Once concern about global URL in general, it tends to be occupied

^^^
sorry, LRU not URL.


by specific pattern, like accesses from one process or to on dir.

one 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



e.g.

#define FAT_LOOKUP_HINT_MAX16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*int state;*/
};



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.

As implementation issue, if number of entires is small enough,
we can use an array, not a list.



static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, 
loff_t);

static int fat_lkup_hint_init(void);



I think super_block can be retrieved from inode, any other intention do
you have?


In addtion, we can do follwoing to check the exact match case;

0. Record hash value of file name in struct fat_lookup_hint

1. Check hash value to find exact match case,
1-1. If matched entry is found, check if file name and
 file name retieved from dirent corresponding
1-2. We found the entry

2. Get hint value, if there seem to have locality
2-1. Check locality of access pattern for this PID and this
 DIR.
2-2. If we relize access locality, return hit value so that
 it covers a potential working set.
2-3. Use hint value as start position of dirscan.




--
Hiroyuki Machida
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[OGAWA Hirofumi]

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.0 +0900
+++ linux-2.6.13-hirofumi/fs/fat/dir.c	2005-09-02 01:06:50.0 +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 

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

OGAWA Hirofumi wrote:

"Machida, Hiroyuki" <[EMAIL PROTECTED]> writes:



Right, it looks like TLB, which holds cache "Physical addres"
correponding to "Logical address". In this case, PID and file name
to be looked up, perform role of "Logical address".



But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?


Sounds interesting...

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



e.g.

#define FAT_LOOKUP_HINT_MAX 16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*  int state;*/
};


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.

As implementation issue, if number of entires is small enough,
we can use an array, not a list.



static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, loff_t);
static int fat_lkup_hint_init(void);


I think super_block can be retrieved from inode, any other intention do
you have?


In addtion, we can do follwoing to check the exact match case;

0. Record hash value of file name in struct fat_lookup_hint

1. Check hash value to find exact match case,
1-1. If matched entry is found, check if file name and
 file name retieved from dirent corresponding
1-2. We found the entry

2. Get hint value, if there seem to have locality
2-1. Check locality of access pattern for this PID and this
 DIR.
2-2. If we relize access locality, return hit value so that
 it covers a potential working set.
2-3. Use hint value as start position of dirscan.

--
Hiroyuki Machida
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[OGAWA Hirofumi]

"Machida, Hiroyuki" <[EMAIL PROTECTED]> writes:

> Right, it looks like TLB, which holds cache "Physical addres"
> correponding to "Logical address". In this case, PID and file name
> to be looked up, perform role of "Logical address".

But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?

e.g.

#define FAT_LOOKUP_HINT_MAX 16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*  int state;*/
};

static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, loff_t);
static int fat_lkup_hint_init(void);
-- 
OGAWA Hirofumi <[EMAIL PROTECTED]>
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Pekka Enberg <[EMAIL PROTECTED]> wrote:
> After finally understanding what you're doing, how about:
> 
> static inline int hint_allocate(struct inode *dir)
> {
> loff_t *hints;
> int err = 0;
> 
> if (!MSDOS_I(dir)->scan_hints)

Should read:

if (MSDOS_I(dir)->scan_hints)

> return 0;
> 
> hints = kcalloc(FAT_SCAN_NWAY, sizeof(loff_t), GFP_KERNEL);
> if (!hints)
> err = -ENOMEM;
> 
> down(_I(dir)->scan_lock);
> /*
>  * We allocated memory without scan_lock so lets make sure
>  * no other thread completed hint_allocate() before us.
>  */
> if (!MSDOS_I(dir)->scan_hints) {
> MSDOS_I(dir)->scan_hints = hints;
> hints = NULL;
> }
> up(_I(dir)->scan_lock);
> 
> kfree(hints);
> return err;
> }
> 
> Pekka
>
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:
> How about this ?
> 
> if (!MSDOS_I(dir)->scan_hints) {
> hints  = kcalllo();
> 
> down
> if (MSDOS_I(dir)->scan_hints) {
> up
> goto already_allocated;
> }
> if (hints)
> MSDOS_I(dir)->scan_hints = hints;
> up
> }
> return (hints == 0) ? -ENOMEM : 0;
> 
> already_allocated:
> kfree(hints); /* kfree accepts NULL */
> return 0;

After finally understanding what you're doing, how about:

static inline int hint_allocate(struct inode *dir)
{
loff_t *hints;
int err = 0;

if (!MSDOS_I(dir)->scan_hints)
return 0;

hints = kcalloc(FAT_SCAN_NWAY, sizeof(loff_t), GFP_KERNEL);
if (!hints)
err = -ENOMEM;

down(_I(dir)->scan_lock);
/*
 * We allocated memory without scan_lock so lets make sure
 * no other thread completed hint_allocate() before us.
 */
if (!MSDOS_I(dir)->scan_hints) {
MSDOS_I(dir)->scan_hints = hints;
hints = NULL;
}
up(_I(dir)->scan_lock);

kfree(hints);
return err;
}

Pekka
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:
> > Please consider moving this check to callers. Conditional allocation
> > makes this bit strange API-wise. Or alternatively, give
> > hint_allocate() a better name.
> 
> How about hint_allocate_conditional() ?

hint_get() sounds better to me.

Pekka
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Pekka Enberg wrote:

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:


+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> 8) & 0xf) ^ (id & 0xf);
+   val = (val << 1) | (id & 1);
+   return val & (FAT_SCAN_NWAY-1);



Couldn't you use jhash() from  here?

 Pekka

Thanks, I'll replace it with functions in jhash.h, then
check performance again.

--
Hiroyuki Machida[EMAIL PROTECTED]   

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Hi,

Thank you checking code...

Pekka Enberg wrote:

Hi,


:
snip



This patch enables using hint information on scanning dir.
It achieves excellent performance with "ls -l" for over 1000 entries.

* fat-dirscan-with-hint_3.patch for linux 2.6.13

fs/fat/dir.c |  130 ---
fs/fat/inode.c   |   13 
include/linux/msdos_fs.h |2
3 files changed, 137 insertions(+), 8 deletions(-)

Signed-off-by: Hiroyuki Machida <[EMAIL PROTECTED]> for CELF

* modified files


--- linux-2.6.13/fs/fat/dir.c   2005-08-29 08:41:01.0 +0900
+++ linux-2.6.13-work/fs/fat/dir.c  2005-08-31 13:48:01.001119437 +0900
@@ -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  (1i_version++;
   inode->i_generation = get_seconds();

+   init_MUTEX(_I(inode)->scan_lock);
+   MSDOS_I(inode)->scan_hints = 0;



Please use NULL.


Ok,




   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(_I(inode)->scan_lock);
+   hints = (MSDOS_I(inode)->scan_hints);



Pleas drop redundant parenthesis.


Ok,




+   if (hints) {
+   MSDOS_I(inode)->scan_hints = NULL;
+   }
+   up(_I(inode)->scan_lock);
+   kfree(hints);



Why can't you do kfree() under scan_lock?


Just try to minimize blocked period.





@@ -1011,6 +1022,8 @@ static int fat_read_root(struct inode *i
   struct msdos_sb_info *sbi = MSDOS_SB(sb);
   int error;

+   init_MUTEX(_I(inode)->scan_lock);
+   MSDOS_I(inode)->scan_hints = 0;



Please use NULL here.


Ok.


 Pekka
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



--
Hiroyuki Machida[EMAIL PROTECTED]   
SSW Dept. HENC, Sony Corp.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Hi,

Pekka Enberg wrote:

Hi,

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:


+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;



Better to bail out here as...



+
+   down(_I(dir)->scan_lock);
+   if (MSDOS_I(dir)->scan_hints)
+   err = -EINVAL;



...you might overwrite -ENOMEM here masking the real problem.



It's ok. If MSDOS_I(dir)->scan_hints isn't NULL, it's not error case.
We need just kfree(hints) and return 0.(Assuming  kfree() accepts NULL)
I think EINVAL confuse you.



+   if (!err)
+   MSDOS_I(dir)->scan_hints = hints;
+   up(_I(dir)->scan_lock);
+   if (err == -EINVAL) {



Gotos would make error handling much cleaner.


How about this ?

if (!MSDOS_I(dir)->scan_hints) {
hints  = kcalllo();

down
if (MSDOS_I(dir)->scan_hints) {
up
goto already_allocated;
}
if (hints)
MSDOS_I(dir)->scan_hints = hints;
up
}
return (hints == 0) ? -ENOMEM : 0;

already_allocated:
kfree(hints); /* kfree accepts NULL */
return 0;






+inline
+static int hint_index_body(const unsigned char *name, int name_len, int 
check_null)



Please consider calling this __hint_index() instead as per normal
naming conventions.


Agree.




+{
+   int i;
+   int val = 0;
+   unsigned char *p = (unsigned char *) name;
+   int id = current->pid;
+
+   for (i=0; i


Please put break on separate line. You still have quite a few of these.


Agree





+   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);
+}



  Pekka



--
Hiroyuki Machida[EMAIL PROTECTED]   
SSW Dept. HENC, Sony Corp.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

Hi,

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:
> 
> Sorry, I send out wrong version. I attached the latest patch to 2.6.13.
> 
> OGAWA Hirofumi wrote:
> > "Machida, Hiroyuki" <[EMAIL PROTECTED]> writes:
> >
> >
> >>Here is a revised version of dirent scan patch,  mentioned at
> >>following E-mail.
> >>
> >>This patch addresses performance damages on "ls | xargs xxx" and
> >>reverse order scan which are reported to the previous patch.
> >>
> >>With this patch, fat_search_long() and fat_scan() use hint value
> >>as start of scan. For each directory holds multiple hint value entries.
> >>The entry would be selected by hash value based on scan target name and
> >>PID. Hint value would be calculated based on the entry previously found
> >>entry, so that the hint can cover backward neighborhood.
> >
> >
> > This patch couldn't compile. I assume you post a wrong patch...?
> >
> > The code is strange... Is the hint value related to the previously
> > accessed entry?
> >
> > This seems to be randomly cacheing the recent access position...  Is
> > it your intention of this patch?
> 
> Right, it looks like TLB, which holds cache "Physical addres"
> correponding to "Logical address". In this case, PID and file name
> to be looked up, perform role of "Logical address".
> 
> I prepared vfat16 fs where over 4000 files in /foo
> and 200 files in root, then checked with following cases;
> 
> 
> without patch   with patch
> ls-vfat 59.02.49
> xargs-vfat  61.311.9
> stat-vfat   41  17
> stat-vfat-reverse   56  32
> 
> ls-msdos14.20.62
> xargs-msdos 16.816.7
> stat-msdos  21  15
> stat-msdos-reverse  22  16
> - all valuses have sec unit
> 
> 1-1 ls-vat)
> mount vfat to /a
> /usr/bin/time -p sh -c "/usr/bin/ls -Rl /a > /dev/null"
> umount /a
> 
> 1-2 ls-msdos)
> mount msdos to /a
> /usr/bin/time -p sh -c "/usr/bin/ls -Rl /a > /dev/null"
> umount /a
> 
> 2-1 xargs-vfat)
> mount vfat to /a
> cd /a/foo
> /usr/bin/time -p sh -c "(/usr/bin/ls | /usr/in/xargs stat) > /dev/null"
> umount /a
> 
> 2-2 xargs-msdos)
> mount msdos to /a
> cd /a/foo
> /usr/bin/time -p sh -c "(/usr/bin/ls | /usr/in/xargs stat) > /dev/null"
> umount /a
> 
> 3-1 stat-vfat)
> mount vfat to /a
> cd /a/foo
> repeat stat files which have located in the last 1024 dir entries
>with incremental order.
> umount /a
> 
> 3-2 stat-vfat-reverse)
> do 3-1 with decremental order
> 
> 3-3 stat-msdos)
> do 3-1 with msdos fs
> 
> 3-4 stat-msdos-reverse)
> do 3-2 with msdos fs
> 
> 
> --
> Hiroyuki Machida
> 
> 
> This patch enables using hint information on scanning dir.
> It achieves excellent performance with "ls -l" for over 1000 entries.
> 
> * fat-dirscan-with-hint_3.patch for linux 2.6.13
> 
>  fs/fat/dir.c |  130 
> ---
>  fs/fat/inode.c   |   13 
>  include/linux/msdos_fs.h |2
>  3 files changed, 137 insertions(+), 8 deletions(-)
> 
> Signed-off-by: Hiroyuki Machida <[EMAIL PROTECTED]> for CELF
> 
> * modified files
> 
> 
> --- linux-2.6.13/fs/fat/dir.c   2005-08-29 08:41:01.0 +0900
> +++ linux-2.6.13-work/fs/fat/dir.c  2005-08-31 13:48:01.001119437 +0900
> @@ -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< +
> +inline
> +static int hint_allocate(struct inode *dir)
> +{
> +   loff_t *hints;
> +   int err = 0;
> +
> +   if (!MSDOS_I(dir)->scan_hints) {

Please consider moving this check to callers. Conditional allocation
makes this bit strange API-wise. Or alternatively, give
hint_allocate() a better name.

> --- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.0 +0900
> +++ linux-2.6.13-work/fs/fat/inode.c2005-08-31 12:59:54.292274060 +0900
> @@ -242,6 +242,8 @@ static int fat_fill_inode(struct inode *
> inode->i_version++;
> inode->i_generation = get_seconds();
> 
> +   init_MUTEX(_I(inode)->scan_lock);
> +   MSDOS_I(inode)->scan_hints = 0;

Please use NULL.

> 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(_I(inode)->scan_lock);
> +   hints = (MSDOS_I(inode)->scan_hints);

Pleas drop redundant 

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:
> +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 +   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);

Couldn't you use jhash() from  here?

 Pekka
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

Hi,

On 8/31/05, Machida, Hiroyuki <[EMAIL PROTECTED]> wrote:
> +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;

Better to bail out here as...

> +
> +   down(_I(dir)->scan_lock);
> +   if (MSDOS_I(dir)->scan_hints)
> +   err = -EINVAL;

...you might overwrite -ENOMEM here masking the real problem.

> +   if (!err)
> +   MSDOS_I(dir)->scan_hints = hints;
> +   up(_I(dir)->scan_lock);
> +   if (err == -EINVAL) {

Gotos would make error handling much cleaner.

> +inline
> +static int hint_index_body(const unsigned char *name, int name_len, int 
> check_null)

Please consider calling this __hint_index() instead as per normal
naming conventions.

> +{
> +   int i;
> +   int val = 0;
> +   unsigned char *p = (unsigned char *) name;
> +   int id = current->pid;
> +
> +   for (i=0; i +   if (check_null && !*p) break;

Please put break on separate line. You still have quite a few of these.

> +   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);
> +}

  Pekka
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

Hi,

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:
 +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;

Better to bail out here as...

 +
 +   down(MSDOS_I(dir)-scan_lock);
 +   if (MSDOS_I(dir)-scan_hints)
 +   err = -EINVAL;

...you might overwrite -ENOMEM here masking the real problem.

 +   if (!err)
 +   MSDOS_I(dir)-scan_hints = hints;
 +   up(MSDOS_I(dir)-scan_lock);
 +   if (err == -EINVAL) {

Gotos would make error handling much cleaner.

 +inline
 +static int hint_index_body(const unsigned char *name, int name_len, int 
 check_null)

Please consider calling this __hint_index() instead as per normal
naming conventions.

 +{
 +   int i;
 +   int val = 0;
 +   unsigned char *p = (unsigned char *) name;
 +   int id = current-pid;
 +
 +   for (i=0; iname_len; i++) {
 +   if (check_null  !*p) break;

Please put break on separate line. You still have quite a few of these.

 +   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);
 +}

  Pekka
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:
 +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; iname_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);

Couldn't you use jhash() from linux/jhash.h here?

 Pekka
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

Hi,

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:
 
 Sorry, I send out wrong version. I attached the latest patch to 2.6.13.
 
 OGAWA Hirofumi wrote:
  Machida, Hiroyuki [EMAIL PROTECTED] writes:
 
 
 Here is a revised version of dirent scan patch,  mentioned at
 following E-mail.
 
 This patch addresses performance damages on ls | xargs xxx and
 reverse order scan which are reported to the previous patch.
 
 With this patch, fat_search_long() and fat_scan() use hint value
 as start of scan. For each directory holds multiple hint value entries.
 The entry would be selected by hash value based on scan target name and
 PID. Hint value would be calculated based on the entry previously found
 entry, so that the hint can cover backward neighborhood.
 
 
  This patch couldn't compile. I assume you post a wrong patch...?
 
  The code is strange... Is the hint value related to the previously
  accessed entry?
 
  This seems to be randomly cacheing the recent access position...  Is
  it your intention of this patch?
 
 Right, it looks like TLB, which holds cache Physical addres
 correponding to Logical address. In this case, PID and file name
 to be looked up, perform role of Logical address.
 
 I prepared vfat16 fs where over 4000 files in /foo
 and 200 files in root, then checked with following cases;
 
 
 without patch   with patch
 ls-vfat 59.02.49
 xargs-vfat  61.311.9
 stat-vfat   41  17
 stat-vfat-reverse   56  32
 
 ls-msdos14.20.62
 xargs-msdos 16.816.7
 stat-msdos  21  15
 stat-msdos-reverse  22  16
 - all valuses have sec unit
 
 1-1 ls-vat)
 mount vfat to /a
 /usr/bin/time -p sh -c /usr/bin/ls -Rl /a  /dev/null
 umount /a
 
 1-2 ls-msdos)
 mount msdos to /a
 /usr/bin/time -p sh -c /usr/bin/ls -Rl /a  /dev/null
 umount /a
 
 2-1 xargs-vfat)
 mount vfat to /a
 cd /a/foo
 /usr/bin/time -p sh -c (/usr/bin/ls | /usr/in/xargs stat)  /dev/null
 umount /a
 
 2-2 xargs-msdos)
 mount msdos to /a
 cd /a/foo
 /usr/bin/time -p sh -c (/usr/bin/ls | /usr/in/xargs stat)  /dev/null
 umount /a
 
 3-1 stat-vfat)
 mount vfat to /a
 cd /a/foo
 repeat stat files which have located in the last 1024 dir entries
with incremental order.
 umount /a
 
 3-2 stat-vfat-reverse)
 do 3-1 with decremental order
 
 3-3 stat-msdos)
 do 3-1 with msdos fs
 
 3-4 stat-msdos-reverse)
 do 3-2 with msdos fs
 
 
 --
 Hiroyuki Machida
 
 
 This patch enables using hint information on scanning dir.
 It achieves excellent performance with ls -l for over 1000 entries.
 
 * fat-dirscan-with-hint_3.patch for linux 2.6.13
 
  fs/fat/dir.c |  130 
 ---
  fs/fat/inode.c   |   13 
  include/linux/msdos_fs.h |2
  3 files changed, 137 insertions(+), 8 deletions(-)
 
 Signed-off-by: Hiroyuki Machida [EMAIL PROTECTED] for CELF
 
 * modified files
 
 
 --- linux-2.6.13/fs/fat/dir.c   2005-08-29 08:41:01.0 +0900
 +++ linux-2.6.13-work/fs/fat/dir.c  2005-08-31 13:48:01.001119437 +0900
 @@ -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  (1FAT_SCAN_SHIFT)
 +
 +inline
 +static int hint_allocate(struct inode *dir)
 +{
 +   loff_t *hints;
 +   int err = 0;
 +
 +   if (!MSDOS_I(dir)-scan_hints) {

Please consider moving this check to callers. Conditional allocation
makes this bit strange API-wise. Or alternatively, give
hint_allocate() a better name.

 --- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.0 +0900
 +++ linux-2.6.13-work/fs/fat/inode.c2005-08-31 12:59:54.292274060 +0900
 @@ -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;

Please use NULL.

 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);

Pleas drop redundant parenthesis.

 +   if (hints) {
 +   MSDOS_I(inode)-scan_hints = NULL;
 +   }
 +   up(MSDOS_I(inode)-scan_lock);
 +   kfree(hints);

Why can't you do kfree() under scan_lock?

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Hi,

Pekka Enberg wrote:

Hi,

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:


+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;



Better to bail out here as...



+
+   down(MSDOS_I(dir)-scan_lock);
+   if (MSDOS_I(dir)-scan_hints)
+   err = -EINVAL;



...you might overwrite -ENOMEM here masking the real problem.



It's ok. If MSDOS_I(dir)-scan_hints isn't NULL, it's not error case.
We need just kfree(hints) and return 0.(Assuming  kfree() accepts NULL)
I think EINVAL confuse you.



+   if (!err)
+   MSDOS_I(dir)-scan_hints = hints;
+   up(MSDOS_I(dir)-scan_lock);
+   if (err == -EINVAL) {



Gotos would make error handling much cleaner.


How about this ?

if (!MSDOS_I(dir)-scan_hints) {
hints  = kcalllo();

down
if (MSDOS_I(dir)-scan_hints) {
up
goto already_allocated;
}
if (hints)
MSDOS_I(dir)-scan_hints = hints;
up
}
return (hints == 0) ? -ENOMEM : 0;

already_allocated:
kfree(hints); /* kfree accepts NULL */
return 0;






+inline
+static int hint_index_body(const unsigned char *name, int name_len, int 
check_null)



Please consider calling this __hint_index() instead as per normal
naming conventions.


Agree.




+{
+   int i;
+   int val = 0;
+   unsigned char *p = (unsigned char *) name;
+   int id = current-pid;
+
+   for (i=0; iname_len; i++) {
+   if (check_null  !*p) break;



Please put break on separate line. You still have quite a few of these.


Agree





+   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);
+}



  Pekka



--
Hiroyuki Machida[EMAIL PROTECTED]   
SSW Dept. HENC, Sony Corp.
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Hi,

Thank you checking code...

Pekka Enberg wrote:

Hi,


:
snip



This patch enables using hint information on scanning dir.
It achieves excellent performance with ls -l for over 1000 entries.

* fat-dirscan-with-hint_3.patch for linux 2.6.13

fs/fat/dir.c |  130 ---
fs/fat/inode.c   |   13 
include/linux/msdos_fs.h |2
3 files changed, 137 insertions(+), 8 deletions(-)

Signed-off-by: Hiroyuki Machida [EMAIL PROTECTED] for CELF

* modified files


--- linux-2.6.13/fs/fat/dir.c   2005-08-29 08:41:01.0 +0900
+++ linux-2.6.13-work/fs/fat/dir.c  2005-08-31 13:48:01.001119437 +0900
@@ -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  (1FAT_SCAN_SHIFT)
+
+inline
+static int hint_allocate(struct inode *dir)
+{
+   loff_t *hints;
+   int err = 0;
+
+   if (!MSDOS_I(dir)-scan_hints) {



Please consider moving this check to callers. Conditional allocation
makes this bit strange API-wise. Or alternatively, give
hint_allocate() a better name.


How about hint_allocate_conditional() ?




--- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.0 +0900
+++ linux-2.6.13-work/fs/fat/inode.c2005-08-31 12:59:54.292274060 +0900
@@ -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;



Please use NULL.


Ok,




   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);



Pleas drop redundant parenthesis.


Ok,




+   if (hints) {
+   MSDOS_I(inode)-scan_hints = NULL;
+   }
+   up(MSDOS_I(inode)-scan_lock);
+   kfree(hints);



Why can't you do kfree() under scan_lock?


Just try to minimize blocked period.





@@ -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;



Please use NULL here.


Ok.


 Pekka
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



--
Hiroyuki Machida[EMAIL PROTECTED]   
SSW Dept. HENC, Sony Corp.
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

Pekka Enberg wrote:

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:


+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; iname_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);



Couldn't you use jhash() from linux/jhash.h here?

 Pekka

Thanks, I'll replace it with functions in jhash.h, then
check performance again.

--
Hiroyuki Machida[EMAIL PROTECTED]   

-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:
  Please consider moving this check to callers. Conditional allocation
  makes this bit strange API-wise. Or alternatively, give
  hint_allocate() a better name.
 
 How about hint_allocate_conditional() ?

hint_get() sounds better to me.

Pekka
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Machida, Hiroyuki [EMAIL PROTECTED] wrote:
 How about this ?
 
 if (!MSDOS_I(dir)-scan_hints) {
 hints  = kcalllo();
 
 down
 if (MSDOS_I(dir)-scan_hints) {
 up
 goto already_allocated;
 }
 if (hints)
 MSDOS_I(dir)-scan_hints = hints;
 up
 }
 return (hints == 0) ? -ENOMEM : 0;
 
 already_allocated:
 kfree(hints); /* kfree accepts NULL */
 return 0;

After finally understanding what you're doing, how about:

static inline int hint_allocate(struct inode *dir)
{
loff_t *hints;
int err = 0;

if (!MSDOS_I(dir)-scan_hints)
return 0;

hints = kcalloc(FAT_SCAN_NWAY, sizeof(loff_t), GFP_KERNEL);
if (!hints)
err = -ENOMEM;

down(MSDOS_I(dir)-scan_lock);
/*
 * We allocated memory without scan_lock so lets make sure
 * no other thread completed hint_allocate() before us.
 */
if (!MSDOS_I(dir)-scan_hints) {
MSDOS_I(dir)-scan_hints = hints;
hints = NULL;
}
up(MSDOS_I(dir)-scan_lock);

kfree(hints);
return err;
}

Pekka
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Pekka Enberg]

On 8/31/05, Pekka Enberg [EMAIL PROTECTED] wrote:
 After finally understanding what you're doing, how about:
 
 static inline int hint_allocate(struct inode *dir)
 {
 loff_t *hints;
 int err = 0;
 
 if (!MSDOS_I(dir)-scan_hints)

Should read:

if (MSDOS_I(dir)-scan_hints)

 return 0;
 
 hints = kcalloc(FAT_SCAN_NWAY, sizeof(loff_t), GFP_KERNEL);
 if (!hints)
 err = -ENOMEM;
 
 down(MSDOS_I(dir)-scan_lock);
 /*
  * We allocated memory without scan_lock so lets make sure
  * no other thread completed hint_allocate() before us.
  */
 if (!MSDOS_I(dir)-scan_hints) {
 MSDOS_I(dir)-scan_hints = hints;
 hints = NULL;
 }
 up(MSDOS_I(dir)-scan_lock);
 
 kfree(hints);
 return err;
 }
 
 Pekka

-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[OGAWA Hirofumi]

Machida, Hiroyuki [EMAIL PROTECTED] writes:

 Right, it looks like TLB, which holds cache Physical addres
 correponding to Logical address. In this case, PID and file name
 to be looked up, perform role of Logical address.

But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?

e.g.

#define FAT_LOOKUP_HINT_MAX 16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*  int state;*/
};

static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, loff_t);
static int fat_lkup_hint_init(void);
-- 
OGAWA Hirofumi [EMAIL PROTECTED]
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][FAT] FAT dirent scan with hin take #3

[Machida, Hiroyuki]

OGAWA Hirofumi wrote:

Machida, Hiroyuki [EMAIL PROTECTED] writes:



Right, it looks like TLB, which holds cache Physical addres
correponding to Logical address. In this case, PID and file name
to be looked up, perform role of Logical address.



But, there is the big difference between hint table and TLB. TLB is
just the cache, and TLB hit is perfectly good, because kernel is
flushing the wrong values.

But this hint table is just collecting the recent access, it's not
cache, and it's not tracking the process's access at all.  So, since
the hint value is really random, the hint value may be bad.

I worry bad cases of this.


Umm... How about tracking the access pattern of process?  If that
seems randomly access, just give up tracking and return no hint.  And,
probably, I think it would be easy to improve the behavior later.

What do you think?


Sounds interesting...

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



e.g.

#define FAT_LOOKUP_HINT_MAX 16

/* this data per task */
struct fat_lookup_hint {
struct list_head lru;
pid_t pid;
struct super_block *sb;
struct inode *dir;
loff_t last_pos;
/*  int state;*/
};


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.

As implementation issue, if number of entires is small enough,
we can use an array, not a list.



static void fat_lkup_hint_inval(struct super_block *, struct inode *);
static loff_t fat_lkup_hint_get(struct super_block *, struct inode *);
static void fat_lkup_hint_add(struct super_block *, struct inode *, loff_t);
static int fat_lkup_hint_init(void);


I think super_block can be retrieved from inode, any other intention do
you have?


In addtion, we can do follwoing to check the exact match case;

0. Record hash value of file name in struct fat_lookup_hint

1. Check hash value to find exact match case,
1-1. If matched entry is found, check if file name and
 file name retieved from dirent corresponding
1-2. We found the entry

2. Get hint value, if there seem to have locality
2-1. Check locality of access pattern for this PID and this
 DIR.
2-2. If we relize access locality, return hit value so that
 it covers a potential working set.
2-3. Use hint value as start position of dirscan.

--
Hiroyuki Machida
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/