varnish-cache/bin/varnishd/cache/cache_expire.c
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2011 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
 * LRU and object timer handling.
30
 *
31
 */
32
33
#include "config.h"
34
35
#include <stdlib.h>
36
37
#include "cache_varnishd.h"
38
#include "cache_objhead.h"
39
40
#include "binary_heap.h"
41
#include "vtim.h"
42
43
struct exp_priv {
44
        unsigned                        magic;
45
#define EXP_PRIV_MAGIC                  0x9db22482
46
        /* shared */
47
        struct lock                     mtx;
48
        VSTAILQ_HEAD(,objcore)          inbox;
49
        pthread_cond_t                  condvar;
50
51
        /* owned by exp thread */
52
        struct worker                   *wrk;
53
        struct vsl_log                  vsl;
54
        struct binheap                  *heap;
55
};
56
57
static struct exp_priv *exphdl;
58
59
/*--------------------------------------------------------------------
60
 * Calculate an object's effective ttl time, taking req.ttl into account
61
 * if it is available.
62
 */
63
64
double
65 1900
EXP_Ttl(const struct req *req, const struct objcore *oc)
66
{
67
        double r;
68
69 1900
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
70
71 1900
        r = oc->ttl;
72 1900
        if (req != NULL && req->d_ttl > 0. && req->d_ttl < r)
73 14
                r = req->d_ttl;
74 1900
        return (oc->t_origin + r);
75
}
76
77
/*--------------------------------------------------------------------
78
 * Calculate an object's effective ttl+grace time, taking req.grace into
79
 * account if it is available.
80
 */
81
82
double
83 82
EXP_Ttl_grace(const struct req *req, const struct objcore *oc)
84
{
85
        double g;
86
87 82
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
88
89 82
        g = oc->grace;
90 82
        if (req != NULL && req->d_grace >= 0. && req->d_grace < g)
91 6
                g = req->d_grace;
92 82
        return (EXP_Ttl(req, oc) + g);
93
}
94
95
/*--------------------------------------------------------------------
96
 * Post an objcore to the exp_thread's inbox.
97
 */
98
99
static void
100 2570
exp_mail_it(struct objcore *oc, uint8_t cmds)
101
{
102 2570
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
103 2570
        assert(oc->refcnt > 0);
104
105 2570
        Lck_Lock(&exphdl->mtx);
106 2570
        if ((cmds | oc->exp_flags) & OC_EF_REFD) {
107 2570
                if (!(oc->exp_flags & OC_EF_POSTED)) {
108 2570
                        if (cmds & OC_EF_REMOVE)
109 200
                                VSTAILQ_INSERT_HEAD(&exphdl->inbox,
110
                                    oc, exp_list);
111
                        else
112 2370
                                VSTAILQ_INSERT_TAIL(&exphdl->inbox,
113
                                    oc, exp_list);
114
                }
115 2570
                oc->exp_flags |= cmds | OC_EF_POSTED;
116 2570
                AN(oc->exp_flags & OC_EF_REFD);
117 2570
                VSC_C_main->exp_mailed++;
118 2570
                AZ(pthread_cond_signal(&exphdl->condvar));
119
        }
120 2570
        Lck_Unlock(&exphdl->mtx);
121 2570
}
122
123
/*--------------------------------------------------------------------
124
 * Call EXP's attention to a an oc
125
 */
126
127
void
128 506
EXP_Remove(struct objcore *oc)
129
{
130
131 506
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
132 506
        if (oc->exp_flags & OC_EF_REFD)
133 200
                exp_mail_it(oc, OC_EF_REMOVE);
134 506
}
135
136
/*--------------------------------------------------------------------
137
 * Insert new object.
138
 *
139
 * Caller got a oc->refcnt for us.
140
 */
141
142
void
143 2206
EXP_Insert(struct worker *wrk, struct objcore *oc)
144
{
145
146 2206
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
147 2206
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
148 2206
        assert(oc->refcnt >= 2);
149
150 2206
        AZ(oc->exp_flags & (OC_EF_INSERT | OC_EF_MOVE));
151 2206
        AZ(oc->flags & OC_F_DYING);
152
153 2206
        ObjSendEvent(wrk, oc, OEV_INSERT);
154 2206
        exp_mail_it(oc, OC_EF_INSERT | OC_EF_REFD | OC_EF_MOVE);
155 2206
}
156
157
/*--------------------------------------------------------------------
158
 * We have changed one or more of the object timers, tell the exp_thread
159
 *
160
 */
