1. 02 Dec, 2013 1 commit
    • David Howells's avatar
      KEYS: Fix multiple key add into associative array · 23fd78d7
      David Howells authored
      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
      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
      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: [<ffffffff81191ee4>] hash_key_type_and_desc+0x18/0xb0
      RIP: 0010:[<ffffffff81191ee4>] hash_key_type_and_desc+0x18/0xb0
      Call Trace:
       [<ffffffff81191f9d>] keyring_diff_objects+0x21/0xd2
       [<ffffffff811f09ef>] assoc_array_insert+0x3b6/0x908
       [<ffffffff811929a7>] __key_link_begin+0x78/0xe5
       [<ffffffff81191a2e>] key_create_or_update+0x17d/0x36a
       [<ffffffff81192e0a>] SyS_add_key+0x123/0x183
       [<ffffffff81400ddb>] tracesys+0xdd/0xe2
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      Tested-by: default avatarStephen Gallagher <sgallagh@redhat.com>
  2. 24 Sep, 2013 1 commit
    • David Howells's avatar
      Add a generic associative array implementation. · 3cb98950
      David Howells authored
      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
       (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: default avatarDavid Howells <dhowells@redhat.com>