1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2007 Oracle.  All rights reserved.
4  */
5 
6 #include <linux/slab.h>
7 #include <linux/blkdev.h>
8 #include <linux/writeback.h>
9 #include "ctree.h"
10 #include "transaction.h"
11 #include "btrfs_inode.h"
12 #include "extent_io.h"
13 #include "disk-io.h"
14 #include "compression.h"
15 
16 static struct kmem_cache *btrfs_ordered_extent_cache;
17 
entry_end(struct btrfs_ordered_extent * entry)18 static u64 entry_end(struct btrfs_ordered_extent *entry)
19 {
20 	if (entry->file_offset + entry->len < entry->file_offset)
21 		return (u64)-1;
22 	return entry->file_offset + entry->len;
23 }
24 
25 /* returns NULL if the insertion worked, or it returns the node it did find
26  * in the tree
27  */
tree_insert(struct rb_root * root,u64 file_offset,struct rb_node * node)28 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset,
29 				   struct rb_node *node)
30 {
31 	struct rb_node **p = &root->rb_node;
32 	struct rb_node *parent = NULL;
33 	struct btrfs_ordered_extent *entry;
34 
35 	while (*p) {
36 		parent = *p;
37 		entry = rb_entry(parent, struct btrfs_ordered_extent, rb_node);
38 
39 		if (file_offset < entry->file_offset)
40 			p = &(*p)->rb_left;
41 		else if (file_offset >= entry_end(entry))
42 			p = &(*p)->rb_right;
43 		else
44 			return parent;
45 	}
46 
47 	rb_link_node(node, parent, p);
48 	rb_insert_color(node, root);
49 	return NULL;
50 }
51 
ordered_data_tree_panic(struct inode * inode,int errno,u64 offset)52 static void ordered_data_tree_panic(struct inode *inode, int errno,
53 					       u64 offset)
54 {
55 	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
56 	btrfs_panic(fs_info, errno,
57 		    "Inconsistency in ordered tree at offset %llu", offset);
58 }
59 
60 /*
61  * look for a given offset in the tree, and if it can't be found return the
62  * first lesser offset
63  */
__tree_search(struct rb_root * root,u64 file_offset,struct rb_node ** prev_ret)64 static struct rb_node *__tree_search(struct rb_root *root, u64 file_offset,
65 				     struct rb_node **prev_ret)
66 {
67 	struct rb_node *n = root->rb_node;
68 	struct rb_node *prev = NULL;
69 	struct rb_node *test;
70 	struct btrfs_ordered_extent *entry;
71 	struct btrfs_ordered_extent *prev_entry = NULL;
72 
73 	while (n) {
74 		entry = rb_entry(n, struct btrfs_ordered_extent, rb_node);
75 		prev = n;
76 		prev_entry = entry;
77 
78 		if (file_offset < entry->file_offset)
79 			n = n->rb_left;
80 		else if (file_offset >= entry_end(entry))
81 			n = n->rb_right;
82 		else
83 			return n;
84 	}
85 	if (!prev_ret)
86 		return NULL;
87 
88 	while (prev && file_offset >= entry_end(prev_entry)) {
89 		test = rb_next(prev);
90 		if (!test)
91 			break;
92 		prev_entry = rb_entry(test, struct btrfs_ordered_extent,
93 				      rb_node);
94 		if (file_offset < entry_end(prev_entry))
95 			break;
96 
97 		prev = test;
98 	}
99 	if (prev)
100 		prev_entry = rb_entry(prev, struct btrfs_ordered_extent,
101 				      rb_node);
102 	while (prev && file_offset < entry_end(prev_entry)) {
103 		test = rb_prev(prev);
104 		if (!test)
105 			break;
106 		prev_entry = rb_entry(test, struct btrfs_ordered_extent,
107 				      rb_node);
108 		prev = test;
109 	}
110 	*prev_ret = prev;
111 	return NULL;
112 }
113 
114 /*
115  * helper to check if a given offset is inside a given entry
116  */
offset_in_entry(struct btrfs_ordered_extent * entry,u64 file_offset)117 static int offset_in_entry(struct btrfs_ordered_extent *entry, u64 file_offset)
118 {
119 	if (file_offset < entry->file_offset ||
120 	    entry->file_offset + entry->len <= file_offset)
121 		return 0;
122 	return 1;
123 }
124 
range_overlaps(struct btrfs_ordered_extent * entry,u64 file_offset,u64 len)125 static int range_overlaps(struct btrfs_ordered_extent *entry, u64 file_offset,
126 			  u64 len)
127 {
128 	if (file_offset + len <= entry->file_offset ||
129 	    entry->file_offset + entry->len <= file_offset)
130 		return 0;
131 	return 1;
132 }
133 
134 /*
135  * look find the first ordered struct that has this offset, otherwise
136  * the first one less than this offset
137  */
tree_search(struct btrfs_ordered_inode_tree * tree,u64 file_offset)138 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree,
139 					  u64 file_offset)
140 {
141 	struct rb_root *root = &tree->tree;
142 	struct rb_node *prev = NULL;
143 	struct rb_node *ret;
144 	struct btrfs_ordered_extent *entry;
145 
146 	if (tree->last) {
147 		entry = rb_entry(tree->last, struct btrfs_ordered_extent,
148 				 rb_node);
149 		if (offset_in_entry(entry, file_offset))
150 			return tree->last;
151 	}
152 	ret = __tree_search(root, file_offset, &prev);
153 	if (!ret)
154 		ret = prev;
155 	if (ret)
156 		tree->last = ret;
157 	return ret;
158 }
159 
160 /* allocate and add a new ordered_extent into the per-inode tree.
161  * file_offset is the logical offset in the file
162  *
163  * start is the disk block number of an extent already reserved in the
164  * extent allocation tree
165  *
166  * len is the length of the extent
167  *
168  * The tree is given a single reference on the ordered extent that was
169  * inserted.
170  */
__btrfs_add_ordered_extent(struct inode * inode,u64 file_offset,u64 start,u64 len,u64 disk_len,int type,int dio,int compress_type)171 static int __btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
172 				      u64 start, u64 len, u64 disk_len,
173 				      int type, int dio, int compress_type)
174 {
175 	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
176 	struct btrfs_root *root = BTRFS_I(inode)->root;
177 	struct btrfs_ordered_inode_tree *tree;
178 	struct rb_node *node;
179 	struct btrfs_ordered_extent *entry;
180 
181 	tree = &BTRFS_I(inode)->ordered_tree;
182 	entry = kmem_cache_zalloc(btrfs_ordered_extent_cache, GFP_NOFS);
183 	if (!entry)
184 		return -ENOMEM;
185 
186 	entry->file_offset = file_offset;
187 	entry->start = start;
188 	entry->len = len;
189 	entry->disk_len = disk_len;
190 	entry->bytes_left = len;
191 	entry->inode = igrab(inode);
192 	entry->compress_type = compress_type;
193 	entry->truncated_len = (u64)-1;
194 	if (type != BTRFS_ORDERED_IO_DONE && type != BTRFS_ORDERED_COMPLETE)
195 		set_bit(type, &entry->flags);
196 
197 	if (dio)
198 		set_bit(BTRFS_ORDERED_DIRECT, &entry->flags);
199 
200 	/* one ref for the tree */
201 	refcount_set(&entry->refs, 1);
202 	init_waitqueue_head(&entry->wait);
203 	INIT_LIST_HEAD(&entry->list);
204 	INIT_LIST_HEAD(&entry->root_extent_list);
205 	INIT_LIST_HEAD(&entry->work_list);
206 	init_completion(&entry->completion);
207 	INIT_LIST_HEAD(&entry->log_list);
208 	INIT_LIST_HEAD(&entry->trans_list);
209 
210 	trace_btrfs_ordered_extent_add(inode, entry);
211 
212 	spin_lock_irq(&tree->lock);
213 	node = tree_insert(&tree->tree, file_offset,
214 			   &entry->rb_node);
215 	if (node)
216 		ordered_data_tree_panic(inode, -EEXIST, file_offset);
217 	spin_unlock_irq(&tree->lock);
218 
219 	spin_lock(&root->ordered_extent_lock);
220 	list_add_tail(&entry->root_extent_list,
221 		      &root->ordered_extents);
222 	root->nr_ordered_extents++;
223 	if (root->nr_ordered_extents == 1) {
224 		spin_lock(&fs_info->ordered_root_lock);
225 		BUG_ON(!list_empty(&root->ordered_root));
226 		list_add_tail(&root->ordered_root, &fs_info->ordered_roots);
227 		spin_unlock(&fs_info->ordered_root_lock);
228 	}
229 	spin_unlock(&root->ordered_extent_lock);
230 
231 	/*
232 	 * We don't need the count_max_extents here, we can assume that all of
233 	 * that work has been done at higher layers, so this is truly the
234 	 * smallest the extent is going to get.
235 	 */
236 	spin_lock(&BTRFS_I(inode)->lock);
237 	btrfs_mod_outstanding_extents(BTRFS_I(inode), 1);
238 	spin_unlock(&BTRFS_I(inode)->lock);
239 
240 	return 0;
241 }
242 
btrfs_add_ordered_extent(struct inode * inode,u64 file_offset,u64 start,u64 len,u64 disk_len,int type)243 int btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
244 			     u64 start, u64 len, u64 disk_len, int type)
245 {
246 	return __btrfs_add_ordered_extent(inode, file_offset, start, len,
247 					  disk_len, type, 0,
248 					  BTRFS_COMPRESS_NONE);
249 }
250 
btrfs_add_ordered_extent_dio(struct inode * inode,u64 file_offset,u64 start,u64 len,u64 disk_len,int type)251 int btrfs_add_ordered_extent_dio(struct inode *inode, u64 file_offset,
252 				 u64 start, u64 len, u64 disk_len, int type)
253 {
254 	return __btrfs_add_ordered_extent(inode, file_offset, start, len,
255 					  disk_len, type, 1,
256 					  BTRFS_COMPRESS_NONE);
257 }
258 
btrfs_add_ordered_extent_compress(struct inode * inode,u64 file_offset,u64 start,u64 len,u64 disk_len,int type,int compress_type)259 int btrfs_add_ordered_extent_compress(struct inode *inode, u64 file_offset,
260 				      u64 start, u64 len, u64 disk_len,
261 				      int type, int compress_type)
262 {
263 	return __btrfs_add_ordered_extent(inode, file_offset, start, len,
264 					  disk_len, type, 0,
265 					  compress_type);
266 }
267 
268 /*
269  * Add a struct btrfs_ordered_sum into the list of checksums to be inserted
270  * when an ordered extent is finished.  If the list covers more than one
271  * ordered extent, it is split across multiples.
272  */
btrfs_add_ordered_sum(struct inode * inode,struct btrfs_ordered_extent * entry,struct btrfs_ordered_sum * sum)273 void btrfs_add_ordered_sum(struct inode *inode,
274 			   struct btrfs_ordered_extent *entry,
275 			   struct btrfs_ordered_sum *sum)
276 {
277 	struct btrfs_ordered_inode_tree *tree;
278 
279 	tree = &BTRFS_I(inode)->ordered_tree;
280 	spin_lock_irq(&tree->lock);
281 	list_add_tail(&sum->list, &entry->list);
282 	spin_unlock_irq(&tree->lock);
283 }
284 
285 /*
286  * this is used to account for finished IO across a given range
287  * of the file.  The IO may span ordered extents.  If
288  * a given ordered_extent is completely done, 1 is returned, otherwise
289  * 0.
290  *
291  * test_and_set_bit on a flag in the struct btrfs_ordered_extent is used
292  * to make sure this function only returns 1 once for a given ordered extent.
293  *
294  * file_offset is updated to one byte past the range that is recorded as
295  * complete.  This allows you to walk forward in the file.
296  */
btrfs_dec_test_first_ordered_pending(struct inode * inode,struct btrfs_ordered_extent ** cached,u64 * file_offset,u64 io_size,int uptodate)297 int btrfs_dec_test_first_ordered_pending(struct inode *inode,
298 				   struct btrfs_ordered_extent **cached,
299 				   u64 *file_offset, u64 io_size, int uptodate)
300 {
301 	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
302 	struct btrfs_ordered_inode_tree *tree;
303 	struct rb_node *node;
304 	struct btrfs_ordered_extent *entry = NULL;
305 	int ret;
306 	unsigned long flags;
307 	u64 dec_end;
308 	u64 dec_start;
309 	u64 to_dec;
310 
311 	tree = &BTRFS_I(inode)->ordered_tree;
312 	spin_lock_irqsave(&tree->lock, flags);
313 	node = tree_search(tree, *file_offset);
314 	if (!node) {
315 		ret = 1;
316 		goto out;
317 	}
318 
319 	entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
320 	if (!offset_in_entry(entry, *file_offset)) {
321 		ret = 1;
322 		goto out;
323 	}
324 
325 	dec_start = max(*file_offset, entry->file_offset);
326 	dec_end = min(*file_offset + io_size, entry->file_offset +
327 		      entry->len);
328 	*file_offset = dec_end;
329 	if (dec_start > dec_end) {
330 		btrfs_crit(fs_info, "bad ordering dec_start %llu end %llu",
331 			   dec_start, dec_end);
332 	}
333 	to_dec = dec_end - dec_start;
334 	if (to_dec > entry->bytes_left) {
335 		btrfs_crit(fs_info,
336 			   "bad ordered accounting left %llu size %llu",
337 			   entry->bytes_left, to_dec);
338 	}
339 	entry->bytes_left -= to_dec;
340 	if (!uptodate)
341 		set_bit(BTRFS_ORDERED_IOERR, &entry->flags);
342 
343 	if (entry->bytes_left == 0) {
344 		ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags);
345 		/* test_and_set_bit implies a barrier */
346 		cond_wake_up_nomb(&entry->wait);
347 	} else {
348 		ret = 1;
349 	}
350 out:
351 	if (!ret && cached && entry) {
352 		*cached = entry;
353 		refcount_inc(&entry->refs);
354 	}
355 	spin_unlock_irqrestore(&tree->lock, flags);
356 	return ret == 0;
357 }
358 
359 /*
360  * this is used to account for finished IO across a given range
361  * of the file.  The IO should not span ordered extents.  If
362  * a given ordered_extent is completely done, 1 is returned, otherwise
363  * 0.
364  *
365  * test_and_set_bit on a flag in the struct btrfs_ordered_extent is used
366  * to make sure this function only returns 1 once for a given ordered extent.
367  */
btrfs_dec_test_ordered_pending(struct inode * inode,struct btrfs_ordered_extent ** cached,u64 file_offset,u64 io_size,int uptodate)368 int btrfs_dec_test_ordered_pending(struct inode *inode,
369 				   struct btrfs_ordered_extent **cached,
370 				   u64 file_offset, u64 io_size, int uptodate)
371 {
372 	struct btrfs_ordered_inode_tree *tree;
373 	struct rb_node *node;
374 	struct btrfs_ordered_extent *entry = NULL;
375 	unsigned long flags;
376 	int ret;
377 
378 	tree = &BTRFS_I(inode)->ordered_tree;
379 	spin_lock_irqsave(&tree->lock, flags);
380 	if (cached && *cached) {
381 		entry = *cached;
382 		goto have_entry;
383 	}
384 
385 	node = tree_search(tree, file_offset);
386 	if (!node) {
387 		ret = 1;
388 		goto out;
389 	}
390 
391 	entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
392 have_entry:
393 	if (!offset_in_entry(entry, file_offset)) {
394 		ret = 1;
395 		goto out;
396 	}
397 
398 	if (io_size > entry->bytes_left) {
399 		btrfs_crit(BTRFS_I(inode)->root->fs_info,
400 			   "bad ordered accounting left %llu size %llu",
401 		       entry->bytes_left, io_size);
402 	}
403 	entry->bytes_left -= io_size;
404 	if (!uptodate)
405 		set_bit(BTRFS_ORDERED_IOERR, &entry->flags);
406 
407 	if (entry->bytes_left == 0) {
408 		ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags);
409 		/* test_and_set_bit implies a barrier */
410 		cond_wake_up_nomb(&entry->wait);
411 	} else {
412 		ret = 1;
413 	}
414 out:
415 	if (!ret && cached && entry) {
416 		*cached = entry;
417 		refcount_inc(&entry->refs);
418 	}
419 	spin_unlock_irqrestore(&tree->lock, flags);
420 	return ret == 0;
421 }
422 
423 /*
424  * used to drop a reference on an ordered extent.  This will free
425  * the extent if the last reference is dropped
426  */
btrfs_put_ordered_extent(struct btrfs_ordered_extent * entry)427 void btrfs_put_ordered_extent(struct btrfs_ordered_extent *entry)
428 {
429 	struct list_head *cur;
430 	struct btrfs_ordered_sum *sum;
431 
432 	trace_btrfs_ordered_extent_put(entry->inode, entry);
433 
434 	if (refcount_dec_and_test(&entry->refs)) {
435 		ASSERT(list_empty(&entry->log_list));
436 		ASSERT(list_empty(&entry->trans_list));
437 		ASSERT(list_empty(&entry->root_extent_list));
438 		ASSERT(RB_EMPTY_NODE(&entry->rb_node));
439 		if (entry->inode)
440 			btrfs_add_delayed_iput(entry->inode);
441 		while (!list_empty(&entry->list)) {
442 			cur = entry->list.next;
443 			sum = list_entry(cur, struct btrfs_ordered_sum, list);
444 			list_del(&sum->list);
445 			kfree(sum);
446 		}
447 		kmem_cache_free(btrfs_ordered_extent_cache, entry);
448 	}
449 }
450 
451 /*
452  * remove an ordered extent from the tree.  No references are dropped
453  * and waiters are woken up.
454  */
btrfs_remove_ordered_extent(struct inode * inode,struct btrfs_ordered_extent * entry)455 void btrfs_remove_ordered_extent(struct inode *inode,
456 				 struct btrfs_ordered_extent *entry)
457 {
458 	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
459 	struct btrfs_ordered_inode_tree *tree;
460 	struct btrfs_inode *btrfs_inode = BTRFS_I(inode);
461 	struct btrfs_root *root = btrfs_inode->root;
462 	struct rb_node *node;
463 	bool dec_pending_ordered = false;
464 
465 	/* This is paired with btrfs_add_ordered_extent. */
466 	spin_lock(&btrfs_inode->lock);
467 	btrfs_mod_outstanding_extents(btrfs_inode, -1);
468 	spin_unlock(&btrfs_inode->lock);
469 	if (root != fs_info->tree_root)
470 		btrfs_delalloc_release_metadata(btrfs_inode, entry->len, false);
471 
472 	tree = &btrfs_inode->ordered_tree;
473 	spin_lock_irq(&tree->lock);
474 	node = &entry->rb_node;
475 	rb_erase(node, &tree->tree);
476 	RB_CLEAR_NODE(node);
477 	if (tree->last == node)
478 		tree->last = NULL;
479 	set_bit(BTRFS_ORDERED_COMPLETE, &entry->flags);
480 	if (test_and_clear_bit(BTRFS_ORDERED_PENDING, &entry->flags))
481 		dec_pending_ordered = true;
482 	spin_unlock_irq(&tree->lock);
483 
484 	/*
485 	 * The current running transaction is waiting on us, we need to let it
486 	 * know that we're complete and wake it up.
487 	 */
488 	if (dec_pending_ordered) {
489 		struct btrfs_transaction *trans;
490 
491 		/*
492 		 * The checks for trans are just a formality, it should be set,
493 		 * but if it isn't we don't want to deref/assert under the spin
494 		 * lock, so be nice and check if trans is set, but ASSERT() so
495 		 * if it isn't set a developer will notice.
496 		 */
497 		spin_lock(&fs_info->trans_lock);
498 		trans = fs_info->running_transaction;
499 		if (trans)
500 			refcount_inc(&trans->use_count);
501 		spin_unlock(&fs_info->trans_lock);
502 
503 		ASSERT(trans);
504 		if (trans) {
505 			if (atomic_dec_and_test(&trans->pending_ordered))
506 				wake_up(&trans->pending_wait);
507 			btrfs_put_transaction(trans);
508 		}
509 	}
510 
511 	spin_lock(&root->ordered_extent_lock);
512 	list_del_init(&entry->root_extent_list);
513 	root->nr_ordered_extents--;
514 
515 	trace_btrfs_ordered_extent_remove(inode, entry);
516 
517 	if (!root->nr_ordered_extents) {
518 		spin_lock(&fs_info->ordered_root_lock);
519 		BUG_ON(list_empty(&root->ordered_root));
520 		list_del_init(&root->ordered_root);
521 		spin_unlock(&fs_info->ordered_root_lock);
522 	}
523 	spin_unlock(&root->ordered_extent_lock);
524 	wake_up(&entry->wait);
525 }
526 
btrfs_run_ordered_extent_work(struct btrfs_work * work)527 static void btrfs_run_ordered_extent_work(struct btrfs_work *work)
528 {
529 	struct btrfs_ordered_extent *ordered;
530 
531 	ordered = container_of(work, struct btrfs_ordered_extent, flush_work);
532 	btrfs_start_ordered_extent(ordered->inode, ordered, 1);
533 	complete(&ordered->completion);
534 }
535 
536 /*
537  * wait for all the ordered extents in a root.  This is done when balancing
538  * space between drives.
539  */
btrfs_wait_ordered_extents(struct btrfs_root * root,u64 nr,const u64 range_start,const u64 range_len)540 u64 btrfs_wait_ordered_extents(struct btrfs_root *root, u64 nr,
541 			       const u64 range_start, const u64 range_len)
542 {
543 	struct btrfs_fs_info *fs_info = root->fs_info;
544 	LIST_HEAD(splice);
545 	LIST_HEAD(skipped);
546 	LIST_HEAD(works);
547 	struct btrfs_ordered_extent *ordered, *next;
548 	u64 count = 0;
549 	const u64 range_end = range_start + range_len;
550 
551 	mutex_lock(&root->ordered_extent_mutex);
552 	spin_lock(&root->ordered_extent_lock);
553 	list_splice_init(&root->ordered_extents, &splice);
554 	while (!list_empty(&splice) && nr) {
555 		ordered = list_first_entry(&splice, struct btrfs_ordered_extent,
556 					   root_extent_list);
557 
558 		if (range_end <= ordered->start ||
559 		    ordered->start + ordered->disk_len <= range_start) {
560 			list_move_tail(&ordered->root_extent_list, &skipped);
561 			cond_resched_lock(&root->ordered_extent_lock);
562 			continue;
563 		}
564 
565 		list_move_tail(&ordered->root_extent_list,
566 			       &root->ordered_extents);
567 		refcount_inc(&ordered->refs);
568 		spin_unlock(&root->ordered_extent_lock);
569 
570 		btrfs_init_work(&ordered->flush_work,
571 				btrfs_flush_delalloc_helper,
572 				btrfs_run_ordered_extent_work, NULL, NULL);
573 		list_add_tail(&ordered->work_list, &works);
574 		btrfs_queue_work(fs_info->flush_workers, &ordered->flush_work);
575 
576 		cond_resched();
577 		spin_lock(&root->ordered_extent_lock);
578 		if (nr != U64_MAX)
579 			nr--;
580 		count++;
581 	}
582 	list_splice_tail(&skipped, &root->ordered_extents);
583 	list_splice_tail(&splice, &root->ordered_extents);
584 	spin_unlock(&root->ordered_extent_lock);
585 
586 	list_for_each_entry_safe(ordered, next, &works, work_list) {
587 		list_del_init(&ordered->work_list);
588 		wait_for_completion(&ordered->completion);
589 		btrfs_put_ordered_extent(ordered);
590 		cond_resched();
591 	}
592 	mutex_unlock(&root->ordered_extent_mutex);
593 
594 	return count;
595 }
596 
btrfs_wait_ordered_roots(struct btrfs_fs_info * fs_info,u64 nr,const u64 range_start,const u64 range_len)597 u64 btrfs_wait_ordered_roots(struct btrfs_fs_info *fs_info, u64 nr,
598 			     const u64 range_start, const u64 range_len)
599 {
600 	struct btrfs_root *root;
601 	struct list_head splice;
602 	u64 total_done = 0;
603 	u64 done;
604 
605 	INIT_LIST_HEAD(&splice);
606 
607 	mutex_lock(&fs_info->ordered_operations_mutex);
608 	spin_lock(&fs_info->ordered_root_lock);
609 	list_splice_init(&fs_info->ordered_roots, &splice);
610 	while (!list_empty(&splice) && nr) {
611 		root = list_first_entry(&splice, struct btrfs_root,
612 					ordered_root);
613 		root = btrfs_grab_fs_root(root);
614 		BUG_ON(!root);
615 		list_move_tail(&root->ordered_root,
616 			       &fs_info->ordered_roots);
617 		spin_unlock(&fs_info->ordered_root_lock);
618 
619 		done = btrfs_wait_ordered_extents(root, nr,
620 						  range_start, range_len);
621 		btrfs_put_fs_root(root);
622 		total_done += done;
623 
624 		spin_lock(&fs_info->ordered_root_lock);
625 		if (nr != U64_MAX) {
626 			nr -= done;
627 		}
628 	}
629 	list_splice_tail(&splice, &fs_info->ordered_roots);
630 	spin_unlock(&fs_info->ordered_root_lock);
631 	mutex_unlock(&fs_info->ordered_operations_mutex);
632 
633 	return total_done;
634 }
635 
636 /*
637  * Used to start IO or wait for a given ordered extent to finish.
638  *
639  * If wait is one, this effectively waits on page writeback for all the pages
640  * in the extent, and it waits on the io completion code to insert
641  * metadata into the btree corresponding to the extent
642  */
btrfs_start_ordered_extent(struct inode * inode,struct btrfs_ordered_extent * entry,int wait)643 void btrfs_start_ordered_extent(struct inode *inode,
644 				       struct btrfs_ordered_extent *entry,
645 				       int wait)
646 {
647 	u64 start = entry->file_offset;
648 	u64 end = start + entry->len - 1;
649 
650 	trace_btrfs_ordered_extent_start(inode, entry);
651 
652 	/*
653 	 * pages in the range can be dirty, clean or writeback.  We
654 	 * start IO on any dirty ones so the wait doesn't stall waiting
655 	 * for the flusher thread to find them
656 	 */
657 	if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags))
658 		filemap_fdatawrite_range(inode->i_mapping, start, end);
659 	if (wait) {
660 		wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE,
661 						 &entry->flags));
662 	}
663 }
664 
665 /*
666  * Used to wait on ordered extents across a large range of bytes.
667  */
btrfs_wait_ordered_range(struct inode * inode,u64 start,u64 len)668 int btrfs_wait_ordered_range(struct inode *inode, u64 start, u64 len)
669 {
670 	int ret = 0;
671 	int ret_wb = 0;
672 	u64 end;
673 	u64 orig_end;
674 	struct btrfs_ordered_extent *ordered;
675 
676 	if (start + len < start) {
677 		orig_end = INT_LIMIT(loff_t);
678 	} else {
679 		orig_end = start + len - 1;
680 		if (orig_end > INT_LIMIT(loff_t))
681 			orig_end = INT_LIMIT(loff_t);
682 	}
683 
684 	/* start IO across the range first to instantiate any delalloc
685 	 * extents
686 	 */
687 	ret = btrfs_fdatawrite_range(inode, start, orig_end);
688 	if (ret)
689 		return ret;
690 
691 	/*
692 	 * If we have a writeback error don't return immediately. Wait first
693 	 * for any ordered extents that haven't completed yet. This is to make
694 	 * sure no one can dirty the same page ranges and call writepages()
695 	 * before the ordered extents complete - to avoid failures (-EEXIST)
696 	 * when adding the new ordered extents to the ordered tree.
697 	 */
698 	ret_wb = filemap_fdatawait_range(inode->i_mapping, start, orig_end);
699 
700 	end = orig_end;
701 	while (1) {
702 		ordered = btrfs_lookup_first_ordered_extent(inode, end);
703 		if (!ordered)
704 			break;
705 		if (ordered->file_offset > orig_end) {
706 			btrfs_put_ordered_extent(ordered);
707 			break;
708 		}
709 		if (ordered->file_offset + ordered->len <= start) {
710 			btrfs_put_ordered_extent(ordered);
711 			break;
712 		}
713 		btrfs_start_ordered_extent(inode, ordered, 1);
714 		end = ordered->file_offset;
715 		/*
716 		 * If the ordered extent had an error save the error but don't
717 		 * exit without waiting first for all other ordered extents in
718 		 * the range to complete.
719 		 */
720 		if (test_bit(BTRFS_ORDERED_IOERR, &ordered->flags))
721 			ret = -EIO;
722 		btrfs_put_ordered_extent(ordered);
723 		if (end == 0 || end == start)
724 			break;
725 		end--;
726 	}
727 	return ret_wb ? ret_wb : ret;
728 }
729 
730 /*
731  * find an ordered extent corresponding to file_offset.  return NULL if
732  * nothing is found, otherwise take a reference on the extent and return it
733  */
btrfs_lookup_ordered_extent(struct inode * inode,u64 file_offset)734 struct btrfs_ordered_extent *btrfs_lookup_ordered_extent(struct inode *inode,
735 							 u64 file_offset)
736 {
737 	struct btrfs_ordered_inode_tree *tree;
738 	struct rb_node *node;
739 	struct btrfs_ordered_extent *entry = NULL;
740 
741 	tree = &BTRFS_I(inode)->ordered_tree;
742 	spin_lock_irq(&tree->lock);
743 	node = tree_search(tree, file_offset);
744 	if (!node)
745 		goto out;
746 
747 	entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
748 	if (!offset_in_entry(entry, file_offset))
749 		entry = NULL;
750 	if (entry)
751 		refcount_inc(&entry->refs);
752 out:
753 	spin_unlock_irq(&tree->lock);
754 	return entry;
755 }
756 
757 /* Since the DIO code tries to lock a wide area we need to look for any ordered
758  * extents that exist in the range, rather than just the start of the range.
759  */
btrfs_lookup_ordered_range(struct btrfs_inode * inode,u64 file_offset,u64 len)760 struct btrfs_ordered_extent *btrfs_lookup_ordered_range(
761 		struct btrfs_inode *inode, u64 file_offset, u64 len)
762 {
763 	struct btrfs_ordered_inode_tree *tree;
764 	struct rb_node *node;
765 	struct btrfs_ordered_extent *entry = NULL;
766 
767 	tree = &inode->ordered_tree;
768 	spin_lock_irq(&tree->lock);
769 	node = tree_search(tree, file_offset);
770 	if (!node) {
771 		node = tree_search(tree, file_offset + len);
772 		if (!node)
773 			goto out;
774 	}
775 
776 	while (1) {
777 		entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
778 		if (range_overlaps(entry, file_offset, len))
779 			break;
780 
781 		if (entry->file_offset >= file_offset + len) {
782 			entry = NULL;
783 			break;
784 		}
785 		entry = NULL;
786 		node = rb_next(node);
787 		if (!node)
788 			break;
789 	}
790 out:
791 	if (entry)
792 		refcount_inc(&entry->refs);
793 	spin_unlock_irq(&tree->lock);
794 	return entry;
795 }
796 
797 /*
798  * lookup and return any extent before 'file_offset'.  NULL is returned
799  * if none is found
800  */
801 struct btrfs_ordered_extent *
btrfs_lookup_first_ordered_extent(struct inode * inode,u64 file_offset)802 btrfs_lookup_first_ordered_extent(struct inode *inode, u64 file_offset)
803 {
804 	struct btrfs_ordered_inode_tree *tree;
805 	struct rb_node *node;
806 	struct btrfs_ordered_extent *entry = NULL;
807 
808 	tree = &BTRFS_I(inode)->ordered_tree;
809 	spin_lock_irq(&tree->lock);
810 	node = tree_search(tree, file_offset);
811 	if (!node)
812 		goto out;
813 
814 	entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
815 	refcount_inc(&entry->refs);
816 out:
817 	spin_unlock_irq(&tree->lock);
818 	return entry;
819 }
820 
821 /*
822  * After an extent is done, call this to conditionally update the on disk
823  * i_size.  i_size is updated to cover any fully written part of the file.
824  */
btrfs_ordered_update_i_size(struct inode * inode,u64 offset,struct btrfs_ordered_extent * ordered)825 int btrfs_ordered_update_i_size(struct inode *inode, u64 offset,
826 				struct btrfs_ordered_extent *ordered)
827 {
828 	struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree;
829 	u64 disk_i_size;
830 	u64 new_i_size;
831 	u64 i_size = i_size_read(inode);
832 	struct rb_node *node;
833 	struct rb_node *prev = NULL;
834 	struct btrfs_ordered_extent *test;
835 	int ret = 1;
836 	u64 orig_offset = offset;
837 
838 	spin_lock_irq(&tree->lock);
839 	if (ordered) {
840 		offset = entry_end(ordered);
841 		if (test_bit(BTRFS_ORDERED_TRUNCATED, &ordered->flags))
842 			offset = min(offset,
843 				     ordered->file_offset +
844 				     ordered->truncated_len);
845 	} else {
846 		offset = ALIGN(offset, btrfs_inode_sectorsize(inode));
847 	}
848 	disk_i_size = BTRFS_I(inode)->disk_i_size;
849 
850 	/*
851 	 * truncate file.
852 	 * If ordered is not NULL, then this is called from endio and
853 	 * disk_i_size will be updated by either truncate itself or any
854 	 * in-flight IOs which are inside the disk_i_size.
855 	 *
856 	 * Because btrfs_setsize() may set i_size with disk_i_size if truncate
857 	 * fails somehow, we need to make sure we have a precise disk_i_size by
858 	 * updating it as usual.
859 	 *
860 	 */
861 	if (!ordered && disk_i_size > i_size) {
862 		BTRFS_I(inode)->disk_i_size = orig_offset;
863 		ret = 0;
864 		goto out;
865 	}
866 
867 	/*
868 	 * if the disk i_size is already at the inode->i_size, or
869 	 * this ordered extent is inside the disk i_size, we're done
870 	 */
871 	if (disk_i_size == i_size)
872 		goto out;
873 
874 	/*
875 	 * We still need to update disk_i_size if outstanding_isize is greater
876 	 * than disk_i_size.
877 	 */
878 	if (offset <= disk_i_size &&
879 	    (!ordered || ordered->outstanding_isize <= disk_i_size))
880 		goto out;
881 
882 	/*
883 	 * walk backward from this ordered extent to disk_i_size.
884 	 * if we find an ordered extent then we can't update disk i_size
885 	 * yet
886 	 */
887 	if (ordered) {
888 		node = rb_prev(&ordered->rb_node);
889 	} else {
890 		prev = tree_search(tree, offset);
891 		/*
892 		 * we insert file extents without involving ordered struct,
893 		 * so there should be no ordered struct cover this offset
894 		 */
895 		if (prev) {
896 			test = rb_entry(prev, struct btrfs_ordered_extent,
897 					rb_node);
898 			BUG_ON(offset_in_entry(test, offset));
899 		}
900 		node = prev;
901 	}
902 	for (; node; node = rb_prev(node)) {
903 		test = rb_entry(node, struct btrfs_ordered_extent, rb_node);
904 
905 		/* We treat this entry as if it doesn't exist */
906 		if (test_bit(BTRFS_ORDERED_UPDATED_ISIZE, &test->flags))
907 			continue;
908 
909 		if (entry_end(test) <= disk_i_size)
910 			break;
911 		if (test->file_offset >= i_size)
912 			break;
913 
914 		/*
915 		 * We don't update disk_i_size now, so record this undealt
916 		 * i_size. Or we will not know the real i_size.
917 		 */
918 		if (test->outstanding_isize < offset)
919 			test->outstanding_isize = offset;
920 		if (ordered &&
921 		    ordered->outstanding_isize > test->outstanding_isize)
922 			test->outstanding_isize = ordered->outstanding_isize;
923 		goto out;
924 	}
925 	new_i_size = min_t(u64, offset, i_size);
926 
927 	/*
928 	 * Some ordered extents may completed before the current one, and
929 	 * we hold the real i_size in ->outstanding_isize.
930 	 */
931 	if (ordered && ordered->outstanding_isize > new_i_size)
932 		new_i_size = min_t(u64, ordered->outstanding_isize, i_size);
933 	BTRFS_I(inode)->disk_i_size = new_i_size;
934 	ret = 0;
935 out:
936 	/*
937 	 * We need to do this because we can't remove ordered extents until
938 	 * after the i_disk_size has been updated and then the inode has been
939 	 * updated to reflect the change, so we need to tell anybody who finds
940 	 * this ordered extent that we've already done all the real work, we
941 	 * just haven't completed all the other work.
942 	 */
943 	if (ordered)
944 		set_bit(BTRFS_ORDERED_UPDATED_ISIZE, &ordered->flags);
945 	spin_unlock_irq(&tree->lock);
946 	return ret;
947 }
948 
949 /*
950  * search the ordered extents for one corresponding to 'offset' and
951  * try to find a checksum.  This is used because we allow pages to
952  * be reclaimed before their checksum is actually put into the btree
953  */
btrfs_find_ordered_sum(struct inode * inode,u64 offset,u64 disk_bytenr,u32 * sum,int len)954 int btrfs_find_ordered_sum(struct inode *inode, u64 offset, u64 disk_bytenr,
955 			   u32 *sum, int len)
956 {
957 	struct btrfs_ordered_sum *ordered_sum;
958 	struct btrfs_ordered_extent *ordered;
959 	struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree;
960 	unsigned long num_sectors;
961 	unsigned long i;
962 	u32 sectorsize = btrfs_inode_sectorsize(inode);
963 	int index = 0;
964 
965 	ordered = btrfs_lookup_ordered_extent(inode, offset);
966 	if (!ordered)
967 		return 0;
968 
969 	spin_lock_irq(&tree->lock);
970 	list_for_each_entry_reverse(ordered_sum, &ordered->list, list) {
971 		if (disk_bytenr >= ordered_sum->bytenr &&
972 		    disk_bytenr < ordered_sum->bytenr + ordered_sum->len) {
973 			i = (disk_bytenr - ordered_sum->bytenr) >>
974 			    inode->i_sb->s_blocksize_bits;
975 			num_sectors = ordered_sum->len >>
976 				      inode->i_sb->s_blocksize_bits;
977 			num_sectors = min_t(int, len - index, num_sectors - i);
978 			memcpy(sum + index, ordered_sum->sums + i,
979 			       num_sectors);
980 
981 			index += (int)num_sectors;
982 			if (index == len)
983 				goto out;
984 			disk_bytenr += num_sectors * sectorsize;
985 		}
986 	}
987 out:
988 	spin_unlock_irq(&tree->lock);
989 	btrfs_put_ordered_extent(ordered);
990 	return index;
991 }
992 
ordered_data_init(void)993 int __init ordered_data_init(void)
994 {
995 	btrfs_ordered_extent_cache = kmem_cache_create("btrfs_ordered_extent",
996 				     sizeof(struct btrfs_ordered_extent), 0,
997 				     SLAB_MEM_SPREAD,
998 				     NULL);
999 	if (!btrfs_ordered_extent_cache)
1000 		return -ENOMEM;
1001 
1002 	return 0;
1003 }
1004 
ordered_data_exit(void)1005 void __cold ordered_data_exit(void)
1006 {
1007 	kmem_cache_destroy(btrfs_ordered_extent_cache);
1008 }
1009