blob: 3f1383d160e89897ba7f979427c0d30e259ded35 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * 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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * 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
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110019#include "xfs_fs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include "xfs_types.h"
Nathan Scotta844f452005-11-02 14:38:42 +110021#include "xfs_bit.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#include "xfs_log.h"
Nathan Scotta844f452005-11-02 14:38:42 +110023#include "xfs_inum.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#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"
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include "xfs_bmap_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110032#include "xfs_alloc_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include "xfs_ialloc_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110034#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"
Linus Torvalds1da177e2005-04-16 15:20:36 -070041#include "xfs_btree.h"
42#include "xfs_ialloc.h"
43#include "xfs_itable.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070044#include "xfs_bmap.h"
45#include "xfs_error.h"
46#include "xfs_quota.h"
47
48#if defined(XFS_BMBT_TRACE)
49ktrace_t *xfs_bmbt_trace_buf;
50#endif
51
52/*
53 * Prototypes for internal btree functions.
54 */
55
56
57STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
58STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
59STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
60STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
61STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
62STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
63 xfs_bmbt_key_t *, xfs_btree_cur_t **, int *);
64STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);
65
66
67#if defined(XFS_BMBT_TRACE)
68
69static char ARGS[] = "args";
70static char ENTRY[] = "entry";
71static char ERROR[] = "error";
72#undef EXIT
73static char EXIT[] = "exit";
74
75/*
76 * Add a trace buffer entry for the arguments given to the routine,
77 * generic form.
78 */
79STATIC void
80xfs_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 */
120STATIC void
121xfs_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 */
137STATIC void
138xfs_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 */
156STATIC void
157xfs_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 */
175STATIC void
176xfs_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 */
191STATIC void
192xfs_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 */
214STATIC void
215xfs_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 */
243STATIC void
244xfs_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 */
263STATIC void
264xfs_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 */
318STATIC int /* error */
319xfs_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);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100369 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370#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--;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100414 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100450 rbno = be64_to_cpu(block->bb_rightsib);
451 lbno = be64_to_cpu(block->bb_leftsib);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 /*
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
Christoph Hellwig16259e72005-11-02 15:11:25 +1100495 bno = be64_to_cpu(right->bb_leftsib);
496 if (be16_to_cpu(right->bb_numrecs) - 1 >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497 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) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100503 ASSERT(be16_to_cpu(block->bb_numrecs) >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100520 rrecs = be16_to_cpu(right->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700521 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
Christoph Hellwig16259e72005-11-02 15:11:25 +1100551 bno = be64_to_cpu(left->bb_rightsib);
552 if (be16_to_cpu(left->bb_numrecs) - 1 >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553 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) {
Christoph Hellwig16259e72005-11-02 15:11:25 +1100559 ASSERT(be16_to_cpu(block->bb_numrecs) >=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100570 lrecs = be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571 }
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 &&
Christoph Hellwig16259e72005-11-02 15:11:25 +1100577 lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578 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 &&
Christoph Hellwig16259e72005-11-02 15:11:25 +1100592 rrecs + be16_to_cpu(block->bb_numrecs) <=
Linus Torvalds1da177e2005-04-16 15:20:36 -0700593 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100607 lrecs = be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700608 } 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100617 numlrecs = be16_to_cpu(left->bb_numrecs);
618 numrrecs = be16_to_cpu(right->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100642 be16_add(&left->bb_numrecs, numrrecs);
643 left->bb_rightsib = right->bb_rightsib;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100645 if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +1100647 be64_to_cpu(left->bb_rightsib),
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100657 rrblock->bb_leftsib = cpu_to_be64(lbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658 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
681error0:
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 */
691int
692xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +1100714 if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715 *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 */
732STATIC int /* error */
733xfs_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);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100775 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776#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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100857 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700858 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++;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100884 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885 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++;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100893 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700894 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
921STATIC int
922xfs_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 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100958 if (be16_to_cpu(block->bb_numrecs) != 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100969 if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
971 return 0;
972 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100973 ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
974 ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975 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));
Christoph Hellwig16259e72005-11-02 15:11:25 +1100979 i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 if (i) {
981 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
982 block = ifp->if_broot;
983 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100984 be16_add(&block->bb_numrecs, i);
985 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
987 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100988 memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700989 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
990 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
991#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +1100992 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993 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
Christoph Hellwig16259e72005-11-02 15:11:25 +1100999 memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000 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;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001007 be16_add(&block->bb_level, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001008 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 */
1018STATIC void
1019xfs_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 */
1057STATIC void
1058xfs_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 */
1096STATIC int /* error */
1097xfs_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;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001163 if (!(high = be16_to_cpu(block->bb_numrecs))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164 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 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001210 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
1211 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212 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;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001226 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001227 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 */
1240STATIC int /* error */
1241xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001283 if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001284 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;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001294 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295 &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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001304 if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1306 *stat = 0;
1307 return 0;
1308 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001309 lrecs = be16_to_cpu(left->bb_numrecs) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001310 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001331 left->bb_numrecs = cpu_to_be16(lrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001339 rrecs = be16_to_cpu(right->bb_numrecs) - 1;
1340 right->bb_numrecs = cpu_to_be16(rrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341 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 */
1377STATIC int /* error */
1378xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001417 if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1419 *stat = 0;
1420 return 0;
1421 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001422 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001423 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1424 *stat = 0;
1425 return 0;
1426 }
1427 mp = cur->bc_mp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001428 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429 &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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001438 if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001439 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1440 *stat = 0;
1441 return 0;
1442 }
1443 if (level > 0) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11001444 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001446 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1447 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1448#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001449 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001456 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001458#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 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001466 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001468 } else {
Christoph Hellwig16259e72005-11-02 15:11:25 +11001469 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001471 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001472 *rrp = *lrp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001473 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474 INT_SET(key.br_startoff, ARCH_CONVERT,
1475 xfs_bmbt_disk_get_startoff(rrp));
1476 rkp = &key;
1477 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001478 be16_add(&left->bb_numrecs, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001480 be16_add(&right->bb_numrecs, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481#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;
1507error0:
1508 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1509error1:
1510 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1511 return error;
1512}
1513
1514/*
1515 * Determine the extent state.
1516 */
1517/* ARGSUSED */
1518STATIC xfs_exntst_t
1519xfs_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 */
1535STATIC int /* error */
1536xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001611 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001618 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001624 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001625 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001631 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001635 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001639 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001641 keyp->br_startoff = xfs_bmbt_disk_get_startoff(rrp);
1642 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001643 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001647 xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1648 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001649 if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001650 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001651 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001652 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001661 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001662 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1663 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001664 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001665 xfs_btree_setbuf(cur, level, rbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001666 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001667 }
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 */
1685STATIC int
1686xfs_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 */
1725void
1726xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001738 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001744 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001749 dmxr = be16_to_cpu(dblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001750 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 */
1758int /* error */
1759xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11001792 if (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001793 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 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001824 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001825 }
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 */
1834int /* error */
1835xfs_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
1876STATIC __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
1915void
1916xfs_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 */
1927xfs_bmbt_block_t *
1928xfs_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 */
1951xfs_filblks_t
1952xfs_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 */
1961xfs_fsblock_t
1962xfs_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 */
1985xfs_fileoff_t
1986xfs_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
1993xfs_exntst_t
1994xfs_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
Nathan Scottf016bad2005-09-08 15:30:05 +10002004#ifndef XFS_NATIVE_HOST
Linus Torvalds1da177e2005-04-16 15:20:36 -07002005/* Endian flipping versions of the bmbt extraction functions */
2006void
2007xfs_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 */
2022xfs_filblks_t
2023xfs_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 */
2032xfs_fsblock_t
2033xfs_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 */
2056xfs_fileoff_t
2057xfs_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
2064xfs_exntst_t
2065xfs_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}
Nathan Scottf016bad2005-09-08 15:30:05 +10002074#endif /* XFS_NATIVE_HOST */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002075
2076
2077/*
2078 * Increment cursor by one record at the level.
2079 * For nonzero levels the leaf-ward information is untouched.
2080 */
2081int /* error */
2082xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11002110 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002111 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2112 *stat = 1;
2113 return 0;
2114 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11002115 if (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002116 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11002128 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002129 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 */
2164int /* error */
2165xfs_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;
2217error0:
2218 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2219 return error;
2220}
2221
2222/*
2223 * Log fields from the btree block header.
2224 */
2225void
2226xfs_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 */
2262void
2263xfs_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
2290int /* error */
2291xfs_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
2304int /* error */
2305xfs_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
Linus Torvalds1da177e2005-04-16 15:20:36 -07002318/*
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 */
2322int /* error */
2323xfs_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;
Christoph Hellwig16259e72005-11-02 15:11:25 +11002390 be16_add(&block->bb_level, 1);
2391 block->bb_numrecs = cpu_to_be16(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002392 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002396 memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002397 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
2398#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11002399 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002400 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
Christoph Hellwig16259e72005-11-02 15:11:25 +11002406 memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002407#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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002415 xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
Linus Torvalds1da177e2005-04-16 15:20:36 -07002416 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002423 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002425 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 */
2435void
2436xfs_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 */
2477void
2478xfs_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
Nathan Scottf016bad2005-09-08 15:30:05 +10002518#ifndef XFS_NATIVE_HOST
Linus Torvalds1da177e2005-04-16 15:20:36 -07002519/*
2520 * Set all the fields in a bmap extent record from the uncompressed form.
2521 */
2522void
2523xfs_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 */
2564void
2565xfs_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}
Nathan Scottf016bad2005-09-08 15:30:05 +10002604#endif /* XFS_NATIVE_HOST */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002605
2606/*
2607 * Set the blockcount field in a bmap extent record.
2608 */
2609void
2610xfs_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 */
2622void
2623xfs_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 */
2650void
2651xfs_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 */
2664void
2665xfs_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 */
2679void
2680xfs_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
Christoph Hellwig16259e72005-11-02 15:11:25 +11002692 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002698 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);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002703 dmxr = be16_to_cpu(dblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002704 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 */
2711int
2712xfs_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 an extent list, which has 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
2764int
2765xfs_check_nostate_extents(
2766 xfs_bmbt_rec_t *ep,
2767 xfs_extnum_t num)
2768{
2769 for (; num > 0; num--, ep++) {
2770 if ((ep->l0 >>
2771 (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
2772 ASSERT(0);
2773 return 1;
2774 }
2775 }
2776 return 0;
2777}