Skip to contentSkip to conversation

fs/inode: iunique() Optimize Performance

PATCH In review Liuweni 5 participants 12 messages Nov 25, 2009 – Dec 2, 2009 VFS

lore
Share & tools
lore

Liuweni

author
#0 lore raw

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

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

---

---

fs/inode.c +3 -2
index 4d8e3be..8ff1e99 100644
@@ -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

#1 lore raw
Quoted 6 lines · 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().

That's not true.

fs/inode.c ino_t iunique(struct super_block *sb, ino_t max_reserved) · line 845

Quoted 11 lines
fs/inode.c +3 -2
@@ -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.

Quoted 13 lines
(quoted diff) +0 -1
 		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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 4 lines
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."
#2 lore raw

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 <[email protected]>:

Quoted 49 lines · Liuweni
Quoted 6 lines

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

fs/inode.c ino_t iunique(struct super_block *sb, ino_t max_reserved) · line 845

Quoted 11 lines
fs/inode.c +3 -2
@@ -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.

Quoted 9 lines
(quoted diff) +0 -1
               head = inode_hashtable + hash(sb, res);
               inode = find_inode_fast(sb, head, res);
 
 
--------------

Best Regards,
Liuweni
2009-11-25

Quoted 4 lines

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

--
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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Signature · 4 lines
Jérémy Cochoy - L1 MI (Lyon1)
Mail : [email protected]
Tel : 06-43-01-74-02
Alias Zenol - http://zenol.fr
#3 lore raw
Quoted 6 lines · 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?

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

Quoted 1 line

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.

Quoted 12 lines

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

Quoted 4 lines

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

Signature · 4 lines
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."
author
#4 lore raw

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

2009/11/26 Matthew Wilcox <[email protected]>:

Quoted 36 lines · J?r?my Cochoy
Quoted 6 lines

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.

Quoted 1 line

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.

Quoted 12 lines

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

Quoted 4 lines

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.

Quoted 8 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#5 lore raw
Quoted 1 line · liu weni

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?

Signature · 4 lines
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."
author
#6 lore raw

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

Quoted 1 line · liu weni

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?

Signature · 4 lines
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."
#7 lore raw
Quoted 10 lines · 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.

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?

Signature · 4 lines
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."
#8 lore raw
Quoted 11 lines · Matthew Wilcox
Quoted 4 lines · Liuweni

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

Quoted 4 lines

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.

author
#9 lore raw
In reply to 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().

Quoted 2 lines

+ 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

Quoted 6 lines · 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().

That's not true.

fs/inode.c ino_t iunique(struct super_block *sb, ino_t max_reserved) · line 845

Quoted 11 lines
fs/inode.c +3 -2
@@ -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.

Quoted 13 lines
(quoted diff) +0 -1
  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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 5 lines
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."
�翳簕.n�+壏煯壄�+%娝�遍荻w�簕.n�+壏{炳G珴�妠ay�蕠跈�,jf"穐殢飦�戧鐉_璁(殠娸"濟�m���G珴�⒏?櫒璀�&x忈秈O曟瑉窔v豝�m����鹅�⒏?朓�
#10 lore raw
Quoted 7 lines · 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().

Quoted 2 lines

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

Quoted 57 lines

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

Quoted 6 lines · 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().

That's not true.

fs/inode.c ino_t iunique(struct super_block *sb, ino_t max_reserved) · line 845

Quoted 11 lines
fs/inode.c +3 -2
@@ -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.

Quoted 13 lines
(quoted diff) +0 -1
  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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 4 lines
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."
Signature · 4 lines
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."
#11 lore raw
In reply to Liuweni
Quoted 6 lines · 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().

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

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.