From 3cb989501c2688cacbb7dc4b0d353faf838f53a1 Mon Sep 17 00:00:00 2001 From: David Howells Date: Tue, 24 Sep 2013 10:35:17 +0100 Subject: Add a generic associative array implementation. Add a generic associative array implementation that can be used as the container for keyrings, thereby massively increasing the capacity available whilst also speeding up searching in keyrings that contain a lot of keys. This may also be useful in FS-Cache for tracking cookies. Documentation is added into Documentation/associative_array.txt Some of the properties of the implementation are: (1) Objects are opaque pointers. The implementation does not care where they point (if anywhere) or what they point to (if anything). [!] NOTE: Pointers to objects _must_ be zero in the two least significant bits. (2) Objects do not need to contain linkage blocks for use by the array. This permits an object to be located in multiple arrays simultaneously. Rather, the array is made up of metadata blocks that point to objects. (3) Objects are labelled as being one of two types (the type is a bool value). This information is stored in the array, but has no consequence to the array itself or its algorithms. (4) Objects require index keys to locate them within the array. (5) Index keys must be unique. Inserting an object with the same key as one already in the array will replace the old object. (6) Index keys can be of any length and can be of different lengths. (7) Index keys should encode the length early on, before any variation due to length is seen. (8) Index keys can include a hash to scatter objects throughout the array. (9) The array can iterated over. The objects will not necessarily come out in key order. (10) The array can be iterated whilst it is being modified, provided the RCU readlock is being held by the iterator. Note, however, under these circumstances, some objects may be seen more than once. If this is a problem, the iterator should lock against modification. Objects will not be missed, however, unless deleted. (11) Objects in the array can be looked up by means of their index key. (12) Objects can be looked up whilst the array is being modified, provided the RCU readlock is being held by the thread doing the look up. The implementation uses a tree of 16-pointer nodes internally that are indexed on each level by nibbles from the index key. To improve memory efficiency, shortcuts can be emplaced to skip over what would otherwise be a series of single-occupancy nodes. Further, nodes pack leaf object pointers into spare space in the node rather than making an extra branch until as such time an object needs to be added to a full node. Signed-off-by: David Howells --- include/linux/assoc_array.h | 92 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 92 insertions(+) create mode 100644 include/linux/assoc_array.h (limited to 'include/linux/assoc_array.h') diff --git a/include/linux/assoc_array.h b/include/linux/assoc_array.h new file mode 100644 index 000000000000..9a193b84238a --- /dev/null +++ b/include/linux/assoc_array.h @@ -0,0 +1,92 @@ +/* Generic associative array implementation. + * + * See Documentation/assoc_array.txt for information. + * + * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public Licence + * as published by the Free Software Foundation; either version + * 2 of the Licence, or (at your option) any later version. + */ + +#ifndef _LINUX_ASSOC_ARRAY_H +#define _LINUX_ASSOC_ARRAY_H + +#ifdef CONFIG_ASSOCIATIVE_ARRAY + +#include + +#define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */ + +/* + * Generic associative array. + */ +struct assoc_array { + struct assoc_array_ptr *root; /* The node at the root of the tree */ + unsigned long nr_leaves_on_tree; +}; + +/* + * Operations on objects and index keys for use by array manipulation routines. + */ +struct assoc_array_ops { + /* Method to get a chunk of an index key from caller-supplied data */ + unsigned long (*get_key_chunk)(const void *index_key, int level); + + /* Method to get a piece of an object's index key */ + unsigned long (*get_object_key_chunk)(const void *object, int level); + + /* 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) + */ + int (*diff_objects)(const void *a, const void *b); + + /* Method to free an object. */ + void (*free_object)(void *object); +}; + +/* + * Access and manipulation functions. + */ +struct assoc_array_edit; + +static inline void assoc_array_init(struct assoc_array *array) +{ + array->root = NULL; + array->nr_leaves_on_tree = 0; +} + +extern int assoc_array_iterate(const struct assoc_array *array, + int (*iterator)(const void *object, + void *iterator_data), + void *iterator_data); +extern void *assoc_array_find(const struct assoc_array *array, + const struct assoc_array_ops *ops, + const void *index_key); +extern void assoc_array_destroy(struct assoc_array *array, + const struct assoc_array_ops *ops); +extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array, + const struct assoc_array_ops *ops, + const void *index_key, + void *object); +extern void assoc_array_insert_set_object(struct assoc_array_edit *edit, + void *object); +extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array, + const struct assoc_array_ops *ops, + const void *index_key); +extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array, + const struct assoc_array_ops *ops); +extern void assoc_array_apply_edit(struct assoc_array_edit *edit); +extern void assoc_array_cancel_edit(struct assoc_array_edit *edit); +extern int assoc_array_gc(struct assoc_array *array, + const struct assoc_array_ops *ops, + bool (*iterator)(void *object, void *iterator_data), + void *iterator_data); + +#endif /* CONFIG_ASSOCIATIVE_ARRAY */ +#endif /* _LINUX_ASSOC_ARRAY_H */ -- 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 'include/linux/assoc_array.h') diff --git a/Documentation/assoc_array.txt b/Documentation/assoc_array.txt index f4faec0f66e4..2f2c6cdd73c0 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 9a193b84238a..a89df3be1686 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 17edeaf19180..1b6a44f1ec3e 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 0adbc77a59b9..3dd8445cd489 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