← Documents Documentation/kernel-hacking/false-sharing.rst GitHub 원문 ↗

Linux 6.18.37 · Kernel Hacking

Kernel false sharing 분석

서로 관련 없는 field의 write가 cacheline invalidation을 일으키는 false sharing을 perf c2c와 pahole로 찾고 구조를 개선하는 방법을 설명합니다.

Source pathDocumentation/kernel-hacking/false-sharing.rst
Source versionLinux v6.18.37
TranslationDUJINLABS 전문 번역 + 해설

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

Field가 아니라 cacheline 단위로 coherence된다

false-sharing.rst:7-50 
struct foo {
    refcount_t refcount; /* CPU 0이 자주 write */
    char name[16];       /* 다른 CPU들은 read-only */
};

/* 두 field가 같은 64-byte cacheline에 놓일 수 있다. */
그림 1. refcount(A)와 name(B)이 한 cache line을 공유하는 경우
CPU 0refcount(A) write
CPU 1name(B) read
Cache 0A: refcount | B: nameModified owner
Cache 1A: refcount | B: nameInvalidated
cache-line ownership and invalidation
Main MemoryA: refcount | B: name
  1. CPU 1이 B를 읽어 Cache 1에 A와 B가 포함된 line을 보유한다.
  2. CPU 0이 A를 쓰기 위해 소유권을 얻으면 Cache 1의 line 전체가 invalid된다.
  3. B는 바뀌지 않았지만 CPU 1의 다음 B 읽기는 line을 다시 가져와야 한다.

A와 B는 C 언어 관점에서는 별도 member지만 coherence protocol의 소유권 단위는 cache line입니다. CPU 0의 refcount write는 B의 값까지 바꾸지는 않지만 CPU 1이 가진 A+B line 전체를 invalid 상태로 만들고, CPU 1의 다음 name read에 불필요한 cache miss와 line transfer를 발생시킵니다.

CPU cache coherence protocol은 C struct field가 아니라 cacheline을 소유권 단위로 다룹니다. CPU 0이 refcount를 갱신하면 같은 line에 들어 있는 name까지 다른 CPU cache에서 invalidated됩니다. Name은 한 번도 바뀌지 않아도 reader CPU는 line 전체를 반복해 다시 가져옵니다.

유해한 false sharing에는 두 조건이 필요합니다. 여러 CPU가 접근하는 global 또는 shared data이고, 동시에 발생하는 access 중 적어도 하나가 write여야 합니다. Write/write뿐 아니라 write/read 조합도 line ownership을 이동시킵니다.

자주 반복되는 배치 실수

false-sharing.rst:52-89
  • Spinlock이나 mutex와 그 lock이 보호하는 hot data를 같은 cacheline에 둔다.
  • 서로 독립적으로 갱신되는 작은 global counter들을 linker가 같은 line에 모은다.
  • 큰 struct에서 우연히 인접한 field가 서로 다른 CPU hot path에서 write된다.
  • 한 CPU가 lock word에서 spin하는 동안 owner CPU가 같은 line의 protected data를 갱신한다.

작은 SMP에서는 lock과 데이터를 같이 두어 cache locality를 높이는 선택이 유리할 수 있었습니다. 수백 CPU에서 contended lock을 반복 write하면 waiter와 owner 사이에 line이 이동하여 같은 배치가 병목으로 바뀝니다. Alignment는 workload와 access owner를 모른 채 기계적으로 적용할 수 없습니다.

perf c2c로 HITM cacheline 찾기

false-sharing.rst:91-124 
perf c2c record -ag -- sleep 3
perf c2c report --call-graph none -k vmlinux

perf c2c는 cache-to-cache transfer와 HITM, 즉 다른 CPU cache에 modified 상태로 있던 line에서 load한 사건을 모읍니다. Local HITM과 Remote HITM이 많은 physical line을 찾고, 그 line을 접근한 symbol, source line, line 내부 offset과 CPU 분포를 봅니다.

높은 HITM 하나만으로 false sharing을 확정하면 안 됩니다. 같은 shared field를 의도적으로 동기화하는 true sharing일 수도 있습니다. 서로 다른 source path가 같은 line의 서로 다른 offset을 읽고 쓰는지 확인해야 합니다.

pahole과 System.map으로 실제 member 확인

false-sharing.rst:125-131

pahole은 DWARF type 정보를 이용해 struct member offset, hole과 cacheline 경계를 보여 줍니다. perf c2c의 line offset을 pahole layout과 맞추면 어떤 두 member가 충돌하는지 확인할 수 있습니다. Global symbol은 perf 주소를 System.map 또는 vmlinux symbol과 대응시킵니다.

