include/linux/kfifo.h

   1 /*
   2  * A generic kernel FIFO implementation.
   3  *
   4  * Copyright (C) 2009 Stefani Seibold <stefani@seibold.net>
   5  * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20  *
  21  */
  22
  23 /*
  24  * Howto porting drivers to the new generic fifo API:
  25  *
  26  * - Modify the declaration of the "struct kfifo *" object into a
  27  *   in-place "struct kfifo" object
  28  * - Init the in-place object with kfifo_alloc() or kfifo_init()
  29  *   Note: The address of the in-place "struct kfifo" object must be
  30  *   passed as the first argument to this functions
  31  * - Replace the use of __kfifo_put into kfifo_in and __kfifo_get
  32  *   into kfifo_out
  33  * - Replace the use of kfifo_put into kfifo_in_locked and kfifo_get
  34  *   into kfifo_out_locked
  35  *   Note: the spinlock pointer formerly passed to kfifo_init/kfifo_alloc
  36  *   must be passed now to the kfifo_in_locked and kfifo_out_locked
  37  *   as the last parameter.
  38  * - All formerly name __kfifo_* functions has been renamed into kfifo_*
  39  */
  40
  41 #ifndef _LINUX_KFIFO_H
  42 #define _LINUX_KFIFO_H
  43
  44 #include <linux/kernel.h>
  45 #include <linux/spinlock.h>
  46
  47 struct kfifo {
  48         unsigned char *buffer;  /* the buffer holding the data */
  49         unsigned int size;      /* the size of the allocated buffer */
  50         unsigned int in;        /* data is added at offset (in % size) */
  51         unsigned int out;       /* data is extracted from off. (out % size) */
  52 };
  53
  54 /*
  55  * Macros for declaration and initialization of the kfifo datatype
  56  */
  57
  58 /* helper macro */
  59 #define __kfifo_initializer(s, b) \
  60         (struct kfifo) { \
  61                 .size   = s, \
  62                 .in     = 0, \
  63                 .out    = 0, \
  64                 .buffer = b \
  65         }
  66
  67 /**
  68  * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer
  69  * @name: name of the declared kfifo datatype
  70  * @size: size of the fifo buffer. Must be a power of two.
  71  *
  72  * Note1: the macro can be used inside struct or union declaration
  73  * Note2: the macro creates two objects:
  74  *  A kfifo object with the given name and a buffer for the kfifo
  75  *  object named name##kfifo_buffer
  76  */
  77 #define DECLARE_KFIFO(name, size) \
  78 union { \
  79         struct kfifo name; \
  80         unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \
  81 }
  82
  83 /**
  84  * INIT_KFIFO - Initialize a kfifo declared by DECLARE_KFIFO
  85  * @name: name of the declared kfifo datatype
  86  */
  87 #define INIT_KFIFO(name) \
  88         name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \
  89                                 sizeof(struct kfifo), \
  90                                 name##kfifo_buffer + sizeof(struct kfifo))
  91
  92 /**
  93  * DEFINE_KFIFO - macro to define and initialize a kfifo
  94  * @name: name of the declared kfifo datatype
  95  * @size: size of the fifo buffer. Must be a power of two.
  96  *
  97  * Note1: the macro can be used for global and local kfifo data type variables
  98  * Note2: the macro creates two objects:
  99  *  A kfifo object with the given name and a buffer for the kfifo
 100  *  object named name##kfifo_buffer
 101  */
 102 #define DEFINE_KFIFO(name, size) \
 103         unsigned char name##kfifo_buffer[size]; \
 104         struct kfifo name = __kfifo_initializer(size, name##kfifo_buffer)
 105
 106 extern void kfifo_init(struct kfifo *fifo, void *buffer,
 107                         unsigned int size);
 108 extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
 109                         gfp_t gfp_mask);
 110 extern void kfifo_free(struct kfifo *fifo);
 111 extern unsigned int kfifo_in(struct kfifo *fifo,
 112                                 const void *from, unsigned int len);
 113 extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
 114                                 void *to, unsigned int len);
 115 extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
 116                                 void *to, unsigned int len, unsigned offset);
 117
 118 /**
 119  * kfifo_initialized - Check if kfifo is initialized.
 120  * @fifo: fifo to check
 121  * Return %true if FIFO is initialized, otherwise %false.
 122  * Assumes the fifo was 0 before.
 123  */
 124 static inline bool kfifo_initialized(struct kfifo *fifo)
 125 {
 126         return fifo->buffer != NULL;
 127 }
 128
 129 /**
 130  * kfifo_reset - removes the entire FIFO contents
 131  * @fifo: the fifo to be emptied.
 132  */
 133 static inline void kfifo_reset(struct kfifo *fifo)
 134 {
 135         fifo->in = fifo->out = 0;
 136 }
 137
 138 /**
 139  * kfifo_reset_out - skip FIFO contents
 140  * @fifo: the fifo to be emptied.
 141  */
 142 static inline void kfifo_reset_out(struct kfifo *fifo)
 143 {
 144         smp_mb();
 145         fifo->out = fifo->in;
 146 }
 147
 148 /**
 149  * kfifo_size - returns the size of the fifo in bytes
 150  * @fifo: the fifo to be used.
 151  */
 152 static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)
 153 {
 154         return fifo->size;
 155 }
 156
 157 /**
 158  * kfifo_len - returns the number of used bytes in the FIFO
 159  * @fifo: the fifo to be used.
 160  */
 161 static inline unsigned int kfifo_len(struct kfifo *fifo)
 162 {
 163         register unsigned int   out;
 164
 165         out = fifo->out;
 166         smp_rmb();
 167         return fifo->in - out;
 168 }
 169
 170 /**
 171  * kfifo_is_empty - returns true if the fifo is empty
 172  * @fifo: the fifo to be used.
 173  */
 174 static inline __must_check int kfifo_is_empty(struct kfifo *fifo)
 175 {
 176         return fifo->in == fifo->out;
 177 }
 178
 179 /**
 180  * kfifo_is_full - returns true if the fifo is full
 181  * @fifo: the fifo to be used.
 182  */
 183 static inline __must_check int kfifo_is_full(struct kfifo *fifo)
 184 {
 185         return kfifo_len(fifo) == kfifo_size(fifo);
 186 }
 187
 188 /**
 189  * kfifo_avail - returns the number of bytes available in the FIFO
 190  * @fifo: the fifo to be used.
 191  */
 192 static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
 193 {
 194         return kfifo_size(fifo) - kfifo_len(fifo);
 195 }
 196
 197 /**
 198  * kfifo_in_locked - puts some data into the FIFO using a spinlock for locking
 199  * @fifo: the fifo to be used.
 200  * @from: the data to be added.
 201  * @n: the length of the data to be added.
 202  * @lock: pointer to the spinlock to use for locking.
 203  *
 204  * This function copies at most @n bytes from the @from buffer into
 205  * the FIFO depending on the free space, and returns the number of
 206  * bytes copied.
 207  */
 208 static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
 209                 const void *from, unsigned int n, spinlock_t *lock)
 210 {
 211         unsigned long flags;
 212         unsigned int ret;
 213
 214         spin_lock_irqsave(lock, flags);
 215
 216         ret = kfifo_in(fifo, from, n);
 217
 218         spin_unlock_irqrestore(lock, flags);
 219
 220         return ret;
 221 }
 222
 223 /**
 224  * kfifo_out_locked - gets some data from the FIFO using a spinlock for locking
 225  * @fifo: the fifo to be used.
 226  * @to: where the data must be copied.
 227  * @n: the size of the destination buffer.
 228  * @lock: pointer to the spinlock to use for locking.
 229  *
 230  * This function copies at most @n bytes from the FIFO into the
 231  * @to buffer and returns the number of copied bytes.
 232  */
 233 static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
 234         void *to, unsigned int n, spinlock_t *lock)
 235 {
 236         unsigned long flags;
 237         unsigned int ret;
 238
 239         spin_lock_irqsave(lock, flags);
 240
 241         ret = kfifo_out(fifo, to, n);
 242
 243         spin_unlock_irqrestore(lock, flags);
 244
 245         return ret;
 246 }
 247
 248 extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
 249
 250 extern __must_check int kfifo_from_user(struct kfifo *fifo,
 251         const void __user *from, unsigned int n, unsigned *lenout);
 252
 253 extern __must_check int kfifo_to_user(struct kfifo *fifo,
 254         void __user *to, unsigned int n, unsigned *lenout);
 255
 256 /*
 257  * __kfifo_add_out internal helper function for updating the out offset
 258  */
 259 static inline void __kfifo_add_out(struct kfifo *fifo,
 260                                 unsigned int off)
 261 {
 262         smp_mb();
 263         fifo->out += off;
 264 }
 265
 266 /*
 267  * __kfifo_add_in internal helper function for updating the in offset
 268  */
 269 static inline void __kfifo_add_in(struct kfifo *fifo,
 270                                 unsigned int off)
 271 {
 272         smp_wmb();
 273         fifo->in += off;
 274 }
 275
 276 /*
 277  * __kfifo_off internal helper function for calculating the index of a
 278  * given offeset
 279  */
 280 static inline unsigned int __kfifo_off(struct kfifo *fifo, unsigned int off)
 281 {
 282         return off & (fifo->size - 1);
 283 }
 284
 285 /*
 286  * __kfifo_peek_n internal helper function for determinate the length of
 287  * the next record in the fifo
 288  */
 289 static inline unsigned int __kfifo_peek_n(struct kfifo *fifo,
 290                                 unsigned int recsize)
 291 {
 292 #define __KFIFO_GET(fifo, off, shift) \
 293         ((fifo)->buffer[__kfifo_off((fifo), (fifo)->out+(off))] << (shift))
 294
 295         unsigned int l;
 296
 297         l = __KFIFO_GET(fifo, 0, 0);
 298
 299         if (--recsize)
 300                 l |= __KFIFO_GET(fifo, 1, 8);
 301
 302         return l;
 303 #undef  __KFIFO_GET
 304 }
 305
 306 /*
 307  * __kfifo_poke_n internal helper function for storing the length of
 308  * the next record into the fifo
 309  */
 310 static inline void __kfifo_poke_n(struct kfifo *fifo,
 311                         unsigned int recsize, unsigned int n)
 312 {
 313 #define __KFIFO_PUT(fifo, off, val, shift) \
 314                 ( \
 315                 (fifo)->buffer[__kfifo_off((fifo), (fifo)->in+(off))] = \
 316                 (unsigned char)((val) >> (shift)) \
 317                 )
 318
 319         __KFIFO_PUT(fifo, 0, n, 0);
 320
 321         if (--recsize)
 322                 __KFIFO_PUT(fifo, 1, n, 8);
 323 #undef  __KFIFO_PUT
 324 }
 325
 326 /*
 327  * __kfifo_in_... internal functions for put date into the fifo
 328  * do not call it directly, use kfifo_in_rec() instead
 329  */
 330 extern unsigned int __kfifo_in_n(struct kfifo *fifo,
 331         const void *from, unsigned int n, unsigned int recsize);
 332
 333 extern unsigned int __kfifo_in_generic(struct kfifo *fifo,
 334         const void *from, unsigned int n, unsigned int recsize);
 335
 336 static inline unsigned int __kfifo_in_rec(struct kfifo *fifo,
 337         const void *from, unsigned int n, unsigned int recsize)
 338 {
 339         unsigned int ret;
 340
 341         ret = __kfifo_in_n(fifo, from, n, recsize);
 342
 343         if (likely(ret == 0)) {
 344                 if (recsize)
 345                         __kfifo_poke_n(fifo, recsize, n);
 346                 __kfifo_add_in(fifo, n + recsize);
 347         }
 348         return ret;
 349 }
 350
 351 /**
 352  * kfifo_in_rec - puts some record data into the FIFO
 353  * @fifo: the fifo to be used.
 354  * @from: the data to be added.
 355  * @n: the length of the data to be added.
 356  * @recsize: size of record field
 357  *
 358  * This function copies @n bytes from the @from into the FIFO and returns
 359  * the number of bytes which cannot be copied.
 360  * A returned value greater than the @n value means that the record doesn't
 361  * fit into the buffer.
 362  *
 363  * Note that with only one concurrent reader and one concurrent
 364  * writer, you don't need extra locking to use these functions.
 365  */
 366 static inline __must_check unsigned int kfifo_in_rec(struct kfifo *fifo,
 367         void *from, unsigned int n, unsigned int recsize)
 368 {
 369         if (!__builtin_constant_p(recsize))
 370                 return __kfifo_in_generic(fifo, from, n, recsize);
 371         return __kfifo_in_rec(fifo, from, n, recsize);
 372 }
 373
 374 /*
 375  * __kfifo_out_... internal functions for get date from the fifo
 376  * do not call it directly, use kfifo_out_rec() instead
 377  */
 378 extern unsigned int __kfifo_out_n(struct kfifo *fifo,
 379         void *to, unsigned int reclen, unsigned int recsize);
 380
 381 extern unsigned int __kfifo_out_generic(struct kfifo *fifo,
 382         void *to, unsigned int n,
 383         unsigned int recsize, unsigned int *total);
 384
 385 static inline unsigned int __kfifo_out_rec(struct kfifo *fifo,
 386         void *to, unsigned int n, unsigned int recsize,
 387         unsigned int *total)
 388 {
 389         unsigned int l;
 390
 391         if (!recsize) {
 392                 l = n;
 393                 if (total)
 394                         *total = l;
 395         } else {
 396                 l = __kfifo_peek_n(fifo, recsize);
 397                 if (total)
 398                         *total = l;
 399                 if (n < l)
 400                         return l;
 401         }
 402
 403         return __kfifo_out_n(fifo, to, l, recsize);
 404 }
 405
 406 /**
 407  * kfifo_out_rec - gets some record data from the FIFO
 408  * @fifo: the fifo to be used.
 409  * @to: where the data must be copied.
 410  * @n: the size of the destination buffer.
 411  * @recsize: size of record field
 412  * @total: pointer where the total number of to copied bytes should stored
 413  *
 414  * This function copies at most @n bytes from the FIFO to @to and returns the
 415  * number of bytes which cannot be copied.
 416  * A returned value greater than the @n value means that the record doesn't
 417  * fit into the @to buffer.
 418  *
 419  * Note that with only one concurrent reader and one concurrent
 420  * writer, you don't need extra locking to use these functions.
 421  */
 422 static inline __must_check unsigned int kfifo_out_rec(struct kfifo *fifo,
 423         void *to, unsigned int n, unsigned int recsize,
 424         unsigned int *total)
 425
 426 {
 427         if (!__builtin_constant_p(recsize))
 428                 return __kfifo_out_generic(fifo, to, n, recsize, total);
 429         return __kfifo_out_rec(fifo, to, n, recsize, total);
 430 }
 431
 432 /*
 433  * __kfifo_from_user_... internal functions for transfer from user space into
 434  * the fifo. do not call it directly, use kfifo_from_user_rec() instead
 435  */
 436 extern unsigned int __kfifo_from_user_n(struct kfifo *fifo,
 437         const void __user *from, unsigned int n, unsigned int recsize);
 438
 439 extern unsigned int __kfifo_from_user_generic(struct kfifo *fifo,
 440         const void __user *from, unsigned int n, unsigned int recsize);
 441
 442 static inline unsigned int __kfifo_from_user_rec(struct kfifo *fifo,
 443         const void __user *from, unsigned int n, unsigned int recsize)
 444 {
 445         unsigned int ret;
 446
 447         ret = __kfifo_from_user_n(fifo, from, n, recsize);
 448
 449         if (likely(ret == 0)) {
 450                 if (recsize)
 451                         __kfifo_poke_n(fifo, recsize, n);
 452                 __kfifo_add_in(fifo, n + recsize);
 453         }
 454         return ret;
 455 }
 456
 457 /**
 458  * kfifo_from_user_rec - puts some data from user space into the FIFO
 459  * @fifo: the fifo to be used.
 460  * @from: pointer to the data to be added.
 461  * @n: the length of the data to be added.
 462  * @recsize: size of record field
 463  *
 464  * This function copies @n bytes from the @from into the
 465  * FIFO and returns the number of bytes which cannot be copied.
 466  *
 467  * If the returned value is equal or less the @n value, the copy_from_user()
 468  * functions has failed. Otherwise the record doesn't fit into the buffer.
 469  *
 470  * Note that with only one concurrent reader and one concurrent
 471  * writer, you don't need extra locking to use these functions.
 472  */
 473 static inline __must_check unsigned int kfifo_from_user_rec(struct kfifo *fifo,
 474         const void __user *from, unsigned int n, unsigned int recsize)
 475 {
 476         if (!__builtin_constant_p(recsize))
 477                 return __kfifo_from_user_generic(fifo, from, n, recsize);
 478         return __kfifo_from_user_rec(fifo, from, n, recsize);
 479 }
 480
 481 /*
 482  * __kfifo_to_user_... internal functions for transfer fifo data into user space
 483  * do not call it directly, use kfifo_to_user_rec() instead
 484  */
 485 extern unsigned int __kfifo_to_user_n(struct kfifo *fifo,
 486         void __user *to, unsigned int n, unsigned int reclen,
 487         unsigned int recsize);
 488
 489 extern unsigned int __kfifo_to_user_generic(struct kfifo *fifo,
 490         void __user *to, unsigned int n, unsigned int recsize,
 491         unsigned int *total);
 492
 493 static inline unsigned int __kfifo_to_user_rec(struct kfifo *fifo,
 494         void __user *to, unsigned int n,
 495         unsigned int recsize, unsigned int *total)
 496 {
 497         unsigned int l;
 498
 499         if (!recsize) {
 500                 l = n;
 501                 if (total)
 502                         *total = l;
 503         } else {
 504                 l = __kfifo_peek_n(fifo, recsize);
 505                 if (total)
 506                         *total = l;
 507                 if (n < l)
 508                         return l;
 509         }
 510
 511         return __kfifo_to_user_n(fifo, to, n, l, recsize);
 512 }
 513
 514 /**
 515  * kfifo_to_user_rec - gets data from the FIFO and write it to user space
 516  * @fifo: the fifo to be used.
 517  * @to: where the data must be copied.
 518  * @n: the size of the destination buffer.
 519  * @recsize: size of record field
 520  * @total: pointer where the total number of to copied bytes should stored
 521  *
 522  * This function copies at most @n bytes from the FIFO to the @to.
 523  * In case of an error, the function returns the number of bytes which cannot
 524  * be copied.
 525  * If the returned value is equal or less the @n value, the copy_to_user()
 526  * functions has failed. Otherwise the record doesn't fit into the @to buffer.
 527  *
 528  * Note that with only one concurrent reader and one concurrent
 529  * writer, you don't need extra locking to use these functions.
 530  */
 531 static inline __must_check unsigned int kfifo_to_user_rec(struct kfifo *fifo,
 532                 void __user *to, unsigned int n, unsigned int recsize,
 533                 unsigned int *total)
 534 {
 535         if (!__builtin_constant_p(recsize))
 536                 return __kfifo_to_user_generic(fifo, to, n, recsize, total);
 537         return __kfifo_to_user_rec(fifo, to, n, recsize, total);
 538 }
 539
 540 /*
 541  * __kfifo_peek_... internal functions for peek into the next fifo record
 542  * do not call it directly, use kfifo_peek_rec() instead
 543  */
 544 extern unsigned int __kfifo_peek_generic(struct kfifo *fifo,
 545                                 unsigned int recsize);
 546
 547 /**
 548  * kfifo_peek_rec - gets the size of the next FIFO record data
 549  * @fifo: the fifo to be used.
 550  * @recsize: size of record field
 551  *
 552  * This function returns the size of the next FIFO record in number of bytes
 553  */
 554 static inline __must_check unsigned int kfifo_peek_rec(struct kfifo *fifo,
 555         unsigned int recsize)
 556 {
 557         if (!__builtin_constant_p(recsize))
 558                 return __kfifo_peek_generic(fifo, recsize);
 559         if (!recsize)
 560                 return kfifo_len(fifo);
 561         return __kfifo_peek_n(fifo, recsize);
 562 }
 563
 564 /*
 565  * __kfifo_skip_... internal functions for skip the next fifo record
 566  * do not call it directly, use kfifo_skip_rec() instead
 567  */
 568 extern void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize);
 569
 570 static inline void __kfifo_skip_rec(struct kfifo *fifo,
 571         unsigned int recsize)
 572 {
 573         unsigned int l;
 574
 575         if (recsize) {
 576                 l = __kfifo_peek_n(fifo, recsize);
 577
 578                 if (l + recsize <= kfifo_len(fifo)) {
 579                         __kfifo_add_out(fifo, l + recsize);
 580                         return;
 581                 }
 582         }
 583         kfifo_reset_out(fifo);
 584 }
 585
 586 /**
 587  * kfifo_skip_rec - skip the next fifo out record
 588  * @fifo: the fifo to be used.
 589  * @recsize: size of record field
 590  *
 591  * This function skips the next FIFO record
 592  */
 593 static inline void kfifo_skip_rec(struct kfifo *fifo,
 594         unsigned int recsize)
 595 {
 596         if (!__builtin_constant_p(recsize))
 597                 __kfifo_skip_generic(fifo, recsize);
 598         else
 599                 __kfifo_skip_rec(fifo, recsize);
 600 }
 601
 602 /**
 603  * kfifo_avail_rec - returns the number of bytes available in a record FIFO
 604  * @fifo: the fifo to be used.
 605  * @recsize: size of record field
 606  */
 607 static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
 608         unsigned int recsize)
 609 {
 610         unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);
 611
 612         return (l > recsize) ? l - recsize : 0;
 613 }
 614
 615 #endif