blob: 0bf192fea3eb3fe59807b4a00cb1c0cb84670b6a [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
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681/*
682 * Insert one record/level. Return information to the caller
683 * allowing the next level up to proceed if necessary.
684 */
685STATIC int /* error */
686xfs_bmbt_insrec(
687 xfs_btree_cur_t *cur,
688 int level,
689 xfs_fsblock_t *bnop,
690 xfs_bmbt_rec_t *recp,
691 xfs_btree_cur_t **curp,
692 int *stat) /* no-go/done/continue */
693{
694 xfs_bmbt_block_t *block; /* bmap btree block */
695 xfs_buf_t *bp; /* buffer for block */
696 int error; /* error return value */
697#ifdef XFS_BMBT_TRACE
698 static char fname[] = "xfs_bmbt_insrec";
699#endif
700 int i; /* loop index */
701 xfs_bmbt_key_t key; /* bmap btree key */
702 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
703 int logflags; /* inode logging flags */
704 xfs_fsblock_t nbno; /* new block number */
705 struct xfs_btree_cur *ncur; /* new btree cursor */
Christoph Hellwig8801bb92006-09-28 10:58:17 +1000706 __uint64_t startoff; /* new btree key value */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700707 xfs_bmbt_rec_t nrec; /* new record count */
708 int optr; /* old key/record index */
709 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
710 int ptr; /* key/record index */
711 xfs_bmbt_rec_t *rp=NULL; /* pointer to bmap btree rec */
712 int numrecs;
713
714 ASSERT(level < cur->bc_nlevels);
715 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
716 XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
Nathan Scott1121b212006-09-28 10:58:40 +1000717 ncur = NULL;
Christoph Hellwig8801bb92006-09-28 10:58:17 +1000718 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700719 optr = ptr = cur->bc_ptrs[level];
720 if (ptr == 0) {
721 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
722 *stat = 0;
723 return 0;
724 }
725 XFS_STATS_INC(xs_bmbt_insrec);
726 block = xfs_bmbt_get_block(cur, level, &bp);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100727 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700728#ifdef DEBUG
729 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
730 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
731 return error;
732 }
733 if (ptr <= numrecs) {
734 if (level == 0) {
735 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
736 xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
737 } else {
738 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
739 xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
740 }
741 }
742#endif
743 nbno = NULLFSBLOCK;
744 if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
745 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
746 /*
747 * A root block, that can be made bigger.
748 */
749 xfs_iroot_realloc(cur->bc_private.b.ip, 1,
750 cur->bc_private.b.whichfork);
751 block = xfs_bmbt_get_block(cur, level, &bp);
752 } else if (level == cur->bc_nlevels - 1) {
753 if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
754 *stat == 0) {
755 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
756 return error;
757 }
758 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
759 logflags);
760 block = xfs_bmbt_get_block(cur, level, &bp);
761 } else {
762 if ((error = xfs_bmbt_rshift(cur, level, &i))) {
763 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
764 return error;
765 }
766 if (i) {
767 /* nothing */
768 } else {
769 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
770 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
771 return error;
772 }
773 if (i) {
774 optr = ptr = cur->bc_ptrs[level];
775 } else {
776 if ((error = xfs_bmbt_split(cur, level,
Christoph Hellwig8801bb92006-09-28 10:58:17 +1000777 &nbno, &startoff, &ncur,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700778 &i))) {
779 XFS_BMBT_TRACE_CURSOR(cur,
780 ERROR);
781 return error;
782 }
783 if (i) {
784 block = xfs_bmbt_get_block(
785 cur, level, &bp);
786#ifdef DEBUG
787 if ((error =
788 xfs_btree_check_lblock(cur,
789 block, level, bp))) {
790 XFS_BMBT_TRACE_CURSOR(
791 cur, ERROR);
792 return error;
793 }
794#endif
795 ptr = cur->bc_ptrs[level];
796 xfs_bmbt_disk_set_allf(&nrec,
Christoph Hellwig8801bb92006-09-28 10:58:17 +1000797 startoff, 0, 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798 XFS_EXT_NORM);
799 } else {
800 XFS_BMBT_TRACE_CURSOR(cur,
801 EXIT);
802 *stat = 0;
803 return 0;
804 }
805 }
806 }
807 }
808 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100809 numrecs = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810 if (level > 0) {
811 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
812 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
813#ifdef DEBUG
814 for (i = numrecs; i >= ptr; i--) {
Christoph Hellwigb113bcb2006-09-28 10:57:42 +1000815 if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
Linus Torvalds1da177e2005-04-16 15:20:36 -0700816 level))) {
817 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
818 return error;
819 }
820 }
821#endif
822 memmove(&kp[ptr], &kp[ptr - 1],
823 (numrecs - ptr + 1) * sizeof(*kp));
824 memmove(&pp[ptr], &pp[ptr - 1], /* INT_: direct copy */
825 (numrecs - ptr + 1) * sizeof(*pp));
826#ifdef DEBUG
Christoph Hellwig576039c2006-09-28 10:58:06 +1000827 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
829 return error;
830 }
831#endif
832 kp[ptr - 1] = key;
Christoph Hellwig576039c2006-09-28 10:58:06 +1000833 pp[ptr - 1] = cpu_to_be64(*bnop);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700834 numrecs++;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100835 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
837 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
838 } else {
839 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
840 memmove(&rp[ptr], &rp[ptr - 1],
841 (numrecs - ptr + 1) * sizeof(*rp));
842 rp[ptr - 1] = *recp;
843 numrecs++;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100844 block->bb_numrecs = cpu_to_be16(numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700845 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
846 }
847 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
848#ifdef DEBUG
849 if (ptr < numrecs) {
850 if (level == 0)
851 xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
852 rp + ptr);
853 else
854 xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
855 kp + ptr);
856 }
857#endif
858 if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
859 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
860 return error;
861 }
862 *bnop = nbno;
863 if (nbno != NULLFSBLOCK) {
864 *recp = nrec;
865 *curp = ncur;
866 }
867 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
868 *stat = 1;
869 return 0;
870}
871
872STATIC int
873xfs_bmbt_killroot(
874 xfs_btree_cur_t *cur)
875{
876 xfs_bmbt_block_t *block;
877 xfs_bmbt_block_t *cblock;
878 xfs_buf_t *cbp;
879 xfs_bmbt_key_t *ckp;
880 xfs_bmbt_ptr_t *cpp;
881#ifdef DEBUG
882 int error;
883#endif
884#ifdef XFS_BMBT_TRACE
885 static char fname[] = "xfs_bmbt_killroot";
886#endif
887 int i;
888 xfs_bmbt_key_t *kp;
889 xfs_inode_t *ip;
890 xfs_ifork_t *ifp;
891 int level;
892 xfs_bmbt_ptr_t *pp;
893
894 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
895 level = cur->bc_nlevels - 1;
896 ASSERT(level >= 1);
897 /*
898 * Don't deal with the root block needs to be a leaf case.
899 * We're just going to turn the thing back into extents anyway.
900 */
901 if (level == 1) {
902 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
903 return 0;
904 }
905 block = xfs_bmbt_get_block(cur, level, &cbp);
906 /*
907 * Give up if the root has multiple children.
908 */
Christoph Hellwig16259e72005-11-02 15:11:25 +1100909 if (be16_to_cpu(block->bb_numrecs) != 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
911 return 0;
912 }
913 /*
914 * Only do this if the next level will fit.
915 * Then the data must be copied up to the inode,
916 * instead of freeing the root you free the next level.
917 */
918 cbp = cur->bc_bufs[level - 1];
919 cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100920 if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
922 return 0;
923 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100924 ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
925 ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 ip = cur->bc_private.b.ip;
927 ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
928 ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
929 XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
Christoph Hellwig16259e72005-11-02 15:11:25 +1100930 i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931 if (i) {
932 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
933 block = ifp->if_broot;
934 }
Christoph Hellwig16259e72005-11-02 15:11:25 +1100935 be16_add(&block->bb_numrecs, i);
936 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
938 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100939 memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
941 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
942#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +1100943 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
Christoph Hellwigb113bcb2006-09-28 10:57:42 +1000944 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
946 return error;
947 }
948 }
949#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +1100950 memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700951 xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
952 cur->bc_private.b.flist, cur->bc_mp);
953 ip->i_d.di_nblocks--;
954 XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
955 XFS_TRANS_DQ_BCOUNT, -1L);
956 xfs_trans_binval(cur->bc_tp, cbp);
957 cur->bc_bufs[level - 1] = NULL;
Christoph Hellwig16259e72005-11-02 15:11:25 +1100958 be16_add(&block->bb_level, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959 xfs_trans_log_inode(cur->bc_tp, ip,
960 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
961 cur->bc_nlevels--;
962 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
963 return 0;
964}
965
966/*
967 * Log key values from the btree block.
968 */
969STATIC void
970xfs_bmbt_log_keys(
971 xfs_btree_cur_t *cur,
972 xfs_buf_t *bp,
973 int kfirst,
974 int klast)
975{
976#ifdef XFS_BMBT_TRACE
977 static char fname[] = "xfs_bmbt_log_keys";
978#endif
979 xfs_trans_t *tp;
980
981 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
982 XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
983 tp = cur->bc_tp;
984 if (bp) {
985 xfs_bmbt_block_t *block;
986 int first;
987 xfs_bmbt_key_t *kp;
988 int last;
989
990 block = XFS_BUF_TO_BMBT_BLOCK(bp);
991 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
992 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
993 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
994 xfs_trans_log_buf(tp, bp, first, last);
995 } else {
996 xfs_inode_t *ip;
997
998 ip = cur->bc_private.b.ip;
999 xfs_trans_log_inode(tp, ip,
1000 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1001 }
1002 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1003}
1004
1005/*
1006 * Log pointer values from the btree block.
1007 */
1008STATIC void
1009xfs_bmbt_log_ptrs(
1010 xfs_btree_cur_t *cur,
1011 xfs_buf_t *bp,
1012 int pfirst,
1013 int plast)
1014{
1015#ifdef XFS_BMBT_TRACE
1016 static char fname[] = "xfs_bmbt_log_ptrs";
1017#endif
1018 xfs_trans_t *tp;
1019
1020 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1021 XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
1022 tp = cur->bc_tp;
1023 if (bp) {
1024 xfs_bmbt_block_t *block;
1025 int first;
1026 int last;
1027 xfs_bmbt_ptr_t *pp;
1028
1029 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1030 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
1031 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
1032 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
1033 xfs_trans_log_buf(tp, bp, first, last);
1034 } else {
1035 xfs_inode_t *ip;
1036
1037 ip = cur->bc_private.b.ip;
1038 xfs_trans_log_inode(tp, ip,
1039 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1040 }
1041 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1042}
1043
1044/*
1045 * Lookup the record. The cursor is made to point to it, based on dir.
1046 */
1047STATIC int /* error */
1048xfs_bmbt_lookup(
1049 xfs_btree_cur_t *cur,
1050 xfs_lookup_t dir,
1051 int *stat) /* success/failure */
1052{
1053 xfs_bmbt_block_t *block=NULL;
1054 xfs_buf_t *bp;
1055 xfs_daddr_t d;
1056 xfs_sfiloff_t diff;
1057 int error; /* error return value */
1058#ifdef XFS_BMBT_TRACE
1059 static char fname[] = "xfs_bmbt_lookup";
1060#endif
1061 xfs_fsblock_t fsbno=0;
1062 int high;
1063 int i;
1064 int keyno=0;
1065 xfs_bmbt_key_t *kkbase=NULL;
1066 xfs_bmbt_key_t *kkp;
1067 xfs_bmbt_rec_t *krbase=NULL;
1068 xfs_bmbt_rec_t *krp;
1069 int level;
1070 int low;
1071 xfs_mount_t *mp;
1072 xfs_bmbt_ptr_t *pp;
1073 xfs_bmbt_irec_t *rp;
1074 xfs_fileoff_t startoff;
1075 xfs_trans_t *tp;
1076
1077 XFS_STATS_INC(xs_bmbt_lookup);
1078 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1079 XFS_BMBT_TRACE_ARGI(cur, (int)dir);
1080 tp = cur->bc_tp;
1081 mp = cur->bc_mp;
1082 rp = &cur->bc_rec.b;
1083 for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1084 if (level < cur->bc_nlevels - 1) {
1085 d = XFS_FSB_TO_DADDR(mp, fsbno);
1086 bp = cur->bc_bufs[level];
1087 if (bp && XFS_BUF_ADDR(bp) != d)
Nathan Scott1121b212006-09-28 10:58:40 +10001088 bp = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001089 if (!bp) {
1090 if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
1091 0, &bp, XFS_BMAP_BTREE_REF))) {
1092 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1093 return error;
1094 }
1095 xfs_btree_setbuf(cur, level, bp);
1096 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1097 if ((error = xfs_btree_check_lblock(cur, block,
1098 level, bp))) {
1099 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1100 return error;
1101 }
1102 } else
1103 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1104 } else
1105 block = xfs_bmbt_get_block(cur, level, &bp);
1106 if (diff == 0)
1107 keyno = 1;
1108 else {
1109 if (level > 0)
1110 kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
1111 else
1112 krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
1113 low = 1;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001114 if (!(high = be16_to_cpu(block->bb_numrecs))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001115 ASSERT(level == 0);
1116 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1117 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1118 *stat = 0;
1119 return 0;
1120 }
1121 while (low <= high) {
1122 XFS_STATS_INC(xs_bmbt_compare);
1123 keyno = (low + high) >> 1;
1124 if (level > 0) {
1125 kkp = kkbase + keyno - 1;
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001126 startoff = be64_to_cpu(kkp->br_startoff);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127 } else {
1128 krp = krbase + keyno - 1;
1129 startoff = xfs_bmbt_disk_get_startoff(krp);
1130 }
1131 diff = (xfs_sfiloff_t)
1132 (startoff - rp->br_startoff);
1133 if (diff < 0)
1134 low = keyno + 1;
1135 else if (diff > 0)
1136 high = keyno - 1;
1137 else
1138 break;
1139 }
1140 }
1141 if (level > 0) {
1142 if (diff > 0 && --keyno < 1)
1143 keyno = 1;
1144 pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
Christoph Hellwig576039c2006-09-28 10:58:06 +10001145 fsbno = be64_to_cpu(*pp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001146#ifdef DEBUG
Christoph Hellwig576039c2006-09-28 10:58:06 +10001147 if ((error = xfs_btree_check_lptr(cur, fsbno, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1149 return error;
1150 }
1151#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001152 cur->bc_ptrs[level] = keyno;
1153 }
1154 }
1155 if (dir != XFS_LOOKUP_LE && diff < 0) {
1156 keyno++;
1157 /*
1158 * If ge search and we went off the end of the block, but it's
1159 * not the last block, we're in the wrong block.
1160 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001161 if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
1162 be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163 cur->bc_ptrs[0] = keyno;
1164 if ((error = xfs_bmbt_increment(cur, 0, &i))) {
1165 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1166 return error;
1167 }
1168 XFS_WANT_CORRUPTED_RETURN(i == 1);
1169 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1170 *stat = 1;
1171 return 0;
1172 }
1173 }
1174 else if (dir == XFS_LOOKUP_LE && diff > 0)
1175 keyno--;
1176 cur->bc_ptrs[0] = keyno;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001177 if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001178 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1179 *stat = 0;
1180 } else {
1181 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1182 *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
1183 }
1184 return 0;
1185}
1186
1187/*
1188 * Move 1 record left from cur/level if possible.
1189 * Update cur to reflect the new path.
1190 */
1191STATIC int /* error */
1192xfs_bmbt_lshift(
1193 xfs_btree_cur_t *cur,
1194 int level,
1195 int *stat) /* success/failure */
1196{
1197 int error; /* error return value */
1198#ifdef XFS_BMBT_TRACE
1199 static char fname[] = "xfs_bmbt_lshift";
1200#endif
1201#ifdef DEBUG
1202 int i; /* loop counter */
1203#endif
1204 xfs_bmbt_key_t key; /* bmap btree key */
1205 xfs_buf_t *lbp; /* left buffer pointer */
1206 xfs_bmbt_block_t *left; /* left btree block */
1207 xfs_bmbt_key_t *lkp=NULL; /* left btree key */
1208 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1209 int lrecs; /* left record count */
1210 xfs_bmbt_rec_t *lrp=NULL; /* left record pointer */
1211 xfs_mount_t *mp; /* file system mount point */
1212 xfs_buf_t *rbp; /* right buffer pointer */
1213 xfs_bmbt_block_t *right; /* right btree block */
1214 xfs_bmbt_key_t *rkp=NULL; /* right btree key */
1215 xfs_bmbt_ptr_t *rpp=NULL; /* right address pointer */
1216 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
1217 int rrecs; /* right record count */
1218
1219 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1220 XFS_BMBT_TRACE_ARGI(cur, level);
1221 if (level == cur->bc_nlevels - 1) {
1222 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1223 *stat = 0;
1224 return 0;
1225 }
1226 rbp = cur->bc_bufs[level];
1227 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1228#ifdef DEBUG
1229 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1230 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1231 return error;
1232 }
1233#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001234 if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001235 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1236 *stat = 0;
1237 return 0;
1238 }
1239 if (cur->bc_ptrs[level] <= 1) {
1240 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1241 *stat = 0;
1242 return 0;
1243 }
1244 mp = cur->bc_mp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001245 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246 &lbp, XFS_BMAP_BTREE_REF))) {
1247 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1248 return error;
1249 }
1250 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1251 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1252 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1253 return error;
1254 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001255 if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001256 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1257 *stat = 0;
1258 return 0;
1259 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001260 lrecs = be16_to_cpu(left->bb_numrecs) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001261 if (level > 0) {
1262 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
1263 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1264 *lkp = *rkp;
1265 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
1266 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
1267 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1268#ifdef DEBUG
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10001269 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001270 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1271 return error;
1272 }
1273#endif
1274 *lpp = *rpp; /* INT_: direct copy */
1275 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
1276 } else {
1277 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
1278 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
1279 *lrp = *rrp;
1280 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
1281 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001282 left->bb_numrecs = cpu_to_be16(lrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001283 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
1284#ifdef DEBUG
1285 if (level > 0)
1286 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
1287 else
1288 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
1289#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001290 rrecs = be16_to_cpu(right->bb_numrecs) - 1;
1291 right->bb_numrecs = cpu_to_be16(rrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001292 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1293 if (level > 0) {
1294#ifdef DEBUG
1295 for (i = 0; i < rrecs; i++) {
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10001296 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
Linus Torvalds1da177e2005-04-16 15:20:36 -07001297 level))) {
1298 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1299 return error;
1300 }
1301 }
1302#endif
1303 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
1304 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
1305 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
1306 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
1307 } else {
1308 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
1309 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001310 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311 rkp = &key;
1312 }
1313 if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
1314 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1315 return error;
1316 }
1317 cur->bc_ptrs[level]--;
1318 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1319 *stat = 1;
1320 return 0;
1321}
1322
1323/*
1324 * Move 1 record right from cur/level if possible.
1325 * Update cur to reflect the new path.
1326 */
1327STATIC int /* error */
1328xfs_bmbt_rshift(
1329 xfs_btree_cur_t *cur,
1330 int level,
1331 int *stat) /* success/failure */
1332{
1333 int error; /* error return value */
1334#ifdef XFS_BMBT_TRACE
1335 static char fname[] = "xfs_bmbt_rshift";
1336#endif
1337 int i; /* loop counter */
1338 xfs_bmbt_key_t key; /* bmap btree key */
1339 xfs_buf_t *lbp; /* left buffer pointer */
1340 xfs_bmbt_block_t *left; /* left btree block */
1341 xfs_bmbt_key_t *lkp; /* left btree key */
1342 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1343 xfs_bmbt_rec_t *lrp; /* left record pointer */
1344 xfs_mount_t *mp; /* file system mount point */
1345 xfs_buf_t *rbp; /* right buffer pointer */
1346 xfs_bmbt_block_t *right; /* right btree block */
1347 xfs_bmbt_key_t *rkp; /* right btree key */
1348 xfs_bmbt_ptr_t *rpp; /* right address pointer */
1349 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
1350 struct xfs_btree_cur *tcur; /* temporary btree cursor */
1351
1352 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1353 XFS_BMBT_TRACE_ARGI(cur, level);
1354 if (level == cur->bc_nlevels - 1) {
1355 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1356 *stat = 0;
1357 return 0;
1358 }
1359 lbp = cur->bc_bufs[level];
1360 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1361#ifdef DEBUG
1362 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
1363 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1364 return error;
1365 }
1366#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001367 if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001368 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1369 *stat = 0;
1370 return 0;
1371 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001372 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001373 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1374 *stat = 0;
1375 return 0;
1376 }
1377 mp = cur->bc_mp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001378 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379 &rbp, XFS_BMAP_BTREE_REF))) {
1380 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1381 return error;
1382 }
1383 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1384 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1385 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1386 return error;
1387 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001388 if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1390 *stat = 0;
1391 return 0;
1392 }
1393 if (level > 0) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11001394 lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1395 lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1397 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1398#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001399 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
Christoph Hellwig576039c2006-09-28 10:58:06 +10001400 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1402 return error;
1403 }
1404 }
1405#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001406 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1407 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001408#ifdef DEBUG
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10001409 if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1411 return error;
1412 }
1413#endif
1414 *rkp = *lkp;
1415 *rpp = *lpp; /* INT_: direct copy */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001416 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1417 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418 } else {
Christoph Hellwig16259e72005-11-02 15:11:25 +11001419 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001420 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001421 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001422 *rrp = *lrp;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001423 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001424 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001425 rkp = &key;
1426 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001427 be16_add(&left->bb_numrecs, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001429 be16_add(&right->bb_numrecs, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430#ifdef DEBUG
1431 if (level > 0)
1432 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1433 else
1434 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1435#endif
1436 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1437 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1438 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1439 return error;
1440 }
1441 i = xfs_btree_lastrec(tcur, level);
1442 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1443 if ((error = xfs_bmbt_increment(tcur, level, &i))) {
1444 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1445 goto error1;
1446 }
1447 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1448 if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {
1449 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1450 goto error1;
1451 }
1452 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1453 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1454 *stat = 1;
1455 return 0;
1456error0:
1457 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1458error1:
1459 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1460 return error;
1461}
1462
1463/*
1464 * Determine the extent state.
1465 */
1466/* ARGSUSED */
1467STATIC xfs_exntst_t
1468xfs_extent_state(
1469 xfs_filblks_t blks,
1470 int extent_flag)
1471{
1472 if (extent_flag) {
1473 ASSERT(blks != 0); /* saved for DMIG */
1474 return XFS_EXT_UNWRITTEN;
1475 }
1476 return XFS_EXT_NORM;
1477}
1478
1479
1480/*
1481 * Split cur/level block in half.
1482 * Return new block number and its first record (to be inserted into parent).
1483 */
1484STATIC int /* error */
1485xfs_bmbt_split(
1486 xfs_btree_cur_t *cur,
1487 int level,
1488 xfs_fsblock_t *bnop,
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001489 __uint64_t *startoff,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001490 xfs_btree_cur_t **curp,
1491 int *stat) /* success/failure */
1492{
1493 xfs_alloc_arg_t args; /* block allocation args */
1494 int error; /* error return value */
1495#ifdef XFS_BMBT_TRACE
1496 static char fname[] = "xfs_bmbt_split";
1497#endif
1498 int i; /* loop counter */
1499 xfs_fsblock_t lbno; /* left sibling block number */
1500 xfs_buf_t *lbp; /* left buffer pointer */
1501 xfs_bmbt_block_t *left; /* left btree block */
1502 xfs_bmbt_key_t *lkp; /* left btree key */
1503 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1504 xfs_bmbt_rec_t *lrp; /* left record pointer */
1505 xfs_buf_t *rbp; /* right buffer pointer */
1506 xfs_bmbt_block_t *right; /* right btree block */
1507 xfs_bmbt_key_t *rkp; /* right btree key */
1508 xfs_bmbt_ptr_t *rpp; /* right address pointer */
1509 xfs_bmbt_block_t *rrblock; /* right-right btree block */
1510 xfs_buf_t *rrbp; /* right-right buffer pointer */
1511 xfs_bmbt_rec_t *rrp; /* right record pointer */
1512
1513 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001514 XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001515 args.tp = cur->bc_tp;
1516 args.mp = cur->bc_mp;
1517 lbp = cur->bc_bufs[level];
1518 lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1519 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1520 args.fsbno = cur->bc_private.b.firstblock;
Yingping Lud210a282006-06-09 14:55:18 +10001521 args.firstblock = args.fsbno;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001522 if (args.fsbno == NULLFSBLOCK) {
1523 args.fsbno = lbno;
1524 args.type = XFS_ALLOCTYPE_START_BNO;
Yingping Lud210a282006-06-09 14:55:18 +10001525 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -07001526 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1527 args.mod = args.minleft = args.alignment = args.total = args.isfl =
1528 args.userdata = args.minalignslop = 0;
1529 args.minlen = args.maxlen = args.prod = 1;
1530 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1531 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1532 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1533 return XFS_ERROR(ENOSPC);
1534 }
1535 if ((error = xfs_alloc_vextent(&args))) {
1536 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1537 return error;
1538 }
1539 if (args.fsbno == NULLFSBLOCK) {
1540 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1541 *stat = 0;
1542 return 0;
1543 }
1544 ASSERT(args.len == 1);
1545 cur->bc_private.b.firstblock = args.fsbno;
1546 cur->bc_private.b.allocated++;
1547 cur->bc_private.b.ip->i_d.di_nblocks++;
1548 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1549 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1550 XFS_TRANS_DQ_BCOUNT, 1L);
1551 rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1552 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1553#ifdef DEBUG
1554 if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1555 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1556 return error;
1557 }
1558#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001559 right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1560 right->bb_level = left->bb_level;
1561 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1562 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1563 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
1564 be16_add(&right->bb_numrecs, 1);
1565 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001566 if (level > 0) {
1567 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1568 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1569 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1570 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1571#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11001572 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10001573 if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1575 return error;
1576 }
1577 }
1578#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001579 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1580 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1581 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1582 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001583 *startoff = be64_to_cpu(rkp->br_startoff);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001584 } else {
1585 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1586 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001587 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1588 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
Christoph Hellwig8801bb92006-09-28 10:58:17 +10001589 *startoff = xfs_bmbt_disk_get_startoff(rrp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001590 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001591 be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
1592 right->bb_rightsib = left->bb_rightsib;
1593 left->bb_rightsib = cpu_to_be64(args.fsbno);
1594 right->bb_leftsib = cpu_to_be64(lbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001595 xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1596 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001597 if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001598 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001599 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001600 XFS_BMAP_BTREE_REF))) {
1601 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1602 return error;
1603 }
1604 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1605 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1606 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1607 return error;
1608 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001609 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001610 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1611 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001612 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001613 xfs_btree_setbuf(cur, level, rbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001614 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001615 }
1616 if (level + 1 < cur->bc_nlevels) {
1617 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1618 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1619 return error;
1620 }
1621 (*curp)->bc_ptrs[level + 1]++;
1622 }
1623 *bnop = args.fsbno;
1624 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1625 *stat = 1;
1626 return 0;
1627}
1628
1629
1630/*
1631 * Update keys for the record.
1632 */
1633STATIC int
1634xfs_bmbt_updkey(
1635 xfs_btree_cur_t *cur,
1636 xfs_bmbt_key_t *keyp, /* on-disk format */
1637 int level)
1638{
1639 xfs_bmbt_block_t *block;
1640 xfs_buf_t *bp;
1641#ifdef DEBUG
1642 int error;
1643#endif
1644#ifdef XFS_BMBT_TRACE
1645 static char fname[] = "xfs_bmbt_updkey";
1646#endif
1647 xfs_bmbt_key_t *kp;
1648 int ptr;
1649
1650 ASSERT(level >= 1);
1651 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1652 XFS_BMBT_TRACE_ARGIK(cur, level, keyp);
1653 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1654 block = xfs_bmbt_get_block(cur, level, &bp);
1655#ifdef DEBUG
1656 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1657 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1658 return error;
1659 }
1660#endif
1661 ptr = cur->bc_ptrs[level];
1662 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
1663 *kp = *keyp;
1664 xfs_bmbt_log_keys(cur, bp, ptr, ptr);
1665 }
1666 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1667 return 0;
1668}
1669
1670/*
1671 * Convert on-disk form of btree root to in-memory form.
1672 */
1673void
1674xfs_bmdr_to_bmbt(
1675 xfs_bmdr_block_t *dblock,
1676 int dblocklen,
1677 xfs_bmbt_block_t *rblock,
1678 int rblocklen)
1679{
1680 int dmxr;
1681 xfs_bmbt_key_t *fkp;
Christoph Hellwig576039c2006-09-28 10:58:06 +10001682 __be64 *fpp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001683 xfs_bmbt_key_t *tkp;
Christoph Hellwig576039c2006-09-28 10:58:06 +10001684 __be64 *tpp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001685
Christoph Hellwig16259e72005-11-02 15:11:25 +11001686 rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1687 rblock->bb_level = dblock->bb_level;
1688 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1689 rblock->bb_numrecs = dblock->bb_numrecs;
1690 rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
1691 rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001692 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
Eric Sandeen2c36dde2007-02-10 18:37:33 +11001693 fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001694 tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
Eric Sandeen2c36dde2007-02-10 18:37:33 +11001695 fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001696 tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001697 dmxr = be16_to_cpu(dblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001698 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
Christoph Hellwig576039c2006-09-28 10:58:06 +10001699 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001700}
1701
1702/*
1703 * Decrement cursor by one record at the level.
1704 * For nonzero levels the leaf-ward information is untouched.
1705 */
1706int /* error */
1707xfs_bmbt_decrement(
1708 xfs_btree_cur_t *cur,
1709 int level,
1710 int *stat) /* success/failure */
1711{
1712 xfs_bmbt_block_t *block;
1713 xfs_buf_t *bp;
1714 int error; /* error return value */
1715#ifdef XFS_BMBT_TRACE
1716 static char fname[] = "xfs_bmbt_decrement";
1717#endif
1718 xfs_fsblock_t fsbno;
1719 int lev;
1720 xfs_mount_t *mp;
1721 xfs_trans_t *tp;
1722
1723 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1724 XFS_BMBT_TRACE_ARGI(cur, level);
1725 ASSERT(level < cur->bc_nlevels);
1726 if (level < cur->bc_nlevels - 1)
1727 xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1728 if (--cur->bc_ptrs[level] > 0) {
1729 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1730 *stat = 1;
1731 return 0;
1732 }
1733 block = xfs_bmbt_get_block(cur, level, &bp);
1734#ifdef DEBUG
1735 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1736 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1737 return error;
1738 }
1739#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11001740 if (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001741 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1742 *stat = 0;
1743 return 0;
1744 }
1745 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1746 if (--cur->bc_ptrs[lev] > 0)
1747 break;
1748 if (lev < cur->bc_nlevels - 1)
1749 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1750 }
1751 if (lev == cur->bc_nlevels) {
1752 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1753 *stat = 0;
1754 return 0;
1755 }
1756 tp = cur->bc_tp;
1757 mp = cur->bc_mp;
1758 for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
Christoph Hellwig576039c2006-09-28 10:58:06 +10001759 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
1761 XFS_BMAP_BTREE_REF))) {
1762 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1763 return error;
1764 }
1765 lev--;
1766 xfs_btree_setbuf(cur, lev, bp);
1767 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1768 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
1769 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1770 return error;
1771 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11001772 cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001773 }
1774 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1775 *stat = 1;
1776 return 0;
1777}
1778
1779/*
1780 * Delete the record pointed to by cur.
1781 */
1782int /* error */
1783xfs_bmbt_delete(
1784 xfs_btree_cur_t *cur,
1785 int *stat) /* success/failure */
1786{
1787 int error; /* error return value */
1788#ifdef XFS_BMBT_TRACE
1789 static char fname[] = "xfs_bmbt_delete";
1790#endif
1791 int i;
1792 int level;
1793
1794 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1795 for (level = 0, i = 2; i == 2; level++) {
1796 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1797 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1798 return error;
1799 }
1800 }
1801 if (i == 0) {
1802 for (level = 1; level < cur->bc_nlevels; level++) {
1803 if (cur->bc_ptrs[level] == 0) {
1804 if ((error = xfs_bmbt_decrement(cur, level,
1805 &i))) {
1806 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1807 return error;
1808 }
1809 break;
1810 }
1811 }
1812 }
1813 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1814 *stat = i;
1815 return 0;
1816}
1817
1818/*
1819 * Convert a compressed bmap extent record to an uncompressed form.
1820 * This code must be in sync with the routines xfs_bmbt_get_startoff,
1821 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1822 */
1823
David Chinner7989cb82007-02-10 18:34:56 +11001824STATIC_INLINE void
Linus Torvalds1da177e2005-04-16 15:20:36 -07001825__xfs_bmbt_get_all(
1826 __uint64_t l0,
1827 __uint64_t l1,
1828 xfs_bmbt_irec_t *s)
1829{
1830 int ext_flag;
1831 xfs_exntst_t st;
1832
1833 ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1834 s->br_startoff = ((xfs_fileoff_t)l0 &
1835 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1836#if XFS_BIG_BLKNOS
1837 s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1838 (((xfs_fsblock_t)l1) >> 21);
1839#else
1840#ifdef DEBUG
1841 {
1842 xfs_dfsbno_t b;
1843
1844 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1845 (((xfs_dfsbno_t)l1) >> 21);
1846 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1847 s->br_startblock = (xfs_fsblock_t)b;
1848 }
1849#else /* !DEBUG */
1850 s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1851#endif /* DEBUG */
1852#endif /* XFS_BIG_BLKNOS */
1853 s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1854 /* This is xfs_extent_state() in-line */
1855 if (ext_flag) {
1856 ASSERT(s->br_blockcount != 0); /* saved for DMIG */
1857 st = XFS_EXT_UNWRITTEN;
1858 } else
1859 st = XFS_EXT_NORM;
1860 s->br_state = st;
1861}
1862
1863void
1864xfs_bmbt_get_all(
1865 xfs_bmbt_rec_t *r,
1866 xfs_bmbt_irec_t *s)
1867{
1868 __xfs_bmbt_get_all(r->l0, r->l1, s);
1869}
1870
1871/*
1872 * Get the block pointer for the given level of the cursor.
1873 * Fill in the buffer pointer, if applicable.
1874 */
1875xfs_bmbt_block_t *
1876xfs_bmbt_get_block(
1877 xfs_btree_cur_t *cur,
1878 int level,
1879 xfs_buf_t **bpp)
1880{
1881 xfs_ifork_t *ifp;
1882 xfs_bmbt_block_t *rval;
1883
1884 if (level < cur->bc_nlevels - 1) {
1885 *bpp = cur->bc_bufs[level];
1886 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1887 } else {
1888 *bpp = NULL;
1889 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1890 cur->bc_private.b.whichfork);
1891 rval = ifp->if_broot;
1892 }
1893 return rval;
1894}
1895
1896/*
1897 * Extract the blockcount field from an in memory bmap extent record.
1898 */
1899xfs_filblks_t
1900xfs_bmbt_get_blockcount(
1901 xfs_bmbt_rec_t *r)
1902{
1903 return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1904}
1905
1906/*
1907 * Extract the startblock field from an in memory bmap extent record.
1908 */
1909xfs_fsblock_t
1910xfs_bmbt_get_startblock(
1911 xfs_bmbt_rec_t *r)
1912{
1913#if XFS_BIG_BLKNOS
1914 return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1915 (((xfs_fsblock_t)r->l1) >> 21);
1916#else
1917#ifdef DEBUG
1918 xfs_dfsbno_t b;
1919
1920 b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1921 (((xfs_dfsbno_t)r->l1) >> 21);
1922 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1923 return (xfs_fsblock_t)b;
1924#else /* !DEBUG */
1925 return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1926#endif /* DEBUG */
1927#endif /* XFS_BIG_BLKNOS */
1928}
1929
1930/*
1931 * Extract the startoff field from an in memory bmap extent record.
1932 */
1933xfs_fileoff_t
1934xfs_bmbt_get_startoff(
1935 xfs_bmbt_rec_t *r)
1936{
1937 return ((xfs_fileoff_t)r->l0 &
1938 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1939}
1940
1941xfs_exntst_t
1942xfs_bmbt_get_state(
1943 xfs_bmbt_rec_t *r)
1944{
1945 int ext_flag;
1946
1947 ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
1948 return xfs_extent_state(xfs_bmbt_get_blockcount(r),
1949 ext_flag);
1950}
1951
Nathan Scottf016bad2005-09-08 15:30:05 +10001952#ifndef XFS_NATIVE_HOST
Linus Torvalds1da177e2005-04-16 15:20:36 -07001953/* Endian flipping versions of the bmbt extraction functions */
1954void
1955xfs_bmbt_disk_get_all(
1956 xfs_bmbt_rec_t *r,
1957 xfs_bmbt_irec_t *s)
1958{
1959 __uint64_t l0, l1;
1960
1961 l0 = INT_GET(r->l0, ARCH_CONVERT);
1962 l1 = INT_GET(r->l1, ARCH_CONVERT);
1963
1964 __xfs_bmbt_get_all(l0, l1, s);
1965}
1966
1967/*
1968 * Extract the blockcount field from an on disk bmap extent record.
1969 */
1970xfs_filblks_t
1971xfs_bmbt_disk_get_blockcount(
1972 xfs_bmbt_rec_t *r)
1973{
1974 return (xfs_filblks_t)(INT_GET(r->l1, ARCH_CONVERT) & XFS_MASK64LO(21));
1975}
1976
1977/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001978 * Extract the startoff field from a disk format bmap extent record.
1979 */
1980xfs_fileoff_t
1981xfs_bmbt_disk_get_startoff(
1982 xfs_bmbt_rec_t *r)
1983{
1984 return ((xfs_fileoff_t)INT_GET(r->l0, ARCH_CONVERT) &
1985 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1986}
Nathan Scottf016bad2005-09-08 15:30:05 +10001987#endif /* XFS_NATIVE_HOST */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001988
1989
1990/*
1991 * Increment cursor by one record at the level.
1992 * For nonzero levels the leaf-ward information is untouched.
1993 */
1994int /* error */
1995xfs_bmbt_increment(
1996 xfs_btree_cur_t *cur,
1997 int level,
1998 int *stat) /* success/failure */
1999{
2000 xfs_bmbt_block_t *block;
2001 xfs_buf_t *bp;
2002 int error; /* error return value */
2003#ifdef XFS_BMBT_TRACE
2004 static char fname[] = "xfs_bmbt_increment";
2005#endif
2006 xfs_fsblock_t fsbno;
2007 int lev;
2008 xfs_mount_t *mp;
2009 xfs_trans_t *tp;
2010
2011 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2012 XFS_BMBT_TRACE_ARGI(cur, level);
2013 ASSERT(level < cur->bc_nlevels);
2014 if (level < cur->bc_nlevels - 1)
2015 xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
2016 block = xfs_bmbt_get_block(cur, level, &bp);
2017#ifdef DEBUG
2018 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
2019 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2020 return error;
2021 }
2022#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11002023 if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002024 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2025 *stat = 1;
2026 return 0;
2027 }
Christoph Hellwig16259e72005-11-02 15:11:25 +11002028 if (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002029 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2030 *stat = 0;
2031 return 0;
2032 }
2033 for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
2034 block = xfs_bmbt_get_block(cur, lev, &bp);
2035#ifdef DEBUG
2036 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2037 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2038 return error;
2039 }
2040#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11002041 if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002042 break;
2043 if (lev < cur->bc_nlevels - 1)
2044 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
2045 }
2046 if (lev == cur->bc_nlevels) {
2047 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2048 *stat = 0;
2049 return 0;
2050 }
2051 tp = cur->bc_tp;
2052 mp = cur->bc_mp;
2053 for (block = xfs_bmbt_get_block(cur, lev, &bp); lev > level; ) {
Christoph Hellwig576039c2006-09-28 10:58:06 +10002054 fsbno = be64_to_cpu(*XFS_BMAP_PTR_IADDR(block, cur->bc_ptrs[lev], cur));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002055 if ((error = xfs_btree_read_bufl(mp, tp, fsbno, 0, &bp,
2056 XFS_BMAP_BTREE_REF))) {
2057 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2058 return error;
2059 }
2060 lev--;
2061 xfs_btree_setbuf(cur, lev, bp);
2062 block = XFS_BUF_TO_BMBT_BLOCK(bp);
2063 if ((error = xfs_btree_check_lblock(cur, block, lev, bp))) {
2064 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2065 return error;
2066 }
2067 cur->bc_ptrs[lev] = 1;
2068 }
2069 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2070 *stat = 1;
2071 return 0;
2072}
2073
2074/*
2075 * Insert the current record at the point referenced by cur.
2076 */
2077int /* error */
2078xfs_bmbt_insert(
2079 xfs_btree_cur_t *cur,
2080 int *stat) /* success/failure */
2081{
2082 int error; /* error return value */
2083#ifdef XFS_BMBT_TRACE
2084 static char fname[] = "xfs_bmbt_insert";
2085#endif
2086 int i;
2087 int level;
2088 xfs_fsblock_t nbno;
2089 xfs_btree_cur_t *ncur;
2090 xfs_bmbt_rec_t nrec;
2091 xfs_btree_cur_t *pcur;
2092
2093 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2094 level = 0;
2095 nbno = NULLFSBLOCK;
2096 xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
Nathan Scott1121b212006-09-28 10:58:40 +10002097 ncur = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002098 pcur = cur;
2099 do {
2100 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
2101 &i))) {
2102 if (pcur != cur)
2103 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2104 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2105 return error;
2106 }
2107 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2108 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
2109 cur->bc_nlevels = pcur->bc_nlevels;
2110 cur->bc_private.b.allocated +=
2111 pcur->bc_private.b.allocated;
2112 pcur->bc_private.b.allocated = 0;
2113 ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
2114 (cur->bc_private.b.ip->i_d.di_flags &
2115 XFS_DIFLAG_REALTIME));
2116 cur->bc_private.b.firstblock =
2117 pcur->bc_private.b.firstblock;
2118 ASSERT(cur->bc_private.b.flist ==
2119 pcur->bc_private.b.flist);
2120 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2121 }
2122 if (ncur) {
2123 pcur = ncur;
Nathan Scott1121b212006-09-28 10:58:40 +10002124 ncur = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002125 }
2126 } while (nbno != NULLFSBLOCK);
2127 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2128 *stat = i;
2129 return 0;
2130error0:
2131 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2132 return error;
2133}
2134
2135/*
2136 * Log fields from the btree block header.
2137 */
2138void
2139xfs_bmbt_log_block(
2140 xfs_btree_cur_t *cur,
2141 xfs_buf_t *bp,
2142 int fields)
2143{
2144 int first;
2145#ifdef XFS_BMBT_TRACE
2146 static char fname[] = "xfs_bmbt_log_block";
2147#endif
2148 int last;
2149 xfs_trans_t *tp;
2150 static const short offsets[] = {
2151 offsetof(xfs_bmbt_block_t, bb_magic),
2152 offsetof(xfs_bmbt_block_t, bb_level),
2153 offsetof(xfs_bmbt_block_t, bb_numrecs),
2154 offsetof(xfs_bmbt_block_t, bb_leftsib),
2155 offsetof(xfs_bmbt_block_t, bb_rightsib),
2156 sizeof(xfs_bmbt_block_t)
2157 };
2158
2159 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2160 XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
2161 tp = cur->bc_tp;
2162 if (bp) {
2163 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
2164 &last);
2165 xfs_trans_log_buf(tp, bp, first, last);
2166 } else
2167 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
2168 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
2169 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2170}
2171
2172/*
2173 * Log record values from the btree block.
2174 */
2175void
2176xfs_bmbt_log_recs(
2177 xfs_btree_cur_t *cur,
2178 xfs_buf_t *bp,
2179 int rfirst,
2180 int rlast)
2181{
2182 xfs_bmbt_block_t *block;
2183 int first;
2184#ifdef XFS_BMBT_TRACE
2185 static char fname[] = "xfs_bmbt_log_recs";
2186#endif
2187 int last;
2188 xfs_bmbt_rec_t *rp;
2189 xfs_trans_t *tp;
2190
2191 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2192 XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
2193 ASSERT(bp);
2194 tp = cur->bc_tp;
2195 block = XFS_BUF_TO_BMBT_BLOCK(bp);
2196 rp = XFS_BMAP_REC_DADDR(block, 1, cur);
2197 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
2198 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
2199 xfs_trans_log_buf(tp, bp, first, last);
2200 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2201}
2202
2203int /* error */
2204xfs_bmbt_lookup_eq(
2205 xfs_btree_cur_t *cur,
2206 xfs_fileoff_t off,
2207 xfs_fsblock_t bno,
2208 xfs_filblks_t len,
2209 int *stat) /* success/failure */
2210{
2211 cur->bc_rec.b.br_startoff = off;
2212 cur->bc_rec.b.br_startblock = bno;
2213 cur->bc_rec.b.br_blockcount = len;
2214 return xfs_bmbt_lookup(cur, XFS_LOOKUP_EQ, stat);
2215}
2216
2217int /* error */
2218xfs_bmbt_lookup_ge(
2219 xfs_btree_cur_t *cur,
2220 xfs_fileoff_t off,
2221 xfs_fsblock_t bno,
2222 xfs_filblks_t len,
2223 int *stat) /* success/failure */
2224{
2225 cur->bc_rec.b.br_startoff = off;
2226 cur->bc_rec.b.br_startblock = bno;
2227 cur->bc_rec.b.br_blockcount = len;
2228 return xfs_bmbt_lookup(cur, XFS_LOOKUP_GE, stat);
2229}
2230
Linus Torvalds1da177e2005-04-16 15:20:36 -07002231/*
2232 * Give the bmap btree a new root block. Copy the old broot contents
2233 * down into a real block and make the broot point to it.
2234 */
2235int /* error */
2236xfs_bmbt_newroot(
2237 xfs_btree_cur_t *cur, /* btree cursor */
2238 int *logflags, /* logging flags for inode */
2239 int *stat) /* return status - 0 fail */
2240{
2241 xfs_alloc_arg_t args; /* allocation arguments */
2242 xfs_bmbt_block_t *block; /* bmap btree block */
2243 xfs_buf_t *bp; /* buffer for block */
2244 xfs_bmbt_block_t *cblock; /* child btree block */
2245 xfs_bmbt_key_t *ckp; /* child key pointer */
2246 xfs_bmbt_ptr_t *cpp; /* child ptr pointer */
2247 int error; /* error return code */
2248#ifdef XFS_BMBT_TRACE
2249 static char fname[] = "xfs_bmbt_newroot";
2250#endif
2251#ifdef DEBUG
2252 int i; /* loop counter */
2253#endif
2254 xfs_bmbt_key_t *kp; /* pointer to bmap btree key */
2255 int level; /* btree level */
2256 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
2257
2258 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2259 level = cur->bc_nlevels - 1;
2260 block = xfs_bmbt_get_block(cur, level, &bp);
2261 /*
2262 * Copy the root into a real block.
2263 */
2264 args.mp = cur->bc_mp;
2265 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
2266 args.tp = cur->bc_tp;
2267 args.fsbno = cur->bc_private.b.firstblock;
2268 args.mod = args.minleft = args.alignment = args.total = args.isfl =
2269 args.userdata = args.minalignslop = 0;
2270 args.minlen = args.maxlen = args.prod = 1;
2271 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
Yingping Lud210a282006-06-09 14:55:18 +10002272 args.firstblock = args.fsbno;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002273 if (args.fsbno == NULLFSBLOCK) {
2274#ifdef DEBUG
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10002275 if ((error = xfs_btree_check_lptr_disk(cur, *pp, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002276 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2277 return error;
2278 }
2279#endif
Christoph Hellwig576039c2006-09-28 10:58:06 +10002280 args.fsbno = be64_to_cpu(*pp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002281 args.type = XFS_ALLOCTYPE_START_BNO;
Yingping Lud210a282006-06-09 14:55:18 +10002282 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -07002283 args.type = XFS_ALLOCTYPE_NEAR_BNO;
2284 if ((error = xfs_alloc_vextent(&args))) {
2285 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2286 return error;
2287 }
2288 if (args.fsbno == NULLFSBLOCK) {
2289 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2290 *stat = 0;
2291 return 0;
2292 }
2293 ASSERT(args.len == 1);
2294 cur->bc_private.b.firstblock = args.fsbno;
2295 cur->bc_private.b.allocated++;
2296 cur->bc_private.b.ip->i_d.di_nblocks++;
2297 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
2298 XFS_TRANS_DQ_BCOUNT, 1L);
2299 bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
2300 cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
2301 *cblock = *block;
Christoph Hellwig16259e72005-11-02 15:11:25 +11002302 be16_add(&block->bb_level, 1);
2303 block->bb_numrecs = cpu_to_be16(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002304 cur->bc_nlevels++;
2305 cur->bc_ptrs[level + 1] = 1;
2306 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
2307 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002308 memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002309 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
2310#ifdef DEBUG
Christoph Hellwig16259e72005-11-02 15:11:25 +11002311 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
Christoph Hellwigb113bcb2006-09-28 10:57:42 +10002312 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002313 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2314 return error;
2315 }
2316 }
2317#endif
Christoph Hellwig16259e72005-11-02 15:11:25 +11002318 memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002319#ifdef DEBUG
Christoph Hellwig576039c2006-09-28 10:58:06 +10002320 if ((error = xfs_btree_check_lptr(cur, args.fsbno, level))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002321 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2322 return error;
2323 }
2324#endif
Christoph Hellwig576039c2006-09-28 10:58:06 +10002325 *pp = cpu_to_be64(args.fsbno);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002326 xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
Linus Torvalds1da177e2005-04-16 15:20:36 -07002327 cur->bc_private.b.whichfork);
2328 xfs_btree_setbuf(cur, level, bp);
2329 /*
2330 * Do all this logging at the end so that
2331 * the root is at the right level.
2332 */
2333 xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002334 xfs_bmbt_log_keys(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
2335 xfs_bmbt_log_ptrs(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002336 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2337 *logflags |=
2338 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
2339 *stat = 1;
2340 return 0;
2341}
2342
2343/*
2344 * Set all the fields in a bmap extent record from the uncompressed form.
2345 */
2346void
2347xfs_bmbt_set_all(
2348 xfs_bmbt_rec_t *r,
2349 xfs_bmbt_irec_t *s)
2350{
2351 int extent_flag;
2352
2353 ASSERT((s->br_state == XFS_EXT_NORM) ||
2354 (s->br_state == XFS_EXT_UNWRITTEN));
2355 extent_flag = (s->br_state == XFS_EXT_NORM) ? 0 : 1;
2356 ASSERT((s->br_startoff & XFS_MASK64HI(9)) == 0);
2357 ASSERT((s->br_blockcount & XFS_MASK64HI(43)) == 0);
2358#if XFS_BIG_BLKNOS
2359 ASSERT((s->br_startblock & XFS_MASK64HI(12)) == 0);
2360 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2361 ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2362 ((xfs_bmbt_rec_base_t)s->br_startblock >> 43);
2363 r->l1 = ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2364 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2365 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2366#else /* !XFS_BIG_BLKNOS */
2367 if (ISNULLSTARTBLOCK(s->br_startblock)) {
2368 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2369 ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2370 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2371 r->l1 = XFS_MASK64HI(11) |
2372 ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2373 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2374 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2375 } else {
2376 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2377 ((xfs_bmbt_rec_base_t)s->br_startoff << 9);
2378 r->l1 = ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2379 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2380 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2381 }
2382#endif /* XFS_BIG_BLKNOS */
2383}
2384
2385/*
2386 * Set all the fields in a bmap extent record from the arguments.
2387 */
2388void
2389xfs_bmbt_set_allf(
2390 xfs_bmbt_rec_t *r,
2391 xfs_fileoff_t o,
2392 xfs_fsblock_t b,
2393 xfs_filblks_t c,
2394 xfs_exntst_t v)
2395{
2396 int extent_flag;
2397
2398 ASSERT((v == XFS_EXT_NORM) || (v == XFS_EXT_UNWRITTEN));
2399 extent_flag = (v == XFS_EXT_NORM) ? 0 : 1;
2400 ASSERT((o & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2401 ASSERT((c & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2402#if XFS_BIG_BLKNOS
2403 ASSERT((b & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2404 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2405 ((xfs_bmbt_rec_base_t)o << 9) |
2406 ((xfs_bmbt_rec_base_t)b >> 43);
2407 r->l1 = ((xfs_bmbt_rec_base_t)b << 21) |
2408 ((xfs_bmbt_rec_base_t)c &
2409 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2410#else /* !XFS_BIG_BLKNOS */
2411 if (ISNULLSTARTBLOCK(b)) {
2412 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2413 ((xfs_bmbt_rec_base_t)o << 9) |
2414 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2415 r->l1 = XFS_MASK64HI(11) |
2416 ((xfs_bmbt_rec_base_t)b << 21) |
2417 ((xfs_bmbt_rec_base_t)c &
2418 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2419 } else {
2420 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2421 ((xfs_bmbt_rec_base_t)o << 9);
2422 r->l1 = ((xfs_bmbt_rec_base_t)b << 21) |
2423 ((xfs_bmbt_rec_base_t)c &
2424 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2425 }
2426#endif /* XFS_BIG_BLKNOS */
2427}
2428
Nathan Scottf016bad2005-09-08 15:30:05 +10002429#ifndef XFS_NATIVE_HOST
Linus Torvalds1da177e2005-04-16 15:20:36 -07002430/*
2431 * Set all the fields in a bmap extent record from the uncompressed form.
2432 */
2433void
2434xfs_bmbt_disk_set_all(
2435 xfs_bmbt_rec_t *r,
2436 xfs_bmbt_irec_t *s)
2437{
2438 int extent_flag;
2439
2440 ASSERT((s->br_state == XFS_EXT_NORM) ||
2441 (s->br_state == XFS_EXT_UNWRITTEN));
2442 extent_flag = (s->br_state == XFS_EXT_NORM) ? 0 : 1;
2443 ASSERT((s->br_startoff & XFS_MASK64HI(9)) == 0);
2444 ASSERT((s->br_blockcount & XFS_MASK64HI(43)) == 0);
2445#if XFS_BIG_BLKNOS
2446 ASSERT((s->br_startblock & XFS_MASK64HI(12)) == 0);
2447 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2448 ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2449 ((xfs_bmbt_rec_base_t)s->br_startblock >> 43));
2450 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2451 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2452 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2453#else /* !XFS_BIG_BLKNOS */
2454 if (ISNULLSTARTBLOCK(s->br_startblock)) {
2455 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2456 ((xfs_bmbt_rec_base_t)s->br_startoff << 9) |
2457 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2458 INT_SET(r->l1, ARCH_CONVERT, XFS_MASK64HI(11) |
2459 ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2460 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2461 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2462 } else {
2463 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2464 ((xfs_bmbt_rec_base_t)s->br_startoff << 9));
2465 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)s->br_startblock << 21) |
2466 ((xfs_bmbt_rec_base_t)s->br_blockcount &
2467 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2468 }
2469#endif /* XFS_BIG_BLKNOS */
2470}
2471
2472/*
2473 * Set all the fields in a disk format bmap extent record from the arguments.
2474 */
2475void
2476xfs_bmbt_disk_set_allf(
2477 xfs_bmbt_rec_t *r,
2478 xfs_fileoff_t o,
2479 xfs_fsblock_t b,
2480 xfs_filblks_t c,
2481 xfs_exntst_t v)
2482{
2483 int extent_flag;
2484
2485 ASSERT((v == XFS_EXT_NORM) || (v == XFS_EXT_UNWRITTEN));
2486 extent_flag = (v == XFS_EXT_NORM) ? 0 : 1;
2487 ASSERT((o & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
2488 ASSERT((c & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
2489#if XFS_BIG_BLKNOS
2490 ASSERT((b & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
2491 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2492 ((xfs_bmbt_rec_base_t)o << 9) |
2493 ((xfs_bmbt_rec_base_t)b >> 43));
2494 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)b << 21) |
2495 ((xfs_bmbt_rec_base_t)c &
2496 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2497#else /* !XFS_BIG_BLKNOS */
2498 if (ISNULLSTARTBLOCK(b)) {
2499 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2500 ((xfs_bmbt_rec_base_t)o << 9) |
2501 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2502 INT_SET(r->l1, ARCH_CONVERT, XFS_MASK64HI(11) |
2503 ((xfs_bmbt_rec_base_t)b << 21) |
2504 ((xfs_bmbt_rec_base_t)c &
2505 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2506 } else {
2507 INT_SET(r->l0, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)extent_flag << 63) |
2508 ((xfs_bmbt_rec_base_t)o << 9));
2509 INT_SET(r->l1, ARCH_CONVERT, ((xfs_bmbt_rec_base_t)b << 21) |
2510 ((xfs_bmbt_rec_base_t)c &
2511 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
2512 }
2513#endif /* XFS_BIG_BLKNOS */
2514}
Nathan Scottf016bad2005-09-08 15:30:05 +10002515#endif /* XFS_NATIVE_HOST */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002516
2517/*
2518 * Set the blockcount field in a bmap extent record.
2519 */
2520void
2521xfs_bmbt_set_blockcount(
2522 xfs_bmbt_rec_t *r,
2523 xfs_filblks_t v)
2524{
2525 ASSERT((v & XFS_MASK64HI(43)) == 0);
2526 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
2527 (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
2528}
2529
2530/*
2531 * Set the startblock field in a bmap extent record.
2532 */
2533void
2534xfs_bmbt_set_startblock(
2535 xfs_bmbt_rec_t *r,
2536 xfs_fsblock_t v)
2537{
2538#if XFS_BIG_BLKNOS
2539 ASSERT((v & XFS_MASK64HI(12)) == 0);
2540 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
2541 (xfs_bmbt_rec_base_t)(v >> 43);
2542 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
2543 (xfs_bmbt_rec_base_t)(v << 21);
2544#else /* !XFS_BIG_BLKNOS */
2545 if (ISNULLSTARTBLOCK(v)) {
2546 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2547 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
2548 ((xfs_bmbt_rec_base_t)v << 21) |
2549 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2550 } else {
2551 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
2552 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
2553 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
2554 }
2555#endif /* XFS_BIG_BLKNOS */
2556}
2557
2558/*
2559 * Set the startoff field in a bmap extent record.
2560 */
2561void
2562xfs_bmbt_set_startoff(
2563 xfs_bmbt_rec_t *r,
2564 xfs_fileoff_t v)
2565{
2566 ASSERT((v & XFS_MASK64HI(9)) == 0);
2567 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
2568 ((xfs_bmbt_rec_base_t)v << 9) |
2569 (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
2570}
2571
2572/*
2573 * Set the extent state field in a bmap extent record.
2574 */
2575void
2576xfs_bmbt_set_state(
2577 xfs_bmbt_rec_t *r,
2578 xfs_exntst_t v)
2579{
2580 ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
2581 if (v == XFS_EXT_NORM)
2582 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
2583 else
2584 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
2585}
2586
2587/*
2588 * Convert in-memory form of btree root to on-disk form.
2589 */
2590void
2591xfs_bmbt_to_bmdr(
2592 xfs_bmbt_block_t *rblock,
2593 int rblocklen,
2594 xfs_bmdr_block_t *dblock,
2595 int dblocklen)
2596{
2597 int dmxr;
2598 xfs_bmbt_key_t *fkp;
Christoph Hellwig576039c2006-09-28 10:58:06 +10002599 __be64 *fpp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002600 xfs_bmbt_key_t *tkp;
Christoph Hellwig576039c2006-09-28 10:58:06 +10002601 __be64 *tpp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002602
Christoph Hellwig16259e72005-11-02 15:11:25 +11002603 ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
2604 ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
2605 ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
2606 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
2607 dblock->bb_level = rblock->bb_level;
2608 dblock->bb_numrecs = rblock->bb_numrecs;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002609 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2610 fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
Eric Sandeen2c36dde2007-02-10 18:37:33 +11002611 tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002612 fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
Eric Sandeen2c36dde2007-02-10 18:37:33 +11002613 tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002614 dmxr = be16_to_cpu(dblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002615 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
Christoph Hellwig576039c2006-09-28 10:58:06 +10002616 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002617}
2618
2619/*
2620 * Update the record to the passed values.
2621 */
2622int
2623xfs_bmbt_update(
2624 xfs_btree_cur_t *cur,
2625 xfs_fileoff_t off,
2626 xfs_fsblock_t bno,
2627 xfs_filblks_t len,
2628 xfs_exntst_t state)
2629{
2630 xfs_bmbt_block_t *block;
2631 xfs_buf_t *bp;
2632 int error;
2633#ifdef XFS_BMBT_TRACE
2634 static char fname[] = "xfs_bmbt_update";
2635#endif
2636 xfs_bmbt_key_t key;
2637 int ptr;
2638 xfs_bmbt_rec_t *rp;
2639
2640 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2641 XFS_BMBT_TRACE_ARGFFFI(cur, (xfs_dfiloff_t)off, (xfs_dfsbno_t)bno,
2642 (xfs_dfilblks_t)len, (int)state);
2643 block = xfs_bmbt_get_block(cur, 0, &bp);
2644#ifdef DEBUG
2645 if ((error = xfs_btree_check_lblock(cur, block, 0, bp))) {
2646 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2647 return error;
2648 }
2649#endif
2650 ptr = cur->bc_ptrs[0];
2651 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
2652 xfs_bmbt_disk_set_allf(rp, off, bno, len, state);
2653 xfs_bmbt_log_recs(cur, bp, ptr, ptr);
2654 if (ptr > 1) {
2655 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2656 return 0;
2657 }
Christoph Hellwig8801bb92006-09-28 10:58:17 +10002658 key.br_startoff = cpu_to_be64(off);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002659 if ((error = xfs_bmbt_updkey(cur, &key, 1))) {
2660 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2661 return error;
2662 }
2663 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2664 return 0;
2665}
2666
2667/*
Mandy Kirkconnell4eea22f2006-03-14 13:29:52 +11002668 * Check extent records, which have just been read, for
Linus Torvalds1da177e2005-04-16 15:20:36 -07002669 * any bit in the extent flag field. ASSERT on debug
2670 * kernels, as this condition should not occur.
2671 * Return an error condition (1) if any flags found,
2672 * otherwise return 0.
2673 */
2674
2675int
2676xfs_check_nostate_extents(
Mandy Kirkconnell4eea22f2006-03-14 13:29:52 +11002677 xfs_ifork_t *ifp,
2678 xfs_extnum_t idx,
Linus Torvalds1da177e2005-04-16 15:20:36 -07002679 xfs_extnum_t num)
2680{
Mandy Kirkconnell4eea22f2006-03-14 13:29:52 +11002681 xfs_bmbt_rec_t *ep;
2682
2683 for (; num > 0; num--, idx++) {
2684 ep = xfs_iext_get_ext(ifp, idx);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002685 if ((ep->l0 >>
2686 (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
2687 ASSERT(0);
2688 return 1;
2689 }
2690 }
2691 return 0;
2692}