[PATCH v4 0/2] Replacing PID bitmap implementation with IDR API

[PATCH v4 0/2] Replacing PID bitmap implementation with IDR API

[Gargi Sharma]

This patch series replaces kernel bitmap implementation of PID allocation
with IDR API. These patches are written to simplify the kernel by replacing custom code with calls to generic code.

The following are the stats for pid and pid_namespace object files
before and after the replacement. There is a noteworthy change between
the IDR and bitmap implementation.

Before
text       data        bss        dec        hex    filename
   8447       3894         64      12405       3075    kernel/pid.o
After
text       data        bss        dec        hex    filename
   3397        304          0       3701        e75    kernel/pid.o

Before
 text       data        bss        dec        hex    filename
   5692       1842        192       7726       1e2e    kernel/pid_namespace.o
After
text       data        bss        dec        hex    filename
   2854        216         16       3086        c0e    kernel/pid_namespace.o

The following are the stats for ps, pstree and calling readdir on /proc
for 10,000 processes.

ps:
        With IDR API    With bitmap
real    0m1.479s        0m2.319s
user    0m0.070s        0m0.060s
sys     0m0.289s        0m0.516s

pstree:
        With IDR API    With bitmap
real    0m1.024s        0m1.794s
user    0m0.348s        0m0.612s
sys     0m0.184s        0m0.264s

proc:
        With IDR API    With bitmap
real    0m0.059s        0m0.074s
user    0m0.000s        0m0.004s
sys     0m0.016s        0m0.016s

---
Changes in v4:
	- Make comments for alloc_pid clearer.
Changes in v3:
        - Replace idr_next with idr_get_cursor().
        - Correct pid_alloc so that find_pid_ns can't
          find not completely allocated pids.
Changes in v2:
        - Removed redundant  IDR function that was introduced
          in the previous patchset.
        - Renamed PIDNS_HASH_ADDING
        - Used idr_for_each_entry_continue()
        - Used idr_find() to lookup pids

Gargi Sharma (2):
  pid: Replace pid bitmap implementation with IDR API
  pid: Remove pidhash

 arch/powerpc/platforms/cell/spufs/sched.c |   2 +-
 fs/proc/loadavg.c                         |   2 +-
 include/linux/init_task.h                 |   1 -
 include/linux/pid.h                       |   2 -
 include/linux/pid_namespace.h             |  18 +--
 init/main.c                               |   3 +-
 kernel/fork.c                             |   2 +-
 kernel/pid.c                              | 245 ++++++------------------------
 kernel/pid_namespace.c                    |  48 ++----
 9 files changed, 68 insertions(+), 255 deletions(-)

-- 
2.7.4

[PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Gargi Sharma]

This patch replaces the current bitmap implemetation for
Process ID allocation. Functions that are no longer required,
for example, free_pidmap(), alloc_pidmap(), etc. are removed.
The rest of the functions are modified to use the IDR API.
The change was made to make the PID allocation less complex by
replacing custom code with calls to generic API.

Signed-off-by: Gargi Sharma <gs051095@gmail.com>
---
 arch/powerpc/platforms/cell/spufs/sched.c |   2 +-
 fs/proc/loadavg.c                         |   2 +-
 include/linux/pid_namespace.h             |  14 +--
 init/main.c                               |   2 +-
 kernel/pid.c                              | 197 +++++-------------------------
 kernel/pid_namespace.c                    |  42 ++-----
 6 files changed, 52 insertions(+), 207 deletions(-)

diff --git a/arch/powerpc/platforms/cell/spufs/sched.c b/arch/powerpc/platforms/cell/spufs/sched.c
index 1fbb5da..e47761c 100644
--- a/arch/powerpc/platforms/cell/spufs/sched.c
+++ b/arch/powerpc/platforms/cell/spufs/sched.c
@@ -1093,7 +1093,7 @@ static int show_spu_loadavg(struct seq_file *s, void *private)
 		LOAD_INT(c), LOAD_FRAC(c),
 		count_active_contexts(),
 		atomic_read(&nr_spu_contexts),
-		task_active_pid_ns(current)->last_pid);
+		idr_get_cursor(&task_active_pid_ns(current)->idr));
 	return 0;
 }
 
diff --git a/fs/proc/loadavg.c b/fs/proc/loadavg.c
index 983fce5..ba3d0e2 100644
--- a/fs/proc/loadavg.c
+++ b/fs/proc/loadavg.c
@@ -23,7 +23,7 @@ static int loadavg_proc_show(struct seq_file *m, void *v)
 		LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
 		LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
 		nr_running(), nr_threads,
-		task_active_pid_ns(current)->last_pid);
+		idr_get_cursor(&task_active_pid_ns(current)->idr));
 	return 0;
 }
 
diff --git a/include/linux/pid_namespace.h b/include/linux/pid_namespace.h
index b09136f..f4db4a7 100644
--- a/include/linux/pid_namespace.h
+++ b/include/linux/pid_namespace.h
@@ -9,15 +9,8 @@
 #include <linux/nsproxy.h>
 #include <linux/kref.h>
 #include <linux/ns_common.h>
+#include <linux/idr.h>
 
-struct pidmap {
-       atomic_t nr_free;
-       void *page;
-};
-
-#define BITS_PER_PAGE		(PAGE_SIZE * 8)
-#define BITS_PER_PAGE_MASK	(BITS_PER_PAGE-1)
-#define PIDMAP_ENTRIES		((PID_MAX_LIMIT+BITS_PER_PAGE-1)/BITS_PER_PAGE)
 
 struct fs_pin;
 
