[PATCH 1/3]fs/inode: iunique() Optimize Performance

[PATCH 1/3]fs/inode: iunique() Optimize Performance

[Liuweni]

---
move the if condition out the while{}.
While the function executing, the if 
condition won't check again and again.
And this code won't change the function
of iunique().

---
Signed-off-by: Liuwenyi<qingshenlwy@gmail.com>
Cc: Alexander Viro <viro@zeniv.linux.org.uk>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Jan Kara <jack@suse.cz>
Cc: Nick Piggin <npiggin@suse.de>
Cc: linux-fsdevel@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
---
diff --git a/fs/inode.c b/fs/inode.c
index 4d8e3be..8ff1e99 100644
--- a/fs/inode.c
+++ b/fs/inode.c
@@ -838,9 +838,10 @@ ino_t iunique(struct super_block *sb, ino_t max_reserved)
 	ino_t res;
 
 	spin_lock(&inode_lock);
+
+	if (counter <= max_reserved)
+		counter = max_reserved + 1;
 	do {
-		if (counter <= max_reserved)
-			counter = max_reserved + 1;
 		res = counter++;
 		head = inode_hashtable + hash(sb, res);
 		inode = find_inode_fast(sb, head, res);

 				
--------------
Best Regards,
Liuweni
2009-11-25

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Matthew Wilcox]

On Wed, Nov 25, 2009 at 10:09:45PM +0800, Liuweni wrote:
> ---
> move the if condition out the while{}.
> While the function executing, the if 
> condition won't check again and again.
> And this code won't change the function
> of iunique().

That's not true.

> @@ -838,9 +838,10 @@ ino_t iunique(struct super_block *sb, ino_t max_reserved)
>  	ino_t res;
>  
>  	spin_lock(&inode_lock);
> +
> +	if (counter <= max_reserved)
> +		counter = max_reserved + 1;
>  	do {
> -		if (counter <= max_reserved)
> -			counter = max_reserved + 1;
>  		res = counter++;

'counter' is incremented here, so if it wraps around, we'll blunder into 
the reserved space again.

>  		head = inode_hashtable + hash(sb, res);
>  		inode = find_inode_fast(sb, head, res);
> 
>  				
> --------------
> Best Regards,
> Liuweni
> 2009-11-25
> 
> --
> 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

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Jérémy Cochoy]

Hello,

There is something strange in iunique : what will happend if all inode
between max_reserved+1 and (unsinged in)(0-1) ? Will it make an
infinite loop or an interruption can happen and make an inode become
free?

In that case, it will be better to stop search when counter overflow, no?

Will it not be better to use a field max_ino_used (in superblock, for
exemple) where we store the last inode allocated with iunique and make
a search only if max_ino_used become to (unsigned)(-1) ?

But, if iunique is here to provide a solution in order to generate
unused inode in filesystem which have various inode number, it's
better to use a list of used ino, in a short hash table which use the
first 8 bits of the inode, always use the same function to create a
new inode and look at the head if we can add a new inode with bigger
ino and still in the range. (But i think filesystems developper prefer
to write ther own functions in order to do that, no?)

Well, if we want to stop in case of full inode filesystem, we can put
the first condition in the head and add change return as :
return inode->i_ino > max_reserved ? res : 0; // 0 might "i can't find
an inode after max_reserved"

