lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date:	Tue, 20 Mar 2012 09:28:09 +0400
From:	Konstantin Khlebnikov <khlebnikov@...nvz.org>
To:	Andrew Morton <akpm@...ux-foundation.org>
CC:	Hugh Dickins <hughd@...gle.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"linux-mm@...ck.org" <linux-mm@...ck.org>
Subject: Re: [PATCH v3] radix-tree: introduce bit-optimized iterator

Andrew Morton wrote:
> On Mon, 19 Mar 2012 09:19:08 +0400
> Konstantin Khlebnikov<khlebnikov@...nvz.org>  wrote:
>
>> This patch implements clean, simple and effective radix-tree iteration routine.
>>
>> Iterating divided into two phases:
>> * search for the next chunk of slots in radix-tree leaf node
>> * iterate through slots in this chunk
>>
>> Main iterator function radix_tree_next_chunk() returns pointer to first slot,
>> and stores in the struct radix_tree_iter index and next-to-last slot for chunk.
>> For tagged-iterating it also construct bit-mask of tags for slots in chunk.
>> All additional logic implemented as static-inline functions and macroses.
>>
>> Also patch adds radix_tree_find_next_bit() static-inline variant of
>> find_next_bit() optimized for small constant size arrays, because
>> find_next_bit() too heavy for searching in an array with one/two long elements.
>>
>> Signed-off-by: Konstantin Khlebnikov<khlebnikov@...nvz.org>
>>
>> ---
>> v3: No functional changes: renaming variables, updating comments, fixing style errors.
>
> Here's what you changed:
>
> --- a/include/linux/radix-tree.h~radix-tree-introduce-bit-optimized-iterator-v3
> +++ a/include/linux/radix-tree.h
> @@ -258,28 +258,76 @@ static inline void radix_tree_preload_en
>          preempt_enable();
>   }
>
> +/**
> + * struct radix_tree_iter - radix tree iterator state
> + *
> + * @index:     index of current slot
> + * @next_index:        next-to-last index for this chunk
> + * @tags:      bit-mask for tag-iterating
> + *
> + * Radix tree iterator works in terms of "chunks" of slots.
> + * Chunk is sub-interval of slots contained in one radix tree leaf node.
> + * It described by pointer to its first slot and struct radix_tree_iter
> + * which holds chunk position in tree and its size. For tagged iterating
> + * radix_tree_iter also holds slots' bit-mask for one chosen radix tree tag.
> + */
>   struct radix_tree_iter {
> -       unsigned long   index;          /* current index, do not overflow it */
> -       unsigned long   next_index;     /* next-to-last index for this chunk */
> -       unsigned long   tags;           /* bitmask for tag-iterating */
> +       unsigned long   index;
> +       unsigned long   next_index;
> +       unsigned long   tags;
>   };
>
>   #define RADIX_TREE_ITER_TAG_MASK       0x00FF  /* tag index in lower byte */
>   #define RADIX_TREE_ITER_TAGGED         0x0100  /* lookup tagged slots */
>   #define RADIX_TREE_ITER_CONTIG         0x0200  /* stop at first hole */
>
> -void **radix_tree_next_chunk(struct radix_tree_root *root,
> -                            struct radix_tree_iter *iter, unsigned flags);
> -
> -static inline
> -void **radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
> +/**
> + * radix_tree_iter_init - initialize radix tree iterator
> + *
> + * @iter:      pointer to iterator state
> + * @start:     iteration starting index
> + * Returns:    NULL
> + */
> +static __always_inline void **
> +radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
>   {
> -       iter->index = 0; /* to bypass next_index overflow protection */
> +       /*
> +        * Leave iter->tags unitialized. radix_tree_next_chunk()
> +        * anyway fill it in case successful tagged chunk lookup.
> +        * At unsuccessful or non-tagged lookup nobody cares about it.
> +        *
> +        * Set index to zero to bypass next_index overflow protection.
> +        * See comment inside radix_tree_next_chunk() for details.
> +        */
> +       iter->index = 0;
>          iter->next_index = start;
>          return NULL;
>   }
>
> -static inline unsigned long radix_tree_chunk_size(struct radix_tree_iter *iter)
> +/**
> + * radix_tree_next_chunk - find next chunk of slots for iteration
> + *
> + * @root:      radix tree root
> + * @iter:      iterator state
> + * @flags:     RADIX_TREE_ITER_* flags and tag index
> + * Returns:    pointer to chunk first slot, or NULL if there no more left
> + *
> + * This function lookup next chunk in the radix tree starting from
> + * @iter->next_index, it returns pointer to chunk first slot.
> + * Also it fills @iter with data about chunk: position in the tree (index),
> + * its end (next_index), and construct bit mask for tagged iterating (tags).
> + */
> +void **radix_tree_next_chunk(struct radix_tree_root *root,
> +                            struct radix_tree_iter *iter, unsigned flags);
> +
> +/**
> + * radix_tree_chunk_size - get current chunk size
> + *
> + * @iter:      pointer to radix tree iterator
> + * Returns:    current chunk size
> + */
> +static __always_inline unsigned
> +radix_tree_chunk_size(struct radix_tree_iter *iter)
>   {
>          return iter->next_index - iter->index;
>   }
> @@ -287,41 +335,40 @@ static inline unsigned long radix_tree_c
>   /**
>    * radix_tree_next_slot - find next slot in chunk
>    *
> - * @slot       pointer to slot
> - * @iter       iterator state
> - * @flags      RADIX_TREE_ITER_*
> - *
> - * Returns pointer to next slot, or NULL if no more left.
> - */
> -static __always_inline
> -void **radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> -                           unsigned flags)
> + * @slot:      pointer to current slot
> + * @iter:      pointer to interator state
> + * @flags:     RADIX_TREE_ITER_*, should be constant
> + * Returns:    pointer to next slot, or NULL if there no more left
> + *
> + * This function updates @iter->index in case successful lookup.
> + * For tagged lookup it also eats @iter->tags.
> + */
> +static __always_inline void **
> +radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
>   {
> -       unsigned size, offset;
> -
> -       size = radix_tree_chunk_size(iter) - 1;
>          if (flags&  RADIX_TREE_ITER_TAGGED) {
>                  iter->tags>>= 1;
>                  if (likely(iter->tags&  1ul)) {
>                          iter->index++;
>                          return slot + 1;
>                  }
> -               if ((flags&  RADIX_TREE_ITER_CONTIG)&&  size)
> -                       return NULL;
> -               if (likely(iter->tags)) {
> -                       offset = __ffs(iter->tags);
> +               if (!(flags&  RADIX_TREE_ITER_CONTIG)&&  likely(iter->tags)) {
> +                       unsigned offset = __ffs(iter->tags);
> +
>                          iter->tags>>= offset;
>                          iter->index += offset + 1;
>                          return slot + offset + 1;
>                  }
>          } else {
> +               unsigned size = radix_tree_chunk_size(iter) - 1;
> +
>                  while (size--) {
>                          slot++;
>                          iter->index++;
>                          if (likely(*slot))
>                                  return slot;
>                          if (flags&  RADIX_TREE_ITER_CONTIG)
> -                               return NULL;
> +                               break;
>                  }
>          }
>          return NULL;
> @@ -330,70 +377,79 @@ void **radix_tree_next_slot(void **slot,
>   /**
>    * radix_tree_for_each_chunk - iterate over chunks
>    *
> - * @slot:      the void** for pointer to chunk first slot
> - * @root       the struct radix_tree_root pointer
> - * @iter       the struct radix_tree_iter pointer
> - * @start      starting index
> - * @flags      RADIX_TREE_ITER_* and tag index
> + * @slot:      the void** variable for pointer to chunk first slot
> + * @root:      the struct radix_tree_root pointer
> + * @iter:      the struct radix_tree_iter pointer
> + * @start:     iteration starting index
> + * @flags:     RADIX_TREE_ITER_* and tag index
>    *
> - * Locks can be released and reasquired between iterations.
> + * Locks can be released and reacquired between iterations.
>    */
>   #define radix_tree_for_each_chunk(slot, root, iter, start, flags)      \
> -       for ( slot = radix_tree_iter_init(iter, start) ;                \
> -             (slot = radix_tree_next_chunk(root, iter, flags)) ; )
> +       for (slot = radix_tree_iter_init(iter, start) ;                 \
> +             (slot = radix_tree_next_chunk(root, iter, flags)) ;)
>
>   /**
>    * radix_tree_for_each_chunk_slot - iterate over slots in one chunk
>    *
> - * @slot:      the void** for pointer to slot
> - * @iter       the struct radix_tree_iter pointer
> - * @flags      RADIX_TREE_ITER_*
> + * @slot:      the void** variable, at the beginning points to chunk first slot
> + * @iter:      the struct radix_tree_iter pointer
> + * @flags:     RADIX_TREE_ITER_*, should be constant
> + *
> + * This macro supposed to be nested inside radix_tree_for_each_chunk().
> + * @slot points to radix tree slot, @iter->index contains its index.
>    */
> -#define radix_tree_for_each_chunk_slot(slot, iter, flags)      \
> -       for ( ; slot ; slot = radix_tree_next_slot(slot, iter, flags) )
> +#define radix_tree_for_each_chunk_slot(slot, iter, flags)              \
> +       for (; slot ; slot = radix_tree_next_slot(slot, iter, flags))
>
>   /**
> - * radix_tree_for_each_slot - iterate over all slots
> + * radix_tree_for_each_slot - iterate over non-empty slots
>    *
> - * @slot:      the void** for pointer to slot
> - * @root       the struct radix_tree_root pointer
> - * @iter       the struct radix_tree_iter pointer
> - * @start      starting index
> + * @slot:      the void** variable for pointer to slot
> + * @root:      the struct radix_tree_root pointer
> + * @iter:      the struct radix_tree_iter pointer
> + * @start:     iteration starting index
> + *
> + * @slot points to radix tree slot, @iter->index contains its index.
>    */
> -#define radix_tree_for_each_slot(slot, root, iter, start)      \
> -       for ( slot = radix_tree_iter_init(iter, start) ;        \
> -             slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
> -             slot = radix_tree_next_slot(slot, iter, 0) )
> +#define radix_tree_for_each_slot(slot, root, iter, start)              \
> +       for (slot = radix_tree_iter_init(iter, start) ;                 \
> +            slot || (slot = radix_tree_next_chunk(root, iter, 0)) ;    \
> +            slot = radix_tree_next_slot(slot, iter, 0))
>
>   /**
> - * radix_tree_for_each_contig - iterate over all contiguous slots
> + * radix_tree_for_each_contig - iterate over contiguous slots
> + *
> + * @slot:      the void** variable for pointer to slot
> + * @root:      the struct radix_tree_root pointer
> + * @iter:      the struct radix_tree_iter pointer
> + * @start:     iteration starting index
>    *
> - * @slot:      the void** for pointer to slot
> - * @root       the struct radix_tree_root pointer
> - * @iter       the struct radix_tree_iter pointer
> - * @start      starting index
> + * @slot points to radix tree slot, @iter->index contains its index.
>    */
>   #define radix_tree_for_each_contig(slot, root, iter, start)            \
> -       for ( slot = radix_tree_iter_init(iter, start) ;                \
> -             slot || (slot = radix_tree_next_chunk(root, iter,         \
> +       for (slot = radix_tree_iter_init(iter, start) ;                 \
> +            slot || (slot = radix_tree_next_chunk(root, iter,          \
>                                  RADIX_TREE_ITER_CONTIG)) ;              \
> -             slot = radix_tree_next_slot(slot, iter,                   \
> -                               RADIX_TREE_ITER_CONTIG) )
> +            slot = radix_tree_next_slot(slot, iter,                    \
> +                               RADIX_TREE_ITER_CONTIG))
>
>   /**
> - * radix_tree_for_each_tagged - iterate over all tagged slots
> + * radix_tree_for_each_tagged - iterate over tagged slots
> + *
> + * @slot:      the void** variable for pointer to slot
> + * @root:      the struct radix_tree_root pointer
> + * @iter:      the struct radix_tree_iter pointer
> + * @start:     iteration starting index
> + * @tag:       tag index
>    *
> - * @slot:      the void** for pointer to slot
> - * @root       the struct radix_tree_root pointer
> - * @iter       the struct radix_tree_iter pointer
> - * @start      starting index
> - * @tag                tag index
> + * @slot points to radix tree slot, @iter->index contains its index.
>    */
>   #define radix_tree_for_each_tagged(slot, root, iter, start, tag)       \
> -       for ( slot = radix_tree_iter_init(iter, start) ;                \
> -             slot || (slot = radix_tree_next_chunk(root, iter,         \
> +       for (slot = radix_tree_iter_init(iter, start) ;                 \
> +            slot || (slot = radix_tree_next_chunk(root, iter,          \
>                                RADIX_TREE_ITER_TAGGED | tag)) ;          \
> -             slot = radix_tree_next_slot(slot, iter,                   \
> -                               RADIX_TREE_ITER_TAGGED) )
> +            slot = radix_tree_next_slot(slot, iter,                    \
> +                               RADIX_TREE_ITER_TAGGED))
>
>   #endif /* _LINUX_RADIX_TREE_H */
> diff -puN lib/radix-tree.c~radix-tree-introduce-bit-optimized-iterator-v3 lib/radix-tree.c
> --- a/lib/radix-tree.c~radix-tree-introduce-bit-optimized-iterator-v3
> +++ a/lib/radix-tree.c
> @@ -150,6 +150,7 @@ static inline int any_tag_set(struct rad
>
>   /**
>    * radix_tree_find_next_bit - find the next set bit in a memory region
> + *
>    * @addr: The address to base the search on
>    * @size: The bitmap size in bits
>    * @offset: The bitnumber to start searching at
> @@ -158,8 +159,9 @@ static inline int any_tag_set(struct rad
>    * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
>    * Returns next bit offset, or size if nothing found.
>    */
> -static inline unsigned long radix_tree_find_next_bit(const unsigned long *addr,
> -               unsigned long size, unsigned long offset)
> +static __always_inline unsigned long
> +radix_tree_find_next_bit(const unsigned long *addr,
> +                        unsigned long size, unsigned long offset)
>   {
>          if (!__builtin_constant_p(size))
>                  return find_next_bit(addr, size, offset);
> @@ -651,27 +653,26 @@ EXPORT_SYMBOL(radix_tree_tag_get);
>   /**
>    * radix_tree_next_chunk - find next chunk of slots for iteration
>    *
> - * @root:              radix tree root
> - * @iter:              iterator state
> - * @flags              RADIX_TREE_ITER_* flags and tag index
> - *
> - * Returns pointer to first slots in chunk, or NULL if there no more left
> + * @root:      radix tree root
> + * @iter:      iterator state
> + * @flags:     RADIX_TREE_ITER_* flags and tag index
> + * Returns:    pointer to chunk first slot, or NULL if iteration is over
>    */
>   void **radix_tree_next_chunk(struct radix_tree_root *root,
>                               struct radix_tree_iter *iter, unsigned flags)
>   {
>          unsigned shift, tag = flags&  RADIX_TREE_ITER_TAG_MASK;
>          struct radix_tree_node *rnode, *node;
> -       unsigned long i, index;
> +       unsigned long index, offset;
>
>          if ((flags&  RADIX_TREE_ITER_TAGGED)&&  !root_tag_get(root, tag))
>                  return NULL;
>
>          /*
> -        * Catch next_index overflow after ~0UL.
> -        * iter->index can be zero only at the beginning.
> -        * Because RADIX_TREE_MAP_SHIFT<  BITS_PER_LONG we cannot
> -        * oveflow iter->next_index in single step.
> +        * Catch next_index overflow after ~0UL. iter->index never overflows
> +        * during iterating, it can be zero only at the beginning.
> +        * And we cannot overflow iter->next_index in single step,
> +        * because RADIX_TREE_MAP_SHIFT<  BITS_PER_LONG.
>           */
>          index = iter->next_index;
>          if (!index&&  iter->index)
> @@ -691,34 +692,37 @@ void **radix_tree_next_chunk(struct radi
>
>   restart:
>          shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT;
> -       i = index>>  shift;
> +       offset = index>>  shift;
>
> -       /* Index ouside of the tree */
> -       if (i>= RADIX_TREE_MAP_SIZE)
> +       /* Index outside of the tree */
> +       if (offset>= RADIX_TREE_MAP_SIZE)
>                  return NULL;
>
>          node = rnode;
>          while (1) {
>                  if ((flags&  RADIX_TREE_ITER_TAGGED) ?
> -                               !test_bit(i, node->tags[tag]) :
> -                               !node->slots[i]) {
> +                               !test_bit(offset, node->tags[tag]) :
> +                               !node->slots[offset]) {
>                          /* Hole detected */
>                          if (flags&  RADIX_TREE_ITER_CONTIG)
>                                  return NULL;
>
>                          if (flags&  RADIX_TREE_ITER_TAGGED)
> -                               i = radix_tree_find_next_bit(node->tags[tag],
> -                                               RADIX_TREE_MAP_SIZE, i + 1);
> +                               offset = radix_tree_find_next_bit(
> +                                               node->tags[tag],
> +                                               RADIX_TREE_MAP_SIZE,
> +                                               offset + 1);
>                          else
> -                               while (++i<  RADIX_TREE_MAP_SIZE&&
> -                                               !node->slots[i]);
> -
> +                               while (++offset<  RADIX_TREE_MAP_SIZE) {
> +                                       if (node->slots[offset])
> +                                               break;
> +                               }
>                          index&= ~((RADIX_TREE_MAP_SIZE<<  shift) - 1);
> -                       index += i<<  shift;
> +                       index += offset<<  shift;
>                          /* Overflow after ~0UL */
>                          if (!index)
>                                  return NULL;
> -                       if (i == RADIX_TREE_MAP_SIZE)
> +                       if (offset == RADIX_TREE_MAP_SIZE)
>                                  goto restart;
>                  }
>
> @@ -726,23 +730,23 @@ restart:
>                  if (!shift)
>                          break;
>
> -               node = rcu_dereference_raw(node->slots[i]);
> +               node = rcu_dereference_raw(node->slots[offset]);
>                  if (node == NULL)
>                          goto restart;
>                  shift -= RADIX_TREE_MAP_SHIFT;
> -               i = (index>>  shift)&  RADIX_TREE_MAP_MASK;
> +               offset = (index>>  shift)&  RADIX_TREE_MAP_MASK;
>          }
>
>          /* Update the iterator state */
>          iter->index = index;
>          iter->next_index = (index | RADIX_TREE_MAP_MASK) + 1;
>
> -       /* Construct iter->tags bitmask from node->tags[tag] array */
> +       /* Construct iter->tags bit-mask from node->tags[tag] array */
>          if (flags&  RADIX_TREE_ITER_TAGGED) {
>                  unsigned tag_long, tag_bit;
>
> -               tag_long = i / BITS_PER_LONG;
> -               tag_bit  = i % BITS_PER_LONG;
> +               tag_long = offset / BITS_PER_LONG;
> +               tag_bit  = offset % BITS_PER_LONG;
>                  iter->tags = node->tags[tag][tag_long]>>  tag_bit;
>                  /* This never happens if RADIX_TREE_TAG_LONGS == 1 */
>                  if (tag_long<  RADIX_TREE_TAG_LONGS - 1) {
> @@ -755,7 +759,7 @@ restart:
>                  }
>          }
>
> -       return node->slots + i;
> +       return node->slots + offset;
>   }
>   EXPORT_SYMBOL(radix_tree_next_chunk);
>
> _
>
>
>
> And here are some changes I made to that:
>
> --- a/include/linux/radix-tree.h~radix-tree-introduce-bit-optimized-iterator-v3-fix
> +++ a/include/linux/radix-tree.h
> @@ -265,11 +265,12 @@ static inline void radix_tree_preload_en
>    * @next_index:        next-to-last index for this chunk
>    * @tags:      bit-mask for tag-iterating
>    *
> - * Radix tree iterator works in terms of "chunks" of slots.
> - * Chunk is sub-interval of slots contained in one radix tree leaf node.
> - * It described by pointer to its first slot and struct radix_tree_iter
> - * which holds chunk position in tree and its size. For tagged iterating
> - * radix_tree_iter also holds slots' bit-mask for one chosen radix tree tag.
> + * This radix tree iterator works in terms of "chunks" of slots.  A chunk is a
> + * subinterval of slots contained within one radix tree leaf node.  It is
> + * described by a pointer to its first slot and a struct radix_tree_iter
> + * which holds the chunk's position in the tree and its size.  For tagged
> + * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
> + * radix tree tag.
>    */
>   struct radix_tree_iter {
>          unsigned long   index;
> @@ -292,12 +293,12 @@ static __always_inline void **
>   radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
>   {
>          /*
> -        * Leave iter->tags unitialized. radix_tree_next_chunk()
> -        * anyway fill it in case successful tagged chunk lookup.
> -        * At unsuccessful or non-tagged lookup nobody cares about it.
> +        * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
> +        * in the case of a successful tagged chunk lookup.  If the lookup was
> +        * unsuccessful or non-tagged then nobody cares about ->tags.
>           *
>           * Set index to zero to bypass next_index overflow protection.
> -        * See comment inside radix_tree_next_chunk() for details.
> +        * See the comment in radix_tree_next_chunk() for details.
>           */
>          iter->index = 0;
>          iter->next_index = start;
> @@ -312,10 +313,10 @@ radix_tree_iter_init(struct radix_tree_i
>    * @flags:     RADIX_TREE_ITER_* flags and tag index
>    * Returns:    pointer to chunk first slot, or NULL if there no more left
>    *
> - * This function lookup next chunk in the radix tree starting from
> - * @iter->next_index, it returns pointer to chunk first slot.
> + * This function looks up the next chunk in the radix tree starting from
> + * @iter->next_index.  It returns a pointer to the chunk's first slot.
>    * Also it fills @iter with data about chunk: position in the tree (index),
> - * its end (next_index), and construct bit mask for tagged iterating (tags).
> + * its end (next_index), and constructs a bit mask for tagged iterating (tags).
>    */
>   void **radix_tree_next_chunk(struct radix_tree_root *root,
>                               struct radix_tree_iter *iter, unsigned flags);
> @@ -340,7 +341,7 @@ radix_tree_chunk_size(struct radix_tree_
>    * @flags:     RADIX_TREE_ITER_*, should be constant
>    * Returns:    pointer to next slot, or NULL if there no more left
>    *
> - * This function updates @iter->index in case successful lookup.
> + * This function updates @iter->index in the case of a successful lookup.
>    * For tagged lookup it also eats @iter->tags.
>    */
>   static __always_inline void **
> @@ -396,8 +397,8 @@ radix_tree_next_slot(void **slot, struct
>    * @iter:      the struct radix_tree_iter pointer
>    * @flags:     RADIX_TREE_ITER_*, should be constant
>    *
> - * This macro supposed to be nested inside radix_tree_for_each_chunk().
> - * @slot points to radix tree slot, @iter->index contains its index.
> + * This macro is designed to be nested inside radix_tree_for_each_chunk().
> + * @slot points to the radix tree slot, @iter->index contains its index.
>    */
>   #define radix_tree_for_each_chunk_slot(slot, iter, flags)              \
>          for (; slot ; slot = radix_tree_next_slot(slot, iter, flags))
> diff -puN lib/radix-tree.c~radix-tree-introduce-bit-optimized-iterator-v3-fix lib/radix-tree.c
> --- a/lib/radix-tree.c~radix-tree-introduce-bit-optimized-iterator-v3-fix
> +++ a/lib/radix-tree.c
> @@ -670,8 +670,8 @@ void **radix_tree_next_chunk(struct radi
>
>          /*
>           * Catch next_index overflow after ~0UL. iter->index never overflows
> -        * during iterating, it can be zero only at the beginning.
> -        * And we cannot overflow iter->next_index in single step,
> +        * during iterating; it can be zero only at the beginning.
> +        * And we cannot overflow iter->next_index in a single step,
>           * because RADIX_TREE_MAP_SHIFT<  BITS_PER_LONG.
>           */
>          index = iter->next_index;
> _
>
>

Yes, I screwed up with the spelling, again =(
Please merge your changes into final patch =)

>
> The comment over radix_tree_next_slot() is a bit terse: "eats
> @iter->tags".  Can you please explain what's going on with iter->tags?
> afacit it gets copied from the radix-tree node's relevant tag field and
> then gets right-shifted as we advance across the radix-tree node, so
> that bit 0 of iter->tags always reflects the state of the tag bit for
> the slot which we're currently processing?

Yes, radix_tree_next_slot() search next tag with __ffs() and shift bits to right.
So bit 0 represent tag for current slot.

Also these is fast-path for testing tag for slot next after current,
because this is much likely case and this test works much faster than __ffs().

Usually bit 0 is set, except case if rcu-protected radix_tree_next_chink() is raced
with it's clearing, so this function saw this bit once in lookup loop. But when it comes
to iter->tags constructing this bit already cleared, but we expose this slot into iteration anyway.
iter->tags is for internal use, so this is ok, but maybe we should document this corner case.

>
> Why was it done this way, rather than simply testing the appropriate
> bit within the radix-tree node's tag?  That would do away with
> iter->tags altogether?
>

Because nested loop (which uses radix_tree_next_slot()) is inlined into outer code,
so here no pointers to radix_tree_node and even its type declaration.

Also this approach makes inlined code smaller and faster, because we prepare data for processing.
On 32-bit systems iterating is little bit twisted, because not all tags fits
into single unsigned long iter->tags field, but it still faster than old implementation.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists