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;
        char s[12]; // log10(UINT32_MAX) + 2;

        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++) {
                        bprintf(s, "%d", j);
                        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 (vstrcmp(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);
}

		vinyl-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	57	shard_change_fini(VRT_CTX, void * priv)
90		{
91		struct shard_change *change;
92
93	57	if (priv == NULL)
94	0	return;
95
96	57	CAST_OBJ_NOTNULL(change, priv, SHARD_CHANGE_MAGIC);
97
98	57	(void) change_reconfigure(ctx, change, 67);
99	57	}
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	591	shard_change_get(VRT_CTX, struct sharddir * const shardd)
109		{
110		struct vmod_priv *task;
111		struct shard_change *change;
112	591	const void id = (const char )shardd + task_off_cfg;
113
114	591	CHECK_OBJ_NOTNULL(ctx, VRT_CTX_MAGIC);
115
116	591	task = VRT_priv_task(ctx, id);
117	591	if (task == NULL) {
118	0	shard_fail(ctx, shardd->name, "%s", "no priv_task");
119	0	return (NULL);
120		}
121
122	591	if (task->priv != NULL) {
123	534	CAST_OBJ_NOTNULL(change, task->priv, SHARD_CHANGE_MAGIC);
124	534	assert (change->vsl == ctx->vsl);
125	534	assert (change->shardd == shardd);
126	534	return (change);
127		}
128
129	114	WS_TASK_ALLOC_OBJ(ctx, change, SHARD_CHANGE_MAGIC);
130	57	if (change == NULL)
131	0	return (NULL);
132	57	change->vsl = ctx->vsl;
133	57	change->shardd = shardd;
134	57	VSTAILQ_INIT(&change->tasks);
135	57	task->priv = change;
136	57	task->methods = shard_change_priv_methods;
137
138	57	return (change);
139	591	}
140
141		static void
142	120	shard_change_finish(struct shard_change *change)
143		{
144	120	CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);
145
146	120	VSTAILQ_INIT(&change->tasks);
147	120	}
148
149		static struct shard_change_task *
150	471	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	471	CHECK_OBJ_NOTNULL(change, SHARD_CHANGE_MAGIC);
156
157	942	WS_TASK_ALLOC_OBJ(ctx, task, SHARD_CHANGE_TASK_MAGIC);
158	471	if (task == NULL)
159	0	return (NULL);
160	471	task->task = task_e;
161	471	task->priv = priv;
162	471	VSTAILQ_INSERT_TAIL(&change->tasks, task, list);
163
164	471	return (task);
165	471	}
166
167		static inline struct shard_change_task *
168	426	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	426	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
176	426	assert(task_e == ADD_BE \|\| task_e == REMOVE_BE);
177
178	426	change = shard_change_get(ctx, shardd);
179	426	if (change == NULL)
180	0	return (NULL);
181
182	426	b = WS_Alloc(ctx->ws, sizeof(*b));
183	426	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	426	b->backend = NULL;
190	426	VRT_Assign_Backend(&b->backend, be);
191	426	b->ident = ident != NULL && *ident != '\0' ? ident : NULL;
192	426	b->rampup = rampup;
193
194	426	return (shard_change_task_add(ctx, change, task_e, b));
195	426	}
196
197		/*
198		* ============================================================
199		* director reconfiguration tasks
200		*/
201		VCL_BOOL
202	339	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	339	assert (weight >= 1);
208	339	AN(be);
209
210	678	task = shard_change_task_backend(ctx, shardd, ADD_BE,
211	339	be, ident, rampup);
212
213	339	if (task == NULL)
214	0	return (0);
215
216	339	task->weight = weight;
217	339	return (1);
218	339	}
219
220		VCL_BOOL
221	87	shardcfg_remove_backend(VRT_CTX, struct sharddir *shardd,
222		VCL_BACKEND be, VCL_STRING ident)
223		{
224	261	return (shard_change_task_backend(ctx, shardd, REMOVE_BE,
225	174	be, ident, 0) != NULL);
226		}
227
228		VCL_BOOL
229	45	shardcfg_clear(VRT_CTX, struct sharddir *shardd)
230		{
231		struct shard_change *change;
232
233	45	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
234
235	45	change = shard_change_get(ctx, shardd);
236	45	if (change == NULL)
237	0	return (0);
238
239	45	return (shard_change_task_add(ctx, change, CLEAR, NULL) != NULL);
240	45	}
241
242		/*
243		* ============================================================
244		* consistent hashing circle init
245		*/
246
247		typedef int (compar)( const void, const void* );
248
249		static int
250	31029	circlepoint_compare(const struct shard_circlepoint *a,
251		const struct shard_circlepoint *b)
252		{
253	31029	return ((a->point == b->point) ? 0 : ((a->point > b->point) ? 1 : -1));
254		}
255
256		static void
257	108	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		char s[12]; // log10(UINT32_MAX) + 2;
264
265	108	CHECK_OBJ_NOTNULL(shardd, SHARDDIR_MAGIC);
266	108	AZ(shardd->hashcircle);
267
268	108	assert(shardd->n_backend > 0);
269	108	backends=shardd->backend;
270	108	AN(backends);
271
272	108	n_points = 0;
273	108	rmax = (UINT32_MAX - 1) / shardd->n_backend;
274	561	for (b = backends; b < backends + shardd->n_backend; b++) {
275	453	CHECK_OBJ_NOTNULL(b->backend, DIRECTOR_MAGIC);
276	453	n_points += vmin_t(uint32_t, b->replicas, rmax);
277	453	}
278
279	108	assert(n_points < UINT32_MAX);
280
281	108	shardd->n_points = n_points;
282	108	shardd->hashcircle = calloc(n_points, sizeof(struct shard_circlepoint));
283	108	AN(shardd->hashcircle);
284
285	108	i = 0;
286	561	for (h = 0, b = backends; h < shardd->n_backend; h++, b++) {
287	453	ident = b->ident ? b->ident : VRT_BACKEND_string(b->backend);
288
289	453	AN(ident);
290	453	assert(ident[0] != '\0');
291
292	453	r = vmin_t(uint32_t, b->replicas, rmax);
293
294	5505	for (j = 0; j < r; j++) {
295	5052	bprintf(s, "%d", j);
296	5052	assert (i < n_points);
297	5052	shardd->hashcircle[i].point =
298	5052	VRT_HashStrands32(TOSTRANDS(2, ident, s));
299	5052	shardd->hashcircle[i].host = h;
300	5052	i++;
301	5052	}
302	453	}
303	108	assert (i == n_points);
304	108	qsort( (void *) shardd->hashcircle, n_points,
305		sizeof (struct shard_circlepoint), (compar) circlepoint_compare);
306
307	108	if ((shardd->debug_flags & SHDBG_CIRCLE) == 0)
308	39	return;
309
310	1887	for (i = 0; i < n_points; i++)
311	1818	SHDBG(SHDBG_CIRCLE, shardd,
312		"hashcircle[%5jd] = {point = %8x, host = %2u}\n",
313		(intmax_t)i, shardd->hashcircle[i].point,
314		shardd->hashcircle[i].host);
315	108	}
316
317		/*
318		* ============================================================
319		* configure the director backends
320		*/
321
322		static void
323	138	shardcfg_backend_free(struct shard_backend *f)
324		{
325	138	if (f->freeptr)
326	105	free (f->freeptr);
327	138	VRT_Assign_Backend(&f->backend, NULL);
328	138	memset(f, 0, sizeof(*f));
329	138	}
330
331		static void
332	291	shardcfg_backend_copyin(struct shard_backend *dst,
333		const struct shard_backend *src)
334		{
335	291	dst->backend = src->backend;
336	291	dst->ident = src->ident ? strdup(src->ident) : NULL;
337	291	dst->rampup = src->rampup;
338	291	}
339
340		static int
341	2142	shardcfg_backend_cmp(const struct shard_backend *a,
342		const struct shard_backend *b)
343		{
344		const char ai, bi;
345
346	2142	ai = a->ident;
347	2142	bi = b->ident;
348
349	2142	assert(ai \|\| a->backend);
350	2142	assert(bi \|\| b->backend);
351
352		/* vcl_names are unique, so we can compare the backend pointers */
353	2142	if (ai == NULL && bi == NULL)
354	141	return (a->backend != b->backend);
355
356	2001	if (ai == NULL)
357	18	ai = VRT_BACKEND_string(a->backend);
358
359	2001	if (bi == NULL)
360	45	bi = VRT_BACKEND_string(b->backend);
361
362	2001	AN(ai);
363	2001	AN(bi);
364	2001	return (vstrcmp(ai, bi));
365	2142	}
366
367		/* for removal, we delete all instances if the backend matches */
368		static int
369	975	shardcfg_backend_del_cmp(const struct shard_backend *task,
370		const struct shard_backend *b)
371		{
372	975	assert(task->backend \|\| task->ident);
373
374	975	if (task->ident == NULL)
375	27	return (task->backend != b->backend);
376
377	948	return (shardcfg_backend_cmp(task, b));
378	975	}
379
380		static const struct shard_backend *
381	315	shardcfg_backend_lookup(const struct backend_reconfig *re,
382		const struct shard_backend *b)
383		{
384	315	unsigned i, max = re->shardd->n_backend + re->hole_n;
385	315	const struct shard_backend *bb = re->shardd->backend;
386
387	315	if (max > 0)
388	240	AN(bb);
389
390	1503	for (i = 0; i < max; i++) {
391	1212	if (bb[i].backend == NULL)
392	18	continue; // hole
393	1194	if (!shardcfg_backend_cmp(b, &bb[i]))
394	24	return (&bb[i]);
395	1170	}
396	291	return (NULL);
397	315	}
398
399		static void
400	57	shardcfg_backend_expand(const struct backend_reconfig *re)
401		{
402	57	unsigned min = re->hint;
403
404	57	CHECK_OBJ_NOTNULL(re->shardd, SHARDDIR_MAGIC);
405
406	57	min = vmax_t(unsigned, min, 16);
407
408	57	if (re->shardd->l_backend < min)
409	57	re->shardd->l_backend = min;
410		else
411	0	re->shardd->l_backend *= 2;
412
413	114	re->shardd->backend = realloc(re->shardd->backend,
414	57	re->shardd->l_backend * sizeof *re->shardd->backend);
415
416	57	AN(re->shardd->backend);
417	57	}
418
419		static void
420	291	shardcfg_backend_add(struct backend_reconfig *re,
421		const struct shard_backend *b, uint32_t replicas)
422		{
423		unsigned i;
424	291	struct shard_backend *bb = re->shardd->backend;
425
426	291	if (re->hole_n == 0) {
427	279	if (re->shardd->n_backend >= re->shardd->l_backend) {
428	57	shardcfg_backend_expand(re);
429	57	bb = re->shardd->backend;
430	57	}
431	279	assert(re->shardd->n_backend < re->shardd->l_backend);
432	279	i = re->shardd->n_backend;
433	279	} else {
434	12	assert(re->hole_i != UINT_MAX);
435	12	do {
436	12	if (!bb[re->hole_i].backend)
437	12	break;
438	0	} while (++(re->hole_i) < re->shardd->n_backend + re->hole_n);
439	12	assert(re->hole_i < re->shardd->n_backend + re->hole_n);
440
441	12	i = (re->hole_i)++;
442	12	(re->hole_n)--;
443		}
444
445	291	re->shardd->n_backend++;
446	291	shardcfg_backend_copyin(&bb[i], b);
447	291	bb[i].replicas = replicas;
448	291	}
449
450		void
451	54	shardcfg_backend_clear(struct sharddir *shardd)
452		{
453		unsigned i;
454	99	for (i = 0; i < shardd->n_backend; i++)
455	45	shardcfg_backend_free(&shardd->backend[i]);
456	54	shardd->n_backend = 0;
457	54	}
458
459
460		static void
461	87	shardcfg_backend_del(struct backend_reconfig re, struct shard_backend spec)
462		{
463	87	unsigned i, max = re->shardd->n_backend + re->hole_n;
464	87	struct shard_backend * const bb = re->shardd->backend;
465
466	1428	for (i = 0; i < max; i++) {
467	1341	if (bb[i].backend == NULL)
468	366	continue; // hole
469	975	if (shardcfg_backend_del_cmp(spec, &bb[i]))
470	882	continue;
471
472	93	shardcfg_backend_free(&bb[i]);
473	93	re->shardd->n_backend--;
474	93	if (i < re->shardd->n_backend + re->hole_n) {
475	81	(re->hole_n)++;
476	81	re->hole_i = vmin(re->hole_i, i);
477	81	}
478	93	}
479	87	VRT_Assign_Backend(&spec->backend, NULL);
480	87	}
481
482		static void
483	108	shardcfg_backend_finalize(struct backend_reconfig *re)
484		{
485		unsigned i;
486	108	struct shard_backend * const bb = re->shardd->backend;
487
488	126	while (re->hole_n > 0) {
489		// trim end
490	27	i = re->shardd->n_backend + re->hole_n - 1;
491	78	while (re->hole_n && bb[i].backend == NULL) {
492	51	(re->hole_n)--;
493	51	i--;
494		}
495
496	27	if (re->hole_n == 0)
497	9	break;
498
499	18	assert(re->hole_i < i);