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 17448
ban_kick_lurker(void)
49
{
50
51 17448
        Lck_AssertHeld(&ban_mtx);
52 17448
        ban_generation++;
53 17448
        AZ(pthread_cond_signal(&ban_lurker_cond));
54 17448
}
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 17556
ban_cleantail(const struct ban *victim, struct VSC_main *stats)
66
{
67
        struct ban *b, *bt;
68 17556
        struct banhead_s freelist = VTAILQ_HEAD_INITIALIZER(freelist);
69 17556
        int r = 0;
70
71
        /* handle the zero-length tail unprotected */
72 17556
        if (VTAILQ_LAST(&ban_head, banhead_s) == VTAILQ_FIRST(&ban_head))
73 16224
                return (r);
74
75 1332
        Lck_Lock(&ban_mtx);
76
        do {
77 1932
                b = VTAILQ_LAST(&ban_head, banhead_s);
78 1932
                if (b != VTAILQ_FIRST(&ban_head) && b->refcount == 0) {
79 600
                        assert(VTAILQ_EMPTY(&b->objcore));
80 600
                        if (b->flags & BANS_FLAG_COMPLETED)
81 408
                                stats->bans_completed--;
82 600
                        if (b->flags & BANS_FLAG_OBJ)
83 156
                                stats->bans_obj--;
84 600
                        if (b->flags & BANS_FLAG_REQ)
85 216
                                stats->bans_req--;
86 600
                        stats->bans--;
87 600
                        stats->bans_deleted++;
88 600
                        VTAILQ_REMOVE(&ban_head, b, list);
89 600
                        VTAILQ_INSERT_TAIL(&freelist, b, list);
90 600
                        bans_persisted_fragmentation +=
91 600
                            ban_len(b->spec);
92
                        /*
93
                         * XXX absolute update of gauges - may be inaccurate for
94
                         * Pool_Sumstat race
95
                         */
96 600
                        VSC_C_main->bans_persisted_fragmentation =
97
                            bans_persisted_fragmentation;
98 600
                        ban_info_drop(b->spec, ban_len(b->spec));
99
                } else {
100 1332
                        b = NULL;
101
                }
102 1932
        } while (b != NULL);
103
104 1332
        Lck_Unlock(&ban_mtx);
105
106 1932
        VTAILQ_FOREACH_SAFE(b, &freelist, list, bt) {
107 600
                if (b == victim)
108 0
                        r = 1;
109 600
                BAN_Free(b);
110
        }
111
112 1332
        return (r);
113
}
114
115
/*--------------------------------------------------------------------
116
 * Our task here is somewhat tricky:  The canonical locking order is
117
 * objhead->mtx first, then ban_mtx, because that is the order which
118
 * makes most sense in HSH_Lookup(), but we come the other way.
119
 * We optimistically try to get them the other way, and get out of
120
 * the way if that fails, and retry again later.
121
 *
122
 * To avoid hammering on contested ocs, we first move those behind a marker
123
 * once. When we only have contested ocs left, we stop moving them around and
124
 * re-try them in order.
125
 */
