[RFC][PATCH 0/7] Optimized MPEG file system

[RFC][PATCH 0/7] Optimized MPEG file system

[Bob Copeland]

The following set of patches implement a new filesystem: the "Optimized
MPEG File System" or OMFS (their name, not mine; I make no claims of
actual optimization or utility with digital video).  OMFS is used in
ReplayTV as well as the Rio Karma, but has only been tested with the
latter.  This is a bit rough around the edges but I'd like to get some
feedback in its current state.  The structures were reverse engineered
so not everything is known, but here are the basics:

 - The directories are implemented as a hash table with hashing on the name.
   The mixture of an unfortunate hash function, file naming policy, and
   block size means that in practice only a small number of buckets are
   utilized, and chains tend to be somewhat long (usually 5 or 6 links).

 - Files are implemented as a table of extents: a list of block numbers
   and the count of contiguous blocks allocated starting from that block.

 - All filesystem objects have CRCs and mirrors.  Presumably this is so 
   online consistency checks can be made; this module updates them but 
   otherwise ignores them.

 - ReplayTV, I am told (note I have never seen an RTV image), does not 
   have an on disk free bitmap.  The Karma has one however.  Presumably the
   ReplayTV scans the entire disk every time it's mounted.

 - The fs typically uses a large block size (8k).  It also only uses 
   part of a given block for "system" structures (e.g. inodes), so there is 
   a lot of wasted space in the book-keeping.

 - Some ReplayTV models write everything byte-swapped.  I don't do anything
   about this.

More documentation can be found at:
http://rtvpatch.sourceforge.net/omfs.html
http://bobcopeland.com/karma/

Consequently, the following "interesting" choices were made:

 - Because the blocksize is larger than a page, the FS sets the blocksize
   to the system structure blocksize (usually 2k) and multiplies the block
   numbers accordingly when needed.

 - In order to traverse the hash table inside readdir without extra state,
   the bucket index is encoded into the upper byte of fpos and the link
   index is stored in the lower 24 bits.  No existing block size allows 
   more than 256 hash buckets.

 - To support the ReplayTV, the module allocates space for the whole block 
   bitmap at mount time instead of reading the bitmap blocks as needed.   
   The code to traverse the tree for RTV at startup isn't there yet.

 - CRCs and mirroring are performed whenever the inode is written.

 - I realize extent traversal is very non optimal and could probably
   benefit from Badari's new get_block(s) stuff.  OTOH, I don't expect
   many people to use this FS for anything but interoperability, so I'm
   trying to keep it simple to start.

At present there is no locking and several required filesystem features 
are missing.  

Particularly I am interested in the following feedback:
 - is the use of sb_bread everywhere kosher or should that only be done
   for the superblock and in get_block(), and the pagecache used everywhere
   else?

 - the disk has a structure that doesn't represent a file or a directory
   (a continuation of the extent table for extremely fragmented files)
   which otherwise operates the same as an inode.  Could/should it be an 
   inode even if it wouldn't go into the dcache, i.e. just for 
   mark_inode_dirty?  Right now it has its own write path.

 - is the readdir thing legal?

 - what else looks really wrong?

[RFC][PATCH 1/7] omfs: filesystem headers

[Bob Copeland]

This patch defines basic on-disk and memory structures used by
OMFS and prototypes for various functions.

---

 fs/omfs/omfs.h |  147 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 147 insertions(+), 0 deletions(-)
 create mode 100644 fs/omfs/omfs.h

