1 /* 2 * Copyright (c) 2000-2005 Silicon Graphics, Inc. 3 * Copyright (c) 2013 Red Hat, Inc. 4 * All Rights Reserved. 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License as 8 * published by the Free Software Foundation. 9 * 10 * This program is distributed in the hope that it would be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 18 */ 19 #include "xfs.h" 20 #include "xfs_fs.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_mount.h" 26 #include "xfs_da_format.h" 27 #include "xfs_da_btree.h" 28 #include "xfs_inode.h" 29 #include "xfs_dir2.h" 30 #include "xfs_dir2_priv.h" 31 #include "xfs_error.h" 32 #include "xfs_trace.h" 33 #include "xfs_bmap.h" 34 #include "xfs_trans.h" 35 36 /* 37 * Directory file type support functions 38 */ 39 static unsigned char xfs_dir3_filetype_table[] = { 40 DT_UNKNOWN, DT_REG, DT_DIR, DT_CHR, DT_BLK, 41 DT_FIFO, DT_SOCK, DT_LNK, DT_WHT, 42 }; 43 44 static unsigned char 45 xfs_dir3_get_dtype( 46 struct xfs_mount *mp, 47 __uint8_t filetype) 48 { 49 if (!xfs_sb_version_hasftype(&mp->m_sb)) 50 return DT_UNKNOWN; 51 52 if (filetype >= XFS_DIR3_FT_MAX) 53 return DT_UNKNOWN; 54 55 return xfs_dir3_filetype_table[filetype]; 56 } 57 58 STATIC int 59 xfs_dir2_sf_getdents( 60 struct xfs_da_args *args, 61 struct dir_context *ctx) 62 { 63 int i; /* shortform entry number */ 64 struct xfs_inode *dp = args->dp; /* incore directory inode */ 65 xfs_dir2_dataptr_t off; /* current entry's offset */ 66 xfs_dir2_sf_entry_t *sfep; /* shortform directory entry */ 67 xfs_dir2_sf_hdr_t *sfp; /* shortform structure */ 68 xfs_dir2_dataptr_t dot_offset; 69 xfs_dir2_dataptr_t dotdot_offset; 70 xfs_ino_t ino; 71 struct xfs_da_geometry *geo = args->geo; 72 73 ASSERT(dp->i_df.if_flags & XFS_IFINLINE); 74 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); 75 ASSERT(dp->i_df.if_u1.if_data != NULL); 76 77 sfp = (xfs_dir2_sf_hdr_t *)dp->i_df.if_u1.if_data; 78 79 /* 80 * If the block number in the offset is out of range, we're done. 81 */ 82 if (xfs_dir2_dataptr_to_db(geo, ctx->pos) > geo->datablk) 83 return 0; 84 85 /* 86 * Precalculate offsets for . and .. as we will always need them. 87 * 88 * XXX(hch): the second argument is sometimes 0 and sometimes 89 * geo->datablk 90 */ 91 dot_offset = xfs_dir2_db_off_to_dataptr(geo, geo->datablk, 92 dp->d_ops->data_dot_offset); 93 dotdot_offset = xfs_dir2_db_off_to_dataptr(geo, geo->datablk, 94 dp->d_ops->data_dotdot_offset); 95 96 /* 97 * Put . entry unless we're starting past it. 98 */ 99 if (ctx->pos <= dot_offset) { 100 ctx->pos = dot_offset & 0x7fffffff; 101 if (!dir_emit(ctx, ".", 1, dp->i_ino, DT_DIR)) 102 return 0; 103 } 104 105 /* 106 * Put .. entry unless we're starting past it. 107 */ 108 if (ctx->pos <= dotdot_offset) { 109 ino = dp->d_ops->sf_get_parent_ino(sfp); 110 ctx->pos = dotdot_offset & 0x7fffffff; 111 if (!dir_emit(ctx, "..", 2, ino, DT_DIR)) 112 return 0; 113 } 114 115 /* 116 * Loop while there are more entries and put'ing works. 117 */ 118 sfep = xfs_dir2_sf_firstentry(sfp); 119 for (i = 0; i < sfp->count; i++) { 120 __uint8_t filetype; 121 122 off = xfs_dir2_db_off_to_dataptr(geo, geo->datablk, 123 xfs_dir2_sf_get_offset(sfep)); 124 125 if (ctx->pos > off) { 126 sfep = dp->d_ops->sf_nextentry(sfp, sfep); 127 continue; 128 } 129 130 ino = dp->d_ops->sf_get_ino(sfp, sfep); 131 filetype = dp->d_ops->sf_get_ftype(sfep); 132 ctx->pos = off & 0x7fffffff; 133 if (!dir_emit(ctx, (char *)sfep->name, sfep->namelen, ino, 134 xfs_dir3_get_dtype(dp->i_mount, filetype))) 135 return 0; 136 sfep = dp->d_ops->sf_nextentry(sfp, sfep); 137 } 138 139 ctx->pos = xfs_dir2_db_off_to_dataptr(geo, geo->datablk + 1, 0) & 140 0x7fffffff; 141 return 0; 142 } 143 144 /* 145 * Readdir for block directories. 146 */ 147 STATIC int 148 xfs_dir2_block_getdents( 149 struct xfs_da_args *args, 150 struct dir_context *ctx) 151 { 152 struct xfs_inode *dp = args->dp; /* incore directory inode */ 153 xfs_dir2_data_hdr_t *hdr; /* block header */ 154 struct xfs_buf *bp; /* buffer for block */ 155 xfs_dir2_block_tail_t *btp; /* block tail */ 156 xfs_dir2_data_entry_t *dep; /* block data entry */ 157 xfs_dir2_data_unused_t *dup; /* block unused entry */ 158 char *endptr; /* end of the data entries */ 159 int error; /* error return value */ 160 char *ptr; /* current data entry */ 161 int wantoff; /* starting block offset */ 162 xfs_off_t cook; 163 struct xfs_da_geometry *geo = args->geo; 164 int lock_mode; 165 166 /* 167 * If the block number in the offset is out of range, we're done. 168 */ 169 if (xfs_dir2_dataptr_to_db(geo, ctx->pos) > geo->datablk) 170 return 0; 171 172 lock_mode = xfs_ilock_data_map_shared(dp); 173 error = xfs_dir3_block_read(NULL, dp, &bp); 174 xfs_iunlock(dp, lock_mode); 175 if (error) 176 return error; 177 178 /* 179 * Extract the byte offset we start at from the seek pointer. 180 * We'll skip entries before this. 181 */ 182 wantoff = xfs_dir2_dataptr_to_off(geo, ctx->pos); 183 hdr = bp->b_addr; 184 xfs_dir3_data_check(dp, bp); 185 /* 186 * Set up values for the loop. 187 */ 188 btp = xfs_dir2_block_tail_p(geo, hdr); 189 ptr = (char *)dp->d_ops->data_entry_p(hdr); 190 endptr = (char *)xfs_dir2_block_leaf_p(btp); 191 192 /* 193 * Loop over the data portion of the block. 194 * Each object is a real entry (dep) or an unused one (dup). 195 */ 196 while (ptr < endptr) { 197 __uint8_t filetype; 198 199 dup = (xfs_dir2_data_unused_t *)ptr; 200 /* 201 * Unused, skip it. 202 */ 203 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 204 ptr += be16_to_cpu(dup->length); 205 continue; 206 } 207 208 dep = (xfs_dir2_data_entry_t *)ptr; 209 210 /* 211 * Bump pointer for the next iteration. 212 */ 213 ptr += dp->d_ops->data_entsize(dep->namelen); 214 /* 215 * The entry is before the desired starting point, skip it. 216 */ 217 if ((char *)dep - (char *)hdr < wantoff) 218 continue; 219 220 cook = xfs_dir2_db_off_to_dataptr(geo, geo->datablk, 221 (char *)dep - (char *)hdr); 222 223 ctx->pos = cook & 0x7fffffff; 224 filetype = dp->d_ops->data_get_ftype(dep); 225 /* 226 * If it didn't fit, set the final offset to here & return. 227 */ 228 if (!dir_emit(ctx, (char *)dep->name, dep->namelen, 229 be64_to_cpu(dep->inumber), 230 xfs_dir3_get_dtype(dp->i_mount, filetype))) { 231 xfs_trans_brelse(NULL, bp); 232 return 0; 233 } 234 } 235 236 /* 237 * Reached the end of the block. 238 * Set the offset to a non-existent block 1 and return. 239 */ 240 ctx->pos = xfs_dir2_db_off_to_dataptr(geo, geo->datablk + 1, 0) & 241 0x7fffffff; 242 xfs_trans_brelse(NULL, bp); 243 return 0; 244 } 245 246 struct xfs_dir2_leaf_map_info { 247 xfs_extlen_t map_blocks; /* number of fsbs in map */ 248 xfs_dablk_t map_off; /* last mapped file offset */ 249 int map_size; /* total entries in *map */ 250 int map_valid; /* valid entries in *map */ 251 int nmap; /* mappings to ask xfs_bmapi */ 252 xfs_dir2_db_t curdb; /* db for current block */ 253 int ra_current; /* number of read-ahead blks */ 254 int ra_index; /* *map index for read-ahead */ 255 int ra_offset; /* map entry offset for ra */ 256 int ra_want; /* readahead count wanted */ 257 struct xfs_bmbt_irec map[]; /* map vector for blocks */ 258 }; 259 260 STATIC int 261 xfs_dir2_leaf_readbuf( 262 struct xfs_da_args *args, 263 size_t bufsize, 264 struct xfs_dir2_leaf_map_info *mip, 265 xfs_dir2_off_t *curoff, 266 struct xfs_buf **bpp, 267 bool trim_map) 268 { 269 struct xfs_inode *dp = args->dp; 270 struct xfs_buf *bp = NULL; 271 struct xfs_bmbt_irec *map = mip->map; 272 struct blk_plug plug; 273 int error = 0; 274 int length; 275 int i; 276 int j; 277 struct xfs_da_geometry *geo = args->geo; 278 279 /* 280 * If the caller just finished processing a buffer, it will tell us 281 * we need to trim that block out of the mapping now it is done. 282 */ 283 if (trim_map) { 284 mip->map_blocks -= geo->fsbcount; 285 /* 286 * Loop to get rid of the extents for the 287 * directory block. 288 */ 289 for (i = geo->fsbcount; i > 0; ) { 290 j = min_t(int, map->br_blockcount, i); 291 map->br_blockcount -= j; 292 map->br_startblock += j; 293 map->br_startoff += j; 294 /* 295 * If mapping is done, pitch it from 296 * the table. 297 */ 298 if (!map->br_blockcount && --mip->map_valid) 299 memmove(&map[0], &map[1], 300 sizeof(map[0]) * mip->map_valid); 301 i -= j; 302 } 303 } 304 305 /* 306 * Recalculate the readahead blocks wanted. 307 */ 308 mip->ra_want = howmany(bufsize + geo->blksize, (1 << geo->fsblog)) - 1; 309 ASSERT(mip->ra_want >= 0); 310 311 /* 312 * If we don't have as many as we want, and we haven't 313 * run out of data blocks, get some more mappings. 314 */ 315 if (1 + mip->ra_want > mip->map_blocks && 316 mip->map_off < xfs_dir2_byte_to_da(geo, XFS_DIR2_LEAF_OFFSET)) { 317 /* 318 * Get more bmaps, fill in after the ones 319 * we already have in the table. 320 */ 321 mip->nmap = mip->map_size - mip->map_valid; 322 error = xfs_bmapi_read(dp, mip->map_off, 323 xfs_dir2_byte_to_da(geo, XFS_DIR2_LEAF_OFFSET) - 324 mip->map_off, 325 &map[mip->map_valid], &mip->nmap, 0); 326 327 /* 328 * Don't know if we should ignore this or try to return an 329 * error. The trouble with returning errors is that readdir 330 * will just stop without actually passing the error through. 331 */ 332 if (error) 333 goto out; /* XXX */ 334 335 /* 336 * If we got all the mappings we asked for, set the final map 337 * offset based on the last bmap value received. Otherwise, 338 * we've reached the end. 339 */ 340 if (mip->nmap == mip->map_size - mip->map_valid) { 341 i = mip->map_valid + mip->nmap - 1; 342 mip->map_off = map[i].br_startoff + map[i].br_blockcount; 343 } else 344 mip->map_off = xfs_dir2_byte_to_da(geo, 345 XFS_DIR2_LEAF_OFFSET); 346 347 /* 348 * Look for holes in the mapping, and eliminate them. Count up 349 * the valid blocks. 350 */ 351 for (i = mip->map_valid; i < mip->map_valid + mip->nmap; ) { 352 if (map[i].br_startblock == HOLESTARTBLOCK) { 353 mip->nmap--; 354 length = mip->map_valid + mip->nmap - i; 355 if (length) 356 memmove(&map[i], &map[i + 1], 357 sizeof(map[i]) * length); 358 } else { 359 mip->map_blocks += map[i].br_blockcount; 360 i++; 361 } 362 } 363 mip->map_valid += mip->nmap; 364 } 365 366 /* 367 * No valid mappings, so no more data blocks. 368 */ 369 if (!mip->map_valid) { 370 *curoff = xfs_dir2_da_to_byte(geo, mip->map_off); 371 goto out; 372 } 373 374 /* 375 * Read the directory block starting at the first mapping. 376 */ 377 mip->curdb = xfs_dir2_da_to_db(geo, map->br_startoff); 378 error = xfs_dir3_data_read(NULL, dp, map->br_startoff, 379 map->br_blockcount >= geo->fsbcount ? 380 XFS_FSB_TO_DADDR(dp->i_mount, map->br_startblock) : 381 -1, &bp); 382 /* 383 * Should just skip over the data block instead of giving up. 384 */ 385 if (error) 386 goto out; /* XXX */ 387 388 /* 389 * Adjust the current amount of read-ahead: we just read a block that 390 * was previously ra. 391 */ 392 if (mip->ra_current) 393 mip->ra_current -= geo->fsbcount; 394 395 /* 396 * Do we need more readahead? 397 * Each loop tries to process 1 full dir blk; last may be partial. 398 */ 399 blk_start_plug(&plug); 400 for (mip->ra_index = mip->ra_offset = i = 0; 401 mip->ra_want > mip->ra_current && i < mip->map_blocks; 402 i += geo->fsbcount) { 403 ASSERT(mip->ra_index < mip->map_valid); 404 /* 405 * Read-ahead a contiguous directory block. 406 */ 407 if (i > mip->ra_current && 408 (map[mip->ra_index].br_blockcount - mip->ra_offset) >= 409 geo->fsbcount) { 410 xfs_dir3_data_readahead(dp, 411 map[mip->ra_index].br_startoff + mip->ra_offset, 412 XFS_FSB_TO_DADDR(dp->i_mount, 413 map[mip->ra_index].br_startblock + 414 mip->ra_offset)); 415 mip->ra_current = i; 416 } 417 418 /* 419 * Read-ahead a non-contiguous directory block. This doesn't 420 * use our mapping, but this is a very rare case. 421 */ 422 else if (i > mip->ra_current) { 423 xfs_dir3_data_readahead(dp, 424 map[mip->ra_index].br_startoff + 425 mip->ra_offset, -1); 426 mip->ra_current = i; 427 } 428 429 /* 430 * Advance offset through the mapping table, processing a full 431 * dir block even if it is fragmented into several extents. 432 * But stop if we have consumed all valid mappings, even if 433 * it's not yet a full directory block. 434 */ 435 for (j = 0; 436 j < geo->fsbcount && mip->ra_index < mip->map_valid; 437 j += length ) { 438 /* 439 * The rest of this extent but not more than a dir 440 * block. 441 */ 442 length = min_t(int, geo->fsbcount - j, 443 map[mip->ra_index].br_blockcount - 444 mip->ra_offset); 445 mip->ra_offset += length; 446 447 /* 448 * Advance to the next mapping if this one is used up. 449 */ 450 if (mip->ra_offset == map[mip->ra_index].br_blockcount) { 451 mip->ra_offset = 0; 452 mip->ra_index++; 453 } 454 } 455 } 456 blk_finish_plug(&plug); 457 458 out: 459 *bpp = bp; 460 return error; 461 } 462 463 /* 464 * Getdents (readdir) for leaf and node directories. 465 * This reads the data blocks only, so is the same for both forms. 466 */ 467 STATIC int 468 xfs_dir2_leaf_getdents( 469 struct xfs_da_args *args, 470 struct dir_context *ctx, 471 size_t bufsize) 472 { 473 struct xfs_inode *dp = args->dp; 474 struct xfs_buf *bp = NULL; /* data block buffer */ 475 xfs_dir2_data_hdr_t *hdr; /* data block header */ 476 xfs_dir2_data_entry_t *dep; /* data entry */ 477 xfs_dir2_data_unused_t *dup; /* unused entry */ 478 int error = 0; /* error return value */ 479 int length; /* temporary length value */ 480 int byteoff; /* offset in current block */ 481 xfs_dir2_off_t curoff; /* current overall offset */ 482 xfs_dir2_off_t newoff; /* new curoff after new blk */ 483 char *ptr = NULL; /* pointer to current data */ 484 struct xfs_dir2_leaf_map_info *map_info; 485 struct xfs_da_geometry *geo = args->geo; 486 487 /* 488 * If the offset is at or past the largest allowed value, 489 * give up right away. 490 */ 491 if (ctx->pos >= XFS_DIR2_MAX_DATAPTR) 492 return 0; 493 494 /* 495 * Set up to bmap a number of blocks based on the caller's 496 * buffer size, the directory block size, and the filesystem 497 * block size. 498 */ 499 length = howmany(bufsize + geo->blksize, (1 << geo->fsblog)); 500 map_info = kmem_zalloc(offsetof(struct xfs_dir2_leaf_map_info, map) + 501 (length * sizeof(struct xfs_bmbt_irec)), 502 KM_SLEEP | KM_NOFS); 503 map_info->map_size = length; 504 505 /* 506 * Inside the loop we keep the main offset value as a byte offset 507 * in the directory file. 508 */ 509 curoff = xfs_dir2_dataptr_to_byte(ctx->pos); 510 511 /* 512 * Force this conversion through db so we truncate the offset 513 * down to get the start of the data block. 514 */ 515 map_info->map_off = xfs_dir2_db_to_da(geo, 516 xfs_dir2_byte_to_db(geo, curoff)); 517 518 /* 519 * Loop over directory entries until we reach the end offset. 520 * Get more blocks and readahead as necessary. 521 */ 522 while (curoff < XFS_DIR2_LEAF_OFFSET) { 523 __uint8_t filetype; 524 525 /* 526 * If we have no buffer, or we're off the end of the 527 * current buffer, need to get another one. 528 */ 529 if (!bp || ptr >= (char *)bp->b_addr + geo->blksize) { 530 int lock_mode; 531 bool trim_map = false; 532 533 if (bp) { 534 xfs_trans_brelse(NULL, bp); 535 bp = NULL; 536 trim_map = true; 537 } 538 539 lock_mode = xfs_ilock_data_map_shared(dp); 540 error = xfs_dir2_leaf_readbuf(args, bufsize, map_info, 541 &curoff, &bp, trim_map); 542 xfs_iunlock(dp, lock_mode); 543 if (error || !map_info->map_valid) 544 break; 545 546 /* 547 * Having done a read, we need to set a new offset. 548 */ 549 newoff = xfs_dir2_db_off_to_byte(geo, 550 map_info->curdb, 0); 551 /* 552 * Start of the current block. 553 */ 554 if (curoff < newoff) 555 curoff = newoff; 556 /* 557 * Make sure we're in the right block. 558 */ 559 else if (curoff > newoff) 560 ASSERT(xfs_dir2_byte_to_db(geo, curoff) == 561 map_info->curdb); 562 hdr = bp->b_addr; 563 xfs_dir3_data_check(dp, bp); 564 /* 565 * Find our position in the block. 566 */ 567 ptr = (char *)dp->d_ops->data_entry_p(hdr); 568 byteoff = xfs_dir2_byte_to_off(geo, curoff); 569 /* 570 * Skip past the header. 571 */ 572 if (byteoff == 0) 573 curoff += dp->d_ops->data_entry_offset; 574 /* 575 * Skip past entries until we reach our offset. 576 */ 577 else { 578 while ((char *)ptr - (char *)hdr < byteoff) { 579 dup = (xfs_dir2_data_unused_t *)ptr; 580 581 if (be16_to_cpu(dup->freetag) 582 == XFS_DIR2_DATA_FREE_TAG) { 583 584 length = be16_to_cpu(dup->length); 585 ptr += length; 586 continue; 587 } 588 dep = (xfs_dir2_data_entry_t *)ptr; 589 length = 590 dp->d_ops->data_entsize(dep->namelen); 591 ptr += length; 592 } 593 /* 594 * Now set our real offset. 595 */ 596 curoff = 597 xfs_dir2_db_off_to_byte(geo, 598 xfs_dir2_byte_to_db(geo, curoff), 599 (char *)ptr - (char *)hdr); 600 if (ptr >= (char *)hdr + geo->blksize) { 601 continue; 602 } 603 } 604 } 605 /* 606 * We have a pointer to an entry. 607 * Is it a live one? 608 */ 609 dup = (xfs_dir2_data_unused_t *)ptr; 610 /* 611 * No, it's unused, skip over it. 612 */ 613 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 614 length = be16_to_cpu(dup->length); 615 ptr += length; 616 curoff += length; 617 continue; 618 } 619 620 dep = (xfs_dir2_data_entry_t *)ptr; 621 length = dp->d_ops->data_entsize(dep->namelen); 622 filetype = dp->d_ops->data_get_ftype(dep); 623 624 ctx->pos = xfs_dir2_byte_to_dataptr(curoff) & 0x7fffffff; 625 if (!dir_emit(ctx, (char *)dep->name, dep->namelen, 626 be64_to_cpu(dep->inumber), 627 xfs_dir3_get_dtype(dp->i_mount, filetype))) 628 break; 629 630 /* 631 * Advance to next entry in the block. 632 */ 633 ptr += length; 634 curoff += length; 635 /* bufsize may have just been a guess; don't go negative */ 636 bufsize = bufsize > length ? bufsize - length : 0; 637 } 638 639 /* 640 * All done. Set output offset value to current offset. 641 */ 642 if (curoff > xfs_dir2_dataptr_to_byte(XFS_DIR2_MAX_DATAPTR)) 643 ctx->pos = XFS_DIR2_MAX_DATAPTR & 0x7fffffff; 644 else 645 ctx->pos = xfs_dir2_byte_to_dataptr(curoff) & 0x7fffffff; 646 kmem_free(map_info); 647 if (bp) 648 xfs_trans_brelse(NULL, bp); 649 return error; 650 } 651 652 /* 653 * Read a directory. 654 */ 655 int 656 xfs_readdir( 657 struct xfs_inode *dp, 658 struct dir_context *ctx, 659 size_t bufsize) 660 { 661 struct xfs_da_args args = { NULL }; 662 int rval; 663 int v; 664 665 trace_xfs_readdir(dp); 666 667 if (XFS_FORCED_SHUTDOWN(dp->i_mount)) 668 return -EIO; 669 670 ASSERT(S_ISDIR(VFS_I(dp)->i_mode)); 671 XFS_STATS_INC(dp->i_mount, xs_dir_getdents); 672 673 args.dp = dp; 674 args.geo = dp->i_mount->m_dir_geo; 675 676 if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) 677 rval = xfs_dir2_sf_getdents(&args, ctx); 678 else if ((rval = xfs_dir2_isblock(&args, &v))) 679 ; 680 else if (v) 681 rval = xfs_dir2_block_getdents(&args, ctx); 682 else 683 rval = xfs_dir2_leaf_getdents(&args, ctx, bufsize); 684 685 return rval; 686 } 687