免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 4702 | 回复: 9

[C] 内核中kfifo.c相关的问题【已解决】 [复制链接]

论坛徽章:
0
发表于 2013-06-28 10:37 |显示全部楼层
本帖最后由 txgc_wm 于 2013-06-29 16:33 编辑

先上内核循环缓冲结构体的定义:
  1. struct kfifo {
  2.         unsigned char *buffer;        /* the buffer holding the data */
  3.         unsigned int size;        /* the size of the allocated buffer */
  4.         unsigned int in;        /* data is added at offset (in % size) */
  5.         unsigned int out;        /* data is extracted from off. (out % size) */
  6.         spinlock_t *lock;        /* protects concurrent modifications */
  7. };
复制代码
如果对“Linux内核中的循环缓冲区”不是很了解的话,可以先参考这里

对于结构体内的in和out两个变量,内核是作如下处理的:1、在读入数据时增加in;2、在取出数据时增加out;3、当检测到两个相等的时候将它们复位归0。1和2不作讨论和分析,针对第3点的处理,内核代码如下:
  1. static inline unsigned int kfifo_get(struct kfifo *fifo,
  2.                                      unsigned char *buffer, unsigned int len)
  3. {
  4.         unsigned long flags;
  5.         unsigned int ret;

  6.         spin_lock_irqsave(fifo->lock, flags);

  7.         ret = __kfifo_get(fifo, buffer, len);

  8.         /*
  9.          * optimization: if the FIFO is empty, set the indices to 0
  10.          * so we don't wrap the next time
  11.          */
  12.         if (fifo->in == fifo->out)
  13.                 fifo->in = fifo->out = 0;

  14.         spin_unlock_irqrestore(fifo->lock, flags);

  15.         return ret;
  16. }
复制代码
问题:当数据写入速度大于读取速度的时候,in和out的值将永远不会相等,也就是说buffer永远是有数据的,这样的话in和out都存在超出自身数值表示范围,从而导致错误?

针对这个问题,不知大家有什么好的建议?

问题已解决,参考这里