pahole -C mem_cgroup vmlinux
pahole --cacheline-size=64 -C target_type vmlinux
addr2line -e vmlinux -fi 0xffffffff81234567

공간, 복잡도와 맞바꾸는 완화 방법

false-sharing.rst:132-179
완화효과비용 또는 위험
Hot global을 전용 cacheline에 정렬독립 writer 사이 line 이동 제거memory, cache와 TLB footprint 증가
Struct member 재배치읽기 전용 field와 write-hot field 분리다른 member 사이 새 false sharing 가능
변경이 필요할 때만 write불필요한 ownership 획득 감소추가 read와 branch 비용
Per-CPU counter와 batch 합산global write 빈도 감소정확한 즉시 값이 아니며 merge 비용 발생
/* 매번 write하지 않는다. */
if (!test_bit(FLAG, &state))
    set_bit(FLAG, &state);

if (atomic_read(&value) == OLD)
    atomic_set(&value, NEW);

수정 전후를 같은 workload로 검증한다

false-sharing.rst:180-207

Mostly read-only field끼리, 같은 시점에 함께 write되는 field끼리 묶고, 자주 읽는 field와 다른 CPU가 자주 쓰는 field는 분리합니다. 의도적인 layout에는 comment를 남겨 다음 refactor가 경계를 없애지 않게 합니다.

심한 false sharing을 없애도 전체 성능이 오르지 않을 수 있습니다. 병목이 다음 cacheline이나 다른 lock으로 이동하기 때문입니다. 같은 kernel config, CPU affinity, workload와 측정 시간으로 throughput, tail latency, HITM 수를 수정 전후 비교해야 합니다.

