aboutsummaryrefslogtreecommitdiff
path: root/include/linux/kfifo.h
blob: 3d44e9c65a8e3afa5621b8f771f7e0b54dc40515 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
/*
 * A generic kernel FIFO implementation.
 *
 * Copyright (C) 2009 Stefani Seibold <stefani@seibold.net>
 * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/*
 * Howto porting drivers to the new generic fifo API:
 *
 * - Modify the declaration of the "struct kfifo *" object into a
 *   in-place "struct kfifo" object
 * - Init the in-place object with kfifo_alloc() or kfifo_init()
 *   Note: The address of the in-place "struct kfifo" object must be
 *   passed as the first argument to this functions
 * - Replace the use of __kfifo_put into kfifo_in and __kfifo_get
 *   into kfifo_out
 * - Replace the use of kfifo_put into kfifo_in_locked and kfifo_get
 *   into kfifo_out_locked
 *   Note: the spinlock pointer formerly passed to kfifo_init/kfifo_alloc
 *   must be passed now to the kfifo_in_locked and kfifo_out_locked
 *   as the last parameter.
 * - All formerly name __kfifo_* functions has been renamed into kfifo_*
 */

#ifndef _LINUX_KFIFO_H
#define _LINUX_KFIFO_H

#include <linux/kernel.h>
#include <linux/spinlock.h>

struct kfifo {
	unsigned char *buffer;	/* the buffer holding the data */
	unsigned int size;	/* the size of the allocated buffer */
	unsigned int in;	/* data is added at offset (in % size) */
	unsigned int out;	/* data is extracted from off. (out % size) */
};

/*
 * Macros for declaration and initialization of the kfifo datatype
 */

/* helper macro */
#define __kfifo_initializer(s, b) \
	(struct kfifo) { \
		.size	= s, \
		.in	= 0, \
		.out	= 0, \
		.buffer = b \
	}

/**
 * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer
 * @name: name of the declared kfifo datatype
 * @size: size of the fifo buffer
 *
 * Note1: the macro can be used inside struct or union declaration
 * Note2: the macro creates two objects:
 *  A kfifo object with the given name and a buffer for the kfifo
 *  object named name##kfifo_buffer
 */
#define DECLARE_KFIFO(name, size) \
union { \
	struct kfifo name; \
	unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \
}

/**
 * INIT_KFIFO - Initialize a kfifo declared by DECLARED_KFIFO
 * @name: name of the declared kfifo datatype
 */
#define INIT_KFIFO(name) \
	name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \
				sizeof(struct kfifo), name##kfifo_buffer)

/**
 * DEFINE_KFIFO - macro to define and initialize a kfifo
 * @name: name of the declared kfifo datatype
 * @size: size of the fifo buffer
 *
 * Note1: the macro can be used for global and local kfifo data type variables
 * Note2: the macro creates two objects:
 *  A kfifo object with the given name and a buffer for the kfifo
 *  object named name##kfifo_buffer
 */
#define DEFINE_KFIFO(name, size) \
	unsigned char name##kfifo_buffer[size]; \
	struct kfifo name = __kfifo_initializer(size, name##kfifo_buffer)

#undef __kfifo_initializer

extern void kfifo_init(struct kfifo *fifo, unsigned char *buffer,
			unsigned int size);
extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
			gfp_t gfp_mask);
extern void kfifo_free(struct kfifo *fifo);
extern unsigned int kfifo_in(struct kfifo *fifo,
				const unsigned char *from, unsigned int len);
extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
				unsigned char *to, unsigned int len);

/**
 * kfifo_reset - removes the entire FIFO contents
 * @fifo: the fifo to be emptied.
 */
static inline void kfifo_reset(struct kfifo *fifo)
{
	fifo->in = fifo->out = 0;
}

/**
 * kfifo_reset_out - skip FIFO contents
 * @fifo: the fifo to be emptied.
 */
static inline void kfifo_reset_out(struct kfifo *fifo)
{
	smp_mb();
	fifo->out = fifo->in;
}

/**
 * kfifo_size - returns the size of the fifo in bytes
 * @fifo: the fifo to be used.
 */
static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)
{
	return fifo->size;
}

/**
 * kfifo_len - returns the number of used bytes in the FIFO
 * @fifo: the fifo to be used.
 */
static inline unsigned int kfifo_len(struct kfifo *fifo)
{
	register unsigned int	out;

	out = fifo->out;
	smp_rmb();
	return fifo->in - out;
}

