ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)
Subsystems (3)
RFC PATCH 1/1 ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)
This patch is a proof of concept. It works, but still needs a bit of polish before it's ready for submission. First, the problems:
1) on filesystems w/o permanent inode numbers, i_ino values can be larger than 32 bits, which can cause problems for some 32 bit userspace programs on a 64 bit kernel.
2) many filesystems call new_inode and assume that the i_ino values they are given are unique. They are not guaranteed to be so, since the static counter can wrap.
3) after allocating a new inode, some filesystems call iunique to try to get a unique i_ino value, but they don't actually add their inodes to the hashtable, and so they're still not guaranteed to be unique.
This patch is a first step at correcting these problems. It declares a new file_system_type flag (FS_I_INO_DYNAMIC). If this is set, then when new_inode is called, we'll use the IDR functions to generate a unique 31-bit value, leaving the first 100 inode numbers for statically allocated stuff like root inodes, etc. At inode deletion time, we idr_remove it so the i_ino value can be reused.
The patch also converts pipefs to use the new scheme (though the conversion just consists of setting the fs_flags value for its file_system_type).
There are some things that need to be cleaned up, of course:
- error handling for the idr calls
- recheck all the possible places where the inode should be unhashed
- don't attempt to remove inodes with values <100
- convert other filesystems
- remove the static counter from new_inode and (maybe) eliminate iunique
It seems to basically work, but there is one oddity. idr seems to prefer reusing values when it can. So if a program, for instance, makes a pipe, then closes it, and makes a new one, the second one is likely to get the same st_ino value as the first one. The value is still unique, but I have to wonder if this may cause some userspace programs to get confused...
I'm posting this to get some feedback. If this approach seems acceptable, then I'll clean up the patch and start working on converting the filesystems individually.
Comments and suggestions appreciated...
-- Jeff
fs/inode.c +20 -1
@@ -93,6 +93,12 @@ DEFINE_SPINLOCK(inode_lock);static DEFINE_MUTEX (iprune_mutex);/* +* for filesystems that dynamically allocate inode numbers, we reserve the +* first 100 for statically assigned values (root inodes and such) +*/ +#define DYNAMIC_I_INO_RESERVED 100 + +/* * Statistics gathering.. */ struct inodes_stat_t inodes_stat;
@@ -116,6 +122,7 @@ static struct inode *alloc_inode(struct inode->i_sb = sb; inode->i_blkbits = sb->s_blocksize_bits; + inode->i_ino =0 ; inode->i_flags =0 ;atomic_set (&inode->i_count,1 ); inode->i_op = &empty_iops;
@@ -286,6 +293,8 @@ static void dispose_list(struct list_heaspin_lock (&inode_lock);hlist_del_init (&inode->i_hash);list_del_init (&inode->i_sb_list); +if (inode->i_sb->s_type->fs_flags &FS_I_INO_DYNAMIC ) +idr_remove (&inode->i_sb->s_inode_ids, inode->i_ino);spin_unlock (&inode_lock);wake_up_inode (inode);
@@ -531,11 +540,17 @@ struct inode *new_inode(struct super_blo inode =alloc_inode (sb);if (inode) { +if (sb->s_type->fs_flags &FS_I_INO_DYNAMIC ) +idr_pre_get (&sb->s_inode_ids,GFP_KERNEL );spin_lock (&inode_lock); 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; +if (sb->s_type->fs_flags &FS_I_INO_DYNAMIC ) +idr_get_new_above (&sb->s_inode_ids, inode, +DYNAMIC_I_INO_RESERVED , (int *) &inode->i_ino); +else + inode->i_ino = ++last_ino; inode->i_state =0 ;spin_unlock (&inode_lock); }
@@ -1024,6 +1039,8 @@ void generic_delete_inode(struct inode * }spin_lock (&inode_lock);hlist_del_init (&inode->i_hash); +if (inode->i_sb->s_type->fs_flags &FS_I_INO_DYNAMIC ) +idr_remove (&inode->i_sb->s_inode_ids, inode->i_ino);spin_unlock (&inode_lock);wake_up_inode (inode);BUG_ON (inode->i_state !=I_CLEAR );
@@ -1052,6 +1069,8 @@ static void generic_forget_inode(struct inodes_stat.nr_unused--;hlist_del_init (&inode->i_hash); } +if (inode->i_sb->s_type->fs_flags &FS_I_INO_DYNAMIC ) +idr_remove (&sb->s_inode_ids, inode->i_ino);list_del_init (&inode->i_list);list_del_init (&inode->i_sb_list); inode->i_state |=I_FREEING ;
fs/pipe.c +1 -0
@@ -1005,6 +1005,7 @@ static struct file_system_type pipe_fs_t .name = "pipefs", .get_sb = pipefs_get_sb, .kill_sb = kill_anon_super, + .fs_flags = FS_I_INO_DYNAMIC, };static int __init init_pipe_fs (void )
fs/super.c +1 -0
@@ -93,6 +93,7 @@ static struct super_block *alloc_super(s s->s_qcop = sb_quotactl_ops; s->s_op = &default_op; s->s_time_gran =1000000000 ; +idr_init (&s->s_inode_ids); } out:return s;
include/linux/fs.h +5 -0
@@ -91,6 +91,7 @@ #define SEL_EX 4/* public flags for file_system_type */ #define FS_REQUIRES_DEV 1#define FS_BINARY_MOUNTDATA 2 +#define FS_I_INO_DYNAMIC 4/* i_ino values are not permanent */ #define FS_REVAL_DOT 16384/* Check the paths ".", ".." for staleness */ #define FS_RENAME_DOES_D_MOVE 32768/* FS will handle d_move() * during rename() internally.
@@ -278,6 +279,7 @@ #include <linux/prio_tree.h>#include <linux/init.h> #include <linux/sched.h> #include <linux/mutex.h> +#include <linux/idr.h> #include <asm/atomic.h> #include <asm/semaphore.h>
@@ -961,6 +963,9 @@ #endif/* Granularity of c/m/atime in ns. Cannot be worse than a second */ u32 s_time_gran; + +/* for fs's with dynamic i_ino values, track them with idr */ +struct idr s_inode_ids; };extern struct timespec current_fs_time (struct super_block *sb);
Quoted 6 lines · Jeff Layton
This patch is a first step at correcting these problems. It declares a new
file_system_typeflag (FS_I_INO_DYNAMIC). If this is set, then whennew_inodeis called, we'll use the IDR functions to generate a unique 31-bit value, leaving the first 100 inode numbers for statically allocated stuff like root inodes, etc. At inode deletion time, weidr_removeit so thei_inovalue can be reused.
NAK. All calls of new_inode() are triggered from within fs code; there's no reason to introduce flags (which should be the last resort) when you bloody well can have a separate helpers for that case and have them called. Explicitly.
Quoted 4 lines · Al Viro
NAK. All calls of
new_inode()are triggered from within fs code; there's no reason to introduce flags (which should be the last resort) when you bloody well can have a separate helpers for that case and have them called. Explicitly.
Ok, that sounds reasonable. Here's a respun patch. This adds 2 new functions, an idr_register and idr_unregister. Filesystems can call idr_register at inode creation time, and then at deletion time, we'll automatically unregister them. Again, this contains a conversion of pipefs to this scheme as an example. If this looks good, I'll start on the legwork to clean up the other filesystems that call new_inode.
This patch also adds a new s_generation counter to the superblock. Because i_ino's can be reused so quickly, we don't want NFS getting confused when it happens. When iunique_register is called, we'll assign the s_generation value to the i_generation, and then increment it to help ensure that we get different filehandles.
I've left the original iunique function in place here, and new_inode still has the static counter, but that stuff can all be ripped out once I convert the filesystems to the new scheme.
Again, comments appreciated...
-- Jeff
fs/inode.c +32 -0
@@ -288,6 +288,8 @@ static void dispose_list(struct list_healist_del_init (&inode->i_sb_list);spin_unlock (&inode_lock); +iunique_unregister (inode); +wake_up_inode (inode);destroy_inode (inode); nr_disposed++;
@@ -706,6 +708,34 @@ retry:EXPORT_SYMBOL (iunique); +int iunique_register (struct inode *inode,int max_reserved) +{ +int rv; + + rv =idr_pre_get (&inode->i_sb->s_inode_ids,GFP_KERNEL ); +if (! rv) +return -ENOMEM ; + +lock_super (inode->i_sb); + rv =idr_get_new_above (&inode->i_sb->s_inode_ids, inode, + max_reserved+1 , (int *) &inode->i_ino); + inode->i_generation = inode->i_sb->s_generation++; +unlock_super (inode->i_sb); +return rv; +} + +EXPORT_SYMBOL (iunique_register); + +void iunique_unregister (struct inode *inode) +{ +lock_super (inode->i_sb); +if (idr_find (&inode->i_sb->s_inode_ids, (int ) inode->i_ino)) +idr_remove (&inode->i_sb->s_inode_ids, (int ) inode->i_ino); +unlock_super (inode->i_sb); +} + +EXPORT_SYMBOL (iunique_unregister); +struct inode *igrab (struct inode *inode) {spin_lock (&inode_lock);
@@ -1025,6 +1055,7 @@ void generic_delete_inode(struct inode *spin_lock (&inode_lock);hlist_del_init (&inode->i_hash);spin_unlock (&inode_lock); +iunique_unregister (inode);wake_up_inode (inode);BUG_ON (inode->i_state !=I_CLEAR );destroy_inode (inode);
@@ -1057,6 +1088,7 @@ static void generic_forget_inode(struct inode->i_state |=I_FREEING ; inodes_stat.nr_inodes--;spin_unlock (&inode_lock); +iunique_unregister (inode);if (inode->i_data.nrpages)truncate_inode_pages (&inode->i_data,0 );clear_inode (inode);
fs/pipe.c +3 -0
@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voiif (!inode) goto fail_inode; +if (iunique_register (inode,0 )) + goto fail_iput; + pipe =alloc_pipe_info (inode);if (!pipe) goto fail_iput;
fs/super.c +1 -0
@@ -93,6 +93,7 @@ static struct super_block *alloc_super(s s->s_qcop = sb_quotactl_ops; s->s_op = &default_op; s->s_time_gran =1000000000 ; +idr_init (&s->s_inode_ids); } out:return s;
include/linux/fs.h +8 -0
@@ -278,6 +278,7 @@ #include <linux/prio_tree.h>#include <linux/init.h> #include <linux/sched.h> #include <linux/mutex.h> +#include <linux/idr.h> #include <asm/atomic.h> #include <asm/semaphore.h>
@@ -961,6 +962,11 @@ #endif/* Granularity of c/m/atime in ns. Cannot be worse than a second */ u32 s_time_gran; + +/* for fs's with dynamic i_ino values, track them with idr, and increment +the generation every time we register a new inode */ +__u32 s_generation; +struct idr s_inode_ids; };extern struct timespec current_fs_time (struct super_block *sb);
@@ -1681,6 +1687,8 @@ extern void inode_init_once(struct inodeextern void iput (struct inode *);extern struct inode *igrab (struct inode *);extern ino_t iunique (struct super_block *,ino_t ); +extern int iunique_register (struct inode *,int ); +extern void iunique_unregister (struct inode *);extern int inode_needs_sync (struct inode *inode);extern void generic_delete_inode (struct inode *inode);extern void generic_drop_inode (struct inode *inode);
lib/idr.c +0 -0
Quoted 3 lines · Jeff Layton
Ok, that sounds reasonable. Here's a respun patch. This adds 2 new functions, an
idr_registerandidr_unregister.
Doh! That should read iunique_register and iunique_unregister... -- Jeff
fs/inode.c retry: · line 719
Quoted 8 lines · Jeff Layton
fs/inode.c +8
-0+{ +int rv; + + rv =idr_pre_get (&inode->i_sb->s_inode_ids,GFP_KERNEL ); +if (! rv) +return -ENOMEM ; + +lock_super (inode->i_sb);
?!#!@#!???
Please, use something saner. Use of lock_super() for anything generic is wrong; using it for something that'd better be fast is even dumber...
fs/inode.c void generic_delete_inode(struct inode * · line 1058
Quoted 5 lines
fs/inode.c +1
-0@@ -1025,6 +1055,7 @@ void generic_delete_inode(struct inode *spin_lock (&inode_lock);hlist_del_init (&inode->i_hash);spin_unlock (&inode_lock); +iunique_unregister (inode);
Unconditional? Hitting every fs out there? With that kind of locking?
fs/inode.c static void generic_forget_inode(struct · line 1091
Quoted 8 lines
fs/inode.c +1
-0wake_up_inode (inode);BUG_ON (inode->i_state !=I_CLEAR );destroy_inode (inode);@@ -1057,6 +1088,7 @@ static void generic_forget_inode(struct inode->i_state |=I_FREEING ; inodes_stat.nr_inodes--;spin_unlock (&inode_lock); +iunique_unregister (inode);
Ditto.
Quoted 8 lines
fs/inode.c +0
-0if (inode->i_data.nrpages)truncate_inode_pages (&inode->i_data,0 );clear_inode (inode);fs/pipe.c +0
-0
fs/pipe.c static struct inode * get_pipe_inode(voi · line 850
Quoted 6 lines
fs/pipe.c +3
-0@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voiif (!inode) goto fail_inode; +if (iunique_register (inode,0 )) + goto fail_iput; +
Humm... I wonder what the overhead of that is going to be. There easily can be shitloads of pipes on the box, with all sorts of lifetimes. And we'd better be fast on that codepath...
Quoted 12 lines · Al Viro
fs/inode.c retry: · line 719
Quoted 8 lines · Jeff Layton
fs/inode.c +8
-0+{ +int rv; + + rv =idr_pre_get (&inode->i_sb->s_inode_ids,GFP_KERNEL ); +if (! rv) +return -ENOMEM ; + +lock_super (inode->i_sb);?!#!@#!???
Quoted 3 lines
Please, use something saner. Use of
lock_super()for anything generic is wrong; using it for something that'd better be fast is even dumber...
Well, I considered the inode_lock here, but since all of this stuff is per-sb, I thought s_lock would be a better choice. If that's not suitable, what do you suggest? A new spinlock to protect the new sb fields?
Quoted 8 lines
fs/inode.c void generic_delete_inode(struct inode * · line 1058
Quoted 5 lines
fs/inode.c +1
-0@@ -1025,6 +1055,7 @@ void generic_delete_inode(struct inode *spin_lock (&inode_lock);hlist_del_init (&inode->i_hash);spin_unlock (&inode_lock); +iunique_unregister (inode);Unconditional? Hitting every fs out there? With that kind of locking?
I'm not sure what condition I would base this on. That said, I don't think the impact would be too bad here though. Presumably, those filesystems that don't use iunique_register will have empty idr hashes and would return quickly.
Quoted 12 lines
Quoted 12 lines
fs/inode.c +0
-0if (inode->i_data.nrpages)truncate_inode_pages (&inode->i_data,0 );clear_inode (inode);fs/pipe.c +0
-0@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voiif (!inode) goto fail_inode;
Quoted 7 lines
fs/pipe.c static struct inode * get_pipe_inode(voi · line 850
Quoted 3 lines
fs/pipe.c +3
-0+if (iunique_register (inode,0 )) + goto fail_iput; +Humm... I wonder what the overhead of that is going to be. There easily can be shitloads of pipes on the box, with all sorts of lifetimes. And we'd better be fast on that codepath...
IDR is supposedly quick for this sort of thing though I don't have any numbers as of yet. Still, getting i_ino uniqueness isn't going to come for free. There will be some performance impact regardless of what scheme we use.
-- Jeff
Quoted 11 lines · Jeff Layton
1) on filesystems w/o permanent inode numbers,
i_inovalues can be larger than 32 bits, which can cause problems for some 32 bit userspace programs on a 64 bit kernel.2) many filesystems call
new_inodeand assume that thei_inovalues they are given are unique. They are not guaranteed to be so, since the static counter can wrap.3) after allocating a new inode, some filesystems call iunique to try to get a unique
i_inovalue, but they don't actually add their inodes to the hashtable, and so they're still not guaranteed to be unique.
I agree with these problems, but I liked your earlier approach to fixing them. I don't particularly like the idr approach because, as you say, it will reuse numbers rapidly.
Why is it these filesystems don't add their inodes to the hashtable? Might that not be a more profitable approach to fixing this problem?
Quoted 4 lines · Matthew Wilcox
I agree with these problems, but I liked your earlier approach to fixing them. I don't particularly like the idr approach because, as you say, it will reuse numbers rapidly.
Is that a problem for nfs only? Or are there others. For nfs, Jeff already increments i_generation, so the (i_ino|i_generation) tupel is not rapidly reused.
Quoted 2 lines
Why is it these filesystems don't add their inodes to the hashtable? Might that not be a more profitable approach to fixing this problem?
To keep the hashtable small, as per hch's request.
Jörn
Signature · 6 lines
/* Keep these two variables together */ int bar; - 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
Quoted 1 line · Jörn Engel
To keep the hashtable small, as per hch's request.
Adding to the hashtable was my first suggestion (and actually it still seems reasonable to me), but according to hch, the reason most of these filesystems don't add their inodes to the hashtable is that they are generally pinned in memory. Adding them might slow down inode lookups for filesystems that don't pin their inodes.
Still, even though they're pinned, we need to keep track of them somehow to know that i_ino is unique. idr is one way, but there are certainly others. Another approach would be to add a entirely separate hashtable for these inodes, but I figured I'd try this way first.
-- 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