GCOV - Varnish Cache


/*-
 * Copyright 2009-2016 UPLEX - Nils Goroll Systemoptimierung
 * All rights reserved.
 *
 * Authors: Nils Goroll <nils.goroll@uplex.de>
 *          Geoffrey Simmons <geoff@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.
 */

#include "config.h"

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

#include "cache/cache.h"

#include "vmod_directors_shard_dir.h"
#include "vmod_directors_shard_cfg.h"

/*lint -esym(749,  shard_change_task_e::*) */
enum shard_change_task_e {
        _SHARD_TASK_E_INVALID = 0,
        CLEAR,
        ADD_BE,
        REMOVE_BE,
        _SHARD_TASK_E_MAX
};

struct shard_change_task {
        unsigned                                magic;
#define SHARD_CHANGE_TASK_MAGIC                 0x1e1168af
        enum shard_change_task_e                task;
        void                                    *priv;
        VCL_REAL                                weight;
        VSTAILQ_ENTRY(shard_change_task)        list;
};

struct shard_change {
        unsigned                                magic;
#define SHARD_CHANGE_MAGIC                      0xdff5c9a6
        struct vsl_log                          *vsl;
        struct sharddir                         *shardd;
        VSTAILQ_HEAD(,shard_change_task)        tasks;
};

struct backend_reconfig {
        struct sharddir * const shardd;
        unsigned                hint;   // on number of backends after reconfig
        unsigned                hole_n; // number of holes in backends array
        unsigned                hole_i; // index hint on first hole
};

/* forward decl */
static VCL_BOOL
change_reconfigure(VRT_CTX, struct shard_change *change, VCL_INT replicas);

/*
 * ============================================================
 * change / task list
 *
 * for backend reconfiguration, we create a change list on the VCL workspace in
 * a PRIV_TASK state, which we work in reconfigure.
 */

static void v_matchproto_(vmod_priv_fini_f)
shard_change_fini(VRT_CTX, void * priv)
{
        struct shard_change *change;

        if (priv == NULL)
                return;

        CAST_OBJ_NOTNULL(change, priv, SHARD_CHANGE_MAGIC);

        (void) change_reconfigure(ctx, change, 67);
}

static const struct vmod_priv_methods shard_change_priv_methods[1] = {{
        .magic = VMOD_PRIV_METHODS_MAGIC,
        .type = "vmod_directors_shard_cfg",
        .fini = shard_change_fini
}};

static struct shard_change *
shard_change_get(VRT_CTX, struct sharddir * const shardd)
{
        struct vmod_priv *task;
        struct shard_change *change;
        const void *id = (const char *)shardd + task_off_cfg;

        CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);

        task = VRT_priv_task(ctx, id);
        if (task == NULL) {
                shard_fail(ctx, shardd->name, "%s", "no priv_task");
                return (NULL);
        }

        if (task->priv != NULL) {
                CAST_OBJ_NOTNULL(change, task->priv, SHARD_CHANGE_MAGIC);
                assert (change->vsl == ctx->vsl);
                assert (change->shardd == shardd);
                return (change);
        }

        WS_TASK_ALLOC_OBJ(ctx, change, SHARD_CHANGE_MAGIC);
        if (change == NULL)
                return (NULL);
        change->vsl = ctx->vsl;
        change->shardd = shardd;
        VSTAILQ_INIT(&change->tasks);
        task->priv = change;
        task->methods = shard_change_priv_methods;

        return (change);
}

static void
shard_change_finish(struct shard_change *change)
{
        CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);

        VSTAILQ_INIT(&change->tasks);
}

static struct shard_change_task *
shard_change_task_add(VRT_CTX, struct shard_change *change,
    enum shard_change_task_e task_e, void *priv)
{
        struct shard_change_task *task;

        CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);

        WS_TASK_ALLOC_OBJ(ctx, task, SHARD_CHANGE_TASK_MAGIC);
        if (task == NULL)
                return (NULL);
        task->task = task_e;
        task->priv = priv;
        VSTAILQ_INSERT_TAIL(&change->tasks, task, list);

        return (task);
}

static inline struct shard_change_task *
shard_change_task_backend(VRT_CTX, struct sharddir *shardd,
    enum shard_change_task_e task_e, VCL_BACKEND be, VCL_STRING ident,
    VCL_DURATION rampup)
{
        struct shard_change *change;
        struct shard_backend *b;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        assert(task_e == ADD_BE || task_e == REMOVE_BE);

        change = shard_change_get(ctx, shardd);
        if (change == NULL)
                return (NULL);

        b = WS_Alloc(ctx->ws, sizeof(*b));
        if (b == NULL) {
                shard_fail(ctx, change->shardd->name, "%s",
                    "could not get workspace for task");
                return (NULL);
        }

        b->backend = NULL;
        VRT_Assign_Backend(&b->backend, be);
        b->ident = ident != NULL && *ident != '\0' ? ident : NULL;
        b->rampup = rampup;

        return (shard_change_task_add(ctx, change, task_e, b));
}

