Merge /spare/repo/linux-2.6/
[linux-2.6] / fs / xfs / xfs_bmap_btree.c
1 /*
2  * Copyright (c) 2000-2003 Silicon Graphics, Inc.  All Rights Reserved.
3  *
4  * This program is free software; you can redistribute it and/or modify it
5  * under the terms of version 2 of the GNU General Public License as
6  * published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it would be useful, but
9  * WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
11  *
12  * Further, this software is distributed without any warranty that it is
13  * free of the rightful claim of any third person regarding infringement
14  * or the like.  Any license provided herein, whether implied or
15  * otherwise, applies only to this software file.  Patent licenses, if
16  * any, provided herein do not apply to combinations of this program with
17  * other software, or any other product whatsoever.
18  *
19  * You should have received a copy of the GNU General Public License along
20  * with this program; if not, write the Free Software Foundation, Inc., 59
21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
22  *
23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24  * Mountain View, CA  94043, or:
25  *
26  * http://www.sgi.com
27  *
28  * For further information regarding this notice, see:
29  *
30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
31  */
32
33 #include "xfs.h"
34
35 #include "xfs_macros.h"
36 #include "xfs_types.h"
37 #include "xfs_inum.h"
38 #include "xfs_log.h"
39 #include "xfs_trans.h"
40 #include "xfs_sb.h"
41 #include "xfs_ag.h"
42 #include "xfs_dir.h"
43 #include "xfs_dir2.h"
44 #include "xfs_dmapi.h"
45 #include "xfs_mount.h"
46 #include "xfs_alloc_btree.h"
47 #include "xfs_bmap_btree.h"
48 #include "xfs_ialloc_btree.h"
49 #include "xfs_btree.h"
50 #include "xfs_ialloc.h"
51 #include "xfs_itable.h"
52 #include "xfs_attr_sf.h"
53 #include "xfs_dir_sf.h"
54 #include "xfs_dir2_sf.h"
55 #include "xfs_dinode.h"
56 #include "xfs_inode_item.h"
57 #include "xfs_inode.h"
58 #include "xfs_alloc.h"
59 #include "xfs_bit.h"
60 #include "xfs_bmap.h"
61 #include "xfs_error.h"
62 #include "xfs_quota.h"
63
64 #if defined(XFS_BMBT_TRACE)
65 ktrace_t        *xfs_bmbt_trace_buf;
66 #endif
67
68 /*
69  * Prototypes for internal btree functions.
70  */
71
72
73 STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
74 STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
75 STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
76 STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
77 STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
78 STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
79                 xfs_bmbt_key_t *, xfs_btree_cur_t **, int *);
80 STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);
81
82
83 #if defined(XFS_BMBT_TRACE)
84
85 static char     ARGS[] = "args";
86 static char     ENTRY[] = "entry";
87 static char     ERROR[] = "error";
88 #undef EXIT
89 static char     EXIT[] = "exit";
90
91 /*
92  * Add a trace buffer entry for the arguments given to the routine,
93  * generic form.
94  */
95 STATIC void
96 xfs_bmbt_trace_enter(
97         char            *func,
98         xfs_btree_cur_t *cur,
99         char            *s,
100         int             type,
101         int             line,
102         __psunsigned_t  a0,
103         __psunsigned_t  a1,
104         __psunsigned_t  a2,
105         __psunsigned_t  a3,
106         __psunsigned_t  a4,
107         __psunsigned_t  a5,
108         __psunsigned_t  a6,
109         __psunsigned_t  a7,
110         __psunsigned_t  a8,
111         __psunsigned_t  a9,
112         __psunsigned_t  a10)
113 {
114         xfs_inode_t     *ip;
115         int             whichfork;
116
117         ip = cur->bc_private.b.ip;
118         whichfork = cur->bc_private.b.whichfork;
119         ktrace_enter(xfs_bmbt_trace_buf,
120                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
121                 (void *)func, (void *)s, (void *)ip, (void *)cur,
122                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
123                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
124                 (void *)a8, (void *)a9, (void *)a10);
125         ASSERT(ip->i_btrace);
126         ktrace_enter(ip->i_btrace,
127                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
128                 (void *)func, (void *)s, (void *)ip, (void *)cur,
129                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
130                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
131                 (void *)a8, (void *)a9, (void *)a10);
132 }
133 /*
134  * Add a trace buffer entry for arguments, for a buffer & 1 integer arg.
135  */
136 STATIC void
137 xfs_bmbt_trace_argbi(
138         char            *func,
139         xfs_btree_cur_t *cur,
140         xfs_buf_t       *b,
141         int             i,
142         int             line)
143 {
144         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBI, line,
145                 (__psunsigned_t)b, i, 0, 0,
146                 0, 0, 0, 0,
147                 0, 0, 0);
148 }
149
150 /*
151  * Add a trace buffer entry for arguments, for a buffer & 2 integer args.
152  */
153 STATIC void
154 xfs_bmbt_trace_argbii(
155         char            *func,
156         xfs_btree_cur_t *cur,
157         xfs_buf_t       *b,
158         int             i0,
159         int             i1,
160         int             line)
161 {
162         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBII, line,
163                 (__psunsigned_t)b, i0, i1, 0,
164                 0, 0, 0, 0,
165                 0, 0, 0);
166 }
167
168 /*
169  * Add a trace buffer entry for arguments, for 3 block-length args
170  * and an integer arg.
171  */
172 STATIC void
173 xfs_bmbt_trace_argfffi(
174         char                    *func,
175         xfs_btree_cur_t         *cur,
176         xfs_dfiloff_t           o,
177         xfs_dfsbno_t            b,
178         xfs_dfilblks_t          i,
179         int                     j,
180         int                     line)
181 {
182         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGFFFI, line,
183                 o >> 32, (int)o, b >> 32, (int)b,
184                 i >> 32, (int)i, (int)j, 0,
185                 0, 0, 0);
186 }
187
188 /*
189  * Add a trace buffer entry for arguments, for one integer arg.
190  */
191 STATIC void
192 xfs_bmbt_trace_argi(
193         char            *func,
194         xfs_btree_cur_t *cur,
195         int             i,
196         int             line)
197 {
198         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGI, line,
199                 i, 0, 0, 0,
200                 0, 0, 0, 0,
201                 0, 0, 0);
202 }
203
204 /*
205  * Add a trace buffer entry for arguments, for int, fsblock, key.
206  */
207 STATIC void
208 xfs_bmbt_trace_argifk(
209         char                    *func,
210         xfs_btree_cur_t         *cur,
211         int                     i,
212         xfs_fsblock_t           f,
213         xfs_bmbt_key_t          *k,
214         int                     line)
215 {
216         xfs_dfsbno_t            d;
217         xfs_dfiloff_t           o;
218
219         d = (xfs_dfsbno_t)f;
220         o = INT_GET(k->br_startoff, ARCH_CONVERT);
221         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
222                 i, d >> 32, (int)d, o >> 32,
223                 (int)o, 0, 0, 0,
224                 0, 0, 0);
225 }
226
227 /*
228  * Add a trace buffer entry for arguments, for int, fsblock, rec.
229  */
230 STATIC void
231 xfs_bmbt_trace_argifr(
232         char                    *func,
233         xfs_btree_cur_t         *cur,
234         int                     i,
235         xfs_fsblock_t           f,
236         xfs_bmbt_rec_t          *r,
237         int                     line)
238 {
239         xfs_dfsbno_t            b;
240         xfs_dfilblks_t          c;
241         xfs_dfsbno_t            d;
242         xfs_dfiloff_t           o;
243         xfs_bmbt_irec_t         s;
244
245         d = (xfs_dfsbno_t)f;
246         xfs_bmbt_disk_get_all(r, &s);
247         o = (xfs_dfiloff_t)s.br_startoff;
248         b = (xfs_dfsbno_t)s.br_startblock;
249         c = s.br_blockcount;
250         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFR, line,
251                 i, d >> 32, (int)d, o >> 32,
252                 (int)o, b >> 32, (int)b, c >> 32,
253                 (int)c, 0, 0);
254 }
255
256 /*
257  * Add a trace buffer entry for arguments, for int, key.
258  */
259 STATIC void
260 xfs_bmbt_trace_argik(
261         char                    *func,
262         xfs_btree_cur_t         *cur,
263         int                     i,
264         xfs_bmbt_key_t          *k,
265         int                     line)
266 {
267         xfs_dfiloff_t           o;
268
269         o = INT_GET(k->br_startoff, ARCH_CONVERT);
270         xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
271                 i, o >> 32, (int)o, 0,
272                 0, 0, 0, 0,
273                 0, 0, 0);
274 }
275
276 /*
277  * Add a trace buffer entry for the cursor/operation.
278  */
279 STATIC void
280 xfs_bmbt_trace_cursor(
281         char            *func,
282         xfs_btree_cur_t *cur,
283         char            *s,
284         int             line)
285 {
286         xfs_bmbt_rec_t  r;
287
288         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
289         xfs_bmbt_trace_enter(func, cur, s, XFS_BMBT_KTRACE_CUR, line,
290                 (cur->bc_nlevels << 24) | (cur->bc_private.b.flags << 16) |
291                 cur->bc_private.b.allocated,
292                 INT_GET(r.l0, ARCH_CONVERT) >> 32, (int)INT_GET(r.l0, ARCH_CONVERT), INT_GET(r.l1, ARCH_CONVERT) >> 32, (int)INT_GET(r.l1, ARCH_CONVERT),
293                 (unsigned long)cur->bc_bufs[0], (unsigned long)cur->bc_bufs[1],
294                 (unsigned long)cur->bc_bufs[2], (unsigned long)cur->bc_bufs[3],
295                 (cur->bc_ptrs[0] << 16) | cur->bc_ptrs[1],
296                 (cur->bc_ptrs[2] << 16) | cur->bc_ptrs[3]);
297 }
298
299 #define XFS_BMBT_TRACE_ARGBI(c,b,i)     \
300         xfs_bmbt_trace_argbi(fname, c, b, i, __LINE__)
301 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j)  \
302         xfs_bmbt_trace_argbii(fname, c, b, i, j, __LINE__)
303 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j)       \
304         xfs_bmbt_trace_argfffi(fname, c, o, b, i, j, __LINE__)
305 #define XFS_BMBT_TRACE_ARGI(c,i)        \
306         xfs_bmbt_trace_argi(fname, c, i, __LINE__)
307 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,k)  \
308         xfs_bmbt_trace_argifk(fname, c, i, f, k, __LINE__)
309 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r)  \
310         xfs_bmbt_trace_argifr(fname, c, i, f, r, __LINE__)
311 #define XFS_BMBT_TRACE_ARGIK(c,i,k)     \
312         xfs_bmbt_trace_argik(fname, c, i, k, __LINE__)
313 #define XFS_BMBT_TRACE_CURSOR(c,s)      \
314         xfs_bmbt_trace_cursor(fname, c, s, __LINE__)
315 #else
316 #define XFS_BMBT_TRACE_ARGBI(c,b,i)
317 #define XFS_BMBT_TRACE_ARGBII(c,b,i,j)
318 #define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j)
319 #define XFS_BMBT_TRACE_ARGI(c,i)
320 #define XFS_BMBT_TRACE_ARGIFK(c,i,f,k)
321 #define XFS_BMBT_TRACE_ARGIFR(c,i,f,r)
322 #define XFS_BMBT_TRACE_ARGIK(c,i,k)
323 #define XFS_BMBT_TRACE_CURSOR(c,s)
324 #endif  /* XFS_BMBT_TRACE */
325
326
327 /*
328  * Internal functions.
329  */
330
331 /*
332  * Delete record pointed to by cur/level.
333  */
334 STATIC int                                      /* error */
335 xfs_bmbt_delrec(
336         xfs_btree_cur_t         *cur,
337         int                     level,
338         int                     *stat)          /* success/failure */
339 {
340         xfs_bmbt_block_t        *block;         /* bmap btree block */
341         xfs_fsblock_t           bno;            /* fs-relative block number */
342         xfs_buf_t               *bp;            /* buffer for block */
343         int                     error;          /* error return value */
344 #ifdef XFS_BMBT_TRACE
345         static char             fname[] = "xfs_bmbt_delrec";
346 #endif
347         int                     i;              /* loop counter */
348         int                     j;              /* temp state */
349         xfs_bmbt_key_t          key;            /* bmap btree key */
350         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
351         xfs_fsblock_t           lbno;           /* left sibling block number */
352         xfs_buf_t               *lbp;           /* left buffer pointer */
353         xfs_bmbt_block_t        *left;          /* left btree block */
354         xfs_bmbt_key_t          *lkp;           /* left btree key */
355         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
356         int                     lrecs=0;        /* left record count */
357         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
358         xfs_mount_t             *mp;            /* file system mount point */
359         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
360         int                     ptr;            /* key/record index */
361         xfs_fsblock_t           rbno;           /* right sibling block number */
362         xfs_buf_t               *rbp;           /* right buffer pointer */
363         xfs_bmbt_block_t        *right;         /* right btree block */
364         xfs_bmbt_key_t          *rkp;           /* right btree key */
365         xfs_bmbt_rec_t          *rp;            /* pointer to bmap btree rec */
366         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
367         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
368         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
369         int                     rrecs=0;        /* right record count */
370         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
371         xfs_btree_cur_t         *tcur;          /* temporary btree cursor */
372         int                     numrecs;        /* temporary numrec count */
373         int                     numlrecs, numrrecs;
374
375         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
376         XFS_BMBT_TRACE_ARGI(cur, level);
377         ptr = cur->bc_ptrs[level];
378         tcur = (xfs_btree_cur_t *)0;
379         if (ptr == 0) {
380                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
381                 *stat = 0;
382                 return 0;
383         }
384         block = xfs_bmbt_get_block(cur, level, &bp);
385         numrecs = INT_GET(block->bb_numrecs, ARCH_CONVERT);
386 #ifdef DEBUG
387         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
388                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
389                 goto error0;
390         }
391 #endif
392         if (ptr > numrecs) {
393                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
394                 *stat = 0;
395                 return 0;
396         }
397         XFS_STATS_INC(xs_bmbt_delrec);
398         if (level > 0) {
399                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
400                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
401 #ifdef DEBUG
402                 for (i = ptr; i < numrecs; i++) {
403                         if ((error = xfs_btree_check_lptr(cur, INT_GET(pp[i], ARCH_CONVERT), level))) {
404                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
405                                 goto error0;
406                         }
407                 }
408 #endif
409                 if (ptr < numrecs) {
410                         memmove(&kp[ptr - 1], &kp[ptr],
411                                 (numrecs - ptr) * sizeof(*kp));
412                         memmove(&pp[ptr - 1], &pp[ptr], /* INT_: direct copy */
413                                 (numrecs - ptr) * sizeof(*pp));
414                         xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
415                         xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
416                 }
417         } else {
418                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
419                 if (ptr < numrecs) {
420                         memmove(&rp[ptr - 1], &rp[ptr],
421                                 (numrecs - ptr) * sizeof(*rp));
422                         xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
423                 }
424                 if (ptr == 1) {
425                         INT_SET(key.br_startoff, ARCH_CONVERT, xfs_bmbt_disk_get_startoff(rp));
426                         kp = &key;
427                 }
428         }
429         numrecs--;
430         INT_SET(block->bb_numrecs, ARCH_CONVERT, numrecs);
431         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
432         /*
433          * We're at the root level.
434          * First, shrink the root block in-memory.
435          * Try to get rid of the next level down.
436          * If we can't then there's nothing left to do.
437          */
438         if (level == cur->bc_nlevels - 1) {
439                 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
440                         cur->bc_private.b.whichfork);
441                 if ((error = xfs_bmbt_killroot(cur))) {
442                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
443                         goto error0;
444                 }
445                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
446                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
447                         goto error0;
448                 }
449                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
450                 *stat = 1;
451                 return 0;
452         }
453         if (ptr == 1 && (error = xfs_bmbt_updkey(cur, kp, level + 1))) {
454                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
455                 goto error0;
456         }
457         if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
458                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
459                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
460                         goto error0;
461                 }
462                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
463                 *stat = 1;
464                 return 0;
465         }
466         rbno = INT_GET(block->bb_rightsib, ARCH_CONVERT);
467         lbno = INT_GET(block->bb_leftsib, ARCH_CONVERT);
468         /*
469          * One child of root, need to get a chance to copy its contents
470          * into the root and delete it. Can't go up to next level,
471          * there's nothing to delete there.
472          */
473         if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
474             level == cur->bc_nlevels - 2) {
475                 if ((error = xfs_bmbt_killroot(cur))) {
476                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
477                         goto error0;
478                 }
479                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
480                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
481                         goto error0;
482                 }
483                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
484                 *stat = 1;
485                 return 0;
486         }
487         ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
488         if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
489                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
490                 goto error0;
491         }
492         bno = NULLFSBLOCK;
493         if (rbno != NULLFSBLOCK) {
494                 i = xfs_btree_lastrec(tcur, level);
495                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
496                 if ((error = xfs_bmbt_increment(tcur, level, &i))) {
497                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
498                         goto error0;
499                 }
500                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
501                 i = xfs_btree_lastrec(tcur, level);
502                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
503                 rbp = tcur->bc_bufs[level];
504                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
505 #ifdef DEBUG
506                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
507                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
508                         goto error0;
509                 }
510 #endif
511                 bno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
512                 if (INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1 >=
513                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
514                         if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
515                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
516                                 goto error0;
517                         }
518                         if (i) {
519                                 ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
520                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
521                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
522                                 tcur = NULL;
523                                 if (level > 0) {
524                                         if ((error = xfs_bmbt_decrement(cur,
525                                                         level, &i))) {
526                                                 XFS_BMBT_TRACE_CURSOR(cur,
527                                                         ERROR);
528                                                 goto error0;
529                                         }
530                                 }
531                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
532                                 *stat = 1;
533                                 return 0;
534                         }
535                 }
536                 rrecs = INT_GET(right->bb_numrecs, ARCH_CONVERT);
537                 if (lbno != NULLFSBLOCK) {
538                         i = xfs_btree_firstrec(tcur, level);
539                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
540                         if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
541                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
542                                 goto error0;
543                         }
544                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
545                 }
546         }
547         if (lbno != NULLFSBLOCK) {
548                 i = xfs_btree_firstrec(tcur, level);
549                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
550                 /*
551                  * decrement to last in block
552                  */
553                 if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
554                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
555                         goto error0;
556                 }
557                 i = xfs_btree_firstrec(tcur, level);
558                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
559                 lbp = tcur->bc_bufs[level];
560                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
561 #ifdef DEBUG
562                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
563                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
564                         goto error0;
565                 }
566 #endif
567                 bno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
568                 if (INT_GET(left->bb_numrecs, ARCH_CONVERT) - 1 >=
569                     XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
570                         if ((error = xfs_bmbt_rshift(tcur, level, &i))) {
571                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
572                                 goto error0;
573                         }
574                         if (i) {
575                                 ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
576                                        XFS_BMAP_BLOCK_IMINRECS(level, tcur));
577                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
578                                 tcur = NULL;
579                                 if (level == 0)
580                                         cur->bc_ptrs[0]++;
581                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
582                                 *stat = 1;
583                                 return 0;
584                         }
585                 }
586                 lrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT);
587         }
588         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
589         tcur = NULL;
590         mp = cur->bc_mp;
591         ASSERT(bno != NULLFSBLOCK);
592         if (lbno != NULLFSBLOCK &&
593             lrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
594                 rbno = bno;
595                 right = block;
596                 rbp = bp;
597                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
598                                 XFS_BMAP_BTREE_REF))) {
599                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
600                         goto error0;
601                 }
602                 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
603                 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
604                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
605                         goto error0;
606                 }
607         } else if (rbno != NULLFSBLOCK &&
608                    rrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
609                    XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
610                 lbno = bno;
611                 left = block;
612                 lbp = bp;
613                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
614                                 XFS_BMAP_BTREE_REF))) {
615                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
616                         goto error0;
617                 }
618                 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
619                 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
620                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
621                         goto error0;
622                 }
623                 lrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT);
624         } else {
625                 if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
626                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
627                         goto error0;
628                 }
629                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
630                 *stat = 1;
631                 return 0;
632         }
633         numlrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT);
634         numrrecs = INT_GET(right->bb_numrecs, ARCH_CONVERT);
635         if (level > 0) {
636                 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
637                 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
638                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
639                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
640 #ifdef DEBUG
641                 for (i = 0; i < numrrecs; i++) {
642                         if ((error = xfs_btree_check_lptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level))) {
643                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
644                                 goto error0;
645                         }
646                 }
647 #endif
648                 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
649                 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
650                 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
651                 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
652         } else {
653                 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
654                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
655                 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
656                 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
657         }
658         INT_MOD(left->bb_numrecs, ARCH_CONVERT, numrrecs);
659         left->bb_rightsib = right->bb_rightsib; /* INT_: direct copy */
660         xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
661         if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLDFSBNO) {
662                 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
663                                 INT_GET(left->bb_rightsib, ARCH_CONVERT),
664                                 0, &rrbp, XFS_BMAP_BTREE_REF))) {
665                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
666                         goto error0;
667                 }
668                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
669                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
670                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
671                         goto error0;
672                 }
673                 INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, lbno);
674                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
675         }
676         xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
677                 cur->bc_private.b.flist, mp);
678         cur->bc_private.b.ip->i_d.di_nblocks--;
679         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
680         XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
681                         XFS_TRANS_DQ_BCOUNT, -1L);
682         xfs_trans_binval(cur->bc_tp, rbp);
683         if (bp != lbp) {
684                 cur->bc_bufs[level] = lbp;
685                 cur->bc_ptrs[level] += lrecs;
686                 cur->bc_ra[level] = 0;
687         } else if ((error = xfs_bmbt_increment(cur, level + 1, &i))) {
688                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
689                 goto error0;
690         }
691         if (level > 0)
692                 cur->bc_ptrs[level]--;
693         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
694         *stat = 2;
695         return 0;
696
697 error0:
698         if (tcur)
699                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
700         return error;
701 }
702
703 #ifdef DEBUG
704 /*
705  * Get the data from the pointed-to record.
706  */
707 int
708 xfs_bmbt_get_rec(
709         xfs_btree_cur_t         *cur,
710         xfs_fileoff_t           *off,
711         xfs_fsblock_t           *bno,
712         xfs_filblks_t           *len,
713         xfs_exntst_t            *state,
714         int                     *stat)
715 {
716         xfs_bmbt_block_t        *block;
717         xfs_buf_t               *bp;
718 #ifdef DEBUG
719         int                     error;
720 #endif
721         int                     ptr;
722         xfs_bmbt_rec_t          *rp;
723
724         block = xfs_bmbt_get_block(cur, 0, &bp);
725         ptr = cur->bc_ptrs[0];
726 #ifdef DEBUG
727         if ((error = xfs_btree_check_lblock(cur, block, 0, bp)))
728                 return error;
729 #endif
730         if (ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT) || ptr <= 0) {
731                 *stat = 0;
732                 return 0;
733         }
734         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
735         *off = xfs_bmbt_disk_get_startoff(rp);
736         *bno = xfs_bmbt_disk_get_startblock(rp);
737         *len = xfs_bmbt_disk_get_blockcount(rp);
738         *state = xfs_bmbt_disk_get_state(rp);
739         *stat = 1;
740         return 0;
741 }
742 #endif
743
744 /*
745  * Insert one record/level.  Return information to the caller
746  * allowing the next level up to proceed if necessary.
747  */
748 STATIC int                                      /* error */
749 xfs_bmbt_insrec(
750         xfs_btree_cur_t         *cur,
751         int                     level,
752         xfs_fsblock_t           *bnop,
753         xfs_bmbt_rec_t          *recp,
754         xfs_btree_cur_t         **curp,
755         int                     *stat)          /* no-go/done/continue */
756 {
757         xfs_bmbt_block_t        *block;         /* bmap btree block */
758         xfs_buf_t               *bp;            /* buffer for block */
759         int                     error;          /* error return value */
760 #ifdef XFS_BMBT_TRACE
761         static char             fname[] = "xfs_bmbt_insrec";
762 #endif
763         int                     i;              /* loop index */
764         xfs_bmbt_key_t          key;            /* bmap btree key */
765         xfs_bmbt_key_t          *kp=NULL;       /* pointer to bmap btree key */
766         int                     logflags;       /* inode logging flags */
767         xfs_fsblock_t           nbno;           /* new block number */
768         struct xfs_btree_cur    *ncur;          /* new btree cursor */
769         xfs_bmbt_key_t          nkey;           /* new btree key value */
770         xfs_bmbt_rec_t          nrec;           /* new record count */
771         int                     optr;           /* old key/record index */
772         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
773         int                     ptr;            /* key/record index */
774         xfs_bmbt_rec_t          *rp=NULL;       /* pointer to bmap btree rec */
775         int                     numrecs;
776
777         ASSERT(level < cur->bc_nlevels);
778         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
779         XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
780         ncur = (xfs_btree_cur_t *)0;
781         INT_SET(key.br_startoff, ARCH_CONVERT,
782                 xfs_bmbt_disk_get_startoff(recp));
783         optr = ptr = cur->bc_ptrs[level];
784         if (ptr == 0) {
785                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
786                 *stat = 0;
787                 return 0;
788         }
789         XFS_STATS_INC(xs_bmbt_insrec);
790         block = xfs_bmbt_get_block(cur, level, &bp);
791         numrecs = INT_GET(block->bb_numrecs, ARCH_CONVERT);
792 #ifdef DEBUG
793         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
794                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
795                 return error;
796         }
797         if (ptr <= numrecs) {
798                 if (level == 0) {
799                         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
800                         xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
801                 } else {
802                         kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
803                         xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
804                 }
805         }
806 #endif
807         nbno = NULLFSBLOCK;
808         if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
809                 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
810                         /*
811                          * A root block, that can be made bigger.
812                          */
813                         xfs_iroot_realloc(cur->bc_private.b.ip, 1,
814                                 cur->bc_private.b.whichfork);
815                         block = xfs_bmbt_get_block(cur, level, &bp);
816                 } else if (level == cur->bc_nlevels - 1) {
817                         if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
818                             *stat == 0) {
819                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
820                                 return error;
821                         }
822                         xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
823                                 logflags);
824                         block = xfs_bmbt_get_block(cur, level, &bp);
825                 } else {
826                         if ((error = xfs_bmbt_rshift(cur, level, &i))) {
827                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
828                                 return error;
829                         }
830                         if (i) {
831                                 /* nothing */
832                         } else {
833                                 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
834                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
835                                         return error;
836                                 }
837                                 if (i) {
838                                         optr = ptr = cur->bc_ptrs[level];
839                                 } else {
840                                         if ((error = xfs_bmbt_split(cur, level,
841                                                         &nbno, &nkey, &ncur,
842                                                         &i))) {
843                                                 XFS_BMBT_TRACE_CURSOR(cur,
844                                                         ERROR);
845                                                 return error;
846                                         }
847                                         if (i) {
848                                                 block = xfs_bmbt_get_block(
849                                                             cur, level, &bp);
850 #ifdef DEBUG
851                                                 if ((error =
852                                                     xfs_btree_check_lblock(cur,
853                                                             block, level, bp))) {
854                                                         XFS_BMBT_TRACE_CURSOR(
855                                                                 cur, ERROR);
856                                                         return error;
857                                                 }
858 #endif
859                                                 ptr = cur->bc_ptrs[level];
860                                                 xfs_bmbt_disk_set_allf(&nrec,
861                                                         nkey.br_startoff, 0, 0,
862                                                         XFS_EXT_NORM);
863                                         } else {
864                                                 XFS_BMBT_TRACE_CURSOR(cur,
865                                                         EXIT);
866                                                 *stat = 0;
867                                                 return 0;
868                                         }
869                                 }
870                         }
871                 }
872         }
873         numrecs = INT_GET(block->bb_numrecs, ARCH_CONVERT);
874         if (level > 0) {
875                 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
876                 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
877 #ifdef DEBUG
878                 for (i = numrecs; i >= ptr; i--) {
879                         if ((error = xfs_btree_check_lptr(cur, INT_GET(pp[i - 1], ARCH_CONVERT),
880                                         level))) {
881                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
882                                 return error;
883                         }
884                 }
885 #endif
886                 memmove(&kp[ptr], &kp[ptr - 1],
887                         (numrecs - ptr + 1) * sizeof(*kp));
888                 memmove(&pp[ptr], &pp[ptr - 1], /* INT_: direct copy */
889                         (numrecs - ptr + 1) * sizeof(*pp));
890 #ifdef DEBUG
891                 if ((error = xfs_btree_check_lptr(cur, (xfs_bmbt_ptr_t)*bnop,
892                                 level))) {
893                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
894                         return error;
895                 }
896 #endif
897                 kp[ptr - 1] = key;
898                 INT_SET(pp[ptr - 1], ARCH_CONVERT, *bnop);
899                 numrecs++;
900                 INT_SET(block->bb_numrecs, ARCH_CONVERT, numrecs);
901                 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
902                 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
903         } else {
904                 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
905                 memmove(&rp[ptr], &rp[ptr - 1],
906                         (numrecs - ptr + 1) * sizeof(*rp));
907                 rp[ptr - 1] = *recp;
908                 numrecs++;
909                 INT_SET(block->bb_numrecs, ARCH_CONVERT, numrecs);
910                 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
911         }
912         xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
913 #ifdef DEBUG
914         if (ptr < numrecs) {
915                 if (level == 0)
916                         xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
917                                 rp + ptr);
918                 else
919                         xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
920                                 kp + ptr);
921         }
922 #endif
923         if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
924                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
925                 return error;
926         }
927         *bnop = nbno;
928         if (nbno != NULLFSBLOCK) {
929                 *recp = nrec;
930                 *curp = ncur;
931         }
932         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
933         *stat = 1;
934         return 0;
935 }
936
937 STATIC int
938 xfs_bmbt_killroot(
939         xfs_btree_cur_t         *cur)
940 {
941         xfs_bmbt_block_t        *block;
942         xfs_bmbt_block_t        *cblock;
943         xfs_buf_t               *cbp;
944         xfs_bmbt_key_t          *ckp;
945         xfs_bmbt_ptr_t          *cpp;
946 #ifdef DEBUG
947         int                     error;
948 #endif
949 #ifdef XFS_BMBT_TRACE
950         static char             fname[] = "xfs_bmbt_killroot";
951 #endif
952         int                     i;
953         xfs_bmbt_key_t          *kp;
954         xfs_inode_t             *ip;
955         xfs_ifork_t             *ifp;
956         int                     level;
957         xfs_bmbt_ptr_t          *pp;
958
959         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
960         level = cur->bc_nlevels - 1;
961         ASSERT(level >= 1);
962         /*
963          * Don't deal with the root block needs to be a leaf case.
964          * We're just going to turn the thing back into extents anyway.
965          */
966         if (level == 1) {
967                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
968                 return 0;
969         }
970         block = xfs_bmbt_get_block(cur, level, &cbp);
971         /*
972          * Give up if the root has multiple children.
973          */
974         if (INT_GET(block->bb_numrecs, ARCH_CONVERT) != 1) {
975                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
976                 return 0;
977         }
978         /*
979          * Only do this if the next level will fit.
980          * Then the data must be copied up to the inode,
981          * instead of freeing the root you free the next level.
982          */
983         cbp = cur->bc_bufs[level - 1];
984         cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
985         if (INT_GET(cblock->bb_numrecs, ARCH_CONVERT) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
986                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
987                 return 0;
988         }
989         ASSERT(INT_GET(cblock->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO);
990         ASSERT(INT_GET(cblock->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO);
991         ip = cur->bc_private.b.ip;
992         ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
993         ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
994                XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
995         i = (int)(INT_GET(cblock->bb_numrecs, ARCH_CONVERT) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
996         if (i) {
997                 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
998                 block = ifp->if_broot;
999         }
1000         INT_MOD(block->bb_numrecs, ARCH_CONVERT, i);
1001         ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) == INT_GET(cblock->bb_numrecs, ARCH_CONVERT));
1002         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
1003         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
1004         memcpy(kp, ckp, INT_GET(block->bb_numrecs, ARCH_CONVERT) * sizeof(*kp));
1005         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
1006         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
1007 #ifdef DEBUG
1008         for (i = 0; i < INT_GET(cblock->bb_numrecs, ARCH_CONVERT); i++) {
1009                 if ((error = xfs_btree_check_lptr(cur, INT_GET(cpp[i], ARCH_CONVERT), level - 1))) {
1010                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1011                         return error;
1012                 }
1013         }
1014 #endif
1015         memcpy(pp, cpp, INT_GET(block->bb_numrecs, ARCH_CONVERT) * sizeof(*pp));
1016         xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
1017                         cur->bc_private.b.flist, cur->bc_mp);
1018         ip->i_d.di_nblocks--;
1019         XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
1020                         XFS_TRANS_DQ_BCOUNT, -1L);
1021         xfs_trans_binval(cur->bc_tp, cbp);
1022         cur->bc_bufs[level - 1] = NULL;
1023         INT_MOD(block->bb_level, ARCH_CONVERT, -1);
1024         xfs_trans_log_inode(cur->bc_tp, ip,
1025                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1026         cur->bc_nlevels--;
1027         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1028         return 0;
1029 }
1030
1031 /*
1032  * Log key values from the btree block.
1033  */
1034 STATIC void
1035 xfs_bmbt_log_keys(
1036         xfs_btree_cur_t *cur,
1037         xfs_buf_t       *bp,
1038         int             kfirst,
1039         int             klast)
1040 {
1041 #ifdef XFS_BMBT_TRACE
1042         static char     fname[] = "xfs_bmbt_log_keys";
1043 #endif
1044         xfs_trans_t     *tp;
1045
1046         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1047         XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
1048         tp = cur->bc_tp;
1049         if (bp) {
1050                 xfs_bmbt_block_t        *block;
1051                 int                     first;
1052                 xfs_bmbt_key_t          *kp;
1053                 int                     last;
1054
1055                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1056                 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
1057                 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
1058                 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
1059                 xfs_trans_log_buf(tp, bp, first, last);
1060         } else {
1061                 xfs_inode_t              *ip;
1062
1063                 ip = cur->bc_private.b.ip;
1064                 xfs_trans_log_inode(tp, ip,
1065                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1066         }
1067         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1068 }
1069
1070 /*
1071  * Log pointer values from the btree block.
1072  */
1073 STATIC void
1074 xfs_bmbt_log_ptrs(
1075         xfs_btree_cur_t *cur,
1076         xfs_buf_t       *bp,
1077         int             pfirst,
1078         int             plast)
1079 {
1080 #ifdef XFS_BMBT_TRACE
1081         static char     fname[] = "xfs_bmbt_log_ptrs";
1082 #endif
1083         xfs_trans_t     *tp;
1084
1085         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1086         XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
1087         tp = cur->bc_tp;
1088         if (bp) {
1089                 xfs_bmbt_block_t        *block;
1090                 int                     first;
1091                 int                     last;
1092                 xfs_bmbt_ptr_t          *pp;
1093
1094                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1095                 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
1096                 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
1097                 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
1098                 xfs_trans_log_buf(tp, bp, first, last);
1099         } else {
1100                 xfs_inode_t             *ip;
1101
1102                 ip = cur->bc_private.b.ip;
1103                 xfs_trans_log_inode(tp, ip,
1104                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1105         }
1106         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1107 }
1108
1109 /*
1110  * Lookup the record.  The cursor is made to point to it, based on dir.
1111  */
1112 STATIC int                              /* error */
1113 xfs_bmbt_lookup(
1114         xfs_btree_cur_t         *cur,
1115         xfs_lookup_t            dir,
1116         int                     *stat)          /* success/failure */
1117 {
1118         xfs_bmbt_block_t        *block=NULL;
1119         xfs_buf_t               *bp;
1120         xfs_daddr_t             d;
1121         xfs_sfiloff_t           diff;
1122         int                     error;          /* error return value */
1123 #ifdef XFS_BMBT_TRACE
1124         static char     fname[] = "xfs_bmbt_lookup";
1125 #endif
1126         xfs_fsblock_t           fsbno=0;
1127         int                     high;
1128         int                     i;
1129         int                     keyno=0;
1130         xfs_bmbt_key_t          *kkbase=NULL;
1131         xfs_bmbt_key_t          *kkp;
1132         xfs_bmbt_rec_t          *krbase=NULL;
1133         xfs_bmbt_rec_t          *krp;
1134         int                     level;
1135         int                     low;
1136         xfs_mount_t             *mp;
1137         xfs_bmbt_ptr_t          *pp;
1138         xfs_bmbt_irec_t         *rp;
1139         xfs_fileoff_t           startoff;
1140         xfs_trans_t             *tp;
1141
1142         XFS_STATS_INC(xs_bmbt_lookup);
1143         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1144         XFS_BMBT_TRACE_ARGI(cur, (int)dir);
1145         tp = cur->bc_tp;
1146         mp = cur->bc_mp;
1147         rp = &cur->bc_rec.b;
1148         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1149                 if (level < cur->bc_nlevels - 1) {
1150                         d = XFS_FSB_TO_DADDR(mp, fsbno);
1151                         bp = cur->bc_bufs[level];
1152                         if (bp && XFS_BUF_ADDR(bp) != d)
1153                                 bp = (xfs_buf_t *)0;
1154                         if (!bp) {
1155                                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
1156                                                 0, &bp, XFS_BMAP_BTREE_REF))) {
1157                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1158                                         return error;
1159                                 }
1160                                 xfs_btree_setbuf(cur, level, bp);
1161                                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1162                                 if ((error = xfs_btree_check_lblock(cur, block,
1163                                                 level, bp))) {
1164                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1165                                         return error;
1166                                 }
1167                         } else
1168                                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1169                 } else
1170                         block = xfs_bmbt_get_block(cur, level, &bp);
1171                 if (diff == 0)
1172                         keyno = 1;
1173                 else {
1174                         if (level > 0)
1175                                 kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
1176                         else
1177                                 krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
1178                         low = 1;
1179                         if (!(high = INT_GET(block->bb_numrecs, ARCH_CONVERT))) {
1180                                 ASSERT(level == 0);
1181                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1182                                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1183                                 *stat = 0;
1184                                 return 0;
1185                         }
1186                         while (low <= high) {
1187                                 XFS_STATS_INC(xs_bmbt_compare);
1188                                 keyno = (low + high) >> 1;
1189                                 if (level > 0) {
1190                                         kkp = kkbase + keyno - 1;
1191                                         startoff = INT_GET(kkp->br_startoff, ARCH_CONVERT);
1192                                 } else {
1193                                         krp = krbase + keyno - 1;
1194                                         startoff = xfs_bmbt_disk_get_startoff(krp);
1195                                 }
1196                                 diff = (xfs_sfiloff_t)
1197                                                 (startoff - rp->br_startoff);
1198                                 if (diff < 0)
1199                                         low = keyno + 1;
1200                                 else if (diff > 0)
1201                                         high = keyno - 1;
1202                                 else
1203                                         break;
1204                         }
1205                 }
1206                 if (level > 0) {
1207                         if (diff > 0 && --keyno < 1)
1208                                 keyno = 1;
1209                         pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
1210 #ifdef DEBUG
1211                         if ((error = xfs_btree_check_lptr(cur, INT_GET(*pp, ARCH_CONVERT), level))) {
1212                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1213                                 return error;
1214                         }
1215 #endif
1216                         fsbno = INT_GET(*pp, ARCH_CONVERT);
1217                         cur->bc_ptrs[level] = keyno;
1218                 }
1219         }
1220         if (dir != XFS_LOOKUP_LE && diff < 0) {
1221                 keyno++;
1222                 /*
1223                  * If ge search and we went off the end of the block, but it's
1224                  * not the last block, we're in the wrong block.
1225                  */
1226                 if (dir == XFS_LOOKUP_GE && keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT) &&
1227                     INT_GET(block->bb_rightsib, ARCH_CONVERT) != NULLDFSBNO) {
1228                         cur->bc_ptrs[0] = keyno;
1229                         if ((error = xfs_bmbt_increment(cur, 0, &i))) {
1230                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1231                                 return error;
1232                         }
1233                         XFS_WANT_CORRUPTED_RETURN(i == 1);
1234                         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1235                         *stat = 1;
1236                         return 0;
1237                 }
1238         }
1239         else if (dir == XFS_LOOKUP_LE && diff > 0)
1240                 keyno--;
1241         cur->bc_ptrs[0] = keyno;
1242         if (keyno == 0 || keyno > INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
1243                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1244                 *stat = 0;
1245         } else {
1246                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1247                 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1248         }
1249         return 0;
1250 }
1251
1252 /*
1253  * Move 1 record left from cur/level if possible.
1254  * Update cur to reflect the new path.
1255  */
1256 STATIC int                                      /* error */
1257 xfs_bmbt_lshift(
1258         xfs_btree_cur_t         *cur,
1259         int                     level,
1260         int                     *stat)          /* success/failure */
1261 {
1262         int                     error;          /* error return value */
1263 #ifdef XFS_BMBT_TRACE
1264         static char             fname[] = "xfs_bmbt_lshift";
1265 #endif
1266 #ifdef DEBUG
1267         int                     i;              /* loop counter */
1268 #endif
1269         xfs_bmbt_key_t          key;            /* bmap btree key */
1270         xfs_buf_t               *lbp;           /* left buffer pointer */
1271         xfs_bmbt_block_t        *left;          /* left btree block */
1272         xfs_bmbt_key_t          *lkp=NULL;      /* left btree key */
1273         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
1274         int                     lrecs;          /* left record count */
1275         xfs_bmbt_rec_t          *lrp=NULL;      /* left record pointer */
1276         xfs_mount_t             *mp;            /* file system mount point */
1277         xfs_buf_t               *rbp;           /* right buffer pointer */
1278         xfs_bmbt_block_t        *right;         /* right btree block */
1279         xfs_bmbt_key_t          *rkp=NULL;      /* right btree key */
1280         xfs_bmbt_ptr_t          *rpp=NULL;      /* right address pointer */
1281         xfs_bmbt_rec_t          *rrp=NULL;      /* right record pointer */
1282         int                     rrecs;          /* right record count */
1283
1284         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1285         XFS_BMBT_TRACE_ARGI(cur, level);
1286         if (level == cur->bc_nlevels - 1) {
1287                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1288                 *stat = 0;
1289                 return 0;
1290         }
1291         rbp = cur->bc_bufs[level];
1292         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1293 #ifdef DEBUG
1294         if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1295                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1296                 return error;
1297         }
1298 #endif
1299         if (INT_GET(right->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO) {
1300                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1301                 *stat = 0;
1302                 return 0;
1303         }
1304         if (cur->bc_ptrs[level] <= 1) {
1305                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1306                 *stat = 0;
1307                 return 0;
1308         }
1309         mp = cur->bc_mp;
1310         if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, INT_GET(right->bb_leftsib, ARCH_CONVERT), 0,
1311                         &lbp, XFS_BMAP_BTREE_REF))) {
1312                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1313                 return error;
1314         }
1315         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1316         if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1317                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1318                 return error;
1319         }
1320         if (INT_GET(left->bb_numrecs, ARCH_CONVERT) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1321                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1322                 *stat = 0;
1323                 return 0;
1324         }
1325         lrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1;
1326         if (level > 0) {
1327                 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
1328                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1329                 *lkp = *rkp;
1330                 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
1331                 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
1332                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1333 #ifdef DEBUG
1334                 if ((error = xfs_btree_check_lptr(cur, INT_GET(*rpp, ARCH_CONVERT), level))) {
1335                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1336                         return error;
1337                 }
1338 #endif
1339                 *lpp = *rpp; /* INT_: direct copy */
1340                 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
1341         } else {
1342                 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
1343                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1344                 *lrp = *rrp;
1345                 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
1346         }
1347         INT_SET(left->bb_numrecs, ARCH_CONVERT, lrecs);
1348         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1349 #ifdef DEBUG
1350         if (level > 0)
1351                 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
1352         else
1353                 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
1354 #endif
1355         rrecs = INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1;
1356         INT_SET(right->bb_numrecs, ARCH_CONVERT, rrecs);
1357         xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1358         if (level > 0) {
1359 #ifdef DEBUG
1360                 for (i = 0; i < rrecs; i++) {
1361                         if ((error = xfs_btree_check_lptr(cur, INT_GET(rpp[i + 1], ARCH_CONVERT),
1362                                         level))) {
1363                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1364                                 return error;
1365                         }
1366                 }
1367 #endif
1368                 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
1369                 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
1370                 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
1371                 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
1372         } else {
1373                 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
1374                 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
1375                 INT_SET(key.br_startoff, ARCH_CONVERT,
1376                         xfs_bmbt_disk_get_startoff(rrp));
1377                 rkp = &key;
1378         }
1379         if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
1380                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1381                 return error;
1382         }
1383         cur->bc_ptrs[level]--;
1384         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1385         *stat = 1;
1386         return 0;
1387 }
1388
1389 /*
1390  * Move 1 record right from cur/level if possible.
1391  * Update cur to reflect the new path.
1392  */
1393 STATIC int                                      /* error */
1394 xfs_bmbt_rshift(
1395         xfs_btree_cur_t         *cur,
1396         int                     level,
1397         int                     *stat)          /* success/failure */
1398 {
1399         int                     error;          /* error return value */
1400 #ifdef XFS_BMBT_TRACE
1401         static char             fname[] = "xfs_bmbt_rshift";
1402 #endif
1403         int                     i;              /* loop counter */
1404         xfs_bmbt_key_t          key;            /* bmap btree key */
1405         xfs_buf_t               *lbp;           /* left buffer pointer */
1406         xfs_bmbt_block_t        *left;          /* left btree block */
1407         xfs_bmbt_key_t          *lkp;           /* left btree key */
1408         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
1409         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
1410         xfs_mount_t             *mp;            /* file system mount point */
1411         xfs_buf_t               *rbp;           /* right buffer pointer */
1412         xfs_bmbt_block_t        *right;         /* right btree block */
1413         xfs_bmbt_key_t          *rkp;           /* right btree key */
1414         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
1415         xfs_bmbt_rec_t          *rrp=NULL;      /* right record pointer */
1416         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
1417
1418         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1419         XFS_BMBT_TRACE_ARGI(cur, level);
1420         if (level == cur->bc_nlevels - 1) {
1421                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1422                 *stat = 0;
1423                 return 0;
1424         }
1425         lbp = cur->bc_bufs[level];
1426         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1427 #ifdef DEBUG
1428         if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1429                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1430                 return error;
1431         }
1432 #endif
1433         if (INT_GET(left->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO) {
1434                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1435                 *stat = 0;
1436                 return 0;
1437         }
1438         if (cur->bc_ptrs[level] >= INT_GET(left->bb_numrecs, ARCH_CONVERT)) {
1439                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1440                 *stat = 0;
1441                 return 0;
1442         }
1443         mp = cur->bc_mp;
1444         if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, INT_GET(left->bb_rightsib, ARCH_CONVERT), 0,
1445                         &rbp, XFS_BMAP_BTREE_REF))) {
1446                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1447                 return error;
1448         }
1449         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1450         if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1451                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1452                 return error;
1453         }
1454         if (INT_GET(right->bb_numrecs, ARCH_CONVERT) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1455                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1456                 *stat = 0;
1457                 return 0;
1458         }
1459         if (level > 0) {
1460                 lkp = XFS_BMAP_KEY_IADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1461                 lpp = XFS_BMAP_PTR_IADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1462                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1463                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1464 #ifdef DEBUG
1465                 for (i = INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1; i >= 0; i--) {
1466                         if ((error = xfs_btree_check_lptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level))) {
1467                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1468                                 return error;
1469                         }
1470                 }
1471 #endif
1472                 memmove(rkp + 1, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1473                 memmove(rpp + 1, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1474 #ifdef DEBUG
1475                 if ((error = xfs_btree_check_lptr(cur, INT_GET(*lpp, ARCH_CONVERT), level))) {
1476                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1477                         return error;
1478                 }
1479 #endif
1480                 *rkp = *lkp;
1481                 *rpp = *lpp; /* INT_: direct copy */
1482                 xfs_bmbt_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1483                 xfs_bmbt_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1484         } else {
1485                 lrp = XFS_BMAP_REC_IADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
1486                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1487                 memmove(rrp + 1, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1488                 *rrp = *lrp;
1489                 xfs_bmbt_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
1490                 INT_SET(key.br_startoff, ARCH_CONVERT,
1491                         xfs_bmbt_disk_get_startoff(rrp));
1492                 rkp = &key;
1493         }
1494         INT_MOD(left->bb_numrecs, ARCH_CONVERT, -1);
1495         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1496         INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1497 #ifdef DEBUG
1498         if (level > 0)
1499                 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1500         else
1501                 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1502 #endif
1503         xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1504         if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1505                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1506                 return error;
1507         }
1508         i = xfs_btree_lastrec(tcur, level);
1509         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1510         if ((error = xfs_bmbt_increment(tcur, level, &i))) {
1511                 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1512                 goto error1;
1513         }
1514         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1515         if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {
1516                 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1517                 goto error1;
1518         }
1519         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1520         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1521         *stat = 1;
1522         return 0;
1523 error0:
1524         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1525 error1:
1526         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1527         return error;
1528 }
1529
1530 /*
1531  * Determine the extent state.
1532  */
1533 /* ARGSUSED */
1534 STATIC xfs_exntst_t
1535 xfs_extent_state(
1536         xfs_filblks_t           blks,
1537         int                     extent_flag)
1538 {
1539         if (extent_flag) {
1540                 ASSERT(blks != 0);      /* saved for DMIG */
1541                 return XFS_EXT_UNWRITTEN;
1542         }
1543         return XFS_EXT_NORM;
1544 }
1545
1546
1547 /*
1548  * Split cur/level block in half.
1549  * Return new block number and its first record (to be inserted into parent).
1550  */
1551 STATIC int                                      /* error */
1552 xfs_bmbt_split(
1553         xfs_btree_cur_t         *cur,
1554         int                     level,
1555         xfs_fsblock_t           *bnop,
1556         xfs_bmbt_key_t          *keyp,
1557         xfs_btree_cur_t         **curp,
1558         int                     *stat)          /* success/failure */
1559 {
1560         xfs_alloc_arg_t         args;           /* block allocation args */
1561         int                     error;          /* error return value */
1562 #ifdef XFS_BMBT_TRACE
1563         static char             fname[] = "xfs_bmbt_split";
1564 #endif
1565         int                     i;              /* loop counter */
1566         xfs_fsblock_t           lbno;           /* left sibling block number */
1567         xfs_buf_t               *lbp;           /* left buffer pointer */
1568         xfs_bmbt_block_t        *left;          /* left btree block */
1569         xfs_bmbt_key_t          *lkp;           /* left btree key */
1570         xfs_bmbt_ptr_t          *lpp;           /* left address pointer */
1571         xfs_bmbt_rec_t          *lrp;           /* left record pointer */
1572         xfs_buf_t               *rbp;           /* right buffer pointer */
1573         xfs_bmbt_block_t        *right;         /* right btree block */
1574         xfs_bmbt_key_t          *rkp;           /* right btree key */
1575         xfs_bmbt_ptr_t          *rpp;           /* right address pointer */
1576         xfs_bmbt_block_t        *rrblock;       /* right-right btree block */
1577         xfs_buf_t               *rrbp;          /* right-right buffer pointer */
1578         xfs_bmbt_rec_t          *rrp;           /* right record pointer */
1579
1580         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1581         XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, keyp);
1582         args.tp = cur->bc_tp;
1583         args.mp = cur->bc_mp;
1584         lbp = cur->bc_bufs[level];
1585         lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1586         left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1587         args.fsbno = cur->bc_private.b.firstblock;
1588         if (args.fsbno == NULLFSBLOCK) {
1589                 args.fsbno = lbno;
1590                 args.type = XFS_ALLOCTYPE_START_BNO;
1591         } else if (cur->bc_private.b.flist->xbf_low)
1592                 args.type = XFS_ALLOCTYPE_FIRST_AG;
1593         else
1594                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1595         args.mod = args.minleft = args.alignment = args.total = args.isfl =
1596                 args.userdata = args.minalignslop = 0;
1597         args.minlen = args.maxlen = args.prod = 1;
1598         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1599         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1600                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1601                 return XFS_ERROR(ENOSPC);
1602         }
1603         if ((error = xfs_alloc_vextent(&args))) {
1604                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1605                 return error;
1606         }
1607         if (args.fsbno == NULLFSBLOCK) {
1608                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1609                 *stat = 0;
1610                 return 0;
1611         }
1612         ASSERT(args.len == 1);
1613         cur->bc_private.b.firstblock = args.fsbno;
1614         cur->bc_private.b.allocated++;
1615         cur->bc_private.b.ip->i_d.di_nblocks++;
1616         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1617         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1618                         XFS_TRANS_DQ_BCOUNT, 1L);
1619         rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1620         right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1621 #ifdef DEBUG
1622         if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1623                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1624                 return error;
1625         }
1626 #endif
1627         INT_SET(right->bb_magic, ARCH_CONVERT, XFS_BMAP_MAGIC);
1628         right->bb_level = left->bb_level; /* INT_: direct copy */
1629         INT_SET(right->bb_numrecs, ARCH_CONVERT, (__uint16_t)(INT_GET(left->bb_numrecs, ARCH_CONVERT) / 2));
1630         if ((INT_GET(left->bb_numrecs, ARCH_CONVERT) & 1) &&
1631             cur->bc_ptrs[level] <= INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1)
1632                 INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
1633         i = INT_GET(left->bb_numrecs, ARCH_CONVERT) - INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1;
1634         if (level > 0) {
1635                 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1636                 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1637                 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1638                 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1639 #ifdef DEBUG
1640                 for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
1641                         if ((error = xfs_btree_check_lptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level))) {
1642                                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1643                                 return error;
1644                         }
1645                 }
1646 #endif
1647                 memcpy(rkp, lkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
1648                 memcpy(rpp, lpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
1649                 xfs_bmbt_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1650                 xfs_bmbt_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1651                 keyp->br_startoff = INT_GET(rkp->br_startoff, ARCH_CONVERT);
1652         } else {
1653                 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1654                 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1655                 memcpy(rrp, lrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
1656                 xfs_bmbt_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
1657                 keyp->br_startoff = xfs_bmbt_disk_get_startoff(rrp);
1658         }
1659         INT_MOD(left->bb_numrecs, ARCH_CONVERT, -(INT_GET(right->bb_numrecs, ARCH_CONVERT)));
1660         right->bb_rightsib = left->bb_rightsib; /* INT_: direct copy */
1661         INT_SET(left->bb_rightsib, ARCH_CONVERT, args.fsbno);
1662         INT_SET(right->bb_leftsib, ARCH_CONVERT, lbno);
1663         xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1664         xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
1665         if (INT_GET(right->bb_rightsib, ARCH_CONVERT) != NULLDFSBNO) {
1666                 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
1667                                 INT_GET(right->bb_rightsib, ARCH_CONVERT), 0, &rrbp,
1668                                 XFS_BMAP_BTREE_REF))) {
1669                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1670                         return error;
1671                 }
1672                 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1673                 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1674                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1675                         return error;
1676                 }
1677                 INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, args.fsbno);
1678                 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1679         }
1680         if (cur->bc_ptrs[level] > INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1) {
1681                 xfs_btree_setbuf(cur, level, rbp);
1682                 cur->bc_ptrs[level] -= INT_GET(left->bb_numrecs, ARCH_CONVERT);
1683         }
1684         if (level + 1 < cur->bc_nlevels) {
1685                 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1686                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1687                         return error;
1688                 }
1689                 (*curp)->bc_ptrs[level + 1]++;
1690         }
1691         *bnop = args.fsbno;
1692         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1693         *stat = 1;
1694         return 0;
1695 }
1696
1697
1698 /*
1699  * Update keys for the record.
1700  */
1701 STATIC int
1702 xfs_bmbt_updkey(
1703         xfs_btree_cur_t         *cur,
1704         xfs_bmbt_key_t          *keyp,  /* on-disk format */
1705         int                     level)
1706 {
1707         xfs_bmbt_block_t        *block;
1708         xfs_buf_t               *bp;
1709 #ifdef DEBUG
1710         int                     error;
1711 #endif
1712 #ifdef XFS_BMBT_TRACE
1713         static char             fname[] = "xfs_bmbt_updkey";
1714 #endif
1715         xfs_bmbt_key_t          *kp;
1716         int                     ptr;
1717
1718         ASSERT(level >= 1);
1719         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1720         XFS_BMBT_TRACE_ARGIK(cur, level, keyp);
1721         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1722                 block = xfs_bmbt_get_block(cur, level, &bp);
1723 #ifdef DEBUG
1724                 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1725                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1726                         return error;
1727                 }
1728 #endif
1729                 ptr = cur->bc_ptrs[level];
1730                 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
1731                 *kp = *keyp;
1732                 xfs_bmbt_log_keys(cur, bp, ptr, ptr);
1733         }
1734         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1735         return 0;
1736 }
1737
1738 /*
1739  * Convert on-disk form of btree root to in-memory form.
1740  */
1741 void
1742 xfs_bmdr_to_bmbt(
1743         xfs_bmdr_block_t        *dblock,
1744         int                     dblocklen,
1745         xfs_bmbt_block_t        *rblock,
1746         int                     rblocklen)
1747 {
1748         int                     dmxr;
1749         xfs_bmbt_key_t          *fkp;
1750         xfs_bmbt_ptr_t          *fpp;
1751         xfs_bmbt_key_t          *tkp;
1752         xfs_bmbt_ptr_t          *tpp;
1753
1754         INT_SET(rblock->bb_magic, ARCH_CONVERT, XFS_BMAP_MAGIC);
1755         rblock->bb_level = dblock->bb_level;    /* both in on-disk format */
1756         ASSERT(INT_GET(rblock->bb_level, ARCH_CONVERT) > 0);
1757         rblock->bb_numrecs = dblock->bb_numrecs;/* both in on-disk format */
1758         INT_SET(rblock->bb_leftsib, ARCH_CONVERT, NULLDFSBNO);
1759         INT_SET(rblock->bb_rightsib, ARCH_CONVERT, NULLDFSBNO);
1760         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1761         fkp = XFS_BTREE_KEY_ADDR(dblocklen, xfs_bmdr, dblock, 1, dmxr);
1762         tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
1763         fpp = XFS_BTREE_PTR_ADDR(dblocklen, xfs_bmdr, dblock, 1, dmxr);
1764         tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
1765         dmxr = INT_GET(dblock->bb_numrecs, ARCH_CONVERT);
1766         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
1767         memcpy(tpp, fpp, sizeof(*fpp) * dmxr); /* INT_: direct copy */
1768 }
1769
1770 /*
1771  * Decrement cursor by one record at the level.
1772  * For nonzero levels the leaf-ward information is untouched.
1773  */
1774 int                                             /* error */
1775 xfs_bmbt_decrement(
1776         xfs_btree_cur_t         *cur,
1777         int                     level,
1778         int                     *stat)          /* success/failure */
1779 {
1780         xfs_bmbt_block_t        *block;
1781         xfs_buf_t               *bp;
1782         int                     error;          /* error return value */
1783 #ifdef XFS_BMBT_TRACE
1784         static char             fname[] = "xfs_bmbt_decrement";
1785 #endif
1786         xfs_fsblock_t           fsbno;
1787         int                     lev;
1788         xfs_mount_t             *mp;
1789         xfs_trans_t             *tp;
1790
1791         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1792         XFS_BMBT_TRACE_ARGI(cur, level);
1793         ASSERT(level < cur->bc_nlevels);
1794         if (level < cur->bc_nlevels - 1)
1795                 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1796         if (--cur->bc_ptrs[level] > 0) {
1797                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1798                 *stat = 1;
1799                 return 0;
1800         }
1801         block = xfs_bmbt_get_block(cur, level, &bp);
1802 #ifdef DEBUG
1803         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1804                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1805                 return error;
1806         }
1807 #endif
1808         if (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO) {
1809                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1810                 *stat = 0;
1811                 return 0;
1812         }
1813         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1814                 if (--cur->bc_ptrs[lev] > 0)
1815                         break;
1816                 if (lev < cur->bc_nlevels - 1)
1817                         xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1818         }
1819         if (lev == cur->bc_nlevels) {
1820                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1821                 *stat = 0;
1822                 return 0;
1823         }
1824         tp = cur->bc_tp;
1825         mp = cur->bc_mp;
1826         for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
1827                 fsbno = INT_GET(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
1828                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1829                                 XFS_BMAP_BTREE_REF))) {
1830                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1831                         return error;
1832                 }
1833                 lev--;
1834                 xfs_btree_setbuf(cur, lev, bp);
1835                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1836                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1837                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1838                         return error;
1839                 }
1840                 cur->bc_ptrs[lev] = INT_GET(block->bb_numrecs, ARCH_CONVERT);
1841         }
1842         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1843         *stat = 1;
1844         return 0;
1845 }
1846
1847 /*
1848  * Delete the record pointed to by cur.
1849  */
1850 int                                     /* error */
1851 xfs_bmbt_delete(
1852         xfs_btree_cur_t *cur,
1853         int             *stat)          /* success/failure */
1854 {
1855         int             error;          /* error return value */
1856 #ifdef XFS_BMBT_TRACE
1857         static char     fname[] = "xfs_bmbt_delete";
1858 #endif
1859         int             i;
1860         int             level;
1861
1862         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1863         for (level = 0, i = 2; i == 2; level++) {
1864                 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1865                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1866                         return error;
1867                 }
1868         }
1869         if (i == 0) {
1870                 for (level = 1; level < cur->bc_nlevels; level++) {
1871                         if (cur->bc_ptrs[level] == 0) {
1872                                 if ((error = xfs_bmbt_decrement(cur, level,
1873                                                 &i))) {
1874                                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1875                                         return error;
1876                                 }
1877                                 break;
1878                         }
1879                 }
1880         }
1881         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1882         *stat = i;
1883         return 0;
1884 }
1885
1886 /*
1887  * Convert a compressed bmap extent record to an uncompressed form.
1888  * This code must be in sync with the routines xfs_bmbt_get_startoff,
1889  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1890  */
1891
1892 STATIC __inline__ void
1893 __xfs_bmbt_get_all(
1894                 __uint64_t l0,
1895                 __uint64_t l1,
1896                 xfs_bmbt_irec_t *s)
1897 {
1898         int     ext_flag;
1899         xfs_exntst_t st;
1900
1901         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1902         s->br_startoff = ((xfs_fileoff_t)l0 &
1903                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1904 #if XFS_BIG_BLKNOS
1905         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1906                            (((xfs_fsblock_t)l1) >> 21);
1907 #else
1908 #ifdef DEBUG
1909         {
1910                 xfs_dfsbno_t    b;
1911
1912                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1913                     (((xfs_dfsbno_t)l1) >> 21);
1914                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1915                 s->br_startblock = (xfs_fsblock_t)b;
1916         }
1917 #else   /* !DEBUG */
1918         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1919 #endif  /* DEBUG */
1920 #endif  /* XFS_BIG_BLKNOS */
1921         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1922         /* This is xfs_extent_state() in-line */
1923         if (ext_flag) {
1924                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
1925                 st = XFS_EXT_UNWRITTEN;
1926         } else
1927                 st = XFS_EXT_NORM;
1928         s->br_state = st;
1929 }
1930
1931 void
1932 xfs_bmbt_get_all(
1933         xfs_bmbt_rec_t  *r,
1934         xfs_bmbt_irec_t *s)
1935 {
1936         __xfs_bmbt_get_all(r->l0, r->l1, s);
1937 }
1938
1939 /*
1940  * Get the block pointer for the given level of the cursor.
1941  * Fill in the buffer pointer, if applicable.
1942  */
1943 xfs_bmbt_block_t *
1944 xfs_bmbt_get_block(
1945         xfs_btree_cur_t         *cur,
1946         int                     level,
1947         xfs_buf_t               **bpp)
1948 {
1949         xfs_ifork_t             *ifp;
1950         xfs_bmbt_block_t        *rval;
1951
1952         if (level < cur->bc_nlevels - 1) {
1953                 *bpp = cur->bc_bufs[level];
1954                 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1955         } else {
1956                 *bpp = NULL;
1957                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1958                         cur->bc_private.b.whichfork);
1959                 rval = ifp->if_broot;
1960         }
1961         return rval;
1962 }
1963
1964 /*
1965  * Extract the blockcount field from an in memory bmap extent record.
1966  */
1967 xfs_filblks_t
1968 xfs_bmbt_get_blockcount(
1969         xfs_bmbt_rec_t  *r)
1970 {
1971         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1972 }
1973
1974 /*
1975  * Extract the startblock field from an in memory bmap extent record.
1976  */
1977 xfs_fsblock_t
1978 xfs_bmbt_get_startblock(
1979         xfs_bmbt_rec_t  *r)
1980 {
1981 #if XFS_BIG_BLKNOS
1982         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1983                (((xfs_fsblock_t)r->l1) >> 21);
1984 #else
1985 #ifdef DEBUG
1986         xfs_dfsbno_t    b;
1987
1988         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1989             (((xfs_dfsbno_t)r->l1) >> 21);
1990         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1991         return (xfs_fsblock_t)b;
1992 #else   /* !DEBUG */
1993         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1994 #endif  /* DEBUG */
1995 #endif  /* XFS_BIG_BLKNOS */
1996 }
1997
1998 /*
1999  * Extract the startoff field from an in memory bmap extent record.
2000  */
2001 xfs_fileoff_t
2002 xfs_bmbt_get_startoff(
2003         xfs_bmbt_rec_t  *r)
2004 {
2005         return ((xfs_fileoff_t)r->l0 &
2006                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
2007 }
2008
2009 xfs_exntst_t
2010 xfs_bmbt_get_state(
2011         xfs_bmbt_rec_t  *r)
2012 {
2013         int     ext_flag;
2014
2015         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
2016         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
2017                                 ext_flag);
2018 }
2019
2020 #ifndef XFS_NATIVE_HOST
2021 /* Endian flipping versions of the bmbt extraction functions */
2022 void
2023 xfs_bmbt_disk_get_all(
2024         xfs_bmbt_rec_t  *r,
2025         xfs_bmbt_irec_t *s)
2026 {
2027         __uint64_t      l0, l1;
2028
2029         l0 = INT_GET(r->l0, ARCH_CONVERT);
2030         l1 = INT_GET(r->l1, ARCH_CONVERT);
2031
2032         __xfs_bmbt_get_all(l0, l1, s);
2033 }
2034
2035 /*
2036  * Extract the blockcount field from an on disk bmap extent record.
2037  */
2038 xfs_filblks_t
2039 xfs_bmbt_disk_get_blockcount(
2040         xfs_bmbt_rec_t  *r)
2041 {
2042         return (xfs_filblks_t)(INT_GET(r->l1, ARCH_CONVERT) & XFS_MASK64LO(21));
2043 }
2044
2045 /*
2046  * Extract the startblock field from an on disk bmap extent record.
2047  */
2048 xfs_fsblock_t
2049 xfs_bmbt_disk_get_startblock(
2050         xfs_bmbt_rec_t  *r)
2051 {
2052 #if XFS_BIG_BLKNOS
2053         return (((xfs_fsblock_t)INT_GET(r->l0, ARCH_CONVERT) & XFS_MASK64LO(9)) << 43) |
2054                (((xfs_fsblock_t)INT_GET(r->l1, ARCH_CONVERT)) >> 21);
2055 #else
2056 #ifdef DEBUG
2057         xfs_dfsbno_t    b;
2058
2059         b = (((xfs_dfsbno_t)INT_GET(r->l0, ARCH_CONVERT) & XFS_MASK64LO(9)) << 43) |
2060             (((xfs_dfsbno_t)INT_GET(r->l1, ARCH_CONVERT)) >> 21);
2061         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
2062         return (xfs_fsblock_t)b;
2063 #else   /* !DEBUG */
2064         return (xfs_fsblock_t)(((xfs_dfsbno_t)INT_GET(r->l1, ARCH_CONVERT)) >> 21);
2065 #endif  /* DEBUG */
2066 #endif  /* XFS_BIG_BLKNOS */
2067 }
2068
2069 /*
2070  * Extract the startoff field from a disk format bmap extent record.
2071  */
2072 xfs_fileoff_t
2073 xfs_bmbt_disk_get_startoff(
2074         xfs_bmbt_rec_t  *r)
2075 {
2076         return ((xfs_fileoff_t)INT_GET(r->l0, ARCH_CONVERT) &
2077                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
2078 }
2079
2080 xfs_exntst_t
2081 xfs_bmbt_disk_get_state(
2082         xfs_bmbt_rec_t  *r)
2083 {
2084         int     ext_flag;
2085
2086         ext_flag = (int)((INT_GET(r->l0, ARCH_CONVERT)) >> (64 - BMBT_EXNTFLAG_BITLEN));
2087         return xfs_extent_state(xfs_bmbt_disk_get_blockcount(r),
2088                                 ext_flag);
2089 }
2090 #endif /* XFS_NATIVE_HOST */
2091
2092
2093 /*
2094  * Increment cursor by one record at the level.
2095  * For nonzero levels the leaf-ward information is untouched.
2096  */
2097 int                                             /* error */
2098 xfs_bmbt_increment(
2099         xfs_btree_cur_t         *cur,
2100         int                     level,
2101         int                     *stat)          /* success/failure */
2102 {
2103         xfs_bmbt_block_t        *block;
2104         xfs_buf_t               *bp;
2105         int                     error;          /* error return value */
2106 #ifdef XFS_BMBT_TRACE
2107         static char             fname[] = "xfs_bmbt_increment";
2108 #endif
2109         xfs_fsblock_t           fsbno;
2110         int                     lev;
2111         xfs_mount_t             *mp;
2112         xfs_trans_t             *tp;
2113
2114         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2115         XFS_BMBT_TRACE_ARGI(cur, level);
2116         ASSERT(level < cur->bc_nlevels);
2117         if (level < cur->bc_nlevels - 1)
2118                 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
2119         block = xfs_bmbt_get_block(cur, level, &bp);
2120 #ifdef DEBUG
2121         if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
2122                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2123                 return error;
2124         }
2125 #endif
2126         if (++cur->bc_ptrs[level] <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
2127                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2128                 *stat = 1;
2129                 return 0;
2130         }
2131         if (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO) {
2132                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2133                 *stat = 0;
2134                 return 0;
2135         }
2136         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
2137                 block = xfs_bmbt_get_block(cur, lev, &bp);
2138 #ifdef DEBUG
2139                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2140                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2141                         return error;
2142                 }
2143 #endif
2144                 if (++cur->bc_ptrs[lev] <= INT_GET(block->bb_numrecs, ARCH_CONVERT))
2145                         break;
2146                 if (lev < cur->bc_nlevels - 1)
2147                         xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2148         }
2149         if (lev == cur->bc_nlevels) {
2150                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2151                 *stat = 0;
2152                 return 0;
2153         }
2154         tp = cur->bc_tp;
2155         mp = cur->bc_mp;
2156         for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
2157                 fsbno = INT_GET(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur), ARCH_CONVERT);
2158                 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
2159                                 XFS_BMAP_BTREE_REF))) {
2160                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2161                         return error;
2162                 }
2163                 lev--;
2164                 xfs_btree_setbuf(cur, lev, bp);
2165                 block = XFS_BUF_TO_BMBT_BLOCK(bp);
2166                 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2167                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2168                         return error;
2169                 }
2170                 cur->bc_ptrs[lev] = 1;
2171         }
2172         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2173         *stat = 1;
2174         return 0;
2175 }
2176
2177 /*
2178  * Insert the current record at the point referenced by cur.
2179  */
2180 int                                     /* error */
2181 xfs_bmbt_insert(
2182         xfs_btree_cur_t *cur,
2183         int             *stat)          /* success/failure */
2184 {
2185         int             error;          /* error return value */
2186 #ifdef XFS_BMBT_TRACE
2187         static char     fname[] = "xfs_bmbt_insert";
2188 #endif
2189         int             i;
2190         int             level;
2191         xfs_fsblock_t   nbno;
2192         xfs_btree_cur_t *ncur;
2193         xfs_bmbt_rec_t  nrec;
2194         xfs_btree_cur_t *pcur;
2195
2196         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2197         level = 0;
2198         nbno = NULLFSBLOCK;
2199         xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
2200         ncur = (xfs_btree_cur_t *)0;
2201         pcur = cur;
2202         do {
2203                 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
2204                                 &i))) {
2205                         if (pcur != cur)
2206                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2207                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2208                         return error;
2209                 }
2210                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2211                 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
2212                         cur->bc_nlevels = pcur->bc_nlevels;
2213                         cur->bc_private.b.allocated +=
2214                                 pcur->bc_private.b.allocated;
2215                         pcur->bc_private.b.allocated = 0;
2216                         ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
2217                                (cur->bc_private.b.ip->i_d.di_flags &
2218                                 XFS_DIFLAG_REALTIME));
2219                         cur->bc_private.b.firstblock =
2220                                 pcur->bc_private.b.firstblock;
2221                         ASSERT(cur->bc_private.b.flist ==
2222                                pcur->bc_private.b.flist);
2223                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2224                 }
2225                 if (ncur) {
2226                         pcur = ncur;
2227                         ncur = (xfs_btree_cur_t *)0;
2228                 }
2229         } while (nbno != NULLFSBLOCK);
2230         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2231         *stat = i;
2232         return 0;
2233 error0:
2234         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2235         return error;
2236 }
2237
2238 /*
2239  * Log fields from the btree block header.
2240  */
2241 void
2242 xfs_bmbt_log_block(
2243         xfs_btree_cur_t         *cur,
2244         xfs_buf_t               *bp,
2245         int                     fields)
2246 {
2247         int                     first;
2248 #ifdef XFS_BMBT_TRACE
2249         static char             fname[] = "xfs_bmbt_log_block";
2250 #endif
2251         int                     last;
2252         xfs_trans_t             *tp;
2253         static const short      offsets[] = {
2254                 offsetof(xfs_bmbt_block_t, bb_magic),
2255                 offsetof(xfs_bmbt_block_t, bb_level),
2256                 offsetof(xfs_bmbt_block_t, bb_numrecs),
2257                 offsetof(xfs_bmbt_block_t, bb_leftsib),
2258                 offsetof(xfs_bmbt_block_t, bb_rightsib),
2259                 sizeof(xfs_bmbt_block_t)
2260         };
2261
2262         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2263         XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
2264         tp = cur->bc_tp;
2265         if (bp) {
2266                 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
2267                                   &last);
2268                 xfs_trans_log_buf(tp, bp, first, last);
2269         } else
2270                 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
2271                         XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
2272         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2273 }
2274
2275 /*
2276  * Log record values from the btree block.
2277  */
2278 void
2279 xfs_bmbt_log_recs(
2280         xfs_btree_cur_t         *cur,
2281         xfs_buf_t               *bp,
2282         int                     rfirst,
2283         int                     rlast)
2284 {
2285         xfs_bmbt_block_t        *block;
2286         int                     first;
2287 #ifdef XFS_BMBT_TRACE
2288         static char             fname[] = "xfs_bmbt_log_recs";
2289 #endif
2290         int                     last;
2291         xfs_bmbt_rec_t          *rp;
2292         xfs_trans_t             *tp;
2293
2294         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2295         XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
2296         ASSERT(bp);
2297         tp = cur->bc_tp;
2298         block = XFS_BUF_TO_BMBT_BLOCK(bp);
2299         rp = XFS_BMAP_REC_DADDR(block, 1, cur);
2300         first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
2301         last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
2302         xfs_trans_log_buf(tp, bp, first, last);
2303         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2304 }
2305
2306 int                                     /* error */
2307 xfs_bmbt_lookup_eq(
2308         xfs_btree_cur_t *cur,
2309         xfs_fileoff_t   off,
2310         xfs_fsblock_t   bno,
2311         xfs_filblks_t   len,
2312         int             *stat)          /* success/failure */
2313 {
2314         cur->bc_rec.b.br_startoff = off;
2315         cur->bc_rec.b.br_startblock = bno;
2316         cur->bc_rec.b.br_blockcount = len;
2317         return xfs_bmbt_lookup(cur, XFS_LOOKUP_EQ, stat);
2318 }
2319
2320 int                                     /* error */
2321 xfs_bmbt_lookup_ge(
2322         xfs_btree_cur_t *cur,
2323         xfs_fileoff_t   off,
2324         xfs_fsblock_t   bno,
2325         xfs_filblks_t   len,
2326         int             *stat)          /* success/failure */
2327 {
2328         cur->bc_rec.b.br_startoff = off;
2329         cur->bc_rec.b.br_startblock = bno;
2330         cur->bc_rec.b.br_blockcount = len;
2331         return xfs_bmbt_lookup(cur, XFS_LOOKUP_GE, stat);
2332 }
2333
2334 /*
2335  * Give the bmap btree a new root block.  Copy the old broot contents
2336  * down into a real block and make the broot point to it.
2337  */
2338 int                                             /* error */
2339 xfs_bmbt_newroot(
2340         xfs_btree_cur_t         *cur,           /* btree cursor */
2341         int                     *logflags,      /* logging flags for inode */
2342         int                     *stat)          /* return status - 0 fail */
2343 {
2344         xfs_alloc_arg_t         args;           /* allocation arguments */
2345         xfs_bmbt_block_t        *block;         /* bmap btree block */
2346         xfs_buf_t               *bp;            /* buffer for block */
2347         xfs_bmbt_block_t        *cblock;        /* child btree block */
2348         xfs_bmbt_key_t          *ckp;           /* child key pointer */
2349         xfs_bmbt_ptr_t          *cpp;           /* child ptr pointer */
2350         int                     error;          /* error return code */
2351 #ifdef XFS_BMBT_TRACE
2352         static char             fname[] = "xfs_bmbt_newroot";
2353 #endif
2354 #ifdef DEBUG
2355         int                     i;              /* loop counter */
2356 #endif
2357         xfs_bmbt_key_t          *kp;            /* pointer to bmap btree key */
2358         int                     level;          /* btree level */
2359         xfs_bmbt_ptr_t          *pp;            /* pointer to bmap block addr */
2360
2361         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2362         level = cur->bc_nlevels - 1;
2363         block = xfs_bmbt_get_block(cur, level, &bp);
2364         /*
2365          * Copy the root into a real block.
2366          */
2367         args.mp = cur->bc_mp;
2368         pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
2369         args.tp = cur->bc_tp;
2370         args.fsbno = cur->bc_private.b.firstblock;
2371         args.mod = args.minleft = args.alignment = args.total = args.isfl =
2372                 args.userdata = args.minalignslop = 0;
2373         args.minlen = args.maxlen = args.prod = 1;
2374         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
2375         if (args.fsbno == NULLFSBLOCK) {
2376 #ifdef DEBUG
2377                 if ((error = xfs_btree_check_lptr(cur, INT_GET(*pp, ARCH_CONVERT), level))) {
2378                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2379                         return error;
2380                 }
2381 #endif
2382                 args.fsbno = INT_GET(*pp, ARCH_CONVERT);
2383                 args.type = XFS_ALLOCTYPE_START_BNO;
2384         } else if (args.wasdel)
2385                 args.type = XFS_ALLOCTYPE_FIRST_AG;
2386         else
2387                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
2388         if ((error = xfs_alloc_vextent(&args))) {
2389                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2390                 return error;
2391         }
2392         if (args.fsbno == NULLFSBLOCK) {
2393                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2394                 *stat = 0;
2395                 return 0;
2396         }
2397         ASSERT(args.len == 1);
2398         cur->bc_private.b.firstblock = args.fsbno;
2399         cur->bc_private.b.allocated++;
2400         cur->bc_private.b.ip->i_d.di_nblocks++;
2401         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
2402                           XFS_TRANS_DQ_BCOUNT, 1L);
2403         bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
2404         cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
2405         *cblock = *block;
2406         INT_MOD(block->bb_level, ARCH_CONVERT, +1);
2407         INT_SET(block->bb_numrecs, ARCH_CONVERT, 1);
2408         cur->bc_nlevels++;
2409         cur->bc_ptrs[level + 1] = 1;
2410         kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
2411         ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
2412         memcpy(ckp, kp, INT_GET(cblock->bb_numrecs, ARCH_CONVERT) * sizeof(*kp));
2413         cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
2414 #ifdef DEBUG
2415         for (i = 0; i < INT_GET(cblock->bb_numrecs, ARCH_CONVERT); i++) {
2416                 if ((error = xfs_btree_check_lptr(cur, INT_GET(pp[i], ARCH_CONVERT), level))) {
2417                         XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2418                         return error;
2419                 }
2420         }
2421 #endif
2422         memcpy(cpp, pp, INT_GET(cblock->bb_numrecs, ARCH_CONVERT) * sizeof(*pp));
2423 #ifdef DEBUG
2424         if ((error = xfs_btree_check_lptr(cur, (xfs_bmbt_ptr_t)args.fsbno,
2425                         level))) {
2426                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2427                 return error;
2428         }
2429 #endif
2430         INT_SET(*pp, ARCH_CONVERT, args.fsbno);
2431         xfs_iroot_realloc(cur->bc_private.b.ip, 1 - INT_GET(cblock->bb_numrecs, ARCH_CONVERT),
2432                 cur->bc_private.b.whichfork);
2433         xfs_btree_setbuf(cur, level, bp);
2434         /*
2435          * Do all this logging at the end so that
2436          * the root is at the right level.
2437          */
2438         xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
2439         xfs_bmbt_log_keys(cur, bp, 1, INT_GET(cblock->bb_numrecs, ARCH_CONVERT));
2440         xfs_bmbt_log_ptrs(cur, bp, 1, INT_GET(cblock->bb_numrecs, ARCH_CONVERT));
2441         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2442         *logflags |=
2443                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
2444         *stat = 1;
2445         return 0;
2446 }
2447
2448 /*
2449  * Set all the fields in a bmap extent record from the uncompressed form.
2450  */
2451 void
2452 xfs_bmbt_set_all(
2453         xfs_bmbt_rec_t  *r,
2454         xfs_bmbt_irec_t *s)
2455 {
2456         int     extent_flag;
2457
2458         ASSERT((s->br_state == XFS_EXT_NORM) ||
2459                 (s->br_state == XFS_EXT_UNWRITTEN));
2460         extent_flag = (s->br_state == XFS_EXT_NORM) ? 0 : 1;
2461         ASSERT((s->br_startoff & XFS_MASK64HI(9)) == 0);
2462         ASSERT((s->br_blockcount & XFS_MASK64HI(43)) == 0);
2463 #if XFS_BIG_BLKNOS
2464         ASSERT((s->br_startblock & XFS_MASK64HI(12)) == 0);
2465         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2466                  ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2467                  ((xfs_bmbt_rec_base_t)s->br_startblock >> 43);
2468         r->l1 = ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2469                  ((xfs_bmbt_rec_base_t)s->br_blockcount &
2470                  (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2471 #else   /* !XFS_BIG_BLKNOS */
2472         if (ISNULLSTARTBLOCK(s->br_startblock)) {
2473                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2474                         ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2475                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2476                 r->l1 = XFS_MASK64HI(11) |
2477                           ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2478                           ((xfs_bmbt_rec_base_t)s->br_blockcount &
2479                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2480         } else {
2481                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2482                         ((xfs_bmbt_rec_base_t)s->br_startoff << 9);
2483                 r->l1 = ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2484                           ((xfs_bmbt_rec_base_t)s->br_blockcount &
2485                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2486         }
2487 #endif  /* XFS_BIG_BLKNOS */
2488 }
2489
2490 /*
2491  * Set all the fields in a bmap extent record from the arguments.
2492  */
2493 void
2494 xfs_bmbt_set_allf(
2495         xfs_bmbt_rec_t  *r,
2496         xfs_fileoff_t   o,
2497         xfs_fsblock_t   b,
2498         xfs_filblks_t   c,
2499         xfs_exntst_t    v)
2500 {
2501         int     extent_flag;
2502
2503         ASSERT((v == XFS_EXT_NORM) || (v == XFS_EXT_UNWRITTEN));
2504         extent_flag = (v == XFS_EXT_NORM) ? 0 : 1;
2505         ASSERT((o & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2506         ASSERT((c & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2507 #if XFS_BIG_BLKNOS
2508         ASSERT((b & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2509         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2510                 ((xfs_bmbt_rec_base_t)o << 9) |
2511                 ((xfs_bmbt_rec_base_t)b >> 43);
2512         r->l1 = ((xfs_bmbt_rec_base_t)b << 21) |
2513                 ((xfs_bmbt_rec_base_t)c &
2514                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2515 #else   /* !XFS_BIG_BLKNOS */
2516         if (ISNULLSTARTBLOCK(b)) {
2517                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2518                         ((xfs_bmbt_rec_base_t)o << 9) |
2519                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2520                 r->l1 = XFS_MASK64HI(11) |
2521                           ((xfs_bmbt_rec_base_t)b << 21) |
2522                           ((xfs_bmbt_rec_base_t)c &
2523                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2524         } else {
2525                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2526                         ((xfs_bmbt_rec_base_t)o << 9);
2527                 r->l1 = ((xfs_bmbt_rec_base_t)b << 21) |
2528                          ((xfs_bmbt_rec_base_t)c &
2529                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2530         }
2531 #endif  /* XFS_BIG_BLKNOS */
2532 }
2533
2534 #ifndef XFS_NATIVE_HOST
2535 /*
2536  * Set all the fields in a bmap extent record from the uncompressed form.
2537  */
2538 void
2539 xfs_bmbt_disk_set_all(
2540         xfs_bmbt_rec_t  *r,
2541         xfs_bmbt_irec_t *s)
2542 {
2543         int     extent_flag;
2544
2545         ASSERT((s->br_state == XFS_EXT_NORM) ||
2546                 (s->br_state == XFS_EXT_UNWRITTEN));
2547         extent_flag = (s->br_state == XFS_EXT_NORM) ? 0 : 1;
2548         ASSERT((s->br_startoff & XFS_MASK64HI(9)) == 0);
2549         ASSERT((s->br_blockcount & XFS_MASK64HI(43)) == 0);
2550 #if XFS_BIG_BLKNOS
2551         ASSERT((s->br_startblock & XFS_MASK64HI(12)) == 0);
2552         INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2553                   ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2554                   ((xfs_bmbt_rec_base_t)s->br_startblock >> 43));
2555         INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2556                   ((xfs_bmbt_rec_base_t)s->br_blockcount &
2557                    (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2558 #else   /* !XFS_BIG_BLKNOS */
2559         if (ISNULLSTARTBLOCK(s->br_startblock)) {
2560                 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2561                         ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2562                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2563                 INT_SET(r->l1, ARCH_CONVERT, XFS_MASK64HI(11) |
2564                           ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2565                           ((xfs_bmbt_rec_base_t)s->br_blockcount &
2566                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2567         } else {
2568                 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2569                         ((xfs_bmbt_rec_base_t)s->br_startoff << 9));
2570                 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2571                           ((xfs_bmbt_rec_base_t)s->br_blockcount &
2572                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2573         }
2574 #endif  /* XFS_BIG_BLKNOS */
2575 }
2576
2577 /*
2578  * Set all the fields in a disk format bmap extent record from the arguments.
2579  */
2580 void
2581 xfs_bmbt_disk_set_allf(
2582         xfs_bmbt_rec_t  *r,
2583         xfs_fileoff_t   o,
2584         xfs_fsblock_t   b,
2585         xfs_filblks_t   c,
2586         xfs_exntst_t    v)
2587 {
2588         int     extent_flag;
2589
2590         ASSERT((v == XFS_EXT_NORM) || (v == XFS_EXT_UNWRITTEN));
2591         extent_flag = (v == XFS_EXT_NORM) ? 0 : 1;
2592         ASSERT((o & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2593         ASSERT((c & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2594 #if XFS_BIG_BLKNOS
2595         ASSERT((b & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2596         INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2597                 ((xfs_bmbt_rec_base_t)o << 9) |
2598                 ((xfs_bmbt_rec_base_t)b >> 43));
2599         INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)b << 21) |
2600                   ((xfs_bmbt_rec_base_t)c &
2601                    (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2602 #else   /* !XFS_BIG_BLKNOS */
2603         if (ISNULLSTARTBLOCK(b)) {
2604                 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2605                         ((xfs_bmbt_rec_base_t)o << 9) |
2606                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2607                 INT_SET(r->l1, ARCH_CONVERT, XFS_MASK64HI(11) |
2608                           ((xfs_bmbt_rec_base_t)b << 21) |
2609                           ((xfs_bmbt_rec_base_t)c &
2610                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2611         } else {
2612                 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2613                         ((xfs_bmbt_rec_base_t)o << 9));
2614                 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)b << 21) |
2615                           ((xfs_bmbt_rec_base_t)c &
2616                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2617         }
2618 #endif  /* XFS_BIG_BLKNOS */
2619 }
2620 #endif /* XFS_NATIVE_HOST */
2621
2622 /*
2623  * Set the blockcount field in a bmap extent record.
2624  */
2625 void
2626 xfs_bmbt_set_blockcount(
2627         xfs_bmbt_rec_t  *r,
2628         xfs_filblks_t   v)
2629 {
2630         ASSERT((v & XFS_MASK64HI(43)) == 0);
2631         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
2632                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
2633 }
2634
2635 /*
2636  * Set the startblock field in a bmap extent record.
2637  */
2638 void
2639 xfs_bmbt_set_startblock(
2640         xfs_bmbt_rec_t  *r,
2641         xfs_fsblock_t   v)
2642 {
2643 #if XFS_BIG_BLKNOS
2644         ASSERT((v & XFS_MASK64HI(12)) == 0);
2645         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
2646                   (xfs_bmbt_rec_base_t)(v >> 43);
2647         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
2648                   (xfs_bmbt_rec_base_t)(v << 21);
2649 #else   /* !XFS_BIG_BLKNOS */
2650         if (ISNULLSTARTBLOCK(v)) {
2651                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2652                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
2653                           ((xfs_bmbt_rec_base_t)v << 21) |
2654                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2655         } else {
2656                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2657                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
2658                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2659         }
2660 #endif  /* XFS_BIG_BLKNOS */
2661 }
2662
2663 /*
2664  * Set the startoff field in a bmap extent record.
2665  */
2666 void
2667 xfs_bmbt_set_startoff(
2668         xfs_bmbt_rec_t  *r,
2669         xfs_fileoff_t   v)
2670 {
2671         ASSERT((v & XFS_MASK64HI(9)) == 0);
2672         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
2673                 ((xfs_bmbt_rec_base_t)v << 9) |
2674                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2675 }
2676
2677 /*
2678  * Set the extent state field in a bmap extent record.
2679  */
2680 void
2681 xfs_bmbt_set_state(
2682         xfs_bmbt_rec_t  *r,
2683         xfs_exntst_t    v)
2684 {
2685         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
2686         if (v == XFS_EXT_NORM)
2687                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
2688         else
2689                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
2690 }
2691
2692 /*
2693  * Convert in-memory form of btree root to on-disk form.
2694  */
2695 void
2696 xfs_bmbt_to_bmdr(
2697         xfs_bmbt_block_t        *rblock,
2698         int                     rblocklen,
2699         xfs_bmdr_block_t        *dblock,
2700         int                     dblocklen)
2701 {
2702         int                     dmxr;
2703         xfs_bmbt_key_t          *fkp;
2704         xfs_bmbt_ptr_t          *fpp;
2705         xfs_bmbt_key_t          *tkp;
2706         xfs_bmbt_ptr_t          *tpp;
2707
2708         ASSERT(INT_GET(rblock->bb_magic, ARCH_CONVERT) == XFS_BMAP_MAGIC);
2709         ASSERT(INT_GET(rblock->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO);
2710         ASSERT(INT_GET(rblock->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO);
2711         ASSERT(INT_GET(rblock->bb_level, ARCH_CONVERT) > 0);
2712         dblock->bb_level = rblock->bb_level;    /* both in on-disk format */
2713         dblock->bb_numrecs = rblock->bb_numrecs;/* both in on-disk format */
2714         dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2715         fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2716         tkp = XFS_BTREE_KEY_ADDR(dblocklen, xfs_bmdr, dblock, 1, dmxr);
2717         fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
2718         tpp = XFS_BTREE_PTR_ADDR(dblocklen, xfs_bmdr, dblock, 1, dmxr);
2719         dmxr = INT_GET(dblock->bb_numrecs, ARCH_CONVERT);
2720         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
2721         memcpy(tpp, fpp, sizeof(*fpp) * dmxr); /* INT_: direct copy */
2722 }
2723
2724 /*
2725  * Update the record to the passed values.
2726  */
2727 int
2728 xfs_bmbt_update(
2729         xfs_btree_cur_t         *cur,
2730         xfs_fileoff_t           off,
2731         xfs_fsblock_t           bno,
2732         xfs_filblks_t           len,
2733         xfs_exntst_t            state)
2734 {
2735         xfs_bmbt_block_t        *block;
2736         xfs_buf_t               *bp;
2737         int                     error;
2738 #ifdef XFS_BMBT_TRACE
2739         static char             fname[] = "xfs_bmbt_update";
2740 #endif
2741         xfs_bmbt_key_t          key;
2742         int                     ptr;
2743         xfs_bmbt_rec_t          *rp;
2744
2745         XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2746         XFS_BMBT_TRACE_ARGFFFI(cur, (xfs_dfiloff_t)off, (xfs_dfsbno_t)bno,
2747                 (xfs_dfilblks_t)len, (int)state);
2748         block = xfs_bmbt_get_block(cur, 0, &bp);
2749 #ifdef DEBUG
2750         if ((error = xfs_btree_check_lblock(cur, block, 0, bp))) {
2751                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2752                 return error;
2753         }
2754 #endif
2755         ptr = cur->bc_ptrs[0];
2756         rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
2757         xfs_bmbt_disk_set_allf(rp, off, bno, len, state);
2758         xfs_bmbt_log_recs(cur, bp, ptr, ptr);
2759         if (ptr > 1) {
2760                 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2761                 return 0;
2762         }
2763         INT_SET(key.br_startoff, ARCH_CONVERT, off);
2764         if ((error = xfs_bmbt_updkey(cur, &key, 1))) {
2765                 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2766                 return error;
2767         }
2768         XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2769         return 0;
2770 }
2771
2772 /*
2773  * Check an extent list, which has just been read, for
2774  * any bit in the extent flag field. ASSERT on debug
2775  * kernels, as this condition should not occur.
2776  * Return an error condition (1) if any flags found,
2777  * otherwise return 0.
2778  */
2779
2780 int
2781 xfs_check_nostate_extents(
2782         xfs_bmbt_rec_t          *ep,
2783         xfs_extnum_t            num)
2784 {
2785         for (; num > 0; num--, ep++) {
2786                 if ((ep->l0 >>
2787                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
2788                         ASSERT(0);
2789                         return 1;
2790                 }
2791         }
2792         return 0;
2793 }