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 <allocman/cspace/single_level.h>
14#include <allocman/util.h>
15#include <allocman/allocman.h>
16#include <sel4/sel4.h>
17#include <string.h>
18
19#define BITS_PER_WORD (sizeof(size_t) * 8)
20
21int cspace_single_level_create(struct allocman *alloc, cspace_single_level_t *cspace, struct cspace_single_level_config config)
22{
23    size_t num_slots;
24    size_t num_entries;
25    int error;
26    cspace->config = config;
27    /* Allocate bitmap */
28    num_slots = cspace->config.end_slot - cspace->config.first_slot;
29    num_entries = num_slots / BITS_PER_WORD;
30    cspace->bitmap_length = num_entries;
31    if (num_slots % BITS_PER_WORD != 0) {
32        num_entries++;
33    }
34    cspace->bitmap = (size_t*)allocman_mspace_alloc(alloc, num_entries * sizeof(size_t), &error);
35    if (error) {
36        return error;
37    }
38    /* Make everything 1's */
39    memset(cspace->bitmap, -1, num_entries * sizeof(size_t));
40    if (num_slots % BITS_PER_WORD != 0) {
41        /* Mark the padding slots as allocated */
42        size_t excess = num_slots % BITS_PER_WORD;
43        size_t i;
44        for (i = excess; i < BITS_PER_WORD; i++) {
45            cspace->bitmap[num_entries - 1] ^= BIT(i);
46        }
47    }
48    cspace->last_entry = 0;
49    return 0;
50}
51
52void cspace_single_level_destroy(struct allocman *alloc, cspace_single_level_t *cspace)
53{
54    allocman_mspace_free(alloc, cspace->bitmap, cspace->bitmap_length * sizeof(size_t));
55}
56
57int _cspace_single_level_alloc(allocman_t *alloc, void *_cspace, cspacepath_t *slot)
58{
59    size_t i;
60    size_t index;
61    cspace_single_level_t *cspace = (cspace_single_level_t*)_cspace;
62    i = cspace->last_entry;
63    if (cspace->bitmap[i] == 0) {
64        assert(cspace->bitmap_length != 0);
65        assert(cspace->last_entry < cspace->bitmap_length);
66        do {
67            i = (i + 1) % cspace->bitmap_length;
68        } while (cspace->bitmap[i] == 0 && i != cspace->last_entry);
69        if (i == cspace->last_entry) {
70            return 1;
71        }
72        cspace->last_entry = i;
73    }
74    index = BITS_PER_WORD - 1 - CLZL(cspace->bitmap[i]);
75    cspace->bitmap[i] &= ~BIT(index);
76    *slot = _cspace_single_level_make_path(cspace, cspace->config.first_slot + (i * BITS_PER_WORD + index));
77    return 0;
78}
79
80int _cspace_single_level_alloc_at(allocman_t *alloc, void *_cspace, seL4_CPtr slot) {
81    cspace_single_level_t *cspace = (cspace_single_level_t*)_cspace;
82    size_t index = slot - cspace->config.first_slot;
83    /* make sure index is in range */
84    if (index / BITS_PER_WORD >= cspace->bitmap_length) {
85        return 1;
86    }
87    /* make sure not already allocated */
88    if ( (cspace->bitmap[index / BITS_PER_WORD] & BIT(index % BITS_PER_WORD)) == 0) {
89        return 1;
90    }
91    /* mark it as allocated */
92    cspace->bitmap[index / BITS_PER_WORD] &= ~BIT(index % BITS_PER_WORD);
93    return 0;
94}
95
96void _cspace_single_level_free(allocman_t *alloc, void *_cspace, const cspacepath_t *slot)
97{
98    cspace_single_level_t *cspace = (cspace_single_level_t*)_cspace;
99    size_t index = slot->capPtr - cspace->config.first_slot;
100    assert((cspace->bitmap[index / BITS_PER_WORD] & BIT(index % BITS_PER_WORD)) == 0);
101    cspace->bitmap[index / BITS_PER_WORD] |= BIT(index % BITS_PER_WORD);
102}
103