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