1// SPDX-License-Identifier: GPL-2.0-only
2
3#include <linux/nstree.h>
4#include <linux/proc_ns.h>
5#include <linux/vfsdebug.h>
6
7/**
8 * struct ns_tree - Namespace tree
9 * @ns_tree: Rbtree of namespaces of a particular type
10 * @ns_list: Sequentially walkable list of all namespaces of this type
11 * @ns_tree_lock: Seqlock to protect the tree and list
12 * @type: type of namespaces in this tree
13 */
14struct ns_tree {
15 struct rb_root ns_tree;
16 struct list_head ns_list;
17 seqlock_t ns_tree_lock;
18 int type;
19};
20
21struct ns_tree mnt_ns_tree = {
22 .ns_tree = RB_ROOT,
23 .ns_list = LIST_HEAD_INIT(mnt_ns_tree.ns_list),
24 .ns_tree_lock = __SEQLOCK_UNLOCKED(mnt_ns_tree.ns_tree_lock),
25 .type = CLONE_NEWNS,
26};
27
28struct ns_tree net_ns_tree = {
29 .ns_tree = RB_ROOT,
30 .ns_list = LIST_HEAD_INIT(net_ns_tree.ns_list),
31 .ns_tree_lock = __SEQLOCK_UNLOCKED(net_ns_tree.ns_tree_lock),
32 .type = CLONE_NEWNET,
33};
34EXPORT_SYMBOL_GPL(net_ns_tree);
35
36struct ns_tree uts_ns_tree = {
37 .ns_tree = RB_ROOT,
38 .ns_list = LIST_HEAD_INIT(uts_ns_tree.ns_list),
39 .ns_tree_lock = __SEQLOCK_UNLOCKED(uts_ns_tree.ns_tree_lock),
40 .type = CLONE_NEWUTS,
41};
42
43struct ns_tree user_ns_tree = {
44 .ns_tree = RB_ROOT,
45 .ns_list = LIST_HEAD_INIT(user_ns_tree.ns_list),
46 .ns_tree_lock = __SEQLOCK_UNLOCKED(user_ns_tree.ns_tree_lock),
47 .type = CLONE_NEWUSER,
48};
49
50struct ns_tree ipc_ns_tree = {
51 .ns_tree = RB_ROOT,
52 .ns_list = LIST_HEAD_INIT(ipc_ns_tree.ns_list),
53 .ns_tree_lock = __SEQLOCK_UNLOCKED(ipc_ns_tree.ns_tree_lock),
54 .type = CLONE_NEWIPC,
55};
56
57struct ns_tree pid_ns_tree = {
58 .ns_tree = RB_ROOT,
59 .ns_list = LIST_HEAD_INIT(pid_ns_tree.ns_list),
60 .ns_tree_lock = __SEQLOCK_UNLOCKED(pid_ns_tree.ns_tree_lock),
61 .type = CLONE_NEWPID,
62};
63
64struct ns_tree cgroup_ns_tree = {
65 .ns_tree = RB_ROOT,
66 .ns_list = LIST_HEAD_INIT(cgroup_ns_tree.ns_list),
67 .ns_tree_lock = __SEQLOCK_UNLOCKED(cgroup_ns_tree.ns_tree_lock),
68 .type = CLONE_NEWCGROUP,
69};
70
71struct ns_tree time_ns_tree = {
72 .ns_tree = RB_ROOT,
73 .ns_list = LIST_HEAD_INIT(time_ns_tree.ns_list),
74 .ns_tree_lock = __SEQLOCK_UNLOCKED(time_ns_tree.ns_tree_lock),
75 .type = CLONE_NEWTIME,
76};
77
78DEFINE_COOKIE(namespace_cookie);
79
80static inline struct ns_common *node_to_ns(const struct rb_node *node)
81{
82 if (!node)
83 return NULL;
84 return rb_entry(node, struct ns_common, ns_tree_node);
85}
86
87static inline int ns_cmp(struct rb_node *a, const struct rb_node *b)
88{
89 struct ns_common *ns_a = node_to_ns(node: a);
90 struct ns_common *ns_b = node_to_ns(node: b);
91 u64 ns_id_a = ns_a->ns_id;
92 u64 ns_id_b = ns_b->ns_id;
93
94 if (ns_id_a < ns_id_b)
95 return -1;
96 if (ns_id_a > ns_id_b)
97 return 1;
98 return 0;
99}
100
101void __ns_tree_add_raw(struct ns_common *ns, struct ns_tree *ns_tree)
102{
103 struct rb_node *node, *prev;
104
105 VFS_WARN_ON_ONCE(!ns->ns_id);
106
107 write_seqlock(sl: &ns_tree->ns_tree_lock);
108
109 VFS_WARN_ON_ONCE(ns->ns_type != ns_tree->type);
110
111 node = rb_find_add_rcu(node: &ns->ns_tree_node, tree: &ns_tree->ns_tree, cmp: ns_cmp);
112 /*
113 * If there's no previous entry simply add it after the
114 * head and if there is add it after the previous entry.
115 */
116 prev = rb_prev(&ns->ns_tree_node);
117 if (!prev)
118 list_add_rcu(new: &ns->ns_list_node, head: &ns_tree->ns_list);
119 else
120 list_add_rcu(new: &ns->ns_list_node, head: &node_to_ns(node: prev)->ns_list_node);
121
122 write_sequnlock(sl: &ns_tree->ns_tree_lock);
123
124 VFS_WARN_ON_ONCE(node);
125}
126
127void __ns_tree_remove(struct ns_common *ns, struct ns_tree *ns_tree)
128{
129 VFS_WARN_ON_ONCE(RB_EMPTY_NODE(&ns->ns_tree_node));
130 VFS_WARN_ON_ONCE(list_empty(&ns->ns_list_node));
131 VFS_WARN_ON_ONCE(ns->ns_type != ns_tree->type);
132
133 write_seqlock(sl: &ns_tree->ns_tree_lock);
134 rb_erase(&ns->ns_tree_node, &ns_tree->ns_tree);
135 list_bidir_del_rcu(entry: &ns->ns_list_node);
136 RB_CLEAR_NODE(&ns->ns_tree_node);
137 write_sequnlock(sl: &ns_tree->ns_tree_lock);
138}
139EXPORT_SYMBOL_GPL(__ns_tree_remove);
140
141static int ns_find(const void *key, const struct rb_node *node)
142{
143 const u64 ns_id = *(u64 *)key;
144 const struct ns_common *ns = node_to_ns(node);
145
146 if (ns_id < ns->ns_id)
147 return -1;
148 if (ns_id > ns->ns_id)
149 return 1;
150 return 0;
151}
152
153
154static struct ns_tree *ns_tree_from_type(int ns_type)
155{
156 switch (ns_type) {
157 case CLONE_NEWCGROUP:
158 return &cgroup_ns_tree;
159 case CLONE_NEWIPC:
160 return &ipc_ns_tree;
161 case CLONE_NEWNS:
162 return &mnt_ns_tree;
163 case CLONE_NEWNET:
164 return &net_ns_tree;
165 case CLONE_NEWPID:
166 return &pid_ns_tree;
167 case CLONE_NEWUSER:
168 return &user_ns_tree;
169 case CLONE_NEWUTS:
170 return &uts_ns_tree;
171 case CLONE_NEWTIME:
172 return &time_ns_tree;
173 }
174
175 return NULL;
176}
177
178struct ns_common *ns_tree_lookup_rcu(u64 ns_id, int ns_type)
179{
180 struct ns_tree *ns_tree;
181 struct rb_node *node;
182 unsigned int seq;
183
184 RCU_LOCKDEP_WARN(!rcu_read_lock_held(), "suspicious ns_tree_lookup_rcu() usage");
185
186 ns_tree = ns_tree_from_type(ns_type);
187 if (!ns_tree)
188 return NULL;
189
190 do {
191 seq = read_seqbegin(sl: &ns_tree->ns_tree_lock);
192 node = rb_find_rcu(key: &ns_id, tree: &ns_tree->ns_tree, cmp: ns_find);
193 if (node)
194 break;
195 } while (read_seqretry(sl: &ns_tree->ns_tree_lock, start: seq));
196
197 if (!node)
198 return NULL;
199
200 VFS_WARN_ON_ONCE(node_to_ns(node)->ns_type != ns_type);
201
202 return node_to_ns(node);
203}
204
205/**
206 * ns_tree_adjoined_rcu - find the next/previous namespace in the same
207 * tree
208 * @ns: namespace to start from
209 * @previous: if true find the previous namespace, otherwise the next
210 *
211 * Find the next or previous namespace in the same tree as @ns. If
212 * there is no next/previous namespace, -ENOENT is returned.
213 */
214struct ns_common *__ns_tree_adjoined_rcu(struct ns_common *ns,
215 struct ns_tree *ns_tree, bool previous)
216{
217 struct list_head *list;
218
219 RCU_LOCKDEP_WARN(!rcu_read_lock_held(), "suspicious ns_tree_adjoined_rcu() usage");
220
221 if (previous)
222 list = rcu_dereference(list_bidir_prev_rcu(&ns->ns_list_node));
223 else
224 list = rcu_dereference(list_next_rcu(&ns->ns_list_node));
225 if (list_is_head(list, head: &ns_tree->ns_list))
226 return ERR_PTR(error: -ENOENT);
227
228 VFS_WARN_ON_ONCE(list_entry_rcu(list, struct ns_common, ns_list_node)->ns_type != ns_tree->type);
229
230 return list_entry_rcu(list, struct ns_common, ns_list_node);
231}
232
233/**
234 * ns_tree_gen_id - generate a new namespace id
235 * @ns: namespace to generate id for
236 *
237 * Generates a new namespace id and assigns it to the namespace. All
238 * namespaces types share the same id space and thus can be compared
239 * directly. IOW, when two ids of two namespace are equal, they are
240 * identical.
241 */
242u64 ns_tree_gen_id(struct ns_common *ns)
243{
244 guard(preempt)();
245 ns->ns_id = gen_cookie_next(gc: &namespace_cookie);
246 return ns->ns_id;
247}
248