2
* Copyright (C) 2007 Oracle. All rights reserved.
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.
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.
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.
19
#include <linux/bio.h>
20
#include <linux/slab.h>
21
#include <linux/pagemap.h>
22
#include <linux/highmem.h>
25
#include "transaction.h"
26
#include "print-tree.h"
28
#define MAX_CSUM_ITEMS(r, size) ((((BTRFS_LEAF_DATA_SIZE(r) - \
29
sizeof(struct btrfs_item) * 2) / \
32
#define MAX_ORDERED_SUM_BYTES(r) ((PAGE_SIZE - \
33
sizeof(struct btrfs_ordered_sum)) / \
34
sizeof(struct btrfs_sector_sum) * \
35
(r)->sectorsize - (r)->sectorsize)
37
int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
38
struct btrfs_root *root,
39
u64 objectid, u64 pos,
40
u64 disk_offset, u64 disk_num_bytes,
41
u64 num_bytes, u64 offset, u64 ram_bytes,
42
u8 compression, u8 encryption, u16 other_encoding)
45
struct btrfs_file_extent_item *item;
46
struct btrfs_key file_key;
47
struct btrfs_path *path;
48
struct extent_buffer *leaf;
50
path = btrfs_alloc_path();
53
file_key.objectid = objectid;
54
file_key.offset = pos;
55
btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY);
57
path->leave_spinning = 1;
58
ret = btrfs_insert_empty_item(trans, root, path, &file_key,
63
leaf = path->nodes[0];
64
item = btrfs_item_ptr(leaf, path->slots[0],
65
struct btrfs_file_extent_item);
66
btrfs_set_file_extent_disk_bytenr(leaf, item, disk_offset);
67
btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes);
68
btrfs_set_file_extent_offset(leaf, item, offset);
69
btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
70
btrfs_set_file_extent_ram_bytes(leaf, item, ram_bytes);
71
btrfs_set_file_extent_generation(leaf, item, trans->transid);
72
btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
73
btrfs_set_file_extent_compression(leaf, item, compression);
74
btrfs_set_file_extent_encryption(leaf, item, encryption);
75
btrfs_set_file_extent_other_encoding(leaf, item, other_encoding);
77
btrfs_mark_buffer_dirty(leaf);
79
btrfs_free_path(path);
83
struct btrfs_csum_item *btrfs_lookup_csum(struct btrfs_trans_handle *trans,
84
struct btrfs_root *root,
85
struct btrfs_path *path,
89
struct btrfs_key file_key;
90
struct btrfs_key found_key;
91
struct btrfs_csum_item *item;
92
struct extent_buffer *leaf;
94
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
97
file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
98
file_key.offset = bytenr;
99
btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY);
100
ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow);
103
leaf = path->nodes[0];
106
if (path->slots[0] == 0)
109
btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
110
if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY)
113
csum_offset = (bytenr - found_key.offset) >>
114
root->fs_info->sb->s_blocksize_bits;
115
csums_in_item = btrfs_item_size_nr(leaf, path->slots[0]);
116
csums_in_item /= csum_size;
118
if (csum_offset >= csums_in_item) {
123
item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
124
item = (struct btrfs_csum_item *)((unsigned char *)item +
125
csum_offset * csum_size);
134
int btrfs_lookup_file_extent(struct btrfs_trans_handle *trans,
135
struct btrfs_root *root,
136
struct btrfs_path *path, u64 objectid,
140
struct btrfs_key file_key;
141
int ins_len = mod < 0 ? -1 : 0;
144
file_key.objectid = objectid;
145
file_key.offset = offset;
146
btrfs_set_key_type(&file_key, BTRFS_EXTENT_DATA_KEY);
147
ret = btrfs_search_slot(trans, root, &file_key, path, ins_len, cow);
152
static int __btrfs_lookup_bio_sums(struct btrfs_root *root,
153
struct inode *inode, struct bio *bio,
154
u64 logical_offset, u32 *dst, int dio)
157
struct bio_vec *bvec = bio->bi_io_vec;
160
u64 item_start_offset = 0;
161
u64 item_last_offset = 0;
164
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
166
struct btrfs_path *path;
167
struct btrfs_csum_item *item = NULL;
168
struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
170
path = btrfs_alloc_path();
173
if (bio->bi_size > PAGE_CACHE_SIZE * 8)
176
WARN_ON(bio->bi_vcnt <= 0);
179
* the free space stuff is only read when it hasn't been
180
* updated in the current transaction. So, we can safely
181
* read from the commit root and sidestep a nasty deadlock
182
* between reading the free space cache and updating the csum tree.
184
if (btrfs_is_free_space_inode(root, inode)) {
185
path->search_commit_root = 1;
186
path->skip_locking = 1;
189
disk_bytenr = (u64)bio->bi_sector << 9;
191
offset = logical_offset;
192
while (bio_index < bio->bi_vcnt) {
194
offset = page_offset(bvec->bv_page) + bvec->bv_offset;
195
ret = btrfs_find_ordered_sum(inode, offset, disk_bytenr, &sum);
199
if (!item || disk_bytenr < item_start_offset ||
200
disk_bytenr >= item_last_offset) {
201
struct btrfs_key found_key;
205
btrfs_release_path(path);
206
item = btrfs_lookup_csum(NULL, root->fs_info->csum_root,
207
path, disk_bytenr, 0);
210
if (ret == -ENOENT || ret == -EFBIG)
213
if (BTRFS_I(inode)->root->root_key.objectid ==
214
BTRFS_DATA_RELOC_TREE_OBJECTID) {
215
set_extent_bits(io_tree, offset,
216
offset + bvec->bv_len - 1,
217
EXTENT_NODATASUM, GFP_NOFS);
219
printk(KERN_INFO "btrfs no csum found "
220
"for inode %llu start %llu\n",
223
(unsigned long long)offset);
226
btrfs_release_path(path);
229
btrfs_item_key_to_cpu(path->nodes[0], &found_key,
232
item_start_offset = found_key.offset;
233
item_size = btrfs_item_size_nr(path->nodes[0],
235
item_last_offset = item_start_offset +
236
(item_size / csum_size) *
238
item = btrfs_item_ptr(path->nodes[0], path->slots[0],
239
struct btrfs_csum_item);
242
* this byte range must be able to fit inside
243
* a single leaf so it will also fit inside a u32
245
diff = disk_bytenr - item_start_offset;
246
diff = diff / root->sectorsize;
247
diff = diff * csum_size;
249
read_extent_buffer(path->nodes[0], &sum,
250
((unsigned long)item) + diff,
256
set_state_private(io_tree, offset, sum);
257
disk_bytenr += bvec->bv_len;
258
offset += bvec->bv_len;
262
btrfs_free_path(path);
266
int btrfs_lookup_bio_sums(struct btrfs_root *root, struct inode *inode,
267
struct bio *bio, u32 *dst)
269
return __btrfs_lookup_bio_sums(root, inode, bio, 0, dst, 0);
272
int btrfs_lookup_bio_sums_dio(struct btrfs_root *root, struct inode *inode,
273
struct bio *bio, u64 offset, u32 *dst)
275
return __btrfs_lookup_bio_sums(root, inode, bio, offset, dst, 1);
278
int btrfs_lookup_csums_range(struct btrfs_root *root, u64 start, u64 end,
279
struct list_head *list, int search_commit)
281
struct btrfs_key key;
282
struct btrfs_path *path;
283
struct extent_buffer *leaf;
284
struct btrfs_ordered_sum *sums;
285
struct btrfs_sector_sum *sector_sum;
286
struct btrfs_csum_item *item;
287
unsigned long offset;
291
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
293
path = btrfs_alloc_path();
298
path->skip_locking = 1;
300
path->search_commit_root = 1;
303
key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
305
key.type = BTRFS_EXTENT_CSUM_KEY;
307
ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
310
if (ret > 0 && path->slots[0] > 0) {
311
leaf = path->nodes[0];
312
btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
313
if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
314
key.type == BTRFS_EXTENT_CSUM_KEY) {
315
offset = (start - key.offset) >>
316
root->fs_info->sb->s_blocksize_bits;
317
if (offset * csum_size <
318
btrfs_item_size_nr(leaf, path->slots[0] - 1))
323
while (start <= end) {
324
leaf = path->nodes[0];
325
if (path->slots[0] >= btrfs_header_nritems(leaf)) {
326
ret = btrfs_next_leaf(root, path);
331
leaf = path->nodes[0];
334
btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
335
if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
336
key.type != BTRFS_EXTENT_CSUM_KEY)
339
btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
340
if (key.offset > end)
343
if (key.offset > start)
346
size = btrfs_item_size_nr(leaf, path->slots[0]);
347
csum_end = key.offset + (size / csum_size) * root->sectorsize;
348
if (csum_end <= start) {
353
csum_end = min(csum_end, end + 1);
354
item = btrfs_item_ptr(path->nodes[0], path->slots[0],
355
struct btrfs_csum_item);
356
while (start < csum_end) {
357
size = min_t(size_t, csum_end - start,
358
MAX_ORDERED_SUM_BYTES(root));
359
sums = kzalloc(btrfs_ordered_sum_size(root, size),
363
sector_sum = sums->sums;
364
sums->bytenr = start;
367
offset = (start - key.offset) >>
368
root->fs_info->sb->s_blocksize_bits;
372
read_extent_buffer(path->nodes[0],
374
((unsigned long)item) +
376
sector_sum->bytenr = start;
378
size -= root->sectorsize;
379
start += root->sectorsize;
383
list_add_tail(&sums->list, list);
389
btrfs_free_path(path);
393
int btrfs_csum_one_bio(struct btrfs_root *root, struct inode *inode,
394
struct bio *bio, u64 file_start, int contig)
396
struct btrfs_ordered_sum *sums;
397
struct btrfs_sector_sum *sector_sum;
398
struct btrfs_ordered_extent *ordered;
400
struct bio_vec *bvec = bio->bi_io_vec;
402
unsigned long total_bytes = 0;
403
unsigned long this_sum_bytes = 0;
407
WARN_ON(bio->bi_vcnt <= 0);
408
sums = kzalloc(btrfs_ordered_sum_size(root, bio->bi_size), GFP_NOFS);
412
sector_sum = sums->sums;
413
disk_bytenr = (u64)bio->bi_sector << 9;
414
sums->len = bio->bi_size;
415
INIT_LIST_HEAD(&sums->list);
420
offset = page_offset(bvec->bv_page) + bvec->bv_offset;
422
ordered = btrfs_lookup_ordered_extent(inode, offset);
424
sums->bytenr = ordered->start;
426
while (bio_index < bio->bi_vcnt) {
428
offset = page_offset(bvec->bv_page) + bvec->bv_offset;
430
if (!contig && (offset >= ordered->file_offset + ordered->len ||
431
offset < ordered->file_offset)) {
432
unsigned long bytes_left;
433
sums->len = this_sum_bytes;
435
btrfs_add_ordered_sum(inode, ordered, sums);
436
btrfs_put_ordered_extent(ordered);
438
bytes_left = bio->bi_size - total_bytes;
440
sums = kzalloc(btrfs_ordered_sum_size(root, bytes_left),
443
sector_sum = sums->sums;
444
sums->len = bytes_left;
445
ordered = btrfs_lookup_ordered_extent(inode, offset);
447
sums->bytenr = ordered->start;
450
data = kmap_atomic(bvec->bv_page, KM_USER0);
451
sector_sum->sum = ~(u32)0;
452
sector_sum->sum = btrfs_csum_data(root,
453
data + bvec->bv_offset,
456
kunmap_atomic(data, KM_USER0);
457
btrfs_csum_final(sector_sum->sum,
458
(char *)§or_sum->sum);
459
sector_sum->bytenr = disk_bytenr;
463
total_bytes += bvec->bv_len;
464
this_sum_bytes += bvec->bv_len;
465
disk_bytenr += bvec->bv_len;
466
offset += bvec->bv_len;
470
btrfs_add_ordered_sum(inode, ordered, sums);
471
btrfs_put_ordered_extent(ordered);
476
* helper function for csum removal, this expects the
477
* key to describe the csum pointed to by the path, and it expects
478
* the csum to overlap the range [bytenr, len]
480
* The csum should not be entirely contained in the range and the
481
* range should not be entirely contained in the csum.
483
* This calls btrfs_truncate_item with the correct args based on the
484
* overlap, and fixes up the key as required.
486
static noinline int truncate_one_csum(struct btrfs_trans_handle *trans,
487
struct btrfs_root *root,
488
struct btrfs_path *path,
489
struct btrfs_key *key,
492
struct extent_buffer *leaf;
493
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
495
u64 end_byte = bytenr + len;
496
u32 blocksize_bits = root->fs_info->sb->s_blocksize_bits;
499
leaf = path->nodes[0];
500
csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
501
csum_end <<= root->fs_info->sb->s_blocksize_bits;
502
csum_end += key->offset;
504
if (key->offset < bytenr && csum_end <= end_byte) {
509
* A simple truncate off the end of the item
511
u32 new_size = (bytenr - key->offset) >> blocksize_bits;
512
new_size *= csum_size;
513
ret = btrfs_truncate_item(trans, root, path, new_size, 1);
514
} else if (key->offset >= bytenr && csum_end > end_byte &&
515
end_byte > key->offset) {
520
* we need to truncate from the beginning of the csum
522
u32 new_size = (csum_end - end_byte) >> blocksize_bits;
523
new_size *= csum_size;
525
ret = btrfs_truncate_item(trans, root, path, new_size, 0);
527
key->offset = end_byte;
528
ret = btrfs_set_item_key_safe(trans, root, path, key);
537
* deletes the csum items from the csum tree for a given
540
int btrfs_del_csums(struct btrfs_trans_handle *trans,
541
struct btrfs_root *root, u64 bytenr, u64 len)
543
struct btrfs_path *path;
544
struct btrfs_key key;
545
u64 end_byte = bytenr + len;
547
struct extent_buffer *leaf;
549
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
550
int blocksize_bits = root->fs_info->sb->s_blocksize_bits;
552
root = root->fs_info->csum_root;
554
path = btrfs_alloc_path();
559
key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
560
key.offset = end_byte - 1;
561
key.type = BTRFS_EXTENT_CSUM_KEY;
563
path->leave_spinning = 1;
564
ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
566
if (path->slots[0] == 0)
569
} else if (ret < 0) {
573
leaf = path->nodes[0];
574
btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
576
if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
577
key.type != BTRFS_EXTENT_CSUM_KEY) {
581
if (key.offset >= end_byte)
584
csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
585
csum_end <<= blocksize_bits;
586
csum_end += key.offset;
588
/* this csum ends before we start, we're done */
589
if (csum_end <= bytenr)
592
/* delete the entire item, it is inside our range */
593
if (key.offset >= bytenr && csum_end <= end_byte) {
594
ret = btrfs_del_item(trans, root, path);
597
if (key.offset == bytenr)
599
} else if (key.offset < bytenr && csum_end > end_byte) {
600
unsigned long offset;
601
unsigned long shift_len;
602
unsigned long item_offset;
607
* Our bytes are in the middle of the csum,
608
* we need to split this item and insert a new one.
610
* But we can't drop the path because the
611
* csum could change, get removed, extended etc.
613
* The trick here is the max size of a csum item leaves
614
* enough room in the tree block for a single
615
* item header. So, we split the item in place,
616
* adding a new header pointing to the existing
617
* bytes. Then we loop around again and we have
618
* a nicely formed csum item that we can neatly
621
offset = (bytenr - key.offset) >> blocksize_bits;
624
shift_len = (len >> blocksize_bits) * csum_size;
626
item_offset = btrfs_item_ptr_offset(leaf,
629
memset_extent_buffer(leaf, 0, item_offset + offset,
634
* btrfs_split_item returns -EAGAIN when the
635
* item changed size or key
637
ret = btrfs_split_item(trans, root, path, &key, offset);
638
BUG_ON(ret && ret != -EAGAIN);
640
key.offset = end_byte - 1;
642
ret = truncate_one_csum(trans, root, path,
645
if (key.offset < bytenr)
648
btrfs_release_path(path);
652
btrfs_free_path(path);
656
int btrfs_csum_file_blocks(struct btrfs_trans_handle *trans,
657
struct btrfs_root *root,
658
struct btrfs_ordered_sum *sums)
662
struct btrfs_key file_key;
663
struct btrfs_key found_key;
667
struct btrfs_path *path;
668
struct btrfs_csum_item *item;
669
struct btrfs_csum_item *item_end;
670
struct extent_buffer *leaf = NULL;
672
struct btrfs_sector_sum *sector_sum;
675
u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
677
path = btrfs_alloc_path();
681
sector_sum = sums->sums;
683
next_offset = (u64)-1;
685
file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
686
file_key.offset = sector_sum->bytenr;
687
bytenr = sector_sum->bytenr;
688
btrfs_set_key_type(&file_key, BTRFS_EXTENT_CSUM_KEY);
690
item = btrfs_lookup_csum(trans, root, path, sector_sum->bytenr, 1);
692
leaf = path->nodes[0];
697
if (ret != -EFBIG && ret != -ENOENT)
702
/* we found one, but it isn't big enough yet */
703
leaf = path->nodes[0];
704
item_size = btrfs_item_size_nr(leaf, path->slots[0]);
705
if ((item_size / csum_size) >=
706
MAX_CSUM_ITEMS(root, csum_size)) {
707
/* already at max size, make a new one */
711
int slot = path->slots[0] + 1;
712
/* we didn't find a csum item, insert one */
713
nritems = btrfs_header_nritems(path->nodes[0]);
714
if (path->slots[0] >= nritems - 1) {
715
ret = btrfs_next_leaf(root, path);
722
btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
723
if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
724
found_key.type != BTRFS_EXTENT_CSUM_KEY) {
728
next_offset = found_key.offset;
734
* at this point, we know the tree has an item, but it isn't big
735
* enough yet to put our csum in. Grow it
737
btrfs_release_path(path);
738
ret = btrfs_search_slot(trans, root, &file_key, path,
744
if (path->slots[0] == 0)
749
leaf = path->nodes[0];
750
btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
751
csum_offset = (bytenr - found_key.offset) >>
752
root->fs_info->sb->s_blocksize_bits;
754
if (btrfs_key_type(&found_key) != BTRFS_EXTENT_CSUM_KEY ||
755
found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
756
csum_offset >= MAX_CSUM_ITEMS(root, csum_size)) {
760
if (csum_offset >= btrfs_item_size_nr(leaf, path->slots[0]) /
762
u32 diff = (csum_offset + 1) * csum_size;
765
* is the item big enough already? we dropped our lock
766
* before and need to recheck
768
if (diff < btrfs_item_size_nr(leaf, path->slots[0]))
771
diff = diff - btrfs_item_size_nr(leaf, path->slots[0]);
772
if (diff != csum_size)
775
ret = btrfs_extend_item(trans, root, path, diff);
780
btrfs_release_path(path);
783
u64 tmp = total_bytes + root->sectorsize;
784
u64 next_sector = sector_sum->bytenr;
785
struct btrfs_sector_sum *next = sector_sum + 1;
787
while (tmp < sums->len) {
788
if (next_sector + root->sectorsize != next->bytenr)
790
tmp += root->sectorsize;
791
next_sector = next->bytenr;
794
tmp = min(tmp, next_offset - file_key.offset);
795
tmp >>= root->fs_info->sb->s_blocksize_bits;
796
tmp = max((u64)1, tmp);
797
tmp = min(tmp, (u64)MAX_CSUM_ITEMS(root, csum_size));
798
ins_size = csum_size * tmp;
800
ins_size = csum_size;
802
path->leave_spinning = 1;
803
ret = btrfs_insert_empty_item(trans, root, path, &file_key,
805
path->leave_spinning = 0;
813
leaf = path->nodes[0];
814
item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
816
item = (struct btrfs_csum_item *)((unsigned char *)item +
817
csum_offset * csum_size);
819
item_end = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
820
item_end = (struct btrfs_csum_item *)((unsigned char *)item_end +
821
btrfs_item_size_nr(leaf, path->slots[0]));
824
write_extent_buffer(leaf, §or_sum->sum, (unsigned long)item, csum_size);
826
total_bytes += root->sectorsize;
828
if (total_bytes < sums->len) {
829
item = (struct btrfs_csum_item *)((char *)item +
831
if (item < item_end && bytenr + PAGE_CACHE_SIZE ==
832
sector_sum->bytenr) {
833
bytenr = sector_sum->bytenr;
838
btrfs_mark_buffer_dirty(path->nodes[0]);
839
if (total_bytes < sums->len) {
840
btrfs_release_path(path);
845
btrfs_free_path(path);