From: Jeff Moyer <jmoyer@redhat.com>
Date: Tue, 31 Aug 2010 15:16:37 -0400
Subject: [block] cfq: no merges for queues w/no process references
Message-id: <x494oeax162.fsf@segfault.boston.devel.redhat.com>
Patchwork-id: 27968
O-Subject: [RHEL 5 PATCH] cfq: don't allow merges for queues that have no
	process references
Bugzilla: 605265
RH-Acked-by: Rik van Riel <riel@redhat.com>
RH-Acked-by: Vivek Goyal <vgoyal@redhat.com>

Hi,

This is a backport of the following upstream commit:

commit c10b61f0910466b4b99c266a7d76ac4390743fb5
Author: Jeff Moyer <jmoyer@redhat.com>
Date:   Thu Jun 17 10:19:11 2010 -0400

    cfq: Don't allow queue merges for queues that have no process references

    Hi,

    A user reported a kernel bug when running a particular program that did
    the following:

    created 32 threads
    - each thread took a mutex, grabbed a global offset, added a buffer size
      to that offset, released the lock
    - read from the given offset in the file
    - created a new thread to do the same
    - exited

    The result is that cfq's close cooperator logic would trigger, as the
    threads were issuing I/O within the mean seek distance of one another.
    This workload managed to routinely trigger a use after free bug when
    walking the list of merge candidates for a particular cfqq
    (cfqq->new_cfqq).  The logic used for merging queues looks like this:

    static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
    {
    	int process_refs, new_process_refs;
    	struct cfq_queue *__cfqq;

    	/* Avoid a circular list and skip interim queue merges */
    	while ((__cfqq = new_cfqq->new_cfqq)) {
    		if (__cfqq == cfqq)
    			return;
    		new_cfqq = __cfqq;
    	}

    	process_refs = cfqq_process_refs(cfqq);
    	/*
    	 * If the process for the cfqq has gone away, there is no
    	 * sense in merging the queues.
    	 */
    	if (process_refs == 0)
    		return;

    	/*
    	 * Merge in the direction of the lesser amount of work.
    	 */
    	new_process_refs = cfqq_process_refs(new_cfqq);
    	if (new_process_refs >= process_refs) {
    		cfqq->new_cfqq = new_cfqq;
    		atomic_add(process_refs, &new_cfqq->ref);
    	} else {
    		new_cfqq->new_cfqq = cfqq;
    		atomic_add(new_process_refs, &cfqq->ref);
    	}
    }

    When a merge candidate is found, we add the process references for the
    queue with less references to the queue with more.  The actual merging
    of queues happens when a new request is issued for a given cfqq.  In the
    case of the test program, it only does a single pread call to read in
    1MB, so the actual merge never happens.

    Normally, this is fine, as when the queue exits, we simply drop the
    references we took on the other cfqqs in the merge chain:

    	/*
    	 * If this queue was scheduled to merge with another queue, be
    	 * sure to drop the reference taken on that queue (and others in
    	 * the merge chain).  See cfq_setup_merge and cfq_merge_cfqqs.
    	 */
    	__cfqq = cfqq->new_cfqq;
    	while (__cfqq) {
    		if (__cfqq == cfqq) {
    			WARN(1, "cfqq->new_cfqq loop detected\n");
    			break;
    		}
    		next = __cfqq->new_cfqq;
    		cfq_put_queue(__cfqq);
    		__cfqq = next;
    	}

    However, there is a hole in this logic.  Consider the following (and
    keep in mind that each I/O keeps a reference to the cfqq):

    q1->new_cfqq = q2   // q2 now has 2 process references
    q3->new_cfqq = q2   // q2 now has 3 process references

    // the process associated with q2 exits
    // q2 now has 2 process references

    // queue 1 exits, drops its reference on q2
    // q2 now has 1 process reference

    // q3 exits, so has 0 process references, and hence drops its references
    // to q2, which leaves q2 also with 0 process references

    q4 comes along and wants to merge with q3

    q3->new_cfqq still points at q2!  We follow that link and end up at an
    already freed cfqq.

    So, the fix is to not follow a merge chain if the top-most queue does
    not have a process reference, otherwise any queue in the chain could be
    already freed.  I also changed the logic to disallow merging with a
    queue that does not have any process references.  Previously, we did
    this check for one of the merge candidates, but not the other.  That
    doesn't really make sense.

    Without the attached patch, my system would BUG within a couple of
    seconds of running the reproducer program.  With the patch applied, my
    system ran the program for over an hour without issues.

    This addresses the following bugzilla:
        https://bugzilla.kernel.org/show_bug.cgi?id=16217

    Thanks a ton to Phil Carns for providing the bug report and an excellent
    reproducer.

This address red hat bugzilla #605265.  Comments, as always, are
appreciated.

Cheers,
Jeff

Signed-off-by: Jarod Wilson <jarod@redhat.com>

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 822e8cf..b2ebbbe 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1253,6 +1253,15 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
 	int process_refs, new_process_refs;
 	struct cfq_queue *__cfqq;
 
+	/*
+	 * If there are no process references on the new_cfqq, then it is
+	 * unsafe to follow the ->new_cfqq chain as other cfqq's in the
+	 * chain may have dropped their last reference (not just their
+	 * last process reference).
+	 */
+	if (!cfqq_process_refs(new_cfqq))
+		return;
+
 	/* Avoid a circular list and skip interim queue merges */
 	while ((__cfqq = new_cfqq->new_cfqq)) {
 		if (__cfqq == cfqq)
@@ -1261,17 +1270,17 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
 	}
 
 	process_refs = cfqq_process_refs(cfqq);
+	new_process_refs = cfqq_process_refs(new_cfqq);
 	/*
 	 * If the process for the cfqq has gone away, there is
 	 * no sense in merging the queues.
 	 */
-	if (process_refs == 0)
+	if (process_refs == 0 || new_process_refs == 0)
 		return;
 
 	/*
 	 * Merge in the direction of the lesser amount of work.
 	 */
-	new_process_refs = cfqq_process_refs(new_cfqq);
 	if (new_process_refs >= process_refs) {
 		cfqq->new_cfqq = new_cfqq;
 		atomic_add(process_refs, &new_cfqq->ref);