varnish-cache/bin/varnishd/cache/cache_expire.c
0
/*-
1
 * Copyright (c) 2006 Verdens Gang AS
2
 * Copyright (c) 2006-2011 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
 * LRU and object timer handling.
31
 *
32
 */
33
34
#include "config.h"
35
36
#include <stdlib.h>
37
38
#include "cache_varnishd.h"
39
#include "cache_objhead.h"
40
41
#include "vbh.h"
42
#include "vtim.h"
43
44
struct exp_priv {
45
        unsigned                        magic;
46
#define EXP_PRIV_MAGIC                  0x9db22482
47
        /* shared */
48
        struct lock                     mtx;
49
        VSTAILQ_HEAD(,objcore)          inbox;
50
        pthread_cond_t                  condvar;
51
52
        /* owned by exp thread */
53
        struct worker                   *wrk;
54
        struct vsl_log                  vsl;
55
        struct vbh                      *heap;
56
        pthread_t                       thread;
57
};
58
59
static struct exp_priv *exphdl;
60
static int exp_shutdown = 0;
61
62
/*--------------------------------------------------------------------
63
 * Calculate an object's effective ttl time, taking req.ttl into account
64
 * if it is available.
65
 */
66
67
vtim_real
68 3754
EXP_Ttl(const struct req *req, const struct objcore *oc)
69
{
70
        vtim_dur r;
71
72 3754
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
73
74 3754
        r = oc->ttl;
75 3754
        if (req != NULL && req->d_ttl > 0. && req->d_ttl < r)
76 8
                r = req->d_ttl;
77 3754
        return (oc->t_origin + r);
78
}
79
80
/*--------------------------------------------------------------------
81
 * Calculate an object's effective ttl+grace time, taking req.grace into
82
 * account if it is available.
83
 */
84
85
vtim_real
86 272
EXP_Ttl_grace(const struct req *req, const struct objcore *oc)
87
{
88
        vtim_dur g;
89
90 272
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
91
92 272
        g = oc->grace;
93 272
        if (req != NULL && req->d_grace >= 0. && req->d_grace < g)
94 4
                g = req->d_grace;
95 272
        return (EXP_Ttl(req, oc) + g);
96
}
97
98
/*--------------------------------------------------------------------
99
 * Post an objcore to the exp_thread's inbox.
100
 */
101
102
static void
103 3435
exp_mail_it(struct objcore *oc, uint8_t cmds)
104
{
105 3435
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
106 3435
        assert(oc->refcnt > 0);
107 3435
        AZ(cmds & OC_EF_REFD);
108
109 3435
        Lck_AssertHeld(&exphdl->mtx);
110
111 3435
        if (oc->exp_flags & OC_EF_REFD) {
112 3435
                if (!(oc->exp_flags & OC_EF_POSTED)) {
113 3435
                        if (cmds & OC_EF_REMOVE)
114 501
                                VSTAILQ_INSERT_HEAD(&exphdl->inbox,
115
                                    oc, exp_list);
116
                        else
117 2934
                                VSTAILQ_INSERT_TAIL(&exphdl->inbox,
118
                                    oc, exp_list);
119 3435
                        VSC_C_main->exp_mailed++;
120 3435
                }
121 3435
                oc->exp_flags |= cmds | OC_EF_POSTED;
122 3435
                PTOK(pthread_cond_signal(&exphdl->condvar));
123 3435
        }
124 3435
}
125
126
/*--------------------------------------------------------------------
127
 * Setup a new ObjCore for control by expire. Should be called with the
128
 * ObjHead locked by HSH_Unbusy(/HSH_Insert) (in private access).
129
 */
130
131
void
132 2922
EXP_RefNewObjcore(struct objcore *oc)
133
{
134 2922
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
135
136 2922
        Lck_AssertHeld(&oc->objhead->mtx);
137
138 2922
        AZ(oc->exp_flags);
139 2922
        assert(oc->refcnt >= 1);
140 2922
        oc->refcnt++;
141 2922
        oc->exp_flags |= OC_EF_REFD | OC_EF_NEW;
142 2922
}
143
144
145
146
/*--------------------------------------------------------------------
147
 * Call EXP's attention to an oc
148
 */