be5e7e0aa517140d139dbb250a3659e991310bbd
diff --git a/fs/omfs/omfs.h b/fs/omfs/omfs.h
new file mode 100644
index 0000000..1f4f495
--- /dev/null
+++ b/fs/omfs/omfs.h
@@ -0,0 +1,147 @@
+#ifndef _OMFS_H
+#define _OMFS_H
+
+#include <linux/config.h>
+#include <linux/module.h>
+#include <linux/fs.h>
+
+#define OMFS_MAGIC 0xC2993D87
+#define OMFS_IMAGIC 0xD2
+
+#define OMFS_DIR 'D'
+#define OMFS_FILE 'F'
+#define OMFS_INODE_NORMAL 'e'
+#define OMFS_INODE_SYSTEM 's'
+#define OMFS_NAMELEN 256
+#define OMFS_DIR_START 0x1b8
+#define OMFS_EXTENT_START 0x1d0
+#define OMFS_EXTENT_CONT 0x40
+#define OMFS_XOR_COUNT 19
+
+// Still experimental
+// #define OMFS_WRITE
+
+#define OMFS_STATE_NEW 1
+
+/* In-memory structures */
+struct omfs_sb_info {
+	u64 s_num_blocks;
+	u64 s_bitmap_ino;
+	u64 s_root_ino;
+	u32 s_blocksize;
+	u32 s_mirrors;
+	u32 s_sys_blocksize;
+	u32 s_clustersize;
+	int s_block_shift;
+	unsigned long **s_imap;
+	int s_imap_size;
+};
+
+struct omfs_inode_info {
+	u8 i_state;	
+	struct inode vfs_inode;
+};
+
+/* On-disk structures */
+struct omfs_super_block {
+	char s_fill1[256];
+	__be64 s_root_block;
+	__be64 s_num_blocks;
+	__be32 s_magic;
+	__be32 s_blocksize;
+	__be32 s_mirrors;
+	__be32 s_sys_blocksize;
+};
+
+struct omfs_header {
+	__be64 h_self;
+	__be32 h_body_size;
+	__be16 h_crc;
+	char h_fill1[2];
+	u8 h_version;       
+	char h_type;
+	u8 h_magic;
+	u8 h_check_xor;
+	__be32 h_fill2;
+};
+
+struct omfs_root_block {
+	struct omfs_header r_head;
+	__be64 r_fill1;
+	__be64 r_num_blocks;
+	__be64 r_root_dir;
+	__be64 r_bitmap;
+	__be32 r_blocksize;
+	__be32 r_clustersize;
+	__be64 r_mirrors;
+	char r_name[OMFS_NAMELEN];
+};
+
+struct omfs_inode {
+	struct omfs_header i_head;
+	__be64 i_parent;
+	__be64 i_sibling;
+	__be64 i_ctime;
+	char i_fill1[35];
+	char i_type;
+	__be32 i_fill2;
+	char i_fill3[64];
+	char i_name[OMFS_NAMELEN];
+	__be64 i_size;
+};
+
+struct omfs_extent_entry {
+	__be64 e_cluster;
+	__be64 e_blocks;
+};
+	
+struct omfs_extent {
+	__be64 e_next;
+	__be32 e_extent_count;
+	__be32 e_fill;
+	struct omfs_extent_entry e_entry;
+};
+
+
+/* convert a cluster number to a 512-byte block number */
+static inline sector_t clus_to_blk(struct omfs_sb_info *sbi, sector_t block)
+{
+	return block << sbi->s_block_shift; 
+}
+
+static inline struct omfs_sb_info *OMFS_SB(struct super_block *sb)
+{
+	return sb->s_fs_info;
+}
+
+static inline struct omfs_inode_info *OMFS_I(struct inode *inode)
+{
+	return list_entry(inode, struct omfs_inode_info, vfs_inode);
+}
+
+/* bitmap.c */
+extern unsigned long omfs_count_free(struct super_block *sb);
+extern int omfs_allocate_block(struct super_block *sb, u64 block);
+extern int omfs_allocate_range(struct super_block *sb, int min_request, 
+			int max_request, u64 *return_block, int *return_size);
+
+/* checksum.c */
+int omfs_update_checksums(struct omfs_inode *oi, struct super_block *sb, 
+		ino_t ino);
+
+/* 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;
+extern void omfs_make_empty_table(struct buffer_head *bh, int offset);
+
+/* inode.c */
+extern void omfs_read_inode(struct inode *inode);
+extern struct inode *omfs_new_inode(struct inode *dir, int mode);
+extern int omfs_reserve_block(struct super_block *sb, sector_t block);
+extern int omfs_find_empty_block(struct super_block *sb, int mode, ino_t *ino);
+
+#endif
-- 
1.2.1

[RFC][PATCH 2/7] omfs: inode and superblock routines

[Bob Copeland]

This patch contains routines for reading and writing OMFS inodes
and the filesystem superblock.

---

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

