diff --git a/fs/xattr.c b/fs/xattr.c
index 61107b6bbed2..be7c3829a544 100644
--- a/fs/xattr.c
+++ b/fs/xattr.c
@@ -992,8 +992,65 @@ const char *xattr_full_name(const struct xattr_handler *handler,
 }
 EXPORT_SYMBOL(xattr_full_name);
 
-/*
- * Allocate new xattr and copy in the value; but leave the name to callers.
+/**
+ * free_simple_xattr - free an xattr object
+ * @xattr: the xattr object
+ *
+ * Free the xattr object. Can handle @xattr being NULL.
+ */
+static inline void free_simple_xattr(struct simple_xattr *xattr)
+{
+	if (xattr)
+		kfree(xattr->name);
+	kvfree(xattr);
+}
+
+/**
+ * free_simple_xattr_rcu_cb - callback for freeing xattr object through rcu
+ * @cb: the rcu callback head
+ */
+static void free_simple_xattr_rcu_cb(struct callback_head *cb_head)
+{
+	struct simple_xattr *xattr =
+		container_of(cb_head, struct simple_xattr, rcu);
+	free_simple_xattr(xattr);
+}
+
+/**
+ * free_simple_xattr_rcu - free an xattr object with rcu semantics
+ * @xattr: the xattr object
+ */
+static void free_simple_xattr_rcu(struct simple_xattr *xattr)
+{
+	call_rcu(&xattr->rcu, free_simple_xattr_rcu_cb);
+}
+
+/**
+ * put_simple_xattr_rcu - decrement refcount for xattr object
+ * @xattr: the xattr object
+ *
+ * Decrement the reference count of an xattr object and free it using rcu
+ * semantics if we're the holder of the last reference. Can handle @xattr being
+ * NULL.
+ */
+static inline void put_simple_xattr_rcu(struct simple_xattr *xattr)
+{
+	if (xattr && refcount_dec_and_test(&xattr->ref))
+		free_simple_xattr_rcu(xattr);
+}
+
+/**
+ * simple_xattr_alloc - allocate new xattr object
+ * @value: value of the xattr object
+ * @size: size of @value
+ *
+ * Allocate a new xattr object and initialize respective members. The caller is
+ * responsible for handling the name of the xattr.
+ *
+ * The initial reference count belongs to the rbtree.
+ *
+ * Return: On success a new xattr object is returned. On failure NULL is
+ * returned.
  */
 struct simple_xattr *simple_xattr_alloc(const void *value, size_t size)
 {
@@ -1011,57 +1068,99 @@ struct simple_xattr *simple_xattr_alloc(const void *value, size_t size)
 
 	new_xattr->size = size;
 	memcpy(new_xattr->value, value, size);
+	refcount_set(&new_xattr->ref, 1);
 	return new_xattr;
 }
 
