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, 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 */ 292struct cnode * 293hfs_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 */ 306loop: 307 hfs_chash_lock_spin(hfsmp); 308 309loop_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__ 434void 435hfs_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__ 453void 454hfs_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__ 471int 472hfs_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__ 495void 496hfs_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__ 517void 518hfs_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 */ 532static 533struct cnode * 534hfs_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__ 563int 564hfs_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} 584