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 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 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 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 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 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 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 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 */ 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 */ 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