/*
 * ============================================================
 * director reconfiguration tasks
 */
VCL_BOOL
shardcfg_add_backend(VRT_CTX, struct sharddir *shardd,
    VCL_BACKEND be, VCL_STRING ident, VCL_DURATION rampup, VCL_REAL weight)
{
        struct shard_change_task *task;

        assert (weight >= 1);
        AN(be);

        task = shard_change_task_backend(ctx, shardd, ADD_BE,
            be, ident, rampup);

        if (task == NULL)
                return (0);

        task->weight = weight;
        return (1);
}

VCL_BOOL
shardcfg_remove_backend(VRT_CTX, struct sharddir *shardd,
    VCL_BACKEND be, VCL_STRING ident)
{
        return (shard_change_task_backend(ctx, shardd, REMOVE_BE,
            be, ident, 0) != NULL);
}

VCL_BOOL
shardcfg_clear(VRT_CTX, struct sharddir *shardd)
{
        struct shard_change *change;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);

        change = shard_change_get(ctx, shardd);
        if (change == NULL)
                return (0);

        return (shard_change_task_add(ctx, change, CLEAR, NULL) != NULL);
}

/*
 * ============================================================
 * consistent hashing circle init
 */

typedef int (*compar)( const void*, const void* );

static int
circlepoint_compare(const struct shard_circlepoint *a,
    const struct shard_circlepoint *b)
{
        return ((a->point == b->point) ? 0 : ((a->point > b->point) ? 1 : -1));
}

static void
shardcfg_hashcircle(struct sharddir *shardd)
{
        const struct shard_backend *backends, *b;
        unsigned h;
        uint32_t i, j, n_points, r, rmax;
        const char *ident;
        const int len = 12; // log10(UINT32_MAX) + 2;
        char s[len];

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        AZ(shardd->hashcircle);

        assert(shardd->n_backend > 0);
        backends=shardd->backend;
        AN(backends);

        n_points = 0;
        rmax = (UINT32_MAX - 1) / shardd->n_backend;
        for (b = backends; b < backends + shardd->n_backend; b++) {
                CHECK_OBJ_NOTNULL(b->backend, DIRECTOR_MAGIC);
                n_points += vmin_t(uint32_t, b->replicas, rmax);
        }

        assert(n_points < UINT32_MAX);

        shardd->n_points = n_points;
        shardd->hashcircle = calloc(n_points, sizeof(struct shard_circlepoint));
        AN(shardd->hashcircle);

        i = 0;
        for (h = 0, b = backends; h < shardd->n_backend; h++, b++) {
                ident = b->ident ? b->ident : VRT_BACKEND_string(b->backend);

                AN(ident);
                assert(ident[0] != '\0');

                r = vmin_t(uint32_t, b->replicas, rmax);

                for (j = 0; j < r; j++) {
                        assert(snprintf(s, len, "%d", j) < len);
                        assert (i < n_points);
                        shardd->hashcircle[i].point =
                            VRT_HashStrands32(TOSTRANDS(2, ident, s));
                        shardd->hashcircle[i].host = h;
                        i++;
                }
        }
        assert (i == n_points);
        qsort( (void *) shardd->hashcircle, n_points,
            sizeof (struct shard_circlepoint), (compar) circlepoint_compare);

        if ((shardd->debug_flags & SHDBG_CIRCLE) == 0)
                return;

        for (i = 0; i < n_points; i++)
                SHDBG(SHDBG_CIRCLE, shardd,
                    "hashcircle[%5jd] = {point = %8x, host = %2u}\n",
                    (intmax_t)i, shardd->hashcircle[i].point,
                    shardd->hashcircle[i].host);
}

/*
 * ============================================================
 * configure the director backends
 */

static void
shardcfg_backend_free(struct shard_backend *f)
{
        if (f->freeptr)
                free (f->freeptr);
        VRT_Assign_Backend(&f->backend, NULL);
        memset(f, 0, sizeof(*f));
}

static void
shardcfg_backend_copyin(struct shard_backend *dst,
    const struct shard_backend *src)
{
        dst->backend = src->backend;
        dst->ident = src->ident ? strdup(src->ident) : NULL;
        dst->rampup = src->rampup;
}

