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 <mdb/mdb.h> 9#include <mdb/mdb_tree.h> 10 11bool debug_all_the_things = false; 12 13#define DEBUG_ALL_THE_THINGS(...) \ 14 do { \ 15 if (debug_all_the_things) \ 16 printf(__VA_ARGS__); \ 17 } while(0) 18 19 20#define RUNS 5000 21#define MIN_RANGES 30 22#define MAX_RANGES 100 23#define MAX_ADDR_BITS 20 24#define MAX_ADDR (1<<MAX_ADDR_BITS) 25#define QUERY_COUNT 20 26 27struct node { 28 genvaddr_t address; 29 size_t size; 30 int tiebreak; 31}; 32 33static inline size_t randrange(size_t begin, size_t end) 34{ 35 return begin + rand() / (RAND_MAX / (end - begin + 1) + 1); 36} 37 38static void 39get_ranges(size_t count, uint8_t max_addr_bits, struct cte *out) 40{ 41 size_t gencount = 0; 42 size_t sizebits; 43 size_t size; 44 genvaddr_t max_addr = 1ULL<<max_addr_bits; 45 while (gencount < count) { 46 sizebits = randrange(1,max_addr_bits-2); 47 size = 1ULL<<sizebits; 48 genvaddr_t begin = randrange(max_addr/10, max_addr-max_addr/4); 49 genvaddr_t end = begin + size; 50 if (end > max_addr) { 51 continue; 52 } 53 bool valid = true; 54 for (int j = 0; j < gencount; j++) { 55 genvaddr_t r_addr = get_address(&(out[j].cap)); 56 size_t r_size = get_size(&(out[j].cap)); 57 genvaddr_t r_end = r_addr + r_size; 58 if (begin < r_addr && end > r_addr && end < r_end) { 59 valid = false; 60 break; 61 } 62 if (begin > r_addr && begin < r_end && end > r_end) { 63 valid = false; 64 break; 65 } 66 } 67 if (valid) { 68 memset(&out[gencount], 0, sizeof(struct cte)); 69 out[gencount].cap.type = ObjType_RAM; 70 out[gencount].cap.rights = CAPRIGHTS_ALLRIGHTS; 71 out[gencount].cap.u.ram = (struct RAM) { .base = begin, .bytes = 1UL << sizebits }; 72 gencount++; 73 } 74 } 75} 76 77enum query_type { 78 NONE, 79 CONTAINS, 80 INNER, 81 EXC, 82}; 83 84struct query { 85 genvaddr_t begin; 86 size_t size; 87 struct cte *target; 88}; 89 90static inline size_t min_count(size_t *counts, size_t countcount) 91{ 92 size_t min = (size_t)-1; 93 for (int i = 0; i < countcount; i++) { 94 if (counts[i] < min) 95 min = counts[i]; 96 } 97 return min; 98} 99 100static void 101get_overlap_queries(struct cte *ranges, size_t range_count, size_t count, genvaddr_t max_addr, struct query *out) 102{ 103 size_t gencount[4] = { 0 }; 104 105 DEBUG_ALL_THE_THINGS("get_overlap_queries() count = %zu, gencount = [ %zu %zu %zu %zu ]\n", 106 count, gencount[0], gencount[1], gencount[2], gencount[3]); 107 108 while (min_count(gencount, 4) < count) { 109 genvaddr_t begin = randrange(0, max_addr); 110 genvaddr_t end = randrange(0, max_addr); 111 if (begin == end) { 112 continue; 113 } 114 if (begin > end) { 115 begin ^= end; 116 end ^= begin; 117 begin ^= end; 118 } 119 enum query_type res = NONE; 120 struct cte *target = NULL; 121 for (int i = 0; i < range_count; i++) { 122 struct cte *r = &ranges[i]; 123 genvaddr_t r_begin = get_address(&r->cap); 124 size_t r_size = get_size(&r->cap); 125 genvaddr_t r_end = r_begin + r_size; 126 DEBUG_ALL_THE_THINGS("beg = 0x%"PRIxGENVADDR", end = 0x%"PRIxGENVADDR", r_beg = 0x%"PRIxGENVADDR", r_end = 0x%"PRIxGENVADDR"\n", begin, end, r_begin, r_end); 127 if (r_end <= begin) { 128 DEBUG_ALL_THE_THINGS("r_end <= beg\n"); 129 // do nothing 130 } 131 else if (r_begin <= begin && r_end >= end) { 132 DEBUG_ALL_THE_THINGS("CONTAINS\n"); 133 if (res < CONTAINS) { 134 res = CONTAINS; 135 target = r; 136 } 137 else if (res == CONTAINS && compare_caps(&target->cap, &r->cap, true) < 0) { 138 target = r; 139 } 140 } 141 else if (r_begin >= end) { 142 DEBUG_ALL_THE_THINGS("r_beg >= end\n"); 143 // do nothing 144 } 145 else if ((r_begin >= begin && r_end < end) || 146 (r_begin > begin && r_end <= end)) 147 { 148 DEBUG_ALL_THE_THINGS("INNER\n"); 149 if (res < INNER) { 150 res = INNER; 151 target = r; 152 } 153 else if (res == INNER && compare_caps(&target->cap, &r->cap, true) > 0) { 154 target = r; 155 } 156 } 157 else if ((r_begin < begin && r_end > begin && r_end < end) || 158 (r_begin > begin && r_begin < end && r_end > end)) 159 { 160 DEBUG_ALL_THE_THINGS("EXC\n"); 161 if (res < EXC) { 162 res = EXC; 163 target = r; 164 } 165 else if (res == EXC) { 166 if (r_begin < begin && target->cap.u.ram.base > begin) { 167 res = EXC; 168 target = r; 169 } 170 else if ((target->cap.u.ram.base < begin) == (r_begin < begin)) { 171 if (compare_caps(&r->cap, &target->cap, true) > 0) { 172 res = EXC; 173 target = r; 174 } 175 } 176 } 177 } 178 else { 179 printf("strange query: %"PRIxGENVADDR" - %"PRIxGENVADDR" (%"PRIxGENVADDR" - %"PRIxGENVADDR")\n", begin, end, r_begin, r_end); 180 USER_PANIC("huh?\n"); 181 } 182 } 183 if (gencount[res] < count) { 184 size_t index_ = res * count + gencount[res]++; 185 out[index_] = (struct query) { .begin = begin, .size = end - begin, .target = target }; 186 } 187 } 188} 189 190__attribute__((unused)) 191static void dump_ranges(struct cte *ranges, size_t count) 192{ 193 for (int i = 0; i < count; i++) { 194 printf("address = %"PRIxGENVADDR"\nsize=0x%"PRIxGENSIZE"\n", 195 ranges[i].cap.u.ram.base, ranges[i].cap.u.ram.bytes); 196 } 197} 198 199struct kcb clear = { 200 .mdb_root = 0 201}; 202int main(int argc, char *argv[]) 203{ 204 for (int run = 0; run < RUNS; run++) { 205 putchar('-'); fflush(stdout); 206 size_t count = randrange(MIN_RANGES, MAX_RANGES); 207 struct cte ranges[count]; 208 get_ranges(count, MAX_ADDR_BITS, ranges); 209 //dump_ranges(ranges, count); 210 set_init_mapping(ranges, count); 211 //mdb_dump_all_the_things(); 212 struct query queries[4][QUERY_COUNT]; 213 DEBUG_ALL_THE_THINGS("generating overlap queries\n"); 214 get_overlap_queries(ranges, count, QUERY_COUNT, MAX_ADDR, &queries[0][0]); 215 DEBUG_ALL_THE_THINGS("finished generating overlap queries\n"); 216 for (int i = 0; i < 4*QUERY_COUNT; i++) { 217 int qtype = i / QUERY_COUNT; 218 int qindex = i % QUERY_COUNT; 219 struct query *q = &queries[qtype][qindex]; 220 int result; 221 struct cte *retcap; 222 errval_t r = mdb_find_range(get_type_root(ObjType_RAM), q->begin, q->size, MDB_RANGE_FOUND_PARTIAL, &retcap, &result); 223 if (err_is_fail(r)) { 224 printf("begin = 0x%"PRIxGENVADDR", size = %zu, type = %d\n", q->begin, q->size, qtype); 225 USER_PANIC("mdb_find_range returned with error %d\n", r); 226 } 227 if (result != qtype) { 228 printf("Query: address = 0x%"PRIxGENVADDR", size = %zu\n", q->begin, q->size); 229 if (retcap) { 230 printf("Result: address = 0x%"PRIxGENVADDR", size = %"PRIuGENSIZE"\n", 231 get_address(&retcap->cap), 232 get_size(&retcap->cap)); 233 } 234 USER_PANIC("mdb_find_range returned %d (expected %d)\n", result, qtype); 235 } 236 if (retcap != q->target) { 237 printf("Query: address = 0x%"PRIxGENVADDR", size = %zu\n", q->begin, q->size); 238 USER_PANIC("mdb_find_range returned cap (.base = 0x%" 239 PRIxGENVADDR", .bytes = 0x%"PRIxGENSIZE") (expected (.base = 0x%" 240 PRIxGENVADDR", .bytes = 0x%"PRIxGENSIZE"))\n", 241 retcap->cap.u.ram.base, retcap->cap.u.ram.bytes, 242 q->target->cap.u.ram.base, q->target->cap.u.ram.bytes); 243 } 244 } 245 // empty tree 246 memset(ranges, 0, count * sizeof(struct cte)); 247 mdb_init(&clear); 248 } 249 return 0; 250} 251