extent_io.c

   1
   2 /*
   3  * Copyright (C) 2007 Oracle.  All rights reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public
   7  * License v2 as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public
  15  * License along with this program; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 021110-1307, USA.
  18  */
  19 #define _XOPEN_SOURCE 600
  20 #define __USE_XOPEN2K
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <sys/types.h>
  24 #include <sys/stat.h>
  25 #include <fcntl.h>
  26 #include <unistd.h>
  27 #include "kerncompat.h"
  28 #include "extent_io.h"
  29 #include "list.h"
  30
  31 u64 cache_max = 1024 * 1024 * 32;
  32
  33 void extent_io_tree_init(struct extent_io_tree *tree)
  34 {
  35         cache_tree_init(&tree->state);
  36         cache_tree_init(&tree->cache);
  37         INIT_LIST_HEAD(&tree->lru);
  38         tree->cache_size = 0;
  39 }
  40
  41 static struct extent_state *alloc_extent_state(void)
  42 {
  43         struct extent_state *state;
  44
  45         state = malloc(sizeof(*state));
  46         if (!state)
  47                 return NULL;
  48         state->refs = 1;
  49         state->state = 0;
  50         state->private = 0;
  51         return state;
  52 }
  53
  54 static void free_extent_state(struct extent_state *state)
  55 {
  56         state->refs--;
  57         BUG_ON(state->refs < 0);
  58         if (state->refs == 0)
  59                 free(state);
  60 }
  61
  62 void extent_io_tree_cleanup(struct extent_io_tree *tree)
  63 {
  64         struct extent_state *es;
  65         struct extent_buffer *eb;
  66         struct cache_extent *cache;
  67
  68         while(!list_empty(&tree->lru)) {
  69                 eb = list_entry(tree->lru.next, struct extent_buffer, lru);
  70                 if (eb->refs != 1) {
  71                         fprintf(stderr, "extent buffer leak: "
  72                                 "start %llu len %u\n",
  73                                 (unsigned long long)eb->start, eb->len);
  74                         eb->refs = 1;
  75                 }
  76                 free_extent_buffer(eb);
  77         }
  78         while (1) {
  79                 cache = find_first_cache_extent(&tree->state, 0);
  80                 if (!cache)
  81                         break;
  82                 es = container_of(cache, struct extent_state, cache_node);
  83                 remove_cache_extent(&tree->state, &es->cache_node);
  84                 free_extent_state(es);
  85         }
  86 }
  87
  88 static inline void update_extent_state(struct extent_state *state)
  89 {
  90         state->cache_node.start = state->start;
  91         state->cache_node.size = state->end + 1 - state->start;
  92 }
  93
  94 /*
  95  * Utility function to look for merge candidates inside a given range.
  96  * Any extents with matching state are merged together into a single
  97  * extent in the tree. Extents with EXTENT_IO in their state field are
  98  * not merged
  99  */
 100 static int merge_state(struct extent_io_tree *tree,
 101                        struct extent_state *state)
 102 {
 103         struct extent_state *other;
 104         struct cache_extent *other_node;
 105
 106         if (state->state & EXTENT_IOBITS)
 107                 return 0;
 108
 109         other_node = prev_cache_extent(&state->cache_node);
 110         if (other_node) {
 111                 other = container_of(other_node, struct extent_state,
 112                                      cache_node);
 113                 if (other->end == state->start - 1 &&
 114                     other->state == state->state) {
 115                         state->start = other->start;
 116                         update_extent_state(state);
 117                         remove_cache_extent(&tree->state, &other->cache_node);
 118                         free_extent_state(other);
 119                 }
 120         }
 121         other_node = next_cache_extent(&state->cache_node);
 122         if (other_node) {
 123                 other = container_of(other_node, struct extent_state,
 124                                      cache_node);
 125                 if (other->start == state->end + 1 &&
 126                     other->state == state->state) {
 127                         other->start = state->start;
 128                         update_extent_state(other);
 129                         remove_cache_extent(&tree->state, &state->cache_node);
 130                         free_extent_state(state);
 131                 }
 132         }
 133         return 0;
 134 }
 135
 136 /*
 137  * insert an extent_state struct into the tree.  'bits' are set on the
 138  * struct before it is inserted.
 139  */
 140 static int insert_state(struct extent_io_tree *tree,
 141                         struct extent_state *state, u64 start, u64 end,
 142                         int bits)
 143 {
 144         int ret;
 145
 146         BUG_ON(end < start);
 147         state->state |= bits;
 148         state->start = start;
 149         state->end = end;
 150         update_extent_state(state);
 151         ret = insert_existing_cache_extent(&tree->state, &state->cache_node);
 152         BUG_ON(ret);
 153         merge_state(tree, state);
 154         return 0;
 155 }
 156
 157 /*
 158  * split a given extent state struct in two, inserting the preallocated
 159  * struct 'prealloc' as the newly created second half.  'split' indicates an
 160  * offset inside 'orig' where it should be split.
 161  */
 162 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 163                        struct extent_state *prealloc, u64 split)
 164 {
 165         int ret;
 166         prealloc->start = orig->start;
 167         prealloc->end = split - 1;
 168         prealloc->state = orig->state;
 169         update_extent_state(prealloc);
 170         orig->start = split;
 171         update_extent_state(orig);
 172         ret = insert_existing_cache_extent(&tree->state,
 173                                            &prealloc->cache_node);
 174         BUG_ON(ret);
 175         return 0;
 176 }
 177
 178 /*
 179  * clear some bits on a range in the tree.
 180  */
 181 static int clear_state_bit(struct extent_io_tree *tree,
 182                             struct extent_state *state, int bits)
 183 {
 184         int ret = state->state & bits;
 185
 186         state->state &= ~bits;
 187         if (state->state == 0) {
 188                 remove_cache_extent(&tree->state, &state->cache_node);
 189                 free_extent_state(state);
 190         } else {
 191                 merge_state(tree, state);
 192         }
 193         return ret;
 194 }
 195
 196 /*
 197  * set some bits on a range in the tree.
 198  */
 199 int clear_extent_bits(struct extent_io_tree *tree, u64 start,
 200                       u64 end, int bits, gfp_t mask)
 201 {
 202         struct extent_state *state;
 203         struct extent_state *prealloc = NULL;
 204         struct cache_extent *node;
 205         int err;
 206         int set = 0;
 207
 208 again:
 209         prealloc = alloc_extent_state();
 210         if (!prealloc)
 211                 return -ENOMEM;
 212
 213         /*
 214          * this search will find the extents that end after
 215          * our range starts
 216          */
 217         node = find_first_cache_extent(&tree->state, start);
 218         if (!node)
 219                 goto out;
 220         state = container_of(node, struct extent_state, cache_node);
 221         if (state->start > end)
 222                 goto out;
 223
 224         /*
 225          *     | ---- desired range ---- |
 226          *  | state | or
 227          *  | ------------- state -------------- |
 228          *
 229          * We need to split the extent we found, and may flip
 230          * bits on second half.
 231          *
 232          * If the extent we found extends past our range, we
 233          * just split and search again.  It'll get split again
 234          * the next time though.
 235          *
 236          * If the extent we found is inside our range, we clear
 237          * the desired bit on it.
 238          */
 239         if (state->start < start) {
 240                 err = split_state(tree, state, prealloc, start);
 241                 BUG_ON(err == -EEXIST);
 242                 prealloc = NULL;
 243                 if (err)
 244                         goto out;
 245                 if (state->end <= end) {
 246                         start = state->end + 1;
 247                         set |= clear_state_bit(tree, state, bits);
 248                 } else {
 249                         start = state->start;
 250                 }
 251                 goto search_again;
 252         }
 253         /*
 254          * | ---- desired range ---- |
 255          *                        | state |
 256          * We need to split the extent, and clear the bit
 257          * on the first half
 258          */
 259         if (state->start <= end && state->end > end) {
 260                 err = split_state(tree, state, prealloc, end + 1);
 261                 BUG_ON(err == -EEXIST);
 262
 263                 set |= clear_state_bit(tree, prealloc, bits);
 264                 prealloc = NULL;
 265                 goto out;
 266         }
 267
 268         start = state->end + 1;
 269         set |= clear_state_bit(tree, state, bits);
 270         goto search_again;
 271 out:
 272         if (prealloc)
 273                 free_extent_state(prealloc);
 274         return set;
 275
 276 search_again:
 277         if (start > end)
 278                 goto out;
 279         goto again;
 280 }
 281
 282 /*
 283  * set some bits on a range in the tree.
 284  */
 285 int set_extent_bits(struct extent_io_tree *tree, u64 start,
 286                     u64 end, int bits, gfp_t mask)
 287 {
 288         struct extent_state *state;
 289         struct extent_state *prealloc = NULL;
 290         struct cache_extent *node;
 291         int err = 0;
 292         int set;
 293         u64 last_start;
 294         u64 last_end;
 295 again:
 296         prealloc = alloc_extent_state();
 297         if (!prealloc)
 298                 return -ENOMEM;
 299
 300         /*
 301          * this search will find the extents that end after
 302          * our range starts
 303          */
 304         node = find_first_cache_extent(&tree->state, start);
 305         if (!node) {
 306                 err = insert_state(tree, prealloc, start, end, bits);
 307                 BUG_ON(err == -EEXIST);
 308                 prealloc = NULL;
 309                 goto out;
 310         }
 311
 312         state = container_of(node, struct extent_state, cache_node);
 313         last_start = state->start;
 314         last_end = state->end;
 315
 316         /*
 317          * | ---- desired range ---- |
 318          * | state |
 319          *
 320          * Just lock what we found and keep going
 321          */
 322         if (state->start == start && state->end <= end) {
 323                 set = state->state & bits;
 324                 state->state |= bits;
 325                 start = state->end + 1;
 326                 merge_state(tree, state);
 327                 goto search_again;
 328         }
 329         /*
 330          *     | ---- desired range ---- |
 331          * | state |
 332          *   or
 333          * | ------------- state -------------- |
 334          *
 335          * We need to split the extent we found, and may flip bits on
 336          * second half.
 337          *
 338          * If the extent we found extends past our
 339          * range, we just split and search again.  It'll get split
 340          * again the next time though.
 341          *
 342          * If the extent we found is inside our range, we set the
 343          * desired bit on it.
 344          */
 345         if (state->start < start) {
 346                 set = state->state & bits;
 347                 err = split_state(tree, state, prealloc, start);
 348                 BUG_ON(err == -EEXIST);
 349                 prealloc = NULL;
 350                 if (err)
 351                         goto out;
 352                 if (state->end <= end) {
 353                         state->state |= bits;
 354                         start = state->end + 1;
 355                         merge_state(tree, state);
 356                 } else {
 357                         start = state->start;
 358                 }
 359                 goto search_again;
 360         }
 361         /*
 362          * | ---- desired range ---- |
 363          *     | state | or               | state |
 364          *
 365          * There's a hole, we need to insert something in it and
 366          * ignore the extent we found.
 367          */
 368         if (state->start > start) {
 369                 u64 this_end;
 370                 if (end < last_start)
 371                         this_end = end;
 372                 else
 373                         this_end = last_start -1;
 374                 err = insert_state(tree, prealloc, start, this_end,
 375                                 bits);
 376                 BUG_ON(err == -EEXIST);
 377                 prealloc = NULL;
 378                 if (err)
 379                         goto out;
 380                 start = this_end + 1;
 381                 goto search_again;
 382         }
 383         /*
 384          * | ---- desired range ---- |
 385          * | ---------- state ---------- |
 386          * We need to split the extent, and set the bit
 387          * on the first half
 388          */
 389         set = state->state & bits;
 390         err = split_state(tree, state, prealloc, end + 1);
 391         BUG_ON(err == -EEXIST);
 392
 393         state->state |= bits;
 394         merge_state(tree, prealloc);
 395         prealloc = NULL;
 396 out:
 397         if (prealloc)
 398                 free_extent_state(prealloc);
 399         return err;
 400 search_again:
 401         if (start > end)
 402                 goto out;
 403         goto again;
 404 }
 405
 406 int set_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
 407                      gfp_t mask)
 408 {
 409         return set_extent_bits(tree, start, end, EXTENT_DIRTY, mask);
 410 }
 411
 412 int clear_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
 413                        gfp_t mask)
 414 {
 415         return clear_extent_bits(tree, start, end, EXTENT_DIRTY, mask);
 416 }
 417
 418 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
 419                           u64 *start_ret, u64 *end_ret, int bits)
 420 {
 421         struct cache_extent *node;
 422         struct extent_state *state;
 423         int ret = 1;
 424
 425         /*
 426          * this search will find all the extents that end after
 427          * our range starts.
 428          */
 429         node = find_first_cache_extent(&tree->state, start);
 430         if (!node)
 431                 goto out;
 432
 433         while(1) {
 434                 state = container_of(node, struct extent_state, cache_node);
 435                 if (state->end >= start && (state->state & bits)) {
 436                         *start_ret = state->start;
 437                         *end_ret = state->end;
 438                         ret = 0;
 439                         break;
 440                 }
 441                 node = next_cache_extent(node);
 442                 if (!node)
 443                         break;
 444         }
 445 out:
 446         return ret;
 447 }
 448
 449 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
 450                    int bits, int filled)
 451 {
 452         struct extent_state *state = NULL;
 453         struct cache_extent *node;
 454         int bitset = 0;
 455
 456         node = find_first_cache_extent(&tree->state, start);
 457         while (node && start <= end) {
 458                 state = container_of(node, struct extent_state, cache_node);
 459
 460                 if (filled && state->start > start) {
 461                         bitset = 0;
 462                         break;
 463                 }
 464                 if (state->start > end)
 465                         break;
 466                 if (state->state & bits) {
 467                         bitset = 1;
 468                         if (!filled)
 469                                 break;
 470                 } else if (filled) {
 471                         bitset = 0;
 472                         break;
 473                 }
 474                 start = state->end + 1;
 475                 if (start > end)
 476                         break;
 477                 node = next_cache_extent(node);
 478                 if (!node) {
 479                         if (filled)
 480                                 bitset = 0;
 481                         break;
 482                 }
 483         }
 484         return bitset;
 485 }
 486
 487 int set_state_private(struct extent_io_tree *tree, u64 start, u64 private)
 488 {
 489         struct cache_extent *node;
 490         struct extent_state *state;
 491         int ret = 0;
 492
 493         node = find_first_cache_extent(&tree->state, start);
 494         if (!node) {
 495                 ret = -ENOENT;
 496                 goto out;
 497         }
 498         state = container_of(node, struct extent_state, cache_node);
 499         if (state->start != start) {
 500                 ret = -ENOENT;
 501                 goto out;
 502         }
 503         state->private = private;
 504 out:
 505         return ret;
 506 }
 507
 508 int get_state_private(struct extent_io_tree *tree, u64 start, u64 *private)
 509 {
 510         struct cache_extent *node;
 511         struct extent_state *state;
 512         int ret = 0;
 513
 514         node = find_first_cache_extent(&tree->state, start);
 515         if (!node) {
 516                 ret = -ENOENT;
 517                 goto out;
 518         }
 519         state = container_of(node, struct extent_state, cache_node);
 520         if (state->start != start) {
 521                 ret = -ENOENT;
 522                 goto out;
 523         }
 524         *private = state->private;
 525 out:
 526         return ret;
 527 }
 528
 529 static int free_some_buffers(struct extent_io_tree *tree)
 530 {
 531         u32 nrscan = 0;
 532         struct extent_buffer *eb;
 533         struct list_head *node, *next;
 534
 535         if (tree->cache_size < cache_max)
 536                 return 0;
 537         list_for_each_safe(node, next, &tree->lru) {
 538                 eb = list_entry(node, struct extent_buffer, lru);
 539                 if (eb->refs == 1) {
 540                         free_extent_buffer(eb);
 541                         if (tree->cache_size < cache_max)
 542                                 break;
 543                 } else {
 544                         list_move_tail(&eb->lru, &tree->lru);
 545                 }
 546                 if (nrscan++ > 64)
 547                         break;
 548         }
 549         return 0;
 550 }
 551
 552 static struct extent_buffer *__alloc_extent_buffer(struct extent_io_tree *tree,
 553                                                    u64 bytenr, u32 blocksize)
 554 {
 555         struct extent_buffer *eb;
 556         int ret;
 557
 558         eb = malloc(sizeof(struct extent_buffer) + blocksize);
 559         if (!eb) {
 560                 BUG();
 561                 return NULL;
 562         }
 563
 564         eb->start = bytenr;
 565         eb->len = blocksize;
 566         eb->refs = 2;
 567         eb->flags = 0;
 568         eb->tree = tree;
 569         eb->fd = -1;
 570         eb->dev_bytenr = (u64)-1;
 571         eb->cache_node.start = bytenr;
 572         eb->cache_node.size = blocksize;
 573
 574         free_some_buffers(tree);
 575         ret = insert_existing_cache_extent(&tree->cache, &eb->cache_node);
 576         if (ret) {
 577                 free(eb);
 578                 return NULL;
 579         }
 580         list_add_tail(&eb->lru, &tree->lru);
 581         tree->cache_size += blocksize;
 582         return eb;
 583 }
 584
 585 void free_extent_buffer(struct extent_buffer *eb)
 586 {
 587         if (!eb)
 588                 return;
 589
 590         eb->refs--;
 591         BUG_ON(eb->refs < 0);
 592         if (eb->refs == 0) {
 593                 struct extent_io_tree *tree = eb->tree;
 594                 BUG_ON(eb->flags & EXTENT_DIRTY);
 595                 list_del_init(&eb->lru);
 596                 remove_cache_extent(&tree->cache, &eb->cache_node);
 597                 BUG_ON(tree->cache_size < eb->len);
 598                 tree->cache_size -= eb->len;
 599                 free(eb);
 600         }
 601 }
 602
 603 struct extent_buffer *find_extent_buffer(struct extent_io_tree *tree,
 604                                          u64 bytenr, u32 blocksize)
 605 {
 606         struct extent_buffer *eb = NULL;
 607         struct cache_extent *cache;
 608
 609         cache = find_cache_extent(&tree->cache, bytenr, blocksize);
 610         if (cache && cache->start == bytenr && cache->size == blocksize) {
 611                 eb = container_of(cache, struct extent_buffer, cache_node);
 612                 list_move_tail(&eb->lru, &tree->lru);
 613                 eb->refs++;
 614         }
 615         return eb;
 616 }
 617
 618 struct extent_buffer *find_first_extent_buffer(struct extent_io_tree *tree,
 619                                                u64 start)
 620 {
 621         struct extent_buffer *eb = NULL;
 622         struct cache_extent *cache;
 623
 624         cache = find_first_cache_extent(&tree->cache, start);
 625         if (cache) {
 626                 eb = container_of(cache, struct extent_buffer, cache_node);
 627                 list_move_tail(&eb->lru, &tree->lru);
 628                 eb->refs++;
 629         }
 630         return eb;
 631 }
 632
 633 struct extent_buffer *alloc_extent_buffer(struct extent_io_tree *tree,
 634                                           u64 bytenr, u32 blocksize)
 635 {
 636         struct extent_buffer *eb;
 637         struct cache_extent *cache;
 638
 639         cache = find_cache_extent(&tree->cache, bytenr, blocksize);
 640         if (cache && cache->start == bytenr && cache->size == blocksize) {
 641                 eb = container_of(cache, struct extent_buffer, cache_node);
 642                 list_move_tail(&eb->lru, &tree->lru);
 643                 eb->refs++;
 644         } else {
 645                 if (cache) {
 646                         eb = container_of(cache, struct extent_buffer,
 647                                           cache_node);
 648                         BUG_ON(eb->refs != 1);
 649                         free_extent_buffer(eb);
 650                 }
 651                 eb = __alloc_extent_buffer(tree, bytenr, blocksize);
 652         }
 653         return eb;
 654 }
 655
 656 int read_extent_from_disk(struct extent_buffer *eb)
 657 {
 658         int ret;
 659         ret = pread(eb->fd, eb->data, eb->len, eb->dev_bytenr);
 660         if (ret < 0)
 661                 goto out;
 662         if (ret != eb->len) {
 663                 ret = -EIO;
 664                 goto out;
 665         }
 666         ret = 0;
 667 out:
 668         return ret;
 669 }
 670
 671 int write_extent_to_disk(struct extent_buffer *eb)
 672 {
 673         int ret;
 674         ret = pwrite(eb->fd, eb->data, eb->len, eb->dev_bytenr);
 675         if (ret < 0)
 676                 goto out;
 677         if (ret != eb->len) {
 678                 ret = -EIO;
 679                 goto out;
 680         }
 681         ret = 0;
 682 out:
 683         return ret;
 684 }
 685
 686 int set_extent_buffer_uptodate(struct extent_buffer *eb)
 687 {
 688         eb->flags |= EXTENT_UPTODATE;
 689         return 0;
 690 }
 691
 692 int clear_extent_buffer_uptodate(struct extent_io_tree *tree,
 693                                 struct extent_buffer *eb)
 694 {
 695         eb->flags &= ~EXTENT_UPTODATE;
 696         return 0;
 697 }
 698
 699 int extent_buffer_uptodate(struct extent_buffer *eb)
 700 {
 701         if (eb->flags & EXTENT_UPTODATE)
 702                 return 1;
 703         return 0;
 704 }
 705
 706 int set_extent_buffer_dirty(struct extent_buffer *eb)
 707 {
 708         struct extent_io_tree *tree = eb->tree;
 709         if (!(eb->flags & EXTENT_DIRTY)) {
 710                 eb->flags |= EXTENT_DIRTY;
 711                 set_extent_dirty(tree, eb->start, eb->start + eb->len - 1, 0);
 712                 extent_buffer_get(eb);
 713         }
 714         return 0;
 715 }
 716
 717 int clear_extent_buffer_dirty(struct extent_buffer *eb)
 718 {
 719         struct extent_io_tree *tree = eb->tree;
 720         if (eb->flags & EXTENT_DIRTY) {
 721                 eb->flags &= ~EXTENT_DIRTY;
 722                 clear_extent_dirty(tree, eb->start, eb->start + eb->len - 1, 0);
 723                 free_extent_buffer(eb);
 724         }
 725         return 0;
 726 }
 727
 728 int memcmp_extent_buffer(struct extent_buffer *eb, const void *ptrv,
 729                          unsigned long start, unsigned long len)
 730 {
 731         return memcmp(eb->data + start, ptrv, len);
 732 }
 733
 734 void read_extent_buffer(struct extent_buffer *eb, void *dst,
 735                         unsigned long start, unsigned long len)
 736 {
 737         memcpy(dst, eb->data + start, len);
 738 }
 739
 740 void write_extent_buffer(struct extent_buffer *eb, const void *src,
 741                          unsigned long start, unsigned long len)
 742 {
 743         memcpy(eb->data + start, src, len);
 744 }
 745
 746 void copy_extent_buffer(struct extent_buffer *dst, struct extent_buffer *src,
 747                         unsigned long dst_offset, unsigned long src_offset,
 748                         unsigned long len)
 749 {
 750         memcpy(dst->data + dst_offset, src->data + src_offset, len);
 751 }
 752
 753 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 754                           unsigned long src_offset, unsigned long len)
 755 {
 756         memcpy(dst->data + dst_offset, dst->data + src_offset, len);
 757 }
 758
 759 void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 760                            unsigned long src_offset, unsigned long len)
 761 {
 762         memmove(dst->data + dst_offset, dst->data + src_offset, len);
 763 }
 764
 765 void memset_extent_buffer(struct extent_buffer *eb, char c,
 766                           unsigned long start, unsigned long len)
 767 {
 768         memset(eb->data + start, c, len);
 769 }