[ClusterLabs/libqb] 44a937: skiplist: fix use-after-free in the skiplist trave...

[Christine Caulfield]

  Branch: refs/heads/master
  Home:   https://github.com/ClusterLabs/libqb
  Commit: 44a9379c89e2fd0a2d09df79e2a3eaf1d1b4a5c7
     
https://github.com/ClusterLabs/libqb/commit/44a9379c89e2fd0a2d09df79e2a3e...
  Author: Christine Caulfield <ccaulfie(a)redhat.com&gt;
  Date:   2018-10-15 (Mon, 15 Oct 2018)

  Changed paths:
    M lib/skiplist.c
    M tests/check_map.c

  Log Message:
  -----------
  skiplist: fix use-after-free in the skiplist traversal

(Patch from poki, only committed under my name because github is being
weird)

This used to happen when an iterator contained a reference on the item
to continue with, which got outdated when such item had been removed in
the interim, though it's original memory would still be -- mistakenly --
accessed. Actually such a condition is exercised with an existing
"test_map_iter_safety(ordered=true)" test, though it likely never run
under valgrind's supervision and standard memory checking harness was
too coarse (perhaps because of low memory pressure or other "lucky"
coincidence). Thankfully, the default, paranoid approach towards dynamic
memory handling in OpenBSD (free(3) call makes small chunks "junked",
i.e., filled with 0xdf bytes, see malloc.conf(5)) resulted in the
explicit segmentation fault when tripping over the happens-to-be-freed
pointer in the assumed iteration chain.

We solve the "out-of-sync iterator" issue with a twist, inverting
the responsibility to carry (and more widely, to contribute in the
propagation of) the up-to-date "forward" pointers, as clearly,
iterating over and over through the items would not be very scalable
(and it was not done, which had resulted in the first place).
So now, when any skiplist item is to be removed, its preceding item
gets the "forward" pointers recomputed as before, but then, they are
copied into "forward" pointers for the item to be removed, original
area containing them is disposed, and this preceding item just points
to the area primarily managed by the to-be-removed item (procedure
dubbed "takeover-and-repoint" in the comment). This itself gets
a special mark so that this area won't be dropped when that item gets
disposed, which rather happens with the disposal of the preceding item
that points to the "forward" memory area at hand and is not marked so.
This is believed to be sufficient to address out-of-band (iterator
based) access versus interim future iteration chain mangling, as these
operate de facto on the non-sparse, linear level of the skiplist.

Alternative approaches include:

    turning pointers-to-arrays into pointers-to-pointers-to-arrays to
    allow for explicit setting to NULL after free, and sharing this
    additional indirection -- this straightforward extension was
    attempted first, but shortly after, it became apparent it would
    be a nightmare with the current interprocedural dependencies

    extra tagging of the structures and adding complexities around
    checking the eligibility, like every other manipulation with the
    skiplist

    completely split life-cycle of "node" and "node->forward",
i.e.,
    separate reference-counting etc.

Also said test was extended to push the corner case to the limit:
when to-resume-with item in the chain is being figured out, the
predecessors may be consulted (it is in that test), but the very
first predecessor is now removed as well, for good measure, as
it makes for boundary condition ^ 2.

Signed-off-by: Jan Pokorný jpokorny(a)redhat.com



      **NOTE:** This service has been marked for deprecation:
https://developer.github.com/changes/2018-04-25-github-services-deprecation/

      Functionality will be removed from GitHub.com on January 31st, 2019.