Code Coverage: vinyl-cache/bin/vinyld/cache/cache_expire.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
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_int.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 the point in time when an object will become stale, taking
64
 * req.max_age into account, if available
65
 */
66
67
vtim_real
68
EXP_Ttl(const struct req *req, const struct objcore *oc)
69 2935
{
70 2935
        vtim_dur r;
71
72 2935
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
73
74 2935
        r = oc->ttl;
75 2935
        if (req != NULL && req->d_ttl >= 0. && req->d_ttl < r)
76 6
                r = req->d_ttl;
77 2935
        return (oc->t_origin + r);
78 2935
}
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
EXP_Ttl_grace(const struct req *req, const struct objcore *oc)
87 141
{
88 141
        vtim_dur g;
89
90 141
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
91
92 141
        g = oc->grace;
93 141
        if (req != NULL && req->d_grace >= 0. && req->d_grace < g)
94 2
                g = req->d_grace;
95 141
        return (EXP_Ttl(req, oc) + g);
96 141
}
97
98
/*--------------------------------------------------------------------
99
 * Post an objcore to the exp_thread's inbox.
100
 */
101
102
static void
103
exp_mail_it(struct objcore *oc, uint8_t cmds)
104 1786
{
105 1786
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
106 1786
        assert(oc->refcnt > 0);
107 1786
        AZ(cmds & OC_EF_REFD);
108
109 1786
        Lck_AssertHeld(&exphdl->mtx);
110
111 1786
        if (oc->exp_flags & OC_EF_REFD) {
112 1786
                if (!(oc->exp_flags & OC_EF_POSTED)) {
113 1785
                        if (cmds & OC_EF_REMOVE)
114 281
                                VSTAILQ_INSERT_HEAD(&exphdl->inbox,
115 1785
                                    oc, exp_list);
116 1504
                        else
117 1504
                                VSTAILQ_INSERT_TAIL(&exphdl->inbox,
118 1785
                                    oc, exp_list);
119 1785
                        VSC_C_main->exp_mailed++;
120 1785
                }
121 1786
                oc->exp_flags |= cmds | OC_EF_POSTED;
122 1786
                PTOK(pthread_cond_signal(&exphdl->condvar));
123 1786
        }
124 1786
}
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
EXP_RefNewObjcore(struct objcore *oc)
133 1498
{
134 1498
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
135
136 1498
        Lck_AssertHeld(&oc->objhead->mtx);
137
138 1498
        AZ(oc->exp_flags);
139 1498
        assert(oc->refcnt >= 1);
140 1498
        oc->refcnt++;
141 1498
        oc->exp_flags |= OC_EF_REFD | OC_EF_NEW;
142 1498
}
143
144
145
146
/*--------------------------------------------------------------------
147
 * Call EXP's attention to an oc
148
 */
149
150
void
151
EXP_Remove(struct objcore *oc, const struct objcore *new_oc)
152 482
{
153
154 482
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
155 482
        CHECK_OBJ_ORNULL(new_oc, OBJCORE_MAGIC);
156
157 482
        if (oc->exp_flags & OC_EF_REFD) {
158 282
                Lck_Lock(&exphdl->mtx);
159 282
                if (new_oc != NULL)
160 77
                        VSC_C_main->n_superseded++;
161 282
                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 282
                        exp_mail_it(oc, OC_EF_REMOVE);
169 282
                Lck_Unlock(&exphdl->mtx);
170 282
        }
171 482
}
172
173
/*--------------------------------------------------------------------
174
 * Insert new object.
175
 *
176
 * Caller got a oc->refcnt for us.
177
 */
178
179
void
180
EXP_Insert(struct worker *wrk, struct objcore *oc)
181 1498
{
182 1498
        unsigned remove_race = 0;
183 1498
        struct objcore *tmpoc;
184
185 1498
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
186 1498
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
187
188 1498
        AZ(oc->flags & OC_F_BUSY);
189
190 1498
        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 1498
        assert(oc->refcnt >= 2);
196
197 1498
        ObjSendEvent(wrk, oc, OEV_INSERT);
198
199 1498
        Lck_Lock(&exphdl->mtx);
200 1498
        AN(oc->exp_flags & OC_EF_NEW);
201 1498
        oc->exp_flags &= ~OC_EF_NEW;
202 1498
        AZ(oc->exp_flags & (OC_EF_INSERT | OC_EF_MOVE | OC_EF_POSTED));
203 1498
        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 1498
                exp_mail_it(oc, OC_EF_INSERT | OC_EF_MOVE);
209 1498
        Lck_Unlock(&exphdl->mtx);
210
211 1498
        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 1498
}
220
221
/*--------------------------------------------------------------------
222
 * Reduce object timers
223
 */
