| | varnish-cache/bin/varnishd/cache/cache_ban_lurker.c |
0 |
|
/*- |
1 |
|
* Copyright (c) 2006 Verdens Gang AS |
2 |
|
* Copyright (c) 2006-2015 Varnish Software AS |
3 |
|
* All rights reserved. |
4 |
|
* |
5 |
|
* Author: Poul-Henning Kamp <phk@phk.freebsd.dk> |
6 |
|
* |
7 |
|
* SPDX-License-Identifier: BSD-2-Clause |
8 |
|
* |
9 |
|
* Redistribution and use in source and binary forms, with or without |
10 |
|
* modification, are permitted provided that the following conditions |
11 |
|
* are met: |
12 |
|
* 1. Redistributions of source code must retain the above copyright |
13 |
|
* notice, this list of conditions and the following disclaimer. |
14 |
|
* 2. Redistributions in binary form must reproduce the above copyright |
15 |
|
* notice, this list of conditions and the following disclaimer in the |
16 |
|
* documentation and/or other materials provided with the distribution. |
17 |
|
* |
18 |
|
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
19 |
|
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
20 |
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
21 |
|
* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE |
22 |
|
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
23 |
|
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
24 |
|
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
25 |
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
26 |
|
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
27 |
|
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
28 |
|
* SUCH DAMAGE. |
29 |
|
* |
30 |
|
*/ |
31 |
|
|
32 |
|
#include "config.h" |
33 |
|
|
34 |
|
#include "cache_varnishd.h" |
35 |
|
|
36 |
|
#include "cache_ban.h" |
37 |
|
#include "cache_objhead.h" |
38 |
|
|
39 |
|
#include "vtim.h" |
40 |
|
|
41 |
|
static struct objcore oc_mark_cnt = { .magic = OBJCORE_MAGIC, }; |
42 |
|
static struct objcore oc_mark_end = { .magic = OBJCORE_MAGIC, }; |
43 |
|
static unsigned ban_batch; |
44 |
|
static unsigned ban_generation; |
45 |
|
|
46 |
|
pthread_cond_t ban_lurker_cond; |
47 |
|
|
48 |
|
void |
49 |
80627 |
ban_kick_lurker(void) |
50 |
|
{ |
51 |
|
|
52 |
80627 |
Lck_AssertHeld(&ban_mtx); |
53 |
80627 |
ban_generation++; |
54 |
80627 |
PTOK(pthread_cond_signal(&ban_lurker_cond)); |
55 |
80627 |
} |
56 |
|
|
57 |
|
/* |
58 |
|
* ban_cleantail: clean the tail of the ban list up to the first ban which is |
59 |
|
* still referenced. For already completed bans, we update statistics |
60 |
|
* accordingly, but otherwise just skip the completion step and remove directly |
61 |
|
* |
62 |
|
* if an obans list is passed, we clean its tail as well |
63 |
|
*/ |
64 |
|
|
65 |
|
static void |
66 |
81174 |
ban_cleantail(struct banhead_s *obans) |
67 |
|
{ |
68 |
|
struct ban *b, *bt; |
69 |
81174 |
struct banhead_s freelist = VTAILQ_HEAD_INITIALIZER(freelist); |
70 |
|
|
71 |
|
/* handle the zero-length tail unprotected */ |
72 |
81174 |
if (VTAILQ_LAST(&ban_head, banhead_s) == VTAILQ_FIRST(&ban_head)) |
73 |
73894 |
return; |
74 |
|
|
75 |
7280 |
Lck_Lock(&ban_mtx); |
76 |
7280 |
do { |
77 |
10162 |
b = VTAILQ_LAST(&ban_head, banhead_s); |
78 |
10162 |
if (b != VTAILQ_FIRST(&ban_head) && b->refcount == 0) { |
79 |
2882 |
assert(VTAILQ_EMPTY(&b->objcore)); |
80 |
2882 |
if (b->flags & BANS_FLAG_COMPLETED) |
81 |
1682 |
VSC_C_main->bans_completed--; |
82 |
2882 |
if (b->flags & BANS_FLAG_OBJ) |
83 |
1160 |
VSC_C_main->bans_obj--; |
84 |
2882 |
if (b->flags & BANS_FLAG_REQ) |
85 |
840 |
VSC_C_main->bans_req--; |
86 |
2882 |
VSC_C_main->bans--; |
87 |
2882 |
VSC_C_main->bans_deleted++; |
88 |
2882 |
VTAILQ_REMOVE(&ban_head, b, list); |
89 |
2882 |
VTAILQ_INSERT_TAIL(&freelist, b, list); |
90 |
2882 |
bans_persisted_fragmentation += |
91 |
2882 |
ban_len(b->spec); |
92 |
2882 |
VSC_C_main->bans_persisted_fragmentation = |
93 |
2882 |
bans_persisted_fragmentation; |
94 |
2882 |
ban_info_drop(b->spec, ban_len(b->spec)); |
95 |
2882 |
} else { |
96 |
7280 |
b = NULL; |
97 |
|
} |
98 |
10162 |
} while (b != NULL); |
99 |
|
|
100 |
7280 |
Lck_Unlock(&ban_mtx); |
101 |
|
|
102 |
|
/* oban order is head to tail, freelist tail to head */ |
103 |
7280 |
if (obans != NULL) |
104 |
5880 |
bt = VTAILQ_LAST(obans, banhead_s); |
105 |
|
else |
106 |
1400 |
bt = NULL; |
107 |
|
|
108 |
7280 |
if (bt != NULL) { |
109 |
360 |
AN(obans); |
110 |
960 |
VTAILQ_FOREACH(b, &freelist, list) { |
111 |
600 |
if (b != bt) |
112 |
160 |
continue; |
113 |
440 |
VTAILQ_REMOVE(obans, b, l_list); |
114 |
440 |
bt = VTAILQ_LAST(obans, banhead_s); |
115 |
440 |
if (bt == NULL) |
116 |
0 |
break; |
117 |
440 |
} |
118 |
360 |
} |
119 |
|
|
120 |
10162 |
VTAILQ_FOREACH_SAFE(b, &freelist, list, bt) |
121 |
2882 |
BAN_Free(b); |
122 |
|
|
123 |
7280 |
return; |
124 |
81174 |
} |
125 |
|
|
126 |
|
/*-------------------------------------------------------------------- |
127 |
|
* Our task here is somewhat tricky: The canonical locking order is |
128 |
|
* objhead->mtx first, then ban_mtx, because that is the order which |
129 |
|
* makes most sense in HSH_Lookup(), but we come the other way. |
130 |
|
* We optimistically try to get them the other way, and get out of |
131 |
|
* the way if that fails, and retry again later. |
132 |
|
* |
133 |
|
* To avoid hammering on contested ocs, we first move those behind a marker |
134 |
|
* once. When we only have contested ocs left, we stop moving them around and |
135 |
|
* re-try them in order. |
136 |
|
*/ |
137 |
|
|
138 |
|
static struct objcore * |
139 |
1560 |
ban_lurker_getfirst(struct vsl_log *vsl, struct ban *bt) |
140 |
|
{ |
141 |
|
struct objhead *oh; |
142 |
|
struct objcore *oc, *noc; |
143 |
1560 |
int move_oc = 1; |
144 |
|
|
145 |
1560 |
Lck_Lock(&ban_mtx); |
146 |
|
|
147 |
1560 |
oc = VTAILQ_FIRST(&bt->objcore); |
148 |
1560 |
while (1) { |
149 |
1560 |
CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC); |
150 |
|
|
151 |
1560 |
if (oc == &oc_mark_cnt) { |
152 |
680 |
if (VTAILQ_NEXT(oc, ban_list) == &oc_mark_end) { |
153 |
|
/* done with this ban's oc list */ |
154 |
680 |
VTAILQ_REMOVE(&bt->objcore, &oc_mark_cnt, |
155 |
|
ban_list); |
156 |
680 |
VTAILQ_REMOVE(&bt->objcore, &oc_mark_end, |
157 |
|
ban_list); |
158 |
680 |
oc = NULL; |
159 |
680 |
break; |
160 |
|
} |
161 |
0 |
oc = VTAILQ_NEXT(oc, ban_list); |
162 |
0 |
CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC); |
163 |
0 |
move_oc = 0; |
164 |
880 |
} else if (oc == &oc_mark_end) { |
165 |
0 |
assert(move_oc == 0); |
166 |
|
|
167 |
|
/* hold off to give lookup a chance and reiterate */ |
168 |
0 |
VSC_C_main->bans_lurker_contention++; |
169 |
0 |
Lck_Unlock(&ban_mtx); |
170 |
0 |
VSL_Flush(vsl, 0); |
171 |
0 |
VTIM_sleep(cache_param->ban_lurker_holdoff); |
172 |
0 |
Lck_Lock(&ban_mtx); |
173 |
|
|
174 |
0 |
oc = VTAILQ_FIRST(&bt->objcore); |
175 |
0 |
assert(oc == &oc_mark_cnt); |
176 |
0 |
continue; |
177 |
|
} |
178 |
|
|
179 |
880 |
assert(oc != &oc_mark_cnt); |
180 |
880 |
assert(oc != &oc_mark_end); |
181 |
|
|
182 |
880 |
oh = oc->objhead; |
183 |
880 |
CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC); |
184 |
880 |
if (!Lck_Trylock(&oh->mtx)) { |
185 |
880 |
if (oc->flags & OC_F_BUSY) { |
186 |
0 |
Lck_Unlock(&oh->mtx); |
187 |
880 |
} else if (oc->refcnt == 0 || |
188 |
880 |
oc->flags & (OC_F_DYING | OC_F_FAILED)) { |
189 |
|
/* |
190 |
|
* We seize the opportunity to remove |
191 |
|
* the object completely off the ban |
192 |
|
* list, now that we have both the oh |
193 |
|
* and ban mutexes. |
194 |
|
*/ |
195 |
0 |
noc = VTAILQ_NEXT(oc, ban_list); |
196 |
0 |
VTAILQ_REMOVE(&bt->objcore, oc, ban_list); |
197 |
0 |
oc->ban = NULL; |
198 |
0 |
bt->refcount--; |
199 |
0 |
Lck_Unlock(&oh->mtx); |
200 |
0 |
oc = noc; |
201 |
0 |
continue; |
202 |
|
} else { |
203 |
|
/* |
204 |
|
* We got the lock, and the oc is not being |
205 |
|
* dismantled under our feet - grab a ref |
206 |
|
*/ |
207 |
880 |
AZ(oc->flags & OC_F_BUSY); |
208 |
880 |
oc->refcnt += 1; |
209 |
880 |
VTAILQ_REMOVE(&bt->objcore, oc, ban_list); |
210 |
880 |
VTAILQ_INSERT_TAIL(&bt->objcore, oc, ban_list); |
211 |
880 |
Lck_Unlock(&oh->mtx); |
212 |
880 |
break; |
213 |
|
} |
214 |
0 |
} |
215 |
|
|
216 |
0 |
noc = VTAILQ_NEXT(oc, ban_list); |
217 |
|
|
218 |
0 |
if (move_oc) { |
219 |
|
/* contested ocs go between the two markers */ |
220 |
0 |
VTAILQ_REMOVE(&bt->objcore, oc, ban_list); |
221 |
0 |
VTAILQ_INSERT_BEFORE(&oc_mark_end, oc, ban_list); |
222 |
0 |
} |
223 |
|
|
224 |
0 |
oc = noc; |
225 |
|
} |
226 |
1560 |
Lck_Unlock(&ban_mtx); |
227 |
1560 |
return (oc); |
228 |
|
} |
229 |
|
|
230 |
|
static void |
231 |
1400 |
ban_lurker_test_ban(struct worker *wrk, struct ban *bt, |
232 |
|
struct banhead_s *obans, struct ban *bd, int kill) |
233 |
|
{ |
234 |
|
struct ban *bl, *bln; |
235 |
|
struct objcore *oc; |
236 |
|
unsigned tests; |
237 |
|
int i; |
238 |
1400 |
uint64_t tested = 0, tested_tests = 0, lok = 0, lokc = 0; |
239 |
|
|
240 |
1400 |
CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC); |
241 |
|
|
242 |
|
/* |
243 |
|
* First see if there is anything to do, and if so, insert markers |
244 |
|
*/ |
245 |
1400 |
Lck_Lock(&ban_mtx); |
246 |
1400 |
oc = VTAILQ_FIRST(&bt->objcore); |
247 |
1400 |
if (oc != NULL) { |
248 |
680 |
VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_cnt, ban_list); |
249 |
680 |
VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_end, ban_list); |
250 |
680 |
} |
251 |
1400 |
Lck_Unlock(&ban_mtx); |
252 |
1400 |
if (oc == NULL) |
253 |
720 |
return; |
254 |
|
|
255 |
1560 |
while (1) { |
256 |
1560 |
if (++ban_batch > cache_param->ban_lurker_batch) { |
257 |
0 |
(void)Pool_TrySumstat(wrk); |
258 |
0 |
VTIM_sleep(cache_param->ban_lurker_sleep); |
259 |
0 |
ban_batch = 0; |
260 |
0 |
} |
261 |
1560 |
oc = ban_lurker_getfirst(wrk->vsl, bt); |
262 |
1560 |
if (oc == NULL) { |
263 |
680 |
if (tested == 0 && lokc == 0) { |
264 |
280 |
AZ(tested_tests); |
265 |
280 |
AZ(lok); |
266 |
280 |
return; |
267 |
|
} |
268 |
400 |
Lck_Lock(&ban_mtx); |
269 |
400 |
VSC_C_main->bans_lurker_tested += tested; |
270 |
400 |
VSC_C_main->bans_lurker_tests_tested += tested_tests; |
271 |
400 |
VSC_C_main->bans_lurker_obj_killed += lok; |
272 |
400 |
VSC_C_main->bans_lurker_obj_killed_cutoff += lokc; |
273 |
400 |
Lck_Unlock(&ban_mtx); |
274 |
400 |
return; |
275 |
|
} |
276 |
880 |
i = 0; |
277 |
1720 |
VTAILQ_FOREACH_REVERSE_SAFE(bl, obans, banhead_s, l_list, bln) { |
278 |
1440 |
if (oc->ban != bt) { |
279 |
|
/* |
280 |
|
* HSH_Lookup() grabbed this oc, killed |
281 |
|
* it or tested it to top. We're done. |
282 |
|
*/ |
283 |
0 |
break; |
284 |
|
} |
285 |
1440 |
if (bl->flags & BANS_FLAG_COMPLETED) { |
286 |
|
/* Ban was overtaken by new (dup) ban */ |
287 |
0 |
VTAILQ_REMOVE(obans, bl, l_list); |
288 |
0 |
continue; |
289 |
|
} |
290 |
1440 |
if (kill == 1) |
291 |
120 |
i = 1; |
292 |
|
else { |
293 |
1320 |
AZ(bl->flags & BANS_FLAG_REQ); |
294 |
1320 |
tests = 0; |
295 |
1320 |
i = ban_evaluate(wrk, bl->spec, oc, NULL, |
296 |
|
&tests); |
297 |
1320 |
tested++; |
298 |
1320 |
tested_tests += tests; |
299 |
|
} |
300 |
1440 |
if (i) { |
301 |
600 |
if (kill) { |
302 |
240 |
VSLb(wrk->vsl, SLT_ExpBan, |
303 |
|
"%ju killed for lurker cutoff", |
304 |
120 |
VXID(ObjGetXID(wrk, oc))); |
305 |
120 |
lokc++; |
306 |
120 |
} else { |
307 |
960 |
VSLb(wrk->vsl, SLT_ExpBan, |
308 |
|
"%ju banned by lurker", |
309 |
480 |
VXID(ObjGetXID(wrk, oc))); |
310 |
480 |
lok++; |
311 |
|
} |
312 |
600 |
HSH_Kill(oc); |
313 |
600 |
break; |
314 |
|
} |
315 |
840 |
} |
316 |
880 |
if (i == 0 && oc->ban == bt) { |
317 |
280 |
Lck_Lock(&ban_mtx); |
318 |
280 |
VSC_C_main->bans_lurker_tested += tested; |
319 |
280 |
VSC_C_main->bans_lurker_tests_tested += tested_tests; |
320 |
280 |
VSC_C_main->bans_lurker_obj_killed += lok; |
321 |
280 |
VSC_C_main->bans_lurker_obj_killed_cutoff += lokc; |
322 |
280 |
tested = tested_tests = lok = lokc = 0; |
323 |
280 |
if (oc->ban == bt && bt != bd) { |
324 |
200 |
bt->refcount--; |
325 |
200 |
VTAILQ_REMOVE(&bt->objcore, oc, ban_list); |
326 |
200 |
oc->ban = bd; |
327 |
200 |
bd->refcount++; |
328 |
200 |
VTAILQ_INSERT_TAIL(&bd->objcore, oc, ban_list); |
329 |
200 |
i = 1; |
330 |
200 |
} |
331 |
280 |
Lck_Unlock(&ban_mtx); |
332 |
280 |
if (i) |
333 |
200 |
ObjSendEvent(wrk, oc, OEV_BANCHG); |
334 |
280 |
} |
335 |
880 |
(void)HSH_DerefObjCore(wrk, &oc, 0); |
336 |
|
} |
337 |
1400 |
} |
338 |
|
|
339 |
|
/*-------------------------------------------------------------------- |
340 |
|
* Ban lurker thread: |
341 |
|
* |
342 |
|
* try to move ocs as far up the ban list as possible (to bd) |
343 |
|
* |
344 |
|
* BANS_FLAG_REQ bans act as barriers, for bans further down, ocs get moved to |
345 |
|
* them. But still all bans up to the initial bd get checked and marked |
346 |
|
* completed. |
347 |
|
*/ |
348 |
|
|
349 |
|
static vtim_dur |
350 |
81174 |
ban_lurker_work(struct worker *wrk) |
351 |
|
{ |
352 |
|
struct ban *b, *bd; |
353 |
|
struct banhead_s obans; |
354 |
|
vtim_real d; |
355 |
|
vtim_dur dt, n; |
356 |
81174 |
unsigned count = 0, cutoff = UINT_MAX; |
357 |
|
|
358 |
81174 |
CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC); |
359 |
|
|
360 |
81174 |
dt = 49.62; // Random, non-magic |
361 |
81174 |
if (cache_param->ban_lurker_sleep == 0) { |
362 |
2000 |
ban_cleantail(NULL); |
363 |
2000 |
return (dt); |
364 |
|
} |
365 |
79174 |
if (cache_param->ban_cutoff > 0) |
366 |
560 |
cutoff = cache_param->ban_cutoff; |
367 |
|
|
368 |
79174 |
Lck_Lock(&ban_mtx); |
369 |
79174 |
b = ban_start; |
370 |
79174 |
Lck_Unlock(&ban_mtx); |
371 |
79174 |
d = VTIM_real() - cache_param->ban_lurker_age; |
372 |
79174 |
bd = NULL; |
373 |
79174 |
VTAILQ_INIT(&obans); |
374 |
179228 |
for (; b != NULL; b = VTAILQ_NEXT(b, list), count++) { |
375 |
100054 |
if (bd != NULL) |
376 |
2800 |
ban_lurker_test_ban(wrk, b, &obans, bd, |
377 |
1400 |
count > cutoff ? 1 : 0); |
378 |
100054 |
if (b->flags & BANS_FLAG_COMPLETED) |
379 |
79494 |
continue; |
380 |
20560 |
if (b->flags & BANS_FLAG_REQ && count <= cutoff) { |
381 |
3680 |
if (bd != NULL) |
382 |
200 |
bd = VTAILQ_NEXT(b, list); |
383 |
3680 |
continue; |
384 |
|
} |
385 |
16880 |
n = ban_time(b->spec) - d; |
386 |
16880 |
if (n < 0) { |
387 |
1120 |
VTAILQ_INSERT_TAIL(&obans, b, l_list); |
388 |
1120 |
if (bd == NULL) |
389 |
400 |
bd = b; |
390 |
16880 |
} else if (n < dt) { |
391 |
1000 |
dt = n; |
392 |
1000 |
} |
393 |
16880 |
} |
394 |
|
|
395 |
|
/* |
396 |
|
* conceptually, all obans are now completed. Remove the tail. |
397 |
|
* If any bans to be completed remain after the tail is cut, |
398 |
|
* mark them completed |
399 |
|
*/ |
400 |
79174 |
ban_cleantail(&obans); |
401 |
|
|
402 |
79174 |
if (VTAILQ_FIRST(&obans) == NULL) |
403 |
78774 |
return (dt); |
404 |
|
|
405 |
400 |
Lck_Lock(&ban_mtx); |
406 |
1080 |
VTAILQ_FOREACH(b, &obans, l_list) |
407 |
680 |
ban_mark_completed(b); |
408 |
400 |
Lck_Unlock(&ban_mtx); |
409 |
400 |
return (dt); |
410 |
81174 |
} |
411 |
|
|
412 |
|
void * v_matchproto_(bgthread_t) |
413 |
37307 |
ban_lurker(struct worker *wrk, void *priv) |
414 |
|
{ |
415 |
|
struct vsl_log vsl; |
416 |
|
vtim_dur dt; |
417 |
37307 |
unsigned gen = ban_generation + 1; |
418 |
|
|
419 |
37307 |
CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC); |
420 |
37307 |
AZ(priv); |
421 |
|
|
422 |
37307 |
VSL_Setup(&vsl, NULL, 0); |
423 |
37307 |
AZ(wrk->vsl); |
424 |
37307 |
wrk->vsl = &vsl; |
425 |
|
|
426 |
118054 |
while (!ban_shutdown) { |
427 |
80747 |
dt = ban_lurker_work(wrk); |
428 |
80747 |
if (DO_DEBUG(DBG_LURKER)) |
429 |
1160 |
VSLb(&vsl, SLT_Debug, "lurker: sleep = %lf", dt); |
430 |
80747 |
Lck_Lock(&ban_mtx); |
431 |
80747 |
if (gen == ban_generation) { |
432 |
43867 |
Pool_Sumstat(wrk); |
433 |
43867 |
(void)Lck_CondWaitTimeout( |
434 |
43867 |
&ban_lurker_cond, &ban_mtx, dt); |
435 |
43867 |
ban_batch = 0; |
436 |
43867 |
} |
437 |
80747 |
gen = ban_generation; |
438 |
80747 |
Lck_Unlock(&ban_mtx); |
439 |
|
} |
440 |
37307 |
wrk->vsl = NULL; |
441 |
37307 |
pthread_exit(0); |
442 |
|
NEEDLESS(return (NULL)); |
443 |
|
} |