以下是摘自内核版本2.6.32.61的源码部分:
  1. /*
  2. * A simple kernel FIFO implementation.
  3. *
  4. * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
  5. *
  6. * This program is free software; you can redistribute it and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation; either version 2 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program; if not, write to the Free Software
  18. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19. *
  20. */
  21. #ifndef _LINUX_KFIFO_H
  22. #define _LINUX_KFIFO_H

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

  25. struct kfifo {
  26.         unsigned char *buffer;        /* the buffer holding the data */
  27.         unsigned int size;        /* the size of the allocated buffer */
  28.         unsigned int in;        /* data is added at offset (in % size) */
  29.         unsigned int out;        /* data is extracted from off. (out % size) */
  30.         spinlock_t *lock;        /* protects concurrent modifications */
  31. };

  32. extern struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
  33.                                 gfp_t gfp_mask, spinlock_t *lock);
  34. extern struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask,
  35.                                  spinlock_t *lock);
  36. extern void kfifo_free(struct kfifo *fifo);
  37. extern unsigned int __kfifo_put(struct kfifo *fifo,
  38.                                 const unsigned char *buffer, unsigned int len);
  39. extern unsigned int __kfifo_get(struct kfifo *fifo,
  40.                                 unsigned char *buffer, unsigned int len);

  41. /**
  42. * __kfifo_reset - removes the entire FIFO contents, no locking version
  43. * @fifo: the fifo to be emptied.
  44. */
  45. static inline void __kfifo_reset(struct kfifo *fifo)
  46. {
  47.         fifo->in = fifo->out = 0;
  48. }

  49. /**
  50. * kfifo_reset - removes the entire FIFO contents
  51. * @fifo: the fifo to be emptied.
  52. */
  53. static inline void kfifo_reset(struct kfifo *fifo)
  54. {
  55.         unsigned long flags;

  56.         spin_lock_irqsave(fifo->lock, flags);

  57.         __kfifo_reset(fifo);

  58.         spin_unlock_irqrestore(fifo->lock, flags);
  59. }

  60. /**
  61. * kfifo_put - puts some data into the FIFO
  62. * @fifo: the fifo to be used.
  63. * @buffer: the data to be added.
  64. * @len: the length of the data to be added.
  65. *
  66. * This function copies at most @len bytes from the @buffer into
  67. * the FIFO depending on the free space, and returns the number of
  68. * bytes copied.
  69. */
  70. static inline unsigned int kfifo_put(struct kfifo *fifo,
  71.                                 const unsigned char *buffer, unsigned int len)
  72. {
  73.         unsigned long flags;
  74.         unsigned int ret;

  75.         spin_lock_irqsave(fifo->lock, flags);

  76.         ret = __kfifo_put(fifo, buffer, len);

  77.         spin_unlock_irqrestore(fifo->lock, flags);

  78.         return ret;
  79. }

  80. /**
  81. * kfifo_get - gets some data from the FIFO
  82. * @fifo: the fifo to be used.
  83. * @buffer: where the data must be copied.
  84. * @len: the size of the destination buffer.
  85. *
  86. * This function copies at most @len bytes from the FIFO into the
  87. * @buffer and returns the number of copied bytes.
  88. */
  89. static inline unsigned int kfifo_get(struct kfifo *fifo,
  90.                                      unsigned char *buffer, unsigned int len)
  91. {
  92.         unsigned long flags;
  93.         unsigned int ret;

  94.         spin_lock_irqsave(fifo->lock, flags);

  95.         ret = __kfifo_get(fifo, buffer, len);

  96.         /*
  97.          * optimization: if the FIFO is empty, set the indices to 0
  98.          * so we don't wrap the next time
  99.          */
  100.         if (fifo->in == fifo->out)
  101.                 fifo->in = fifo->out = 0;

  102.         spin_unlock_irqrestore(fifo->lock, flags);

  103.         return ret;
  104. }

  105. /**
  106. * __kfifo_len - returns the number of bytes available in the FIFO, no locking version
  107. * @fifo: the fifo to be used.
  108. */
  109. static inline unsigned int __kfifo_len(struct kfifo *fifo)
  110. {
  111.         return fifo->in - fifo->out;
  112. }

  113. /**
  114. * kfifo_len - returns the number of bytes available in the FIFO
  115. * @fifo: the fifo to be used.
  116. */
  117. static inline unsigned int kfifo_len(struct kfifo *fifo)
  118. {
  119.         unsigned long flags;
  120.         unsigned int ret;

  121.         spin_lock_irqsave(fifo->lock, flags);

  122.         ret = __kfifo_len(fifo);

  123.         spin_unlock_irqrestore(fifo->lock, flags);

  124.         return ret;
  125. }
  126. #endif
