Code Coverage: vinyl-cache/vmod/vmod_directors_shard_dir.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
0
/*-
1
 * Copyright 2009-2016 UPLEX - Nils Goroll Systemoptimierung
2
 * All rights reserved.
3
 *
4
 * Authors: Nils Goroll <nils.goroll@uplex.de>
5
 *          Geoffrey Simmons <geoff.simmons@uplex.de>
6
 *          Julian Wiesener <jw@uplex.de>
7
 *
8
 * SPDX-License-Identifier: BSD-2-Clause
9
 *
10
 * Redistribution and use in source and binary forms, with or without
11
 * modification, are permitted provided that the following conditions
12
 * are met:
13
 * 1. Redistributions of source code must retain the above copyright
14
 *    notice, this list of conditions and the following disclaimer.
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in the
17
 *    documentation and/or other materials provided with the distribution.
18
 *
19
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
23
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29
 * SUCH DAMAGE.
30
 */
31
32
/*lint --e{801} */
33
34
#include "config.h"
35
36
#include <stdlib.h>
37
#include <stdio.h>
38
#include <time.h>
39
#include <limits.h>
40
41
#include "cache/cache.h"
42
43
#include "vbm.h"
44
#include "vrnd.h"
45
46
#include "vcc_directors_if.h"
47
#include "vmod_directors_shard_dir.h"
48
49
struct shard_be_info {
50
        unsigned        hostid;
51
        unsigned        healthy;
52
        double          changed;        // when
53
};
54
55
/*
56
 * circle walk state for shard_next
57
 *
58
 * pick* cut off the search after having seen all possible backends
59
 */
60
struct shard_state {
61
        const struct vrt_ctx    *ctx;
62
        struct sharddir *shardd;
63
        uint32_t                idx;
64
65
        struct vbitmap          *picklist;
66
        unsigned                pickcount;
67
68
        struct shard_be_info    previous;
69
        struct shard_be_info    last;
70
};
71
72
void
73
sharddir_debug(struct sharddir *shardd, const uint32_t flags)
74 7
{
75 7
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
76 7
        shardd->debug_flags = flags;
77 7
}
78
79
void
80
sharddir_log(struct vsl_log *vsl, enum VSL_tag_e tag,  const char *fmt, ...)
81 21
{
82 21
        va_list ap;
83
84 21
        va_start(ap, fmt);
85 21
        if (vsl != NULL)
86 10
                VSLbv(vsl, tag, fmt, ap);
87 11
        else
88 11
                VSLv(tag, NO_VXID, fmt, ap);
89 21
        va_end(ap);
90 21
}
91
92
static int
93
shard_lookup(const struct sharddir *shardd, const uint32_t key)
94 104
{
95 104
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
96
97 104
        const uint32_t n = shardd->n_points;
98 104
        uint32_t i, idx = UINT32_MAX, high = n, low = 0;
99
100 104
        assert (n < idx);
101
102 635
        do {
103 635
            i = (high + low) / 2 ;
104 635
            if (shardd->hashcircle[i].point == key)
105 1
                idx = i;
106 634
            else if (i == n - 1)
107 18
                idx = n - 1;
108 616
            else if (shardd->hashcircle[i].point < key &&
109 616
                     shardd->hashcircle[i+1].point >= key)
110 68
                idx = i + 1;
111 548
            else if (shardd->hashcircle[i].point > key)
112 290
                if (i == 0)
113 17
                    idx = 0;
114 273
                else
115 273
                    high = i;
116 258
            else
117 258
                low = i;
118 635
        } while (idx == UINT32_MAX);
119
120 104
        return (idx);
121 104
}
122
123
static int
124
shard_next(struct shard_state *state, VCL_INT skip, VCL_BOOL healthy)
125 208
{
126 208
        int c, chosen = -1;
127 208
        VCL_BACKEND be;
128 208
        vtim_real changed;
129 208
        struct shard_be_info *sbe;
130
131 208
        AN(state);
132 208
        CHECK_OBJ_NOTNULL(state->shardd, SHARDDIR_MAGIC);
133
134 208
        if (state->pickcount >= state->shardd->n_backend)
135 3
                return (-1);
136
137 328
        while (state->pickcount < state->shardd->n_backend && skip >= 0) {
138
139 327
                c = state->shardd->hashcircle[state->idx].host;
140
141 327
                if (!vbit_test(state->picklist, c)) {
142
143 220
                        vbit_set(state->picklist, c);
144 220
                        state->pickcount++;
145
146 220
                        sbe = NULL;
147 220
                        be = state->shardd->backend[c].backend;
148 220
                        AN(be);
149 220
                        if (VRT_Healthy(state->ctx, be, &changed)) {
150 214
                                if (skip-- == 0) {
151 204
                                        chosen = c;
152 204
                                        sbe = &state->last;
153 204
                                } else {
154 10
                                        sbe = &state->previous;
155 10
                                }
156
157 214
                        } else if (!healthy && skip-- == 0) {
158 0
                                chosen = c;
159 0
                                sbe = &state->last;
160 0
                        }
161 220
                        if (sbe == &state->last &&
162 220
                            state->last.hostid != UINT_MAX)
163 100
                                vmemcpy(&state->previous, &state->last,
164 220
                                        sizeof(state->previous));
165
166 220
                        if (sbe) {
167 214
                                sbe->hostid = c;
168 214
                                sbe->healthy = 1;
169 214
                                sbe->changed = changed;
170 214
                        }
171 220
                        if (chosen != -1)
172 204
                                break;
173 220
                }
174
175 123
                if (++(state->idx) == state->shardd->n_points)
176 19
                        state->idx = 0;
177 123
        }
178 205
        return (chosen);
179 205
}
180
181
void
182
sharddir_new(struct sharddir **sharddp, const char *vcl_name,
183
    const struct vmod_directors_shard_param *param)