RANDSTRUCT 같은 구조체 layout randomization은 member 위치와 cacheline sharing을 바꿀 수 있습니다. 재현할 때 build config와 exact vmlinux를 반드시 보존합니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기
1 .. SPDX-License-Identifier: GPL-2.0
2
3 =============
4 False Sharing
5 =============
6
7 What is False Sharing
8 =====================
9 False sharing is related with cache mechanism of maintaining the data
10 coherence of one cache line stored in multiple CPU's caches; then
11 academic definition for it is in [1]_. Consider a struct with a
12 refcount and a string::
13
14 struct foo {
15 refcount_t refcount;
16 ...
17 char name[16];
18 } ____cacheline_internodealigned_in_smp;
19
20 Member 'refcount'(A) and 'name'(B) _share_ one cache line like below::
21
22 +-----------+ +-----------+
23 | CPU 0 | | CPU 1 |
24 +-----------+ +-----------+
25 / |
26 / |
27 V V
28 +----------------------+ +----------------------+
29 | A B | Cache 0 | A B | Cache 1
30 +----------------------+ +----------------------+
31 | |
32 ---------------------------+------------------+-----------------------------
33 | |
34 +----------------------+
35 | |
36 +----------------------+
37 Main Memory | A B |
38 +----------------------+
39
40 'refcount' is modified frequently, but 'name' is set once at object
41 creation time and is never modified. When many CPUs access 'foo' at
42 the same time, with 'refcount' being only bumped by one CPU frequently
43 and 'name' being read by other CPUs, all those reading CPUs have to
44 reload the whole cache line over and over due to the 'sharing', even
45 though 'name' is never changed.
46
47 There are many real-world cases of performance regressions caused by
48 false sharing. One of these is a rw_semaphore 'mmap_lock' inside
49 mm_struct struct, whose cache line layout change triggered a
50 regression and Linus analyzed in [2]_.
51
52 There are two key factors for a harmful false sharing:
53
54 * A global datum accessed (shared) by many CPUs
55 * In the concurrent accesses to the data, there is at least one write
56 operation: write/write or write/read cases.
57
58 The sharing could be from totally unrelated kernel components, or
59 different code paths of the same kernel component.
60
61
62 False Sharing Pitfalls
63 ======================
64 Back in time when one platform had only one or a few CPUs, hot data
65 members could be purposely put in the same cache line to make them
66 cache hot and save cacheline/TLB, like a lock and the data protected
67 by it. But for recent large system with hundreds of CPUs, this may
68 not work when the lock is heavily contended, as the lock owner CPU
69 could write to the data, while other CPUs are busy spinning the lock.
70
71 Looking at past cases, there are several frequently occurring patterns
72 for false sharing:
73
74 * lock (spinlock/mutex/semaphore) and data protected by it are
75 purposely put in one cache line.
76 * global data being put together in one cache line. Some kernel
77 subsystems have many global parameters of small size (4 bytes),
78 which can easily be grouped together and put into one cache line.
79 * data members of a big data structure randomly sitting together
80 without being noticed (cache line is usually 64 bytes or more),
81 like 'mem_cgroup' struct.
82
83 Following 'mitigation' section provides real-world examples.
84
85 False sharing could easily happen unless they are intentionally
86 checked, and it is valuable to run specific tools for performance
87 critical workloads to detect false sharing affecting performance case
88 and optimize accordingly.
89
90
91 How to detect and analyze False Sharing
92 ========================================
93 perf record/report/stat are widely used for performance tuning, and
94 once hotspots are detected, tools like 'perf-c2c' and 'pahole' can
95 be further used to detect and pinpoint the possible false sharing
96 data structures. 'addr2line' is also good at decoding instruction
97 pointer when there are multiple layers of inline functions.
98
99 perf-c2c can capture the cache lines with most false sharing hits,
100 decoded functions (line number of file) accessing that cache line,
101 and in-line offset of the data. Simple commands are::
102
103 $ perf c2c record -ag sleep 3
104 $ perf c2c report --call-graph none -k vmlinux
105
106 When running above during testing will-it-scale's tlb_flush1 case,
107 perf reports something like::
108
109 Total records : 1658231
110 Locked Load/Store Operations : 89439
111 Load Operations : 623219
112 Load Local HITM : 92117
113 Load Remote HITM : 139
114
115 #----------------------------------------------------------------------
116 4 0 2374 0 0 0 0xff1100088366d880
117 #----------------------------------------------------------------------
118 0.00% 42.29% 0.00% 0.00% 0.00% 0x8 1 1 0xffffffff81373b7b 0 231 129 5312 64 [k] __mod_lruvec_page_state [kernel.vmlinux] memcontrol.h:752 1
119 0.00% 13.10% 0.00% 0.00% 0.00% 0x8 1 1 0xffffffff81374718 0 226 97 3551 64 [k] folio_lruvec_lock_irqsave [kernel.vmlinux] memcontrol.h:752 1
120 0.00% 11.20% 0.00% 0.00% 0.00% 0x8 1 1 0xffffffff812c29bf 0 170 136 555 64 [k] lru_add_fn [kernel.vmlinux] mm_inline.h:41 1
121 0.00% 7.62% 0.00% 0.00% 0.00% 0x8 1 1 0xffffffff812c3ec5 0 175 108 632 64 [k] release_pages [kernel.vmlinux] mm_inline.h:41 1
122 0.00% 23.29% 0.00% 0.00% 0.00% 0x10 1 1 0xffffffff81372d0a 0 234 279 1051 64 [k] __mod_memcg_lruvec_state [kernel.vmlinux] memcontrol.c:736 1
123
124 A nice introduction for perf-c2c is [3]_.
125
126 'pahole' decodes data structure layouts delimited in cache line
127 granularity. Users can match the offset in perf-c2c output with
128 pahole's decoding to locate the exact data members. For global
129 data, users can search the data address in System.map.
130
131
132 Possible Mitigations
133 ====================
134 False sharing does not always need to be mitigated. False sharing
135 mitigations should balance performance gains with complexity and
136 space consumption. Sometimes, lower performance is OK, and it's
137 unnecessary to hyper-optimize every rarely used data structure or
138 a cold data path.
139
140 False sharing hurting performance cases are seen more frequently with
141 core count increasing. Because of these detrimental effects, many
142 patches have been proposed across variety of subsystems (like
143 networking and memory management) and merged. Some common mitigations
144 (with examples) are:
145
146 * Separate hot global data in its own dedicated cache line, even if it
147 is just a 'short' type. The downside is more consumption of memory,
148 cache line and TLB entries.
149
150 - Commit 91b6d3256356 ("net: cache align tcp_memory_allocated, tcp_sockets_allocated")
151
152 * Reorganize the data structure, separate the interfering members to
153 different cache lines. One downside is it may introduce new false
154 sharing of other members.
155
156 - Commit 802f1d522d5f ("mm: page_counter: re-layout structure to reduce false sharing")
157
158 * Replace 'write' with 'read' when possible, especially in loops.
159 Like for some global variable, use compare(read)-then-write instead
160 of unconditional write. For example, use::
161
162 if (!test_bit(XXX))
163 set_bit(XXX);
164
165 instead of directly "set_bit(XXX);", similarly for atomic_t data::
166
167 if (atomic_read(XXX) == AAA)
168 atomic_set(XXX, BBB);
169
170 - Commit 7b1002f7cfe5 ("bcache: fixup bcache_dev_sectors_dirty_add() multithreaded CPU false sharing")
171 - Commit 292648ac5cf1 ("mm: gup: allow FOLL_PIN to scale in SMP")
172
173 * Turn hot global data to 'per-cpu data + global data' when possible,
174 or reasonably increase the threshold for syncing per-cpu data to
175 global data, to reduce or postpone the 'write' to that global data.
176
177 - Commit 520f897a3554 ("ext4: use percpu_counters for extent_status cache hits/misses")
178 - Commit 56f3547bfa4d ("mm: adjust vm_committed_as_batch according to vm overcommit policy")
179
180 Surely, all mitigations should be carefully verified to not cause side
181 effects. To avoid introducing false sharing when coding, it's better
182 to:
183
184 * Be aware of cache line boundaries
185 * Group mostly read-only fields together
186 * Group things that are written at the same time together
187 * Separate frequently read and frequently written fields on
188 different cache lines.
189
190 and better add a comment stating the false sharing consideration.
191
192 One note is, sometimes even after a severe false sharing is detected
193 and solved, the performance may still have no obvious improvement as
194 the hotspot switches to a new place.
195
196
197 Miscellaneous
198 =============
199 One open issue is that the kernel has an optional data structure
200 randomization mechanism, which also randomizes the situation of cache
201 line sharing among data members.
202
203
204 .. [1] https://en.wikipedia.org/wiki/False_sharing
205 .. [2] https://lore.kernel.org/lkml/CAHk-=whoqV=cX5VC80mmR9rr+Z+yQ6fiQZm36Fb-izsanHg23w@mail.gmail.com/
206 .. [3] https://joemario.github.io/blog/2016/09/01/c2c-blog/
207

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

