Skip to contentSkip to conversation

RFC: new kqueue API

PATCH In review Stefani Seibold 2 participants 5 messages Dec 13, 2009 – Dec 14, 2009

lore
Share & tools
lore
#0 lore raw

cover RFC: new kqueue API

As i figured out during the port the old kfifo API users, most of them did not need a streamed fifo, because there work only with fixed size entries. The kfifo is oversized for this kind of users, so i decided to write a new kqueue API which is optimized for fixed size entries.

There are a some benefits:

- Performance (a put or get of an integer does only generate 4 assembly instructions on a x86)
- Type save
- Cleaner interface
- Easier to use
- Less error prone
- Smaller footprint

The API is similar to the new kfifo API, but there is no need for a length paramter, because the size of the entry is know by the queue structure.

Here is a small user land example how to use it:

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <stddef.h>

#ifndef __KERNEL__
#define EXPORT_SYMBOL(x)
#define unlikely(x) x
#define likely(x) x
#define __must_check
#define __user
#define spinlock_t void
#define gfp_t unsigned long
#define spin_lock_irqsave(a,b)
#define spin_unlock_irqsave(a,b)
#define BUG_ON(x)
#define is_power_of_2(x) 1
#define roundup_pow_of_two(x) (x)
#define kmalloc(a,b) malloc(a)
#define kfree(a) free(a)
#define BUG()

#define barrier() __asm__ __volatile__("": : :"memory")

#define mb() asm volatile("mfence":::"memory")
#define rmb() asm volatile("lfence":::"memory")
#define wmb() asm volatile("sfence" ::: "memory")

#define smp_mb() mb()
#define smp_rmb() rmb()
#define smp_wmb() wmb()

#define min(X,Y) (((X) < (Y)) ? (X) : (Y))
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*x))

struct scatterlist {
	unsigned long	page_link;
	unsigned int	offset;
	unsigned int	length;
};

static inline void sg_mark_end(struct scatterlist *sg)

{
	sg->page_link |= 0x02;
	sg->page_link &= ~0x01;
}

static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
unsigned int buflen)
{
}

static unsigned long copy_to_user(void * to, const void * from, unsigned long n)

{
	memcpy(to, from, n);
	return 0;
}

static unsigned long copy_from_user(void * to, const void * from, unsigned long n)

{
	memcpy(to, from, n);
	return 0;
}

#endif

/* --------------------------> test program */

#include "kqueue.h"
#include "kqueue.c"

//#define DYNAMIC

#ifdef DYNAMIC
static DECLARE_KQUEUE(*test, int, 32);
#else
typedef STRUCT_KQUEUE(int, 32) mytest;

static mytest testx;
static mytest *test = &testx;
#endif

int main(void)

{
	unsigned int	i;
	char	buf[6];
	int	ret;
#ifdef DYNAMIC
	if (kqueue_alloc(&test, 64, 0)) {
		fprintf(stderr,"error kqueue_alloc\n");
		return 1;
	}
#else
	INIT_KQUEUE(testx);

#endif

	for(i=0; i != 10; i++) {
		kqueue_in(test, i);
	}

	while(!kqueue_is_empty(test)) {
		i = kqueue_out(test);
		printf("%d:\n", i);
	}

	for(i=0; i!=9; i++) {
		kqueue_in(test, i);
	}

	ret = kqueue_to_user(test, buf, sizeof(buf));
	printf("-ret: %d \n", ret);
	ret = kqueue_from_user(test, buf, sizeof(buf));
	printf("-ret: %d \n", ret);
	ret = kqueue_to_user(test, buf, sizeof(buf));
	printf("-ret: %d \n", ret);
	ret = kqueue_from_user(test, buf, sizeof(buf));
	printf("-ret: %d \n", ret);

	while(!kqueue_is_empty(test)) {
		i = kqueue_out(test);
		printf("%d:\n", i);
	}

	i=0;


	while(!kqueue_is_full(test)) {
		++i;

		kqueue_in(test, i);
		printf("%u ", kqueue_len(test));
	}
	printf("\n");

	while(!kqueue_is_empty(test))
		printf("%d ", kqueue_out(test));

	printf("\n");

	return 0;
}

I hope you like it. If yes, i will start to port the kfifo fixed size users to the new API.

