core/hfs_chash.c

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