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