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

Next we insert the entry ptr0 (0x4) into the tree and tag it with TAG 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

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

In this case segfault is avoided by proceeding with de-referencing the slot only if

Similar is the case for iteration over all contiguous slots, until the first empty slot, via the

In this case segfault is avoided by the following type of check in

The next three tests check the same behavior of

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().*
## No comments:

## Post a Comment