/**
 * kfifo_is_empty - returns true if the fifo is empty
 * @fifo: the fifo to be used.
 */
static inline __must_check int kfifo_is_empty(struct kfifo *fifo)
{
	return fifo->in == fifo->out;
}

/**
 * kfifo_is_full - returns true if the fifo is full
 * @fifo: the fifo to be used.
 */
static inline __must_check int kfifo_is_full(struct kfifo *fifo)
{
	return kfifo_len(fifo) == kfifo_size(fifo);
}

/**
 * kfifo_avail - returns the number of bytes available in the FIFO
 * @fifo: the fifo to be used.
 */
static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
{
	return kfifo_size(fifo) - kfifo_len(fifo);
}

/**
 * kfifo_in_locked - puts some data into the FIFO using a spinlock for locking
 * @fifo: the fifo to be used.
 * @from: the data to be added.
 * @n: the length of the data to be added.
 * @lock: pointer to the spinlock to use for locking.
 *
 * This function copies at most @len bytes from the @from buffer into
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.
 */
static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
		const unsigned char *from, unsigned int n, spinlock_t *lock)
{
	unsigned long flags;
	unsigned int ret;

	spin_lock_irqsave(lock, flags);

	ret = kfifo_in(fifo, from, n);

	spin_unlock_irqrestore(lock, flags);

	return ret;
}

/**
 * kfifo_out_locked - gets some data from the FIFO using a spinlock for locking
 * @fifo: the fifo to be used.
 * @to: where the data must be copied.
 * @n: the size of the destination buffer.
 * @lock: pointer to the spinlock to use for locking.
 *
 * This function copies at most @len bytes from the FIFO into the
 * @to buffer and returns the number of copied bytes.
 */
static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
	unsigned char *to, unsigned int n, spinlock_t *lock)
{
	unsigned long flags;
	unsigned int ret;

	spin_lock_irqsave(lock, flags);

	ret = kfifo_out(fifo, to, n);

	/*
	 * optimization: if the FIFO is empty, set the indices to 0
	 * so we don't wrap the next time
	 */
	if (kfifo_is_empty(fifo))
		kfifo_reset(fifo);

	spin_unlock_irqrestore(lock, flags);

	return ret;
}

extern void kfifo_skip(struct kfifo *fifo, unsigned int len);

extern __must_check unsigned int kfifo_from_user(struct kfifo *fifo,
	const void __user *from, unsigned int n);

extern __must_check unsigned int kfifo_to_user(struct kfifo *fifo,
	void __user *to, unsigned int n);

/*
 * __kfifo_add_out internal helper function for updating the out offset
 */
static inline void __kfifo_add_out(struct kfifo *fifo,
				unsigned int off)
{
	smp_mb();
	fifo->out += off;
}

/*
 * __kfifo_add_in internal helper function for updating the in offset
 */
static inline void __kfifo_add_in(struct kfifo *fifo,
				unsigned int off)
{
	smp_wmb();
	fifo->in += off;
}

/*
 * __kfifo_off internal helper function for calculating the index of a
 * given offeset
 */
static inline unsigned int __kfifo_off(struct kfifo *fifo, unsigned int off)
{
	return off & (fifo->size - 1);
}

/*
 * __kfifo_peek_n internal helper function for determinate the length of
 * the next record in the fifo
 */
static inline unsigned int __kfifo_peek_n(struct kfifo *fifo,
				unsigned int recsize)
{
#define __KFIFO_GET(fifo, off, shift) \
	((fifo)->buffer[__kfifo_off((fifo), (fifo)->out+(off))] << (shift))

	unsigned int l;

	l = __KFIFO_GET(fifo, 0, 0);

	if (--recsize)
		l |= __KFIFO_GET(fifo, 1, 8);

	return l;
#undef	__KFIFO_GET
}

/*
 * __kfifo_poke_n internal helper function for storing the length of
 * the next record into the fifo
 */
static inline void __kfifo_poke_n(struct kfifo *fifo,
			unsigned int recsize, unsigned int n)
{
#define __KFIFO_PUT(fifo, off, val, shift) \
		( \
		(fifo)->buffer[__kfifo_off((fifo), (fifo)->in+(off))] = \
		(unsigned char)((val) >> (shift)) \
		)

	__KFIFO_PUT(fifo, 0, n, 0);

	if (--recsize)
		__KFIFO_PUT(fifo, 1, n, 8);
#undef	__KFIFO_PUT
}

/*
 * __kfifo_in_... internal functions for put date into the fifo
 * do not call it directly, use kfifo_in_rec() instead
 */
