Hi, Stefani,

The sample code is attached with the mail too. If it is necessary, I
can put the sample code into samples/kfifo directory if the basic
idea of the patch is accepted.

Best Regards,
Huang Ying
------------------------------>
This patch add lock-less support for kfifo writer side amongst
different contexts on one CPU, such as NMI, IRQ, soft_irq, process,
etc. This makes kfifo can be used to implement per-CPU lock-less data
structure.

The different contexts on one CPU have some kind of preemption
priority as follow:

process -> soft_irq -> IRQ -> NMI

Where preemption priority increases from left to right. That is, the
right side context can preempt left side context, but not in the
reverse direction, that means the right side context will run to the
end before return to the left side context. The lock-less algorithm
used in the patch take advantage of this.

The algorithm works in reserve/commit style, where "reserve" only
allocate the space, while "commit" really makes the data into buffer,
data is prepared in between. cmpxchg is used in "reserve", this
guarantees different spaces will be allocated for different
contexts. Only the "commit" in lowest context will commit all
allocated spaces. Because all contexts preempting lowest context
between "reserve" and "commit" will run to the end, all data put into
buffer are valid.

Some idea of the lock-less algorithm in the patch comes from Steven
Rostedt's trace ring buffer implementation.

The new xxx_ptr interface and kfifo_iter makes it possible to
write/read content of kfifo in-place in addition to copying out/in.

v2:

- Rebased on 2.6.36

Signed-off-by: Huang Ying <ying.huang@intel.com>
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 include/linux/kfifo.h |  142 ++++++++++++++++++++++++++++++++++++++++++++++++--
 kernel/kfifo.c        |  106 +++++++++++++++++++++++++++++++++++--
 2 files changed, 239 insertions(+), 9 deletions(-)

--- a/include/linux/kfifo.h
+++ b/include/linux/kfifo.h
@@ ...
[ message continues ]

Hi Huang,


The samples use a own implementation of a record handling. Please use

I don't like it, because it handles a very rare use case. The batch is
bloating the code of the fifo API and the macros, so user of this get
also an increase of the code size. most and increase the size of the
kfifo structure. Most of the user, i think more than 99 percent will not
need it.
 
And there a lot of bugs on a first small review.

Your kfifo_skip_len does not handle record fifos. User of kfifo_put,
kfifo_avail will get an increased code size. Your kfifo_is_full isn't
longer working correctly. You did not fixed kfifo_in(), so this function

The regular use case of a fifo is that there is one write and one
reader. In this case, the current implementation of the kfifo structure
is lock less.


I was never CC by a mail where Andi has signed off this patch. It would
be great if i will get some infos why he like it.

But i think you will never get an ACK for this by me, because it bloats
the most-used functions of the hand optimized kfifo API.

Rule number one: do not increase the code size if the functionality is
not needed and used!

BTW: I am in vacation, so it could take some time answering Emails.

- Stefani


--

[ message continues ]

The patch adds only 1 field (unsigned int) to struct __kfifo. I think
that should be acceptable. Because sizeof(struct __kfifo) should be much
smaller that __kfifo->mask + 1 in most cases.

For macros, only INIT_KFIFO, kfifo_reset and kfifo_put is enlarged a
little (one instruction?).

And yes, I added some new functions and macros. But if I implement
another ring buffer instead of making kfifo lock-less (for multiple
writers), I need to implement more functions and macros, the code size

After we reach the consensus on the general idea, we can look at these

I really need multiple-writers and one reader in APEI GHES support, and
I need lock-less in writer side (because the buffer need to be written

There is at least one user. I will post the corresponding patches later.

Best Regards,
Huang Ying


--

[ message continues ]

I don't know what you mean with "because sizeof(struct __kfifo) should
be much smaller that __kfifo->mask + 1 in most cases". I am convinced
that you did not really understand the kfifo code. sizeof(struct
__kfifo) is constant and __kfifo->mask + 1 is the fifo size in elements,
which is not constant. Before you answering study the code first!

And is not acceptable to bload the struct __kfifo, because it will never

No, you add also code to kfifo_avail, so you enlarge two of the most
used macros. And again:

Rule number one - do not increase the code size if the functionality is



I believe you that you need it, but the question is: Is there more users
who need it. And i am sure, there are no more users or very very few.

So for the protocol a big NAK!

- Stefani


--

[ message continues ]

I need to access the record inside kfifo "in-place", so I can not use
the original record implementation. Maybe we can unify the two

I mean, for most user, __kfifo->mask + 1 > sizeof(struct __kfifo), so


Is it good to extend the interface? Maybe there will be other users too.

There will not be many users. So I try to minimize the performance

Sorry to hear this.

Best Regards,
Huang Ying


--

[ message continues ]

You have no idea. As i wrote you should study the code before answering!

sizeof(struct __kfifo) is always 20 bytes on a 32 bit cpu, and
kfifo->mask +1 depends on the size of the number of fifo elements and it
is an initialization parameter. 


If you will be able to shrink the footprint of the struct __kfifo,
whithout wasting the code, you are welcome to do. 

Currently you generate only a lot of hot air. The assertion in your
"number of elements or bytes for kfifo_in etc" thread was also wrong.
You should first study code and understand it.

Until you have can prove your assertion by measurements and working
patches, please stop bothering.

- Stefani


--

[ message continues ]

After my changing, sizeof(struct __kfifo) should be 24 on 32 bit CPU,
that is 4 bytes more. But I think for most users, kfifo->mask + 1 should
be hundreds or thousands. If the average(kfifo->mask + 1) = 256, the
increment percentage for each user is about:

4 / (256 + 20) = 1.45%

So I think the changes to the size of struct __kfifo should be
acceptable.

Best Regards,
Huang Ying


--

[ message continues ]

We really need the lock-less writer side support. So we try to do that
by extending kfifo. But it is clear that you don't like our design and
implementation. Can you help us to design a better protocol for it?

Thanks,
Huang Ying


--

[ message continues ]