Messages in this thread Patch in this message | | | Date | Thu, 18 Aug 2022 12:12:30 +0300 | From | Vasily Averin <> | Subject | [RFC PATCH] simple_xattr: switch from list to rb_tree |
| |
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> --- fs/xattr.c | 109 ++++++++++++++++++++++++++++++++---------- include/linux/xattr.h | 13 +++-- 2 files changed, 92 insertions(+), 30 deletions(-)
diff --git a/fs/xattr.c b/fs/xattr.c index 6401703707f2..672f2214fcfd 100644 --- a/fs/xattr.c +++ b/fs/xattr.c @@ -1021,6 +1021,60 @@ struct simple_xattr *simple_xattr_alloc(const void *value, size_t size) return new_xattr; } +static struct simple_xattr *simple_xattr_rb_search(struct rb_root *root, + const char* name) +{ + struct rb_node **new = &(root->rb_node), *parent = NULL; + + /* Figure out where to put new node */ + while (*new) + { + struct simple_xattr *xattr; + int result; + + xattr = container_of(*new, struct simple_xattr, node); + result = strcmp(xattr->name, name); + + parent = *new; + if (result < 0) + new = &((*new)->rb_left); + else if (result > 0) + new = &((*new)->rb_right); + else + return xattr; + } + return NULL; +} + +static bool simple_xattr_rb_insert(struct rb_root *root, + struct simple_xattr *new_xattr) +{ + struct rb_node **new = &(root->rb_node), *parent = NULL; + + /* Figure out where to put new node */ + while (*new) { + struct simple_xattr *xattr; + int result; + + xattr = container_of(*new, struct simple_xattr, node); + result = strcmp(xattr->name, new_xattr->name); + + parent = *new; + if (result < 0) + new = &((*new)->rb_left); + else if (result > 0) + new = &((*new)->rb_right); + else + return false; + } + + /* Add new node and rebalance tree. */ + rb_link_node(&new_xattr->node, parent, new); + rb_insert_color(&new_xattr->node, root); + + return true; +} + /* * xattr GET operation for in-memory/pseudo filesystems */ @@ -1031,10 +1085,8 @@ int simple_xattr_get(struct simple_xattrs *xattrs, const char *name, int ret = -ENODATA; spin_lock(&xattrs->lock); - list_for_each_entry(xattr, &xattrs->head, list) { - if (strcmp(name, xattr->name)) - continue; - + xattr = simple_xattr_rb_search(&xattrs->rb_root, name); + if (xattr) { ret = xattr->size; if (buffer) { if (size < xattr->size) @@ -1042,7 +1094,6 @@ int simple_xattr_get(struct simple_xattrs *xattrs, const char *name, else memcpy(buffer, xattr->value, xattr->size); } - break; } spin_unlock(&xattrs->lock); return ret; @@ -1067,7 +1118,7 @@ int simple_xattr_set(struct simple_xattrs *xattrs, const char *name, const void *value, size_t size, int flags, ssize_t *removed_size) { - struct simple_xattr *xattr; + struct simple_xattr *xattr = NULL; struct simple_xattr *new_xattr = NULL; int err = 0; @@ -1088,31 +1139,36 @@ 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 ((flags & XATTR_CREATE) && new_xattr) { + /* create new */ + if (!simple_xattr_rb_insert(&xattrs->rb_root, new_xattr)) { + /* already exist */ + xattr = new_xattr; + err = -EEXIST; + } + } else { + /* replace or remove */ + xattr = simple_xattr_rb_search(&xattrs->rb_root, name); + if (xattr) { + /* found */ + if (!new_xattr) { + /* remove existing */ + rb_erase(&xattr->node, &xattrs->rb_root); if (removed_size) *removed_size = xattr->size; } else { - list_del(&xattr->list); + /* replace existing */ + rb_replace_node(&xattr->node, &new_xattr->node, + &xattrs->rb_root); if (removed_size) *removed_size = xattr->size; } - goto out; + } else if (new_xattr) { + /* not found, incorrect replace */ + xattr = new_xattr; + err = -ENODATA; } } - if (flags & XATTR_REPLACE) { - 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); @@ -1149,6 +1205,7 @@ ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs, { bool trusted = capable(CAP_SYS_ADMIN); struct simple_xattr *xattr; + struct rb_node *node; ssize_t remaining_size = size; int err = 0; @@ -1170,7 +1227,9 @@ ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs, #endif spin_lock(&xattrs->lock); - list_for_each_entry(xattr, &xattrs->head, list) { + for (node = rb_first(&xattrs->rb_root); node; node = rb_next(node)) { + xattr = container_of(node, struct simple_xattr, node); + /* skip "trusted." attributes for unprivileged callers */ if (!trusted && xattr_is_trusted(xattr->name)) continue; @@ -1191,6 +1250,6 @@ void simple_xattr_list_add(struct simple_xattrs *xattrs, struct simple_xattr *new_xattr) { spin_lock(&xattrs->lock); - list_add(&new_xattr->list, &xattrs->head); + simple_xattr_rb_insert(&xattrs->rb_root, new_xattr); spin_unlock(&xattrs->lock); } diff --git a/include/linux/xattr.h b/include/linux/xattr.h index 979a9d3e5bfb..bbe81cfb7a4d 100644 --- a/include/linux/xattr.h +++ b/include/linux/xattr.h @@ -80,12 +80,12 @@ static inline const char *xattr_prefix(const struct xattr_handler *handler) } struct simple_xattrs { - struct list_head head; + struct rb_root rb_root; spinlock_t lock; }; struct simple_xattr { - struct list_head list; + struct rb_node node; char *name; size_t size; char value[]; @@ -96,7 +96,7 @@ struct simple_xattr { */ static inline void simple_xattrs_init(struct simple_xattrs *xattrs) { - INIT_LIST_HEAD(&xattrs->head); + xattrs->rb_root = RB_ROOT; spin_lock_init(&xattrs->lock); } @@ -105,9 +105,12 @@ static inline void simple_xattrs_init(struct simple_xattrs *xattrs) */ static inline void simple_xattrs_free(struct simple_xattrs *xattrs) { - struct simple_xattr *xattr, *node; + struct simple_xattr *xattr; + struct rb_node *node; - list_for_each_entry_safe(xattr, node, &xattrs->head, list) { + while ((node = rb_first(&xattrs->rb_root))) { + rb_erase(node, &xattrs->rb_root); + xattr = container_of(node, struct simple_xattr, node); kfree(xattr->name); kvfree(xattr); } -- 2.34.1
| |