[RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

[-- Attachment #1: Type: text/plain, Size: 2232 bytes --]

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, so they're still not guaranteed to be unique.

This patch is a first step at correcting these problems. 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.

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.

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

The patch also converts pipefs to use the new scheme as an example. Al
Viro had expressed some concern with an earlier patch that this might
slow down pipe creation. I've done some testing and I think the impact
will be minimal. Timing a small program that creates and closes 100
million pipes in a loop:

patched:
-------------
real    8m8.623s
user    0m37.418s
sys     7m31.196s

unpatched:
--------------
real    8m7.150s
user    0m40.943s
sys     7m26.204s

As the number of pipes grows on the system, this time may grow somewhat
but it doesn't seem like it would be terrible.

Comments and suggestions appreciated.

Signed-off-by: Jeff Layton <jlayton@redhat.com>



[-- Attachment #2: idr_register.patch --]
[-- Type: text/x-patch, Size: 3643 bytes --]

diff --git a/fs/inode.c b/fs/inode.c
index 26cdb11..841e2fc 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -288,6 +288,8 @@ static void dispose_list(struct list_hea
 		list_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;
+
+	spin_lock(&inode->i_sb->s_inode_ids_lock);
+	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++;
+	spin_unlock(&inode->i_sb->s_inode_ids_lock);
+	return rv;
+}
+
+EXPORT_SYMBOL(iunique_register);
+
+void iunique_unregister(struct inode *inode)
+{
+	spin_lock(&inode->i_sb->s_inode_ids_lock);
+	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);
+	spin_unlock(&inode->i_sb->s_inode_ids_lock);
+}
+
+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);
diff --git a/fs/pipe.c b/fs/pipe.c
index b1626f2..d74ae65 100644
--- a/fs/pipe.c
+++ b/fs/pipe.c
@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voi
 	if (!inode)
 		goto fail_inode;
 
+	if (iunique_register(inode, 0))
+		goto fail_iput;
+
 	pipe = alloc_pipe_info(inode);
 	if (!pipe)
 		goto fail_iput;
diff --git a/fs/super.c b/fs/super.c
index 47e554c..d2dbdec 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -93,6 +93,8 @@ 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);
+		spin_lock_init(&s->s_inode_ids_lock);
 	}
 out:
 	return s;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 2fe6e3f..3ad12a6 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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,12 @@ #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;
+	spinlock_t		s_inode_ids_lock;
 };
 
 extern struct timespec current_fs_time(struct super_block *sb);
@@ -1681,6 +1688,8 @@ extern void inode_init_once(struct inode
 extern 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);

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Randy Dunlap]

On Fri, 01 Dec 2006 09:48:36 -0500 Jeff Layton wrote:

> 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:
> 
> 
> This patch is a first step at correcting these problems. 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.

s/idr_/iunique_/

> 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.
> 
> 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

Please explain that one.  (May be obvious to some, but not to me.)

> - convert other filesystems
> 
> - remove the static counter from new_inode and (maybe) eliminate iunique
> 
> Comments and suggestions appreciated.


Better to post patches inline (for review) rather than as attachments.

Some (mostly style) comments on the patch:

+	rv = idr_pre_get(&inode->i_sb->s_inode_ids, GFP_KERNEL);
+	if (! rv)
+		return -ENOMEM;

	if (!rv)

+	rv = idr_get_new_above(&inode->i_sb->s_inode_ids, inode,
+		max_reserved+1, (int *) &inode->i_ino);

		max_reserved + 1,

+}
+
+EXPORT_SYMBOL(iunique_register);

No need for the extra blank line after the function closing
brace.  Just put the EXPORT_SYMBOL immediately on the next line.
(in multiple places)

@@ -1681,6 +1688,8 @@ extern void inode_init_once(struct inode
 extern 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);

Some of these have a parameter name, some don't.
Having a (meaningful) parameter name is strongly preferred.

---
~Randy

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

On Fri, Dec 01, 2006 at 08:52:27AM -0800, Randy Dunlap wrote:

Thanks for having a look, Randy...

> s/idr_/iunique_/

Doh! Can you tell I cut and pasted this email from earlier ones? :-)

> > - don't attempt to remove inodes with values <100
> 
> Please explain that one.  (May be obvious to some, but not to me.)

Actually, we probably don't need to do that now. My thought here was to add
a low range of i_ino numbers that could be used by the filesystem code without
needing to call iunique (in particular for things like the root inode in the
filesystem). It's probably best to not do this though and let the filesystem
handle it on its own.

