[RFC] kfifo writer side lock-less support

[RFC] kfifo writer side lock-less support

[Huang Ying]

This patch add lock-less support for kfifo writer side amongst
different contexts on one CPU, such as NMI, IRQ, soft_irq, process,
etc. This makes kfifo can be used to implement per-CPU lock-less data
structure.

The different contexts on one CPU have some kind of preemption
priority as follow:

process -> soft_irq -> IRQ -> NMI

Where preemption priority increases from left to right. That is, the
right side context can preempt left side context, but not in the
reverse direction, that means the right side context will run to the
end before return to the left side context. The lock-less algorithm
used in the patch take advantage of this.

The algorithm works in reserve/commit style, where "reserve" only
allocate the space, while "commit" really makes the data into buffer,
data is prepared in between. cmpxchg is used in "reserve", this
guarantees different spaces will be allocated for different
contexts. Only the "commit" in lowest context will commit all
allocated spaces. Because all contexts preempting lowest context
between "reserve" and "commit" will run to the end, all data put into
buffer are valid.

Some idea of the lock-less algorithm in the patch comes from Steven
Rostedt's trace ring buffer implementation.

The new xxx_ptr interface and kfifo_iter makes it possible to
write/read content of kfifo in-place in addition to copying out/in.

Signed-off-by: Huang Ying <ying.huang@intel.com>
---
 include/linux/kfifo.h |   87 +++++++++++++++++-
 kernel/kfifo.c        |  231 ++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 305 insertions(+), 13 deletions(-)

--- a/include/linux/kfifo.h
+++ b/include/linux/kfifo.h
@@ -49,6 +49,7 @@ struct kfifo {
 	unsigned int size;	/* the size of the allocated buffer */
 	unsigned int in;	/* data is added at offset (in % size) */
 	unsigned int out;	/* data is extracted from off. (out % size) */
+	unsigned int reserve;	/* space is reserved at off (reserve % size) */
 };
 
 /*
@@ -60,6 +61,7 @@ struct kfifo {
 	(struct kfifo) { \
 		.size	= s, \
 		.in	= 0, \
+		.reserve = 0, \
 		.out	= 0, \
 		.buffer = b \
 	}
@@ -132,7 +134,7 @@ static inline bool kfifo_initialized(str
  */
 static inline void kfifo_reset(struct kfifo *fifo)
 {
-	fifo->in = fifo->out = 0;
+	fifo->reserve = fifo->in = fifo->out = 0;
 }
 
 /**
@@ -167,6 +169,18 @@ static inline unsigned int kfifo_len(str
 	return fifo->in - out;
 }
 
+/*
+ * returns the number of used bytes (including reserved) in the FIFO
+ */
+static inline unsigned int __kfifo_used(struct kfifo *fifo)
+{
+	register unsigned int	out;
+
+	out = fifo->out;
+	smp_rmb();
+	return fifo->reserve - out;
+}
+
 /**
  * kfifo_is_empty - returns true if the fifo is empty
  * @fifo: the fifo to be used.
@@ -182,7 +196,7 @@ static inline __must_check int kfifo_is_
  */
 static inline __must_check int kfifo_is_full(struct kfifo *fifo)
 {
-	return kfifo_len(fifo) == kfifo_size(fifo);
+	return __kfifo_used(fifo) == kfifo_size(fifo);
 }
 
 /**
@@ -191,7 +205,7 @@ static inline __must_check int kfifo_is_
  */
 static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
 {
-	return kfifo_size(fifo) - kfifo_len(fifo);
+	return kfifo_size(fifo) - __kfifo_used(fifo);
 }
 
 /**
@@ -269,6 +283,7 @@ static inline void __kfifo_add_out(struc
 static inline void __kfifo_add_in(struct kfifo *fifo,
 				unsigned int off)
 {
+	fifo->reserve += off;
 	smp_wmb();
 	fifo->in += off;
 }
@@ -283,6 +298,15 @@ static inline unsigned int __kfifo_off(s
 }
 
 /*
+ * __kfifo_ptr internal helper function to get pointer at the position
+ * for in-place accessing
+ */
+static inline void *__kfifo_ptr(struct kfifo *fifo, unsigned int pos)
+{
+	return fifo->buffer + __kfifo_off(fifo, pos);
+}
+
+/*
  * __kfifo_peek_n internal helper function for determinate the length of
  * the next record in the fifo
  */
@@ -607,9 +631,64 @@ static inline void kfifo_skip_rec(struct
 static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
 	unsigned int recsize)
 {
-	unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);
+	unsigned int l = kfifo_size(fifo) - __kfifo_used(fifo);
 
 	return (l > recsize) ? l - recsize : 0;
 }
 
+extern __must_check int kfifo_reserve(struct kfifo *fifo,
+	unsigned int len, unsigned int *ppos);
+extern void kfifo_commit(struct kfifo *fifo, unsigned int pos);
+extern void kfifo_in_data(struct kfifo *fifo, const void *from,
+	unsigned int len, unsigned int off);
+extern unsigned int kfifo_ll_in(struct kfifo *fifo, const void *from,
+	unsigned int len);
+extern __must_check void *kfifo_reserve_continuous_ptr(struct kfifo *fifo,
+	unsigned int *len);
+extern void kfifo_commit_ptr(struct kfifo *fifo, void *ptr);
+
+struct kfifo_iter {
+	struct kfifo *fifo;
+	unsigned int pos;
+};
+
+/**
+ * kfifo_iter_init - initialize a FIFO iterator
+ * @iter: the iterator to be initialized
+ * @fifo: the fifo to be accessed
+ *
+ */
+static inline void kfifo_iter_init(struct kfifo_iter *iter, struct kfifo *fifo)
+{
+	iter->fifo = fifo;
+	iter->pos = fifo->out;
+}
+
+/**
+ * kfifo_iter_advance - advances the position of iterator
+ * @iter: the iterator to be used
+ * @adv: the bytes to advance
+ *
+ * This function advances the position of iterator by @adv bytes,
+ * usually goes to the position of the next record.
+ */
+static inline void kfifo_iter_advance(struct kfifo_iter *iter, unsigned int adv)
+{
+	iter->pos += adv;
+}
+
+/**
+ * kfifo_iter_get_ptr - gets the pointer to the current position of iterator
+ * @iter: the iterator to be used
+ *
+ * This function returns the pointer to the current position of
+ * iterator. If the iterator is at the end of FIFO, NULL is
+ * returned. This is used to access the data/records in FIFO in-place.
+ */
+static inline void *kfifo_iter_get_ptr(struct kfifo_iter *iter)
+{
+	if (iter->pos == iter->fifo->in)
+		return NULL;
+	return __kfifo_ptr(iter->fifo, iter->pos);
+}
 #endif
--- a/kernel/kfifo.c
+++ b/kernel/kfifo.c
@@ -116,8 +116,18 @@ void kfifo_skip(struct kfifo *fifo, unsi
 }
 EXPORT_SYMBOL(kfifo_skip);
 
-static inline void __kfifo_in_data(struct kfifo *fifo,
-		const void *from, unsigned int len, unsigned int off)
+/**
+ * kfifo_in_data - copies some data into FIFO
+ * @fifo: the fifo to be used.
+ * @from: the data to be copied
+ * @len: length of the data to be copied
+ * @off: the offset in FIFO, to which the data is copied
+ *
+ * This function copied @len bytes from the @from buffer into the @off
+ * position of the FIFO.
+ */
+void kfifo_in_data(struct kfifo *fifo, const void *from, unsigned int len,
+	unsigned int off)
 {
 	unsigned int l;
 
@@ -128,7 +138,7 @@ static inline void __kfifo_in_data(struc
 
 	smp_mb();
 
-	off = __kfifo_off(fifo, fifo->in + off);
+	off = __kfifo_off(fifo, off);
 
 	/* first put the data starting from fifo->in to buffer end */
 	l = min(len, fifo->size - off);
@@ -137,6 +147,7 @@ static inline void __kfifo_in_data(struc
 	/* then put the rest (if any) at the beginning of the buffer */
 	memcpy(fifo->buffer, from + l, len - l);
 }
+EXPORT_SYMBOL_GPL(kfifo_in_data);
 
 static inline void __kfifo_out_data(struct kfifo *fifo,
 		void *to, unsigned int len, unsigned int off)
@@ -150,7 +161,7 @@ static inline void __kfifo_out_data(stru
 
 	smp_rmb();
 
-	off = __kfifo_off(fifo, fifo->out + off);
+	off = __kfifo_off(fifo, off);
 
 	/* first get the data from fifo->out until the end of the buffer */
 	l = min(len, fifo->size - off);
@@ -232,7 +243,7 @@ unsigned int __kfifo_in_n(struct kfifo *
 	if (kfifo_avail(fifo) < len + recsize)
 		return len + 1;
 
-	__kfifo_in_data(fifo, from, len, recsize);
+	kfifo_in_data(fifo, from, len, fifo->in + recsize);
 	return 0;
 }
 EXPORT_SYMBOL(__kfifo_in_n);
@@ -255,7 +266,7 @@ unsigned int kfifo_in(struct kfifo *fifo
 {
 	len = min(kfifo_avail(fifo), len);
 
-	__kfifo_in_data(fifo, from, len, 0);
+	kfifo_in_data(fifo, from, len, fifo->in);
 	__kfifo_add_in(fifo, len);
 	return len;
 }
@@ -274,7 +285,7 @@ unsigned int __kfifo_out_n(struct kfifo
 	if (kfifo_len(fifo) < len + recsize)
 		return len;
 
-	__kfifo_out_data(fifo, to, len, recsize);
+	__kfifo_out_data(fifo, to, len, fifo->out + recsize);
 	__kfifo_add_out(fifo, len + recsize);
 	return 0;
 }
@@ -296,7 +307,7 @@ unsigned int kfifo_out(struct kfifo *fif
 {
 	len = min(kfifo_len(fifo), len);
 
-	__kfifo_out_data(fifo, to, len, 0);
+	__kfifo_out_data(fifo, to, len, fifo->out);
 	__kfifo_add_out(fifo, len);
 
 	return len;
@@ -319,7 +330,7 @@ unsigned int kfifo_out_peek(struct kfifo
 {
 	len = min(kfifo_len(fifo), len + offset);
 
-	__kfifo_out_data(fifo, to, len, offset);
+	__kfifo_out_data(fifo, to, len, fifo->out + offset);
 	return len;
 }
 EXPORT_SYMBOL(kfifo_out_peek);
@@ -443,3 +454,205 @@ void __kfifo_skip_generic(struct kfifo *
 }
 EXPORT_SYMBOL(__kfifo_skip_generic);
 
+/**
+ * kfifo_reserve - reserves some space in the FIFO
+ * @fifo: the fifo to be used.
+ * @len: the length of space to be reserved.
+ * @ppos: return position of the reserved space.
+ *
+ * This function reserves space of @len bytes in the FIFO. The
+ * position of the reserved space is returned in @ppos. After the
+ * space is reserved, the data can be copied into reserved space with
+ * kfifo_in_data, and finally put into FIFO with kfifo_commit.
+ *
+ * This function must be paired with kfifo_commit, unless 0 is
+ * returned, which means no space is reserved.
+ *
+ * If the FIFO is used only on one CPU, kfifo_reserve/kfifo_commit
+ * pair can be used by different contexts such as NMI, IRQ, soft_irq
+ * and process (with preempt off) simultaneously safely without any
+ * locking or interrupt disabling.
+ *
+ * Preempt must be disabled between kfifo_reserve and kfifo_commit in
+ * process context for lock-less usage.
+ *
+ * Return 1 if success; return 0 if no enough space, nothing will be
+ * reserved.
+ */
+int kfifo_reserve(struct kfifo *fifo,
+	unsigned int len, unsigned int *ppos)
+{
+	unsigned int pos, npos;
+
+	npos = fifo->reserve;
+	do {
+		pos = npos;
+		if (kfifo_size(fifo) - (pos - fifo->out) < len)
+			return 0;
+		npos = cmpxchg(&fifo->reserve, pos, pos + len);
+	} while (npos != pos);
+	*ppos = pos;
+
+	return 1;
+}
+EXPORT_SYMBOL_GPL(kfifo_reserve);
+
+/**
+ * kfifo_commit - commits the previous reserved space in the FIFO
+ * @fifo: the fifo to be used.
+ * @pos: position of the previous reserved space
+ *
+ * This function makes the data in previous reserved space at @pos
+ * into FIFO and can be consumed by reader.
+ */
+void kfifo_commit(struct kfifo *fifo, unsigned int pos)
+{
+	unsigned int in, nin, reserve;
+
+	if (fifo->in == pos) {
+		/* fifo->in must be updated after data */
+		smp_wmb();
+		do {
+			in = fifo->in;
+			/*
+			 * fifo->in must be read before fifo->reserve,
+			 * otherwise "in" may go beyond "reserve".
+			 */
+			rmb();
+			reserve = fifo->reserve;
+			/*
+			 * If preempted here, fifo->reserve may go
+			 * beyond reserve, this must be checked after
+			 * fifo->in assignment.
+			 */
+			nin = cmpxchg(&fifo->in, in, reserve);
+			/*
+			 * If preempted here, fifo->reserve != reserve
+			 * too, fifo->in need change with cmpxchg to
+			 * prevent fifo->in go backwards.
+			 */
+		} while (reserve != fifo->reserve || in != nin);
+	}
+}
+EXPORT_SYMBOL_GPL(kfifo_commit);
+
+/**
+ * kfifo_ll_in - puts some data into the FIFO, lock-less version
+ * @fifo: the fifo to be used.
+ * @from: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function puts @len bytes from @from buffer into the FIFO. If
+ * it is used on one CPU, the function can be used simultaneously by
+ * multiple contexts such as NMI, IRQ, soft_irq, process, etc safely
+ * without any locking or interrupt disabling.
+ *
+ * Return @len if success, 0 if no enough space
+ */
+unsigned int kfifo_ll_in(struct kfifo *fifo, const void *from, unsigned int len)
+{
+	unsigned int pos;
+
+	preempt_disable();
+	if (!kfifo_reserve(fifo, len, &pos))
+		return 0;
+	kfifo_in_data(fifo, from, len, pos);
+	kfifo_commit(fifo, pos);
+	preempt_enable_no_resched();
+	return len;
+}
+EXPORT_SYMBOL_GPL(kfifo_ll_in);
+
+/*
+ * Reserves some continuous spaces in the FIFO.
+ */
+static int kfifo_reserve_continuous(struct kfifo *fifo,
+	unsigned int *rlen, unsigned int *ppos)
+{
+	unsigned int pos, npos, l, to_end, avail, len = *rlen;
+
+	npos = fifo->reserve;
+	do {
+		pos = npos;
+		avail = kfifo_size(fifo) - (pos - fifo->out);
+		if (avail < len)
+			return 0;
+		to_end = kfifo_size(fifo) - __kfifo_off(fifo, pos);
+		if (to_end < len) {
+			if (avail - to_end < len)
+				return 0;
+			l = to_end;
+		} else
+			l = len;
+		npos = cmpxchg(&fifo->reserve, pos, pos + l);
+	} while (npos != pos);
+	*ppos = pos;
+	*rlen = l;
+
+	return 1;
+}
+
+/**
+ * kfifo_reserve_continuous_ptr - reserves some continuous space in the FIFO
+ * @fifo: the fifo to be used.
+ * @len: the length of space to be reserved, also used to return
+ *       actual reserved length.
+ *
+ * This function reserves some continuous space of at most @len bytes
+ * in the FIFO, and return the pointer to the space. So the reserved
+ * space can be accessed "in-place", until they are committed with
+ * kfifo_commit_ptr. The resulting FIFO layout also makes it possible
+ * to be read in-place.
+ *
+ * There may be two separated free spaces in FIFO, at begin and end of
+ * the buffer. If both are not big enough, NULL will return. If the
+ * free space at end is not but the free space at begin is big enough,
+ * the free space at end will be return, with @len set to actual
+ * length. Otherwise, @len will not be changed, and free space with
+ * length @len will be returned.
+ *
+ * This function must be paired with kfifo_commit_ptr, unless NULL is
+ * returned, which means no space is reserved.
+ *
+ * If the FIFO is used only on one CPU,
+ * kfifo_reserve_continuous_ptr/kfifo_commit_ptr pair can be used by
+ * different contexts such as NMI, IRQ, soft_irq and process (with
+ * preempt off) simultaneously and safely without any locking or
+ * interrupt disabling.
+ *
+ * Preempt must be disabled between kfifo_reserve_continuous_ptr and
+ * kfifo_commit_ptr in process context for lock-less usage.
+ */
+void *kfifo_reserve_continuous_ptr(struct kfifo *fifo,
+	unsigned int *len)
+{
+	unsigned int pos;
+
+	if (!kfifo_reserve_continuous(fifo, len, &pos))
+		return NULL;
+	return __kfifo_ptr(fifo, pos);
+}
+EXPORT_SYMBOL_GPL(kfifo_reserve_continuous_ptr);
+
+/**
+ * kfifo_commit_ptr - commits the previous reserved space in the FIFO
+ * @fifo: the fifo to be used.
+ * @ptr: pointer to the previous reserved space
+ *
+ * This functions makes the previous reserved space pointed by @ptr
+ * into FIFO and can be consumed by reader.
+ */
+void kfifo_commit_ptr(struct kfifo *fifo, void *ptr)
+{
+	unsigned int pos, in;
+
+	pos = ptr - (void *)fifo->buffer;
+	BUG_ON(pos >= fifo->size);
+	in = fifo->in;
+	pos += in & ~(fifo->size - 1);
+	if (pos < in)
+		pos += fifo->size;
+
+	kfifo_commit(fifo, pos);
+}
+EXPORT_SYMBOL_GPL(kfifo_commit_ptr);

Re: [RFC] kfifo writer side lock-less support

[Stefani Seibold]

Hi Huang,

it would be great if you could post an example code how to use your
code.

Stefani

Am Dienstag, den 08.06.2010, 14:45 +0800 schrieb Huang Ying:
> This patch add lock-less support for kfifo writer side amongst
> different contexts on one CPU, such as NMI, IRQ, soft_irq, process,
> etc. This makes kfifo can be used to implement per-CPU lock-less data
> structure.
> 
> The different contexts on one CPU have some kind of preemption
> priority as follow:
> 
> process -> soft_irq -> IRQ -> NMI
> 
> Where preemption priority increases from left to right. That is, the
> right side context can preempt left side context, but not in the
> reverse direction, that means the right side context will run to the
> end before return to the left side context. The lock-less algorithm
> used in the patch take advantage of this.
> 
> The algorithm works in reserve/commit style, where "reserve" only
> allocate the space, while "commit" really makes the data into buffer,
> data is prepared in between. cmpxchg is used in "reserve", this
> guarantees different spaces will be allocated for different
> contexts. Only the "commit" in lowest context will commit all
> allocated spaces. Because all contexts preempting lowest context
> between "reserve" and "commit" will run to the end, all data put into
> buffer are valid.
> 
> Some idea of the lock-less algorithm in the patch comes from Steven
> Rostedt's trace ring buffer implementation.
> 
> The new xxx_ptr interface and kfifo_iter makes it possible to
> write/read content of kfifo in-place in addition to copying out/in.
> 
> Signed-off-by: Huang Ying <ying.huang@intel.com>
> ---
>  include/linux/kfifo.h |   87 +++++++++++++++++-
>  kernel/kfifo.c        |  231 ++++++++++++++++++++++++++++++++++++++++++++++++--
>  2 files changed, 305 insertions(+), 13 deletions(-)
> 
> --- a/include/linux/kfifo.h
> +++ b/include/linux/kfifo.h
> @@ -49,6 +49,7 @@ struct kfifo {
>  	unsigned int size;	/* the size of the allocated buffer */
>  	unsigned int in;	/* data is added at offset (in % size) */
>  	unsigned int out;	/* data is extracted from off. (out % size) */
> +	unsigned int reserve;	/* space is reserved at off (reserve % size) */
>  };
>  
>  /*
> @@ -60,6 +61,7 @@ struct kfifo {
>  	(struct kfifo) { \
>  		.size	= s, \
>  		.in	= 0, \
> +		.reserve = 0, \
>  		.out	= 0, \
>  		.buffer = b \
>  	}
> @@ -132,7 +134,7 @@ static inline bool kfifo_initialized(str
>   */
>  static inline void kfifo_reset(struct kfifo *fifo)
>  {
> -	fifo->in = fifo->out = 0;
> +	fifo->reserve = fifo->in = fifo->out = 0;
>  }
>  
>  /**
> @@ -167,6 +169,18 @@ static inline unsigned int kfifo_len(str
>  	return fifo->in - out;
>  }
>  
> +/*
> + * returns the number of used bytes (including reserved) in the FIFO
> + */
> +static inline unsigned int __kfifo_used(struct kfifo *fifo)
> +{
> +	register unsigned int	out;
> +
> +	out = fifo->out;
> +	smp_rmb();
> +	return fifo->reserve - out;
> +}
> +
>  /**
>   * kfifo_is_empty - returns true if the fifo is empty
>   * @fifo: the fifo to be used.
> @@ -182,7 +196,7 @@ static inline __must_check int kfifo_is_
>   */
>  static inline __must_check int kfifo_is_full(struct kfifo *fifo)
>  {
> -	return kfifo_len(fifo) == kfifo_size(fifo);
> +	return __kfifo_used(fifo) == kfifo_size(fifo);
>  }
>  
>  /**
> @@ -191,7 +205,7 @@ static inline __must_check int kfifo_is_
>   */
>  static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
>  {
> -	return kfifo_size(fifo) - kfifo_len(fifo);
> +	return kfifo_size(fifo) - __kfifo_used(fifo);
>  }
>  
>  /**
> @@ -269,6 +283,7 @@ static inline void __kfifo_add_out(struc
>  static inline void __kfifo_add_in(struct kfifo *fifo,
>  				unsigned int off)
>  {
> +	fifo->reserve += off;
>  	smp_wmb();
>  	fifo->in += off;
>  }
> @@ -283,6 +298,15 @@ static inline unsigned int __kfifo_off(s
>  }
>  
>  /*
> + * __kfifo_ptr internal helper function to get pointer at the position
> + * for in-place accessing
> + */
> +static inline void *__kfifo_ptr(struct kfifo *fifo, unsigned int pos)
> +{
> +	return fifo->buffer + __kfifo_off(fifo, pos);
> +}
> +
> +/*
>   * __kfifo_peek_n internal helper function for determinate the length of
>   * the next record in the fifo
>   */
> @@ -607,9 +631,64 @@ static inline void kfifo_skip_rec(struct
>  static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
>  	unsigned int recsize)
>  {
> -	unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);
> +	unsigned int l = kfifo_size(fifo) - __kfifo_used(fifo);
>  
>  	return (l > recsize) ? l - recsize : 0;
>  }
>  
> +extern __must_check int kfifo_reserve(struct kfifo *fifo,
> +	unsigned int len, unsigned int *ppos);
> +extern void kfifo_commit(struct kfifo *fifo, unsigned int pos);
> +extern void kfifo_in_data(struct kfifo *fifo, const void *from,
> +	unsigned int len, unsigned int off);
> +extern unsigned int kfifo_ll_in(struct kfifo *fifo, const void *from,
> +	unsigned int len);
> +extern __must_check void *kfifo_reserve_continuous_ptr(struct kfifo *fifo,
> +	unsigned int *len);
> +extern void kfifo_commit_ptr(struct kfifo *fifo, void *ptr);
> +
> +struct kfifo_iter {
> +	struct kfifo *fifo;
> +	unsigned int pos;
> +};
> +
> +/**
> + * kfifo_iter_init - initialize a FIFO iterator
> + * @iter: the iterator to be initialized
> + * @fifo: the fifo to be accessed
> + *
> + */
> +static inline void kfifo_iter_init(struct kfifo_iter *iter, struct kfifo *fifo)
> +{
> +	iter->fifo = fifo;
> +	iter->pos = fifo->out;
> +}
> +
> +/**
> + * kfifo_iter_advance - advances the position of iterator
> + * @iter: the iterator to be used
> + * @adv: the bytes to advance
> + *
> + * This function advances the position of iterator by @adv bytes,
> + * usually goes to the position of the next record.
> + */
> +static inline void kfifo_iter_advance(struct kfifo_iter *iter, unsigned int adv)
> +{
> +	iter->pos += adv;
> +}
> +
> +/**
> + * kfifo_iter_get_ptr - gets the pointer to the current position of iterator
> + * @iter: the iterator to be used
> + *
> + * This function returns the pointer to the current position of
> + * iterator. If the iterator is at the end of FIFO, NULL is
> + * returned. This is used to access the data/records in FIFO in-place.
> + */
> +static inline void *kfifo_iter_get_ptr(struct kfifo_iter *iter)
> +{
> +	if (iter->pos == iter->fifo->in)
> +		return NULL;
> +	return __kfifo_ptr(iter->fifo, iter->pos);
> +}
>  #endif
> --- a/kernel/kfifo.c
> +++ b/kernel/kfifo.c
> @@ -116,8 +116,18 @@ void kfifo_skip(struct kfifo *fifo, unsi
>  }
>  EXPORT_SYMBOL(kfifo_skip);
>  
> -static inline void __kfifo_in_data(struct kfifo *fifo,
> -		const void *from, unsigned int len, unsigned int off)
> +/**
> + * kfifo_in_data - copies some data into FIFO
> + * @fifo: the fifo to be used.
> + * @from: the data to be copied
> + * @len: length of the data to be copied
> + * @off: the offset in FIFO, to which the data is copied
> + *
> + * This function copied @len bytes from the @from buffer into the @off
> + * position of the FIFO.
> + */
> +void kfifo_in_data(struct kfifo *fifo, const void *from, unsigned int len,
> +	unsigned int off)
>  {
>  	unsigned int l;
>  
> @@ -128,7 +138,7 @@ static inline void __kfifo_in_data(struc
>  
>  	smp_mb();
>  
> -	off = __kfifo_off(fifo, fifo->in + off);
> +	off = __kfifo_off(fifo, off);
>  
>  	/* first put the data starting from fifo->in to buffer end */
>  	l = min(len, fifo->size - off);
> @@ -137,6 +147,7 @@ static inline void __kfifo_in_data(struc
>  	/* then put the rest (if any) at the beginning of the buffer */
>  	memcpy(fifo->buffer, from + l, len - l);
>  }
> +EXPORT_SYMBOL_GPL(kfifo_in_data);
>  
>  static inline void __kfifo_out_data(struct kfifo *fifo,
>  		void *to, unsigned int len, unsigned int off)
> @@ -150,7 +161,7 @@ static inline void __kfifo_out_data(stru
>  
>  	smp_rmb();
>  
> -	off = __kfifo_off(fifo, fifo->out + off);
> +	off = __kfifo_off(fifo, off);
>  
>  	/* first get the data from fifo->out until the end of the buffer */
>  	l = min(len, fifo->size - off);
> @@ -232,7 +243,7 @@ unsigned int __kfifo_in_n(struct kfifo *
>  	if (kfifo_avail(fifo) < len + recsize)
>  		return len + 1;
>  
> -	__kfifo_in_data(fifo, from, len, recsize);
> +	kfifo_in_data(fifo, from, len, fifo->in + recsize);
>  	return 0;
>  }
>  EXPORT_SYMBOL(__kfifo_in_n);
> @@ -255,7 +266,7 @@ unsigned int kfifo_in(struct kfifo *fifo
>  {
>  	len = min(kfifo_avail(fifo), len);
>  
> -	__kfifo_in_data(fifo, from, len, 0);
> +	kfifo_in_data(fifo, from, len, fifo->in);
>  	__kfifo_add_in(fifo, len);
>  	return len;
>  }
> @@ -274,7 +285,7 @@ unsigned int __kfifo_out_n(struct kfifo
>  	if (kfifo_len(fifo) < len + recsize)
>  		return len;
>  
> -	__kfifo_out_data(fifo, to, len, recsize);
> +	__kfifo_out_data(fifo, to, len, fifo->out + recsize);
>  	__kfifo_add_out(fifo, len + recsize);
>  	return 0;
>  }
> @@ -296,7 +307,7 @@ unsigned int kfifo_out(struct kfifo *fif
>  {
>  	len = min(kfifo_len(fifo), len);
>  
> -	__kfifo_out_data(fifo, to, len, 0);
> +	__kfifo_out_data(fifo, to, len, fifo->out);
>  	__kfifo_add_out(fifo, len);
>  
>  	return len;
> @@ -319,7 +330,7 @@ unsigned int kfifo_out_peek(struct kfifo
>  {
>  	len = min(kfifo_len(fifo), len + offset);
>  
> -	__kfifo_out_data(fifo, to, len, offset);
> +	__kfifo_out_data(fifo, to, len, fifo->out + offset);
>  	return len;
>  }
>  EXPORT_SYMBOL(kfifo_out_peek);
> @@ -443,3 +454,205 @@ void __kfifo_skip_generic(struct kfifo *
>  }
>  EXPORT_SYMBOL(__kfifo_skip_generic);
>  
> +/**
> + * kfifo_reserve - reserves some space in the FIFO
> + * @fifo: the fifo to be used.
> + * @len: the length of space to be reserved.
> + * @ppos: return position of the reserved space.
> + *
> + * This function reserves space of @len bytes in the FIFO. The
> + * position of the reserved space is returned in @ppos. After the
> + * space is reserved, the data can be copied into reserved space with
> + * kfifo_in_data, and finally put into FIFO with kfifo_commit.
> + *
> + * This function must be paired with kfifo_commit, unless 0 is
> + * returned, which means no space is reserved.
> + *
> + * If the FIFO is used only on one CPU, kfifo_reserve/kfifo_commit
> + * pair can be used by different contexts such as NMI, IRQ, soft_irq
> + * and process (with preempt off) simultaneously safely without any
> + * locking or interrupt disabling.
> + *
> + * Preempt must be disabled between kfifo_reserve and kfifo_commit in
> + * process context for lock-less usage.
> + *
> + * Return 1 if success; return 0 if no enough space, nothing will be
> + * reserved.
> + */
> +int kfifo_reserve(struct kfifo *fifo,
> +	unsigned int len, unsigned int *ppos)
> +{
> +	unsigned int pos, npos;
> +
> +	npos = fifo->reserve;
> +	do {
> +		pos = npos;
> +		if (kfifo_size(fifo) - (pos - fifo->out) < len)
> +			return 0;
> +		npos = cmpxchg(&fifo->reserve, pos, pos + len);
> +	} while (npos != pos);
> +	*ppos = pos;
> +
> +	return 1;
> +}
> +EXPORT_SYMBOL_GPL(kfifo_reserve);
> +
> +/**
> + * kfifo_commit - commits the previous reserved space in the FIFO
> + * @fifo: the fifo to be used.
> + * @pos: position of the previous reserved space
> + *
> + * This function makes the data in previous reserved space at @pos
> + * into FIFO and can be consumed by reader.
> + */
> +void kfifo_commit(struct kfifo *fifo, unsigned int pos)
> +{
> +	unsigned int in, nin, reserve;
> +
> +	if (fifo->in == pos) {
> +		/* fifo->in must be updated after data */
> +		smp_wmb();
> +		do {
> +			in = fifo->in;
> +			/*
> +			 * fifo->in must be read before fifo->reserve,
> +			 * otherwise "in" may go beyond "reserve".
> +			 */
> +			rmb();
> +			reserve = fifo->reserve;
> +			/*
> +			 * If preempted here, fifo->reserve may go
> +			 * beyond reserve, this must be checked after
> +			 * fifo->in assignment.
> +			 */
> +			nin = cmpxchg(&fifo->in, in, reserve);
> +			/*
> +			 * If preempted here, fifo->reserve != reserve
> +			 * too, fifo->in need change with cmpxchg to
> +			 * prevent fifo->in go backwards.
> +			 */
> +		} while (reserve != fifo->reserve || in != nin);
> +	}
> +}
> +EXPORT_SYMBOL_GPL(kfifo_commit);
> +
> +/**
> + * kfifo_ll_in - puts some data into the FIFO, lock-less version
> + * @fifo: the fifo to be used.
> + * @from: the data to be added.
> + * @len: the length of the data to be added.
> + *
> + * This function puts @len bytes from @from buffer into the FIFO. If
> + * it is used on one CPU, the function can be used simultaneously by
> + * multiple contexts such as NMI, IRQ, soft_irq, process, etc safely
> + * without any locking or interrupt disabling.
> + *
> + * Return @len if success, 0 if no enough space
> + */
> +unsigned int kfifo_ll_in(struct kfifo *fifo, const void *from, unsigned int len)
> +{
> +	unsigned int pos;
> +
> +	preempt_disable();
> +	if (!kfifo_reserve(fifo, len, &pos))
> +		return 0;
> +	kfifo_in_data(fifo, from, len, pos);
> +	kfifo_commit(fifo, pos);
> +	preempt_enable_no_resched();
> +	return len;
> +}
> +EXPORT_SYMBOL_GPL(kfifo_ll_in);
> +
> +/*
> + * Reserves some continuous spaces in the FIFO.
> + */
> +static int kfifo_reserve_continuous(struct kfifo *fifo,
> +	unsigned int *rlen, unsigned int *ppos)
> +{
> +	unsigned int pos, npos, l, to_end, avail, len = *rlen;
> +
> +	npos = fifo->reserve;
> +	do {
> +		pos = npos;
> +		avail = kfifo_size(fifo) - (pos - fifo->out);
> +		if (avail < len)
> +			return 0;
> +		to_end = kfifo_size(fifo) - __kfifo_off(fifo, pos);
> +		if (to_end < len) {
> +			if (avail - to_end < len)
> +				return 0;
> +			l = to_end;
> +		} else
> +			l = len;
> +		npos = cmpxchg(&fifo->reserve, pos, pos + l);
> +	} while (npos != pos);
> +	*ppos = pos;
> +	*rlen = l;
> +
> +	return 1;
> +}
> +
> +/**
> + * kfifo_reserve_continuous_ptr - reserves some continuous space in the FIFO
> + * @fifo: the fifo to be used.
> + * @len: the length of space to be reserved, also used to return
> + *       actual reserved length.
> + *
> + * This function reserves some continuous space of at most @len bytes
> + * in the FIFO, and return the pointer to the space. So the reserved
> + * space can be accessed "in-place", until they are committed with
> + * kfifo_commit_ptr. The resulting FIFO layout also makes it possible
> + * to be read in-place.
> + *
> + * There may be two separated free spaces in FIFO, at begin and end of
> + * the buffer. If both are not big enough, NULL will return. If the
> + * free space at end is not but the free space at begin is big enough,
> + * the free space at end will be return, with @len set to actual
> + * length. Otherwise, @len will not be changed, and free space with
> + * length @len will be returned.
> + *
> + * This function must be paired with kfifo_commit_ptr, unless NULL is
> + * returned, which means no space is reserved.
> + *
> + * If the FIFO is used only on one CPU,
> + * kfifo_reserve_continuous_ptr/kfifo_commit_ptr pair can be used by
> + * different contexts such as NMI, IRQ, soft_irq and process (with
> + * preempt off) simultaneously and safely without any locking or
> + * interrupt disabling.
> + *
> + * Preempt must be disabled between kfifo_reserve_continuous_ptr and
> + * kfifo_commit_ptr in process context for lock-less usage.
> + */
> +void *kfifo_reserve_continuous_ptr(struct kfifo *fifo,
> +	unsigned int *len)
> +{
> +	unsigned int pos;
> +
> +	if (!kfifo_reserve_continuous(fifo, len, &pos))
> +		return NULL;
> +	return __kfifo_ptr(fifo, pos);
> +}
> +EXPORT_SYMBOL_GPL(kfifo_reserve_continuous_ptr);
> +
> +/**
> + * kfifo_commit_ptr - commits the previous reserved space in the FIFO
> + * @fifo: the fifo to be used.
> + * @ptr: pointer to the previous reserved space
> + *
> + * This functions makes the previous reserved space pointed by @ptr
> + * into FIFO and can be consumed by reader.
> + */
> +void kfifo_commit_ptr(struct kfifo *fifo, void *ptr)
> +{
> +	unsigned int pos, in;
> +
> +	pos = ptr - (void *)fifo->buffer;
> +	BUG_ON(pos >= fifo->size);
> +	in = fifo->in;
> +	pos += in & ~(fifo->size - 1);
> +	if (pos < in)
> +		pos += fifo->size;
> +
> +	kfifo_commit(fifo, pos);
> +}
> +EXPORT_SYMBOL_GPL(kfifo_commit_ptr);
> 
> 

Re: [RFC] kfifo writer side lock-less support

[Huang Ying]

[-- Attachment #1: Type: text/plain, Size: 285 bytes --]

Hi, Stefani,

On Wed, 2010-06-09 at 03:01 +0800, Stefani Seibold wrote:
> Hi Huang,
> 
> it would be great if you could post an example code how to use your
> code.

The file attached is the testing code I used. Is it a good example from
your point of view?

Best Regards,
Huang Ying


[-- Attachment #2: kfifo_test.c --]
[-- Type: text/x-csrc, Size: 6243 bytes --]

/* kfifo_test.c */

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kfifo.h>
#include <linux/random.h>
#include <linux/sched.h>
#include <linux/kthread.h>

#define KTPFX		"kfifo_test: "

#define FIFO_SIZE	PAGE_SIZE

#define IN_LEN_BITS	8
#define IN_LEN_MASK	((1<<IN_LEN_BITS) - 1)
#define IN_LEN_SHIFT	13
#define IN_LEN_MAX	(1<<IN_LEN_BITS)

#define IN_LEN_MEAN	(IN_LEN_MAX >> 1)

#define RECORDS_MEAN	(FIFO_SIZE / IN_LEN_MEAN)

#define IO_NUM_MAX	(RECORDS_MEAN * 3 / 2)

static char fifo_page[FIFO_SIZE];

static int test_intvl = 10;

static struct timer_list test_timer;
static int test_exiting;
static struct kfifo test_fifo;

static atomic_t test_added;
static atomic_t test_deled;
static atomic_t test_timer_added;
static atomic_t test_overlapped;

static atomic_t test_freezed;

static int test_ptr;

static unsigned int random_inl(void)
{
	u32 rand;

	rand = random32();

	rand = (rand >> IN_LEN_SHIFT) & IN_LEN_MASK;
	if (!rand)
		rand = 1;
	return rand;
}

static unsigned int random_io_num(void)
{
	u32 rand;

	rand = random32();
	rand = ((rand&0xff)<<24) | ((rand&0xff00)<<8) |
		((rand&0xff0000)>>8) | ((rand&0xff000000)>>24);
	return rand % IO_NUM_MAX;
}

static unsigned int kfifo_ll_in_one_random(struct kfifo *fifo)
{
	unsigned char in_buf[IN_LEN_MAX];
	unsigned int i, inl, rc;

	inl = random_inl();
	for (i = 0; i < inl; i++)
		in_buf[i] = inl;
	rc = kfifo_ll_in(fifo, in_buf, inl);
	if (rc)
		atomic_inc(&test_added);
	return rc;
}

static unsigned int kfifo_check_and_skip_one(struct kfifo *fifo)
{
	unsigned char out_buf[IN_LEN_MAX];
	unsigned int i, skipl, len;

	len = kfifo_len(fifo);
	if (!len)
		return 0;
	i = kfifo_out_peek(fifo, out_buf, 1, 0);
	skipl = out_buf[0];
	if (len < skipl) {
		pr_info(KTPFX "len: %u, skipl: %u\n", len, skipl);
		BUG();
	}
	i = kfifo_out_peek(fifo, out_buf, skipl, 0);
	for (i = 0; i < skipl; i++)
		BUG_ON(out_buf[i] != skipl);
	kfifo_skip(fifo, skipl);
	atomic_inc(&test_deled);

	return skipl;
}

#define kfifo_check_ptr(fifo, p)					\
	{								\
	if (p < fifo->buffer || p + *p > fifo->buffer + fifo->size) {	\
		pr_info(KTPFX "fifo->buffer: %p, p: %p, *p: %u\n",	\
			fifo->buffer, p, *p);				\
		BUG();							\
	}								\
}

static unsigned int kfifo_ll_in_one_random_ptr(struct kfifo *fifo)
{
	unsigned char *p;
	unsigned int i, inl;

	inl = random_inl();
	preempt_disable();
	p = kfifo_reserve_continuous_ptr(fifo, &inl);
	if (!p) {
		preempt_enable_no_resched();
		return 0;
	}
	for (i = 0; i < inl; i++)
		p[i] = inl;
	kfifo_commit_ptr(fifo, p);
	kfifo_check_ptr(fifo, p);
	preempt_enable_no_resched();
	atomic_inc(&test_added);
	return inl;
}

static unsigned int kfifo_check_and_skip_one_ptr(struct kfifo *fifo)
{
	unsigned char *p;
	unsigned int i;
	struct kfifo_iter iter;

	kfifo_iter_init(&iter, fifo);
	p = kfifo_iter_get_ptr(&iter);
	if (!p)
		return 0;
#if 1
	while (p) {
		kfifo_check_ptr(fifo, p);
		for (i = 1; i < *p; i++)
			BUG_ON(p[i] != *p);
		kfifo_iter_advance(&iter, *p);
		p = kfifo_iter_get_ptr(&iter);
	}
	kfifo_iter_init(&iter, fifo);
	p = kfifo_iter_get_ptr(&iter);
#else
	for (i = 0; i < *p; i++)
		BUG_ON(p[i] != *p);
#endif
	kfifo_skip(fifo, *p);

	atomic_inc(&test_deled);

	return *p;
}

static void test_round(struct kfifo *fifo)
{
	unsigned int i, numi, numo;
	unsigned int old_added, old_deled, full, empty;

	numi = random_io_num();
	numo = random_io_num();

	old_added = atomic_read(&test_added);
	old_deled = atomic_read(&test_deled);

	full = kfifo_avail(fifo) < IN_LEN_MAX / 2;

	if (test_ptr) {
		for (i = 0; i < numi; i++)
			kfifo_ll_in_one_random_ptr(fifo);
	} else {
		for (i = 0; i < numi; i++)
			kfifo_ll_in_one_random(fifo);
	}

	if (!full && numi && old_added == atomic_read(&test_added))
		atomic_inc(&test_freezed);

	empty = kfifo_len(fifo) == 0;

	if (test_ptr) {
		for (i = 0; i < numo; i++)
			kfifo_check_and_skip_one_ptr(fifo);
	} else {
		for (i = 0; i < numo; i++)
			kfifo_check_and_skip_one(fifo);
	}

	if (!empty && numo && old_deled == atomic_read(&test_deled))
		atomic_inc(&test_freezed);
}

void test_fifo_init(void)
{
	kfifo_init(&test_fifo, fifo_page, sizeof(fifo_page));
	test_fifo.in = test_fifo.out = test_fifo.reserve = (~0U - PAGE_SIZE);
}

static void simple_test(void)
{
	int i;

	test_fifo_init();
	for (i = 0; i < 100; i++) {
		test_round(&test_fifo);
		schedule();
	}
}

static void test_timer_func(unsigned long data)
{
	if (test_ptr)
		kfifo_ll_in_one_random_ptr(&test_fifo);
	else
		kfifo_ll_in_one_random(&test_fifo);

	if (test_fifo.reserve != test_fifo.in)
		atomic_inc(&test_overlapped);
	atomic_inc(&test_timer_added);
	if (!test_exiting) {
		test_timer.expires = jiffies + 1;
		add_timer_on(&test_timer, 1);
	}
}

static int test_thread1(void *data)
{
	unsigned long until;
	struct completion *comp = data;
	unsigned int i = 0;

	until = jiffies;
	until += msecs_to_jiffies(MSEC_PER_SEC * test_intvl);

	do {
		test_round(&test_fifo);
		if ((i & 0xf) == 0)
			schedule();
	} while ((long)(until - jiffies) > 0);

	complete(comp);

	return 0;
}

static void full_test(void)
{
	struct task_struct *thd;
	struct completion comp;

	atomic_set(&test_added, 0);
	atomic_set(&test_deled, 0);
	atomic_set(&test_timer_added, 0);
	atomic_set(&test_overlapped, 0);
	atomic_set(&test_freezed, 0);

	test_fifo_init();

	test_timer.expires = jiffies + 1;
	add_timer_on(&test_timer, 1);

	init_completion(&comp);
	thd = kthread_create(test_thread1, &comp, "kfifo_tester1");
	if (IS_ERR(thd)) {
		pr_err(KTPFX "Failed to create thread!\n");
		return;
	}
	kthread_bind(thd, 1);
	wake_up_process(thd);
	wait_for_completion(&comp);

	del_timer_sync(&test_timer);

	pr_info(KTPFX
	"%s: added: %u, deled: %u, overlapped: %u of %u, freezed: %u\n",
		test_ptr ? "ptr" : "nor",
		atomic_read(&test_added), atomic_read(&test_deled),
		atomic_read(&test_overlapped), atomic_read(&test_timer_added),
		atomic_read(&test_freezed));
}

static int kfifo_test_init(void)
{
	init_timer(&test_timer);
	test_timer.function = test_timer_func;

	test_ptr = 0;
	simple_test();
	test_ptr = 1;
	simple_test();

	test_ptr = 0;
	full_test();
	test_ptr = 1;
	full_test();

	return 0;
}

static void kfifo_test_exit(void)
{
}

module_init(kfifo_test_init);
module_exit(kfifo_test_exit);

MODULE_LICENSE("GPL");