[PATCH bpf-next 5/9] uprobes: Don't sleep on mmap_lock under dup_mmap_sem

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

From: Alexei Starovoitov <ast@kernel.org>

register_for_each_vma() takes dup_mmap_sem for writing, collects mms that
map the file and takes mmap_lock of every mm. fork() takes dup_mmap_sem for
reading. When mmap_lock of one mm is busy every fork() in the system waits
for it:

  A:       mmap(MAP_POPULATE) -> mmap_read_lock(A)
  tracer:  percpu_down_write(&dup_mmap_sem), mmap_write_lock(A) sleeps
  others:  fork() -> percpu_down_read(&dup_mmap_sem) sleeps

Only trylock mmap_lock under dup_mmap_sem. Leave mms with busy mmap_lock in
the list, drop dup_mmap_sem and then wait for them.

dup_mmap_sem makes sure that mm doesn't fork between build_map_info() and
install_breakpoint() or remove_breakpoint(). Otherwise the child misses
the breakpoint, or inherits the breakpoint of uprobe that is gone and gets
SIGTRAP. Now mm in the list can fork. dup_mmap() holds mmap_lock of
the parent, so uprobe_dup_mmap() does what the walk is going to do to this
mm before vmas are copied. The walk sees info->done and skips it.

The error in uprobe_dup_mmap() is the error of the walk, unless fork() is
being killed. Such fork() fails in copy_process() and there is no child, so
leave mm to the walk. With ref_ctr_offset the walk can update the counter
twice in this case.

dup_mmap_sem protects the list of walks. mm in the list is kept by
mm_count. The walk takes mm_users only for the visit, so the process that
exits meanwhile frees its memory.

Busy mms are visited last. The tracer that is killed while it waits for one
of them has installed the breakpoint in all other mms and cannot remove it.
"uprobes: Don't leak the breakpoints if the unregistering task is killed"
fixes that.

Process A loops over mmap(4G, MAP_POPULATE) and munmap(). A and 10 idle
processes map the file. Process B calls fork() in a loop. 32 cpu VM.
Median (max) of 15-25 runs, msec:

                         the longest fork() in B    attach
                         before      after          before  after
 uprobe_multi, 1 uprobe  197 (209)   0.33 (0.70)       210    233
 uprobe_multi, 4 uprobes 421 (429)   0.38 (0.60)      1467   1532
 perf_event, 4 uprobes   422 (439)   0.43 (0.59)      3135   3289

During detach: 264-423 -> 0.35-0.47. Attach and detach still wait for
mmap_lock of A. B doesn't.

The tracer pays when traced processes fork all the time. mm that forks
holds its mmap_lock, so the walk sleeps on many mms in turn. Fork storms of
1200, 2000 and 5000 processes, 6 cpu VM, msec, without and with the series:

 enable uprobe event    105 -> 205   201 -> 481   207 -> 784
 disable uprobe event   225 -> 294   354 -> 579   407 -> 893

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/events/uprobes.c | 178 ++++++++++++++++++++++++++++++++--------
 1 file changed, 143 insertions(+), 35 deletions(-)

diff --git a/kernel/events/uprobes.c b/kernel/events/uprobes.c
index 6792004be6fa..a9274016c55d 100644
--- a/kernel/events/uprobes.c
+++ b/kernel/events/uprobes.c
@@ -1192,8 +1192,29 @@ struct map_info {
 	struct map_info *next;
 	struct mm_struct *mm;
 	unsigned long vaddr;
+	bool done;
 };
 
