GCOV - Varnish Cache


/*-
 * Copyright (c) 2007-2015 Varnish Software AS
 * All rights reserved.
 *
 * Author: Dag-Erling Smørgav <des@des.no>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Least-Recently-Used logic for freeing space in stevedores.
 */

#include "config.h"

#include <stdlib.h>

#include "cache/cache_varnishd.h"
#include "cache/cache_objhead.h"

#include "storage/storage.h"

struct lru {
        unsigned                magic;
#define LRU_MAGIC               0x3fec7bb0
        VTAILQ_HEAD(,objcore)   lru_head;
        struct lock             mtx;
};

static struct lru *
lru_get(const struct objcore *oc)
{
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->stobj->stevedore, STEVEDORE_MAGIC);
        CHECK_OBJ_NOTNULL(oc->stobj->stevedore->lru, LRU_MAGIC);
        return (oc->stobj->stevedore->lru);
}

struct lru *
LRU_Alloc(void)
{
        struct lru *lru;

        ALLOC_OBJ(lru, LRU_MAGIC);
        AN(lru);
        VTAILQ_INIT(&lru->lru_head);
        Lck_New(&lru->mtx, lck_lru);
        return (lru);
}

void
LRU_Free(struct lru **pp)
{
        struct lru *lru;

        TAKE_OBJ_NOTNULL(lru, pp, LRU_MAGIC);
        Lck_Lock(&lru->mtx);
        AN(VTAILQ_EMPTY(&lru->lru_head));
        Lck_Unlock(&lru->mtx);
        Lck_Delete(&lru->mtx);
        FREE_OBJ(lru);
}

void
LRU_Add(struct objcore *oc, vtim_real now)
{
        struct lru *lru;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);

        if (oc->flags & OC_F_PRIVATE)
                return;

        AZ(oc->boc);
        AN(isnan(oc->last_lru));
        AZ(isnan(now));
        lru = lru_get(oc);
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
        Lck_Lock(&lru->mtx);
        VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
        oc->last_lru = now;
        AZ(isnan(oc->last_lru));
        Lck_Unlock(&lru->mtx);
}

void
LRU_Remove(struct objcore *oc)
{
        struct lru *lru;

        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);

        if (oc->flags & OC_F_PRIVATE)
                return;

        AZ(oc->boc);
        lru = lru_get(oc);
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
        Lck_Lock(&lru->mtx);
        AZ(isnan(oc->last_lru));
        VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
        oc->last_lru = NAN;
        Lck_Unlock(&lru->mtx);
}

void v_matchproto_(objtouch_f)
LRU_Touch(struct worker *wrk, struct objcore *oc, vtim_real now)
{
        struct lru *lru;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);

        if (oc->flags & OC_F_PRIVATE || isnan(oc->last_lru))
                return;

        /*
         * To avoid the exphdl->mtx becoming a hotspot, we only
         * attempt to move objects if they have not been moved
         * recently and if the lock is available.  This optimization
         * obviously leaves the LRU list imperfectly sorted.
         */

        if (now - oc->last_lru < cache_param->lru_interval)
                return;

        lru = lru_get(oc);
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);

        if (Lck_Trylock(&lru->mtx))
                return;

        if (!isnan(oc->last_lru)) {
                VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
                VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
                VSC_C_main->n_lru_moved++;
                oc->last_lru = now;
        }
        Lck_Unlock(&lru->mtx);
}

/*--------------------------------------------------------------------
 * Attempt to make space by nuking the oldest object on the LRU list
 * which isn't in use.
 * Returns: 1: did, 0: didn't;
 */

