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 */
14 struct 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
21 struct 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
28 struct 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 };
34 EXPORT_SYMBOL_GPL(net_ns_tree);
35
36 struct 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
43 struct 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
50 struct 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
57 struct 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
64 struct 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
71 struct 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
78 DEFINE_COOKIE(namespace_cookie);
79
node_to_ns(const struct rb_node * node)80 static 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
ns_cmp(struct rb_node * a,const struct rb_node * b)87 static inline int ns_cmp(struct rb_node *a, const struct rb_node *b)
88 {
89 struct ns_common *ns_a = node_to_ns(a);
90 struct ns_common *ns_b = node_to_ns(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
__ns_tree_add_raw(struct ns_common * ns,struct ns_tree * ns_tree)101 void __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(&ns_tree->ns_tree_lock);
108
109 VFS_WARN_ON_ONCE(ns->ns_type != ns_tree->type);
110
111 node = rb_find_add_rcu(&ns->ns_tree_node, &ns_tree->ns_tree, 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(&ns->ns_list_node, &ns_tree->ns_list);
119 else
120 list_add_rcu(&ns->ns_list_node, &node_to_ns(prev)->ns_list_node);
121
122 write_sequnlock(&ns_tree->ns_tree_lock);
123
124 VFS_WARN_ON_ONCE(node);
125 }
126
__ns_tree_remove(struct ns_common * ns,struct ns_tree * ns_tree)127 void __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(&ns_tree->ns_tree_lock);
134 rb_erase(&ns->ns_tree_node, &ns_tree->ns_tree);
135 list_bidir_del_rcu(&ns->ns_list_node);
136 RB_CLEAR_NODE(&ns->ns_tree_node);
137 write_sequnlock(&ns_tree->ns_tree_lock);
138 }
139 EXPORT_SYMBOL_GPL(__ns_tree_remove);
140
ns_find(const void * key,const struct rb_node * node)141 static 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
ns_tree_from_type(int ns_type)154 static 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
ns_tree_lookup_rcu(u64 ns_id,int ns_type)178 struct 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(&ns_tree->ns_tree_lock);
192 node = rb_find_rcu(&ns_id, &ns_tree->ns_tree, ns_find);
193 if (node)
194 break;
195 } while (read_seqretry(&ns_tree->ns_tree_lock, 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 */
__ns_tree_adjoined_rcu(struct ns_common * ns,struct ns_tree * ns_tree,bool previous)214 struct 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, &ns_tree->ns_list))
226 return ERR_PTR(-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 */
ns_tree_gen_id(struct ns_common * ns)242 u64 ns_tree_gen_id(struct ns_common *ns)
243 {
244 guard(preempt)();
245 ns->ns_id = gen_cookie_next(&namespace_cookie);
246 return ns->ns_id;
247 }
248