fs/nfs/blocklayout/extent_tree.c

   1 /*
   2  * Copyright (c) 2014-2016 Christoph Hellwig.
   3  */
   4
   5 #include <linux/vmalloc.h>
   6
   7 #include "blocklayout.h"
   8
   9 #define NFSDBG_FACILITY         NFSDBG_PNFS_LD
  10
  11 static inline struct pnfs_block_extent *
  12 ext_node(struct rb_node *node)
  13 {
  14         return rb_entry(node, struct pnfs_block_extent, be_node);
  15 }
  16
  17 static struct pnfs_block_extent *
  18 ext_tree_first(struct rb_root *root)
  19 {
  20         struct rb_node *node = rb_first(root);
  21         return node ? ext_node(node) : NULL;
  22 }
  23
  24 static struct pnfs_block_extent *
  25 ext_tree_prev(struct pnfs_block_extent *be)
  26 {
  27         struct rb_node *node = rb_prev(&be->be_node);
  28         return node ? ext_node(node) : NULL;
  29 }
  30
  31 static struct pnfs_block_extent *
  32 ext_tree_next(struct pnfs_block_extent *be)
  33 {
  34         struct rb_node *node = rb_next(&be->be_node);
  35         return node ? ext_node(node) : NULL;
  36 }
  37
  38 static inline sector_t
  39 ext_f_end(struct pnfs_block_extent *be)
  40 {
  41         return be->be_f_offset + be->be_length;
  42 }
  43
  44 static struct pnfs_block_extent *
  45 __ext_tree_search(struct rb_root *root, sector_t start)
  46 {
  47         struct rb_node *node = root->rb_node;
  48         struct pnfs_block_extent *be = NULL;
  49
  50         while (node) {
  51                 be = ext_node(node);
  52                 if (start < be->be_f_offset)
  53                         node = node->rb_left;
  54                 else if (start >= ext_f_end(be))
  55                         node = node->rb_right;
  56                 else
  57                         return be;
  58         }
  59
  60         if (be) {
  61                 if (start < be->be_f_offset)
  62                         return be;
  63
  64                 if (start >= ext_f_end(be))
  65                         return ext_tree_next(be);
  66         }
  67
  68         return NULL;
  69 }
  70
  71 static bool
  72 ext_can_merge(struct pnfs_block_extent *be1, struct pnfs_block_extent *be2)
  73 {
  74         if (be1->be_state != be2->be_state)
  75                 return false;
  76         if (be1->be_device != be2->be_device)
  77                 return false;
  78
  79         if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
  80                 return false;
  81
  82         if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
  83             (be1->be_v_offset + be1->be_length != be2->be_v_offset))
  84                 return false;
  85
  86         if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
  87             be1->be_tag != be2->be_tag)
  88                 return false;
  89
  90         return true;
  91 }
  92
  93 static struct pnfs_block_extent *
  94 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
  95 {
  96         struct pnfs_block_extent *left = ext_tree_prev(be);
  97
  98         if (left && ext_can_merge(left, be)) {
  99                 left->be_length += be->be_length;
 100                 rb_erase(&be->be_node, root);
 101                 nfs4_put_deviceid_node(be->be_device);
 102                 kfree(be);
 103                 return left;
 104         }
 105
 106         return be;
 107 }
 108
 109 static struct pnfs_block_extent *
 110 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
 111 {
 112         struct pnfs_block_extent *right = ext_tree_next(be);
 113
 114         if (right && ext_can_merge(be, right)) {
 115                 be->be_length += right->be_length;
 116                 rb_erase(&right->be_node, root);
 117                 nfs4_put_deviceid_node(right->be_device);
 118                 kfree(right);
 119         }
 120
 121         return be;
 122 }
 123
 124 static void __ext_put_deviceids(struct list_head *head)
 125 {
 126         struct pnfs_block_extent *be, *tmp;
 127
 128         list_for_each_entry_safe(be, tmp, head, be_list) {
 129                 nfs4_put_deviceid_node(be->be_device);
 130                 kfree(be);
 131         }
 132 }
 133
 134 static void
 135 __ext_tree_insert(struct rb_root *root,
 136                 struct pnfs_block_extent *new, bool merge_ok)
 137 {
 138         struct rb_node **p = &root->rb_node, *parent = NULL;
 139         struct pnfs_block_extent *be;
 140
 141         while (*p) {
 142                 parent = *p;
 143                 be = ext_node(parent);
 144
 145                 if (new->be_f_offset < be->be_f_offset) {
 146                         if (merge_ok && ext_can_merge(new, be)) {
 147                                 be->be_f_offset = new->be_f_offset;
 148                                 if (be->be_state != PNFS_BLOCK_NONE_DATA)
 149                                         be->be_v_offset = new->be_v_offset;
 150                                 be->be_length += new->be_length;
 151                                 be = ext_try_to_merge_left(root, be);
 152                                 goto free_new;
 153                         }
 154                         p = &(*p)->rb_left;
 155                 } else if (new->be_f_offset >= ext_f_end(be)) {
 156                         if (merge_ok && ext_can_merge(be, new)) {
 157                                 be->be_length += new->be_length;
 158                                 be = ext_try_to_merge_right(root, be);
 159                                 goto free_new;
 160                         }
 161                         p = &(*p)->rb_right;
 162                 } else {
 163                         BUG();
 164                 }
 165         }
 166
 167         rb_link_node(&new->be_node, parent, p);
 168         rb_insert_color(&new->be_node, root);
 169         return;
 170 free_new:
 171         nfs4_put_deviceid_node(new->be_device);
 172         kfree(new);
 173 }
 174
 175 static int
 176 __ext_tree_remove(struct rb_root *root,
 177                 sector_t start, sector_t end, struct list_head *tmp)
 178 {
 179         struct pnfs_block_extent *be;
 180         sector_t len1 = 0, len2 = 0;
 181         sector_t orig_v_offset;
 182         sector_t orig_len;
 183
 184         be = __ext_tree_search(root, start);
 185         if (!be)
 186                 return 0;
 187         if (be->be_f_offset >= end)
 188                 return 0;
 189
 190         orig_v_offset = be->be_v_offset;
 191         orig_len = be->be_length;
 192
 193         if (start > be->be_f_offset)
 194                 len1 = start - be->be_f_offset;
 195         if (ext_f_end(be) > end)
 196                 len2 = ext_f_end(be) - end;
 197
 198         if (len2 > 0) {
 199                 if (len1 > 0) {
 200                         struct pnfs_block_extent *new;
 201
 202                         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 203                         if (!new)
 204                                 return -ENOMEM;
 205
 206                         be->be_length = len1;
 207
 208                         new->be_f_offset = end;
 209                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
 210                                 new->be_v_offset =
 211                                         orig_v_offset + orig_len - len2;
 212                         }
 213                         new->be_length = len2;
 214                         new->be_state = be->be_state;
 215                         new->be_tag = be->be_tag;
 216                         new->be_device = nfs4_get_deviceid(be->be_device);
 217
 218                         __ext_tree_insert(root, new, true);
 219                 } else {
 220                         be->be_f_offset = end;
 221                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
 222                                 be->be_v_offset =
 223                                         orig_v_offset + orig_len - len2;
 224                         }
 225                         be->be_length = len2;
 226                 }
 227         } else {
 228                 if (len1 > 0) {
 229                         be->be_length = len1;
 230                         be = ext_tree_next(be);
 231                 }
 232
 233                 while (be && ext_f_end(be) <= end) {
 234                         struct pnfs_block_extent *next = ext_tree_next(be);
 235
 236                         rb_erase(&be->be_node, root);
 237                         list_add_tail(&be->be_list, tmp);
 238                         be = next;
 239                 }
 240
 241                 if (be && be->be_f_offset < end) {
 242                         len1 = ext_f_end(be) - end;
 243                         be->be_f_offset = end;
 244                         if (be->be_state != PNFS_BLOCK_NONE_DATA)
 245                                 be->be_v_offset += be->be_length - len1;
 246                         be->be_length = len1;
 247                 }
 248         }
 249
 250         return 0;
 251 }
 252
 253 int
 254 ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
 255 {
 256         struct pnfs_block_extent *be;
 257         struct rb_root *root;
 258         int err = 0;
 259
 260         switch (new->be_state) {
 261         case PNFS_BLOCK_READWRITE_DATA:
 262         case PNFS_BLOCK_INVALID_DATA:
 263                 root = &bl->bl_ext_rw;
 264                 break;
 265         case PNFS_BLOCK_READ_DATA:
 266         case PNFS_BLOCK_NONE_DATA:
 267                 root = &bl->bl_ext_ro;
 268                 break;
 269         default:
 270                 dprintk("invalid extent type\n");
 271                 return -EINVAL;
 272         }
 273
 274         spin_lock(&bl->bl_ext_lock);
 275 retry:
 276         be = __ext_tree_search(root, new->be_f_offset);
 277         if (!be || be->be_f_offset >= ext_f_end(new)) {
 278                 __ext_tree_insert(root, new, true);
 279         } else if (new->be_f_offset >= be->be_f_offset) {
 280                 if (ext_f_end(new) <= ext_f_end(be)) {
 281                         nfs4_put_deviceid_node(new->be_device);
 282                         kfree(new);
 283                 } else {
 284                         sector_t new_len = ext_f_end(new) - ext_f_end(be);
 285                         sector_t diff = new->be_length - new_len;
 286
 287                         new->be_f_offset += diff;
 288                         new->be_v_offset += diff;
 289                         new->be_length = new_len;
 290                         goto retry;
 291                 }
 292         } else if (ext_f_end(new) <= ext_f_end(be)) {
 293                 new->be_length = be->be_f_offset - new->be_f_offset;
 294                 __ext_tree_insert(root, new, true);
 295         } else {
 296                 struct pnfs_block_extent *split;
 297                 sector_t new_len = ext_f_end(new) - ext_f_end(be);
 298                 sector_t diff = new->be_length - new_len;
 299
 300                 split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
 301                 if (!split) {
 302                         err = -EINVAL;
 303                         goto out;
 304                 }
 305
 306                 split->be_length = be->be_f_offset - split->be_f_offset;
 307                 split->be_device = nfs4_get_deviceid(new->be_device);
 308                 __ext_tree_insert(root, split, true);
 309
 310                 new->be_f_offset += diff;
 311                 new->be_v_offset += diff;
 312                 new->be_length = new_len;
 313                 goto retry;
 314         }
 315 out:
 316         spin_unlock(&bl->bl_ext_lock);
 317         return err;
 318 }
 319
 320 static bool
 321 __ext_tree_lookup(struct rb_root *root, sector_t isect,
 322                 struct pnfs_block_extent *ret)
 323 {
 324         struct rb_node *node;
 325         struct pnfs_block_extent *be;
 326
 327         node = root->rb_node;
 328         while (node) {
 329                 be = ext_node(node);
 330                 if (isect < be->be_f_offset)
 331                         node = node->rb_left;
 332                 else if (isect >= ext_f_end(be))
 333                         node = node->rb_right;
 334                 else {
 335                         *ret = *be;
 336                         return true;
 337                 }
 338         }
 339
 340         return false;
 341 }
 342
 343 bool
 344 ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
 345             struct pnfs_block_extent *ret, bool rw)
 346 {
 347         bool found = false;
 348
 349         spin_lock(&bl->bl_ext_lock);
 350         if (!rw)
 351                 found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
 352         if (!found)
 353                 found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
 354         spin_unlock(&bl->bl_ext_lock);
 355
 356         return found;
 357 }
 358
 359 int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
 360                 sector_t start, sector_t end)
 361 {
 362         int err, err2;
 363         LIST_HEAD(tmp);
 364
 365         spin_lock(&bl->bl_ext_lock);
 366         err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
 367         if (rw) {
 368                 err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end, &tmp);
 369                 if (!err)
 370                         err = err2;
 371         }
 372         spin_unlock(&bl->bl_ext_lock);
 373
 374         __ext_put_deviceids(&tmp);
 375         return err;
 376 }
 377
 378 static int
 379 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
 380                 sector_t split)
 381 {
 382         struct pnfs_block_extent *new;
 383         sector_t orig_len = be->be_length;
 384
 385         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 386         if (!new)
 387                 return -ENOMEM;
 388
 389         be->be_length = split - be->be_f_offset;
 390
 391         new->be_f_offset = split;
 392         if (be->be_state != PNFS_BLOCK_NONE_DATA)
 393                 new->be_v_offset = be->be_v_offset + be->be_length;
 394         new->be_length = orig_len - be->be_length;
 395         new->be_state = be->be_state;
 396         new->be_tag = be->be_tag;
 397         new->be_device = nfs4_get_deviceid(be->be_device);
 398
 399         __ext_tree_insert(root, new, false);
 400         return 0;
 401 }
 402
 403 int
 404 ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
 405                 sector_t len, u64 lwb)
 406 {
 407         struct rb_root *root = &bl->bl_ext_rw;
 408         sector_t end = start + len;
 409         struct pnfs_block_extent *be;
 410         int err = 0;
 411         LIST_HEAD(tmp);
 412
 413         spin_lock(&bl->bl_ext_lock);
 414         /*
 415          * First remove all COW extents or holes from written to range.
 416          */
 417         err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
 418         if (err)
 419                 goto out;
 420
 421         /*
 422          * Then mark all invalid extents in the range as written to.
 423          */
 424         for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
 425                 if (be->be_f_offset >= end)
 426                         break;
 427
 428                 if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
 429                         continue;
 430
 431                 if (be->be_f_offset < start) {
 432                         struct pnfs_block_extent *left = ext_tree_prev(be);
 433
 434                         if (left && ext_can_merge(left, be)) {
 435                                 sector_t diff = start - be->be_f_offset;
 436
 437                                 left->be_length += diff;
 438
 439                                 be->be_f_offset += diff;
 440                                 be->be_v_offset += diff;
 441                                 be->be_length -= diff;
 442                         } else {
 443                                 err = ext_tree_split(root, be, start);
 444                                 if (err)
 445                                         goto out;
 446                         }
 447                 }
 448
 449                 if (ext_f_end(be) > end) {
 450                         struct pnfs_block_extent *right = ext_tree_next(be);
 451
 452                         if (right && ext_can_merge(be, right)) {
 453                                 sector_t diff = end - be->be_f_offset;
 454
 455                                 be->be_length -= diff;
 456
 457                                 right->be_f_offset -= diff;
 458                                 right->be_v_offset -= diff;
 459                                 right->be_length += diff;
 460                         } else {
 461                                 err = ext_tree_split(root, be, end);
 462                                 if (err)
 463                                         goto out;
 464                         }
 465                 }
 466
 467                 if (be->be_f_offset >= start && ext_f_end(be) <= end) {
 468                         be->be_tag = EXTENT_WRITTEN;
 469                         be = ext_try_to_merge_left(root, be);
 470                         be = ext_try_to_merge_right(root, be);
 471                 }
 472         }
 473 out:
 474         if (bl->bl_lwb < lwb)
 475                 bl->bl_lwb = lwb;
 476         spin_unlock(&bl->bl_ext_lock);
 477
 478         __ext_put_deviceids(&tmp);
 479         return err;
 480 }
 481
 482 static size_t ext_tree_layoutupdate_size(struct pnfs_block_layout *bl, size_t count)
 483 {
 484         if (bl->bl_scsi_layout)
 485                 return sizeof(__be32) + PNFS_SCSI_RANGE_SIZE * count;
 486         else
 487                 return sizeof(__be32) + PNFS_BLOCK_EXTENT_SIZE * count;
 488 }
 489
 490 static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
 491                 size_t buffer_size)
 492 {
 493         if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
 494                 int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;
 495
 496                 for (i = 0; i < nr_pages; i++)
 497                         put_page(arg->layoutupdate_pages[i]);
 498                 vfree(arg->start_p);
 499                 kfree(arg->layoutupdate_pages);
 500         } else {
 501                 put_page(arg->layoutupdate_page);
 502         }
 503 }
 504
 505 static __be32 *encode_block_extent(struct pnfs_block_extent *be, __be32 *p)
 506 {
 507         p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
 508                         NFS4_DEVICEID4_SIZE);
 509         p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
 510         p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
 511         p = xdr_encode_hyper(p, 0LL);
 512         *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
 513         return p;
 514 }
 515
 516 static __be32 *encode_scsi_range(struct pnfs_block_extent *be, __be32 *p)
 517 {
 518         p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
 519         return xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
 520 }
 521
 522 static int ext_tree_encode_commit(struct pnfs_block_layout *bl, __be32 *p,
 523                 size_t buffer_size, size_t *count, __u64 *lastbyte)
 524 {
 525         struct pnfs_block_extent *be;
 526         int ret = 0;
 527
 528         spin_lock(&bl->bl_ext_lock);
 529         for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
 530                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
 531                     be->be_tag != EXTENT_WRITTEN)
 532                         continue;
 533
 534                 (*count)++;
 535                 if (ext_tree_layoutupdate_size(bl, *count) > buffer_size) {
 536                         /* keep counting.. */
 537                         ret = -ENOSPC;
 538                         continue;
 539                 }
 540
 541                 if (bl->bl_scsi_layout)
 542                         p = encode_scsi_range(be, p);
 543                 else
 544                         p = encode_block_extent(be, p);
 545                 be->be_tag = EXTENT_COMMITTING;
 546         }
 547         *lastbyte = bl->bl_lwb - 1;
 548         bl->bl_lwb = 0;
 549         spin_unlock(&bl->bl_ext_lock);
 550
 551         return ret;
 552 }
 553
 554 int
 555 ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
 556 {
 557         struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
 558         size_t count = 0, buffer_size = PAGE_SIZE;
 559         __be32 *start_p;
 560         int ret;
 561
 562         dprintk("%s enter\n", __func__);
 563
 564         arg->layoutupdate_page = alloc_page(GFP_NOFS);
 565         if (!arg->layoutupdate_page)
 566                 return -ENOMEM;
 567         start_p = page_address(arg->layoutupdate_page);
 568         arg->layoutupdate_pages = &arg->layoutupdate_page;
 569
 570 retry:
 571         ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count, &arg->lastbytewritten);
 572         if (unlikely(ret)) {
 573                 ext_tree_free_commitdata(arg, buffer_size);
 574
 575                 buffer_size = ext_tree_layoutupdate_size(bl, count);
 576                 count = 0;
 577
 578                 arg->layoutupdate_pages =
 579                         kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
 580                                 sizeof(struct page *), GFP_NOFS);
 581                 if (!arg->layoutupdate_pages)
 582                         return -ENOMEM;
 583
 584                 start_p = __vmalloc(buffer_size, GFP_NOFS, PAGE_KERNEL);
 585                 if (!start_p) {
 586                         kfree(arg->layoutupdate_pages);
 587                         return -ENOMEM;
 588                 }
 589
 590                 goto retry;
 591         }
 592
 593         *start_p = cpu_to_be32(count);
 594         arg->layoutupdate_len = ext_tree_layoutupdate_size(bl, count);
 595
 596         if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
 597                 void *p = start_p, *end = p + arg->layoutupdate_len;
 598                 struct page *page = NULL;
 599                 int i = 0;
 600
 601                 arg->start_p = start_p;
 602                 for ( ; p < end; p += PAGE_SIZE) {
 603                         page = vmalloc_to_page(p);
 604                         arg->layoutupdate_pages[i++] = page;
 605                         get_page(page);
 606                 }
 607         }
 608
 609         dprintk("%s found %zu ranges\n", __func__, count);
 610         return 0;
 611 }
 612
 613 void
 614 ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
 615 {
 616         struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
 617         struct rb_root *root = &bl->bl_ext_rw;
 618         struct pnfs_block_extent *be;
 619
 620         dprintk("%s status %d\n", __func__, status);
 621
 622         ext_tree_free_commitdata(arg, arg->layoutupdate_len);
 623
 624         spin_lock(&bl->bl_ext_lock);
 625         for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
 626                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
 627                     be->be_tag != EXTENT_COMMITTING)
 628                         continue;
 629
 630                 if (status) {
 631                         /*
 632                          * Mark as written and try again.
 633                          *
 634                          * XXX: some real error handling here wouldn't hurt..
 635                          */
 636                         be->be_tag = EXTENT_WRITTEN;
 637                 } else {
 638                         be->be_state = PNFS_BLOCK_READWRITE_DATA;
 639                         be->be_tag = 0;
 640                 }
 641
 642                 be = ext_try_to_merge_left(root, be);
 643                 be = ext_try_to_merge_right(root, be);
 644         }
 645         spin_unlock(&bl->bl_ext_lock);
 646 }