projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Btrfs: Fix extent_buffer and extent_state leaks
[deliverable/linux.git] / fs / btrfs / ctree.c
1 /*
2 * Copyright (C) 2007 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/highmem.h>
20 #include "ctree.h"
21 #include "disk-io.h"
22 #include "transaction.h"
23 #include "print-tree.h"
24
25 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
26 *root, struct btrfs_path *path, int level);
27 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
28 *root, struct btrfs_key *ins_key,
29 struct btrfs_path *path, int data_size);
30 static int push_node_left(struct btrfs_trans_handle *trans,
31 struct btrfs_root *root, struct extent_buffer *dst,
32 struct extent_buffer *src);
33 static int balance_node_right(struct btrfs_trans_handle *trans,
34 struct btrfs_root *root,
35 struct extent_buffer *dst_buf,
36 struct extent_buffer *src_buf);
37 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
38 struct btrfs_path *path, int level, int slot);
39
40 inline void btrfs_init_path(struct btrfs_path *p)
41 {
42 memset(p, 0, sizeof(*p));
43 }
44
45 struct btrfs_path *btrfs_alloc_path(void)
46 {
47 struct btrfs_path *path;
48 path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
49 if (path) {
50 btrfs_init_path(path);
51 path->reada = 1;
52 }
53 return path;
54 }
55
56 void btrfs_free_path(struct btrfs_path *p)
57 {
58 btrfs_release_path(NULL, p);
59 kmem_cache_free(btrfs_path_cachep, p);
60 }
61
62 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
63 {
64 int i;
65 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
66 if (!p->nodes[i])
67 break;
68 free_extent_buffer(p->nodes[i]);
69 }
70 memset(p, 0, sizeof(*p));
71 }
72
73 static int __btrfs_cow_block(struct btrfs_trans_handle *trans,
74 struct btrfs_root *root,
75 struct extent_buffer *buf,
76 struct extent_buffer *parent, int parent_slot,
77 struct extent_buffer **cow_ret,
78 u64 search_start, u64 empty_size)
79 {
80 struct extent_buffer *cow;
81 int ret = 0;
82 int different_trans = 0;
83
84 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
85
86 cow = btrfs_alloc_free_block(trans, root, search_start, empty_size);
87 if (IS_ERR(cow))
88 return PTR_ERR(cow);
89
90 cow->alloc_addr = (unsigned long)__builtin_return_address(0);
91 if (buf->len != root->sectorsize || cow->len != root->sectorsize)
92 WARN_ON(1);
93
94 copy_extent_buffer(cow, buf, 0, 0, cow->len);
95 btrfs_set_header_blocknr(cow, extent_buffer_blocknr(cow));
96 btrfs_set_header_generation(cow, trans->transid);
97 btrfs_set_header_owner(cow, root->root_key.objectid);
98
99 WARN_ON(btrfs_header_generation(buf) > trans->transid);
100 if (btrfs_header_generation(buf) != trans->transid) {
101 different_trans = 1;
102 ret = btrfs_inc_ref(trans, root, buf);
103 if (ret)
104 return ret;
105 } else {
106 clean_tree_block(trans, root, buf);
107 }
108
109 if (buf == root->node) {
110 root->node = cow;
111 extent_buffer_get(cow);
112 if (buf != root->commit_root) {
113 btrfs_free_extent(trans, root,
114 extent_buffer_blocknr(buf), 1, 1);
115 }
116 free_extent_buffer(buf);
117 } else {
118 btrfs_set_node_blockptr(parent, parent_slot,
119 extent_buffer_blocknr(cow));
120 btrfs_mark_buffer_dirty(parent);
121 WARN_ON(btrfs_header_generation(parent) != trans->transid);
122 btrfs_free_extent(trans, root, extent_buffer_blocknr(buf),1,1);
123 }
124 free_extent_buffer(buf);
125 btrfs_mark_buffer_dirty(cow);
126 *cow_ret = cow;
127 return 0;
128 }
129
130 int btrfs_cow_block(struct btrfs_trans_handle *trans,
131 struct btrfs_root *root, struct extent_buffer *buf,
132 struct extent_buffer *parent, int parent_slot,
133 struct extent_buffer **cow_ret)
134 {
135 u64 search_start;
136 int ret;
137 if (trans->transaction != root->fs_info->running_transaction) {
138 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
139 root->fs_info->running_transaction->transid);
140 WARN_ON(1);
141 }
142 if (trans->transid != root->fs_info->generation) {
143 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
144 root->fs_info->generation);
145 WARN_ON(1);
146 }
147 if (btrfs_header_generation(buf) == trans->transid) {
148 *cow_ret = buf;
149 return 0;
150 }
151
152 search_start = extent_buffer_blocknr(buf) & ~((u64)65535);
153 ret = __btrfs_cow_block(trans, root, buf, parent,
154 parent_slot, cow_ret, search_start, 0);
155 (*cow_ret)->alloc_addr = (unsigned long)__builtin_return_address(0);
156 return ret;
157 }
158
159 static int close_blocks(u64 blocknr, u64 other)
160 {
161 if (blocknr < other && other - blocknr < 8)
162 return 1;
163 if (blocknr > other && blocknr - other < 8)
164 return 1;
165 return 0;
166 }
167
168 #if 0
169 static int should_defrag_leaf(struct extent_buffer *eb)
170 {
171 return 0;
172 struct btrfs_leaf *leaf = btrfs_buffer_leaf(eb);
173 struct btrfs_disk_key *key;
174 u32 nritems;
175
176 if (buffer_defrag(bh))
177 return 1;
178
179 nritems = btrfs_header_nritems(&leaf->header);
180 if (nritems == 0)
181 return 0;
182
183 key = &leaf->items[0].key;
184 if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY)
185 return 1;
186
187 key = &leaf->items[nritems-1].key;
188 if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY)
189 return 1;
190 if (nritems > 4) {
191 key = &leaf->items[nritems/2].key;
192 if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY)
193 return 1;
194 }
195 return 0;
196 }
197 #endif
198
199 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
200 struct btrfs_root *root, struct extent_buffer *parent,
201 int cache_only, u64 *last_ret)
202 {
203 return 0;
204 #if 0
205 struct btrfs_node *parent_node;
206 struct extent_buffer *cur_eb;
207 struct extent_buffer *tmp_eb;
208 u64 blocknr;
209 u64 search_start = *last_ret;
210 u64 last_block = 0;
211 u64 other;
212 u32 parent_nritems;
213 int start_slot;
214 int end_slot;
215 int i;
216 int err = 0;
217 int parent_level;
218
219 if (trans->transaction != root->fs_info->running_transaction) {
220 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
221 root->fs_info->running_transaction->transid);
222 WARN_ON(1);
223 }
224 if (trans->transid != root->fs_info->generation) {
225 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
226 root->fs_info->generation);
227 WARN_ON(1);
228 }
229 if (buffer_defrag_done(parent))
230 return 0;
231
232 parent_node = btrfs_buffer_node(parent);
233 parent_nritems = btrfs_header_nritems(&parent_node->header);
234 parent_level = btrfs_header_level(&parent_node->header);
235
236 start_slot = 0;
237 end_slot = parent_nritems;
238
239 if (parent_nritems == 1)
240 return 0;
241
242 for (i = start_slot; i < end_slot; i++) {
243 int close = 1;
244 blocknr = btrfs_node_blockptr(parent_node, i);
245 if (last_block == 0)
246 last_block = blocknr;
247 if (i > 0) {
248 other = btrfs_node_blockptr(parent_node, i - 1);
249 close = close_blocks(blocknr, other);
250 }
251 if (close && i < end_slot - 1) {
252 other = btrfs_node_blockptr(parent_node, i + 1);
253 close = close_blocks(blocknr, other);
254 }
255 if (close) {
256 last_block = blocknr;
257 continue;
258 }
259
260 cur_bh = btrfs_find_tree_block(root, blocknr);
261 if (!cur_bh || !buffer_uptodate(cur_bh) ||
262 buffer_locked(cur_bh) ||
263 (parent_level != 1 && !buffer_defrag(cur_bh)) ||
264 (parent_level == 1 && !should_defrag_leaf(cur_bh))) {
265 if (cache_only) {
266 brelse(cur_bh);
267 continue;
268 }
269 if (!cur_bh || !buffer_uptodate(cur_bh) ||
270 buffer_locked(cur_bh)) {
271 brelse(cur_bh);
272 cur_bh = read_tree_block(root, blocknr);
273 }
274 }
275 if (search_start == 0)
276 search_start = last_block & ~((u64)65535);
277
278 err = __btrfs_cow_block(trans, root, cur_bh, parent, i,
279 &tmp_bh, search_start,
280 min(8, end_slot - i));
281 if (err) {
282 brelse(cur_bh);
283 break;
284 }
285 search_start = bh_blocknr(tmp_bh);
286 *last_ret = search_start;
287 if (parent_level == 1)
288 clear_buffer_defrag(tmp_bh);
289 set_buffer_defrag_done(tmp_bh);
290 brelse(tmp_bh);
291 }
292 return err;
293 #endif
294 }
295
296 /*
297 * The leaf data grows from end-to-front in the node.
298 * this returns the address of the start of the last item,
299 * which is the stop of the leaf data stack
300 */
301 static inline unsigned int leaf_data_end(struct btrfs_root *root,
302 struct extent_buffer *leaf)
303 {
304 u32 nr = btrfs_header_nritems(leaf);
305 if (nr == 0)
306 return BTRFS_LEAF_DATA_SIZE(root);
307 return btrfs_item_offset_nr(leaf, nr - 1);
308 }
309
310 /*
311 * compare two keys in a memcmp fashion
312 */
313 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
314 {
315 struct btrfs_key k1;
316
317 btrfs_disk_key_to_cpu(&k1, disk);
318
319 if (k1.objectid > k2->objectid)
320 return 1;
321 if (k1.objectid < k2->objectid)
322 return -1;
323 if (k1.type > k2->type)
324 return 1;
325 if (k1.type < k2->type)
326 return -1;
327 if (k1.offset > k2->offset)
328 return 1;
329 if (k1.offset < k2->offset)
330 return -1;
331 return 0;
332 }
333
334 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
335 int level)
336 {
337 struct extent_buffer *parent = NULL;
338 struct extent_buffer *node = path->nodes[level];
339 struct btrfs_disk_key parent_key;
340 struct btrfs_disk_key node_key;
341 int parent_slot;
342 int slot;
343 struct btrfs_key cpukey;
344 u32 nritems = btrfs_header_nritems(node);
345
346 if (path->nodes[level + 1])
347 parent = path->nodes[level + 1];
348
349 slot = path->slots[level];
350 BUG_ON(nritems == 0);
351 if (parent) {
352 parent_slot = path->slots[level + 1];
353 btrfs_node_key(parent, &parent_key, parent_slot);
354 btrfs_node_key(node, &node_key, 0);
355 BUG_ON(memcmp(&parent_key, &node_key,
356 sizeof(struct btrfs_disk_key)));
357 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
358 btrfs_header_blocknr(node));
359 }
360 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
361 if (slot != 0) {
362 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
363 btrfs_node_key(node, &node_key, slot);
364 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
365 }
366 if (slot < nritems - 1) {
367 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
368 btrfs_node_key(node, &node_key, slot);
369 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
370 }
371 return 0;
372 }
373
374 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
375 int level)
376 {
377 struct extent_buffer *leaf = path->nodes[level];
378 struct extent_buffer *parent = NULL;
379 int parent_slot;
380 struct btrfs_key cpukey;
381 struct btrfs_disk_key parent_key;
382 struct btrfs_disk_key leaf_key;
383 int slot = path->slots[0];
384
385 u32 nritems = btrfs_header_nritems(leaf);
386
387 if (path->nodes[level + 1])
388 parent = path->nodes[level + 1];
389
390 if (nritems == 0)
391 return 0;
392
393 if (parent) {
394 parent_slot = path->slots[level + 1];
395 btrfs_node_key(parent, &parent_key, parent_slot);
396 btrfs_item_key(leaf, &leaf_key, 0);
397
398 BUG_ON(memcmp(&parent_key, &leaf_key,
399 sizeof(struct btrfs_disk_key)));
400 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
401 btrfs_header_blocknr(leaf));
402 }
403 #if 0
404 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
405 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
406 btrfs_item_key(leaf, &leaf_key, i);
407 if (comp_keys(&leaf_key, &cpukey) >= 0) {
408 btrfs_print_leaf(root, leaf);
409 printk("slot %d offset bad key\n", i);
410 BUG_ON(1);
411 }
412 if (btrfs_item_offset_nr(leaf, i) !=
413 btrfs_item_end_nr(leaf, i + 1)) {
414 btrfs_print_leaf(root, leaf);
415 printk("slot %d offset bad\n", i);
416 BUG_ON(1);
417 }
418 if (i == 0) {
419 if (btrfs_item_offset_nr(leaf, i) +
420 btrfs_item_size_nr(leaf, i) !=
421 BTRFS_LEAF_DATA_SIZE(root)) {
422 btrfs_print_leaf(root, leaf);
423 printk("slot %d first offset bad\n", i);
424 BUG_ON(1);
425 }
426 }
427 }
428 if (nritems > 0) {
429 if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
430 btrfs_print_leaf(root, leaf);
431 printk("slot %d bad size \n", nritems - 1);
432 BUG_ON(1);
433 }
434 }
435 #endif
436 if (slot != 0 && slot < nritems - 1) {
437 btrfs_item_key(leaf, &leaf_key, slot);
438 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
439 if (comp_keys(&leaf_key, &cpukey) <= 0) {
440 btrfs_print_leaf(root, leaf);
441 printk("slot %d offset bad key\n", slot);
442 BUG_ON(1);
443 }
444 if (btrfs_item_offset_nr(leaf, slot - 1) !=
445 btrfs_item_end_nr(leaf, slot)) {
446 btrfs_print_leaf(root, leaf);
447 printk("slot %d offset bad\n", slot);
448 BUG_ON(1);
449 }
450 }
451 if (slot < nritems - 1) {
452 btrfs_item_key(leaf, &leaf_key, slot);
453 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
454 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
455 if (btrfs_item_offset_nr(leaf, slot) !=
456 btrfs_item_end_nr(leaf, slot + 1)) {
457 btrfs_print_leaf(root, leaf);
458 printk("slot %d offset bad\n", slot);
459 BUG_ON(1);
460 }
461 }
462 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
463 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
464 return 0;
465 }
466
467 static int check_block(struct btrfs_root *root, struct btrfs_path *path,
468 int level)
469 {
470 struct extent_buffer *buf = path->nodes[level];
471
472 if (memcmp_extent_buffer(buf, root->fs_info->fsid,
473 (unsigned long)btrfs_header_fsid(buf),
474 BTRFS_FSID_SIZE)) {
475 printk("warning bad block %Lu\n", buf->start);
476 BUG();
477 }
478 if (level == 0)
479 return check_leaf(root, path, level);
480 return check_node(root, path, level);
481 }
482
483 /*
484 * search for key in the extent_buffer. The items start at offset p,
485 * and they are item_size apart. There are 'max' items in p.
486 *
487 * the slot in the array is returned via slot, and it points to
488 * the place where you would insert key if it is not found in
489 * the array.
490 *
491 * slot may point to max if the key is bigger than all of the keys
492 */
493 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
494 int item_size, struct btrfs_key *key,
495 int max, int *slot)
496 {
497 int low = 0;
498 int high = max;
499 int mid;
500 int ret;
501 struct btrfs_disk_key *tmp = NULL;
502 struct btrfs_disk_key unaligned;
503 unsigned long offset;
504 char *map_token = NULL;
505 char *kaddr = NULL;
506 unsigned long map_start = 0;
507 unsigned long map_len = 0;
508 int err;
509
510 while(low < high) {
511 mid = (low + high) / 2;
512 offset = p + mid * item_size;
513
514 if (!map_token || offset < map_start ||
515 (offset + sizeof(struct btrfs_disk_key)) >
516 map_start + map_len) {
517 if (map_token) {
518 unmap_extent_buffer(eb, map_token, KM_USER0);
519 map_token = NULL;
520 }
521 err = map_extent_buffer(eb, offset,
522 sizeof(struct btrfs_disk_key),
523 &map_token, &kaddr,
524 &map_start, &map_len, KM_USER0);
525
526 if (!err) {
527 tmp = (struct btrfs_disk_key *)(kaddr + offset -
528 map_start);
529 } else {
530 read_extent_buffer(eb, &unaligned,
531 offset, sizeof(unaligned));
532 tmp = &unaligned;
533 }
534
535 } else {
536 tmp = (struct btrfs_disk_key *)(kaddr + offset -
537 map_start);
538 }
539 ret = comp_keys(tmp, key);
540
541 if (ret < 0)
542 low = mid + 1;
543 else if (ret > 0)
544 high = mid;
545 else {
546 *slot = mid;
547 if (map_token)
548 unmap_extent_buffer(eb, map_token, KM_USER0);
549 return 0;
550 }
551 }
552 *slot = low;
553 if (map_token)
554 unmap_extent_buffer(eb, map_token, KM_USER0);
555 return 1;
556 }
557
558 /*
559 * simple bin_search frontend that does the right thing for
560 * leaves vs nodes
561 */
562 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
563 int level, int *slot)
564 {
565 if (level == 0) {
566 return generic_bin_search(eb,
567 offsetof(struct btrfs_leaf, items),
568 sizeof(struct btrfs_item),
569 key, btrfs_header_nritems(eb),
570 slot);
571 } else {
572 return generic_bin_search(eb,
573 offsetof(struct btrfs_node, ptrs),
574 sizeof(struct btrfs_key_ptr),
575 key, btrfs_header_nritems(eb),
576 slot);
577 }
578 return -1;
579 }
580
581 static struct extent_buffer *read_node_slot(struct btrfs_root *root,
582 struct extent_buffer *parent, int slot)
583 {
584 if (slot < 0)
585 return NULL;
586 if (slot >= btrfs_header_nritems(parent))
587 return NULL;
588 return read_tree_block(root, btrfs_node_blockptr(parent, slot));
589 }
590
591 static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
592 *root, struct btrfs_path *path, int level)
593 {
594 struct extent_buffer *right = NULL;
595 struct extent_buffer *mid;
596 struct extent_buffer *left = NULL;
597 struct extent_buffer *parent = NULL;
598 int ret = 0;
599 int wret;
600 int pslot;
601 int orig_slot = path->slots[level];
602 int err_on_enospc = 0;
603 u64 orig_ptr;
604
605 if (level == 0)
606 return 0;
607
608 mid = path->nodes[level];
609 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
610
611 if (level < BTRFS_MAX_LEVEL - 1)
612 parent = path->nodes[level + 1];
613 pslot = path->slots[level + 1];
614
615 /*
616 * deal with the case where there is only one pointer in the root
617 * by promoting the node below to a root
618 */
619 if (!parent) {
620 struct extent_buffer *child;
621 u64 blocknr = extent_buffer_blocknr(mid);
622
623 if (btrfs_header_nritems(mid) != 1)
624 return 0;
625
626 /* promote the child to a root */
627 child = read_node_slot(root, mid, 0);
628 BUG_ON(!child);
629 root->node = child;
630 path->nodes[level] = NULL;
631 clean_tree_block(trans, root, mid);
632 wait_on_tree_block_writeback(root, mid);
633 /* once for the path */
634 free_extent_buffer(mid);
635 /* once for the root ptr */
636 free_extent_buffer(mid);
637 return btrfs_free_extent(trans, root, blocknr, 1, 1);
638 }
639 if (btrfs_header_nritems(mid) >
640 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
641 return 0;
642
643 if (btrfs_header_nritems(mid) < 2)
644 err_on_enospc = 1;
645
646 left = read_node_slot(root, parent, pslot - 1);
647 if (left) {
648 wret = btrfs_cow_block(trans, root, left,
649 parent, pslot - 1, &left);
650 if (wret) {
651 ret = wret;
652 goto enospc;
653 }
654 }
655 right = read_node_slot(root, parent, pslot + 1);
656 if (right) {
657 wret = btrfs_cow_block(trans, root, right,
658 parent, pslot + 1, &right);
659 if (wret) {
660 ret = wret;
661 goto enospc;
662 }
663 }
664
665 /* first, try to make some room in the middle buffer */
666 if (left) {
667 orig_slot += btrfs_header_nritems(left);
668 wret = push_node_left(trans, root, left, mid);
669 if (wret < 0)
670 ret = wret;
671 if (btrfs_header_nritems(mid) < 2)
672 err_on_enospc = 1;
673 }
674
675 /*
676 * then try to empty the right most buffer into the middle
677 */
678 if (right) {
679 wret = push_node_left(trans, root, mid, right);
680 if (wret < 0 && wret != -ENOSPC)
681 ret = wret;
682 if (btrfs_header_nritems(right) == 0) {
683 u64 blocknr = extent_buffer_blocknr(right);
684 clean_tree_block(trans, root, right);
685 wait_on_tree_block_writeback(root, right);
686 free_extent_buffer(right);
687 right = NULL;
688 wret = del_ptr(trans, root, path, level + 1, pslot +
689 1);
690 if (wret)
691 ret = wret;
692 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
693 if (wret)
694 ret = wret;
695 } else {
696 struct btrfs_disk_key right_key;
697 btrfs_node_key(right, &right_key, 0);
698 btrfs_set_node_key(parent, &right_key, pslot + 1);
699 btrfs_mark_buffer_dirty(parent);
700 }
701 }
702 if (btrfs_header_nritems(mid) == 1) {
703 /*
704 * we're not allowed to leave a node with one item in the
705 * tree during a delete. A deletion from lower in the tree
706 * could try to delete the only pointer in this node.
707 * So, pull some keys from the left.
708 * There has to be a left pointer at this point because
709 * otherwise we would have pulled some pointers from the
710 * right
711 */
712 BUG_ON(!left);
713 wret = balance_node_right(trans, root, mid, left);
714 if (wret < 0) {
715 ret = wret;
716 goto enospc;
717 }
718 BUG_ON(wret == 1);
719 }
720 if (btrfs_header_nritems(mid) == 0) {
721 /* we've managed to empty the middle node, drop it */
722 u64 blocknr = extent_buffer_blocknr(mid);
723 clean_tree_block(trans, root, mid);
724 wait_on_tree_block_writeback(root, mid);
725 free_extent_buffer(mid);
726 mid = NULL;
727 wret = del_ptr(trans, root, path, level + 1, pslot);
728 if (wret)
729 ret = wret;
730 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
731 if (wret)
732 ret = wret;
733 } else {
734 /* update the parent key to reflect our changes */
735 struct btrfs_disk_key mid_key;
736 btrfs_node_key(mid, &mid_key, 0);
737 btrfs_set_node_key(parent, &mid_key, pslot);
738 btrfs_mark_buffer_dirty(parent);
739 }
740
741 /* update the path */
742 if (left) {
743 if (btrfs_header_nritems(left) > orig_slot) {
744 extent_buffer_get(left);
745 path->nodes[level] = left;
746 path->slots[level + 1] -= 1;
747 path->slots[level] = orig_slot;
748 if (mid)
749 free_extent_buffer(mid);
750 } else {
751 orig_slot -= btrfs_header_nritems(left);
752 path->slots[level] = orig_slot;
753 }
754 }
755 /* double check we haven't messed things up */
756 check_block(root, path, level);
757 if (orig_ptr !=
758 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
759 BUG();
760 enospc:
761 if (right)
762 free_extent_buffer(right);
763 if (left)
764 free_extent_buffer(left);
765 return ret;
766 }
767
768 /* returns zero if the push worked, non-zero otherwise */
769 static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
770 struct btrfs_root *root,
771 struct btrfs_path *path, int level)
772 {
773 struct extent_buffer *right = NULL;
774 struct extent_buffer *mid;
775 struct extent_buffer *left = NULL;
776 struct extent_buffer *parent = NULL;
777 int ret = 0;
778 int wret;
779 int pslot;
780 int orig_slot = path->slots[level];
781 u64 orig_ptr;
782
783 if (level == 0)
784 return 1;
785
786 mid = path->nodes[level];
787 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
788
789 if (level < BTRFS_MAX_LEVEL - 1)
790 parent = path->nodes[level + 1];
791 pslot = path->slots[level + 1];
792
793 if (!parent)
794 return 1;
795
796 left = read_node_slot(root, parent, pslot - 1);
797
798 /* first, try to make some room in the middle buffer */
799 if (left) {
800 u32 left_nr;
801 left_nr = btrfs_header_nritems(left);
802 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
803 wret = 1;
804 } else {
805 ret = btrfs_cow_block(trans, root, left, parent,
806 pslot - 1, &left);
807 if (ret)
808 wret = 1;
809 else {
810 wret = push_node_left(trans, root,
811 left, mid);
812 }
813 }
814 if (wret < 0)
815 ret = wret;
816 if (wret == 0) {
817 struct btrfs_disk_key disk_key;
818 orig_slot += left_nr;
819 btrfs_node_key(mid, &disk_key, 0);
820 btrfs_set_node_key(parent, &disk_key, pslot);
821 btrfs_mark_buffer_dirty(parent);
822 if (btrfs_header_nritems(left) > orig_slot) {
823 path->nodes[level] = left;
824 path->slots[level + 1] -= 1;
825 path->slots[level] = orig_slot;
826 free_extent_buffer(mid);
827 } else {
828 orig_slot -=
829 btrfs_header_nritems(left);
830 path->slots[level] = orig_slot;
831 free_extent_buffer(left);
832 }
833 check_node(root, path, level);
834 return 0;
835 }
836 free_extent_buffer(left);
837 }
838 right= read_node_slot(root, parent, pslot + 1);
839
840 /*
841 * then try to empty the right most buffer into the middle
842 */
843 if (right) {
844 u32 right_nr;
845 right_nr = btrfs_header_nritems(right);
846 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
847 wret = 1;
848 } else {
849 ret = btrfs_cow_block(trans, root, right,
850 parent, pslot + 1,
851 &right);
852 if (ret)
853 wret = 1;
854 else {
855 wret = balance_node_right(trans, root,
856 right, mid);
857 }
858 }
859 if (wret < 0)
860 ret = wret;
861 if (wret == 0) {
862 struct btrfs_disk_key disk_key;
863
864 btrfs_node_key(right, &disk_key, 0);
865 btrfs_set_node_key(parent, &disk_key, pslot + 1);
866 btrfs_mark_buffer_dirty(parent);
867
868 if (btrfs_header_nritems(mid) <= orig_slot) {
869 path->nodes[level] = right;
870 path->slots[level + 1] += 1;
871 path->slots[level] = orig_slot -
872 btrfs_header_nritems(mid);
873 free_extent_buffer(mid);
874 } else {
875 free_extent_buffer(right);
876 }
877 check_node(root, path, level);
878 return 0;
879 }
880 free_extent_buffer(right);
881 }
882 check_node(root, path, level);
883 return 1;
884 }
885
886 /*
887 * readahead one full node of leaves
888 */
889 static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
890 int level, int slot)
891 {
892 struct extent_buffer *node;
893 int i;
894 u32 nritems;
895 u64 blocknr;
896 u64 search;
897 u64 cluster_start;
898 int ret;
899 int nread = 0;
900 int direction = path->reada;
901 struct radix_tree_root found;
902 unsigned long gang[8];
903 struct extent_buffer *eb;
904
905 if (level == 0)
906 return;
907
908 if (!path->nodes[level])
909 return;
910
911 node = path->nodes[level];
912 search = btrfs_node_blockptr(node, slot);
913 eb = btrfs_find_tree_block(root, search);
914 if (eb) {
915 free_extent_buffer(eb);
916 return;
917 }
918
919 init_bit_radix(&found);
920 nritems = btrfs_header_nritems(node);
921 for (i = slot; i < nritems; i++) {
922 blocknr = btrfs_node_blockptr(node, i);
923 set_radix_bit(&found, blocknr);
924 }
925 if (direction > 0) {
926 cluster_start = search - 4;
927 if (cluster_start > search)
928 cluster_start = 0;
929 } else
930 cluster_start = search + 4;
931 while(1) {
932 ret = find_first_radix_bit(&found, gang, 0, ARRAY_SIZE(gang));
933 if (!ret)
934 break;
935 for (i = 0; i < ret; i++) {
936 blocknr = gang[i];
937 clear_radix_bit(&found, blocknr);
938 if (path->reada == 1 && nread > 16)
939 continue;
940 if (close_blocks(cluster_start, blocknr)) {
941 readahead_tree_block(root, blocknr);
942 nread++;
943 cluster_start = blocknr;
944 }
945 }
946 }
947 }
948 /*
949 * look for key in the tree. path is filled in with nodes along the way
950 * if key is found, we return zero and you can find the item in the leaf
951 * level of the path (level 0)
952 *
953 * If the key isn't found, the path points to the slot where it should
954 * be inserted, and 1 is returned. If there are other errors during the
955 * search a negative error number is returned.
956 *
957 * if ins_len > 0, nodes and leaves will be split as we walk down the
958 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
959 * possible)
960 */
961 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
962 *root, struct btrfs_key *key, struct btrfs_path *p, int
963 ins_len, int cow)
964 {
965 struct extent_buffer *b;
966 u64 blocknr;
967 int slot;
968 int ret;
969 int level;
970 int should_reada = p->reada;
971 u8 lowest_level = 0;
972
973 lowest_level = p->lowest_level;
974 WARN_ON(lowest_level && ins_len);
975 WARN_ON(p->nodes[0] != NULL);
976 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
977 again:
978 b = root->node;
979 extent_buffer_get(b);
980 while (b) {
981 level = btrfs_header_level(b);
982 if (cow) {
983 int wret;
984 wret = btrfs_cow_block(trans, root, b,
985 p->nodes[level + 1],
986 p->slots[level + 1],
987 &b);
988 if (wret) {
989 free_extent_buffer(b);
990 return wret;
991 }
992 }
993 BUG_ON(!cow && ins_len);
994 if (level != btrfs_header_level(b))
995 WARN_ON(1);
996 level = btrfs_header_level(b);
997 p->nodes[level] = b;
998 ret = check_block(root, p, level);
999 if (ret)
1000 return -1;
1001 ret = bin_search(b, key, level, &slot);
1002 if (level != 0) {
1003 if (ret && slot > 0)
1004 slot -= 1;
1005 p->slots[level] = slot;
1006 if (ins_len > 0 && btrfs_header_nritems(b) >=
1007 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1008 int sret = split_node(trans, root, p, level);
1009 BUG_ON(sret > 0);
1010 if (sret)
1011 return sret;
1012 b = p->nodes[level];
1013 slot = p->slots[level];
1014 } else if (ins_len < 0) {
1015 int sret = balance_level(trans, root, p,
1016 level);
1017 if (sret)
1018 return sret;
1019 b = p->nodes[level];
1020 if (!b) {
1021 btrfs_release_path(NULL, p);
1022 goto again;
1023 }
1024 slot = p->slots[level];
1025 BUG_ON(btrfs_header_nritems(b) == 1);
1026 }
1027 /* this is only true while dropping a snapshot */
1028 if (level == lowest_level)
1029 break;
1030 blocknr = btrfs_node_blockptr(b, slot);
1031 if (should_reada)
1032 reada_for_search(root, p, level, slot);
1033 b = read_tree_block(root, btrfs_node_blockptr(b, slot));
1034 } else {
1035 p->slots[level] = slot;
1036 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1037 sizeof(struct btrfs_item) + ins_len) {
1038 int sret = split_leaf(trans, root, key,
1039 p, ins_len);
1040 BUG_ON(sret > 0);
1041 if (sret)
1042 return sret;
1043 }
1044 return ret;
1045 }
1046 }
1047 return 1;
1048 }
1049
1050 /*
1051 * adjust the pointers going up the tree, starting at level
1052 * making sure the right key of each node is points to 'key'.
1053 * This is used after shifting pointers to the left, so it stops
1054 * fixing up pointers when a given leaf/node is not in slot 0 of the
1055 * higher levels
1056 *
1057 * If this fails to write a tree block, it returns -1, but continues
1058 * fixing up the blocks in ram so the tree is consistent.
1059 */
1060 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1061 struct btrfs_root *root, struct btrfs_path *path,
1062 struct btrfs_disk_key *key, int level)
1063 {
1064 int i;
1065 int ret = 0;
1066 struct extent_buffer *t;
1067
1068 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1069 int tslot = path->slots[i];
1070 if (!path->nodes[i])
1071 break;
1072 t = path->nodes[i];
1073 btrfs_set_node_key(t, key, tslot);
1074 btrfs_mark_buffer_dirty(path->nodes[i]);
1075 if (tslot != 0)
1076 break;
1077 }
1078 return ret;
1079 }
1080
1081 /*
1082 * try to push data from one node into the next node left in the
1083 * tree.
1084 *
1085 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1086 * error, and > 0 if there was no room in the left hand block.
1087 */
1088 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
1089 *root, struct extent_buffer *dst,
1090 struct extent_buffer *src)
1091 {
1092 int push_items = 0;
1093 int src_nritems;
1094 int dst_nritems;
1095 int ret = 0;
1096
1097 src_nritems = btrfs_header_nritems(src);
1098 dst_nritems = btrfs_header_nritems(dst);
1099 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1100
1101 if (push_items <= 0) {
1102 return 1;
1103 }
1104
1105 if (src_nritems < push_items)
1106 push_items = src_nritems;
1107
1108 copy_extent_buffer(dst, src,
1109 btrfs_node_key_ptr_offset(dst_nritems),
1110 btrfs_node_key_ptr_offset(0),
1111 push_items * sizeof(struct btrfs_key_ptr));
1112
1113 if (push_items < src_nritems) {
1114 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1115 btrfs_node_key_ptr_offset(push_items),
1116 (src_nritems - push_items) *
1117 sizeof(struct btrfs_key_ptr));
1118 }
1119 btrfs_set_header_nritems(src, src_nritems - push_items);
1120 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1121 btrfs_mark_buffer_dirty(src);
1122 btrfs_mark_buffer_dirty(dst);
1123 return ret;
1124 }
1125
1126 /*
1127 * try to push data from one node into the next node right in the
1128 * tree.
1129 *
1130 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1131 * error, and > 0 if there was no room in the right hand block.
1132 *
1133 * this will only push up to 1/2 the contents of the left node over
1134 */
1135 static int balance_node_right(struct btrfs_trans_handle *trans,
1136 struct btrfs_root *root,
1137 struct extent_buffer *dst,
1138 struct extent_buffer *src)
1139 {
1140 int push_items = 0;
1141 int max_push;
1142 int src_nritems;
1143 int dst_nritems;
1144 int ret = 0;
1145
1146 src_nritems = btrfs_header_nritems(src);
1147 dst_nritems = btrfs_header_nritems(dst);
1148 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1149 if (push_items <= 0)
1150 return 1;
1151
1152 max_push = src_nritems / 2 + 1;
1153 /* don't try to empty the node */
1154 if (max_push >= src_nritems)
1155 return 1;
1156
1157 if (max_push < push_items)
1158 push_items = max_push;
1159
1160 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1161 btrfs_node_key_ptr_offset(0),
1162 (dst_nritems) *
1163 sizeof(struct btrfs_key_ptr));
1164
1165 copy_extent_buffer(dst, src,
1166 btrfs_node_key_ptr_offset(0),
1167 btrfs_node_key_ptr_offset(src_nritems - push_items),
1168 push_items * sizeof(struct btrfs_key_ptr));
1169
1170 btrfs_set_header_nritems(src, src_nritems - push_items);
1171 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1172
1173 btrfs_mark_buffer_dirty(src);
1174 btrfs_mark_buffer_dirty(dst);
1175 return ret;
1176 }
1177
1178 /*
1179 * helper function to insert a new root level in the tree.
1180 * A new node is allocated, and a single item is inserted to
1181 * point to the existing root
1182 *
1183 * returns zero on success or < 0 on failure.
1184 */
1185 static int insert_new_root(struct btrfs_trans_handle *trans,
1186 struct btrfs_root *root,
1187 struct btrfs_path *path, int level)
1188 {
1189 struct extent_buffer *lower;
1190 struct extent_buffer *c;
1191 struct btrfs_disk_key lower_key;
1192
1193 BUG_ON(path->nodes[level]);
1194 BUG_ON(path->nodes[level-1] != root->node);
1195
1196 c = btrfs_alloc_free_block(trans, root,
1197 extent_buffer_blocknr(root->node), 0);
1198 if (IS_ERR(c))
1199 return PTR_ERR(c);
1200 memset_extent_buffer(c, 0, 0, root->nodesize);
1201 btrfs_set_header_nritems(c, 1);
1202 btrfs_set_header_level(c, level);
1203 btrfs_set_header_blocknr(c, extent_buffer_blocknr(c));
1204 btrfs_set_header_generation(c, trans->transid);
1205 btrfs_set_header_owner(c, root->root_key.objectid);
1206 lower = path->nodes[level-1];
1207
1208 write_extent_buffer(c, root->fs_info->fsid,
1209 (unsigned long)btrfs_header_fsid(c),
1210 BTRFS_FSID_SIZE);
1211 if (level == 1)
1212 btrfs_item_key(lower, &lower_key, 0);
1213 else
1214 btrfs_node_key(lower, &lower_key, 0);
1215 btrfs_set_node_key(c, &lower_key, 0);
1216 btrfs_set_node_blockptr(c, 0, extent_buffer_blocknr(lower));
1217
1218 btrfs_mark_buffer_dirty(c);
1219
1220 /* the super has an extra ref to root->node */
1221 free_extent_buffer(root->node);
1222 root->node = c;
1223 extent_buffer_get(c);
1224 path->nodes[level] = c;
1225 path->slots[level] = 0;
1226 return 0;
1227 }
1228
1229 /*
1230 * worker function to insert a single pointer in a node.
1231 * the node should have enough room for the pointer already
1232 *
1233 * slot and level indicate where you want the key to go, and
1234 * blocknr is the block the key points to.
1235 *
1236 * returns zero on success and < 0 on any error
1237 */
1238 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1239 *root, struct btrfs_path *path, struct btrfs_disk_key
1240 *key, u64 blocknr, int slot, int level)
1241 {
1242 struct extent_buffer *lower;
1243 int nritems;
1244
1245 BUG_ON(!path->nodes[level]);
1246 lower = path->nodes[level];
1247 nritems = btrfs_header_nritems(lower);
1248 if (slot > nritems)
1249 BUG();
1250 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1251 BUG();
1252 if (slot != nritems) {
1253 memmove_extent_buffer(lower,
1254 btrfs_node_key_ptr_offset(slot + 1),
1255 btrfs_node_key_ptr_offset(slot),
1256 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1257 }
1258 btrfs_set_node_key(lower, key, slot);
1259 btrfs_set_node_blockptr(lower, slot, blocknr);
1260 btrfs_set_header_nritems(lower, nritems + 1);
1261 btrfs_mark_buffer_dirty(lower);
1262 check_node(root, path, level);
1263 return 0;
1264 }
1265
1266 /*
1267 * split the node at the specified level in path in two.
1268 * The path is corrected to point to the appropriate node after the split
1269 *
1270 * Before splitting this tries to make some room in the node by pushing
1271 * left and right, if either one works, it returns right away.
1272 *
1273 * returns 0 on success and < 0 on failure
1274 */
1275 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1276 *root, struct btrfs_path *path, int level)
1277 {
1278 struct extent_buffer *c;
1279 struct extent_buffer *split;
1280 struct btrfs_disk_key disk_key;
1281 int mid;
1282 int ret;
1283 int wret;
1284 u32 c_nritems;
1285
1286 c = path->nodes[level];
1287 if (c == root->node) {
1288 /* trying to split the root, lets make a new one */
1289 ret = insert_new_root(trans, root, path, level + 1);
1290 if (ret)
1291 return ret;
1292 } else {
1293 ret = push_nodes_for_insert(trans, root, path, level);
1294 c = path->nodes[level];
1295 if (!ret && btrfs_header_nritems(c) <
1296 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1297 return 0;
1298 if (ret < 0)
1299 return ret;
1300 }
1301
1302 c_nritems = btrfs_header_nritems(c);
1303 split = btrfs_alloc_free_block(trans, root,
1304 extent_buffer_blocknr(c), 0);
1305 if (IS_ERR(split))
1306 return PTR_ERR(split);
1307
1308 btrfs_set_header_flags(split, btrfs_header_flags(c));
1309 btrfs_set_header_level(split, btrfs_header_level(c));
1310 btrfs_set_header_blocknr(split, extent_buffer_blocknr(split));
1311 btrfs_set_header_generation(split, trans->transid);
1312 btrfs_set_header_owner(split, root->root_key.objectid);
1313 write_extent_buffer(split, root->fs_info->fsid,
1314 (unsigned long)btrfs_header_fsid(split),
1315 BTRFS_FSID_SIZE);
1316
1317 mid = (c_nritems + 1) / 2;
1318
1319 copy_extent_buffer(split, c,
1320 btrfs_node_key_ptr_offset(0),
1321 btrfs_node_key_ptr_offset(mid),
1322 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1323 btrfs_set_header_nritems(split, c_nritems - mid);
1324 btrfs_set_header_nritems(c, mid);
1325 ret = 0;
1326
1327 btrfs_mark_buffer_dirty(c);
1328 btrfs_mark_buffer_dirty(split);
1329
1330 btrfs_node_key(split, &disk_key, 0);
1331 wret = insert_ptr(trans, root, path, &disk_key,
1332 extent_buffer_blocknr(split),
1333 path->slots[level + 1] + 1,
1334 level + 1);
1335 if (wret)
1336 ret = wret;
1337
1338 if (path->slots[level] >= mid) {
1339 path->slots[level] -= mid;
1340 free_extent_buffer(c);
1341 path->nodes[level] = split;
1342 path->slots[level + 1] += 1;
1343 } else {
1344 free_extent_buffer(split);
1345 }
1346 return ret;
1347 }
1348
1349 /*
1350 * how many bytes are required to store the items in a leaf. start
1351 * and nr indicate which items in the leaf to check. This totals up the
1352 * space used both by the item structs and the item data
1353 */
1354 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1355 {
1356 int data_len;
1357 int nritems = btrfs_header_nritems(l);
1358 int end = min(nritems, start + nr) - 1;
1359
1360 if (!nr)
1361 return 0;
1362 data_len = btrfs_item_end_nr(l, start);
1363 data_len = data_len - btrfs_item_offset_nr(l, end);
1364 data_len += sizeof(struct btrfs_item) * nr;
1365 WARN_ON(data_len < 0);
1366 return data_len;
1367 }
1368
1369 /*
1370 * The space between the end of the leaf items and
1371 * the start of the leaf data. IOW, how much room
1372 * the leaf has left for both items and data
1373 */
1374 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1375 {
1376 int nritems = btrfs_header_nritems(leaf);
1377 int ret;
1378 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1379 if (ret < 0) {
1380 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1381 ret, BTRFS_LEAF_DATA_SIZE(root),
1382 leaf_space_used(leaf, 0, nritems), nritems);
1383 }
1384 return ret;
1385 }
1386
1387 /*
1388 * push some data in the path leaf to the right, trying to free up at
1389 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1390 *
1391 * returns 1 if the push failed because the other node didn't have enough
1392 * room, 0 if everything worked out and < 0 if there were major errors.
1393 */
1394 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1395 *root, struct btrfs_path *path, int data_size)
1396 {
1397 struct extent_buffer *left = path->nodes[0];
1398 struct extent_buffer *right;
1399 struct extent_buffer *upper;
1400 struct btrfs_disk_key disk_key;
1401 int slot;
1402 int i;
1403 int free_space;
1404 int push_space = 0;
1405 int push_items = 0;
1406 struct btrfs_item *item;
1407 u32 left_nritems;
1408 u32 right_nritems;
1409 u32 data_end;
1410 int ret;
1411
1412 slot = path->slots[1];
1413 if (!path->nodes[1]) {
1414 return 1;
1415 }
1416 upper = path->nodes[1];
1417 if (slot >= btrfs_header_nritems(upper) - 1)
1418 return 1;
1419
1420 right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1));
1421 free_space = btrfs_leaf_free_space(root, right);
1422 if (free_space < data_size + sizeof(struct btrfs_item)) {
1423 free_extent_buffer(right);
1424 return 1;
1425 }
1426
1427 /* cow and double check */
1428 ret = btrfs_cow_block(trans, root, right, upper,
1429 slot + 1, &right);
1430 if (ret) {
1431 free_extent_buffer(right);
1432 return 1;
1433 }
1434 free_space = btrfs_leaf_free_space(root, right);
1435 if (free_space < data_size + sizeof(struct btrfs_item)) {
1436 free_extent_buffer(right);
1437 return 1;
1438 }
1439
1440 left_nritems = btrfs_header_nritems(left);
1441 if (left_nritems == 0) {
1442 free_extent_buffer(right);
1443 return 1;
1444 }
1445
1446 for (i = left_nritems - 1; i >= 1; i--) {
1447 item = btrfs_item_nr(left, i);
1448 if (path->slots[0] == i)
1449 push_space += data_size + sizeof(*item);
1450 if (btrfs_item_size(left, item) + sizeof(*item) + push_space >
1451 free_space)
1452 break;
1453 push_items++;
1454 push_space += btrfs_item_size(left, item) + sizeof(*item);
1455 }
1456
1457 if (push_items == 0) {
1458 free_extent_buffer(right);
1459 return 1;
1460 }
1461
1462 if (push_items == left_nritems)
1463 WARN_ON(1);
1464
1465 /* push left to right */
1466 right_nritems = btrfs_header_nritems(right);
1467 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1468 push_space -= leaf_data_end(root, left);
1469
1470 /* make room in the right data area */
1471 data_end = leaf_data_end(root, right);
1472 memmove_extent_buffer(right,
1473 btrfs_leaf_data(right) + data_end - push_space,
1474 btrfs_leaf_data(right) + data_end,
1475 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1476
1477 /* copy from the left data area */
1478 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1479 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1480 btrfs_leaf_data(left) + leaf_data_end(root, left),
1481 push_space);
1482
1483 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1484 btrfs_item_nr_offset(0),
1485 right_nritems * sizeof(struct btrfs_item));
1486
1487 /* copy the items from left to right */
1488 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1489 btrfs_item_nr_offset(left_nritems - push_items),
1490 push_items * sizeof(struct btrfs_item));
1491
1492 /* update the item pointers */
1493 right_nritems += push_items;
1494 btrfs_set_header_nritems(right, right_nritems);
1495 push_space = BTRFS_LEAF_DATA_SIZE(root);
1496 for (i = 0; i < right_nritems; i++) {
1497 item = btrfs_item_nr(right, i);
1498 btrfs_set_item_offset(right, item, push_space -
1499 btrfs_item_size(right, item));
1500 push_space = btrfs_item_offset(right, item);
1501 }
1502 left_nritems -= push_items;
1503 btrfs_set_header_nritems(left, left_nritems);
1504
1505 btrfs_mark_buffer_dirty(left);
1506 btrfs_mark_buffer_dirty(right);
1507
1508 btrfs_item_key(right, &disk_key, 0);
1509 btrfs_set_node_key(upper, &disk_key, slot + 1);
1510 btrfs_mark_buffer_dirty(upper);
1511
1512 /* then fixup the leaf pointer in the path */
1513 if (path->slots[0] >= left_nritems) {
1514 path->slots[0] -= left_nritems;
1515 free_extent_buffer(path->nodes[0]);
1516 path->nodes[0] = right;
1517 path->slots[1] += 1;
1518 } else {
1519 free_extent_buffer(right);
1520 }
1521 if (path->nodes[1])
1522 check_node(root, path, 1);
1523 return 0;
1524 }
1525 /*
1526 * push some data in the path leaf to the left, trying to free up at
1527 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1528 */
1529 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1530 *root, struct btrfs_path *path, int data_size)
1531 {
1532 struct btrfs_disk_key disk_key;
1533 struct extent_buffer *right = path->nodes[0];
1534 struct extent_buffer *left;
1535 int slot;
1536 int i;
1537 int free_space;
1538 int push_space = 0;
1539 int push_items = 0;
1540 struct btrfs_item *item;
1541 u32 old_left_nritems;
1542 u32 right_nritems;
1543 int ret = 0;
1544 int wret;
1545
1546 slot = path->slots[1];
1547 if (slot == 0)
1548 return 1;
1549 if (!path->nodes[1])
1550 return 1;
1551
1552 left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1553 slot - 1));
1554 free_space = btrfs_leaf_free_space(root, left);
1555 if (free_space < data_size + sizeof(struct btrfs_item)) {
1556 free_extent_buffer(left);
1557 return 1;
1558 }
1559
1560 /* cow and double check */
1561 ret = btrfs_cow_block(trans, root, left,
1562 path->nodes[1], slot - 1, &left);
1563 if (ret) {
1564 /* we hit -ENOSPC, but it isn't fatal here */
1565 free_extent_buffer(left);
1566 return 1;
1567 }
1568 free_space = btrfs_leaf_free_space(root, left);
1569 if (free_space < data_size + sizeof(struct btrfs_item)) {
1570 free_extent_buffer(left);
1571 return 1;
1572 }
1573
1574 right_nritems = btrfs_header_nritems(right);
1575 if (right_nritems == 0) {
1576 free_extent_buffer(left);
1577 return 1;
1578 }
1579
1580 for (i = 0; i < right_nritems - 1; i++) {
1581 item = btrfs_item_nr(right, i);
1582 if (path->slots[0] == i)
1583 push_space += data_size + sizeof(*item);
1584 if (btrfs_item_size(right, item) + sizeof(*item) + push_space >
1585 free_space)
1586 break;
1587 push_items++;
1588 push_space += btrfs_item_size(right, item) + sizeof(*item);
1589 }
1590 if (push_items == 0) {
1591 free_extent_buffer(left);
1592 return 1;
1593 }
1594 if (push_items == btrfs_header_nritems(right))
1595 WARN_ON(1);
1596
1597 /* push data from right to left */
1598 copy_extent_buffer(left, right,
1599 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1600 btrfs_item_nr_offset(0),
1601 push_items * sizeof(struct btrfs_item));
1602
1603 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1604 btrfs_item_offset_nr(right, push_items -1);
1605
1606 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1607 leaf_data_end(root, left) - push_space,
1608 btrfs_leaf_data(right) +
1609 btrfs_item_offset_nr(right, push_items - 1),
1610 push_space);
1611 old_left_nritems = btrfs_header_nritems(left);
1612 BUG_ON(old_left_nritems < 0);
1613
1614 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1615 u32 ioff;
1616 item = btrfs_item_nr(left, i);
1617 ioff = btrfs_item_offset(left, item);
1618 btrfs_set_item_offset(left, item,
1619 ioff - (BTRFS_LEAF_DATA_SIZE(root) -
1620 btrfs_item_offset_nr(left, old_left_nritems - 1)));
1621 }
1622 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1623
1624 /* fixup right node */
1625 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1626 leaf_data_end(root, right);
1627 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1628 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1629 btrfs_leaf_data(right) +
1630 leaf_data_end(root, right), push_space);
1631
1632 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1633 btrfs_item_nr_offset(push_items),
1634 (btrfs_header_nritems(right) - push_items) *
1635 sizeof(struct btrfs_item));
1636
1637 right_nritems = btrfs_header_nritems(right) - push_items;
1638 btrfs_set_header_nritems(right, right_nritems);
1639 push_space = BTRFS_LEAF_DATA_SIZE(root);
1640
1641 for (i = 0; i < right_nritems; i++) {
1642 item = btrfs_item_nr(right, i);
1643 btrfs_set_item_offset(right, item, push_space -
1644 btrfs_item_size(right, item));
1645 push_space = btrfs_item_offset(right, item);
1646 }
1647
1648 btrfs_mark_buffer_dirty(left);
1649 btrfs_mark_buffer_dirty(right);
1650
1651 btrfs_item_key(right, &disk_key, 0);
1652 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1653 if (wret)
1654 ret = wret;
1655
1656 /* then fixup the leaf pointer in the path */
1657 if (path->slots[0] < push_items) {
1658 path->slots[0] += old_left_nritems;
1659 free_extent_buffer(path->nodes[0]);
1660 path->nodes[0] = left;
1661 path->slots[1] -= 1;
1662 } else {
1663 free_extent_buffer(left);
1664 path->slots[0] -= push_items;
1665 }
1666 BUG_ON(path->slots[0] < 0);
1667 if (path->nodes[1])
1668 check_node(root, path, 1);
1669 return ret;
1670 }
1671
1672 /*
1673 * split the path's leaf in two, making sure there is at least data_size
1674 * available for the resulting leaf level of the path.
1675 *
1676 * returns 0 if all went well and < 0 on failure.
1677 */
1678 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1679 *root, struct btrfs_key *ins_key,
1680 struct btrfs_path *path, int data_size)
1681 {
1682 struct extent_buffer *l;
1683 u32 nritems;
1684 int mid;
1685 int slot;
1686 struct extent_buffer *right;
1687 int space_needed = data_size + sizeof(struct btrfs_item);
1688 int data_copy_size;
1689 int rt_data_off;
1690 int i;
1691 int ret = 0;
1692 int wret;
1693 int double_split = 0;
1694 struct btrfs_disk_key disk_key;
1695
1696 /* first try to make some room by pushing left and right */
1697 wret = push_leaf_left(trans, root, path, data_size);
1698 if (wret < 0)
1699 return wret;
1700 if (wret) {
1701 wret = push_leaf_right(trans, root, path, data_size);
1702 if (wret < 0)
1703 return wret;
1704 }
1705 l = path->nodes[0];
1706
1707 /* did the pushes work? */
1708 if (btrfs_leaf_free_space(root, l) >=
1709 sizeof(struct btrfs_item) + data_size)
1710 return 0;
1711
1712 if (!path->nodes[1]) {
1713 ret = insert_new_root(trans, root, path, 1);
1714 if (ret)
1715 return ret;
1716 }
1717 slot = path->slots[0];
1718 nritems = btrfs_header_nritems(l);
1719 mid = (nritems + 1)/ 2;
1720
1721 right = btrfs_alloc_free_block(trans, root,
1722 extent_buffer_blocknr(l), 0);
1723 if (IS_ERR(right))
1724 return PTR_ERR(right);
1725
1726 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1727 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1728 btrfs_set_header_generation(right, trans->transid);
1729 btrfs_set_header_owner(right, root->root_key.objectid);
1730 btrfs_set_header_level(right, 0);
1731 write_extent_buffer(right, root->fs_info->fsid,
1732 (unsigned long)btrfs_header_fsid(right),
1733 BTRFS_FSID_SIZE);
1734
1735 if (mid <= slot) {
1736 if (nritems == 1 ||
1737 leaf_space_used(l, mid, nritems - mid) + space_needed >
1738 BTRFS_LEAF_DATA_SIZE(root)) {
1739 if (slot >= nritems) {
1740 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1741 btrfs_set_header_nritems(right, 0);
1742 wret = insert_ptr(trans, root, path,
1743 &disk_key,
1744 extent_buffer_blocknr(right),
1745 path->slots[1] + 1, 1);
1746 if (wret)
1747 ret = wret;
1748 free_extent_buffer(path->nodes[0]);
1749 path->nodes[0] = right;
1750 path->slots[0] = 0;
1751 path->slots[1] += 1;
1752 return ret;
1753 }
1754 mid = slot;
1755 double_split = 1;
1756 }
1757 } else {
1758 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1759 BTRFS_LEAF_DATA_SIZE(root)) {
1760 if (slot == 0) {
1761 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1762 btrfs_set_header_nritems(right, 0);
1763 wret = insert_ptr(trans, root, path,
1764 &disk_key,
1765 extent_buffer_blocknr(right),
1766 path->slots[1], 1);
1767 if (wret)
1768 ret = wret;
1769 free_extent_buffer(path->nodes[0]);
1770 path->nodes[0] = right;
1771 path->slots[0] = 0;
1772 if (path->slots[1] == 0) {
1773 wret = fixup_low_keys(trans, root,
1774 path, &disk_key, 1);
1775 if (wret)
1776 ret = wret;
1777 }
1778 return ret;
1779 }
1780 mid = slot;
1781 double_split = 1;
1782 }
1783 }
1784 nritems = nritems - mid;
1785 btrfs_set_header_nritems(right, nritems);
1786 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
1787
1788 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
1789 btrfs_item_nr_offset(mid),
1790 nritems * sizeof(struct btrfs_item));
1791
1792 copy_extent_buffer(right, l,
1793 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1794 data_copy_size, btrfs_leaf_data(l) +
1795 leaf_data_end(root, l), data_copy_size);
1796
1797 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1798 btrfs_item_end_nr(l, mid);
1799
1800 for (i = 0; i < nritems; i++) {
1801 struct btrfs_item *item = btrfs_item_nr(right, i);
1802 u32 ioff = btrfs_item_offset(right, item);
1803 btrfs_set_item_offset(right, item, ioff + rt_data_off);
1804 }
1805
1806 btrfs_set_header_nritems(l, mid);
1807 ret = 0;
1808 btrfs_item_key(right, &disk_key, 0);
1809 wret = insert_ptr(trans, root, path, &disk_key,
1810 extent_buffer_blocknr(right), path->slots[1] + 1, 1);
1811 if (wret)
1812 ret = wret;
1813
1814 btrfs_mark_buffer_dirty(right);
1815 btrfs_mark_buffer_dirty(l);
1816 BUG_ON(path->slots[0] != slot);
1817
1818 if (mid <= slot) {
1819 free_extent_buffer(path->nodes[0]);
1820 path->nodes[0] = right;
1821 path->slots[0] -= mid;
1822 path->slots[1] += 1;
1823 } else
1824 free_extent_buffer(right);
1825
1826 BUG_ON(path->slots[0] < 0);
1827 check_node(root, path, 1);
1828 check_leaf(root, path, 0);
1829
1830 if (!double_split)
1831 return ret;
1832
1833 right = btrfs_alloc_free_block(trans, root,
1834 extent_buffer_blocknr(l), 0);
1835 if (IS_ERR(right))
1836 return PTR_ERR(right);
1837
1838 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1839 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1840 btrfs_set_header_generation(right, trans->transid);
1841 btrfs_set_header_owner(right, root->root_key.objectid);
1842 btrfs_set_header_level(right, 0);
1843 write_extent_buffer(right, root->fs_info->fsid,
1844 (unsigned long)btrfs_header_fsid(right),
1845 BTRFS_FSID_SIZE);
1846
1847 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1848 btrfs_set_header_nritems(right, 0);
1849 wret = insert_ptr(trans, root, path,
1850 &disk_key,
1851 extent_buffer_blocknr(right),
1852 path->slots[1], 1);
1853 if (wret)
1854 ret = wret;
1855 if (path->slots[1] == 0) {
1856 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1857 if (wret)
1858 ret = wret;
1859 }
1860 free_extent_buffer(path->nodes[0]);
1861 path->nodes[0] = right;
1862 path->slots[0] = 0;
1863 check_node(root, path, 1);
1864 check_leaf(root, path, 0);
1865 return ret;
1866 }
1867
1868 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1869 struct btrfs_root *root,
1870 struct btrfs_path *path,
1871 u32 new_size)
1872 {
1873 int ret = 0;
1874 int slot;
1875 int slot_orig;
1876 struct extent_buffer *leaf;
1877 struct btrfs_item *item;
1878 u32 nritems;
1879 unsigned int data_end;
1880 unsigned int old_data_start;
1881 unsigned int old_size;
1882 unsigned int size_diff;
1883 int i;
1884
1885 slot_orig = path->slots[0];
1886 leaf = path->nodes[0];
1887
1888 nritems = btrfs_header_nritems(leaf);
1889 data_end = leaf_data_end(root, leaf);
1890
1891 slot = path->slots[0];
1892 old_data_start = btrfs_item_offset_nr(leaf, slot);
1893 old_size = btrfs_item_size_nr(leaf, slot);
1894 BUG_ON(old_size <= new_size);
1895 size_diff = old_size - new_size;
1896
1897 BUG_ON(slot < 0);
1898 BUG_ON(slot >= nritems);
1899
1900 /*
1901 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1902 */
1903 /* first correct the data pointers */
1904 for (i = slot; i < nritems; i++) {
1905 u32 ioff;
1906 item = btrfs_item_nr(leaf, i);
1907 ioff = btrfs_item_offset(leaf, item);
1908 btrfs_set_item_offset(leaf, item, ioff + size_diff);
1909 }
1910 /* shift the data */
1911 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1912 data_end + size_diff, btrfs_leaf_data(leaf) +
1913 data_end, old_data_start + new_size - data_end);
1914
1915 item = btrfs_item_nr(leaf, slot);
1916 btrfs_set_item_size(leaf, item, new_size);
1917 btrfs_mark_buffer_dirty(leaf);
1918
1919 ret = 0;
1920 if (btrfs_leaf_free_space(root, leaf) < 0) {
1921 btrfs_print_leaf(root, leaf);
1922 BUG();
1923 }
1924 check_leaf(root, path, 0);
1925 return ret;
1926 }
1927
1928 int btrfs_extend_item(struct btrfs_trans_handle *trans,
1929 struct btrfs_root *root, struct btrfs_path *path,
1930 u32 data_size)
1931 {
1932 int ret = 0;
1933 int slot;
1934 int slot_orig;
1935 struct extent_buffer *leaf;
1936 struct btrfs_item *item;
1937 u32 nritems;
1938 unsigned int data_end;
1939 unsigned int old_data;
1940 unsigned int old_size;
1941 int i;
1942
1943 slot_orig = path->slots[0];
1944 leaf = path->nodes[0];
1945
1946 nritems = btrfs_header_nritems(leaf);
1947 data_end = leaf_data_end(root, leaf);
1948
1949 if (btrfs_leaf_free_space(root, leaf) < data_size) {
1950 btrfs_print_leaf(root, leaf);
1951 BUG();
1952 }
1953 slot = path->slots[0];
1954 old_data = btrfs_item_end_nr(leaf, slot);
1955
1956 BUG_ON(slot < 0);
1957 BUG_ON(slot >= nritems);
1958
1959 /*
1960 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1961 */
1962 /* first correct the data pointers */
1963 for (i = slot; i < nritems; i++) {
1964 u32 ioff;
1965 item = btrfs_item_nr(leaf, i);
1966 ioff = btrfs_item_offset(leaf, item);
1967 btrfs_set_item_offset(leaf, item, ioff - data_size);
1968 }
1969
1970 /* shift the data */
1971 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1972 data_end - data_size, btrfs_leaf_data(leaf) +
1973 data_end, old_data - data_end);
1974
1975 data_end = old_data;
1976 old_size = btrfs_item_size_nr(leaf, slot);
1977 item = btrfs_item_nr(leaf, slot);
1978 btrfs_set_item_size(leaf, item, old_size + data_size);
1979 btrfs_mark_buffer_dirty(leaf);
1980
1981 ret = 0;
1982 if (btrfs_leaf_free_space(root, leaf) < 0) {
1983 btrfs_print_leaf(root, leaf);
1984 BUG();
1985 }
1986 check_leaf(root, path, 0);
1987 return ret;
1988 }
1989
1990 /*
1991 * Given a key and some data, insert an item into the tree.
1992 * This does all the path init required, making room in the tree if needed.
1993 */
1994 int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
1995 struct btrfs_root *root,
1996 struct btrfs_path *path,
1997 struct btrfs_key *cpu_key, u32 data_size)
1998 {
1999 struct extent_buffer *leaf;
2000 struct btrfs_item *item;
2001 int ret = 0;
2002 int slot;
2003 int slot_orig;
2004 u32 nritems;
2005 unsigned int data_end;
2006 struct btrfs_disk_key disk_key;
2007
2008 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2009
2010 /* create a root if there isn't one */
2011 if (!root->node)
2012 BUG();
2013
2014 ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
2015 if (ret == 0) {
2016 return -EEXIST;
2017 }
2018 if (ret < 0)
2019 goto out;
2020
2021 slot_orig = path->slots[0];
2022 leaf = path->nodes[0];
2023
2024 nritems = btrfs_header_nritems(leaf);
2025 data_end = leaf_data_end(root, leaf);
2026
2027 if (btrfs_leaf_free_space(root, leaf) <
2028 sizeof(struct btrfs_item) + data_size) {
2029 BUG();
2030 }
2031
2032 slot = path->slots[0];
2033 BUG_ON(slot < 0);
2034
2035 if (slot != nritems) {
2036 int i;
2037 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2038
2039 if (old_data < data_end) {
2040 btrfs_print_leaf(root, leaf);
2041 printk("slot %d old_data %d data_end %d\n",
2042 slot, old_data, data_end);
2043 BUG_ON(1);
2044 }
2045 /*
2046 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2047 */
2048 /* first correct the data pointers */
2049 for (i = slot; i < nritems; i++) {
2050 u32 ioff;
2051 item = btrfs_item_nr(leaf, i);
2052 ioff = btrfs_item_offset(leaf, item);
2053 btrfs_set_item_offset(leaf, item, ioff - data_size);
2054 }
2055
2056 /* shift the items */
2057 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2058 btrfs_item_nr_offset(slot),
2059 (nritems - slot) * sizeof(struct btrfs_item));
2060
2061 /* shift the data */
2062 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2063 data_end - data_size, btrfs_leaf_data(leaf) +
2064 data_end, old_data - data_end);
2065 data_end = old_data;
2066 }
2067
2068 /* setup the item for the new data */
2069 btrfs_set_item_key(leaf, &disk_key, slot);
2070 item = btrfs_item_nr(leaf, slot);
2071 btrfs_set_item_offset(leaf, item, data_end - data_size);
2072 btrfs_set_item_size(leaf, item, data_size);
2073 btrfs_set_header_nritems(leaf, nritems + 1);
2074 btrfs_mark_buffer_dirty(leaf);
2075
2076 ret = 0;
2077 if (slot == 0)
2078 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2079
2080 if (btrfs_leaf_free_space(root, leaf) < 0) {
2081 btrfs_print_leaf(root, leaf);
2082 BUG();
2083 }
2084 check_leaf(root, path, 0);
2085 out:
2086 return ret;
2087 }
2088
2089 /*
2090 * Given a key and some data, insert an item into the tree.
2091 * This does all the path init required, making room in the tree if needed.
2092 */
2093 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2094 *root, struct btrfs_key *cpu_key, void *data, u32
2095 data_size)
2096 {
2097 int ret = 0;
2098 struct btrfs_path *path;
2099 struct extent_buffer *leaf;
2100 unsigned long ptr;
2101
2102 path = btrfs_alloc_path();
2103 BUG_ON(!path);
2104 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2105 if (!ret) {
2106 leaf = path->nodes[0];
2107 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2108 write_extent_buffer(leaf, data, ptr, data_size);
2109 btrfs_mark_buffer_dirty(leaf);
2110 }
2111 btrfs_free_path(path);
2112 return ret;
2113 }
2114
2115 /*
2116 * delete the pointer from a given node.
2117 *
2118 * If the delete empties a node, the node is removed from the tree,
2119 * continuing all the way the root if required. The root is converted into
2120 * a leaf if all the nodes are emptied.
2121 */
2122 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2123 struct btrfs_path *path, int level, int slot)
2124 {
2125 struct extent_buffer *parent = path->nodes[level];
2126 u32 nritems;
2127 int ret = 0;
2128 int wret;
2129
2130 nritems = btrfs_header_nritems(parent);
2131 if (slot != nritems -1) {
2132 memmove_extent_buffer(parent,
2133 btrfs_node_key_ptr_offset(slot),
2134 btrfs_node_key_ptr_offset(slot + 1),
2135 sizeof(struct btrfs_key_ptr) *
2136 (nritems - slot - 1));
2137 }
2138 nritems--;
2139 btrfs_set_header_nritems(parent, nritems);
2140 if (nritems == 0 && parent == root->node) {
2141 BUG_ON(btrfs_header_level(root->node) != 1);
2142 /* just turn the root into a leaf and break */
2143 btrfs_set_header_level(root->node, 0);
2144 } else if (slot == 0) {
2145 struct btrfs_disk_key disk_key;
2146
2147 btrfs_node_key(parent, &disk_key, 0);
2148 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2149 if (wret)
2150 ret = wret;
2151 }
2152 btrfs_mark_buffer_dirty(parent);
2153 return ret;
2154 }
2155
2156 /*
2157 * delete the item at the leaf level in path. If that empties
2158 * the leaf, remove it from the tree
2159 */
2160 int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2161 struct btrfs_path *path)
2162 {
2163 int slot;
2164 struct extent_buffer *leaf;
2165 struct btrfs_item *item;
2166 int doff;
2167 int dsize;
2168 int ret = 0;
2169 int wret;
2170 u32 nritems;
2171
2172 leaf = path->nodes[0];
2173 slot = path->slots[0];
2174 doff = btrfs_item_offset_nr(leaf, slot);
2175 dsize = btrfs_item_size_nr(leaf, slot);
2176 nritems = btrfs_header_nritems(leaf);
2177
2178 if (slot != nritems - 1) {
2179 int i;
2180 int data_end = leaf_data_end(root, leaf);
2181
2182 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2183 data_end + dsize,
2184 btrfs_leaf_data(leaf) + data_end,
2185 doff - data_end);
2186
2187 for (i = slot + 1; i < nritems; i++) {
2188 u32 ioff;
2189 item = btrfs_item_nr(leaf, i);
2190 ioff = btrfs_item_offset(leaf, item);
2191 btrfs_set_item_offset(leaf, item, ioff + dsize);
2192 }
2193 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2194 btrfs_item_nr_offset(slot + 1),
2195 sizeof(struct btrfs_item) *
2196 (nritems - slot - 1));
2197 }
2198 btrfs_set_header_nritems(leaf, nritems - 1);
2199 nritems--;
2200
2201 /* delete the leaf if we've emptied it */
2202 if (nritems == 0) {
2203 if (leaf == root->node) {
2204 btrfs_set_header_level(leaf, 0);
2205 } else {
2206 clean_tree_block(trans, root, leaf);
2207 wait_on_tree_block_writeback(root, leaf);
2208 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2209 if (wret)
2210 ret = wret;
2211 wret = btrfs_free_extent(trans, root,
2212 extent_buffer_blocknr(leaf),
2213 1, 1);
2214 if (wret)
2215 ret = wret;
2216 }
2217 } else {
2218 int used = leaf_space_used(leaf, 0, nritems);
2219 if (slot == 0) {
2220 struct btrfs_disk_key disk_key;
2221
2222 btrfs_item_key(leaf, &disk_key, 0);
2223 wret = fixup_low_keys(trans, root, path,
2224 &disk_key, 1);
2225 if (wret)
2226 ret = wret;
2227 }
2228
2229 /* delete the leaf if it is mostly empty */
2230 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
2231 /* push_leaf_left fixes the path.
2232 * make sure the path still points to our leaf
2233 * for possible call to del_ptr below
2234 */
2235 slot = path->slots[1];
2236 extent_buffer_get(leaf);
2237
2238 wret = push_leaf_left(trans, root, path, 1);
2239 if (wret < 0 && wret != -ENOSPC)
2240 ret = wret;
2241
2242 if (path->nodes[0] == leaf &&
2243 btrfs_header_nritems(leaf)) {
2244 wret = push_leaf_right(trans, root, path, 1);
2245 if (wret < 0 && wret != -ENOSPC)
2246 ret = wret;
2247 }
2248
2249 if (btrfs_header_nritems(leaf) == 0) {
2250 u64 blocknr = extent_buffer_blocknr(leaf);
2251
2252 clean_tree_block(trans, root, leaf);
2253 wait_on_tree_block_writeback(root, leaf);
2254
2255 wret = del_ptr(trans, root, path, 1, slot);
2256 if (wret)
2257 ret = wret;
2258
2259 free_extent_buffer(leaf);
2260 wret = btrfs_free_extent(trans, root, blocknr,
2261 1, 1);
2262 if (wret)
2263 ret = wret;
2264 } else {
2265 btrfs_mark_buffer_dirty(leaf);
2266 free_extent_buffer(leaf);
2267 }
2268 } else {
2269 btrfs_mark_buffer_dirty(leaf);
2270 }
2271 }
2272 return ret;
2273 }
2274
2275 /*
2276 * walk up the tree as far as required to find the next leaf.
2277 * returns 0 if it found something or 1 if there are no greater leaves.
2278 * returns < 0 on io errors.
2279 */
2280 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2281 {
2282 int slot;
2283 int level = 1;
2284 u64 blocknr;
2285 struct extent_buffer *c;
2286 struct extent_buffer *next = NULL;
2287
2288 while(level < BTRFS_MAX_LEVEL) {
2289 if (!path->nodes[level])
2290 return 1;
2291
2292 slot = path->slots[level] + 1;
2293 c = path->nodes[level];
2294 if (slot >= btrfs_header_nritems(c)) {
2295 level++;
2296 continue;
2297 }
2298
2299 blocknr = btrfs_node_blockptr(c, slot);
2300 if (next)
2301 free_extent_buffer(next);
2302
2303 if (path->reada)
2304 reada_for_search(root, path, level, slot);
2305
2306 next = read_tree_block(root, blocknr);
2307 break;
2308 }
2309 path->slots[level] = slot;
2310 while(1) {
2311 level--;
2312 c = path->nodes[level];
2313 free_extent_buffer(c);
2314 path->nodes[level] = next;
2315 path->slots[level] = 0;
2316 if (!level)
2317 break;
2318 if (path->reada)
2319 reada_for_search(root, path, level, 0);
2320 next = read_tree_block(root, btrfs_node_blockptr(next, 0));
2321 }
2322 return 0;
2323 }
Linux kernel - Deliverables
This page took 0.097272 seconds and 6 git commands to generate.