Merge branch 'master' of ssh://brick.kernel.dk/data/git/fio
diff --git a/Makefile b/Makefile
index 88d397b..f59f809 100644
--- a/Makefile
+++ b/Makefile
@@ -77,7 +77,7 @@
T_IEEE_PROGS = t/ieee754
T_ZIPF_OBS = t/genzipf.o
-T_ZIPF_OBJS += t/log.o lib/ieee754.o lib/rand.o lib/zipf.o t/genzipf.o
+T_ZIPF_OBJS += rbtree.o t/log.o lib/ieee754.o lib/rand.o lib/zipf.o t/genzipf.o
T_ZIPF_PROGS = t/genzip
T_OBJS = $(T_SMALLOC_OBJS)
diff --git a/hash.h b/hash.h
index 4b8c6bf..93dd831 100644
--- a/hash.h
+++ b/hash.h
@@ -28,7 +28,7 @@
#error Define GOLDEN_RATIO_PRIME for your wordsize.
#endif
-static inline unsigned long hash_long(unsigned long val, unsigned int bits)
+static inline unsigned long __hash_long(unsigned long val)
{
unsigned long hash = val;
@@ -52,8 +52,13 @@
hash *= GOLDEN_RATIO_PRIME;
#endif
+ return hash;
+}
+
+static inline unsigned long hash_long(unsigned long val, unsigned int bits)
+{
/* High bits are more random, so use them. */
- return hash >> (BITS_PER_LONG - bits);
+ return __hash_long(val) >> (BITS_PER_LONG - bits);
}
static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
diff --git a/lib/zipf.c b/lib/zipf.c
index 28e8d77..527ae29 100644
--- a/lib/zipf.c
+++ b/lib/zipf.c
@@ -9,6 +9,7 @@
#include "../log.h"
#include "zipf.h"
#include "../minmax.h"
+#include "../hash.h"
#include "../os/os.h"
struct fio_zipf_disk {
@@ -124,7 +125,7 @@
else
val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha));
- return val - 1;
+ return __hash_long(val - 1) % zs->nranges;
}
void pareto_init(struct zipf_state *zs, unsigned long nranges, double h)
@@ -142,5 +143,5 @@
double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX;
unsigned long long n = zs->nranges - 1;
- return n * pow(rand, zs->pareto_pow);
+ return __hash_long(n * pow(rand, zs->pareto_pow)) % zs->nranges;
}
diff --git a/rbtree.c b/rbtree.c
index 7cff649..883bc72 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -300,3 +300,34 @@
n = n->rb_left;
return n;
}
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (RB_EMPTY_NODE(node))
+ return NULL;
+
+ /*
+ * If we have a right-hand child, go down and then left as far
+ * as we can.
+ */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return (struct rb_node *)node;
+ }
+
+ /*
+ * No right-hand children. Everything down and left is smaller than us,
+ * so any 'next' node must be in the general direction of our parent.
+ * Go up the tree; any time the ancestor is a right-hand child of its
+ * parent, keep going up. First time it's a left-hand child of its
+ * parent, said parent is our 'next' node.
+ */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
diff --git a/rbtree.h b/rbtree.h
index 7563725..c6cfe4a 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -141,6 +141,7 @@
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_first(struct rb_root *);
+extern struct rb_node *rb_next(const struct rb_node *);
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
diff --git a/t/genzipf.c b/t/genzipf.c
index f286744..d06f561 100644
--- a/t/genzipf.c
+++ b/t/genzipf.c
@@ -18,25 +18,107 @@
#include <string.h>
#include "../lib/zipf.h"
+#include "../flist.h"
+#include "../hash.h"
+#include "../rbtree.h"
#define DEF_NR 1000000
#define DEF_NR_OUTPUT 23
-static int val_cmp(const void *p1, const void *p2)
-{
- const unsigned long *v1 = p1;
- const unsigned long *v2 = p2;
+struct node {
+ struct flist_head list;
+ struct rb_node rb;
+ unsigned long long val;
+ unsigned long hits;
+};
- return *v1 - *v2;
+static struct flist_head *hash;
+static unsigned long hash_bits = 24;
+static unsigned long hash_size = 1 << 24;
+static struct rb_root rb;
+
+static struct node *hash_lookup(unsigned long long val)
+{
+ struct flist_head *l = &hash[hash_long(val, hash_bits)];
+ struct flist_head *entry;
+ struct node *n;
+
+ flist_for_each(entry, l) {
+ n = flist_entry(entry, struct node, list);
+ if (n->val == val)
+ return n;
+ }
+
+ return NULL;
+}
+
+static void hash_insert(unsigned long long val)
+{
+ struct flist_head *l = &hash[hash_long(val, hash_bits)];
+ struct node *n = malloc(sizeof(*n));
+
+ n->val = val;
+ n->hits = 1;
+ flist_add_tail(&n->list, l);
+}
+
+static void rb_insert(struct node *n)
+{
+ struct rb_node **p, *parent;
+
+ memset(&n->rb, 0, sizeof(n->rb));
+ p = &rb.rb_node;
+ parent = NULL;
+ while (*p) {
+ struct node *__n;
+
+ parent = *p;
+ __n = rb_entry(parent, struct node, rb);
+ if (n->hits > __n->hits)
+ p = &(*p)->rb_left;
+ else
+ p = &(*p)->rb_right;
+ }
+
+ rb_link_node(&n->rb, parent, p);
+ rb_insert_color(&n->rb, &rb);
+}
+
+static unsigned long rb_add(struct flist_head *list)
+{
+ struct flist_head *entry;
+ unsigned long ret = 0;
+ struct node *n;
+
+ flist_for_each(entry, list) {
+ n = flist_entry(entry, struct node, list);
+
+ rb_insert(n);
+ ret++;
+ }
+
+ return ret;
+}
+
+static unsigned long rb_gen(void)
+{
+ unsigned long ret = 0;
+ unsigned int i;
+
+ for (i = 0; i < hash_size; i++)
+ ret += rb_add(&hash[i]);
+
+ return ret;
}
int main(int argc, char *argv[])
{
unsigned long nranges, output_nranges;
- unsigned long *vals;
- unsigned long i, j, nr_vals, cur_vals, max_val, interval;
+ unsigned long offset;
+ unsigned long i, j, nr_vals, cur_vals, interval;
double *output, perc, perc_i;
struct zipf_state zs;
+ struct rb_node *n;
int use_zipf;
double val;
@@ -71,52 +153,67 @@
else
pareto_init(&zs, nranges, val);
- vals = malloc(nranges * sizeof(unsigned long));
+ hash_bits = 0;
+ hash_size = nranges;
+ while ((hash_size >>= 1) != 0)
+ hash_bits++;
- max_val = nr_vals = 0;
- for (i = 0; i < nranges; i++) {
+ hash_size = 1 << hash_bits;
+
+ hash = malloc(hash_size * sizeof(struct flist_head));
+ for (i = 0; i < hash_size; i++)
+ INIT_FLIST_HEAD(&hash[i]);
+
+ for (nr_vals = 0, i = 0; i < nranges; i++) {
+ struct node *n;
+
if (use_zipf)
- vals[nr_vals] = zipf_next(&zs);
+ offset = zipf_next(&zs);
else
- vals[nr_vals] = pareto_next(&zs);
+ offset = pareto_next(&zs);
- if (vals[nr_vals] > max_val)
- max_val = vals[nr_vals];
+ n = hash_lookup(offset);
+ if (n)
+ n->hits++;
+ else
+ hash_insert(offset);
+
nr_vals++;
}
- qsort(vals, nr_vals, sizeof(unsigned long), val_cmp);
+ nr_vals = rb_gen();
- interval = (max_val + output_nranges - 1) / output_nranges;
+ interval = (nr_vals + output_nranges - 1) / output_nranges;
output = malloc(output_nranges * sizeof(double));
- for (i = j = 0, cur_vals = 0; i < nr_vals; i++) {
- if (vals[i] > interval) {
- output[j] = (double) (cur_vals + 1) / (double) nr_vals;
+ i = j = cur_vals = 0;
+
+ n = rb_first(&rb);
+ while (n) {
+ struct node *node = rb_entry(n, struct node, rb);
+
+ if (i >= interval) {
+ output[j] = (double) (cur_vals + 1) / (double) nranges;
output[j] *= 100.0;
j++;
- cur_vals = 0;
- interval += (max_val + output_nranges - 1) / output_nranges;
- continue;
- }
- cur_vals++;
- }
+ cur_vals = node->hits;
+ interval += (nr_vals + output_nranges - 1) / output_nranges;
+ } else
+ cur_vals += node->hits;
- if (cur_vals) {
- output[j] = (double) (cur_vals + 1) / (double) nr_vals;
- output[j] *= 100.0;
- j++;
+ n = rb_next(n);
+ i++;
}
perc_i = 100.0 / (double) output_nranges;
perc = 0.0;
for (i = 0; i < j; i++) {
- printf("%6.2f%% -> %6.2f%%:\t%6.2f%%\n", perc, perc + perc_i, output[i]);
perc += perc_i;
+ printf("%s %6.2f%%:\t%6.2f%% of hits\n", i ? "|->" : "Top", perc, output[i]);
}
free(output);
- free(vals);
+ free(hash);
return 0;
}