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