内核源码kfifo分析

发表于 2009-4-9 14:51

/** * kfifo_init - allocates a new FIFO using a preallocated buffer * @buffer: the preallocated buffer to be used. * @size: the size of the internal buffer, this have to be a power of 2. * @gfp_mask: get_free_pages mask, passed to kmalloc() * @lock: the lock to be used to protect the fifo buffer * * Do NOT pass the kfifo to kfifo_free() after use! Simply free the * &struct kfifo with kfree(). */ struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,              gfp_t gfp_mask, spinlock_t *lock) {     struct kfifo *fifo;     /* size must be a power of 2 */     BUG_ON(size & (size - 1)); //大小必须为2的k次方(k&gt0)的目的在于put/get中从虚拟索引计算真实索引,size & (size - 1)是常用判断技巧     fifo = kmalloc(sizeof(struct kfifo), gfp_mask); //分配kfifo数据结构     if (!fifo)         return ERR_PTR(-ENOMEM);     fifo-&gtbuffer = buffer;     fifo-&gtsize = size;     fifo-&gtin = fifo-&gtout = 0; //当fifo-&gtin == fifo-&gtout 时，表示空队列     fifo-&gtlock = lock;     return fifo; } /** * kfifo_alloc - allocates a new FIFO and its internal buffer * @size: the size of the internal buffer to be allocated. * @gfp_mask: get_free_pages mask, passed to kmalloc() * @lock: the lock to be used to protect the fifo buffer * * The size will be rounded-up to a power of 2. */ //通过调用kfifo_alloc分配队列空间，该函数会调用kfifo_init初始化kfifo结构体，并调整size的大小以适应运算 struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock) {     unsigned char *buffer;     struct kfifo *ret;     /*      * round up to the next power of 2, since our 'let the indices      * wrap' tachnique works only in this case.      */     if (size & (size - 1)) { //如果size不是2的k次方，代码将size调整最近的2^k次方附近         BUG_ON(size &gt 0x80000000);         size = roundup_pow_of_two(size);     }     buffer = kmalloc(size, gfp_mask);     if (!buffer)         return ERR_PTR(-ENOMEM);     ret = kfifo_init(buffer, size, gfp_mask, lock);     if (IS_ERR(ret))         kfree(buffer);     return ret; } /** * __kfifo_put - puts some data into the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: the data to be added. * @len: the length of the data to be added. * * This function copies at most @len bytes from the @buffer into * the FIFO depending on the free space, and returns the number of * bytes copied. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. */ unsigned int __kfifo_put(struct kfifo *fifo,              unsigned char *buffer, unsigned int len) {     unsigned int l;     //fifo-&gtsize - fifo-&gtin + fifo-&gtout，这段代码计算空闲的空间     //in是写索引，out是读索引，而且put与get操作都是分别增加in与out的值来重新计算虚拟索引     //注意，out 始终不会大于 in，(in - out)是有效数据空间大小，size是总空间的大小     //那么空闲的空间大小就是 size - (int - out)     //如果请求的len大于空闲空间，就使len = size - (int - out)     len = min(len, fifo-&gtsize - fifo-&gtin + fifo-&gtout);      /*      * Ensure that we sample the fifo-&gtout index -before- we      * start putting bytes into the kfifo.      */     smp_mb();     /* first put the data starting from fifo-&gtin to buffer end */     //(fifo-&gtin & (fifo-&gtsize - 1))这段代码计算真实的写索引偏移，笔者假设为real_in     //这是因为in在每次调用put之后都会增加一个len的长度     //由于fifo-&gtsize必定是2的k次方，而(fifo-&gtsize - 1)就是类似0x00FFFFF的值     //(fifo-&gtin & (fifo-&gtsize - 1))的操作从数学角度将就是对长度fifo-&gtsize的取模运算     //这里能用AND运算代替取模运算得益于前面申请的空间大小为2^k次方     //l = min(空闲空间大小,从real_in开始到缓冲区结尾的空间)     l = min(len, fifo-&gtsize - (fifo-&gtin & (fifo-&gtsize - 1)));     //先从buffer中拷贝l字节到缓冲区剩余空间，l&lt=len，也&lt=从real_in开始到缓冲区结尾的空间     //所以这个copy可能没拷贝完，但是不会造成缓冲区越界     memcpy(fifo-&gtbuffer + (fifo-&gtin & (fifo-&gtsize - 1)), buffer, l);     /* then put the rest (if any) at the beginning of the buffer */     //当len &gt l时，拷贝buffer中剩余的内容，其实地址当然为buffer + l，而剩余的大小为len - l     //当len == l时，下面的memcpy啥都不干，绝对精妙的算法     memcpy(fifo-&gtbuffer, buffer + l, len - l);     /*      * Ensure that we add the bytes to the kfifo -before-      * we update the fifo-&gtin index.      */     smp_wmb();     //更新in（写者）的逻辑索引     fifo-&gtin += len;     return len; } /** * __kfifo_get - gets some data from the FIFO, no locking version * @fifo: the fifo to be used. * @buffer: where the data must be copied. * @len: the size of the destination buffer. * * This function copies at most @len bytes from the FIFO into the * @buffer and returns the number of copied bytes. * * Note that with only one concurrent reader and one concurrent * writer, you don't need extra locking to use these functions. */ unsigned int __kfifo_get(struct kfifo *fifo,              unsigned char *buffer, unsigned int len) {     unsigned int l;     //读取的大小不能超过有效空间长度     //经过min运算后len &lt= 请求的空间len, len &lt= size     len = min(len, fifo-&gtin - fifo-&gtout);     /*      * Ensure that we sample the fifo-&gtin index -before- we      * start removing bytes from the kfifo.      */     smp_rmb();     /* first get the data from fifo-&gtout until the end of the buffer */     //同理，fifo-&gtout & (fifo-&gtsize - 1)等于out（读者）的虚拟索引计算出来真实索引real_out     //fifo-&gtsize - real_out就等于该索引到缓冲区尾部的空间大小     //经过min运算后,l&lt=len,l&lt=real_out至缓冲区尾部的空间大小     l = min(len, fifo-&gtsize - (fifo-&gtout & (fifo-&gtsize - 1)));     //从real_out开始拷贝l字节内容到buffer中     memcpy(buffer, fifo-&gtbuffer + (fifo-&gtout & (fifo-&gtsize - 1)), l);     /* then get the rest (if any) from the beginning of the buffer */     //如果l&ltlen，那么从fifo-&gtbuffer的首部开始继续拷贝剩下的内容     //如果l == len，memcpy啥都不干     memcpy(buffer + l, fifo-&gtbuffer, len - l);     /*      * Ensure that we remove the bytes from the kfifo -before-      * we update the fifo-&gtout index.      */     smp_mb();     //更新out（读者）的虚拟索引     fifo-&gtout += len;     return len; }         从上面几个重要的函数可以看出一些特性，就是put函数能放入的数据长度永远不会大于缓冲区的长度，而fifo-&gtin - fifo-&gtout永远小于等于size。 get函数得到的数据永远小于等于size（这个是必然的）。

发表于 2009-4-9 14:58

[ZLG-ARM] 内核源码kfifo分析

相关帖子

kfifo是干什么的？有什么功能？

浏览过的版块