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