5a57cd0c9df8444bb16354bddf0142744f672b08
diff --git a/fs/omfs/inode.c b/fs/omfs/inode.c
new file mode 100644
index 0000000..ac0febb
--- /dev/null
+++ b/fs/omfs/inode.c
@@ -0,0 +1,453 @@
+/*
+ * Optimized MPEG FS - 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 <linux/vmalloc.h>
+#include "omfs.h"
+
+MODULE_AUTHOR("Bob Copeland <me@bobcopeland.com>");
+MODULE_DESCRIPTION("OMFS (ReplayTV/Karma) Filesystem for Linux");
+MODULE_LICENSE("GPL");
+
+static kmem_cache_t *omfs_inode_cachep;
+
+static struct inode *omfs_alloc_inode(struct super_block *sb)
+{
+	struct omfs_inode_info *oinf;
+	oinf = (struct omfs_inode_info *) kmem_cache_alloc(omfs_inode_cachep, 
+			SLAB_KERNEL);
+	if (!oinf)
+		return NULL;
+	return &oinf->vfs_inode;
+}
+
+static void omfs_destroy_inode(struct inode *inode)
+{
+	kmem_cache_free(omfs_inode_cachep, OMFS_I(inode));
+}
+
+static void init_once(void *p, kmem_cache_t *cachep, unsigned long flags)
+{
+	struct omfs_inode_info *oinf = (struct omfs_inode_info *) p;
+
+	if ((flags & (SLAB_CTOR_VERIFY|SLAB_CTOR_CONSTRUCTOR)) ==
+	    SLAB_CTOR_CONSTRUCTOR)
+		inode_init_once(&oinf->vfs_inode);
+}
+ 
+static int init_inodecache(void)
+{
+	omfs_inode_cachep = kmem_cache_create("omfs_inode_cache",
+					     sizeof(struct omfs_inode_info),
+					     0, SLAB_RECLAIM_ACCOUNT,
+					     init_once, NULL);
+	if (!omfs_inode_cachep)
+		return -ENOMEM;
+	return 0;
+}
+
+static void destroy_inodecache(void)
+{
+	if (kmem_cache_destroy(omfs_inode_cachep))
+		printk(KERN_INFO "omfs_inode_cache: not all structures were freed\n");
+}
+
+#ifdef OMFS_WRITE
+struct inode *omfs_new_inode(struct inode *dir, int mode)
+{
+	struct inode *inode;
+	u64 new_block;
+	int res;
+	int len;
+	struct omfs_sb_info *sbi = OMFS_SB(dir->i_sb);
+	
+	inode = new_inode(dir->i_sb);
+	if (!inode)
+		return ERR_PTR(-ENOMEM);
+
+	res = omfs_allocate_range(dir->i_sb, sbi->s_mirrors, sbi->s_mirrors, 
+			&new_block, &len);
+	if (res)
+		return ERR_PTR(res);
+
+	inode->i_ino = new_block;
+	inode->i_mode = mode;
+	inode->i_uid = current->fsuid;
+	inode->i_gid = current->fsgid;
+	inode->i_blksize = PAGE_SIZE;
+	inode->i_blocks = 0;
+	inode->i_mapping->a_ops = &omfs_aops;
+
+	OMFS_I(inode)->i_state = OMFS_STATE_NEW;
+
+	inode->i_atime = inode->i_mtime = inode->i_ctime = CURRENT_TIME;
+	switch (mode & S_IFMT) {
+	case S_IFDIR:
+		inode->i_op = &omfs_dir_inops;
+		inode->i_fop = &omfs_dir_operations;
+		inode->i_size = sbi->s_sys_blocksize;
+		inode->i_nlink++;  /* "." entry */
+		break;
+	case S_IFREG:
+		inode->i_fop = &omfs_file_operations;
+		inode->i_size = 0;
+		break;
+	}
+
+	insert_inode_hash(inode);
+	printk(KERN_DEBUG "omfs: new marked dirty: %lx\n", inode->i_ino);
+	mark_inode_dirty(inode);
+	return inode;
+}
+
+static int omfs_write_inode(struct inode *inode, int wait)
+{
+	struct omfs_inode *oi;
+	struct omfs_sb_info *sbi = OMFS_SB(inode->i_sb);
+	struct buffer_head *bh, *bh2;
+	unsigned int block;
+	u64 ctime;
+	int i;
+
+	printk(KERN_DEBUG "omfs: writing inode %lx\n", inode->i_ino);
+
+	/* get current inode since we may have written sibling ptrs etc. */
+	block = clus_to_blk(sbi, inode->i_ino);
+	bh = sb_bread(inode->i_sb, block);
+	if (!bh) 
+		return -EIO;
+	
+	oi = (struct omfs_inode *) bh->b_data;
+	if (OMFS_I(inode)->i_state & OMFS_STATE_NEW)
+	{
+		memset(oi, 0, sizeof(struct omfs_header));
+		OMFS_I(inode)->i_state &= ~OMFS_STATE_NEW;
+	}
+
+	oi->i_head.h_self = cpu_to_be64(inode->i_ino);
+	if (S_ISDIR(inode->i_mode)) {
+		oi->i_type = OMFS_DIR;
+	} else if (S_ISREG(inode->i_mode)) {
+		oi->i_type = OMFS_FILE;
+	} else 
+		BUG();
+
+	oi->i_head.h_body_size = cpu_to_be32(sbi->s_sys_blocksize - 
+		sizeof(struct omfs_header));
+	oi->i_head.h_version = 1;
+	oi->i_head.h_type = OMFS_INODE_NORMAL;
+	oi->i_head.h_magic = OMFS_IMAGIC;
+	oi->i_size = cpu_to_be64(inode->i_size);
+
+	ctime = inode->i_ctime.tv_sec * 1000LL + 
+		((inode->i_ctime.tv_nsec + 999)/1000);
+	oi->i_ctime = cpu_to_be64(ctime);
+
+	if (omfs_update_checksums(oi, inode->i_sb, inode->i_ino) != 0)
+		return -EIO;
+
+	mark_buffer_dirty(bh);
+	brelse(bh);
+
+	// if mirroring writes, copy to next fsblock
+	for (i = 0; i < sbi->s_mirrors; i++)
+	{
+		bh = sb_bread(inode->i_sb, block);
+		if (!bh)
+			return -EIO;
+		bh2 = sb_bread(inode->i_sb, block + i * 
+			(sbi->s_blocksize / sbi->s_sys_blocksize));
+		if (!bh2)
+		{
+			brelse(bh);
+			return -EIO;
+		}
+		memcpy(bh2->b_data, bh->b_data, bh->b_size);
+		mark_buffer_dirty(bh2);
+		brelse(bh);
+		brelse(bh2);
+	}
+
+	// do_sync?
+	return 0;
+}
+#endif
+
+void omfs_read_inode(struct inode *inode)
+{
+	struct omfs_inode *oi;
+	struct omfs_inode_info *oinf = OMFS_I(inode);
+	struct buffer_head *bh;
+	unsigned int block;
+	u64 ctime;
+	unsigned long nsecs;
+	ino_t ino = inode->i_ino;
+
+	// check against s_num_blocks
+	block = clus_to_blk(OMFS_SB(inode->i_sb), 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 != be64_to_cpu(oi->i_head.h_self)) {
+		make_bad_inode(inode);
+		return;
+	}
+
+	inode->i_uid = 0;
+	inode->i_gid = 0;
+
+	ctime = be64_to_cpu(oi->i_ctime);
+	nsecs = do_div(ctime, 1000) * 1000L;
+
+	inode->i_atime.tv_sec = ctime;
+	inode->i_mtime.tv_sec = ctime;
+	inode->i_ctime.tv_sec = ctime;
+	inode->i_atime.tv_nsec = nsecs;
+	inode->i_mtime.tv_nsec = nsecs;
+	inode->i_ctime.tv_nsec = nsecs;
+
+	oinf->i_state = 0;
+
+	if (oi->i_type == OMFS_DIR) {
+		inode->i_mode = S_IFDIR | S_IRUGO | S_IWUGO | S_IXUGO;
+		inode->i_op = &omfs_dir_inops;
+		inode->i_fop = &omfs_dir_operations;
+		inode->i_size = be32_to_cpu(oi->i_head.h_body_size) +
+			sizeof(struct omfs_header);
+	} else if (oi->i_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 = be64_to_cpu(oi->i_size);
+	}
+	brelse(bh);
+}
+
+
+static void omfs_put_super(struct super_block *sb)
+{
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+	if (sbi)
+	{
+		kfree(sbi->s_imap);
+		kfree(sbi);
+	}
+	sb->s_fs_info = NULL;
+}
+
+static int omfs_statfs(struct super_block *s, struct kstatfs *buf)
+{
+	struct omfs_sb_info *sbi = OMFS_SB(s);
+	buf->f_type = OMFS_MAGIC;
+	buf->f_bsize = sbi->s_blocksize;
+	buf->f_blocks = sbi->s_num_blocks;
+	buf->f_files = sbi->s_num_blocks;
+	buf->f_namelen = OMFS_NAMELEN;
+
+	buf->f_bfree = buf->f_bavail = buf->f_ffree = 
+		omfs_count_free(s);
+	return 0;
+}
+
+struct super_operations omfs_sops = {
+	.alloc_inode	= omfs_alloc_inode,
+	.destroy_inode	= omfs_destroy_inode,
+#ifdef OMFS_WRITE
+	.write_inode	= omfs_write_inode, 
+#endif
+	.read_inode	= omfs_read_inode,
+	.put_super	= omfs_put_super,
+	.statfs		= omfs_statfs,
+};
+
+/*
+ * For Rio Karma, there is an on-disk free bitmap whose location is
+ * stored in the root block.  For ReplayTV, there is no such free bitmap
+ * so we have to walk the tree.  Both inodes and file data are allocated
+ * from the same map.  This array can be big (300k) so we allocate 
+ * in units of the blocksize.
+ */
+static int omfs_get_imap(struct super_block *sb)
+{
+	int bitmap_size;
+	int array_size;
+	int count;
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+	struct buffer_head *bh;
+	unsigned long **ptr;
+	sector_t block;
+
+	bitmap_size = (sbi->s_num_blocks + 7) / 8;
+	array_size = (bitmap_size + sb->s_blocksize - 1) / sb->s_blocksize;
+
+	printk(KERN_DEBUG "omfs: trying to alloc %d bytes\n", array_size);
+	printk(KERN_DEBUG "omfs: bitmap size: %d / blocksize %ld \n", 
+		bitmap_size, sb->s_blocksize);
+	sbi->s_imap_size = array_size;
+	sbi->s_imap = kzalloc(array_size * sizeof(unsigned long), GFP_KERNEL);
+	if (!sbi->s_imap)
+		return -ENOMEM;
+
+	block = clus_to_blk(sbi, sbi->s_bitmap_ino);
+	ptr = sbi->s_imap;
+	for (count = bitmap_size; count > 0; count -= sb->s_blocksize) {
+		bh = sb_bread(sb, block++);
+		if (!bh)
+			goto nomem;
+		*ptr = kmalloc(sb->s_blocksize, GFP_KERNEL);
+		memcpy(*ptr, bh->b_data, sb->s_blocksize);
+		brelse(bh);
+		ptr ++;
+	}
+	return 0;
+nomem:
+	for (count=0; count<array_size; count++)
+	{
+		printk(KERN_DEBUG "Freeing %d\n", count);
+		kfree(sbi->s_imap[count]);
+	}
+	printk(KERN_DEBUG "Freeing imap\n");
+	kfree(sbi->s_imap);
+	sbi->s_imap = NULL;
+	return -ENOMEM;
+}
+
+static void set_block_shift(struct omfs_sb_info *sbi)
+{
+	unsigned int scale = sbi->s_blocksize / sbi->s_sys_blocksize;
+	sbi->s_block_shift = 0;
+	for (scale>>=1; scale; scale>>=1)
+		sbi->s_block_shift++;
+}
+
+static int omfs_fill_super(struct super_block *sb, void *data, int silent)
+{
+	struct buffer_head *bh=NULL, *bh2=NULL;
+	struct omfs_super_block *omfs_sb;
+	struct omfs_root_block *omfs_rb;
+	struct omfs_sb_info *sbi;
+	struct inode *root;
+	sector_t start;
+	int ret = 0;
+
+	sbi = kzalloc(sizeof(struct omfs_sb_info), GFP_KERNEL);
+	if (!sbi)
+		return -ENOMEM;
+	sb->s_fs_info = sbi;
+
+#ifndef OMFS_WRITE
+	sb->s_flags |= MS_RDONLY; 
+#endif
+	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->s_magic) != OMFS_MAGIC) {
+		if (!silent)
+			printk(KERN_ERR "omfs: Invalid superblock (%x)\n",
+				   omfs_sb->s_magic);
+		goto out;
+	}
+	sb->s_magic = OMFS_MAGIC;
+
+	sbi->s_num_blocks = be64_to_cpu(omfs_sb->s_num_blocks);
+	sbi->s_blocksize = be32_to_cpu(omfs_sb->s_blocksize);
+	sbi->s_mirrors = be32_to_cpu(omfs_sb->s_mirrors);
+	sbi->s_root_ino = be64_to_cpu(omfs_sb->s_root_block);
+	sbi->s_sys_blocksize = be32_to_cpu(omfs_sb->s_sys_blocksize);
+
+	// Use sys_blocksize as the fs block since it is smaller than a 
+	// page while the fs blocksize can be larger.
+	sb_set_blocksize(sb, sbi->s_sys_blocksize);
+
+	// and the difference goes into a shift.  sys_blocksize is always
+	// a power of two factor of blocksize.
+	set_block_shift(sbi);
+
+	start = clus_to_blk(sbi, be64_to_cpu(omfs_sb->s_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->r_name);
+
+	sbi->s_bitmap_ino = be64_to_cpu(omfs_rb->r_bitmap);
+	sbi->s_clustersize = be32_to_cpu(omfs_rb->r_clustersize);
+
+	ret = omfs_get_imap(sb);
+	if (ret)
+		goto end;
+
+	sb->s_op = &omfs_sops;
+	root = iget(sb, be64_to_cpu(omfs_rb->r_root_dir));
+
+	sb->s_root = d_alloc_root(root);
+	if (!sb->s_root) {
+		iput(root);
+		goto out;
+	}
+	goto end;
+
+out:
+	ret = -EINVAL;
+
+end:
+	if (bh2)
+		brelse(bh2);
+	if (bh)
+		brelse(bh);
+	return ret;
+}
+
+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)
+{
+	int err = init_inodecache();
+	if (err)
+		goto out;
+
+	err = register_filesystem(&omfs_fs_type);
+	if (err)
+		destroy_inodecache();
+out:
+	return err;
+}
+
+static void __exit exit_omfs_fs(void)
+{
+	unregister_filesystem(&omfs_fs_type);
+	destroy_inodecache();
+}
+
+module_init(init_omfs_fs);
+module_exit(exit_omfs_fs);
-- 
1.2.1

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

