Commit | Line | Data |
---|---|---|
1da177e4 | 1 | /* |
45465487 | 2 | * A generic kernel FIFO implementation. |
1da177e4 | 3 | * |
45465487 | 4 | * Copyright (C) 2009 Stefani Seibold <stefani@seibold.net> |
1da177e4 LT |
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> | |
f84d5a76 | 28 | #include <linux/log2.h> |
a121f24a | 29 | #include <linux/uaccess.h> |
1da177e4 | 30 | |
8ecc2951 | 31 | static void _kfifo_init(struct kfifo *fifo, void *buffer, |
c1e13f25 | 32 | unsigned int size) |
45465487 SS |
33 | { |
34 | fifo->buffer = buffer; | |
35 | fifo->size = size; | |
45465487 SS |
36 | |
37 | kfifo_reset(fifo); | |
38 | } | |
39 | ||
1da177e4 | 40 | /** |
45465487 SS |
41 | * kfifo_init - initialize a FIFO using a preallocated buffer |
42 | * @fifo: the fifo to assign the buffer | |
1da177e4 | 43 | * @buffer: the preallocated buffer to be used. |
5dab600e | 44 | * @size: the size of the internal buffer, this has to be a power of 2. |
1da177e4 | 45 | * |
1da177e4 | 46 | */ |
8ecc2951 | 47 | void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size) |
1da177e4 | 48 | { |
1da177e4 | 49 | /* size must be a power of 2 */ |
f84d5a76 | 50 | BUG_ON(!is_power_of_2(size)); |
1da177e4 | 51 | |
c1e13f25 | 52 | _kfifo_init(fifo, buffer, size); |
1da177e4 LT |
53 | } |
54 | EXPORT_SYMBOL(kfifo_init); | |
55 | ||
56 | /** | |
45465487 SS |
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. | |
1da177e4 | 60 | * @gfp_mask: get_free_pages mask, passed to kmalloc() |
1da177e4 | 61 | * |
45465487 SS |
62 | * This function dynamically allocates a new fifo internal buffer |
63 | * | |
1da177e4 | 64 | * The size will be rounded-up to a power of 2. |
45465487 SS |
65 | * The buffer will be release with kfifo_free(). |
66 | * Return 0 if no error, otherwise the an error code | |
1da177e4 | 67 | */ |
c1e13f25 | 68 | int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask) |
1da177e4 LT |
69 | { |
70 | unsigned char *buffer; | |
1da177e4 LT |
71 | |
72 | /* | |
73 | * round up to the next power of 2, since our 'let the indices | |
b33112d1 | 74 | * wrap' technique works only in this case. |
1da177e4 | 75 | */ |
b33112d1 | 76 | if (!is_power_of_2(size)) { |
1da177e4 LT |
77 | BUG_ON(size > 0x80000000); |
78 | size = roundup_pow_of_two(size); | |
79 | } | |
80 | ||
81 | buffer = kmalloc(size, gfp_mask); | |
45465487 | 82 | if (!buffer) { |
5a5e0f4c | 83 | _kfifo_init(fifo, NULL, 0); |
45465487 SS |
84 | return -ENOMEM; |
85 | } | |
1da177e4 | 86 | |
c1e13f25 | 87 | _kfifo_init(fifo, buffer, size); |
1da177e4 | 88 | |
45465487 | 89 | return 0; |
1da177e4 LT |
90 | } |
91 | EXPORT_SYMBOL(kfifo_alloc); | |
92 | ||
93 | /** | |
45465487 | 94 | * kfifo_free - frees the FIFO internal buffer |
1da177e4 LT |
95 | * @fifo: the fifo to be freed. |
96 | */ | |
97 | void kfifo_free(struct kfifo *fifo) | |
98 | { | |
99 | kfree(fifo->buffer); | |
1a02d59a | 100 | _kfifo_init(fifo, NULL, 0); |
1da177e4 LT |
101 | } |
102 | EXPORT_SYMBOL(kfifo_free); | |
103 | ||
a121f24a SS |
104 | /** |
105 | * kfifo_skip - skip output data | |
106 | * @fifo: the fifo to be used. | |
107 | * @len: number of bytes to skip | |
108 | */ | |
109 | void 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 | } | |
117 | EXPORT_SYMBOL(kfifo_skip); | |
118 | ||
86d48803 SS |
119 | static inline void __kfifo_in_data(struct kfifo *fifo, |
120 | const void *from, unsigned int len, unsigned int off) | |
1da177e4 LT |
121 | { |
122 | unsigned int l; | |
123 | ||
a45bce49 PM |
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 | ||
86d48803 | 131 | off = __kfifo_off(fifo, fifo->in + off); |
a121f24a | 132 | |
1da177e4 | 133 | /* first put the data starting from fifo->in to buffer end */ |
a121f24a SS |
134 | l = min(len, fifo->size - off); |
135 | memcpy(fifo->buffer + off, from, l); | |
1da177e4 LT |
136 | |
137 | /* then put the rest (if any) at the beginning of the buffer */ | |
7acd72eb | 138 | memcpy(fifo->buffer, from + l, len - l); |
1da177e4 | 139 | } |
1da177e4 | 140 | |
86d48803 SS |
141 | static inline void __kfifo_out_data(struct kfifo *fifo, |
142 | void *to, unsigned int len, unsigned int off) | |
1da177e4 LT |
143 | { |
144 | unsigned int l; | |
145 | ||
a45bce49 PM |
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 | ||
86d48803 | 153 | off = __kfifo_off(fifo, fifo->out + off); |
a121f24a | 154 | |
1da177e4 | 155 | /* first get the data from fifo->out until the end of the buffer */ |
a121f24a SS |
156 | l = min(len, fifo->size - off); |
157 | memcpy(to, fifo->buffer + off, l); | |
1da177e4 LT |
158 | |
159 | /* then get the rest (if any) from the beginning of the buffer */ | |
7acd72eb | 160 | memcpy(to + l, fifo->buffer, len - l); |
a121f24a | 161 | } |
a121f24a | 162 | |
64ce1037 AK |
163 | static inline int __kfifo_from_user_data(struct kfifo *fifo, |
164 | const void __user *from, unsigned int len, unsigned int off, | |
165 | unsigned *lenout) | |
a121f24a | 166 | { |
a121f24a SS |
167 | unsigned int l; |
168 | int ret; | |
169 | ||
a45bce49 | 170 | /* |
a121f24a SS |
171 | * Ensure that we sample the fifo->out index -before- we |
172 | * start putting bytes into the kfifo. | |
a45bce49 PM |
173 | */ |
174 | ||
175 | smp_mb(); | |
176 | ||
86d48803 | 177 | off = __kfifo_off(fifo, fifo->in + off); |
a121f24a SS |
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); | |
64ce1037 AK |
182 | if (unlikely(ret)) { |
183 | *lenout = ret; | |
184 | return -EFAULT; | |
185 | } | |
186 | *lenout = l; | |
a121f24a SS |
187 | |
188 | /* then put the rest (if any) at the beginning of the buffer */ | |
64ce1037 AK |
189 | ret = copy_from_user(fifo->buffer, from + l, len - l); |
190 | *lenout += ret ? ret : len - l; | |
191 | return ret ? -EFAULT : 0; | |
86d48803 SS |
192 | } |
193 | ||
64ce1037 AK |
194 | static inline int __kfifo_to_user_data(struct kfifo *fifo, |
195 | void __user *to, unsigned int len, unsigned int off, unsigned *lenout) | |
86d48803 SS |
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); | |
64ce1037 AK |
212 | *lenout = l; |
213 | if (unlikely(ret)) { | |
214 | *lenout -= ret; | |
215 | return -EFAULT; | |
216 | } | |
a121f24a | 217 | |
86d48803 | 218 | /* then get the rest (if any) from the beginning of the buffer */ |
64ce1037 AK |
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; | |
86d48803 | 227 | } |
1da177e4 | 228 | |
86d48803 SS |
229 | unsigned 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 | } | |
238 | EXPORT_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 | */ | |
8ecc2951 | 253 | unsigned int kfifo_in(struct kfifo *fifo, const void *from, |
86d48803 SS |
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); | |
1da177e4 LT |
260 | return len; |
261 | } | |
86d48803 SS |
262 | EXPORT_SYMBOL(kfifo_in); |
263 | ||
264 | unsigned 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 | } | |
269 | EXPORT_SYMBOL(__kfifo_in_generic); | |
270 | ||
271 | unsigned 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 | } | |
281 | EXPORT_SYMBOL(__kfifo_out_n); | |
a121f24a SS |
282 | |
283 | /** | |
86d48803 | 284 | * kfifo_out - gets some data from the FIFO |
a121f24a SS |
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 | */ | |
8ecc2951 | 295 | unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len) |
a121f24a | 296 | { |
86d48803 | 297 | len = min(kfifo_len(fifo), len); |
a121f24a | 298 | |
86d48803 SS |
299 | __kfifo_out_data(fifo, to, len, 0); |
300 | __kfifo_add_out(fifo, len); | |
a121f24a | 301 | |
86d48803 SS |
302 | return len; |
303 | } | |
304 | EXPORT_SYMBOL(kfifo_out); | |
a121f24a | 305 | |
a5b9e2c1 AK |
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 | */ | |
317 | unsigned 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 | } | |
325 | EXPORT_SYMBOL(kfifo_out_peek); | |
326 | ||
86d48803 SS |
327 | unsigned 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 | } | |
333 | EXPORT_SYMBOL(__kfifo_out_generic); | |
a121f24a | 334 | |
86d48803 SS |
335 | unsigned int __kfifo_from_user_n(struct kfifo *fifo, |
336 | const void __user *from, unsigned int len, unsigned int recsize) | |
337 | { | |
64ce1037 AK |
338 | unsigned total; |
339 | ||
86d48803 SS |
340 | if (kfifo_avail(fifo) < len + recsize) |
341 | return len + 1; | |
a121f24a | 342 | |
64ce1037 AK |
343 | __kfifo_from_user_data(fifo, from, len, recsize, &total); |
344 | return total; | |
86d48803 SS |
345 | } |
346 | EXPORT_SYMBOL(__kfifo_from_user_n); | |
a121f24a | 347 | |
86d48803 SS |
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. | |
bc173f70 | 353 | * @total: the actual returned data length. |
86d48803 SS |
354 | * |
355 | * This function copies at most @len bytes from the @from into the | |
64ce1037 | 356 | * FIFO depending and returns -EFAULT/0. |
86d48803 SS |
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 | */ | |
64ce1037 AK |
361 | int kfifo_from_user(struct kfifo *fifo, |
362 | const void __user *from, unsigned int len, unsigned *total) | |
86d48803 | 363 | { |
64ce1037 | 364 | int ret; |
86d48803 | 365 | len = min(kfifo_avail(fifo), len); |
64ce1037 AK |
366 | ret = __kfifo_from_user_data(fifo, from, len, 0, total); |
367 | if (ret) | |
368 | return ret; | |
86d48803 | 369 | __kfifo_add_in(fifo, len); |
64ce1037 | 370 | return 0; |
86d48803 SS |
371 | } |
372 | EXPORT_SYMBOL(kfifo_from_user); | |
a121f24a | 373 | |
86d48803 SS |
374 | unsigned 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 | } | |
379 | EXPORT_SYMBOL(__kfifo_from_user_generic); | |
a121f24a | 380 | |
86d48803 SS |
381 | unsigned int __kfifo_to_user_n(struct kfifo *fifo, |
382 | void __user *to, unsigned int len, unsigned int reclen, | |
383 | unsigned int recsize) | |
384 | { | |
64ce1037 | 385 | unsigned int ret, total; |
a121f24a | 386 | |
86d48803 SS |
387 | if (kfifo_len(fifo) < reclen + recsize) |
388 | return len; | |
a121f24a | 389 | |
64ce1037 | 390 | ret = __kfifo_to_user_data(fifo, to, reclen, recsize, &total); |
86d48803 SS |
391 | |
392 | if (likely(ret == 0)) | |
393 | __kfifo_add_out(fifo, reclen + recsize); | |
394 | ||
64ce1037 | 395 | return total; |
86d48803 SS |
396 | } |
397 | EXPORT_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. | |
bc173f70 | 404 | * @lenout: pointer to output variable with copied data |
86d48803 SS |
405 | * |
406 | * This function copies at most @len bytes from the FIFO into the | |
64ce1037 | 407 | * @to buffer and 0 or -EFAULT. |
86d48803 SS |
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 | */ | |
64ce1037 AK |
412 | int kfifo_to_user(struct kfifo *fifo, |
413 | void __user *to, unsigned int len, unsigned *lenout) | |
86d48803 | 414 | { |
64ce1037 | 415 | int ret; |
86d48803 | 416 | len = min(kfifo_len(fifo), len); |
64ce1037 AK |
417 | ret = __kfifo_to_user_data(fifo, to, len, 0, lenout); |
418 | __kfifo_add_out(fifo, *lenout); | |
419 | return ret; | |
a121f24a SS |
420 | } |
421 | EXPORT_SYMBOL(kfifo_to_user); | |
422 | ||
86d48803 SS |
423 | unsigned 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 | } | |
429 | EXPORT_SYMBOL(__kfifo_to_user_generic); | |
430 | ||
431 | unsigned 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 | } | |
438 | EXPORT_SYMBOL(__kfifo_peek_generic); | |
439 | ||
440 | void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize) | |
441 | { | |
442 | __kfifo_skip_rec(fifo, recsize); | |
443 | } | |
444 | EXPORT_SYMBOL(__kfifo_skip_generic); | |
445 |