Assoc_array: Drop leaf-type concept

Commit Message

David Howells July 18, 2013, 1:18 p.m. UTC

Hi Joe, George,

How about the attached changes?  I've dropped support for multiple leaf types
in the assoc_array API (leaving that to the caller).  The array still uses bit
0 of the object pointer to mark an internal metadata pointer if set (and then
uses bit 1 to specify the subtype internally).

It makes assoc_array.o about 250 bytes smaller too, whereas keyrings.o grows
by about 150 - so a net gain.

David
---
 Documentation/assoc_array.txt    |   45 +++++++------------
 include/linux/assoc_array.h      |   10 +---
 include/linux/assoc_array_priv.h |   85 ++++++++++++++++++++++--------------
 lib/assoc_array.c                |   87 +++++++++++++++++-------------------
 security/keys/gc.c               |    2 
 security/keys/internal.h         |    2 
 security/keys/keyring.c          |   92 +++++++++++++++++++++++++--------------
 7 files changed, 179 insertions(+), 144 deletions(-)

--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Comments

George Spelvin July 18, 2013, 9:31 p.m. UTC | #1

Looks cleaner.

The larger issues that bother me:

1) The fact that the abstract daya type "index key" provides access to
   a byte string "index key" is a bit confusing.  I'd describe it as
   follows:  (Based on my current understanding.)


   Each object has an associated "index key" that is used for lookup.
   The index key is a string of bits which is stored "inside" the object,
   however all access to it is done through method functions, so it is
   not necessary to explicitly store it anywhere.

   For example, it is possible to have the leading portion of the
   index_key be a hash of the remainder.

   Index keys may be variable-length, but must be self-delimiting.
   Specifically, two different index keys must differ at some bit position
   before the end of the shorter of the two.

   Some index key methods take an isolated "const void *index_key"
   argument, while others take an object pointer.

2) The code does not look 32-bit safe.  In particular, keyring_get_key_chunk
   assumes the hash is BITS_PER_LONG long, but keyring_diff_objects 
   assumes it's 8*8 bits...

3) I presume you looked at wider tries like Judy arrays and found that
   a fan-out of 16 was better?

4) There are 3/7 unused bytes in an assoc_array_node, after parent_slot.
   Would it be worth storing 16/48 bits of index key and 3/4 bits of
   number of levels to skip per assoc_array_node?
   Since parent_slot is actually only 4 bits, you could store 4 bits
   of nubmer of levels and 56 bits (up to 14 levels, plus the one
   from the famout) of index key.

   With 32-way fanout, you could fit 5 bits of parent index, 25/55 bits of
   index key, and encode the number of levels to skip (0-5/11) more carefully.

5) The big question: Why not use a hash table?  That's what people
   usually expect when you say "associative array".  It would be simpler
   and faster.

   RCU-safe resizeable hash tables are tricky, but a solved problem,
   There are universal hashing techniques for preventing hash collision
   attacks.  
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

David Howells July 19, 2013, 2:37 p.m. UTC | #2

George Spelvin <[e-mail]> wrote:

> Looks cleaner.

Thanks!

> The larger issues that bother me:
> 
> 1) The fact that the abstract daya type "index key" provides access to
>    a byte string "index key" is a bit confusing.  I'd describe it as
>    follows:  (Based on my current understanding.)
> 
> 
>    Each object has an associated "index key" that is used for lookup.
>    The index key is a string of bits which is stored "inside" the object,
>    however all access to it is done through method functions, so it is
>    not necessary to explicitly store it anywhere.
> 
>    For example, it is possible to have the leading portion of the
>    index_key be a hash of the remainder.
> 
>    Index keys may be variable-length, but must be self-delimiting.
>    Specifically, two different index keys must differ at some bit position
>    before the end of the shorter of the two.

This is a reasonable summary - but there's no requirement for the index key to
be a string of bits in its native form.  It's just that it must be presented to
my routines as a bit string.  It doesn't even need to be stored inside the
object - though I did note you quoted that.  Maybe "associated with"?

>    Some index key methods take an isolated "const void *index_key"
>    argument, while others take an object pointer.

Indeed.  Sometimes I have an explicit index key available (look up, for
example) and sometimes I only have the object available (determining whether a
key I'm inserting matches a key I already have when debating shortcut
creation).

The reason assoc_array_insert() takes an explicit index key _and_ an object
(which provides an implicit index key) is that it permits me to use
assoc_array_walk() - which only wants the the explicit index key.

> 2) The code does not look 32-bit safe.  In particular, keyring_get_key_chunk
>    assumes the hash is BITS_PER_LONG long, but keyring_diff_objects 
>    assumes it's 8*8 bits...

Good point.  Fixed.

> 3) I presume you looked at wider tries like Judy arrays and found that
>    a fan-out of 16 was better?

I have not looked at Judy arrays, but I have looked at the other stuff Linux
has available and some stuff beyond that.

To select the algorithm, I started off with a list of criteria:

 (1) It must not be necessary to modify an object to be able to include it in
     the container.  That means no list_head, rb_node or similar emplacement
     within the object.

 (2) Can't use nodes > PAGE_SIZE.  Preferably they'd be much smaller.

 (3) Having lots of blocks that have one object pointer and two or three
     metadata pointers is bad.  I'd prefer a much higher object-to-meta pointer
     ratio.

 (4) All algorithms must be non-recursive functions as stack space is at a
     premium.  Also can't rely on being able to allocate extra space during R/O
     accesses.

 (5) Must be possible for RCU R/O accesses to be concurrent with modification.

 (6) Reading must be non-sleeping (so no use of a semaphore for reading).

 (7) Concurrent modification is not a requirement.

 (8) Needs to be primarily optimised for direct walking to a node by index key.

 (9) Needs reasonable iteration performance too.

