varnish-cache/bin/varnishd/cache/cache_mempool.c
1
/*-
2
 * Copyright (c) 2011 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
6
 *
7
 * Redistribution and use in source and binary forms, with or without
8
 * modification, are permitted provided that the following conditions
9
 * are met:
10
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in the
14
 *    documentation and/or other materials provided with the distribution.
15
 *
16
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
20
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26
 * SUCH DAMAGE.
27
 *
28
 * Generic memory pool
29
 */
30
31
#include "config.h"
32
33
#include "cache_varnishd.h"
34
35
#include <stdio.h>
36
#include <stdlib.h>
37
38
#include "vtim.h"
39
40
#include "VSC_mempool.h"
41
42
struct memitem {
43
        unsigned                        magic;
44
#define MEMITEM_MAGIC                   0x42e55401
45
        unsigned                        size;
46
        VTAILQ_ENTRY(memitem)           list;
47
        double                          touched;
48
};
49
50
VTAILQ_HEAD(memhead_s, memitem);
51
52
struct mempool {
53
        unsigned                        magic;
54
#define MEMPOOL_MAGIC                   0x37a75a8d
55
        char                            name[12];
56
        struct memhead_s                list;
57
        struct memhead_s                surplus;
58
        struct lock                     mtx;
59
        volatile struct poolparam       *param;
60
        volatile unsigned               *cur_size;
61
        uint64_t                        live;
62
        struct VSC_mempool              *vsc;
63
        unsigned                        n_pool;
64
        pthread_t                       thread;
65
        double                          t_now;
66
        int                             self_destruct;
67
};
68
69
/*---------------------------------------------------------------------
70
 */
71
72
static struct memitem *
73 61721
mpl_alloc(const struct mempool *mpl)
74
{
75
        unsigned tsz;
76
        struct memitem *mi;
77
78 61721
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
79 61721
        tsz = *mpl->cur_size;
80 61721
        mi = calloc(1, tsz);
81 61721
        AN(mi);
82 61721
        mi->magic = MEMITEM_MAGIC;
83 61721
        mi->size = tsz;
84 61721
        mpl->vsc->sz_wanted = tsz;
85 61721
        mpl->vsc->sz_actual = tsz - sizeof *mi;
86 61721
        return (mi);
87
}
88
89
/*---------------------------------------------------------------------
90
 * Pool-guard
91
 *   Attempt to keep number of free items in pool inside bounds with
92
 *   minimum locking activity, and keep an eye on items at the tail
93
 *   of the list not getting too old.
94
 */