Stefani

#1 lore raw

New kqueue API for queues with fixed size entries.

---
 include/linux/kqueue.h |  407 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/Makefile        |    2 
 kernel/kqueue.c        |  200 ++++++++++++++++++++++++
 3 files changed, 608 insertions(+), 1 deletion(-)
include/linux/kqueue.h +407 -0
diff -u -N -r orig/include/linux/kqueue.h new/include/linux/kqueue.h
@@ -0,0 +1,407 @@
+/*
+ * A generic kernel queue implementation for fixed size elements.
+ *
+ * Copyright (C) 2009 Stefani Seibold <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#ifndef _LINUX_KQUEUE_H
+#define _LINUX_KQUEUE_H
+
+#ifdef __KERNEL__
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+#include <linux/stddef.h>
+#include <linux/scatterlist.h>
+#endif
+
+#define STRUCT_KQUEUE(type, size) \
+struct { \
+	unsigned int	in; \
+	unsigned int	out; \
+	unsigned int	mask; \
+	type		data[size ? ((size & (size - 1)) ? -1 : size) : 1]; \
+}
+
+/**
+ * DECLARE_KQUEUE - macro to declare a kqueue object
+ * @queue: name of the declared kqueue
+ * @type: type of the queue elements
+ * @size: the number of elements in the queue, this must be a power of 2.
+ */
+#define DECLARE_KQUEUE(queue, type, size) \
+	STRUCT_KQUEUE(type, size) queue
+
+/*
+ * Macros for declaration and initialization of the kqueue datatype
+ */
+
+/* helper macro */
+#define __kqueue_initializer(queue) \
+	(typeof(queue)) { \
+		.in	= 0, \
+		.out	= 0, \
+		.mask	= ARRAY_SIZE(queue.data) - 1, \
+	}
+
+/**
+ * INIT_KQUEUE - Initialize a kqueue declared by DECLARED_KQUEUE
+ * @queue: name of the declared kqueue datatype
+ */
+#define INIT_KQUEUE(queue) \
+	queue = __kqueue_initializer(queue)
+
+/**
+ * DEFINE_KQUEUE - macro to define and initialize a kqueue
+ * @queue: name of the declared kqueue datatype
+ * @type: type of the queue elements
+ * @size: the number of elements in the queue, this must be a power of 2.
+ *
+ * Note: the macro can be used for global and local kqueue data type variables
+ */
+#define DEFINE_KQUEUE(queue, type, size) \
+	DECLARE_KQUEUE(queue, type, size) = __kqueue_initializer(queue)
+
+/**
+ * kqueue_size - returns the size of the queue in elements
+ * @queue: the queue to be used.
+ */
+#define kqueue_size(queue)	((queue)->mask + 1)
+
+/**
+ * kqueue_reset - removes the entire queue content
+ * @queue: the queue to be used.
+ */
+#define kqueue_reset(queue) \
+(void)({ \
+	typeof(queue) __tmp = queue; \
+	__tmp->in = __tmp->out = 0; \
+})
+
+/**
+ * kqueue_reset_out - skip queue content
+ * @queue: the queue to be used.
+ */
+#define kqueue_reset_out(queue)	\
+(void)({ \
+	typeof(queue) __tmp = queue; \
+	__tmp->out = __tmp->in; \
+})
+
+/**
+ * kqueue_len - returns the number of used elements in the queue
+ * @queue: the queue to be used.
+ */
+#define kqueue_len(queue) \
+({ \
+	typeof(queue) __tmp = queue; \
+	register unsigned int	__out; \
+	__out = __tmp->out; \
+	smp_rmb(); \
+	__tmp->in - __out; \
+})
+
+/**
+ * kqueue_is_empty - returns true if the queue is empty
+ * @queue: the queue to be used.
+ */
+#define	kqueue_is_empty(queue) \
+({ \
+	typeof(queue) __tmp = queue; \
+	__tmp->in == __tmp->out; \
+})
+
+/**
+ * kqueue_is_full - returns true if the queue is full
+ * @queue: the queue to be used.
+ */
+#define	kqueue_is_full(queue) \
+({ \
+	typeof(queue) __tmpq = queue; \
+	kqueue_size(__tmpq) == kqueue_len(__tmpq); \
+})
+
+/**
+ * kqueue_avail - returns the number of elements available in the queue
+ * @queue: the queue to be used.
+ */
+#define	kqueue_avail(queue) \
+({ \
+	typeof(queue) __tmpq = queue; \
+	kqueue_size(__tmpq) - kqueue_len(__tmpq); \
+})
+
+/**
+ * kqueue_skip - skip output data
+ * @queue: the queue to be used.
+ */
+#define	kqueue_skip(queue)	((queue)->out++)
+
+/**
+ * kqueue_in - puts some data into the queue
+ * @queue: the queue to be used.
+ * @val: the data to be added.
+ *
+ * This macro opies the given value into the queue.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kqueue_in(queue, val) \
+({ \
+	typeof(queue) __tmp = queue; \
+	typeof(val) __val = val; \
+	smp_mb(); \
+	__tmp->data[__tmp->in & __tmp->mask] = __val; \
+	barrier(); \
+	__tmp->in++; \
+	__val; \
+})
+
+/**
+ * kqueue_in_locked - put data into the queue using a spinlock for locking
+ * @queue: the queue to be used.
+ * @val: the data to be added.
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro copies the given value into the queue.
+ */
+#define	kqueue_in_locked(queue, val, lock) \
+({ \
+	typeof(val) __val = val; \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	kqueue_in(queue, __val); \
+	spin_unlock_irqrestore(lock, __flags); \
+	__val; \
+})
+
+/**
+ * kqueue_out - get data from the queue
+ * @queue: the queue to be used.
+ *
+ * This macro returns the data from the queue
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kqueue_out(queue) \
+({ \
+	typeof(queue) __tmp = queue; \
+	typeof(__tmp->data[0]) __ret; \
+	smp_rmb(); \
+	__ret = __tmp->data[__tmp->out & __tmp->mask]; \
+	barrier(); \
+	__tmp->out++; \
+	__ret; \
+})
+
+/**
+ * kqueue_out_locked - get data from the queue using a spinlock for locking
+ * @queue: the queue to be used.
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro returns the data from the queue
+ */
+#define	kqueue_out_locked(queue, lock) \
+({ \
+	typeof(queue) __tmpq = queue; \
+	typeof(__tmp->data[0]) __ret; \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kqueue_out(__tmpq); \
+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+})
+
+extern unsigned int __kqueue_from_user(void *data, unsigned int size,
+		unsigned int in, unsigned int out, size_t esize,
+		const void __user *from, unsigned int len);
+
+/**
+ * kqueue_from_user - puts some data from user space into the queue
+ * @queue: the queue to be used.
+ * @from: pointer to the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This macro copies at most @len bytes from the @from into the
+ * queue, depending of the available space 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 macro.
+ */
+#define	kqueue_from_user(queue, from, len) \
+({ \
+	typeof(queue) __tmp = queue; \
+	unsigned int __len = len; \
+	unsigned int __ret; \
+	size_t __esize = sizeof(__tmp->data[0]); \
+	smp_mb(); \
+	__ret = __kqueue_from_user(__tmp->data, kqueue_size(__tmp), __tmp->in, \
+					__tmp->out, __esize, from, __len); \
+	__tmp->in += __ret; \
+	__len - __ret * __esize; \
+})
+
+extern unsigned int __kqueue_to_user(void *data, unsigned int size,
+		unsigned int in, unsigned int out, size_t esize,
+		void __user *to, unsigned int len);
+
+/**
+ * kqueue_to_user - gets data from the queue and write it to user space
+ * @queue: the queue to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This macro copies at most @len bytes from the queue into the
+ * @to buffer 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 macro.
+ */
+#define	kqueue_to_user(queue, to, len) \
+({ \
+	typeof(queue) __tmp = queue; \
+	unsigned int __len = len; \
+	unsigned int __ret; \
+	size_t __esize = sizeof(__tmp->data[0]); \
+	smp_rmb(); \
+	__ret = __kqueue_to_user(__tmp->data, kqueue_size(__tmp), __tmp->in, \
+					__tmp->out, __esize, to, __len); \
+	__tmp->out += __ret; \
+	__len - __ret * __esize; \
+})
+
+extern int __kqueue_alloc(void **queue, unsigned int size,
+		size_t off, size_t esize, gfp_t gfp_mask);
+
+/**
+ * kqueue_alloc - allocates a new queue
+ * @queue: pointer to a pointer to the queue
+ * @size: the number of elements in the queue, this must be a power of 2.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ *
+ * This macro dynamically allocates a new queue.
+ *
+ * The size will be rounded-up to a power of 2.
+ * The queue will be release with kqueue_free().
+ * Return 0 if no error, otherwise an error code
+ */
+#define kqueue_alloc(queue, size, gfp_mask) \
+({ \
+	typeof(queue) __tmp = queue; \
+	__kqueue_alloc((void **)__tmp, size, offsetof(typeof(**__tmp), data), \
+		sizeof((*__tmp)->data[0]), gfp_mask); \
+})
+
+/**
+ * kqueue_free - frees the queue
+ * @queue: the queue to be freed.
+ */
+#define kqueue_free(queue)	kfree(queue)
+
+extern unsigned int __kqueue_dma_in_prepare(void *data, unsigned int size,
+		unsigned int in, unsigned int out, size_t esize,
+		struct scatterlist *sgl, int nents);
+
+/**
+ * kqueue_dma_in_prepare - setup a scatterlist for DMA input
+ * @queue: the queue to be used.
+ * @sgl: pointer to the scatterlist array.
+ * @nents: number of entries in the scatterlist array (should be 1 or 2).
+ *
+ * This function fills a scatterlist for DMA input.
+ * It returns the number of bytes which are available for the transfer.
+ * A return value of 0 means that no scatterlist was written.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these functions.
+ */
+#define	kqueue_dma_in_prepare(queue, sgl, nents) \
+({ \
+	typeof(queue) __tmp = queue; \
+	smp_mb(); \
+	__kqueue_dma_in_prepare(__tmp->data, kqueue_size(__tmp), __tmp->in, \
+			__tmp->out, sizeof(__tmp->data[0]), sgl, nents); \
+})
+
+/**
+ * kqueue_dma_in_finish - finish a DMA IN operation
+ * @queue: the queue to be used.
+ * @len: number number of bytes to received.
+ *
+ * This function finish a DMA IN operation. The in counter will be updated by
+ * the len parameter. No error checking will be done.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these functions.
+ */
+#define kqueue_dma_in_finish(queue, len) \
+(void)({ \
+	typeof(queue) __tmp = queue; \
+	__tmp->in += len / sizeof(__tmp->data[0]); \
+})
+
+extern unsigned int __kqueue_dma_out_prepare(void *data, unsigned int size,
+		unsigned int in, unsigned int out, size_t esize,
+		struct scatterlist *sgl, int nents, unsigned int len);
+
+/**
+ * kqueue_dma_out_prepare - setup a scatterlist for DMA output
+ * @queue: the queue to be used.
+ * @sgl: pointer to the scatterlist array.
+ * @nents: number of entries in the scatterlist array (should be 1 or 2).
+ * @len: number number of bytes to transfer.
+ *
+ * This function fills a scatterlist for DMA output which at most @len bytes
+ * to transfer.
+ * It returns the number of bytes which are available for the transfer.
+ * A return value of 0 means that no scatterlist was written.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these functions.
+ */
+#define	kqueue_dma_out_prepare(queue, sgl, nents, len) \
+({ \
+	typeof(queue) __tmp = queue; \
+	smp_rmb(); \
+	__kqueue_dma_out_prepare(__tmp->data, kqueue_size(__tmp), __tmp->in, \
+			__tmp->out, sizeof(__tmp->data[0]), sgl, nents, len); \
+})
+
+/**
+ * kqueue_dma_out_finish - finish a DMA OUT operation
+ * @queue: the queue to be used.
+ * @len: number number of bytes transferd.
+ *
+ * This function finish a DMA OUT operation. The out counter will be updated by
+ * the len parameter. No error checking will be done.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these functions.
+ */
+#define kqueue_dma_out_finish(queue, len) \
+(void)({ \
+	typeof(queue) __tmp = queue; \
+	__tmp->out += len / sizeof(__tmp->data[0]); \
+})
+
+#endif
+
kernel/kqueue.c +200 -0