> Better to post patches inline (for review) rather than as attachments.

Here's an updated (but untested) patch based on your suggestions. I also went
ahead and made the exported symbols GPL-only since that seems like it would be
appropriate here. Any further thoughts on it?

Signed-off-by: Jeff Layton <jlayton@redhat.com>

diff --git a/fs/inode.c b/fs/inode.c
index 26cdb11..e45cec9 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -288,6 +288,8 @@ static void dispose_list(struct list_hea
 		list_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,32 @@ 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;
+
+	spin_lock(&inode->i_sb->s_inode_ids_lock);
+	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++;
+	spin_unlock(&inode->i_sb->s_inode_ids_lock);
+	return rv;
+}
+EXPORT_SYMBOL_GPL(iunique_register);
+
+void iunique_unregister(struct inode *inode)
+{
+	spin_lock(&inode->i_sb->s_inode_ids_lock);
+	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);
+	spin_unlock(&inode->i_sb->s_inode_ids_lock);
+}
+EXPORT_SYMBOL_GPL(iunique_unregister);
+
 struct inode *igrab(struct inode *inode)
 {
 	spin_lock(&inode_lock);
@@ -1025,6 +1053,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 +1086,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);
diff --git a/fs/pipe.c b/fs/pipe.c
index b1626f2..d74ae65 100644
--- a/fs/pipe.c
+++ b/fs/pipe.c
@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voi
 	if (!inode)
 		goto fail_inode;
 
+	if (iunique_register(inode, 0))
+		goto fail_iput;
+
 	pipe = alloc_pipe_info(inode);
 	if (!pipe)
 		goto fail_iput;
diff --git a/fs/super.c b/fs/super.c
index 47e554c..d2dbdec 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -93,6 +93,8 @@ 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);
+		spin_lock_init(&s->s_inode_ids_lock);
 	}
 out:
 	return s;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 2fe6e3f..3afb4a2 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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,12 @@ #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;
+	spinlock_t		s_inode_ids_lock;
 };
 
 extern struct timespec current_fs_time(struct super_block *sb);
@@ -1681,6 +1688,8 @@ extern void inode_init_once(struct inode
 extern 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 *inode, int max_reserved);
+extern void iunique_unregister(struct inode *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);

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Randy Dunlap]

Jeff Layton wrote:
> On Fri, Dec 01, 2006 at 08:52:27AM -0800, Randy Dunlap wrote:
> 
> Thanks for having a look, Randy...
> 
>> s/idr_/iunique_/
> 
> Doh! Can you tell I cut and pasted this email from earlier ones? :-)
> 
>>> - don't attempt to remove inodes with values <100
>> Please explain that one.  (May be obvious to some, but not to me.)
> 
> Actually, we probably don't need to do that now. My thought here was to add
> a low range of i_ino numbers that could be used by the filesystem code without
> needing to call iunique (in particular for things like the root inode in the
> filesystem). It's probably best to not do this though and let the filesystem
> handle it on its own.
> 
>> Better to post patches inline (for review) rather than as attachments.
> 
> Here's an updated (but untested) patch based on your suggestions. I also went
> ahead and made the exported symbols GPL-only since that seems like it would be
> appropriate here. Any further thoughts on it?

Just needs new/updated patch description.
and one "typo" fixed.

> diff --git a/fs/inode.c b/fs/inode.c
> index 26cdb11..e45cec9 100644
> --- a/fs/inode.c
> +++ b/fs/inode.c
> @@ -706,6 +708,32 @@ 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)

No space after !, just:
	if (!rv)

> +		return -ENOMEM;
> +
> +	spin_lock(&inode->i_sb->s_inode_ids_lock);
> +	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++;
> +	spin_unlock(&inode->i_sb->s_inode_ids_lock);
> +	return rv;
> +}

Thanks.
-- 
~Randy

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Brad Boyer]

On Fri, Dec 01, 2006 at 12:21:36PM -0500, Jeff Layton wrote:
> Here's an updated (but untested) patch based on your suggestions. I also went
> ahead and made the exported symbols GPL-only since that seems like it would be
> appropriate here. Any further thoughts on it?