184 25
{
185 25
        struct sharddir *shardd;
186
187 25
        AN(vcl_name);
188 25
        AN(sharddp);
189 25
        AZ(*sharddp);
190 25
        ALLOC_OBJ(shardd, SHARDDIR_MAGIC);
191 25
        AN(shardd);
192 25
        *sharddp = shardd;
193 25
        shardd->name = vcl_name;
194 25
        shardd->param = param;
195 25
        PTOK(pthread_rwlock_init(&shardd->mtx, NULL));
196 25
}
197
198
void
199
sharddir_set_param(struct sharddir *shardd,
200
    const struct vmod_directors_shard_param *param)
201 3
{
202 3
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
203 3
        shardd->param = param;
204 3
}
205
206
void
207
sharddir_release(struct sharddir *shardd)
208 5
{
209 5
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
210 5
        shardcfg_backend_clear(shardd);
211 5
}
212
213
void
214
sharddir_delete(struct sharddir **sharddp)
215 5
{
216 5
        struct sharddir *shardd;
217
218 5
        TAKE_OBJ_NOTNULL(shardd, sharddp, SHARDDIR_MAGIC);
219 5
        shardcfg_delete(shardd);
220 5
        PTOK(pthread_rwlock_destroy(&shardd->mtx));
221 5
        FREE_OBJ(shardd);
222 5
}
223
224
void
225
sharddir_rdlock(struct sharddir *shardd)
226 150
{
227 150
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
228 150
        PTOK(pthread_rwlock_rdlock(&shardd->mtx));
229 150
}
230
231
void
232
sharddir_wrlock(struct sharddir *shardd)
233 44
{
234 44
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
235 44
        PTOK(pthread_rwlock_wrlock(&shardd->mtx));
236 44
}
237
238
void
239
sharddir_unlock(struct sharddir *shardd)
240 194
{
241 194
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
242 194
        PTOK(pthread_rwlock_unlock(&shardd->mtx));
243 194
}
244
245
static inline void
246
validate_alt(VRT_CTX, const struct sharddir *shardd, VCL_INT *alt)
247 104
{
248 104
        const VCL_INT alt_max = shardd->n_backend - 1;
249
250 104
        if (*alt < 0) {
251 0
                shard_err(ctx->vsl, shardd->name,
252 0
                    "invalid negative parameter alt=%jd, set to 0",
253 0
                    (intmax_t)*alt);
254 0
                *alt = 0;
255 104
        } else if (*alt > alt_max) {
256 3
                shard_err(ctx->vsl, shardd->name,
257 3
                    "parameter alt=%jd limited to %jd", (intmax_t)*alt,
258 3
                    (intmax_t)alt_max);
259 3
                *alt = alt_max;
260 3
        }
261 104
}
262
263
static inline void
264
init_state(struct shard_state *state,
265
    VRT_CTX, struct sharddir *shardd, struct vbitmap *picklist)