2009/11/25 Matthew Wilcox <matthew@wil.cx>:
> On Wed, Nov 25, 2009 at 10:09:45PM +0800, Liuweni wrote:
>> ---
>> move the if condition out the while{}.
>> While the function executing, the if
>> condition won't check again and again.
>> And this code won't change the function
>> of iunique().
>
> That's not true.
>
>> @@ -838,9 +838,10 @@ ino_t iunique(struct super_block *sb, ino_t max_reserved)
>>       ino_t res;
>>
>>       spin_lock(&inode_lock);
>> +
>> +     if (counter <= max_reserved)
>> +             counter = max_reserved + 1;
>>       do {
>> -             if (counter <= max_reserved)
>> -                     counter = max_reserved + 1;
>>               res = counter++;
>
> 'counter' is incremented here, so if it wraps around, we'll blunder into
> the reserved space again.
>
>>               head = inode_hashtable + hash(sb, res);
>>               inode = find_inode_fast(sb, head, res);
>>
>>
>> --------------
>> Best Regards,
>> Liuweni
>> 2009-11-25
>>
>> --
>> 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
>
> --
> Matthew Wilcox                          Intel Open Source Technology Centre
> "Bill, look, we understand that you're interested in selling us this
> operating system, but compare it to ours.  We can't possibly take such
> a retrograde step."
> --
> 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
>



-- 
Jérémy Cochoy - L1 MI (Lyon1)
Mail : jeremy.cochoy@gmail.com
Tel : 06-43-01-74-02
Alias Zenol - http://zenol.fr

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Matthew Wilcox]

On Wed, Nov 25, 2009 at 08:20:02PM +0100, J?r?my Cochoy wrote:
> Hello,
> 
> There is something strange in iunique : what will happend if all inode
> between max_reserved+1 and (unsinged in)(0-1) ? Will it make an
> infinite loop or an interruption can happen and make an inode become
> free?

Another process can free an inode while this loop is executing.

> In that case, it will be better to stop search when counter overflow, no?

If you have all four billion inodes allocated, you have significantly
bigger problems than this loop.  For a start, at 600 bytes per inode,
I'd like to see your machine with 2.4TB of memory.  Then there's the
size of your inode hash, and the depth of the chains within it.

> Will it not be better to use a field max_ino_used (in superblock, for
> exemple) where we store the last inode allocated with iunique and make
> a search only if max_ino_used become to (unsigned)(-1) ?
> 
> But, if iunique is here to provide a solution in order to generate
> unused inode in filesystem which have various inode number, it's
> better to use a list of used ino, in a short hash table which use the
> first 8 bits of the inode, always use the same function to create a
> new inode and look at the head if we can add a new inode with bigger
> ino and still in the range. (But i think filesystems developper prefer
> to write ther own functions in order to do that, no?)
> 
> Well, if we want to stop in case of full inode filesystem, we can put
> the first condition in the head and add change return as :
> return inode->i_ino > max_reserved ? res : 0; // 0 might "i can't find
> an inode after max_reserved"

Gloves.

http://thedailywtf.com/Articles/The_Complicator_0x27_s_Gloves.aspx

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[liu weni]

Thanks, I will try others way to improve the performance.


2009/11/26 Matthew Wilcox <matthew@wil.cx>:
> On Wed, Nov 25, 2009 at 08:20:02PM +0100, J?r?my Cochoy wrote:
>> Hello,
>>
>> There is something strange in iunique : what will happend if all inode
>> between max_reserved+1 and (unsinged in)(0-1) ? Will it make an
>> infinite loop or an interruption can happen and make an inode become
>> free?
>
> Another process can free an inode while this loop is executing.
>
>> In that case, it will be better to stop search when counter overflow, no?
>
> If you have all four billion inodes allocated, you have significantly
> bigger problems than this loop.  For a start, at 600 bytes per inode,
> I'd like to see your machine with 2.4TB of memory.  Then there's the
> size of your inode hash, and the depth of the chains within it.
>
>> Will it not be better to use a field max_ino_used (in superblock, for
>> exemple) where we store the last inode allocated with iunique and make
>> a search only if max_ino_used become to (unsigned)(-1) ?
>>
>> But, if iunique is here to provide a solution in order to generate
>> unused inode in filesystem which have various inode number, it's
>> better to use a list of used ino, in a short hash table which use the
>> first 8 bits of the inode, always use the same function to create a
>> new inode and look at the head if we can add a new inode with bigger
>> ino and still in the range. (But i think filesystems developper prefer
>> to write ther own functions in order to do that, no?)
>>
>> Well, if we want to stop in case of full inode filesystem, we can put
>> the first condition in the head and add change return as :
>> return inode->i_ino > max_reserved ? res : 0; // 0 might "i can't find
>> an inode after max_reserved"
>
> Gloves.
>
> http://thedailywtf.com/Articles/The_Complicator_0x27_s_Gloves.aspx
>
> --
> Matthew Wilcox                          Intel Open Source Technology Centre
> "Bill, look, we understand that you're interested in selling us this
> operating system, but compare it to ours.  We can't possibly take such
> a retrograde step."
>
--
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: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Matthew Wilcox]

