2 * Generic pidhash and scalable, time-bounded PID allocator
4 * (C) 2002-2003 William Irwin, IBM
5 * (C) 2004 William Irwin, 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).
24 #include <linux/module.h>
25 #include <linux/slab.h>
26 #include <linux/init.h>
27 #include <linux/bootmem.h>
28 #include <linux/hash.h>
29 #include <linux/pspace.h>
31 #define pid_hashfn(nr) hash_long((unsigned long)nr, pidhash_shift)
32 static struct hlist_head
*pid_hash
;
33 static int pidhash_shift
;
34 static kmem_cache_t
*pid_cachep
;
36 int pid_max
= PID_MAX_DEFAULT
;
39 #define RESERVED_PIDS 300
41 int pid_max_min
= RESERVED_PIDS
+ 1;
42 int pid_max_max
= PID_MAX_LIMIT
;
44 #define BITS_PER_PAGE (PAGE_SIZE*8)
45 #define BITS_PER_PAGE_MASK (BITS_PER_PAGE-1)
46 #define mk_pid(map, off) (((map) - pidmap_array)*BITS_PER_PAGE + (off))
47 #define find_next_offset(map, off) \
48 find_next_zero_bit((map)->page, BITS_PER_PAGE, off)
51 * PID-map pages start out as NULL, they get allocated upon
52 * first use and are never deallocated. This way a low pid_max
53 * value does not cause lots of bitmaps to be allocated, but
54 * the scheme scales to up to 4 million PIDs, runtime.
56 static struct pidmap pidmap_array
[PIDMAP_ENTRIES
] =
57 { [ 0 ... PIDMAP_ENTRIES
-1 ] = { ATOMIC_INIT(BITS_PER_PAGE
), NULL
} };
60 * Note: disable interrupts while the pidmap_lock is held as an
61 * interrupt might come in and do read_lock(&tasklist_lock).
63 * If we don't disable interrupts there is a nasty deadlock between
64 * detach_pid()->free_pid() and another cpu that does
65 * spin_lock(&pidmap_lock) followed by an interrupt routine that does
66 * read_lock(&tasklist_lock);
68 * After we clean up the tasklist_lock and know there are no
69 * irq handlers that take it we can leave the interrupts enabled.
70 * For now it is easier to be safe than to prove it can't happen.
72 static __cacheline_aligned_in_smp
DEFINE_SPINLOCK(pidmap_lock
);
74 static fastcall
void free_pidmap(int pid
)
76 struct pidmap
*map
= pidmap_array
+ pid
/ BITS_PER_PAGE
;
77 int offset
= pid
& BITS_PER_PAGE_MASK
;
79 clear_bit(offset
, map
->page
);
80 atomic_inc(&map
->nr_free
);
83 static int alloc_pidmap(void)
85 int i
, offset
, max_scan
, pid
, last
= last_pid
;
91 offset
= pid
& BITS_PER_PAGE_MASK
;
92 map
= &pidmap_array
[pid
/BITS_PER_PAGE
];
93 max_scan
= (pid_max
+ BITS_PER_PAGE
- 1)/BITS_PER_PAGE
- !offset
;
94 for (i
= 0; i
<= max_scan
; ++i
) {
95 if (unlikely(!map
->page
)) {
96 unsigned long page
= get_zeroed_page(GFP_KERNEL
);
98 * Free the page if someone raced with us
101 spin_lock_irq(&pidmap_lock
);
105 map
->page
= (void *)page
;
106 spin_unlock_irq(&pidmap_lock
);
107 if (unlikely(!map
->page
))
110 if (likely(atomic_read(&map
->nr_free
))) {
112 if (!test_and_set_bit(offset
, map
->page
)) {
113 atomic_dec(&map
->nr_free
);
117 offset
= find_next_offset(map
, offset
);
118 pid
= mk_pid(map
, offset
);
120 * find_next_offset() found a bit, the pid from it
121 * is in-bounds, and if we fell back to the last
122 * bitmap block and the final block was the same
123 * as the starting point, pid is before last_pid.
125 } while (offset
< BITS_PER_PAGE
&& pid
< pid_max
&&
126 (i
!= max_scan
|| pid
< last
||
127 !((last
+1) & BITS_PER_PAGE_MASK
)));
129 if (map
< &pidmap_array
[(pid_max
-1)/BITS_PER_PAGE
]) {
133 map
= &pidmap_array
[0];
134 offset
= RESERVED_PIDS
;
135 if (unlikely(last
== offset
))
138 pid
= mk_pid(map
, offset
);
143 static int next_pidmap(int last
)
148 offset
= (last
+ 1) & BITS_PER_PAGE_MASK
;
149 map
= &pidmap_array
[(last
+ 1)/BITS_PER_PAGE
];
150 for (; map
< &pidmap_array
[PIDMAP_ENTRIES
]; map
++, offset
= 0) {
151 if (unlikely(!map
->page
))
153 offset
= find_next_bit((map
)->page
, BITS_PER_PAGE
, offset
);
154 if (offset
< BITS_PER_PAGE
)
155 return mk_pid(map
, offset
);
160 fastcall
void put_pid(struct pid
*pid
)
164 if ((atomic_read(&pid
->count
) == 1) ||
165 atomic_dec_and_test(&pid
->count
))
166 kmem_cache_free(pid_cachep
, pid
);
168 EXPORT_SYMBOL_GPL(put_pid
);
170 static void delayed_put_pid(struct rcu_head
*rhp
)
172 struct pid
*pid
= container_of(rhp
, struct pid
, rcu
);
176 fastcall
void free_pid(struct pid
*pid
)
178 /* We can be called with write_lock_irq(&tasklist_lock) held */
181 spin_lock_irqsave(&pidmap_lock
, flags
);
182 hlist_del_rcu(&pid
->pid_chain
);
183 spin_unlock_irqrestore(&pidmap_lock
, flags
);
185 free_pidmap(pid
->nr
);
186 call_rcu(&pid
->rcu
, delayed_put_pid
);
189 struct pid
*alloc_pid(void)
195 pid
= kmem_cache_alloc(pid_cachep
, GFP_KERNEL
);
203 atomic_set(&pid
->count
, 1);
205 for (type
= 0; type
< PIDTYPE_MAX
; ++type
)
206 INIT_HLIST_HEAD(&pid
->tasks
[type
]);
208 spin_lock_irq(&pidmap_lock
);
209 hlist_add_head_rcu(&pid
->pid_chain
, &pid_hash
[pid_hashfn(pid
->nr
)]);
210 spin_unlock_irq(&pidmap_lock
);
216 kmem_cache_free(pid_cachep
, pid
);
221 struct pid
* fastcall
find_pid(int nr
)
223 struct hlist_node
*elem
;
226 hlist_for_each_entry_rcu(pid
, elem
,
227 &pid_hash
[pid_hashfn(nr
)], pid_chain
) {
233 EXPORT_SYMBOL_GPL(find_pid
);
235 int fastcall
attach_pid(struct task_struct
*task
, enum pid_type type
, int nr
)
237 struct pid_link
*link
;
240 link
= &task
->pids
[type
];
241 link
->pid
= pid
= find_pid(nr
);
242 hlist_add_head_rcu(&link
->node
, &pid
->tasks
[type
]);
247 void fastcall
detach_pid(struct task_struct
*task
, enum pid_type type
)
249 struct pid_link
*link
;
253 link
= &task
->pids
[type
];
256 hlist_del_rcu(&link
->node
);
259 for (tmp
= PIDTYPE_MAX
; --tmp
>= 0; )
260 if (!hlist_empty(&pid
->tasks
[tmp
]))
266 /* transfer_pid is an optimization of attach_pid(new), detach_pid(old) */
267 void fastcall
transfer_pid(struct task_struct
*old
, struct task_struct
*new,
270 new->pids
[type
].pid
= old
->pids
[type
].pid
;
271 hlist_replace_rcu(&old
->pids
[type
].node
, &new->pids
[type
].node
);
272 old
->pids
[type
].pid
= NULL
;
275 struct task_struct
* fastcall
pid_task(struct pid
*pid
, enum pid_type type
)
277 struct task_struct
*result
= NULL
;
279 struct hlist_node
*first
;
280 first
= rcu_dereference(pid
->tasks
[type
].first
);
282 result
= hlist_entry(first
, struct task_struct
, pids
[(type
)].node
);
288 * Must be called under rcu_read_lock() or with tasklist_lock read-held.
290 struct task_struct
*find_task_by_pid_type(int type
, int nr
)
292 return pid_task(find_pid(nr
), type
);
295 EXPORT_SYMBOL(find_task_by_pid_type
);
297 struct task_struct
*fastcall
get_pid_task(struct pid
*pid
, enum pid_type type
)
299 struct task_struct
*result
;
301 result
= pid_task(pid
, type
);
303 get_task_struct(result
);
308 struct pid
*find_get_pid(pid_t nr
)
313 pid
= get_pid(find_pid(nr
));
320 * Used by proc to find the first pid that is greater then or equal to nr.
322 * If there is a pid at nr this function is exactly the same as find_pid.
324 struct pid
*find_ge_pid(int nr
)
332 nr
= next_pidmap(nr
);
337 EXPORT_SYMBOL_GPL(find_get_pid
);
340 * The pid hash table is scaled according to the amount of memory in the
341 * machine. From a minimum of 16 slots up to 4096 slots at one gigabyte or
344 void __init
pidhash_init(void)
347 unsigned long megabytes
= nr_kernel_pages
>> (20 - PAGE_SHIFT
);
349 pidhash_shift
= max(4, fls(megabytes
* 4));
350 pidhash_shift
= min(12, pidhash_shift
);
351 pidhash_size
= 1 << pidhash_shift
;
353 printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
354 pidhash_size
, pidhash_shift
,
355 pidhash_size
* sizeof(struct hlist_head
));
357 pid_hash
= alloc_bootmem(pidhash_size
* sizeof(*(pid_hash
)));
359 panic("Could not alloc pidhash!\n");
360 for (i
= 0; i
< pidhash_size
; i
++)
361 INIT_HLIST_HEAD(&pid_hash
[i
]);
364 void __init
pidmap_init(void)
366 pidmap_array
->page
= (void *)get_zeroed_page(GFP_KERNEL
);
367 /* Reserve PID 0. We never call free_pidmap(0) */
368 set_bit(0, pidmap_array
->page
);
369 atomic_dec(&pidmap_array
->nr_free
);
371 pid_cachep
= kmem_cache_create("pid", sizeof(struct pid
),
372 __alignof__(struct pid
),
373 SLAB_PANIC
, NULL
, NULL
);