readdir on hash filesystems

readdir on hash filesystems

[Bob Copeland]

[-- Attachment #1: Type: text/plain, Size: 1013 bytes --]

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.

[-- Attachment #2: 0003-Added-OMFS-the-filesystem-for-Rio-Karma.txt --]
[-- Type: text/plain, Size: 15673 bytes --]

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
diff --git a/fs/Kconfig b/fs/Kconfig
--- a/fs/Kconfig
+++ b/fs/Kconfig
@@ -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)"
diff --git a/fs/Makefile b/fs/Makefile
--- a/fs/Makefile
+++ b/fs/Makefile
@@ -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/
diff --git a/fs/omfs/Makefile b/fs/omfs/Makefile
new file mode 100644
--- /dev/null
+++ b/fs/omfs/Makefile
@@ -0,0 +1,8 @@
+#
+# Makefile for OMFS filesystem.
+#
+
+
+obj-$(CONFIG_OMFS_FS) += omfs.o
+
+omfs-objs := inode.o dir.o file.o
diff --git a/fs/omfs/dir.c b/fs/omfs/dir.c
new file mode 100644
--- /dev/null
+++ b/fs/omfs/dir.c
@@ -0,0 +1,246 @@
+/*
+ * fs/omfs/dir.c
+ * OMFS (as used by RIO Karma) directory operations.
+ * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com>
+ */
+
+#include <linux/config.h>
+#include <linux/fs.h>
+#include <linux/ctype.h>
+#include <linux/buffer_head.h>
+#include "omfs.h"
+
+static int omfs_hash(const char *name, int namelen, int mod)
+{
+	int i, hash=0;
+	for (i=0; i<namelen; i++)
+		hash ^= tolower(name[i]) << (i % 24);
+	return hash % mod;
+}
+
+static struct buffer_head *omfs_find_entry(struct inode *dir,
+					   const char *name, int namelen)
+{
+	struct buffer_head *bh;
+	struct omfs_inode *oi;
+	loff_t ptr;
+	u64 cluster;
+
+	int block = clus_to_blk(dir->i_ino);
+	int bucket = omfs_hash(name, namelen, 201);
+
+	ptr = OMFS_DIR_START + bucket * 8;
+	block += ptr >> dir->i_sb->s_blocksize_bits;
+	int ofs = ptr & (dir->i_sb->s_blocksize - 1);
+
+	bh = sb_bread(dir->i_sb, block);
+	cluster = be32_to_cpu(*((u32 *) & bh->b_data[ofs + 4]));
+	brelse(bh);
+	while (cluster != ~0) {
+		bh = sb_bread(dir->i_sb, clus_to_blk(cluster));
+		if (!bh)
+			goto out;
+
+		oi = (struct omfs_inode *)bh->b_data;
+		if (strncmp(oi->name, name, namelen) == 0) {
+			return bh;
+		}
+		cluster = be32_to_cpu(oi->sibling);
+		brelse(bh);
+	}
+out:
+	return 0;
+}
+
+static struct dentry *omfs_lookup(struct inode *dir, struct dentry *dentry,
+				  struct nameidata *nd)
+{
+	struct buffer_head *bh;
+	struct inode *inode = NULL;
+
+	if (dentry->d_name.len > OMFS_NAMELEN)
+		return ERR_PTR(-ENAMETOOLONG);
+
+	bh = omfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len);
+	if (bh) {
+		struct omfs_inode *oi = (struct omfs_inode *)bh->b_data;
+		ino_t ino = be32_to_cpu(oi->head.self);
+		brelse(bh);
+		inode = iget(dir->i_sb, ino);
+		if (!inode) {
+			return ERR_PTR(-EINVAL);	
+		}
+	}
+	d_add(dentry, inode);
+	return NULL;
+}
+
+#if 1
+static int omfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
+{
+	struct inode *dir = filp->f_dentry->d_inode;
+	struct buffer_head *bh, *bh2;
+	struct omfs_inode *oi;
+	loff_t bl_ofs;
+	loff_t offset, pos, res;
+	u32 cluster;
+	unsigned char d_type;
+	ino_t self;
+
+	switch (filp->f_pos) {
+	case 0:
+		if (filldir(dirent, ".", 1, 0, dir->i_ino, DT_DIR) < 0) 
+			goto out;
+		filp->f_pos++;
+		/* fall through */
+	case 1:
+		if (filldir(dirent, "..", 2, 1, parent_ino(filp->f_dentry), DT_DIR) < 0) 
+			goto out;
+		filp->f_pos++;
+		/* fall through */
+	}
+
+	/* this is not at all efficient. :( count the nodes until we hit
+	 * f_pos or end
+	 */
+	pos = 2;
+
+	bh = sb_bread(dir->i_sb, clus_to_blk(dir->i_ino));
+	if (!bh)
+		goto no_bh;
+
+	for (offset = OMFS_DIR_START; offset < dir->i_size; offset += 8) {
+		sector_t block = offset >> dir->i_sb->s_blocksize_bits;
+		bl_ofs = offset & (dir->i_sb->s_blocksize - 1);
+		if (!bl_ofs) { // wrapped a block
+			brelse(bh);
+			bh = sb_bread(dir->i_sb, block + clus_to_blk(dir->i_ino));
+			if (!bh) 
+				goto no_bh;
+		}
+		cluster = be32_to_cpu(*((u32 *) & bh->b_data[bl_ofs + 4]));
+		while (cluster != ~0) {
+			bh2 = sb_bread(dir->i_sb, clus_to_blk(cluster));
+			if (!bh2)
+				goto no_bh2;
+
+			oi = (struct omfs_inode *)bh2->b_data;
+			self = cluster;
+			cluster = be32_to_cpu(oi->sibling);
+
+			if (pos++ < filp->f_pos) {
+				brelse(bh2);
+				continue;
+			}
+
+			if (oi->type == OMFS_DIR)
+				d_type = DT_DIR;
+			else
+				d_type = DT_REG;
+
+			res = filldir(dirent, oi->name, strnlen(oi->name, 
+				OMFS_NAMELEN), filp->f_pos, self, d_type);
+			brelse(bh2);
+			if (res < 0) 
+			{
+				brelse(bh);
+				return 0;
+			}
+			filp->f_pos++;
+		}
+	}
+	brelse(bh);
+out:
+	return 0;
+no_bh2:
+	brelse(bh);
+no_bh:
+	return -EINVAL;
+}
+
+#else
+
+static int omfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
+{
+	struct inode *dir = filp->f_dentry->d_inode;
+	struct buffer_head *bh, *bh2;
+	struct omfs_inode *oi;
+	loff_t bl_ofs;
+	int ret = 0;
+
+	switch (filp->f_pos) {
+	case 0:
+		if (filldir(dirent, ".", 1, 0, dir->i_ino, DT_DIR) < 0) 
+			goto out;
+		filp->f_pos++;
+		/* fall through */
+	case 1:
+		if (filldir(dirent, "..", 2, 1, parent_ino(filp->f_dentry), DT_DIR) < 0) 
+			goto out;
+		filp->f_pos++;
+		/* fall through */
+	}
+
+	loff_t offset = filp->f_pos + OMFS_DIR_START - 2 ;
+
+	while (offset < dir->i_size) {
+		sector_t block = offset >> dir->i_sb->s_blocksize_bits;
+		bl_ofs = offset & (dir->i_sb->s_blocksize - 1);
+
+		bh = sb_bread(dir->i_sb, block + clus_to_blk(dir->i_ino));
+		if (!bh) {
+			ret = -EINVAL;
+			goto out;
+		}
+		do {
+			unsigned char d_type = DT_DIR;
+			u64 cluster =
+				be64_to_cpu(*((u64 *) & bh->b_data[bl_ofs]));
+			if (cluster != ~0) {
+				bh2 = sb_bread(dir->i_sb,
+						 clus_to_blk(cluster));
+				if (!bh2) {
+					ret = -EINVAL;
+					goto out;
+				}
+
+				printk(KERN_DEBUG "%llx\n", cluster);
+
+				oi = (struct omfs_inode *)bh2->b_data;
+				if (oi->type == OMFS_DIR)
+					d_type = DT_DIR;
+				else
+					d_type = DT_REG;
+
+				ret = filldir(dirent, oi->name,
+					strnlen(oi->name, OMFS_NAMELEN),
+					filp->f_pos, cluster, d_type);
+				brelse(bh2);
+				if (ret < 0) 
+				{
+					brelse(bh);
+					return 0;
+				}
+			}
+			offset += 8;
+			bl_ofs += 8;
+			filp->f_pos += 8;
+
+		} while (offset < dir->i_size &&
+			 bl_ofs < dir->i_sb->s_blocksize);
+		brelse(bh);
+	}
+out:
+	return ret;
+}
+
+#endif
+
+struct inode_operations omfs_dir_inops = {
+	.lookup = omfs_lookup,
+};
+
+struct file_operations omfs_dir_operations = {
+	.read = generic_read_dir,
+	.readdir = omfs_readdir,
+};
diff --git a/fs/omfs/file.c b/fs/omfs/file.c
new file mode 100644
--- /dev/null
+++ b/fs/omfs/file.c
@@ -0,0 +1,116 @@
+/*
+ * fs/omfs/file.c
+ * OMFS (as used by RIO Karma) file operations.
+ * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com>
+ */
+
+#include <linux/config.h>
+#include <linux/fs.h>
+#include <linux/buffer_head.h>
+#include "omfs.h"
+
+/* 
+ * Scans across the directory table for a given block number.  There are 
+ * several possible exit conditions: 
+ * 1) we find the cluster and return it
+ * 2) count is zero (for this table); we return 0 and *count is zero.
+ * 3) no more pointers on this page (but more in table); return 0 and
+ * *count is non-zero.  caller must repeat with ent on next block.
+ */
+static sector_t find_block(struct inode *inode, struct omfs_extent_entry *ent, 
+	 	       sector_t block, sector_t *searched,
+		       int block_ofs, int *count)
+{
+	for (; *count > 0 && block_ofs < inode->i_sb->s_blocksize; 
+		*count--, block_ofs += sizeof(struct omfs_extent_entry))
+	{
+		int numblocks = clus_to_blk(be32_to_cpu(ent->blocks));
+		if (block >= *searched  && 
+		    block < (*searched + numblocks))
+		{
+			// found it at cluster + (block - searched)
+			return clus_to_blk(be32_to_cpu(ent->cluster)) + 
+				block - *searched;
+		}
+		*searched += numblocks;
+		ent++;
+	}
+	return 0;
+}
+
+static int omfs_get_block(struct inode *inode, sector_t block,
+			  struct buffer_head *bh_result, int create)
+{
+	struct buffer_head *bh;
+	sector_t next, block_start, offset, searched=0;
+	int block_ofs;
+	struct omfs_extent *oe;
+	struct omfs_extent_entry *entry;
+	if (create)
+		goto err;
+
+	if (block < 0)		// || > stuff
+		goto err;
+
+	block_start = clus_to_blk(inode->i_ino);
+	bh = sb_bread(inode->i_sb, block_start);
+	if (!bh)
+		goto err;
+
+	oe = (struct omfs_extent *)(&bh->b_data[0x1d0]);
+
+	for(;;) {
+		int count = be32_to_cpu(oe->extent_count);
+		next = be32_to_cpu(oe->next);
+		entry = &oe->entry;
+		block_ofs = (long) entry - (long)bh->b_data;
+
+		while (count > 0) {
+			offset = find_block(inode, entry, block, &searched, 
+					block_ofs, &count);
+			if (offset > 0) {
+				brelse(bh);
+				map_bh(bh_result, inode->i_sb, offset);
+				return 0;
+			}
+			if (count) {
+				// spilled over a buffer
+				brelse(bh);
+				bh = sb_bread(inode->i_sb, ++block_start);
+				if (!bh) goto err;
+				entry = (struct omfs_extent_entry *) bh->b_data;
+				block_ofs = 0;
+			}
+		}
+		brelse(bh);
+
+		if (next == ~0)
+			break;
+
+		bh = sb_bread(inode->i_sb, next);
+		if (!bh) goto err;
+		oe = (struct omfs_extent *) (&bh->b_data[0x40]);
+	}
+
+	return 0;
+err:
+	return -EIO;
+}
+
+static int omfs_readpage(struct file *file, struct page *page)
+{
+	return block_read_full_page(page, omfs_get_block);
+}
+
+struct file_operations omfs_file_operations = {
+	.llseek = generic_file_llseek,
+	.read = generic_file_read,
+	.write = generic_file_write,
+	.mmap = generic_file_mmap,
+	.sendfile = generic_file_sendfile,
+};
+
+struct address_space_operations omfs_aops = {
+	.readpage = omfs_readpage,
+};
+
diff --git a/fs/omfs/inode.c b/fs/omfs/inode.c
new file mode 100644
--- /dev/null
+++ b/fs/omfs/inode.c
@@ -0,0 +1,151 @@
+/*
+ * fs/omfs/inode.c
+ * OMFS (as used by RIO Karma) inode and super operations.
+ * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com>
+ */
+
+#include <linux/config.h>
+#include <linux/module.h>
+#include <linux/fs.h>
+#include <linux/vfs.h>
+#include <linux/buffer_head.h>
+#include "omfs.h"
+
+MODULE_AUTHOR("Bob Copeland <me@bobcopeland.com>");
+MODULE_DESCRIPTION("OMFS (ReplayTV/Karma) Filesystem for Linux");
+MODULE_LICENSE("GPL");
+
+void omfs_read_inode(struct inode *inode)
+{
+	struct omfs_inode *oi;
+	struct buffer_head *bh;
+	unsigned int block;
+	ino_t ino = inode->i_ino;
+
+	// check against num_blocks
+	block = clus_to_blk(ino);
+	bh = sb_bread(inode->i_sb, block);
+	if (!bh) {
+		make_bad_inode(inode);
+		return;
+	}
+
+	oi = (struct omfs_inode *)bh->b_data;
+
+	// check self
+	if (ino != be32_to_cpu(oi->head.self)) {
+		make_bad_inode(inode);
+		return;
+	}
+
+	inode->i_uid = 0;
+	inode->i_gid = 0;
+
+	long secs = ((long)be64_to_cpu(oi->ctime)) / 1000;
+	long nsecs = ((long)be64_to_cpu(oi->ctime)) % 1000;
+
+	inode->i_atime.tv_sec = secs;
+	inode->i_mtime.tv_sec = secs;
+	inode->i_ctime.tv_sec = secs;
+	inode->i_atime.tv_nsec = nsecs;
+	inode->i_mtime.tv_nsec = nsecs;
+	inode->i_ctime.tv_nsec = nsecs;
+
+	if (oi->type == OMFS_DIR) {
+		inode->i_mode = S_IFDIR | S_IRUGO | S_IXUGO;
+		inode->i_mode |= S_IFDIR;
+		inode->i_op = &omfs_dir_inops;
+		inode->i_fop = &omfs_dir_operations;
+		inode->i_size = (loff_t) be32_to_cpu(oi->head.body_size) +
+			sizeof(struct omfs_header);
+	} else if (oi->type == OMFS_FILE) {
+		inode->i_mode = S_IFREG | S_IRUGO;
+		inode->i_mapping->a_ops = &omfs_aops;
+		inode->i_fop = &omfs_file_operations;
+		inode->i_size = (loff_t) be64_to_cpu(oi->size);
+	}
+	brelse(bh);
+}
+
+struct super_operations omfs_sops = {
+	.read_inode = omfs_read_inode,
+};
+
+static int omfs_fill_super(struct super_block *sb, void *data, int silent)
+{
+	struct buffer_head *bh, *bh2;
+	struct omfs_super_block *omfs_sb;
+	struct omfs_root_block *omfs_rb;
+	struct inode *root;
+
+	sb->s_flags |= MS_RDONLY;
+	sb->s_maxbytes = 0xffffffff;
+
+	sb_set_blocksize(sb, 0x200);
+
+	if (!(bh = sb_bread(sb, 0)))
+		goto out;
+
+	omfs_sb = (struct omfs_super_block *)bh->b_data;
+	if (be32_to_cpu(omfs_sb->magic) != OMFS_MAGIC) {
+		if (!silent)
+			printk(KERN_ERR "omfs: Invalid superblock (%x)\n",
+				   omfs_sb->magic);
+		goto out;
+	}
+	sb->s_magic = OMFS_MAGIC;
+
+	sector_t start = clus_to_blk(be32_to_cpu(omfs_sb->root_block));
+	if (!(bh2 = sb_bread(sb, start)))
+		goto out;
+
+	omfs_rb = (struct omfs_root_block *)bh2->b_data;
+	printk(KERN_DEBUG "omfs: volume: %s\n", omfs_rb->name);
+
+	sb->s_op = &omfs_sops;
+	root = iget(sb, be32_to_cpu(omfs_rb->root_dir));
+
+	brelse(bh);
+	brelse(bh2);
+
+	sb->s_root = d_alloc_root(root);
+	if (!sb->s_root) {
+		iput(root);
+		goto out;
+	}
+
+	return 0;
+
+out:
+	// fixup brelses
+	return -EINVAL;
+}
+
+static struct super_block *omfs_get_sb(struct file_system_type *fs_type,
+					   int flags, const char *dev_name,
+					   void *data)
+{
+	return get_sb_bdev(fs_type, flags, dev_name, data, omfs_fill_super);
+}
+
+static struct file_system_type omfs_fs_type = {
+	.owner = THIS_MODULE,
+	.name = "omfs",
+	.get_sb = omfs_get_sb,
+	.kill_sb = kill_block_super,
+	.fs_flags = FS_REQUIRES_DEV,
+};
+
+static int __init init_omfs_fs(void)
+{
+	register_filesystem(&omfs_fs_type);
+	return 0;
+}
+
+static void __exit exit_omfs_fs(void)
+{
+	unregister_filesystem(&omfs_fs_type);
+}
+
+module_init(init_omfs_fs);
+module_exit(exit_omfs_fs);
diff --git a/fs/omfs/omfs.h b/fs/omfs/omfs.h
new file mode 100644
--- /dev/null
+++ b/fs/omfs/omfs.h
@@ -0,0 +1,94 @@
+#ifndef _OMFS_H
+#define _OMFS_H
+
+#include <linux/config.h>
+
+#define OMFS_MAGIC 0xC2993D87
+#define OMFS_DIR 'D'
+#define OMFS_FILE 'F'
+#define OMFS_NAMELEN 256
+#define OMFS_DIR_START 0x1b8
+
+struct omfs_super_block {
+	char fill1[256];
+	u32 fill2;
+	u32 root_block;
+	u64 num_blocks;
+	u32 magic;
+	u32 blocksize;
+	u32 mirrors;
+	u32 sys_blocksize;
+};
+
+struct omfs_header {
+	u32 fill1;
+	u32 self;
+	u32 body_size;
+	u16 crc;
+	char fill2[5];
+	u8 check_xor;
+	u32 fill3;
+};
+
+struct omfs_root_block {
+	struct omfs_header head;
+	u64 fill3;
+	u64 num_blocks;
+	u32 fill4;
+	u32 root_dir;
+	u64 fill5;
+	u32 blocksize;
+	u32 clustersize;
+	u64 mirrors;
+	char name[OMFS_NAMELEN];
+};
+
+struct omfs_inode {
+	struct omfs_header head;
+	u32 fill1;
+	u32 parent;
+	u32 fill2;
+	u32 sibling;
+	u64 ctime;
+	char fill3[35];
+	char type;
+	u32 fill4;
+	char fill5[64];
+	char name[OMFS_NAMELEN];
+	u64 size;
+	// 198 bytes of nonsense.
+};
+
+struct omfs_extent_entry {
+	u32 fill1;
+	u32 cluster;
+	u32 fill2;
+	u32 blocks;
+};
+	
+struct omfs_extent {
+	u32 fill1;
+	u32 next;
+	u32 extent_count;
+	u32 fill2;
+	struct omfs_extent_entry entry;
+};
+
+/* convert a cluster number to a 512-byte block number */
+static inline sector_t clus_to_blk(sector_t in)
+{
+	return in << 4;
+}
+
+/* dir.c */
+extern struct file_operations omfs_dir_operations;
+extern struct inode_operations omfs_dir_inops;
+
+/* file.c */
+extern struct file_operations omfs_file_operations;
+extern struct address_space_operations omfs_aops;
+
+/* inode.c */
+extern void omfs_read_inode(struct inode *inode);
+
+#endif

Re: readdir on hash filesystems

[Nikita Danilov]

Bob Copeland writes:
 > 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

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.

 > 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.

Re: readdir on hash filesystems

[Bob Copeland]

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