memory ordering in __kfifo primitives

PATCH In review Paul E. McKenney 4 participants 14 messages Aug 10, 2006

lore

Share & tools

lore

Paul E. McKenney

author

2006-08-10 00:18 UTC #0 lore raw

PATCH 1/1 memory ordering in __kfifo primitives

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 <[email protected]>

---

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

kernel/kfifo.c +4 -0

diff -urpNa -X dontdiff linux-2.6.18-rc2/kernel/kfifo.c linux-2.6.18-rc2-kfifo/kernel/kfifo.c
@@ -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;

Andrew Morton

2006-08-10 00:29 UTC #1 lore raw

Quoted 10 lines · On Wed, 9 Aug 2006 17:18:23 -0700 "Paul E. McKenney" <[email protected]> wrote:

kernel/kfifo.c +2 -0

@@ -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;

kernel/kfifo.c unsigned int __kfifo_get(struct kfifo *f · line 170

Quoted 8 lines

kernel/kfifo.c +2 -0

@@ -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.

Paul E. McKenney

author

2006-08-10 00:32 UTC #3 lore raw

In reply to Paul E. McKenney

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 [email protected] 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 [email protected] know that they should take a look at this?

Thanx, Paul

Quoted 30 lines · 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 <[email protected]>
---
 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
kernel/kfifo.c +2 -0
@@ -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;

kernel/kfifo.c unsigned int __kfifo_get(struct kfifo *f · line 170

Quoted 8 lines

kernel/kfifo.c +2 -0

@@ -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;

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,

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.

Paul E. McKenney

author

2006-08-10 01:00 UTC #2 lore raw

In reply to Andrew Morton

Quoted 20 lines · Andrew Morton

Quoted 17 lines · On Wed, 9 Aug 2006 17:18:23 -0700 "Paul E. McKenney" <[email protected]> wrote:

(quoted diff) +4 -0

@@ -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;

Quoted 7 lines

Review unsigned int __kfifo_get(struct kfifo *f · line 170
Quoted 1 line
(quoted diff) +0 -0
 	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 <[email protected]>

---

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

kernel/kfifo.c +28 -0

diff -urpNa -X dontdiff linux-2.6.18-rc2/kernel/kfifo.c linux-2.6.18-rc2-kfifo/kernel/kfifo.c
@@ -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;

Mike Christie

2006-08-10 06:51 UTC #4 lore raw

In reply to Paul E. McKenney

Quoted 5 lines · Paul E. McKenney

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 [email protected] 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.

Quoted 3 lines

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.

Paul E. McKenney

author

2006-08-10 13:40 UTC #5 lore raw

Quoted 10 lines · Mike Christie

Quoted 5 lines · Paul E. McKenney
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 [email protected] 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!

Quoted 7 lines

Quoted 1 line
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

Stelian Pop

2006-08-10 14:26 UTC #6 lore raw

Quoted 9 lines · Paul E. McKenney

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.

Signature · 1 line

Stelian Pop <[email protected]>

Paul E. McKenney

author

2006-08-10 15:38 UTC #7 lore raw

Quoted 8 lines · Stelian Pop

Quoted 6 lines · Paul E. McKenney
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.

Quoted 6 lines

Quoted 3 lines
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.

Quoted 2 lines

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

Stelian Pop

2006-08-10 15:47 UTC #8 lore raw

Quoted 9 lines · Paul E. McKenney

Quoted 8 lines · Stelian Pop
Quoted 6 lines · Paul E. McKenney
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.

Quoted 8 lines

Quoted 6 lines
Quoted 3 lines
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.

Signature · 1 line

Stelian Pop <[email protected]>

Paul E. McKenney

author

2006-08-10 16:10 UTC #9 lore raw

Quoted 14 lines · Stelian Pop

Quoted 13 lines · Paul E. McKenney
Quoted 12 lines · Stelian Pop
Quoted 9 lines · Paul E. McKenney
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()?

Quoted 7 lines

Quoted 4 lines
Quoted 2 lines
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

Stelian Pop

2006-08-10 16:23 UTC #10 lore raw

Quoted 18 lines · Paul E. McKenney

Quoted 17 lines · Stelian Pop
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Stelian Pop
Quoted 9 lines · Paul E. McKenney
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.

Quoted 7 lines

Quoted 4 lines
Quoted 1 line
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.

Quoted 1 line

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.

Signature · 1 line

Stelian Pop <[email protected]>

Paul E. McKenney

author

2006-08-10 16:47 UTC #11 lore raw

Quoted 39 lines · Stelian Pop

Quoted 18 lines · Paul E. McKenney
Quoted 17 lines · Stelian Pop
Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Stelian Pop
Quoted 9 lines · Paul E. McKenney
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.
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
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.
Quoted 1 line
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()

Quoted 4 lines

with the simpler:

	kfifo_alloc(..., &session->lock)
	...
	kfifo_get()

Fair enough!

Quoted 7 lines

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

Agreed!

Quoted 2 lines

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.

Quoted 2 lines

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

Stelian Pop

2006-08-10 20:28 UTC #12 lore raw

[[email protected] bouncing, removed from CC:]

Quoted 5 lines · Paul E. McKenney

Quoted 2 lines
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.

Quoted 6 lines

Quoted 2 lines
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.

Quoted 7 lines

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.

Signature · 1 line

Stelian Pop <[email protected]>

Paul E. McKenney

author

2006-08-10 20:53 UTC #13 lore raw

Quoted 11 lines · Stelian Pop

[[email protected] bouncing, removed from CC:]
Quoted 5 lines · Paul E. McKenney
Quoted 2 lines
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?

Quoted 12 lines

Quoted 12 lines
Quoted 2 lines
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.

Quoted 6 lines

Quoted 1 line
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