149
150
void
151 878
EXP_Remove(struct objcore *oc, const struct objcore *new_oc)
152
{
153
154 878
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
155 878
        CHECK_OBJ_ORNULL(new_oc, OBJCORE_MAGIC);
156
157 878
        if (oc->exp_flags & OC_EF_REFD) {
158 501
                Lck_Lock(&exphdl->mtx);
159 501
                if (new_oc != NULL)
160 147
                        VSC_C_main->n_superseded++;
161 501
                if (oc->exp_flags & OC_EF_NEW) {
162
                        /* EXP_Insert has not been called for this object
163
                         * yet. Mark it for removal, and EXP_Insert will
164
                         * clean up once it is called. */
165 0
                        AZ(oc->exp_flags & OC_EF_POSTED);
166 0
                        oc->exp_flags |= OC_EF_REMOVE;
167 0
                } else
168 501
                        exp_mail_it(oc, OC_EF_REMOVE);
169 501
                Lck_Unlock(&exphdl->mtx);
170 501
        }
171 878
}
172
173
/*--------------------------------------------------------------------
174
 * Insert new object.
175
 *
176
 * Caller got a oc->refcnt for us.
177
 */
178
179
void
180 2922
EXP_Insert(struct worker *wrk, struct objcore *oc)
181
{
182 2922
        unsigned remove_race = 0;
183
        struct objcore *tmpoc;
184
185 2922
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
186 2922
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
187
188 2922
        AZ(oc->flags & OC_F_BUSY);
189
190 2922
        if (!(oc->exp_flags & OC_EF_REFD))
191 0
                return;
192
193
        /* One ref held by the caller, and one that will be owned by
194
         * expiry. */
195 2922
        assert(oc->refcnt >= 2);
196
197 2922
        ObjSendEvent(wrk, oc, OEV_INSERT);
198
199 2922
        Lck_Lock(&exphdl->mtx);
200 2922
        AN(oc->exp_flags & OC_EF_NEW);
201 2922
        oc->exp_flags &= ~OC_EF_NEW;
202 2922
        AZ(oc->exp_flags & (OC_EF_INSERT | OC_EF_MOVE | OC_EF_POSTED));
203 2922
        if (oc->exp_flags & OC_EF_REMOVE) {
204
                /* We raced some other thread executing EXP_Remove */
205 0
                remove_race = 1;
206 0
                oc->exp_flags &= ~(OC_EF_REFD | OC_EF_REMOVE);
207 0
        } else
208 2922
                exp_mail_it(oc, OC_EF_INSERT | OC_EF_MOVE);
209 2922
        Lck_Unlock(&exphdl->mtx);
210
211 2922
        if (remove_race) {
212 0
                ObjSendEvent(wrk, oc, OEV_EXPIRE);
213 0
                tmpoc = oc;
214 0
                assert(oc->refcnt >= 2); /* Silence coverity */
215 0
                (void)HSH_DerefObjCore(wrk, &oc);
216 0
                AZ(oc);
217 0
                assert(tmpoc->refcnt >= 1); /* Silence coverity */
218 0
        }
219 2922
}
220
221
/*--------------------------------------------------------------------
222
 * Reduce object timers
223
 */
224
225
void
226 20
EXP_Reduce(struct objcore *oc, vtim_real now,
227
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
228
{
229
230 20
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
231 20
        assert(oc->refcnt > 0);
232
233 20
        if (!isnan(ttl) && now + ttl - oc->t_origin >= oc->ttl)
234 12
                ttl = NAN;
235 20
        if (!isnan(grace) && grace >= oc->grace)
236 4
                grace = NAN;
237 20
        if (!isnan(keep) && keep >= oc->keep)
238 2
                keep = NAN;
239
240 20
        EXP_Rearm(oc, now, ttl, grace, keep);
241 20
}
242
243
/*--------------------------------------------------------------------
244
 * We have changed one or more of the object timers, tell the exp_thread
245
 *
246
 */
247
248
void
249 20
EXP_Rearm(struct objcore *oc, vtim_real now,
250
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
251
{
252
        vtim_real when;
253
254 20
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
255 20
        assert(oc->refcnt > 0);
256
257 20
        if (!(oc->exp_flags & OC_EF_REFD))
258 0
                return;
259
260 20
        if (!isnan(ttl))
261 8
                oc->ttl = now + ttl - oc->t_origin;
262 20
        if (!isnan(grace))
263 4
                oc->grace = grace;
264 20
        if (!isnan(keep))
265 4
                oc->keep = keep;
266
267 20
        when = EXP_WHEN(oc);
268
269 40
        VSL(SLT_ExpKill, NO_VXID, "EXP_Rearm p=%p E=%.6f e=%.6f f=0x%x", oc,
270 20
            oc->timer_when, when, oc->flags);
271
272 20
        if (when < oc->t_origin || when < oc->timer_when) {
273 12
                Lck_Lock(&exphdl->mtx);
274 12
                if (oc->exp_flags & OC_EF_NEW) {
275
                        /* EXP_Insert has not been called yet, do nothing
276
                         * as the initial insert will execute the move
277
                         * operation. */
278 0
                } else
279 12
                        exp_mail_it(oc, OC_EF_MOVE);
280 12
                Lck_Unlock(&exphdl->mtx);
281 12
        }
282 20
}
283
284
/*--------------------------------------------------------------------
285
 * Handle stuff in the inbox
286
 */
287
288
static void
289 3435
exp_inbox(struct exp_priv *ep, struct objcore *oc, unsigned flags, vtim_real now)
290
{
291
292 3435
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
293 3435
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
294 3435
        assert(oc->refcnt > 0);
295
296 6870
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inbox flg=%x p=%p e=%.6f f=0x%x",
297 3435
            flags, oc, oc->timer_when, oc->flags);
298
299 3435
        if (flags & OC_EF_REMOVE) {
300 501
                if (!(flags & OC_EF_INSERT)) {
301 501
                        assert(oc->timer_idx != VBH_NOIDX);
302 501
                        VBH_delete(ep->heap, oc->timer_idx);
303 501
                }
304 501
                assert(oc->timer_idx == VBH_NOIDX);
305 501
                assert(oc->refcnt > 0);
306 501
                AZ(oc->exp_flags);
307 1002
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Removed x=%ju t=%.0f h=%jd",
308 501
                    VXID(ObjGetXID(ep->wrk, oc)), EXP_Ttl(NULL, oc) - now,
309 501
                    (intmax_t)oc->hits);
310 501
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
311 501
                (void)HSH_DerefObjCore(ep->wrk, &oc);
312 501
                return;
313
        }
314
315 2934
        if (flags & OC_EF_MOVE) {
316 2934
                oc->timer_when = EXP_WHEN(oc);
317 2934
                ObjSendEvent(ep->wrk, oc, OEV_TTLCHG);
318 2934
        }
319
320 5868
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_When p=%p e=%.6f f=0x%x", oc,
321 2934
            oc->timer_when, flags);
