projects / deliverable / linux.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
[XFS] implement generic xfs_btree_lookup
[deliverable/linux.git] / fs / xfs / xfs_bmap_btree.c
CommitLineData
1da177e4 1/*
7b718769
NS		 2 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
1da177e4 4 *
7b718769
NS		 5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
1da177e4
LT		 7 * published by the Free Software Foundation.
8 *
7b718769
NS		 9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
1da177e4 13 *
7b718769
NS		 14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
1da177e4 17 */
1da177e4 18#include "xfs.h"
a844f451 19#include "xfs_fs.h"
1da177e4 20#include "xfs_types.h"
a844f451 21#include "xfs_bit.h"
1da177e4 22#include "xfs_log.h"
a844f451 23#include "xfs_inum.h"
1da177e4
LT		 24#include "xfs_trans.h"
25#include "xfs_sb.h"
26#include "xfs_ag.h"
1da177e4
LT		 27#include "xfs_dir2.h"
28#include "xfs_dmapi.h"
29#include "xfs_mount.h"
1da177e4 30#include "xfs_bmap_btree.h"
a844f451 31#include "xfs_alloc_btree.h"
1da177e4 32#include "xfs_ialloc_btree.h"
1da177e4 33#include "xfs_dir2_sf.h"
a844f451 34#include "xfs_attr_sf.h"
1da177e4 35#include "xfs_dinode.h"
1da177e4 36#include "xfs_inode.h"
a844f451 37#include "xfs_inode_item.h"
1da177e4 38#include "xfs_alloc.h"
a844f451 39#include "xfs_btree.h"
8c4ed633 40#include "xfs_btree_trace.h"
a844f451
NS		 41#include "xfs_ialloc.h"
42#include "xfs_itable.h"
1da177e4
LT		 43#include "xfs_bmap.h"
44#include "xfs_error.h"
45#include "xfs_quota.h"
46
1da177e4
LT		 47/*
48 * Prototypes for internal btree functions.
49 */
50
51
52STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
55STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
56STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
57STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
8801bb99 58 __uint64_t *, xfs_btree_cur_t **, int *);
1da177e4
LT		 59STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);
60
1da177e4 61#undef EXIT
1da177e4 62
8c4ed633
CH		 63#define ENTRY XBT_ENTRY
64#define ERROR XBT_ERROR
65#define EXIT XBT_EXIT
1da177e4 66
1da177e4 67/*
8c4ed633
CH		 68 * Keep the XFS_BMBT_TRACE_ names around for now until all code using them
69 * is converted to be generic and thus switches to the XFS_BTREE_TRACE_ names.
1da177e4 70 */
8c4ed633
CH		 71#define XFS_BMBT_TRACE_ARGBI(c,b,i) \
72 XFS_BTREE_TRACE_ARGBI(c,b,i)
73#define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
74 XFS_BTREE_TRACE_ARGBII(c,b,i,j)
75#define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
76 XFS_BTREE_TRACE_ARGFFFI(c,o,b,i,j)
77#define XFS_BMBT_TRACE_ARGI(c,i) \
78 XFS_BTREE_TRACE_ARGI(c,i)
79#define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
80 XFS_BTREE_TRACE_ARGIPK(c,i,(union xfs_btree_ptr)f,s)
81#define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
82 XFS_BTREE_TRACE_ARGIPR(c,i, \
83 (union xfs_btree_ptr)f, (union xfs_btree_rec *)r)
84#define XFS_BMBT_TRACE_ARGIK(c,i,k) \
85 XFS_BTREE_TRACE_ARGIK(c,i,(union xfs_btree_key *)k)
86#define XFS_BMBT_TRACE_CURSOR(c,s) \
87 XFS_BTREE_TRACE_CURSOR(c,s)
1da177e4
LT		 88
89
90/*
91 * Internal functions.
92 */
93
94/*
95 * Delete record pointed to by cur/level.
96 */
97STATIC int /* error */
98xfs_bmbt_delrec(
99 xfs_btree_cur_t *cur,
100 int level,
101 int *stat) /* success/failure */
102{
103 xfs_bmbt_block_t *block; /* bmap btree block */
104 xfs_fsblock_t bno; /* fs-relative block number */
105 xfs_buf_t *bp; /* buffer for block */
106 int error; /* error return value */
1da177e4
LT		 107 int i; /* loop counter */
108 int j; /* temp state */
109 xfs_bmbt_key_t key; /* bmap btree key */
110 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
111 xfs_fsblock_t lbno; /* left sibling block number */
112 xfs_buf_t *lbp; /* left buffer pointer */
113 xfs_bmbt_block_t *left; /* left btree block */
114 xfs_bmbt_key_t *lkp; /* left btree key */
115 xfs_bmbt_ptr_t *lpp; /* left address pointer */
116 int lrecs=0; /* left record count */
117 xfs_bmbt_rec_t *lrp; /* left record pointer */
118 xfs_mount_t *mp; /* file system mount point */
119 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
120 int ptr; /* key/record index */
121 xfs_fsblock_t rbno; /* right sibling block number */
122 xfs_buf_t *rbp; /* right buffer pointer */
123 xfs_bmbt_block_t *right; /* right btree block */
124 xfs_bmbt_key_t *rkp; /* right btree key */
125 xfs_bmbt_rec_t *rp; /* pointer to bmap btree rec */
126 xfs_bmbt_ptr_t *rpp; /* right address pointer */
127 xfs_bmbt_block_t *rrblock; /* right-right btree block */
128 xfs_buf_t *rrbp; /* right-right buffer pointer */
129 int rrecs=0; /* right record count */
130 xfs_bmbt_rec_t *rrp; /* right record pointer */
131 xfs_btree_cur_t *tcur; /* temporary btree cursor */
132 int numrecs; /* temporary numrec count */
133 int numlrecs, numrrecs;
134
135 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
136 XFS_BMBT_TRACE_ARGI(cur, level);
137 ptr = cur->bc_ptrs[level];
1121b219 138 tcur = NULL;
1da177e4
LT		 139 if (ptr == 0) {
140 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
141 *stat = 0;
142 return 0;
143 }
144 block = xfs_bmbt_get_block(cur, level, &bp);
16259e7d 145 numrecs = be16_to_cpu(block->bb_numrecs);
1da177e4
LT		 146#ifdef DEBUG
147 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
148 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
149 goto error0;
150 }
151#endif
152 if (ptr > numrecs) {
153 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
154 *stat = 0;
155 return 0;
156 }
157 XFS_STATS_INC(xs_bmbt_delrec);
158 if (level > 0) {
159 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
160 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
161#ifdef DEBUG
162 for (i = ptr; i < numrecs; i++) {
b113bcb8 163 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
1da177e4
LT		 164 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
165 goto error0;
166 }
167 }
168#endif
169 if (ptr < numrecs) {
170 memmove(&kp[ptr - 1], &kp[ptr],
171 (numrecs - ptr) * sizeof(*kp));
d580ef6e 172 memmove(&pp[ptr - 1], &pp[ptr],
1da177e4
LT		 173 (numrecs - ptr) * sizeof(*pp));
174 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
175 xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
176 }
177 } else {
178 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
179 if (ptr < numrecs) {
180 memmove(&rp[ptr - 1], &rp[ptr],
181 (numrecs - ptr) * sizeof(*rp));
182 xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
183 }
184 if (ptr == 1) {
8801bb99
CH		 185 key.br_startoff =
186 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
1da177e4
LT		 187 kp = &key;
188 }
189 }
190 numrecs--;
16259e7d 191 block->bb_numrecs = cpu_to_be16(numrecs);
1da177e4
LT		 192 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
193 /*
194 * We're at the root level.
195 * First, shrink the root block in-memory.
196 * Try to get rid of the next level down.
197 * If we can't then there's nothing left to do.
198 */
199 if (level == cur->bc_nlevels - 1) {
200 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
201 cur->bc_private.b.whichfork);
202 if ((error = xfs_bmbt_killroot(cur))) {
203 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
204 goto error0;
205 }
8df4da4a 206 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
1da177e4
LT		 207 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
208 goto error0;
209 }
210 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
211 *stat = 1;
212 return 0;
213 }
214 if (ptr == 1 && (error = xfs_bmbt_updkey(cur, kp, level + 1))) {
215 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
216 goto error0;
217 }
218 if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
8df4da4a 219 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
1da177e4
LT		 220 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
221 goto error0;
222 }
223 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
224 *stat = 1;
225 return 0;
226 }
16259e7d
CH		 227 rbno = be64_to_cpu(block->bb_rightsib);
228 lbno = be64_to_cpu(block->bb_leftsib);
1da177e4
LT		 229 /*
230 * One child of root, need to get a chance to copy its contents
231 * into the root and delete it. Can't go up to next level,
232 * there's nothing to delete there.
233 */
234 if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
235 level == cur->bc_nlevels - 2) {
236 if ((error = xfs_bmbt_killroot(cur))) {
237 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
238 goto error0;
239 }
8df4da4a 240 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
1da177e4
LT		 241 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
242 goto error0;
243 }
244 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
245 *stat = 1;
246 return 0;
247 }
248 ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
249 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
250 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
251 goto error0;
252 }
253 bno = NULLFSBLOCK;
254 if (rbno != NULLFSBLOCK) {
255 i = xfs_btree_lastrec(tcur, level);
256 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
637aa50f 257 if ((error = xfs_btree_increment(tcur, level, &i))) {
1da177e4
LT		 258 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
259 goto error0;
260 }
261 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
262 i = xfs_btree_lastrec(tcur, level);
263 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
264 rbp = tcur->bc_bufs[level];
265 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
266#ifdef DEBUG
267 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
268 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
269 goto error0;
270 }
271#endif
16259e7d
CH		 272 bno = be64_to_cpu(right->bb_leftsib);
273 if (be16_to_cpu(right->bb_numrecs) - 1 >=
1da177e4
LT		 274 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
275 if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
276 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
277 goto error0;
278 }
279 if (i) {
16259e7d 280 ASSERT(be16_to_cpu(block->bb_numrecs) >=
1da177e4
LT		 281 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
282 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
283 tcur = NULL;
284 if (level > 0) {
8df4da4a 285 if ((error = xfs_btree_decrement(cur,
1da177e4
LT		 286 level, &i))) {
287 XFS_BMBT_TRACE_CURSOR(cur,
288 ERROR);
289 goto error0;
290 }
291 }
292 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
293 *stat = 1;
294 return 0;
295 }
296 }
16259e7d 297 rrecs = be16_to_cpu(right->bb_numrecs);
1da177e4
LT		 298 if (lbno != NULLFSBLOCK) {
299 i = xfs_btree_firstrec(tcur, level);
300 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
8df4da4a 301 if ((error = xfs_btree_decrement(tcur, level, &i))) {
1da177e4
LT		 302 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
303 goto error0;
304 }
305 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
306 }
307 }
308 if (lbno != NULLFSBLOCK) {
309 i = xfs_btree_firstrec(tcur, level);
310 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
311 /*
312 * decrement to last in block
313 */
8df4da4a 314 if ((error = xfs_btree_decrement(tcur, level, &i))) {
1da177e4
LT		 315 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
316 goto error0;
317 }
318 i = xfs_btree_firstrec(tcur, level);
319 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
320 lbp = tcur->bc_bufs[level];
321 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
322#ifdef DEBUG
323 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
324 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
325 goto error0;
326 }
327#endif
16259e7d
CH		 328 bno = be64_to_cpu(left->bb_rightsib);
329 if (be16_to_cpu(left->bb_numrecs) - 1 >=
1da177e4
LT		 330 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
331 if ((error = xfs_bmbt_rshift(tcur, level, &i))) {
332 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
333 goto error0;
334 }
335 if (i) {
16259e7d 336 ASSERT(be16_to_cpu(block->bb_numrecs) >=
1da177e4
LT		 337 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
338 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
339 tcur = NULL;
340 if (level == 0)
341 cur->bc_ptrs[0]++;
342 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
343 *stat = 1;
344 return 0;
345 }
346 }
16259e7d 347 lrecs = be16_to_cpu(left->bb_numrecs);
1da177e4
LT		 348 }
349 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
350 tcur = NULL;
351 mp = cur->bc_mp;
352 ASSERT(bno != NULLFSBLOCK);
353 if (lbno != NULLFSBLOCK &&
16259e7d 354 lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1da177e4
LT		 355 rbno = bno;
356 right = block;
357 rbp = bp;
358 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
359 XFS_BMAP_BTREE_REF))) {
360 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
361 goto error0;
362 }
363 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
364 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
365 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
366 goto error0;
367 }
368 } else if (rbno != NULLFSBLOCK &&
16259e7d 369 rrecs + be16_to_cpu(block->bb_numrecs) <=
1da177e4
LT		 370 XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
371 lbno = bno;
372 left = block;
373 lbp = bp;
374 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
375 XFS_BMAP_BTREE_REF))) {
376 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
377 goto error0;
378 }
379 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
380 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
381 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
382 goto error0;
383 }
16259e7d 384 lrecs = be16_to_cpu(left->bb_numrecs);
1da177e4 385 } else {
8df4da4a 386 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
1da177e4
LT		 387 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
388 goto error0;
389 }
390 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
391 *stat = 1;
392 return 0;
393 }
16259e7d
CH		 394 numlrecs = be16_to_cpu(left->bb_numrecs);
395 numrrecs = be16_to_cpu(right->bb_numrecs);
1da177e4
LT		 396 if (level > 0) {
397 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
398 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
399 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
400 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
401#ifdef DEBUG
402 for (i = 0; i < numrrecs; i++) {
b113bcb8 403 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1da177e4
LT		 404 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
405 goto error0;
406 }
407 }
408#endif
409 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
410 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
411 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
412 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
413 } else {
414 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
415 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
416 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
417 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
418 }
413d57c9 419 be16_add_cpu(&left->bb_numrecs, numrrecs);
16259e7d 420 left->bb_rightsib = right->bb_rightsib;
1da177e4 421 xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
16259e7d 422 if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
1da177e4 423 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
16259e7d 424 be64_to_cpu(left->bb_rightsib),
1da177e4
LT		 425 0, &rrbp, XFS_BMAP_BTREE_REF))) {
426 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
427 goto error0;
428 }
429 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
430 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
431 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
432 goto error0;
433 }
16259e7d 434 rrblock->bb_leftsib = cpu_to_be64(lbno);
1da177e4
LT		 435 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
436 }
437 xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
438 cur->bc_private.b.flist, mp);
439 cur->bc_private.b.ip->i_d.di_nblocks--;
440 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
441 XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
442 XFS_TRANS_DQ_BCOUNT, -1L);
443 xfs_trans_binval(cur->bc_tp, rbp);
444 if (bp != lbp) {
445 cur->bc_bufs[level] = lbp;
446 cur->bc_ptrs[level] += lrecs;
447 cur->bc_ra[level] = 0;
637aa50f 448 } else if ((error = xfs_btree_increment(cur, level + 1, &i))) {
1da177e4
LT		 449 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
450 goto error0;
451 }
452 if (level > 0)
453 cur->bc_ptrs[level]--;
454 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
455 *stat = 2;
456 return 0;
457
458error0:
459 if (tcur)
460 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
461 return error;
462}
463
1da177e4
LT		 464/*
465 * Insert one record/level. Return information to the caller
466 * allowing the next level up to proceed if necessary.
467 */
468STATIC int /* error */
469xfs_bmbt_insrec(
470 xfs_btree_cur_t *cur,
471 int level,
472 xfs_fsblock_t *bnop,
473 xfs_bmbt_rec_t *recp,
474 xfs_btree_cur_t **curp,
475 int *stat) /* no-go/done/continue */
476{
477 xfs_bmbt_block_t *block; /* bmap btree block */
478 xfs_buf_t *bp; /* buffer for block */
479 int error; /* error return value */
1da177e4
LT		 480 int i; /* loop index */
481 xfs_bmbt_key_t key; /* bmap btree key */
482 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
483 int logflags; /* inode logging flags */
484 xfs_fsblock_t nbno; /* new block number */
485 struct xfs_btree_cur *ncur; /* new btree cursor */
8801bb99 486 __uint64_t startoff; /* new btree key value */
1da177e4
LT		 487 xfs_bmbt_rec_t nrec; /* new record count */
488 int optr; /* old key/record index */
489 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
490 int ptr; /* key/record index */
491 xfs_bmbt_rec_t *rp=NULL; /* pointer to bmap btree rec */
492 int numrecs;
493
494 ASSERT(level < cur->bc_nlevels);
495 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
496 XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
1121b219 497 ncur = NULL;
8801bb99 498 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
1da177e4
LT		 499 optr = ptr = cur->bc_ptrs[level];
500 if (ptr == 0) {
501 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
502 *stat = 0;
503 return 0;
504 }
505 XFS_STATS_INC(xs_bmbt_insrec);
506 block = xfs_bmbt_get_block(cur, level, &bp);
16259e7d 507 numrecs = be16_to_cpu(block->bb_numrecs);
1da177e4
LT		 508#ifdef DEBUG
509 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
510 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
511 return error;
512 }
513 if (ptr <= numrecs) {
514 if (level == 0) {
515 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
516 xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
517 } else {
518 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
519 xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
520 }
521 }
522#endif
523 nbno = NULLFSBLOCK;
524 if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
525 if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
526 /*
527 * A root block, that can be made bigger.
528 */
529 xfs_iroot_realloc(cur->bc_private.b.ip, 1,
530 cur->bc_private.b.whichfork);
531 block = xfs_bmbt_get_block(cur, level, &bp);
532 } else if (level == cur->bc_nlevels - 1) {
533 if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
534 *stat == 0) {
535 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
536 return error;
537 }
538 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
539 logflags);
540 block = xfs_bmbt_get_block(cur, level, &bp);
541 } else {
542 if ((error = xfs_bmbt_rshift(cur, level, &i))) {
543 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
544 return error;
545 }
546 if (i) {
547 /* nothing */
548 } else {
549 if ((error = xfs_bmbt_lshift(cur, level, &i))) {
550 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
551 return error;
552 }
553 if (i) {
554 optr = ptr = cur->bc_ptrs[level];
555 } else {
556 if ((error = xfs_bmbt_split(cur, level,
8801bb99 557 &nbno, &startoff, &ncur,
1da177e4
LT		 558 &i))) {
559 XFS_BMBT_TRACE_CURSOR(cur,
560 ERROR);
561 return error;
562 }
563 if (i) {
564 block = xfs_bmbt_get_block(
565 cur, level, &bp);
566#ifdef DEBUG
567 if ((error =
568 xfs_btree_check_lblock(cur,
569 block, level, bp))) {
570 XFS_BMBT_TRACE_CURSOR(
571 cur, ERROR);
572 return error;
573 }
574#endif
575 ptr = cur->bc_ptrs[level];
576 xfs_bmbt_disk_set_allf(&nrec,
8801bb99 577 startoff, 0, 0,
1da177e4
LT		 578 XFS_EXT_NORM);
579 } else {
580 XFS_BMBT_TRACE_CURSOR(cur,
581 EXIT);
582 *stat = 0;
583 return 0;
584 }
585 }
586 }
587 }
588 }
16259e7d 589 numrecs = be16_to_cpu(block->bb_numrecs);
1da177e4
LT		 590 if (level > 0) {
591 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
592 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
593#ifdef DEBUG
594 for (i = numrecs; i >= ptr; i--) {
b113bcb8 595 if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
1da177e4
LT		 596 level))) {
597 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
598 return error;
599 }
600 }
601#endif
602 memmove(&kp[ptr], &kp[ptr - 1],
603 (numrecs - ptr + 1) * sizeof(*kp));
d580ef6e 604 memmove(&pp[ptr], &pp[ptr - 1],
1da177e4
LT		 605 (numrecs - ptr + 1) * sizeof(*pp));
606#ifdef DEBUG
576039cf 607 if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
1da177e4
LT		 608 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
609 return error;
610 }
611#endif
612 kp[ptr - 1] = key;
576039cf 613 pp[ptr - 1] = cpu_to_be64(*bnop);
1da177e4 614 numrecs++;
16259e7d 615 block->bb_numrecs = cpu_to_be16(numrecs);
1da177e4
LT		 616 xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
617 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
618 } else {
619 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
620 memmove(&rp[ptr], &rp[ptr - 1],
621 (numrecs - ptr + 1) * sizeof(*rp));
622 rp[ptr - 1] = *recp;
623 numrecs++;
16259e7d 624 block->bb_numrecs = cpu_to_be16(numrecs);
1da177e4
LT		 625 xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
626 }
627 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
628#ifdef DEBUG
629 if (ptr < numrecs) {
630 if (level == 0)
631 xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
632 rp + ptr);
633 else
634 xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
635 kp + ptr);
636 }
637#endif
638 if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
639 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
640 return error;
641 }
642 *bnop = nbno;
643 if (nbno != NULLFSBLOCK) {
644 *recp = nrec;
645 *curp = ncur;
646 }
647 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
648 *stat = 1;
649 return 0;
650}
651
652STATIC int
653xfs_bmbt_killroot(
654 xfs_btree_cur_t *cur)
655{
656 xfs_bmbt_block_t *block;
657 xfs_bmbt_block_t *cblock;
658 xfs_buf_t *cbp;
659 xfs_bmbt_key_t *ckp;
660 xfs_bmbt_ptr_t *cpp;
661#ifdef DEBUG
662 int error;
1da177e4
LT		 663#endif
664 int i;
665 xfs_bmbt_key_t *kp;
666 xfs_inode_t *ip;
667 xfs_ifork_t *ifp;
668 int level;
669 xfs_bmbt_ptr_t *pp;
670
671 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
672 level = cur->bc_nlevels - 1;
673 ASSERT(level >= 1);
674 /*
675 * Don't deal with the root block needs to be a leaf case.
676 * We're just going to turn the thing back into extents anyway.
677 */
678 if (level == 1) {
679 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
680 return 0;
681 }
682 block = xfs_bmbt_get_block(cur, level, &cbp);
683 /*
684 * Give up if the root has multiple children.
685 */
16259e7d 686 if (be16_to_cpu(block->bb_numrecs) != 1) {
1da177e4
LT		 687 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
688 return 0;
689 }
690 /*
691 * Only do this if the next level will fit.
692 * Then the data must be copied up to the inode,
693 * instead of freeing the root you free the next level.
694 */
695 cbp = cur->bc_bufs[level - 1];
696 cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
16259e7d 697 if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
1da177e4
LT		 698 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
699 return 0;
700 }
16259e7d
CH		 701 ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
702 ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
1da177e4
LT		 703 ip = cur->bc_private.b.ip;
704 ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
705 ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
706 XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
16259e7d 707 i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
1da177e4
LT		 708 if (i) {
709 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
710 block = ifp->if_broot;
711 }
413d57c9 712 be16_add_cpu(&block->bb_numrecs, i);
16259e7d 713 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
1da177e4
LT		 714 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
715 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
16259e7d 716 memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
1da177e4
LT		 717 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
718 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
719#ifdef DEBUG
16259e7d 720 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
b113bcb8 721 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
1da177e4
LT		 722 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
723 return error;
724 }
725 }
726#endif
16259e7d 727 memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
1da177e4
LT		 728 xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
729 cur->bc_private.b.flist, cur->bc_mp);
730 ip->i_d.di_nblocks--;
731 XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
732 XFS_TRANS_DQ_BCOUNT, -1L);
733 xfs_trans_binval(cur->bc_tp, cbp);
734 cur->bc_bufs[level - 1] = NULL;
413d57c9 735 be16_add_cpu(&block->bb_level, -1);
1da177e4
LT		 736 xfs_trans_log_inode(cur->bc_tp, ip,
737 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
738 cur->bc_nlevels--;
739 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
740 return 0;
741}
742
743/*
744 * Log key values from the btree block.
745 */
746STATIC void
747xfs_bmbt_log_keys(
748 xfs_btree_cur_t *cur,
749 xfs_buf_t *bp,
750 int kfirst,
751 int klast)
752{
1da177e4
LT		 753 xfs_trans_t *tp;
754
755 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
756 XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
757 tp = cur->bc_tp;
758 if (bp) {
759 xfs_bmbt_block_t *block;
760 int first;
761 xfs_bmbt_key_t *kp;
762 int last;
763
764 block = XFS_BUF_TO_BMBT_BLOCK(bp);
765 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
766 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
767 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
768 xfs_trans_log_buf(tp, bp, first, last);
769 } else {
770 xfs_inode_t *ip;
771
772 ip = cur->bc_private.b.ip;
773 xfs_trans_log_inode(tp, ip,
774 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
775 }
776 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
777}
778
779/*
780 * Log pointer values from the btree block.
781 */
782STATIC void
783xfs_bmbt_log_ptrs(
784 xfs_btree_cur_t *cur,
785 xfs_buf_t *bp,
786 int pfirst,
787 int plast)
788{
1da177e4
LT		 789 xfs_trans_t *tp;
790
791 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
792 XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
793 tp = cur->bc_tp;
794 if (bp) {
795 xfs_bmbt_block_t *block;
796 int first;
797 int last;
798 xfs_bmbt_ptr_t *pp;
799
800 block = XFS_BUF_TO_BMBT_BLOCK(bp);
801 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
802 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
803 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
804 xfs_trans_log_buf(tp, bp, first, last);
805 } else {
806 xfs_inode_t *ip;
807
808 ip = cur->bc_private.b.ip;
809 xfs_trans_log_inode(tp, ip,
810 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
811 }
812 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
813}
814
1da177e4
LT		 815/*
816 * Move 1 record left from cur/level if possible.
817 * Update cur to reflect the new path.
818 */
819STATIC int /* error */
820xfs_bmbt_lshift(
821 xfs_btree_cur_t *cur,
822 int level,
823 int *stat) /* success/failure */
824{
825 int error; /* error return value */
1da177e4
LT		 826#ifdef DEBUG
827 int i; /* loop counter */
828#endif
829 xfs_bmbt_key_t key; /* bmap btree key */
830 xfs_buf_t *lbp; /* left buffer pointer */
831 xfs_bmbt_block_t *left; /* left btree block */
832 xfs_bmbt_key_t *lkp=NULL; /* left btree key */
833 xfs_bmbt_ptr_t *lpp; /* left address pointer */
834 int lrecs; /* left record count */
835 xfs_bmbt_rec_t *lrp=NULL; /* left record pointer */
836 xfs_mount_t *mp; /* file system mount point */
837 xfs_buf_t *rbp; /* right buffer pointer */
838 xfs_bmbt_block_t *right; /* right btree block */
839 xfs_bmbt_key_t *rkp=NULL; /* right btree key */
840 xfs_bmbt_ptr_t *rpp=NULL; /* right address pointer */
841 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
842 int rrecs; /* right record count */
843
844 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
845 XFS_BMBT_TRACE_ARGI(cur, level);
846 if (level == cur->bc_nlevels - 1) {
847 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
848 *stat = 0;
849 return 0;
850 }
851 rbp = cur->bc_bufs[level];
852 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
853#ifdef DEBUG
854 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
855 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
856 return error;
857 }
858#endif
16259e7d 859 if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
1da177e4
LT		 860 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
861 *stat = 0;
862 return 0;
863 }
864 if (cur->bc_ptrs[level] <= 1) {
865 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
866 *stat = 0;
867 return 0;
868 }
869 mp = cur->bc_mp;
16259e7d 870 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
1da177e4
LT		 871 &lbp, XFS_BMAP_BTREE_REF))) {
872 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
873 return error;
874 }
875 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
876 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
877 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
878 return error;
879 }
16259e7d 880 if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1da177e4
LT		 881 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
882 *stat = 0;
883 return 0;
884 }
16259e7d 885 lrecs = be16_to_cpu(left->bb_numrecs) + 1;
1da177e4
LT		 886 if (level > 0) {
887 lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
888 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
889 *lkp = *rkp;
890 xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
891 lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
892 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
893#ifdef DEBUG
b113bcb8 894 if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
1da177e4
LT		 895 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
896 return error;
897 }
898#endif
d580ef6e 899 *lpp = *rpp;
1da177e4
LT		 900 xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
901 } else {
902 lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
903 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
904 *lrp = *rrp;
905 xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
906 }
16259e7d 907 left->bb_numrecs = cpu_to_be16(lrecs);
1da177e4
LT		 908 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
909#ifdef DEBUG
910 if (level > 0)
911 xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
912 else
913 xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
914#endif
16259e7d
CH		 915 rrecs = be16_to_cpu(right->bb_numrecs) - 1;
916 right->bb_numrecs = cpu_to_be16(rrecs);
1da177e4
LT		 917 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
918 if (level > 0) {
919#ifdef DEBUG
920 for (i = 0; i < rrecs; i++) {
b113bcb8 921 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
1da177e4
LT		 922 level))) {
923 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
924 return error;
925 }
926 }
927#endif
928 memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
929 memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
930 xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
931 xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
932 } else {
933 memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
934 xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
8801bb99 935 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1da177e4
LT		 936 rkp = &key;
937 }
938 if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
939 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
940 return error;
941 }
942 cur->bc_ptrs[level]--;
943 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
944 *stat = 1;
945 return 0;
946}
947
948/*
949 * Move 1 record right from cur/level if possible.
950 * Update cur to reflect the new path.
951 */
952STATIC int /* error */
953xfs_bmbt_rshift(
954 xfs_btree_cur_t *cur,
955 int level,
956 int *stat) /* success/failure */
957{
958 int error; /* error return value */
1da177e4
LT		 959 int i; /* loop counter */
960 xfs_bmbt_key_t key; /* bmap btree key */
961 xfs_buf_t *lbp; /* left buffer pointer */
962 xfs_bmbt_block_t *left; /* left btree block */
963 xfs_bmbt_key_t *lkp; /* left btree key */
964 xfs_bmbt_ptr_t *lpp; /* left address pointer */
965 xfs_bmbt_rec_t *lrp; /* left record pointer */
966 xfs_mount_t *mp; /* file system mount point */
967 xfs_buf_t *rbp; /* right buffer pointer */
968 xfs_bmbt_block_t *right; /* right btree block */
969 xfs_bmbt_key_t *rkp; /* right btree key */
970 xfs_bmbt_ptr_t *rpp; /* right address pointer */
971 xfs_bmbt_rec_t *rrp=NULL; /* right record pointer */
972 struct xfs_btree_cur *tcur; /* temporary btree cursor */
973
974 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
975 XFS_BMBT_TRACE_ARGI(cur, level);
976 if (level == cur->bc_nlevels - 1) {
977 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
978 *stat = 0;
979 return 0;
980 }
981 lbp = cur->bc_bufs[level];
982 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
983#ifdef DEBUG
984 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
985 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
986 return error;
987 }
988#endif
16259e7d 989 if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
1da177e4
LT		 990 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
991 *stat = 0;
992 return 0;
993 }
16259e7d 994 if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
1da177e4
LT		 995 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
996 *stat = 0;
997 return 0;
998 }
999 mp = cur->bc_mp;
16259e7d 1000 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
1da177e4
LT		 1001 &rbp, XFS_BMAP_BTREE_REF))) {
1002 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1003 return error;
1004 }
1005 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1006 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
1007 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1008 return error;
1009 }
16259e7d 1010 if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1da177e4
LT		 1011 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1012 *stat = 0;
1013 return 0;
1014 }
1015 if (level > 0) {
16259e7d
CH		 1016 lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1017 lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1da177e4
LT		 1018 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1019 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1020#ifdef DEBUG
16259e7d 1021 for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
576039cf 1022 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1da177e4
LT		 1023 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1024 return error;
1025 }
1026 }
1027#endif
16259e7d
CH		 1028 memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1029 memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1da177e4 1030#ifdef DEBUG
b113bcb8 1031 if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
1da177e4
LT		 1032 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1033 return error;
1034 }
1035#endif
1036 *rkp = *lkp;
d580ef6e 1037 *rpp = *lpp;
16259e7d
CH		 1038 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1039 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
1da177e4 1040 } else {
16259e7d 1041 lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
1da177e4 1042 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
16259e7d 1043 memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1da177e4 1044 *rrp = *lrp;
16259e7d 1045 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
8801bb99 1046 key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
1da177e4
LT		 1047 rkp = &key;
1048 }
413d57c9 1049 be16_add_cpu(&left->bb_numrecs, -1);
1da177e4 1050 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
413d57c9 1051 be16_add_cpu(&right->bb_numrecs, 1);
1da177e4
LT		 1052#ifdef DEBUG
1053 if (level > 0)
1054 xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
1055 else
1056 xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
1057#endif
1058 xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
1059 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
1060 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1061 return error;
1062 }
1063 i = xfs_btree_lastrec(tcur, level);
1064 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
637aa50f 1065 if ((error = xfs_btree_increment(tcur, level, &i))) {
1da177e4
LT		 1066 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1067 goto error1;
1068 }
1069 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1070 if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {
1071 XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
1072 goto error1;
1073 }
1074 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
1075 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1076 *stat = 1;
1077 return 0;
1078error0:
1079 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1080error1:
1081 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
1082 return error;
1083}
1084
1085/*
1086 * Determine the extent state.
1087 */
1088/* ARGSUSED */
1089STATIC xfs_exntst_t
1090xfs_extent_state(
1091 xfs_filblks_t blks,
1092 int extent_flag)
1093{
1094 if (extent_flag) {
1095 ASSERT(blks != 0); /* saved for DMIG */
1096 return XFS_EXT_UNWRITTEN;
1097 }
1098 return XFS_EXT_NORM;
1099}
1100
1101
1102/*
1103 * Split cur/level block in half.
1104 * Return new block number and its first record (to be inserted into parent).
1105 */
1106STATIC int /* error */
1107xfs_bmbt_split(
1108 xfs_btree_cur_t *cur,
1109 int level,
1110 xfs_fsblock_t *bnop,
8801bb99 1111 __uint64_t *startoff,
1da177e4
LT		 1112 xfs_btree_cur_t **curp,
1113 int *stat) /* success/failure */
1114{
1115 xfs_alloc_arg_t args; /* block allocation args */
1116 int error; /* error return value */
1da177e4
LT		 1117 int i; /* loop counter */
1118 xfs_fsblock_t lbno; /* left sibling block number */
1119 xfs_buf_t *lbp; /* left buffer pointer */
1120 xfs_bmbt_block_t *left; /* left btree block */
1121 xfs_bmbt_key_t *lkp; /* left btree key */
1122 xfs_bmbt_ptr_t *lpp; /* left address pointer */
1123 xfs_bmbt_rec_t *lrp; /* left record pointer */
1124 xfs_buf_t *rbp; /* right buffer pointer */
1125 xfs_bmbt_block_t *right; /* right btree block */
1126 xfs_bmbt_key_t *rkp; /* right btree key */
1127 xfs_bmbt_ptr_t *rpp; /* right address pointer */
1128 xfs_bmbt_block_t *rrblock; /* right-right btree block */
1129 xfs_buf_t *rrbp; /* right-right buffer pointer */
1130 xfs_bmbt_rec_t *rrp; /* right record pointer */
1131
1132 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
8c4ed633
CH		 1133 // disable until merged into common code
1134// XFS_BMBT_TRACE_ARGIFK(cur, level, *bnop, *startoff);
1da177e4
LT		 1135 args.tp = cur->bc_tp;
1136 args.mp = cur->bc_mp;
1137 lbp = cur->bc_bufs[level];
1138 lbno = XFS_DADDR_TO_FSB(args.mp, XFS_BUF_ADDR(lbp));
1139 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
1140 args.fsbno = cur->bc_private.b.firstblock;
d210a28c 1141 args.firstblock = args.fsbno;
4ddd8bb1 1142 args.minleft = 0;
1da177e4
LT		 1143 if (args.fsbno == NULLFSBLOCK) {
1144 args.fsbno = lbno;
1145 args.type = XFS_ALLOCTYPE_START_BNO;
4ddd8bb1
LM		 1146 /*
1147 * Make sure there is sufficient room left in the AG to
1148 * complete a full tree split for an extent insert. If
1149 * we are converting the middle part of an extent then
1150 * we may need space for two tree splits.
1151 *
1152 * We are relying on the caller to make the correct block
1153 * reservation for this operation to succeed. If the
1154 * reservation amount is insufficient then we may fail a
1155 * block allocation here and corrupt the filesystem.
1156 */
1157 args.minleft = xfs_trans_get_block_res(args.tp);
b877e3d3
LM		 1158 } else if (cur->bc_private.b.flist->xbf_low)
1159 args.type = XFS_ALLOCTYPE_START_BNO;
1160 else
1da177e4 1161 args.type = XFS_ALLOCTYPE_NEAR_BNO;
4ddd8bb1 1162 args.mod = args.alignment = args.total = args.isfl =
1da177e4
LT		 1163 args.userdata = args.minalignslop = 0;
1164 args.minlen = args.maxlen = args.prod = 1;
1165 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1166 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1167 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1168 return XFS_ERROR(ENOSPC);
1169 }
1170 if ((error = xfs_alloc_vextent(&args))) {
1171 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1172 return error;
1173 }
313b5c76
LM		 1174 if (args.fsbno == NULLFSBLOCK && args.minleft) {
1175 /*
1176 * Could not find an AG with enough free space to satisfy
1177 * a full btree split. Try again without minleft and if
1178 * successful activate the lowspace algorithm.
1179 */
1180 args.fsbno = 0;
1181 args.type = XFS_ALLOCTYPE_FIRST_AG;
1182 args.minleft = 0;
1183 if ((error = xfs_alloc_vextent(&args))) {
1184 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1185 return error;
1186 }
1187 cur->bc_private.b.flist->xbf_low = 1;
1188 }
1da177e4
LT		 1189 if (args.fsbno == NULLFSBLOCK) {
1190 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1191 *stat = 0;
1192 return 0;
1193 }
1194 ASSERT(args.len == 1);
1195 cur->bc_private.b.firstblock = args.fsbno;
1196 cur->bc_private.b.allocated++;
1197 cur->bc_private.b.ip->i_d.di_nblocks++;
1198 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1199 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1200 XFS_TRANS_DQ_BCOUNT, 1L);
1201 rbp = xfs_btree_get_bufl(args.mp, args.tp, args.fsbno, 0);
1202 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
1203#ifdef DEBUG
1204 if ((error = xfs_btree_check_lblock(cur, left, level, rbp))) {
1205 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1206 return error;
1207 }
1208#endif
16259e7d
CH		 1209 right->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1210 right->bb_level = left->bb_level;
1211 right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
1212 if ((be16_to_cpu(left->bb_numrecs) & 1) &&
1213 cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
413d57c9 1214 be16_add_cpu(&right->bb_numrecs, 1);
16259e7d 1215 i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
1da177e4
LT		 1216 if (level > 0) {
1217 lkp = XFS_BMAP_KEY_IADDR(left, i, cur);
1218 lpp = XFS_BMAP_PTR_IADDR(left, i, cur);
1219 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
1220 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
1221#ifdef DEBUG
16259e7d 1222 for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
b113bcb8 1223 if ((error = xfs_btree_check_lptr_disk(cur, lpp[i], level))) {
1da177e4
LT		 1224 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1225 return error;
1226 }
1227 }
1228#endif
16259e7d
CH		 1229 memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
1230 memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
1231 xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
1232 xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
8801bb99 1233 *startoff = be64_to_cpu(rkp->br_startoff);
1da177e4
LT		 1234 } else {
1235 lrp = XFS_BMAP_REC_IADDR(left, i, cur);
1236 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
16259e7d
CH		 1237 memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
1238 xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
8801bb99 1239 *startoff = xfs_bmbt_disk_get_startoff(rrp);
1da177e4 1240 }
413d57c9 1241 be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
16259e7d
CH		 1242 right->bb_rightsib = left->bb_rightsib;
1243 left->bb_rightsib = cpu_to_be64(args.fsbno);
1244 right->bb_leftsib = cpu_to_be64(lbno);
1da177e4
LT		 1245 xfs_bmbt_log_block(cur, rbp, XFS_BB_ALL_BITS);
1246 xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
16259e7d 1247 if (be64_to_cpu(right->bb_rightsib) != NULLDFSBNO) {
1da177e4 1248 if ((error = xfs_btree_read_bufl(args.mp, args.tp,
16259e7d 1249 be64_to_cpu(right->bb_rightsib), 0, &rrbp,
1da177e4
LT		 1250 XFS_BMAP_BTREE_REF))) {
1251 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1252 return error;
1253 }
1254 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
1255 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
1256 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1257 return error;
1258 }
16259e7d 1259 rrblock->bb_leftsib = cpu_to_be64(args.fsbno);
1da177e4
LT		 1260 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
1261 }
16259e7d 1262 if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
1da177e4 1263 xfs_btree_setbuf(cur, level, rbp);
16259e7d 1264 cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
1da177e4
LT		 1265 }
1266 if (level + 1 < cur->bc_nlevels) {
1267 if ((error = xfs_btree_dup_cursor(cur, curp))) {
1268 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1269 return error;
1270 }
1271 (*curp)->bc_ptrs[level + 1]++;
1272 }
1273 *bnop = args.fsbno;
1274 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1275 *stat = 1;
1276 return 0;
1277}
1278
1279
1280/*
1281 * Update keys for the record.
1282 */
1283STATIC int
1284xfs_bmbt_updkey(
1285 xfs_btree_cur_t *cur,
1286 xfs_bmbt_key_t *keyp, /* on-disk format */
1287 int level)
1288{
1289 xfs_bmbt_block_t *block;
1290 xfs_buf_t *bp;
1291#ifdef DEBUG
1292 int error;
1da177e4
LT		 1293#endif
1294 xfs_bmbt_key_t *kp;
1295 int ptr;
1296
1297 ASSERT(level >= 1);
1298 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1299 XFS_BMBT_TRACE_ARGIK(cur, level, keyp);
1300 for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1301 block = xfs_bmbt_get_block(cur, level, &bp);
1302#ifdef DEBUG
1303 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
1304 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1305 return error;
1306 }
1307#endif
1308 ptr = cur->bc_ptrs[level];
1309 kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
1310 *kp = *keyp;
1311 xfs_bmbt_log_keys(cur, bp, ptr, ptr);
1312 }
1313 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1314 return 0;
1315}
1316
1317/*
1318 * Convert on-disk form of btree root to in-memory form.
1319 */
1320void
1321xfs_bmdr_to_bmbt(
1322 xfs_bmdr_block_t *dblock,
1323 int dblocklen,
1324 xfs_bmbt_block_t *rblock,
1325 int rblocklen)
1326{
1327 int dmxr;
1328 xfs_bmbt_key_t *fkp;
576039cf 1329 __be64 *fpp;
1da177e4 1330 xfs_bmbt_key_t *tkp;
576039cf 1331 __be64 *tpp;
1da177e4 1332
16259e7d
CH		 1333 rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
1334 rblock->bb_level = dblock->bb_level;
1335 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1336 rblock->bb_numrecs = dblock->bb_numrecs;
1337 rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
1338 rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
1da177e4 1339 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2c36dded 1340 fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1da177e4 1341 tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2c36dded 1342 fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1da177e4 1343 tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
16259e7d 1344 dmxr = be16_to_cpu(dblock->bb_numrecs);
1da177e4 1345 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
576039cf 1346 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1da177e4
LT		 1347}
1348
1da177e4
LT		 1349/*
1350 * Delete the record pointed to by cur.
1351 */
1352int /* error */
1353xfs_bmbt_delete(
1354 xfs_btree_cur_t *cur,
1355 int *stat) /* success/failure */
1356{
1357 int error; /* error return value */
1da177e4
LT		 1358 int i;
1359 int level;
1360
1361 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1362 for (level = 0, i = 2; i == 2; level++) {
1363 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
1364 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1365 return error;
1366 }
1367 }
1368 if (i == 0) {
1369 for (level = 1; level < cur->bc_nlevels; level++) {
1370 if (cur->bc_ptrs[level] == 0) {
8df4da4a 1371 if ((error = xfs_btree_decrement(cur, level,
1da177e4
LT		 1372 &i))) {
1373 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1374 return error;
1375 }
1376 break;
1377 }
1378 }
1379 }
1380 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1381 *stat = i;
1382 return 0;
1383}
1384
1385/*
1386 * Convert a compressed bmap extent record to an uncompressed form.
1387 * This code must be in sync with the routines xfs_bmbt_get_startoff,
1388 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
1389 */
1390
7989cb8e 1391STATIC_INLINE void
1da177e4
LT		 1392__xfs_bmbt_get_all(
1393 __uint64_t l0,
1394 __uint64_t l1,
1395 xfs_bmbt_irec_t *s)
1396{
1397 int ext_flag;
1398 xfs_exntst_t st;
1399
1400 ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
1401 s->br_startoff = ((xfs_fileoff_t)l0 &
1402 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1403#if XFS_BIG_BLKNOS
1404 s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
1405 (((xfs_fsblock_t)l1) >> 21);
1406#else
1407#ifdef DEBUG
1408 {
1409 xfs_dfsbno_t b;
1410
1411 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
1412 (((xfs_dfsbno_t)l1) >> 21);
1413 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1414 s->br_startblock = (xfs_fsblock_t)b;
1415 }
1416#else /* !DEBUG */
1417 s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
1418#endif /* DEBUG */
1419#endif /* XFS_BIG_BLKNOS */
1420 s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
1421 /* This is xfs_extent_state() in-line */
1422 if (ext_flag) {
1423 ASSERT(s->br_blockcount != 0); /* saved for DMIG */
1424 st = XFS_EXT_UNWRITTEN;
1425 } else
1426 st = XFS_EXT_NORM;
1427 s->br_state = st;
1428}
1429
1430void
1431xfs_bmbt_get_all(
a6f64d4a 1432 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1433 xfs_bmbt_irec_t *s)
1434{
1435 __xfs_bmbt_get_all(r->l0, r->l1, s);
1436}
1437
1438/*
1439 * Get the block pointer for the given level of the cursor.
1440 * Fill in the buffer pointer, if applicable.
1441 */
1442xfs_bmbt_block_t *
1443xfs_bmbt_get_block(
1444 xfs_btree_cur_t *cur,
1445 int level,
1446 xfs_buf_t **bpp)
1447{
1448 xfs_ifork_t *ifp;
1449 xfs_bmbt_block_t *rval;
1450
1451 if (level < cur->bc_nlevels - 1) {
1452 *bpp = cur->bc_bufs[level];
1453 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
1454 } else {
1455 *bpp = NULL;
1456 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
1457 cur->bc_private.b.whichfork);
1458 rval = ifp->if_broot;
1459 }
1460 return rval;
1461}
1462
1463/*
1464 * Extract the blockcount field from an in memory bmap extent record.
1465 */
1466xfs_filblks_t
1467xfs_bmbt_get_blockcount(
a6f64d4a 1468 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 1469{
1470 return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
1471}
1472
1473/*
1474 * Extract the startblock field from an in memory bmap extent record.
1475 */
1476xfs_fsblock_t
1477xfs_bmbt_get_startblock(
a6f64d4a 1478 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 1479{
1480#if XFS_BIG_BLKNOS
1481 return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1482 (((xfs_fsblock_t)r->l1) >> 21);
1483#else
1484#ifdef DEBUG
1485 xfs_dfsbno_t b;
1486
1487 b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
1488 (((xfs_dfsbno_t)r->l1) >> 21);
1489 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
1490 return (xfs_fsblock_t)b;
1491#else /* !DEBUG */
1492 return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
1493#endif /* DEBUG */
1494#endif /* XFS_BIG_BLKNOS */
1495}
1496
1497/*
1498 * Extract the startoff field from an in memory bmap extent record.
1499 */
1500xfs_fileoff_t
1501xfs_bmbt_get_startoff(
a6f64d4a 1502 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 1503{
1504 return ((xfs_fileoff_t)r->l0 &
1505 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1506}
1507
1508xfs_exntst_t
1509xfs_bmbt_get_state(
a6f64d4a 1510 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 1511{
1512 int ext_flag;
1513
1514 ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
1515 return xfs_extent_state(xfs_bmbt_get_blockcount(r),
1516 ext_flag);
1517}
1518
1da177e4
LT		 1519/* Endian flipping versions of the bmbt extraction functions */
1520void
1521xfs_bmbt_disk_get_all(
1522 xfs_bmbt_rec_t *r,
1523 xfs_bmbt_irec_t *s)
1524{
cd8b0a97 1525 __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
1da177e4
LT		 1526}
1527
1528/*
1529 * Extract the blockcount field from an on disk bmap extent record.
1530 */
1531xfs_filblks_t
1532xfs_bmbt_disk_get_blockcount(
1533 xfs_bmbt_rec_t *r)
1534{
cd8b0a97 1535 return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
1da177e4
LT		 1536}
1537
1da177e4
LT		 1538/*
1539 * Extract the startoff field from a disk format bmap extent record.
1540 */
1541xfs_fileoff_t
1542xfs_bmbt_disk_get_startoff(
1543 xfs_bmbt_rec_t *r)
1544{
cd8b0a97 1545 return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
1da177e4
LT		 1546 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
1547}
1da177e4 1548
1da177e4
LT		 1549/*
1550 * Insert the current record at the point referenced by cur.
59a33f9f
DC		 1551 *
1552 * A multi-level split of the tree on insert will invalidate the original
ddea2d52
LM		 1553 * cursor. All callers of this function should assume that the cursor is
1554 * no longer valid and revalidate it.
1da177e4
LT		 1555 */
1556int /* error */
1557xfs_bmbt_insert(
1558 xfs_btree_cur_t *cur,
1559 int *stat) /* success/failure */
1560{
1561 int error; /* error return value */
1da177e4
LT		 1562 int i;
1563 int level;
1564 xfs_fsblock_t nbno;
1565 xfs_btree_cur_t *ncur;
1566 xfs_bmbt_rec_t nrec;
1567 xfs_btree_cur_t *pcur;
1568
1569 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1570 level = 0;
1571 nbno = NULLFSBLOCK;
1572 xfs_bmbt_disk_set_all(&nrec, &cur->bc_rec.b);
1121b219 1573 ncur = NULL;
1da177e4
LT		 1574 pcur = cur;
1575 do {
1576 if ((error = xfs_bmbt_insrec(pcur, level++, &nbno, &nrec, &ncur,
1577 &i))) {
1578 if (pcur != cur)
1579 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
ddea2d52
LM		 1580 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1581 return error;
1da177e4
LT		 1582 }
1583 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1584 if (pcur != cur && (ncur || nbno == NULLFSBLOCK)) {
1585 cur->bc_nlevels = pcur->bc_nlevels;
1586 cur->bc_private.b.allocated +=
1587 pcur->bc_private.b.allocated;
1588 pcur->bc_private.b.allocated = 0;
1589 ASSERT((cur->bc_private.b.firstblock != NULLFSBLOCK) ||
71ddabb9 1590 XFS_IS_REALTIME_INODE(cur->bc_private.b.ip));
1da177e4
LT		 1591 cur->bc_private.b.firstblock =
1592 pcur->bc_private.b.firstblock;
1593 ASSERT(cur->bc_private.b.flist ==
1594 pcur->bc_private.b.flist);
1595 xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
1596 }
1597 if (ncur) {
1598 pcur = ncur;
1121b219 1599 ncur = NULL;
1da177e4
LT		 1600 }
1601 } while (nbno != NULLFSBLOCK);
1602 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1603 *stat = i;
1604 return 0;
1605error0:
1606 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1607 return error;
1608}
1609
1610/*
1611 * Log fields from the btree block header.
1612 */
1613void
1614xfs_bmbt_log_block(
1615 xfs_btree_cur_t *cur,
1616 xfs_buf_t *bp,
1617 int fields)
1618{
1619 int first;
1da177e4
LT		 1620 int last;
1621 xfs_trans_t *tp;
1622 static const short offsets[] = {
1623 offsetof(xfs_bmbt_block_t, bb_magic),
1624 offsetof(xfs_bmbt_block_t, bb_level),
1625 offsetof(xfs_bmbt_block_t, bb_numrecs),
1626 offsetof(xfs_bmbt_block_t, bb_leftsib),
1627 offsetof(xfs_bmbt_block_t, bb_rightsib),
1628 sizeof(xfs_bmbt_block_t)
1629 };
1630
1631 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1632 XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
1633 tp = cur->bc_tp;
1634 if (bp) {
1635 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
1636 &last);
1637 xfs_trans_log_buf(tp, bp, first, last);
1638 } else
1639 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
1640 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
1641 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1642}
1643
1644/*
1645 * Log record values from the btree block.
1646 */
1647void
1648xfs_bmbt_log_recs(
1649 xfs_btree_cur_t *cur,
1650 xfs_buf_t *bp,
1651 int rfirst,
1652 int rlast)
1653{
1654 xfs_bmbt_block_t *block;
1655 int first;
1da177e4
LT		 1656 int last;
1657 xfs_bmbt_rec_t *rp;
1658 xfs_trans_t *tp;
1659
1660 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1661 XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
1662 ASSERT(bp);
1663 tp = cur->bc_tp;
1664 block = XFS_BUF_TO_BMBT_BLOCK(bp);
1665 rp = XFS_BMAP_REC_DADDR(block, 1, cur);
1666 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
1667 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
1668 xfs_trans_log_buf(tp, bp, first, last);
1669 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1670}
1671
1da177e4
LT		 1672/*
1673 * Give the bmap btree a new root block. Copy the old broot contents
1674 * down into a real block and make the broot point to it.
1675 */
1676int /* error */
1677xfs_bmbt_newroot(
1678 xfs_btree_cur_t *cur, /* btree cursor */
1679 int *logflags, /* logging flags for inode */
1680 int *stat) /* return status - 0 fail */
1681{
1682 xfs_alloc_arg_t args; /* allocation arguments */
1683 xfs_bmbt_block_t *block; /* bmap btree block */
1684 xfs_buf_t *bp; /* buffer for block */
1685 xfs_bmbt_block_t *cblock; /* child btree block */
1686 xfs_bmbt_key_t *ckp; /* child key pointer */
1687 xfs_bmbt_ptr_t *cpp; /* child ptr pointer */
1688 int error; /* error return code */
1da177e4
LT		 1689#ifdef DEBUG
1690 int i; /* loop counter */
1691#endif
1692 xfs_bmbt_key_t *kp; /* pointer to bmap btree key */
1693 int level; /* btree level */
1694 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
1695
1696 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
1697 level = cur->bc_nlevels - 1;
1698 block = xfs_bmbt_get_block(cur, level, &bp);
1699 /*
1700 * Copy the root into a real block.
1701 */
1702 args.mp = cur->bc_mp;
1703 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
1704 args.tp = cur->bc_tp;
1705 args.fsbno = cur->bc_private.b.firstblock;
1706 args.mod = args.minleft = args.alignment = args.total = args.isfl =
1707 args.userdata = args.minalignslop = 0;
1708 args.minlen = args.maxlen = args.prod = 1;
1709 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
d210a28c 1710 args.firstblock = args.fsbno;
1da177e4
LT		 1711 if (args.fsbno == NULLFSBLOCK) {
1712#ifdef DEBUG
b113bcb8 1713 if ((error = xfs_btree_check_lptr_disk(cur, *pp, level))) {
1da177e4
LT		 1714 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1715 return error;
1716 }
1717#endif
576039cf 1718 args.fsbno = be64_to_cpu(*pp);
1da177e4 1719 args.type = XFS_ALLOCTYPE_START_BNO;
b877e3d3
LM		 1720 } else if (cur->bc_private.b.flist->xbf_low)
1721 args.type = XFS_ALLOCTYPE_START_BNO;
1722 else
1da177e4
LT		 1723 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1724 if ((error = xfs_alloc_vextent(&args))) {
1725 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1726 return error;
1727 }
1728 if (args.fsbno == NULLFSBLOCK) {
1729 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1730 *stat = 0;
1731 return 0;
1732 }
1733 ASSERT(args.len == 1);
1734 cur->bc_private.b.firstblock = args.fsbno;
1735 cur->bc_private.b.allocated++;
1736 cur->bc_private.b.ip->i_d.di_nblocks++;
1737 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1738 XFS_TRANS_DQ_BCOUNT, 1L);
1739 bp = xfs_btree_get_bufl(args.mp, cur->bc_tp, args.fsbno, 0);
1740 cblock = XFS_BUF_TO_BMBT_BLOCK(bp);
1741 *cblock = *block;
413d57c9 1742 be16_add_cpu(&block->bb_level, 1);
16259e7d 1743 block->bb_numrecs = cpu_to_be16(1);
1da177e4
LT		 1744 cur->bc_nlevels++;
1745 cur->bc_ptrs[level + 1] = 1;
1746 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
1747 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
16259e7d 1748 memcpy(ckp, kp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*kp));
1da177e4
LT		 1749 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
1750#ifdef DEBUG
16259e7d 1751 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
b113bcb8 1752 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
1da177e4
LT		 1753 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1754 return error;
1755 }
1756 }
1757#endif
16259e7d 1758 memcpy(cpp, pp, be16_to_cpu(cblock->bb_numrecs) * sizeof(*pp));
1da177e4 1759#ifdef DEBUG
576039cf 1760 if ((error = xfs_btree_check_lptr(cur, args.fsbno, level))) {
1da177e4
LT		 1761 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
1762 return error;
1763 }
1764#endif
576039cf 1765 *pp = cpu_to_be64(args.fsbno);
16259e7d 1766 xfs_iroot_realloc(cur->bc_private.b.ip, 1 - be16_to_cpu(cblock->bb_numrecs),
1da177e4
LT		 1767 cur->bc_private.b.whichfork);
1768 xfs_btree_setbuf(cur, level, bp);
1769 /*
1770 * Do all this logging at the end so that
1771 * the root is at the right level.
1772 */
1773 xfs_bmbt_log_block(cur, bp, XFS_BB_ALL_BITS);
16259e7d
CH		 1774 xfs_bmbt_log_keys(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
1775 xfs_bmbt_log_ptrs(cur, bp, 1, be16_to_cpu(cblock->bb_numrecs));
1da177e4
LT		 1776 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
1777 *logflags |=
1778 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
1779 *stat = 1;
1780 return 0;
1781}
1782
1da177e4
LT		 1783/*
1784 * Set all the fields in a bmap extent record from the arguments.
1785 */
1786void
1787xfs_bmbt_set_allf(
8cba4344
CH		 1788 xfs_bmbt_rec_host_t *r,
1789 xfs_fileoff_t startoff,
1790 xfs_fsblock_t startblock,
1791 xfs_filblks_t blockcount,
1792 xfs_exntst_t state)
1da177e4 1793{
8cba4344
CH		 1794 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1795
1796 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1797 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1798 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1da177e4 1799
1da177e4 1800#if XFS_BIG_BLKNOS
8cba4344
CH		 1801 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1802
1da177e4 1803 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344
CH		 1804 ((xfs_bmbt_rec_base_t)startoff << 9) |
1805 ((xfs_bmbt_rec_base_t)startblock >> 43);
1806 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
1807 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 1808 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1809#else /* !XFS_BIG_BLKNOS */
ddc6d3b3 1810 if (ISNULLSTARTBLOCK(startblock)) {
1da177e4 1811 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344 1812 ((xfs_bmbt_rec_base_t)startoff << 9) |
1da177e4
LT		 1813 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1814 r->l1 = XFS_MASK64HI(11) |
8cba4344
CH		 1815 ((xfs_bmbt_rec_base_t)startblock << 21) |
1816 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 1817 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1818 } else {
1819 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344
CH		 1820 ((xfs_bmbt_rec_base_t)startoff << 9);
1821 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
1822 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 1823 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1824 }
1825#endif /* XFS_BIG_BLKNOS */
1826}
1827
1da177e4
LT		 1828/*
1829 * Set all the fields in a bmap extent record from the uncompressed form.
1830 */
1831void
8cba4344
CH		 1832xfs_bmbt_set_all(
1833 xfs_bmbt_rec_host_t *r,
1834 xfs_bmbt_irec_t *s)
1da177e4 1835{
8cba4344
CH		 1836 xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
1837 s->br_blockcount, s->br_state);
1da177e4
LT		 1838}
1839
8cba4344 1840
1da177e4
LT		 1841/*
1842 * Set all the fields in a disk format bmap extent record from the arguments.
1843 */
1844void
1845xfs_bmbt_disk_set_allf(
8cba4344
CH		 1846 xfs_bmbt_rec_t *r,
1847 xfs_fileoff_t startoff,
1848 xfs_fsblock_t startblock,
1849 xfs_filblks_t blockcount,
1850 xfs_exntst_t state)
1da177e4 1851{
8cba4344
CH		 1852 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1853
1854 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1855 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1856 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1da177e4 1857
1da177e4 1858#if XFS_BIG_BLKNOS
8cba4344
CH		 1859 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1860
cd8b0a97 1861 r->l0 = cpu_to_be64(
8cba4344
CH		 1862 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1863 ((xfs_bmbt_rec_base_t)startoff << 9) |
1864 ((xfs_bmbt_rec_base_t)startblock >> 43));
cd8b0a97 1865 r->l1 = cpu_to_be64(
8cba4344
CH		 1866 ((xfs_bmbt_rec_base_t)startblock << 21) |
1867 ((xfs_bmbt_rec_base_t)blockcount &
1868 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1da177e4 1869#else /* !XFS_BIG_BLKNOS */
ddc6d3b3 1870 if (ISNULLSTARTBLOCK(startblock)) {
cd8b0a97 1871 r->l0 = cpu_to_be64(
8cba4344
CH		 1872 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1873 ((xfs_bmbt_rec_base_t)startoff << 9) |
1874 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
cd8b0a97 1875 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
8cba4344
CH		 1876 ((xfs_bmbt_rec_base_t)startblock << 21) |
1877 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 1878 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1879 } else {
cd8b0a97 1880 r->l0 = cpu_to_be64(
8cba4344
CH		 1881 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1882 ((xfs_bmbt_rec_base_t)startoff << 9));
cd8b0a97 1883 r->l1 = cpu_to_be64(
8cba4344
CH		 1884 ((xfs_bmbt_rec_base_t)startblock << 21) |
1885 ((xfs_bmbt_rec_base_t)blockcount &
1886 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1da177e4
LT		 1887 }
1888#endif /* XFS_BIG_BLKNOS */
1889}
8cba4344
CH		 1890
1891/*
1892 * Set all the fields in a bmap extent record from the uncompressed form.
1893 */
1894void
1895xfs_bmbt_disk_set_all(
1896 xfs_bmbt_rec_t *r,
1897 xfs_bmbt_irec_t *s)
1898{
1899 xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
1900 s->br_blockcount, s->br_state);
1901}
1da177e4
LT		 1902
1903/*
1904 * Set the blockcount field in a bmap extent record.
1905 */
1906void
1907xfs_bmbt_set_blockcount(
a6f64d4a 1908 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1909 xfs_filblks_t v)
1910{
1911 ASSERT((v & XFS_MASK64HI(43)) == 0);
1912 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
1913 (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
1914}
1915
1916/*
1917 * Set the startblock field in a bmap extent record.
1918 */
1919void
1920xfs_bmbt_set_startblock(
a6f64d4a 1921 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1922 xfs_fsblock_t v)
1923{
1924#if XFS_BIG_BLKNOS
1925 ASSERT((v & XFS_MASK64HI(12)) == 0);
1926 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
1927 (xfs_bmbt_rec_base_t)(v >> 43);
1928 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
1929 (xfs_bmbt_rec_base_t)(v << 21);
1930#else /* !XFS_BIG_BLKNOS */
1931 if (ISNULLSTARTBLOCK(v)) {
1932 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1933 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
1934 ((xfs_bmbt_rec_base_t)v << 21) |
1935 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1936 } else {
1937 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1938 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
1939 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1940 }
1941#endif /* XFS_BIG_BLKNOS */
1942}
1943
1944/*
1945 * Set the startoff field in a bmap extent record.
1946 */
1947void
1948xfs_bmbt_set_startoff(
a6f64d4a 1949 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1950 xfs_fileoff_t v)
1951{
1952 ASSERT((v & XFS_MASK64HI(9)) == 0);
1953 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
1954 ((xfs_bmbt_rec_base_t)v << 9) |
1955 (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1956}
1957
1958/*
1959 * Set the extent state field in a bmap extent record.
1960 */
1961void
1962xfs_bmbt_set_state(
a6f64d4a 1963 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1964 xfs_exntst_t v)
1965{
1966 ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
1967 if (v == XFS_EXT_NORM)
1968 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
1969 else
1970 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
1971}
1972
1973/*
1974 * Convert in-memory form of btree root to on-disk form.
1975 */
1976void
1977xfs_bmbt_to_bmdr(
1978 xfs_bmbt_block_t *rblock,
1979 int rblocklen,
1980 xfs_bmdr_block_t *dblock,
1981 int dblocklen)
1982{
1983 int dmxr;
1984 xfs_bmbt_key_t *fkp;
576039cf 1985 __be64 *fpp;
1da177e4 1986 xfs_bmbt_key_t *tkp;
576039cf 1987 __be64 *tpp;
1da177e4 1988
16259e7d
CH		 1989 ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
1990 ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
1991 ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
1992 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1993 dblock->bb_level = rblock->bb_level;
1994 dblock->bb_numrecs = rblock->bb_numrecs;
1da177e4
LT		 1995 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1996 fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2c36dded 1997 tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1da177e4 1998 fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
2c36dded 1999 tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
16259e7d 2000 dmxr = be16_to_cpu(dblock->bb_numrecs);
1da177e4 2001 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
576039cf 2002 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1da177e4
LT		 2003}
2004
2005/*
2006 * Update the record to the passed values.
2007 */
2008int
2009xfs_bmbt_update(
2010 xfs_btree_cur_t *cur,
2011 xfs_fileoff_t off,
2012 xfs_fsblock_t bno,
2013 xfs_filblks_t len,
2014 xfs_exntst_t state)
2015{
2016 xfs_bmbt_block_t *block;
2017 xfs_buf_t *bp;
2018 int error;
1da177e4
LT		 2019 xfs_bmbt_key_t key;
2020 int ptr;
2021 xfs_bmbt_rec_t *rp;
2022
2023 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
2024 XFS_BMBT_TRACE_ARGFFFI(cur, (xfs_dfiloff_t)off, (xfs_dfsbno_t)bno,
2025 (xfs_dfilblks_t)len, (int)state);
2026 block = xfs_bmbt_get_block(cur, 0, &bp);
2027#ifdef DEBUG
2028 if ((error = xfs_btree_check_lblock(cur, block, 0, bp))) {
2029 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2030 return error;
2031 }
2032#endif
2033 ptr = cur->bc_ptrs[0];
2034 rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
2035 xfs_bmbt_disk_set_allf(rp, off, bno, len, state);
2036 xfs_bmbt_log_recs(cur, bp, ptr, ptr);
2037 if (ptr > 1) {
2038 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2039 return 0;
2040 }
8801bb99 2041 key.br_startoff = cpu_to_be64(off);
1da177e4
LT		 2042 if ((error = xfs_bmbt_updkey(cur, &key, 1))) {
2043 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
2044 return error;
2045 }
2046 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
2047 return 0;
2048}
2049
2050/*
4eea22f0 2051 * Check extent records, which have just been read, for
1da177e4
LT		 2052 * any bit in the extent flag field. ASSERT on debug
2053 * kernels, as this condition should not occur.
2054 * Return an error condition (1) if any flags found,
2055 * otherwise return 0.
2056 */
2057
2058int
2059xfs_check_nostate_extents(
4eea22f0
MK		 2060 xfs_ifork_t *ifp,
2061 xfs_extnum_t idx,
1da177e4
LT		 2062 xfs_extnum_t num)
2063{
4eea22f0 2064 for (; num > 0; num--, idx++) {
a6f64d4a 2065 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
1da177e4
LT		 2066 if ((ep->l0 >>
2067 (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
2068 ASSERT(0);
2069 return 1;
2070 }
2071 }
2072 return 0;
2073}
561f7d17
CH		 2074
2075
2076STATIC struct xfs_btree_cur *
2077xfs_bmbt_dup_cursor(
2078 struct xfs_btree_cur *cur)
2079{
2080 struct xfs_btree_cur *new;
2081
2082 new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
2083 cur->bc_private.b.ip, cur->bc_private.b.whichfork);
2084
2085 /*
2086 * Copy the firstblock, flist, and flags values,
2087 * since init cursor doesn't get them.
2088 */
2089 new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
2090 new->bc_private.b.flist = cur->bc_private.b.flist;
2091 new->bc_private.b.flags = cur->bc_private.b.flags;
2092
2093 return new;
2094}
2095
ce5e42db
CH		 2096STATIC int
2097xfs_bmbt_get_maxrecs(
2098 struct xfs_btree_cur *cur,
2099 int level)
2100{
2101 return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
2102}
2103
fe033cc8
CH		 2104STATIC void
2105xfs_bmbt_init_key_from_rec(
2106 union xfs_btree_key *key,
2107 union xfs_btree_rec *rec)
2108{
2109 key->bmbt.br_startoff =
2110 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
2111}
2112
2113STATIC void
2114xfs_bmbt_init_ptr_from_cur(
2115 struct xfs_btree_cur *cur,
2116 union xfs_btree_ptr *ptr)
2117{
2118 ptr->l = 0;
2119}
2120
2121STATIC __int64_t
2122xfs_bmbt_key_diff(
2123 struct xfs_btree_cur *cur,
2124 union xfs_btree_key *key)
2125{
2126 return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
2127 cur->bc_rec.b.br_startoff;
2128}
2129
8c4ed633
CH		 2130#ifdef XFS_BTREE_TRACE
2131ktrace_t *xfs_bmbt_trace_buf;
2132
2133STATIC void
2134xfs_bmbt_trace_enter(
2135 struct xfs_btree_cur *cur,
2136 const char *func,
2137 char *s,
2138 int type,
2139 int line,
2140 __psunsigned_t a0,
2141 __psunsigned_t a1,
2142 __psunsigned_t a2,
2143 __psunsigned_t a3,
2144 __psunsigned_t a4,
2145 __psunsigned_t a5,
2146 __psunsigned_t a6,
2147 __psunsigned_t a7,
2148 __psunsigned_t a8,
2149 __psunsigned_t a9,
2150 __psunsigned_t a10)
2151{
2152 struct xfs_inode *ip = cur->bc_private.b.ip;
2153 int whichfork = cur->bc_private.b.whichfork;
2154
2155 ktrace_enter(xfs_bmbt_trace_buf,
2156 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
2157 (void *)func, (void *)s, (void *)ip, (void *)cur,
2158 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
2159 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
2160 (void *)a8, (void *)a9, (void *)a10);
2161 ktrace_enter(ip->i_btrace,
2162 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
2163 (void *)func, (void *)s, (void *)ip, (void *)cur,
2164 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
2165 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
2166 (void *)a8, (void *)a9, (void *)a10);
2167}
2168
2169STATIC void
2170xfs_bmbt_trace_cursor(
2171 struct xfs_btree_cur *cur,
2172 __uint32_t *s0,
2173 __uint64_t *l0,
2174 __uint64_t *l1)
2175{
2176 struct xfs_bmbt_rec_host r;
2177
2178 xfs_bmbt_set_all(&r, &cur->bc_rec.b);
2179
2180 *s0 = (cur->bc_nlevels << 24) |
2181 (cur->bc_private.b.flags << 16) |
2182 cur->bc_private.b.allocated;
2183 *l0 = r.l0;
2184 *l1 = r.l1;
2185}
2186
2187STATIC void
2188xfs_bmbt_trace_key(
2189 struct xfs_btree_cur *cur,
2190 union xfs_btree_key *key,
2191 __uint64_t *l0,
2192 __uint64_t *l1)
2193{
2194 *l0 = be64_to_cpu(key->bmbt.br_startoff);
2195 *l1 = 0;
2196}
2197
2198STATIC void
2199xfs_bmbt_trace_record(
2200 struct xfs_btree_cur *cur,
2201 union xfs_btree_rec *rec,
2202 __uint64_t *l0,
2203 __uint64_t *l1,
2204 __uint64_t *l2)
2205{
2206 struct xfs_bmbt_irec irec;
2207
2208 xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
2209 *l0 = irec.br_startoff;
2210 *l1 = irec.br_startblock;
2211 *l2 = irec.br_blockcount;
2212}
2213#endif /* XFS_BTREE_TRACE */
2214
561f7d17 2215static const struct xfs_btree_ops xfs_bmbt_ops = {
65f1eaea
CH		 2216 .rec_len = sizeof(xfs_bmbt_rec_t),
2217 .key_len = sizeof(xfs_bmbt_key_t),
2218
561f7d17 2219 .dup_cursor = xfs_bmbt_dup_cursor,
ce5e42db 2220 .get_maxrecs = xfs_bmbt_get_maxrecs,
fe033cc8
CH		 2221 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
2222 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur,
2223 .key_diff = xfs_bmbt_key_diff,
8c4ed633
CH		 2224
2225#ifdef XFS_BTREE_TRACE
2226 .trace_enter = xfs_bmbt_trace_enter,
2227 .trace_cursor = xfs_bmbt_trace_cursor,
2228 .trace_key = xfs_bmbt_trace_key,
2229 .trace_record = xfs_bmbt_trace_record,
2230#endif
561f7d17
CH		 2231};
2232
2233/*
2234 * Allocate a new bmap btree cursor.
2235 */
2236struct xfs_btree_cur * /* new bmap btree cursor */
2237xfs_bmbt_init_cursor(
2238 struct xfs_mount *mp, /* file system mount point */
2239 struct xfs_trans *tp, /* transaction pointer */
2240 struct xfs_inode *ip, /* inode owning the btree */
2241 int whichfork) /* data or attr fork */
2242{
2243 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork);
2244 struct xfs_btree_cur *cur;
2245
2246 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
2247
2248 cur->bc_tp = tp;
2249 cur->bc_mp = mp;
2250 cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
2251 cur->bc_btnum = XFS_BTNUM_BMAP;
2252 cur->bc_blocklog = mp->m_sb.sb_blocklog;
2253
2254 cur->bc_ops = &xfs_bmbt_ops;
e99ab90d 2255 cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
561f7d17
CH		 2256
2257 cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
2258 cur->bc_private.b.ip = ip;
2259 cur->bc_private.b.firstblock = NULLFSBLOCK;
2260 cur->bc_private.b.flist = NULL;
2261 cur->bc_private.b.allocated = 0;
2262 cur->bc_private.b.flags = 0;
2263 cur->bc_private.b.whichfork = whichfork;
2264
2265 return cur;
2266}
Linux kernel - Deliverables
This page took 0.482449 seconds and 5 git commands to generate.