pid.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418
  1. /*
  2. * Generic pidhash and scalable, time-bounded PID allocator
  3. *
  4. * (C) 2002-2003 William Irwin, IBM
  5. * (C) 2004 William Irwin, 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. #include <linux/mm.h>
  23. #include <linux/module.h>
  24. #include <linux/slab.h>
  25. #include <linux/init.h>
  26. #include <linux/bootmem.h>
  27. #include <linux/hash.h>
  28. #include <linux/pid_namespace.h>
  29. #define pid_hashfn(nr) hash_long((unsigned long)nr, pidhash_shift)
  30. static struct hlist_head *pid_hash;
  31. static int pidhash_shift;
  32. static struct kmem_cache *pid_cachep;
  33. int pid_max = PID_MAX_DEFAULT;
  34. #define RESERVED_PIDS 300
  35. int pid_max_min = RESERVED_PIDS + 1;
  36. int pid_max_max = PID_MAX_LIMIT;
  37. #define BITS_PER_PAGE (PAGE_SIZE*8)
  38. #define BITS_PER_PAGE_MASK (BITS_PER_PAGE-1)
  39. static inline int mk_pid(struct pid_namespace *pid_ns,
  40. struct pidmap *map, int off)
  41. {
  42. return (map - pid_ns->pidmap)*BITS_PER_PAGE + off;
  43. }
  44. #define find_next_offset(map, off) \
  45. find_next_zero_bit((map)->page, BITS_PER_PAGE, off)
  46. /*
  47. * PID-map pages start out as NULL, they get allocated upon
  48. * first use and are never deallocated. This way a low pid_max
  49. * value does not cause lots of bitmaps to be allocated, but
  50. * the scheme scales to up to 4 million PIDs, runtime.
  51. */
  52. struct pid_namespace init_pid_ns = {
  53. .kref = {
  54. .refcount = ATOMIC_INIT(2),
  55. },
  56. .pidmap = {
  57. [ 0 ... PIDMAP_ENTRIES-1] = { ATOMIC_INIT(BITS_PER_PAGE), NULL }
  58. },
  59. .last_pid = 0,
  60. .child_reaper = &init_task
  61. };
  62. /*
  63. * Note: disable interrupts while the pidmap_lock is held as an
  64. * interrupt might come in and do read_lock(&tasklist_lock).
  65. *
  66. * If we don't disable interrupts there is a nasty deadlock between
  67. * detach_pid()->free_pid() and another cpu that does
  68. * spin_lock(&pidmap_lock) followed by an interrupt routine that does
  69. * read_lock(&tasklist_lock);
  70. *
  71. * After we clean up the tasklist_lock and know there are no
  72. * irq handlers that take it we can leave the interrupts enabled.
  73. * For now it is easier to be safe than to prove it can't happen.
  74. */
  75. static __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock);
  76. static fastcall void free_pidmap(struct pid_namespace *pid_ns, int pid)
  77. {
  78. struct pidmap *map = pid_ns->pidmap + pid / BITS_PER_PAGE;
  79. int offset = pid & BITS_PER_PAGE_MASK;
  80. clear_bit(offset, map->page);
  81. atomic_inc(&map->nr_free);
  82. }
  83. static int alloc_pidmap(struct pid_namespace *pid_ns)
  84. {
  85. int i, offset, max_scan, pid, last = pid_ns->last_pid;
  86. struct pidmap *map;
  87. pid = last + 1;
  88. if (pid >= pid_max)
  89. pid = RESERVED_PIDS;
  90. offset = pid & BITS_PER_PAGE_MASK;
  91. map = &pid_ns->pidmap[pid/BITS_PER_PAGE];
  92. max_scan = (pid_max + BITS_PER_PAGE - 1)/BITS_PER_PAGE - !offset;
  93. for (i = 0; i <= max_scan; ++i) {
  94. if (unlikely(!map->page)) {
  95. void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);
  96. /*
  97. * Free the page if someone raced with us
  98. * installing it:
  99. */
  100. spin_lock_irq(&pidmap_lock);
  101. if (map->page)
  102. kfree(page);
  103. else
  104. map->page = page;
  105. spin_unlock_irq(&pidmap_lock);
  106. if (unlikely(!map->page))
  107. break;
  108. }
  109. if (likely(atomic_read(&map->nr_free))) {
  110. do {
  111. if (!test_and_set_bit(offset, map->page)) {
  112. atomic_dec(&map->nr_free);
  113. pid_ns->last_pid = pid;
  114. return pid;
  115. }
  116. offset = find_next_offset(map, offset);
  117. pid = mk_pid(pid_ns, map, offset);
  118. /*
  119. * find_next_offset() found a bit, the pid from it
  120. * is in-bounds, and if we fell back to the last
  121. * bitmap block and the final block was the same
  122. * as the starting point, pid is before last_pid.
  123. */
  124. } while (offset < BITS_PER_PAGE && pid < pid_max &&
  125. (i != max_scan || pid < last ||
  126. !((last+1) & BITS_PER_PAGE_MASK)));
  127. }
  128. if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {
  129. ++map;
  130. offset = 0;
  131. } else {
  132. map = &pid_ns->pidmap[0];
  133. offset = RESERVED_PIDS;
  134. if (unlikely(last == offset))
  135. break;
  136. }
  137. pid = mk_pid(pid_ns, map, offset);
  138. }
  139. return -1;
  140. }
  141. static int next_pidmap(struct pid_namespace *pid_ns, int last)
  142. {
  143. int offset;
  144. struct pidmap *map, *end;
  145. offset = (last + 1) & BITS_PER_PAGE_MASK;
  146. map = &pid_ns->pidmap[(last + 1)/BITS_PER_PAGE];
  147. end = &pid_ns->pidmap[PIDMAP_ENTRIES];
  148. for (; map < end; map++, offset = 0) {
  149. if (unlikely(!map->page))
  150. continue;
  151. offset = find_next_bit((map)->page, BITS_PER_PAGE, offset);
  152. if (offset < BITS_PER_PAGE)
  153. return mk_pid(pid_ns, map, offset);
  154. }
  155. return -1;
  156. }
  157. fastcall void put_pid(struct pid *pid)
  158. {
  159. if (!pid)
  160. return;
  161. if ((atomic_read(&pid->count) == 1) ||
  162. atomic_dec_and_test(&pid->count))
  163. kmem_cache_free(pid_cachep, pid);
  164. }
  165. EXPORT_SYMBOL_GPL(put_pid);
  166. static void delayed_put_pid(struct rcu_head *rhp)
  167. {
  168. struct pid *pid = container_of(rhp, struct pid, rcu);
  169. put_pid(pid);
  170. }
  171. fastcall void free_pid(struct pid *pid)
  172. {
  173. /* We can be called with write_lock_irq(&tasklist_lock) held */
  174. unsigned long flags;
  175. spin_lock_irqsave(&pidmap_lock, flags);
  176. hlist_del_rcu(&pid->pid_chain);
  177. spin_unlock_irqrestore(&pidmap_lock, flags);
  178. free_pidmap(&init_pid_ns, pid->nr);
  179. call_rcu(&pid->rcu, delayed_put_pid);
  180. }
  181. struct pid *alloc_pid(void)
  182. {
  183. struct pid *pid;
  184. enum pid_type type;
  185. int nr = -1;
  186. pid = kmem_cache_alloc(pid_cachep, GFP_KERNEL);
  187. if (!pid)
  188. goto out;
  189. nr = alloc_pidmap(current->nsproxy->pid_ns);
  190. if (nr < 0)
  191. goto out_free;
  192. atomic_set(&pid->count, 1);
  193. pid->nr = nr;
  194. for (type = 0; type < PIDTYPE_MAX; ++type)
  195. INIT_HLIST_HEAD(&pid->tasks[type]);
  196. spin_lock_irq(&pidmap_lock);
  197. hlist_add_head_rcu(&pid->pid_chain, &pid_hash[pid_hashfn(pid->nr)]);
  198. spin_unlock_irq(&pidmap_lock);
  199. out:
  200. return pid;
  201. out_free:
  202. kmem_cache_free(pid_cachep, pid);
  203. pid = NULL;
  204. goto out;
  205. }
  206. struct pid * fastcall find_pid(int nr)
  207. {
  208. struct hlist_node *elem;
  209. struct pid *pid;
  210. hlist_for_each_entry_rcu(pid, elem,
  211. &pid_hash[pid_hashfn(nr)], pid_chain) {
  212. if (pid->nr == nr)
  213. return pid;
  214. }
  215. return NULL;
  216. }
  217. EXPORT_SYMBOL_GPL(find_pid);
  218. int fastcall attach_pid(struct task_struct *task, enum pid_type type, int nr)
  219. {
  220. struct pid_link *link;
  221. struct pid *pid;
  222. link = &task->pids[type];
  223. link->pid = pid = find_pid(nr);
  224. hlist_add_head_rcu(&link->node, &pid->tasks[type]);
  225. return 0;
  226. }
  227. void fastcall detach_pid(struct task_struct *task, enum pid_type type)
  228. {
  229. struct pid_link *link;
  230. struct pid *pid;
  231. int tmp;
  232. link = &task->pids[type];
  233. pid = link->pid;
  234. hlist_del_rcu(&link->node);
  235. link->pid = NULL;
  236. for (tmp = PIDTYPE_MAX; --tmp >= 0; )
  237. if (!hlist_empty(&pid->tasks[tmp]))
  238. return;
  239. free_pid(pid);
  240. }
  241. /* transfer_pid is an optimization of attach_pid(new), detach_pid(old) */
  242. void fastcall transfer_pid(struct task_struct *old, struct task_struct *new,
  243. enum pid_type type)
  244. {
  245. new->pids[type].pid = old->pids[type].pid;
  246. hlist_replace_rcu(&old->pids[type].node, &new->pids[type].node);
  247. old->pids[type].pid = NULL;
  248. }
  249. struct task_struct * fastcall pid_task(struct pid *pid, enum pid_type type)
  250. {
  251. struct task_struct *result = NULL;
  252. if (pid) {
  253. struct hlist_node *first;
  254. first = rcu_dereference(pid->tasks[type].first);
  255. if (first)
  256. result = hlist_entry(first, struct task_struct, pids[(type)].node);
  257. }
  258. return result;
  259. }
  260. /*
  261. * Must be called under rcu_read_lock() or with tasklist_lock read-held.
  262. */
  263. struct task_struct *find_task_by_pid_type(int type, int nr)
  264. {
  265. return pid_task(find_pid(nr), type);
  266. }
  267. EXPORT_SYMBOL(find_task_by_pid_type);
  268. struct pid *get_task_pid(struct task_struct *task, enum pid_type type)
  269. {
  270. struct pid *pid;
  271. rcu_read_lock();
  272. pid = get_pid(task->pids[type].pid);
  273. rcu_read_unlock();
  274. return pid;
  275. }
  276. struct task_struct *fastcall get_pid_task(struct pid *pid, enum pid_type type)
  277. {
  278. struct task_struct *result;
  279. rcu_read_lock();
  280. result = pid_task(pid, type);
  281. if (result)
  282. get_task_struct(result);
  283. rcu_read_unlock();
  284. return result;
  285. }
  286. struct pid *find_get_pid(pid_t nr)
  287. {
  288. struct pid *pid;
  289. rcu_read_lock();
  290. pid = get_pid(find_pid(nr));
  291. rcu_read_unlock();
  292. return pid;
  293. }
  294. /*
  295. * Used by proc to find the first pid that is greater then or equal to nr.
  296. *
  297. * If there is a pid at nr this function is exactly the same as find_pid.
  298. */
  299. struct pid *find_ge_pid(int nr)
  300. {
  301. struct pid *pid;
  302. do {
  303. pid = find_pid(nr);
  304. if (pid)
  305. break;
  306. nr = next_pidmap(current->nsproxy->pid_ns, nr);
  307. } while (nr > 0);
  308. return pid;
  309. }
  310. EXPORT_SYMBOL_GPL(find_get_pid);
  311. int copy_pid_ns(int flags, struct task_struct *tsk)
  312. {
  313. struct pid_namespace *old_ns = tsk->nsproxy->pid_ns;
  314. int err = 0;
  315. if (!old_ns)
  316. return 0;
  317. get_pid_ns(old_ns);
  318. return err;
  319. }
  320. void free_pid_ns(struct kref *kref)
  321. {
  322. struct pid_namespace *ns;
  323. ns = container_of(kref, struct pid_namespace, kref);
  324. kfree(ns);
  325. }
  326. /*
  327. * The pid hash table is scaled according to the amount of memory in the
  328. * machine. From a minimum of 16 slots up to 4096 slots at one gigabyte or
  329. * more.
  330. */
  331. void __init pidhash_init(void)
  332. {
  333. int i, pidhash_size;
  334. unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);
  335. pidhash_shift = max(4, fls(megabytes * 4));
  336. pidhash_shift = min(12, pidhash_shift);
  337. pidhash_size = 1 << pidhash_shift;
  338. printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
  339. pidhash_size, pidhash_shift,
  340. pidhash_size * sizeof(struct hlist_head));
  341. pid_hash = alloc_bootmem(pidhash_size * sizeof(*(pid_hash)));
  342. if (!pid_hash)
  343. panic("Could not alloc pidhash!\n");
  344. for (i = 0; i < pidhash_size; i++)
  345. INIT_HLIST_HEAD(&pid_hash[i]);
  346. }
  347. void __init pidmap_init(void)
  348. {
  349. init_pid_ns.pidmap[0].page = kzalloc(PAGE_SIZE, GFP_KERNEL);
  350. /* Reserve PID 0. We never call free_pidmap(0) */
  351. set_bit(0, init_pid_ns.pidmap[0].page);
  352. atomic_dec(&init_pid_ns.pidmap[0].nr_free);
  353. pid_cachep = kmem_cache_create("pid", sizeof(struct pid),
  354. __alignof__(struct pid),
  355. SLAB_PANIC, NULL, NULL);
  356. }