Messages in this thread | | | Date | Tue, 23 Aug 2022 13:42:36 +0300 | Subject | Re: [RFC PATCH] simple_xattr: switch from list to rb_tree | From | Vasily Averin <> |
| |
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@openvz.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);
| |