On Tue, Dec 01, 2009 at 01:01:57PM +0800, liu weni wrote:
> Thanks, I will try others way to improve the performance.

Is there a performance problem with iunique?  What benchmark are you
running to show this?

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Liuweni]

Hi Matthew Wilcox:
	I got the code note as the following. if there is no performance problem, 
maybe the code note need update.


------
 *	BUGS:
 *	With a large number of inodes live on the file system this function
 *	currently becomes quite slow.


------------------		
Best Regards,		 
Liuweni
2009-12-01

-------------------------------------------------------------
发件人：Matthew Wilcox
发送日期：2009-12-01 20:03:41
收件人：liu weni
抄送：strongzgy; xgr178; Liu Hui; viro; akpm; jack; npiggin; linux-fsdevel; linux-kernel
主题：Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

On Tue, Dec 01, 2009 at 01:01:57PM +0800, liu weni wrote:
> Thanks, I will try others way to improve the performance.

Is there a performance problem with iunique?  What benchmark are you
running to show this?

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Matthew Wilcox]

On Tue, Dec 01, 2009 at 09:21:32PM +0800, Liuweni wrote:
> Hi Matthew Wilcox:
> 	I got the code note as the following. if there is no performance problem, 
> maybe the code note need update.
> 
> 
> ------
>  *	BUGS:
>  *	With a large number of inodes live on the file system this function
>  *	currently becomes quite slow.
> 

I don't believe that comment is correct.  In any case, your optimisation
wouldn't make a lick of difference to the speed; it's a single comparison
in a loop which also calculates a hash, makes a function call, and walks
the length of a hash chain.

The old adage about debugging code, not comments applies here.  Don't take
somebody else's word for it that there's a performance problem here.
Devise a test to demonstrate the performance problem.  Otherwise, how
will you know if you solved it?

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Nick Piggin]

On Tue, Dec 01, 2009 at 07:00:41AM -0700, Matthew Wilcox wrote:
> On Tue, Dec 01, 2009 at 09:21:32PM +0800, Liuweni wrote:
> >  *	BUGS:
> >  *	With a large number of inodes live on the file system this function
> >  *	currently becomes quite slow.
> > 
> 
> I don't believe that comment is correct.  In any case, your optimisation
> wouldn't make a lick of difference to the speed; it's a single comparison
> in a loop which also calculates a hash, makes a function call, and walks
> the length of a hash chain.
> 
> The old adage about debugging code, not comments applies here.  Don't take
> somebody else's word for it that there's a performance problem here.
> Devise a test to demonstrate the performance problem.  Otherwise, how
> will you know if you solved it?

Yeah I agree. And then we can debate the usefulness of that workload.

iunique is not used in many filesystems.  If performance really becomes a
problem, then you most likely need another data structure. A per-sb ida or
something would come to mind, but I expect any filesystem that cares already
has a decent inode number allocation so iunique is just a simple hack for
those that don't care so much.

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Liuweni]

Hi  Matthew Wilcox ,
    The code means set counter's value to the max max_reserved and counter.
Then, the if condition will choose a large one, and in the function, the counter
is increased. so this code won't change the function of iunique().

> + if (counter <= max_reserved)
> + counter = max_reserved + 1;


