Root/kernel/kfifo.c

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#include <linux/kernel.h>
24#include <linux/module.h>
25#include <linux/slab.h>
26#include <linux/err.h>
27#include <linux/kfifo.h>
28#include <linux/log2.h>
29#include <linux/uaccess.h>
30
31static void _kfifo_init(struct kfifo *fifo, void *buffer,
32        unsigned int size)
33{
34    fifo->buffer = buffer;
35    fifo->size = size;
36
37    kfifo_reset(fifo);
38}
39
40/**
41 * kfifo_init - initialize a FIFO using a preallocated buffer
42 * @fifo: the fifo to assign the buffer
43 * @buffer: the preallocated buffer to be used.
44 * @size: the size of the internal buffer, this has to be a power of 2.
45 *
46 */
47void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)
48{
49    /* size must be a power of 2 */
50    BUG_ON(!is_power_of_2(size));
51
52    _kfifo_init(fifo, buffer, size);
53}
54EXPORT_SYMBOL(kfifo_init);
55
56/**
57 * kfifo_alloc - allocates a new FIFO internal buffer
58 * @fifo: the fifo to assign then new buffer
59 * @size: the size of the buffer to be allocated, this have to be a power of 2.
60 * @gfp_mask: get_free_pages mask, passed to kmalloc()
61 *
62 * This function dynamically allocates a new fifo internal buffer
63 *
64 * The size will be rounded-up to a power of 2.
65 * The buffer will be release with kfifo_free().
66 * Return 0 if no error, otherwise the an error code
67 */
68int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask)
69{
70    unsigned char *buffer;
71
72    /*
73     * round up to the next power of 2, since our 'let the indices
74     * wrap' technique works only in this case.
75     */
76    if (!is_power_of_2(size)) {
77        BUG_ON(size > 0x80000000);
78        size = roundup_pow_of_two(size);
79    }
80
81    buffer = kmalloc(size, gfp_mask);
82    if (!buffer) {
83        _kfifo_init(fifo, NULL, 0);
84        return -ENOMEM;
85    }
86
87    _kfifo_init(fifo, buffer, size);
88
89    return 0;
90}
91EXPORT_SYMBOL(kfifo_alloc);
92
93/**
94 * kfifo_free - frees the FIFO internal buffer
95 * @fifo: the fifo to be freed.
96 */
97void kfifo_free(struct kfifo *fifo)
98{
99    kfree(fifo->buffer);
100    _kfifo_init(fifo, NULL, 0);
101}
102EXPORT_SYMBOL(kfifo_free);
103
104/**
105 * kfifo_skip - skip output data
106 * @fifo: the fifo to be used.
107 * @len: number of bytes to skip
108 */
109void kfifo_skip(struct kfifo *fifo, unsigned int len)
110{
111    if (len < kfifo_len(fifo)) {
112        __kfifo_add_out(fifo, len);
113        return;
114    }
115    kfifo_reset_out(fifo);
116}
117EXPORT_SYMBOL(kfifo_skip);
118
119static inline void __kfifo_in_data(struct kfifo *fifo,
120        const void *from, unsigned int len, unsigned int off)
121{
122    unsigned int l;
123
124    /*
125     * Ensure that we sample the fifo->out index -before- we
126     * start putting bytes into the kfifo.
127     */
128
129    smp_mb();
130
131    off = __kfifo_off(fifo, fifo->in + off);
132
133    /* first put the data starting from fifo->in to buffer end */
134    l = min(len, fifo->size - off);
135    memcpy(fifo->buffer + off, from, l);
136
137    /* then put the rest (if any) at the beginning of the buffer */
138    memcpy(fifo->buffer, from + l, len - l);
139}
140
141static inline void __kfifo_out_data(struct kfifo *fifo,
142        void *to, unsigned int len, unsigned int off)
143{
144    unsigned int l;
145
146    /*
147     * Ensure that we sample the fifo->in index -before- we
148     * start removing bytes from the kfifo.
149     */
150
151    smp_rmb();
152
153    off = __kfifo_off(fifo, fifo->out + off);
154
155    /* first get the data from fifo->out until the end of the buffer */
156    l = min(len, fifo->size - off);
157    memcpy(to, fifo->buffer + off, l);
158
159    /* then get the rest (if any) from the beginning of the buffer */
160    memcpy(to + l, fifo->buffer, len - l);
161}
162
163static inline int __kfifo_from_user_data(struct kfifo *fifo,
164     const void __user *from, unsigned int len, unsigned int off,
165     unsigned *lenout)
166{
167    unsigned int l;
168    int ret;
169
170    /*
171     * Ensure that we sample the fifo->out index -before- we
172     * start putting bytes into the kfifo.
173     */
174
175    smp_mb();
176
177    off = __kfifo_off(fifo, fifo->in + off);
178
179    /* first put the data starting from fifo->in to buffer end */
180    l = min(len, fifo->size - off);
181    ret = copy_from_user(fifo->buffer + off, from, l);
182    if (unlikely(ret)) {
183        *lenout = ret;
184        return -EFAULT;
185    }
186    *lenout = l;
187
188    /* then put the rest (if any) at the beginning of the buffer */
189    ret = copy_from_user(fifo->buffer, from + l, len - l);
190    *lenout += ret ? ret : len - l;
191    return ret ? -EFAULT : 0;
192}
193
194static inline int __kfifo_to_user_data(struct kfifo *fifo,
195        void __user *to, unsigned int len, unsigned int off, unsigned *lenout)
196{
197    unsigned int l;
198    int ret;
199
200    /*
201     * Ensure that we sample the fifo->in index -before- we
202     * start removing bytes from the kfifo.
203     */
204
205    smp_rmb();
206
207    off = __kfifo_off(fifo, fifo->out + off);
208
209    /* first get the data from fifo->out until the end of the buffer */
210    l = min(len, fifo->size - off);
211    ret = copy_to_user(to, fifo->buffer + off, l);
212    *lenout = l;
213    if (unlikely(ret)) {
214        *lenout -= ret;
215        return -EFAULT;
216    }
217
218    /* then get the rest (if any) from the beginning of the buffer */
219    len -= l;
220    ret = copy_to_user(to + l, fifo->buffer, len);
221    if (unlikely(ret)) {
222        *lenout += len - ret;
223        return -EFAULT;
224    }
225    *lenout += len;
226    return 0;
227}
228
229unsigned int __kfifo_in_n(struct kfifo *fifo,
230    const void *from, unsigned int len, unsigned int recsize)
231{
232    if (kfifo_avail(fifo) < len + recsize)
233        return len + 1;
234
235    __kfifo_in_data(fifo, from, len, recsize);
236    return 0;
237}
238EXPORT_SYMBOL(__kfifo_in_n);
239
240/**
241 * kfifo_in - puts some data into the FIFO
242 * @fifo: the fifo to be used.
243 * @from: the data to be added.
244 * @len: the length of the data to be added.
245 *
246 * This function copies at most @len bytes from the @from buffer into
247 * the FIFO depending on the free space, and returns the number of
248 * bytes copied.
249 *
250 * Note that with only one concurrent reader and one concurrent
251 * writer, you don't need extra locking to use these functions.
252 */
253unsigned int kfifo_in(struct kfifo *fifo, const void *from,
254                unsigned int len)
255{
256    len = min(kfifo_avail(fifo), len);
257
258    __kfifo_in_data(fifo, from, len, 0);
259    __kfifo_add_in(fifo, len);
260    return len;
261}
262EXPORT_SYMBOL(kfifo_in);
263
264unsigned int __kfifo_in_generic(struct kfifo *fifo,
265    const void *from, unsigned int len, unsigned int recsize)
266{
267    return __kfifo_in_rec(fifo, from, len, recsize);
268}
269EXPORT_SYMBOL(__kfifo_in_generic);
270
271unsigned int __kfifo_out_n(struct kfifo *fifo,
272    void *to, unsigned int len, unsigned int recsize)
273{
274    if (kfifo_len(fifo) < len + recsize)
275        return len;
276
277    __kfifo_out_data(fifo, to, len, recsize);
278    __kfifo_add_out(fifo, len + recsize);
279    return 0;
280}
281EXPORT_SYMBOL(__kfifo_out_n);
282
283/**
284 * kfifo_out - gets some data from the FIFO
285 * @fifo: the fifo to be used.
286 * @to: where the data must be copied.
287 * @len: the size of the destination buffer.
288 *
289 * This function copies at most @len bytes from the FIFO into the
290 * @to buffer and returns the number of copied bytes.
291 *
292 * Note that with only one concurrent reader and one concurrent
293 * writer, you don't need extra locking to use these functions.
294 */
295unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)
296{
297    len = min(kfifo_len(fifo), len);
298
299    __kfifo_out_data(fifo, to, len, 0);
300    __kfifo_add_out(fifo, len);
301
302    return len;
303}
304EXPORT_SYMBOL(kfifo_out);
305
306/**
307 * kfifo_out_peek - copy some data from the FIFO, but do not remove it
308 * @fifo: the fifo to be used.
309 * @to: where the data must be copied.
310 * @len: the size of the destination buffer.
311 * @offset: offset into the fifo
312 *
313 * This function copies at most @len bytes at @offset from the FIFO
314 * into the @to buffer and returns the number of copied bytes.
315 * The data is not removed from the FIFO.
316 */
317unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len,
318                unsigned offset)
319{
320    len = min(kfifo_len(fifo), len + offset);
321
322    __kfifo_out_data(fifo, to, len, offset);
323    return len;
324}
325EXPORT_SYMBOL(kfifo_out_peek);
326
327unsigned int __kfifo_out_generic(struct kfifo *fifo,
328    void *to, unsigned int len, unsigned int recsize,
329    unsigned int *total)
330{
331    return __kfifo_out_rec(fifo, to, len, recsize, total);
332}
333EXPORT_SYMBOL(__kfifo_out_generic);
334
335unsigned int __kfifo_from_user_n(struct kfifo *fifo,
336    const void __user *from, unsigned int len, unsigned int recsize)
337{
338    unsigned total;
339
340    if (kfifo_avail(fifo) < len + recsize)
341        return len + 1;
342
343    __kfifo_from_user_data(fifo, from, len, recsize, &total);
344    return total;
345}
346EXPORT_SYMBOL(__kfifo_from_user_n);
347
348/**
349 * kfifo_from_user - puts some data from user space into the FIFO
350 * @fifo: the fifo to be used.
351 * @from: pointer to the data to be added.
352 * @len: the length of the data to be added.
353 * @total: the actual returned data length.
354 *
355 * This function copies at most @len bytes from the @from into the
356 * FIFO depending and returns -EFAULT/0.
357 *
358 * Note that with only one concurrent reader and one concurrent
359 * writer, you don't need extra locking to use these functions.
360 */
361int kfifo_from_user(struct kfifo *fifo,
362        const void __user *from, unsigned int len, unsigned *total)
363{
364    int ret;
365    len = min(kfifo_avail(fifo), len);
366    ret = __kfifo_from_user_data(fifo, from, len, 0, total);
367    if (ret)
368        return ret;
369    __kfifo_add_in(fifo, len);
370    return 0;
371}
372EXPORT_SYMBOL(kfifo_from_user);
373
374unsigned int __kfifo_from_user_generic(struct kfifo *fifo,
375    const void __user *from, unsigned int len, unsigned int recsize)
376{
377    return __kfifo_from_user_rec(fifo, from, len, recsize);
378}
379EXPORT_SYMBOL(__kfifo_from_user_generic);
380
381unsigned int __kfifo_to_user_n(struct kfifo *fifo,
382    void __user *to, unsigned int len, unsigned int reclen,
383    unsigned int recsize)
384{
385    unsigned int ret, total;
386
387    if (kfifo_len(fifo) < reclen + recsize)
388        return len;
389
390    ret = __kfifo_to_user_data(fifo, to, reclen, recsize, &total);
391
392    if (likely(ret == 0))
393        __kfifo_add_out(fifo, reclen + recsize);
394
395    return total;
396}
397EXPORT_SYMBOL(__kfifo_to_user_n);
398
399/**
400 * kfifo_to_user - gets data from the FIFO and write it to user space
401 * @fifo: the fifo to be used.
402 * @to: where the data must be copied.
403 * @len: the size of the destination buffer.
404 * @lenout: pointer to output variable with copied data
405 *
406 * This function copies at most @len bytes from the FIFO into the
407 * @to buffer and 0 or -EFAULT.
408 *
409 * Note that with only one concurrent reader and one concurrent
410 * writer, you don't need extra locking to use these functions.
411 */
412int kfifo_to_user(struct kfifo *fifo,
413    void __user *to, unsigned int len, unsigned *lenout)
414{
415    int ret;
416    len = min(kfifo_len(fifo), len);
417    ret = __kfifo_to_user_data(fifo, to, len, 0, lenout);
418    __kfifo_add_out(fifo, *lenout);
419    return ret;
420}
421EXPORT_SYMBOL(kfifo_to_user);
422
423unsigned int __kfifo_to_user_generic(struct kfifo *fifo,
424    void __user *to, unsigned int len, unsigned int recsize,
425    unsigned int *total)
426{
427    return __kfifo_to_user_rec(fifo, to, len, recsize, total);
428}
429EXPORT_SYMBOL(__kfifo_to_user_generic);
430
431unsigned int __kfifo_peek_generic(struct kfifo *fifo, unsigned int recsize)
432{
433    if (recsize == 0)
434        return kfifo_avail(fifo);
435
436    return __kfifo_peek_n(fifo, recsize);
437}
438EXPORT_SYMBOL(__kfifo_peek_generic);
439
440void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize)
441{
442    __kfifo_skip_rec(fifo, recsize);
443}
444EXPORT_SYMBOL(__kfifo_skip_generic);
445
446

Archive Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9



interactive