Linuxカーネル同期(四):シーケンスロック(seqlock)

シーヶンスロック
第3章で述べた読み書きスピンロックは,読者に偏っている.カーネルは、書き込み者に偏ったロックを提供します.
このロックは簡単な読み書き共有のメカニズムを提供し、彼の設計は書く者に偏っており、どんな状況(複数の書く者が競争していない場合)、書く者には直接書く権利(覇道)があり、読者は?ここでは、書き込み者が入ると、このシーケンス値に1が加算され、読者が読み出し値の前後にそれぞれこの値をチェックすると、読み取り中(奇数は偶数)、書き込み者がデータを「改ざん」したかどうかを知るシーケンス値が提供され、もしあれば、再びspinの読み取りが行われ、データが完全に改ざんされるまで行われる.
シーケンスロック臨界領域は1つのwriter threadのみが入ることを許可し(複数のライター間で反発している)、臨界領域は1つのwriter threadのみが入ることを許可し、writer threadがない場合、reader threadは勝手に入ることができ、つまりreaderはreaderをブロックしない.臨界領域にreader threadしかない場合、writer threadはすぐに実行でき、待つことはありません
 
Writer threadの操作:
writer threadの場合、seqlockを取得する操作は次のとおりです.
(1)臨界領域にwriterが1つしか入らないことを保証するspin lockなどのロックを取得する.
(2)sequence counterプラス1
seqlockを解放するには、次の手順に従います.
(1)ロックを解除し、他のwriter threadが臨界領域に入ることを許可する.
(2)sequence counterプラス1(注意:マイナス1ではありませんよ、sequence counterは累積的なcounterです)
以上の操作から分かるように、臨界領域にwriter threadがない場合、sequence counterは偶数(sequence counterは0に初期化)であり、臨界領域にwriter threadが1つある場合(もちろん、1つしかない)、sequence counterは奇数である.
 
Reader threadの操作は次のとおりです.
(1)sequence counterの値を取得し、偶数であれば臨界領域に入ることができ、奇数であればwriterが臨界領域から離れるのを待つ(sequence counterが偶数になる).臨界領域に入るときのsequence counterの値をold sequence counterと呼ぶ.
(2)臨界領域に入り、データを読み取る
(3)sequence counterの値を取得し、old sequence counterに等しい場合はすべてOKであることを説明し、そうでなければstep(1)に戻る
 
適用シーン:
一般的にseqlockは次のように適用されます.
(1)read操作が比較的頻繁である
(2)write操作は少ないが、性能要求が高く、reader threadにブロックされたくない(write操作が少ないのは主にread sideの性能を考慮する)
(3)データ型は比較的簡単であるが,データへのアクセスは原子操作では保護できない.簡単な例を挙げて説明します.保護する必要があるデータがチェーンテーブルであると仮定すると、header--->A node->>B node->>C node->>nullです.reader threadがチェーンテーブルを遍歴する過程で、B nodeのポインタを一時変数xに付与すると、割り込みが発生し、reader threadがpreemptされる(seqlockの場合、readerはプリエンプトを禁止していないことに注意).これにより、他のcpu上で実行されるwriter threadは、B nodeのmemoryを解放するのに十分な時間がある(reader threadの一時変数xは、このメモリを指すことに注意).read threadが実行を再開し、xというポインタでメモリアクセスを行うと(例えばnextでC nodeを見つけようとする)、悲劇が起こります......
 
シーケンシャルロックの使用
定義＃テイギ＃
順序ロックを定義するには、次の2つの方法があります.

seqlock_t seqlock
seqlock_init(&seqlock)

DEFINE_SEQLOCK(seqlock)

 
書き込み臨界領域:

write_seqlock(&seqlock);
/* --------      ---------*/
write_sequnlock(&seqlock);

 
リード臨界領域:

unsigned long seq;

do { 
     seq = read_seqbegin(&seqlock); 
/* ----------          ----------*/
} while (read_seqretry(&seqlock, seq)); 

 
例:kernelでjiffies_64システムが起動してからtickの数が保存されており、そのデータへのアクセス(および他のjiffies関連データ)にはjiffies_が必要である.lockこのseq lock:
現在のtickを読みます.

u64 get_jiffies_64(void) 
{

    do { 
        seq = read_seqbegin(&jiffies_lock); 
        ret = jiffies_64; 
    } while (read_seqretry(&jiffies_lock, seq)); 
}

カーネル更新現在のtick:

static void tick_do_update_jiffies64(ktime_t now) 
{ 
    write_seqlock(&jiffies_lock);

    /*       jiffies_64      */
    write_sequnlock(&jiffies_lock); 
}

シーケンスロックの実装
1. seqlock_t構造:

typedef struct {
	struct seqcount seqcount;
	spinlock_t lock;
} seqlock_t;

2. write_seqlock/write_sequnlock

static inline void write_seqlock(seqlock_t *sl) 
{ 
    spin_lock(&sl->lock);
    sl->sequence++; 
    smp_wmb(); 
}

static inline void write_sequnlock(seqlock_t *sl)
{
    smp_wmb();
    s->sequence++;
    spin_unlock(&sl->lock);
}

seqlockも実はspinlockに基づいていることがわかります.smp_wmbは書き込みメモリバリアであり,seq lockはsequence counterに基づいているため,この動作を保証しなければならない.
 
3. read_seqbegin:

static inline unsigned read_seqbegin(const seqlock_t *sl) 
{  
    unsigned ret;

repeat: 
    ret = ACCESS_ONCE(sl->sequence); －－－       ，    sequenc counter    
    if (unlikely(ret & 1)) {        －－－－－     ，   writer thread 
        cpu_relax(); 
        goto repeat;  －－－－   writer，          ，   polling sequenc counter 
    }

    smp_rmb();  －－－  sequenc counter            
    return ret; 
}

writer threadがあればread_seqbegin関数には偶数になるまでpolling sequenc counterが絶えず存在し、この過程で制御しなければシステム全体の性能が損なわれる(ここでの性能は消費電力と速度を指す).したがって、polling中にcpu_がrelaxの呼び出しは、ARM 64のコード:

static inline void cpu_relax(void) 
{ 
    asm volatile("yield" ::: "memory"); 
}

yield命令はハードウェアシステムに通知するために使用され、本cpuで実行される命令はpolling操作であり、それほど急迫していない.リソースの衝突があれば、本cpuは制御権を譲ることができる.
 
4. read_seqretry

static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start) 
{ 
    smp_rmb();－－－  sequenc counter            
    return unlikely(sl->sequence != start); 
}

startパラメータは、現在臨界領域を脱退しているsequenc counterよりも、臨界領域に入るときのsequenc counterのスナップショットであり、等しい場合はwriterが邪魔reader threadに入っていないことを示すと、快適に臨界領域を離れることができる.
もう一つ面白い論理問題があります.read_seqbeginはなぜパリティ判断を行うのですか?すべてをreadに押し付けるseqretryで判断してはいけませんか?つまり、なぜread_seqbeginはwriter threadがない場合に臨界領域に入るのですか?実はwriter threadも入ってもいいし、どうせread_seqretryでは,パリティおよび等しい判断を行い,論理の正確性を保証することができる.もちろん、そう思うのも正しいですが、performanceに欠けています.readerはwriter threadが臨界領域にあることを検出した後も、reader threadを入れて入ると、writer threadの追加のオーバーヘッド(cache miss)を招く可能性があります.そのため、最善の方法はread_seqbeginでブロックします.
 
参考文献:http://www.wowotech.net/kernel_synchronization/seqlock.html