@@ -29,9 +22,8 @@ enum { /* definitions for pid_namespace's hide_pid field */
 
 struct pid_namespace {
 	struct kref kref;
-	struct pidmap pidmap[PIDMAP_ENTRIES];
+	struct idr idr;
 	struct rcu_head rcu;
-	int last_pid;
 	unsigned int nr_hashed;
 	struct task_struct *child_reaper;
 	struct kmem_cache *pid_cachep;
@@ -105,6 +97,6 @@ static inline int reboot_pid_ns(struct pid_namespace *pid_ns, int cmd)
 
 extern struct pid_namespace *task_active_pid_ns(struct task_struct *tsk);
 void pidhash_init(void);
-void pidmap_init(void);
+void pid_idr_init(void);
 
 #endif /* _LINUX_PID_NS_H */
diff --git a/init/main.c b/init/main.c
index 0ee9c686..9f4db20 100644
--- a/init/main.c
+++ b/init/main.c
@@ -667,7 +667,7 @@ asmlinkage __visible void __init start_kernel(void)
 	if (late_time_init)
 		late_time_init();
 	calibrate_delay();
-	pidmap_init();
+	pid_idr_init();
 	anon_vma_init();
 	acpi_early_init();
 #ifdef CONFIG_X86
diff --git a/kernel/pid.c b/kernel/pid.c
index 020dedb..fb1ee40 100644
--- a/kernel/pid.c
+++ b/kernel/pid.c
@@ -39,6 +39,7 @@
 #include <linux/proc_ns.h>
 #include <linux/proc_fs.h>
 #include <linux/sched/task.h>
+#include <linux/idr.h>
 
 #define pid_hashfn(nr, ns)	\
 	hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
@@ -53,14 +54,6 @@ int pid_max = PID_MAX_DEFAULT;
 int pid_max_min = RESERVED_PIDS + 1;
 int pid_max_max = PID_MAX_LIMIT;
 
-static inline int mk_pid(struct pid_namespace *pid_ns,
-		struct pidmap *map, int off)
-{
-	return (map - pid_ns->pidmap)*BITS_PER_PAGE + off;
-}
-
-#define find_next_offset(map, off)					\
-		find_next_zero_bit((map)->page, BITS_PER_PAGE, off)
 
 /*
  * PID-map pages start out as NULL, they get allocated upon
@@ -70,10 +63,7 @@ static inline int mk_pid(struct pid_namespace *pid_ns,
  */
 struct pid_namespace init_pid_ns = {
 	.kref = KREF_INIT(2),
-	.pidmap = {
-		[ 0 ... PIDMAP_ENTRIES-1] = { ATOMIC_INIT(BITS_PER_PAGE), NULL }
-	},
-	.last_pid = 0,
+	.idr = IDR_INIT,
 	.nr_hashed = PIDNS_HASH_ADDING,
 	.level = 0,
 	.child_reaper = &init_task,
@@ -101,138 +91,6 @@ EXPORT_SYMBOL_GPL(init_pid_ns);
 
 static  __cacheline_aligned_in_smp DEFINE_SPINLOCK(pidmap_lock);
 
-static void free_pidmap(struct upid *upid)
-{
-	int nr = upid->nr;
-	struct pidmap *map = upid->ns->pidmap + nr / BITS_PER_PAGE;
-	int offset = nr & BITS_PER_PAGE_MASK;
-
-	clear_bit(offset, map->page);
-	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
- * at the pid allocation time (there's also a sysctl for this, but racing
- * with this one is OK, see comment in kernel/pid_namespace.c about it).
- * 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;
-	struct pidmap *map;
-
-	pid = last + 1;
-	if (pid >= pid_max)
-		pid = RESERVED_PIDS;
-	offset = pid & BITS_PER_PAGE_MASK;
-	map = &pid_ns->pidmap[pid/BITS_PER_PAGE];
-	/*
-	 * 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);
-			/*
-			 * Free the page if someone raced with us
-			 * installing it:
-			 */
-			spin_lock_irq(&pidmap_lock);
-			if (!map->page) {
-				map->page = page;
-				page = NULL;
-			}
-			spin_unlock_irq(&pidmap_lock);
-			kfree(page);
-			if (unlikely(!map->page))
-				return -ENOMEM;
-		}
-		if (likely(atomic_read(&map->nr_free))) {
-			for ( ; ; ) {
-				if (!test_and_set_bit(offset, map->page)) {
-					atomic_dec(&map->nr_free);
-					set_last_pid(pid_ns, last, pid);
-					return pid;
-				}
-				offset = find_next_offset(map, offset);
-				if (offset >= BITS_PER_PAGE)
-					break;
-				pid = mk_pid(pid_ns, map, offset);
-				if (pid >= pid_max)
-					break;
-			}
-		}
-		if (map < &pid_ns->pidmap[(pid_max-1)/BITS_PER_PAGE]) {
-			++map;
-			offset = 0;
-		} else {
-			map = &pid_ns->pidmap[0];
-			offset = RESERVED_PIDS;
-			if (unlikely(last == offset))
-				break;
-		}
-		pid = mk_pid(pid_ns, map, offset);
-	}
-	return -EAGAIN;
-}
-
-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];
-	for (; map < end; map++, offset = 0) {
-		if (unlikely(!map->page))
-			continue;
-		offset = find_next_bit((map)->page, BITS_PER_PAGE, offset);
-		if (offset < BITS_PER_PAGE)
-			return mk_pid(pid_ns, map, offset);
-	}
-	return -1;
-}
-
 void put_pid(struct pid *pid)
 {
 	struct pid_namespace *ns;
@@ -284,12 +142,11 @@ void free_pid(struct pid *pid)
 			schedule_work(&ns->proc_work);
 			break;
 		}
+
+		idr_remove(&ns->idr, upid->nr);
 	}
 	spin_unlock_irqrestore(&pidmap_lock, flags);
 
-	for (i = 0; i <= pid->level; i++)
-		free_pidmap(pid->numbers + i);
-
 	call_rcu(&pid->rcu, delayed_put_pid);
 }
 
@@ -308,8 +165,27 @@ struct pid *alloc_pid(struct pid_namespace *ns)
 
 	tmp = ns;
 	pid->level = ns->level;
+
 	for (i = ns->level; i >= 0; i--) {
-		nr = alloc_pidmap(tmp);
+		int pid_min = 1;
+		idr_preload(GFP_KERNEL);
+		spin_lock_irq(&pidmap_lock);
+
+		/*
+		 * init really needs pid 1, but after reaching the maximum
+		 * wrap back to RESERVED_PIDS
+		 */
+		if (idr_get_cursor(&tmp->idr) > RESERVED_PIDS)
+			pid_min = RESERVED_PIDS;
+
+		/* Store a null pointer so find_pid_ns does not find             *
+		 * a partially initialized PID (see below).
+		 */
+		nr = idr_alloc_cyclic(&tmp->idr, NULL, pid_min,
+				      pid_max, GFP_ATOMIC);
+		spin_unlock_irq(&pidmap_lock);
+		idr_preload_end();
+
 		if (nr < 0) {
 			retval = nr;
 			goto out_free;
@@ -339,6 +215,8 @@ struct pid *alloc_pid(struct pid_namespace *ns)
 	for ( ; upid >= pid->numbers; --upid) {
 		hlist_add_head_rcu(&upid->pid_chain,
 				&pid_hash[pid_hashfn(upid->nr, upid->ns)]);
+		/* Make the PID visible to find_pid_ns. */
+		idr_replace(&upid->ns->idr, pid, upid->nr);
 		upid->ns->nr_hashed++;
 	}
 	spin_unlock_irq(&pidmap_lock);
@@ -350,8 +228,11 @@ struct pid *alloc_pid(struct pid_namespace *ns)
 	put_pid_ns(ns);
 
 out_free:
+	spin_lock_irq(&pidmap_lock);
 	while (++i <= ns->level)
-		free_pidmap(pid->numbers + i);
+		idr_remove(&ns->idr, (pid->numbers + i)->nr);
+
+	spin_unlock_irq(&pidmap_lock);
 
 	kmem_cache_free(ns->pid_cachep, pid);
 	return ERR_PTR(retval);
@@ -553,16 +434,7 @@ EXPORT_SYMBOL_GPL(task_active_pid_ns);
  */
 struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
 {
-	struct pid *pid;
-
-	do {
-		pid = find_pid_ns(nr, ns);
-		if (pid)
-			break;
-		nr = next_pidmap(ns, nr);
-	} while (nr > 0);
-
-	return pid;
+	return idr_get_next(&ns->idr, &nr);
 }
 
 /*
@@ -578,7 +450,7 @@ void __init pidhash_init(void)
 					   0, 4096);
 }
 
-void __init pidmap_init(void)
+void __init pid_idr_init(void)
 {
 	/* Verify no one has done anything silly: */
 	BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_HASH_ADDING);
@@ -590,10 +462,7 @@ void __init pidmap_init(void)
 				PIDS_PER_CPU_MIN * num_possible_cpus());
 	pr_info("pid_max: default: %u minimum: %u\n", pid_max, pid_max_min);
 
-	init_pid_ns.pidmap[0].page = kzalloc(PAGE_SIZE, GFP_KERNEL);
-	/* Reserve PID 0. We never call free_pidmap(0) */
-	set_bit(0, init_pid_ns.pidmap[0].page);
-	atomic_dec(&init_pid_ns.pidmap[0].nr_free);
+	idr_init(&init_pid_ns.idr);
 
 	init_pid_ns.pid_cachep = KMEM_CACHE(pid,
 			SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT);
diff --git a/kernel/pid_namespace.c b/kernel/pid_namespace.c
index 4918314..596f90a 100644
--- a/kernel/pid_namespace.c
+++ b/kernel/pid_namespace.c
@@ -21,6 +21,7 @@
 #include <linux/export.h>
 #include <linux/sched/task.h>
 #include <linux/sched/signal.h>
