Skip to contentSkip to conversation

NFS: Improving the access cache

RFC PATCH In review Steve Dickson 7 participants 31 messages Apr 26, 2006 – May 8, 2006

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 NFS: Improving the access cache

Currently the NFS client caches ACCESS information on a per uid basis which fall apart when different process with different uid consistently access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entries of struct list_head giving it a total size of 2k.

The patch is based on Trond's GIT tree...

Comments?

steved.

This patch improves the caching of ACCESS information by storing the information in hash table. The patch will greatly decrease the number of ACCESS calls with processes with different uids access the same directory.

----------------------------------------------------

fs/nfs/inode.c renamed from fs/nfs/inode.c.acc +6 -5
@@ -74,6 +74,9 @@ static void nfs_zap_acl_cache(struct ino
 
 static struct rpc_program	nfs_program;
 
+extern void nfs_zap_access_cache(struct inode *);
+extern void nfs_init_access_cache(void);
+
 static struct super_operations nfs_sops = { 
 	.alloc_inode	= nfs_alloc_inode,
 	.destroy_inode	= nfs_destroy_inode,
@@ -170,14 +173,11 @@ static void
 nfs_clear_inode(struct inode *inode)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
-	struct rpc_cred *cred;
 
 	nfs_wb_all(inode);
 	BUG_ON (!list_empty(&nfsi->open_files));
 	nfs_zap_acl_cache(inode);
-	cred = nfsi->cache_access.cred;
-	if (cred)
-		put_rpccred(cred);
+	nfs_zap_access_cache(inode);
 	BUG_ON(atomic_read(&nfsi->data_updates) != 0);
 }
 
@@ -940,7 +940,6 @@ nfs_fhget(struct super_block *sb, struct
 		nfsi->attrtimeo = NFS_MINATTRTIMEO(inode);
 		nfsi->attrtimeo_timestamp = jiffies;
 		memset(nfsi->cookieverf, 0, sizeof(nfsi->cookieverf));
-		nfsi->cache_access.cred = NULL;
 
 		unlock_new_inode(inode);
 	} else
@@ -2892,6 +2891,8 @@ static int __init init_nfs_fs(void)
 {
 	int err;
 
+	nfs_init_access_cache();
+
 	err = nfs_init_nfspagecache();
 	if (err)
 		goto out4;
fs/nfs/dir.c renamed from fs/nfs/dir.c.acc +92 -16

134 lines not on this page · raw message

include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.acc +2 -1
@@ -72,6 +72,8 @@ struct nfs_access_entry {
 	unsigned long		jiffies;
 	struct rpc_cred *	cred;
 	int			mask;
+	void   *id;
+	struct list_head acc_list;
 };
 
 struct nfs4_state;
@@ -145,7 +147,6 @@ struct nfs_inode {
 	 */
 	atomic_t		data_updates;
 
-	struct nfs_access_entry	cache_access;
 #ifdef CONFIG_NFS_V3_ACL
 	struct posix_acl	*acl_access;
 	struct posix_acl	*acl_default;
#1 lore raw
Quoted 7 lines · Steve Dickson

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entries of struct list_head giving it a total size of 2k.

Seems to me like you could use an hlist instead, saving you 1k.

#2 lore raw
In reply to Steve Dickson
Quoted 13 lines · On Tuesday April 25, [email protected] wrote:

Currently the NFS client caches ACCESS information on a per uid basis which fall apart when different process with different uid consistently access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entries of struct list_head giving it a total size of 2k.

Quoted 3 lines

The patch is based on Trond's GIT tree...

Comments?

- There is no upper bound imposed on the size of the cache, and no way for memory pressure to shrink the cache except indirectly by discarding inodes.
I cannot see this being exploitable as getting access to lots of credentials would be hard for any given user. However I feel that some cleaning might be in order.
- The nfs_zap_access_cache call isn't cheap. If that could be amortised somehow it would be good. Maybe use some version tagging so that when an inode is reused the access entry will no longer match in some way. Then just clean the table by periodic scans that discard based on timeout information ?

It occurs to me that the large majority of inodes will only be accessed by a single user and so need not reside in the cache.

So how about having a single "struct nfs_access_entry" pointer in the inode.
When we do a lookup we look there first.
When we want to add an entry, we try to add it there first. When we end up with two current access entries for the same inode, only then do we insert them into the hash.
We would need to be able to tell from the inode whether anything is hashed or not. This could simply be if the nfs_access_entry point is non-null, and its hashlist it non-empty. Or we could just use a bit flag somewhere.

I suspect this would keep the cache much smaller, and some of my other concerns might then become irrelevant.

NeilBrown

#22 lore raw
In reply to Steve Dickson
Quoted 2 lines · Steve Dickson

Currently the NFS client caches ACCESS information on a per uid basis which fall apart when different process with different uid consistent=

ly

Quoted 9 lines

access the same directory. The end result being a storm of needless ACCESS calls...
=20
The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entr=

ies

Quoted 1 line

of struct list_head giving it a total size of 2k.

Instead of having the field 'id', why don't you let the nfs_inode keep = a
small (hashed?) list of all the nfs_access_entry objects that refer to it? That would speed up searches for cached entries.

I agree with Neil's assessment that we need a bound on the size of the cache. In fact, enforcing a bound is pretty much the raison d'=C3=AAtre=
for a
global table (by which I mean that if we don't need a bound, then we might as well cache everything in the nfs_inode).
How about rather changing that hash table into an LRU list, then adding a shrinker callback (using set_shrinker()) to allow the VM to free up entries when memory pressure dictates that it must?

Cheers,
Trond

-
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

#23 lore raw
Quoted 5 lines · Trond Myklebust

On Tue, 2006-04-25 at 21:14 -0400, Steve Dickson wrote:
=20

Quoted 2 lines

Currently the NFS client caches ACCESS information on a per uid basis which fall apart when different process with different uid consistent=

ly

Quoted 9 lines
Quoted 9 lines

access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entr=

ies

Quoted 5 lines
Quoted 3 lines

of struct list_head giving it a total size of 2k.
=20

Instead of having the field 'id', why don't you let the nfs_inode keep=

a

Quoted 5 lines

small (hashed?) list of all the nfs_access_entry objects that refer to it? That would speed up searches for cached entries.

I agree with Neil's assessment that we need a bound on the size of the cache. In fact, enforcing a bound is pretty much the raison d'=EAtre f=

or a

Quoted 3 lines

global table (by which I mean that if we don't need a bound, then we might as well cache everything in the nfs_inode).
How about rather changing that hash table into an LRU list, then addin=

g

Quoted 3 lines

a shrinker callback (using set_shrinker()) to allow the VM to free up entries when memory pressure dictates that it must?

Previous implementations have shown that a single per inode linear=20 linked list
ends up not being scalable enough in certain situations. There would e= nd up
being too many entries in the list and searching the list would become a bottleneck. Adding a set of hash buckets per inode also proved to be inefficient because in order to have enough hash buckets to make the ha= shing
efficient, much space was wasted. Having a single set of hash buckets, adequately sized, ended up being the best solution.

Why have a limit? A better solution is to have the cache grow dynamica= lly
as need requires and then have the system reclaim the memory when it st= arts
to run low on memory.

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

#29 lore raw
In reply to Steve Dickson
Quoted 13 lines · Steve Dickson

Currently the NFS client caches ACCESS information on a per uid basis which fall apart when different process with different uid consistently access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 entries of struct list_head giving it a total size of 2k.

Quoted 5 lines

The patch is based on Trond's GIT tree...

Comments?

steved.

Hi Steve-

Thanks for digging into this.

I can't tell, but have you addressed the problem of racing processes generating multiple similar ACCESS requests? Seems like some kind of serialization through your caching mechanism would resolve that nicely.

Signature · 2 lines
corporate:	<cel at netapp dot com>
personal:	<chucklever at bigfoot dot com>
#24 lore raw
In reply to Peter Staubach
Quoted 6 lines · Peter Staubach

Trond Myklebust wrote:
=20

Quoted 4 lines · Steve Dickson

=20

Quoted 1 line

Currently the NFS client caches ACCESS information on a per uid bas=

is

Quoted 1 line
Quoted 1 line
Quoted 1 line

which fall apart when different process with different uid consiste=

ntly

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 en=

tries

Quoted 5 lines
Quoted 5 lines
Quoted 3 lines

of struct list_head giving it a total size of 2k.
=20

Instead of having the field 'id', why don't you let the nfs_inode ke=

ep a

Quoted 1 line
Quoted 1 line

small (hashed?) list of all the nfs_access_entry objects that refer =

to

Quoted 3 lines
Quoted 3 lines

it? That would speed up searches for cached entries.

I agree with Neil's assessment that we need a bound on the size of t=

he

Quoted 1 line
Quoted 1 line

cache. In fact, enforcing a bound is pretty much the raison d'=C3=AA=

tre for a

Quoted 3 lines
Quoted 3 lines

global table (by which I mean that if we don't need a bound, then we might as well cache everything in the nfs_inode).
How about rather changing that hash table into an LRU list, then add=

ing

Quoted 1 line
Quoted 1 line

a shrinker callback (using set_shrinker()) to allow the VM to free u=

p

Quoted 6 lines
Quoted 2 lines

entries when memory pressure dictates that it must?

=20
Previous implementations have shown that a single per inode linear=20 linked list
ends up not being scalable enough in certain situations. There would=

end up

Quoted 1 line

being too many entries in the list and searching the list would becom=

e

Quoted 1 line

a bottleneck. Adding a set of hash buckets per inode also proved to =

be

Quoted 1 line

inefficient because in order to have enough hash buckets to make the =

hashing

Quoted 1 line

efficient, much space was wasted. Having a single set of hash bucket=

s,

Quoted 1 line

adequately sized, ended up being the best solution.

What situations? AFAIA the number of processes in a typical setup are almost always far smaller than the number of cached inodes.

=46or instance on my laptop, I'm currently running 146 processes, but according to /proc/slabinfo I'm caching 330000 XFS inodes + 141500 ext3 inodes.
If I were to assume that a typical nfsroot system will show roughly the same behaviour, then it would mean that a typical bucket in Steve's 256 hash entry table will contain at least 2000 entries that I need to search through every time I want to do an access call.

Quoted 1 line

Why have a limit? A better solution is to have the cache grow dynami=

cally

Quoted 1 line

as need requires and then have the system reclaim the memory when it =

starts

Quoted 1 line

to run low on memory.

See my previous mail: that is exactly what I suggested in the 3rd paragraph.

Cheers,
Trond

-
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

#25 lore raw
Quoted 13 lines · Trond Myklebust

On Wed, 2006-04-26 at 09:14 -0400, Peter Staubach wrote:
=20

Quoted 10 lines

Trond Myklebust wrote:

=20

Quoted 6 lines · Steve Dickson

=20

    =20
Quoted 1 line

Currently the NFS client caches ACCESS information on a per uid bas=

is

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

which fall apart when different process with different uid consiste=

ntly

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

access the same directory. The end result being a storm of needless ACCESS calls...

The attached patch used a hash table to store the nfs_access_entry entires which cause the ACCESS request to only happen when the attributes timeout.. The table is indexed by the addition of the nfs_inode pointer and the cr_uid in the cred structure which should spread things out nicely for some decent scalability (although the locking scheme may need to be reworked a bit). The table has 256 en=

tries

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

of struct list_head giving it a total size of 2k.
=20

      =20

Instead of having the field 'id', why don't you let the nfs_inode ke=

ep a

Quoted 1 line
Quoted 1 line
Quoted 1 line

small (hashed?) list of all the nfs_access_entry objects that refer =

to

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

it? That would speed up searches for cached entries.

I agree with Neil's assessment that we need a bound on the size of t=

he

Quoted 1 line
Quoted 1 line
Quoted 1 line

cache. In fact, enforcing a bound is pretty much the raison d'=EAtre=

for a

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

global table (by which I mean that if we don't need a bound, then we might as well cache everything in the nfs_inode).
How about rather changing that hash table into an LRU list, then add=

ing

Quoted 1 line
Quoted 1 line
Quoted 1 line

a shrinker callback (using set_shrinker()) to allow the VM to free u=

p

Quoted 7 lines
Quoted 7 lines
Quoted 4 lines

entries when memory pressure dictates that it must?

    =20

Previous implementations have shown that a single per inode linear=20 linked list
ends up not being scalable enough in certain situations. There would=

end up

Quoted 1 line
Quoted 1 line

being too many entries in the list and searching the list would becom=

e

Quoted 1 line
Quoted 1 line

a bottleneck. Adding a set of hash buckets per inode also proved to =

be

Quoted 1 line
Quoted 1 line

inefficient because in order to have enough hash buckets to make the =

hashing

Quoted 1 line
Quoted 1 line

efficient, much space was wasted. Having a single set of hash bucket=

s,

Quoted 9 lines
Quoted 3 lines

adequately sized, ended up being the best solution.
=20

What situations? AFAIA the number of processes in a typical setup are almost always far smaller than the number of cached inodes.

=20

The situation that doesn't scale is one where there are many different users on the system. It is the situation where there are more then jus= t
a few users per file. This can happen on compute servers or systems used for timesharing sorts of purposes.

Quoted 2 lines

For instance on my laptop, I'm currently running 146 processes, but according to /proc/slabinfo I'm caching 330000 XFS inodes + 141500 ext=

3

Quoted 2 lines

inodes.
If I were to assume that a typical nfsroot system will show roughly th=

e

Quoted 1 line

same behaviour, then it would mean that a typical bucket in Steve's 25=

6

Quoted 3 lines

hash entry table will contain at least 2000 entries that I need to search through every time I want to do an access call.

=46or such a system, there needs to be more than 256 hash buckets. The= number
of the access cache hash buckets needs to be on scale with the number o= f=20
hash
buckets used for similarly sized caches and tables.

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

#30 lore raw
In reply to Chuck Lever
Quoted 6 lines · Chuck Lever

Hi Steve-

Thanks for digging into this.

I can't tell, but have you addressed the problem of racing processes generating multiple similar ACCESS requests? Seems like some kind of serialization through your caching mechanism would resolve that nicely.

No.. I was just trying to duplicate logic that was there... but that is a good point... It turns out that I messed up the locking anyways... the NFS_INO_INVALID_ACCESS bit is no longer being protect by the inode->i_lock which is not good... so I need to rework that part...

steved.

#3 lore raw
In reply to Neil Brown
Quoted 6 lines · Neil Brown

- There is no upper bound imposed on the size of the cache, and no way for memory pressure to shrink the cache except indirectly by discarding inodes.
I cannot see this being exploitable as getting access to lots of credentials would be hard for any given user. However I feel that some cleaning might be in order.

I guess there is no upper bound checking because I didn't see any type of boundary checking the server hashing code I stoled 8-) Or maybe I just missed it... Is there an example and what would trigger this cleanup?

Quoted 5 lines

- The nfs_zap_access_cache call isn't cheap. If that could be amortised somehow it would be good. Maybe use some version tagging so that when an inode is reused the access entry will no longer match in some way. Then just clean the table by periodic scans that discard based on timeout information ?

yes.. I did realize that ifs_zap_access_cache would be expensive... and I think there might be an issue with holding the access_hash lock spin lock while calling put_rpccred() since it can also take out another spin lock... Maybe I just spin through the table marking entries for deletion and then let somebody else clean them up?? Is there already a clean up process that I would us? I don't recall one...

Quoted 10 lines

It occurs to me that the large majority of inodes will only be accessed by a single user and so need not reside in the cache.

So how about having a single "struct nfs_access_entry" pointer in the inode.
When we do a lookup we look there first.
When we want to add an entry, we try to add it there first. When we end up with two current access entries for the same inode, only then do we insert them into the hash.

To rephrase to make sure I understand....
1) P1(uid=1) creates an access pointer in the nfs_inode
2) P2(uid=2) sees the access pointer is not null so it adds them both to the table, right?

Quoted 4 lines

We would need to be able to tell from the inode whether anything is hashed or not. This could simply be if the nfs_access_entry point is non-null, and its hashlist it non-empty. Or we could just use a bit flag somewhere.

So I guess it would be something like:
if (nfs_inode->access == null)

    set nfs_inode->access

if (nfs_inode->access =! NULL && nfs_inode->access_hash == empty)
move both pointer into hast able.
if (nfs_inode->access == null && nfs_inode->access_hash != empty)
use hastable.

But now the question is how would I know when there is only one entry in the table? Or do we just let the hash table "drain" naturally and when it become empty we start with the nfs_inode->access pointer again... Is this close to what your thinking??

steved.

#28 lore raw
In reply to Trond Myklebust
Quoted 3 lines · Trond Myklebust

=20
=20
Instead of having the field 'id', why don't you let the nfs_inode kee=

p a

Quoted 1 line

small (hashed?) list of all the nfs_access_entry objects that refer t=

o

Quoted 1 line

it? That would speed up searches for cached entries.

Actually I did look into having a pointer in the nfs_inode... but what do you do when the second hashed list is needed. Meaning P2(uid2) comes along and hashes to a different que. I guess I thought it was a bit messy to keep overwriting the point in the nfs_inode so I just kept everything in the hash table...

Quoted 1 line

I agree with Neil's assessment that we need a bound on the size of th=

e

Quoted 1 line

cache. In fact, enforcing a bound is pretty much the raison d'=C3=AAt=

re for a

Quoted 2 lines

global table (by which I mean that if we don't need a bound, then we might as well cache everything in the nfs_inode).

Ok..

Quoted 1 line

How about rather changing that hash table into an LRU list, then addi=

ng

Quoted 2 lines

a shrinker callback (using set_shrinker()) to allow the VM to free up entries when memory pressure dictates that it must?

Sounds interesting.. Just to be clear, by LRU list you mean use hlist correct?

steved.

-
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

#26 lore raw
In reply to Peter Staubach
Quoted 11 lines · Peter Staubach
Quoted 6 lines

What situations? AFAIA the number of processes in a typical setup are almost always far smaller than the number of cached inodes.

The situation that doesn't scale is one where there are many different users on the system. It is the situation where there are more then just a few users per file. This can happen on compute servers or systems used for timesharing sorts of purposes.

Yes, but the number of users <= number of processes which even on those systems is almost always much, much less than the number of cached inodes.

Quoted 9 lines
Quoted 8 lines

For instance on my laptop, I'm currently running 146 processes, but according to /proc/slabinfo I'm caching 330000 XFS inodes + 141500 ext3 inodes.
If I were to assume that a typical nfsroot system will show roughly the same behaviour, then it would mean that a typical bucket in Steve's 256 hash entry table will contain at least 2000 entries that I need to search through every time I want to do an access call.

Quoted 4 lines

For such a system, there needs to be more than 256 hash buckets. The number of the access cache hash buckets needs to be on scale with the number of hash
buckets used for similarly sized caches and tables.

The inode cache is the only similarly sized cache I can think of.

That is set either by the user, or it takes a default value of (total memory size) / 2^14 buckets (see alloc_large_system_hash). On a 1Gb system, that makes the default hash table size ~ 65536 entries. I can't see people wanting to put up with a 256K static hash table for access caching too.

Furthermore, note that the inode cache is only searched when initialising a dentry. It is not searched on _every_ traversal of a path element.

Cheers,
Trond

#27 lore raw
Quoted 17 lines · Trond Myklebust
Quoted 7 lines · Peter Staubach
Quoted 7 lines

What situations? AFAIA the number of processes in a typical setup are almost always far smaller than the number of cached inodes.

Quoted 6 lines

The situation that doesn't scale is one where there are many different users on the system. It is the situation where there are more then just a few users per file. This can happen on compute servers or systems used for timesharing sorts of purposes.

Quoted 6 lines

Yes, but the number of users <= number of processes which even on those systems is almost always much, much less than the number of cached inodes.

There isn't a 1-to-1 correspondence between processes and files. A single process accesses many different files and many of the processes will be accessing the same files. Shared libraries are easy examples of files which are accessed by multiple processes and processes themselves access multiple shared libraries.

Quoted 16 lines
Quoted 10 lines
Quoted 10 lines

For instance on my laptop, I'm currently running 146 processes, but according to /proc/slabinfo I'm caching 330000 XFS inodes + 141500 ext3 inodes.
If I were to assume that a typical nfsroot system will show roughly the same behaviour, then it would mean that a typical bucket in Steve's 256 hash entry table will contain at least 2000 entries that I need to search through every time I want to do an access call.

Quoted 5 lines

For such a system, there needs to be more than 256 hash buckets. The number of the access cache hash buckets needs to be on scale with the number of hash buckets used for similarly sized caches and tables.

Quoted 10 lines

The inode cache is the only similarly sized cache I can think of.

That is set either by the user, or it takes a default value of (total memory size) / 2^14 buckets (see alloc_large_system_hash). On a 1Gb system, that makes the default hash table size ~ 65536 entries. I can't see people wanting to put up with a 256K static hash table for access caching too.

I think that if the performance benefits warrant such a cache, then it is worth it. It is a very small percentage of the real memory on the system.

Previous, informal, studies showed that caching access privileges like this was good at short circuiting 90%+ of access calls.

However, we could always divide this further when sizing the access cache. If we assume that 1/2 or 1/4 or some percentage of the files accessed will be on NFS mounted file systems, then the access cache just needs to be based on the number of NFS inodes, not the total number of inodes.

Quoted 4 lines

Furthermore, note that the inode cache is only searched when initialising a dentry. It is not searched on _every_ traversal of a path element.

Very true, which points out the importance of getting the access to the access cache correct and fast. The number of entries in the access cache will be at least the number of NFS inodes in the system and could be much higher depending upon whether the system is single-user, desktop style system, or a multi-user shared system. The key to making this cache cheap is to make the hash algorithm cheap and keeping the hash chains short.

ps

#4 lore raw
In reply to Steve Dickson
Quoted 9 lines · On Wednesday April 26, [email protected] wrote:
Quoted 6 lines · Neil Brown

- There is no upper bound imposed on the size of the cache, and no way for memory pressure to shrink the cache except indirectly by discarding inodes.
I cannot see this being exploitable as getting access to lots of credentials would be hard for any given user. However I feel that some cleaning might be in order.

Quoted 4 lines

I guess there is no upper bound checking because I didn't see any type of boundary checking the server hashing code I stoled 8-) Or maybe I just missed it... Is there an example and what would trigger this cleanup?

You can register a 'shrinker' which gets called then the vm wants to reclaim memory. See mm/vmscan.c
It gets passed the number of items you should try to discard, and returned the number of items that are left.

And if you arrange to do all the freeing in batches using the shrinker, you could use RCU to make all the searches and additions lockless (Well, you still need rcu_read_lock, but that is super light weight). That would be fun :-)

Quoted 10 lines
Quoted 10 lines

It occurs to me that the large majority of inodes will only be accessed by a single user and so need not reside in the cache.

So how about having a single "struct nfs_access_entry" pointer in the inode.
When we do a lookup we look there first.
When we want to add an entry, we try to add it there first. When we end up with two current access entries for the same inode, only then do we insert them into the hash.

Quoted 5 lines

To rephrase to make sure I understand....
1) P1(uid=1) creates an access pointer in the nfs_inode
2) P2(uid=2) sees the access pointer is not null so it adds them both to the table, right?

Exactly.

Quoted 12 lines
Quoted 4 lines

We would need to be able to tell from the inode whether anything is hashed or not. This could simply be if the nfs_access_entry point is non-null, and its hashlist it non-empty. Or we could just use a bit flag somewhere.

So I guess it would be something like:
if (nfs_inode->access == null)

     set nfs_inode->access

if (nfs_inode->access =! NULL && nfs_inode->access_hash == empty)
move both pointer into hast able.
if (nfs_inode->access == null && nfs_inode->access_hash != empty)
use hastable.

Quoted 4 lines

But now the question is how would I know when there is only one entry in the table? Or do we just let the hash table "drain" naturally and when it become empty we start with the nfs_inode->access pointer again... Is this close to what your thinking??

Yes. Spot on. Once some inode has 'spilled' into the hash table there isn't a lot to gain by "unspilling" it.

NeilBrown

#5 lore raw
Quoted 23 lines · Neil Brown
Quoted 5 lines

To rephrase to make sure I understand....
1) P1(uid=1) creates an access pointer in the nfs_inode
2) P2(uid=2) sees the access pointer is not null so it adds them both to the table, right?

Exactly.

Quoted 13 lines
Quoted 4 lines

We would need to be able to tell from the inode whether anything is hashed or not. This could simply be if the nfs_access_entry point is non-null, and its hashlist it non-empty. Or we could just use a bit flag somewhere.

So I guess it would be something like:
if (nfs_inode->access == null)

    set nfs_inode->access

if (nfs_inode->access =! NULL && nfs_inode->access_hash == empty)
move both pointer into hast able.
if (nfs_inode->access == null && nfs_inode->access_hash != empty)
use hastable.

Quoted 8 lines
Quoted 4 lines

But now the question is how would I know when there is only one entry in the table? Or do we just let the hash table "drain" naturally and when it become empty we start with the nfs_inode->access pointer again... Is this close to what your thinking??

Yes. Spot on. Once some inode has 'spilled' into the hash table there isn't a lot to gain by "unspilling" it.

Talking with Trond, he would like to do something slightly different which I'll outline here to make sure we are all on the same page....

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

We would govern memory consumption by only allowing 30 entries on any one hlist in the nfs_inode and by registering the globe hlist with the VFS shrinker which will cause the list to be prune when memory is needed. So this means, when the 31st entry was added to the hlist in the nfs_inode, the least recently used entry would be removed.

Locking might be a bit tricky, but do able... To make this scalable, I would think we would need global read/write spin_lock. The read_lock() would be taken when the hlist in the inode was searched and the write_lock() would taken when the hlist in the inode was changed and when the global list was prune.

Comments?

steved.

#6 lore raw
Quoted 36 lines · Steve Dickson
Quoted 31 lines · Neil Brown
Quoted 5 lines

To rephrase to make sure I understand....
1) P1(uid=1) creates an access pointer in the nfs_inode
2) P2(uid=2) sees the access pointer is not null so it adds them both to the table, right?