-----------
Best Regards,
Liuweni 
2009-11-25 







发件人： Matthew Wilcox 
发送时间： 2009-11-25  22:15:09 
收件人： Liuweni 
抄送： linux-kernel; strongzgy; xgr178; Liu Hui; viro; akpm; jack; npiggin; linux-fsdevel 
主题： Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance 
 
On Wed, Nov 25, 2009 at 10:09:45PM +0800, Liuweni wrote:
> ---
> move the if condition out the while{}.
> While the function executing, the if 
> condition won't check again and again.
> And this code won't change the function
> of iunique().
That's not true.
> @@ -838,9 +838,10 @@ ino_t iunique(struct super_block *sb, ino_t max_reserved)
>   ino_t res;
>  
>   spin_lock(&inode_lock);
> +
> + if (counter <= max_reserved)
> + counter = max_reserved + 1;
>   do {
> - if (counter <= max_reserved)
> - counter = max_reserved + 1;
>   res = counter++;
'counter' is incremented here, so if it wraps around, we'll blunder into 
the reserved space again.
>   head = inode_hashtable + hash(sb, res);
>   inode = find_inode_fast(sb, head, res);
> 
>   
> --------------
> Best Regards,
> Liuweni
> 2009-11-25
> 
> --
> 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
-- 
Matthew Wilcox Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Matthew Wilcox]

On Wed, Nov 25, 2009 at 10:51:33PM +0800, Liuweni wrote:
> Hi  Matthew Wilcox ,
>     The code means set counter's value to the max max_reserved and counter.
> Then, the if condition will choose a large one, and in the function, the counter
> is increased. so this code won't change the function of iunique().
> 
> > + if (counter <= max_reserved)
> > + counter = max_reserved + 1;

If 'counter' has the value 0xffffffff, and the loop increments 'counter'
to zero, this check needs to be inside the loop.

> 
> -----------
> Best Regards,
> Liuweni 
> 2009-11-25 
> 
> 
> 
> 
> 
> 
> 
> ???????? Matthew Wilcox 
> ?????????? 2009-11-25  22:15:09 
> ???????? Liuweni 
> ?????? linux-kernel; strongzgy; xgr178; Liu Hui; viro; akpm; jack; npiggin; linux-fsdevel 
> ?????? Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance 
>  
> On Wed, Nov 25, 2009 at 10:09:45PM +0800, Liuweni wrote:
> > ---
> > move the if condition out the while{}.
> > While the function executing, the if 
> > condition won't check again and again.
> > And this code won't change the function
> > of iunique().
> That's not true.
> > @@ -838,9 +838,10 @@ ino_t iunique(struct super_block *sb, ino_t max_reserved)
> >   ino_t res;
> >  
> >   spin_lock(&inode_lock);
> > +
> > + if (counter <= max_reserved)
> > + counter = max_reserved + 1;
> >   do {
> > - if (counter <= max_reserved)
> > - counter = max_reserved + 1;
> >   res = counter++;
> 'counter' is incremented here, so if it wraps around, we'll blunder into 
> the reserved space again.
> >   head = inode_hashtable + hash(sb, res);
> >   inode = find_inode_fast(sb, head, res);
> > 
> >   
> > --------------
> > Best Regards,
> > Liuweni
> > 2009-11-25
> > 
> > --
> > 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
> -- 
> Matthew Wilcox Intel Open Source Technology Centre
> "Bill, look, we understand that you're interested in selling us this
> operating system, but compare it to ours.  We can't possibly take such
> a retrograde step."

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 1/3]fs/inode: iunique() Optimize Performance

[Andi Kleen]

"Liuweni" <qingshenlwy@gmail.com> writes:

> ---
> move the if condition out the while{}.
> While the function executing, the if 
> condition won't check again and again.
> And this code won't change the function
> of iunique().

Normally compiler automatically move loop invariant code out of loop
bodies. Have you verified that's not the case here?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.