1. 02 Nov, 2017 1 commit
    • David Howells's avatar
      assoc_array: Fix a buggy node-splitting case · 67bcc5e5
      David Howells authored
      commit ea678998 upstream.
      This fixes CVE-2017-12193.
      Fix a case in the assoc_array implementation in which a new leaf is
      added that needs to go into a node that happens to be full, where the
      existing leaves in that node cluster together at that level to the
      exclusion of new leaf.
      What needs to happen is that the existing leaves get moved out to a new
      node, N1, at level + 1 and the existing node needs replacing with one,
      N0, that has pointers to the new leaf and to N1.
      The code that tries to do this gets this wrong in two ways:
       (1) The pointer that should've pointed from N0 to N1 is set to point
           recursively to N0 instead.
       (2) The backpointer from N0 needs to be set correctly in the case N0 is
           either the root node or reached through a shortcut.
      Fix this by removing this path and using the split_node path instead,
      which achieves the same end, but in a more general way (thanks to Eric
      Biggers for spotting the redundancy).
      The problem manifests itself as:
        BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
        IP: assoc_array_apply_edit+0x59/0xe5
      Fixes: 3cb98950 ("Add a generic associative array implementation.")
      Reported-and-tested-by: default avatarWU Fan <u3536072@connect.hku.hk>
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      Signed-off-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
  2. 06 Apr, 2016 1 commit
    • Jerome Marchand's avatar
      assoc_array: don't call compare_object() on a node · 8d4a2ec1
      Jerome Marchand authored
      Changes since V1: fixed the description and added KASan warning.
      In assoc_array_insert_into_terminal_node(), we call the
      compare_object() method on all non-empty slots, even when they're
      not leaves, passing a pointer to an unexpected structure to
      compare_object(). Currently it causes an out-of-bound read access
      in keyring_compare_object detected by KASan (see below). The issue
      is easily reproduced with keyutils testsuite.
      Only call compare_object() when the slot is a leave.
      KASan warning:
      BUG: KASAN: slab-out-of-bounds in keyring_compare_object+0x213/0x240 at addr ffff880060a6f838
      Read of size 8 by task keyctl/1655
      BUG kmalloc-192 (Not tainted): kasan: bad access detected
      Disabling lock debugging due to kernel taint
      INFO: Allocated in assoc_array_insert+0xfd0/0x3a60 age=69 cpu=1 pid=1647
      INFO: Slab 0xffffea0001829b80 objects=16 used=8 fp=0xffff880060a6f550 flags=0x3fff8000004080
      INFO: Object 0xffff880060a6f740 @offset=5952 fp=0xffff880060a6e5d1
      Bytes b4 ffff880060a6f730: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f740: d1 e5 a6 60 00 88 ff ff 0e 00 00 00 00 00 00 00  ...`............
      Object ffff880060a6f750: 02 cf 8e 60 00 88 ff ff 02 c0 8e 60 00 88 ff ff  ...`.......`....
      Object ffff880060a6f760: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f770: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f780: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f790: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7d0: 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      Object ffff880060a6f7f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
      CPU: 0 PID: 1655 Comm: keyctl Tainted: G    B           4.5.0-rc4-kasan+ #291
      Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011
       0000000000000000 000000001b2800b4 ffff880060a179e0 ffffffff81b60491
       ffff88006c802900 ffff880060a6f740 ffff880060a17a10 ffffffff815e2969
       ffff88006c802900 ffffea0001829b80 ffff880060a6f740 ffff880060a6e650
      Call Trace:
       [<ffffffff81b60491>] dump_stack+0x85/0xc4
       [<ffffffff815e2969>] print_trailer+0xf9/0x150
       [<ffffffff815e9454>] object_err+0x34/0x40
       [<ffffffff815ebe50>] kasan_report_error+0x230/0x550
       [<ffffffff819949be>] ? keyring_get_key_chunk+0x13e/0x210
       [<ffffffff815ec62d>] __asan_report_load_n_noabort+0x5d/0x70
       [<ffffffff81994cc3>] ? keyring_compare_object+0x213/0x240
       [<ffffffff81994cc3>] keyring_compare_object+0x213/0x240
       [<ffffffff81bc238c>] assoc_array_insert+0x86c/0x3a60
       [<ffffffff81bc1b20>] ? assoc_array_cancel_edit+0x70/0x70
       [<ffffffff8199797d>] ? __key_link_begin+0x20d/0x270
       [<ffffffff8199786c>] __key_link_begin+0xfc/0x270
       [<ffffffff81993389>] key_create_or_update+0x459/0xaf0
       [<ffffffff8128ce0d>] ? trace_hardirqs_on+0xd/0x10
       [<ffffffff81992f30>] ? key_type_lookup+0xc0/0xc0
       [<ffffffff8199e19d>] ? lookup_user_key+0x13d/0xcd0
       [<ffffffff81534763>] ? memdup_user+0x53/0x80
       [<ffffffff819983ea>] SyS_add_key+0x1ba/0x350
       [<ffffffff81998230>] ? key_get_type_from_user.constprop.6+0xa0/0xa0
       [<ffffffff828bcf4e>] ? retint_user+0x18/0x23
       [<ffffffff8128cc7e>] ? trace_hardirqs_on_caller+0x3fe/0x580
       [<ffffffff81004017>] ? trace_hardirqs_on_thunk+0x17/0x19
       [<ffffffff828bc432>] entry_SYSCALL_64_fastpath+0x12/0x76
      Memory state around the buggy address:
       ffff880060a6f700: fc fc fc fc fc fc fc fc 00 00 00 00 00 00 00 00
       ffff880060a6f780: 00 00 00 00 00 00 00 00 00 00 00 fc fc fc fc fc
      >ffff880060a6f800: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
       ffff880060a6f880: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
       ffff880060a6f900: fc fc fc fc fc fc 00 00 00 00 00 00 00 00 00 00
      Signed-off-by: default avatarJerome Marchand <jmarchan@redhat.com>
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      cc: stable@vger.kernel.org
  3. 07 Jan, 2015 1 commit
    • Pranith Kumar's avatar
      assoc_array: Include rcupdate.h for call_rcu() definition · 990428b8
      Pranith Kumar authored
      Include rcupdate.h header to provide call_rcu() definition. This was implicitly
      being provided by slab.h file which include srcu.h somewhere in its include
      hierarchy which in-turn included rcupdate.h.
      Lately, tinification effort added support to remove srcu entirely because of
      which we are encountering build errors like
      lib/assoc_array.c: In function 'assoc_array_apply_edit':
      lib/assoc_array.c:1426:2: error: implicit declaration of function 'call_rcu' [-Werror=implicit-function-declaration]
      cc1: some warnings being treated as errors
      Fix these by including rcupdate.h explicitly.
      Signed-off-by: default avatarPranith Kumar <bobby.prani@gmail.com>
      Reported-by: Scott Wood's avatarScott Wood <scottwood@freescale.com>
  4. 12 Sep, 2014 1 commit
    • David Howells's avatar
      KEYS: Fix termination condition in assoc array garbage collection · 95389b08
      David Howells authored
      This fixes CVE-2014-3631.
      It is possible for an associative array to end up with a shortcut node at the
      root of the tree if there are more than fan-out leaves in the tree, but they
      all crowd into the same slot in the lowest level (ie. they all have the same
      first nibble of their index keys).
      When assoc_array_gc() returns back up the tree after scanning some leaves, it
      can fall off of the root and crash because it assumes that the back pointer
      from a shortcut (after label ascend_old_tree) must point to a normal node -
      which isn't true of a shortcut node at the root.
      Should we find we're ascending rootwards over a shortcut, we should check to
      see if the backpointer is zero - and if it is, we have completed the scan.
      This particular bug cannot occur if the root node is not a shortcut - ie. if
      you have fewer than 17 keys in a keyring or if you have at least two keys that
      sit into separate slots (eg. a keyring and a non keyring).
      This can be reproduced by:
      	ring=`keyctl newring bar @s`
      	for ((i=1; i<=18; i++)); do last_key=`keyctl newring foo$i $ring`; done
      	keyctl timeout $last_key 2
      Doing this:
      	echo 3 >/proc/sys/kernel/keys/gc_delay
      first will speed things up.
      If we do fall off of the top of the tree, we get the following oops:
      BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
      IP: [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
      PGD dae15067 PUD cfc24067 PMD 0
      Oops: 0000 [#1] SMP
      Modules linked in: xt_nat xt_mark nf_conntrack_netbios_ns nf_conntrack_broadcast ip6t_rpfilter ip6t_REJECT xt_conntrack ebtable_nat ebtable_broute bridge stp llc ebtable_filter ebtables ip6table_ni
      CPU: 0 PID: 26011 Comm: kworker/0:1 Not tainted 3.14.9-200.fc20.x86_64 #1
      Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011
      Workqueue: events key_garbage_collector
      task: ffff8800918bd580 ti: ffff8800aac14000 task.ti: ffff8800aac14000
      RIP: 0010:[<ffffffff8136cea7>] [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
      RSP: 0018:ffff8800aac15d40  EFLAGS: 00010206
      RAX: 0000000000000000 RBX: 0000000000000000 RCX: ffff8800aaecacc0
      RDX: ffff8800daecf440 RSI: 0000000000000001 RDI: ffff8800aadc2bc0
      RBP: ffff8800aac15da8 R08: 0000000000000001 R09: 0000000000000003
      R10: ffffffff8136ccc7 R11: 0000000000000000 R12: 0000000000000000
      R13: 0000000000000000 R14: 0000000000000070 R15: 0000000000000001
      FS:  0000000000000000(0000) GS:ffff88011fc00000(0000) knlGS:0000000000000000
      CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
      CR2: 0000000000000018 CR3: 00000000db10d000 CR4: 00000000000006f0
       ffff8800aac15d50 0000000000000011 ffff8800aac15db8 ffffffff812e2a70
       ffff880091a00600 0000000000000000 ffff8800aadc2bc3 00000000cd42c987
       ffff88003702df20 ffff88003702dfa0 0000000053b65c09 ffff8800aac15fd8
      Call Trace:
       [<ffffffff812e2a70>] ? keyring_detect_cycle_iterator+0x30/0x30
       [<ffffffff812e3e75>] keyring_gc+0x75/0x80
       [<ffffffff812e1424>] key_garbage_collector+0x154/0x3c0
       [<ffffffff810a67b6>] process_one_work+0x176/0x430
       [<ffffffff810a744b>] worker_thread+0x11b/0x3a0
       [<ffffffff810a7330>] ? rescuer_thread+0x3b0/0x3b0
       [<ffffffff810ae1a8>] kthread+0xd8/0xf0
       [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
       [<ffffffff816ffb7c>] ret_from_fork+0x7c/0xb0
       [<ffffffff810ae0d0>] ? insert_kthread_work+0x40/0x40
      Code: 08 4c 8b 22 0f 84 bf 00 00 00 41 83 c7 01 49 83 e4 fc 41 83 ff 0f 4c 89 65 c0 0f 8f 5a fe ff ff 48 8b 45 c0 4d 63 cf 49 83 c1 02 <4e> 8b 34 c8 4d 85 f6 0f 84 be 00 00 00 41 f6 c6 01 0f 84 92
      RIP  [<ffffffff8136cea7>] assoc_array_gc+0x2f7/0x540
       RSP <ffff8800aac15d40>
      CR2: 0000000000000018
      ---[ end trace 1129028a088c0cbd ]---
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
      Acked-by: default avatarDon Zickus <dzickus@redhat.com>
      Signed-off-by: default avatarJames Morris <james.l.morris@oracle.com>
  5. 03 Sep, 2014 1 commit
  6. 23 Jan, 2014 1 commit
  7. 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>
  8. 24 Sep, 2013 2 commits
    • David Howells's avatar
      KEYS: Expand the capacity of a keyring · b2a4df20
      David Howells authored
      Expand the capacity of a keyring to be able to hold a lot more keys by using
      the previously added associative array implementation.  Currently the maximum
      capacity is:
      	(PAGE_SIZE - sizeof(header)) / sizeof(struct key *)
      which, on a 64-bit system, is a little more 500.  However, since this is being
      used for the NFS uid mapper, we need more than that.  The new implementation
      gives us effectively unlimited capacity.
      With some alterations, the keyutils testsuite runs successfully to completion
      after this patch is applied.  The alterations are because (a) keyrings that
      are simply added to no longer appear ordered and (b) some of the errors have
      changed a bit.
      Signed-off-by: default avatarDavid Howells <dhowells@redhat.com>
    • 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>