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