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 <sel4utils/slab.h>
14#include <vka/capops.h>
15#include <vka/object.h>
16#include <utils/attribute.h>
17
18typedef struct {
19    /* number of objects in the slab */
20    seL4_CPtr n;
21    /* next free object in the slab */
22    seL4_CPtr next;
23    /* list of objects in the slab */
24    vka_object_t *objects;
25} slab_t;
26
27typedef struct {
28    /* allocator to delegate further allocations to */
29    vka_t *delegate;
30    /* allocation slab of each type */
31    slab_t slabs[seL4_ObjectTypeCount];
32    /* untyped to allocate from */
33    vka_object_t untyped;
34} slab_data_t;
35
36typedef struct {
37    ssize_t size_bits;
38    seL4_Word type;
39} object_desc_t;
40
41static int compare_object_descs(const void *a, const void *b)
42{
43    const object_desc_t *obj_a = a;
44    const object_desc_t *obj_b = b;
45    /* order by biggest first */
46    return obj_b->size_bits - obj_a->size_bits;
47}
48
49static int delegate_cspace_alloc(void *data, seL4_CPtr *res)
50{
51    slab_data_t *sdata = data;
52    assert(data != NULL);
53    assert(sdata->delegate != NULL);
54    return vka_cspace_alloc(sdata->delegate, res);
55}
56
57static void delegate_cspace_make_path(void *data, seL4_CPtr slot, cspacepath_t *res)
58{
59    slab_data_t *sdata = data;
60    vka_cspace_make_path(sdata->delegate, slot, res);
61}
62
63static void delegate_cspace_free(void *data, seL4_CPtr slot)
64{
65    slab_data_t *sdata = data;
66    vka_cspace_free(sdata->delegate, slot);
67}
68
69static int slab_utspace_alloc(void *data, const cspacepath_t *dest, seL4_Word type,
70        seL4_Word size_bits, seL4_Word *res)
71{
72    slab_data_t *sdata = data;
73
74    if (type >= seL4_ObjectTypeCount) {
75        return -1;
76    }
77
78    slab_t *slab = &sdata->slabs[type];
79    if (slab->next == slab->n) {
80        ZF_LOGW("Slab of type %lu expired, using delegate allocator", type);
81        return vka_utspace_alloc(sdata->delegate, dest, type, size_bits, res);
82    }
83
84    cspacepath_t src;
85    vka_cspace_make_path(sdata->delegate, slab->objects[slab->next].cptr, &src);
86    if (vka_cnode_move(dest, &src) != seL4_NoError) {
87        ZF_LOGW("Dest invalid\n");
88        return -1;
89    }
90
91    slab->next++;
92    return 0;
93}
94
95static int slab_utspace_alloc_maybe_device(void *data, const cspacepath_t *dest, seL4_Word type,
96                                           seL4_Word size_bits, bool can_use_dev, seL4_Word *res)
97{
98    return slab_utspace_alloc(data, dest, type, size_bits, res);
99}
100
101static int delegate_utspace_alloc_at(void *data, const cspacepath_t *dest, seL4_Word type, seL4_Word size_bits,
102                                     uintptr_t paddr, seL4_Word *res)
103{
104    slab_data_t *sdata = data;
105    return vka_utspace_alloc_at(sdata->delegate, dest, type, size_bits, paddr, res);
106}
107
108static void
109slab_utspace_free(void *data, seL4_Word type, seL4_Word size_bits, seL4_Word target)
110{
111    //TODO this should be possible - swap the object in at next, but do we need it?
112    ZF_LOGW("slab_utspace_free not implemented");
113}
114
115static size_t calculate_total_size(size_t object_freq[seL4_ObjectTypeCount]) {
116    size_t total_size = 0;
117    for (int i = 0; i < seL4_ObjectTypeCount; i++) {
118        if (object_freq[i] > 0) {
119            size_t object_size = vka_get_object_size(i, 0);
120            if (object_size == 0 || object_size == -1) {
121                ZF_LOGE("Object of undetermined size passed to slab allocator");
122                return 0;
123            }
124            total_size += (BIT(object_size)) * object_freq[i];
125        }
126    }
127    return total_size;
128}
129
130static void slab_destroy(vka_t *slab)
131{
132    ZF_LOGW("Slab destroy not implemented");
133}
134
135static seL4_Error alloc_object(vka_t *delegate, vka_object_t *untyped, size_t size_bits, seL4_Word type,
136                               vka_object_t *object)
137{
138    /* allocate slot for object */
139    object->type = type;
140    object->size_bits = size_bits;
141    seL4_Error error = vka_cspace_alloc(delegate, &object->cptr);
142    if (error != seL4_NoError) {
143        ZF_LOGE("Failed to allocate cslot");
144        return error;
145    }
146
147    /* convert to cspacepath */
148    cspacepath_t path;
149    vka_cspace_make_path(delegate, object->cptr, &path);
150
151    /* retype object */
152    return seL4_Untyped_Retype(untyped->cptr, type, size_bits, path.root, path.dest,
153                                        path.destDepth, path.offset, 1);
154}
155
156static int alloc_object_slab(vka_t *delegate, vka_object_t *untyped, slab_t *slab, size_t n,
157                             size_t size_bits, seL4_Word type)
158{
159    ZF_LOGI("Preallocating %zu objects of %zu size bits, %lu type\n", n, size_bits, (long) type);
160
161    slab->n = n;
162    slab->next = 0;
163
164    if (n > 0) {
165        slab->objects = calloc(n, sizeof(vka_object_t));
166        if (slab->objects == NULL) {
167            ZF_LOGI("Failed to allocate %zu objects of %zu size bits, %lu type", n, size_bits, (long) type);
168            return -1;
169        }
170    }
171
172    for (int i = 0; i < slab->n; i++) {
173        if (alloc_object(delegate, untyped, size_bits, type, &slab->objects[i]) != seL4_NoError) {
174            return -1;
175        }
176    }
177
178    /* success */
179    return 0;
180}
181
182int slab_init(vka_t *slab_vka, vka_t *delegate, size_t object_freq[seL4_ObjectTypeCount]) {
183
184    slab_data_t *data = calloc(1, sizeof(slab_data_t));
185
186    if (!data) {
187        slab_destroy(slab_vka);
188        return -1;
189    }
190
191    slab_vka->data = data;
192    data->delegate = delegate;
193
194    slab_vka->cspace_alloc = delegate_cspace_alloc;
195    slab_vka->cspace_make_path = delegate_cspace_make_path;
196    slab_vka->cspace_free = delegate_cspace_free;
197    slab_vka->utspace_alloc_at = delegate_utspace_alloc_at;
198    slab_vka->utspace_alloc = slab_utspace_alloc;
199    slab_vka->utspace_alloc_maybe_device = slab_utspace_alloc_maybe_device;
200    slab_vka->utspace_free = slab_utspace_free;
201
202    /* allocate untyped */
203    size_t total_size = calculate_total_size(object_freq);
204    size_t total_size_bits = seL4_WordBits - CLZL(total_size);
205    /* sanity */
206    assert(BIT(total_size_bits) >= total_size);
207    if (total_size == 0) {
208        ZF_LOGW("No objects to allocate\n");
209        return 0;
210    }
211
212    int error = vka_alloc_untyped(delegate, total_size_bits, &data->untyped);
213    if (error != 0) {
214        ZF_LOGE("Failed to allocate untyped of size bits %zu\n", total_size_bits);
215        slab_destroy(slab_vka);
216        return -1;
217    }
218
219    /* order object sizes by size */
220    object_desc_t object_descs[seL4_ObjectTypeCount];
221    for (int i = 0; i < seL4_ObjectTypeCount; i++) {
222        object_descs[i].type = i;
223        object_descs[i].size_bits = vka_get_object_size(i, 0);
224    }
225
226    qsort(object_descs, seL4_ObjectTypeCount, sizeof(object_desc_t), compare_object_descs);
227
228    /* allocate slabs */
229    for (int i = 0; i < seL4_ObjectTypeCount && object_descs[i].size_bits != 0; i++) {
230        int type = object_descs[i].type;
231        error = alloc_object_slab(delegate, &data->untyped, &data->slabs[type],
232                                  object_freq[type], object_descs[i].size_bits, type);
233        if (error != 0) {
234            ZF_LOGE("Failed to create slab\n");
235            slab_destroy(slab_vka);
236            return -1;
237        }
238    }
239
240    return 0;
241}
242