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 #include "rbtree-utils.h"
  23
  24 struct cache_extent_search_range {
  25         u64 objectid;
  26         u64 start;
  27         u64 size;
  28 };
  29
  30 static int cache_tree_comp_range(struct rb_node *node, void *data)
  31 {
  32         struct cache_extent *entry;
  33         struct cache_extent_search_range *range;
  34
  35         range = (struct cache_extent_search_range *)data;
  36         entry = rb_entry(node, struct cache_extent, rb_node);
  37
  38         if (entry->start + entry->size <= range->start)
  39                 return 1;
  40         else if (range->start + range->size <= entry->start)
  41                 return -1;
  42         else
  43                 return 0;
  44 }
  45
  46 static int cache_tree_comp_nodes(struct rb_node *node1, struct rb_node *node2)
  47 {
  48         struct cache_extent *entry;
  49         struct cache_extent_search_range range;
  50
  51         entry = rb_entry(node2, struct cache_extent, rb_node);
  52         range.start = entry->start;
  53         range.size = entry->size;
  54
  55         return cache_tree_comp_range(node1, (void *)&range);
  56 }
  57
  58 static int cache_tree_comp_range2(struct rb_node *node, void *data)
  59 {
  60         struct cache_extent *entry;
  61         struct cache_extent_search_range *range;
  62
  63         range = (struct cache_extent_search_range *)data;
  64         entry = rb_entry(node, struct cache_extent, rb_node);
  65
  66         if (entry->objectid < range->objectid)
  67                 return 1;
  68         else if (entry->objectid > range->objectid)
  69                 return -1;
  70         else if (entry->start + entry->size <= range->start)
  71                 return 1;
  72         else if (range->start + range->size <= entry->start)
  73                 return -1;
  74         else
  75                 return 0;
  76 }
  77
  78 static int cache_tree_comp_nodes2(struct rb_node *node1, struct rb_node *node2)
  79 {
  80         struct cache_extent *entry;
  81         struct cache_extent_search_range range;
  82
  83         entry = rb_entry(node2, struct cache_extent, rb_node);
  84         range.objectid = entry->objectid;
  85         range.start = entry->start;
  86         range.size = entry->size;
  87
  88         return cache_tree_comp_range2(node1, (void *)&range);
  89 }
  90
  91 void cache_tree_init(struct cache_tree *tree)
  92 {
  93         tree->root = RB_ROOT;
  94 }
  95
  96 static struct cache_extent *alloc_cache_extent(u64 start, u64 size)
  97 {
  98         struct cache_extent *pe = malloc(sizeof(*pe));
  99
 100         if (!pe)
 101                 return pe;
 102
 103         pe->objectid = 0;
 104         pe->start = start;
 105         pe->size = size;
 106         return pe;
 107 }
 108
 109 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size)
 110 {
 111         struct cache_extent *pe = alloc_cache_extent(start, size);
 112         int ret;
 113
 114         if (!pe) {
 115                 fprintf(stderr, "memory allocation failed\n");
 116                 exit(1);
 117         }
 118
 119         ret = insert_cache_extent(tree, pe);
 120         if (ret)
 121                 free(pe);
 122
 123         return ret;
 124 }
 125
 126 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 127 {
 128         return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes);
 129 }
 130
 131 int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe)
 132 {
 133         return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes2);
 134 }
 135
 136 struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
 137                                          u64 start, u64 size)
 138 {
 139         struct rb_node *node;
 140         struct cache_extent *entry;
 141         struct cache_extent_search_range range;
 142
 143         range.start = start;
 144         range.size = size;
 145         node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL);
 146         if (!node)
 147                 return NULL;
 148
 149         entry = rb_entry(node, struct cache_extent, rb_node);
 150         return entry;
 151 }
 152
 153 struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
 154                                          u64 objectid, u64 start, u64 size)
 155 {
 156         struct rb_node *node;
 157         struct cache_extent *entry;
 158         struct cache_extent_search_range range;
 159
 160         range.objectid = objectid;
 161         range.start = start;
 162         range.size = size;
 163         node = rb_search(&tree->root, &range, cache_tree_comp_range2, NULL);
 164         if (!node)
 165                 return NULL;
 166
 167         entry = rb_entry(node, struct cache_extent, rb_node);
 168         return entry;
 169 }
 170
 171 struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start)
 172 {
 173         struct rb_node *next;
 174         struct rb_node *node;
 175         struct cache_extent *entry;
 176         struct cache_extent_search_range range;
 177
 178         range.start = start;
 179         range.size = 1;
 180         node = rb_search(&tree->root, &range, cache_tree_comp_range, &next);
 181         if (!node)
 182                 node = next;
 183         if (!node)
 184                 return NULL;
 185
 186         entry = rb_entry(node, struct cache_extent, rb_node);
 187         return entry;
 188 }
 189
 190 struct cache_extent *search_cache_extent2(struct cache_tree *tree,
 191                                          u64 objectid, u64 start)
 192 {
 193         struct rb_node *next;
 194         struct rb_node *node;
 195         struct cache_extent *entry;
 196         struct cache_extent_search_range range;
 197
 198         range.objectid = objectid;
 199         range.start = start;
 200         range.size = 1;
 201         node = rb_search(&tree->root, &range, cache_tree_comp_range2, &next);
 202         if (!node)
 203                 node = next;
 204         if (!node)
 205                 return NULL;
 206
 207         entry = rb_entry(node, struct cache_extent, rb_node);
 208         return entry;
 209 }
 210
 211 struct cache_extent *first_cache_extent(struct cache_tree *tree)
 212 {
 213         struct rb_node *node = rb_first(&tree->root);
 214
 215         if (!node)
 216                 return NULL;
 217         return rb_entry(node, struct cache_extent, rb_node);
 218 }
 219
 220 struct cache_extent *last_cache_extent(struct cache_tree *tree)
 221 {
 222         struct rb_node *node = rb_last(&tree->root);
 223
 224         if (!node)
 225                 return NULL;
 226         return rb_entry(node, struct cache_extent, rb_node);
 227 }
 228
 229 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 230 {
 231         struct rb_node *node = rb_prev(&pe->rb_node);
 232
 233         if (!node)
 234                 return NULL;
 235         return rb_entry(node, struct cache_extent, rb_node);
 236 }
 237
 238 struct cache_extent *next_cache_extent(struct cache_extent *pe)
 239 {
 240         struct rb_node *node = rb_next(&pe->rb_node);
 241
 242         if (!node)
 243                 return NULL;
 244         return rb_entry(node, struct cache_extent, rb_node);
 245 }
 246
 247 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 248 {
 249         rb_erase(&pe->rb_node, &tree->root);
 250 }
 251
 252 void cache_tree_free_extents(struct cache_tree *tree,
 253                              free_cache_extent free_func)
 254 {
 255         struct cache_extent *ce;
 256
 257         while ((ce = first_cache_extent(tree))) {
 258                 remove_cache_extent(tree, ce);
 259                 free_func(ce);
 260         }
 261 }
 262
 263 static void free_extent_cache(struct cache_extent *pe)
 264 {
 265         free(pe);
 266 }
 267
 268 void free_extent_cache_tree(struct cache_tree *tree)
 269 {
 270         cache_tree_free_extents(tree, free_extent_cache);
 271 }
 272
 273 int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size)
 274 {
 275         struct cache_extent *cache;
 276         struct cache_extent *next = NULL;
 277         struct cache_extent *prev = NULL;
 278         int next_merged = 0;
 279         int prev_merged = 0;
 280         int ret = 0;
 281
 282         if (cache_tree_empty(tree))
 283                 goto insert;
 284
 285         cache = search_cache_extent(tree, start);
 286         if (!cache) {
 287                 /*
 288                  * Either the tree is completely empty, or the no range after
 289                  * start.
 290                  * Either way, the last cache_extent should be prev.
 291                  */
 292                 prev = last_cache_extent(tree);
 293         } else if (start <= cache->start) {
 294                 next = cache;
 295                 prev = prev_cache_extent(cache);
 296         } else {
 297                 prev = cache;
 298                 next = next_cache_extent(cache);
 299         }
 300
 301         /*
 302          * Ensure the range to be inserted won't cover with existings
 303          * Or we will need extra loop to do merge
 304          */
 305         BUG_ON(next && start + size > next->start);
 306         BUG_ON(prev && prev->start + prev->size > start);
 307
 308         if (next && start + size == next->start) {
 309                 next_merged = 1;
 310                 next->size = next->start + next->size - start;
 311                 next->start = start;
 312         }
 313         if (prev && prev->start + prev->size == start) {
 314                 prev_merged = 1;
 315                 if (next_merged) {
 316                         next->size = next->start + next->size - prev->start;
 317                         next->start = prev->start;
 318                         remove_cache_extent(tree, prev);
 319                         free(prev);
 320                 } else {
 321                         prev->size = start + size - prev->start;
 322                 }
 323         }
 324 insert:
 325         if (!prev_merged && !next_merged)
 326                 ret = add_cache_extent(tree, start, size);
 327         return ret;
 328 }