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 @@
