file-item.c 27.1 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
Chris Mason's avatar
Chris Mason committed
2
3
4
5
/*
 * Copyright (C) 2007 Oracle.  All rights reserved.
 */

6
#include <linux/bio.h>
7
#include <linux/slab.h>
8
9
#include <linux/pagemap.h>
#include <linux/highmem.h>
10
#include <linux/sched/mm.h>
11
#include <crypto/hash.h>
Chris Mason's avatar
Chris Mason committed
12
#include "ctree.h"
Chris Mason's avatar
Chris Mason committed
13
#include "disk-io.h"
14
#include "transaction.h"
15
#include "volumes.h"
16
#include "print-tree.h"
17
#include "compression.h"
Chris Mason's avatar
Chris Mason committed
18

Chris Mason's avatar
Chris Mason committed
19
20
21
#define __MAX_CSUM_ITEMS(r, size) ((unsigned long)(((BTRFS_LEAF_DATA_SIZE(r) - \
				   sizeof(struct btrfs_item) * 2) / \
				  size) - 1))
Yan Zheng's avatar
Yan Zheng committed
22

23
#define MAX_CSUM_ITEMS(r, size) (min_t(u32, __MAX_CSUM_ITEMS(r, size), \
24
				       PAGE_SIZE))
25

26
27
28
29
30
31
32
static inline u32 max_ordered_sum_bytes(struct btrfs_fs_info *fs_info,
					u16 csum_size)
{
	u32 ncsums = (PAGE_SIZE - sizeof(struct btrfs_ordered_sum)) / csum_size;

	return ncsums * fs_info->sectorsize;
}
Yan Zheng's avatar
Yan Zheng committed
33

Chris Mason's avatar
Chris Mason committed
34
int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
Sage Weil's avatar
Sage Weil committed
35
36
37
			     struct btrfs_root *root,
			     u64 objectid, u64 pos,
			     u64 disk_offset, u64 disk_num_bytes,
38
39
			     u64 num_bytes, u64 offset, u64 ram_bytes,
			     u8 compression, u8 encryption, u16 other_encoding)
40
{
Chris Mason's avatar
Chris Mason committed
41
42
43
	int ret = 0;
	struct btrfs_file_extent_item *item;
	struct btrfs_key file_key;
44
	struct btrfs_path *path;
45
	struct extent_buffer *leaf;
Chris Mason's avatar
Chris Mason committed
46

47
	path = btrfs_alloc_path();
Tsutomu Itoh's avatar
Tsutomu Itoh committed
48
49
	if (!path)
		return -ENOMEM;
Chris Mason's avatar
Chris Mason committed
50
	file_key.objectid = objectid;
Chris Mason's avatar
Chris Mason committed
51
	file_key.offset = pos;
52
	file_key.type = BTRFS_EXTENT_DATA_KEY;
Chris Mason's avatar
Chris Mason committed
53

54
	path->leave_spinning = 1;
55
	ret = btrfs_insert_empty_item(trans, root, path, &file_key,
Chris Mason's avatar
Chris Mason committed
56
				      sizeof(*item));
57
58
	if (ret < 0)
		goto out;
59
	BUG_ON(ret); /* Can't happen */
60
61
	leaf = path->nodes[0];
	item = btrfs_item_ptr(leaf, path->slots[0],
Chris Mason's avatar
Chris Mason committed
62
			      struct btrfs_file_extent_item);
Sage Weil's avatar
Sage Weil committed
63
	btrfs_set_file_extent_disk_bytenr(leaf, item, disk_offset);
64
	btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes);
Sage Weil's avatar
Sage Weil committed
65
	btrfs_set_file_extent_offset(leaf, item, offset);
66
	btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
67
	btrfs_set_file_extent_ram_bytes(leaf, item, ram_bytes);
68
69
	btrfs_set_file_extent_generation(leaf, item, trans->transid);
	btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
70
71
72
73
	btrfs_set_file_extent_compression(leaf, item, compression);
	btrfs_set_file_extent_encryption(leaf, item, encryption);
	btrfs_set_file_extent_other_encoding(leaf, item, other_encoding);

74
	btrfs_mark_buffer_dirty(leaf);
75
out:
76
	btrfs_free_path(path);
77
	return ret;
78
}
Chris Mason's avatar
Chris Mason committed
79

