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