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 */ 398 blk_start_plug(&plug); 399 for (mip->ra_index = mip->ra_offset = i = 0; 400 mip->ra_want > mip->ra_current && i < mip->map_blocks; 401 i += geo->fsbcount) { 402 ASSERT(mip->ra_index < mip->map_valid); 403 /* 404 * Read-ahead a contiguous directory block. 405 */ 406 if (i > mip->ra_current && 407 map[mip->ra_index].br_blockcount >= geo->fsbcount) { 408 xfs_dir3_data_readahead(dp, 409 map[mip->ra_index].br_startoff + mip->ra_offset, 410 XFS_FSB_TO_DADDR(dp->i_mount, 411 map[mip->ra_index].br_startblock + 412 mip->ra_offset)); 413 mip->ra_current = i; 414 } 415 416 /* 417 * Read-ahead a non-contiguous directory block. This doesn't 418 * use our mapping, but this is a very rare case. 419 */ 420 else if (i > mip->ra_current) { 421 xfs_dir3_data_readahead(dp, 422 map[mip->ra_index].br_startoff + 423 mip->ra_offset, -1); 424 mip->ra_current = i; 425 } 426 427 /* 428 * Advance offset through the mapping table. 429 */ 430 for (j = 0; j < geo->fsbcount; j += length ) { 431 /* 432 * The rest of this extent but not more than a dir 433 * block. 434 */ 435 length = min_t(int, geo->fsbcount, 436 map[mip->ra_index].br_blockcount - 437 mip->ra_offset); 438 mip->ra_offset += length; 439 440 /* 441 * Advance to the next mapping if this one is used up. 442 */ 443 if (mip->ra_offset == map[mip->ra_index].br_blockcount) { 444 mip->ra_offset = 0; 445 mip->ra_index++; 446 } 447 } 448 } 449 blk_finish_plug(&plug); 450 451 out: 452 *bpp = bp; 453 return error; 454 } 455 456 /* 457 * Getdents (readdir) for leaf and node directories. 458 * This reads the data blocks only, so is the same for both forms. 459 */ 460 STATIC int 461 xfs_dir2_leaf_getdents( 462 struct xfs_da_args *args, 463 struct dir_context *ctx, 464 size_t bufsize) 465 { 466 struct xfs_inode *dp = args->dp; 467 struct xfs_buf *bp = NULL; /* data block buffer */ 468 xfs_dir2_data_hdr_t *hdr; /* data block header */ 469 xfs_dir2_data_entry_t *dep; /* data entry */ 470 xfs_dir2_data_unused_t *dup; /* unused entry */ 471 int error = 0; /* error return value */ 472 int length; /* temporary length value */ 473 int byteoff; /* offset in current block */ 474 xfs_dir2_off_t curoff; /* current overall offset */ 475 xfs_dir2_off_t newoff; /* new curoff after new blk */ 476 char *ptr = NULL; /* pointer to current data */ 477 struct xfs_dir2_leaf_map_info *map_info; 478 struct xfs_da_geometry *geo = args->geo; 479 480 /* 481 * If the offset is at or past the largest allowed value, 482 * give up right away. 483 */ 484 if (ctx->pos >= XFS_DIR2_MAX_DATAPTR) 485 return 0; 486 487 /* 488 * Set up to bmap a number of blocks based on the caller's 489 * buffer size, the directory block size, and the filesystem 490 * block size. 491 */ 492 length = howmany(bufsize + geo->blksize, (1 << geo->fsblog)); 493 map_info = kmem_zalloc(offsetof(struct xfs_dir2_leaf_map_info, map) + 494 (length * sizeof(struct xfs_bmbt_irec)), 495 KM_SLEEP | KM_NOFS); 496 map_info->map_size = length; 497 498 /* 499 * Inside the loop we keep the main offset value as a byte offset 500 * in the directory file. 501 */ 502 curoff = xfs_dir2_dataptr_to_byte(ctx->pos); 503 504 /* 505 * Force this conversion through db so we truncate the offset 506 * down to get the start of the data block. 507 */ 508 map_info->map_off = xfs_dir2_db_to_da(geo, 509 xfs_dir2_byte_to_db(geo, curoff)); 510 511 /* 512 * Loop over directory entries until we reach the end offset. 513 * Get more blocks and readahead as necessary. 514 */ 515 while (curoff < XFS_DIR2_LEAF_OFFSET) { 516 __uint8_t filetype; 517 518 /* 519 * If we have no buffer, or we're off the end of the 520 * current buffer, need to get another one. 521 */ 522 if (!bp || ptr >= (char *)bp->b_addr + geo->blksize) { 523 int lock_mode; 524 bool trim_map = false; 525 526 if (bp) { 527 xfs_trans_brelse(NULL, bp); 528 bp = NULL; 529 trim_map = true; 530 } 531 532 lock_mode = xfs_ilock_data_map_shared(dp); 533 error = xfs_dir2_leaf_readbuf(args, bufsize, map_info, 534 &curoff, &bp, trim_map); 535 xfs_iunlock(dp, lock_mode); 536 if (error || !map_info->map_valid) 537 break; 538 539 /* 540 * Having done a read, we need to set a new offset. 541 */ 542 newoff = xfs_dir2_db_off_to_byte(geo, 543 map_info->curdb, 0); 544 /* 545 * Start of the current block. 546 */ 547 if (curoff < newoff) 548 curoff = newoff; 549 /* 550 * Make sure we're in the right block. 551 */ 552 else if (curoff > newoff) 553 ASSERT(xfs_dir2_byte_to_db(geo, curoff) == 554 map_info->curdb); 555 hdr = bp->b_addr; 556 xfs_dir3_data_check(dp, bp); 557 /* 558 * Find our position in the block. 559 */ 560 ptr = (char *)dp->d_ops->data_entry_p(hdr); 561 byteoff = xfs_dir2_byte_to_off(geo, curoff); 562 /* 563 * Skip past the header. 564 */ 565 if (byteoff == 0) 566 curoff += dp->d_ops->data_entry_offset; 567 /* 568 * Skip past entries until we reach our offset. 569 */ 570 else { 571 while ((char *)ptr - (char *)hdr < byteoff) { 572 dup = (xfs_dir2_data_unused_t *)ptr; 573 574 if (be16_to_cpu(dup->freetag) 575 == XFS_DIR2_DATA_FREE_TAG) { 576 577 length = be16_to_cpu(dup->length); 578 ptr += length; 579 continue; 580 } 581 dep = (xfs_dir2_data_entry_t *)ptr; 582 length = 583 dp->d_ops->data_entsize(dep->namelen); 584 ptr += length; 585 } 586 /* 587 * Now set our real offset. 588 */ 589 curoff = 590 xfs_dir2_db_off_to_byte(geo, 591 xfs_dir2_byte_to_db(geo, curoff), 592 (char *)ptr - (char *)hdr); 593 if (ptr >= (char *)hdr + geo->blksize) { 594 continue; 595 } 596 } 597 } 598 /* 599 * We have a pointer to an entry. 600 * Is it a live one? 601 */ 602 dup = (xfs_dir2_data_unused_t *)ptr; 603 /* 604 * No, it's unused, skip over it. 605 */ 606 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 607 length = be16_to_cpu(dup->length); 608 ptr += length; 609 curoff += length; 610 continue; 611 } 612 613 dep = (xfs_dir2_data_entry_t *)ptr; 614 length = dp->d_ops->data_entsize(dep->namelen); 615 filetype = dp->d_ops->data_get_ftype(dep); 616 617 ctx->pos = xfs_dir2_byte_to_dataptr(curoff) & 0x7fffffff; 618 if (!dir_emit(ctx, (char *)dep->name, dep->namelen, 619 be64_to_cpu(dep->inumber), 620 xfs_dir3_get_dtype(dp->i_mount, filetype))) 621 break; 622 623 /* 624 * Advance to next entry in the block. 625 */ 626 ptr += length; 627 curoff += length; 628 /* bufsize may have just been a guess; don't go negative */ 629 bufsize = bufsize > length ? bufsize - length : 0; 630 } 631 632 /* 633 * All done. Set output offset value to current offset. 634 */ 635 if (curoff > xfs_dir2_dataptr_to_byte(XFS_DIR2_MAX_DATAPTR)) 636 ctx->pos = XFS_DIR2_MAX_DATAPTR & 0x7fffffff; 637 else 638 ctx->pos = xfs_dir2_byte_to_dataptr(curoff) & 0x7fffffff; 639 kmem_free(map_info); 640 if (bp) 641 xfs_trans_brelse(NULL, bp); 642 return error; 643 } 644 645 /* 646 * Read a directory. 647 */ 648 int 649 xfs_readdir( 650 struct xfs_inode *dp, 651 struct dir_context *ctx, 652 size_t bufsize) 653 { 654 struct xfs_da_args args = { NULL }; 655 int rval; 656 int v; 657 658 trace_xfs_readdir(dp); 659 660 if (XFS_FORCED_SHUTDOWN(dp->i_mount)) 661 return -EIO; 662 663 ASSERT(S_ISDIR(VFS_I(dp)->i_mode)); 664 XFS_STATS_INC(dp->i_mount, xs_dir_getdents); 665 666 args.dp = dp; 667 args.geo = dp->i_mount->m_dir_geo; 668 669 if (dp->i_d.di_format == XFS_DINODE_FMT_LOCAL) 670 rval = xfs_dir2_sf_getdents(&args, ctx); 671 else if ((rval = xfs_dir2_isblock(&args, &v))) 672 ; 673 else if (v) 674 rval = xfs_dir2_block_getdents(&args, ctx); 675 else 676 rval = xfs_dir2_leaf_getdents(&args, ctx, bufsize); 677 678 return rval; 679 } 680