Branch data Line data Source code
1 : : /*
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>
20 : : #include <linux/slab.h>
21 : : #include <linux/sort.h>
22 : : #include "ctree.h"
23 : : #include "delayed-ref.h"
24 : : #include "transaction.h"
25 : :
26 : : struct kmem_cache *btrfs_delayed_ref_head_cachep;
27 : : struct kmem_cache *btrfs_delayed_tree_ref_cachep;
28 : : struct kmem_cache *btrfs_delayed_data_ref_cachep;
29 : : struct kmem_cache *btrfs_delayed_extent_op_cachep;
30 : : /*
31 : : * delayed back reference update tracking. For subvolume trees
32 : : * we queue up extent allocations and backref maintenance for
33 : : * delayed processing. This avoids deep call chains where we
34 : : * add extents in the middle of btrfs_search_slot, and it allows
35 : : * us to buffer up frequently modified backrefs in an rb tree instead
36 : : * of hammering updates on the extent allocation tree.
37 : : */
38 : :
39 : : /*
40 : : * compare two delayed tree backrefs with same bytenr and type
41 : : */
42 : : static int comp_tree_refs(struct btrfs_delayed_tree_ref *ref2,
43 : : struct btrfs_delayed_tree_ref *ref1, int type)
44 : : {
45 [ # # ]: 0 : if (type == BTRFS_TREE_BLOCK_REF_KEY) {
46 [ # # ]: 0 : if (ref1->root < ref2->root)
47 : : return -1;
48 [ # # ]: 0 : if (ref1->root > ref2->root)
49 : : return 1;
50 : : } else {
51 [ # # ]: 0 : if (ref1->parent < ref2->parent)
52 : : return -1;
53 [ # # ]: 0 : if (ref1->parent > ref2->parent)
54 : : return 1;
55 : : }
56 : : return 0;
57 : : }
58 : :
59 : : /*
60 : : * compare two delayed data backrefs with same bytenr and type
61 : : */
62 : 0 : static int comp_data_refs(struct btrfs_delayed_data_ref *ref2,
63 : : struct btrfs_delayed_data_ref *ref1)
64 : : {
65 [ # # ]: 0 : if (ref1->node.type == BTRFS_EXTENT_DATA_REF_KEY) {
66 [ # # ]: 0 : if (ref1->root < ref2->root)
67 : : return -1;
68 [ # # ]: 0 : if (ref1->root > ref2->root)
69 : : return 1;
70 [ # # ]: 0 : if (ref1->objectid < ref2->objectid)
71 : : return -1;
72 [ # # ]: 0 : if (ref1->objectid > ref2->objectid)
73 : : return 1;
74 [ # # ]: 0 : if (ref1->offset < ref2->offset)
75 : : return -1;
76 [ # # ]: 0 : if (ref1->offset > ref2->offset)
77 : : return 1;
78 : : } else {
79 [ # # ]: 0 : if (ref1->parent < ref2->parent)
80 : : return -1;
81 [ # # ]: 0 : if (ref1->parent > ref2->parent)
82 : : return 1;
83 : : }
84 : 0 : return 0;
85 : : }
86 : :
87 : : /*
88 : : * entries in the rb tree are ordered by the byte number of the extent,
89 : : * type of the delayed backrefs and content of delayed backrefs.
90 : : */
91 : 0 : static int comp_entry(struct btrfs_delayed_ref_node *ref2,
92 : : struct btrfs_delayed_ref_node *ref1,
93 : : bool compare_seq)
94 : : {
95 [ # # ]: 0 : if (ref1->bytenr < ref2->bytenr)
96 : : return -1;
97 [ # # ]: 0 : if (ref1->bytenr > ref2->bytenr)
98 : : return 1;
99 [ # # ][ # # ]: 0 : if (ref1->is_head && ref2->is_head)
100 : : return 0;
101 [ # # ]: 0 : if (ref2->is_head)
102 : : return -1;
103 [ # # ]: 0 : if (ref1->is_head)
104 : : return 1;
105 [ # # ]: 0 : if (ref1->type < ref2->type)
106 : : return -1;
107 [ # # ]: 0 : if (ref1->type > ref2->type)
108 : : return 1;
109 : : /* merging of sequenced refs is not allowed */
110 [ # # ]: 0 : if (compare_seq) {
111 [ # # ]: 0 : if (ref1->seq < ref2->seq)
112 : : return -1;
113 [ # # ]: 0 : if (ref1->seq > ref2->seq)
114 : : return 1;
115 : : }
116 [ # # ]: 0 : if (ref1->type == BTRFS_TREE_BLOCK_REF_KEY ||
117 : : ref1->type == BTRFS_SHARED_BLOCK_REF_KEY) {
118 : 0 : return comp_tree_refs(btrfs_delayed_node_to_tree_ref(ref2),
119 : : btrfs_delayed_node_to_tree_ref(ref1),
120 : 0 : ref1->type);
121 [ # # ]: 0 : } else if (ref1->type == BTRFS_EXTENT_DATA_REF_KEY ||
122 : : ref1->type == BTRFS_SHARED_DATA_REF_KEY) {
123 : 0 : return comp_data_refs(btrfs_delayed_node_to_data_ref(ref2),
124 : : btrfs_delayed_node_to_data_ref(ref1));
125 : : }
126 : 0 : BUG();
127 : : return 0;
128 : : }
129 : :
130 : : /*
131 : : * insert a new ref into the rbtree. This returns any existing refs
132 : : * for the same (bytenr,parent) tuple, or NULL if the new node was properly
133 : : * inserted.
134 : : */
135 : 0 : static struct btrfs_delayed_ref_node *tree_insert(struct rb_root *root,
136 : : struct rb_node *node)
137 : : {
138 : 0 : struct rb_node **p = &root->rb_node;
139 : : struct rb_node *parent_node = NULL;
140 : : struct btrfs_delayed_ref_node *entry;
141 : : struct btrfs_delayed_ref_node *ins;
142 : : int cmp;
143 : :
144 : : ins = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
145 [ # # ]: 0 : while (*p) {
146 : : parent_node = *p;
147 : : entry = rb_entry(parent_node, struct btrfs_delayed_ref_node,
148 : : rb_node);
149 : :
150 : 0 : cmp = comp_entry(entry, ins, 1);
151 [ # # ]: 0 : if (cmp < 0)
152 : 0 : p = &(*p)->rb_left;
153 [ # # ]: 0 : else if (cmp > 0)
154 : 0 : p = &(*p)->rb_right;
155 : : else
156 : : return entry;
157 : : }
158 : :
159 : : rb_link_node(node, parent_node, p);
160 : 0 : rb_insert_color(node, root);
161 : 0 : return NULL;
162 : : }
163 : :
164 : : /*
165 : : * find an head entry based on bytenr. This returns the delayed ref
166 : : * head if it was able to find one, or NULL if nothing was in that spot.
167 : : * If return_bigger is given, the next bigger entry is returned if no exact
168 : : * match is found.
169 : : */
170 : 0 : static struct btrfs_delayed_ref_node *find_ref_head(struct rb_root *root,
171 : : u64 bytenr,
172 : : struct btrfs_delayed_ref_node **last,
173 : : int return_bigger)
174 : : {
175 : : struct rb_node *n;
176 : : struct btrfs_delayed_ref_node *entry;
177 : : int cmp = 0;
178 : :
179 : : again:
180 : 0 : n = root->rb_node;
181 : : entry = NULL;
182 [ # # ]: 0 : while (n) {
183 : : entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
184 [ # # ]: 0 : WARN_ON(!entry->in_tree);
185 [ # # ]: 0 : if (last)
186 : 0 : *last = entry;
187 : :
188 [ # # ]: 0 : if (bytenr < entry->bytenr)
189 : : cmp = -1;
190 [ # # ]: 0 : else if (bytenr > entry->bytenr)
191 : : cmp = 1;
192 [ # # ]: 0 : else if (!btrfs_delayed_ref_is_head(entry))
193 : : cmp = 1;
194 : : else
195 : : cmp = 0;
196 : :
197 [ # # ]: 0 : if (cmp < 0)
198 : 0 : n = n->rb_left;
199 [ # # ]: 0 : else if (cmp > 0)
200 : 0 : n = n->rb_right;
201 : : else
202 : : return entry;
203 : : }
204 [ # # ]: 0 : if (entry && return_bigger) {
205 [ # # ]: 0 : if (cmp > 0) {
206 : 0 : n = rb_next(&entry->rb_node);
207 [ # # ]: 0 : if (!n)
208 : 0 : n = rb_first(root);
209 : : entry = rb_entry(n, struct btrfs_delayed_ref_node,
210 : : rb_node);
211 : 0 : bytenr = entry->bytenr;
212 : : return_bigger = 0;
213 : 0 : goto again;
214 : : }
215 : : return entry;
216 : : }
217 : : return NULL;
218 : : }
219 : :
220 : 0 : int btrfs_delayed_ref_lock(struct btrfs_trans_handle *trans,
221 : : struct btrfs_delayed_ref_head *head)
222 : : {
223 : : struct btrfs_delayed_ref_root *delayed_refs;
224 : :
225 : 0 : delayed_refs = &trans->transaction->delayed_refs;
226 [ # # ]: 0 : assert_spin_locked(&delayed_refs->lock);
227 [ # # ]: 0 : if (mutex_trylock(&head->mutex))
228 : : return 0;
229 : :
230 : 0 : atomic_inc(&head->node.refs);
231 : : spin_unlock(&delayed_refs->lock);
232 : :
233 : 0 : mutex_lock(&head->mutex);
234 : : spin_lock(&delayed_refs->lock);
235 [ # # ]: 0 : if (!head->node.in_tree) {
236 : 0 : mutex_unlock(&head->mutex);
237 : 0 : btrfs_put_delayed_ref(&head->node);
238 : : return -EAGAIN;
239 : : }
240 : 0 : btrfs_put_delayed_ref(&head->node);
241 : : return 0;
242 : : }
243 : :
244 : : static inline void drop_delayed_ref(struct btrfs_trans_handle *trans,
245 : : struct btrfs_delayed_ref_root *delayed_refs,
246 : : struct btrfs_delayed_ref_node *ref)
247 : : {
248 : 0 : rb_erase(&ref->rb_node, &delayed_refs->root);
249 : 0 : ref->in_tree = 0;
250 : : btrfs_put_delayed_ref(ref);
251 : 0 : delayed_refs->num_entries--;
252 [ # # ][ # # ]: 0 : if (trans->delayed_ref_updates)
[ # # ]
253 : 0 : trans->delayed_ref_updates--;
254 : : }
255 : :
256 : 0 : static int merge_ref(struct btrfs_trans_handle *trans,
257 : : struct btrfs_delayed_ref_root *delayed_refs,
258 : : struct btrfs_delayed_ref_node *ref, u64 seq)
259 : : {
260 : : struct rb_node *node;
261 : : int merged = 0;
262 : : int mod = 0;
263 : : int done = 0;
264 : :
265 : 0 : node = rb_prev(&ref->rb_node);
266 [ # # ]: 0 : while (node) {
267 : : struct btrfs_delayed_ref_node *next;
268 : :
269 : : next = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
270 : 0 : node = rb_prev(node);
271 [ # # ]: 0 : if (next->bytenr != ref->bytenr)
272 : : break;
273 [ # # ][ # # ]: 0 : if (seq && next->seq >= seq)
274 : : break;
275 [ # # ]: 0 : if (comp_entry(ref, next, 0))
276 : 0 : continue;
277 : :
278 [ # # ]: 0 : if (ref->action == next->action) {
279 : 0 : mod = next->ref_mod;
280 : : } else {
281 [ # # ]: 0 : if (ref->ref_mod < next->ref_mod) {
282 : : struct btrfs_delayed_ref_node *tmp;
283 : :
284 : : tmp = ref;
285 : : ref = next;
286 : : next = tmp;
287 : : done = 1;
288 : : }
289 : 0 : mod = -next->ref_mod;
290 : : }
291 : :
292 : 0 : merged++;
293 : : drop_delayed_ref(trans, delayed_refs, next);
294 : 0 : ref->ref_mod += mod;
295 [ # # ]: 0 : if (ref->ref_mod == 0) {
296 : : drop_delayed_ref(trans, delayed_refs, ref);
297 : : break;
298 : : } else {
299 : : /*
300 : : * You can't have multiples of the same ref on a tree
301 : : * block.
302 : : */
303 [ # # ]: 0 : WARN_ON(ref->type == BTRFS_TREE_BLOCK_REF_KEY ||
304 : : ref->type == BTRFS_SHARED_BLOCK_REF_KEY);
305 : : }
306 : :
307 [ # # ]: 0 : if (done)
308 : : break;
309 : 0 : node = rb_prev(&ref->rb_node);
310 : : }
311 : :
312 : 0 : return merged;
313 : : }
314 : :
315 : 0 : void btrfs_merge_delayed_refs(struct btrfs_trans_handle *trans,
316 : : struct btrfs_fs_info *fs_info,
317 : : struct btrfs_delayed_ref_root *delayed_refs,
318 : : struct btrfs_delayed_ref_head *head)
319 : : {
320 : : struct rb_node *node;
321 : : u64 seq = 0;
322 : :
323 : : spin_lock(&fs_info->tree_mod_seq_lock);
324 [ # # ]: 0 : if (!list_empty(&fs_info->tree_mod_seq_list)) {
325 : : struct seq_list *elem;
326 : :
327 : : elem = list_first_entry(&fs_info->tree_mod_seq_list,
328 : : struct seq_list, list);
329 : 0 : seq = elem->seq;
330 : : }
331 : : spin_unlock(&fs_info->tree_mod_seq_lock);
332 : :
333 : 0 : node = rb_prev(&head->node.rb_node);
334 [ # # ]: 0 : while (node) {
335 : : struct btrfs_delayed_ref_node *ref;
336 : :
337 : : ref = rb_entry(node, struct btrfs_delayed_ref_node,
338 : : rb_node);
339 [ # # ]: 0 : if (ref->bytenr != head->node.bytenr)
340 : : break;
341 : :
342 : : /* We can't merge refs that are outside of our seq count */
343 [ # # ][ # # ]: 0 : if (seq && ref->seq >= seq)
344 : : break;
345 [ # # ]: 0 : if (merge_ref(trans, delayed_refs, ref, seq))
346 : 0 : node = rb_prev(&head->node.rb_node);
347 : : else
348 : 0 : node = rb_prev(node);
349 : : }
350 : 0 : }
351 : :
352 : 0 : int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info,
353 : : struct btrfs_delayed_ref_root *delayed_refs,
354 : : u64 seq)
355 : : {
356 : : struct seq_list *elem;
357 : : int ret = 0;
358 : :
359 : : spin_lock(&fs_info->tree_mod_seq_lock);
360 [ # # ]: 0 : if (!list_empty(&fs_info->tree_mod_seq_list)) {
361 : : elem = list_first_entry(&fs_info->tree_mod_seq_list,
362 : : struct seq_list, list);
363 [ # # ]: 0 : if (seq >= elem->seq) {
364 : : pr_debug("holding back delayed_ref %#x.%x, lowest is %#x.%x (%p)\n",
365 : : (u32)(seq >> 32), (u32)seq,
366 : : (u32)(elem->seq >> 32), (u32)elem->seq,
367 : : delayed_refs);
368 : : ret = 1;
369 : : }
370 : : }
371 : :
372 : : spin_unlock(&fs_info->tree_mod_seq_lock);
373 : 0 : return ret;
374 : : }
375 : :
376 : 0 : int btrfs_find_ref_cluster(struct btrfs_trans_handle *trans,
377 : : struct list_head *cluster, u64 start)
378 : : {
379 : : int count = 0;
380 : : struct btrfs_delayed_ref_root *delayed_refs;
381 : : struct rb_node *node;
382 : : struct btrfs_delayed_ref_node *ref;
383 : : struct btrfs_delayed_ref_head *head;
384 : :
385 : 0 : delayed_refs = &trans->transaction->delayed_refs;
386 [ # # ]: 0 : if (start == 0) {
387 : 0 : node = rb_first(&delayed_refs->root);
388 : : } else {
389 : 0 : ref = NULL;
390 : 0 : find_ref_head(&delayed_refs->root, start + 1, &ref, 1);
391 [ # # ]: 0 : if (ref) {
392 : 0 : node = &ref->rb_node;
393 : : } else
394 : 0 : node = rb_first(&delayed_refs->root);
395 : : }
396 : : again:
397 [ # # ]: 0 : while (node && count < 32) {
398 : 0 : ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
399 [ # # ]: 0 : if (btrfs_delayed_ref_is_head(ref)) {
400 : : head = btrfs_delayed_node_to_head(ref);
401 [ # # ]: 0 : if (list_empty(&head->cluster)) {
402 : : list_add_tail(&head->cluster, cluster);
403 : 0 : delayed_refs->run_delayed_start =
404 : 0 : head->node.bytenr;
405 : 0 : count++;
406 : :
407 [ # # ]: 0 : WARN_ON(delayed_refs->num_heads_ready == 0);
408 : 0 : delayed_refs->num_heads_ready--;
409 [ # # ]: 0 : } else if (count) {
410 : : /* the goal of the clustering is to find extents
411 : : * that are likely to end up in the same extent
412 : : * leaf on disk. So, we don't want them spread
413 : : * all over the tree. Stop now if we've hit
414 : : * a head that was already in use
415 : : */
416 : : break;
417 : : }
418 : : }
419 : 0 : node = rb_next(node);
420 : : }
421 [ # # ]: 0 : if (count) {
422 : : return 0;
423 [ # # ]: 0 : } else if (start) {
424 : : /*
425 : : * we've gone to the end of the rbtree without finding any
426 : : * clusters. start from the beginning and try again
427 : : */
428 : : start = 0;
429 : 0 : node = rb_first(&delayed_refs->root);
430 : 0 : goto again;
431 : : }
432 : : return 1;
433 : : }
434 : :
435 : 0 : void btrfs_release_ref_cluster(struct list_head *cluster)
436 : : {
437 : : struct list_head *pos, *q;
438 : :
439 [ # # ]: 0 : list_for_each_safe(pos, q, cluster)
440 : : list_del_init(pos);
441 : 0 : }
442 : :
443 : : /*
444 : : * helper function to update an extent delayed ref in the
445 : : * rbtree. existing and update must both have the same
446 : : * bytenr and parent
447 : : *
448 : : * This may free existing if the update cancels out whatever
449 : : * operation it was doing.
450 : : */
451 : : static noinline void
452 : 0 : update_existing_ref(struct btrfs_trans_handle *trans,
453 : : struct btrfs_delayed_ref_root *delayed_refs,
454 : : struct btrfs_delayed_ref_node *existing,
455 : : struct btrfs_delayed_ref_node *update)
456 : : {
457 [ # # ]: 0 : if (update->action != existing->action) {
458 : : /*
459 : : * this is effectively undoing either an add or a
460 : : * drop. We decrement the ref_mod, and if it goes
461 : : * down to zero we just delete the entry without
462 : : * every changing the extent allocation tree.
463 : : */
464 : 0 : existing->ref_mod--;
465 [ # # ]: 0 : if (existing->ref_mod == 0)
466 : : drop_delayed_ref(trans, delayed_refs, existing);
467 : : else
468 [ # # ]: 0 : WARN_ON(existing->type == BTRFS_TREE_BLOCK_REF_KEY ||
469 : : existing->type == BTRFS_SHARED_BLOCK_REF_KEY);
470 : : } else {
471 [ # # ]: 0 : WARN_ON(existing->type == BTRFS_TREE_BLOCK_REF_KEY ||
472 : : existing->type == BTRFS_SHARED_BLOCK_REF_KEY);
473 : : /*
474 : : * the action on the existing ref matches
475 : : * the action on the ref we're trying to add.
476 : : * Bump the ref_mod by one so the backref that
477 : : * is eventually added/removed has the correct
478 : : * reference count
479 : : */
480 : 0 : existing->ref_mod += update->ref_mod;
481 : : }
482 : 0 : }
483 : :
484 : : /*
485 : : * helper function to update the accounting in the head ref
486 : : * existing and update must have the same bytenr
487 : : */
488 : : static noinline void
489 : 0 : update_existing_head_ref(struct btrfs_delayed_ref_node *existing,
490 : : struct btrfs_delayed_ref_node *update)
491 : : {
492 : : struct btrfs_delayed_ref_head *existing_ref;
493 : : struct btrfs_delayed_ref_head *ref;
494 : :
495 : : existing_ref = btrfs_delayed_node_to_head(existing);
496 : : ref = btrfs_delayed_node_to_head(update);
497 [ # # ]: 0 : BUG_ON(existing_ref->is_data != ref->is_data);
498 : :
499 [ # # ]: 0 : if (ref->must_insert_reserved) {
500 : : /* if the extent was freed and then
501 : : * reallocated before the delayed ref
502 : : * entries were processed, we can end up
503 : : * with an existing head ref without
504 : : * the must_insert_reserved flag set.
505 : : * Set it again here
506 : : */
507 : 0 : existing_ref->must_insert_reserved = ref->must_insert_reserved;
508 : :
509 : : /*
510 : : * update the num_bytes so we make sure the accounting
511 : : * is done correctly
512 : : */
513 : 0 : existing->num_bytes = update->num_bytes;
514 : :
515 : : }
516 : :
517 [ # # ]: 0 : if (ref->extent_op) {
518 [ # # ]: 0 : if (!existing_ref->extent_op) {
519 : 0 : existing_ref->extent_op = ref->extent_op;
520 : : } else {
521 [ # # ]: 0 : if (ref->extent_op->update_key) {
522 : 0 : memcpy(&existing_ref->extent_op->key,
523 : 0 : &ref->extent_op->key,
524 : : sizeof(ref->extent_op->key));
525 : 0 : existing_ref->extent_op->update_key = 1;
526 : : }
527 [ # # ]: 0 : if (ref->extent_op->update_flags) {
528 : 0 : existing_ref->extent_op->flags_to_set |=
529 : 0 : ref->extent_op->flags_to_set;
530 : 0 : existing_ref->extent_op->update_flags = 1;
531 : : }
532 : 0 : btrfs_free_delayed_extent_op(ref->extent_op);
533 : : }
534 : : }
535 : : /*
536 : : * update the reference mod on the head to reflect this new operation
537 : : */
538 : 0 : existing->ref_mod += update->ref_mod;
539 : 0 : }
540 : :
541 : : /*
542 : : * helper function to actually insert a head node into the rbtree.
543 : : * this does all the dirty work in terms of maintaining the correct
544 : : * overall modification count.
545 : : */
546 : 0 : static noinline void add_delayed_ref_head(struct btrfs_fs_info *fs_info,
547 : : struct btrfs_trans_handle *trans,
548 : : struct btrfs_delayed_ref_node *ref,
549 : : u64 bytenr, u64 num_bytes,
550 : : int action, int is_data)
551 : : {
552 : : struct btrfs_delayed_ref_node *existing;
553 : : struct btrfs_delayed_ref_head *head_ref = NULL;
554 : : struct btrfs_delayed_ref_root *delayed_refs;
555 : : int count_mod = 1;
556 : : int must_insert_reserved = 0;
557 : :
558 : : /*
559 : : * the head node stores the sum of all the mods, so dropping a ref
560 : : * should drop the sum in the head node by one.
561 : : */
562 [ # # ]: 0 : if (action == BTRFS_UPDATE_DELAYED_HEAD)
563 : : count_mod = 0;
564 [ # # ]: 0 : else if (action == BTRFS_DROP_DELAYED_REF)
565 : : count_mod = -1;
566 : :
567 : : /*
568 : : * BTRFS_ADD_DELAYED_EXTENT means that we need to update
569 : : * the reserved accounting when the extent is finally added, or
570 : : * if a later modification deletes the delayed ref without ever
571 : : * inserting the extent into the extent allocation tree.
572 : : * ref->must_insert_reserved is the flag used to record
573 : : * that accounting mods are required.
574 : : *
575 : : * Once we record must_insert_reserved, switch the action to
576 : : * BTRFS_ADD_DELAYED_REF because other special casing is not required.
577 : : */
578 [ # # ]: 0 : if (action == BTRFS_ADD_DELAYED_EXTENT)
579 : : must_insert_reserved = 1;
580 : : else
581 : : must_insert_reserved = 0;
582 : :
583 : 0 : delayed_refs = &trans->transaction->delayed_refs;
584 : :
585 : : /* first set the basic ref node struct up */
586 : 0 : atomic_set(&ref->refs, 1);
587 : 0 : ref->bytenr = bytenr;
588 : 0 : ref->num_bytes = num_bytes;
589 : 0 : ref->ref_mod = count_mod;
590 : 0 : ref->type = 0;
591 : 0 : ref->action = 0;
592 : 0 : ref->is_head = 1;
593 : 0 : ref->in_tree = 1;
594 : 0 : ref->seq = 0;
595 : :
596 : : head_ref = btrfs_delayed_node_to_head(ref);
597 : 0 : head_ref->must_insert_reserved = must_insert_reserved;
598 : 0 : head_ref->is_data = is_data;
599 : :
600 : 0 : INIT_LIST_HEAD(&head_ref->cluster);
601 : 0 : mutex_init(&head_ref->mutex);
602 : :
603 : : trace_add_delayed_ref_head(ref, head_ref, action);
604 : :
605 : 0 : existing = tree_insert(&delayed_refs->root, &ref->rb_node);
606 : :
607 [ # # ]: 0 : if (existing) {
608 : 0 : update_existing_head_ref(existing, ref);
609 : : /*
610 : : * we've updated the existing ref, free the newly
611 : : * allocated ref
612 : : */
613 : 0 : kmem_cache_free(btrfs_delayed_ref_head_cachep, head_ref);
614 : : } else {
615 : 0 : delayed_refs->num_heads++;
616 : 0 : delayed_refs->num_heads_ready++;
617 : 0 : delayed_refs->num_entries++;
618 : 0 : trans->delayed_ref_updates++;
619 : : }
620 : 0 : }
621 : :
622 : : /*
623 : : * helper to insert a delayed tree ref into the rbtree.
624 : : */
625 : 0 : static noinline void add_delayed_tree_ref(struct btrfs_fs_info *fs_info,
626 : : struct btrfs_trans_handle *trans,
627 : : struct btrfs_delayed_ref_node *ref,
628 : : u64 bytenr, u64 num_bytes, u64 parent,
629 : : u64 ref_root, int level, int action,
630 : : int for_cow)
631 : : {
632 : : struct btrfs_delayed_ref_node *existing;
633 : : struct btrfs_delayed_tree_ref *full_ref;
634 : : struct btrfs_delayed_ref_root *delayed_refs;
635 : : u64 seq = 0;
636 : :
637 [ # # ]: 0 : if (action == BTRFS_ADD_DELAYED_EXTENT)
638 : : action = BTRFS_ADD_DELAYED_REF;
639 : :
640 : 0 : delayed_refs = &trans->transaction->delayed_refs;
641 : :
642 : : /* first set the basic ref node struct up */
643 : 0 : atomic_set(&ref->refs, 1);
644 : 0 : ref->bytenr = bytenr;
645 : 0 : ref->num_bytes = num_bytes;
646 : 0 : ref->ref_mod = 1;
647 : 0 : ref->action = action;
648 : 0 : ref->is_head = 0;
649 : 0 : ref->in_tree = 1;
650 : :
651 [ # # ]: 0 : if (need_ref_seq(for_cow, ref_root))
652 : 0 : seq = btrfs_get_tree_mod_seq(fs_info, &trans->delayed_ref_elem);
653 : 0 : ref->seq = seq;
654 : :
655 : : full_ref = btrfs_delayed_node_to_tree_ref(ref);
656 : 0 : full_ref->parent = parent;
657 : 0 : full_ref->root = ref_root;
658 [ # # ]: 0 : if (parent)
659 : 0 : ref->type = BTRFS_SHARED_BLOCK_REF_KEY;
660 : : else
661 : 0 : ref->type = BTRFS_TREE_BLOCK_REF_KEY;
662 : 0 : full_ref->level = level;
663 : :
664 : : trace_add_delayed_tree_ref(ref, full_ref, action);
665 : :
666 : 0 : existing = tree_insert(&delayed_refs->root, &ref->rb_node);
667 : :
668 [ # # ]: 0 : if (existing) {
669 : 0 : update_existing_ref(trans, delayed_refs, existing, ref);
670 : : /*
671 : : * we've updated the existing ref, free the newly
672 : : * allocated ref
673 : : */
674 : 0 : kmem_cache_free(btrfs_delayed_tree_ref_cachep, full_ref);
675 : : } else {
676 : 0 : delayed_refs->num_entries++;
677 : 0 : trans->delayed_ref_updates++;
678 : : }
679 : 0 : }
680 : :
681 : : /*
682 : : * helper to insert a delayed data ref into the rbtree.
683 : : */
684 : 0 : static noinline void add_delayed_data_ref(struct btrfs_fs_info *fs_info,
685 : : struct btrfs_trans_handle *trans,
686 : : struct btrfs_delayed_ref_node *ref,
687 : : u64 bytenr, u64 num_bytes, u64 parent,
688 : : u64 ref_root, u64 owner, u64 offset,
689 : : int action, int for_cow)
690 : : {
691 : : struct btrfs_delayed_ref_node *existing;
692 : : struct btrfs_delayed_data_ref *full_ref;
693 : : struct btrfs_delayed_ref_root *delayed_refs;
694 : : u64 seq = 0;
695 : :
696 [ # # ]: 0 : if (action == BTRFS_ADD_DELAYED_EXTENT)
697 : : action = BTRFS_ADD_DELAYED_REF;
698 : :
699 : 0 : delayed_refs = &trans->transaction->delayed_refs;
700 : :
701 : : /* first set the basic ref node struct up */
702 : 0 : atomic_set(&ref->refs, 1);
703 : 0 : ref->bytenr = bytenr;
704 : 0 : ref->num_bytes = num_bytes;
705 : 0 : ref->ref_mod = 1;
706 : 0 : ref->action = action;
707 : 0 : ref->is_head = 0;
708 : 0 : ref->in_tree = 1;
709 : :
710 [ # # ]: 0 : if (need_ref_seq(for_cow, ref_root))
711 : 0 : seq = btrfs_get_tree_mod_seq(fs_info, &trans->delayed_ref_elem);
712 : 0 : ref->seq = seq;
713 : :
714 : : full_ref = btrfs_delayed_node_to_data_ref(ref);
715 : 0 : full_ref->parent = parent;
716 : 0 : full_ref->root = ref_root;
717 [ # # ]: 0 : if (parent)
718 : 0 : ref->type = BTRFS_SHARED_DATA_REF_KEY;
719 : : else
720 : 0 : ref->type = BTRFS_EXTENT_DATA_REF_KEY;
721 : :
722 : 0 : full_ref->objectid = owner;
723 : 0 : full_ref->offset = offset;
724 : :
725 : : trace_add_delayed_data_ref(ref, full_ref, action);
726 : :
727 : 0 : existing = tree_insert(&delayed_refs->root, &ref->rb_node);
728 : :
729 [ # # ]: 0 : if (existing) {
730 : 0 : update_existing_ref(trans, delayed_refs, existing, ref);
731 : : /*
732 : : * we've updated the existing ref, free the newly
733 : : * allocated ref
734 : : */
735 : 0 : kmem_cache_free(btrfs_delayed_data_ref_cachep, full_ref);
736 : : } else {
737 : 0 : delayed_refs->num_entries++;
738 : 0 : trans->delayed_ref_updates++;
739 : : }
740 : 0 : }
741 : :
742 : : /*
743 : : * add a delayed tree ref. This does all of the accounting required
744 : : * to make sure the delayed ref is eventually processed before this
745 : : * transaction commits.
746 : : */
747 : 0 : int btrfs_add_delayed_tree_ref(struct btrfs_fs_info *fs_info,
748 : 0 : struct btrfs_trans_handle *trans,
749 : : u64 bytenr, u64 num_bytes, u64 parent,
750 : : u64 ref_root, int level, int action,
751 : : struct btrfs_delayed_extent_op *extent_op,
752 : : int for_cow)
753 : : {
754 : : struct btrfs_delayed_tree_ref *ref;
755 : : struct btrfs_delayed_ref_head *head_ref;
756 : : struct btrfs_delayed_ref_root *delayed_refs;
757 : :
758 [ # # ][ # # ]: 0 : BUG_ON(extent_op && extent_op->is_data);
759 : 0 : ref = kmem_cache_alloc(btrfs_delayed_tree_ref_cachep, GFP_NOFS);
760 [ # # ]: 0 : if (!ref)
761 : : return -ENOMEM;
762 : :
763 : 0 : head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
764 [ # # ]: 0 : if (!head_ref) {
765 : 0 : kmem_cache_free(btrfs_delayed_tree_ref_cachep, ref);
766 : 0 : return -ENOMEM;
767 : : }
768 : :
769 : 0 : head_ref->extent_op = extent_op;
770 : :
771 : 0 : delayed_refs = &trans->transaction->delayed_refs;
772 : : spin_lock(&delayed_refs->lock);
773 : :
774 : : /*
775 : : * insert both the head node and the new ref without dropping
776 : : * the spin lock
777 : : */
778 : 0 : add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
779 : : num_bytes, action, 0);
780 : :
781 : 0 : add_delayed_tree_ref(fs_info, trans, &ref->node, bytenr,
782 : : num_bytes, parent, ref_root, level, action,
783 : : for_cow);
784 : : spin_unlock(&delayed_refs->lock);
785 [ # # ]: 0 : if (need_ref_seq(for_cow, ref_root))
786 : 0 : btrfs_qgroup_record_ref(trans, &ref->node, extent_op);
787 : :
788 : : return 0;
789 : : }
790 : :
791 : : /*
792 : : * add a delayed data ref. it's similar to btrfs_add_delayed_tree_ref.
793 : : */
794 : 0 : int btrfs_add_delayed_data_ref(struct btrfs_fs_info *fs_info,
795 : 0 : struct btrfs_trans_handle *trans,
796 : : u64 bytenr, u64 num_bytes,
797 : : u64 parent, u64 ref_root,
798 : : u64 owner, u64 offset, int action,
799 : : struct btrfs_delayed_extent_op *extent_op,
800 : : int for_cow)
801 : : {
802 : : struct btrfs_delayed_data_ref *ref;
803 : : struct btrfs_delayed_ref_head *head_ref;
804 : : struct btrfs_delayed_ref_root *delayed_refs;
805 : :
806 [ # # ][ # # ]: 0 : BUG_ON(extent_op && !extent_op->is_data);
807 : 0 : ref = kmem_cache_alloc(btrfs_delayed_data_ref_cachep, GFP_NOFS);
808 [ # # ]: 0 : if (!ref)
809 : : return -ENOMEM;
810 : :
811 : 0 : head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
812 [ # # ]: 0 : if (!head_ref) {
813 : 0 : kmem_cache_free(btrfs_delayed_data_ref_cachep, ref);
814 : 0 : return -ENOMEM;
815 : : }
816 : :
817 : 0 : head_ref->extent_op = extent_op;
818 : :
819 : 0 : delayed_refs = &trans->transaction->delayed_refs;
820 : : spin_lock(&delayed_refs->lock);
821 : :
822 : : /*
823 : : * insert both the head node and the new ref without dropping
824 : : * the spin lock
825 : : */
826 : 0 : add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
827 : : num_bytes, action, 1);
828 : :
829 : 0 : add_delayed_data_ref(fs_info, trans, &ref->node, bytenr,
830 : : num_bytes, parent, ref_root, owner, offset,
831 : : action, for_cow);
832 : : spin_unlock(&delayed_refs->lock);
833 [ # # ]: 0 : if (need_ref_seq(for_cow, ref_root))
834 : 0 : btrfs_qgroup_record_ref(trans, &ref->node, extent_op);
835 : :
836 : : return 0;
837 : : }
838 : :
839 : 0 : int btrfs_add_delayed_extent_op(struct btrfs_fs_info *fs_info,
840 : 0 : struct btrfs_trans_handle *trans,
841 : : u64 bytenr, u64 num_bytes,
842 : : struct btrfs_delayed_extent_op *extent_op)
843 : : {
844 : : struct btrfs_delayed_ref_head *head_ref;
845 : : struct btrfs_delayed_ref_root *delayed_refs;
846 : :
847 : 0 : head_ref = kmem_cache_alloc(btrfs_delayed_ref_head_cachep, GFP_NOFS);
848 [ # # ]: 0 : if (!head_ref)
849 : : return -ENOMEM;
850 : :
851 : 0 : head_ref->extent_op = extent_op;
852 : :
853 : 0 : delayed_refs = &trans->transaction->delayed_refs;
854 : : spin_lock(&delayed_refs->lock);
855 : :
856 : 0 : add_delayed_ref_head(fs_info, trans, &head_ref->node, bytenr,
857 : : num_bytes, BTRFS_UPDATE_DELAYED_HEAD,
858 : 0 : extent_op->is_data);
859 : :
860 : : spin_unlock(&delayed_refs->lock);
861 : 0 : return 0;
862 : : }
863 : :
864 : : /*
865 : : * this does a simple search for the head node for a given extent.
866 : : * It must be called with the delayed ref spinlock held, and it returns
867 : : * the head node if any where found, or NULL if not.
868 : : */
869 : : struct btrfs_delayed_ref_head *
870 : 0 : btrfs_find_delayed_ref_head(struct btrfs_trans_handle *trans, u64 bytenr)
871 : : {
872 : : struct btrfs_delayed_ref_node *ref;
873 : : struct btrfs_delayed_ref_root *delayed_refs;
874 : :
875 : 0 : delayed_refs = &trans->transaction->delayed_refs;
876 : 0 : ref = find_ref_head(&delayed_refs->root, bytenr, NULL, 0);
877 [ # # ]: 0 : if (ref)
878 : 0 : return btrfs_delayed_node_to_head(ref);
879 : : return NULL;
880 : : }
881 : :
882 : 0 : void btrfs_delayed_ref_exit(void)
883 : : {
884 [ # # ]: 0 : if (btrfs_delayed_ref_head_cachep)
885 : 0 : kmem_cache_destroy(btrfs_delayed_ref_head_cachep);
886 [ # # ]: 0 : if (btrfs_delayed_tree_ref_cachep)
887 : 0 : kmem_cache_destroy(btrfs_delayed_tree_ref_cachep);
888 [ # # ]: 0 : if (btrfs_delayed_data_ref_cachep)
889 : 0 : kmem_cache_destroy(btrfs_delayed_data_ref_cachep);
890 [ # # ]: 0 : if (btrfs_delayed_extent_op_cachep)
891 : 0 : kmem_cache_destroy(btrfs_delayed_extent_op_cachep);
892 : 0 : }
893 : :
894 : 0 : int btrfs_delayed_ref_init(void)
895 : : {
896 : 0 : btrfs_delayed_ref_head_cachep = kmem_cache_create(
897 : : "btrfs_delayed_ref_head",
898 : : sizeof(struct btrfs_delayed_ref_head), 0,
899 : : SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
900 [ # # ]: 0 : if (!btrfs_delayed_ref_head_cachep)
901 : : goto fail;
902 : :
903 : 0 : btrfs_delayed_tree_ref_cachep = kmem_cache_create(
904 : : "btrfs_delayed_tree_ref",
905 : : sizeof(struct btrfs_delayed_tree_ref), 0,
906 : : SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
907 [ # # ]: 0 : if (!btrfs_delayed_tree_ref_cachep)
908 : : goto fail;
909 : :
910 : 0 : btrfs_delayed_data_ref_cachep = kmem_cache_create(
911 : : "btrfs_delayed_data_ref",
912 : : sizeof(struct btrfs_delayed_data_ref), 0,
913 : : SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
914 [ # # ]: 0 : if (!btrfs_delayed_data_ref_cachep)
915 : : goto fail;
916 : :
917 : 0 : btrfs_delayed_extent_op_cachep = kmem_cache_create(
918 : : "btrfs_delayed_extent_op",
919 : : sizeof(struct btrfs_delayed_extent_op), 0,
920 : : SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
921 [ # # ]: 0 : if (!btrfs_delayed_extent_op_cachep)
922 : : goto fail;
923 : :
924 : : return 0;
925 : : fail:
926 : 0 : btrfs_delayed_ref_exit();
927 : 0 : return -ENOMEM;
928 : : }
|