(10) Modifications shouldn't have to replace a lot of internal blocks.

I think the biggest pain is actually the non-recursive algorithm criterion.

I have actually used this container before for a disk-based tree.


Anyway, with regards to the size of the fan out, I wanted a compromise between
having slack available so as not to get too deep a tree too quickly whilst not
have too much slack space - after all, kernel memory is not easily reclaimable.

However, the biggest factor was that I decided to grab the index key a chunk at
a time.  The logical choice for chunk size was register size (ie. unsigned
long) and ideally there would be no wastage in the chunk I got back.  This
means a fan out that divides exactly in to 2^32 and 2^64.  From that point of
view, the choices are 2^(N^2).  A fan out of 16 seems nice as it's a nibble or
one hex digit.

Another factor was that I wanted, if possible, to have keyring objects to
cluster together to make iterating over them easier (and I know when to stop
iterating over them because the rest of the objects are just keys), but still
have them fan out to make them easier to look up directly.  The direct lookup
is of lesser importance because keyrings tend not to point to many other
keyrings.

> 4) There are 3/7 unused bytes in an assoc_array_node, after parent_slot.
>    Would it be worth storing 16/48 bits of index key and 3/4 bits of
>    number of levels to skip per assoc_array_node?
>    Since parent_slot is actually only 4 bits, you could store 4 bits
>    of nubmer of levels and 56 bits (up to 14 levels, plus the one
>    from the famout) of index key.
> 
>    With 32-way fanout, you could fit 5 bits of parent index, 25/55 bits of
>    index key, and encode the number of levels to skip (0-5/11) more carefully.

You mean merge some shortcut representation into a node?  Maybe.  It gets
messy, though, if the parent of such a node gets folded into *its* parent and
leaves the "skip+node" out of range of the index key storage that it has.  Now
you have to replace the "skip node" too (or insert a shortcut).  Multiply by
the fanout...

Actually, I'd rather store the index key nibble for each object I have a
pointer too.  That would take up another word sadly (16 * log2(16)), but would
improve insertion and searching a bit.

> 5) The big question: Why not use a hash table?  That's what people
>    usually expect when you say "associative array".  It would be simpler
>    and faster.

What I've implemented *is* in essence a series of nested hash tables;-)

But, in answer, no, it wouldn't necessarily be faster, but yes, it would mostly
be simpler[*].  The hash table approach would also be less memory efficient
generally - though one can construct datasets that would be horribly
inefficient for both algorithms - and much less efficient for mine.

[*] Until it comes to expanding or collapsing the hash table.  How do you work
    out how much to expand it or contract it by to get a good spread of
    objects?

A hash table would not be able to grow beyond PAGE_SIZE practically[**] - so a
maximum of 512 buckets on most 64-bit systems (assuming no other per-bucket
metadata for things like occupancy counts).  However, I'm looking at a case
with a need to store ~36000 keys in a keyring - so on the order of 70 keys per
hash bucket.  Assuming a perfect distribution, my array would require about
2500 nodes in a tree four levels deep and the maximum number of
index-key-to-object comparisons you'd have to make would be 16.

[**] order>0 allocations are to be avoided where possible, but it would be
     possible to stitch multiple pages together with a higher level pointer
     block - which adds complexity.

In a hash table the hash function is much more critical as it's only applied
once and you may not have control over variety of data you're going to be asked
to hash.  Also, in the keyrings case, you cannot link the objects (keys)
directly into the hash table, so each object would need to be represented by a
linkage block.

Further, once you've got a few objects into a hash table, a traditional hash
table is actually slower and less efficient because the object pointers are
spread over more cachelines.

I will grant you, though, that hash table look up, iteration, insertion and
deletion are all simpler - the last two _provided_ you do not need to resize
the hash table.

But I won't grant you that a hash table would necessarily be faster for the
given amount of metadata memory used.

>    RCU-safe resizeable hash tables are tricky, but a solved problem,

Conceptually, that's not too hard - provided you are willing to accept a
complete replacement of the entire metadata tree.  You have to do that so as
not to destabilise iteration and lookup when items jump to a different bucket.
Remember: modification shalt not block iteration or lookup.

>    There are universal hashing techniques for preventing hash collision
>    attacks.  

I'm not too worried about attacks.  If someone really wants to attack, you
can't really stop them.  The main difficulty with hashing is that you might
have no control over the data you're hashing.  The upside is that there's no
reason you have to only use one hashing function.  In my case, hashing
functions could be per-keytype for example.

