1/* 2 * Copyright (c) 2002-2008 Apple Computer, 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 111#ifdef i386 112static void hfs_chash_lock_convert (struct hfsmount *hfsmp) 113#else 114static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp) 115#endif 116{ 117 lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex); 118} 119 120static void hfs_chash_unlock(struct hfsmount *hfsmp) 121{ 122 lck_mtx_unlock(&hfsmp->hfs_chash_mutex); 123} 124 125__private_extern__ 126void 127hfs_chashinit_finish(struct hfsmount *hfsmp) 128{ 129 lck_mtx_init(&hfsmp->hfs_chash_mutex, chash_lck_grp, chash_lck_attr); 130 131 hfsmp->hfs_cnodehashtbl = hashinit(desiredvnodes / 4, M_HFSMNT, &hfsmp->hfs_cnodehash); 132} 133 134__private_extern__ 135void 136hfs_delete_chash(struct hfsmount *hfsmp) 137{ 138 lck_mtx_destroy(&hfsmp->hfs_chash_mutex, chash_lck_grp); 139 140 FREE(hfsmp->hfs_cnodehashtbl, M_HFSMNT); 141} 142 143 144/* 145 * Use the device, inum pair to find the incore cnode. 146 * 147 * If it is in core, but locked, wait for it. 148 */ 149struct vnode * 150hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock, int allow_deleted) 151{ 152 struct cnode *cp; 153 struct vnode *vp; 154 int error; 155 u_int32_t vid; 156 157 /* 158 * Go through the hash list 159 * If a cnode is in the process of being cleaned out or being 160 * allocated, wait for it to be finished and then try again. 161 */ 162loop: 163 hfs_chash_lock_spin(hfsmp); 164 165 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { 166 if (cp->c_fileid != inum) 167 continue; 168 /* Wait if cnode is being created or reclaimed. */ 169 if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { 170 SET(cp->c_hflag, H_WAITING); 171 172 (void) msleep(cp, &hfsmp->hfs_chash_mutex, PDROP | PINOD, 173 "hfs_chash_getvnode", 0); 174 goto loop; 175 } 176 /* Obtain the desired vnode. */ 177 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; 178 if (vp == NULLVP) 179 goto exit; 180 181 vid = vnode_vid(vp); 182 hfs_chash_unlock(hfsmp); 183 184 if ((error = vnode_getwithvid(vp, vid))) { 185 /* 186 * If vnode is being reclaimed, or has 187 * already changed identity, no need to wait 188 */ 189 return (NULL); 190 } 191 if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) { 192 vnode_put(vp); 193 return (NULL); 194 } 195 196 /* 197 * Skip cnodes that are not in the name space anymore 198 * we need to check with the cnode lock held because 199 * we may have blocked acquiring the vnode ref or the 200 * lock on the cnode which would allow the node to be 201 * unlinked 202 */ 203 if (!allow_deleted) { 204 if (cp->c_flag & (C_NOEXISTS | C_DELETED)) { 205 if (!skiplock) { 206 hfs_unlock(cp); 207 } 208 vnode_put(vp); 209 return (NULL); 210 } 211 } 212 return (vp); 213 } 214exit: 215 hfs_chash_unlock(hfsmp); 216 return (NULL); 217} 218 219 220/* 221 * Use the device, fileid pair to snoop an incore cnode. 222 * 223 * A cnode can exists in chash even after it has been 224 * deleted from the catalog, so this function returns 225 * ENOENT if C_NOEXIST is set in the cnode's flag. 226 * 227 */ 228int 229hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int existence_only, int (*callout)(const struct cat_desc *, 230 const struct cat_attr *, void *), void * arg) 231{ 232 struct cnode *cp; 233 int result = ENOENT; 234 235 /* 236 * Go through the hash list 237 * If a cnode is in the process of being cleaned out or being 238 * allocated, wait for it to be finished and then try again. 239 */ 240 hfs_chash_lock(hfsmp); 241 242 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { 243 if (cp->c_fileid != inum) 244 continue; 245 246 /* 247 * Under normal circumstances, we would want to return ENOENT if a cnode is in 248 * the hash and it is marked C_NOEXISTS or C_DELETED. However, if the CNID 249 * namespace has wrapped around, then we have the possibility of collisions. 250 * In that case, we may use this function to validate whether or not we 251 * should trust the nextCNID value in the hfs mount point. 252 * 253 * If we didn't do this, then it would be possible for a cnode that is no longer backed 254 * by anything on-disk (C_NOEXISTS) to still exist in the hash along with its 255 * vnode. The cat_create routine could then create a new entry in the catalog 256 * re-using that CNID. Then subsequent hfs_getnewvnode calls will repeatedly fail 257 * trying to look it up/validate it because it is marked C_NOEXISTS. So we want 258 * to prevent that from happening as much as possible. 259 */ 260 if (existence_only) { 261 result = 0; 262 break; 263 } 264 265 /* Skip cnodes that have been removed from the catalog */ 266 if (cp->c_flag & (C_NOEXISTS | C_DELETED)) { 267 break; 268 } 269 /* Skip cnodes being created or reclaimed. */ 270 if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { 271 result = callout(&cp->c_desc, &cp->c_attr, arg); 272 } 273 break; 274 } 275 hfs_chash_unlock(hfsmp); 276 277 return (result); 278} 279 280 281/* 282 * Use the device, fileid pair to find the incore cnode. 283 * If no cnode if found one is created 284 * 285 * If it is in core, but locked, wait for it. 286 * 287 * If the cnode is C_DELETED, then return NULL since that 288 * inum is no longer valid for lookups (open-unlinked file). 289 * 290 * If the cnode is C_DELETED but also marked C_RENAMED, then that means 291 * the cnode was renamed over and a new entry exists in its place. The caller 292 * should re-drive the lookup to get the newer entry. In that case, we'll still 293 * return NULL for the cnode, but also return GNV_CHASH_RENAMED in the output flags 294 * of this function to indicate the caller that they should re-drive. 295 */ 296struct cnode * 297hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp, 298 int wantrsrc, int skiplock, int *out_flags, int *hflags) 299{ 300 struct cnode *cp; 301 struct cnode *ncp = NULL; 302 vnode_t vp; 303 u_int32_t vid; 304 305 /* 306 * Go through the hash list 307 * If a cnode is in the process of being cleaned out or being 308 * allocated, wait for it to be finished and then try again. 309 */ 310loop: 311 hfs_chash_lock_spin(hfsmp); 312 313loop_with_lock: 314 for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) { 315 if (cp->c_fileid != inum) 316 continue; 317 /* 318 * Wait if cnode is being created, attached to or reclaimed. 319 */ 320 if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) { 321 SET(cp->c_hflag, H_WAITING); 322 323 (void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD, 324 "hfs_chash_getcnode", 0); 325 goto loop_with_lock; 326 } 327 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp; 328 if (vp == NULL) { 329 /* 330 * The desired vnode isn't there so tag the cnode. 331 */ 332 SET(cp->c_hflag, H_ATTACH); 333 *hflags |= H_ATTACH; 334 335 hfs_chash_unlock(hfsmp); 336 } else { 337 vid = vnode_vid(vp); 338 339 hfs_chash_unlock(hfsmp); 340 341 if (vnode_getwithvid(vp, vid)) 342 goto loop; 343 } 344 if (ncp) { 345 /* 346 * someone else won the race to create 347 * this cnode and add it to the hash 348 * just dump our allocation 349 */ 350 FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE); 351 ncp = NULL; 352 } 353 354 if (!skiplock) { 355 hfs_lock(cp, HFS_FORCE_LOCK); 356 } 357 358 /* 359 * Skip cnodes that are not in the name space anymore 360 * we need to check with the cnode lock held because 361 * we may have blocked acquiring the vnode ref or the 362 * lock on the cnode which would allow the node to be 363 * unlinked. 364 * 365 * Don't return a cnode in this case since the inum 366 * is no longer valid for lookups. 367 */ 368 if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) { 369 int renamed = 0; 370 if (cp->c_flag & C_RENAMED) { 371 renamed = 1; 372 } 373 if (!skiplock) 374 hfs_unlock(cp); 375 if (vp != NULLVP) { 376 vnode_put(vp); 377 } else { 378 hfs_chash_lock_spin(hfsmp); 379 CLR(cp->c_hflag, H_ATTACH); 380 *hflags &= ~H_ATTACH; 381 if (ISSET(cp->c_hflag, H_WAITING)) { 382 CLR(cp->c_hflag, H_WAITING); 383 wakeup((caddr_t)cp); 384 } 385 hfs_chash_unlock(hfsmp); 386 } 387 vp = NULL; 388 cp = NULL; 389 if (renamed) { 390 *out_flags = GNV_CHASH_RENAMED; 391 } 392 } 393 *vpp = vp; 394 return (cp); 395 } 396 397 /* 398 * Allocate a new cnode 399 */ 400 if (skiplock && !wantrsrc) 401 panic("%s - should never get here when skiplock is set \n", __FUNCTION__); 402 403 if (ncp == NULL) { 404 hfs_chash_unlock(hfsmp); 405 406 MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK); 407 /* 408 * since we dropped the chash lock, 409 * we need to go back and re-verify 410 * that this node hasn't come into 411 * existence... 412 */ 413 goto loop; 414 } 415 hfs_chash_lock_convert(hfsmp); 416 417 bzero(ncp, sizeof(struct cnode)); 418 SET(ncp->c_hflag, H_ALLOC); 419 *hflags |= H_ALLOC; 420 ncp->c_fileid = inum; 421 TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */ 422 TAILQ_INIT(&ncp->c_originlist); 423 424 lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr); 425 if (!skiplock) 426 (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK); 427 428 /* Insert the new cnode with it's H_ALLOC flag set */ 429 LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash); 430 hfs_chash_unlock(hfsmp); 431 432 *vpp = NULL; 433 return (ncp); 434} 435 436 437__private_extern__ 438void 439hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags) 440{ 441 hfs_chash_lock_spin(hfsmp); 442 443 CLR(cp->c_hflag, hflags); 444 445 if (ISSET(cp->c_hflag, H_WAITING)) { 446 CLR(cp->c_hflag, H_WAITING); 447 wakeup((caddr_t)cp); 448 } 449 hfs_chash_unlock(hfsmp); 450} 451 452 453/* 454 * Re-hash two cnodes in the hash table. 455 */ 456__private_extern__ 457void 458hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2) 459{ 460 hfs_chash_lock_spin(hfsmp); 461 462 LIST_REMOVE(cp1, c_hash); 463 LIST_REMOVE(cp2, c_hash); 464 LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp1->c_fileid), cp1, c_hash); 465 LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp2->c_fileid), cp2, c_hash); 466 467 hfs_chash_unlock(hfsmp); 468} 469 470 471/* 472 * Remove a cnode from the hash table. 473 */ 474__private_extern__ 475int 476hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp) 477{ 478 hfs_chash_lock_spin(hfsmp); 479 480 /* Check if a vnode is getting attached */ 481 if (ISSET(cp->c_hflag, H_ATTACH)) { 482 hfs_chash_unlock(hfsmp); 483 return (EBUSY); 484 } 485 if (cp->c_hash.le_next || cp->c_hash.le_prev) { 486 LIST_REMOVE(cp, c_hash); 487 cp->c_hash.le_next = NULL; 488 cp->c_hash.le_prev = NULL; 489 } 490 hfs_chash_unlock(hfsmp); 491 492 return (0); 493} 494 495/* 496 * Remove a cnode from the hash table and wakeup any waiters. 497 */ 498__private_extern__ 499void 500hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp) 501{ 502 hfs_chash_lock_spin(hfsmp); 503 504 LIST_REMOVE(cp, c_hash); 505 cp->c_hash.le_next = NULL; 506 cp->c_hash.le_prev = NULL; 507 508 CLR(cp->c_hflag, H_ATTACH | H_ALLOC); 509 if (ISSET(cp->c_hflag, H_WAITING)) { 510 CLR(cp->c_hflag, H_WAITING); 511 wakeup((caddr_t)cp); 512 } 513 hfs_chash_unlock(hfsmp); 514} 515 516 517/* 518 * mark a cnode as in transition 519 */ 520__private_extern__ 521void 522hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp) 523{ 524 hfs_chash_lock_spin(hfsmp); 525 526 SET(cp->c_hflag, H_TRANSIT); 527 528 hfs_chash_unlock(hfsmp); 529} 530 531/* Search a cnode in the hash. This function does not return cnode which 532 * are getting created, destroyed or in transition. Note that this function 533 * does not acquire the cnode hash mutex, and expects the caller to acquire it. 534 * On success, returns pointer to the cnode found. On failure, returns NULL. 535 */ 536static 537struct cnode * 538hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid) 539{ 540 struct cnode *cp; 541 542 for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) { 543 if (cp->c_fileid == cnid) { 544 break; 545 } 546 } 547 548 /* If cnode is being created or reclaimed, return error. */ 549 if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) { 550 cp = NULL; 551 } 552 553 return cp; 554} 555 556/* Search a cnode corresponding to given device and ID in the hash. If the 557 * found cnode has kHFSHasChildLinkBit cleared, set it. If the cnode is not 558 * found, no new cnode is created and error is returned. 559 * 560 * Return values - 561 * -1 : The cnode was not found. 562 * 0 : The cnode was found, and the kHFSHasChildLinkBit was already set. 563 * 1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the 564 * function had to set that bit. 565 */ 566__private_extern__ 567int 568hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid) 569{ 570 int retval = -1; 571 struct cnode *cp; 572 573 hfs_chash_lock_spin(hfsmp); 574 575 cp = hfs_chash_search_cnid(hfsmp, cnid); 576 if (cp) { 577 if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) { 578 retval = 0; 579 } else { 580 cp->c_attr.ca_recflags |= kHFSHasChildLinkMask; 581 retval = 1; 582 } 583 } 584 hfs_chash_unlock(hfsmp); 585 586 return retval; 587} 588