+#include <linux/idr.h>
 
 struct pid_cache {
 	int nr_ids;
@@ -98,7 +99,6 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_ns
 	struct pid_namespace *ns;
 	unsigned int level = parent_pid_ns->level + 1;
 	struct ucounts *ucounts;
-	int i;
 	int err;
 
 	err = -EINVAL;
@@ -117,17 +117,15 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_ns
 	if (ns == NULL)
 		goto out_dec;
 
-	ns->pidmap[0].page = kzalloc(PAGE_SIZE, GFP_KERNEL);
-	if (!ns->pidmap[0].page)
-		goto out_free;
+	idr_init(&ns->idr);
 
 	ns->pid_cachep = create_pid_cachep(level + 1);
 	if (ns->pid_cachep == NULL)
-		goto out_free_map;
+		goto out_free_idr;
 
 	err = ns_alloc_inum(&ns->ns);
 	if (err)
-		goto out_free_map;
+		goto out_free_idr;
 	ns->ns.ops = &pidns_operations;
 
 	kref_init(&ns->kref);
@@ -138,17 +136,10 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_ns
 	ns->nr_hashed = PIDNS_HASH_ADDING;
 	INIT_WORK(&ns->proc_work, proc_cleanup_work);
 
-	set_bit(0, ns->pidmap[0].page);
-	atomic_set(&ns->pidmap[0].nr_free, BITS_PER_PAGE - 1);
-
-	for (i = 1; i < PIDMAP_ENTRIES; i++)
-		atomic_set(&ns->pidmap[i].nr_free, BITS_PER_PAGE);
-
 	return ns;
 
-out_free_map:
-	kfree(ns->pidmap[0].page);
-out_free:
+out_free_idr:
+	idr_destroy(&ns->idr);
 	kmem_cache_free(pid_ns_cachep, ns);
 out_dec:
 	dec_pid_namespaces(ucounts);
@@ -168,11 +159,9 @@ static void delayed_free_pidns(struct rcu_head *p)
 
 static void destroy_pid_namespace(struct pid_namespace *ns)
 {
-	int i;
-
 	ns_free_inum(&ns->ns);
-	for (i = 0; i < PIDMAP_ENTRIES; i++)
-		kfree(ns->pidmap[i].page);
+
+	idr_destroy(&ns->idr);
 	call_rcu(&ns->rcu, delayed_free_pidns);
 }
 
@@ -213,6 +202,7 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 	int rc;
 	struct task_struct *task, *me = current;
 	int init_pids = thread_group_leader(me) ? 1 : 2;
+	struct pid *pid;
 
 	/* Don't allow any more processes into the pid namespace */
 	disable_pid_allocation(pid_ns);
@@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 	 *
 	 */
 	read_lock(&tasklist_lock);
-	nr = next_pidmap(pid_ns, 1);
-	while (nr > 0) {
-		rcu_read_lock();
-
-		task = pid_task(find_vpid(nr), PIDTYPE_PID);
+	nr = 2;
+	idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
+		task = pid_task(pid, PIDTYPE_PID);
 		if (task && !__fatal_signal_pending(task))
 			send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
-
-		rcu_read_unlock();
-
-		nr = next_pidmap(pid_ns, nr);
 	}
 	read_unlock(&tasklist_lock);
 
@@ -311,7 +295,7 @@ static int pid_ns_ctl_handler(struct ctl_table *table, int write,
 	 * it should synchronize its usage with external means.
 	 */
 
-	tmp.data = &pid_ns->last_pid;
+	tmp.data = &pid_ns->idr.idr_next;
 	return proc_dointvec_minmax(&tmp, write, buffer, lenp, ppos);
 }
 
-- 
2.7.4

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Andrew Morton]

On Mon,  9 Oct 2017 17:13:43 -0400 Gargi Sharma <gs051095@gmail.com> wrote:

> This patch replaces the current bitmap implemetation for
> Process ID allocation. Functions that are no longer required,
> for example, free_pidmap(), alloc_pidmap(), etc. are removed.
> The rest of the functions are modified to use the IDR API.
> The change was made to make the PID allocation less complex by
> replacing custom code with calls to generic API.
> 

I can't say I really understand the locking here.

>
> ...
>
> @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
>  	 *
>  	 */
>  	read_lock(&tasklist_lock);
> -	nr = next_pidmap(pid_ns, 1);
> -	while (nr > 0) {
> -		rcu_read_lock();
> -
> -		task = pid_task(find_vpid(nr), PIDTYPE_PID);
> +	nr = 2;
> +	idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
> +		task = pid_task(pid, PIDTYPE_PID);
>  		if (task && !__fatal_signal_pending(task))
>  			send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
> -
> -		rcu_read_unlock();
> -
> -		nr = next_pidmap(pid_ns, nr);
>  	}
>  	read_unlock(&tasklist_lock);

Especially here.  I don't think pidmap_lock is held.  Is that IDR
iteration safe?

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Oleg Nesterov]

On 10/09, Andrew Morton wrote:
>
> > @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
> >  	 *
> >  	 */
> >  	read_lock(&tasklist_lock);
> > -	nr = next_pidmap(pid_ns, 1);
> > -	while (nr > 0) {
> > -		rcu_read_lock();
> > -
> > -		task = pid_task(find_vpid(nr), PIDTYPE_PID);
> > +	nr = 2;
> > +	idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
> > +		task = pid_task(pid, PIDTYPE_PID);
> >  		if (task && !__fatal_signal_pending(task))
> >  			send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
> > -
> > -		rcu_read_unlock();
> > -
> > -		nr = next_pidmap(pid_ns, nr);
> >  	}
> >  	read_unlock(&tasklist_lock);
> 
> Especially here.  I don't think pidmap_lock is held.  Is that IDR
> iteration safe?

Yes, this doesn't look right, we need rcu_read_lock() or pidmap_lock.

And, we also need rcu_read_lock() for another reason, to protect "struct pid".

Gargi, I suggested to use idr_for_each_entry_continue(), but now I am wondering
if we should use idr_for_each() instead. IIUC this would be a bit faster? Not
that I think this is really important...

Oleg.

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Gargi Sharma]

On Tue, Oct 10, 2017 at 12:50 PM, Oleg Nesterov <oleg@redhat.com> wrote:
> On 10/09, Andrew Morton wrote:
>>
>> > @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
>> >      *
>> >      */
>> >     read_lock(&tasklist_lock);
>> > -   nr = next_pidmap(pid_ns, 1);
>> > -   while (nr > 0) {
>> > -           rcu_read_lock();
>> > -
>> > -           task = pid_task(find_vpid(nr), PIDTYPE_PID);
>> > +   nr = 2;
>> > +   idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
>> > +           task = pid_task(pid, PIDTYPE_PID);
>> >             if (task && !__fatal_signal_pending(task))
>> >                     send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
>> > -
>> > -           rcu_read_unlock();
>> > -
>> > -           nr = next_pidmap(pid_ns, nr);
>> >     }
>> >     read_unlock(&tasklist_lock);
>>
>> Especially here.  I don't think pidmap_lock is held.  Is that IDR
>> iteration safe?
>
> Yes, this doesn't look right, we need rcu_read_lock() or pidmap_lock.
>
> And, we also need rcu_read_lock() for another reason, to protect "struct pid".

Ah, I missed this. From what I understood idr_for_each_entry_continue
should be safe because calls idr_get_next which in turn calls
radix_tree_iter_find to find the next populated entry in the idr. If
the pid that you are looking up the task for is deleted, task will get
a NULL from pid_task and no signal to kill will be sent.
>
> Gargi, I suggested to use idr_for_each_entry_continue(), but now I am wondering
> if we should use idr_for_each() instead. IIUC this would be a bit faster? Not
> that I think this is really important...

I can run benchmarks with idr_for_each to see how much speed up is
achieved and then we can go with whatever we think is better. How does
that sounds?

Thanks!
Gargi
>
> Oleg.
>

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Oleg Nesterov]

On 10/10, Gargi Sharma wrote:
>
> On Tue, Oct 10, 2017 at 12:50 PM, Oleg Nesterov <oleg@redhat.com> wrote:
> > On 10/09, Andrew Morton wrote:
> >>
> >> Especially here.  I don't think pidmap_lock is held.  Is that IDR
> >> iteration safe?
> >
> > Yes, this doesn't look right, we need rcu_read_lock() or pidmap_lock.
> >
> > And, we also need rcu_read_lock() for another reason, to protect "struct pid".
>
> Ah, I missed this. From what I understood idr_for_each_entry_continue
> should be safe

