bsd/hfs/hfs_chash.c

   1 /*
   2  * Copyright (c) 2002-2006 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  * Structures associated with cnode caching.
  87  */
  88 LIST_HEAD(cnodehashhead, cnode) *cnodehashtbl;
  89 u_long  cnodehash;              /* size of hash table - 1 */
  90 #define CNODEHASH(device, inum) (&cnodehashtbl[((device) + (inum)) & cnodehash])
  91
  92 lck_mtx_t  hfs_chash_mutex;
  93
  94 /*
  95  * Initialize cnode hash table.
  96  */
  97 __private_extern__
  98 void
  99 hfs_chashinit()
 100 {
 101         chash_lck_grp_attr= lck_grp_attr_alloc_init();
 102         chash_lck_grp  = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);
 103         chash_lck_attr = lck_attr_alloc_init();
 104
 105         lck_mtx_init(&hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
 106 }
 107
 108 static void hfs_chash_lock(void)
 109 {
 110         lck_mtx_lock(&hfs_chash_mutex);
 111 }
 112
 113 static void hfs_chash_unlock(void)
 114 {
 115         lck_mtx_unlock(&hfs_chash_mutex);
 116 }
 117
 118 __private_extern__
 119 void
 120 hfs_chashinit_finish()
 121 {
 122         hfs_chash_lock();
 123         if (!cnodehashtbl)
 124                 cnodehashtbl = hashinit(desiredvnodes, M_HFSMNT, &cnodehash);
 125         hfs_chash_unlock();
 126 }
 127
 128
 129 /*
 130  * Use the device, inum pair to find the incore cnode.
 131  *
 132  * If it is in core, but locked, wait for it.
 133  */
 134 __private_extern__
 135 struct vnode *
 136 hfs_chash_getvnode(dev_t dev, ino_t inum, int wantrsrc, int skiplock)
 137 {
 138         struct cnode *cp;
 139         struct vnode *vp;
 140         int error;
 141         u_int32_t vid;
 142
 143         /*
 144          * Go through the hash list
 145          * If a cnode is in the process of being cleaned out or being
 146          * allocated, wait for it to be finished and then try again.
 147          */
 148 loop:
 149         hfs_chash_lock();
 150         for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 151                 if ((cp->c_fileid != inum) || (cp->c_dev != dev))
 152                         continue;
 153                 /* Wait if cnode is being created or reclaimed. */
 154                 if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 155                         SET(cp->c_hflag, H_WAITING);
 156
 157                         (void) msleep(cp, &hfs_chash_mutex, PDROP | PINOD,
 158                                       "hfs_chash_getvnode", 0);
 159                         goto loop;
 160                 }
 161                 /* Obtain the desired vnode. */
 162                 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 163                 if (vp == NULLVP)
 164                         goto exit;
 165
 166                 vid = vnode_vid(vp);
 167                 hfs_chash_unlock();
 168
 169                 if ((error = vnode_getwithvid(vp, vid))) {
 170                         /*
 171                          * If vnode is being reclaimed, or has
 172                          * already changed identity, no need to wait
 173                          */
 174                         return (NULL);
 175                 }
 176                 if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK) != 0) {
 177                         vnode_put(vp);
 178                         return (NULL);
 179                 }
 180
 181                 /*
 182                  * Skip cnodes that are not in the name space anymore
 183                  * we need to check with the cnode lock held because
 184                  * we may have blocked acquiring the vnode ref or the
 185                  * lock on the cnode which would allow the node to be
 186                  * unlinked
 187                  */
 188                 if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
 189                         if (!skiplock)
 190                                 hfs_unlock(cp);
 191                         vnode_put(vp);
 192
 193                         return (NULL);
 194                 }
 195                 return (vp);
 196         }
 197 exit:
 198         hfs_chash_unlock();
 199         return (NULL);
 200 }
 201
 202
 203 /*
 204  * Use the device, fileid pair to snoop an incore cnode.
 205  */
 206 __private_extern__
 207 int
 208 hfs_chash_snoop(dev_t dev, ino_t inum, int (*callout)(const struct cat_desc *,
 209                 const struct cat_attr *, void *), void * arg)
 210 {
 211         struct cnode *cp;
 212         int result = ENOENT;
 213
 214         /*
 215          * Go through the hash list
 216          * If a cnode is in the process of being cleaned out or being
 217          * allocated, wait for it to be finished and then try again.
 218          */
 219         hfs_chash_lock();
 220         for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 221                 if ((cp->c_fileid != inum) || (cp->c_dev != dev))
 222                         continue;
 223                 /* Skip cnodes being created or reclaimed. */
 224                 if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 225                         result = callout(&cp->c_desc, &cp->c_attr, arg);
 226                 }
 227                 break;
 228         }
 229         hfs_chash_unlock();
 230         return (result);
 231 }
 232
 233
 234 /*
 235  * Use the device, fileid pair to find the incore cnode.
 236  * If no cnode if found one is created
 237  *
 238  * If it is in core, but locked, wait for it.
 239  *
 240  * If the cnode is C_DELETED, then return NULL since that
 241  * inum is no longer valid for lookups (open-unlinked file).
 242  */
 243 __private_extern__
 244 struct cnode *
 245 hfs_chash_getcnode(dev_t dev, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock)
 246 {
 247         struct cnode    *cp;
 248         struct cnode    *ncp = NULL;
 249         vnode_t         vp;
 250         u_int32_t       vid;
 251
 252         /*
 253          * Go through the hash list
 254          * If a cnode is in the process of being cleaned out or being
 255          * allocated, wait for it to be finished and then try again.
 256          */
 257 loop:
 258         hfs_chash_lock();
 259
 260 loop_with_lock:
 261         for (cp = CNODEHASH(dev, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 262                 if ((cp->c_fileid != inum) || (cp->c_dev != dev))
 263                         continue;
 264                 /*
 265                  * Wait if cnode is being created, attached to or reclaimed.
 266                  */
 267                 if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) {
 268                         SET(cp->c_hflag, H_WAITING);
 269
 270                         (void) msleep(cp, &hfs_chash_mutex, PINOD,
 271                                       "hfs_chash_getcnode", 0);
 272                         goto loop_with_lock;
 273                 }
 274                 vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 275                 if (vp == NULL) {
 276                         /*
 277                          * The desired vnode isn't there so tag the cnode.
 278                          */
 279                         SET(cp->c_hflag, H_ATTACH);
 280
 281                         hfs_chash_unlock();
 282                 } else {
 283                         vid = vnode_vid(vp);
 284
 285                         hfs_chash_unlock();
 286
 287                         if (vnode_getwithvid(vp, vid))
 288                                 goto loop;
 289                 }
 290                 if (ncp) {
 291                         /*
 292                          * someone else won the race to create
 293                          * this cnode and add it to the hash
 294                          * just dump our allocation
 295                          */
 296                         FREE_ZONE(ncp, sizeof(struct cnode), M_HFSNODE);
 297                         ncp = NULL;
 298                 }
 299
 300                 if (!skiplock) {
 301                         hfs_lock(cp, HFS_FORCE_LOCK);
 302                 }
 303
 304                 /*
 305                  * Skip cnodes that are not in the name space anymore
 306                  * we need to check with the cnode lock held because
 307                  * we may have blocked acquiring the vnode ref or the
 308                  * lock on the cnode which would allow the node to be
 309                  * unlinked.
 310                  *
 311                  * Don't return a cnode in this case since the inum
 312                  * is no longer valid for lookups.
 313                  */
 314                 if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) {
 315                         if (!skiplock)
 316                                 hfs_unlock(cp);
 317                         if (vp != NULLVP) {
 318                                 vnode_put(vp);
 319                         } else {
 320                                 hfs_chash_lock();
 321                                 CLR(cp->c_hflag, H_ATTACH);
 322                                 if (ISSET(cp->c_hflag, H_WAITING)) {
 323                                         CLR(cp->c_hflag, H_WAITING);
 324                                         wakeup((caddr_t)cp);
 325                                 }
 326                                 hfs_chash_unlock();
 327                         }
 328                         vp = NULL;
 329                         cp = NULL;
 330                 }
 331                 *vpp = vp;
 332                 return (cp);
 333         }
 334
 335         /*
 336          * Allocate a new cnode
 337          */
 338         if (skiplock && !wantrsrc)
 339                 panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
 340
 341         if (ncp == NULL) {
 342                 hfs_chash_unlock();
 343
 344                 MALLOC_ZONE(ncp, struct cnode *, sizeof(struct cnode), M_HFSNODE, M_WAITOK);
 345                 /*
 346                  * since we dropped the chash lock,
 347                  * we need to go back and re-verify
 348                  * that this node hasn't come into
 349                  * existence...
 350                  */
 351                 goto loop;
 352         }
 353         bzero(ncp, sizeof(struct cnode));
 354         SET(ncp->c_hflag, H_ALLOC);
 355         ncp->c_fileid = inum;
 356         ncp->c_dev = dev;
 357         TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
 358         TAILQ_INIT(&ncp->c_originlist);
 359
 360         lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr);
 361         if (!skiplock)
 362                 (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK);
 363
 364         /* Insert the new cnode with it's H_ALLOC flag set */
 365         LIST_INSERT_HEAD(CNODEHASH(dev, inum), ncp, c_hash);
 366         hfs_chash_unlock();
 367
 368         *vpp = NULL;
 369         return (ncp);
 370 }
 371
 372
 373 __private_extern__
 374 void
 375 hfs_chashwakeup(struct cnode *cp, int hflags)
 376 {
 377         hfs_chash_lock();
 378
 379         CLR(cp->c_hflag, hflags);
 380
 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();
 386 }
 387
 388
 389 /*
 390  * Re-hash two cnodes in the hash table.
 391  */
 392 __private_extern__
 393 void
 394 hfs_chash_rehash(struct cnode *cp1, struct cnode *cp2)
 395 {
 396         hfs_chash_lock();
 397
 398         LIST_REMOVE(cp1, c_hash);
 399         LIST_REMOVE(cp2, c_hash);
 400         LIST_INSERT_HEAD(CNODEHASH(cp1->c_dev, cp1->c_fileid), cp1, c_hash);
 401         LIST_INSERT_HEAD(CNODEHASH(cp2->c_dev, cp2->c_fileid), cp2, c_hash);
 402
 403         hfs_chash_unlock();
 404 }
 405
 406
 407 /*
 408  * Remove a cnode from the hash table.
 409  */
 410 __private_extern__
 411 int
 412 hfs_chashremove(struct cnode *cp)
 413 {
 414         hfs_chash_lock();
 415
 416         /* Check if a vnode is getting attached */
 417         if (ISSET(cp->c_hflag, H_ATTACH)) {
 418                 hfs_chash_unlock();
 419                 return (EBUSY);
 420         }
 421         if (cp->c_hash.le_next || cp->c_hash.le_prev) {
 422             LIST_REMOVE(cp, c_hash);
 423             cp->c_hash.le_next = NULL;
 424             cp->c_hash.le_prev = NULL;
 425         }
 426         hfs_chash_unlock();
 427         return (0);
 428 }
 429
 430 /*
 431  * Remove a cnode from the hash table and wakeup any waiters.
 432  */
 433 __private_extern__
 434 void
 435 hfs_chash_abort(struct cnode *cp)
 436 {
 437         hfs_chash_lock();
 438
 439         LIST_REMOVE(cp, c_hash);
 440         cp->c_hash.le_next = NULL;
 441         cp->c_hash.le_prev = NULL;
 442
 443         CLR(cp->c_hflag, H_ATTACH | H_ALLOC);
 444         if (ISSET(cp->c_hflag, H_WAITING)) {
 445                 CLR(cp->c_hflag, H_WAITING);
 446                 wakeup((caddr_t)cp);
 447         }
 448         hfs_chash_unlock();
 449 }
 450
 451
 452 /*
 453  * mark a cnode as in transition
 454  */
 455 __private_extern__
 456 void
 457 hfs_chash_mark_in_transit(struct cnode *cp)
 458 {
 459         hfs_chash_lock();
 460
 461         SET(cp->c_hflag, H_TRANSIT);
 462
 463         hfs_chash_unlock();
 464 }
 465
 466 /* Search a cnode in the hash.  This function does not return cnode which
 467  * are getting created, destroyed or in transition.  Note that this function
 468  * does not acquire the cnode hash mutex, and expects the caller to acquire it.
 469  * On success, returns pointer to the cnode found.  On failure, returns NULL.
 470  */
 471 static
 472 struct cnode *
 473 hfs_chash_search_cnid(dev_t dev, cnid_t cnid)
 474 {
 475         struct cnode *cp;
 476
 477         for (cp = CNODEHASH(dev, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
 478                 if ((cp->c_fileid == cnid) && (cp->c_dev == dev)) {
 479                         break;
 480                 }
 481         }
 482
 483         /* If cnode is being created or reclaimed, return error. */
 484         if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 485                 cp = NULL;
 486         }
 487
 488         return cp;
 489 }
 490
 491 /* Search a cnode corresponding to given device and ID in the hash.  If the
 492  * found cnode has kHFSHasChildLinkBit cleared, set it.  If the cnode is not
 493  * found, no new cnode is created and error is returned.
 494  *
 495  * Return values -
 496  *      -1 : The cnode was not found.
 497  *       0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
 498  *       1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
 499  *           function had to set that bit.
 500  */
 501 __private_extern__
 502 int
 503 hfs_chash_set_childlinkbit(dev_t dev, cnid_t cnid)
 504 {
 505         int retval = -1;
 506         struct cnode *cp;
 507
 508         hfs_chash_lock();
 509         cp = hfs_chash_search_cnid(dev, cnid);
 510         if (cp) {
 511                 if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
 512                         retval = 0;
 513                 } else {
 514                         cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
 515                         retval = 1;
 516                 }
 517         }
 518         hfs_chash_unlock();
 519
 520         return retval;
 521 }