Line data    Source code

       1             : /*   SPDX-License-Identifier: BSD-3-Clause
       2             :  *   Copyright (C) 2017 Intel Corporation.
       3             :  *   All rights reserved.
       4             :  */
       5             : 
       6             : #include "spdk/stdinc.h"
       7             : 
       8             : #include "cache_tree.h"
       9             : 
      10             : #include "spdk/assert.h"
      11             : 
      12             : struct cache_buffer *
      13          46 : tree_find_buffer(struct cache_tree *tree, uint64_t offset)
      14             : {
      15          46 :         uint64_t index;
      16             : 
      17          62 :         while (tree != NULL) {
      18          57 :                 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level);
      19          57 :                 if (index >= CACHE_TREE_WIDTH) {
      20           0 :                         return NULL;
      21             :                 }
      22          57 :                 if (tree->level == 0) {
      23          41 :                         return tree->u.buffer[index];
      24             :                 } else {
      25          16 :                         offset &= CACHE_TREE_LEVEL_MASK(tree->level);
      26          16 :                         tree = tree->u.tree[index];
      27             :                 }
      28             :         }
      29             : 
      30           5 :         return NULL;
      31          46 : }
      32             : 
      33             : struct cache_buffer *
      34           3 : tree_find_filled_buffer(struct cache_tree *tree, uint64_t offset)
      35             : {
      36           3 :         struct cache_buffer *buf;
      37             : 
      38           3 :         buf = tree_find_buffer(tree, offset);
      39           3 :         if (buf != NULL && buf->bytes_filled > 0) {
      40           2 :                 return buf;
      41             :         } else {
      42           1 :                 return NULL;
      43             :         }
      44           3 : }
      45             : 
      46             : struct cache_tree *
      47          16 : tree_insert_buffer(struct cache_tree *root, struct cache_buffer *buffer)
      48             : {
      49          16 :         struct cache_tree *tree;
      50          16 :         uint64_t index, offset;
      51             : 
      52          16 :         offset = buffer->offset;
      53          19 :         while (offset >= CACHE_TREE_LEVEL_SIZE(root->level + 1)) {
      54           3 :                 if (root->present_mask != 0) {
      55           3 :                         tree = calloc(1, sizeof(*tree));
      56           3 :                         assert(tree != NULL);
      57           3 :                         tree->level = root->level + 1;
      58           3 :                         tree->u.tree[0] = root;
      59           3 :                         root = tree;
      60           3 :                         root->present_mask = 0x1ULL;
      61           3 :                 } else {
      62           0 :                         root->level++;
      63             :                 }
      64             :         }
      65             : 
      66          16 :         tree = root;
      67          21 :         while (tree->level > 0) {
      68           5 :                 index = offset / CACHE_TREE_LEVEL_SIZE(tree->level);
      69           5 :                 assert(index < CACHE_TREE_WIDTH);
      70           5 :                 offset &= CACHE_TREE_LEVEL_MASK(tree->level);
      71           5 :                 if (tree->u.tree[index] == NULL) {
      72           5 :                         tree->u.tree[index] = calloc(1, sizeof(*tree));
      73           5 :                         assert(tree->u.tree[index] != NULL);
      74           5 :                         tree->u.tree[index]->level = tree->level - 1;
      75           5 :                         tree->present_mask |= (1ULL << index);
      76           5 :                 }
      77           5 :                 tree = tree->u.tree[index];
      78             :         }
      79             : 
      80          16 :         index = offset / CACHE_BUFFER_SIZE;
      81          16 :         assert(index < CACHE_TREE_WIDTH);
      82          16 :         assert(tree->u.buffer[index] == NULL);
      83          16 :         tree->u.buffer[index] = buffer;
      84          16 :         tree->present_mask |= (1ULL << index);
      85          32 :         return root;
      86          16 : }
      87             : 
      88             : void
      89           6 : tree_remove_buffer(struct cache_tree *tree, struct cache_buffer *buffer)
      90             : {
      91           6 :         struct cache_tree *child;
      92           6 :         uint64_t index;
      93             : 
      94           6 :         index = CACHE_TREE_INDEX(tree->level, buffer->offset);
      95             : 
      96           6 :         if (tree->level == 0) {
      97           2 :                 assert(tree->u.buffer[index] != NULL);
      98           2 :                 assert(buffer == tree->u.buffer[index]);
      99           2 :                 tree->present_mask &= ~(1ULL << index);
     100           2 :                 tree->u.buffer[index] = NULL;
     101           2 :                 cache_buffer_free(buffer);
     102           2 :                 return;
     103             :         }
     104             : 
     105           4 :         child = tree->u.tree[index];
     106           4 :         assert(child != NULL);
     107           4 :         tree_remove_buffer(child, buffer);
     108           4 :         if (child->present_mask == 0) {
     109           1 :                 tree->present_mask &= ~(1ULL << index);
     110           1 :                 tree->u.tree[index] = NULL;
     111           1 :                 free(child);
     112           1 :         }
     113           6 : }
     114             : 
     115             : void
     116          16 : tree_free_buffers(struct cache_tree *tree)
     117             : {
     118          16 :         struct cache_buffer *buffer;
     119          16 :         struct cache_tree *child;
     120          16 :         uint32_t i;
     121             : 
     122          16 :         if (tree->present_mask == 0) {
     123           0 :                 return;
     124             :         }
     125             : 
     126          16 :         if (tree->level == 0) {
     127         650 :                 for (i = 0; i < CACHE_TREE_WIDTH; i++) {
     128         640 :                         buffer = tree->u.buffer[i];
     129         656 :                         if (buffer != NULL && buffer->in_progress == false &&
     130          16 :                             buffer->bytes_filled == buffer->bytes_flushed) {
     131          16 :                                 cache_buffer_free(buffer);
     132          16 :                                 tree->u.buffer[i] = NULL;
     133          16 :                                 tree->present_mask &= ~(1ULL << i);
     134          16 :                         }
     135         640 :                 }
     136          10 :         } else {
     137         390 :                 for (i = 0; i < CACHE_TREE_WIDTH; i++) {
     138         384 :                         child = tree->u.tree[i];
     139         384 :                         if (child != NULL) {
     140           9 :                                 tree_free_buffers(child);
     141           9 :                                 if (child->present_mask == 0) {
     142           9 :                                         free(child);
     143           9 :                                         tree->u.tree[i] = NULL;
     144           9 :                                         tree->present_mask &= ~(1ULL << i);
     145           9 :                                 }
     146           9 :                         }
     147         384 :                 }
     148             :         }
     149          16 : }