pid: replace pid bitmap implementation with IDR API
[muen/linux.git] / kernel / pid.c
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 #define pid_hashfn(nr, ns)      \
45         hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
46 static struct hlist_head *pid_hash;
47 static unsigned int pidhash_shift = 4;
48 struct pid init_struct_pid = INIT_STRUCT_PID;
49
50 int pid_max = PID_MAX_DEFAULT;
51
52 #define RESERVED_PIDS           300
53
54 int pid_max_min = RESERVED_PIDS + 1;
55 int pid_max_max = PID_MAX_LIMIT;
56
57
58 /*
59  * PID-map pages start out as NULL, they get allocated upon
60  * first use and are never deallocated. This way a low pid_max
61  * value does not cause lots of bitmaps to be allocated, but
62  * the scheme scales to up to 4 million PIDs, runtime.
63  */
64 struct pid_namespace init_pid_ns = {
65         .kref = KREF_INIT(2),
66         .idr = IDR_INIT,
67         .nr_hashed = PIDNS_HASH_ADDING,
68         .level = 0,
69         .child_reaper = &init_task,
70         .user_ns = &init_user_ns,
71         .ns.inum = PROC_PID_INIT_INO,
72 #ifdef CONFIG_PID_NS
73         .ns.ops = &pidns_operations,
74 #endif
75 };
76 EXPORT_SYMBOL_GPL(init_pid_ns);
77
78 /*
79  * Note: disable interrupts while the pidmap_lock is held as an
80  * interrupt might come in and do read_lock(&tasklist_lock).
81  *
82  * If we don't disable interrupts there is a nasty deadlock between
83  * detach_pid()->free_pid() and another cpu that does
84  * spin_lock(&pidmap_lock) followed by an interrupt routine that does
85  * read_lock(&tasklist_lock);
86  *
87  * After we clean up the tasklist_lock and know there are no
88  * irq handlers that take it we can leave the interrupts enabled.
89  * For now it is easier to be safe than to prove it can't happen.
90  */
91
92 static  __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock);
93
94 void put_pid(struct pid *pid)
95 {
96         struct pid_namespace *ns;
97
98         if (!pid)
99                 return;
100
101         ns = pid->numbers[pid->level].ns;
102         if ((atomic_read(&pid->count) == 1) ||
103              atomic_dec_and_test(&pid->count)) {
104                 kmem_cache_free(ns->pid_cachep, pid);
105                 put_pid_ns(ns);
106         }
107 }
108 EXPORT_SYMBOL_GPL(put_pid);
109
110 static void delayed_put_pid(struct rcu_head *rhp)
111 {
112         struct pid *pid = container_of(rhp, struct pid, rcu);
113         put_pid(pid);
114 }
115
116 void free_pid(struct pid *pid)
117 {
118         /* We can be called with write_lock_irq(&tasklist_lock) held */
119         int i;
120         unsigned long flags;
121
122         spin_lock_irqsave(&pidmap_lock, flags);
123         for (i = 0; i <= pid->level; i++) {
124                 struct upid *upid = pid->numbers + i;
125                 struct pid_namespace *ns = upid->ns;
126                 hlist_del_rcu(&upid->pid_chain);
127                 switch (--ns->nr_hashed) {
128                 case 2:
129                 case 1:
130                         /* When all that is left in the pid namespace
131                          * is the reaper wake up the reaper.  The reaper
132                          * may be sleeping in zap_pid_ns_processes().
133                          */
134                         wake_up_process(ns->child_reaper);
135                         break;
136                 case PIDNS_HASH_ADDING:
137                         /* Handle a fork failure of the first process */
138                         WARN_ON(ns->child_reaper);
139                         ns->nr_hashed = 0;
140                         /* fall through */
141                 case 0:
142                         schedule_work(&ns->proc_work);
143                         break;
144                 }
145
146                 idr_remove(&ns->idr, upid->nr);
147         }
148         spin_unlock_irqrestore(&pidmap_lock, flags);
149
150         call_rcu(&pid->rcu, delayed_put_pid);
151 }
152
153 struct pid *alloc_pid(struct pid_namespace *ns)
154 {
155         struct pid *pid;
156         enum pid_type type;
157         int i, nr;
158         struct pid_namespace *tmp;
159         struct upid *upid;
160         int retval = -ENOMEM;
161
162         pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL);
163         if (!pid)
164                 return ERR_PTR(retval);
165
166         tmp = ns;
167         pid->level = ns->level;
168
169         for (i = ns->level; i >= 0; i--) {
170                 int pid_min = 1;
171
172                 idr_preload(GFP_KERNEL);
173                 spin_lock_irq(&pidmap_lock);
174
175                 /*
176                  * init really needs pid 1, but after reaching the maximum
177                  * wrap back to RESERVED_PIDS
178                  */
179                 if (idr_get_cursor(&tmp->idr) > RESERVED_PIDS)
180                         pid_min = RESERVED_PIDS;
181
182                 /*
183                  * Store a null pointer so find_pid_ns does not find
184                  * a partially initialized PID (see below).
185                  */
186                 nr = idr_alloc_cyclic(&tmp->idr, NULL, pid_min,
187                                       pid_max, GFP_ATOMIC);
188                 spin_unlock_irq(&pidmap_lock);
189                 idr_preload_end();
190
191                 if (nr < 0) {
192                         retval = nr;
193                         goto out_free;
194                 }
195
196                 pid->numbers[i].nr = nr;
197                 pid->numbers[i].ns = tmp;
198                 tmp = tmp->parent;
199         }
200
201         if (unlikely(is_child_reaper(pid))) {
202                 if (pid_ns_prepare_proc(ns)) {
203                         disable_pid_allocation(ns);
204                         goto out_free;
205                 }
206         }
207
208         get_pid_ns(ns);
209         atomic_set(&pid->count, 1);
210         for (type = 0; type < PIDTYPE_MAX; ++type)
211                 INIT_HLIST_HEAD(&pid->tasks[type]);
212
213         upid = pid->numbers + ns->level;
214         spin_lock_irq(&pidmap_lock);
215         if (!(ns->nr_hashed & PIDNS_HASH_ADDING))
216                 goto out_unlock;
217         for ( ; upid >= pid->numbers; --upid) {
218                 hlist_add_head_rcu(&upid->pid_chain,
219                                 &pid_hash[pid_hashfn(upid->nr, upid->ns)]);
220                 /* Make the PID visible to find_pid_ns. */
221                 idr_replace(&upid->ns->idr, pid, upid->nr);
222                 upid->ns->nr_hashed++;
223         }
224         spin_unlock_irq(&pidmap_lock);
225
226         return pid;
227
228 out_unlock:
229         spin_unlock_irq(&pidmap_lock);
230         put_pid_ns(ns);
231
232 out_free:
233         spin_lock_irq(&pidmap_lock);
234         while (++i <= ns->level)
235                 idr_remove(&ns->idr, (pid->numbers + i)->nr);
236
237         spin_unlock_irq(&pidmap_lock);
238
239         kmem_cache_free(ns->pid_cachep, pid);
240         return ERR_PTR(retval);
241 }
242
243 void disable_pid_allocation(struct pid_namespace *ns)
244 {
245         spin_lock_irq(&pidmap_lock);
246         ns->nr_hashed &= ~PIDNS_HASH_ADDING;
247         spin_unlock_irq(&pidmap_lock);
248 }
249
250 struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
251 {
252         struct upid *pnr;
253
254         hlist_for_each_entry_rcu(pnr,
255                         &pid_hash[pid_hashfn(nr, ns)], pid_chain)
256                 if (pnr->nr == nr && pnr->ns == ns)
257                         return container_of(pnr, struct pid,
258                                         numbers[ns->level]);
259
260         return NULL;
261 }
262 EXPORT_SYMBOL_GPL(find_pid_ns);
263
264 struct pid *find_vpid(int nr)
265 {
266         return find_pid_ns(nr, task_active_pid_ns(current));
267 }
268 EXPORT_SYMBOL_GPL(find_vpid);
269
270 /*
271  * attach_pid() must be called with the tasklist_lock write-held.
272  */
273 void attach_pid(struct task_struct *task, enum pid_type type)
274 {
275         struct pid_link *link = &task->pids[type];
276         hlist_add_head_rcu(&link->node, &link->pid->tasks[type]);
277 }
278
279 static void __change_pid(struct task_struct *task, enum pid_type type,
280                         struct pid *new)
281 {
282         struct pid_link *link;
283         struct pid *pid;
284         int tmp;
285
286         link = &task->pids[type];
287         pid = link->pid;
288
289         hlist_del_rcu(&link->node);
290         link->pid = new;
291
292         for (tmp = PIDTYPE_MAX; --tmp >= 0; )
293                 if (!hlist_empty(&pid->tasks[tmp]))
294                         return;
295
296         free_pid(pid);
297 }
298
299 void detach_pid(struct task_struct *task, enum pid_type type)
300 {
301         __change_pid(task, type, NULL);
302 }
303
304 void change_pid(struct task_struct *task, enum pid_type type,
305                 struct pid *pid)
306 {
307         __change_pid(task, type, pid);
308         attach_pid(task, type);
309 }
310
311 /* transfer_pid is an optimization of attach_pid(new), detach_pid(old) */
312 void transfer_pid(struct task_struct *old, struct task_struct *new,
313                            enum pid_type type)
314 {
315         new->pids[type].pid = old->pids[type].pid;
316         hlist_replace_rcu(&old->pids[type].node, &new->pids[type].node);
317 }
318
319 struct task_struct *pid_task(struct pid *pid, enum pid_type type)
320 {
321         struct task_struct *result = NULL;
322         if (pid) {
323                 struct hlist_node *first;
324                 first = rcu_dereference_check(hlist_first_rcu(&pid->tasks[type]),
325                                               lockdep_tasklist_lock_is_held());
326                 if (first)
327                         result = hlist_entry(first, struct task_struct, pids[(type)].node);
328         }
329         return result;
330 }
331 EXPORT_SYMBOL(pid_task);
332
333 /*
334  * Must be called under rcu_read_lock().
335  */
336 struct task_struct *find_task_by_pid_ns(pid_t nr, struct pid_namespace *ns)
337 {
338         RCU_LOCKDEP_WARN(!rcu_read_lock_held(),
339                          "find_task_by_pid_ns() needs rcu_read_lock() protection");
340         return pid_task(find_pid_ns(nr, ns), PIDTYPE_PID);
341 }
342
343 struct task_struct *find_task_by_vpid(pid_t vnr)
344 {
345         return find_task_by_pid_ns(vnr, task_active_pid_ns(current));
346 }
347
348 struct pid *get_task_pid(struct task_struct *task, enum pid_type type)
349 {
350         struct pid *pid;
351         rcu_read_lock();
352         if (type != PIDTYPE_PID)
353                 task = task->group_leader;
354         pid = get_pid(rcu_dereference(task->pids[type].pid));
355         rcu_read_unlock();
356         return pid;
357 }
358 EXPORT_SYMBOL_GPL(get_task_pid);
359
360 struct task_struct *get_pid_task(struct pid *pid, enum pid_type type)
361 {
362         struct task_struct *result;
363         rcu_read_lock();
364         result = pid_task(pid, type);
365         if (result)
366                 get_task_struct(result);
367         rcu_read_unlock();
368         return result;
369 }
370 EXPORT_SYMBOL_GPL(get_pid_task);
371
372 struct pid *find_get_pid(pid_t nr)
373 {
374         struct pid *pid;
375
376         rcu_read_lock();
377         pid = get_pid(find_vpid(nr));
378         rcu_read_unlock();
379
380         return pid;
381 }
382 EXPORT_SYMBOL_GPL(find_get_pid);
383
384 pid_t pid_nr_ns(struct pid *pid, struct pid_namespace *ns)
385 {
386         struct upid *upid;
387         pid_t nr = 0;
388
389         if (pid && ns->level <= pid->level) {
390                 upid = &pid->numbers[ns->level];
391                 if (upid->ns == ns)
392                         nr = upid->nr;
393         }
394         return nr;
395 }
396 EXPORT_SYMBOL_GPL(pid_nr_ns);
397
398 pid_t pid_vnr(struct pid *pid)
399 {
400         return pid_nr_ns(pid, task_active_pid_ns(current));
401 }
402 EXPORT_SYMBOL_GPL(pid_vnr);
403
404 pid_t __task_pid_nr_ns(struct task_struct *task, enum pid_type type,
405                         struct pid_namespace *ns)
406 {
407         pid_t nr = 0;
408
409         rcu_read_lock();
410         if (!ns)
411                 ns = task_active_pid_ns(current);
412         if (likely(pid_alive(task))) {
413                 if (type != PIDTYPE_PID) {
414                         if (type == __PIDTYPE_TGID)
415                                 type = PIDTYPE_PID;
416                         task = task->group_leader;
417                 }
418                 nr = pid_nr_ns(rcu_dereference(task->pids[type].pid), ns);
419         }
420         rcu_read_unlock();
421
422         return nr;
423 }
424 EXPORT_SYMBOL(__task_pid_nr_ns);
425
426 struct pid_namespace *task_active_pid_ns(struct task_struct *tsk)
427 {
428         return ns_of_pid(task_pid(tsk));
429 }
430 EXPORT_SYMBOL_GPL(task_active_pid_ns);
431
432 /*
433  * Used by proc to find the first pid that is greater than or equal to nr.
434  *
435  * If there is a pid at nr this function is exactly the same as find_pid_ns.
436  */
437 struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
438 {
439         return idr_get_next(&ns->idr, &nr);
440 }
441
442 /*
443  * The pid hash table is scaled according to the amount of memory in the
444  * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
445  * more.
446  */
447 void __init pidhash_init(void)
448 {
449         pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
450                                            HASH_EARLY | HASH_SMALL | HASH_ZERO,
451                                            &pidhash_shift, NULL,
452                                            0, 4096);
453 }
454
455 void __init pid_idr_init(void)
456 {
457         /* Verify no one has done anything silly: */
458         BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_HASH_ADDING);
459
460         /* bump default and minimum pid_max based on number of cpus */
461         pid_max = min(pid_max_max, max_t(int, pid_max,
462                                 PIDS_PER_CPU_DEFAULT * num_possible_cpus()));
463         pid_max_min = max_t(int, pid_max_min,
464                                 PIDS_PER_CPU_MIN * num_possible_cpus());
465         pr_info("pid_max: default: %u minimum: %u\n", pid_max, pid_max_min);
466
467         idr_init(&init_pid_ns.idr);
468
469         init_pid_ns.pid_cachep = KMEM_CACHE(pid,
470                         SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT);
471 }