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
        vtim_real                       touched;        // XXX -> mono?
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
        vtim_real                       t_now;  // XXX -> mono?
67
        int                             self_destruct;
68
};
69
70
/*---------------------------------------------------------------------
71
 */
72
73
static struct memitem *
74 138296
mpl_alloc(const struct mempool *mpl)
75
{
76
        unsigned tsz;
77
        struct memitem *mi;
78
79 138296
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
80 138296
        tsz = *mpl->cur_size;
81 138296
        mi = calloc(1, tsz);
82 138296
        AN(mi);
83 138296
        mi->magic = MEMITEM_MAGIC;
84 138296
        mi->size = tsz;
85 138296
        mpl->vsc->sz_wanted = tsz;
86 138296
        mpl->vsc->sz_actual = tsz - sizeof *mi;
87 138296
        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 13688
mpl_guard(void *priv)
99
{
100
        struct mempool *mpl;
101 13688
        struct memitem *mi = NULL;
102
        vtim_dur v_statevariable_(mpl_slp);
103 13688
        vtim_real last = 0;
104
105 13688
        CAST_OBJ_NOTNULL(mpl, priv, MEMPOOL_MAGIC);
106 13688
        THR_SetName(mpl->name);
107 13688
        THR_Init();
108 13688
        mpl_slp = 0.15; // random
109
        while (1) {
110 400528
                VTIM_sleep(mpl_slp);
111 193672
                mpl_slp = 0.814;        // random
112 193672
                mpl->t_now = VTIM_real();
113
114 193809
                if (mi != NULL && (mpl->n_pool > mpl->param->max_pool ||
115 0
                    mi->size < *mpl->cur_size)) {
116 1
                        FREE_OBJ(mi);
117 0
                        mi = NULL;
118
                }
119
120 193808
                if (mi == NULL && mpl->n_pool < mpl->param->min_pool)
121 138635
                        mi = mpl_alloc(mpl);
122
123 193464
                if (mpl->n_pool < mpl->param->min_pool && mi != NULL) {
124
                        /* can do */
125 55169
                } else if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
126
                        /* can do */
127 55089
                } else if (!VTAILQ_EMPTY(&mpl->surplus)) {
128
                        /* can do */
129 55089
                } else if (last + .1 * mpl->param->max_age < mpl->t_now) {
130
                        /* should do */
131 37918
                } else if (mpl->self_destruct) {
132
                        /* can do */
133
                } else {
134 37852
                        continue;       /* nothing to do */
135
                }
136
137 155612
                mpl_slp = 0.314;        // random
138
139 155612
                if (Lck_Trylock(&mpl->mtx))
140 0
                        continue;
141
142 155622
                if (mpl->self_destruct) {
143 16
                        AZ(mpl->live);
144
                        while (1) {
145 364
                                if (mi == NULL) {
146 190
                                        mi = VTAILQ_FIRST(&mpl->list);
147 190
                                        if (mi != NULL) {
148 174
                                                mpl->vsc->pool = --mpl->n_pool;
149 174
                                                VTAILQ_REMOVE(&mpl->list,
150
                                                    mi, list);
151
                                        }
152
                                }
153 190
                                if (mi == NULL) {
154 16
                                        mi = VTAILQ_FIRST(&mpl->surplus);
155 16
                                        if (mi != NULL)
156 0
                                                VTAILQ_REMOVE(&mpl->surplus,
157
                                                    mi, list);
158
                                }
159 190
                                if (mi == NULL)
160 16
                                        break;
161 174
                                FREE_OBJ(mi);
162 174
                                mi = NULL;
163
                        }
164 16
                        VSC_mempool_Destroy(&mpl->vsc_seg);
165 16
                        Lck_Unlock(&mpl->mtx);
166 16
                        Lck_Delete(&mpl->mtx);
167 16
                        FREE_OBJ(mpl);
168 16
                        break;
169
                }
170
171 155606
                if (mpl->n_pool < mpl->param->min_pool &&
172 138329
                    mi != NULL && mi->size >= *mpl->cur_size) {
173 138358
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
174 138358
                        mpl->vsc->pool = ++mpl->n_pool;
175 138358
                        mi->touched = mpl->t_now;
176 138358
                        VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
177 138358
                        mi = NULL;
178 138358
                        mpl_slp = .01;  // random
179
180
                }
181 155606
                if (mpl->n_pool > mpl->param->max_pool && mi == NULL) {
182 80
                        mi = VTAILQ_FIRST(&mpl->list);
183 80
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
184 80
                        mpl->vsc->pool = --mpl->n_pool;
185 80
                        mpl->vsc->surplus++;
186 80
                        VTAILQ_REMOVE(&mpl->list, mi, list);
187 80
                        mpl_slp = .01;  // random
188
                }
189 155606
                if (mi == NULL) {
190 155487
                        mi = VTAILQ_FIRST(&mpl->surplus);
191 155487
                        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 155606
                if (mi == NULL && mpl->n_pool > mpl->param->min_pool) {
198 1319
                        mi = VTAILQ_LAST(&mpl->list, memhead_s);
199 1319
                        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
200 2638
                        if (mi->touched + mpl->param->max_age < mpl->t_now) {
201 563
                                mpl->vsc->pool = --mpl->n_pool;
202 563
                                mpl->vsc->timeout++;
203 563
                                VTAILQ_REMOVE(&mpl->list, mi, list);
204 563
                                mpl_slp = .01;  // random
205
                        } else {
206 756
                                mi = NULL;
207 756
                                last = mpl->t_now;
208
                        }
209 154287
                } else if (mpl->n_pool <= mpl->param->min_pool) {
210 154265
                        last = mpl->t_now;
211
                }
212
213 155606
                Lck_Unlock(&mpl->mtx);
214
215 155568
                if (mi != NULL) {
216 643
                        FREE_OBJ(mi);
217 643
                        mi = NULL;
218
                }
219
        }
220 16
        return (NULL);
221
}
222
223
/*---------------------------------------------------------------------
224
 * Create a new memory pool, and start the guard thread for it.
225
 */
226
227
struct mempool *
228 13688
MPL_New(const char *name,
229
    volatile struct poolparam *pp, volatile unsigned *cur_size)
230
{
231
        struct mempool *mpl;
232
233 13688
        ALLOC_OBJ(mpl, MEMPOOL_MAGIC);
234 13688
        AN(mpl);
235 13688
        bprintf(mpl->name, "MPL_%s", name);
236 13688
        mpl->param = pp;
237 13688
        mpl->cur_size = cur_size;
238 13688
        VTAILQ_INIT(&mpl->list);
239 13688
        VTAILQ_INIT(&mpl->surplus);
240 13688
        Lck_New(&mpl->mtx, lck_mempool);
241
        /* XXX: prealloc min_pool */
242 13688
        mpl->vsc = VSC_mempool_New(NULL, &mpl->vsc_seg, mpl->name + 4);
243 13688
        AN(mpl->vsc);
244 13688
        AZ(pthread_create(&mpl->thread, NULL, mpl_guard, mpl));
245 13688
        AZ(pthread_detach(mpl->thread));
246 13688
        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 16
MPL_Destroy(struct mempool **mpp)
256
{
257
        struct mempool *mpl;
258
259 16
        TAKE_OBJ_NOTNULL(mpl, mpp, MEMPOOL_MAGIC);
260 16
        Lck_Lock(&mpl->mtx);
261 16
        AZ(mpl->live);
262 16
        mpl->self_destruct = 1;
263 16
        Lck_Unlock(&mpl->mtx);
264 16
}
265
266
/*---------------------------------------------------------------------
267
 */
268
269
void *
270 19908
MPL_Get(struct mempool *mpl, unsigned *size)
271
{
272
        struct memitem *mi;
273
274 19908
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
275 19908
        AN(size);
276
277 19908
        Lck_Lock(&mpl->mtx);
278
279 19908
        mpl->vsc->allocs++;
280 19908
        mpl->vsc->live = ++mpl->live;
281
282
        do {
283 19908
                mi = VTAILQ_FIRST(&mpl->list);
284 19908
                if (mi == NULL) {
285 0
                        mpl->vsc->randry++;
286 0
                        break;
287
                }
288 19908
                mpl->vsc->pool = --mpl->n_pool;
289 19908
                CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
290 19908
                VTAILQ_REMOVE(&mpl->list, mi, list);
291 19908
                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 19908
                        mpl->vsc->recycle++;
297
                }
298 19908
        } while (mi == NULL);
299
300 19908
        Lck_Unlock(&mpl->mtx);
301
302 19908
        if (mi == NULL)
303 0
                mi = mpl_alloc(mpl);
304 19908
        *size = mi->size - sizeof *mi;
305
306 19908
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
307
        /* Throw away sizeof info for FlexeLint: */
308 19908
        return ((void*)(uintptr_t)(mi+1));
309
}
310
311
void
312 19824
MPL_Free(struct mempool *mpl, void *item)
313
{
314
        struct memitem *mi;
315
316 19824
        CHECK_OBJ_NOTNULL(mpl, MEMPOOL_MAGIC);
317 19824
        AN(item);
318
319 19824
        mi = (void*)((uintptr_t)item - sizeof(*mi));
320 19824
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
321 19824
        memset(item, 0, mi->size - sizeof *mi);
322
323 19824
        Lck_Lock(&mpl->mtx);
324
325 19824
        mpl->vsc->frees++;
326 19824
        mpl->vsc->live = --mpl->live;
327
328 19824
        if (mi->size < *mpl->cur_size) {
329 0
                mpl->vsc->toosmall++;
330 0
                VTAILQ_INSERT_HEAD(&mpl->surplus, mi, list);
331
        } else {
332 19824
                mpl->vsc->pool = ++mpl->n_pool;
333 19824
                mi->touched = mpl->t_now;
334 19824
                VTAILQ_INSERT_HEAD(&mpl->list, mi, list);
335
        }
336
337 19824
        Lck_Unlock(&mpl->mtx);
338 19824
}
339
340
void
341 7616
MPL_AssertSane(const void *item)
342
{
343
        struct memitem *mi;
344 7616
        mi = (void*)((uintptr_t)item - sizeof(*mi));
345 7616
        CHECK_OBJ_NOTNULL(mi, MEMITEM_MAGIC);
346 7616
}