Skip to content

fix_extra_red() crashes when inserting duplicate of root node #14

@devarajabc

Description

@devarajabc

Description

Inserting a duplicate node whose pointer matches the root node causes a crash due to invalid stack indexing in fix_extra_red().

This happens when the inserted node is:

  • The same pointer as the root node, i.e., a repeated insertion of an identical rb_node_t*, and

  • The node is recolored to red again as part of rb_insert(), and

  • fix_extra_red() is triggered with a stack like [root, root] → stacksz == 2

/* If the parent is black, the tree is already balanced. */
if (likely(is_black(parent)))
    return;
rb_node_t *grandparent = stack[stacksz - 3];

Because the node was forced red earlier, parent is not black, so the function proceeds — but stacksz == 2, and the next line accesses stack[stacksz - 3], which is stack[-1] — undefined behavior.

Steps to Reproduce

  1. Build with AddressSanitizer enabled
  2. In rb-perf.c, after the initial insert loop, insert the following code:
/* Insert nodes */
for (int i = 0; i < count; i++) {
    rb_insert(&tree, &test_nodes[i].node);
}

int root_id = container_of(tree.root, struct perf_node, node)->key;

// Trigger crash by re-inserting the root node 
rb_insert(&tree, &test_nodes[root_id].node);

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions