1 /* 2 * Copyright (c) 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * (c) UNIX System Laboratories, Inc. 5 * All or some portions of this file are derived from material licensed 6 * to the University of California by American Telephone and Telegraph 7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8 * the permission of UNIX System Laboratories, Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 * @(#)ufs_lookup.c 8.15 (Berkeley) 6/16/95 35 * $FreeBSD: src/sys/ufs/ufs/ufs_lookup.c,v 1.33.2.7 2001/09/22 19:22:13 iedowse Exp $ 36 */ 37 38 #include "opt_ufs.h" 39 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/kernel.h> 43 #include <sys/buf.h> 44 #include <sys/proc.h> 45 #include <sys/namei.h> 46 #include <sys/stat.h> 47 #include <sys/mount.h> 48 #include <sys/vnode.h> 49 #include <sys/sysctl.h> 50 51 #include <vm/vm.h> 52 #include <vm/vm_extern.h> 53 54 #include "quota.h" 55 #include "inode.h" 56 #include "dir.h" 57 #ifdef UFS_DIRHASH 58 #include "dirhash.h" 59 #endif 60 #include "ufsmount.h" 61 #include "ufs_extern.h" 62 #include "ffs_extern.h" 63 64 #ifdef DIAGNOSTIC 65 int dirchk = 1; 66 #else 67 int dirchk = 0; 68 #endif 69 70 SYSCTL_INT(_debug, OID_AUTO, dircheck, CTLFLAG_RW, &dirchk, 0, 71 "Enable full validation checks of directory"); 72 73 /* true if old FS format...*/ 74 #define OFSFMT(vp) ((vp)->v_mount->mnt_maxsymlinklen <= 0) 75 76 /* 77 * Convert a component of a pathname into a pointer to a locked inode. 78 * This is a very central and rather complicated routine. 79 * If the filesystem is not maintained in a strict tree hierarchy, 80 * this can result in a deadlock situation (see comments in code below). 81 * 82 * The cnp->cn_nameiop argument is LOOKUP, CREATE, RENAME, or DELETE depending 83 * on whether the name is to be looked up, created, renamed, or deleted. 84 * When CREATE, RENAME, or DELETE is specified, information usable in 85 * creating, renaming, or deleting a directory entry may be calculated. 86 * If flag has LOCKPARENT or'ed into it and the target of the pathname 87 * exists, lookup returns both the target and its parent directory locked. 88 * When creating or renaming and LOCKPARENT is specified, the target may 89 * not be ".". When deleting and LOCKPARENT is specified, the target may 90 * be "."., but the caller must check to ensure it does an vrele and vput 91 * instead of two vputs. 92 * 93 * Overall outline of ufs_lookup: 94 * 95 * search for name in directory, to found or notfound 96 * notfound: 97 * if creating, return locked directory, leaving info on available slots 98 * else return error 99 * found: 100 * if at end of path and deleting, return information to allow delete 101 * if at end of path and rewriting (RENAME and LOCKPARENT), lock target 102 * inode and return info to allow rewrite 103 * if not at end, add name to cache; if at end and neither creating 104 * nor deleting, add name to cache 105 * 106 * ufs_lookup(struct vnode *a_dvp, struct vnode **a_vpp, 107 * struct componentname *a_cnp) 108 */ 109 int 110 ufs_lookup(struct vop_old_lookup_args *ap) 111 { 112 struct vnode *vdp; /* vnode for directory being searched */ 113 struct inode *dp; /* inode for directory being searched */ 114 struct buf *bp; /* a buffer of directory entries */ 115 struct direct *ep; /* the current directory entry */ 116 int entryoffsetinblock; /* offset of ep in bp's buffer */ 117 enum {NONE, COMPACT, FOUND} slotstatus; 118 doff_t slotoffset; /* offset of area with free space */ 119 int slotsize; /* size of area at slotoffset */ 120 int slotfreespace; /* amount of space free in slot */ 121 int slotneeded; /* size of the entry we're seeking */ 122 int numdirpasses; /* strategy for directory search */ 123 doff_t endsearch; /* offset to end directory search */ 124 doff_t prevoff; /* prev entry dp->i_offset */ 125 struct vnode *pdp; /* saved dp during symlink work */ 126 struct vnode *tdp; /* returned by VFS_VGET */ 127 doff_t enduseful; /* pointer past last used dir slot */ 128 u_long bmask; /* block offset mask */ 129 int lockparent; /* 1 => lockparent flag is set */ 130 int wantparent; /* 1 => wantparent or lockparent flag */ 131 int namlen, error; 132 struct vnode **vpp = ap->a_vpp; 133 struct componentname *cnp = ap->a_cnp; 134 struct ucred *cred = cnp->cn_cred; 135 int flags = cnp->cn_flags; 136 int nameiop = cnp->cn_nameiop; 137 138 bp = NULL; 139 slotoffset = -1; 140 cnp->cn_flags &= ~CNP_PDIRUNLOCK; 141 /* 142 * XXX there was a soft-update diff about this I couldn't merge. 143 * I think this was the equiv. 144 */ 145 *vpp = NULL; 146 147 vdp = ap->a_dvp; 148 dp = VTOI(vdp); 149 lockparent = flags & CNP_LOCKPARENT; 150 wantparent = flags & (CNP_LOCKPARENT|CNP_WANTPARENT); 151 152 /* 153 * We now have a segment name to search for, and a directory to search. 154 * 155 * Suppress search for slots unless creating 156 * file and at end of pathname, in which case 157 * we watch for a place to put the new file in 158 * case it doesn't already exist. 159 */ 160 slotstatus = FOUND; 161 slotfreespace = slotsize = slotneeded = 0; 162 if (nameiop == NAMEI_CREATE || nameiop == NAMEI_RENAME) { 163 slotstatus = NONE; 164 slotneeded = DIRECTSIZ(cnp->cn_namelen); 165 } 166 bmask = VFSTOUFS(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1; 167 168 #ifdef UFS_DIRHASH 169 /* 170 * Use dirhash for fast operations on large directories. The logic 171 * to determine whether to hash the directory is contained within 172 * ufsdirhash_build(); a zero return means that it decided to hash 173 * this directory and it successfully built up the hash table. 174 */ 175 if (ufsdirhash_build(dp) == 0) { 176 /* Look for a free slot if needed. */ 177 enduseful = dp->i_size; 178 if (slotstatus != FOUND) { 179 slotoffset = ufsdirhash_findfree(dp, slotneeded, 180 &slotsize); 181 if (slotoffset >= 0) { 182 slotstatus = COMPACT; 183 enduseful = ufsdirhash_enduseful(dp); 184 if (enduseful < 0) 185 enduseful = dp->i_size; 186 } 187 } 188 /* Look up the component. */ 189 numdirpasses = 1; 190 entryoffsetinblock = 0; /* silence compiler warning */ 191 switch (ufsdirhash_lookup(dp, cnp->cn_nameptr, cnp->cn_namelen, 192 &dp->i_offset, &bp, nameiop == NAMEI_DELETE ? &prevoff : NULL)) { 193 case 0: 194 ep = (struct direct *)((char *)bp->b_data + 195 (dp->i_offset & bmask)); 196 goto foundentry; 197 case ENOENT: 198 dp->i_offset = roundup2(dp->i_size, DIRBLKSIZ); 199 goto notfound; 200 default: 201 /* Something failed; just do a linear search. */ 202 break; 203 } 204 } 205 #endif /* UFS_DIRHASH */ 206 /* 207 * If there is cached information on a previous search of 208 * this directory, pick up where we last left off. 209 * We cache only lookups as these are the most common 210 * and have the greatest payoff. Caching CREATE has little 211 * benefit as it usually must search the entire directory 212 * to determine that the entry does not exist. Caching the 213 * location of the last DELETE or RENAME has not reduced 214 * profiling time and hence has been removed in the interest 215 * of simplicity. 216 */ 217 if (nameiop != NAMEI_LOOKUP || dp->i_diroff == 0 || 218 dp->i_diroff >= dp->i_size) { 219 entryoffsetinblock = 0; 220 dp->i_offset = 0; 221 numdirpasses = 1; 222 } else { 223 dp->i_offset = dp->i_diroff; 224 if ((entryoffsetinblock = dp->i_offset & bmask) && 225 (error = ffs_blkatoff(vdp, (off_t)dp->i_offset, NULL, &bp))) 226 return (error); 227 numdirpasses = 2; 228 } 229 prevoff = dp->i_offset; 230 endsearch = roundup2(dp->i_size, DIRBLKSIZ); 231 enduseful = 0; 232 233 searchloop: 234 while (dp->i_offset < endsearch) { 235 /* 236 * If necessary, get the next directory block. 237 */ 238 if ((dp->i_offset & bmask) == 0) { 239 if (bp != NULL) 240 brelse(bp); 241 error = 242 ffs_blkatoff(vdp, (off_t)dp->i_offset, NULL, &bp); 243 if (error) 244 return (error); 245 entryoffsetinblock = 0; 246 } 247 /* 248 * If still looking for a slot, and at a DIRBLKSIZE 249 * boundary, have to start looking for free space again. 250 */ 251 if (slotstatus == NONE && 252 (entryoffsetinblock & (DIRBLKSIZ - 1)) == 0) { 253 slotoffset = -1; 254 slotfreespace = 0; 255 } 256 /* 257 * Get pointer to next entry. 258 * Full validation checks are slow, so we only check 259 * enough to insure forward progress through the 260 * directory. Complete checks can be run by patching 261 * "dirchk" to be true. 262 */ 263 ep = (struct direct *)((char *)bp->b_data + entryoffsetinblock); 264 if (ep->d_reclen == 0 || ep->d_reclen > 265 DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)) || 266 (dirchk && ufs_dirbadentry(vdp, ep, entryoffsetinblock))) { 267 int i; 268 269 ufs_dirbad(dp, dp->i_offset, "mangled entry"); 270 i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)); 271 dp->i_offset += i; 272 entryoffsetinblock += i; 273 continue; 274 } 275 276 /* 277 * If an appropriate sized slot has not yet been found, 278 * check to see if one is available. Also accumulate space 279 * in the current block so that we can determine if 280 * compaction is viable. 281 */ 282 if (slotstatus != FOUND) { 283 int size = ep->d_reclen; 284 285 if (ep->d_ino != 0) 286 size -= DIRSIZ(OFSFMT(vdp), ep); 287 if (size > 0) { 288 if (size >= slotneeded) { 289 slotstatus = FOUND; 290 slotoffset = dp->i_offset; 291 slotsize = ep->d_reclen; 292 } else if (slotstatus == NONE) { 293 slotfreespace += size; 294 if (slotoffset == -1) 295 slotoffset = dp->i_offset; 296 if (slotfreespace >= slotneeded) { 297 slotstatus = COMPACT; 298 slotsize = dp->i_offset + 299 ep->d_reclen - slotoffset; 300 } 301 } 302 } 303 } 304 305 /* 306 * Check for a name match. 307 */ 308 if (ep->d_ino) { 309 # if (BYTE_ORDER == LITTLE_ENDIAN) 310 if (OFSFMT(vdp)) 311 namlen = ep->d_type; 312 else 313 namlen = ep->d_namlen; 314 # else 315 namlen = ep->d_namlen; 316 # endif 317 if (namlen == cnp->cn_namelen && 318 (cnp->cn_nameptr[0] == ep->d_name[0]) && 319 !bcmp(cnp->cn_nameptr, ep->d_name, 320 (unsigned)namlen)) { 321 #ifdef UFS_DIRHASH 322 foundentry: 323 #endif 324 /* 325 * Save directory entry's inode number and 326 * reclen in ndp->ni_ufs area, and release 327 * directory buffer. 328 */ 329 if (vdp->v_mount->mnt_maxsymlinklen > 0 && 330 ep->d_type == DT_WHT) { 331 slotstatus = FOUND; 332 slotoffset = dp->i_offset; 333 slotsize = ep->d_reclen; 334 dp->i_reclen = slotsize; 335 enduseful = dp->i_size; 336 ap->a_cnp->cn_flags |= CNP_ISWHITEOUT; 337 numdirpasses--; 338 goto notfound; 339 } 340 dp->i_ino = ep->d_ino; 341 dp->i_reclen = ep->d_reclen; 342 goto found; 343 } 344 } 345 prevoff = dp->i_offset; 346 dp->i_offset += ep->d_reclen; 347 entryoffsetinblock += ep->d_reclen; 348 if (ep->d_ino) 349 enduseful = dp->i_offset; 350 } 351 notfound: 352 /* 353 * If we started in the middle of the directory and failed 354 * to find our target, we must check the beginning as well. 355 */ 356 if (numdirpasses == 2) { 357 numdirpasses--; 358 dp->i_offset = 0; 359 endsearch = dp->i_diroff; 360 goto searchloop; 361 } 362 if (bp != NULL) 363 brelse(bp); 364 /* 365 * If creating, and at end of pathname and current 366 * directory has not been removed, then can consider 367 * allowing file to be created. 368 */ 369 if ((nameiop == NAMEI_CREATE || nameiop == NAMEI_RENAME || 370 (nameiop == NAMEI_DELETE && 371 (ap->a_cnp->cn_flags & CNP_DOWHITEOUT) && 372 (ap->a_cnp->cn_flags & CNP_ISWHITEOUT))) && 373 dp->i_effnlink != 0) { 374 /* 375 * Access for write is interpreted as allowing 376 * creation of files in the directory. 377 */ 378 error = VOP_EACCESS(vdp, VWRITE, cred); 379 if (error) 380 return (error); 381 /* 382 * Return an indication of where the new directory 383 * entry should be put. If we didn't find a slot, 384 * then set dp->i_count to 0 indicating 385 * that the new slot belongs at the end of the 386 * directory. If we found a slot, then the new entry 387 * can be put in the range from dp->i_offset to 388 * dp->i_offset + dp->i_count. 389 */ 390 if (slotstatus == NONE) { 391 dp->i_offset = roundup2(dp->i_size, DIRBLKSIZ); 392 dp->i_count = 0; 393 enduseful = dp->i_offset; 394 } else if (nameiop == NAMEI_DELETE) { 395 dp->i_offset = slotoffset; 396 if ((dp->i_offset & (DIRBLKSIZ - 1)) == 0) 397 dp->i_count = 0; 398 else 399 dp->i_count = dp->i_offset - prevoff; 400 } else { 401 dp->i_offset = slotoffset; 402 dp->i_count = slotsize; 403 if (enduseful < slotoffset + slotsize) 404 enduseful = slotoffset + slotsize; 405 } 406 dp->i_endoff = roundup2(enduseful, DIRBLKSIZ); 407 dp->i_flag |= IN_CHANGE | IN_UPDATE; 408 /* 409 * We return with the directory locked, so that 410 * the parameters we set up above will still be 411 * valid if we actually decide to do a direnter(). 412 * We return ni_vp == NULL to indicate that the entry 413 * does not currently exist; we leave a pointer to 414 * the (locked) directory inode in ndp->ni_dvp. 415 * The pathname buffer is saved so that the name 416 * can be obtained later. 417 * 418 * NB - if the directory is unlocked, then this 419 * information cannot be used. 420 */ 421 if (!lockparent) { 422 vn_unlock(vdp); 423 cnp->cn_flags |= CNP_PDIRUNLOCK; 424 } 425 return (EJUSTRETURN); 426 } 427 return (ENOENT); 428 429 found: 430 /* 431 * Check that directory length properly reflects presence 432 * of this entry. 433 */ 434 if (dp->i_offset + DIRSIZ(OFSFMT(vdp), ep) > dp->i_size) { 435 ufs_dirbad(dp, dp->i_offset, "i_size too small"); 436 dp->i_size = dp->i_offset + DIRSIZ(OFSFMT(vdp), ep); 437 dp->i_flag |= IN_CHANGE | IN_UPDATE; 438 } 439 brelse(bp); 440 441 /* 442 * Found component in pathname. 443 * If the final component of path name, save information 444 * in the cache as to where the entry was found. 445 */ 446 if (nameiop == NAMEI_LOOKUP) 447 dp->i_diroff = rounddown2(dp->i_offset, DIRBLKSIZ); 448 449 /* 450 * If deleting, and at end of pathname, return 451 * parameters which can be used to remove file. 452 * If the wantparent flag isn't set, we return only 453 * the directory (in ndp->ni_dvp), otherwise we go 454 * on and lock the inode, being careful with ".". 455 */ 456 if (nameiop == NAMEI_DELETE) { 457 /* 458 * Write access to directory required to delete files. 459 */ 460 error = VOP_EACCESS(vdp, VWRITE, cred); 461 if (error) 462 return (error); 463 /* 464 * Return pointer to current entry in dp->i_offset, 465 * and distance past previous entry (if there 466 * is a previous entry in this block) in dp->i_count. 467 * Save directory inode pointer in ndp->ni_dvp for dirremove(). 468 */ 469 if ((dp->i_offset & (DIRBLKSIZ - 1)) == 0) 470 dp->i_count = 0; 471 else 472 dp->i_count = dp->i_offset - prevoff; 473 if (dp->i_number == dp->i_ino) { 474 vref(vdp); 475 *vpp = vdp; 476 return (0); 477 } 478 if (flags & CNP_ISDOTDOT) 479 vn_unlock(vdp); /* race to get the inode */ 480 error = VFS_VGET(vdp->v_mount, NULL, dp->i_ino, &tdp); 481 if (flags & CNP_ISDOTDOT) { 482 if (vn_lock(vdp, LK_EXCLUSIVE | LK_RETRY | 483 LK_FAILRECLAIM) != 0) { 484 cnp->cn_flags |= CNP_PDIRUNLOCK; 485 } 486 } 487 if (error) 488 return (error); 489 /* 490 * If directory is "sticky", then user must own 491 * the directory, or the file in it, else she 492 * may not delete it (unless she's root). This 493 * implements append-only directories. 494 */ 495 if ((dp->i_mode & ISVTX) && 496 cred->cr_uid != 0 && 497 cred->cr_uid != dp->i_uid && 498 VTOI(tdp)->i_uid != cred->cr_uid) { 499 vput(tdp); 500 return (EPERM); 501 } 502 *vpp = tdp; 503 if (!lockparent) { 504 vn_unlock(vdp); 505 cnp->cn_flags |= CNP_PDIRUNLOCK; 506 } 507 return (0); 508 } 509 510 /* 511 * If rewriting (RENAME), return the inode and the 512 * information required to rewrite the present directory 513 * Must get inode of directory entry to verify it's a 514 * regular file, or empty directory. 515 */ 516 if (nameiop == NAMEI_RENAME && wantparent) { 517 if ((error = VOP_EACCESS(vdp, VWRITE, cred)) != 0) 518 return (error); 519 /* 520 * Careful about locking second inode. 521 * This can only occur if the target is ".". 522 */ 523 if (dp->i_number == dp->i_ino) 524 return (EISDIR); 525 if (flags & CNP_ISDOTDOT) 526 vn_unlock(vdp); /* race to get the inode */ 527 error = VFS_VGET(vdp->v_mount, NULL, dp->i_ino, &tdp); 528 if (flags & CNP_ISDOTDOT) { 529 if (vn_lock(vdp, LK_EXCLUSIVE | LK_RETRY | 530 LK_FAILRECLAIM) != 0) { 531 cnp->cn_flags |= CNP_PDIRUNLOCK; 532 } 533 } 534 if (error) 535 return (error); 536 *vpp = tdp; 537 if (!lockparent) { 538 vn_unlock(vdp); 539 cnp->cn_flags |= CNP_PDIRUNLOCK; 540 } 541 return (0); 542 } 543 544 /* 545 * Step through the translation in the name. We do not `vput' the 546 * directory because we may need it again if a symbolic link 547 * is relative to the current directory. Instead we save it 548 * unlocked as "pdp". We must get the target inode before unlocking 549 * the directory to insure that the inode will not be removed 550 * before we get it. We prevent deadlock by always fetching 551 * inodes from the root, moving down the directory tree. Thus 552 * when following backward pointers ".." we must unlock the 553 * parent directory before getting the requested directory. 554 * There is a potential race condition here if both the current 555 * and parent directories are removed before the VFS_VGET for the 556 * inode associated with ".." returns. We hope that this occurs 557 * infrequently since we cannot avoid this race condition without 558 * implementing a sophisticated deadlock detection algorithm. 559 * Note also that this simple deadlock detection scheme will not 560 * work if the filesystem has any hard links other than ".." 561 * that point backwards in the directory structure. 562 */ 563 pdp = vdp; 564 if (flags & CNP_ISDOTDOT) { 565 vn_unlock(pdp); /* race to get the inode */ 566 cnp->cn_flags |= CNP_PDIRUNLOCK; 567 error = VFS_VGET(vdp->v_mount, NULL, dp->i_ino, &tdp); 568 if (error) { 569 if (vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY | 570 LK_FAILRECLAIM) == 0) { 571 cnp->cn_flags &= ~CNP_PDIRUNLOCK; 572 } 573 return (error); 574 } 575 if (lockparent) { 576 error = vn_lock(pdp, LK_EXCLUSIVE | LK_FAILRECLAIM); 577 if (error) { 578 vput(tdp); 579 return (error); 580 } 581 cnp->cn_flags &= ~CNP_PDIRUNLOCK; 582 } 583 *vpp = tdp; 584 } else if (dp->i_number == dp->i_ino) { 585 vref(vdp); /* we want ourself, ie "." */ 586 *vpp = vdp; 587 } else { 588 error = VFS_VGET(vdp->v_mount, NULL, dp->i_ino, &tdp); 589 if (error) 590 return (error); 591 if (!lockparent) { 592 vn_unlock(pdp); 593 cnp->cn_flags |= CNP_PDIRUNLOCK; 594 } 595 *vpp = tdp; 596 } 597 return (0); 598 } 599 600 void 601 ufs_dirbad(struct inode *ip, doff_t offset, char *how) 602 { 603 struct mount *mp; 604 605 mp = ITOV(ip)->v_mount; 606 (void)kprintf("%s: bad dir ino %lu at offset %ld: %s\n", 607 mp->mnt_stat.f_mntfromname, (u_long)ip->i_number, (long)offset, how); 608 if ((mp->mnt_flag & MNT_RDONLY) == 0) 609 panic("ufs_dirbad: bad dir"); 610 } 611 612 /* 613 * Do consistency checking on a directory entry: 614 * record length must be multiple of 4 615 * entry must fit in rest of its DIRBLKSIZ block 616 * record must be large enough to contain entry 617 * name is not longer than MAXNAMLEN 618 * name must be as long as advertised, and null terminated 619 */ 620 int 621 ufs_dirbadentry(struct vnode *dp, struct direct *ep, int entryoffsetinblock) 622 { 623 int i; 624 int namlen; 625 626 # if (BYTE_ORDER == LITTLE_ENDIAN) 627 if (OFSFMT(dp)) 628 namlen = ep->d_type; 629 else 630 namlen = ep->d_namlen; 631 # else 632 namlen = ep->d_namlen; 633 # endif 634 if ((ep->d_reclen & 0x3) != 0 || 635 ep->d_reclen > DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)) || 636 ep->d_reclen < DIRSIZ(OFSFMT(dp), ep) || namlen > MAXNAMLEN) { 637 /*return (1); */ 638 kprintf("First bad\n"); 639 goto bad; 640 } 641 if (ep->d_ino == 0) 642 return (0); 643 for (i = 0; i < namlen; i++) 644 if (ep->d_name[i] == '\0') { 645 /*return (1); */ 646 kprintf("Second bad\n"); 647 goto bad; 648 } 649 if (ep->d_name[i]) 650 goto bad; 651 return (0); 652 bad: 653 return (1); 654 } 655 656 /* 657 * Construct a new directory entry after a call to namei, using the 658 * parameters that it left in the componentname argument cnp. The 659 * argument ip is the inode to which the new directory entry will refer. 660 */ 661 void 662 ufs_makedirentry(struct inode *ip, struct componentname *cnp, 663 struct direct *newdirp) 664 { 665 666 newdirp->d_ino = ip->i_number; 667 newdirp->d_namlen = cnp->cn_namelen; 668 bcopy(cnp->cn_nameptr, newdirp->d_name, (unsigned)cnp->cn_namelen + 1); 669 if (ITOV(ip)->v_mount->mnt_maxsymlinklen > 0) 670 newdirp->d_type = IFTODT(ip->i_mode); 671 else { 672 newdirp->d_type = 0; 673 # if (BYTE_ORDER == LITTLE_ENDIAN) 674 { u_char tmp = newdirp->d_namlen; 675 newdirp->d_namlen = newdirp->d_type; 676 newdirp->d_type = tmp; } 677 # endif 678 } 679 } 680 681 /* 682 * Write a directory entry after a call to namei, using the parameters 683 * that it left in the directory inode. The argument dirp is the new directory 684 * entry contents. Dvp is a pointer to the directory to be written, 685 * which was left locked by namei. Remaining parameters (dp->i_offset, 686 * dp->i_count) indicate how the space for the new entry is to be obtained. 687 * Non-null bp indicates that a directory is being created (for the 688 * soft dependency code). 689 */ 690 int 691 ufs_direnter(struct vnode *dvp, struct vnode *tvp, struct direct *dirp, 692 struct componentname *cnp, struct buf *newdirbp) 693 { 694 struct ucred *cred; 695 int newentrysize; 696 struct inode *dp; 697 struct buf *bp; 698 uint dsize; 699 struct direct *ep, *nep; 700 int error, ret, blkoff, loc, spacefree, flags; 701 char *dirbuf; 702 703 cred = cnp->cn_cred; 704 KKASSERT(cred != NULL); 705 706 dp = VTOI(dvp); 707 newentrysize = DIRSIZ(OFSFMT(dvp), dirp); 708 709 if (dp->i_count == 0) { 710 /* 711 * If dp->i_count is 0, then namei could find no 712 * space in the directory. Here, dp->i_offset will 713 * be on a directory block boundary and we will write the 714 * new entry into a fresh block. 715 */ 716 if (dp->i_offset & (DIRBLKSIZ - 1)) 717 panic("ufs_direnter: newblk"); 718 nvnode_pager_setsize(dvp, dp->i_offset + DIRBLKSIZ, 719 DIRBLKSIZ, -1); 720 flags = B_CLRBUF; 721 if (!DOINGSOFTDEP(dvp) && !DOINGASYNC(dvp)) 722 flags |= B_SYNC; 723 if ((error = VOP_BALLOC(dvp, (off_t)dp->i_offset, DIRBLKSIZ, 724 cred, flags, &bp)) != 0) { 725 if (DOINGSOFTDEP(dvp) && newdirbp != NULL) 726 bdwrite(newdirbp); 727 return (error); 728 } 729 dp->i_size = dp->i_offset + DIRBLKSIZ; 730 dp->i_flag |= IN_CHANGE | IN_UPDATE; 731 dirp->d_reclen = DIRBLKSIZ; 732 blkoff = dp->i_offset & 733 (VFSTOUFS(dvp->v_mount)->um_mountp->mnt_stat.f_iosize - 1); 734 bcopy((caddr_t)dirp, (caddr_t)bp->b_data + blkoff,newentrysize); 735 #ifdef UFS_DIRHASH 736 if (dp->i_dirhash != NULL) { 737 ufsdirhash_newblk(dp, dp->i_offset); 738 ufsdirhash_add(dp, dirp, dp->i_offset); 739 ufsdirhash_checkblock(dp, (char *)bp->b_data + blkoff, 740 dp->i_offset); 741 } 742 #endif 743 if (DOINGSOFTDEP(dvp)) { 744 /* 745 * Ensure that the entire newly allocated block is a 746 * valid directory so that future growth within the 747 * block does not have to ensure that the block is 748 * written before the inode. 749 */ 750 blkoff += DIRBLKSIZ; 751 while (blkoff < bp->b_bcount) { 752 ((struct direct *) 753 (bp->b_data + blkoff))->d_reclen = DIRBLKSIZ; 754 blkoff += DIRBLKSIZ; 755 } 756 softdep_setup_directory_add(bp, dp, dp->i_offset, 757 dirp->d_ino, newdirbp); 758 bdwrite(bp); 759 return (ffs_update(dvp, 0)); 760 } 761 if (DOINGASYNC(dvp)) { 762 bdwrite(bp); 763 return (ffs_update(dvp, 0)); 764 } 765 error = bwrite(bp); 766 ret = ffs_update(dvp, 1); 767 if (error == 0) 768 return (ret); 769 return (error); 770 } 771 772 /* 773 * If dp->i_count is non-zero, then namei found space for the new 774 * entry in the range dp->i_offset to dp->i_offset + dp->i_count 775 * in the directory. To use this space, we may have to compact 776 * the entries located there, by copying them together towards the 777 * beginning of the block, leaving the free space in one usable 778 * chunk at the end. 779 */ 780 781 /* 782 * Increase size of directory if entry eats into new space. 783 * This should never push the size past a new multiple of 784 * DIRBLKSIZE. 785 * 786 * N.B. - THIS IS AN ARTIFACT OF 4.2 AND SHOULD NEVER HAPPEN. 787 */ 788 if (dp->i_offset + dp->i_count > dp->i_size) 789 dp->i_size = dp->i_offset + dp->i_count; 790 /* 791 * Get the block containing the space for the new directory entry. 792 */ 793 error = ffs_blkatoff(dvp, (off_t)dp->i_offset, &dirbuf, &bp); 794 if (error) { 795 if (DOINGSOFTDEP(dvp) && newdirbp != NULL) 796 bdwrite(newdirbp); 797 return (error); 798 } 799 /* 800 * Find space for the new entry. In the simple case, the entry at 801 * offset base will have the space. If it does not, then namei 802 * arranged that compacting the region dp->i_offset to 803 * dp->i_offset + dp->i_count would yield the space. 804 */ 805 ep = (struct direct *)dirbuf; 806 dsize = ep->d_ino ? DIRSIZ(OFSFMT(dvp), ep) : 0; 807 spacefree = ep->d_reclen - dsize; 808 for (loc = ep->d_reclen; loc < dp->i_count; ) { 809 nep = (struct direct *)(dirbuf + loc); 810 811 /* Trim the existing slot (NB: dsize may be zero). */ 812 ep->d_reclen = dsize; 813 ep = (struct direct *)((char *)ep + dsize); 814 815 /* Read nep->d_reclen now as the bcopy() may clobber it. */ 816 loc += nep->d_reclen; 817 if (nep->d_ino == 0) { 818 /* 819 * A mid-block unused entry. Such entries are 820 * never created by the kernel, but fsck_ffs 821 * can create them (and it doesn't fix them). 822 * 823 * Add up the free space, and initialise the 824 * relocated entry since we don't bcopy it. 825 */ 826 spacefree += nep->d_reclen; 827 ep->d_ino = 0; 828 dsize = 0; 829 continue; 830 } 831 dsize = DIRSIZ(OFSFMT(dvp), nep); 832 spacefree += nep->d_reclen - dsize; 833 #ifdef UFS_DIRHASH 834 if (dp->i_dirhash != NULL) 835 ufsdirhash_move(dp, nep, 836 dp->i_offset + ((char *)nep - dirbuf), 837 dp->i_offset + ((char *)ep - dirbuf)); 838 #endif 839 if (DOINGSOFTDEP(dvp)) 840 softdep_change_directoryentry_offset(dp, dirbuf, 841 (caddr_t)nep, (caddr_t)ep, dsize); 842 else 843 bcopy((caddr_t)nep, (caddr_t)ep, dsize); 844 } 845 /* 846 * Here, `ep' points to a directory entry containing `dsize' in-use 847 * bytes followed by `spacefree' unused bytes. If ep->d_ino == 0, 848 * then the entry is completely unused (dsize == 0). The value 849 * of ep->d_reclen is always indeterminate. 850 * 851 * Update the pointer fields in the previous entry (if any), 852 * copy in the new entry, and write out the block. 853 */ 854 if (ep->d_ino == 0 || 855 (ep->d_ino == UFS_WINO && 856 bcmp(ep->d_name, dirp->d_name, dirp->d_namlen) == 0)) { 857 if (spacefree + dsize < newentrysize) 858 panic("ufs_direnter: compact1"); 859 dirp->d_reclen = spacefree + dsize; 860 } else { 861 if (spacefree < newentrysize) 862 panic("ufs_direnter: compact2"); 863 dirp->d_reclen = spacefree; 864 ep->d_reclen = dsize; 865 ep = (struct direct *)((char *)ep + dsize); 866 } 867 #ifdef UFS_DIRHASH 868 if (dp->i_dirhash != NULL && (ep->d_ino == 0 || 869 dirp->d_reclen == spacefree)) 870 ufsdirhash_add(dp, dirp, dp->i_offset + ((char *)ep - dirbuf)); 871 #endif 872 bcopy((caddr_t)dirp, (caddr_t)ep, (uint)newentrysize); 873 #ifdef UFS_DIRHASH 874 if (dp->i_dirhash != NULL) 875 ufsdirhash_checkblock(dp, dirbuf - 876 (dp->i_offset & (DIRBLKSIZ - 1)), 877 rounddown2(dp->i_offset, DIRBLKSIZ)); 878 #endif 879 880 if (DOINGSOFTDEP(dvp)) { 881 softdep_setup_directory_add(bp, dp, 882 dp->i_offset + (caddr_t)ep - dirbuf, dirp->d_ino, newdirbp); 883 bdwrite(bp); 884 } else { 885 if (DOINGASYNC(dvp)) { 886 bdwrite(bp); 887 error = 0; 888 } else { 889 error = bwrite(bp); 890 } 891 } 892 dp->i_flag |= IN_CHANGE | IN_UPDATE; 893 /* 894 * If all went well, and the directory can be shortened, proceed 895 * with the truncation. Note that we have to unlock the inode for 896 * the entry that we just entered, as the truncation may need to 897 * lock other inodes which can lead to deadlock if we also hold a 898 * lock on the newly entered node. 899 */ 900 if (error == 0 && dp->i_endoff && dp->i_endoff < dp->i_size) { 901 if (tvp != NULL) 902 vn_unlock(tvp); 903 #ifdef UFS_DIRHASH 904 if (dp->i_dirhash != NULL) 905 ufsdirhash_dirtrunc(dp, dp->i_endoff); 906 #endif 907 (void)ffs_truncate(dvp, (off_t)dp->i_endoff, IO_SYNC, cred); 908 if (tvp != NULL) 909 vn_lock(tvp, LK_EXCLUSIVE | LK_RETRY); 910 } 911 return (error); 912 } 913 914 /* 915 * Remove a directory entry after a call to namei, using 916 * the parameters which it left in the directory inode. The entry 917 * dp->i_offset contains the offset into the directory of the 918 * entry to be eliminated. The dp->i_count field contains the 919 * size of the previous record in the directory. If this 920 * is 0, the first entry is being deleted, so we need only 921 * zero the inode number to mark the entry as free. If the 922 * entry is not the first in the directory, we must reclaim 923 * the space of the now empty record by adding the record size 924 * to the size of the previous entry. 925 */ 926 int 927 ufs_dirremove(struct vnode *dvp, struct inode *ip, int flags, int isrmdir) 928 { 929 struct inode *dp; 930 struct direct *ep; 931 struct buf *bp; 932 int error; 933 934 dp = VTOI(dvp); 935 936 if (flags & CNP_DOWHITEOUT) { 937 /* 938 * Whiteout entry: set d_ino to UFS_WINO. 939 */ 940 if ((error = 941 ffs_blkatoff(dvp, (off_t)dp->i_offset, (char **)&ep, &bp)) != 0) 942 return (error); 943 ep->d_ino = UFS_WINO; 944 ep->d_type = DT_WHT; 945 goto out; 946 } 947 948 if ((error = ffs_blkatoff(dvp, 949 (off_t)(dp->i_offset - dp->i_count), (char **)&ep, &bp)) != 0) 950 return (error); 951 #ifdef UFS_DIRHASH 952 /* 953 * Remove the dirhash entry. This is complicated by the fact 954 * that `ep' is the previous entry when dp->i_count != 0. 955 */ 956 if (dp->i_dirhash != NULL) 957 ufsdirhash_remove(dp, (dp->i_count == 0) ? ep : 958 (struct direct *)((char *)ep + ep->d_reclen), dp->i_offset); 959 #endif 960 if (dp->i_count == 0) { 961 /* 962 * First entry in block: set d_ino to zero. 963 */ 964 ep->d_ino = 0; 965 } else { 966 /* 967 * Collapse new free space into previous entry. 968 */ 969 ep->d_reclen += dp->i_reclen; 970 } 971 #ifdef UFS_DIRHASH 972 if (dp->i_dirhash != NULL) 973 ufsdirhash_checkblock(dp, (char *)ep - 974 ((dp->i_offset - dp->i_count) & (DIRBLKSIZ - 1)), 975 rounddown2(dp->i_offset, DIRBLKSIZ)); 976 #endif 977 out: 978 if (DOINGSOFTDEP(dvp)) { 979 if (ip) { 980 ip->i_effnlink--; 981 softdep_change_linkcnt(ip); 982 softdep_setup_remove(bp, dp, ip, isrmdir); 983 } 984 if (softdep_slowdown(dvp)) { 985 error = bwrite(bp); 986 } else { 987 bdwrite(bp); 988 error = 0; 989 } 990 } else { 991 if (ip) { 992 ip->i_effnlink--; 993 ip->i_nlink--; 994 ip->i_flag |= IN_CHANGE; 995 } 996 if (flags & CNP_DOWHITEOUT) 997 error = bwrite(bp); 998 else if (DOINGASYNC(dvp) && dp->i_count != 0) { 999 bdwrite(bp); 1000 error = 0; 1001 } else { 1002 error = bwrite(bp); 1003 } 1004 } 1005 dp->i_flag |= IN_CHANGE | IN_UPDATE; 1006 return (error); 1007 } 1008 1009 /* 1010 * Rewrite an existing directory entry to point at the inode 1011 * supplied. The parameters describing the directory entry are 1012 * set up by a call to namei. 1013 */ 1014 int 1015 ufs_dirrewrite(struct inode *dp, struct inode *oip, ino_t newinum, int newtype, 1016 int isrmdir) 1017 { 1018 struct buf *bp; 1019 struct direct *ep; 1020 struct vnode *vdp = ITOV(dp); 1021 int error; 1022 1023 error = ffs_blkatoff(vdp, (off_t)dp->i_offset, (char **)&ep, &bp); 1024 if (error) 1025 return (error); 1026 ep->d_ino = newinum; 1027 if (!OFSFMT(vdp)) 1028 ep->d_type = newtype; 1029 oip->i_effnlink--; 1030 if (DOINGSOFTDEP(vdp)) { 1031 softdep_change_linkcnt(oip); 1032 softdep_setup_directory_change(bp, dp, oip, newinum, isrmdir); 1033 bdwrite(bp); 1034 } else { 1035 oip->i_nlink--; 1036 oip->i_flag |= IN_CHANGE; 1037 if (DOINGASYNC(vdp)) { 1038 bdwrite(bp); 1039 error = 0; 1040 } else { 1041 error = bwrite(bp); 1042 } 1043 } 1044 dp->i_flag |= IN_CHANGE | IN_UPDATE; 1045 return (error); 1046 } 1047 1048 /* 1049 * Check if a directory is empty or not. 1050 * Inode supplied must be locked. 1051 * 1052 * Using a struct dirtemplate here is not precisely 1053 * what we want, but better than using a struct direct. 1054 * 1055 * NB: does not handle corrupted directories. 1056 */ 1057 int 1058 ufs_dirempty(struct inode *ip, ino_t parentino, struct ucred *cred) 1059 { 1060 off_t off; 1061 struct dirtemplate dbuf; 1062 struct direct *dp = (struct direct *)&dbuf; 1063 int error, count, namlen; 1064 #define MINDIRSIZ (sizeof (struct dirtemplate) / 2) 1065 1066 for (off = 0; off < ip->i_size; off += dp->d_reclen) { 1067 error = vn_rdwr(UIO_READ, ITOV(ip), (caddr_t)dp, MINDIRSIZ, off, 1068 UIO_SYSSPACE, IO_NODELOCKED, cred, &count); 1069 /* 1070 * Since we read MINDIRSIZ, residual must 1071 * be 0 unless we're at end of file. 1072 */ 1073 if (error || count != 0) 1074 return (0); 1075 /* avoid infinite loops */ 1076 if (dp->d_reclen == 0) 1077 return (0); 1078 /* skip empty entries */ 1079 if (dp->d_ino == 0 || dp->d_ino == UFS_WINO) 1080 continue; 1081 /* accept only "." and ".." */ 1082 # if (BYTE_ORDER == LITTLE_ENDIAN) 1083 if (OFSFMT(ITOV(ip))) 1084 namlen = dp->d_type; 1085 else 1086 namlen = dp->d_namlen; 1087 # else 1088 namlen = dp->d_namlen; 1089 # endif 1090 if (namlen > 2) 1091 return (0); 1092 if (dp->d_name[0] != '.') 1093 return (0); 1094 /* 1095 * At this point namlen must be 1 or 2. 1096 * 1 implies ".", 2 implies ".." if second 1097 * char is also "." 1098 */ 1099 if (namlen == 1 && dp->d_ino == ip->i_number) 1100 continue; 1101 if (dp->d_name[1] == '.' && dp->d_ino == parentino) 1102 continue; 1103 return (0); 1104 } 1105 return (1); 1106 } 1107 1108 /* 1109 * Check if source directory is in the path of the target directory. 1110 * Target is supplied locked, source is unlocked. 1111 * The target is always vput before returning. 1112 */ 1113 int 1114 ufs_checkpath(struct inode *source, struct inode *target, struct ucred *cred) 1115 { 1116 struct vnode *vp; 1117 int error, rootino, namlen; 1118 struct dirtemplate dirbuf; 1119 1120 vp = ITOV(target); 1121 if (target->i_number == source->i_number) { 1122 error = EEXIST; 1123 goto out; 1124 } 1125 rootino = UFS_ROOTINO; 1126 error = 0; 1127 if (target->i_number == rootino) 1128 goto out; 1129 1130 for (;;) { 1131 if (vp->v_type != VDIR) { 1132 error = ENOTDIR; 1133 break; 1134 } 1135 error = vn_rdwr(UIO_READ, vp, (caddr_t)&dirbuf, 1136 sizeof (struct dirtemplate), (off_t)0, 1137 UIO_SYSSPACE, IO_NODELOCKED, cred, NULL); 1138 if (error != 0) 1139 break; 1140 # if (BYTE_ORDER == LITTLE_ENDIAN) 1141 if (OFSFMT(vp)) 1142 namlen = dirbuf.dotdot_type; 1143 else 1144 namlen = dirbuf.dotdot_namlen; 1145 # else 1146 namlen = dirbuf.dotdot_namlen; 1147 # endif 1148 if (namlen != 2 || 1149 dirbuf.dotdot_name[0] != '.' || 1150 dirbuf.dotdot_name[1] != '.') { 1151 error = ENOTDIR; 1152 break; 1153 } 1154 if (dirbuf.dotdot_ino == source->i_number) { 1155 error = EINVAL; 1156 break; 1157 } 1158 if (dirbuf.dotdot_ino == rootino) 1159 break; 1160 vput(vp); 1161 error = VFS_VGET(vp->v_mount, NULL, dirbuf.dotdot_ino, &vp); 1162 if (error) { 1163 vp = NULL; 1164 break; 1165 } 1166 } 1167 1168 out: 1169 if (error == ENOTDIR) 1170 kprintf("checkpath: .. not a directory\n"); 1171 if (vp != NULL) 1172 vput(vp); 1173 return (error); 1174 } 1175