[Bob Copeland]

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

[RFC][PATCH 4/7] omfs: file routines

[Bob Copeland]

File routines for OMFS.  Each file is stored as a table of extents,
containing a block number and count for each entry, followed by a
terminator that has a 1's complement of the preceeding block counts.
If more entries are needed than will fit in an inode, continuation 
blocks are added as needed.

---

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

af9af9dd0f834c570412e415d3dca319122ef04d
diff --git a/fs/omfs/file.c b/fs/omfs/file.c
new file mode 100644
index 0000000..0e32506
--- /dev/null
+++ b/fs/omfs/file.c
@@ -0,0 +1,301 @@
+/*
+ * 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"
+
+void omfs_make_empty_table(struct buffer_head *bh, int offset)
+{
+	struct omfs_extent *oe = (struct omfs_extent *) &bh->b_data[offset];
+
+	memset(bh->b_data, 0, offset);
+
+	oe->e_next = ~0;
+	oe->e_extent_count = cpu_to_be32(1),
+	oe->e_fill = cpu_to_be32(0x22),
+	oe->e_entry.e_cluster = ~0;
+	oe->e_entry.e_blocks = ~0;
+}
+
+#ifdef OMFS_WRITE
+static void update_continuation(struct super_block *sb, struct buffer_head *bh)
+{
+	struct omfs_inode *oi = (struct omfs_inode *) bh->b_data;
+	omfs_update_checksums(oi, sb, be64_to_cpu(oi->i_head.h_self));
+	// copy mirrors too.
+}
+
+static int omfs_add_continuation(struct super_block *sb, u64 *ret_block, 
+		struct buffer_head **ret_bh)
+{
+	int dummy, ret;
+	struct omfs_inode *oi;
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+
+	// alloc a block
+	ret = omfs_allocate_range(sb, sbi->s_mirrors, sbi->s_mirrors, ret_block, 
+			&dummy);
+	if (ret)
+		return ret;
+
+	// read it
+	*ret_bh = sb_bread(sb, clus_to_blk(sbi, *ret_block));
+	if (!*ret_bh)
+		return -ENOMEM;
+
+	omfs_make_empty_table(*ret_bh, OMFS_EXTENT_CONT);
+
+	oi = (struct omfs_inode *) (*ret_bh)->b_data;
+
+	oi->i_head.h_self = cpu_to_be64(*ret_block); 
+	// and so forth
+	oi->i_head.h_body_size = cpu_to_be32(sbi->s_sys_blocksize - 
+		sizeof(struct omfs_header));
+	oi->i_head.h_version = 1;
+	oi->i_head.h_type = OMFS_INODE_NORMAL;
+	oi->i_head.h_magic = OMFS_IMAGIC;
+
+	return 0;
+}
+#endif
+
+
+/* 
+ * Scans across the directory table for a given file block number.  
+ * If block not found, return 0.
+ */
+static sector_t find_block(struct inode *inode, struct omfs_extent_entry *ent, 
+	 	       sector_t block, int count)
+{
+	// count>1 because of terminator 
+	sector_t searched = 0;
+	for (; count > 1; count--)
+	{
+		int numblocks = clus_to_blk(OMFS_SB(inode->i_sb), 
+			be64_to_cpu(ent->e_blocks));
+
+		if (block >= searched  && 
+		    block < searched + numblocks)
+		{
+			// found it at cluster + (block - searched)
+			return clus_to_blk(OMFS_SB(inode->i_sb), 
+				be64_to_cpu(ent->e_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, offset;
+#ifdef OMFS_WRITE
+	u64 new_block;
+	int new_count;
+	int ret;
+	int is_continue = 0;
+	int max_count;
+	struct omfs_extent_entry *terminator;
+#endif
+	int extent_count;
+	struct omfs_extent *oe;
+	struct omfs_extent_entry *entry;
+	struct omfs_sb_info *sbi = OMFS_SB(inode->i_sb);
+
+	bh = sb_bread(inode->i_sb, clus_to_blk(sbi, inode->i_ino));
+	if (!bh)
+		goto err;
+
+	oe = (struct omfs_extent *)(&bh->b_data[OMFS_EXTENT_START]);
+
+	for(;;) {
+		extent_count = be32_to_cpu(oe->e_extent_count);
+		next = be64_to_cpu(oe->e_next);
+		entry = &oe->e_entry;
+
+		offset = find_block(inode, entry, block, extent_count);
+		if (offset > 0) {
+			brelse(bh);
+
+			map_bh(bh_result, inode->i_sb, offset);
+			return 0;
+		}
+		if (next == ~0)
+			break;
+
+		brelse(bh);
+		bh = sb_bread(inode->i_sb, clus_to_blk(sbi, next));
+		if (!bh) goto err;
+		oe = (struct omfs_extent *) (&bh->b_data[OMFS_EXTENT_CONT]);
+	}
+	if (!create) {
+		brelse(bh);
+		return 0;
+	}
+
+#ifdef OMFS_WRITE
+
+	/* reached the end of the extent table with no blocks mapped.
+	 * there are three possibilities for adding: grow last extent,
+	 * add a new extent to the current extent table, and add a 
+	 * continuation inode.  in last two cases need an allocator for
+	 * sbi->s_cluster_size
+	 */
+
+	/* TODO: handle holes */
+
+	// should always have a terminator
+	if (extent_count < 1)
+		return -EIO;
+
+	/* trivially grow current extent, if next block is not taken */
+	terminator = entry + extent_count - 1;
+	if (extent_count > 1)
+	{
+		entry = terminator-1;
+		new_block = be64_to_cpu(entry->e_cluster) + 
+			be64_to_cpu(entry->e_blocks);
+
+		printk(KERN_DEBUG "trying to grow %llx+%llx = %llx\n",
+				be64_to_cpu(entry->e_cluster), 
+				be64_to_cpu(entry->e_blocks), 
+				new_block);
+	
+		if (omfs_allocate_block(inode->i_sb, new_block))
+		{
+			entry->e_blocks = 
+				cpu_to_be64(be64_to_cpu(entry->e_blocks) + 1);
+			terminator->e_blocks = ~(cpu_to_be64(
+				be64_to_cpu(~terminator->e_blocks) + 1));
+
+			mark_buffer_dirty(bh);
+			brelse(bh);
+	
+			mark_inode_dirty(inode);
+
+			map_bh(bh_result, inode->i_sb, 
+				clus_to_blk(sbi, new_block));
+			return 0;
+		}
+	}
+	max_count = (sbi->s_sys_blocksize - OMFS_EXTENT_START - 
+		sizeof(struct omfs_extent)) / 
+		sizeof(struct omfs_extent_entry) + 1;
+
+	// add a continuation block here
+	if (be32_to_cpu(oe->e_extent_count) > max_count-1)
+	{
+		struct omfs_extent *new_table;
+		u64 cblock;
+		struct buffer_head *new_bh;
+
+		return -EIO;
+
+		ret = omfs_add_continuation(inode->i_sb, &cblock, &new_bh);
+		if (ret)
+			return ret;
+
+		new_table = (struct omfs_extent *) 
+			&new_bh->b_data[OMFS_EXTENT_CONT];
+
+		oe->e_next = cblock;
+		mark_buffer_dirty(bh);
+		brelse(bh);
+
+		bh = new_bh;
+		oe = new_table;
+		terminator = &oe->e_entry;
+
+		is_continue = 1;
+	}
+
+	// try to allocate a new cluster
+	ret = omfs_allocate_range(inode->i_sb, 1, sbi->s_clustersize, 
+		&new_block, &new_count);
+	if (ret)
+		return ret;
+
+	printk(KERN_DEBUG "omfs: made a new block at %llx\n", new_block);
+
+	// copy terminator down an entry
+	entry = terminator;
+	terminator ++;
+	memcpy(terminator, entry, sizeof(struct omfs_extent_entry));
+
+	entry->e_cluster = cpu_to_be64(new_block);
+	entry->e_blocks = cpu_to_be64((u64) new_count);
+
+	terminator->e_blocks = ~(cpu_to_be64(
+		be64_to_cpu(~terminator->e_blocks) + (u64) new_count));
+
+	// write in new entry
+	oe->e_extent_count = cpu_to_be32(1 + be32_to_cpu(oe->e_extent_count));
+
+	if (is_continue)
+	{
+		update_continuation(inode->i_sb, bh);
+	}
+	mark_buffer_dirty(bh);
+	brelse(bh);
+
+	if (!is_continue)
+		mark_inode_dirty(inode);
+
+	map_bh(bh_result, inode->i_sb, clus_to_blk(sbi, new_block));
+	return 0;
+#endif
+
+err:
+	return -EIO;
+}
+
+static int omfs_readpage(struct file *file, struct page *page)
+{
+	return block_read_full_page(page, omfs_get_block);
+}
+
+#ifdef OMFS_WRITE
+static int omfs_writepage(struct page *page, struct writeback_control *wbc)
+{
+	return block_write_full_page(page, omfs_get_block, wbc);
+}
+
+static int omfs_prepare_write(struct file *file, struct page *page, unsigned from, unsigned to)
+{
+	return block_prepare_write(page,from,to,omfs_get_block);
+}
+
+static sector_t omfs_bmap(struct address_space *mapping, sector_t block)
+{
+	return generic_block_bmap(mapping,block,omfs_get_block);
+}
+#endif
+
+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,
+#ifdef OMFS_WRITE
+	.writepage = omfs_writepage,
+	.sync_page = block_sync_page,
+	.prepare_write = omfs_prepare_write,
+	.commit_write = generic_commit_write,
+	.bmap = omfs_bmap,
+#endif
+};
+
-- 
1.2.1

[RFC][PATCH 5/7] omfs: bitmap / block allocation routines

[Bob Copeland]

This patch adds routines for allocating free space on the disk.
The block bitmap is stored on disk and loaded in entirety at mount time.
---

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

c805e8524962d2277276d5337fe72b0f78fd2cd3
diff --git a/fs/omfs/bitmap.c b/fs/omfs/bitmap.c
new file mode 100644
index 0000000..2b740a1
--- /dev/null
+++ b/fs/omfs/bitmap.c
@@ -0,0 +1,194 @@
+#include <linux/kernel.h>
+#include <linux/fs.h>
+#include <linux/buffer_head.h>
+#include "omfs.h"
+
+static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
+
+unsigned long omfs_count_free(struct super_block *sb)
+{
+	unsigned int i, j, count = 0;
+	long *map;
+	unsigned long sum = 0;
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+
+	// lock
+	for (i = 0; i < sbi->s_imap_size; i++)
+	{
+		map = sbi->s_imap[i];
+		for (j=0; j < sb->s_blocksize && 
+				count + j < sbi->s_num_blocks/8; j++)
+			sum += nibblemap[map[j] & 0xf] +
+				nibblemap[(map[j] >> 4) & 0xf];
+		count += sb->s_blocksize;
+	}
+	// unlock
+	return sum;
+}
+
+/*
+ *  Counts the run of zero bits starting at bit up to max.
+ *  It handles the case where a run might spill over a buffer.
+ *  Assumes block lock is held.
+ */
+static int count_run(unsigned long **addr, int nbits, 
+		int addrlen, int bit, int max)
+{
+	int count = 0;
+	int x;
+
+	for (; addrlen > 0; addrlen--, addr++)
+	{
+		x = find_next_bit(*addr, nbits, bit);
+		count += x - bit;
+
+		if (x < nbits || count > max)
+			return min(count,max);
+
+		bit = 0;
+	}
+	return min(count,max);
+}
+
+/*
+ * Sets the run of count bits starting with bit.
+ */
+static int set_run(struct super_block *sb, int map, 
+		int nbits, int bit, int count)
+{
+	int i;
+	struct buffer_head *bh;
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+
+	bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino + map));
+	if (!bh)
+		goto nomem;
+
+	for (i = 0; i < count; i++, bit++)
+	{
+		if (bit > nbits)
+		{
+			bit = 0;
+			map++;
+
+			mark_buffer_dirty(bh);
+			brelse(bh);
+			bh = sb_bread(sb, 
+				clus_to_blk(sbi, sbi->s_bitmap_ino + map));
+			if (!bh)
+				goto nomem;
+		}
+		set_bit(bit, sbi->s_imap[map]);
+		set_bit(bit, (long*) bh->b_data);
+	}
+	mark_buffer_dirty(bh);
+	brelse(bh);
+	return 0;
+nomem:
+	return -ENOMEM;
+}
+
+/*
+ * Tries to allocate exactly one block.  Returns true if sucessful.
+ */
+int omfs_allocate_block(struct super_block *sb, u64 block)
+{
+
+	struct buffer_head *bh;
+        struct omfs_sb_info *sbi = OMFS_SB(sb);
+        int bits_per_entry = 8 * sb->s_blocksize;
+        int map, bit;
+	int ret = 1;
+	u64 tmp;
+
+	tmp = block;
+	bit = do_div(tmp, bits_per_entry);
+	map = tmp;
+
+	// lock
+        if (map >= sbi->s_imap_size || 
+	    test_and_set_bit(bit, sbi->s_imap[map]))
+	{
+		ret = 0;
+		goto out;
+	}
+
+        if (sbi->s_bitmap_ino > 0)
+        {
+                bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino + map));
+		if (!bh)
+		{
+			ret = 0;
+			goto out;
+		}
+                set_bit(bit, (long*) bh->b_data);
+                mark_buffer_dirty(bh);
+                brelse(bh);
+        }
+out:
+	printk(KERN_DEBUG 
+		"omfs: requested 1 block at %llx (%s)\n",
+		block, ret ? "filled" : "unfilled");
+	// unlock
+        return ret;
+}
+
+
+/*
+ *  Tries to allocate a set of blocks.  The request size depends on the 
+ *  type: for inodes, we must allocate sbi->s_mirrors blocks, and for file 
+ *  blocks, we try to allocate sbi->s_clustersize, but can always get away
+ *  with just one block.
+ */
+int omfs_allocate_range(struct super_block *sb, 
+			int min_request, 
+			int max_request,
+			u64 *return_block,
+			int *return_size)
+{
+	struct omfs_sb_info *sbi = OMFS_SB(sb);
+	int bits_per_entry = 8 * sb->s_blocksize;
+	int ret = 0;
+	int i, run, bit;
+
+	// lock
+	for (i=0; i < sbi->s_imap_size; i++)
+	{
+		bit = 0;
+		while (bit < bits_per_entry)
+		{
+			bit = find_next_zero_bit(sbi->s_imap[i], bits_per_entry,
+				bit);
+			run = count_run(&sbi->s_imap[i], bits_per_entry, 
+				sbi->s_imap_size-i, bit, max_request);
+
+			printk(KERN_DEBUG "run starting at %x is %d bits long\n",
+				i * bits_per_entry + bit, run);
+
+
+			if (run >= min_request)
+				goto found;
+			bit += run;
+		}
+	}
+	ret = -ENOSPC;
+	goto out;
+
+found:
+	*return_block = i * bits_per_entry + bit;
+	*return_size = run;
+	ret = set_run(sb, i, bits_per_entry, bit, run);
+
+	printk(KERN_DEBUG 
+		"omfs: requested %d->%d blocks, filled at %llx (%d)\n",
+		min_request, max_request, *return_block, *return_size);
+
+out:
+	if (ret)
+		printk(KERN_DEBUG 
+			"omfs: requested %d->%d blocks, unfilled at %d\n",
+			min_request, max_request, i);
+	// unlock
+	return ret;
+}
+
-- 
1.2.1

