]>
git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfs_chash.c
2 * Copyright (c) 2002-2012 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
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.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
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.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
30 * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
31 * The Regents of the University of California. All rights reserved.
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
36 * 1. Redistributions of source code must retain the above copyright
37 * notice, this list of conditions and the following disclaimer.
38 * 2. Redistributions in binary form must reproduce the above copyright
39 * notice, this list of conditions and the following disclaimer in the
40 * documentation and/or other materials provided with the distribution.
41 * 3. All advertising materials mentioning features or use of this software
42 * must display the following acknowledgement:
43 * This product includes software developed by the University of
44 * California, Berkeley and its contributors.
45 * 4. Neither the name of the University nor the names of its contributors
46 * may be used to endorse or promote products derived from this software
47 * without specific prior written permission.
49 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
65 #include <sys/param.h>
66 #include <sys/systm.h>
67 #include <sys/vnode.h>
68 #include <sys/kernel.h>
69 #include <sys/malloc.h>
71 #include <sys/queue.h>
74 #include "hfs.h" /* XXX bringup */
75 #include "hfs_cnode.h"
77 extern lck_attr_t
* hfs_lock_attr
;
78 extern lck_grp_t
* hfs_mutex_group
;
79 extern lck_grp_t
* hfs_rwlock_group
;
81 lck_grp_t
* chash_lck_grp
;
82 lck_grp_attr_t
* chash_lck_grp_attr
;
83 lck_attr_t
* chash_lck_attr
;
86 #define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])
90 * Initialize cnode hash table.
96 chash_lck_grp_attr
= lck_grp_attr_alloc_init();
97 chash_lck_grp
= lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr
);
98 chash_lck_attr
= lck_attr_alloc_init();
101 static void hfs_chash_lock(struct hfsmount
*hfsmp
)
103 lck_mtx_lock(&hfsmp
->hfs_chash_mutex
);
106 static void hfs_chash_lock_spin(struct hfsmount
*hfsmp
)
108 lck_mtx_lock_spin(&hfsmp
->hfs_chash_mutex
);
111 static void hfs_chash_lock_convert (__unused
struct hfsmount
*hfsmp
)
113 lck_mtx_convert_spin(&hfsmp
->hfs_chash_mutex
);
116 static void hfs_chash_unlock(struct hfsmount
*hfsmp
)
118 lck_mtx_unlock(&hfsmp
->hfs_chash_mutex
);
123 hfs_chashinit_finish(struct hfsmount
*hfsmp
)
125 lck_mtx_init(&hfsmp
->hfs_chash_mutex
, chash_lck_grp
, chash_lck_attr
);
127 hfsmp
->hfs_cnodehashtbl
= hashinit(desiredvnodes
/ 4, M_HFSMNT
, &hfsmp
->hfs_cnodehash
);
132 hfs_delete_chash(struct hfsmount
*hfsmp
)
134 lck_mtx_destroy(&hfsmp
->hfs_chash_mutex
, chash_lck_grp
);
136 FREE(hfsmp
->hfs_cnodehashtbl
, M_HFSMNT
);
141 * Use the device, inum pair to find the incore cnode.
143 * If it is in core, but locked, wait for it.
146 hfs_chash_getvnode(struct hfsmount
*hfsmp
, ino_t inum
, int wantrsrc
, int skiplock
, int allow_deleted
)
154 * Go through the hash list
155 * If a cnode is in the process of being cleaned out or being
156 * allocated, wait for it to be finished and then try again.
159 hfs_chash_lock_spin(hfsmp
);
161 for (cp
= CNODEHASH(hfsmp
, inum
)->lh_first
; cp
; cp
= cp
->c_hash
.le_next
) {
162 if (cp
->c_fileid
!= inum
)
164 /* Wait if cnode is being created or reclaimed. */
165 if (ISSET(cp
->c_hflag
, H_ALLOC
| H_TRANSIT
| H_ATTACH
)) {
166 SET(cp
->c_hflag
, H_WAITING
);
168 (void) msleep(cp
, &hfsmp
->hfs_chash_mutex
, PDROP
| PINOD
,
169 "hfs_chash_getvnode", 0);
172 /* Obtain the desired vnode. */
173 vp
= wantrsrc
? cp
->c_rsrc_vp
: cp
->c_vp
;
178 hfs_chash_unlock(hfsmp
);
180 if ((error
= vnode_getwithvid(vp
, vid
))) {
182 * If vnode is being reclaimed, or has
183 * already changed identity, no need to wait
187 if (!skiplock
&& hfs_lock(cp
, HFS_EXCLUSIVE_LOCK
, HFS_LOCK_DEFAULT
) != 0) {
193 * Skip cnodes that are not in the name space anymore
194 * we need to check with the cnode lock held because
195 * we may have blocked acquiring the vnode ref or the
196 * lock on the cnode which would allow the node to be
199 if (!allow_deleted
) {
200 if (cp
->c_flag
& (C_NOEXISTS
| C_DELETED
)) {
211 hfs_chash_unlock(hfsmp
);
217 * Use the device, fileid pair to snoop an incore cnode.
219 * A cnode can exists in chash even after it has been
220 * deleted from the catalog, so this function returns
221 * ENOENT if C_NOEXIST is set in the cnode's flag.
225 hfs_chash_snoop(struct hfsmount
*hfsmp
, ino_t inum
, int existence_only
, int (*callout
)(const struct cat_desc
*,
226 const struct cat_attr
*, void *), void * arg
)
232 * Go through the hash list
233 * If a cnode is in the process of being cleaned out or being
234 * allocated, wait for it to be finished and then try again.
236 hfs_chash_lock(hfsmp
);
238 for (cp
= CNODEHASH(hfsmp
, inum
)->lh_first
; cp
; cp
= cp
->c_hash
.le_next
) {
239 if (cp
->c_fileid
!= inum
)
243 * Under normal circumstances, we would want to return ENOENT if a cnode is in
244 * the hash and it is marked C_NOEXISTS or C_DELETED. However, if the CNID
245 * namespace has wrapped around, then we have the possibility of collisions.
246 * In that case, we may use this function to validate whether or not we
247 * should trust the nextCNID value in the hfs mount point.
249 * If we didn't do this, then it would be possible for a cnode that is no longer backed
250 * by anything on-disk (C_NOEXISTS) to still exist in the hash along with its
251 * vnode. The cat_create routine could then create a new entry in the catalog
252 * re-using that CNID. Then subsequent hfs_getnewvnode calls will repeatedly fail
253 * trying to look it up/validate it because it is marked C_NOEXISTS. So we want
254 * to prevent that from happening as much as possible.
256 if (existence_only
) {
261 /* Skip cnodes that have been removed from the catalog */
262 if (cp
->c_flag
& (C_NOEXISTS
| C_DELETED
)) {
265 /* Skip cnodes being created or reclaimed. */
266 if (!ISSET(cp
->c_hflag
, H_ALLOC
| H_TRANSIT
| H_ATTACH
)) {
267 result
= callout(&cp
->c_desc
, &cp
->c_attr
, arg
);
271 hfs_chash_unlock(hfsmp
);
278 * Use the device, fileid pair to find the incore cnode.
279 * If no cnode if found one is created
281 * If it is in core, but locked, wait for it.
283 * If the cnode is C_DELETED, then return NULL since that
284 * inum is no longer valid for lookups (open-unlinked file).
286 * If the cnode is C_DELETED but also marked C_RENAMED, then that means
287 * the cnode was renamed over and a new entry exists in its place. The caller
288 * should re-drive the lookup to get the newer entry. In that case, we'll still
289 * return NULL for the cnode, but also return GNV_CHASH_RENAMED in the output flags
290 * of this function to indicate the caller that they should re-drive.
293 hfs_chash_getcnode(struct hfsmount
*hfsmp
, ino_t inum
, struct vnode
**vpp
,
294 int wantrsrc
, int skiplock
, int *out_flags
, int *hflags
)
297 struct cnode
*ncp
= NULL
;
302 * Go through the hash list
303 * If a cnode is in the process of being cleaned out or being
304 * allocated, wait for it to be finished and then try again.
307 hfs_chash_lock_spin(hfsmp
);
310 for (cp
= CNODEHASH(hfsmp
, inum
)->lh_first
; cp
; cp
= cp
->c_hash
.le_next
) {
311 if (cp
->c_fileid
!= inum
)
314 * Wait if cnode is being created, attached to or reclaimed.
316 if (ISSET(cp
->c_hflag
, H_ALLOC
| H_ATTACH
| H_TRANSIT
)) {
317 SET(cp
->c_hflag
, H_WAITING
);
319 (void) msleep(cp
, &hfsmp
->hfs_chash_mutex
, PINOD
,
320 "hfs_chash_getcnode", 0);
323 vp
= wantrsrc
? cp
->c_rsrc_vp
: cp
->c_vp
;
326 * The desired vnode isn't there so tag the cnode.
328 SET(cp
->c_hflag
, H_ATTACH
);
331 hfs_chash_unlock(hfsmp
);
335 hfs_chash_unlock(hfsmp
);
337 if (vnode_getwithvid(vp
, vid
))
342 * someone else won the race to create
343 * this cnode and add it to the hash
344 * just dump our allocation
346 FREE_ZONE(ncp
, sizeof(struct cnode
), M_HFSNODE
);
351 hfs_lock(cp
, HFS_EXCLUSIVE_LOCK
, HFS_LOCK_ALLOW_NOEXISTS
);
355 * Skip cnodes that are not in the name space anymore
356 * we need to check with the cnode lock held because
357 * we may have blocked acquiring the vnode ref or the
358 * lock on the cnode which would allow the node to be
361 * Don't return a cnode in this case since the inum
362 * is no longer valid for lookups.
364 if ((cp
->c_flag
& (C_NOEXISTS
| C_DELETED
)) && !wantrsrc
) {
366 if (cp
->c_flag
& C_RENAMED
) {
374 hfs_chash_lock_spin(hfsmp
);
375 CLR(cp
->c_hflag
, H_ATTACH
);
376 *hflags
&= ~H_ATTACH
;
377 if (ISSET(cp
->c_hflag
, H_WAITING
)) {
378 CLR(cp
->c_hflag
, H_WAITING
);
381 hfs_chash_unlock(hfsmp
);
386 *out_flags
= GNV_CHASH_RENAMED
;
394 * Allocate a new cnode
396 if (skiplock
&& !wantrsrc
)
397 panic("%s - should never get here when skiplock is set \n", __FUNCTION__
);
400 hfs_chash_unlock(hfsmp
);
402 MALLOC_ZONE(ncp
, struct cnode
*, sizeof(struct cnode
), M_HFSNODE
, M_WAITOK
);
404 * since we dropped the chash lock,
405 * we need to go back and re-verify
406 * that this node hasn't come into
411 hfs_chash_lock_convert(hfsmp
);
413 bzero(ncp
, sizeof(struct cnode
));
414 SET(ncp
->c_hflag
, H_ALLOC
);
416 ncp
->c_fileid
= inum
;
417 TAILQ_INIT(&ncp
->c_hintlist
); /* make the list empty */
418 TAILQ_INIT(&ncp
->c_originlist
);
420 lck_rw_init(&ncp
->c_rwlock
, hfs_rwlock_group
, hfs_lock_attr
);
422 (void) hfs_lock(ncp
, HFS_EXCLUSIVE_LOCK
, HFS_LOCK_DEFAULT
);
424 /* Insert the new cnode with it's H_ALLOC flag set */
425 LIST_INSERT_HEAD(CNODEHASH(hfsmp
, inum
), ncp
, c_hash
);
426 hfs_chash_unlock(hfsmp
);
435 hfs_chashwakeup(struct hfsmount
*hfsmp
, struct cnode
*cp
, int hflags
)
437 hfs_chash_lock_spin(hfsmp
);
439 CLR(cp
->c_hflag
, hflags
);
441 if (ISSET(cp
->c_hflag
, H_WAITING
)) {
442 CLR(cp
->c_hflag
, H_WAITING
);
445 hfs_chash_unlock(hfsmp
);
450 * Re-hash two cnodes in the hash table.
454 hfs_chash_rehash(struct hfsmount
*hfsmp
, struct cnode
*cp1
, struct cnode
*cp2
)
456 hfs_chash_lock_spin(hfsmp
);
458 LIST_REMOVE(cp1
, c_hash
);
459 LIST_REMOVE(cp2
, c_hash
);
460 LIST_INSERT_HEAD(CNODEHASH(hfsmp
, cp1
->c_fileid
), cp1
, c_hash
);
461 LIST_INSERT_HEAD(CNODEHASH(hfsmp
, cp2
->c_fileid
), cp2
, c_hash
);
463 hfs_chash_unlock(hfsmp
);
468 * Remove a cnode from the hash table.
472 hfs_chashremove(struct hfsmount
*hfsmp
, struct cnode
*cp
)
474 hfs_chash_lock_spin(hfsmp
);
476 /* Check if a vnode is getting attached */
477 if (ISSET(cp
->c_hflag
, H_ATTACH
)) {
478 hfs_chash_unlock(hfsmp
);
481 if (cp
->c_hash
.le_next
|| cp
->c_hash
.le_prev
) {
482 LIST_REMOVE(cp
, c_hash
);
483 cp
->c_hash
.le_next
= NULL
;
484 cp
->c_hash
.le_prev
= NULL
;
486 hfs_chash_unlock(hfsmp
);
492 * Remove a cnode from the hash table and wakeup any waiters.
496 hfs_chash_abort(struct hfsmount
*hfsmp
, struct cnode
*cp
)
498 hfs_chash_lock_spin(hfsmp
);
500 LIST_REMOVE(cp
, c_hash
);
501 cp
->c_hash
.le_next
= NULL
;
502 cp
->c_hash
.le_prev
= NULL
;
504 CLR(cp
->c_hflag
, H_ATTACH
| H_ALLOC
);
505 if (ISSET(cp
->c_hflag
, H_WAITING
)) {
506 CLR(cp
->c_hflag
, H_WAITING
);
509 hfs_chash_unlock(hfsmp
);
514 * mark a cnode as in transition
518 hfs_chash_mark_in_transit(struct hfsmount
*hfsmp
, struct cnode
*cp
)
520 hfs_chash_lock_spin(hfsmp
);
522 SET(cp
->c_hflag
, H_TRANSIT
);
524 hfs_chash_unlock(hfsmp
);
527 /* Search a cnode in the hash. This function does not return cnode which
528 * are getting created, destroyed or in transition. Note that this function
529 * does not acquire the cnode hash mutex, and expects the caller to acquire it.
530 * On success, returns pointer to the cnode found. On failure, returns NULL.
534 hfs_chash_search_cnid(struct hfsmount
*hfsmp
, cnid_t cnid
)
538 for (cp
= CNODEHASH(hfsmp
, cnid
)->lh_first
; cp
; cp
= cp
->c_hash
.le_next
) {
539 if (cp
->c_fileid
== cnid
) {
544 /* If cnode is being created or reclaimed, return error. */
545 if (cp
&& ISSET(cp
->c_hflag
, H_ALLOC
| H_TRANSIT
| H_ATTACH
)) {
552 /* Search a cnode corresponding to given device and ID in the hash. If the
553 * found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not
554 * found, no new cnode is created and error is returned.
557 * -1 : The cnode was not found.
558 * 0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
559 * 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
560 * function had to set that bit.
564 hfs_chash_set_childlinkbit(struct hfsmount
*hfsmp
, cnid_t cnid
)
569 hfs_chash_lock_spin(hfsmp
);
571 cp
= hfs_chash_search_cnid(hfsmp
, cnid
);
573 if (cp
->c_attr
.ca_recflags
& kHFSHasChildLinkMask
) {
576 cp
->c_attr
.ca_recflags
|= kHFSHasChildLinkMask
;
580 hfs_chash_unlock(hfsmp
);