static int
shardcfg_backend_cmp(const struct shard_backend *a,
    const struct shard_backend *b)
{
        const char *ai, *bi;

        ai = a->ident;
        bi = b->ident;

        assert(ai || a->backend);
        assert(bi || b->backend);

        /* vcl_names are unique, so we can compare the backend pointers */
        if (ai == NULL && bi == NULL)
                return (a->backend != b->backend);

        if (ai == NULL)
                ai = VRT_BACKEND_string(a->backend);

        if (bi == NULL)
                bi = VRT_BACKEND_string(b->backend);

        AN(ai);
        AN(bi);
        return (strcmp(ai, bi));
}

/* for removal, we delete all instances if the backend matches */
static int
shardcfg_backend_del_cmp(const struct shard_backend *task,
    const struct shard_backend *b)
{
        assert(task->backend || task->ident);

        if (task->ident == NULL)
                return (task->backend != b->backend);

        return (shardcfg_backend_cmp(task, b));
}

static const struct shard_backend *
shardcfg_backend_lookup(const struct backend_reconfig *re,
    const struct shard_backend *b)
{
        unsigned i, max = re->shardd->n_backend + re->hole_n;
        const struct shard_backend *bb = re->shardd->backend;

        if (max > 0)
                AN(bb);

        for (i = 0; i < max; i++) {
                if (bb[i].backend == NULL)
                        continue;       // hole
                if (!shardcfg_backend_cmp(b, &bb[i]))
                        return (&bb[i]);
        }
        return (NULL);
}

static void
shardcfg_backend_expand(const struct backend_reconfig *re)
{
        unsigned min = re->hint;

        CHECK_OBJ_NOTNULL(re->shardd, SHARDDIR_MAGIC);

        min = vmax_t(unsigned, min, 16);

        if (re->shardd->l_backend < min)
                re->shardd->l_backend = min;
        else
                re->shardd->l_backend *= 2;

        re->shardd->backend = realloc(re->shardd->backend,
            re->shardd->l_backend * sizeof *re->shardd->backend);

        AN(re->shardd->backend);
}

static void
shardcfg_backend_add(struct backend_reconfig *re,
    const struct shard_backend *b, uint32_t replicas)
{
        unsigned i;
        struct shard_backend *bb = re->shardd->backend;

        if (re->hole_n == 0) {
                if (re->shardd->n_backend >= re->shardd->l_backend) {
                        shardcfg_backend_expand(re);
                        bb = re->shardd->backend;
                }
                assert(re->shardd->n_backend < re->shardd->l_backend);
                i = re->shardd->n_backend;
        } else {
                assert(re->hole_i != UINT_MAX);
                do {
                        if (!bb[re->hole_i].backend)
                                break;
                } while (++(re->hole_i) < re->shardd->n_backend + re->hole_n);
                assert(re->hole_i < re->shardd->n_backend + re->hole_n);

                i = (re->hole_i)++;
                (re->hole_n)--;
        }

        re->shardd->n_backend++;
        shardcfg_backend_copyin(&bb[i], b);
        bb[i].replicas = replicas;
}

void
shardcfg_backend_clear(struct sharddir *shardd)
{
        unsigned i;
        for (i = 0; i < shardd->n_backend; i++)
                shardcfg_backend_free(&shardd->backend[i]);
        shardd->n_backend = 0;
}


static void
shardcfg_backend_del(struct backend_reconfig *re, struct shard_backend *spec)
{
        unsigned i, max = re->shardd->n_backend + re->hole_n;
        struct shard_backend * const bb = re->shardd->backend;

        for (i = 0; i < max; i++) {
                if (bb[i].backend == NULL)
                        continue;       // hole
                if (shardcfg_backend_del_cmp(spec, &bb[i]))
                        continue;

                shardcfg_backend_free(&bb[i]);
                re->shardd->n_backend--;
                if (i < re->shardd->n_backend + re->hole_n) {
                        (re->hole_n)++;
                        re->hole_i = vmin(re->hole_i, i);
                }
        }
        VRT_Assign_Backend(&spec->backend, NULL);
}

