Replace PID implementation with IDR API

RFC In review Gargi Sharma 3 participants 6 messages Sep 9, 2017 – Sep 11, 2017

Subsystems (2)

Proc filesystem Namespaces:

lore

Share & tools

lore

Gargi Sharma

author

2017-09-09 15:21 UTC #0 lore raw

cover Replace PID implementation with IDR API

This patch series replaces kernel bitmap implementation of PID allocation with IDR API.

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
3602 324 8 3934 f5e 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
2858 216 16 3090 c12 kernel/pid_namespace.o

There wasn't a considerable difference between the time required for allocation of PIDs to the processes. The IDR implementation is a little faster than bitmap implementation.

The next change in the pipeline is replacing pidhash with IDR API implementation.

Gargi Sharma (2):
proc: Return if nothing to unmount
pid: Replace PID bitmap implementation with IDR API

 fs/proc/base.c                |   4 +
 include/linux/pid.h           |   1 +
 include/linux/pid_namespace.h |   5 +-
 init/main.c                   |   4 +-
 kernel/pid.c                  | 204 ++++++++----------------------------------
 kernel/pid_namespace.c        |  39 ++++----
 6 files changed, 63 insertions(+), 194 deletions(-)

Signature · 1 line

2.7.4

Gargi Sharma

author

2017-09-09 15:21 UTC #1 lore raw

RFC 1/2 proc: Return if nothing to unmount

If a task exits before procfs is mounted, proc_flush_task_mnt will be called with a NULL mnt parameter. In that case, not only is there nothing to unhash, but trying to do so will oops the kernel with a null pointer dereference.

Signed-off-by Gargi Sharma <[email protected]>

---
 fs/proc/base.c | 4 ++++
 1 file changed, 4 insertions(+)

fs/proc/base.c +4 -0

index e5d89a0..7b83c21 100644
@@ -3021,6 +3021,10 @@ static void proc_flush_task_mnt(struct vfsmount *mnt, pid_t pid, pid_t tgid)
 	char buf[PROC_NUMBUF];
 	struct qstr name;
 
+	/* procfs is not mounted. There is nothing to unhash. */
+	if (!mnt)
+		return;
+
 	name.name = buf;
 	name.len = snprintf(buf, sizeof(buf), "%d", pid);
 	/* no ->d_hash() rejects on procfs */

Signature · 1 line

2.7.4

Al Viro

2017-09-09 18:31 UTC #2 lore raw

Re: [RFC 1/2] proc: Return if nothing to unmount

Quoted 4 lines · Gargi Sharma

If a task exits before procfs is mounted, proc_flush_task_mnt will be called with a NULL mnt parameter. In that case, not only is there nothing to unhash, but trying to do so will oops the kernel with a null pointer dereference.

You are misreading that sucker. It's about userland mounts, it's about the internal ones in pidns, for each pidns the process belongs to.

IOW, what you are adding is dead code. The very first alloc_pid() in that pidns should've called pid_ns_prepare_proc(), which creates that vfsmount.

Rik van Riel

2017-09-10 20:08 UTC #3 lore raw

Re: [RFC 1/2] proc: Return if nothing to unmount

Quoted 6 lines · Al Viro

Quoted 4 lines · Gargi Sharma
If a task exits before procfs is mounted, proc_flush_task_mnt will be called with a NULL mnt parameter. In that case, not only is there nothing to unhash, but trying to do so will oops the kernel with a null pointer dereference.

Quoted 6 lines

You are misreading that sucker. It's about userland mounts, it's about the internal ones in pidns, for each pidns the process belongs to.
IOW, what you are adding is dead code. The very first alloc_pid() in that pidns should've called pid_ns_prepare_proc(), which creates that vfsmount.

Huh, my bad. I wonder why Gargi's code ran into a null pointer dereference on a null mnt pointer, then...

Signature · 1 line

Sent from my Android device with K-9 Mail. Please excuse my brevity.

Rik van Riel

2017-09-11 00:58 UTC #4 lore raw

Re: [RFC 1/2] proc: Return if nothing to unmount

In reply to Al Viro

Quoted 7 lines · Al Viro

Quoted 5 lines · Gargi Sharma
If a task exits before procfs is mounted, proc_flush_task_mnt will be called with a NULL mnt parameter. In that case, not only is there
nothing to unhash, but trying to do so will oops the kernel with a null pointer dereference.