int
LRU_NukeOne(struct worker *wrk, struct lru *lru)
{
        struct objcore *oc, *oc2;

        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);

        if (wrk->strangelove-- <= 0) {
                VSLb(wrk->vsl, SLT_ExpKill, "LRU reached nuke_limit");
                VSC_C_main->n_lru_limited++;
                return (0);
        }

        /* Find the first currently unused object on the LRU.  */
        Lck_Lock(&lru->mtx);
        VTAILQ_FOREACH_SAFE(oc, &lru->lru_head, lru_list, oc2) {
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
                AZ(isnan(oc->last_lru));

                VSLb(wrk->vsl, SLT_ExpKill, "LRU_Cand p=%p f=0x%x r=%d",
                    oc, oc->flags, oc->refcnt);

                if (HSH_Snipe(wrk, oc)) {
                        VSC_C_main->n_lru_nuked++; // XXX per lru ?
                        VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
                        VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
                        break;
                }
        }
        Lck_Unlock(&lru->mtx);

        if (oc == NULL) {
                VSLb(wrk->vsl, SLT_ExpKill, "LRU_Fail");
                return (0);
        }

        /* XXX: We could grab and return one storage segment to our caller */
        ObjSlim(wrk, oc);

        VSLb(wrk->vsl, SLT_ExpKill, "LRU xid=%ju", VXID(ObjGetXID(wrk, oc)));
        (void)HSH_DerefObjCore(wrk, &oc, 0);    // Ref from HSH_Snipe
        return (1);
}

		varnish-cache/bin/varnishd/storage/storage_lru.c
