kernel/pid.c

   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
  23 #include <linux/mm.h>
  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/vs_cvirt.h>
  30
  31 #define pid_hashfn(nr) hash_long((unsigned long)nr, pidhash_shift)
  32 static struct hlist_head *pid_hash[PIDTYPE_MAX];
  33 static int pidhash_shift;
  34
  35 int pid_max = PID_MAX_DEFAULT;
  36 int last_pid;
  37
  38 #define RESERVED_PIDS           300
  39
  40 int pid_max_min = RESERVED_PIDS + 1;
  41 int pid_max_max = PID_MAX_LIMIT;
  42
  43 #define PIDMAP_ENTRIES          ((PID_MAX_LIMIT + 8*PAGE_SIZE - 1)/PAGE_SIZE/8)
  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)
  49
  50 /*
  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.
  55  */
  56 typedef struct pidmap {
  57         atomic_t nr_free;
  58         void *page;
  59 } pidmap_t;
  60
  61 static pidmap_t pidmap_array[PIDMAP_ENTRIES] =
  62          { [ 0 ... PIDMAP_ENTRIES-1 ] = { ATOMIC_INIT(BITS_PER_PAGE), NULL } };
  63
  64 static  __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock);
  65
  66 fastcall void free_pidmap(int pid)
  67 {
  68         pidmap_t *map = pidmap_array + pid / BITS_PER_PAGE;
  69         int offset = pid & BITS_PER_PAGE_MASK;
  70
  71         clear_bit(offset, map->page);
  72         atomic_inc(&map->nr_free);
  73 }
  74
  75 int alloc_pidmap(void)
  76 {
  77         int i, offset, max_scan, pid, last = last_pid;
  78         pidmap_t *map;
  79
  80         pid = last + 1;
  81         if (pid >= pid_max)
  82                 pid = RESERVED_PIDS;
  83         offset = pid & BITS_PER_PAGE_MASK;
  84         map = &pidmap_array[pid/BITS_PER_PAGE];
  85         max_scan = (pid_max + BITS_PER_PAGE - 1)/BITS_PER_PAGE - !offset;
  86         for (i = 0; i <= max_scan; ++i) {
  87                 if (unlikely(!map->page)) {
  88                         unsigned long page = get_zeroed_page(GFP_KERNEL);
  89                         /*
  90                          * Free the page if someone raced with us
  91                          * installing it:
  92                          */
  93                         spin_lock(&pidmap_lock);
  94                         if (map->page)
  95                                 free_page(page);
  96                         else
  97                                 map->page = (void *)page;
  98                         spin_unlock(&pidmap_lock);
  99                         if (unlikely(!map->page))
 100                                 break;
 101                 }
 102                 if (likely(atomic_read(&map->nr_free))) {
 103                         do {
 104                                 if (!test_and_set_bit(offset, map->page)) {
 105                                         atomic_dec(&map->nr_free);
 106                                         last_pid = pid;
 107                                         return pid;
 108                                 }
 109                                 offset = find_next_offset(map, offset);
 110                                 pid = mk_pid(map, offset);
 111                         /*
 112                          * find_next_offset() found a bit, the pid from it
 113                          * is in-bounds, and if we fell back to the last
 114                          * bitmap block and the final block was the same
 115                          * as the starting point, pid is before last_pid.
 116                          */
 117                         } while (offset < BITS_PER_PAGE && pid < pid_max &&
 118                                         (i != max_scan || pid < last ||
 119                                             !((last+1) & BITS_PER_PAGE_MASK)));
 120                 }
 121                 if (map < &pidmap_array[(pid_max-1)/BITS_PER_PAGE]) {
 122                         ++map;
 123                         offset = 0;
 124                 } else {
 125                         map = &pidmap_array[0];
 126                         offset = RESERVED_PIDS;
 127                         if (unlikely(last == offset))
 128                                 break;
 129                 }
 130                 pid = mk_pid(map, offset);
 131         }
 132         return -1;
 133 }
 134
 135 struct pid * fastcall find_pid(enum pid_type type, int nr)
 136 {
 137         struct hlist_node *elem;
 138         struct pid *pid;
 139
 140         hlist_for_each_entry_rcu(pid, elem,
 141                         &pid_hash[type][pid_hashfn(nr)], pid_chain) {
 142                 if (pid->nr == nr)
 143                         return pid;
 144         }
 145         return NULL;
 146 }
 147
 148 int fastcall attach_pid(task_t *task, enum pid_type type, int nr)
 149 {
 150         struct pid *pid, *task_pid;
 151
 152         task_pid = &task->pids[type];
 153         pid = find_pid(type, nr);
 154         task_pid->nr = nr;
 155         if (pid == NULL) {
 156                 INIT_LIST_HEAD(&task_pid->pid_list);
 157                 hlist_add_head_rcu(&task_pid->pid_chain,
 158                                    &pid_hash[type][pid_hashfn(nr)]);
 159         } else {
 160                 INIT_HLIST_NODE(&task_pid->pid_chain);
 161                 list_add_tail_rcu(&task_pid->pid_list, &pid->pid_list);
 162         }
 163
 164         return 0;
 165 }
 166
 167 static fastcall int __detach_pid(task_t *task, enum pid_type type)
 168 {
 169         struct pid *pid, *pid_next;
 170         int nr = 0;
 171
 172         pid = &task->pids[type];
 173         if (!hlist_unhashed(&pid->pid_chain)) {
 174
 175                 if (list_empty(&pid->pid_list)) {
 176                         nr = pid->nr;
 177                         hlist_del_rcu(&pid->pid_chain);
 178                 } else {
 179                         pid_next = list_entry(pid->pid_list.next,
 180                                                 struct pid, pid_list);
 181                         /* insert next pid from pid_list to hash */
 182                         hlist_replace_rcu(&pid->pid_chain,
 183                                           &pid_next->pid_chain);
 184                 }
 185         }
 186
 187         list_del_rcu(&pid->pid_list);
 188         pid->nr = 0;
 189
 190         return nr;
 191 }
 192
 193 void fastcall detach_pid(task_t *task, enum pid_type type)
 194 {
 195         int tmp, nr;
 196
 197         nr = __detach_pid(task, type);
 198         if (!nr)
 199                 return;
 200
 201         for (tmp = PIDTYPE_MAX; --tmp >= 0; )
 202                 if (tmp != type && find_pid(tmp, nr))
 203                         return;
 204
 205         free_pidmap(nr);
 206 }
 207
 208 task_t *find_task_by_pid_type(int type, int nr)
 209 {
 210         struct pid *pid;
 211
 212         if (type == PIDTYPE_REALPID)
 213                 type = PIDTYPE_PID;
 214         else if (type == PIDTYPE_PID)
 215                 nr = vx_rmap_pid(nr);
 216
 217         pid = find_pid(type, nr);
 218         if (!pid)
 219                 return NULL;
 220
 221         return pid_task(&pid->pid_list, type);
 222 }
 223
 224 EXPORT_SYMBOL(find_task_by_pid_type);
 225
 226 /*
 227  * This function switches the PIDs if a non-leader thread calls
 228  * sys_execve() - this must be done without releasing the PID.
 229  * (which a detach_pid() would eventually do.)
 230  */
 231 void switch_exec_pids(task_t *leader, task_t *thread)
 232 {
 233         __detach_pid(leader, PIDTYPE_PID);
 234         __detach_pid(leader, PIDTYPE_TGID);
 235         __detach_pid(leader, PIDTYPE_PGID);
 236         __detach_pid(leader, PIDTYPE_SID);
 237
 238         __detach_pid(thread, PIDTYPE_PID);
 239         __detach_pid(thread, PIDTYPE_TGID);
 240
 241         leader->pid = leader->tgid = thread->pid;
 242         thread->pid = thread->tgid;
 243
 244         attach_pid(thread, PIDTYPE_PID, thread->pid);
 245         attach_pid(thread, PIDTYPE_TGID, thread->tgid);
 246         attach_pid(thread, PIDTYPE_PGID, thread->signal->pgrp);
 247         attach_pid(thread, PIDTYPE_SID, thread->signal->session);
 248         list_add_tail(&thread->tasks, &init_task.tasks);
 249
 250         attach_pid(leader, PIDTYPE_PID, leader->pid);
 251         attach_pid(leader, PIDTYPE_TGID, leader->tgid);
 252         attach_pid(leader, PIDTYPE_PGID, leader->signal->pgrp);
 253         attach_pid(leader, PIDTYPE_SID, leader->signal->session);
 254 }
 255
 256 /*
 257  * The pid hash table is scaled according to the amount of memory in the
 258  * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
 259  * more.
 260  */
 261 void __init pidhash_init(void)
 262 {
 263         int i, j, pidhash_size;
 264         unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);
 265
 266         pidhash_shift = max(4, fls(megabytes * 4));
 267         pidhash_shift = min(12, pidhash_shift);
 268         pidhash_size = 1 << pidhash_shift;
 269
 270         printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",
 271                 pidhash_size, pidhash_shift,
 272                 PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head));
 273
 274         for (i = 0; i < PIDTYPE_MAX; i++) {
 275                 pid_hash[i] = alloc_bootmem(pidhash_size *
 276                                         sizeof(*(pid_hash[i])));
 277                 if (!pid_hash[i])
 278                         panic("Could not alloc pidhash!\n");
 279                 for (j = 0; j < pidhash_size; j++)
 280                         INIT_HLIST_HEAD(&pid_hash[i][j]);
 281         }
 282 }
 283
 284 void __init pidmap_init(void)
 285 {
 286         int i;
 287
 288         pidmap_array->page = (void *)get_zeroed_page(GFP_KERNEL);
 289         set_bit(0, pidmap_array->page);
 290         atomic_dec(&pidmap_array->nr_free);
 291
 292         /*
 293          * Allocate PID 0, and hash it via all PID types:
 294          */
 295
 296         for (i = 0; i < PIDTYPE_MAX; i++)
 297                 attach_pid(current, i, 0);
 298 }