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 spdk_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 spdk_tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset) 69 { 70 struct cache_buffer *buf; 71 72 buf = spdk_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 spdk_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 tree->level = root->level + 1; 91 tree->u.tree[0] = root; 92 root = tree; 93 root->present_mask = 0x1ULL; 94 } else { 95 root->level++; 96 } 97 } 98 99 tree = root; 100 while (tree->level > 0) { 101 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 102 assert(index < CACHE_TREE_WIDTH); 103 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 104 if (tree->u.tree[index] == NULL) { 105 tree->u.tree[index] = calloc(1, sizeof(*tree)); 106 tree->u.tree[index]->level = tree->level - 1; 107 tree->present_mask |= (1ULL << index); 108 } 109 tree = tree->u.tree[index]; 110 } 111 112 index = offset / CACHE_BUFFER_SIZE; 113 assert(index < CACHE_TREE_WIDTH); 114 assert(tree->u.buffer[index] == NULL); 115 tree->u.buffer[index] = buffer; 116 tree->present_mask |= (1ULL << index); 117 return root; 118 } 119 120 void 121 spdk_tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer) 122 { 123 struct cache_tree *child; 124 uint64_t index; 125 126 index = CACHE_TREE_INDEX(tree->level, buffer->offset); 127 128 if (tree->level == 0) { 129 assert(tree->u.buffer[index] != NULL); 130 assert(buffer == tree->u.buffer[index]); 131 tree->present_mask &= ~(1ULL << index); 132 tree->u.buffer[index] = NULL; 133 spdk_cache_buffer_free(buffer); 134 return; 135 } 136 137 child = tree->u.tree[index]; 138 assert(child != NULL); 139 spdk_tree_remove_buffer(child, buffer); 140 if (child->present_mask == 0) { 141 tree->present_mask &= ~(1ULL << index); 142 tree->u.tree[index] = NULL; 143 free(child); 144 } 145 } 146 147 void 148 spdk_tree_free_buffers(struct cache_tree *tree) 149 { 150 struct cache_buffer *buffer; 151 struct cache_tree *child; 152 uint32_t i; 153 154 if (tree->present_mask == 0) { 155 return; 156 } 157 158 if (tree->level == 0) { 159 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 160 buffer = tree->u.buffer[i]; 161 if (buffer != NULL && buffer->in_progress == false && 162 buffer->bytes_filled == buffer->bytes_flushed) { 163 spdk_cache_buffer_free(buffer); 164 tree->u.buffer[i] = NULL; 165 tree->present_mask &= ~(1ULL << i); 166 } 167 } 168 } else { 169 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 170 child = tree->u.tree[i]; 171 if (child != NULL) { 172 spdk_tree_free_buffers(child); 173 if (child->present_mask == 0) { 174 free(child); 175 tree->u.tree[i] = NULL; 176 tree->present_mask &= ~(1ULL << i); 177 } 178 } 179 } 180 } 181 } 182