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 943
EXP_Ttl(const struct req *req, const struct objcore *oc)
66
{
67
        double r;
68
69 943
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
70
71 943
        r = oc->ttl;
72 943
        if (req != NULL && req->d_ttl > 0. && req->d_ttl < r)
73 8
                r = req->d_ttl;
74 943
        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 40
EXP_Ttl_grace(const struct req *req, const struct objcore *oc)
84
{
85
        double g;
86
87 40
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
88
89 40
        g = oc->grace;
90 40
        if (req != NULL && req->d_grace >= 0. && req->d_grace < g)
91 3
                g = req->d_grace;
92 40
        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 1264
exp_mail_it(struct objcore *oc, uint8_t cmds)
101
{
102 1264
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
103 1264
        assert(oc->refcnt > 0);
104
105 1264
        Lck_Lock(&exphdl->mtx);
106 1264
        if ((cmds | oc->exp_flags) & OC_EF_REFD) {
107 1264
                if (!(oc->exp_flags & OC_EF_POSTED)) {
108 1264
                        if (cmds & OC_EF_REMOVE)
109 84
                                VSTAILQ_INSERT_HEAD(&exphdl->inbox,
110
                                    oc, exp_list);
111
                        else
112 1180
                                VSTAILQ_INSERT_TAIL(&exphdl->inbox,
113
                                    oc, exp_list);
114
                }
115 1264
                oc->exp_flags |= cmds | OC_EF_POSTED;
116 1264
                AN(oc->exp_flags & OC_EF_REFD);
117 1264
                VSC_C_main->exp_mailed++;
118 1264
                AZ(pthread_cond_signal(&exphdl->condvar));
119
        }
120 1264
        Lck_Unlock(&exphdl->mtx);
121 1264
}
122
123
/*--------------------------------------------------------------------
124
 * Call EXP's attention to a an oc
125
 */
126
127
void
128 237
EXP_Remove(struct objcore *oc)
129
{
130
131 237
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
132 237
        if (oc->exp_flags & OC_EF_REFD)
133 84
                exp_mail_it(oc, OC_EF_REMOVE);
134 237
}
135
136
/*--------------------------------------------------------------------
137
 * Insert new object.
138
 *
139
 * Caller got a oc->refcnt for us.
140
 */
141
142
void
143 1098
EXP_Insert(struct worker *wrk, struct objcore *oc)
144
{
145
146 1098
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
147 1098
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
148 1098
        assert(oc->refcnt >= 2);
149
150 1098
        AZ(oc->exp_flags & (OC_EF_INSERT | OC_EF_MOVE));
151 1098
        AZ(oc->flags & OC_F_DYING);
152
153 1098
        ObjSendEvent(wrk, oc, OEV_INSERT);
154 1098
        exp_mail_it(oc, OC_EF_INSERT | OC_EF_REFD | OC_EF_MOVE);
155 1098
}
156
157
/*--------------------------------------------------------------------
158
 * We have changed one or more of the object timers, tell the exp_thread
159
 *
160
 */
161
162
void
163 82
EXP_Rearm(struct objcore *oc, double now, double ttl, double grace, double keep)
164
{
165
        double when;
166
167 82
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
168 82
        assert(oc->refcnt > 0);
169
170 82
        if (!(oc->exp_flags & OC_EF_REFD))
171 0
                return;
172
173 82
        if (!isnan(ttl))
174 82
                oc->ttl = now + ttl - oc->t_origin;
175 82
        if (!isnan(grace))
176 81
                oc->grace = grace;
177 82
        if (!isnan(keep))
178 81
                oc->keep = keep;
179
180 82
        when = EXP_WHEN(oc);
181
182 82
        VSL(SLT_ExpKill, 0, "EXP_Rearm p=%p E=%.9f e=%.9f f=0x%x", oc,
183 82
            oc->timer_when, when, oc->flags);
184
185 82
        if (when < oc->t_origin || when < oc->timer_when)
186 82
                exp_mail_it(oc, OC_EF_MOVE);
187
}
188
189
/*--------------------------------------------------------------------
190
 * Handle stuff in the inbox
191
 */
192
193
static void
194 1264
exp_inbox(struct exp_priv *ep, struct objcore *oc, unsigned flags)
195
{
196
197 1264
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
198 1264
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
199 1264
        assert(oc->refcnt > 0);
200
201 2528
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_Inbox flg=%x p=%p e=%.9f f=0x%x",
202 2528
            flags, oc, oc->timer_when, oc->flags);
203
204 1264
        if (flags & OC_EF_REMOVE) {
205 84
                if (!(flags & OC_EF_INSERT)) {
206 84
                        assert(oc->timer_idx != BINHEAP_NOIDX);
207 84
                        binheap_delete(ep->heap, oc->timer_idx);
208
                }
209 84
                assert(oc->timer_idx == BINHEAP_NOIDX);
210 84
                assert(oc->refcnt > 0);
211 84
                AZ(oc->exp_flags);
212 84
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
213 84
                (void)HSH_DerefObjCore(ep->wrk, &oc, 0);
214 84
                return;
215
        }
216
217 1180
        if (flags & OC_EF_MOVE) {
218 1180
                oc->timer_when = EXP_WHEN(oc);
219 1180
                ObjSendEvent(ep->wrk, oc, OEV_TTLCHG);
220
        }
221
222 1180
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_When p=%p e=%.9f f=0x%x", oc,
223 1180
            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 1180
        if (flags & OC_EF_INSERT) {
232 1098
                assert(oc->timer_idx == BINHEAP_NOIDX);
233 1098
                binheap_insert(exphdl->heap, oc);
234 1098
                assert(oc->timer_idx != BINHEAP_NOIDX);
235 82
        } else if (flags & OC_EF_MOVE) {
236 82
                assert(oc->timer_idx != BINHEAP_NOIDX);
237 82
                binheap_reorder(exphdl->heap, oc->timer_idx);
238 82
                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 3334
exp_expire(struct exp_priv *ep, double now)
250
{
251
        struct objcore *oc;
252
253 3334
        CHECK_OBJ_NOTNULL(ep, EXP_PRIV_MAGIC);
254
255 3334
        oc = binheap_root(ep->heap);
256 3334
        if (oc == NULL)
257 1469
                return (now + 355./113.);
258 3730
        VSLb(&ep->vsl, SLT_ExpKill, "EXP_expire p=%p e=%.9f f=0x%x", oc,
259 3730
            oc->timer_when - now, oc->flags);
260
261 1865
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
262
263
        /* Ready ? */
264 1865
        if (oc->timer_when > now)
265 1714
                return (oc->timer_when);
266
267 151
        VSC_C_main->n_expired++;
268
269 151
        Lck_Lock(&ep->mtx);
270 151
        if (oc->exp_flags & OC_EF_POSTED) {
271 0
                oc->exp_flags |= OC_EF_REMOVE;
272 0
                oc = NULL;
273
        } else {
274 151
                oc->exp_flags &= ~OC_EF_REFD;
275
        }
276 151
        Lck_Unlock(&ep->mtx);
277 151
        if (oc != NULL) {
278 151
                if (!(oc->flags & OC_F_DYING))
279 151
                        HSH_Kill(oc);
280
281
                /* Remove from binheap */
282 151
                assert(oc->timer_idx != BINHEAP_NOIDX);
283 151
                binheap_delete(ep->heap, oc->timer_idx);
284 151
                assert(oc->timer_idx == BINHEAP_NOIDX);
285
286 151
                CHECK_OBJ_NOTNULL(oc->objhead, OBJHEAD_MAGIC);
287 151
                VSLb(&ep->vsl, SLT_ExpKill, "EXP_Expired x=%u t=%.0f",
288 151
                    ObjGetXID(ep->wrk, oc), EXP_Ttl(NULL, oc) - now);
289 151
                ObjSendEvent(ep->wrk, oc, OEV_EXPIRE);
290 151
                (void)HSH_DerefObjCore(ep->wrk, &oc, 0);
291
        }
292 151
        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 1397
object_cmp(void *priv, const void *a, const void *b)
302
{
303
        const struct objcore *aa, *bb;
304
305
        (void)priv;
306 1397
        CAST_OBJ_NOTNULL(aa, a, OBJCORE_MAGIC);
307 1397
        CAST_OBJ_NOTNULL(bb, b, OBJCORE_MAGIC);
308 1397
        return (aa->timer_when < bb->timer_when);
309
}
310
311
static void v_matchproto_(binheap_update_t)
312 2335
object_update(void *priv, void *p, unsigned u)
313
{
314
        struct objcore *oc;
315
316
        (void)priv;
317 2335
        CAST_OBJ_NOTNULL(oc, p, OBJCORE_MAGIC);
318 2335
        oc->timer_idx = u;
319 2335
}
320
321
static void * v_matchproto_(bgthread_t)
322 685
exp_thread(struct worker *wrk, void *priv)
323
{
324
        struct objcore *oc;
325 685
        double t = 0, tnext = 0;
326
        struct exp_priv *ep;
327 685
        unsigned flags = 0;
328
329 685
        CAST_OBJ_NOTNULL(ep, priv, EXP_PRIV_MAGIC);
330 685
        ep->wrk = wrk;
331 685
        VSL_Setup(&ep->vsl, NULL, 0);
332 685
        ep->heap = binheap_new(NULL, object_cmp, object_update);
333 685
        AN(ep->heap);
334
        while (1) {
335
336 9881
                Lck_Lock(&ep->mtx);
337 5283
                oc = VSTAILQ_FIRST(&ep->inbox);
338 5283
                CHECK_OBJ_ORNULL(oc, OBJCORE_MAGIC);
339 5283
                if (oc != NULL) {
340 1264
                        assert(oc->refcnt >= 1);
341 1264
                        VSTAILQ_REMOVE(&ep->inbox, oc, objcore, exp_list);
342 1264
                        VSC_C_main->exp_received++;
343 1264
                        tnext = 0;
344 1264
                        flags = oc->exp_flags;
345 1264
                        if (flags & OC_EF_REMOVE)
346 84
                                oc->exp_flags = 0;
347
                        else
348 1180
                                oc->exp_flags &= OC_EF_REFD;
349 4019
                } else if (tnext > t) {
350 2006
                        VSL_Flush(&ep->vsl, 0);
351 2006
                        Pool_Sumstat(wrk);
352 2006
                        (void)Lck_CondWait(&ep->condvar, &ep->mtx, tnext);
353
                }
354 4598
                Lck_Unlock(&ep->mtx);
355
356 4598
                t = VTIM_real();
357
358 4598
                if (oc != NULL)
359 1264
                        exp_inbox(ep, oc, flags);
360
                else
361 3334
                        tnext = exp_expire(ep, t);
362
        }
363
        NEEDLESS(return NULL);
364
}
365
366
/*--------------------------------------------------------------------*/
367
368
void
369 685
EXP_Init(void)
370
{
371
        struct exp_priv *ep;
372
        pthread_t pt;
373
374 685
        ALLOC_OBJ(ep, EXP_PRIV_MAGIC);
375 685
        AN(ep);
376
377 685
        Lck_New(&ep->mtx, lck_exp);
378 685
        AZ(pthread_cond_init(&ep->condvar, NULL));
379 685
        VSTAILQ_INIT(&ep->inbox);
380 685
        exphdl = ep;
381 685
        WRK_BgThread(&pt, "cache-exp", exp_thread, ep);
382 685
}