1 #include "test/jemalloc_test.h" 2 3 /******************************************************************************/ 4 5 /* 6 * General purpose tool for examining random number distributions. 7 * 8 * Input - 9 * (a) a random number generator, and 10 * (b) the buckets: 11 * (1) number of buckets, 12 * (2) width of each bucket, in log scale, 13 * (3) expected mean and stddev of the count of random numbers in each 14 * bucket, and 15 * (c) number of iterations to invoke the generator. 16 * 17 * The program generates the specified amount of random numbers, and assess how 18 * well they conform to the expectations: for each bucket, output - 19 * (a) the (given) expected mean and stddev, 20 * (b) the actual count and any interesting level of deviation: 21 * (1) ~68% buckets should show no interesting deviation, meaning a 22 * deviation less than stddev from the expectation; 23 * (2) ~27% buckets should show '+' / '-', meaning a deviation in the range 24 * of [stddev, 2 * stddev) from the expectation; 25 * (3) ~4% buckets should show '++' / '--', meaning a deviation in the 26 * range of [2 * stddev, 3 * stddev) from the expectation; and 27 * (4) less than 0.3% buckets should show more than two '+'s / '-'s. 28 * 29 * Technical remarks: 30 * (a) The generator is expected to output uint64_t numbers, so you might need 31 * to define a wrapper. 32 * (b) The buckets must be of equal width and the lowest bucket starts at 33 * [0, 2^lg_bucket_width - 1). 34 * (c) Any generated number >= n_bucket * 2^lg_bucket_width will be counted 35 * towards the last bucket; the expected mean and stddev provided should 36 * also reflect that. 37 * (d) The number of iterations is advised to be determined so that the bucket 38 * with the minimal expected proportion gets a sufficient count. 39 */ 40 41 static void 42 fill(size_t a[], const size_t n, const size_t k) { 43 for (size_t i = 0; i < n; ++i) { 44 a[i] = k; 45 } 46 } 47 48 static void 49 collect_buckets(uint64_t (*gen)(void *), void *opaque, size_t buckets[], 50 const size_t n_bucket, const size_t lg_bucket_width, const size_t n_iter) { 51 for (size_t i = 0; i < n_iter; ++i) { 52 uint64_t num = gen(opaque); 53 uint64_t bucket_id = num >> lg_bucket_width; 54 if (bucket_id >= n_bucket) { 55 bucket_id = n_bucket - 1; 56 } 57 ++buckets[bucket_id]; 58 } 59 } 60 61 static void 62 print_buckets(const size_t buckets[], const size_t means[], 63 const size_t stddevs[], const size_t n_bucket) { 64 for (size_t i = 0; i < n_bucket; ++i) { 65 malloc_printf("%zu:\tmean = %zu,\tstddev = %zu,\tbucket = %zu", 66 i, means[i], stddevs[i], buckets[i]); 67 68 /* Make sure there's no overflow. */ 69 assert(buckets[i] + stddevs[i] >= stddevs[i]); 70 assert(means[i] + stddevs[i] >= stddevs[i]); 71 72 if (buckets[i] + stddevs[i] <= means[i]) { 73 malloc_write(" "); 74 for (size_t t = means[i] - buckets[i]; t >= stddevs[i]; 75 t -= stddevs[i]) { 76 malloc_write("-"); 77 } 78 } else if (buckets[i] >= means[i] + stddevs[i]) { 79 malloc_write(" "); 80 for (size_t t = buckets[i] - means[i]; t >= stddevs[i]; 81 t -= stddevs[i]) { 82 malloc_write("+"); 83 } 84 } 85 malloc_write("\n"); 86 } 87 } 88 89 static void 90 bucket_analysis(uint64_t (*gen)(void *), void *opaque, size_t buckets[], 91 const size_t means[], const size_t stddevs[], const size_t n_bucket, 92 const size_t lg_bucket_width, const size_t n_iter) { 93 for (size_t i = 1; i <= 3; ++i) { 94 malloc_printf("round %zu\n", i); 95 fill(buckets, n_bucket, 0); 96 collect_buckets(gen, opaque, buckets, n_bucket, 97 lg_bucket_width, n_iter); 98 print_buckets(buckets, means, stddevs, n_bucket); 99 } 100 } 101 102 /* (Recommended) minimal bucket mean. */ 103 #define MIN_BUCKET_MEAN 10000 104 105 /******************************************************************************/ 106 107 /* Uniform random number generator. */ 108 109 typedef struct uniform_gen_arg_s uniform_gen_arg_t; 110 struct uniform_gen_arg_s { 111 uint64_t state; 112 const unsigned lg_range; 113 }; 114 115 static uint64_t 116 uniform_gen(void *opaque) { 117 uniform_gen_arg_t *arg = (uniform_gen_arg_t *)opaque; 118 return prng_lg_range_u64(&arg->state, arg->lg_range); 119 } 120 121 TEST_BEGIN(test_uniform) { 122 #define LG_N_BUCKET 5 123 #define N_BUCKET (1 << LG_N_BUCKET) 124 125 #define QUOTIENT_CEIL(n, d) (((n) - 1) / (d) + 1) 126 127 const unsigned lg_range_test = 25; 128 129 /* 130 * Mathematical tricks to guarantee that both mean and stddev are 131 * integers, and that the minimal bucket mean is at least 132 * MIN_BUCKET_MEAN. 133 */ 134 const size_t q = 1 << QUOTIENT_CEIL(LG_CEIL(QUOTIENT_CEIL( 135 MIN_BUCKET_MEAN, N_BUCKET * (N_BUCKET - 1))), 2); 136 const size_t stddev = (N_BUCKET - 1) * q; 137 const size_t mean = N_BUCKET * stddev * q; 138 const size_t n_iter = N_BUCKET * mean; 139 140 size_t means[N_BUCKET]; 141 fill(means, N_BUCKET, mean); 142 size_t stddevs[N_BUCKET]; 143 fill(stddevs, N_BUCKET, stddev); 144 145 uniform_gen_arg_t arg = {(uint64_t)(uintptr_t)&lg_range_test, 146 lg_range_test}; 147 size_t buckets[N_BUCKET]; 148 assert_zu_ge(lg_range_test, LG_N_BUCKET, ""); 149 const size_t lg_bucket_width = lg_range_test - LG_N_BUCKET; 150 151 bucket_analysis(uniform_gen, &arg, buckets, means, stddevs, 152 N_BUCKET, lg_bucket_width, n_iter); 153 154 #undef LG_N_BUCKET 155 #undef N_BUCKET 156 #undef QUOTIENT_CEIL 157 } 158 TEST_END 159 160 /******************************************************************************/ 161 162 /* Geometric random number generator; compiled only when prof is on. */ 163 164 #ifdef JEMALLOC_PROF 165 166 /* 167 * Fills geometric proportions and returns the minimal proportion. See 168 * comments in test_prof_sample for explanations for n_divide. 169 */ 170 static double 171 fill_geometric_proportions(double proportions[], const size_t n_bucket, 172 const size_t n_divide) { 173 assert(n_bucket > 0); 174 assert(n_divide > 0); 175 double x = 1.; 176 for (size_t i = 0; i < n_bucket; ++i) { 177 if (i == n_bucket - 1) { 178 proportions[i] = x; 179 } else { 180 double y = x * exp(-1. / n_divide); 181 proportions[i] = x - y; 182 x = y; 183 } 184 } 185 /* 186 * The minimal proportion is the smaller one of the last two 187 * proportions for geometric distribution. 188 */ 189 double min_proportion = proportions[n_bucket - 1]; 190 if (n_bucket >= 2 && proportions[n_bucket - 2] < min_proportion) { 191 min_proportion = proportions[n_bucket - 2]; 192 } 193 return min_proportion; 194 } 195 196 static size_t 197 round_to_nearest(const double x) { 198 return (size_t)(x + .5); 199 } 200 201 static void 202 fill_references(size_t means[], size_t stddevs[], const double proportions[], 203 const size_t n_bucket, const size_t n_iter) { 204 for (size_t i = 0; i < n_bucket; ++i) { 205 double x = n_iter * proportions[i]; 206 means[i] = round_to_nearest(x); 207 stddevs[i] = round_to_nearest(sqrt(x * (1. - proportions[i]))); 208 } 209 } 210 211 static uint64_t 212 prof_sample_gen(void *opaque) { 213 return prof_sample_new_event_wait((tsd_t *)opaque) - 1; 214 } 215 216 #endif /* JEMALLOC_PROF */ 217 218 TEST_BEGIN(test_prof_sample) { 219 test_skip_if(!config_prof); 220 #ifdef JEMALLOC_PROF 221 222 /* Number of divisions within [0, mean). */ 223 #define LG_N_DIVIDE 3 224 #define N_DIVIDE (1 << LG_N_DIVIDE) 225 226 /* Coverage of buckets in terms of multiples of mean. */ 227 #define LG_N_MULTIPLY 2 228 #define N_GEO_BUCKET (N_DIVIDE << LG_N_MULTIPLY) 229 230 test_skip_if(!opt_prof); 231 232 size_t lg_prof_sample_test = 25; 233 234 size_t lg_prof_sample_orig = lg_prof_sample; 235 assert_d_eq(mallctl("prof.reset", NULL, NULL, &lg_prof_sample_test, 236 sizeof(size_t)), 0, ""); 237 malloc_printf("lg_prof_sample = %zu\n", lg_prof_sample_test); 238 239 double proportions[N_GEO_BUCKET + 1]; 240 const double min_proportion = fill_geometric_proportions(proportions, 241 N_GEO_BUCKET + 1, N_DIVIDE); 242 const size_t n_iter = round_to_nearest(MIN_BUCKET_MEAN / 243 min_proportion); 244 size_t means[N_GEO_BUCKET + 1]; 245 size_t stddevs[N_GEO_BUCKET + 1]; 246 fill_references(means, stddevs, proportions, N_GEO_BUCKET + 1, n_iter); 247 248 tsd_t *tsd = tsd_fetch(); 249 assert_ptr_not_null(tsd, ""); 250 size_t buckets[N_GEO_BUCKET + 1]; 251 assert_zu_ge(lg_prof_sample, LG_N_DIVIDE, ""); 252 const size_t lg_bucket_width = lg_prof_sample - LG_N_DIVIDE; 253 254 bucket_analysis(prof_sample_gen, tsd, buckets, means, stddevs, 255 N_GEO_BUCKET + 1, lg_bucket_width, n_iter); 256 257 assert_d_eq(mallctl("prof.reset", NULL, NULL, &lg_prof_sample_orig, 258 sizeof(size_t)), 0, ""); 259 260 #undef LG_N_DIVIDE 261 #undef N_DIVIDE 262 #undef LG_N_MULTIPLY 263 #undef N_GEO_BUCKET 264 265 #endif /* JEMALLOC_PROF */ 266 } 267 TEST_END 268 269 /******************************************************************************/ 270 271 int 272 main(void) { 273 return test_no_reentrancy( 274 test_uniform, 275 test_prof_sample); 276 } 277