linux-kernel - Re: [RFC PATCH] simple_xattr: switch from list to rb

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: <ab83125e-bac4-c5eb-160b-7f5611f5fcb0@openvz.org>
Date:   Tue, 23 Aug 2022 13:42:36 +0300
From:   Vasily Averin <vvs@...nvz.org>
To:     Christian Brauner <brauner@...nel.org>
Cc:     Roman Gushchin <roman.gushchin@...ux.dev>, mkoutny@...e.com,
        tj@...nel.org, gregkh@...uxfoundation.org, hannes@...xchg.org,
        kernel@...nvz.org, linux-kernel@...r.kernel.org, mhocko@...e.com,
        shakeelb@...gle.com, songmuchun@...edance.com,
        viro@...iv.linux.org.uk
Subject: Re: [RFC PATCH] simple_xattr: switch from list to rb_tree

On 8/18/22 16:19, Christian Brauner wrote:
> On Thu, Aug 18, 2022 at 12:12:30PM +0300, Vasily Averin wrote:
>> The patch was announced here:
>> https://lore.kernel.org/all/62188f37-f816-08e9-cdd5-8df23131746d@openvz.org/
>> "5) simple_xattrs: replace list to rb-tree
>>   This significantly reduces the search time for existing entries."
>>
>> It was compiled but was not tested yet.
>> ---
>> Currently simple_xattr uses a list to store existing entries.
>> If the list grows, the presence check may be slow and potentially
>> lead to problems. Red-black tree should work more efficiently
>> in this situation.
>>
>> This patch replaces list to rb_tree and switches simple_xattr_* calls
>> to its using.
>>
>> Signed-off-by: Vasily Averin <vvs@...nvz.org>
>> ---
> 
> I think the background for the performance issues in the commit message
> would be helpful and I have a few comments. Also, trying to test whether the
> lockups are gone due to the rbtree switch would be +1. 
> 
> This will likely conflict with some acl/xattr changes I have lined up so
> if we decide to proceed I wouldn't mind dealing with this series if
> there are no objections.

I would be very grateful if you pick up this issue.
Unfortunately I do not have enough time to process it properly. 

I'm agree with all your remarks, however I would like to comment following one.

> I think keeping this rather close to the original code might be nicer.
> I find the code more difficult to follow afterwards. So how about
> (COMPLETELY UNTESTED) sm like:

I had this idea too, however it have one disadvantage in rb-tree scenario:
in the most typical case, when adding a new entry, we run through the tree twice:
first in simple_xattr_rb_search() and then in simple_xattr_rb_insert().
In my patch version we run through the rb-tree once only.

However now I think we can save closest neighbour on "search" stage, 
and use it on "insert" stage. This should be safe because both functions
are called under the same spinlock. 

> @@ -1077,30 +1139,40 @@ int simple_xattr_set(struct simple_xattrs *xattrs, const char *name,
>         }
> 
>         spin_lock(&xattrs->lock);
> -       list_for_each_entry(xattr, &xattrs->head, list) {
> -               if (!strcmp(name, xattr->name)) {
> -                       if (flags & XATTR_CREATE) {
> -                               xattr = new_xattr;
> -                               err = -EEXIST;
> -                       } else if (new_xattr) {
> -                               list_replace(&xattr->list, &new_xattr->list);
> -                               if (removed_size)
> -                                       *removed_size = xattr->size;
> -                       } else {
> -                               list_del(&xattr->list);
> -                               if (removed_size)
> -                                       *removed_size = xattr->size;
> -                       }
> -                       goto out;
> +       /* Find any matching xattr by name. */
> +       xattr = simple_xattr_rb_search(&xattrs->rb_root, name);
> +       if (xattr) {
> +               if (flags & XATTR_CREATE) {
> +                       /* Creating request but the xattr already existed. */
> +                       xattr = new_xattr;
> +                       err = -EEXIST;
> +               } else if (new_xattr) {
> +                       /* Replace the existing xattr. */
> +                       rb_replace_node(&xattr->node, &new_xattr->node,
> +                                       &xattrs->rb_root);
> +                       if (removed_size)
> +                               *removed_size = xattr->size;
> +               } else {
> +                       /* No new xattr specified so wipe the existing xattr. */
> +                       rb_erase(&xattr->node, &xattrs->rb_root);
> +                       if (removed_size)
> +                               *removed_size = xattr->size;
>                 }
> +               goto out;
>         }
> +
>         if (flags & XATTR_REPLACE) {
> +               /* There's no matching xattr so fail on replace. */
>                 xattr = new_xattr;
>                 err = -ENODATA;
>         } else {
> -               list_add(&new_xattr->list, &xattrs->head);
> -               xattr = NULL;
> +               /*
> +                * We're holding the lock and verified that there's no
> +                * pre-existing xattr so this should always succeed.
> +                */
> +               WARN_ON(!simple_xattr_rb_insert(&xattrs->rb_root, new_xattr))
>         }
> +
>  out:
>         spin_unlock(&xattrs->lock);
>         if (xattr) {
> 
> 
>> -		xattr = new_xattr;
>> -		err = -ENODATA;
>> -	} else {
>> -		list_add(&new_xattr->list, &xattrs->head);
>> -		xattr = NULL;
>> -	}
>> -out:
>>  	spin_unlock(&xattrs->lock);
>>  	if (xattr) {
>>  		kfree(xattr->name);