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_seg                  *vsc_seg;
63
        struct VSC_mempool              *vsc;
64
        unsigned                        n_pool;
65
        pthread_t                       thread;
66
        double                          t_now;
67
        int                             self_destruct;
68
};
69
70
/*---------------------------------------------------------------------
71
 */
72
73
static struct memitem *
74 103368
mpl_alloc(const struct mempool *mpl)
75
{
76
        unsigned tsz;
77
        struct memitem *mi;
78
79 103368
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
80 103368
        tsz = *mpl->cur_size;
81 103368
        mi = calloc(1, tsz);
82 103368
        AN(mi);
83 103368
        mi->magic = MEMITEM_MAGIC;
84 103368
        mi->size = tsz;
85 103368
        mpl->vsc->sz_wanted = tsz;
86 103368
        mpl->vsc->sz_actual = tsz - sizeof *mi;
87 103368
        return (mi);
88
}
89
90
/*---------------------------------------------------------------------
91
 * Pool-guard
92
 *   Attempt to keep number of free items in pool inside bounds with
93
 *   minimum locking activity, and keep an eye on items at the tail
94
 *   of the list not getting too old.
95
 */
96
97
static void *
98 10227
mpl_guard(void *priv)
99
{
100
        struct mempool *mpl;
101 10227
        struct memitem *mi = NULL;
102
        double v_statevariable_(mpl_slp);
103 10227
        double last = 0;
104
105 10227
        CAST_OBJ_NOTNULL(mpl, priv, MEMPOOL_MAGIC);
106 10227
        THR_SetName(mpl->name);
107 10227
        THR_Init();
108 10227
        mpl_slp = 0.15; // random
109
        while (1) {
110 295245
                VTIM_sleep(mpl_slp);
111 142753
                mpl_slp = 0.814;        // random
112 142753
                mpl->t_now = VTIM_real();
113
114 142826
                if (mi != NULL && (mpl->n_pool > mpl->param->max_pool ||
115 0
                    mi->size < *mpl->cur_size)) {
116 28
                        FREE_OBJ(mi);
117 0
                        mi = NULL;
118
                }
119
120 142798
                if (mi == NULL && mpl->n_pool < mpl->param->min_pool)
121 103619
                        mi = mpl_alloc(mpl);
122
123 142539
                if (mpl->n_pool < mpl->param->min_pool && mi != NULL) {
124
                        /* can do */
125 39179
                } else if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
126
                        /* can do */
127 39119
                } else if (!VTAILQ_EMPTY(&mpl->surplus)) {
128
                        /* can do */
129 39119
                } else if (last + .1 * mpl->param->max_age < mpl->t_now) {
130
                        /* should do */
131 27280
                } else if (mpl->self_destruct) {
132
                        /* can do */
133
                } else {
134 27233
                        continue;       /* nothing to do */
135
                }
136
137 115306
                mpl_slp = 0.314;        // random
138
139 115306
                if (Lck_Trylock(&mpl->mtx))
140 0
                        continue;
141
142 115384
                if (mpl->self_destruct) {
143 12
                        AZ(mpl->live);
144
                        while (1) {
145 276
                                if (mi == NULL) {
146 144
                                        mi = VTAILQ_FIRST(&mpl->list);
147 144
                                        if (mi != NULL) {
148 132
                                                mpl->vsc->pool = --mpl->n_pool;
149 132
                                                VTAILQ_REMOVE(&mpl->list,
150
                                                    mi, list);
151
                                        }
152
                                }
153 144
                                if (mi == NULL) {
154 12
                                        mi = VTAILQ_FIRST(&mpl->surplus);
155 12
                                        if (mi != NULL)
156 0
                                                VTAILQ_REMOVE(&mpl->surplus,
157
                                                    mi, list);
158
                                }
159 144
                                if (mi == NULL)
160 12
                                        break;
161 132
                                FREE_OBJ(mi);
162 132
                                mi = NULL;
163
                        }
164 12
                        VSC_mempool_Destroy(&mpl->vsc_seg);
165 12
                        Lck_Unlock(&mpl->mtx);
166 12
                        Lck_Delete(&mpl->mtx);
167 12
                        FREE_OBJ(mpl);
168 12
                        break;
169
                }
170
171 115372
                if (mpl->n_pool < mpl->param->min_pool &&
172 103461
                    mi != NULL && mi->size >= *mpl->cur_size) {
173 103432
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
174 103432
                        mpl->vsc->pool = ++mpl->n_pool;
175 103432
                        mi->touched = mpl->t_now;
176 103432
                        VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
177 103432
                        mi = NULL;
178 103432
                        mpl_slp = .01;  // random
179
180
                }
181 115372
                if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
182 60
                        mi = VTAILQ_FIRST(&mpl->list);
183 60
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
184 60
                        mpl->vsc->pool = --mpl->n_pool;
185 60
                        mpl->vsc->surplus++;
186 60
                        VTAILQ_REMOVE(&mpl->list, mi, list);
187 60
                        mpl_slp = .01;  // random
188
                }
189 115372
                if (mi == NULL) {
190 115265
                        mi = VTAILQ_FIRST(&mpl->surplus);
191 115265
                        if (mi != NULL) {
192 0
                                CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
193 0
                                VTAILQ_REMOVE(&mpl->surplus, mi, list);
194 0
                                mpl_slp = .01;  // random
195
                        }
196
                }
197 115372
                if (mi == NULL && mpl->n_pool > mpl->param->min_pool) {
198 979
                        mi = VTAILQ_LAST(&mpl->list, memhead_s);
199 979
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
200 1958
                        if (mi->touched + mpl->param->max_age < mpl->t_now) {
201 422
                                mpl->vsc->pool = --mpl->n_pool;
202 422
                                mpl->vsc->timeout++;
203 422
                                VTAILQ_REMOVE(&mpl->list, mi, list);
204 422
                                mpl_slp = .01;  // random
205
                        } else {
206 557
                                mi = NULL;
207 557
                                last = mpl->t_now;
208
                        }
209 114393
                } else if (mpl->n_pool <= mpl->param->min_pool) {
210 114274
                        last = mpl->t_now;
211
                }
212
213 115372
                Lck_Unlock(&mpl->mtx);
214
215 115276
                if (mi != NULL) {
216 485
                        FREE_OBJ(mi);
217 485
                        mi = NULL;
218
                }
219
        }
220 12
        return (NULL);
221
}
222
223
/*---------------------------------------------------------------------
224
 * Create a new memory pool, and start the guard thread for it.
225
 */
226
227
struct mempool *
228 10227
MPL_New(const char *name,
229
    volatile struct poolparam *pp, volatile unsigned *cur_size)
230
{
231
        struct mempool *mpl;
232
233 10227
        ALLOC_OBJ(mpl, MEMPOOL_MAGIC);
234 10227
        AN(mpl);
235 10227
        bprintf(mpl->name, "MPL_%s", name);
236 10227
        mpl->param = pp;
237 10227
        mpl->cur_size = cur_size;
238 10227
        VTAILQ_INIT(&mpl->list);
239 10227
        VTAILQ_INIT(&mpl->surplus);
240 10227
        Lck_New(&mpl->mtx, lck_mempool);
241
        /* XXX: prealloc min_pool */
242 10227
        mpl->vsc = VSC_mempool_New(NULL, &mpl->vsc_seg, mpl->name + 4);
243 10227
        AN(mpl->vsc);
244 10227
        AZ(pthread_create(&mpl->thread, NULL, mpl_guard, mpl));
245 10227
        AZ(pthread_detach(mpl->thread));
246 10227
        return (mpl);
247
}
248
249
/*---------------------------------------------------------------------
250
 * Destroy a memory pool.  There must be no live items, and we cheat
251
 * and leave all the hard work to the guard thread.
252
 */
253
254
void
255 12
MPL_Destroy(struct mempool **mpp)
256
{
257
        struct mempool *mpl;
258
259 12
        TAKE_OBJ_NOTNULL(mpl, mpp, MEMPOOL_MAGIC);
260 12
        Lck_Lock(&mpl->mtx);
261 12
        AZ(mpl->live);
262 12
        mpl->self_destruct = 1;
263 12
        Lck_Unlock(&mpl->mtx);
264 12
}
265
266
/*---------------------------------------------------------------------
267
 */
268
269
void *
270 15258
MPL_Get(struct mempool *mpl, unsigned *size)
271
{
272
        struct memitem *mi;
273
274 15258
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
275 15258
        AN(size);
276
277 15258
        Lck_Lock(&mpl->mtx);
278
279 15258
        mpl->vsc->allocs++;
280 15258
        mpl->vsc->live = ++mpl->live;
281
282
        do {
283 15258
                mi = VTAILQ_FIRST(&mpl->list);
284 15258
                if (mi == NULL) {
285 0
                        mpl->vsc->randry++;
286 0
                        break;
287
                }
288 15258
                mpl->vsc->pool = --mpl->n_pool;
289 15258
                CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
290 15258
                VTAILQ_REMOVE(&mpl->list, mi, list);
291 15258
                if (mi->size < *mpl->cur_size) {
292 0
                        mpl->vsc->toosmall++;
293 0
                        VTAILQ_INSERT_HEAD(&mpl->surplus, mi, list);
294 0
                        mi = NULL;
295
                } else {
296 15258
                        mpl->vsc->recycle++;
297
                }
298 15258
        } while (mi == NULL);
299
300 15258
        Lck_Unlock(&mpl->mtx);
301
302 15258
        if (mi == NULL)
303 0
                mi = mpl_alloc(mpl);
304 15258
        *size = mi->size - sizeof *mi;
305
306 15258
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
307
        /* Throw away sizeof info for FlexeLint: */
308 15258
        return ((void*)(uintptr_t)(mi+1));
309
}
310
311
void
312 15218
MPL_Free(struct mempool *mpl, void *item)
313
{
314
        struct memitem *mi;
315
316 15218
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
317 15218
        AN(item);
318
319 15218
        mi = (void*)((uintptr_t)item - sizeof(*mi));
320 15218
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
321 15218
        memset(item, 0, mi->size - sizeof *mi);
322
323 15218
        Lck_Lock(&mpl->mtx);
324
325 15219
        mpl->vsc->frees++;
326 15219
        mpl->vsc->live = --mpl->live;
327
328 15219
        if (mi->size < *mpl->cur_size) {
329 0
                mpl->vsc->toosmall++;
330 0
                VTAILQ_INSERT_HEAD(&mpl->surplus, mi, list);
331
        } else {
332 15219
                mpl->vsc->pool = ++mpl->n_pool;
333 15219
                mi->touched = mpl->t_now;
334 15219
                VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
335
        }
336
337 15219
        Lck_Unlock(&mpl->mtx);
338 15219
}
339
340
void
341 5904
MPL_AssertSane(const void *item)
342
{
343
        struct memitem *mi;
344 5904
        mi = (void*)((uintptr_t)item - sizeof(*mi));
345 5904
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
346 5904
}