Quoted 7 lines

You are misreading that sucker. It's about userland mounts, it's about
the internal ones in pidns, for each pidns the process belongs to.
IOW, what you are adding is dead code. The very first alloc_pid() in that pidns should've called pid_ns_prepare_proc(), which creates that vfsmount.

Looking at the code (now that I am home, and no longer reading this email on my phone), I see the cause of this problem.

A previous version of Gargi's code had RESERVED_PIDS as the lower bound for idr_alloc_cyclic, even on the very first PID allocation cycle in a PID namespace.

With the code changed to have 1 as the lower bound during the first allocation cycle, pid_ns_prepare_proc() should be called correctly, and things should work as expected.

Gargi, can you drop this patch 1/2, and make sure the code still works fine?

Signature · 1 line

All Rights Reversed.

Gargi Sharma

author

2017-09-09 15:21 UTC #5 lore raw

RFC 2/2 pid: Replace PID bitmap implementation with IDR API

In reply to 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 <[email protected]>

---
 include/linux/pid.h           |   1 +
 include/linux/pid_namespace.h |   5 +-
 init/main.c                   |   4 +-
 kernel/pid.c                  | 204 ++++++++----------------------------------
 kernel/pid_namespace.c        |  39 ++++----
 5 files changed, 59 insertions(+), 194 deletions(-)

include/linux/pid.h +1 -0

index 7195827..de85a7b 100644
@@ -99,6 +99,7 @@ extern void transfer_pid(struct task_struct *old, struct task_struct *new,
 
 struct pid_namespace;
 extern struct pid_namespace init_pid_ns;
+extern int pid_max;
 
 /*
  * look up a PID in the hash table. Must be called with the tasklist_lock

include/linux/pid_namespace.h +3 -2

index b09136f..1ac6e85 100644
@@ -9,6 +9,7 @@
 #include <linux/nsproxy.h>
 #include <linux/kref.h>
 #include <linux/ns_common.h>
+#include <linux/idr.h>
 
 struct pidmap {
        atomic_t nr_free;

@@ -29,7 +30,7 @@ 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;

@@ -105,6 +106,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 */

init/main.c +2 -2

index a21a1a8..8821c1d 100644
@@ -16,6 +16,7 @@
 #include <linux/module.h>
 #include <linux/proc_fs.h>
 #include <linux/binfmts.h>
+#include <linux/delay.h>
 #include <linux/kernel.h>
 #include <linux/syscalls.h>
 #include <linux/stackprotector.h>

@@ -667,7 +668,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

@@ -989,7 +990,6 @@ static inline void mark_readonly(void)
 static int __ref kernel_init(void *unused)
 {
 	int ret;
-
 	kernel_init_freeable();
 	/* need to finish all async __init code before freeing the memory */
 	async_synchronize_full();

kernel/pid.c +38 ~~-166~~

283 lines not on this page · raw message

kernel/pid_namespace.c +15 ~~-24~~

index 74a5a72..d0dc231 100644
@@ -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 = -ENOSPC;

@@ -113,17 +113,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);

@@ -134,17 +132,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);

@@ -164,11 +155,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);
 }

@@ -205,10 +194,11 @@ EXPORT_SYMBOL_GPL(put_pid_ns);
 
 void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 {
-	int nr;
+	int nr = 2;
 	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);

@@ -236,8 +226,8 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 	 *
 	 */
 	read_lock(&tasklist_lock);
-	nr = next_pidmap(pid_ns, 1);
-	while (nr > 0) {
+	pid = idr_get_next(&pid_ns->idr, &nr);
+	while (pid) {
 		rcu_read_lock();
 
 		task = pid_task(find_vpid(nr), PIDTYPE_PID);

@@ -246,7 +236,8 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)
 
 		rcu_read_unlock();
 
-		nr = next_pidmap(pid_ns, nr);
+		nr++;
+		pid = idr_get_next(&pid_ns->idr, &nr);
 	}
 	read_unlock(&tasklist_lock);

@@ -307,7 +298,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_max;
 	return proc_dointvec_minmax(&tmp, write, buffer, lenp, ppos);
 }

Signature · 1 line

2.7.4