2 * Generic pidhash and scalable, time-bounded PID allocator
4 * (C) 2002-2003 Nadia Yvette Chambers, IBM
5 * (C) 2004 Nadia Yvette Chambers, Oracle
6 * (C) 2002-2004 Ingo Molnar, Red Hat
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.
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.
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).
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
30 #include <linux/export.h>
31 #include <linux/slab.h>
32 #include <linux/init.h>
33 #include <linux/rculist.h>
34 #include <linux/memblock.h>
35 #include <linux/pid_namespace.h>
36 #include <linux/init_task.h>
37 #include <linux/syscalls.h>
38 #include <linux/proc_ns.h>
39 #include <linux/proc_fs.h>
40 #include <linux/sched/task.h>
41 #include <linux/idr.h>
43 struct pid init_struct_pid
= {
44 .count
= ATOMIC_INIT(1),
57 int pid_max
= PID_MAX_DEFAULT
;
59 #define RESERVED_PIDS 300
61 int pid_max_min
= RESERVED_PIDS
+ 1;
62 int pid_max_max
= PID_MAX_LIMIT
;
65 * PID-map pages start out as NULL, they get allocated upon
66 * first use and are never deallocated. This way a low pid_max
67 * value does not cause lots of bitmaps to be allocated, but
68 * the scheme scales to up to 4 million PIDs, runtime.
70 struct pid_namespace init_pid_ns
= {
72 .idr
= IDR_INIT(init_pid_ns
.idr
),
73 .pid_allocated
= PIDNS_ADDING
,
75 .child_reaper
= &init_task
,
76 .user_ns
= &init_user_ns
,
77 .ns
.inum
= PROC_PID_INIT_INO
,
79 .ns
.ops
= &pidns_operations
,
82 EXPORT_SYMBOL_GPL(init_pid_ns
);
85 * Note: disable interrupts while the pidmap_lock is held as an
86 * interrupt might come in and do read_lock(&tasklist_lock).
88 * If we don't disable interrupts there is a nasty deadlock between
89 * detach_pid()->free_pid() and another cpu that does
90 * spin_lock(&pidmap_lock) followed by an interrupt routine that does
91 * read_lock(&tasklist_lock);
93 * After we clean up the tasklist_lock and know there are no
94 * irq handlers that take it we can leave the interrupts enabled.
95 * For now it is easier to be safe than to prove it can't happen.
98 static __cacheline_aligned_in_smp
DEFINE_SPINLOCK(pidmap_lock
);
100 void put_pid(struct pid
*pid
)
102 struct pid_namespace
*ns
;
107 ns
= pid
->numbers
[pid
->level
].ns
;
108 if ((atomic_read(&pid
->count
) == 1) ||
109 atomic_dec_and_test(&pid
->count
)) {
110 kmem_cache_free(ns
->pid_cachep
, pid
);
114 EXPORT_SYMBOL_GPL(put_pid
);
116 static void delayed_put_pid(struct rcu_head
*rhp
)
118 struct pid
*pid
= container_of(rhp
, struct pid
, rcu
);
122 void free_pid(struct pid
*pid
)
124 /* We can be called with write_lock_irq(&tasklist_lock) held */
128 spin_lock_irqsave(&pidmap_lock
, flags
);
129 for (i
= 0; i
<= pid
->level
; i
++) {
130 struct upid
*upid
= pid
->numbers
+ i
;
131 struct pid_namespace
*ns
= upid
->ns
;
132 switch (--ns
->pid_allocated
) {
135 /* When all that is left in the pid namespace
136 * is the reaper wake up the reaper. The reaper
137 * may be sleeping in zap_pid_ns_processes().
139 wake_up_process(ns
->child_reaper
);
142 /* Handle a fork failure of the first process */
143 WARN_ON(ns
->child_reaper
);
144 ns
->pid_allocated
= 0;
147 schedule_work(&ns
->proc_work
);
151 idr_remove(&ns
->idr
, upid
->nr
);
153 spin_unlock_irqrestore(&pidmap_lock
, flags
);
155 call_rcu(&pid
->rcu
, delayed_put_pid
);
158 struct pid
*alloc_pid(struct pid_namespace
*ns
)
163 struct pid_namespace
*tmp
;
165 int retval
= -ENOMEM
;
167 pid
= kmem_cache_alloc(ns
->pid_cachep
, GFP_KERNEL
);
169 return ERR_PTR(retval
);
172 pid
->level
= ns
->level
;
174 for (i
= ns
->level
; i
>= 0; i
--) {
177 idr_preload(GFP_KERNEL
);
178 spin_lock_irq(&pidmap_lock
);
181 * init really needs pid 1, but after reaching the maximum
182 * wrap back to RESERVED_PIDS
184 if (idr_get_cursor(&tmp
->idr
) > RESERVED_PIDS
)
185 pid_min
= RESERVED_PIDS
;
188 * Store a null pointer so find_pid_ns does not find
189 * a partially initialized PID (see below).
191 nr
= idr_alloc_cyclic(&tmp
->idr
, NULL
, pid_min
,
192 pid_max
, GFP_ATOMIC
);
193 spin_unlock_irq(&pidmap_lock
);
197 retval
= (nr
== -ENOSPC
) ? -EAGAIN
: nr
;
201 pid
->numbers
[i
].nr
= nr
;
202 pid
->numbers
[i
].ns
= tmp
;
206 if (unlikely(is_child_reaper(pid
))) {
207 if (pid_ns_prepare_proc(ns
))
212 atomic_set(&pid
->count
, 1);
213 for (type
= 0; type
< PIDTYPE_MAX
; ++type
)
214 INIT_HLIST_HEAD(&pid
->tasks
[type
]);
216 upid
= pid
->numbers
+ ns
->level
;
217 spin_lock_irq(&pidmap_lock
);
218 if (!(ns
->pid_allocated
& PIDNS_ADDING
))
220 for ( ; upid
>= pid
->numbers
; --upid
) {
221 /* Make the PID visible to find_pid_ns. */
222 idr_replace(&upid
->ns
->idr
, pid
, upid
->nr
);
223 upid
->ns
->pid_allocated
++;
225 spin_unlock_irq(&pidmap_lock
);
230 spin_unlock_irq(&pidmap_lock
);
234 spin_lock_irq(&pidmap_lock
);
235 while (++i
<= ns
->level
) {
236 upid
= pid
->numbers
+ i
;
237 idr_remove(&upid
->ns
->idr
, upid
->nr
);
240 /* On failure to allocate the first pid, reset the state */
241 if (ns
->pid_allocated
== PIDNS_ADDING
)
242 idr_set_cursor(&ns
->idr
, 0);
244 spin_unlock_irq(&pidmap_lock
);
246 kmem_cache_free(ns
->pid_cachep
, pid
);
247 return ERR_PTR(retval
);
250 void disable_pid_allocation(struct pid_namespace
*ns
)
252 spin_lock_irq(&pidmap_lock
);
253 ns
->pid_allocated
&= ~PIDNS_ADDING
;
254 spin_unlock_irq(&pidmap_lock
);
257 struct pid
*find_pid_ns(int nr
, struct pid_namespace
*ns
)
259 return idr_find(&ns
->idr
, nr
);
261 EXPORT_SYMBOL_GPL(find_pid_ns
);
263 struct pid
*find_vpid(int nr
)
265 return find_pid_ns(nr
, task_active_pid_ns(current
));
267 EXPORT_SYMBOL_GPL(find_vpid
);
269 static struct pid
**task_pid_ptr(struct task_struct
*task
, enum pid_type type
)
271 return (type
== PIDTYPE_PID
) ?
273 &task
->signal
->pids
[type
];
277 * attach_pid() must be called with the tasklist_lock write-held.
279 void attach_pid(struct task_struct
*task
, enum pid_type type
)
281 struct pid
*pid
= *task_pid_ptr(task
, type
);
282 hlist_add_head_rcu(&task
->pid_links
[type
], &pid
->tasks
[type
]);
285 static void __change_pid(struct task_struct
*task
, enum pid_type type
,
288 struct pid
**pid_ptr
= task_pid_ptr(task
, type
);
294 hlist_del_rcu(&task
->pid_links
[type
]);
297 for (tmp
= PIDTYPE_MAX
; --tmp
>= 0; )
298 if (!hlist_empty(&pid
->tasks
[tmp
]))
304 void detach_pid(struct task_struct
*task
, enum pid_type type
)
306 __change_pid(task
, type
, NULL
);
309 void change_pid(struct task_struct
*task
, enum pid_type type
,
312 __change_pid(task
, type
, pid
);
313 attach_pid(task
, type
);
316 /* transfer_pid is an optimization of attach_pid(new), detach_pid(old) */
317 void transfer_pid(struct task_struct
*old
, struct task_struct
*new,
320 if (type
== PIDTYPE_PID
)
321 new->thread_pid
= old
->thread_pid
;
322 hlist_replace_rcu(&old
->pid_links
[type
], &new->pid_links
[type
]);
325 struct task_struct
*pid_task(struct pid
*pid
, enum pid_type type
)
327 struct task_struct
*result
= NULL
;
329 struct hlist_node
*first
;
330 first
= rcu_dereference_check(hlist_first_rcu(&pid
->tasks
[type
]),
331 lockdep_tasklist_lock_is_held());
333 result
= hlist_entry(first
, struct task_struct
, pid_links
[(type
)]);
337 EXPORT_SYMBOL(pid_task
);
340 * Must be called under rcu_read_lock().
342 struct task_struct
*find_task_by_pid_ns(pid_t nr
, struct pid_namespace
*ns
)
344 RCU_LOCKDEP_WARN(!rcu_read_lock_held(),
345 "find_task_by_pid_ns() needs rcu_read_lock() protection");
346 return pid_task(find_pid_ns(nr
, ns
), PIDTYPE_PID
);
349 struct task_struct
*find_task_by_vpid(pid_t vnr
)
351 return find_task_by_pid_ns(vnr
, task_active_pid_ns(current
));
354 struct task_struct
*find_get_task_by_vpid(pid_t nr
)
356 struct task_struct
*task
;
359 task
= find_task_by_vpid(nr
);
361 get_task_struct(task
);
367 struct pid
*get_task_pid(struct task_struct
*task
, enum pid_type type
)
371 pid
= get_pid(rcu_dereference(*task_pid_ptr(task
, type
)));
375 EXPORT_SYMBOL_GPL(get_task_pid
);
377 struct task_struct
*get_pid_task(struct pid
*pid
, enum pid_type type
)
379 struct task_struct
*result
;
381 result
= pid_task(pid
, type
);
383 get_task_struct(result
);
387 EXPORT_SYMBOL_GPL(get_pid_task
);
389 struct pid
*find_get_pid(pid_t nr
)
394 pid
= get_pid(find_vpid(nr
));
399 EXPORT_SYMBOL_GPL(find_get_pid
);
401 pid_t
pid_nr_ns(struct pid
*pid
, struct pid_namespace
*ns
)
406 if (pid
&& ns
->level
<= pid
->level
) {
407 upid
= &pid
->numbers
[ns
->level
];
413 EXPORT_SYMBOL_GPL(pid_nr_ns
);
415 pid_t
pid_vnr(struct pid
*pid
)
417 return pid_nr_ns(pid
, task_active_pid_ns(current
));
419 EXPORT_SYMBOL_GPL(pid_vnr
);
421 pid_t
__task_pid_nr_ns(struct task_struct
*task
, enum pid_type type
,
422 struct pid_namespace
*ns
)
428 ns
= task_active_pid_ns(current
);
429 if (likely(pid_alive(task
)))
430 nr
= pid_nr_ns(rcu_dereference(*task_pid_ptr(task
, type
)), ns
);
435 EXPORT_SYMBOL(__task_pid_nr_ns
);
437 struct pid_namespace
*task_active_pid_ns(struct task_struct
*tsk
)
439 return ns_of_pid(task_pid(tsk
));
441 EXPORT_SYMBOL_GPL(task_active_pid_ns
);
444 * Used by proc to find the first pid that is greater than or equal to nr.
446 * If there is a pid at nr this function is exactly the same as find_pid_ns.
448 struct pid
*find_ge_pid(int nr
, struct pid_namespace
*ns
)
450 return idr_get_next(&ns
->idr
, &nr
);
453 void __init
pid_idr_init(void)
455 /* Verify no one has done anything silly: */
456 BUILD_BUG_ON(PID_MAX_LIMIT
>= PIDNS_ADDING
);
458 /* bump default and minimum pid_max based on number of cpus */
459 pid_max
= min(pid_max_max
, max_t(int, pid_max
,
460 PIDS_PER_CPU_DEFAULT
* num_possible_cpus()));
461 pid_max_min
= max_t(int, pid_max_min
,
462 PIDS_PER_CPU_MIN
* num_possible_cpus());
463 pr_info("pid_max: default: %u minimum: %u\n", pid_max
, pid_max_min
);
465 idr_init(&init_pid_ns
.idr
);
467 init_pid_ns
.pid_cachep
= KMEM_CACHE(pid
,
468 SLAB_HWCACHE_ALIGN
| SLAB_PANIC
| SLAB_ACCOUNT
);