-/*
- * xattr GET operation for in-memory/pseudo filesystems
+/**
+ * simple_xattr_get - get an xattr object
+ * @xattrs: the header of the xattr object
+ * @name: the name of the xattr to retrieve
+ * @buffer: the buffer to store the value into
+ * @size: the size of @buffer
+ *
+ * Try to find and retrieve the xattr object associated with @name. If the
+ * object is found and still in the rbtree bump the reference count.
+ *
+ * If @buffer is provided store the value of @xattr in @buffer.
+ *
+ * Return: On success zero and on error a negative error code is returned.
  */
 int simple_xattr_get(struct simple_xattrs *xattrs, const char *name,
 		     void *buffer, size_t size)
 {
-	struct simple_xattr *xattr;
-	int ret = -ENODATA;
-
-	spin_lock(&xattrs->lock);
-	list_for_each_entry(xattr, &xattrs->head, list) {
-		if (strcmp(name, xattr->name))
-			continue;
-
-		ret = xattr->size;
-		if (buffer) {
-			if (size < xattr->size)
-				ret = -ERANGE;
-			else
-				memcpy(buffer, xattr->value, xattr->size);
+	struct simple_xattr *xattr = NULL;
+	struct rb_node *rbp;
+	int ret, seq = 0;
+
+	rcu_read_lock();
+	do {
+		read_seqbegin_or_lock(&xattrs->lock, &seq);
+		rbp = rcu_dereference(xattrs->rb_root.rb_node);
+		while (rbp) {
+			xattr = rb_entry(rbp, struct simple_xattr, rb_node);
+			if (strcmp(xattr->name, name) < 0) {
+				rbp = rcu_dereference(rbp->rb_left);
+			} else if (strcmp(xattr->name, name) > 0) {
+				rbp = rcu_dereference(rbp->rb_right);
+			} else {
+				if (!likely(refcount_inc_not_zero(&xattr->ref)))
+					xattr = NULL;
+				break;
+			}
+			xattr = NULL;
 		}
-		break;
+	} while (need_seqretry(&xattrs->lock, seq));
+	done_seqretry(&xattrs->lock, seq);
+	rcu_read_unlock();
+
+	if (!xattr)
+		return -ENODATA;
+
+	ret = xattr->size;
+	if (buffer) {
+		if (size < xattr->size)
+			ret = -ERANGE;
+		else
+			memcpy(buffer, xattr->value, xattr->size);
 	}
-	spin_unlock(&xattrs->lock);
+
+	put_simple_xattr_rcu(xattr);
 	return ret;
 }
 
 /**
- * simple_xattr_set - xattr SET operation for in-memory/pseudo filesystems
- * @xattrs: target simple_xattr list
- * @name: name of the extended attribute
- * @value: value of the xattr. If %NULL, will remove the attribute.
- * @size: size of the new xattr
- * @flags: %XATTR_{CREATE|REPLACE}
- * @removed_size: returns size of the removed xattr, -1 if none removed
+ * simple_xattr_set - set an xattr object
+ * @xattrs: the header of the xattr object
+ * @name: the name of the xattr to retrieve
+ * @value: the value to store along the xattr
+ * @size: the size of @value
+ * @flags: the flags determining how to set the xattr
+ * @removed_size: the size of the removed xattr
+ *
+ * Set a new xattr object.
+ * If @value is passed a new xattr object will be allocated. If XATTR_REPLACE
+ * is specified in @flags a matching xattr object for @name must already exist.
+ * If it does it will be replace with the new xattr object. If it doesn't we
+ * fail. If XATTR_CREATE is specified and a matching xattr does already exist
+ * we fail. If it doesn't we create a new xattr. If @flags is zero we simply
+ * insert the new xattr replacing any existing one.
  *
- * %XATTR_CREATE is set, the xattr shouldn't exist already; otherwise fails
- * with -EEXIST.  If %XATTR_REPLACE is set, the xattr should exist;
- * otherwise, fails with -ENODATA.
+ * If @value is empty and a matching xattr object is found we delete it if
+ * XATTR_REPLACE is specified in @flags or @flags is zero.
  *
- * Returns 0 on success, -errno on failure.
+ * If @value is empty and no matching xattr object for @name is found we do
+ * nothing if XATTR_CREATE is specified in @flags or @flags is zero. For
+ * XATTR_REPLACE we fail as mentioned above.
+ *
+ * Return: On success zero and on error a negative error code is returned.
  */
 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 *new_xattr = NULL;
+	struct simple_xattr *xattr = NULL, *new_xattr = NULL;
+	struct rb_node *parent = NULL, **rbp;
 	int err = 0;
 
 	if (removed_size)
@@ -1080,37 +1179,64 @@ 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;
-		}
-	}
-	if (flags & XATTR_REPLACE) {
-		xattr = new_xattr;
-		err = -ENODATA;
-	} else {
-		list_add(&new_xattr->list, &xattrs->head);
+	write_seqlock(&xattrs->lock);
+	rbp = &xattrs->rb_root.rb_node;
+	while (*rbp) {
+		parent = *rbp;
+		xattr = rb_entry(*rbp, struct simple_xattr, rb_node);
+		if (strcmp(xattr->name, name) < 0)
+			rbp = &(*rbp)->rb_left;
+		else if (strcmp(xattr->name, name) > 0)
+			rbp = &(*rbp)->rb_right;
+		else
+			break;
 		xattr = NULL;
 	}
-out:
-	spin_unlock(&xattrs->lock);
+
 	if (xattr) {
-		kfree(xattr->name);
-		kvfree(xattr);
+		/* Fail if XATTR_CREATE is requested and the xattr exists. */
+		if (flags & XATTR_CREATE) {
+			err = -EEXIST;
+			goto out_unlock;
+		}
+
+		if (new_xattr)
+			rb_replace_node_rcu(&xattr->rb_node,
+					    &new_xattr->rb_node,
+					    &xattrs->rb_root);
+		else
+			rb_erase(&xattr->rb_node, &xattrs->rb_root);
+		if (!err && removed_size)
+			*removed_size = xattr->size;
+	} else {
+		/* Fail if XATTR_REPLACE is requested but no xattr is found. */
+		if (flags & XATTR_REPLACE) {
+			err = -ENODATA;
+			goto out_unlock;
+		}
+
+		/*
+		 * If XATTR_CREATE or no flags are specified together with a
+		 * new value simply insert it.
+		 */
+		if (new_xattr) {
+			rb_link_node_rcu(&new_xattr->rb_node, parent, rbp);
+			rb_insert_color(&new_xattr->rb_node, &xattrs->rb_root);
+		}
+
+		/*
+		 * If XATTR_CREATE or no flags are specified and neither an old
+		 * or new xattr were found/exist then we don't need to do
+		 * anything.
+		 */
 	}
+
+out_unlock:
+	write_sequnlock(&xattrs->lock);
+	if (err)
+		free_simple_xattr(new_xattr);
+	else
+		put_simple_xattr_rcu(xattr);
 	return err;
 
 }