Without rcu? Why?

> because calls idr_get_next which in turn calls
> radix_tree_iter_find to find the next populated entry in the idr.

and then it does rcu_dereference_raw(*slot). Without rcu or pidmap this
slot can got away if we race with free_pid().

> If
> the pid that you are looking up the task for is deleted, task will get
> a NULL from pid_task and no signal to kill will be sent.

pid->tasks is protected by tasklist_lock, but the pid itself can go away
without rcu lock.

So I think you need to take rcu_read_lock() right after tasklist_lock.

> > Gargi, I suggested to use idr_for_each_entry_continue(), but now I am wondering
> > if we should use idr_for_each() instead. IIUC this would be a bit faster? Not
> > that I think this is really important...
>
> I can run benchmarks with idr_for_each to see how much speed up is
> achieved and then we can go with whatever we think is better. How does
> that sounds?

Up to you ;) I am fine either way.

Oleg.

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 2673 bytes --]

On Tue, 2017-10-10 at 13:35 +0100, Gargi Sharma wrote:
> On Tue, Oct 10, 2017 at 12:50 PM, Oleg Nesterov <oleg@redhat.com>
> wrote:
> > On 10/09, Andrew Morton wrote:
> > > 
> > > > @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct
> > > > pid_namespace *pid_ns)
> > > >      *
> > > >      */
> > > >     read_lock(&tasklist_lock);
> > > > -   nr = next_pidmap(pid_ns, 1);
> > > > -   while (nr > 0) {
> > > > -           rcu_read_lock();
> > > > -
> > > > -           task = pid_task(find_vpid(nr), PIDTYPE_PID);
> > > > +   nr = 2;
> > > > +   idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
> > > > +           task = pid_task(pid, PIDTYPE_PID);
> > > >             if (task && !__fatal_signal_pending(task))
> > > >                     send_sig_info(SIGKILL, SEND_SIG_FORCED,
> > > > task);
> > > > -
> > > > -           rcu_read_unlock();
> > > > -
> > > > -           nr = next_pidmap(pid_ns, nr);
> > > >     }
> > > >     read_unlock(&tasklist_lock);
> > > 
> > > Especially here.  I don't think pidmap_lock is held.  Is that IDR
> > > iteration safe?
> > 
> > Yes, this doesn't look right, we need rcu_read_lock() or
> > pidmap_lock.
> > 
> > And, we also need rcu_read_lock() for another reason, to protect
> > "struct pid".
> 
> Ah, I missed this. From what I understood idr_for_each_entry_continue
> should be safe because calls idr_get_next which in turn calls
> radix_tree_iter_find to find the next populated entry in the idr. If
> the pid that you are looking up the task for is deleted, task will
> get
> a NULL from pid_task and no signal to kill will be sent.
> > 
> > Gargi, I suggested to use idr_for_each_entry_continue(), but now I
> > am wondering
> > if we should use idr_for_each() instead. IIUC this would be a bit
> > faster? Not
> > that I think this is really important...
> 
> I can run benchmarks with idr_for_each to see how much speed up is
> achieved and then we can go with whatever we think is better. How
> does
> that sounds?

I suspect this code will not be a hot path in any
conceivable "kill off hundreds of containers"
benchmark, since the overhead of having all of the
tasks in those containers exit will dwarf any
changes in this code.

Simply making it safe for fully preemptible
kernels by adding rcu_read_lock() around the
section is what matters the most.

The choice between idr_for_each_entry_continue()
and idr_for_each() is dictated more by which
of the two results in easier to read code.

-- 
All rights reversed

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Gargi Sharma]

On Tue, Oct 10, 2017 at 4:46 PM, Rik van Riel <riel@surriel.com> wrote:
> On Tue, 2017-10-10 at 13:35 +0100, Gargi Sharma wrote:
>> On Tue, Oct 10, 2017 at 12:50 PM, Oleg Nesterov <oleg@redhat.com>
>> wrote:
>> > On 10/09, Andrew Morton wrote:
>> > >
>> > > > @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct
>> > > > pid_namespace *pid_ns)
>> > > >      *
>> > > >      */
>> > > >     read_lock(&tasklist_lock);
>> > > > -   nr = next_pidmap(pid_ns, 1);
>> > > > -   while (nr > 0) {
>> > > > -           rcu_read_lock();
>> > > > -
>> > > > -           task = pid_task(find_vpid(nr), PIDTYPE_PID);
>> > > > +   nr = 2;
>> > > > +   idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
>> > > > +           task = pid_task(pid, PIDTYPE_PID);
>> > > >             if (task && !__fatal_signal_pending(task))
>> > > >                     send_sig_info(SIGKILL, SEND_SIG_FORCED,
>> > > > task);
>> > > > -
>> > > > -           rcu_read_unlock();
>> > > > -
>> > > > -           nr = next_pidmap(pid_ns, nr);
>> > > >     }
>> > > >     read_unlock(&tasklist_lock);
>> > >
>> > > Especially here.  I don't think pidmap_lock is held.  Is that IDR
>> > > iteration safe?
>> >
>> > Yes, this doesn't look right, we need rcu_read_lock() or
>> > pidmap_lock.
>> >
>> > And, we also need rcu_read_lock() for another reason, to protect
>> > "struct pid".
>>
>> Ah, I missed this. From what I understood idr_for_each_entry_continue
>> should be safe because calls idr_get_next which in turn calls
>> radix_tree_iter_find to find the next populated entry in the idr. If
>> the pid that you are looking up the task for is deleted, task will
>> get
>> a NULL from pid_task and no signal to kill will be sent.
>> >
>> > Gargi, I suggested to use idr_for_each_entry_continue(), but now I
>> > am wondering
>> > if we should use idr_for_each() instead. IIUC this would be a bit
>> > faster? Not
>> > that I think this is really important...
>>
>> I can run benchmarks with idr_for_each to see how much speed up is
>> achieved and then we can go with whatever we think is better. How
>> does
>> that sounds?
>
> I suspect this code will not be a hot path in any
> conceivable "kill off hundreds of containers"
> benchmark, since the overhead of having all of the
> tasks in those containers exit will dwarf any
> changes in this code.
>
> Simply making it safe for fully preemptible
> kernels by adding rcu_read_lock() around the
> section is what matters the most.
>
> The choice between idr_for_each_entry_continue()
> and idr_for_each() is dictated more by which
> of the two results in easier to read code.

I have listed down the code for both idr_for_each and idr_for_each_entry.
IMHO idr_for_each_entry is easier to read, but YMMV. :)

void kill_task(int id, void *ptr, void *data)
{
    struct *pid = ptr;
    struct task_struct *task = pid_task(pid, PIDTYPE_PID);
    if (task && !__fatal_signal_pending(task))
         send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
}

rcu_read_unlock();
idr_for_each(&pid_ns->idr, &kill_task, NULL);
rcu_read_unlock();


VS

idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
          task = pid_task(pid, PIDTYPE_PID);
          if (task && !__fatal_signal_pending(task))
              send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
}

Thanks!
Gargi
>
> --
> All rights reversed

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 1138 bytes --]

On Tue, 2017-10-10 at 17:11 +0100, Gargi Sharma wrote:
> 
> I have listed down the code for both idr_for_each and
> idr_for_each_entry.
> IMHO idr_for_each_entry is easier to read, but YMMV. :)
> 
> void kill_task(int id, void *ptr, void *data)
> {
>     struct *pid = ptr;
>     struct task_struct *task = pid_task(pid, PIDTYPE_PID);
>     if (task && !__fatal_signal_pending(task))
>          send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
> }
> 
> rcu_read_unlock();
> idr_for_each(&pid_ns->idr, &kill_task, NULL);
> rcu_read_unlock();

It also looks like idr_for_each has no easy
way to skip over PID 1, like you can do with
idr_for_each_entry_continue().

