]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfs_chash.c
xnu-2422.115.4.tar.gz
[apple/xnu.git] / bsd / hfs / hfs_chash.c
1 /*
2 * Copyright (c) 2002-2012 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
29 /*
30 * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
31 * The Regents of the University of California. All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
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.
48 *
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
59 * SUCH DAMAGE.
60 *
61 * @(#)hfs_chash.c
62 * derived from @(#)ufs_ihash.c 8.7 (Berkeley) 5/17/95
63 */
64
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>
70 #include <sys/proc.h>
71 #include <sys/queue.h>
72
73
74 #include "hfs.h" /* XXX bringup */
75 #include "hfs_cnode.h"
76
77 extern lck_attr_t * hfs_lock_attr;
78 extern lck_grp_t * hfs_mutex_group;
79 extern lck_grp_t * hfs_rwlock_group;
80
81 lck_grp_t * chash_lck_grp;
82 lck_grp_attr_t * chash_lck_grp_attr;
83 lck_attr_t * chash_lck_attr;
84
85
86 #define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])
87
88
89 /*
90 * Initialize cnode hash table.
91 */
92 __private_extern__
93 void
94 hfs_chashinit()
95 {
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();
99 }
100
101 static void hfs_chash_lock(struct hfsmount *hfsmp)
102 {
103 lck_mtx_lock(&hfsmp->hfs_chash_mutex);
104 }
105
106 static void hfs_chash_lock_spin(struct hfsmount *hfsmp)
107 {
108 lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
109 }
110
111 static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp)
112 {
113 lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex);
114 }
115
116 static void hfs_chash_unlock(struct hfsmount *hfsmp)
117 {
118 lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
119 }
120
121 __private_extern__
122 void
123 hfs_chashinit_finish(struct hfsmount *hfsmp)
124 {
125 lck_mtx_init(&hfsmp->hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
126
127 hfsmp->hfs_cnodehashtbl = hashinit(desiredvnodes / 4, M_HFSMNT, &hfsmp->hfs_cnodehash);
128 }
129
130 __private_extern__
131 void
132 hfs_delete_chash(struct hfsmount *hfsmp)
133 {
134 lck_mtx_destroy(&hfsmp->hfs_chash_mutex, chash_lck_grp);
135
136 FREE(hfsmp->hfs_cnodehashtbl, M_HFSMNT);
137 }
138
139
140 /*
141 * Use the device, inum pair to find the incore cnode.
142 *
143 * If it is in core, but locked, wait for it.
144 */
145 struct vnode *
146 hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock, int allow_deleted)
147 {
148 struct cnode *cp;
149 struct vnode *vp;
150 int error;
151 u_int32_t vid;
152
153 /*
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.
157 */
158 loop:
159 hfs_chash_lock_spin(hfsmp);
160
161 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
162 if (cp->c_fileid != inum)
163 continue;
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);
167
168 (void) msleep(cp, &hfsmp->hfs_chash_mutex, PDROP | PINOD,
169 "hfs_chash_getvnode", 0);
170 goto loop;
171 }
172 /* Obtain the desired vnode. */
173 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
174 if (vp == NULLVP)
175 goto exit;
176
177 vid = vnode_vid(vp);
178 hfs_chash_unlock(hfsmp);
179
180 if ((error = vnode_getwithvid(vp, vid))) {
181 /*
182 * If vnode is being reclaimed, or has
183 * already changed identity, no need to wait
184 */
185 return (NULL);
186 }
187 if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT) != 0) {
188 vnode_put(vp);
189 return (NULL);
190 }
191
192 /*
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
197 * unlinked
198 */
199 if (!allow_deleted) {
200 if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
201 if (!skiplock) {
202 hfs_unlock(cp);
203 }
204 vnode_put(vp);
205 return (NULL);
206 }
207 }
208 return (vp);
209 }
210 exit:
211 hfs_chash_unlock(hfsmp);
212 return (NULL);
213 }
214
215
216 /*
217 * Use the device, fileid pair to snoop an incore cnode.
218 *
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.
222 *
223 */
224 int
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)
227 {
228 struct cnode *cp;
229 int result = ENOENT;
230
231 /*
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.
235 */
236 hfs_chash_lock(hfsmp);
237
238 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
239 if (cp->c_fileid != inum)
240 continue;
241
242 /*
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.
248 *
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.
255 */
256 if (existence_only) {
257 result = 0;
258 break;
259 }
260
261 /* Skip cnodes that have been removed from the catalog */
262 if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
263 break;
264 }
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);
268 }
269 break;
270 }
271 hfs_chash_unlock(hfsmp);
272
273 return (result);
274 }
275
276
277 /*
278 * Use the device, fileid pair to find the incore cnode.
279 * If no cnode if found one is created
280 *
281 * If it is in core, but locked, wait for it.
282 *
283 * If the cnode is C_DELETED, then return NULL since that
284 * inum is no longer valid for lookups (open-unlinked file).
285 *
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.
291 */
292 struct cnode *
293 hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp,
294 int wantrsrc, int skiplock, int *out_flags, int *hflags)
295 {
296 struct cnode *cp;
297 struct cnode *ncp = NULL;
298 vnode_t vp;
299 u_int32_t vid;
300
301 /*
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.
305 */
306 loop:
307 hfs_chash_lock_spin(hfsmp);
308
309 loop_with_lock:
310 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
311 if (cp->c_fileid != inum)
312 continue;
313 /*
314 * Wait if cnode is being created, attached to or reclaimed.
315 */
316 if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) {
317 SET(cp->c_hflag, H_WAITING);
318
319 (void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD,
320 "hfs_chash_getcnode", 0);
321 goto loop_with_lock;
322 }
323 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
324 if (vp == NULL) {
325 /*
326 * The desired vnode isn't there so tag the cnode.
327 */
328 SET(cp->c_hflag, H_ATTACH);
329 *hflags |= H_ATTACH;
330
331 hfs_chash_unlock(hfsmp);
332 } else {
333 vid = vnode_vid(vp);
334
335 hfs_chash_unlock(hfsmp);
336
337 if (vnode_getwithvid(vp, vid))
338 goto loop;
339 }
340 if (ncp) {
341 /*
342 * someone else won the race to create
343 * this cnode and add it to the hash
344 * just dump our allocation
345 */
346 FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE);
347 ncp = NULL;
348 }
349
350 if (!skiplock) {
351 hfs_lock(cp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS);
352 }
353
354 /*
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
359 * unlinked.
360 *
361 * Don't return a cnode in this case since the inum
362 * is no longer valid for lookups.
363 */
364 if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) {
365 int renamed = 0;
366 if (cp->c_flag & C_RENAMED) {
367 renamed = 1;
368 }
369 if (!skiplock)
370 hfs_unlock(cp);
371 if (vp != NULLVP) {
372 vnode_put(vp);
373 } else {
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);
379 wakeup((caddr_t)cp);
380 }
381 hfs_chash_unlock(hfsmp);
382 }
383 vp = NULL;
384 cp = NULL;
385 if (renamed) {
386 *out_flags = GNV_CHASH_RENAMED;
387 }
388 }
389 *vpp = vp;
390 return (cp);
391 }
392
393 /*
394 * Allocate a new cnode
395 */
396 if (skiplock && !wantrsrc)
397 panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
398
399 if (ncp == NULL) {
400 hfs_chash_unlock(hfsmp);
401
402 MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK);
403 /*
404 * since we dropped the chash lock,
405 * we need to go back and re-verify
406 * that this node hasn't come into
407 * existence...
408 */
409 goto loop;
410 }
411 hfs_chash_lock_convert(hfsmp);
412
413 bzero(ncp, sizeof(struct cnode));
414 SET(ncp->c_hflag, H_ALLOC);
415 *hflags |= H_ALLOC;
416 ncp->c_fileid = inum;
417 TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
418 TAILQ_INIT(&ncp->c_originlist);
419
420 lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr);
421 if (!skiplock)
422 (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT);
423
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);
427
428 *vpp = NULL;
429 return (ncp);
430 }
431
432
433 __private_extern__
434 void
435 hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags)
436 {
437 hfs_chash_lock_spin(hfsmp);
438
439 CLR(cp->c_hflag, hflags);
440
441 if (ISSET(cp->c_hflag, H_WAITING)) {
442 CLR(cp->c_hflag, H_WAITING);
443 wakeup((caddr_t)cp);
444 }
445 hfs_chash_unlock(hfsmp);
446 }
447
448
449 /*
450 * Re-hash two cnodes in the hash table.
451 */
452 __private_extern__
453 void
454 hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2)
455 {
456 hfs_chash_lock_spin(hfsmp);
457
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);
462
463 hfs_chash_unlock(hfsmp);
464 }
465
466
467 /*
468 * Remove a cnode from the hash table.
469 */
470 __private_extern__
471 int
472 hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp)
473 {
474 hfs_chash_lock_spin(hfsmp);
475
476 /* Check if a vnode is getting attached */
477 if (ISSET(cp->c_hflag, H_ATTACH)) {
478 hfs_chash_unlock(hfsmp);
479 return (EBUSY);
480 }
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;
485 }
486 hfs_chash_unlock(hfsmp);
487
488 return (0);
489 }
490
491 /*
492 * Remove a cnode from the hash table and wakeup any waiters.
493 */
494 __private_extern__
495 void
496 hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp)
497 {
498 hfs_chash_lock_spin(hfsmp);
499
500 LIST_REMOVE(cp, c_hash);
501 cp->c_hash.le_next = NULL;
502 cp->c_hash.le_prev = NULL;
503
504 CLR(cp->c_hflag, H_ATTACH | H_ALLOC);
505 if (ISSET(cp->c_hflag, H_WAITING)) {
506 CLR(cp->c_hflag, H_WAITING);
507 wakeup((caddr_t)cp);
508 }
509 hfs_chash_unlock(hfsmp);
510 }
511
512
513 /*
514 * mark a cnode as in transition
515 */
516 __private_extern__
517 void
518 hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp)
519 {
520 hfs_chash_lock_spin(hfsmp);
521
522 SET(cp->c_hflag, H_TRANSIT);
523
524 hfs_chash_unlock(hfsmp);
525 }
526
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.
531 */
532 static
533 struct cnode *
534 hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid)
535 {
536 struct cnode *cp;
537
538 for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
539 if (cp->c_fileid == cnid) {
540 break;
541 }
542 }
543
544 /* If cnode is being created or reclaimed, return error. */
545 if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
546 cp = NULL;
547 }
548
549 return cp;
550 }
551
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.
555 *
556 * Return values -
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.
561 */
562 __private_extern__
563 int
564 hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid)
565 {
566 int retval = -1;
567 struct cnode *cp;
568
569 hfs_chash_lock_spin(hfsmp);
570
571 cp = hfs_chash_search_cnid(hfsmp, cnid);
572 if (cp) {
573 if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
574 retval = 0;
575 } else {
576 cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
577 retval = 1;
578 }
579 }
580 hfs_chash_unlock(hfsmp);
581
582 return retval;
583 }