<kernel v5.4>
RCU 콜백 리스트
RCU Segmented 콜백 리스트
커널 v4.12에서 콜백 리스트의 관리 방법이 바뀌어 콜백 리스트를 4 등분하여 관리하는 segmented 콜백 리스트로 이름이 바뀌었다.
다음 4개의 세그먼트들을 알아본다.
include/linux/rcu_segcblist.h
/* Complicated segmented callback lists. 😉 */ /* * Index values for segments in rcu_segcblist structure. * * The segments are as follows: * * [head, *tails[RCU_DONE_TAIL]): * Callbacks whose grace period has elapsed, and thus can be invoked. * [*tails[RCU_DONE_TAIL], *tails[RCU_WAIT_TAIL]): * Callbacks waiting for the current GP from the current CPU's viewpoint. * [*tails[RCU_WAIT_TAIL], *tails[RCU_NEXT_READY_TAIL]): * Callbacks that arrived before the next GP started, again from * the current CPU's viewpoint. These can be handled by the next GP. * [*tails[RCU_NEXT_READY_TAIL], *tails[RCU_NEXT_TAIL]): * Callbacks that might have arrived after the next GP started. * There is some uncertainty as to when a given GP starts and * ends, but a CPU knows the exact times if it is the one starting * or ending the GP. Other CPUs know that the previous GP ends * before the next one starts. * * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also * empty. * * The ->gp_seq[] array contains the grace-period number at which the * corresponding segment of callbacks will be ready to invoke. A given * element of this array is meaningful only when the corresponding segment * is non-empty, and it is never valid for RCU_DONE_TAIL (whose callbacks * are already ready to invoke) or for RCU_NEXT_TAIL (whose callbacks have * not yet been assigned a grace-period number). */
#define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */ #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */ #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */ #define RCU_NEXT_TAIL 3 #define RCU_CBLIST_NSEGS 4
콜백 리스트는 done 구간, wait 구간, next-ready 구간, next 구간과 같이 총 4개의 구간으로 나누어 관리한다.
먼저 tails[0] 과 *tails[0]의 의미를 구분해야 한다.
- tails[0]
- tails[0]이 가리키는 곳
- *tails[0]
- tails[0]의 값으로 이 값은 다음 콜백을 가리킨다.
수의 범위 괄호 표기법
다음과 같이 수의 범위 괄호 표기법을 기억해둔다.
- [1, 5]
- 실수: 1 <= x <= 5
- 정수: 1, 2, 3, 4, 5
- (1, 5)
- 실수: 1 < x < 5
- 정수: 2, 3, 4
- [1, 5)
- 실수: 1 <= x < 5
- 정수: 1, 2, 3, 4
[head, *tails[0])
- head 위치부터 tails[0]의 값이 가리키는 다음 콜백의 전까지
- 예) CB1, CB2, CB3가 범위에 포함된다.
- head tails[0] *tails[0]
- CB1 —–> CB2 —–> CB3 —–> CB4
rcu의 segmented 콜백 리스트는 다음과 같이 4개의 구간으로 나뉘어 관리한다.
4개의 구간 관리를 위해 cb 리스트는 1개의 head와 4개의 포인터 tails[0~3]를 사용한다.
- 1개의 콜백 리스트 = rdp->cblist = rsclp
- 1개의 시작 : rsclp->head
- 4개의 구간에 대한 포인터 배열: rsclp->tails[]
- 1 번째 done 구간:
- [head, *tails[0])
- head에 연결된 콜백 위치부터 tails[RCU_DONE_TAIL] 까지
- g.p가 완료하여 처리 가능한 구간이다. blimit 제한으로 인해 다 처리되지 못한 콜백들이 이 구간에 남아 있을 수 있다.
- 이 구간의 콜백들은 아무때나 처리 가능하다.
- 2 번째 wait 구간
- [*tails[0], *tails[1])
- tails[RCU_DONE_TAIL]에 연결된 다음 콜백 위치부터 tails[RCU_WAIT_TAIL] 까지
- current gp 이전에 추가된 콜백으로 current gp가 끝난 후에 처리될 예정인 콜백들이 대기중인 구간이다.
- 3 번째 next-ready 구간 (=wait 2 구간)
- [*tails[1], *tails[2])
- tails[RCU_WAIT_TAIL]에 연결된 다음 콜백 위치부터 tails[RCU_NEXT_READY_TAIL] 까지
- current gp 진행 중에 추가된 콜백들이 추가된 구간이다. 이 콜백들은 current gp가 완료되어도 곧바로 처리되면 안되고, 다음 gp가 완료된 후에 처리될 예정인 콜백들이 있는 구간이다.
- 이 구간의 콜백들은 current gp 및 next gp 까지 완료된 후에 처리되어야 한다.
- 전통적인(classic) rcu에서는 이 구간이 없이 1개의 wait 구간만으로 처리가 되었지만 preemptible rcu 처리를 위해 1 번의 gp를 더 연장하기 위해 구간을 추가하였다. preemptible rcu 에서 rcu_read_lock()에서 메모리 배리어를 사용하지 않게 하기 위해 gp를 1단계 더 delay하여 처리한다.
- 4 번째 next 구간
- [*tails[2], tails[3])
- tails[RCU_NEXT_READY_TAIL]에 연결된 다음 콜백 위치부터 tails[RCU_NEXT_TAIL] 까지
- 새 콜백이 추가되면 이 구간의 마지막에 추가되고, tails[RCU_NEXT_TAIL]이 추가된 마지막 콜백을 항상 가리키게 해야한다.
- 1 번째 done 구간:
- 일반적인 콜백 진행은 위와 같지만 cpu가 16개를 초과하면 1 단계가 느려질 수도 있고, 반대로 acceleration 조건에 부합하여 1단계씩 전진될 수도 있다.
un-segmented 콜백 리스트 관련
rcu un-segmented 콜백 리스트는 구간을 나뉘지 않고 그냥 하나로 관리된다.
rcu_cblist_init()
kernel/rcu/rcu_segcblist.c
/* Initialize simple callback list. */ void rcu_cblist_init(struct rcu_cblist *rclp) { rclp->head = NULL; rclp->tail = &rclp->head; rclp->len = 0; rclp->len_lazy = 0; }
rcu 콜백 리스트를 초기화한다. (주의: unsegmented 콜백 리스트이다)
rcu_cblist_enqueue()
kernel/rcu/rcu_segcblist.c
/* * Enqueue an rcu_head structure onto the specified callback list. * This function assumes that the callback is non-lazy because it * is intended for use by no-CBs CPUs, which do not distinguish * between lazy and non-lazy RCU callbacks. */
void rcu_cblist_enqueue(struct rcu_cblist *rclp, struct rcu_head *rhp) { *rclp->tail = rhp; rclp->tail = &rhp->next; WRITE_ONCE(rclp->len, rclp->len + 1); };
rcu 콜백리스트의 뒷부분에 rcu 콜백을 추가한다.
다음 그림은 rcu 콜백 리스트에 rcu 콜백을 엔큐하는 모습을 보여준다.
rcu_cblist_dequeue()
kernel/rcu/rcu_segcblist.c
/* * Dequeue the oldest rcu_head structure from the specified callback * list. This function assumes that the callback is non-lazy, but * the caller can later invoke rcu_cblist_dequeued_lazy() if it * finds otherwise (and if it cares about laziness). This allows * different users to have different ways of determining laziness. */
struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp) { struct rcu_head *rhp; rhp = rclp->head; if (!rhp) return NULL; rclp->len--; rclp->head = rhp->next; if (!rclp->head) rclp->tail = &rclp->head; return rhp; };
rcu 콜백리스트의 앞부분에서 rcu 콜백을 하나 디큐해온다.
다음 그림은 rcu 콜백 리스트로부터 rcu 콜백을 디큐하는 모습을 보여준다.
rcu_cblist_flush_enqueue()
kernel/rcu/rcu_segcblist.c
/* * Flush the second rcu_cblist structure onto the first one, obliterating * any contents of the first. If rhp is non-NULL, enqueue it as the sole * element of the second rcu_cblist structure, but ensuring that the second * rcu_cblist structure, if initially non-empty, always appears non-empty * throughout the process. If rdp is NULL, the second rcu_cblist structure * is instead initialized to empty. */
void rcu_cblist_flush_enqueue(struct rcu_cblist *drclp, struct rcu_cblist *srclp, struct rcu_head *rhp) { drclp->head = srclp->head; if (drclp->head) drclp->tail = srclp->tail; else drclp->tail = &drclp->head; drclp->len = srclp->len; drclp->len_lazy = srclp->len_lazy; if (!rhp) { rcu_cblist_init(srclp); } else { rhp->next = NULL; srclp->head = rhp; srclp->tail = &rhp->next; WRITE_ONCE(srclp->len, 1); srclp->len_lazy = 0; } };
콜백 리스트 @drclp을 모두 콜백 리스트 @srclp로 옮기고, 콜백 리스트 @srclp에 새로운 콜백 헤드 @rhp를 대입한다. (@rhp가 null인 경우에는 콜백 리스트 @srclp를 초기화한다)
다음 그림은 소스측의 rcu 콜백리스트를 목적측에 flush하고, 새로운 콜백을 대입하는 모습을 보여준다.
rcu_cblist_n_cbs()
kernel/rcu/rcu_segcblist.h
/* Return number of callbacks in the specified callback list. */ static inline long rcu_cblist_n_cbs(struct rcu_cblist *rclp) { return READ_ONCE(rclp->len); }
콜백 리스트에 있는 콜백 수를 반환한다.
rcu_cblist_dequeued_lazy()
kernel/rcu/rcu_segcblist.h
/* * Account for the fact that a previously dequeued callback turned out * to be marked as lazy. */
static inline void rcu_cblist_dequeued_lazy(struct rcu_cblist *rclp) { rclp->len_lazy--; }
콜백 리스트에서 lazy 카운터를 감소시킨다.
segmented 콜백 리스트 관련
rcu_segcblist_init()
kernel/rcu/rcu_segcblist.c
/* * Initialize an rcu_segcblist structure. */
void rcu_segcblist_init(struct rcu_segcblist *rsclp) { int i; BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq)); BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq)); rsclp->head = NULL; for (i = 0; i < RCU_CBLIST_NSEGS; i++) rsclp->tails[i] = &rsclp->head; rcu_segcblist_set_len(rsclp, 0); rsclp->len_lazy = 0; rsclp->enabled = 1; };
rcu segmented 콜백 리스트를 초기화한다.
다음 그림은 segmented 콜백 리스트를 초기화하는 모습을 보여준다.
rcu_segcblist_set_len()
kernel/rcu/rcu_segcblist.c
/* Set the length of an rcu_segcblist structure. */ void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v) { #ifdef CONFIG_RCU_NOCB_CPU atomic_long_set(&rsclp->len, v); #else WRITE_ONCE(rsclp->len, v); #endif }
rcu seg 콜백 리스트에 콜백 수를 기록한다.
rcu_segcblist_add_len()
kernel/rcu/rcu_segcblist.c
/* * Increase the numeric length of an rcu_segcblist structure by the * specified amount, which can be negative. This can cause the ->len * field to disagree with the actual number of callbacks on the structure. * This increase is fully ordered with respect to the callers accesses * both before and after. */
void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v) { #ifdef CONFIG_RCU_NOCB_CPU smp_mb__before_atomic(); /* Up to the caller! */ atomic_long_add(v, &rsclp->len); smp_mb__after_atomic(); /* Up to the caller! */ #else smp_mb(); /* Up to the caller! */ WRITE_ONCE(rsclp->len, rsclp->len + v); smp_mb(); /* Up to the caller! */ #endif };
rcu seg 콜백 리스트에 콜백 수 @v를 추가한다.
rcu_segcblist_inc_len()
kernel/rcu/rcu_segcblist.c
/* * Increase the numeric length of an rcu_segcblist structure by one. * This can cause the ->len field to disagree with the actual number of * callbacks on the structure. This increase is fully ordered with respect * to the callers accesses both before and after. */
void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp) { rcu_segcblist_add_len(rsclp, 1); };
rcu seg 콜백 리스트에 콜백 수를 1 증가시킨다.
rcu_segcblist_xchg_len()
kernel/rcu/rcu_segcblist.c
/* * Exchange the numeric length of the specified rcu_segcblist structure * with the specified value. This can cause the ->len field to disagree * with the actual number of callbacks on the structure. This exchange is * fully ordered with respect to the callers accesses both before and after. */
long rcu_segcblist_xchg_len(struct rcu_segcblist *rsclp, long v) { #ifdef CONFIG_RCU_NOCB_CPU return atomic_long_xchg(&rsclp->len, v); #else long ret = rsclp->len; smp_mb(); /* Up to the caller! */ WRITE_ONCE(rsclp->len, v); smp_mb(); /* Up to the caller! */ return ret; #endif };
rcu seg 콜백 리스트에 콜백 수를 @v 값으로 치환한다. 그리고 반환 값은 기존 값을 반환한다.
rcu_segcblist_disable()
kernel/rcu/rcu_segcblist.c
/* * Disable the specified rcu_segcblist structure, so that callbacks can * no longer be posted to it. This structure must be empty. */
void rcu_segcblist_disable(struct rcu_segcblist *rsclp) { WARN_ON_ONCE(!rcu_segcblist_empty(rsclp)); WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp)); WARN_ON_ONCE(rcu_segcblist_n_lazy_cbs(rsclp)); rsclp->enabled = 0; };
rcu seg 콜백 리스트를 disable 한다.
rcu_segcblist_offload()
kernel/rcu/rcu_segcblist.c
/* * Mark the specified rcu_segcblist structure as offloaded. This * structure must be empty. */
void rcu_segcblist_offload(struct rcu_segcblist *rsclp) { rsclp->offloaded = 1; };
rcu seg 콜백 리스트를 offloaded 상태로 변경한다.
rcu_segcblist_ready_cbs()
kernel/rcu/rcu_segcblist.c
/* * Does the specified rcu_segcblist structure contain callbacks that * are ready to be invoked? */
bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp) { return rcu_segcblist_is_enabled(rsclp) && &rsclp->head != rsclp->tails[RCU_DONE_TAIL]; };
rcu seg 콜백 리스트에 호출 준비된 콜백들이 있는지 여부를 반환한다.
- done 구간에 있는 콜백들이 있는지 여부를 반환한다.
rcu_segcblist_pend_cbs()
kernel/rcu/rcu_segcblist.c
/* * Does the specified rcu_segcblist structure contain callbacks that * are still pending, that is, not yet ready to be invoked? */
bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp) { return rcu_segcblist_is_enabled(rsclp) && !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL); };
rcu seg 콜백 리스트에 콜백들이 있는지 여부를 반환한다.
rcu_segcblist_first_cb()
kernel/rcu/rcu_segcblist.c
/* * Return a pointer to the first callback in the specified rcu_segcblist * structure. This is useful for diagnostics. */
struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp) { if (rcu_segcblist_is_enabled(rsclp)) return rsclp->head; return NULL; };
rcu seg 콜백 리스트의 첫 콜백을 알아온다.
rcu_segcblist_first_pend_cb()
kernel/rcu/rcu_segcblist.c
/* * Return a pointer to the first pending callback in the specified * rcu_segcblist structure. This is useful just after posting a given * callback -- if that callback is the first pending callback, then * you cannot rely on someone else having already started up the required * grace period. */
struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp) { if (rcu_segcblist_is_enabled(rsclp)) return *rsclp->tails[RCU_DONE_TAIL]; return NULL; };
rcu seg 콜백 리스트의 호출 준비된 첫 콜백을 반환한다.
rcu_segcblist_nextgp()
kernel/rcu/rcu_segcblist.c
/* * Return false if there are no CBs awaiting grace periods, otherwise, * return true and store the nearest waited-upon grace period into *lp. */
bool rcu_segcblist_nextgp(struct rcu_segcblist *rsclp, unsigned long *lp) { if (!rcu_segcblist_pend_cbs(rsclp)) return false; *lp = rsclp->gp_seq[RCU_WAIT_TAIL]; return true; };
rcu seg 콜백 리스트에서 콜백들이 있는 경우 여부를 반환한다. 만일 콜백들이 있는 경우 출력 인자 @lp에 gp 대기 중인 gp 시퀀스를 기록한다.
rcu_segcblist_enqueue()
kernel/rcu/rcu_segcblist.c
/* * Enqueue the specified callback onto the specified rcu_segcblist * structure, updating accounting as needed. Note that the ->len * field may be accessed locklessly, hence the WRITE_ONCE(). * The ->len field is used by rcu_barrier() and friends to determine * if it must post a callback on this structure, and it is OK * for rcu_barrier() to sometimes post callbacks needlessly, but * absolutely not OK for it to ever miss posting a callback. */
void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp, struct rcu_head *rhp, bool lazy) { rcu_segcblist_inc_len(rsclp); if (lazy) rsclp->len_lazy++; smp_mb(); /* Ensure counts are updated before callback is enqueued. */ rhp->next = NULL; WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp); WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next); };
rcu seg 콜백 리스트에 rcu 콜백을 엔큐한다.
- 코드 라인 4에서 rcu cb 수를 하나 추가한다.
- 코드 라인 5~6에서 @lazy 요청인 경우 len_lazy 카운터도 증가시킨다.
- 코드 라인 7에서 카운터가 완전히 업데이트 된 후 tails[]에 대한 처리를 수행하게 한다. (읽기 측에서는 tails[]를 먼저 확인한 후 카운터를 보게 한다)
- 코드 라인 9에서 tails[RCU_NEXT_TAIL]이 가리키는 곳의 다음에 cb를 추가한다. 즉 가장 마지막에 cb를 추가한다.
- tails[RCU_NEXT_TAIL]은 항상 마지막에 추가된 cb들을 가리킨다.
rcu_segcblist_entrain()
kernel/rcu/rcu_segcblist.c
/* * Entrain the specified callback onto the specified rcu_segcblist at * the end of the last non-empty segment. If the entire rcu_segcblist * is empty, make no change, but return false. * * This is intended for use by rcu_barrier()-like primitives, -not- * for normal grace-period use. IMPORTANT: The callback you enqueue * will wait for all prior callbacks, NOT necessarily for a grace * period. You have been warned. */
bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp, struct rcu_head *rhp, bool lazy) { int i; if (rcu_segcblist_n_cbs(rsclp) == 0) return false; rcu_segcblist_inc_len(rsclp); if (lazy) rsclp->len_lazy++; smp_mb(); /* Ensure counts are updated before callback is entrained. */ rhp->next = NULL; for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--) if (rsclp->tails[i] != rsclp->tails[i - 1]) break; WRITE_ONCE(*rsclp->tails[i], rhp); for (; i <= RCU_NEXT_TAIL; i++) WRITE_ONCE(rsclp->tails[i], &rhp->next); return true; };
rcu seg 콜백 리스트에 rcu 콜백을 추가한다. done 구간을 제외하고, 마지막 콜백이 있는 구간에 콜백을 추가하고 true를 반환한다. 만일 seg 콜백 리스트의 모든 구간이 비어 있는 경우 false를 반환한다.
- 코드 라인 6~7에서 seg 콜백 리스트가 비어 있는 경우 false를 반환한다.
- 코드 라인 8에서 콜백 수를 1 증가 시킨다.
- 코드 라인 9~10에서 @lazy 요청한 경우 lazy 카운터를 1 증가시킨다.
- 코드 라인 11에서 콜백을 추가하기 전에 반드시 먼저 카운터를 갱신해야 하므로 메모리 베리어를 수행한다.
- 코드 라인 12에서 추가되는 콜백의 다음이 없으므로 null을 대입한다.
- 코드 라인 13~15에서 done을 제외하고 가장 마지막 콜백이 위치한 구간을 찾는다. (i=3, 2, 1 순)
- 코드 라인 16에서 찾은 구간에 콜백을 추가하낟.
- 코드 라인 17~18에서 마지막 구간부터 찾은 구간의 tails[] 포인터가 새로 추가한 콜백을 가리키게 한다.
- 코드 라인 19에서 성공에 해당하는 true를 반환한다.
rcu seg 콜백 리스트의 적절한 위치에 콜백이 추가되는 모습을 보여준다.
rcu_segcblist_empty()
kernel/rcu/rcu_segcblist.h
/* * Is the specified rcu_segcblist structure empty? * * But careful! The fact that the ->head field is NULL does not * necessarily imply that there are no callbacks associated with * this structure. When callbacks are being invoked, they are * removed as a group. If callback invocation must be preempted, * the remaining callbacks will be added back to the list. Either * way, the counts are updated later. * * So it is often the case that rcu_segcblist_n_cbs() should be used * instead. */
static inline bool rcu_segcblist_empty(struct rcu_segcblist *rsclp) { return !READ_ONCE(rsclp->head); }
seg 콜백 리스트가 비어 있는지 여부를 반환한다.
rcu_segcblist_n_cbs()
kernel/rcu/rcu_segcblist.h
/* Return number of callbacks in segmented callback list. */ static inline long rcu_segcblist_n_cbs(struct rcu_segcblist *rsclp) { #ifdef CONFIG_RCU_NOCB_CPU return atomic_long_read(&rsclp->len); #else return READ_ONCE(rsclp->len); #endif }
seg 콜백 리스트의 콜백 수를 반환한다.
rcu_segcblist_n_lazy_cbs()
kernel/rcu/rcu_segcblist.h
/* Return number of lazy callbacks in segmented callback list. */ static inline long rcu_segcblist_n_lazy_cbs(struct rcu_segcblist *rsclp) { return rsclp->len_lazy; }
seg 콜백 리스트의 lazy 콜백 수를 반환한다.
rcu_segcblist_n_nonlazy_cbs()
kernel/rcu/rcu_segcblist.h
/* Return number of lazy callbacks in segmented callback list. */ static inline long rcu_segcblist_n_nonlazy_cbs(struct rcu_segcblist *rsclp) { return rcu_segcblist_n_cbs(rsclp) - rsclp->len_lazy; }
seg 콜백 리스트의 non-lazy 콜백 수를 반환한다.
rcu_segcblist_is_enabled()
kernel/rcu/rcu_segcblist.h
/* * Is the specified rcu_segcblist enabled, for example, not corresponding * to an offline CPU? */
static inline bool rcu_segcblist_is_enabled(struct rcu_segcblist *rsclp) { return rsclp->enabled; }
seg 콜백 리스트의 enabled 여부를 반환한다.
rcu_segcblist_is_offloaded()
kernel/rcu/rcu_segcblist.h
/* Is the specified rcu_segcblist offloaded? */ static inline bool rcu_segcblist_is_offloaded(struct rcu_segcblist *rsclp) { return rsclp->offloaded; }
seg 콜백 리스트의 offloaded 여부를 반환한다.
rcu_segcblist_restempty()
kernel/rcu/rcu_segcblist.h
/* * Are all segments following the specified segment of the specified * rcu_segcblist structure empty of callbacks? (The specified * segment might well contain callbacks.) */
static inline bool rcu_segcblist_restempty(struct rcu_segcblist *rsclp, int seg) { return !READ_ONCE(*READ_ONCE(rsclp->tails[seg])); }
seg 콜백 리스트의 @seg 구간 뒤 대기중인 콜백이 비어 있는지 여부를 반환한다.
RCU 콜백 이동
rcu_segcblist_merge()
kernel/rcu/rcu_segcblist.c
/* * Merge the source rcu_segcblist structure into the destination * rcu_segcblist structure, then initialize the source. Any pending * callbacks from the source get to start over. It is best to * advance and accelerate both the destination and the source * before merging. */
void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp, struct rcu_segcblist *src_rsclp) { struct rcu_cblist donecbs; struct rcu_cblist pendcbs; rcu_cblist_init(&donecbs); rcu_cblist_init(&pendcbs); rcu_segcblist_extract_count(src_rsclp, &donecbs); rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs); rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs); rcu_segcblist_insert_count(dst_rsclp, &donecbs); rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs); rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs); rcu_segcblist_init(src_rsclp); }
done 구간 -> rcu 콜백으로 옮기기
rcu_segcblist_extract_done_cbs()
kernel/rcu/rcu_segcblist.c
/* * Extract only those callbacks ready to be invoked from the specified * rcu_segcblist structure and place them in the specified rcu_cblist * structure. */
void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { int i; if (!rcu_segcblist_ready_cbs(rsclp)) return; /* Nothing to do. */ *rclp->tail = rsclp->head; WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]); WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL); rclp->tail = rsclp->tails[RCU_DONE_TAIL]; for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--) if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL]) WRITE_ONCE(rsclp->tails[i], &rsclp->head); };
rcu seg 콜백리스트의 done 구간의 콜백들을 extract하여 rcu 콜백리스트로 옮긴다.
다음 그림은 rcu seg 콜백리스트의 done 구간의 콜백들을 extract하여 rcu 콜백리스트로 옮기는 모습을 보여준다.
done 구간 제외 -> rcu 콜백으로 옮기기
rcu_segcblist_extract_pend_cbs()
kernel/rcu/rcu_segcblist.c
/* * Extract only those callbacks still pending (not yet ready to be * invoked) from the specified rcu_segcblist structure and place them in * the specified rcu_cblist structure. Note that this loses information * about any callbacks that might have been partway done waiting for * their grace period. Too bad! They will have to start over. */
void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { int i; if (!rcu_segcblist_pend_cbs(rsclp)) return; /* Nothing to do. */ *rclp->tail = *rsclp->tails[RCU_DONE_TAIL]; rclp->tail = rsclp->tails[RCU_NEXT_TAIL]; WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL); for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]); };
rcu seg 콜백리스트의 done 구간을 제외한 나머지 콜백들을 extract하여 rcu 콜백리스트로 옮긴다.
다음 그림은 rcu seg 콜백리스트의 done 구간을 제외한 나머지 콜백들을 extract하여 rcu 콜백리스트로 옮기는 모습을 보여준다.
rcu_segcblist_extract_count()
kernel/rcu/rcu_segcblist.c
/* * Extract only the counts from the specified rcu_segcblist structure, * and place them in the specified rcu_cblist structure. This function * supports both callback orphaning and invocation, hence the separation * of counts and callbacks. (Callbacks ready for invocation must be * orphaned and adopted separately from pending callbacks, but counts * apply to all callbacks. Locking must be used to make sure that * both orphaned-callbacks lists are consistent.) */
void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { rclp->len_lazy += rsclp->len_lazy; rsclp->len_lazy = 0; rclp->len = rcu_segcblist_xchg_len(rsclp, 0); };
rcu seg 콜백 리스트에 rcu 콜백 리스트의 lazy 카운터를 extract하여 누적시킨다. (rcu 콜백 리스트의 콜백 수 및 lazy 카운터는 0으로 클리어된다)
rcu 콜백 -> done 구간으로 옮기기
rcu_segcblist_insert_done_cbs()
kernel/rcu/rcu_segcblist.c
/* * Move callbacks from the specified rcu_cblist to the beginning of the * done-callbacks segment of the specified rcu_segcblist. */
void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { int i; if (!rclp->head) return; /* No callbacks to move. */ *rclp->tail = rsclp->head; WRITE_ONCE(rsclp->head, rclp->head); for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++) if (&rsclp->head == rsclp->tails[i]) WRITE_ONCE(rsclp->tails[i], rclp->tail); else break; rclp->head = NULL; rclp->tail = &rclp->head; };
rcu 콜백 리스트의 콜백들을 rcu seg 콜백리스트의 done 구간으로 옮긴다.
다음 그림은 rcu 콜백 리스트의 콜백들을 rcu seg 콜백리스트의 done 구간으로 옮기는 모습을 보여준다.
rcu 콜백 -> next 구간으로 옮기기
rcu_segcblist_insert_pend_cbs()
kernel/rcu/rcu_segcblist.c
/* * Move callbacks from the specified rcu_cblist to the end of the * new-callbacks segment of the specified rcu_segcblist. */
void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { if (!rclp->head) return; /* Nothing to do. */ WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head); WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail); rclp->head = NULL; rclp->tail = &rclp->head; };
rcu 콜백 리스트의 콜백들을 rcu seg 콜백리스트의 next 구간으로 옮긴다.
다음 그림은 rcu 콜백 리스트의 콜백들을 rcu seg 콜백리스트의 next 구간으로 옮기는 모습을 보여준다.
rcu_segcblist_insert_count()
kernel/rcu/rcu_segcblist.c
/* * Insert counts from the specified rcu_cblist structure in the * specified rcu_segcblist structure. */
void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp, struct rcu_cblist *rclp) { rsclp->len_lazy += rclp->len_lazy; rcu_segcblist_add_len(rsclp, rclp->len); rclp->len_lazy = 0; rclp->len = 0; };
rcu 콜백리스트의 len_lazy 카운터와 콜백 수를 extract하여 rcu seg 콜백리스트에 추가한다.
RCU Cascading 처리
rcu_advance_cbs()
kernel/rcu/tree.c
/* * Move any callbacks whose grace period has completed to the * RCU_DONE_TAIL sublist, then compact the remaining sublists and * assign ->gp_seq numbers to any callbacks in the RCU_NEXT_TAIL * sublist. This function is idempotent, so it does not hurt to * invoke it repeatedly. As long as it is not invoked -too- often... * Returns true if the RCU grace-period kthread needs to be awakened. * * The caller must hold rnp->lock with interrupts disabled. */
static bool rcu_advance_cbs(struct rcu_node *rnp, struct rcu_data *rdp) { rcu_lockdep_assert_cblist_protected(rdp); raw_lockdep_assert_held_rcu_node(rnp); /* If no pending (not yet ready to invoke) callbacks, nothing to do. */ if (!rcu_segcblist_pend_cbs(&rdp->cblist)) return false; /* * Find all callbacks whose ->gp_seq numbers indicate that they * are ready to invoke, and put them into the RCU_DONE_TAIL sublist. */ rcu_segcblist_advance(&rdp->cblist, rnp->gp_seq); /* Classify any remaining callbacks. */ return rcu_accelerate_cbs(rnp, rdp); }
콜백들을 앞쪽으로 옮기는 cascade 처리를 수행한다.
- 코드 라인 7~8에서 pending 콜백들이 없는 경우 false를 반환한다.
- 코드 라인 14에서 콜백들을 앞쪽으로 옮기는 cascade 처리를 수행한다.
- 코드 라인 17에서 남은 콜백들에 대해 accelerate 처리가 가능한 콜백들을 묶어 앞으로 옮긴다.
rcu_segcblist_advance()
kernel/rcu/rcu_segcblist.c
/* * Advance the callbacks in the specified rcu_segcblist structure based * on the current value passed in for the grace-period counter. */
void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq) { int i, j; WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp)); if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL)) return; /* * Find all callbacks whose ->gp_seq numbers indicate that they * are ready to invoke, and put them into the RCU_DONE_TAIL segment. */ for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) { if (ULONG_CMP_LT(seq, rsclp->gp_seq[i])) break; WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]); } /* If no callbacks moved, nothing more need be done. */ if (i == RCU_WAIT_TAIL) return; /* Clean up tail pointers that might have been misordered above. */ for (j = RCU_WAIT_TAIL; j < i; j++) WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]); /* * Callbacks moved, so clean up the misordered ->tails[] pointers * that now point into the middle of the list of ready-to-invoke * callbacks. The overall effect is to copy down the later pointers * into the gap that was created by the now-ready segments. */ for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) { if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) break; /* No more callbacks. */ WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]); rsclp->gp_seq[j] = rsclp->gp_seq[i]; } };
콜백들을 앞쪽으로 옮기는 cascade 처리를 수행한다. gp가 만료된 콜백들을 done 구간으로 옮기고, wait 구간이 빈 경우 next-ready 구간의 콜백들을 wait구간으로 옮긴다. 신규 진입한 콜백들의 경우 동일한 completed 발급번호를 사용하는 구간이 있으면 그 구간(wait or next-ready)과 합치는 acceleration작업도 수행한다. gp kthread를 깨워야 하는 경우 true를 반환한다.
- 코드 라인 6~7에서 done 구간 이후에 대기중인 콜백이 없으면 true를 반환한다.
- 코드 라인 13~17에서 1단계) 완료 처리. wait 구간과 next_ready 구간에 이미 만료된 콜백을 done 구간으로 옮긴다.
- rnp->gp_seq < gp_seq[]인 경우는 gp가 아직 완료되지 않아 처리할 수 없는 콜백들이다.
- 코드 라인 20~21에서 옮겨진 콜백이 없는 경우 함수를 빠져나간다.
- 코드 라인 24~25에서 위에서 wait 구간 또는 next 구간에 콜백들이 있었던 경우 wait tail 또는 next ready tail이 done tail 보다 앞서 있을 수 있다. 따라서 해당 구간을 일단 done tail과 동일하게 조정한다.
- 코드 라인 33~33에서 2단계) cascade 처리. 하위 (next ready, next) 구간에 있었던 콜백들을 한 단계 상위 구간으로 옮긴다.
다음 그림은 rcu_segcblist_advance() 함수를 통해 cascade 처리가 가능한 경우를 보여준다.
- wait 및 next-ready 구간의 완료 처리 가능한 콜백들을 done 구간으로 옮긴다. wait 구간만 옮겨진 경우 next-ready 구간의 콜백을 wait 구간으로 옮기는 모습을 볼 수 있다.
신규 콜백들의 accelerate 처리
rcu_accelerate_cbs_unlocked()
kernel/rcu/tree.c
/* * Similar to rcu_accelerate_cbs(), but does not require that the leaf * rcu_node structure's ->lock be held. It consults the cached value * of ->gp_seq_needed in the rcu_data structure, and if that indicates * that a new grace-period request be made, invokes rcu_accelerate_cbs() * while holding the leaf rcu_node structure's ->lock. */
static void rcu_accelerate_cbs_unlocked(struct rcu_node *rnp, struct rcu_data *rdp) { unsigned long c; bool needwake; rcu_lockdep_assert_cblist_protected(rdp); c = rcu_seq_snap(&rcu_state.gp_seq); if (!rdp->gpwrap && ULONG_CMP_GE(rdp->gp_seq_needed, c)) { /* Old request still live, so mark recent callbacks. */ (void)rcu_segcblist_accelerate(&rdp->cblist, c); return; } raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */ needwake = rcu_accelerate_cbs(rnp, rdp); raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */ if (needwake) rcu_gp_kthread_wake(); }
신규 콜백들을 묶어 가능한 경우 앞으로 accelerate 처리한다. (leaf 노드 락 없이 진입)
- 코드 라인 8에서 rdp->gp_seq_needed 값이 gp 시퀀스의 스냅샷 보다 크거나 같은 경우 신규 콜백들을 묶어 가능한 경우 앞으로 accelerate 처리하고 함수를 빠져나간다.
- 코드 라인 10~12에서 노드 락을 건후 신규 콜백들을 묶어 가능한 경우 앞으로 accelerate 처리한다.
- 코드 라인 13~14에서 결과 값이 true인 경우 gp 커널 스레드를 깨워야 한다.
rcu_accelerate_cbs()
kernel/rcu/tree.c
/* * If there is room, assign a ->gp_seq number to any callbacks on this * CPU that have not already been assigned. Also accelerate any callbacks * that were previously assigned a ->gp_seq number that has since proven * to be too conservative, which can happen if callbacks get assigned a * ->gp_seq number while RCU is idle, but with reference to a non-root * rcu_node structure. This function is idempotent, so it does not hurt * to call it repeatedly. Returns an flag saying that we should awaken * the RCU grace-period kthread. * * The caller must hold rnp->lock with interrupts disabled. */
static bool rcu_accelerate_cbs(struct rcu_node *rnp, struct rcu_data *rdp) { unsigned long gp_seq_req; bool ret = false; rcu_lockdep_assert_cblist_protected(rdp); raw_lockdep_assert_held_rcu_node(rnp); /* If no pending (not yet ready to invoke) callbacks, nothing to do. */ if (!rcu_segcblist_pend_cbs(&rdp->cblist)) return false; /* * Callbacks are often registered with incomplete grace-period * information. Something about the fact that getting exact * information requires acquiring a global lock... RCU therefore * makes a conservative estimate of the grace period number at which * a given callback will become ready to invoke. The following * code checks this estimate and improves it when possible, thus * accelerating callback invocation to an earlier grace-period * number. */ gp_seq_req = rcu_seq_snap(&rcu_state.gp_seq); if (rcu_segcblist_accelerate(&rdp->cblist, gp_seq_req)) ret = rcu_start_this_gp(rnp, rdp, gp_seq_req); /* Trace depending on how much we were able to accelerate. */ if (rcu_segcblist_restempty(&rdp->cblist, RCU_WAIT_TAIL)) trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("AccWaitCB")); else trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("AccReadyCB")); return ret; }
신규 콜백들을 묶어 가능한 경우 앞으로 accelerate 처리한다. 결과 값이 true인 경우 콜러에서 gp 커널 스레드를 깨워야 한다. (반드시 leaf 노드 락이 획득된 상태에서 진입되어야 한다)
- 코드 라인 10~11에서 pending 콜백들이 없는 경우 함수를 빠져나간다.
- 코드 라인 23~25에서 스냅된 gp 시퀀스 요청 값에 따라 신규 콜백들의 accelerate 처리를 수행한다. 만일 accelerate 처리가 성공한 경우 스냅된 gp 시퀀스 번호로 gp를 시작 요청한다.
rcu_segcblist_accelerate()
kernel/rcu/rcu_segcblist.c
/* * "Accelerate" callbacks based on more-accurate grace-period information. * The reason for this is that RCU does not synchronize the beginnings and * ends of grace periods, and that callbacks are posted locally. This in * turn means that the callbacks must be labelled conservatively early * on, as getting exact information would degrade both performance and * scalability. When more accurate grace-period information becomes * available, previously posted callbacks can be "accelerated", marking * them to complete at the end of the earlier grace period. * * This function operates on an rcu_segcblist structure, and also the * grace-period sequence number seq at which new callbacks would become * ready to invoke. Returns true if there are callbacks that won't be * ready to invoke until seq, false otherwise. */
bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq) { int i; WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp)); if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL)) return false; /* * Find the segment preceding the oldest segment of callbacks * whose ->gp_seq[] completion is at or after that passed in via * "seq", skipping any empty segments. This oldest segment, along * with any later segments, can be merged in with any newly arrived * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq" * as their ->gp_seq[] grace-period completion sequence number. */ for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--) if (rsclp->tails[i] != rsclp->tails[i - 1] && ULONG_CMP_LT(rsclp->gp_seq[i], seq)) break; /* * If all the segments contain callbacks that correspond to * earlier grace-period sequence numbers than "seq", leave. * Assuming that the rcu_segcblist structure has enough * segments in its arrays, this can only happen if some of * the non-done segments contain callbacks that really are * ready to invoke. This situation will get straightened * out by the next call to rcu_segcblist_advance(). * * Also advance to the oldest segment of callbacks whose * ->gp_seq[] completion is at or after that passed in via "seq", * skipping any empty segments. */ if (++i >= RCU_NEXT_TAIL) return false; /* * Merge all later callbacks, including newly arrived callbacks, * into the segment located by the for-loop above. Assign "seq" * as the ->gp_seq[] value in order to correctly handle the case * where there were no pending callbacks in the rcu_segcblist * structure other than in the RCU_NEXT_TAIL segment. */ for (; i < RCU_NEXT_TAIL; i++) { WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]); rsclp->gp_seq[i] = seq; } return true; };
이 함수에서는 next 구간에 새로 진입한 콜백들이 여건이 되면 next-ready 또는 더 나아가 wait 구간으로 옮겨 빠르게 처리할 수 있도록 앞당긴다.(acceleration). rcu gp kthread를 깨워햐 하는 경우 true를 반환한다.
- 코드 라인 6~7에서 done 구간 이후에 대기중인 콜백이 없으면 false를 반환한다.
- 코드 라인 17~20에서 next-ready(2) 구간과 wait(1) 구간에 대해 역순회한다. 만일 assign된 콜백들이 존재하면 루프를 벗어난다.
- 코드 라인 35~36에서 next-ready(2) 구간에 이미 assign된 콜백이 있으면 신규 콜백들을 acceleration 할 수 없으므로 false를 반환하고 함수를 빠져나간다.
- 코드 라인 45~48에서 next(3) 구간의 콜백들을 wait(1) 또는 next-ready(2) 구간에 통합하고, 글로벌 진행 중인 seq 번호로 gp_seq 번호를 갱신한다.
- 코드 라인 49에서 성공 true를 반환한다.
다음 그림은 next 구간에 새로 진입한 콜백을 next-ready 또는 wait 구간으로 acceleration하여 빠르게 처리할 수 있도록 하는 모습을 보여준다.
구조체
rcu_cblist 구조체
include/linux/rcu_segcblist.h”
/* Simple unsegmented callback lists. */ struct rcu_cblist { struct rcu_head *head; struct rcu_head **tail; long len; long len_lazy; };
rcu un-segmented 콜백 리스트 구조체이다.
- *head
- rcu 콜백들이 연결된다.
- 비어있는 경우 null이 사용된다.
- **tail
- 마지막 rcu 콜백을 가리킨다.
- 비어있는 경우 head를 가리킨다.
- len
- 콜백 수
- len_lazy
- lazy 콜백 수
- 참고) non-lazy 콜백 수 = len – len_lazy
rcu_segcblist 구조체
include/linux/rcu_segcblist.h”
struct rcu_segcblist { struct rcu_head *head; struct rcu_head **tails[RCU_CBLIST_NSEGS]; unsigned long gp_seq[RCU_CBLIST_NSEGS]; #ifdef CONFIG_RCU_NOCB_CPU atomic_long_t len; #else long len; #endif long len_lazy; u8 enabled; u8 offloaded; };
rcu segmented 콜백 리스트 구조체이다.
- *head
- rcu 콜백들이 연결된다.
- 비어있는 경우 null이 사용된다.
- **tails[]
- 4 단계로 구성되며, 각각 구간의 마지막 rcu 콜백을 가리킨다.
- 비어있는 경우 이전 구간의 콜백을 가리키고, 모두 비어 있는 경우 head를 가리킨다.
- gp_seq[]
- 각 구간의 gp 시퀀스 번호가 담긴다.
- len
- 콜백 수
- len_lazy
- lazy 콜백 수
- 참고) non-lazy 콜백 수 = len – len_lazy
- enabled
- 활성화 여부가 담긴다. (1=enabled, 0=disabled)
- offloaded
- 커널 v5.4-rc1에서 no-cb 처리를 위한 오프로드 여부가 담긴다. (1=offloaded, 0=none)
참고
- RCU(Read Copy Update) -1- (Basic) | 문c
- RCU(Read Copy Update) -2- (Callback process) | 문c
- RCU(Read Copy Update) -3- (RCU threads) | 문c
- RCU(Read Copy Update) -4- (NOCB process) | 문c
- RCU(Read Copy Update) -5- (Callback list) | 문c – 현재글
- RCU(Read Copy Update) -6- (Expedited GP) | 문c
- RCU(Read Copy Update) -7- (Preemptible RCU) | 문c
- rcu_init() | 문c
- wait_for_completion() | 문c