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