1 /* ufs_lookup.c 6.23 85/05/22 */ 2 3 #include "param.h" 4 #include "systm.h" 5 #include "inode.h" 6 #include "fs.h" 7 #include "mount.h" 8 #include "dir.h" 9 #include "user.h" 10 #include "buf.h" 11 #include "conf.h" 12 #include "uio.h" 13 #include "kernel.h" 14 15 struct buf *blkatoff(); 16 struct buf *freenamebuf; 17 int dirchk = 0; 18 19 /* 20 * Structures associated with name cacheing. 21 */ 22 #define NCHHASH 32 /* size of hash table */ 23 24 #if ((NCHHASH)&((NCHHASH)-1)) != 0 25 #define NHASH(h, i, d) ((unsigned)((h) + (i) + 13 * (int)(d)) % (NCHHASH)) 26 #else 27 #define NHASH(h, i, d) ((unsigned)((h) + (i) + 13 * (int)(d)) & ((NCHHASH)-1)) 28 #endif 29 30 union nchash { 31 union nchash *nch_head[2]; 32 struct nch *nch_chain[2]; 33 } nchash[NCHHASH]; 34 #define nch_forw nch_chain[0] 35 #define nch_back nch_chain[1] 36 37 struct nch *nchhead, **nchtail; /* LRU chain pointers */ 38 struct nchstats nchstats; /* cache effectiveness statistics */ 39 40 /* 41 * Convert a pathname into a pointer to a locked inode, 42 * with side effects usable in creating and removing files. 43 * This is a very central and rather complicated routine. 44 * 45 * The segflg defines whether the name is to be copied from user 46 * space or kernel space. 47 * 48 * The flag argument is (LOOKUP, CREATE, DELETE) depending on whether 49 * the name is to be (looked up, created, deleted). If flag has 50 * LOCKPARENT or'ed into it and the target of the pathname exists, 51 * namei returns both the target and its parent directory locked. 52 * If the file system is not maintained in a strict tree hierarchy, 53 * this can result in a deadlock situation. When creating and 54 * LOCKPARENT is specified, the target may not be ".". When deleting 55 * and LOCKPARENT is specified, the target may be ".", but the caller 56 * must check to insure it does an irele and iput instead of two iputs. 57 * 58 * The FOLLOW flag is set when symbolic links are to be followed 59 * when they occur at the end of the name translation process. 60 * 61 * Name caching works as follows: 62 * 63 * names found by directory scans are retained in a cache 64 * for future reference. It is managed LRU, so frequently 65 * used names will hang around. Cache is indexed by hash value 66 * obtained from (ino,dev,name) where ino & dev refer to the 67 * directory containing name. 68 * 69 * For simplicity (and economy of storage), names longer than 70 * some (small) maximum length are not cached, they occur 71 * infrequently in any case, and are almost never of interest. 72 * 73 * Upon reaching the last segment of a path, if the reference 74 * is for DELETE, or NOCACHE is set (rewrite), and the 75 * name is located in the cache, it will be dropped. 76 * 77 * We must be sure never to enter the name ".." into the cache 78 * because of the extremely kludgey way that rename() alters 79 * ".." in a situation like 80 * mv a/x b/x 81 * where x is a directory, and x/.. is the ".." in question. 82 * 83 * Overall outline of namei: 84 * 85 * copy in name 86 * get starting directory 87 * dirloop: 88 * check accessibility of directory 89 * dirloop2: 90 * copy next component of name to ndp->ni_dent 91 * handle degenerate case where name is null string 92 * look for name in cache, if found, then if at end of path 93 * and deleting or creating, drop it, else to haveino 94 * search for name in directory, to found or notfound 95 * notfound: 96 * if creating, return locked directory, leaving info on avail. slots 97 * else return error 98 * found: 99 * if at end of path and deleting, return information to allow delete 100 * if at end of path and rewriting (create and LOCKPARENT), lock target 101 * inode and return info to allow rewrite 102 * if .. and on mounted filesys, look in mount table for parent 103 * if not at end, if neither creating nor deleting, add name to cache 104 * haveino: 105 * if symbolic link, massage name in buffer and continue at dirloop 106 * if more components of name, do next level at dirloop 107 * return the answer as locked inode 108 * 109 * NOTE: (LOOKUP | LOCKPARENT) currently returns the parent inode, 110 * but unlocked. 111 */ 112 struct inode * 113 namei(ndp) 114 register struct nameidata *ndp; 115 { 116 register char *cp; /* pointer into pathname argument */ 117 /* these variables refer to things which must be freed or unlocked */ 118 register struct inode *dp = 0; /* the directory we are searching */ 119 register struct nch *ncp; /* cache slot for entry */ 120 register struct fs *fs; /* file system that directory is in */ 121 register struct buf *bp = 0; /* a buffer of directory entries */ 122 register struct direct *ep; /* the current directory entry */ 123 int entryoffsetinblock; /* offset of ep in bp's buffer */ 124 register struct buf *nbp; /* buffer storing path name argument */ 125 /* these variables hold information about the search for a slot */ 126 enum {NONE, COMPACT, FOUND} slotstatus; 127 int slotoffset = -1; /* offset of area with free space */ 128 int slotsize; /* size of area at slotoffset */ 129 int slotfreespace; /* amount of space free in slot */ 130 int slotneeded; /* size of the entry we're seeking */ 131 /* */ 132 int numdirpasses; /* strategy for directory search */ 133 int endsearch; /* offset to end directory search */ 134 int prevoff; /* ndp->ni_offset of previous entry */ 135 int nlink = 0; /* number of symbolic links taken */ 136 struct inode *pdp; /* saved dp during symlink work */ 137 int error, i; 138 int lockparent; 139 int docache; /* == 0 do not cache last component */ 140 int makeentry; /* != 0 if name to be added to cache */ 141 unsigned hash; /* value of name hash for entry */ 142 union nchash *nhp; /* cache chain head for entry */ 143 int isdotdot; /* != 0 if current name is ".." */ 144 int flag; /* op ie, LOOKUP, CREATE, or DELETE */ 145 off_t enduseful; /* pointer past last used dir slot */ 146 147 lockparent = ndp->ni_nameiop & LOCKPARENT; 148 docache = (ndp->ni_nameiop & NOCACHE) ^ NOCACHE; 149 flag = ndp->ni_nameiop &~ (LOCKPARENT|NOCACHE|FOLLOW); 150 if (flag == DELETE || lockparent) 151 docache = 0; 152 /* 153 * Get a buffer for the name to be translated, and copy the 154 * name into the buffer. 155 */ 156 nbp = freenamebuf; 157 if (nbp == NULL) 158 nbp = geteblk(MAXPATHLEN); 159 else 160 freenamebuf = nbp->av_forw; 161 if (ndp->ni_segflg == UIO_SYSSPACE) 162 error = copystr(ndp->ni_dirp, nbp->b_un.b_addr, MAXPATHLEN, 163 (u_int *)0); 164 else 165 error = copyinstr(ndp->ni_dirp, nbp->b_un.b_addr, MAXPATHLEN, 166 (u_int *)0); 167 if (error) { 168 u.u_error = error; 169 goto bad; 170 } 171 172 /* 173 * Get starting directory. 174 */ 175 cp = nbp->b_un.b_addr; 176 if (*cp == '/') { 177 while (*cp == '/') 178 cp++; 179 if ((dp = u.u_rdir) == NULL) 180 dp = rootdir; 181 } else 182 dp = u.u_cdir; 183 fs = dp->i_fs; 184 ILOCK(dp); 185 dp->i_count++; 186 ndp->ni_pdir = (struct inode *)0xc0000000; /* illegal */ 187 ndp->ni_endoff = 0; 188 189 /* 190 * We come to dirloop to search a new directory. 191 * The directory must be locked so that it can be 192 * iput, and fs must be already set to dp->i_fs. 193 */ 194 dirloop: 195 /* 196 * Check accessiblity of directory. 197 */ 198 if ((dp->i_mode&IFMT) != IFDIR) { 199 u.u_error = ENOTDIR; 200 goto bad; 201 } 202 if (access(dp, IEXEC)) 203 goto bad; 204 205 dirloop2: 206 /* 207 * Copy next component of name to ndp->ni_dent. 208 */ 209 hash = 0; 210 for (i = 0; *cp != 0 && *cp != '/'; cp++) { 211 if (i >= MAXNAMLEN) { 212 u.u_error = ENAMETOOLONG; 213 goto bad; 214 } 215 if (*cp & 0200) 216 if ((*cp&0377) == ('/'|0200) || flag != DELETE) { 217 u.u_error = EINVAL; 218 goto bad; 219 } 220 ndp->ni_dent.d_name[i++] = *cp; 221 hash += (unsigned char)*cp * i; 222 } 223 ndp->ni_dent.d_namlen = i; 224 ndp->ni_dent.d_name[i] = '\0'; 225 isdotdot = (i == 2 && 226 ndp->ni_dent.d_name[0] == '.' && ndp->ni_dent.d_name[1] == '.'); 227 makeentry = 1; 228 if (*cp == '\0' && docache == 0) 229 makeentry = 0; 230 231 /* 232 * Check for degenerate name (e.g. / or "") 233 * which is a way of talking about a directory, 234 * e.g. like "/." or ".". 235 */ 236 if (ndp->ni_dent.d_name[0] == '\0') { 237 if (flag != LOOKUP || lockparent) { 238 u.u_error = EISDIR; 239 goto bad; 240 } 241 nbp->av_forw = freenamebuf; 242 freenamebuf = nbp; 243 return (dp); 244 } 245 246 /* 247 * We now have a segment name to search for, and a directory to search. 248 * 249 * Before tediously performing a linear scan of the directory, 250 * check the name cache to see if the directory/name pair 251 * we are looking for is known already. We don't do this 252 * if the segment name is long, simply so the cache can avoid 253 * holding long names (which would either waste space, or 254 * add greatly to the complexity). 255 */ 256 if (ndp->ni_dent.d_namlen > NCHNAMLEN) { 257 nchstats.ncs_long++; 258 makeentry = 0; 259 } else { 260 nhp = &nchash[NHASH(hash, dp->i_number, dp->i_dev)]; 261 for (ncp = nhp->nch_forw; ncp != (struct nch *)nhp; 262 ncp = ncp->nc_forw) { 263 if (ncp->nc_ino == dp->i_number && 264 ncp->nc_dev == dp->i_dev && 265 ncp->nc_nlen == ndp->ni_dent.d_namlen && 266 !bcmp(ncp->nc_name, ndp->ni_dent.d_name, 267 ncp->nc_nlen)) 268 break; 269 } 270 271 if (ncp == (struct nch *)nhp) { 272 nchstats.ncs_miss++; 273 ncp = NULL; 274 } else { 275 if (ncp->nc_id != ncp->nc_ip->i_id) { 276 nchstats.ncs_falsehits++; 277 } else if (!makeentry) { 278 nchstats.ncs_badhits++; 279 } else { 280 281 /* 282 * move this slot to end of LRU 283 * chain, if not already there 284 */ 285 if (ncp->nc_nxt) { 286 /* remove from LRU chain */ 287 *ncp->nc_prev = ncp->nc_nxt; 288 ncp->nc_nxt->nc_prev = ncp->nc_prev; 289 290 /* and replace at end of it */ 291 ncp->nc_nxt = NULL; 292 ncp->nc_prev = nchtail; 293 *nchtail = ncp; 294 nchtail = &ncp->nc_nxt; 295 } 296 297 /* 298 * Get the next inode in the path. 299 * See comment above other `IUNLOCK' code for 300 * an explaination of the locking protocol. 301 */ 302 pdp = dp; 303 if (!isdotdot || dp != u.u_rdir) 304 dp = ncp->nc_ip; 305 if (dp == NULL) 306 panic("nami: null cache ino"); 307 if (pdp == dp) { 308 dp->i_count++; 309 } else if (isdotdot) { 310 IUNLOCK(pdp); 311 igrab(dp); 312 } else { 313 igrab(dp); 314 IUNLOCK(pdp); 315 } 316 317 /* 318 * Verify that the inode that we got 319 * did not change while we were waiting 320 * for it to be locked. 321 */ 322 if (ncp->nc_id != ncp->nc_ip->i_id) { 323 iput(dp); 324 ILOCK(pdp); 325 dp = pdp; 326 nchstats.ncs_falsehits++; 327 } else { 328 ndp->ni_dent.d_ino = dp->i_number; 329 /* ni_dent.d_reclen is garbage ... */ 330 nchstats.ncs_goodhits++; 331 goto haveino; 332 } 333 } 334 335 /* 336 * Last component and we are renaming or deleting, 337 * the cache entry is invalid, or otherwise don't 338 * want cache entry to exist. 339 */ 340 341 /* remove from LRU chain */ 342 *ncp->nc_prev = ncp->nc_nxt; 343 if (ncp->nc_nxt) 344 ncp->nc_nxt->nc_prev = ncp->nc_prev; 345 else 346 nchtail = ncp->nc_prev; 347 348 /* remove from hash chain */ 349 remque(ncp); 350 351 /* insert at head of LRU list (first to grab) */ 352 ncp->nc_nxt = nchhead; 353 ncp->nc_prev = &nchhead; 354 nchhead->nc_prev = &ncp->nc_nxt; 355 nchhead = ncp; 356 357 /* and make a dummy hash chain */ 358 ncp->nc_forw = ncp; 359 ncp->nc_back = ncp; 360 361 ncp = NULL; 362 } 363 } 364 365 /* 366 * Suppress search for slots unless creating 367 * file and at end of pathname, in which case 368 * we watch for a place to put the new file in 369 * case it doesn't already exist. 370 */ 371 slotstatus = FOUND; 372 if (flag == CREATE && *cp == 0) { 373 slotstatus = NONE; 374 slotfreespace = 0; 375 slotneeded = DIRSIZ(&ndp->ni_dent); 376 } 377 /* 378 * If this is the same directory that this process 379 * previously searched, pick up where we last left off. 380 * We cache only lookups as these are the most common 381 * and have the greatest payoff. Caching CREATE has little 382 * benefit as it usually must search the entire directory 383 * to determine that the entry does not exist. Caching the 384 * location of the last DELETE has not reduced profiling time 385 * and hence has been removed in the interest of simplicity. 386 */ 387 if (flag != LOOKUP || dp->i_number != u.u_ncache.nc_inumber || 388 dp->i_dev != u.u_ncache.nc_dev) { 389 ndp->ni_offset = 0; 390 numdirpasses = 1; 391 } else { 392 if ((dp->i_flag & ICHG) || dp->i_ctime >= u.u_ncache.nc_time) { 393 if (u.u_ncache.nc_prevoffset > dp->i_size) 394 u.u_ncache.nc_prevoffset = 0; 395 else 396 u.u_ncache.nc_prevoffset &= ~(DIRBLKSIZ - 1); 397 u.u_ncache.nc_time = time.tv_sec; 398 } 399 ndp->ni_offset = u.u_ncache.nc_prevoffset; 400 entryoffsetinblock = blkoff(fs, ndp->ni_offset); 401 if (entryoffsetinblock != 0) { 402 bp = blkatoff(dp, ndp->ni_offset, (char **)0); 403 if (bp == 0) 404 goto bad; 405 } 406 numdirpasses = 2; 407 nchstats.ncs_2passes++; 408 } 409 endsearch = roundup(dp->i_size, DIRBLKSIZ); 410 enduseful = 0; 411 412 searchloop: 413 while (ndp->ni_offset < endsearch) { 414 /* 415 * If offset is on a block boundary, 416 * read the next directory block. 417 * Release previous if it exists. 418 */ 419 if (blkoff(fs, ndp->ni_offset) == 0) { 420 if (bp != NULL) 421 brelse(bp); 422 bp = blkatoff(dp, ndp->ni_offset, (char **)0); 423 if (bp == 0) 424 goto bad; 425 entryoffsetinblock = 0; 426 } 427 428 /* 429 * If still looking for a slot, and at a DIRBLKSIZE 430 * boundary, have to start looking for free space again. 431 */ 432 if (slotstatus == NONE && 433 (entryoffsetinblock&(DIRBLKSIZ-1)) == 0) { 434 slotoffset = -1; 435 slotfreespace = 0; 436 } 437 438 /* 439 * Get pointer to next entry. 440 * Full validation checks are slow, so we only check 441 * enough to insure forward progress through the 442 * directory. Complete checks can be run by patching 443 * "dirchk" to be true. 444 */ 445 ep = (struct direct *)(bp->b_un.b_addr + entryoffsetinblock); 446 if (ep->d_reclen <= 0 || 447 dirchk && dirbadentry(ep, entryoffsetinblock)) { 448 dirbad(dp, ndp->ni_offset, "mangled entry"); 449 i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)); 450 ndp->ni_offset += i; 451 entryoffsetinblock += i; 452 continue; 453 } 454 455 /* 456 * If an appropriate sized slot has not yet been found, 457 * check to see if one is available. Also accumulate space 458 * in the current block so that we can determine if 459 * compaction is viable. 460 */ 461 if (slotstatus != FOUND) { 462 int size = ep->d_reclen; 463 464 if (ep->d_ino != 0) 465 size -= DIRSIZ(ep); 466 if (size > 0) { 467 if (size >= slotneeded) { 468 slotstatus = FOUND; 469 slotoffset = ndp->ni_offset; 470 slotsize = ep->d_reclen; 471 } else if (slotstatus == NONE) { 472 slotfreespace += size; 473 if (slotoffset == -1) 474 slotoffset = ndp->ni_offset; 475 if (slotfreespace >= slotneeded) { 476 slotstatus = COMPACT; 477 slotsize = ndp->ni_offset + 478 ep->d_reclen - slotoffset; 479 } 480 } 481 } 482 } 483 484 /* 485 * Check for a name match. 486 */ 487 if (ep->d_ino) { 488 if (ep->d_namlen == ndp->ni_dent.d_namlen && 489 !bcmp(ndp->ni_dent.d_name, ep->d_name, 490 ep->d_namlen)) 491 goto found; 492 } 493 prevoff = ndp->ni_offset; 494 ndp->ni_offset += ep->d_reclen; 495 entryoffsetinblock += ep->d_reclen; 496 if (ep->d_ino) 497 enduseful = ndp->ni_offset; 498 } 499 /* notfound: */ 500 /* 501 * If we started in the middle of the directory and failed 502 * to find our target, we must check the beginning as well. 503 */ 504 if (numdirpasses == 2) { 505 numdirpasses--; 506 ndp->ni_offset = 0; 507 endsearch = u.u_ncache.nc_prevoffset; 508 goto searchloop; 509 } 510 /* 511 * If creating, and at end of pathname and current 512 * directory has not been removed, then can consider 513 * allowing file to be created. 514 */ 515 if (flag == CREATE && *cp == 0 && dp->i_nlink != 0) { 516 /* 517 * Access for write is interpreted as allowing 518 * creation of files in the directory. 519 */ 520 if (access(dp, IWRITE)) 521 goto bad; 522 /* 523 * Return an indication of where the new directory 524 * entry should be put. If we didn't find a slot, 525 * then set ndp->ni_count to 0 indicating that the new 526 * slot belongs at the end of the directory. If we found 527 * a slot, then the new entry can be put in the range 528 * [ndp->ni_offset .. ndp->ni_offset + ndp->ni_count) 529 */ 530 if (slotstatus == NONE) { 531 ndp->ni_offset = roundup(dp->i_size, DIRBLKSIZ); 532 ndp->ni_count = 0; 533 enduseful = ndp->ni_offset; 534 } else { 535 ndp->ni_offset = slotoffset; 536 ndp->ni_count = slotsize; 537 if (enduseful < slotoffset + slotsize) 538 enduseful = slotoffset + slotsize; 539 } 540 ndp->ni_endoff = roundup(enduseful, DIRBLKSIZ); 541 dp->i_flag |= IUPD|ICHG; 542 if (bp) 543 brelse(bp); 544 nbp->av_forw = freenamebuf; 545 freenamebuf = nbp; 546 /* 547 * We return with the directory locked, so that 548 * the parameters we set up above will still be 549 * valid if we actually decide to do a direnter(). 550 * We return NULL to indicate that the entry doesn't 551 * currently exist, leaving a pointer to the (locked) 552 * directory inode in ndp->ni_pdir. 553 */ 554 ndp->ni_pdir = dp; 555 return (NULL); 556 } 557 u.u_error = ENOENT; 558 goto bad; 559 found: 560 if (numdirpasses == 2) 561 nchstats.ncs_pass2++; 562 /* 563 * Check that directory length properly reflects presence 564 * of this entry. 565 */ 566 if (entryoffsetinblock + DIRSIZ(ep) > dp->i_size) { 567 dirbad(dp, ndp->ni_offset, "i_size too small"); 568 dp->i_size = entryoffsetinblock + DIRSIZ(ep); 569 dp->i_flag |= IUPD|ICHG; 570 } 571 572 /* 573 * Found component in pathname. 574 * If the final component of path name, save information 575 * in the cache as to where the entry was found. 576 */ 577 if (*cp == '\0' && flag == LOOKUP) { 578 u.u_ncache.nc_prevoffset = ndp->ni_offset; 579 u.u_ncache.nc_inumber = dp->i_number; 580 u.u_ncache.nc_dev = dp->i_dev; 581 u.u_ncache.nc_time = time.tv_sec; 582 } 583 /* 584 * Save directory entry's inode number and reclen in ndp->ni_dent, 585 * and release directory buffer. 586 */ 587 ndp->ni_dent.d_ino = ep->d_ino; 588 ndp->ni_dent.d_reclen = ep->d_reclen; 589 brelse(bp); 590 bp = NULL; 591 592 /* 593 * If deleting, and at end of pathname, return 594 * parameters which can be used to remove file. 595 * If the lockparent flag isn't set, we return only 596 * the directory (in ndp->ni_pdir), otherwise we go 597 * on and lock the inode, being careful with ".". 598 */ 599 if (flag == DELETE && *cp == 0) { 600 /* 601 * Write access to directory required to delete files. 602 */ 603 if (access(dp, IWRITE)) 604 goto bad; 605 ndp->ni_pdir = dp; /* for dirremove() */ 606 /* 607 * Return pointer to current entry in ndp->ni_offset, 608 * and distance past previous entry (if there 609 * is a previous entry in this block) in ndp->ni_count. 610 * Save directory inode pointer in ndp->ni_pdir for dirremove(). 611 */ 612 if ((ndp->ni_offset&(DIRBLKSIZ-1)) == 0) 613 ndp->ni_count = 0; 614 else 615 ndp->ni_count = ndp->ni_offset - prevoff; 616 if (lockparent) { 617 if (dp->i_number == ndp->ni_dent.d_ino) 618 dp->i_count++; 619 else { 620 dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); 621 if (dp == NULL) { 622 iput(ndp->ni_pdir); 623 goto bad; 624 } 625 /* 626 * If directory is "sticky", then user must own 627 * the directory, or the file in it, else he 628 * may not delete it (unless he's root). This 629 * implements append-only directories. 630 */ 631 if ((ndp->ni_pdir->i_mode & ISVTX) && 632 u.u_uid != 0 && 633 u.u_uid != ndp->ni_pdir->i_uid && 634 dp->i_uid != u.u_uid) { 635 iput(ndp->ni_pdir); 636 u.u_error = EPERM; 637 goto bad; 638 } 639 } 640 } 641 nbp->av_forw = freenamebuf; 642 freenamebuf = nbp; 643 return (dp); 644 } 645 646 /* 647 * Special handling for ".." allowing chdir out of mounted 648 * file system: indirect .. in root inode to reevaluate 649 * in directory file system was mounted on. 650 */ 651 if (isdotdot) { 652 if (dp == u.u_rdir) { 653 ndp->ni_dent.d_ino = dp->i_number; 654 makeentry = 0; 655 } else if (ndp->ni_dent.d_ino == ROOTINO && 656 dp->i_number == ROOTINO) { 657 for (i = 1; i < NMOUNT; i++) 658 if (mount[i].m_bufp != NULL && 659 mount[i].m_dev == dp->i_dev) { 660 iput(dp); 661 dp = mount[i].m_inodp; 662 ILOCK(dp); 663 dp->i_count++; 664 fs = dp->i_fs; 665 cp -= 2; /* back over .. */ 666 goto dirloop2; 667 } 668 } 669 } 670 671 /* 672 * If rewriting (rename), return the inode and the 673 * information required to rewrite the present directory 674 * Must get inode of directory entry to verify it's a 675 * regular file, or empty directory. 676 */ 677 if ((flag == CREATE && lockparent) && *cp == 0) { 678 if (access(dp, IWRITE)) 679 goto bad; 680 ndp->ni_pdir = dp; /* for dirrewrite() */ 681 /* 682 * Careful about locking second inode. 683 * This can only occur if the target is ".". 684 */ 685 if (dp->i_number == ndp->ni_dent.d_ino) { 686 u.u_error = EISDIR; /* XXX */ 687 goto bad; 688 } 689 dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); 690 if (dp == NULL) { 691 iput(ndp->ni_pdir); 692 goto bad; 693 } 694 nbp->av_forw = freenamebuf; 695 freenamebuf = nbp; 696 return (dp); 697 } 698 699 /* 700 * Check for symbolic link, which may require us to massage the 701 * name before we continue translation. We do not `iput' the 702 * directory because we may need it again if the symbolic link 703 * is relative to the current directory. Instead we save it 704 * unlocked as "pdp". We must get the target inode before unlocking 705 * the directory to insure that the inode will not be removed 706 * before we get it. We prevent deadlock by always fetching 707 * inodes from the root, moving down the directory tree. Thus 708 * when following backward pointers ".." we must unlock the 709 * parent directory before getting the requested directory. 710 * There is a potential race condition here if both the current 711 * and parent directories are removed before the `iget' for the 712 * inode associated with ".." returns. We hope that this occurs 713 * infrequently since we cannot avoid this race condition without 714 * implementing a sophisticated deadlock detection algorithm. 715 * Note also that this simple deadlock detection scheme will not 716 * work if the file system has any hard links other than ".." 717 * that point backwards in the directory structure. 718 */ 719 pdp = dp; 720 if (isdotdot) { 721 IUNLOCK(pdp); /* race to get the inode */ 722 dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); 723 if (dp == NULL) 724 goto bad2; 725 } else if (dp->i_number == ndp->ni_dent.d_ino) { 726 dp->i_count++; /* we want ourself, ie "." */ 727 } else { 728 dp = iget(dp->i_dev, fs, ndp->ni_dent.d_ino); 729 IUNLOCK(pdp); 730 if (dp == NULL) 731 goto bad2; 732 } 733 734 /* 735 * insert name into cache if appropriate 736 */ 737 if (makeentry) { 738 if (ncp != NULL) 739 panic("nami: duplicating cache"); 740 741 /* 742 * free the cache slot at head of lru chain 743 */ 744 if (ncp = nchhead) { 745 /* remove from lru chain */ 746 *ncp->nc_prev = ncp->nc_nxt; 747 if (ncp->nc_nxt) 748 ncp->nc_nxt->nc_prev = ncp->nc_prev; 749 else 750 nchtail = ncp->nc_prev; 751 752 /* remove from old hash chain */ 753 remque(ncp); 754 755 /* grab the inode we just found */ 756 ncp->nc_ip = dp; 757 758 /* fill in cache info */ 759 ncp->nc_ino = pdp->i_number; /* parents inum */ 760 ncp->nc_dev = pdp->i_dev; /* & device */ 761 ncp->nc_idev = dp->i_dev; /* our device */ 762 ncp->nc_id = dp->i_id; /* identifier */ 763 ncp->nc_nlen = ndp->ni_dent.d_namlen; 764 bcopy(ndp->ni_dent.d_name, ncp->nc_name, ncp->nc_nlen); 765 766 /* link at end of lru chain */ 767 ncp->nc_nxt = NULL; 768 ncp->nc_prev = nchtail; 769 *nchtail = ncp; 770 nchtail = &ncp->nc_nxt; 771 772 /* and insert on hash chain */ 773 insque(ncp, nhp); 774 } 775 } 776 777 haveino: 778 fs = dp->i_fs; 779 780 /* 781 * Check for symbolic link 782 */ 783 if ((dp->i_mode & IFMT) == IFLNK && 784 ((ndp->ni_nameiop & FOLLOW) || *cp == '/')) { 785 u_int pathlen = strlen(cp) + 1; 786 787 if (dp->i_size + pathlen >= MAXPATHLEN - 1) { 788 u.u_error = ENAMETOOLONG; 789 goto bad2; 790 } 791 if (++nlink > MAXSYMLINKS) { 792 u.u_error = ELOOP; 793 goto bad2; 794 } 795 ovbcopy(cp, nbp->b_un.b_addr + dp->i_size, pathlen); 796 u.u_error = 797 rdwri(UIO_READ, dp, nbp->b_un.b_addr, (int)dp->i_size, 798 0, 1, (int *)0); 799 if (u.u_error) 800 goto bad2; 801 cp = nbp->b_un.b_addr; 802 iput(dp); 803 if (*cp == '/') { 804 irele(pdp); 805 while (*cp == '/') 806 cp++; 807 if ((dp = u.u_rdir) == NULL) 808 dp = rootdir; 809 ILOCK(dp); 810 dp->i_count++; 811 } else { 812 dp = pdp; 813 ILOCK(dp); 814 } 815 fs = dp->i_fs; 816 goto dirloop; 817 } 818 819 /* 820 * Not a symbolic link. If more pathname, 821 * continue at next component, else return. 822 */ 823 if (*cp == '/') { 824 while (*cp == '/') 825 cp++; 826 irele(pdp); 827 goto dirloop; 828 } 829 nbp->av_forw = freenamebuf; 830 freenamebuf = nbp; 831 if (lockparent) 832 ndp->ni_pdir = pdp; 833 else 834 irele(pdp); 835 return (dp); 836 bad2: 837 irele(pdp); 838 bad: 839 if (bp) 840 brelse(bp); 841 if (dp) 842 iput(dp); 843 nbp->av_forw = freenamebuf; 844 freenamebuf = nbp; 845 return (NULL); 846 } 847 848 849 dirbad(ip, offset, how) 850 struct inode *ip; 851 off_t offset; 852 char *how; 853 { 854 855 printf("%s: bad dir ino %d at offset %d: %s\n", 856 ip->i_fs->fs_fsmnt, ip->i_number, offset, how); 857 } 858 859 /* 860 * Do consistency checking on a directory entry: 861 * record length must be multiple of 4 862 * record length must not be non-negative 863 * entry must fit in rest of its DIRBLKSIZ block 864 * record must be large enough to contain entry 865 * name is not longer than MAXNAMLEN 866 * name must be as long as advertised, and null terminated 867 */ 868 dirbadentry(ep, entryoffsetinblock) 869 register struct direct *ep; 870 int entryoffsetinblock; 871 { 872 register int i; 873 874 if ((ep->d_reclen & 0x3) != 0 || ep->d_reclen <= 0 || 875 ep->d_reclen > DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)) || 876 ep->d_reclen < DIRSIZ(ep) || ep->d_namlen > MAXNAMLEN) 877 return (1); 878 for (i = 0; i < ep->d_namlen; i++) 879 if (ep->d_name[i] == '\0') 880 return (1); 881 return (ep->d_name[i]); 882 } 883 884 /* 885 * Write a directory entry after a call to namei, using the parameters 886 * which it left in the u. area. The argument ip is the inode which 887 * the new directory entry will refer to. The u. area field ndp->ni_pdir is 888 * a pointer to the directory to be written, which was left locked by 889 * namei. Remaining parameters (ndp->ni_offset, ndp->ni_count) indicate 890 * how the space for the new entry is to be gotten. 891 */ 892 direnter(ip, ndp) 893 struct inode *ip; 894 register struct nameidata *ndp; 895 { 896 register struct direct *ep, *nep; 897 register struct inode *dp = ndp->ni_pdir; 898 struct buf *bp; 899 int loc, spacefree, error = 0; 900 u_int dsize; 901 int newentrysize; 902 char *dirbuf; 903 904 ndp->ni_dent.d_ino = ip->i_number; 905 newentrysize = DIRSIZ(&ndp->ni_dent); 906 if (ndp->ni_count == 0) { 907 /* 908 * If ndp->ni_count is 0, then namei could find no space in the 909 * directory. In this case ndp->ni_offset will be on a directory 910 * block boundary and we will write the new entry into a fresh 911 * block. 912 */ 913 if (ndp->ni_offset&(DIRBLKSIZ-1)) 914 panic("wdir: newblk"); 915 ndp->ni_dent.d_reclen = DIRBLKSIZ; 916 error = rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, 917 newentrysize, ndp->ni_offset, 1, (int *)0); 918 if (DIRBLKSIZ > dp->i_fs->fs_fsize) 919 panic("wdir: blksize"); /* XXX - should grow w/bmap() */ 920 else 921 dp->i_size = roundup(dp->i_size, DIRBLKSIZ); 922 iput(dp); 923 return (error); 924 } 925 926 /* 927 * If ndp->ni_count is non-zero, then namei found space for the new 928 * entry in the range ndp->ni_offset to ndp->ni_offset + ndp->ni_count. 929 * in the directory. To use this space, we may have to compact 930 * the entries located there, by copying them together towards 931 * the beginning of the block, leaving the free space in 932 * one usable chunk at the end. 933 */ 934 935 /* 936 * Increase size of directory if entry eats into new space. 937 * This should never push the size past a new multiple of 938 * DIRBLKSIZE. 939 * 940 * N.B. - THIS IS AN ARTIFACT OF 4.2 AND SHOULD NEVER HAPPEN. 941 */ 942 if (ndp->ni_offset + ndp->ni_count > dp->i_size) 943 dp->i_size = ndp->ni_offset + ndp->ni_count; 944 945 /* 946 * Get the block containing the space for the new directory 947 * entry. Should return error by result instead of u.u_error. 948 */ 949 bp = blkatoff(dp, ndp->ni_offset, (char **)&dirbuf); 950 if (bp == 0) { 951 iput(dp); 952 return (u.u_error); 953 } 954 955 /* 956 * Find space for the new entry. In the simple case, the 957 * entry at offset base will have the space. If it does 958 * not, then namei arranged that compacting the region 959 * ndp->ni_offset to ndp->ni_offset+ndp->ni_count would yield the space. 960 */ 961 ep = (struct direct *)dirbuf; 962 dsize = DIRSIZ(ep); 963 spacefree = ep->d_reclen - dsize; 964 for (loc = ep->d_reclen; loc < ndp->ni_count; ) { 965 nep = (struct direct *)(dirbuf + loc); 966 if (ep->d_ino) { 967 /* trim the existing slot */ 968 ep->d_reclen = dsize; 969 ep = (struct direct *)((char *)ep + dsize); 970 } else { 971 /* overwrite; nothing there; header is ours */ 972 spacefree += dsize; 973 } 974 dsize = DIRSIZ(nep); 975 spacefree += nep->d_reclen - dsize; 976 loc += nep->d_reclen; 977 bcopy((caddr_t)nep, (caddr_t)ep, dsize); 978 } 979 /* 980 * Update the pointer fields in the previous entry (if any), 981 * copy in the new entry, and write out the block. 982 */ 983 if (ep->d_ino == 0) { 984 if (spacefree + dsize < newentrysize) 985 panic("wdir: compact1"); 986 ndp->ni_dent.d_reclen = spacefree + dsize; 987 } else { 988 if (spacefree < newentrysize) 989 panic("wdir: compact2"); 990 ndp->ni_dent.d_reclen = spacefree; 991 ep->d_reclen = dsize; 992 ep = (struct direct *)((char *)ep + dsize); 993 } 994 bcopy((caddr_t)&ndp->ni_dent, (caddr_t)ep, (u_int)newentrysize); 995 bwrite(bp); 996 dp->i_flag |= IUPD|ICHG; 997 if (ndp->ni_endoff && ndp->ni_endoff < dp->i_size) 998 itrunc(dp, ndp->ni_endoff); 999 iput(dp); 1000 return (error); 1001 } 1002 1003 /* 1004 * Remove a directory entry after a call to namei, using the 1005 * parameters which it left in the u. area. The u. entry 1006 * ni_offset contains the offset into the directory of the 1007 * entry to be eliminated. The ni_count field contains the 1008 * size of the previous record in the directory. If this 1009 * is 0, the first entry is being deleted, so we need only 1010 * zero the inode number to mark the entry as free. If the 1011 * entry isn't the first in the directory, we must reclaim 1012 * the space of the now empty record by adding the record size 1013 * to the size of the previous entry. 1014 */ 1015 dirremove(ndp) 1016 register struct nameidata *ndp; 1017 { 1018 register struct inode *dp = ndp->ni_pdir; 1019 register struct buf *bp; 1020 struct direct *ep; 1021 1022 if (ndp->ni_count == 0) { 1023 /* 1024 * First entry in block: set d_ino to zero. 1025 */ 1026 ndp->ni_dent.d_ino = 0; 1027 (void) rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, 1028 (int)DIRSIZ(&ndp->ni_dent), ndp->ni_offset, 1, (int *)0); 1029 } else { 1030 /* 1031 * Collapse new free space into previous entry. 1032 */ 1033 bp = blkatoff(dp, (int)(ndp->ni_offset - ndp->ni_count), 1034 (char **)&ep); 1035 if (bp == 0) 1036 return (0); 1037 ep->d_reclen += ndp->ni_dent.d_reclen; 1038 bwrite(bp); 1039 dp->i_flag |= IUPD|ICHG; 1040 } 1041 return (1); 1042 } 1043 1044 /* 1045 * Rewrite an existing directory entry to point at the inode 1046 * supplied. The parameters describing the directory entry are 1047 * set up by a call to namei. 1048 */ 1049 dirrewrite(dp, ip, ndp) 1050 struct inode *dp, *ip; 1051 struct nameidata *ndp; 1052 { 1053 1054 ndp->ni_dent.d_ino = ip->i_number; 1055 u.u_error = rdwri(UIO_WRITE, dp, (caddr_t)&ndp->ni_dent, 1056 (int)DIRSIZ(&ndp->ni_dent), ndp->ni_offset, 1, (int *)0); 1057 iput(dp); 1058 } 1059 1060 /* 1061 * Return buffer with contents of block "offset" 1062 * from the beginning of directory "ip". If "res" 1063 * is non-zero, fill it in with a pointer to the 1064 * remaining space in the directory. 1065 */ 1066 struct buf * 1067 blkatoff(ip, offset, res) 1068 struct inode *ip; 1069 off_t offset; 1070 char **res; 1071 { 1072 register struct fs *fs = ip->i_fs; 1073 daddr_t lbn = lblkno(fs, offset); 1074 int bsize = blksize(fs, ip, lbn); 1075 register struct buf *bp; 1076 daddr_t bn; 1077 1078 bn = bmap(ip, lbn, B_READ, bsize); 1079 if (u.u_error) 1080 return (0); 1081 if (bn == (daddr_t)-1) { 1082 dirbad(ip, offset, "hole in dir"); 1083 return (0); 1084 } 1085 bp = bread(ip->i_dev, fsbtodb(fs, bn), bsize); 1086 if (bp->b_flags & B_ERROR) { 1087 brelse(bp); 1088 return (0); 1089 } 1090 if (res) 1091 *res = bp->b_un.b_addr + blkoff(fs, offset); 1092 return (bp); 1093 } 1094 1095 /* 1096 * Check if a directory is empty or not. 1097 * Inode supplied must be locked. 1098 * 1099 * Using a struct dirtemplate here is not precisely 1100 * what we want, but better than using a struct direct. 1101 * 1102 * NB: does not handle corrupted directories. 1103 */ 1104 dirempty(ip, parentino) 1105 register struct inode *ip; 1106 ino_t parentino; 1107 { 1108 register off_t off; 1109 struct dirtemplate dbuf; 1110 register struct direct *dp = (struct direct *)&dbuf; 1111 int error, count; 1112 #define MINDIRSIZ (sizeof (struct dirtemplate) / 2) 1113 1114 for (off = 0; off < ip->i_size; off += dp->d_reclen) { 1115 if (dp->d_reclen <= 0) 1116 return (0); 1117 error = rdwri(UIO_READ, ip, (caddr_t)dp, MINDIRSIZ, 1118 off, 1, &count); 1119 /* 1120 * Since we read MINDIRSIZ, residual must 1121 * be 0 unless we're at end of file. 1122 */ 1123 if (error || count != 0) 1124 return (0); 1125 /* skip empty entries */ 1126 if (dp->d_ino == 0) 1127 continue; 1128 /* accept only "." and ".." */ 1129 if (dp->d_namlen > 2) 1130 return (0); 1131 if (dp->d_name[0] != '.') 1132 return (0); 1133 /* 1134 * At this point d_namlen must be 1 or 2. 1135 * 1 implies ".", 2 implies ".." if second 1136 * char is also "." 1137 */ 1138 if (dp->d_namlen == 1) 1139 continue; 1140 if (dp->d_name[1] == '.' && dp->d_ino == parentino) 1141 continue; 1142 return (0); 1143 } 1144 return (1); 1145 } 1146 1147 /* 1148 * Check if source directory is in the path of the target directory. 1149 * Target is supplied locked, source is unlocked. 1150 * The target is always iput() before returning. 1151 */ 1152 checkpath(source, target) 1153 struct inode *source, *target; 1154 { 1155 struct dirtemplate dirbuf; 1156 register struct inode *ip; 1157 int error = 0; 1158 1159 ip = target; 1160 if (ip->i_number == source->i_number) { 1161 error = EEXIST; 1162 goto out; 1163 } 1164 if (ip->i_number == ROOTINO) 1165 goto out; 1166 1167 for (;;) { 1168 if ((ip->i_mode&IFMT) != IFDIR) { 1169 error = ENOTDIR; 1170 break; 1171 } 1172 error = rdwri(UIO_READ, ip, (caddr_t)&dirbuf, 1173 sizeof (struct dirtemplate), (off_t)0, 1, (int *)0); 1174 if (error != 0) 1175 break; 1176 if (dirbuf.dotdot_namlen != 2 || 1177 dirbuf.dotdot_name[0] != '.' || 1178 dirbuf.dotdot_name[1] != '.') { 1179 error = ENOTDIR; 1180 break; 1181 } 1182 if (dirbuf.dotdot_ino == source->i_number) { 1183 error = EINVAL; 1184 break; 1185 } 1186 if (dirbuf.dotdot_ino == ROOTINO) 1187 break; 1188 iput(ip); 1189 ip = iget(ip->i_dev, ip->i_fs, dirbuf.dotdot_ino); 1190 if (ip == NULL) { 1191 error = u.u_error; 1192 break; 1193 } 1194 } 1195 1196 out: 1197 if (error == ENOTDIR) 1198 printf("checkpath: .. not a directory\n"); 1199 if (ip != NULL) 1200 iput(ip); 1201 return (error); 1202 } 1203 1204 /* 1205 * Name cache initialization, from main() when we are booting 1206 */ 1207 nchinit() 1208 { 1209 register union nchash *nchp; 1210 register struct nch *ncp; 1211 1212 nchhead = 0; 1213 nchtail = &nchhead; 1214 1215 for (ncp = nch; ncp < &nch[nchsize]; ncp++) { 1216 ncp->nc_forw = ncp; /* hash chain */ 1217 ncp->nc_back = ncp; 1218 1219 ncp->nc_nxt = NULL; /* lru chain */ 1220 *nchtail = ncp; 1221 ncp->nc_prev = nchtail; 1222 nchtail = &ncp->nc_nxt; 1223 1224 /* all else is zero already */ 1225 } 1226 1227 for (nchp = nchash; nchp < &nchash[NCHHASH]; nchp++) { 1228 nchp->nch_head[0] = nchp; 1229 nchp->nch_head[1] = nchp; 1230 } 1231 } 1232 1233 /* 1234 * Cache flush, called when filesys is umounted to 1235 * remove entries that would now be invalid 1236 * 1237 * The line "nxtcp = nchhead" near the end is to avoid potential problems 1238 * if the cache lru chain is modified while we are dumping the 1239 * inode. This makes the algorithm O(n^2), but do you think I care? 1240 */ 1241 nchinval(dev) 1242 register dev_t dev; 1243 { 1244 register struct nch *ncp, *nxtcp; 1245 1246 for (ncp = nchhead; ncp; ncp = nxtcp) { 1247 nxtcp = ncp->nc_nxt; 1248 1249 if (ncp->nc_ip == NULL || 1250 (ncp->nc_idev != dev && ncp->nc_dev != dev)) 1251 continue; 1252 1253 /* free the resources we had */ 1254 ncp->nc_idev = NODEV; 1255 ncp->nc_dev = NODEV; 1256 ncp->nc_id = NULL; 1257 ncp->nc_ino = 0; 1258 ncp->nc_ip = NULL; 1259 1260 1261 /* remove the entry from its hash chain */ 1262 remque(ncp); 1263 /* and make a dummy one */ 1264 ncp->nc_forw = ncp; 1265 ncp->nc_back = ncp; 1266 1267 /* delete this entry from LRU chain */ 1268 *ncp->nc_prev = nxtcp; 1269 if (nxtcp) 1270 nxtcp->nc_prev = ncp->nc_prev; 1271 else 1272 nchtail = ncp->nc_prev; 1273 1274 /* cause rescan of list, it may have altered */ 1275 nxtcp = nchhead; 1276 /* put the now-free entry at head of LRU */ 1277 ncp->nc_nxt = nxtcp; 1278 ncp->nc_prev = &nchhead; 1279 nxtcp->nc_prev = &ncp->nc_nxt; 1280 nchhead = ncp; 1281 } 1282 } 1283 1284 /* 1285 * Name cache invalidation of all entries. 1286 */ 1287 cacheinvalall() 1288 { 1289 register struct nch *ncp; 1290 1291 for (ncp = nch; ncp < &nch[nchsize]; ncp++) { 1292 ncp->nc_id = 0; 1293 } 1294 } 1295