Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:
> On Tue, Oct 30, 2012 at 11:52:10PM -0700, Andrew Morton wrote:
> > On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stef...@seibold.net>
> > wrote:
> >
> > > > Yes, and I guess the same to give them a 64-element one.
> > > >
> > > > >
> > > > > If there's absolutely no prospect that the kfifo code will ever
> > > > > support
> > > > > 100-byte fifos then I guess we should rework the API so that the
> > > > > caller
> > > > > has to pass in log2 of the size, not the size itself. That way there
> > > > > will be no surprises and no mistakes.
> > > > >
> > > > > That being said, the power-of-2 limitation isn't at all intrinsic to a
> > > > > fifo, so we shouldn't do this. Ideally, we'd change the kfifo
> > > > > implementation so it does what the caller asked it to do!
> > > >
> > > > I'm fine with removing the power-of-2 limitation. Stefani, what's your
> > > > comment on that?
> > > >
> > >
> > > You can't remove the power-of-2-limitation, since this would result in a
> > > performance decrease (bit wise and vs. modulo operation).
> >
> > Probably an insignificant change in performance.
> >
> > It could be made much smaller by just never doing the modulus operation
> > - instead do
> >
> > if (++index == max)
> > index = 0;
> >
> > this does introduce one problem: it's no longer possible to distinguish
> > the "full" and "empty" states by comparing the head and tail indices.
> > But that is soluble.
>
> Hi Andrew,
>
> Yes, it is soluble. How about the following solution?
>
> Add 2 more fields(in_off and out_off) in __kfifo structure, so that in
> and out will keep increasing each time, while in_off and out_off will be
> wrapped to head if goes to the end of fifo buffer.
>
> So, we can use in and out for counting unused space, and distinguish the
> "full" and "empty" state, and also, of course no need for locking.
>
> Stefani, sorry for quite late reply. I checked all the code used kfifo_alloc
> and kfifo_init. Firstly, there are a lot of users ;-)
>
> And secondly, I did find some examples used kfifo as it supports
> none-power-of-2 kfifo. Say, the one at drivers/hid/hid-logitech-dj.c:
> if (kfifo_alloc(&djrcv_dev->notif_fifo,
> DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report),
> GFP_KERNEL)) {
>
> which means it wants to allocate a kfifo buffer which can store
> DJ_MAX_NUMBER_NOTIFICATIONS(8 here) dj_report(each 15 bytes) at once.
>
> And DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report) = 8 * 15.
> Then current code would allocate a size of rounddown_power_of_2(120) =
> 64 bytes, which can hold 4 dj_report only once, which is a half of expected.
>
This will go away with a log API.
> There are few more examples like this.
>
> And, kfifo_init used a pre-allocated buffer, it would be a little strange
> to ask user to pre-allocate a power of 2 size aligned buffer.
>
> So, I guess it's would be good to support none-power-of-2 kfifo?
>
> I know you care the performance a lot. Well, as Andrew said, it may
> introduce a little insignificant drop(no modulus, few more add/dec).
> Thus, do you have some benchmarks for that? I can have a test to check
> if it is a insignificant change on performance or not :)
>
Dirty, Ugly, Hacky and this will produce a lot of overhead, especially
for kfifo_put and kfifo_get which are inlined code.
In the kernel world it was always a regular use case to use power-of-2
restricted API's, f.e. the slab cache.
I see no benefit for a none-power-of-2 kfifo, only drawbacks.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
