linuxソースコードのスピンロック/読み書きスピンロック分析
33754 ワード
本文kernelコード分析は以下の1.linux-4.159 2.64 bitコード処理ロジック
私たちは上でsemaphoreを勉強しているときに中断のあるシーンでは使用できないことを知っています.この節ではスピンロックspinlockを見ています.これは主に中断のあるシーンで使われています.その最大の特徴は、ロックが得られないとスピンが忙しくてcpuを譲らないこと、臨界領域の入り口で死ぬことなどです.これは主にSMP(マルチコア)での同期問題に使われています.
まずspinlockの特徴を概説します.
1.spinlockは再帰的ではなく、再入不能であり、ロックを解除する前にインタフェースを呼び出してこのロックを取得すると、cpuデッドロックを引き起こすに違いない.cpuが待機するロックメカニズムである、すなわち、cpuが他のプロセスを呼び出すのではなく、ずっと死ぬなどである.このような特性のため、シーンは主に臨界領域のリソースに対して比較的短いシーンを実行し、そうでなければcpuリソースの深刻な浪費をもたらす.
spinlock不足と改善:
1.古いkernelバージョンのspinlockはリソースアクセスの公平性と秩序性を保証できない.Linux 2.6.25はキュー戦略(FIFO Ticket Spinlock)の概念を導入し、先訪問者が先にロックを取得し、先に来るという原則を採用してリソースアクセスの公平性と秩序性を保証した.これは後でこの戦略を重点的に紹介する.
2.共有メモリなどの共有リソースへのアクセスでは、同時読み取り操作に対するspinlock保護が不要になったり、読み書きにさらに細分化が必要になったりするシーンspinlockには区別がなく、spinlockは読み書きspinlockを導入したりしています.この後で詳しく説明します.
一.spinlock
1.1まずspinlockのデータ構造を見る:
1.2初期化後、使用シーンを見る
spin_lock
またspin_unlock
関連するコアコードを直接見てみましょう
私たちはspinlockの不足と改善の中でspinlockの読み書きに言及したことがあります.
二.読み書きスピンロック読み書きロックの基本原理は、前に見たrw_に似ています.semaphore 1.同時に、複数の読者(reader)がロックを獲得して臨界領域2に入ることを許可する.同じ時点で1人のライター(writer)のみがロックを獲得して臨界領域に入ることを許可する、すなわちライターとライターが反発する.同じ時刻に、読者と同時にロックを取得して臨界領域に入ることは許されない、すなわち、読者と書く者が互いに反発する.このロックメカニズムは読者に配慮しており、使用時に自分のシーンが適切かどうかを評価してください.そうしないと、パフォーマンスの問題が発生します.
2.1. データ構造を見てみましょう
2.2初期化後、使用シーンを見る
注意:read_ロックとread_unlockペア、write_lockとwrite_unlockペア、readとwriteペア、すなわちread_lockとwrite_unlockは不法です.
上の最終的な実装はspinlockと基本的に似ているので,コアのcodeだけを見てみましょう.
arch_read_lock
arch_read_unlock
arch_を見てwrite_lock
arch_write_unlock
以上のような構造体である読み書きスピンロックの実現は、読み書きスピンロックの実現が簡単であり、lock変数はunsigned intの32ビット数であり、bit 31ビットはライターのロック情報を表し、bit 0−bit 30ビットは読者のロック情報を表す.
以上のコード実装により、1 bitで書き込み者のロック状態を表すことができ、書き込み者がロックを取得した場合bit 31が1を書き(この場合読者は存在しない)、ロックを解放するとlockが直接ゼロになる.読者がロックを取得することに成功した場合、ライターは必ず取得しません.lock++、読者がロックを解除するときlock-、lockの数は現在何人の読者がロックを持っているかを示します.
なぜ読み書きスピンロックの設計は読み書き信号量の設計よりずっと簡単ですか?待機キューには関係ありませんか?これは実際に彼らがシーンの違い(中断)を使うことと大きく関係しています.
三.スピンロックその他のインタフェース
これらのコア実装は同じで、自分でソースコードをチェックすることができます.
参照先:https://www.ibm.com/developerworks/cn/linux/l-cn-spinlock_mips/index.html
私たちは上でsemaphoreを勉強しているときに中断のあるシーンでは使用できないことを知っています.この節ではスピンロックspinlockを見ています.これは主に中断のあるシーンで使われています.その最大の特徴は、ロックが得られないとスピンが忙しくてcpuを譲らないこと、臨界領域の入り口で死ぬことなどです.これは主にSMP(マルチコア)での同期問題に使われています.
まずspinlockの特徴を概説します.
1.spinlockは再帰的ではなく、再入不能であり、ロックを解除する前にインタフェースを呼び出してこのロックを取得すると、cpuデッドロックを引き起こすに違いない.cpuが待機するロックメカニズムである、すなわち、cpuが他のプロセスを呼び出すのではなく、ずっと死ぬなどである.このような特性のため、シーンは主に臨界領域のリソースに対して比較的短いシーンを実行し、そうでなければcpuリソースの深刻な浪費をもたらす.
spinlock不足と改善:
1.古いkernelバージョンのspinlockはリソースアクセスの公平性と秩序性を保証できない.Linux 2.6.25はキュー戦略(FIFO Ticket Spinlock)の概念を導入し、先訪問者が先にロックを取得し、先に来るという原則を採用してリソースアクセスの公平性と秩序性を保証した.これは後でこの戦略を重点的に紹介する.
2.共有メモリなどの共有リソースへのアクセスでは、同時読み取り操作に対するspinlock保護が不要になったり、読み書きにさらに細分化が必要になったりするシーンspinlockには区別がなく、spinlockは読み書きspinlockを導入したりしています.この後で詳しく説明します.
一.spinlock
1.1まずspinlockのデータ構造を見る:
// debug code
typedef struct spinlock {
//@1
union {
struct raw_spinlock rlock;
};
} spinlock_t;
typedef struct raw_spinlock {
arch_spinlock_t raw_lock;
} raw_spinlock_t;
typedef struct {
//@2
#ifdef __AARCH64EB__ //@3
u16 next;
u16 owner;
#else
u16 owner;
u16 next;
#endif
} __aligned(4) arch_spinlock_t;
@1. spinlock raw_spinlock, arch_spinlock_t,
@2. spinlock ,
a. arch_spinlock_t next owner,
next ,owner
b. 0, next=owner ;
c. next++, owner++
:
a. ,next=owner=0, , (next++)=1
b. , , owner++, next=owner=1, ;
, ,goto step c
c. next=1,owner=0; (next++)=2 ( lock next, next++ lock , )
d. next=2,owner=0; (next++)=3
e. next=3,owner=0; (next++)=4
f. (owner++)=1; next=1,
owner=next=1( next next next++ ), ,
g. , ,
@3
1.2初期化後、使用シーンを見る
spin_lock(lock);
... ...
spin_unlock(lock);
spin_lock
spin_lock->raw_spin_lock->_raw_spin_lock->__raw_spin_lock
static inline void __raw_spin_lock(raw_spinlock_t *lock)//@1
{
preempt_disable();
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}
static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{
__acquire(lock); //@2
arch_spin_lock(&lock->raw_lock);//@3
}
@1. ,spin_acquire debug, , do_raw_spin_lock
@2. ,
@3. arch_spin_lock , arm64
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
unsigned int tmp;
arch_spinlock_t lockval, newval;
asm volatile( //@4
/* Atomically increment the next ticket. */
ARM64_LSE_ATOMIC_INSN(
/* LL/SC */
" prfm pstl1strm, %3
" //@5
"1: ldaxr %w0, %3
" //@6
" add %w1, %w0, %w5
" //@7
" stxr %w2, %w1, %3
" //@8
" cbnz %w2, 1b
", //@9
/* LSE atomics */
" mov %w2, %w5
"
" ldadda %w2, %w0, %3
"
__nops(3)
)
/* Did we get the lock? */
" eor %w1, %w0, %w0, ror #16
" //@11
" cbz %w1, 3f
" //@12
/*
* No: spin on the owner. Send a local event to avoid missing an
* unlock before the exclusive load.
*/
" sevl
" //@13
"2: wfe
" //@14
" ldaxrh %w2, %4
" //@15
" eor %w1, %w2, %w0, lsr #16
" //@16
" cbnz %w1, 2b
" //@17
/* We got the lock. Critical section starts here. */
"3:"
: "=&r" (lockval), "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
: "Q" (lock->owner), "I" (1 << TICKET_SHIFT)
: "memory");
}
@4. ,
@5. lock cache ,
@6. ldaxr( ) lock lockval,lockval=lock
@7. %w5 1 << TICKET_SHIFT,TICKET_SHIFT 16, lockval+(1<<16) newval
newval next next++ , lockval
@8. stxr( ) newval lock, tmp
@9. tmp 0, , 1
@5-@9 next, next++
@10. next ,
@11. lockval 16 , lockval , newval
next owner
@12. newval 0, next==owner, 3,
@13. sevl(Send Event Local) event , WFE
@14. cpu ,
@15. ,ldaxrh( ldaxr,h halfword) lock->owner tmp
@16. lockval 16 , next, tmp , newval,
next owner
@17. newval 0, 2 ;
またspin_unlock
関連するコアコードを直接見てみましょう
static inline void arch_spin_unlock(arch_spinlock_t *lock) //@1
{
unsigned long tmp;
asm volatile(ARM64_LSE_ATOMIC_INSN(
/* LL/SC */
" ldrh %w1, %0
"
" add %w1, %w1, #1
"
" stlrh %w1, %0",
/* LSE atomics */
" mov %w1, #1
"
" staddlh %w1, %0
"
__nops(1))
: "=Q" (lock->owner), "=&r" (tmp)
:
: "memory");
}
@1. , owner, owner++ ,
私たちはspinlockの不足と改善の中でspinlockの読み書きに言及したことがあります.
二.読み書きスピンロック読み書きロックの基本原理は、前に見たrw_に似ています.semaphore 1.同時に、複数の読者(reader)がロックを獲得して臨界領域2に入ることを許可する.同じ時点で1人のライター(writer)のみがロックを獲得して臨界領域に入ることを許可する、すなわちライターとライターが反発する.同じ時刻に、読者と同時にロックを取得して臨界領域に入ることは許されない、すなわち、読者と書く者が互いに反発する.このロックメカニズムは読者に配慮しており、使用時に自分のシーンが適切かどうかを評価してください.そうしないと、パフォーマンスの問題が発生します.
2.1. データ構造を見てみましょう
// debug code
typedef struct {
arch_rwlock_t raw_lock;
} rwlock_t;
typedef struct {
volatile unsigned int lock; //@1
} arch_rwlock_t;
@1 spinlock ;
next owner; lock
2.2初期化後、使用シーンを見る
//
read_lock(rwlock);
... ...
read_unlock(rwlock)
//
write_lock(rwlock);
... ...
write_unlock(rwlock)
注意:read_ロックとread_unlockペア、write_lockとwrite_unlockペア、readとwriteペア、すなわちread_lockとwrite_unlockは不法です.
上の最終的な実装はspinlockと基本的に似ているので,コアのcodeだけを見てみましょう.
arch_read_lock
static inline void arch_read_lock(arch_rwlock_t *rw)
{
unsigned int tmp, tmp2;
asm volatile(
" sevl
"
ARM64_LSE_ATOMIC_INSN(
/* LL/SC */
"1: wfe
"
"2: ldaxr %w0, %2
" //@1
" add %w0, %w0, #1
" //@2
" tbnz %w0, #31, 1b
" //@3
" stxr %w1, %w0, %2
" //@4
" cbnz %w1, 2b
" //@5
__nops(1),
: "=&r" (tmp), "=&r" (tmp2), "+Q" (rw->lock)
:
: "cc", "memory");
}
@1. rw->lock tmp
@2. tmp++
@3. tmp[31] 0, 0 write , 1
@4. tmp rw->lock, tmp2
@5. tmp2 0, , 2
arch_read_unlock
static inline void arch_read_unlock(arch_rwlock_t *rw)
{
unsigned int tmp, tmp2;
asm volatile(ARM64_LSE_ATOMIC_INSN(
/* LL/SC */
"1: ldxr %w0, %2
" //@1
" sub %w0, %w0, #1
" //@2
" stlxr %w1, %w0, %2
" //@3
" cbnz %w1, 1b", //@4
/* LSE atomics */
" movn %w0, #0
"
" staddl %w0, %2
"
__nops(2))
: "=&r" (tmp), "=&r" (tmp2), "+Q" (rw->lock)
:
: "memory");
}
@1. rw->lock tmp
@2. tmp--
@3. tmp rw->lock, tmp2
@4. tmp2 0, 1
arch_を見てwrite_lock
static inline void arch_write_lock(arch_rwlock_t *rw)
{
unsigned int tmp;
asm volatile(ARM64_LSE_ATOMIC_INSN(
/* LL/SC */
" sevl
"
"1: wfe
"
"2: ldaxr %w0, %1
" //@1
" cbnz %w0, 1b
" //@2
" stxr %w0, %w2, %1
" //@3
" cbnz %w0, 2b
" //@4
__nops(1),
"3:")
: "=&r" (tmp), "+Q" (rw->lock)
: "r" (0x80000000)
: "memory");
}
@1. rw->lock tmp
@2. tmp 0, / , 1
@3. 0x80000000 rw->lock, lock bit31 1, tmp
@4. , 2
arch_write_unlock
static inline void arch_write_unlock(arch_rwlock_t *rw)
{
asm volatile(ARM64_LSE_ATOMIC_INSN(
" stlr wzr, %0", //@1
" swpl wzr, wzr, %0") //@2
: "=Q" (rw->lock) :: "memory");
}
@1. lock
@2. 0 , lock
以上のような構造体である読み書きスピンロックの実現は、読み書きスピンロックの実現が簡単であり、lock変数はunsigned intの32ビット数であり、bit 31ビットはライターのロック情報を表し、bit 0−bit 30ビットは読者のロック情報を表す.
以上のコード実装により、1 bitで書き込み者のロック状態を表すことができ、書き込み者がロックを取得した場合bit 31が1を書き(この場合読者は存在しない)、ロックを解放するとlockが直接ゼロになる.読者がロックを取得することに成功した場合、ライターは必ず取得しません.lock++、読者がロックを解除するときlock-、lockの数は現在何人の読者がロックを持っているかを示します.
なぜ読み書きスピンロックの設計は読み書き信号量の設計よりずっと簡単ですか?待機キューには関係ありませんか?これは実際に彼らがシーンの違い(中断)を使うことと大きく関係しています.
三.スピンロックその他のインタフェース
spin_lock_irq // ,
spin_lock_irqsave // , CPU irq
spin_lock_bh // (bottom half)
これらのコア実装は同じで、自分でソースコードをチェックすることができます.
参照先:https://www.ibm.com/developerworks/cn/linux/l-cn-spinlock_mips/index.html