224
225
void
226
EXP_Reduce(struct objcore *oc, vtim_real now,
227
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
228 10
{
229
230 10
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
231 10
        assert(oc->refcnt > 0);
232
233 10
        if (!isnan(ttl) && now + ttl - oc->t_origin >= oc->ttl)
234 6
                ttl = NAN;
235 10
        if (!isnan(grace) && grace >= oc->grace)
236 2
                grace = NAN;
237 10
        if (!isnan(keep) && keep >= oc->keep)
238 1
                keep = NAN;
239
240 10
        EXP_Rearm(oc, now, ttl, grace, keep);
241 10
}
242
243
/*--------------------------------------------------------------------
244
 * We have changed one or more of the object timers, tell the exp_thread
245
 *
246
 */
247
248
static inline void
249
apply_timers(struct objcore *oc, vtim_real now,
250
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
251 10
{
252 10
        if (!isnan(ttl))
253 4
                oc->ttl = now + ttl - oc->t_origin;
254 10
        if (!isnan(grace))
255 2
                oc->grace = grace;
256 10
        if (!isnan(keep))
257 2
                oc->keep = keep;
258 10
}
259
260
void
261
EXP_Rearm(struct objcore *oc, vtim_real now,
262
    vtim_dur ttl, vtim_dur grace, vtim_dur keep)
263 10
{
264 10
        vtim_real when;
265
266 10
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
267 10
        assert(oc->refcnt > 0);
268
269 10
        if (oc->flags & OC_F_BUSY) {
270 0
                struct objhead *oh = oc->objhead;
271 0
                uint8_t flags;
272
273 0
                Lck_Lock(&oh->mtx);
274 0
                flags = oc->flags;
275 0
                if (flags & OC_F_BUSY)
276 0
                        apply_timers(oc, now, ttl, grace, keep);
277 0
                Lck_Unlock(&oh->mtx);
278 0
                if (flags & OC_F_BUSY)
279 0
                        return;
280 0
        }
281
282 10
        if (!(oc->exp_flags & OC_EF_REFD))
283 0
                return;
284
285 10
        apply_timers(oc, now, ttl, grace, keep);
286
287 10
        when = EXP_WHEN(oc);
288
289 10
        VSL(SLT_ExpKill, NO_VXID, "EXP_Rearm p=%p E=%.6f e=%.6f f=0x%x", oc,
290 10
            oc->timer_when, when, oc->flags);
291
292 10
        if (when < oc->t_origin || when < oc->timer_when) {
293 6
                Lck_Lock(&exphdl->mtx);
294 6
                if (oc->exp_flags & OC_EF_NEW) {
295
                        /* EXP_Insert has not been called yet, do nothing
296
                         * as the initial insert will execute the move
297
                         * operation. */
298 0
                } else
299 6
                        exp_mail_it(oc, OC_EF_MOVE);
300 6
                Lck_Unlock(&exphdl->mtx);
301 6
        }
302 10
}
303
304
/*--------------------------------------------------------------------
305
 * Handle stuff in the inbox
306
 */
307
308
static void
309
exp_inbox(struct exp_priv *ep, struct objcore *oc, unsigned flags, vtim_real now)
310 1785
{
311
312 1785
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
313 1785
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
314 1785
        assert(oc->refcnt > 0);
315
316 1785
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inbox flg=%x p=%p e=%.6f f=0x%x",
317 1785
            flags, oc, oc->timer_when, oc->flags);
318
319 1785
        if (flags & OC_EF_REMOVE) {
320 281
                if (!(flags & OC_EF_INSERT)) {
321 281
                        assert(oc->timer_idx != VBH_NOIDX);
322 281
                        VBH_delete(ep->heap, oc->timer_idx);
323 281
                }
324 281
                assert(oc->timer_idx == VBH_NOIDX);
325 281
                assert(oc->refcnt > 0);
326 281
                AZ(oc->exp_flags);
327 281
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Removed x=%ju t=%.0f h=%jd",
328 281
                    VXID(ObjGetXID(ep->wrk, oc)), EXP_Ttl(NULL, oc) - now,
329 281
                    (intmax_t)oc->hits);
330 281
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
331 281
                (void)HSH_DerefObjCore(ep->wrk, &oc);
332 281
                return;
333 281
        }
334
335 1504
        if (flags & OC_EF_MOVE) {
336 1504
                oc->timer_when = EXP_WHEN(oc);
337 1504
                ObjSendEvent(ep->wrk, oc, OEV_TTLCHG);
338 1504
        }
339
340 1504
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_When p=%p e=%.6f f=0x%x", oc,
341 1504
            oc->timer_when, flags);
342
343
        /*
344
         * XXX: There are some pathological cases here, were we
345
         * XXX: insert or move an expired object, only to find out
346
         * XXX: the next moment and rip them out again.
347
         */
348
349 1504
        if (flags & OC_EF_INSERT) {
350 1498
                assert(oc->timer_idx == VBH_NOIDX);
351 1498
                VBH_insert(exphdl->heap, oc);
352 1498
                assert(oc->timer_idx != VBH_NOIDX);
353 1498
        } else if (flags & OC_EF_MOVE) {
354 6
                assert(oc->timer_idx != VBH_NOIDX);
355 6
                VBH_reorder(exphdl->heap, oc->timer_idx);
356 6
                assert(oc->timer_idx != VBH_NOIDX);
357 6
        } else {
358 0
                WRONG("Objcore state wrong in inbox");
359 0
        }
360 1504
}
361
362
/*--------------------------------------------------------------------
363
 * Expire stuff from the binheap
364
 */
365
366
static vtim_real
367
exp_expire(struct exp_priv *ep, vtim_real now)
368 5588
{
369 5588
        struct objcore *oc;
370
371 5588
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
372
373 5588
        oc = VBH_root(ep->heap);
374 5588
        if (oc == NULL)
375 2408
                return (now + 355. / 113.);
376 3180
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inspect p=%p e=%.6f f=0x%x", oc,
377 3180
            oc->timer_when - now, oc->flags);
378
379 3180
        CHECK_OBJ(oc, OBJCORE_MAGIC);
380
381
        /* Ready ? */
382 3180
        if (oc->timer_when > now)
383 3040
                return (oc->timer_when);
384
385 140
        VSC_C_main->n_expired++;
386
387 140
        Lck_Lock(&ep->mtx);
388 140
        if (oc->exp_flags & OC_EF_POSTED) {
389 0
                oc->exp_flags |= OC_EF_REMOVE;
390 0
                oc = NULL;
391 140
        } else {
392 140
                oc->exp_flags &= ~OC_EF_REFD;
393 140
        }
394 140
        Lck_Unlock(&ep->mtx);
395 140
        if (oc != NULL) {
396 140
                if (!(oc->flags & OC_F_DYING))
397 140
                        HSH_Kill(oc);
398
399
                /* Remove from binheap */
400 140
                assert(oc->timer_idx != VBH_NOIDX);
401 140
                VBH_delete(ep->heap, oc->timer_idx);
402 140
                assert(oc->timer_idx == VBH_NOIDX);
403
404 140
                CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
405 140
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Expired x=%ju t=%.0f h=%jd",
406 140
                    VXID(ObjGetXID(ep->wrk, oc)), EXP_Ttl(NULL, oc) - now,
407 140
                    (intmax_t)oc->hits);
408 140
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
409 140
                (void)HSH_DerefObjCore(ep->wrk, &oc);
410 140
        }
411 140
        return (0);
412 140
}
413
414
/*--------------------------------------------------------------------
415
 * This thread monitors the root of the binary heap and whenever an
416
 * object expires, accounting also for graceability, it is killed.
417
 */
