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 77extern lck_attr_t * hfs_lock_attr; 78extern lck_grp_t * hfs_mutex_group; 79extern lck_grp_t * hfs_rwlock_group; 80 81lck_grp_t * chash_lck_grp; 82lck_grp_attr_t * chash_lck_grp_attr; 83lck_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__ 93void 94hfs_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 101static void hfs_chash_lock(struct hfsmount *hfsmp) 102{ 103 lck_mtx_lock(&hfsmp->hfs_chash_mutex); 104} 105 106static void hfs_chash_lock_spin(struct hfsmount *hfsmp) 107{ 108 lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex); 109} 110 111static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp) 112{ 113 lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex); 114} 115 116static void hfs_chash_unlock(struct hfsmount *hfsmp) 117{ 118 lck_mtx_unlock(&hfsmp->hfs_chash_mutex); 119} 120 121__private_extern__ 122void 123hfs_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__ 131void 132hfs_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 */ 145struct vnode * 146hfs_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 */ 158loop: 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 } 210exit: 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 */ 224int 225hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int existence_only, 226 int (*callout)(const cnode_t *cp, 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 result = EACCES; 264 break; 265 } 266 267 /* Skip cnodes being created or reclaimed. */ 268 if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { 269 result = callout(cp, arg); 270 } 271 break; 272 } 273 hfs_chash_unlock(hfsmp); 274 275 return (result); 276} 277 278 279/* 280 * Use the device, fileid pair to find the incore cnode. 281 * If no cnode if found one is created 282 * 283 * If it is in core, but locked, wait for it. 284 * 285 * If the cnode is C_DELETED, then return NULL since that 286 * inum is no longer valid for lookups (open-unlinked file). 287 * 288 * If the cnode is C_DELETED but also marked C_RENAMED, then that means 289 * the cnode was renamed over and a new entry exists in its place. The caller 290 * should re-drive the lookup to get the newer entry. In that case, we'll still 291 * return NULL for the cnode, but also return GNV_CHASH_RENAMED in the output flags 292 * of this function to indicate the caller that they should re-drive. 293 */ 294struct cnode * 295hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp, 296 int wantrsrc, int skiplock, int *out_flags, int *hflags) 297{ 298 struct cnode *cp; 299 struct cnode *ncp = NULL; 300 vnode_t vp; 301 u_int32_t vid; 302 303 /* 304 * Go through the hash list 305 * If a cnode is in the process of being cleaned out or being 306 * allocated, wait for it to be finished and then try again. 307 */ 308loop: 309 hfs_chash_lock_spin(hfsmp); 310 311loop_with_lock: 312 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { 313 if (cp->c_fileid != inum) 314 continue; 315 /* 316 * Wait if cnode is being created, attached to or reclaimed. 317 */ 318 if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) { 319 SET(cp->c_hflag, H_WAITING); 320 321 (void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD, 322 "hfs_chash_getcnode", 0); 323 goto loop_with_lock; 324 } 325 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; 326 if (vp == NULL) { 327 /* 328 * The desired vnode isn't there so tag the cnode. 329 */ 330 SET(cp->c_hflag, H_ATTACH); 331 *hflags |= H_ATTACH; 332 333 hfs_chash_unlock(hfsmp); 334 } else { 335 vid = vnode_vid(vp); 336 337 hfs_chash_unlock(hfsmp); 338 339 if (vnode_getwithvid(vp, vid)) 340 goto loop; 341 } 342 if (ncp) { 343 /* 344 * someone else won the race to create 345 * this cnode and add it to the hash 346 * just dump our allocation 347 */ 348 FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE); 349 ncp = NULL; 350 } 351 352 if (!skiplock) { 353 hfs_lock(cp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS); 354 } 355 356 /* 357 * Skip cnodes that are not in the name space anymore 358 * we need to check with the cnode lock held because 359 * we may have blocked acquiring the vnode ref or the 360 * lock on the cnode which would allow the node to be 361 * unlinked. 362 * 363 * Don't return a cnode in this case since the inum 364 * is no longer valid for lookups. 365 */ 366 if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) { 367 int renamed = 0; 368 if (cp->c_flag & C_RENAMED) { 369 renamed = 1; 370 } 371 if (!skiplock) 372 hfs_unlock(cp); 373 if (vp != NULLVP) { 374 vnode_put(vp); 375 } else { 376 hfs_chash_lock_spin(hfsmp); 377 CLR(cp->c_hflag, H_ATTACH); 378 *hflags &= ~H_ATTACH; 379 if (ISSET(cp->c_hflag, H_WAITING)) { 380 CLR(cp->c_hflag, H_WAITING); 381 wakeup((caddr_t)cp); 382 } 383 hfs_chash_unlock(hfsmp); 384 } 385 vp = NULL; 386 cp = NULL; 387 if (renamed) { 388 *out_flags = GNV_CHASH_RENAMED; 389 } 390 } 391 *vpp = vp; 392 return (cp); 393 } 394 395 /* 396 * Allocate a new cnode 397 */ 398 if (skiplock && !wantrsrc) 399 panic("%s - should never get here when skiplock is set \n", __FUNCTION__); 400 401 if (ncp == NULL) { 402 hfs_chash_unlock(hfsmp); 403 404 MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK); 405 /* 406 * since we dropped the chash lock, 407 * we need to go back and re-verify 408 * that this node hasn't come into 409 * existence... 410 */ 411 goto loop; 412 } 413 hfs_chash_lock_convert(hfsmp); 414 415 bzero(ncp, sizeof(struct cnode)); 416 SET(ncp->c_hflag, H_ALLOC); 417 *hflags |= H_ALLOC; 418 ncp->c_fileid = inum; 419 TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */ 420 TAILQ_INIT(&ncp->c_originlist); 421 422 lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr); 423 if (!skiplock) 424 (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT); 425 426 /* Insert the new cnode with it's H_ALLOC flag set */ 427 LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash); 428 hfs_chash_unlock(hfsmp); 429 430 *vpp = NULL; 431 return (ncp); 432} 433 434 435__private_extern__ 436void 437hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags) 438{ 439 hfs_chash_lock_spin(hfsmp); 440 441 CLR(cp->c_hflag, hflags); 442 443 if (ISSET(cp->c_hflag, H_WAITING)) { 444 CLR(cp->c_hflag, H_WAITING); 445 wakeup((caddr_t)cp); 446 } 447 hfs_chash_unlock(hfsmp); 448} 449 450 451/* 452 * Re-hash two cnodes in the hash table. 453 */ 454__private_extern__ 455void 456hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2) 457{ 458 hfs_chash_lock_spin(hfsmp); 459 460 LIST_REMOVE(cp1, c_hash); 461 LIST_REMOVE(cp2, c_hash); 462 LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp1->c_fileid), cp1, c_hash); 463 LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp2->c_fileid), cp2, c_hash); 464 465 hfs_chash_unlock(hfsmp); 466} 467 468 469/* 470 * Remove a cnode from the hash table. 471 */ 472__private_extern__ 473int 474hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp) 475{ 476 hfs_chash_lock_spin(hfsmp); 477 478 /* Check if a vnode is getting attached */ 479 if (ISSET(cp->c_hflag, H_ATTACH)) { 480 hfs_chash_unlock(hfsmp); 481 return (EBUSY); 482 } 483 if (cp->c_hash.le_next || cp->c_hash.le_prev) { 484 LIST_REMOVE(cp, c_hash); 485 cp->c_hash.le_next = NULL; 486 cp->c_hash.le_prev = NULL; 487 } 488 hfs_chash_unlock(hfsmp); 489 490 return (0); 491} 492 493/* 494 * Remove a cnode from the hash table and wakeup any waiters. 495 */ 496__private_extern__ 497void 498hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp) 499{ 500 hfs_chash_lock_spin(hfsmp); 501 502 LIST_REMOVE(cp, c_hash); 503 cp->c_hash.le_next = NULL; 504 cp->c_hash.le_prev = NULL; 505 506 CLR(cp->c_hflag, H_ATTACH | H_ALLOC); 507 if (ISSET(cp->c_hflag, H_WAITING)) { 508 CLR(cp->c_hflag, H_WAITING); 509 wakeup((caddr_t)cp); 510 } 511 hfs_chash_unlock(hfsmp); 512} 513 514 515/* 516 * mark a cnode as in transition 517 */ 518__private_extern__ 519void 520hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp) 521{ 522 hfs_chash_lock_spin(hfsmp); 523 524 SET(cp->c_hflag, H_TRANSIT); 525 526 hfs_chash_unlock(hfsmp); 527} 528 529/* Search a cnode in the hash. This function does not return cnode which 530 * are getting created, destroyed or in transition. Note that this function 531 * does not acquire the cnode hash mutex, and expects the caller to acquire it. 532 * On success, returns pointer to the cnode found. On failure, returns NULL. 533 */ 534static 535struct cnode * 536hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid) 537{ 538 struct cnode *cp; 539 540 for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) { 541 if (cp->c_fileid == cnid) { 542 break; 543 } 544 } 545 546 /* If cnode is being created or reclaimed, return error. */ 547 if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { 548 cp = NULL; 549 } 550 551 return cp; 552} 553 554/* Search a cnode corresponding to given device and ID in the hash. If the 555 * found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not 556 * found, no new cnode is created and error is returned. 557 * 558 * Return values - 559 * -1 : The cnode was not found. 560 * 0 : The cnode was found, and the kHFSHasChildLinkBit was already set. 561 * 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the 562 * function had to set that bit. 563 */ 564__private_extern__ 565int 566hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid) 567{ 568 int retval = -1; 569 struct cnode *cp; 570 571 hfs_chash_lock_spin(hfsmp); 572 573 cp = hfs_chash_search_cnid(hfsmp, cnid); 574 if (cp) { 575 if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) { 576 retval = 0; 577 } else { 578 cp->c_attr.ca_recflags |= kHFSHasChildLinkMask; 579 retval = 1; 580 } 581 } 582 hfs_chash_unlock(hfsmp); 583 584 return retval; 585} 586