[PATCH] memory ordering in __kfifo primitives

[PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

Hello!

Both __kfifo_put() and __kfifo_get() have header comments stating
that if there is but one concurrent reader and one concurrent writer,
locking is not necessary.  This is almost the case, but a couple of
memory barriers are needed.  Another option would be to change the
header comments to remove the bit about locking not being needed, and
to change the those callers who currently don't use locking to add
the required locking.  The attachment analyzes this approach, but the
patch below seems simpler.

Signed-off-by: Paul E. McKenney <paulmck@us.ibm.com>
---

 kfifo.c |    4 ++++
 1 files changed, 4 insertions(+)

diff -urpNa -X dontdiff linux-2.6.18-rc2/kernel/kfifo.c linux-2.6.18-rc2-kfifo/kernel/kfifo.c
--- linux-2.6.18-rc2/kernel/kfifo.c	2006-07-15 14:53:08.000000000 -0700
+++ linux-2.6.18-rc2-kfifo/kernel/kfifo.c	2006-08-09 14:01:53.000000000 -0700
@@ -129,6 +129,8 @@ unsigned int __kfifo_put(struct kfifo *f
 	/* then put the rest (if any) at the beginning of the buffer */
 	memcpy(fifo->buffer, buffer + l, len - l);
 
+	smp_wmb();
+
 	fifo->in += len;
 
 	return len;
@@ -161,6 +163,8 @@ unsigned int __kfifo_get(struct kfifo *f
 	/* then get the rest (if any) from the beginning of the buffer */
 	memcpy(buffer + l, fifo->buffer, len - l);
 
+	smp_mb();
+
 	fifo->out += len;
 
 	return len;

Re: [PATCH] memory ordering in __kfifo primitives

[Andrew Morton]

On Wed, 9 Aug 2006 17:18:23 -0700
"Paul E. McKenney" <paulmck@us.ibm.com> wrote:

> @@ -129,6 +129,8 @@ unsigned int __kfifo_put(struct kfifo *f
>  	/* then put the rest (if any) at the beginning of the buffer */
>  	memcpy(fifo->buffer, buffer + l, len - l);
>  
> +	smp_wmb();
> +
>  	fifo->in += len;
>  
>  	return len;
> @@ -161,6 +163,8 @@ unsigned int __kfifo_get(struct kfifo *f
>  	/* then get the rest (if any) from the beginning of the buffer */
>  	memcpy(buffer + l, fifo->buffer, len - l);
>  
> +	smp_mb();
> +
>  	fifo->out += len;
>  
>  	return len;

When adding barriers, please also add a little comment explaining what the
barrier is protecting us from.

Often it's fairly obvious, but sometimes it is not, and in both cases it is still
useful to communicate the programmer's intent in this way.

Thanks.

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

[-- Attachment #1: Type: text/plain, Size: 1976 bytes --]

OK, it appears that we are even.  I forgot to attach the promised
analysis of the callers to __kfifo_put() and __kfifo_get(), and
the open-iscsi@googlegroups.com email address listed as maintainer
in drivers/scsi/libiscsi.c bounces complaining that, as a non-member,
I am not allowed to send it email.  ;-)

Anyway, this time the analysis really is attached, sorry for my confusion!

Could someone please let the guys on open-iscsi@googlegroups.com know
that they should take a look at this?

						Thanx, Paul

On Wed, Aug 09, 2006 at 05:18:23PM -0700, Paul E. McKenney wrote:
> Hello!
> 
> Both __kfifo_put() and __kfifo_get() have header comments stating
> that if there is but one concurrent reader and one concurrent writer,
> locking is not necessary.  This is almost the case, but a couple of
> memory barriers are needed.  Another option would be to change the
> header comments to remove the bit about locking not being needed, and
> to change the those callers who currently don't use locking to add
> the required locking.  The attachment analyzes this approach, but the
> patch below seems simpler.
> 
> Signed-off-by: Paul E. McKenney <paulmck@us.ibm.com>
> ---
> 
>  kfifo.c |    4 ++++
>  1 files changed, 4 insertions(+)
> 
> diff -urpNa -X dontdiff linux-2.6.18-rc2/kernel/kfifo.c linux-2.6.18-rc2-kfifo/kernel/kfifo.c
> --- linux-2.6.18-rc2/kernel/kfifo.c	2006-07-15 14:53:08.000000000 -0700
> +++ linux-2.6.18-rc2-kfifo/kernel/kfifo.c	2006-08-09 14:01:53.000000000 -0700
> @@ -129,6 +129,8 @@ unsigned int __kfifo_put(struct kfifo *f
>  	/* then put the rest (if any) at the beginning of the buffer */
>  	memcpy(fifo->buffer, buffer + l, len - l);
>  
> +	smp_wmb();
> +
>  	fifo->in += len;
>  
>  	return len;
> @@ -161,6 +163,8 @@ unsigned int __kfifo_get(struct kfifo *f
>  	/* then get the rest (if any) from the beginning of the buffer */
>  	memcpy(buffer + l, fifo->buffer, len - l);
>  
> +	smp_mb();
> +
>  	fifo->out += len;
>  
>  	return len;

[-- Attachment #2: kfifo.txt --]
[-- Type: text/plain, Size: 6922 bytes --]

drivers/scsi/iscsi_tcp.c iscsi_r2t_rsp 377 rc = __kfifo_get(tcp_ctask->r2tpool.queue, (void *)&r2t, sizeof(void *));

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c handle_xmstate_sol_data 1718 if (__kfifo_get(tcp_ctask->r2tqueue, (void *)&r2t, sizeof(void *))) {

	Not covered by session->lock.

drivers/scsi/iscsi_tcp.c iscsi_tcp_ctask_xmit 1839 __kfifo_get(tcp_ctask->r2tqueue, (void *)&tcp_ctask->r2t,

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c iscsi_tcp_cleanup_ctask 2011 while (__kfifo_get(tcp_ctask->r2tqueue, (void *)&r2t, sizeof(void *)))

	Covered by session->lock, at least according to the comments.
	(called by iscsi_tcp_cleanup_ctask(), which is called by
	things invoking the cleanup_cmd_task function pointer, which
	is invoked by fail_command(), which has a header comment
	demanding that session->lock be held by callers.

drivers/scsi/libiscsi.c iscsi_data_xmit 556 while (__kfifo_get(conn->immqueue, (void *)&conn->mtask,

	Not covered by session->lock.

drivers/scsi/libiscsi.c iscsi_data_xmit 571 while (__kfifo_get(conn->xmitqueue, (void *)&conn->ctask,

	Not covered by session->lock.

drivers/scsi/libiscsi.c iscsi_data_xmit 590 while (__kfifo_get(conn->mgmtqueue, (void *)&conn->mtask,

	Not covered by session->lock.

drivers/scsi/libiscsi.c iscsi_data_xmit 690 __kfifo_get(session->cmdpool.queue, (void *)&ctask, sizeof(void *));

	Covered by session->lock.

drivers/scsi/libiscsi.c iscsi_conn_send_generic 766 if (!__kfifo_get(session->mgmtpool.queue,

	Covered by session->lock.

drivers/scsi/libiscsi.c iscsi_remove_task 990 __kfifo_get(fifo, (void *)&task, sizeof(void *)); \

	Macro that expands to iscsi_remove_mgmt_task() and
	iscsi_remove_cmd_task()

	o	iscsi_remove_mgmt_task called from iscsi_ctask_mtask_cleanup,
		which in turn is called from fail_command() and 
		iscsi_eh_abort().

		o	fail_command() comment indicates that session
			lock must be held.

		o	iscsi_eh_abort() has the session lock held.

	o	iscsi_remove_cmd_task() called from iscsi_eh_abort(),
		which again has the session lock held.

drivers/scsi/libiscsi.c iscsi_conn_setup 1386 if (!__kfifo_get(session->mgmtpool.queue,

	Covered by session->lock.

drivers/scsi/libiscsi.c flush_control_queues 1546 while (__kfifo_get(conn->immqueue, (void *)&mtask, sizeof(void *)) ||

	Covered by session->lock.  (Held by caller
	iscsi_start_session_recovery().)

drivers/scsi/libiscsi.c flush_control_queues 1547 __kfifo_get(conn->mgmtqueue, (void *)&mtask, sizeof(void *))) {

	Covered by session->lock.  (Held by caller
	iscsi_start_session_recovery().)

drivers/scsi/libiscsi.c fail_all_commands 1575 while (__kfifo_get(conn->xmitqueue, (void *)&ctask, sizeof(void *))) {

	Covered by session->lock.

include/linux/kfifo.h kfifo_get 113 ret = __kfifo_get(fifo, buffer, len);

	Covered by fifo->lock.

kernel/kfifo.c __kfifo_get 150 unsigned int __kfifo_get(struct kfifo *fifo,

	Covered by fifo->lock.

drivers/infiniband/ulp/iser/iser_initiator.c iser_snd_completion 674 __kfifo_put(session->mgmtpool.queue, (void *)&mtask,

	Covered by conn->session->lock.  But I have no idea what
	consumes the resulting message -- my guess is that it is
	actually going down to iscsi, based on the
	"conn = iser_conn->iscsi_conn" earlier in this function.

drivers/scsi/iscsi_tcp.c iscsi_r2t_rsp 401 __kfifo_put(tcp_ctask->r2tqueue, (void *)&r2t, sizeof(void *));

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c iscsi_r2t_rsp 402 __kfifo_put(conn->xmitqueue, (void *)&ctask, sizeof(void *));

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c iscsi_tcp_mtask_xmit 1388 __kfifo_put(session->mgmtpool.queue, (void *)&conn->mtask,

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c handle_xmstate_sol_data 1716 __kfifo_put(tcp_ctask->r2tpool.queue, (void *)&r2t, sizeof(void *));

	Covered by session->lock.

drivers/scsi/iscsi_tcp.c iscsi_tcp_cleanup_ctask 2012 __kfifo_put(tcp_ctask->r2tpool.queue, (void *)&r2t,

	Covered by session->lock, at least according to the comments.
	(called by iscsi_tcp_cleanup_ctask(), which is called by
	things invoking the cleanup_cmd_task function pointer, which
	is invoked by fail_command(), which has a header comment
	demanding that session->lock be held by callers.

drivers/scsi/libiscsi.c iscsi_complete_command 194 __kfifo_put(session->cmdpool.queue, (void *)&ctask, sizeof(void *));

	Covered by session->lock, or at least the header comment claims
	that it should be called under this lock.

drivers/scsi/libiscsi.c __iscsi_complete_pdu 354 __kfifo_put(session->mgmtpool.queue,

	Covered by session->lock by all in-tree calls, but is an
	exported symbol.

drivers/scsi/libiscsi.c __iscsi_complete_pdu 384 __kfifo_put(session->mgmtpool.queue,

	Covered by session->lock by all in-tree calls, but is an
	exported symbol.

drivers/scsi/libiscsi.c __iscsi_complete_pdu 703 __kfifo_put(conn->xmitqueue, (void *)&ctask, sizeof(void *));

	Covered by session->lock by all in-tree calls, but is an
	exported symbol.

drivers/scsi/libiscsi.c iscsi_conn_send_generic 808 __kfifo_put(conn->immqueue, (void *)&mtask, sizeof(void *));

	Not covered by session->lock.

drivers/scsi/libiscsi.c iscsi_conn_send_generic 810 __kfifo_put(conn->mgmtqueue, (void *)&mtask, sizeof(void *));

	Not covered by session->lock.

drivers/scsi/libiscsi.c iscsi_remove_task 998 __kfifo_put(fifo, (void *)&task, sizeof(void *)); \

	Covered by session->lock, analysis is the same as for the
	earlier occurrence of iscsi_remove_task().

drivers/scsi/libiscsi.c iscsi_ctask_mtask_cleanup 1016 __kfifo_put(session->mgmtpool.queue, (void *)&ctask->mtask,

	Called from fail_command(), which has a header comment claiming
	that session->lock must be held, and from iscsi_eh_abort(),
	which has session->lock held.

drivers/scsi/libiscsi.c iscsi_eh_abort 1082 __kfifo_put(conn->xmitqueue, (void *)&pending_ctask,

	Covered by session->lock.

drivers/scsi/libiscsi.c iscsi_pool_init 1175 __kfifo_put(q->queue, (void *)&q->pool[i], sizeof(void *));

	Looks like initialization code, where no-one else would have
	a reference to the kfifo, so should be OK.

drivers/scsi/libiscsi.c iscsi_conn_setup 1406 __kfifo_put(session->mgmtpool.queue, (void *)&conn->login_mtask,

	Not covered by session->lock, despite other __kfifo operations
	being covered by this lock elsewhere in this function.

drivers/scsi/libiscsi.c iscsi_conn_teardown 1478 __kfifo_put(session->mgmtpool.queue, (void *)&conn->login_mtask,

	Covered by session->lock.

drivers/scsi/libiscsi.c flush_control_queues 1551 __kfifo_put(session->mgmtpool.queue, (void *)&mtask,

	Covered by session->lock.  (Held by caller
	iscsi_start_session_recovery().)

drivers/scsi/libiscsi.c flush_control_queues 1562 __kfifo_put(session->mgmtpool.queue, (void *)&mtask,

	Covered by session->lock.  (Held by caller
	iscsi_start_session_recovery().)

include/linux/kfifo.h kfifo_put 89 ret = __kfifo_put(fifo, buffer, len);

	Covered by fifo->lock.

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Wed, Aug 09, 2006 at 05:29:10PM -0700, Andrew Morton wrote:
> On Wed, 9 Aug 2006 17:18:23 -0700
> "Paul E. McKenney" <paulmck@us.ibm.com> wrote:
> 
> > @@ -129,6 +129,8 @@ unsigned int __kfifo_put(struct kfifo *f
> >  	/* then put the rest (if any) at the beginning of the buffer */
> >  	memcpy(fifo->buffer, buffer + l, len - l);
> >  
> > +	smp_wmb();
> > +
> >  	fifo->in += len;
> >  
> >  	return len;
> > @@ -161,6 +163,8 @@ unsigned int __kfifo_get(struct kfifo *f
> >  	/* then get the rest (if any) from the beginning of the buffer */
> >  	memcpy(buffer + l, fifo->buffer, len - l);
> >  
> > +	smp_mb();
> > +
> >  	fifo->out += len;
> >  
> >  	return len;
> 
> When adding barriers, please also add a little comment explaining what the
> barrier is protecting us from.
> 
> Often it's fairly obvious, but sometimes it is not, and in both cases it is still
> useful to communicate the programmer's intent in this way.

I certainly cannot claim that it was obvious in this case, as the act
of adding the comments caused me to realize that I had added only two
of the four memory barriers that are required.  :-/  Updated patch below.

Signed-off-by: Paul E. McKenney <paulmck@us.ibm.com>
---

 kfifo.c |   28 ++++++++++++++++++++++++++++
 1 files changed, 28 insertions(+)

diff -urpNa -X dontdiff linux-2.6.18-rc2/kernel/kfifo.c linux-2.6.18-rc2-kfifo/kernel/kfifo.c
--- linux-2.6.18-rc2/kernel/kfifo.c	2006-07-15 14:53:08.000000000 -0700
+++ linux-2.6.18-rc2-kfifo/kernel/kfifo.c	2006-08-09 17:45:41.000000000 -0700
@@ -122,6 +122,13 @@ unsigned int __kfifo_put(struct kfifo *f
 
 	len = min(len, fifo->size - fifo->in + fifo->out);
 
+	/*
+	 * Ensure that we sample the fifo->out index -before- we
+	 * start putting bytes into the kfifo.
+	 */
+
+	smp_mb();
+
 	/* first put the data starting from fifo->in to buffer end */
 	l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
 	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
@@ -129,6 +136,13 @@ unsigned int __kfifo_put(struct kfifo *f
 	/* then put the rest (if any) at the beginning of the buffer */
 	memcpy(fifo->buffer, buffer + l, len - l);
 
+	/*
+	 * Ensure that we add the bytes to the kfifo -before-
+	 * we update the fifo->in index.
+	 */
+
+	smp_wmb();
+
 	fifo->in += len;
 
 	return len;
@@ -154,6 +168,13 @@ unsigned int __kfifo_get(struct kfifo *f
 
 	len = min(len, fifo->in - fifo->out);
 
+	/*
+	 * Ensure that we sample the fifo->in index -before- we
+	 * start removing bytes from the kfifo.
+	 */
+
+	smp_rmb();
+
 	/* first get the data from fifo->out until the end of the buffer */
 	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
 	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
@@ -161,6 +182,13 @@ unsigned int __kfifo_get(struct kfifo *f
 	/* then get the rest (if any) from the beginning of the buffer */
 	memcpy(buffer + l, fifo->buffer, len - l);
 
+	/*
+	 * Ensure that we remove the bytes from the kfifo -before-
+	 * we update the fifo->out index.
+	 */
+
+	smp_mb();
+
 	fifo->out += len;
 
 	return len;

Re: [PATCH] memory ordering in __kfifo primitives

[Mike Christie]

Paul E. McKenney wrote:
> OK, it appears that we are even.  I forgot to attach the promised
> analysis of the callers to __kfifo_put() and __kfifo_get(), and
> the open-iscsi@googlegroups.com email address listed as maintainer
> in drivers/scsi/libiscsi.c bounces complaining that, as a non-member,
> I am not allowed to send it email.  ;-)

Sorry about that. I do not have any control over the email list. I will
change the maintainer info entry to indicate that users should just send
mail to me or linux-scsi.

> 
> Anyway, this time the analysis really is attached, sorry for my confusion!
> 

We have change the code a little since the analysis was made. But, it
does not really matter much now. I am fine with us just grabbing the
session lock or xmitmitex (I will send a patch and test it as well) if
your barrier patch is not accepted. We grab the session lock in the fast
path now so there is not much benefit left for us.

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Thu, Aug 10, 2006 at 01:48:02AM -0400, Mike Christie wrote:
> Paul E. McKenney wrote:
> > OK, it appears that we are even.  I forgot to attach the promised
> > analysis of the callers to __kfifo_put() and __kfifo_get(), and
> > the open-iscsi@googlegroups.com email address listed as maintainer
> > in drivers/scsi/libiscsi.c bounces complaining that, as a non-member,
> > I am not allowed to send it email.  ;-)
> 
> Sorry about that. I do not have any control over the email list. I will
> change the maintainer info entry to indicate that users should just send
> mail to me or linux-scsi.

Sounds good!

> > Anyway, this time the analysis really is attached, sorry for my confusion!
> 
> We have change the code a little since the analysis was made. But, it
> does not really matter much now. I am fine with us just grabbing the
> session lock or xmitmitex (I will send a patch and test it as well) if
> your barrier patch is not accepted. We grab the session lock in the fast
> path now so there is not much benefit left for us.

I am happy to go either way -- the patch with the memory barriers
(which does have the side-effect of slowing down kfifo_get() and
kfifo_put(), by the way), or a patch removing the comments saying
that it is OK to invoke __kfifo_get() and __kfifo_put() without
locking.

Any other thoughts on which is better?  (1) the memory barriers or
(2) requiring the caller hold appropriate locks across calls to
__kfifo_get() and __kfifo_put()?

							Thanx, Paul

Re: [PATCH] memory ordering in __kfifo primitives

[Stelian Pop]

Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :

> I am happy to go either way -- the patch with the memory barriers
> (which does have the side-effect of slowing down kfifo_get() and
> kfifo_put(), by the way), or a patch removing the comments saying
> that it is OK to invoke __kfifo_get() and __kfifo_put() without
> locking.
> 
> Any other thoughts on which is better?  (1) the memory barriers or
> (2) requiring the caller hold appropriate locks across calls to
> __kfifo_get() and __kfifo_put()?

If someone wants to use explicit locking, he/she can go with kfifo_get()
instead of the __ version.

I'd rather keep the __kfifo_get() and __kfifo_put() functions lockless,
so I say go for (1) even if there is a tiny price to pay for corectness.

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> 
> > I am happy to go either way -- the patch with the memory barriers
> > (which does have the side-effect of slowing down kfifo_get() and
> > kfifo_put(), by the way), or a patch removing the comments saying
> > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > locking.
> > 
> > Any other thoughts on which is better?  (1) the memory barriers or
> > (2) requiring the caller hold appropriate locks across calls to
> > __kfifo_get() and __kfifo_put()?
> 
> If someone wants to use explicit locking, he/she can go with kfifo_get()
> instead of the __ version.

However, the kfifo_get()/kfifo_put() interfaces use the internal lock,
which cannot be used by the caller to protect other code surrounding
the call to kfifo_get()/kfifo_put().  See for example the ISCSI use,
where they have a session->lock that, among other things, protects their
__kfifo_get()/__kfifo_put() calls.

> I'd rather keep the __kfifo_get() and __kfifo_put() functions lockless,
> so I say go for (1) even if there is a tiny price to pay for corectness.

If we require the caller to supply the locks for __kfifo_get() and
__kfifo_put(), then we have -both- correctness -and- better performance.
And the only current user of __kfifo_get()/__kfifo_put() stated that
they could easily expand their session->lock to cover all such calls,
and that doing so would not hurt their performance.

So, are you sure?  And if so, why?

						Thanx, Paul

Re: [PATCH] memory ordering in __kfifo primitives

[Stelian Pop]

Le jeudi 10 août 2006 à 08:39 -0700, Paul E. McKenney a écrit :
> On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> > Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> > 
> > > I am happy to go either way -- the patch with the memory barriers
> > > (which does have the side-effect of slowing down kfifo_get() and
> > > kfifo_put(), by the way), or a patch removing the comments saying
> > > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > > locking.
> > > 
> > > Any other thoughts on which is better?  (1) the memory barriers or
> > > (2) requiring the caller hold appropriate locks across calls to
> > > __kfifo_get() and __kfifo_put()?
> > 
> > If someone wants to use explicit locking, he/she can go with kfifo_get()
> > instead of the __ version.
> 
> However, the kfifo_get()/kfifo_put() interfaces use the internal lock,

... and the internal lock can be supplied by the user at kfifo_alloc()
time.

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Thu, Aug 10, 2006 at 05:47:22PM +0200, Stelian Pop wrote:
> Le jeudi 10 août 2006 à 08:39 -0700, Paul E. McKenney a écrit :
> > On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> > > Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> > > 
> > > > I am happy to go either way -- the patch with the memory barriers
> > > > (which does have the side-effect of slowing down kfifo_get() and
> > > > kfifo_put(), by the way), or a patch removing the comments saying
> > > > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > > > locking.
> > > > 
> > > > Any other thoughts on which is better?  (1) the memory barriers or
> > > > (2) requiring the caller hold appropriate locks across calls to
> > > > __kfifo_get() and __kfifo_put()?
> > > 
> > > If someone wants to use explicit locking, he/she can go with kfifo_get()
> > > instead of the __ version.
> > 
> > However, the kfifo_get()/kfifo_put() interfaces use the internal lock,
> 
> ... and the internal lock can be supplied by the user at kfifo_alloc()
> time.

Would that really work for them?  Looks to me like it would result
in self-deadlock if they passed in session->lock.

Or did you have something else in mind for them?

These are the __kfifo_get() and __kfifo_put() uses in:

	drivers/scsi/iscsi_tcp.c
	drivers/scsi/libiscsi.c
	drivers/infiniband/ulp/iser/iser_initiator.c

							Thanx, Paul

Re: [PATCH] memory ordering in __kfifo primitives

[Stelian Pop]

Le jeudi 10 août 2006 à 09:11 -0700, Paul E. McKenney a écrit :
> On Thu, Aug 10, 2006 at 05:47:22PM +0200, Stelian Pop wrote:
> > Le jeudi 10 août 2006 à 08:39 -0700, Paul E. McKenney a écrit :
> > > On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> > > > Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> > > > 
> > > > > I am happy to go either way -- the patch with the memory barriers
> > > > > (which does have the side-effect of slowing down kfifo_get() and
> > > > > kfifo_put(), by the way), or a patch removing the comments saying
> > > > > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > > > > locking.
> > > > > 
> > > > > Any other thoughts on which is better?  (1) the memory barriers or
> > > > > (2) requiring the caller hold appropriate locks across calls to
> > > > > __kfifo_get() and __kfifo_put()?
> > > > 
> > > > If someone wants to use explicit locking, he/she can go with kfifo_get()
> > > > instead of the __ version.
> > > 
> > > However, the kfifo_get()/kfifo_put() interfaces use the internal lock,
> > 
> > ... and the internal lock can be supplied by the user at kfifo_alloc()
> > time.
> 
> Would that really work for them?  Looks to me like it would result
> in self-deadlock if they passed in session->lock.

Yeah, it will deadlock if the lock is already taken before calling
__kfifo_get and __kfifo_put.

> Or did you have something else in mind for them?

What I had in mind is to replace all occurences of:
	kfifo_alloc(..., NULL);
	...
	spin_lock(&session->lock)
	__kfifo_get()
	spin_unlock()

with the simpler:
	kfifo_alloc(..., &session->lock)
	...
	kfifo_get()

As for the occurences of:
	...
	spin_lock(&session->lock)
	do_something();
	__kifo_get();

well, there is not much we can do about them...

Let's take this problem differently: is a memory barrier cheaper than a
spinlock ? 

If the answer is yes as I suspect, why should the kfifo API force the
user to take a spinlock ?

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Thu, Aug 10, 2006 at 06:23:04PM +0200, Stelian Pop wrote:
> Le jeudi 10 août 2006 à 09:11 -0700, Paul E. McKenney a écrit :
> > On Thu, Aug 10, 2006 at 05:47:22PM +0200, Stelian Pop wrote:
> > > Le jeudi 10 août 2006 à 08:39 -0700, Paul E. McKenney a écrit :
> > > > On Thu, Aug 10, 2006 at 04:26:53PM +0200, Stelian Pop wrote:
> > > > > Le jeudi 10 août 2006 à 06:41 -0700, Paul E. McKenney a écrit :
> > > > > 
> > > > > > I am happy to go either way -- the patch with the memory barriers
> > > > > > (which does have the side-effect of slowing down kfifo_get() and
> > > > > > kfifo_put(), by the way), or a patch removing the comments saying
> > > > > > that it is OK to invoke __kfifo_get() and __kfifo_put() without
> > > > > > locking.
> > > > > > 
> > > > > > Any other thoughts on which is better?  (1) the memory barriers or
> > > > > > (2) requiring the caller hold appropriate locks across calls to
> > > > > > __kfifo_get() and __kfifo_put()?
> > > > > 
> > > > > If someone wants to use explicit locking, he/she can go with kfifo_get()
> > > > > instead of the __ version.
> > > > 
> > > > However, the kfifo_get()/kfifo_put() interfaces use the internal lock,
> > > 
> > > ... and the internal lock can be supplied by the user at kfifo_alloc()
> > > time.
> > 
> > Would that really work for them?  Looks to me like it would result
> > in self-deadlock if they passed in session->lock.
> 
> Yeah, it will deadlock if the lock is already taken before calling
> __kfifo_get and __kfifo_put.
> 
> > Or did you have something else in mind for them?
> 
> What I had in mind is to replace all occurences of:
> 	kfifo_alloc(..., NULL);
> 	...
> 	spin_lock(&session->lock)
> 	__kfifo_get()
> 	spin_unlock()
> 
> with the simpler:
> 	kfifo_alloc(..., &session->lock)
> 	...
> 	kfifo_get()

Fair enough!

> As for the occurences of:
> 	...
> 	spin_lock(&session->lock)
> 	do_something();
> 	__kifo_get();
> 
> well, there is not much we can do about them...

Agreed!

> Let's take this problem differently: is a memory barrier cheaper than a
> spinlock ? 

Almost always, yes.  But a spinlock is cheaper than a spinlock plus
a pair of memory barriers.

> If the answer is yes as I suspect, why should the kfifo API force the
> user to take a spinlock ?

My concern is that currently a majority of the calls to __kfifo_{get,put}()
are already holding a spinlock.

But if you could send me your tests for lock-free __kfifo_{get,put}(),
I would be happy to run them on weak-memory-consistency model machines
with the memory barriers.  And without the memory barriers -- we need
a test that fails in the latter case to prove that the memory barriers
really are in the right place and that all of them are present.

Does this sound reasonable?

						Thanx, Paul

Re: [PATCH] memory ordering in __kfifo primitives

[Stelian Pop]

[open-iscsi@googlegroups.com bouncing, removed from CC:]

Le jeudi 10 août 2006 à 09:47 -0700, Paul E. McKenney a écrit :

> > Let's take this problem differently: is a memory barrier cheaper than a
> > spinlock ? 
> 
> Almost always, yes.  But a spinlock is cheaper than a spinlock plus
> a pair of memory barriers.

Right, but I think we're optimizing too much here. 

> > If the answer is yes as I suspect, why should the kfifo API force the
> > user to take a spinlock ?
> 
> My concern is that currently a majority of the calls to __kfifo_{get,put}()
> are already holding a spinlock.
> 
> But if you could send me your tests for lock-free __kfifo_{get,put}(),
> I would be happy to run them on weak-memory-consistency model machines
> with the memory barriers.  And without the memory barriers -- we need
> a test that fails in the latter case to prove that the memory barriers
> really are in the right place and that all of them are present.
> 
> Does this sound reasonable?

It would sound reasonable if I had any tests to send to you :)

Since I don't have any and since you're the one proposing the change, I
guess it's up to you to write them. :)

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [PATCH] memory ordering in __kfifo primitives

[Paul E. McKenney]

On Thu, Aug 10, 2006 at 10:27:42PM +0200, Stelian Pop wrote:
> [open-iscsi@googlegroups.com bouncing, removed from CC:]
> 
> Le jeudi 10 août 2006 à 09:47 -0700, Paul E. McKenney a écrit :
> 
> > > Let's take this problem differently: is a memory barrier cheaper than a
> > > spinlock ? 
> > 
> > Almost always, yes.  But a spinlock is cheaper than a spinlock plus
> > a pair of memory barriers.
> 
> Right, but I think we're optimizing too much here. 

That was in fact my point initially -- why not just require locking,
either that registered at kfifo_alloc() time or a separately acquired
lock?

> > > If the answer is yes as I suspect, why should the kfifo API force the
> > > user to take a spinlock ?
> > 
> > My concern is that currently a majority of the calls to __kfifo_{get,put}()
> > are already holding a spinlock.
> > 
> > But if you could send me your tests for lock-free __kfifo_{get,put}(),
> > I would be happy to run them on weak-memory-consistency model machines
> > with the memory barriers.  And without the memory barriers -- we need
> > a test that fails in the latter case to prove that the memory barriers
> > really are in the right place and that all of them are present.
> > 
> > Does this sound reasonable?
> 
> It would sound reasonable if I had any tests to send to you :)
> 
> Since I don't have any and since you're the one proposing the change, I
> guess it's up to you to write them. :)

Ah, but you owe a test debt from your earlier submission of kfifo!  ;-)

						Thanx, Paul