+/*
+ * Every fork() waits for dup_mmap_sem, so register_for_each_vma() must not
+ * sleep on mmap_lock while it holds dup_mmap_sem. It leaves mms with busy
+ * mmap_lock in ->busy, drops dup_mmap_sem, and only then waits for them.
+ *
+ * Such mm can fork before its turn comes. dup_mmap() holds its mmap_lock, so
+ * uprobe_dup_mmap() does what the walk is going to do to this mm, and
+ * the child has the same breakpoints as the child of mm that wasn't busy.
+ */
+struct uprobe_walk {
+	struct list_head list;
+	struct uprobe *uprobe;
+	struct uprobe_consumer *new;
+	struct map_info *busy;
+	int err;
+};
+
+/* dup_mmap_sem protects the list and ->busy of every walk in it */
+static LIST_HEAD(uprobe_walks);
+
 static inline struct map_info *free_map_info(struct map_info *info)
 {
 	struct map_info *next = info->next;
@@ -1242,6 +1263,7 @@ build_map_info(struct address_space *mapping, loff_t offset, bool is_register)
 
 		info->mm = vma->vm_mm;
 		info->vaddr = offset_to_vaddr(vma, offset);
+		info->done = false;
 	}
 	i_mmap_unlock_read(mapping);
 
@@ -1271,26 +1293,79 @@ build_map_info(struct address_space *mapping, loff_t offset, bool is_register)
 	return curr;
 }
 