I don't know that this is a good idea. I know this isn't likely to be
a popular statement, but I think that there should be at least some
minor justification to making a symbol GPL-only (it won't take much).
This seems like exactly the sort of thing that should be a generic
service available to all filesystem implementors whether it's GPL or
not. The usual justification for GPL-only is that it's something
random modules shouldn't be touching anyway, but it's something that
some part of the tree which could be a module needs.

	Brad Boyer
	flar@allandria.com

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

Brad Boyer wrote:
> On Fri, Dec 01, 2006 at 12:21:36PM -0500, Jeff Layton wrote:
>> Here's an updated (but untested) patch based on your suggestions. I also went
>> ahead and made the exported symbols GPL-only since that seems like it would be
>> appropriate here. Any further thoughts on it?
> 

> This seems like exactly the sort of thing that should be a generic
> service available to all filesystem implementors whether it's GPL or
> not. The usual justification for GPL-only is that it's something
> random modules shouldn't be touching anyway, but it's something that
> some part of the tree which could be a module needs.

My main reasoning for doing this was that the structures involved are 
per-superblock. There is virtually no reason that a filesystem would 
ever need to touch these structures in another filesystem.

So, this is essentially a service to make it easy for filesystems to 
implement i_ino uniqueness. I'm not terribly interested in making things 
easier for proprietary filesystems, so I don't see a real reason to make 
this available to them. They can always implement their own scheme to do 
this.

I'm certainly open to discussion though. Is there a compelling reason to 
open this up to proprietary software authors?

-- Jeff

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Brad Boyer]

On Sat, Dec 02, 2006 at 09:56:27PM -0500, Jeff Layton wrote:
> My main reasoning for doing this was that the structures involved are 
> per-superblock. There is virtually no reason that a filesystem would 
> ever need to touch these structures in another filesystem.

I don't think this is relevant to the issue. I wouldn't expect that
if you allow people to use this functionality that they would go
poking around in other filesystems. I would expect people to use it
on the filesystem they are writing.

> So, this is essentially a service to make it easy for filesystems to 
> implement i_ino uniqueness. I'm not terribly interested in making things 
> easier for proprietary filesystems, so I don't see a real reason to make 
> this available to them. They can always implement their own scheme to do 
> this.

This sounds slightly petty to me. For example, generic_file_read() is
there just to make it easier to implement the read callback, but it
isn't required. In fact, I would think that any filesystem complex
enough to be worth making proprietary would not use it. However, that
doesn't seem to me to be a good argument for marking it GPL-only. The
functionality in question is easier to reimplement, but that doesn't
make it right to force it on people just because of a license choice.

> I'm certainly open to discussion though. Is there a compelling reason to 
> open this up to proprietary software authors?

I don't think there is a compelling reason to open it up since the
functionality could be reimplemented if needed, but I also think
the only reason it is being marked GPL-only is the very common
attitude that there should not be any proprietary modules.

To be honest, I think it looks bad for someone associated with redhat
to be suggesting that life should be made more difficult for those
who write proprietary software on Linux. The support from commercial
software is a major reason for the success of the RHEL product line.
I can't imagine that this attitude will affect support from software
companies as long as there is a demand for software on Linux, but
it isn't exactly supportive.

	Brad Boyer
	flar@allandria.com

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Al Boldi]

Brad Boyer wrote:
> To be honest, I think it looks bad for someone associated with redhat
> to be suggesting that life should be made more difficult for those
> who write proprietary software on Linux. The support from commercial
> software is a major reason for the success of the RHEL product line.

The real reason for the success of the RHEL product line is that its been GPL 
from the beginning.  And commercial software saw it fit to leverage this 
GPL-pool, which is OK, but to then come around and say that "The support 
from commercial software is a major reason for the success of the RHEL 
product line" is trying to portray the situation up-side-down.

This does not mean that we shouldn't allow non-GPL linkage, on the contrary, 
I am even calling for a stable API for the benefit of everyone, but it's 
probably the closed-source market's arrogant behavior that forces 
GPL-developers to respond in kind.  Which is rather sad, if you think about 
it.


Thanks!

--
Al

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

Brad Boyer wrote:
> 
> This sounds slightly petty to me. For example, generic_file_read() is
> there just to make it easier to implement the read callback, but it
> isn't required. In fact, I would think that any filesystem complex
> enough to be worth making proprietary would not use it. However, that
> doesn't seem to me to be a good argument for marking it GPL-only. The
> functionality in question is easier to reimplement, but that doesn't
> make it right to force it on people just because of a license choice.
> 

Yes, most filesystems have their own scheme for managing i_ino 
assignment, so this is primarily for "pseudo-filesystems". Stuff like 
pipefs, sockfs, /proc, etc...