David
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/Documentation/assoc_array.txt b/Documentation/assoc_array.txt
index 91ea88e..f4faec0 100644
--- a/Documentation/assoc_array.txt
+++ b/Documentation/assoc_array.txt
@@ -31,41 +31,36 @@  properties:
  (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.
+     [!] NOTE: Pointers to objects _must_ be zero in the least significant bit.
 
  (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.
+ (3) Objects require index keys to locate them within the array.
 
- (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
+ (4) 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.
+ (5) 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
+ (6) 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.
+ (7) 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
+ (8) The array can iterated over.  The objects will not necessarily come out in
      key order.
 
-(10) The array can be iterated over whilst it is being modified, provided the
+ (9) The array can be iterated over 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.
+(10) 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
+(11) 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
@@ -203,12 +198,11 @@  There are a number of functions for manipulating an associative array:
 	assoc_array_insert(struct assoc_array *array,
 			   const struct assoc_array_ops *ops,
 			   const void *index_key,
-			   void *object, bool type);
+			   void *object);
 
      This inserts the given object into the array.  Note that the least
-     significant two bits of the pointer must be zero as they're used to
-     type-mark pointers internally.  The type argument is an arbitrary
-     two-value type retained by the array but not used by the algorithms.
+     significant bit of the pointer must be zero as it's used to type-mark
+     pointers internally.
 
      If an object already exists for that key then it will be replaced with the
      new object and the old one will be freed automatically.
@@ -278,8 +272,7 @@  There are a number of functions for manipulating an associative array:
 
 	int assoc_array_gc(struct assoc_array *array,
 			   const struct assoc_array_ops *ops,
-			   bool (*iterator)(void *object, bool type,
-					    void *iterator_data),
+			   bool (*iterator)(void *object, void *iterator_data),
 			   void *iterator_data);
 
      This iterates over the objects in an associative array and passes each one
@@ -310,7 +303,7 @@  There are two functions for accessing an associative array:
  (1) Iterate over all the objects in an associative array.
 
 	int assoc_array_iterate(const struct assoc_array *array,
-				int (*iterator)(const void *object, bool type,
+				int (*iterator)(const void *object,
 						void *iterator_data),
 				void *iterator_data);
 
@@ -333,12 +326,10 @@  There are two functions for accessing an associative array:
 
 	void *assoc_array_find(const struct assoc_array *array,
 			       const struct assoc_array_ops *ops,
-			       const void *index_key,
-			       bool *_type);
+			       const void *index_key);
 
      This walks through the array's internal tree directly to the object
-     specified by the index key.  If the object is present then a pointer to it
-     is returned and the type is stored in *_type.
+     specified by the index key..
 
      This may be used on an array at the same time as the array is being
      modified, provided the RCU read lock is held.
@@ -384,7 +375,7 @@  A node is an array of slots.  Each slot can contain one of four things:
 
  (*) A NULL pointer, indicating that the slot is empty.
 
- (*) A pointer to one of two types of object (leaves).
+ (*) A pointer to an object (a leaf).
 
  (*) A pointer to a node at the next level.
 
diff --git a/include/linux/assoc_array.h b/include/linux/assoc_array.h
index c3c24da..9a193b8 100644
--- a/include/linux/assoc_array.h
+++ b/include/linux/assoc_array.h
@@ -62,19 +62,18 @@  static inline void assoc_array_init(struct assoc_array *array)
 }
 
 extern int assoc_array_iterate(const struct assoc_array *array,
-			       int (*iterator)(const void *object, bool type,
+			       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,
-			      bool *_type);
+			      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, bool type);
+						   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,
@@ -86,8 +85,7 @@  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, bool type,
-					   void *iterator_data),
+			  bool (*iterator)(void *object, void *iterator_data),
 			  void *iterator_data);
 
 #endif /* CONFIG_ASSOCIATIVE_ARRAY */
diff --git a/include/linux/assoc_array_priv.h b/include/linux/assoc_array_priv.h
index 2890afc..711275e 100644
--- a/include/linux/assoc_array_priv.h
+++ b/include/linux/assoc_array_priv.h
@@ -38,11 +38,11 @@  struct assoc_array_ptr;
  *
  *	(1) Nothing (NULL).
  *
- *	(2) A leaf object (pointer types 0 and 1).
+ *	(2) A leaf object (pointer types 0).
  *
- *	(3) A next-level node (pointer type 2).
+ *	(3) A next-level node (pointer type 1, subtype 0).
  *
- *	(4) A shortcut (pointer type 3).
+ *	(4) A shortcut (pointer type 1, subtype 1).
  *
  * The tree is optimised for search-by-ID, but permits reasonable iteration
  * also.
@@ -102,57 +102,80 @@  struct assoc_array_edit {
 };
 
 /*
- * Internal tree member pointer type annotations and translation functions.
+ * Internal tree member pointers are marked in the bottom one or two bits to
+ * indicate what type they are so that we don't have to look behind every
+ * pointer to see what it points to.
+ *
+ * We provide functions to test type annotations and to create and translate
+ * the annotated pointers.
  */
-enum assoc_array_ptr_type {
-	ASSOC_ARRAY_PTR_LEAF0	= 0x0UL,  /* The pointer points to a type 0 object */
-	ASSOC_ARRAY_PTR_LEAF1	= 0x1UL,  /* The pointer points to a type 1 object */
-	ASSOC_ARRAY_PTR_NODE	= 0x2UL,  /* The pointer points to a node */
-	ASSOC_ARRAY_PTR_SHORTCUT = 0x3UL, /* The pointer points to a shortcut */
-};
-
-#define ASSOC_ARRAY_PTR_TYPE_MASK 0x3UL	/* The bottom bits of the pointer hold type data */
-#define ASSOC_ARRAY_PTR_META	  0x2UL	/* Node and shortcut pointers are metadata */
+#define ASSOC_ARRAY_PTR_TYPE_MASK 0x1UL
+#define ASSOC_ARRAY_PTR_LEAF_TYPE 0x0UL	/* Points to leaf (or nowhere) */
+#define ASSOC_ARRAY_PTR_META_TYPE 0x1UL	/* Points to node or shortcut */
+#define ASSOC_ARRAY_PTR_SUBTYPE_MASK	0x2UL
+#define ASSOC_ARRAY_PTR_NODE_SUBTYPE	0x0UL
+#define ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE 0x2UL
 
-static inline
-enum assoc_array_ptr_type assoc_array_ptr_type(const struct assoc_array_ptr *x)
+static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr *x)
 {
 	return (unsigned long)x & ASSOC_ARRAY_PTR_TYPE_MASK;
 }
-#define assoc_array_ptr_is_leaf0(X)	(assoc_array_ptr_type((X)) == ASSOC_ARRAY_PTR_LEAF0)
-#define assoc_array_ptr_is_leaf1(X)	(assoc_array_ptr_type((X)) == ASSOC_ARRAY_PTR_LEAF1)
-#define assoc_array_ptr_is_node(X)	(assoc_array_ptr_type((X)) == ASSOC_ARRAY_PTR_NODE)
-#define assoc_array_ptr_is_shortcut(X)	(assoc_array_ptr_type((X)) == ASSOC_ARRAY_PTR_SHORTCUT)
-#define assoc_array_ptr_is_leaf(X)	(assoc_array_ptr_type((X)) <  ASSOC_ARRAY_PTR_META)
-#define assoc_array_ptr_is_meta(X)	(assoc_array_ptr_type((X)) >= ASSOC_ARRAY_PTR_META)
+static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr *x)
+{
+	return !assoc_array_ptr_is_meta(x);
+}
+static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_ptr *x)
+{
+	return (unsigned long)x & ASSOC_ARRAY_PTR_SUBTYPE_MASK;
+}
+static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr *x)
+{
+	return !assoc_array_ptr_is_shortcut(x);
+}
 
-static inline unsigned long __assoc_array_ptr_to_x(const struct assoc_array_ptr *x)
+static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr *x)
+{
+	return (void *)((unsigned long)x & ~ASSOC_ARRAY_PTR_TYPE_MASK);
+}
+
+static inline
+unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr *x)
+{
+	return (unsigned long)x &
+		~(ASSOC_ARRAY_PTR_SUBTYPE_MASK | ASSOC_ARRAY_PTR_TYPE_MASK);
+}
+static inline
+struct assoc_array_node *assoc_array_ptr_to_node(const struct assoc_array_ptr *x)
+{
+	return (struct assoc_array_node *)__assoc_array_ptr_to_meta(x);
+}
+static inline
+struct assoc_array_shortcut *assoc_array_ptr_to_shortcut(const struct assoc_array_ptr *x)
 {
-	return (unsigned long)x & ~ASSOC_ARRAY_PTR_TYPE_MASK;
+	return (struct assoc_array_shortcut *)__assoc_array_ptr_to_meta(x);
 }
-#define assoc_array_ptr_to_leaf(X)	((void *)__assoc_array_ptr_to_x((X)))
-#define assoc_array_ptr_to_node(X)	((struct assoc_array_node *)__assoc_array_ptr_to_x((X)))
-#define assoc_array_ptr_to_shortcut(X)	((struct assoc_array_shortcut *)__assoc_array_ptr_to_x((X)))
 
 static inline
-struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, enum assoc_array_ptr_type t)
+struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, unsigned long t)
 {
 	return (struct assoc_array_ptr *)((unsigned long)p | t);
 }
 static inline
-struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p, bool type)
+struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p)
 {
-	return __assoc_array_x_to_ptr(p, type ? ASSOC_ARRAY_PTR_LEAF1 : ASSOC_ARRAY_PTR_LEAF0);
+	return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_LEAF_TYPE);
 }
 static inline
 struct assoc_array_ptr *assoc_array_node_to_ptr(const struct assoc_array_node *p)
 {
-	return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_NODE);
+	return __assoc_array_x_to_ptr(
+		p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_NODE_SUBTYPE);
 }
 static inline
 struct assoc_array_ptr *assoc_array_shortcut_to_ptr(const struct assoc_array_shortcut *p)
 {
-	return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_SHORTCUT);
+	return __assoc_array_x_to_ptr(
+		p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE);
 }
 
 #endif /* CONFIG_ASSOCIATIVE_ARRAY */
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index e023c05..a095281 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -20,7 +20,7 @@ 
  */
 static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
 				       const struct assoc_array_ptr *stop,