126
127
static struct objcore *
128 240
ban_lurker_getfirst(struct vsl_log *vsl, struct ban *bt, struct VSC_main *stats)
129
{
130
        struct objhead *oh;
131
        struct objcore *oc, *noc;
132 240
        int move_oc = 1;
133
134 240
        Lck_Lock(&ban_mtx);
135
136 240
        oc = VTAILQ_FIRST(&bt->objcore);
137
        while (1) {
138 240
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
139
140 240
                if (oc == &oc_mark_cnt) {
141 96
                        if (VTAILQ_NEXT(oc, ban_list) == &oc_mark_end) {
142
                                /* done with this ban's oc list */
143 96
                                VTAILQ_REMOVE(&bt->objcore, &oc_mark_cnt,
144
                                    ban_list);
145 96
                                VTAILQ_REMOVE(&bt->objcore, &oc_mark_end,
146
                                    ban_list);
147 96
                                oc = NULL;
148 96
                                break;
149
                        }
150 0
                        oc = VTAILQ_NEXT(oc, ban_list);
151 0
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
152 0
                        move_oc = 0;
153 144
                } else if (oc == &oc_mark_end) {
154 0
                        assert(move_oc == 0);
155
156
                        /* hold off to give lookup a chance and reiterate */
157 0
                        Lck_Unlock(&ban_mtx);
158 0
                        stats->bans_lurker_contention++;
159 0
                        VSL_Flush(vsl, 0);
160 0
                        VTIM_sleep(cache_param->ban_lurker_holdoff);
161 0
                        Lck_Lock(&ban_mtx);
162
163 0
                        oc = VTAILQ_FIRST(&bt->objcore);
164 0
                        assert(oc == &oc_mark_cnt);
165 0
                        continue;
166
                }
167
168 144
                assert(oc != &oc_mark_cnt);
169 144
                assert(oc != &oc_mark_end);
170
171 144
                oh = oc->objhead;
172 144
                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
173 144
                if (!Lck_Trylock(&oh->mtx)) {
174 144
                        if (oc->refcnt == 0 || oc->flags & OC_F_BUSY) {
175 0
                                Lck_Unlock(&oh->mtx);
176
                        } else {
177
                                /*
178
                                 * We got the lock, and the oc is not being
179
                                 * dismantled under our feet - grab a ref
180
                                 */
181 144
                                AZ(oc->flags & OC_F_BUSY);
182 144
                                oc->refcnt += 1;
183 144
                                VTAILQ_REMOVE(&bt->objcore, oc, ban_list);
184 144
                                VTAILQ_INSERT_TAIL(&bt->objcore, oc, ban_list);
185 144
                                Lck_Unlock(&oh->mtx);
186 144
                                break;
187
                        }
188
                }
189
190 0
                noc = VTAILQ_NEXT(oc, ban_list);
191
192 0
                if (move_oc) {
193
                        /* contested ocs go between the two markers */
194 0
                        VTAILQ_REMOVE(&bt->objcore, oc, ban_list);
195 0
                        VTAILQ_INSERT_BEFORE(&oc_mark_end, oc, ban_list);
196
                }
197
198 0
                oc = noc;
199
        }
200 240
        Lck_Unlock(&ban_mtx);
201 240
        return (oc);
202
}
203
204
static void
205 155
ban_lurker_test_ban(struct worker *wrk, struct vsl_log *vsl, struct ban *bt,
206
    struct banhead_s *obans, struct ban *bd, int kill)
207
{
208
        struct ban *bl, *bln;
209
        struct objcore *oc;
210
        unsigned tests;
211
        int i;
212
        struct VSC_main *stats;
213
214 155
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
215 155
        stats = wrk->stats;
216
217
        /*
218
         * First see if there is anything to do, and if so, insert markers
219
         */
220 155
        Lck_Lock(&ban_mtx);
221 155
        oc = VTAILQ_FIRST(&bt->objcore);
222 155
        if (oc != NULL) {
223 96
                VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_cnt, ban_list);
224 96
                VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_end, ban_list);
225
        }
226 155
        Lck_Unlock(&ban_mtx);
227 155
        if (oc == NULL)
228 59
                return;
