Re: [RFC PATCH 0/3 v3] futex/sched: introduce FUTEX_SWAP operation

I'm not well versed in this part of the kernel (ok, any part, really), but I wanted to chime in from a user perspective that I'm very interested in this functionality. We (Rob + Ryan + I, cc'd) are currently developing the second generation of the Shadow simulator , whic

[PATCH v7] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

This patch adds a special-case when waiting on a pid (via waitpid, waitid, wait4, etc) to avoid doing an O(n) scan of children and tracees, and instead do an O(1) lookup. This improves performance when waiting on a pid from a thread group with many children and/or tracees. Time to fork and then ca

Re: [PATCH v6] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/14/21 17:56, Jim Newsome wrote: > * Switched back to explicitly looking up by tgid and then pid. Shoot, I seem to have dropped that somehow in my rebase-and-squash. v7 out shortly; sorry for the noise.

[PATCH v6] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

This patch adds a special-case when waiting on a pid (via waitpid, waitid, wait4, etc) to avoid doing an O(n) scan of children and tracees, and instead do an O(1) lookup. This improves performance when waiting on a pid from a thread group with many children and/or tracees. Time to fork and then ca

Re: [PATCH v5] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

Here are the micro-benchmark results. I ended up reworking it to use google's benchmark tool [1]. For each N I timed how long it took to fork a new child and then immediately wait on it, while already having N other children. (Initially I tried to vfork, but that didn't play nicely with the benchma

Re: [PATCH v5] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/12/21 14:29, Eric W. Biederman wrote: > When I looked at this a second time it became apparent that using > pid_task twice should actually be faster as it removes a dependent load > caused by thread_group_leader, and replaces it by accessing two adjacent > pointers in the same cache line. > >

Re: [PATCH v5] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

(Re-sent without html part, which the list rejected) On 3/12/21 12:47, Andrew Morton wrote: > IOW, please spend a bit of time selling the patch! What is the case > for including it in Linux? What benefit does it provide our users? Ah yes - I'd included some context when I first reached out to

Re: [PATCH v5] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/12/21 12:22, Andrew Morton wrote: > > Could we please see some performance testing results to permit us to > evaluate the value of this change? Sure. I've been doing some ad-hoc measurements with the code below. It forks 8k children and then waits for them in reverse order (forcing a full li

[PATCH v5] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

do_wait is an internal function used to implement waitpid, waitid, wait4, etc. To handle the general case, it does an O(n) linear scan of the thread group's children and tracees. This patch adds a special-case when waiting on a pid to skip these scans and instead do an O(1) lookup. This improves p

Re: [PATCH v4] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/12/21 10:41, Oleg Nesterov wrote: > On 03/11, Jim Newsome wrote: >> + >> +if (target && is_effectively_child(wo, ptrace, target)) { >> +retval = wait_consider_task(wo, ptrace, target); > No, this is not right... You need to check target->p

[PATCH v4] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

do_wait is an internal function used to implement waitpid, waitid, wait4, etc. To handle the general case, it does an O(n) linear scan of the thread group's children and tracees. This patch adds a special-case when waiting on a pid to skip these scans and instead do an O(1) lookup. This improves p

Re: [PATCH] ptrace: Allow other threads to access tracee

On 3/11/21 09:21, Oleg Nesterov wrote: > Cough... it is not that simple. Yes, I was afraid of that :) > Just suppose that 2 threads call ptrace(tracee) at the same time. Say, the 1st > thread does PTRACE_CONT while the 2nd thread tries to change the registers. Is it acceptable for the new register

Re: [PATCH v3] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/11/21 09:15, Oleg Nesterov wrote: > On 03/10, Jim Newsome wrote: >> On 3/10/21 16:40, Eric W. Biederman wrote: >> >>>> +static int do_wait_pid(struct wait_opts *wo) >>>> +{ >>>> + struct tas

Re: [PATCH v3] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/10/21 16:40, Eric W. Biederman wrote: >> +// Optimization for waiting on PIDTYPE_PID. No need to iterate through child >> +// and tracee lists to find the target task. > > Minor nit: C++ style comments look very out of place in this file > which uses old school C /* */ comment del

[PATCH] ptrace: Allow other threads to access tracee

Currently only the tracing thread can call ptrace on a given pid. This patch allows any task in the tracing thread's thread group to also call ptrace. This makes it easier and more performant to write multi-threaded applications that use ptrace. In our ptrace-based simulator, we currently work-aro

Re: [PATCH v2] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

On 3/9/21 11:15, Oleg Nesterov wrote: > Jim, > > Thanks, the patch looks good to me. Yet I think you need to send V3 even > if I personally do not care ;) Please consider ./scripts/checkpatch.pl, > it reports all the coding-style problems I was going to mention. Thanks! I'd thought clang-format wi

[PATCH v3] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

do_wait is an internal function used to implement waitpid, waitid, wait4, etc. To handle the general case, it does an O(n) linear scan of the thread group's children and tracees. This patch adds a special-case when waiting on a pid to skip these scans and instead do an O(1) lookup. This improves p

Re: patch: do_wait: make PIDTYPE_PID case O(1) instead of O(n)

Thanks for the quick review! On 3/9/21 02:56, Oleg Nesterov wrote: > I'd suggest to put this PIDTYPE_PID code into the new function. Done > No, you don't need rcu lock, tasklist_lock is sufficient Done > This is wrong, you forgot to drop tasklist_lock. Done >> +real_parent = !tar

[PATCH v2] do_wait: make PIDTYPE_PID case O(1) instead of O(n)

do_wait is an internal function used to implement waitpid, waitid, wait4, etc. To handle the general case, it does an O(n) linear scan of the thread group's children and tracees. This patch adds a special-case when waiting on a pid to skip these scans and instead do an O(1) lookup. This improves p