extent-cache.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include "kerncompat.h"
  21 #include "extent-cache.h"
  22
  23 struct cache_extent_search_range {
  24         u64 objectid;
  25         u64 start;
  26         u64 size;
  27 };
  28
  29 static int cache_tree_comp_range(struct rb_node *node, void *data)
  30 {
  31         struct cache_extent *entry;
  32         struct cache_extent_search_range *range;
  33
  34         range = (struct cache_extent_search_range *)data;
  35         entry = rb_entry(node, struct cache_extent, rb_node);
  36
  37         if (entry->start + entry->size <= range->start)
  38                 return 1;
  39         else if (range->start + range->size <= entry->start)
  40                 return -1;
  41         else
  42                 return 0;
  43 }
  44
  45 static int cache_tree_comp_nodes(struct rb_node *node1, struct rb_node *node2)
  46 {
  47         struct cache_extent *entry;
  48         struct cache_extent_search_range range;
  49
  50         entry = rb_entry(node2, struct cache_extent, rb_node);
  51         range.start = entry->start;
  52         range.size = entry->size;
  53
  54         return cache_tree_comp_range(node1, (void *)&range);
  55 }
  56
  57 static int cache_tree_comp_range2(struct rb_node *node, void *data)
  58 {
  59         struct cache_extent *entry;
  60         struct cache_extent_search_range *range;
  61
  62         range = (struct cache_extent_search_range *)data;
  63         entry = rb_entry(node, struct cache_extent, rb_node);
  64
  65         if (entry->objectid < range->objectid)
  66                 return 1;
  67         else if (entry->objectid > range->objectid)
  68                 return -1;
  69         else if (entry->start + entry->size <= range->start)
  70                 return 1;
  71         else if (range->start + range->size <= entry->start)
  72                 return -1;
  73         else
  74                 return 0;
  75 }
  76
  77 static int cache_tree_comp_nodes2(struct rb_node *node1, struct rb_node *node2)
  78 {
  79         struct cache_extent *entry;
  80         struct cache_extent_search_range range;
  81
  82         entry = rb_entry(node2, struct cache_extent, rb_node);
  83         range.objectid = entry->objectid;
  84         range.start = entry->start;
  85         range.size = entry->size;
  86
  87         return cache_tree_comp_range2(node1, (void *)&range);
  88 }
  89
  90 void cache_tree_init(struct cache_tree *tree)
  91 {
  92         tree->root = RB_ROOT;
  93 }
  94
  95 static struct cache_extent *
  96 alloc_cache_extent(u64 objectid, u64 start, u64 size)
  97 {
  98         struct cache_extent *pe = malloc(sizeof(*pe));
  99
 100         if (!pe)
 101                 return pe;
 102
 103         pe->objectid = objectid;
 104         pe->start = start;
 105         pe->size = size;
 106         return pe;
 107 }
 108
 109 static int __add_cache_extent(struct cache_tree *tree,
 110                               u64 objectid, u64 start, u64 size)
 111 {
 112         struct cache_extent *pe = alloc_cache_extent(objectid, start, size);
 113         int ret;
 114
 115         if (!pe) {
 116                 fprintf(stderr, "memory allocation failed\n");
 117                 exit(1);
 118         }
 119
 120         ret = insert_cache_extent(tree, pe);
 121         if (ret)
 122                 free(pe);
 123
 124         return ret;
 125 }
 126
 127 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size)
 128 {
 129         return __add_cache_extent(tree, 0, start, size);
 130 }
 131
 132 int add_cache_extent2(struct cache_tree *tree,
 133                       u64 objectid, u64 start, u64 size)
 134 {
 135         return __add_cache_extent(tree, objectid, start, size);
 136 }
 137
 138 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 139 {
 140         return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes);
 141 }
 142
 143 int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe)
 144 {
 145         return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes2);
 146 }
 147
 148 struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
 149                                          u64 start, u64 size)
 150 {
 151         struct rb_node *node;
 152         struct cache_extent *entry;
 153         struct cache_extent_search_range range;
 154
 155         range.start = start;
 156         range.size = size;
 157         node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL);
 158         if (!node)
 159                 return NULL;
 160
 161         entry = rb_entry(node, struct cache_extent, rb_node);
 162         return entry;
 163 }
 164
 165 struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
 166                                          u64 objectid, u64 start, u64 size)
 167 {
 168         struct rb_node *node;
 169         struct cache_extent *entry;
 170         struct cache_extent_search_range range;
 171
 172         range.objectid = objectid;
 173         range.start = start;
 174         range.size = size;
 175         node = rb_search(&tree->root, &range, cache_tree_comp_range2, NULL);
 176         if (!node)
 177                 return NULL;
 178
 179         entry = rb_entry(node, struct cache_extent, rb_node);
 180         return entry;
 181 }
 182
 183 struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start)
 184 {
 185         struct rb_node *next;
 186         struct rb_node *node;
 187         struct cache_extent *entry;
 188         struct cache_extent_search_range range;
 189
 190         range.start = start;
 191         range.size = 1;
 192         node = rb_search(&tree->root, &range, cache_tree_comp_range, &next);
 193         if (!node)
 194                 node = next;
 195         if (!node)
 196                 return NULL;
 197
 198         entry = rb_entry(node, struct cache_extent, rb_node);
 199         return entry;
 200 }
 201
 202 struct cache_extent *search_cache_extent2(struct cache_tree *tree,
 203                                          u64 objectid, u64 start)
 204 {
 205         struct rb_node *next;
 206         struct rb_node *node;
 207         struct cache_extent *entry;
 208         struct cache_extent_search_range range;
 209
 210         range.objectid = objectid;
 211         range.start = start;
 212         range.size = 1;
 213         node = rb_search(&tree->root, &range, cache_tree_comp_range2, &next);
 214         if (!node)
 215                 node = next;
 216         if (!node)
 217                 return NULL;
 218
 219         entry = rb_entry(node, struct cache_extent, rb_node);
 220         return entry;
 221 }
 222
 223 struct cache_extent *first_cache_extent(struct cache_tree *tree)
 224 {
 225         struct rb_node *node = rb_first(&tree->root);
 226
 227         if (!node)
 228                 return NULL;
 229         return rb_entry(node, struct cache_extent, rb_node);
 230 }
 231
 232 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 233 {
 234         struct rb_node *node = rb_prev(&pe->rb_node);
 235
 236         if (!node)
 237                 return NULL;
 238         return rb_entry(node, struct cache_extent, rb_node);
 239 }
 240
 241 struct cache_extent *next_cache_extent(struct cache_extent *pe)
 242 {
 243         struct rb_node *node = rb_next(&pe->rb_node);
 244
 245         if (!node)
 246                 return NULL;
 247         return rb_entry(node, struct cache_extent, rb_node);
 248 }
 249
 250 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 251 {
 252         rb_erase(&pe->rb_node, &tree->root);
 253 }
 254
 255 void cache_tree_free_extents(struct cache_tree *tree,
 256                              free_cache_extent free_func)
 257 {
 258         struct cache_extent *ce;
 259
 260         while ((ce = first_cache_extent(tree))) {
 261                 remove_cache_extent(tree, ce);
 262                 free_func(ce);
 263         }
 264 }
 265
 266 static void free_extent_cache(struct cache_extent *pe)
 267 {
 268         free(pe);
 269 }
 270
 271 void free_extent_cache_tree(struct cache_tree *tree)
 272 {
 273         cache_tree_free_extents(tree, free_extent_cache);
 274 }