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