pid: replace idr api with xarray
Subsystems (6)
cover pid: replace idr api with xarray
Hi all,
This series is a few patches to switch struct pid management over from the idr api to the xarray api. The underlying data structures are already the same between both apis, but the idr relies on the old and slightly customized radix-tree implementation to accomplish things like efficient free id tracking, which xarray already supports directly.
This is all based on a prototype patch[1] from Willy that fell out from discussion on a separate series to try and improve /proc readdir performance using radix-tree tags (to be replaced with xarray marks). I've basically split it up into a few smaller patches, made some minor tweaks, and ran some tests on the result.
Willy,
Re: the above, I've included your s-o-b on each of the patches. I'm not sure what your preference or the proper etiquette is here. Let me know if you want me to change authorship or tags or whatever in any way..
Brian
[1] https://lore.kernel.org/linux-fsdevel/[email protected]/
Brian Foster (3):
pid: replace pidmap_lock with xarray lock
pid: split cyclic id allocation cursor from idr
pid: switch pid_namespace from idr to xarray
arch/powerpc/platforms/cell/spufs/sched.c | 2 +- fs/proc/loadavg.c | 2 +- include/linux/pid_namespace.h | 9 +- include/linux/threads.h | 2 +- init/main.c | 3 +- kernel/pid.c | 133 +++++++++++----------- kernel/pid_namespace.c | 23 ++-- 7 files changed, 85 insertions(+), 89 deletions(-)
Signature · 1 line
2.35.3
PATCH 1/3 pid: replace pidmap_lock with xarray lock
As a first step to changing the struct pid tracking code from the idr over to the xarray, replace the custom pidmap_lock spinlock with the internal lock associated with the underlying xarray. This is effectively equivalent to using idr_lock() and friends, but since the goal is to disentangle from the idr, move directly to the underlying xarray api.
Signed-off-by Matthew Wilcox <[email protected]>
Signed-off-by Brian Foster <[email protected]>
--- kernel/pid.c | 79 ++++++++++++++++++++++++++-------------------------- 1 file changed, 40 insertions(+), 39 deletions(-)
kernel/pid.c +40 -39
@@ -86,22 +86,6 @@ struct pid_namespace init_pid_ns = { };EXPORT_SYMBOL_GPL (init_pid_ns); -/* -* Note: disable interrupts while the pidmap_lock is held as an -* interrupt might come in and do read_lock(&tasklist_lock). -* -* If we don't disable interrupts there is a nasty deadlock between -* detach_pid()->free_pid() and another cpu that does -* spin_lock(&pidmap_lock) followed by an interrupt routine that does -* read_lock(&tasklist_lock); -* -* After we clean up the tasklist_lock and know there are no -* irq handlers that take it we can leave the interrupts enabled. -* For now it is easier to be safe than to prove it can't happen. -*/ - -static __cacheline_aligned_in_smp DEFINE_SPINLOCK (pidmap_lock ); -void put_pid (struct pid *pid) {struct pid_namespace *ns;
@@ -129,10 +113,11 @@ void free_pid(struct pid *pid)int i;unsigned long flags; -spin_lock_irqsave (&pidmap_lock, flags);for (i =0 ; i <= pid->level; i++) {struct upid *upid = pid->numbers + i;struct pid_namespace *ns = upid->ns; + +xa_lock_irqsave (&ns->idr.idr_rt, flags);switch (--ns->pid_allocated) {case 2 :case 1 :
@@ -150,8 +135,8 @@ void free_pid(struct pid *pid) }idr_remove (&ns->idr, upid->nr); +xa_unlock_irqrestore (&ns->idr.idr_rt, flags); } -spin_unlock_irqrestore (&pidmap_lock, flags);call_rcu (&pid->rcu, delayed_put_pid); }
@@ -206,7 +191,7 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid, }idr_preload (GFP_KERNEL ); -spin_lock_irq (&pidmap_lock); +xa_lock_irq (&tmp->idr.idr_rt);if (tid) { nr = idr_alloc(&tmp->idr, NULL, tid,
@@ -233,7 +218,7 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid, nr =idr_alloc_cyclic (&tmp->idr,NULL , pid_min, pid_max,GFP_ATOMIC ); } -spin_unlock_irq (&pidmap_lock); +xa_unlock_irq (&tmp->idr.idr_rt);idr_preload_end ();if (nr <0 ) {
@@ -266,34 +251,38 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,INIT_HLIST_HEAD (&pid->inodes); upid = pid->numbers + ns->level; -spin_lock_irq (&pidmap_lock); -if (!(ns->pid_allocated &PIDNS_ADDING )) - goto out_unlock;for ( ; upid >= pid->numbers; --upid) { + tmp = upid->ns; + +xa_lock_irq (&tmp->idr.idr_rt); +if (tmp == ns && !(tmp->pid_allocated &PIDNS_ADDING )) { +xa_unlock_irq (&tmp->idr.idr_rt); +put_pid_ns (ns); + goto out_free; + } +/* Make the PID visible to find_pid_ns. */ -idr_replace (&upid->ns->idr, pid, upid->nr); - upid->ns->pid_allocated++; +idr_replace (&tmp->idr, pid, upid->nr); + tmp->pid_allocated++; +xa_unlock_irq (&tmp->idr.idr_rt); } -spin_unlock_irq (&pidmap_lock);return pid; -out_unlock: -spin_unlock_irq (&pidmap_lock); -put_pid_ns (ns); - out_free: -spin_lock_irq (&pidmap_lock);while (++i <= ns->level) { upid = pid->numbers + i; -idr_remove (&upid->ns->idr, upid->nr); - } + tmp = upid->ns; -/* On failure to allocate the first pid, reset the state */ -if (ns->pid_allocated ==PIDNS_ADDING ) -idr_set_cursor (&ns->idr,0 ); +xa_lock_irq (&tmp->idr.idr_rt); -spin_unlock_irq (&pidmap_lock); +/* On failure to allocate the first pid, reset the state */ +if (tmp == ns && tmp->pid_allocated ==PIDNS_ADDING ) +idr_set_cursor (&ns->idr,0 ); + +idr_remove (&tmp->idr, upid->nr); +xa_unlock_irq (&tmp->idr.idr_rt); + }kmem_cache_free (ns->pid_cachep, pid);return ERR_PTR (retval);
@@ -301,9 +290,9 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,void disable_pid_allocation (struct pid_namespace *ns) { -spin_lock_irq (&pidmap_lock); +xa_lock_irq (&ns->idr.idr_rt); ns->pid_allocated &= ~PIDNS_ADDING ; -spin_unlock_irq (&pidmap_lock); +xa_unlock_irq (&ns->idr.idr_rt); }struct pid *find_pid_ns (int nr,struct pid_namespace *ns)
@@ -646,6 +635,18 @@ SYSCALL_DEFINE2(pidfd_open, pid_t, pid, unsigned int, flags)return fd; } +/* +* Note: disable interrupts while the xarray lock is held as an interrupt might +* come in and do read_lock(&tasklist_lock). +* +* If we don't disable interrupts there is a nasty deadlock between +* detach_pid()->free_pid() and another cpu that does xa_lock() followed by an +* interrupt routine that does read_lock(&tasklist_lock); +* +* After we clean up the tasklist_lock and know there are no irq handlers that +* take it we can leave the interrupts enabled. For now it is easier to be safe +* than to prove it can't happen. +*/ void __init pid_idr_init (void ) {/* Verify no one has done anything silly: */
Signature · 1 line
2.35.3
PATCH 2/3 pid: split cyclic id allocation cursor from idr
In reply to Brian FosterAs a next step in separating pid allocation from the idr, split off the cyclic pid allocation cursor from the idr. Lift the cursor value into the sturct pid_namespace. Note that this involves temporarily open-coding the cursor increment on allocation, but this is cleaned up in the subsequent patch.
Signed-off-by Matthew Wilcox <[email protected]>
Signed-off-by Brian Foster <[email protected]>
--- arch/powerpc/platforms/cell/spufs/sched.c | 2 +- fs/proc/loadavg.c | 2 +- include/linux/pid_namespace.h | 1 + kernel/pid.c | 6 ++++-- kernel/pid_namespace.c | 4 ++-- 5 files changed, 9 insertions(+), 6 deletions(-)
arch/powerpc/platforms/cell/spufs/sched.c +1 -1
@@ -1072,7 +1072,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), - idr_get_cursor(&task_active_pid_ns(current)->idr) - 1); + READ_ONCE(task_active_pid_ns(current)->pid_next) - 1); return 0; }#endif
fs/proc/loadavg.c +1 -1
@@ -21,7 +21,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, - idr_get_cursor(&task_active_pid_ns(current)->idr) - 1); + READ_ONCE(task_active_pid_ns(current)->pid_next) - 1);return 0 ; }
include/linux/pid_namespace.h +1 -0
@@ -18,6 +18,7 @@ struct fs_pin;struct pid_namespace {struct idr idr; +unsigned int pid_next;struct rcu_head rcu;unsigned int pid_allocated;struct task_struct *child_reaper;
kernel/pid.c +4 -2
@@ -75,6 +75,7 @@ int pid_max_max = PID_MAX_LIMIT;struct pid_namespace init_pid_ns = { .ns.count =REFCOUNT_INIT (2 ), .idr =IDR_INIT (init_pid_ns.idr), + .pid_next =0 , .pid_allocated =PIDNS_ADDING , .level =0 , .child_reaper = &init_task,
@@ -208,7 +209,7 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,* init really needs pid 1, but after reaching the * maximum wrap back to RESERVED_PIDS */ -if (idr_get_cursor (&tmp->idr) >RESERVED_PIDS ) +if (tmp->pid_next >RESERVED_PIDS ) pid_min =RESERVED_PIDS ;/*
@@ -217,6 +218,7 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,*/ nr =idr_alloc_cyclic (&tmp->idr,NULL , pid_min, pid_max,GFP_ATOMIC ); + tmp->pid_next = nr +1 ; }xa_unlock_irq (&tmp->idr.idr_rt);idr_preload_end ();
@@ -278,7 +280,7 @@ struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,/* On failure to allocate the first pid, reset the state */ if (tmp == ns && tmp->pid_allocated ==PIDNS_ADDING ) -idr_set_cursor (&ns->idr,0 ); + ns->pid_next =0 ;idr_remove (&tmp->idr, upid->nr);xa_unlock_irq (&tmp->idr.idr_rt);
kernel/pid_namespace.c +2 -2
@@ -272,12 +272,12 @@ static int pid_ns_ctl_handler(struct ctl_table *table, int write,* it should synchronize its usage with external means. */ - next =idr_get_cursor (&pid_ns->idr) -1 ; + next =READ_ONCE (pid_ns->pid_next) -1 ; tmp.data = &next; ret =proc_dointvec_minmax (&tmp, write, buffer, lenp, ppos);if (!ret && write) -idr_set_cursor (&pid_ns->idr, next +1 ); +WRITE_ONCE (pid_ns->pid_next, next +1 );return ret; }
Signature · 1 line
2.35.3
PATCH 3/3 pid: switch pid_namespace from idr to xarray
In reply to Brian FosterSwitch struct pid[_namespace] management over to use the xarray api directly instead of the idr. The underlying data structures used by both interfaces is the same. The difference is that the idr api relies on the old, idr-custom radix-tree implementation for things like efficient tracking/allocation of free ids. The xarray already supports this, so most of this is a direct switchover from the old api to the new.
Signed-off-by Matthew Wilcox <[email protected]>
Signed-off-by Brian Foster <[email protected]>
--- include/linux/pid_namespace.h | 8 ++-- include/linux/threads.h | 2 +- init/main.c | 3 +- kernel/pid.c | 78 ++++++++++++++++------------------- kernel/pid_namespace.c | 19 ++++----- 5 files changed, 51 insertions(+), 59 deletions(-)
include/linux/pid_namespace.h +5 -3
@@ -9,7 +9,7 @@#include <linux/threads.h> #include <linux/nsproxy.h> #include <linux/ns_common.h> -#include <linux/idr.h> +#include <linux/xarray.h> /* MAX_PID_NS_LEVEL is needed for limiting size of 'struct pid' */ #define MAX_PID_NS_LEVEL 32
@@ -17,7 +17,7 @@struct fs_pin ;struct pid_namespace { -struct idr idr; +struct xarray xa;unsigned int pid_next;struct rcu_head rcu;unsigned int pid_allocated;
@@ -38,6 +38,8 @@ extern struct pid_namespace init_pid_ns;#define PIDNS_ADDING (1U << 31) +#define PID_XA_FLAGS (XA_FLAGS_TRACK_FREE | XA_FLAGS_LOCK_IRQ) +#ifdef CONFIG_PID_NS static inline struct pid_namespace *get_pid_ns (struct pid_namespace *ns) {
@@ -85,7 +87,7 @@ 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 pid_idr_init (void ); +void pid_init (void );static inline bool task_is_in_init_pid_ns (struct task_struct *tsk) {
include/linux/threads.h +1 -1
@@ -38,7 +38,7 @@* Define a minimum number of pids per cpu. Heuristically based * on original pid max of 32k for 32 cpus. Also, increase the * minimum settable value for pid_max on the running system based -* on similar defaults. See kernel/pid.c:pid_idr_init() for details. +* on similar defaults. See kernel/pid.c:pid_init() for details. */ #define PIDS_PER_CPU_DEFAULT 1024#define PIDS_PER_CPU_MIN 8
init/main.c +1 -2
@@ -73,7 +73,6 @@#include <linux/sched.h> #include <linux/sched/init.h> #include <linux/signal.h> -#include <linux/idr.h> #include <linux/kgdb.h> #include <linux/ftrace.h> #include <linux/async.h>
@@ -1100,7 +1099,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)late_time_init ();sched_clock_init ();calibrate_delay (); -pid_idr_init (); +pid_init ();anon_vma_init ();#ifdef CONFIG_X86 if (efi_enabled (EFI_RUNTIME_SERVICES ))
kernel/pid.c +35 -43
183 lines not on this page · raw message
kernel/pid_namespace.c +9 -10
@@ -22,7 +22,7 @@#include <linux/export.h> #include <linux/sched/task.h> #include <linux/sched/signal.h> -#include <linux/idr.h> +#include <linux/xarray.h> static DEFINE_MUTEX (pid_caches_mutex);static struct kmem_cache *pid_ns_cachep;
@@ -92,15 +92,15 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_nsif (ns ==NULL ) goto out_dec; -idr_init (&ns->idr); +xa_init_flags (&ns->xa,PID_XA_FLAGS ); ns->pid_cachep =create_pid_cachep (level);if (ns->pid_cachep ==NULL ) - goto out_free_idr; + goto out_free_xa; err =ns_alloc_inum (&ns->ns);if (err) - goto out_free_idr; + goto out_free_xa; ns->ns.ops = &pidns_operations;refcount_set (&ns->ns.count,1 );
@@ -112,8 +112,8 @@ static struct pid_namespace *create_pid_namespace(struct user_namespace *user_nsreturn ns; -out_free_idr: -idr_destroy (&ns->idr); +out_free_xa: +xa_destroy (&ns->xa);kmem_cache_free (pid_ns_cachep, ns); out_dec:dec_pid_namespaces (ucounts);
@@ -135,7 +135,7 @@ static void destroy_pid_namespace(struct pid_namespace *ns) {ns_free_inum (&ns->ns); -idr_destroy (&ns->idr); +xa_destroy (&ns->xa);call_rcu (&ns->rcu, delayed_free_pidns); }
@@ -165,7 +165,7 @@ EXPORT_SYMBOL_GPL(put_pid_ns);void zap_pid_ns_processes (struct pid_namespace *pid_ns) { -int nr; +long nr;int rc;struct task_struct *task, *me = current;int init_pids =thread_group_leader (me) ?1 :2 ;
@@ -198,8 +198,7 @@ void zap_pid_ns_processes(struct pid_namespace *pid_ns)*/ rcu_read_lock ();read_lock (&tasklist_lock); - nr =2 ; -idr_for_each_entry_continue (&pid_ns->idr, pid, nr) { +xa_for_each_range (&pid_ns->xa, nr, pid,2 ,ULONG_MAX ) { task =pid_task (pid,PIDTYPE_PID );if (task && !__fatal_signal_pending (task))group_send_sig_info (SIGKILL ,SEND_SIG_PRIV , task,PIDTYPE_MAX );
Signature · 1 line
2.35.3