[RFC 0/2] extended kfifo API V0.2

[Stefani Seibold]

This is a the second proposal of an extended and cleaned up generic kernel FIFO 
implementation.

Changes since V0.1:

 add kfifo_init()
 kfifo_put() and kfifo_get() restored to the original behavior (but without locking)
 introduce new kfifo_put_rec() and kfifo_put_rec() for FIFO record handling
 kfifo_alloc() does only allocate the FIFO buffer
 kfifo_free() does only release the FIFO buffer
 revert to power of two buffer sizes

Again the (modified) proposal:
------------------------------ 
 
The current kernel fifo API is not very widely used, because it has to many
constrains. Only 13 files in the current 2.6.30 used it. FIFO's are
like list are a very basic thing and a kfifo API which handles the most use
case would save a lot of time and memory resources.

I think there are the following reasons why kfifo is not in use.

- There is a need of a spinlock despite you need it or not
- A fifo can only allocated dynamically
- There is no support for data records inside a fifo
- The API is to tall, some important functions are missing

So i decided to extend the kfifo in a more generic way without blowing up
the API to much. This was my design goals:

- Generic usage: For kernel internal use or device driver
- Provide an API for the most use case
- Preserve memory resource
- Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros
- Slim API: The whole API provides 16 functions.
- Ability to handle variable length records. Three type of records are
  supported:
  - Records between 0-255 bytes, with a record size field of 1 bytes
  - Records between 0-65535 bytes, with a record size field of 2 bytes
  - Byte stream, which no record size field
  Inside a fifo this record types it is not a good idea to mix them together.
- Direct copy_to_user from the fifo and copy_from_user into the fifo.
- Single structure: The fifo structure contains the management variables and
  the buffer. No extra indirection is needed to access the fifo buffer.
- Lockless access: if only one reader and one writer is active on the fifo,
  which is the common use case, there is no additional locking necessary.
- Performance
- Easy to use

The API:
--------

The struct kfifo is defined as following:

struct kfifo {
	unsigned long size;	/* the size of the allocated buffer */
	unsigned long in;	/* data is added at offset (in&(size-1)) */
	unsigned long out;	/* data is extracted from off. (out&(size-1)) */
	unsigned char *buffer;	/* the buffer holding the data */
};

This structure is so short that an extra allocation for this is omitted in the
new implementation. Simple define a "struct kfifo" where it is needed.
 
void kfifo_init(struct kfifo *fifo, unsigned char *buffer, unsigned int size)
 Initialize a FIFO using a preallocated buffer
 @fifo: the fifo to assign the buffer
 @buffer: the preallocated buffer to be used.
 @size: the size of the internal buffer, this have to be a power of 2.


struct kfifo *kfifo_alloc(struct kfifo *fifo, unsigned long size, gfp_t gfp_mask)
 This function dynamically allocates a new fifo internal buffer
 @fifo: the fifo to assign then new buffer
 @size: the size of the internal buffer to be allocated.
 @gfp_mask: get_free_pages mask, passed to kmalloc()


void kfifo_free(struct kfifo *fifo)
 frees a dynamic allocated FIFO buffer
 @fifo: the fifo which buffer should be freed.


void kfifo_reset(struct kfifo *fifo)
 removes the entire FIFO contents
 @fifo: the fifo to be emptied.


unsigned long kfifo_used(struct kfifo *fifo)
 kfifo_used - returns the number of bytes currently used in the FIFO
 @fifo: the fifo to be used.


unsigned long kfifo_size(struct kfifo *fifo)
 returns the size of the fifo in bytes
 @fifo: the fifo to be used.


kfifo_empty(struct kfifo *fifo)
 returns true if the fifo is empty
 @fifo: the fifo to be used.


kfifo_is_full(struct kfifo *fifo)
 returns true if the fifo is full
 @fifo: the fifo to be used.


unsigned long kfifo_avail(struct kfifo *fifo)
 returns the number of bytes available in the FIFO
 @fifo: the fifo to be used.