>> I'm certainly open to discussion though. Is there a compelling reason to 
>> open this up to proprietary software authors?
> 
> I don't think there is a compelling reason to open it up since the
> functionality could be reimplemented if needed, but I also think
> the only reason it is being marked GPL-only is the very common
> attitude that there should not be any proprietary modules.
> 
> To be honest, I think it looks bad for someone associated with redhat
> to be suggesting that life should be made more difficult for those
> who write proprietary software on Linux. The support from commercial
> software is a major reason for the success of the RHEL product line.
> I can't imagine that this attitude will affect support from software
> companies as long as there is a demand for software on Linux, but
> it isn't exactly supportive.
> 

I have no problem with someone writing, selling and supporting 
proprietary modules. Knock yourself out. I just don't see a reason why I 
should contribute code to such an effort.

Still though, this was coded in part on company time. I certainly don't 
want to go against Red Hat's policy in such a matter, so I'll do some 
due diligence internally as to how this should be done.

In the meantime, does anyone have objections or comments on this 
approach on technical grounds?

Thanks,
Jeff

[RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

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

diff --git a/fs/inode.c b/fs/inode.c
index 26cdb11..52779f4 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -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_hea
 		spin_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;
diff --git a/fs/pipe.c b/fs/pipe.c
index b1626f2..ea50833 100644
--- a/fs/pipe.c
+++ b/fs/pipe.c
@@ -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)
diff --git a/fs/super.c b/fs/super.c
index 47e554c..23b662b 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -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;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 2fe6e3f..2c1a215 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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);

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Al Viro]

On Tue, Nov 14, 2006 at 03:22:08PM -0500, Jeff Layton wrote:
> 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.

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.

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

On Tue, 2006-11-14 at 20:26 +0000, Al Viro wrote:
> 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

diff --git a/fs/inode.c b/fs/inode.c
index 26cdb11..b63b473 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -288,6 +288,8 @@ static void dispose_list(struct list_hea
 		list_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);
diff --git a/fs/pipe.c b/fs/pipe.c
index b1626f2..d74ae65 100644
--- a/fs/pipe.c
+++ b/fs/pipe.c
@@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voi
 	if (!inode)
 		goto fail_inode;
 
+	if (iunique_register(inode, 0))
+		goto fail_iput;
+
 	pipe = alloc_pipe_info(inode);
 	if (!pipe)
 		goto fail_iput;
diff --git a/fs/super.c b/fs/super.c
index 47e554c..23b662b 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -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;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 2fe6e3f..c05bf23 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -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 inode
 extern 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);
diff --git a/lib/idr.c b/lib/idr.c

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

On Wed, 2006-11-15 at 11:42 -0500, Jeff Layton wrote:
> 
> Ok, that sounds reasonable. Here's a respun patch. This adds 2 new
> functions, an idr_register and idr_unregister. 

Doh! That should read iunique_register and iunique_unregister...
-- Jeff

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Al Viro]

On Wed, Nov 15, 2006 at 11:42:38AM -0500, Jeff Layton wrote:
> +{
> +	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...

> @@ -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?

>  	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);

Ditto.

>  	if (inode->i_data.nrpages)
>  		truncate_inode_pages(&inode->i_data, 0);
>  	clear_inode(inode);
> diff --git a/fs/pipe.c b/fs/pipe.c
> index b1626f2..d74ae65 100644
> --- a/fs/pipe.c
> +++ b/fs/pipe.c
> @@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voi
>  	if (!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...

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

On Thu, 2006-11-16 at 14:06 +0000, Al Viro wrote:
> On Wed, Nov 15, 2006 at 11:42:38AM -0500, Jeff Layton wrote:
> > +{
> > +	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...
> 

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?

> > @@ -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.

> 
> >  	if (inode->i_data.nrpages)
> >  		truncate_inode_pages(&inode->i_data, 0);
> >  	clear_inode(inode);
> > diff --git a/fs/pipe.c b/fs/pipe.c
> > index b1626f2..d74ae65 100644
> > --- a/fs/pipe.c
> > +++ b/fs/pipe.c
> > @@ -845,6 +845,9 @@ static struct inode * get_pipe_inode(voi
> >  	if (!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...

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

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Matthew Wilcox]

On Tue, Nov 14, 2006 at 03:22:08PM -0500, Jeff Layton wrote:
> 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.

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?

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jörn Engel]

On Wed, 15 November 2006 10:27:20 -0700, Matthew Wilcox wrote:
> 
> 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.

> 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

-- 
/* 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 majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC][PATCH] ensure i_ino uniqueness in filesystems without permanent inode numbers (via idr)

[Jeff Layton]

On Wed, 2006-11-15 at 18:56 +0100, Jörn Engel wrote:
> 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 majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html