ceph/src/spdk/lib/blobfs/tree.c

   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                         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 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 }