200 lines not on this page · raw message

kernel/Makefile +1 -1
diff -u -N -r orig/kernel/Makefile new/kernel/Makefile
@@ -6,7 +6,7 @@
 	    cpu.o exit.o itimer.o time.o softirq.o resource.o \
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
-	    rcupdate.o extable.o params.o posix-timers.o \
+	    rcupdate.o extable.o params.o posix-timers.o kqueue.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
 	    hrtimer.o rwsem.o nsproxy.o srcu.o semaphore.o \
 	    notifier.o ksysfs.o pm_qos_params.o sched_clock.o cred.o \
#2 lore raw
In reply to Stefani Seibold
Quoted 15 lines · Stefani Seibold

As i figured out during the port the old kfifo API users, most of them did not need a streamed fifo, because there work only with fixed size entries. The kfifo is oversized for this kind of users, so i decided to write a new kqueue API which is optimized for fixed size entries.

There are a some benefits:

- Performance (a put or get of an integer does only generate 4 assembly instructions on a x86)
- Type save
- Cleaner interface
- Easier to use
- Less error prone
- Smaller footprint

Quoted 3 lines

The API is similar to the new kfifo API, but there is no need for a length paramter, because the size of the entry is know by the queue structure.

I must say I'm a bit sceptical if the advantages are really worth the additional code. That code would be always compiled in in addition to kfifo, so at least the code footprint would be always larger.

