LCOV - code coverage report
Current view: top level - drivers - block-cache.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 245 0.0 %
Date: 2024-06-19 15:27:45 Functions: 0 33 0.0 %
Branches: 0 116 0.0 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (c) 2016, Citrix Systems, Inc.
       3                 :            :  *
       4                 :            :  * All rights reserved.
       5                 :            :  *
       6                 :            :  * Redistribution and use in source and binary forms, with or without
       7                 :            :  * modification, are permitted provided that the following conditions are met:
       8                 :            :  * 
       9                 :            :  *  1. Redistributions of source code must retain the above copyright
      10                 :            :  *     notice, this list of conditions and the following disclaimer.
      11                 :            :  *  2. Redistributions in binary form must reproduce the above copyright
      12                 :            :  *     notice, this list of conditions and the following disclaimer in the
      13                 :            :  *     documentation and/or other materials provided with the distribution.
      14                 :            :  *  3. Neither the name of the copyright holder nor the names of its 
      15                 :            :  *     contributors may be used to endorse or promote products derived from 
      16                 :            :  *     this software without specific prior written permission.
      17                 :            :  *
      18                 :            :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
      19                 :            :  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
      20                 :            :  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
      21                 :            :  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
      22                 :            :  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
      23                 :            :  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
      24                 :            :  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
      25                 :            :  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
      26                 :            :  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
      27                 :            :  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
      28                 :            :  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      29                 :            :  */
      30                 :            : 
      31                 :            : #ifdef HAVE_CONFIG_H
      32                 :            : #include "config.h"
      33                 :            : #endif
      34                 :            : 
      35                 :            : #include <errno.h>
      36                 :            : #include <fcntl.h>
      37                 :            : #include <unistd.h>
      38                 :            : #include <stdlib.h>
      39                 :            : #include <sys/mman.h>
      40                 :            : 
      41                 :            : #include "tapdisk.h"
      42                 :            : #include "tapdisk-utils.h"
      43                 :            : #include "tapdisk-driver.h"
      44                 :            : #include "tapdisk-server.h"
      45                 :            : #include "tapdisk-interface.h"
      46                 :            : #include "timeout-math.h"
      47                 :            : 
      48                 :            : #ifdef DEBUG
      49                 :            : #define DBG(_f, _a...) tlog_write(TLOG_DBG, _f, ##_a)
      50                 :            : #else
      51                 :            : #define DBG(_f, _a...) ((void)0)
      52                 :            : #endif
      53                 :            : 
      54                 :            : #define WARN(_f, _a...) tlog_write(TLOG_WARN, _f, ##_a)
      55                 :            : 
      56                 :            : #define RADIX_TREE_PAGE_SHIFT           12 /* 4K pages */
      57                 :            : #define RADIX_TREE_PAGE_SIZE            (1 << RADIX_TREE_PAGE_SHIFT)
      58                 :            : 
      59                 :            : #define RADIX_TREE_NODE_SHIFT           9 /* 512B nodes */
      60                 :            : #define RADIX_TREE_NODE_SIZE            (1 << RADIX_TREE_NODE_SHIFT)
      61                 :            : #define RADIX_TREE_NODE_MASK            (RADIX_TREE_NODE_SIZE - 1)
      62                 :            : 
      63                 :            : #define BLOCK_CACHE_NODES_PER_PAGE      (1 << (RADIX_TREE_PAGE_SHIFT - RADIX_TREE_NODE_SHIFT))
      64                 :            : 
      65                 :            : #define BLOCK_CACHE_MAX_SIZE            (10 << 20) /* 100MB cache */
      66                 :            : #define BLOCK_CACHE_REQUESTS            (TAPDISK_DATA_REQUESTS << 3)
      67                 :            : #define BLOCK_CACHE_PAGE_IDLETIME       60
      68                 :            : 
      69                 :            : typedef struct radix_tree               radix_tree_t;
      70                 :            : typedef struct radix_tree_node          radix_tree_node_t;
      71                 :            : typedef struct radix_tree_link          radix_tree_link_t;
      72                 :            : typedef struct radix_tree_leaf          radix_tree_leaf_t;
      73                 :            : typedef struct radix_tree_page          radix_tree_page_t;
      74                 :            : 
      75                 :            : typedef struct block_cache              block_cache_t;
      76                 :            : typedef struct block_cache_request      block_cache_request_t;
      77                 :            : typedef struct block_cache_stats        block_cache_stats_t;
      78                 :            : 
      79                 :            : struct radix_tree_page {
      80                 :            :         char                           *buf;
      81                 :            :         size_t                          size;
      82                 :            :         uint64_t                        sec;
      83                 :            :         radix_tree_link_t              *owners[BLOCK_CACHE_NODES_PER_PAGE];
      84                 :            : };
      85                 :            : 
      86                 :            : struct radix_tree_leaf {
      87                 :            :         radix_tree_page_t              *page;
      88                 :            :         char                           *buf;
      89                 :            : };
      90                 :            : 
      91                 :            : struct radix_tree_link {
      92                 :            :         uint32_t                        time;
      93                 :            :         union {
      94                 :            :                 radix_tree_node_t      *next;
      95                 :            :                 radix_tree_leaf_t       leaf;
      96                 :            :         } u;
      97                 :            : };
      98                 :            : 
      99                 :            : struct radix_tree_node {
     100                 :            :         int                             height;
     101                 :            :         radix_tree_link_t               links[RADIX_TREE_NODE_SIZE];
     102                 :            : };
     103                 :            : 
     104                 :            : struct radix_tree {
     105                 :            :         int                             height;
     106                 :            :         uint64_t                        size;
     107                 :            :         uint32_t                        nodes;
     108                 :            :         radix_tree_node_t              *root;
     109                 :            : 
     110                 :            :         block_cache_t                  *cache;
     111                 :            : };
     112                 :            : 
     113                 :            : struct block_cache_request {
     114                 :            :         int                             err;
     115                 :            :         char                           *buf;
     116                 :            :         uint64_t                        secs;
     117                 :            :         td_request_t                    treq;
     118                 :            :         block_cache_t                  *cache;
     119                 :            : };
     120                 :            : 
     121                 :            : struct block_cache_stats {
     122                 :            :         uint64_t                        reads;
     123                 :            :         uint64_t                        hits;
     124                 :            :         uint64_t                        misses;
     125                 :            :         uint64_t                        prunes;
     126                 :            : };
     127                 :            : 
     128                 :            : struct block_cache {
     129                 :            :         int                             ptype;
     130                 :            :         char                           *name;
     131                 :            : 
     132                 :            :         uint64_t                        sectors;
     133                 :            : 
     134                 :            :         block_cache_request_t           requests[BLOCK_CACHE_REQUESTS];
     135                 :            :         block_cache_request_t          *request_free_list[BLOCK_CACHE_REQUESTS];
     136                 :            :         int                             requests_free;
     137                 :            : 
     138                 :            :         event_id_t                      timeout_id;
     139                 :            : 
     140                 :            :         radix_tree_t                    tree;
     141                 :            : 
     142                 :            :         block_cache_stats_t             stats;
     143                 :            : };
     144                 :            : 
     145                 :            : static inline uint64_t
     146                 :            : radix_tree_calculate_size(int height)
     147                 :            : {
     148                 :          0 :         return (uint64_t)RADIX_TREE_NODE_SIZE <<
     149                 :          0 :           (height * RADIX_TREE_NODE_SHIFT);
     150                 :            : }
     151                 :            : 
     152                 :            : static inline int
     153                 :            : radix_tree_calculate_height(uint64_t sectors)
     154                 :            : {
     155                 :            :         int height;
     156                 :            :         uint64_t tree_size;
     157                 :            : 
     158                 :          0 :         height = 1;  /* always allocate root node */
     159                 :          0 :         tree_size = radix_tree_calculate_size(height);
     160         [ #  # ]:          0 :         while (sectors > tree_size)
     161                 :          0 :                 tree_size = radix_tree_calculate_size(++height);
     162                 :            : 
     163                 :            :         return height;
     164                 :            : }
     165                 :            : 
     166                 :            : static inline int
     167                 :          0 : radix_tree_index(radix_tree_node_t *node, uint64_t sector)
     168                 :            : {
     169                 :          0 :         return ((sector >> (node->height * RADIX_TREE_NODE_SHIFT)) &
     170                 :            :                 RADIX_TREE_NODE_MASK);
     171                 :            : }
     172                 :            : 
     173                 :            : static inline int
     174                 :          0 : radix_tree_node_contains_leaves(radix_tree_t *tree, radix_tree_node_t *node)
     175                 :            : {
     176                 :          0 :         return (node->height == 0);
     177                 :            : }
     178                 :            : 
     179                 :            : static inline int
     180                 :          0 : radix_tree_node_is_root(radix_tree_t *tree, radix_tree_node_t *node)
     181                 :            : {
     182                 :          0 :         return (node->height == tree->height);
     183                 :            : }
     184                 :            : 
     185                 :            : static inline uint64_t
     186                 :          0 : radix_tree_size(radix_tree_t *tree)
     187                 :            : {
     188                 :          0 :         return tree->size + tree->nodes * sizeof(radix_tree_node_t);
     189                 :            : }
     190                 :            : 
     191                 :            : static inline void
     192                 :            : radix_tree_clear_link(radix_tree_link_t *link)
     193                 :            : {
     194 [ #  # ][ #  # ]:          0 :         if (link)
         [ #  # ][ #  # ]
     195                 :            :                 memset(link, 0, sizeof(radix_tree_link_t));
     196                 :            : }
     197                 :            : 
     198                 :            : static inline radix_tree_node_t *
     199                 :          0 : radix_tree_allocate_node(radix_tree_t *tree, int height)
     200                 :            : {
     201                 :            :         radix_tree_node_t *node;
     202                 :            : 
     203                 :          0 :         node = calloc(1, sizeof(radix_tree_node_t));
     204 [ #  # ][ #  # ]:          0 :         if (!node)
     205                 :            :                 return NULL;
     206                 :            : 
     207                 :          0 :         node->height = height;
     208                 :          0 :         tree->nodes++;
     209                 :            : 
     210                 :          0 :         return node;
     211                 :            : }
     212                 :            : 
     213                 :            : static inline radix_tree_node_t *
     214                 :          0 : radix_tree_allocate_child_node(radix_tree_t *tree, radix_tree_node_t *parent)
     215                 :            : {
     216                 :          0 :         return radix_tree_allocate_node(tree, parent->height - 1);
     217                 :            : }
     218                 :            : 
     219                 :            : void
     220                 :          0 : radix_tree_free_node(radix_tree_t *tree, radix_tree_node_t *node)
     221                 :            : {
     222         [ #  # ]:          0 :         if (!node)
     223                 :          0 :                 return;
     224                 :            : 
     225                 :          0 :         free(node);
     226                 :          0 :         tree->nodes--;
     227                 :            : }
     228                 :            : 
     229                 :            : static inline radix_tree_page_t *
     230                 :          0 : radix_tree_allocate_page(radix_tree_t *tree,
     231                 :            :                          char *buf, uint64_t sec, size_t size)
     232                 :            : {
     233                 :            :         radix_tree_page_t *page;
     234                 :            : 
     235                 :          0 :         page = calloc(1, sizeof(radix_tree_page_t));
     236         [ #  # ]:          0 :         if (!page)
     237                 :            :                 return NULL;
     238                 :            : 
     239                 :          0 :         page->buf   = buf;
     240                 :          0 :         page->sec   = sec;
     241                 :          0 :         page->size  = size;
     242                 :          0 :         tree->size += size;
     243                 :            : 
     244                 :          0 :         return page;
     245                 :            : }
     246                 :            : 
     247                 :            : static inline void
     248                 :          0 : radix_tree_free_page(radix_tree_t *tree, radix_tree_page_t *page)
     249                 :            : {
     250                 :            :         int i;
     251                 :            : 
     252         [ #  # ]:          0 :         for (i = 0; i < page->size >> RADIX_TREE_NODE_SHIFT; i++)
     253                 :            :                 DBG("%s: ejecting sector 0x%llx\n",
     254                 :            :                     tree->cache->name, page->sec + i);
     255                 :            : 
     256                 :          0 :         tree->cache->stats.prunes += (page->size >> RADIX_TREE_NODE_SHIFT);
     257                 :          0 :         tree->size -= page->size;
     258                 :          0 :         free(page->buf);
     259                 :          0 :         free(page);
     260                 :          0 : }
     261                 :            : 
     262                 :            : /*
     263                 :            :  * remove a leaf and the shared radix_tree_page_t containing its buffer.
     264                 :            :  * leaves are deleted, nodes are not; gc will reap the nodes later.
     265                 :            :  */
     266                 :            : static void
     267                 :          0 : radix_tree_remove_page(radix_tree_t *tree, radix_tree_page_t *page)
     268                 :            : {
     269                 :            :         int i;
     270                 :            : 
     271         [ #  # ]:          0 :         if (!page)
     272                 :          0 :                 return;
     273                 :            : 
     274         [ #  # ]:          0 :         for (i = 0; i < BLOCK_CACHE_NODES_PER_PAGE; i++)
     275                 :          0 :                 radix_tree_clear_link(page->owners[i]);
     276                 :            : 
     277                 :          0 :         radix_tree_free_page(tree, page);
     278                 :            : }
     279                 :            : 
     280                 :            : static void
     281                 :          0 : radix_tree_insert_leaf(radix_tree_t *tree, radix_tree_link_t *link,
     282                 :            :                        radix_tree_page_t *page, off_t off)
     283                 :            : {
     284                 :            :         int i;
     285                 :            : 
     286         [ #  # ]:          0 :         if (off + RADIX_TREE_NODE_SIZE > page->size)
     287                 :          0 :                 return;
     288                 :            : 
     289         [ #  # ]:          0 :         for (i = 0; i < BLOCK_CACHE_NODES_PER_PAGE; i++) {
     290         [ #  # ]:          0 :                 if (page->owners[i])
     291                 :          0 :                         continue;
     292                 :            : 
     293                 :          0 :                 page->owners[i]   = link;
     294                 :          0 :                 link->u.leaf.page = page;
     295                 :          0 :                 link->u.leaf.buf  = page->buf + off;
     296                 :            : 
     297                 :          0 :                 break;
     298                 :            :         }
     299                 :            : }
     300                 :            : 
     301                 :            : static char *
     302                 :          0 : radix_tree_find_leaf(radix_tree_t *tree, uint64_t sector)
     303                 :            : {
     304                 :            :         int idx;
     305                 :            :         struct timeval now;
     306                 :            :         radix_tree_link_t *link;
     307                 :          0 :         radix_tree_node_t *node;
     308                 :            : 
     309                 :          0 :         node = tree->root;
     310                 :          0 :         gettimeofday(&now, NULL);
     311                 :            : 
     312                 :            :         do {
     313                 :          0 :                 idx        = radix_tree_index(node, sector);
     314                 :          0 :                 link       = node->links + idx;
     315                 :          0 :                 link->time = now.tv_sec;
     316                 :            : 
     317         [ #  # ]:          0 :                 if (radix_tree_node_contains_leaves(tree, node))
     318                 :          0 :                         return link->u.leaf.buf;
     319                 :            : 
     320         [ #  # ]:          0 :                 if (!link->u.next)
     321                 :            :                         return NULL;
     322                 :            : 
     323                 :            :                 node = link->u.next;
     324                 :            :         } while (1);
     325                 :            : }
     326                 :            : 
     327                 :            : static char *
     328                 :          0 : radix_tree_add_leaf(radix_tree_t *tree, uint64_t sector,
     329                 :            :                     radix_tree_page_t *page, off_t off)
     330                 :            : {
     331                 :            :         int idx;
     332                 :            :         struct timeval now;
     333                 :            :         radix_tree_link_t *link;
     334                 :          0 :         radix_tree_node_t *node;
     335                 :            : 
     336                 :          0 :         node = tree->root;
     337                 :          0 :         gettimeofday(&now, NULL);
     338                 :            : 
     339                 :            :         do {
     340                 :          0 :                 idx        = radix_tree_index(node, sector);
     341                 :          0 :                 link       = node->links + idx;
     342                 :          0 :                 link->time = now.tv_sec;
     343                 :            : 
     344         [ #  # ]:          0 :                 if (radix_tree_node_contains_leaves(tree, node)) {
     345                 :          0 :                         radix_tree_remove_page(tree, link->u.leaf.page);
     346                 :          0 :                         radix_tree_insert_leaf(tree, link, page, off);
     347                 :          0 :                         return link->u.leaf.buf;
     348                 :            :                 }
     349                 :            : 
     350         [ #  # ]:          0 :                 if (!link->u.next) {
     351                 :          0 :                         link->u.next = radix_tree_allocate_child_node(tree,
     352                 :            :                                                                       node);
     353         [ #  # ]:          0 :                         if (!link->u.next)
     354                 :            :                                 return NULL;
     355                 :            :                 }
     356                 :            : 
     357                 :          0 :                 node = link->u.next;
     358                 :          0 :         } while (1);
     359                 :            : }
     360                 :            : 
     361                 :            : static int
     362                 :          0 : radix_tree_add_leaves(radix_tree_t *tree, char *buf,
     363                 :            :                       uint64_t sector, uint64_t sectors)
     364                 :            : {
     365                 :            :         int i;
     366                 :            :         radix_tree_page_t *page;
     367                 :            : 
     368                 :          0 :         page = radix_tree_allocate_page(tree, buf, sector,
     369                 :            :                                         sectors << RADIX_TREE_NODE_SHIFT);
     370         [ #  # ]:          0 :         if (!page)
     371                 :            :                 return -ENOMEM;
     372                 :            : 
     373         [ #  # ]:          0 :         for (i = 0; i < sectors; i++)
     374         [ #  # ]:          0 :                 if (!radix_tree_add_leaf(tree, sector + i, 
     375                 :          0 :                                          page, ((off_t)i << RADIX_TREE_NODE_SHIFT)))
     376                 :            :                         goto fail;
     377                 :            : 
     378                 :            :         return 0;
     379                 :            : 
     380                 :            : fail:
     381                 :          0 :         page->buf = NULL;
     382                 :          0 :         radix_tree_remove_page(tree, page);
     383                 :          0 :         return -ENOMEM;
     384                 :            : }
     385                 :            : 
     386                 :            : static void
     387                 :          0 : radix_tree_delete_branch(radix_tree_t *tree, radix_tree_node_t *node)
     388                 :            : {
     389                 :            :         int i;
     390                 :            :         radix_tree_link_t *link;
     391                 :            : 
     392         [ #  # ]:          0 :         if (!node)
     393                 :          0 :                 return;
     394                 :            : 
     395         [ #  # ]:          0 :         for (i = 0; i < RADIX_TREE_NODE_SIZE; i++) {
     396                 :          0 :                 link = node->links + i;
     397                 :            : 
     398         [ #  # ]:          0 :                 if (radix_tree_node_contains_leaves(tree, node))
     399                 :          0 :                         radix_tree_remove_page(tree, link->u.leaf.page);
     400                 :            :                 else
     401                 :          0 :                         radix_tree_delete_branch(tree, link->u.next);
     402                 :            : 
     403                 :            :                 radix_tree_clear_link(link);
     404                 :            :         }
     405                 :            : 
     406                 :          0 :         radix_tree_free_node(tree, node);
     407                 :            : }
     408                 :            : 
     409                 :            : static inline void
     410                 :            : radix_tree_destroy(radix_tree_t *tree)
     411                 :            : {
     412                 :          0 :         radix_tree_delete_branch(tree, tree->root);
     413                 :          0 :         tree->root = NULL;
     414                 :            : }
     415                 :            : 
     416                 :            : /*
     417                 :            :  * returns 1 if @node is empty after pruning, 0 otherwise
     418                 :            :  */
     419                 :            : static int
     420                 :          0 : radix_tree_prune_branch(radix_tree_t *tree,
     421                 :          0 :                         radix_tree_node_t *node, uint32_t now)
     422                 :            : {
     423                 :            :         int i, empty;
     424                 :            :         radix_tree_link_t *link;
     425                 :            : 
     426                 :          0 :         empty = 1;
     427         [ #  # ]:          0 :         if (!node)
     428                 :            :                 return empty;
     429                 :            : 
     430         [ #  # ]:          0 :         for (i = 0; i < RADIX_TREE_NODE_SIZE; i++) {
     431                 :          0 :                 link = node->links + i;
     432                 :            : 
     433         [ #  # ]:          0 :                 if (now - link->time < BLOCK_CACHE_PAGE_IDLETIME) {
     434         [ #  # ]:          0 :                         if (radix_tree_node_contains_leaves(tree, node)) {
     435                 :          0 :                                 empty = 0;
     436                 :          0 :                                 continue;
     437                 :            :                         }
     438                 :            : 
     439         [ #  # ]:          0 :                         if (radix_tree_prune_branch(tree, link->u.next, now))
     440                 :            :                                 radix_tree_clear_link(link);
     441                 :            :                         else
     442                 :            :                                 empty = 0;
     443                 :            : 
     444                 :          0 :                         continue;
     445                 :            :                 }
     446                 :            : 
     447         [ #  # ]:          0 :                 if (radix_tree_node_contains_leaves(tree, node))
     448                 :          0 :                         radix_tree_remove_page(tree, link->u.leaf.page);
     449                 :            :                 else
     450                 :          0 :                         radix_tree_delete_branch(tree, link->u.next);
     451                 :            : 
     452                 :            :                 radix_tree_clear_link(link);
     453                 :            :         }
     454                 :            : 
     455 [ #  # ][ #  # ]:          0 :         if (empty && !radix_tree_node_is_root(tree, node))
     456                 :          0 :                 radix_tree_free_node(tree, node);
     457                 :            : 
     458                 :          0 :         return empty;
     459                 :            : }
     460                 :            : 
     461                 :            : /*
     462                 :            :  * walk tree and free any node that has been idle for too long
     463                 :            :  */
     464                 :            : static void
     465                 :          0 : radix_tree_prune(radix_tree_t *tree)
     466                 :            : {
     467                 :            :         struct timeval now;
     468                 :            : 
     469         [ #  # ]:          0 :         if (!tree->root)
     470                 :          0 :                 return;
     471                 :            : 
     472                 :          0 :         DPRINTF("tree %s has %"PRIu64" bytes\n",
     473                 :            :                 tree->cache->name, tree->size);
     474                 :            : 
     475                 :          0 :         gettimeofday(&now, NULL);
     476                 :          0 :         radix_tree_prune_branch(tree, tree->root, now.tv_sec);
     477                 :            : 
     478                 :          0 :         DPRINTF("tree %s now has %"PRIu64" bytes\n",
     479                 :            :                 tree->cache->name, tree->size);
     480                 :            : }
     481                 :            : 
     482                 :            : static inline int
     483                 :          0 : radix_tree_initialize(radix_tree_t *tree, uint64_t sectors)
     484                 :            : {
     485                 :          0 :         tree->height = radix_tree_calculate_height(sectors);
     486                 :          0 :         tree->root   = radix_tree_allocate_node(tree, tree->height);
     487         [ #  # ]:          0 :         if (!tree->root)
     488                 :            :                 return -ENOMEM;
     489                 :            : 
     490                 :          0 :         return 0;
     491                 :            : }
     492                 :            : 
     493                 :            : static inline void
     494                 :            : radix_tree_free(radix_tree_t *tree)
     495                 :            : {
     496                 :            :         radix_tree_destroy(tree);
     497                 :            : }
     498                 :            : 
     499                 :            : static void
     500                 :          0 : block_cache_prune_event(event_id_t id, char mode, void *private)
     501                 :            : {
     502                 :            :         radix_tree_t *tree;
     503                 :            :         block_cache_t *cache;
     504                 :            : 
     505                 :          0 :         cache = (block_cache_t *)private;
     506                 :          0 :         tree  = &cache->tree;
     507                 :            : 
     508                 :          0 :         radix_tree_prune(tree);
     509                 :          0 : }
     510                 :            : 
     511                 :            : static inline block_cache_request_t *
     512                 :            : block_cache_get_request(block_cache_t *cache)
     513                 :            : {
     514         [ #  # ]:          0 :         if (!cache->requests_free)
     515                 :            :                 return NULL;
     516                 :            : 
     517                 :          0 :         return cache->request_free_list[--cache->requests_free];
     518                 :            : }
     519                 :            : 
     520                 :            : static inline void
     521                 :            : block_cache_put_request(block_cache_t *cache, block_cache_request_t *breq)
     522                 :            : {
     523                 :            :         memset(breq, 0, sizeof(block_cache_request_t));
     524                 :          0 :         cache->request_free_list[cache->requests_free++] = breq;
     525                 :            : }
     526                 :            : 
     527                 :            : static int
     528                 :          0 : block_cache_open(td_driver_t *driver, const char *name,
     529                 :            :                  struct td_vbd_encryption *encryption, td_flag_t flags)
     530                 :            : {
     531                 :            :         int i, err;
     532                 :            :         radix_tree_t *tree;
     533                 :            :         block_cache_t *cache;
     534                 :            : 
     535         [ #  # ]:          0 :         if (!td_flag_test(flags, TD_OPEN_RDONLY))
     536                 :            :                 return -EINVAL;
     537                 :            : 
     538         [ #  # ]:          0 :         if (driver->info.sector_size != RADIX_TREE_NODE_SIZE)
     539                 :            :                 return -EINVAL;
     540                 :            : 
     541                 :          0 :         cache = (block_cache_t *)driver->data;
     542                 :          0 :         err   = tapdisk_namedup(&cache->name, (char *)name);
     543         [ #  # ]:          0 :         if (err)
     544                 :            :                 return -ENOMEM;
     545                 :            : 
     546                 :          0 :         cache->sectors = driver->info.size;
     547                 :            : 
     548                 :          0 :         tree = &cache->tree;
     549                 :          0 :         err  = radix_tree_initialize(tree, cache->sectors);
     550         [ #  # ]:          0 :         if (err)
     551                 :            :                 goto fail;
     552                 :            : 
     553                 :          0 :         tree->cache = cache;
     554                 :          0 :         cache->requests_free = BLOCK_CACHE_REQUESTS;
     555         [ #  # ]:          0 :         for (i = 0; i < BLOCK_CACHE_REQUESTS; i++)
     556                 :          0 :                 cache->request_free_list[i] = cache->requests + i;
     557                 :            : 
     558                 :          0 :         cache->timeout_id = tapdisk_server_register_event(SCHEDULER_POLL_TIMEOUT,
     559                 :            :                                                           -1, /* dummy fd */
     560                 :          0 :                                                           TV_SECS(BLOCK_CACHE_PAGE_IDLETIME << 1),
     561                 :            :                                                           block_cache_prune_event,
     562                 :            :                                                           cache);
     563         [ #  # ]:          0 :         if (cache->timeout_id < 0)
     564                 :            :                 goto fail;
     565                 :            : 
     566                 :          0 :         DPRINTF("opening cache for %s, sectors: %"PRIu64", "
     567                 :            :                 "tree: %p, height: %d\n",
     568                 :            :                 cache->name, cache->sectors, tree, tree->height);
     569                 :            : 
     570         [ #  # ]:          0 :         if (mlockall(MCL_CURRENT | MCL_FUTURE))
     571                 :          0 :                 DPRINTF("mlockall failed: %d\n", -errno);
     572                 :            : 
     573                 :            :         return 0;
     574                 :            : 
     575                 :            : fail:
     576                 :          0 :         free(cache->name);
     577                 :          0 :         radix_tree_free(&cache->tree);
     578                 :          0 :         return err;
     579                 :            : }
     580                 :            : 
     581                 :            : static int
     582                 :          0 : block_cache_close(td_driver_t *driver)
     583                 :            : {
     584                 :            :         radix_tree_t *tree;
     585                 :            :         block_cache_t *cache;
     586                 :            : 
     587                 :          0 :         cache = (block_cache_t *)driver->data;
     588                 :          0 :         tree  = &cache->tree;
     589                 :            : 
     590                 :          0 :         DPRINTF("closing cache for %s\n", cache->name);
     591                 :            : 
     592                 :          0 :         tapdisk_server_unregister_event(cache->timeout_id);
     593                 :            :         radix_tree_free(tree);
     594                 :          0 :         free(cache->name);
     595                 :            : 
     596                 :          0 :         return 0;
     597                 :            : }
     598                 :            : 
     599                 :            : static inline uint64_t
     600                 :            : block_cache_hash(block_cache_t *cache, char *buf)
     601                 :            : {
     602                 :            :         return 0;
     603                 :            : #if 0
     604                 :            :         int i, n;
     605                 :            :         uint64_t cksm, *data;
     606                 :            : 
     607                 :            :         cksm = 0;
     608                 :            :         data = (uint64_t *)buf;
     609                 :            :         n    = RADIX_TREE_NODE_SIZE / sizeof(uint64_t);
     610                 :            : 
     611                 :            :         for (i = 0; i < n; i++)
     612                 :            :                 cksm += data[i];
     613                 :            : 
     614                 :            :         return ~cksm;
     615                 :            : #endif
     616                 :            : }
     617                 :            : 
     618                 :            : static void
     619                 :          0 : block_cache_hit(block_cache_t *cache, td_request_t treq, char *iov[])
     620                 :            : {
     621                 :            :         int i;
     622                 :            :         off_t off;
     623                 :            : 
     624                 :          0 :         cache->stats.hits += treq.secs;
     625                 :            : 
     626         [ #  # ]:          0 :         for (i = 0; i < treq.secs; i++) {
     627                 :            :                 DBG("%s: block cache hit: sec 0x%08llx, hash: 0x%08llx\n",
     628                 :            :                     cache->name, treq.sec + i, block_cache_hash(cache, iov[i]));
     629                 :            : 
     630                 :          0 :                 off = (off_t)i << RADIX_TREE_NODE_SHIFT;
     631                 :          0 :                 memcpy(treq.buf + off, iov[i], RADIX_TREE_NODE_SIZE);
     632                 :            :         }
     633                 :            : 
     634                 :          0 :         td_complete_request(treq, 0);
     635                 :          0 : }
     636                 :            : 
     637                 :            : static void
     638                 :          0 : block_cache_populate_cache(td_request_t clone, int err)
     639                 :            : {
     640                 :            :         int i;
     641                 :            :         radix_tree_t *tree;
     642                 :            :         block_cache_t *cache;
     643                 :            :         block_cache_request_t *breq;
     644                 :            : 
     645                 :          0 :         breq        = (block_cache_request_t *)clone.cb_data;
     646                 :          0 :         cache       = breq->cache;
     647                 :          0 :         tree        = &cache->tree;
     648                 :          0 :         breq->secs -= clone.secs;
     649         [ #  # ]:          0 :         breq->err   = (breq->err ? breq->err : err);
     650                 :            : 
     651         [ #  # ]:          0 :         if (breq->secs)
     652                 :          0 :                 return;
     653                 :            : 
     654         [ #  # ]:          0 :         if (breq->err) {
     655                 :          0 :                 free(breq->buf);
     656                 :          0 :                 goto out;
     657                 :            :         }
     658                 :            : 
     659         [ #  # ]:          0 :         for (i = 0; i < breq->treq.secs; i++) {
     660                 :          0 :                 off_t off = (off_t)i << RADIX_TREE_NODE_SHIFT;
     661                 :            :                 DBG("%s: populating sec 0x%08llx\n",
     662                 :            :                     cache->name, breq->treq.sec + i);
     663                 :          0 :                 memcpy(breq->treq.buf + off,
     664                 :          0 :                        breq->buf + off, RADIX_TREE_NODE_SIZE);
     665                 :            :         }
     666                 :            : 
     667         [ #  # ]:          0 :         if (radix_tree_add_leaves(tree, breq->buf,
     668                 :            :                                   breq->treq.sec, breq->treq.secs))
     669                 :          0 :                 free(breq->buf);
     670                 :            : 
     671                 :            : out:
     672                 :          0 :         td_complete_request(breq->treq, breq->err);
     673                 :            :         block_cache_put_request(cache, breq);
     674                 :            : }
     675                 :            : 
     676                 :            : static void
     677                 :          0 : block_cache_miss(block_cache_t *cache, td_request_t treq)
     678                 :            : {
     679                 :            :         void *buf;
     680                 :            :         size_t size;
     681                 :            :         td_request_t clone;
     682                 :          0 :         radix_tree_t *tree;
     683                 :            :         block_cache_request_t *breq;
     684                 :            : 
     685                 :            :         DBG("%s: block cache miss: sec 0x%08llx\n", cache->name, treq.sec);
     686                 :            : 
     687                 :          0 :         clone = treq;
     688                 :          0 :         tree  = &cache->tree;
     689                 :          0 :         size  = (size_t)treq.secs << RADIX_TREE_NODE_SHIFT;
     690                 :            : 
     691                 :          0 :         cache->stats.misses += treq.secs;
     692                 :            : 
     693         [ #  # ]:          0 :         if (radix_tree_size(tree) + size >= BLOCK_CACHE_MAX_SIZE)
     694                 :            :                 goto out;
     695                 :            : 
     696                 :          0 :         breq = block_cache_get_request(cache);
     697         [ #  # ]:          0 :         if (!breq)
     698                 :            :                 goto out;
     699                 :            : 
     700         [ #  # ]:          0 :         if (posix_memalign(&buf, RADIX_TREE_NODE_SIZE, size)) {
     701                 :            :                 block_cache_put_request(cache, breq);
     702                 :            :                 goto out;
     703                 :            :         }
     704                 :            : 
     705                 :          0 :         breq->treq    = treq;
     706                 :          0 :         breq->secs    = treq.secs;
     707                 :          0 :         breq->err     = 0;
     708                 :          0 :         breq->buf     = buf;
     709                 :          0 :         breq->cache   = cache;
     710                 :            : 
     711                 :          0 :         clone.buf     = buf;
     712                 :          0 :         clone.cb      = block_cache_populate_cache;
     713                 :          0 :         clone.cb_data = breq;
     714                 :            : 
     715                 :            : out:
     716                 :          0 :         td_forward_request(clone);
     717                 :          0 : }
     718                 :            : 
     719                 :            : static void
     720                 :          0 : block_cache_queue_read(td_driver_t *driver, td_request_t treq)
     721                 :            : {
     722                 :            :         int i;
     723                 :          0 :         radix_tree_t *tree;
     724                 :            :         block_cache_t *cache;
     725                 :            :         char *iov[BLOCK_CACHE_NODES_PER_PAGE];
     726                 :            : 
     727                 :          0 :         cache = (block_cache_t *)driver->data;
     728                 :          0 :         tree  = &cache->tree;
     729                 :            : 
     730                 :          0 :         cache->stats.reads += treq.secs;
     731                 :            : 
     732         [ #  # ]:          0 :         if (treq.secs > BLOCK_CACHE_NODES_PER_PAGE)
     733                 :          0 :                 return td_forward_request(treq);
     734                 :            : 
     735         [ #  # ]:          0 :         for (i = 0; i < treq.secs; i++) {
     736                 :          0 :                 iov[i] = radix_tree_find_leaf(tree, treq.sec + i);
     737         [ #  # ]:          0 :                 if (!iov[i])
     738                 :          0 :                         return block_cache_miss(cache, treq);
     739                 :            :         }
     740                 :            : 
     741                 :          0 :         return block_cache_hit(cache, treq, iov);
     742                 :            : }
     743                 :            : 
     744                 :            : static void
     745                 :          0 : block_cache_queue_write(td_driver_t *driver, td_request_t treq)
     746                 :            : {
     747                 :          0 :         td_complete_request(treq, -EPERM);
     748                 :          0 : }
     749                 :            : 
     750                 :            : static int
     751                 :          0 : block_cache_get_parent_id(td_driver_t *driver, td_disk_id_t *id)
     752                 :            : {
     753                 :          0 :         return -EINVAL;
     754                 :            : }
     755                 :            : 
     756                 :            : static int
     757                 :          0 : block_cache_validate_parent(td_driver_t *driver,
     758                 :            :                             td_driver_t *pdriver, td_flag_t flags)
     759                 :            : {
     760         [ #  # ]:          0 :         if (!td_flag_test(pdriver->state, TD_DRIVER_RDONLY))
     761                 :            :                 return -EINVAL;
     762                 :            : 
     763         [ #  # ]:          0 :         if (strcmp(driver->name, pdriver->name))
     764                 :            :                 return -EINVAL;
     765                 :            : 
     766                 :          0 :         return 0;
     767                 :            : }
     768                 :            : 
     769                 :            : static void
     770                 :          0 : block_cache_debug(td_driver_t *driver)
     771                 :            : {
     772                 :            :         block_cache_t *cache;
     773                 :            :         block_cache_stats_t *stats;
     774                 :            : 
     775                 :          0 :         cache = (block_cache_t *)driver->data;
     776                 :          0 :         stats = &cache->stats;
     777                 :            : 
     778                 :          0 :         WARN("BLOCK CACHE %s\n", cache->name);
     779                 :          0 :         WARN("reads: %"PRIu64", hits: %"PRIu64", "
     780                 :            :              "misses: %"PRIu64", prunes: %"PRIu64"\n",
     781                 :            :              stats->reads, stats->hits, stats->misses, stats->prunes);
     782                 :          0 : }
     783                 :            : 
     784                 :            : struct tap_disk tapdisk_block_cache = {
     785                 :            :         .disk_type                  = "tapdisk_block_cache",
     786                 :            :         .flags                      = 0,
     787                 :            :         .private_data_size          = sizeof(block_cache_t),
     788                 :            :         .td_open                    = block_cache_open,
     789                 :            :         .td_close                   = block_cache_close,
     790                 :            :         .td_queue_read              = block_cache_queue_read,
     791                 :            :         .td_queue_write             = block_cache_queue_write,
     792                 :            :         .td_get_parent_id           = block_cache_get_parent_id,
     793                 :            :         .td_validate_parent         = block_cache_validate_parent,
     794                 :            :         .td_debug                   = block_cache_debug,
     795                 :            : };

Generated by: LCOV version 1.13