0		/*-
1		* Copyright (c) 2007-2015 Varnish Software AS
2		* All rights reserved.
3		*
4		* Author: Dag-Erling Smørgav <des@des.no>
5		*
6		* SPDX-License-Identifier: BSD-2-Clause
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		* Least-Recently-Used logic for freeing space in stevedores.
30		*/
31
32		#include "config.h"
33
34		#include <stdlib.h>
35
36		#include "cache/cache_varnishd.h"
37		#include "cache/cache_objhead.h"
38
39		#include "storage/storage.h"
40
41		struct lru {
42		unsigned magic;
43		#define LRU_MAGIC 0x3fec7bb0
44		VTAILQ_HEAD(,objcore) lru_head;
45		struct lock mtx;
46		};
47
48		static struct lru *
49	70258	lru_get(const struct objcore *oc)
50		{
51	70258	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
52	70258	CHECK_OBJ_NOTNULL(oc->stobj->stevedore, STEVEDORE_MAGIC);
53	70258	CHECK_OBJ_NOTNULL(oc->stobj->stevedore->lru, LRU_MAGIC);
54	70258	return (oc->stobj->stevedore->lru);
55		}
56
57		struct lru *
58	72142	LRU_Alloc(void)
59		{
60		struct lru *lru;
61
62	72142	ALLOC_OBJ(lru, LRU_MAGIC);
63	72142	AN(lru);
64	72142	VTAILQ_INIT(&lru->lru_head);
65	72142	Lck_New(&lru->mtx, lck_lru);
66	72142	return (lru);
67		}
68
69		void
70	0	LRU_Free(struct lru **pp)
71		{
72		struct lru *lru;
73
74	0	TAKE_OBJ_NOTNULL(lru, pp, LRU_MAGIC);
75	0	Lck_Lock(&lru->mtx);
76	0	AN(VTAILQ_EMPTY(&lru->lru_head));
77	0	Lck_Unlock(&lru->mtx);
78	0	Lck_Delete(&lru->mtx);
79	0	FREE_OBJ(lru);
80	0	}
81
82		void
83	109559	LRU_Add(struct objcore *oc, vtim_real now)
84		{
85		struct lru *lru;
86
87	109559	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
88
89	109559	if (oc->flags & OC_F_PRIVATE)
90	55039	return;
91
92	54520	AZ(oc->boc);
93	54520	AN(isnan(oc->last_lru));
94	54520	AZ(isnan(now));
95	54520	lru = lru_get(oc);
96	54520	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
97	54520	Lck_Lock(&lru->mtx);
98	54520	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
99	54520	oc->last_lru = now;
100	54520	AZ(isnan(oc->last_lru));
101	54520	Lck_Unlock(&lru->mtx);
102	109559	}
103
104		void
105	69423	LRU_Remove(struct objcore *oc)
106		{
107		struct lru *lru;
108
109	69423	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
110
111	69423	if (oc->flags & OC_F_PRIVATE)
112	55040	return;
113
114	14383	AZ(oc->boc);
115	14383	lru = lru_get(oc);
116	14383	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
117	14383	Lck_Lock(&lru->mtx);
118	14383	AZ(isnan(oc->last_lru));
119	14383	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
120	14383	oc->last_lru = NAN;
121	14383	Lck_Unlock(&lru->mtx);
122	69423	}
123
124		void v_matchproto_(objtouch_f)
125	125786	LRU_Touch(struct worker wrk, struct objcore oc, vtim_real now)
126		{
127		struct lru *lru;
128
129	125786	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
130	125786	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
131
132	125786	if (oc->flags & OC_F_PRIVATE \|\| isnan(oc->last_lru))
133	55040	return;
134
135		/*
136		* To avoid the exphdl->mtx becoming a hotspot, we only
137		* attempt to move objects if they have not been moved
138		* recently and if the lock is available. This optimization
139		* obviously leaves the LRU list imperfectly sorted.
140		*/
141
142	70746	if (now - oc->last_lru < cache_param->lru_interval)
143	69384	return;
144
145	1362	lru = lru_get(oc);
146	1362	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
147
148	1362	if (Lck_Trylock(&lru->mtx))
149	1	return;
150
151	1361	if (!isnan(oc->last_lru)) {
152	1361	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
153	1361	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
154	1361	VSC_C_main->n_lru_moved++;
155	1361	oc->last_lru = now;
156	1361	}
157	1361	Lck_Unlock(&lru->mtx);
158	125786	}
159
160		/*--------------------------------------------------------------------
161		* Attempt to make space by nuking the oldest object on the LRU list
162		* which isn't in use.
163		* Returns: 1: did, 0: didn't;
164		*/
165
166		int
167	1080	LRU_NukeOne(struct worker wrk, struct lru lru)
168		{
169		struct objcore oc, oc2;
170
171	1080	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
172	1080	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
173
174	1080	if (wrk->strangelove-- <= 0) {
175	520	VSLb(wrk->vsl, SLT_ExpKill, "LRU reached nuke_limit");
176	520	VSC_C_main->n_lru_limited++;
177	520	return (0);
178		}
179
180		/* Find the first currently unused object on the LRU. */
181	560	Lck_Lock(&lru->mtx);
182	560	VTAILQ_FOREACH_SAFE(oc, &lru->lru_head, lru_list, oc2) {
183	440	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
184	440	AZ(isnan(oc->last_lru));
185
186	880	VSLb(wrk->vsl, SLT_ExpKill, "LRU_Cand p=%p f=0x%x r=%d",
187	440	oc, oc->flags, oc->refcnt);
188
189	440	if (HSH_Snipe(wrk, oc)) {
190	440	VSC_C_main->n_lru_nuked++; // XXX per lru ?
191	440	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
192	440	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
193	440	break;
194		}
195	0	}
196	560	Lck_Unlock(&lru->mtx);
197
198	560	if (oc == NULL) {
199	120	VSLb(wrk->vsl, SLT_ExpKill, "LRU_Fail");
200	120	return (0);
201		}
202
203		/* XXX: We could grab and return one storage segment to our caller */
204	440	ObjSlim(wrk, oc);
205
206	440	VSLb(wrk->vsl, SLT_ExpKill, "LRU xid=%ju", VXID(ObjGetXID(wrk, oc)));
207	440	(void)HSH_DerefObjCore(wrk, &oc, 0); // Ref from HSH_Snipe
208	440	return (1);
209	1080	}