bsd/hfs/hfs_chash.c

   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
  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 #ifdef i386
 112 static void hfs_chash_lock_convert (struct hfsmount *hfsmp)
 113 #else
 114 static void hfs_chash_lock_convert (__unused struct hfsmount *hfsmp)
 115 #endif
 116 {
 117         lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex);
 118 }
 119
 120 static void hfs_chash_unlock(struct hfsmount *hfsmp)
 121 {
 122         lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
 123 }
 124
 125 __private_extern__
 126 void
 127 hfs_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__
 135 void
 136 hfs_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  */
 149 struct vnode *
 150 hfs_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          */
 162 loop:
 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                                 vnode_put(vp);
 208
 209                                 return (NULL);
 210                         }
 211                 }
 212                 return (vp);
 213         }
 214 exit:
 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  */
 228 int
 229 hfs_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  */
 296 struct cnode *
 297 hfs_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          */
 310 loop:
 311         hfs_chash_lock_spin(hfsmp);
 312
 313 loop_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
 382                                 if (ISSET(cp->c_hflag, H_WAITING)) {
 383                                         CLR(cp->c_hflag, H_WAITING);
 384                                         wakeup((caddr_t)cp);
 385                                 }
 386                                 hfs_chash_unlock(hfsmp);
 387                         }
 388                         vp = NULL;
 389                         cp = NULL;
 390                         if (renamed) {
 391                                 *out_flags = GNV_CHASH_RENAMED;
 392                         }
 393                 }
 394                 *vpp = vp;
 395                 return (cp);
 396         }
 397
 398         /*
 399          * Allocate a new cnode
 400          */
 401         if (skiplock && !wantrsrc)
 402                 panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
 403
 404         if (ncp == NULL) {
 405                 hfs_chash_unlock(hfsmp);
 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__
 438 void
 439 hfs_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__
 457 void
 458 hfs_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__
 475 int
 476 hfs_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__
 499 void
 500 hfs_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__
 521 void
 522 hfs_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  */
 536 static
 537 struct cnode *
 538 hfs_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__
 567 int
 568 hfs_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 }