Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2047218
  • 博文数量: 505
  • 博客积分: 1552
  • 博客等级: 上尉
  • 技术积分: 2514
  • 用 户 组: 普通用户
  • 注册时间: 2007-09-23 18:24
文章分类

全部博文(505)

文章存档

2019年(12)

2018年(15)

2017年(1)

2016年(17)

2015年(14)

2014年(93)

2013年(233)

2012年(108)

2011年(1)

2009年(11)

分类: LINUX

2013-12-20 13:57:20

转自:http://blog.csdn.net/lamdoc/article/details/7662426

linux 内核通用队列称为 kfifo.  定义于

linux 的 kfifo 和多数其他队列一样,也提供了两个主要函数,enqueue(入队列) 和 dequeue(出队列)

kfifo 对象 维护了两个偏移量,入口偏移 和 出口偏移。

入口偏移 指下一次入队列时的位置

出口偏移 指下一次出队列的位置。

出口偏移 总是小于等于 入口偏移,否则就意味着要出队列的元素根本没有入队列。

1. 创建队列:

a. kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask) : 动态创建, (常用),

该函数创建并初始化一个大小为size的kfifo. gfp_mask  用来标识分配队列。

  1. /** 
  2.  * kfifo_alloc - allocates a new FIFO internal buffer 
  3.  * @fifo: the fifo to assign then new buffer 
  4.  * @size: the size of the buffer to be allocated, this have to be a power of 2. 
  5.  * @gfp_mask: get_free_pages mask, passed to kmalloc() 
  6.  * 
  7.  * This function dynamically allocates a new fifo internal buffer 
  8.  * 
  9.  * The size will be rounded-up to a power of 2. 
  10.  * The buffer will be release with kfifo_free(). 
  11.  * Return 0 if no error, otherwise the an error code 
  12.  */  
  13. int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask)  
  14. {  
  15.     unsigned char *buffer;  
  16.   
  17.     /* 
  18.      * round up to the next power of 2, since our 'let the indices 
  19.      * wrap' technique works only in this case. 
  20.      */  
  21.     if (!is_power_of_2(size)) {  //size必须是2的指数次幂  
  22.         BUG_ON(size > 0x80000000);  
  23.         size = roundup_pow_of_two(size); //如果不是整成是~  
  24.     }  
  25.   
  26.     buffer = kmalloc(size, gfp_mask);  
  27.     if (!buffer) {  
  28.         _kfifo_init(fifo, NULL, 0);  
  29.         return -ENOMEM;  
  30.     }  
  31.   
  32.     _kfifo_init(fifo, buffer, size); //初始化fifo  
  33.   
  34.     return 0;  
  35. }  
  1. static void _kfifo_init(struct kfifo *fifo, void *buffer,  
  2.         unsigned int size)  
  3. {  
  4.     fifo->buffer = buffer;  
  5.     fifo->size = size;  
  6.   
  7.     kfifo_reset(fifo);  
  8. }  

  1. /** 
  2.  * kfifo_reset - removes the entire FIFO contents 
  3.  * @fifo: the fifo to be emptied. 
  4.  */  
  5. static inline void kfifo_reset(struct kfifo *fifo)  
  6. {  
  7.     fifo->in = fifo->out = 0;  
  8. }  

例:
  1. struct kfifo fifo;  
  2.   
  3. int ret;  
  4.   
  5. ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);  
  6.   
  7. if(ret)  
  8.   
  9.     return ret;  
  10.   
  11. //fifo 现在是一个大小为PAGE_SIZE的队列  

b. kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size):

该函数创建并初始化一个kfifo,它将使用 由 buffer 指向的 大小为size 的内存

  1. /** 
  2.  * kfifo_init - initialize a FIFO using a preallocated buffer 
  3.  * @fifo: the fifo to assign the buffer 
  4.  * @buffer: the preallocated buffer to be used. 
  5.  * @size: the size of the internal buffer, this has to be a power of 2. 
  6.  * 
  7.  */  
  8. void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)  
  9. {  
  10.     /* size must be a power of 2 */  
  11.     BUG_ON(!is_power_of_2(size)); //size必须是2的指数次幂  
  12.   
  13.     _kfifo_init(fifo, buffer, size);  
  14. }  
  15. EXPORT_SYMBOL(kfifo_init);  

c. 静态创建kfifo,(不大常用)

