Radix Tree Test Suite Regression Test 3

We start by creating two void pointers ptr0 with value 0x4 and ptr with value 0x8.

void *ptr0 = (void *)4ul;
void *ptr = (void *)8ul;

Next we insert the entry ptr0 (0x4) into the tree and tag it with TAG 0.

radix_tree_insert(&root, 0, ptr0);
radix_tree_tag_set(&root, 0, 0);

Now we begin the tagged iteration. We get the first tagged slot 0x4 at index 0, then insert a new item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
        printv(2, "tagged %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                radix_tree_tag_set(&root, 1, 0);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

radix_tree_iter_retry(&iter) works by updating the iter->next_index to iter->index, iter->tags to 0 and slot to NULL, so that the subsequent call to radix_tree_next_slot() returns NULL and the subsequent call to radix_tree_next_chunk() returns the first slot of the chunk associated with iter, which was the slot for which we needed to repeat the look-up.

static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
        if (flags & RADIX_TREE_ITER_TAGGED) {
                iter->tags >>= 1;
                if (unlikely(!iter->tags))
                        return NULL;
...

However, if care is not taken we can get a segfault if we try to de-reference a NULL slot. This is checked with the if (unlikely(!iter->tags)).

Similar is the case with iteration for all non-empty slots via the radix_tree_for_each_slot(). We start with the tree containing only one item (0x4) at index 0. After looking it up we insert another item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_slot(slot, &root, &iter, 0) {
        printv(2, "slot %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

In this case segfault is avoided by proceeding with de-referencing the slot only if radix_tree_chunk_size(iter) returns a positive value.

static __always_inline long
radix_tree_chunk_size(struct radix_tree_iter *iter)
{
        return (iter->next_index - iter->index) >> iter_shift(iter);
}

radix_tree_iter_retry(&iter) works by updating the iter->next_index to iter->index so count is returned as 0 (for 0 order slots).

Similar is the case for iteration over all contiguous slots, until the first empty slot, via the radix_tree_for_each_contig(). We start with the tree containing only one item (0x4) at index 0. After looking it up we insert another item 0x8 at index 1, so as to trigger radix_tree_deref_retry, as slot at index 0 is moved after the insertion.

radix_tree_for_each_contig(slot, &root, &iter, 0) {
        printv(2, "contig %ld %p\n", iter.index, *slot);
        if (first) {
                radix_tree_insert(&root, 1, ptr);
                first = false;
        }
        if (radix_tree_deref_retry(*slot)) {
                printv(2, "retry at %ld\n", iter.index);
                slot = radix_tree_iter_retry(&iter);
                continue;
        }
}

In this case segfault is avoided by the following type of check in radix_tree_next_slot() and radix_tree_next_chunk().

if (flags & RADIX_TREE_ITER_CONTIG) {
        /* forbid switching to the next chunk */
        iter->next_index = 0;
        break;
}
...
return NULL;

The next three tests check the same behavior of radix_tree_next_slot() to prevent a segfault, the difference here being that the slot is made NULL by radix_tree_iter_resume().