| Message ID | 20180606085239.22499-2-po-hsu.lin@canonical.com |
|---|---|
| State | New |
| Headers | show |
| Series | Fix for CVE-2017-12193 | expand |
On 06.06.2018 01:52, Po-Hsu Lin wrote: > From: David Howells <dhowells@redhat.com> > > CVE-2017-12193 > > BugLink: https://bugs.launchpad.net/bugs/1775316 > > 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: 3cb989501c26 ("Add a generic associative array implementation.") > Reported-and-tested-by: WU Fan <u3536072@connect.hku.hk> > Signed-off-by: David Howells <dhowells@redhat.com> > Cc: stable@vger.kernel.org [v3.13-rc1+] > Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> > (cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b) > Signed-off-by: Po-Hsu Lin <po-hsu.lin@canonical.com> Acked-by: Stefan Bader <stefan.bader@canonical.com> > --- > lib/assoc_array.c | 51 +++++++++++++++++---------------------------------- > 1 file changed, 17 insertions(+), 34 deletions(-) > > diff --git a/lib/assoc_array.c b/lib/assoc_array.c > index afef906..035c236 100644 > --- a/lib/assoc_array.c > +++ b/lib/assoc_array.c > @@ -597,21 +597,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). > @@ -716,33 +726,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 >
On 06/06/18 01:52, Po-Hsu Lin wrote: > From: David Howells <dhowells@redhat.com> > > CVE-2017-12193 > > BugLink: https://bugs.launchpad.net/bugs/1775316 > > 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: 3cb989501c26 ("Add a generic associative array implementation.") > Reported-and-tested-by: WU Fan <u3536072@connect.hku.hk> > Signed-off-by: David Howells <dhowells@redhat.com> > Cc: stable@vger.kernel.org [v3.13-rc1+] > Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> > (cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b) > Signed-off-by: Po-Hsu Lin <po-hsu.lin@canonical.com> Acked-by: Kleber Sacilotto de Souza <kleber.souza@canonical.com> > --- > lib/assoc_array.c | 51 +++++++++++++++++---------------------------------- > 1 file changed, 17 insertions(+), 34 deletions(-) > > diff --git a/lib/assoc_array.c b/lib/assoc_array.c > index afef906..035c236 100644 > --- a/lib/assoc_array.c > +++ b/lib/assoc_array.c > @@ -597,21 +597,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). > @@ -716,33 +726,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 >
diff --git a/lib/assoc_array.c b/lib/assoc_array.c index afef906..035c236 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -597,21 +597,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). @@ -716,33 +726,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