kfifo.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610
  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. * Howto porting drivers to the new generic fifo API:
  24. *
  25. * - Modify the declaration of the "struct kfifo *" object into a
  26. * in-place "struct kfifo" object
  27. * - Init the in-place object with kfifo_alloc() or kfifo_init()
  28. * Note: The address of the in-place "struct kfifo" object must be
  29. * passed as the first argument to this functions
  30. * - Replace the use of __kfifo_put into kfifo_in and __kfifo_get
  31. * into kfifo_out
  32. * - Replace the use of kfifo_put into kfifo_in_locked and kfifo_get
  33. * into kfifo_out_locked
  34. * Note: the spinlock pointer formerly passed to kfifo_init/kfifo_alloc
  35. * must be passed now to the kfifo_in_locked and kfifo_out_locked
  36. * as the last parameter.
  37. * - All formerly name __kfifo_* functions has been renamed into kfifo_*
  38. */
  39. #ifndef _LINUX_KFIFO_H
  40. #define _LINUX_KFIFO_H
  41. #include <linux/kernel.h>
  42. #include <linux/spinlock.h>
  43. struct kfifo {
  44. unsigned char *buffer; /* the buffer holding the data */
  45. unsigned int size; /* the size of the allocated buffer */
  46. unsigned int in; /* data is added at offset (in % size) */
  47. unsigned int out; /* data is extracted from off. (out % size) */
  48. };
  49. /*
  50. * Macros for declaration and initialization of the kfifo datatype
  51. */
  52. /* helper macro */
  53. #define __kfifo_initializer(s, b) \
  54. (struct kfifo) { \
  55. .size = s, \
  56. .in = 0, \
  57. .out = 0, \
  58. .buffer = b \
  59. }
  60. /**
  61. * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer
  62. * @name: name of the declared kfifo datatype
  63. * @size: size of the fifo buffer
  64. *
  65. * Note1: the macro can be used inside struct or union declaration
  66. * Note2: the macro creates two objects:
  67. * A kfifo object with the given name and a buffer for the kfifo
  68. * object named name##kfifo_buffer
  69. */
  70. #define DECLARE_KFIFO(name, size) \
  71. union { \
  72. struct kfifo name; \
  73. unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \
  74. }
  75. /**
  76. * INIT_KFIFO - Initialize a kfifo declared by DECLARED_KFIFO
  77. * @name: name of the declared kfifo datatype
  78. */
  79. #define INIT_KFIFO(name) \
  80. name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \
  81. sizeof(struct kfifo), name##kfifo_buffer)
  82. /**
  83. * DEFINE_KFIFO - macro to define and initialize a kfifo
  84. * @name: name of the declared kfifo datatype
  85. * @size: size of the fifo buffer
  86. *
  87. * Note1: the macro can be used for global and local kfifo data type variables
  88. * Note2: the macro creates two objects:
  89. * A kfifo object with the given name and a buffer for the kfifo
  90. * object named name##kfifo_buffer
  91. */
  92. #define DEFINE_KFIFO(name, size) \
  93. unsigned char name##kfifo_buffer[size]; \
  94. struct kfifo name = __kfifo_initializer(size, name##kfifo_buffer)
  95. #undef __kfifo_initializer
  96. extern void kfifo_init(struct kfifo *fifo, unsigned char *buffer,
  97. unsigned int size);
  98. extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
  99. gfp_t gfp_mask);
  100. extern void kfifo_free(struct kfifo *fifo);
  101. extern unsigned int kfifo_in(struct kfifo *fifo,
  102. const unsigned char *from, unsigned int len);
  103. extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
  104. unsigned char *to, unsigned int len);
  105. /**
  106. * kfifo_reset - removes the entire FIFO contents
  107. * @fifo: the fifo to be emptied.
  108. */
  109. static inline void kfifo_reset(struct kfifo *fifo)
  110. {
  111. fifo->in = fifo->out = 0;
  112. }
  113. /**
  114. * kfifo_reset_out - skip FIFO contents
  115. * @fifo: the fifo to be emptied.
  116. */
  117. static inline void kfifo_reset_out(struct kfifo *fifo)
  118. {
  119. smp_mb();
  120. fifo->out = fifo->in;
  121. }
  122. /**
  123. * kfifo_size - returns the size of the fifo in bytes
  124. * @fifo: the fifo to be used.
  125. */
  126. static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)
  127. {
  128. return fifo->size;
  129. }
  130. /**
  131. * kfifo_len - returns the number of used bytes in the FIFO
  132. * @fifo: the fifo to be used.
  133. */
  134. static inline unsigned int kfifo_len(struct kfifo *fifo)
  135. {
  136. register unsigned int out;
  137. out = fifo->out;
  138. smp_rmb();
  139. return fifo->in - out;
  140. }
  141. /**
  142. * kfifo_is_empty - returns true if the fifo is empty
  143. * @fifo: the fifo to be used.
  144. */
  145. static inline __must_check int kfifo_is_empty(struct kfifo *fifo)
  146. {
  147. return fifo->in == fifo->out;
  148. }
  149. /**
  150. * kfifo_is_full - returns true if the fifo is full
  151. * @fifo: the fifo to be used.
  152. */
  153. static inline __must_check int kfifo_is_full(struct kfifo *fifo)
  154. {
  155. return kfifo_len(fifo) == kfifo_size(fifo);
  156. }
  157. /**
  158. * kfifo_avail - returns the number of bytes available in the FIFO
  159. * @fifo: the fifo to be used.
  160. */
  161. static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)
  162. {
  163. return kfifo_size(fifo) - kfifo_len(fifo);
  164. }
  165. /**
  166. * kfifo_in_locked - puts some data into the FIFO using a spinlock for locking
  167. * @fifo: the fifo to be used.
  168. * @from: the data to be added.
  169. * @n: the length of the data to be added.
  170. * @lock: pointer to the spinlock to use for locking.
  171. *
  172. * This function copies at most @len bytes from the @from buffer into
  173. * the FIFO depending on the free space, and returns the number of
  174. * bytes copied.
  175. */
  176. static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
  177. const unsigned char *from, unsigned int n, spinlock_t *lock)
  178. {
  179. unsigned long flags;
  180. unsigned int ret;
  181. spin_lock_irqsave(lock, flags);
  182. ret = kfifo_in(fifo, from, n);
  183. spin_unlock_irqrestore(lock, flags);
  184. return ret;
  185. }
  186. /**
  187. * kfifo_out_locked - gets some data from the FIFO using a spinlock for locking
  188. * @fifo: the fifo to be used.
  189. * @to: where the data must be copied.
  190. * @n: the size of the destination buffer.
  191. * @lock: pointer to the spinlock to use for locking.
  192. *
  193. * This function copies at most @len bytes from the FIFO into the
  194. * @to buffer and returns the number of copied bytes.
  195. */
  196. static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
  197. unsigned char *to, unsigned int n, spinlock_t *lock)
  198. {
  199. unsigned long flags;
  200. unsigned int ret;
  201. spin_lock_irqsave(lock, flags);
  202. ret = kfifo_out(fifo, to, n);
  203. /*
  204. * optimization: if the FIFO is empty, set the indices to 0
  205. * so we don't wrap the next time
  206. */
  207. if (kfifo_is_empty(fifo))
  208. kfifo_reset(fifo);
  209. spin_unlock_irqrestore(lock, flags);
  210. return ret;
  211. }
  212. extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
  213. extern __must_check unsigned int kfifo_from_user(struct kfifo *fifo,
  214. const void __user *from, unsigned int n);
  215. extern __must_check unsigned int kfifo_to_user(struct kfifo *fifo,
  216. void __user *to, unsigned int n);
  217. /*
  218. * __kfifo_add_out internal helper function for updating the out offset
  219. */
  220. static inline void __kfifo_add_out(struct kfifo *fifo,
  221. unsigned int off)
  222. {
  223. smp_mb();
  224. fifo->out += off;
  225. }
  226. /*
  227. * __kfifo_add_in internal helper function for updating the in offset
  228. */
  229. static inline void __kfifo_add_in(struct kfifo *fifo,
  230. unsigned int off)
  231. {
  232. smp_wmb();
  233. fifo->in += off;
  234. }
  235. /*
  236. * __kfifo_off internal helper function for calculating the index of a
  237. * given offeset
  238. */
  239. static inline unsigned int __kfifo_off(struct kfifo *fifo, unsigned int off)
  240. {
  241. return off & (fifo->size - 1);
  242. }
  243. /*
  244. * __kfifo_peek_n internal helper function for determinate the length of
  245. * the next record in the fifo
  246. */
  247. static inline unsigned int __kfifo_peek_n(struct kfifo *fifo,
  248. unsigned int recsize)
  249. {
  250. #define __KFIFO_GET(fifo, off, shift) \
  251. ((fifo)->buffer[__kfifo_off((fifo), (fifo)->out+(off))] << (shift))
  252. unsigned int l;
  253. l = __KFIFO_GET(fifo, 0, 0);
  254. if (--recsize)
  255. l |= __KFIFO_GET(fifo, 1, 8);
  256. return l;
  257. #undef __KFIFO_GET
  258. }
  259. /*
  260. * __kfifo_poke_n internal helper function for storing the length of
  261. * the next record into the fifo
  262. */
  263. static inline void __kfifo_poke_n(struct kfifo *fifo,
  264. unsigned int recsize, unsigned int n)
  265. {
  266. #define __KFIFO_PUT(fifo, off, val, shift) \
  267. ( \
  268. (fifo)->buffer[__kfifo_off((fifo), (fifo)->in+(off))] = \
  269. (unsigned char)((val) >> (shift)) \
  270. )
  271. __KFIFO_PUT(fifo, 0, n, 0);
  272. if (--recsize)
  273. __KFIFO_PUT(fifo, 1, n, 8);
  274. #undef __KFIFO_PUT
  275. }
  276. /*
  277. * __kfifo_in_... internal functions for put date into the fifo
  278. * do not call it directly, use kfifo_in_rec() instead
  279. */
  280. extern unsigned int __kfifo_in_n(struct kfifo *fifo,
  281. const void *from, unsigned int n, unsigned int recsize);
  282. extern unsigned int __kfifo_in_generic(struct kfifo *fifo,
  283. const void *from, unsigned int n, unsigned int recsize);
  284. static inline unsigned int __kfifo_in_rec(struct kfifo *fifo,
  285. const void *from, unsigned int n, unsigned int recsize)
  286. {
  287. unsigned int ret;
  288. ret = __kfifo_in_n(fifo, from, n, recsize);
  289. if (likely(ret == 0)) {
  290. if (recsize)
  291. __kfifo_poke_n(fifo, recsize, n);
  292. __kfifo_add_in(fifo, n + recsize);
  293. }
  294. return ret;
  295. }
  296. /**
  297. * kfifo_in_rec - puts some record data into the FIFO
  298. * @fifo: the fifo to be used.
  299. * @from: the data to be added.
  300. * @n: the length of the data to be added.
  301. * @recsize: size of record field
  302. *
  303. * This function copies @n bytes from the @from into the FIFO and returns
  304. * the number of bytes which cannot be copied.
  305. * A returned value greater than the @n value means that the record doesn't
  306. * fit into the buffer.
  307. *
  308. * Note that with only one concurrent reader and one concurrent
  309. * writer, you don't need extra locking to use these functions.
  310. */
  311. static inline __must_check unsigned int kfifo_in_rec(struct kfifo *fifo,
  312. void *from, unsigned int n, unsigned int recsize)
  313. {
  314. if (!__builtin_constant_p(recsize))
  315. return __kfifo_in_generic(fifo, from, n, recsize);
  316. return __kfifo_in_rec(fifo, from, n, recsize);
  317. }
  318. /*
  319. * __kfifo_out_... internal functions for get date from the fifo
  320. * do not call it directly, use kfifo_out_rec() instead
  321. */
  322. extern unsigned int __kfifo_out_n(struct kfifo *fifo,
  323. void *to, unsigned int reclen, unsigned int recsize);
  324. extern unsigned int __kfifo_out_generic(struct kfifo *fifo,
  325. void *to, unsigned int n,
  326. unsigned int recsize, unsigned int *total);
  327. static inline unsigned int __kfifo_out_rec(struct kfifo *fifo,
  328. void *to, unsigned int n, unsigned int recsize,
  329. unsigned int *total)
  330. {
  331. unsigned int l;
  332. if (!recsize) {
  333. l = n;
  334. if (total)
  335. *total = l;
  336. } else {
  337. l = __kfifo_peek_n(fifo, recsize);
  338. if (total)
  339. *total = l;
  340. if (n < l)
  341. return l;
  342. }
  343. return __kfifo_out_n(fifo, to, l, recsize);
  344. }
  345. /**
  346. * kfifo_out_rec - gets some record data from the FIFO
  347. * @fifo: the fifo to be used.
  348. * @to: where the data must be copied.
  349. * @n: the size of the destination buffer.
  350. * @recsize: size of record field
  351. * @total: pointer where the total number of to copied bytes should stored
  352. *
  353. * This function copies at most @n bytes from the FIFO to @to and returns the
  354. * number of bytes which cannot be copied.
  355. * A returned value greater than the @n value means that the record doesn't
  356. * fit into the @to buffer.
  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. */
  361. static inline __must_check unsigned int kfifo_out_rec(struct kfifo *fifo,
  362. void *to, unsigned int n, unsigned int recsize,
  363. unsigned int *total)
  364. {
  365. if (!__builtin_constant_p(recsize))
  366. return __kfifo_out_generic(fifo, to, n, recsize, total);
  367. return __kfifo_out_rec(fifo, to, n, recsize, total);
  368. }
  369. /*
  370. * __kfifo_from_user_... internal functions for transfer from user space into
  371. * the fifo. do not call it directly, use kfifo_from_user_rec() instead
  372. */
  373. extern unsigned int __kfifo_from_user_n(struct kfifo *fifo,
  374. const void __user *from, unsigned int n, unsigned int recsize);
  375. extern unsigned int __kfifo_from_user_generic(struct kfifo *fifo,
  376. const void __user *from, unsigned int n, unsigned int recsize);
  377. static inline unsigned int __kfifo_from_user_rec(struct kfifo *fifo,
  378. const void __user *from, unsigned int n, unsigned int recsize)
  379. {
  380. unsigned int ret;
  381. ret = __kfifo_from_user_n(fifo, from, n, recsize);
  382. if (likely(ret == 0)) {
  383. if (recsize)
  384. __kfifo_poke_n(fifo, recsize, n);
  385. __kfifo_add_in(fifo, n + recsize);
  386. }
  387. return ret;
  388. }
  389. /**
  390. * kfifo_from_user_rec - puts some data from user space into the FIFO
  391. * @fifo: the fifo to be used.
  392. * @from: pointer to the data to be added.
  393. * @n: the length of the data to be added.
  394. * @recsize: size of record field
  395. *
  396. * This function copies @n bytes from the @from into the
  397. * FIFO and returns the number of bytes which cannot be copied.
  398. *
  399. * If the returned value is equal or less the @n value, the copy_from_user()
  400. * functions has failed. Otherwise the record doesn't fit into the buffer.
  401. *
  402. * Note that with only one concurrent reader and one concurrent
  403. * writer, you don't need extra locking to use these functions.
  404. */
  405. static inline __must_check unsigned int kfifo_from_user_rec(struct kfifo *fifo,
  406. const void __user *from, unsigned int n, unsigned int recsize)
  407. {
  408. if (!__builtin_constant_p(recsize))
  409. return __kfifo_from_user_generic(fifo, from, n, recsize);
  410. return __kfifo_from_user_rec(fifo, from, n, recsize);
  411. }
  412. /*
  413. * __kfifo_to_user_... internal functions for transfer fifo data into user space
  414. * do not call it directly, use kfifo_to_user_rec() instead
  415. */
  416. extern unsigned int __kfifo_to_user_n(struct kfifo *fifo,
  417. void __user *to, unsigned int n, unsigned int reclen,
  418. unsigned int recsize);
  419. extern unsigned int __kfifo_to_user_generic(struct kfifo *fifo,
  420. void __user *to, unsigned int n, unsigned int recsize,
  421. unsigned int *total);
  422. static inline unsigned int __kfifo_to_user_rec(struct kfifo *fifo,
  423. void __user *to, unsigned int n,
  424. unsigned int recsize, unsigned int *total)
  425. {
  426. unsigned int l;
  427. if (!recsize) {
  428. l = n;
  429. if (total)
  430. *total = l;
  431. } else {
  432. l = __kfifo_peek_n(fifo, recsize);
  433. if (total)
  434. *total = l;
  435. if (n < l)
  436. return l;
  437. }
  438. return __kfifo_to_user_n(fifo, to, n, l, recsize);
  439. }
  440. /**
  441. * kfifo_to_user_rec - gets data from the FIFO and write it to user space
  442. * @fifo: the fifo to be used.
  443. * @to: where the data must be copied.
  444. * @n: the size of the destination buffer.
  445. * @recsize: size of record field
  446. * @total: pointer where the total number of to copied bytes should stored
  447. *
  448. * This function copies at most @n bytes from the FIFO to the @to.
  449. * In case of an error, the function returns the number of bytes which cannot
  450. * be copied.
  451. * If the returned value is equal or less the @n value, the copy_to_user()
  452. * functions has failed. Otherwise the record doesn't fit into the @to buffer.
  453. *
  454. * Note that with only one concurrent reader and one concurrent
  455. * writer, you don't need extra locking to use these functions.
  456. */
  457. static inline __must_check unsigned int kfifo_to_user_rec(struct kfifo *fifo,
  458. void __user *to, unsigned int n, unsigned int recsize,
  459. unsigned int *total)
  460. {
  461. if (!__builtin_constant_p(recsize))
  462. return __kfifo_to_user_generic(fifo, to, n, recsize, total);
  463. return __kfifo_to_user_rec(fifo, to, n, recsize, total);
  464. }
  465. /*
  466. * __kfifo_peek_... internal functions for peek into the next fifo record
  467. * do not call it directly, use kfifo_peek_rec() instead
  468. */
  469. extern unsigned int __kfifo_peek_generic(struct kfifo *fifo,
  470. unsigned int recsize);
  471. /**
  472. * kfifo_peek_rec - gets the size of the next FIFO record data
  473. * @fifo: the fifo to be used.
  474. * @recsize: size of record field
  475. *
  476. * This function returns the size of the next FIFO record in number of bytes
  477. */
  478. static inline __must_check unsigned int kfifo_peek_rec(struct kfifo *fifo,
  479. unsigned int recsize)
  480. {
  481. if (!__builtin_constant_p(recsize))
  482. return __kfifo_peek_generic(fifo, recsize);
  483. if (!recsize)
  484. return kfifo_len(fifo);
  485. return __kfifo_peek_n(fifo, recsize);
  486. }
  487. /*
  488. * __kfifo_skip_... internal functions for skip the next fifo record
  489. * do not call it directly, use kfifo_skip_rec() instead
  490. */
  491. extern void __kfifo_skip_generic(struct kfifo *fifo, unsigned int recsize);
  492. static inline void __kfifo_skip_rec(struct kfifo *fifo,
  493. unsigned int recsize)
  494. {
  495. unsigned int l;
  496. if (recsize) {
  497. l = __kfifo_peek_n(fifo, recsize);
  498. if (l + recsize <= kfifo_len(fifo)) {
  499. __kfifo_add_out(fifo, l + recsize);
  500. return;
  501. }
  502. }
  503. kfifo_reset_out(fifo);
  504. }
  505. /**
  506. * kfifo_skip_rec - skip the next fifo out record
  507. * @fifo: the fifo to be used.
  508. * @recsize: size of record field
  509. *
  510. * This function skips the next FIFO record
  511. */
  512. static inline void kfifo_skip_rec(struct kfifo *fifo,
  513. unsigned int recsize)
  514. {
  515. if (!__builtin_constant_p(recsize))
  516. __kfifo_skip_generic(fifo, recsize);
  517. else
  518. __kfifo_skip_rec(fifo, recsize);
  519. }
  520. /**
  521. * kfifo_avail_rec - returns the number of bytes available in a record FIFO
  522. * @fifo: the fifo to be used.
  523. * @recsize: size of record field
  524. */
  525. static inline __must_check unsigned int kfifo_avail_rec(struct kfifo *fifo,
  526. unsigned int recsize)
  527. {
  528. unsigned int l = kfifo_size(fifo) - kfifo_len(fifo);
  529. return (l > recsize) ? l - recsize : 0;
  530. }
  531. #endif