Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss
On Thu, Jan 03, 2019 at 07:43:10AM +, xiaoguangrong(Xiao Guangrong) wrote: > On 12/12/18 8:50 AM, Kees Cook wrote: > > On Mon, Dec 10, 2018 at 7:41 PM wrote: > >> > >> From: Yulei Zhang > >> > >> Early this year we spot there may be two issues in kernel > >> kfifo. > >> > >> One is reported by Xiao Guangrong to linux kernel. > >> https://lkml.org/lkml/2018/5/11/58 > >> In current kfifo implementation there are missing memory > >> barrier in the read side, so that without proper barrier > >> between reading the kfifo->in and fetching the data there > >> is potential ordering issue. > >> > >> Beside that, there is another potential issue in kfifo, > >> please consider the following case: > >> at the beginning > >> ring->size = 4 > >> ring->out = 0 > >> ring->in = 4 > >> > >> ConsumerProducer > >> --- -- > >> index = ring->out; /* index == 0 */ > >> ring->out++; /* ring->out == 1 */ > >> < Re-Order > > >> out = ring->out; > >> if (ring->in - out >= ring->mask) > >> return -EFULL; > >> /* see the ring is not full */ > >> index = ring->in & ring->mask; > >> /* index == 0 */ > >> ring->data[index] = new_data; > >> ring->in++; > >> > >> data = ring->data[index]; > >> /* you will find the old data is overwritten by the new_data */ > >> > >> In order to avoid the issue: > >> 1) for the consumer, we should read the ring->data[] out before > >> updating ring->out > >> 2) for the producer, we should read ring->out before updating > >> ring->data[] > >> > >> So in this patch we introduce the following four functions which > >> are wrapped with proper memory barrier and keep in pairs to make > >> sure the in and out index are fetched and updated in order to avoid > >> data loss. > >> > >> kfifo_read_index_in() > >> kfifo_write_index_in() > >> kfifo_read_index_out() > >> kfifo_write_index_out() > >> > >> Signed-off-by: Yulei Zhang > >> Signed-off-by: Guangrong Xiao > > > > I've added some more people to CC that might want to see this. Thanks > > for sending this! > > Hi, > > Ping... could anyone have a look? ;) I've started looking at kfifo, but I suspect it needs a fair amount more work than your patch. Please stay tuned. Will
Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss
On 12/12/18 8:50 AM, Kees Cook wrote: > On Mon, Dec 10, 2018 at 7:41 PM wrote: >> >> From: Yulei Zhang >> >> Early this year we spot there may be two issues in kernel >> kfifo. >> >> One is reported by Xiao Guangrong to linux kernel. >> https://lkml.org/lkml/2018/5/11/58 >> In current kfifo implementation there are missing memory >> barrier in the read side, so that without proper barrier >> between reading the kfifo->in and fetching the data there >> is potential ordering issue. >> >> Beside that, there is another potential issue in kfifo, >> please consider the following case: >> at the beginning >> ring->size = 4 >> ring->out = 0 >> ring->in = 4 >> >> ConsumerProducer >> --- -- >> index = ring->out; /* index == 0 */ >> ring->out++; /* ring->out == 1 */ >> < Re-Order > >> out = ring->out; >> if (ring->in - out >= ring->mask) >> return -EFULL; >> /* see the ring is not full */ >> index = ring->in & ring->mask; >> /* index == 0 */ >> ring->data[index] = new_data; >> ring->in++; >> >> data = ring->data[index]; >> /* you will find the old data is overwritten by the new_data */ >> >> In order to avoid the issue: >> 1) for the consumer, we should read the ring->data[] out before >> updating ring->out >> 2) for the producer, we should read ring->out before updating >> ring->data[] >> >> So in this patch we introduce the following four functions which >> are wrapped with proper memory barrier and keep in pairs to make >> sure the in and out index are fetched and updated in order to avoid >> data loss. >> >> kfifo_read_index_in() >> kfifo_write_index_in() >> kfifo_read_index_out() >> kfifo_write_index_out() >> >> Signed-off-by: Yulei Zhang >> Signed-off-by: Guangrong Xiao > > I've added some more people to CC that might want to see this. Thanks > for sending this! Hi, Ping... could anyone have a look? ;) Thanks!
Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss
Hi Yulei, Thank you for the patch! Perhaps something to improve: [auto build test WARNING on linus/master] [also build test WARNING on v4.20-rc6 next-20181214] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/yulei-kernel-gmail-com/kfifo-add-memory-barrier-in-kfifo-to-prevent-data-loss/20181211-204949 reproduce: make htmldocs All warnings (new ones prefixed by >>): WARNING: convert(1) not found, for SVG to PDF conversion install ImageMagick (https://www.imagemagick.org) >> include/linux/kfifo.h:305: warning: Function parameter or member 'kfifo' not >> described in 'kfifo_read_index_in' include/linux/kfifo.h:305: warning: Excess function parameter 'fifo' description in 'kfifo_read_index_in' >> include/linux/kfifo.h:321: warning: Function parameter or member 'kfifo' not >> described in 'kfifo_write_index_in' >> include/linux/kfifo.h:321: warning: Function parameter or member 'val' not >> described in 'kfifo_write_index_in' include/linux/kfifo.h:321: warning: Excess function parameter 'fifo' description in 'kfifo_write_index_in' >> include/linux/kfifo.h:337: warning: Function parameter or member 'kfifo' not >> described in 'kfifo_read_index_out' include/linux/kfifo.h:337: warning: Excess function parameter 'fifo' description in 'kfifo_read_index_out' >> include/linux/kfifo.h:353: warning: Function parameter or member 'kfifo' not >> described in 'kfifo_write_index_out' >> include/linux/kfifo.h:353: warning: Function parameter or member 'val' not >> described in 'kfifo_write_index_out' include/linux/kfifo.h:353: warning: Excess function parameter 'fifo' description in 'kfifo_write_index_out' include/linux/rcutree.h:1: warning: no structured comments found kernel/rcu/tree.c:684: warning: Excess function parameter 'irq' description in 'rcu_nmi_exit' include/linux/srcu.h:175: warning: Function parameter or member 'p' not described in 'srcu_dereference_notrace' include/linux/srcu.h:175: warning: Function parameter or member 'sp' not described in 'srcu_dereference_notrace' include/linux/gfp.h:1: warning: no structured comments found include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:2838: warning: cannot understand function prototype: 'struct cfg80211_ftm_responder_stats ' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.ibss' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.connect' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.keys' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.ie' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.ie_len' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.bssid' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.ssid' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.default_key' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.default_mgmt_key' not described in 'wireless_dev' include/net/cfg80211.h:4439: warning: Function parameter or member 'wext.prev_bssid_valid' not described in 'wireless_dev' include/net/cfg80211.h:2838: warning: cannot
Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss
On Tue, Dec 11, 2018 at 04:50:34PM -0800, Kees Cook wrote: > On Mon, Dec 10, 2018 at 7:41 PM wrote: > > > > From: Yulei Zhang > > > > Early this year we spot there may be two issues in kernel > > kfifo. > > > > One is reported by Xiao Guangrong to linux kernel. > > https://lkml.org/lkml/2018/5/11/58 > > In current kfifo implementation there are missing memory > > barrier in the read side, so that without proper barrier > > between reading the kfifo->in and fetching the data there > > is potential ordering issue. > > > > Beside that, there is another potential issue in kfifo, > > please consider the following case: > > at the beginning > > ring->size = 4 > > ring->out = 0 > > ring->in = 4 > > > > ConsumerProducer > > --- -- > > index = ring->out; /* index == 0 */ > > ring->out++; /* ring->out == 1 */ > > < Re-Order > > > out = ring->out; > > if (ring->in - out >= ring->mask) > > return -EFULL; > > /* see the ring is not full */ > > index = ring->in & ring->mask; > > /* index == 0 */ > > ring->data[index] = new_data; > > ring->in++; > > > > data = ring->data[index]; > > /* you will find the old data is overwritten by the new_data */ > > > > In order to avoid the issue: > > 1) for the consumer, we should read the ring->data[] out before > > updating ring->out > > 2) for the producer, we should read ring->out before updating > > ring->data[] > > > > So in this patch we introduce the following four functions which > > are wrapped with proper memory barrier and keep in pairs to make > > sure the in and out index are fetched and updated in order to avoid > > data loss. > > > > kfifo_read_index_in() > > kfifo_write_index_in() > > kfifo_read_index_out() > > kfifo_write_index_out() > > > > Signed-off-by: Yulei Zhang > > Signed-off-by: Guangrong Xiao > > I've added some more people to CC that might want to see this. Thanks > for sending this! I haven't looked at the guts of kfifo before and I'm fully prepared to believe that there are ordering problems in there. However, I'm having a hard time matching the implementation to the snippets above. Please could you provide the description of the consumer/producer interaction as above, but annotated with the function/macro names? There are things like kfifo_get() using smp_wmb(), which looks suspicious, but doesn't appear to be what you're reporting here. Thanks, Will
Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss
On Mon, Dec 10, 2018 at 7:41 PM wrote:
>
> From: Yulei Zhang
>
> Early this year we spot there may be two issues in kernel
> kfifo.
>
> One is reported by Xiao Guangrong to linux kernel.
> https://lkml.org/lkml/2018/5/11/58
> In current kfifo implementation there are missing memory
> barrier in the read side, so that without proper barrier
> between reading the kfifo->in and fetching the data there
> is potential ordering issue.
>
> Beside that, there is another potential issue in kfifo,
> please consider the following case:
> at the beginning
> ring->size = 4
> ring->out = 0
> ring->in = 4
>
> ConsumerProducer
> --- --
> index = ring->out; /* index == 0 */
> ring->out++; /* ring->out == 1 */
> < Re-Order >
> out = ring->out;
> if (ring->in - out >= ring->mask)
> return -EFULL;
> /* see the ring is not full */
> index = ring->in & ring->mask;
> /* index == 0 */
> ring->data[index] = new_data;
> ring->in++;
>
> data = ring->data[index];
> /* you will find the old data is overwritten by the new_data */
>
> In order to avoid the issue:
> 1) for the consumer, we should read the ring->data[] out before
> updating ring->out
> 2) for the producer, we should read ring->out before updating
> ring->data[]
>
> So in this patch we introduce the following four functions which
> are wrapped with proper memory barrier and keep in pairs to make
> sure the in and out index are fetched and updated in order to avoid
> data loss.
>
> kfifo_read_index_in()
> kfifo_write_index_in()
> kfifo_read_index_out()
> kfifo_write_index_out()
>
> Signed-off-by: Yulei Zhang
> Signed-off-by: Guangrong Xiao
I've added some more people to CC that might want to see this. Thanks
for sending this!
-Kees
> ---
> include/linux/kfifo.h | 70 ++-
> lib/kfifo.c | 107 +++---
> 2 files changed, 136 insertions(+), 41 deletions(-)
>
> diff --git a/include/linux/kfifo.h b/include/linux/kfifo.h
> index 89fc8dc7bf38..3bd2a869ca7e 100644
> --- a/include/linux/kfifo.h
> +++ b/include/linux/kfifo.h
> @@ -286,6 +286,71 @@ __kfifo_uint_must_check_helper( \
> }) \
> )
>
> +/**
> + * kfifo_read_index_in - returns the in index of the fifo
> + * @fifo: address of the kfifo to be used
> + *
> + * add memory read barrier to make sure the fifo->in index
> + * is fetched first before write data to the fifo, which
> + * is paired with the write barrier in kfifo_write_index_in
> + */
> +#define kfifo_read_index_in(kfifo) \
> +({ \
> + typeof((kfifo) + 1) __tmp = (kfifo); \
> + struct __kfifo *__kfifo = __tmp; \
> + unsigned int __val = READ_ONCE(__kfifo->in); \
> + smp_rmb(); \
> + __val; \
> +})
> +
> +/**
> + * kfifo_write_index_in - updates the in index of the fifo
> + * @fifo: address of the kfifo to be used
> + *
> + * add memory write barrier to make sure the data entry is
> + * updated before increase the fifo->in
> + */
> +#define kfifo_write_index_in(kfifo, val) \
> +({ \
> + typeof((kfifo) + 1) __tmp = (kfifo); \
> + struct __kfifo *__kfifo = __tmp; \
> + unsigned int __val = (val); \
> + smp_wmb(); \
> + WRITE_ONCE(__kfifo->in, __val); \
> +})
> +
> +/**
> + * kfifo_read_index_out - returns the out index of the fifo
> + * @fifo: address of the kfifo to be used
> + *
> + * add memory barrier to make sure the fifo->out index is
> + * fetched before read data from the fifo, which is paired
> + * with the memory barrier in kfifo_write_index_out
> + */
> +#define kfifo_read_index_out(kfifo) \
> +({ \
> + typeof((kfifo) + 1) __tmp = (kfifo); \
> + struct __kfifo *__kfifo = __tmp; \
> + unsigned int __val = smp_load_acquire(&__kfifo->out); \
> + __val; \
> +})
> +
> +/**
> + * kfifo_write_index_out - updates the out index of the fifo
> + * @fifo: address of the kfifo to be used
> + *
> + * add memory barrier to make sure reading out the entry before
> + * update the fifo->out index to avoid overwitten the entry by
> + * the producer
> + */
> +#define kfifo_write_index_out(kfifo, val) \
> +({ \
> + typeof((kfifo) + 1) __tmp = (kfifo); \
> + struct __kfifo *__kfifo = __tmp; \
> + unsigned int __val = (val); \
> + smp_store_release(&__kfifo->out, __val); \
> +})
> +
> /**
> * kfifo_skip - skip output data
> * @fifo: address of the fifo to be used
> @@ -298,7 +363,7 @@ __kfifo_uint_must_check_helper( \
> if (__recsize) \
> __kfifo_skip_r(__kfifo, __recsize); \
> else \
> - __kfifo->out++; \
> + kfifo_write_index_out(__kfifo, __kfifo->out++); \
> })
>
> /**
> @@ -740,7 +805,8 @@
[PATCH] kfifo: add memory barrier in kfifo to prevent data loss
From: Yulei Zhang
Early this year we spot there may be two issues in kernel
kfifo.
One is reported by Xiao Guangrong to linux kernel.
https://lkml.org/lkml/2018/5/11/58
In current kfifo implementation there are missing memory
barrier in the read side, so that without proper barrier
between reading the kfifo->in and fetching the data there
is potential ordering issue.
Beside that, there is another potential issue in kfifo,
please consider the following case:
at the beginning
ring->size = 4
ring->out = 0
ring->in = 4
ConsumerProducer
--- --
index = ring->out; /* index == 0 */
ring->out++; /* ring->out == 1 */
< Re-Order >
out = ring->out;
if (ring->in - out >= ring->mask)
return -EFULL;
/* see the ring is not full */
index = ring->in & ring->mask;
/* index == 0 */
ring->data[index] = new_data;
ring->in++;
data = ring->data[index];
/* you will find the old data is overwritten by the new_data */
In order to avoid the issue:
1) for the consumer, we should read the ring->data[] out before
updating ring->out
2) for the producer, we should read ring->out before updating
ring->data[]
So in this patch we introduce the following four functions which
are wrapped with proper memory barrier and keep in pairs to make
sure the in and out index are fetched and updated in order to avoid
data loss.
kfifo_read_index_in()
kfifo_write_index_in()
kfifo_read_index_out()
kfifo_write_index_out()
Signed-off-by: Yulei Zhang
Signed-off-by: Guangrong Xiao
---
include/linux/kfifo.h | 70 ++-
lib/kfifo.c | 107 +++---
2 files changed, 136 insertions(+), 41 deletions(-)
diff --git a/include/linux/kfifo.h b/include/linux/kfifo.h
index 89fc8dc7bf38..3bd2a869ca7e 100644
--- a/include/linux/kfifo.h
+++ b/include/linux/kfifo.h
@@ -286,6 +286,71 @@ __kfifo_uint_must_check_helper( \
}) \
)
+/**
+ * kfifo_read_index_in - returns the in index of the fifo
+ * @fifo: address of the kfifo to be used
+ *
+ * add memory read barrier to make sure the fifo->in index
+ * is fetched first before write data to the fifo, which
+ * is paired with the write barrier in kfifo_write_index_in
+ */
+#define kfifo_read_index_in(kfifo) \
+({ \
+ typeof((kfifo) + 1) __tmp = (kfifo); \
+ struct __kfifo *__kfifo = __tmp; \
+ unsigned int __val = READ_ONCE(__kfifo->in); \
+ smp_rmb(); \
+ __val; \
+})
+
+/**
+ * kfifo_write_index_in - updates the in index of the fifo
+ * @fifo: address of the kfifo to be used
+ *
+ * add memory write barrier to make sure the data entry is
+ * updated before increase the fifo->in
+ */
+#define kfifo_write_index_in(kfifo, val) \
+({ \
+ typeof((kfifo) + 1) __tmp = (kfifo); \
+ struct __kfifo *__kfifo = __tmp; \
+ unsigned int __val = (val); \
+ smp_wmb(); \
+ WRITE_ONCE(__kfifo->in, __val); \
+})
+
+/**
+ * kfifo_read_index_out - returns the out index of the fifo
+ * @fifo: address of the kfifo to be used
+ *
+ * add memory barrier to make sure the fifo->out index is
+ * fetched before read data from the fifo, which is paired
+ * with the memory barrier in kfifo_write_index_out
+ */
+#define kfifo_read_index_out(kfifo) \
+({ \
+ typeof((kfifo) + 1) __tmp = (kfifo); \
+ struct __kfifo *__kfifo = __tmp; \
+ unsigned int __val = smp_load_acquire(&__kfifo->out); \
+ __val; \
+})
+
+/**
+ * kfifo_write_index_out - updates the out index of the fifo
+ * @fifo: address of the kfifo to be used
+ *
+ * add memory barrier to make sure reading out the entry before
+ * update the fifo->out index to avoid overwitten the entry by
+ * the producer
+ */
+#define kfifo_write_index_out(kfifo, val) \
+({ \
+ typeof((kfifo) + 1) __tmp = (kfifo); \
+ struct __kfifo *__kfifo = __tmp; \
+ unsigned int __val = (val); \
+ smp_store_release(&__kfifo->out, __val); \
+})
+
/**
* kfifo_skip - skip output data
* @fifo: address of the fifo to be used
@@ -298,7 +363,7 @@ __kfifo_uint_must_check_helper( \
if (__recsize) \
__kfifo_skip_r(__kfifo, __recsize); \
else \
- __kfifo->out++; \
+ kfifo_write_index_out(__kfifo, __kfifo->out++); \
})
/**
@@ -740,7 +805,8 @@ __kfifo_uint_must_check_helper( \
if (__recsize) \
__kfifo_dma_out_finish_r(__kfifo, __recsize); \
else \
- __kfifo->out += __len / sizeof(*__tmp->type); \
+ kfifo_write_index_out(__kfifo, __kfifo->out \
+ + (__len / sizeof(*__tmp->type))); \
})
/**
diff --git a/lib/kfifo.c b/lib/kfifo.c
index 015656aa8182..189590d9d614 100644
--- a/lib/kfifo.c
