Re: [PATCH v5 1/4] qrwlock: A queue read/write lock implementation

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Fri, Nov 08, 2013 at 05:36:12PM -0500, Waiman Long wrote:
> On 11/08/2013 04:11 PM, Paul E. McKenney wrote:
> >On Mon, Nov 04, 2013 at 12:17:17PM -0500, Waiman Long wrote:
> >>Kernel	JPM	%Change from (1)
> >>------	---	----------------
> >>   1	148265		-
> >>   2	238715	       +61%
> >>   3	242048	       +63%
> >>   4	234881	       +58%
> >>
> >>The use of unfair qrwlock provides a small boost of 2%, while using
> >>fair qrwlock leads to 3% decrease of performance. However, looking
> >>at the perf profiles, we can clearly see that other bottlenecks were
> >>constraining the performance improvement.
> >>
> >>Perf profile of kernel (2):
> >>
> >>   18.20%   reaim  [kernel.kallsyms]  [k] __write_lock_failed
> >>    9.36%   reaim  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    2.91%   reaim  [kernel.kallsyms]  [k] mspin_lock
> >>    2.73%   reaim  [kernel.kallsyms]  [k] anon_vma_interval_tree_insert
> >>    2.23%      ls  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    1.29%   reaim  [kernel.kallsyms]  [k] __read_lock_failed
> >>    1.21%    true  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    1.14%   reaim  [kernel.kallsyms]  [k] zap_pte_range
> >>    1.13%   reaim  [kernel.kallsyms]  [k] _raw_spin_lock
> >>    1.04%   reaim  [kernel.kallsyms]  [k] mutex_spin_on_owner
> >>
> >>Perf profile of kernel (3):
> >>
> >>   10.57%   reaim  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    7.98%   reaim  [kernel.kallsyms]  [k] queue_write_lock_slowpath
> >>    5.83%   reaim  [kernel.kallsyms]  [k] mspin_lock
> >>    2.86%      ls  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    2.71%   reaim  [kernel.kallsyms]  [k] anon_vma_interval_tree_insert
> >>    1.52%    true  [kernel.kallsyms]  [k] _raw_spin_lock_irqsave
> >>    1.51%   reaim  [kernel.kallsyms]  [k] queue_read_lock_slowpath
> >>    1.35%   reaim  [kernel.kallsyms]  [k] mutex_spin_on_owner
> >>    1.12%   reaim  [kernel.kallsyms]  [k] zap_pte_range
> >>    1.06%   reaim  [kernel.kallsyms]  [k] perf_event_aux_ctx
> >>    1.01%   reaim  [kernel.kallsyms]  [k] perf_event_aux
> >But wouldn't kernel (4) be the one that was the most highly constrained?
> >
> >(That said, yes, I get that _raw_spin_lock_irqsave() is some lock that
> >is unrelated to the qrwlock.)
> 
> I think the performance data is a bit off as it was collected with a
> previous version that has a minor bug in it. I will rerun the test
> to get the new data.
> 
> >
> >+/**
> >+ * queue_write_can_lock- would write_trylock() succeed?
> >+ * @lock: Pointer to queue rwlock structure
> >+ */
> >+static inline int queue_write_can_lock(struct qrwlock *lock)
> >+{
> >+	union qrwcnts rwcnts;
> >+
> >+	rwcnts.rw = ACCESS_ONCE(lock->cnts.rw);
> >+	return !rwcnts.writer&&  !rwcnts.readers;
> >+}
> >+
> >+/**
> >+ * queue_read_trylock - try to acquire read lock of a queue rwlock
> >+ * @lock : Pointer to queue rwlock structure
> >+ * Return: 1 if lock acquired, 0 if failed
> >+ */
> >+static inline int queue_read_trylock(struct qrwlock *lock)
> >+{
> >+	union qrwcnts cnts;
> >+	u8 wmask;
> >+
> >+	cnts.rw = ACCESS_ONCE(lock->cnts.rw);
> >+	wmask   = cnts.fair ? QW_MASK_FAIR : QW_MASK_UNFAIR;
> >+	if (likely(!(cnts.writer&  wmask))) {
> >+		cnts.rw = xadd(&lock->cnts.rw, QRW_READER_BIAS);
> >On an unfair lock, this can momentarily make queue_read_can_lock() give
> >a false positive.  Not sure that this is a problem -- after all, the
> >return value from queue_read_can_lock() is immediately obsolete anyway.
> 
> Yes, this is an issue. However, I don't this is a big deal as you
> said. Using cmpxchg may avoid this issue, but then their will be a
> fair chance of false collision among readers. So it is probably
> something we may have to live with.
> 
> >>+/**
> >>+ * queue_write_unlock - release write lock of a queue rwlock
> >>+ * @lock : Pointer to queue rwlock structure
> >>+ */
> >>+static inline void queue_write_unlock(struct qrwlock *lock)
> >>+{
> >>+	/*
> >>+	 * Make sure that none of the critical section will be leaked out.
> >>+	 */
> >>+	smp_mb__before_clear_bit();
> >>+	ACCESS_ONCE(lock->cnts.writer) = 0;
> >>+	smp_mb__after_clear_bit();
> >How about the new smp_store_release() for this write?  Looks to me that
> >smp_mb__before_clear_bit() and smp_mb__after_clear_bit() work by accident,
> >if they in fact do work for all architectures.
> 
> Yes, I am thinking about updating the patch to use
> smp_store_release() once it is in. I don't want to create such a
> dependency for this patch yet. Anyway, clearing a bit looks the same
> as clearing a byte to me.
> 
> >>+/*
> >>+ * Compared with regular rwlock, the queue rwlock has has the following
> >>+ * advantages:
> >>+ * 1. It is more deterministic for the fair variant. Even though there is
> >>+ *    a slight chance of stealing the lock if come at the right moment, the
> >>+ *    granting of the lock is mostly in FIFO order. Even the default unfair
> >>+ *    variant is fairer at least among the writers.
> >>+ * 2. It is faster in high contention situation.
> >Sometimes, anyway!  (Referring to your performance results on top of
> >Ingo's patch.)
> 
> Will adjust the wording by adding "usually".
> 
> >
> >+/**
> >+ * wait_in_queue - Add to queue and wait until it is at the head
> >+ * @lock: Pointer to queue rwlock structure
> >+ * @node: Node pointer to be added to the queue
> >+ *
> >+ * The use of smp_wmb() is to make sure that the other CPUs see the change
> >+ * ASAP.
> >+ */
> >+static __always_inline void
> >+wait_in_queue(struct qrwlock *lock, struct qrwnode *node)
> >+{
> >+	struct qrwnode *prev;
> >+
> >+	node->next = NULL;
> >+	node->wait = true;
> >+	prev = xchg(&lock->waitq, node);
> >+	if (prev) {
> >+		prev->next = node;
> >+		smp_wmb();
> >This smp_wmb() desperately needs a comment.  Presumably it is ordering
> >the above "prev->next = node" with some later write, but what write?
> >
> >Oh...  I see the header comment above.
> >
> >Actually, memory barriers don't necessarily make things visible sooner.
> >They are instead used for ordering.  Or did you actually measure a
> >performance increase with this?  (Seems -highly- unlikely given smp_wmb()'s
> >definition on x86...)
> 
> I have some incorrect assumptions about memory barrier. Anyway, this
> issue will be gone once I use the MCS lock/unlock code.

Here is a presentation that has some diagrams that might help:

http://www.rdrop.com/users/paulmck/scalability/paper/Scaling.2013.10.25c.pdf

So, for example, if X and Y are both initially zero:

	CPU 0			CPU 1

	ACCESS_ONCE(X) = 1;	r1 = ACCESS_ONCE(Y);
	smp_wmb();		smp_rmb();
	ACCESS_ONCE(Y) = 1;	r2 = ACCESS_ONCE(X);

Then the two memory barriers enforce a conditional ordering.  The
condition is whether or not CPU 0's store to Y is seen by CPU 1's
load from Y.  If it is, then the pair of memory barriers ensure that
CPU 1's load from X sees the result of CPU 0's store to X.  In other
words, BUG_ON(r1 == 1 && r2 == 0) will never fire.

In general, if a memory access after memory barrier A happens before
a memory access before memory barrier B, then the two memory barriers
will ensure that applicable accesses before memory barrier A happen
before applicable accesses after memory barrier B.

Does that help?

							Thanx, Paul

> >>+		/*
> >>+		 * Wait until the waiting flag is off
> >>+		 */
> >>+		while (ACCESS_ONCE(node->wait))
> >>+			cpu_relax();
> >>+	}
> >>+}
> >>+
> >>+/**
> >>+ * signal_next - Signal the next one in queue to be at the head
> >>+ * @lock: Pointer to queue rwlock structure
> >>+ * @node: Node pointer to the current head of queue
> >>+ */
> >>+static __always_inline void
> >>+signal_next(struct qrwlock *lock, struct qrwnode *node)
> >>+{
> >>+	struct qrwnode *next;
> >>+
> >>+	/*
> >>+	 * Try to notify the next node first without disturbing the cacheline
> >>+	 * of the lock. If that fails, check to see if it is the last node
> >>+	 * and so should clear the wait queue.
> >>+	 */
> >>+	next = ACCESS_ONCE(node->next);
> >>+	if (likely(next))
> >>+		goto notify_next;
> >>+
> >>+	/*
> >>+	 * Clear the wait queue if it is the last node
> >>+	 */
> >>+	if ((ACCESS_ONCE(lock->waitq) == node)&&
> >>+	    (cmpxchg(&lock->waitq, node, NULL) == node))
> >>+			return;
> >>+	/*
> >>+	 * Wait until the next one in queue set up the next field
> >>+	 */
> >>+	while (likely(!(next = ACCESS_ONCE(node->next))))
> >>+		cpu_relax();
> >>+	/*
> >>+	 * The next one in queue is now at the head
> >>+	 */
> >>+notify_next:
> >>+	barrier();
> >>+	ACCESS_ONCE(next->wait) = false;
> >>+	smp_wmb();
> >Because smp_wmb() does not order reads, reads from the critical section
> >could leak out of the critical section.  A full memory barrier (smp_mb())
> >seems necessary to avoid this.
> >
> >Yes, you do have full memory barriers implicit in various atomic operations,
> >but it appears to be possible to avoid them all in some situations.
> 
> Yes, you are right.
> 
> >>+/**
> >>+ * queue_write_3step_lock - acquire write lock in 3 steps
> >>+ * @lock : Pointer to queue rwlock structure
> >>+ * Return: 1 if lock acquired, 0 otherwise
> >>+ *
> >>+ * Step 1 - Try to acquire the lock directly if no reader is present
> >>+ * Step 2 - Set the waiting flag to notify readers that a writer is waiting
> >>+ * Step 3 - When the readers field goes to 0, set the locked flag
> >>+ *
> >>+ * When not in fair mode, the readers actually ignore the second step.
> >>+ * However, this is still necessary to force other writers to fall in line.
> >>+ */
> >>+static __always_inline int queue_write_3step_lock(struct qrwlock *lock)
> >>+{
> >>+	union qrwcnts old, new;
> >>+
> >>+	old.rw = ACCESS_ONCE(lock->cnts.rw);
> >>+
> >>+	/* Step 1 */
> >>+	if (!old.writer&  !old.readers) {
> >>+		new.rw     = old.rw;
> >>+		new.writer = QW_LOCKED;
> >>+		if (likely(cmpxchg(&lock->cnts.rw, old.rw, new.rw) == old.rw))
> >>+			return 1;
> >>+	}
> >>+
> >>+	/* Step 2 */
> >>+	if (old.writer || (cmpxchg(&lock->cnts.writer, 0, QW_WAITING) != 0))
> >>+		return 0;
> >>+
> >>+	/* Step 3 */
> >>+	while (true) {
> >>+		cpu_relax();
> >>+		old.rw = ACCESS_ONCE(lock->cnts.rw);
> >Suppose that there now is a writer, but no readers...
> >
> >>+		if (!old.readers) {
> >>+			new.rw     = old.rw;
> >>+			new.writer = QW_LOCKED;
> >>+			if (likely(cmpxchg(&lock->cnts.rw, old.rw, new.rw)
> >>+				== old.rw))
> >... can't this mistakenly hand out the lock to a second writer?
> >
> >Ah, the trick is that we are at the head of the queue, so the only writer
> >we can possibly contend with is a prior holder of the lock.  Once that
> >writer leaves, no other writer but can appear.  And the QW_WAITING bit
> >prevents new writers from immediately grabbing the lock.
> 
> Yes, that is the point. The current has 2 queue for writers - a one
> position queue in the waiting bit and the MCS locking queue that are
> used by both readers and writers.
> 
> >>+				return 1;
> >>+		}
> >>+	}
> >>+	/* Should never reach here */
> >>+	return 0;
> >>+}
> >>+
> >>+/**
> >>+ * queue_write_lock_slowpath - acquire write lock of a queue rwlock
> >>+ * @lock : Pointer to queue rwlock structure
> >>+ */
> >>+void queue_write_lock_slowpath(struct qrwlock *lock)
> >>+{
> >>+	struct qrwnode node;
> >>+
> >>+	/*
> >>+	 * Put the writer into the wait queue
> >>+	 */
> >>+	wait_in_queue(lock,&node);
> >>+
> >>+	/*
> >>+	 * At the head of the wait queue now, call queue_write_3step_lock()
> >>+	 * to acquire the lock until it is done.
> >>+	 */
> >>+	while (!queue_write_3step_lock(lock))
> >>+		cpu_relax();
> >If we get here, queue_write_3step_lock() just executed a successful
> >cmpxchg(), which implies a full memory barrier.  This prevents the
> >critical section from leaking out, good!
> >
> >>+	signal_next(lock,&node);
> >>+}
> >>+EXPORT_SYMBOL(queue_write_lock_slowpath);
> >>-- 
> >>1.7.1
> >>
> >--
> >To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> >the body of a message to majordomo@vger.kernel.org
> >More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >Please read the FAQ at  http://www.tux.org/lkml/
> 
> Thank for the review.
> 
> -Longman
>