GCOV - Varnish Cache


/*-
 * Copyright 2025 UPLEX - Nils Goroll Systemoptimierung
 * All rights reserved.
 *
 * Author: Nils Goroll <nils.goroll@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.
 *
 * This code creates an index on top of the ban list to speed up lookup during
 * cache load (while ban_holds > 0). Its only assumption is that bans do not
 * vanish (as guaranteed by ban_holds), and it does not change any functions
 * called _after_ cache reload by constructing the additional index during
 * lookup only.
 *
 * The lookup function returns a ban for VTAILQ_FOREACH_FROM() to start from,
 * such that changes to the ban code remain minimal.
 *
 */

#include "config.h"

#include <stdlib.h>

#include "cache_varnishd.h"
#include "cache_ban.h"

struct metaban {
        unsigned                magic;
#define BANIDX_MAGIC            0x39b799f8
        VRBT_ENTRY(metaban)     tree;
        // duplicate the ban time for efficiency
        vtim_real               time;
        struct ban              *ban;
};

static inline int
metaban_cmp(const struct metaban *i1, const struct metaban *i2)
{
        if (i1->time < i2->time)
                return (-1);
        if (i1->time > i2->time)
                return (1);
        return (0);
}

VRBT_HEAD(banidx_s, metaban);
VRBT_GENERATE_REMOVE_COLOR(banidx_s, metaban, tree, static)
VRBT_GENERATE_REMOVE(banidx_s, metaban, tree, static)
VRBT_GENERATE_NFIND(banidx_s, metaban, tree, metaban_cmp, static)
VRBT_GENERATE_INSERT_COLOR(banidx_s, metaban, tree, static)
VRBT_GENERATE_INSERT_FINISH(banidx_s, metaban, tree, static)
VRBT_GENERATE_INSERT(banidx_s, metaban, tree, metaban_cmp, static)
VRBT_GENERATE_NEXT(banidx_s, metaban, tree, static)
VRBT_GENERATE_MINMAX(banidx_s, metaban, tree, static)

static struct banidx_s banidx = VRBT_INITIALIZER(banidx);
static pthread_mutex_t banidxmtx = PTHREAD_MUTEX_INITIALIZER;

struct ban *
BANIDX_lookup(vtim_real t0)
{
        struct metaban *m;      //lint -e429 not freed or returned
        struct metaban needle = {0, .time = t0};
        struct ban *best = NULL, *b = NULL;
        vtim_real t1;

        PTOK(pthread_mutex_lock(&banidxmtx));
        m = VRBT_NFIND(banidx_s, &banidx, &needle);
        if (m != NULL && ! (m->time > t0)) {
                PTOK(pthread_mutex_unlock(&banidxmtx));
                return (m->ban);
        }
        /*
         * if we have m, it is later than t0, which is higher up the list.
         * check if there is a better match and create missing elements
         * along the way
         * if VRBT_NFIND did not return anything, it means it has no index for
         * elements higher up the list and we can index from the top (implicit
         * in VTAILQ_FOREACH_FROM())
         */
        if (m != NULL) {
                best = m->ban;
                b = VTAILQ_NEXT(best, list);
                if (b == NULL) {
                        PTOK(pthread_mutex_unlock(&banidxmtx));
                        return (best);
                }
        }
        VTAILQ_FOREACH_FROM(b, &ban_head, list) {
                t1 = ban_time(b->spec);
                if (t1 < t0)
                        break;
                ALLOC_OBJ(m, BANIDX_MAGIC);
                AN(m);
                m->time = t1;
                m->ban = b;
                AZ(VRBT_INSERT(banidx_s, &banidx, m));
                best = b;
        }
        PTOK(pthread_mutex_unlock(&banidxmtx));
        return (best);
}

void
BANIDX_fini(void)
{
        struct metaban *m, *mm;

        VRBT_FOREACH_SAFE(m, banidx_s, &banidx, mm) {
                VRBT_REMOVE(banidx_s, &banidx, m);
                FREE_OBJ(m);
        }
}

		varnish-cache/bin/varnishd/cache/cache_ban_idx.c
