GCOV - Varnish Cache


/*-
 * Copyright (c) 2006 Verdens Gang AS
 * Copyright (c) 2006-2011 Varnish Software AS
 * Copyright (c) 1983, 1993 The Regents of the University of California.
 * All rights reserved.
 *
 * Author: Dag-Erling Smørgrav <des@des.no>
 *
 * 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.
 *
 * Partially from: $FreeBSD: head/lib/libc/stdlib/random.c 303342
 *
 */

#include "config.h"

#include <fcntl.h>
#include <math.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "vdef.h"

#include "vas.h"
#include "vrnd.h"


vrnd_lock_f *VRND_Lock;
vrnd_lock_f *VRND_Unlock;

/**********************************************************************
 * Stripped down random(3) implementation from FreeBSD, to provide
 * predictable "random" numbers of testing purposes.
 */

#define TYPE_3          3               /* x**31 + x**3 + 1 */
#define DEG_3           31
#define SEP_3           3

static uint32_t randtbl[DEG_3 + 1] = {
        TYPE_3,
        0x2cf41758, 0x27bb3711, 0x4916d4d1, 0x7b02f59f, 0x9b8e28eb, 0xc0e80269,
        0x696f5c16, 0x878f1ff5, 0x52d9c07f, 0x916a06cd, 0xb50b3a20, 0x2776970a,
        0xee4eb2a6, 0xe94640ec, 0xb1d65612, 0x9d1ed968, 0x1043f6b7, 0xa3432a76,
        0x17eacbb9, 0x3c09e2eb, 0x4f8c2b3,  0x708a1f57, 0xee341814, 0x95d0e4d2,
        0xb06f216c, 0x8bd2e72e, 0x8f7c38d7, 0xcfc6a8fc, 0x2a59495,  0xa20d2a69,
        0xe29d12d1
};

static uint32_t *fptr = &randtbl[SEP_3 + 1];
static uint32_t *rptr = &randtbl[1];

static uint32_t * const state = &randtbl[1];
static const int rand_deg = DEG_3;
static const int rand_sep = SEP_3;
static const uint32_t * const end_ptr = &randtbl[DEG_3 + 1];

static inline uint32_t
good_rand(uint32_t ctx)
{
/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
        int32_t hi, lo, x;

        /* Transform to [1, 0x7ffffffe] range. */
        x = (ctx % 0x7ffffffe) + 1;
        hi = x / 127773;
        lo = x % 127773;
        x = 16807 * lo - 2836 * hi;
        if (x < 0)
                x += 0x7fffffff;
        /* Transform to [0, 0x7ffffffd] range. */
        return (x - 1);
}

static long
vrnd_RandomTestable(void)
{
        uint32_t i;
        uint32_t *f, *r;

        /*
         * Use local variables rather than static variables for speed.
         */
        f = fptr; r = rptr;
        *f += *r;
        i = *f >> 1;    /* chucking least random bit */
        if (++f >= end_ptr) {
                f = state;
                ++r;
        }
        else if (++r >= end_ptr) {
                r = state;
        }

        fptr = f; rptr = r;
        return ((long)i);
}


void
VRND_SeedTestable(unsigned int x)
{
        int i, lim;

        state[0] = (uint32_t)x;
        for (i = 1; i < rand_deg; i++)
                state[i] = good_rand(state[i - 1]);
        fptr = &state[rand_sep];
        rptr = &state[0];
        lim = 10 * rand_deg;
        for (i = 0; i < lim; i++)
                (void)vrnd_RandomTestable();
}

long
VRND_RandomTestable(void)
{
        long l;

        AN(VRND_Lock);
        VRND_Lock();
        l = vrnd_RandomTestable();
        AN(VRND_Unlock);
        VRND_Unlock();
        return (l);
}

double
VRND_RandomTestableDouble(void)
{
        return (
            ldexp((double)VRND_RandomTestable(), -31) +
            ldexp((double)VRND_RandomTestable(), -62)
        );
}

int
VRND_RandomCrypto(void *ptr, size_t len)
{
        int fd;
        char *p = ptr;
        ssize_t l;

        AN(ptr);
        fd = open("/dev/urandom", O_RDONLY);
        if (fd < 0)
                return (-1);
        while (len > 0) {
                l = read(fd, p, len);
                if (l < 0)
                        break;
                p += l;
                len -= l;
        }
        closefd(&fd);
        return (len == 0 ? 0 : -1);
}

void
VRND_SeedAll(void)
{
        unsigned long seed;

        AZ(VRND_RandomCrypto(&seed, sizeof seed));
        srandom(seed);
        AZ(VRND_RandomCrypto(&seed, sizeof seed));
        VRND_SeedTestable(seed);
        AZ(VRND_RandomCrypto(&seed, sizeof seed));
        srand48((long)seed);
}

		varnish-cache/lib/libvarnish/vrnd.c
