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