extern unsigned int __kfifo_in_n(struct kfifo *fifo,
	const void *from, unsigned int n, unsigned int recsize);

extern unsigned int __kfifo_in_generic(struct kfifo *fifo,
	const void *from, unsigned int n, unsigned int recsize);

static inline unsigned int __kfifo_in_rec(struct kfifo *fifo,
	const void *from, unsigned int n, unsigned int recsize)
{
	unsigned int ret;

	ret = __kfifo_in_n(fifo, from, n, recsize);

	if (likely(ret == 0)) {
		if (recsize)
			__kfifo_poke_n(fifo, recsize, n);
		__kfifo_add_in(fifo, n + recsize);
	}
	return ret;
}

/**
 * kfifo_in_rec - puts some record data into the FIFO
 * @fifo: the fifo to be used.
 * @from: the data to be added.
 * @n: the length of the data to be added.
 * @recsize: size of record field
 *
 * This function copies @n bytes from the @from into the FIFO and returns
 * the number of bytes which cannot be copied.
 * A returned value greater than the @n value means that the record doesn't
 * fit into the buffer.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
static inline __must_check unsigned int kfifo_in_rec(struct kfifo *fifo,
	void *from, unsigned int n, unsigned int recsize)
{
	if (!__builtin_constant_p(recsize))
		return __kfifo_in_generic(fifo, from, n, recsize);
	return __kfifo_in_rec(fifo, from, n, recsize);
}

/*
 * __kfifo_out_... internal functions for get date from the fifo
 * do not call it directly, use kfifo_out_rec() instead
 */
extern unsigned int __kfifo_out_n(struct kfifo *fifo,
	void *to, unsigned int reclen, unsigned int recsize);

extern unsigned int __kfifo_out_generic(struct kfifo *fifo,
	void *to, unsigned int n,
	unsigned int recsize, unsigned int *total);

static inline unsigned int __kfifo_out_rec(struct kfifo *fifo,
	void *to, unsigned int n, unsigned int recsize,
	unsigned int *total)
{
	unsigned int l;

	if (!recsize) {
		l = n;
		if (total)
			*total = l;
	} else {
		l = __kfifo_peek_n(fifo, recsize);
		if (total)
			*total = l;
		if (n < l)
			return l;
	}

	return __kfifo_out_n(fifo, to, l, recsize);
}

/**
 * kfifo_out_rec - gets some record data from the FIFO
 * @fifo: the fifo to be used.
 * @to: where the data must be copied.
 * @n: the size of the destination buffer.
 * @recsize: size of record field
 * @total: pointer where the total number of to copied bytes should stored
 *
 * This function copies at most @n bytes from the FIFO to @to and returns the
 * number of bytes which cannot be copied.
 * A returned value greater than the @n value means that the record doesn't
 * fit into the @to buffer.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
static inline __must_check unsigned int kfifo_out_rec(struct kfifo *fifo,
	void *to, unsigned int n, unsigned int recsize,
	unsigned int *total)

{
	if (!__builtin_constant_p(recsize))
		return __kfifo_out_generic(fifo, to, n, recsize, total);
	return __kfifo_out_rec(fifo, to, n, recsize, total);
}

/*
 * __kfifo_from_user_... internal functions for transfer from user space into
 * the fifo. do not call it directly, use kfifo_from_user_rec() instead
 */
extern unsigned int __kfifo_from_user_n(struct kfifo *fifo,
	const void __user *from, unsigned int n, unsigned int recsize);

extern unsigned int __kfifo_from_user_generic(struct kfifo *fifo,
	const void __user *from, unsigned int n, unsigned int recsize);

static inline unsigned int __kfifo_from_user_rec(struct kfifo *fifo,
	const void __user *from, unsigned int n, unsigned int recsize)
{
	unsigned int ret;

	ret = __kfifo_from_user_n(fifo, from, n, recsize);

	if (likely(ret == 0)) {
		if (recsize)
			__kfifo_poke_n(fifo, recsize, n);
		__kfifo_add_in(fifo, n + recsize);
	}
	return ret;
}

