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