GCOV - Varnish Cache


/*-
 * Copyright 2009-2016 UPLEX - Nils Goroll Systemoptimierung
 * All rights reserved.
 *
 * Authors: Nils Goroll <nils.goroll@uplex.de>
 *          Geoffrey Simmons <geoff.simmons@uplex.de>
 *          Julian Wiesener <jw@uplex.de>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*lint -e801 */

#include "config.h"

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

#include "cache/cache.h"

#include "vbm.h"
#include "vrnd.h"

#include "vcc_directors_if.h"
#include "vmod_directors_shard_dir.h"

struct shard_be_info {
        unsigned        hostid;
        unsigned        healthy;
        double          changed;        // when
};

/*
 * circle walk state for shard_next
 *
 * pick* cut off the search after having seen all possible backends
 */
struct shard_state {
        const struct vrt_ctx    *ctx;
        struct sharddir *shardd;
        uint32_t                idx;

        struct vbitmap          *picklist;
        unsigned                pickcount;

        struct shard_be_info    previous;
        struct shard_be_info    last;
};

void
sharddir_debug(struct sharddir *shardd, const uint32_t flags)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        shardd->debug_flags = flags;
}

void
sharddir_log(struct vsl_log *vsl, enum VSL_tag_e tag,  const char *fmt, ...)
{
        va_list ap;

        va_start(ap, fmt);
        if (vsl != NULL)
                VSLbv(vsl, tag, fmt, ap);
        else
                VSLv(tag, NO_VXID, fmt, ap);
        va_end(ap);
}

static int
shard_lookup(const struct sharddir *shardd, const uint32_t key)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);

        const uint32_t n = shardd->n_points;
        uint32_t i, idx = UINT32_MAX, high = n, low = 0;

        assert (n < idx);

        do {
            i = (high + low) / 2 ;
            if (shardd->hashcircle[i].point == key)
                idx = i;
            else if (i == n - 1)
                idx = n - 1;
            else if (shardd->hashcircle[i].point < key &&
                     shardd->hashcircle[i+1].point >= key)
                idx = i + 1;
            else if (shardd->hashcircle[i].point > key)
                if (i == 0)
                    idx = 0;
                else
                    high = i;
            else
                low = i;
        } while (idx == UINT32_MAX);

        return (idx);
}

static int
shard_next(struct shard_state *state, VCL_INT skip, VCL_BOOL healthy)
{
        int c, chosen = -1;
        VCL_BACKEND be;
        vtim_real changed;
        struct shard_be_info *sbe;

        AN(state);
        CHECK_OBJ_NOTNULL(state->shardd, SHARDDIR_MAGIC);

        if (state->pickcount >= state->shardd->n_backend)
                return (-1);

        while (state->pickcount < state->shardd->n_backend && skip >= 0) {

                c = state->shardd->hashcircle[state->idx].host;

                if (!vbit_test(state->picklist, c)) {

                        vbit_set(state->picklist, c);
                        state->pickcount++;

                        sbe = NULL;
                        be = state->shardd->backend[c].backend;
                        AN(be);
                        if (VRT_Healthy(state->ctx, be, &changed)) {
                                if (skip-- == 0) {
                                        chosen = c;
                                        sbe = &state->last;
                                } else {
                                        sbe = &state->previous;
                                }

                        } else if (!healthy && skip-- == 0) {
                                chosen = c;
                                sbe = &state->last;
                        }
                        if (sbe == &state->last &&
                            state->last.hostid != UINT_MAX)
                                memcpy(&state->previous, &state->last,
                                    sizeof(state->previous));

                        if (sbe) {
                                sbe->hostid = c;
                                sbe->healthy = 1;
                                sbe->changed = changed;
                        }
                        if (chosen != -1)
                                break;
                }

                if (++(state->idx) == state->shardd->n_points)
                        state->idx = 0;
        }
        return (chosen);
}

