1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright (C) 2017 Intel Corporation. 3 * All rights reserved. 4 */ 5 6 #include "spdk/stdinc.h" 7 8 #include "cache_tree.h" 9 10 #include "spdk/assert.h" 11 12 struct cache_buffer * 13 tree_find_buffer(struct cache_tree *tree, uint64_t offset) 14 { 15 uint64_t index; 16 17 while (tree != NULL) { 18 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 19 if (index >= CACHE_TREE_WIDTH) { 20 return NULL; 21 } 22 if (tree->level == 0) { 23 return tree->u.buffer[index]; 24 } else { 25 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 26 tree = tree->u.tree[index]; 27 } 28 } 29 30 return NULL; 31 } 32 33 struct cache_buffer * 34 tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset) 35 { 36 struct cache_buffer *buf; 37 38 buf = tree_find_buffer(tree, offset); 39 if (buf != NULL && buf->bytes_filled > 0) { 40 return buf; 41 } else { 42 return NULL; 43 } 44 } 45 46 struct cache_tree * 47 tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer) 48 { 49 struct cache_tree *tree; 50 uint64_t index, offset; 51 52 offset = buffer->offset; 53 while (offset >= CACHE_TREE_LEVEL_SIZE(root->level + 1)) { 54 if (root->present_mask != 0) { 55 tree = calloc(1, sizeof(*tree)); 56 assert(tree != NULL); 57 tree->level = root->level + 1; 58 tree->u.tree[0] = root; 59 root = tree; 60 root->present_mask = 0x1ULL; 61 } else { 62 root->level++; 63 } 64 } 65 66 tree = root; 67 while (tree->level > 0) { 68 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 69 assert(index < CACHE_TREE_WIDTH); 70 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 71 if (tree->u.tree[index] == NULL) { 72 tree->u.tree[index] = calloc(1, sizeof(*tree)); 73 assert(tree->u.tree[index] != NULL); 74 tree->u.tree[index]->level = tree->level - 1; 75 tree->present_mask |= (1ULL << index); 76 } 77 tree = tree->u.tree[index]; 78 } 79 80 index = offset / CACHE_BUFFER_SIZE; 81 assert(index < CACHE_TREE_WIDTH); 82 assert(tree->u.buffer[index] == NULL); 83 tree->u.buffer[index] = buffer; 84 tree->present_mask |= (1ULL << index); 85 return root; 86 } 87 88 void 89 tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer) 90 { 91 struct cache_tree *child; 92 uint64_t index; 93 94 index = CACHE_TREE_INDEX(tree->level, buffer->offset); 95 96 if (tree->level == 0) { 97 assert(tree->u.buffer[index] != NULL); 98 assert(buffer == tree->u.buffer[index]); 99 tree->present_mask &= ~(1ULL << index); 100 tree->u.buffer[index] = NULL; 101 cache_buffer_free(buffer); 102 return; 103 } 104 105 child = tree->u.tree[index]; 106 assert(child != NULL); 107 tree_remove_buffer(child, buffer); 108 if (child->present_mask == 0) { 109 tree->present_mask &= ~(1ULL << index); 110 tree->u.tree[index] = NULL; 111 free(child); 112 } 113 } 114 115 void 116 tree_free_buffers(struct cache_tree *tree) 117 { 118 struct cache_buffer *buffer; 119 struct cache_tree *child; 120 uint32_t i; 121 122 if (tree->present_mask == 0) { 123 return; 124 } 125 126 if (tree->level == 0) { 127 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 128 buffer = tree->u.buffer[i]; 129 if (buffer != NULL && buffer->in_progress == false && 130 buffer->bytes_filled == buffer->bytes_flushed) { 131 cache_buffer_free(buffer); 132 tree->u.buffer[i] = NULL; 133 tree->present_mask &= ~(1ULL << i); 134 } 135 } 136 } else { 137 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 138 child = tree->u.tree[i]; 139 if (child != NULL) { 140 tree_free_buffers(child); 141 if (child->present_mask == 0) { 142 free(child); 143 tree->u.tree[i] = NULL; 144 tree->present_mask &= ~(1ULL << i); 145 } 146 } 147 } 148 } 149 } 150