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