I agree with you, the code below is easier to
read than the code above.

> idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
>           task = pid_task(pid, PIDTYPE_PID);
>           if (task && !__fatal_signal_pending(task))
>               send_sig_info(SIGKILL, SEND_SIG_FORCED, task);
> }
> 
> Thanks!
> Gargi
> > 
> > --
> > All rights reversed
> 
> 
-- 
All rights reversed

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [PATCH v4 1/2] pid: Replace pid bitmap implementation with IDR API

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 1333 bytes --]

On Tue, 2017-10-10 at 13:50 +0200, Oleg Nesterov wrote:
> On 10/09, Andrew Morton wrote:
> > 
> > > @@ -240,17 +230,11 @@ void zap_pid_ns_processes(struct
> > > pid_namespace *pid_ns)
> > >  	 *
> > >  	 */
> > >  	read_lock(&tasklist_lock);
> > > -	nr = next_pidmap(pid_ns, 1);
> > > -	while (nr > 0) {
> > > -		rcu_read_lock();
> > > -
> > > -		task = pid_task(find_vpid(nr), PIDTYPE_PID);
> > > +	nr = 2;
> > > +	idr_for_each_entry_continue(&pid_ns->idr, pid, nr) {
> > > +		task = pid_task(pid, PIDTYPE_PID);
> > >  		if (task && !__fatal_signal_pending(task))
> > >  			send_sig_info(SIGKILL, SEND_SIG_FORCED,
> > > task);
> > > -
> > > -		rcu_read_unlock();
> > > -
> > > -		nr = next_pidmap(pid_ns, nr);
> > >  	}
> > >  	read_unlock(&tasklist_lock);
> > 
> > Especially here.  I don't think pidmap_lock is held.  Is that IDR
> > iteration safe?
> 
> Yes, this doesn't look right, we need rcu_read_lock() or pidmap_lock.
> 
> And, we also need rcu_read_lock() for another reason, to protect
> "struct pid".

I think rcu_read_lock alone should do the trick, for both.

The IDR code specifically says that lookups are safe under just
the rcu_read_lock, and that only insertions and deletions need
a separate lock for synchronization.

Good catch.

-- 
All Rights Reversed.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

[PATCH v4 2/2] pid: Remove pidhash

[Gargi Sharma]

pidhash is no longer required as all the information
can be looked up from idr tree. nr_hashed represented
the number of pids that had been hashed. Since, nr_hashed and
PIDNS_HASH_ADDING are no longer relevant, it has been renamed
to pid_allocated and PIDNS_ADDING respectively.

Signed-off-by: Gargi Sharma <gs051095@gmail.com>
---
 include/linux/init_task.h     |  1 -
 include/linux/pid.h           |  2 --
 include/linux/pid_namespace.h |  4 ++--
 init/main.c                   |  1 -
 kernel/fork.c                 |  2 +-
 kernel/pid.c                  | 48 +++++++++----------------------------------
 kernel/pid_namespace.c        |  6 +++---
 7 files changed, 16 insertions(+), 48 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index 3c07ace..cc45798 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -104,7 +104,6 @@ extern struct group_info init_groups;
 	.numbers	= { {						\
 		.nr		= 0,					\
 		.ns		= &init_pid_ns,				\
-		.pid_chain	= { .next = NULL, .pprev = NULL },	\
 	}, }								\
 }
 
diff --git a/include/linux/pid.h b/include/linux/pid.h
index 7195827..3915664 100644
--- a/include/linux/pid.h
+++ b/include/linux/pid.h
@@ -50,10 +50,8 @@ enum pid_type
  */
 
 struct upid {
-	/* Try to keep pid_chain in the same cacheline as nr for find_vpid */
 	int nr;
 	struct pid_namespace *ns;
-	struct hlist_node pid_chain;
 };
 
 struct pid