void
sharddir_new(struct sharddir **sharddp, const char *vcl_name,
    const struct vmod_directors_shard_param *param)
{
        struct sharddir *shardd;

        AN(vcl_name);
        AN(sharddp);
        AZ(*sharddp);
        ALLOC_OBJ(shardd, SHARDDIR_MAGIC);
        AN(shardd);
        *sharddp = shardd;
        shardd->name = vcl_name;
        shardd->param = param;
        PTOK(pthread_rwlock_init(&shardd->mtx, NULL));
}

void
sharddir_set_param(struct sharddir *shardd,
    const struct vmod_directors_shard_param *param)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        shardd->param = param;
}

void
sharddir_release(struct sharddir *shardd)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        shardcfg_backend_clear(shardd);
}

void
sharddir_delete(struct sharddir **sharddp)
{
        struct sharddir *shardd;

        TAKE_OBJ_NOTNULL(shardd, sharddp, SHARDDIR_MAGIC);
        shardcfg_delete(shardd);
        PTOK(pthread_rwlock_destroy(&shardd->mtx));
        FREE_OBJ(shardd);
}

void
sharddir_rdlock(struct sharddir *shardd)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        PTOK(pthread_rwlock_rdlock(&shardd->mtx));
}

void
sharddir_wrlock(struct sharddir *shardd)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        PTOK(pthread_rwlock_wrlock(&shardd->mtx));
}

void
sharddir_unlock(struct sharddir *shardd)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        PTOK(pthread_rwlock_unlock(&shardd->mtx));
}

static inline void
validate_alt(VRT_CTX, const struct sharddir *shardd, VCL_INT *alt)
{
        const VCL_INT alt_max = shardd->n_backend - 1;

        if (*alt < 0) {
                shard_err(ctx->vsl, shardd->name,
                    "invalid negative parameter alt=%ld, set to 0", *alt);
                *alt = 0;
        } else if (*alt > alt_max) {
                shard_err(ctx->vsl, shardd->name,
                    "parameter alt=%ld limited to %ld", *alt, alt_max);
                *alt = alt_max;
        }
}

static inline void
init_state(struct shard_state *state,
    VRT_CTX, struct sharddir *shardd, struct vbitmap *picklist)
{
        AN(picklist);

        state->ctx = ctx;
        state->shardd = shardd;
        state->idx = UINT32_MAX;
        state->picklist = picklist;

        /* healthy and changed only defined for valid hostids */
        state->previous.hostid = UINT_MAX;
        state->last.hostid = UINT_MAX;
}

/* basically same as vdir_any_healthy
 * - XXX we should embed a vdir
 * - XXX should we return the health state of the actual backend
 *   for healthy=IGNORE ?
 */
VCL_BOOL
sharddir_any_healthy(VRT_CTX, struct sharddir *shardd, VCL_TIME *changed)
{
        unsigned i, retval = 0;
        VCL_BACKEND be;
        vtim_real c;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        sharddir_rdlock(shardd);
        if (changed != NULL)
                *changed = 0;
        for (i = 0; i < shardd->n_backend; i++) {
                be = shardd->backend[i].backend;
                CHECK_OBJ_NOTNULL(be, DIRECTOR_MAGIC);
                retval = VRT_Healthy(ctx, be, &c);
                if (changed != NULL && c > *changed)
                        *changed = c;
                if (retval)
                        break;
        }
        sharddir_unlock(shardd);
        return (retval);
}

/*
 * core function for the director backend/resolve method
 */

static VCL_BACKEND
sharddir_pick_be_locked(VRT_CTX, const struct sharddir *shardd, uint32_t key,
    VCL_INT alt, VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy,
    struct shard_state *state)
{
        VCL_BACKEND be;
        VCL_DURATION chosen_r, alt_r;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
        AN(ctx->vsl);
        assert(shardd->n_backend > 0);

        assert(shardd->hashcircle);

        validate_alt(ctx, shardd, &alt);

        state->idx = shard_lookup(shardd, key);
        assert(state->idx < UINT32_MAX);

        SHDBG(SHDBG_LOOKUP, shardd, "lookup key %x idx %u host %u",
            key, state->idx, shardd->hashcircle[state->idx].host);