复制代码
  1. /*
  2. * A simple kernel FIFO implementation.
  3. *
  4. * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
  5. *
  6. * This program is free software; you can redistribute it and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation; either version 2 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program; if not, write to the Free Software
  18. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19. *
  20. */

  21. #include <linux/kernel.h>
  22. #include <linux/module.h>
  23. #include <linux/slab.h>
  24. #include <linux/err.h>
  25. #include <linux/kfifo.h>
  26. #include <linux/log2.h>

  27. /**
  28. * kfifo_init - allocates a new FIFO using a preallocated buffer
  29. * @buffer: the preallocated buffer to be used.
  30. * @size: the size of the internal buffer, this have to be a power of 2.
  31. * @gfp_mask: get_free_pages mask, passed to kmalloc()
  32. * @lock: the lock to be used to protect the fifo buffer
  33. *
  34. * Do NOT pass the kfifo to kfifo_free() after use! Simply free the
  35. * &struct kfifo with kfree().
  36. */
  37. struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
  38.                          gfp_t gfp_mask, spinlock_t *lock)
  39. {
  40.         struct kfifo *fifo;

  41.         /* size must be a power of 2 */
  42.         BUG_ON(!is_power_of_2(size));

  43.         fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
  44.         if (!fifo)
  45.                 return ERR_PTR(-ENOMEM);

  46.         fifo->buffer = buffer;
  47.         fifo->size = size;
  48.         fifo->in = fifo->out = 0;
  49.         fifo->lock = lock;

  50.         return fifo;
  51. }
  52. EXPORT_SYMBOL(kfifo_init);

  53. /**
  54. * kfifo_alloc - allocates a new FIFO and its internal buffer
  55. * @size: the size of the internal buffer to be allocated.
  56. * @gfp_mask: get_free_pages mask, passed to kmalloc()
  57. * @lock: the lock to be used to protect the fifo buffer
  58. *
  59. * The size will be rounded-up to a power of 2.
  60. */
  61. struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
  62. {
  63.         unsigned char *buffer;
  64.         struct kfifo *ret;

  65.         /*
  66.          * round up to the next power of 2, since our 'let the indices
  67.          * wrap' technique works only in this case.
  68.          */
  69.         if (!is_power_of_2(size)) {
  70.                 BUG_ON(size > 0x80000000);
  71.                 size = roundup_pow_of_two(size);
  72.         }

  73.         buffer = kmalloc(size, gfp_mask);
  74.         if (!buffer)
  75.                 return ERR_PTR(-ENOMEM);

  76.         ret = kfifo_init(buffer, size, gfp_mask, lock);

  77.         if (IS_ERR(ret))
  78.                 kfree(buffer);

  79.         return ret;
  80. }
  81. EXPORT_SYMBOL(kfifo_alloc);

  82. /**
  83. * kfifo_free - frees the FIFO
  84. * @fifo: the fifo to be freed.
  85. */
  86. void kfifo_free(struct kfifo *fifo)
  87. {
  88.         kfree(fifo->buffer);
  89.         kfree(fifo);
  90. }
  91. EXPORT_SYMBOL(kfifo_free);

  92. /**
  93. * __kfifo_put - puts some data into the FIFO, no locking version
  94. * @fifo: the fifo to be used.
  95. * @buffer: the data to be added.
  96. * @len: the length of the data to be added.
  97. *
  98. * This function copies at most @len bytes from the @buffer into
  99. * the FIFO depending on the free space, and returns the number of
  100. * bytes copied.
  101. *
  102. * Note that with only one concurrent reader and one concurrent
  103. * writer, you don't need extra locking to use these functions.
  104. */
  105. unsigned int __kfifo_put(struct kfifo *fifo,
  106.                         const unsigned char *buffer, unsigned int len)
  107. {
  108.         unsigned int l;

  109.         len = min(len, fifo->size - fifo->in + fifo->out);

  110.         /*
  111.          * Ensure that we sample the fifo->out index -before- we
  112.          * start putting bytes into the kfifo.
  113.          */

  114.         smp_mb();

  115.         /* first put the data starting from fifo->in to buffer end */
  116.         l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
  117.         memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

  118.         /* then put the rest (if any) at the beginning of the buffer */
  119.         memcpy(fifo->buffer, buffer + l, len - l);

  120.         /*
  121.          * Ensure that we add the bytes to the kfifo -before-
  122.          * we update the fifo->in index.
  123.          */

  124.         smp_wmb();

  125.         fifo->in += len;

  126.         return len;
  127. }
  128. EXPORT_SYMBOL(__kfifo_put);

  129. /**
  130. * __kfifo_get - gets some data from the FIFO, no locking version
  131. * @fifo: the fifo to be used.
  132. * @buffer: where the data must be copied.
  133. * @len: the size of the destination buffer.
  134. *
  135. * This function copies at most @len bytes from the FIFO into the
  136. * @buffer and returns the number of copied bytes.
  137. *
  138. * Note that with only one concurrent reader and one concurrent
  139. * writer, you don't need extra locking to use these functions.
  140. */
  141. unsigned int __kfifo_get(struct kfifo *fifo,
  142.                          unsigned char *buffer, unsigned int len)
  143. {
  144.         unsigned int l;

  145.         len = min(len, fifo->in - fifo->out);

  146.         /*
  147.          * Ensure that we sample the fifo->in index -before- we
  148.          * start removing bytes from the kfifo.
  149.          */

  150.         smp_rmb();

  151.         /* first get the data from fifo->out until the end of the buffer */
  152.         l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
  153.         memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

  154.         /* then get the rest (if any) from the beginning of the buffer */
  155.         memcpy(buffer + l, fifo->buffer, len - l);

  156.         /*
  157.          * Ensure that we remove the bytes from the kfifo -before-
  158.          * we update the fifo->out index.
  159.          */

  160.         smp_mb();

  161.         fifo->out += len;

  162.         return len;
  163. }
  164. EXPORT_SYMBOL(__kfifo_get);
