1 // SPDX-License-Identifier: GPL-2.0+ 2 /* 3 * Copyright (C) 2017 Oracle. All Rights Reserved. 4 * 5 * Author: Darrick J. Wong <darrick.wong@oracle.com> 6 */ 7 #include "ext4.h" 8 #include <linux/fsmap.h> 9 #include "fsmap.h" 10 #include "mballoc.h" 11 #include <linux/sort.h> 12 #include <linux/list_sort.h> 13 #include <trace/events/ext4.h> 14 15 /* Convert an ext4_fsmap to an fsmap. */ 16 void ext4_fsmap_from_internal(struct super_block *sb, struct fsmap *dest, 17 struct ext4_fsmap *src) 18 { 19 dest->fmr_device = src->fmr_device; 20 dest->fmr_flags = src->fmr_flags; 21 dest->fmr_physical = src->fmr_physical << sb->s_blocksize_bits; 22 dest->fmr_owner = src->fmr_owner; 23 dest->fmr_offset = 0; 24 dest->fmr_length = src->fmr_length << sb->s_blocksize_bits; 25 dest->fmr_reserved[0] = 0; 26 dest->fmr_reserved[1] = 0; 27 dest->fmr_reserved[2] = 0; 28 } 29 30 /* Convert an fsmap to an ext4_fsmap. */ 31 void ext4_fsmap_to_internal(struct super_block *sb, struct ext4_fsmap *dest, 32 struct fsmap *src) 33 { 34 dest->fmr_device = src->fmr_device; 35 dest->fmr_flags = src->fmr_flags; 36 dest->fmr_physical = src->fmr_physical >> sb->s_blocksize_bits; 37 dest->fmr_owner = src->fmr_owner; 38 dest->fmr_length = src->fmr_length >> sb->s_blocksize_bits; 39 } 40 41 /* getfsmap query state */ 42 struct ext4_getfsmap_info { 43 struct ext4_fsmap_head *gfi_head; 44 ext4_fsmap_format_t gfi_formatter; /* formatting fn */ 45 void *gfi_format_arg;/* format buffer */ 46 ext4_fsblk_t gfi_next_fsblk; /* next fsblock we expect */ 47 u32 gfi_dev; /* device id */ 48 ext4_group_t gfi_agno; /* bg number, if applicable */ 49 struct ext4_fsmap gfi_low; /* low rmap key */ 50 struct ext4_fsmap gfi_high; /* high rmap key */ 51 struct ext4_fsmap gfi_lastfree; /* free ext at end of last bg */ 52 struct list_head gfi_meta_list; /* fixed metadata list */ 53 bool gfi_last; /* last extent? */ 54 }; 55 56 /* Associate a device with a getfsmap handler. */ 57 struct ext4_getfsmap_dev { 58 int (*gfd_fn)(struct super_block *sb, 59 struct ext4_fsmap *keys, 60 struct ext4_getfsmap_info *info); 61 u32 gfd_dev; 62 }; 63 64 /* Compare two getfsmap device handlers. */ 65 static int ext4_getfsmap_dev_compare(const void *p1, const void *p2) 66 { 67 const struct ext4_getfsmap_dev *d1 = p1; 68 const struct ext4_getfsmap_dev *d2 = p2; 69 70 return d1->gfd_dev - d2->gfd_dev; 71 } 72 73 /* Compare a record against our starting point */ 74 static bool ext4_getfsmap_rec_before_low_key(struct ext4_getfsmap_info *info, 75 struct ext4_fsmap *rec) 76 { 77 return rec->fmr_physical < info->gfi_low.fmr_physical; 78 } 79 80 /* 81 * Format a reverse mapping for getfsmap, having translated rm_startblock 82 * into the appropriate daddr units. 83 */ 84 static int ext4_getfsmap_helper(struct super_block *sb, 85 struct ext4_getfsmap_info *info, 86 struct ext4_fsmap *rec) 87 { 88 struct ext4_fsmap fmr; 89 struct ext4_sb_info *sbi = EXT4_SB(sb); 90 ext4_fsblk_t rec_fsblk = rec->fmr_physical; 91 ext4_group_t agno; 92 ext4_grpblk_t cno; 93 int error; 94 95 if (fatal_signal_pending(current)) 96 return -EINTR; 97 98 /* 99 * Filter out records that start before our startpoint, if the 100 * caller requested that. 101 */ 102 if (ext4_getfsmap_rec_before_low_key(info, rec)) { 103 rec_fsblk += rec->fmr_length; 104 if (info->gfi_next_fsblk < rec_fsblk) 105 info->gfi_next_fsblk = rec_fsblk; 106 return EXT4_QUERY_RANGE_CONTINUE; 107 } 108 109 /* Are we just counting mappings? */ 110 if (info->gfi_head->fmh_count == 0) { 111 if (info->gfi_head->fmh_entries == UINT_MAX) 112 return EXT4_QUERY_RANGE_ABORT; 113 114 if (rec_fsblk > info->gfi_next_fsblk) 115 info->gfi_head->fmh_entries++; 116 117 if (info->gfi_last) 118 return EXT4_QUERY_RANGE_CONTINUE; 119 120 info->gfi_head->fmh_entries++; 121 122 rec_fsblk += rec->fmr_length; 123 if (info->gfi_next_fsblk < rec_fsblk) 124 info->gfi_next_fsblk = rec_fsblk; 125 return EXT4_QUERY_RANGE_CONTINUE; 126 } 127 128 /* 129 * If the record starts past the last physical block we saw, 130 * then we've found a gap. Report the gap as being owned by 131 * whatever the caller specified is the missing owner. 132 */ 133 if (rec_fsblk > info->gfi_next_fsblk) { 134 if (info->gfi_head->fmh_entries >= info->gfi_head->fmh_count) 135 return EXT4_QUERY_RANGE_ABORT; 136 137 ext4_get_group_no_and_offset(sb, info->gfi_next_fsblk, 138 &agno, &cno); 139 trace_ext4_fsmap_mapping(sb, info->gfi_dev, agno, 140 EXT4_C2B(sbi, cno), 141 rec_fsblk - info->gfi_next_fsblk, 142 EXT4_FMR_OWN_UNKNOWN); 143 144 fmr.fmr_device = info->gfi_dev; 145 fmr.fmr_physical = info->gfi_next_fsblk; 146 fmr.fmr_owner = EXT4_FMR_OWN_UNKNOWN; 147 fmr.fmr_length = rec_fsblk - info->gfi_next_fsblk; 148 fmr.fmr_flags = FMR_OF_SPECIAL_OWNER; 149 error = info->gfi_formatter(&fmr, info->gfi_format_arg); 150 if (error) 151 return error; 152 info->gfi_head->fmh_entries++; 153 } 154 155 if (info->gfi_last) 156 goto out; 157 158 /* Fill out the extent we found */ 159 if (info->gfi_head->fmh_entries >= info->gfi_head->fmh_count) 160 return EXT4_QUERY_RANGE_ABORT; 161 162 ext4_get_group_no_and_offset(sb, rec_fsblk, &agno, &cno); 163 trace_ext4_fsmap_mapping(sb, info->gfi_dev, agno, EXT4_C2B(sbi, cno), 164 rec->fmr_length, rec->fmr_owner); 165 166 fmr.fmr_device = info->gfi_dev; 167 fmr.fmr_physical = rec_fsblk; 168 fmr.fmr_owner = rec->fmr_owner; 169 fmr.fmr_flags = FMR_OF_SPECIAL_OWNER; 170 fmr.fmr_length = rec->fmr_length; 171 error = info->gfi_formatter(&fmr, info->gfi_format_arg); 172 if (error) 173 return error; 174 info->gfi_head->fmh_entries++; 175 176 out: 177 rec_fsblk += rec->fmr_length; 178 if (info->gfi_next_fsblk < rec_fsblk) 179 info->gfi_next_fsblk = rec_fsblk; 180 return EXT4_QUERY_RANGE_CONTINUE; 181 } 182 183 static inline ext4_fsblk_t ext4_fsmap_next_pblk(struct ext4_fsmap *fmr) 184 { 185 return fmr->fmr_physical + fmr->fmr_length; 186 } 187 188 static int ext4_getfsmap_meta_helper(struct super_block *sb, 189 ext4_group_t agno, ext4_grpblk_t start, 190 ext4_grpblk_t len, void *priv) 191 { 192 struct ext4_getfsmap_info *info = priv; 193 struct ext4_fsmap *p; 194 struct ext4_fsmap *tmp; 195 struct ext4_sb_info *sbi = EXT4_SB(sb); 196 ext4_fsblk_t fsb, fs_start, fs_end; 197 int error; 198 199 fs_start = fsb = (EXT4_C2B(sbi, start) + 200 ext4_group_first_block_no(sb, agno)); 201 fs_end = fs_start + EXT4_C2B(sbi, len); 202 203 /* Return relevant extents from the meta_list */ 204 list_for_each_entry_safe(p, tmp, &info->gfi_meta_list, fmr_list) { 205 if (p->fmr_physical < info->gfi_next_fsblk) { 206 list_del(&p->fmr_list); 207 kfree(p); 208 continue; 209 } 210 if (p->fmr_physical <= fs_start || 211 p->fmr_physical + p->fmr_length <= fs_end) { 212 /* Emit the retained free extent record if present */ 213 if (info->gfi_lastfree.fmr_owner) { 214 error = ext4_getfsmap_helper(sb, info, 215 &info->gfi_lastfree); 216 if (error) 217 return error; 218 info->gfi_lastfree.fmr_owner = 0; 219 } 220 error = ext4_getfsmap_helper(sb, info, p); 221 if (error) 222 return error; 223 fsb = p->fmr_physical + p->fmr_length; 224 if (info->gfi_next_fsblk < fsb) 225 info->gfi_next_fsblk = fsb; 226 list_del(&p->fmr_list); 227 kfree(p); 228 continue; 229 } 230 } 231 if (info->gfi_next_fsblk < fsb) 232 info->gfi_next_fsblk = fsb; 233 234 return 0; 235 } 236 237 238 /* Transform a blockgroup's free record into a fsmap */ 239 static int ext4_getfsmap_datadev_helper(struct super_block *sb, 240 ext4_group_t agno, ext4_grpblk_t start, 241 ext4_grpblk_t len, void *priv) 242 { 243 struct ext4_fsmap irec; 244 struct ext4_getfsmap_info *info = priv; 245 struct ext4_fsmap *p; 246 struct ext4_fsmap *tmp; 247 struct ext4_sb_info *sbi = EXT4_SB(sb); 248 ext4_fsblk_t fsb; 249 ext4_fsblk_t fslen; 250 int error; 251 252 fsb = (EXT4_C2B(sbi, start) + ext4_group_first_block_no(sb, agno)); 253 fslen = EXT4_C2B(sbi, len); 254 255 /* If the retained free extent record is set... */ 256 if (info->gfi_lastfree.fmr_owner) { 257 /* ...and abuts this one, lengthen it and return. */ 258 if (ext4_fsmap_next_pblk(&info->gfi_lastfree) == fsb) { 259 info->gfi_lastfree.fmr_length += fslen; 260 return 0; 261 } 262 263 /* 264 * There's a gap between the two free extents; emit the 265 * retained extent prior to merging the meta_list. 266 */ 267 error = ext4_getfsmap_helper(sb, info, &info->gfi_lastfree); 268 if (error) 269 return error; 270 info->gfi_lastfree.fmr_owner = 0; 271 } 272 273 /* Merge in any relevant extents from the meta_list */ 274 list_for_each_entry_safe(p, tmp, &info->gfi_meta_list, fmr_list) { 275 if (p->fmr_physical + p->fmr_length <= info->gfi_next_fsblk) { 276 list_del(&p->fmr_list); 277 kfree(p); 278 } else if (p->fmr_physical < fsb) { 279 error = ext4_getfsmap_helper(sb, info, p); 280 if (error) 281 return error; 282 283 list_del(&p->fmr_list); 284 kfree(p); 285 } 286 } 287 288 irec.fmr_device = 0; 289 irec.fmr_physical = fsb; 290 irec.fmr_length = fslen; 291 irec.fmr_owner = EXT4_FMR_OWN_FREE; 292 irec.fmr_flags = 0; 293 294 /* If this is a free extent at the end of a bg, buffer it. */ 295 if (ext4_fsmap_next_pblk(&irec) == 296 ext4_group_first_block_no(sb, agno + 1)) { 297 info->gfi_lastfree = irec; 298 return 0; 299 } 300 301 /* Otherwise, emit it */ 302 return ext4_getfsmap_helper(sb, info, &irec); 303 } 304 305 /* Execute a getfsmap query against the log device. */ 306 static int ext4_getfsmap_logdev(struct super_block *sb, struct ext4_fsmap *keys, 307 struct ext4_getfsmap_info *info) 308 { 309 journal_t *journal = EXT4_SB(sb)->s_journal; 310 struct ext4_fsmap irec; 311 312 /* Set up search keys */ 313 info->gfi_low = keys[0]; 314 info->gfi_low.fmr_length = 0; 315 316 memset(&info->gfi_high, 0xFF, sizeof(info->gfi_high)); 317 318 trace_ext4_fsmap_low_key(sb, info->gfi_dev, 0, 319 info->gfi_low.fmr_physical, 320 info->gfi_low.fmr_length, 321 info->gfi_low.fmr_owner); 322 323 trace_ext4_fsmap_high_key(sb, info->gfi_dev, 0, 324 info->gfi_high.fmr_physical, 325 info->gfi_high.fmr_length, 326 info->gfi_high.fmr_owner); 327 328 if (keys[0].fmr_physical > 0) 329 return 0; 330 331 /* Fabricate an rmap entry for the external log device. */ 332 irec.fmr_physical = journal->j_blk_offset; 333 irec.fmr_length = journal->j_total_len; 334 irec.fmr_owner = EXT4_FMR_OWN_LOG; 335 irec.fmr_flags = 0; 336 337 return ext4_getfsmap_helper(sb, info, &irec); 338 } 339 340 /* Helper to fill out an ext4_fsmap. */ 341 static inline int ext4_getfsmap_fill(struct list_head *meta_list, 342 ext4_fsblk_t fsb, ext4_fsblk_t len, 343 uint64_t owner) 344 { 345 struct ext4_fsmap *fsm; 346 347 fsm = kmalloc(sizeof(*fsm), GFP_NOFS); 348 if (!fsm) 349 return -ENOMEM; 350 fsm->fmr_device = 0; 351 fsm->fmr_flags = 0; 352 fsm->fmr_physical = fsb; 353 fsm->fmr_owner = owner; 354 fsm->fmr_length = len; 355 list_add_tail(&fsm->fmr_list, meta_list); 356 357 return 0; 358 } 359 360 /* 361 * This function returns the number of file system metadata blocks at 362 * the beginning of a block group, including the reserved gdt blocks. 363 */ 364 static unsigned int ext4_getfsmap_find_sb(struct super_block *sb, 365 ext4_group_t agno, 366 struct list_head *meta_list) 367 { 368 struct ext4_sb_info *sbi = EXT4_SB(sb); 369 ext4_fsblk_t fsb = ext4_group_first_block_no(sb, agno); 370 ext4_fsblk_t len; 371 unsigned long first_meta_bg = le32_to_cpu(sbi->s_es->s_first_meta_bg); 372 unsigned long metagroup = agno / EXT4_DESC_PER_BLOCK(sb); 373 int error; 374 375 /* Record the superblock. */ 376 if (ext4_bg_has_super(sb, agno)) { 377 error = ext4_getfsmap_fill(meta_list, fsb, 1, EXT4_FMR_OWN_FS); 378 if (error) 379 return error; 380 fsb++; 381 } 382 383 /* Record the group descriptors. */ 384 len = ext4_bg_num_gdb(sb, agno); 385 if (!len) 386 return 0; 387 error = ext4_getfsmap_fill(meta_list, fsb, len, 388 EXT4_FMR_OWN_GDT); 389 if (error) 390 return error; 391 fsb += len; 392 393 /* Reserved GDT blocks */ 394 if (!ext4_has_feature_meta_bg(sb) || metagroup < first_meta_bg) { 395 len = le16_to_cpu(sbi->s_es->s_reserved_gdt_blocks); 396 error = ext4_getfsmap_fill(meta_list, fsb, len, 397 EXT4_FMR_OWN_RESV_GDT); 398 if (error) 399 return error; 400 } 401 402 return 0; 403 } 404 405 /* Compare two fsmap items. */ 406 static int ext4_getfsmap_compare(void *priv, 407 const struct list_head *a, 408 const struct list_head *b) 409 { 410 struct ext4_fsmap *fa; 411 struct ext4_fsmap *fb; 412 413 fa = container_of(a, struct ext4_fsmap, fmr_list); 414 fb = container_of(b, struct ext4_fsmap, fmr_list); 415 if (fa->fmr_physical < fb->fmr_physical) 416 return -1; 417 else if (fa->fmr_physical > fb->fmr_physical) 418 return 1; 419 return 0; 420 } 421 422 /* Merge adjacent extents of fixed metadata. */ 423 static void ext4_getfsmap_merge_fixed_metadata(struct list_head *meta_list) 424 { 425 struct ext4_fsmap *p; 426 struct ext4_fsmap *prev = NULL; 427 struct ext4_fsmap *tmp; 428 429 list_for_each_entry_safe(p, tmp, meta_list, fmr_list) { 430 if (!prev) { 431 prev = p; 432 continue; 433 } 434 435 if (prev->fmr_owner == p->fmr_owner && 436 prev->fmr_physical + prev->fmr_length == p->fmr_physical) { 437 prev->fmr_length += p->fmr_length; 438 list_del(&p->fmr_list); 439 kfree(p); 440 } else 441 prev = p; 442 } 443 } 444 445 /* Free a list of fixed metadata. */ 446 static void ext4_getfsmap_free_fixed_metadata(struct list_head *meta_list) 447 { 448 struct ext4_fsmap *p; 449 struct ext4_fsmap *tmp; 450 451 list_for_each_entry_safe(p, tmp, meta_list, fmr_list) { 452 list_del(&p->fmr_list); 453 kfree(p); 454 } 455 } 456 457 /* Find all the fixed metadata in the filesystem. */ 458 static int ext4_getfsmap_find_fixed_metadata(struct super_block *sb, 459 struct list_head *meta_list) 460 { 461 struct ext4_group_desc *gdp; 462 ext4_group_t agno; 463 int error; 464 465 INIT_LIST_HEAD(meta_list); 466 467 /* Collect everything. */ 468 for (agno = 0; agno < EXT4_SB(sb)->s_groups_count; agno++) { 469 gdp = ext4_get_group_desc(sb, agno, NULL); 470 if (!gdp) { 471 error = -EFSCORRUPTED; 472 goto err; 473 } 474 475 /* Superblock & GDT */ 476 error = ext4_getfsmap_find_sb(sb, agno, meta_list); 477 if (error) 478 goto err; 479 480 /* Block bitmap */ 481 error = ext4_getfsmap_fill(meta_list, 482 ext4_block_bitmap(sb, gdp), 1, 483 EXT4_FMR_OWN_BLKBM); 484 if (error) 485 goto err; 486 487 /* Inode bitmap */ 488 error = ext4_getfsmap_fill(meta_list, 489 ext4_inode_bitmap(sb, gdp), 1, 490 EXT4_FMR_OWN_INOBM); 491 if (error) 492 goto err; 493 494 /* Inodes */ 495 error = ext4_getfsmap_fill(meta_list, 496 ext4_inode_table(sb, gdp), 497 EXT4_SB(sb)->s_itb_per_group, 498 EXT4_FMR_OWN_INODES); 499 if (error) 500 goto err; 501 } 502 503 /* Sort the list */ 504 list_sort(NULL, meta_list, ext4_getfsmap_compare); 505 506 /* Merge adjacent extents */ 507 ext4_getfsmap_merge_fixed_metadata(meta_list); 508 509 return 0; 510 err: 511 ext4_getfsmap_free_fixed_metadata(meta_list); 512 return error; 513 } 514 515 /* Execute a getfsmap query against the buddy bitmaps */ 516 static int ext4_getfsmap_datadev(struct super_block *sb, 517 struct ext4_fsmap *keys, 518 struct ext4_getfsmap_info *info) 519 { 520 struct ext4_sb_info *sbi = EXT4_SB(sb); 521 ext4_fsblk_t start_fsb; 522 ext4_fsblk_t end_fsb; 523 ext4_fsblk_t bofs; 524 ext4_fsblk_t eofs; 525 ext4_group_t start_ag; 526 ext4_group_t end_ag; 527 ext4_grpblk_t first_cluster; 528 ext4_grpblk_t last_cluster; 529 int error = 0; 530 531 bofs = le32_to_cpu(sbi->s_es->s_first_data_block); 532 eofs = ext4_blocks_count(sbi->s_es); 533 if (keys[0].fmr_physical >= eofs) 534 return 0; 535 else if (keys[0].fmr_physical < bofs) 536 keys[0].fmr_physical = bofs; 537 if (keys[1].fmr_physical >= eofs) 538 keys[1].fmr_physical = eofs - 1; 539 if (keys[1].fmr_physical < keys[0].fmr_physical) 540 return 0; 541 start_fsb = keys[0].fmr_physical; 542 end_fsb = keys[1].fmr_physical; 543 544 /* Determine first and last group to examine based on start and end */ 545 ext4_get_group_no_and_offset(sb, start_fsb, &start_ag, &first_cluster); 546 ext4_get_group_no_and_offset(sb, end_fsb, &end_ag, &last_cluster); 547 548 /* 549 * Convert the fsmap low/high keys to bg based keys. Initialize 550 * low to the fsmap low key and max out the high key to the end 551 * of the bg. 552 */ 553 info->gfi_low = keys[0]; 554 info->gfi_low.fmr_physical = EXT4_C2B(sbi, first_cluster); 555 info->gfi_low.fmr_length = 0; 556 557 memset(&info->gfi_high, 0xFF, sizeof(info->gfi_high)); 558 559 /* Assemble a list of all the fixed-location metadata. */ 560 error = ext4_getfsmap_find_fixed_metadata(sb, &info->gfi_meta_list); 561 if (error) 562 goto err; 563 564 /* Query each bg */ 565 for (info->gfi_agno = start_ag; 566 info->gfi_agno <= end_ag; 567 info->gfi_agno++) { 568 /* 569 * Set the bg high key from the fsmap high key if this 570 * is the last bg that we're querying. 571 */ 572 if (info->gfi_agno == end_ag) { 573 info->gfi_high = keys[1]; 574 info->gfi_high.fmr_physical = EXT4_C2B(sbi, 575 last_cluster); 576 info->gfi_high.fmr_length = 0; 577 } 578 579 trace_ext4_fsmap_low_key(sb, info->gfi_dev, info->gfi_agno, 580 info->gfi_low.fmr_physical, 581 info->gfi_low.fmr_length, 582 info->gfi_low.fmr_owner); 583 584 trace_ext4_fsmap_high_key(sb, info->gfi_dev, info->gfi_agno, 585 info->gfi_high.fmr_physical, 586 info->gfi_high.fmr_length, 587 info->gfi_high.fmr_owner); 588 589 error = ext4_mballoc_query_range(sb, info->gfi_agno, 590 EXT4_B2C(sbi, info->gfi_low.fmr_physical), 591 EXT4_B2C(sbi, info->gfi_high.fmr_physical), 592 ext4_getfsmap_meta_helper, 593 ext4_getfsmap_datadev_helper, info); 594 if (error) 595 goto err; 596 597 /* 598 * Set the bg low key to the start of the bg prior to 599 * moving on to the next bg. 600 */ 601 if (info->gfi_agno == start_ag) 602 memset(&info->gfi_low, 0, sizeof(info->gfi_low)); 603 } 604 605 /* Do we have a retained free extent? */ 606 if (info->gfi_lastfree.fmr_owner) { 607 error = ext4_getfsmap_helper(sb, info, &info->gfi_lastfree); 608 if (error) 609 goto err; 610 } 611 612 /* Report any gaps at the end of the bg */ 613 info->gfi_last = true; 614 error = ext4_getfsmap_datadev_helper(sb, end_ag, last_cluster + 1, 615 0, info); 616 if (error) 617 goto err; 618 619 err: 620 ext4_getfsmap_free_fixed_metadata(&info->gfi_meta_list); 621 return error; 622 } 623 624 /* Do we recognize the device? */ 625 static bool ext4_getfsmap_is_valid_device(struct super_block *sb, 626 struct ext4_fsmap *fm) 627 { 628 if (fm->fmr_device == 0 || fm->fmr_device == UINT_MAX || 629 fm->fmr_device == new_encode_dev(sb->s_bdev->bd_dev)) 630 return true; 631 if (EXT4_SB(sb)->s_journal_bdev_file && 632 fm->fmr_device == 633 new_encode_dev(file_bdev(EXT4_SB(sb)->s_journal_bdev_file)->bd_dev)) 634 return true; 635 return false; 636 } 637 638 /* Ensure that the low key is less than the high key. */ 639 static bool ext4_getfsmap_check_keys(struct ext4_fsmap *low_key, 640 struct ext4_fsmap *high_key) 641 { 642 if (low_key->fmr_device > high_key->fmr_device) 643 return false; 644 if (low_key->fmr_device < high_key->fmr_device) 645 return true; 646 647 if (low_key->fmr_physical > high_key->fmr_physical) 648 return false; 649 if (low_key->fmr_physical < high_key->fmr_physical) 650 return true; 651 652 if (low_key->fmr_owner > high_key->fmr_owner) 653 return false; 654 if (low_key->fmr_owner < high_key->fmr_owner) 655 return true; 656 657 return false; 658 } 659 660 #define EXT4_GETFSMAP_DEVS 2 661 /* 662 * Get filesystem's extents as described in head, and format for 663 * output. Calls formatter to fill the user's buffer until all 664 * extents are mapped, until the passed-in head->fmh_count slots have 665 * been filled, or until the formatter short-circuits the loop, if it 666 * is tracking filled-in extents on its own. 667 * 668 * Key to Confusion 669 * ---------------- 670 * There are multiple levels of keys and counters at work here: 671 * _fsmap_head.fmh_keys -- low and high fsmap keys passed in; 672 * these reflect fs-wide block addrs. 673 * dkeys -- fmh_keys used to query each device; 674 * these are fmh_keys but w/ the low key 675 * bumped up by fmr_length. 676 * _getfsmap_info.gfi_next_fsblk-- next fs block we expect to see; this 677 * is how we detect gaps in the fsmap 678 * records and report them. 679 * _getfsmap_info.gfi_low/high -- per-bg low/high keys computed from 680 * dkeys; used to query the free space. 681 */ 682 int ext4_getfsmap(struct super_block *sb, struct ext4_fsmap_head *head, 683 ext4_fsmap_format_t formatter, void *arg) 684 { 685 struct ext4_fsmap dkeys[2]; /* per-dev keys */ 686 struct ext4_getfsmap_dev handlers[EXT4_GETFSMAP_DEVS]; 687 struct ext4_getfsmap_info info = { NULL }; 688 int i; 689 int error = 0; 690 691 if (head->fmh_iflags & ~FMH_IF_VALID) 692 return -EINVAL; 693 if (!ext4_getfsmap_is_valid_device(sb, &head->fmh_keys[0]) || 694 !ext4_getfsmap_is_valid_device(sb, &head->fmh_keys[1])) 695 return -EINVAL; 696 697 head->fmh_entries = 0; 698 699 /* Set up our device handlers. */ 700 memset(handlers, 0, sizeof(handlers)); 701 handlers[0].gfd_dev = new_encode_dev(sb->s_bdev->bd_dev); 702 handlers[0].gfd_fn = ext4_getfsmap_datadev; 703 if (EXT4_SB(sb)->s_journal_bdev_file) { 704 handlers[1].gfd_dev = new_encode_dev( 705 file_bdev(EXT4_SB(sb)->s_journal_bdev_file)->bd_dev); 706 handlers[1].gfd_fn = ext4_getfsmap_logdev; 707 } 708 709 sort(handlers, EXT4_GETFSMAP_DEVS, sizeof(struct ext4_getfsmap_dev), 710 ext4_getfsmap_dev_compare, NULL); 711 712 /* 713 * To continue where we left off, we allow userspace to use the 714 * last mapping from a previous call as the low key of the next. 715 * This is identified by a non-zero length in the low key. We 716 * have to increment the low key in this scenario to ensure we 717 * don't return the same mapping again, and instead return the 718 * very next mapping. 719 * 720 * Bump the physical offset as there can be no other mapping for 721 * the same physical block range. 722 */ 723 dkeys[0] = head->fmh_keys[0]; 724 dkeys[0].fmr_physical += dkeys[0].fmr_length; 725 dkeys[0].fmr_owner = 0; 726 dkeys[0].fmr_length = 0; 727 memset(&dkeys[1], 0xFF, sizeof(struct ext4_fsmap)); 728 729 if (!ext4_getfsmap_check_keys(dkeys, &head->fmh_keys[1])) 730 return -EINVAL; 731 732 info.gfi_next_fsblk = head->fmh_keys[0].fmr_physical + 733 head->fmh_keys[0].fmr_length; 734 info.gfi_formatter = formatter; 735 info.gfi_format_arg = arg; 736 info.gfi_head = head; 737 738 /* For each device we support... */ 739 for (i = 0; i < EXT4_GETFSMAP_DEVS; i++) { 740 /* Is this device within the range the user asked for? */ 741 if (!handlers[i].gfd_fn) 742 continue; 743 if (head->fmh_keys[0].fmr_device > handlers[i].gfd_dev) 744 continue; 745 if (head->fmh_keys[1].fmr_device < handlers[i].gfd_dev) 746 break; 747 748 /* 749 * If this device number matches the high key, we have 750 * to pass the high key to the handler to limit the 751 * query results. If the device number exceeds the 752 * low key, zero out the low key so that we get 753 * everything from the beginning. 754 */ 755 if (handlers[i].gfd_dev == head->fmh_keys[1].fmr_device) 756 dkeys[1] = head->fmh_keys[1]; 757 if (handlers[i].gfd_dev > head->fmh_keys[0].fmr_device) 758 memset(&dkeys[0], 0, sizeof(struct ext4_fsmap)); 759 760 info.gfi_dev = handlers[i].gfd_dev; 761 info.gfi_last = false; 762 info.gfi_agno = -1; 763 error = handlers[i].gfd_fn(sb, dkeys, &info); 764 if (error) 765 break; 766 info.gfi_next_fsblk = 0; 767 } 768 769 head->fmh_oflags = FMH_OF_DEV_T; 770 return error; 771 } 772