Messages in this thread | | | From | Kees Cook <> | Date | Tue, 11 Dec 2018 16:50:34 -0800 | Subject | Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss |
| |
On Mon, Dec 10, 2018 at 7:41 PM <yulei.kernel@gmail.com> wrote: > > From: Yulei Zhang <yuleixzhang@tencent.com> > > 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 > > Consumer Producer > --------------- -------------- > 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 <yuleixzhang@tencent.com> > Signed-off-by: Guangrong Xiao <xiaoguangrong@tencent.com>
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_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 > +++ b/lib/kfifo.c > @@ -32,7 +32,12 @@ > */ > static inline unsigned int kfifo_unused(struct __kfifo *fifo) > { > - return (fifo->mask + 1) - (fifo->in - fifo->out); > + /* > + * add memory barrier to make sure the index is fetched > + * before write to the buffer > + */ > + return (fifo->mask + 1) - > + (fifo->in - kfifo_read_index_out(fifo)); > } > > int __kfifo_alloc(struct __kfifo *fifo, unsigned int size, > @@ -116,11 +121,6 @@ static void kfifo_copy_in(struct __kfifo *fifo, const void *src, > > memcpy(fifo->data + off, src, l); > memcpy(fifo->data, src + l, len - l); > - /* > - * make sure that the data in the fifo is up to date before > - * incrementing the fifo->in index counter > - */ > - smp_wmb(); > } > > unsigned int __kfifo_in(struct __kfifo *fifo, > @@ -133,7 +133,11 @@ unsigned int __kfifo_in(struct __kfifo *fifo, > len = l; > > kfifo_copy_in(fifo, buf, len, fifo->in); > - fifo->in += len; > + /* > + * make sure that the data in the fifo is up to date before > + * incrementing the fifo->in index counter > + */ > + kfifo_write_index_in(fifo, fifo->in + len); > return len; > } > EXPORT_SYMBOL(__kfifo_in); > @@ -155,11 +159,6 @@ static void kfifo_copy_out(struct __kfifo *fifo, void *dst, > > memcpy(dst, fifo->data + off, l); > memcpy(dst + l, fifo->data, len - l); > - /* > - * make sure that the data is copied before > - * incrementing the fifo->out index counter > - */ > - smp_wmb(); > } > > unsigned int __kfifo_out_peek(struct __kfifo *fifo, > @@ -167,7 +166,7 @@ unsigned int __kfifo_out_peek(struct __kfifo *fifo, > { > unsigned int l; > > - l = fifo->in - fifo->out; > + l = kfifo_read_index_in(fifo) - fifo->out; > if (len > l) > len = l; > > @@ -180,7 +179,11 @@ unsigned int __kfifo_out(struct __kfifo *fifo, > void *buf, unsigned int len) > { > len = __kfifo_out_peek(fifo, buf, len); > - fifo->out += len; > + /* > + * make sure that the data in the fifo is fetched before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + len); > return len; > } > EXPORT_SYMBOL(__kfifo_out); > @@ -210,11 +213,6 @@ static unsigned long kfifo_copy_from_user(struct __kfifo *fifo, > if (unlikely(ret)) > ret = DIV_ROUND_UP(ret, esize); > } > - /* > - * make sure that the data in the fifo is up to date before > - * incrementing the fifo->in index counter > - */ > - smp_wmb(); > *copied = len - ret * esize; > /* return the number of elements which are not copied */ > return ret; > @@ -241,7 +239,11 @@ int __kfifo_from_user(struct __kfifo *fifo, const void __user *from, > err = -EFAULT; > } else > err = 0; > - fifo->in += len; > + /* > + * make sure that the data in the fifo is up to date before > + * incrementing the fifo->in index counter > + */ > + kfifo_write_index_in(fifo, fifo->in + len); > return err; > } > EXPORT_SYMBOL(__kfifo_from_user); > @@ -270,11 +272,6 @@ static unsigned long kfifo_copy_to_user(struct __kfifo *fifo, void __user *to, > if (unlikely(ret)) > ret = DIV_ROUND_UP(ret, esize); > } > - /* > - * make sure that the data is copied before > - * incrementing the fifo->out index counter > - */ > - smp_wmb(); > *copied = len - ret * esize; > /* return the number of elements which are not copied */ > return ret; > @@ -291,7 +288,7 @@ int __kfifo_to_user(struct __kfifo *fifo, void __user *to, > if (esize != 1) > len /= esize; > > - l = fifo->in - fifo->out; > + l = kfifo_read_index_in(fifo) - fifo->out; > if (len > l) > len = l; > ret = kfifo_copy_to_user(fifo, to, len, fifo->out, copied); > @@ -300,7 +297,11 @@ int __kfifo_to_user(struct __kfifo *fifo, void __user *to, > err = -EFAULT; > } else > err = 0; > - fifo->out += len; > + /* > + * make sure that the data is copied before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + len); > return err; > } > EXPORT_SYMBOL(__kfifo_to_user); > @@ -384,7 +385,7 @@ unsigned int __kfifo_dma_out_prepare(struct __kfifo *fifo, > { > unsigned int l; > > - l = fifo->in - fifo->out; > + l = kfifo_read_index_in(fifo) - fifo->out; > if (len > l) > len = l; > > @@ -457,7 +458,11 @@ unsigned int __kfifo_in_r(struct __kfifo *fifo, const void *buf, > __kfifo_poke_n(fifo, len, recsize); > > kfifo_copy_in(fifo, buf, len, fifo->in + recsize); > - fifo->in += len + recsize; > + /* > + * make sure that the data in the fifo is up to date before > + * incrementing the fifo->in index counter > + */ > + kfifo_write_index_in(fifo, fifo->in + len + recsize); > return len; > } > EXPORT_SYMBOL(__kfifo_in_r); > @@ -479,7 +484,7 @@ unsigned int __kfifo_out_peek_r(struct __kfifo *fifo, void *buf, > { > unsigned int n; > > - if (fifo->in == fifo->out) > + if (kfifo_read_index_in(fifo) == fifo->out) > return 0; > > return kfifo_out_copy_r(fifo, buf, len, recsize, &n); > @@ -491,11 +496,15 @@ unsigned int __kfifo_out_r(struct __kfifo *fifo, void *buf, > { > unsigned int n; > > - if (fifo->in == fifo->out) > + if (kfifo_read_index_in(fifo) == fifo->out) > return 0; > > len = kfifo_out_copy_r(fifo, buf, len, recsize, &n); > - fifo->out += n + recsize; > + /* > + * make sure that the fifo data is fetched before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + n + recsize); > return len; > } > EXPORT_SYMBOL(__kfifo_out_r); > @@ -505,7 +514,11 @@ void __kfifo_skip_r(struct __kfifo *fifo, size_t recsize) > unsigned int n; > > n = __kfifo_peek_n(fifo, recsize); > - fifo->out += n + recsize; > + /* > + * make sure that the fifo data is fetched before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + n + recsize); > } > EXPORT_SYMBOL(__kfifo_skip_r); > > @@ -528,7 +541,11 @@ int __kfifo_from_user_r(struct __kfifo *fifo, const void __user *from, > *copied = 0; > return -EFAULT; > } > - fifo->in += len + recsize; > + /* > + * make sure that the data in the fifo is up to date before > + * incrementing the fifo->in index counter > + */ > + kfifo_write_index_in(fifo, fifo->in + len + recsize); > return 0; > } > EXPORT_SYMBOL(__kfifo_from_user_r); > @@ -539,7 +556,7 @@ int __kfifo_to_user_r(struct __kfifo *fifo, void __user *to, > unsigned long ret; > unsigned int n; > > - if (fifo->in == fifo->out) { > + if (kfifo_read_index_in(fifo) == fifo->out) { > *copied = 0; > return 0; > } > @@ -553,7 +570,11 @@ int __kfifo_to_user_r(struct __kfifo *fifo, void __user *to, > *copied = 0; > return -EFAULT; > } > - fifo->out += n + recsize; > + /* > + * make sure that the data is copied before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + n + recsize); > return 0; > } > EXPORT_SYMBOL(__kfifo_to_user_r); > @@ -577,7 +598,11 @@ void __kfifo_dma_in_finish_r(struct __kfifo *fifo, > { > len = __kfifo_max_r(len, recsize); > __kfifo_poke_n(fifo, len, recsize); > - fifo->in += len + recsize; > + /* > + * make sure that the data in the fifo is updated before > + * incrementing the fifo->in index counter > + */ > + kfifo_write_index_in(fifo, fifo->in + len + recsize); > } > EXPORT_SYMBOL(__kfifo_dma_in_finish_r); > > @@ -588,7 +613,7 @@ unsigned int __kfifo_dma_out_prepare_r(struct __kfifo *fifo, > > len = __kfifo_max_r(len, recsize); > > - if (len + recsize > fifo->in - fifo->out) > + if (len + recsize > kfifo_read_index_in(fifo) - fifo->out) > return 0; > > return setup_sgl(fifo, sgl, nents, len, fifo->out + recsize); > @@ -600,6 +625,10 @@ void __kfifo_dma_out_finish_r(struct __kfifo *fifo, size_t recsize) > unsigned int len; > > len = __kfifo_peek_n(fifo, recsize); > - fifo->out += len + recsize; > + /* > + * make sure that the data is copied before > + * incrementing the fifo->out index counter > + */ > + kfifo_write_index_out(fifo, fifo->out + len + recsize); > } > EXPORT_SYMBOL(__kfifo_dma_out_finish_r); > -- > 2.17.1 >
-- Kees Cook
| |