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