1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2014 Red Hat, Inc. 4 * All Rights Reserved. 5 */ 6 #include "xfs.h" 7 #include "xfs_fs.h" 8 #include "xfs_shared.h" 9 #include "xfs_format.h" 10 #include "xfs_log_format.h" 11 #include "xfs_trans_resv.h" 12 #include "xfs_bit.h" 13 #include "xfs_mount.h" 14 #include "xfs_sb.h" 15 #include "xfs_defer.h" 16 #include "xfs_btree.h" 17 #include "xfs_trans.h" 18 #include "xfs_alloc.h" 19 #include "xfs_rmap.h" 20 #include "xfs_rmap_btree.h" 21 #include "xfs_trace.h" 22 #include "xfs_errortag.h" 23 #include "xfs_error.h" 24 #include "xfs_inode.h" 25 #include "xfs_ag.h" 26 #include "xfs_health.h" 27 28 struct kmem_cache *xfs_rmap_intent_cache; 29 30 /* 31 * Lookup the first record less than or equal to [bno, len, owner, offset] 32 * in the btree given by cur. 33 */ 34 int 35 xfs_rmap_lookup_le( 36 struct xfs_btree_cur *cur, 37 xfs_agblock_t bno, 38 uint64_t owner, 39 uint64_t offset, 40 unsigned int flags, 41 struct xfs_rmap_irec *irec, 42 int *stat) 43 { 44 int get_stat = 0; 45 int error; 46 47 cur->bc_rec.r.rm_startblock = bno; 48 cur->bc_rec.r.rm_blockcount = 0; 49 cur->bc_rec.r.rm_owner = owner; 50 cur->bc_rec.r.rm_offset = offset; 51 cur->bc_rec.r.rm_flags = flags; 52 53 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat); 54 if (error || !(*stat) || !irec) 55 return error; 56 57 error = xfs_rmap_get_rec(cur, irec, &get_stat); 58 if (error) 59 return error; 60 if (!get_stat) { 61 xfs_btree_mark_sick(cur); 62 return -EFSCORRUPTED; 63 } 64 65 return 0; 66 } 67 68 /* 69 * Lookup the record exactly matching [bno, len, owner, offset] 70 * in the btree given by cur. 71 */ 72 int 73 xfs_rmap_lookup_eq( 74 struct xfs_btree_cur *cur, 75 xfs_agblock_t bno, 76 xfs_extlen_t len, 77 uint64_t owner, 78 uint64_t offset, 79 unsigned int flags, 80 int *stat) 81 { 82 cur->bc_rec.r.rm_startblock = bno; 83 cur->bc_rec.r.rm_blockcount = len; 84 cur->bc_rec.r.rm_owner = owner; 85 cur->bc_rec.r.rm_offset = offset; 86 cur->bc_rec.r.rm_flags = flags; 87 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat); 88 } 89 90 /* 91 * Update the record referred to by cur to the value given 92 * by [bno, len, owner, offset]. 93 * This either works (return 0) or gets an EFSCORRUPTED error. 94 */ 95 STATIC int 96 xfs_rmap_update( 97 struct xfs_btree_cur *cur, 98 struct xfs_rmap_irec *irec) 99 { 100 union xfs_btree_rec rec; 101 int error; 102 103 trace_xfs_rmap_update(cur->bc_mp, cur->bc_ag.pag->pag_agno, 104 irec->rm_startblock, irec->rm_blockcount, 105 irec->rm_owner, irec->rm_offset, irec->rm_flags); 106 107 rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock); 108 rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount); 109 rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner); 110 rec.rmap.rm_offset = cpu_to_be64( 111 xfs_rmap_irec_offset_pack(irec)); 112 error = xfs_btree_update(cur, &rec); 113 if (error) 114 trace_xfs_rmap_update_error(cur->bc_mp, 115 cur->bc_ag.pag->pag_agno, error, _RET_IP_); 116 return error; 117 } 118 119 int 120 xfs_rmap_insert( 121 struct xfs_btree_cur *rcur, 122 xfs_agblock_t agbno, 123 xfs_extlen_t len, 124 uint64_t owner, 125 uint64_t offset, 126 unsigned int flags) 127 { 128 int i; 129 int error; 130 131 trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno, 132 len, owner, offset, flags); 133 134 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i); 135 if (error) 136 goto done; 137 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 0)) { 138 xfs_btree_mark_sick(rcur); 139 error = -EFSCORRUPTED; 140 goto done; 141 } 142 143 rcur->bc_rec.r.rm_startblock = agbno; 144 rcur->bc_rec.r.rm_blockcount = len; 145 rcur->bc_rec.r.rm_owner = owner; 146 rcur->bc_rec.r.rm_offset = offset; 147 rcur->bc_rec.r.rm_flags = flags; 148 error = xfs_btree_insert(rcur, &i); 149 if (error) 150 goto done; 151 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) { 152 xfs_btree_mark_sick(rcur); 153 error = -EFSCORRUPTED; 154 goto done; 155 } 156 done: 157 if (error) 158 trace_xfs_rmap_insert_error(rcur->bc_mp, 159 rcur->bc_ag.pag->pag_agno, error, _RET_IP_); 160 return error; 161 } 162 163 STATIC int 164 xfs_rmap_delete( 165 struct xfs_btree_cur *rcur, 166 xfs_agblock_t agbno, 167 xfs_extlen_t len, 168 uint64_t owner, 169 uint64_t offset, 170 unsigned int flags) 171 { 172 int i; 173 int error; 174 175 trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_ag.pag->pag_agno, agbno, 176 len, owner, offset, flags); 177 178 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i); 179 if (error) 180 goto done; 181 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) { 182 xfs_btree_mark_sick(rcur); 183 error = -EFSCORRUPTED; 184 goto done; 185 } 186 187 error = xfs_btree_delete(rcur, &i); 188 if (error) 189 goto done; 190 if (XFS_IS_CORRUPT(rcur->bc_mp, i != 1)) { 191 xfs_btree_mark_sick(rcur); 192 error = -EFSCORRUPTED; 193 goto done; 194 } 195 done: 196 if (error) 197 trace_xfs_rmap_delete_error(rcur->bc_mp, 198 rcur->bc_ag.pag->pag_agno, error, _RET_IP_); 199 return error; 200 } 201 202 /* Convert an internal btree record to an rmap record. */ 203 xfs_failaddr_t 204 xfs_rmap_btrec_to_irec( 205 const union xfs_btree_rec *rec, 206 struct xfs_rmap_irec *irec) 207 { 208 irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock); 209 irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount); 210 irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner); 211 return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset), 212 irec); 213 } 214 215 /* Simple checks for rmap records. */ 216 xfs_failaddr_t 217 xfs_rmap_check_irec( 218 struct xfs_btree_cur *cur, 219 const struct xfs_rmap_irec *irec) 220 { 221 struct xfs_mount *mp = cur->bc_mp; 222 bool is_inode; 223 bool is_unwritten; 224 bool is_bmbt; 225 bool is_attr; 226 227 if (irec->rm_blockcount == 0) 228 return __this_address; 229 if (irec->rm_startblock <= XFS_AGFL_BLOCK(mp)) { 230 if (irec->rm_owner != XFS_RMAP_OWN_FS) 231 return __this_address; 232 if (irec->rm_blockcount != XFS_AGFL_BLOCK(mp) + 1) 233 return __this_address; 234 } else { 235 /* check for valid extent range, including overflow */ 236 if (!xfs_verify_agbext(cur->bc_ag.pag, irec->rm_startblock, 237 irec->rm_blockcount)) 238 return __this_address; 239 } 240 241 if (!(xfs_verify_ino(mp, irec->rm_owner) || 242 (irec->rm_owner <= XFS_RMAP_OWN_FS && 243 irec->rm_owner >= XFS_RMAP_OWN_MIN))) 244 return __this_address; 245 246 /* Check flags. */ 247 is_inode = !XFS_RMAP_NON_INODE_OWNER(irec->rm_owner); 248 is_bmbt = irec->rm_flags & XFS_RMAP_BMBT_BLOCK; 249 is_attr = irec->rm_flags & XFS_RMAP_ATTR_FORK; 250 is_unwritten = irec->rm_flags & XFS_RMAP_UNWRITTEN; 251 252 if (is_bmbt && irec->rm_offset != 0) 253 return __this_address; 254 255 if (!is_inode && irec->rm_offset != 0) 256 return __this_address; 257 258 if (is_unwritten && (is_bmbt || !is_inode || is_attr)) 259 return __this_address; 260 261 if (!is_inode && (is_bmbt || is_unwritten || is_attr)) 262 return __this_address; 263 264 /* Check for a valid fork offset, if applicable. */ 265 if (is_inode && !is_bmbt && 266 !xfs_verify_fileext(mp, irec->rm_offset, irec->rm_blockcount)) 267 return __this_address; 268 269 return NULL; 270 } 271 272 static inline int 273 xfs_rmap_complain_bad_rec( 274 struct xfs_btree_cur *cur, 275 xfs_failaddr_t fa, 276 const struct xfs_rmap_irec *irec) 277 { 278 struct xfs_mount *mp = cur->bc_mp; 279 280 xfs_warn(mp, 281 "Reverse Mapping BTree record corruption in AG %d detected at %pS!", 282 cur->bc_ag.pag->pag_agno, fa); 283 xfs_warn(mp, 284 "Owner 0x%llx, flags 0x%x, start block 0x%x block count 0x%x", 285 irec->rm_owner, irec->rm_flags, irec->rm_startblock, 286 irec->rm_blockcount); 287 xfs_btree_mark_sick(cur); 288 return -EFSCORRUPTED; 289 } 290 291 /* 292 * Get the data from the pointed-to record. 293 */ 294 int 295 xfs_rmap_get_rec( 296 struct xfs_btree_cur *cur, 297 struct xfs_rmap_irec *irec, 298 int *stat) 299 { 300 union xfs_btree_rec *rec; 301 xfs_failaddr_t fa; 302 int error; 303 304 error = xfs_btree_get_rec(cur, &rec, stat); 305 if (error || !*stat) 306 return error; 307 308 fa = xfs_rmap_btrec_to_irec(rec, irec); 309 if (!fa) 310 fa = xfs_rmap_check_irec(cur, irec); 311 if (fa) 312 return xfs_rmap_complain_bad_rec(cur, fa, irec); 313 314 return 0; 315 } 316 317 struct xfs_find_left_neighbor_info { 318 struct xfs_rmap_irec high; 319 struct xfs_rmap_irec *irec; 320 }; 321 322 /* For each rmap given, figure out if it matches the key we want. */ 323 STATIC int 324 xfs_rmap_find_left_neighbor_helper( 325 struct xfs_btree_cur *cur, 326 const struct xfs_rmap_irec *rec, 327 void *priv) 328 { 329 struct xfs_find_left_neighbor_info *info = priv; 330 331 trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp, 332 cur->bc_ag.pag->pag_agno, rec->rm_startblock, 333 rec->rm_blockcount, rec->rm_owner, rec->rm_offset, 334 rec->rm_flags); 335 336 if (rec->rm_owner != info->high.rm_owner) 337 return 0; 338 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) && 339 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) && 340 rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset) 341 return 0; 342 343 *info->irec = *rec; 344 return -ECANCELED; 345 } 346 347 /* 348 * Find the record to the left of the given extent, being careful only to 349 * return a match with the same owner and adjacent physical and logical 350 * block ranges. 351 */ 352 STATIC int 353 xfs_rmap_find_left_neighbor( 354 struct xfs_btree_cur *cur, 355 xfs_agblock_t bno, 356 uint64_t owner, 357 uint64_t offset, 358 unsigned int flags, 359 struct xfs_rmap_irec *irec, 360 int *stat) 361 { 362 struct xfs_find_left_neighbor_info info; 363 int found = 0; 364 int error; 365 366 *stat = 0; 367 if (bno == 0) 368 return 0; 369 info.high.rm_startblock = bno - 1; 370 info.high.rm_owner = owner; 371 if (!XFS_RMAP_NON_INODE_OWNER(owner) && 372 !(flags & XFS_RMAP_BMBT_BLOCK)) { 373 if (offset == 0) 374 return 0; 375 info.high.rm_offset = offset - 1; 376 } else 377 info.high.rm_offset = 0; 378 info.high.rm_flags = flags; 379 info.high.rm_blockcount = 0; 380 info.irec = irec; 381 382 trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp, 383 cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags); 384 385 /* 386 * Historically, we always used the range query to walk every reverse 387 * mapping that could possibly overlap the key that the caller asked 388 * for, and filter out the ones that don't. That is very slow when 389 * there are a lot of records. 390 * 391 * However, there are two scenarios where the classic btree search can 392 * produce correct results -- if the index contains a record that is an 393 * exact match for the lookup key; and if there are no other records 394 * between the record we want and the key we supplied. 395 * 396 * As an optimization, try a non-overlapped lookup first. This makes 397 * extent conversion and remap operations run a bit faster if the 398 * physical extents aren't being shared. If we don't find what we 399 * want, we fall back to the overlapped query. 400 */ 401 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec, 402 &found); 403 if (error) 404 return error; 405 if (found) 406 error = xfs_rmap_find_left_neighbor_helper(cur, irec, &info); 407 if (!error) 408 error = xfs_rmap_query_range(cur, &info.high, &info.high, 409 xfs_rmap_find_left_neighbor_helper, &info); 410 if (error != -ECANCELED) 411 return error; 412 413 *stat = 1; 414 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp, 415 cur->bc_ag.pag->pag_agno, irec->rm_startblock, 416 irec->rm_blockcount, irec->rm_owner, irec->rm_offset, 417 irec->rm_flags); 418 return 0; 419 } 420 421 /* For each rmap given, figure out if it matches the key we want. */ 422 STATIC int 423 xfs_rmap_lookup_le_range_helper( 424 struct xfs_btree_cur *cur, 425 const struct xfs_rmap_irec *rec, 426 void *priv) 427 { 428 struct xfs_find_left_neighbor_info *info = priv; 429 430 trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp, 431 cur->bc_ag.pag->pag_agno, rec->rm_startblock, 432 rec->rm_blockcount, rec->rm_owner, rec->rm_offset, 433 rec->rm_flags); 434 435 if (rec->rm_owner != info->high.rm_owner) 436 return 0; 437 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) && 438 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) && 439 (rec->rm_offset > info->high.rm_offset || 440 rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset)) 441 return 0; 442 443 *info->irec = *rec; 444 return -ECANCELED; 445 } 446 447 /* 448 * Find the record to the left of the given extent, being careful only to 449 * return a match with the same owner and overlapping physical and logical 450 * block ranges. This is the overlapping-interval version of 451 * xfs_rmap_lookup_le. 452 */ 453 int 454 xfs_rmap_lookup_le_range( 455 struct xfs_btree_cur *cur, 456 xfs_agblock_t bno, 457 uint64_t owner, 458 uint64_t offset, 459 unsigned int flags, 460 struct xfs_rmap_irec *irec, 461 int *stat) 462 { 463 struct xfs_find_left_neighbor_info info; 464 int found = 0; 465 int error; 466 467 info.high.rm_startblock = bno; 468 info.high.rm_owner = owner; 469 if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK)) 470 info.high.rm_offset = offset; 471 else 472 info.high.rm_offset = 0; 473 info.high.rm_flags = flags; 474 info.high.rm_blockcount = 0; 475 *stat = 0; 476 info.irec = irec; 477 478 trace_xfs_rmap_lookup_le_range(cur->bc_mp, cur->bc_ag.pag->pag_agno, 479 bno, 0, owner, offset, flags); 480 481 /* 482 * Historically, we always used the range query to walk every reverse 483 * mapping that could possibly overlap the key that the caller asked 484 * for, and filter out the ones that don't. That is very slow when 485 * there are a lot of records. 486 * 487 * However, there are two scenarios where the classic btree search can 488 * produce correct results -- if the index contains a record that is an 489 * exact match for the lookup key; and if there are no other records 490 * between the record we want and the key we supplied. 491 * 492 * As an optimization, try a non-overlapped lookup first. This makes 493 * scrub run much faster on most filesystems because bmbt records are 494 * usually an exact match for rmap records. If we don't find what we 495 * want, we fall back to the overlapped query. 496 */ 497 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec, 498 &found); 499 if (error) 500 return error; 501 if (found) 502 error = xfs_rmap_lookup_le_range_helper(cur, irec, &info); 503 if (!error) 504 error = xfs_rmap_query_range(cur, &info.high, &info.high, 505 xfs_rmap_lookup_le_range_helper, &info); 506 if (error != -ECANCELED) 507 return error; 508 509 *stat = 1; 510 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 511 cur->bc_ag.pag->pag_agno, irec->rm_startblock, 512 irec->rm_blockcount, irec->rm_owner, irec->rm_offset, 513 irec->rm_flags); 514 return 0; 515 } 516 517 /* 518 * Perform all the relevant owner checks for a removal op. If we're doing an 519 * unknown-owner removal then we have no owner information to check. 520 */ 521 static int 522 xfs_rmap_free_check_owner( 523 struct xfs_btree_cur *cur, 524 uint64_t ltoff, 525 struct xfs_rmap_irec *rec, 526 xfs_filblks_t len, 527 uint64_t owner, 528 uint64_t offset, 529 unsigned int flags) 530 { 531 struct xfs_mount *mp = cur->bc_mp; 532 int error = 0; 533 534 if (owner == XFS_RMAP_OWN_UNKNOWN) 535 return 0; 536 537 /* Make sure the unwritten flag matches. */ 538 if (XFS_IS_CORRUPT(mp, 539 (flags & XFS_RMAP_UNWRITTEN) != 540 (rec->rm_flags & XFS_RMAP_UNWRITTEN))) { 541 xfs_btree_mark_sick(cur); 542 error = -EFSCORRUPTED; 543 goto out; 544 } 545 546 /* Make sure the owner matches what we expect to find in the tree. */ 547 if (XFS_IS_CORRUPT(mp, owner != rec->rm_owner)) { 548 xfs_btree_mark_sick(cur); 549 error = -EFSCORRUPTED; 550 goto out; 551 } 552 553 /* Check the offset, if necessary. */ 554 if (XFS_RMAP_NON_INODE_OWNER(owner)) 555 goto out; 556 557 if (flags & XFS_RMAP_BMBT_BLOCK) { 558 if (XFS_IS_CORRUPT(mp, 559 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK))) { 560 xfs_btree_mark_sick(cur); 561 error = -EFSCORRUPTED; 562 goto out; 563 } 564 } else { 565 if (XFS_IS_CORRUPT(mp, rec->rm_offset > offset)) { 566 xfs_btree_mark_sick(cur); 567 error = -EFSCORRUPTED; 568 goto out; 569 } 570 if (XFS_IS_CORRUPT(mp, 571 offset + len > ltoff + rec->rm_blockcount)) { 572 xfs_btree_mark_sick(cur); 573 error = -EFSCORRUPTED; 574 goto out; 575 } 576 } 577 578 out: 579 return error; 580 } 581 582 /* 583 * Find the extent in the rmap btree and remove it. 584 * 585 * The record we find should always be an exact match for the extent that we're 586 * looking for, since we insert them into the btree without modification. 587 * 588 * Special Case #1: when growing the filesystem, we "free" an extent when 589 * growing the last AG. This extent is new space and so it is not tracked as 590 * used space in the btree. The growfs code will pass in an owner of 591 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this 592 * extent. We verify that - the extent lookup result in a record that does not 593 * overlap. 594 * 595 * Special Case #2: EFIs do not record the owner of the extent, so when 596 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap 597 * btree to ignore the owner (i.e. wildcard match) so we don't trigger 598 * corruption checks during log recovery. 599 */ 600 STATIC int 601 xfs_rmap_unmap( 602 struct xfs_btree_cur *cur, 603 xfs_agblock_t bno, 604 xfs_extlen_t len, 605 bool unwritten, 606 const struct xfs_owner_info *oinfo) 607 { 608 struct xfs_mount *mp = cur->bc_mp; 609 struct xfs_rmap_irec ltrec; 610 uint64_t ltoff; 611 int error = 0; 612 int i; 613 uint64_t owner; 614 uint64_t offset; 615 unsigned int flags; 616 bool ignore_off; 617 618 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 619 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) || 620 (flags & XFS_RMAP_BMBT_BLOCK); 621 if (unwritten) 622 flags |= XFS_RMAP_UNWRITTEN; 623 trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len, 624 unwritten, oinfo); 625 626 /* 627 * We should always have a left record because there's a static record 628 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that 629 * will not ever be removed from the tree. 630 */ 631 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, <rec, &i); 632 if (error) 633 goto out_error; 634 if (XFS_IS_CORRUPT(mp, i != 1)) { 635 xfs_btree_mark_sick(cur); 636 error = -EFSCORRUPTED; 637 goto out_error; 638 } 639 640 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 641 cur->bc_ag.pag->pag_agno, ltrec.rm_startblock, 642 ltrec.rm_blockcount, ltrec.rm_owner, 643 ltrec.rm_offset, ltrec.rm_flags); 644 ltoff = ltrec.rm_offset; 645 646 /* 647 * For growfs, the incoming extent must be beyond the left record we 648 * just found as it is new space and won't be used by anyone. This is 649 * just a corruption check as we don't actually do anything with this 650 * extent. Note that we need to use >= instead of > because it might 651 * be the case that the "left" extent goes all the way to EOFS. 652 */ 653 if (owner == XFS_RMAP_OWN_NULL) { 654 if (XFS_IS_CORRUPT(mp, 655 bno < 656 ltrec.rm_startblock + ltrec.rm_blockcount)) { 657 xfs_btree_mark_sick(cur); 658 error = -EFSCORRUPTED; 659 goto out_error; 660 } 661 goto out_done; 662 } 663 664 /* 665 * If we're doing an unknown-owner removal for EFI recovery, we expect 666 * to find the full range in the rmapbt or nothing at all. If we 667 * don't find any rmaps overlapping either end of the range, we're 668 * done. Hopefully this means that the EFI creator already queued 669 * (and finished) a RUI to remove the rmap. 670 */ 671 if (owner == XFS_RMAP_OWN_UNKNOWN && 672 ltrec.rm_startblock + ltrec.rm_blockcount <= bno) { 673 struct xfs_rmap_irec rtrec; 674 675 error = xfs_btree_increment(cur, 0, &i); 676 if (error) 677 goto out_error; 678 if (i == 0) 679 goto out_done; 680 error = xfs_rmap_get_rec(cur, &rtrec, &i); 681 if (error) 682 goto out_error; 683 if (XFS_IS_CORRUPT(mp, i != 1)) { 684 xfs_btree_mark_sick(cur); 685 error = -EFSCORRUPTED; 686 goto out_error; 687 } 688 if (rtrec.rm_startblock >= bno + len) 689 goto out_done; 690 } 691 692 /* Make sure the extent we found covers the entire freeing range. */ 693 if (XFS_IS_CORRUPT(mp, 694 ltrec.rm_startblock > bno || 695 ltrec.rm_startblock + ltrec.rm_blockcount < 696 bno + len)) { 697 xfs_btree_mark_sick(cur); 698 error = -EFSCORRUPTED; 699 goto out_error; 700 } 701 702 /* Check owner information. */ 703 error = xfs_rmap_free_check_owner(cur, ltoff, <rec, len, owner, 704 offset, flags); 705 if (error) 706 goto out_error; 707 708 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) { 709 /* exact match, simply remove the record from rmap tree */ 710 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 711 ltrec.rm_startblock, ltrec.rm_blockcount, 712 ltrec.rm_owner, ltrec.rm_offset, 713 ltrec.rm_flags); 714 error = xfs_btree_delete(cur, &i); 715 if (error) 716 goto out_error; 717 if (XFS_IS_CORRUPT(mp, i != 1)) { 718 xfs_btree_mark_sick(cur); 719 error = -EFSCORRUPTED; 720 goto out_error; 721 } 722 } else if (ltrec.rm_startblock == bno) { 723 /* 724 * overlap left hand side of extent: move the start, trim the 725 * length and update the current record. 726 * 727 * ltbno ltlen 728 * Orig: |oooooooooooooooooooo| 729 * Freeing: |fffffffff| 730 * Result: |rrrrrrrrrr| 731 * bno len 732 */ 733 ltrec.rm_startblock += len; 734 ltrec.rm_blockcount -= len; 735 if (!ignore_off) 736 ltrec.rm_offset += len; 737 error = xfs_rmap_update(cur, <rec); 738 if (error) 739 goto out_error; 740 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) { 741 /* 742 * overlap right hand side of extent: trim the length and update 743 * the current record. 744 * 745 * ltbno ltlen 746 * Orig: |oooooooooooooooooooo| 747 * Freeing: |fffffffff| 748 * Result: |rrrrrrrrrr| 749 * bno len 750 */ 751 ltrec.rm_blockcount -= len; 752 error = xfs_rmap_update(cur, <rec); 753 if (error) 754 goto out_error; 755 } else { 756 757 /* 758 * overlap middle of extent: trim the length of the existing 759 * record to the length of the new left-extent size, increment 760 * the insertion position so we can insert a new record 761 * containing the remaining right-extent space. 762 * 763 * ltbno ltlen 764 * Orig: |oooooooooooooooooooo| 765 * Freeing: |fffffffff| 766 * Result: |rrrrr| |rrrr| 767 * bno len 768 */ 769 xfs_extlen_t orig_len = ltrec.rm_blockcount; 770 771 ltrec.rm_blockcount = bno - ltrec.rm_startblock; 772 error = xfs_rmap_update(cur, <rec); 773 if (error) 774 goto out_error; 775 776 error = xfs_btree_increment(cur, 0, &i); 777 if (error) 778 goto out_error; 779 780 cur->bc_rec.r.rm_startblock = bno + len; 781 cur->bc_rec.r.rm_blockcount = orig_len - len - 782 ltrec.rm_blockcount; 783 cur->bc_rec.r.rm_owner = ltrec.rm_owner; 784 if (ignore_off) 785 cur->bc_rec.r.rm_offset = 0; 786 else 787 cur->bc_rec.r.rm_offset = offset + len; 788 cur->bc_rec.r.rm_flags = flags; 789 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, 790 cur->bc_rec.r.rm_startblock, 791 cur->bc_rec.r.rm_blockcount, 792 cur->bc_rec.r.rm_owner, 793 cur->bc_rec.r.rm_offset, 794 cur->bc_rec.r.rm_flags); 795 error = xfs_btree_insert(cur, &i); 796 if (error) 797 goto out_error; 798 } 799 800 out_done: 801 trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 802 unwritten, oinfo); 803 out_error: 804 if (error) 805 trace_xfs_rmap_unmap_error(mp, cur->bc_ag.pag->pag_agno, 806 error, _RET_IP_); 807 return error; 808 } 809 810 /* 811 * Remove a reference to an extent in the rmap btree. 812 */ 813 int 814 xfs_rmap_free( 815 struct xfs_trans *tp, 816 struct xfs_buf *agbp, 817 struct xfs_perag *pag, 818 xfs_agblock_t bno, 819 xfs_extlen_t len, 820 const struct xfs_owner_info *oinfo) 821 { 822 struct xfs_mount *mp = tp->t_mountp; 823 struct xfs_btree_cur *cur; 824 int error; 825 826 if (!xfs_has_rmapbt(mp)) 827 return 0; 828 829 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag); 830 831 error = xfs_rmap_unmap(cur, bno, len, false, oinfo); 832 833 xfs_btree_del_cursor(cur, error); 834 return error; 835 } 836 837 /* 838 * A mergeable rmap must have the same owner and the same values for 839 * the unwritten, attr_fork, and bmbt flags. The startblock and 840 * offset are checked separately. 841 */ 842 static bool 843 xfs_rmap_is_mergeable( 844 struct xfs_rmap_irec *irec, 845 uint64_t owner, 846 unsigned int flags) 847 { 848 if (irec->rm_owner == XFS_RMAP_OWN_NULL) 849 return false; 850 if (irec->rm_owner != owner) 851 return false; 852 if ((flags & XFS_RMAP_UNWRITTEN) ^ 853 (irec->rm_flags & XFS_RMAP_UNWRITTEN)) 854 return false; 855 if ((flags & XFS_RMAP_ATTR_FORK) ^ 856 (irec->rm_flags & XFS_RMAP_ATTR_FORK)) 857 return false; 858 if ((flags & XFS_RMAP_BMBT_BLOCK) ^ 859 (irec->rm_flags & XFS_RMAP_BMBT_BLOCK)) 860 return false; 861 return true; 862 } 863 864 /* 865 * When we allocate a new block, the first thing we do is add a reference to 866 * the extent in the rmap btree. This takes the form of a [agbno, length, 867 * owner, offset] record. Flags are encoded in the high bits of the offset 868 * field. 869 */ 870 STATIC int 871 xfs_rmap_map( 872 struct xfs_btree_cur *cur, 873 xfs_agblock_t bno, 874 xfs_extlen_t len, 875 bool unwritten, 876 const struct xfs_owner_info *oinfo) 877 { 878 struct xfs_mount *mp = cur->bc_mp; 879 struct xfs_rmap_irec ltrec; 880 struct xfs_rmap_irec gtrec; 881 int have_gt; 882 int have_lt; 883 int error = 0; 884 int i; 885 uint64_t owner; 886 uint64_t offset; 887 unsigned int flags = 0; 888 bool ignore_off; 889 890 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 891 ASSERT(owner != 0); 892 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) || 893 (flags & XFS_RMAP_BMBT_BLOCK); 894 if (unwritten) 895 flags |= XFS_RMAP_UNWRITTEN; 896 trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len, 897 unwritten, oinfo); 898 ASSERT(!xfs_rmap_should_skip_owner_update(oinfo)); 899 900 /* 901 * For the initial lookup, look for an exact match or the left-adjacent 902 * record for our insertion point. This will also give us the record for 903 * start block contiguity tests. 904 */ 905 error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, <rec, 906 &have_lt); 907 if (error) 908 goto out_error; 909 if (have_lt) { 910 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 911 cur->bc_ag.pag->pag_agno, ltrec.rm_startblock, 912 ltrec.rm_blockcount, ltrec.rm_owner, 913 ltrec.rm_offset, ltrec.rm_flags); 914 915 if (!xfs_rmap_is_mergeable(<rec, owner, flags)) 916 have_lt = 0; 917 } 918 919 if (XFS_IS_CORRUPT(mp, 920 have_lt != 0 && 921 ltrec.rm_startblock + ltrec.rm_blockcount > bno)) { 922 xfs_btree_mark_sick(cur); 923 error = -EFSCORRUPTED; 924 goto out_error; 925 } 926 927 /* 928 * Increment the cursor to see if we have a right-adjacent record to our 929 * insertion point. This will give us the record for end block 930 * contiguity tests. 931 */ 932 error = xfs_btree_increment(cur, 0, &have_gt); 933 if (error) 934 goto out_error; 935 if (have_gt) { 936 error = xfs_rmap_get_rec(cur, >rec, &have_gt); 937 if (error) 938 goto out_error; 939 if (XFS_IS_CORRUPT(mp, have_gt != 1)) { 940 xfs_btree_mark_sick(cur); 941 error = -EFSCORRUPTED; 942 goto out_error; 943 } 944 if (XFS_IS_CORRUPT(mp, bno + len > gtrec.rm_startblock)) { 945 xfs_btree_mark_sick(cur); 946 error = -EFSCORRUPTED; 947 goto out_error; 948 } 949 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 950 cur->bc_ag.pag->pag_agno, gtrec.rm_startblock, 951 gtrec.rm_blockcount, gtrec.rm_owner, 952 gtrec.rm_offset, gtrec.rm_flags); 953 if (!xfs_rmap_is_mergeable(>rec, owner, flags)) 954 have_gt = 0; 955 } 956 957 /* 958 * Note: cursor currently points one record to the right of ltrec, even 959 * if there is no record in the tree to the right. 960 */ 961 if (have_lt && 962 ltrec.rm_startblock + ltrec.rm_blockcount == bno && 963 (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) { 964 /* 965 * left edge contiguous, merge into left record. 966 * 967 * ltbno ltlen 968 * orig: |ooooooooo| 969 * adding: |aaaaaaaaa| 970 * result: |rrrrrrrrrrrrrrrrrrr| 971 * bno len 972 */ 973 ltrec.rm_blockcount += len; 974 if (have_gt && 975 bno + len == gtrec.rm_startblock && 976 (ignore_off || offset + len == gtrec.rm_offset) && 977 (unsigned long)ltrec.rm_blockcount + len + 978 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) { 979 /* 980 * right edge also contiguous, delete right record 981 * and merge into left record. 982 * 983 * ltbno ltlen gtbno gtlen 984 * orig: |ooooooooo| |ooooooooo| 985 * adding: |aaaaaaaaa| 986 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr| 987 */ 988 ltrec.rm_blockcount += gtrec.rm_blockcount; 989 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 990 gtrec.rm_startblock, 991 gtrec.rm_blockcount, 992 gtrec.rm_owner, 993 gtrec.rm_offset, 994 gtrec.rm_flags); 995 error = xfs_btree_delete(cur, &i); 996 if (error) 997 goto out_error; 998 if (XFS_IS_CORRUPT(mp, i != 1)) { 999 xfs_btree_mark_sick(cur); 1000 error = -EFSCORRUPTED; 1001 goto out_error; 1002 } 1003 } 1004 1005 /* point the cursor back to the left record and update */ 1006 error = xfs_btree_decrement(cur, 0, &have_gt); 1007 if (error) 1008 goto out_error; 1009 error = xfs_rmap_update(cur, <rec); 1010 if (error) 1011 goto out_error; 1012 } else if (have_gt && 1013 bno + len == gtrec.rm_startblock && 1014 (ignore_off || offset + len == gtrec.rm_offset)) { 1015 /* 1016 * right edge contiguous, merge into right record. 1017 * 1018 * gtbno gtlen 1019 * Orig: |ooooooooo| 1020 * adding: |aaaaaaaaa| 1021 * Result: |rrrrrrrrrrrrrrrrrrr| 1022 * bno len 1023 */ 1024 gtrec.rm_startblock = bno; 1025 gtrec.rm_blockcount += len; 1026 if (!ignore_off) 1027 gtrec.rm_offset = offset; 1028 error = xfs_rmap_update(cur, >rec); 1029 if (error) 1030 goto out_error; 1031 } else { 1032 /* 1033 * no contiguous edge with identical owner, insert 1034 * new record at current cursor position. 1035 */ 1036 cur->bc_rec.r.rm_startblock = bno; 1037 cur->bc_rec.r.rm_blockcount = len; 1038 cur->bc_rec.r.rm_owner = owner; 1039 cur->bc_rec.r.rm_offset = offset; 1040 cur->bc_rec.r.rm_flags = flags; 1041 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len, 1042 owner, offset, flags); 1043 error = xfs_btree_insert(cur, &i); 1044 if (error) 1045 goto out_error; 1046 if (XFS_IS_CORRUPT(mp, i != 1)) { 1047 xfs_btree_mark_sick(cur); 1048 error = -EFSCORRUPTED; 1049 goto out_error; 1050 } 1051 } 1052 1053 trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 1054 unwritten, oinfo); 1055 out_error: 1056 if (error) 1057 trace_xfs_rmap_map_error(mp, cur->bc_ag.pag->pag_agno, 1058 error, _RET_IP_); 1059 return error; 1060 } 1061 1062 /* 1063 * Add a reference to an extent in the rmap btree. 1064 */ 1065 int 1066 xfs_rmap_alloc( 1067 struct xfs_trans *tp, 1068 struct xfs_buf *agbp, 1069 struct xfs_perag *pag, 1070 xfs_agblock_t bno, 1071 xfs_extlen_t len, 1072 const struct xfs_owner_info *oinfo) 1073 { 1074 struct xfs_mount *mp = tp->t_mountp; 1075 struct xfs_btree_cur *cur; 1076 int error; 1077 1078 if (!xfs_has_rmapbt(mp)) 1079 return 0; 1080 1081 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, pag); 1082 error = xfs_rmap_map(cur, bno, len, false, oinfo); 1083 1084 xfs_btree_del_cursor(cur, error); 1085 return error; 1086 } 1087 1088 #define RMAP_LEFT_CONTIG (1 << 0) 1089 #define RMAP_RIGHT_CONTIG (1 << 1) 1090 #define RMAP_LEFT_FILLING (1 << 2) 1091 #define RMAP_RIGHT_FILLING (1 << 3) 1092 #define RMAP_LEFT_VALID (1 << 6) 1093 #define RMAP_RIGHT_VALID (1 << 7) 1094 1095 #define LEFT r[0] 1096 #define RIGHT r[1] 1097 #define PREV r[2] 1098 #define NEW r[3] 1099 1100 /* 1101 * Convert an unwritten extent to a real extent or vice versa. 1102 * Does not handle overlapping extents. 1103 */ 1104 STATIC int 1105 xfs_rmap_convert( 1106 struct xfs_btree_cur *cur, 1107 xfs_agblock_t bno, 1108 xfs_extlen_t len, 1109 bool unwritten, 1110 const struct xfs_owner_info *oinfo) 1111 { 1112 struct xfs_mount *mp = cur->bc_mp; 1113 struct xfs_rmap_irec r[4]; /* neighbor extent entries */ 1114 /* left is 0, right is 1, */ 1115 /* prev is 2, new is 3 */ 1116 uint64_t owner; 1117 uint64_t offset; 1118 uint64_t new_endoff; 1119 unsigned int oldext; 1120 unsigned int newext; 1121 unsigned int flags = 0; 1122 int i; 1123 int state = 0; 1124 int error; 1125 1126 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 1127 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) || 1128 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK)))); 1129 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0; 1130 new_endoff = offset + len; 1131 trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len, 1132 unwritten, oinfo); 1133 1134 /* 1135 * For the initial lookup, look for an exact match or the left-adjacent 1136 * record for our insertion point. This will also give us the record for 1137 * start block contiguity tests. 1138 */ 1139 error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, &PREV, &i); 1140 if (error) 1141 goto done; 1142 if (XFS_IS_CORRUPT(mp, i != 1)) { 1143 xfs_btree_mark_sick(cur); 1144 error = -EFSCORRUPTED; 1145 goto done; 1146 } 1147 1148 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 1149 cur->bc_ag.pag->pag_agno, PREV.rm_startblock, 1150 PREV.rm_blockcount, PREV.rm_owner, 1151 PREV.rm_offset, PREV.rm_flags); 1152 1153 ASSERT(PREV.rm_offset <= offset); 1154 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff); 1155 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext); 1156 newext = ~oldext & XFS_RMAP_UNWRITTEN; 1157 1158 /* 1159 * Set flags determining what part of the previous oldext allocation 1160 * extent is being replaced by a newext allocation. 1161 */ 1162 if (PREV.rm_offset == offset) 1163 state |= RMAP_LEFT_FILLING; 1164 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff) 1165 state |= RMAP_RIGHT_FILLING; 1166 1167 /* 1168 * Decrement the cursor to see if we have a left-adjacent record to our 1169 * insertion point. This will give us the record for end block 1170 * contiguity tests. 1171 */ 1172 error = xfs_btree_decrement(cur, 0, &i); 1173 if (error) 1174 goto done; 1175 if (i) { 1176 state |= RMAP_LEFT_VALID; 1177 error = xfs_rmap_get_rec(cur, &LEFT, &i); 1178 if (error) 1179 goto done; 1180 if (XFS_IS_CORRUPT(mp, i != 1)) { 1181 xfs_btree_mark_sick(cur); 1182 error = -EFSCORRUPTED; 1183 goto done; 1184 } 1185 if (XFS_IS_CORRUPT(mp, 1186 LEFT.rm_startblock + LEFT.rm_blockcount > 1187 bno)) { 1188 xfs_btree_mark_sick(cur); 1189 error = -EFSCORRUPTED; 1190 goto done; 1191 } 1192 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp, 1193 cur->bc_ag.pag->pag_agno, LEFT.rm_startblock, 1194 LEFT.rm_blockcount, LEFT.rm_owner, 1195 LEFT.rm_offset, LEFT.rm_flags); 1196 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno && 1197 LEFT.rm_offset + LEFT.rm_blockcount == offset && 1198 xfs_rmap_is_mergeable(&LEFT, owner, newext)) 1199 state |= RMAP_LEFT_CONTIG; 1200 } 1201 1202 /* 1203 * Increment the cursor to see if we have a right-adjacent record to our 1204 * insertion point. This will give us the record for end block 1205 * contiguity tests. 1206 */ 1207 error = xfs_btree_increment(cur, 0, &i); 1208 if (error) 1209 goto done; 1210 if (XFS_IS_CORRUPT(mp, i != 1)) { 1211 xfs_btree_mark_sick(cur); 1212 error = -EFSCORRUPTED; 1213 goto done; 1214 } 1215 error = xfs_btree_increment(cur, 0, &i); 1216 if (error) 1217 goto done; 1218 if (i) { 1219 state |= RMAP_RIGHT_VALID; 1220 error = xfs_rmap_get_rec(cur, &RIGHT, &i); 1221 if (error) 1222 goto done; 1223 if (XFS_IS_CORRUPT(mp, i != 1)) { 1224 xfs_btree_mark_sick(cur); 1225 error = -EFSCORRUPTED; 1226 goto done; 1227 } 1228 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) { 1229 xfs_btree_mark_sick(cur); 1230 error = -EFSCORRUPTED; 1231 goto done; 1232 } 1233 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 1234 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock, 1235 RIGHT.rm_blockcount, RIGHT.rm_owner, 1236 RIGHT.rm_offset, RIGHT.rm_flags); 1237 if (bno + len == RIGHT.rm_startblock && 1238 offset + len == RIGHT.rm_offset && 1239 xfs_rmap_is_mergeable(&RIGHT, owner, newext)) 1240 state |= RMAP_RIGHT_CONTIG; 1241 } 1242 1243 /* check that left + prev + right is not too long */ 1244 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1245 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) == 1246 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1247 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) && 1248 (unsigned long)LEFT.rm_blockcount + len + 1249 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX) 1250 state &= ~RMAP_RIGHT_CONTIG; 1251 1252 trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state, 1253 _RET_IP_); 1254 1255 /* reset the cursor back to PREV */ 1256 error = xfs_rmap_lookup_le(cur, bno, owner, offset, oldext, NULL, &i); 1257 if (error) 1258 goto done; 1259 if (XFS_IS_CORRUPT(mp, i != 1)) { 1260 xfs_btree_mark_sick(cur); 1261 error = -EFSCORRUPTED; 1262 goto done; 1263 } 1264 1265 /* 1266 * Switch out based on the FILLING and CONTIG state bits. 1267 */ 1268 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1269 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) { 1270 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1271 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1272 /* 1273 * Setting all of a previous oldext extent to newext. 1274 * The left and right neighbors are both contiguous with new. 1275 */ 1276 error = xfs_btree_increment(cur, 0, &i); 1277 if (error) 1278 goto done; 1279 if (XFS_IS_CORRUPT(mp, i != 1)) { 1280 xfs_btree_mark_sick(cur); 1281 error = -EFSCORRUPTED; 1282 goto done; 1283 } 1284 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 1285 RIGHT.rm_startblock, RIGHT.rm_blockcount, 1286 RIGHT.rm_owner, RIGHT.rm_offset, 1287 RIGHT.rm_flags); 1288 error = xfs_btree_delete(cur, &i); 1289 if (error) 1290 goto done; 1291 if (XFS_IS_CORRUPT(mp, i != 1)) { 1292 xfs_btree_mark_sick(cur); 1293 error = -EFSCORRUPTED; 1294 goto done; 1295 } 1296 error = xfs_btree_decrement(cur, 0, &i); 1297 if (error) 1298 goto done; 1299 if (XFS_IS_CORRUPT(mp, i != 1)) { 1300 xfs_btree_mark_sick(cur); 1301 error = -EFSCORRUPTED; 1302 goto done; 1303 } 1304 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 1305 PREV.rm_startblock, PREV.rm_blockcount, 1306 PREV.rm_owner, PREV.rm_offset, 1307 PREV.rm_flags); 1308 error = xfs_btree_delete(cur, &i); 1309 if (error) 1310 goto done; 1311 if (XFS_IS_CORRUPT(mp, i != 1)) { 1312 xfs_btree_mark_sick(cur); 1313 error = -EFSCORRUPTED; 1314 goto done; 1315 } 1316 error = xfs_btree_decrement(cur, 0, &i); 1317 if (error) 1318 goto done; 1319 if (XFS_IS_CORRUPT(mp, i != 1)) { 1320 xfs_btree_mark_sick(cur); 1321 error = -EFSCORRUPTED; 1322 goto done; 1323 } 1324 NEW = LEFT; 1325 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount; 1326 error = xfs_rmap_update(cur, &NEW); 1327 if (error) 1328 goto done; 1329 break; 1330 1331 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1332 /* 1333 * Setting all of a previous oldext extent to newext. 1334 * The left neighbor is contiguous, the right is not. 1335 */ 1336 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 1337 PREV.rm_startblock, PREV.rm_blockcount, 1338 PREV.rm_owner, PREV.rm_offset, 1339 PREV.rm_flags); 1340 error = xfs_btree_delete(cur, &i); 1341 if (error) 1342 goto done; 1343 if (XFS_IS_CORRUPT(mp, i != 1)) { 1344 xfs_btree_mark_sick(cur); 1345 error = -EFSCORRUPTED; 1346 goto done; 1347 } 1348 error = xfs_btree_decrement(cur, 0, &i); 1349 if (error) 1350 goto done; 1351 if (XFS_IS_CORRUPT(mp, i != 1)) { 1352 xfs_btree_mark_sick(cur); 1353 error = -EFSCORRUPTED; 1354 goto done; 1355 } 1356 NEW = LEFT; 1357 NEW.rm_blockcount += PREV.rm_blockcount; 1358 error = xfs_rmap_update(cur, &NEW); 1359 if (error) 1360 goto done; 1361 break; 1362 1363 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1364 /* 1365 * Setting all of a previous oldext extent to newext. 1366 * The right neighbor is contiguous, the left is not. 1367 */ 1368 error = xfs_btree_increment(cur, 0, &i); 1369 if (error) 1370 goto done; 1371 if (XFS_IS_CORRUPT(mp, i != 1)) { 1372 xfs_btree_mark_sick(cur); 1373 error = -EFSCORRUPTED; 1374 goto done; 1375 } 1376 trace_xfs_rmap_delete(mp, cur->bc_ag.pag->pag_agno, 1377 RIGHT.rm_startblock, RIGHT.rm_blockcount, 1378 RIGHT.rm_owner, RIGHT.rm_offset, 1379 RIGHT.rm_flags); 1380 error = xfs_btree_delete(cur, &i); 1381 if (error) 1382 goto done; 1383 if (XFS_IS_CORRUPT(mp, i != 1)) { 1384 xfs_btree_mark_sick(cur); 1385 error = -EFSCORRUPTED; 1386 goto done; 1387 } 1388 error = xfs_btree_decrement(cur, 0, &i); 1389 if (error) 1390 goto done; 1391 if (XFS_IS_CORRUPT(mp, i != 1)) { 1392 xfs_btree_mark_sick(cur); 1393 error = -EFSCORRUPTED; 1394 goto done; 1395 } 1396 NEW = PREV; 1397 NEW.rm_blockcount = len + RIGHT.rm_blockcount; 1398 NEW.rm_flags = newext; 1399 error = xfs_rmap_update(cur, &NEW); 1400 if (error) 1401 goto done; 1402 break; 1403 1404 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING: 1405 /* 1406 * Setting all of a previous oldext extent to newext. 1407 * Neither the left nor right neighbors are contiguous with 1408 * the new one. 1409 */ 1410 NEW = PREV; 1411 NEW.rm_flags = newext; 1412 error = xfs_rmap_update(cur, &NEW); 1413 if (error) 1414 goto done; 1415 break; 1416 1417 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG: 1418 /* 1419 * Setting the first part of a previous oldext extent to newext. 1420 * The left neighbor is contiguous. 1421 */ 1422 NEW = PREV; 1423 NEW.rm_offset += len; 1424 NEW.rm_startblock += len; 1425 NEW.rm_blockcount -= len; 1426 error = xfs_rmap_update(cur, &NEW); 1427 if (error) 1428 goto done; 1429 error = xfs_btree_decrement(cur, 0, &i); 1430 if (error) 1431 goto done; 1432 NEW = LEFT; 1433 NEW.rm_blockcount += len; 1434 error = xfs_rmap_update(cur, &NEW); 1435 if (error) 1436 goto done; 1437 break; 1438 1439 case RMAP_LEFT_FILLING: 1440 /* 1441 * Setting the first part of a previous oldext extent to newext. 1442 * The left neighbor is not contiguous. 1443 */ 1444 NEW = PREV; 1445 NEW.rm_startblock += len; 1446 NEW.rm_offset += len; 1447 NEW.rm_blockcount -= len; 1448 error = xfs_rmap_update(cur, &NEW); 1449 if (error) 1450 goto done; 1451 NEW.rm_startblock = bno; 1452 NEW.rm_owner = owner; 1453 NEW.rm_offset = offset; 1454 NEW.rm_blockcount = len; 1455 NEW.rm_flags = newext; 1456 cur->bc_rec.r = NEW; 1457 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, 1458 len, owner, offset, newext); 1459 error = xfs_btree_insert(cur, &i); 1460 if (error) 1461 goto done; 1462 if (XFS_IS_CORRUPT(mp, i != 1)) { 1463 xfs_btree_mark_sick(cur); 1464 error = -EFSCORRUPTED; 1465 goto done; 1466 } 1467 break; 1468 1469 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1470 /* 1471 * Setting the last part of a previous oldext extent to newext. 1472 * The right neighbor is contiguous with the new allocation. 1473 */ 1474 NEW = PREV; 1475 NEW.rm_blockcount -= len; 1476 error = xfs_rmap_update(cur, &NEW); 1477 if (error) 1478 goto done; 1479 error = xfs_btree_increment(cur, 0, &i); 1480 if (error) 1481 goto done; 1482 NEW = RIGHT; 1483 NEW.rm_offset = offset; 1484 NEW.rm_startblock = bno; 1485 NEW.rm_blockcount += len; 1486 error = xfs_rmap_update(cur, &NEW); 1487 if (error) 1488 goto done; 1489 break; 1490 1491 case RMAP_RIGHT_FILLING: 1492 /* 1493 * Setting the last part of a previous oldext extent to newext. 1494 * The right neighbor is not contiguous. 1495 */ 1496 NEW = PREV; 1497 NEW.rm_blockcount -= len; 1498 error = xfs_rmap_update(cur, &NEW); 1499 if (error) 1500 goto done; 1501 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, 1502 oldext, &i); 1503 if (error) 1504 goto done; 1505 if (XFS_IS_CORRUPT(mp, i != 0)) { 1506 xfs_btree_mark_sick(cur); 1507 error = -EFSCORRUPTED; 1508 goto done; 1509 } 1510 NEW.rm_startblock = bno; 1511 NEW.rm_owner = owner; 1512 NEW.rm_offset = offset; 1513 NEW.rm_blockcount = len; 1514 NEW.rm_flags = newext; 1515 cur->bc_rec.r = NEW; 1516 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, 1517 len, owner, offset, newext); 1518 error = xfs_btree_insert(cur, &i); 1519 if (error) 1520 goto done; 1521 if (XFS_IS_CORRUPT(mp, i != 1)) { 1522 xfs_btree_mark_sick(cur); 1523 error = -EFSCORRUPTED; 1524 goto done; 1525 } 1526 break; 1527 1528 case 0: 1529 /* 1530 * Setting the middle part of a previous oldext extent to 1531 * newext. Contiguity is impossible here. 1532 * One extent becomes three extents. 1533 */ 1534 /* new right extent - oldext */ 1535 NEW.rm_startblock = bno + len; 1536 NEW.rm_owner = owner; 1537 NEW.rm_offset = new_endoff; 1538 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount - 1539 new_endoff; 1540 NEW.rm_flags = PREV.rm_flags; 1541 error = xfs_rmap_update(cur, &NEW); 1542 if (error) 1543 goto done; 1544 /* new left extent - oldext */ 1545 NEW = PREV; 1546 NEW.rm_blockcount = offset - PREV.rm_offset; 1547 cur->bc_rec.r = NEW; 1548 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, 1549 NEW.rm_startblock, NEW.rm_blockcount, 1550 NEW.rm_owner, NEW.rm_offset, 1551 NEW.rm_flags); 1552 error = xfs_btree_insert(cur, &i); 1553 if (error) 1554 goto done; 1555 if (XFS_IS_CORRUPT(mp, i != 1)) { 1556 xfs_btree_mark_sick(cur); 1557 error = -EFSCORRUPTED; 1558 goto done; 1559 } 1560 /* 1561 * Reset the cursor to the position of the new extent 1562 * we are about to insert as we can't trust it after 1563 * the previous insert. 1564 */ 1565 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, 1566 oldext, &i); 1567 if (error) 1568 goto done; 1569 if (XFS_IS_CORRUPT(mp, i != 0)) { 1570 xfs_btree_mark_sick(cur); 1571 error = -EFSCORRUPTED; 1572 goto done; 1573 } 1574 /* new middle extent - newext */ 1575 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN; 1576 cur->bc_rec.r.rm_flags |= newext; 1577 trace_xfs_rmap_insert(mp, cur->bc_ag.pag->pag_agno, bno, len, 1578 owner, offset, newext); 1579 error = xfs_btree_insert(cur, &i); 1580 if (error) 1581 goto done; 1582 if (XFS_IS_CORRUPT(mp, i != 1)) { 1583 xfs_btree_mark_sick(cur); 1584 error = -EFSCORRUPTED; 1585 goto done; 1586 } 1587 break; 1588 1589 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1590 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1591 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG: 1592 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1593 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1594 case RMAP_LEFT_CONTIG: 1595 case RMAP_RIGHT_CONTIG: 1596 /* 1597 * These cases are all impossible. 1598 */ 1599 ASSERT(0); 1600 } 1601 1602 trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 1603 unwritten, oinfo); 1604 done: 1605 if (error) 1606 trace_xfs_rmap_convert_error(cur->bc_mp, 1607 cur->bc_ag.pag->pag_agno, error, _RET_IP_); 1608 return error; 1609 } 1610 1611 /* 1612 * Convert an unwritten extent to a real extent or vice versa. If there is no 1613 * possibility of overlapping extents, delegate to the simpler convert 1614 * function. 1615 */ 1616 STATIC int 1617 xfs_rmap_convert_shared( 1618 struct xfs_btree_cur *cur, 1619 xfs_agblock_t bno, 1620 xfs_extlen_t len, 1621 bool unwritten, 1622 const struct xfs_owner_info *oinfo) 1623 { 1624 struct xfs_mount *mp = cur->bc_mp; 1625 struct xfs_rmap_irec r[4]; /* neighbor extent entries */ 1626 /* left is 0, right is 1, */ 1627 /* prev is 2, new is 3 */ 1628 uint64_t owner; 1629 uint64_t offset; 1630 uint64_t new_endoff; 1631 unsigned int oldext; 1632 unsigned int newext; 1633 unsigned int flags = 0; 1634 int i; 1635 int state = 0; 1636 int error; 1637 1638 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 1639 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) || 1640 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK)))); 1641 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0; 1642 new_endoff = offset + len; 1643 trace_xfs_rmap_convert(mp, cur->bc_ag.pag->pag_agno, bno, len, 1644 unwritten, oinfo); 1645 1646 /* 1647 * For the initial lookup, look for and exact match or the left-adjacent 1648 * record for our insertion point. This will also give us the record for 1649 * start block contiguity tests. 1650 */ 1651 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, oldext, 1652 &PREV, &i); 1653 if (error) 1654 goto done; 1655 if (XFS_IS_CORRUPT(mp, i != 1)) { 1656 xfs_btree_mark_sick(cur); 1657 error = -EFSCORRUPTED; 1658 goto done; 1659 } 1660 1661 ASSERT(PREV.rm_offset <= offset); 1662 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff); 1663 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext); 1664 newext = ~oldext & XFS_RMAP_UNWRITTEN; 1665 1666 /* 1667 * Set flags determining what part of the previous oldext allocation 1668 * extent is being replaced by a newext allocation. 1669 */ 1670 if (PREV.rm_offset == offset) 1671 state |= RMAP_LEFT_FILLING; 1672 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff) 1673 state |= RMAP_RIGHT_FILLING; 1674 1675 /* Is there a left record that abuts our range? */ 1676 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext, 1677 &LEFT, &i); 1678 if (error) 1679 goto done; 1680 if (i) { 1681 state |= RMAP_LEFT_VALID; 1682 if (XFS_IS_CORRUPT(mp, 1683 LEFT.rm_startblock + LEFT.rm_blockcount > 1684 bno)) { 1685 xfs_btree_mark_sick(cur); 1686 error = -EFSCORRUPTED; 1687 goto done; 1688 } 1689 if (xfs_rmap_is_mergeable(&LEFT, owner, newext)) 1690 state |= RMAP_LEFT_CONTIG; 1691 } 1692 1693 /* Is there a right record that abuts our range? */ 1694 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len, 1695 newext, &i); 1696 if (error) 1697 goto done; 1698 if (i) { 1699 state |= RMAP_RIGHT_VALID; 1700 error = xfs_rmap_get_rec(cur, &RIGHT, &i); 1701 if (error) 1702 goto done; 1703 if (XFS_IS_CORRUPT(mp, i != 1)) { 1704 xfs_btree_mark_sick(cur); 1705 error = -EFSCORRUPTED; 1706 goto done; 1707 } 1708 if (XFS_IS_CORRUPT(mp, bno + len > RIGHT.rm_startblock)) { 1709 xfs_btree_mark_sick(cur); 1710 error = -EFSCORRUPTED; 1711 goto done; 1712 } 1713 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 1714 cur->bc_ag.pag->pag_agno, RIGHT.rm_startblock, 1715 RIGHT.rm_blockcount, RIGHT.rm_owner, 1716 RIGHT.rm_offset, RIGHT.rm_flags); 1717 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext)) 1718 state |= RMAP_RIGHT_CONTIG; 1719 } 1720 1721 /* check that left + prev + right is not too long */ 1722 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1723 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) == 1724 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1725 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) && 1726 (unsigned long)LEFT.rm_blockcount + len + 1727 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX) 1728 state &= ~RMAP_RIGHT_CONTIG; 1729 1730 trace_xfs_rmap_convert_state(mp, cur->bc_ag.pag->pag_agno, state, 1731 _RET_IP_); 1732 /* 1733 * Switch out based on the FILLING and CONTIG state bits. 1734 */ 1735 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1736 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) { 1737 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1738 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1739 /* 1740 * Setting all of a previous oldext extent to newext. 1741 * The left and right neighbors are both contiguous with new. 1742 */ 1743 error = xfs_rmap_delete(cur, RIGHT.rm_startblock, 1744 RIGHT.rm_blockcount, RIGHT.rm_owner, 1745 RIGHT.rm_offset, RIGHT.rm_flags); 1746 if (error) 1747 goto done; 1748 error = xfs_rmap_delete(cur, PREV.rm_startblock, 1749 PREV.rm_blockcount, PREV.rm_owner, 1750 PREV.rm_offset, PREV.rm_flags); 1751 if (error) 1752 goto done; 1753 NEW = LEFT; 1754 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1755 NEW.rm_blockcount, NEW.rm_owner, 1756 NEW.rm_offset, NEW.rm_flags, &i); 1757 if (error) 1758 goto done; 1759 if (XFS_IS_CORRUPT(mp, i != 1)) { 1760 xfs_btree_mark_sick(cur); 1761 error = -EFSCORRUPTED; 1762 goto done; 1763 } 1764 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount; 1765 error = xfs_rmap_update(cur, &NEW); 1766 if (error) 1767 goto done; 1768 break; 1769 1770 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1771 /* 1772 * Setting all of a previous oldext extent to newext. 1773 * The left neighbor is contiguous, the right is not. 1774 */ 1775 error = xfs_rmap_delete(cur, PREV.rm_startblock, 1776 PREV.rm_blockcount, PREV.rm_owner, 1777 PREV.rm_offset, PREV.rm_flags); 1778 if (error) 1779 goto done; 1780 NEW = LEFT; 1781 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1782 NEW.rm_blockcount, NEW.rm_owner, 1783 NEW.rm_offset, NEW.rm_flags, &i); 1784 if (error) 1785 goto done; 1786 if (XFS_IS_CORRUPT(mp, i != 1)) { 1787 xfs_btree_mark_sick(cur); 1788 error = -EFSCORRUPTED; 1789 goto done; 1790 } 1791 NEW.rm_blockcount += PREV.rm_blockcount; 1792 error = xfs_rmap_update(cur, &NEW); 1793 if (error) 1794 goto done; 1795 break; 1796 1797 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1798 /* 1799 * Setting all of a previous oldext extent to newext. 1800 * The right neighbor is contiguous, the left is not. 1801 */ 1802 error = xfs_rmap_delete(cur, RIGHT.rm_startblock, 1803 RIGHT.rm_blockcount, RIGHT.rm_owner, 1804 RIGHT.rm_offset, RIGHT.rm_flags); 1805 if (error) 1806 goto done; 1807 NEW = PREV; 1808 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1809 NEW.rm_blockcount, NEW.rm_owner, 1810 NEW.rm_offset, NEW.rm_flags, &i); 1811 if (error) 1812 goto done; 1813 if (XFS_IS_CORRUPT(mp, i != 1)) { 1814 xfs_btree_mark_sick(cur); 1815 error = -EFSCORRUPTED; 1816 goto done; 1817 } 1818 NEW.rm_blockcount += RIGHT.rm_blockcount; 1819 NEW.rm_flags = RIGHT.rm_flags; 1820 error = xfs_rmap_update(cur, &NEW); 1821 if (error) 1822 goto done; 1823 break; 1824 1825 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING: 1826 /* 1827 * Setting all of a previous oldext extent to newext. 1828 * Neither the left nor right neighbors are contiguous with 1829 * the new one. 1830 */ 1831 NEW = PREV; 1832 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1833 NEW.rm_blockcount, NEW.rm_owner, 1834 NEW.rm_offset, NEW.rm_flags, &i); 1835 if (error) 1836 goto done; 1837 if (XFS_IS_CORRUPT(mp, i != 1)) { 1838 xfs_btree_mark_sick(cur); 1839 error = -EFSCORRUPTED; 1840 goto done; 1841 } 1842 NEW.rm_flags = newext; 1843 error = xfs_rmap_update(cur, &NEW); 1844 if (error) 1845 goto done; 1846 break; 1847 1848 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG: 1849 /* 1850 * Setting the first part of a previous oldext extent to newext. 1851 * The left neighbor is contiguous. 1852 */ 1853 NEW = PREV; 1854 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1855 NEW.rm_blockcount, NEW.rm_owner, 1856 NEW.rm_offset, NEW.rm_flags); 1857 if (error) 1858 goto done; 1859 NEW.rm_offset += len; 1860 NEW.rm_startblock += len; 1861 NEW.rm_blockcount -= len; 1862 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1863 NEW.rm_blockcount, NEW.rm_owner, 1864 NEW.rm_offset, NEW.rm_flags); 1865 if (error) 1866 goto done; 1867 NEW = LEFT; 1868 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1869 NEW.rm_blockcount, NEW.rm_owner, 1870 NEW.rm_offset, NEW.rm_flags, &i); 1871 if (error) 1872 goto done; 1873 if (XFS_IS_CORRUPT(mp, i != 1)) { 1874 xfs_btree_mark_sick(cur); 1875 error = -EFSCORRUPTED; 1876 goto done; 1877 } 1878 NEW.rm_blockcount += len; 1879 error = xfs_rmap_update(cur, &NEW); 1880 if (error) 1881 goto done; 1882 break; 1883 1884 case RMAP_LEFT_FILLING: 1885 /* 1886 * Setting the first part of a previous oldext extent to newext. 1887 * The left neighbor is not contiguous. 1888 */ 1889 NEW = PREV; 1890 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1891 NEW.rm_blockcount, NEW.rm_owner, 1892 NEW.rm_offset, NEW.rm_flags); 1893 if (error) 1894 goto done; 1895 NEW.rm_offset += len; 1896 NEW.rm_startblock += len; 1897 NEW.rm_blockcount -= len; 1898 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1899 NEW.rm_blockcount, NEW.rm_owner, 1900 NEW.rm_offset, NEW.rm_flags); 1901 if (error) 1902 goto done; 1903 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext); 1904 if (error) 1905 goto done; 1906 break; 1907 1908 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1909 /* 1910 * Setting the last part of a previous oldext extent to newext. 1911 * The right neighbor is contiguous with the new allocation. 1912 */ 1913 NEW = PREV; 1914 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1915 NEW.rm_blockcount, NEW.rm_owner, 1916 NEW.rm_offset, NEW.rm_flags, &i); 1917 if (error) 1918 goto done; 1919 if (XFS_IS_CORRUPT(mp, i != 1)) { 1920 xfs_btree_mark_sick(cur); 1921 error = -EFSCORRUPTED; 1922 goto done; 1923 } 1924 NEW.rm_blockcount = offset - NEW.rm_offset; 1925 error = xfs_rmap_update(cur, &NEW); 1926 if (error) 1927 goto done; 1928 NEW = RIGHT; 1929 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1930 NEW.rm_blockcount, NEW.rm_owner, 1931 NEW.rm_offset, NEW.rm_flags); 1932 if (error) 1933 goto done; 1934 NEW.rm_offset = offset; 1935 NEW.rm_startblock = bno; 1936 NEW.rm_blockcount += len; 1937 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1938 NEW.rm_blockcount, NEW.rm_owner, 1939 NEW.rm_offset, NEW.rm_flags); 1940 if (error) 1941 goto done; 1942 break; 1943 1944 case RMAP_RIGHT_FILLING: 1945 /* 1946 * Setting the last part of a previous oldext extent to newext. 1947 * The right neighbor is not contiguous. 1948 */ 1949 NEW = PREV; 1950 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1951 NEW.rm_blockcount, NEW.rm_owner, 1952 NEW.rm_offset, NEW.rm_flags, &i); 1953 if (error) 1954 goto done; 1955 if (XFS_IS_CORRUPT(mp, i != 1)) { 1956 xfs_btree_mark_sick(cur); 1957 error = -EFSCORRUPTED; 1958 goto done; 1959 } 1960 NEW.rm_blockcount -= len; 1961 error = xfs_rmap_update(cur, &NEW); 1962 if (error) 1963 goto done; 1964 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext); 1965 if (error) 1966 goto done; 1967 break; 1968 1969 case 0: 1970 /* 1971 * Setting the middle part of a previous oldext extent to 1972 * newext. Contiguity is impossible here. 1973 * One extent becomes three extents. 1974 */ 1975 /* new right extent - oldext */ 1976 NEW.rm_startblock = bno + len; 1977 NEW.rm_owner = owner; 1978 NEW.rm_offset = new_endoff; 1979 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount - 1980 new_endoff; 1981 NEW.rm_flags = PREV.rm_flags; 1982 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1983 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset, 1984 NEW.rm_flags); 1985 if (error) 1986 goto done; 1987 /* new left extent - oldext */ 1988 NEW = PREV; 1989 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1990 NEW.rm_blockcount, NEW.rm_owner, 1991 NEW.rm_offset, NEW.rm_flags, &i); 1992 if (error) 1993 goto done; 1994 if (XFS_IS_CORRUPT(mp, i != 1)) { 1995 xfs_btree_mark_sick(cur); 1996 error = -EFSCORRUPTED; 1997 goto done; 1998 } 1999 NEW.rm_blockcount = offset - NEW.rm_offset; 2000 error = xfs_rmap_update(cur, &NEW); 2001 if (error) 2002 goto done; 2003 /* new middle extent - newext */ 2004 NEW.rm_startblock = bno; 2005 NEW.rm_blockcount = len; 2006 NEW.rm_owner = owner; 2007 NEW.rm_offset = offset; 2008 NEW.rm_flags = newext; 2009 error = xfs_rmap_insert(cur, NEW.rm_startblock, 2010 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset, 2011 NEW.rm_flags); 2012 if (error) 2013 goto done; 2014 break; 2015 2016 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 2017 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 2018 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG: 2019 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 2020 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 2021 case RMAP_LEFT_CONTIG: 2022 case RMAP_RIGHT_CONTIG: 2023 /* 2024 * These cases are all impossible. 2025 */ 2026 ASSERT(0); 2027 } 2028 2029 trace_xfs_rmap_convert_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 2030 unwritten, oinfo); 2031 done: 2032 if (error) 2033 trace_xfs_rmap_convert_error(cur->bc_mp, 2034 cur->bc_ag.pag->pag_agno, error, _RET_IP_); 2035 return error; 2036 } 2037 2038 #undef NEW 2039 #undef LEFT 2040 #undef RIGHT 2041 #undef PREV 2042 2043 /* 2044 * Find an extent in the rmap btree and unmap it. For rmap extent types that 2045 * can overlap (data fork rmaps on reflink filesystems) we must be careful 2046 * that the prev/next records in the btree might belong to another owner. 2047 * Therefore we must use delete+insert to alter any of the key fields. 2048 * 2049 * For every other situation there can only be one owner for a given extent, 2050 * so we can call the regular _free function. 2051 */ 2052 STATIC int 2053 xfs_rmap_unmap_shared( 2054 struct xfs_btree_cur *cur, 2055 xfs_agblock_t bno, 2056 xfs_extlen_t len, 2057 bool unwritten, 2058 const struct xfs_owner_info *oinfo) 2059 { 2060 struct xfs_mount *mp = cur->bc_mp; 2061 struct xfs_rmap_irec ltrec; 2062 uint64_t ltoff; 2063 int error = 0; 2064 int i; 2065 uint64_t owner; 2066 uint64_t offset; 2067 unsigned int flags; 2068 2069 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 2070 if (unwritten) 2071 flags |= XFS_RMAP_UNWRITTEN; 2072 trace_xfs_rmap_unmap(mp, cur->bc_ag.pag->pag_agno, bno, len, 2073 unwritten, oinfo); 2074 2075 /* 2076 * We should always have a left record because there's a static record 2077 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that 2078 * will not ever be removed from the tree. 2079 */ 2080 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags, 2081 <rec, &i); 2082 if (error) 2083 goto out_error; 2084 if (XFS_IS_CORRUPT(mp, i != 1)) { 2085 xfs_btree_mark_sick(cur); 2086 error = -EFSCORRUPTED; 2087 goto out_error; 2088 } 2089 ltoff = ltrec.rm_offset; 2090 2091 /* Make sure the extent we found covers the entire freeing range. */ 2092 if (XFS_IS_CORRUPT(mp, 2093 ltrec.rm_startblock > bno || 2094 ltrec.rm_startblock + ltrec.rm_blockcount < 2095 bno + len)) { 2096 xfs_btree_mark_sick(cur); 2097 error = -EFSCORRUPTED; 2098 goto out_error; 2099 } 2100 2101 /* Make sure the owner matches what we expect to find in the tree. */ 2102 if (XFS_IS_CORRUPT(mp, owner != ltrec.rm_owner)) { 2103 xfs_btree_mark_sick(cur); 2104 error = -EFSCORRUPTED; 2105 goto out_error; 2106 } 2107 2108 /* Make sure the unwritten flag matches. */ 2109 if (XFS_IS_CORRUPT(mp, 2110 (flags & XFS_RMAP_UNWRITTEN) != 2111 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN))) { 2112 xfs_btree_mark_sick(cur); 2113 error = -EFSCORRUPTED; 2114 goto out_error; 2115 } 2116 2117 /* Check the offset. */ 2118 if (XFS_IS_CORRUPT(mp, ltrec.rm_offset > offset)) { 2119 xfs_btree_mark_sick(cur); 2120 error = -EFSCORRUPTED; 2121 goto out_error; 2122 } 2123 if (XFS_IS_CORRUPT(mp, offset > ltoff + ltrec.rm_blockcount)) { 2124 xfs_btree_mark_sick(cur); 2125 error = -EFSCORRUPTED; 2126 goto out_error; 2127 } 2128 2129 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) { 2130 /* Exact match, simply remove the record from rmap tree. */ 2131 error = xfs_rmap_delete(cur, ltrec.rm_startblock, 2132 ltrec.rm_blockcount, ltrec.rm_owner, 2133 ltrec.rm_offset, ltrec.rm_flags); 2134 if (error) 2135 goto out_error; 2136 } else if (ltrec.rm_startblock == bno) { 2137 /* 2138 * Overlap left hand side of extent: move the start, trim the 2139 * length and update the current record. 2140 * 2141 * ltbno ltlen 2142 * Orig: |oooooooooooooooooooo| 2143 * Freeing: |fffffffff| 2144 * Result: |rrrrrrrrrr| 2145 * bno len 2146 */ 2147 2148 /* Delete prev rmap. */ 2149 error = xfs_rmap_delete(cur, ltrec.rm_startblock, 2150 ltrec.rm_blockcount, ltrec.rm_owner, 2151 ltrec.rm_offset, ltrec.rm_flags); 2152 if (error) 2153 goto out_error; 2154 2155 /* Add an rmap at the new offset. */ 2156 ltrec.rm_startblock += len; 2157 ltrec.rm_blockcount -= len; 2158 ltrec.rm_offset += len; 2159 error = xfs_rmap_insert(cur, ltrec.rm_startblock, 2160 ltrec.rm_blockcount, ltrec.rm_owner, 2161 ltrec.rm_offset, ltrec.rm_flags); 2162 if (error) 2163 goto out_error; 2164 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) { 2165 /* 2166 * Overlap right hand side of extent: trim the length and 2167 * update the current record. 2168 * 2169 * ltbno ltlen 2170 * Orig: |oooooooooooooooooooo| 2171 * Freeing: |fffffffff| 2172 * Result: |rrrrrrrrrr| 2173 * bno len 2174 */ 2175 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 2176 ltrec.rm_blockcount, ltrec.rm_owner, 2177 ltrec.rm_offset, ltrec.rm_flags, &i); 2178 if (error) 2179 goto out_error; 2180 if (XFS_IS_CORRUPT(mp, i != 1)) { 2181 xfs_btree_mark_sick(cur); 2182 error = -EFSCORRUPTED; 2183 goto out_error; 2184 } 2185 ltrec.rm_blockcount -= len; 2186 error = xfs_rmap_update(cur, <rec); 2187 if (error) 2188 goto out_error; 2189 } else { 2190 /* 2191 * Overlap middle of extent: trim the length of the existing 2192 * record to the length of the new left-extent size, increment 2193 * the insertion position so we can insert a new record 2194 * containing the remaining right-extent space. 2195 * 2196 * ltbno ltlen 2197 * Orig: |oooooooooooooooooooo| 2198 * Freeing: |fffffffff| 2199 * Result: |rrrrr| |rrrr| 2200 * bno len 2201 */ 2202 xfs_extlen_t orig_len = ltrec.rm_blockcount; 2203 2204 /* Shrink the left side of the rmap */ 2205 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 2206 ltrec.rm_blockcount, ltrec.rm_owner, 2207 ltrec.rm_offset, ltrec.rm_flags, &i); 2208 if (error) 2209 goto out_error; 2210 if (XFS_IS_CORRUPT(mp, i != 1)) { 2211 xfs_btree_mark_sick(cur); 2212 error = -EFSCORRUPTED; 2213 goto out_error; 2214 } 2215 ltrec.rm_blockcount = bno - ltrec.rm_startblock; 2216 error = xfs_rmap_update(cur, <rec); 2217 if (error) 2218 goto out_error; 2219 2220 /* Add an rmap at the new offset */ 2221 error = xfs_rmap_insert(cur, bno + len, 2222 orig_len - len - ltrec.rm_blockcount, 2223 ltrec.rm_owner, offset + len, 2224 ltrec.rm_flags); 2225 if (error) 2226 goto out_error; 2227 } 2228 2229 trace_xfs_rmap_unmap_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 2230 unwritten, oinfo); 2231 out_error: 2232 if (error) 2233 trace_xfs_rmap_unmap_error(cur->bc_mp, 2234 cur->bc_ag.pag->pag_agno, error, _RET_IP_); 2235 return error; 2236 } 2237 2238 /* 2239 * Find an extent in the rmap btree and map it. For rmap extent types that 2240 * can overlap (data fork rmaps on reflink filesystems) we must be careful 2241 * that the prev/next records in the btree might belong to another owner. 2242 * Therefore we must use delete+insert to alter any of the key fields. 2243 * 2244 * For every other situation there can only be one owner for a given extent, 2245 * so we can call the regular _alloc function. 2246 */ 2247 STATIC int 2248 xfs_rmap_map_shared( 2249 struct xfs_btree_cur *cur, 2250 xfs_agblock_t bno, 2251 xfs_extlen_t len, 2252 bool unwritten, 2253 const struct xfs_owner_info *oinfo) 2254 { 2255 struct xfs_mount *mp = cur->bc_mp; 2256 struct xfs_rmap_irec ltrec; 2257 struct xfs_rmap_irec gtrec; 2258 int have_gt; 2259 int have_lt; 2260 int error = 0; 2261 int i; 2262 uint64_t owner; 2263 uint64_t offset; 2264 unsigned int flags = 0; 2265 2266 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 2267 if (unwritten) 2268 flags |= XFS_RMAP_UNWRITTEN; 2269 trace_xfs_rmap_map(mp, cur->bc_ag.pag->pag_agno, bno, len, 2270 unwritten, oinfo); 2271 2272 /* Is there a left record that abuts our range? */ 2273 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags, 2274 <rec, &have_lt); 2275 if (error) 2276 goto out_error; 2277 if (have_lt && 2278 !xfs_rmap_is_mergeable(<rec, owner, flags)) 2279 have_lt = 0; 2280 2281 /* Is there a right record that abuts our range? */ 2282 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len, 2283 flags, &have_gt); 2284 if (error) 2285 goto out_error; 2286 if (have_gt) { 2287 error = xfs_rmap_get_rec(cur, >rec, &have_gt); 2288 if (error) 2289 goto out_error; 2290 if (XFS_IS_CORRUPT(mp, have_gt != 1)) { 2291 xfs_btree_mark_sick(cur); 2292 error = -EFSCORRUPTED; 2293 goto out_error; 2294 } 2295 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 2296 cur->bc_ag.pag->pag_agno, gtrec.rm_startblock, 2297 gtrec.rm_blockcount, gtrec.rm_owner, 2298 gtrec.rm_offset, gtrec.rm_flags); 2299 2300 if (!xfs_rmap_is_mergeable(>rec, owner, flags)) 2301 have_gt = 0; 2302 } 2303 2304 if (have_lt && 2305 ltrec.rm_startblock + ltrec.rm_blockcount == bno && 2306 ltrec.rm_offset + ltrec.rm_blockcount == offset) { 2307 /* 2308 * Left edge contiguous, merge into left record. 2309 * 2310 * ltbno ltlen 2311 * orig: |ooooooooo| 2312 * adding: |aaaaaaaaa| 2313 * result: |rrrrrrrrrrrrrrrrrrr| 2314 * bno len 2315 */ 2316 ltrec.rm_blockcount += len; 2317 if (have_gt && 2318 bno + len == gtrec.rm_startblock && 2319 offset + len == gtrec.rm_offset) { 2320 /* 2321 * Right edge also contiguous, delete right record 2322 * and merge into left record. 2323 * 2324 * ltbno ltlen gtbno gtlen 2325 * orig: |ooooooooo| |ooooooooo| 2326 * adding: |aaaaaaaaa| 2327 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr| 2328 */ 2329 ltrec.rm_blockcount += gtrec.rm_blockcount; 2330 error = xfs_rmap_delete(cur, gtrec.rm_startblock, 2331 gtrec.rm_blockcount, gtrec.rm_owner, 2332 gtrec.rm_offset, gtrec.rm_flags); 2333 if (error) 2334 goto out_error; 2335 } 2336 2337 /* Point the cursor back to the left record and update. */ 2338 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 2339 ltrec.rm_blockcount, ltrec.rm_owner, 2340 ltrec.rm_offset, ltrec.rm_flags, &i); 2341 if (error) 2342 goto out_error; 2343 if (XFS_IS_CORRUPT(mp, i != 1)) { 2344 xfs_btree_mark_sick(cur); 2345 error = -EFSCORRUPTED; 2346 goto out_error; 2347 } 2348 2349 error = xfs_rmap_update(cur, <rec); 2350 if (error) 2351 goto out_error; 2352 } else if (have_gt && 2353 bno + len == gtrec.rm_startblock && 2354 offset + len == gtrec.rm_offset) { 2355 /* 2356 * Right edge contiguous, merge into right record. 2357 * 2358 * gtbno gtlen 2359 * Orig: |ooooooooo| 2360 * adding: |aaaaaaaaa| 2361 * Result: |rrrrrrrrrrrrrrrrrrr| 2362 * bno len 2363 */ 2364 /* Delete the old record. */ 2365 error = xfs_rmap_delete(cur, gtrec.rm_startblock, 2366 gtrec.rm_blockcount, gtrec.rm_owner, 2367 gtrec.rm_offset, gtrec.rm_flags); 2368 if (error) 2369 goto out_error; 2370 2371 /* Move the start and re-add it. */ 2372 gtrec.rm_startblock = bno; 2373 gtrec.rm_blockcount += len; 2374 gtrec.rm_offset = offset; 2375 error = xfs_rmap_insert(cur, gtrec.rm_startblock, 2376 gtrec.rm_blockcount, gtrec.rm_owner, 2377 gtrec.rm_offset, gtrec.rm_flags); 2378 if (error) 2379 goto out_error; 2380 } else { 2381 /* 2382 * No contiguous edge with identical owner, insert 2383 * new record at current cursor position. 2384 */ 2385 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags); 2386 if (error) 2387 goto out_error; 2388 } 2389 2390 trace_xfs_rmap_map_done(mp, cur->bc_ag.pag->pag_agno, bno, len, 2391 unwritten, oinfo); 2392 out_error: 2393 if (error) 2394 trace_xfs_rmap_map_error(cur->bc_mp, 2395 cur->bc_ag.pag->pag_agno, error, _RET_IP_); 2396 return error; 2397 } 2398 2399 /* Insert a raw rmap into the rmapbt. */ 2400 int 2401 xfs_rmap_map_raw( 2402 struct xfs_btree_cur *cur, 2403 struct xfs_rmap_irec *rmap) 2404 { 2405 struct xfs_owner_info oinfo; 2406 2407 oinfo.oi_owner = rmap->rm_owner; 2408 oinfo.oi_offset = rmap->rm_offset; 2409 oinfo.oi_flags = 0; 2410 if (rmap->rm_flags & XFS_RMAP_ATTR_FORK) 2411 oinfo.oi_flags |= XFS_OWNER_INFO_ATTR_FORK; 2412 if (rmap->rm_flags & XFS_RMAP_BMBT_BLOCK) 2413 oinfo.oi_flags |= XFS_OWNER_INFO_BMBT_BLOCK; 2414 2415 if (rmap->rm_flags || XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner)) 2416 return xfs_rmap_map(cur, rmap->rm_startblock, 2417 rmap->rm_blockcount, 2418 rmap->rm_flags & XFS_RMAP_UNWRITTEN, 2419 &oinfo); 2420 2421 return xfs_rmap_map_shared(cur, rmap->rm_startblock, 2422 rmap->rm_blockcount, 2423 rmap->rm_flags & XFS_RMAP_UNWRITTEN, 2424 &oinfo); 2425 } 2426 2427 struct xfs_rmap_query_range_info { 2428 xfs_rmap_query_range_fn fn; 2429 void *priv; 2430 }; 2431 2432 /* Format btree record and pass to our callback. */ 2433 STATIC int 2434 xfs_rmap_query_range_helper( 2435 struct xfs_btree_cur *cur, 2436 const union xfs_btree_rec *rec, 2437 void *priv) 2438 { 2439 struct xfs_rmap_query_range_info *query = priv; 2440 struct xfs_rmap_irec irec; 2441 xfs_failaddr_t fa; 2442 2443 fa = xfs_rmap_btrec_to_irec(rec, &irec); 2444 if (!fa) 2445 fa = xfs_rmap_check_irec(cur, &irec); 2446 if (fa) 2447 return xfs_rmap_complain_bad_rec(cur, fa, &irec); 2448 2449 return query->fn(cur, &irec, query->priv); 2450 } 2451 2452 /* Find all rmaps between two keys. */ 2453 int 2454 xfs_rmap_query_range( 2455 struct xfs_btree_cur *cur, 2456 const struct xfs_rmap_irec *low_rec, 2457 const struct xfs_rmap_irec *high_rec, 2458 xfs_rmap_query_range_fn fn, 2459 void *priv) 2460 { 2461 union xfs_btree_irec low_brec = { .r = *low_rec }; 2462 union xfs_btree_irec high_brec = { .r = *high_rec }; 2463 struct xfs_rmap_query_range_info query = { .priv = priv, .fn = fn }; 2464 2465 return xfs_btree_query_range(cur, &low_brec, &high_brec, 2466 xfs_rmap_query_range_helper, &query); 2467 } 2468 2469 /* Find all rmaps. */ 2470 int 2471 xfs_rmap_query_all( 2472 struct xfs_btree_cur *cur, 2473 xfs_rmap_query_range_fn fn, 2474 void *priv) 2475 { 2476 struct xfs_rmap_query_range_info query; 2477 2478 query.priv = priv; 2479 query.fn = fn; 2480 return xfs_btree_query_all(cur, xfs_rmap_query_range_helper, &query); 2481 } 2482 2483 /* Clean up after calling xfs_rmap_finish_one. */ 2484 void 2485 xfs_rmap_finish_one_cleanup( 2486 struct xfs_trans *tp, 2487 struct xfs_btree_cur *rcur, 2488 int error) 2489 { 2490 struct xfs_buf *agbp; 2491 2492 if (rcur == NULL) 2493 return; 2494 agbp = rcur->bc_ag.agbp; 2495 xfs_btree_del_cursor(rcur, error); 2496 if (error) 2497 xfs_trans_brelse(tp, agbp); 2498 } 2499 2500 /* 2501 * Process one of the deferred rmap operations. We pass back the 2502 * btree cursor to maintain our lock on the rmapbt between calls. 2503 * This saves time and eliminates a buffer deadlock between the 2504 * superblock and the AGF because we'll always grab them in the same 2505 * order. 2506 */ 2507 int 2508 xfs_rmap_finish_one( 2509 struct xfs_trans *tp, 2510 struct xfs_rmap_intent *ri, 2511 struct xfs_btree_cur **pcur) 2512 { 2513 struct xfs_mount *mp = tp->t_mountp; 2514 struct xfs_btree_cur *rcur; 2515 struct xfs_buf *agbp = NULL; 2516 int error = 0; 2517 struct xfs_owner_info oinfo; 2518 xfs_agblock_t bno; 2519 bool unwritten; 2520 2521 bno = XFS_FSB_TO_AGBNO(mp, ri->ri_bmap.br_startblock); 2522 2523 trace_xfs_rmap_deferred(mp, ri->ri_pag->pag_agno, ri->ri_type, bno, 2524 ri->ri_owner, ri->ri_whichfork, 2525 ri->ri_bmap.br_startoff, ri->ri_bmap.br_blockcount, 2526 ri->ri_bmap.br_state); 2527 2528 if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_RMAP_FINISH_ONE)) 2529 return -EIO; 2530 2531 /* 2532 * If we haven't gotten a cursor or the cursor AG doesn't match 2533 * the startblock, get one now. 2534 */ 2535 rcur = *pcur; 2536 if (rcur != NULL && rcur->bc_ag.pag != ri->ri_pag) { 2537 xfs_rmap_finish_one_cleanup(tp, rcur, 0); 2538 rcur = NULL; 2539 *pcur = NULL; 2540 } 2541 if (rcur == NULL) { 2542 /* 2543 * Refresh the freelist before we start changing the 2544 * rmapbt, because a shape change could cause us to 2545 * allocate blocks. 2546 */ 2547 error = xfs_free_extent_fix_freelist(tp, ri->ri_pag, &agbp); 2548 if (error) { 2549 xfs_ag_mark_sick(ri->ri_pag, XFS_SICK_AG_AGFL); 2550 return error; 2551 } 2552 if (XFS_IS_CORRUPT(tp->t_mountp, !agbp)) { 2553 xfs_ag_mark_sick(ri->ri_pag, XFS_SICK_AG_AGFL); 2554 return -EFSCORRUPTED; 2555 } 2556 2557 rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, ri->ri_pag); 2558 } 2559 *pcur = rcur; 2560 2561 xfs_rmap_ino_owner(&oinfo, ri->ri_owner, ri->ri_whichfork, 2562 ri->ri_bmap.br_startoff); 2563 unwritten = ri->ri_bmap.br_state == XFS_EXT_UNWRITTEN; 2564 bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, ri->ri_bmap.br_startblock); 2565 2566 switch (ri->ri_type) { 2567 case XFS_RMAP_ALLOC: 2568 case XFS_RMAP_MAP: 2569 error = xfs_rmap_map(rcur, bno, ri->ri_bmap.br_blockcount, 2570 unwritten, &oinfo); 2571 break; 2572 case XFS_RMAP_MAP_SHARED: 2573 error = xfs_rmap_map_shared(rcur, bno, 2574 ri->ri_bmap.br_blockcount, unwritten, &oinfo); 2575 break; 2576 case XFS_RMAP_FREE: 2577 case XFS_RMAP_UNMAP: 2578 error = xfs_rmap_unmap(rcur, bno, ri->ri_bmap.br_blockcount, 2579 unwritten, &oinfo); 2580 break; 2581 case XFS_RMAP_UNMAP_SHARED: 2582 error = xfs_rmap_unmap_shared(rcur, bno, 2583 ri->ri_bmap.br_blockcount, unwritten, &oinfo); 2584 break; 2585 case XFS_RMAP_CONVERT: 2586 error = xfs_rmap_convert(rcur, bno, ri->ri_bmap.br_blockcount, 2587 !unwritten, &oinfo); 2588 break; 2589 case XFS_RMAP_CONVERT_SHARED: 2590 error = xfs_rmap_convert_shared(rcur, bno, 2591 ri->ri_bmap.br_blockcount, !unwritten, &oinfo); 2592 break; 2593 default: 2594 ASSERT(0); 2595 error = -EFSCORRUPTED; 2596 } 2597 2598 return error; 2599 } 2600 2601 /* 2602 * Don't defer an rmap if we aren't an rmap filesystem. 2603 */ 2604 static bool 2605 xfs_rmap_update_is_needed( 2606 struct xfs_mount *mp, 2607 int whichfork) 2608 { 2609 return xfs_has_rmapbt(mp) && whichfork != XFS_COW_FORK; 2610 } 2611 2612 /* 2613 * Record a rmap intent; the list is kept sorted first by AG and then by 2614 * increasing age. 2615 */ 2616 static void 2617 __xfs_rmap_add( 2618 struct xfs_trans *tp, 2619 enum xfs_rmap_intent_type type, 2620 uint64_t owner, 2621 int whichfork, 2622 struct xfs_bmbt_irec *bmap) 2623 { 2624 struct xfs_rmap_intent *ri; 2625 2626 trace_xfs_rmap_defer(tp->t_mountp, 2627 XFS_FSB_TO_AGNO(tp->t_mountp, bmap->br_startblock), 2628 type, 2629 XFS_FSB_TO_AGBNO(tp->t_mountp, bmap->br_startblock), 2630 owner, whichfork, 2631 bmap->br_startoff, 2632 bmap->br_blockcount, 2633 bmap->br_state); 2634 2635 ri = kmem_cache_alloc(xfs_rmap_intent_cache, GFP_KERNEL | __GFP_NOFAIL); 2636 INIT_LIST_HEAD(&ri->ri_list); 2637 ri->ri_type = type; 2638 ri->ri_owner = owner; 2639 ri->ri_whichfork = whichfork; 2640 ri->ri_bmap = *bmap; 2641 2642 xfs_rmap_update_get_group(tp->t_mountp, ri); 2643 xfs_defer_add(tp, &ri->ri_list, &xfs_rmap_update_defer_type); 2644 } 2645 2646 /* Map an extent into a file. */ 2647 void 2648 xfs_rmap_map_extent( 2649 struct xfs_trans *tp, 2650 struct xfs_inode *ip, 2651 int whichfork, 2652 struct xfs_bmbt_irec *PREV) 2653 { 2654 enum xfs_rmap_intent_type type = XFS_RMAP_MAP; 2655 2656 if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork)) 2657 return; 2658 2659 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip)) 2660 type = XFS_RMAP_MAP_SHARED; 2661 2662 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV); 2663 } 2664 2665 /* Unmap an extent out of a file. */ 2666 void 2667 xfs_rmap_unmap_extent( 2668 struct xfs_trans *tp, 2669 struct xfs_inode *ip, 2670 int whichfork, 2671 struct xfs_bmbt_irec *PREV) 2672 { 2673 enum xfs_rmap_intent_type type = XFS_RMAP_UNMAP; 2674 2675 if (!xfs_rmap_update_is_needed(tp->t_mountp, whichfork)) 2676 return; 2677 2678 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip)) 2679 type = XFS_RMAP_UNMAP_SHARED; 2680 2681 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV); 2682 } 2683 2684 /* 2685 * Convert a data fork extent from unwritten to real or vice versa. 2686 * 2687 * Note that tp can be NULL here as no transaction is used for COW fork 2688 * unwritten conversion. 2689 */ 2690 void 2691 xfs_rmap_convert_extent( 2692 struct xfs_mount *mp, 2693 struct xfs_trans *tp, 2694 struct xfs_inode *ip, 2695 int whichfork, 2696 struct xfs_bmbt_irec *PREV) 2697 { 2698 enum xfs_rmap_intent_type type = XFS_RMAP_CONVERT; 2699 2700 if (!xfs_rmap_update_is_needed(mp, whichfork)) 2701 return; 2702 2703 if (whichfork != XFS_ATTR_FORK && xfs_is_reflink_inode(ip)) 2704 type = XFS_RMAP_CONVERT_SHARED; 2705 2706 __xfs_rmap_add(tp, type, ip->i_ino, whichfork, PREV); 2707 } 2708 2709 /* Schedule the creation of an rmap for non-file data. */ 2710 void 2711 xfs_rmap_alloc_extent( 2712 struct xfs_trans *tp, 2713 xfs_agnumber_t agno, 2714 xfs_agblock_t bno, 2715 xfs_extlen_t len, 2716 uint64_t owner) 2717 { 2718 struct xfs_bmbt_irec bmap; 2719 2720 if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK)) 2721 return; 2722 2723 bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno); 2724 bmap.br_blockcount = len; 2725 bmap.br_startoff = 0; 2726 bmap.br_state = XFS_EXT_NORM; 2727 2728 __xfs_rmap_add(tp, XFS_RMAP_ALLOC, owner, XFS_DATA_FORK, &bmap); 2729 } 2730 2731 /* Schedule the deletion of an rmap for non-file data. */ 2732 void 2733 xfs_rmap_free_extent( 2734 struct xfs_trans *tp, 2735 xfs_agnumber_t agno, 2736 xfs_agblock_t bno, 2737 xfs_extlen_t len, 2738 uint64_t owner) 2739 { 2740 struct xfs_bmbt_irec bmap; 2741 2742 if (!xfs_rmap_update_is_needed(tp->t_mountp, XFS_DATA_FORK)) 2743 return; 2744 2745 bmap.br_startblock = XFS_AGB_TO_FSB(tp->t_mountp, agno, bno); 2746 bmap.br_blockcount = len; 2747 bmap.br_startoff = 0; 2748 bmap.br_state = XFS_EXT_NORM; 2749 2750 __xfs_rmap_add(tp, XFS_RMAP_FREE, owner, XFS_DATA_FORK, &bmap); 2751 } 2752 2753 /* Compare rmap records. Returns -1 if a < b, 1 if a > b, and 0 if equal. */ 2754 int 2755 xfs_rmap_compare( 2756 const struct xfs_rmap_irec *a, 2757 const struct xfs_rmap_irec *b) 2758 { 2759 __u64 oa; 2760 __u64 ob; 2761 2762 oa = xfs_rmap_irec_offset_pack(a); 2763 ob = xfs_rmap_irec_offset_pack(b); 2764 2765 if (a->rm_startblock < b->rm_startblock) 2766 return -1; 2767 else if (a->rm_startblock > b->rm_startblock) 2768 return 1; 2769 else if (a->rm_owner < b->rm_owner) 2770 return -1; 2771 else if (a->rm_owner > b->rm_owner) 2772 return 1; 2773 else if (oa < ob) 2774 return -1; 2775 else if (oa > ob) 2776 return 1; 2777 else 2778 return 0; 2779 } 2780 2781 /* 2782 * Scan the physical storage part of the keyspace of the reverse mapping index 2783 * and tell us if the area has no records, is fully mapped by records, or is 2784 * partially filled. 2785 */ 2786 int 2787 xfs_rmap_has_records( 2788 struct xfs_btree_cur *cur, 2789 xfs_agblock_t bno, 2790 xfs_extlen_t len, 2791 enum xbtree_recpacking *outcome) 2792 { 2793 union xfs_btree_key mask = { 2794 .rmap.rm_startblock = cpu_to_be32(-1U), 2795 }; 2796 union xfs_btree_irec low; 2797 union xfs_btree_irec high; 2798 2799 memset(&low, 0, sizeof(low)); 2800 low.r.rm_startblock = bno; 2801 memset(&high, 0xFF, sizeof(high)); 2802 high.r.rm_startblock = bno + len - 1; 2803 2804 return xfs_btree_has_records(cur, &low, &high, &mask, outcome); 2805 } 2806 2807 struct xfs_rmap_ownercount { 2808 /* Owner that we're looking for. */ 2809 struct xfs_rmap_irec good; 2810 2811 /* rmap search keys */ 2812 struct xfs_rmap_irec low; 2813 struct xfs_rmap_irec high; 2814 2815 struct xfs_rmap_matches *results; 2816 2817 /* Stop early if we find a nonmatch? */ 2818 bool stop_on_nonmatch; 2819 }; 2820 2821 /* Does this rmap represent space that can have multiple owners? */ 2822 static inline bool 2823 xfs_rmap_shareable( 2824 struct xfs_mount *mp, 2825 const struct xfs_rmap_irec *rmap) 2826 { 2827 if (!xfs_has_reflink(mp)) 2828 return false; 2829 if (XFS_RMAP_NON_INODE_OWNER(rmap->rm_owner)) 2830 return false; 2831 if (rmap->rm_flags & (XFS_RMAP_ATTR_FORK | 2832 XFS_RMAP_BMBT_BLOCK)) 2833 return false; 2834 return true; 2835 } 2836 2837 static inline void 2838 xfs_rmap_ownercount_init( 2839 struct xfs_rmap_ownercount *roc, 2840 xfs_agblock_t bno, 2841 xfs_extlen_t len, 2842 const struct xfs_owner_info *oinfo, 2843 struct xfs_rmap_matches *results) 2844 { 2845 memset(roc, 0, sizeof(*roc)); 2846 roc->results = results; 2847 2848 roc->low.rm_startblock = bno; 2849 memset(&roc->high, 0xFF, sizeof(roc->high)); 2850 roc->high.rm_startblock = bno + len - 1; 2851 2852 memset(results, 0, sizeof(*results)); 2853 roc->good.rm_startblock = bno; 2854 roc->good.rm_blockcount = len; 2855 roc->good.rm_owner = oinfo->oi_owner; 2856 roc->good.rm_offset = oinfo->oi_offset; 2857 if (oinfo->oi_flags & XFS_OWNER_INFO_ATTR_FORK) 2858 roc->good.rm_flags |= XFS_RMAP_ATTR_FORK; 2859 if (oinfo->oi_flags & XFS_OWNER_INFO_BMBT_BLOCK) 2860 roc->good.rm_flags |= XFS_RMAP_BMBT_BLOCK; 2861 } 2862 2863 /* Figure out if this is a match for the owner. */ 2864 STATIC int 2865 xfs_rmap_count_owners_helper( 2866 struct xfs_btree_cur *cur, 2867 const struct xfs_rmap_irec *rec, 2868 void *priv) 2869 { 2870 struct xfs_rmap_ownercount *roc = priv; 2871 struct xfs_rmap_irec check = *rec; 2872 unsigned int keyflags; 2873 bool filedata; 2874 int64_t delta; 2875 2876 filedata = !XFS_RMAP_NON_INODE_OWNER(check.rm_owner) && 2877 !(check.rm_flags & XFS_RMAP_BMBT_BLOCK); 2878 2879 /* Trim the part of check that comes before the comparison range. */ 2880 delta = (int64_t)roc->good.rm_startblock - check.rm_startblock; 2881 if (delta > 0) { 2882 check.rm_startblock += delta; 2883 check.rm_blockcount -= delta; 2884 if (filedata) 2885 check.rm_offset += delta; 2886 } 2887 2888 /* Trim the part of check that comes after the comparison range. */ 2889 delta = (check.rm_startblock + check.rm_blockcount) - 2890 (roc->good.rm_startblock + roc->good.rm_blockcount); 2891 if (delta > 0) 2892 check.rm_blockcount -= delta; 2893 2894 /* Don't care about unwritten status for establishing ownership. */ 2895 keyflags = check.rm_flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK); 2896 2897 if (check.rm_startblock == roc->good.rm_startblock && 2898 check.rm_blockcount == roc->good.rm_blockcount && 2899 check.rm_owner == roc->good.rm_owner && 2900 check.rm_offset == roc->good.rm_offset && 2901 keyflags == roc->good.rm_flags) { 2902 roc->results->matches++; 2903 } else { 2904 roc->results->non_owner_matches++; 2905 if (xfs_rmap_shareable(cur->bc_mp, &roc->good) ^ 2906 xfs_rmap_shareable(cur->bc_mp, &check)) 2907 roc->results->bad_non_owner_matches++; 2908 } 2909 2910 if (roc->results->non_owner_matches && roc->stop_on_nonmatch) 2911 return -ECANCELED; 2912 2913 return 0; 2914 } 2915 2916 /* Count the number of owners and non-owners of this range of blocks. */ 2917 int 2918 xfs_rmap_count_owners( 2919 struct xfs_btree_cur *cur, 2920 xfs_agblock_t bno, 2921 xfs_extlen_t len, 2922 const struct xfs_owner_info *oinfo, 2923 struct xfs_rmap_matches *results) 2924 { 2925 struct xfs_rmap_ownercount roc; 2926 int error; 2927 2928 xfs_rmap_ownercount_init(&roc, bno, len, oinfo, results); 2929 error = xfs_rmap_query_range(cur, &roc.low, &roc.high, 2930 xfs_rmap_count_owners_helper, &roc); 2931 if (error) 2932 return error; 2933 2934 /* 2935 * There can't be any non-owner rmaps that conflict with the given 2936 * owner if we didn't find any rmaps matching the owner. 2937 */ 2938 if (!results->matches) 2939 results->bad_non_owner_matches = 0; 2940 2941 return 0; 2942 } 2943 2944 /* 2945 * Given an extent and some owner info, can we find records overlapping 2946 * the extent whose owner info does not match the given owner? 2947 */ 2948 int 2949 xfs_rmap_has_other_keys( 2950 struct xfs_btree_cur *cur, 2951 xfs_agblock_t bno, 2952 xfs_extlen_t len, 2953 const struct xfs_owner_info *oinfo, 2954 bool *has_other) 2955 { 2956 struct xfs_rmap_matches res; 2957 struct xfs_rmap_ownercount roc; 2958 int error; 2959 2960 xfs_rmap_ownercount_init(&roc, bno, len, oinfo, &res); 2961 roc.stop_on_nonmatch = true; 2962 2963 error = xfs_rmap_query_range(cur, &roc.low, &roc.high, 2964 xfs_rmap_count_owners_helper, &roc); 2965 if (error == -ECANCELED) { 2966 *has_other = true; 2967 return 0; 2968 } 2969 if (error) 2970 return error; 2971 2972 *has_other = false; 2973 return 0; 2974 } 2975 2976 const struct xfs_owner_info XFS_RMAP_OINFO_SKIP_UPDATE = { 2977 .oi_owner = XFS_RMAP_OWN_NULL, 2978 }; 2979 const struct xfs_owner_info XFS_RMAP_OINFO_ANY_OWNER = { 2980 .oi_owner = XFS_RMAP_OWN_UNKNOWN, 2981 }; 2982 const struct xfs_owner_info XFS_RMAP_OINFO_FS = { 2983 .oi_owner = XFS_RMAP_OWN_FS, 2984 }; 2985 const struct xfs_owner_info XFS_RMAP_OINFO_LOG = { 2986 .oi_owner = XFS_RMAP_OWN_LOG, 2987 }; 2988 const struct xfs_owner_info XFS_RMAP_OINFO_AG = { 2989 .oi_owner = XFS_RMAP_OWN_AG, 2990 }; 2991 const struct xfs_owner_info XFS_RMAP_OINFO_INOBT = { 2992 .oi_owner = XFS_RMAP_OWN_INOBT, 2993 }; 2994 const struct xfs_owner_info XFS_RMAP_OINFO_INODES = { 2995 .oi_owner = XFS_RMAP_OWN_INODES, 2996 }; 2997 const struct xfs_owner_info XFS_RMAP_OINFO_REFC = { 2998 .oi_owner = XFS_RMAP_OWN_REFC, 2999 }; 3000 const struct xfs_owner_info XFS_RMAP_OINFO_COW = { 3001 .oi_owner = XFS_RMAP_OWN_COW, 3002 }; 3003 3004 int __init 3005 xfs_rmap_intent_init_cache(void) 3006 { 3007 xfs_rmap_intent_cache = kmem_cache_create("xfs_rmap_intent", 3008 sizeof(struct xfs_rmap_intent), 3009 0, 0, NULL); 3010 3011 return xfs_rmap_intent_cache != NULL ? 0 : -ENOMEM; 3012 } 3013 3014 void 3015 xfs_rmap_intent_destroy_cache(void) 3016 { 3017 kmem_cache_destroy(xfs_rmap_intent_cache); 3018 xfs_rmap_intent_cache = NULL; 3019 } 3020