]> git.saurik.com Git - apple/xnu.git/blob - bsd/vfs/vfs_cache.c
projects / apple / xnu.git / blob
? search:


1575aafea967f29df2c31facbde3e41d31f9cea4
[apple/xnu.git] / bsd / vfs / vfs_cache.c
1 /*
2 * Copyright (c) 2000-2015 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
29 /*
30 * Copyright (c) 1989, 1993, 1995
31 * The Regents of the University of California. All rights reserved.
32 *
33 * This code is derived from software contributed to Berkeley by
34 * Poul-Henning Kamp of the FreeBSD Project.
35 *
36 * Redistribution and use in source and binary forms, with or without
37 * modification, are permitted provided that the following conditions
38 * are met:
39 * 1. Redistributions of source code must retain the above copyright
40 * notice, this list of conditions and the following disclaimer.
41 * 2. Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimer in the
43 * documentation and/or other materials provided with the distribution.
44 * 3. All advertising materials mentioning features or use of this software
45 * must display the following acknowledgement:
46 * This product includes software developed by the University of
47 * California, Berkeley and its contributors.
48 * 4. Neither the name of the University nor the names of its contributors
49 * may be used to endorse or promote products derived from this software
50 * without specific prior written permission.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * SUCH DAMAGE.
63 *
64 *
65 * @(#)vfs_cache.c 8.5 (Berkeley) 3/22/95
66 */
67 /*
68 * NOTICE: This file was modified by SPARTA, Inc. in 2005 to introduce
69 * support for mandatory and extensible security protections. This notice
70 * is included in support of clause 2.2 (b) of the Apple Public License,
71 * Version 2.0.
72 */
73 #include <sys/param.h>
74 #include <sys/systm.h>
75 #include <sys/time.h>
76 #include <sys/mount_internal.h>
77 #include <sys/vnode_internal.h>
78 #include <miscfs/specfs/specdev.h>
79 #include <sys/namei.h>
80 #include <sys/errno.h>
81 #include <sys/malloc.h>
82 #include <sys/kauth.h>
83 #include <sys/user.h>
84 #include <sys/paths.h>
85
86 #if CONFIG_MACF
87 #include <security/mac_framework.h>
88 #endif
89
90 /*
91 * Name caching works as follows:
92 *
93 * Names found by directory scans are retained in a cache
94 * for future reference. It is managed LRU, so frequently
95 * used names will hang around. Cache is indexed by hash value
96 * obtained from (vp, name) where vp refers to the directory
97 * containing name.
98 *
99 * If it is a "negative" entry, (i.e. for a name that is known NOT to
100 * exist) the vnode pointer will be NULL.
101 *
102 * Upon reaching the last segment of a path, if the reference
103 * is for DELETE, or NOCACHE is set (rewrite), and the
104 * name is located in the cache, it will be dropped.
105 */
106
107 /*
108 * Structures associated with name cacheing.
109 */
110
111 LIST_HEAD(nchashhead, namecache) *nchashtbl; /* Hash Table */
112 u_long nchashmask;
113 u_long nchash; /* size of hash table - 1 */
114 long numcache; /* number of cache entries allocated */
115 int desiredNodes;
116 int desiredNegNodes;
117 int ncs_negtotal;
118 int nc_disabled = 0;
119 TAILQ_HEAD(, namecache) nchead; /* chain of all name cache entries */
120 TAILQ_HEAD(, namecache) neghead; /* chain of only negative cache entries */
121
122
123 #if COLLECT_STATS
124
125 struct nchstats nchstats; /* cache effectiveness statistics */
126
127 #define NCHSTAT(v) { \
128 nchstats.v++; \
129 }
130 #define NAME_CACHE_LOCK() name_cache_lock()
131 #define NAME_CACHE_UNLOCK() name_cache_unlock()
132 #define NAME_CACHE_LOCK_SHARED() name_cache_lock()
133
134 #else
135
136 #define NCHSTAT(v)
137 #define NAME_CACHE_LOCK() name_cache_lock()
138 #define NAME_CACHE_UNLOCK() name_cache_unlock()
139 #define NAME_CACHE_LOCK_SHARED() name_cache_lock_shared()
140
141 #endif
142
143
144 /* vars for name cache list lock */
145 lck_grp_t * namecache_lck_grp;
146 lck_grp_attr_t * namecache_lck_grp_attr;
147 lck_attr_t * namecache_lck_attr;
148
149 lck_grp_t * strcache_lck_grp;
150 lck_grp_attr_t * strcache_lck_grp_attr;
151 lck_attr_t * strcache_lck_attr;
152
153 lck_rw_t * namecache_rw_lock;
154 lck_rw_t * strtable_rw_lock;
155
156 #define NUM_STRCACHE_LOCKS 1024
157
158 lck_mtx_t strcache_mtx_locks[NUM_STRCACHE_LOCKS];
159
160
161 static vnode_t cache_lookup_locked(vnode_t dvp, struct componentname *cnp);
162 static const char *add_name_internal(const char *, uint32_t, u_int, boolean_t, u_int);
163 static void init_string_table(void);
164 static void cache_delete(struct namecache *, int);
165 static void cache_enter_locked(vnode_t dvp, vnode_t vp, struct componentname *cnp, const char *strname);
166
167 #ifdef DUMP_STRING_TABLE
168 /*
169 * Internal dump function used for debugging
170 */
171 void dump_string_table(void);
172 #endif /* DUMP_STRING_TABLE */
173
174 static void init_crc32(void);
175 static unsigned int crc32tab[256];
176
177
178 #define NCHHASH(dvp, hash_val) \
179 (&nchashtbl[(dvp->v_id ^ (hash_val)) & nchashmask])
180
181
182
183 /*
184 * This function builds the path to a filename in "buff". The
185 * length of the buffer *INCLUDING* the trailing zero byte is
186 * returned in outlen. NOTE: the length includes the trailing
187 * zero byte and thus the length is one greater than what strlen
188 * would return. This is important and lots of code elsewhere
189 * in the kernel assumes this behavior.
190 *
191 * This function can call vnop in file system if the parent vnode
192 * does not exist or when called for hardlinks via volfs path.
193 * If BUILDPATH_NO_FS_ENTER is set in flags, it only uses values present
194 * in the name cache and does not enter the file system.
195 *
196 * If BUILDPATH_CHECK_MOVED is set in flags, we return EAGAIN when
197 * we encounter ENOENT during path reconstruction. ENOENT means that
198 * one of the parents moved while we were building the path. The
199 * caller can special handle this case by calling build_path again.
200 *
201 * If BUILDPATH_VOLUME_RELATIVE is set in flags, we return path
202 * that is relative to the nearest mount point, i.e. do not
203 * cross over mount points during building the path.
204 *
205 * passed in vp must have a valid io_count reference
206 */
207 int
208 build_path(vnode_t first_vp, char *buff, int buflen, int *outlen, int flags, vfs_context_t ctx)
209 {
210 vnode_t vp, tvp;
211 vnode_t vp_with_iocount;
212 vnode_t proc_root_dir_vp;
213 char *end;
214 const char *str;
215 int len;
216 int ret = 0;
217 int fixhardlink;
218
219 if (first_vp == NULLVP)
220 return (EINVAL);
221
222 if (buflen <= 1)
223 return (ENOSPC);
224
225 /*
226 * Grab the process fd so we can evaluate fd_rdir.
227 */
228 if (vfs_context_proc(ctx)->p_fd)
229 proc_root_dir_vp = vfs_context_proc(ctx)->p_fd->fd_rdir;
230 else
231 proc_root_dir_vp = NULL;
232
233 vp_with_iocount = NULLVP;
234 again:
235 vp = first_vp;
236
237 end = &buff[buflen-1];
238 *end = '\0';
239
240 /*
241 * holding the NAME_CACHE_LOCK in shared mode is
242 * sufficient to stabilize both the vp->v_parent chain
243 * and the 'vp->v_mount->mnt_vnodecovered' chain
244 *
245 * if we need to drop this lock, we must first grab the v_id
246 * from the vnode we're currently working with... if that
247 * vnode doesn't already have an io_count reference (the vp
248 * passed in comes with one), we must grab a reference
249 * after we drop the NAME_CACHE_LOCK via vnode_getwithvid...
250 * deadlocks may result if you call vnode_get while holding
251 * the NAME_CACHE_LOCK... we lazily release the reference
252 * we pick up the next time we encounter a need to drop
253 * the NAME_CACHE_LOCK or before we return from this routine
254 */
255 NAME_CACHE_LOCK_SHARED();
256
257 /*
258 * Check if this is the root of a file system.
259 */
260 while (vp && vp->v_flag & VROOT) {
261 if (vp->v_mount == NULL) {
262 ret = EINVAL;
263 goto out_unlock;
264 }
265 if ((vp->v_mount->mnt_flag & MNT_ROOTFS) || (vp == proc_root_dir_vp)) {
266 /*
267 * It's the root of the root file system, so it's
268 * just "/".
269 */
270 *--end = '/';
271
272 goto out_unlock;
273 } else {
274 /*
275 * This the root of the volume and the caller does not
276 * want to cross mount points. Therefore just return
277 * '/' as the relative path.
278 */
279 if (flags & BUILDPATH_VOLUME_RELATIVE) {
280 *--end = '/';
281 goto out_unlock;
282 } else {
283 vp = vp->v_mount->mnt_vnodecovered;
284 }
285 }
286 }
287
288 while ((vp != NULLVP) && (vp->v_parent != vp)) {
289 int vid;
290
291 /*
292 * For hardlinks the v_name may be stale, so if its OK
293 * to enter a file system, ask the file system for the
294 * name and parent (below).
295 */
296 fixhardlink = (vp->v_flag & VISHARDLINK) &&
297 (vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID) &&
298 !(flags & BUILDPATH_NO_FS_ENTER);
299
300 if (!fixhardlink) {
301 str = vp->v_name;
302
303 if (str == NULL || *str == '\0') {
304 if (vp->v_parent != NULL)
305 ret = EINVAL;
306 else
307 ret = ENOENT;
308 goto out_unlock;
309 }
310 len = strlen(str);
311 /*
312 * Check that there's enough space (including space for the '/')
313 */
314 if ((end - buff) < (len + 1)) {
315 ret = ENOSPC;
316 goto out_unlock;
317 }
318 /*
319 * Copy the name backwards.
320 */
321 str += len;
322
323 for (; len > 0; len--)
324 *--end = *--str;
325 /*
326 * Add a path separator.
327 */
328 *--end = '/';
329 }
330
331 /*
332 * Walk up the parent chain.
333 */
334 if (((vp->v_parent != NULLVP) && !fixhardlink) ||
335 (flags & BUILDPATH_NO_FS_ENTER)) {
336
337 /*
338 * In this if () block we are not allowed to enter the filesystem
339 * to conclusively get the most accurate parent identifier.
340 * As a result, if 'vp' does not identify '/' and it
341 * does not have a valid v_parent, then error out
342 * and disallow further path construction
343 */
344 if ((vp->v_parent == NULLVP) && (rootvnode != vp)) {
345 /*
346 * Only '/' is allowed to have a NULL parent
347 * pointer. Upper level callers should ideally
348 * re-drive name lookup on receiving a ENOENT.
349 */
350 ret = ENOENT;
351
352 /* The code below will exit early if 'tvp = vp' == NULL */
353 }
354 vp = vp->v_parent;
355
356 /*
357 * if the vnode we have in hand isn't a directory and it
358 * has a v_parent, then we started with the resource fork
359 * so skip up to avoid getting a duplicate copy of the
360 * file name in the path.
361 */
362 if (vp && !vnode_isdir(vp) && vp->v_parent) {
363 vp = vp->v_parent;
364 }
365 } else {
366 /*
367 * No parent, go get it if supported.
368 */
369 struct vnode_attr va;
370 vnode_t dvp;
371
372 /*
373 * Make sure file system supports obtaining a path from id.
374 */
375 if (!(vp->v_mount->mnt_kern_flag & MNTK_PATH_FROM_ID)) {
376 ret = ENOENT;
377 goto out_unlock;
378 }
379 vid = vp->v_id;
380
381 NAME_CACHE_UNLOCK();
382
383 if (vp != first_vp && vp != vp_with_iocount) {
384 if (vp_with_iocount) {
385 vnode_put(vp_with_iocount);
386 vp_with_iocount = NULLVP;
387 }
388 if (vnode_getwithvid(vp, vid))
389 goto again;
390 vp_with_iocount = vp;
391 }
392 VATTR_INIT(&va);
393 VATTR_WANTED(&va, va_parentid);
394
395 if (fixhardlink) {
396 VATTR_WANTED(&va, va_name);
397 MALLOC_ZONE(va.va_name, caddr_t, MAXPATHLEN, M_NAMEI, M_WAITOK);
398 } else {
399 va.va_name = NULL;
400 }
401 /*
402 * Ask the file system for its parent id and for its name (optional).
403 */
404 ret = vnode_getattr(vp, &va, ctx);
405
406 if (fixhardlink) {
407 if ((ret == 0) && (VATTR_IS_SUPPORTED(&va, va_name))) {
408 str = va.va_name;
409 vnode_update_identity(vp, NULL, str, strlen(str), 0, VNODE_UPDATE_NAME);
410 } else if (vp->v_name) {
411 str = vp->v_name;
412 ret = 0;
413 } else {
414 ret = ENOENT;
415 goto bad_news;
416 }
417 len = strlen(str);
418
419 /*
420 * Check that there's enough space.
421 */
422 if ((end - buff) < (len + 1)) {
423 ret = ENOSPC;
424 } else {
425 /* Copy the name backwards. */
426 str += len;
427
428 for (; len > 0; len--) {
429 *--end = *--str;
430 }
431 /*
432 * Add a path separator.
433 */
434 *--end = '/';
435 }
436 bad_news:
437 FREE_ZONE(va.va_name, MAXPATHLEN, M_NAMEI);
438 }
439 if (ret || !VATTR_IS_SUPPORTED(&va, va_parentid)) {
440 ret = ENOENT;
441 goto out;
442 }
443 /*
444 * Ask the file system for the parent vnode.
445 */
446 if ((ret = VFS_VGET(vp->v_mount, (ino64_t)va.va_parentid, &dvp, ctx)))
447 goto out;
448
449 if (!fixhardlink && (vp->v_parent != dvp))
450 vnode_update_identity(vp, dvp, NULL, 0, 0, VNODE_UPDATE_PARENT);
451
452 if (vp_with_iocount)
453 vnode_put(vp_with_iocount);
454 vp = dvp;
455 vp_with_iocount = vp;
456
457 NAME_CACHE_LOCK_SHARED();
458
459 /*
460 * if the vnode we have in hand isn't a directory and it
461 * has a v_parent, then we started with the resource fork
462 * so skip up to avoid getting a duplicate copy of the
463 * file name in the path.
464 */
465 if (vp && !vnode_isdir(vp) && vp->v_parent)
466 vp = vp->v_parent;
467 }
468
469 /*
470 * When a mount point is crossed switch the vp.
471 * Continue until we find the root or we find
472 * a vnode that's not the root of a mounted
473 * file system.
474 */
475 tvp = vp;
476
477 while (tvp) {
478 if (tvp == proc_root_dir_vp)
479 goto out_unlock; /* encountered the root */
480
481 if (!(tvp->v_flag & VROOT) || !tvp->v_mount)
482 break; /* not the root of a mounted FS */
483
484 if (flags & BUILDPATH_VOLUME_RELATIVE) {
485 /* Do not cross over mount points */
486 tvp = NULL;
487 } else {
488 tvp = tvp->v_mount->mnt_vnodecovered;
489 }
490 }
491 if (tvp == NULLVP)
492 goto out_unlock;
493 vp = tvp;
494
495 if (vp && (flags & BUILDPATH_CHECKACCESS)) {
496 vid = vp->v_id;
497
498 NAME_CACHE_UNLOCK();
499
500 if (vp != first_vp && vp != vp_with_iocount) {
501 if (vp_with_iocount) {
502 vnode_put(vp_with_iocount);
503 vp_with_iocount = NULLVP;
504 }
505 if (vnode_getwithvid(vp, vid))
506 goto again;
507 vp_with_iocount = vp;
508 }
509 if ((ret = vnode_authorize(vp, NULL, KAUTH_VNODE_SEARCH, ctx)))
510 goto out; /* no peeking */
511
512 NAME_CACHE_LOCK_SHARED();
513 }
514 }
515 out_unlock:
516 NAME_CACHE_UNLOCK();
517 out:
518 if (vp_with_iocount)
519 vnode_put(vp_with_iocount);
520 /*
521 * Slide the name down to the beginning of the buffer.
522 */
523 memmove(buff, end, &buff[buflen] - end);
524
525 /*
526 * length includes the trailing zero byte
527 */
528 *outlen = &buff[buflen] - end;
529
530 /* One of the parents was moved during path reconstruction.
531 * The caller is interested in knowing whether any of the
532 * parents moved via BUILDPATH_CHECK_MOVED, so return EAGAIN.
533 */
534 if ((ret == ENOENT) && (flags & BUILDPATH_CHECK_MOVED)) {
535 ret = EAGAIN;
536 }
537
538 return (ret);
539 }
540
541
542 /*
543 * return NULLVP if vp's parent doesn't
544 * exist, or we can't get a valid iocount
545 * else return the parent of vp
546 */
547 vnode_t
548 vnode_getparent(vnode_t vp)
549 {
550 vnode_t pvp = NULLVP;
551 int pvid;
552
553 NAME_CACHE_LOCK_SHARED();
554 /*
555 * v_parent is stable behind the name_cache lock
556 * however, the only thing we can really guarantee
557 * is that we've grabbed a valid iocount on the
558 * parent of 'vp' at the time we took the name_cache lock...
559 * once we drop the lock, vp could get re-parented
560 */
561 if ( (pvp = vp->v_parent) != NULLVP ) {
562 pvid = pvp->v_id;
563
564 NAME_CACHE_UNLOCK();
565
566 if (vnode_getwithvid(pvp, pvid) != 0)
567 pvp = NULL;
568 } else
569 NAME_CACHE_UNLOCK();
570 return (pvp);
571 }
572
573 const char *
574 vnode_getname(vnode_t vp)
575 {
576 const char *name = NULL;
577
578 NAME_CACHE_LOCK_SHARED();
579
580 if (vp->v_name)
581 name = vfs_addname(vp->v_name, strlen(vp->v_name), 0, 0);
582 NAME_CACHE_UNLOCK();
583
584 return (name);
585 }
586
587 void
588 vnode_putname(const char *name)
589 {
590 vfs_removename(name);
591 }
592
593 static const char unknown_vnodename[] = "(unknown vnode name)";
594
595 const char *
596 vnode_getname_printable(vnode_t vp)
597 {
598 const char *name = vnode_getname(vp);
599 if (name != NULL)
600 return name;
601
602 switch (vp->v_type) {
603 case VCHR:
604 case VBLK:
605 {
606 /*
607 * Create an artificial dev name from
608 * major and minor device number
609 */
610 char dev_name[64];
611 (void) snprintf(dev_name, sizeof(dev_name),
612 "%c(%u, %u)", VCHR == vp->v_type ? 'c':'b',
613 major(vp->v_rdev), minor(vp->v_rdev));
614 /*
615 * Add the newly created dev name to the name
616 * cache to allow easier cleanup. Also,
617 * vfs_addname allocates memory for the new name
618 * and returns it.
619 */
620 NAME_CACHE_LOCK_SHARED();
621 name = vfs_addname(dev_name, strlen(dev_name), 0, 0);
622 NAME_CACHE_UNLOCK();
623 return name;
624 }
625 default:
626 return unknown_vnodename;
627 }
628 }
629
630 void
631 vnode_putname_printable(const char *name)
632 {
633 if (name == unknown_vnodename)
634 return;
635 vnode_putname(name);
636 }
637
638
639 /*
640 * if VNODE_UPDATE_PARENT, and we can take
641 * a reference on dvp, then update vp with
642 * it's new parent... if vp already has a parent,
643 * then drop the reference vp held on it
644 *
645 * if VNODE_UPDATE_NAME,
646 * then drop string ref on v_name if it exists, and if name is non-NULL
647 * then pick up a string reference on name and record it in v_name...
648 * optionally pass in the length and hashval of name if known
649 *
650 * if VNODE_UPDATE_CACHE, flush the name cache entries associated with vp
651 */
652 void
653 vnode_update_identity(vnode_t vp, vnode_t dvp, const char *name, int name_len, uint32_t name_hashval, int flags)
654 {
655 struct namecache *ncp;
656 vnode_t old_parentvp = NULLVP;
657 #if NAMEDSTREAMS
658 int isstream = (vp->v_flag & VISNAMEDSTREAM);
659 int kusecountbumped = 0;
660 #endif
661 kauth_cred_t tcred = NULL;
662 const char *vname = NULL;
663 const char *tname = NULL;
664
665 if (flags & VNODE_UPDATE_PARENT) {
666 if (dvp && vnode_ref(dvp) != 0) {
667 dvp = NULLVP;
668 }
669 #if NAMEDSTREAMS
670 /* Don't count a stream's parent ref during unmounts */
671 if (isstream && dvp && (dvp != vp) && (dvp != vp->v_parent) && (dvp->v_type == VREG)) {
672 vnode_lock_spin(dvp);
673 ++dvp->v_kusecount;
674 kusecountbumped = 1;
675 vnode_unlock(dvp);
676 }
677 #endif
678 } else {
679 dvp = NULLVP;
680 }
681 if ( (flags & VNODE_UPDATE_NAME) ) {
682 if (name != vp->v_name) {
683 if (name && *name) {
684 if (name_len == 0)
685 name_len = strlen(name);
686 tname = vfs_addname(name, name_len, name_hashval, 0);
687 }
688 } else
689 flags &= ~VNODE_UPDATE_NAME;
690 }
691 if ( (flags & (VNODE_UPDATE_PURGE | VNODE_UPDATE_PARENT | VNODE_UPDATE_CACHE | VNODE_UPDATE_NAME)) ) {
692
693 NAME_CACHE_LOCK();
694
695 if ( (flags & VNODE_UPDATE_PURGE) ) {
696
697 if (vp->v_parent)
698 vp->v_parent->v_nc_generation++;
699
700 while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
701 cache_delete(ncp, 1);
702
703 while ( (ncp = LIST_FIRST(&vp->v_ncchildren)) )
704 cache_delete(ncp, 1);
705
706 /*
707 * Use a temp variable to avoid kauth_cred_unref() while NAME_CACHE_LOCK is held
708 */
709 tcred = vp->v_cred;
710 vp->v_cred = NOCRED;
711 vp->v_authorized_actions = 0;
712 }
713 if ( (flags & VNODE_UPDATE_NAME) ) {
714 vname = vp->v_name;
715 vp->v_name = tname;
716 }
717 if (flags & VNODE_UPDATE_PARENT) {
718 if (dvp != vp && dvp != vp->v_parent) {
719 old_parentvp = vp->v_parent;
720 vp->v_parent = dvp;
721 dvp = NULLVP;
722
723 if (old_parentvp)
724 flags |= VNODE_UPDATE_CACHE;
725 }
726 }
727 if (flags & VNODE_UPDATE_CACHE) {
728 while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
729 cache_delete(ncp, 1);
730 }
731 NAME_CACHE_UNLOCK();
732
733 if (vname != NULL)
734 vfs_removename(vname);
735
736 if (IS_VALID_CRED(tcred))
737 kauth_cred_unref(&tcred);
738 }
739 if (dvp != NULLVP) {
740 #if NAMEDSTREAMS
741 /* Back-out the ref we took if we lost a race for vp->v_parent. */
742 if (kusecountbumped) {
743 vnode_lock_spin(dvp);
744 if (dvp->v_kusecount > 0)
745 --dvp->v_kusecount;
746 vnode_unlock(dvp);
747 }
748 #endif
749 vnode_rele(dvp);
750 }
751 if (old_parentvp) {
752 struct uthread *ut;
753
754 #if NAMEDSTREAMS
755 if (isstream) {
756 vnode_lock_spin(old_parentvp);
757 if ((old_parentvp->v_type != VDIR) && (old_parentvp->v_kusecount > 0))
758 --old_parentvp->v_kusecount;
759 vnode_unlock(old_parentvp);
760 }
761 #endif
762 ut = get_bsdthread_info(current_thread());
763
764 /*
765 * indicated to vnode_rele that it shouldn't do a
766 * vnode_reclaim at this time... instead it will
767 * chain the vnode to the uu_vreclaims list...
768 * we'll be responsible for calling vnode_reclaim
769 * on each of the vnodes in this list...
770 */
771 ut->uu_defer_reclaims = 1;
772 ut->uu_vreclaims = NULLVP;
773
774 while ( (vp = old_parentvp) != NULLVP ) {
775
776 vnode_lock_spin(vp);
777 vnode_rele_internal(vp, 0, 0, 1);
778
779 /*
780 * check to see if the vnode is now in the state
781 * that would have triggered a vnode_reclaim in vnode_rele
782 * if it is, we save it's parent pointer and then NULL
783 * out the v_parent field... we'll drop the reference
784 * that was held on the next iteration of this loop...
785 * this short circuits a potential deep recursion if we
786 * have a long chain of parents in this state...
787 * we'll sit in this loop until we run into
788 * a parent in this chain that is not in this state
789 *
790 * make our check and the vnode_rele atomic
791 * with respect to the current vnode we're working on
792 * by holding the vnode lock
793 * if vnode_rele deferred the vnode_reclaim and has put
794 * this vnode on the list to be reaped by us, than
795 * it has left this vnode with an iocount == 1
796 */
797 if ( (vp->v_iocount == 1) && (vp->v_usecount == 0) &&
798 ((vp->v_lflag & (VL_MARKTERM | VL_TERMINATE | VL_DEAD)) == VL_MARKTERM)) {
799 /*
800 * vnode_rele wanted to do a vnode_reclaim on this vnode
801 * it should be sitting on the head of the uu_vreclaims chain
802 * pull the parent pointer now so that when we do the
803 * vnode_reclaim for each of the vnodes in the uu_vreclaims
804 * list, we won't recurse back through here
805 *
806 * need to do a convert here in case vnode_rele_internal
807 * returns with the lock held in the spin mode... it
808 * can drop and retake the lock under certain circumstances
809 */
810 vnode_lock_convert(vp);
811
812 NAME_CACHE_LOCK();
813 old_parentvp = vp->v_parent;
814 vp->v_parent = NULLVP;
815 NAME_CACHE_UNLOCK();
816 } else {
817 /*
818 * we're done... we ran into a vnode that isn't
819 * being terminated
820 */
821 old_parentvp = NULLVP;
822 }
823 vnode_unlock(vp);
824 }
825 ut->uu_defer_reclaims = 0;
826
827 while ( (vp = ut->uu_vreclaims) != NULLVP) {
828 ut->uu_vreclaims = vp->v_defer_reclaimlist;
829
830 /*
831 * vnode_put will drive the vnode_reclaim if
832 * we are still the only reference on this vnode
833 */
834 vnode_put(vp);
835 }
836 }
837 }
838
839
840 /*
841 * Mark a vnode as having multiple hard links. HFS makes use of this
842 * because it keeps track of each link separately, and wants to know
843 * which link was actually used.
844 *
845 * This will cause the name cache to force a VNOP_LOOKUP on the vnode
846 * so that HFS can post-process the lookup. Also, volfs will call
847 * VNOP_GETATTR2 to determine the parent, instead of using v_parent.
848 */
849 void vnode_setmultipath(vnode_t vp)
850 {
851 vnode_lock_spin(vp);
852
853 /*
854 * In theory, we're changing the vnode's identity as far as the
855 * name cache is concerned, so we ought to grab the name cache lock
856 * here. However, there is already a race, and grabbing the name
857 * cache lock only makes the race window slightly smaller.
858 *
859 * The race happens because the vnode already exists in the name
860 * cache, and could be found by one thread before another thread
861 * can set the hard link flag.
862 */
863
864 vp->v_flag |= VISHARDLINK;
865
866 vnode_unlock(vp);
867 }
868
869
870
871 /*
872 * backwards compatibility
873 */
874 void vnode_uncache_credentials(vnode_t vp)
875 {
876 vnode_uncache_authorized_action(vp, KAUTH_INVALIDATE_CACHED_RIGHTS);
877 }
878
879
880 /*
881 * use the exclusive form of NAME_CACHE_LOCK to protect the update of the
882 * following fields in the vnode: v_cred_timestamp, v_cred, v_authorized_actions
883 * we use this lock so that we can look at the v_cred and v_authorized_actions
884 * atomically while behind the NAME_CACHE_LOCK in shared mode in 'cache_lookup_path',
885 * which is the super-hot path... if we are updating the authorized actions for this
886 * vnode, we are already in the super-slow and far less frequented path so its not
887 * that bad that we take the lock exclusive for this case... of course we strive
888 * to hold it for the minimum amount of time possible
889 */
890
891 void vnode_uncache_authorized_action(vnode_t vp, kauth_action_t action)
892 {
893 kauth_cred_t tcred = NOCRED;
894
895 NAME_CACHE_LOCK();
896
897 vp->v_authorized_actions &= ~action;
898
899 if (action == KAUTH_INVALIDATE_CACHED_RIGHTS &&
900 IS_VALID_CRED(vp->v_cred)) {
901 /*
902 * Use a temp variable to avoid kauth_cred_unref() while NAME_CACHE_LOCK is held
903 */
904 tcred = vp->v_cred;
905 vp->v_cred = NOCRED;
906 }
907 NAME_CACHE_UNLOCK();
908
909 if (tcred != NOCRED)
910 kauth_cred_unref(&tcred);
911 }
912
913
914 extern int bootarg_vnode_cache_defeat; /* default = 0, from bsd_init.c */
915
916 boolean_t
917 vnode_cache_is_authorized(vnode_t vp, vfs_context_t ctx, kauth_action_t action)
918 {
919 kauth_cred_t ucred;
920 boolean_t retval = FALSE;
921
922 /* Boot argument to defeat rights caching */
923 if (bootarg_vnode_cache_defeat)
924 return FALSE;
925
926 if ( (vp->v_mount->mnt_kern_flag & (MNTK_AUTH_OPAQUE | MNTK_AUTH_CACHE_TTL)) ) {
927 /*
928 * a TTL is enabled on the rights cache... handle it here
929 * a TTL of 0 indicates that no rights should be cached
930 */
931 if (vp->v_mount->mnt_authcache_ttl) {
932 if ( !(vp->v_mount->mnt_kern_flag & MNTK_AUTH_CACHE_TTL) ) {
933 /*
934 * For filesystems marked only MNTK_AUTH_OPAQUE (generally network ones),
935 * we will only allow a SEARCH right on a directory to be cached...
936 * that cached right always has a default TTL associated with it
937 */
938 if (action != KAUTH_VNODE_SEARCH || vp->v_type != VDIR)
939 vp = NULLVP;
940 }
941 if (vp != NULLVP && vnode_cache_is_stale(vp) == TRUE) {
942 vnode_uncache_authorized_action(vp, vp->v_authorized_actions);
943 vp = NULLVP;
944 }
945 } else
946 vp = NULLVP;
947 }
948 if (vp != NULLVP) {
949 ucred = vfs_context_ucred(ctx);
950
951 NAME_CACHE_LOCK_SHARED();
952
953 if (vp->v_cred == ucred && (vp->v_authorized_actions & action) == action)
954 retval = TRUE;
955
956 NAME_CACHE_UNLOCK();
957 }
958 return retval;
959 }
960
961
962 void vnode_cache_authorized_action(vnode_t vp, vfs_context_t ctx, kauth_action_t action)
963 {
964 kauth_cred_t tcred = NOCRED;
965 kauth_cred_t ucred;
966 struct timeval tv;
967 boolean_t ttl_active = FALSE;
968
969 ucred = vfs_context_ucred(ctx);
970
971 if (!IS_VALID_CRED(ucred) || action == 0)
972 return;
973
974 if ( (vp->v_mount->mnt_kern_flag & (MNTK_AUTH_OPAQUE | MNTK_AUTH_CACHE_TTL)) ) {
975 /*
976 * a TTL is enabled on the rights cache... handle it here
977 * a TTL of 0 indicates that no rights should be cached
978 */
979 if (vp->v_mount->mnt_authcache_ttl == 0)
980 return;
981
982 if ( !(vp->v_mount->mnt_kern_flag & MNTK_AUTH_CACHE_TTL) ) {
983 /*
984 * only cache SEARCH action for filesystems marked
985 * MNTK_AUTH_OPAQUE on VDIRs...
986 * the lookup_path code will time these out
987 */
988 if ( (action & ~KAUTH_VNODE_SEARCH) || vp->v_type != VDIR )
989 return;
990 }
991 ttl_active = TRUE;
992
993 microuptime(&tv);
994 }
995 NAME_CACHE_LOCK();
996
997 if (vp->v_cred != ucred) {
998 kauth_cred_ref(ucred);
999 /*
1000 * Use a temp variable to avoid kauth_cred_unref() while NAME_CACHE_LOCK is held
1001 */
1002 tcred = vp->v_cred;
1003 vp->v_cred = ucred;
1004 vp->v_authorized_actions = 0;
1005 }
1006 if (ttl_active == TRUE && vp->v_authorized_actions == 0) {
1007 /*
1008 * only reset the timestamnp on the
1009 * first authorization cached after the previous
1010 * timer has expired or we're switching creds...
1011 * 'vnode_cache_is_authorized' will clear the
1012 * authorized actions if the TTL is active and
1013 * it has expired
1014 */
1015 vp->v_cred_timestamp = tv.tv_sec;
1016 }
1017 vp->v_authorized_actions |= action;
1018
1019 NAME_CACHE_UNLOCK();
1020
1021 if (IS_VALID_CRED(tcred))
1022 kauth_cred_unref(&tcred);
1023 }
1024
1025
1026 boolean_t vnode_cache_is_stale(vnode_t vp)
1027 {
1028 struct timeval tv;
1029 boolean_t retval;
1030
1031 microuptime(&tv);
1032
1033 if ((tv.tv_sec - vp->v_cred_timestamp) > vp->v_mount->mnt_authcache_ttl)
1034 retval = TRUE;
1035 else
1036 retval = FALSE;
1037
1038 return retval;
1039 }
1040
1041
1042
1043 /*
1044 * Returns: 0 Success
1045 * ERECYCLE vnode was recycled from underneath us. Force lookup to be re-driven from namei.
1046 * This errno value should not be seen by anyone outside of the kernel.
1047 */
1048 int
1049 cache_lookup_path(struct nameidata *ndp, struct componentname *cnp, vnode_t dp,
1050 vfs_context_t ctx, int *dp_authorized, vnode_t last_dp)
1051 {
1052 char *cp; /* pointer into pathname argument */
1053 int vid;
1054 int vvid = 0; /* protected by vp != NULLVP */
1055 vnode_t vp = NULLVP;
1056 vnode_t tdp = NULLVP;
1057 kauth_cred_t ucred;
1058 boolean_t ttl_enabled = FALSE;
1059 struct timeval tv;
1060 mount_t mp;
1061 unsigned int hash;
1062 int error = 0;
1063
1064 #if CONFIG_TRIGGERS
1065 vnode_t trigger_vp;
1066 #endif /* CONFIG_TRIGGERS */
1067
1068 ucred = vfs_context_ucred(ctx);
1069 ndp->ni_flag &= ~(NAMEI_TRAILINGSLASH);
1070
1071 NAME_CACHE_LOCK_SHARED();
1072
1073 if ( dp->v_mount && (dp->v_mount->mnt_kern_flag & (MNTK_AUTH_OPAQUE | MNTK_AUTH_CACHE_TTL)) ) {
1074 ttl_enabled = TRUE;
1075 microuptime(&tv);
1076 }
1077 for (;;) {
1078 /*
1079 * Search a directory.
1080 *
1081 * The cn_hash value is for use by cache_lookup
1082 * The last component of the filename is left accessible via
1083 * cnp->cn_nameptr for callers that need the name.
1084 */
1085 hash = 0;
1086 cp = cnp->cn_nameptr;
1087
1088 while (*cp && (*cp != '/')) {
1089 hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
1090 }
1091 /*
1092 * the crc generator can legitimately generate
1093 * a 0... however, 0 for us means that we
1094 * haven't computed a hash, so use 1 instead
1095 */
1096 if (hash == 0)
1097 hash = 1;
1098 cnp->cn_hash = hash;
1099 cnp->cn_namelen = cp - cnp->cn_nameptr;
1100
1101 ndp->ni_pathlen -= cnp->cn_namelen;
1102 ndp->ni_next = cp;
1103
1104 /*
1105 * Replace multiple slashes by a single slash and trailing slashes
1106 * by a null. This must be done before VNOP_LOOKUP() because some
1107 * fs's don't know about trailing slashes. Remember if there were
1108 * trailing slashes to handle symlinks, existing non-directories
1109 * and non-existing files that won't be directories specially later.
1110 */
1111 while (*cp == '/' && (cp[1] == '/' || cp[1] == '\0')) {
1112 cp++;
1113 ndp->ni_pathlen--;
1114
1115 if (*cp == '\0') {
1116 ndp->ni_flag |= NAMEI_TRAILINGSLASH;
1117 *ndp->ni_next = '\0';
1118 }
1119 }
1120 ndp->ni_next = cp;
1121
1122 cnp->cn_flags &= ~(MAKEENTRY | ISLASTCN | ISDOTDOT);
1123
1124 if (*cp == '\0')
1125 cnp->cn_flags |= ISLASTCN;
1126
1127 if (cnp->cn_namelen == 2 && cnp->cn_nameptr[1] == '.' && cnp->cn_nameptr[0] == '.')
1128 cnp->cn_flags |= ISDOTDOT;
1129
1130 *dp_authorized = 0;
1131 #if NAMEDRSRCFORK
1132 /*
1133 * Process a request for a file's resource fork.
1134 *
1135 * Consume the _PATH_RSRCFORKSPEC suffix and tag the path.
1136 */
1137 if ((ndp->ni_pathlen == sizeof(_PATH_RSRCFORKSPEC)) &&
1138 (cp[1] == '.' && cp[2] == '.') &&
1139 bcmp(cp, _PATH_RSRCFORKSPEC, sizeof(_PATH_RSRCFORKSPEC)) == 0) {
1140 /* Skip volfs file systems that don't support native streams. */
1141 if ((dp->v_mount != NULL) &&
1142 (dp->v_mount->mnt_flag & MNT_DOVOLFS) &&
1143 (dp->v_mount->mnt_kern_flag & MNTK_NAMED_STREAMS) == 0) {
1144 goto skiprsrcfork;
1145 }
1146 cnp->cn_flags |= CN_WANTSRSRCFORK;
1147 cnp->cn_flags |= ISLASTCN;
1148 ndp->ni_next[0] = '\0';
1149 ndp->ni_pathlen = 1;
1150 }
1151 skiprsrcfork:
1152 #endif
1153
1154 #if CONFIG_MACF
1155
1156 /*
1157 * Name cache provides authorization caching (see below)
1158 * that will short circuit MAC checks in lookup().
1159 * We must perform MAC check here. On denial
1160 * dp_authorized will remain 0 and second check will
1161 * be perfomed in lookup().
1162 */
1163 if (!(cnp->cn_flags & DONOTAUTH)) {
1164 error = mac_vnode_check_lookup(ctx, dp, cnp);
1165 if (error) {
1166 NAME_CACHE_UNLOCK();
1167 goto errorout;
1168 }
1169 }
1170 #endif /* MAC */
1171 if (ttl_enabled && ((tv.tv_sec - dp->v_cred_timestamp) > dp->v_mount->mnt_authcache_ttl))
1172 break;
1173
1174 /*
1175 * NAME_CACHE_LOCK holds these fields stable
1176 */
1177 if ((dp->v_cred != ucred || !(dp->v_authorized_actions & KAUTH_VNODE_SEARCH)) &&
1178 !(dp->v_authorized_actions & KAUTH_VNODE_SEARCHBYANYONE))
1179 break;
1180
1181 /*
1182 * indicate that we're allowed to traverse this directory...
1183 * even if we fail the cache lookup or decide to bail for
1184 * some other reason, this information is valid and is used
1185 * to avoid doing a vnode_authorize before the call to VNOP_LOOKUP
1186 */
1187 *dp_authorized = 1;
1188
1189 if ( (cnp->cn_flags & (ISLASTCN | ISDOTDOT)) ) {
1190 if (cnp->cn_nameiop != LOOKUP)
1191 break;
1192 if (cnp->cn_flags & LOCKPARENT)
1193 break;
1194 if (cnp->cn_flags & NOCACHE)
1195 break;
1196 if (cnp->cn_flags & ISDOTDOT) {
1197 /*
1198 * Force directory hardlinks to go to
1199 * file system for ".." requests.
1200 */
1201 if (dp && (dp->v_flag & VISHARDLINK)) {
1202 break;
1203 }
1204 /*
1205 * Quit here only if we can't use
1206 * the parent directory pointer or
1207 * don't have one. Otherwise, we'll
1208 * use it below.
1209 */
1210 if ((dp->v_flag & VROOT) ||
1211 dp == ndp->ni_rootdir ||
1212 dp->v_parent == NULLVP)
1213 break;
1214 }
1215 }
1216
1217 if ((cnp->cn_flags & CN_SKIPNAMECACHE)) {
1218 /*
1219 * Force lookup to go to the filesystem with
1220 * all cnp fields set up.
1221 */
1222 break;
1223 }
1224
1225 /*
1226 * "." and ".." aren't supposed to be cached, so check
1227 * for them before checking the cache.
1228 */
1229 if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.')
1230 vp = dp;
1231 else if ( (cnp->cn_flags & ISDOTDOT) )
1232 vp = dp->v_parent;
1233 else {
1234 if ( (vp = cache_lookup_locked(dp, cnp)) == NULLVP)
1235 break;
1236
1237 if ( (vp->v_flag & VISHARDLINK) ) {
1238 /*
1239 * The file system wants a VNOP_LOOKUP on this vnode
1240 */
1241 vp = NULL;
1242 break;
1243 }
1244 }
1245 if ( (cnp->cn_flags & ISLASTCN) )
1246 break;
1247
1248 if (vp->v_type != VDIR) {
1249 if (vp->v_type != VLNK)
1250 vp = NULL;
1251 break;
1252 }
1253
1254 if ( (mp = vp->v_mountedhere) && ((cnp->cn_flags & NOCROSSMOUNT) == 0)) {
1255
1256 if (mp->mnt_realrootvp == NULLVP || mp->mnt_generation != mount_generation ||
1257 mp->mnt_realrootvp_vid != mp->mnt_realrootvp->v_id)
1258 break;
1259 vp = mp->mnt_realrootvp;
1260 }
1261
1262 #if CONFIG_TRIGGERS
1263 /*
1264 * After traversing all mountpoints stacked here, if we have a
1265 * trigger in hand, resolve it. Note that we don't need to
1266 * leave the fast path if the mount has already happened.
1267 */
1268 if ((vp->v_resolve != NULL) &&
1269 (vp->v_resolve->vr_resolve_func != NULL)) {
1270 break;
1271 }
1272 #endif /* CONFIG_TRIGGERS */
1273
1274
1275 dp = vp;
1276 vp = NULLVP;
1277
1278 cnp->cn_nameptr = ndp->ni_next + 1;
1279 ndp->ni_pathlen--;
1280 while (*cnp->cn_nameptr == '/') {
1281 cnp->cn_nameptr++;
1282 ndp->ni_pathlen--;
1283 }
1284 }
1285 if (vp != NULLVP)
1286 vvid = vp->v_id;
1287 vid = dp->v_id;
1288
1289 NAME_CACHE_UNLOCK();
1290
1291 if ((vp != NULLVP) && (vp->v_type != VLNK) &&
1292 ((cnp->cn_flags & (ISLASTCN | LOCKPARENT | WANTPARENT | SAVESTART)) == ISLASTCN)) {
1293 /*
1294 * if we've got a child and it's the last component, and
1295 * the lookup doesn't need to return the parent then we
1296 * can skip grabbing an iocount on the parent, since all
1297 * we're going to do with it is a vnode_put just before
1298 * we return from 'lookup'. If it's a symbolic link,
1299 * we need the parent in case the link happens to be
1300 * a relative pathname.
1301 */
1302 tdp = dp;
1303 dp = NULLVP;
1304 } else {
1305 need_dp:
1306 /*
1307 * return the last directory we looked at
1308 * with an io reference held. If it was the one passed
1309 * in as a result of the last iteration of VNOP_LOOKUP,
1310 * it should already hold an io ref. No need to increase ref.
1311 */
1312 if (last_dp != dp){
1313
1314 if (dp == ndp->ni_usedvp) {
1315 /*
1316 * if this vnode matches the one passed in via USEDVP
1317 * than this context already holds an io_count... just
1318 * use vnode_get to get an extra ref for lookup to play
1319 * with... can't use the getwithvid variant here because
1320 * it will block behind a vnode_drain which would result
1321 * in a deadlock (since we already own an io_count that the
1322 * vnode_drain is waiting on)... vnode_get grabs the io_count
1323 * immediately w/o waiting... it always succeeds
1324 */
1325 vnode_get(dp);
1326 } else if ((error = vnode_getwithvid_drainok(dp, vid))) {
1327 /*
1328 * failure indicates the vnode
1329 * changed identity or is being
1330 * TERMINATED... in either case
1331 * punt this lookup.
1332 *
1333 * don't necessarily return ENOENT, though, because
1334 * we really want to go back to disk and make sure it's
1335 * there or not if someone else is changing this
1336 * vnode. That being said, the one case where we do want
1337 * to return ENOENT is when the vnode's mount point is
1338 * in the process of unmounting and we might cause a deadlock
1339 * in our attempt to take an iocount. An ENODEV error return
1340 * is from vnode_get* is an indication this but we change that
1341 * ENOENT for upper layers.
1342 */
1343 if (error == ENODEV) {
1344 error = ENOENT;
1345 } else {
1346 error = ERECYCLE;
1347 }
1348 goto errorout;
1349 }
1350 }
1351 }
1352 if (vp != NULLVP) {
1353 if ( (vnode_getwithvid_drainok(vp, vvid)) ) {
1354 vp = NULLVP;
1355
1356 /*
1357 * can't get reference on the vp we'd like
1358 * to return... if we didn't grab a reference
1359 * on the directory (due to fast path bypass),
1360 * then we need to do it now... we can't return
1361 * with both ni_dvp and ni_vp NULL, and no
1362 * error condition
1363 */
1364 if (dp == NULLVP) {
1365 dp = tdp;
1366 goto need_dp;
1367 }
1368 }
1369 }
1370
1371 ndp->ni_dvp = dp;
1372 ndp->ni_vp = vp;
1373
1374 #if CONFIG_TRIGGERS
1375 trigger_vp = vp ? vp : dp;
1376 if ((error == 0) && (trigger_vp != NULLVP) && vnode_isdir(trigger_vp)) {
1377 error = vnode_trigger_resolve(trigger_vp, ndp, ctx);
1378 if (error) {
1379 if (vp)
1380 vnode_put(vp);
1381 if (dp)
1382 vnode_put(dp);
1383 goto errorout;
1384 }
1385 }
1386 #endif /* CONFIG_TRIGGERS */
1387
1388 errorout:
1389 /*
1390 * If we came into cache_lookup_path after an iteration of the lookup loop that
1391 * resulted in a call to VNOP_LOOKUP, then VNOP_LOOKUP returned a vnode with a io ref
1392 * on it. It is now the job of cache_lookup_path to drop the ref on this vnode
1393 * when it is no longer needed. If we get to this point, and last_dp is not NULL
1394 * and it is ALSO not the dvp we want to return to caller of this function, it MUST be
1395 * the case that we got to a subsequent path component and this previous vnode is
1396 * no longer needed. We can then drop the io ref on it.
1397 */
1398 if ((last_dp != NULLVP) && (last_dp != ndp->ni_dvp)){
1399 vnode_put(last_dp);
1400 }
1401
1402 //initialized to 0, should be the same if no error cases occurred.
1403 return error;
1404 }
1405
1406
1407 static vnode_t
1408 cache_lookup_locked(vnode_t dvp, struct componentname *cnp)
1409 {
1410 struct namecache *ncp;
1411 struct nchashhead *ncpp;
1412 long namelen = cnp->cn_namelen;
1413 unsigned int hashval = cnp->cn_hash;
1414
1415 if (nc_disabled) {
1416 return NULL;
1417 }
1418
1419 ncpp = NCHHASH(dvp, cnp->cn_hash);
1420 LIST_FOREACH(ncp, ncpp, nc_hash) {
1421 if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
1422 if (memcmp(ncp->nc_name, cnp->cn_nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
1423 break;
1424 }
1425 }
1426 if (ncp == 0) {
1427 /*
1428 * We failed to find an entry
1429 */
1430 NCHSTAT(ncs_miss);
1431 return (NULL);
1432 }
1433 NCHSTAT(ncs_goodhits);
1434
1435 return (ncp->nc_vp);
1436 }
1437
1438
1439 unsigned int hash_string(const char *cp, int len);
1440 //
1441 // Have to take a len argument because we may only need to
1442 // hash part of a componentname.
1443 //
1444 unsigned int
1445 hash_string(const char *cp, int len)
1446 {
1447 unsigned hash = 0;
1448
1449 if (len) {
1450 while (len--) {
1451 hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
1452 }
1453 } else {
1454 while (*cp != '\0') {
1455 hash = crc32tab[((hash >> 24) ^ (unsigned char)*cp++)] ^ hash << 8;
1456 }
1457 }
1458 /*
1459 * the crc generator can legitimately generate
1460 * a 0... however, 0 for us means that we
1461 * haven't computed a hash, so use 1 instead
1462 */
1463 if (hash == 0)
1464 hash = 1;
1465 return hash;
1466 }
1467
1468
1469 /*
1470 * Lookup an entry in the cache
1471 *
1472 * We don't do this if the segment name is long, simply so the cache
1473 * can avoid holding long names (which would either waste space, or
1474 * add greatly to the complexity).
1475 *
1476 * Lookup is called with dvp pointing to the directory to search,
1477 * cnp pointing to the name of the entry being sought. If the lookup
1478 * succeeds, the vnode is returned in *vpp, and a status of -1 is
1479 * returned. If the lookup determines that the name does not exist
1480 * (negative cacheing), a status of ENOENT is returned. If the lookup
1481 * fails, a status of zero is returned.
1482 */
1483
1484 int
1485 cache_lookup(struct vnode *dvp, struct vnode **vpp, struct componentname *cnp)
1486 {
1487 struct namecache *ncp;
1488 struct nchashhead *ncpp;
1489 long namelen = cnp->cn_namelen;
1490 unsigned int hashval;
1491 boolean_t have_exclusive = FALSE;
1492 uint32_t vid;
1493 vnode_t vp;
1494
1495 if (cnp->cn_hash == 0)
1496 cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
1497 hashval = cnp->cn_hash;
1498
1499 if (nc_disabled) {
1500 return 0;
1501 }
1502
1503 NAME_CACHE_LOCK_SHARED();
1504
1505 relook:
1506 ncpp = NCHHASH(dvp, cnp->cn_hash);
1507 LIST_FOREACH(ncp, ncpp, nc_hash) {
1508 if ((ncp->nc_dvp == dvp) && (ncp->nc_hashval == hashval)) {
1509 if (memcmp(ncp->nc_name, cnp->cn_nameptr, namelen) == 0 && ncp->nc_name[namelen] == 0)
1510 break;
1511 }
1512 }
1513 /* We failed to find an entry */
1514 if (ncp == 0) {
1515 NCHSTAT(ncs_miss);
1516 NAME_CACHE_UNLOCK();
1517 return (0);
1518 }
1519
1520 /* We don't want to have an entry, so dump it */
1521 if ((cnp->cn_flags & MAKEENTRY) == 0) {
1522 if (have_exclusive == TRUE) {
1523 NCHSTAT(ncs_badhits);
1524 cache_delete(ncp, 1);
1525 NAME_CACHE_UNLOCK();
1526 return (0);
1527 }
1528 NAME_CACHE_UNLOCK();
1529 NAME_CACHE_LOCK();
1530 have_exclusive = TRUE;
1531 goto relook;
1532 }
1533 vp = ncp->nc_vp;
1534
1535 /* We found a "positive" match, return the vnode */
1536 if (vp) {
1537 NCHSTAT(ncs_goodhits);
1538
1539 vid = vp->v_id;
1540 NAME_CACHE_UNLOCK();
1541
1542 if (vnode_getwithvid(vp, vid)) {
1543 #if COLLECT_STATS
1544 NAME_CACHE_LOCK();
1545 NCHSTAT(ncs_badvid);
1546 NAME_CACHE_UNLOCK();
1547 #endif
1548 return (0);
1549 }
1550 *vpp = vp;
1551 return (-1);
1552 }
1553
1554 /* We found a negative match, and want to create it, so purge */
1555 if (cnp->cn_nameiop == CREATE || cnp->cn_nameiop == RENAME) {
1556 if (have_exclusive == TRUE) {
1557 NCHSTAT(ncs_badhits);
1558 cache_delete(ncp, 1);
1559 NAME_CACHE_UNLOCK();
1560 return (0);
1561 }
1562 NAME_CACHE_UNLOCK();
1563 NAME_CACHE_LOCK();
1564 have_exclusive = TRUE;
1565 goto relook;
1566 }
1567
1568 /*
1569 * We found a "negative" match, ENOENT notifies client of this match.
1570 */
1571 NCHSTAT(ncs_neghits);
1572
1573 NAME_CACHE_UNLOCK();
1574 return (ENOENT);
1575 }
1576
1577 const char *
1578 cache_enter_create(vnode_t dvp, vnode_t vp, struct componentname *cnp)
1579 {
1580 const char *strname;
1581
1582 if (cnp->cn_hash == 0)
1583 cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
1584
1585 /*
1586 * grab 2 references on the string entered
1587 * one for the cache_enter_locked to consume
1588 * and the second to be consumed by v_name (vnode_create call point)
1589 */
1590 strname = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, TRUE, 0);
1591
1592 NAME_CACHE_LOCK();
1593
1594 cache_enter_locked(dvp, vp, cnp, strname);
1595
1596 NAME_CACHE_UNLOCK();
1597
1598 return (strname);
1599 }
1600
1601
1602 /*
1603 * Add an entry to the cache...
1604 * but first check to see if the directory
1605 * that this entry is to be associated with has
1606 * had any cache_purges applied since we took
1607 * our identity snapshot... this check needs to
1608 * be done behind the name cache lock
1609 */
1610 void
1611 cache_enter_with_gen(struct vnode *dvp, struct vnode *vp, struct componentname *cnp, int gen)
1612 {
1613
1614 if (cnp->cn_hash == 0)
1615 cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
1616
1617 NAME_CACHE_LOCK();
1618
1619 if (dvp->v_nc_generation == gen)
1620 (void)cache_enter_locked(dvp, vp, cnp, NULL);
1621
1622 NAME_CACHE_UNLOCK();
1623 }
1624
1625
1626 /*
1627 * Add an entry to the cache.
1628 */
1629 void
1630 cache_enter(struct vnode *dvp, struct vnode *vp, struct componentname *cnp)
1631 {
1632 const char *strname;
1633
1634 if (cnp->cn_hash == 0)
1635 cnp->cn_hash = hash_string(cnp->cn_nameptr, cnp->cn_namelen);
1636
1637 /*
1638 * grab 1 reference on the string entered
1639 * for the cache_enter_locked to consume
1640 */
1641 strname = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, FALSE, 0);
1642
1643 NAME_CACHE_LOCK();
1644
1645 cache_enter_locked(dvp, vp, cnp, strname);
1646
1647 NAME_CACHE_UNLOCK();
1648 }
1649
1650
1651 static void
1652 cache_enter_locked(struct vnode *dvp, struct vnode *vp, struct componentname *cnp, const char *strname)
1653 {
1654 struct namecache *ncp, *negp;
1655 struct nchashhead *ncpp;
1656
1657 if (nc_disabled)
1658 return;
1659
1660 /*
1661 * if the entry is for -ve caching vp is null
1662 */
1663 if ((vp != NULLVP) && (LIST_FIRST(&vp->v_nclinks))) {
1664 /*
1665 * someone beat us to the punch..
1666 * this vnode is already in the cache
1667 */
1668 if (strname != NULL)
1669 vfs_removename(strname);
1670 return;
1671 }
1672 /*
1673 * We allocate a new entry if we are less than the maximum
1674 * allowed and the one at the front of the list is in use.
1675 * Otherwise we use the one at the front of the list.
1676 */
1677 if (numcache < desiredNodes &&
1678 ((ncp = nchead.tqh_first) == NULL ||
1679 ncp->nc_hash.le_prev != 0)) {
1680 /*
1681 * Allocate one more entry
1682 */
1683 ncp = (struct namecache *)_MALLOC_ZONE(sizeof(*ncp), M_CACHE, M_WAITOK);
1684 numcache++;
1685 } else {
1686 /*
1687 * reuse an old entry
1688 */
1689 ncp = TAILQ_FIRST(&nchead);
1690 TAILQ_REMOVE(&nchead, ncp, nc_entry);
1691
1692 if (ncp->nc_hash.le_prev != 0) {
1693 /*
1694 * still in use... we need to
1695 * delete it before re-using it
1696 */
1697 NCHSTAT(ncs_stolen);
1698 cache_delete(ncp, 0);
1699 }
1700 }
1701 NCHSTAT(ncs_enters);
1702
1703 /*
1704 * Fill in cache info, if vp is NULL this is a "negative" cache entry.
1705 */
1706 ncp->nc_vp = vp;
1707 ncp->nc_dvp = dvp;
1708 ncp->nc_hashval = cnp->cn_hash;
1709
1710 if (strname == NULL)
1711 ncp->nc_name = add_name_internal(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, FALSE, 0);
1712 else
1713 ncp->nc_name = strname;
1714 /*
1715 * make us the newest entry in the cache
1716 * i.e. we'll be the last to be stolen
1717 */
1718 TAILQ_INSERT_TAIL(&nchead, ncp, nc_entry);
1719
1720 ncpp = NCHHASH(dvp, cnp->cn_hash);
1721 #if DIAGNOSTIC
1722 {
1723 struct namecache *p;
1724
1725 for (p = ncpp->lh_first; p != 0; p = p->nc_hash.le_next)
1726 if (p == ncp)
1727 panic("cache_enter: duplicate");
1728 }
1729 #endif
1730 /*
1731 * make us available to be found via lookup
1732 */
1733 LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
1734
1735 if (vp) {
1736 /*
1737 * add to the list of name cache entries
1738 * that point at vp
1739 */
1740 LIST_INSERT_HEAD(&vp->v_nclinks, ncp, nc_un.nc_link);
1741 } else {
1742 /*
1743 * this is a negative cache entry (vp == NULL)
1744 * stick it on the negative cache list.
1745 */
1746 TAILQ_INSERT_TAIL(&neghead, ncp, nc_un.nc_negentry);
1747
1748 ncs_negtotal++;
1749
1750 if (ncs_negtotal > desiredNegNodes) {
1751 /*
1752 * if we've reached our desired limit
1753 * of negative cache entries, delete
1754 * the oldest
1755 */
1756 negp = TAILQ_FIRST(&neghead);
1757 cache_delete(negp, 1);
1758 }
1759 }
1760 /*
1761 * add us to the list of name cache entries that
1762 * are children of dvp
1763 */
1764 LIST_INSERT_HEAD(&dvp->v_ncchildren, ncp, nc_child);
1765 }
1766
1767
1768 /*
1769 * Initialize CRC-32 remainder table.
1770 */
1771 static void init_crc32(void)
1772 {
1773 /*
1774 * the CRC-32 generator polynomial is:
1775 * x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^10
1776 * + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
1777 */
1778 unsigned int crc32_polynomial = 0x04c11db7;
1779 unsigned int i,j;
1780
1781 /*
1782 * pre-calculate the CRC-32 remainder for each possible octet encoding
1783 */
1784 for (i = 0; i < 256; i++) {
1785 unsigned int crc_rem = i << 24;
1786
1787 for (j = 0; j < 8; j++) {
1788 if (crc_rem & 0x80000000)
1789 crc_rem = (crc_rem << 1) ^ crc32_polynomial;
1790 else
1791 crc_rem = (crc_rem << 1);
1792 }
1793 crc32tab[i] = crc_rem;
1794 }
1795 }
1796
1797
1798 /*
1799 * Name cache initialization, from vfs_init() when we are booting
1800 */
1801 void
1802 nchinit(void)
1803 {
1804 int i;
1805
1806 desiredNegNodes = (desiredvnodes / 10);
1807 desiredNodes = desiredvnodes + desiredNegNodes;
1808
1809 TAILQ_INIT(&nchead);
1810 TAILQ_INIT(&neghead);
1811
1812 init_crc32();
1813
1814 nchashtbl = hashinit(MAX(CONFIG_NC_HASH, (2 *desiredNodes)), M_CACHE, &nchash);
1815 nchashmask = nchash;
1816 nchash++;
1817
1818 init_string_table();
1819
1820 /* Allocate name cache lock group attribute and group */
1821 namecache_lck_grp_attr= lck_grp_attr_alloc_init();
1822
1823 namecache_lck_grp = lck_grp_alloc_init("Name Cache", namecache_lck_grp_attr);
1824
1825 /* Allocate name cache lock attribute */
1826 namecache_lck_attr = lck_attr_alloc_init();
1827
1828 /* Allocate name cache lock */
1829 namecache_rw_lock = lck_rw_alloc_init(namecache_lck_grp, namecache_lck_attr);
1830
1831
1832 /* Allocate string cache lock group attribute and group */
1833 strcache_lck_grp_attr= lck_grp_attr_alloc_init();
1834
1835 strcache_lck_grp = lck_grp_alloc_init("String Cache", strcache_lck_grp_attr);
1836
1837 /* Allocate string cache lock attribute */
1838 strcache_lck_attr = lck_attr_alloc_init();
1839
1840 /* Allocate string cache lock */
1841 strtable_rw_lock = lck_rw_alloc_init(strcache_lck_grp, strcache_lck_attr);
1842
1843 for (i = 0; i < NUM_STRCACHE_LOCKS; i++)
1844 lck_mtx_init(&strcache_mtx_locks[i], strcache_lck_grp, strcache_lck_attr);
1845 }
1846
1847 void
1848 name_cache_lock_shared(void)
1849 {
1850 lck_rw_lock_shared(namecache_rw_lock);
1851 }
1852
1853 void
1854 name_cache_lock(void)
1855 {
1856 lck_rw_lock_exclusive(namecache_rw_lock);
1857 }
1858
1859 void
1860 name_cache_unlock(void)
1861 {
1862 lck_rw_done(namecache_rw_lock);
1863 }
1864
1865
1866 int
1867 resize_namecache(u_int newsize)
1868 {
1869 struct nchashhead *new_table;
1870 struct nchashhead *old_table;
1871 struct nchashhead *old_head, *head;
1872 struct namecache *entry, *next;
1873 uint32_t i, hashval;
1874 int dNodes, dNegNodes;
1875 u_long new_size, old_size;
1876
1877 dNegNodes = (newsize / 10);
1878 dNodes = newsize + dNegNodes;
1879
1880 // we don't support shrinking yet
1881 if (dNodes <= desiredNodes) {
1882 return 0;
1883 }
1884 new_table = hashinit(2 * dNodes, M_CACHE, &nchashmask);
1885 new_size = nchashmask + 1;
1886
1887 if (new_table == NULL) {
1888 return ENOMEM;
1889 }
1890
1891 NAME_CACHE_LOCK();
1892 // do the switch!
1893 old_table = nchashtbl;
1894 nchashtbl = new_table;
1895 old_size = nchash;
1896 nchash = new_size;
1897
1898 // walk the old table and insert all the entries into
1899 // the new table
1900 //
1901 for(i=0; i < old_size; i++) {
1902 old_head = &old_table[i];
1903 for (entry=old_head->lh_first; entry != NULL; entry=next) {
1904 //
1905 // XXXdbg - Beware: this assumes that hash_string() does
1906 // the same thing as what happens in
1907 // lookup() over in vfs_lookup.c
1908 hashval = hash_string(entry->nc_name, 0);
1909 entry->nc_hashval = hashval;
1910 head = NCHHASH(entry->nc_dvp, hashval);
1911
1912 next = entry->nc_hash.le_next;
1913 LIST_INSERT_HEAD(head, entry, nc_hash);
1914 }
1915 }
1916 desiredNodes = dNodes;
1917 desiredNegNodes = dNegNodes;
1918
1919 NAME_CACHE_UNLOCK();
1920 FREE(old_table, M_CACHE);
1921
1922 return 0;
1923 }
1924
1925 static void
1926 cache_delete(struct namecache *ncp, int age_entry)
1927 {
1928 NCHSTAT(ncs_deletes);
1929
1930 if (ncp->nc_vp) {
1931 LIST_REMOVE(ncp, nc_un.nc_link);
1932 } else {
1933 TAILQ_REMOVE(&neghead, ncp, nc_un.nc_negentry);
1934 ncs_negtotal--;
1935 }
1936 LIST_REMOVE(ncp, nc_child);
1937
1938 LIST_REMOVE(ncp, nc_hash);
1939 /*
1940 * this field is used to indicate
1941 * that the entry is in use and
1942 * must be deleted before it can
1943 * be reused...
1944 */
1945 ncp->nc_hash.le_prev = NULL;
1946
1947 if (age_entry) {
1948 /*
1949 * make it the next one available
1950 * for cache_enter's use
1951 */
1952 TAILQ_REMOVE(&nchead, ncp, nc_entry);
1953 TAILQ_INSERT_HEAD(&nchead, ncp, nc_entry);
1954 }
1955 vfs_removename(ncp->nc_name);
1956 ncp->nc_name = NULL;
1957 }
1958
1959
1960 /*
1961 * purge the entry associated with the
1962 * specified vnode from the name cache
1963 */
1964 void
1965 cache_purge(vnode_t vp)
1966 {
1967 struct namecache *ncp;
1968 kauth_cred_t tcred = NULL;
1969
1970 if ((LIST_FIRST(&vp->v_nclinks) == NULL) &&
1971 (LIST_FIRST(&vp->v_ncchildren) == NULL) &&
1972 (vp->v_cred == NOCRED) &&
1973 (vp->v_parent == NULLVP))
1974 return;
1975
1976 NAME_CACHE_LOCK();
1977
1978 if (vp->v_parent)
1979 vp->v_parent->v_nc_generation++;
1980
1981 while ( (ncp = LIST_FIRST(&vp->v_nclinks)) )
1982 cache_delete(ncp, 1);
1983
1984 while ( (ncp = LIST_FIRST(&vp->v_ncchildren)) )
1985 cache_delete(ncp, 1);
1986
1987 /*
1988 * Use a temp variable to avoid kauth_cred_unref() while NAME_CACHE_LOCK is held
1989 */
1990 tcred = vp->v_cred;
1991 vp->v_cred = NOCRED;
1992 vp->v_authorized_actions = 0;
1993
1994 NAME_CACHE_UNLOCK();
1995
1996 if (IS_VALID_CRED(tcred))
1997 kauth_cred_unref(&tcred);
1998 }
1999
2000 /*
2001 * Purge all negative cache entries that are children of the
2002 * given vnode. A case-insensitive file system (or any file
2003 * system that has multiple equivalent names for the same
2004 * directory entry) can use this when creating or renaming
2005 * to remove negative entries that may no longer apply.
2006 */
2007 void
2008 cache_purge_negatives(vnode_t vp)
2009 {
2010 struct namecache *ncp, *next_ncp;
2011
2012 NAME_CACHE_LOCK();
2013
2014 LIST_FOREACH_SAFE(ncp, &vp->v_ncchildren, nc_child, next_ncp)
2015 if (ncp->nc_vp == NULL)
2016 cache_delete(ncp , 1);
2017
2018 NAME_CACHE_UNLOCK();
2019 }
2020
2021 /*
2022 * Flush all entries referencing a particular filesystem.
2023 *
2024 * Since we need to check it anyway, we will flush all the invalid
2025 * entries at the same time.
2026 */
2027 void
2028 cache_purgevfs(struct mount *mp)
2029 {
2030 struct nchashhead *ncpp;
2031 struct namecache *ncp;
2032
2033 NAME_CACHE_LOCK();
2034 /* Scan hash tables for applicable entries */
2035 for (ncpp = &nchashtbl[nchash - 1]; ncpp >= nchashtbl; ncpp--) {
2036 restart:
2037 for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
2038 if (ncp->nc_dvp->v_mount == mp) {
2039 cache_delete(ncp, 0);
2040 goto restart;
2041 }
2042 }
2043 }
2044 NAME_CACHE_UNLOCK();
2045 }
2046
2047
2048
2049 //
2050 // String ref routines
2051 //
2052 static LIST_HEAD(stringhead, string_t) *string_ref_table;
2053 static u_long string_table_mask;
2054 static uint32_t filled_buckets=0;
2055
2056
2057 typedef struct string_t {
2058 LIST_ENTRY(string_t) hash_chain;
2059 const char *str;
2060 uint32_t refcount;
2061 } string_t;
2062
2063
2064 static void
2065 resize_string_ref_table(void)
2066 {
2067 struct stringhead *new_table;
2068 struct stringhead *old_table;
2069 struct stringhead *old_head, *head;
2070 string_t *entry, *next;
2071 uint32_t i, hashval;
2072 u_long new_mask, old_mask;
2073
2074 /*
2075 * need to hold the table lock exclusively
2076 * in order to grow the table... need to recheck
2077 * the need to resize again after we've taken
2078 * the lock exclusively in case some other thread
2079 * beat us to the punch
2080 */
2081 lck_rw_lock_exclusive(strtable_rw_lock);
2082
2083 if (4 * filled_buckets < ((string_table_mask + 1) * 3)) {
2084 lck_rw_done(strtable_rw_lock);
2085 return;
2086 }
2087 new_table = hashinit((string_table_mask + 1) * 2, M_CACHE, &new_mask);
2088
2089 if (new_table == NULL) {
2090 printf("failed to resize the hash table.\n");
2091 lck_rw_done(strtable_rw_lock);
2092 return;
2093 }
2094
2095 // do the switch!
2096 old_table = string_ref_table;
2097 string_ref_table = new_table;
2098 old_mask = string_table_mask;
2099 string_table_mask = new_mask;
2100 filled_buckets = 0;
2101
2102 // walk the old table and insert all the entries into
2103 // the new table
2104 //
2105 for (i = 0; i <= old_mask; i++) {
2106 old_head = &old_table[i];
2107 for (entry = old_head->lh_first; entry != NULL; entry = next) {
2108 hashval = hash_string((const char *)entry->str, 0);
2109 head = &string_ref_table[hashval & string_table_mask];
2110 if (head->lh_first == NULL) {
2111 filled_buckets++;
2112 }
2113 next = entry->hash_chain.le_next;
2114 LIST_INSERT_HEAD(head, entry, hash_chain);
2115 }
2116 }
2117 lck_rw_done(strtable_rw_lock);
2118
2119 FREE(old_table, M_CACHE);
2120 }
2121
2122
2123 static void
2124 init_string_table(void)
2125 {
2126 string_ref_table = hashinit(CONFIG_VFS_NAMES, M_CACHE, &string_table_mask);
2127 }
2128
2129
2130 const char *
2131 vfs_addname(const char *name, uint32_t len, u_int hashval, u_int flags)
2132 {
2133 return (add_name_internal(name, len, hashval, FALSE, flags));
2134 }
2135
2136
2137 static const char *
2138 add_name_internal(const char *name, uint32_t len, u_int hashval, boolean_t need_extra_ref, __unused u_int flags)
2139 {
2140 struct stringhead *head;
2141 string_t *entry;
2142 uint32_t chain_len = 0;
2143 uint32_t hash_index;
2144 uint32_t lock_index;
2145 char *ptr;
2146
2147 /*
2148 * if the length already accounts for the null-byte, then
2149 * subtract one so later on we don't index past the end
2150 * of the string.
2151 */
2152 if (len > 0 && name[len-1] == '\0') {
2153 len--;
2154 }
2155 if (hashval == 0) {
2156 hashval = hash_string(name, len);
2157 }
2158
2159 /*
2160 * take this lock 'shared' to keep the hash stable
2161 * if someone else decides to grow the pool they
2162 * will take this lock exclusively
2163 */
2164 lck_rw_lock_shared(strtable_rw_lock);
2165
2166 /*
2167 * If the table gets more than 3/4 full, resize it
2168 */
2169 if (4 * filled_buckets >= ((string_table_mask + 1) * 3)) {
2170 lck_rw_done(strtable_rw_lock);
2171
2172 resize_string_ref_table();
2173
2174 lck_rw_lock_shared(strtable_rw_lock);
2175 }
2176 hash_index = hashval & string_table_mask;
2177 lock_index = hash_index % NUM_STRCACHE_LOCKS;
2178
2179 head = &string_ref_table[hash_index];
2180
2181 lck_mtx_lock_spin(&strcache_mtx_locks[lock_index]);
2182
2183 for (entry = head->lh_first; entry != NULL; chain_len++, entry = entry->hash_chain.le_next) {
2184 if (memcmp(entry->str, name, len) == 0 && entry->str[len] == 0) {
2185 entry->refcount++;
2186 break;
2187 }
2188 }
2189 if (entry == NULL) {
2190 lck_mtx_convert_spin(&strcache_mtx_locks[lock_index]);
2191 /*
2192 * it wasn't already there so add it.
2193 */
2194 MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
2195
2196 if (head->lh_first == NULL) {
2197 OSAddAtomic(1, &filled_buckets);
2198 }
2199 ptr = (char *)((char *)entry + sizeof(string_t));
2200 strncpy(ptr, name, len);
2201 ptr[len] = '\0';
2202 entry->str = ptr;
2203 entry->refcount = 1;
2204 LIST_INSERT_HEAD(head, entry, hash_chain);
2205 }
2206 if (need_extra_ref == TRUE)
2207 entry->refcount++;
2208
2209 lck_mtx_unlock(&strcache_mtx_locks[lock_index]);
2210 lck_rw_done(strtable_rw_lock);
2211
2212 return (const char *)entry->str;
2213 }
2214
2215
2216 int
2217 vfs_removename(const char *nameref)
2218 {
2219 struct stringhead *head;
2220 string_t *entry;
2221 uint32_t hashval;
2222 uint32_t hash_index;
2223 uint32_t lock_index;
2224 int retval = ENOENT;
2225
2226 hashval = hash_string(nameref, 0);
2227
2228 /*
2229 * take this lock 'shared' to keep the hash stable
2230 * if someone else decides to grow the pool they
2231 * will take this lock exclusively
2232 */
2233 lck_rw_lock_shared(strtable_rw_lock);
2234 /*
2235 * must compute the head behind the table lock
2236 * since the size and location of the table
2237 * can change on the fly
2238 */
2239 hash_index = hashval & string_table_mask;
2240 lock_index = hash_index % NUM_STRCACHE_LOCKS;
2241
2242 head = &string_ref_table[hash_index];
2243
2244 lck_mtx_lock_spin(&strcache_mtx_locks[lock_index]);
2245
2246 for (entry = head->lh_first; entry != NULL; entry = entry->hash_chain.le_next) {
2247 if (entry->str == nameref) {
2248 entry->refcount--;
2249
2250 if (entry->refcount == 0) {
2251 LIST_REMOVE(entry, hash_chain);
2252
2253 if (head->lh_first == NULL) {
2254 OSAddAtomic(-1, &filled_buckets);
2255 }
2256 } else {
2257 entry = NULL;
2258 }
2259 retval = 0;
2260 break;
2261 }
2262 }
2263 lck_mtx_unlock(&strcache_mtx_locks[lock_index]);
2264 lck_rw_done(strtable_rw_lock);
2265
2266 if (entry != NULL)
2267 FREE(entry, M_TEMP);
2268
2269 return retval;
2270 }
2271
2272
2273 #ifdef DUMP_STRING_TABLE
2274 void
2275 dump_string_table(void)
2276 {
2277 struct stringhead *head;
2278 string_t *entry;
2279 u_long i;
2280
2281 lck_rw_lock_shared(strtable_rw_lock);
2282
2283 for (i = 0; i <= string_table_mask; i++) {
2284 head = &string_ref_table[i];
2285 for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
2286 printf("%6d - %s\n", entry->refcount, entry->str);
2287 }
2288 }
2289 lck_rw_done(strtable_rw_lock);
2290 }
2291 #endif /* DUMP_STRING_TABLE */
mirror of XNU