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 --e{801} */

#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)
                                vmemcpy(&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=%jd, set to 0",
                    (intmax_t)*alt);
                *alt = 0;
        } else if (*alt > alt_max) {
                shard_err(ctx->vsl, shardd->name,
                    "parameter alt=%jd limited to %jd", (intmax_t)*alt,
                    (intmax_t)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);
}

		vinyl-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 --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	147	sharddir_debug(struct sharddir *shardd, const uint32_t flags)
74		{
75	147	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
76	147	shardd->debug_flags = flags;
77	147	}
78
79		void
80	441	sharddir_log(struct vsl_log vsl, enum VSL_tag_e tag, const char fmt, ...)
81		{
82		va_list ap;
83
84	441	va_start(ap, fmt);
85	441	if (vsl != NULL)
86	210	VSLbv(vsl, tag, fmt, ap);
87		else
88	231	VSLv(tag, NO_VXID, fmt, ap);
89	441	va_end(ap);
90	441	}
91
92		static int
93	2184	shard_lookup(const struct sharddir *shardd, const uint32_t key)
94		{
95	2184	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
96
97	2184	const uint32_t n = shardd->n_points;
98	2184	uint32_t i, idx = UINT32_MAX, high = n, low = 0;
99
100	2184	assert (n < idx);
101
102	2184	do {
103	13335	i = (high + low) / 2 ;
104	13335	if (shardd->hashcircle[i].point == key)
105	21	idx = i;
106	13314	else if (i == n - 1)
107	378	idx = n - 1;
108	12936	else if (shardd->hashcircle[i].point < key &&
109	6846	shardd->hashcircle[i+1].point >= key)
110	1428	idx = i + 1;
111	11508	else if (shardd->hashcircle[i].point > key)
112	12180	if (i == 0)
113	357	idx = 0;
114		else
115	5733	high = i;
116		else
117	5418	low = i;
118	13335	} while (idx == UINT32_MAX);
119
120	2184	return (idx);
121		}
122
123		static int
124	4368	shard_next(struct shard_state *state, VCL_INT skip, VCL_BOOL healthy)
125		{
126	4368	int c, chosen = -1;
127		VCL_BACKEND be;
128		vtim_real changed;
129		struct shard_be_info *sbe;
130
131	4368	AN(state);
132	4368	CHECK_OBJ_NOTNULL(state->shardd, SHARDDIR_MAGIC);
133
134	4368	if (state->pickcount >= state->shardd->n_backend)
135	63	return (-1);
136
137	6888	while (state->pickcount < state->shardd->n_backend && skip >= 0) {
138
139	6867	c = state->shardd->hashcircle[state->idx].host;
140
141	6867	if (!vbit_test(state->picklist, c)) {
142
143	4620	vbit_set(state->picklist, c);
144	4620	state->pickcount++;
145
146	4620	sbe = NULL;
147	4620	be = state->shardd->backend[c].backend;
148	4620	AN(be);
149	4620	if (VRT_Healthy(state->ctx, be, &changed)) {
150	4494	if (skip-- == 0) {
151	4284	chosen = c;
152	4284	sbe = &state->last;
153	4284	} else {
154	210	sbe = &state->previous;
155		}
156
157	4620	} else if (!healthy && skip-- == 0) {
158	0	chosen = c;
159	0	sbe = &state->last;
160	0	}
161	4620	if (sbe == &state->last &&
162	4284	state->last.hostid != UINT_MAX)
163	2100	vmemcpy(&state->previous, &state->last,
164		sizeof(state->previous));
165
166	4620	if (sbe) {
167	4494	sbe->hostid = c;
168	4494	sbe->healthy = 1;
169	4494	sbe->changed = changed;
170	4494	}
171	4620	if (chosen != -1)
172	4284	break;
173	336	}
174
175	2583	if (++(state->idx) == state->shardd->n_points)
176	399	state->idx = 0;
177		}
178	4305	return (chosen);
179	4368	}
180
181		void
182	525	sharddir_new(struct sharddir *sharddp, const char vcl_name,
183		const struct vmod_directors_shard_param *param)
184		{
185		struct sharddir *shardd;
186
187	525	AN(vcl_name);
188	525	AN(sharddp);
189	525	AZ(*sharddp);
190	525	ALLOC_OBJ(shardd, SHARDDIR_MAGIC);
191	525	AN(shardd);
192	525	*sharddp = shardd;
193	525	shardd->name = vcl_name;
194	525	shardd->param = param;
195	525	PTOK(pthread_rwlock_init(&shardd->mtx, NULL));
196	525	}
197
198		void
199	63	sharddir_set_param(struct sharddir *shardd,
200		const struct vmod_directors_shard_param *param)
201		{
202	63	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
203	63	shardd->param = param;
204	63	}
205
206		void
207	105	sharddir_release(struct sharddir *shardd)
208		{
209	105	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
210	105	shardcfg_backend_clear(shardd);
211	105	}
212
213		void
214	105	sharddir_delete(struct sharddir **sharddp)
215		{
216		struct sharddir *shardd;
217
218	105	TAKE_OBJ_NOTNULL(shardd, sharddp, SHARDDIR_MAGIC);
219	105	shardcfg_delete(shardd);
220	105	PTOK(pthread_rwlock_destroy(&shardd->mtx));
221	105	FREE_OBJ(shardd);
222	105	}
223
224		void
225	3150	sharddir_rdlock(struct sharddir *shardd)
226		{
227	3150	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
228	3150	PTOK(pthread_rwlock_rdlock(&shardd->mtx));
229	3150	}
230
231		void
232	924	sharddir_wrlock(struct sharddir *shardd)
233		{
234	924	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
235	924	PTOK(pthread_rwlock_wrlock(&shardd->mtx));
236	924	}
237
238		void
239	4074	sharddir_unlock(struct sharddir *shardd)
240		{
241	4074	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
242	4074	PTOK(pthread_rwlock_unlock(&shardd->mtx));
243	4074	}
244
245		static inline void
246	2184	validate_alt(VRT_CTX, const struct sharddir shardd, VCL_INT alt)
247		{
248	2184	const VCL_INT alt_max = shardd->n_backend - 1;
249
250	2184	if (*alt < 0) {
251	0	shard_err(ctx->vsl, shardd->name,
252		"invalid negative parameter alt=%jd, set to 0",
253		(intmax_t)*alt);
254	0	*alt = 0;
255	2184	} else if (*alt > alt_max) {
256	63	shard_err(ctx->vsl, shardd->name,
257		"parameter alt=%jd limited to %jd", (intmax_t)*alt,
258		(intmax_t)alt_max);
259	63	*alt = alt_max;
260	63	}
261	2184	}
262
263		static inline void
264	2184	init_state(struct shard_state *state,
265		VRT_CTX, struct sharddir shardd, struct vbitmap picklist)
266		{
267	2184	AN(picklist);
268
269	2184	state->ctx = ctx;
270	2184	state->shardd = shardd;
271	2184	state->idx = UINT32_MAX;
272	2184	state->picklist = picklist;
273
274		/* healthy and changed only defined for valid hostids */
275	2184	state->previous.hostid = UINT_MAX;
276	2184	state->last.hostid = UINT_MAX;
277	2184	}
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	336	sharddir_any_healthy(VRT_CTX, struct sharddir shardd, VCL_TIME changed)
286		{
287	336	unsigned i, retval = 0;
288		VCL_BACKEND be;
289		vtim_real c;
290
291	336	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
292	336	sharddir_rdlock(shardd);
293	336	if (changed != NULL)
294	147	*changed = 0;
295	336	for (i = 0; i < shardd->n_backend; i++) {
296	336	be = shardd->backend[i].backend;
297	336	CHECK_OBJ_NOTNULL(be, DIRECTOR_MAGIC);
298	336	retval = VRT_Healthy(ctx, be, &c);
299	336	if (changed != NULL && c > *changed)
300	147	*changed = c;
301	336	if (retval)
302	336	break;
303	0	}
304	336	sharddir_unlock(shardd);
305	336	return (retval);
306		}
307
308		/*
309		* core function for the director backend/resolve method
310		*/
311
312		static VCL_BACKEND
313	2184	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		{
317		VCL_BACKEND be;
318		VCL_DURATION chosen_r, alt_r;
319
320	2184	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
321	2184	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
322	2184	AN(ctx->vsl);
323	2184	assert(shardd->n_backend > 0);
324
325	2184	assert(shardd->hashcircle);
326
327	2184	validate_alt(ctx, shardd, &alt);
328
329	2184	state->idx = shard_lookup(shardd, key);
330	2184	assert(state->idx < UINT32_MAX);
331
332	2184	SHDBG(SHDBG_LOOKUP, shardd, "lookup key %x idx %u host %u",
333		key, state->idx, shardd->hashcircle[state->idx].host);
334
335	2184	if (alt > 0) {
336	1701	if (shard_next(state, alt - 1,
337	1134	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		}
344	0	return (NULL);
345		}
346	567	}
347
348	2184	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		}
354	0	return (NULL);
355		}
356
357	2184	be = sharddir_backend(shardd, state->last.hostid);
358	2184	AN(be);
359
360	2184	if (warmup == -1)
361	2163	warmup = shardd->warmup;
362
363		/* short path for cases we dont want ramup/warmup or can't */
364	2184	if (alt > 0 \|\| healthy == VENUM(IGNORE) \|\| (!rampup && warmup == 0) \|\|
365	1617	shard_next(state, 0, 1) == -1)
366	651	return (be);
367
368	1533	assert(alt == 0);
369	1533	assert(state->previous.hostid != UINT_MAX);
370	1533	assert(state->last.hostid != UINT_MAX);
371	1533	assert(state->previous.hostid != state->last.hostid);
372	1533	assert(be == sharddir_backend(shardd, state->previous.hostid));
373
374	1533	chosen_r = shardcfg_get_rampup(shardd, state->previous.hostid);
375	1533	alt_r = shardcfg_get_rampup(shardd, state->last.hostid);
376
377	1533	SHDBG(SHDBG_RAMPWARM, shardd, "chosen host %u rampup %f changed %f",
378		state->previous.hostid, chosen_r,
379		ctx->now - state->previous.changed);
380	1533	SHDBG(SHDBG_RAMPWARM, shardd, "alt host %u rampup %f changed %f",
381		state->last.hostid, alt_r,
382		ctx->now - state->last.changed);
383
384	1533	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	63	if (!rampup \|\|
391	42	ctx->now - state->last.changed < alt_r \|\|
392	42	VRND_RandomTestableDouble() * chosen_r <
393	21	(ctx->now - state->previous.changed))
394	21	return (be);
395	21	} else {
396		/* chosen host not in rampup - warmup ? */
397	1491	if (warmup == 0 \|\| VRND_RandomTestableDouble() > warmup)
398	1491	return (be);
399		}
400
401	21	be = sharddir_backend(shardd, state->last.hostid);
402	21	return (be);
403	2184	}
404
405		VCL_BACKEND
406	2184	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		{
409		VCL_BACKEND be;
410		struct shard_state state[1];
411		unsigned picklist_sz;
412
413	2184	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
414	2184	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
415
416	2184	sharddir_rdlock(shardd);
417
418	2184	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		}
423
424	2184	picklist_sz = VBITMAP_SZ(shardd->n_backend);
425	2184	char picklist_spc[picklist_sz];
426
427	2184	memset(state, 0, sizeof(state));
428	2184	init_state(state, ctx, shardd, vbit_init(picklist_spc, picklist_sz));
429
430	4368	be = sharddir_pick_be_locked(ctx, shardd, key, alt, warmup, rampup,
431	2184	healthy, state);
432	2184	sharddir_unlock(shardd);
433
434	2184	vbit_destroy(state->picklist);
435	2184	return (be);
436	2184	}