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