1/*
2 * Copyright 2017, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(DATA61_BSD)
11 */
12
13#include <assert.h>
14#include <autoconf.h>
15#include <sel4vka/gen_config.h>
16#include <sel4/sel4.h>
17#include <stddef.h>
18#include <stdint.h>
19#include <stdio.h>
20#include <stdlib.h>
21#include <vka/cspacepath_t.h>
22#include <vka/vka.h>
23
24#ifndef CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_SLOTS_SZ
25#define CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_SLOTS_SZ 0
26#endif
27#ifndef CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_OBJS_SZ
28#define CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_SLOTS_SZ 0
29#endif
30
31/* Kconfig-set sizes for buffers to track live slots and objects. */
32static size_t live_slots_sz = CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_SLOTS_SZ;
33static size_t live_objs_sz = CONFIG_LIB_SEL4_VKA_DEBUG_LIVE_OBJS_SZ;
34
35typedef struct {
36
37    /* The underlying allocator that we call to effect allocations. This is
38     * effectively our debugging target if we're troubleshooting problems with
39     * the allocator itself.
40     */
41    vka_t *underlying;
42
43    /* Metadata related to currently live CSlots. The live_slots list contains
44     * non-null entries representing currently live CSlots. Note that these may
45     * be interspersed with null (dead) entries.
46     */
47    seL4_CPtr *live_slots;
48    size_t live_slots_sz;
49
50    /* Metadata related to currently live objects. The live_objs list contains
51     * live entries with non-0 cookie members, potentially interspersed with
52     * dead entries with 0 cookies. The other members are used for confirming
53     * that a caller is freeing an object in the same way they allocated it.
54     */
55    struct obj {
56        seL4_Word type;
57        seL4_Word size_bits;
58        seL4_Word cookie;
59    } *live_objs;
60    size_t live_objs_sz;
61
62} state_t;
63
64/* This is called when we encounter an allocator/caller error. */
65#define fatal(args...) do { \
66        fprintf(stderr, "VKA debug: " args); \
67        fprintf(stderr, "\n"); \
68        abort(); \
69    } while (0)
70
71/* This is called when we encounter a non-fatal problem. */
72#define warn(args...) do { \
73        fprintf(stderr, "VKA debug: " args); \
74        fprintf(stderr, "\n"); \
75    } while (0)
76
77/* Track a slot that has just become live. */
78static void track_slot(state_t *state, seL4_CPtr slot)
79{
80    assert(state != NULL);
81
82    if (state->live_slots_sz == 0) {
83        /* Disable tracking if we have no buffer. */
84        return;
85    }
86
87    if (slot == 0) {
88        fatal("allocator attempted to hand out the null slot");
89    }
90
91    /* Search the current list of live slots for this slot in case it's
92     * currently live. Pretty slow to do this on every allocate, but we're
93     * debugging so hey.
94     */
95    unsigned int available = 0;
96    for (unsigned int i = 0; i < state->live_slots_sz; i++) {
97        if (state->live_slots[i] == slot) {
98            fatal("allocator attempted to hand out slot %lu that is currently "
99                  "in use", (long)slot);
100        } else if (available == i && state->live_slots[i] != 0) {
101            available++;
102        }
103    }
104
105    if (available == state->live_slots_sz) {
106        /* The entire live slot list is full. */
107        warn("ran out of space for tracking slots; disabling tracking");
108        state->live_slots_sz = 0;
109    } else {
110        state->live_slots[available] = slot;
111    }
112}
113
114static int cspace_alloc(void *data, seL4_CPtr *res)
115{
116    assert(data != NULL);
117
118    state_t *s = (state_t *)data;
119    vka_t *v = s->underlying;
120    int result = v->cspace_alloc(v->data, res);
121    if (result == 0 && res != NULL) {
122        track_slot(s, *res);
123    }
124    return result;
125}
126
127/* Stop tracking a slot that is now dead. */
128static void untrack_slot(state_t *state, seL4_CPtr slot)
129{
130    assert(state != NULL);
131
132    for (unsigned int i = 0; i < state->live_slots_sz; i++) {
133        if (state->live_slots[i] == slot) {
134            /* Found it. */
135            state->live_slots[i] = 0;
136            return;
137        }
138    }
139    fatal("attempt to free slot %lu that was not live (double free?)", (long)slot);
140}
141
142static void cspace_free(void *data, seL4_CPtr slot)
143{
144    assert(data != NULL);
145
146    state_t *s = (state_t *)data;
147
148    if (slot != 0) {
149        /* Let's assume malloc semantics, i.e. that it's always OK to free
150         * NULL. Therefore the caller may have called this with 0 even if they
151         * were never handed out 0. We should ignore trying to untrack this.
152         */
153        untrack_slot(s, slot);
154    }
155    vka_t *v = s->underlying;
156    v->cspace_free(v->data, slot);
157}
158
159/* No instrumentation required for this one. Just invoke the underlying
160 * allocator.
161 */
162static void cspace_make_path(void *data, seL4_CPtr slot, cspacepath_t *res)
163{
164    assert(data != NULL);
165
166    state_t *s = (state_t *)data;
167    vka_t *v = s->underlying;
168    v->cspace_make_path(v->data, slot, res);
169}
170
171/* Track an object that has just become live. Logic is essentially the same as
172 * track_slot. Refer to the comments in it for explanations.
173 */
174static void track_obj(state_t *state, seL4_Word type, seL4_Word size_bits,
175                      seL4_Word cookie)
176{
177    assert(state != NULL);
178
179    if (state->live_objs_sz == 0) {
180        return;
181    }
182
183    if (cookie == 0) {
184        fatal("allocator attempted to hand out an object with no cookie");
185    }
186
187    unsigned int available = 0;
188    for (unsigned int i = 0; i < state->live_objs_sz; i++) {
189        if (state->live_objs[i].cookie == cookie) {
190            fatal("allocator attempted to hand out an object with a cookie %zu "
191                  "that is currently in use", cookie);
192        } else if (available == i && state->live_objs[i].cookie != 0) {
193            available++;
194        }
195    }
196
197    if (available == state->live_objs_sz) {
198        warn("ran out of space for tracking objects; disabling tracking");
199        state->live_objs_sz = 0;
200    } else {
201        state->live_objs[available].type = type;
202        state->live_objs[available].size_bits = size_bits;
203        state->live_objs[available].cookie = cookie;
204    }
205}
206
207static int utspace_alloc(void *data, const cspacepath_t *dest, seL4_Word type,
208                         seL4_Word size_bits, seL4_Word *res)
209{
210    assert(data != NULL);
211
212    state_t *s = (state_t *)data;
213
214    /* At this point I guess we could check that dest is a path that was
215     * previously returned from cspace_make_path, but there seems to be nothing
216     * in the interface that spells out that dest needs to have originated from
217     * this allocator and not another co-existing one.
218     */
219
220    vka_t *v = s->underlying;
221    int result = v->utspace_alloc(v->data, dest, type, size_bits, res);
222    if (result == 0 && res != NULL) {
223        track_obj(s, type, size_bits, *res);
224    }
225    return result;
226}
227
228static int utspace_alloc_maybe_device(void *data, const cspacepath_t *dest, seL4_Word type,
229                                      seL4_Word size_bits, bool can_use_dev, seL4_Word *res)
230{
231    assert(data != NULL);
232
233    state_t *s = (state_t *)data;
234
235    vka_t *v = s->underlying;
236    int result = v->utspace_alloc_maybe_device(v->data, dest, type, size_bits, can_use_dev, res);
237    if (result == 0 && res != NULL) {
238        track_obj(s, type, size_bits, *res);
239    }
240    return result;
241}
242
243static int utspace_alloc_at(void *data, const cspacepath_t *dest, seL4_Word type,
244                            seL4_Word size_bits, uintptr_t paddr, seL4_Word *cookie)
245{
246    assert(data != NULL);
247
248    state_t *s = (state_t *)data;
249
250    /* At this point I guess we could check that dest is a path that was
251     * previously returned from cspace_make_path, but there seems to be nothing
252     * in the interface that spells out that dest needs to have originated from
253     * this allocator and not another co-existing one.
254     */
255
256    vka_t *v = s->underlying;
257    int result = v->utspace_alloc_at(v->data, dest, type, size_bits, paddr, cookie);
258    if (result == 0 && cookie != NULL) {
259        track_obj(s, type, size_bits, *cookie);
260    }
261    return result;
262}
263
264/* Stop tracking an object that is now dead. */
265static void untrack_obj(state_t *state, seL4_Word type, seL4_Word size_bits,
266                        seL4_Word cookie)
267{
268    assert(state != NULL);
269
270    for (unsigned int i = 0; i < state->live_objs_sz; i++) {
271        if (state->live_objs[i].cookie == cookie) {
272            if (state->live_objs[i].type != type) {
273                fatal("attempt to free object with type %d that was allocated "
274                      "with type %d", (int)type, (int)state->live_objs[i].type);
275            }
276            if (state->live_objs[i].size_bits != size_bits) {
277                fatal("attempt to free object with size %d that was allocated "
278                      "with size %d", (int)size_bits, (int)state->live_objs[i].size_bits);
279            }
280            state->live_objs[i].cookie = 0;
281            return;
282        }
283    }
284    fatal("attempt to free object %lu that was not live (double free?)",
285          (long)cookie);
286}
287
288static void utspace_free(void *data, seL4_Word type, seL4_Word size_bits,
289                         seL4_Word target)
290{
291    assert(data != NULL);
292
293    state_t *s = (state_t *)data;
294    vka_t *v = s->underlying;
295    if (target != 0) {
296        /* Again, assume malloc semantics that freeing NULL is fine. */
297        untrack_obj(s, type, size_bits, target);
298    }
299    v->utspace_free(v->data, type, size_bits, target);
300}
301
302int vka_init_debugvka(vka_t *vka, vka_t *tracee)
303{
304    assert(vka != NULL);
305
306    state_t *s = (state_t *)malloc(sizeof(state_t));
307    if (s == NULL) {
308        goto fail;
309    }
310    s->underlying = tracee;
311    s->live_slots = NULL;
312    s->live_objs = NULL;
313
314    s->live_slots_sz = live_slots_sz;
315    if (live_slots_sz > 0) {
316        s->live_slots = (seL4_CPtr *)malloc(sizeof(seL4_CPtr) * live_slots_sz);
317        if (s->live_slots == NULL) {
318            goto fail;
319        }
320    }
321
322    s->live_objs_sz = live_objs_sz;
323    if (live_objs_sz > 0) {
324        s->live_objs = (struct obj *)malloc(sizeof(struct obj) * live_objs_sz);
325        if (s->live_objs == NULL) {
326            goto fail;
327        }
328    }
329
330    vka->data = (void *)s;
331    vka->cspace_alloc = cspace_alloc;
332    vka->cspace_make_path = cspace_make_path;
333    vka->utspace_alloc = utspace_alloc;
334    vka->utspace_alloc_maybe_device = utspace_alloc_maybe_device;
335    vka->utspace_alloc_at = utspace_alloc_at;
336    vka->cspace_free = cspace_free;
337    vka->utspace_free = utspace_free;
338
339    return 0;
340
341fail:
342    if (s != NULL) {
343        if (s->live_slots != NULL) {
344            free(s->live_slots);
345        }
346        if (s->live_objs != NULL) {
347            free(s->live_objs);
348        }
349        free(s);
350    }
351    return -1;
352}
353