Re: [PATCH v2 17/33] nstree: make iterator generic

On Fri 12-09-25 13:52:40, Christian Brauner wrote:

Move the namespace iteration infrastructure originally introduced for mount namespaces into a generic library usable by all namespace types.

Signed-off-by: Christian Brauner brauner@kernel.org

Looks good. Feel free to add:

Reviewed-by: Jan Kara jack@suse.cz

Honza

---

include/linux/ns_common.h | 9 ++ include/linux/nstree.h | 89 ++++++++++++++++++ include/linux/proc_ns.h | 3 + kernel/Makefile | 2 +- kernel/nstree.c | 233 ++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 335 insertions(+), 1 deletion(-)

diff --git a/include/linux/ns_common.h b/include/linux/ns_common.h index bc2e0758e1c9..7224072cccc5 100644 --- a/include/linux/ns_common.h +++ b/include/linux/ns_common.h @@ -3,6 +3,7 @@ #define _LINUX_NS_COMMON_H #include <linux/refcount.h> +#include <linux/rbtree.h> struct proc_ns_operations; @@ -20,6 +21,14 @@ struct ns_common { const struct proc_ns_operations *ops; unsigned int inum; refcount_t count;

• union {

• struct {
  

• 	u64 ns_id;
  

• 	struct rb_node ns_tree_node;
  

• 	struct list_head ns_list_node;
  

• };
  

• struct rcu_head ns_rcu;
  

• };

}; #define to_ns_common(__ns) \ diff --git a/include/linux/nstree.h b/include/linux/nstree.h new file mode 100644 index 000000000000..e26951a83924 --- /dev/null +++ b/include/linux/nstree.h @@ -0,0 +1,89 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_NSTREE_H +#define _LINUX_NSTREE_H

+#include <linux/ns_common.h> +#include <linux/nsproxy.h> +#include <linux/rbtree.h> +#include <linux/seqlock.h> +#include <linux/rculist.h> +#include <linux/cookie.h>

+/**

• • struct ns_tree - Namespace tree
• • @ns_tree: Rbtree of namespaces of a particular type
• • @ns_list: Sequentially walkable list of all namespaces of this type
• • @ns_tree_lock: Seqlock to protect the tree and list
• */

+struct ns_tree {

• struct rb_root ns_tree;
• struct list_head ns_list;
• seqlock_t ns_tree_lock;
• int type;

+};

+extern struct ns_tree cgroup_ns_tree; +extern struct ns_tree ipc_ns_tree; +extern struct ns_tree mnt_ns_tree; +extern struct ns_tree net_ns_tree; +extern struct ns_tree pid_ns_tree; +extern struct ns_tree time_ns_tree; +extern struct ns_tree user_ns_tree; +extern struct ns_tree uts_ns_tree;

+#define to_ns_tree(__ns) \

• _Generic((__ns), \

• struct cgroup_namespace *: &(cgroup_ns_tree),	\
  

• struct ipc_namespace *:    &(ipc_ns_tree),	\
  

• struct net *:              &(net_ns_tree),	\
  

• struct pid_namespace *:    &(pid_ns_tree),	\
  

• struct mnt_namespace *:    &(mnt_ns_tree),	\
  

• struct time_namespace *:   &(time_ns_tree),	\
  

• struct user_namespace *:   &(user_ns_tree),	\
  

• struct uts_namespace *:    &(uts_ns_tree))
  

+u64 ns_tree_gen_id(struct ns_common *ns); +void __ns_tree_add_raw(struct ns_common *ns, struct ns_tree *ns_tree); +void __ns_tree_remove(struct ns_common *ns, struct ns_tree *ns_tree); +struct ns_common *ns_tree_lookup_rcu(u64 ns_id, int ns_type); +struct ns_common *__ns_tree_adjoined_rcu(struct ns_common *ns,

• 			 struct ns_tree *ns_tree,
  

• 			 bool previous);
  

+static inline void __ns_tree_add(struct ns_common *ns, struct ns_tree *ns_tree) +{

• ns_tree_gen_id(ns);
• __ns_tree_add_raw(ns, ns_tree);

+}

+/**

• • ns_tree_add_raw - Add a namespace to a namespace
• • @ns: Namespace to add
• • This function adds a namespace to the appropriate namespace tree
• • without assigning a id.
• */

+#define ns_tree_add_raw(__ns) __ns_tree_add_raw(to_ns_common(__ns), to_ns_tree(__ns))

+/**

• • ns_tree_add - Add a namespace to a namespace tree
• • @ns: Namespace to add
• • This function assigns a new id to the namespace and adds it to the
• • appropriate namespace tree and list.
• */

+#define ns_tree_add(__ns) __ns_tree_add(to_ns_common(__ns), to_ns_tree(__ns))

+/**

• • ns_tree_remove - Remove a namespace from a namespace tree
• • @ns: Namespace to remove
• • This function removes a namespace from the appropriate namespace
• • tree and list.
• */

+#define ns_tree_remove(__ns) __ns_tree_remove(to_ns_common(__ns), to_ns_tree(__ns))

+#define ns_tree_adjoined_rcu(__ns, __previous) \

• __ns_tree_adjoined_rcu(to_ns_common(__ns), to_ns_tree(__ns), __previous)

+#endif /* _LINUX_NSTREE_H */ diff --git a/include/linux/proc_ns.h b/include/linux/proc_ns.h index e50d312f9fee..7f89f0829e60 100644 --- a/include/linux/proc_ns.h +++ b/include/linux/proc_ns.h @@ -79,6 +79,9 @@ static inline int ns_common_init(struct ns_common *ns, refcount_set(&ns->count, 1); ns->stashed = NULL; ns->ops = ops;

• ns->ns_id = 0;
• RB_CLEAR_NODE(&ns->ns_tree_node);
• INIT_LIST_HEAD(&ns->ns_list_node); return 0;

} diff --git a/kernel/Makefile b/kernel/Makefile index c60623448235..b807516a1b43 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -8,7 +8,7 @@ obj-y = fork.o exec_domain.o panic.o \ sysctl.o capability.o ptrace.o user.o \ signal.o sys.o umh.o workqueue.o pid.o task_work.o \ extable.o params.o \

•    kthread.o sys_ni.o nsproxy.o \
  

•    kthread.o sys_ni.o nsproxy.o nstree.o \
   notifier.o ksysfs.o cred.o reboot.o \
   async.o range.o smpboot.o ucount.o regset.o ksyms_common.o
  

diff --git a/kernel/nstree.c b/kernel/nstree.c new file mode 100644 index 000000000000..bbe8bedc924c --- /dev/null +++ b/kernel/nstree.c @@ -0,0 +1,233 @@ +// SPDX-License-Identifier: GPL-2.0-only

+#include <linux/nstree.h> +#include <linux/proc_ns.h> +#include <linux/vfsdebug.h>

+struct ns_tree mnt_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(mnt_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(mnt_ns_tree.ns_tree_lock),
• .type = CLONE_NEWNS,

+};

+struct ns_tree net_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(net_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(net_ns_tree.ns_tree_lock),
• .type = CLONE_NEWNET,

+}; +EXPORT_SYMBOL_GPL(net_ns_tree);

+struct ns_tree uts_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(uts_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(uts_ns_tree.ns_tree_lock),
• .type = CLONE_NEWUTS,

+};

+struct ns_tree user_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(user_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(user_ns_tree.ns_tree_lock),
• .type = CLONE_NEWUSER,

+};

+struct ns_tree ipc_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(ipc_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(ipc_ns_tree.ns_tree_lock),
• .type = CLONE_NEWIPC,

+};

+struct ns_tree pid_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(pid_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(pid_ns_tree.ns_tree_lock),
• .type = CLONE_NEWPID,

+};

+struct ns_tree cgroup_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(cgroup_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(cgroup_ns_tree.ns_tree_lock),
• .type = CLONE_NEWCGROUP,

+};

+struct ns_tree time_ns_tree = {

• .ns_tree = RB_ROOT,
• .ns_list = LIST_HEAD_INIT(time_ns_tree.ns_list),
• .ns_tree_lock = __SEQLOCK_UNLOCKED(time_ns_tree.ns_tree_lock),
• .type = CLONE_NEWTIME,

+};

+DEFINE_COOKIE(namespace_cookie);

+static inline struct ns_common *node_to_ns(const struct rb_node *node) +{

• if (!node)

• return NULL;
  

• return rb_entry(node, struct ns_common, ns_tree_node);

+}

+static inline int ns_cmp(struct rb_node *a, const struct rb_node *b) +{

• struct ns_common *ns_a = node_to_ns(a);
• struct ns_common *ns_b = node_to_ns(b);
• u64 ns_id_a = ns_a->ns_id;
• u64 ns_id_b = ns_b->ns_id;
• if (ns_id_a < ns_id_b)

• return -1;
  

• if (ns_id_a > ns_id_b)

• return 1;
  

• return 0;

+}

+void __ns_tree_add_raw(struct ns_common *ns, struct ns_tree *ns_tree) +{

• struct rb_node *node, *prev;
• VFS_WARN_ON_ONCE(!ns->ns_id);
• write_seqlock(&ns_tree->ns_tree_lock);
• VFS_WARN_ON_ONCE(ns->ops->type != ns_tree->type);
• node = rb_find_add_rcu(&ns->ns_tree_node, &ns_tree->ns_tree, ns_cmp);
• /*

• * If there's no previous entry simply add it after the
  

• * head and if there is add it after the previous entry.
  

• */
  

• prev = rb_prev(&ns->ns_tree_node);
• if (!prev)

• list_add_rcu(&ns->ns_list_node, &ns_tree->ns_list);
  

• else

• list_add_rcu(&ns->ns_list_node, &node_to_ns(prev)->ns_list_node);
  

• write_sequnlock(&ns_tree->ns_tree_lock);
• VFS_WARN_ON_ONCE(node);

+}

