1 /*- 2 * BSD LICENSE 3 * 4 * Copyright (c) Intel Corporation. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include "spdk/stdinc.h" 35 36 #include "spdk/blobfs.h" 37 #include "tree.h" 38 39 #include "spdk/queue.h" 40 #include "spdk/assert.h" 41 #include "spdk/env.h" 42 #include "spdk_internal/log.h" 43 44 uint32_t g_fs_cache_buffer_shift = CACHE_BUFFER_SHIFT_DEFAULT; 45 46 struct cache_buffer * 47 tree_find_buffer(struct cache_tree *tree, uint64_t offset) 48 { 49 uint64_t index; 50 51 while (tree != NULL) { 52 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 53 if (index >= CACHE_TREE_WIDTH) { 54 return NULL; 55 } 56 if (tree->level == 0) { 57 return tree->u.buffer[index]; 58 } else { 59 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 60 tree = tree->u.tree[index]; 61 } 62 } 63 64 return NULL; 65 } 66 67 struct cache_buffer * 68 tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset) 69 { 70 struct cache_buffer *buf; 71 72 buf = tree_find_buffer(tree, offset); 73 if (buf != NULL && buf->bytes_filled > 0) { 74 return buf; 75 } else { 76 return NULL; 77 } 78 } 79 80 struct cache_tree * 81 tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer) 82 { 83 struct cache_tree *tree; 84 uint64_t index, offset; 85 86 offset = buffer->offset; 87 while (offset >= CACHE_TREE_LEVEL_SIZE(root->level + 1)) { 88 if (root->present_mask != 0) { 89 tree = calloc(1, sizeof(*tree)); 90 assert(tree != NULL); 91 tree->level = root->level + 1; 92 tree->u.tree[0] = root; 93 root = tree; 94 root->present_mask = 0x1ULL; 95 } else { 96 root->level++; 97 } 98 } 99 100 tree = root; 101 while (tree->level > 0) { 102 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 103 assert(index < CACHE_TREE_WIDTH); 104 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 105 if (tree->u.tree[index] == NULL) { 106 tree->u.tree[index] = calloc(1, sizeof(*tree)); 107 assert(tree->u.tree[index] != NULL); 108 tree->u.tree[index]->level = tree->level - 1; 109 tree->present_mask |= (1ULL << index); 110 } 111 tree = tree->u.tree[index]; 112 } 113 114 index = offset / CACHE_BUFFER_SIZE; 115 assert(index < CACHE_TREE_WIDTH); 116 assert(tree->u.buffer[index] == NULL); 117 tree->u.buffer[index] = buffer; 118 tree->present_mask |= (1ULL << index); 119 return root; 120 } 121 122 void 123 tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer) 124 { 125 struct cache_tree *child; 126 uint64_t index; 127 128 index = CACHE_TREE_INDEX(tree->level, buffer->offset); 129 130 if (tree->level == 0) { 131 assert(tree->u.buffer[index] != NULL); 132 assert(buffer == tree->u.buffer[index]); 133 tree->present_mask &= ~(1ULL << index); 134 tree->u.buffer[index] = NULL; 135 cache_buffer_free(buffer); 136 return; 137 } 138 139 child = tree->u.tree[index]; 140 assert(child != NULL); 141 tree_remove_buffer(child, buffer); 142 if (child->present_mask == 0) { 143 tree->present_mask &= ~(1ULL << index); 144 tree->u.tree[index] = NULL; 145 free(child); 146 } 147 } 148 149 void 150 tree_free_buffers(struct cache_tree *tree) 151 { 152 struct cache_buffer *buffer; 153 struct cache_tree *child; 154 uint32_t i; 155 156 if (tree->present_mask == 0) { 157 return; 158 } 159 160 if (tree->level == 0) { 161 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 162 buffer = tree->u.buffer[i]; 163 if (buffer != NULL && buffer->in_progress == false && 164 buffer->bytes_filled == buffer->bytes_flushed) { 165 cache_buffer_free(buffer); 166 tree->u.buffer[i] = NULL; 167 tree->present_mask &= ~(1ULL << i); 168 } 169 } 170 } else { 171 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 172 child = tree->u.tree[i]; 173 if (child != NULL) { 174 tree_free_buffers(child); 175 if (child->present_mask == 0) { 176 free(child); 177 tree->u.tree[i] = NULL; 178 tree->present_mask &= ~(1ULL << i); 179 } 180 } 181 } 182 } 183 } 184