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