266 104
{
267 104
        AN(picklist);
268
269 104
        state->ctx = ctx;
270 104
        state->shardd = shardd;
271 104
        state->idx = UINT32_MAX;
272 104
        state->picklist = picklist;
273
274
        /* healthy and changed only defined for valid hostids */
275 104
        state->previous.hostid = UINT_MAX;
276 104
        state->last.hostid = UINT_MAX;
277 104
}
278
279
/* basically same as vdir_any_healthy
280
 * - XXX we should embed a vdir
281
 * - XXX should we return the health state of the actual backend
282
 *   for healthy=IGNORE ?
283
 */
284
VCL_BOOL
285
sharddir_any_healthy(VRT_CTX, struct sharddir *shardd, VCL_TIME *changed)
286 16
{
287 16
        unsigned i, retval = 0;
288 16
        VCL_BACKEND be;
289 16
        vtim_real c;
290
291 16
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
292 16
        sharddir_rdlock(shardd);
293 16
        if (changed != NULL)
294 7
                *changed = 0;
295 16
        for (i = 0; i < shardd->n_backend; i++) {
296 16
                be = shardd->backend[i].backend;
297 16
                CHECK_OBJ_NOTNULL(be, DIRECTOR_MAGIC);
298 16
                retval = VRT_Healthy(ctx, be, &c);
299 16
                if (changed != NULL && c > *changed)
300 7
                        *changed = c;
301 16
                if (retval)
302 16
                        break;
303 16
        }
304 16
        sharddir_unlock(shardd);
305 16
        return (retval);
306 16
}
307
308
/*
309
 * core function for the director backend/resolve method
310
 */
311
312
static VCL_BACKEND
313
sharddir_pick_be_locked(VRT_CTX, const struct sharddir *shardd, uint32_t key,
314
    VCL_INT alt, VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy,
315
    struct shard_state *state)
