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