Re: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface

From: Liam R. Howlett
Date: Wed May 03 2023 - 15:31:41 EST

Next message: Liam R. Howlett: "Re: [PATCH 10/34] maple_tree: Use MAS_BUG_ON() when setting a leaf node as a parent"
Previous message: Mathieu Desnoyers: "[RFC PATCH] selftests/rseq: Fix CID_ID typo in Makefile"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

* Peng Zhang <perlyzhang@xxxxxxxxx> [230428 02:48]:
>
>
> 在 2023/4/25 22:09, Liam R. Howlett 写道:
> > Sometimes, during a tree walk, the user needs the next slot regardless
> > of if it is empty or not. Add an interface to get the next slot.
> >
> > Since there are no consecutive NULLs allowed in the tree, the mas_next()
> > function can only advance two slots at most. So use the new
> > mas_next_slot() interface to align both implementations.
> >
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> > ---
> > lib/maple_tree.c | 178 +++++++++++++++++++----------------------------
> > 1 file changed, 71 insertions(+), 107 deletions(-)
> >
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 31cbfd7b44728..fe6c9da6f2bd5 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
> > if (mas->max >= max)
> > goto no_entry;
> > + min = mas->max + 1;
> > + if (min > max)
> > + goto no_entry;
> Unnecessary check due to mas->max < max.

Thanks, I will address this in v2.