95
96
static void *
97 6112
mpl_guard(void *priv)
98
{
99
        struct mempool *mpl;
100 6112
        struct memitem *mi = NULL;
101
        double v_statevariable_(mpl_slp);
102 6112
        double last = 0;
103
104 6112
        CAST_OBJ_NOTNULL(mpl, priv, MEMPOOL_MAGIC);
105 6112
        THR_SetName(mpl->name);
106 6112
        THR_Init();
107 6112
        mpl_slp = 0.15; // random
108
        while (1) {
109 89298
                VTIM_sleep(mpl_slp);
110 83220
                mpl_slp = 0.814;        // random
111 83220
                mpl->t_now = VTIM_real();
112
113 83100
                if (mi != NULL && (mpl->n_pool > mpl->param->max_pool ||
114 0
                    mi->size < *mpl->cur_size)) {
115 -144
                        FREE_OBJ(mi);
116 0
                        mi = NULL;
117
                }
118
119 83244
                if (mi == NULL && mpl->n_pool < mpl->param->min_pool)
120 61712
                        mi = mpl_alloc(mpl);
121
122 83251
                if (mpl->n_pool < mpl->param->min_pool && mi != NULL) {
123
                        /* can do */
124 21532
                } else if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
125
                        /* can do */
126 21492
                } else if (!VTAILQ_EMPTY(&mpl->surplus)) {
127
                        /* can do */
128 21492
                } else if (last + .1 * mpl->param->max_age < mpl->t_now) {
129
                        /* should do */
130 15166
                } else if (mpl->self_destruct) {
131
                        /* can do */
132
                } else {
133 15173
                        continue;       /* nothing to do */
134
                }
135
136 68078
                mpl_slp = 0.314;        // random
137
138 68078
                if (Lck_Trylock(&mpl->mtx))
139 0
                        continue;
140
141 67850
                if (mpl->self_destruct) {
142 8
                        AZ(mpl->live);
143
                        while (1) {
144 94
                                if (mi == NULL) {
145 94
                                        mi = VTAILQ_FIRST(&mpl->list);
146 94
                                        if (mi != NULL) {
147 86
                                                mpl->vsc->pool = --mpl->n_pool;
148 86
                                                VTAILQ_REMOVE(&mpl->list,
149
                                                    mi, list);
150
                                        }
151
                                }
152 94
                                if (mi == NULL) {
153 8
                                        mi = VTAILQ_FIRST(&mpl->surplus);
154 8
                                        if (mi != NULL)
155 0
                                                VTAILQ_REMOVE(&mpl->surplus,
156
                                                    mi, list);
157
                                }
158 94
                                if (mi == NULL)
159 8
                                        break;
160 86
                                FREE_OBJ(mi);
161 86
                                mi = NULL;
162 86
                        }
163 8
                        VSC_mempool_Destroy(&mpl->vsc);
164 8
                        Lck_Unlock(&mpl->mtx);
165 8
                        Lck_Delete(&mpl->mtx);
166 8
                        FREE_OBJ(mpl);
167 8
                        break;
168
                }
169
170 67842
                if (mpl->n_pool < mpl->param->min_pool &&
171 61774
                    mi != NULL && mi->size >= *mpl->cur_size) {
172 61486
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
173 61486
                        mpl->vsc->pool = ++mpl->n_pool;
174 61486
                        mi->touched = mpl->t_now;
175 61486
                        VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
176 61486
                        mi = NULL;
177 61486
                        mpl_slp = .01;  // random
178
179
                }
180 67842
                if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
181 40
                        mi = VTAILQ_FIRST(&mpl->list);
182 40
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
183 40
                        mpl->vsc->pool = --mpl->n_pool;
184 40
                        mpl->vsc->surplus++;
185 40
                        VTAILQ_REMOVE(&mpl->list, mi, list);
186 40
                        mpl_slp = .01;  // random
187
                }
188 67842
                if (mi == NULL) {
189 67811
                        mi = VTAILQ_FIRST(&mpl->surplus);
190 67811
                        if (mi != NULL) {
191 0
                                CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
192 0
                                VTAILQ_REMOVE(&mpl->surplus, mi, list);
193 0
                                mpl_slp = .01;  // random
194
                        }
195
                }
196 67842
                if (mi == NULL && mpl->n_pool > mpl->param->min_pool) {
197 558
                        mi = VTAILQ_LAST(&mpl->list, memhead_s);
198 558
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
199 1116
                        if (mi->touched + mpl->param->max_age < mpl->t_now) {
200 284
                                mpl->vsc->pool = --mpl->n_pool;
201 284
                                mpl->vsc->timeout++;
202 284
                                VTAILQ_REMOVE(&mpl->list, mi, list);
203 284
                                mpl_slp = .01;  // random
204
                        } else {
205 274
                                mi = NULL;
206 274
                                last = mpl->t_now;
207
                        }
208 67284
                } else if (mpl->n_pool <= mpl->param->min_pool) {
209 67296
                        last = mpl->t_now;
210
                }
211
212 67842
                Lck_Unlock(&mpl->mtx);
213
214 68012
                if (mi != NULL) {
215 323
                        FREE_OBJ(mi);
216 324
                        mi = NULL;
217
                }
218 83186
        }
219 8
        return (NULL);
220
}
221
222
/*---------------------------------------------------------------------
223
 * Create a new memory pool, and start the guard thread for it.
224
 */
225
226
struct mempool *
227 6112
MPL_New(const char *name,
228
    volatile struct poolparam *pp, volatile unsigned *cur_size)
229
{
230
        struct mempool *mpl;
231
232 6112
        ALLOC_OBJ(mpl, MEMPOOL_MAGIC);
233 6112
        AN(mpl);
234 6112
        bprintf(mpl->name, "MPL_%s", name);
235 6112
        mpl->param = pp;
236 6112
        mpl->cur_size = cur_size;
237 6112
        VTAILQ_INIT(&mpl->list);
238 6112
        VTAILQ_INIT(&mpl->surplus);
239 6112
        Lck_New(&mpl->mtx, lck_mempool);
240
        /* XXX: prealloc min_pool */
241 6112
        mpl->vsc = VSC_mempool_New(mpl->name + 4);
242 6112
        AN(mpl->vsc);
243 6112
        AZ(pthread_create(&mpl->thread, NULL, mpl_guard, mpl));
244 6112
        AZ(pthread_detach(mpl->thread));
245 6112
        return (mpl);
246
}
247
248
/*---------------------------------------------------------------------
249
 * Destroy a memory pool.  There must be no live items, and we cheat
250
 * and leave all the hard work to the guard thread.
251
 */
252
253
void
254 8
MPL_Destroy(struct mempool **mpp)
255
{
256
        struct mempool *mpl;
257
258 8
        TAKE_OBJ_NOTNULL(mpl, mpp, MEMPOOL_MAGIC);
259 8
        Lck_Lock(&mpl->mtx);
260 8
        AZ(mpl->live);
261 8
        mpl->self_destruct = 1;
262 8
        Lck_Unlock(&mpl->mtx);
263 8
}
264
265
/*---------------------------------------------------------------------
266
 */
267
268
void *
269 7969
MPL_Get(struct mempool *mpl, unsigned *size)
270
{
271
        struct memitem *mi;
272
273 7969
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
274 7969
        AN(size);
275
276 7969
        Lck_Lock(&mpl->mtx);
277
278 7971
        mpl->vsc->allocs++;
279 7971
        mpl->vsc->live = ++mpl->live;
280
281
        do {
282 7971
                mi = VTAILQ_FIRST(&mpl->list);
283 7971
                if (mi == NULL) {
284 0
                        mpl->vsc->randry++;
285 0
                        break;
286
                }
287 7971
                mpl->vsc->pool = --mpl->n_pool;
288 7971
                CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
289 7971
                VTAILQ_REMOVE(&mpl->list, mi, list);
290 7971
                if (mi->size < *mpl->cur_size) {
291 0
                        mpl->vsc->toosmall++;
292 0
                        VTAILQ_INSERT_HEAD(&mpl->surplus, mi, list);
293 0
                        mi = NULL;
294
                } else {
295 7971
                        mpl->vsc->recycle++;
296
                }
297 7971
        } while (mi == NULL);
298
299 7971
        Lck_Unlock(&mpl->mtx);
300
301 7971
        if (mi == NULL)
302 0
                mi = mpl_alloc(mpl);
303 7970
        *size = mi->size - sizeof *mi;
304
305 7970
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
306
        /* Throw away sizeof info for FlexeLint: */
307 7970
        return ((void*)(uintptr_t)(mi+1));
308
}
309
310
void
311 7949
MPL_Free(struct mempool *mpl, void *item)
312
{
313
        struct memitem *mi;
314
315 7949
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
316 7949
        AN(item);
317
318 7949
        mi = (void*)((uintptr_t)item - sizeof(*mi));
319 7949
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
320 7949
        memset(item, 0, mi->size - sizeof *mi);
321
322 7949
        Lck_Lock(&mpl->mtx);
323
324 7949
        mpl->vsc->frees++;
325 7949
        mpl->vsc->live = --mpl->live;
326
327 7949
        if (mi->size < *mpl->cur_size) {
328 0
                mpl->vsc->toosmall++;
329 0
                VTAILQ_INSERT_HEAD(&mpl->surplus, mi, list);
330
        } else {
331 7949
                mpl->vsc->pool = ++mpl->n_pool;
332 7949
                mi->touched = mpl->t_now;
333 7949
                VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
334
        }
335
336 7949
        Lck_Unlock(&mpl->mtx);
337 7949
}
338
339
void
340 3089
MPL_AssertSane(const void *item)
341
{
342
        struct memitem *mi;
343 3089
        mi = (void*)((uintptr_t)item - sizeof(*mi));
344 3089
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
345 3089
}