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               /* x**31 + x**3 + 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 3073470
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 3073470
        x = (ctx % 0x7ffffffe) + 1;
95 3073470
        hi = x / 127773;
96 3073470
        lo = x % 127773;
97 3073470
        x = 16807 * lo - 2836 * hi;
98 3073470
        if (x < 0)
99 34070
                x += 0x7fffffff;
100
        /* Transform to [0, 0x7ffffffd] range. */
101 3073470
        return (x - 1);
102
}
103
104
static long
105 124730226
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 124730226
        f = fptr; r = rptr;
114 124730226
        *f += *r;
115 124730226
        i = *f >> 1;    /* chucking least random bit */
116 124730226
        if (++f >= end_ptr) {
117 4023412
                f = state;
118 4023412
                ++r;
119 4023412
        }
120 120706814
        else if (++r >= end_ptr) {
121 4023388
                r = state;
122 4023388
        }
123
124 124730226
        fptr = f; rptr = r;
125 124730226
        return ((long)i);
126
}
127
128
129
void
130 102449
VRND_SeedTestable(unsigned int x)
131
{
132
        int i, lim;
133
134 102449
        state[0] = (uint32_t)x;
135 3175919
        for (i = 1; i < rand_deg; i++)
136 3073470
                state[i] = good_rand(state[i - 1]);
137 102449
        fptr = &state[rand_sep];
138 102449
        rptr = &state[0];
139 102449
        lim = 10 * rand_deg;
140 31861639
        for (i = 0; i < lim; i++)
141 31759190
                (void)vrnd_RandomTestable();
142 102449
}
143
144
long
145 92971036
VRND_RandomTestable(void)
146
{
147
        long l;
148
149 92971036
        AN(VRND_Lock);
150 92971036
        VRND_Lock();
151 92971036
        l = vrnd_RandomTestable();
152 92971036
        AN(VRND_Unlock);
153 92971036
        VRND_Unlock();
154 92971036
        return (l);
155
}
156
157
double
158 168
VRND_RandomTestableDouble(void)
159
{
160 168
        return (
161 336
            ldexp((double)VRND_RandomTestable(), -31) +
162 168
            ldexp((double)VRND_RandomTestable(), -62)
163
        );
164
}
165
166
int
167 8497516
VRND_RandomCrypto(void *ptr, size_t len)
168
{
169
        int fd;
170 8497516
        char *p = ptr;
171
        ssize_t l;
172
173 8497516
        AN(ptr);
174 8497516
        fd = open("/dev/urandom", O_RDONLY);
175 8497516
        if (fd < 0)
176 0
                return (-1);
177 16995028
        while (len > 0) {
178 8497512
                l = read(fd, p, len);
179 8497512
                if (l < 0)
180 0
                        break;
181 8497512
                p += l;
182 8497512
                len -= l;
183
        }
184 8497516
        closefd(&fd);
185 8497516
        return (len == 0 ? 0 : -1);
186 8497516
}
187
188
void
189 102337
VRND_SeedAll(void)
190
{
191
        unsigned long seed;
192
193 102337
        AZ(VRND_RandomCrypto(&seed, sizeof seed));
194 102337
        srandom(seed);
195 102337
        AZ(VRND_RandomCrypto(&seed, sizeof seed));
196 102337
        VRND_SeedTestable(seed);
197 102337
        AZ(VRND_RandomCrypto(&seed, sizeof seed));
198 102337
        srand48(seed);
199 102337
}