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