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