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;
        AZ(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_delete(struct sharddir **sharddp)
{
        struct sharddir *shardd;

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

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

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

void
sharddir_unlock(struct sharddir *shardd)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        AZ(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;

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