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