+void __ns_tree_remove(struct ns_common *ns, struct ns_tree *ns_tree) +{

• VFS_WARN_ON_ONCE(RB_EMPTY_NODE(&ns->ns_tree_node));
• VFS_WARN_ON_ONCE(list_empty(&ns->ns_list_node));
• VFS_WARN_ON_ONCE(ns->ops->type != ns_tree->type);
• write_seqlock(&ns_tree->ns_tree_lock);
• rb_erase(&ns->ns_tree_node, &ns_tree->ns_tree);
• list_bidir_del_rcu(&ns->ns_list_node);
• RB_CLEAR_NODE(&ns->ns_tree_node);
• write_sequnlock(&ns_tree->ns_tree_lock);

+} +EXPORT_SYMBOL_GPL(__ns_tree_remove);

+static int ns_find(const void *key, const struct rb_node *node) +{

• const u64 ns_id = *(u64 *)key;
• const struct ns_common *ns = node_to_ns(node);
• if (ns_id < ns->ns_id)

• return -1;
  

• if (ns_id > ns->ns_id)

• return 1;
  

• return 0;

+}

+static struct ns_tree *ns_tree_from_type(int ns_type) +{

• switch (ns_type) {
• case CLONE_NEWCGROUP:

• return &cgroup_ns_tree;
  

• case CLONE_NEWIPC:

• return &ipc_ns_tree;
  

• case CLONE_NEWNS:

• return &mnt_ns_tree;
  

• case CLONE_NEWNET:

• return &net_ns_tree;
  

• case CLONE_NEWPID:

• return &pid_ns_tree;
  

• case CLONE_NEWUSER:

• return &user_ns_tree;
  

• case CLONE_NEWUTS:

• return &uts_ns_tree;
  

• case CLONE_NEWTIME:

• return &time_ns_tree;
  

• }
• return NULL;

+}

+struct ns_common *ns_tree_lookup_rcu(u64 ns_id, int ns_type) +{

• struct ns_tree *ns_tree;
• struct rb_node *node;
• unsigned int seq;
• RCU_LOCKDEP_WARN(!rcu_read_lock_held(), "suspicious ns_tree_lookup_rcu() usage");
• ns_tree = ns_tree_from_type(ns_type);
• if (!ns_tree)

• return NULL;
  

• do {

• seq = read_seqbegin(&ns_tree->ns_tree_lock);
  

• node = rb_find_rcu(&ns_id, &ns_tree->ns_tree, ns_find);
  

• if (node)
  

• 	break;
  

• } while (read_seqretry(&ns_tree->ns_tree_lock, seq));
• if (!node)

• return NULL;
  

• VFS_WARN_ON_ONCE(node_to_ns(node)->ops->type != ns_type);
• return node_to_ns(node);

+}

+/**

• • ns_tree_adjoined_rcu - find the next/previous namespace in the same
• • tree
• • @ns: namespace to start from
• • @previous: if true find the previous namespace, otherwise the next
• • Find the next or previous namespace in the same tree as @ns. If
• • there is no next/previous namespace, -ENOENT is returned.
• */

+struct ns_common *__ns_tree_adjoined_rcu(struct ns_common *ns,

• 			 struct ns_tree *ns_tree, bool previous)
  

+{

• struct list_head *list;
• RCU_LOCKDEP_WARN(!rcu_read_lock_held(), "suspicious ns_tree_adjoined_rcu() usage");
• if (previous)

• list = rcu_dereference(list_bidir_prev_rcu(&ns->ns_list_node));
  

• else

• list = rcu_dereference(list_next_rcu(&ns->ns_list_node));
  

• if (list_is_head(list, &ns_tree->ns_list))

• return ERR_PTR(-ENOENT);
  

• VFS_WARN_ON_ONCE(list_entry_rcu(list, struct ns_common, ns_list_node)->ops->type != ns_tree->type);
• return list_entry_rcu(list, struct ns_common, ns_list_node);

+}

+/**

• • ns_tree_gen_id - generate a new namespace id
• • @ns: namespace to generate id for
• • Generates a new namespace id and assigns it to the namespace. All
• • namespaces types share the same id space and thus can be compared
• • directly. IOW, when two ids of two namespace are equal, they are
• • identical.
• */

+u64 ns_tree_gen_id(struct ns_common *ns) +{

• guard(preempt)();
• ns->ns_id = gen_cookie_next(&namespace_cookie);
• return ns->ns_id;

+}

-- 2.47.3