Perhaps you could get the advantages for type-safety using inline wrappers to kfifo?

-Andi

#3 lore raw

Am Sonntag, den 13.12.2009, 19:37 +0100 schrieb Andi Kleen:

Quoted 16 lines · Stefani Seibold
Quoted 15 lines

As i figured out during the port the old kfifo API users, most of them did not need a streamed fifo, because there work only with fixed size entries. The kfifo is oversized for this kind of users, so i decided to write a new kqueue API which is optimized for fixed size entries.

There are a some benefits:

- Performance (a put or get of an integer does only generate 4 assembly instructions on a x86)
- Type save
- Cleaner interface
- Easier to use
- Less error prone
- Smaller footprint

Quoted 8 lines
Quoted 3 lines

The API is similar to the new kfifo API, but there is no need for a length paramter, because the size of the entry is know by the queue structure.

I must say I'm a bit sceptical if the advantages are really worth the additional code. That code would be always compiled in in addition to kfifo, so at least the code footprint would be always larger.

The additional code is very tiny... less than 1 kb ;-) Changing the fixed size user to the new kqueue API would result on the other side in less footprint and a much better performance.

Quoted 3 lines

Perhaps you could get the advantages for type-safety using inline wrappers to kfifo?

No, i have no idea how to do this. If you give me the okay to use C++ it could be easy done with templates (just kidding...)

