1#include <stdlib.h>
2#include <stdbool.h>
3#include <stdio.h>
4#include <string.h>
5#include <barrelfish/barrelfish.h>
6#include <barrelfish/types.h>
7#include <barrelfish/cap_predicates.h>
8#include <bench/bench.h>
9
10#include "mdb_bench.h"
11
12static cycles_t measure_insert_one(struct cte *ctes, size_t count)
13{
14    // insert all except first
15    for (int i = 1; i < count; i++) {
16        INS(&ctes[i]);
17    }
18
19    __asm volatile ("" : : : "memory");
20
21    // measure insert time for first
22    cycles_t begin = bench_tsc();
23    INS(&ctes[0]);
24    cycles_t end = bench_tsc();
25
26    return end - begin;
27}
28
29static cycles_t measure_remove_one(struct cte *ctes, size_t count)
30{
31    // insert all except first
32    for (int i = 0; i < count; i++) {
33        INS(&ctes[i]);
34    }
35
36    __asm volatile ("" : : : "memory");
37
38    // measure insert time for first
39    cycles_t begin = bench_tsc();
40    REM(&ctes[0]);
41    cycles_t end = bench_tsc();
42
43    return end - begin;
44}
45
46static cycles_t measure_iterate_n(struct cte *ctes, size_t count, size_t steps)
47{
48    // insert all caps
49    for (int i = 0; i < count; i++) {
50        INS(&ctes[i]);
51    }
52
53    // randomly select start cap
54    size_t startpos, mod = 1;
55    while (mod < count) { mod <<= 1; }
56    do {
57        // assuming count is power-of-two
58        startpos = rand() % mod;
59    } while (startpos >= count);
60    struct cte *cte = &ctes[startpos];
61
62    __asm volatile ("" : : : "memory");
63
64    // measure iteration speed
65    cycles_t begin = bench_tsc();
66    for (int i = 0; i < steps; i++) {
67        cte = NEXT(cte);
68        if (!cte) {
69            return 0;
70        }
71    }
72    cycles_t end = bench_tsc();
73
74    return end - begin;
75}
76
77static cycles_t measure_iterate_1(struct cte *ctes, size_t count)
78{
79    return measure_iterate_n(ctes, count, 1);
80}
81static cycles_t measure_iterate_10(struct cte *ctes, size_t count)
82{
83    return measure_iterate_n(ctes, count, 10);
84}
85static cycles_t measure_iterate_100(struct cte *ctes, size_t count)
86{
87    return measure_iterate_n(ctes, count, 100);
88}
89static cycles_t measure_iterate_1000(struct cte *ctes, size_t count)
90{
91    return measure_iterate_n(ctes, count, 1000);
92}
93
94static cycles_t measure_has_copies(struct cte *ctes, size_t count)
95{
96    for (int i = 0; i < count; i++) {
97        INS(&ctes[i]);
98    }
99
100    // randomly select start cap
101    size_t pos, mod = 1;
102    while (mod < count) { mod <<= 1; }
103    do {
104        // assuming count is power-of-two
105        pos = rand() % mod;
106    } while (pos >= count);
107    struct cte *cte = &ctes[pos];
108
109    __asm volatile ("" : : : "memory");
110
111    cycles_t begin = bench_tsc();
112    HASCOP(cte);
113    cycles_t end = bench_tsc();
114
115    return end - begin;
116}
117
118static cycles_t measure_has_ancestors(struct cte *ctes, size_t count)
119{
120    for (int i = 0; i < count; i++) {
121        INS(&ctes[i]);
122    }
123
124    // randomly select start cap
125    size_t pos, mod = 1;
126    while (mod < count) { mod <<= 1; }
127    do {
128        // assuming count is power-of-two
129        pos = rand() % mod;
130    } while (pos >= count);
131    struct cte *cte = &ctes[pos];
132
133    __asm volatile ("" : : : "memory");
134
135    cycles_t begin = bench_tsc();
136    HASANC(cte);
137    cycles_t end = bench_tsc();
138
139    return end - begin;
140}
141
142static cycles_t measure_has_descendants(struct cte *ctes, size_t count)
143{
144    for (int i = 0; i < count; i++) {
145        INS(&ctes[i]);
146    }
147
148    // randomly select start cap
149    size_t pos, mod = 1;
150    while (mod < count) { mod <<= 1; }
151    do {
152        // assuming count is power-of-two
153        pos = rand() % mod;
154    } while (pos >= count);
155    struct cte *cte = &ctes[pos];
156
157    __asm volatile ("" : : : "memory");
158
159    cycles_t begin = bench_tsc();
160    HASDESC(cte);
161    cycles_t end = bench_tsc();
162
163    return end - begin;
164}
165
166#ifndef OLD_MDB
167static cycles_t measure_query_address(struct cte *ctes, size_t count)
168{
169    for (int i = 0; i < count; i++) {
170        INS(&ctes[i]);
171    }
172
173    // randomly select a cap from which to take the address
174    size_t pos, mod = 1;
175    while (mod < count) { mod <<= 1; }
176    do {
177        // assuming count is power-of-two
178        pos = rand() % mod;
179    } while (pos >= count);
180    genpaddr_t base = ctes[pos].cap.u.ram.base;
181    struct cte *result;
182
183    __asm volatile ("" : : : "memory");
184
185    cycles_t begin = bench_tsc();
186    mdb_find_cap_for_address(base, &result);
187    cycles_t end = bench_tsc();
188
189    return end - begin;
190}
191#endif
192
193struct measure_opt measure_opts[] = {
194    { "insert_one", measure_insert_one, },
195    { "remove_one", measure_remove_one, },
196    { "iterate_1", measure_iterate_1, },
197    { "iterate_10", measure_iterate_10, },
198    { "iterate_100", measure_iterate_100, },
199    { "iterate_1000", measure_iterate_1000, },
200    { "has_copies", measure_has_copies, },
201    { "has_ancestors", measure_has_ancestors, },
202    { "has_descendants", measure_has_descendants, },
203#ifndef OLD_MDB
204    { "query_address", measure_query_address, },
205#endif
206    { NULL, NULL, },
207};
208