[RFC][PATCH 6/7] omfs: checksumming routines

[Bob Copeland]

This patch adds routines to compute checksums that are stored in the
headers of all filesystem entities in OMFS.
---

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

e1a3b6f48ad0d0f0d69fcc35c890f92afaffb38f
diff --git a/fs/omfs/checksum.c b/fs/omfs/checksum.c
new file mode 100644
index 0000000..212e8b5
--- /dev/null
+++ b/fs/omfs/checksum.c
@@ -0,0 +1,60 @@
+#include <linux/config.h>
+#include <linux/fs.h>
+#include <linux/buffer_head.h>
+#include "omfs.h"
+
+#define POLY 0x1021
+
+/*
+ * crc-ccitt with MSB first (i.e., backwards), so we can't use the
+ * kernel table as-is.  
+ */
+#ifdef OMFS_WRITE
+static u16 omfs_crc(u16 crc, unsigned char *buf, int count)
+{
+	int i, j;
+	printk(KERN_DEBUG "omfs: in crc for count %x\n", count);
+	for (i=0; i<count; i++) {
+		crc ^= buf[i] << 8;
+		for (j = 0; j < 8; j++)
+			crc = (crc << 1) ^ ((crc & 0x8000) ? POLY : 0);
+	}
+	return crc;
+}
+#endif
+
+/*
+ * Update the header checksums for a dirty inode based on its contents.
+ * Caller is expected to hold the buffer head underlying oi and mark it 
+ * dirty.
+ */
+int omfs_update_checksums(struct omfs_inode *oi, struct super_block *sb, 
+		ino_t ino)
+{
+	int ret=0;
+#ifdef OMFS_WRITE
+	int xor, i, ofs=0, count;
+	u16 crc=0;
+	unsigned char *ptr = (unsigned char *) oi;
+
+	count = be32_to_cpu(oi->i_head.h_body_size);
+	ofs = sizeof(struct omfs_header);
+
+	printk(KERN_DEBUG "omfs: body size is %x\n", count);
+
+	crc = omfs_crc(crc, ptr + ofs, count);
+	oi->i_head.h_crc = cpu_to_be16(crc);
+
+	xor = ptr[0];
+	for (i=1; i<OMFS_XOR_COUNT; i++)
+		xor ^= ptr[i];
+
+	oi->i_head.h_check_xor = xor;
+
+	printk(KERN_DEBUG "Calculated checksum for %lx as %x\n", 
+		ino, crc);
+#endif
+	return ret;
+}
+
+
-- 
1.2.1