Exactly.

Quoted 14 lines
Quoted 4 lines

We would need to be able to tell from the inode whether anything is hashed or not. This could simply be if the nfs_access_entry point is non-null, and its hashlist it non-empty. Or we could just use a bit flag somewhere.

So I guess it would be something like:
if (nfs_inode->access == null)

    set nfs_inode->access

if (nfs_inode->access =! NULL && nfs_inode->access_hash == empty)
move both pointer into hast able.
if (nfs_inode->access == null && nfs_inode->access_hash != empty)
use hastable.

Quoted 4 lines

But now the question is how would I know when there is only one entry in the table? Or do we just let the hash table "drain" naturally and when it become empty we start with the nfs_inode->access pointer again... Is this close to what your thinking??

Quoted 2 lines

Yes. Spot on. Once some inode has 'spilled' into the hash table there isn't a lot to gain by "unspilling" it.

Quoted 9 lines

Talking with Trond, he would like to do something slightly different which I'll outline here to make sure we are all on the same page....

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

How are these lists used?

I would suggest that a global set of hash queues would work better than a linked list and that these hash queues by used to find the cache entry for any particular user. Finding the entry for a particular (user,inode) needs to be fast and linearly searching a linked list is slow. Linear searching needs to be avoided. Comparing the fewest number of entries possible will result in the best performance because the comparisons need to take into account the entire user identification, including the groups list.

The list in the inode seems useful, but only for purges. Searching via this list will be very slow once the list grows beyond a few entries. Purging needs to be fast because purging the access cache entries for a particular file will need to happen whenever the ctime on the file changes. This list can be used to make it easy to find the correct entries in the global access cache.

Quoted 7 lines

We would govern memory consumption by only allowing 30 entries on any one hlist in the nfs_inode and by registering the globe hlist with the VFS shrinker which will cause the list to be prune when memory is needed. So this means, when the 31st entry was added to the hlist in the nfs_inode, the least recently used entry would be removed.

Why is there a limit at all and why is 30 the right number? This seems small and rather arbitrary. If there is some way to trigger memory reclaiming, then letting the list grow as appropriate seems like a good thing to do.

Making sure that you are one of the original 30 users accessing the file in order to get reasonable performance seems tricky to me. :-)

Quoted 6 lines

Locking might be a bit tricky, but do able... To make this scalable, I would think we would need global read/write spin_lock. The read_lock() would be taken when the hlist in the inode was searched and the write_lock() would taken when the hlist in the inode was changed and when the global list was prune.

Sorry, read/write spin lock? I thought that spin locks were exclusive, either the lock was held or the process spins waiting to acquire it.

A global reader/writer lock can make a lot of sense though. The reader lock can allow concurrent lookups in the cache and the writer lock can serialize updates to the cache.

