linux-kernel - Re: [RFC 0/2] new kfifo API

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <200908041424.54472.arnd@arndb.de>
Date:	Tue, 4 Aug 2009 14:24:54 +0200
From:	Arnd Bergmann <arnd@...db.de>
To:	Stefani Seibold <stefani@...bold.net>
Cc:	"linux-kernel" <linux-kernel@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [RFC 0/2] new kfifo API

On Monday 03 August 2009, Stefani Seibold wrote:
> Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
> 
> DECLARE_KFIFO looks for me more useful, because i can use it inside a
> struct decalaration. And then i need INIT_KFIFO for initializing this.
> 
> BTW: DECLARE_...., DEFINE_..... and INIT_..... are linux style. Habe a
> look at workqueue.h, wait.h, types.h, semaphore.h, rwsem-spinlock.h,
> interrupt.h, completion.h, seqlock.h and so on....

Yes, you are right. I realized that myself after I sent out my
comments.

> > 1. you can no longer use preallocated buffers, which limits the possible
> > users to those that are unrestricted to the type of allocation.
> > 2. The size of the buffer is no longer power-of-two. In fact, it's guaranteed
> > to be non-power-of-two because kmalloc gives you a power-of-two allocation
> > but now you also put the struct kfifo in there.
> > 
> > Users that need a power-of-two buffer (the common case) now waste almost
> > 50% of the space.
> > 
> 
> Okay, give me a thought about this....... yes you are right ;-( But what
> is with vmalloc? 128 MB should be enough?

vmalloc also has performance problems on some architectures that can
access the linear mapping faster than paged memory and it is
rather wasteful if you have 64kb pages.

I don't think the total size matters, the 128 MB limit only exists
if you have a 32 bit CPU and 1GB or more of memory, which is hopefully
getting rarer and already causes other problems (highmem...).

kmalloc currently limits the kfifo size to something like 128kb (arch
specific), if you need more than that, you need alloc_pages(), which
is limited to a power-of-two amount of pages.

> > The requirement for power-of-two also meant a much faster __kfifo_off
> > function on certain embedded platforms that don't have an integer division
> > instruction in hardware.
>
> Yes i know this argument, but since the day of the 6502 and Z80 i have
> never seen this kind of CPU. Okay i forgot to mention the stupid ARM
> CPU, but newer ARM cores have a hardware division support.

I think this is actually more relevant than the vmalloc limit you mentioned,
demand for tiny processors will probably stay because of cost reasons.
Architectures that we support in Linux without integer divide include
arm, blackfin, h8300, ia64 (!), m68k, microblaze, sh and xtensa.

Your first version with the non-power-of-two buffers also had a bug
in the handling because it would not handle 32 bit integer overflows
correctly. To get those right, you need an extra branch every time you
add to the counter.

Your second version is ok in this regard because it uses the original
size logic.

	Arnd <><
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/