0		/*-
1		* Copyright (c) 2006 Verdens Gang AS
2		* Copyright (c) 2006-2011 Varnish Software AS
3		* Copyright (c) 1983, 1993 The Regents of the University of California.
4		* All rights reserved.
5		*
6		* Author: Dag-Erling Smørgrav <des@des.no>
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		* Partially from: $FreeBSD: head/lib/libc/stdlib/random.c 303342
32		*
33		*/
34
35		#include "config.h"
36
37		#include <fcntl.h>
38		#include <math.h>
39		#include <stdint.h>
40		#include <stdlib.h>
41		#include <string.h>
42		#include <unistd.h>
43
44		#include "vdef.h"
45
46		#include "vas.h"
47		#include "vrnd.h"
48
49
50		vrnd_lock_f *VRND_Lock;
51		vrnd_lock_f *VRND_Unlock;
52
53		/**********************************************************************
54		* Stripped down random(3) implementation from FreeBSD, to provide
55		* predictable "random" numbers of testing purposes.
56		*/
57
58		#define TYPE_3 3 /* x31 + x3 + 1 */
59		#define DEG_3 31
60		#define SEP_3 3
61
62		static uint32_t randtbl[DEG_3 + 1] = {
63		TYPE_3,
64		0x2cf41758, 0x27bb3711, 0x4916d4d1, 0x7b02f59f, 0x9b8e28eb, 0xc0e80269,
65		0x696f5c16, 0x878f1ff5, 0x52d9c07f, 0x916a06cd, 0xb50b3a20, 0x2776970a,
66		0xee4eb2a6, 0xe94640ec, 0xb1d65612, 0x9d1ed968, 0x1043f6b7, 0xa3432a76,
67		0x17eacbb9, 0x3c09e2eb, 0x4f8c2b3, 0x708a1f57, 0xee341814, 0x95d0e4d2,
68		0xb06f216c, 0x8bd2e72e, 0x8f7c38d7, 0xcfc6a8fc, 0x2a59495, 0xa20d2a69,
69		0xe29d12d1
70		};
71
72		static uint32_t *fptr = &randtbl[SEP_3 + 1];
73		static uint32_t *rptr = &randtbl[1];
74
75		static uint32_t * const state = &randtbl[1];
76		static const int rand_deg = DEG_3;
77		static const int rand_sep = SEP_3;
78		static const uint32_t * const end_ptr = &randtbl[DEG_3 + 1];
79
80		static inline uint32_t
81	5889330	good_rand(uint32_t ctx)
82		{
83		/*
84		* Compute x = (7^5 * x) mod (2^31 - 1)
85		* without overflowing 31 bits:
86		* (2^31 - 1) = 127773 * (7^5) + 2836
87		* From "Random number generators: good ones are hard to find",
88		* Park and Miller, Communications of the ACM, vol. 31, no. 10,
89		* October 1988, p. 1195.
90		*/
91		int32_t hi, lo, x;
92
93		/* Transform to [1, 0x7ffffffe] range. */
94	5889330	x = (ctx % 0x7ffffffe) + 1;
95	5889330	hi = x / 127773;
96	5889330	lo = x % 127773;
97	5889330	x = 16807 * lo - 2836 * hi;
98	5889330	if (x < 0)
99	65578	x += 0x7fffffff;
100		/* Transform to [0, 0x7ffffffd] range. */
101	5889330	return (x - 1);
102		}
103
104		static long
105	193670980	vrnd_RandomTestable(void)
106		{
107		uint32_t i;
108		uint32_t f, r;
109
110		/*
111		* Use local variables rather than static variables for speed.
112		*/
113	193670980	f = fptr; r = rptr;
114	193670980	f += r;
115	193670980	i = f >> 1; / chucking least random bit */
116	193670980	if (++f >= end_ptr) {
117	6247246	f = state;
118	6247246	++r;
119	6247246	}
120	187423734	else if (++r >= end_ptr) {
121	6247213	r = state;
122	6247213	}
123
124	193670980	fptr = f; rptr = r;
125	193670980	return ((long)i);
126		}
127
128
129		void
130	196311	VRND_SeedTestable(unsigned int x)
131		{
132		int i, lim;
133
134	196311	state[0] = (uint32_t)x;
135	6085641	for (i = 1; i < rand_deg; i++)
136	5889330	state[i] = good_rand(state[i - 1]);
137	196311	fptr = &state[rand_sep];
138	196311	rptr = &state[0];
139	196311	lim = 10 * rand_deg;
140	61052721	for (i = 0; i < lim; i++)
141	60856410	(void)vrnd_RandomTestable();
142	196311	}
143
144		long
145	132814570	VRND_RandomTestable(void)
146		{
147		long l;
148
149	132814570	AN(VRND_Lock);
150	132814570	VRND_Lock();
151	132814570	l = vrnd_RandomTestable();
152	132814570	AN(VRND_Unlock);
153	132814570	VRND_Unlock();
154	132814570	return (l);
155		}
156
157		double
158	240	VRND_RandomTestableDouble(void)
159		{
160	240	return (
161	480	ldexp((double)VRND_RandomTestable(), -31) +
162	240	ldexp((double)VRND_RandomTestable(), -62)
163		);
164		}
165
166		int
167	13255281	VRND_RandomCrypto(void *ptr, size_t len)
168		{
169		int fd;
170	13255281	char *p = ptr;
171		ssize_t l;
172
173	13255281	AN(ptr);
174	13255281	fd = open("/dev/urandom", O_RDONLY);
175	13255281	if (fd < 0)
176	0	return (-1);
177	26510562	while (len > 0) {
178	13255281	l = read(fd, p, len);
179	13255281	if (l < 0)
180	0	break;
181	13255281	p += l;
182	13255281	len -= l;
183		}
184	13255281	closefd(&fd);
185	13255281	return (len == 0 ? 0 : -1);
186	13255281	}
187
188		void
189	196151	VRND_SeedAll(void)
190		{
191		unsigned long seed;
192
193	196151	AZ(VRND_RandomCrypto(&seed, sizeof seed));
194	196151	srandom(seed);
195	196151	AZ(VRND_RandomCrypto(&seed, sizeof seed));
196	196151	VRND_SeedTestable(seed);
197	196151	AZ(VRND_RandomCrypto(&seed, sizeof seed));
198	196151	srand48((long)seed);
199	196151	}