* [RFC][FAT] diren scan profiling report
@ 2005-08-30 3:01 Machida, Hiroyuki
2005-08-30 4:50 ` [PATCH][FAT] FAT dirent scan with hin take #2 Machida, Hiroyuki
0 siblings, 1 reply; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-30 3:01 UTC (permalink / raw)
To: linux-kernel, hirofumi
As I said in "[RFC] FAT dirent scan with hint"
<43024977.7020101@sm.sony.co.jp>, we realized that FAT/VFAT has
poor performance with scanning directory entries.
Per discussions with Ogawa-san, VFAT maintainer, I took profiling data
to seek better solution. Here are results attached.
In short, I would say we need to reduce following factors.
a) number of iterations inside fat_search_long()
b) number of callings to uni16_to_x8()
c) number of callings to fat__get_entry(), for short name scan.
In another E-mail, I'll send revised version patch which use hint
values to scan dirent. That patch would reduce number of iterations
inside fat_search_long() and fat_scan(). Those contributes reductions
above a)-c) factors.
RESULTS:
1-1) Top 10 function consuming time on long file name dir scan
(vfat_lookup) for 4095th LFN entry.
% kd -n 10 /tmp/lfn_kft-a.log
Function Count Time Average Local
----------------------------------- ----- -------- -------- --------
vfat_lookup 1 1242285 1242285 705
vfat_find 1 1241522 1241522 629
fat_search_long 1 1240893 1240893 887490
uni16_to_x8 4209 250222 59 249143
fat_get_entry 765 69908 91 3306
fat__get_entry 762 66602 87 50796
fat_shortname2uni 593 33158 55 11393
fat_short2lower_uni 414 21765 52 20860
fat_bmap 202 13425 66 857
fat_bmap_cluster 201 12568 62 1015
*)To exclude profiling overhead, doesn't count functions < 50usec
**) Remove "inline" from fat/dir.c to count up inline funcs.
1-2) Top 10 function consuming time on short file name dir scan
(fat_scan) for 4095th short file name entry.
% kd -n 10 /tmp/kft-a.log
Function Count Time Average Local
----------------------------------- ----- -------- -------- --------
fat_scan 1 149743 149743 68069
fat_get_short_entry 812 81512 100 11706
fat_get_entry 765 69806 91 3252
fat__get_entry 762 66554 87 50425
fat_bmap 199 13181 66 838
fat_bmap_cluster 198 12343 62 1055
fat_get_cluster 194 11288 58 8481
fat_ent_read 52 2807 53 2583
__getblk 32 2339 73 326
__bread 29 2145 73 598
*)To exclude profiling overhead, doesn't count functions < 50usec
**) Remove "inline" from fat/dir.c to count up inline funcs.
2-1) how to get result 1-1)
% ( cat <<__CONF
new
begin
trigger start entry 0xc00cd904 # vfat_lookup
trigger stop exit 0xc00cd904 # vfat_lookup
filter mintime 50
filter maxtime 0
filter noints
logentries 5000000
end
__CONF
) > /proc/kft
% echo prime > /proc/kft
# mount vtat
% time stat 4095th-shortfilename-entry
real 0m1.351s
user 0m0.007s
sys 0m1.295s
# umount
# get data from /proc/kft_data
2-2) how to get result 1-2)
% ( cat <<__CONF
new
begin
trigger start entry 0xc00c36dc # fat_scan
trigger stop exit 0xc00c36dc # fat_scan
filter mintime 50
filter maxtime 0
filter noints
logentries 5000000
end
__CONF
) > /proc/kft
% echo prime > /proc/kft
# mount msdos
% time stat 4095th-shortname-entry
real 0m0.216s
user 0m0.002s
sys 0m0.200s
# umount
# get data from /proc/kft_data
--
Hiroyuki Machida machida@sm.sony.co.jp
SSW Dept. HENC, Sony Corp.
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 3:01 [RFC][FAT] diren scan profiling report Machida, Hiroyuki
@ 2005-08-30 4:50 ` Machida, Hiroyuki
2005-08-30 8:51 ` Pekka Enberg
` (2 more replies)
0 siblings, 3 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-30 4:50 UTC (permalink / raw)
To: linux-kernel, hirofumi
[-- Attachment #1: Type: text/plain, Size: 1493 bytes --]
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 is for 2.6.12, because I tested it at the last weekend...
Machida, Hiroyuki wrote:
>
> As I said in "[RFC] FAT dirent scan with hint"
> <43024977.7020101@sm.sony.co.jp>, we realized that FAT/VFAT has
> poor performance with scanning directory entries.
>
> Per discussions with Ogawa-san, VFAT maintainer, I took profiling data
> to seek better solution. Here are results attached.
>
> In short, I would say we need to reduce following factors.
> a) number of iterations inside fat_search_long()
> b) number of callings to uni16_to_x8()
> c) number of callings to fat__get_entry(), for short name scan.
>
> In another E-mail, I'll send revised version patch which use hint
> values to scan dirent. That patch would reduce number of iterations
> inside fat_search_long() and fat_scan(). Those contributes reductions
> above a)-c) factors.
>
:
snip
:
--
Hiroyuki Machida machida@sm.sony.co.jp
SSW Dept. HENC, Sony Corp.
[-- Attachment #2: fat-dirscan-with-hint_2.patch --]
[-- Type: text/plain, Size: 6952 bytes --]
This patch enables using hint nformation on scanning dir.
It reaches excelent performance with "ls -l" for over 1000 entries.
* fat-dirscan-with-hint.patch
fs/fat/dir.c | 133 ++++++++++++++++++++++++++++++++++++++++++++---
fs/fat/inode.c | 13 ++++
include/linux/msdos_fs.h | 2
3 files changed, 140 insertions(+), 8 deletions(-)
Signed-off-by: Hiroyuki Machida <machida@sm.sony.co.jp> for CELF
* modified files
--- old/include/linux/msdos_fs.h 2005-08-29 09:38:53.308587787 +0900
+++ new/include/linux/msdos_fs.h 2005-08-29 09:39:33.889555606 +0900
@@ -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 */
--- old/fs/fat/dir.c 2005-08-29 09:38:53.158584210 +0900
+++ new/fs/fat/dir.c 2005-08-29 09:39:33.889555606 +0900
@@ -201,6 +201,91 @@ 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)
+
+
+DECLARE_MUTEX(hint_alloc_lock);
+
+inline
+static int hint_allocate(struct inode *dir)
+{
+ void *hints;
+ int err = 0;
+
+ if (!MSDOS_I(dir)->scan_hints) {
+ hints = kmalloc(FAT_SCAN_NWAY*sizeof(loff_t),GFP_KERNEL);
+ if (hints)
+ memset(hints, 0, FAT_SCAN_NWAY*sizeof(loff_t));
+ else
+ 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) {
+ if (hints) 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 +303,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 +372,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 +464,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 +940,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;
}
--- old/fs/fat/inode.c 2005-08-29 09:38:53.308587787 +0900
+++ new/fs/fat/inode.c 2005-08-29 09:39:33.889555606 +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;
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;
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 4:50 ` [PATCH][FAT] FAT dirent scan with hin take #2 Machida, Hiroyuki
@ 2005-08-30 8:51 ` Pekka Enberg
2005-08-30 8:55 ` Pekka Enberg
2005-08-30 19:27 ` OGAWA Hirofumi
2 siblings, 0 replies; 22+ messages in thread
From: Pekka Enberg @ 2005-08-30 8:51 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel, hirofumi
Hi,
Some coding style nitpicks.
On 8/30/05, Machida, Hiroyuki <machida@sm.sony.co.jp> wrote:
> +inline
> +static int hint_allocate(struct inode *dir)
> +{
> + void *hints;
> + int err = 0;
> +
> + if (!MSDOS_I(dir)->scan_hints) {
> + hints = kmalloc(FAT_SCAN_NWAY*sizeof(loff_t),GFP_KERNEL);
> + if (hints)
> + memset(hints, 0, FAT_SCAN_NWAY*sizeof(loff_t));
> + else
> + err = -ENOMEM;
Please consider using kcalloc().
> +
> + down(&MSDOS_I(dir)->scan_lock);
> + if (MSDOS_I(dir)->scan_hints) err = -EINVAL;
Please put the statement after if clause to a separate line. The above
makes code very hard to read.
> + if (!err) MSDOS_I(dir)->scan_hints = hints;
> + up(&MSDOS_I(dir)->scan_lock);
> + if (err == -EINVAL) {
> + if (hints) kfree(hints);
kfree() can handle NULLs just fine so please drop the redundant check.
Pekka
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 4:50 ` [PATCH][FAT] FAT dirent scan with hin take #2 Machida, Hiroyuki
2005-08-30 8:51 ` Pekka Enberg
@ 2005-08-30 8:55 ` Pekka Enberg
2005-08-30 9:18 ` Vojtech Pavlik
2005-08-30 19:27 ` OGAWA Hirofumi
2 siblings, 1 reply; 22+ messages in thread
From: Pekka Enberg @ 2005-08-30 8:55 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel, hirofumi
Hi,
Some more.
On 8/30/05, Machida, Hiroyuki <machida@sm.sony.co.jp> wrote:
> --- old/fs/fat/inode.c 2005-08-29 09:38:53.308587787 +0900
> +++ new/fs/fat/inode.c 2005-08-29 09:39:33.889555606 +0900
> @@ -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);
Please just make the local variable hints of type loff_t * to get rid
of the pointless casting.
>
> 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;
Use NULLs instead of 0 for pointers to keep new code sparse-clean.
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 8:55 ` Pekka Enberg
@ 2005-08-30 9:18 ` Vojtech Pavlik
0 siblings, 0 replies; 22+ messages in thread
From: Vojtech Pavlik @ 2005-08-30 9:18 UTC (permalink / raw)
To: Pekka Enberg; +Cc: Machida, Hiroyuki, linux-kernel, hirofumi
On Tue, Aug 30, 2005 at 11:55:46AM +0300, Pekka Enberg wrote:
> Hi,
>
> Some more.
>
> On 8/30/05, Machida, Hiroyuki <machida@sm.sony.co.jp> wrote:
> > --- old/fs/fat/inode.c 2005-08-29 09:38:53.308587787 +0900
> > +++ new/fs/fat/inode.c 2005-08-29 09:39:33.889555606 +0900
> > @@ -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);
>
> Please just make the local variable hints of type loff_t * to get rid
> of the pointless casting.
For voids no casting is needed anyway, the type exists for the very
reason of being compatible with any other.
> > 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;
>
> Use NULLs instead of 0 for pointers to keep new code sparse-clean.
It's a good idea for readability, too.
--
Vojtech Pavlik
SuSE Labs, SuSE CR
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 4:50 ` [PATCH][FAT] FAT dirent scan with hin take #2 Machida, Hiroyuki
2005-08-30 8:51 ` Pekka Enberg
2005-08-30 8:55 ` Pekka Enberg
@ 2005-08-30 19:27 ` OGAWA Hirofumi
2005-08-31 1:43 ` OGAWA Hirofumi
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
2 siblings, 2 replies; 22+ messages in thread
From: OGAWA Hirofumi @ 2005-08-30 19:27 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel
"Machida, Hiroyuki" <machida@sm.sony.co.jp> 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?
--
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #2
2005-08-30 19:27 ` OGAWA Hirofumi
@ 2005-08-31 1:43 ` OGAWA Hirofumi
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
1 sibling, 0 replies; 22+ messages in thread
From: OGAWA Hirofumi @ 2005-08-31 1:43 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp> writes:
> This patch couldn't compile. I assume you post a wrong patch...?
^^^^^
version
--
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-30 19:27 ` OGAWA Hirofumi
2005-08-31 1:43 ` OGAWA Hirofumi
@ 2005-08-31 8:25 ` Machida, Hiroyuki
2005-08-31 10:00 ` Pekka Enberg
` (3 more replies)
1 sibling, 4 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-31 8:25 UTC (permalink / raw)
To: OGAWA Hirofumi; +Cc: linux-kernel
[-- Attachment #1: Type: text/plain, Size: 2293 bytes --]
Sorry, I send out wrong version. I attached the latest patch to 2.6.13.
OGAWA Hirofumi wrote:
> "Machida, Hiroyuki" <machida@sm.sony.co.jp> 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.0 2.49
xargs-vfat 61.3 11.9
stat-vfat 41 17
stat-vfat-reverse 56 32
ls-msdos 14.2 0.62
xargs-msdos 16.8 16.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
[-- Attachment #2: fat-dirscan-with-hint_3.patch --]
[-- Type: text/plain, Size: 6936 bytes --]
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 <machida@sm.sony.co.jp> for CELF
* modified files
--- linux-2.6.13/fs/fat/dir.c 2005-08-29 08:41:01.000000000 +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<<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;
}
--- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.000000000 +0900
+++ linux-2.6.13-work/fs/fat/inode.c 2005-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;
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;
--- linux-2.6.13/include/linux/msdos_fs.h 2005-08-29 08:41:01.000000000 +0900
+++ linux-2.6.13-work/include/linux/msdos_fs.h 2005-08-31 12:58:30.090265918 +0900
@@ -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 */
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
@ 2005-08-31 10:00 ` Pekka Enberg
2005-08-31 12:57 ` Machida, Hiroyuki
2005-08-31 10:03 ` Pekka Enberg
` (2 subsequent siblings)
3 siblings, 1 reply; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 10:00 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: OGAWA Hirofumi, linux-kernel
Hi,
On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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; i<name_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
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
2005-08-31 10:00 ` Pekka Enberg
@ 2005-08-31 10:03 ` Pekka Enberg
2005-08-31 13:27 ` Machida, Hiroyuki
2005-08-31 10:14 ` Pekka Enberg
2005-08-31 16:41 ` OGAWA Hirofumi
3 siblings, 1 reply; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 10:03 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: OGAWA Hirofumi, linux-kernel
On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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<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);
Couldn't you use jhash() from <linux/jhash.h> here?
Pekka
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
2005-08-31 10:00 ` Pekka Enberg
2005-08-31 10:03 ` Pekka Enberg
@ 2005-08-31 10:14 ` Pekka Enberg
2005-08-31 13:04 ` Machida, Hiroyuki
2005-08-31 16:41 ` OGAWA Hirofumi
3 siblings, 1 reply; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 10:14 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: OGAWA Hirofumi, linux-kernel
Hi,
On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> wrote:
>
> Sorry, I send out wrong version. I attached the latest patch to 2.6.13.
>
> OGAWA Hirofumi wrote:
> > "Machida, Hiroyuki" <machida@sm.sony.co.jp> 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.0 2.49
> xargs-vfat 61.3 11.9
> stat-vfat 41 17
> stat-vfat-reverse 56 32
>
> ls-msdos 14.2 0.62
> xargs-msdos 16.8 16.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 <machida@sm.sony.co.jp> for CELF
>
> * modified files
>
>
> --- linux-2.6.13/fs/fat/dir.c 2005-08-29 08:41:01.000000000 +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<<FAT_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.000000000 +0900
> +++ linux-2.6.13-work/fs/fat/inode.c 2005-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?
> @@ -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.
Pekka
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 10:00 ` Pekka Enberg
@ 2005-08-31 12:57 ` Machida, Hiroyuki
2005-08-31 13:51 ` Pekka Enberg
0 siblings, 1 reply; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-31 12:57 UTC (permalink / raw)
To: Pekka Enberg; +Cc: linux-kernel, hirofumi
Hi,
Pekka Enberg wrote:
> Hi,
>
> On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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; i<name_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 machida@sm.sony.co.jp
SSW Dept. HENC, Sony Corp.
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 10:14 ` Pekka Enberg
@ 2005-08-31 13:04 ` Machida, Hiroyuki
2005-08-31 13:52 ` Pekka Enberg
0 siblings, 1 reply; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-31 13:04 UTC (permalink / raw)
To: Pekka Enberg; +Cc: OGAWA Hirofumi, linux-kernel
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 <machida@sm.sony.co.jp> for CELF
>>
>>* modified files
>>
>>
>>--- linux-2.6.13/fs/fat/dir.c 2005-08-29 08:41:01.000000000 +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<<FAT_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.000000000 +0900
>>+++ linux-2.6.13-work/fs/fat/inode.c 2005-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 majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
--
Hiroyuki Machida machida@sm.sony.co.jp
SSW Dept. HENC, Sony Corp.
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 10:03 ` Pekka Enberg
@ 2005-08-31 13:27 ` Machida, Hiroyuki
0 siblings, 0 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-08-31 13:27 UTC (permalink / raw)
To: Pekka Enberg; +Cc: OGAWA Hirofumi, linux-kernel
Pekka Enberg wrote:
> On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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<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);
>
>
> 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 machida@sm.sony.co.jp
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 12:57 ` Machida, Hiroyuki
@ 2005-08-31 13:51 ` Pekka Enberg
2005-08-31 13:53 ` Pekka Enberg
0 siblings, 1 reply; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 13:51 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel, hirofumi
On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 13:04 ` Machida, Hiroyuki
@ 2005-08-31 13:52 ` Pekka Enberg
0 siblings, 0 replies; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 13:52 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: OGAWA Hirofumi, linux-kernel
On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> 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
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 13:51 ` Pekka Enberg
@ 2005-08-31 13:53 ` Pekka Enberg
0 siblings, 0 replies; 22+ messages in thread
From: Pekka Enberg @ 2005-08-31 13:53 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel, hirofumi
On 8/31/05, Pekka Enberg <penberg@cs.helsinki.fi> 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
>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
` (2 preceding siblings ...)
2005-08-31 10:14 ` Pekka Enberg
@ 2005-08-31 16:41 ` OGAWA Hirofumi
2005-09-01 5:50 ` Machida, Hiroyuki
3 siblings, 1 reply; 22+ messages in thread
From: OGAWA Hirofumi @ 2005-08-31 16:41 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel
"Machida, Hiroyuki" <machida@sm.sony.co.jp> 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 <hirofumi@mail.parknet.co.jp>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-08-31 16:41 ` OGAWA Hirofumi
@ 2005-09-01 5:50 ` Machida, Hiroyuki
2005-09-01 7:45 ` Machida, Hiroyuki
2005-09-01 17:48 ` OGAWA Hirofumi
0 siblings, 2 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-09-01 5:50 UTC (permalink / raw)
To: OGAWA Hirofumi; +Cc: linux-kernel
OGAWA Hirofumi wrote:
> "Machida, Hiroyuki" <machida@sm.sony.co.jp> 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
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-09-01 5:50 ` Machida, Hiroyuki
@ 2005-09-01 7:45 ` Machida, Hiroyuki
2005-09-01 17:48 ` OGAWA Hirofumi
1 sibling, 0 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-09-01 7:45 UTC (permalink / raw)
To: OGAWA Hirofumi; +Cc: Machida, Hiroyuki, linux-kernel
Machida, Hiroyuki wrote:
> OGAWA Hirofumi wrote:
>
>> "Machida, Hiroyuki" <machida@sm.sony.co.jp> 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_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
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-09-01 5:50 ` Machida, Hiroyuki
2005-09-01 7:45 ` Machida, Hiroyuki
@ 2005-09-01 17:48 ` OGAWA Hirofumi
2005-09-14 18:59 ` Machida, Hiroyuki
1 sibling, 1 reply; 22+ messages in thread
From: OGAWA Hirofumi @ 2005-09-01 17:48 UTC (permalink / raw)
To: Machida, Hiroyuki; +Cc: linux-kernel
[-- Attachment #1: Type: text/plain, Size: 911 bytes --]
"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>
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fat_lookup-hint.patch --]
[-- Type: text/x-patch, Size: 6172 bytes --]
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);
_
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH][FAT] FAT dirent scan with hin take #3
2005-09-01 17:48 ` OGAWA Hirofumi
@ 2005-09-14 18:59 ` Machida, Hiroyuki
0 siblings, 0 replies; 22+ messages in thread
From: Machida, Hiroyuki @ 2005-09-14 18:59 UTC (permalink / raw)
To: OGAWA Hirofumi; +Cc: linux-kernel
[-- Attachment #1: Type: text/plain, Size: 2393 bytes --]
OGAWA Hirofumi wrote:
:
>
>
> 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.
Sorry late, at the last weekend I looked into the patch you post and run it.
I got your idea, now. I would propose following changes on it and attached
modified patch into this mail.
1. The original patch has system wide 16 entries access-tracking buffer.
I modified system has one access-tracking buffer for each mounted FS instance.
And it allocates the buffer on mounting as a part of FS dependent super block.
2. On looking up hints, the original patch try to find the entry which has
same pid and dir. If matched entry is not found, it uses always zero.
However we can expect locality beyond process, so I changes a little bit,
behavior of fail to find the matched entry.
try to find the entry which has same pid and dir.
if matched entry is not found, try to find recent access to same dir.
3. With the original code, the access-tracking buffer can hold just one entry
for one pid. I think it is better to have few entries for one pid.
I modified patch to have up to 3 entires (less than 1/4 of total entries) for
each pid.
4. Originally window size to determine locality seems wide due to using max len
of LFN(MSDOS_SLOTS), like;
WIN_BOTTOM = 5 * MSDOS_SLOTS * size of entry
We can use the value based on statistic instead of MSDOS_SLOTS. I checked with
my FC3 installed system, most files(over 99%) have less than or equal to 48
chars file name length. So use 9 instead of 21(MSDOS_SLOTS)
5. Adding short name entry support.
And I have fixed a bug which makes infinite loop on lookup empty dir
after all files were removed.
> However, these lookup-hint approaches seems the hack after all....
> Hhmmm...
I have another idea as following;
On reading blocks ahead, try to build dentry caches for all FAT dir entries
which reside in those blocks. And start dir-scan at some position
close to bottom of the latest read-ahead block, instead of zero.
However, I guess this tends to consume dentry caches and it may have affects
on other area.
As you said, I think "lookup-hint" is hack, but not so bad. Because it has
no side effect to other area and memory consumption is predictable.
--
Hiroyuki Machida
[-- Attachment #2: fat_lookup-hint_1.patch --]
[-- Type: text/plain, Size: 10194 bytes --]
Signed-off-by: Hiroyuki Machida <machida@sm.sony.co.jp>
Signed-off-by: OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>
---
fs/fat/dir.c | 232 ++++++++++++++++++++++++++++++++++++++++++++---
fs/fat/inode.c | 7 +
include/linux/msdos_fs.h | 19 +++
3 files changed, 246 insertions(+), 12 deletions(-)
diff -r -up linux-2.6.13/fs/fat/dir.c linux-2.6.13-scan2/fs/fat/dir.c
--- linux-2.6.13/fs/fat/dir.c 2005-08-29 08:41:01.000000000 +0900
+++ linux-2.6.13-scan2/fs/fat/dir.c 2005-09-14 17:20:38.220767449 +0900
@@ -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
--- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.000000000 +0900
+++ linux-2.6.13-scan2/fs/fat/inode.c 2005-09-14 17:24:21.446091170 +0900
@@ -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
--- linux-2.6.13/include/linux/msdos_fs.h 2005-08-29 08:41:01.000000000 +0900
+++ linux-2.6.13-scan2/include/linux/msdos_fs.h 2005-09-14 17:22:38.223629408 +0900
@@ -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 */
^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2005-09-14 19:02 UTC | newest]
Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-08-30 3:01 [RFC][FAT] diren scan profiling report Machida, Hiroyuki
2005-08-30 4:50 ` [PATCH][FAT] FAT dirent scan with hin take #2 Machida, Hiroyuki
2005-08-30 8:51 ` Pekka Enberg
2005-08-30 8:55 ` Pekka Enberg
2005-08-30 9:18 ` Vojtech Pavlik
2005-08-30 19:27 ` OGAWA Hirofumi
2005-08-31 1:43 ` OGAWA Hirofumi
2005-08-31 8:25 ` [PATCH][FAT] FAT dirent scan with hin take #3 Machida, Hiroyuki
2005-08-31 10:00 ` Pekka Enberg
2005-08-31 12:57 ` Machida, Hiroyuki
2005-08-31 13:51 ` Pekka Enberg
2005-08-31 13:53 ` Pekka Enberg
2005-08-31 10:03 ` Pekka Enberg
2005-08-31 13:27 ` Machida, Hiroyuki
2005-08-31 10:14 ` Pekka Enberg
2005-08-31 13:04 ` Machida, Hiroyuki
2005-08-31 13:52 ` Pekka Enberg
2005-08-31 16:41 ` OGAWA Hirofumi
2005-09-01 5:50 ` Machida, Hiroyuki
2005-09-01 7:45 ` Machida, Hiroyuki
2005-09-01 17:48 ` OGAWA Hirofumi
2005-09-14 18:59 ` Machida, Hiroyuki
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).