blob: ae94117733973e2d7aa8ea590c171fcf2e6bd26a [file] [log] [blame]
Chris Mason56bec292009-03-13 10:10:06 -04001/*
2 * Copyright (C) 2009 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
19#include <linux/sched.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090020#include <linux/slab.h>
Chris Mason56bec292009-03-13 10:10:06 -040021#include <linux/sort.h>
Chris Mason56bec292009-03-13 10:10:06 -040022#include "ctree.h"
23#include "delayed-ref.h"
24#include "transaction.h"
25
26/*
27 * delayed back reference update tracking. For subvolume trees
28 * we queue up extent allocations and backref maintenance for
29 * delayed processing. This avoids deep call chains where we
30 * add extents in the middle of btrfs_search_slot, and it allows
31 * us to buffer up frequently modified backrefs in an rb tree instead
32 * of hammering updates on the extent allocation tree.
Chris Mason56bec292009-03-13 10:10:06 -040033 */
34
35/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -040036 * compare two delayed tree backrefs with same bytenr and type
Chris Mason56bec292009-03-13 10:10:06 -040037 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -040038static int comp_tree_refs(struct btrfs_delayed_tree_ref *ref2,
39 struct btrfs_delayed_tree_ref *ref1)
Chris Mason56bec292009-03-13 10:10:06 -040040{
Josef Bacikae1e2062012-08-07 16:00:32 -040041 if (ref1->root < ref2->root)
42 return -1;
43 if (ref1->root > ref2->root)
44 return 1;
45 if (ref1->parent < ref2->parent)
46 return -1;
47 if (ref1->parent > ref2->parent)
48 return 1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -040049 return 0;
50}
51
52/*
53 * compare two delayed data backrefs with same bytenr and type
54 */
55static int comp_data_refs(struct btrfs_delayed_data_ref *ref2,
56 struct btrfs_delayed_data_ref *ref1)
57{
58 if (ref1->node.type == BTRFS_EXTENT_DATA_REF_KEY) {
59 if (ref1->root < ref2->root)
60 return -1;
61 if (ref1->root > ref2->root)
62 return 1;
63 if (ref1->objectid < ref2->objectid)
64 return -1;
65 if (ref1->objectid > ref2->objectid)
66 return 1;
67 if (ref1->offset < ref2->offset)
68 return -1;
69 if (ref1->offset > ref2->offset)
70 return 1;
71 } else {
72 if (ref1->parent < ref2->parent)
73 return -1;
74 if (ref1->parent > ref2->parent)
75 return 1;
76 }
77 return 0;
78}
79
80/*
81 * entries in the rb tree are ordered by the byte number of the extent,
82 * type of the delayed backrefs and content of delayed backrefs.
83 */
84static int comp_entry(struct btrfs_delayed_ref_node *ref2,
Josef Bacikae1e2062012-08-07 16:00:32 -040085 struct btrfs_delayed_ref_node *ref1,
86 bool compare_seq)
Yan Zheng5d4f98a2009-06-10 10:45:14 -040087{
88 if (ref1->bytenr < ref2->bytenr)
Chris Mason56bec292009-03-13 10:10:06 -040089 return -1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -040090 if (ref1->bytenr > ref2->bytenr)
Chris Mason56bec292009-03-13 10:10:06 -040091 return 1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -040092 if (ref1->is_head && ref2->is_head)
93 return 0;
94 if (ref2->is_head)
Chris Mason56bec292009-03-13 10:10:06 -040095 return -1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -040096 if (ref1->is_head)
Chris Mason56bec292009-03-13 10:10:06 -040097 return 1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -040098 if (ref1->type < ref2->type)
99 return -1;
100 if (ref1->type > ref2->type)
101 return 1;
Arne Jansen00f04b82011-09-14 12:37:00 +0200102 /* merging of sequenced refs is not allowed */
Josef Bacikae1e2062012-08-07 16:00:32 -0400103 if (compare_seq) {
104 if (ref1->seq < ref2->seq)
105 return -1;
106 if (ref1->seq > ref2->seq)
107 return 1;
108 }
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400109 if (ref1->type == BTRFS_TREE_BLOCK_REF_KEY ||
110 ref1->type == BTRFS_SHARED_BLOCK_REF_KEY) {
111 return comp_tree_refs(btrfs_delayed_node_to_tree_ref(ref2),
112 btrfs_delayed_node_to_tree_ref(ref1));
113 } else if (ref1->type == BTRFS_EXTENT_DATA_REF_KEY ||
114 ref1->type == BTRFS_SHARED_DATA_REF_KEY) {
115 return comp_data_refs(btrfs_delayed_node_to_data_ref(ref2),
116 btrfs_delayed_node_to_data_ref(ref1));
117 }
118 BUG();
Chris Mason56bec292009-03-13 10:10:06 -0400119 return 0;
120}
121
122/*
123 * insert a new ref into the rbtree. This returns any existing refs
124 * for the same (bytenr,parent) tuple, or NULL if the new node was properly
125 * inserted.
126 */
127static struct btrfs_delayed_ref_node *tree_insert(struct rb_root *root,
Chris Mason56bec292009-03-13 10:10:06 -0400128 struct rb_node *node)
129{
130 struct rb_node **p = &root->rb_node;
131 struct rb_node *parent_node = NULL;
132 struct btrfs_delayed_ref_node *entry;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400133 struct btrfs_delayed_ref_node *ins;
Chris Mason56bec292009-03-13 10:10:06 -0400134 int cmp;
135
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400136 ins = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
Chris Mason56bec292009-03-13 10:10:06 -0400137 while (*p) {
138 parent_node = *p;
139 entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
140 rb_node);
141
Josef Bacikae1e2062012-08-07 16:00:32 -0400142 cmp = comp_entry(entry, ins, 1);
Chris Mason56bec292009-03-13 10:10:06 -0400143 if (cmp < 0)
144 p = &(*p)->rb_left;
145 else if (cmp > 0)
146 p = &(*p)->rb_right;
147 else
148 return entry;
149 }
150
Chris Mason56bec292009-03-13 10:10:06 -0400151 rb_link_node(node, parent_node, p);
152 rb_insert_color(node, root);
153 return NULL;
154}
155
156/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400157 * find an head entry based on bytenr. This returns the delayed ref
Arne Jansend1270cd2011-09-13 15:16:43 +0200158 * head if it was able to find one, or NULL if nothing was in that spot.
159 * If return_bigger is given, the next bigger entry is returned if no exact
160 * match is found.
Chris Mason56bec292009-03-13 10:10:06 -0400161 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400162static struct btrfs_delayed_ref_node *find_ref_head(struct rb_root *root,
163 u64 bytenr,
Arne Jansend1270cd2011-09-13 15:16:43 +0200164 struct btrfs_delayed_ref_node **last,
165 int return_bigger)
Chris Mason56bec292009-03-13 10:10:06 -0400166{
Arne Jansend1270cd2011-09-13 15:16:43 +0200167 struct rb_node *n;
Chris Mason56bec292009-03-13 10:10:06 -0400168 struct btrfs_delayed_ref_node *entry;
Arne Jansend1270cd2011-09-13 15:16:43 +0200169 int cmp = 0;
Chris Mason56bec292009-03-13 10:10:06 -0400170
Arne Jansend1270cd2011-09-13 15:16:43 +0200171again:
172 n = root->rb_node;
173 entry = NULL;
Chris Mason56bec292009-03-13 10:10:06 -0400174 while (n) {
175 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
176 WARN_ON(!entry->in_tree);
Chris Masonc3e69d52009-03-13 10:17:05 -0400177 if (last)
178 *last = entry;
Chris Mason56bec292009-03-13 10:10:06 -0400179
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400180 if (bytenr < entry->bytenr)
181 cmp = -1;
182 else if (bytenr > entry->bytenr)
183 cmp = 1;
184 else if (!btrfs_delayed_ref_is_head(entry))
185 cmp = 1;
186 else
187 cmp = 0;
188
Chris Mason56bec292009-03-13 10:10:06 -0400189 if (cmp < 0)
190 n = n->rb_left;
191 else if (cmp > 0)
192 n = n->rb_right;
193 else
194 return entry;
195 }
Arne Jansend1270cd2011-09-13 15:16:43 +0200196 if (entry && return_bigger) {
197 if (cmp > 0) {
198 n = rb_next(&entry->rb_node);
199 if (!n)
200 n = rb_first(root);
201 entry = rb_entry(n, struct btrfs_delayed_ref_node,
202 rb_node);
203 bytenr = entry->bytenr;
204 return_bigger = 0;
205 goto again;
206 }
207 return entry;
208 }
Chris Mason56bec292009-03-13 10:10:06 -0400209 return NULL;
210}
211
Chris Masonc3e69d52009-03-13 10:17:05 -0400212int btrfs_delayed_ref_lock(struct btrfs_trans_handle *trans,
213 struct btrfs_delayed_ref_head *head)
Chris Mason56bec292009-03-13 10:10:06 -0400214{
Chris Masonc3e69d52009-03-13 10:17:05 -0400215 struct btrfs_delayed_ref_root *delayed_refs;
Chris Mason56bec292009-03-13 10:10:06 -0400216
Chris Masonc3e69d52009-03-13 10:17:05 -0400217 delayed_refs = &trans->transaction->delayed_refs;
218 assert_spin_locked(&delayed_refs->lock);
219 if (mutex_trylock(&head->mutex))
220 return 0;
221
222 atomic_inc(&head->node.refs);
223 spin_unlock(&delayed_refs->lock);
224
225 mutex_lock(&head->mutex);
226 spin_lock(&delayed_refs->lock);
227 if (!head->node.in_tree) {
228 mutex_unlock(&head->mutex);
229 btrfs_put_delayed_ref(&head->node);
230 return -EAGAIN;
231 }
232 btrfs_put_delayed_ref(&head->node);
233 return 0;
234}
235
Josef Bacikae1e2062012-08-07 16:00:32 -0400236static void inline drop_delayed_ref(struct btrfs_trans_handle *trans,
237 struct btrfs_delayed_ref_root *delayed_refs,
238 struct btrfs_delayed_ref_node *ref)
239{
240 rb_erase(&ref->rb_node, &delayed_refs->root);
241 ref->in_tree = 0;
242 btrfs_put_delayed_ref(ref);
243 delayed_refs->num_entries--;
244 if (trans->delayed_ref_updates)
245 trans->delayed_ref_updates--;
246}
247
248static int merge_ref(struct btrfs_trans_handle *trans,
249 struct btrfs_delayed_ref_root *delayed_refs,
250 struct btrfs_delayed_ref_node *ref, u64 seq)
251{
252 struct rb_node *node;
253 int merged = 0;
254 int mod = 0;
255 int done = 0;
256
257 node = rb_prev(&ref->rb_node);
258 while (node) {
259 struct btrfs_delayed_ref_node *next;
260
261 next = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
262 node = rb_prev(node);
263 if (next->bytenr != ref->bytenr)
264 break;
265 if (seq && next->seq >= seq)
266 break;
267 if (comp_entry(ref, next, 0))
268 continue;
269
270 if (ref->action == next->action) {
271 mod = next->ref_mod;
272 } else {
273 if (ref->ref_mod < next->ref_mod) {
274 struct btrfs_delayed_ref_node *tmp;
275
276 tmp = ref;
277 ref = next;
278 next = tmp;
279 done = 1;
280 }
281 mod = -next->ref_mod;
282 }
283
284 merged++;
285 drop_delayed_ref(trans, delayed_refs, next);
286 ref->ref_mod += mod;
287 if (ref->ref_mod == 0) {
288 drop_delayed_ref(trans, delayed_refs, ref);
289 break;
290 } else {
291 /*
292 * You can't have multiples of the same ref on a tree
293 * block.
294 */
295 WARN_ON(ref->type == BTRFS_TREE_BLOCK_REF_KEY ||
296 ref->type == BTRFS_SHARED_BLOCK_REF_KEY);
297 }
298
299 if (done)
300 break;
301 node = rb_prev(&ref->rb_node);
302 }
303
304 return merged;
305}
306
307void btrfs_merge_delayed_refs(struct btrfs_trans_handle *trans,
308 struct btrfs_fs_info *fs_info,
309 struct btrfs_delayed_ref_root *delayed_refs,
310 struct btrfs_delayed_ref_head *head)
311{
312 struct rb_node *node;
313 u64 seq = 0;
314
315 spin_lock(&fs_info->tree_mod_seq_lock);
316 if (!list_empty(&fs_info->tree_mod_seq_list)) {
317 struct seq_list *elem;
318
319 elem = list_first_entry(&fs_info->tree_mod_seq_list,
320 struct seq_list, list);
321 seq = elem->seq;
322 }
323 spin_unlock(&fs_info->tree_mod_seq_lock);
324
325 node = rb_prev(&head->node.rb_node);
326 while (node) {
327 struct btrfs_delayed_ref_node *ref;
328
329 ref = rb_entry(node, struct btrfs_delayed_ref_node,
330 rb_node);
331 if (ref->bytenr != head->node.bytenr)
332 break;
333
334 /* We can't merge refs that are outside of our seq count */
335 if (seq && ref->seq >= seq)
336 break;
337 if (merge_ref(trans, delayed_refs, ref, seq))
338 node = rb_prev(&head->node.rb_node);
339 else
340 node = rb_prev(node);
341 }
342}
343
Jan Schmidt097b8a72012-06-21 11:08:04 +0200344int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info,
345 struct btrfs_delayed_ref_root *delayed_refs,
Arne Jansen00f04b82011-09-14 12:37:00 +0200346 u64 seq)
347{
348 struct seq_list *elem;
Jan Schmidt097b8a72012-06-21 11:08:04 +0200349 int ret = 0;
Arne Jansen00f04b82011-09-14 12:37:00 +0200350
Jan Schmidt097b8a72012-06-21 11:08:04 +0200351 spin_lock(&fs_info->tree_mod_seq_lock);
352 if (!list_empty(&fs_info->tree_mod_seq_list)) {
353 elem = list_first_entry(&fs_info->tree_mod_seq_list,
354 struct seq_list, list);
355 if (seq >= elem->seq) {
356 pr_debug("holding back delayed_ref %llu, lowest is "
357 "%llu (%p)\n", seq, elem->seq, delayed_refs);
358 ret = 1;
359 }
Arne Jansen00f04b82011-09-14 12:37:00 +0200360 }
Jan Schmidt097b8a72012-06-21 11:08:04 +0200361
362 spin_unlock(&fs_info->tree_mod_seq_lock);
363 return ret;
Arne Jansen00f04b82011-09-14 12:37:00 +0200364}
365
Chris Masonc3e69d52009-03-13 10:17:05 -0400366int btrfs_find_ref_cluster(struct btrfs_trans_handle *trans,
367 struct list_head *cluster, u64 start)
368{
369 int count = 0;
370 struct btrfs_delayed_ref_root *delayed_refs;
371 struct rb_node *node;
372 struct btrfs_delayed_ref_node *ref;
373 struct btrfs_delayed_ref_head *head;
374
375 delayed_refs = &trans->transaction->delayed_refs;
376 if (start == 0) {
377 node = rb_first(&delayed_refs->root);
378 } else {
379 ref = NULL;
Arne Jansend1270cd2011-09-13 15:16:43 +0200380 find_ref_head(&delayed_refs->root, start + 1, &ref, 1);
Chris Masonc3e69d52009-03-13 10:17:05 -0400381 if (ref) {
Chris Masonc3e69d52009-03-13 10:17:05 -0400382 node = &ref->rb_node;
383 } else
384 node = rb_first(&delayed_refs->root);
385 }
386again:
387 while (node && count < 32) {
388 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
Chris Mason56bec292009-03-13 10:10:06 -0400389 if (btrfs_delayed_ref_is_head(ref)) {
390 head = btrfs_delayed_node_to_head(ref);
Chris Masonc3e69d52009-03-13 10:17:05 -0400391 if (list_empty(&head->cluster)) {
392 list_add_tail(&head->cluster, cluster);
393 delayed_refs->run_delayed_start =
394 head->node.bytenr;
395 count++;
396
397 WARN_ON(delayed_refs->num_heads_ready == 0);
398 delayed_refs->num_heads_ready--;
399 } else if (count) {
400 /* the goal of the clustering is to find extents
401 * that are likely to end up in the same extent
402 * leaf on disk. So, we don't want them spread
403 * all over the tree. Stop now if we've hit
404 * a head that was already in use
405 */
Chris Mason56bec292009-03-13 10:10:06 -0400406 break;
407 }
408 }
Chris Masonc3e69d52009-03-13 10:17:05 -0400409 node = rb_next(node);
Chris Mason56bec292009-03-13 10:10:06 -0400410 }
Chris Masonc3e69d52009-03-13 10:17:05 -0400411 if (count) {
412 return 0;
413 } else if (start) {
414 /*
415 * we've gone to the end of the rbtree without finding any
416 * clusters. start from the beginning and try again
417 */
418 start = 0;
419 node = rb_first(&delayed_refs->root);
420 goto again;
421 }
422 return 1;
Chris Mason56bec292009-03-13 10:10:06 -0400423}
424
425/*
Chris Mason56bec292009-03-13 10:10:06 -0400426 * helper function to update an extent delayed ref in the
427 * rbtree. existing and update must both have the same
428 * bytenr and parent
429 *
430 * This may free existing if the update cancels out whatever
431 * operation it was doing.
432 */
433static noinline void
434update_existing_ref(struct btrfs_trans_handle *trans,
435 struct btrfs_delayed_ref_root *delayed_refs,
436 struct btrfs_delayed_ref_node *existing,
437 struct btrfs_delayed_ref_node *update)
438{
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400439 if (update->action != existing->action) {
Chris Mason56bec292009-03-13 10:10:06 -0400440 /*
441 * this is effectively undoing either an add or a
442 * drop. We decrement the ref_mod, and if it goes
443 * down to zero we just delete the entry without
444 * every changing the extent allocation tree.
445 */
446 existing->ref_mod--;
Josef Bacikae1e2062012-08-07 16:00:32 -0400447 if (existing->ref_mod == 0)
448 drop_delayed_ref(trans, delayed_refs, existing);
449 else
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400450 WARN_ON(existing->type == BTRFS_TREE_BLOCK_REF_KEY ||
451 existing->type == BTRFS_SHARED_BLOCK_REF_KEY);
Chris Mason56bec292009-03-13 10:10:06 -0400452 } else {
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400453 WARN_ON(existing->type == BTRFS_TREE_BLOCK_REF_KEY ||
454 existing->type == BTRFS_SHARED_BLOCK_REF_KEY);
Chris Mason56bec292009-03-13 10:10:06 -0400455 /*
456 * the action on the existing ref matches
457 * the action on the ref we're trying to add.
458 * Bump the ref_mod by one so the backref that
459 * is eventually added/removed has the correct
460 * reference count
461 */
462 existing->ref_mod += update->ref_mod;
463 }
464}
465
466/*
467 * helper function to update the accounting in the head ref
468 * existing and update must have the same bytenr
469 */
470static noinline void
471update_existing_head_ref(struct btrfs_delayed_ref_node *existing,
472 struct btrfs_delayed_ref_node *update)
473{
474 struct btrfs_delayed_ref_head *existing_ref;
475 struct btrfs_delayed_ref_head *ref;
476
477 existing_ref = btrfs_delayed_node_to_head(existing);
478 ref = btrfs_delayed_node_to_head(update);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400479 BUG_ON(existing_ref->is_data != ref->is_data);
Chris Mason56bec292009-03-13 10:10:06 -0400480
481 if (ref->must_insert_reserved) {
482 /* if the extent was freed and then
483 * reallocated before the delayed ref
484 * entries were processed, we can end up
485 * with an existing head ref without
486 * the must_insert_reserved flag set.
487 * Set it again here
488 */
489 existing_ref->must_insert_reserved = ref->must_insert_reserved;
490
491 /*
492 * update the num_bytes so we make sure the accounting
493 * is done correctly
494 */
495 existing->num_bytes = update->num_bytes;
496
497 }
498
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400499 if (ref->extent_op) {
500 if (!existing_ref->extent_op) {
501 existing_ref->extent_op = ref->extent_op;
502 } else {
503 if (ref->extent_op->update_key) {
504 memcpy(&existing_ref->extent_op->key,
505 &ref->extent_op->key,
506 sizeof(ref->extent_op->key));
507 existing_ref->extent_op->update_key = 1;
508 }
509 if (ref->extent_op->update_flags) {
510 existing_ref->extent_op->flags_to_set |=
511 ref->extent_op->flags_to_set;
512 existing_ref->extent_op->update_flags = 1;
513 }
514 kfree(ref->extent_op);
515 }
516 }
Chris Mason56bec292009-03-13 10:10:06 -0400517 /*
518 * update the reference mod on the head to reflect this new operation
519 */
520 existing->ref_mod += update->ref_mod;
521}
522
523/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400524 * helper function to actually insert a head node into the rbtree.
Chris Mason56bec292009-03-13 10:10:06 -0400525 * this does all the dirty work in terms of maintaining the correct
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400526 * overall modification count.
Chris Mason56bec292009-03-13 10:10:06 -0400527 */
Jeff Mahoney143bede2012-03-01 14:56:26 +0100528static noinline void add_delayed_ref_head(struct btrfs_fs_info *fs_info,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200529 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400530 struct btrfs_delayed_ref_node *ref,
531 u64 bytenr, u64 num_bytes,
532 int action, int is_data)
Chris Mason56bec292009-03-13 10:10:06 -0400533{
534 struct btrfs_delayed_ref_node *existing;
Chris Masonc3e69d52009-03-13 10:17:05 -0400535 struct btrfs_delayed_ref_head *head_ref = NULL;
Chris Mason56bec292009-03-13 10:10:06 -0400536 struct btrfs_delayed_ref_root *delayed_refs;
537 int count_mod = 1;
538 int must_insert_reserved = 0;
539
540 /*
541 * the head node stores the sum of all the mods, so dropping a ref
542 * should drop the sum in the head node by one.
543 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400544 if (action == BTRFS_UPDATE_DELAYED_HEAD)
545 count_mod = 0;
546 else if (action == BTRFS_DROP_DELAYED_REF)
547 count_mod = -1;
Chris Mason56bec292009-03-13 10:10:06 -0400548
549 /*
550 * BTRFS_ADD_DELAYED_EXTENT means that we need to update
551 * the reserved accounting when the extent is finally added, or
552 * if a later modification deletes the delayed ref without ever
553 * inserting the extent into the extent allocation tree.
554 * ref->must_insert_reserved is the flag used to record
555 * that accounting mods are required.
556 *
557 * Once we record must_insert_reserved, switch the action to
558 * BTRFS_ADD_DELAYED_REF because other special casing is not required.
559 */
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400560 if (action == BTRFS_ADD_DELAYED_EXTENT)
Chris Mason56bec292009-03-13 10:10:06 -0400561 must_insert_reserved = 1;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400562 else
Chris Mason56bec292009-03-13 10:10:06 -0400563 must_insert_reserved = 0;
Chris Mason56bec292009-03-13 10:10:06 -0400564
565 delayed_refs = &trans->transaction->delayed_refs;
566
567 /* first set the basic ref node struct up */
568 atomic_set(&ref->refs, 1);
569 ref->bytenr = bytenr;
Chris Mason56bec292009-03-13 10:10:06 -0400570 ref->num_bytes = num_bytes;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400571 ref->ref_mod = count_mod;
572 ref->type = 0;
573 ref->action = 0;
574 ref->is_head = 1;
575 ref->in_tree = 1;
Arne Jansen00f04b82011-09-14 12:37:00 +0200576 ref->seq = 0;
Chris Mason56bec292009-03-13 10:10:06 -0400577
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400578 head_ref = btrfs_delayed_node_to_head(ref);
579 head_ref->must_insert_reserved = must_insert_reserved;
580 head_ref->is_data = is_data;
Chris Mason56bec292009-03-13 10:10:06 -0400581
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400582 INIT_LIST_HEAD(&head_ref->cluster);
583 mutex_init(&head_ref->mutex);
584
liubo1abe9b82011-03-24 11:18:59 +0000585 trace_btrfs_delayed_ref_head(ref, head_ref, action);
586
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400587 existing = tree_insert(&delayed_refs->root, &ref->rb_node);
Chris Mason56bec292009-03-13 10:10:06 -0400588
589 if (existing) {
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400590 update_existing_head_ref(existing, ref);
Chris Mason56bec292009-03-13 10:10:06 -0400591 /*
592 * we've updated the existing ref, free the newly
593 * allocated ref
594 */
Jeff Mahoneycddcd802011-10-03 23:23:23 -0400595 kfree(head_ref);
Chris Mason56bec292009-03-13 10:10:06 -0400596 } else {
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400597 delayed_refs->num_heads++;
598 delayed_refs->num_heads_ready++;
Chris Mason56bec292009-03-13 10:10:06 -0400599 delayed_refs->num_entries++;
600 trans->delayed_ref_updates++;
601 }
Chris Mason56bec292009-03-13 10:10:06 -0400602}
603
604/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400605 * helper to insert a delayed tree ref into the rbtree.
606 */
Jeff Mahoney143bede2012-03-01 14:56:26 +0100607static noinline void add_delayed_tree_ref(struct btrfs_fs_info *fs_info,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200608 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400609 struct btrfs_delayed_ref_node *ref,
610 u64 bytenr, u64 num_bytes, u64 parent,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200611 u64 ref_root, int level, int action,
612 int for_cow)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400613{
614 struct btrfs_delayed_ref_node *existing;
615 struct btrfs_delayed_tree_ref *full_ref;
616 struct btrfs_delayed_ref_root *delayed_refs;
Arne Jansen00f04b82011-09-14 12:37:00 +0200617 u64 seq = 0;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400618
619 if (action == BTRFS_ADD_DELAYED_EXTENT)
620 action = BTRFS_ADD_DELAYED_REF;
621
622 delayed_refs = &trans->transaction->delayed_refs;
623
624 /* first set the basic ref node struct up */
625 atomic_set(&ref->refs, 1);
626 ref->bytenr = bytenr;
627 ref->num_bytes = num_bytes;
628 ref->ref_mod = 1;
629 ref->action = action;
630 ref->is_head = 0;
631 ref->in_tree = 1;
632
Jan Schmidt546adb02012-06-14 16:37:44 +0200633 if (need_ref_seq(for_cow, ref_root))
634 seq = btrfs_get_tree_mod_seq(fs_info, &trans->delayed_ref_elem);
Arne Jansen00f04b82011-09-14 12:37:00 +0200635 ref->seq = seq;
636
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400637 full_ref = btrfs_delayed_node_to_tree_ref(ref);
Arne Janseneebe0632011-09-14 14:01:24 +0200638 full_ref->parent = parent;
639 full_ref->root = ref_root;
640 if (parent)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400641 ref->type = BTRFS_SHARED_BLOCK_REF_KEY;
Arne Janseneebe0632011-09-14 14:01:24 +0200642 else
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400643 ref->type = BTRFS_TREE_BLOCK_REF_KEY;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400644 full_ref->level = level;
645
liubo1abe9b82011-03-24 11:18:59 +0000646 trace_btrfs_delayed_tree_ref(ref, full_ref, action);
647
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400648 existing = tree_insert(&delayed_refs->root, &ref->rb_node);
649
650 if (existing) {
651 update_existing_ref(trans, delayed_refs, existing, ref);
652 /*
653 * we've updated the existing ref, free the newly
654 * allocated ref
655 */
Jeff Mahoneycddcd802011-10-03 23:23:23 -0400656 kfree(full_ref);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400657 } else {
658 delayed_refs->num_entries++;
659 trans->delayed_ref_updates++;
660 }
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400661}
662
663/*
664 * helper to insert a delayed data ref into the rbtree.
665 */
Jeff Mahoney143bede2012-03-01 14:56:26 +0100666static noinline void add_delayed_data_ref(struct btrfs_fs_info *fs_info,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200667 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400668 struct btrfs_delayed_ref_node *ref,
669 u64 bytenr, u64 num_bytes, u64 parent,
670 u64 ref_root, u64 owner, u64 offset,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200671 int action, int for_cow)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400672{
673 struct btrfs_delayed_ref_node *existing;
674 struct btrfs_delayed_data_ref *full_ref;
675 struct btrfs_delayed_ref_root *delayed_refs;
Arne Jansen00f04b82011-09-14 12:37:00 +0200676 u64 seq = 0;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400677
678 if (action == BTRFS_ADD_DELAYED_EXTENT)
679 action = BTRFS_ADD_DELAYED_REF;
680
681 delayed_refs = &trans->transaction->delayed_refs;
682
683 /* first set the basic ref node struct up */
684 atomic_set(&ref->refs, 1);
685 ref->bytenr = bytenr;
686 ref->num_bytes = num_bytes;
687 ref->ref_mod = 1;
688 ref->action = action;
689 ref->is_head = 0;
690 ref->in_tree = 1;
691
Jan Schmidt546adb02012-06-14 16:37:44 +0200692 if (need_ref_seq(for_cow, ref_root))
693 seq = btrfs_get_tree_mod_seq(fs_info, &trans->delayed_ref_elem);
Arne Jansen00f04b82011-09-14 12:37:00 +0200694 ref->seq = seq;
695
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400696 full_ref = btrfs_delayed_node_to_data_ref(ref);
Arne Janseneebe0632011-09-14 14:01:24 +0200697 full_ref->parent = parent;
698 full_ref->root = ref_root;
699 if (parent)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400700 ref->type = BTRFS_SHARED_DATA_REF_KEY;
Arne Janseneebe0632011-09-14 14:01:24 +0200701 else
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400702 ref->type = BTRFS_EXTENT_DATA_REF_KEY;
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200703
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400704 full_ref->objectid = owner;
705 full_ref->offset = offset;
706
liubo1abe9b82011-03-24 11:18:59 +0000707 trace_btrfs_delayed_data_ref(ref, full_ref, action);
708
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400709 existing = tree_insert(&delayed_refs->root, &ref->rb_node);
710
711 if (existing) {
712 update_existing_ref(trans, delayed_refs, existing, ref);
713 /*
714 * we've updated the existing ref, free the newly
715 * allocated ref
716 */
Jeff Mahoneycddcd802011-10-03 23:23:23 -0400717 kfree(full_ref);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400718 } else {
719 delayed_refs->num_entries++;
720 trans->delayed_ref_updates++;
721 }
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400722}
723
724/*
725 * add a delayed tree ref. This does all of the accounting required
Chris Mason56bec292009-03-13 10:10:06 -0400726 * to make sure the delayed ref is eventually processed before this
727 * transaction commits.
728 */
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200729int btrfs_add_delayed_tree_ref(struct btrfs_fs_info *fs_info,
730 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400731 u64 bytenr, u64 num_bytes, u64 parent,
732 u64 ref_root, int level, int action,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200733 struct btrfs_delayed_extent_op *extent_op,
734 int for_cow)
Chris Mason56bec292009-03-13 10:10:06 -0400735{
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400736 struct btrfs_delayed_tree_ref *ref;
Chris Mason56bec292009-03-13 10:10:06 -0400737 struct btrfs_delayed_ref_head *head_ref;
738 struct btrfs_delayed_ref_root *delayed_refs;
Chris Mason56bec292009-03-13 10:10:06 -0400739
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400740 BUG_ON(extent_op && extent_op->is_data);
Chris Mason56bec292009-03-13 10:10:06 -0400741 ref = kmalloc(sizeof(*ref), GFP_NOFS);
742 if (!ref)
743 return -ENOMEM;
744
Chris Mason56bec292009-03-13 10:10:06 -0400745 head_ref = kmalloc(sizeof(*head_ref), GFP_NOFS);
746 if (!head_ref) {
747 kfree(ref);
748 return -ENOMEM;
749 }
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400750
751 head_ref->extent_op = extent_op;
752
Chris Mason56bec292009-03-13 10:10:06 -0400753 delayed_refs = &trans->transaction->delayed_refs;
754 spin_lock(&delayed_refs->lock);
755
756 /*
757 * insert both the head node and the new ref without dropping
758 * the spin lock
759 */
Jeff Mahoney143bede2012-03-01 14:56:26 +0100760 add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200761 num_bytes, action, 0);
Chris Mason56bec292009-03-13 10:10:06 -0400762
Jeff Mahoney143bede2012-03-01 14:56:26 +0100763 add_delayed_tree_ref(fs_info, trans, &ref->node, bytenr,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200764 num_bytes, parent, ref_root, level, action,
765 for_cow);
Chris Mason56bec292009-03-13 10:10:06 -0400766 spin_unlock(&delayed_refs->lock);
Jan Schmidt546adb02012-06-14 16:37:44 +0200767 if (need_ref_seq(for_cow, ref_root))
768 btrfs_qgroup_record_ref(trans, &ref->node, extent_op);
Jan Schmidt95a06072012-05-29 17:06:54 +0200769
Chris Mason56bec292009-03-13 10:10:06 -0400770 return 0;
771}
772
773/*
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400774 * add a delayed data ref. it's similar to btrfs_add_delayed_tree_ref.
775 */
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200776int btrfs_add_delayed_data_ref(struct btrfs_fs_info *fs_info,
777 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400778 u64 bytenr, u64 num_bytes,
779 u64 parent, u64 ref_root,
780 u64 owner, u64 offset, int action,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200781 struct btrfs_delayed_extent_op *extent_op,
782 int for_cow)
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400783{
784 struct btrfs_delayed_data_ref *ref;
785 struct btrfs_delayed_ref_head *head_ref;
786 struct btrfs_delayed_ref_root *delayed_refs;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400787
788 BUG_ON(extent_op && !extent_op->is_data);
789 ref = kmalloc(sizeof(*ref), GFP_NOFS);
790 if (!ref)
791 return -ENOMEM;
792
793 head_ref = kmalloc(sizeof(*head_ref), GFP_NOFS);
794 if (!head_ref) {
795 kfree(ref);
796 return -ENOMEM;
797 }
798
799 head_ref->extent_op = extent_op;
800
801 delayed_refs = &trans->transaction->delayed_refs;
802 spin_lock(&delayed_refs->lock);
803
804 /*
805 * insert both the head node and the new ref without dropping
806 * the spin lock
807 */
Jeff Mahoney143bede2012-03-01 14:56:26 +0100808 add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200809 num_bytes, action, 1);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400810
Jeff Mahoney143bede2012-03-01 14:56:26 +0100811 add_delayed_data_ref(fs_info, trans, &ref->node, bytenr,
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200812 num_bytes, parent, ref_root, owner, offset,
813 action, for_cow);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400814 spin_unlock(&delayed_refs->lock);
Jan Schmidt546adb02012-06-14 16:37:44 +0200815 if (need_ref_seq(for_cow, ref_root))
816 btrfs_qgroup_record_ref(trans, &ref->node, extent_op);
Jan Schmidt95a06072012-05-29 17:06:54 +0200817
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400818 return 0;
819}
820
Arne Jansen66d7e7f2011-09-12 15:26:38 +0200821int btrfs_add_delayed_extent_op(struct btrfs_fs_info *fs_info,
822 struct btrfs_trans_handle *trans,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400823 u64 bytenr, u64 num_bytes,
824 struct btrfs_delayed_extent_op *extent_op)
825{
826 struct btrfs_delayed_ref_head *head_ref;
827 struct btrfs_delayed_ref_root *delayed_refs;
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400828
829 head_ref = kmalloc(sizeof(*head_ref), GFP_NOFS);
830 if (!head_ref)
831 return -ENOMEM;
832
833 head_ref->extent_op = extent_op;
834
835 delayed_refs = &trans->transaction->delayed_refs;
836 spin_lock(&delayed_refs->lock);
837
Jeff Mahoney143bede2012-03-01 14:56:26 +0100838 add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400839 num_bytes, BTRFS_UPDATE_DELAYED_HEAD,
840 extent_op->is_data);
Yan Zheng5d4f98a2009-06-10 10:45:14 -0400841
842 spin_unlock(&delayed_refs->lock);
843 return 0;
844}
845
846/*
Chris Mason1887be62009-03-13 10:11:24 -0400847 * this does a simple search for the head node for a given extent.
848 * It must be called with the delayed ref spinlock held, and it returns
849 * the head node if any where found, or NULL if not.
850 */
851struct btrfs_delayed_ref_head *
852btrfs_find_delayed_ref_head(struct btrfs_trans_handle *trans, u64 bytenr)
853{
854 struct btrfs_delayed_ref_node *ref;
855 struct btrfs_delayed_ref_root *delayed_refs;
856
857 delayed_refs = &trans->transaction->delayed_refs;
Arne Jansend1270cd2011-09-13 15:16:43 +0200858 ref = find_ref_head(&delayed_refs->root, bytenr, NULL, 0);
Chris Mason1887be62009-03-13 10:11:24 -0400859 if (ref)
860 return btrfs_delayed_node_to_head(ref);
861 return NULL;
862}