From 76d8aeabfeb1c42641a81c44280177b9a08670d8 Mon Sep 17 00:00:00 2001 From: David Howells Date: Thu, 23 Jun 2005 22:00:49 -0700 Subject: [PATCH] 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. (6) Update the keys documentation. Signed-Off-By: David Howells Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- security/keys/keyring.c | 245 +++++++++++++++++++++++++++++------------------- 1 file changed, 148 insertions(+), 97 deletions(-) (limited to 'security/keys/keyring.c') diff --git a/security/keys/keyring.c b/security/keys/keyring.c index e2ab4f8e7481..c9a5de197487 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -132,10 +132,17 @@ static int keyring_duplicate(struct key *keyring, const struct key *source) (PAGE_SIZE - sizeof(*klist)) / sizeof(struct key); ret = 0; - sklist = source->payload.subscriptions; - if (sklist && sklist->nkeys > 0) { + /* find out how many keys are currently linked */ + rcu_read_lock(); + sklist = rcu_dereference(source->payload.subscriptions); + max = 0; + if (sklist) max = sklist->nkeys; + rcu_read_unlock(); + + /* allocate a new payload and stuff load with key links */ + if (max > 0) { BUG_ON(max > limit); max = (max + 3) & ~3; @@ -148,6 +155,10 @@ static int keyring_duplicate(struct key *keyring, const struct key *source) if (!klist) goto error; + /* set links */ + rcu_read_lock(); + sklist = rcu_dereference(source->payload.subscriptions); + klist->maxkeys = max; klist->nkeys = sklist->nkeys; memcpy(klist->keys, @@ -157,7 +168,9 @@ static int keyring_duplicate(struct key *keyring, const struct key *source) for (loop = klist->nkeys - 1; loop >= 0; loop--) atomic_inc(&klist->keys[loop]->usage); - keyring->payload.subscriptions = klist; + rcu_read_unlock(); + + rcu_assign_pointer(keyring->payload.subscriptions, klist); ret = 0; } @@ -192,7 +205,7 @@ static void keyring_destroy(struct key *keyring) write_unlock(&keyring_name_lock); } - klist = keyring->payload.subscriptions; + klist = rcu_dereference(keyring->payload.subscriptions); if (klist) { for (loop = klist->nkeys - 1; loop >= 0; loop--) key_put(klist->keys[loop]); @@ -216,17 +229,20 @@ static void keyring_describe(const struct key *keyring, struct seq_file *m) seq_puts(m, "[anon]"); } - klist = keyring->payload.subscriptions; + rcu_read_lock(); + klist = rcu_dereference(keyring->payload.subscriptions); if (klist) seq_printf(m, ": %u/%u", klist->nkeys, klist->maxkeys); else seq_puts(m, ": empty"); + rcu_read_unlock(); } /* end keyring_describe() */ /*****************************************************************************/ /* * read a list of key IDs from the keyring's contents + * - the keyring's semaphore is read-locked */ static long keyring_read(const struct key *keyring, char __user *buffer, size_t buflen) @@ -237,7 +253,7 @@ static long keyring_read(const struct key *keyring, int loop, ret; ret = 0; - klist = keyring->payload.subscriptions; + klist = rcu_dereference(keyring->payload.subscriptions); if (klist) { /* calculate how much data we could return */ @@ -320,7 +336,7 @@ struct key *keyring_search_aux(struct key *keyring, key_match_func_t match) { struct { - struct key *keyring; + struct keyring_list *keylist; int kix; } stack[KEYRING_SEARCH_MAX_DEPTH]; @@ -328,10 +344,12 @@ struct key *keyring_search_aux(struct key *keyring, struct timespec now; struct key *key; long err; - int sp, psp, kix; + int sp, kix; key_check(keyring); + rcu_read_lock(); + /* top keyring must have search permission to begin the search */ key = ERR_PTR(-EACCES); if (!key_permission(keyring, KEY_SEARCH)) @@ -347,11 +365,10 @@ struct key *keyring_search_aux(struct key *keyring, /* start processing a new keyring */ descend: - read_lock(&keyring->lock); - if (keyring->flags & KEY_FLAG_REVOKED) + if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) goto not_this_keyring; - keylist = keyring->payload.subscriptions; + keylist = rcu_dereference(keyring->payload.subscriptions); if (!keylist) goto not_this_keyring; @@ -364,7 +381,7 @@ struct key *keyring_search_aux(struct key *keyring, continue; /* skip revoked keys and expired keys */ - if (key->flags & KEY_FLAG_REVOKED) + if (test_bit(KEY_FLAG_REVOKED, &key->flags)) continue; if (key->expiry && now.tv_sec >= key->expiry) @@ -379,7 +396,7 @@ struct key *keyring_search_aux(struct key *keyring, continue; /* we set a different error code if we find a negative key */ - if (key->flags & KEY_FLAG_NEGATIVE) { + if (test_bit(KEY_FLAG_NEGATIVE, &key->flags)) { err = -ENOKEY; continue; } @@ -390,48 +407,37 @@ struct key *keyring_search_aux(struct key *keyring, /* search through the keyrings nested in this one */ kix = 0; ascend: - while (kix < keylist->nkeys) { + for (; kix < keylist->nkeys; kix++) { key = keylist->keys[kix]; if (key->type != &key_type_keyring) - goto next; + continue; /* recursively search nested keyrings * - only search keyrings for which we have search permission */ if (sp >= KEYRING_SEARCH_MAX_DEPTH) - goto next; + continue; if (!key_permission(key, KEY_SEARCH)) - goto next; - - /* evade loops in the keyring tree */ - for (psp = 0; psp < sp; psp++) - if (stack[psp].keyring == keyring) - goto next; + continue; /* stack the current position */ - stack[sp].keyring = keyring; + stack[sp].keylist = keylist; stack[sp].kix = kix; sp++; /* begin again with the new keyring */ keyring = key; goto descend; - - next: - kix++; } /* the keyring we're looking at was disqualified or didn't contain a * matching key */ not_this_keyring: - read_unlock(&keyring->lock); - if (sp > 0) { /* resume the processing of a keyring higher up in the tree */ sp--; - keyring = stack[sp].keyring; - keylist = keyring->payload.subscriptions; + keylist = stack[sp].keylist; kix = stack[sp].kix + 1; goto ascend; } @@ -442,16 +448,9 @@ struct key *keyring_search_aux(struct key *keyring, /* we found a viable match */ found: atomic_inc(&key->usage); - read_unlock(&keyring->lock); - - /* unwind the keyring stack */ - while (sp > 0) { - sp--; - read_unlock(&stack[sp].keyring->lock); - } - key_check(key); error: + rcu_read_unlock(); return key; } /* end keyring_search_aux() */ @@ -489,7 +488,9 @@ struct key *__keyring_search_one(struct key *keyring, struct key *key; int loop; - klist = keyring->payload.subscriptions; + rcu_read_lock(); + + klist = rcu_dereference(keyring->payload.subscriptions); if (klist) { for (loop = 0; loop < klist->nkeys; loop++) { key = klist->keys[loop]; @@ -497,7 +498,7 @@ struct key *__keyring_search_one(struct key *keyring, if (key->type == ktype && key->type->match(key, description) && key_permission(key, perm) && - !(key->flags & KEY_FLAG_REVOKED) + !test_bit(KEY_FLAG_REVOKED, &key->flags) ) goto found; } @@ -509,6 +510,7 @@ struct key *__keyring_search_one(struct key *keyring, found: atomic_inc(&key->usage); error: + rcu_read_unlock(); return key; } /* end __keyring_search_one() */ @@ -540,7 +542,7 @@ struct key *find_keyring_by_name(const char *name, key_serial_t bound) &keyring_name_hash[bucket], type_data.link ) { - if (keyring->flags & KEY_FLAG_REVOKED) + if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) continue; if (strcmp(keyring->description, name) != 0) @@ -579,7 +581,7 @@ struct key *find_keyring_by_name(const char *name, key_serial_t bound) static int keyring_detect_cycle(struct key *A, struct key *B) { struct { - struct key *subtree; + struct keyring_list *keylist; int kix; } stack[KEYRING_SEARCH_MAX_DEPTH]; @@ -587,20 +589,21 @@ static int keyring_detect_cycle(struct key *A, struct key *B) struct key *subtree, *key; int sp, kix, ret; + rcu_read_lock(); + ret = -EDEADLK; if (A == B) - goto error; + goto cycle_detected; subtree = B; sp = 0; /* start processing a new keyring */ descend: - read_lock(&subtree->lock); - if (subtree->flags & KEY_FLAG_REVOKED) + if (test_bit(KEY_FLAG_REVOKED, &subtree->flags)) goto not_this_keyring; - keylist = subtree->payload.subscriptions; + keylist = rcu_dereference(subtree->payload.subscriptions); if (!keylist) goto not_this_keyring; kix = 0; @@ -619,7 +622,7 @@ static int keyring_detect_cycle(struct key *A, struct key *B) goto too_deep; /* stack the current position */ - stack[sp].subtree = subtree; + stack[sp].keylist = keylist; stack[sp].kix = kix; sp++; @@ -632,13 +635,10 @@ static int keyring_detect_cycle(struct key *A, struct key *B) /* the keyring we're looking at was disqualified or didn't contain a * matching key */ not_this_keyring: - read_unlock(&subtree->lock); - if (sp > 0) { /* resume the checking of a keyring higher up in the tree */ sp--; - subtree = stack[sp].subtree; - keylist = subtree->payload.subscriptions; + keylist = stack[sp].keylist; kix = stack[sp].kix + 1; goto ascend; } @@ -646,30 +646,36 @@ static int keyring_detect_cycle(struct key *A, struct key *B) ret = 0; /* no cycles detected */ error: + rcu_read_unlock(); return ret; too_deep: ret = -ELOOP; - goto error_unwind; + goto error; + cycle_detected: ret = -EDEADLK; - error_unwind: - read_unlock(&subtree->lock); - - /* unwind the keyring stack */ - while (sp > 0) { - sp--; - read_unlock(&stack[sp].subtree->lock); - } - goto error; } /* end keyring_detect_cycle() */ +/*****************************************************************************/ +/* + * dispose of a keyring list after the RCU grace period + */ +static void keyring_link_rcu_disposal(struct rcu_head *rcu) +{ + struct keyring_list *klist = + container_of(rcu, struct keyring_list, rcu); + + kfree(klist); + +} /* end keyring_link_rcu_disposal() */ + /*****************************************************************************/ /* * link a key into to a keyring - * - must be called with the keyring's semaphore held + * - must be called with the keyring's semaphore write-locked */ int __key_link(struct key *keyring, struct key *key) { @@ -679,7 +685,7 @@ int __key_link(struct key *keyring, struct key *key) int ret; ret = -EKEYREVOKED; - if (keyring->flags & KEY_FLAG_REVOKED) + if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) goto error; ret = -ENOTDIR; @@ -710,9 +716,10 @@ int __key_link(struct key *keyring, struct key *key) /* there's sufficient slack space to add directly */ atomic_inc(&key->usage); - write_lock(&keyring->lock); - klist->keys[klist->nkeys++] = key; - write_unlock(&keyring->lock); + klist->keys[klist->nkeys] = key; + smp_wmb(); + klist->nkeys++; + smp_wmb(); ret = 0; } @@ -723,6 +730,8 @@ int __key_link(struct key *keyring, struct key *key) max += klist->maxkeys; ret = -ENFILE; + if (max > 65535) + goto error3; size = sizeof(*klist) + sizeof(*key) * max; if (size > PAGE_SIZE) goto error3; @@ -743,14 +752,13 @@ int __key_link(struct key *keyring, struct key *key) /* add the key into the new space */ atomic_inc(&key->usage); - - write_lock(&keyring->lock); - keyring->payload.subscriptions = nklist; nklist->keys[nklist->nkeys++] = key; - write_unlock(&keyring->lock); + + rcu_assign_pointer(keyring->payload.subscriptions, nklist); /* dispose of the old keyring list */ - kfree(klist); + if (klist) + call_rcu(&klist->rcu, keyring_link_rcu_disposal); ret = 0; } @@ -789,13 +797,28 @@ int key_link(struct key *keyring, struct key *key) EXPORT_SYMBOL(key_link); +/*****************************************************************************/ +/* + * dispose of a keyring list after the RCU grace period, freeing the unlinked + * key + */ +static void keyring_unlink_rcu_disposal(struct rcu_head *rcu) +{ + struct keyring_list *klist = + container_of(rcu, struct keyring_list, rcu); + + key_put(klist->keys[klist->delkey]); + kfree(klist); + +} /* end keyring_unlink_rcu_disposal() */ + /*****************************************************************************/ /* * unlink the first link to a key from a keyring */ int key_unlink(struct key *keyring, struct key *key) { - struct keyring_list *klist; + struct keyring_list *klist, *nklist; int loop, ret; key_check(keyring); @@ -819,36 +842,69 @@ int key_unlink(struct key *keyring, struct key *key) ret = -ENOENT; goto error; - key_is_present: +key_is_present: + /* we need to copy the key list for RCU purposes */ + nklist = kmalloc(sizeof(*klist) + sizeof(*key) * klist->maxkeys, + GFP_KERNEL); + if (!nklist) + goto nomem; + nklist->maxkeys = klist->maxkeys; + nklist->nkeys = klist->nkeys - 1; + + if (loop > 0) + memcpy(&nklist->keys[0], + &klist->keys[0], + loop * sizeof(klist->keys[0])); + + if (loop < nklist->nkeys) + memcpy(&nklist->keys[loop], + &klist->keys[loop + 1], + (nklist->nkeys - loop) * sizeof(klist->keys[0])); + /* adjust the user's quota */ key_payload_reserve(keyring, keyring->datalen - KEYQUOTA_LINK_BYTES); - /* shuffle down the key pointers - * - it might be worth shrinking the allocated memory, but that runs - * the risk of ENOMEM as we would have to copy - */ - write_lock(&keyring->lock); + rcu_assign_pointer(keyring->payload.subscriptions, nklist); - klist->nkeys--; - if (loop < klist->nkeys) - memcpy(&klist->keys[loop], - &klist->keys[loop + 1], - (klist->nkeys - loop) * sizeof(struct key *)); + up_write(&keyring->sem); - write_unlock(&keyring->lock); + /* schedule for later cleanup */ + klist->delkey = loop; + call_rcu(&klist->rcu, keyring_unlink_rcu_disposal); - up_write(&keyring->sem); - key_put(key); ret = 0; - error: +error: return ret; +nomem: + ret = -ENOMEM; + up_write(&keyring->sem); + goto error; } /* end key_unlink() */ EXPORT_SYMBOL(key_unlink); +/*****************************************************************************/ +/* + * dispose of a keyring list after the RCU grace period, releasing the keys it + * links to + */ +static void keyring_clear_rcu_disposal(struct rcu_head *rcu) +{ + struct keyring_list *klist; + int loop; + + klist = container_of(rcu, struct keyring_list, rcu); + + for (loop = klist->nkeys - 1; loop >= 0; loop--) + key_put(klist->keys[loop]); + + kfree(klist); + +} /* end keyring_clear_rcu_disposal() */ + /*****************************************************************************/ /* * clear the specified process keyring @@ -857,7 +913,7 @@ EXPORT_SYMBOL(key_unlink); int keyring_clear(struct key *keyring) { struct keyring_list *klist; - int loop, ret; + int ret; ret = -ENOTDIR; if (keyring->type == &key_type_keyring) { @@ -870,20 +926,15 @@ int keyring_clear(struct key *keyring) key_payload_reserve(keyring, sizeof(struct keyring_list)); - write_lock(&keyring->lock); - keyring->payload.subscriptions = NULL; - write_unlock(&keyring->lock); + rcu_assign_pointer(keyring->payload.subscriptions, + NULL); } up_write(&keyring->sem); /* free the keys after the locks have been dropped */ - if (klist) { - for (loop = klist->nkeys - 1; loop >= 0; loop--) - key_put(klist->keys[loop]); - - kfree(klist); - } + if (klist) + call_rcu(&klist->rcu, keyring_clear_rcu_disposal); ret = 0; } -- cgit v1.2.1 From 3e30148c3d524a9c1c63ca28261bc24c457eb07a Mon Sep 17 00:00:00 2001 From: David Howells Date: Thu, 23 Jun 2005 22:00:56 -0700 Subject: [PATCH] Keys: Make request-key create an authorisation key The attached patch makes the following changes: (1) There's a new special key type called ".request_key_auth". This is an authorisation key for when one process requests a key and another process is started to construct it. This type of key cannot be created by the user; nor can it be requested by kernel services. Authorisation keys hold two references: (a) Each refers to a key being constructed. When the key being constructed is instantiated the authorisation key is revoked, rendering it of no further use. (b) The "authorising process". This is either: (i) the process that called request_key(), or: (ii) if the process that called request_key() itself had an authorisation key in its session keyring, then the authorising process referred to by that authorisation key will also be referred to by the new authorisation key. This means that the process that initiated a chain of key requests will authorise the lot of them, and will, by default, wind up with the keys obtained from them in its keyrings. (2) request_key() creates an authorisation key which is then passed to /sbin/request-key in as part of a new session keyring. (3) When request_key() is searching for a key to hand back to the caller, if it comes across an authorisation key in the session keyring of the calling process, it will also search the keyrings of the process specified therein and it will use the specified process's credentials (fsuid, fsgid, groups) to do that rather than the calling process's credentials. This allows a process started by /sbin/request-key to find keys belonging to the authorising process. (4) A key can be read, even if the process executing KEYCTL_READ doesn't have direct read or search permission if that key is contained within the keyrings of a process specified by an authorisation key found within the calling process's session keyring, and is searchable using the credentials of the authorising process. This allows a process started by /sbin/request-key to read keys belonging to the authorising process. (5) The magic KEY_SPEC_*_KEYRING key IDs when passed to KEYCTL_INSTANTIATE or KEYCTL_NEGATE will specify a keyring of the authorising process, rather than the process doing the instantiation. (6) One of the process keyrings can be nominated as the default to which request_key() should attach new keys if not otherwise specified. This is done with KEYCTL_SET_REQKEY_KEYRING and one of the KEY_REQKEY_DEFL_* constants. The current setting can also be read using this call. (7) request_key() is partially interruptible. If it is waiting for another process to finish constructing a key, it can be interrupted. This permits a request-key cycle to be broken without recourse to rebooting. Signed-Off-By: David Howells Signed-Off-By: Benoit Boissinot Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- security/keys/keyring.c | 67 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 59 insertions(+), 8 deletions(-) (limited to 'security/keys/keyring.c') diff --git a/security/keys/keyring.c b/security/keys/keyring.c index c9a5de197487..90a551e4da66 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -1,6 +1,6 @@ /* keyring.c: keyring handling * - * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. + * Copyright (C) 2004-5 Red Hat, Inc. All Rights Reserved. * Written by David Howells (dhowells@redhat.com) * * This program is free software; you can redistribute it and/or @@ -308,7 +308,7 @@ struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid, uid, gid, KEY_USR_ALL, not_in_quota); if (!IS_ERR(keyring)) { - ret = key_instantiate_and_link(keyring, NULL, 0, dest); + ret = key_instantiate_and_link(keyring, NULL, 0, dest, NULL); if (ret < 0) { key_put(keyring); keyring = ERR_PTR(ret); @@ -326,11 +326,12 @@ struct key *keyring_alloc(const char *description, uid_t uid, gid_t gid, * - we only find keys on which we have search permission * - we use the supplied match function to see if the description (or other * feature of interest) matches - * - we readlock the keyrings as we search down the tree + * - we rely on RCU to prevent the keyring lists from disappearing on us * - we return -EAGAIN if we didn't find any matching key * - we return -ENOKEY if we only found negative matching keys */ struct key *keyring_search_aux(struct key *keyring, + struct task_struct *context, struct key_type *type, const void *description, key_match_func_t match) @@ -352,7 +353,7 @@ struct key *keyring_search_aux(struct key *keyring, /* top keyring must have search permission to begin the search */ key = ERR_PTR(-EACCES); - if (!key_permission(keyring, KEY_SEARCH)) + if (!key_task_permission(keyring, context, KEY_SEARCH)) goto error; key = ERR_PTR(-ENOTDIR); @@ -392,7 +393,7 @@ struct key *keyring_search_aux(struct key *keyring, continue; /* key must have search permissions */ - if (!key_permission(key, KEY_SEARCH)) + if (!key_task_permission(key, context, KEY_SEARCH)) continue; /* we set a different error code if we find a negative key */ @@ -418,7 +419,7 @@ struct key *keyring_search_aux(struct key *keyring, if (sp >= KEYRING_SEARCH_MAX_DEPTH) continue; - if (!key_permission(key, KEY_SEARCH)) + if (!key_task_permission(key, context, KEY_SEARCH)) continue; /* stack the current position */ @@ -468,7 +469,11 @@ struct key *keyring_search(struct key *keyring, struct key_type *type, const char *description) { - return keyring_search_aux(keyring, type, description, type->match); + if (!type->match) + return ERR_PTR(-ENOKEY); + + return keyring_search_aux(keyring, current, + type, description, type->match); } /* end keyring_search() */ @@ -496,7 +501,8 @@ struct key *__keyring_search_one(struct key *keyring, key = klist->keys[loop]; if (key->type == ktype && - key->type->match(key, description) && + (!key->type->match || + key->type->match(key, description)) && key_permission(key, perm) && !test_bit(KEY_FLAG_REVOKED, &key->flags) ) @@ -515,6 +521,51 @@ struct key *__keyring_search_one(struct key *keyring, } /* end __keyring_search_one() */ +/*****************************************************************************/ +/* + * search for an instantiation authorisation key matching a target key + * - the RCU read lock must be held by the caller + * - a target_id of zero specifies any valid token + */ +struct key *keyring_search_instkey(struct key *keyring, + key_serial_t target_id) +{ + struct request_key_auth *rka; + struct keyring_list *klist; + struct key *instkey; + int loop; + + klist = rcu_dereference(keyring->payload.subscriptions); + if (klist) { + for (loop = 0; loop < klist->nkeys; loop++) { + instkey = klist->keys[loop]; + + if (instkey->type != &key_type_request_key_auth) + continue; + + rka = instkey->payload.data; + if (target_id && rka->target_key->serial != target_id) + continue; + + /* the auth key is revoked during instantiation */ + if (!test_bit(KEY_FLAG_REVOKED, &instkey->flags)) + goto found; + + instkey = ERR_PTR(-EKEYREVOKED); + goto error; + } + } + + instkey = ERR_PTR(-EACCES); + goto error; + +found: + atomic_inc(&instkey->usage); +error: + return instkey; + +} /* end keyring_search_instkey() */ + /*****************************************************************************/ /* * find a keyring with the specified name -- cgit v1.2.1