diff --git a/include/linux/pid_namespace.h b/include/linux/pid_namespace.h
index f4db4a7..7911b58 100644
--- a/include/linux/pid_namespace.h
+++ b/include/linux/pid_namespace.h
@@ -24,7 +24,7 @@ struct pid_namespace {
 	struct kref kref;
 	struct idr idr;
 	struct rcu_head rcu;
-	unsigned int nr_hashed;
+	unsigned int pid_allocated;
 	struct task_struct *child_reaper;
 	struct kmem_cache *pid_cachep;
 	unsigned int level;
@@ -48,7 +48,7 @@ struct pid_namespace {
 
 extern struct pid_namespace init_pid_ns;
 
-#define PIDNS_HASH_ADDING (1U << 31)
+#define PIDNS_ADDING (1U << 31)
 
 #ifdef CONFIG_PID_NS
 static inline struct pid_namespace *get_pid_ns(struct pid_namespace *ns)
diff --git a/init/main.c b/init/main.c
index 9f4db20..c17a21b 100644
--- a/init/main.c
+++ b/init/main.c
@@ -562,7 +562,6 @@ asmlinkage __visible void __init start_kernel(void)
 	 * kmem_cache_init()
 	 */
 	setup_log_buf(0);
-	pidhash_init();
 	vfs_caches_init_early();
 	sort_main_extable();
 	trap_init();
diff --git a/kernel/fork.c b/kernel/fork.c
index 1064618..c3518b8 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1853,7 +1853,7 @@ static __latent_entropy struct task_struct *copy_process(
 		retval = -ERESTARTNOINTR;
 		goto bad_fork_cancel_cgroup;
 	}
-	if (unlikely(!(ns_of_pid(pid)->nr_hashed & PIDNS_HASH_ADDING))) {
+	if (unlikely(!(ns_of_pid(pid)->pid_allocated & PIDNS_ADDING))) {
 		retval = -ENOMEM;
 		goto bad_fork_cancel_cgroup;
 	}
diff --git a/kernel/pid.c b/kernel/pid.c
index fb1ee40..5cb1fd5 100644
--- a/kernel/pid.c
+++ b/kernel/pid.c
@@ -41,10 +41,6 @@
 #include <linux/sched/task.h>
 #include <linux/idr.h>
 
-#define pid_hashfn(nr, ns)	\
-	hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
-static struct hlist_head *pid_hash;
-static unsigned int pidhash_shift = 4;
 struct pid init_struct_pid = INIT_STRUCT_PID;
 
 int pid_max = PID_MAX_DEFAULT;
@@ -54,7 +50,6 @@ int pid_max = PID_MAX_DEFAULT;
 int pid_max_min = RESERVED_PIDS + 1;
 int pid_max_max = PID_MAX_LIMIT;
 
-
 /*
  * PID-map pages start out as NULL, they get allocated upon
  * first use and are never deallocated. This way a low pid_max
@@ -64,7 +59,7 @@ int pid_max_max = PID_MAX_LIMIT;
 struct pid_namespace init_pid_ns = {
 	.kref = KREF_INIT(2),
 	.idr = IDR_INIT,
-	.nr_hashed = PIDNS_HASH_ADDING,
+	.pid_allocated = PIDNS_ADDING,
 	.level = 0,
 	.child_reaper = &init_task,
 	.user_ns = &init_user_ns,
@@ -123,8 +118,7 @@ void free_pid(struct pid *pid)
 	for (i = 0; i <= pid->level; i++) {
 		struct upid *upid = pid->numbers + i;
 		struct pid_namespace *ns = upid->ns;
-		hlist_del_rcu(&upid->pid_chain);
-		switch(--ns->nr_hashed) {
+		switch(--ns->pid_allocated) {
 		case 2:
 		case 1:
 			/* When all that is left in the pid namespace
@@ -133,10 +127,10 @@ void free_pid(struct pid *pid)
 			 */
 			wake_up_process(ns->child_reaper);
 			break;
-		case PIDNS_HASH_ADDING:
+		case PIDNS_ADDING:
 			/* Handle a fork failure of the first process */
 			WARN_ON(ns->child_reaper);
-			ns->nr_hashed = 0;
+			ns->pid_allocated = 0;
 			/* fall through */
 		case 0:
 			schedule_work(&ns->proc_work);
@@ -210,14 +204,12 @@ struct pid *alloc_pid(struct pid_namespace *ns)
 
 	upid = pid->numbers + ns->level;
 	spin_lock_irq(&pidmap_lock);
-	if (!(ns->nr_hashed & PIDNS_HASH_ADDING))
+	if (!(ns->pid_allocated & PIDNS_ADDING))
 		goto out_unlock;
 	for ( ; upid >= pid->numbers; --upid) {
-		hlist_add_head_rcu(&upid->pid_chain,
-				&pid_hash[pid_hashfn(upid->nr, upid->ns)]);
 		/* Make the PID visible to find_pid_ns. */
 		idr_replace(&upid->ns->idr, pid, upid->nr);
-		upid->ns->nr_hashed++;
+		upid->ns->pid_allocated++;
 	}
 	spin_unlock_irq(&pidmap_lock);
 
@@ -241,21 +233,13 @@ struct pid *alloc_pid(struct pid_namespace *ns)
 void disable_pid_allocation(struct pid_namespace *ns)
 {
 	spin_lock_irq(&pidmap_lock);
-	ns->nr_hashed &= ~PIDNS_HASH_ADDING;
+	ns->pid_allocated &= ~PIDNS_ADDING;
 	spin_unlock_irq(&pidmap_lock);
 }
 
 struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
 {
-	struct upid *pnr;
-
-	hlist_for_each_entry_rcu(pnr,
-			&pid_hash[pid_hashfn(nr, ns)], pid_chain)
-		if (pnr->nr == nr && pnr->ns == ns)
-			return container_of(pnr, struct pid,
-					numbers[ns->level]);
-
-	return NULL;
+	return idr_find(&ns->idr, nr);
 }
 EXPORT_SYMBOL_GPL(find_pid_ns);
 
@@ -411,6 +395,7 @@ pid_t __task_pid_nr_ns(struct task_struct *task, enum pid_type type,
 		if (type != PIDTYPE_PID) {
 			if (type == __PIDTYPE_TGID)
 				type = PIDTYPE_PID;
+
 			task = task->group_leader;
 		}
 		nr = pid_nr_ns(rcu_dereference(task->pids[type].pid), ns);
@@ -437,23 +422,10 @@ struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
 	return idr_get_next(&ns->idr, &nr);
 }
 
-/*
- * The pid hash table is scaled according to the amount of memory in the
- * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
- * more.
- */
-void __init pidhash_init(void)
-{
-	pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
-					   HASH_EARLY | HASH_SMALL | HASH_ZERO,
-					   &pidhash_shift, NULL,
-					   0, 4096);
-}
-
 void __init pid_idr_init(void)
 {
 	/* Verify no one has done anything silly: */
-	BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_HASH_ADDING);
+	BUILD_BUG_ON(PID_MAX_LIMIT >= PIDNS_ADDING);
 
 	/* bump default and minimum pid_max based on number of cpus */
 	pid_max = min(pid_max_max, max_t(int, pid_max,
diff --git a/kernel/pid_namespace.c b/kernel/pid_namespace.c
index 596f90a..14844e8 100644
--- a/kernel/pid_namespace.c
+++ b/kernel/pid_namespace.c
@@ -133,7 +133,7 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_ns
 	ns->parent = get_pid_ns(parent_pid_ns);
 	ns->user_ns = get_user_ns(user_ns);
 	ns->ucounts = ucounts;
-	ns->nr_hashed = PIDNS_HASH_ADDING;
+	ns->pid_allocated = PIDNS_ADDING;
 	INIT_WORK(&ns->proc_work, proc_cleanup_work);
 
 	return ns;
@@ -252,7 +252,7 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 	 * sys_wait4() above can't reap the EXIT_DEAD children but we do not
 	 * really care, we could reparent them to the global init. We could
 	 * exit and reap ->child_reaper even if it is not the last thread in
-	 * this pid_ns, free_pid(nr_hashed == 0) calls proc_cleanup_work(),
+	 * this pid_ns, free_pid(pid_allocated == 0) calls proc_cleanup_work(),
 	 * pid_ns can not go away until proc_kill_sb() drops the reference.
 	 *
 	 * But this ns can also have other tasks injected by setns()+fork().
@@ -266,7 +266,7 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 	 */
 	for (;;) {
 		set_current_state(TASK_INTERRUPTIBLE);
-		if (pid_ns->nr_hashed == init_pids)
+		if (pid_ns->pid_allocated == init_pids)
 			break;
 		schedule();
 	}
-- 
2.7.4

Re: [PATCH v4 2/2] pid: Remove pidhash

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 6124 bytes --]

Hi Gargi,

[auto build test ERROR on linus/master]
[also build test ERROR on v4.14-rc4]
[cannot apply to next-20171009]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Gargi-Sharma/pid-Replace-pid-bitmap-implementation-with-IDR-API/20171011-165615
config: ia64-allyesconfig (attached as .config)
compiler: ia64-linux-gcc (GCC) 6.2.0
reproduce:
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=ia64 

All error/warnings (new ones prefixed by >>):

   warning: (INTEL_SOC_PMIC && INTEL_SOC_PMIC_CHTWC && MFD_TPS68470) selects I2C_DESIGNWARE_PLATFORM which has unmet direct dependencies (I2C && HAS_IOMEM && (ACPI && COMMON_CLK || !ACPI))
   warning: (DW_APB_TIMER_OF && ROCKCHIP_TIMER && ARMADA_370_XP_TIMER && ORION_TIMER && CLKSRC_TI_32K && CLKSRC_NPS && CLKSRC_MPS2 && ARM_ARCH_TIMER && ARM_GLOBAL_TIMER && ARM_TIMER_SP804 && ARMV7M_SYSTICK && ATMEL_PIT && CLKSRC_QCOM && CLKSRC_VERSATILE && CLKSRC_MIPS_GIC && CLKSRC_TANGO_XTAL && CLKSRC_ST_LPC) selects TIMER_OF which has unmet direct dependencies (!ARCH_USES_GETTIMEOFFSET && GENERIC_CLOCKEVENTS)
   warning: (FAULT_INJECTION_STACKTRACE_FILTER && LATENCYTOP && KMEMCHECK && LOCKDEP) selects FRAME_POINTER which has unmet direct dependencies (DEBUG_KERNEL && (CRIS || M68K || FRV || UML || SUPERH || BLACKFIN || MN10300 || METAG) || ARCH_WANT_FRAME_POINTERS)
   warning: (INTEL_SOC_PMIC && INTEL_SOC_PMIC_CHTWC && MFD_TPS68470) selects I2C_DESIGNWARE_PLATFORM which has unmet direct dependencies (I2C && HAS_IOMEM && (ACPI && COMMON_CLK || !ACPI))
   warning: (DW_APB_TIMER_OF && ROCKCHIP_TIMER && ARMADA_370_XP_TIMER && ORION_TIMER && CLKSRC_TI_32K && CLKSRC_NPS && CLKSRC_MPS2 && ARM_ARCH_TIMER && ARM_GLOBAL_TIMER && ARM_TIMER_SP804 && ARMV7M_SYSTICK && ATMEL_PIT && CLKSRC_QCOM && CLKSRC_VERSATILE && CLKSRC_MIPS_GIC && CLKSRC_TANGO_XTAL && CLKSRC_ST_LPC) selects TIMER_OF which has unmet direct dependencies (!ARCH_USES_GETTIMEOFFSET && GENERIC_CLOCKEVENTS)
   warning: (FAULT_INJECTION_STACKTRACE_FILTER && LATENCYTOP && KMEMCHECK && LOCKDEP) selects FRAME_POINTER which has unmet direct dependencies (DEBUG_KERNEL && (CRIS || M68K || FRV || UML || SUPERH || BLACKFIN || MN10300 || METAG) || ARCH_WANT_FRAME_POINTERS)
   In file included from include/uapi/linux/stddef.h:1:0,
                    from include/linux/stddef.h:4,
                    from include/uapi/linux/posix_types.h:4,
                    from include/uapi/linux/types.h:13,
                    from include/linux/types.h:5,
                    from include/linux/list.h:4,
                    from include/linux/rculist.h:9,
                    from include/linux/sched/signal.h:4,
                    from arch/ia64/kernel/asm-offsets.c:9:
   arch/ia64/kernel/asm-offsets.c: In function 'foo':
>> include/linux/compiler.h:576:38: error: call to '__compiletime_assert_33' declared with attribute error: BUILD_BUG_ON failed: sizeof(struct upid) != 32
     _compiletime_assert(condition, msg, __compiletime_assert_, __LINE__)
                                         ^
   include/linux/compiler.h:556:4: note: in definition of macro '__compiletime_assert'
       prefix ## suffix();    \
       ^~~~~~
   include/linux/compiler.h:576:2: note: in expansion of macro '_compiletime_assert'
     _compiletime_assert(condition, msg, __compiletime_assert_, __LINE__)
     ^~~~~~~~~~~~~~~~~~~
   include/linux/build_bug.h:46:37: note: in expansion of macro 'compiletime_assert'
    #define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond), msg)
                                        ^~~~~~~~~~~~~~~~~~
   include/linux/build_bug.h:70:2: note: in expansion of macro 'BUILD_BUG_ON_MSG'
     BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition)
     ^~~~~~~~~~~~~~~~
>> arch/ia64/kernel/asm-offsets.c:33:2: note: in expansion of macro 'BUILD_BUG_ON'
     BUILD_BUG_ON(sizeof(struct upid) != 32);
     ^~~~~~~~~~~~
   make[2]: *** [arch/ia64/kernel/asm-offsets.s] Error 1
   make[2]: Target '__build' not remade because of errors.
   make[1]: *** [prepare0] Error 2
   make[1]: Target 'prepare' not remade because of errors.
   make: *** [sub-make] Error 2

vim +/__compiletime_assert_33 +576 include/linux/compiler.h

9a8ab1c3 Daniel Santos 2013-02-21  562  
9a8ab1c3 Daniel Santos 2013-02-21  563  #define _compiletime_assert(condition, msg, prefix, suffix) \
9a8ab1c3 Daniel Santos 2013-02-21  564  	__compiletime_assert(condition, msg, prefix, suffix)
9a8ab1c3 Daniel Santos 2013-02-21  565  
9a8ab1c3 Daniel Santos 2013-02-21  566  /**
9a8ab1c3 Daniel Santos 2013-02-21  567   * compiletime_assert - break build and emit msg if condition is false
9a8ab1c3 Daniel Santos 2013-02-21  568   * @condition: a compile-time constant condition to check
9a8ab1c3 Daniel Santos 2013-02-21  569   * @msg:       a message to emit if condition is false
9a8ab1c3 Daniel Santos 2013-02-21  570   *
9a8ab1c3 Daniel Santos 2013-02-21  571   * In tradition of POSIX assert, this macro will break the build if the
9a8ab1c3 Daniel Santos 2013-02-21  572   * supplied condition is *false*, emitting the supplied error message if the
9a8ab1c3 Daniel Santos 2013-02-21  573   * compiler has support to do so.
9a8ab1c3 Daniel Santos 2013-02-21  574   */
9a8ab1c3 Daniel Santos 2013-02-21  575  #define compiletime_assert(condition, msg) \
9a8ab1c3 Daniel Santos 2013-02-21 @576  	_compiletime_assert(condition, msg, __compiletime_assert_, __LINE__)
9a8ab1c3 Daniel Santos 2013-02-21  577  

:::::: The code at line 576 was first introduced by commit
:::::: 9a8ab1c39970a4938a72d94e6fd13be88a797590 bug.h, compiler.h: introduce compiletime_assert & BUILD_BUG_ON_MSG

:::::: TO: Daniel Santos <daniel.santos@pobox.com>
:::::: CC: Linus Torvalds <torvalds@linux-foundation.org>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 51910 bytes --]

Re: [PATCH v4 2/2] pid: Remove pidhash

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 2750 bytes --]