DECLARE_KFIFO(name, size) --- 将创建一个名字为name,大小为size的kfifo对象。

  1. /** 
  2.  * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer 
  3.  * @name: name of the declared kfifo datatype 
  4.  * @size: size of the fifo buffer. Must be a power of two. 
  5.  * 
  6.  * Note1: the macro can be used inside struct or union declaration 
  7.  * Note2: the macro creates two objects: 
  8.  *  A kfifo object with the given name and a buffer for the kfifo 
  9.  *  object named name##kfifo_buffer 
  10.  */  
  11. #define DECLARE_KFIFO(name, size) \  
  12. union { \  
  13.     struct kfifo name; \  
  14.     unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \  
  15. }  
 INIT_KFIFO(name) --- 初始化kfifo
  1. /** 
  2.  * INIT_KFIFO - Initialize a kfifo declared by DECLARE_KFIFO 
  3.  * @name: name of the declared kfifo datatype 
  4.  */  
  5. #define INIT_KFIFO(name) \  
  6.     name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \  
  7.                 sizeof(struct kfifo), \  
  8.                 name##kfifo_buffer + sizeof(struct kfifo))  
  1. /* 
  2.  * Macros for declaration and initialization of the kfifo datatype 
  3.  */  
  4.   
  5. /* helper macro */  
  6. #define __kfifo_initializer(s, b) \  
  7.     (struct kfifo) { \  
  8.         .size   = s, \  
  9.         .in = 0, \  
  10.         .out    = 0, \  
  11.         .buffer = b \  
  12.     }  

DEFINE_KFIFO(name, size)  =DECLARE_KFIFO(name, size) +  INIT_KFIFO(name)

  1. /** 
  2.  * DEFINE_KFIFO - macro to define and initialize a kfifo 
  3.  * @name: name of the declared kfifo datatype 
  4.  * @size: size of the fifo buffer. Must be a power of two. 
  5.  * 
  6.  * Note1: the macro can be used for global and local kfifo data type variables 
  7.  * Note2: the macro creates two objects: 
  8.  *  A kfifo object with the given name and a buffer for the kfifo 
  9.  *  object named name##kfifo_buffer 
  10.  */  
  11. #define DEFINE_KFIFO(name, size) \  
  12.     unsigned char name##kfifo_buffer[size]; \  
  13.     struct kfifo name = __kfifo_initializer(size, name##kfifo_buffer)  

2. kfifo_in(struct kfifo *fifo, const void *from, unsigned int len) : 入队列操作:

该函数把from指针所指向的 len字节长度的 数据拷贝到fifo所指队列中。

成功则返回推入的字节长度。

  1. /** 
  2.  * kfifo_in - puts some data into the FIFO 
  3.  * @fifo: the fifo to be used. 
  4.  * @from: the data to be added. 
  5.  * @len: the length of the data to be added. 
  6.  * 
  7.  * This function copies at most @len bytes from the @from buffer into 
  8.  * the FIFO depending on the free space, and returns the number of 
  9.  * bytes copied. 
  10.  * 
  11.  * Note that with only one concurrent reader and one concurrent 
  12.  * writer, you don't need extra locking to use these functions. 
  13.  */  
  14. unsigned int kfifo_in(struct kfifo *fifo, const void *from,  
  15.                 unsigned int len)  
  16. {  
  17.     len = min(kfifo_avail(fifo), len);  
  18.   
  19.     __kfifo_in_data(fifo, from, len, 0);  
  20.     __kfifo_add_in(fifo, len);  
  21.     return len;  
  22. "color:#FF0000;">"font-size:12px;">  
  23.   
3. kfifo_out(struct kfifo *fifo, void *to, unsigned int len) : 出队列操作:

该函数从 fifo所指向的队列中 拷贝出 长度为len字节的数据 到 to所指的缓冲 中。

成功返回拷贝数据的长度。

  1. /** 
  2.  * kfifo_out - gets some data from the FIFO 
  3.  * @fifo: the fifo to be used. 
  4.  * @to: where the data must be copied. 
  5.  * @len: the size of the destination buffer. 
  6.  * 
  7.  * This function copies at most @len bytes from the FIFO into the 
  8.  * @to buffer and returns the number of copied bytes. 
  9.  * 
  10.  * Note that with only one concurrent reader and one concurrent 
  11.  * writer, you don't need extra locking to use these functions. 
  12.  */  
  13. unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)  
  14. {  
  15.     len = min(kfifo_len(fifo), len);  
  16.   
  17.     __kfifo_out_data(fifo, to, len, 0);  
  18.     __kfifo_add_out(fifo, len);  
  19.   
  20.     return len;  
  21. }  
  22. EXPORT_SYMBOL(kfifo_out);  
数据被出队列之后,就不再存于队列当中,这是常用队列操作。如果仅仅想“偷窥”下队列中的数据,不想删除它,可以用:

kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset)

  1. /** 
  2.  * kfifo_out_peek - copy some data from the FIFO, but do not remove it 
  3.  * @fifo: the fifo to be used. 
  4.  * @to: where the data must be copied. 
  5.  * @len: the size of the destination buffer. 
  6.  * @offset: offset into the fifo 
  7.  * 
  8.  * This function copies at most @len bytes at @offset from the FIFO 
  9.  * into the @to buffer and returns the number of copied bytes. 
  10.  * The data is not removed from the FIFO. 
  11.  */  
  12. unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len,  
  13.                 unsigned offset)  
  14. {  
  15.     len = min(kfifo_len(fifo), len + offset);  
  16.   
  17.     __kfifo_out_data(fifo, to, len, offset);  
  18.     return len;  
  19. }  
  20. EXPORT_SYMBOL(kfifo_out_peek);  
