Skip to contentSkip to conversation

ensure i_ino uniqueness in filesystems without permanent inode numbers (via pointer conversion)

RFC PATCH In review Jeff Layton 4 participants 11 messages Nov 17, 2006 VFS

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 ensure i_ino uniqueness in filesystems without permanent inode numbers (via pointer conversion)

Here's a completely different approach to ensuring inode uniqueness. This one was inspired by a suggestion by Al Viro. I'll refer to my earlier email for a description of the problem...

We already have what could be considered a unique number for each inode -- the inode pointer address. The problem is converting that into an i_ino value.

With this patch, when new_inode is called, we pretend that all of the kernel memory is one huge array of inode pointers, and determine what the position of the pointer would be in the array. We then take that value, and mask off anything higher than 32 bits. Obviously this is a much cheaper operation than keeping track of what's been allocated.

Since we're masking off the high bits, we have a chance for collisions when those bits become significant. On my x86_64 FC6 machine, an inode struct is 720 bytes according to slabinfo. The next lowest power of two is 512 (2^9), so we automatically get 9 bits for "free". So this scheme can cope with any situation where two inode addresses are not more than 2^41 (2 petabytes) apart.

This calculation was done quickly, so I might be off by one exponentially, but still I think we'd probably be OK for the next several years with this scheme. inode structs are smaller on 32 bit boxes, but they won't have 64-bit pointers so this won't be an issue there.

There are a couple of problems, but I think this patch should address them too:

1) because the slab allocator tends to reuse slab objects quickly, i_ino's get reused quickly. The patch copes with this by removing the initialization of i_generation from alloc_inode, and having new_inode increment that value. This should make sure that when an inode slab object is reused that it at least has a different i_generation than before (barring major page allocation/release churn in the slab). There may be callers of new_inode that assume that the i_generation they get is 0. They'll need to be fixed with this scheme, but that should be fairly easy.

2) this scheme would effectively leak inode addresses into userspace. I'm not sure if that would be exploitable, but it's probably best not to do it. The patch adds a static unsigned int that is initialized to a random value at boot time. We'll xor the inode offset with this value. That should allow for a unique i_ino value, but since the xor mask would be secret, it shouldn't be possible to turn it back into an address. There may be a more secure way to do this. I'm definitely open to suggestions here.

Again, patch is still a little rough but this one shouldn't need much work if it looks good. Comments, thoughts, suggestions appreciated.

Thanks,
Jeff

fs/inode.c renamed from fs/inode.c.ino2uint +15 -3
@@ -22,6 +22,7 @@
 #include <linux/bootmem.h>
 #include <linux/inotify.h>
 #include <linux/mount.h>
+#include <linux/random.h>
 
 /*
  * This is needed for the following functions:
@@ -98,6 +99,15 @@ static DEFINE_MUTEX(iprune_mutex);
 struct inodes_stat_t inodes_stat;
 
 static kmem_cache_t * inode_cachep __read_mostly;
+static unsigned int inode_xor_mask;
+
+/* convert an inode address into an unsigned int and xor it with a random value
+ * determined at boot time */
+static inline unsigned int inode_to_uint (struct inode *inode)
+{
+	return ((((unsigned long) (inode - (struct inode *) 0))
+		 ^ inode_xor_mask) & 0xffffffff);
+}
 
 static struct inode *alloc_inode(struct super_block *sb)
 {
@@ -125,7 +135,6 @@ static struct inode *alloc_inode(struct 
 		inode->i_size = 0;
 		inode->i_blocks = 0;
 		inode->i_bytes = 0;
-		inode->i_generation = 0;
 #ifdef CONFIG_QUOTA
 		memset(&inode->i_dquot, 0, sizeof(inode->i_dquot));
 #endif
@@ -546,7 +555,6 @@ repeat:
  */
 struct inode *new_inode(struct super_block *sb)
 {
-	static unsigned long last_ino;
 	struct inode * inode;
 
 	spin_lock_prefetch(&inode_lock);
@@ -557,7 +565,8 @@ struct inode *new_inode(struct super_blo
 		inodes_stat.nr_inodes++;
 		list_add(&inode->i_list, &inode_in_use);
 		list_add(&inode->i_sb_list, &sb->s_inodes);
-		inode->i_ino = ++last_ino;
+		inode->i_ino = inode_to_uint(inode);
+		inode->i_generation++;
 		inode->i_state = 0;
 		spin_unlock(&inode_lock);
 	}
@@ -1393,6 +1402,9 @@ void __init inode_init(unsigned long mem
 
 	for (loop = 0; loop < (1 << i_hash_shift); loop++)
 		INIT_HLIST_HEAD(&inode_hashtable[loop]);
+
+	/* initialize the xor mask for unique inode generation */
+	get_random_bytes(&inode_xor_mask, sizeof(inode_xor_mask));
 }
 
 void init_special_inode(struct inode *inode, umode_t mode, dev_t rdev)
#1 lore raw

fs/inode.c static DEFINE_MUTEX(iprune_mutex); · line 110

Quoted 7 lines · Jeff Layton
fs/inode.c renamed from fs/inode.c.ino2uint +7 -0
+/* convert an inode address into an unsigned int and xor it with a random value
+ * determined at boot time */
+static inline unsigned int inode_to_uint (struct inode *inode)
+{
+	return ((((unsigned long) (inode - (struct inode *) 0))
+		 ^ inode_xor_mask) & 0xffffffff);
+}

Seems a little obfuscated. Why not simply:

	return ((unsigned long)inode ^ inode_xor_mask) & 0xffffffff;

fs/inode.c static struct inode *alloc_inode(struct · line 140

Quoted 8 lines
fs/inode.c renamed from fs/inode.c.ino2uint +0 -1
@@ -125,7 +135,6 @@ static struct inode *alloc_inode(struct 
 		inode->i_size = 0;
 		inode->i_blocks = 0;
 		inode->i_bytes = 0;
-		inode->i_generation = 0;
 #ifdef CONFIG_QUOTA
 		memset(&inode->i_dquot, 0, sizeof(inode->i_dquot));
 #endif

It seems to me that filesystems with fake inodes could instead initialise i_generation to, say, jiffies. What do you think to that?

I like this idea, very creative.

#2 lore raw
Quoted 11 lines · Matthew Wilcox

fs/inode.c static DEFINE_MUTEX(iprune_mutex); · line 110

Quoted 7 lines · Jeff Layton
fs/inode.c renamed from fs/inode.c.ino2uint +7 -0
+/* convert an inode address into an unsigned int and xor it with a random value
+ * determined at boot time */
+static inline unsigned int inode_to_uint (struct inode *inode)
+{
+	return ((((unsigned long) (inode - (struct inode *) 0))
+		 ^ inode_xor_mask) & 0xffffffff);
+}

Seems a little obfuscated. Why not simply:

Quoted 1 line
	return ((unsigned long)inode ^ inode_xor_mask) & 0xffffffff;

Because that could give i_ino collisions with >4GiB memory. The original would require something like 2PiB memory before the first collision.

What I wonder, though, is how much code gcc generates for the pointer arithmetic. Maybe something like

	return (((unsigned long)inode >> INODE_SHIFT) ^ inode_xor_mask)
			& 0xffffffff);

would be faster.

Quoted 11 lines

fs/inode.c static struct inode *alloc_inode(struct · line 140

Quoted 8 lines
fs/inode.c renamed from fs/inode.c.ino2uint +0 -1
@@ -125,7 +135,6 @@ static struct inode *alloc_inode(struct 
 		inode->i_size = 0;
 		inode->i_blocks = 0;
 		inode->i_bytes = 0;
-		inode->i_generation = 0;
 #ifdef CONFIG_QUOTA
 		memset(&inode->i_dquot, 0, sizeof(inode->i_dquot));
 #endif

It seems to me that filesystems with fake inodes could instead initialise i_generation to, say, jiffies. What do you think to that?

If you are talking about inode_init_once() here, I like the idea. i_generation must be initialized somehow, even a 4-byte information leak could be a problem. But the initialization should happen in the rare event of allocating a slab page, not when reusing a deleted inode.

Jeff, why do you increment i_generation in new_inode instead of here?

Jörn

Signature · 6 lines
...one more straw can't possibly matter...
-- Kirby Bakken
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#3 lore raw
Quoted 7 lines · Jörn Engel

If you are talking about inode_init_once() here, I like the idea. i_generation must be initialized somehow, even a 4-byte information leak could be a problem. But the initialization should happen in the rare event of allocating a slab page, not when reusing a deleted inode.

Jeff, why do you increment i_generation in new_inode instead of here?

I suppose we could do that...that might be better for stuff that calls alloc_inode directly.

-- Jeff

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#4 lore raw
In reply to Matthew Wilcox
Quoted 11 lines · Matthew Wilcox

fs/inode.c static DEFINE_MUTEX(iprune_mutex); · line 110

Quoted 7 lines · Jeff Layton
fs/inode.c renamed from fs/inode.c.ino2uint +7 -0
+/* convert an inode address into an unsigned int and xor it with a random value
+ * determined at boot time */
+static inline unsigned int inode_to_uint (struct inode *inode)
+{
+	return ((((unsigned long) (inode - (struct inode *) 0))
+		 ^ inode_xor_mask) & 0xffffffff);
+}

Seems a little obfuscated. Why not simply:

Quoted 1 line
	return ((unsigned long)inode ^ inode_xor_mask) & 0xffffffff;

Because the lower 8-9 bits of the inode pointer aren't significant (presuming an inode struct size of ~400-800 bytes). If we take those out of the picture then we extend the range of addresses that we can uniquely squish into a 32 bit value.

Of course, all of this depends on the idea that the slab allocator grabs pages that are somewhat close together in the kernel's address space. I'm trying to figure out whether that is the case or not...

I've also been told that the address subtraction above is bogus and undefined, though it does seem to work. I'll probably need to respin that part into actual bit shifts by hand...

-- Jeff

#5 lore raw
Quoted 8 lines · Jeff Layton

Because the lower 8-9 bits of the inode pointer aren't significant (presuming an inode struct size of ~400-800 bytes). If we take those out of the picture then we extend the range of addresses that we can uniquely squish into a 32 bit value.

Of course, all of this depends on the idea that the slab allocator grabs pages that are somewhat close together in the kernel's address space. I'm trying to figure out whether that is the case or not...

It sounds like we can't count on that though. A NUMA system will apparently map pages *anywhere* within the entire 64-bit address range. If that's the case, we can't count on the addresses being close enough together to make this work.

Bummer, I really liked this scheme :-). I suppose I'll have to look at other options...

-- Jeff

#6 lore raw
In reply to Jeff Layton
Quoted 8 lines · Jeff Layton

2) this scheme would effectively leak inode addresses into userspace. I'm not sure if that would be exploitable, but it's probably best not to do it. The patch adds a static unsigned int that is initialized to a random value at boot time. We'll xor the inode offset with this value. That should allow for a unique i_ino value, but since the xor mask would be secret, it shouldn't be possible to turn it back into an address. There may be a more secure way to do this. I'm definitely open to suggestions here.

I *think* the xor mask is mere obfuscation. It looks likely that you can recover it with a little bit of trial and error. If you can force the filesystem to hand you back new inodes quickly such that there is a high probability you get consecutive allocations, you'll get a sequence which would be spaced 700-odd bytes apart, except that it's been xored. Since you know it's incrementing, if you see the sequence decrease, you'll know that was a 1 in that bit.

It'd be a bit more complex than that, and cryptanalysis was never my forte, but I suspect we should either use a folded hash like md5, or give up and just divide the address by sizeof(struct inode). Sure, divides are slow, but this is a divide by a constant, so it shouldn't be that bad.

#7 lore raw
Quoted 7 lines · Matthew Wilcox

I *think* the xor mask is mere obfuscation. It looks likely that you can recover it with a little bit of trial and error. If you can force the filesystem to hand you back new inodes quickly such that there is a high probability you get consecutive allocations, you'll get a sequence which would be spaced 700-odd bytes apart, except that it's been xored. Since you know it's incrementing, if you see the sequence decrease, you'll know that was a 1 in that bit.

I think you're right, the addresses would often be sequential, so this is probably crackable. I'll look over the md5 routines when I get the chance, though if someone more cryptographically inclined than I has a different suggestion, I'd love to hear it.
-- Jeff

#8 lore raw
Quoted 11 lines · Jeff Layton
Quoted 7 lines · Matthew Wilcox

I *think* the xor mask is mere obfuscation. It looks likely that you can recover it with a little bit of trial and error. If you can force the filesystem to hand you back new inodes quickly such that there is a high probability you get consecutive allocations, you'll get a sequence which would be spaced 700-odd bytes apart, except that it's been xored. Since you know it's incrementing, if you see the sequence decrease, you'll know that was a 1 in that bit.

I think you're right, the addresses would often be sequential, so this is probably crackable.

Wouldn't you only be able to only crack a few of the low-order bits due to a cluster of inodes being sequential? I don't think you'd be able crack enough of it to be useful. You may be able to determine where some inodes are relative to others, but I don't think you'd be able to point the their location in memory. I don't know anything about crypto, so I could be wrong.

Quoted 4 lines

I'll look over the md5 routines when I get the
chance, though if someone more cryptographically inclined than I has a different suggestion, I'd love to hear it.
-- Jeff

Shaggy

Signature · 2 lines
David Kleikamp
IBM Linux Technology Center
#9 lore raw
Quoted 7 lines · Dave Kleikamp

Wouldn't you only be able to only crack a few of the low-order bits due to a cluster of inodes being sequential? I don't think you'd be able crack enough of it to be useful. You may be able to determine where some inodes are relative to others, but I don't think you'd be able to point the their location in memory. I don't know anything about crypto, so I could be wrong.

On a 64-bit kernel, that would be the case. On a 32-bit kernel, there are no high order bits to chop off, so this would effectively give you the address.
-- Jeff

#10 lore raw
Quoted 10 lines · Jeff Layton
Quoted 7 lines · Dave Kleikamp

Wouldn't you only be able to only crack a few of the low-order bits due to a cluster of inodes being sequential? I don't think you'd be able crack enough of it to be useful. You may be able to determine where some inodes are relative to others, but I don't think you'd be able to point the their location in memory. I don't know anything about crypto, so I could be wrong.

Quoted 3 lines

On a 64-bit kernel, that would be the case. On a 32-bit kernel, there are no high order bits to chop off, so this would effectively give you the address.

By a few of the low-order bits, I mean very few, not 32. The slab allocator generally allocates one page at a time, so you typically don't get more than about 6 inodes in a slab page. Even if you consider that you may be able allocate several slab pages together, it would be hard to get very many contiguous pages of inode slab cache. Even if it were possible to force the system to allocate around 256 contiguous inodes, you would still only be able to determine 8 bits out of 32. At most one or two more if you could determine a pattern of inode numbers that would be skipped due to the inclusion of struct inode within the fs-dependent inode structure. I may be wrong, but I doubt that someone could determine the entire mask from the observed i_ino's.

Shaggy

Signature · 2 lines
David Kleikamp
IBM Linux Technology Center