1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include "xfs.h"
19#include "xfs_fs.h"
20#include "xfs_types.h"
21#include "xfs_bit.h"
22#include "xfs_log.h"
23#include "xfs_trans.h"
24#include "xfs_sb.h"
25#include "xfs_ag.h"
26#include "xfs_mount.h"
27#include "xfs_bmap_btree.h"
28#include "xfs_alloc_btree.h"
29#include "xfs_ialloc_btree.h"
30#include "xfs_dinode.h"
31#include "xfs_inode.h"
32#include "xfs_inode_item.h"
33#include "xfs_buf_item.h"
34#include "xfs_btree.h"
35#include "xfs_error.h"
36#include "xfs_trace.h"
37#include "xfs_cksum.h"
38
39
40
41
42kmem_zone_t *xfs_btree_cur_zone;
43
44
45
46
47static const __uint32_t xfs_magics[2][XFS_BTNUM_MAX] = {
48 { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC },
49 { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC,
50 XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC }
51};
52#define xfs_btree_magic(cur) \
53 xfs_magics[!!((cur)->bc_flags & XFS_BTREE_CRC_BLOCKS)][cur->bc_btnum]
54
55
56STATIC int
57xfs_btree_check_lblock(
58 struct xfs_btree_cur *cur,
59 struct xfs_btree_block *block,
60 int level,
61 struct xfs_buf *bp)
62{
63 int lblock_ok = 1;
64 struct xfs_mount *mp;
65
66 mp = cur->bc_mp;
67
68 if (xfs_sb_version_hascrc(&mp->m_sb)) {
69 lblock_ok = lblock_ok &&
70 uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_uuid) &&
71 block->bb_u.l.bb_blkno == cpu_to_be64(
72 bp ? bp->b_bn : XFS_BUF_DADDR_NULL);
73 }
74
75 lblock_ok = lblock_ok &&
76 be32_to_cpu(block->bb_magic) == xfs_btree_magic(cur) &&
77 be16_to_cpu(block->bb_level) == level &&
78 be16_to_cpu(block->bb_numrecs) <=
79 cur->bc_ops->get_maxrecs(cur, level) &&
80 block->bb_u.l.bb_leftsib &&
81 (block->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO) ||
82 XFS_FSB_SANITY_CHECK(mp,
83 be64_to_cpu(block->bb_u.l.bb_leftsib))) &&
84 block->bb_u.l.bb_rightsib &&
85 (block->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO) ||
86 XFS_FSB_SANITY_CHECK(mp,
87 be64_to_cpu(block->bb_u.l.bb_rightsib)));
88
89 if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp,
90 XFS_ERRTAG_BTREE_CHECK_LBLOCK,
91 XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
92 if (bp)
93 trace_xfs_btree_corrupt(bp, _RET_IP_);
94 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp);
95 return XFS_ERROR(EFSCORRUPTED);
96 }
97 return 0;
98}
99
100STATIC int
101xfs_btree_check_sblock(
102 struct xfs_btree_cur *cur,
103 struct xfs_btree_block *block,
104 int level,
105 struct xfs_buf *bp)
106{
107 struct xfs_mount *mp;
108 struct xfs_buf *agbp;
109 struct xfs_agf *agf;
110 xfs_agblock_t agflen;
111 int sblock_ok = 1;
112
113 mp = cur->bc_mp;
114 agbp = cur->bc_private.a.agbp;
115 agf = XFS_BUF_TO_AGF(agbp);
116 agflen = be32_to_cpu(agf->agf_length);
117
118 if (xfs_sb_version_hascrc(&mp->m_sb)) {
119 sblock_ok = sblock_ok &&
120 uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid) &&
121 block->bb_u.s.bb_blkno == cpu_to_be64(
122 bp ? bp->b_bn : XFS_BUF_DADDR_NULL);
123 }
124
125 sblock_ok = sblock_ok &&
126 be32_to_cpu(block->bb_magic) == xfs_btree_magic(cur) &&
127 be16_to_cpu(block->bb_level) == level &&
128 be16_to_cpu(block->bb_numrecs) <=
129 cur->bc_ops->get_maxrecs(cur, level) &&
130 (block->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK) ||
131 be32_to_cpu(block->bb_u.s.bb_leftsib) < agflen) &&
132 block->bb_u.s.bb_leftsib &&
133 (block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK) ||
134 be32_to_cpu(block->bb_u.s.bb_rightsib) < agflen) &&
135 block->bb_u.s.bb_rightsib;
136
137 if (unlikely(XFS_TEST_ERROR(!sblock_ok, mp,
138 XFS_ERRTAG_BTREE_CHECK_SBLOCK,
139 XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
140 if (bp)
141 trace_xfs_btree_corrupt(bp, _RET_IP_);
142 XFS_ERROR_REPORT(__func__, XFS_ERRLEVEL_LOW, mp);
143 return XFS_ERROR(EFSCORRUPTED);
144 }
145 return 0;
146}
147
148
149
150
151int
152xfs_btree_check_block(
153 struct xfs_btree_cur *cur,
154 struct xfs_btree_block *block,
155 int level,
156 struct xfs_buf *bp)
157{
158 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
159 return xfs_btree_check_lblock(cur, block, level, bp);
160 else
161 return xfs_btree_check_sblock(cur, block, level, bp);
162}
163
164
165
166
167int
168xfs_btree_check_lptr(
169 struct xfs_btree_cur *cur,
170 xfs_dfsbno_t bno,
171 int level)
172{
173 XFS_WANT_CORRUPTED_RETURN(
174 level > 0 &&
175 bno != NULLDFSBNO &&
176 XFS_FSB_SANITY_CHECK(cur->bc_mp, bno));
177 return 0;
178}
179
180#ifdef DEBUG
181
182
183
184STATIC int
185xfs_btree_check_sptr(
186 struct xfs_btree_cur *cur,
187 xfs_agblock_t bno,
188 int level)
189{
190 xfs_agblock_t agblocks = cur->bc_mp->m_sb.sb_agblocks;
191
192 XFS_WANT_CORRUPTED_RETURN(
193 level > 0 &&
194 bno != NULLAGBLOCK &&
195 bno != 0 &&
196 bno < agblocks);
197 return 0;
198}
199
200
201
202
203STATIC int
204xfs_btree_check_ptr(
205 struct xfs_btree_cur *cur,
206 union xfs_btree_ptr *ptr,
207 int index,
208 int level)
209{
210 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
211 return xfs_btree_check_lptr(cur,
212 be64_to_cpu((&ptr->l)[index]), level);
213 } else {
214 return xfs_btree_check_sptr(cur,
215 be32_to_cpu((&ptr->s)[index]), level);
216 }
217}
218#endif
219
220
221
222
223
224
225
226
227
228void
229xfs_btree_lblock_calc_crc(
230 struct xfs_buf *bp)
231{
232 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
233 struct xfs_buf_log_item *bip = bp->b_fspriv;
234
235 if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
236 return;
237 if (bip)
238 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
239 xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length),
240 XFS_BTREE_LBLOCK_CRC_OFF);
241}
242
243bool
244xfs_btree_lblock_verify_crc(
245 struct xfs_buf *bp)
246{
247 if (xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
248 return xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
249 XFS_BTREE_LBLOCK_CRC_OFF);
250 return true;
251}
252
253
254
255
256
257
258
259
260
261void
262xfs_btree_sblock_calc_crc(
263 struct xfs_buf *bp)
264{
265 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
266 struct xfs_buf_log_item *bip = bp->b_fspriv;
267
268 if (!xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
269 return;
270 if (bip)
271 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
272 xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length),
273 XFS_BTREE_SBLOCK_CRC_OFF);
274}
275
276bool
277xfs_btree_sblock_verify_crc(
278 struct xfs_buf *bp)
279{
280 if (xfs_sb_version_hascrc(&bp->b_target->bt_mount->m_sb))
281 return xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
282 XFS_BTREE_SBLOCK_CRC_OFF);
283 return true;
284}
285
286
287
288
289void
290xfs_btree_del_cursor(
291 xfs_btree_cur_t *cur,
292 int error)
293{
294 int i;
295
296
297
298
299
300
301
302
303
304
305
306 for (i = 0; i < cur->bc_nlevels; i++) {
307 if (cur->bc_bufs[i])
308 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
309 else if (!error)
310 break;
311 }
312
313
314
315
316 ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
317 cur->bc_private.b.allocated == 0);
318
319
320
321 kmem_zone_free(xfs_btree_cur_zone, cur);
322}
323
324
325
326
327
328int
329xfs_btree_dup_cursor(
330 xfs_btree_cur_t *cur,
331 xfs_btree_cur_t **ncur)
332{
333 xfs_buf_t *bp;
334 int error;
335 int i;
336 xfs_mount_t *mp;
337 xfs_btree_cur_t *new;
338 xfs_trans_t *tp;
339
340 tp = cur->bc_tp;
341 mp = cur->bc_mp;
342
343
344
345
346 new = cur->bc_ops->dup_cursor(cur);
347
348
349
350
351 new->bc_rec = cur->bc_rec;
352
353
354
355
356 for (i = 0; i < new->bc_nlevels; i++) {
357 new->bc_ptrs[i] = cur->bc_ptrs[i];
358 new->bc_ra[i] = cur->bc_ra[i];
359 bp = cur->bc_bufs[i];
360 if (bp) {
361 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
362 XFS_BUF_ADDR(bp), mp->m_bsize,
363 0, &bp,
364 cur->bc_ops->buf_ops);
365 if (error) {
366 xfs_btree_del_cursor(new, error);
367 *ncur = NULL;
368 return error;
369 }
370 }
371 new->bc_bufs[i] = bp;
372 }
373 *ncur = new;
374 return 0;
375}
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
411{
412 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
413 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
414 return XFS_BTREE_LBLOCK_CRC_LEN;
415 return XFS_BTREE_LBLOCK_LEN;
416 }
417 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
418 return XFS_BTREE_SBLOCK_CRC_LEN;
419 return XFS_BTREE_SBLOCK_LEN;
420}
421
422
423
424
425static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
426{
427 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
428 sizeof(__be64) : sizeof(__be32);
429}
430
431
432
433
434STATIC size_t
435xfs_btree_rec_offset(
436 struct xfs_btree_cur *cur,
437 int n)
438{
439 return xfs_btree_block_len(cur) +
440 (n - 1) * cur->bc_ops->rec_len;
441}
442
443
444
445
446STATIC size_t
447xfs_btree_key_offset(
448 struct xfs_btree_cur *cur,
449 int n)
450{
451 return xfs_btree_block_len(cur) +
452 (n - 1) * cur->bc_ops->key_len;
453}
454
455
456
457
458STATIC size_t
459xfs_btree_ptr_offset(
460 struct xfs_btree_cur *cur,
461 int n,
462 int level)
463{
464 return xfs_btree_block_len(cur) +
465 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
466 (n - 1) * xfs_btree_ptr_len(cur);
467}
468
469
470
471
472STATIC union xfs_btree_rec *
473xfs_btree_rec_addr(
474 struct xfs_btree_cur *cur,
475 int n,
476 struct xfs_btree_block *block)
477{
478 return (union xfs_btree_rec *)
479 ((char *)block + xfs_btree_rec_offset(cur, n));
480}
481
482
483
484
485STATIC union xfs_btree_key *
486xfs_btree_key_addr(
487 struct xfs_btree_cur *cur,
488 int n,
489 struct xfs_btree_block *block)
490{
491 return (union xfs_btree_key *)
492 ((char *)block + xfs_btree_key_offset(cur, n));
493}
494
495
496
497
498STATIC union xfs_btree_ptr *
499xfs_btree_ptr_addr(
500 struct xfs_btree_cur *cur,
501 int n,
502 struct xfs_btree_block *block)
503{
504 int level = xfs_btree_get_level(block);
505
506 ASSERT(block->bb_level != 0);
507
508 return (union xfs_btree_ptr *)
509 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
510}
511
512
513
514
515
516
517
518STATIC struct xfs_btree_block *
519xfs_btree_get_iroot(
520 struct xfs_btree_cur *cur)
521{
522 struct xfs_ifork *ifp;
523
524 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, cur->bc_private.b.whichfork);
525 return (struct xfs_btree_block *)ifp->if_broot;
526}
527
528
529
530
531
532STATIC struct xfs_btree_block *
533xfs_btree_get_block(
534 struct xfs_btree_cur *cur,
535 int level,
536 struct xfs_buf **bpp)
537{
538 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
539 (level == cur->bc_nlevels - 1)) {
540 *bpp = NULL;
541 return xfs_btree_get_iroot(cur);
542 }
543
544 *bpp = cur->bc_bufs[level];
545 return XFS_BUF_TO_BLOCK(*bpp);
546}
547
548
549
550
551
552xfs_buf_t *
553xfs_btree_get_bufl(
554 xfs_mount_t *mp,
555 xfs_trans_t *tp,
556 xfs_fsblock_t fsbno,
557 uint lock)
558{
559 xfs_buf_t *bp;
560 xfs_daddr_t d;
561
562 ASSERT(fsbno != NULLFSBLOCK);
563 d = XFS_FSB_TO_DADDR(mp, fsbno);
564 bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
565 ASSERT(!xfs_buf_geterror(bp));
566 return bp;
567}
568
569
570
571
572
573xfs_buf_t *
574xfs_btree_get_bufs(
575 xfs_mount_t *mp,
576 xfs_trans_t *tp,
577 xfs_agnumber_t agno,
578 xfs_agblock_t agbno,
579 uint lock)
580{
581 xfs_buf_t *bp;
582 xfs_daddr_t d;
583
584 ASSERT(agno != NULLAGNUMBER);
585 ASSERT(agbno != NULLAGBLOCK);
586 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
587 bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
588 ASSERT(!xfs_buf_geterror(bp));
589 return bp;
590}
591
592
593
594
595int
596xfs_btree_islastblock(
597 xfs_btree_cur_t *cur,
598 int level)
599{
600 struct xfs_btree_block *block;
601 xfs_buf_t *bp;
602
603 block = xfs_btree_get_block(cur, level, &bp);
604 xfs_btree_check_block(cur, block, level, bp);
605 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
606 return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO);
607 else
608 return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
609}
610
611
612
613
614
615STATIC int
616xfs_btree_firstrec(
617 xfs_btree_cur_t *cur,
618 int level)
619{
620 struct xfs_btree_block *block;
621 xfs_buf_t *bp;
622
623
624
625
626 block = xfs_btree_get_block(cur, level, &bp);
627 xfs_btree_check_block(cur, block, level, bp);
628
629
630
631 if (!block->bb_numrecs)
632 return 0;
633
634
635
636 cur->bc_ptrs[level] = 1;
637 return 1;
638}
639
640
641
642
643
644STATIC int
645xfs_btree_lastrec(
646 xfs_btree_cur_t *cur,
647 int level)
648{
649 struct xfs_btree_block *block;
650 xfs_buf_t *bp;
651
652
653
654
655 block = xfs_btree_get_block(cur, level, &bp);
656 xfs_btree_check_block(cur, block, level, bp);
657
658
659
660 if (!block->bb_numrecs)
661 return 0;
662
663
664
665 cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
666 return 1;
667}
668
669
670
671
672
673void
674xfs_btree_offsets(
675 __int64_t fields,
676 const short *offsets,
677 int nbits,
678 int *first,
679 int *last)
680{
681 int i;
682 __int64_t imask;
683
684 ASSERT(fields != 0);
685
686
687
688 for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
689 if (imask & fields) {
690 *first = offsets[i];
691 break;
692 }
693 }
694
695
696
697 for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
698 if (imask & fields) {
699 *last = offsets[i + 1] - 1;
700 break;
701 }
702 }
703}
704
705
706
707
708
709int
710xfs_btree_read_bufl(
711 struct xfs_mount *mp,
712 struct xfs_trans *tp,
713 xfs_fsblock_t fsbno,
714 uint lock,
715 struct xfs_buf **bpp,
716 int refval,
717 const struct xfs_buf_ops *ops)
718{
719 struct xfs_buf *bp;
720 xfs_daddr_t d;
721 int error;
722
723 ASSERT(fsbno != NULLFSBLOCK);
724 d = XFS_FSB_TO_DADDR(mp, fsbno);
725 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
726 mp->m_bsize, lock, &bp, ops);
727 if (error)
728 return error;
729 ASSERT(!xfs_buf_geterror(bp));
730 if (bp)
731 xfs_buf_set_ref(bp, refval);
732 *bpp = bp;
733 return 0;
734}
735
736
737
738
739
740
741void
742xfs_btree_reada_bufl(
743 struct xfs_mount *mp,
744 xfs_fsblock_t fsbno,
745 xfs_extlen_t count,
746 const struct xfs_buf_ops *ops)
747{
748 xfs_daddr_t d;
749
750 ASSERT(fsbno != NULLFSBLOCK);
751 d = XFS_FSB_TO_DADDR(mp, fsbno);
752 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
753}
754
755
756
757
758
759
760void
761xfs_btree_reada_bufs(
762 struct xfs_mount *mp,
763 xfs_agnumber_t agno,
764 xfs_agblock_t agbno,
765 xfs_extlen_t count,
766 const struct xfs_buf_ops *ops)
767{
768 xfs_daddr_t d;
769
770 ASSERT(agno != NULLAGNUMBER);
771 ASSERT(agbno != NULLAGBLOCK);
772 d = XFS_AGB_TO_DADDR(mp, agno, agbno);
773 xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
774}
775
776STATIC int
777xfs_btree_readahead_lblock(
778 struct xfs_btree_cur *cur,
779 int lr,
780 struct xfs_btree_block *block)
781{
782 int rval = 0;
783 xfs_dfsbno_t left = be64_to_cpu(block->bb_u.l.bb_leftsib);
784 xfs_dfsbno_t right = be64_to_cpu(block->bb_u.l.bb_rightsib);
785
786 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLDFSBNO) {
787 xfs_btree_reada_bufl(cur->bc_mp, left, 1,
788 cur->bc_ops->buf_ops);
789 rval++;
790 }
791
792 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLDFSBNO) {
793 xfs_btree_reada_bufl(cur->bc_mp, right, 1,
794 cur->bc_ops->buf_ops);
795 rval++;
796 }
797
798 return rval;
799}
800
801STATIC int
802xfs_btree_readahead_sblock(
803 struct xfs_btree_cur *cur,
804 int lr,
805 struct xfs_btree_block *block)
806{
807 int rval = 0;
808 xfs_agblock_t left = be32_to_cpu(block->bb_u.s.bb_leftsib);
809 xfs_agblock_t right = be32_to_cpu(block->bb_u.s.bb_rightsib);
810
811
812 if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
813 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
814 left, 1, cur->bc_ops->buf_ops);
815 rval++;
816 }
817
818 if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
819 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
820 right, 1, cur->bc_ops->buf_ops);
821 rval++;
822 }
823
824 return rval;
825}
826
827
828
829
830
831STATIC int
832xfs_btree_readahead(
833 struct xfs_btree_cur *cur,
834 int lev,
835 int lr)
836{
837 struct xfs_btree_block *block;
838
839
840
841
842
843 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
844 (lev == cur->bc_nlevels - 1))
845 return 0;
846
847 if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
848 return 0;
849
850 cur->bc_ra[lev] |= lr;
851 block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]);
852
853 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
854 return xfs_btree_readahead_lblock(cur, lr, block);
855 return xfs_btree_readahead_sblock(cur, lr, block);
856}
857
858
859
860
861
862STATIC void
863xfs_btree_setbuf(
864 xfs_btree_cur_t *cur,
865 int lev,
866 xfs_buf_t *bp)
867{
868 struct xfs_btree_block *b;
869
870 if (cur->bc_bufs[lev])
871 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]);
872 cur->bc_bufs[lev] = bp;
873 cur->bc_ra[lev] = 0;
874
875 b = XFS_BUF_TO_BLOCK(bp);
876 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
877 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO))
878 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
879 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO))
880 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
881 } else {
882 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
883 cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
884 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
885 cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
886 }
887}
888
889STATIC int
890xfs_btree_ptr_is_null(
891 struct xfs_btree_cur *cur,
892 union xfs_btree_ptr *ptr)
893{
894 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
895 return ptr->l == cpu_to_be64(NULLDFSBNO);
896 else
897 return ptr->s == cpu_to_be32(NULLAGBLOCK);
898}
899
900STATIC void
901xfs_btree_set_ptr_null(
902 struct xfs_btree_cur *cur,
903 union xfs_btree_ptr *ptr)
904{
905 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
906 ptr->l = cpu_to_be64(NULLDFSBNO);
907 else
908 ptr->s = cpu_to_be32(NULLAGBLOCK);
909}
910
911
912
913
914STATIC void
915xfs_btree_get_sibling(
916 struct xfs_btree_cur *cur,
917 struct xfs_btree_block *block,
918 union xfs_btree_ptr *ptr,
919 int lr)
920{
921 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
922
923 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
924 if (lr == XFS_BB_RIGHTSIB)
925 ptr->l = block->bb_u.l.bb_rightsib;
926 else
927 ptr->l = block->bb_u.l.bb_leftsib;
928 } else {
929 if (lr == XFS_BB_RIGHTSIB)
930 ptr->s = block->bb_u.s.bb_rightsib;
931 else
932 ptr->s = block->bb_u.s.bb_leftsib;
933 }
934}
935
936STATIC void
937xfs_btree_set_sibling(
938 struct xfs_btree_cur *cur,
939 struct xfs_btree_block *block,
940 union xfs_btree_ptr *ptr,
941 int lr)
942{
943 ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
944
945 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
946 if (lr == XFS_BB_RIGHTSIB)
947 block->bb_u.l.bb_rightsib = ptr->l;
948 else
949 block->bb_u.l.bb_leftsib = ptr->l;
950 } else {
951 if (lr == XFS_BB_RIGHTSIB)
952 block->bb_u.s.bb_rightsib = ptr->s;
953 else
954 block->bb_u.s.bb_leftsib = ptr->s;
955 }
956}
957
958void
959xfs_btree_init_block_int(
960 struct xfs_mount *mp,
961 struct xfs_btree_block *buf,
962 xfs_daddr_t blkno,
963 __u32 magic,
964 __u16 level,
965 __u16 numrecs,
966 __u64 owner,
967 unsigned int flags)
968{
969 buf->bb_magic = cpu_to_be32(magic);
970 buf->bb_level = cpu_to_be16(level);
971 buf->bb_numrecs = cpu_to_be16(numrecs);
972
973 if (flags & XFS_BTREE_LONG_PTRS) {
974 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLDFSBNO);
975 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLDFSBNO);
976 if (flags & XFS_BTREE_CRC_BLOCKS) {
977 buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);
978 buf->bb_u.l.bb_owner = cpu_to_be64(owner);
979 uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_uuid);
980 buf->bb_u.l.bb_pad = 0;
981 }
982 } else {
983
984 __u32 __owner = (__u32)owner;
985
986 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
987 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
988 if (flags & XFS_BTREE_CRC_BLOCKS) {
989 buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);
990 buf->bb_u.s.bb_owner = cpu_to_be32(__owner);
991 uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_uuid);
992 }
993 }
994}
995
996void
997xfs_btree_init_block(
998 struct xfs_mount *mp,
999 struct xfs_buf *bp,
1000 __u32 magic,
1001 __u16 level,
1002 __u16 numrecs,
1003 __u64 owner,
1004 unsigned int flags)
1005{
1006 xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1007 magic, level, numrecs, owner, flags);
1008}
1009
1010STATIC void
1011xfs_btree_init_block_cur(
1012 struct xfs_btree_cur *cur,
1013 struct xfs_buf *bp,
1014 int level,
1015 int numrecs)
1016{
1017 __u64 owner;
1018
1019
1020
1021
1022
1023
1024
1025 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1026 owner = cur->bc_private.b.ip->i_ino;
1027 else
1028 owner = cur->bc_private.a.agno;
1029
1030 xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp), bp->b_bn,
1031 xfs_btree_magic(cur), level, numrecs,
1032 owner, cur->bc_flags);
1033}
1034
1035
1036
1037
1038
1039
1040STATIC int
1041xfs_btree_is_lastrec(
1042 struct xfs_btree_cur *cur,
1043 struct xfs_btree_block *block,
1044 int level)
1045{
1046 union xfs_btree_ptr ptr;
1047
1048 if (level > 0)
1049 return 0;
1050 if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
1051 return 0;
1052
1053 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1054 if (!xfs_btree_ptr_is_null(cur, &ptr))
1055 return 0;
1056 return 1;
1057}
1058
1059STATIC void
1060xfs_btree_buf_to_ptr(
1061 struct xfs_btree_cur *cur,
1062 struct xfs_buf *bp,
1063 union xfs_btree_ptr *ptr)
1064{
1065 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1066 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
1067 XFS_BUF_ADDR(bp)));
1068 else {
1069 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,
1070 XFS_BUF_ADDR(bp)));
1071 }
1072}
1073
1074STATIC xfs_daddr_t
1075xfs_btree_ptr_to_daddr(
1076 struct xfs_btree_cur *cur,
1077 union xfs_btree_ptr *ptr)
1078{
1079 if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1080 ASSERT(ptr->l != cpu_to_be64(NULLDFSBNO));
1081
1082 return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
1083 } else {
1084 ASSERT(cur->bc_private.a.agno != NULLAGNUMBER);
1085 ASSERT(ptr->s != cpu_to_be32(NULLAGBLOCK));
1086
1087 return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
1088 be32_to_cpu(ptr->s));
1089 }
1090}
1091
1092STATIC void
1093xfs_btree_set_refs(
1094 struct xfs_btree_cur *cur,
1095 struct xfs_buf *bp)
1096{
1097 switch (cur->bc_btnum) {
1098 case XFS_BTNUM_BNO:
1099 case XFS_BTNUM_CNT:
1100 xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF);
1101 break;
1102 case XFS_BTNUM_INO:
1103 xfs_buf_set_ref(bp, XFS_INO_BTREE_REF);
1104 break;
1105 case XFS_BTNUM_BMAP:
1106 xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF);
1107 break;
1108 default:
1109 ASSERT(0);
1110 }
1111}
1112
1113STATIC int
1114xfs_btree_get_buf_block(
1115 struct xfs_btree_cur *cur,
1116 union xfs_btree_ptr *ptr,
1117 int flags,
1118 struct xfs_btree_block **block,
1119 struct xfs_buf **bpp)
1120{
1121 struct xfs_mount *mp = cur->bc_mp;
1122 xfs_daddr_t d;
1123
1124
1125 ASSERT(!(flags & XBF_TRYLOCK));
1126
1127 d = xfs_btree_ptr_to_daddr(cur, ptr);
1128 *bpp = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d,
1129 mp->m_bsize, flags);
1130
1131 if (!*bpp)
1132 return ENOMEM;
1133
1134 (*bpp)->b_ops = cur->bc_ops->buf_ops;
1135 *block = XFS_BUF_TO_BLOCK(*bpp);
1136 return 0;
1137}
1138
1139
1140
1141
1142
1143STATIC int
1144xfs_btree_read_buf_block(
1145 struct xfs_btree_cur *cur,
1146 union xfs_btree_ptr *ptr,
1147 int level,
1148 int flags,
1149 struct xfs_btree_block **block,
1150 struct xfs_buf **bpp)
1151{
1152 struct xfs_mount *mp = cur->bc_mp;
1153 xfs_daddr_t d;
1154 int error;
1155
1156
1157 ASSERT(!(flags & XBF_TRYLOCK));
1158
1159 d = xfs_btree_ptr_to_daddr(cur, ptr);
1160 error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1161 mp->m_bsize, flags, bpp,
1162 cur->bc_ops->buf_ops);
1163 if (error)
1164 return error;
1165
1166 ASSERT(!xfs_buf_geterror(*bpp));
1167 xfs_btree_set_refs(cur, *bpp);
1168 *block = XFS_BUF_TO_BLOCK(*bpp);
1169 return 0;
1170}
1171
1172
1173
1174
1175STATIC void
1176xfs_btree_copy_keys(
1177 struct xfs_btree_cur *cur,
1178 union xfs_btree_key *dst_key,
1179 union xfs_btree_key *src_key,
1180 int numkeys)
1181{
1182 ASSERT(numkeys >= 0);
1183 memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1184}
1185
1186
1187
1188
1189STATIC void
1190xfs_btree_copy_recs(
1191 struct xfs_btree_cur *cur,
1192 union xfs_btree_rec *dst_rec,
1193 union xfs_btree_rec *src_rec,
1194 int numrecs)
1195{
1196 ASSERT(numrecs >= 0);
1197 memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1198}
1199
1200
1201
1202
1203STATIC void
1204xfs_btree_copy_ptrs(
1205 struct xfs_btree_cur *cur,
1206 union xfs_btree_ptr *dst_ptr,
1207 union xfs_btree_ptr *src_ptr,
1208 int numptrs)
1209{
1210 ASSERT(numptrs >= 0);
1211 memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1212}
1213
1214
1215
1216
1217STATIC void
1218xfs_btree_shift_keys(
1219 struct xfs_btree_cur *cur,
1220 union xfs_btree_key *key,
1221 int dir,
1222 int numkeys)
1223{
1224 char *dst_key;
1225
1226 ASSERT(numkeys >= 0);
1227 ASSERT(dir == 1 || dir == -1);
1228
1229 dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1230 memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1231}
1232
1233
1234
1235
1236STATIC void
1237xfs_btree_shift_recs(
1238 struct xfs_btree_cur *cur,
1239 union xfs_btree_rec *rec,
1240 int dir,
1241 int numrecs)
1242{
1243 char *dst_rec;
1244
1245 ASSERT(numrecs >= 0);
1246 ASSERT(dir == 1 || dir == -1);
1247
1248 dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1249 memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1250}
1251
1252
1253
1254
1255STATIC void
1256xfs_btree_shift_ptrs(
1257 struct xfs_btree_cur *cur,
1258 union xfs_btree_ptr *ptr,
1259 int dir,
1260 int numptrs)
1261{
1262 char *dst_ptr;
1263
1264 ASSERT(numptrs >= 0);
1265 ASSERT(dir == 1 || dir == -1);
1266
1267 dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1268 memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1269}
1270
1271
1272
1273
1274STATIC void
1275xfs_btree_log_keys(
1276 struct xfs_btree_cur *cur,
1277 struct xfs_buf *bp,
1278 int first,
1279 int last)
1280{
1281 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1282 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1283
1284 if (bp) {
1285 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1286 xfs_trans_log_buf(cur->bc_tp, bp,
1287 xfs_btree_key_offset(cur, first),
1288 xfs_btree_key_offset(cur, last + 1) - 1);
1289 } else {
1290 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1291 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1292 }
1293
1294 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1295}
1296
1297
1298
1299
1300void
1301xfs_btree_log_recs(
1302 struct xfs_btree_cur *cur,
1303 struct xfs_buf *bp,
1304 int first,
1305 int last)
1306{
1307 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1308 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1309
1310 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1311 xfs_trans_log_buf(cur->bc_tp, bp,
1312 xfs_btree_rec_offset(cur, first),
1313 xfs_btree_rec_offset(cur, last + 1) - 1);
1314
1315 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1316}
1317
1318
1319
1320
1321STATIC void
1322xfs_btree_log_ptrs(
1323 struct xfs_btree_cur *cur,
1324 struct xfs_buf *bp,
1325 int first,
1326 int last)
1327{
1328 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1329 XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1330
1331 if (bp) {
1332 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp);
1333 int level = xfs_btree_get_level(block);
1334
1335 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1336 xfs_trans_log_buf(cur->bc_tp, bp,
1337 xfs_btree_ptr_offset(cur, first, level),
1338 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1339 } else {
1340 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1341 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1342 }
1343
1344 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1345}
1346
1347
1348
1349
1350void
1351xfs_btree_log_block(
1352 struct xfs_btree_cur *cur,
1353 struct xfs_buf *bp,
1354 int fields)
1355{
1356 int first;
1357 int last;
1358 static const short soffsets[] = {
1359 offsetof(struct xfs_btree_block, bb_magic),
1360 offsetof(struct xfs_btree_block, bb_level),
1361 offsetof(struct xfs_btree_block, bb_numrecs),
1362 offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib),
1363 offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib),
1364 offsetof(struct xfs_btree_block, bb_u.s.bb_blkno),
1365 offsetof(struct xfs_btree_block, bb_u.s.bb_lsn),
1366 offsetof(struct xfs_btree_block, bb_u.s.bb_uuid),
1367 offsetof(struct xfs_btree_block, bb_u.s.bb_owner),
1368 offsetof(struct xfs_btree_block, bb_u.s.bb_crc),
1369 XFS_BTREE_SBLOCK_CRC_LEN
1370 };
1371 static const short loffsets[] = {
1372 offsetof(struct xfs_btree_block, bb_magic),
1373 offsetof(struct xfs_btree_block, bb_level),
1374 offsetof(struct xfs_btree_block, bb_numrecs),
1375 offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib),
1376 offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib),
1377 offsetof(struct xfs_btree_block, bb_u.l.bb_blkno),
1378 offsetof(struct xfs_btree_block, bb_u.l.bb_lsn),
1379 offsetof(struct xfs_btree_block, bb_u.l.bb_uuid),
1380 offsetof(struct xfs_btree_block, bb_u.l.bb_owner),
1381 offsetof(struct xfs_btree_block, bb_u.l.bb_crc),
1382 offsetof(struct xfs_btree_block, bb_u.l.bb_pad),
1383 XFS_BTREE_LBLOCK_CRC_LEN
1384 };
1385
1386 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1387 XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
1388
1389 if (bp) {
1390 int nbits;
1391
1392 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
1393
1394
1395
1396
1397
1398
1399
1400 if (fields == XFS_BB_ALL_BITS)
1401 fields = XFS_BB_ALL_BITS_CRC;
1402 nbits = XFS_BB_NUM_BITS_CRC;
1403 } else {
1404 nbits = XFS_BB_NUM_BITS;
1405 }
1406 xfs_btree_offsets(fields,
1407 (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1408 loffsets : soffsets,
1409 nbits, &first, &last);
1410 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1411 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1412 } else {
1413 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1414 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1415 }
1416
1417 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1418}
1419
1420
1421
1422
1423
1424int
1425xfs_btree_increment(
1426 struct xfs_btree_cur *cur,
1427 int level,
1428 int *stat)
1429{
1430 struct xfs_btree_block *block;
1431 union xfs_btree_ptr ptr;
1432 struct xfs_buf *bp;
1433 int error;
1434 int lev;
1435
1436 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1437 XFS_BTREE_TRACE_ARGI(cur, level);
1438
1439 ASSERT(level < cur->bc_nlevels);
1440
1441
1442 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1443
1444
1445 block = xfs_btree_get_block(cur, level, &bp);
1446
1447#ifdef DEBUG
1448 error = xfs_btree_check_block(cur, block, level, bp);
1449 if (error)
1450 goto error0;
1451#endif
1452
1453
1454 if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1455 goto out1;
1456
1457
1458 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1459 if (xfs_btree_ptr_is_null(cur, &ptr))
1460 goto out0;
1461
1462 XFS_BTREE_STATS_INC(cur, increment);
1463
1464
1465
1466
1467
1468 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1469 block = xfs_btree_get_block(cur, lev, &bp);
1470
1471#ifdef DEBUG
1472 error = xfs_btree_check_block(cur, block, lev, bp);
1473 if (error)
1474 goto error0;
1475#endif
1476
1477 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1478 break;
1479
1480
1481 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1482 }
1483
1484
1485
1486
1487
1488 if (lev == cur->bc_nlevels) {
1489 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1490 goto out0;
1491 ASSERT(0);
1492 error = EFSCORRUPTED;
1493 goto error0;
1494 }
1495 ASSERT(lev < cur->bc_nlevels);
1496
1497
1498
1499
1500
1501 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1502 union xfs_btree_ptr *ptrp;
1503
1504 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1505 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1506 0, &block, &bp);
1507 if (error)
1508 goto error0;
1509
1510 xfs_btree_setbuf(cur, lev, bp);
1511 cur->bc_ptrs[lev] = 1;
1512 }
1513out1:
1514 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1515 *stat = 1;
1516 return 0;
1517
1518out0:
1519 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1520 *stat = 0;
1521 return 0;
1522
1523error0:
1524 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1525 return error;
1526}
1527
1528
1529
1530
1531
1532int
1533xfs_btree_decrement(
1534 struct xfs_btree_cur *cur,
1535 int level,
1536 int *stat)
1537{
1538 struct xfs_btree_block *block;
1539 xfs_buf_t *bp;
1540 int error;
1541 int lev;
1542 union xfs_btree_ptr ptr;
1543
1544 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1545 XFS_BTREE_TRACE_ARGI(cur, level);
1546
1547 ASSERT(level < cur->bc_nlevels);
1548
1549
1550 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1551
1552
1553 if (--cur->bc_ptrs[level] > 0)
1554 goto out1;
1555
1556
1557 block = xfs_btree_get_block(cur, level, &bp);
1558
1559#ifdef DEBUG
1560 error = xfs_btree_check_block(cur, block, level, bp);
1561 if (error)
1562 goto error0;
1563#endif
1564
1565
1566 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1567 if (xfs_btree_ptr_is_null(cur, &ptr))
1568 goto out0;
1569
1570 XFS_BTREE_STATS_INC(cur, decrement);
1571
1572
1573
1574
1575
1576 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1577 if (--cur->bc_ptrs[lev] > 0)
1578 break;
1579
1580 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1581 }
1582
1583
1584
1585
1586
1587 if (lev == cur->bc_nlevels) {
1588 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1589 goto out0;
1590 ASSERT(0);
1591 error = EFSCORRUPTED;
1592 goto error0;
1593 }
1594 ASSERT(lev < cur->bc_nlevels);
1595
1596
1597
1598
1599
1600 for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1601 union xfs_btree_ptr *ptrp;
1602
1603 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1604 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1605 0, &block, &bp);
1606 if (error)
1607 goto error0;
1608 xfs_btree_setbuf(cur, lev, bp);
1609 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block);
1610 }
1611out1:
1612 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1613 *stat = 1;
1614 return 0;
1615
1616out0:
1617 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1618 *stat = 0;
1619 return 0;
1620
1621error0:
1622 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1623 return error;
1624}
1625
1626STATIC int
1627xfs_btree_lookup_get_block(
1628 struct xfs_btree_cur *cur,
1629 int level,
1630 union xfs_btree_ptr *pp,
1631 struct xfs_btree_block **blkp)
1632{
1633 struct xfs_buf *bp;
1634 int error = 0;
1635
1636
1637 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1638 (level == cur->bc_nlevels - 1)) {
1639 *blkp = xfs_btree_get_iroot(cur);
1640 return 0;
1641 }
1642
1643
1644
1645
1646
1647
1648
1649 bp = cur->bc_bufs[level];
1650 if (bp && XFS_BUF_ADDR(bp) == xfs_btree_ptr_to_daddr(cur, pp)) {
1651 *blkp = XFS_BUF_TO_BLOCK(bp);
1652 return 0;
1653 }
1654
1655 error = xfs_btree_read_buf_block(cur, pp, level, 0, blkp, &bp);
1656 if (error)
1657 return error;
1658
1659 xfs_btree_setbuf(cur, level, bp);
1660 return 0;
1661}
1662
1663
1664
1665
1666
1667
1668STATIC union xfs_btree_key *
1669xfs_lookup_get_search_key(
1670 struct xfs_btree_cur *cur,
1671 int level,
1672 int keyno,
1673 struct xfs_btree_block *block,
1674 union xfs_btree_key *kp)
1675{
1676 if (level == 0) {
1677 cur->bc_ops->init_key_from_rec(kp,
1678 xfs_btree_rec_addr(cur, keyno, block));
1679 return kp;
1680 }
1681
1682 return xfs_btree_key_addr(cur, keyno, block);
1683}
1684
1685
1686
1687
1688
1689int
1690xfs_btree_lookup(
1691 struct xfs_btree_cur *cur,
1692 xfs_lookup_t dir,
1693 int *stat)
1694{
1695 struct xfs_btree_block *block;
1696 __int64_t diff;
1697 int error;
1698 int keyno;
1699 int level;
1700 union xfs_btree_ptr *pp;
1701 union xfs_btree_ptr ptr;
1702
1703 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1704 XFS_BTREE_TRACE_ARGI(cur, dir);
1705
1706 XFS_BTREE_STATS_INC(cur, lookup);
1707
1708 block = NULL;
1709 keyno = 0;
1710
1711
1712 cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1713 pp = &ptr;
1714
1715
1716
1717
1718
1719
1720
1721 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1722
1723 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1724 if (error)
1725 goto error0;
1726
1727 if (diff == 0) {
1728
1729
1730
1731
1732 keyno = 1;
1733 } else {
1734
1735
1736 int high;
1737 int low;
1738
1739
1740 low = 1;
1741 high = xfs_btree_get_numrecs(block);
1742 if (!high) {
1743
1744 ASSERT(level == 0 && cur->bc_nlevels == 1);
1745
1746 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1747 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1748 *stat = 0;
1749 return 0;
1750 }
1751
1752
1753 while (low <= high) {
1754 union xfs_btree_key key;
1755 union xfs_btree_key *kp;
1756
1757 XFS_BTREE_STATS_INC(cur, compare);
1758
1759
1760 keyno = (low + high) >> 1;
1761
1762
1763 kp = xfs_lookup_get_search_key(cur, level,
1764 keyno, block, &key);
1765
1766
1767
1768
1769
1770
1771
1772 diff = cur->bc_ops->key_diff(cur, kp);
1773 if (diff < 0)
1774 low = keyno + 1;
1775 else if (diff > 0)
1776 high = keyno - 1;
1777 else
1778 break;
1779 }
1780 }
1781
1782
1783
1784
1785
1786 if (level > 0) {
1787
1788
1789
1790
1791 if (diff > 0 && --keyno < 1)
1792 keyno = 1;
1793 pp = xfs_btree_ptr_addr(cur, keyno, block);
1794
1795#ifdef DEBUG
1796 error = xfs_btree_check_ptr(cur, pp, 0, level);
1797 if (error)
1798 goto error0;
1799#endif
1800 cur->bc_ptrs[level] = keyno;
1801 }
1802 }
1803
1804
1805 if (dir != XFS_LOOKUP_LE && diff < 0) {
1806 keyno++;
1807
1808
1809
1810
1811 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1812 if (dir == XFS_LOOKUP_GE &&
1813 keyno > xfs_btree_get_numrecs(block) &&
1814 !xfs_btree_ptr_is_null(cur, &ptr)) {
1815 int i;
1816
1817 cur->bc_ptrs[0] = keyno;
1818 error = xfs_btree_increment(cur, 0, &i);
1819 if (error)
1820 goto error0;
1821 XFS_WANT_CORRUPTED_RETURN(i == 1);
1822 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1823 *stat = 1;
1824 return 0;
1825 }
1826 } else if (dir == XFS_LOOKUP_LE && diff > 0)
1827 keyno--;
1828 cur->bc_ptrs[0] = keyno;
1829
1830
1831 if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
1832 *stat = 0;
1833 else if (dir != XFS_LOOKUP_EQ || diff == 0)
1834 *stat = 1;
1835 else
1836 *stat = 0;
1837 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1838 return 0;
1839
1840error0:
1841 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1842 return error;
1843}
1844
1845
1846
1847
1848STATIC int
1849xfs_btree_updkey(
1850 struct xfs_btree_cur *cur,
1851 union xfs_btree_key *keyp,
1852 int level)
1853{
1854 struct xfs_btree_block *block;
1855 struct xfs_buf *bp;
1856 union xfs_btree_key *kp;
1857 int ptr;
1858
1859 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1860 XFS_BTREE_TRACE_ARGIK(cur, level, keyp);
1861
1862 ASSERT(!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || level >= 1);
1863
1864
1865
1866
1867
1868
1869
1870 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1871#ifdef DEBUG
1872 int error;
1873#endif
1874 block = xfs_btree_get_block(cur, level, &bp);
1875#ifdef DEBUG
1876 error = xfs_btree_check_block(cur, block, level, bp);
1877 if (error) {
1878 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1879 return error;
1880 }
1881#endif
1882 ptr = cur->bc_ptrs[level];
1883 kp = xfs_btree_key_addr(cur, ptr, block);
1884 xfs_btree_copy_keys(cur, kp, keyp, 1);
1885 xfs_btree_log_keys(cur, bp, ptr, ptr);
1886 }
1887
1888 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1889 return 0;
1890}
1891
1892
1893
1894
1895
1896
1897int
1898xfs_btree_update(
1899 struct xfs_btree_cur *cur,
1900 union xfs_btree_rec *rec)
1901{
1902 struct xfs_btree_block *block;
1903 struct xfs_buf *bp;
1904 int error;
1905 int ptr;
1906 union xfs_btree_rec *rp;
1907
1908 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1909 XFS_BTREE_TRACE_ARGR(cur, rec);
1910
1911
1912 block = xfs_btree_get_block(cur, 0, &bp);
1913
1914#ifdef DEBUG
1915 error = xfs_btree_check_block(cur, block, 0, bp);
1916 if (error)
1917 goto error0;
1918#endif
1919
1920 ptr = cur->bc_ptrs[0];
1921 rp = xfs_btree_rec_addr(cur, ptr, block);
1922
1923
1924 xfs_btree_copy_recs(cur, rp, rec, 1);
1925 xfs_btree_log_recs(cur, bp, ptr, ptr);
1926
1927
1928
1929
1930
1931 if (xfs_btree_is_lastrec(cur, block, 0)) {
1932 cur->bc_ops->update_lastrec(cur, block, rec,
1933 ptr, LASTREC_UPDATE);
1934 }
1935
1936
1937 if (ptr == 1) {
1938 union xfs_btree_key key;
1939
1940 cur->bc_ops->init_key_from_rec(&key, rec);
1941 error = xfs_btree_updkey(cur, &key, 1);
1942 if (error)
1943 goto error0;
1944 }
1945
1946 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1947 return 0;
1948
1949error0:
1950 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1951 return error;
1952}
1953
1954
1955
1956
1957
1958STATIC int
1959xfs_btree_lshift(
1960 struct xfs_btree_cur *cur,
1961 int level,
1962 int *stat)
1963{
1964 union xfs_btree_key key;
1965 struct xfs_buf *lbp;
1966 struct xfs_btree_block *left;
1967 int lrecs;
1968 struct xfs_buf *rbp;
1969 struct xfs_btree_block *right;
1970 int rrecs;
1971 union xfs_btree_ptr lptr;
1972 union xfs_btree_key *rkp = NULL;
1973 union xfs_btree_ptr *rpp = NULL;
1974 union xfs_btree_rec *rrp = NULL;
1975 int error;
1976
1977 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1978 XFS_BTREE_TRACE_ARGI(cur, level);
1979
1980 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1981 level == cur->bc_nlevels - 1)
1982 goto out0;
1983
1984
1985 right = xfs_btree_get_block(cur, level, &rbp);
1986
1987#ifdef DEBUG
1988 error = xfs_btree_check_block(cur, right, level, rbp);
1989 if (error)
1990 goto error0;
1991#endif
1992
1993
1994 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
1995 if (xfs_btree_ptr_is_null(cur, &lptr))
1996 goto out0;
1997
1998
1999
2000
2001
2002 if (cur->bc_ptrs[level] <= 1)
2003 goto out0;
2004
2005
2006 error = xfs_btree_read_buf_block(cur, &lptr, level, 0, &left, &lbp);
2007 if (error)
2008 goto error0;
2009
2010
2011 lrecs = xfs_btree_get_numrecs(left);
2012 if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2013 goto out0;
2014
2015 rrecs = xfs_btree_get_numrecs(right);
2016
2017
2018
2019
2020
2021
2022 lrecs++;
2023 rrecs--;
2024
2025 XFS_BTREE_STATS_INC(cur, lshift);
2026 XFS_BTREE_STATS_ADD(cur, moves, 1);
2027
2028
2029
2030
2031
2032 if (level > 0) {
2033
2034 union xfs_btree_key *lkp;
2035 union xfs_btree_ptr *lpp;
2036
2037 lkp = xfs_btree_key_addr(cur, lrecs, left);
2038 rkp = xfs_btree_key_addr(cur, 1, right);
2039
2040 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2041 rpp = xfs_btree_ptr_addr(cur, 1, right);
2042#ifdef DEBUG
2043 error = xfs_btree_check_ptr(cur, rpp, 0, level);
2044 if (error)
2045 goto error0;
2046#endif
2047 xfs_btree_copy_keys(cur, lkp, rkp, 1);
2048 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
2049
2050 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
2051 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
2052
2053 ASSERT(cur->bc_ops->keys_inorder(cur,
2054 xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
2055 } else {
2056
2057 union xfs_btree_rec *lrp;
2058
2059 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2060 rrp = xfs_btree_rec_addr(cur, 1, right);
2061
2062 xfs_btree_copy_recs(cur, lrp, rrp, 1);
2063 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
2064
2065 ASSERT(cur->bc_ops->recs_inorder(cur,
2066 xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
2067 }
2068
2069 xfs_btree_set_numrecs(left, lrecs);
2070 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2071
2072 xfs_btree_set_numrecs(right, rrecs);
2073 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2074
2075
2076
2077
2078 XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
2079 if (level > 0) {
2080
2081#ifdef DEBUG
2082 int i;
2083
2084 for (i = 0; i < rrecs; i++) {
2085 error = xfs_btree_check_ptr(cur, rpp, i + 1, level);
2086 if (error)
2087 goto error0;
2088 }
2089#endif
2090 xfs_btree_shift_keys(cur,
2091 xfs_btree_key_addr(cur, 2, right),
2092 -1, rrecs);
2093 xfs_btree_shift_ptrs(cur,
2094 xfs_btree_ptr_addr(cur, 2, right),
2095 -1, rrecs);
2096
2097 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2098 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2099 } else {
2100
2101 xfs_btree_shift_recs(cur,
2102 xfs_btree_rec_addr(cur, 2, right),
2103 -1, rrecs);
2104 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2105
2106
2107
2108
2109
2110 cur->bc_ops->init_key_from_rec(&key,
2111 xfs_btree_rec_addr(cur, 1, right));
2112 rkp = &key;
2113 }
2114
2115
2116 error = xfs_btree_updkey(cur, rkp, level + 1);
2117 if (error)
2118 goto error0;
2119
2120
2121 cur->bc_ptrs[level]--;
2122
2123 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2124 *stat = 1;
2125 return 0;
2126
2127out0:
2128 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2129 *stat = 0;
2130 return 0;
2131
2132error0:
2133 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2134 return error;
2135}
2136
2137
2138
2139
2140
2141STATIC int
2142xfs_btree_rshift(
2143 struct xfs_btree_cur *cur,
2144 int level,
2145 int *stat)
2146{
2147 union xfs_btree_key key;
2148 struct xfs_buf *lbp;
2149 struct xfs_btree_block *left;
2150 struct xfs_buf *rbp;
2151 struct xfs_btree_block *right;
2152 struct xfs_btree_cur *tcur;
2153 union xfs_btree_ptr rptr;
2154 union xfs_btree_key *rkp;
2155 int rrecs;
2156 int lrecs;
2157 int error;
2158 int i;
2159
2160 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2161 XFS_BTREE_TRACE_ARGI(cur, level);
2162
2163 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2164 (level == cur->bc_nlevels - 1))
2165 goto out0;
2166
2167
2168 left = xfs_btree_get_block(cur, level, &lbp);
2169
2170#ifdef DEBUG
2171 error = xfs_btree_check_block(cur, left, level, lbp);
2172 if (error)
2173 goto error0;
2174#endif
2175
2176
2177 xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2178 if (xfs_btree_ptr_is_null(cur, &rptr))
2179 goto out0;
2180
2181
2182
2183
2184
2185 lrecs = xfs_btree_get_numrecs(left);
2186 if (cur->bc_ptrs[level] >= lrecs)
2187 goto out0;
2188
2189
2190 error = xfs_btree_read_buf_block(cur, &rptr, level, 0, &right, &rbp);
2191 if (error)
2192 goto error0;
2193
2194
2195 rrecs = xfs_btree_get_numrecs(right);
2196 if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2197 goto out0;
2198
2199 XFS_BTREE_STATS_INC(cur, rshift);
2200 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2201
2202
2203
2204
2205
2206 if (level > 0) {
2207
2208 union xfs_btree_key *lkp;
2209 union xfs_btree_ptr *lpp;
2210 union xfs_btree_ptr *rpp;
2211
2212 lkp = xfs_btree_key_addr(cur, lrecs, left);
2213 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2214 rkp = xfs_btree_key_addr(cur, 1, right);
2215 rpp = xfs_btree_ptr_addr(cur, 1, right);
2216
2217#ifdef DEBUG
2218 for (i = rrecs - 1; i >= 0; i--) {
2219 error = xfs_btree_check_ptr(cur, rpp, i, level);
2220 if (error)
2221 goto error0;
2222 }
2223#endif
2224
2225 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2226 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2227
2228#ifdef DEBUG
2229 error = xfs_btree_check_ptr(cur, lpp, 0, level);
2230 if (error)
2231 goto error0;
2232#endif
2233
2234
2235 xfs_btree_copy_keys(cur, rkp, lkp, 1);
2236 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2237
2238 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2239 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2240
2241 ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2242 xfs_btree_key_addr(cur, 2, right)));
2243 } else {
2244
2245 union xfs_btree_rec *lrp;
2246 union xfs_btree_rec *rrp;
2247
2248 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2249 rrp = xfs_btree_rec_addr(cur, 1, right);
2250
2251 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2252
2253
2254 xfs_btree_copy_recs(cur, rrp, lrp, 1);
2255 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2256
2257 cur->bc_ops->init_key_from_rec(&key, rrp);
2258 rkp = &key;
2259
2260 ASSERT(cur->bc_ops->recs_inorder(cur, rrp,
2261 xfs_btree_rec_addr(cur, 2, right)));
2262 }
2263
2264
2265
2266
2267 xfs_btree_set_numrecs(left, --lrecs);
2268 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2269
2270 xfs_btree_set_numrecs(right, ++rrecs);
2271 xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2272
2273
2274
2275
2276
2277 error = xfs_btree_dup_cursor(cur, &tcur);
2278 if (error)
2279 goto error0;
2280 i = xfs_btree_lastrec(tcur, level);
2281 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2282
2283 error = xfs_btree_increment(tcur, level, &i);
2284 if (error)
2285 goto error1;
2286
2287 error = xfs_btree_updkey(tcur, rkp, level + 1);
2288 if (error)
2289 goto error1;
2290
2291 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2292
2293 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2294 *stat = 1;
2295 return 0;
2296
2297out0:
2298 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2299 *stat = 0;
2300 return 0;
2301
2302error0:
2303 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2304 return error;
2305
2306error1:
2307 XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR);
2308 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2309 return error;
2310}
2311
2312
2313
2314
2315
2316
2317STATIC int
2318xfs_btree_split(
2319 struct xfs_btree_cur *cur,
2320 int level,
2321 union xfs_btree_ptr *ptrp,
2322 union xfs_btree_key *key,
2323 struct xfs_btree_cur **curp,
2324 int *stat)
2325{
2326 union xfs_btree_ptr lptr;
2327 struct xfs_buf *lbp;
2328 struct xfs_btree_block *left;
2329 union xfs_btree_ptr rptr;
2330 struct xfs_buf *rbp;
2331 struct xfs_btree_block *right;
2332 union xfs_btree_ptr rrptr;
2333 struct xfs_buf *rrbp;
2334 struct xfs_btree_block *rrblock;
2335 int lrecs;
2336 int rrecs;
2337 int src_index;
2338 int error;
2339#ifdef DEBUG
2340 int i;
2341#endif
2342
2343 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2344 XFS_BTREE_TRACE_ARGIPK(cur, level, *ptrp, key);
2345
2346 XFS_BTREE_STATS_INC(cur, split);
2347
2348
2349 left = xfs_btree_get_block(cur, level, &lbp);
2350
2351#ifdef DEBUG
2352 error = xfs_btree_check_block(cur, left, level, lbp);
2353 if (error)
2354 goto error0;
2355#endif
2356
2357 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2358
2359
2360 error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, 1, stat);
2361 if (error)
2362 goto error0;
2363 if (*stat == 0)
2364 goto out0;
2365 XFS_BTREE_STATS_INC(cur, alloc);
2366
2367
2368 error = xfs_btree_get_buf_block(cur, &rptr, 0, &right, &rbp);
2369 if (error)
2370 goto error0;
2371
2372
2373 xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0);
2374
2375
2376
2377
2378
2379
2380 lrecs = xfs_btree_get_numrecs(left);
2381 rrecs = lrecs / 2;
2382 if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2383 rrecs++;
2384 src_index = (lrecs - rrecs + 1);
2385
2386 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2387
2388
2389
2390
2391
2392
2393 if (level > 0) {
2394
2395 union xfs_btree_key *lkp;
2396 union xfs_btree_ptr *lpp;
2397 union xfs_btree_key *rkp;
2398 union xfs_btree_ptr *rpp;
2399
2400 lkp = xfs_btree_key_addr(cur, src_index, left);
2401 lpp = xfs_btree_ptr_addr(cur, src_index, left);
2402 rkp = xfs_btree_key_addr(cur, 1, right);
2403 rpp = xfs_btree_ptr_addr(cur, 1, right);
2404
2405#ifdef DEBUG
2406 for (i = src_index; i < rrecs; i++) {
2407 error = xfs_btree_check_ptr(cur, lpp, i, level);
2408 if (error)
2409 goto error0;
2410 }
2411#endif
2412
2413 xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2414 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2415
2416 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2417 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2418
2419
2420 xfs_btree_copy_keys(cur, key, rkp, 1);
2421 } else {
2422
2423 union xfs_btree_rec *lrp;
2424 union xfs_btree_rec *rrp;
2425
2426 lrp = xfs_btree_rec_addr(cur, src_index, left);
2427 rrp = xfs_btree_rec_addr(cur, 1, right);
2428
2429 xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2430 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2431
2432 cur->bc_ops->init_key_from_rec(key,
2433 xfs_btree_rec_addr(cur, 1, right));
2434 }
2435
2436
2437
2438
2439
2440
2441 xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2442 xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2443 xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2444 xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2445
2446 lrecs -= rrecs;
2447 xfs_btree_set_numrecs(left, lrecs);
2448 xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2449
2450 xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2451 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2452
2453
2454
2455
2456
2457 if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2458 error = xfs_btree_read_buf_block(cur, &rrptr, level,
2459 0, &rrblock, &rrbp);
2460 if (error)
2461 goto error0;
2462 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2463 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2464 }
2465
2466
2467
2468
2469
2470 if (cur->bc_ptrs[level] > lrecs + 1) {
2471 xfs_btree_setbuf(cur, level, rbp);
2472 cur->bc_ptrs[level] -= lrecs;
2473 }
2474
2475
2476
2477
2478 if (level + 1 < cur->bc_nlevels) {
2479 error = xfs_btree_dup_cursor(cur, curp);
2480 if (error)
2481 goto error0;
2482 (*curp)->bc_ptrs[level + 1]++;
2483 }
2484 *ptrp = rptr;
2485 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2486 *stat = 1;
2487 return 0;
2488out0:
2489 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2490 *stat = 0;
2491 return 0;
2492
2493error0:
2494 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2495 return error;
2496}
2497
2498
2499
2500
2501
2502int
2503xfs_btree_new_iroot(
2504 struct xfs_btree_cur *cur,
2505 int *logflags,
2506 int *stat)
2507{
2508 struct xfs_buf *cbp;
2509 struct xfs_btree_block *block;
2510 struct xfs_btree_block *cblock;
2511 union xfs_btree_key *ckp;
2512 union xfs_btree_ptr *cpp;
2513 union xfs_btree_key *kp;
2514 union xfs_btree_ptr *pp;
2515 union xfs_btree_ptr nptr;
2516 int level;
2517 int error;
2518#ifdef DEBUG
2519 int i;
2520#endif
2521
2522 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2523 XFS_BTREE_STATS_INC(cur, newroot);
2524
2525 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2526
2527 level = cur->bc_nlevels - 1;
2528
2529 block = xfs_btree_get_iroot(cur);
2530 pp = xfs_btree_ptr_addr(cur, 1, block);
2531
2532
2533 error = cur->bc_ops->alloc_block(cur, pp, &nptr, 1, stat);
2534 if (error)
2535 goto error0;
2536 if (*stat == 0) {
2537 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2538 return 0;
2539 }
2540 XFS_BTREE_STATS_INC(cur, alloc);
2541
2542
2543 error = xfs_btree_get_buf_block(cur, &nptr, 0, &cblock, &cbp);
2544 if (error)
2545 goto error0;
2546
2547
2548
2549
2550
2551 memcpy(cblock, block, xfs_btree_block_len(cur));
2552 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
2553 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
2554 cblock->bb_u.l.bb_blkno = cpu_to_be64(cbp->b_bn);
2555 else
2556 cblock->bb_u.s.bb_blkno = cpu_to_be64(cbp->b_bn);
2557 }
2558
2559 be16_add_cpu(&block->bb_level, 1);
2560 xfs_btree_set_numrecs(block, 1);
2561 cur->bc_nlevels++;
2562 cur->bc_ptrs[level + 1] = 1;
2563
2564 kp = xfs_btree_key_addr(cur, 1, block);
2565 ckp = xfs_btree_key_addr(cur, 1, cblock);
2566 xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
2567
2568 cpp = xfs_btree_ptr_addr(cur, 1, cblock);
2569#ifdef DEBUG
2570 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2571 error = xfs_btree_check_ptr(cur, pp, i, level);
2572 if (error)
2573 goto error0;
2574 }
2575#endif
2576 xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
2577
2578#ifdef DEBUG
2579 error = xfs_btree_check_ptr(cur, &nptr, 0, level);
2580 if (error)
2581 goto error0;
2582#endif
2583 xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
2584
2585 xfs_iroot_realloc(cur->bc_private.b.ip,
2586 1 - xfs_btree_get_numrecs(cblock),
2587 cur->bc_private.b.whichfork);
2588
2589 xfs_btree_setbuf(cur, level, cbp);
2590
2591
2592
2593
2594
2595 xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
2596 xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2597 xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2598
2599 *logflags |=
2600 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork);
2601 *stat = 1;
2602 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2603 return 0;
2604error0:
2605 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2606 return error;
2607}
2608
2609
2610
2611
2612STATIC int
2613xfs_btree_new_root(
2614 struct xfs_btree_cur *cur,
2615 int *stat)
2616{
2617 struct xfs_btree_block *block;
2618 struct xfs_buf *bp;
2619 int error;
2620 struct xfs_buf *lbp;
2621 struct xfs_btree_block *left;
2622 struct xfs_buf *nbp;
2623 struct xfs_btree_block *new;
2624 int nptr;
2625 struct xfs_buf *rbp;
2626 struct xfs_btree_block *right;
2627 union xfs_btree_ptr rptr;
2628 union xfs_btree_ptr lptr;
2629
2630 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2631 XFS_BTREE_STATS_INC(cur, newroot);
2632
2633
2634 cur->bc_ops->init_ptr_from_cur(cur, &rptr);
2635
2636
2637 error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, 1, stat);
2638 if (error)
2639 goto error0;
2640 if (*stat == 0)
2641 goto out0;
2642 XFS_BTREE_STATS_INC(cur, alloc);
2643
2644
2645 error = xfs_btree_get_buf_block(cur, &lptr, 0, &new, &nbp);
2646 if (error)
2647 goto error0;
2648
2649
2650 cur->bc_ops->set_root(cur, &lptr, 1);
2651
2652
2653
2654
2655
2656
2657
2658 block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
2659
2660#ifdef DEBUG
2661 error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
2662 if (error)
2663 goto error0;
2664#endif
2665
2666 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
2667 if (!xfs_btree_ptr_is_null(cur, &rptr)) {
2668
2669 lbp = bp;
2670 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2671 left = block;
2672 error = xfs_btree_read_buf_block(cur, &rptr,
2673 cur->bc_nlevels - 1, 0, &right, &rbp);
2674 if (error)
2675 goto error0;
2676 bp = rbp;
2677 nptr = 1;
2678 } else {
2679
2680 rbp = bp;
2681 xfs_btree_buf_to_ptr(cur, rbp, &rptr);
2682 right = block;
2683 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2684 error = xfs_btree_read_buf_block(cur, &lptr,
2685 cur->bc_nlevels - 1, 0, &left, &lbp);
2686 if (error)
2687 goto error0;
2688 bp = lbp;
2689 nptr = 2;
2690 }
2691
2692 xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);
2693 xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
2694 ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
2695 !xfs_btree_ptr_is_null(cur, &rptr));
2696
2697
2698 if (xfs_btree_get_level(left) > 0) {
2699 xfs_btree_copy_keys(cur,
2700 xfs_btree_key_addr(cur, 1, new),
2701 xfs_btree_key_addr(cur, 1, left), 1);
2702 xfs_btree_copy_keys(cur,
2703 xfs_btree_key_addr(cur, 2, new),
2704 xfs_btree_key_addr(cur, 1, right), 1);
2705 } else {
2706 cur->bc_ops->init_key_from_rec(
2707 xfs_btree_key_addr(cur, 1, new),
2708 xfs_btree_rec_addr(cur, 1, left));
2709 cur->bc_ops->init_key_from_rec(
2710 xfs_btree_key_addr(cur, 2, new),
2711 xfs_btree_rec_addr(cur, 1, right));
2712 }
2713 xfs_btree_log_keys(cur, nbp, 1, 2);
2714
2715
2716 xfs_btree_copy_ptrs(cur,
2717 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
2718 xfs_btree_copy_ptrs(cur,
2719 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
2720 xfs_btree_log_ptrs(cur, nbp, 1, 2);
2721
2722
2723 xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
2724 cur->bc_ptrs[cur->bc_nlevels] = nptr;
2725 cur->bc_nlevels++;
2726 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2727 *stat = 1;
2728 return 0;
2729error0:
2730 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2731 return error;
2732out0:
2733 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2734 *stat = 0;
2735 return 0;
2736}
2737
2738STATIC int
2739xfs_btree_make_block_unfull(
2740 struct xfs_btree_cur *cur,
2741 int level,
2742 int numrecs,
2743 int *oindex,
2744 int *index,
2745 union xfs_btree_ptr *nptr,
2746 struct xfs_btree_cur **ncur,
2747 union xfs_btree_rec *nrec,
2748 int *stat)
2749{
2750 union xfs_btree_key key;
2751 int error = 0;
2752
2753 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2754 level == cur->bc_nlevels - 1) {
2755 struct xfs_inode *ip = cur->bc_private.b.ip;
2756
2757 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
2758
2759
2760 xfs_iroot_realloc(ip, 1, cur->bc_private.b.whichfork);
2761 } else {
2762
2763 int logflags = 0;
2764
2765 error = xfs_btree_new_iroot(cur, &logflags, stat);
2766 if (error || *stat == 0)
2767 return error;
2768
2769 xfs_trans_log_inode(cur->bc_tp, ip, logflags);
2770 }
2771
2772 return 0;
2773 }
2774
2775
2776 error = xfs_btree_rshift(cur, level, stat);
2777 if (error || *stat)
2778 return error;
2779
2780
2781 error = xfs_btree_lshift(cur, level, stat);
2782 if (error)
2783 return error;
2784
2785 if (*stat) {
2786 *oindex = *index = cur->bc_ptrs[level];
2787 return 0;
2788 }
2789
2790
2791
2792
2793
2794
2795
2796 error = xfs_btree_split(cur, level, nptr, &key, ncur, stat);
2797 if (error || *stat == 0)
2798 return error;
2799
2800
2801 *index = cur->bc_ptrs[level];
2802 cur->bc_ops->init_rec_from_key(&key, nrec);
2803 return 0;
2804}
2805
2806
2807
2808
2809
2810STATIC int
2811xfs_btree_insrec(
2812 struct xfs_btree_cur *cur,
2813 int level,
2814 union xfs_btree_ptr *ptrp,
2815 union xfs_btree_rec *recp,
2816 struct xfs_btree_cur **curp,
2817 int *stat)
2818{
2819 struct xfs_btree_block *block;
2820 struct xfs_buf *bp;
2821 union xfs_btree_key key;
2822 union xfs_btree_ptr nptr;
2823 struct xfs_btree_cur *ncur;
2824 union xfs_btree_rec nrec;
2825 int optr;
2826 int ptr;
2827 int numrecs;
2828 int error;
2829#ifdef DEBUG
2830 int i;
2831#endif
2832
2833 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2834 XFS_BTREE_TRACE_ARGIPR(cur, level, *ptrp, recp);
2835
2836 ncur = NULL;
2837
2838
2839
2840
2841
2842 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2843 (level >= cur->bc_nlevels)) {
2844 error = xfs_btree_new_root(cur, stat);
2845 xfs_btree_set_ptr_null(cur, ptrp);
2846
2847 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2848 return error;
2849 }
2850
2851
2852 ptr = cur->bc_ptrs[level];
2853 if (ptr == 0) {
2854 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2855 *stat = 0;
2856 return 0;
2857 }
2858
2859
2860 cur->bc_ops->init_key_from_rec(&key, recp);
2861
2862 optr = ptr;
2863
2864 XFS_BTREE_STATS_INC(cur, insrec);
2865
2866
2867 block = xfs_btree_get_block(cur, level, &bp);
2868 numrecs = xfs_btree_get_numrecs(block);
2869
2870#ifdef DEBUG
2871 error = xfs_btree_check_block(cur, block, level, bp);
2872 if (error)
2873 goto error0;
2874
2875
2876 if (ptr <= numrecs) {
2877 if (level == 0) {
2878 ASSERT(cur->bc_ops->recs_inorder(cur, recp,
2879 xfs_btree_rec_addr(cur, ptr, block)));
2880 } else {
2881 ASSERT(cur->bc_ops->keys_inorder(cur, &key,
2882 xfs_btree_key_addr(cur, ptr, block)));
2883 }
2884 }
2885#endif
2886
2887
2888
2889
2890
2891 xfs_btree_set_ptr_null(cur, &nptr);
2892 if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
2893 error = xfs_btree_make_block_unfull(cur, level, numrecs,
2894 &optr, &ptr, &nptr, &ncur, &nrec, stat);
2895 if (error || *stat == 0)
2896 goto error0;
2897 }
2898
2899
2900
2901
2902
2903 block = xfs_btree_get_block(cur, level, &bp);
2904 numrecs = xfs_btree_get_numrecs(block);
2905
2906#ifdef DEBUG
2907 error = xfs_btree_check_block(cur, block, level, bp);
2908 if (error)
2909 return error;
2910#endif
2911
2912
2913
2914
2915
2916 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
2917
2918 if (level > 0) {
2919
2920 union xfs_btree_key *kp;
2921 union xfs_btree_ptr *pp;
2922
2923 kp = xfs_btree_key_addr(cur, ptr, block);
2924 pp = xfs_btree_ptr_addr(cur, ptr, block);
2925
2926#ifdef DEBUG
2927 for (i = numrecs - ptr; i >= 0; i--) {
2928 error = xfs_btree_check_ptr(cur, pp, i, level);
2929 if (error)
2930 return error;
2931 }
2932#endif
2933
2934 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
2935 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
2936
2937#ifdef DEBUG
2938 error = xfs_btree_check_ptr(cur, ptrp, 0, level);
2939 if (error)
2940 goto error0;
2941#endif
2942
2943
2944 xfs_btree_copy_keys(cur, kp, &key, 1);
2945 xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
2946 numrecs++;
2947 xfs_btree_set_numrecs(block, numrecs);
2948 xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
2949 xfs_btree_log_keys(cur, bp, ptr, numrecs);
2950#ifdef DEBUG
2951 if (ptr < numrecs) {
2952 ASSERT(cur->bc_ops->keys_inorder(cur, kp,
2953 xfs_btree_key_addr(cur, ptr + 1, block)));
2954 }
2955#endif
2956 } else {
2957
2958 union xfs_btree_rec *rp;
2959
2960 rp = xfs_btree_rec_addr(cur, ptr, block);
2961
2962 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
2963
2964
2965 xfs_btree_copy_recs(cur, rp, recp, 1);
2966 xfs_btree_set_numrecs(block, ++numrecs);
2967 xfs_btree_log_recs(cur, bp, ptr, numrecs);
2968#ifdef DEBUG
2969 if (ptr < numrecs) {
2970 ASSERT(cur->bc_ops->recs_inorder(cur, rp,
2971 xfs_btree_rec_addr(cur, ptr + 1, block)));
2972 }
2973#endif
2974 }
2975
2976
2977 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
2978
2979
2980 if (optr == 1) {
2981 error = xfs_btree_updkey(cur, &key, level + 1);
2982 if (error)
2983 goto error0;
2984 }
2985
2986
2987
2988
2989
2990 if (xfs_btree_is_lastrec(cur, block, level)) {
2991 cur->bc_ops->update_lastrec(cur, block, recp,
2992 ptr, LASTREC_INSREC);
2993 }
2994
2995
2996
2997
2998
2999 *ptrp = nptr;
3000 if (!xfs_btree_ptr_is_null(cur, &nptr)) {
3001 *recp = nrec;
3002 *curp = ncur;
3003 }
3004
3005 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3006 *stat = 1;
3007 return 0;
3008
3009error0:
3010 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3011 return error;
3012}
3013
3014
3015
3016
3017
3018
3019
3020
3021int
3022xfs_btree_insert(
3023 struct xfs_btree_cur *cur,
3024 int *stat)
3025{
3026 int error;
3027 int i;
3028 int level;
3029 union xfs_btree_ptr nptr;
3030 struct xfs_btree_cur *ncur;
3031 struct xfs_btree_cur *pcur;
3032 union xfs_btree_rec rec;
3033
3034 level = 0;
3035 ncur = NULL;
3036 pcur = cur;
3037
3038 xfs_btree_set_ptr_null(cur, &nptr);
3039 cur->bc_ops->init_rec_from_cur(cur, &rec);
3040
3041
3042
3043
3044
3045
3046 do {
3047
3048
3049
3050
3051 error = xfs_btree_insrec(pcur, level, &nptr, &rec, &ncur, &i);
3052 if (error) {
3053 if (pcur != cur)
3054 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
3055 goto error0;
3056 }
3057
3058 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3059 level++;
3060
3061
3062
3063
3064
3065
3066 if (pcur != cur &&
3067 (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
3068
3069 if (cur->bc_ops->update_cursor)
3070 cur->bc_ops->update_cursor(pcur, cur);
3071 cur->bc_nlevels = pcur->bc_nlevels;
3072 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
3073 }
3074
3075 if (ncur) {
3076 pcur = ncur;
3077 ncur = NULL;
3078 }
3079 } while (!xfs_btree_ptr_is_null(cur, &nptr));
3080
3081 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3082 *stat = i;
3083 return 0;
3084error0:
3085 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3086 return error;
3087}
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097STATIC int
3098xfs_btree_kill_iroot(
3099 struct xfs_btree_cur *cur)
3100{
3101 int whichfork = cur->bc_private.b.whichfork;
3102 struct xfs_inode *ip = cur->bc_private.b.ip;
3103 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork);
3104 struct xfs_btree_block *block;
3105 struct xfs_btree_block *cblock;
3106 union xfs_btree_key *kp;
3107 union xfs_btree_key *ckp;
3108 union xfs_btree_ptr *pp;
3109 union xfs_btree_ptr *cpp;
3110 struct xfs_buf *cbp;
3111 int level;
3112 int index;
3113 int numrecs;
3114#ifdef DEBUG
3115 union xfs_btree_ptr ptr;
3116 int i;
3117#endif
3118
3119 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3120
3121 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
3122 ASSERT(cur->bc_nlevels > 1);
3123
3124
3125
3126
3127
3128 level = cur->bc_nlevels - 1;
3129 if (level == 1)
3130 goto out0;
3131
3132
3133
3134
3135 block = xfs_btree_get_iroot(cur);
3136 if (xfs_btree_get_numrecs(block) != 1)
3137 goto out0;
3138
3139 cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3140 numrecs = xfs_btree_get_numrecs(cblock);
3141
3142
3143
3144
3145
3146
3147 if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3148 goto out0;
3149
3150 XFS_BTREE_STATS_INC(cur, killroot);
3151
3152#ifdef DEBUG
3153 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3154 ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3155 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3156 ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3157#endif
3158
3159 index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3160 if (index) {
3161 xfs_iroot_realloc(cur->bc_private.b.ip, index,
3162 cur->bc_private.b.whichfork);
3163 block = ifp->if_broot;
3164 }
3165
3166 be16_add_cpu(&block->bb_numrecs, index);
3167 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3168
3169 kp = xfs_btree_key_addr(cur, 1, block);
3170 ckp = xfs_btree_key_addr(cur, 1, cblock);
3171 xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3172
3173 pp = xfs_btree_ptr_addr(cur, 1, block);
3174 cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3175#ifdef DEBUG
3176 for (i = 0; i < numrecs; i++) {
3177 int error;
3178
3179 error = xfs_btree_check_ptr(cur, cpp, i, level - 1);
3180 if (error) {
3181 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3182 return error;
3183 }
3184 }
3185#endif
3186 xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3187
3188 cur->bc_ops->free_block(cur, cbp);
3189 XFS_BTREE_STATS_INC(cur, free);
3190
3191 cur->bc_bufs[level - 1] = NULL;
3192 be16_add_cpu(&block->bb_level, -1);
3193 xfs_trans_log_inode(cur->bc_tp, ip,
3194 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_private.b.whichfork));
3195 cur->bc_nlevels--;
3196out0:
3197 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3198 return 0;
3199}
3200
3201
3202
3203
3204STATIC int
3205xfs_btree_kill_root(
3206 struct xfs_btree_cur *cur,
3207 struct xfs_buf *bp,
3208 int level,
3209 union xfs_btree_ptr *newroot)
3210{
3211 int error;
3212
3213 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3214 XFS_BTREE_STATS_INC(cur, killroot);
3215
3216
3217
3218
3219
3220 cur->bc_ops->set_root(cur, newroot, -1);
3221
3222 error = cur->bc_ops->free_block(cur, bp);
3223 if (error) {
3224 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3225 return error;
3226 }
3227
3228 XFS_BTREE_STATS_INC(cur, free);
3229
3230 cur->bc_bufs[level] = NULL;
3231 cur->bc_ra[level] = 0;
3232 cur->bc_nlevels--;
3233
3234 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3235 return 0;
3236}
3237
3238STATIC int
3239xfs_btree_dec_cursor(
3240 struct xfs_btree_cur *cur,
3241 int level,
3242 int *stat)
3243{
3244 int error;
3245 int i;
3246
3247 if (level > 0) {
3248 error = xfs_btree_decrement(cur, level, &i);
3249 if (error)
3250 return error;
3251 }
3252
3253 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3254 *stat = 1;
3255 return 0;
3256}
3257
3258
3259
3260
3261
3262
3263
3264STATIC int
3265xfs_btree_delrec(
3266 struct xfs_btree_cur *cur,
3267 int level,
3268 int *stat)
3269{
3270 struct xfs_btree_block *block;
3271 union xfs_btree_ptr cptr;
3272 struct xfs_buf *bp;
3273 int error;
3274 int i;
3275 union xfs_btree_key key;
3276 union xfs_btree_key *keyp = &key;
3277 union xfs_btree_ptr lptr;
3278 struct xfs_buf *lbp;
3279 struct xfs_btree_block *left;
3280 int lrecs = 0;
3281 int ptr;
3282 union xfs_btree_ptr rptr;
3283 struct xfs_buf *rbp;
3284 struct xfs_btree_block *right;
3285 struct xfs_btree_block *rrblock;
3286 struct xfs_buf *rrbp;
3287 int rrecs = 0;
3288 struct xfs_btree_cur *tcur;
3289 int numrecs;
3290
3291 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3292 XFS_BTREE_TRACE_ARGI(cur, level);
3293
3294 tcur = NULL;
3295
3296
3297 ptr = cur->bc_ptrs[level];
3298 if (ptr == 0) {
3299 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3300 *stat = 0;
3301 return 0;
3302 }
3303
3304
3305 block = xfs_btree_get_block(cur, level, &bp);
3306 numrecs = xfs_btree_get_numrecs(block);
3307
3308#ifdef DEBUG
3309 error = xfs_btree_check_block(cur, block, level, bp);
3310 if (error)
3311 goto error0;
3312#endif
3313
3314
3315 if (ptr > numrecs) {
3316 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3317 *stat = 0;
3318 return 0;
3319 }
3320
3321 XFS_BTREE_STATS_INC(cur, delrec);
3322 XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3323
3324
3325 if (level > 0) {
3326
3327 union xfs_btree_key *lkp;
3328 union xfs_btree_ptr *lpp;
3329
3330 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3331 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3332
3333#ifdef DEBUG
3334 for (i = 0; i < numrecs - ptr; i++) {
3335 error = xfs_btree_check_ptr(cur, lpp, i, level);
3336 if (error)
3337 goto error0;
3338 }
3339#endif
3340
3341 if (ptr < numrecs) {
3342 xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3343 xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3344 xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3345 xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3346 }
3347
3348
3349
3350
3351
3352 if (ptr == 1)
3353 keyp = xfs_btree_key_addr(cur, 1, block);
3354 } else {
3355
3356 if (ptr < numrecs) {
3357 xfs_btree_shift_recs(cur,
3358 xfs_btree_rec_addr(cur, ptr + 1, block),
3359 -1, numrecs - ptr);
3360 xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3361 }
3362
3363
3364
3365
3366
3367 if (ptr == 1) {
3368 cur->bc_ops->init_key_from_rec(&key,
3369 xfs_btree_rec_addr(cur, 1, block));
3370 keyp = &key;
3371 }
3372 }
3373
3374
3375
3376
3377 xfs_btree_set_numrecs(block, --numrecs);
3378 xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3379
3380
3381
3382
3383
3384 if (xfs_btree_is_lastrec(cur, block, level)) {
3385 cur->bc_ops->update_lastrec(cur, block, NULL,
3386 ptr, LASTREC_DELREC);
3387 }
3388
3389
3390
3391
3392
3393
3394 if (level == cur->bc_nlevels - 1) {
3395 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3396 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
3397 cur->bc_private.b.whichfork);
3398
3399 error = xfs_btree_kill_iroot(cur);
3400 if (error)
3401 goto error0;
3402
3403 error = xfs_btree_dec_cursor(cur, level, stat);
3404 if (error)
3405 goto error0;
3406 *stat = 1;
3407 return 0;
3408 }
3409
3410
3411
3412
3413
3414
3415 if (numrecs == 1 && level > 0) {
3416 union xfs_btree_ptr *pp;
3417
3418
3419
3420
3421 pp = xfs_btree_ptr_addr(cur, 1, block);
3422 error = xfs_btree_kill_root(cur, bp, level, pp);
3423 if (error)
3424 goto error0;
3425 } else if (level > 0) {
3426 error = xfs_btree_dec_cursor(cur, level, stat);
3427 if (error)
3428 goto error0;
3429 }
3430 *stat = 1;
3431 return 0;
3432 }
3433
3434
3435
3436
3437
3438 if (ptr == 1) {
3439 error = xfs_btree_updkey(cur, keyp, level + 1);
3440 if (error)
3441 goto error0;
3442 }
3443
3444
3445
3446
3447
3448 if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3449 error = xfs_btree_dec_cursor(cur, level, stat);
3450 if (error)
3451 goto error0;
3452 return 0;
3453 }
3454
3455
3456
3457
3458
3459
3460 xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3461 xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3462
3463 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3464
3465
3466
3467
3468
3469 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3470 xfs_btree_ptr_is_null(cur, &lptr) &&
3471 level == cur->bc_nlevels - 2) {
3472 error = xfs_btree_kill_iroot(cur);
3473 if (!error)
3474 error = xfs_btree_dec_cursor(cur, level, stat);
3475 if (error)
3476 goto error0;
3477 return 0;
3478 }
3479 }
3480
3481 ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3482 !xfs_btree_ptr_is_null(cur, &lptr));
3483
3484
3485
3486
3487
3488 error = xfs_btree_dup_cursor(cur, &tcur);
3489 if (error)
3490 goto error0;
3491
3492
3493
3494
3495
3496 if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3497
3498
3499
3500
3501 i = xfs_btree_lastrec(tcur, level);
3502 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3503
3504 error = xfs_btree_increment(tcur, level, &i);
3505 if (error)
3506 goto error0;
3507 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3508
3509 i = xfs_btree_lastrec(tcur, level);
3510 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3511
3512
3513 right = xfs_btree_get_block(tcur, level, &rbp);
3514#ifdef DEBUG
3515 error = xfs_btree_check_block(tcur, right, level, rbp);
3516 if (error)
3517 goto error0;
3518#endif
3519
3520 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3521
3522
3523
3524
3525
3526
3527 if (xfs_btree_get_numrecs(right) - 1 >=
3528 cur->bc_ops->get_minrecs(tcur, level)) {
3529 error = xfs_btree_lshift(tcur, level, &i);
3530 if (error)
3531 goto error0;
3532 if (i) {
3533 ASSERT(xfs_btree_get_numrecs(block) >=
3534 cur->bc_ops->get_minrecs(tcur, level));
3535
3536 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3537 tcur = NULL;
3538
3539 error = xfs_btree_dec_cursor(cur, level, stat);
3540 if (error)
3541 goto error0;
3542 return 0;
3543 }
3544 }
3545
3546
3547
3548
3549
3550
3551 rrecs = xfs_btree_get_numrecs(right);
3552 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3553 i = xfs_btree_firstrec(tcur, level);
3554 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3555
3556 error = xfs_btree_decrement(tcur, level, &i);
3557 if (error)
3558 goto error0;
3559 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3560 }
3561 }
3562
3563
3564
3565
3566
3567 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3568
3569
3570
3571
3572 i = xfs_btree_firstrec(tcur, level);
3573 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3574
3575 error = xfs_btree_decrement(tcur, level, &i);
3576 if (error)
3577 goto error0;
3578 i = xfs_btree_firstrec(tcur, level);
3579 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3580
3581
3582 left = xfs_btree_get_block(tcur, level, &lbp);
3583#ifdef DEBUG
3584 error = xfs_btree_check_block(cur, left, level, lbp);
3585 if (error)
3586 goto error0;
3587#endif
3588
3589 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
3590
3591
3592
3593
3594
3595
3596 if (xfs_btree_get_numrecs(left) - 1 >=
3597 cur->bc_ops->get_minrecs(tcur, level)) {
3598 error = xfs_btree_rshift(tcur, level, &i);
3599 if (error)
3600 goto error0;
3601 if (i) {
3602 ASSERT(xfs_btree_get_numrecs(block) >=
3603 cur->bc_ops->get_minrecs(tcur, level));
3604 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3605 tcur = NULL;
3606 if (level == 0)
3607 cur->bc_ptrs[0]++;
3608 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3609 *stat = 1;
3610 return 0;
3611 }
3612 }
3613
3614
3615
3616
3617
3618 lrecs = xfs_btree_get_numrecs(left);
3619 }
3620
3621
3622 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3623 tcur = NULL;
3624
3625
3626 ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
3627
3628 if (!xfs_btree_ptr_is_null(cur, &lptr) &&
3629 lrecs + xfs_btree_get_numrecs(block) <=
3630 cur->bc_ops->get_maxrecs(cur, level)) {
3631
3632
3633
3634
3635 rptr = cptr;
3636 right = block;
3637 rbp = bp;
3638 error = xfs_btree_read_buf_block(cur, &lptr, level,
3639 0, &left, &lbp);
3640 if (error)
3641 goto error0;
3642
3643
3644
3645
3646 } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
3647 rrecs + xfs_btree_get_numrecs(block) <=
3648 cur->bc_ops->get_maxrecs(cur, level)) {
3649
3650
3651
3652
3653 lptr = cptr;
3654 left = block;
3655 lbp = bp;
3656 error = xfs_btree_read_buf_block(cur, &rptr, level,
3657 0, &right, &rbp);
3658 if (error)
3659 goto error0;
3660
3661
3662
3663
3664
3665 } else {
3666 error = xfs_btree_dec_cursor(cur, level, stat);
3667 if (error)
3668 goto error0;
3669 return 0;
3670 }
3671
3672 rrecs = xfs_btree_get_numrecs(right);
3673 lrecs = xfs_btree_get_numrecs(left);
3674
3675
3676
3677
3678
3679 XFS_BTREE_STATS_ADD(cur, moves, rrecs);
3680 if (level > 0) {
3681
3682 union xfs_btree_key *lkp;
3683 union xfs_btree_ptr *lpp;
3684 union xfs_btree_key *rkp;
3685 union xfs_btree_ptr *rpp;
3686
3687 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
3688 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
3689 rkp = xfs_btree_key_addr(cur, 1, right);
3690 rpp = xfs_btree_ptr_addr(cur, 1, right);
3691#ifdef DEBUG
3692 for (i = 1; i < rrecs; i++) {
3693 error = xfs_btree_check_ptr(cur, rpp, i, level);
3694 if (error)
3695 goto error0;
3696 }
3697#endif
3698 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
3699 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
3700
3701 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
3702 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
3703 } else {
3704
3705 union xfs_btree_rec *lrp;
3706 union xfs_btree_rec *rrp;
3707
3708 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
3709 rrp = xfs_btree_rec_addr(cur, 1, right);
3710
3711 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
3712 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
3713 }
3714
3715 XFS_BTREE_STATS_INC(cur, join);
3716
3717
3718
3719
3720
3721 xfs_btree_set_numrecs(left, lrecs + rrecs);
3722 xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB),
3723 xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3724 xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
3725
3726
3727 xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3728 if (!xfs_btree_ptr_is_null(cur, &cptr)) {
3729 error = xfs_btree_read_buf_block(cur, &cptr, level,
3730 0, &rrblock, &rrbp);
3731 if (error)
3732 goto error0;
3733 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
3734 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
3735 }
3736
3737
3738 error = cur->bc_ops->free_block(cur, rbp);
3739 if (error)
3740 goto error0;
3741 XFS_BTREE_STATS_INC(cur, free);
3742
3743
3744
3745
3746
3747 if (bp != lbp) {
3748 cur->bc_bufs[level] = lbp;
3749 cur->bc_ptrs[level] += lrecs;
3750 cur->bc_ra[level] = 0;
3751 }
3752
3753
3754
3755
3756 else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
3757 (level + 1 < cur->bc_nlevels)) {
3758 error = xfs_btree_increment(cur, level + 1, &i);
3759 if (error)
3760 goto error0;
3761 }
3762
3763
3764
3765
3766
3767
3768
3769 if (level > 0)
3770 cur->bc_ptrs[level]--;
3771
3772 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3773
3774 *stat = 2;
3775 return 0;
3776
3777error0:
3778 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3779 if (tcur)
3780 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
3781 return error;
3782}
3783
3784
3785
3786
3787
3788
3789int
3790xfs_btree_delete(
3791 struct xfs_btree_cur *cur,
3792 int *stat)
3793{
3794 int error;
3795 int level;
3796 int i;
3797
3798 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3799
3800
3801
3802
3803
3804
3805
3806 for (level = 0, i = 2; i == 2; level++) {
3807 error = xfs_btree_delrec(cur, level, &i);
3808 if (error)
3809 goto error0;
3810 }
3811
3812 if (i == 0) {
3813 for (level = 1; level < cur->bc_nlevels; level++) {
3814 if (cur->bc_ptrs[level] == 0) {
3815 error = xfs_btree_decrement(cur, level, &i);
3816 if (error)
3817 goto error0;
3818 break;
3819 }
3820 }
3821 }
3822
3823 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3824 *stat = i;
3825 return 0;
3826error0:
3827 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3828 return error;
3829}
3830
3831
3832
3833
3834int
3835xfs_btree_get_rec(
3836 struct xfs_btree_cur *cur,
3837 union xfs_btree_rec **recp,
3838 int *stat)
3839{
3840 struct xfs_btree_block *block;
3841 struct xfs_buf *bp;
3842 int ptr;
3843#ifdef DEBUG
3844 int error;
3845#endif
3846
3847 ptr = cur->bc_ptrs[0];
3848 block = xfs_btree_get_block(cur, 0, &bp);
3849
3850#ifdef DEBUG
3851 error = xfs_btree_check_block(cur, block, 0, bp);
3852 if (error)
3853 return error;
3854#endif
3855
3856
3857
3858
3859 if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
3860 *stat = 0;
3861 return 0;
3862 }
3863
3864
3865
3866
3867 *recp = xfs_btree_rec_addr(cur, ptr, block);
3868 *stat = 1;
3869 return 0;
3870}
3871