161
162
void
163 164
EXP_Rearm(struct objcore *oc, double now, double ttl, double grace, double keep)
164
{
165
        double when;
166
167 164
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
168 164
        assert(oc->refcnt > 0);
169
170 164
        if (!(oc->exp_flags & OC_EF_REFD))
171 0
                return;
172
173 164
        if (!isnan(ttl))
174 164
                oc->ttl = now + ttl - oc->t_origin;
175 164
        if (!isnan(grace))
176 162
                oc->grace = grace;
177 164
        if (!isnan(keep))
178 162
                oc->keep = keep;
179
180 164
        when = EXP_WHEN(oc);
181
182 164
        VSL(SLT_ExpKill, 0, "EXP_Rearm p=%p E=%.6f e=%.6f f=0x%x", oc,
183 164
            oc->timer_when, when, oc->flags);
184
185 164
        if (when < oc->t_origin || when < oc->timer_when)
186 164
                exp_mail_it(oc, OC_EF_MOVE);
187
}
188
189
/*--------------------------------------------------------------------
190
 * Handle stuff in the inbox
191
 */
192
193
static void
194 2570
exp_inbox(struct exp_priv *ep, struct objcore *oc, unsigned flags)
195
{
196
197 2570
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
198 2570
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
199 2570
        assert(oc->refcnt > 0);
200
201 5140
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inbox flg=%x p=%p e=%.6f f=0x%x",
202 5140
            flags, oc, oc->timer_when, oc->flags);
203
204 2570
        if (flags & OC_EF_REMOVE) {
205 200
                if (!(flags & OC_EF_INSERT)) {
206 200
                        assert(oc->timer_idx != BINHEAP_NOIDX);
207 200
                        binheap_delete(ep->heap, oc->timer_idx);
208
                }
209 200
                assert(oc->timer_idx == BINHEAP_NOIDX);
210 200
                assert(oc->refcnt > 0);
211 200
                AZ(oc->exp_flags);
212 200
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
213 200
                (void)HSH_DerefObjCore(ep->wrk, &oc, 0);
214 200
                return;
215
        }
216
217 2370
        if (flags & OC_EF_MOVE) {
218 2370
                oc->timer_when = EXP_WHEN(oc);
219 2370
                ObjSendEvent(ep->wrk, oc, OEV_TTLCHG);
220
        }
221
222 2370
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_When p=%p e=%.6f f=0x%x", oc,
223 2370
            oc->timer_when, flags);
224
225
        /*
226
         * XXX: There are some pathological cases here, were we
227
         * XXX: insert or move an expired object, only to find out
228
         * XXX: the next moment and rip them out again.
229
         */
230
231 2370
        if (flags & OC_EF_INSERT) {
232 2206
                assert(oc->timer_idx == BINHEAP_NOIDX);
233 2206
                binheap_insert(exphdl->heap, oc);
234 2206
                assert(oc->timer_idx != BINHEAP_NOIDX);
235 164
        } else if (flags & OC_EF_MOVE) {
236 164
                assert(oc->timer_idx != BINHEAP_NOIDX);
237 164
                binheap_reorder(exphdl->heap, oc->timer_idx);
238 164
                assert(oc->timer_idx != BINHEAP_NOIDX);
239
        } else {
240 0
                WRONG("Objcore state wrong in inbox");
241
        }
242
}
243
244
/*--------------------------------------------------------------------
245
 * Expire stuff from the binheap
246
 */
247
248
static double
249 6818
exp_expire(struct exp_priv *ep, double now)
250
{
251
        struct objcore *oc;
252
253 6818
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
254
255 6818
        oc = binheap_root(ep->heap);
256 6818
        if (oc == NULL)
257 2988
                return (now + 355./113.);
258 7660
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_expire p=%p e=%.6f f=0x%x", oc,
259 7660
            oc->timer_when - now, oc->flags);
260
261 3830
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
262
263
        /* Ready ? */
264 3830
        if (oc->timer_when > now)
265 3528
                return (oc->timer_when);
266
267 302
        VSC_C_main->n_expired++;
268
269 302
        Lck_Lock(&ep->mtx);
270 302
        if (oc->exp_flags & OC_EF_POSTED) {
271 0
                oc->exp_flags |= OC_EF_REMOVE;
272 0
                oc = NULL;
273
        } else {
274 302
                oc->exp_flags &= ~OC_EF_REFD;
275
        }
276 302
        Lck_Unlock(&ep->mtx);