        if (alt > 0) {
                if (shard_next(state, alt - 1,
                    healthy == VENUM(ALL) ? 1 : 0) == -1) {
                        if (state->previous.hostid != UINT_MAX) {
                                be = sharddir_backend(shardd,
                                    state->previous.hostid);
                                AN(be);
                                return (be);
                        }
                        return (NULL);
                }
        }

        if (shard_next(state, 0, healthy == VENUM(IGNORE) ? 0 : 1) == -1) {
                if (state->previous.hostid != UINT_MAX) {
                        be = sharddir_backend(shardd, state->previous.hostid);
                        AN(be);
                        return (be);
                }
                return (NULL);
        }

        be = sharddir_backend(shardd, state->last.hostid);
        AN(be);

        if (warmup == -1)
                warmup = shardd->warmup;

        /* short path for cases we dont want ramup/warmup or can't */
        if (alt > 0 || healthy == VENUM(IGNORE) || (!rampup && warmup == 0) ||
            shard_next(state, 0, 1) == -1)
                return (be);

        assert(alt == 0);
        assert(state->previous.hostid != UINT_MAX);
        assert(state->last.hostid != UINT_MAX);
        assert(state->previous.hostid != state->last.hostid);
        assert(be == sharddir_backend(shardd, state->previous.hostid));

        chosen_r = shardcfg_get_rampup(shardd, state->previous.hostid);
        alt_r = shardcfg_get_rampup(shardd, state->last.hostid);

        SHDBG(SHDBG_RAMPWARM, shardd, "chosen host %u rampup %f changed %f",
            state->previous.hostid, chosen_r,
            ctx->now - state->previous.changed);
        SHDBG(SHDBG_RAMPWARM, shardd, "alt host %u rampup %f changed %f",
            state->last.hostid, alt_r,
            ctx->now - state->last.changed);

        if (ctx->now - state->previous.changed < chosen_r) {
                /*
                 * chosen host is in rampup
                 * - no change if alternative host is also in rampup or the dice
                 *   has rolled in favour of the chosen host
                 */
                if (!rampup ||
                    ctx->now - state->last.changed < alt_r ||
                    VRND_RandomTestableDouble() * chosen_r <
                    (ctx->now - state->previous.changed))
                        return (be);
        } else {
                /* chosen host not in rampup - warmup ? */
                if (warmup == 0 || VRND_RandomTestableDouble() > warmup)
                        return (be);
        }

        be = sharddir_backend(shardd, state->last.hostid);
        return (be);
}

