| 1 | #include <math.h> |
| 2 | #include <string.h> |
| 3 | #include <inttypes.h> |
| 4 | #include <stdio.h> |
| 5 | #include <unistd.h> |
| 6 | #include <sys/types.h> |
| 7 | #include <fcntl.h> |
| 8 | #include "ieee754.h" |
| 9 | #include "../log.h" |
| 10 | #include "zipf.h" |
| 11 | #include "../minmax.h" |
| 12 | #include "../os/os.h" |
| 13 | |
| 14 | struct fio_zipf_disk { |
| 15 | uint64_t ver_magic; |
| 16 | uint64_t nranges; |
| 17 | uint64_t zetan; |
| 18 | }; |
| 19 | |
| 20 | #define FIO_ZIPF_DISK_MAGIC 0x7a697066 |
| 21 | #define FIO_ZIPF_DISK_VER 1 |
| 22 | #define FIO_ZIPF_MAGIC ((FIO_ZIPF_DISK_MAGIC << 16) | FIO_ZIPF_DISK_VER) |
| 23 | |
| 24 | static void write_zipf(struct zipf_state *zs) |
| 25 | { |
| 26 | struct fio_zipf_disk f; |
| 27 | char tmp[80]; |
| 28 | int fd; |
| 29 | |
| 30 | sprintf(tmp, "fio.zipf.%f.%llu", zs->theta, (unsigned long long) zs->nranges); |
| 31 | fd = open(tmp, O_CREAT | O_WRONLY, 0644); |
| 32 | if (fd == -1) |
| 33 | return; |
| 34 | |
| 35 | f.ver_magic = __cpu_to_le64(FIO_ZIPF_MAGIC); |
| 36 | f.nranges = __cpu_to_le64(zs->nranges); |
| 37 | f.zetan = __cpu_to_le64(fio_double_to_uint64(zs->zetan)); |
| 38 | if (write(fd, &f, sizeof(f)) != sizeof(f)) |
| 39 | unlink(tmp); |
| 40 | |
| 41 | close(fd); |
| 42 | } |
| 43 | |
| 44 | static void zipf_update(struct zipf_state *zs) |
| 45 | { |
| 46 | unsigned int i; |
| 47 | |
| 48 | log_info("fio: generating zetan for theta=%f, ranges=%lu\n", zs->theta, zs->nranges); |
| 49 | |
| 50 | for (i = 0; i < zs->nranges; i++) |
| 51 | zs->zetan += pow(1.0 / (double) (i + 1), zs->theta); |
| 52 | |
| 53 | write_zipf(zs); |
| 54 | } |
| 55 | |
| 56 | static void zipf_load_gen_zeta(struct zipf_state *zs) |
| 57 | { |
| 58 | struct fio_zipf_disk f; |
| 59 | char tmp[80]; |
| 60 | int fd; |
| 61 | |
| 62 | sprintf(tmp, "fio.zipf.%f.%llu", zs->theta, (unsigned long long) zs->nranges); |
| 63 | fd = open(tmp, O_RDONLY); |
| 64 | if (fd == -1) { |
| 65 | punt: |
| 66 | zipf_update(zs); |
| 67 | return; |
| 68 | } |
| 69 | |
| 70 | if (read(fd, &f, sizeof(f)) != sizeof(f)) { |
| 71 | close(fd); |
| 72 | goto punt; |
| 73 | } |
| 74 | |
| 75 | close(fd); |
| 76 | |
| 77 | f.ver_magic = le64_to_cpu(f.ver_magic); |
| 78 | f.nranges = le64_to_cpu(f.nranges); |
| 79 | f.zetan = le64_to_cpu(f.zetan); |
| 80 | |
| 81 | if (f.ver_magic != FIO_ZIPF_MAGIC) { |
| 82 | unlink(tmp); |
| 83 | goto punt; |
| 84 | } |
| 85 | |
| 86 | zs->zetan = fio_uint64_to_double(f.zetan); |
| 87 | zs->nranges = f.nranges; |
| 88 | } |
| 89 | |
| 90 | void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta) |
| 91 | { |
| 92 | unsigned int i; |
| 93 | |
| 94 | memset(zs, 0, sizeof(*zs)); |
| 95 | |
| 96 | zs->nranges = nranges; |
| 97 | zs->theta = theta; |
| 98 | |
| 99 | for (i = 1; i <= 2; i++) |
| 100 | zs->zeta2 += pow(1.0 / (double) i, zs->theta); |
| 101 | |
| 102 | init_rand(&zs->rand); |
| 103 | |
| 104 | zipf_load_gen_zeta(zs); |
| 105 | } |
| 106 | |
| 107 | unsigned long long zipf_next(struct zipf_state *zs) |
| 108 | { |
| 109 | |
| 110 | double alpha, eta, rand_uni, rand_z; |
| 111 | unsigned long long n = zs->nranges; |
| 112 | unsigned long long val; |
| 113 | |
| 114 | alpha = 1.0 / (1.0 - zs->theta); |
| 115 | eta = (1.0 - pow(2.0 / n, 1.0 - zs->theta)) / (1.0 - zs->zeta2 / zs->zetan); |
| 116 | |
| 117 | rand_uni = (double) __rand(&zs->rand) / (double) FRAND_MAX; |
| 118 | rand_z = rand_uni * zs->zetan; |
| 119 | |
| 120 | if (rand_z < 1.0) |
| 121 | val = 1; |
| 122 | else if (rand_z < (1.0 + pow(0.5, zs->theta))) |
| 123 | val = 2; |
| 124 | else |
| 125 | val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha)); |
| 126 | |
| 127 | return val - 1; |
| 128 | } |
| 129 | |
| 130 | void pareto_init(struct zipf_state *zs, unsigned long nranges, double h) |
| 131 | { |
| 132 | memset(zs, 0, sizeof(*zs)); |
| 133 | |
| 134 | zs->nranges = nranges; |
| 135 | zs->pareto_pow = log(h) / log(1.0 - h); |
| 136 | |
| 137 | init_rand(&zs->rand); |
| 138 | } |
| 139 | |
| 140 | unsigned long long pareto_next(struct zipf_state *zs) |
| 141 | { |
| 142 | double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX; |
| 143 | unsigned long long n = zs->nranges - 1; |
| 144 | |
| 145 | return n * pow(rand, zs->pareto_pow); |
| 146 | } |