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_int.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);
}

/*
 * LRU_Free requires the LRU list to be drained. This is not actually used
 * in-tree, but by external storage. Please do not remove, this is not dead code
 */
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|OC_F_FAILED))
                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|OC_F_FAILED))
                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|OC_F_FAILED) || 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(oc->flags & (OC_F_PRIVATE|OC_F_FAILED));
                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);       // Ref from HSH_Snipe
        return (1);
}

		vinyl-cache/bin/vinyld/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_int.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	38775	lru_get(const struct objcore *oc)
50		{
51	38775	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
52	38775	CHECK_OBJ_NOTNULL(oc->stobj->stevedore, STEVEDORE_MAGIC);
53	38775	CHECK_OBJ_NOTNULL(oc->stobj->stevedore->lru, LRU_MAGIC);
54	38775	return (oc->stobj->stevedore->lru);
55		}
56
57		struct lru *
58	41222	LRU_Alloc(void)
59		{
60		struct lru *lru;
61
62	41222	ALLOC_OBJ(lru, LRU_MAGIC);
63	41222	AN(lru);
64	41222	VTAILQ_INIT(&lru->lru_head);
65	41222	Lck_New(&lru->mtx, lck_lru);
66	41222	return (lru);
67		}
68
69		/*
70		* LRU_Free requires the LRU list to be drained. This is not actually used
71		* in-tree, but by external storage. Please do not remove, this is not dead code
72		*/
73		void
74	0	LRU_Free(struct lru **pp)
75		{
76		struct lru *lru;
77
78	0	TAKE_OBJ_NOTNULL(lru, pp, LRU_MAGIC);
79	0	Lck_Lock(&lru->mtx);
80	0	AN(VTAILQ_EMPTY(&lru->lru_head));
81	0	Lck_Unlock(&lru->mtx);
82	0	Lck_Delete(&lru->mtx);
83	0	FREE_OBJ(lru);
84	0	}
85
86		void
87	55019	LRU_Add(struct objcore *oc, vtim_real now)
88		{
89		struct lru *lru;
90
91	55019	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
92
93	55019	if (oc->flags & (OC_F_PRIVATE\|OC_F_FAILED))
94	25367	return;
95
96	29652	AZ(oc->boc);
97	29652	AN(isnan(oc->last_lru));
98	29652	AZ(isnan(now));
99	29652	lru = lru_get(oc);
100	29652	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
101	29652	Lck_Lock(&lru->mtx);
102	29652	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
103	29652	oc->last_lru = now;
104	29652	AZ(isnan(oc->last_lru));
105	29652	Lck_Unlock(&lru->mtx);
106	55019	}
107
108		void
109	33715	LRU_Remove(struct objcore *oc)
110		{
111		struct lru *lru;
112
113	33715	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
114
115	33715	if (oc->flags & (OC_F_PRIVATE\|OC_F_FAILED))
116	25366	return;
117
118	8349	AZ(oc->boc);
119	8349	lru = lru_get(oc);
120	8349	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
121	8349	Lck_Lock(&lru->mtx);
122	8349	AZ(isnan(oc->last_lru));
123	8349	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
124	8349	oc->last_lru = NAN;
125	8349	Lck_Unlock(&lru->mtx);
126	33715	}
127
128		void v_matchproto_(objtouch_f)
129	73057	LRU_Touch(struct worker wrk, struct objcore oc, vtim_real now)
130		{
131		struct lru *lru;
132
133	73057	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
134	73057	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
135
136	73057	if (oc->flags & (OC_F_PRIVATE\|OC_F_FAILED) \|\| isnan(oc->last_lru))
137	33740	return;
138
139		/*
140		* To avoid the exphdl->mtx becoming a hotspot, we only
141		* attempt to move objects if they have not been moved
142		* recently and if the lock is available. This optimization
143		* obviously leaves the LRU list imperfectly sorted.
144		*/
145
146	39317	if (now - oc->last_lru < cache_param->lru_interval)
147	38542	return;
148
149	775	lru = lru_get(oc);
150	775	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
151
152	775	if (Lck_Trylock(&lru->mtx))
153	1	return;
154
155	774	if (!isnan(oc->last_lru)) {
156	774	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
157	774	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
158	774	VSC_C_main->n_lru_moved++;
159	774	oc->last_lru = now;
160	774	}
161	774	Lck_Unlock(&lru->mtx);
162	73057	}
163
164		/*--------------------------------------------------------------------
165		* Attempt to make space by nuking the oldest object on the LRU list
166		* which isn't in use.
167		* Returns: 1: did, 0: didn't;
168		*/
169
170		int
171	525	LRU_NukeOne(struct worker wrk, struct lru lru)
172		{
173		struct objcore oc, oc2;
174
175	525	CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
176	525	CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
177
178	525	if (wrk->strangelove-- <= 0) {
179	231	VSLb(wrk->vsl, SLT_ExpKill, "LRU reached nuke_limit");
180	231	VSC_C_main->n_lru_limited++;
181	231	return (0);
182		}
183
184		/* Find the first currently unused object on the LRU. */
185	294	Lck_Lock(&lru->mtx);
186	294	VTAILQ_FOREACH_SAFE(oc, &lru->lru_head, lru_list, oc2) {
187	231	CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
188	231	AZ(oc->flags & (OC_F_PRIVATE\|OC_F_FAILED));
189	231	AZ(isnan(oc->last_lru));
190
191	462	VSLb(wrk->vsl, SLT_ExpKill, "LRU_Cand p=%p f=0x%x r=%d",
192	231	oc, oc->flags, oc->refcnt);
193
194	231	if (HSH_Snipe(wrk, oc)) {
195	231	VSC_C_main->n_lru_nuked++; // XXX per lru ?
196	231	VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
197	231	VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
198	231	break;
199		}
200	0	}
201	294	Lck_Unlock(&lru->mtx);
202
203	294	if (oc == NULL) {
204	63	VSLb(wrk->vsl, SLT_ExpKill, "LRU_Fail");
205	63	return (0);
206		}
207
208		/* XXX: We could grab and return one storage segment to our caller */
209	231	ObjSlim(wrk, oc);
210
211	231	VSLb(wrk->vsl, SLT_ExpKill, "LRU xid=%ju", VXID(ObjGetXID(wrk, oc)));
212	231	(void)HSH_DerefObjCore(wrk, &oc); // Ref from HSH_Snipe
213	231	return (1);
214	525	}