From d54e58b7f01552b0eb7d445f4b58de4499ad5ea6 Mon Sep 17 00:00:00 2001 From: David Howells Date: Mon, 2 Dec 2013 11:24:18 +0000 Subject: KEYS: Fix the keyring hash function The keyring hash function (used by the associative array) is supposed to clear the bottommost nibble of the index key (where the hash value resides) for keyrings and make sure it is non-zero for non-keyrings. This is done to make keyrings cluster together on one branch of the tree separately to other keys. Unfortunately, the wrong mask is used, so only the bottom two bits are examined and cleared and not the whole bottom nibble. This means that keys and keyrings can still be successfully searched for under most circumstances as the hash is consistent in its miscalculation, but if a keyring's associative array bottom node gets filled up then approx 75% of the keyrings will not be put into the 0 branch. The consequence of this is that a key in a keyring linked to by another keyring, ie. keyring A -> keyring B -> key may not be found if the search starts at keyring A and then descends into keyring B because search_nested_keyrings() only searches up the 0 branch (as it "knows" all keyrings must be there and not elsewhere in the tree). The fix is to use the right mask. This can be tested with: r=`keyctl newring sandbox @s` for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done for ((i=0; i<=16; i++)); do keyctl add user a$i a %:ring$i; done for ((i=0; i<=16; i++)); do keyctl search $r user a$i; done This creates a sandbox keyring, then creates 17 keyrings therein (labelled ring0..ring16). This causes the root node of the sandbox's associative array to overflow and for the tree to have extra nodes inserted. Each keyring then is given a user key (labelled aN for ringN) for us to search for. We then search for the user keys we added, starting from the sandbox. If working correctly, it should return the same ordered list of key IDs as for...keyctl add... did. Without this patch, it reports ENOKEY "Required key not available" for some of the keys. Just which keys get this depends as the kernel pointer to the key type forms part of the hash function. Reported-by: Nalin Dahyabhai Signed-off-by: David Howells Tested-by: Stephen Gallagher --- security/keys/keyring.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'security/keys/keyring.c') diff --git a/security/keys/keyring.c b/security/keys/keyring.c index 69f0cb7bab7..0adbc77a59b 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -160,7 +160,7 @@ static u64 mult_64x32_and_fold(u64 x, u32 y) static unsigned long hash_key_type_and_desc(const struct keyring_index_key *index_key) { const unsigned level_shift = ASSOC_ARRAY_LEVEL_STEP; - const unsigned long level_mask = ASSOC_ARRAY_LEVEL_STEP_MASK; + const unsigned long fan_mask = ASSOC_ARRAY_FAN_MASK; const char *description = index_key->description; unsigned long hash, type; u32 piece; @@ -194,10 +194,10 @@ static unsigned long hash_key_type_and_desc(const struct keyring_index_key *inde * ordinary keys by making sure the lowest level segment in the hash is * zero for keyrings and non-zero otherwise. */ - if (index_key->type != &key_type_keyring && (hash & level_mask) == 0) + if (index_key->type != &key_type_keyring && (hash & fan_mask) == 0) return hash | (hash >> (ASSOC_ARRAY_KEY_CHUNK_SIZE - level_shift)) | 1; - if (index_key->type == &key_type_keyring && (hash & level_mask) != 0) - return (hash + (hash << level_shift)) & ~level_mask; + if (index_key->type == &key_type_keyring && (hash & fan_mask) != 0) + return (hash + (hash << level_shift)) & ~fan_mask; return hash; } -- cgit v1.2.3-70-g09d2 From 23fd78d76415729b338ff1802a0066b4a62f7fb8 Mon Sep 17 00:00:00 2001 From: David Howells Date: Mon, 2 Dec 2013 11:24:18 +0000 Subject: KEYS: Fix multiple key add into associative array If sufficient keys (or keyrings) are added into a keyring such that a node in the associative array's tree overflows (each node has a capacity N, currently 16) and such that all N+1 keys have the same index key segment for that level of the tree (the level'th nibble of the index key), then assoc_array_insert() calls ops->diff_objects() to indicate at which bit position the two index keys vary. However, __key_link_begin() passes a NULL object to assoc_array_insert() with the intention of supplying the correct pointer later before we commit the change. This means that keyring_diff_objects() is given a NULL pointer as one of its arguments which it does not expect. This results in an oops like the attached. With the previous patch to fix the keyring hash function, this can be forced much more easily by creating a keyring and only adding keyrings to it. Add any other sort of key and a different insertion path is taken - all 16+1 objects must want to cluster in the same node slot. This can be tested by: r=`keyctl newring sandbox @s` for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done This should work fine, but oopses when the 17th keyring is added. Since ops->diff_objects() is always called with the first pointer pointing to the object to be inserted (ie. the NULL pointer), we can fix the problem by changing the to-be-inserted object pointer to point to the index key passed into assoc_array_insert() instead. Whilst we're at it, we also switch the arguments so that they are the same as for ->compare_object(). BUG: unable to handle kernel NULL pointer dereference at 0000000000000088 IP: [] hash_key_type_and_desc+0x18/0xb0 ... RIP: 0010:[] hash_key_type_and_desc+0x18/0xb0 ... Call Trace: [] keyring_diff_objects+0x21/0xd2 [] assoc_array_insert+0x3b6/0x908 [] __key_link_begin+0x78/0xe5 [] key_create_or_update+0x17d/0x36a [] SyS_add_key+0x123/0x183 [] tracesys+0xdd/0xe2 Signed-off-by: David Howells Tested-by: Stephen Gallagher --- Documentation/assoc_array.txt | 6 +++--- include/linux/assoc_array.h | 6 +++--- lib/assoc_array.c | 4 ++-- security/keys/keyring.c | 7 +++---- 4 files changed, 11 insertions(+), 12 deletions(-) (limited to 'security/keys/keyring.c') diff --git a/Documentation/assoc_array.txt b/Documentation/assoc_array.txt index f4faec0f66e..2f2c6cdd73c 100644 --- a/Documentation/assoc_array.txt +++ b/Documentation/assoc_array.txt @@ -164,10 +164,10 @@ This points to a number of methods, all of which need to be provided: (4) Diff the index keys of two objects. - int (*diff_objects)(const void *a, const void *b); + int (*diff_objects)(const void *object, const void *index_key); - Return the bit position at which the index keys of two objects differ or - -1 if they are the same. + Return the bit position at which the index key of the specified object + differs from the given index key or -1 if they are the same. (5) Free an object. diff --git a/include/linux/assoc_array.h b/include/linux/assoc_array.h index 9a193b84238..a89df3be168 100644 --- a/include/linux/assoc_array.h +++ b/include/linux/assoc_array.h @@ -41,10 +41,10 @@ struct assoc_array_ops { /* Is this the object we're looking for? */ bool (*compare_object)(const void *object, const void *index_key); - /* How different are two objects, to a bit position in their keys? (or - * -1 if they're the same) + /* How different is an object from an index key, to a bit position in + * their keys? (or -1 if they're the same) */ - int (*diff_objects)(const void *a, const void *b); + int (*diff_objects)(const void *object, const void *index_key); /* Method to free an object. */ void (*free_object)(void *object); diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 17edeaf1918..1b6a44f1ec3 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -759,8 +759,8 @@ all_leaves_cluster_together: pr_devel("all leaves cluster together\n"); diff = INT_MAX; for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - int x = ops->diff_objects(assoc_array_ptr_to_leaf(edit->leaf), - assoc_array_ptr_to_leaf(node->slots[i])); + int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]), + index_key); if (x < diff) { BUG_ON(x < 0); diff = x; diff --git a/security/keys/keyring.c b/security/keys/keyring.c index 0adbc77a59b..3dd8445cd48 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -279,12 +279,11 @@ static bool keyring_compare_object(const void *object, const void *data) * Compare the index keys of a pair of objects and determine the bit position * at which they differ - if they differ. */ -static int keyring_diff_objects(const void *_a, const void *_b) +static int keyring_diff_objects(const void *object, const void *data) { - const struct key *key_a = keyring_ptr_to_key(_a); - const struct key *key_b = keyring_ptr_to_key(_b); + const struct key *key_a = keyring_ptr_to_key(object); const struct keyring_index_key *a = &key_a->index_key; - const struct keyring_index_key *b = &key_b->index_key; + const struct keyring_index_key *b = data; unsigned long seg_a, seg_b; int level, i; -- cgit v1.2.3-70-g09d2 From 9c5e45df215b4788f7a41c983ce862d08a083c2d Mon Sep 17 00:00:00 2001 From: David Howells Date: Mon, 2 Dec 2013 11:24:19 +0000 Subject: KEYS: Fix searching of nested keyrings If a keyring contains more than 16 keyrings (the capacity of a single node in the associative array) then those keyrings are split over multiple nodes arranged as a tree. If search_nested_keyrings() is called to search the keyring then it will attempt to manually walk over just the 0 branch of the associative array tree where all the keyring links are stored. This works provided the key is found before the algorithm steps from one node containing keyrings to a child node or if there are sufficiently few keyring links that the keyrings are all in one node. However, if the algorithm does need to step from a node to a child node, it doesn't change the node pointer unless a shortcut also gets transited. This means that the algorithm will keep scanning the same node over and over again without terminating and without returning. To fix this, move the internal-pointer-to-node translation from inside the shortcut transit handler so that it applies it to node arrival as well. This can be tested by: r=`keyctl newring sandbox @s` for ((i=0; i<=16; i++)); do keyctl newring ring$i $r; done for ((i=0; i<=16; i++)); do keyctl add user a$i a %:ring$i; done for ((i=0; i<=16; i++)); do keyctl search $r user a$i; done for ((i=17; i<=20; i++)); do keyctl search $r user a$i; done The searches should all complete successfully (or with an error for 17-20), but instead one or more of them will hang. Signed-off-by: David Howells Tested-by: Stephen Gallagher --- security/keys/keyring.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'security/keys/keyring.c') diff --git a/security/keys/keyring.c b/security/keys/keyring.c index 3dd8445cd48..d46cbc5e335 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -690,8 +690,8 @@ descend_to_node: smp_read_barrier_depends(); ptr = ACCESS_ONCE(shortcut->next_node); BUG_ON(!assoc_array_ptr_is_node(ptr)); - node = assoc_array_ptr_to_node(ptr); } + node = assoc_array_ptr_to_node(ptr); begin_node: kdebug("begin_node"); -- cgit v1.2.3-70-g09d2