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/log.h" 43 44 struct cache_buffer * 45 tree_find_buffer(struct cache_tree *tree, uint64_t offset) 46 { 47 uint64_t index; 48 49 while (tree != NULL) { 50 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 51 if (index >= CACHE_TREE_WIDTH) { 52 return NULL; 53 } 54 if (tree->level == 0) { 55 return tree->u.buffer[index]; 56 } else { 57 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 58 tree = tree->u.tree[index]; 59 } 60 } 61 62 return NULL; 63 } 64 65 struct cache_buffer * 66 tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset) 67 { 68 struct cache_buffer *buf; 69 70 buf = tree_find_buffer(tree, offset); 71 if (buf != NULL && buf->bytes_filled > 0) { 72 return buf; 73 } else { 74 return NULL; 75 } 76 } 77 78 struct cache_tree * 79 tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer) 80 { 81 struct cache_tree *tree; 82 uint64_t index, offset; 83 84 offset = buffer->offset; 85 while (offset >= CACHE_TREE_LEVEL_SIZE(root->level + 1)) { 86 if (root->present_mask != 0) { 87 tree = calloc(1, sizeof(*tree)); 88 assert(tree != NULL); 89 tree->level = root->level + 1; 90 tree->u.tree[0] = root; 91 root = tree; 92 root->present_mask = 0x1ULL; 93 } else { 94 root->level++; 95 } 96 } 97 98 tree = root; 99 while (tree->level > 0) { 100 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 101 assert(index < CACHE_TREE_WIDTH); 102 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 103 if (tree->u.tree[index] == NULL) { 104 tree->u.tree[index] = calloc(1, sizeof(*tree)); 105 assert(tree->u.tree[index] != NULL); 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 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 cache_buffer_free(buffer); 134 return; 135 } 136 137 child = tree->u.tree[index]; 138 assert(child != NULL); 139 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 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 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 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