iso9660 Inodes Anywhere and NFS

PATCH In review Paul Serice 3 participants 7 messages Jun 2, 2004 – Jun 10, 2004 Isofs filesystem

Share & tools

Paul Serice

author

2004-06-02 01:07 UTC #0 lore raw

PATCH 1/1 iso9660 Inodes Anywhere and NFS

This is my fourth attempt to patch the isofs code. It is similar to the last posting except this one implements the NFS get_parent() method which has always been missing.

The original problem I set out to addresses is that the current iso9660 file system cannot reach inodes located beyond the 4GB barrier. This is caused by using the inode number as the byte offset of the inode data. Being 32-bits wide, the inode number is unable to reach inode data that does not reside on the first 4GB of the file system.

This causes real problems with "growisofs"

    http://fy.chalmers.se/~appro/linux/DVD+RW/#isofs4gb

and my pet project "shunt"

http://www.serice.net/shunt/

This patch switches the isofs code from iget() to iget5_locked() which allows extra data to be passed into isofs_read_inode() so that inode data anywhere on the disk can be reached.

The inode number scheme was also changed. Continuing to use the byte offset would have resulted in non-unique inodes in many common situations, but because the inode number no longer plays any role in reading the meta-data off the disk, I was free to set the inode number to some unique characteristic of the file. I have chosen to use the block offset which is also 32-bits wide.

Lastly, the pre-patch code uses the default export_operations to handle accessing the file system through NFS. The problem with this is that the default NFS operations assume that iget() works which is no longer the case because of the necessity of switching to iget5_locked(). So, I had to implement the NFS operations too. As a bonus, I went ahead and implemented the NFS get_parent() method which has always been missing.

Thanks,
Paul Serice

fs/isofs/Makefile +1 -1

diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/Makefile linux-2.6.7-rc2-isofs.3/fs/isofs/Makefile
@@ -4,7 +4,7 @@
 
 obj-$(CONFIG_ISO9660_FS) += isofs.o
 
-isofs-objs-y 			:= namei.o inode.o dir.o util.o rock.o
+isofs-objs-y 			:= namei.o inode.o dir.o util.o rock.o export.o
 isofs-objs-$(CONFIG_JOLIET)	+= joliet.o
 isofs-objs-$(CONFIG_ZISOFS)	+= compress.o
 isofs-objs			:= $(isofs-objs-y)

fs/isofs/dir.c +3 -3

diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/dir.c linux-2.6.7-rc2-isofs.3/fs/isofs/dir.c
@@ -106,8 +106,8 @@ static int do_isofs_readdir(struct inode
 {
 	unsigned long bufsize = ISOFS_BUFFER_SIZE(inode);
 	unsigned char bufbits = ISOFS_BUFFER_BITS(inode);
-	unsigned int block, offset;
-	int inode_number = 0;	/* Quiet GCC */
+	unsigned long block, offset;
+	unsigned long inode_number = 0;	/* Quiet GCC */
 	struct buffer_head *bh = NULL;
 	int len;
 	int map;

@@ -130,7 +130,7 @@ static int do_isofs_readdir(struct inode
 
 		de = (struct iso_directory_record *) (bh->b_data + offset);
 		if (first_de)
-			inode_number = (bh->b_blocknr << bufbits) + offset;
+			inode_number = isofs_get_ino(de);
 
 		de_len = *(unsigned char *) de;

fs/isofs/export.c +231 -0

231 lines not on this page · raw message

fs/isofs/inode.c +104 ~~-50~~

306 lines not on this page · raw message

fs/isofs/namei.c +21 -9

diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/namei.c linux-2.6.7-rc2-isofs.3/fs/isofs/namei.c
@@ -17,6 +17,7 @@
 #include <linux/config.h>	/* Joliet? */
 #include <linux/smp_lock.h>
 #include <linux/buffer_head.h>
+#include <linux/dcache.h>
 
 #include <asm/uaccess.h>

@@ -59,12 +60,12 @@ isofs_cmp(struct dentry * dentry, const 
  */
 static unsigned long
 isofs_find_entry(struct inode *dir, struct dentry *dentry,
+	unsigned long *block_rv, unsigned long* offset_rv,
 	char * tmpname, struct iso_directory_record * tmpde)
 {
-	unsigned long inode_number;
 	unsigned long bufsize = ISOFS_BUFFER_SIZE(dir);
 	unsigned char bufbits = ISOFS_BUFFER_BITS(dir);
-	unsigned int block, f_pos, offset;
+	unsigned long block, f_pos, offset, block_saved, offset_saved;
 	struct buffer_head * bh = NULL;
 	struct isofs_sb_info *sbi = ISOFS_SB(dir->i_sb);

@@ -87,7 +88,6 @@ isofs_find_entry(struct inode *dir, stru
 		}
 
 		de = (struct iso_directory_record *) (bh->b_data + offset);
-		inode_number = (bh->b_blocknr << bufbits) + offset;
 
 		de_len = *(unsigned char *) de;
 		if (!de_len) {

@@ -99,6 +99,8 @@ isofs_find_entry(struct inode *dir, stru
 			continue;
 		}
 
+		block_saved = bh->b_blocknr;
+		offset_saved = offset;
 		offset += de_len;
 		f_pos += de_len;

@@ -150,8 +152,13 @@ isofs_find_entry(struct inode *dir, stru
 			match = (isofs_cmp(dentry,dpnt,dlen) == 0);
 		}
 		if (match) {
+			isofs_normalize_block_and_offset(de,
+							 &block_saved,
+							 &offset_saved);
+                        *block_rv = block_saved;
+                        *offset_rv = offset_saved;
 			if (bh) brelse(bh);
-			return inode_number;
+			return 1;
 		}
 	}
 	if (bh) brelse(bh);

@@ -160,7 +167,8 @@ isofs_find_entry(struct inode *dir, stru
 
 struct dentry *isofs_lookup(struct inode * dir, struct dentry * dentry, struct nameidata *nd)
 {
-	unsigned long ino;
+	int found;
+	unsigned long block, offset;
 	struct inode *inode;
 	struct page *page;

@@ -171,19 +179,23 @@ struct dentry *isofs_lookup(struct inode
 		return ERR_PTR(-ENOMEM);
 
 	lock_kernel();
-	ino = isofs_find_entry(dir, dentry, page_address(page),
-			       1024 + page_address(page));
+	found = isofs_find_entry(dir, dentry,
+				 &block, &offset,
+				 page_address(page),
+				 1024 + page_address(page));
 	__free_page(page);
 
 	inode = NULL;
-	if (ino) {
-		inode = iget(dir->i_sb, ino);
+	if (found) {
+		inode = isofs_iget(dir->i_sb, block, offset);
 		if (!inode) {
 			unlock_kernel();
 			return ERR_PTR(-EACCES);
 		}
 	}
 	unlock_kernel();
+	if (inode)
+		return d_splice_alias(inode, dentry);
 	d_add(dentry, inode);
 	return NULL;
 }

fs/isofs/rock.c +7 -8

diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/rock.c linux-2.6.7-rc2-isofs.3/fs/isofs/rock.c
@@ -306,9 +306,7 @@ int parse_rock_ridge_inode_internal(stru
 	goto out;
       case SIG('C','L'):
 	ISOFS_I(inode)->i_first_extent = isonum_733(rr->u.CL.location);
-	reloc = iget(inode->i_sb,
-		     (ISOFS_I(inode)->i_first_extent <<
-		      ISOFS_SB(inode->i_sb)->s_log_zone_size));
+	reloc = isofs_iget(inode->i_sb, ISOFS_I(inode)->i_first_extent, 0);
 	if (!reloc)
 		goto out;
 	inode->i_mode = reloc->i_mode;

@@ -447,15 +445,15 @@ int parse_rock_ridge_inode(struct iso_di
 static int rock_ridge_symlink_readpage(struct file *file, struct page *page)
 {
 	struct inode *inode = page->mapping->host;
+        struct iso_inode_info *ei = ISOFS_I(inode);
 	char *link = kmap(page);
 	unsigned long bufsize = ISOFS_BUFFER_SIZE(inode);
-	unsigned char bufbits = ISOFS_BUFFER_BITS(inode);
 	struct buffer_head *bh;
 	char *rpnt = link;
 	unsigned char *pnt;
 	struct iso_directory_record *raw_inode;
 	CONTINUE_DECLS;
-	int block;
+	unsigned long block, offset;
 	int sig;
 	int len;
 	unsigned char *chr;

@@ -464,20 +462,21 @@ static int rock_ridge_symlink_readpage(s
 	if (!ISOFS_SB(inode->i_sb)->s_rock)
 		panic ("Cannot have symlink with high sierra variant of iso filesystem\n");
 
-	block = inode->i_ino >> bufbits;
+	block = ei->i_iget5_block;
 	lock_kernel();
 	bh = sb_bread(inode->i_sb, block);
 	if (!bh)
 		goto out_noread;
 
-	pnt = (unsigned char *) bh->b_data + (inode->i_ino & (bufsize - 1));
+        offset = ei->i_iget5_offset;
+	pnt = (unsigned char *) bh->b_data + offset;
 
 	raw_inode = (struct iso_directory_record *) pnt;
 
 	/*
 	 * If we go past the end of the buffer, there is some sort of error.
 	 */
-	if ((inode->i_ino & (bufsize - 1)) + *pnt > bufsize)
+	if (offset + *pnt > bufsize)
 		goto out_bad_span;
 
 	/* Now test for possible Rock Ridge extensions which will override

include/linux/iso_fs.h +66 -0

75 lines not on this page · raw message

include/linux/iso_fs_i.h +4 -1

diff -uprN -X dontdiff linux-2.6.7-rc2/include/linux/iso_fs_i.h linux-2.6.7-rc2-isofs.3/include/linux/iso_fs_i.h
@@ -13,10 +13,13 @@ enum isofs_file_format {
  * iso fs inode data in memory
  */
 struct iso_inode_info {
+	unsigned long i_iget5_block;
+	unsigned long i_iget5_offset;
 	unsigned int i_first_extent;
 	unsigned char i_file_format;
 	unsigned char i_format_parm[3];
-	unsigned long i_next_section_ino;
+	unsigned long i_next_section_block;
+	unsigned long i_next_section_offset;
 	off_t i_section_size;
 	struct inode vfs_inode;
 };

Sergey Vlasov

2004-06-02 11:44 UTC #1 lore raw

Quoted 44 lines · On Tue, 01 Jun 2004 20:07:13 -0500 Paul Serice wrote:

This is my fourth attempt to patch the isofs code. It is similar to the last posting except this one implements the NFS get_parent() method which has always been missing.
The original problem I set out to addresses is that the current iso9660 file system cannot reach inodes located beyond the 4GB barrier. This is caused by using the inode number as the byte offset of the inode data. Being 32-bits wide, the inode number is unable to reach inode data that does not reside on the first 4GB of the file system.
This causes real problems with "growisofs"
     http://fy.chalmers.se/~appro/linux/DVD+RW/#isofs4gb
and my pet project "shunt"
http://www.serice.net/shunt/
This patch switches the isofs code from iget() to iget5_locked() which allows extra data to be passed into isofs_read_inode() so that inode data anywhere on the disk can be reached.
The inode number scheme was also changed. Continuing to use the byte offset would have resulted in non-unique inodes in many common situations, but because the inode number no longer plays any role in reading the meta-data off the disk, I was free to set the inode number to some unique characteristic of the file. I have chosen to use the block offset which is also 32-bits wide.
Lastly, the pre-patch code uses the default export_operations to handle accessing the file system through NFS. The problem with this is that the default NFS operations assume that iget() works which is no longer the case because of the necessity of switching to iget5_locked(). So, I had to implement the NFS operations too. As a bonus, I went ahead and implemented the NFS get_parent() method which has always been missing.
Thanks,
Paul Serice
diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/export.c linux-2.6.7-rc2-isofs.3/fs/isofs/export.c
fs/isofs/export.c +0 -0

...

Quoted 3 lines

+/* The .get_parent method should be added, but .get_parent has never
+ * been implemented in the isofs code. So, its absence will not be
+ * sorely missed. */

Obviously this comment is stale.

fs/isofs/inode.c root_found: · line 729

Quoted 6 lines

diff -uprN -X dontdiff linux-2.6.7-rc2/fs/isofs/inode.c linux-2.6.7-rc2-isofs.3/fs/isofs/inode.c
fs/isofs/inode.c +0 -0
@@ -740,17 +728,14 @@ root_found:
 
 	/* RDE: data zone now byte offset! */

This comment is now wrong too.

Quoted 6 lines

fs/isofs/inode.c +2 -3

-	first_data_zone = ((isonum_733 (rootp->extent) +
-			  isonum_711 (rootp->ext_attr_length))
-			 << sbi->s_log_zone_size);
+	first_data_zone = isonum_733 (rootp->extent) +
+			  isonum_711 (rootp->ext_attr_length);
 	sbi->s_firstdatazone = first_data_zone;

Paul Serice

author

2004-06-02 13:47 UTC #2 lore raw

Sergey, thanks for looking over the original patch. The incremental patch is attached.

fs/isofs/export.c +0 -3

diff -uprN -X dontdiff linux-2.6.7-rc2-isofs.3.orig/fs/isofs/export.c linux-2.6.7-rc2-isofs.3/fs/isofs/export.c
@@ -220,9 +220,6 @@ isofs_export_decode_fh(struct super_bloc
 }
 
 
-/* The .get_parent method should be added, but .get_parent has never
- * been implemented in the isofs code.  So, its absence will not be
- * sorely missed. */
 struct export_operations isofs_export_ops = {
 	.decode_fh	= isofs_export_decode_fh,
 	.encode_fh	= isofs_export_encode_fh,

fs/isofs/inode.c +0 -2

diff -uprN -X dontdiff linux-2.6.7-rc2-isofs.3.orig/fs/isofs/inode.c linux-2.6.7-rc2-isofs.3/fs/isofs/inode.c
@@ -726,8 +726,6 @@ root_found:
 	/* Set this for reference. Its not currently used except on write
 	   which we don't have .. */
 	   
-	/* RDE: data zone now byte offset! */
-
 	first_data_zone = isonum_733 (rootp->extent) +
 			  isonum_711 (rootp->ext_attr_length);
 	sbi->s_firstdatazone = first_data_zone;

Eric Lammerts

2004-06-09 05:24 UTC #3 lore raw

In reply to Paul Serice

Quoted 6 lines · Paul Serice

The inode number scheme was also changed. Continuing to use the byte offset would have resulted in non-unique inodes in many common situations, but because the inode number no longer plays any role in reading the meta-data off the disk, I was free to set the inode number to some unique characteristic of the file. I have chosen to use the block offset which is also 32-bits wide.

But what about 0-byte files? The block offset could be the same for all 0-byte files, or worse, it could be the same as the block offset of a non-0-byte file.

I don't know if this has been mentioned before, but since a directory record is always 34 bytes or bigger, why not simply divide the directory record byte offset by 32? I.e.,

- inode_number = (bh->b_blocknr << bufbits) + offset;
+ inode_number = (bh->b_blocknr << (bufbits - 5)) + (offset >> 5);

Eric

Paul Serice

author

2004-06-09 10:04 UTC #4 lore raw

Quoted 3 lines

But what about 0-byte files? The block offset could be the same for all 0-byte files, or worse, it could be the same as the block offset of a non-0-byte file.

For my latest patch, the only complaints (so far) have been regarding my inode numbering scheme. So, I would like to keep the switch from iget() to iget5_locked() to allow the NFS get_parent() method to work which has always been missing.

So basically, I think we are talking about a one line change to the isofs_get_ino() function in include/linux/iso_fs.h. I only mention this because I don't want to seem too defensive about my choice of inode numbers. I'm more than happy to make the change to another inode numbering scheme, but before doing that I would like to defend the one I chose.

Review

Quoted 6 lines

I don't know if this has been mentioned before, but since a directory record is always 34 bytes or bigger, why not simply divide the directory record byte offset by 32? I.e.,
(quoted diff) +1 -1
-   inode_number = (bh->b_blocknr << bufbits) + offset;
+   inode_number = (bh->b_blocknr << (bufbits - 5)) + (offset >> 5);

There was a previous e-mail from Sergey Vlasov that suggested this, and the second patch I posted (which was buggy) tried to implement this. I posted the patch to the cdwrite mailing list, and J"org Schilling told me that "the assumptions were correct but that the conclusions were wrong" and that because of this I was assigning duplicate inode numbers. I get the feeling that carving out 6 bits (11 - 5) for the offset is not sufficient. I was never able to get to the bottom of it, and he never really elaborated further. Your math is somewhat different so maybe you don't have the problem.

So there's that degree of uncertainty, and there's the problem that this approach also assigns duplicate inode numbers starting at block 67108864.

I think the next generation of storage media will come close to reaching this block count. So, I decided to abandon my second patch in order to find a solution that can handle the maximum block count allowed by the ISO 9660 standard. If not now, it is going to have to be done in a number of years anyway.

So my thoughts on what would make a good inode number ran down two lines. The first line of reasoning is that I know "ls" and "find" required inode numbers to be unique among directories, or they will not recurse down some directories. I think my patch provides "ls" and "find" with what they need.

The second line of reasoning is that I do not know of any other common use of inode numbers in user space, and while posix says inode numbers shall be unique, BSD (at least NetBSD) appears to me to assign non-unique inode numbers for files by returning the lower 32 bits of the byte offset.

I did have another idea, but it has limitations too. We could use the upper 16 bits of the inode number to store the index into the Path Table and use the lower 16 bits to store the index into the directory. This would limit the number of directories and the number of directory entries per directory to 65535 each. I have never been able to figure out what the Optional Occurrence of the Path Table is used for so I have never pursued this approach, and I'm not sure that the arbitrary limitation on the number of directories and directory entries is worth a few duplicate inode numbers in cases where two files actually do point to the same block on disc.

In conclusion, I just don't see much long-term difference in any of the inode numbering schemes, and the advantage of the scheme in my patch is that directories should always have unique inode numbers which to me is the important case. So, that's my reasoning, but I'm not married to it.

Eric Lammerts

2004-06-09 13:15 UTC #5 lore raw

Quoted 6 lines

The second line of reasoning is that I do not know of any other common use of inode numbers in user space, and while posix says inode numbers shall be unique, BSD (at least NetBSD) appears to me to assign non-unique inode numbers for files by returning the lower 32 bits of the byte offset.

Tar uses inode numbers to determine which files are hardlinked. So if you tar up a tree containing 0-byte files, then untar it somewhere, all 0-byte files will end up being hardlinked to each other. The same happens when you use cp -a.

Quoted 4 lines

In conclusion, I just don't see much long-term difference in any of the inode numbering schemes, and the advantage of the scheme in my patch is that directories should always have unique inode numbers which to me is the important case.

Or take a hybrid approach: use your scheme for directories and my scheme for files; use bit 0 or bit 31 to indicate what scheme is used. Then directories have unique inode numbers, and files too as long as their directory records are in the first 64Gb of the disc.

Eric

Paul Serice

author

2004-06-10 03:23 UTC #6 lore raw

Quoted 4 lines

Tar uses inode numbers to determine which files are hardlinked. So if you tar up a tree containing 0-byte files, then untar it somewhere, all 0-byte files will end up being hardlinked to each other. The same happens when you use cp -a.

Ahhh! O.k., that changes everything.

Quoted 4 lines

Or take a hybrid approach: use your scheme for directories and my scheme for files; use bit 0 or bit 31 to indicate what scheme is used. Then directories have unique inode numbers, and files too as long as their directory records are in the first 64Gb of the disc.

An incremental patch is attached that should apply cleanly to the latest -mm tree. It's not a hybrid. It is a straight implementation of your suggestion. Hopefully this will make all inode numbers unique for images less than 128GB in size.

Thanks

fs/isofs/dir.c +12 -3

diff -uprN -X dontdiff linux-2.6.7-rc3-mm1/fs/isofs/dir.c linux-2.6.7-rc3-mm1-isofs.3/fs/isofs/dir.c
@@ -106,7 +106,7 @@ static int do_isofs_readdir(struct inode
 {
 	unsigned long bufsize = ISOFS_BUFFER_SIZE(inode);
 	unsigned char bufbits = ISOFS_BUFFER_BITS(inode);
-	unsigned long block, offset;
+	unsigned long block, offset, block_saved, offset_saved;
 	unsigned long inode_number = 0;	/* Quiet GCC */
 	struct buffer_head *bh = NULL;
 	int len;

@@ -129,8 +129,6 @@ static int do_isofs_readdir(struct inode
 		}
 
 		de = (struct iso_directory_record *) (bh->b_data + offset);
-		if (first_de)
-			inode_number = isofs_get_ino(de);
 
 		de_len = *(unsigned char *) de;

@@ -147,6 +145,8 @@ static int do_isofs_readdir(struct inode
 			continue;
 		}
 
+		block_saved = block;
+		offset_saved = offset;
 		offset += de_len;
 
 		/* Make sure we have a full directory entry */

@@ -166,6 +166,15 @@ static int do_isofs_readdir(struct inode
 			de = tmpde;
 		}
 
+		if (first_de) {
+			isofs_normalize_block_and_offset(de,
+							 &block_saved,
+							 &offset_saved);
+			inode_number = isofs_get_ino(block_saved,
+						     offset_saved,
+						     bufbits);
+		}
+
 		if (de->flags[-sbi->s_high_sierra] & 0x80) {
 			first_de = 0;
 			filp->f_pos += de_len;

fs/isofs/inode.c +4 -2

diff -uprN -X dontdiff linux-2.6.7-rc3-mm1/fs/isofs/inode.c linux-2.6.7-rc3-mm1-isofs.3/fs/isofs/inode.c
@@ -7,7 +7,7 @@
  *      1995  Mark Dobie - allow mounting of some weird VideoCDs and PhotoCDs.
  *	1997  Gordon Chaffee - Joliet CDs
  *	1998  Eric Lammerts - ISO 9660 Level 3
- *	2004  Paul Serice - Comprehensive Inode Scheme
+ *	2004  Paul Serice - Inode Support pushed out from 4GB to 128GB
  *	2004  Paul Serice - NFS Export Operations
  */

@@ -1229,7 +1229,9 @@ static void isofs_read_inode(struct inod
 		de = tmpde;
 	}
 
-	inode->i_ino = isofs_get_ino(de);
+	inode->i_ino = isofs_get_ino(ei->i_iget5_block,
+				     ei->i_iget5_offset,
+				     ISOFS_BUFFER_BITS(inode));
 
 	/* Assume it is a normal-format file unless told otherwise */
 	ei->i_file_format = isofs_file_normal;

include/linux/iso_fs.h +6 ~~-12~~

diff -uprN -X dontdiff linux-2.6.7-rc3-mm1/include/linux/iso_fs.h linux-2.6.7-rc3-mm1-isofs.3/include/linux/iso_fs.h
@@ -237,19 +237,13 @@ extern struct inode *isofs_iget(struct s
 
 /* Because the inode number is no longer relevant to finding the
  * underlying meta-data for an inode, we are free to choose a more
- * convenient 32-bit number as the inode number.  Because directories
- * and files are block aligned (except in a few very unusual cases)
- * and because blocks are limited to 32-bits, I've chosen the starting
- * block that holds the file or directory data as the inode number.
- *
- * One nice side effect of this is that you can use "ls -i" to get the
- * inode number which will tell you exactly where you need to start a
- * hex dump if you want to see the contents of the directory or
- * file. */
-static inline unsigned long isofs_get_ino(struct iso_directory_record *d)
+ * convenient 32-bit number as the inode number.  The inode numbering
+ * scheme was recommended by Sergey Vlasov and Eric Lammerts. */
+static inline unsigned long isofs_get_ino(unsigned long block,
+					  unsigned long offset,
+					  unsigned long bufbits)
 {
-	return (unsigned long)isonum_733(d->extent)
-		+ (unsigned long)isonum_711(d->ext_attr_length);
+	return (block << (bufbits - 5)) | (offset >> 5);
 }
 
 /* Every directory can have many redundant directory entries scattered