Sequence counter와 seqlock

Sequence counter의 consistency protocol

Sequence counter는 lockless reader가 read-only retry loop를 돌고 writer starvation이 없는 reader-writer consistency mechanism이다. System time처럼 write가 드문 data에서 reader가 일관된 snapshot을 원하고 update와 겹치면 다시 읽을 수 있을 때 사용한다.

Reader는 critical section 시작에서 sequence count가 even인지 확인하고 data 전체를 section 안에서 복사한 뒤 끝에서 같은 count를 다시 읽는다. Count가 바뀌었으면 snapshot이 update와 겹친 것이므로 재시도한다.

Writer는 critical section 시작과 끝에서 sequence count를 증가시킨다. Update 중에는 odd라 reader가 진행하지 않고, 끝나면 다시 even이 되어 reader가 consistent snapshot을 얻을 수 있다.

Writer non-preemptibility와 pointer 금지

Sequence counter write-side critical section은 read-side section에 의해 preempt되거나 interrupt되어서는 안 된다. Odd count를 남긴 writer가 중단되면 reader는 scheduler tick 전체를 spin한다. Real-time reader가 writer보다 높은 priority라면 writer가 다시 실행되지 못해 kernel livelock이 될 수 있다.

보호 data가 pointer를 포함하면 writer가 reader가 따라가는 pointer를 invalidate할 수 있으므로 이 mechanism을 사용할 수 없다.

Raw seqcount_t와 외부 writer lock

seqcount_t는 raw counting mechanism이며 여러 writer를 직렬화하지 않는다. Write-side critical section은 반드시 외부 lock으로 serialize해야 한다.

그 lock이 preemption을 암묵적으로 disable하지 않으면 write section 전에 명시적으로 disable한다. Reader가 hardirq 또는 softirq에서 실행될 수 있다면 writer는 각각 interrupt 또는 bottom half도 disable해야 한다. Writer serialization과 non-preemptibility를 자동으로 다루려면 seqlock_t를 사용한다.

seqcount_t 초기화와 read/write path

/* dynamic */
seqcount_t foo_seqcount;
seqcount_init(&foo_seqcount);

/* static */
static seqcount_t foo_seqcount = SEQCNT_ZERO(foo_seqcount);

/* C99 struct init */
struct {
    .seq = SEQCNT_ZERO(foo.seq),
} foo;

/* writer: serialized, preemption disabled */
write_seqcount_begin(&foo_seqcount);
/* update snapshot fields */
write_seqcount_end(&foo_seqcount);

/* reader */
do {
    seq = read_seqcount_begin(&foo_seqcount);
    /* copy all protected fields */
} while (read_seqcount_retry(&foo_seqcount, seq));

seqcount_LOCKNAME_t와 lockdep 연계

seqcount_LOCKNAME_t는 writer serialization에 쓰는 lock을 초기화 시 sequence counter와 연결한다. Lockdep은 write-side critical section이 올바른 lock으로 보호되는지 검증할 수 있다.

Lockdep이 꺼져 있으면 association은 storage와 runtime overhead가 없는 NOOP다. 켜져 있으면 struct seqcount에 lock pointer를 저장하고 write section 시작에 lock-held assertion을 삽입한다. Lock type이 preemption을 암묵적으로 막지 않으면 write function이 이를 보장한다.

• seqcount_spinlock_t
• seqcount_raw_spinlock_t
• seqcount_rwlock_t
• seqcount_mutex_t
• seqcount_ww_mutex_t

Sequence counter read/write API는 plain seqcount_t와 모든 seqcount_LOCKNAME_t variant를 같은 방식으로 받는다.

Associated-lock sequence counter 초기화

/* dynamic */
seqcount_LOCKNAME_t foo_seqcount;
seqcount_LOCKNAME_init(&foo_seqcount, &lock);

/* static */
static seqcount_LOCKNAME_t foo_seqcount =
    SEQCNT_LOCKNAME_ZERO(foo_seqcount, &lock);

/* C99 struct init */
struct {
    .seq = SEQCNT_LOCKNAME_ZERO(foo.seq, &lock),
} foo;

LOCKNAME은 지원하는 lock 이름으로 바꾼다. Write path는 associated serialization lock을 획득한 context에서 plain seqcount_t와 같은 API를 쓰고 read path도 동일하다.

seqcount_latch_t와 NMI reader

seqcount_latch_t는 embedded seqcount_t의 even/odd 값을 이용해 보호 data 사본 두 개 사이를 전환하는 multiversion concurrency-control mechanism이다. Reader가 자기 write-side critical section을 interrupt해도 안전하게 읽을 수 있다.

NMI handler에서 read side가 호출되는 경우처럼 reader interruption으로부터 writer를 보호할 수 없을 때 사용한다. 자세한 protocol은 write_seqcount_latch() 문서를 확인한다.

seqlock_t의 embedded spinlock

seqlock_t는 seqcount_t mechanism에 writer serialization과 non-preemptibility를 위한 spinlock을 embedded한다. Reader가 hardirq나 softirq에서 실행될 수 있다면 writer는 각각 interrupt 또는 bottom half를 disable하는 variant를 사용한다.

/* dynamic */
seqlock_t foo_seqlock;
seqlock_init(&foo_seqlock);

/* static */
static DEFINE_SEQLOCK(foo_seqlock);

/* C99 struct init */
struct {
    .seql = __SEQLOCK_UNLOCKED(foo.seql)
} foo;

seqlock_t write path

write_seqlock(&foo_seqlock);
/* write-side critical section */
write_sequnlock(&foo_seqlock);

Reader 1: lockless retry loop

일반 sequence reader는 writer를 block하지 않는다. Writer가 진행 중이거나 sequence가 바뀌면 재시도하며 writer는 reader를 기다리지 않는다.

do {
    seq = read_seqbegin(&foo_seqlock);
    /* read-side critical section */
} while (read_seqretry(&foo_seqlock, seq));

Reader 2: exclusive locking reader

Locking reader는 writer 또는 다른 locking reader가 진행 중이면 기다리고, 자신이 진행 중일 때 writer 진입도 막는다. rwlock_t와 달리 reader 사이에도 exclusive라 한 번에 하나만 획득한다.

read_seqlock_excl(&foo_seqlock);
/* read-side critical section */
read_sequnlock_excl(&foo_seqlock);

Reader 3: retry 폭증 시 locking으로 전환

Write activity가 급증해 lockless reader가 계속 retry하며 starvation되는 것을 막는 hybrid 방식이다. Even marker로 lockless read를 먼저 시도한다. 실패해 odd sequence가 다음 marker가 되면 다음 iteration은 full locking read로 전환되어 retry가 필요 없다.

int seq = 0; /* even marker */
do {
    read_seqbegin_or_lock(&foo_seqlock, &seq);
    /* read-side critical section */
} while (need_seqretry(&foo_seqlock, seq));
done_seqretry(&foo_seqlock, seq);

API 원본 위치

Sequence counter와 sequential lock 전체 kernel-doc은 include/linux/seqlock.h에서 생성된다.