kernel/kfifo.c

   1 /*
   2  * A simple kernel FIFO implementation.
   3  *
   4  * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  *
  20  */
  21
  22 #include <linux/kernel.h>
  23 #include <linux/module.h>
  24 #include <linux/slab.h>
  25 #include <linux/err.h>
  26 #include <linux/kfifo.h>
  27 #include <linux/log2.h>
  28 #include <linux/uaccess.h>
  29
  30 /**
  31  * kfifo_init - allocates a new FIFO using a preallocated buffer
  32  * @buffer: the preallocated buffer to be used.
  33  * @size: the size of the internal buffer, this have to be a power of 2.
  34  * @gfp_mask: get_free_pages mask, passed to kmalloc()
  35  * @lock: the lock to be used to protect the fifo buffer
  36  *
  37  * Do NOT pass the kfifo to kfifo_free() after use! Simply free the
  38  * &struct kfifo with kfree().
  39  */
  40 struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
  41                          gfp_t gfp_mask, spinlock_t *lock)
  42 {
  43         struct kfifo *fifo;
  44
  45         /* size must be a power of 2 */
  46         BUG_ON(!is_power_of_2(size));
  47
  48         fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
  49         if (!fifo)
  50                 return ERR_PTR(-ENOMEM);
  51
  52         fifo->buffer = buffer;
  53         fifo->size = size;
  54         fifo->in = fifo->out = 0;
  55         fifo->lock = lock;
  56
  57         return fifo;
  58 }
  59 EXPORT_SYMBOL(kfifo_init);
  60
  61 /**
  62  * kfifo_alloc - allocates a new FIFO and its internal buffer
  63  * @size: the size of the internal buffer to be allocated.
  64  * @gfp_mask: get_free_pages mask, passed to kmalloc()
  65  * @lock: the lock to be used to protect the fifo buffer
  66  *
  67  * The size will be rounded-up to a power of 2.
  68  */
  69 struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
  70 {
  71         unsigned char *buffer;
  72         struct kfifo *ret;
  73
  74         /*
  75          * round up to the next power of 2, since our 'let the indices
  76          * wrap' tachnique works only in this case.
  77          */
  78         if (size & (size - 1)) {
  79                 BUG_ON(size > 0x80000000);
  80                 size = roundup_pow_of_two(size);
  81         }
  82
  83         buffer = kmalloc(size, gfp_mask);
  84         if (!buffer)
  85                 return ERR_PTR(-ENOMEM);
  86
  87         ret = kfifo_init(buffer, size, gfp_mask, lock);
  88
  89         if (IS_ERR(ret))
  90                 kfree(buffer);
  91
  92         return ret;
  93 }
  94 EXPORT_SYMBOL(kfifo_alloc);
  95
  96 /**
  97  * kfifo_free - frees the FIFO
  98  * @fifo: the fifo to be freed.
  99  */
 100 void kfifo_free(struct kfifo *fifo)
 101 {
 102         kfree(fifo->buffer);
 103         kfree(fifo);
 104 }
 105 EXPORT_SYMBOL(kfifo_free);
 106
 107 /**
 108  * __kfifo_put - puts some data into the FIFO, no locking version
 109  * @fifo: the fifo to be used.
 110  * @buffer: the data to be added.
 111  * @len: the length of the data to be added.
 112  *
 113  * This function copies at most @len bytes from the @buffer into
 114  * the FIFO depending on the free space, and returns the number of
 115  * bytes copied.
 116  *
 117  * Note that with only one concurrent reader and one concurrent
 118  * writer, you don't need extra locking to use these functions.
 119  */
 120 unsigned int __kfifo_put(struct kfifo *fifo,
 121                          unsigned char *buffer, unsigned int len)
 122 {
 123         unsigned int l;
 124
 125         len = min(len, fifo->size - fifo->in + fifo->out);
 126
 127         /*
 128          * Ensure that we sample the fifo->out index -before- we
 129          * start putting bytes into the kfifo.
 130          */
 131
 132         smp_mb();
 133
 134         /* first put the data starting from fifo->in to buffer end */
 135         l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
 136         memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
 137
 138         /* then put the rest (if any) at the beginning of the buffer */
 139         memcpy(fifo->buffer, buffer + l, len - l);
 140
 141         /*
 142          * Ensure that we add the bytes to the kfifo -before-
 143          * we update the fifo->in index.
 144          */
 145
 146         smp_wmb();
 147
 148         fifo->in += len;
 149
 150         return len;
 151 }
 152 EXPORT_SYMBOL(__kfifo_put);
 153
 154 /**
 155  * __kfifo_get - gets some data from the FIFO, no locking version
 156  * @fifo: the fifo to be used.
 157  * @buffer: where the data must be copied.
 158  * @len: the size of the destination buffer.
 159  *
 160  * This function copies at most @len bytes from the FIFO into the
 161  * @buffer and returns the number of copied bytes.
 162  *
 163  * Note that with only one concurrent reader and one concurrent
 164  * writer, you don't need extra locking to use these functions.
 165  */
 166 unsigned int __kfifo_get(struct kfifo *fifo,
 167                          unsigned char *buffer, unsigned int len)
 168 {
 169         unsigned int l;
 170
 171         len = min(len, fifo->in - fifo->out);
 172
 173         /*
 174          * Ensure that we sample the fifo->in index -before- we
 175          * start removing bytes from the kfifo.
 176          */
 177
 178         smp_rmb();
 179
 180         /* first get the data from fifo->out until the end of the buffer */
 181         l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
 182         memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
 183
 184         /* then get the rest (if any) from the beginning of the buffer */
 185         memcpy(buffer + l, fifo->buffer, len - l);
 186
 187         /*
 188          * Ensure that we remove the bytes from the kfifo -before-
 189          * we update the fifo->out index.
 190          */
 191
 192         smp_mb();
 193
 194         fifo->out += len;
 195
 196         return len;
 197 }
 198 EXPORT_SYMBOL(__kfifo_get);
 199
 200 /**
 201  * __kfifo_get_to_user - gets some data from the FIFO, no locking version
 202  * @fifo: the fifo to be used.
 203  * @buffer: where the data must be copied. user buffer.
 204  * @len: the size of the destination buffer.
 205  *
 206  * This function copies at most @len bytes from the FIFO into the
 207  * user @buffer and returns the number of copied bytes.
 208  *
 209  * Note that with only one concurrent reader and one concurrent
 210  * writer, you don't need extra locking to use these functions.
 211  */
 212 unsigned int __kfifo_get_to_user(struct kfifo *fifo,
 213                                  unsigned char __user *buffer,
 214                                  unsigned int len)
 215 {
 216         unsigned int n1, n2;
 217         int ret;
 218
 219         len = min(len, fifo->in - fifo->out);
 220
 221         /*
 222          * Ensure that we sample the fifo->in index -before- we
 223          * start removing bytes from the kfifo.
 224          */
 225
 226         smp_rmb();
 227
 228         /* first get the data from fifo->out until the end of the buffer */
 229         n1 = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
 230         n2 = len -n1;
 231         ret = copy_to_user(buffer,
 232                            fifo->buffer + (fifo->out & (fifo->size - 1)), n1);
 233         if (ret) {
 234                 len = n1 - ret;
 235                 goto out;
 236         }
 237
 238         /* then get the rest (if any) from the beginning of the buffer */
 239         ret = copy_to_user(buffer + n1, fifo->buffer, n2);
 240         if (ret)
 241                 len = n1 + n2 - ret;
 242
 243         /*
 244          * Ensure that we remove the bytes from the kfifo -before-
 245          * we update the fifo->out index.
 246          */
 247 out:
 248         smp_mb();
 249
 250         fifo->out += len;
 251
 252         return len;
 253 }
 254 EXPORT_SYMBOL(__kfifo_get_to_user);