> > +
> > level = 0;
> > do {
> > if (ma_is_root(node))
> > goto no_entry;
> > - min = mas->max + 1;
> > - if (min > max)
> > - goto no_entry;
> > -
> > + /* Walk up. */
> > if (unlikely(mas_ascend(mas)))
> > return 1;
> > @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
> > slots = ma_slots(node, mt);
> > pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
> > while (unlikely(level > 1)) {
> > - /* Descend, if necessary */
> > + level--;
> > enode = mas_slot(mas, slots, offset);
> > if (unlikely(ma_dead_node(node)))
> > return 1;
> > mas->node = enode;
> > - level--;
> > node = mas_mn(mas);
> > mt = mte_node_type(mas->node);
> > slots = ma_slots(node, mt);
> > @@ -4680,85 +4680,84 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
> > return 0;
> > }
> > +static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
> > +{
> > +retry:
> > + mas_set(mas, index);
> > + mas_state_walk(mas);
> > + if (mas_is_start(mas))
> > + goto retry;
> > +}
> > +
> > +static inline bool mas_rewalk_if_dead(struct ma_state *mas,
> > + struct maple_node *node, const unsigned long index)
> > +{
> > + if (unlikely(ma_dead_node(node))) {
> > + mas_rewalk(mas, index);
> > + return true;
> > + }
> > + return false;
> > +}
> > +
> > /*
> > - * mas_next_nentry() - Get the next node entry
> > - * @mas: The maple state
> > - * @max: The maximum value to check
> > - * @*range_start: Pointer to store the start of the range.
> > + * mas_next_slot() - Get the entry in the next slot
> > *
> > - * Sets @mas->offset to the offset of the next node entry, @mas->last to the
> > - * pivot of the entry.
> > + * @mas: The maple state
> > + * @max: The maximum starting range
> > *
> > - * Return: The next entry, %NULL otherwise
> > + * Return: The entry in the next slot which is possibly NULL
> > */
> > -static inline void *mas_next_nentry(struct ma_state *mas,
> > - struct maple_node *node, unsigned long max, enum maple_type type)
> > +void *mas_next_slot(struct ma_state *mas, unsigned long max)
> > {
> > - unsigned char count;
> > - unsigned long pivot;
> > - unsigned long *pivots;
> > void __rcu **slots;
> > + unsigned long *pivots;
> > + unsigned long pivot;
> > + enum maple_type type;
> > + struct maple_node *node;
> > + unsigned char data_end;
> > + unsigned long save_point = mas->last;
> > void *entry;
> > - if (mas->last == mas->max) {
> > - mas->index = mas->max;
> > - return NULL;
> > - }
> > -
> > - slots = ma_slots(node, type);
> > +retry:
> > + node = mas_mn(mas);
> > + type = mte_node_type(mas->node);
> > pivots = ma_pivots(node, type);
> > - count = ma_data_end(node, type, pivots, mas->max);
> > - if (unlikely(ma_dead_node(node)))
> > - return NULL;
> > -
> > - mas->index = mas_safe_min(mas, pivots, mas->offset);
> > - if (unlikely(ma_dead_node(node)))
> > - return NULL;
> > -
> > - if (mas->index > max)
> > - return NULL;
> > + data_end = ma_data_end(node, type, pivots, mas->max);
> > + pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
> > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > + goto retry;
> > - if (mas->offset > count)
> > + if (pivot >= max)
> > return NULL;
> > - while (mas->offset < count) {
> > - pivot = pivots[mas->offset];
> > - entry = mas_slot(mas, slots, mas->offset);
> > - if (ma_dead_node(node))
> > - return NULL;
> > -
> > - mas->last = pivot;
> > - if (entry)
> > - return entry;
> > -
> > - if (pivot >= max)
> > - return NULL;
> > + if (likely(data_end > mas->offset)) {
> > + mas->offset++;
> > + mas->index = mas->last + 1;
> > + } else {
> > + if (mas_next_node(mas, node, max)) {
> > + mas_rewalk(mas, save_point);
> > + goto retry;
> > + }
> > - if (pivot >= mas->max)
> > + if (mas_is_none(mas))
> > return NULL;
> > - mas->index = pivot + 1;
> > - mas->offset++;
> > + mas->offset = 0;
> > + mas->index = mas->min;
> > + node = mas_mn(mas);
> > + type = mte_node_type(mas->node);
> > + pivots = ma_pivots(node, type);
> > }
> > - pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
> > + slots = ma_slots(node, type);
> > + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type);
> > entry = mas_slot(mas, slots, mas->offset);
> > - if (ma_dead_node(node))
> > - return NULL;
> > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > + goto retry;
> > - mas->last = pivot;
> > return entry;
> > }
> > -static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
> > -{
> > -retry:
> > - mas_set(mas, index);
> > - mas_state_walk(mas);
> > - if (mas_is_start(mas))
> > - goto retry;
> > -}
> > -
> > /*
> > * mas_next_entry() - Internal function to get the next entry.
> > * @mas: The maple state
> > @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
> > static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
> > {
> > void *entry = NULL;
> > - struct maple_node *node;
> > - unsigned long last;
> > - enum maple_type mt;
> > if (mas->last >= limit)
> > return NULL;
> > - last = mas->last;
> > -retry:
> > - node = mas_mn(mas);
> > - mt = mte_node_type(mas->node);
> > - mas->offset++;
> > - if (unlikely(mas->offset >= mt_slots[mt])) {
> > - mas->offset = mt_slots[mt] - 1;
> > - goto next_node;
> > - }
> > -
> > - while (!mas_is_none(mas)) {
> > - entry = mas_next_nentry(mas, node, limit, mt);
> > - if (unlikely(ma_dead_node(node))) {
> > - mas_rewalk(mas, last);
> > - goto retry;
> > - }
> > -
> > - if (likely(entry))
> > - return entry;
> > -
> > - if (unlikely((mas->last >= limit)))
> > - return NULL;
> > + entry = mas_next_slot_limit(mas, limit);
> > + if (entry)
> > + return entry;
> > -next_node:
> > - if (unlikely(mas_next_node(mas, node, limit))) {
> > - mas_rewalk(mas, last);
> > - goto retry;
> > - }
> > - mas->offset = 0;
> > - node = mas_mn(mas);
> > - mt = mte_node_type(mas->node);
> > - }
> > + if (mas_is_none(mas))
> > + return NULL;
> > - return NULL;
> > + return mas_next_slot_limit(mas, limit);
> > }
> > /*
> > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> > slots = ma_slots(mn, mt);
> > pivots = ma_pivots(mn, mt);
> > count = ma_data_end(mn, mt, pivots, mas->max);
> > - if (unlikely(ma_dead_node(mn))) {
> > - mas_rewalk(mas, index);
> > + if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > goto retry;
> > - }
> > offset = mas->offset - 1;
> > if (offset >= mt_slots[mt])
> > @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> > pivot = pivots[offset];
> > }
> > - if (unlikely(ma_dead_node(mn))) {
> > - mas_rewalk(mas, index);
> > + if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > goto retry;
> > - }
> > while (offset && !mas_slot(mas, slots, offset)) {
> > pivot = pivots[--offset];
> > @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> > min = mas_safe_min(mas, pivots, offset);
> > entry = mas_slot(mas, slots, offset);
> > - if (unlikely(ma_dead_node(mn))) {
> > - mas_rewalk(mas, index);
> > + if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > goto retry;
> > - }
> > mas->offset = offset;
> > mas->last = pivot;

Next message: Liam R. Howlett: "Re: [PATCH 10/34] maple_tree: Use MAS_BUG_ON() when setting a leaf node as a parent"
Previous message: Mathieu Desnoyers: "[RFC PATCH] selftests/rseq: Fix CID_ID typo in Makefile"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]