277 302
        if (oc != NULL) {
278 302
                if (!(oc->flags & OC_F_DYING))
279 302
                        HSH_Kill(oc);
280
281
                /* Remove from binheap */
282 302
                assert(oc->timer_idx != BINHEAP_NOIDX);
283 302
                binheap_delete(ep->heap, oc->timer_idx);
284 302
                assert(oc->timer_idx == BINHEAP_NOIDX);
285
286 302
                CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
287 302
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Expired x=%u t=%.0f",
288 302
                    ObjGetXID(ep->wrk, oc), EXP_Ttl(NULL, oc) - now);
289 302
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
290 302
                (void)HSH_DerefObjCore(ep->wrk, &oc, 0);
291
        }
292 302
        return (0);
293
}
294
295
/*--------------------------------------------------------------------
296
 * This thread monitors the root of the binary heap and whenever an
297
 * object expires, accounting also for graceability, it is killed.
298
 */
299
300
static int v_matchproto_(binheap_cmp_t)
301 2790
object_cmp(void *priv, const void *a, const void *b)
302
{
303
        const struct objcore *aa, *bb;
304
305
        (void)priv;
306 2790
        CAST_OBJ_NOTNULL(aa, a, OBJCORE_MAGIC);
307 2790
        CAST_OBJ_NOTNULL(bb, b, OBJCORE_MAGIC);
308 2790
        return (aa->timer_when < bb->timer_when);
309
}
310
311
static void v_matchproto_(binheap_update_t)
312 4740
object_update(void *priv, void *p, unsigned u)
313
{
314
        struct objcore *oc;
315
316
        (void)priv;
317 4740
        CAST_OBJ_NOTNULL(oc, p, OBJCORE_MAGIC);
318 4740
        oc->timer_idx = u;
319 4740
}
320
321
static void * v_matchproto_(bgthread_t)
322 1376
exp_thread(struct worker *wrk, void *priv)
323
{
324
        struct objcore *oc;
325 1376
        double t = 0, tnext = 0;
326
        struct exp_priv *ep;
327 1376
        unsigned flags = 0;
328
329 1376
        CAST_OBJ_NOTNULL(ep, priv, EXP_PRIV_MAGIC);
330 1376
        ep->wrk = wrk;
331 1376
        VSL_Setup(&ep->vsl, NULL, 0);
332 1376
        ep->heap = binheap_new(NULL, object_cmp, object_update);
333 1376
        AN(ep->heap);
334
        while (1) {
335
336 20152
                Lck_Lock(&ep->mtx);
337 10764
                oc = VSTAILQ_FIRST(&ep->inbox);
338 10764
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
339 10764
                if (oc != NULL) {
340 2570
                        assert(oc->refcnt >= 1);
341 2570
                        VSTAILQ_REMOVE(&ep->inbox, oc, objcore, exp_list);
342 2570
                        VSC_C_main->exp_received++;
343 2570
                        tnext = 0;
344 2570
                        flags = oc->exp_flags;
345 2570
                        if (flags & OC_EF_REMOVE)
346 200
                                oc->exp_flags = 0;
347
                        else
348 2370
                                oc->exp_flags &= OC_EF_REFD;
349 8194
                } else if (tnext > t) {
350 4111
                        VSL_Flush(&ep->vsl, 0);
351 4111
                        Pool_Sumstat(wrk);
352 4111
                        (void)Lck_CondWait(&ep->condvar, &ep->mtx, tnext);
353
                }
354 9388
                Lck_Unlock(&ep->mtx);
355
356 9388
                t = VTIM_real();
357
358 9388
                if (oc != NULL)
359 2570
                        exp_inbox(ep, oc, flags);
360
                else
361 6818
                        tnext = exp_expire(ep, t);
362
        }
363
        NEEDLESS(return NULL);
364
}
365
366
/*--------------------------------------------------------------------*/
367
368
void
369 1376
EXP_Init(void)
370
{
371
        struct exp_priv *ep;
372
        pthread_t pt;
373
374 1376
        ALLOC_OBJ(ep, EXP_PRIV_MAGIC);
375 1376
        AN(ep);
376
377 1376
        Lck_New(&ep->mtx, lck_exp);
378 1376
        AZ(pthread_cond_init(&ep->condvar, NULL));
379 1376
        VSTAILQ_INIT(&ep->inbox);
380 1376
        exphdl = ep;
381 1376
        WRK_BgThread(&pt, "cache-exp", exp_thread, ep);
382 1376
}