Skip to contentSkip to conversation

readdir on hash filesystems

PATCH Bob Copeland 2 participants 3 messages Sep 21, 2005 – Sep 22, 2005

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

Hi all,

I am writing a new filesystem driver for the filesystem used by the Rio Karma (and, as it happens, ReplayTV). See the attached patch and my webpage here for more info: http://bobcopeland.com/karma/. I have a
couple of newbie questions:

1) The directory structure implements a hash table where each directory has a fixed number of entries. Each entry is a file that has a pointer to another file in the hash chain and so there can be an unlimited number of files in any hash chain. What is the usual way to implement readdir efficiently in this case? With f_pos alone, I don't have any idea which node I want along the hash chain without counting up f_pos nodes in the tree.

2) Also, does there happen to be a way to use sb_bread to operate on more than 4k at a time? OMFS uses 8k blocks and a lot of the complexity in my driver involves operating on 512-byte blocks, loading new sectors when I hit a sector boundary, etc; reading 8k at a time would clean things up a little.

Subject: [PATCH] Added OMFS, the filesystem for Rio Karma

---

 fs/Kconfig       |    5 +
 fs/Makefile      |    1 
 fs/omfs/Makefile |    8 ++
 fs/omfs/dir.c    |  246 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/omfs/file.c   |  116 +++++++++++++++++++++++++
 fs/omfs/inode.c  |  151 +++++++++++++++++++++++++++++++++
 fs/omfs/omfs.h   |   94 +++++++++++++++++++++
 7 files changed, 621 insertions(+), 0 deletions(-)
 create mode 100644 fs/omfs/Makefile
 create mode 100644 fs/omfs/dir.c
 create mode 100644 fs/omfs/file.c
 create mode 100644 fs/omfs/inode.c
 create mode 100644 fs/omfs/omfs.h

075945081ae33a1825ce79317f5b3d5cba2592f2

fs/Kconfig +5 -0
@@ -1700,6 +1700,11 @@ config CODA_FS_OLD_API
 	  
 	  For most cases you probably want to say N.
 
+config OMFS_FS
+	tristate "OMFS (Rio Karma)"
+	help
+	  Say 'Y' to get support for the RIO Karma fs.
+
 config AFS_FS
 # for fs/nls/Config.in
 	tristate "Andrew File System support (AFS) (Experimental)"
fs/Makefile +1 -0
@@ -100,4 +100,5 @@ obj-$(CONFIG_AFS_FS)		+= afs/
 obj-$(CONFIG_BEFS_FS)		+= befs/
 obj-$(CONFIG_HOSTFS)		+= hostfs/
 obj-$(CONFIG_HPPFS)		+= hppfs/
+obj-$(CONFIG_OMFS_FS)		+= omfs/
 obj-$(CONFIG_DEBUG_FS)		+= debugfs/
fs/omfs/Makefile new file +8 -0
new file mode 100644
@@ -0,0 +1,8 @@
+#
+# Makefile for OMFS filesystem.
+#
+
+
+obj-$(CONFIG_OMFS_FS) += omfs.o
+
+omfs-objs := inode.o dir.o file.o
fs/omfs/dir.c new file +246 -0

246 lines not on this page · raw message

fs/omfs/file.c new file +116 -0

116 lines not on this page · raw message

fs/omfs/inode.c new file +151 -0

151 lines not on this page · raw message

fs/omfs/omfs.h new file +94 -0

94 lines not on this page · raw message

#1 lore raw
Quoted 8 lines · Bob Copeland

Hi all,

I am writing a new filesystem driver for the filesystem used by the Rio Karma (and, as it happens, ReplayTV). See the attached patch and my webpage here for more info: http://bobcopeland.com/karma/. I have a
couple of newbie questions:

Quoted 5 lines

1) The directory structure implements a hash table where each directory has a fixed number of entries. Each entry is a file that has a pointer to another file in the hash chain and so there can be an unlimited number of files in any hash chain. What is the usual way to implement readdir efficiently in this case? With f_pos alone, I don't

All file systems with hash-based directories I know of, treat hash collisions (a hash chain with more than one item) as some sort of exception, because they have large number of hash buckets. For your case where long hash chains are ordinary --because omfs has 201 hash buckets per directory (hard-coded value is bad, by the way)-- there is no "usual way", you have to invent one yourself.

Quoted 2 lines

have any idea which node I want along the hash chain without counting up f_pos nodes in the tree.

One possible solution is to use lower 24 bits of f_pos to store an index within given hash chain, and next 8 bits to store index of hash chain:

int hchain = file->f_pos >> 24 & 0xff;
int hindex = file->f_pos & 0xffffff;

Nikita.

#2 lore raw
Quoted 8 lines
Quoted 2 lines

have any idea which node I want along the hash chain without counting up f_pos nodes in the tree.

One possible solution is to use lower 24 bits of f_pos to store an index within given hash chain, and next 8 bits to store index of hash chain:

int hchain = file->f_pos >> 24 & 0xff;
int hindex = file->f_pos & 0xffffff;

Good idea, this works much better. In practice the chains are five
or six files long, so a few seeks on entry to readdir is not too bad, considering.

Thanks,
Bob