unsigned long kfifo_put(struct kfifo *fifo, unsigned char *from, unsigned long n)
 puts some data into the FIFO without locking

 This function copies at most @n bytes from the @from into
 the FIFO depending and returns the number of copied bytes.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.
 This function is for compatibility reasons due the old kfifo API
 @fifo: the fifo to be used.
 @from: the data to be added.
 @n: the length of the data to be added.


unsigned long kfifo_put_rec(struct kfifo *fifo,
	unsigned char *from, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 puts some record data into the FIFO without locking

 This function copies at most @n bytes from the @from into
 the FIFO depending @flags argument, and returns the number of
 bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.
 @fifo: the fifo to be used.
 @from: the data to be added.
 @n: the length of the data to be added.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL


unsigned long kfifo_get(struct kfifo *fifo, unsigned char *to, unsigned long n);
 Gets some data from the FIFO without locking.

 This function copies at most @n bytes from the @to into and returns
 the number of copied bytes

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.
 This function is for compatibility reasons due the old kfifo API
 @fifo: the fifo to be used.
 @to: where the data must be copied.
 @n: the size of the destination buffer.


unsigned long kfifo_get(struct kfifo *fifo,
	unsigned char *to, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 Gets some data record from the FIFO without locking.

 This function copies at most @n bytes from the @to into the FIFO depending
 on @flags argument, and returns the number of bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.
 @fifo: the fifo to be used.
 @to: where the data must be copied.
 @n: the size of the destination buffer.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL


unsigned long kfifo_from_user(struct kfifo *fifo,
	const void __user *from, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 Puts some data from user space into the FIFO.

 This function copies at most @n bytes from the @from into the FIFO depending
 on @flags argument, and returns the number of bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.
 @fifo: the fifo to be used.
 @from: pointer to the data to be added.
 @n: the length of the data to be added.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL


unsigned long kfifo_to_user(struct kfifo *fifo,
		void __user *to, unsigned long n, unsigned long recsize,
		unsigned long flags, unsigned long *total)
 Gets data from the FIFO and write it to user space.

 This function copies at most @n bytes from the FIFO into the @to depending
 on @flags argument.
 In case of an error, the function returns the number of bytes which cannot
 be copied.
 - If the flags KFIFO_F_NOTRIM is set and the returned value is greater than
   the n parameter this means that there is not enough space to copy the
   whole record
 - Otherwise this means that the copy_to_user() functions has failed.

 Note that with only one concurrent reader and one concurrent writer, you don't
 need extra locking to use these functions.
 @fifo: the fifo to be used.
 @to: where the data must be copied.
 @n: the size of the destination buffer.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL


unsigned long kfifo_peek(struct kfifo *fifo, unsigned long recsize)
 Gets the size of the next FIFO record data.

 This function returns the size of the next FIFO record in number of bytes
 @fifo: the fifo to be used.
 @recsize: size of record field


Macros defined for kernel FIFO:
-------------------------------

KFIFO_F_NOTRIM 
	flags argumet: do not cut of the record

DECLARE_KFIFO(name, size)
	declare a kernel fifo (can be used inside a struct declaration)

DEFINE_KFIFO(name, size)
	define a kernel fifo

INIT_KFIFO(name)
	initialize a FIFO


One thing is that the new API is not compatible with the old one. I had
a look at the current user of the old kfifo API and it is easy to adapt it to
the new API. These are the files which use currently the kfifo API:

/usr/src/linux/./drivers/char/nozomi.c
/usr/src/linux/./drivers/char/sonypi.c
/usr/src/linux/./drivers/infiniband/hw/cxgb3/cxio_resource.c
/usr/src/linux/./drivers/media/video/meye.c
/usr/src/linux/./drivers/net/wireless/libertas/main.c
/usr/src/linux/./drivers/platform/x86/fujitsu-laptop.c
/usr/src/linux/./drivers/platform/x86/sony-laptop.c
/usr/src/linux/./drivers/scsi/libiscsi.c
/usr/src/linux/./drivers/scsi/libiscsi_tcp.c
/usr/src/linux/./drivers/scsi/libsrp.c
/usr/src/linux/./drivers/usb/host/fhci.h
/usr/src/linux/./net/dccp/probe.c

I will do this job if there is a tendency for substitute the old API. So i ask
for comments....

Greetings,
Stefani


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