On Wed, 2017-10-11 at 17:47 +0800, kbuild test robot wrote:

> > > '__compiletime_assert_33' declared with attribute error:
> > > BUILD_BUG_ON failed: sizeof(struct upid) != 32
> 
>      _compiletime_assert(condition, msg, __compiletime_assert_,
> __LINE__)
>                                          ^
>    include/linux/compiler.h:556:4: note: in definition of macro
> '__compiletime_assert'
>        prefix ## suffix();    \
>        ^~~~~~
>    include/linux/compiler.h:576:2: note: in expansion of macro
> '_compiletime_assert'
>      _compiletime_assert(condition, msg, __compiletime_assert_,
> __LINE__)
>      ^~~~~~~~~~~~~~~~~~~
>    include/linux/build_bug.h:46:37: note: in expansion of macro
> 'compiletime_assert'
>     #define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond),
> msg)
>                                         ^~~~~~~~~~~~~~~~~~
>    include/linux/build_bug.h:70:2: note: in expansion of macro
> 'BUILD_BUG_ON_MSG'
>      BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition)
>      ^~~~~~~~~~~~~~~~
> > > arch/ia64/kernel/asm-offsets.c:33:2: note: in expansion of macro
> > > 'BUILD_BUG_ON'
> 
>      BUILD_BUG_ON(sizeof(struct upid) != 32);
>      ^~~~~~~~~~~~
> 
Looks like arch/ia64/kernel/asm-offsets.c throws a BUILD_BUG
if sizeof(struct upid) != 32.

Your patch reduced the size of struct upid, which is a nice
thing, but now IA64 no longer builds.

Lets see what IA64 was doing with the size of struct upid
in the first place:

in arch/ia64/kernel/asm-offsets.c:

        BUILD_BUG_ON(sizeof(struct upid) != 32);
        DEFINE(IA64_UPID_SHIFT, 5);

Grepping for IA64_UPID_SHIFT leads us to some assembly
code implementing fsys_getpid (why is that in assembly?!):

        add r8=IA64_PID_LEVEL_OFFSET,r17
        ;;
        ld4 r8=[r8]                             // r8 = pid->level
        add r17=IA64_PID_UPID_OFFSET,r17        // r17 = &pid->numbers[0]
        ;;
        shl r8=r8,IA64_UPID_SHIFT
        ;;
        add r17=r17,r8                          // r17 = &pid->numbers[pid->level]
        ;;
        ld4 r8=[r17]                            // r8 = pid->numbers[pid->level].nr
        ;;
        mov r17=0

Luckily it looks like this is only referencing the first members of struct upid,
and you are removing the last member, so I suspect you will be fine changing the IA64
to this:

        BUILD_BUG_ON(sizeof(struct upid) != 16);
        DEFINE(IA64_UPID_SHIFT, 4);

Tony, does that look ok to you?

-- 
All Rights Reversed.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [PATCH v4 2/2] pid: Remove pidhash

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 2750 bytes --]

On Wed, 2017-10-11 at 17:47 +0800, kbuild test robot wrote:

