1 /* 2 * Copyright (c) 2014 Red Hat, 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_shared.h" 21 #include "xfs_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_bit.h" 25 #include "xfs_sb.h" 26 #include "xfs_mount.h" 27 #include "xfs_defer.h" 28 #include "xfs_inode.h" 29 #include "xfs_trans.h" 30 #include "xfs_alloc.h" 31 #include "xfs_btree.h" 32 #include "xfs_rmap.h" 33 #include "xfs_rmap_btree.h" 34 #include "xfs_trace.h" 35 #include "xfs_cksum.h" 36 #include "xfs_error.h" 37 #include "xfs_extent_busy.h" 38 39 /* 40 * Reverse map btree. 41 * 42 * This is a per-ag tree used to track the owner(s) of a given extent. With 43 * reflink it is possible for there to be multiple owners, which is a departure 44 * from classic XFS. Owner records for data extents are inserted when the 45 * extent is mapped and removed when an extent is unmapped. Owner records for 46 * all other block types (i.e. metadata) are inserted when an extent is 47 * allocated and removed when an extent is freed. There can only be one owner 48 * of a metadata extent, usually an inode or some other metadata structure like 49 * an AG btree. 50 * 51 * The rmap btree is part of the free space management, so blocks for the tree 52 * are sourced from the agfl. Hence we need transaction reservation support for 53 * this tree so that the freelist is always large enough. This also impacts on 54 * the minimum space we need to leave free in the AG. 55 * 56 * The tree is ordered by [ag block, owner, offset]. This is a large key size, 57 * but it is the only way to enforce unique keys when a block can be owned by 58 * multiple files at any offset. There's no need to order/search by extent 59 * size for online updating/management of the tree. It is intended that most 60 * reverse lookups will be to find the owner(s) of a particular block, or to 61 * try to recover tree and file data from corrupt primary metadata. 62 */ 63 64 static struct xfs_btree_cur * 65 xfs_rmapbt_dup_cursor( 66 struct xfs_btree_cur *cur) 67 { 68 return xfs_rmapbt_init_cursor(cur->bc_mp, cur->bc_tp, 69 cur->bc_private.a.agbp, cur->bc_private.a.agno); 70 } 71 72 STATIC void 73 xfs_rmapbt_set_root( 74 struct xfs_btree_cur *cur, 75 union xfs_btree_ptr *ptr, 76 int inc) 77 { 78 struct xfs_buf *agbp = cur->bc_private.a.agbp; 79 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 80 xfs_agnumber_t seqno = be32_to_cpu(agf->agf_seqno); 81 int btnum = cur->bc_btnum; 82 struct xfs_perag *pag = xfs_perag_get(cur->bc_mp, seqno); 83 84 ASSERT(ptr->s != 0); 85 86 agf->agf_roots[btnum] = ptr->s; 87 be32_add_cpu(&agf->agf_levels[btnum], inc); 88 pag->pagf_levels[btnum] += inc; 89 xfs_perag_put(pag); 90 91 xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS); 92 } 93 94 STATIC int 95 xfs_rmapbt_alloc_block( 96 struct xfs_btree_cur *cur, 97 union xfs_btree_ptr *start, 98 union xfs_btree_ptr *new, 99 int *stat) 100 { 101 int error; 102 xfs_agblock_t bno; 103 104 XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY); 105 106 /* Allocate the new block from the freelist. If we can't, give up. */ 107 error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp, 108 &bno, 1); 109 if (error) { 110 XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR); 111 return error; 112 } 113 114 trace_xfs_rmapbt_alloc_block(cur->bc_mp, cur->bc_private.a.agno, 115 bno, 1); 116 if (bno == NULLAGBLOCK) { 117 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 118 *stat = 0; 119 return 0; 120 } 121 122 xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, 123 false); 124 125 xfs_trans_agbtree_delta(cur->bc_tp, 1); 126 new->s = cpu_to_be32(bno); 127 128 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT); 129 *stat = 1; 130 return 0; 131 } 132 133 STATIC int 134 xfs_rmapbt_free_block( 135 struct xfs_btree_cur *cur, 136 struct xfs_buf *bp) 137 { 138 struct xfs_buf *agbp = cur->bc_private.a.agbp; 139 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 140 xfs_agblock_t bno; 141 int error; 142 143 bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp)); 144 trace_xfs_rmapbt_free_block(cur->bc_mp, cur->bc_private.a.agno, 145 bno, 1); 146 error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1); 147 if (error) 148 return error; 149 150 xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1, 151 XFS_EXTENT_BUSY_SKIP_DISCARD); 152 xfs_trans_agbtree_delta(cur->bc_tp, -1); 153 154 return 0; 155 } 156 157 STATIC int 158 xfs_rmapbt_get_minrecs( 159 struct xfs_btree_cur *cur, 160 int level) 161 { 162 return cur->bc_mp->m_rmap_mnr[level != 0]; 163 } 164 165 STATIC int 166 xfs_rmapbt_get_maxrecs( 167 struct xfs_btree_cur *cur, 168 int level) 169 { 170 return cur->bc_mp->m_rmap_mxr[level != 0]; 171 } 172 173 STATIC void 174 xfs_rmapbt_init_key_from_rec( 175 union xfs_btree_key *key, 176 union xfs_btree_rec *rec) 177 { 178 key->rmap.rm_startblock = rec->rmap.rm_startblock; 179 key->rmap.rm_owner = rec->rmap.rm_owner; 180 key->rmap.rm_offset = rec->rmap.rm_offset; 181 } 182 183 /* 184 * The high key for a reverse mapping record can be computed by shifting 185 * the startblock and offset to the highest value that would still map 186 * to that record. In practice this means that we add blockcount-1 to 187 * the startblock for all records, and if the record is for a data/attr 188 * fork mapping, we add blockcount-1 to the offset too. 189 */ 190 STATIC void 191 xfs_rmapbt_init_high_key_from_rec( 192 union xfs_btree_key *key, 193 union xfs_btree_rec *rec) 194 { 195 __uint64_t off; 196 int adj; 197 198 adj = be32_to_cpu(rec->rmap.rm_blockcount) - 1; 199 200 key->rmap.rm_startblock = rec->rmap.rm_startblock; 201 be32_add_cpu(&key->rmap.rm_startblock, adj); 202 key->rmap.rm_owner = rec->rmap.rm_owner; 203 key->rmap.rm_offset = rec->rmap.rm_offset; 204 if (XFS_RMAP_NON_INODE_OWNER(be64_to_cpu(rec->rmap.rm_owner)) || 205 XFS_RMAP_IS_BMBT_BLOCK(be64_to_cpu(rec->rmap.rm_offset))) 206 return; 207 off = be64_to_cpu(key->rmap.rm_offset); 208 off = (XFS_RMAP_OFF(off) + adj) | (off & ~XFS_RMAP_OFF_MASK); 209 key->rmap.rm_offset = cpu_to_be64(off); 210 } 211 212 STATIC void 213 xfs_rmapbt_init_rec_from_cur( 214 struct xfs_btree_cur *cur, 215 union xfs_btree_rec *rec) 216 { 217 rec->rmap.rm_startblock = cpu_to_be32(cur->bc_rec.r.rm_startblock); 218 rec->rmap.rm_blockcount = cpu_to_be32(cur->bc_rec.r.rm_blockcount); 219 rec->rmap.rm_owner = cpu_to_be64(cur->bc_rec.r.rm_owner); 220 rec->rmap.rm_offset = cpu_to_be64( 221 xfs_rmap_irec_offset_pack(&cur->bc_rec.r)); 222 } 223 224 STATIC void 225 xfs_rmapbt_init_ptr_from_cur( 226 struct xfs_btree_cur *cur, 227 union xfs_btree_ptr *ptr) 228 { 229 struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp); 230 231 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno)); 232 ASSERT(agf->agf_roots[cur->bc_btnum] != 0); 233 234 ptr->s = agf->agf_roots[cur->bc_btnum]; 235 } 236 237 STATIC __int64_t 238 xfs_rmapbt_key_diff( 239 struct xfs_btree_cur *cur, 240 union xfs_btree_key *key) 241 { 242 struct xfs_rmap_irec *rec = &cur->bc_rec.r; 243 struct xfs_rmap_key *kp = &key->rmap; 244 __u64 x, y; 245 __int64_t d; 246 247 d = (__int64_t)be32_to_cpu(kp->rm_startblock) - rec->rm_startblock; 248 if (d) 249 return d; 250 251 x = be64_to_cpu(kp->rm_owner); 252 y = rec->rm_owner; 253 if (x > y) 254 return 1; 255 else if (y > x) 256 return -1; 257 258 x = XFS_RMAP_OFF(be64_to_cpu(kp->rm_offset)); 259 y = rec->rm_offset; 260 if (x > y) 261 return 1; 262 else if (y > x) 263 return -1; 264 return 0; 265 } 266 267 STATIC __int64_t 268 xfs_rmapbt_diff_two_keys( 269 struct xfs_btree_cur *cur, 270 union xfs_btree_key *k1, 271 union xfs_btree_key *k2) 272 { 273 struct xfs_rmap_key *kp1 = &k1->rmap; 274 struct xfs_rmap_key *kp2 = &k2->rmap; 275 __int64_t d; 276 __u64 x, y; 277 278 d = (__int64_t)be32_to_cpu(kp1->rm_startblock) - 279 be32_to_cpu(kp2->rm_startblock); 280 if (d) 281 return d; 282 283 x = be64_to_cpu(kp1->rm_owner); 284 y = be64_to_cpu(kp2->rm_owner); 285 if (x > y) 286 return 1; 287 else if (y > x) 288 return -1; 289 290 x = XFS_RMAP_OFF(be64_to_cpu(kp1->rm_offset)); 291 y = XFS_RMAP_OFF(be64_to_cpu(kp2->rm_offset)); 292 if (x > y) 293 return 1; 294 else if (y > x) 295 return -1; 296 return 0; 297 } 298 299 static bool 300 xfs_rmapbt_verify( 301 struct xfs_buf *bp) 302 { 303 struct xfs_mount *mp = bp->b_target->bt_mount; 304 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 305 struct xfs_perag *pag = bp->b_pag; 306 unsigned int level; 307 308 /* 309 * magic number and level verification 310 * 311 * During growfs operations, we can't verify the exact level or owner as 312 * the perag is not fully initialised and hence not attached to the 313 * buffer. In this case, check against the maximum tree depth. 314 * 315 * Similarly, during log recovery we will have a perag structure 316 * attached, but the agf information will not yet have been initialised 317 * from the on disk AGF. Again, we can only check against maximum limits 318 * in this case. 319 */ 320 if (block->bb_magic != cpu_to_be32(XFS_RMAP_CRC_MAGIC)) 321 return false; 322 323 if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) 324 return false; 325 if (!xfs_btree_sblock_v5hdr_verify(bp)) 326 return false; 327 328 level = be16_to_cpu(block->bb_level); 329 if (pag && pag->pagf_init) { 330 if (level >= pag->pagf_levels[XFS_BTNUM_RMAPi]) 331 return false; 332 } else if (level >= mp->m_rmap_maxlevels) 333 return false; 334 335 return xfs_btree_sblock_verify(bp, mp->m_rmap_mxr[level != 0]); 336 } 337 338 static void 339 xfs_rmapbt_read_verify( 340 struct xfs_buf *bp) 341 { 342 if (!xfs_btree_sblock_verify_crc(bp)) 343 xfs_buf_ioerror(bp, -EFSBADCRC); 344 else if (!xfs_rmapbt_verify(bp)) 345 xfs_buf_ioerror(bp, -EFSCORRUPTED); 346 347 if (bp->b_error) { 348 trace_xfs_btree_corrupt(bp, _RET_IP_); 349 xfs_verifier_error(bp); 350 } 351 } 352 353 static void 354 xfs_rmapbt_write_verify( 355 struct xfs_buf *bp) 356 { 357 if (!xfs_rmapbt_verify(bp)) { 358 trace_xfs_btree_corrupt(bp, _RET_IP_); 359 xfs_buf_ioerror(bp, -EFSCORRUPTED); 360 xfs_verifier_error(bp); 361 return; 362 } 363 xfs_btree_sblock_calc_crc(bp); 364 365 } 366 367 const struct xfs_buf_ops xfs_rmapbt_buf_ops = { 368 .name = "xfs_rmapbt", 369 .verify_read = xfs_rmapbt_read_verify, 370 .verify_write = xfs_rmapbt_write_verify, 371 }; 372 373 #if defined(DEBUG) || defined(XFS_WARN) 374 STATIC int 375 xfs_rmapbt_keys_inorder( 376 struct xfs_btree_cur *cur, 377 union xfs_btree_key *k1, 378 union xfs_btree_key *k2) 379 { 380 __uint32_t x; 381 __uint32_t y; 382 __uint64_t a; 383 __uint64_t b; 384 385 x = be32_to_cpu(k1->rmap.rm_startblock); 386 y = be32_to_cpu(k2->rmap.rm_startblock); 387 if (x < y) 388 return 1; 389 else if (x > y) 390 return 0; 391 a = be64_to_cpu(k1->rmap.rm_owner); 392 b = be64_to_cpu(k2->rmap.rm_owner); 393 if (a < b) 394 return 1; 395 else if (a > b) 396 return 0; 397 a = XFS_RMAP_OFF(be64_to_cpu(k1->rmap.rm_offset)); 398 b = XFS_RMAP_OFF(be64_to_cpu(k2->rmap.rm_offset)); 399 if (a <= b) 400 return 1; 401 return 0; 402 } 403 404 STATIC int 405 xfs_rmapbt_recs_inorder( 406 struct xfs_btree_cur *cur, 407 union xfs_btree_rec *r1, 408 union xfs_btree_rec *r2) 409 { 410 __uint32_t x; 411 __uint32_t y; 412 __uint64_t a; 413 __uint64_t b; 414 415 x = be32_to_cpu(r1->rmap.rm_startblock); 416 y = be32_to_cpu(r2->rmap.rm_startblock); 417 if (x < y) 418 return 1; 419 else if (x > y) 420 return 0; 421 a = be64_to_cpu(r1->rmap.rm_owner); 422 b = be64_to_cpu(r2->rmap.rm_owner); 423 if (a < b) 424 return 1; 425 else if (a > b) 426 return 0; 427 a = XFS_RMAP_OFF(be64_to_cpu(r1->rmap.rm_offset)); 428 b = XFS_RMAP_OFF(be64_to_cpu(r2->rmap.rm_offset)); 429 if (a <= b) 430 return 1; 431 return 0; 432 } 433 #endif /* DEBUG */ 434 435 static const struct xfs_btree_ops xfs_rmapbt_ops = { 436 .rec_len = sizeof(struct xfs_rmap_rec), 437 .key_len = 2 * sizeof(struct xfs_rmap_key), 438 439 .dup_cursor = xfs_rmapbt_dup_cursor, 440 .set_root = xfs_rmapbt_set_root, 441 .alloc_block = xfs_rmapbt_alloc_block, 442 .free_block = xfs_rmapbt_free_block, 443 .get_minrecs = xfs_rmapbt_get_minrecs, 444 .get_maxrecs = xfs_rmapbt_get_maxrecs, 445 .init_key_from_rec = xfs_rmapbt_init_key_from_rec, 446 .init_high_key_from_rec = xfs_rmapbt_init_high_key_from_rec, 447 .init_rec_from_cur = xfs_rmapbt_init_rec_from_cur, 448 .init_ptr_from_cur = xfs_rmapbt_init_ptr_from_cur, 449 .key_diff = xfs_rmapbt_key_diff, 450 .buf_ops = &xfs_rmapbt_buf_ops, 451 .diff_two_keys = xfs_rmapbt_diff_two_keys, 452 #if defined(DEBUG) || defined(XFS_WARN) 453 .keys_inorder = xfs_rmapbt_keys_inorder, 454 .recs_inorder = xfs_rmapbt_recs_inorder, 455 #endif 456 }; 457 458 /* 459 * Allocate a new allocation btree cursor. 460 */ 461 struct xfs_btree_cur * 462 xfs_rmapbt_init_cursor( 463 struct xfs_mount *mp, 464 struct xfs_trans *tp, 465 struct xfs_buf *agbp, 466 xfs_agnumber_t agno) 467 { 468 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp); 469 struct xfs_btree_cur *cur; 470 471 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 472 cur->bc_tp = tp; 473 cur->bc_mp = mp; 474 /* Overlapping btree; 2 keys per pointer. */ 475 cur->bc_btnum = XFS_BTNUM_RMAP; 476 cur->bc_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING; 477 cur->bc_blocklog = mp->m_sb.sb_blocklog; 478 cur->bc_ops = &xfs_rmapbt_ops; 479 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]); 480 481 cur->bc_private.a.agbp = agbp; 482 cur->bc_private.a.agno = agno; 483 484 return cur; 485 } 486 487 /* 488 * Calculate number of records in an rmap btree block. 489 */ 490 int 491 xfs_rmapbt_maxrecs( 492 struct xfs_mount *mp, 493 int blocklen, 494 int leaf) 495 { 496 blocklen -= XFS_RMAP_BLOCK_LEN; 497 498 if (leaf) 499 return blocklen / sizeof(struct xfs_rmap_rec); 500 return blocklen / 501 (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); 502 } 503 504 /* Compute the maximum height of an rmap btree. */ 505 void 506 xfs_rmapbt_compute_maxlevels( 507 struct xfs_mount *mp) 508 { 509 mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels(mp, 510 mp->m_rmap_mnr, mp->m_sb.sb_agblocks); 511 } 512