-				       int (*iterator)(const void *leaf, bool type,
+				       int (*iterator)(const void *leaf,
 						       void *iterator_data),
 				       void *iterator_data)
 {
@@ -64,7 +64,6 @@  begin_node:
 
 			/* Invoke the callback */
 			ret = iterator(assoc_array_ptr_to_leaf(ptr),
-				       assoc_array_ptr_type(ptr),
 				       iterator_data);
 			if (ret)
 				return ret;
@@ -79,7 +78,7 @@  begin_node:
 	 * a particular portion of the key space cannot change - and we
 	 * continue at the back pointer + 1.
 	 */
-	if (!(has_meta & ASSOC_ARRAY_PTR_META))
+	if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
 		goto finished_node;
 	slot = 0;
 
@@ -142,7 +141,7 @@  finished_node:
  * modification is possible.
  */
 int assoc_array_iterate(const struct assoc_array *array,
-			int (*iterator)(const void *object, bool type,
+			int (*iterator)(const void *object,
 					void *iterator_data),
 			void *iterator_data)
 {
@@ -221,8 +220,8 @@  consider_node:
 	slot &= ASSOC_ARRAY_FAN_MASK;
 	ptr = ACCESS_ONCE(node->slots[slot]);
 
-	pr_devel("consider slot %x [ix=%d type=%u]\n",
-		 slot, level, assoc_array_ptr_type(ptr));
+	pr_devel("consider slot %x [ix=%d type=%lu]\n",
+		 slot, level, (unsigned long)ptr & 3);
 
 	if (!assoc_array_ptr_is_meta(ptr)) {
 		/* The node doesn't have a node/shortcut pointer in the slot
@@ -308,7 +307,6 @@  follow_shortcut:
  * @array: The associative array to search.
  * @ops: The operations to use.
  * @index_key: The key to the object.
- * @_type: Where the object type will be returned (if found).
  *
  * Find an object in an associative array by walking through the internal tree
  * to the node that should contain the object and then searching the leaves
@@ -318,8 +316,7 @@  follow_shortcut:
  */
 void *assoc_array_find(const struct assoc_array *array,
 		       const struct assoc_array_ops *ops,
-		       const void *index_key,
-		       bool *_type)
+		       const void *index_key)
 {
 	struct assoc_array_walk_result result;
 	const struct assoc_array_node *node;
@@ -346,10 +343,8 @@  void *assoc_array_find(const struct assoc_array *array,
 			 */
 			leaf = assoc_array_ptr_to_leaf(ptr);
 			smp_read_barrier_depends();
-			if (ops->compare_object(leaf, index_key)) {
-				*_type = assoc_array_ptr_type(ptr);
+			if (ops->compare_object(leaf, index_key))
 				return (void *)leaf;
-			}
 		}
 	}
 
@@ -527,8 +522,7 @@  static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
 			free_slot = i;
 			continue;
 		}
-		if (assoc_array_ptr_type(ptr) == assoc_array_ptr_type(edit->leaf) &&
-		    ops->compare_object(assoc_array_ptr_to_leaf(ptr), index_key)) {
+		if (ops->compare_object(assoc_array_ptr_to_leaf(ptr), index_key)) {
 			pr_devel("replace in slot %d\n", i);
 			edit->leaf_p = &node->slots[i];
 			edit->dead_leaf = node->slots[i];
@@ -697,17 +691,13 @@  found_slot_for_multiple_occupancy:
 	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
 		if (edit->segment_cache[i] == 0xff) {
 			ptr = node->slots[i];
-			switch (assoc_array_ptr_type(ptr)) {
-			case ASSOC_ARRAY_PTR_NODE:
+			BUG_ON(assoc_array_ptr_is_leaf(ptr));
+			if (assoc_array_ptr_is_node(ptr)) {
 				side = assoc_array_ptr_to_node(ptr);
 				edit->set_backpointers[i] = &side->back_pointer;
-				break;
-			case ASSOC_ARRAY_PTR_SHORTCUT:
+			} else {
 				shortcut = assoc_array_ptr_to_shortcut(ptr);
 				edit->set_backpointers[i] = &shortcut->back_pointer;
-				break;
-			default:
-				BUG();
 			}
 		}
 	}
@@ -986,7 +976,6 @@  static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
  * @ops: The operations to use.
  * @index_key: The key to insert at.
  * @object: The object to insert.
- * @type: The type of the object.
  *
  * Precalculate and preallocate a script for the insertion or replacement of an
  * object in an associative array.  This results in an edit script that can
@@ -1003,24 +992,26 @@  static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
 struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
 					    const struct assoc_array_ops *ops,
 					    const void *index_key,
-					    void *object, bool type)
+					    void *object)
 {
 	struct assoc_array_walk_result result;
 	struct assoc_array_edit *edit;
 
 	pr_devel("-->%s()\n", __func__);
 
-	/* The leaf pointer we're given must not have the bottom two bits set
-	 * as we use those for type-marking the pointer.
+	/* The leaf pointer we're given must not have the bottom bit set as we
+	 * use those for type-marking the pointer.  NULL pointers are also not
+	 * allowed as they indicate an empty slot but we have to allow them
+	 * here as they can be updated later.
 	 */
-	BUG_ON(assoc_array_ptr_type(object) != 0);
+	BUG_ON(assoc_array_ptr_is_meta(object));
 
 	edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
 	if (!edit)
 		return ERR_PTR(-ENOMEM);
 	edit->array = array;
 	edit->ops = ops;
-	edit->leaf = assoc_array_leaf_to_ptr(object, type);
+	edit->leaf = assoc_array_leaf_to_ptr(object);
 	edit->adjust_count_by = 1;
 
 	switch (assoc_array_walk(array, ops, index_key, &result)) {
@@ -1058,12 +1049,17 @@  enomem:
 
 /**
  * assoc_array_insert_set_object - Set the new object pointer in an edit script
+ * @edit: The edit script to modify.
+ * @object: The object pointer to set.
+ *
+ * Change the object to be inserted in an edit script.  The object pointed to
+ * by the old object is not freed.  This must be done prior to applying the
+ * script.
  */
 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
 {
-	bool type = assoc_array_ptr_is_leaf1(edit->leaf);
-
-	edit->leaf = assoc_array_leaf_to_ptr(object, type);
+	BUG_ON(!object);
+	edit->leaf = assoc_array_leaf_to_ptr(object);
 }
 
 struct assoc_array_delete_collapse_context {
@@ -1075,7 +1071,7 @@  struct assoc_array_delete_collapse_context {
 /*
  * Subtree collapse to node iterator.
  */
-static int assoc_array_delete_collapse_iterator(const void *leaf, bool type,
+static int assoc_array_delete_collapse_iterator(const void *leaf,
 						void *iterator_data)
 {
 	struct assoc_array_delete_collapse_context *collapse = iterator_data;
@@ -1085,8 +1081,7 @@  static int assoc_array_delete_collapse_iterator(const void *leaf, bool type,
 
 	BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
 
-	collapse->node->slots[collapse->slot++] =
-		assoc_array_leaf_to_ptr(leaf, type);
+	collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
 	return 0;
 }
 
@@ -1261,6 +1256,8 @@  found_leaf:
 
 			if (!node->back_pointer) {
 				edit->set[1].ptr = &array->root;
+			} else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
+				BUG();
 			} else if (assoc_array_ptr_is_node(node->back_pointer)) {
 				struct assoc_array_node *p =
 					assoc_array_ptr_to_node(node->back_pointer);
@@ -1269,8 +1266,6 @@  found_leaf:
 				struct assoc_array_shortcut *s =
 					assoc_array_ptr_to_shortcut(node->back_pointer);
 				edit->set[1].ptr = &s->next_node;
-			} else {
-				BUG();
 			}
 			edit->set[1].to = assoc_array_node_to_ptr(new_n0);
 			edit->excised_subtree = assoc_array_node_to_ptr(node);
@@ -1345,16 +1340,15 @@  static void assoc_array_rcu_cleanup(struct rcu_head *head)
 			kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
 
 	if (edit->excised_subtree) {
+		BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
 		if (assoc_array_ptr_is_node(edit->excised_subtree)) {
 			struct assoc_array_node *n =
 				assoc_array_ptr_to_node(edit->excised_subtree);
 			n->back_pointer = NULL;
-		} else if (assoc_array_ptr_is_shortcut(edit->excised_subtree)) {
+		} else {
 			struct assoc_array_shortcut *s =
 				assoc_array_ptr_to_shortcut(edit->excised_subtree);
 			s->back_pointer = NULL;
-		} else {
-			BUG();
 		}
 		assoc_array_destroy_subtree(edit->excised_subtree,
 					    edit->ops_for_excised_subtree);
@@ -1450,10 +1444,12 @@  void assoc_array_cancel_edit(struct assoc_array_edit *edit)
 	/* Clean up after an out of memory error */
 	for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
 		ptr = edit->new_meta[i];
-		if (assoc_array_ptr_is_node(ptr))
-			kfree(assoc_array_ptr_to_node(ptr));
-		else
-			kfree(assoc_array_ptr_to_shortcut(ptr));
+		if (ptr) {
+			if (assoc_array_ptr_is_node(ptr))
+				kfree(assoc_array_ptr_to_node(ptr));
+			else
+				kfree(assoc_array_ptr_to_shortcut(ptr));
+		}
 	}
 	kfree(edit);
 }
@@ -1484,8 +1480,7 @@  void assoc_array_cancel_edit(struct assoc_array_edit *edit)
  */
 int assoc_array_gc(struct assoc_array *array,
 		   const struct assoc_array_ops *ops,
-		   bool (*iterator)(void *object, bool type,
-				    void *iterator_data),
+		   bool (*iterator)(void *object, void *iterator_data),
 		   void *iterator_data)
 {
 	struct assoc_array_shortcut *shortcut, *new_s;
@@ -1557,7 +1552,6 @@  continue_node:
 
 		if (assoc_array_ptr_is_leaf(ptr)) {
 			if (iterator(assoc_array_ptr_to_leaf(ptr),
-				     assoc_array_ptr_is_leaf1(ptr),
 				     iterator_data))
 				/* The iterator will have done any reference
 				 * counting on the object for us.
@@ -1650,7 +1644,8 @@  continue_node:
 			if ((ptr = new_n->slots[slot]))
 				break;
 
-		if (assoc_array_ptr_is_shortcut(ptr)) {
+		if (assoc_array_ptr_is_meta(ptr) &&
+		    assoc_array_ptr_is_shortcut(ptr)) {
 			pr_devel("excise node %p with 1 shortcut\n", new_n);
 			new_s = assoc_array_ptr_to_shortcut(ptr);
 			new_parent = new_n->back_pointer;
diff --git a/security/keys/gc.c b/security/keys/gc.c
index 5af99b8..627bdd06 100644
--- a/security/keys/gc.c
+++ b/security/keys/gc.c
@@ -130,7 +130,7 @@  void key_gc_keytype(struct key_type *ktype)
 	kleave("");
 }
 
-static int key_gc_keyring_func(const void *object, bool type, void *iterator_data)
+static int key_gc_keyring_func(const void *object, void *iterator_data)
 {
 	const struct key *key = object;
 	time_t *limit = iterator_data;
diff --git a/security/keys/internal.h b/security/keys/internal.h
index 2a8d624..581c6f6 100644
--- a/security/keys/internal.h
+++ b/security/keys/internal.h
@@ -122,7 +122,7 @@  struct keyring_search_context {
 #define KEYRING_SEARCH_NO_CHECK_PERM	0x0010	/* Don't check permissions */
 #define KEYRING_SEARCH_DETECT_TOO_DEEP	0x0020	/* Give an error on excessive depth */
 
-	int (*iterator)(const void *object, bool type, void *iterator_data);
+	int (*iterator)(const void *object, void *iterator_data);
 
 	/* Internal stuff */
 	int			skipped_ret;
diff --git a/security/keys/keyring.c b/security/keys/keyring.c
index 8b7ec48..8ce680d 100644
--- a/security/keys/keyring.c
+++ b/security/keys/keyring.c
@@ -33,8 +33,27 @@ 
  */
 #define KEYRING_NAME_HASH_SIZE	(1 << 5)
 
-#define assoc_array_ptr_is_key(X)	(assoc_array_ptr_is_leaf0(X))
-#define assoc_array_ptr_is_keyring(X)	(assoc_array_ptr_is_leaf1(X))
+/*
+ * We mark pointers we pass to the associative array with bit 1 set if
+ * they're keyrings and clear otherwise.
+ */
+#define KEYRING_PTR_SUBTYPE	0x2UL
+
+static inline bool keyring_ptr_is_keyring(const struct assoc_array_ptr *x)
+{
+	return (unsigned long)x & KEYRING_PTR_SUBTYPE;
+}
+static inline struct key *keyring_ptr_to_key(const struct assoc_array_ptr *x)
+{
+	void *object = assoc_array_ptr_to_leaf(x);
+	return (struct key *)((unsigned long)object & ~KEYRING_PTR_SUBTYPE);
+}
+static inline void *keyring_key_to_ptr(struct key *key)
+{
+	if (key->type == &key_type_keyring)
+		return (void *)((unsigned long)key | KEYRING_PTR_SUBTYPE);
+	return key;
+}
 
 static struct list_head	keyring_name_hash[KEYRING_NAME_HASH_SIZE];
 static DEFINE_RWLOCK(keyring_name_lock);
@@ -239,14 +258,14 @@  static unsigned long keyring_get_key_chunk(const void *data, int level)
 
 static unsigned long keyring_get_object_key_chunk(const void *object, int level)
 {
-	const struct key *key = object;
+	const struct key *key = keyring_ptr_to_key(object);
 	return keyring_get_key_chunk(&key->index_key, level);
 }
 
 static bool keyring_compare_object(const void *object, const void *data)
 {
 	const struct keyring_index_key *index_key = data;
-	const struct key *key = object;
+	const struct key *key = keyring_ptr_to_key(object);
 
 	return key->index_key.type == index_key->type &&
 		key->index_key.desc_len == index_key->desc_len &&
@@ -260,7 +279,8 @@  static bool keyring_compare_object(const void *object, const void *data)
  */
 static int keyring_diff_objects(const void *_a, const void *_b)
 {
-	const struct key *key_a = _a, *key_b = _b;
+	const struct key *key_a = keyring_ptr_to_key(_a);
+	const struct key *key_b = keyring_ptr_to_key(_b);
 	const struct keyring_index_key *a = &key_a->index_key;
 	const struct keyring_index_key *b = &key_b->index_key;
 	unsigned long seg_a, seg_b;
@@ -319,6 +339,14 @@  differ:
 }
 
 /*
+ * Free an object after stripping the keyring flag off of the pointer.
+ */
+static void keyring_free_object(void *object)
+{
+	key_put(keyring_ptr_to_key(object));
+}
+
+/*
  * Operations for keyring management by the index-tree routines.
  */
 static const struct assoc_array_ops keyring_assoc_array_ops = {
@@ -326,7 +354,7 @@  static const struct assoc_array_ops keyring_assoc_array_ops = {
 	.get_object_key_chunk	= keyring_get_object_key_chunk,
 	.compare_object		= keyring_compare_object,
 	.diff_objects		= keyring_diff_objects,
-	.free_object		= (void (*)(void *))key_put,
+	.free_object		= keyring_free_object,
 };
 
 /*
@@ -377,10 +405,10 @@  struct keyring_read_iterator_context {
 	key_serial_t __user	*buffer;
 };
 
-static int keyring_read_iterator(const void *object, bool type, void *data)
+static int keyring_read_iterator(const void *object, void *data)
 {
 	struct keyring_read_iterator_context *ctx = data;
-	const struct key *key = object;
+	const struct key *key = keyring_ptr_to_key(object);
 	int ret;
 
 	kenter("{%s,%d},,{%zu/%zu}",
@@ -469,11 +497,10 @@  EXPORT_SYMBOL(keyring_alloc);
 /*
  * Iteration function to consider each key found.
  */
-static int keyring_search_iterator(const void *object, bool type,
-				   void *iterator_data)
+static int keyring_search_iterator(const void *object, void *iterator_data)
 {
 	struct keyring_search_context *ctx = iterator_data;
-	const struct key *key = object;
+	const struct key *key = keyring_ptr_to_key(object);
 	unsigned long kflags = key->flags;
 
 	kenter("{%d}", key->serial);
@@ -542,13 +569,12 @@  static int search_keyring(struct key *keyring, struct keyring_search_context *ct
 {
 	if ((ctx->flags & KEYRING_SEARCH_LOOKUP_TYPE) ==
 	    KEYRING_SEARCH_LOOKUP_DIRECT) {
-		struct key *key;
-		bool type;
+		const void *object;
 
-		key = assoc_array_find(&keyring->keys,
-				       &keyring_assoc_array_ops,
-				       &ctx->index_key, &type);
-		return key ? ctx->iterator(key, type, ctx) : 0;
+		object = assoc_array_find(&keyring->keys,
+					  &keyring_assoc_array_ops,
+					  &ctx->index_key);
+		return object ? ctx->iterator(object, ctx) : 0;
 	}
 	return assoc_array_iterate(&keyring->keys, ctx->iterator, ctx);
 }
@@ -587,7 +613,7 @@  static bool search_nested_keyrings(struct key *keyring,
 	    keyring_compare_object(keyring, &ctx->index_key)) {
 		ctx->skipped_ret = 2;
 		ctx->flags |= KEYRING_SEARCH_DO_STATE_CHECK;
-		switch (ctx->iterator(keyring, true, ctx)) {
+		switch (ctx->iterator(keyring_key_to_ptr(keyring), ctx)) {
 		case 1:
 			goto found;
 		case 2:
@@ -673,10 +699,10 @@  ascend_to_node:
 		if (assoc_array_ptr_is_meta(ptr) && node->back_pointer)
 			goto descend_to_node;
 
-		if (!assoc_array_ptr_is_keyring(ptr))
+		if (!keyring_ptr_is_keyring(ptr))
 			continue;
 
-		key = assoc_array_ptr_to_leaf(ptr);
+		key = keyring_ptr_to_key(ptr);
 
 		if (sp >= KEYRING_SEARCH_MAX_DEPTH) {
 			if (ctx->flags & KEYRING_SEARCH_DETECT_TOO_DEEP) {
@@ -709,7 +735,7 @@  ascend_to_node:
 	ptr = ACCESS_ONCE(node->back_pointer);
 	slot = node->parent_slot;
 
-	if (assoc_array_ptr_is_shortcut(ptr)) {
+	if (ptr && assoc_array_ptr_is_shortcut(ptr)) {
 		shortcut = assoc_array_ptr_to_shortcut(ptr);
 		smp_read_barrier_depends();
 		ptr = ACCESS_ONCE(shortcut->back_pointer);
@@ -872,23 +898,24 @@  key_ref_t find_key_to_update(key_ref_t keyring_ref,
 			     const struct keyring_index_key *index_key)
 {
 	struct key *keyring, *key;
-	bool type;
+	const void *object;
 
 	keyring = key_ref_to_ptr(keyring_ref);
 
 	kenter("{%d},{%s,%s}",
 	       keyring->serial, index_key->type->name, index_key->description);
 
-	key = assoc_array_find(&keyring->keys, &keyring_assoc_array_ops,
-			       index_key, &type);
+	object = assoc_array_find(&keyring->keys, &keyring_assoc_array_ops,
+				  index_key);
 
-	if (key)
+	if (object)
 		goto found;
 
 	kleave(" = NULL");
 	return NULL;
 
 found:
+	key = keyring_ptr_to_key(object);
 	if (key->flags & ((1 << KEY_FLAG_INVALIDATED) |
 			  (1 << KEY_FLAG_REVOKED))) {
 		kleave(" = NULL [x]");
@@ -959,11 +986,11 @@  out:
 	return keyring;
 }
 
-static int keyring_detect_cycle_iterator(const void *object, bool type,
+static int keyring_detect_cycle_iterator(const void *object,
 					 void *iterator_data)
 {
 	struct keyring_search_context *ctx = iterator_data;
-	const struct key *key = object;
+	const struct key *key = keyring_ptr_to_key(object);
 
 	kenter("{%d}", key->serial);
 
@@ -1038,9 +1065,10 @@  int __key_link_begin(struct key *keyring,
 	/* Create an edit script that will insert/replace the key in the
 	 * keyring tree.
 	 */
-	edit = assoc_array_insert(&keyring->keys, &keyring_assoc_array_ops,
+	edit = assoc_array_insert(&keyring->keys,
+				  &keyring_assoc_array_ops,
 				  index_key,
-				  NULL, index_key->type == &key_type_keyring);
+				  NULL);
 	if (IS_ERR(edit)) {
 		ret = PTR_ERR(edit);
 		goto error_quota;
@@ -1089,7 +1117,7 @@  int __key_link_check_live_key(struct key *keyring, struct key *key)
 void __key_link(struct key *key, struct assoc_array_edit **_edit)
 {
 	__key_get(key);
-	assoc_array_insert_set_object(*_edit, key);
+	assoc_array_insert_set_object(*_edit, keyring_key_to_ptr(key));
 	assoc_array_apply_edit(*_edit);
 	*_edit = NULL;
 }
@@ -1262,9 +1290,9 @@  static void keyring_revoke(struct key *keyring)
 	}
 }
 
-static bool gc_iterator(void *object, bool type, void *iterator_data)
+static bool gc_iterator(void *object, void *iterator_data)
 {
-	struct key *key = object;
+	struct key *key = keyring_ptr_to_key(object);
 	time_t *limit = iterator_data;
 
 	if (key_is_dead(key, *limit))