Re: [PATCH 29/34] maple_tree: Introduce mas_prev_slot() interface

From: Liam R. Howlett
Date: Wed May 03 2023 - 15:29:25 EST

Next message: Mathieu Desnoyers: "[RFC PATCH] selftests/rseq: Fix CID_ID typo in Makefile"
Previous message: pr-tracker-bot: "Re: [GIT PULL] More power management updates for v6.4-rc1"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

* Peng Zhang <perlyzhang@xxxxxxxxx> [230428 04:27]:
>
>
> 在 2023/4/25 22:09, Liam R. Howlett 写道:
> > Sometimes the user needs to revert to the previous slot, regardless of
> > if it is empty or not. Add an interface to go to the previous slot.
> >
> > Since there can't be two consecutive NULLs in the tree, the mas_prev()
> > function can be implemented by calling mas_prev_slot() a maximum of 2
> > times. Change the underlying interface to use mas_prev_slot() to align
> > the code.
> >
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> > ---
> > lib/maple_tree.c | 217 ++++++++++++++++++++---------------------------
> > 1 file changed, 90 insertions(+), 127 deletions(-)
> >
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 7370d7c12fe3b..297d936321347 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -4498,6 +4498,25 @@ static inline void *mas_insert(struct ma_state *mas, void *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;
> > +}
> > +
> > +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_prev_node() - Find the prev non-null entry at the same level in the
> > * tree. The prev value will be mas->node[mas->offset] or MAS_NONE.
> > @@ -4515,13 +4534,15 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > struct maple_node *node;
> > struct maple_enode *enode;
> > unsigned long *pivots;
> > + unsigned long max;
> > - if (mas_is_none(mas))
> > - return 0;
> > + node = mas_mn(mas);
> > + max = mas->min - 1;
> May underflow.

Thanks, I will address this in v2.