316 104
{
317 104
        VCL_BACKEND be;
318 104
        VCL_DURATION chosen_r, alt_r;
319
320 104
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
321 104
        CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
322 104
        AN(ctx->vsl);
323 104
        assert(shardd->n_backend > 0);
324
325 104
        assert(shardd->hashcircle);
326
327 104
        validate_alt(ctx, shardd, &alt);
328
329 104
        state->idx = shard_lookup(shardd, key);
330 104
        assert(state->idx < UINT32_MAX);
331
332 104
        SHDBG(SHDBG_LOOKUP, shardd, "lookup key %x idx %u host %u",
333 104
            key, state->idx, shardd->hashcircle[state->idx].host);
334
335 104
        if (alt > 0) {
336 27
                if (shard_next(state, alt - 1,
337 27
                    healthy == VENUM(ALL) ? 1 : 0) == -1) {
338 0
                        if (state->previous.hostid != UINT_MAX) {
339 0
                                be = sharddir_backend(shardd,
340 0
                                    state->previous.hostid);
341 0
                                AN(be);
342 0
                                return (be);
343 0
                        }
344 0
                        return (NULL);
345 0
                }
346 27
        }
347
348 104
        if (shard_next(state, 0, healthy == VENUM(IGNORE) ? 0 : 1) == -1) {
349 0
                if (state->previous.hostid != UINT_MAX) {
350 0
                        be = sharddir_backend(shardd, state->previous.hostid);
351 0
                        AN(be);
352 0
                        return (be);
353 0
                }
354 0
                return (NULL);
355 0
        }
356
357 104
        be = sharddir_backend(shardd, state->last.hostid);
358 104
        AN(be);
359
360 104
        if (warmup == -1)
361 103
                warmup = shardd->warmup;
362
363
        /* short path for cases we dont want ramup/warmup or can't */
364 104
        if (alt > 0 || healthy == VENUM(IGNORE) || (!rampup && warmup == 0) ||
365 104
            shard_next(state, 0, 1) == -1)
366 31
                return (be);
367
368 73
        assert(alt == 0);
369 73
        assert(state->previous.hostid != UINT_MAX);
370 73
        assert(state->last.hostid != UINT_MAX);
371 73
        assert(state->previous.hostid != state->last.hostid);
372 73
        assert(be == sharddir_backend(shardd, state->previous.hostid));
373
374 73
        chosen_r = shardcfg_get_rampup(shardd, state->previous.hostid);
375 73
        alt_r = shardcfg_get_rampup(shardd, state->last.hostid);
376
377 73
        SHDBG(SHDBG_RAMPWARM, shardd, "chosen host %u rampup %f changed %f",
378 73
            state->previous.hostid, chosen_r,
379 73
            ctx->now - state->previous.changed);
380 73
        SHDBG(SHDBG_RAMPWARM, shardd, "alt host %u rampup %f changed %f",
381 73
            state->last.hostid, alt_r,
382 73
            ctx->now - state->last.changed);
383
384 73
        if (ctx->now - state->previous.changed < chosen_r) {
385
                /*
386
                 * chosen host is in rampup
387
                 * - no change if alternative host is also in rampup or the dice
388
                 *   has rolled in favour of the chosen host
389
                 */
390 2
                if (!rampup ||
391 2
                    ctx->now - state->last.changed < alt_r ||
392 2
                    VRND_RandomTestableDouble() * chosen_r <
393 1
                    (ctx->now - state->previous.changed))
394 1
                        return (be);
395 71
        } else {
396
                /* chosen host not in rampup - warmup ? */
397 71
                if (warmup == 0 || VRND_RandomTestableDouble() > warmup)
398 71
                        return (be);
399 71
        }
400
401 1
        be = sharddir_backend(shardd, state->last.hostid);
402 1
        return (be);
403 73
}
404
405
VCL_BACKEND
406
sharddir_pick_be(VRT_CTX, struct sharddir *shardd, uint32_t key, VCL_INT alt,
407
    VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy)
408 104
{
409 104
        VCL_BACKEND be;
410 104
        struct shard_state state[1];
411 104
        unsigned picklist_sz;
412
413 104
        CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
414 104
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
415
416 104
        sharddir_rdlock(shardd);
417
418 104
        if (shardd->n_backend == 0) {
419 0
                shard_err0(ctx->vsl, shardd->name, "no backends");
420 0
                sharddir_unlock(shardd);
421 0
                return (NULL);
422 0
        }
423
424 104
        picklist_sz = VBITMAP_SZ(shardd->n_backend);
425 104
        char picklist_spc[picklist_sz];
426
427 104
        memset(state, 0, sizeof(state));
428 104
        init_state(state, ctx, shardd, vbit_init(picklist_spc, picklist_sz));
429
430 104
        be = sharddir_pick_be_locked(ctx, shardd, key, alt, warmup, rampup,
431 104
            healthy, state);
432 104
        sharddir_unlock(shardd);
433
434 104
        vbit_destroy(state->picklist);
435 104
        return (be);
436 104
}