static void
shardcfg_backend_finalize(struct backend_reconfig *re)
{
        unsigned i;
        struct shard_backend * const bb = re->shardd->backend;

        while (re->hole_n > 0) {
                // trim end
                i = re->shardd->n_backend + re->hole_n - 1;
                while (re->hole_n && bb[i].backend == NULL) {
                        (re->hole_n)--;
                        i--;
                }

                if (re->hole_n == 0)
                        break;

                assert(re->hole_i < i);

                do {
                        if (!bb[re->hole_i].backend)
                                break;
                } while (++(re->hole_i) <= i);

                assert(re->hole_i < i);
                assert(bb[re->hole_i].backend == NULL);
                assert(bb[i].backend != NULL);

                memcpy(&bb[re->hole_i], &bb[i], sizeof(*bb));
                memset(&bb[i], 0, sizeof(*bb));

                (re->hole_n)--;
                (re->hole_i)++;
        }

        assert(re->hole_n == 0);
}

/*
 * ============================================================
 * work the change tasks
 */

static void
shardcfg_apply_change(struct vsl_log *vsl, struct sharddir *shardd,
    const struct shard_change *change, VCL_INT replicas)
{
        struct shard_change_task *task, *clear;
        const struct shard_backend *b;
        uint32_t b_replicas;

        struct backend_reconfig re = {
                .shardd = shardd,
                .hint = shardd->n_backend,
                .hole_n = 0,
                .hole_i = UINT_MAX
        };

        // XXX assert sharddir_locked(shardd)

        clear = NULL;
        VSTAILQ_FOREACH(task, &change->tasks, list) {
                CHECK_OBJ_NOTNULL(task, SHARD_CHANGE_TASK_MAGIC);
                switch (task->task) {
                case CLEAR:
                        clear = task;
                        re.hint = 0;
                        break;
                case ADD_BE:
                        re.hint++;
                        break;
                case REMOVE_BE:
                        break;
                default:
                        INCOMPL();
                }
        }

        if (clear) {
                shardcfg_backend_clear(shardd);
                clear = VSTAILQ_NEXT(clear, list);
                if (clear == NULL)
                        return;
        }

        task = clear;
        VSTAILQ_FOREACH_FROM(task, &change->tasks, list) {
                CHECK_OBJ_NOTNULL(task, SHARD_CHANGE_TASK_MAGIC);
                switch (task->task) {
                case CLEAR:
                        assert(task->task != CLEAR);
                        break;
                case ADD_BE:
                        b = shardcfg_backend_lookup(&re, task->priv);

                        if (b == NULL) {
                                assert (task->weight >= 1);
                                if (replicas * task->weight > UINT32_MAX)
                                        b_replicas = UINT32_MAX;
                                else
                                        b_replicas = (uint32_t) // flint
                                                (replicas * task->weight);

                                shardcfg_backend_add(&re, task->priv,
                                    b_replicas);
                                break;
                        }

                        const char * const ident = b->ident;

                        shard_notice(vsl, shardd->name,
                            "backend %s%s%s already exists - skipping",
                            VRT_BACKEND_string(b->backend),
                            ident ? "/" : "",
                            ident ? ident : "");
                        break;
                case REMOVE_BE:
                        shardcfg_backend_del(&re, task->priv);
                        break;
                default:
                        INCOMPL();
                }
        }
        shardcfg_backend_finalize(&re);
}

/*
 * ============================================================
 * top reconfiguration function
 */

static VCL_BOOL
change_reconfigure(VRT_CTX, struct shard_change *change, VCL_INT replicas)
{
        struct sharddir *shardd;

        CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);
        assert (replicas > 0);
        shardd = change->shardd;
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);

        if (VSTAILQ_FIRST(&change->tasks) == NULL)
                return (1);

        sharddir_wrlock(shardd);

        shardcfg_apply_change(ctx->vsl, shardd, change, replicas);
        shard_change_finish(change);

        if (shardd->hashcircle)
                free(shardd->hashcircle);
        shardd->hashcircle = NULL;

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

        shardcfg_hashcircle(shardd);
        sharddir_unlock(shardd);
        return (1);
}

VCL_BOOL
shardcfg_reconfigure(VRT_CTX, struct sharddir *shardd, VCL_INT replicas)
{
        struct shard_change *change;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        if (replicas <= 0) {
                shard_err(ctx->vsl, shardd->name,
                    ".reconfigure() invalid replicas argument %ld", replicas);
                return (0);
        }

        change = shard_change_get(ctx, shardd);
        if (change == NULL)
                return (0);

        return (change_reconfigure(ctx, change, replicas));
}

/*
 * ============================================================
 * misc config related
 */

/* only for sharddir_delete() */
void
shardcfg_delete(const struct sharddir *shardd)
{

        AZ(shardd->n_backend);
        if (shardd->backend)
                free(shardd->backend);
        if (shardd->hashcircle)
                free(shardd->hashcircle);
}

VCL_VOID
shardcfg_set_warmup(struct sharddir *shardd, VCL_REAL ratio)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        assert(ratio >= 0 && ratio < 1);
        sharddir_wrlock(shardd);
        shardd->warmup = ratio;
        sharddir_unlock(shardd);
}

VCL_VOID
shardcfg_set_rampup(struct sharddir *shardd, VCL_DURATION duration)
{
        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        assert(duration >= 0);
        sharddir_wrlock(shardd);
        shardd->rampup_duration = duration;
        sharddir_unlock(shardd);
}

VCL_DURATION
shardcfg_get_rampup(const struct sharddir *shardd, unsigned host)
{
        VCL_DURATION r;

        CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
        // assert sharddir_rdlock_held(shardd);
        assert (host < shardd->n_backend);

        if (isnan(shardd->backend[host].rampup))
                r = shardd->rampup_duration;
        else
                r = shardd->backend[host].rampup;

        return (r);
}

		varnish-cache/vmod/vmod_directors_shard_cfg.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@uplex.de>
6		*
7		* SPDX-License-Identifier: BSD-2-Clause
8		*
9		* Redistribution and use in source and binary forms, with or without
10		* modification, are permitted provided that the following conditions
11		* are met:
12		* 1. Redistributions of source code must retain the above copyright
13		* notice, this list of conditions and the following disclaimer.
14		* 2. Redistributions in binary form must reproduce the above copyright
15		* notice, this list of conditions and the following disclaimer in the
16		* documentation and/or other materials provided with the distribution.
17		*
18		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21		* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
22		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28		* SUCH DAMAGE.
29		*/
30
31		#include "config.h"
32
33		#include <limits.h>
34		#include <stdlib.h>
35		#include <stdio.h>
36		#include <string.h>
37
38		#include "cache/cache.h"
39
40		#include "vmod_directors_shard_dir.h"
41		#include "vmod_directors_shard_cfg.h"
42
43		/lint -esym(749, shard_change_task_e::) */
44		enum shard_change_task_e {
45		_SHARD_TASK_E_INVALID = 0,
46		CLEAR,
47		ADD_BE,
48		REMOVE_BE,
49		_SHARD_TASK_E_MAX
50		};
51
52		struct shard_change_task {
53		unsigned magic;
54		#define SHARD_CHANGE_TASK_MAGIC 0x1e1168af
55		enum shard_change_task_e task;
56		void *priv;
57		VCL_REAL weight;
58		VSTAILQ_ENTRY(shard_change_task) list;
59		};
60
61		struct shard_change {
62		unsigned magic;
63		#define SHARD_CHANGE_MAGIC 0xdff5c9a6
64		struct vsl_log *vsl;
65		struct sharddir *shardd;
66		VSTAILQ_HEAD(,shard_change_task) tasks;
67		};
68
69		struct backend_reconfig {
70		struct sharddir * const shardd;
71		unsigned hint; // on number of backends after reconfig
72		unsigned hole_n; // number of holes in backends array
73		unsigned hole_i; // index hint on first hole
74		};
75
76		/* forward decl */
77		static VCL_BOOL
78		change_reconfigure(VRT_CTX, struct shard_change *change, VCL_INT replicas);
79
80		/*
81		* ============================================================
82		* change / task list
83		*
84		* for backend reconfiguration, we create a change list on the VCL workspace in
85		* a PRIV_TASK state, which we work in reconfigure.
86		*/
87
88		static void v_matchproto_(vmod_priv_fini_f)
89	760	shard_change_fini(VRT_CTX, void * priv)
90		{
91		struct shard_change *change;
92
93	760	if (priv == NULL)
94	0	return;
95
96	760	CAST_OBJ_NOTNULL(change, priv, SHARD_CHANGE_MAGIC);
97
98	760	(void) change_reconfigure(ctx, change, 67);
99	760	}
100
101		static const struct vmod_priv_methods shard_change_priv_methods[1] = {{
102		.magic = VMOD_PRIV_METHODS_MAGIC,
103		.type = "vmod_directors_shard_cfg",
104		.fini = shard_change_fini
105		}};
106
107		static struct shard_change *
108	7880	shard_change_get(VRT_CTX, struct sharddir * const shardd)
109		{
110		struct vmod_priv *task;
111		struct shard_change *change;
112	7880	const void id = (const char )shardd + task_off_cfg;
113
114	7880	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
115
116	7880	task = VRT_priv_task(ctx, id);
117	7880	if (task == NULL) {
118	0	shard_fail(ctx, shardd->name, "%s", "no priv_task");
119	0	return (NULL);
120		}
121
122	7880	if (task->priv != NULL) {
123	7120	CAST_OBJ_NOTNULL(change, task->priv, SHARD_CHANGE_MAGIC);
124	7120	assert (change->vsl == ctx->vsl);
125	7120	assert (change->shardd == shardd);
126	7120	return (change);
127		}
128
129	1520	WS_TASK_ALLOC_OBJ(ctx, change, SHARD_CHANGE_MAGIC);
130	760	if (change == NULL)
131	0	return (NULL);
132	760	change->vsl = ctx->vsl;
133	760	change->shardd = shardd;
134	760	VSTAILQ_INIT(&change->tasks);
135	760	task->priv = change;
136	760	task->methods = shard_change_priv_methods;
137
138	760	return (change);
139	7880	}
140
141		static void
142	1600	shard_change_finish(struct shard_change *change)
143		{
144	1600	CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);
145
146	1600	VSTAILQ_INIT(&change->tasks);
147	1600	}
148
149		static struct shard_change_task *
150	6280	shard_change_task_add(VRT_CTX, struct shard_change *change,
151		enum shard_change_task_e task_e, void *priv)
152		{
153		struct shard_change_task *task;
154
155	6280	CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);
156
157	12560	WS_TASK_ALLOC_OBJ(ctx, task, SHARD_CHANGE_TASK_MAGIC);
158	6280	if (task == NULL)
159	0	return (NULL);
160	6280	task->task = task_e;
161	6280	task->priv = priv;
162	6280	VSTAILQ_INSERT_TAIL(&change->tasks, task, list);
163
164	6280	return (task);
165	6280	}
166
167		static inline struct shard_change_task *
168	5680	shard_change_task_backend(VRT_CTX, struct sharddir *shardd,
169		enum shard_change_task_e task_e, VCL_BACKEND be, VCL_STRING ident,
170		VCL_DURATION rampup)
171		{
172		struct shard_change *change;
173		struct shard_backend *b;
174
175	5680	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
176	5680	assert(task_e == ADD_BE \|\| task_e == REMOVE_BE);
177
178	5680	change = shard_change_get(ctx, shardd);
179	5680	if (change == NULL)
180	0	return (NULL);
181
182	5680	b = WS_Alloc(ctx->ws, sizeof(*b));
183	5680	if (b == NULL) {
184	0	shard_fail(ctx, change->shardd->name, "%s",
185		"could not get workspace for task");
186	0	return (NULL);
187		}
188
189	5680	b->backend = NULL;
190	5680	VRT_Assign_Backend(&b->backend, be);
191	5680	b->ident = ident != NULL && *ident != '\0' ? ident : NULL;
192	5680	b->rampup = rampup;
193
194	5680	return (shard_change_task_add(ctx, change, task_e, b));
195	5680	}
196
197		/*
198		* ============================================================
199		* director reconfiguration tasks
200		*/
201		VCL_BOOL
202	4520	shardcfg_add_backend(VRT_CTX, struct sharddir *shardd,
203		VCL_BACKEND be, VCL_STRING ident, VCL_DURATION rampup, VCL_REAL weight)
204		{
205		struct shard_change_task *task;
206
207	4520	assert (weight >= 1);
208	4520	AN(be);
209
210	9040	task = shard_change_task_backend(ctx, shardd, ADD_BE,
211	4520	be, ident, rampup);
212
213	4520	if (task == NULL)
214	0	return (0);
215
216	4520	task->weight = weight;
217	4520	return (1);
218	4520	}
219
220		VCL_BOOL
221	1160	shardcfg_remove_backend(VRT_CTX, struct sharddir *shardd,
222		VCL_BACKEND be, VCL_STRING ident)
223		{
224	3480	return (shard_change_task_backend(ctx, shardd, REMOVE_BE,
225	2320	be, ident, 0) != NULL);
226		}
227
228		VCL_BOOL
229	600	shardcfg_clear(VRT_CTX, struct sharddir *shardd)
230		{
231		struct shard_change *change;
232
233	600	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
234
235	600	change = shard_change_get(ctx, shardd);
236	600	if (change == NULL)
237	0	return (0);
238
239	600	return (shard_change_task_add(ctx, change, CLEAR, NULL) != NULL);
240	600	}
241
242		/*
243		* ============================================================
244		* consistent hashing circle init
245		*/
246
247		typedef int (compar)( const void, const void* );
248
249		static int
250	416920	circlepoint_compare(const struct shard_circlepoint *a,
251		const struct shard_circlepoint *b)
252		{
253	416920	return ((a->point == b->point) ? 0 : ((a->point > b->point) ? 1 : -1));
254		}
255
256		static void
257	1440	shardcfg_hashcircle(struct sharddir *shardd)
258		{
259		const struct shard_backend backends, b;
260		unsigned h;
261		uint32_t i, j, n_points, r, rmax;
262		const char *ident;
263	1440	const int len = 12; // log10(UINT32_MAX) + 2;
264	1440	char s[len];
265
266	1440	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
267	1440	AZ(shardd->hashcircle);
268
269	1440	assert(shardd->n_backend > 0);
270	1440	backends=shardd->backend;
271	1440	AN(backends);
272
273	1440	n_points = 0;
274	1440	rmax = (UINT32_MAX - 1) / shardd->n_backend;
275	7480	for (b = backends; b < backends + shardd->n_backend; b++) {
276	6040	CHECK_OBJ_NOTNULL(b->backend, DIRECTOR_MAGIC);
277	6040	n_points += vmin_t(uint32_t, b->replicas, rmax);
278	6040	}
279
280	1440	assert(n_points < UINT32_MAX);
281
282	1440	shardd->n_points = n_points;
283	1440	shardd->hashcircle = calloc(n_points, sizeof(struct shard_circlepoint));
284	1440	AN(shardd->hashcircle);
285
286	1440	i = 0;
287	7480	for (h = 0, b = backends; h < shardd->n_backend; h++, b++) {
288	6040	ident = b->ident ? b->ident : VRT_BACKEND_string(b->backend);
289
290	6040	AN(ident);
291	6040	assert(ident[0] != '\0');
292
293	6040	r = vmin_t(uint32_t, b->replicas, rmax);
294
295	73400	for (j = 0; j < r; j++) {
296	67360	assert(snprintf(s, len, "%d", j) < len);
297	67360	assert (i < n_points);
298	67360	shardd->hashcircle[i].point =
299	67360	VRT_HashStrands32(TOSTRANDS(2, ident, s));
300	67360	shardd->hashcircle[i].host = h;
301	67360	i++;
302	67360	}
303	6040	}
304	1440	assert (i == n_points);
305	1440	qsort( (void *) shardd->hashcircle, n_points,
306		sizeof (struct shard_circlepoint), (compar) circlepoint_compare);
307
308	1440	if ((shardd->debug_flags & SHDBG_CIRCLE) == 0)
309	520	return;
310
311	25160	for (i = 0; i < n_points; i++)
312	24240	SHDBG(SHDBG_CIRCLE, shardd,
313		"hashcircle[%5jd] = {point = %8x, host = %2u}\n",
314		(intmax_t)i, shardd->hashcircle[i].point,
315		shardd->hashcircle[i].host);
316	1440	}
317
318		/*
319		* ============================================================
320		* configure the director backends
321		*/
322
323		static void
324	1840	shardcfg_backend_free(struct shard_backend *f)
325		{
326	1840	if (f->freeptr)
327	1400	free (f->freeptr);
328	1840	VRT_Assign_Backend(&f->backend, NULL);
329	1840	memset(f, 0, sizeof(*f));
330	1840	}
331
332		static void
333	3880	shardcfg_backend_copyin(struct shard_backend *dst,
334		const struct shard_backend *src)
335		{
336	3880	dst->backend = src->backend;
337	3880	dst->ident = src->ident ? strdup(src->ident) : NULL;
338	3880	dst->rampup = src->rampup;
339	3880	}
340
341		static int
342	28560	shardcfg_backend_cmp(const struct shard_backend *a,
343		const struct shard_backend *b)
344		{
345		const char ai, bi;
346
347	28560	ai = a->ident;
348	28560	bi = b->ident;
349
350	28560	assert(ai \|\| a->backend);
351	28560	assert(bi \|\| b->backend);
352
353		/* vcl_names are unique, so we can compare the backend pointers */
354	28560	if (ai == NULL && bi == NULL)
355	1880	return (a->backend != b->backend);
356
357	26680	if (ai == NULL)
358	240	ai = VRT_BACKEND_string(a->backend);
359
360	26680	if (bi == NULL)
361	600	bi = VRT_BACKEND_string(b->backend);
362
363	26680	AN(ai);
364	26680	AN(bi);
365	26680	return (strcmp(ai, bi));
366	28560	}
367
368		/* for removal, we delete all instances if the backend matches */
369		static int
370	13000	shardcfg_backend_del_cmp(const struct shard_backend *task,
371		const struct shard_backend *b)
372		{
373	13000	assert(task->backend \|\| task->ident);
374
375	13000	if (task->ident == NULL)
376	360	return (task->backend != b->backend);
377
378	12640	return (shardcfg_backend_cmp(task, b));
379	13000	}
380
381		static const struct shard_backend *
382	4200	shardcfg_backend_lookup(const struct backend_reconfig *re,
383		const struct shard_backend *b)
384		{
385	4200	unsigned i, max = re->shardd->n_backend + re->hole_n;
386	4200	const struct shard_backend *bb = re->shardd->backend;
387
388	4200	if (max > 0)
389	3200	AN(bb);
390
391	20040	for (i = 0; i < max; i++) {
392	16160	if (bb[i].backend == NULL)
393	240	continue; // hole
394	15920	if (!shardcfg_backend_cmp(b, &bb[i]))
395	320	return (&bb[i]);
396	15600	}
397	3880	return (NULL);
398	4200	}
399
400		static void
401	760	shardcfg_backend_expand(const struct backend_reconfig *re)
402		{
403	760	unsigned min = re->hint;
404
405	760	CHECK_OBJ_NOTNULL(re->shardd, SHARDDIR_MAGIC);
406
407	760	min = vmax_t(unsigned, min, 16);
408
409	760	if (re->shardd->l_backend < min)
410	760	re->shardd->l_backend = min;
411		else
412	0	re->shardd->l_backend *= 2;
413
414	1520	re->shardd->backend = realloc(re->shardd->backend,
415	760	re->shardd->l_backend * sizeof *re->shardd->backend);
416
417	760	AN(re->shardd->backend);
418	760	}
419
420		static void
421	3880	shardcfg_backend_add(struct backend_reconfig *re,
422		const struct shard_backend *b, uint32_t replicas)
423		{
424		unsigned i;
425	3880	struct shard_backend *bb = re->shardd->backend;
426
427	3880	if (re->hole_n == 0) {
428	3720	if (re->shardd->n_backend >= re->shardd->l_backend) {
429	760	shardcfg_backend_expand(re);
430	760	bb = re->shardd->backend;
431	760	}
432	3720	assert(re->shardd->n_backend < re->shardd->l_backend);
433	3720	i = re->shardd->n_backend;
434	3720	} else {
435	160	assert(re->hole_i != UINT_MAX);
436	160	do {
437	160	if (!bb[re->hole_i].backend)
438	160	break;
439	0	} while (++(re->hole_i) < re->shardd->n_backend + re->hole_n);
440	160	assert(re->hole_i < re->shardd->n_backend + re->hole_n);
441
442	160	i = (re->hole_i)++;
443	160	(re->hole_n)--;
444		}
445
446	3880	re->shardd->n_backend++;
447	3880	shardcfg_backend_copyin(&bb[i], b);
448	3880	bb[i].replicas = replicas;
449	3880	}
450
451		void
452	720	shardcfg_backend_clear(struct sharddir *shardd)
453		{
454		unsigned i;
455	1320	for (i = 0; i < shardd->n_backend; i++)
456	600	shardcfg_backend_free(&shardd->backend[i]);
457	720	shardd->n_backend = 0;
458	720	}
459
460
461		static void
462	1160	shardcfg_backend_del(struct backend_reconfig re, struct shard_backend spec)
463		{
464	1160	unsigned i, max = re->shardd->n_backend + re->hole_n;
465	1160	struct shard_backend * const bb = re->shardd->backend;
466
467	19040	for (i = 0; i < max; i++) {
468	17880	if (bb[i].backend == NULL)
469	4880	continue; // hole
470	13000	if (shardcfg_backend_del_cmp(spec, &bb[i]))
471	11760	continue;
472
473	1240	shardcfg_backend_free(&bb[i]);
474	1240	re->shardd->n_backend--;
475	1240	if (i < re->shardd->n_backend + re->hole_n) {
476	1080	(re->hole_n)++;
477	1080	re->hole_i = vmin(re->hole_i, i);
478	1080	}
479	1240	}
480	1160	VRT_Assign_Backend(&spec->backend, NULL);
481	1160	}
482
483		static void
484	1440	shardcfg_backend_finalize(struct backend_reconfig *re)
485		{
486		unsigned i;
487	1440	struct shard_backend * const bb = re->shardd->backend;
488
489	1680	while (re->hole_n > 0) {
490		// trim end
491	360	i = re->shardd->n_backend + re->hole_n - 1;
492	1040	while (re->hole_n && bb[i].backend == NULL) {
493	680	(re->hole_n)--;
494	680	i--;
495		}
496
497	360	if (re->hole_n == 0)
498	120	break;
499