| 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 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <cfa05198-9ab0-3529-bc1f-08d8035a435c@gmail.com>
Date: Fri, 28 Apr 2023 14:48:13 +0800
From: Peng Zhang <perlyzhang@...il.com>
To: "Liam R. Howlett" <Liam.Howlett@...cle.com>
Cc: linux-kernel@...r.kernel.org, linux-mm@...ck.org,
maple-tree@...ts.infradead.org,
Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface
在 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@...cle.com>
> ---
> 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.
> +
> 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;
Powered by blists - more mailing lists