复制代码

论坛徽章:
0
发表于 2013-06-28 10:53 |显示全部楼层
in % size
out % size

论坛徽章:
0
发表于 2013-06-28 11:00 |显示全部楼层
本帖最后由 txgc_wm 于 2013-06-28 12:41 编辑

回复 2# lrita

楼主的意思是“给in和out设置一个阀值,接近的时候再对它们进行求余操作”?
抑或是建议在什么样的情况下进行以上的操作,能否具体说说你的想法?
   

论坛徽章:
0
发表于 2013-06-28 11:35 |显示全部楼层
回复 3# txgc_wm


    __kfifo_get已经保证了 int out 不会超过size了 那你还担心int 、out 超过表示范围?

论坛徽章:
0
发表于 2013-06-28 11:41 |显示全部楼层
本帖最后由 txgc_wm 于 2013-06-28 11:44 编辑

回复 4# lrita
__kfifo_get已经保证了 int out 不会超过size了
=>in和out的值是会超过size的,(in-out)肯定是小于等于size。问题中我所指的超出范围指的是“unsigned int”所能表示的最大值。以下两个变量可一直在作增量的操作:
  1. fifo->in += len;
  2. fifo->out += len;
复制代码

论坛徽章:
0
发表于 2013-06-28 11:48 |显示全部楼层
txgc_wm 发表于 2013-06-28 11:41
回复 4# lrita
__kfifo_get已经保证了 int out 不会超过size了
=>in和out的值是会超过size的,(in-out) ...

那你再仔细看下下面2段代码
out in 再怎么加也超不过size 所以不存在超过表示范围的问题。
按照你说的情况 write超过read 出现的情况只是buff写满而已。

论坛徽章:
0
发表于 2013-06-28 12:02 |显示全部楼层
回复 6# lrita

好吧,如果楼主认为你的观点是正确的话,可以写一个简单的测试用例看看答案。

为避免将其置位清零,请先将以下两句mark掉。
  1. if (buf->out == buf->in)
  2.         buf->out=buf->in = 0;
复制代码

论坛徽章:
0
发表于 2013-06-28 13:53 |显示全部楼层
txgc_wm 发表于 2013-06-28 12:02
回复 6# lrita

好吧,如果楼主认为你的观点是正确的话,可以写一个简单的测试用例看看答案。

看来你还没理解,给你比喻下吧。

读和写好比两个人A、B在赛跑。
A追上B后两个人就返回起点重赛,如果B跑的快,也就最多跑到终点等着B。

论坛徽章:
0
发表于 2013-06-28 14:07 |显示全部楼层
本帖最后由 txgc_wm 于 2013-06-28 14:25 编辑

回复 8# lrita

等写完测试例子运行后再说说相关的心得吧,在此之前请楼主不必急于回复。
也请先看看其他人对该部分的分析,比如我上面给的链接!
   

论坛徽章:
0
发表于 2013-06-29 16:48 |显示全部楼层
问题已解决!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP