keys: Discard key spinlock and use RCU for key payload
Subsystems (3)
David Howells
maintainerPATCH 1/1 keys: Discard key spinlock and use RCU for key payload
The attached patch changes the key implementation in a number of ways:
(1) It removes the spinlock from the key structure.
(2) The key flags are now accessed using atomic bitops instead of write-locking the key spinlock and using C bitwise operators.
The three instantiation flags are dealt with with the construction semaphore held during the request_key/instantiate/negate sequence, thus rendering the spinlock superfluous.
The key flags are also now bit numbers not bit masks.
(3) The key payload is now accessed using RCU. This permits the recursive keyring search algorithm to be simplified greatly since no locks need be taken other than the usual RCU preemption disablement. Searching now does not require any locks or semaphores to be held; merely that the starting keyring be pinned.
(4) The keyring payload now includes an RCU head so that it can be disposed of by call_rcu(). This requires that the payload be copied on unlink to prevent introducing races in copy-down vs search-up.
(5) The user key payload is now a structure with the data following it. It includes an RCU head like the keyring payload and for the same reason. It also contains a data length because the data length in the key may be changed on another CPU whilst an RCU protected read is in progress on the payload. This would then see the supposed RCU payload and the on-key data length getting out of sync.
I'm tempted to drop the key's datalen entirely, except that it's used in conjunction with quota management and so is a little tricky to get rid of.
---
warthog>diffstat -p1 keys-rcu-2611.diff
Documentation/keys.txt | 5 include/linux/key-ui.h | 6 - include/linux/key.h | 25 ++-- security/keys/key.c | 95 +++++++--------- security/keys/keyctl.c | 23 +-- security/keys/keyring.c | 250 ++++++++++++++++++++++++++----------------- security/keys/proc.c | 21 ++- security/keys/process_keys.c | 16 -- security/keys/request_key.c | 32 ++--- security/keys/user_defined.c | 87 ++++++++++---- 10 files changed, 316 insertions(+), 244 deletions(-)
Documentation/keys.txt +3 -2
@@ -606,8 +606,9 @@ due to two different users opening the same file is left to the filesystem author to solve. -When accessing a key's payload data, the key->lock should be at least read -locked, or else the data may be changed by update during the access. +When accessing a key's payload data, RCU reading precautions on the payload +pointer should be taken, or else the data may be changed by update during the +access. (*) To search for a key, call:
include/linux/key.h +15 -10
@@ -18,7 +18,7 @@#include <linux/types.h> #include <linux/list.h> #include <linux/rbtree.h> -#include <linux/spinlock.h> +#include <linux/rcupdate.h> #include <asm/atomic.h> #ifdef __KERNEL__
@@ -77,7 +77,6 @@key_serial_t serial;/* key serial number */ struct rb_node serial_node;struct key_type *type;/* type of key */ -rwlock_t lock;/* examination vs change lock */ struct rw_semaphore sem;/* change vs change sem */ struct key_user *user;/* owner of this key */ time_t expiry;/* time at which key expires (or 0) */
@@ -85,14 +84,10 @@gid_t gid;key_perm_t perm;/* access permissions */ unsigned short quotalen;/* length added to quota */ -unsigned short datalen;/* payload data length */ -unsigned short flags;/* status flags (change with lock writelocked) */ -#define KEY_FLAG_INSTANTIATED 0x00000001/* set if key has been instantiated */ -#define KEY_FLAG_DEAD 0x00000002/* set if key type has been deleted */ -#define KEY_FLAG_REVOKED 0x00000004/* set if key had been revoked */ -#define KEY_FLAG_IN_QUOTA 0x00000008/* set if key consumes quota */ -#define KEY_FLAG_USER_CONSTRUCT 0x00000010/* set if key is being constructed in userspace */ -#define KEY_FLAG_NEGATIVE 0x00000020/* set if key is negative */ +unsigned short datalen;/* payload data length +* - may not match RCU dereferenced payload +* - payload should contain own length +*/ #ifdef KEY_DEBUGGING unsigned magic;
@@ -100,6 +95,14 @@#define KEY_DEBUG_MAGIC_X 0xf8e9dacbu#endif +unsigned long flags;/* status flags (change with bitops) */ +#define KEY_FLAG_INSTANTIATED 0/* set if key has been instantiated */ +#define KEY_FLAG_DEAD 1/* set if key type has been deleted */ +#define KEY_FLAG_REVOKED 2/* set if key had been revoked */ +#define KEY_FLAG_IN_QUOTA 3/* set if key consumes quota */ +#define KEY_FLAG_USER_CONSTRUCT 4/* set if key is being constructed in userspace */ +#define KEY_FLAG_NEGATIVE 5/* set if key is negative */ +/* the description string * - this is used to match a key against search criteria * - this should be a printable string
@@ -249,6 +252,8 @@extern struct key *key_lookup (key_serial_t id); +extern void keyring_replace_payload (struct key *key,void *replacement); +#define key_serial (key) ((key) ? (key)->serial : 0)/*
include/linux/key-ui.h +4 -2
@@ -31,8 +31,10 @@* subscribed */ struct keyring_list { -unsigned maxkeys;/* max keys this list can hold */ -unsigned nkeys;/* number of keys currently held */ +struct rcu_head rcu;/* RCU deletion hook */ +unsigned short maxkeys;/* max keys this list can hold */ +unsigned short nkeys;/* number of keys currently held */ +unsigned short delkey;/* key to be unlinked by RCU */ struct key *keys[0 ]; };
security/keys/key.c +42 -53
198 lines not on this page · raw message
security/keys/keyctl.c +7 -16
@@ -728,7 +728,6 @@/* make the changes with the locks held to prevent chown/chown races */ ret = -EACCES ;down_write (&key->sem); -write_lock (&key->lock);if (!capable (CAP_SYS_ADMIN )) {/* only the sysadmin can chown a key to some other UID */
@@ -755,7 +754,6 @@ ret =0 ; no_access: -write_unlock (&key->lock);up_write (&key->sem);key_put (key); error:
@@ -784,26 +782,19 @@ goto error; } -/* make the changes with the locks held to prevent chown/chmod -* races */ +/* make the changes with the locks held to prevent chown/chmod races */ ret = -EACCES ;down_write (&key->sem); -write_lock (&key->lock); -/* if we're not the sysadmin, we can only chmod a key that we -* own */ -if (!capable (CAP_SYS_ADMIN ) && key->uid != current->fsuid) - goto no_access; - -/* changing the permissions mask */ - key->perm = perm; - ret =0 ; +/* if we're not the sysadmin, we can only change a key that we own */ +if (capable (CAP_SYS_ADMIN ) || key->uid == current->fsuid) { + key->perm = perm; + ret =0 ; + } - no_access: -write_unlock (&key->lock);up_write (&key->sem);key_put (key); - error: +error:return ret; }/* end keyctl_setperm_key() */
security/keys/keyring.c +152 -98
537 lines not on this page · raw message
security/keys/proc.c +13 -8
@@ -140,7 +140,7 @@ now =current_kernel_time (); -read_lock (&key->lock); +rcu_read_lock ();/* come up with a suitable timeout value */ if (key->expiry ==0 ) {
@@ -164,14 +164,17 @@sprintf (xbuf,"%luw" , timo / (60 *60 *24 *7 )); } +#define showflag (KEY ,LETTER ,FLAG ) \ + (test_bit(FLAG, &(KEY)->flags) ? LETTER : '-') + seq_printf(m, "%08x %c%c%c%c%c%c %5d %4s %06x %5d %5d %-9.9s ", key->serial, - key->flags & KEY_FLAG_INSTANTIATED ? 'I' : '-', - key->flags & KEY_FLAG_REVOKED ? 'R' : '-', - key->flags & KEY_FLAG_DEAD ? 'D' : '-', - key->flags & KEY_FLAG_IN_QUOTA ? 'Q' : '-', - key->flags & KEY_FLAG_USER_CONSTRUCT ? 'U' : '-', - key->flags & KEY_FLAG_NEGATIVE ? 'N' : '-', + showflag(key, 'I', KEY_FLAG_INSTANTIATED), + showflag(key, 'R', KEY_FLAG_REVOKED), + showflag(key, 'D', KEY_FLAG_DEAD), + showflag(key, 'Q', KEY_FLAG_IN_QUOTA), + showflag(key, 'U', KEY_FLAG_USER_CONSTRUCT), + showflag(key, 'N', KEY_FLAG_NEGATIVE), atomic_read(&key->usage), xbuf, key->perm,
@@ -179,11 +182,13 @@ key->gid, key->type->name); +#undef showflag +if (key->type->describe) key->type->describe (key, m);seq_putc (m,'\n' ); -read_unlock (&key->lock); +rcu_read_unlock ();return 0 ;
security/keys/process_keys.c +3 -13
@@ -38,10 +38,9 @@ .serial = 2, .type = &key_type_keyring, .user = &root_key_user, - .lock = RW_LOCK_UNLOCKED, .sem = __RWSEM_INITIALIZER(root_user_keyring.sem), .perm = KEY_USR_ALL, - .flags = KEY_FLAG_INSTANTIATED, + .flags = 1 << KEY_FLAG_INSTANTIATED, .description ="_uid.0" , #ifdef KEY_DEBUGGING .magic = KEY_DEBUG_MAGIC,
@@ -54,10 +53,9 @@ .serial = 1, .type = &key_type_keyring, .user = &root_key_user, - .lock = RW_LOCK_UNLOCKED, .sem = __RWSEM_INITIALIZER(root_session_keyring.sem), .perm = KEY_USR_ALL, - .flags = KEY_FLAG_INSTANTIATED, + .flags = 1 << KEY_FLAG_INSTANTIATED, .description ="_uid_ses.0" , #ifdef KEY_DEBUGGING .magic = KEY_DEBUG_MAGIC,
@@ -317,18 +315,14 @@/* update the ownership of the process keyring */ if (tsk->process_keyring) {down_write (&tsk->process_keyring->sem); -write_lock (&tsk->process_keyring->lock); tsk->process_keyring->uid = tsk->fsuid; -write_unlock (&tsk->process_keyring->lock);up_write (&tsk->process_keyring->sem); }/* update the ownership of the thread keyring */ if (tsk->thread_keyring) {down_write (&tsk->thread_keyring->sem); -write_lock (&tsk->thread_keyring->lock); tsk->thread_keyring->uid = tsk->fsuid; -write_unlock (&tsk->thread_keyring->lock);up_write (&tsk->thread_keyring->sem); }
@@ -343,18 +337,14 @@/* update the ownership of the process keyring */ if (tsk->process_keyring) {down_write (&tsk->process_keyring->sem); -write_lock (&tsk->process_keyring->lock); tsk->process_keyring->gid = tsk->fsgid; -write_unlock (&tsk->process_keyring->lock);up_write (&tsk->process_keyring->sem); }/* update the ownership of the thread keyring */ if (tsk->thread_keyring) {down_write (&tsk->thread_keyring->sem); -write_lock (&tsk->thread_keyring->lock); tsk->thread_keyring->gid = tsk->fsgid; -write_unlock (&tsk->thread_keyring->lock);up_write (&tsk->thread_keyring->sem); }
@@ -565,7 +555,7 @@ } ret = -EIO ; -if (!partial && !(key->flags &KEY_FLAG_INSTANTIATED )) +if (!partial && !test_bit (KEY_FLAG_INSTANTIATED , &key->flags)) goto invalid_key; ret = -EACCES ;
security/keys/request_key.c +15 -17
@@ -94,7 +94,7 @@struct key_construction cons;struct timespec now;struct key *key; -int ret, negative; +int ret, negated;/* create a key and add it to the queue */ key = key_alloc(type, description,
@@ -102,9 +102,7 @@if (IS_ERR (key)) goto alloc_failed; -write_lock (&key->lock); - key->flags |=KEY_FLAG_USER_CONSTRUCT ; -write_unlock (&key->lock); +set_bit (KEY_FLAG_USER_CONSTRUCT , &key->flags); cons.key = key;list_add_tail (&cons.link, &key->user->consq);
@@ -119,7 +117,7 @@/* if the key wasn't instantiated, then we want to give an error */ ret = -ENOKEY ; -if (!(key->flags &KEY_FLAG_INSTANTIATED )) +if (!test_bit (KEY_FLAG_INSTANTIATED , &key->flags)) goto request_failed;down_write (&key_construction_sem);
@@ -128,7 +126,7 @@/* also give an error if the key was negatively instantiated */ check_not_negative: -if (key->flags &KEY_FLAG_NEGATIVE ) { +if (test_bit (KEY_FLAG_NEGATIVE , &key->flags)) {key_put (key); key =ERR_PTR (-ENOKEY ); }
@@ -141,24 +139,23 @@* - remove from construction queue * - mark the key as dead */ - negative =0 ; + negated =0 ;down_write (&key_construction_sem);list_del (&cons.link); -write_lock (&key->lock); - key->flags &= ~KEY_FLAG_USER_CONSTRUCT ; -/* check it didn't get instantiated between the check and the down */ -if (!(key->flags &KEY_FLAG_INSTANTIATED )) { - key->flags |=KEY_FLAG_INSTANTIATED |KEY_FLAG_NEGATIVE ; - negative =1 ; +if (!test_bit (KEY_FLAG_INSTANTIATED , &key->flags)) { +set_bit (KEY_FLAG_NEGATIVE , &key->flags); +set_bit (KEY_FLAG_INSTANTIATED , &key->flags); + negated =1 ; } -write_unlock (&key->lock); +clear_bit (KEY_FLAG_USER_CONSTRUCT , &key->flags); +up_write (&key_construction_sem); -if (!negative) +if (!negated) goto check_not_negative;/* surprisingly, the key got * instantiated */
@@ -228,7 +225,7 @@for (;;) {set_current_state (TASK_UNINTERRUPTIBLE ); -if (!(ckey->flags &KEY_FLAG_USER_CONSTRUCT )) +if (!test_bit (KEY_FLAG_USER_CONSTRUCT , &ckey->flags))break ;schedule (); }
@@ -317,7 +314,8 @@if (key) {/* check it's still accessible */ ret = -EKEYREVOKED ; -if (key->flags & (KEY_FLAG_REVOKED |KEY_FLAG_DEAD )) +if (test_bit (KEY_FLAG_REVOKED , &key->flags) || +test_bit (KEY_FLAG_DEAD , &key->flags)) goto error;/* check it hasn't expired */
security/keys/user_defined.c +62 -25
176 lines not on this page · raw message
Quoted 7 lines · David Howells
The attached patch changes the key implementation in a number of ways:
(1) It removes the spinlock from the key structure.
(2) The key flags are now accessed using atomic bitops instead of write-locking the key spinlock and using C bitwise operators.
I'd suggest against using __set_bit() for the initialization. Either use the proper set_bit() (which is slow, but at least consistent), or just initialize it with (1ul << KEY_FLAG_IN_QUOTA). __set_bit is generally slower than setting a value (it's pretty guaranteed not to be faster, and at least on x86 is clearly slower), so using it as an "optimization" is misguided.
RCU seems to fit the key model pretty well, but I still wonder whether the conceptual complexity is worth it. Was this done on a whim, or was there some real reason for it? I'd love for that to be documented while you're at it..
Linus
David Howells
maintainerQuoted 7 lines · Linus Torvalds
Quoted 6 lines
The attached patch changes the key implementation in a number of ways:
(1) It removes the spinlock from the key structure.
(2) The key flags are now accessed using atomic bitops instead of write-locking the key spinlock and using C bitwise operators.
Quoted 6 lines
I'd suggest against using
__set_bit()for the initialization. Either use the properset_bit()(which is slow, but at least consistent), or just initialize it with (1ul <<KEY_FLAG_IN_QUOTA).__set_bitis generally slower than setting a value (it's pretty guaranteed not to be faster, and at least on x86 is clearly slower), so using it as an "optimization" is misguided.
Yeah... fair enough.
Quoted 3 lines
RCU seems to fit the key model pretty well, but I still wonder whether the conceptual complexity is worth it. Was this done on a whim, or was there some real reason for it?
There are two parts to the reason:
(1) Keys are for the most part invariant. Whilst they can be modified if the type supports it, this should be uncommon. Except in the case of keyrings, that is, but they're a special case anyway.
(2) Anything that accesses a key's payload (which includes the keyring search algorithm) must hold the key's spinlock whilst it is looking at it, for as long as it is looking at it.
With RCU, this is no longer necessary. You just can't schedule until you've finished looking at it.
Given that for the most part keys don't change, it'd be very nice not to have to get a read lock on them. For something like NFS or AFS, the key will probably have to be accessed for every remote procedure call, for example; and a process's keyrings will have to be searched on every open call, assuming keys are associated with struct files or struct inodes.
The current locking model is quite complicated, and great care has to be taken to avoid recursive deadlocks; so in some ways the RCU model is actually simpler.
Quoted 1 line
I'd love for that to be documented while you're at it..
I need to update the key documentation to reflect the changes in locking, but the base kernel doesn't have the previous sets of doc changes; something I'd like to build on.
When you or Andrew have released such a kernel, I'll update the docs too.
David