]> git.proxmox.com Git - mirror_ubuntu-zesty-kernel.git/blame - fs/xfs/xfs_bmap_btree.c
projects / mirror_ubuntu-zesty-kernel.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
[XFS] implement generic xfs_btree_insert/insrec
[mirror_ubuntu-zesty-kernel.git] / fs / xfs / xfs_bmap_btree.c
CommitLineData
1da177e4 1/*
7b718769
NS		 2 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
1da177e4 4 *
7b718769
NS		 5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
1da177e4
LT		 7 * published by the Free Software Foundation.
8 *
7b718769
NS		 9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
1da177e4 13 *
7b718769
NS		 14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
1da177e4 17 */
1da177e4 18#include "xfs.h"
a844f451 19#include "xfs_fs.h"
1da177e4 20#include "xfs_types.h"
a844f451 21#include "xfs_bit.h"
1da177e4 22#include "xfs_log.h"
a844f451 23#include "xfs_inum.h"
1da177e4
LT		 24#include "xfs_trans.h"
25#include "xfs_sb.h"
26#include "xfs_ag.h"
1da177e4
LT		 27#include "xfs_dir2.h"
28#include "xfs_dmapi.h"
29#include "xfs_mount.h"
1da177e4 30#include "xfs_bmap_btree.h"
a844f451 31#include "xfs_alloc_btree.h"
1da177e4 32#include "xfs_ialloc_btree.h"
1da177e4 33#include "xfs_dir2_sf.h"
a844f451 34#include "xfs_attr_sf.h"
1da177e4 35#include "xfs_dinode.h"
1da177e4 36#include "xfs_inode.h"
a844f451 37#include "xfs_inode_item.h"
1da177e4 38#include "xfs_alloc.h"
a844f451 39#include "xfs_btree.h"
8c4ed633 40#include "xfs_btree_trace.h"
a844f451
NS		 41#include "xfs_ialloc.h"
42#include "xfs_itable.h"
1da177e4
LT		 43#include "xfs_bmap.h"
44#include "xfs_error.h"
45#include "xfs_quota.h"
46
1da177e4
LT		 47/*
48 * Prototypes for internal btree functions.
49 */
50
51
52STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
53STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
54STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
1da177e4 55
1da177e4 56#undef EXIT
1da177e4 57
8c4ed633
CH		 58#define ENTRY XBT_ENTRY
59#define ERROR XBT_ERROR
60#define EXIT XBT_EXIT
1da177e4 61
1da177e4 62/*
8c4ed633
CH		 63 * Keep the XFS_BMBT_TRACE_ names around for now until all code using them
64 * is converted to be generic and thus switches to the XFS_BTREE_TRACE_ names.
1da177e4 65 */
8c4ed633
CH		 66#define XFS_BMBT_TRACE_ARGBI(c,b,i) \
67 XFS_BTREE_TRACE_ARGBI(c,b,i)
68#define XFS_BMBT_TRACE_ARGBII(c,b,i,j) \
69 XFS_BTREE_TRACE_ARGBII(c,b,i,j)
70#define XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j) \
71 XFS_BTREE_TRACE_ARGFFFI(c,o,b,i,j)
72#define XFS_BMBT_TRACE_ARGI(c,i) \
73 XFS_BTREE_TRACE_ARGI(c,i)
74#define XFS_BMBT_TRACE_ARGIFK(c,i,f,s) \
75 XFS_BTREE_TRACE_ARGIPK(c,i,(union xfs_btree_ptr)f,s)
76#define XFS_BMBT_TRACE_ARGIFR(c,i,f,r) \
77 XFS_BTREE_TRACE_ARGIPR(c,i, \
78 (union xfs_btree_ptr)f, (union xfs_btree_rec *)r)
79#define XFS_BMBT_TRACE_ARGIK(c,i,k) \
80 XFS_BTREE_TRACE_ARGIK(c,i,(union xfs_btree_key *)k)
81#define XFS_BMBT_TRACE_CURSOR(c,s) \
82 XFS_BTREE_TRACE_CURSOR(c,s)
1da177e4
LT		 83
84
85/*
86 * Internal functions.
87 */
88
89/*
90 * Delete record pointed to by cur/level.
91 */
92STATIC int /* error */
93xfs_bmbt_delrec(
94 xfs_btree_cur_t *cur,
95 int level,
96 int *stat) /* success/failure */
97{
98 xfs_bmbt_block_t *block; /* bmap btree block */
99 xfs_fsblock_t bno; /* fs-relative block number */
100 xfs_buf_t *bp; /* buffer for block */
101 int error; /* error return value */
1da177e4
LT		 102 int i; /* loop counter */
103 int j; /* temp state */
104 xfs_bmbt_key_t key; /* bmap btree key */
105 xfs_bmbt_key_t *kp=NULL; /* pointer to bmap btree key */
106 xfs_fsblock_t lbno; /* left sibling block number */
107 xfs_buf_t *lbp; /* left buffer pointer */
108 xfs_bmbt_block_t *left; /* left btree block */
109 xfs_bmbt_key_t *lkp; /* left btree key */
110 xfs_bmbt_ptr_t *lpp; /* left address pointer */
111 int lrecs=0; /* left record count */
112 xfs_bmbt_rec_t *lrp; /* left record pointer */
113 xfs_mount_t *mp; /* file system mount point */
114 xfs_bmbt_ptr_t *pp; /* pointer to bmap block addr */
115 int ptr; /* key/record index */
116 xfs_fsblock_t rbno; /* right sibling block number */
117 xfs_buf_t *rbp; /* right buffer pointer */
118 xfs_bmbt_block_t *right; /* right btree block */
119 xfs_bmbt_key_t *rkp; /* right btree key */
120 xfs_bmbt_rec_t *rp; /* pointer to bmap btree rec */
121 xfs_bmbt_ptr_t *rpp; /* right address pointer */
122 xfs_bmbt_block_t *rrblock; /* right-right btree block */
123 xfs_buf_t *rrbp; /* right-right buffer pointer */
124 int rrecs=0; /* right record count */
125 xfs_bmbt_rec_t *rrp; /* right record pointer */
126 xfs_btree_cur_t *tcur; /* temporary btree cursor */
127 int numrecs; /* temporary numrec count */
128 int numlrecs, numrrecs;
129
130 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
131 XFS_BMBT_TRACE_ARGI(cur, level);
132 ptr = cur->bc_ptrs[level];
1121b219 133 tcur = NULL;
1da177e4
LT		 134 if (ptr == 0) {
135 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
136 *stat = 0;
137 return 0;
138 }
139 block = xfs_bmbt_get_block(cur, level, &bp);
16259e7d 140 numrecs = be16_to_cpu(block->bb_numrecs);
1da177e4
LT		 141#ifdef DEBUG
142 if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
143 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
144 goto error0;
145 }
146#endif
147 if (ptr > numrecs) {
148 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
149 *stat = 0;
150 return 0;
151 }
152 XFS_STATS_INC(xs_bmbt_delrec);
153 if (level > 0) {
154 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
155 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
156#ifdef DEBUG
157 for (i = ptr; i < numrecs; i++) {
b113bcb8 158 if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
1da177e4
LT		 159 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
160 goto error0;
161 }
162 }
163#endif
164 if (ptr < numrecs) {
165 memmove(&kp[ptr - 1], &kp[ptr],
166 (numrecs - ptr) * sizeof(*kp));
d580ef6e 167 memmove(&pp[ptr - 1], &pp[ptr],
1da177e4
LT		 168 (numrecs - ptr) * sizeof(*pp));
169 xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
170 xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
171 }
172 } else {
173 rp = XFS_BMAP_REC_IADDR(block, 1, cur);
174 if (ptr < numrecs) {
175 memmove(&rp[ptr - 1], &rp[ptr],
176 (numrecs - ptr) * sizeof(*rp));
177 xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
178 }
179 if (ptr == 1) {
8801bb99
CH		 180 key.br_startoff =
181 cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
1da177e4
LT		 182 kp = &key;
183 }
184 }
185 numrecs--;
16259e7d 186 block->bb_numrecs = cpu_to_be16(numrecs);
1da177e4
LT		 187 xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
188 /*
189 * We're at the root level.
190 * First, shrink the root block in-memory.
191 * Try to get rid of the next level down.
192 * If we can't then there's nothing left to do.
193 */
194 if (level == cur->bc_nlevels - 1) {
195 xfs_iroot_realloc(cur->bc_private.b.ip, -1,
196 cur->bc_private.b.whichfork);
197 if ((error = xfs_bmbt_killroot(cur))) {
198 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
199 goto error0;
200 }
8df4da4a 201 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
1da177e4
LT		 202 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
203 goto error0;
204 }
205 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
206 *stat = 1;
207 return 0;
208 }
38bb7423 209 if (ptr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)kp, level + 1))) {
1da177e4
LT		 210 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
211 goto error0;
212 }
213 if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
8df4da4a 214 if (level > 0 && (error = xfs_btree_decrement(cur, level, &j))) {
1da177e4
LT		 215 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
216 goto error0;
217 }
218 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
219 *stat = 1;
220 return 0;
221 }
16259e7d
CH		 222 rbno = be64_to_cpu(block->bb_rightsib);
223 lbno = be64_to_cpu(block->bb_leftsib);
1da177e4
LT		 224 /*
225 * One child of root, need to get a chance to copy its contents
226 * into the root and delete it. Can't go up to next level,
227 * there's nothing to delete there.
228 */
229 if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
230 level == cur->bc_nlevels - 2) {
231 if ((error = xfs_bmbt_killroot(cur))) {
232 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
233 goto error0;
234 }
8df4da4a 235 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
1da177e4
LT		 236 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
237 goto error0;
238 }
239 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
240 *stat = 1;
241 return 0;
242 }
243 ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
244 if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
245 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
246 goto error0;
247 }
248 bno = NULLFSBLOCK;
249 if (rbno != NULLFSBLOCK) {
250 i = xfs_btree_lastrec(tcur, level);
251 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
637aa50f 252 if ((error = xfs_btree_increment(tcur, level, &i))) {
1da177e4
LT		 253 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
254 goto error0;
255 }
256 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
257 i = xfs_btree_lastrec(tcur, level);
258 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
259 rbp = tcur->bc_bufs[level];
260 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
261#ifdef DEBUG
262 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
263 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
264 goto error0;
265 }
266#endif
16259e7d
CH		 267 bno = be64_to_cpu(right->bb_leftsib);
268 if (be16_to_cpu(right->bb_numrecs) - 1 >=
1da177e4 269 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
687b890a 270 if ((error = xfs_btree_lshift(tcur, level, &i))) {
1da177e4
LT		 271 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
272 goto error0;
273 }
274 if (i) {
16259e7d 275 ASSERT(be16_to_cpu(block->bb_numrecs) >=
1da177e4
LT		 276 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
277 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
278 tcur = NULL;
279 if (level > 0) {
8df4da4a 280 if ((error = xfs_btree_decrement(cur,
1da177e4
LT		 281 level, &i))) {
282 XFS_BMBT_TRACE_CURSOR(cur,
283 ERROR);
284 goto error0;
285 }
286 }
287 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
288 *stat = 1;
289 return 0;
290 }
291 }
16259e7d 292 rrecs = be16_to_cpu(right->bb_numrecs);
1da177e4
LT		 293 if (lbno != NULLFSBLOCK) {
294 i = xfs_btree_firstrec(tcur, level);
295 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
8df4da4a 296 if ((error = xfs_btree_decrement(tcur, level, &i))) {
1da177e4
LT		 297 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
298 goto error0;
299 }
300 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
301 }
302 }
303 if (lbno != NULLFSBLOCK) {
304 i = xfs_btree_firstrec(tcur, level);
305 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
306 /*
307 * decrement to last in block
308 */
8df4da4a 309 if ((error = xfs_btree_decrement(tcur, level, &i))) {
1da177e4
LT		 310 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
311 goto error0;
312 }
313 i = xfs_btree_firstrec(tcur, level);
314 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
315 lbp = tcur->bc_bufs[level];
316 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
317#ifdef DEBUG
318 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
319 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
320 goto error0;
321 }
322#endif
16259e7d
CH		 323 bno = be64_to_cpu(left->bb_rightsib);
324 if (be16_to_cpu(left->bb_numrecs) - 1 >=
1da177e4 325 XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
9eaead51 326 if ((error = xfs_btree_rshift(tcur, level, &i))) {
1da177e4
LT		 327 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
328 goto error0;
329 }
330 if (i) {
16259e7d 331 ASSERT(be16_to_cpu(block->bb_numrecs) >=
1da177e4
LT		 332 XFS_BMAP_BLOCK_IMINRECS(level, tcur));
333 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
334 tcur = NULL;
335 if (level == 0)
336 cur->bc_ptrs[0]++;
337 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
338 *stat = 1;
339 return 0;
340 }
341 }
16259e7d 342 lrecs = be16_to_cpu(left->bb_numrecs);
1da177e4
LT		 343 }
344 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
345 tcur = NULL;
346 mp = cur->bc_mp;
347 ASSERT(bno != NULLFSBLOCK);
348 if (lbno != NULLFSBLOCK &&
16259e7d 349 lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
1da177e4
LT		 350 rbno = bno;
351 right = block;
352 rbp = bp;
353 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
354 XFS_BMAP_BTREE_REF))) {
355 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
356 goto error0;
357 }
358 left = XFS_BUF_TO_BMBT_BLOCK(lbp);
359 if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
360 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
361 goto error0;
362 }
363 } else if (rbno != NULLFSBLOCK &&
16259e7d 364 rrecs + be16_to_cpu(block->bb_numrecs) <=
1da177e4
LT		 365 XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
366 lbno = bno;
367 left = block;
368 lbp = bp;
369 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
370 XFS_BMAP_BTREE_REF))) {
371 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
372 goto error0;
373 }
374 right = XFS_BUF_TO_BMBT_BLOCK(rbp);
375 if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
376 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
377 goto error0;
378 }
16259e7d 379 lrecs = be16_to_cpu(left->bb_numrecs);
1da177e4 380 } else {
8df4da4a 381 if (level > 0 && (error = xfs_btree_decrement(cur, level, &i))) {
1da177e4
LT		 382 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
383 goto error0;
384 }
385 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
386 *stat = 1;
387 return 0;
388 }
16259e7d
CH		 389 numlrecs = be16_to_cpu(left->bb_numrecs);
390 numrrecs = be16_to_cpu(right->bb_numrecs);
1da177e4
LT		 391 if (level > 0) {
392 lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
393 lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
394 rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
395 rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
396#ifdef DEBUG
397 for (i = 0; i < numrrecs; i++) {
b113bcb8 398 if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
1da177e4
LT		 399 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
400 goto error0;
401 }
402 }
403#endif
404 memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
405 memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
406 xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
407 xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
408 } else {
409 lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
410 rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
411 memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
412 xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
413 }
413d57c9 414 be16_add_cpu(&left->bb_numrecs, numrrecs);
16259e7d 415 left->bb_rightsib = right->bb_rightsib;
1da177e4 416 xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
16259e7d 417 if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
1da177e4 418 if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
16259e7d 419 be64_to_cpu(left->bb_rightsib),
1da177e4
LT		 420 0, &rrbp, XFS_BMAP_BTREE_REF))) {
421 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
422 goto error0;
423 }
424 rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
425 if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
426 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
427 goto error0;
428 }
16259e7d 429 rrblock->bb_leftsib = cpu_to_be64(lbno);
1da177e4
LT		 430 xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
431 }
432 xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
433 cur->bc_private.b.flist, mp);
434 cur->bc_private.b.ip->i_d.di_nblocks--;
435 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
436 XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
437 XFS_TRANS_DQ_BCOUNT, -1L);
438 xfs_trans_binval(cur->bc_tp, rbp);
439 if (bp != lbp) {
440 cur->bc_bufs[level] = lbp;
441 cur->bc_ptrs[level] += lrecs;
442 cur->bc_ra[level] = 0;
637aa50f 443 } else if ((error = xfs_btree_increment(cur, level + 1, &i))) {
1da177e4
LT		 444 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
445 goto error0;
446 }
447 if (level > 0)
448 cur->bc_ptrs[level]--;
449 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
450 *stat = 2;
451 return 0;
452
453error0:
454 if (tcur)
455 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
456 return error;
457}
458
1da177e4
LT		 459STATIC int
460xfs_bmbt_killroot(
461 xfs_btree_cur_t *cur)
462{
463 xfs_bmbt_block_t *block;
464 xfs_bmbt_block_t *cblock;
465 xfs_buf_t *cbp;
466 xfs_bmbt_key_t *ckp;
467 xfs_bmbt_ptr_t *cpp;
468#ifdef DEBUG
469 int error;
1da177e4
LT		 470#endif
471 int i;
472 xfs_bmbt_key_t *kp;
473 xfs_inode_t *ip;
474 xfs_ifork_t *ifp;
475 int level;
476 xfs_bmbt_ptr_t *pp;
477
478 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
479 level = cur->bc_nlevels - 1;
480 ASSERT(level >= 1);
481 /*
482 * Don't deal with the root block needs to be a leaf case.
483 * We're just going to turn the thing back into extents anyway.
484 */
485 if (level == 1) {
486 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
487 return 0;
488 }
489 block = xfs_bmbt_get_block(cur, level, &cbp);
490 /*
491 * Give up if the root has multiple children.
492 */
16259e7d 493 if (be16_to_cpu(block->bb_numrecs) != 1) {
1da177e4
LT		 494 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
495 return 0;
496 }
497 /*
498 * Only do this if the next level will fit.
499 * Then the data must be copied up to the inode,
500 * instead of freeing the root you free the next level.
501 */
502 cbp = cur->bc_bufs[level - 1];
503 cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
16259e7d 504 if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
1da177e4
LT		 505 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
506 return 0;
507 }
16259e7d
CH		 508 ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
509 ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
1da177e4
LT		 510 ip = cur->bc_private.b.ip;
511 ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
512 ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
513 XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
16259e7d 514 i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
1da177e4
LT		 515 if (i) {
516 xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
517 block = ifp->if_broot;
518 }
413d57c9 519 be16_add_cpu(&block->bb_numrecs, i);
16259e7d 520 ASSERT(block->bb_numrecs == cblock->bb_numrecs);
1da177e4
LT		 521 kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
522 ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
16259e7d 523 memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
1da177e4
LT		 524 pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
525 cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
526#ifdef DEBUG
16259e7d 527 for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
b113bcb8 528 if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
1da177e4
LT		 529 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
530 return error;
531 }
532 }
533#endif
16259e7d 534 memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
1da177e4
LT		 535 xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
536 cur->bc_private.b.flist, cur->bc_mp);
537 ip->i_d.di_nblocks--;
538 XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
539 XFS_TRANS_DQ_BCOUNT, -1L);
540 xfs_trans_binval(cur->bc_tp, cbp);
541 cur->bc_bufs[level - 1] = NULL;
413d57c9 542 be16_add_cpu(&block->bb_level, -1);
1da177e4
LT		 543 xfs_trans_log_inode(cur->bc_tp, ip,
544 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
545 cur->bc_nlevels--;
546 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
547 return 0;
548}
549
550/*
551 * Log key values from the btree block.
552 */
553STATIC void
554xfs_bmbt_log_keys(
555 xfs_btree_cur_t *cur,
556 xfs_buf_t *bp,
557 int kfirst,
558 int klast)
559{
1da177e4
LT		 560 xfs_trans_t *tp;
561
562 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
563 XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
564 tp = cur->bc_tp;
565 if (bp) {
566 xfs_bmbt_block_t *block;
567 int first;
568 xfs_bmbt_key_t *kp;
569 int last;
570
571 block = XFS_BUF_TO_BMBT_BLOCK(bp);
572 kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
573 first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
574 last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
575 xfs_trans_log_buf(tp, bp, first, last);
576 } else {
577 xfs_inode_t *ip;
578
579 ip = cur->bc_private.b.ip;
580 xfs_trans_log_inode(tp, ip,
581 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
582 }
583 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
584}
585
586/*
587 * Log pointer values from the btree block.
588 */
589STATIC void
590xfs_bmbt_log_ptrs(
591 xfs_btree_cur_t *cur,
592 xfs_buf_t *bp,
593 int pfirst,
594 int plast)
595{
1da177e4
LT		 596 xfs_trans_t *tp;
597
598 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
599 XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
600 tp = cur->bc_tp;
601 if (bp) {
602 xfs_bmbt_block_t *block;
603 int first;
604 int last;
605 xfs_bmbt_ptr_t *pp;
606
607 block = XFS_BUF_TO_BMBT_BLOCK(bp);
608 pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
609 first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
610 last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
611 xfs_trans_log_buf(tp, bp, first, last);
612 } else {
613 xfs_inode_t *ip;
614
615 ip = cur->bc_private.b.ip;
616 xfs_trans_log_inode(tp, ip,
617 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
618 }
619 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
620}
621
1da177e4
LT		 622/*
623 * Determine the extent state.
624 */
625/* ARGSUSED */
626STATIC xfs_exntst_t
627xfs_extent_state(
628 xfs_filblks_t blks,
629 int extent_flag)
630{
631 if (extent_flag) {
632 ASSERT(blks != 0); /* saved for DMIG */
633 return XFS_EXT_UNWRITTEN;
634 }
635 return XFS_EXT_NORM;
636}
637
1da177e4
LT		 638/*
639 * Convert on-disk form of btree root to in-memory form.
640 */
641void
642xfs_bmdr_to_bmbt(
643 xfs_bmdr_block_t *dblock,
644 int dblocklen,
645 xfs_bmbt_block_t *rblock,
646 int rblocklen)
647{
648 int dmxr;
649 xfs_bmbt_key_t *fkp;
576039cf 650 __be64 *fpp;
1da177e4 651 xfs_bmbt_key_t *tkp;
576039cf 652 __be64 *tpp;
1da177e4 653
16259e7d
CH		 654 rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
655 rblock->bb_level = dblock->bb_level;
656 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
657 rblock->bb_numrecs = dblock->bb_numrecs;
658 rblock->bb_leftsib = cpu_to_be64(NULLDFSBNO);
659 rblock->bb_rightsib = cpu_to_be64(NULLDFSBNO);
1da177e4 660 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
2c36dded 661 fkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1da177e4 662 tkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2c36dded 663 fpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
1da177e4 664 tpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
16259e7d 665 dmxr = be16_to_cpu(dblock->bb_numrecs);
1da177e4 666 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
576039cf 667 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1da177e4
LT		 668}
669
1da177e4
LT		 670/*
671 * Delete the record pointed to by cur.
672 */
673int /* error */
674xfs_bmbt_delete(
675 xfs_btree_cur_t *cur,
676 int *stat) /* success/failure */
677{
678 int error; /* error return value */
1da177e4
LT		 679 int i;
680 int level;
681
682 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
683 for (level = 0, i = 2; i == 2; level++) {
684 if ((error = xfs_bmbt_delrec(cur, level, &i))) {
685 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
686 return error;
687 }
688 }
689 if (i == 0) {
690 for (level = 1; level < cur->bc_nlevels; level++) {
691 if (cur->bc_ptrs[level] == 0) {
8df4da4a 692 if ((error = xfs_btree_decrement(cur, level,
1da177e4
LT		 693 &i))) {
694 XFS_BMBT_TRACE_CURSOR(cur, ERROR);
695 return error;
696 }
697 break;
698 }
699 }
700 }
701 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
702 *stat = i;
703 return 0;
704}
705
706/*
707 * Convert a compressed bmap extent record to an uncompressed form.
708 * This code must be in sync with the routines xfs_bmbt_get_startoff,
709 * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
710 */
711
7989cb8e 712STATIC_INLINE void
1da177e4
LT		 713__xfs_bmbt_get_all(
714 __uint64_t l0,
715 __uint64_t l1,
716 xfs_bmbt_irec_t *s)
717{
718 int ext_flag;
719 xfs_exntst_t st;
720
721 ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
722 s->br_startoff = ((xfs_fileoff_t)l0 &
723 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
724#if XFS_BIG_BLKNOS
725 s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
726 (((xfs_fsblock_t)l1) >> 21);
727#else
728#ifdef DEBUG
729 {
730 xfs_dfsbno_t b;
731
732 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
733 (((xfs_dfsbno_t)l1) >> 21);
734 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
735 s->br_startblock = (xfs_fsblock_t)b;
736 }
737#else /* !DEBUG */
738 s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
739#endif /* DEBUG */
740#endif /* XFS_BIG_BLKNOS */
741 s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
742 /* This is xfs_extent_state() in-line */
743 if (ext_flag) {
744 ASSERT(s->br_blockcount != 0); /* saved for DMIG */
745 st = XFS_EXT_UNWRITTEN;
746 } else
747 st = XFS_EXT_NORM;
748 s->br_state = st;
749}
750
751void
752xfs_bmbt_get_all(
a6f64d4a 753 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 754 xfs_bmbt_irec_t *s)
755{
756 __xfs_bmbt_get_all(r->l0, r->l1, s);
757}
758
759/*
760 * Get the block pointer for the given level of the cursor.
761 * Fill in the buffer pointer, if applicable.
762 */
763xfs_bmbt_block_t *
764xfs_bmbt_get_block(
765 xfs_btree_cur_t *cur,
766 int level,
767 xfs_buf_t **bpp)
768{
769 xfs_ifork_t *ifp;
770 xfs_bmbt_block_t *rval;
771
772 if (level < cur->bc_nlevels - 1) {
773 *bpp = cur->bc_bufs[level];
774 rval = XFS_BUF_TO_BMBT_BLOCK(*bpp);
775 } else {
776 *bpp = NULL;
777 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
778 cur->bc_private.b.whichfork);
779 rval = ifp->if_broot;
780 }
781 return rval;
782}
783
784/*
785 * Extract the blockcount field from an in memory bmap extent record.
786 */
787xfs_filblks_t
788xfs_bmbt_get_blockcount(
a6f64d4a 789 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 790{
791 return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
792}
793
794/*
795 * Extract the startblock field from an in memory bmap extent record.
796 */
797xfs_fsblock_t
798xfs_bmbt_get_startblock(
a6f64d4a 799 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 800{
801#if XFS_BIG_BLKNOS
802 return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
803 (((xfs_fsblock_t)r->l1) >> 21);
804#else
805#ifdef DEBUG
806 xfs_dfsbno_t b;
807
808 b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
809 (((xfs_dfsbno_t)r->l1) >> 21);
810 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
811 return (xfs_fsblock_t)b;
812#else /* !DEBUG */
813 return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
814#endif /* DEBUG */
815#endif /* XFS_BIG_BLKNOS */
816}
817
818/*
819 * Extract the startoff field from an in memory bmap extent record.
820 */
821xfs_fileoff_t
822xfs_bmbt_get_startoff(
a6f64d4a 823 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 824{
825 return ((xfs_fileoff_t)r->l0 &
826 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
827}
828
829xfs_exntst_t
830xfs_bmbt_get_state(
a6f64d4a 831 xfs_bmbt_rec_host_t *r)
1da177e4
LT		 832{
833 int ext_flag;
834
835 ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
836 return xfs_extent_state(xfs_bmbt_get_blockcount(r),
837 ext_flag);
838}
839
1da177e4
LT		 840/* Endian flipping versions of the bmbt extraction functions */
841void
842xfs_bmbt_disk_get_all(
843 xfs_bmbt_rec_t *r,
844 xfs_bmbt_irec_t *s)
845{
cd8b0a97 846 __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
1da177e4
LT		 847}
848
849/*
850 * Extract the blockcount field from an on disk bmap extent record.
851 */
852xfs_filblks_t
853xfs_bmbt_disk_get_blockcount(
854 xfs_bmbt_rec_t *r)
855{
cd8b0a97 856 return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
1da177e4
LT		 857}
858
1da177e4
LT		 859/*
860 * Extract the startoff field from a disk format bmap extent record.
861 */
862xfs_fileoff_t
863xfs_bmbt_disk_get_startoff(
864 xfs_bmbt_rec_t *r)
865{
cd8b0a97 866 return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
1da177e4
LT		 867 XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
868}
1da177e4 869
1da177e4
LT		 870/*
871 * Log fields from the btree block header.
872 */
873void
874xfs_bmbt_log_block(
875 xfs_btree_cur_t *cur,
876 xfs_buf_t *bp,
877 int fields)
878{
879 int first;
1da177e4
LT		 880 int last;
881 xfs_trans_t *tp;
882 static const short offsets[] = {
883 offsetof(xfs_bmbt_block_t, bb_magic),
884 offsetof(xfs_bmbt_block_t, bb_level),
885 offsetof(xfs_bmbt_block_t, bb_numrecs),
886 offsetof(xfs_bmbt_block_t, bb_leftsib),
887 offsetof(xfs_bmbt_block_t, bb_rightsib),
888 sizeof(xfs_bmbt_block_t)
889 };
890
891 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
892 XFS_BMBT_TRACE_ARGBI(cur, bp, fields);
893 tp = cur->bc_tp;
894 if (bp) {
895 xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first,
896 &last);
897 xfs_trans_log_buf(tp, bp, first, last);
898 } else
899 xfs_trans_log_inode(tp, cur->bc_private.b.ip,
900 XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
901 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
902}
903
904/*
905 * Log record values from the btree block.
906 */
907void
908xfs_bmbt_log_recs(
909 xfs_btree_cur_t *cur,
910 xfs_buf_t *bp,
911 int rfirst,
912 int rlast)
913{
914 xfs_bmbt_block_t *block;
915 int first;
1da177e4
LT		 916 int last;
917 xfs_bmbt_rec_t *rp;
918 xfs_trans_t *tp;
919
920 XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
921 XFS_BMBT_TRACE_ARGBII(cur, bp, rfirst, rlast);
922 ASSERT(bp);
923 tp = cur->bc_tp;
924 block = XFS_BUF_TO_BMBT_BLOCK(bp);
925 rp = XFS_BMAP_REC_DADDR(block, 1, cur);
926 first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
927 last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
928 xfs_trans_log_buf(tp, bp, first, last);
929 XFS_BMBT_TRACE_CURSOR(cur, EXIT);
930}
931
1da177e4
LT		 932/*
933 * Set all the fields in a bmap extent record from the arguments.
934 */
935void
936xfs_bmbt_set_allf(
8cba4344
CH		 937 xfs_bmbt_rec_host_t *r,
938 xfs_fileoff_t startoff,
939 xfs_fsblock_t startblock,
940 xfs_filblks_t blockcount,
941 xfs_exntst_t state)
1da177e4 942{
8cba4344
CH		 943 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
944
945 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
946 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
947 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1da177e4 948
1da177e4 949#if XFS_BIG_BLKNOS
8cba4344
CH		 950 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
951
1da177e4 952 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344
CH		 953 ((xfs_bmbt_rec_base_t)startoff << 9) |
954 ((xfs_bmbt_rec_base_t)startblock >> 43);
955 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
956 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 957 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
958#else /* !XFS_BIG_BLKNOS */
ddc6d3b3 959 if (ISNULLSTARTBLOCK(startblock)) {
1da177e4 960 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344 961 ((xfs_bmbt_rec_base_t)startoff << 9) |
1da177e4
LT		 962 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
963 r->l1 = XFS_MASK64HI(11) |
8cba4344
CH		 964 ((xfs_bmbt_rec_base_t)startblock << 21) |
965 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 966 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
967 } else {
968 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
8cba4344
CH		 969 ((xfs_bmbt_rec_base_t)startoff << 9);
970 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
971 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 972 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
973 }
974#endif /* XFS_BIG_BLKNOS */
975}
976
1da177e4
LT		 977/*
978 * Set all the fields in a bmap extent record from the uncompressed form.
979 */
980void
8cba4344
CH		 981xfs_bmbt_set_all(
982 xfs_bmbt_rec_host_t *r,
983 xfs_bmbt_irec_t *s)
1da177e4 984{
8cba4344
CH		 985 xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
986 s->br_blockcount, s->br_state);
1da177e4
LT		 987}
988
8cba4344 989
1da177e4
LT		 990/*
991 * Set all the fields in a disk format bmap extent record from the arguments.
992 */
993void
994xfs_bmbt_disk_set_allf(
8cba4344
CH		 995 xfs_bmbt_rec_t *r,
996 xfs_fileoff_t startoff,
997 xfs_fsblock_t startblock,
998 xfs_filblks_t blockcount,
999 xfs_exntst_t state)
1da177e4 1000{
8cba4344
CH		 1001 int extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
1002
1003 ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
1004 ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
1005 ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
1da177e4 1006
1da177e4 1007#if XFS_BIG_BLKNOS
8cba4344
CH		 1008 ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
1009
cd8b0a97 1010 r->l0 = cpu_to_be64(
8cba4344
CH		 1011 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1012 ((xfs_bmbt_rec_base_t)startoff << 9) |
1013 ((xfs_bmbt_rec_base_t)startblock >> 43));
cd8b0a97 1014 r->l1 = cpu_to_be64(
8cba4344
CH		 1015 ((xfs_bmbt_rec_base_t)startblock << 21) |
1016 ((xfs_bmbt_rec_base_t)blockcount &
1017 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1da177e4 1018#else /* !XFS_BIG_BLKNOS */
ddc6d3b3 1019 if (ISNULLSTARTBLOCK(startblock)) {
cd8b0a97 1020 r->l0 = cpu_to_be64(
8cba4344
CH		 1021 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1022 ((xfs_bmbt_rec_base_t)startoff << 9) |
1023 (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
cd8b0a97 1024 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
8cba4344
CH		 1025 ((xfs_bmbt_rec_base_t)startblock << 21) |
1026 ((xfs_bmbt_rec_base_t)blockcount &
1da177e4
LT		 1027 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1028 } else {
cd8b0a97 1029 r->l0 = cpu_to_be64(
8cba4344
CH		 1030 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
1031 ((xfs_bmbt_rec_base_t)startoff << 9));
cd8b0a97 1032 r->l1 = cpu_to_be64(
8cba4344
CH		 1033 ((xfs_bmbt_rec_base_t)startblock << 21) |
1034 ((xfs_bmbt_rec_base_t)blockcount &
1035 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
1da177e4
LT		 1036 }
1037#endif /* XFS_BIG_BLKNOS */
1038}
8cba4344
CH		 1039
1040/*
1041 * Set all the fields in a bmap extent record from the uncompressed form.
1042 */
1043void
1044xfs_bmbt_disk_set_all(
1045 xfs_bmbt_rec_t *r,
1046 xfs_bmbt_irec_t *s)
1047{
1048 xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
1049 s->br_blockcount, s->br_state);
1050}
1da177e4
LT		 1051
1052/*
1053 * Set the blockcount field in a bmap extent record.
1054 */
1055void
1056xfs_bmbt_set_blockcount(
a6f64d4a 1057 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1058 xfs_filblks_t v)
1059{
1060 ASSERT((v & XFS_MASK64HI(43)) == 0);
1061 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
1062 (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
1063}
1064
1065/*
1066 * Set the startblock field in a bmap extent record.
1067 */
1068void
1069xfs_bmbt_set_startblock(
a6f64d4a 1070 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1071 xfs_fsblock_t v)
1072{
1073#if XFS_BIG_BLKNOS
1074 ASSERT((v & XFS_MASK64HI(12)) == 0);
1075 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
1076 (xfs_bmbt_rec_base_t)(v >> 43);
1077 r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
1078 (xfs_bmbt_rec_base_t)(v << 21);
1079#else /* !XFS_BIG_BLKNOS */
1080 if (ISNULLSTARTBLOCK(v)) {
1081 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1082 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
1083 ((xfs_bmbt_rec_base_t)v << 21) |
1084 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1085 } else {
1086 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
1087 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
1088 (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
1089 }
1090#endif /* XFS_BIG_BLKNOS */
1091}
1092
1093/*
1094 * Set the startoff field in a bmap extent record.
1095 */
1096void
1097xfs_bmbt_set_startoff(
a6f64d4a 1098 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1099 xfs_fileoff_t v)
1100{
1101 ASSERT((v & XFS_MASK64HI(9)) == 0);
1102 r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
1103 ((xfs_bmbt_rec_base_t)v << 9) |
1104 (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
1105}
1106
1107/*
1108 * Set the extent state field in a bmap extent record.
1109 */
1110void
1111xfs_bmbt_set_state(
a6f64d4a 1112 xfs_bmbt_rec_host_t *r,
1da177e4
LT		 1113 xfs_exntst_t v)
1114{
1115 ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
1116 if (v == XFS_EXT_NORM)
1117 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
1118 else
1119 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
1120}
1121
1122/*
1123 * Convert in-memory form of btree root to on-disk form.
1124 */
1125void
1126xfs_bmbt_to_bmdr(
1127 xfs_bmbt_block_t *rblock,
1128 int rblocklen,
1129 xfs_bmdr_block_t *dblock,
1130 int dblocklen)
1131{
1132 int dmxr;
1133 xfs_bmbt_key_t *fkp;
576039cf 1134 __be64 *fpp;
1da177e4 1135 xfs_bmbt_key_t *tkp;
576039cf 1136 __be64 *tpp;
1da177e4 1137
16259e7d
CH		 1138 ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
1139 ASSERT(be64_to_cpu(rblock->bb_leftsib) == NULLDFSBNO);
1140 ASSERT(be64_to_cpu(rblock->bb_rightsib) == NULLDFSBNO);
1141 ASSERT(be16_to_cpu(rblock->bb_level) > 0);
1142 dblock->bb_level = rblock->bb_level;
1143 dblock->bb_numrecs = rblock->bb_numrecs;
1da177e4
LT		 1144 dmxr = (int)XFS_BTREE_BLOCK_MAXRECS(dblocklen, xfs_bmdr, 0);
1145 fkp = XFS_BMAP_BROOT_KEY_ADDR(rblock, 1, rblocklen);
2c36dded 1146 tkp = XFS_BTREE_KEY_ADDR(xfs_bmdr, dblock, 1);
1da177e4 1147 fpp = XFS_BMAP_BROOT_PTR_ADDR(rblock, 1, rblocklen);
2c36dded 1148 tpp = XFS_BTREE_PTR_ADDR(xfs_bmdr, dblock, 1, dmxr);
16259e7d 1149 dmxr = be16_to_cpu(dblock->bb_numrecs);
1da177e4 1150 memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
576039cf 1151 memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
1da177e4
LT		 1152}
1153
1da177e4 1154/*
4eea22f0 1155 * Check extent records, which have just been read, for
1da177e4
LT		 1156 * any bit in the extent flag field. ASSERT on debug
1157 * kernels, as this condition should not occur.
1158 * Return an error condition (1) if any flags found,
1159 * otherwise return 0.
1160 */
1161
1162int
1163xfs_check_nostate_extents(
4eea22f0
MK		 1164 xfs_ifork_t *ifp,
1165 xfs_extnum_t idx,
1da177e4
LT		 1166 xfs_extnum_t num)
1167{
4eea22f0 1168 for (; num > 0; num--, idx++) {
a6f64d4a 1169 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
1da177e4
LT		 1170 if ((ep->l0 >>
1171 (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
1172 ASSERT(0);
1173 return 1;
1174 }
1175 }
1176 return 0;
1177}
561f7d17
CH		 1178
1179
1180STATIC struct xfs_btree_cur *
1181xfs_bmbt_dup_cursor(
1182 struct xfs_btree_cur *cur)
1183{
1184 struct xfs_btree_cur *new;
1185
1186 new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
1187 cur->bc_private.b.ip, cur->bc_private.b.whichfork);
1188
1189 /*
1190 * Copy the firstblock, flist, and flags values,
1191 * since init cursor doesn't get them.
1192 */
1193 new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
1194 new->bc_private.b.flist = cur->bc_private.b.flist;
1195 new->bc_private.b.flags = cur->bc_private.b.flags;
1196
1197 return new;
1198}
1199
4b22a571
CH		 1200STATIC void
1201xfs_bmbt_update_cursor(
1202 struct xfs_btree_cur *src,
1203 struct xfs_btree_cur *dst)
1204{
1205 ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
1206 (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
1207 ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
1208
1209 dst->bc_private.b.allocated += src->bc_private.b.allocated;
1210 dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
1211
1212 src->bc_private.b.allocated = 0;
1213}
1214
f5eb8e7c
CH		 1215STATIC int
1216xfs_bmbt_alloc_block(
1217 struct xfs_btree_cur *cur,
1218 union xfs_btree_ptr *start,
1219 union xfs_btree_ptr *new,
1220 int length,
1221 int *stat)
1222{
1223 xfs_alloc_arg_t args; /* block allocation args */
1224 int error; /* error return value */
1225
1226 memset(&args, 0, sizeof(args));
1227 args.tp = cur->bc_tp;
1228 args.mp = cur->bc_mp;
1229 args.fsbno = cur->bc_private.b.firstblock;
1230 args.firstblock = args.fsbno;
1231
1232 if (args.fsbno == NULLFSBLOCK) {
1233 args.fsbno = be64_to_cpu(start->l);
1234 args.type = XFS_ALLOCTYPE_START_BNO;
1235 /*
1236 * Make sure there is sufficient room left in the AG to
1237 * complete a full tree split for an extent insert. If
1238 * we are converting the middle part of an extent then
1239 * we may need space for two tree splits.
1240 *
1241 * We are relying on the caller to make the correct block
1242 * reservation for this operation to succeed. If the
1243 * reservation amount is insufficient then we may fail a
1244 * block allocation here and corrupt the filesystem.
1245 */
1246 args.minleft = xfs_trans_get_block_res(args.tp);
1247 } else if (cur->bc_private.b.flist->xbf_low) {
1248 args.type = XFS_ALLOCTYPE_START_BNO;
1249 } else {
1250 args.type = XFS_ALLOCTYPE_NEAR_BNO;
1251 }
1252
1253 args.minlen = args.maxlen = args.prod = 1;
1254 args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
1255 if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
1256 error = XFS_ERROR(ENOSPC);
1257 goto error0;
1258 }
1259 error = xfs_alloc_vextent(&args);
1260 if (error)
1261 goto error0;
1262
1263 if (args.fsbno == NULLFSBLOCK && args.minleft) {
1264 /*
1265 * Could not find an AG with enough free space to satisfy
1266 * a full btree split. Try again without minleft and if
1267 * successful activate the lowspace algorithm.
1268 */
1269 args.fsbno = 0;
1270 args.type = XFS_ALLOCTYPE_FIRST_AG;
1271 args.minleft = 0;
1272 error = xfs_alloc_vextent(&args);
1273 if (error)
1274 goto error0;
1275 cur->bc_private.b.flist->xbf_low = 1;
1276 }
1277 if (args.fsbno == NULLFSBLOCK) {
1278 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1279 *stat = 0;
1280 return 0;
1281 }
1282 ASSERT(args.len == 1);
1283 cur->bc_private.b.firstblock = args.fsbno;
1284 cur->bc_private.b.allocated++;
1285 cur->bc_private.b.ip->i_d.di_nblocks++;
1286 xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
1287 XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
1288 XFS_TRANS_DQ_BCOUNT, 1L);
1289
1290 new->l = cpu_to_be64(args.fsbno);
1291
1292 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1293 *stat = 1;
1294 return 0;
1295
1296 error0:
1297 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1298 return error;
1299}
1300
ce5e42db
CH		 1301STATIC int
1302xfs_bmbt_get_maxrecs(
1303 struct xfs_btree_cur *cur,
1304 int level)
1305{
1306 return XFS_BMAP_BLOCK_IMAXRECS(level, cur);
1307}
1308
4b22a571
CH		 1309/*
1310 * Get the maximum records we could store in the on-disk format.
1311 *
1312 * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
1313 * for the root node this checks the available space in the dinode fork
1314 * so that we can resize the in-memory buffer to match it. After a
1315 * resize to the maximum size this function returns the same value
1316 * as xfs_bmbt_get_maxrecs for the root node, too.
1317 */
1318STATIC int
1319xfs_bmbt_get_dmaxrecs(
1320 struct xfs_btree_cur *cur,
1321 int level)
1322{
1323 return XFS_BMAP_BLOCK_DMAXRECS(level, cur);
1324}
1325
fe033cc8
CH		 1326STATIC void
1327xfs_bmbt_init_key_from_rec(
1328 union xfs_btree_key *key,
1329 union xfs_btree_rec *rec)
1330{
1331 key->bmbt.br_startoff =
1332 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
1333}
1334
4b22a571
CH		 1335STATIC void
1336xfs_bmbt_init_rec_from_key(
1337 union xfs_btree_key *key,
1338 union xfs_btree_rec *rec)
1339{
1340 ASSERT(key->bmbt.br_startoff != 0);
1341
1342 xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
1343 0, 0, XFS_EXT_NORM);
1344}
1345
1346STATIC void
1347xfs_bmbt_init_rec_from_cur(
1348 struct xfs_btree_cur *cur,
1349 union xfs_btree_rec *rec)
1350{
1351 xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
1352}
1353
fe033cc8
CH		 1354STATIC void
1355xfs_bmbt_init_ptr_from_cur(
1356 struct xfs_btree_cur *cur,
1357 union xfs_btree_ptr *ptr)
1358{
1359 ptr->l = 0;
1360}
1361
1362STATIC __int64_t
1363xfs_bmbt_key_diff(
1364 struct xfs_btree_cur *cur,
1365 union xfs_btree_key *key)
1366{
1367 return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
1368 cur->bc_rec.b.br_startoff;
1369}
1370
8c4ed633
CH		 1371#ifdef XFS_BTREE_TRACE
1372ktrace_t *xfs_bmbt_trace_buf;
1373
1374STATIC void
1375xfs_bmbt_trace_enter(
1376 struct xfs_btree_cur *cur,
1377 const char *func,
1378 char *s,
1379 int type,
1380 int line,
1381 __psunsigned_t a0,
1382 __psunsigned_t a1,
1383 __psunsigned_t a2,
1384 __psunsigned_t a3,
1385 __psunsigned_t a4,
1386 __psunsigned_t a5,
1387 __psunsigned_t a6,
1388 __psunsigned_t a7,
1389 __psunsigned_t a8,
1390 __psunsigned_t a9,
1391 __psunsigned_t a10)
1392{
1393 struct xfs_inode *ip = cur->bc_private.b.ip;
1394 int whichfork = cur->bc_private.b.whichfork;
1395
1396 ktrace_enter(xfs_bmbt_trace_buf,
1397 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1398 (void *)func, (void *)s, (void *)ip, (void *)cur,
1399 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1400 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1401 (void *)a8, (void *)a9, (void *)a10);
1402 ktrace_enter(ip->i_btrace,
1403 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
1404 (void *)func, (void *)s, (void *)ip, (void *)cur,
1405 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
1406 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
1407 (void *)a8, (void *)a9, (void *)a10);
1408}
1409
1410STATIC void
1411xfs_bmbt_trace_cursor(
1412 struct xfs_btree_cur *cur,
1413 __uint32_t *s0,
1414 __uint64_t *l0,
1415 __uint64_t *l1)
1416{
1417 struct xfs_bmbt_rec_host r;
1418
1419 xfs_bmbt_set_all(&r, &cur->bc_rec.b);
1420
1421 *s0 = (cur->bc_nlevels << 24) |
1422 (cur->bc_private.b.flags << 16) |
1423 cur->bc_private.b.allocated;
1424 *l0 = r.l0;
1425 *l1 = r.l1;
1426}
1427
1428STATIC void
1429xfs_bmbt_trace_key(
1430 struct xfs_btree_cur *cur,
1431 union xfs_btree_key *key,
1432 __uint64_t *l0,
1433 __uint64_t *l1)
1434{
1435 *l0 = be64_to_cpu(key->bmbt.br_startoff);
1436 *l1 = 0;
1437}
1438
1439STATIC void
1440xfs_bmbt_trace_record(
1441 struct xfs_btree_cur *cur,
1442 union xfs_btree_rec *rec,
1443 __uint64_t *l0,
1444 __uint64_t *l1,
1445 __uint64_t *l2)
1446{
1447 struct xfs_bmbt_irec irec;
1448
1449 xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
1450 *l0 = irec.br_startoff;
1451 *l1 = irec.br_startblock;
1452 *l2 = irec.br_blockcount;
1453}
1454#endif /* XFS_BTREE_TRACE */
1455
561f7d17 1456static const struct xfs_btree_ops xfs_bmbt_ops = {
65f1eaea
CH		 1457 .rec_len = sizeof(xfs_bmbt_rec_t),
1458 .key_len = sizeof(xfs_bmbt_key_t),
1459
561f7d17 1460 .dup_cursor = xfs_bmbt_dup_cursor,
4b22a571 1461 .update_cursor = xfs_bmbt_update_cursor,
f5eb8e7c 1462 .alloc_block = xfs_bmbt_alloc_block,
ce5e42db 1463 .get_maxrecs = xfs_bmbt_get_maxrecs,
4b22a571 1464 .get_dmaxrecs = xfs_bmbt_get_dmaxrecs,
fe033cc8 1465 .init_key_from_rec = xfs_bmbt_init_key_from_rec,
4b22a571
CH		 1466 .init_rec_from_key = xfs_bmbt_init_rec_from_key,
1467 .init_rec_from_cur = xfs_bmbt_init_rec_from_cur,
fe033cc8
CH		 1468 .init_ptr_from_cur = xfs_bmbt_init_ptr_from_cur,
1469 .key_diff = xfs_bmbt_key_diff,
8c4ed633
CH		 1470
1471#ifdef XFS_BTREE_TRACE
1472 .trace_enter = xfs_bmbt_trace_enter,
1473 .trace_cursor = xfs_bmbt_trace_cursor,
1474 .trace_key = xfs_bmbt_trace_key,
1475 .trace_record = xfs_bmbt_trace_record,
1476#endif
561f7d17
CH		 1477};
1478
1479/*
1480 * Allocate a new bmap btree cursor.
1481 */
1482struct xfs_btree_cur * /* new bmap btree cursor */
1483xfs_bmbt_init_cursor(
1484 struct xfs_mount *mp, /* file system mount point */
1485 struct xfs_trans *tp, /* transaction pointer */
1486 struct xfs_inode *ip, /* inode owning the btree */
1487 int whichfork) /* data or attr fork */
1488{
1489 struct xfs_ifork *ifp = XFS_IFORK_PTR(ip, whichfork);
1490 struct xfs_btree_cur *cur;
1491
1492 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
1493
1494 cur->bc_tp = tp;
1495 cur->bc_mp = mp;
1496 cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
1497 cur->bc_btnum = XFS_BTNUM_BMAP;
1498 cur->bc_blocklog = mp->m_sb.sb_blocklog;
1499
1500 cur->bc_ops = &xfs_bmbt_ops;
e99ab90d 1501 cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
561f7d17
CH		 1502
1503 cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
1504 cur->bc_private.b.ip = ip;
1505 cur->bc_private.b.firstblock = NULLFSBLOCK;
1506 cur->bc_private.b.flist = NULL;
1507 cur->bc_private.b.allocated = 0;
1508 cur->bc_private.b.flags = 0;
1509 cur->bc_private.b.whichfork = whichfork;
1510
1511 return cur;
1512}
ubuntu-zesty-kernel mirror