tracelevel module: Prioritize trace events
[linux-2.6.git] / kernel / pid.c
index e9fd8c1..e432057 100644 (file)
@@ -122,6 +122,43 @@ static void free_pidmap(struct upid *upid)
        atomic_inc(&map->nr_free);
 }
 
+/*
+ * If we started walking pids at 'base', is 'a' seen before 'b'?
+ */
+static int pid_before(int base, int a, int b)
+{
+       /*
+        * This is the same as saying
+        *
+        * (a - base + MAXUINT) % MAXUINT < (b - base + MAXUINT) % MAXUINT
+        * and that mapping orders 'a' and 'b' with respect to 'base'.
+        */
+       return (unsigned)(a - base) < (unsigned)(b - base);
+}
+
+/*
+ * We might be racing with someone else trying to set pid_ns->last_pid.
+ * We want the winner to have the "later" value, because if the
+ * "earlier" value prevails, then a pid may get reused immediately.
+ *
+ * Since pids rollover, it is not sufficient to just pick the bigger
+ * value.  We have to consider where we started counting from.
+ *
+ * 'base' is the value of pid_ns->last_pid that we observed when
+ * we started looking for a pid.
+ *
+ * 'pid' is the pid that we eventually found.
+ */
+static void set_last_pid(struct pid_namespace *pid_ns, int base, int pid)
+{
+       int prev;
+       int last_write = base;
+       do {
+               prev = last_write;
+               last_write = cmpxchg(&pid_ns->last_pid, prev, pid);
+       } while ((prev != last_write) && (pid_before(base, last_write, pid)));
+}
+
 static int alloc_pidmap(struct pid_namespace *pid_ns)
 {
        int i, offset, max_scan, pid, last = pid_ns->last_pid;
@@ -132,7 +169,12 @@ static int alloc_pidmap(struct pid_namespace *pid_ns)
                pid = RESERVED_PIDS;
        offset = pid & BITS_PER_PAGE_MASK;
        map = &pid_ns->pidmap[pid/BITS_PER_PAGE];
-       max_scan = (pid_max + BITS_PER_PAGE - 1)/BITS_PER_PAGE - !offset;
+       /*
+        * If last_pid points into the middle of the map->page we
+        * want to scan this bitmap block twice, the second time
+        * we start with offset == 0 (or RESERVED_PIDS).
+        */
+       max_scan = DIV_ROUND_UP(pid_max, BITS_PER_PAGE) - !offset;
        for (i = 0; i <= max_scan; ++i) {
                if (unlikely(!map->page)) {
                        void *page = kzalloc(PAGE_SIZE, GFP_KERNEL);
@@ -154,20 +196,12 @@ static int alloc_pidmap(struct pid_namespace *pid_ns)
                        do {
                                if (!test_and_set_bit(offset, map->page)) {
                                        atomic_dec(&map->nr_free);
-                                       pid_ns->last_pid = pid;
+                                       set_last_pid(pid_ns, last, pid);
                                        return pid;
                                }
                                offset = find_next_offset(map, offset);
                                pid = mk_pid(pid_ns, map, offset);
-                       /*
-                        * find_next_offset() found a bit, the pid from it
-                        * is in-bounds, and if we fell back to the last
-                        * bitmap block and the final block was the same
-                        * as the starting point, pid is before last_pid.
-                        */
-                       } while (offset < BITS_PER_PAGE && pid < pid_max &&
-                                       (i != max_scan || pid < last ||
-                                           !((last+1) & BITS_PER_PAGE_MASK)));
+                       } while (offset < BITS_PER_PAGE && pid < pid_max);
                }
                if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {
                        ++map;
@@ -183,11 +217,14 @@ static int alloc_pidmap(struct pid_namespace *pid_ns)
        return -1;
 }
 
-int next_pidmap(struct pid_namespace *pid_ns, int last)
+int next_pidmap(struct pid_namespace *pid_ns, unsigned int last)
 {
        int offset;
        struct pidmap *map, *end;
 
+       if (last >= PID_MAX_LIMIT)
+               return -1;
+
        offset = (last + 1) & BITS_PER_PAGE_MASK;
        map = &pid_ns->pidmap[(last + 1)/BITS_PER_PAGE];
        end = &pid_ns->pidmap[PIDMAP_ENTRIES];
@@ -367,8 +404,7 @@ struct task_struct *pid_task(struct pid *pid, enum pid_type type)
        struct task_struct *result = NULL;
        if (pid) {
                struct hlist_node *first;
-               first = rcu_dereference_check(pid->tasks[type].first,
-                                             rcu_read_lock_held() ||
+               first = rcu_dereference_check(hlist_first_rcu(&pid->tasks[type]),
                                              lockdep_tasklist_lock_is_held());
                if (first)
                        result = hlist_entry(first, struct task_struct, pids[(type)].node);
@@ -382,6 +418,7 @@ EXPORT_SYMBOL(pid_task);
  */
 struct task_struct *find_task_by_pid_ns(pid_t nr, struct pid_namespace *ns)
 {
+       rcu_lockdep_assert(rcu_read_lock_held());
        return pid_task(find_pid_ns(nr, ns), PIDTYPE_PID);
 }
 
@@ -400,6 +437,7 @@ struct pid *get_task_pid(struct task_struct *task, enum pid_type type)
        rcu_read_unlock();
        return pid;
 }
+EXPORT_SYMBOL_GPL(get_task_pid);
 
 struct task_struct *get_pid_task(struct pid *pid, enum pid_type type)
 {
@@ -411,6 +449,7 @@ struct task_struct *get_pid_task(struct pid *pid, enum pid_type type)
        rcu_read_unlock();
        return result;
 }
+EXPORT_SYMBOL_GPL(get_pid_task);
 
 struct pid *find_get_pid(pid_t nr)
 {