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_da_format.h" 29 #include "xfs_da_btree.h" 30 #include "xfs_btree.h" 31 #include "xfs_trans.h" 32 #include "xfs_alloc.h" 33 #include "xfs_rmap.h" 34 #include "xfs_rmap_btree.h" 35 #include "xfs_trans_space.h" 36 #include "xfs_trace.h" 37 #include "xfs_error.h" 38 #include "xfs_extent_busy.h" 39 #include "xfs_bmap.h" 40 #include "xfs_inode.h" 41 42 /* 43 * Lookup the first record less than or equal to [bno, len, owner, offset] 44 * in the btree given by cur. 45 */ 46 int 47 xfs_rmap_lookup_le( 48 struct xfs_btree_cur *cur, 49 xfs_agblock_t bno, 50 xfs_extlen_t len, 51 uint64_t owner, 52 uint64_t offset, 53 unsigned int flags, 54 int *stat) 55 { 56 cur->bc_rec.r.rm_startblock = bno; 57 cur->bc_rec.r.rm_blockcount = len; 58 cur->bc_rec.r.rm_owner = owner; 59 cur->bc_rec.r.rm_offset = offset; 60 cur->bc_rec.r.rm_flags = flags; 61 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat); 62 } 63 64 /* 65 * Lookup the record exactly matching [bno, len, owner, offset] 66 * in the btree given by cur. 67 */ 68 int 69 xfs_rmap_lookup_eq( 70 struct xfs_btree_cur *cur, 71 xfs_agblock_t bno, 72 xfs_extlen_t len, 73 uint64_t owner, 74 uint64_t offset, 75 unsigned int flags, 76 int *stat) 77 { 78 cur->bc_rec.r.rm_startblock = bno; 79 cur->bc_rec.r.rm_blockcount = len; 80 cur->bc_rec.r.rm_owner = owner; 81 cur->bc_rec.r.rm_offset = offset; 82 cur->bc_rec.r.rm_flags = flags; 83 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat); 84 } 85 86 /* 87 * Update the record referred to by cur to the value given 88 * by [bno, len, owner, offset]. 89 * This either works (return 0) or gets an EFSCORRUPTED error. 90 */ 91 STATIC int 92 xfs_rmap_update( 93 struct xfs_btree_cur *cur, 94 struct xfs_rmap_irec *irec) 95 { 96 union xfs_btree_rec rec; 97 int error; 98 99 trace_xfs_rmap_update(cur->bc_mp, cur->bc_private.a.agno, 100 irec->rm_startblock, irec->rm_blockcount, 101 irec->rm_owner, irec->rm_offset, irec->rm_flags); 102 103 rec.rmap.rm_startblock = cpu_to_be32(irec->rm_startblock); 104 rec.rmap.rm_blockcount = cpu_to_be32(irec->rm_blockcount); 105 rec.rmap.rm_owner = cpu_to_be64(irec->rm_owner); 106 rec.rmap.rm_offset = cpu_to_be64( 107 xfs_rmap_irec_offset_pack(irec)); 108 error = xfs_btree_update(cur, &rec); 109 if (error) 110 trace_xfs_rmap_update_error(cur->bc_mp, 111 cur->bc_private.a.agno, error, _RET_IP_); 112 return error; 113 } 114 115 int 116 xfs_rmap_insert( 117 struct xfs_btree_cur *rcur, 118 xfs_agblock_t agbno, 119 xfs_extlen_t len, 120 uint64_t owner, 121 uint64_t offset, 122 unsigned int flags) 123 { 124 int i; 125 int error; 126 127 trace_xfs_rmap_insert(rcur->bc_mp, rcur->bc_private.a.agno, agbno, 128 len, owner, offset, flags); 129 130 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i); 131 if (error) 132 goto done; 133 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 0, done); 134 135 rcur->bc_rec.r.rm_startblock = agbno; 136 rcur->bc_rec.r.rm_blockcount = len; 137 rcur->bc_rec.r.rm_owner = owner; 138 rcur->bc_rec.r.rm_offset = offset; 139 rcur->bc_rec.r.rm_flags = flags; 140 error = xfs_btree_insert(rcur, &i); 141 if (error) 142 goto done; 143 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done); 144 done: 145 if (error) 146 trace_xfs_rmap_insert_error(rcur->bc_mp, 147 rcur->bc_private.a.agno, error, _RET_IP_); 148 return error; 149 } 150 151 STATIC int 152 xfs_rmap_delete( 153 struct xfs_btree_cur *rcur, 154 xfs_agblock_t agbno, 155 xfs_extlen_t len, 156 uint64_t owner, 157 uint64_t offset, 158 unsigned int flags) 159 { 160 int i; 161 int error; 162 163 trace_xfs_rmap_delete(rcur->bc_mp, rcur->bc_private.a.agno, agbno, 164 len, owner, offset, flags); 165 166 error = xfs_rmap_lookup_eq(rcur, agbno, len, owner, offset, flags, &i); 167 if (error) 168 goto done; 169 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done); 170 171 error = xfs_btree_delete(rcur, &i); 172 if (error) 173 goto done; 174 XFS_WANT_CORRUPTED_GOTO(rcur->bc_mp, i == 1, done); 175 done: 176 if (error) 177 trace_xfs_rmap_delete_error(rcur->bc_mp, 178 rcur->bc_private.a.agno, error, _RET_IP_); 179 return error; 180 } 181 182 static int 183 xfs_rmap_btrec_to_irec( 184 union xfs_btree_rec *rec, 185 struct xfs_rmap_irec *irec) 186 { 187 irec->rm_flags = 0; 188 irec->rm_startblock = be32_to_cpu(rec->rmap.rm_startblock); 189 irec->rm_blockcount = be32_to_cpu(rec->rmap.rm_blockcount); 190 irec->rm_owner = be64_to_cpu(rec->rmap.rm_owner); 191 return xfs_rmap_irec_offset_unpack(be64_to_cpu(rec->rmap.rm_offset), 192 irec); 193 } 194 195 /* 196 * Get the data from the pointed-to record. 197 */ 198 int 199 xfs_rmap_get_rec( 200 struct xfs_btree_cur *cur, 201 struct xfs_rmap_irec *irec, 202 int *stat) 203 { 204 union xfs_btree_rec *rec; 205 int error; 206 207 error = xfs_btree_get_rec(cur, &rec, stat); 208 if (error || !*stat) 209 return error; 210 211 return xfs_rmap_btrec_to_irec(rec, irec); 212 } 213 214 struct xfs_find_left_neighbor_info { 215 struct xfs_rmap_irec high; 216 struct xfs_rmap_irec *irec; 217 int *stat; 218 }; 219 220 /* For each rmap given, figure out if it matches the key we want. */ 221 STATIC int 222 xfs_rmap_find_left_neighbor_helper( 223 struct xfs_btree_cur *cur, 224 struct xfs_rmap_irec *rec, 225 void *priv) 226 { 227 struct xfs_find_left_neighbor_info *info = priv; 228 229 trace_xfs_rmap_find_left_neighbor_candidate(cur->bc_mp, 230 cur->bc_private.a.agno, rec->rm_startblock, 231 rec->rm_blockcount, rec->rm_owner, rec->rm_offset, 232 rec->rm_flags); 233 234 if (rec->rm_owner != info->high.rm_owner) 235 return XFS_BTREE_QUERY_RANGE_CONTINUE; 236 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) && 237 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) && 238 rec->rm_offset + rec->rm_blockcount - 1 != info->high.rm_offset) 239 return XFS_BTREE_QUERY_RANGE_CONTINUE; 240 241 *info->irec = *rec; 242 *info->stat = 1; 243 return XFS_BTREE_QUERY_RANGE_ABORT; 244 } 245 246 /* 247 * Find the record to the left of the given extent, being careful only to 248 * return a match with the same owner and adjacent physical and logical 249 * block ranges. 250 */ 251 int 252 xfs_rmap_find_left_neighbor( 253 struct xfs_btree_cur *cur, 254 xfs_agblock_t bno, 255 uint64_t owner, 256 uint64_t offset, 257 unsigned int flags, 258 struct xfs_rmap_irec *irec, 259 int *stat) 260 { 261 struct xfs_find_left_neighbor_info info; 262 int error; 263 264 *stat = 0; 265 if (bno == 0) 266 return 0; 267 info.high.rm_startblock = bno - 1; 268 info.high.rm_owner = owner; 269 if (!XFS_RMAP_NON_INODE_OWNER(owner) && 270 !(flags & XFS_RMAP_BMBT_BLOCK)) { 271 if (offset == 0) 272 return 0; 273 info.high.rm_offset = offset - 1; 274 } else 275 info.high.rm_offset = 0; 276 info.high.rm_flags = flags; 277 info.high.rm_blockcount = 0; 278 info.irec = irec; 279 info.stat = stat; 280 281 trace_xfs_rmap_find_left_neighbor_query(cur->bc_mp, 282 cur->bc_private.a.agno, bno, 0, owner, offset, flags); 283 284 error = xfs_rmap_query_range(cur, &info.high, &info.high, 285 xfs_rmap_find_left_neighbor_helper, &info); 286 if (error == XFS_BTREE_QUERY_RANGE_ABORT) 287 error = 0; 288 if (*stat) 289 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp, 290 cur->bc_private.a.agno, irec->rm_startblock, 291 irec->rm_blockcount, irec->rm_owner, 292 irec->rm_offset, irec->rm_flags); 293 return error; 294 } 295 296 /* For each rmap given, figure out if it matches the key we want. */ 297 STATIC int 298 xfs_rmap_lookup_le_range_helper( 299 struct xfs_btree_cur *cur, 300 struct xfs_rmap_irec *rec, 301 void *priv) 302 { 303 struct xfs_find_left_neighbor_info *info = priv; 304 305 trace_xfs_rmap_lookup_le_range_candidate(cur->bc_mp, 306 cur->bc_private.a.agno, rec->rm_startblock, 307 rec->rm_blockcount, rec->rm_owner, rec->rm_offset, 308 rec->rm_flags); 309 310 if (rec->rm_owner != info->high.rm_owner) 311 return XFS_BTREE_QUERY_RANGE_CONTINUE; 312 if (!XFS_RMAP_NON_INODE_OWNER(rec->rm_owner) && 313 !(rec->rm_flags & XFS_RMAP_BMBT_BLOCK) && 314 (rec->rm_offset > info->high.rm_offset || 315 rec->rm_offset + rec->rm_blockcount <= info->high.rm_offset)) 316 return XFS_BTREE_QUERY_RANGE_CONTINUE; 317 318 *info->irec = *rec; 319 *info->stat = 1; 320 return XFS_BTREE_QUERY_RANGE_ABORT; 321 } 322 323 /* 324 * Find the record to the left of the given extent, being careful only to 325 * return a match with the same owner and overlapping physical and logical 326 * block ranges. This is the overlapping-interval version of 327 * xfs_rmap_lookup_le. 328 */ 329 int 330 xfs_rmap_lookup_le_range( 331 struct xfs_btree_cur *cur, 332 xfs_agblock_t bno, 333 uint64_t owner, 334 uint64_t offset, 335 unsigned int flags, 336 struct xfs_rmap_irec *irec, 337 int *stat) 338 { 339 struct xfs_find_left_neighbor_info info; 340 int error; 341 342 info.high.rm_startblock = bno; 343 info.high.rm_owner = owner; 344 if (!XFS_RMAP_NON_INODE_OWNER(owner) && !(flags & XFS_RMAP_BMBT_BLOCK)) 345 info.high.rm_offset = offset; 346 else 347 info.high.rm_offset = 0; 348 info.high.rm_flags = flags; 349 info.high.rm_blockcount = 0; 350 *stat = 0; 351 info.irec = irec; 352 info.stat = stat; 353 354 trace_xfs_rmap_lookup_le_range(cur->bc_mp, 355 cur->bc_private.a.agno, bno, 0, owner, offset, flags); 356 error = xfs_rmap_query_range(cur, &info.high, &info.high, 357 xfs_rmap_lookup_le_range_helper, &info); 358 if (error == XFS_BTREE_QUERY_RANGE_ABORT) 359 error = 0; 360 if (*stat) 361 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 362 cur->bc_private.a.agno, irec->rm_startblock, 363 irec->rm_blockcount, irec->rm_owner, 364 irec->rm_offset, irec->rm_flags); 365 return error; 366 } 367 368 /* 369 * Find the extent in the rmap btree and remove it. 370 * 371 * The record we find should always be an exact match for the extent that we're 372 * looking for, since we insert them into the btree without modification. 373 * 374 * Special Case #1: when growing the filesystem, we "free" an extent when 375 * growing the last AG. This extent is new space and so it is not tracked as 376 * used space in the btree. The growfs code will pass in an owner of 377 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this 378 * extent. We verify that - the extent lookup result in a record that does not 379 * overlap. 380 * 381 * Special Case #2: EFIs do not record the owner of the extent, so when 382 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap 383 * btree to ignore the owner (i.e. wildcard match) so we don't trigger 384 * corruption checks during log recovery. 385 */ 386 STATIC int 387 xfs_rmap_unmap( 388 struct xfs_btree_cur *cur, 389 xfs_agblock_t bno, 390 xfs_extlen_t len, 391 bool unwritten, 392 struct xfs_owner_info *oinfo) 393 { 394 struct xfs_mount *mp = cur->bc_mp; 395 struct xfs_rmap_irec ltrec; 396 uint64_t ltoff; 397 int error = 0; 398 int i; 399 uint64_t owner; 400 uint64_t offset; 401 unsigned int flags; 402 bool ignore_off; 403 404 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 405 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) || 406 (flags & XFS_RMAP_BMBT_BLOCK); 407 if (unwritten) 408 flags |= XFS_RMAP_UNWRITTEN; 409 trace_xfs_rmap_unmap(mp, cur->bc_private.a.agno, bno, len, 410 unwritten, oinfo); 411 412 /* 413 * We should always have a left record because there's a static record 414 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that 415 * will not ever be removed from the tree. 416 */ 417 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags, &i); 418 if (error) 419 goto out_error; 420 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 421 422 error = xfs_rmap_get_rec(cur, <rec, &i); 423 if (error) 424 goto out_error; 425 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 426 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 427 cur->bc_private.a.agno, ltrec.rm_startblock, 428 ltrec.rm_blockcount, ltrec.rm_owner, 429 ltrec.rm_offset, ltrec.rm_flags); 430 ltoff = ltrec.rm_offset; 431 432 /* 433 * For growfs, the incoming extent must be beyond the left record we 434 * just found as it is new space and won't be used by anyone. This is 435 * just a corruption check as we don't actually do anything with this 436 * extent. Note that we need to use >= instead of > because it might 437 * be the case that the "left" extent goes all the way to EOFS. 438 */ 439 if (owner == XFS_RMAP_OWN_NULL) { 440 XFS_WANT_CORRUPTED_GOTO(mp, bno >= ltrec.rm_startblock + 441 ltrec.rm_blockcount, out_error); 442 goto out_done; 443 } 444 445 /* Make sure the unwritten flag matches. */ 446 XFS_WANT_CORRUPTED_GOTO(mp, (flags & XFS_RMAP_UNWRITTEN) == 447 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN), out_error); 448 449 /* Make sure the extent we found covers the entire freeing range. */ 450 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_startblock <= bno && 451 ltrec.rm_startblock + ltrec.rm_blockcount >= 452 bno + len, out_error); 453 454 /* Make sure the owner matches what we expect to find in the tree. */ 455 XFS_WANT_CORRUPTED_GOTO(mp, owner == ltrec.rm_owner || 456 XFS_RMAP_NON_INODE_OWNER(owner), out_error); 457 458 /* Check the offset, if necessary. */ 459 if (!XFS_RMAP_NON_INODE_OWNER(owner)) { 460 if (flags & XFS_RMAP_BMBT_BLOCK) { 461 XFS_WANT_CORRUPTED_GOTO(mp, 462 ltrec.rm_flags & XFS_RMAP_BMBT_BLOCK, 463 out_error); 464 } else { 465 XFS_WANT_CORRUPTED_GOTO(mp, 466 ltrec.rm_offset <= offset, out_error); 467 XFS_WANT_CORRUPTED_GOTO(mp, 468 ltoff + ltrec.rm_blockcount >= offset + len, 469 out_error); 470 } 471 } 472 473 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) { 474 /* exact match, simply remove the record from rmap tree */ 475 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 476 ltrec.rm_startblock, ltrec.rm_blockcount, 477 ltrec.rm_owner, ltrec.rm_offset, 478 ltrec.rm_flags); 479 error = xfs_btree_delete(cur, &i); 480 if (error) 481 goto out_error; 482 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 483 } else if (ltrec.rm_startblock == bno) { 484 /* 485 * overlap left hand side of extent: move the start, trim the 486 * length and update the current record. 487 * 488 * ltbno ltlen 489 * Orig: |oooooooooooooooooooo| 490 * Freeing: |fffffffff| 491 * Result: |rrrrrrrrrr| 492 * bno len 493 */ 494 ltrec.rm_startblock += len; 495 ltrec.rm_blockcount -= len; 496 if (!ignore_off) 497 ltrec.rm_offset += len; 498 error = xfs_rmap_update(cur, <rec); 499 if (error) 500 goto out_error; 501 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) { 502 /* 503 * overlap right hand side of extent: trim the length and update 504 * the current record. 505 * 506 * ltbno ltlen 507 * Orig: |oooooooooooooooooooo| 508 * Freeing: |fffffffff| 509 * Result: |rrrrrrrrrr| 510 * bno len 511 */ 512 ltrec.rm_blockcount -= len; 513 error = xfs_rmap_update(cur, <rec); 514 if (error) 515 goto out_error; 516 } else { 517 518 /* 519 * overlap middle of extent: trim the length of the existing 520 * record to the length of the new left-extent size, increment 521 * the insertion position so we can insert a new record 522 * containing the remaining right-extent space. 523 * 524 * ltbno ltlen 525 * Orig: |oooooooooooooooooooo| 526 * Freeing: |fffffffff| 527 * Result: |rrrrr| |rrrr| 528 * bno len 529 */ 530 xfs_extlen_t orig_len = ltrec.rm_blockcount; 531 532 ltrec.rm_blockcount = bno - ltrec.rm_startblock; 533 error = xfs_rmap_update(cur, <rec); 534 if (error) 535 goto out_error; 536 537 error = xfs_btree_increment(cur, 0, &i); 538 if (error) 539 goto out_error; 540 541 cur->bc_rec.r.rm_startblock = bno + len; 542 cur->bc_rec.r.rm_blockcount = orig_len - len - 543 ltrec.rm_blockcount; 544 cur->bc_rec.r.rm_owner = ltrec.rm_owner; 545 if (ignore_off) 546 cur->bc_rec.r.rm_offset = 0; 547 else 548 cur->bc_rec.r.rm_offset = offset + len; 549 cur->bc_rec.r.rm_flags = flags; 550 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, 551 cur->bc_rec.r.rm_startblock, 552 cur->bc_rec.r.rm_blockcount, 553 cur->bc_rec.r.rm_owner, 554 cur->bc_rec.r.rm_offset, 555 cur->bc_rec.r.rm_flags); 556 error = xfs_btree_insert(cur, &i); 557 if (error) 558 goto out_error; 559 } 560 561 out_done: 562 trace_xfs_rmap_unmap_done(mp, cur->bc_private.a.agno, bno, len, 563 unwritten, oinfo); 564 out_error: 565 if (error) 566 trace_xfs_rmap_unmap_error(mp, cur->bc_private.a.agno, 567 error, _RET_IP_); 568 return error; 569 } 570 571 /* 572 * Remove a reference to an extent in the rmap btree. 573 */ 574 int 575 xfs_rmap_free( 576 struct xfs_trans *tp, 577 struct xfs_buf *agbp, 578 xfs_agnumber_t agno, 579 xfs_agblock_t bno, 580 xfs_extlen_t len, 581 struct xfs_owner_info *oinfo) 582 { 583 struct xfs_mount *mp = tp->t_mountp; 584 struct xfs_btree_cur *cur; 585 int error; 586 587 if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) 588 return 0; 589 590 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno); 591 592 error = xfs_rmap_unmap(cur, bno, len, false, oinfo); 593 if (error) 594 goto out_error; 595 596 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 597 return 0; 598 599 out_error: 600 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 601 return error; 602 } 603 604 /* 605 * A mergeable rmap must have the same owner and the same values for 606 * the unwritten, attr_fork, and bmbt flags. The startblock and 607 * offset are checked separately. 608 */ 609 static bool 610 xfs_rmap_is_mergeable( 611 struct xfs_rmap_irec *irec, 612 uint64_t owner, 613 unsigned int flags) 614 { 615 if (irec->rm_owner == XFS_RMAP_OWN_NULL) 616 return false; 617 if (irec->rm_owner != owner) 618 return false; 619 if ((flags & XFS_RMAP_UNWRITTEN) ^ 620 (irec->rm_flags & XFS_RMAP_UNWRITTEN)) 621 return false; 622 if ((flags & XFS_RMAP_ATTR_FORK) ^ 623 (irec->rm_flags & XFS_RMAP_ATTR_FORK)) 624 return false; 625 if ((flags & XFS_RMAP_BMBT_BLOCK) ^ 626 (irec->rm_flags & XFS_RMAP_BMBT_BLOCK)) 627 return false; 628 return true; 629 } 630 631 /* 632 * When we allocate a new block, the first thing we do is add a reference to 633 * the extent in the rmap btree. This takes the form of a [agbno, length, 634 * owner, offset] record. Flags are encoded in the high bits of the offset 635 * field. 636 */ 637 STATIC int 638 xfs_rmap_map( 639 struct xfs_btree_cur *cur, 640 xfs_agblock_t bno, 641 xfs_extlen_t len, 642 bool unwritten, 643 struct xfs_owner_info *oinfo) 644 { 645 struct xfs_mount *mp = cur->bc_mp; 646 struct xfs_rmap_irec ltrec; 647 struct xfs_rmap_irec gtrec; 648 int have_gt; 649 int have_lt; 650 int error = 0; 651 int i; 652 uint64_t owner; 653 uint64_t offset; 654 unsigned int flags = 0; 655 bool ignore_off; 656 657 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 658 ASSERT(owner != 0); 659 ignore_off = XFS_RMAP_NON_INODE_OWNER(owner) || 660 (flags & XFS_RMAP_BMBT_BLOCK); 661 if (unwritten) 662 flags |= XFS_RMAP_UNWRITTEN; 663 trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len, 664 unwritten, oinfo); 665 666 /* 667 * For the initial lookup, look for an exact match or the left-adjacent 668 * record for our insertion point. This will also give us the record for 669 * start block contiguity tests. 670 */ 671 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, flags, 672 &have_lt); 673 if (error) 674 goto out_error; 675 XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error); 676 677 error = xfs_rmap_get_rec(cur, <rec, &have_lt); 678 if (error) 679 goto out_error; 680 XFS_WANT_CORRUPTED_GOTO(mp, have_lt == 1, out_error); 681 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 682 cur->bc_private.a.agno, ltrec.rm_startblock, 683 ltrec.rm_blockcount, ltrec.rm_owner, 684 ltrec.rm_offset, ltrec.rm_flags); 685 686 if (!xfs_rmap_is_mergeable(<rec, owner, flags)) 687 have_lt = 0; 688 689 XFS_WANT_CORRUPTED_GOTO(mp, 690 have_lt == 0 || 691 ltrec.rm_startblock + ltrec.rm_blockcount <= bno, out_error); 692 693 /* 694 * Increment the cursor to see if we have a right-adjacent record to our 695 * insertion point. This will give us the record for end block 696 * contiguity tests. 697 */ 698 error = xfs_btree_increment(cur, 0, &have_gt); 699 if (error) 700 goto out_error; 701 if (have_gt) { 702 error = xfs_rmap_get_rec(cur, >rec, &have_gt); 703 if (error) 704 goto out_error; 705 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error); 706 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= gtrec.rm_startblock, 707 out_error); 708 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 709 cur->bc_private.a.agno, gtrec.rm_startblock, 710 gtrec.rm_blockcount, gtrec.rm_owner, 711 gtrec.rm_offset, gtrec.rm_flags); 712 if (!xfs_rmap_is_mergeable(>rec, owner, flags)) 713 have_gt = 0; 714 } 715 716 /* 717 * Note: cursor currently points one record to the right of ltrec, even 718 * if there is no record in the tree to the right. 719 */ 720 if (have_lt && 721 ltrec.rm_startblock + ltrec.rm_blockcount == bno && 722 (ignore_off || ltrec.rm_offset + ltrec.rm_blockcount == offset)) { 723 /* 724 * left edge contiguous, merge into left record. 725 * 726 * ltbno ltlen 727 * orig: |ooooooooo| 728 * adding: |aaaaaaaaa| 729 * result: |rrrrrrrrrrrrrrrrrrr| 730 * bno len 731 */ 732 ltrec.rm_blockcount += len; 733 if (have_gt && 734 bno + len == gtrec.rm_startblock && 735 (ignore_off || offset + len == gtrec.rm_offset) && 736 (unsigned long)ltrec.rm_blockcount + len + 737 gtrec.rm_blockcount <= XFS_RMAP_LEN_MAX) { 738 /* 739 * right edge also contiguous, delete right record 740 * and merge into left record. 741 * 742 * ltbno ltlen gtbno gtlen 743 * orig: |ooooooooo| |ooooooooo| 744 * adding: |aaaaaaaaa| 745 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr| 746 */ 747 ltrec.rm_blockcount += gtrec.rm_blockcount; 748 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 749 gtrec.rm_startblock, 750 gtrec.rm_blockcount, 751 gtrec.rm_owner, 752 gtrec.rm_offset, 753 gtrec.rm_flags); 754 error = xfs_btree_delete(cur, &i); 755 if (error) 756 goto out_error; 757 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 758 } 759 760 /* point the cursor back to the left record and update */ 761 error = xfs_btree_decrement(cur, 0, &have_gt); 762 if (error) 763 goto out_error; 764 error = xfs_rmap_update(cur, <rec); 765 if (error) 766 goto out_error; 767 } else if (have_gt && 768 bno + len == gtrec.rm_startblock && 769 (ignore_off || offset + len == gtrec.rm_offset)) { 770 /* 771 * right edge contiguous, merge into right record. 772 * 773 * gtbno gtlen 774 * Orig: |ooooooooo| 775 * adding: |aaaaaaaaa| 776 * Result: |rrrrrrrrrrrrrrrrrrr| 777 * bno len 778 */ 779 gtrec.rm_startblock = bno; 780 gtrec.rm_blockcount += len; 781 if (!ignore_off) 782 gtrec.rm_offset = offset; 783 error = xfs_rmap_update(cur, >rec); 784 if (error) 785 goto out_error; 786 } else { 787 /* 788 * no contiguous edge with identical owner, insert 789 * new record at current cursor position. 790 */ 791 cur->bc_rec.r.rm_startblock = bno; 792 cur->bc_rec.r.rm_blockcount = len; 793 cur->bc_rec.r.rm_owner = owner; 794 cur->bc_rec.r.rm_offset = offset; 795 cur->bc_rec.r.rm_flags = flags; 796 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len, 797 owner, offset, flags); 798 error = xfs_btree_insert(cur, &i); 799 if (error) 800 goto out_error; 801 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 802 } 803 804 trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len, 805 unwritten, oinfo); 806 out_error: 807 if (error) 808 trace_xfs_rmap_map_error(mp, cur->bc_private.a.agno, 809 error, _RET_IP_); 810 return error; 811 } 812 813 /* 814 * Add a reference to an extent in the rmap btree. 815 */ 816 int 817 xfs_rmap_alloc( 818 struct xfs_trans *tp, 819 struct xfs_buf *agbp, 820 xfs_agnumber_t agno, 821 xfs_agblock_t bno, 822 xfs_extlen_t len, 823 struct xfs_owner_info *oinfo) 824 { 825 struct xfs_mount *mp = tp->t_mountp; 826 struct xfs_btree_cur *cur; 827 int error; 828 829 if (!xfs_sb_version_hasrmapbt(&mp->m_sb)) 830 return 0; 831 832 cur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno); 833 error = xfs_rmap_map(cur, bno, len, false, oinfo); 834 if (error) 835 goto out_error; 836 837 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 838 return 0; 839 840 out_error: 841 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 842 return error; 843 } 844 845 #define RMAP_LEFT_CONTIG (1 << 0) 846 #define RMAP_RIGHT_CONTIG (1 << 1) 847 #define RMAP_LEFT_FILLING (1 << 2) 848 #define RMAP_RIGHT_FILLING (1 << 3) 849 #define RMAP_LEFT_VALID (1 << 6) 850 #define RMAP_RIGHT_VALID (1 << 7) 851 852 #define LEFT r[0] 853 #define RIGHT r[1] 854 #define PREV r[2] 855 #define NEW r[3] 856 857 /* 858 * Convert an unwritten extent to a real extent or vice versa. 859 * Does not handle overlapping extents. 860 */ 861 STATIC int 862 xfs_rmap_convert( 863 struct xfs_btree_cur *cur, 864 xfs_agblock_t bno, 865 xfs_extlen_t len, 866 bool unwritten, 867 struct xfs_owner_info *oinfo) 868 { 869 struct xfs_mount *mp = cur->bc_mp; 870 struct xfs_rmap_irec r[4]; /* neighbor extent entries */ 871 /* left is 0, right is 1, prev is 2 */ 872 /* new is 3 */ 873 uint64_t owner; 874 uint64_t offset; 875 uint64_t new_endoff; 876 unsigned int oldext; 877 unsigned int newext; 878 unsigned int flags = 0; 879 int i; 880 int state = 0; 881 int error; 882 883 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 884 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) || 885 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK)))); 886 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0; 887 new_endoff = offset + len; 888 trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len, 889 unwritten, oinfo); 890 891 /* 892 * For the initial lookup, look for an exact match or the left-adjacent 893 * record for our insertion point. This will also give us the record for 894 * start block contiguity tests. 895 */ 896 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i); 897 if (error) 898 goto done; 899 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 900 901 error = xfs_rmap_get_rec(cur, &PREV, &i); 902 if (error) 903 goto done; 904 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 905 trace_xfs_rmap_lookup_le_range_result(cur->bc_mp, 906 cur->bc_private.a.agno, PREV.rm_startblock, 907 PREV.rm_blockcount, PREV.rm_owner, 908 PREV.rm_offset, PREV.rm_flags); 909 910 ASSERT(PREV.rm_offset <= offset); 911 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff); 912 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext); 913 newext = ~oldext & XFS_RMAP_UNWRITTEN; 914 915 /* 916 * Set flags determining what part of the previous oldext allocation 917 * extent is being replaced by a newext allocation. 918 */ 919 if (PREV.rm_offset == offset) 920 state |= RMAP_LEFT_FILLING; 921 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff) 922 state |= RMAP_RIGHT_FILLING; 923 924 /* 925 * Decrement the cursor to see if we have a left-adjacent record to our 926 * insertion point. This will give us the record for end block 927 * contiguity tests. 928 */ 929 error = xfs_btree_decrement(cur, 0, &i); 930 if (error) 931 goto done; 932 if (i) { 933 state |= RMAP_LEFT_VALID; 934 error = xfs_rmap_get_rec(cur, &LEFT, &i); 935 if (error) 936 goto done; 937 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 938 XFS_WANT_CORRUPTED_GOTO(mp, 939 LEFT.rm_startblock + LEFT.rm_blockcount <= bno, 940 done); 941 trace_xfs_rmap_find_left_neighbor_result(cur->bc_mp, 942 cur->bc_private.a.agno, LEFT.rm_startblock, 943 LEFT.rm_blockcount, LEFT.rm_owner, 944 LEFT.rm_offset, LEFT.rm_flags); 945 if (LEFT.rm_startblock + LEFT.rm_blockcount == bno && 946 LEFT.rm_offset + LEFT.rm_blockcount == offset && 947 xfs_rmap_is_mergeable(&LEFT, owner, newext)) 948 state |= RMAP_LEFT_CONTIG; 949 } 950 951 /* 952 * Increment the cursor to see if we have a right-adjacent record to our 953 * insertion point. This will give us the record for end block 954 * contiguity tests. 955 */ 956 error = xfs_btree_increment(cur, 0, &i); 957 if (error) 958 goto done; 959 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 960 error = xfs_btree_increment(cur, 0, &i); 961 if (error) 962 goto done; 963 if (i) { 964 state |= RMAP_RIGHT_VALID; 965 error = xfs_rmap_get_rec(cur, &RIGHT, &i); 966 if (error) 967 goto done; 968 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 969 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock, 970 done); 971 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 972 cur->bc_private.a.agno, RIGHT.rm_startblock, 973 RIGHT.rm_blockcount, RIGHT.rm_owner, 974 RIGHT.rm_offset, RIGHT.rm_flags); 975 if (bno + len == RIGHT.rm_startblock && 976 offset + len == RIGHT.rm_offset && 977 xfs_rmap_is_mergeable(&RIGHT, owner, newext)) 978 state |= RMAP_RIGHT_CONTIG; 979 } 980 981 /* check that left + prev + right is not too long */ 982 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 983 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) == 984 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 985 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) && 986 (unsigned long)LEFT.rm_blockcount + len + 987 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX) 988 state &= ~RMAP_RIGHT_CONTIG; 989 990 trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state, 991 _RET_IP_); 992 993 /* reset the cursor back to PREV */ 994 error = xfs_rmap_lookup_le(cur, bno, len, owner, offset, oldext, &i); 995 if (error) 996 goto done; 997 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 998 999 /* 1000 * Switch out based on the FILLING and CONTIG state bits. 1001 */ 1002 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1003 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) { 1004 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1005 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1006 /* 1007 * Setting all of a previous oldext extent to newext. 1008 * The left and right neighbors are both contiguous with new. 1009 */ 1010 error = xfs_btree_increment(cur, 0, &i); 1011 if (error) 1012 goto done; 1013 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1014 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 1015 RIGHT.rm_startblock, RIGHT.rm_blockcount, 1016 RIGHT.rm_owner, RIGHT.rm_offset, 1017 RIGHT.rm_flags); 1018 error = xfs_btree_delete(cur, &i); 1019 if (error) 1020 goto done; 1021 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1022 error = xfs_btree_decrement(cur, 0, &i); 1023 if (error) 1024 goto done; 1025 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1026 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 1027 PREV.rm_startblock, PREV.rm_blockcount, 1028 PREV.rm_owner, PREV.rm_offset, 1029 PREV.rm_flags); 1030 error = xfs_btree_delete(cur, &i); 1031 if (error) 1032 goto done; 1033 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1034 error = xfs_btree_decrement(cur, 0, &i); 1035 if (error) 1036 goto done; 1037 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1038 NEW = LEFT; 1039 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount; 1040 error = xfs_rmap_update(cur, &NEW); 1041 if (error) 1042 goto done; 1043 break; 1044 1045 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1046 /* 1047 * Setting all of a previous oldext extent to newext. 1048 * The left neighbor is contiguous, the right is not. 1049 */ 1050 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 1051 PREV.rm_startblock, PREV.rm_blockcount, 1052 PREV.rm_owner, PREV.rm_offset, 1053 PREV.rm_flags); 1054 error = xfs_btree_delete(cur, &i); 1055 if (error) 1056 goto done; 1057 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1058 error = xfs_btree_decrement(cur, 0, &i); 1059 if (error) 1060 goto done; 1061 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1062 NEW = LEFT; 1063 NEW.rm_blockcount += PREV.rm_blockcount; 1064 error = xfs_rmap_update(cur, &NEW); 1065 if (error) 1066 goto done; 1067 break; 1068 1069 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1070 /* 1071 * Setting all of a previous oldext extent to newext. 1072 * The right neighbor is contiguous, the left is not. 1073 */ 1074 error = xfs_btree_increment(cur, 0, &i); 1075 if (error) 1076 goto done; 1077 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1078 trace_xfs_rmap_delete(mp, cur->bc_private.a.agno, 1079 RIGHT.rm_startblock, RIGHT.rm_blockcount, 1080 RIGHT.rm_owner, RIGHT.rm_offset, 1081 RIGHT.rm_flags); 1082 error = xfs_btree_delete(cur, &i); 1083 if (error) 1084 goto done; 1085 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1086 error = xfs_btree_decrement(cur, 0, &i); 1087 if (error) 1088 goto done; 1089 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1090 NEW = PREV; 1091 NEW.rm_blockcount = len + RIGHT.rm_blockcount; 1092 NEW.rm_flags = newext; 1093 error = xfs_rmap_update(cur, &NEW); 1094 if (error) 1095 goto done; 1096 break; 1097 1098 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING: 1099 /* 1100 * Setting all of a previous oldext extent to newext. 1101 * Neither the left nor right neighbors are contiguous with 1102 * the new one. 1103 */ 1104 NEW = PREV; 1105 NEW.rm_flags = newext; 1106 error = xfs_rmap_update(cur, &NEW); 1107 if (error) 1108 goto done; 1109 break; 1110 1111 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG: 1112 /* 1113 * Setting the first part of a previous oldext extent to newext. 1114 * The left neighbor is contiguous. 1115 */ 1116 NEW = PREV; 1117 NEW.rm_offset += len; 1118 NEW.rm_startblock += len; 1119 NEW.rm_blockcount -= len; 1120 error = xfs_rmap_update(cur, &NEW); 1121 if (error) 1122 goto done; 1123 error = xfs_btree_decrement(cur, 0, &i); 1124 if (error) 1125 goto done; 1126 NEW = LEFT; 1127 NEW.rm_blockcount += len; 1128 error = xfs_rmap_update(cur, &NEW); 1129 if (error) 1130 goto done; 1131 break; 1132 1133 case RMAP_LEFT_FILLING: 1134 /* 1135 * Setting the first part of a previous oldext extent to newext. 1136 * The left neighbor is not contiguous. 1137 */ 1138 NEW = PREV; 1139 NEW.rm_startblock += len; 1140 NEW.rm_offset += len; 1141 NEW.rm_blockcount -= len; 1142 error = xfs_rmap_update(cur, &NEW); 1143 if (error) 1144 goto done; 1145 NEW.rm_startblock = bno; 1146 NEW.rm_owner = owner; 1147 NEW.rm_offset = offset; 1148 NEW.rm_blockcount = len; 1149 NEW.rm_flags = newext; 1150 cur->bc_rec.r = NEW; 1151 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, 1152 len, owner, offset, newext); 1153 error = xfs_btree_insert(cur, &i); 1154 if (error) 1155 goto done; 1156 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1157 break; 1158 1159 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1160 /* 1161 * Setting the last part of a previous oldext extent to newext. 1162 * The right neighbor is contiguous with the new allocation. 1163 */ 1164 NEW = PREV; 1165 NEW.rm_blockcount -= len; 1166 error = xfs_rmap_update(cur, &NEW); 1167 if (error) 1168 goto done; 1169 error = xfs_btree_increment(cur, 0, &i); 1170 if (error) 1171 goto done; 1172 NEW = RIGHT; 1173 NEW.rm_offset = offset; 1174 NEW.rm_startblock = bno; 1175 NEW.rm_blockcount += len; 1176 error = xfs_rmap_update(cur, &NEW); 1177 if (error) 1178 goto done; 1179 break; 1180 1181 case RMAP_RIGHT_FILLING: 1182 /* 1183 * Setting the last part of a previous oldext extent to newext. 1184 * The right neighbor is not contiguous. 1185 */ 1186 NEW = PREV; 1187 NEW.rm_blockcount -= len; 1188 error = xfs_rmap_update(cur, &NEW); 1189 if (error) 1190 goto done; 1191 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, 1192 oldext, &i); 1193 if (error) 1194 goto done; 1195 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done); 1196 NEW.rm_startblock = bno; 1197 NEW.rm_owner = owner; 1198 NEW.rm_offset = offset; 1199 NEW.rm_blockcount = len; 1200 NEW.rm_flags = newext; 1201 cur->bc_rec.r = NEW; 1202 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, 1203 len, owner, offset, newext); 1204 error = xfs_btree_insert(cur, &i); 1205 if (error) 1206 goto done; 1207 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1208 break; 1209 1210 case 0: 1211 /* 1212 * Setting the middle part of a previous oldext extent to 1213 * newext. Contiguity is impossible here. 1214 * One extent becomes three extents. 1215 */ 1216 /* new right extent - oldext */ 1217 NEW.rm_startblock = bno + len; 1218 NEW.rm_owner = owner; 1219 NEW.rm_offset = new_endoff; 1220 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount - 1221 new_endoff; 1222 NEW.rm_flags = PREV.rm_flags; 1223 error = xfs_rmap_update(cur, &NEW); 1224 if (error) 1225 goto done; 1226 /* new left extent - oldext */ 1227 NEW = PREV; 1228 NEW.rm_blockcount = offset - PREV.rm_offset; 1229 cur->bc_rec.r = NEW; 1230 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, 1231 NEW.rm_startblock, NEW.rm_blockcount, 1232 NEW.rm_owner, NEW.rm_offset, 1233 NEW.rm_flags); 1234 error = xfs_btree_insert(cur, &i); 1235 if (error) 1236 goto done; 1237 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1238 /* 1239 * Reset the cursor to the position of the new extent 1240 * we are about to insert as we can't trust it after 1241 * the previous insert. 1242 */ 1243 error = xfs_rmap_lookup_eq(cur, bno, len, owner, offset, 1244 oldext, &i); 1245 if (error) 1246 goto done; 1247 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, done); 1248 /* new middle extent - newext */ 1249 cur->bc_rec.r.rm_flags &= ~XFS_RMAP_UNWRITTEN; 1250 cur->bc_rec.r.rm_flags |= newext; 1251 trace_xfs_rmap_insert(mp, cur->bc_private.a.agno, bno, len, 1252 owner, offset, newext); 1253 error = xfs_btree_insert(cur, &i); 1254 if (error) 1255 goto done; 1256 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1257 break; 1258 1259 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1260 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1261 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG: 1262 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1263 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1264 case RMAP_LEFT_CONTIG: 1265 case RMAP_RIGHT_CONTIG: 1266 /* 1267 * These cases are all impossible. 1268 */ 1269 ASSERT(0); 1270 } 1271 1272 trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len, 1273 unwritten, oinfo); 1274 done: 1275 if (error) 1276 trace_xfs_rmap_convert_error(cur->bc_mp, 1277 cur->bc_private.a.agno, error, _RET_IP_); 1278 return error; 1279 } 1280 1281 /* 1282 * Convert an unwritten extent to a real extent or vice versa. If there is no 1283 * possibility of overlapping extents, delegate to the simpler convert 1284 * function. 1285 */ 1286 STATIC int 1287 xfs_rmap_convert_shared( 1288 struct xfs_btree_cur *cur, 1289 xfs_agblock_t bno, 1290 xfs_extlen_t len, 1291 bool unwritten, 1292 struct xfs_owner_info *oinfo) 1293 { 1294 struct xfs_mount *mp = cur->bc_mp; 1295 struct xfs_rmap_irec r[4]; /* neighbor extent entries */ 1296 /* left is 0, right is 1, prev is 2 */ 1297 /* new is 3 */ 1298 uint64_t owner; 1299 uint64_t offset; 1300 uint64_t new_endoff; 1301 unsigned int oldext; 1302 unsigned int newext; 1303 unsigned int flags = 0; 1304 int i; 1305 int state = 0; 1306 int error; 1307 1308 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 1309 ASSERT(!(XFS_RMAP_NON_INODE_OWNER(owner) || 1310 (flags & (XFS_RMAP_ATTR_FORK | XFS_RMAP_BMBT_BLOCK)))); 1311 oldext = unwritten ? XFS_RMAP_UNWRITTEN : 0; 1312 new_endoff = offset + len; 1313 trace_xfs_rmap_convert(mp, cur->bc_private.a.agno, bno, len, 1314 unwritten, oinfo); 1315 1316 /* 1317 * For the initial lookup, look for and exact match or the left-adjacent 1318 * record for our insertion point. This will also give us the record for 1319 * start block contiguity tests. 1320 */ 1321 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags, 1322 &PREV, &i); 1323 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1324 1325 ASSERT(PREV.rm_offset <= offset); 1326 ASSERT(PREV.rm_offset + PREV.rm_blockcount >= new_endoff); 1327 ASSERT((PREV.rm_flags & XFS_RMAP_UNWRITTEN) == oldext); 1328 newext = ~oldext & XFS_RMAP_UNWRITTEN; 1329 1330 /* 1331 * Set flags determining what part of the previous oldext allocation 1332 * extent is being replaced by a newext allocation. 1333 */ 1334 if (PREV.rm_offset == offset) 1335 state |= RMAP_LEFT_FILLING; 1336 if (PREV.rm_offset + PREV.rm_blockcount == new_endoff) 1337 state |= RMAP_RIGHT_FILLING; 1338 1339 /* Is there a left record that abuts our range? */ 1340 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, newext, 1341 &LEFT, &i); 1342 if (error) 1343 goto done; 1344 if (i) { 1345 state |= RMAP_LEFT_VALID; 1346 XFS_WANT_CORRUPTED_GOTO(mp, 1347 LEFT.rm_startblock + LEFT.rm_blockcount <= bno, 1348 done); 1349 if (xfs_rmap_is_mergeable(&LEFT, owner, newext)) 1350 state |= RMAP_LEFT_CONTIG; 1351 } 1352 1353 /* Is there a right record that abuts our range? */ 1354 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len, 1355 newext, &i); 1356 if (error) 1357 goto done; 1358 if (i) { 1359 state |= RMAP_RIGHT_VALID; 1360 error = xfs_rmap_get_rec(cur, &RIGHT, &i); 1361 if (error) 1362 goto done; 1363 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1364 XFS_WANT_CORRUPTED_GOTO(mp, bno + len <= RIGHT.rm_startblock, 1365 done); 1366 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 1367 cur->bc_private.a.agno, RIGHT.rm_startblock, 1368 RIGHT.rm_blockcount, RIGHT.rm_owner, 1369 RIGHT.rm_offset, RIGHT.rm_flags); 1370 if (xfs_rmap_is_mergeable(&RIGHT, owner, newext)) 1371 state |= RMAP_RIGHT_CONTIG; 1372 } 1373 1374 /* check that left + prev + right is not too long */ 1375 if ((state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1376 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) == 1377 (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1378 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG) && 1379 (unsigned long)LEFT.rm_blockcount + len + 1380 RIGHT.rm_blockcount > XFS_RMAP_LEN_MAX) 1381 state &= ~RMAP_RIGHT_CONTIG; 1382 1383 trace_xfs_rmap_convert_state(mp, cur->bc_private.a.agno, state, 1384 _RET_IP_); 1385 /* 1386 * Switch out based on the FILLING and CONTIG state bits. 1387 */ 1388 switch (state & (RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1389 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG)) { 1390 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | 1391 RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1392 /* 1393 * Setting all of a previous oldext extent to newext. 1394 * The left and right neighbors are both contiguous with new. 1395 */ 1396 error = xfs_rmap_delete(cur, RIGHT.rm_startblock, 1397 RIGHT.rm_blockcount, RIGHT.rm_owner, 1398 RIGHT.rm_offset, RIGHT.rm_flags); 1399 if (error) 1400 goto done; 1401 error = xfs_rmap_delete(cur, PREV.rm_startblock, 1402 PREV.rm_blockcount, PREV.rm_owner, 1403 PREV.rm_offset, PREV.rm_flags); 1404 if (error) 1405 goto done; 1406 NEW = LEFT; 1407 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1408 NEW.rm_blockcount, NEW.rm_owner, 1409 NEW.rm_offset, NEW.rm_flags, &i); 1410 if (error) 1411 goto done; 1412 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1413 NEW.rm_blockcount += PREV.rm_blockcount + RIGHT.rm_blockcount; 1414 error = xfs_rmap_update(cur, &NEW); 1415 if (error) 1416 goto done; 1417 break; 1418 1419 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1420 /* 1421 * Setting all of a previous oldext extent to newext. 1422 * The left neighbor is contiguous, the right is not. 1423 */ 1424 error = xfs_rmap_delete(cur, PREV.rm_startblock, 1425 PREV.rm_blockcount, PREV.rm_owner, 1426 PREV.rm_offset, PREV.rm_flags); 1427 if (error) 1428 goto done; 1429 NEW = LEFT; 1430 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1431 NEW.rm_blockcount, NEW.rm_owner, 1432 NEW.rm_offset, NEW.rm_flags, &i); 1433 if (error) 1434 goto done; 1435 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1436 NEW.rm_blockcount += PREV.rm_blockcount; 1437 error = xfs_rmap_update(cur, &NEW); 1438 if (error) 1439 goto done; 1440 break; 1441 1442 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1443 /* 1444 * Setting all of a previous oldext extent to newext. 1445 * The right neighbor is contiguous, the left is not. 1446 */ 1447 error = xfs_rmap_delete(cur, RIGHT.rm_startblock, 1448 RIGHT.rm_blockcount, RIGHT.rm_owner, 1449 RIGHT.rm_offset, RIGHT.rm_flags); 1450 if (error) 1451 goto done; 1452 NEW = PREV; 1453 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1454 NEW.rm_blockcount, NEW.rm_owner, 1455 NEW.rm_offset, NEW.rm_flags, &i); 1456 if (error) 1457 goto done; 1458 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1459 NEW.rm_blockcount += RIGHT.rm_blockcount; 1460 NEW.rm_flags = RIGHT.rm_flags; 1461 error = xfs_rmap_update(cur, &NEW); 1462 if (error) 1463 goto done; 1464 break; 1465 1466 case RMAP_LEFT_FILLING | RMAP_RIGHT_FILLING: 1467 /* 1468 * Setting all of a previous oldext extent to newext. 1469 * Neither the left nor right neighbors are contiguous with 1470 * the new one. 1471 */ 1472 NEW = PREV; 1473 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1474 NEW.rm_blockcount, NEW.rm_owner, 1475 NEW.rm_offset, NEW.rm_flags, &i); 1476 if (error) 1477 goto done; 1478 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1479 NEW.rm_flags = newext; 1480 error = xfs_rmap_update(cur, &NEW); 1481 if (error) 1482 goto done; 1483 break; 1484 1485 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG: 1486 /* 1487 * Setting the first part of a previous oldext extent to newext. 1488 * The left neighbor is contiguous. 1489 */ 1490 NEW = PREV; 1491 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1492 NEW.rm_blockcount, NEW.rm_owner, 1493 NEW.rm_offset, NEW.rm_flags); 1494 if (error) 1495 goto done; 1496 NEW.rm_offset += len; 1497 NEW.rm_startblock += len; 1498 NEW.rm_blockcount -= len; 1499 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1500 NEW.rm_blockcount, NEW.rm_owner, 1501 NEW.rm_offset, NEW.rm_flags); 1502 if (error) 1503 goto done; 1504 NEW = LEFT; 1505 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1506 NEW.rm_blockcount, NEW.rm_owner, 1507 NEW.rm_offset, NEW.rm_flags, &i); 1508 if (error) 1509 goto done; 1510 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1511 NEW.rm_blockcount += len; 1512 error = xfs_rmap_update(cur, &NEW); 1513 if (error) 1514 goto done; 1515 break; 1516 1517 case RMAP_LEFT_FILLING: 1518 /* 1519 * Setting the first part of a previous oldext extent to newext. 1520 * The left neighbor is not contiguous. 1521 */ 1522 NEW = PREV; 1523 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1524 NEW.rm_blockcount, NEW.rm_owner, 1525 NEW.rm_offset, NEW.rm_flags); 1526 if (error) 1527 goto done; 1528 NEW.rm_offset += len; 1529 NEW.rm_startblock += len; 1530 NEW.rm_blockcount -= len; 1531 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1532 NEW.rm_blockcount, NEW.rm_owner, 1533 NEW.rm_offset, NEW.rm_flags); 1534 if (error) 1535 goto done; 1536 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext); 1537 if (error) 1538 goto done; 1539 break; 1540 1541 case RMAP_RIGHT_FILLING | RMAP_RIGHT_CONTIG: 1542 /* 1543 * Setting the last part of a previous oldext extent to newext. 1544 * The right neighbor is contiguous with the new allocation. 1545 */ 1546 NEW = PREV; 1547 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1548 NEW.rm_blockcount, NEW.rm_owner, 1549 NEW.rm_offset, NEW.rm_flags, &i); 1550 if (error) 1551 goto done; 1552 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1553 NEW.rm_blockcount = offset - NEW.rm_offset; 1554 error = xfs_rmap_update(cur, &NEW); 1555 if (error) 1556 goto done; 1557 NEW = RIGHT; 1558 error = xfs_rmap_delete(cur, NEW.rm_startblock, 1559 NEW.rm_blockcount, NEW.rm_owner, 1560 NEW.rm_offset, NEW.rm_flags); 1561 if (error) 1562 goto done; 1563 NEW.rm_offset = offset; 1564 NEW.rm_startblock = bno; 1565 NEW.rm_blockcount += len; 1566 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1567 NEW.rm_blockcount, NEW.rm_owner, 1568 NEW.rm_offset, NEW.rm_flags); 1569 if (error) 1570 goto done; 1571 break; 1572 1573 case RMAP_RIGHT_FILLING: 1574 /* 1575 * Setting the last part of a previous oldext extent to newext. 1576 * The right neighbor is not contiguous. 1577 */ 1578 NEW = PREV; 1579 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1580 NEW.rm_blockcount, NEW.rm_owner, 1581 NEW.rm_offset, NEW.rm_flags, &i); 1582 if (error) 1583 goto done; 1584 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1585 NEW.rm_blockcount -= len; 1586 error = xfs_rmap_update(cur, &NEW); 1587 if (error) 1588 goto done; 1589 error = xfs_rmap_insert(cur, bno, len, owner, offset, newext); 1590 if (error) 1591 goto done; 1592 break; 1593 1594 case 0: 1595 /* 1596 * Setting the middle part of a previous oldext extent to 1597 * newext. Contiguity is impossible here. 1598 * One extent becomes three extents. 1599 */ 1600 /* new right extent - oldext */ 1601 NEW.rm_startblock = bno + len; 1602 NEW.rm_owner = owner; 1603 NEW.rm_offset = new_endoff; 1604 NEW.rm_blockcount = PREV.rm_offset + PREV.rm_blockcount - 1605 new_endoff; 1606 NEW.rm_flags = PREV.rm_flags; 1607 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1608 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset, 1609 NEW.rm_flags); 1610 if (error) 1611 goto done; 1612 /* new left extent - oldext */ 1613 NEW = PREV; 1614 error = xfs_rmap_lookup_eq(cur, NEW.rm_startblock, 1615 NEW.rm_blockcount, NEW.rm_owner, 1616 NEW.rm_offset, NEW.rm_flags, &i); 1617 if (error) 1618 goto done; 1619 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, done); 1620 NEW.rm_blockcount = offset - NEW.rm_offset; 1621 error = xfs_rmap_update(cur, &NEW); 1622 if (error) 1623 goto done; 1624 /* new middle extent - newext */ 1625 NEW.rm_startblock = bno; 1626 NEW.rm_blockcount = len; 1627 NEW.rm_owner = owner; 1628 NEW.rm_offset = offset; 1629 NEW.rm_flags = newext; 1630 error = xfs_rmap_insert(cur, NEW.rm_startblock, 1631 NEW.rm_blockcount, NEW.rm_owner, NEW.rm_offset, 1632 NEW.rm_flags); 1633 if (error) 1634 goto done; 1635 break; 1636 1637 case RMAP_LEFT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1638 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1639 case RMAP_LEFT_FILLING | RMAP_RIGHT_CONTIG: 1640 case RMAP_RIGHT_FILLING | RMAP_LEFT_CONTIG: 1641 case RMAP_LEFT_CONTIG | RMAP_RIGHT_CONTIG: 1642 case RMAP_LEFT_CONTIG: 1643 case RMAP_RIGHT_CONTIG: 1644 /* 1645 * These cases are all impossible. 1646 */ 1647 ASSERT(0); 1648 } 1649 1650 trace_xfs_rmap_convert_done(mp, cur->bc_private.a.agno, bno, len, 1651 unwritten, oinfo); 1652 done: 1653 if (error) 1654 trace_xfs_rmap_convert_error(cur->bc_mp, 1655 cur->bc_private.a.agno, error, _RET_IP_); 1656 return error; 1657 } 1658 1659 #undef NEW 1660 #undef LEFT 1661 #undef RIGHT 1662 #undef PREV 1663 1664 /* 1665 * Find an extent in the rmap btree and unmap it. For rmap extent types that 1666 * can overlap (data fork rmaps on reflink filesystems) we must be careful 1667 * that the prev/next records in the btree might belong to another owner. 1668 * Therefore we must use delete+insert to alter any of the key fields. 1669 * 1670 * For every other situation there can only be one owner for a given extent, 1671 * so we can call the regular _free function. 1672 */ 1673 STATIC int 1674 xfs_rmap_unmap_shared( 1675 struct xfs_btree_cur *cur, 1676 xfs_agblock_t bno, 1677 xfs_extlen_t len, 1678 bool unwritten, 1679 struct xfs_owner_info *oinfo) 1680 { 1681 struct xfs_mount *mp = cur->bc_mp; 1682 struct xfs_rmap_irec ltrec; 1683 uint64_t ltoff; 1684 int error = 0; 1685 int i; 1686 uint64_t owner; 1687 uint64_t offset; 1688 unsigned int flags; 1689 1690 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 1691 if (unwritten) 1692 flags |= XFS_RMAP_UNWRITTEN; 1693 trace_xfs_rmap_unmap(mp, cur->bc_private.a.agno, bno, len, 1694 unwritten, oinfo); 1695 1696 /* 1697 * We should always have a left record because there's a static record 1698 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that 1699 * will not ever be removed from the tree. 1700 */ 1701 error = xfs_rmap_lookup_le_range(cur, bno, owner, offset, flags, 1702 <rec, &i); 1703 if (error) 1704 goto out_error; 1705 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 1706 ltoff = ltrec.rm_offset; 1707 1708 /* Make sure the extent we found covers the entire freeing range. */ 1709 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_startblock <= bno && 1710 ltrec.rm_startblock + ltrec.rm_blockcount >= 1711 bno + len, out_error); 1712 1713 /* Make sure the owner matches what we expect to find in the tree. */ 1714 XFS_WANT_CORRUPTED_GOTO(mp, owner == ltrec.rm_owner, out_error); 1715 1716 /* Make sure the unwritten flag matches. */ 1717 XFS_WANT_CORRUPTED_GOTO(mp, (flags & XFS_RMAP_UNWRITTEN) == 1718 (ltrec.rm_flags & XFS_RMAP_UNWRITTEN), out_error); 1719 1720 /* Check the offset. */ 1721 XFS_WANT_CORRUPTED_GOTO(mp, ltrec.rm_offset <= offset, out_error); 1722 XFS_WANT_CORRUPTED_GOTO(mp, offset <= ltoff + ltrec.rm_blockcount, 1723 out_error); 1724 1725 if (ltrec.rm_startblock == bno && ltrec.rm_blockcount == len) { 1726 /* Exact match, simply remove the record from rmap tree. */ 1727 error = xfs_rmap_delete(cur, ltrec.rm_startblock, 1728 ltrec.rm_blockcount, ltrec.rm_owner, 1729 ltrec.rm_offset, ltrec.rm_flags); 1730 if (error) 1731 goto out_error; 1732 } else if (ltrec.rm_startblock == bno) { 1733 /* 1734 * Overlap left hand side of extent: move the start, trim the 1735 * length and update the current record. 1736 * 1737 * ltbno ltlen 1738 * Orig: |oooooooooooooooooooo| 1739 * Freeing: |fffffffff| 1740 * Result: |rrrrrrrrrr| 1741 * bno len 1742 */ 1743 1744 /* Delete prev rmap. */ 1745 error = xfs_rmap_delete(cur, ltrec.rm_startblock, 1746 ltrec.rm_blockcount, ltrec.rm_owner, 1747 ltrec.rm_offset, ltrec.rm_flags); 1748 if (error) 1749 goto out_error; 1750 1751 /* Add an rmap at the new offset. */ 1752 ltrec.rm_startblock += len; 1753 ltrec.rm_blockcount -= len; 1754 ltrec.rm_offset += len; 1755 error = xfs_rmap_insert(cur, ltrec.rm_startblock, 1756 ltrec.rm_blockcount, ltrec.rm_owner, 1757 ltrec.rm_offset, ltrec.rm_flags); 1758 if (error) 1759 goto out_error; 1760 } else if (ltrec.rm_startblock + ltrec.rm_blockcount == bno + len) { 1761 /* 1762 * Overlap right hand side of extent: trim the length and 1763 * update the current record. 1764 * 1765 * ltbno ltlen 1766 * Orig: |oooooooooooooooooooo| 1767 * Freeing: |fffffffff| 1768 * Result: |rrrrrrrrrr| 1769 * bno len 1770 */ 1771 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 1772 ltrec.rm_blockcount, ltrec.rm_owner, 1773 ltrec.rm_offset, ltrec.rm_flags, &i); 1774 if (error) 1775 goto out_error; 1776 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 1777 ltrec.rm_blockcount -= len; 1778 error = xfs_rmap_update(cur, <rec); 1779 if (error) 1780 goto out_error; 1781 } else { 1782 /* 1783 * Overlap middle of extent: trim the length of the existing 1784 * record to the length of the new left-extent size, increment 1785 * the insertion position so we can insert a new record 1786 * containing the remaining right-extent space. 1787 * 1788 * ltbno ltlen 1789 * Orig: |oooooooooooooooooooo| 1790 * Freeing: |fffffffff| 1791 * Result: |rrrrr| |rrrr| 1792 * bno len 1793 */ 1794 xfs_extlen_t orig_len = ltrec.rm_blockcount; 1795 1796 /* Shrink the left side of the rmap */ 1797 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 1798 ltrec.rm_blockcount, ltrec.rm_owner, 1799 ltrec.rm_offset, ltrec.rm_flags, &i); 1800 if (error) 1801 goto out_error; 1802 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 1803 ltrec.rm_blockcount = bno - ltrec.rm_startblock; 1804 error = xfs_rmap_update(cur, <rec); 1805 if (error) 1806 goto out_error; 1807 1808 /* Add an rmap at the new offset */ 1809 error = xfs_rmap_insert(cur, bno + len, 1810 orig_len - len - ltrec.rm_blockcount, 1811 ltrec.rm_owner, offset + len, 1812 ltrec.rm_flags); 1813 if (error) 1814 goto out_error; 1815 } 1816 1817 trace_xfs_rmap_unmap_done(mp, cur->bc_private.a.agno, bno, len, 1818 unwritten, oinfo); 1819 out_error: 1820 if (error) 1821 trace_xfs_rmap_unmap_error(cur->bc_mp, 1822 cur->bc_private.a.agno, error, _RET_IP_); 1823 return error; 1824 } 1825 1826 /* 1827 * Find an extent in the rmap btree and map it. For rmap extent types that 1828 * can overlap (data fork rmaps on reflink filesystems) we must be careful 1829 * that the prev/next records in the btree might belong to another owner. 1830 * Therefore we must use delete+insert to alter any of the key fields. 1831 * 1832 * For every other situation there can only be one owner for a given extent, 1833 * so we can call the regular _alloc function. 1834 */ 1835 STATIC int 1836 xfs_rmap_map_shared( 1837 struct xfs_btree_cur *cur, 1838 xfs_agblock_t bno, 1839 xfs_extlen_t len, 1840 bool unwritten, 1841 struct xfs_owner_info *oinfo) 1842 { 1843 struct xfs_mount *mp = cur->bc_mp; 1844 struct xfs_rmap_irec ltrec; 1845 struct xfs_rmap_irec gtrec; 1846 int have_gt; 1847 int have_lt; 1848 int error = 0; 1849 int i; 1850 uint64_t owner; 1851 uint64_t offset; 1852 unsigned int flags = 0; 1853 1854 xfs_owner_info_unpack(oinfo, &owner, &offset, &flags); 1855 if (unwritten) 1856 flags |= XFS_RMAP_UNWRITTEN; 1857 trace_xfs_rmap_map(mp, cur->bc_private.a.agno, bno, len, 1858 unwritten, oinfo); 1859 1860 /* Is there a left record that abuts our range? */ 1861 error = xfs_rmap_find_left_neighbor(cur, bno, owner, offset, flags, 1862 <rec, &have_lt); 1863 if (error) 1864 goto out_error; 1865 if (have_lt && 1866 !xfs_rmap_is_mergeable(<rec, owner, flags)) 1867 have_lt = 0; 1868 1869 /* Is there a right record that abuts our range? */ 1870 error = xfs_rmap_lookup_eq(cur, bno + len, len, owner, offset + len, 1871 flags, &have_gt); 1872 if (error) 1873 goto out_error; 1874 if (have_gt) { 1875 error = xfs_rmap_get_rec(cur, >rec, &have_gt); 1876 if (error) 1877 goto out_error; 1878 XFS_WANT_CORRUPTED_GOTO(mp, have_gt == 1, out_error); 1879 trace_xfs_rmap_find_right_neighbor_result(cur->bc_mp, 1880 cur->bc_private.a.agno, gtrec.rm_startblock, 1881 gtrec.rm_blockcount, gtrec.rm_owner, 1882 gtrec.rm_offset, gtrec.rm_flags); 1883 1884 if (!xfs_rmap_is_mergeable(>rec, owner, flags)) 1885 have_gt = 0; 1886 } 1887 1888 if (have_lt && 1889 ltrec.rm_startblock + ltrec.rm_blockcount == bno && 1890 ltrec.rm_offset + ltrec.rm_blockcount == offset) { 1891 /* 1892 * Left edge contiguous, merge into left record. 1893 * 1894 * ltbno ltlen 1895 * orig: |ooooooooo| 1896 * adding: |aaaaaaaaa| 1897 * result: |rrrrrrrrrrrrrrrrrrr| 1898 * bno len 1899 */ 1900 ltrec.rm_blockcount += len; 1901 if (have_gt && 1902 bno + len == gtrec.rm_startblock && 1903 offset + len == gtrec.rm_offset) { 1904 /* 1905 * Right edge also contiguous, delete right record 1906 * and merge into left record. 1907 * 1908 * ltbno ltlen gtbno gtlen 1909 * orig: |ooooooooo| |ooooooooo| 1910 * adding: |aaaaaaaaa| 1911 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr| 1912 */ 1913 ltrec.rm_blockcount += gtrec.rm_blockcount; 1914 error = xfs_rmap_delete(cur, gtrec.rm_startblock, 1915 gtrec.rm_blockcount, gtrec.rm_owner, 1916 gtrec.rm_offset, gtrec.rm_flags); 1917 if (error) 1918 goto out_error; 1919 } 1920 1921 /* Point the cursor back to the left record and update. */ 1922 error = xfs_rmap_lookup_eq(cur, ltrec.rm_startblock, 1923 ltrec.rm_blockcount, ltrec.rm_owner, 1924 ltrec.rm_offset, ltrec.rm_flags, &i); 1925 if (error) 1926 goto out_error; 1927 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error); 1928 1929 error = xfs_rmap_update(cur, <rec); 1930 if (error) 1931 goto out_error; 1932 } else if (have_gt && 1933 bno + len == gtrec.rm_startblock && 1934 offset + len == gtrec.rm_offset) { 1935 /* 1936 * Right edge contiguous, merge into right record. 1937 * 1938 * gtbno gtlen 1939 * Orig: |ooooooooo| 1940 * adding: |aaaaaaaaa| 1941 * Result: |rrrrrrrrrrrrrrrrrrr| 1942 * bno len 1943 */ 1944 /* Delete the old record. */ 1945 error = xfs_rmap_delete(cur, gtrec.rm_startblock, 1946 gtrec.rm_blockcount, gtrec.rm_owner, 1947 gtrec.rm_offset, gtrec.rm_flags); 1948 if (error) 1949 goto out_error; 1950 1951 /* Move the start and re-add it. */ 1952 gtrec.rm_startblock = bno; 1953 gtrec.rm_blockcount += len; 1954 gtrec.rm_offset = offset; 1955 error = xfs_rmap_insert(cur, gtrec.rm_startblock, 1956 gtrec.rm_blockcount, gtrec.rm_owner, 1957 gtrec.rm_offset, gtrec.rm_flags); 1958 if (error) 1959 goto out_error; 1960 } else { 1961 /* 1962 * No contiguous edge with identical owner, insert 1963 * new record at current cursor position. 1964 */ 1965 error = xfs_rmap_insert(cur, bno, len, owner, offset, flags); 1966 if (error) 1967 goto out_error; 1968 } 1969 1970 trace_xfs_rmap_map_done(mp, cur->bc_private.a.agno, bno, len, 1971 unwritten, oinfo); 1972 out_error: 1973 if (error) 1974 trace_xfs_rmap_map_error(cur->bc_mp, 1975 cur->bc_private.a.agno, error, _RET_IP_); 1976 return error; 1977 } 1978 1979 struct xfs_rmap_query_range_info { 1980 xfs_rmap_query_range_fn fn; 1981 void *priv; 1982 }; 1983 1984 /* Format btree record and pass to our callback. */ 1985 STATIC int 1986 xfs_rmap_query_range_helper( 1987 struct xfs_btree_cur *cur, 1988 union xfs_btree_rec *rec, 1989 void *priv) 1990 { 1991 struct xfs_rmap_query_range_info *query = priv; 1992 struct xfs_rmap_irec irec; 1993 int error; 1994 1995 error = xfs_rmap_btrec_to_irec(rec, &irec); 1996 if (error) 1997 return error; 1998 return query->fn(cur, &irec, query->priv); 1999 } 2000 2001 /* Find all rmaps between two keys. */ 2002 int 2003 xfs_rmap_query_range( 2004 struct xfs_btree_cur *cur, 2005 struct xfs_rmap_irec *low_rec, 2006 struct xfs_rmap_irec *high_rec, 2007 xfs_rmap_query_range_fn fn, 2008 void *priv) 2009 { 2010 union xfs_btree_irec low_brec; 2011 union xfs_btree_irec high_brec; 2012 struct xfs_rmap_query_range_info query; 2013 2014 low_brec.r = *low_rec; 2015 high_brec.r = *high_rec; 2016 query.priv = priv; 2017 query.fn = fn; 2018 return xfs_btree_query_range(cur, &low_brec, &high_brec, 2019 xfs_rmap_query_range_helper, &query); 2020 } 2021 2022 /* Clean up after calling xfs_rmap_finish_one. */ 2023 void 2024 xfs_rmap_finish_one_cleanup( 2025 struct xfs_trans *tp, 2026 struct xfs_btree_cur *rcur, 2027 int error) 2028 { 2029 struct xfs_buf *agbp; 2030 2031 if (rcur == NULL) 2032 return; 2033 agbp = rcur->bc_private.a.agbp; 2034 xfs_btree_del_cursor(rcur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR); 2035 if (error) 2036 xfs_trans_brelse(tp, agbp); 2037 } 2038 2039 /* 2040 * Process one of the deferred rmap operations. We pass back the 2041 * btree cursor to maintain our lock on the rmapbt between calls. 2042 * This saves time and eliminates a buffer deadlock between the 2043 * superblock and the AGF because we'll always grab them in the same 2044 * order. 2045 */ 2046 int 2047 xfs_rmap_finish_one( 2048 struct xfs_trans *tp, 2049 enum xfs_rmap_intent_type type, 2050 __uint64_t owner, 2051 int whichfork, 2052 xfs_fileoff_t startoff, 2053 xfs_fsblock_t startblock, 2054 xfs_filblks_t blockcount, 2055 xfs_exntst_t state, 2056 struct xfs_btree_cur **pcur) 2057 { 2058 struct xfs_mount *mp = tp->t_mountp; 2059 struct xfs_btree_cur *rcur; 2060 struct xfs_buf *agbp = NULL; 2061 int error = 0; 2062 xfs_agnumber_t agno; 2063 struct xfs_owner_info oinfo; 2064 xfs_agblock_t bno; 2065 bool unwritten; 2066 2067 agno = XFS_FSB_TO_AGNO(mp, startblock); 2068 ASSERT(agno != NULLAGNUMBER); 2069 bno = XFS_FSB_TO_AGBNO(mp, startblock); 2070 2071 trace_xfs_rmap_deferred(mp, agno, type, bno, owner, whichfork, 2072 startoff, blockcount, state); 2073 2074 if (XFS_TEST_ERROR(false, mp, 2075 XFS_ERRTAG_RMAP_FINISH_ONE, 2076 XFS_RANDOM_RMAP_FINISH_ONE)) 2077 return -EIO; 2078 2079 /* 2080 * If we haven't gotten a cursor or the cursor AG doesn't match 2081 * the startblock, get one now. 2082 */ 2083 rcur = *pcur; 2084 if (rcur != NULL && rcur->bc_private.a.agno != agno) { 2085 xfs_rmap_finish_one_cleanup(tp, rcur, 0); 2086 rcur = NULL; 2087 *pcur = NULL; 2088 } 2089 if (rcur == NULL) { 2090 /* 2091 * Refresh the freelist before we start changing the 2092 * rmapbt, because a shape change could cause us to 2093 * allocate blocks. 2094 */ 2095 error = xfs_free_extent_fix_freelist(tp, agno, &agbp); 2096 if (error) 2097 return error; 2098 if (!agbp) 2099 return -EFSCORRUPTED; 2100 2101 rcur = xfs_rmapbt_init_cursor(mp, tp, agbp, agno); 2102 if (!rcur) { 2103 error = -ENOMEM; 2104 goto out_cur; 2105 } 2106 } 2107 *pcur = rcur; 2108 2109 xfs_rmap_ino_owner(&oinfo, owner, whichfork, startoff); 2110 unwritten = state == XFS_EXT_UNWRITTEN; 2111 bno = XFS_FSB_TO_AGBNO(rcur->bc_mp, startblock); 2112 2113 switch (type) { 2114 case XFS_RMAP_ALLOC: 2115 case XFS_RMAP_MAP: 2116 error = xfs_rmap_map(rcur, bno, blockcount, unwritten, &oinfo); 2117 break; 2118 case XFS_RMAP_MAP_SHARED: 2119 error = xfs_rmap_map_shared(rcur, bno, blockcount, unwritten, 2120 &oinfo); 2121 break; 2122 case XFS_RMAP_FREE: 2123 case XFS_RMAP_UNMAP: 2124 error = xfs_rmap_unmap(rcur, bno, blockcount, unwritten, 2125 &oinfo); 2126 break; 2127 case XFS_RMAP_UNMAP_SHARED: 2128 error = xfs_rmap_unmap_shared(rcur, bno, blockcount, unwritten, 2129 &oinfo); 2130 break; 2131 case XFS_RMAP_CONVERT: 2132 error = xfs_rmap_convert(rcur, bno, blockcount, !unwritten, 2133 &oinfo); 2134 break; 2135 case XFS_RMAP_CONVERT_SHARED: 2136 error = xfs_rmap_convert_shared(rcur, bno, blockcount, 2137 !unwritten, &oinfo); 2138 break; 2139 default: 2140 ASSERT(0); 2141 error = -EFSCORRUPTED; 2142 } 2143 return error; 2144 2145 out_cur: 2146 xfs_trans_brelse(tp, agbp); 2147 2148 return error; 2149 } 2150 2151 /* 2152 * Don't defer an rmap if we aren't an rmap filesystem. 2153 */ 2154 static bool 2155 xfs_rmap_update_is_needed( 2156 struct xfs_mount *mp, 2157 int whichfork) 2158 { 2159 return xfs_sb_version_hasrmapbt(&mp->m_sb) && whichfork != XFS_COW_FORK; 2160 } 2161 2162 /* 2163 * Record a rmap intent; the list is kept sorted first by AG and then by 2164 * increasing age. 2165 */ 2166 static int 2167 __xfs_rmap_add( 2168 struct xfs_mount *mp, 2169 struct xfs_defer_ops *dfops, 2170 enum xfs_rmap_intent_type type, 2171 __uint64_t owner, 2172 int whichfork, 2173 struct xfs_bmbt_irec *bmap) 2174 { 2175 struct xfs_rmap_intent *ri; 2176 2177 trace_xfs_rmap_defer(mp, XFS_FSB_TO_AGNO(mp, bmap->br_startblock), 2178 type, 2179 XFS_FSB_TO_AGBNO(mp, bmap->br_startblock), 2180 owner, whichfork, 2181 bmap->br_startoff, 2182 bmap->br_blockcount, 2183 bmap->br_state); 2184 2185 ri = kmem_alloc(sizeof(struct xfs_rmap_intent), KM_SLEEP | KM_NOFS); 2186 INIT_LIST_HEAD(&ri->ri_list); 2187 ri->ri_type = type; 2188 ri->ri_owner = owner; 2189 ri->ri_whichfork = whichfork; 2190 ri->ri_bmap = *bmap; 2191 2192 xfs_defer_add(dfops, XFS_DEFER_OPS_TYPE_RMAP, &ri->ri_list); 2193 return 0; 2194 } 2195 2196 /* Map an extent into a file. */ 2197 int 2198 xfs_rmap_map_extent( 2199 struct xfs_mount *mp, 2200 struct xfs_defer_ops *dfops, 2201 struct xfs_inode *ip, 2202 int whichfork, 2203 struct xfs_bmbt_irec *PREV) 2204 { 2205 if (!xfs_rmap_update_is_needed(mp, whichfork)) 2206 return 0; 2207 2208 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ? 2209 XFS_RMAP_MAP_SHARED : XFS_RMAP_MAP, ip->i_ino, 2210 whichfork, PREV); 2211 } 2212 2213 /* Unmap an extent out of a file. */ 2214 int 2215 xfs_rmap_unmap_extent( 2216 struct xfs_mount *mp, 2217 struct xfs_defer_ops *dfops, 2218 struct xfs_inode *ip, 2219 int whichfork, 2220 struct xfs_bmbt_irec *PREV) 2221 { 2222 if (!xfs_rmap_update_is_needed(mp, whichfork)) 2223 return 0; 2224 2225 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ? 2226 XFS_RMAP_UNMAP_SHARED : XFS_RMAP_UNMAP, ip->i_ino, 2227 whichfork, PREV); 2228 } 2229 2230 /* Convert a data fork extent from unwritten to real or vice versa. */ 2231 int 2232 xfs_rmap_convert_extent( 2233 struct xfs_mount *mp, 2234 struct xfs_defer_ops *dfops, 2235 struct xfs_inode *ip, 2236 int whichfork, 2237 struct xfs_bmbt_irec *PREV) 2238 { 2239 if (!xfs_rmap_update_is_needed(mp, whichfork)) 2240 return 0; 2241 2242 return __xfs_rmap_add(mp, dfops, xfs_is_reflink_inode(ip) ? 2243 XFS_RMAP_CONVERT_SHARED : XFS_RMAP_CONVERT, ip->i_ino, 2244 whichfork, PREV); 2245 } 2246 2247 /* Schedule the creation of an rmap for non-file data. */ 2248 int 2249 xfs_rmap_alloc_extent( 2250 struct xfs_mount *mp, 2251 struct xfs_defer_ops *dfops, 2252 xfs_agnumber_t agno, 2253 xfs_agblock_t bno, 2254 xfs_extlen_t len, 2255 __uint64_t owner) 2256 { 2257 struct xfs_bmbt_irec bmap; 2258 2259 if (!xfs_rmap_update_is_needed(mp, XFS_DATA_FORK)) 2260 return 0; 2261 2262 bmap.br_startblock = XFS_AGB_TO_FSB(mp, agno, bno); 2263 bmap.br_blockcount = len; 2264 bmap.br_startoff = 0; 2265 bmap.br_state = XFS_EXT_NORM; 2266 2267 return __xfs_rmap_add(mp, dfops, XFS_RMAP_ALLOC, owner, 2268 XFS_DATA_FORK, &bmap); 2269 } 2270 2271 /* Schedule the deletion of an rmap for non-file data. */ 2272 int 2273 xfs_rmap_free_extent( 2274 struct xfs_mount *mp, 2275 struct xfs_defer_ops *dfops, 2276 xfs_agnumber_t agno, 2277 xfs_agblock_t bno, 2278 xfs_extlen_t len, 2279 __uint64_t owner) 2280 { 2281 struct xfs_bmbt_irec bmap; 2282 2283 if (!xfs_rmap_update_is_needed(mp, XFS_DATA_FORK)) 2284 return 0; 2285 2286 bmap.br_startblock = XFS_AGB_TO_FSB(mp, agno, bno); 2287 bmap.br_blockcount = len; 2288 bmap.br_startoff = 0; 2289 bmap.br_state = XFS_EXT_NORM; 2290 2291 return __xfs_rmap_add(mp, dfops, XFS_RMAP_FREE, owner, 2292 XFS_DATA_FORK, &bmap); 2293 } 2294