A global spin lock on the cache can work well. As long as the spin lock is not held for very long, ie. short search times, then the lack of concurrency should not be noticeable. One global spin lock can also make the implementation much simpler by simplifying the locking tremendously. Grab the lock, search for an entry, release it. Grab the lock, insert a new entry, release it. Simple and fast, not prone to deadlock or starvation issues.

Thanx...

ps

#7 lore raw
Quoted 8 lines · Peter Staubach
Quoted 6 lines

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

How are these lists used?

The inode hlist will be used to search and purge...

Quoted 9 lines

I would suggest that a global set of hash queues would work better than a linked list and that these hash queues by used to find the cache entry for any particular user. Finding the entry for a particular (user,inode) needs to be fast and linearly searching a linked list is slow. Linear searching needs to be avoided. Comparing the fewest number of entries possible will result in the best performance because the comparisons need to take into account the entire user identification, including the groups list.

I guess we could have the VFS shrinker to purge a hash table just as well as a link list... although a hash table will have an small memory cost...

Quoted 6 lines

The list in the inode seems useful, but only for purges. Searching via this list will be very slow once the list grows beyond a few entries. Purging needs to be fast because purging the access cache entries for a particular file will need to happen whenever the ctime on the file changes. This list can be used to make it easy to find the correct entries in the global access cache.

Seems reasonable assuming we use a hash table...

Quoted 9 lines
Quoted 8 lines

We would govern memory consumption by only allowing 30 entries on any one hlist in the nfs_inode and by registering the globe hlist with the VFS shrinker which will cause the list to be prune when memory is needed. So this means, when the 31st entry was added to the hlist in the nfs_inode, the least recently used entry would be removed.

Quoted 4 lines

Why is there a limit at all and why is 30 the right number? This seems small and rather arbitrary. If there is some way to trigger memory reclaiming, then letting the list grow as appropriate seems like a good thing to do.

Well the vfs mechanism will be the trigger... so your saying we should just let the purge hlist lists in the nfs_inode grow untethered? How about read-only filesystems where the ctime will not change... I would think we might want some type of high water mark for that case, true?

Quoted 11 lines

Making sure that you are one of the original 30 users accessing the file in order to get reasonable performance seems tricky to me. :-)

Quoted 6 lines

Locking might be a bit tricky, but do able... To make this scalable, I would think we would need global read/write spin_lock. The read_lock() would be taken when the hlist in the inode was searched and the write_lock() would taken when the hlist in the inode was changed and when the global list was prune.

Quoted 2 lines

Sorry, read/write spin lock? I thought that spin locks were exclusive, either the lock was held or the process spins waiting to acquire it.

See the rwlock_t lock type in asm/spinlock.h.. That's the one I was planning on using...

steved.

#8 lore raw
Quoted 9 lines · Steve Dickson
Quoted 7 lines · Peter Staubach
Quoted 6 lines

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

Quoted 4 lines
Quoted 1 line

How are these lists used?

The inode hlist will be used to search and purge...

Eeee! A linear search? That gets expensive as the list grows. A hashed list would keep the search times down.

Quoted 10 lines
Quoted 9 lines

I would suggest that a global set of hash queues would work better than a linked list and that these hash queues by used to find the cache entry for any particular user. Finding the entry for a particular (user,inode) needs to be fast and linearly searching a linked list is slow. Linear searching needs to be avoided. Comparing the fewest number of entries possible will result in the best performance because the comparisons need to take into account the entire user identification, including the groups list.

Quoted 4 lines

I guess we could have the VFS shrinker to purge a hash table just as well as a link list... although a hash table will have an small memory cost...

Yes, but small. There are always space/time tradeoffs.

Quoted 23 lines
Quoted 6 lines

The list in the inode seems useful, but only for purges. Searching via this list will be very slow once the list grows beyond a few entries. Purging needs to be fast because purging the access cache entries for a particular file will need to happen whenever the ctime on the file changes. This list can be used to make it easy to find the correct entries in the global access cache.

Seems reasonable assuming we use a hash table...

Quoted 9 lines
Quoted 8 lines

We would govern memory consumption by only allowing 30 entries on any one hlist in the nfs_inode and by registering the globe hlist with the VFS shrinker which will cause the list to be prune when memory is needed. So this means, when the 31st entry was added to the hlist in the nfs_inode, the least recently used entry would be removed.

Quoted 4 lines

Why is there a limit at all and why is 30 the right number? This seems small and rather arbitrary. If there is some way to trigger memory reclaiming, then letting the list grow as appropriate seems like a good thing to do.

Quoted 6 lines

Well the vfs mechanism will be the trigger... so your saying we should just let the purge hlist lists in the nfs_inode grow untethered? How about read-only filesystems where the ctime will not change... I would think we might want some type of high water mark for that case, true?

Not true. Why have a limit at all? As long as there is memory to store the information, why place arbitrary limits on the amount of information stored?

As long as the memory can be reclaimed when the system needs it, then I don't see any reason to place limits. Whatever number that is chosen is always the wrong number and requiring users to guess at the sizes or take steps to tune the system, when the system could have just done the right thing in the first place, is just wrong.

Quoted 11 lines
Quoted 11 lines

Making sure that you are one of the original 30 users accessing the file in order to get reasonable performance seems tricky to me. :-)

Quoted 6 lines

Locking might be a bit tricky, but do able... To make this scalable, I would think we would need global read/write spin_lock. The read_lock() would be taken when the hlist in the inode was searched and the write_lock() would taken when the hlist in the inode was changed and when the global list was prune.

Quoted 5 lines
Quoted 2 lines

Sorry, read/write spin lock? I thought that spin locks were exclusive, either the lock was held or the process spins waiting to acquire it.

See the rwlock_t lock type in asm/spinlock.h.. That's the one I was planning on using...

Hmmm. A reader/writer lock which is busy waited for. Is there any idea of the costs of such locks? This does seem like it would fit the bill though. It would be interesting to see what the access patterns for the cache end up looking like, whether it is useful to separate readers from writers in this fashion.

Thanx...

ps

-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs

#9 lore raw
Quoted 11 lines · Peter Staubach
Quoted 9 lines · Steve Dickson
Quoted 7 lines · Peter Staubach
Quoted 6 lines

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

How are these lists used?

The inode hlist will be used to search and purge...

Eeee! A linear search? That gets expensive as the list grows. A hashed list would keep the search times down.

I thought hlist was meant to be used for hash tables with chaining?

Ian

#10 lore raw
In reply to Steve Dickson
Quoted 16 lines · Steve Dickson

Talking with Trond, he would like to do something slightly different which I'll outline here to make sure we are all on the same page....

Basically we would maintain one global hlist (i.e. link list) that would contain all of the cached entries; then each nfs_inode would have its own LRU hlist that would contain entries that are associated with that nfs_inode. So each entry would be on two lists, the global hlist and hlist in the nfs_inode.