@@ -1134,14 +1260,30 @@ static int xattr_list_one(char **buffer, ssize_t *remaining_size,
 	return 0;
 }
 
-/*
- * xattr LIST operation for in-memory/pseudo filesystems
+/**
+ * simple_xattr_list - list all xattr objects
+ * @inode: inode from which to get the xattrs
+ * @xattrs: the header of the xattr object
+ * @buffer: the buffer to store all xattrs into
+ * @size: the size of @buffer
+ *
+ * List all xattrs associated with @inode. If @buffer is NULL we returned the
+ * required size of the buffer. If @buffer is provided we store the xattrs
+ * value into it provided it is big enough.
+ *
+ * This is lockles and we don't bump the reference count. So if callers race
+ * with deletion they may see xattrs about to be removed. This is a race
+ * userspace has to handle since forever anyway.
+ *
+ * Return: On success the required size or the size of the copied xattrs is
+ * returned. On error a negative error code is returned.
  */
 ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs,
 			  char *buffer, size_t size)
 {
 	bool trusted = capable(CAP_SYS_ADMIN);
 	struct simple_xattr *xattr;
+	struct rb_node *rbp;
 	ssize_t remaining_size = size;
 	int err = 0;
 
@@ -1162,8 +1304,10 @@ 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) {
+	read_seqlock_excl(&xattrs->lock);
+	for (rbp = rb_first(&xattrs->rb_root); rbp; rbp = rb_next(rbp)) {
+		xattr = rb_entry(rbp, struct simple_xattr, rb_node);
+
 		/* skip "trusted." attributes for unprivileged callers */
 		if (!trusted && xattr_is_trusted(xattr->name))
 			continue;
@@ -1172,18 +1316,61 @@ ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs,
 		if (err)
 			break;
 	}
-	spin_unlock(&xattrs->lock);
+	read_sequnlock_excl(&xattrs->lock);
 
 	return err ? err : size - remaining_size;
 }
 
-/*
- * Adds an extended attribute to the list
+/**
+ * simple_xattr_add - add xattr objects
+ * @xattrs: the header of the xattr object
+ * @new_xattr: the xattr object to add
+ *
+ * Add an xattr object to @xattrs. This assumes no replacement or removal of
+ * matching xattrs is wanted.
  */