0		/*-
1		* Copyright 2025 UPLEX - Nils Goroll Systemoptimierung
2		* All rights reserved.
3		*
4		* Author: Nils Goroll <nils.goroll@uplex.de>
5		*
6		* SPDX-License-Identifier: BSD-2-Clause
7		*
8		* Redistribution and use in source and binary forms, with or without
9		* modification, are permitted provided that the following conditions
10		* are met:
11		* 1. Redistributions of source code must retain the above copyright
12		* notice, this list of conditions and the following disclaimer.
13		* 2. Redistributions in binary form must reproduce the above copyright
14		* notice, this list of conditions and the following disclaimer in the
15		* documentation and/or other materials provided with the distribution.
16		*
17		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20		* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27		* SUCH DAMAGE.
28		*
29		* This code creates an index on top of the ban list to speed up lookup during
30		* cache load (while ban_holds > 0). Its only assumption is that bans do not
31		* vanish (as guaranteed by ban_holds), and it does not change any functions
32		* called _after_ cache reload by constructing the additional index during
33		* lookup only.
34		*
35		* The lookup function returns a ban for VTAILQ_FOREACH_FROM() to start from,
36		* such that changes to the ban code remain minimal.
37		*
38		*/
39
40		#include "config.h"
41
42		#include <stdlib.h>
43
44		#include "cache_varnishd.h"
45		#include "cache_ban.h"
46
47		struct metaban {
48		unsigned magic;
49		#define BANIDX_MAGIC 0x39b799f8
50		VRBT_ENTRY(metaban) tree;
51		// duplicate the ban time for efficiency
52		vtim_real time;
53		struct ban *ban;
54		};
55
56		static inline int
57	3280	metaban_cmp(const struct metaban i1, const struct metaban i2)
58		{
59	3280	if (i1->time < i2->time)
60	2880	return (-1);
61	400	if (i1->time > i2->time)
62	0	return (1);
63	400	return (0);
64	3280	}
65
66		VRBT_HEAD(banidx_s, metaban);
67	760	VRBT_GENERATE_REMOVE_COLOR(banidx_s, metaban, tree, static)
68	2400	VRBT_GENERATE_REMOVE(banidx_s, metaban, tree, static)
69	3480	VRBT_GENERATE_NFIND(banidx_s, metaban, tree, metaban_cmp, static)
70	1440	VRBT_GENERATE_INSERT_COLOR(banidx_s, metaban, tree, static)
71	1640	VRBT_GENERATE_INSERT_FINISH(banidx_s, metaban, tree, static)
72	3080	VRBT_GENERATE_INSERT(banidx_s, metaban, tree, metaban_cmp, static)
73	1640	VRBT_GENERATE_NEXT(banidx_s, metaban, tree, static)
74	38667	VRBT_GENERATE_MINMAX(banidx_s, metaban, tree, static)
75
76		static struct banidx_s banidx = VRBT_INITIALIZER(banidx);
77		static pthread_mutex_t banidxmtx = PTHREAD_MUTEX_INITIALIZER;
78
79		struct ban *
80	2040	BANIDX_lookup(vtim_real t0)
81		{
82		struct metaban *m; //lint -e429 not freed or returned
83	2040	struct metaban needle = {0, .time = t0};
84	2040	struct ban best = NULL, b = NULL;
85		vtim_real t1;
86
87	2040	PTOK(pthread_mutex_lock(&banidxmtx));
88	2040	m = VRBT_NFIND(banidx_s, &banidx, &needle);
89	2040	if (m != NULL && ! (m->time > t0)) {
90	400	PTOK(pthread_mutex_unlock(&banidxmtx));
91	400	return (m->ban);
92		}
93		/*
94		* if we have m, it is later than t0, which is higher up the list.
95		* check if there is a better match and create missing elements
96		* along the way
97		* if VRBT_NFIND did not return anything, it means it has no index for
98		* elements higher up the list and we can index from the top (implicit
99		* in VTAILQ_FOREACH_FROM())
100		*/
101	1640	if (m != NULL) {
102	1000	best = m->ban;
103	1000	b = VTAILQ_NEXT(best, list);
104	1000	if (b == NULL) {
105	0	PTOK(pthread_mutex_unlock(&banidxmtx));
106	0	return (best);
107		}
108	1000	}
109	3280	VTAILQ_FOREACH_FROM(b, &ban_head, list) {
110	2040	t1 = ban_time(b->spec);
111	2040	if (t1 < t0)
112	400	break;
113	1640	ALLOC_OBJ(m, BANIDX_MAGIC);
114	1640	AN(m);
115	1640	m->time = t1;
116	1640	m->ban = b;
117	1640	AZ(VRBT_INSERT(banidx_s, &banidx, m));
118	1640	best = b;
119	1640	}
120	1640	PTOK(pthread_mutex_unlock(&banidxmtx));
121	1640	return (best);
122	2040	}
123
124		void
125	37307	BANIDX_fini(void)
126		{
127		struct metaban m, mm;
128
129	38947	VRBT_FOREACH_SAFE(m, banidx_s, &banidx, mm) {
130	1640	VRBT_REMOVE(banidx_s, &banidx, m);
131	1640	FREE_OBJ(m);
132	1640	}
133	37307	}