Skip to contentSkip to conversation

fat: eliminate iterations in fat_search_long and __fat_readdir in case of EOD

PATCH In review Namjae Jeon 2 participants 5 messages Feb 4, 2013 – Feb 9, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 fat: eliminate iterations in fat_search_long and __fat_readdir in case of EOD

From: Namjae Jeon <[email protected]>

When doing lookups via fat_search_long(), we can stop checking for further entries if we detect End of Directory, i.e. if (de->name[0] == 0x00).The current code traverses the cluster chain of a directory until a hit is found or till the last cluster for that directory, ignoring the EOD mark. Fix this.

Likewise,when readdir(3) is called, we can stop checking for further entries in __fat_readdir() when we hit EOD.

---
 fs/fat/dir.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
fs/fat/dir.c +4 -4
index 58bf744..78dabf00 100644
@@ -484,10 +484,10 @@ parse_record:
 		nr_slots = 0;
 		if (de->name[0] == DELETED_FLAG)
 			continue;
+		if (!de->name[0])
+			goto end_of_dir;
 		if (de->attr != ATTR_EXT && (de->attr & ATTR_VOLUME))
 			continue;
-		if (de->attr != ATTR_EXT && IS_FREE(de->name))
-			continue;
 		if (de->attr == ATTR_EXT) {
 			int status = fat_parse_long(inode, &cpos, &bh, &de,
 						    &unicode, &nr_slots);
@@ -608,8 +608,8 @@ parse_record:
 			goto record_end;
 		if (de->attr != ATTR_EXT && (de->attr & ATTR_VOLUME))
 			goto record_end;
-		if (de->attr != ATTR_EXT && IS_FREE(de->name))
-			goto record_end;
+		if (!de->name[0])
+			goto end_of_dir;
 	} else {
 		if ((de->attr & ATTR_VOLUME) || IS_FREE(de->name))
 			goto record_end;
Signature · 1 line
1.7.9.5
maintainer
#1 lore raw
Quoted 10 lines · Namjae Jeon

From: Namjae Jeon <[email protected]>

When doing lookups via fat_search_long(), we can stop checking for further entries if we detect End of Directory, i.e. if (de->name[0] == 0x00).The current code traverses the cluster chain of a directory until a hit is found or till the last cluster for that directory, ignoring the EOD mark. Fix this.

Likewise,when readdir(3) is called, we can stop checking for further entries in __fat_readdir() when we hit EOD.

Don't we need to change fat_get_short_entry()? And did this work correctly about f_pos for readdir?

I'm not thinking about f_pos deeply though, it may have something wrong. Because it stops at middle of cluster.

Thanks.

Signature · 1 line
OGAWA Hirofumi <[email protected]>
#2 lore raw

2013/2/7, OGAWA Hirofumi <[email protected]>:

Quoted 11 lines
Quoted 9 lines · Namjae Jeon

From: Namjae Jeon <[email protected]>

When doing lookups via fat_search_long(), we can stop checking for further entries if we detect End of Directory, i.e. if (de->name[0] == 0x00).The current code traverses the cluster chain of a directory until a hit
is found or till the last cluster for that directory, ignoring the EOD mark. Fix this.

Quoted 3 lines
Quoted 2 lines

Likewise,when readdir(3) is called, we can stop checking for further entries in __fat_readdir() when we hit EOD.

Hi OGAWA.

Quoted 1 line

Don't we need to change fat_get_short_entry()?

Yes, We need to change here. Thanks for review!

Quoted 1 line

And did this work correctly about f_pos for readdir?

Yes, sure. f_pos is work correctly about each directory entry. because after name[0] == 0x00, there are no allocated directory entires.

Quoted 3 lines

I'm not thinking about f_pos deeply though, it may have something wrong. Because it stops at middle of cluster.

Plz See the below descirption about name[0] in FAT spec.
---------------------------------------------------------------------------------------------------------------------
If DIR_Name[0] == 0x00, then the directory entry is free (same as for 0xE5), and there are no allocated directory entries after this one (all of the DIR_Name[0] bytes in all of the entries after this one are also set to 0).
The special 0 value, rather than the 0xE5 value, indicates to FAT file system driver code that the rest of the entries in this directory do not need to be examined because they are all free.
-----------------------------------------------------------------------------------------------------------------------

I think that lookuping entry till the end of cluster is not needed. Let me know your opinion.

And Would you tell me your opinion about fat exportfs ? Thanks!

Quoted 5 lines

Thanks.
--
OGAWA Hirofumi <[email protected]>

maintainer
#3 lore raw
Quoted 17 lines · Namjae Jeon
Quoted 1 line

And did this work correctly about f_pos for readdir?

Yes, sure. f_pos is work correctly about each directory entry. because after name[0] == 0x00, there are no allocated directory entires.

Quoted 3 lines

I'm not thinking about f_pos deeply though, it may have something wrong. Because it stops at middle of cluster.

Plz See the below descirption about name[0] in FAT spec.
---------------------------------------------------------------------------------------------------------------------
If DIR_Name[0] == 0x00, then the directory entry is free (same as for 0xE5), and there are no allocated directory entries after this one (all of the DIR_Name[0] bytes in all of the entries after this one are also set to 0).
The special 0 value, rather than the 0xE5 value, indicates to FAT file system driver code that the rest of the entries in this directory do not need to be examined because they are all free.
-----------------------------------------------------------------------------------------------------------------------

Quoted 2 lines

I think that lookuping entry till the end of cluster is not needed. Let me know your opinion.

I know it though. There is seek() and broken drivers adds entries after name[0] == 0. I think we don't need to care much about broken drivers though. Even if so, kernel should not be crash, and corrupts fs more.

Quoted 1 line

And Would you tell me your opinion about fat exportfs ?

Ah, I was thinking I did. But it seems I didn't actually. Can you post full of series? So, I can review and probably we can start to test it.

Thanks.

Signature · 1 line
OGAWA Hirofumi <[email protected]>
#4 lore raw

2013/2/8, OGAWA Hirofumi <[email protected]>:

Quoted 19 lines
Quoted 17 lines · Namjae Jeon
Quoted 1 line

And did this work correctly about f_pos for readdir?

Yes, sure. f_pos is work correctly about each directory entry. because after name[0] == 0x00, there are no allocated directory entires.

Quoted 3 lines

I'm not thinking about f_pos deeply though, it may have something wrong. Because it stops at middle of cluster.

Plz See the below descirption about name[0] in FAT spec.
---------------------------------------------------------------------------------------------------------------------
If DIR_Name[0] == 0x00, then the directory entry is free (same as for 0xE5), and there are no allocated directory entries after this one (all of the DIR_Name[0] bytes in all of the entries after this one are also set to 0).
The special 0 value, rather than the 0xE5 value, indicates to FAT file system driver code that the rest of the entries in this directory do not need to be examined because they are all free.
-----------------------------------------------------------------------------------------------------------------------

Quoted 6 lines
Quoted 2 lines

I think that lookuping entry till the end of cluster is not needed. Let me know your opinion.

I know it though. There is seek() and broken drivers adds entries after name[0] == 0. I think we don't need to care much about broken drivers though. Even if so, kernel should not be crash, and corrupts fs more.

Yes, Right. I understood. Plz ignore this patch.

Quoted 5 lines
Quoted 2 lines

And Would you tell me your opinion about fat exportfs ?

Ah, I was thinking I did. But it seems I didn't actually. Can you post full of series? So, I can review and probably we can start to test it.

Okay, I will post full patch-set today.

Thanks OGAWA.

Quoted 5 lines

Thanks.
--
OGAWA Hirofumi <[email protected]>