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