False sharing의 정의

1-20

False sharing은 여러 CPU cache에 복제된 하나의 cacheline을 coherent하게 유지하는 protocol 때문에 생기는 현상이다. 서로 독립적인 두 data member가 같은 cacheline을 공유하면 한 member의 write가 다른 member만 읽는 CPU의 cacheline까지 무효화할 수 있다.

struct foo {
    refcount_t refcount;
    /* ... */
    char name[16];
} ____cacheline_internodealigned_in_smp;

예제에서 자주 수정되는 refcount(A)와 object 생성 때 한 번 설정된 뒤 바뀌지 않는 name(B)이 같은 cacheline에 들어 있다.

CPU cache 사이의 불필요한 line 이동

20-45

원문의 ASCII 그림은 CPU 0과 CPU 1의 private cache가 A와 B를 포함한 같은 cacheline 사본을 갖고, main memory에도 같은 line이 있는 구조를 보여 준다. 홈페이지에서는 이 관계를 깨끗한 구조화 도식으로 다시 그렸다.

CPU 하나가 refcount만 자주 증가시키고 다른 CPU들이 변경되지 않는 name만 읽더라도 write가 cache coherence traffic을 일으킨다. Name 자체는 변하지 않았지만 reading CPU들은 A와 B가 함께 들어 있는 cacheline 전체를 반복해서 다시 가져와야 한다.

성능에 해로운 false sharing의 두 조건

47-59

실제 성능 regression 사례가 많다. mm_struct의 rw_semaphore인 mmap_lock 주변 cacheline layout 변경으로 regression이 생긴 사례를 Linus가 분석했으며 참고문헌 [2]에 연결되어 있다.

  • 많은 CPU가 접근하는 global data가 있다.
  • 동시 access 중 적어도 하나가 write다. 즉 write/write 또는 write/read 조합이다.

같은 cacheline을 공유하는 주체는 완전히 무관한 kernel component일 수도 있고 한 component 안의 서로 다른 code path일 수도 있다.

CPU 수 증가로 바뀐 cacheline 배치의 손익

62-88

CPU가 하나 또는 몇 개뿐이던 시기에는 lock과 그 lock이 보호하는 data처럼 함께 쓰는 hot member를 같은 cacheline에 넣어 cache와 TLB 효율을 높이기도 했다. 하지만 수백 CPU의 큰 system에서는 lock contention이 심할 때 owner CPU가 data를 쓰고 다른 CPU가 같은 line의 lock에서 spin하므로 오히려 성능이 나빠질 수 있다.

  • Spinlock, mutex, semaphore와 그 lock이 보호하는 data를 의도적으로 같은 cacheline에 둔 경우
  • 여러 개의 작은 global parameter가 우연히 한 cacheline에 모인 경우
  • mem_cgroup처럼 큰 structure의 무관한 member가 64 byte 이상의 같은 cacheline에 우연히 들어간 경우

