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