Re: [PATCH v6 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock
From: kbuild test robot
Date: Sun Nov 10 2019 - 16:31:46 EST
Hi Alex,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on linus/master]
[cannot apply to v5.4-rc6 next-20191108]
[if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]
url: https://github.com/0day-ci/linux/commits/Alex-Kogan/locking-qspinlock-Rename-mcs-lock-unlock-macros-and-make-them-more-generic/20191109-180535
base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git 0058b0a506e40d9a2c62015fe92eb64a44d78cd9
reproduce:
# apt-get install sparse
# sparse version: v0.6.1-21-gb31adac-dirty
make ARCH=x86_64 allmodconfig
make C=1 CF='-fdiagnostic-prefix -D__CHECK_ENDIAN__'
If you fix the issue, kindly add following tag
Reported-by: kbuild test robot <lkp@xxxxxxxxx>
sparse warnings: (new ones prefixed by >>)
kernel/locking/qspinlock.c:450:14: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *[assigned] node @@ got ct mcs_spinlock *[assigned] node @@
kernel/locking/qspinlock.c:450:14: sparse: expected struct mcs_spinlock *[assigned] node
kernel/locking/qspinlock.c:450:14: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock.c:498:22: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *prev @@ got struct struct mcs_spinlock *prev @@
kernel/locking/qspinlock.c:498:22: sparse: expected struct mcs_spinlock *prev
kernel/locking/qspinlock.c:498:22: sparse: got struct mcs_spinlock [pure] *
>> kernel/locking/qspinlock_cna.h:141:60: sparse: sparse: incorrect type in initializer (different modifiers) @@ expected struct mcs_spinlock *tail_2nd @@ got struct struct mcs_spinlock *tail_2nd @@
>> kernel/locking/qspinlock_cna.h:141:60: sparse: expected struct mcs_spinlock *tail_2nd
>> kernel/locking/qspinlock_cna.h:141:60: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock.c:450:14: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *[assigned] node @@ got ct mcs_spinlock *[assigned] node @@
kernel/locking/qspinlock.c:450:14: sparse: expected struct mcs_spinlock *[assigned] node
kernel/locking/qspinlock.c:450:14: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock.c:498:22: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *prev @@ got struct struct mcs_spinlock *prev @@
kernel/locking/qspinlock.c:498:22: sparse: expected struct mcs_spinlock *prev
kernel/locking/qspinlock.c:498:22: sparse: got struct mcs_spinlock [pure] *
>> kernel/locking/qspinlock_cna.h:107:18: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *tail_2nd @@ got struct struct mcs_spinlock *tail_2nd @@
kernel/locking/qspinlock_cna.h:107:18: sparse: expected struct mcs_spinlock *tail_2nd
kernel/locking/qspinlock_cna.h:107:18: sparse: got struct mcs_spinlock [pure] *
>> kernel/locking/qspinlock_cna.h:240:61: sparse: sparse: incorrect type in argument 2 (different modifiers) @@ expected struct mcs_spinlock *pred_start @@ got struct struct mcs_spinlock *pred_start @@
>> kernel/locking/qspinlock_cna.h:240:61: sparse: expected struct mcs_spinlock *pred_start
kernel/locking/qspinlock_cna.h:240:61: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock_cna.h:252:26: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *tail_2nd @@ got struct struct mcs_spinlock *tail_2nd @@
kernel/locking/qspinlock_cna.h:252:26: sparse: expected struct mcs_spinlock *tail_2nd
kernel/locking/qspinlock_cna.h:252:26: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock.c:450:14: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *[assigned] node @@ got ct mcs_spinlock *[assigned] node @@
kernel/locking/qspinlock.c:450:14: sparse: expected struct mcs_spinlock *[assigned] node
kernel/locking/qspinlock.c:450:14: sparse: got struct mcs_spinlock [pure] *
kernel/locking/qspinlock.c:498:22: sparse: sparse: incorrect type in assignment (different modifiers) @@ expected struct mcs_spinlock *prev @@ got struct struct mcs_spinlock *prev @@
kernel/locking/qspinlock.c:498:22: sparse: expected struct mcs_spinlock *prev
kernel/locking/qspinlock.c:498:22: sparse: got struct mcs_spinlock [pure] *
vim +141 kernel/locking/qspinlock_cna.h
90
91 static inline bool cna_try_change_tail(struct qspinlock *lock, u32 val,
92 struct mcs_spinlock *node)
93 {
94 struct mcs_spinlock *head_2nd, *tail_2nd;
95 u32 new;
96
97 /* If the secondary queue is empty, do what MCS does. */
98 if (node->locked <= 1)
99 return __try_clear_tail(lock, val, node);
100
101 /*
102 * Try to update the tail value to the last node in the secondary queue.
103 * If successful, pass the lock to the first thread in the secondary
104 * queue. Doing those two actions effectively moves all nodes from the
105 * secondary queue into the main one.
106 */
> 107 tail_2nd = decode_tail(node->locked);
108 head_2nd = tail_2nd->next;
109 new = ((struct cna_node *)tail_2nd)->encoded_tail + _Q_LOCKED_VAL;
110
111 if (atomic_try_cmpxchg_relaxed(&lock->val, &val, new)) {
112 /*
113 * Try to reset @next in tail_2nd to NULL, but no need to check
114 * the result - if failed, a new successor has updated it.
115 */
116 cmpxchg_relaxed(&tail_2nd->next, head_2nd, NULL);
117 arch_mcs_pass_lock(&head_2nd->locked, 1);
118 return true;
119 }
120
121 return false;
122 }
123
124 /*
125 * cna_splice_tail -- splice nodes in the main queue between [first, last]
126 * onto the secondary queue.
127 */
128 static void cna_splice_tail(struct mcs_spinlock *node,
129 struct mcs_spinlock *first,
130 struct mcs_spinlock *last)
131 {
132 /* remove [first,last] */
133 node->next = last->next;
134
135 /* stick [first,last] on the secondary queue tail */
136 if (node->locked <= 1) { /* if secondary queue is empty */
137 /* create secondary queue */
138 last->next = first;
139 } else {
140 /* add to the tail of the secondary queue */
> 141 struct mcs_spinlock *tail_2nd = decode_tail(node->locked);
142 struct mcs_spinlock *head_2nd = tail_2nd->next;
143
144 tail_2nd->next = first;
145 last->next = head_2nd;
146 }
147
148 node->locked = ((struct cna_node *)last)->encoded_tail;
149 }
150
151 /*
152 * cna_scan_main_queue - scan the main waiting queue looking for the first
153 * thread running on the same NUMA node as the lock holder. If found (call it
154 * thread T), move all threads in the main queue between the lock holder and
155 * T to the end of the secondary queue and return 0; otherwise, return the
156 * encoded pointer of the last scanned node in the primary queue (so a
157 * subsequent scan can be resumed from that node)
158 *
159 * Schematically, this may look like the following (nn stands for numa_node and
160 * et stands for encoded_tail).
161 *
162 * when cna_scan_main_queue() is called (the secondary queue is empty):
163 *
164 * A+------------+ B+--------+ C+--------+ T+--------+
165 * |mcs:next | -> |mcs:next| -> |mcs:next| -> |mcs:next| -> NULL
166 * |mcs:locked=1| |cna:nn=0| |cna:nn=2| |cna:nn=1|
167 * |cna:nn=1 | +--------+ +--------+ +--------+
168 * +----------- +
169 *
170 * when cna_scan_main_queue() returns (the secondary queue contains B and C):
171 *
172 * A+----------------+ T+--------+
173 * |mcs:next | -> |mcs:next| -> NULL
174 * |mcs:locked=C.et | -+ |cna:nn=1|
175 * |cna:nn=1 | | +--------+
176 * +--------------- + +-----+
177 * \/
178 * B+--------+ C+--------+
179 * |mcs:next| -> |mcs:next| -+
180 * |cna:nn=0| |cna:nn=2| |
181 * +--------+ +--------+ |
182 * ^ |
183 * +---------------------+
184 *
185 * The worst case complexity of the scan is O(n), where n is the number
186 * of current waiters. However, the amortized complexity is close to O(1),
187 * as the immediate successor is likely to be running on the same node once
188 * threads from other nodes are moved to the secondary queue.
189 */
190 static u32 cna_scan_main_queue(struct mcs_spinlock *node,
191 struct mcs_spinlock *pred_start)
192 {
193 struct cna_node *cn = (struct cna_node *)node;
194 struct cna_node *cni = (struct cna_node *)READ_ONCE(pred_start->next);
195 struct cna_node *last;
196 int my_numa_node = cn->numa_node;
197
198 /* find any next waiter on 'our' NUMA node */
199 for (last = cn;
200 cni && cni->numa_node != my_numa_node;
201 last = cni, cni = (struct cna_node *)READ_ONCE(cni->mcs.next))
202 ;
203
204 /* if found, splice any skipped waiters onto the secondary queue */
205 if (cni) {
206 if (last != cn) /* did we skip any waiters? */
207 cna_splice_tail(node, node->next,
208 (struct mcs_spinlock *)last);
209 return 0;
210 }
211
212 return last->encoded_tail;
213 }
214
215 __always_inline u32 cna_pre_scan(struct qspinlock *lock,
216 struct mcs_spinlock *node)
217 {
218 struct cna_node *cn = (struct cna_node *)node;
219
220 cn->pre_scan_result = cna_scan_main_queue(node, node);
221
222 return 0;
223 }
224
225 static inline void cna_pass_lock(struct mcs_spinlock *node,
226 struct mcs_spinlock *next)
227 {
228 struct cna_node *cn = (struct cna_node *)node;
229 struct mcs_spinlock *next_holder = next, *tail_2nd;
230 u32 val = 1;
231
232 u32 scan = cn->pre_scan_result;
233
234 /*
235 * check if a successor from the same numa node has not been found in
236 * pre-scan, and if so, try to find it in post-scan starting from the
237 * node where pre-scan stopped (stored in @pre_scan_result)
238 */
239 if (scan > 0)
> 240 scan = cna_scan_main_queue(node, decode_tail(scan));
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/hyperkitty/list/kbuild-all@xxxxxxxxxxxx Intel Corporation