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