-void simple_xattr_list_add(struct simple_xattrs *xattrs,
-			   struct simple_xattr *new_xattr)
+void simple_xattr_add(struct simple_xattrs *xattrs,
+		      struct simple_xattr *new_xattr)
 {
-	spin_lock(&xattrs->lock);
-	list_add(&new_xattr->list, &xattrs->head);
-	spin_unlock(&xattrs->lock);
+	write_seqlock(&xattrs->lock);
+	rb_link_node_rcu(&new_xattr->rb_node, xattrs->rb_root.rb_node,
+			 &xattrs->rb_root.rb_node);
+	rb_insert_color(&new_xattr->rb_node, &xattrs->rb_root);
+	write_sequnlock(&xattrs->lock);
+}
+
+/**
+ * simple_xattr_init - initialize new xattr header
+ * @xattrs: header to initialize
+ *
+ * Initialize relevant fields of a an xattr header.
+ */
+void simple_xattrs_init(struct simple_xattrs *xattrs)
+{
+	seqlock_init(&xattrs->lock);
+	xattrs->rb_root = RB_ROOT;
+}
+
+/**
+ * simple_xattrs_free - free xattrs
+ * @xattrs: xattr header whose xattrs to destroy
+ *
+ * Destroy all xattrs in @xattr. When this is called no one can hold a
+ * reference to any of the xattrs anymore.
+ */
+void simple_xattrs_free(struct simple_xattrs *xattrs)
+{
+	struct rb_node *rbp;
+
+	rbp = rb_first(&xattrs->rb_root);
+	while (rbp) {
+		struct simple_xattr *xattr;
+		struct rb_node *rbp_next;
+
+		rbp_next = rb_next(rbp);
+		xattr = rb_entry(rbp, struct simple_xattr, rb_node);
+		rb_erase(&xattr->rb_node, &xattrs->rb_root);
+		free_simple_xattr(xattr);
+		rbp = rbp_next;
+	}
 }
diff --git a/include/linux/xattr.h b/include/linux/xattr.h
index 4c379d23ec6e..9dc4a8c65a16 100644
--- a/include/linux/xattr.h
+++ b/include/linux/xattr.h
@@ -80,48 +80,32 @@ static inline const char *xattr_prefix(const struct xattr_handler *handler)
 }
 
 struct simple_xattrs {
-	struct list_head head;
-	spinlock_t lock;
+	struct rb_root rb_root;
+	seqlock_t lock;
 };
 
 struct simple_xattr {
-	struct list_head list;
+	union {
+		struct rb_node rb_node;
+		struct rcu_head rcu;
+	};
+	refcount_t ref;
 	char *name;
 	size_t size;
 	char value[];
 };
 
-/*
- * initialize the simple_xattrs structure
- */
-static inline void simple_xattrs_init(struct simple_xattrs *xattrs)
-{
-	INIT_LIST_HEAD(&xattrs->head);
-	spin_lock_init(&xattrs->lock);
-}
-
-/*
- * free all the xattrs
- */
-static inline void simple_xattrs_free(struct simple_xattrs *xattrs)
-{
-	struct simple_xattr *xattr, *node;
-
-	list_for_each_entry_safe(xattr, node, &xattrs->head, list) {
-		kfree(xattr->name);
-		kvfree(xattr);
-	}
-}
-
+void simple_xattrs_init(struct simple_xattrs *xattrs);
+void simple_xattrs_free(struct simple_xattrs *xattrs);
 struct simple_xattr *simple_xattr_alloc(const void *value, size_t size);
 int simple_xattr_get(struct simple_xattrs *xattrs, const char *name,
 		     void *buffer, size_t size);
 int simple_xattr_set(struct simple_xattrs *xattrs, const char *name,
 		     const void *value, size_t size, int flags,
 		     ssize_t *removed_size);
-ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs, char *buffer,
-			  size_t size);
-void simple_xattr_list_add(struct simple_xattrs *xattrs,
-			   struct simple_xattr *new_xattr);
+ssize_t simple_xattr_list(struct inode *inode, struct simple_xattrs *xattrs,
+			  char *buffer, size_t size);
+void simple_xattr_add(struct simple_xattrs *xattrs,
+		      struct simple_xattr *new_xattr);
 
 #endif	/* _LINUX_XATTR_H */
diff --git a/mm/shmem.c b/mm/shmem.c
index 8280a5cb48df..2872e6607b2c 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -3255,7 +3255,7 @@ static int shmem_initxattrs(struct inode *inode,
 		memcpy(new_xattr->name + XATTR_SECURITY_PREFIX_LEN,
 		       xattr->name, len);
 
-		simple_xattr_list_add(&info->xattrs, new_xattr);
+		simple_xattr_add(&info->xattrs, new_xattr);
 	}
 
 	return 0;
