Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli <andrea@novell.com>]

On Fri, Sep 17, 2004 at 10:50:12PM +0200, Stelian Pop wrote:
> +	spinlock_t *lock;	/* protects concurrent modifications */

if we've to spend 4 bytes into a pointer, then we could as well have a
spinlock_t. The idea was to pass the pointer through the stack every
time we call a method of the class so no locking-memory would be
allocated at all in the kfifo struct.

Anyways if you like the above I don't mind 4 more bytes per struct
(especially in my usage that is entirely in a slow path and dynamically
allocated). we reached a state where the patch looks good enough, so we
can merge it and later over time can do further modifications
incrementally.

> +	/* 
> +	 * round up to the next power of 2, since our 'let the indices
> +	 * wrap' tachnique works only in this case.
> +	 */
> +	if (size > 0x80000000)
> +		return ERR_PTR(-EINVAL);
> +	newsize = 1;
> +	while (newsize < size)
> +		newsize <<= 1;

this could be:

	newsize = size;
	if (size & (size-1)) {
		BUG_ON(size > 0x80000000);
		newsize = 1;
		while (newsize < size)
			newsize <<= 1;
	}

so we get the fast path when people asks for PAGE_SIZE multiples.

I also wonder if a O(1) algorithm exists to roundup to the next power of
two (doesn't come to mind by memory, hmm maybe it's not that easy
problem).

Thanks Stelian. Now if you like to keep working in this area and you
would like to also change do_syslog to use your new object, more power
to you and good luck! 8)