> > > '__compiletime_assert_33' declared with attribute error:
> > > BUILD_BUG_ON failed: sizeof(struct upid) != 32
> 
>      _compiletime_assert(condition, msg, __compiletime_assert_,
> __LINE__)
>                                          ^
>    include/linux/compiler.h:556:4: note: in definition of macro
> '__compiletime_assert'
>        prefix ## suffix();    \
>        ^~~~~~
>    include/linux/compiler.h:576:2: note: in expansion of macro
> '_compiletime_assert'
>      _compiletime_assert(condition, msg, __compiletime_assert_,
> __LINE__)
>      ^~~~~~~~~~~~~~~~~~~
>    include/linux/build_bug.h:46:37: note: in expansion of macro
> 'compiletime_assert'
>     #define BUILD_BUG_ON_MSG(cond, msg) compiletime_assert(!(cond),
> msg)
>                                         ^~~~~~~~~~~~~~~~~~
>    include/linux/build_bug.h:70:2: note: in expansion of macro
> 'BUILD_BUG_ON_MSG'
>      BUILD_BUG_ON_MSG(condition, "BUILD_BUG_ON failed: " #condition)
>      ^~~~~~~~~~~~~~~~
> > > arch/ia64/kernel/asm-offsets.c:33:2: note: in expansion of macro
> > > 'BUILD_BUG_ON'
> 
>      BUILD_BUG_ON(sizeof(struct upid) != 32);
>      ^~~~~~~~~~~~
> 
Looks like arch/ia64/kernel/asm-offsets.c throws a BUILD_BUG
if sizeof(struct upid) != 32.

Your patch reduced the size of struct upid, which is a nice
thing, but now IA64 no longer builds.

Lets see what IA64 was doing with the size of struct upid
in the first place:

in arch/ia64/kernel/asm-offsets.c:

        BUILD_BUG_ON(sizeof(struct upid) != 32);
        DEFINE(IA64_UPID_SHIFT, 5);

Grepping for IA64_UPID_SHIFT leads us to some assembly
code implementing fsys_getpid (why is that in assembly?!):

        add r8=IA64_PID_LEVEL_OFFSET,r17
        ;;
        ld4 r8=[r8]                             // r8 = pid->level
        add r17=IA64_PID_UPID_OFFSET,r17        // r17 = &pid->numbers[0]
        ;;
        shl r8=r8,IA64_UPID_SHIFT
        ;;
        add r17=r17,r8                          // r17 = &pid->numbers[pid->level]
        ;;
        ld4 r8=[r17]                            // r8 = pid->numbers[pid->level].nr
        ;;
        mov r17=0

Luckily it looks like this is only referencing the first members of struct upid,
and you are removing the last member, so I suspect you will be fine changing the IA64
to this:

        BUILD_BUG_ON(sizeof(struct upid) != 16);
        DEFINE(IA64_UPID_SHIFT, 4);

Tony, does that look ok to you?

-- 
All Rights Reversed.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

RE: [PATCH v4 2/2] pid: Remove pidhash

[Luck, Tony]

>        DEFINE(IA64_UPID_SHIFT, 5);
>
> Grepping for IA64_UPID_SHIFT leads us to some assembly
> code implementing fsys_getpid (why is that in assembly?!):

The fast system call path has a whole host of serious restrictions on what it can
touch. See Documentation/ia64/fsys.txt.  Why is getpid() a fast system call? I think
there was some application (or perhaps benchmark) that used it a lot.

>        add r8=IA64_PID_LEVEL_OFFSET,r17
>        ;;
>        ld4 r8=[r8]                             // r8 = pid->level
>        add r17=IA64_PID_UPID_OFFSET,r17        // r17 = &pid->numbers[0]
>        ;;
>        shl r8=r8,IA64_UPID_SHIFT
>        ;;
>        add r17=r17,r8                          // r17 = &pid->numbers[pid->level]
>        ;;
>        ld4 r8=[r17]                            // r8 = pid->numbers[pid->level].nr
>        ;;
>        mov r17=0
>
> Luckily it looks like this is only referencing the first members of struct upid,
> and you are removing the last member, so I suspect you will be fine changing the IA64
> to this:
>
>        BUILD_BUG_ON(sizeof(struct upid) != 16);
>        DEFINE(IA64_UPID_SHIFT, 4);
>
> Tony, does that look ok to you?

I think so.  Respin and Cc: me on both patches in the series and I'll take it for a spin
on h/w to make sure.

-Tony

RE: [PATCH v4 2/2] pid: Remove pidhash

[Luck, Tony]

PsKgwqDCoMKgwqDCoMKgwqBERUZJTkUoSUE2NF9VUElEX1NISUZULCA1KTsNCj4NCj4gR3JlcHBp
bmcgZm9yIElBNjRfVVBJRF9TSElGVCBsZWFkcyB1cyB0byBzb21lIGFzc2VtYmx5DQo+IGNvZGUg
aW1wbGVtZW50aW5nIGZzeXNfZ2V0cGlkICh3aHkgaXMgdGhhdCBpbiBhc3NlbWJseT8hKToNCg0K
VGhlIGZhc3Qgc3lzdGVtIGNhbGwgcGF0aCBoYXMgYSB3aG9sZSBob3N0IG9mIHNlcmlvdXMgcmVz
dHJpY3Rpb25zIG9uIHdoYXQgaXQgY2FuDQp0b3VjaC4gU2VlIERvY3VtZW50YXRpb24vaWE2NC9m
c3lzLnR4dC4gIFdoeSBpcyBnZXRwaWQoKSBhIGZhc3Qgc3lzdGVtIGNhbGw/IEkgdGhpbmsNCnRo
ZXJlIHdhcyBzb21lIGFwcGxpY2F0aW9uIChvciBwZXJoYXBzIGJlbmNobWFyaykgdGhhdCB1c2Vk
IGl0IGEgbG90Lg0KDQo+ICAgICAgICBhZGQgcjg9SUE2NF9QSURfTEVWRUxfT0ZGU0VULHIxNw0K
PiAgICAgICAgOzsNCj4gICAgICAgIGxkNCByOD1bcjhdICAgICAgICAgICAgICAgICAgICAgICAg
ICAgICAvLyByOCA9IHBpZC0+bGV2ZWwNCj4gICAgICAgIGFkZCByMTc9SUE2NF9QSURfVVBJRF9P
RkZTRVQscjE3ICAgICAgICAvLyByMTcgPSAmcGlkLT5udW1iZXJzWzBdDQo+ICAgICAgICA7Ow0K
PiAgICAgICAgc2hsIHI4PXI4LElBNjRfVVBJRF9TSElGVA0KPiAgICAgICAgOzsNCj4gICAgICAg
IGFkZCByMTc9cjE3LHI4ICAgICAgICAgICAgICAgICAgICAgICAgICAvLyByMTcgPSAmcGlkLT5u
dW1iZXJzW3BpZC0+bGV2ZWxdDQo+ICAgICAgICA7Ow0KPiAgICAgICAgbGQ0IHI4PVtyMTddICAg
ICAgICAgICAgICAgICAgICAgICAgICAgIC8vIHI4ID0gcGlkLT5udW1iZXJzW3BpZC0+bGV2ZWxd
Lm5yDQo+ICAgICAgICA7Ow0KPiAgICAgICAgbW92IHIxNz0wDQo+DQo+IEx1Y2tpbHkgaXQgbG9v
a3MgbGlrZSB0aGlzIGlzIG9ubHkgcmVmZXJlbmNpbmcgdGhlIGZpcnN0IG1lbWJlcnMgb2Ygc3Ry
dWN0IHVwaWQsDQo+IGFuZCB5b3UgYXJlIHJlbW92aW5nIHRoZSBsYXN0IG1lbWJlciwgc28gSSBz
dXNwZWN0IHlvdSB3aWxsIGJlIGZpbmUgY2hhbmdpbmcgdGhlIElBNjQNCj4gdG8gdGhpczoNCj4N
Cj7CoMKgwqDCoMKgwqDCoMKgQlVJTERfQlVHX09OKHNpemVvZihzdHJ1Y3QgdXBpZCkgIT0gMTYp
Ow0KPsKgwqDCoMKgwqDCoMKgwqBERUZJTkUoSUE2NF9VUElEX1NISUZULCA0KTsNCj4NCj4gVG9u
eSwgZG9lcyB0aGF0IGxvb2sgb2sgdG8geW91Pw0KDQpJIHRoaW5rIHNvLiAgUmVzcGluIGFuZCBD
YzogbWUgb24gYm90aCBwYXRjaGVzIGluIHRoZSBzZXJpZXMgYW5kIEknbGwgdGFrZSBpdCBmb3Ig
YSBzcGluDQpvbiBoL3cgdG8gbWFrZSBzdXJlLg0KDQotVG9ueQ0K