linux-kernel - Re: [PATCH v4 04/17] maple_tree: introduce mas_wr_store

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <47463235-bc45-46e2-8d9d-b62c201c6215@oracle.com>
Date: Wed, 25 Sep 2024 14:36:21 -0500
From: Sid Kumar <sidhartha.kumar@...cle.com>
To: Wei Yang <richard.weiyang@...il.com>
Cc: linux-kernel@...r.kernel.org, maple-tree@...ts.infradead.org,
        linux-mm@...ck.org, akpm@...ux-foundation.org, liam.howlett@...cle.com,
        willy@...radead.org, surenb@...gle.com
Subject: Re: [PATCH v4 04/17] maple_tree: introduce mas_wr_store_type()


On 9/25/24 2:33 PM, Sid Kumar wrote:
>
> On 9/24/24 9:04 PM, Wei Yang wrote:
>> On Wed, Aug 14, 2024 at 12:19:31PM -0400, Sidhartha Kumar wrote:
>>
>> Sorry for a late reply, I just see this change.
>>
>>> +
>>> +/*
>>> + * mas_wr_store_type() - Set the store type for a given
>>> + * store operation.
>>> + * @wr_mas: The maple write state
>>> + */
>>> +static inline void mas_wr_store_type(struct ma_wr_state *wr_mas)
>>> +{
>>> +    struct ma_state *mas = wr_mas->mas;
>>> +    unsigned char new_end;
>>> +
>>> +    if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) {
>>> +        mas->store_type = wr_store_root;
>>> +        return;
>>> +    }
>>> +
>>> +    if (unlikely(!mas_wr_walk(wr_mas))) {
>>> +        mas->store_type = wr_spanning_store;
>>> +        return;
>>> +    }
>>> +
>>> +    /* At this point, we are at the leaf node that needs to be 
>>> altered. */
>>> +    mas_wr_end_piv(wr_mas);
>>> +    if (!wr_mas->entry)
>>> +        mas_wr_extend_null(wr_mas);
>>> +
>>> +    new_end = mas_wr_new_end(wr_mas);
>>> +    if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == 
>>> mas->last)) {
>>> +        mas->store_type = wr_exact_fit;
>>> +        return;
>>> +    }
>>> +
>>> +    if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
>>> +        mas->store_type = wr_new_root;
>>> +        return;
>>> +    }
>>> +
>>> +    /* Potential spanning rebalance collapsing a node */
>>> +    if (new_end < mt_min_slots[wr_mas->type]) {
>>> +        if (!mte_is_root(mas->node)) {
>>> +            mas->store_type = wr_rebalance;
>>> +            return;
>>> +        }
>>> +        mas->store_type = wr_node_store;
>>> +        return;
>>> +    }
>> After this check, we are sure new_end >= mt_min_slots[wr_mas->type].
>>
>>> +
>>> +    if (new_end >= mt_slots[wr_mas->type]) {
>>> +        mas->store_type = wr_split_store;
>>> +        return;
>>> +    }
>>> +
>>> +    if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) {
>>> +        mas->store_type = wr_append;
>>> +        return;
>>> +    }
>>> +
>>> +    if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) ||
>>> +        (wr_mas->offset_end - mas->offset == 1))) {
>>> +        mas->store_type = wr_slot_store;
>>> +        return;
>>> +    }
>>> +
>>> +    if (mte_is_root(mas->node) || (new_end >= 
>>> mt_min_slots[wr_mas->type]) ||
>>> +        (mas->mas_flags & MA_STATE_BULK)) {
>> The check (new_end >= mt_min_slots[wr_mas->type]) here seems always 
>> be true.
>>
>> So the if here seems not necessary. Do I miss something?
>
> It is true that at this point new_end >= mt_min_slots[wr_mas->type] 
> must be true but if we remove that check we won't catch this 
> wr_node_store case if !mte_is_root() and !(mas->mas_flags & 
> MA_STATE_BULK).
>
> We could change the default store type to be wr_node_store and get rid 
> of that whole if statement entirely.
>
> This diff passes the tests:
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 
> 4f34e50c92b5..2ae0c4da9d74 100644 --- a/lib/maple_tree.c +++ 
> b/lib/maple_tree.c @@ -4242,14 +4242,7 @@ static inline void 
> mas_wr_store_type(struct ma_wr_state *wr_mas) return; } - if 
> (mte_is_root(mas->node) || (new_end >= mt_min_slots[wr_mas->type]) || 
> - (mas->mas_flags & MA_STATE_BULK)) { - mas->store_type = 
> wr_node_store; - return; - } - - mas->store_type = wr_invalid; - 
> MAS_WARN_ON(mas, 1); + mas->store_type = wr_node_store; }
>
> do you think this makes sense?
>
Sorry this diff wasn't formatted correctly, it should look normal now:

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4f34e50c92b5..2ae0c4da9d74 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4242,14 +4242,7 @@ static inline void mas_wr_store_type(struct 
ma_wr_state *wr_mas)
                 return;
         }

-       if (mte_is_root(mas->node) || (new_end >= 
mt_min_slots[wr_mas->type]) ||
-               (mas->mas_flags & MA_STATE_BULK)) {
-               mas->store_type = wr_node_store;
-               return;
-       }
-
-       mas->store_type = wr_invalid;
-       MAS_WARN_ON(mas, 1);
+       mas->store_type = wr_node_store;
  }

> Thanks,
>
> Sid
>
>>> +        mas->store_type = wr_node_store;
>>> +        return;
>>> +    }
>>> +
>>> +    mas->store_type = wr_invalid;
>>> +    MAS_WARN_ON(mas, 1);
>>> +}
>>> +