[RFC][PATCH 7/7] omfs: kbuild updates

[Bob Copeland]

This patch adds the OMFS option to Kconfig, allowing it to be built.

---

 fs/Kconfig       |   14 ++++++++++++++
 fs/Makefile      |    1 +
 fs/omfs/Makefile |    7 +++++++
 3 files changed, 22 insertions(+), 0 deletions(-)
 create mode 100644 fs/omfs/Makefile

8067d5d256c9663c0bf80f1d3f2a2144425fd20f
diff --git a/fs/Kconfig b/fs/Kconfig
index e9749b0..a9a8101 100644
--- a/fs/Kconfig
+++ b/fs/Kconfig
@@ -356,6 +356,20 @@ config OCFS2_FS
 	          - POSIX ACLs
 	          - readpages / writepages (not user visible)
 
+config OMFS_FS
+	tristate "OMFS fs support (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	help
+	  This option provides support for the Optimized MPEG File System, an
+	  extent-based filesystem using hashing created by SonicBlue for use
+	  in the ReplayTV digital video recorder, and also used by the Rio 
+	  Karma portable music player.  If you say Y here, you will be able
+	  to read and write to OMFS partitions.
+
+	  To compile this file system support as a module, choose M here: the
+	  module will be called omfs.  If unsure, say N.
+
+
 config MINIX_FS
 	tristate "Minix fs support"
 	help
