Code Coverage: vinyl-cache/bin/vinyld/storage/storage_lru.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
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
lru_get(const struct objcore *oc)
50 1888
{
51 1888
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
52 1888
        CHECK_OBJ_NOTNULL(oc->stobj->stevedore, STEVEDORE_MAGIC);
53 1888
        CHECK_OBJ_NOTNULL(oc->stobj->stevedore->lru, LRU_MAGIC);
54 1888
        return (oc->stobj->stevedore->lru);
55 1888
}
56
57
struct lru *
58
LRU_Alloc(void)
59 2025
{
60 2025
        struct lru *lru;
61
62 2025
        ALLOC_OBJ(lru, LRU_MAGIC);
63 2025
        AN(lru);
64 2025
        VTAILQ_INIT(&lru->lru_head);
65 2025
        Lck_New(&lru->mtx, lck_lru);
66 2025
        return (lru);
67 2025
}
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
LRU_Free(struct lru **pp)
75 0
{
76 0
        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
LRU_Add(struct objcore *oc, vtim_real now)
88 4701
{
89 4701
        struct lru *lru;
90
91 4701
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
92
93 4701
        if (oc->flags & (OC_F_PRIVATE|OC_F_FAILED))
94 3257
                return;
95
96 1444
        AZ(oc->boc);
97 1444
        AN(isnan(oc->last_lru));
98 1444
        AZ(isnan(now));
99 1444
        lru = lru_get(oc);
100 1444
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
101 1444
        Lck_Lock(&lru->mtx);
102 1444
        VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
103 1444
        oc->last_lru = now;
104 1444
        AZ(isnan(oc->last_lru));
105 1444
        Lck_Unlock(&lru->mtx);
106 1444
}
107
108
void
109
LRU_Remove(struct objcore *oc)
110 3656
{
111 3656
        struct lru *lru;
112
113 3656
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
114
115 3656
        if (oc->flags & (OC_F_PRIVATE|OC_F_FAILED))
116 3257
                return;
117
118 399
        AZ(oc->boc);
119 399
        lru = lru_get(oc);
120 399
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
121 399
        Lck_Lock(&lru->mtx);
122 399
        AZ(isnan(oc->last_lru));
123 399
        VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
124 399
        oc->last_lru = NAN;
125 399
        Lck_Unlock(&lru->mtx);
126 399
}
127
128
void v_matchproto_(objtouch_f)
129
LRU_Touch(struct worker *wrk, struct objcore *oc, vtim_real now)
130 4997
{
131 4997
        struct lru *lru;
132
133 4997
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
134 4997
        CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
135
136 4997
        if (oc->flags & (OC_F_PRIVATE|OC_F_FAILED) || isnan(oc->last_lru))
137 2127
                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 2870
        if (now - oc->last_lru < cache_param->lru_interval)
147 2824
                return;
148
149 46
        lru = lru_get(oc);
150 46
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
151
152 46
        if (Lck_Trylock(&lru->mtx))
153 0
                return;
154
155 46
        if (!isnan(oc->last_lru)) {
156 45
                VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
157 45
                VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
158 45
                VSC_C_main->n_lru_moved++;
159 45
                oc->last_lru = now;
160 45
        }
161 46
        Lck_Unlock(&lru->mtx);
162 46
}
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
LRU_NukeOne(struct worker *wrk, struct lru *lru)
172 25
{
173 25
        struct objcore *oc, *oc2;
174
175 25
        CHECK_OBJ_NOTNULL(wrk, WORKER_MAGIC);
176 25
        CHECK_OBJ_NOTNULL(lru, LRU_MAGIC);
177
178 25
        if (wrk->strangelove-- <= 0) {
179 11
                VSLb(wrk->vsl, SLT_ExpKill, "LRU reached nuke_limit");
180 11
                VSC_C_main->n_lru_limited++;
181 11
                return (0);
182 11
        }
183
184
        /* Find the first currently unused object on the LRU.  */
185 14
        Lck_Lock(&lru->mtx);
186 14
        VTAILQ_FOREACH_SAFE(oc, &lru->lru_head, lru_list, oc2) {
187 11
                CHECK_OBJ_NOTNULL(oc, OBJCORE_MAGIC);
188 11
                AZ(oc->flags & (OC_F_PRIVATE|OC_F_FAILED));
189 11
                AZ(isnan(oc->last_lru));
190
191 11
                VSLb(wrk->vsl, SLT_ExpKill, "LRU_Cand p=%p f=0x%x r=%d",
192 11
                    oc, oc->flags, oc->refcnt);
193
194 11
                if (HSH_Snipe(wrk, oc)) {
195 11
                        VSC_C_main->n_lru_nuked++; // XXX per lru ?
196 11
                        VTAILQ_REMOVE(&lru->lru_head, oc, lru_list);
197 11
                        VTAILQ_INSERT_TAIL(&lru->lru_head, oc, lru_list);
198 11
                        break;
199 11
                }
200 11
        }
201 14
        Lck_Unlock(&lru->mtx);
202
203 14
        if (oc == NULL) {
204 3
                VSLb(wrk->vsl, SLT_ExpKill, "LRU_Fail");
205 3
                return (0);
206 3
        }
207
208
        /* XXX: We could grab and return one storage segment to our caller */
209 11
        ObjSlim(wrk, oc);
210
211 11
        VSLb(wrk->vsl, SLT_ExpKill, "LRU xid=%ju", VXID(ObjGetXID(wrk, oc)));
212 11
        (void)HSH_DerefObjCore(wrk, &oc);       // Ref from HSH_Snipe
213 11
        return (1);
214 14
}