322
323
        /*
324
         * XXX: There are some pathological cases here, were we
325
         * XXX: insert or move an expired object, only to find out
326
         * XXX: the next moment and rip them out again.
327
         */
328
329 2934
        if (flags & OC_EF_INSERT) {
330 2922
                assert(oc->timer_idx == VBH_NOIDX);
331 2922
                VBH_insert(exphdl->heap, oc);
332 2922
                assert(oc->timer_idx != VBH_NOIDX);
333 2934
        } else if (flags & OC_EF_MOVE) {
334 12
                assert(oc->timer_idx != VBH_NOIDX);
335 12
                VBH_reorder(exphdl->heap, oc->timer_idx);
336 12
                assert(oc->timer_idx != VBH_NOIDX);
337 12
        } else {
338 0
                WRONG("Objcore state wrong in inbox");
339
        }
340 3435
}
341
342
/*--------------------------------------------------------------------
343
 * Expire stuff from the binheap
344
 */
345
346
static vtim_real
347 10610
exp_expire(struct exp_priv *ep, vtim_real now)
348
{
349
        struct objcore *oc;
350
351 10610
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
352
353 10610
        oc = VBH_root(ep->heap);
354 10610
        if (oc == NULL)
355 4420
                return (now + 355. / 113.);
356 12380
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inspect p=%p e=%.6f f=0x%x", oc,
357 6190
            oc->timer_when - now, oc->flags);
358
359 6190
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
360
361
        /* Ready ? */
362 6190
        if (oc->timer_when > now)
363 5928
                return (oc->timer_when);
364
365 262
        VSC_C_main->n_expired++;
366
367 262
        Lck_Lock(&ep->mtx);
368 262
        if (oc->exp_flags & OC_EF_POSTED) {
369 0
                oc->exp_flags |= OC_EF_REMOVE;
370 0
                oc = NULL;
371 0
        } else {
372 262
                oc->exp_flags &= ~OC_EF_REFD;
373
        }
374 262
        Lck_Unlock(&ep->mtx);
375 262
        if (oc != NULL) {
376 262
                if (!(oc->flags & OC_F_DYING))
377 262
                        HSH_Kill(oc);
378
379
                /* Remove from binheap */
380 262
                assert(oc->timer_idx != VBH_NOIDX);
381 262
                VBH_delete(ep->heap, oc->timer_idx);
382 262
                assert(oc->timer_idx == VBH_NOIDX);
383
384 262
                CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
385 524
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Expired x=%ju t=%.0f h=%jd",
386 262
                    VXID(ObjGetXID(ep->wrk, oc)), EXP_Ttl(NULL, oc) - now,
387 262
                    (intmax_t)oc->hits);
388 262
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
389 262
                (void)HSH_DerefObjCore(ep->wrk, &oc);
390 262
        }
391 262
        return (0);
