Merge branch 'master' into for-next
[linux-2.6.git] / 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