-
ldd3-5-1.png (7.74 KB, 下載次數(shù): 189)
| struct kfifo { unsigned char *buffer; /* the buffer holding the data */ unsigned int size; /* the size of the allocated buffer */ unsigned int in; /* data is added at offset (in % size) */ unsigned int out; /* data is extracted from off. (out % size) */ spinlock_t *lock; /* protects concurrent modifications */ }; |
| /** * 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>0)的目的在于put/get中從虛擬索引計(jì)算真實(shí)索引,size & (size - 1)是常用判斷技巧 fifo = kmalloc(sizeof(struct kfifo), gfp_mask); //分配kfifo數(shù)據(jù)結(jié)構(gòu) if (!fifo) return ERR_PTR(-ENOMEM); fifo->buffer = buffer; fifo->size = size; fifo->in = fifo->out = 0; //當(dāng)fifo->in == fifo->out 時(shí)，表示空隊(duì)列 fifo->lock = 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. */ //通過調(diào)用kfifo_alloc分配隊(duì)列空間，該函數(shù)會(huì)調(diào)用kfifo_init初始化kfifo結(jié)構(gòu)體，并調(diào)整size的大小以適應(yīng)運(yùn)算 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調(diào)整最近的2^k次方附近 BUG_ON(size > 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->size - fifo->in + fifo->out，這段代碼計(jì)算空閑的空間 //in是寫索引，out是讀索引，而且put與get操作都是分別增加in與out的值來重新計(jì)算虛擬索引 //注意，out 始終不會(huì)大于 in，(in - out)是有效數(shù)據(jù)空間大小，size是總空間的大小 //那么空閑的空間大小就是 size - (int - out) //如果請(qǐng)求的len大于空閑空間，就使len = size - (int - out) len = min(len, fifo->size - fifo->in + fifo->out); /* * Ensure that we sample the fifo->out index -before- we * start putting bytes into the kfifo. */ smp_mb(); /* first put the data starting from fifo->in to buffer end */ //(fifo->in & (fifo->size - 1))這段代碼計(jì)算真實(shí)的寫索引偏移，筆者假設(shè)為real_in //這是因?yàn)閕n在每次調(diào)用put之后都會(huì)增加一個(gè)len的長(zhǎng)度 //由于fifo->size必定是2的k次方，而(fifo->size - 1)就是類似0x00FFFFF的值 //(fifo->in & (fifo->size - 1))的操作從數(shù)學(xué)角度將就是對(duì)長(zhǎng)度fifo->size的取模運(yùn)算 //這里能用AND運(yùn)算代替取模運(yùn)算得益于前面申請(qǐng)的空間大小為2^k次方 //l = min(空閑空間大小,從real_in開始到緩沖區(qū)結(jié)尾的空間) l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); //先從buffer中拷貝l字節(jié)到緩沖區(qū)剩余空間，l<=len，也<=從real_in開始到緩沖區(qū)結(jié)尾的空間 //所以這個(gè)copy可能沒拷貝完，但是不會(huì)造成緩沖區(qū)越界 memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); /* then put the rest (if any) at the beginning of the buffer */ //當(dāng)len > l時(shí)，拷貝buffer中剩余的內(nèi)容，其實(shí)地址當(dāng)然為buffer + l，而剩余的大小為len - l //當(dāng)len == l時(shí)，下面的memcpy啥都不干，絕對(duì)精妙的算法 memcpy(fifo->buffer, buffer + l, len - l); /* * Ensure that we add the bytes to the kfifo -before- * we update the fifo->in index. */ smp_wmb(); //更新in（寫者）的邏輯索引 fifo->in += 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; //讀取的大小不能超過有效空間長(zhǎng)度 //經(jīng)過min運(yùn)算后len <= 請(qǐng)求的空間len, len <= size len = min(len, fifo->in - fifo->out); /* * Ensure that we sample the fifo->in index -before- we * start removing bytes from the kfifo. */ smp_rmb(); /* first get the data from fifo->out until the end of the buffer */ //同理，fifo->out & (fifo->size - 1)等于out（讀者）的虛擬索引計(jì)算出來真實(shí)索引real_out //fifo->size - real_out就等于該索引到緩沖區(qū)尾部的空間大小 //經(jīng)過min運(yùn)算后,l<=len,l<=real_out至緩沖區(qū)尾部的空間大小 l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); //從real_out開始拷貝l字節(jié)內(nèi)容到buffer中 memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); /* then get the rest (if any) from the beginning of the buffer */ //如果l<len，那么從fifo->buffer的首部開始繼續(xù)拷貝剩下的內(nèi)容 //如果l == len，memcpy啥都不干 memcpy(buffer + l, fifo->buffer, len - l); /* * Ensure that we remove the bytes from the kfifo -before- * we update the fifo->out index. */ smp_mb(); //更新out（讀者）的虛擬索引 fifo->out += len; return len; } |
ldd3-5-1.png (7.74 KB, 下載次數(shù): 189)
145.2 KB, 下載次數(shù): 850
//注意，out 始終不會(huì)大于 in，(in - out)是有效數(shù)據(jù)空間大小，size是總空間的大小
//那么空閑的空間大小就是 size - (int - out)
//如果請(qǐng)求的len大于空閑空間，就使len = size - (int - out)
len = min(len, fifo->size - fifo->in + fifo->out);
原帖由 Godbach 于 2009-3-23 13:20 發(fā)表
考慮到一個(gè)極限的情況啊。因?yàn)檫@里的in和out是一直增加的，那么當(dāng)存在in溢出，out還沒溢出的時(shí)候，是不是有一定的問題了？
原帖由 springtty 于 2009-3-23 23:51 發(fā)表
是的，就是考慮到這種情況。
謝謝各位老大的鼓勵(lì)：）
//如果請(qǐng)求的len大于空閑空間，就使len = size - (int - out)
len = min(len, fifo->size - fifo->in + fifo->out);
原帖由 Godbach 于 2009-3-24 09:56 發(fā)表
出現(xiàn)in溢出的時(shí)候：
這個(gè)結(jié)果還正確嗎？
原帖由 springtty 于 2009-3-25 12:56 發(fā)表
這里的in溢出而out沒有溢出是不是指 in（寫入）而out（讀取）的指針環(huán)繞的情況。
這里應(yīng)該避免這種情況，要不然就不能達(dá)到互斥訪問緩沖區(qū)的目的了。
原帖由 Godbach 于 2009-3-25 14:06 發(fā)表
這里的in和out不都是unsigned int類型的嘛。而且你說out 不會(huì)大于in的。
那么當(dāng)出現(xiàn)in超過該類型的最大值時(shí)，是不是溢出了，它的值是不是回繞到比較小的無符號(hào)整數(shù)了。
原帖由 springtty 于 2009-3-25 22:52 發(fā)表
我理解錯(cuò)了，以為是buffer的溢出。
你說的情況確實(shí)存在，我只考慮數(shù)學(xué)層面上的東西了。
不過如果真的發(fā)生這種情況，程序還是正確的：
unsigned int out = 0xfffffff0;
unsigned int in = 0x00000006;
...
len = min(len, fifo->size - fifo->in + fifo->out);
原帖由 Godbach 于 2009-3-25 23:10 發(fā)表
buffer的話應(yīng)該不會(huì)溢出了，程序里面已經(jīng)控制好了。
在接著寫的時(shí)候，實(shí)際可寫的長(zhǎng)度通過如下代碼判斷，就算in是溢出的值，應(yīng)該也沒有問題。
原帖由 springtty 于 2009-3-25 23:42 發(fā)表
kfifo的代碼雖短，但是蘊(yùn)含的東西卻很多。
我一直沒考慮到整數(shù)溢出的問題，看來以后自己寫代碼時(shí)得多加注意了。
原帖由 epegasus 于 2009-3-26 09:52 發(fā)表
環(huán)型緩沖是一種內(nèi)存管理方式，那改如何使用，使用的場(chǎng)景，以及和驅(qū)動(dòng)中銜接的接口是怎么樣的呢？
還煩請(qǐng)樓主做再接再厲
| 歡迎光臨 Chinaunix (http://72891.cn/) | Powered by Discuz! X3.2 |
