fs/btrfs/file-item.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2007 Oracle.  All rights reserved.
   4  */
   5
   6 #include <linux/bio.h>
   7 #include <linux/slab.h>
   8 #include <linux/pagemap.h>
   9 #include <linux/highmem.h>
  10 #include <linux/sched/mm.h>
  11 #include <crypto/hash.h>
  12 #include "messages.h"
  13 #include "misc.h"
  14 #include "ctree.h"
  15 #include "disk-io.h"
  16 #include "transaction.h"
  17 #include "bio.h"
  18 #include "print-tree.h"
  19 #include "compression.h"
  20 #include "fs.h"
  21 #include "accessors.h"
  22 #include "file-item.h"
  23 #include "super.h"
  24
  25 #define __MAX_CSUM_ITEMS(r, size) ((unsigned long)(((BTRFS_LEAF_DATA_SIZE(r) - \
  26                                    sizeof(struct btrfs_item) * 2) / \
  27                                   size) - 1))
  28
  29 #define MAX_CSUM_ITEMS(r, size) (min_t(u32, __MAX_CSUM_ITEMS(r, size), \
  30                                        PAGE_SIZE))
  31
  32 /*
  33  * Set inode's size according to filesystem options.
  34  *
  35  * @inode:      inode we want to update the disk_i_size for
  36  * @new_i_size: i_size we want to set to, 0 if we use i_size
  37  *
  38  * With NO_HOLES set this simply sets the disk_is_size to whatever i_size_read()
  39  * returns as it is perfectly fine with a file that has holes without hole file
  40  * extent items.
  41  *
  42  * However without NO_HOLES we need to only return the area that is contiguous
  43  * from the 0 offset of the file.  Otherwise we could end up adjust i_size up
  44  * to an extent that has a gap in between.
  45  *
  46  * Finally new_i_size should only be set in the case of truncate where we're not
  47  * ready to use i_size_read() as the limiter yet.
  48  */
  49 void btrfs_inode_safe_disk_i_size_write(struct btrfs_inode *inode, u64 new_i_size)
  50 {
  51         struct btrfs_fs_info *fs_info = inode->root->fs_info;
  52         u64 start, end, i_size;
  53         int ret;
  54
  55         i_size = new_i_size ?: i_size_read(&inode->vfs_inode);
  56         if (btrfs_fs_incompat(fs_info, NO_HOLES)) {
  57                 inode->disk_i_size = i_size;
  58                 return;
  59         }
  60
  61         spin_lock(&inode->lock);
  62         ret = find_contiguous_extent_bit(&inode->file_extent_tree, 0, &start,
  63                                          &end, EXTENT_DIRTY);
  64         if (!ret && start == 0)
  65                 i_size = min(i_size, end + 1);
  66         else
  67                 i_size = 0;
  68         inode->disk_i_size = i_size;
  69         spin_unlock(&inode->lock);
  70 }
  71
  72 /*
  73  * Mark range within a file as having a new extent inserted.
  74  *
  75  * @inode: inode being modified
  76  * @start: start file offset of the file extent we've inserted
  77  * @len:   logical length of the file extent item
  78  *
  79  * Call when we are inserting a new file extent where there was none before.
  80  * Does not need to call this in the case where we're replacing an existing file
  81  * extent, however if not sure it's fine to call this multiple times.
  82  *
  83  * The start and len must match the file extent item, so thus must be sectorsize
  84  * aligned.
  85  */
  86 int btrfs_inode_set_file_extent_range(struct btrfs_inode *inode, u64 start,
  87                                       u64 len)
  88 {
  89         if (len == 0)
  90                 return 0;
  91
  92         ASSERT(IS_ALIGNED(start + len, inode->root->fs_info->sectorsize));
  93
  94         if (btrfs_fs_incompat(inode->root->fs_info, NO_HOLES))
  95                 return 0;
  96         return set_extent_bits(&inode->file_extent_tree, start, start + len - 1,
  97                                EXTENT_DIRTY);
  98 }
  99
 100 /*
 101  * Mark an inode range as not having a backing extent.
 102  *
 103  * @inode: inode being modified
 104  * @start: start file offset of the file extent we've inserted
 105  * @len:   logical length of the file extent item
 106  *
 107  * Called when we drop a file extent, for example when we truncate.  Doesn't
 108  * need to be called for cases where we're replacing a file extent, like when
 109  * we've COWed a file extent.
 110  *
 111  * The start and len must match the file extent item, so thus must be sectorsize
 112  * aligned.
 113  */
 114 int btrfs_inode_clear_file_extent_range(struct btrfs_inode *inode, u64 start,
 115                                         u64 len)
 116 {
 117         if (len == 0)
 118                 return 0;
 119
 120         ASSERT(IS_ALIGNED(start + len, inode->root->fs_info->sectorsize) ||
 121                len == (u64)-1);
 122
 123         if (btrfs_fs_incompat(inode->root->fs_info, NO_HOLES))
 124                 return 0;
 125         return clear_extent_bit(&inode->file_extent_tree, start,
 126                                 start + len - 1, EXTENT_DIRTY, NULL);
 127 }
 128
 129 static size_t bytes_to_csum_size(const struct btrfs_fs_info *fs_info, u32 bytes)
 130 {
 131         ASSERT(IS_ALIGNED(bytes, fs_info->sectorsize));
 132
 133         return (bytes >> fs_info->sectorsize_bits) * fs_info->csum_size;
 134 }
 135
 136 static size_t csum_size_to_bytes(const struct btrfs_fs_info *fs_info, u32 csum_size)
 137 {
 138         ASSERT(IS_ALIGNED(csum_size, fs_info->csum_size));
 139
 140         return (csum_size / fs_info->csum_size) << fs_info->sectorsize_bits;
 141 }
 142
 143 static inline u32 max_ordered_sum_bytes(const struct btrfs_fs_info *fs_info)
 144 {
 145         u32 max_csum_size = round_down(PAGE_SIZE - sizeof(struct btrfs_ordered_sum),
 146                                        fs_info->csum_size);
 147
 148         return csum_size_to_bytes(fs_info, max_csum_size);
 149 }
 150
 151 /*
 152  * Calculate the total size needed to allocate for an ordered sum structure
 153  * spanning @bytes in the file.
 154  */
 155 static int btrfs_ordered_sum_size(struct btrfs_fs_info *fs_info, unsigned long bytes)
 156 {
 157         return sizeof(struct btrfs_ordered_sum) + bytes_to_csum_size(fs_info, bytes);
 158 }
 159
 160 int btrfs_insert_hole_extent(struct btrfs_trans_handle *trans,
 161                              struct btrfs_root *root,
 162                              u64 objectid, u64 pos, u64 num_bytes)
 163 {
 164         int ret = 0;
 165         struct btrfs_file_extent_item *item;
 166         struct btrfs_key file_key;
 167         struct btrfs_path *path;
 168         struct extent_buffer *leaf;
 169
 170         path = btrfs_alloc_path();
 171         if (!path)
 172                 return -ENOMEM;
 173         file_key.objectid = objectid;
 174         file_key.offset = pos;
 175         file_key.type = BTRFS_EXTENT_DATA_KEY;
 176
 177         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
 178                                       sizeof(*item));
 179         if (ret < 0)
 180                 goto out;
 181         BUG_ON(ret); /* Can't happen */
 182         leaf = path->nodes[0];
 183         item = btrfs_item_ptr(leaf, path->slots[0],
 184                               struct btrfs_file_extent_item);
 185         btrfs_set_file_extent_disk_bytenr(leaf, item, 0);
 186         btrfs_set_file_extent_disk_num_bytes(leaf, item, 0);
 187         btrfs_set_file_extent_offset(leaf, item, 0);
 188         btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
 189         btrfs_set_file_extent_ram_bytes(leaf, item, num_bytes);
 190         btrfs_set_file_extent_generation(leaf, item, trans->transid);
 191         btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
 192         btrfs_set_file_extent_compression(leaf, item, 0);
 193         btrfs_set_file_extent_encryption(leaf, item, 0);
 194         btrfs_set_file_extent_other_encoding(leaf, item, 0);
 195
 196         btrfs_mark_buffer_dirty(leaf);
 197 out:
 198         btrfs_free_path(path);
 199         return ret;
 200 }
 201
 202 static struct btrfs_csum_item *
 203 btrfs_lookup_csum(struct btrfs_trans_handle *trans,
 204                   struct btrfs_root *root,
 205                   struct btrfs_path *path,
 206                   u64 bytenr, int cow)
 207 {
 208         struct btrfs_fs_info *fs_info = root->fs_info;
 209         int ret;
 210         struct btrfs_key file_key;
 211         struct btrfs_key found_key;
 212         struct btrfs_csum_item *item;
 213         struct extent_buffer *leaf;
 214         u64 csum_offset = 0;
 215         const u32 csum_size = fs_info->csum_size;
 216         int csums_in_item;
 217
 218         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 219         file_key.offset = bytenr;
 220         file_key.type = BTRFS_EXTENT_CSUM_KEY;
 221         ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow);
 222         if (ret < 0)
 223                 goto fail;
 224         leaf = path->nodes[0];
 225         if (ret > 0) {
 226                 ret = 1;
 227                 if (path->slots[0] == 0)
 228                         goto fail;
 229                 path->slots[0]--;
 230                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 231                 if (found_key.type != BTRFS_EXTENT_CSUM_KEY)
 232                         goto fail;
 233
 234                 csum_offset = (bytenr - found_key.offset) >>
 235                                 fs_info->sectorsize_bits;
 236                 csums_in_item = btrfs_item_size(leaf, path->slots[0]);
 237                 csums_in_item /= csum_size;
 238
 239                 if (csum_offset == csums_in_item) {
 240                         ret = -EFBIG;
 241                         goto fail;
 242                 } else if (csum_offset > csums_in_item) {
 243                         goto fail;
 244                 }
 245         }
 246         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
 247         item = (struct btrfs_csum_item *)((unsigned char *)item +
 248                                           csum_offset * csum_size);
 249         return item;
 250 fail:
 251         if (ret > 0)
 252                 ret = -ENOENT;
 253         return ERR_PTR(ret);
 254 }
 255
 256 int btrfs_lookup_file_extent(struct btrfs_trans_handle *trans,
 257                              struct btrfs_root *root,
 258                              struct btrfs_path *path, u64 objectid,
 259                              u64 offset, int mod)
 260 {
 261         struct btrfs_key file_key;
 262         int ins_len = mod < 0 ? -1 : 0;
 263         int cow = mod != 0;
 264
 265         file_key.objectid = objectid;
 266         file_key.offset = offset;
 267         file_key.type = BTRFS_EXTENT_DATA_KEY;
 268
 269         return btrfs_search_slot(trans, root, &file_key, path, ins_len, cow);
 270 }
 271
 272 /*
 273  * Find checksums for logical bytenr range [disk_bytenr, disk_bytenr + len) and
 274  * store the result to @dst.
 275  *
 276  * Return >0 for the number of sectors we found.
 277  * Return 0 for the range [disk_bytenr, disk_bytenr + sectorsize) has no csum
 278  * for it. Caller may want to try next sector until one range is hit.
 279  * Return <0 for fatal error.
 280  */
 281 static int search_csum_tree(struct btrfs_fs_info *fs_info,
 282                             struct btrfs_path *path, u64 disk_bytenr,
 283                             u64 len, u8 *dst)
 284 {
 285         struct btrfs_root *csum_root;
 286         struct btrfs_csum_item *item = NULL;
 287         struct btrfs_key key;
 288         const u32 sectorsize = fs_info->sectorsize;
 289         const u32 csum_size = fs_info->csum_size;
 290         u32 itemsize;
 291         int ret;
 292         u64 csum_start;
 293         u64 csum_len;
 294
 295         ASSERT(IS_ALIGNED(disk_bytenr, sectorsize) &&
 296                IS_ALIGNED(len, sectorsize));
 297
 298         /* Check if the current csum item covers disk_bytenr */
 299         if (path->nodes[0]) {
 300                 item = btrfs_item_ptr(path->nodes[0], path->slots[0],
 301                                       struct btrfs_csum_item);
 302                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 303                 itemsize = btrfs_item_size(path->nodes[0], path->slots[0]);
 304
 305                 csum_start = key.offset;
 306                 csum_len = (itemsize / csum_size) * sectorsize;
 307
 308                 if (in_range(disk_bytenr, csum_start, csum_len))
 309                         goto found;
 310         }
 311
 312         /* Current item doesn't contain the desired range, search again */
 313         btrfs_release_path(path);
 314         csum_root = btrfs_csum_root(fs_info, disk_bytenr);
 315         item = btrfs_lookup_csum(NULL, csum_root, path, disk_bytenr, 0);
 316         if (IS_ERR(item)) {
 317                 ret = PTR_ERR(item);
 318                 goto out;
 319         }
 320         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 321         itemsize = btrfs_item_size(path->nodes[0], path->slots[0]);
 322
 323         csum_start = key.offset;
 324         csum_len = (itemsize / csum_size) * sectorsize;
 325         ASSERT(in_range(disk_bytenr, csum_start, csum_len));
 326
 327 found:
 328         ret = (min(csum_start + csum_len, disk_bytenr + len) -
 329                    disk_bytenr) >> fs_info->sectorsize_bits;
 330         read_extent_buffer(path->nodes[0], dst, (unsigned long)item,
 331                         ret * csum_size);
 332 out:
 333         if (ret == -ENOENT || ret == -EFBIG)
 334                 ret = 0;
 335         return ret;
 336 }
 337
 338 /*
 339  * Locate the file_offset of @cur_disk_bytenr of a @bio.
 340  *
 341  * Bio of btrfs represents read range of
 342  * [bi_sector << 9, bi_sector << 9 + bi_size).
 343  * Knowing this, we can iterate through each bvec to locate the page belong to
 344  * @cur_disk_bytenr and get the file offset.
 345  *
 346  * @inode is used to determine if the bvec page really belongs to @inode.
 347  *
 348  * Return 0 if we can't find the file offset
 349  * Return >0 if we find the file offset and restore it to @file_offset_ret
 350  */
 351 static int search_file_offset_in_bio(struct bio *bio, struct inode *inode,
 352                                      u64 disk_bytenr, u64 *file_offset_ret)
 353 {
 354         struct bvec_iter iter;
 355         struct bio_vec bvec;
 356         u64 cur = bio->bi_iter.bi_sector << SECTOR_SHIFT;
 357         int ret = 0;
 358
 359         bio_for_each_segment(bvec, bio, iter) {
 360                 struct page *page = bvec.bv_page;
 361
 362                 if (cur > disk_bytenr)
 363                         break;
 364                 if (cur + bvec.bv_len <= disk_bytenr) {
 365                         cur += bvec.bv_len;
 366                         continue;
 367                 }
 368                 ASSERT(in_range(disk_bytenr, cur, bvec.bv_len));
 369                 if (page->mapping && page->mapping->host &&
 370                     page->mapping->host == inode) {
 371                         ret = 1;
 372                         *file_offset_ret = page_offset(page) + bvec.bv_offset +
 373                                            disk_bytenr - cur;
 374                         break;
 375                 }
 376         }
 377         return ret;
 378 }
 379
 380 /*
 381  * Lookup the checksum for the read bio in csum tree.
 382  *
 383  * Return: BLK_STS_RESOURCE if allocating memory fails, BLK_STS_OK otherwise.
 384  */
 385 blk_status_t btrfs_lookup_bio_sums(struct btrfs_bio *bbio)
 386 {
 387         struct btrfs_inode *inode = bbio->inode;
 388         struct btrfs_fs_info *fs_info = inode->root->fs_info;
 389         struct extent_io_tree *io_tree = &inode->io_tree;
 390         struct bio *bio = &bbio->bio;
 391         struct btrfs_path *path;
 392         const u32 sectorsize = fs_info->sectorsize;
 393         const u32 csum_size = fs_info->csum_size;
 394         u32 orig_len = bio->bi_iter.bi_size;
 395         u64 orig_disk_bytenr = bio->bi_iter.bi_sector << SECTOR_SHIFT;
 396         u64 cur_disk_bytenr;
 397         const unsigned int nblocks = orig_len >> fs_info->sectorsize_bits;
 398         int count = 0;
 399         blk_status_t ret = BLK_STS_OK;
 400
 401         if ((inode->flags & BTRFS_INODE_NODATASUM) ||
 402             test_bit(BTRFS_FS_STATE_NO_CSUMS, &fs_info->fs_state))
 403                 return BLK_STS_OK;
 404
 405         /*
 406          * This function is only called for read bio.
 407          *
 408          * This means two things:
 409          * - All our csums should only be in csum tree
 410          *   No ordered extents csums, as ordered extents are only for write
 411          *   path.
 412          * - No need to bother any other info from bvec
 413          *   Since we're looking up csums, the only important info is the
 414          *   disk_bytenr and the length, which can be extracted from bi_iter
 415          *   directly.
 416          */
 417         ASSERT(bio_op(bio) == REQ_OP_READ);
 418         path = btrfs_alloc_path();
 419         if (!path)
 420                 return BLK_STS_RESOURCE;
 421
 422         if (nblocks * csum_size > BTRFS_BIO_INLINE_CSUM_SIZE) {
 423                 bbio->csum = kmalloc_array(nblocks, csum_size, GFP_NOFS);
 424                 if (!bbio->csum) {
 425                         btrfs_free_path(path);
 426                         return BLK_STS_RESOURCE;
 427                 }
 428         } else {
 429                 bbio->csum = bbio->csum_inline;
 430         }
 431
 432         /*
 433          * If requested number of sectors is larger than one leaf can contain,
 434          * kick the readahead for csum tree.
 435          */
 436         if (nblocks > fs_info->csums_per_leaf)
 437                 path->reada = READA_FORWARD;
 438
 439         /*
 440          * the free space stuff is only read when it hasn't been
 441          * updated in the current transaction.  So, we can safely
 442          * read from the commit root and sidestep a nasty deadlock
 443          * between reading the free space cache and updating the csum tree.
 444          */
 445         if (btrfs_is_free_space_inode(inode)) {
 446                 path->search_commit_root = 1;
 447                 path->skip_locking = 1;
 448         }
 449
 450         for (cur_disk_bytenr = orig_disk_bytenr;
 451              cur_disk_bytenr < orig_disk_bytenr + orig_len;
 452              cur_disk_bytenr += (count * sectorsize)) {
 453                 u64 search_len = orig_disk_bytenr + orig_len - cur_disk_bytenr;
 454                 unsigned int sector_offset;
 455                 u8 *csum_dst;
 456
 457                 /*
 458                  * Although both cur_disk_bytenr and orig_disk_bytenr is u64,
 459                  * we're calculating the offset to the bio start.
 460                  *
 461                  * Bio size is limited to UINT_MAX, thus unsigned int is large
 462                  * enough to contain the raw result, not to mention the right
 463                  * shifted result.
 464                  */
 465                 ASSERT(cur_disk_bytenr - orig_disk_bytenr < UINT_MAX);
 466                 sector_offset = (cur_disk_bytenr - orig_disk_bytenr) >>
 467                                 fs_info->sectorsize_bits;
 468                 csum_dst = bbio->csum + sector_offset * csum_size;
 469
 470                 count = search_csum_tree(fs_info, path, cur_disk_bytenr,
 471                                          search_len, csum_dst);
 472                 if (count < 0) {
 473                         ret = errno_to_blk_status(count);
 474                         if (bbio->csum != bbio->csum_inline)
 475                                 kfree(bbio->csum);
 476                         bbio->csum = NULL;
 477                         break;
 478                 }
 479
 480                 /*
 481                  * We didn't find a csum for this range.  We need to make sure
 482                  * we complain loudly about this, because we are not NODATASUM.
 483                  *
 484                  * However for the DATA_RELOC inode we could potentially be
 485                  * relocating data extents for a NODATASUM inode, so the inode
 486                  * itself won't be marked with NODATASUM, but the extent we're
 487                  * copying is in fact NODATASUM.  If we don't find a csum we
 488                  * assume this is the case.
 489                  */
 490                 if (count == 0) {
 491                         memset(csum_dst, 0, csum_size);
 492                         count = 1;
 493
 494                         if (inode->root->root_key.objectid ==
 495                             BTRFS_DATA_RELOC_TREE_OBJECTID) {
 496                                 u64 file_offset;
 497                                 int ret;
 498
 499                                 ret = search_file_offset_in_bio(bio,
 500                                                 &inode->vfs_inode,
 501                                                 cur_disk_bytenr, &file_offset);
 502                                 if (ret)
 503                                         set_extent_bits(io_tree, file_offset,
 504                                                 file_offset + sectorsize - 1,
 505                                                 EXTENT_NODATASUM);
 506                         } else {
 507                                 btrfs_warn_rl(fs_info,
 508                         "csum hole found for disk bytenr range [%llu, %llu)",
 509                                 cur_disk_bytenr, cur_disk_bytenr + sectorsize);
 510                         }
 511                 }
 512         }
 513
 514         btrfs_free_path(path);
 515         return ret;
 516 }
 517
 518 int btrfs_lookup_csums_list(struct btrfs_root *root, u64 start, u64 end,
 519                             struct list_head *list, int search_commit,
 520                             bool nowait)
 521 {
 522         struct btrfs_fs_info *fs_info = root->fs_info;
 523         struct btrfs_key key;
 524         struct btrfs_path *path;
 525         struct extent_buffer *leaf;
 526         struct btrfs_ordered_sum *sums;
 527         struct btrfs_csum_item *item;
 528         LIST_HEAD(tmplist);
 529         int ret;
 530
 531         ASSERT(IS_ALIGNED(start, fs_info->sectorsize) &&
 532                IS_ALIGNED(end + 1, fs_info->sectorsize));
 533
 534         path = btrfs_alloc_path();
 535         if (!path)
 536                 return -ENOMEM;
 537
 538         path->nowait = nowait;
 539         if (search_commit) {
 540                 path->skip_locking = 1;
 541                 path->reada = READA_FORWARD;
 542                 path->search_commit_root = 1;
 543         }
 544
 545         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 546         key.offset = start;
 547         key.type = BTRFS_EXTENT_CSUM_KEY;
 548
 549         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 550         if (ret < 0)
 551                 goto fail;
 552         if (ret > 0 && path->slots[0] > 0) {
 553                 leaf = path->nodes[0];
 554                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
 555
 556                 /*
 557                  * There are two cases we can hit here for the previous csum
 558                  * item:
 559                  *
 560                  *              |<- search range ->|
 561                  *      |<- csum item ->|
 562                  *
 563                  * Or
 564                  *                              |<- search range ->|
 565                  *      |<- csum item ->|
 566                  *
 567                  * Check if the previous csum item covers the leading part of
 568                  * the search range.  If so we have to start from previous csum
 569                  * item.
 570                  */
 571                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
 572                     key.type == BTRFS_EXTENT_CSUM_KEY) {
 573                         if (bytes_to_csum_size(fs_info, start - key.offset) <
 574                             btrfs_item_size(leaf, path->slots[0] - 1))
 575                                 path->slots[0]--;
 576                 }
 577         }
 578
 579         while (start <= end) {
 580                 u64 csum_end;
 581
 582                 leaf = path->nodes[0];
 583                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 584                         ret = btrfs_next_leaf(root, path);
 585                         if (ret < 0)
 586                                 goto fail;
 587                         if (ret > 0)
 588                                 break;
 589                         leaf = path->nodes[0];
 590                 }
 591
 592                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 593                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
 594                     key.type != BTRFS_EXTENT_CSUM_KEY ||
 595                     key.offset > end)
 596                         break;
 597
 598                 if (key.offset > start)
 599                         start = key.offset;
 600
 601                 csum_end = key.offset + csum_size_to_bytes(fs_info,
 602                                         btrfs_item_size(leaf, path->slots[0]));
 603                 if (csum_end <= start) {
 604                         path->slots[0]++;
 605                         continue;
 606                 }
 607
 608                 csum_end = min(csum_end, end + 1);
 609                 item = btrfs_item_ptr(path->nodes[0], path->slots[0],
 610                                       struct btrfs_csum_item);
 611                 while (start < csum_end) {
 612                         unsigned long offset;
 613                         size_t size;
 614
 615                         size = min_t(size_t, csum_end - start,
 616                                      max_ordered_sum_bytes(fs_info));
 617                         sums = kzalloc(btrfs_ordered_sum_size(fs_info, size),
 618                                        GFP_NOFS);
 619                         if (!sums) {
 620                                 ret = -ENOMEM;
 621                                 goto fail;
 622                         }
 623
 624                         sums->bytenr = start;
 625                         sums->len = (int)size;
 626
 627                         offset = bytes_to_csum_size(fs_info, start - key.offset);
 628
 629                         read_extent_buffer(path->nodes[0],
 630                                            sums->sums,
 631                                            ((unsigned long)item) + offset,
 632                                            bytes_to_csum_size(fs_info, size));
 633
 634                         start += size;
 635                         list_add_tail(&sums->list, &tmplist);
 636                 }
 637                 path->slots[0]++;
 638         }
 639         ret = 0;
 640 fail:
 641         while (ret < 0 && !list_empty(&tmplist)) {
 642                 sums = list_entry(tmplist.next, struct btrfs_ordered_sum, list);
 643                 list_del(&sums->list);
 644                 kfree(sums);
 645         }
 646         list_splice_tail(&tmplist, list);
 647
 648         btrfs_free_path(path);
 649         return ret;
 650 }
 651
 652 /*
 653  * Do the same work as btrfs_lookup_csums_list(), the difference is in how
 654  * we return the result.
 655  *
 656  * This version will set the corresponding bits in @csum_bitmap to represent
 657  * that there is a csum found.
 658  * Each bit represents a sector. Thus caller should ensure @csum_buf passed
 659  * in is large enough to contain all csums.
 660  */
 661 int btrfs_lookup_csums_bitmap(struct btrfs_root *root, u64 start, u64 end,
 662                               u8 *csum_buf, unsigned long *csum_bitmap)
 663 {
 664         struct btrfs_fs_info *fs_info = root->fs_info;
 665         struct btrfs_key key;
 666         struct btrfs_path *path;
 667         struct extent_buffer *leaf;
 668         struct btrfs_csum_item *item;
 669         const u64 orig_start = start;
 670         int ret;
 671
 672         ASSERT(IS_ALIGNED(start, fs_info->sectorsize) &&
 673                IS_ALIGNED(end + 1, fs_info->sectorsize));
 674
 675         path = btrfs_alloc_path();
 676         if (!path)
 677                 return -ENOMEM;
 678
 679         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 680         key.type = BTRFS_EXTENT_CSUM_KEY;
 681         key.offset = start;
 682
 683         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 684         if (ret < 0)
 685                 goto fail;
 686         if (ret > 0 && path->slots[0] > 0) {
 687                 leaf = path->nodes[0];
 688                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
 689
 690                 /*
 691                  * There are two cases we can hit here for the previous csum
 692                  * item:
 693                  *
 694                  *              |<- search range ->|
 695                  *      |<- csum item ->|
 696                  *
 697                  * Or
 698                  *                              |<- search range ->|
 699                  *      |<- csum item ->|
 700                  *
 701                  * Check if the previous csum item covers the leading part of
 702                  * the search range.  If so we have to start from previous csum
 703                  * item.
 704                  */
 705                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
 706                     key.type == BTRFS_EXTENT_CSUM_KEY) {
 707                         if (bytes_to_csum_size(fs_info, start - key.offset) <
 708                             btrfs_item_size(leaf, path->slots[0] - 1))
 709                                 path->slots[0]--;
 710                 }
 711         }
 712
 713         while (start <= end) {
 714                 u64 csum_end;
 715
 716                 leaf = path->nodes[0];
 717                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 718                         ret = btrfs_next_leaf(root, path);
 719                         if (ret < 0)
 720                                 goto fail;
 721                         if (ret > 0)
 722                                 break;
 723                         leaf = path->nodes[0];
 724                 }
 725
 726                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 727                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
 728                     key.type != BTRFS_EXTENT_CSUM_KEY ||
 729                     key.offset > end)
 730                         break;
 731
 732                 if (key.offset > start)
 733                         start = key.offset;
 734
 735                 csum_end = key.offset + csum_size_to_bytes(fs_info,
 736                                         btrfs_item_size(leaf, path->slots[0]));
 737                 if (csum_end <= start) {
 738                         path->slots[0]++;
 739                         continue;
 740                 }
 741
 742                 csum_end = min(csum_end, end + 1);
 743                 item = btrfs_item_ptr(path->nodes[0], path->slots[0],
 744                                       struct btrfs_csum_item);
 745                 while (start < csum_end) {
 746                         unsigned long offset;
 747                         size_t size;
 748                         u8 *csum_dest = csum_buf + bytes_to_csum_size(fs_info,
 749                                                 start - orig_start);
 750
 751                         size = min_t(size_t, csum_end - start, end + 1 - start);
 752
 753                         offset = bytes_to_csum_size(fs_info, start - key.offset);
 754
 755                         read_extent_buffer(path->nodes[0], csum_dest,
 756                                            ((unsigned long)item) + offset,
 757                                            bytes_to_csum_size(fs_info, size));
 758
 759                         bitmap_set(csum_bitmap,
 760                                 (start - orig_start) >> fs_info->sectorsize_bits,
 761                                 size >> fs_info->sectorsize_bits);
 762
 763                         start += size;
 764                 }
 765                 path->slots[0]++;
 766         }
 767         ret = 0;
 768 fail:
 769         btrfs_free_path(path);
 770         return ret;
 771 }
 772
 773 /*
 774  * Calculate checksums of the data contained inside a bio.
 775  */
 776 blk_status_t btrfs_csum_one_bio(struct btrfs_bio *bbio)
 777 {
 778         struct btrfs_inode *inode = bbio->inode;
 779         struct btrfs_fs_info *fs_info = inode->root->fs_info;
 780         SHASH_DESC_ON_STACK(shash, fs_info->csum_shash);
 781         struct bio *bio = &bbio->bio;
 782         u64 offset = bbio->file_offset;
 783         struct btrfs_ordered_sum *sums;
 784         struct btrfs_ordered_extent *ordered = NULL;
 785         char *data;
 786         struct bvec_iter iter;
 787         struct bio_vec bvec;
 788         int index;
 789         unsigned int blockcount;
 790         unsigned long total_bytes = 0;
 791         unsigned long this_sum_bytes = 0;
 792         int i;
 793         unsigned nofs_flag;
 794
 795         nofs_flag = memalloc_nofs_save();
 796         sums = kvzalloc(btrfs_ordered_sum_size(fs_info, bio->bi_iter.bi_size),
 797                        GFP_KERNEL);
 798         memalloc_nofs_restore(nofs_flag);
 799
 800         if (!sums)
 801                 return BLK_STS_RESOURCE;
 802
 803         sums->len = bio->bi_iter.bi_size;
 804         INIT_LIST_HEAD(&sums->list);
 805
 806         sums->bytenr = bio->bi_iter.bi_sector << 9;
 807         index = 0;
 808
 809         shash->tfm = fs_info->csum_shash;
 810
 811         bio_for_each_segment(bvec, bio, iter) {
 812                 if (!ordered) {
 813                         ordered = btrfs_lookup_ordered_extent(inode, offset);
 814                         /*
 815                          * The bio range is not covered by any ordered extent,
 816                          * must be a code logic error.
 817                          */
 818                         if (unlikely(!ordered)) {
 819                                 WARN(1, KERN_WARNING
 820                         "no ordered extent for root %llu ino %llu offset %llu\n",
 821                                      inode->root->root_key.objectid,
 822                                      btrfs_ino(inode), offset);
 823                                 kvfree(sums);
 824                                 return BLK_STS_IOERR;
 825                         }
 826                 }
 827
 828                 blockcount = BTRFS_BYTES_TO_BLKS(fs_info,
 829                                                  bvec.bv_len + fs_info->sectorsize
 830                                                  - 1);
 831
 832                 for (i = 0; i < blockcount; i++) {
 833                         if (!(bio->bi_opf & REQ_BTRFS_ONE_ORDERED) &&
 834                             !in_range(offset, ordered->file_offset,
 835                                       ordered->num_bytes)) {
 836                                 unsigned long bytes_left;
 837
 838                                 sums->len = this_sum_bytes;
 839                                 this_sum_bytes = 0;
 840                                 btrfs_add_ordered_sum(ordered, sums);
 841                                 btrfs_put_ordered_extent(ordered);
 842
 843                                 bytes_left = bio->bi_iter.bi_size - total_bytes;
 844
 845                                 nofs_flag = memalloc_nofs_save();
 846                                 sums = kvzalloc(btrfs_ordered_sum_size(fs_info,
 847                                                       bytes_left), GFP_KERNEL);
 848                                 memalloc_nofs_restore(nofs_flag);
 849                                 BUG_ON(!sums); /* -ENOMEM */
 850                                 sums->len = bytes_left;
 851                                 ordered = btrfs_lookup_ordered_extent(inode,
 852                                                                 offset);
 853                                 ASSERT(ordered); /* Logic error */
 854                                 sums->bytenr = (bio->bi_iter.bi_sector << 9)
 855                                         + total_bytes;
 856                                 index = 0;
 857                         }
 858
 859                         data = bvec_kmap_local(&bvec);
 860                         crypto_shash_digest(shash,
 861                                             data + (i * fs_info->sectorsize),
 862                                             fs_info->sectorsize,
 863                                             sums->sums + index);
 864                         kunmap_local(data);
 865                         index += fs_info->csum_size;
 866                         offset += fs_info->sectorsize;
 867                         this_sum_bytes += fs_info->sectorsize;
 868                         total_bytes += fs_info->sectorsize;
 869                 }
 870
 871         }
 872         this_sum_bytes = 0;
 873         btrfs_add_ordered_sum(ordered, sums);
 874         btrfs_put_ordered_extent(ordered);
 875         return 0;
 876 }
 877
 878 /*
 879  * Remove one checksum overlapping a range.
 880  *
 881  * This expects the key to describe the csum pointed to by the path, and it
 882  * expects the csum to overlap the range [bytenr, len]
 883  *
 884  * The csum should not be entirely contained in the range and the range should
 885  * not be entirely contained in the csum.
 886  *
 887  * This calls btrfs_truncate_item with the correct args based on the overlap,
 888  * and fixes up the key as required.
 889  */
 890 static noinline void truncate_one_csum(struct btrfs_fs_info *fs_info,
 891                                        struct btrfs_path *path,
 892                                        struct btrfs_key *key,
 893                                        u64 bytenr, u64 len)
 894 {
 895         struct extent_buffer *leaf;
 896         const u32 csum_size = fs_info->csum_size;
 897         u64 csum_end;
 898         u64 end_byte = bytenr + len;
 899         u32 blocksize_bits = fs_info->sectorsize_bits;
 900
 901         leaf = path->nodes[0];
 902         csum_end = btrfs_item_size(leaf, path->slots[0]) / csum_size;
 903         csum_end <<= blocksize_bits;
 904         csum_end += key->offset;
 905
 906         if (key->offset < bytenr && csum_end <= end_byte) {
 907                 /*
 908                  *         [ bytenr - len ]
 909                  *         [   ]
 910                  *   [csum     ]
 911                  *   A simple truncate off the end of the item
 912                  */
 913                 u32 new_size = (bytenr - key->offset) >> blocksize_bits;
 914                 new_size *= csum_size;
 915                 btrfs_truncate_item(path, new_size, 1);
 916         } else if (key->offset >= bytenr && csum_end > end_byte &&
 917                    end_byte > key->offset) {
 918                 /*
 919                  *         [ bytenr - len ]
 920                  *                 [ ]
 921                  *                 [csum     ]
 922                  * we need to truncate from the beginning of the csum
 923                  */
 924                 u32 new_size = (csum_end - end_byte) >> blocksize_bits;
 925                 new_size *= csum_size;
 926
 927                 btrfs_truncate_item(path, new_size, 0);
 928
 929                 key->offset = end_byte;
 930                 btrfs_set_item_key_safe(fs_info, path, key);
 931         } else {
 932                 BUG();
 933         }
 934 }
 935
 936 /*
 937  * Delete the csum items from the csum tree for a given range of bytes.
 938  */
 939 int btrfs_del_csums(struct btrfs_trans_handle *trans,
 940                     struct btrfs_root *root, u64 bytenr, u64 len)
 941 {
 942         struct btrfs_fs_info *fs_info = trans->fs_info;
 943         struct btrfs_path *path;
 944         struct btrfs_key key;
 945         u64 end_byte = bytenr + len;
 946         u64 csum_end;
 947         struct extent_buffer *leaf;
 948         int ret = 0;
 949         const u32 csum_size = fs_info->csum_size;
 950         u32 blocksize_bits = fs_info->sectorsize_bits;
 951
 952         ASSERT(root->root_key.objectid == BTRFS_CSUM_TREE_OBJECTID ||
 953                root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID);
 954
 955         path = btrfs_alloc_path();
 956         if (!path)
 957                 return -ENOMEM;
 958
 959         while (1) {
 960                 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 961                 key.offset = end_byte - 1;
 962                 key.type = BTRFS_EXTENT_CSUM_KEY;
 963
 964                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 965                 if (ret > 0) {
 966                         ret = 0;
 967                         if (path->slots[0] == 0)
 968                                 break;
 969                         path->slots[0]--;
 970                 } else if (ret < 0) {
 971                         break;
 972                 }
 973
 974                 leaf = path->nodes[0];
 975                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 976
 977                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
 978                     key.type != BTRFS_EXTENT_CSUM_KEY) {
 979                         break;
 980                 }
 981
 982                 if (key.offset >= end_byte)
 983                         break;
 984
 985                 csum_end = btrfs_item_size(leaf, path->slots[0]) / csum_size;
 986                 csum_end <<= blocksize_bits;
 987                 csum_end += key.offset;
 988
 989                 /* this csum ends before we start, we're done */
 990                 if (csum_end <= bytenr)
 991                         break;
 992
 993                 /* delete the entire item, it is inside our range */
 994                 if (key.offset >= bytenr && csum_end <= end_byte) {
 995                         int del_nr = 1;
 996
 997                         /*
 998                          * Check how many csum items preceding this one in this
 999                          * leaf correspond to our range and then delete them all
1000                          * at once.
1001                          */
1002                         if (key.offset > bytenr && path->slots[0] > 0) {
1003                                 int slot = path->slots[0] - 1;
1004
1005                                 while (slot >= 0) {
1006                                         struct btrfs_key pk;
1007
1008                                         btrfs_item_key_to_cpu(leaf, &pk, slot);
1009                                         if (pk.offset < bytenr ||
1010                                             pk.type != BTRFS_EXTENT_CSUM_KEY ||
1011                                             pk.objectid !=
1012                                             BTRFS_EXTENT_CSUM_OBJECTID)
1013                                                 break;
1014                                         path->slots[0] = slot;
1015                                         del_nr++;
1016                                         key.offset = pk.offset;
1017                                         slot--;
1018                                 }
1019                         }
1020                         ret = btrfs_del_items(trans, root, path,
1021                                               path->slots[0], del_nr);
1022                         if (ret)
1023                                 break;
1024                         if (key.offset == bytenr)
1025                                 break;
1026                 } else if (key.offset < bytenr && csum_end > end_byte) {
1027                         unsigned long offset;
1028                         unsigned long shift_len;
1029                         unsigned long item_offset;
1030                         /*
1031                          *        [ bytenr - len ]
1032                          *     [csum                ]
1033                          *
1034                          * Our bytes are in the middle of the csum,
1035                          * we need to split this item and insert a new one.
1036                          *
1037                          * But we can't drop the path because the
1038                          * csum could change, get removed, extended etc.
1039                          *
1040                          * The trick here is the max size of a csum item leaves
1041                          * enough room in the tree block for a single
1042                          * item header.  So, we split the item in place,
1043                          * adding a new header pointing to the existing
1044                          * bytes.  Then we loop around again and we have
1045                          * a nicely formed csum item that we can neatly
1046                          * truncate.
1047                          */
1048                         offset = (bytenr - key.offset) >> blocksize_bits;
1049                         offset *= csum_size;
1050
1051                         shift_len = (len >> blocksize_bits) * csum_size;
1052
1053                         item_offset = btrfs_item_ptr_offset(leaf,
1054                                                             path->slots[0]);
1055
1056                         memzero_extent_buffer(leaf, item_offset + offset,
1057                                              shift_len);
1058                         key.offset = bytenr;
1059
1060                         /*
1061                          * btrfs_split_item returns -EAGAIN when the
1062                          * item changed size or key
1063                          */
1064                         ret = btrfs_split_item(trans, root, path, &key, offset);
1065                         if (ret && ret != -EAGAIN) {
1066                                 btrfs_abort_transaction(trans, ret);
1067                                 break;
1068                         }
1069                         ret = 0;
1070
1071                         key.offset = end_byte - 1;
1072                 } else {
1073                         truncate_one_csum(fs_info, path, &key, bytenr, len);
1074                         if (key.offset < bytenr)
1075                                 break;
1076                 }
1077                 btrfs_release_path(path);
1078         }
1079         btrfs_free_path(path);
1080         return ret;
1081 }
1082
1083 static int find_next_csum_offset(struct btrfs_root *root,
1084                                  struct btrfs_path *path,
1085                                  u64 *next_offset)
1086 {
1087         const u32 nritems = btrfs_header_nritems(path->nodes[0]);
1088         struct btrfs_key found_key;
1089         int slot = path->slots[0] + 1;
1090         int ret;
1091
1092         if (nritems == 0 || slot >= nritems) {
1093                 ret = btrfs_next_leaf(root, path);
1094                 if (ret < 0) {
1095                         return ret;
1096                 } else if (ret > 0) {
1097                         *next_offset = (u64)-1;
1098                         return 0;
1099                 }
1100                 slot = path->slots[0];
1101         }
1102
1103         btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
1104
1105         if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
1106             found_key.type != BTRFS_EXTENT_CSUM_KEY)
1107                 *next_offset = (u64)-1;
1108         else
1109                 *next_offset = found_key.offset;
1110
1111         return 0;
1112 }
1113
1114 int btrfs_csum_file_blocks(struct btrfs_trans_handle *trans,
1115                            struct btrfs_root *root,
1116                            struct btrfs_ordered_sum *sums)
1117 {
1118         struct btrfs_fs_info *fs_info = root->fs_info;
1119         struct btrfs_key file_key;
1120         struct btrfs_key found_key;
1121         struct btrfs_path *path;
1122         struct btrfs_csum_item *item;
1123         struct btrfs_csum_item *item_end;
1124         struct extent_buffer *leaf = NULL;
1125         u64 next_offset;
1126         u64 total_bytes = 0;
1127         u64 csum_offset;
1128         u64 bytenr;
1129         u32 ins_size;
1130         int index = 0;
1131         int found_next;
1132         int ret;
1133         const u32 csum_size = fs_info->csum_size;
1134
1135         path = btrfs_alloc_path();
1136         if (!path)
1137                 return -ENOMEM;
1138 again:
1139         next_offset = (u64)-1;
1140         found_next = 0;
1141         bytenr = sums->bytenr + total_bytes;
1142         file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
1143         file_key.offset = bytenr;
1144         file_key.type = BTRFS_EXTENT_CSUM_KEY;
1145
1146         item = btrfs_lookup_csum(trans, root, path, bytenr, 1);
1147         if (!IS_ERR(item)) {
1148                 ret = 0;
1149                 leaf = path->nodes[0];
1150                 item_end = btrfs_item_ptr(leaf, path->slots[0],
1151                                           struct btrfs_csum_item);
1152                 item_end = (struct btrfs_csum_item *)((char *)item_end +
1153                            btrfs_item_size(leaf, path->slots[0]));
1154                 goto found;
1155         }
1156         ret = PTR_ERR(item);
1157         if (ret != -EFBIG && ret != -ENOENT)
1158                 goto out;
1159
1160         if (ret == -EFBIG) {
1161                 u32 item_size;
1162                 /* we found one, but it isn't big enough yet */
1163                 leaf = path->nodes[0];
1164                 item_size = btrfs_item_size(leaf, path->slots[0]);
1165                 if ((item_size / csum_size) >=
1166                     MAX_CSUM_ITEMS(fs_info, csum_size)) {
1167                         /* already at max size, make a new one */
1168                         goto insert;
1169                 }
1170         } else {
1171                 /* We didn't find a csum item, insert one. */
1172                 ret = find_next_csum_offset(root, path, &next_offset);
1173                 if (ret < 0)
1174                         goto out;
1175                 found_next = 1;
1176                 goto insert;
1177         }
1178
1179         /*
1180          * At this point, we know the tree has a checksum item that ends at an
1181          * offset matching the start of the checksum range we want to insert.
1182          * We try to extend that item as much as possible and then add as many
1183          * checksums to it as they fit.
1184          *
1185          * First check if the leaf has enough free space for at least one
1186          * checksum. If it has go directly to the item extension code, otherwise
1187          * release the path and do a search for insertion before the extension.
1188          */
1189         if (btrfs_leaf_free_space(leaf) >= csum_size) {
1190                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1191                 csum_offset = (bytenr - found_key.offset) >>
1192                         fs_info->sectorsize_bits;
1193                 goto extend_csum;
1194         }
1195
1196         btrfs_release_path(path);
1197         path->search_for_extension = 1;
1198         ret = btrfs_search_slot(trans, root, &file_key, path,
1199                                 csum_size, 1);
1200         path->search_for_extension = 0;
1201         if (ret < 0)
1202                 goto out;
1203
1204         if (ret > 0) {
1205                 if (path->slots[0] == 0)
1206                         goto insert;
1207                 path->slots[0]--;
1208         }
1209
1210         leaf = path->nodes[0];
1211         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1212         csum_offset = (bytenr - found_key.offset) >> fs_info->sectorsize_bits;
1213
1214         if (found_key.type != BTRFS_EXTENT_CSUM_KEY ||
1215             found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
1216             csum_offset >= MAX_CSUM_ITEMS(fs_info, csum_size)) {
1217                 goto insert;
1218         }
1219
1220 extend_csum:
1221         if (csum_offset == btrfs_item_size(leaf, path->slots[0]) /
1222             csum_size) {
1223                 int extend_nr;
1224                 u64 tmp;
1225                 u32 diff;
1226
1227                 tmp = sums->len - total_bytes;
1228                 tmp >>= fs_info->sectorsize_bits;
1229                 WARN_ON(tmp < 1);
1230                 extend_nr = max_t(int, 1, tmp);
1231
1232                 /*
1233                  * A log tree can already have checksum items with a subset of
1234                  * the checksums we are trying to log. This can happen after
1235                  * doing a sequence of partial writes into prealloc extents and
1236                  * fsyncs in between, with a full fsync logging a larger subrange
1237                  * of an extent for which a previous fast fsync logged a smaller
1238                  * subrange. And this happens in particular due to merging file
1239                  * extent items when we complete an ordered extent for a range
1240                  * covered by a prealloc extent - this is done at
1241                  * btrfs_mark_extent_written().
1242                  *
1243                  * So if we try to extend the previous checksum item, which has
1244                  * a range that ends at the start of the range we want to insert,
1245                  * make sure we don't extend beyond the start offset of the next
1246                  * checksum item. If we are at the last item in the leaf, then
1247                  * forget the optimization of extending and add a new checksum
1248                  * item - it is not worth the complexity of releasing the path,
1249                  * getting the first key for the next leaf, repeat the btree
1250                  * search, etc, because log trees are temporary anyway and it
1251                  * would only save a few bytes of leaf space.
1252                  */
1253                 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
1254                         if (path->slots[0] + 1 >=
1255                             btrfs_header_nritems(path->nodes[0])) {
1256                                 ret = find_next_csum_offset(root, path, &next_offset);
1257                                 if (ret < 0)
1258                                         goto out;
1259                                 found_next = 1;
1260                                 goto insert;
1261                         }
1262
1263                         ret = find_next_csum_offset(root, path, &next_offset);
1264                         if (ret < 0)
1265                                 goto out;
1266
1267                         tmp = (next_offset - bytenr) >> fs_info->sectorsize_bits;
1268                         if (tmp <= INT_MAX)
1269                                 extend_nr = min_t(int, extend_nr, tmp);
1270                 }
1271
1272                 diff = (csum_offset + extend_nr) * csum_size;
1273                 diff = min(diff,
1274                            MAX_CSUM_ITEMS(fs_info, csum_size) * csum_size);
1275
1276                 diff = diff - btrfs_item_size(leaf, path->slots[0]);
1277                 diff = min_t(u32, btrfs_leaf_free_space(leaf), diff);
1278                 diff /= csum_size;
1279                 diff *= csum_size;
1280
1281                 btrfs_extend_item(path, diff);
1282                 ret = 0;
1283                 goto csum;
1284         }
1285
1286 insert:
1287         btrfs_release_path(path);
1288         csum_offset = 0;
1289         if (found_next) {
1290                 u64 tmp;
1291
1292                 tmp = sums->len - total_bytes;
1293                 tmp >>= fs_info->sectorsize_bits;
1294                 tmp = min(tmp, (next_offset - file_key.offset) >>
1295                                          fs_info->sectorsize_bits);
1296
1297                 tmp = max_t(u64, 1, tmp);
1298                 tmp = min_t(u64, tmp, MAX_CSUM_ITEMS(fs_info, csum_size));
1299                 ins_size = csum_size * tmp;
1300         } else {
1301                 ins_size = csum_size;
1302         }
1303         ret = btrfs_insert_empty_item(trans, root, path, &file_key,
1304                                       ins_size);
1305         if (ret < 0)
1306                 goto out;
1307         if (WARN_ON(ret != 0))
1308                 goto out;
1309         leaf = path->nodes[0];
1310 csum:
1311         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
1312         item_end = (struct btrfs_csum_item *)((unsigned char *)item +
1313                                       btrfs_item_size(leaf, path->slots[0]));
1314         item = (struct btrfs_csum_item *)((unsigned char *)item +
1315                                           csum_offset * csum_size);
1316 found:
1317         ins_size = (u32)(sums->len - total_bytes) >> fs_info->sectorsize_bits;
1318         ins_size *= csum_size;
1319         ins_size = min_t(u32, (unsigned long)item_end - (unsigned long)item,
1320                               ins_size);
1321         write_extent_buffer(leaf, sums->sums + index, (unsigned long)item,
1322                             ins_size);
1323
1324         index += ins_size;
1325         ins_size /= csum_size;
1326         total_bytes += ins_size * fs_info->sectorsize;
1327
1328         btrfs_mark_buffer_dirty(path->nodes[0]);
1329         if (total_bytes < sums->len) {
1330                 btrfs_release_path(path);
1331                 cond_resched();
1332                 goto again;
1333         }
1334 out:
1335         btrfs_free_path(path);
1336         return ret;
1337 }
1338
1339 void btrfs_extent_item_to_extent_map(struct btrfs_inode *inode,
1340                                      const struct btrfs_path *path,
1341                                      struct btrfs_file_extent_item *fi,
1342                                      struct extent_map *em)
1343 {
1344         struct btrfs_fs_info *fs_info = inode->root->fs_info;
1345         struct btrfs_root *root = inode->root;
1346         struct extent_buffer *leaf = path->nodes[0];
1347         const int slot = path->slots[0];
1348         struct btrfs_key key;
1349         u64 extent_start, extent_end;
1350         u64 bytenr;
1351         u8 type = btrfs_file_extent_type(leaf, fi);
1352         int compress_type = btrfs_file_extent_compression(leaf, fi);
1353
1354         btrfs_item_key_to_cpu(leaf, &key, slot);
1355         extent_start = key.offset;
1356         extent_end = btrfs_file_extent_end(path);
1357         em->ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
1358         em->generation = btrfs_file_extent_generation(leaf, fi);
1359         if (type == BTRFS_FILE_EXTENT_REG ||
1360             type == BTRFS_FILE_EXTENT_PREALLOC) {
1361                 em->start = extent_start;
1362                 em->len = extent_end - extent_start;
1363                 em->orig_start = extent_start -
1364                         btrfs_file_extent_offset(leaf, fi);
1365                 em->orig_block_len = btrfs_file_extent_disk_num_bytes(leaf, fi);
1366                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1367                 if (bytenr == 0) {
1368                         em->block_start = EXTENT_MAP_HOLE;
1369                         return;
1370                 }
1371                 if (compress_type != BTRFS_COMPRESS_NONE) {
1372                         set_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
1373                         em->compress_type = compress_type;
1374                         em->block_start = bytenr;
1375                         em->block_len = em->orig_block_len;
1376                 } else {
1377                         bytenr += btrfs_file_extent_offset(leaf, fi);
1378                         em->block_start = bytenr;
1379                         em->block_len = em->len;
1380                         if (type == BTRFS_FILE_EXTENT_PREALLOC)
1381                                 set_bit(EXTENT_FLAG_PREALLOC, &em->flags);
1382                 }
1383         } else if (type == BTRFS_FILE_EXTENT_INLINE) {
1384                 em->block_start = EXTENT_MAP_INLINE;
1385                 em->start = extent_start;
1386                 em->len = extent_end - extent_start;
1387                 /*
1388                  * Initialize orig_start and block_len with the same values
1389                  * as in inode.c:btrfs_get_extent().
1390                  */
1391                 em->orig_start = EXTENT_MAP_HOLE;
1392                 em->block_len = (u64)-1;
1393                 em->compress_type = compress_type;
1394                 if (compress_type != BTRFS_COMPRESS_NONE)
1395                         set_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
1396         } else {
1397                 btrfs_err(fs_info,
1398                           "unknown file extent item type %d, inode %llu, offset %llu, "
1399                           "root %llu", type, btrfs_ino(inode), extent_start,
1400                           root->root_key.objectid);
1401         }
1402 }
1403
1404 /*
1405  * Returns the end offset (non inclusive) of the file extent item the given path
1406  * points to. If it points to an inline extent, the returned offset is rounded
1407  * up to the sector size.
1408  */
1409 u64 btrfs_file_extent_end(const struct btrfs_path *path)
1410 {
1411         const struct extent_buffer *leaf = path->nodes[0];
1412         const int slot = path->slots[0];
1413         struct btrfs_file_extent_item *fi;
1414         struct btrfs_key key;
1415         u64 end;
1416
1417         btrfs_item_key_to_cpu(leaf, &key, slot);
1418         ASSERT(key.type == BTRFS_EXTENT_DATA_KEY);
1419         fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
1420
1421         if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
1422                 end = btrfs_file_extent_ram_bytes(leaf, fi);
1423                 end = ALIGN(key.offset + end, leaf->fs_info->sectorsize);
1424         } else {
1425                 end = key.offset + btrfs_file_extent_num_bytes(leaf, fi);
1426         }
1427
1428         return end;
1429 }