229
230
        while (1) {
231 144
                if (++ban_batch > cache_param->ban_lurker_batch) {
232 0
                        VTIM_sleep(cache_param->ban_lurker_sleep);
233 0
                        ban_batch = 0;
234
                }
235 240
                oc = ban_lurker_getfirst(vsl, bt, stats);
236 240
                if (oc == NULL)
237 96
                        return;
238 144
                i = 0;
239 192
                VTAILQ_FOREACH_REVERSE_SAFE(bl, obans, banhead_s, l_list, bln) {
240 180
                        if (oc->ban != bt) {
241
                                /*
242
                                 * HSH_Lookup() grabbed this oc, killed
243
                                 * it or tested it to top.  We're done.
244
                                 */
245 0
                                break;
246
                        }
247 180
                        if (bl->flags & BANS_FLAG_COMPLETED) {
248
                                /* Ban was overtaken by new (dup) ban */
249 0
                                VTAILQ_REMOVE(obans, bl, l_list);
250 0
                                continue;
251
                        }
252 180
                        if (kill == 1)
253 36
                                i = 1;
254
                        else {
255 144
                                AZ(bl->flags & BANS_FLAG_REQ);
256 144
                                tests = 0;
257 144
                                i = ban_evaluate(wrk, bl->spec, oc, NULL,
258
                                    &tests);
259 144
                                stats->bans_lurker_tested++;
260 144
                                stats->bans_lurker_tests_tested += tests;
261
                        }
262 180
                        if (i) {
263 132
                                if (kill) {
264 36
                                        VSLb(vsl, SLT_ExpBan,
265
                                            "%u killed for lurker cutoff",
266
                                            ObjGetXID(wrk, oc));
267 36
                                        stats->
268 36
                                            bans_lurker_obj_killed_cutoff++;
269
                                } else {
270 96
                                        VSLb(vsl, SLT_ExpBan,
271
                                            "%u banned by lurker",
272
                                            ObjGetXID(wrk, oc));
273 96
                                        stats->bans_lurker_obj_killed++;
274
                                }
275 132
                                HSH_Kill(oc);
276 132
                                break;
277
                        }
278
                }
279 144
                if (i == 0 && oc->ban == bt) {
280 12
                        Lck_Lock(&ban_mtx);
281 12
                        if (oc->ban == bt) {
282 12
                                bt->refcount--;
283 12
                                VTAILQ_REMOVE(&bt->objcore, oc, ban_list);
284 12
                                oc->ban = bd;
285 12
                                bd->refcount++;
286 12
                                VTAILQ_INSERT_TAIL(&bd->objcore, oc, ban_list);
287 12
                                i = 1;
288
                        }
289 12
                        Lck_Unlock(&ban_mtx);
290 12
                        if (i)
291 12
                                ObjSendEvent(wrk, oc, OEV_BANCHG);
292
                }
293 144
                (void)HSH_DerefObjCore(wrk, &oc, 0);
294
        }
295
}
296
297
/*--------------------------------------------------------------------
298
 * Ban lurker thread:
299
 *
300
 * try to move ocs as far up the ban list as possible (to bd)
301
 *
302
 * BANS_FLAG_REQ bans act as barriers, for bans further down, ocs get moved to
303
 * them. But still all bans up to the initial bd get checked and marked
304
 * completed.
305
 */
