[RFC][PATCH 3/7] omfs: directory routines

[Bob Copeland <me@bobcopeland.com>]

This patch adds directory-related functions to OMFS.  The filesystem
represents each directory on-disk as a hash table for lookups and 
stores the inode numbers of files and directories in the hash buckets.
---

 fs/omfs/dir.c |  310 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 310 insertions(+), 0 deletions(-)
 create mode 100644 fs/omfs/dir.c

d6f496050db8c31ca150894ca9cc36ca2c3d09f2
diff --git a/fs/omfs/dir.c b/fs/omfs/dir.c
new file mode 100644
index 0000000..e244d43
--- /dev/null
+++ b/fs/omfs/dir.c
@@ -0,0 +1,310 @@
+/*
+ * 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;
+}
+
+/* 
+ * Finds the bucket for a given name and reads the containing block; 
+ * *ofs is set to the offset of the first list entry.
+ */
+static struct buffer_head *omfs_get_bucket(struct inode *dir, 
+		const char *name, int namelen, int *ofs)
+{
+	int nbuckets = (dir->i_size - OMFS_DIR_START)/8;
+	int block = clus_to_blk(OMFS_SB(dir->i_sb), dir->i_ino);
+	int bucket = omfs_hash(name, namelen, nbuckets);
+
+	*ofs = OMFS_DIR_START + bucket * 8;
+	return sb_bread(dir->i_sb, block);
+}
+
+static struct buffer_head *omfs_find_entry(struct inode *dir,
+					   const char *name, int namelen)
+{
+	struct buffer_head *bh;
+	struct omfs_inode *oi;
+	int ofs;
+	u64 cluster;
+	bh = omfs_get_bucket(dir, name, namelen, &ofs);
+	if (!bh)
+		goto out;
+
+	cluster = be64_to_cpu(*((u64 *) & bh->b_data[ofs]));
+	brelse(bh);
+	while (cluster != ~0) {
+		bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb), 
+			cluster));
+		if (!bh)
+			goto out;
+
+		oi = (struct omfs_inode *)bh->b_data;
+		if (strncmp(oi->i_name, name, namelen) == 0) {
+			return bh;
+		}
+		cluster = be64_to_cpu(oi->i_sibling);
+		brelse(bh);
+	}
+out:
+	return NULL;
+}
+
+#ifdef OMFS_WRITE
+int omfs_make_empty(struct inode *inode, struct super_block *sb)
+{
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+	int block = clus_to_blk(sbi, inode->i_ino);
+	struct buffer_head *bh;
+
+	bh = sb_bread(sb, block);
+	if (!bh)
+		return -ENOMEM;
+
+	if (inode->i_mode & S_IFDIR)
+	{
+		memset(bh->b_data, 0, OMFS_DIR_START);
+		memset(&bh->b_data[OMFS_DIR_START], 0xff, 
+			sbi->s_sys_blocksize - OMFS_DIR_START);
+	}
+	else
+		omfs_make_empty_table(bh, OMFS_EXTENT_START);
+	
+	mark_buffer_dirty(bh);
+	brelse(bh);
+	return 0;
+}
+
+int omfs_add_link(struct dentry *dentry, struct inode *inode)
+{
+	struct inode *dir = dentry->d_parent->d_inode;
+	const char *name = dentry->d_name.name;
+	int namelen = dentry->d_name.len;
+	struct omfs_inode *oi;
+	struct buffer_head *bh;
+	u64 cluster;
+	u64 *entry;
+	int ofs;
+
+	// just prepend to head of queue in proper bucket and we are done. 
+	bh = omfs_get_bucket(dir, name, namelen, &ofs);
+	if (!bh)
+		goto out;
+
+	entry = (u64 *) &bh->b_data[ofs];
+	cluster = be64_to_cpu(*entry);
+	*entry = cpu_to_be64(inode->i_ino);
+	mark_buffer_dirty(bh);
+	brelse(bh); 
+
+	// now set the sibling and parent pointers on the new inode
+	bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb), inode->i_ino));
+	if (!bh)
+		goto out;
+
+	oi = (struct omfs_inode *) bh->b_data;
+	memcpy (oi->i_name, name, namelen);
+	memset (oi->i_name + namelen, 0, OMFS_NAMELEN - namelen);
+	oi->i_sibling = cpu_to_be64(cluster);
+	oi->i_parent = cpu_to_be64(dir->i_ino);
+	mark_buffer_dirty(bh);
+	brelse(bh);
+
+	dir->i_ctime = CURRENT_TIME_SEC;
+
+	// mark affected inodes dirty to rebuild checksums
+	mark_inode_dirty(dir);
+	mark_inode_dirty(inode);
+	return 0;
+out:
+	return -ENOMEM;
+}
+
+static int omfs_mkdir(struct inode *dir, struct dentry *dentry, int mode)
+{
+	int err = 0;
+	struct inode *inode;
+
+	mode |= S_IFDIR;
+
+	inode = omfs_new_inode(dir, mode);
+	if (IS_ERR(inode))
+		return PTR_ERR(inode);
+
+	if (dir->i_mode & S_ISGID) {
+		inode->i_gid = dir->i_gid;
+		if (S_ISDIR(mode))
+			inode->i_mode |= S_ISGID;
+	}
+
+	err = omfs_make_empty(inode, dir->i_sb);
+	if (err)
+		goto out;
+
+	err = omfs_add_link(dentry, inode); 
+	if (err)
+		goto out;
+
+	d_instantiate(dentry, inode);
+out:
+	return err;
+}
+
+static int omfs_create(struct inode * dir, struct dentry * dentry, int mode,
+		struct nameidata *nd)
+{
+	int err;
+	struct inode *inode;
+
+	mode |= S_IFREG;
+
+	inode = omfs_new_inode(dir, mode);
+	if (IS_ERR(inode))
+		return PTR_ERR(inode);
+
+	err = omfs_make_empty(inode, dir->i_sb);
+	if (err)
+		goto out;
+
+	err = omfs_add_link(dentry, inode); 
+	if (err)
+		goto out;
+	
+	d_instantiate(dentry, inode);
+out:
+	return err;
+}
+#endif
+
+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 = be64_to_cpu(oi->i_head.h_self);
+		brelse(bh);
+		inode = iget(dir->i_sb, ino);
+		if (!inode) {
+			return ERR_PTR(-EINVAL);	
+		}
+	}
+	d_add(dentry, inode);
+	return NULL;
+}
+
+static int omfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
+{
+	struct inode *dir = filp->f_dentry->d_inode;
+	struct buffer_head *bh = NULL, *bh2;
+	struct omfs_inode *oi;
+	loff_t offset, res;
+	unsigned char d_type;
+	ino_t self;
+	unsigned int hchain, hindex;
+	u64 fsblock;
+	int nbuckets;
+
+	switch (filp->f_pos) {
+	case 0:
+		if (filldir(dirent, ".", 1, 0, dir->i_ino, DT_DIR) < 0) 
+			goto success;
+		filp->f_pos++;
+		/* fall through */
+	case 1:
+		if (filldir(dirent, "..", 2, 1, parent_ino(filp->f_dentry), DT_DIR) < 0) 
+			goto success;
+		filp->f_pos = 0x01000000;
+		/* fall through */
+	}
+
+	nbuckets = (dir->i_size - OMFS_DIR_START) / 8;
+
+	/* high byte stores bucket + 1 and low 24 bits store hash index */
+	hchain = (filp->f_pos >> 24) -1;
+	hindex = filp->f_pos & 0xffffff;
+
+	bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb), dir->i_ino));
+	if (!bh)
+		goto no_bh;
+
+	offset = OMFS_DIR_START + hchain * 8;
+
+	for (; hchain < nbuckets; hchain++, offset += 8) {
+		fsblock = be64_to_cpu(*((u64 *) & bh->b_data[offset]));
+
+		// follow chain in this bucket
+		while (fsblock != ~0) {
+			bh2 = sb_bread(dir->i_sb, 
+				clus_to_blk(OMFS_SB(dir->i_sb), fsblock));
+			if (!bh2)
+				goto no_bh2;
+
+			oi = (struct omfs_inode *)bh2->b_data;
+			self = fsblock;
+			fsblock = be64_to_cpu(oi->i_sibling);
+
+			// skip visited nodes
+			if (hindex) { 
+				hindex--;
+				brelse(bh2);
+				continue;
+			}
+
+			if (oi->i_type == OMFS_DIR)
+				d_type = DT_DIR;
+			else
+				d_type = DT_REG;
+
+			res = filldir(dirent, oi->i_name, strnlen(oi->i_name, 
+				OMFS_NAMELEN), filp->f_pos, self, d_type);
+			brelse(bh2);
+			if (res < 0) 
+				goto success;
+			
+			filp->f_pos++;
+		}
+		filp->f_pos = (hchain+2) << 24;
+	}
+success:
+	if (bh)
+		brelse(bh);
+	return 0;
+no_bh2:
+	brelse(bh);
+no_bh:
+	return -EINVAL;
+}
+
+struct inode_operations omfs_dir_inops = {
+	.lookup = omfs_lookup,
+#ifdef OMFS_WRITE
+	.mkdir = omfs_mkdir,
+	.rename = simple_rename,
+	.create = omfs_create,
+#endif
+};
+
+struct file_operations omfs_dir_operations = {
+	.read = generic_read_dir,
+	.readdir = omfs_readdir,
+};
-- 
1.2.1