1 /* 2 * Generic pidhash and scalable, time-bounded PID allocator 3 * 4 * (C) 2002-2003 Nadia Yvette Chambers, IBM 5 * (C) 2004 Nadia Yvette Chambers, Oracle 6 * (C) 2002-2004 Ingo Molnar, Red Hat 7 * 8 * pid-structures are backing objects for tasks sharing a given ID to chain 9 * against. There is very little to them aside from hashing them and 10 * parking tasks using given ID's on a list. 11 * 12 * The hash is always changed with the tasklist_lock write-acquired, 13 * and the hash is only accessed with the tasklist_lock at least 14 * read-acquired, so there's no additional SMP locking needed here. 15 * 16 * We have a list of bitmap pages, which bitmaps represent the PID space. 17 * Allocating and freeing PIDs is completely lockless. The worst-case 18 * allocation scenario when all but one out of 1 million PIDs possible are 19 * allocated already: the scanning of 32 list entries and at most PAGE_SIZE 20 * bytes. The typical fastpath is a single successful setbit. Freeing is O(1). 21 * 22 * Pid namespaces: 23 * (C) 2007 Pavel Emelyanov <xemul@openvz.org>, OpenVZ, SWsoft Inc. 24 * (C) 2007 Sukadev Bhattiprolu <sukadev@us.ibm.com>, IBM 25 * Many thanks to Oleg Nesterov for comments and help 26 * 27 */ 28 29 #include <linux/mm.h> 30 #include <linux/export.h> 31 #include <linux/slab.h> 32 #include <linux/init.h> 33 #include <linux/rculist.h> 34 #include <linux/bootmem.h> 35 #include <linux/hash.h> 36 #include <linux/pid_namespace.h> 37 #include <linux/init_task.h> 38 #include <linux/syscalls.h> 39 #include <linux/proc_ns.h> 40 #include <linux/proc_fs.h> 41 #include <linux/sched/task.h> 42 #include <linux/idr.h> 43 44 struct pid init_struct_pid = INIT_STRUCT_PID; 45 46 int pid_max = PID_MAX_DEFAULT; 47 48 #define RESERVED_PIDS 300 49 50 int pid_max_min = RESERVED_PIDS + 1; 51 int pid_max_max = PID_MAX_LIMIT; 52 53 /* 54 * PID-map pages start out as NULL, they get allocated upon 55 * first use and are never deallocated. This way a low pid_max 56 * value does not cause lots of bitmaps to be allocated, but 57 * the scheme scales to up to 4 million PIDs, runtime. 58 */ 59 struct pid_namespace init_pid_ns = { 60 .kref = KREF_INIT(2), 61 .idr = IDR_INIT, 62 .pid_allocated = PIDNS_ADDING, 63 .level = 0, 64 .child_reaper = &init_task, 65 .user_ns = &init_user_ns, 66 .ns.inum = PROC_PID_INIT_INO, 67 #ifdef CONFIG_PID_NS 68 .ns.ops = &pidns_operations, 69 #endif 70 }; 71 EXPORT_SYMBOL_GPL(init_pid_ns); 72 73 /* 74 * Note: disable interrupts while the pidmap_lock is held as an 75 * interrupt might come in and do read_lock(&tasklist_lock). 76 * 77 * If we don't disable interrupts there is a nasty deadlock between 78 * detach_pid()->free_pid() and another cpu that does 79 * spin_lock(&pidmap_lock) followed by an interrupt routine that does 80 * read_lock(&tasklist_lock); 81 * 82 * After we clean up the tasklist_lock and know there are no 83 * irq handlers that take it we can leave the interrupts enabled. 84 * For now it is easier to be safe than to prove it can't happen. 85 */ 86 87 static __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock); 88 89 void put_pid(struct pid *pid) 90 { 91 struct pid_namespace *ns; 92 93 if (!pid) 94 return; 95 96 ns = pid->numbers[pid->level].ns; 97 if ((atomic_read(&pid->count) == 1) || 98 atomic_dec_and_test(&pid->count)) { 99 kmem_cache_free(ns->pid_cachep, pid); 100 put_pid_ns(ns); 101 } 102 } 103 EXPORT_SYMBOL_GPL(put_pid); 104 105 static void delayed_put_pid(struct rcu_head *rhp) 106 { 107 struct pid *pid = container_of(rhp, struct pid, rcu); 108 put_pid(pid); 109 } 110 111 void free_pid(struct pid *pid) 112 { 113 /* We can be called with write_lock_irq(&tasklist_lock) held */ 114 int i; 115 unsigned long flags; 116 117 spin_lock_irqsave(&pidmap_lock, flags); 118 for (i = 0; i <= pid->level; i++) { 119 struct upid *upid = pid->numbers + i; 120 struct pid_namespace *ns = upid->ns; 121 switch (--ns->pid_allocated) { 122 case 2: 123 case 1: 124 /* When all that is left in the pid namespace 125 * is the reaper wake up the reaper. The reaper 126 * may be sleeping in zap_pid_ns_processes(). 127 */ 128 wake_up_process(ns->child_reaper); 129 break; 130 case PIDNS_ADDING: 131 /* Handle a fork failure of the first process */ 132 WARN_ON(ns->child_reaper); 133 ns->pid_allocated = 0; 134 /* fall through */ 135 case 0: 136 schedule_work(&ns->proc_work); 137 break; 138 } 139 140 idr_remove(&ns->idr, upid->nr); 141 } 142 spin_unlock_irqrestore(&pidmap_lock, flags); 143 144 call_rcu(&pid->rcu, delayed_put_pid); 145 } 146 147 struct pid *alloc_pid(struct pid_namespace *ns) 148 { 149 struct pid *pid; 150 enum pid_type type; 151 int i, nr; 152 struct pid_namespace *tmp; 153 struct upid *upid; 154 int retval = -ENOMEM; 155 156 pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL); 157 if (!pid) 158 return ERR_PTR(retval); 159 160 tmp = ns; 161 pid->level = ns->level; 162 163 for (i = ns->level; i >= 0; i--) { 164 int pid_min = 1; 165 166 idr_preload(GFP_KERNEL); 167 spin_lock_irq(&pidmap_lock); 168 169 /* 170 * init really needs pid 1, but after reaching the maximum 171 * wrap back to RESERVED_PIDS 172 */ 173 if (idr_get_cursor(&tmp->idr) > RESERVED_PIDS) 174 pid_min = RESERVED_PIDS; 175 176 /* 177 * Store a null pointer so find_pid_ns does not find 178 * a partially initialized PID (see below). 179 */ 180 nr = idr_alloc_cyclic(&tmp->idr, NULL, pid_min, 181 pid_max, GFP_ATOMIC); 182 spin_unlock_irq(&pidmap_lock); 183 idr_preload_end(); 184 185 if (nr < 0) { 186 retval = nr; 187 goto out_free; 188 } 189 190 pid->numbers[i].nr = nr; 191 pid->numbers[i].ns = tmp; 192 tmp = tmp->parent; 193 } 194 195 if (unlikely(is_child_reaper(pid))) { 196 if (pid_ns_prepare_proc(ns)) 197 goto out_free; 198 } 199 200 get_pid_ns(ns); 201 atomic_set(&pid->count, 1); 202 for (type = 0; type < PIDTYPE_MAX; ++type) 203 INIT_HLIST_HEAD(&pid->tasks[type]); 204 205 upid = pid->numbers + ns->level; 206 spin_lock_irq(&pidmap_lock); 207 if (!(ns->pid_allocated & PIDNS_ADDING)) 208 goto out_unlock; 209 for ( ; upid >= pid->numbers; --upid) { 210 /* Make the PID visible to find_pid_ns. */ 211 idr_replace(&upid->ns->idr, pid, upid->nr); 212 upid->ns->pid_allocated++; 213 } 214 spin_unlock_irq(&pidmap_lock); 215 216 return pid; 217 218 out_unlock: 219 spin_unlock_irq(&pidmap_lock); 220 put_pid_ns(ns); 221 222 out_free: 223 spin_lock_irq(&pidmap_lock); 224 while (++i <= ns->level) 225 idr_remove(&ns->idr, (pid->numbers + i)->nr); 226 227 /* On failure to allocate the first pid, reset the state */ 228 if (ns->pid_allocated == PIDNS_ADDING) 229 idr_set_cursor(&ns->idr, 0); 230 231 spin_unlock_irq(&pidmap_lock); 232 233 kmem_cache_free(ns->pid_cachep, pid); 234 return ERR_PTR(retval); 235 } 236 237 void disable_pid_allocation(struct pid_namespace *ns) 238 { 239 spin_lock_irq(&pidmap_lock); 240 ns->pid_allocated &= ~PIDNS_ADDING; 241 spin_unlock_irq(&pidmap_lock); 242 } 243 244 struct pid *find_pid_ns(int nr, struct pid_namespace *ns) 245 { 246 return idr_find(&ns->idr, nr); 247 } 248 EXPORT_SYMBOL_GPL(find_pid_ns); 249 250 struct pid *find_vpid(int nr) 251 { 252 return find_pid_ns(nr, task_active_pid_ns(current)); 253 } 254 EXPORT_SYMBOL_GPL(find_vpid); 255 256 /* 257 * attach_pid() must be called with the tasklist_lock write-held. 258 */ 259 void attach_pid(struct task_struct *task, enum pid_type type) 260 { 261 struct pid_link *link = &task->pids[type]; 262 hlist_add_head_rcu(&link->node, &link->pid->tasks[type]); 263 } 264 265 static void __change_pid(struct task_struct *task, enum pid_type type, 266 struct pid *new) 267 { 268 struct pid_link *link; 269 struct pid *pid; 270 int tmp; 271 272 link = &task->pids[type]; 273 pid = link->pid; 274 275 hlist_del_rcu(&link->node); 276 link->pid = new; 277 278 for (tmp = PIDTYPE_MAX; --tmp >= 0; ) 279 if (!hlist_empty(&pid->tasks[tmp])) 280 return; 281 282 free_pid(pid); 283 } 284 285 void detach_pid(struct task_struct *task, enum pid_type type) 286 { 287 __change_pid(task, type, NULL); 288 } 289 290 void change_pid(struct task_struct *task, enum pid_type type, 291 struct pid *pid) 292 { 293 __change_pid(task, type, pid); 294 attach_pid(task, type); 295 } 296 297 /* transfer_pid is an optimization of attach_pid(new), detach_pid(old) */ 298 void transfer_pid(struct task_struct *old, struct task_struct *new, 299 enum pid_type type) 300 { 301 new->pids[type].pid = old->pids[type].pid; 302 hlist_replace_rcu(&old->pids[type].node, &new->pids[type].node); 303 } 304 305 struct task_struct *pid_task(struct pid *pid, enum pid_type type) 306 { 307 struct task_struct *result = NULL; 308 if (pid) { 309 struct hlist_node *first; 310 first = rcu_dereference_check(hlist_first_rcu(&pid->tasks[type]), 311 lockdep_tasklist_lock_is_held()); 312 if (first) 313 result = hlist_entry(first, struct task_struct, pids[(type)].node); 314 } 315 return result; 316 } 317 EXPORT_SYMBOL(pid_task); 318 319 /* 320 * Must be called under rcu_read_lock(). 321 */ 322 struct task_struct *find_task_by_pid_ns(pid_t nr, struct pid_namespace *ns) 323 { 324 RCU_LOCKDEP_WARN(!rcu_read_lock_held(), 325 "find_task_by_pid_ns() needs rcu_read_lock() protection"); 326 return pid_task(find_pid_ns(nr, ns), PIDTYPE_PID); 327 } 328 329 struct task_struct *find_task_by_vpid(pid_t vnr) 330 { 331 return find_task_by_pid_ns(vnr, task_active_pid_ns(current)); 332 } 333 334 struct pid *get_task_pid(struct task_struct *task, enum pid_type type) 335 { 336 struct pid *pid; 337 rcu_read_lock(); 338 if (type != PIDTYPE_PID) 339 task = task->group_leader; 340 pid = get_pid(rcu_dereference(task->pids[type].pid)); 341 rcu_read_unlock(); 342 return pid; 343 } 344 EXPORT_SYMBOL_GPL(get_task_pid); 345 346 struct task_struct *get_pid_task(struct pid *pid, enum pid_type type) 347 { 348 struct task_struct *result; 349 rcu_read_lock(); 350 result = pid_task(pid, type); 351 if (result) 352 get_task_struct(result); 353 rcu_read_unlock(); 354 return result; 355 } 356 EXPORT_SYMBOL_GPL(get_pid_task); 357 358 struct pid *find_get_pid(pid_t nr) 359 { 360 struct pid *pid; 361 362 rcu_read_lock(); 363 pid = get_pid(find_vpid(nr)); 364 rcu_read_unlock(); 365 366 return pid; 367 } 368 EXPORT_SYMBOL_GPL(find_get_pid); 369 370 pid_t pid_nr_ns(struct pid *pid, struct pid_namespace *ns) 371 { 372 struct upid *upid; 373 pid_t nr = 0; 374 375 if (pid && ns->level <= pid->level) { 376 upid = &pid->numbers[ns->level]; 377 if (upid->ns == ns) 378 nr = upid->nr; 379 } 380 return nr; 381 } 382 EXPORT_SYMBOL_GPL(pid_nr_ns); 383 384 pid_t pid_vnr(struct pid *pid) 385 { 386 return pid_nr_ns(pid, task_active_pid_ns(current)); 387 } 388 EXPORT_SYMBOL_GPL(pid_vnr); 389 390 pid_t __task_pid_nr_ns(struct task_struct *task, enum pid_type type, 391 struct pid_namespace *ns) 392 { 393 pid_t nr = 0; 394 395 rcu_read_lock(); 396 if (!ns) 397 ns = task_active_pid_ns(current); 398 if (likely(pid_alive(task))) { 399 if (type != PIDTYPE_PID) { 400 if (type == __PIDTYPE_TGID) 401 type = PIDTYPE_PID; 402 403 task = task->group_leader; 404 } 405 nr = pid_nr_ns(rcu_dereference(task->pids[type].pid), ns); 406 } 407 rcu_read_unlock(); 408 409 return nr; 410 } 411 EXPORT_SYMBOL(__task_pid_nr_ns); 412 413 struct pid_namespace *task_active_pid_ns(struct task_struct *tsk) 414 { 415 return ns_of_pid(task_pid(tsk)); 416 } 417 EXPORT_SYMBOL_GPL(task_active_pid_ns); 418 419 /* 420 * Used by proc to find the first pid that is greater than or equal to nr. 421 * 422 * If there is a pid at nr this function is exactly the same as find_pid_ns. 423 */ 424 struct pid *find_ge_pid(int nr, struct pid_namespace *ns) 425 { 426 return idr_get_next(&ns->idr, &nr); 427 } 428 429 void __init pid_idr_init(void) 430 { 431 /* Verify no one has done anything silly: */ 432 BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_ADDING); 433 434 /* bump default and minimum pid_max based on number of cpus */ 435 pid_max = min(pid_max_max, max_t(int, pid_max, 436 PIDS_PER_CPU_DEFAULT * num_possible_cpus())); 437 pid_max_min = max_t(int, pid_max_min, 438 PIDS_PER_CPU_MIN * num_possible_cpus()); 439 pr_info("pid_max: default: %u minimum: %u\n", pid_max, pid_max_min); 440 441 idr_init(&init_pid_ns.idr); 442 443 init_pid_ns.pid_cachep = KMEM_CACHE(pid, 444 SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT); 445 } 446