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 <stdbool.h> 35 #include <assert.h> 36 #include <errno.h> 37 #include <stdlib.h> 38 #include <string.h> 39 #include <pthread.h> 40 41 #include "spdk/blobfs.h" 42 #include "blobfs_internal.h" 43 44 #include "spdk/queue.h" 45 #include "spdk/assert.h" 46 #include "spdk/env.h" 47 #include "spdk_internal/log.h" 48 49 struct cache_buffer * 50 spdk_tree_find_buffer(struct cache_tree *tree, uint64_t offset) 51 { 52 uint64_t index; 53 54 while (tree != NULL) { 55 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 56 if (index >= CACHE_TREE_WIDTH) { 57 return NULL; 58 } 59 if (tree->level == 0) { 60 return tree->u.buffer[index]; 61 } else { 62 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 63 tree = tree->u.tree[index]; 64 } 65 } 66 67 return NULL; 68 } 69 70 struct cache_buffer * 71 spdk_tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset) 72 { 73 struct cache_buffer *buf; 74 75 buf = spdk_tree_find_buffer(tree, offset); 76 if (buf != NULL && buf->bytes_filled > 0) { 77 return buf; 78 } else { 79 return NULL; 80 } 81 } 82 83 struct cache_tree * 84 spdk_tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer) 85 { 86 struct cache_tree *tree; 87 uint64_t index, offset; 88 89 offset = buffer->offset; 90 while (offset >= CACHE_TREE_LEVEL_SIZE(root->level)) { 91 if (root->present_mask != 0) { 92 tree = calloc(1, sizeof(*tree)); 93 tree->level = root->level + 1; 94 tree->u.tree[0] = root; 95 root = tree; 96 root->present_mask = 0x1ULL; 97 } else { 98 root->level++; 99 } 100 } 101 102 tree = root; 103 while (tree->level > 0) { 104 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level); 105 offset &= CACHE_TREE_LEVEL_MASK(tree->level); 106 if (tree->u.tree[index] == NULL) { 107 tree->u.tree[index] = calloc(1, sizeof(*tree)); 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(tree->u.buffer[index] == NULL); 116 tree->u.buffer[index] = buffer; 117 tree->present_mask |= (1ULL << index); 118 return root; 119 } 120 121 void 122 spdk_tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer) 123 { 124 struct cache_tree *child; 125 uint64_t index; 126 127 index = CACHE_TREE_INDEX(tree->level, buffer->offset); 128 129 if (tree->level == 0) { 130 assert(tree->u.buffer[index] != NULL); 131 assert(buffer == tree->u.buffer[index]); 132 tree->present_mask &= ~(1ULL << index); 133 tree->u.buffer[index] = NULL; 134 spdk_cache_buffer_free(buffer); 135 return; 136 } 137 138 child = tree->u.tree[index]; 139 assert(child != NULL); 140 spdk_tree_remove_buffer(child, buffer); 141 if (child->present_mask == 0) { 142 tree->present_mask &= ~(1ULL << index); 143 tree->u.tree[index] = NULL; 144 free(child); 145 } 146 } 147 148 void 149 spdk_tree_free_buffers(struct cache_tree *tree) 150 { 151 struct cache_buffer *buffer; 152 struct cache_tree *child; 153 uint32_t i; 154 155 if (tree->present_mask == 0) { 156 return; 157 } 158 159 if (tree->level == 0) { 160 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 161 buffer = tree->u.buffer[i]; 162 if (buffer != NULL && buffer->in_progress == false && 163 buffer->bytes_filled == buffer->bytes_flushed) { 164 spdk_cache_buffer_free(buffer); 165 tree->u.buffer[i] = NULL; 166 tree->present_mask &= ~(1ULL << i); 167 } 168 } 169 } else { 170 for (i = 0; i < CACHE_TREE_WIDTH; i++) { 171 child = tree->u.tree[i]; 172 if (child != NULL) { 173 spdk_tree_free_buffers(child); 174 if (child->present_mask == 0) { 175 free(child); 176 tree->u.tree[i] = NULL; 177 tree->present_mask &= ~(1ULL << i); 178 } 179 } 180 } 181 } 182 } 183