linuxカーネル内のループバッファ
Linuxカーネル内の循環バッファ(circular buffer)は、特定の場合の競合問題を解決するためにロックフリーの方法を提供します.このような特殊な状況は、生産者と消費者が1つしかない場合であり、他の場合にもロックをかけなければならない.
循環バッファはinclude/linux/kfifoで定義する.hでは、以下のようになる.
struct kfifo{unsigned char*buffer;//bufferはデータを格納するバッファunsigned int size;//sizeはバッファのサイズunsigned int;//inは書き込みポインタの下にunsigned int out;//outは読み取りポインタの下にspinlock_t*lock;//lockはstruct kfifoに追加されたスピンロック};(上記のロック免除は、ここのロックを免除するものではなく、このロックは必須です)は、複数のプロセスがこのデータ構造に同時にアクセスすることを防止します.in=outの場合、バッファが空であることを示します.(in-out)=sizeの場合、バッファがいっぱいであることを示します.kfifoに提供されるインタフェースは2つに分けることができる:1つは上述の状況を満たすために使用され、2つの下線で始まり、ロックされていない.もう1つのクラスは、満たされていない条件、すなわち、追加のロックが必要な場合に使用される.実は後のクラスは前のクラスに加えてロック後の包装を行っただけで(小さな改良も行われているところもある)、実現中に追加されたロックはspin_lock_irqsave.
クリアバッファの関数:static inline void_kfifo_reset(struct kfifo *fifo); static inline void kfifo_reset(struct kfifo *fifo); これは簡単で、直接読み書きポインタを0にすればいいです.
バッファにデータを入れるインタフェースは、static inline unsigned int kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len); unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len);
後者はkernel/kfifo.cで定義されています.このインタフェースは丹念に構成されており,いくつかの境界状況を注意深く回避することができる.私たちは一緒にその具体的な実現を見る必要があります.
len = min(len, fifo->size - fifo->in + fifo->out); lenと(fifo->size-fifo->in+fifo->out)の間に小さな値を取ってlenに割り当てます.なお、(fifo->in==fifo->out+fifo->size)ではバッファがいっぱいであることを示し、このとき得られる小さな値は0であり、後で実際に書き込まれるバイト数もすべて0であるに違いない.もう1つの境界状況は、lenが大きい場合(lenは記号がないため、負数もそれにとって大きな正数である)、fifo->inは常にfifo->out以上であるため、後の式l=min(len,fifo->size-(fifo->in&(fifosize->1));の値はfifo->sizeのサイズを超えません. smp_mb(); smp_wmb(); メモリバリアを追加します.ここでは議論の範囲ではありません.無視してもいいです. l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));前回決定した書き込むバイト数lenを「切り分ける」のですが、ここではもう一つのテクニックを使いました.注意:fifo->bufferに実際に割り当てられたバイト数fifo->sizeは、2のべき乗でなければなりません.そうしないと、ここでエラーが発生します.fifo->sizeが2のべき乗である以上、(fifo->size-1)つまり1つ後ろの数がすべて1の数であることは、(fifo->in&(fifo->size-1))が常に(fifo->size-1)を超えない部分であり、(fifo->in)%(fifo->size-1)の効果と同じであることを保証することができる.これにより、後続のコードは理解しにくくなり、fifo->inからバッファ末端までのブロックにデータを書き込み、まだ書き終わっていない場合はバッファヘッダから残りを書き込み、ループバッファを実現します.最後に、書き込みポインタをlenバイト後ろに移動し、lenを返します.以上から、fifo->inの値は0からfifo->sizeを超える数値に変化することができ、fifo->outも同様であるが、それらの差はfifo->sizeを超えない.
kfifoからデータを読み出す関数は、static inline unsigned int kfifo_です.get(struct kfifo *fifo, unsigned char *buffer, unsigned int len); unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len);
上の__とkfifo_putは似ていて、分析は難しくありません.
static inline unsigned int __kfifo_len(struct kfifo *fifo); static inline unsigned int kfifo_len(struct kfifo *fifo);
この2つの関数は、fifo->inからfifo->outを減算するだけでバッファ内の実際のバイト数を返します.
kernel/kfifo.cには、kfifoを初期化し、kfifoを割り当て、解放するインタフェースも用意されています.
struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock); struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock);
void kfifo_free(struct kfifo *fifo);
もう一度強調してkfifo_を呼び出しますinitはsizeが2のべき乗であることを保証しなければならないが、kfifo_allocは必要ありません.内部ではsizeを2のべき乗に上げます.kfifo_allocとkfifo_freeは、fifo->bufferにメモリ領域を割り当て/解放するため、2つの関数を組み合わせて使用します.kfifo_Initは割り当てられたスペースのfifo->bufferしか受け入れられず、kfifo->freeと組み合わせることができず、kfifo_Initが割り当てたkfifoはkfreeでしか解放できません.
ループバッファは、特にネットワークアダプタでドライバに多く使用されます.しかし、このロックフリー方式はカーネル反発において使用されることが少なく、代わりに別の高度な反発機構であるRCUが使用される.
循環バッファはinclude/linux/kfifoで定義する.hでは、以下のようになる.
struct kfifo{unsigned char*buffer;//bufferはデータを格納するバッファunsigned int size;//sizeはバッファのサイズunsigned int;//inは書き込みポインタの下にunsigned int out;//outは読み取りポインタの下にspinlock_t*lock;//lockはstruct kfifoに追加されたスピンロック};(上記のロック免除は、ここのロックを免除するものではなく、このロックは必須です)は、複数のプロセスがこのデータ構造に同時にアクセスすることを防止します.in=outの場合、バッファが空であることを示します.(in-out)=sizeの場合、バッファがいっぱいであることを示します.kfifoに提供されるインタフェースは2つに分けることができる:1つは上述の状況を満たすために使用され、2つの下線で始まり、ロックされていない.もう1つのクラスは、満たされていない条件、すなわち、追加のロックが必要な場合に使用される.実は後のクラスは前のクラスに加えてロック後の包装を行っただけで(小さな改良も行われているところもある)、実現中に追加されたロックはspin_lock_irqsave.
クリアバッファの関数:static inline void_kfifo_reset(struct kfifo *fifo); static inline void kfifo_reset(struct kfifo *fifo); これは簡単で、直接読み書きポインタを0にすればいいです.
バッファにデータを入れるインタフェースは、static inline unsigned int kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len); unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len);
後者はkernel/kfifo.cで定義されています.このインタフェースは丹念に構成されており,いくつかの境界状況を注意深く回避することができる.私たちは一緒にその具体的な実現を見る必要があります.
1: /** 2: * __kfifo_put - puts some data into the FIFO, no locking version 3: * @fifo: the fifo to be used. 4: * @buffer: 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 @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_put(struct kfifo *fifo, 15: const unsigned char *buffer, unsigned int len) 16: { 17: unsigned int l; 18: 19: len = min(len, fifo->size - fifo->in + fifo->out); 20: 21: /* 22: * Ensure that we sample the fifo->out index -before- we 23: * start putting bytes into the kfifo. 24: */ 25: 26: smp_mb(); 27: 28: /* first put the data starting from fifo->in to buffer end */ 29: l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); 30: memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); 31: 32: /* then put the rest (if any) at the beginning of the buffer */ 33: memcpy(fifo->buffer, buffer + l, len - l); 34: 35: /* 36: * Ensure that we add the bytes to the kfifo -before- 37: * we update the fifo->in index. 38: */ 39: 40: smp_wmb(); 41: 42: fifo->in += len; 43: 44: return len; 45: } 46: EXPORT_SYMBOL(__kfifo_put); 1: /** 2: * kfifo_put - puts some data into the FIFO 3: * @fifo: the fifo to be used. 4: * @buffer: 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 @buffer into 8: * the FIFO depending on the free space, and returns the number of 9: * bytes copied. 10: */ 11: static inline unsigned int kfifo_put(struct kfifo *fifo, 12: const unsigned char *buffer, unsigned int len) 13: { 14: unsigned long 15: unsigned int ret; 16: 17: spin_lock_irqsave(fifo->lock, flags); 18: 19: ret = __kfifo_put(fifo, buffer, len); 20: 21: spin_unlock_irqrestore(fifo->lock, flags); 22: 23: return ret; 24: }len = min(len, fifo->size - fifo->in + fifo->out); lenと(fifo->size-fifo->in+fifo->out)の間に小さな値を取ってlenに割り当てます.なお、(fifo->in==fifo->out+fifo->size)ではバッファがいっぱいであることを示し、このとき得られる小さな値は0であり、後で実際に書き込まれるバイト数もすべて0であるに違いない.もう1つの境界状況は、lenが大きい場合(lenは記号がないため、負数もそれにとって大きな正数である)、fifo->inは常にfifo->out以上であるため、後の式l=min(len,fifo->size-(fifo->in&(fifosize->1));の値はfifo->sizeのサイズを超えません. smp_mb(); smp_wmb(); メモリバリアを追加します.ここでは議論の範囲ではありません.無視してもいいです. l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));前回決定した書き込むバイト数lenを「切り分ける」のですが、ここではもう一つのテクニックを使いました.注意:fifo->bufferに実際に割り当てられたバイト数fifo->sizeは、2のべき乗でなければなりません.そうしないと、ここでエラーが発生します.fifo->sizeが2のべき乗である以上、(fifo->size-1)つまり1つ後ろの数がすべて1の数であることは、(fifo->in&(fifo->size-1))が常に(fifo->size-1)を超えない部分であり、(fifo->in)%(fifo->size-1)の効果と同じであることを保証することができる.これにより、後続のコードは理解しにくくなり、fifo->inからバッファ末端までのブロックにデータを書き込み、まだ書き終わっていない場合はバッファヘッダから残りを書き込み、ループバッファを実現します.最後に、書き込みポインタをlenバイト後ろに移動し、lenを返します.以上から、fifo->inの値は0からfifo->sizeを超える数値に変化することができ、fifo->outも同様であるが、それらの差はfifo->sizeを超えない.
kfifoからデータを読み出す関数は、static inline unsigned int kfifo_です.get(struct kfifo *fifo, unsigned char *buffer, unsigned int len); unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len);
1: 2: /** 3: * __kfifo_get - gets some data from the FIFO, no locking version 4: * @fifo: the fifo to be used. 5: * @buffer: where the data must be copied. 6: * @len: the size of the destination buffer. 7: * 8: * This function copies at most @len bytes from the FIFO into the 9: * @buffer and returns the number of copied bytes. 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_get(struct kfifo *fifo, 15: unsigned char *buffer, unsigned int len) 16: { 17: unsigned int l; 18: 19: len = min(len, fifo->in - fifo->out); 20: 21: /* 22: * Ensure that we sample the fifo->in index -before- we 23: * start removing bytes from the kfifo. 24: */ 25: 26: smp_rmb(); 27: 28: /* first get the data from fifo->out until the end of the buffer */ 29: l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); 30: memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); 31: 32: /* then get the rest (if any) from the beginning of the buffer */ 33: memcpy(buffer + l, fifo->buffer, len - l); 34: 35: /* 36: * Ensure that we remove the bytes from the kfifo -before- 37: * we update the fifo->out index. 38: */ 39: 40: smp_mb(); 41: 42: fifo->out += len; 43: 44: return len; 45: } 46: EXPORT_SYMBOL(__kfifo_get); 1: 2: /** 3: * kfifo_get - gets some data from the FIFO 4: * @fifo: the fifo to be used. 5: * @buffer: where the data must be copied. 6: * @len: the size of the destination buffer. 7: * 8: * This function copies at most @len bytes from the FIFO into the 9: * @buffer and returns the number of copied bytes. 10: */ 11: static inline unsigned int kfifo_get(struct kfifo *fifo, 12: unsigned char *buffer, unsigned int len) 13: { 14: unsigned long flags; 15: unsigned int ret; 16: 17: spin_lock_irqsave(fifo->lock, flags); 18: 19: ret = __kfifo_get(fifo, buffer, len); 20: 21: /* 22: * optimization: if the FIFO is empty, set the indices to 0 23: * so we don't wrap the next time 24: */ 25: if (fifo->in == fifo->out) 26: fifo->in = fifo->out = 0; 27: 28: spin_unlock_irqrestore(fifo->lock, flags); 29: 30: return ret; 31: }上の__とkfifo_putは似ていて、分析は難しくありません.
static inline unsigned int __kfifo_len(struct kfifo *fifo); static inline unsigned int kfifo_len(struct kfifo *fifo);
1: 2: /** 3: * __kfifo_len - returns the number of bytes available in the FIFO, no locking version 4: * @fifo: the fifo to be used. 5: */ 6: static inline unsigned int __kfifo_len(struct kfifo *fifo) 7: { 8: return fifo->in - fifo->out; 9: } 10: 11: /** 12: * kfifo_len - returns the number of bytes available in the FIFO 13: * @fifo: the fifo to be used. 14: */ 15: static inline unsigned int kfifo_len(struct kfifo *fifo) 16: { 17: unsigned long flags; 18: unsigned int ret; 19: 20: spin_lock_irqsave(fifo->lock, flags); 21: 22: ret = __kfifo_len(fifo); 23: 24: spin_unlock_irqrestore(fifo->lock, flags); 25: 26: return ret; 27: }この2つの関数は、fifo->inからfifo->outを減算するだけでバッファ内の実際のバイト数を返します.
kernel/kfifo.cには、kfifoを初期化し、kfifoを割り当て、解放するインタフェースも用意されています.
struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock); struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock);
void kfifo_free(struct kfifo *fifo);
もう一度強調してkfifo_を呼び出しますinitはsizeが2のべき乗であることを保証しなければならないが、kfifo_allocは必要ありません.内部ではsizeを2のべき乗に上げます.kfifo_allocとkfifo_freeは、fifo->bufferにメモリ領域を割り当て/解放するため、2つの関数を組み合わせて使用します.kfifo_Initは割り当てられたスペースのfifo->bufferしか受け入れられず、kfifo->freeと組み合わせることができず、kfifo_Initが割り当てたkfifoはkfreeでしか解放できません.
ループバッファは、特にネットワークアダプタでドライバに多く使用されます.しかし、このロックフリー方式はカーネル反発において使用されることが少なく、代わりに別の高度な反発機構であるRCUが使用される.