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