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
}