We would govern memory consumption by only allowing 30 entries on any one hlist in the nfs_inode and by registering the globe hlist with the VFS shrinker which will cause the list to be prune when memory is needed. So this means, when the 31st entry was added to the hlist in the nfs_inode, the least recently used entry would be removed.

Quoted 5 lines

Locking might be a bit tricky, but do able... To make this scalable, I would think we would need global read/write spin_lock. The read_lock() would be taken when the hlist in the inode was searched and the write_lock() would taken when the hlist in the inode was changed and when the global list was prune.

For the sake of discussion, let me propose some design alternatives.

1. We already have cache shrinkage built in: when an inode is purged due to cache shrinkage, the access cache for that inode is purged as well. In other words, there is already a mechanism for external memory pressure to shrink this cache. I don't see a strong need to complicate matters by adding more cache shrinkage than already exists with normal inode and dentry cache shrinkage.

Now you won't need to hold a global lock to serialize normal accesses with purging and cache garbage collection. Eliminating global serialization is a Good Thing (tm).

2. Use a radix tree per inode. The radix tree key is a uid or gid, and each node in a tree stores the access mask for that {inode, uid} tuple. This seems a lot simpler to implement than a dual hlist, and will
scale automatically with a large number of uids accessing the same inode. The nodes are small, and you don't need to allocate a big chunk of contiguous memory for a hash table.

3. Instead of serializing by spinning, you should use a semaphore. The reason for this is that when multiple processes owned by the same uid access the same inode concurrently, only the first process should be allowed to generate a real ACCESS request; otherwise they will race and potentially all of them could generate the same ACCESS request concurrently.

You will need to serialize on-the-wire requests with accesses to the cache, and such wire requests will need the waiting processes to sleep, not spin.

4. You will need some mechanism for ensuring that the contents of the access cache are "up to date". You will need some way of deciding when to revalidate each {inode, uid} tuple. Based on what Peter said, I think you are going to check the inode's ctime, and purge the whole access cache for an inode if its ctime changes. But you may need something like an nfs_revalidate_inode() before you proceed to examine an inode's access cache. It might be more efficient to generate just an ACCESS request instead of a GETATTR followed by an ACCESS, but I don't see an easy way to do this given the current inode revalidation architecture of the client.

5. You need to handle ESTALE. Often, ->permission is the first thing the VFS will do before a lookup or open, and that is when the NFS client first notices that a cached file handle is stale. Should ESTALE returned on an ACCESS request mean always return permission denied, or should it mean purge the access cache and grant access, so that the next VFS step sees the ESTALE and can recover appropriately?

Signature · 2 lines
corporate:	<cel at netapp dot com>
personal:	<chucklever at bigfoot dot com>
#11 lore raw

Here is the second attempt at improving the access cache. I believe all of the concerns from the first patch have been addressed.

Quoted 2 lines · Chuck Lever

1. We already have cache shrinkage built in: when an inode is purged due to cache shrinkage, the access cache for that inode is purged as well. In other words, there is already a mechanism for external memory pressure to shrink this cache. I don't see a strong need to complicate matters by adding more cache shrinkage than already exists with normal inode and dentry cache shrinkage.

I agree... so there no extra code to shrink this cache.

Quoted 2 lines

2. Use a radix tree per inode.

Using radix trees actual makes things much simpler... Good idea, imo.

Quoted 2 lines

3. Instead of serializing by spinning, you should use a semaphore.

I turns out that spin lock are probably better protecting this cache because while looking up the cache entry I might have to discard the entry, so I would have to upgrade a read semaphore to a write one which is a bit messy and not needed imho... But I do agree with you about global locks, so I added the spin lock to the nfs_inode.

Quoted 2 lines

You will need to serialize on-the-wire requests with accesses to the cache, and such wire requests will need the waiting processes to sleep, not spin.

True... so I use added a bit to the nfs_inode flags that will serialize over-the-write request similar to how getattrs are.

Quoted 2 lines

4. You will need some mechanism for ensuring that the contents of the access cache are "up to date".

This cache is tied to the attribute cache and when that times out or is invalided, the cache entry is discarded... With my testing, this seems to just fine.

Quoted 2 lines

5. You need to handle ESTALE.

True... and this patch does.

Comments?

steved.

This patch improves the caching of ACCESS information by storing the information in radix tree. It also serializes over-the-wire ACCESS calls. The patch greatly decreases the number of ACCESS calls when processes with different uids access the same directory.

----------------------------------------------------

fs/nfs/nfs4proc.c renamed from fs/nfs/nfs4proc.c.orig +4 -0
@@ -785,6 +785,10 @@ static int _nfs4_do_access(struct inode 
 	status = _nfs4_proc_access(inode, &cache);
 	if (status != 0)
 		return status;
+
+	/* Zero masks are turned into a negative entry */
+	if (!cache.mask) 
+		cache.mask |= ~mask;
 	nfs_access_add_cache(inode, &cache);
 out:
 	if ((cache.mask & mask) == mask)
fs/nfs/inode.c renamed from fs/nfs/inode.c.orig +10 -12
@@ -170,14 +170,11 @@ static void
 nfs_clear_inode(struct inode *inode)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
-	struct rpc_cred *cred;
 
 	nfs_wb_all(inode);
 	BUG_ON (!list_empty(&nfsi->open_files));
 	nfs_zap_acl_cache(inode);
-	cred = nfsi->cache_access.cred;
-	if (cred)
-		put_rpccred(cred);
+	nfs_zap_access_cache(inode);
 	BUG_ON(atomic_read(&nfsi->data_updates) != 0);
 }
 
@@ -940,7 +937,6 @@ nfs_fhget(struct super_block *sb, struct
 		nfsi->attrtimeo = NFS_MINATTRTIMEO(inode);
 		nfsi->attrtimeo_timestamp = jiffies;
 		memset(nfsi->cookieverf, 0, sizeof(nfsi->cookieverf));
-		nfsi->cache_access.cred = NULL;
 
 		unlock_new_inode(inode);
 	} else
@@ -1039,7 +1035,7 @@ static int nfs_wait_schedule(void *word)
 /*
  * Wait for the inode to get unlocked.
  */