VCL_BACKEND
sharddir_pick_be(VRT_CTX, struct sharddir *shardd, uint32_t key, VCL_INT alt,
    VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy)
{
        VCL_BACKEND be;
        struct shard_state state[1];
        unsigned picklist_sz;

        CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);

        sharddir_rdlock(shardd);

        if (shardd->n_backend == 0) {
                shard_err0(ctx->vsl, shardd->name, "no backends");
                sharddir_unlock(shardd);
                return (NULL);
        }

        picklist_sz = VBITMAP_SZ(shardd->n_backend);
        char picklist_spc[picklist_sz];

        memset(state, 0, sizeof(state));
        init_state(state, ctx, shardd, vbit_init(picklist_spc, picklist_sz));

        be = sharddir_pick_be_locked(ctx, shardd, key, alt, warmup, rampup,
            healthy, state);
        sharddir_unlock(shardd);

        vbit_destroy(state->picklist);
        return (be);
}

		varnish-cache/vmod/vmod_directors_shard_dir.c
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 -e801 /
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	266	sharddir_debug(struct sharddir *shardd, const uint32_t flags)
74		{
75	266	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
76	266	shardd->debug_flags = flags;
77	266	}
78
79		void
80	798	sharddir_log(struct vsl_log vsl, enum VSL_tag_e tag, const char fmt, ...)
81		{
82		va_list ap;
83
84	798	va_start(ap, fmt);
85	798	if (vsl != NULL)
86	380	VSLbv(vsl, tag, fmt, ap);
87		else
88	418	VSLv(tag, NO_VXID, fmt, ap);
89	798	va_end(ap);
90	798	}
91
92		static int
93	3952	shard_lookup(const struct sharddir *shardd, const uint32_t key)
94		{
95	3952	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
96
97	3952	const uint32_t n = shardd->n_points;
98	3952	uint32_t i, idx = UINT32_MAX, high = n, low = 0;
99
100	3952	assert (n < idx);
101
102	3952	do {
103	24130	i = (high + low) / 2 ;
104	24130	if (shardd->hashcircle[i].point == key)
105	38	idx = i;
106	24092	else if (i == n - 1)
107	684	idx = n - 1;
108	23408	else if (shardd->hashcircle[i].point < key &&
109	12388	shardd->hashcircle[i+1].point >= key)
110	2584	idx = i + 1;
111	20824	else if (shardd->hashcircle[i].point > key)
112	22040	if (i == 0)
113	646	idx = 0;
114		else
115	10374	high = i;
116		else
117	9804	low = i;
118	24130	} while (idx == UINT32_MAX);
119
120	3952	return (idx);
121		}
122
123		static int
124	7904	shard_next(struct shard_state *state, VCL_INT skip, VCL_BOOL healthy)
125		{
126	7904	int c, chosen = -1;
127		VCL_BACKEND be;
128		vtim_real changed;
129		struct shard_be_info *sbe;
130
131	7904	AN(state);
132	7904	CHECK_OBJ_NOTNULL(state->shardd, SHARDDIR_MAGIC);
133
134	7904	if (state->pickcount >= state->shardd->n_backend)
135	114	return (-1);
136
137	12464	while (state->pickcount < state->shardd->n_backend && skip >= 0) {
138
139	12426	c = state->shardd->hashcircle[state->idx].host;
140
141	12426	if (!vbit_test(state->picklist, c)) {
142
143	8360	vbit_set(state->picklist, c);
144	8360	state->pickcount++;
145
146	8360	sbe = NULL;
147	8360	be = state->shardd->backend[c].backend;
148	8360	AN(be);
149	8360	if (VRT_Healthy(state->ctx, be, &changed)) {
150	8132	if (skip-- == 0) {
151	7752	chosen = c;
152	7752	sbe = &state->last;
153	7752	} else {
154	380	sbe = &state->previous;
155		}
156
157	8360	} else if (!healthy && skip-- == 0) {
158	0	chosen = c;
159	0	sbe = &state->last;
160	0	}
161	8360	if (sbe == &state->last &&
162	7752	state->last.hostid != UINT_MAX)
163	3800	memcpy(&state->previous, &state->last,
164		sizeof(state->previous));
165
166	8360	if (sbe) {
167	8132	sbe->hostid = c;
168	8132	sbe->healthy = 1;
169	8132	sbe->changed = changed;
170	8132	}
171	8360	if (chosen != -1)
172	7752	break;
173	608	}
174
175	4674	if (++(state->idx) == state->shardd->n_points)
176	722	state->idx = 0;
177		}
178	7790	return (chosen);
179	7904	}
180
181		void
182	950	sharddir_new(struct sharddir *sharddp, const char vcl_name,
183		const struct vmod_directors_shard_param *param)
184		{
185		struct sharddir *shardd;
186
187	950	AN(vcl_name);
188	950	AN(sharddp);
189	950	AZ(*sharddp);
190	950	ALLOC_OBJ(shardd, SHARDDIR_MAGIC);
191	950	AN(shardd);
192	950	*sharddp = shardd;
193	950	shardd->name = vcl_name;
194	950	shardd->param = param;
195	950	PTOK(pthread_rwlock_init(&shardd->mtx, NULL));
196	950	}
197
198		void
199	114	sharddir_set_param(struct sharddir *shardd,
200		const struct vmod_directors_shard_param *param)
201		{
202	114	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
203	114	shardd->param = param;
204	114	}
205
206		void
207	190	sharddir_release(struct sharddir *shardd)
208		{
209	190	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
210	190	shardcfg_backend_clear(shardd);
211	190	}
212
213		void
214	190	sharddir_delete(struct sharddir **sharddp)
215		{
216		struct sharddir *shardd;
217
218	190	TAKE_OBJ_NOTNULL(shardd, sharddp, SHARDDIR_MAGIC);
219	190	shardcfg_delete(shardd);
220	190	PTOK(pthread_rwlock_destroy(&shardd->mtx));
221	190	FREE_OBJ(shardd);
222	190	}
223
224		void
225	5700	sharddir_rdlock(struct sharddir *shardd)
226		{
227	5700	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
228	5700	PTOK(pthread_rwlock_rdlock(&shardd->mtx));
229	5700	}
230
231		void
232	1672	sharddir_wrlock(struct sharddir *shardd)
233		{
234	1672	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
235	1672	PTOK(pthread_rwlock_wrlock(&shardd->mtx));
236	1672	}
237
238		void
239	7372	sharddir_unlock(struct sharddir *shardd)
240		{
241	7372	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
242	7372	PTOK(pthread_rwlock_unlock(&shardd->mtx));
243	7372	}
244
245		static inline void
246	3952	validate_alt(VRT_CTX, const struct sharddir shardd, VCL_INT alt)
247		{
248	3952	const VCL_INT alt_max = shardd->n_backend - 1;
249
250	3952	if (*alt < 0) {
251	0	shard_err(ctx->vsl, shardd->name,
252		"invalid negative parameter alt=%ld, set to 0", *alt);
253	0	*alt = 0;
254	3952	} else if (*alt > alt_max) {
255	114	shard_err(ctx->vsl, shardd->name,
256		"parameter alt=%ld limited to %ld", *alt, alt_max);
257	114	*alt = alt_max;
258	114	}
259	3952	}
260
261		static inline void
262	3952	init_state(struct shard_state *state,
263		VRT_CTX, struct sharddir shardd, struct vbitmap picklist)
264		{
265	3952	AN(picklist);
266
267	3952	state->ctx = ctx;
268	3952	state->shardd = shardd;
269	3952	state->idx = UINT32_MAX;
270	3952	state->picklist = picklist;
271
272		/* healthy and changed only defined for valid hostids */
273	3952	state->previous.hostid = UINT_MAX;
274	3952	state->last.hostid = UINT_MAX;
275	3952	}
276
277		/* basically same as vdir_any_healthy
278		* - XXX we should embed a vdir
279		* - XXX should we return the health state of the actual backend
280		* for healthy=IGNORE ?
281		*/
282		VCL_BOOL
283	608	sharddir_any_healthy(VRT_CTX, struct sharddir shardd, VCL_TIME changed)
284		{
285	608	unsigned i, retval = 0;
286		VCL_BACKEND be;
287		vtim_real c;
288
289	608	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
290	608	sharddir_rdlock(shardd);
291	608	if (changed != NULL)
292	266	*changed = 0;
293	608	for (i = 0; i < shardd->n_backend; i++) {
294	608	be = shardd->backend[i].backend;
295	608	CHECK_OBJ_NOTNULL(be, DIRECTOR_MAGIC);
296	608	retval = VRT_Healthy(ctx, be, &c);
297	608	if (changed != NULL && c > *changed)
298	266	*changed = c;
299	608	if (retval)
300	608	break;
301	0	}
302	608	sharddir_unlock(shardd);
303	608	return (retval);
304		}
305
306		/*
307		* core function for the director backend/resolve method
308		*/
309
310		static VCL_BACKEND
311	3952	sharddir_pick_be_locked(VRT_CTX, const struct sharddir *shardd, uint32_t key,
312		VCL_INT alt, VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy,
313		struct shard_state *state)
314		{
315		VCL_BACKEND be;
316		VCL_DURATION chosen_r, alt_r;
317
318	3952	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
319	3952	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
320	3952	AN(ctx->vsl);
321	3952	assert(shardd->n_backend > 0);
322
323	3952	assert(shardd->hashcircle);
324
325	3952	validate_alt(ctx, shardd, &alt);
326
327	3952	state->idx = shard_lookup(shardd, key);
328	3952	assert(state->idx < UINT32_MAX);
329
330	3952	SHDBG(SHDBG_LOOKUP, shardd, "lookup key %x idx %u host %u",
331		key, state->idx, shardd->hashcircle[state->idx].host);
332
333	3952	if (alt > 0) {
334	3078	if (shard_next(state, alt - 1,
335	2052	healthy == VENUM(ALL) ? 1 : 0) == -1) {
336	0	if (state->previous.hostid != UINT_MAX) {
337	0	be = sharddir_backend(shardd,
338	0	state->previous.hostid);
339	0	AN(be);
340	0	return (be);
341		}
342	0	return (NULL);
343		}
344	1026	}
345
346	3952	if (shard_next(state, 0, healthy == VENUM(IGNORE) ? 0 : 1) == -1) {
347	0	if (state->previous.hostid != UINT_MAX) {
348	0	be = sharddir_backend(shardd, state->previous.hostid);
349	0	AN(be);
350	0	return (be);
351		}
352	0	return (NULL);
353		}
354
355	3952	be = sharddir_backend(shardd, state->last.hostid);
356	3952	AN(be);
357
358	3952	if (warmup == -1)
359	3914	warmup = shardd->warmup;
360
361		/* short path for cases we dont want ramup/warmup or can't */
362	3952	if (alt > 0 \|\| healthy == VENUM(IGNORE) \|\| (!rampup && warmup == 0) \|\|
363	2926	shard_next(state, 0, 1) == -1)
364	1178	return (be);
365
366	2774	assert(alt == 0);
367	2774	assert(state->previous.hostid != UINT_MAX);
368	2774	assert(state->last.hostid != UINT_MAX);
369	2774	assert(state->previous.hostid != state->last.hostid);
370	2774	assert(be == sharddir_backend(shardd, state->previous.hostid));
371
372	2774	chosen_r = shardcfg_get_rampup(shardd, state->previous.hostid);
373	2774	alt_r = shardcfg_get_rampup(shardd, state->last.hostid);
374
375	2774	SHDBG(SHDBG_RAMPWARM, shardd, "chosen host %u rampup %f changed %f",
376		state->previous.hostid, chosen_r,
377		ctx->now - state->previous.changed);
378	2774	SHDBG(SHDBG_RAMPWARM, shardd, "alt host %u rampup %f changed %f",
379		state->last.hostid, alt_r,
380		ctx->now - state->last.changed);
381
382	2774	if (ctx->now - state->previous.changed < chosen_r) {
383		/*
384		* chosen host is in rampup
385		* - no change if alternative host is also in rampup or the dice
386		* has rolled in favour of the chosen host
387		*/
388	114	if (!rampup \|\|
389	76	ctx->now - state->last.changed < alt_r \|\|
390	76	VRND_RandomTestableDouble() * chosen_r <
391	38	(ctx->now - state->previous.changed))
392	38	return (be);
393	38	} else {
394		/* chosen host not in rampup - warmup ? */
395	2698	if (warmup == 0 \|\| VRND_RandomTestableDouble() > warmup)
396	2698	return (be);
397		}
398
399	38	be = sharddir_backend(shardd, state->last.hostid);
400	38	return (be);
401	3952	}
402
403		VCL_BACKEND
404	3952	sharddir_pick_be(VRT_CTX, struct sharddir *shardd, uint32_t key, VCL_INT alt,
405		VCL_REAL warmup, VCL_BOOL rampup, VCL_ENUM healthy)
406		{
407		VCL_BACKEND be;
408		struct shard_state state[1];
409		unsigned picklist_sz;
410
411	3952	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
412	3952	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
413
414	3952	sharddir_rdlock(shardd);
415
416	3952	if (shardd->n_backend == 0) {
417	0	shard_err0(ctx->vsl, shardd->name, "no backends");
418	0	sharddir_unlock(shardd);
419	0	return (NULL);
420		}
421
422	3952	picklist_sz = VBITMAP_SZ(shardd->n_backend);
423	3952	char picklist_spc[picklist_sz];
424
425	3952	memset(state, 0, sizeof(state));
426	3952	init_state(state, ctx, shardd, vbit_init(picklist_spc, picklist_sz));
427
428	7904	be = sharddir_pick_be_locked(ctx, shardd, key, alt, warmup, rampup,
429	3952	healthy, state);
430	3952	sharddir_unlock(shardd);
431
432	3952	vbit_destroy(state->picklist);
433	3952	return (be);
434	3952	}