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 19 #include <linux/bio.h> 20 #include <linux/slab.h> 21 #include <linux/pagemap.h> 22 #include <linux/highmem.h> 23 #include "ctree.h" 24 #include "disk-io.h" 25 #include "transaction.h" 26 #include "print-tree.h" 27 28 #define __MAX_CSUM_ITEMS(r, size) ((unsigned long)(((BTRFS_LEAF_DATA_SIZE(r) - \ 29 sizeof(struct btrfs_item) * 2) / \ 30 size) - 1)) 31 32 #define MAX_CSUM_ITEMS(r, size) (min_t(u32, __MAX_CSUM_ITEMS(r, size), \ 33 PAGE_CACHE_SIZE)) 34 35 #define MAX_ORDERED_SUM_BYTES(r) ((PAGE_SIZE - \ 36 sizeof(struct btrfs_ordered_sum)) / \ 37 sizeof(u32) * (r)->sectorsize) 38 39 int btrfs_insert_file_extent(struct btrfs_trans_handle *trans, 40 struct btrfs_root *root, 41 u64 objectid, u64 pos, 42 u64 disk_offset, u64 disk_num_bytes, 43 u64 num_bytes, u64 offset, u64 ram_bytes, 44 u8 compression, u8 encryption, u16 other_encoding) 45 { 46 int ret = 0; 47 struct btrfs_file_extent_item *item; 48 struct btrfs_key file_key; 49 struct btrfs_path *path; 50 struct extent_buffer *leaf; 51 52 path = btrfs_alloc_path(); 53 if (!path) 54 return -ENOMEM; 55 file_key.objectid = objectid; 56 file_key.offset = pos; 57 btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY); 58 59 path->leave_spinning = 1; 60 ret = btrfs_insert_empty_item(trans, root, path, &file_key, 61 sizeof(*item)); 62 if (ret < 0) 63 goto out; 64 BUG_ON(ret); /* Can't happen */ 65 leaf = path->nodes[0]; 66 item = btrfs_item_ptr(leaf, path->slots[0], 67 struct btrfs_file_extent_item); 68 btrfs_set_file_extent_disk_bytenr(leaf, item, disk_offset); 69 btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes); 70 btrfs_set_file_extent_offset(leaf, item, offset); 71 btrfs_set_file_extent_num_bytes(leaf, item, num_bytes); 72 btrfs_set_file_extent_ram_bytes(leaf, item, ram_bytes); 73 btrfs_set_file_extent_generation(leaf, item, trans->transid); 74 btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG); 75 btrfs_set_file_extent_compression(leaf, item, compression); 76 btrfs_set_file_extent_encryption(leaf, item, encryption); 77 btrfs_set_file_extent_other_encoding(leaf, item, other_encoding); 78 79 btrfs_mark_buffer_dirty(leaf); 80 out: 81 btrfs_free_path(path); 82 return ret; 83 } 84 85 static struct btrfs_csum_item * 86 btrfs_lookup_csum(struct btrfs_trans_handle *trans, 87 struct btrfs_root *root, 88 struct btrfs_path *path, 89 u64 bytenr, int cow) 90 { 91 int ret; 92 struct btrfs_key file_key; 93 struct btrfs_key found_key; 94 struct btrfs_csum_item *item; 95 struct extent_buffer *leaf; 96 u64 csum_offset = 0; 97 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 98 int csums_in_item; 99 100 file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID; 101 file_key.offset = bytenr; 102 btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY); 103 ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow); 104 if (ret < 0) 105 goto fail; 106 leaf = path->nodes[0]; 107 if (ret > 0) { 108 ret = 1; 109 if (path->slots[0] == 0) 110 goto fail; 111 path->slots[0]--; 112 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 113 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY) 114 goto fail; 115 116 csum_offset = (bytenr - found_key.offset) >> 117 root->fs_info->sb->s_blocksize_bits; 118 csums_in_item = btrfs_item_size_nr(leaf, path->slots[0]); 119 csums_in_item /= csum_size; 120 121 if (csum_offset == csums_in_item) { 122 ret = -EFBIG; 123 goto fail; 124 } else if (csum_offset > csums_in_item) { 125 goto fail; 126 } 127 } 128 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item); 129 item = (struct btrfs_csum_item *)((unsigned char *)item + 130 csum_offset * csum_size); 131 return item; 132 fail: 133 if (ret > 0) 134 ret = -ENOENT; 135 return ERR_PTR(ret); 136 } 137 138 int btrfs_lookup_file_extent(struct btrfs_trans_handle *trans, 139 struct btrfs_root *root, 140 struct btrfs_path *path, u64 objectid, 141 u64 offset, int mod) 142 { 143 int ret; 144 struct btrfs_key file_key; 145 int ins_len = mod < 0 ? -1 : 0; 146 int cow = mod != 0; 147 148 file_key.objectid = objectid; 149 file_key.offset = offset; 150 btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY); 151 ret = btrfs_search_slot(trans, root, &file_key, path, ins_len, cow); 152 return ret; 153 } 154 155 static int __btrfs_lookup_bio_sums(struct btrfs_root *root, 156 struct inode *inode, struct bio *bio, 157 u64 logical_offset, u32 *dst, int dio) 158 { 159 u32 sum[16]; 160 int len; 161 struct bio_vec *bvec = bio->bi_io_vec; 162 int bio_index = 0; 163 u64 offset = 0; 164 u64 item_start_offset = 0; 165 u64 item_last_offset = 0; 166 u64 disk_bytenr; 167 u32 diff; 168 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 169 int count; 170 struct btrfs_path *path; 171 struct btrfs_csum_item *item = NULL; 172 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree; 173 174 path = btrfs_alloc_path(); 175 if (!path) 176 return -ENOMEM; 177 if (bio->bi_size > PAGE_CACHE_SIZE * 8) 178 path->reada = 2; 179 180 WARN_ON(bio->bi_vcnt <= 0); 181 182 /* 183 * the free space stuff is only read when it hasn't been 184 * updated in the current transaction. So, we can safely 185 * read from the commit root and sidestep a nasty deadlock 186 * between reading the free space cache and updating the csum tree. 187 */ 188 if (btrfs_is_free_space_inode(inode)) { 189 path->search_commit_root = 1; 190 path->skip_locking = 1; 191 } 192 193 disk_bytenr = (u64)bio->bi_sector << 9; 194 if (dio) 195 offset = logical_offset; 196 while (bio_index < bio->bi_vcnt) { 197 len = min_t(int, ARRAY_SIZE(sum), bio->bi_vcnt - bio_index); 198 if (!dio) 199 offset = page_offset(bvec->bv_page) + bvec->bv_offset; 200 count = btrfs_find_ordered_sum(inode, offset, disk_bytenr, sum, 201 len); 202 if (count) 203 goto found; 204 205 if (!item || disk_bytenr < item_start_offset || 206 disk_bytenr >= item_last_offset) { 207 struct btrfs_key found_key; 208 u32 item_size; 209 210 if (item) 211 btrfs_release_path(path); 212 item = btrfs_lookup_csum(NULL, root->fs_info->csum_root, 213 path, disk_bytenr, 0); 214 if (IS_ERR(item)) { 215 count = 1; 216 sum[0] = 0; 217 if (BTRFS_I(inode)->root->root_key.objectid == 218 BTRFS_DATA_RELOC_TREE_OBJECTID) { 219 set_extent_bits(io_tree, offset, 220 offset + bvec->bv_len - 1, 221 EXTENT_NODATASUM, GFP_NOFS); 222 } else { 223 printk(KERN_INFO "btrfs no csum found " 224 "for inode %llu start %llu\n", 225 (unsigned long long) 226 btrfs_ino(inode), 227 (unsigned long long)offset); 228 } 229 item = NULL; 230 btrfs_release_path(path); 231 goto found; 232 } 233 btrfs_item_key_to_cpu(path->nodes[0], &found_key, 234 path->slots[0]); 235 236 item_start_offset = found_key.offset; 237 item_size = btrfs_item_size_nr(path->nodes[0], 238 path->slots[0]); 239 item_last_offset = item_start_offset + 240 (item_size / csum_size) * 241 root->sectorsize; 242 item = btrfs_item_ptr(path->nodes[0], path->slots[0], 243 struct btrfs_csum_item); 244 } 245 /* 246 * this byte range must be able to fit inside 247 * a single leaf so it will also fit inside a u32 248 */ 249 diff = disk_bytenr - item_start_offset; 250 diff = diff / root->sectorsize; 251 diff = diff * csum_size; 252 count = min_t(int, len, (item_last_offset - disk_bytenr) >> 253 inode->i_sb->s_blocksize_bits); 254 read_extent_buffer(path->nodes[0], sum, 255 ((unsigned long)item) + diff, 256 csum_size * count); 257 found: 258 if (dst) { 259 memcpy(dst, sum, count * csum_size); 260 dst += count; 261 } else { 262 if (dio) 263 extent_cache_csums_dio(io_tree, offset, sum, 264 count); 265 else 266 extent_cache_csums(io_tree, bio, bio_index, sum, 267 count); 268 } 269 while (count--) { 270 disk_bytenr += bvec->bv_len; 271 offset += bvec->bv_len; 272 bio_index++; 273 bvec++; 274 } 275 } 276 btrfs_free_path(path); 277 return 0; 278 } 279 280 int btrfs_lookup_bio_sums(struct btrfs_root *root, struct inode *inode, 281 struct bio *bio, u32 *dst) 282 { 283 return __btrfs_lookup_bio_sums(root, inode, bio, 0, dst, 0); 284 } 285 286 int btrfs_lookup_bio_sums_dio(struct btrfs_root *root, struct inode *inode, 287 struct bio *bio, u64 offset) 288 { 289 return __btrfs_lookup_bio_sums(root, inode, bio, offset, NULL, 1); 290 } 291 292 int btrfs_lookup_csums_range(struct btrfs_root *root, u64 start, u64 end, 293 struct list_head *list, int search_commit) 294 { 295 struct btrfs_key key; 296 struct btrfs_path *path; 297 struct extent_buffer *leaf; 298 struct btrfs_ordered_sum *sums; 299 struct btrfs_csum_item *item; 300 LIST_HEAD(tmplist); 301 unsigned long offset; 302 int ret; 303 size_t size; 304 u64 csum_end; 305 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 306 307 path = btrfs_alloc_path(); 308 if (!path) 309 return -ENOMEM; 310 311 if (search_commit) { 312 path->skip_locking = 1; 313 path->reada = 2; 314 path->search_commit_root = 1; 315 } 316 317 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID; 318 key.offset = start; 319 key.type = BTRFS_EXTENT_CSUM_KEY; 320 321 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 322 if (ret < 0) 323 goto fail; 324 if (ret > 0 && path->slots[0] > 0) { 325 leaf = path->nodes[0]; 326 btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1); 327 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID && 328 key.type == BTRFS_EXTENT_CSUM_KEY) { 329 offset = (start - key.offset) >> 330 root->fs_info->sb->s_blocksize_bits; 331 if (offset * csum_size < 332 btrfs_item_size_nr(leaf, path->slots[0] - 1)) 333 path->slots[0]--; 334 } 335 } 336 337 while (start <= end) { 338 leaf = path->nodes[0]; 339 if (path->slots[0] >= btrfs_header_nritems(leaf)) { 340 ret = btrfs_next_leaf(root, path); 341 if (ret < 0) 342 goto fail; 343 if (ret > 0) 344 break; 345 leaf = path->nodes[0]; 346 } 347 348 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 349 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID || 350 key.type != BTRFS_EXTENT_CSUM_KEY || 351 key.offset > end) 352 break; 353 354 if (key.offset > start) 355 start = key.offset; 356 357 size = btrfs_item_size_nr(leaf, path->slots[0]); 358 csum_end = key.offset + (size / csum_size) * root->sectorsize; 359 if (csum_end <= start) { 360 path->slots[0]++; 361 continue; 362 } 363 364 csum_end = min(csum_end, end + 1); 365 item = btrfs_item_ptr(path->nodes[0], path->slots[0], 366 struct btrfs_csum_item); 367 while (start < csum_end) { 368 size = min_t(size_t, csum_end - start, 369 MAX_ORDERED_SUM_BYTES(root)); 370 sums = kzalloc(btrfs_ordered_sum_size(root, size), 371 GFP_NOFS); 372 if (!sums) { 373 ret = -ENOMEM; 374 goto fail; 375 } 376 377 sums->bytenr = start; 378 sums->len = (int)size; 379 380 offset = (start - key.offset) >> 381 root->fs_info->sb->s_blocksize_bits; 382 offset *= csum_size; 383 size >>= root->fs_info->sb->s_blocksize_bits; 384 385 read_extent_buffer(path->nodes[0], 386 sums->sums, 387 ((unsigned long)item) + offset, 388 csum_size * size); 389 390 start += root->sectorsize * size; 391 list_add_tail(&sums->list, &tmplist); 392 } 393 path->slots[0]++; 394 } 395 ret = 0; 396 fail: 397 while (ret < 0 && !list_empty(&tmplist)) { 398 sums = list_entry(&tmplist, struct btrfs_ordered_sum, list); 399 list_del(&sums->list); 400 kfree(sums); 401 } 402 list_splice_tail(&tmplist, list); 403 404 btrfs_free_path(path); 405 return ret; 406 } 407 408 int btrfs_csum_one_bio(struct btrfs_root *root, struct inode *inode, 409 struct bio *bio, u64 file_start, int contig) 410 { 411 struct btrfs_ordered_sum *sums; 412 struct btrfs_ordered_extent *ordered; 413 char *data; 414 struct bio_vec *bvec = bio->bi_io_vec; 415 int bio_index = 0; 416 int index; 417 unsigned long total_bytes = 0; 418 unsigned long this_sum_bytes = 0; 419 u64 offset; 420 421 WARN_ON(bio->bi_vcnt <= 0); 422 sums = kzalloc(btrfs_ordered_sum_size(root, bio->bi_size), GFP_NOFS); 423 if (!sums) 424 return -ENOMEM; 425 426 sums->len = bio->bi_size; 427 INIT_LIST_HEAD(&sums->list); 428 429 if (contig) 430 offset = file_start; 431 else 432 offset = page_offset(bvec->bv_page) + bvec->bv_offset; 433 434 ordered = btrfs_lookup_ordered_extent(inode, offset); 435 BUG_ON(!ordered); /* Logic error */ 436 sums->bytenr = (u64)bio->bi_sector << 9; 437 index = 0; 438 439 while (bio_index < bio->bi_vcnt) { 440 if (!contig) 441 offset = page_offset(bvec->bv_page) + bvec->bv_offset; 442 443 if (offset >= ordered->file_offset + ordered->len || 444 offset < ordered->file_offset) { 445 unsigned long bytes_left; 446 sums->len = this_sum_bytes; 447 this_sum_bytes = 0; 448 btrfs_add_ordered_sum(inode, ordered, sums); 449 btrfs_put_ordered_extent(ordered); 450 451 bytes_left = bio->bi_size - total_bytes; 452 453 sums = kzalloc(btrfs_ordered_sum_size(root, bytes_left), 454 GFP_NOFS); 455 BUG_ON(!sums); /* -ENOMEM */ 456 sums->len = bytes_left; 457 ordered = btrfs_lookup_ordered_extent(inode, offset); 458 BUG_ON(!ordered); /* Logic error */ 459 sums->bytenr = ((u64)bio->bi_sector << 9) + 460 total_bytes; 461 index = 0; 462 } 463 464 data = kmap_atomic(bvec->bv_page); 465 sums->sums[index] = ~(u32)0; 466 sums->sums[index] = btrfs_csum_data(data + bvec->bv_offset, 467 sums->sums[index], 468 bvec->bv_len); 469 kunmap_atomic(data); 470 btrfs_csum_final(sums->sums[index], 471 (char *)(sums->sums + index)); 472 473 bio_index++; 474 index++; 475 total_bytes += bvec->bv_len; 476 this_sum_bytes += bvec->bv_len; 477 offset += bvec->bv_len; 478 bvec++; 479 } 480 this_sum_bytes = 0; 481 btrfs_add_ordered_sum(inode, ordered, sums); 482 btrfs_put_ordered_extent(ordered); 483 return 0; 484 } 485 486 /* 487 * helper function for csum removal, this expects the 488 * key to describe the csum pointed to by the path, and it expects 489 * the csum to overlap the range [bytenr, len] 490 * 491 * The csum should not be entirely contained in the range and the 492 * range should not be entirely contained in the csum. 493 * 494 * This calls btrfs_truncate_item with the correct args based on the 495 * overlap, and fixes up the key as required. 496 */ 497 static noinline void truncate_one_csum(struct btrfs_root *root, 498 struct btrfs_path *path, 499 struct btrfs_key *key, 500 u64 bytenr, u64 len) 501 { 502 struct extent_buffer *leaf; 503 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 504 u64 csum_end; 505 u64 end_byte = bytenr + len; 506 u32 blocksize_bits = root->fs_info->sb->s_blocksize_bits; 507 508 leaf = path->nodes[0]; 509 csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size; 510 csum_end <<= root->fs_info->sb->s_blocksize_bits; 511 csum_end += key->offset; 512 513 if (key->offset < bytenr && csum_end <= end_byte) { 514 /* 515 * [ bytenr - len ] 516 * [ ] 517 * [csum ] 518 * A simple truncate off the end of the item 519 */ 520 u32 new_size = (bytenr - key->offset) >> blocksize_bits; 521 new_size *= csum_size; 522 btrfs_truncate_item(root, path, new_size, 1); 523 } else if (key->offset >= bytenr && csum_end > end_byte && 524 end_byte > key->offset) { 525 /* 526 * [ bytenr - len ] 527 * [ ] 528 * [csum ] 529 * we need to truncate from the beginning of the csum 530 */ 531 u32 new_size = (csum_end - end_byte) >> blocksize_bits; 532 new_size *= csum_size; 533 534 btrfs_truncate_item(root, path, new_size, 0); 535 536 key->offset = end_byte; 537 btrfs_set_item_key_safe(root, path, key); 538 } else { 539 BUG(); 540 } 541 } 542 543 /* 544 * deletes the csum items from the csum tree for a given 545 * range of bytes. 546 */ 547 int btrfs_del_csums(struct btrfs_trans_handle *trans, 548 struct btrfs_root *root, u64 bytenr, u64 len) 549 { 550 struct btrfs_path *path; 551 struct btrfs_key key; 552 u64 end_byte = bytenr + len; 553 u64 csum_end; 554 struct extent_buffer *leaf; 555 int ret; 556 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 557 int blocksize_bits = root->fs_info->sb->s_blocksize_bits; 558 559 root = root->fs_info->csum_root; 560 561 path = btrfs_alloc_path(); 562 if (!path) 563 return -ENOMEM; 564 565 while (1) { 566 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID; 567 key.offset = end_byte - 1; 568 key.type = BTRFS_EXTENT_CSUM_KEY; 569 570 path->leave_spinning = 1; 571 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 572 if (ret > 0) { 573 if (path->slots[0] == 0) 574 break; 575 path->slots[0]--; 576 } else if (ret < 0) { 577 break; 578 } 579 580 leaf = path->nodes[0]; 581 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 582 583 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID || 584 key.type != BTRFS_EXTENT_CSUM_KEY) { 585 break; 586 } 587 588 if (key.offset >= end_byte) 589 break; 590 591 csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size; 592 csum_end <<= blocksize_bits; 593 csum_end += key.offset; 594 595 /* this csum ends before we start, we're done */ 596 if (csum_end <= bytenr) 597 break; 598 599 /* delete the entire item, it is inside our range */ 600 if (key.offset >= bytenr && csum_end <= end_byte) { 601 ret = btrfs_del_item(trans, root, path); 602 if (ret) 603 goto out; 604 if (key.offset == bytenr) 605 break; 606 } else if (key.offset < bytenr && csum_end > end_byte) { 607 unsigned long offset; 608 unsigned long shift_len; 609 unsigned long item_offset; 610 /* 611 * [ bytenr - len ] 612 * [csum ] 613 * 614 * Our bytes are in the middle of the csum, 615 * we need to split this item and insert a new one. 616 * 617 * But we can't drop the path because the 618 * csum could change, get removed, extended etc. 619 * 620 * The trick here is the max size of a csum item leaves 621 * enough room in the tree block for a single 622 * item header. So, we split the item in place, 623 * adding a new header pointing to the existing 624 * bytes. Then we loop around again and we have 625 * a nicely formed csum item that we can neatly 626 * truncate. 627 */ 628 offset = (bytenr - key.offset) >> blocksize_bits; 629 offset *= csum_size; 630 631 shift_len = (len >> blocksize_bits) * csum_size; 632 633 item_offset = btrfs_item_ptr_offset(leaf, 634 path->slots[0]); 635 636 memset_extent_buffer(leaf, 0, item_offset + offset, 637 shift_len); 638 key.offset = bytenr; 639 640 /* 641 * btrfs_split_item returns -EAGAIN when the 642 * item changed size or key 643 */ 644 ret = btrfs_split_item(trans, root, path, &key, offset); 645 if (ret && ret != -EAGAIN) { 646 btrfs_abort_transaction(trans, root, ret); 647 goto out; 648 } 649 650 key.offset = end_byte - 1; 651 } else { 652 truncate_one_csum(root, path, &key, bytenr, len); 653 if (key.offset < bytenr) 654 break; 655 } 656 btrfs_release_path(path); 657 } 658 ret = 0; 659 out: 660 btrfs_free_path(path); 661 return ret; 662 } 663 664 int btrfs_csum_file_blocks(struct btrfs_trans_handle *trans, 665 struct btrfs_root *root, 666 struct btrfs_ordered_sum *sums) 667 { 668 struct btrfs_key file_key; 669 struct btrfs_key found_key; 670 struct btrfs_path *path; 671 struct btrfs_csum_item *item; 672 struct btrfs_csum_item *item_end; 673 struct extent_buffer *leaf = NULL; 674 u64 next_offset; 675 u64 total_bytes = 0; 676 u64 csum_offset; 677 u64 bytenr; 678 u32 nritems; 679 u32 ins_size; 680 int index = 0; 681 int found_next; 682 int ret; 683 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy); 684 685 path = btrfs_alloc_path(); 686 if (!path) 687 return -ENOMEM; 688 again: 689 next_offset = (u64)-1; 690 found_next = 0; 691 bytenr = sums->bytenr + total_bytes; 692 file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID; 693 file_key.offset = bytenr; 694 btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY); 695 696 item = btrfs_lookup_csum(trans, root, path, bytenr, 1); 697 if (!IS_ERR(item)) { 698 ret = 0; 699 leaf = path->nodes[0]; 700 item_end = btrfs_item_ptr(leaf, path->slots[0], 701 struct btrfs_csum_item); 702 item_end = (struct btrfs_csum_item *)((char *)item_end + 703 btrfs_item_size_nr(leaf, path->slots[0])); 704 goto found; 705 } 706 ret = PTR_ERR(item); 707 if (ret != -EFBIG && ret != -ENOENT) 708 goto fail_unlock; 709 710 if (ret == -EFBIG) { 711 u32 item_size; 712 /* we found one, but it isn't big enough yet */ 713 leaf = path->nodes[0]; 714 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 715 if ((item_size / csum_size) >= 716 MAX_CSUM_ITEMS(root, csum_size)) { 717 /* already at max size, make a new one */ 718 goto insert; 719 } 720 } else { 721 int slot = path->slots[0] + 1; 722 /* we didn't find a csum item, insert one */ 723 nritems = btrfs_header_nritems(path->nodes[0]); 724 if (path->slots[0] >= nritems - 1) { 725 ret = btrfs_next_leaf(root, path); 726 if (ret == 1) 727 found_next = 1; 728 if (ret != 0) 729 goto insert; 730 slot = 0; 731 } 732 btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot); 733 if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID || 734 found_key.type != BTRFS_EXTENT_CSUM_KEY) { 735 found_next = 1; 736 goto insert; 737 } 738 next_offset = found_key.offset; 739 found_next = 1; 740 goto insert; 741 } 742 743 /* 744 * at this point, we know the tree has an item, but it isn't big 745 * enough yet to put our csum in. Grow it 746 */ 747 btrfs_release_path(path); 748 ret = btrfs_search_slot(trans, root, &file_key, path, 749 csum_size, 1); 750 if (ret < 0) 751 goto fail_unlock; 752 753 if (ret > 0) { 754 if (path->slots[0] == 0) 755 goto insert; 756 path->slots[0]--; 757 } 758 759 leaf = path->nodes[0]; 760 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 761 csum_offset = (bytenr - found_key.offset) >> 762 root->fs_info->sb->s_blocksize_bits; 763 764 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY || 765 found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID || 766 csum_offset >= MAX_CSUM_ITEMS(root, csum_size)) { 767 goto insert; 768 } 769 770 if (csum_offset == btrfs_item_size_nr(leaf, path->slots[0]) / 771 csum_size) { 772 int extend_nr; 773 u64 tmp; 774 u32 diff; 775 u32 free_space; 776 777 if (btrfs_leaf_free_space(root, leaf) < 778 sizeof(struct btrfs_item) + csum_size * 2) 779 goto insert; 780 781 free_space = btrfs_leaf_free_space(root, leaf) - 782 sizeof(struct btrfs_item) - csum_size; 783 tmp = sums->len - total_bytes; 784 tmp >>= root->fs_info->sb->s_blocksize_bits; 785 WARN_ON(tmp < 1); 786 787 extend_nr = max_t(int, 1, (int)tmp); 788 diff = (csum_offset + extend_nr) * csum_size; 789 diff = min(diff, MAX_CSUM_ITEMS(root, csum_size) * csum_size); 790 791 diff = diff - btrfs_item_size_nr(leaf, path->slots[0]); 792 diff = min(free_space, diff); 793 diff /= csum_size; 794 diff *= csum_size; 795 796 btrfs_extend_item(root, path, diff); 797 ret = 0; 798 goto csum; 799 } 800 801 insert: 802 btrfs_release_path(path); 803 csum_offset = 0; 804 if (found_next) { 805 u64 tmp; 806 807 tmp = sums->len - total_bytes; 808 tmp >>= root->fs_info->sb->s_blocksize_bits; 809 tmp = min(tmp, (next_offset - file_key.offset) >> 810 root->fs_info->sb->s_blocksize_bits); 811 812 tmp = max((u64)1, tmp); 813 tmp = min(tmp, (u64)MAX_CSUM_ITEMS(root, csum_size)); 814 ins_size = csum_size * tmp; 815 } else { 816 ins_size = csum_size; 817 } 818 path->leave_spinning = 1; 819 ret = btrfs_insert_empty_item(trans, root, path, &file_key, 820 ins_size); 821 path->leave_spinning = 0; 822 if (ret < 0) 823 goto fail_unlock; 824 if (ret != 0) { 825 WARN_ON(1); 826 goto fail_unlock; 827 } 828 leaf = path->nodes[0]; 829 csum: 830 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item); 831 item_end = (struct btrfs_csum_item *)((unsigned char *)item + 832 btrfs_item_size_nr(leaf, path->slots[0])); 833 item = (struct btrfs_csum_item *)((unsigned char *)item + 834 csum_offset * csum_size); 835 found: 836 ins_size = (u32)(sums->len - total_bytes) >> 837 root->fs_info->sb->s_blocksize_bits; 838 ins_size *= csum_size; 839 ins_size = min_t(u32, (unsigned long)item_end - (unsigned long)item, 840 ins_size); 841 write_extent_buffer(leaf, sums->sums + index, (unsigned long)item, 842 ins_size); 843 844 ins_size /= csum_size; 845 total_bytes += ins_size * root->sectorsize; 846 index += ins_size; 847 848 btrfs_mark_buffer_dirty(path->nodes[0]); 849 if (total_bytes < sums->len) { 850 btrfs_release_path(path); 851 cond_resched(); 852 goto again; 853 } 854 out: 855 btrfs_free_path(path); 856 return ret; 857 858 fail_unlock: 859 goto out; 860 } 861