-static int nfs_wait_on_inode(struct inode *inode)
+int nfs_wait_on_inode(struct inode *inode, int bit)
 {
 	struct rpc_clnt	*clnt = NFS_CLIENT(inode);
 	struct nfs_inode *nfsi = NFS_I(inode);
@@ -1047,20 +1043,20 @@ static int nfs_wait_on_inode(struct inod
 	int error;
 
 	rpc_clnt_sigmask(clnt, &oldmask);
-	error = wait_on_bit_lock(&nfsi->flags, NFS_INO_REVALIDATING,
+	error = wait_on_bit_lock(&nfsi->flags, bit,
 					nfs_wait_schedule, TASK_INTERRUPTIBLE);
 	rpc_clnt_sigunmask(clnt, &oldmask);
 
 	return error;
 }
 
-static void nfs_wake_up_inode(struct inode *inode)
+void nfs_wake_up_inode(struct inode *inode, int bit)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
 
-	clear_bit(NFS_INO_REVALIDATING, &nfsi->flags);
+	clear_bit(bit, &nfsi->flags);
 	smp_mb__after_clear_bit();
-	wake_up_bit(&nfsi->flags, NFS_INO_REVALIDATING);
+	wake_up_bit(&nfsi->flags, bit);
 }
 
 int nfs_getattr(struct vfsmount *mnt, struct dentry *dentry, struct kstat *stat)
@@ -1235,7 +1231,7 @@ __nfs_revalidate_inode(struct nfs_server
 	if (NFS_STALE(inode))
  		goto out_nowait;
 
-	status = nfs_wait_on_inode(inode);
+	status = nfs_wait_on_inode(inode, NFS_INO_REVALIDATING);
 	if (status < 0)
 		goto out;
 	if (NFS_STALE(inode)) {
@@ -1283,7 +1279,7 @@ __nfs_revalidate_inode(struct nfs_server
 		(long long)NFS_FILEID(inode));
 
  out:
-	nfs_wake_up_inode(inode);
+	nfs_wake_up_inode(inode, NFS_INO_REVALIDATING);
 
  out_nowait:
 	unlock_kernel();
@@ -2874,6 +2870,8 @@ static void init_once(void * foo, kmem_c
 		INIT_LIST_HEAD(&nfsi->commit);
 		INIT_LIST_HEAD(&nfsi->open_files);
 		INIT_RADIX_TREE(&nfsi->nfs_page_tree, GFP_ATOMIC);
+		INIT_RADIX_TREE(&nfsi->access_cache, GFP_ATOMIC);
+		spin_lock_init(&nfsi->access_lock);
 		atomic_set(&nfsi->data_updates, 0);
 		nfsi->ndirty = 0;
 		nfsi->ncommit = 0;
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +76 -21

130 lines not on this page · raw message

include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +16 -1
@@ -145,7 +145,8 @@ struct nfs_inode {
 	 */
 	atomic_t		data_updates;
 
-	struct nfs_access_entry	cache_access;
+	struct radix_tree_root	access_cache;
+	spinlock_t access_lock;
 #ifdef CONFIG_NFS_V3_ACL
 	struct posix_acl	*acl_access;
 	struct posix_acl	*acl_default;
@@ -199,6 +200,7 @@ struct nfs_inode {
 #define NFS_INO_REVALIDATING	(0)		/* revalidating attrs */
 #define NFS_INO_ADVISE_RDPLUS	(1)		/* advise readdirplus */
 #define NFS_INO_STALE		(2)		/* possible stale inode */
+#define NFS_INO_ACCESS		(3)		/* checking access bits */
 
 static inline struct nfs_inode *NFS_I(struct inode *inode)
 {
@@ -256,6 +258,17 @@ static inline int NFS_USE_READDIRPLUS(st
 	return test_bit(NFS_INO_ADVISE_RDPLUS, &NFS_FLAGS(inode));
 }
 
+static inline void nfs_zap_access_cache(struct inode *inode)
+{
+	struct nfs_access_entry *cache;
+
+	cache = radix_tree_delete(&NFS_I(inode)->access_cache, inode->i_uid);
+	if (cache) {
+		put_rpccred(cache->cred);
+		kfree(cache);
+	}
+}
+
 /**
  * nfs_save_change_attribute - Returns the inode attribute change cookie
  * @inode - pointer to inode
@@ -299,6 +312,8 @@ extern int nfs_attribute_timeout(struct 
 extern int nfs_revalidate_inode(struct nfs_server *server, struct inode *inode);
 extern int __nfs_revalidate_inode(struct nfs_server *, struct inode *);
 extern void nfs_revalidate_mapping(struct inode *inode, struct address_space *mapping);
+extern int nfs_wait_on_inode(struct inode *inode, int bit);
+extern void nfs_wake_up_inode(struct inode *inode, int bit);
 extern int nfs_setattr(struct dentry *, struct iattr *);
 extern void nfs_setattr_update_inode(struct inode *inode, struct iattr *attr);
 extern void nfs_begin_attr_update(struct inode *);
#12 lore raw
Quoted 10 lines · Steve Dickson

Here is the second attempt at improving the access cache. I believe all of the concerns from the first patch have been addressed.

Quoted 2 lines · Chuck Lever

1. We already have cache shrinkage built in: when an inode is purged due to cache shrinkage, the access cache for that inode is purged as well. In other words, there is already a mechanism for external memory pressure to shrink this cache. I don't see a strong need to complicate matters by adding more cache shrinkage than already exists with normal inode and dentry cache shrinkage.

I agree... so there no extra code to shrink this cache.

I think that this _may_ be okay, but since this cache is not required for correctness, it would be nice to be able to shrink the entries from active inodes off of it when system memory goes low enough.

Quoted 5 lines
Quoted 2 lines

2. Use a radix tree per inode.

Using radix trees actual makes things much simpler... Good idea, imo.

It does seem like a good idea, although just using the uid is not sufficient to identify the correct access cache entry. The group and groups list must also be used. Can the radix tree implementation support this?

Quoted 8 lines

------------------------------------------------------------------------

This patch improves the caching of ACCESS information by storing
the information in radix tree. It also serializes over-the-wire
ACCESS calls. The patch greatly decreases the number of ACCESS calls when processes with different uids access the same directory.

Some comments intermixed below...

Quoted 195 lines

----------------------------------------------------

fs/nfs/nfs4proc.c renamed from fs/nfs/nfs4proc.c.orig +4 -0
@@ -785,6 +785,10 @@ static int _nfs4_do_access(struct inode 
 	status = _nfs4_proc_access(inode, &cache);
 	if (status != 0)
 		return status;
+
+	/* Zero masks are turned into a negative entry */
+	if (!cache.mask) 
+		cache.mask |= ~mask;
 	nfs_access_add_cache(inode, &cache);

out:

	if ((cache.mask & mask) == mask)
fs/nfs/inode.c renamed from fs/nfs/inode.c.orig +10 -12
@@ -170,14 +170,11 @@ static void
 nfs_clear_inode(struct inode *inode)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
-	struct rpc_cred *cred;
 
 	nfs_wb_all(inode);
 	BUG_ON (!list_empty(&nfsi->open_files));
 	nfs_zap_acl_cache(inode);
-	cred = nfsi->cache_access.cred;
-	if (cred)
-		put_rpccred(cred);
+	nfs_zap_access_cache(inode);
 	BUG_ON(atomic_read(&nfsi->data_updates) != 0);
 }
 
@@ -940,7 +937,6 @@ nfs_fhget(struct super_block *sb, struct
 		nfsi->attrtimeo = NFS_MINATTRTIMEO(inode);
 		nfsi->attrtimeo_timestamp = jiffies;
 		memset(nfsi->cookieverf, 0, sizeof(nfsi->cookieverf));
-		nfsi->cache_access.cred = NULL;
 
 		unlock_new_inode(inode);
 	} else
@@ -1039,7 +1035,7 @@ static int nfs_wait_schedule(void *word)
 /*
 * Wait for the inode to get unlocked.
 */
-static int nfs_wait_on_inode(struct inode *inode)
+int nfs_wait_on_inode(struct inode *inode, int bit)
 {
 	struct rpc_clnt	*clnt = NFS_CLIENT(inode);
 	struct nfs_inode *nfsi = NFS_I(inode);
@@ -1047,20 +1043,20 @@ static int nfs_wait_on_inode(struct inod
 	int error;
 
 	rpc_clnt_sigmask(clnt, &oldmask);
-	error = wait_on_bit_lock(&nfsi->flags, NFS_INO_REVALIDATING,
+	error = wait_on_bit_lock(&nfsi->flags, bit,
 					nfs_wait_schedule, TASK_INTERRUPTIBLE);
 	rpc_clnt_sigunmask(clnt, &oldmask);
 
 	return error;
 }
 
-static void nfs_wake_up_inode(struct inode *inode)
+void nfs_wake_up_inode(struct inode *inode, int bit)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
 
-	clear_bit(NFS_INO_REVALIDATING, &nfsi->flags);
+	clear_bit(bit, &nfsi->flags);
 	smp_mb__after_clear_bit();
-	wake_up_bit(&nfsi->flags, NFS_INO_REVALIDATING);
+	wake_up_bit(&nfsi->flags, bit);
 }
 
 int nfs_getattr(struct vfsmount *mnt, struct dentry *dentry, struct kstat *stat)
@@ -1235,7 +1231,7 @@ __nfs_revalidate_inode(struct nfs_server
 	if (NFS_STALE(inode))
 		goto out_nowait;
 
-	status = nfs_wait_on_inode(inode);
+	status = nfs_wait_on_inode(inode, NFS_INO_REVALIDATING);
 	if (status < 0)
 		goto out;
 	if (NFS_STALE(inode)) {
@@ -1283,7 +1279,7 @@ __nfs_revalidate_inode(struct nfs_server
 		(long long)NFS_FILEID(inode));
 
 out:
-	nfs_wake_up_inode(inode);
+	nfs_wake_up_inode(inode, NFS_INO_REVALIDATING);
 
 out_nowait:
 	unlock_kernel();
@@ -2874,6 +2870,8 @@ static void init_once(void * foo, kmem_c
 		INIT_LIST_HEAD(&nfsi->commit);
 		INIT_LIST_HEAD(&nfsi->open_files);
 		INIT_RADIX_TREE(&nfsi->nfs_page_tree, GFP_ATOMIC);
+		INIT_RADIX_TREE(&nfsi->access_cache, GFP_ATOMIC);
+		spin_lock_init(&nfsi->access_lock);
 		atomic_set(&nfsi->data_updates, 0);
 		nfsi->ndirty = 0;
 		nfsi->ncommit = 0;
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +50 -18
@@ -1636,35 +1636,67 @@ out:
 	return error;
 }
 
-int nfs_access_get_cached(struct inode *inode, struct rpc_cred *cred, struct nfs_access_entry *res)
+int nfs_access_get_cached(struct inode *inode, struct rpc_cred *cred, 
+	struct nfs_access_entry *res)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
-	struct nfs_access_entry *cache = &nfsi->cache_access;
+	int invalid = (nfsi->cache_validity & NFS_INO_INVALID_ACCESS);
+	struct nfs_access_entry *cache;
+	int expired;
+
+	spin_lock(&nfsi->access_lock);
+	cache = (struct nfs_access_entry *)
+		radix_tree_lookup(&nfsi->access_cache, cred->cr_uid);
+
+	if (cache) {
+		expired = time_after(jiffies, 
+				cache->jiffies + NFS_ATTRTIMEO(inode));
+		if (expired || invalid) {
+			(void)radix_tree_delete(&nfsi->access_cache, cred->cr_uid);
+			spin_unlock(&nfsi->access_lock);
+			put_rpccred(cache->cred);
+			kfree(cache);
+			goto nolock;
+		}
+		memcpy(res, cache, sizeof(*res));
+		spin_unlock(&nfsi->access_lock);
+		return 0;
+	}
+	spin_unlock(&nfsi->access_lock);
 
-	if (cache->cred != cred
-			|| time_after(jiffies, cache->jiffies + NFS_ATTRTIMEO(inode))
-			|| (nfsi->cache_validity & NFS_INO_INVALID_ACCESS))
-		return -ENOENT;
-	memcpy(res, cache, sizeof(*res));
-	return 0;
+nolock:
+	return -ENOENT;
 }
 
 void nfs_access_add_cache(struct inode *inode, struct nfs_access_entry *set)
 {
 	struct nfs_inode *nfsi = NFS_I(inode);
-	struct nfs_access_entry *cache = &nfsi->cache_access;
-
-	if (cache->cred != set->cred) {
-		if (cache->cred)
-			put_rpccred(cache->cred);
-		cache->cred = get_rpccred(set->cred);
+	struct nfs_access_entry *cache = NULL;
+	uid_t cr_uid = set->cred->cr_uid;
+	int error;
+
+	cache = (struct nfs_access_entry *)kmalloc(sizeof(*cache), GFP_KERNEL);
+	if (!cache)
+		return;
+
+	spin_lock(&nfsi->access_lock);
+	error = radix_tree_insert(&nfsi->access_cache, cr_uid, cache);
+	if (error) {
+		spin_unlock(&nfsi->access_lock);
+		kfree(cache);
+		return;
 	}
-	/* FIXME: replace current access_cache BKL reliance with inode->i_lock */
+
+	cache->cred = get_rpccred(set->cred);
+	cache->jiffies = jiffies;
+	cache->mask = set->mask;
+	spin_unlock(&nfsi->access_lock);
+
 	spin_lock(&inode->i_lock);
 	nfsi->cache_validity &= ~NFS_INO_INVALID_ACCESS;
 	spin_unlock(&inode->i_lock);
-	cache->jiffies = set->jiffies;
-	cache->mask = set->mask;
+
+	return;
 }
 
 static int nfs_do_access(struct inode *inode, struct rpc_cred *cred, int mask)
@@ -1674,19 +1706,42 @@ static int nfs_do_access(struct inode *i
 
 	status = nfs_access_get_cached(inode, cred, &cache);
 	if (status == 0)
-		goto out;
+		goto out_nowait;

fs/nfs/dir.c static int nfs_do_access(struct inode *i · line 1719

Quoted 10 lines
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +8 -0
+
+	if (test_and_set_bit(NFS_INO_ACCESS, &NFS_FLAGS(inode))) {
+		status = nfs_wait_on_inode(inode, NFS_INO_ACCESS);
+		if (status < 0)
+			return status;
+
+		nfs_access_get_cached(inode, cred, &cache);
+		goto out_nowait;
 
 

You can't just go to out_nowait here, can you? What happens if something happened to the file while you were asleep? Or an entry could be added to the cache for some reason such as kmalloc failure? I would suggest going back to the top and starting the process all over again.

Quoted 54 lines
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +18 -3
+	}
 
 	/* Be clever: ask server to check for all possible rights */
 	cache.mask = MAY_EXEC | MAY_WRITE | MAY_READ;
 	cache.cred = cred;
-	cache.jiffies = jiffies;
 	status = NFS_PROTO(inode)->access(inode, &cache);
-	if (status != 0)
+	if (status != 0) {
+		if (status == -ESTALE) {
+			nfs_zap_caches(inode);
+			if (!S_ISDIR(inode->i_mode))
+				set_bit(NFS_INO_STALE, &NFS_FLAGS(inode));
+		}
+		nfs_wake_up_inode(inode, NFS_INO_ACCESS);
 		return status;
+	}
+
+	/* Zero masks are turned into a negative entry */
+	if (!cache.mask) 
+		cache.mask |= ~mask;
 	nfs_access_add_cache(inode, &cache);
-out:
+
+	nfs_wake_up_inode(inode, NFS_INO_ACCESS);
+
+out_nowait:
 	if ((cache.mask & mask) == mask)
 		return 0;
+
 	return -EACCES;

}

include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +3 -1
@@ -145,7 +145,8 @@ struct nfs_inode {
 	 */
 	atomic_t		data_updates;
 
-	struct nfs_access_entry	cache_access;
+	struct radix_tree_root	access_cache;
+	spinlock_t access_lock;
 #ifdef CONFIG_NFS_V3_ACL
 	struct posix_acl	*acl_access;
 	struct posix_acl	*acl_default;
@@ -199,6 +200,7 @@ struct nfs_inode {
 #define NFS_INO_REVALIDATING	(0)		/* revalidating attrs */
 #define NFS_INO_ADVISE_RDPLUS	(1)		/* advise readdirplus */
 #define NFS_INO_STALE		(2)		/* possible stale inode */
+#define NFS_INO_ACCESS		(3)		/* checking access bits */
 
 static inline struct nfs_inode *NFS_I(struct inode *inode)
 {

include/linux/nfs_fs.h static inline int NFS_USE_READDIRPLUS(st · line 267

Quoted 10 lines
include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +5 -0
@@ -256,6 +258,17 @@ static inline int NFS_USE_READDIRPLUS(st
 	return test_bit(NFS_INO_ADVISE_RDPLUS, &NFS_FLAGS(inode));
 }
 
+static inline void nfs_zap_access_cache(struct inode *inode)
+{
+	struct nfs_access_entry *cache;
+
+	cache = radix_tree_delete(&NFS_I(inode)->access_cache, inode->i_uid);
 
 

Do you need to be hold access_lock here?

include/linux/nfs_fs.h static inline int NFS_USE_READDIRPLUS(st · line 272

Quoted 6 lines
include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +4 -0
+	if (cache) {
+		put_rpccred(cache->cred);
+		kfree(cache);
+	}
 

What happens if there was more than 1 entry in the cache?

Quoted 8 lines
include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +2 -0
+}
+

/**
* nfs_save_change_attribute - Returns the inode attribute change cookie
* @inode - pointer to inode

include/linux/nfs_fs.h extern int nfs_attribute_timeout(struct · line 319

Quoted 8 lines
include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +2 -0
@@ -299,6 +312,8 @@ extern int nfs_attribute_timeout(struct 
 extern int nfs_revalidate_inode(struct nfs_server *server, struct inode *inode);
 extern int __nfs_revalidate_inode(struct nfs_server *, struct inode *);
 extern void nfs_revalidate_mapping(struct inode *inode, struct address_space *mapping);
+extern int nfs_wait_on_inode(struct inode *inode, int bit);
+extern void nfs_wake_up_inode(struct inode *inode, int bit);
 extern int nfs_setattr(struct dentry *, struct iattr *);
 extern void nfs_setattr_update_inode(struct inode *inode, struct iattr *attr);
 extern void nfs_begin_attr_update(struct inode *);

Thanx...

ps

-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs

#13 lore raw
Quoted 3 lines · Peter Staubach

You can't just go to out_nowait here, can you? What happens if something happened to the file while you were asleep? Or an entry could be added to

Opps, that would be "could not be added"...

Quoted 2 lines

the cache for some reason such as kmalloc failure? I would suggest going back to the top and starting the process all over again.

Sorry...

ps

-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs

#14 lore raw
In reply to Peter Staubach
Quoted 10 lines · Peter Staubach
Quoted 6 lines
Quoted 2 lines

2. Use a radix tree per inode.

Using radix trees actual makes things much simpler... Good idea, imo.

It does seem like a good idea, although just using the uid is not sufficient to identify the correct access cache entry. The group and groups list must also be used. Can the radix tree implementation support this?

We could use (nfsi + uid) as the index... but its not clear what that would buys us... And the group and group list were never part of the cache in the first place.... is this something you feel needs to be added or am I just not understanding....

Quoted 12 lines
Quoted 12 lines

static int nfs_do_access(struct inode *inode, struct rpc_cred *cred, int mask)

fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +6 -1
@@ -1674,19 +1706,42 @@ static int nfs_do_access(struct inode *i
 
    status = nfs_access_get_cached(inode, cred, &cache);
    if (status == 0)
-        goto out;
+        goto out_nowait;
+
+    if (test_and_set_bit(NFS_INO_ACCESS, &NFS_FLAGS(inode))) {
+        status = nfs_wait_on_inode(inode, NFS_INO_ACCESS);
+        if (status < 0)
+            return status;
Quoted 8 lines

fs/nfs/dir.c static int nfs_do_access(struct inode *i · line 1747

Quoted 5 lines
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +3 -0
+
+        nfs_access_get_cached(inode, cred, &cache);
+        goto out_nowait;
 
 

You can't just go to out_nowait here, can you? What happens if something happened to the file while you were asleep?

point... after the nfs_wait_on_inode() call, nfs_access_get_cached() will be retried ala...

static int nfs_do_access(struct inode *inode, struct rpc_cred *cred, int mask)

{
    struct nfs_access_entry cache;
    int status;

retry:

    status = nfs_access_get_cached(inode, cred, &cache);
    if (status == 0)
        goto out_nowait;

    if (test_and_set_bit(NFS_INO_ACCESS, &NFS_FLAGS(inode))) {
        status = nfs_wait_on_inode(inode, NFS_INO_ACCESS);
        if (status < 0)
            return status;

        goto retry;
    }
Quoted 10 lines

include/linux/nfs_fs.h static inline int NFS_USE_READDIRPLUS(st

Quoted 8 lines
include/linux/nfs_fs.h renamed from include/linux/nfs_fs.h.orig +5 -0
+static inline void nfs_zap_access_cache(struct inode *inode)
+{
+    struct nfs_access_entry *cache;
+
+    cache = radix_tree_delete(&NFS_I(inode)->access_cache, 
 inode->i_uid);
 
 

Do you need to be hold access_lock here?

Yes...

Quoted 9 lines

fs/nfs/dir.c out: · line 1670

Quoted 7 lines
fs/nfs/dir.c renamed from fs/nfs/dir.c.orig +4 -0
+    if (cache) {
+        put_rpccred(cache->cred);
+        kfree(cache);
+    }
 
 

What happens if there was more than 1 entry in the cache?

I thought that since nfs_clear_inode() is called for each and every inode that cache would drain "naturally" but that turns out to be a bit brain dead... :-\

The problem is there does not seems to be a radix tree interface that will simply destroy the tree... It appears you need to know at least the beginning index and since the indexes in this tree are not symmetrical I'm not sure that would even help...

Anybody.... Is there a way to destroy a radix tree without known any of the indexes?

steved.

#19 lore raw
In reply to Chuck Lever
Quoted 10 lines · On Wednesday May 3, [email protected] wrote:

For the sake of discussion, let me propose some design alternatives.

1. We already have cache shrinkage built in: when an inode is purged due to cache shrinkage, the access cache for that inode is purged as well. In other words, there is already a mechanism for external memory pressure to shrink this cache. I don't see a strong need to complicate matters by adding more cache shrinkage than already exists with normal inode and dentry cache shrinkage.

If you have one particular file that is use regularly - and so never falls out of cache - and is uses occasionally by every single user in you system, then that one inode could contribute to thousands of access cache items that will never be purged.

This is why I thought that some sort of cleaning of the access cache was important.

NeilBrown

#20 lore raw
Quoted 9 lines · Neil Brown
Quoted 3 lines · On Wednesday May 3, [email protected] wrote:

For the sake of discussion, let me propose some design alternatives.

1. We already have cache shrinkage built in: when an inode is purged due to cache shrinkage, the access cache for that inode is purged as well. In other words, there is already a mechanism for external memory pressure to shrink this cache. I don't see a strong need to complicate matters by adding more cache shrinkage than already exists with normal inode and dentry cache shrinkage.

If you have one particular file that is used regularly - and so never falls out of cache - and is used occasionally by every single user in your system, then that one inode could contribute to thousands of access cache items that will never be purged.

I speculate that this would not be a problem.

First, each entry in the cache is not going to be very large. For the sake of easy math, let's say each one is 32 bytes. One hundred thousand of these is a little more than 3MB. Or, say we have ten thousand files with 10 different access cache entries: again, that's just about 3MB. (Naturally I'm ignoring the slab accounting overhead).

Even a single-user system these days is going to have a gigabyte or more of RAM, so we're talking less than a percent of memory tied up in this case. Three megabytes is probably less memory than a single Gnome application uses for its working set.

I'm always told to start with a design that is as simple as possible (and no simpler) and build on it only when I find a problem; this avoids overdesign. I don't see a compelling reason to start with a complicated design here, and there are good reasons to keep it simple.

If allowing the access cache to grow potentially without bounds still makes you nervous, I maintain that we still want to avoid a global LRU.
Having an LRU _per-inode_ might be a simple way to limit the amount of
memory that is consumed without the locking and management overhead of a global LRU. If entries haven't been accessed in more than actimeo seconds, then purge them; we'll have to go back to the server to revalidate such entries anyway, so there's no reason to keep them around.

It is pretty cheap to release, say, the two oldest entries every time you try an access, provided they have not been touched in actimeo seconds.

Signature · 2 lines
corporate:	<cel at netapp dot com>
personal:	<chucklever at bigfoot dot com>
#21 lore raw
Quoted 13 lines · On Sunday May 7, [email protected] wrote:
Quoted 4 lines

If you have one particular file that is used regularly - and so never falls out of cache - and is used occasionally by every single user in your system, then that one inode could contribute to thousands of access cache items that will never be purged.

I speculate that this would not be a problem.

First, each entry in the cache is not going to be very large. For the sake of easy math, let's say each one is 32 bytes. One hundred thousand of these is a little more than 3MB. Or, say we have ten thousand files with 10 different access cache entries: again, that's just about 3MB. (Naturally I'm ignoring the slab accounting overhead).

Quoted 4 lines

Even a single-user system these days is going to have a gigabyte or more of RAM, so we're talking less than a percent of memory tied up in this case. Three megabytes is probably less memory than a single Gnome application uses for its working set.

:-)

Quoted 5 lines

I'm always told to start with a design that is as simple as possible (and no simpler) and build on it only when I find a problem; this avoids overdesign. I don't see a compelling reason to start with a complicated design here, and there are good reasons to keep it simple.

You are probably right.

Quoted 11 lines

If allowing the access cache to grow potentially without bounds still makes you nervous, I maintain that we still want to avoid a global LRU.
Having an LRU _per-inode_ might be a simple way to limit the amount of
memory that is consumed without the locking and management overhead of a global LRU. If entries haven't been accessed in more than actimeo seconds, then purge them; we'll have to go back to the server to revalidate such entries anyway, so there's no reason to keep them around.

It is pretty cheap to release, say, the two oldest entries every time you try an access, provided they have not been touched in actimeo seconds.

If you want simple, a per-inode lru which is search linearly and discards old entries as you suggest would probably be just right. Leave the option of making a more sophisticated data structure if it really seems necessary.

NeilBrown

#15 lore raw
In reply to Steve Dickson
Quoted 10 lines · Steve Dickson
Quoted 8 lines · Peter Staubach
Quoted 7 lines
Quoted 2 lines

2. Use a radix tree per inode.

Using radix trees actual makes things much simpler... Good idea, imo.

Quoted 8 lines
Quoted 3 lines

It does seem like a good idea, although just using the uid is not sufficient to identify the correct access cache entry. The group and groups list must also be used. Can the radix tree implementation support this?

We could use (nfsi + uid) as the index... but its not clear what that would buys us... And the group and group list were never part of the cache in the first place.... is this something you feel needs to be added or am I just not understanding....

Yes, I believe that the entire user identification, uid, gid, groups list, needs to be used to identify the correct cache entry. An easy example of differing access rights, but with the same uid, is an application which is setgid.

I believe that the "key" to the cache entry should be the entire user identification that the NFS server sees and uses when calculating access rights. Using the uid as part of a hash key is okay and probably a good idea, but I don't think that the uid is sufficient to completely identify a specific cache entry.

Given this, then I suspect that the current access cache is broken...

Thanx...

ps

#16 lore raw
Quoted 29 lines · Peter Staubach
Quoted 16 lines · Steve Dickson
Quoted 5 lines · Peter Staubach
Quoted 5 lines
Quoted 2 lines

2. Use a radix tree per inode.

Quoted 8 lines
Quoted 2 lines

Using radix trees actual makes things much simpler... Good idea, imo.

It does seem like a good idea, although just using the uid is not sufficient
to identify the correct access cache entry. The group and groups list must
also be used. Can the radix tree implementation support this?

Quoted 4 lines

We could use (nfsi + uid) as the index... but its not clear what that would buys us... And the group and group list were never part of the cache in the first place.... is this something you feel needs to be added or am I just not understanding....

Yes, I believe that the entire user identification, uid, gid, groups list, needs to be used to identify the correct cache entry. An easy example of differing access rights, but with the same uid, is an application which is setgid.

Quoted 7 lines

I believe that the "key" to the cache entry should be the entire user identification that the NFS server sees and uses when calculating access rights. Using the uid as part of a hash key is okay and probably a good idea, but I don't think that the uid is sufficient to completely identify a specific cache entry.

Given this, then I suspect that the current access cache is broken...

No it is not: it uses the full RPC cred as the index.

Cheers,
Trond

#17 lore raw
Quoted 7 lines · Trond Myklebust
Quoted 7 lines

I believe that the "key" to the cache entry should be the entire user identification that the NFS server sees and uses when calculating access rights. Using the uid as part of a hash key is okay and probably a good idea, but I don't think that the uid is sufficient to completely identify a specific cache entry.

Quoted 6 lines
Quoted 3 lines

Given this, then I suspect that the current access cache is broken...

No it is not: it uses the full RPC cred as the index.

Cool!

ps

#18 lore raw
In reply to Trond Myklebust
Quoted 1 line · Trond Myklebust

No it is not: it uses the full RPC cred as the index.

I concur... I just wrote a test problem and things work as expected...

steved.

-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs