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