-static int
-register_for_each_vma(struct uprobe *uprobe, struct uprobe_consumer *new)
+/*
+ * mmap_lock of info->mm is held for writing. info->done is set under it.
+ * The walk also tests it without mmap_lock, to skip mm.
+ */
+static void register_one_mm(struct uprobe_walk *walk, struct map_info *info,
+			    bool in_fork)
 {
+	struct uprobe_consumer *new = walk->new;
+	struct uprobe *uprobe = walk->uprobe;
+	struct mm_struct *mm = info->mm;
+	struct vm_area_struct *vma;
 	bool is_register = !!new;
-	struct map_info *info;
 	int err = 0;
 
+	if (info->done)
+		return;
+
+	if (is_register && READ_ONCE(walk->err))
+		goto done;
+
+	if (check_stable_address_space(mm))
+		goto done;
+
+	vma = find_vma(mm, info->vaddr);
+	if (!vma || !valid_vma(vma, is_register) ||
+	    file_inode(vma->vm_file) != uprobe->inode)
+		goto done;
+
+	if (vma->vm_start > info->vaddr ||
+	    vaddr_to_offset(vma, info->vaddr) != uprobe->offset)
+		goto done;
+
+	if (is_register) {
+		/* consult only the "caller", new consumer. */
+		if (consumer_filter(new, mm))
+			err = install_breakpoint(uprobe, vma, info->vaddr);
+	} else if (mm_flags_test(MMF_HAS_UPROBES, mm)) {
+		if (!filter_chain(uprobe, mm))
+			err = remove_breakpoint(uprobe, vma, info->vaddr);
+	}
+
+	if (err) {
+		/*
+		 * fork() was killed meanwhile. This is not the error of
+		 * the walk. See uprobe_dup_mmap().
+		 */
+		if (in_fork && fatal_signal_pending(current))
+			return;
+		WRITE_ONCE(walk->err, err);
+	}
+ done:
+	WRITE_ONCE(info->done, true);
+}
+
+static int
+register_for_each_vma(struct uprobe *uprobe, struct uprobe_consumer *new)
+{
+	struct uprobe_walk walk = { .uprobe = uprobe, .new = new };
+	struct map_info *info, *next;
+
 	percpu_down_write(&dup_mmap_sem);
-	info = build_map_info(uprobe->inode->i_mapping,
-					uprobe->offset, is_register);
+	info = build_map_info(uprobe->inode->i_mapping, uprobe->offset, !!new);
 	if (IS_ERR(info)) {
-		err = PTR_ERR(info);
-		goto out;
+		percpu_up_write(&dup_mmap_sem);
+		return PTR_ERR(info);
 	}
 
-	while (info) {
+	for (; info; info = next) {
 		struct mm_struct *mm = info->mm;
-		struct vm_area_struct *vma;
 
-		if (err && is_register)
+		next = info->next;
+		/* If install failed the caller is going to undo it */
+		if (new && walk.err)
 			goto free;
 		/*
 		 * We take mmap_lock for writing to avoid the race with
@@ -1299,38 +1374,56 @@ register_for_each_vma(struct uprobe *uprobe, struct uprobe_consumer *new)
 		 * is_trap_at_addr() true right after find_uprobe_rcu()
 		 * returns NULL in find_active_uprobe_rcu().
 		 */
-		mmap_write_lock(mm);
-		if (check_stable_address_space(mm))
-			goto unlock;
-
-		vma = find_vma(mm, info->vaddr);
-		if (!vma || !valid_vma(vma, is_register) ||
-		    file_inode(vma->vm_file) != uprobe->inode)
-			goto unlock;
-
-		if (vma->vm_start > info->vaddr ||
-		    vaddr_to_offset(vma, info->vaddr) != uprobe->offset)
-			goto unlock;
-
-		if (is_register) {
-			/* consult only the "caller", new consumer. */
-			if (consumer_filter(new, mm))
-				err = install_breakpoint(uprobe, vma, info->vaddr);
-		} else if (mm_flags_test(MMF_HAS_UPROBES, mm)) {
-			if (!filter_chain(uprobe, mm))
-				err |= remove_breakpoint(uprobe, vma, info->vaddr);
+		if (!mmap_write_trylock(mm)) {
+			/*
+			 * uprobe_dup_mmap() compares info->mm until list_del().
+			 * Keep mm_struct, but not the memory of the process.
+			 */
+			mmgrab(mm);
+			mmput_async(mm);
+			info->next = walk.busy;
+			walk.busy = info;
+			continue;
 		}
-
- unlock:
+		register_one_mm(&walk, info, false);
 		mmap_write_unlock(mm);
  free:
 		/* exit_mmap() of the last user must not run under dup_mmap_sem */
 		mmput_async(mm);
-		info = free_map_info(info);
+		kfree(info);
 	}
- out:
+
+	if (!walk.busy) {
+		percpu_up_write(&dup_mmap_sem);
+		return walk.err;
+	}
+
+	list_add(&walk.list, &uprobe_walks);
 	percpu_up_write(&dup_mmap_sem);
-	return err;
+
+	for (info = walk.busy; info; info = info->next) {
+		struct mm_struct *mm = info->mm;
+
+		/* Don't wait for mm if its fork() did it or if install failed */
+		if (READ_ONCE(info->done) || (new && READ_ONCE(walk.err)))
+			continue;
+		/* All users are gone, like in build_map_info() */
+		if (!mmget_not_zero(mm))
+			continue;
+		mmap_write_lock(mm);
+		register_one_mm(&walk, info, false);
+		mmap_write_unlock(mm);
+		mmput(mm);
+	}
+
+	percpu_down_write(&dup_mmap_sem);
+	list_del(&walk.list);
+	percpu_up_write(&dup_mmap_sem);
+
+	for (info = walk.busy; info; info = free_map_info(info))
+		mmdrop(info->mm);
+
+	return walk.err;
 }
 
 /**
@@ -1841,6 +1934,21 @@ void uprobe_end_dup_mmap(void)
 
 void uprobe_dup_mmap(struct mm_struct *oldmm, struct mm_struct *newmm)
 {
+	struct uprobe_walk *walk;
+	struct map_info *info;
+
+	list_for_each_entry(walk, &uprobe_walks, list) {
+		/*
+		 * fork() that is being killed fails in copy_process().
+		 * There will be no child. Leave oldmm to the walk.
+		 */
+		if (fatal_signal_pending(current))
+			break;
+		for (info = walk->busy; info; info = info->next)
+			if (info->mm == oldmm)
+				register_one_mm(walk, info, true);
+	}
+
 	if (mm_flags_test(MMF_HAS_UPROBES, oldmm)) {
 		mm_flags_set(MMF_HAS_UPROBES, newmm);
 		/* unconditionally, dup_mmap() skips VM_DONTCOPY vmas */
-- 
2.55.0