Re: [PATCH] kfifo: add memory barrier in kfifo to prevent data loss

[Kees Cook <keescook@chromium.org>]

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