kfifo: add kfifo_out_peek
[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
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), name##kfifo_buffer)
90
91 /**
92  * DEFINE_KFIFO - macro to define and initialize a kfifo
93  * @name: name of the declared kfifo datatype
94  * @size: size of the fifo buffer
95  *
96  * Note1: the macro can be used for global and local kfifo data type variables
97  * Note2: the macro creates two objects:
98  *  A kfifo object with the given name and a buffer for the kfifo
99  *  object named name##kfifo_buffer
100  */
101 #define DEFINE_KFIFO(name, size) \
102         unsigned char name##kfifo_buffer[size]; \
103         struct kfifo name = __kfifo_initializer(size, name##kfifo_buffer)
104
105 #undef __kfifo_initializer
106
107 extern void kfifo_init(struct kfifo *fifo, void *buffer,
108                         unsigned int size);
109 extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
110                         gfp_t gfp_mask);
111 extern void kfifo_free(struct kfifo *fifo);
112 extern unsigned int kfifo_in(struct kfifo *fifo,
113                                 const void *from, unsigned int len);
114 extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
115                                 void *to, unsigned int len);
116 extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
117                                 void *to, unsigned int len, unsigned offset);
118
119
120 /**
121  * kfifo_reset - removes the entire FIFO contents
122  * @fifo: the fifo to be emptied.
123  */
124 static inline void kfifo_reset(struct kfifo *fifo)
125 {
126         fifo->in = fifo->out = 0;
127 }
128
129 /**
130  * kfifo_reset_out - skip FIFO contents
131  * @fifo: the fifo to be emptied.
132  */
133 static inline void kfifo_reset_out(struct kfifo *fifo)
134 {
135         smp_mb();
136         fifo->out = fifo->in;
137 }
138
139 /**
140  * kfifo_size - returns the size of the fifo in bytes
141  * @fifo: the fifo to be used.
142  */
143 static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)
144 {
145         return fifo->size;
146 }
147
148 /**
149  * kfifo_len - returns the number of used bytes in the FIFO
150  * @fifo: the fifo to be used.
151  */
152 static inline unsigned int kfifo_len(struct kfifo *fifo)
153 {
154         register unsigned int   out;
155
156         out = fifo->out;
157         smp_rmb();
158         return fifo->in - out;
159 }
160
161 /**
162  * kfifo_is_empty - returns true if the fifo is empty
163  * @fifo: the fifo to be used.
164  */
165 static inline __must_check int kfifo_is_empty(struct kfifo *fifo)
166 {
167         return fifo->in == fifo->out;
168 }
169
170 /**
171  * kfifo_is_full - returns true if the fifo is full
172  * @fifo: the fifo to be used.
173  */
174 static inline __must_check int kfifo_is_full(struct kfifo *fifo)
175 {
176         return kfifo_len(fifo) == kfifo_size(fifo);
177 }
178
179 /**
180  * kfifo_avail - returns the number of bytes available in the FIFO
181  * @fifo: the fifo to be used.
182  */
183 static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
184 {
185         return kfifo_size(fifo) - kfifo_len(fifo);
186 }
187
188 /**
189  * kfifo_in_locked - puts some data into the FIFO using a spinlock for locking
190  * @fifo: the fifo to be used.
191  * @from: the data to be added.
192  * @n: the length of the data to be added.
193  * @lock: pointer to the spinlock to use for locking.
194  *
195  * This function copies at most @len bytes from the @from buffer into
196  * the FIFO depending on the free space, and returns the number of
197  * bytes copied.
198  */
199 static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
200                 const void *from, unsigned int n, spinlock_t *lock)
201 {
202         unsigned long flags;
203         unsigned int ret;
204
205         spin_lock_irqsave(lock, flags);
206
207         ret = kfifo_in(fifo, from, n);
208
209         spin_unlock_irqrestore(lock, flags);
210
211         return ret;
212 }
213
214 /**
215  * kfifo_out_locked - gets some data from the FIFO using a spinlock for locking
216  * @fifo: the fifo to be used.
217  * @to: where the data must be copied.
218  * @n: the size of the destination buffer.
219  * @lock: pointer to the spinlock to use for locking.
220  *
221  * This function copies at most @len bytes from the FIFO into the
222  * @to buffer and returns the number of copied bytes.
223  */
224 static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
225         void *to, unsigned int n, spinlock_t *lock)
226 {
227         unsigned long flags;
228         unsigned int ret;
229
230         spin_lock_irqsave(lock, flags);
231
232         ret = kfifo_out(fifo, to, n);
233
234         spin_unlock_irqrestore(lock, flags);
235
236         return ret;
237 }
238
239 extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
240
241 extern __must_check int kfifo_from_user(struct kfifo *fifo,
242         const void __user *from, unsigned int n, unsigned *lenout);
243
244 extern __must_check int kfifo_to_user(struct kfifo *fifo,
245         void __user *to, unsigned int n, unsigned *lenout);
246
247 /*
248  * __kfifo_add_out internal helper function for updating the out offset
249  */
250 static inline void __kfifo_add_out(struct kfifo *fifo,
251                                 unsigned int off)
252 {
253         smp_mb();
254         fifo->out += off;
255 }
256
257 /*
258  * __kfifo_add_in internal helper function for updating the in offset
259  */
260 static inline void __kfifo_add_in(struct kfifo *fifo,
261                                 unsigned int off)
262 {
263         smp_wmb();
264         fifo->in += off;
265 }
266
267 /*
268  * __kfifo_off internal helper function for calculating the index of a
269  * given offeset
270  */
271 static inline unsigned int __kfifo_off(struct kfifo *fifo, unsigned int off)
272 {
273         return off & (fifo->size - 1);
274 }
275
276 /*
277  * __kfifo_peek_n internal helper function for determinate the length of
278  * the next record in the fifo
279  */
280 static inline unsigned int __kfifo_peek_n(struct kfifo *fifo,
281                                 unsigned int recsize)
282 {
283 #define __KFIFO_GET(fifo, off, shift) \
284         ((fifo)->buffer[__kfifo_off((fifo), (fifo)->out+(off))] << (shift))
285
286         unsigned int l;
287
288         l = __KFIFO_GET(fifo, 0, 0);
289
290         if (--recsize)
291                 l |= __KFIFO_GET(fifo, 1, 8);
292
293         return l;
294 #undef  __KFIFO_GET
295 }
296
297 /*
298  * __kfifo_poke_n internal helper function for storing the length of
299  * the next record into the fifo
300  */
301 static inline void __kfifo_poke_n(struct kfifo *fifo,
302                         unsigned int recsize, unsigned int n)
303 {
304 #define __KFIFO_PUT(fifo, off, val, shift) \
305                 ( \
306                 (fifo)->buffer[__kfifo_off((fifo), (fifo)->in+(off))] = \
307                 (unsigned char)((val) >> (shift)) \
308                 )
309
310         __KFIFO_PUT(fifo, 0, n, 0);
311
312         if (--recsize)
313                 __KFIFO_PUT(fifo, 1, n, 8);
314 #undef  __KFIFO_PUT
315 }
316
317 /*
318  * __kfifo_in_... internal functions for put date into the fifo
319  * do not call it directly, use kfifo_in_rec() instead
320  */
321 extern unsigned int __kfifo_in_n(struct kfifo *fifo,
322         const void *from, unsigned int n, unsigned int recsize);
323
324 extern unsigned int __kfifo_in_generic(struct kfifo *fifo,
325         const void *from, unsigned int n, unsigned int recsize);
326
327 static inline unsigned int __kfifo_in_rec(struct kfifo *fifo,
328         const void *from, unsigned int n, unsigned int recsize)
329 {
330         unsigned int ret;
331
332         ret = __kfifo_in_n(fifo, from, n, recsize);
333
334         if (likely(ret == 0)) {
335                 if (recsize)
336                         __kfifo_poke_n(fifo, recsize, n);
337                 __kfifo_add_in(fifo, n + recsize);
338         }
339         return ret;
340 }
341
342 /**
343  * kfifo_in_rec - puts some record data into the FIFO
344  * @fifo: the fifo to be used.
345  * @from: the data to be added.
346  * @n: the length of the data to be added.
347  * @recsize: size of record field
348  *
349  * This function copies @n bytes from the @from into the FIFO and returns
350  * the number of bytes which cannot be copied.
351  * A returned value greater than the @n value means that the record doesn't
352  * fit into the buffer.
353  *
354  * Note that with only one concurrent reader and one concurrent
355  * writer, you don't need extra locking to use these functions.
356  */
357 static inline __must_check unsigned int kfifo_in_rec(struct kfifo *fifo,
358         void *from, unsigned int n, unsigned int recsize)
359 {
360         if (!__builtin_constant_p(recsize))
361                 return __kfifo_in_generic(fifo, from, n, recsize);
362         return __kfifo_in_rec(fifo, from, n, recsize);
363 }
364
365 /*
366  * __kfifo_out_... internal functions for get date from the fifo
367  * do not call it directly, use kfifo_out_rec() instead
368  */
369 extern unsigned int __kfifo_out_n(struct kfifo *fifo,
370         void *to, unsigned int reclen, unsigned int recsize);
371
372 extern unsigned int __kfifo_out_generic(struct kfifo *fifo,
373         void *to, unsigned int n,
374         unsigned int recsize, unsigned int *total);
375
376 static inline unsigned int __kfifo_out_rec(struct kfifo *fifo,
377         void *to, unsigned int n, unsigned int recsize,
378         unsigned int *total)
379 {
380         unsigned int l;
381
382         if (!recsize) {
383                 l = n;
384                 if (total)
385                         *total = l;
386         } else {
387                 l = __kfifo_peek_n(fifo, recsize);
388                 if (total)
389                         *total = l;
390                 if (n < l)
391                         return l;
392         }
393
394         return __kfifo_out_n(fifo, to, l, recsize);
395 }
396
397 /**
398  * kfifo_out_rec - gets some record data from the FIFO
399  * @fifo: the fifo to be used.
400  * @to: where the data must be copied.
401  * @n: the size of the destination buffer.
402  * @recsize: size of record field
403  * @total: pointer where the total number of to copied bytes should stored
404  *
405  * This function copies at most @n bytes from the FIFO to @to and returns the
406  * number of bytes which cannot be copied.
407  * A returned value greater than the @n value means that the record doesn't
408  * fit into the @to buffer.
409  *
410  * Note that with only one concurrent reader and one concurrent
411  * writer, you don't need extra locking to use these functions.
412  */
413 static inline __must_check unsigned int kfifo_out_rec(struct kfifo *fifo,
414         void *to, unsigned int n, unsigned int recsize,
415         unsigned int *total)
416
417 {
418         if (!__builtin_constant_p(recsize))
419                 return __kfifo_out_generic(fifo, to, n, recsize, total);
420         return __kfifo_out_rec(fifo, to, n, recsize, total);
421 }
422
423 /*
424  * __kfifo_from_user_... internal functions for transfer from user space into
425  * the fifo. do not call it directly, use kfifo_from_user_rec() instead
426  */
427 extern unsigned int __kfifo_from_user_n(struct kfifo *fifo,
428         const void __user *from, unsigned int n, unsigned int recsize);
429
430 extern unsigned int __kfifo_from_user_generic(struct kfifo *fifo,
431         const void __user *from, unsigned int n, unsigned int recsize);
432
433 static inline unsigned int __kfifo_from_user_rec(struct kfifo *fifo,
434         const void __user *from, unsigned int n, unsigned int recsize)
435 {
436         unsigned int ret;
437
438         ret = __kfifo_from_user_n(fifo, from, n, recsize);
439
440         if (likely(ret == 0)) {
441                 if (recsize)
442                         __kfifo_poke_n(fifo, recsize, n);
443                 __kfifo_add_in(fifo, n + recsize);
444         }
445         return ret;
446 }
447
448 /**
449  * kfifo_from_user_rec - puts some data from user space into the FIFO
450  * @fifo: the fifo to be used.
451  * @from: pointer to the data to be added.
452  * @n: the length of the data to be added.
453  * @recsize: size of record field
454  *
455  * This function copies @n bytes from the @from into the
456  * FIFO and returns the number of bytes which cannot be copied.
457  *
458  * If the returned value is equal or less the @n value, the copy_from_user()
459  * functions has failed. Otherwise the record doesn't fit into the buffer.
460  *
461  * Note that with only one concurrent reader and one concurrent
462  * writer, you don't need extra locking to use these functions.
463  */
464 static inline __must_check unsigned int kfifo_from_user_rec(struct kfifo *fifo,
465         const void __user *from, unsigned int n, unsigned int recsize)
466 {
467         if (!__builtin_constant_p(recsize))
468                 return __kfifo_from_user_generic(fifo, from, n, recsize);
469         return __kfifo_from_user_rec(fifo, from, n, recsize);
470 }
471
472 /*
473  * __kfifo_to_user_... internal functions for transfer fifo data into user space
474  * do not call it directly, use kfifo_to_user_rec() instead
475  */
476 extern unsigned int __kfifo_to_user_n(struct kfifo *fifo,
477         void __user *to, unsigned int n, unsigned int reclen,
478         unsigned int recsize);
479
480 extern unsigned int __kfifo_to_user_generic(struct kfifo *fifo,
481         void __user *to, unsigned int n, unsigned int recsize,
482         unsigned int *total);
483
484 static inline unsigned int __kfifo_to_user_rec(struct kfifo *fifo,
485         void __user *to, unsigned int n,
486         unsigned int recsize, unsigned int *total)
487 {
488         unsigned int l;
489
490         if (!recsize) {
491                 l = n;
492                 if (total)
493                         *total = l;
494         } else {
495                 l = __kfifo_peek_n(fifo, recsize);
496                 if (total)
497                         *total = l;
498                 if (n < l)
499                         return l;
500         }
501
502         return __kfifo_to_user_n(fifo, to, n, l, recsize);
503 }
504
505 /**
506  * kfifo_to_user_rec - gets data from the FIFO and write it to user space
507  * @fifo: the fifo to be used.
508  * @to: where the data must be copied.
509  * @n: the size of the destination buffer.
510  * @recsize: size of record field
511  * @total: pointer where the total number of to copied bytes should stored
512  *
513  * This function copies at most @n bytes from the FIFO to the @to.
514  * In case of an error, the function returns the number of bytes which cannot
515  * be copied.
516  * If the returned value is equal or less the @n value, the copy_to_user()
517  * functions has failed. Otherwise the record doesn't fit into the @to buffer.
518  *
519  * Note that with only one concurrent reader and one concurrent
520  * writer, you don't need extra locking to use these functions.
521  */
522 static inline __must_check unsigned int kfifo_to_user_rec(struct kfifo *fifo,
523                 void __user *to, unsigned int n, unsigned int recsize,
524                 unsigned int *total)
525 {
526         if (!__builtin_constant_p(recsize))
527                 return __kfifo_to_user_generic(fifo, to, n, recsize, total);
528         return __kfifo_to_user_rec(fifo, to, n, recsize, total);
529 }
530
531 /*
532  * __kfifo_peek_... internal functions for peek into the next fifo record
533  * do not call it directly, use kfifo_peek_rec() instead
534  */
535 extern unsigned int __kfifo_peek_generic(struct kfifo *fifo,
536                                 unsigned int recsize);
537
538 /**
539  * kfifo_peek_rec - gets the size of the next FIFO record data
540  * @fifo: the fifo to be used.
541  * @recsize: size of record field
542  *
543  * This function returns the size of the next FIFO record in number of bytes
544  */
545 static inline __must_check unsigned int kfifo_peek_rec(struct kfifo *fifo,
546         unsigned int recsize)
547 {
548         if (!__builtin_constant_p(recsize))
549                 return __kfifo_peek_generic(fifo, recsize);
550         if (!recsize)
551                 return kfifo_len(fifo);
552         return __kfifo_peek_n(fifo, recsize);
553 }
554
555 /*
556  * __kfifo_skip_... internal functions for skip the next fifo record
557  * do not call it directly, use kfifo_skip_rec() instead
558  */
559 extern void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize);
560
561 static inline void __kfifo_skip_rec(struct kfifo *fifo,
562         unsigned int recsize)
563 {
564         unsigned int l;
565
566         if (recsize) {
567                 l = __kfifo_peek_n(fifo, recsize);
568
569                 if (l + recsize <= kfifo_len(fifo)) {
570                         __kfifo_add_out(fifo, l + recsize);
571                         return;
572                 }
573         }
574         kfifo_reset_out(fifo);
575 }
576
577 /**
578  * kfifo_skip_rec - skip the next fifo out record
579  * @fifo: the fifo to be used.
580  * @recsize: size of record field
581  *
582  * This function skips the next FIFO record
583  */
584 static inline void kfifo_skip_rec(struct kfifo *fifo,
585         unsigned int recsize)
586 {
587         if (!__builtin_constant_p(recsize))
588                 __kfifo_skip_generic(fifo, recsize);
589         else
590                 __kfifo_skip_rec(fifo, recsize);
591 }
592
593 /**
594  * kfifo_avail_rec - returns the number of bytes available in a record FIFO
595  * @fifo: the fifo to be used.
596  * @recsize: size of record field
597  */
598 static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
599         unsigned int recsize)
600 {
601         unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);
602
603         return (l > recsize) ? l - recsize : 0;
604 }
605
606 #endif