fs/nfs/blocklayout/extent_tree.c

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