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