diff --git a/fs/Makefile b/fs/Makefile
index 1db7113..5675690 100644
--- a/fs/Makefile
+++ b/fs/Makefile
@@ -103,3 +103,4 @@ obj-$(CONFIG_HPPFS)		+= hppfs/
 obj-$(CONFIG_DEBUG_FS)		+= debugfs/
 obj-$(CONFIG_CONFIGFS_FS)	+= configfs/
 obj-$(CONFIG_OCFS2_FS)		+= ocfs2/
+obj-$(CONFIG_OMFS_FS)		+= omfs/
diff --git a/fs/omfs/Makefile b/fs/omfs/Makefile
new file mode 100644
index 0000000..e52bab6
--- /dev/null
+++ b/fs/omfs/Makefile
@@ -0,0 +1,7 @@
+#
+# Makefile for OMFS filesystem
+#
+
+obj-$(CONFIG_OMFS_FS) += omfs.o
+
+omfs-objs := bitmap.o checksum.o dir.o file.o inode.o
-- 
1.2.1

Re: [RFC][PATCH 0/7] Optimized MPEG file system

[Brad Boyer]

On Wed, Mar 15, 2006 at 10:01:44PM -0500, Bob Copeland wrote:
>  - the disk has a structure that doesn't represent a file or a directory
>    (a continuation of the extent table for extremely fragmented files)
>    which otherwise operates the same as an inode.  Could/should it be an 
>    inode even if it wouldn't go into the dcache, i.e. just for 
>    mark_inode_dirty?  Right now it has its own write path.

This sounds a lot like HFS/HFS+. Each file has a fixed number of extents
in the main catalog record, and extras go into the extents overflow
tree.  If you look at fs/{hfs,hfsplus}/btree.c, you can find the code
handling the catalog and extents overflow trees for HFS and HFS+. The
initialization happens in the function hfs_btree_open(). In particular,
it fetches an inode out of the regular inode cache and then the
regular page cache routines are used to read the data.

Just as a warning, I wrote the original version of the HFS+ code, but
I don't maintain it anymore and haven't touched it in ages. I'm also
commenting based on a slightly out of date tree, but I don't think
the parts I've mentioned have changed much recently.

	Brad Boyer
	flar@allandria.com

Re: [RFC][PATCH 0/7] Optimized MPEG file system

[Bob Copeland]

On Wed, Mar 15, 2006 at 08:33:51PM -0800, Brad Boyer wrote:
> This sounds a lot like HFS/HFS+. Each file has a fixed number of extents
> in the main catalog record, and extras go into the extents overflow
> tree.  

Yes this sounds basically like the same thing - I'll go take a look at 
the code.

Thanks for the tip!
-Bob