306
307
static double
308 17556
ban_lurker_work(struct worker *wrk, struct vsl_log *vsl)
309
{
310
        struct ban *b, *bd;
311
        struct banhead_s obans;
312
        double d, dt, n;
313 17556
        unsigned count = 0, cutoff = UINT_MAX;
314
        struct VSC_main *stats;
315
316 17556
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
317 17556
        stats = wrk->stats;
318
319 17556
        dt = 49.62;             // Random, non-magic
320 17556
        if (cache_param->ban_lurker_sleep == 0) {
321 600
                (void)ban_cleantail(NULL, stats);
322 600
                return (dt);
323
        }
324 16956
        if (cache_param->ban_cutoff > 0)
325 108
                cutoff = cache_param->ban_cutoff;
326
327 16956
        Lck_Lock(&ban_mtx);
328 16956
        b = ban_start;
329 16956
        Lck_Unlock(&ban_mtx);
330 16956
        d = VTIM_real() - cache_param->ban_lurker_age;
331 16956
        bd = NULL;
332 16956
        VTAILQ_INIT(&obans);
333 35531
        for (; b != NULL; b = VTAILQ_NEXT(b, list)) {
334 18575
                if (bd != NULL && bd != b)
335 155
                        ban_lurker_test_ban(wrk, vsl, b, &obans, bd,
336
                            count > cutoff);
337 18575
                if (b->flags & BANS_FLAG_COMPLETED)
338 17135
                        continue;
339 1440
                if (b->flags & BANS_FLAG_REQ &&
340
                    count <= cutoff) {
341 720
                        if (bd != NULL)
342 12
                                bd = VTAILQ_NEXT(b, list);
343 720
                        continue;
344
                }
345 720
                count++;
346 720
                n = ban_time(b->spec) - d;
347 720
                if (n < 0) {
348 156
                        VTAILQ_INSERT_TAIL(&obans, b, l_list);
349 156
                        if (bd == NULL)
350 72
                                bd = b;
351 564
                } else if (n < dt) {
352 276
                        dt = n;
353
                }
354
        }
355
356
        /*
357
         * conceptually, all obans are now completed. Remove the tail. If it
358
         * containted the first oban, all obans were on the tail and we're
359
         * done.
360
         */
361 16956
        if (ban_cleantail(VTAILQ_FIRST(&obans), stats))
362 0
                return (dt);
363
364 16956
        if (VTAILQ_FIRST(&obans) == NULL)
365 16884
                return (dt);
366
367
        /*
368
         * Mark remaining bans completed: the tail of the obans list is now
369
         * removed, but iterating over it is safe until we hit the new ban list
370
         * tail
371
         *
372
         * bans at the tail of the list may have been completed by other means
373
         * and, consequently, may have been removed from obans, so we skip all
374
         * already completed bans at the tail.
375
         *
376
         * While traversing the ban list backwards, we check if we pass by the
377
         * first oban, in which case we're done.
378
         */
379 72
        bd = VTAILQ_LAST(&ban_head, banhead_s);
380 203
        while (bd->flags & BANS_FLAG_COMPLETED) {
381 118
                if (bd == VTAILQ_FIRST(&ban_head) ||
382 59
                    bd == VTAILQ_FIRST(&obans))
383 0
                        return (dt);
384 59
                bd = VTAILQ_PREV(bd, banhead_s, list);
385
        }
386
387 72
        Lck_Lock(&ban_mtx);
388 156
        VTAILQ_FOREACH(b, &obans, l_list) {
389 156
                ban_mark_completed(b, stats);
390 156
                if (b == bd)
391 72
                        break;
392
        }
393 72
        Lck_Unlock(&ban_mtx);
394 72
        return (dt);
395
}
396
397
void * v_matchproto_(bgthread_t)
398 8220
ban_lurker(struct worker *wrk, void *priv)
399
{
400
        struct vsl_log vsl;
401
        volatile double d;
402 8220
        unsigned gen = ban_generation + 1;
403
404 8220
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
405 8220
        AZ(priv);
406
407 8220
        VSL_Setup(&vsl, NULL, 0);
408
409 33924
        while (!ban_shutdown) {
410 17556
                d = ban_lurker_work(wrk, &vsl);
411 17556
                if (DO_DEBUG(DBG_LURKER))
412 288
                        VSLb(&vsl, SLT_Debug, "lurker: sleep = %lf", d);
413 17556
                d += VTIM_real();
414 17556
                Lck_Lock(&ban_mtx);
415 17556
                if (gen == ban_generation) {
416 9336
                        Pool_Sumstat(wrk);
417 9336
                        (void)Lck_CondWait(&ban_lurker_cond, &ban_mtx, d);
418 9264
                        ban_batch = 0;
419
                }
420 17484
                gen = ban_generation;
421 17484
                Lck_Unlock(&ban_mtx);
422
        }
423 8148
        pthread_exit(0);
424
        NEEDLESS(return NULL);
425
}