diff options
author | Greg Kroah-Hartman <gregkh@google.com> | 2017-11-02 10:24:37 +0100 |
---|---|---|
committer | Greg Kroah-Hartman <gregkh@google.com> | 2017-11-02 10:24:37 +0100 |
commit | aed4c54ad104104ac693e8a0d6b6b3f7e409bc81 (patch) | |
tree | d5cc549d69d2700ae4c233ad8dc29d07894dc4a5 /lib | |
parent | 9e293db0522f2332c3c89f431c488a3f525bc4e6 (diff) | |
parent | 27e68f1bca91a7f69808c8641f03c66cca2bb365 (diff) |
Merge 4.4.96 into android-4.4
Changes in 4.4.96
workqueue: replace pool->manager_arb mutex with a flag
ALSA: hda/realtek - Add support for ALC236/ALC3204
ALSA: hda - fix headset mic problem for Dell machines with alc236
ceph: unlock dangling spinlock in try_flush_caps()
usb: xhci: Handle error condition in xhci_stop_device()
spi: uapi: spidev: add missing ioctl header
fuse: fix READDIRPLUS skipping an entry
xen/gntdev: avoid out of bounds access in case of partial gntdev_mmap()
Input: elan_i2c - add ELAN0611 to the ACPI table
Input: gtco - fix potential out-of-bound access
assoc_array: Fix a buggy node-splitting case
scsi: zfcp: fix erp_action use-before-initialize in REC action trace
scsi: sg: Re-fix off by one in sg_fill_request_table()
can: sun4i: fix loopback mode
can: kvaser_usb: Correct return value in printout
can: kvaser_usb: Ignore CMD_FLUSH_QUEUE_REPLY messages
regulator: fan53555: fix I2C device ids
x86/microcode/intel: Disable late loading on model 79
ecryptfs: fix dereference of NULL user_key_payload
Revert "drm: bridge: add DT bindings for TI ths8135"
Linux 4.4.96
Signed-off-by: Greg Kroah-Hartman <gregkh@google.com>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/assoc_array.c | 51 |
1 files changed, 17 insertions, 34 deletions
diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 59fd7c0b119c..5cd093589c5a 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -598,21 +598,31 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit, if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0) goto all_leaves_cluster_together; - /* Otherwise we can just insert a new node ahead of the old - * one. + /* Otherwise all the old leaves cluster in the same slot, but + * the new leaf wants to go into a different slot - so we + * create a new node (n0) to hold the new leaf and a pointer to + * a new node (n1) holding all the old leaves. + * + * This can be done by falling through to the node splitting + * path. */ - goto present_leaves_cluster_but_not_new_leaf; + pr_devel("present leaves cluster but not new leaf\n"); } split_node: pr_devel("split node\n"); - /* We need to split the current node; we know that the node doesn't - * simply contain a full set of leaves that cluster together (it - * contains meta pointers and/or non-clustering leaves). + /* We need to split the current node. The node must contain anything + * from a single leaf (in the one leaf case, this leaf will cluster + * with the new leaf) and the rest meta-pointers, to all leaves, some + * of which may cluster. + * + * It won't contain the case in which all the current leaves plus the + * new leaves want to cluster in the same slot. * * We need to expel at least two leaves out of a set consisting of the - * leaves in the node and the new leaf. + * leaves in the node and the new leaf. The current meta pointers can + * just be copied as they shouldn't cluster with any of the leaves. * * We need a new node (n0) to replace the current one and a new node to * take the expelled nodes (n1). @@ -717,33 +727,6 @@ found_slot_for_multiple_occupancy: pr_devel("<--%s() = ok [split node]\n", __func__); return true; -present_leaves_cluster_but_not_new_leaf: - /* All the old leaves cluster in the same slot, but the new leaf wants - * to go into a different slot, so we create a new node to hold the new - * leaf and a pointer to a new node holding all the old leaves. - */ - pr_devel("present leaves cluster but not new leaf\n"); - - new_n0->back_pointer = node->back_pointer; - new_n0->parent_slot = node->parent_slot; - new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch; - new_n1->back_pointer = assoc_array_node_to_ptr(new_n0); - new_n1->parent_slot = edit->segment_cache[0]; - new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch; - edit->adjust_count_on = new_n0; - - for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) - new_n1->slots[i] = node->slots[i]; - - new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0); - edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]]; - - edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot]; - edit->set[0].to = assoc_array_node_to_ptr(new_n0); - edit->excised_meta[0] = assoc_array_node_to_ptr(node); - pr_devel("<--%s() = ok [insert node before]\n", __func__); - return true; - all_leaves_cluster_together: /* All the leaves, new and old, want to cluster together in this node * in the same slot, so we have to replace this node with a shortcut to |