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 1313
ban_kick_lurker(void)
49
{
50
51 1313
        Lck_AssertHeld(&ban_mtx);
52 1313
        ban_generation++;
53 1313
        AZ(pthread_cond_signal(&ban_lurker_cond));
54 1313
}
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 1321
ban_cleantail(const struct ban *victim)
66
{
67
        struct ban *b, *bt;
68 1321
        struct banhead_s freelist = VTAILQ_HEAD_INITIALIZER(freelist);
69 1321
        int r = 0;
70
71
        /* handle the zero-length tail unprotected */
72 1321
        if (VTAILQ_LAST(&ban_head, banhead_s) == VTAILQ_FIRST(&ban_head))
73 1210
                return (r);
74
75 111
        Lck_Lock(&ban_mtx);
76
        do {
77 161
                b = VTAILQ_LAST(&ban_head, banhead_s);
78 161
                if (b != VTAILQ_FIRST(&ban_head) && b->refcount == 0) {
79 50
                        assert(VTAILQ_EMPTY(&b->objcore));
80 50
                        if (b->flags & BANS_FLAG_COMPLETED)
81 34
                                VSC_C_main->bans_completed--;
82 50
                        if (b->flags & BANS_FLAG_OBJ)
83 13
                                VSC_C_main->bans_obj--;
84 50
                        if (b->flags & BANS_FLAG_REQ)
85 18
                                VSC_C_main->bans_req--;
86 50
                        VSC_C_main->bans--;
87 50
                        VSC_C_main->bans_deleted++;
88 50
                        VTAILQ_REMOVE(&ban_head, b, list);
89 50
                        VTAILQ_INSERT_TAIL(&freelist, b, list);
90 50
                        bans_persisted_fragmentation +=
91 50
                            ban_len(b->spec);
92 50
                        VSC_C_main->bans_persisted_fragmentation =
93
                            bans_persisted_fragmentation;
94 50
                        ban_info_drop(b->spec, ban_len(b->spec));
95
                } else {
96 111
                        b = NULL;
97
                }
98 161
        } while (b != NULL);
99
100 111
        Lck_Unlock(&ban_mtx);
101
102 161
        VTAILQ_FOREACH_SAFE(b, &freelist, list, bt) {
103 50
                if (b == victim)
104 0
                        r = 1;
105 50
                BAN_Free(b);
106
        }
107
108 111
        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 20
ban_lurker_getfirst(struct vsl_log *vsl, struct ban *bt)
125
{
126
        struct objhead *oh;
127
        struct objcore *oc, *noc;
128 20
        int move_oc = 1;
129
130 20
        Lck_Lock(&ban_mtx);
131
132 20
        oc = VTAILQ_FIRST(&bt->objcore);
133
        while (1) {
134 20
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
135
136 20
                if (oc == &oc_mark_cnt) {
137 8
                        if (VTAILQ_NEXT(oc, ban_list) == &oc_mark_end) {
138
                                /* done with this ban's oc list */
139 8
                                VTAILQ_REMOVE(&bt->objcore, &oc_mark_cnt,
140
                                    ban_list);
141 8
                                VTAILQ_REMOVE(&bt->objcore, &oc_mark_end,
142
                                    ban_list);
143 8
                                oc = NULL;
144 8
                                break;
145
                        }
146 0
                        oc = VTAILQ_NEXT(oc, ban_list);
147 0
                        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
148 0
                        move_oc = 0;
149 12
                } 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
                        Lck_Unlock(&ban_mtx);
154 0
                        VSC_C_main->bans_lurker_contention++;
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 12
                assert(oc != &oc_mark_cnt);
165 12
                assert(oc != &oc_mark_end);
166
167 12
                oh = oc->objhead;
168 12
                CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
169 12
                if (!Lck_Trylock(&oh->mtx)) {
170 12
                        if (oc->refcnt == 0) {
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 12
                                AZ(oc->flags & OC_F_BUSY);
178 12
                                oc->refcnt += 1;
179 12
                                VTAILQ_REMOVE(&bt->objcore, oc, ban_list);
180 12
                                VTAILQ_INSERT_TAIL(&bt->objcore, oc, ban_list);
181 12
                                Lck_Unlock(&oh->mtx);
182 12
                                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 0
        }
196 20
        Lck_Unlock(&ban_mtx);
197 20
        return (oc);
198
}
199
200
static void
201 13
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
209
        /*
210
         * First see if there is anything to do, and if so, insert markers
211
         */
212 13
        Lck_Lock(&ban_mtx);
213 13
        oc = VTAILQ_FIRST(&bt->objcore);
214 13
        if (oc != NULL) {
215 8
                VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_cnt, ban_list);
216 8
                VTAILQ_INSERT_TAIL(&bt->objcore, &oc_mark_end, ban_list);
217
        }
218 13
        Lck_Unlock(&ban_mtx);
219 13
        if (oc == NULL)
220 5
                return;
221
222
        while (1) {
223 20
                if (++ban_batch > cache_param->ban_lurker_batch) {
224 0
                        VTIM_sleep(cache_param->ban_lurker_sleep);
225 0
                        ban_batch = 0;
226
                }
227 20
                oc = ban_lurker_getfirst(vsl, bt);
228 20
                if (oc == NULL)
229 8
                        return;
230 12
                i = 0;
231 16
                VTAILQ_FOREACH_REVERSE_SAFE(bl, obans, banhead_s, l_list, bln) {
232 15
                        if (oc->ban != bt) {
233
                                /*
234
                                 * HSH_Lookup() grabbed this oc, killed
235
                                 * it or tested it to top.  We're done.
236
                                 */
237 0
                                break;
238
                        }
239 15
                        if (bl->flags & BANS_FLAG_COMPLETED) {
240
                                /* Ban was overtaken by new (dup) ban */
241 0
                                VTAILQ_REMOVE(obans, bl, l_list);
242 0
                                continue;
243
                        }
244 15
                        if (kill == 1)
245 3
                                i = 1;
246
                        else {
247 12
                                AZ(bl->flags & BANS_FLAG_REQ);
248 12
                                tests = 0;
249 12
                                i = ban_evaluate(wrk, bl->spec, oc, NULL,
250
                                    &tests);
251 12
                                VSC_C_main->bans_lurker_tested++;
252 12
                                VSC_C_main->bans_lurker_tests_tested += tests;
253
                        }
254 15
                        if (i) {
255 11
                                if (kill) {
256 3
                                        VSLb(vsl, SLT_ExpBan,
257
                                            "%u killed for lurker cutoff",
258
                                            ObjGetXID(wrk, oc));
259 3
                                        VSC_C_main->
260 3
                                            bans_lurker_obj_killed_cutoff++;
261
                                } else {
262 8
                                        VSLb(vsl, SLT_ExpBan,
263
                                            "%u banned by lurker",
264
                                            ObjGetXID(wrk, oc));
265 8
                                        VSC_C_main->bans_lurker_obj_killed++;
266
                                }
267 11
                                HSH_Kill(oc);
268 11
                                break;
269
                        }
270
                }
271 12
                if (i == 0 && oc->ban == bt) {
272 1
                        Lck_Lock(&ban_mtx);
273 1
                        if (oc->ban == bt) {
274 1
                                bt->refcount--;
275 1
                                VTAILQ_REMOVE(&bt->objcore, oc, ban_list);
276 1
                                oc->ban = bd;
277 1
                                bd->refcount++;
278 1
                                VTAILQ_INSERT_TAIL(&bd->objcore, oc, ban_list);
279 1
                                i = 1;
280
                        }
281 1
                        Lck_Unlock(&ban_mtx);
282 1
                        if (i)
283 1
                                ObjSendEvent(wrk, oc, OEV_BANCHG);
284
                }
285 12
                (void)HSH_DerefObjCore(wrk, &oc, 0);
286 12
        }
287
}
288
289
/*--------------------------------------------------------------------
290
 * Ban lurker thread:
291
 *
292
 * try to move ocs as far up the ban list as possible (to bd)
293
 *
294
 * BANS_FLAG_REQ bans act as barriers, for bans further down, ocs get moved to
295
 * them. But still all bans up to the initial bd get checked and marked
296
 * completed.
297
 */
298
299
static double
300 1321
ban_lurker_work(struct worker *wrk, struct vsl_log *vsl)
301
{
302
        struct ban *b, *bd;
303
        struct banhead_s obans;
304
        double d, dt, n;
305 1321
        unsigned count = 0, cutoff = UINT_MAX;
306
307 1321
        dt = 49.62;             // Random, non-magic
308 1321
        if (cache_param->ban_lurker_sleep == 0) {
309 50
                (void)ban_cleantail(NULL);
310 50
                return (dt);
311
        }
312 1271
        if (cache_param->ban_cutoff > 0)
313 9
                cutoff = cache_param->ban_cutoff;
314
315 1271
        Lck_Lock(&ban_mtx);
316 1271
        b = ban_start;
317 1271
        Lck_Unlock(&ban_mtx);
318 1271
        d = VTIM_real() - cache_param->ban_lurker_age;
319 1271
        bd = NULL;
320 1271
        VTAILQ_INIT(&obans);
321 2677
        for (; b != NULL; b = VTAILQ_NEXT(b, list)) {
322 1406
                if (bd != NULL && bd != b)
323 13
                        ban_lurker_test_ban(wrk, vsl, b, &obans, bd,
324
                            count > cutoff);
325 1406
                if (b->flags & BANS_FLAG_COMPLETED)
326 1286
                        continue;
327 120
                if (b->flags & BANS_FLAG_REQ &&
328
                    count <= cutoff) {
329 60
                        if (bd != NULL)
330 1
                                bd = VTAILQ_NEXT(b, list);
331 60
                        continue;
332
                }
333 60
                count++;
334 60
                n = ban_time(b->spec) - d;
335 60
                if (n < 0) {
336 13
                        VTAILQ_INSERT_TAIL(&obans, b, l_list);
337 13
                        if (bd == NULL)
338 6
                                bd = b;
339 47
                } else if (n < dt) {
340 23
                        dt = n;
341
                }
342
        }
343
344
        /*
345
         * conceptually, all obans are now completed. Remove the tail. If it
346
         * containted the first oban, all obans were on the tail and we're
347
         * done.
348
         */
349 1271
        if (ban_cleantail(VTAILQ_FIRST(&obans)))
350 0
                return (dt);
351
352
        /*
353
         * Mark remaining bans completed: the tail of the obans list is now
354
         * removed, but iterating over it is safe until we hit the new tail ban
355
         */
356 1271
        Lck_Lock(&ban_mtx);
357 1271
        bd = VTAILQ_LAST(&ban_head, banhead_s);
358 1283
        VTAILQ_FOREACH(b, &obans, l_list) {
359 13
                ban_mark_completed(b);
360 13
                if (b == bd)
361 1
                        break;
362
        }
363 1271
        Lck_Unlock(&ban_mtx);
364 1271
        return (dt);
365
}
366
367
void * v_matchproto_(bgthread_t)
368 614
ban_lurker(struct worker *wrk, void *priv)
369
{
370
        struct vsl_log vsl;
371
        volatile double d;
372 614
        unsigned gen = ban_generation + 1;
373
374 614
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
375 614
        AZ(priv);
376
377 614
        VSL_Setup(&vsl, NULL, 0);
378
379 2544
        while (!ban_shutdown) {
380 1321
                d = ban_lurker_work(wrk, &vsl);
381 1321
                if (DO_DEBUG(DBG_LURKER))
382 24
                        VSLb(&vsl, SLT_Debug, "lurker: sleep = %lf", d);
383 1321
                d += VTIM_real();
384 1321
                Lck_Lock(&ban_mtx);
385 1321
                if (gen == ban_generation) {
386 707
                        Pool_Sumstat(wrk);
387 707
                        (void)Lck_CondWait(&ban_lurker_cond, &ban_mtx, d);
388 702
                        ban_batch = 0;
389
                }
390 1316
                gen = ban_generation;
391 1316
                Lck_Unlock(&ban_mtx);
392
        }
393 609
        pthread_exit(0);
394
        NEEDLESS(return NULL);
395
}