The patch titled
Subject: kernel/exit.c: do_wait: make PIDTYPE_PID case O(1) instead of O(n)
has been added to the -mm tree. Its filename is
do_wait-make-pidtype_pid-case-o1-instead-of-on.patch
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/do_wait-make-pidtype_pid-case-o1-instead-of-on.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/do_wait-make-pidtype_pid-case-o1-instead-of-on.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Jim Newsome <jnewsome@xxxxxxxxxxxxxx>
Subject: kernel/exit.c: 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 performance when waiting on
a pid from a thread group with many children and/or tracees.
Link: https://lkml.kernel.org/r/20210312173855.24843-1-jnewsome@xxxxxxxxxxxxxx
Signed-off-by: James Newsome <jnewsome@xxxxxxxxxxxxxx>
Cc: Oleg Nesterov <oleg@xxxxxxxxxx>
Cc: "Eric W . Biederman" <ebiederm@xxxxxxxxxxxx>
Cc: Christian Brauner <christian@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
kernel/exit.c | 69 +++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 59 insertions(+), 10 deletions(-)
--- a/kernel/exit.c~do_wait-make-pidtype_pid-case-o1-instead-of-on
+++ a/kernel/exit.c
@@ -1439,9 +1439,50 @@ void __wake_up_parent(struct task_struct
TASK_INTERRUPTIBLE, p);
}
+static bool is_effectively_child(struct wait_opts *wo, bool ptrace,
+ struct task_struct *target)
+{
+ struct task_struct *parent =
+ !ptrace ? target->real_parent : target->parent;
+
+ return current == parent || (!(wo->wo_flags & __WNOTHREAD) &&
+ same_thread_group(current, parent));
+}
+
+/*
+ * Optimization for waiting on PIDTYPE_PID. No need to iterate through child
+ * and tracee lists to find the target task.
+ */
+static int do_wait_pid(struct wait_opts *wo)
+{
+ bool ptrace;
+ struct task_struct *target;
+ int retval;
+
+ target = pid_task(wo->wo_pid, PIDTYPE_PID);
+ if (!target)
+ return 0;
+
+ ptrace = false;
+ if (thread_group_leader(target) &&
+ is_effectively_child(wo, ptrace, target)) {
+ retval = wait_consider_task(wo, ptrace, target);
+ if (retval)
+ return retval;
+ }
+
+ ptrace = true;
+ if (target->ptrace && is_effectively_child(wo, ptrace, target)) {
+ retval = wait_consider_task(wo, ptrace, target);
+ if (retval)
+ return retval;
+ }
+
+ return 0;
+}
+
static long do_wait(struct wait_opts *wo)
{
- struct task_struct *tsk;
int retval;
trace_sched_process_wait(wo->wo_pid);
@@ -1463,19 +1504,27 @@ repeat:
set_current_state(TASK_INTERRUPTIBLE);
read_lock(&tasklist_lock);
- tsk = current;
- do {
- retval = do_wait_thread(wo, tsk);
- if (retval)
- goto end;
- retval = ptrace_do_wait(wo, tsk);
+ if (wo->wo_type == PIDTYPE_PID) {
+ retval = do_wait_pid(wo);
if (retval)
goto end;
+ } else {
+ struct task_struct *tsk = current;
- if (wo->wo_flags & __WNOTHREAD)
- break;
- } while_each_thread(current, tsk);
+ do {
+ retval = do_wait_thread(wo, tsk);
+ if (retval)
+ goto end;
+
+ retval = ptrace_do_wait(wo, tsk);
+ if (retval)
+ goto end;
+
+ if (wo->wo_flags & __WNOTHREAD)
+ break;
+ } while_each_thread(current, tsk);
+ }
read_unlock(&tasklist_lock);
notask:
_
Patches currently in -mm which might be from jnewsome@xxxxxxxxxxxxxx are
do_wait-make-pidtype_pid-case-o1-instead-of-on.patch