/**
 * kfifo_from_user_rec - puts some data from user space into the FIFO
 * @fifo: the fifo to be used.
 * @from: pointer to the data to be added.
 * @n: the length of the data to be added.
 * @recsize: size of record field
 *
 * This function copies @n bytes from the @from into the
 * FIFO and returns the number of bytes which cannot be copied.
 *
 * If the returned value is equal or less the @n value, the copy_from_user()
 * functions has failed. Otherwise the record doesn't fit into the buffer.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
static inline __must_check unsigned int kfifo_from_user_rec(struct kfifo *fifo,
	const void __user *from, unsigned int n, unsigned int recsize)
{
	if (!__builtin_constant_p(recsize))
		return __kfifo_from_user_generic(fifo, from, n, recsize);
	return __kfifo_from_user_rec(fifo, from, n, recsize);
}

/*
 * __kfifo_to_user_... internal functions for transfer fifo data into user space
 * do not call it directly, use kfifo_to_user_rec() instead
 */
extern unsigned int __kfifo_to_user_n(struct kfifo *fifo,
	void __user *to, unsigned int n, unsigned int reclen,
	unsigned int recsize);

extern unsigned int __kfifo_to_user_generic(struct kfifo *fifo,
	void __user *to, unsigned int n, unsigned int recsize,
	unsigned int *total);

static inline unsigned int __kfifo_to_user_rec(struct kfifo *fifo,
	void __user *to, unsigned int n,
	unsigned int recsize, unsigned int *total)
{
	unsigned int l;

	if (!recsize) {
		l = n;
		if (total)
			*total = l;
	} else {
		l = __kfifo_peek_n(fifo, recsize);
		if (total)
			*total = l;
		if (n < l)
			return l;
	}

	return __kfifo_to_user_n(fifo, to, n, l, recsize);
}

/**
 * kfifo_to_user_rec - gets data from the FIFO and write it to user space
 * @fifo: the fifo to be used.
 * @to: where the data must be copied.
 * @n: the size of the destination buffer.
 * @recsize: size of record field
 * @total: pointer where the total number of to copied bytes should stored
 *
 * This function copies at most @n bytes from the FIFO to the @to.
 * In case of an error, the function returns the number of bytes which cannot
 * be copied.
 * If the returned value is equal or less the @n value, the copy_to_user()
 * functions has failed. Otherwise the record doesn't fit into the @to buffer.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
static inline __must_check unsigned int kfifo_to_user_rec(struct kfifo *fifo,
		void __user *to, unsigned int n, unsigned int recsize,
		unsigned int *total)
{
	if (!__builtin_constant_p(recsize))
		return __kfifo_to_user_generic(fifo, to, n, recsize, total);
	return __kfifo_to_user_rec(fifo, to, n, recsize, total);
}

/*
 * __kfifo_peek_... internal functions for peek into the next fifo record
 * do not call it directly, use kfifo_peek_rec() instead
 */
extern unsigned int __kfifo_peek_generic(struct kfifo *fifo,
				unsigned int recsize);

/**
 * kfifo_peek_rec - gets the size of the next FIFO record data
 * @fifo: the fifo to be used.
 * @recsize: size of record field
 *
 * This function returns the size of the next FIFO record in number of bytes
 */
static inline __must_check unsigned int kfifo_peek_rec(struct kfifo *fifo,
	unsigned int recsize)
{
	if (!__builtin_constant_p(recsize))
		return __kfifo_peek_generic(fifo, recsize);
	if (!recsize)
		return kfifo_len(fifo);
	return __kfifo_peek_n(fifo, recsize);
}

/*
 * __kfifo_skip_... internal functions for skip the next fifo record
 * do not call it directly, use kfifo_skip_rec() instead
 */
extern void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize);

static inline void __kfifo_skip_rec(struct kfifo *fifo,
	unsigned int recsize)
{
	unsigned int l;

	if (recsize) {
		l = __kfifo_peek_n(fifo, recsize);

		if (l + recsize <= kfifo_len(fifo)) {
			__kfifo_add_out(fifo, l + recsize);
			return;
		}
	}
	kfifo_reset_out(fifo);
}

/**
 * kfifo_skip_rec - skip the next fifo out record
 * @fifo: the fifo to be used.
 * @recsize: size of record field
 *
 * This function skips the next FIFO record
 */
static inline void kfifo_skip_rec(struct kfifo *fifo,
	unsigned int recsize)
{
	if (!__builtin_constant_p(recsize))
		__kfifo_skip_generic(fifo, recsize);
	else
		__kfifo_skip_rec(fifo, recsize);
}

/**
 * kfifo_avail_rec - returns the number of bytes available in a record FIFO
 * @fifo: the fifo to be used.
 * @recsize: size of record field
 */
static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
	unsigned int recsize)
{
	unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);

	return (l > recsize) ? l - recsize : 0;
}

#endif