The next step after merging of the new kfifo API would be the deinlineing of the code... This will also reduce the footprint of the kfifo API users, but not as much as with the kqueue API.

But have a look to the new interfaces. It is quite simple and natural to use and faster than light ;-)

Stefani

#4 lore raw
In reply to Andi Kleen

Am Sonntag, den 13.12.2009, 19:37 +0100 schrieb Andi Kleen:

Quoted 20 lines · Stefani Seibold
Quoted 15 lines

As i figured out during the port the old kfifo API users, most of them did not need a streamed fifo, because there work only with fixed size entries. The kfifo is oversized for this kind of users, so i decided to write a new kqueue API which is optimized for fixed size entries.

There are a some benefits:

- Performance (a put or get of an integer does only generate 4 assembly instructions on a x86)
- Type save
- Cleaner interface
- Easier to use
- Less error prone
- Smaller footprint

Quoted 3 lines

The API is similar to the new kfifo API, but there is no need for a length paramter, because the size of the entry is know by the queue structure.

Quoted 7 lines

I must say I'm a bit sceptical if the advantages are really worth the additional code. That code would be always compiled in in addition to kfifo, so at least the code footprint would be always larger.

Perhaps you could get the advantages for type-safety using inline wrappers to kfifo?

Okay, i found a nice solution to mix the new kqueue with my kfifo API.

- It its now type safe and the huger functions are now deinlined.
- Non dynamic allocated fifo did not need anymore the extra indirection to the data buffer.
- And i moved the record stuff in an extra header and source file named kfiforec.[ch].

Stefani