392 10610
}
393
394
/*--------------------------------------------------------------------
395
 * This thread monitors the root of the binary heap and whenever an
396
 * object expires, accounting also for graceability, it is killed.
397
 */
398
399
static int v_matchproto_(vbh_cmp_t)
400 2443
object_cmp(void *priv, const void *a, const void *b)
401
{
402
        const struct objcore *aa, *bb;
403
404 2443
        (void)priv;
405 2443
        CAST_OBJ_NOTNULL(aa, a, OBJCORE_MAGIC);
406 2443
        CAST_OBJ_NOTNULL(bb, b, OBJCORE_MAGIC);
407 2443
        return (aa->timer_when < bb->timer_when);
408
}
409
410
static void v_matchproto_(vbh_update_t)
411 5387
object_update(void *priv, void *p, unsigned u)
412
{
413
        struct objcore *oc;
414
415 5387
        (void)priv;
416 5387
        CAST_OBJ_NOTNULL(oc, p, OBJCORE_MAGIC);
417 5387
        oc->timer_idx = u;
418 5387
}
419
420
static void * v_matchproto_(bgthread_t)
421 1898
exp_thread(struct worker *wrk, void *priv)
422
{
423
        struct objcore *oc;
424 1898
        vtim_real t = 0, tnext = 0;
425
        struct exp_priv *ep;
426 1898
        unsigned flags = 0;
427
428 1898
        CAST_OBJ_NOTNULL(ep, priv, EXP_PRIV_MAGIC);
429 1898
        ep->wrk = wrk;
430 1898
        VSL_Setup(&ep->vsl, NULL, 0);
431 1898
        AZ(wrk->vsl);
432 1898
        wrk->vsl = &ep->vsl;
433 1898
        ep->heap = VBH_new(NULL, object_cmp, object_update);
434 1898
        AN(ep->heap);
435 15943
        while (exp_shutdown == 0) {
436
437 14045
                Lck_Lock(&ep->mtx);
438 14045
                oc = VSTAILQ_FIRST(&ep->inbox);
439 14045
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
440 14045
                if (oc != NULL) {
441 3435
                        assert(oc->refcnt >= 1);
442 3435
                        assert(oc->exp_flags & OC_EF_POSTED);
443 3435
                        VSTAILQ_REMOVE(&ep->inbox, oc, objcore, exp_list);
444 3435
                        VSC_C_main->exp_received++;
445 3435
                        tnext = 0;
446 3435
                        flags = oc->exp_flags;
447 3435
                        if (flags & OC_EF_REMOVE)
448 501
                                oc->exp_flags = 0;
449
                        else
450 2934
                                oc->exp_flags &= OC_EF_REFD;
451 14045
                } else if (tnext > t) {
452 5292
                        VSL_Flush(&ep->vsl, 0);
453 5292
                        Pool_Sumstat(wrk);
454 5292
                        (void)Lck_CondWaitUntil(&ep->condvar, &ep->mtx, tnext);
455 5292
                }
456 14045
                Lck_Unlock(&ep->mtx);
457
458 14045
                t = VTIM_real();
459
460 14045
                if (oc != NULL)
461 3435
                        exp_inbox(ep, oc, flags, t);
462
                else
463 10610
                        tnext = exp_expire(ep, t);
464
        }
465 1898
        wrk->vsl = NULL;
466 1898
        return (NULL);
467
}
468
469
/*--------------------------------------------------------------------*/
470
471
void
472 1898
EXP_Init(void)
473
{
474
        struct exp_priv *ep;
475
        pthread_t pt;
476
477 1898
        ALLOC_OBJ(ep, EXP_PRIV_MAGIC);
478 1898
        AN(ep);
479
480 1898
        Lck_New(&ep->mtx, lck_exp);
481 1898
        PTOK(pthread_cond_init(&ep->condvar, NULL));
482 1898
        VSTAILQ_INIT(&ep->inbox);
483 1898
        WRK_BgThread(&pt, "cache-exp", exp_thread, ep);
484 1898
        ep->thread = pt;
485 1898
        exphdl = ep;
486 1898
}
487
488
void
489 1872
EXP_Shutdown(void)
490
{
491 1872
        struct exp_priv *ep = exphdl;
492
        void *status;
493
494 1872
        Lck_Lock(&ep->mtx);
495 1872
        exp_shutdown = 1;
496 1872
        PTOK(pthread_cond_signal(&ep->condvar));
497 1872
        Lck_Unlock(&ep->mtx);
498
499 1872
        AN(ep->thread);
500 1872
        PTOK(pthread_join(ep->thread, &status));
501 1872
        AZ(status);
502 1872
        memset(&ep->thread, 0, sizeof ep->thread);
503
504
        /* XXX could cleanup more - not worth it for now */
505 1872
}