80
81
82
83
84
static struct btrfs_csum_item *
btrfs_lookup_csum(struct btrfs_trans_handle *trans,
		  struct btrfs_root *root,
		  struct btrfs_path *path,
		  u64 bytenr, int cow)
85
{
86
	struct btrfs_fs_info *fs_info = root->fs_info;
87
88
89
90
	int ret;
	struct btrfs_key file_key;
	struct btrfs_key found_key;
	struct btrfs_csum_item *item;
91
	struct extent_buffer *leaf;
92
	u64 csum_offset = 0;
93
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
94
	int csums_in_item;
95

96
97
	file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
	file_key.offset = bytenr;
98
	file_key.type = BTRFS_EXTENT_CSUM_KEY;
Chris Mason's avatar
Chris Mason committed
99
	ret = btrfs_search_slot(trans, root, &file_key, path, 0, cow);
100
101
	if (ret < 0)
		goto fail;
102
	leaf = path->nodes[0];
103
104
	if (ret > 0) {
		ret = 1;
105
		if (path->slots[0] == 0)
106
107
			goto fail;
		path->slots[0]--;
108
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
109
		if (found_key.type != BTRFS_EXTENT_CSUM_KEY)
110
			goto fail;
111
112

		csum_offset = (bytenr - found_key.offset) >>
113
				fs_info->sb->s_blocksize_bits;
114
		csums_in_item = btrfs_item_size_nr(leaf, path->slots[0]);
115
		csums_in_item /= csum_size;
116

117
		if (csum_offset == csums_in_item) {
118
			ret = -EFBIG;
119
			goto fail;
120
121
		} else if (csum_offset > csums_in_item) {
			goto fail;
122
123
124
		}
	}
	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_csum_item);
125
	item = (struct btrfs_csum_item *)((unsigned char *)item +
126
					  csum_offset * csum_size);
127
128
129
	return item;
fail:
	if (ret > 0)
Chris Mason's avatar
Chris Mason committed
130
		ret = -ENOENT;
131
132
133
	return ERR_PTR(ret);
}

Chris Mason's avatar
Chris Mason committed
134
135
136
int btrfs_lookup_file_extent(struct btrfs_trans_handle *trans,
			     struct btrfs_root *root,
			     struct btrfs_path *path, u64 objectid,
137
			     u64 offset, int mod)
Chris Mason's avatar
Chris Mason committed
138
139
140
141
142
143
144
{
	int ret;
	struct btrfs_key file_key;
	int ins_len = mod < 0 ? -1 : 0;
	int cow = mod != 0;

	file_key.objectid = objectid;
145
	file_key.offset = offset;
146
	file_key.type = BTRFS_EXTENT_DATA_KEY;
Chris Mason's avatar
Chris Mason committed
147
148
149
	ret = btrfs_search_slot(trans, root, &file_key, path, ins_len, cow);
	return ret;
}
Chris Mason's avatar
Chris Mason committed
150

151
static blk_status_t __btrfs_lookup_bio_sums(struct inode *inode, struct bio *bio,
152
				   u64 logical_offset, u8 *dst, int dio)
153
{
154
	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
155
156
	struct bio_vec bvec;
	struct bvec_iter iter;
157
158
159
160
161
	struct btrfs_io_bio *btrfs_bio = btrfs_io_bio(bio);
	struct btrfs_csum_item *item = NULL;
	struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
	struct btrfs_path *path;
	u8 *csum;
162
	u64 offset = 0;
163
164
	u64 item_start_offset = 0;
	u64 item_last_offset = 0;
165
	u64 disk_bytenr;
166
	u64 page_bytes_left;
167
	u32 diff;
168
	int nblocks;
169
	int count = 0;
170
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
171
172

	path = btrfs_alloc_path();
173
	if (!path)
174
		return BLK_STS_RESOURCE;
175

176
	nblocks = bio->bi_iter.bi_size >> inode->i_sb->s_blocksize_bits;
177
178
	if (!dst) {
		if (nblocks * csum_size > BTRFS_BIO_INLINE_CSUM_SIZE) {
179
180
181
			btrfs_bio->csum = kmalloc_array(nblocks, csum_size,
							GFP_NOFS);
			if (!btrfs_bio->csum) {
182
				btrfs_free_path(path);
183
				return BLK_STS_RESOURCE;
184
185
186
187
188
189
			}
		} else {
			btrfs_bio->csum = btrfs_bio->csum_inline;
		}
		csum = btrfs_bio->csum;
	} else {
190
		csum = dst;
191
192
	}

193
	if (bio->bi_iter.bi_size > PAGE_SIZE * 8)
194
		path->reada = READA_FORWARD;
195

196
197
198
199
200
201
	/*
	 * the free space stuff is only read when it hasn't been
	 * updated in the current transaction.  So, we can safely
	 * read from the commit root and sidestep a nasty deadlock
	 * between reading the free space cache and updating the csum tree.
	 */
202
	if (btrfs_is_free_space_inode(BTRFS_I(inode))) {
203
		path->search_commit_root = 1;
204
205
		path->skip_locking = 1;
	}
206

207
	disk_bytenr = (u64)bio->bi_iter.bi_sector << 9;
208
209
	if (dio)
		offset = logical_offset;
210

211
212
	bio_for_each_segment(bvec, bio, iter) {
		page_bytes_left = bvec.bv_len;
213
214
215
		if (count)
			goto next;

216
		if (!dio)
217
			offset = page_offset(bvec.bv_page) + bvec.bv_offset;
218
		count = btrfs_find_ordered_sum(inode, offset, disk_bytenr,
219
					       csum, nblocks);
220
		if (count)
221
222
			goto found;

223
224
		if (!item || disk_bytenr < item_start_offset ||
		    disk_bytenr >= item_last_offset) {
225
226
227
228
			struct btrfs_key found_key;
			u32 item_size;

			if (item)
229
				btrfs_release_path(path);
230
			item = btrfs_lookup_csum(NULL, fs_info->csum_root,
231
						 path, disk_bytenr, 0);
232
			if (IS_ERR(item)) {
233
				count = 1;
234
				memset(csum, 0, csum_size);
235
236
237
				if (BTRFS_I(inode)->root->root_key.objectid ==
				    BTRFS_DATA_RELOC_TREE_OBJECTID) {
					set_extent_bits(io_tree, offset,
238
						offset + fs_info->sectorsize - 1,
239
						EXTENT_NODATASUM);
240
				} else {
241
					btrfs_info_rl(fs_info,
242
						   "no csum found for inode %llu start %llu",
243
					       btrfs_ino(BTRFS_I(inode)), offset);
244
				}
245
				item = NULL;
246
				btrfs_release_path(path);
247
248
249
250
251
252
253
254
255
				goto found;
			}
			btrfs_item_key_to_cpu(path->nodes[0], &found_key,
					      path->slots[0]);

			item_start_offset = found_key.offset;
			item_size = btrfs_item_size_nr(path->nodes[0],
						       path->slots[0]);
			item_last_offset = item_start_offset +
256
				(item_size / csum_size) *
257
				fs_info->sectorsize;
258
259
260
261
262
263
264
			item = btrfs_item_ptr(path->nodes[0], path->slots[0],
					      struct btrfs_csum_item);
		}
		/*
		 * this byte range must be able to fit inside
		 * a single leaf so it will also fit inside a u32
		 */
265
		diff = disk_bytenr - item_start_offset;
266
		diff = diff / fs_info->sectorsize;
267
		diff = diff * csum_size;
268
269
270
		count = min_t(int, nblocks, (item_last_offset - disk_bytenr) >>
					    inode->i_sb->s_blocksize_bits);
		read_extent_buffer(path->nodes[0], csum,
271
				   ((unsigned long)item) + diff,
272
				   csum_size * count);
273
found:
274
275
		csum += count * csum_size;
		nblocks -= count;
276
next:
277
		while (count--) {
278
279
280
			disk_bytenr += fs_info->sectorsize;
			offset += fs_info->sectorsize;
			page_bytes_left -= fs_info->sectorsize;
281
282
			if (!page_bytes_left)
				break; /* move to next bio */
283
		}
284
	}
285

286
	WARN_ON_ONCE(count);
287
288
289
290
	btrfs_free_path(path);
	return 0;
}

291
292
blk_status_t btrfs_lookup_bio_sums(struct inode *inode, struct bio *bio,
				   u8 *dst)
293
{
294
	return __btrfs_lookup_bio_sums(inode, bio, 0, dst, 0);
295
296
}

297
blk_status_t btrfs_lookup_bio_sums_dio(struct inode *inode, struct bio *bio, u64 offset)
298
{
299
	return __btrfs_lookup_bio_sums(inode, bio, offset, NULL, 1);
300
301
}

302
int btrfs_lookup_csums_range(struct btrfs_root *root, u64 start, u64 end,
Arne Jansen's avatar
Arne Jansen committed
303
			     struct list_head *list, int search_commit)
304
{
305
	struct btrfs_fs_info *fs_info = root->fs_info;
306
307
308
309
310
	struct btrfs_key key;
	struct btrfs_path *path;
	struct extent_buffer *leaf;
	struct btrfs_ordered_sum *sums;
	struct btrfs_csum_item *item;
311
	LIST_HEAD(tmplist);
312
313
314
315
	unsigned long offset;
	int ret;
	size_t size;
	u64 csum_end;
316
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
317

318
319
	ASSERT(IS_ALIGNED(start, fs_info->sectorsize) &&
	       IS_ALIGNED(end + 1, fs_info->sectorsize));
320

321
	path = btrfs_alloc_path();
322
323
	if (!path)
		return -ENOMEM;
324

Arne Jansen's avatar
Arne Jansen committed
325
326
	if (search_commit) {
		path->skip_locking = 1;
327
		path->reada = READA_FORWARD;
Arne Jansen's avatar
Arne Jansen committed
328
329
330
		path->search_commit_root = 1;
	}

331
332
333
334
	key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
	key.offset = start;
	key.type = BTRFS_EXTENT_CSUM_KEY;

Yan Zheng's avatar
Yan Zheng committed
335
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
336
337
338
339
340
341
342
343
	if (ret < 0)
		goto fail;
	if (ret > 0 && path->slots[0] > 0) {
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
		if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
		    key.type == BTRFS_EXTENT_CSUM_KEY) {
			offset = (start - key.offset) >>
344
				 fs_info->sb->s_blocksize_bits;
345
346
347
348
349
350
351
352
353
			if (offset * csum_size <
			    btrfs_item_size_nr(leaf, path->slots[0] - 1))
				path->slots[0]--;
		}
	}

	while (start <= end) {
		leaf = path->nodes[0];
		if (path->slots[0] >= btrfs_header_nritems(leaf)) {
Yan Zheng's avatar
Yan Zheng committed
354
			ret = btrfs_next_leaf(root, path);
355
356
357
358
359
360
361
362
363
			if (ret < 0)
				goto fail;
			if (ret > 0)
				break;
			leaf = path->nodes[0];
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
364
365
		    key.type != BTRFS_EXTENT_CSUM_KEY ||
		    key.offset > end)
366
367
368
369
370
371
			break;

		if (key.offset > start)
			start = key.offset;

		size = btrfs_item_size_nr(leaf, path->slots[0]);
372
		csum_end = key.offset + (size / csum_size) * fs_info->sectorsize;
373
374
375
376
		if (csum_end <= start) {
			path->slots[0]++;
			continue;
		}
377

Yan Zheng's avatar
Yan Zheng committed
378
		csum_end = min(csum_end, end + 1);
379
380
		item = btrfs_item_ptr(path->nodes[0], path->slots[0],
				      struct btrfs_csum_item);
Yan Zheng's avatar
Yan Zheng committed
381
382
		while (start < csum_end) {
			size = min_t(size_t, csum_end - start,
383
				     max_ordered_sum_bytes(fs_info, csum_size));
384
			sums = kzalloc(btrfs_ordered_sum_size(fs_info, size),
385
				       GFP_NOFS);
386
387
388
389
			if (!sums) {
				ret = -ENOMEM;
				goto fail;
			}
390

Yan Zheng's avatar
Yan Zheng committed
391
			sums->bytenr = start;
392
			sums->len = (int)size;
Yan Zheng's avatar
Yan Zheng committed
393
394

			offset = (start - key.offset) >>
395
				fs_info->sb->s_blocksize_bits;
Yan Zheng's avatar
Yan Zheng committed
396
			offset *= csum_size;
397
			size >>= fs_info->sb->s_blocksize_bits;
Yan Zheng's avatar
Yan Zheng committed
398

399
400
401
402
403
			read_extent_buffer(path->nodes[0],
					   sums->sums,
					   ((unsigned long)item) + offset,
					   csum_size * size);

404
			start += fs_info->sectorsize * size;
405
			list_add_tail(&sums->list, &tmplist);
Yan Zheng's avatar
Yan Zheng committed
406
		}
407
408
409
410
		path->slots[0]++;
	}
	ret = 0;
fail:
411
	while (ret < 0 && !list_empty(&tmplist)) {
412
		sums = list_entry(tmplist.next, struct btrfs_ordered_sum, list);
413
414
415
416
417
		list_del(&sums->list);
		kfree(sums);
	}
	list_splice_tail(&tmplist, list);

418
419
420
421
	btrfs_free_path(path);
	return ret;
}

422
423
424
425
426
427
428
429
430
431
/*
 * btrfs_csum_one_bio - Calculates checksums of the data contained inside a bio
 * @inode:	 Owner of the data inside the bio
 * @bio:	 Contains the data to be checksummed
 * @file_start:  offset in file this bio begins to describe
 * @contig:	 Boolean. If true/1 means all bio vecs in this bio are
 *		 contiguous and they begin at @file_start in the file. False/0
 *		 means this bio can contains potentially discontigous bio vecs
 *		 so the logical offset of each should be calculated separately.
 */
432
blk_status_t btrfs_csum_one_bio(struct inode *inode, struct bio *bio,
433
		       u64 file_start, int contig)
434
{
435
	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
436
	SHASH_DESC_ON_STACK(shash, fs_info->csum_shash);
437
	struct btrfs_ordered_sum *sums;
438
	struct btrfs_ordered_extent *ordered = NULL;
439
	char *data;
440
441
	struct bvec_iter iter;
	struct bio_vec bvec;
442
	int index;
443
	int nr_sectors;
444
445
	unsigned long total_bytes = 0;
	unsigned long this_sum_bytes = 0;
446
	int i;
447
	u64 offset;
448
	unsigned nofs_flag;
449
	const u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
450
451
452
453
454

	nofs_flag = memalloc_nofs_save();
	sums = kvzalloc(btrfs_ordered_sum_size(fs_info, bio->bi_iter.bi_size),
		       GFP_KERNEL);
	memalloc_nofs_restore(nofs_flag);
455
456

	if (!sums)
457
		return BLK_STS_RESOURCE;
458

459
	sums->len = bio->bi_iter.bi_size;
460
	INIT_LIST_HEAD(&sums->list);
461
462
463
464

	if (contig)
		offset = file_start;
	else
465
		offset = 0; /* shut up gcc */
466

467
	sums->bytenr = (u64)bio->bi_iter.bi_sector << 9;
468
	index = 0;
469

470
471
	shash->tfm = fs_info->csum_shash;

472
	bio_for_each_segment(bvec, bio, iter) {
473
		if (!contig)
474
			offset = page_offset(bvec.bv_page) + bvec.bv_offset;
475

476
477
478
479
480
		if (!ordered) {
			ordered = btrfs_lookup_ordered_extent(inode, offset);
			BUG_ON(!ordered); /* Logic error */
		}

481
		nr_sectors = BTRFS_BYTES_TO_BLKS(fs_info,
482
						 bvec.bv_len + fs_info->sectorsize
483
						 - 1);
484
485
486
487
488
489
490
491

		for (i = 0; i < nr_sectors; i++) {
			if (offset >= ordered->file_offset + ordered->len ||
				offset < ordered->file_offset) {
				unsigned long bytes_left;

				sums->len = this_sum_bytes;
				this_sum_bytes = 0;
492
				btrfs_add_ordered_sum(ordered, sums);
493
494
495
496
				btrfs_put_ordered_extent(ordered);

				bytes_left = bio->bi_iter.bi_size - total_bytes;

497
498
499
500
				nofs_flag = memalloc_nofs_save();
				sums = kvzalloc(btrfs_ordered_sum_size(fs_info,
						      bytes_left), GFP_KERNEL);
				memalloc_nofs_restore(nofs_flag);
501
502
503
504
505
506
507
508
509
				BUG_ON(!sums); /* -ENOMEM */
				sums->len = bytes_left;
				ordered = btrfs_lookup_ordered_extent(inode,
								offset);
				ASSERT(ordered); /* Logic error */
				sums->bytenr = ((u64)bio->bi_iter.bi_sector << 9)
					+ total_bytes;
				index = 0;
			}
510

511
			crypto_shash_init(shash);
512
			data = kmap_atomic(bvec.bv_page);
513
514
515
			crypto_shash_update(shash, data + bvec.bv_offset
					    + (i * fs_info->sectorsize),
					    fs_info->sectorsize);
516
			kunmap_atomic(data);
517
			crypto_shash_final(shash, (char *)(sums->sums + index));
518
			index += csum_size;
519
520
521
			offset += fs_info->sectorsize;
			this_sum_bytes += fs_info->sectorsize;
			total_bytes += fs_info->sectorsize;
522
523
		}

524
	}
525
	this_sum_bytes = 0;
526
	btrfs_add_ordered_sum(ordered, sums);
527
	btrfs_put_ordered_extent(ordered);
528
529
530
	return 0;
}

531
532
533
534
535
536
537
538
539
540
541
/*
 * helper function for csum removal, this expects the
 * key to describe the csum pointed to by the path, and it expects
 * the csum to overlap the range [bytenr, len]
 *
 * The csum should not be entirely contained in the range and the
 * range should not be entirely contained in the csum.
 *
 * This calls btrfs_truncate_item with the correct args based on the
 * overlap, and fixes up the key as required.
 */
542
static noinline void truncate_one_csum(struct btrfs_fs_info *fs_info,
543
544
545
				       struct btrfs_path *path,
				       struct btrfs_key *key,
				       u64 bytenr, u64 len)
546
547
{
	struct extent_buffer *leaf;
548
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
549
550
	u64 csum_end;
	u64 end_byte = bytenr + len;
551
	u32 blocksize_bits = fs_info->sb->s_blocksize_bits;
552
553
554

	leaf = path->nodes[0];
	csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
555
	csum_end <<= fs_info->sb->s_blocksize_bits;
556
557
558
559
560
561
562
563
564
565
566
	csum_end += key->offset;

	if (key->offset < bytenr && csum_end <= end_byte) {
		/*
		 *         [ bytenr - len ]
		 *         [   ]
		 *   [csum     ]
		 *   A simple truncate off the end of the item
		 */
		u32 new_size = (bytenr - key->offset) >> blocksize_bits;
		new_size *= csum_size;
567
		btrfs_truncate_item(path, new_size, 1);
568
569
570
571
572
573
574
575
576
577
578
	} else if (key->offset >= bytenr && csum_end > end_byte &&
		   end_byte > key->offset) {
		/*
		 *         [ bytenr - len ]
		 *                 [ ]
		 *                 [csum     ]
		 * we need to truncate from the beginning of the csum
		 */
		u32 new_size = (csum_end - end_byte) >> blocksize_bits;
		new_size *= csum_size;

579
		btrfs_truncate_item(path, new_size, 0);
580
581

		key->offset = end_byte;
582
		btrfs_set_item_key_safe(fs_info, path, key);
583
584
585
586
587
588
589
590
591
592
	} else {
		BUG();
	}
}

/*
 * deletes the csum items from the csum tree for a given
 * range of bytes.
 */
int btrfs_del_csums(struct btrfs_trans_handle *trans,
593
		    struct btrfs_root *root, u64 bytenr, u64 len)
594
{
595
	struct btrfs_fs_info *fs_info = trans->fs_info;
596
597
598
599
600
601
	struct btrfs_path *path;
	struct btrfs_key key;
	u64 end_byte = bytenr + len;
	u64 csum_end;
	struct extent_buffer *leaf;
	int ret;
602
603
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
	int blocksize_bits = fs_info->sb->s_blocksize_bits;
604

605
606
607
	ASSERT(root == fs_info->csum_root ||
	       root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID);

608
	path = btrfs_alloc_path();
609
610
	if (!path)
		return -ENOMEM;
611

612
	while (1) {
613
614
615
616
		key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
		key.offset = end_byte - 1;
		key.type = BTRFS_EXTENT_CSUM_KEY;

617
		path->leave_spinning = 1;
618
619
620
		ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
		if (ret > 0) {
			if (path->slots[0] == 0)
621
				break;
622
			path->slots[0]--;
623
		} else if (ret < 0) {
624
			break;
625
		}
626

627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);

		if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
		    key.type != BTRFS_EXTENT_CSUM_KEY) {
			break;
		}

		if (key.offset >= end_byte)
			break;

		csum_end = btrfs_item_size_nr(leaf, path->slots[0]) / csum_size;
		csum_end <<= blocksize_bits;
		csum_end += key.offset;

		/* this csum ends before we start, we're done */
		if (csum_end <= bytenr)
			break;

		/* delete the entire item, it is inside our range */
		if (key.offset >= bytenr && csum_end <= end_byte) {
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
			int del_nr = 1;

			/*
			 * Check how many csum items preceding this one in this
			 * leaf correspond to our range and then delete them all
			 * at once.
			 */
			if (key.offset > bytenr && path->slots[0] > 0) {
				int slot = path->slots[0] - 1;

				while (slot >= 0) {
					struct btrfs_key pk;

					btrfs_item_key_to_cpu(leaf, &pk, slot);
					if (pk.offset < bytenr ||
					    pk.type != BTRFS_EXTENT_CSUM_KEY ||
					    pk.objectid !=
					    BTRFS_EXTENT_CSUM_OBJECTID)
						break;
					path->slots[0] = slot;
					del_nr++;
					key.offset = pk.offset;
					slot--;
				}
			}
			ret = btrfs_del_items(trans, root, path,
					      path->slots[0], del_nr);
675
676
			if (ret)
				goto out;
677
678
			if (key.offset == bytenr)
				break;
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
		} else if (key.offset < bytenr && csum_end > end_byte) {
			unsigned long offset;
			unsigned long shift_len;
			unsigned long item_offset;
			/*
			 *        [ bytenr - len ]
			 *     [csum                ]
			 *
			 * Our bytes are in the middle of the csum,
			 * we need to split this item and insert a new one.
			 *
			 * But we can't drop the path because the
			 * csum could change, get removed, extended etc.
			 *
			 * The trick here is the max size of a csum item leaves
			 * enough room in the tree block for a single
			 * item header.  So, we split the item in place,
			 * adding a new header pointing to the existing
			 * bytes.  Then we loop around again and we have
			 * a nicely formed csum item that we can neatly
			 * truncate.
			 */
			offset = (bytenr - key.offset) >> blocksize_bits;
			offset *= csum_size;

			shift_len = (len >> blocksize_bits) * csum_size;

			item_offset = btrfs_item_ptr_offset(leaf,
							    path->slots[0]);

709
			memzero_extent_buffer(leaf, item_offset + offset,
710
711
712
713
714
715
716
717
					     shift_len);
			key.offset = bytenr;

			/*
			 * btrfs_split_item returns -EAGAIN when the
			 * item changed size or key
			 */
			ret = btrfs_split_item(trans, root, path, &key, offset);
718
			if (ret && ret != -EAGAIN) {
719
				btrfs_abort_transaction(trans, ret);
720
721
				goto out;
			}
722
723
724

			key.offset = end_byte - 1;
		} else {
725
			truncate_one_csum(fs_info, path, &key, bytenr, len);
726
727
			if (key.offset < bytenr)
				break;
728
		}
729
		btrfs_release_path(path);
730
	}
731
	ret = 0;
732
733
out:
	btrfs_free_path(path);
734
	return ret;
735
736
}

737
int btrfs_csum_file_blocks(struct btrfs_trans_handle *trans,
738
			   struct btrfs_root *root,
739
			   struct btrfs_ordered_sum *sums)
Chris Mason's avatar
Chris Mason committed
740
{
741
	struct btrfs_fs_info *fs_info = root->fs_info;
Chris Mason's avatar
Chris Mason committed
742
	struct btrfs_key file_key;
743
	struct btrfs_key found_key;
744
	struct btrfs_path *path;
Chris Mason's avatar
Chris Mason committed
745
	struct btrfs_csum_item *item;
746
	struct btrfs_csum_item *item_end;
747
	struct extent_buffer *leaf = NULL;
748
749
	u64 next_offset;
	u64 total_bytes = 0;
750
	u64 csum_offset;
751
	u64 bytenr;
752
753
	u32 nritems;
	u32 ins_size;
754
755
756
	int index = 0;
	int found_next;
	int ret;
757
	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
758

759
	path = btrfs_alloc_path();
760
761
	if (!path)
		return -ENOMEM;
762
763
764
again:
	next_offset = (u64)-1;
	found_next = 0;
765
	bytenr = sums->bytenr + total_bytes;
766
	file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
767
	file_key.offset = bytenr;
768
	file_key.type = BTRFS_EXTENT_CSUM_KEY;
769

770
	item = btrfs_lookup_csum(trans, root, path, bytenr, 1);
771
	if (!IS_ERR(item)) {
772
		ret = 0;
773
774
775
776
777
		leaf = path->nodes[0];
		item_end = btrfs_item_ptr(leaf, path->slots[0],
					  struct btrfs_csum_item);
		item_end = (struct btrfs_csum_item *)((char *)item_end +
			   btrfs_item_size_nr(leaf, path->slots[0]));
778
		goto found;
779
	}
780
	ret = PTR_ERR(item);
781
782
783
	if (ret != -EFBIG && ret != -ENOENT)
		goto fail_unlock;

784
785
786
	if (ret == -EFBIG) {
		u32 item_size;
		/* we found one, but it isn't big enough yet */
787
788
		leaf = path->nodes[0];
		item_size = btrfs_item_size_nr(leaf, path->slots[0]);
789
		if ((item_size / csum_size) >=
790
		    MAX_CSUM_ITEMS(fs_info, csum_size)) {
791
792
793
794
			/* already at max size, make a new one */
			goto insert;
		}
	} else {
795
		int slot = path->slots[0] + 1;
796
		/* we didn't find a csum item, insert one */
797
		nritems = btrfs_header_nritems(path->nodes[0]);
798
		if (!nritems || (path->slots[0] >= nritems - 1)) {
799
			ret = btrfs_next_leaf(root, path);
Yan's avatar
Yan committed
800
			if (ret == 1)
801
				found_next = 1;
Yan's avatar
Yan committed
802
			if (ret != 0)
803
				goto insert;
804
			slot = path->slots[0];
805
806
		}
		btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
807
808
		if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
		    found_key.type != BTRFS_EXTENT_CSUM_KEY) {
809
810
811
812
813
			found_next = 1;
			goto insert;
		}
		next_offset = found_key.offset;
		found_next = 1;
814
815
816
817
818
819
820
		goto insert;
	}

	/*
	 * at this point, we know the tree has an item, but it isn't big
	 * enough yet to put our csum in.  Grow it
	 */
821
	btrfs_release_path(path);
822
	ret = btrfs_search_slot(trans, root, &file_key, path,
823
				csum_size, 1);
824
	if (ret < 0)
825
		goto fail_unlock;
826
827
828
829
830

	if (ret > 0) {
		if (path->slots[0] == 0)
			goto insert;
		path->slots[0]--;
831
	}
832

833
834
	leaf = path->nodes[0];
	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
835
	csum_offset = (bytenr - found_key.offset) >>
836
			fs_info->sb->s_blocksize_bits;
837

838
	if (found_key.type != BTRFS_EXTENT_CSUM_KEY ||
839
	    found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
840
	    csum_offset >= MAX_CSUM_ITEMS(fs_info, csum_size)) {
841
842
		goto insert;
	}
843

844
	if (csum_offset == btrfs_item_size_nr(leaf, path->slots[0]) /
845
	    csum_size) {
846
847
848
849
		int extend_nr;
		u64 tmp;
		u32 diff;
		u32 free_space;
850

851
		if (btrfs_leaf_free_space(leaf) <
852
853
854
				 sizeof(struct btrfs_item) + csum_size * 2)
			goto insert;

855
		free_space = btrfs_leaf_free_space(leaf) -
856
					 sizeof(struct btrfs_item) - csum_size;
857
		tmp = sums->len - total_bytes;
858
		tmp >>= fs_info->sb->s_blocksize_bits;
859
860
861
862
		WARN_ON(tmp < 1);

		extend_nr = max_t(int, 1, (int)tmp);
		diff = (csum_offset + extend_nr) * csum_size;
863
864
		diff = min(diff,
			   MAX_CSUM_ITEMS(fs_info, csum_size) * csum_size);
865

866
		diff = diff - btrfs_item_size_nr(leaf, path->slots[0]);
867
868
869
		diff = min(free_space, diff);
		diff /= csum_size;
		diff *= csum_size;
870

871
		btrfs_extend_item(path, diff);
872
		ret = 0;
873
874
875
876
		goto csum;
	}

insert:
877
	btrfs_release_path(path);
878
	csum_offset = 0;
879
	if (found_next) {
880
		u64 tmp;