possible miscompile in libarchive's archive_rb.c

[brooksdavis]

I've spent a good bit of the day looking at a crash in bsdcpio. The crash is a length violation in __archive_rb_tree_insert_rebalance where the grandpa is not a struct archive_rb_node * as expected, but is actually the struct archive_rb_tree * root object. The crash occurs at the bottom of this listing when uncle is actually a struct rbt_opts and rb_info is out of bounds in the type-punned object.

static void
__archive_rb_tree_insert_rebalance(struct archive_rb_tree *rbt,
    struct archive_rb_node *self)
{
        struct archive_rb_node * father = RB_FATHER(self);
        struct archive_rb_node * grandpa;
        struct archive_rb_node * uncle;
        unsigned int which;
        unsigned int other;

        if (!RB_RED_P(father))
                return;

        for (;;) {
                /*
                 * We are red and our parent is red, therefore we must have a
                 * grandfather and he must be black.
                 */
                grandpa = RB_FATHER(father);
                which = (father == grandpa->rb_right);
                other = which ^ RB_DIR_OTHER;
                uncle = grandpa->rb_nodes[other];

                if (RB_BLACK_P(uncle))

After quite a lot of debugging, I'm fairly that __archive_rb_tree_insert_node either has undefined behavior I'm not spotting or it's being miscompiled. The part that's confusing is

        if (parent == (struct archive_rb_node *)(void *)&rbt->rbt_root) {
                RB_MARK_BLACK(self);            /* root is always black */
                rebalance = F;
        } else {
                /*
                 * All new nodes are colored red.  We only need to rebalance
                 * if our parent is also red.
                 */
                RB_MARK_RED(self);
                rebalance = RB_RED_P(parent);
        }  
        self->rb_left = parent->rb_nodes[position];
        self->rb_right = parent->rb_nodes[position];
        parent->rb_nodes[position] = self;

        /*
         * Rebalance tree after insertion
         */
        if (rebalance)
                __archive_rb_tree_insert_rebalance(rbt, self);

By inspection in the debugger, parent is a black node (as it should be given the error occurs on the second insertion), but __archive_rb_tree_insert_rebalance gets called anyway. I suspect a problem with RB_RED_P which is defined as

#define RB_FLAG_RED             (uintptr_t)0x1
#define RB_SENTINEL_P(rb)       ((rb) == NULL)
#define RB_RED_P(rb)            (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)

The reproduction case (on a CheriBSD system built with -DWITH_CHERI_PURE) is:

$ uudecode /usr/tests/usr.bin/cpio/test_option_passphrase.zip.uu > test_option_passphrase.zip
$ cpio  -i --passphrase pass1 < test_option_passphrase.zip

[brooksdavis]

In this case, silent promotion of 0 to NULL bit us. Consider this program:

typedef __uintcap_t     uintptr_t;
#define NULL                    (void*)0
#define RB_FLAG_RED             (uintptr_t)0x1
#define RB_SENTINEL_P(rb)       ((rb) == NULL)
#define RB_RED_P(rb)            (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)

struct archive_rb_node {
        struct archive_rb_node *rb_nodes[2];
        /*
         * rb_info contains the two flags and the parent back pointer.
         * We put the two flags in the low two bits since we know that
         * rb_node will have an alignment of 4 or 8 bytes.
         */
        uintptr_t rb_info;
};

int
rb_red_p(struct archive_rb_node* node)
{

        return (RB_RED_P(node));
}

It compiles to:

0000000000000000 <rb_red_p>:

   0:   67bdffe0        daddiu  sp,sp,-32
   4:   ebcbe81b        csd     s8,sp,24(c11)
   8:   03a0f025        move    s8,sp
   c:   48810007        cfromptr        c1,c0,zero
  10:   49c11840        ceq     at,c3,c1
  14:   14200008        bnez    at,38 <rb_red_p+0x38>
  18:   00000000        nop
  1c:   d8430004        clc     c2,zero,64(c3)
  20:   49a11002        cgetoffset      at,c2
  24:   30210001        andi    at,at,0x1
  28:   49a21041        csetoffset      c2,c2,at
  2c:   49a10801        csetoffset      c1,c1,zero
  30:   10000002        b       3c <rb_red_p+0x3c>
  34:   49c21041        cne     v0,c2,c1
  38:   24020000        li      v0,0
  3c:   03c0e825        move    sp,s8
  40:   cbcbe81b        cld     s8,sp,24(c11)
  44:   49008800        cjr     c17
  48:   67bd0020        daddiu  sp,sp,32

The one at 0x34 is always true because it's comparing a NULL pointer (with an offset mysterious re-zeroed) to rb_info with the flags removed. Changing:

#define RB_RED_P(rb)            (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)

to

#define RB_RED_P(rb)            (!RB_SENTINEL_P(rb) && (vaddr_t)((rb)->rb_info & RB_FLAG_RED) != 0)

Fixes the bug.

This argues for being more pedantic about comparing pointers to 0. It might also argue for specifically disallowing implicit promotion from 0 to NULL when the other side of the comparison involves bitwise operations.