4. 获取队列长度:

a. kfifo_size(struct kfifo *fifo) : kfifo 队列总体长度

  1. /** 
  2.  * kfifo_size - returns the size of the fifo in bytes 
  3.  * @fifo: the fifo to be used. 
  4.  */  
  5. static inline __must_check unsigned int kfifo_size(struct kfifo *fifo)  
  6. {  
  7.     return fifo->size;  
  8. }  
b. kfifo_len(struct kfifo *fifo) :kfifo队列中已推入数据大小
  1. /** 
  2.  * kfifo_len - returns the number of used bytes in the FIFO 
  3.  * @fifo: the fifo to be used. 
  4.  */  
  5. static inline unsigned int kfifo_len(struct kfifo *fifo)  
  6. {  
  7.     register unsigned int   out;  
  8.   
  9.     out = fifo->out;  
  10.     smp_rmb();  
  11.     return fifo->in - out;  
  12. }  
c. kfifo_avail(struct kfifo *fifo) : kfifo队列中,还有多少可用空间
  1. /** 
  2.  * kfifo_avail - returns the number of bytes available in the FIFO 
  3.  * @fifo: the fifo to be used. 
  4.  */  
  5. static inline __must_check unsigned int kfifo_avail(struct kfifo *fifo)  
  6. {  
  7.     return kfifo_size(fifo) - kfifo_len(fifo);  
  8. }  
d. kfifo_is_empty(struct kfifo *fifo) :是否为空
  1. /** 
  2.  * kfifo_is_empty - returns true if the fifo is empty 
  3.  * @fifo: the fifo to be used. 
  4.  */  
  5. static inline __must_check int kfifo_is_empty(struct kfifo *fifo)  
  6. {  
  7.     return fifo->in == fifo->out;  
  8. }  
e. kfifo_is_full(struct kfifo *fifo) : 是否已满
  1. /** 
  2.  * kfifo_is_full - returns true if the fifo is full 
  3.  * @fifo: the fifo to be used. 
  4.  */  
  5. static inline __must_check int kfifo_is_full(struct kfifo *fifo)  
  6. {  
  7.     return kfifo_len(fifo) == kfifo_size(fifo);  
  8. }  
5. kfifo_reset(struct kfifo *fifo) : 重置队列,即清空队列中的内容
  1. /** 
  2.  * kfifo_reset - removes the entire FIFO contents 
  3.  * @fifo: the fifo to be emptied. 
  4.  */  
  5. static inline void kfifo_reset(struct kfifo *fifo)  
  6. {  
  7.     fifo->in = fifo->out = 0;  
  8. }  
kfifo_free(struct kfifo *fifo) : 撤销队列, 与kfifo_alloc对应。
  1. /** 
  2.  * kfifo_free - frees the FIFO internal buffer 
  3.  * @fifo: the fifo to be freed. 
  4.  */  
  5. void kfifo_free(struct kfifo *fifo)  
  6. {  
  7.     kfree(fifo->buffer);  
  8.     _kfifo_init(fifo, NULL, 0);  
  9. }  
  10. EXPORT_SYMBOL(kfifo_free);  
如果是kfifo_init()创建的,还需要释放相关缓冲(buffer)

6. kfifo使用举例:

a. 将0-31压入名为fifo的队列:

  1. unsigned int i;  
  2.   
  3. for(i = 0; i < 32; i++)  //将0 - 31 压入名为fifo的队列中  
  4.   
  5.     kfifo_in(fifo, &i, sizeof(i));  
b. 查看一下队列的第一个元素是不是0:
  1. unsigned int val;  
  2.   
  3. int ret;  
  4.   
  5. ret = kfifo_out_peek(fifo, &val, sizeof(val), 0);  
  6.   
  7. if (ret != sizeof(val))  
  8.   
  9.      return -EINVAL;  
  10.   
  11. printk(KERN_INFO, "%u\n",val);  

c. 出队列,并打印kfifo中的所有元素,即将上面的0-31 打印出来。

  1. while(kfifo_avail(fifo)) {  
  2.   
  3.     unsigned int val;  
  4.   
  5.     int ret;  
  6.   
  7.     ret = kfifo_out(fifo, &val, sizeof(val));  
  8.   
  9.     if(ret != sizeof(val))  
  10.   
  11.         return -EINVAL;  
  12.   
  13.     printk(KERN_INFO, "%u\n", val);  
  14.   

阅读(1275) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册