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