> > + if (max < min)
> > + goto no_entry;
> > level = 0;
> > do {
> > - node = mas_mn(mas);
> > if (ma_is_root(node))
> > goto no_entry;
> > @@ -4530,11 +4551,11 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > return 1;
> > offset = mas->offset;
> > level++;
> > + node = mas_mn(mas);
> > } while (!offset);
> > offset--;
> > mt = mte_node_type(mas->node);
> > - node = mas_mn(mas);
> > slots = ma_slots(node, mt);
> > pivots = ma_pivots(node, mt);
> > if (unlikely(ma_dead_node(node)))
> > @@ -4543,12 +4564,10 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > mas->max = pivots[offset];
> > if (offset)
> > mas->min = pivots[offset - 1] + 1;
> > +
> > if (unlikely(ma_dead_node(node)))
> > return 1;
> > - if (mas->max < min)
> > - goto no_entry_min;
> > -
> > while (level > 1) {
> > level--;
> > enode = mas_slot(mas, slots, offset);
> > @@ -4569,9 +4588,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > if (offset < mt_pivots[mt])
> > mas->max = pivots[offset];
> > -
> > - if (mas->max < min)
> > - goto no_entry;
> > }
> > mas->node = mas_slot(mas, slots, offset);
> > @@ -4584,10 +4600,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > return 0;
> > -no_entry_min:
> > - mas->offset = offset;
> > - if (offset)
> > - mas->min = pivots[offset - 1] + 1;
> > no_entry:
> > if (unlikely(ma_dead_node(node)))
> > return 1;
> > @@ -4596,6 +4608,62 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> > return 0;
> > }
> > +/*
> > + * mas_prev_slot() - Get the entry in the previous slot
> > + *
> > + * @mas: The maple state
> > + * @max: The minimum starting range
> > + *
> > + * Return: The entry in the previous slot which is possibly NULL
> > + */
> > +void *mas_prev_slot(struct ma_state *mas, unsigned long min)
> > +{
> > + void *entry;
> > + void __rcu **slots;
> > + unsigned long pivot;
> > + enum maple_type type;
> > + unsigned long *pivots;
> > + struct maple_node *node;
> > + unsigned long save_point = mas->index;
> > +
> > +retry:
> > + node = mas_mn(mas);
> > + type = mte_node_type(mas->node);
> > + pivots = ma_pivots(node, type);
> > + pivot = mas_safe_min(mas, pivots, mas->offset);
> > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > + goto retry;
> > +
> > + if (pivot <= min)
> > + return NULL;
> > +
> > + if (likely(mas->offset)) {
> > + mas->offset--;
> > + mas->last = mas->index - 1;
> > + } else {
> > + if (mas_prev_node(mas, min)) {
> > + mas_rewalk(mas, save_point);
> > + goto retry;
> > + }
> > +
> > + if (mas_is_none(mas))
> > + return NULL;
> > +
> > + mas->last = mas->max;
> > + node = mas_mn(mas);
> > + type = mte_node_type(mas->node);
> > + pivots = ma_pivots(node, type);
> > + }
> > +
> > + mas->index = mas_safe_min(mas, pivots, mas->offset);
> > + slots = ma_slots(node, type);
> > + entry = mas_slot(mas, slots, mas->offset);
> > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > + goto retry;
> > +
> > + return entry;
> > +}
> > +
> > /*
> > * mas_next_node() - Get the next node at the same level in the tree.
> > * @mas: The maple state
> > @@ -4680,25 +4748,6 @@ 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_slot() - Get the entry in the next slot
> > *
> > @@ -4777,117 +4826,31 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
> > if (mas->last >= limit)
> > return NULL;
> > - entry = mas_next_slot_limit(mas, limit);
> > + entry = mas_next_slot(mas, limit);
> > if (entry)
> > return entry;
> > if (mas_is_none(mas))
> > return NULL;
> > - return mas_next_slot_limit(mas, limit);
> > -}
> > -
> > -/*
> > - * mas_prev_nentry() - Get the previous node entry.
> > - * @mas: The maple state.
> > - * @limit: The lower limit to check for a value.
> > - *
> > - * Return: the entry, %NULL otherwise.
> > - */
> > -static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> > - unsigned long index)
> > -{
> > - unsigned long pivot, min;
> > - unsigned char offset, count;
> > - struct maple_node *mn;
> > - enum maple_type mt;
> > - unsigned long *pivots;
> > - void __rcu **slots;
> > - void *entry;
> > -
> > -retry:
> > - if (!mas->offset)
> > - return NULL;
> > -
> > - mn = mas_mn(mas);
> > - mt = mte_node_type(mas->node);
> > - offset = mas->offset - 1;
> > - slots = ma_slots(mn, mt);
> > - pivots = ma_pivots(mn, mt);
> > - count = ma_data_end(mn, mt, pivots, mas->max);
> > - if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > - goto retry;
> > -
> > - offset = mas->offset - 1;
> > - if (offset >= mt_slots[mt])
> > - offset = mt_slots[mt] - 1;
> > -
> > - if (offset >= count) {
> > - pivot = mas->max;
> > - offset = count;
> > - } else {
> > - pivot = pivots[offset];
> > - }
> > -
> > - if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > - goto retry;
> > -
> > - while (offset && !mas_slot(mas, slots, offset)) {
> > - pivot = pivots[--offset];
> > - if (pivot >= limit)
> > - break;
> > - }
> > -
> > - /*
> > - * If the slot was null but we've shifted outside the limits, then set
> > - * the range to the last NULL.
> > - */
> > - if (unlikely((pivot < limit) && (offset < mas->offset)))
> > - pivot = pivots[++offset];
> > -
> > - min = mas_safe_min(mas, pivots, offset);
> > - entry = mas_slot(mas, slots, offset);
> > - if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > - goto retry;
> > -
> > - mas->offset = offset;
> > - mas->last = pivot;
> > - mas->index = min;
> > - return entry;
> > + return mas_next_slot(mas, limit);
> > }
> > static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
> > {
> > void *entry;
> > - struct maple_enode *prev_enode;
> > - unsigned char prev_offset;
> > if (mas->index < min)
> > return NULL;
> > -retry:
> > - prev_enode = mas->node;
> > - prev_offset = mas->offset;
> > - while (likely(!mas_is_none(mas))) {
> > - entry = mas_prev_nentry(mas, min, mas->index);
> > -
> > - if (likely(entry))
> > - return entry;
> > -
> > - if (unlikely(mas->index <= min))
> > - return NULL;
> > -
> > - if (unlikely(mas_prev_node(mas, min))) {
> > - mas_rewalk(mas, mas->index);
> > - goto retry;
> > - }
> > + entry = mas_prev_slot(mas, min);
> > + if (entry)
> > + return entry;
> > - mas->offset++;
> > - }
> > + if (mas_is_none(mas))
> > + return NULL;
> > - mas->node = prev_enode;
> > - mas->offset = prev_offset;
> > - return NULL;
> > + return mas_prev_slot(mas, min);
> > }
> > /*

Next message: Mathieu Desnoyers: "[RFC PATCH] selftests/rseq: Fix CID_ID typo in Makefile"
Previous message: pr-tracker-bot: "Re: [GIT PULL] More power management updates for v6.4-rc1"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]