| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #include "libnetdata/libnetdata.h" |
| 4 | |
| 5 | #if !defined(HAVE_ARC4RANDOM_BUF) && !defined(HAVE_RAND_S) |
| 6 | static SPINLOCK random_lock = SPINLOCK_INITIALIZER; |
| 7 | static __attribute__((constructor)) void random_seed() { |
| 8 | // Use current time and process ID to create a high-entropy seed |
| 9 | struct timeval tv; |
| 10 | gettimeofday(&tv, NULL); |
| 11 | |
| 12 | uint32_t seed = (uint32_t)(tv.tv_sec ^ tv.tv_usec ^ getpid()); |
| 13 | |
| 14 | // Seed the random number generator |
| 15 | srandom(seed); |
| 16 | } |
| 17 | |
| 18 | static inline void random_bytes(void *buf, size_t bytes) { |
| 19 | spinlock_lock(&random_lock); |
| 20 | while (bytes > 0) { |
| 21 | if (bytes >= sizeof(uint32_t)) { |
| 22 | // Generate 4 bytes at a time |
| 23 | uint32_t temp = random(); |
| 24 | memcpy(buf, &temp, sizeof(uint32_t)); |
| 25 | buf = (uint8_t *)buf + sizeof(uint32_t); |
| 26 | bytes -= sizeof(uint32_t); |
| 27 | } else if (bytes >= sizeof(uint16_t)) { |
| 28 | // Generate 2 bytes at a time |
| 29 | uint16_t temp = random(); |
| 30 | memcpy(buf, &temp, sizeof(uint16_t)); |
| 31 | buf = (uint8_t *)buf + sizeof(uint16_t); |
| 32 | bytes -= sizeof(uint16_t); |
| 33 | } else { |
| 34 | // Generate remaining bytes |
| 35 | uint32_t temp = random(); |
| 36 | for (size_t i = 0; i < bytes; i++) { |
| 37 | ((uint8_t *)buf)[i] = temp & 0xFF; |
| 38 | temp >>= 8; |
| 39 | } |
| 40 | bytes = 0; |
| 41 | } |
| 42 | } |
| 43 | spinlock_unlock(&random_lock); |
| 44 | } |
| 45 | |
| 46 | #if defined(HAVE_GETRANDOM) |
| 47 | #include <sys/random.h> |
| 48 | static inline void getrandom_bytes(void *buf, size_t bytes) { |
| 49 | ssize_t result; |
| 50 | while (bytes > 0) { |
| 51 | result = getrandom(buf, bytes, 0); |
| 52 | if (result == -1) { |
| 53 | if (errno == EINTR) { |
| 54 | // Interrupted, retry |
| 55 | continue; |
| 56 | } else if (errno == EAGAIN) { |
| 57 | // Insufficient entropy; wait and retry |
| 58 | tinysleep(); |
| 59 | continue; |
| 60 | } else { |
| 61 | // fallback to RAND_bytes |
| 62 | random_bytes(buf, bytes); |
| 63 | return; |
| 64 | } |
| 65 | } |
| 66 | buf = (uint8_t *)buf + result; |
| 67 | bytes -= result; |
| 68 | } |
| 69 | } |
| 70 | #endif // HAVE_GETRANDOM |
| 71 | #endif // !HAVE_ARC4RANDOM_BUF && !HAVE_RAND_S |
| 72 | |
| 73 | #if defined(HAVE_RAND_S) |
| 74 | static inline void rand_s_bytes(void *buf, size_t bytes) { |
| 75 | while (bytes > 0) { |
| 76 | if (bytes >= sizeof(unsigned int)) { |
| 77 | unsigned int temp; |
| 78 | rand_s(&temp); |
| 79 | memcpy(buf, &temp, sizeof(unsigned int)); |
| 80 | buf = (uint8_t *)buf + sizeof(unsigned int); |
| 81 | bytes -= sizeof(unsigned int); |
| 82 | } else if (bytes >= sizeof(uint16_t)) { |
| 83 | // Generate 2 bytes at a time |
| 84 | unsigned int t; |
| 85 | rand_s(&t); |
| 86 | uint16_t temp = t; |
| 87 | memcpy(buf, &temp, sizeof(uint16_t)); |
| 88 | buf = (uint8_t *)buf + sizeof(uint16_t); |
| 89 | bytes -= sizeof(uint16_t); |
| 90 | } else { |
| 91 | // Generate remaining bytes |
| 92 | unsigned int temp; |
| 93 | rand_s(&temp); |
| 94 | for (size_t i = 0; i < sizeof(temp) && i < bytes; i++) { |
| 95 | ((uint8_t *)buf)[0] = temp & 0xFF; |
| 96 | temp >>= 8; |
| 97 | buf = (uint8_t *)buf + 1; |
| 98 | bytes--; |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | } |
| 103 | #endif |
| 104 | |
| 105 | inline void os_random_bytes(void *buf, size_t bytes) { |
| 106 | #if defined(HAVE_ARC4RANDOM_BUF) |
| 107 | arc4random_buf(buf, bytes); |
| 108 | #else |
| 109 | |
| 110 | if(RAND_bytes((unsigned char *)buf, bytes) == 1) |
| 111 | return; |
| 112 | |
| 113 | #if defined(HAVE_GETRANDOM) |
| 114 | getrandom_bytes(buf, bytes); |
| 115 | #elif defined(HAVE_RAND_S) |
| 116 | rand_s_bytes(buf, bytes); |
| 117 | #else |
| 118 | random_bytes(buf, bytes); |
| 119 | #endif |
| 120 | #endif |
| 121 | } |
| 122 | |
| 123 | // Generate an 8-bit random number |
| 124 | uint8_t os_random8(void) { |
| 125 | uint8_t value; |
| 126 | os_random_bytes(&value, sizeof(value)); |
| 127 | return value; |
| 128 | } |
| 129 | |
| 130 | // Generate a 16-bit random number |
| 131 | uint16_t os_random16(void) { |
| 132 | uint16_t value; |
| 133 | os_random_bytes(&value, sizeof(value)); |
| 134 | return value; |
| 135 | } |
| 136 | |
| 137 | // Generate a 32-bit random number |
| 138 | uint32_t os_random32(void) { |
| 139 | uint32_t value; |
| 140 | os_random_bytes(&value, sizeof(value)); |
| 141 | return value; |
| 142 | } |
| 143 | |
| 144 | // Generate a 64-bit random number |
| 145 | uint64_t os_random64(void) { |
| 146 | uint64_t value; |
| 147 | os_random_bytes(&value, sizeof(value)); |
| 148 | return value; |
| 149 | } |
| 150 | |
| 151 | /* |
| 152 | * Rejection Sampling |
| 153 | * To reduce bias, we can use rejection sampling without creating an infinite loop. |
| 154 | * This technique works by discarding values that would introduce bias, but limiting |
| 155 | * the number of retries to avoid infinite loops. |
| 156 | */ |
| 157 | |
| 158 | // Calculate an upper limit so that the range evenly divides into max. |
| 159 | // Any values greater than this limit would introduce bias, so we discard them. |
| 160 | #define MAX_RETRIES 10 |
| 161 | #define os_random_rejection_sampling_X(type, type_max, func, max) \ |
| 162 | ({ \ |
| 163 | size_t retries = 0; \ |
| 164 | type value, upper_limit = type_max - (type_max % (max)); \ |
| 165 | while ((value = func()) >= upper_limit && retries++ < MAX_RETRIES); \ |
| 166 | value % (max); \ |
| 167 | }) |
| 168 | |
| 169 | uint64_t os_random(uint64_t max) { |
| 170 | if (max <= 1) return 0; |
| 171 | |
| 172 | #if defined(HAVE_ARC4RANDOM_UNIFORM) |
| 173 | if(max <= UINT32_MAX) |
| 174 | // this is not biased |
| 175 | return arc4random_uniform(max); |
| 176 | #endif |
| 177 | |
| 178 | if ((max & (max - 1)) == 0) { |
| 179 | // max is a power of 2 |
| 180 | // use bitmasking to directly generate an unbiased random number |
| 181 | |
| 182 | if (max <= UINT8_MAX) |
| 183 | return os_random8() & (max - 1); |
| 184 | else if (max <= UINT16_MAX) |
| 185 | return os_random16() & (max - 1); |
| 186 | else if (max <= UINT32_MAX) |
| 187 | return os_random32() & (max - 1); |
| 188 | else |
| 189 | return os_random64() & (max - 1); |
| 190 | } |
| 191 | |
| 192 | if (max <= UINT8_MAX) |
| 193 | return os_random_rejection_sampling_X(uint8_t, UINT8_MAX, os_random8, max); |
| 194 | else if (max <= UINT16_MAX) |
| 195 | return os_random_rejection_sampling_X(uint16_t, UINT16_MAX, os_random16, max); |
| 196 | else if (max <= UINT32_MAX) |
| 197 | return os_random_rejection_sampling_X(uint32_t, UINT32_MAX, os_random32, max); |
| 198 | else |
| 199 | return os_random_rejection_sampling_X(uint64_t, UINT64_MAX, os_random64, max); |
| 200 | } |