418
419
static int v_matchproto_(vbh_cmp_t)
420
object_cmp(void *priv, const void *a, const void *b)
421 1309
{
422 1309
        const struct objcore *aa, *bb;
423
424 1309
        (void)priv;
425 1309
        CAST_OBJ_NOTNULL(aa, a, OBJCORE_MAGIC);
426 1309
        CAST_OBJ_NOTNULL(bb, b, OBJCORE_MAGIC);
427 1309
        return (aa->timer_when < bb->timer_when);
428 1309
}
429
430
static void v_matchproto_(vbh_update_t)
431
object_update(void *priv, void *p, unsigned u)
432 2895
{
433 2895
        struct objcore *oc;
434
435 2895
        (void)priv;
436 2895
        CAST_OBJ_NOTNULL(oc, p, OBJCORE_MAGIC);
437 2895
        oc->timer_idx = u;
438 2895
}
439
440
static void * v_matchproto_(bgthread_t)
441
exp_thread(struct worker *wrk, void *priv)
442 1026
{
443 1026
        struct objcore *oc;
444 1026
        vtim_real t = 0, tnext = 0;
445 1026
        struct exp_priv *ep;
446 1026
        unsigned flags = 0;
447
448 1026
        CAST_OBJ_NOTNULL(ep, priv, EXP_PRIV_MAGIC);
449 1026
        ep->wrk = wrk;
450 1026
        VSL_Alloc(&ep->vsl);
451 1026
        AZ(wrk->vsl);
452 1026
        wrk->vsl = &ep->vsl;
453 1026
        ep->heap = VBH_new(NULL, object_cmp, object_update);
454 1026
        AN(ep->heap);
455 8412
        while (exp_shutdown == 0) {
456
457 7386
                Lck_Lock(&ep->mtx);
458 7386
                oc = VSTAILQ_FIRST(&ep->inbox);
459 7386
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
460 7386
                if (oc != NULL) {
461 1785
                        assert(oc->refcnt >= 1);
462 1785
                        assert(oc->exp_flags & OC_EF_POSTED);
463 1785
                        VSTAILQ_REMOVE(&ep->inbox, oc, objcore, exp_list);
464 1785
                        VSC_C_main->exp_received++;
465 1785
                        tnext = 0;
466 1785
                        flags = oc->exp_flags;
467 1785
                        if (flags & OC_EF_REMOVE)
468 281
                                oc->exp_flags = 0;
469 1504
                        else
470 1504
                                oc->exp_flags &= OC_EF_REFD;
471 5601
                } else if (tnext > t) {
472 2786
                        VSL_Flush(&ep->vsl, 0);
473 2786
                        Pool_Sumstat(wrk);
474 2786
                        (void)Lck_CondWaitUntil(&ep->condvar, &ep->mtx, tnext);
475 2786
                }
476 7386
                Lck_Unlock(&ep->mtx);
477
478 7386
                t = VTIM_real();
479
480 7386
                if (oc != NULL)
481 1785
                        exp_inbox(ep, oc, flags, t);
482 5601
                else
483 5601
                        tnext = exp_expire(ep, t);
484 7386
        }
485 1026
        wrk->vsl = NULL;
486 1026
        VSL_Free(&ep->vsl);
487 1026
        return (NULL);
488 1026
}
489
490
/*--------------------------------------------------------------------*/
491
492
void
493
EXP_Init(void)
494 1026
{
495 1026
        struct exp_priv *ep;
496 1026
        pthread_t pt;
497
498 1026
        ALLOC_OBJ(ep, EXP_PRIV_MAGIC);
499 1026
        AN(ep);
500
501 1026
        Lck_New(&ep->mtx, lck_exp);
502 1026
        PTOK(pthread_cond_init(&ep->condvar, NULL));
503 1026
        VSTAILQ_INIT(&ep->inbox);
504 1026
        WRK_BgThread(&pt, "cache-exp", exp_thread, ep);
505 1026
        ep->thread = pt;
506 1026
        exphdl = ep;
507 1026
}
508
509
void
510
EXP_Shutdown(void)
511 1013
{
512 1013
        struct exp_priv *ep = exphdl;
513 1013
        void *status;
514
515 1013
        Lck_Lock(&ep->mtx);
516 1013
        exp_shutdown = 1;
517 1013
        PTOK(pthread_cond_signal(&ep->condvar));
518 1013
        Lck_Unlock(&ep->mtx);
519
520 1013
        AN(ep->thread);
521 1013
        PTOK(pthread_join(ep->thread, &status));
522 1013
        AZ(status);
523 1013
        memset(&ep->thread, 0, sizeof ep->thread);
524
525
        /* XXX could cleanup more - not worth it for now */
526 1013
}