의도적으로 확인하지 않으면 false sharing은 쉽게 생긴다. 성능이 중요한 workload에서는 전용 도구로 false sharing 영향을 검사하고 결과에 따라 최적화할 가치가 있다.

perf-c2c, pahole, addr2line

91-105

먼저 perf record/report/stat으로 hotspot을 찾은 뒤 perf-c2c와 pahole로 false sharing 후보 structure를 좁힐 수 있다. Inline function layer가 많아 instruction pointer를 source로 해석하기 어려울 때 addr2line도 유용하다.

perf-c2c는 false sharing hit가 많은 cacheline, 그 line에 접근한 function과 source line, line 내부 data offset을 보여 준다.

perf c2c record -ag sleep 3
perf c2c report --call-graph none -k vmlinux

will-it-scale tlb_flush1의 perf-c2c 출력

106-124 
Total records                : 1658231
Locked Load/Store Operations : 89439
Load Operations              : 623219
Load Local HITM              : 92117
Load Remote HITM             : 139

cacheline: 0xff1100088366d880
42.29% offset 0x8  __mod_lruvec_page_state   memcontrol.h:752
13.10% offset 0x8  folio_lruvec_lock_irqsave memcontrol.h:752
11.20% offset 0x8  lru_add_fn                mm_inline.h:41
 7.62% offset 0x8  release_pages             mm_inline.h:41
23.29% offset 0x10 __mod_memcg_lruvec_state  memcontrol.c:736

예시는 특정 cacheline에서 local HITM이 매우 많이 발생하고 offset 0x8과 0x10을 접근하는 여러 function이 coherence contention을 만들고 있음을 보여 준다. perf-c2c 입문 자료는 참고문헌 [3]에 있다.

Cacheline offset을 structure member로 연결하기

126-129

pahole은 data structure layout을 cacheline 경계와 함께 해석한다. perf-c2c가 보고한 line 내부 offset과 pahole layout을 맞추면 정확히 어떤 member가 경쟁하는지 찾을 수 있다. Global data는 System.map에서 주소를 검색한다.

완화 여부를 결정하는 기준

132-144

False sharing이 있다고 항상 고칠 필요는 없다. 성능 개선과 code 복잡성, memory와 cacheline 소비를 함께 비교해야 한다. 거의 사용하지 않는 structure나 cold path를 과도하게 최적화할 필요는 없다.

CPU core 수가 늘수록 false sharing이 성능을 해치는 사례가 더 자주 나타난다. Networking과 memory management를 포함한 여러 subsystem에 이를 완화하는 patch가 merge되어 왔다.

실제 완화 기법과 commit 예

146-179
  • Hot global data가 short type 하나뿐이어도 전용 cacheline으로 분리한다. Memory, cacheline, TLB entry 소비가 늘어난다. 예: 91b6d3256356 net: cache align tcp_memory_allocated, tcp_sockets_allocated.
  • Structure를 재배치해 서로 간섭하는 member를 다른 cacheline으로 나눈다. 다른 member 사이에 새 false sharing을 만들 수 있다. 예: 802f1d522d5f mm: page_counter: re-layout structure to reduce false sharing.
  • 특히 loop에서는 가능한 write를 read로 바꾼다. Global variable을 무조건 쓰지 말고 먼저 읽고 조건이 맞을 때만 쓴다. 예: 7b1002f7cfe5 bcache, 292648ac5cf1 mm: gup.
  • Hot global data를 per-CPU data와 global data 조합으로 바꾸거나 per-CPU 값을 global에 sync하는 threshold를 높여 global write를 줄이거나 늦춘다. 예: 520f897a3554 ext4 percpu_counters, 56f3547bfa4d mm vm_committed_as_batch.
if (!test_bit(XXX))
    set_bit(XXX);

if (atomic_read(XXX) == AAA)
    atomic_set(XXX, BBB);

새 false sharing을 피하는 layout 원칙

180-194
  • Cacheline boundary를 의식한다.
  • 대부분 read-only인 field를 함께 묶는다.
  • 같은 시점에 write되는 field를 함께 묶는다.
  • 자주 read되는 field와 자주 write되는 field를 다른 cacheline으로 분리한다.
  • Layout에 false sharing을 고려했다는 comment를 남긴다.

심한 false sharing을 해결해도 hotspot이 다른 위치로 이동하면 눈에 띄는 성능 개선이 없을 수 있다. 따라서 전체 workload를 다시 측정해야 한다.

구조체 randomization과 참고문헌

197-206

Kernel의 optional data structure randomization은 member 위치뿐 아니라 cacheline 공유 관계도 무작위로 바꾸므로 false sharing 분석에서 고려해야 할 미해결 문제다.