livefiles_hfs_plugin/lf_hfs_chash.c

   1 /*  Copyright © 2017-2018 Apple Inc. All rights reserved.
   2  *
   3  *  lf_hfs_chash.c
   4  *  livefiles_hfs
   5  *
   6  *  Created by Or Haimovich on 18/3/18.
   7  */
   8
   9 #include "lf_hfs_chash.h"
  10 #include "lf_hfs_cnode.h"
  11 #include "lf_hfs_locks.h"
  12 #include "lf_hfs_utils.h"
  13 #include "lf_hfs_logger.h"
  14 #include "lf_hfs_vfsutils.h"
  15
  16 #define DESIRED_VNODES (128)        /* number of vnodes desired */
  17 #define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])
  18
  19 void
  20 hfs_chash_wait(struct hfsmount *hfsmp, struct cnode  *cp)
  21 {
  22     SET(cp->c_hflag, H_WAITING);
  23     pthread_cond_wait(&cp->c_cacsh_cond, &hfsmp->hfs_chash_mutex);
  24 }
  25
  26 void
  27 hfs_chash_broadcast_and_unlock(struct hfsmount *hfsmp, struct cnode  *cp)
  28 {
  29     pthread_cond_signal(&cp->c_cacsh_cond);
  30     hfs_chash_unlock(hfsmp);
  31 }
  32
  33 void
  34 hfs_chash_raise_OpenLookupCounter(struct cnode *cp)
  35 {
  36     if (!cp || cp->uOpenLookupRefCount == UINT32_MAX)
  37     {
  38         LFHFS_LOG(LEVEL_ERROR,
  39                   "hfs_chash_raise_OpenLookupCounter:"
  40                   "cp[%p] is NULL or reached max Open Lookup Counter", cp);
  41         hfs_assert(0);
  42     }
  43     cp->uOpenLookupRefCount++;
  44 }
  45
  46 void
  47 hfs_chash_lower_OpenLookupCounter(struct cnode *cp)
  48 {
  49     if (cp->uOpenLookupRefCount == 0)
  50     {
  51         LFHFS_LOG(LEVEL_ERROR, "hfs_chash_lower_OpenLookupCounter: reached min Open Lookup Counter \n");
  52         hfs_assert(0);
  53     }
  54     cp->uOpenLookupRefCount--;
  55 }
  56
  57 /*
  58  * Initialize cnode hash table.
  59  */
  60 void
  61 hfs_chashinit()
  62 {
  63 }
  64
  65 void hfs_chash_lock(struct hfsmount *hfsmp)
  66 {
  67     lf_lck_mtx_lock(&hfsmp->hfs_chash_mutex);
  68 }
  69
  70 void hfs_chash_lock_spin(struct hfsmount *hfsmp)
  71 {
  72     lf_lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
  73 }
  74
  75
  76 void hfs_chash_unlock(struct hfsmount *hfsmp)
  77 {
  78     lf_lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
  79 }
  80
  81 void
  82 hfs_chashinit_finish(struct hfsmount *hfsmp)
  83 {
  84     lf_lck_mtx_init(&hfsmp->hfs_chash_mutex);
  85     hfsmp->hfs_cnodehashtbl = hashinit(DESIRED_VNODES / 4, &hfsmp->hfs_cnodehash);
  86 }
  87
  88 void
  89 hfs_delete_chash(struct hfsmount *hfsmp)
  90 {
  91     struct cnode  *cp;
  92     hfs_chash_lock_spin(hfsmp);
  93
  94     for (ino_t inum = 0;  inum < (DESIRED_VNODES/4); inum++)
  95     {
  96         for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
  97             LFHFS_LOG(LEVEL_ERROR, "hfs_delete_chash: Cnode for file [%s], cnid: [%d] with open count [%d] left in the cache \n", cp->c_desc.cd_nameptr, cp->c_desc.cd_cnid, cp->uOpenLookupRefCount);
  98         }
  99     }
 100
 101
 102     hfs_chash_unlock(hfsmp);
 103     lf_lck_mtx_destroy(&hfsmp->hfs_chash_mutex);
 104     hfs_free(hfsmp->hfs_cnodehashtbl);
 105 }
 106
 107 /*
 108  * Use the device, fileid pair to find the incore cnode.
 109  * If no cnode if found one is created
 110  *
 111  * If it is in core, but locked, wait for it.
 112  *
 113  * If the cnode is C_DELETED, then return NULL since that
 114  * inum is no longer valid for lookups (open-unlinked file).
 115  *
 116  * If the cnode is C_DELETED but also marked C_RENAMED, then that means
 117  * the cnode was renamed over and a new entry exists in its place.  The caller
 118  * should re-drive the lookup to get the newer entry.  In that case, we'll still
 119  * return NULL for the cnode, but also return GNV_CHASH_RENAMED in the output flags
 120  * of this function to indicate the caller that they should re-drive.
 121  */
 122 struct cnode*
 123 hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp, int wantrsrc, int skiplock, int *out_flags, int *hflags)
 124 {
 125     struct cnode  *cp;
 126     struct cnode  *ncp = NULL;
 127     vnode_t       vp;
 128
 129     /*
 130      * Go through the hash list
 131      * If a cnode is in the process of being cleaned out or being
 132      * allocated, wait for it to be finished and then try again.
 133      */
 134 loop:
 135     hfs_chash_lock_spin(hfsmp);
 136 loop_with_lock:
 137     for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next)
 138     {
 139         if (cp->c_fileid != inum)
 140         {
 141             continue;
 142         }
 143         /*
 144          * Wait if cnode is being created, attached to or reclaimed.
 145          */
 146         if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT))
 147         {
 148             hfs_chash_wait(hfsmp, cp);
 149             goto loop_with_lock;
 150         }
 151
 152         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 153         if (vp == NULL)
 154         {
 155             /*
 156              * The desired vnode isn't there so tag the cnode.
 157              */
 158             SET(cp->c_hflag, H_ATTACH);
 159             *hflags |= H_ATTACH;
 160         }
 161
 162         if (ncp)
 163         {
 164             /*
 165              * someone else won the race to create
 166              * this cnode and add it to the hash
 167              * just dump our allocation
 168              */
 169             hfs_free(ncp);
 170             ncp = NULL;
 171         }
 172
 173         if (!skiplock)
 174         {
 175             if (hfs_lock(cp, HFS_TRY_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS))
 176             {
 177                 SET(cp->c_hflag, H_WAITING);
 178                 hfs_chash_broadcast_and_unlock(hfsmp,cp);
 179                 usleep(100);
 180                 goto loop;
 181             }
 182         }
 183         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 184
 185         /*
 186          * Skip cnodes that are not in the name space anymore
 187          * we need to check with the cnode lock held because
 188          * we may have blocked acquiring the vnode ref or the
 189          * lock on the cnode which would allow the node to be
 190          * unlinked.
 191          *
 192          * Don't return a cnode in this case since the inum
 193          * is no longer valid for lookups.
 194          */
 195         if (((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) ||
 196             ((vp != NULL) &&
 197             ((cp->uOpenLookupRefCount == 0) ||
 198             (vp->uValidNodeMagic1 == VALID_NODE_BADMAGIC) ||
 199             (vp->uValidNodeMagic2 == VALID_NODE_BADMAGIC))))
 200         {
 201             int renamed = 0;
 202             if (cp->c_flag & C_RENAMED)
 203                 renamed = 1;
 204             if (!skiplock)
 205             {
 206                 hfs_unlock(cp);
 207             }
 208
 209             if (vp != NULL)
 210             {
 211                 vnode_rele(vp);
 212             }
 213             else
 214             {
 215                 hfs_chashwakeup(hfsmp, cp, H_ATTACH);
 216                 *hflags &= ~H_ATTACH;
 217             }
 218
 219             vp = NULL;
 220             cp = NULL;
 221             if (renamed)
 222             {
 223                 *out_flags = GNV_CHASH_RENAMED;
 224             }
 225         }
 226
 227         if (cp) hfs_chash_raise_OpenLookupCounter(cp);
 228         hfs_chash_broadcast_and_unlock(hfsmp,cp);
 229         *vpp = vp;
 230         return (cp);
 231     }
 232
 233     /*
 234      * Allocate a new cnode
 235      */
 236     if (skiplock && !wantrsrc)
 237     {
 238         LFHFS_LOG(LEVEL_ERROR, "hfs_chash_getcnode: should never get here when skiplock is set \n");
 239         hfs_assert(0);
 240     }
 241
 242     if (ncp == NULL)
 243     {
 244         hfs_chash_unlock(hfsmp);
 245
 246         ncp = hfs_mallocz(sizeof(struct cnode));
 247         if (ncp == NULL)
 248         {
 249             return ncp;
 250         }
 251         /*
 252          * since we dropped the chash lock,
 253          * we need to go back and re-verify
 254          * that this node hasn't come into
 255          * existence...
 256          */
 257         goto loop;
 258     }
 259
 260     bzero(ncp, sizeof(*ncp));
 261
 262     SET(ncp->c_hflag, H_ALLOC);
 263     *hflags |= H_ALLOC;
 264     ncp->c_fileid = (cnid_t) inum;
 265     TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
 266     TAILQ_INIT(&ncp->c_originlist);
 267
 268     lf_lck_rw_init(&ncp->c_rwlock);
 269     lf_cond_init(&ncp->c_cacsh_cond);
 270
 271     if (!skiplock)
 272     {
 273         (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT);
 274     }
 275
 276     /* Insert the new cnode with it's H_ALLOC flag set */
 277     LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash);
 278     hfs_chash_raise_OpenLookupCounter(ncp);
 279     hfs_chash_unlock(hfsmp);
 280     *vpp = NULL;
 281     return (ncp);
 282 }
 283
 284 void
 285 hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags)
 286 {
 287     hfs_chash_lock_spin(hfsmp);
 288
 289     CLR(cp->c_hflag, hflags);
 290
 291     if (ISSET(cp->c_hflag, H_WAITING)) {
 292         CLR(cp->c_hflag, H_WAITING);
 293         pthread_cond_broadcast(&cp->c_cacsh_cond);
 294     }
 295
 296     hfs_chash_unlock(hfsmp);
 297 }
 298
 299 /*
 300  * Remove a cnode from the hash table and wakeup any waiters.
 301  */
 302 void
 303 hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp)
 304 {
 305     hfs_chash_lock_spin(hfsmp);
 306
 307     LIST_REMOVE(cp, c_hash);
 308     cp->c_hash.le_next = NULL;
 309     cp->c_hash.le_prev = NULL;
 310
 311     CLR(cp->c_hflag, H_ATTACH | H_ALLOC);
 312     if (ISSET(cp->c_hflag, H_WAITING))
 313     {
 314         CLR(cp->c_hflag, H_WAITING);
 315         pthread_cond_broadcast(&cp->c_cacsh_cond);
 316     }
 317     hfs_chash_unlock(hfsmp);
 318 }
 319
 320 /*
 321  * Use the device, inum pair to find the incore cnode.
 322  *
 323  * If it is in core, but locked, wait for it.
 324  */
 325 struct vnode *
 326 hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock, int allow_deleted)
 327 {
 328     struct cnode *cp;
 329     struct vnode *vp;
 330
 331     /*
 332      * Go through the hash list
 333      * If a cnode is in the process of being cleaned out or being
 334      * allocated, wait for it to be finished and then try again.
 335      */
 336 loop:
 337     hfs_chash_lock_spin(hfsmp);
 338
 339     for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 340         if (cp->c_fileid != inum)
 341             continue;
 342         /* Wait if cnode is being created or reclaimed. */
 343         if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 344             SET(cp->c_hflag, H_WAITING);
 345             hfs_chash_broadcast_and_unlock(hfsmp,cp);
 346             usleep(100);
 347             goto loop;
 348         }
 349         /* Obtain the desired vnode. */
 350         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 351         if (vp == NULL)
 352         {
 353             goto exit;
 354         }
 355
 356         if (!skiplock)
 357         {
 358             if (hfs_lock(cp, HFS_TRY_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS))
 359             {
 360                 SET(cp->c_hflag, H_WAITING);
 361                 hfs_chash_broadcast_and_unlock(hfsmp,cp);
 362                 usleep(100);
 363                 goto loop;
 364             }
 365         }
 366         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 367
 368         /*
 369          * Skip cnodes that are not in the name space anymore
 370          * we need to check with the cnode lock held because
 371          * we may have blocked acquiring the vnode ref or the
 372          * lock on the cnode which would allow the node to be
 373          * unlinked
 374          */
 375         if (!allow_deleted) {
 376             if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
 377                 if (!skiplock) hfs_unlock(cp);
 378                 goto exit;
 379             }
 380         }
 381
 382         hfs_chash_raise_OpenLookupCounter(cp);
 383         hfs_chash_broadcast_and_unlock(hfsmp,cp);
 384         return (vp);
 385     }
 386 exit:
 387     hfs_chash_unlock(hfsmp);
 388     return (NULL);
 389 }
 390
 391 int
 392 hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int existence_only,
 393                 int (*callout)(const cnode_t *cp, void *), void * arg)
 394 {
 395     struct cnode *cp;
 396     int result = ENOENT;
 397
 398     /*
 399      * Go through the hash list
 400      * If a cnode is in the process of being cleaned out or being
 401      * allocated, wait for it to be finished and then try again.
 402      */
 403     hfs_chash_lock(hfsmp);
 404
 405     for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 406         if (cp->c_fileid != inum)
 407             continue;
 408
 409         /*
 410          * Under normal circumstances, we would want to return ENOENT if a cnode is in
 411          * the hash and it is marked C_NOEXISTS or C_DELETED.  However, if the CNID
 412          * namespace has wrapped around, then we have the possibility of collisions.
 413          * In that case, we may use this function to validate whether or not we
 414          * should trust the nextCNID value in the hfs mount point.
 415          *
 416          * If we didn't do this, then it would be possible for a cnode that is no longer backed
 417          * by anything on-disk (C_NOEXISTS) to still exist in the hash along with its
 418          * vnode.  The cat_create routine could then create a new entry in the catalog
 419          * re-using that CNID.  Then subsequent hfs_getnewvnode calls will repeatedly fail
 420          * trying to look it up/validate it because it is marked C_NOEXISTS.  So we want
 421          * to prevent that from happening as much as possible.
 422          */
 423         if (existence_only) {
 424             result = 0;
 425             break;
 426         }
 427
 428         /* Skip cnodes that have been removed from the catalog */
 429         if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
 430             result = EACCES;
 431             break;
 432         }
 433
 434         /* Skip cnodes being created or reclaimed. */
 435         if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 436             result = callout(cp, arg);
 437         }
 438         break;
 439     }
 440     hfs_chash_unlock(hfsmp);
 441
 442     return (result);
 443 }
 444
 445 /* Search a cnode in the hash.  This function does not return cnode which
 446  * are getting created, destroyed or in transition.  Note that this function
 447  * does not acquire the cnode hash mutex, and expects the caller to acquire it.
 448  * On success, returns pointer to the cnode found.  On failure, returns NULL.
 449  */
 450 static
 451 struct cnode *
 452 hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid)
 453 {
 454     struct cnode *cp;
 455
 456     for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
 457         if (cp->c_fileid == cnid) {
 458             break;
 459         }
 460     }
 461
 462     /* If cnode is being created or reclaimed, return error. */
 463     if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 464         cp = NULL;
 465     }
 466
 467     return cp;
 468 }
 469
 470 /* Search a cnode corresponding to given device and ID in the hash.  If the
 471  * found cnode has kHFSHasChildLinkBit cleared, set it.  If the cnode is not
 472  * found, no new cnode is created and error is returned.
 473  *
 474  * Return values -
 475  *    -1 : The cnode was not found.
 476  *      0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
 477  *     1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
 478  *         function had to set that bit.
 479  */
 480 int
 481 hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid)
 482 {
 483     int retval = -1;
 484     struct cnode *cp;
 485
 486     hfs_chash_lock_spin(hfsmp);
 487
 488     cp = hfs_chash_search_cnid(hfsmp, cnid);
 489     if (cp) {
 490         if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
 491             retval = 0;
 492         } else {
 493             cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
 494             retval = 1;
 495         }
 496     }
 497     hfs_chash_unlock(hfsmp);
 498
 499     return retval;
 500 }
 501
 502 /*
 503  * Remove a cnode from the hash table.
 504  * Need to lock cache from caller
 505  */
 506 int
 507 hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp)
 508 {
 509     hfs_chash_lock_spin(hfsmp);
 510
 511     /* Check if a vnode is getting attached */
 512     if (ISSET(cp->c_hflag, H_ATTACH)) {
 513         hfs_chash_unlock(hfsmp);
 514         return (EBUSY);
 515     }
 516     if (cp->c_hash.le_next || cp->c_hash.le_prev) {
 517         LIST_REMOVE(cp, c_hash);
 518         cp->c_hash.le_next = NULL;
 519         cp->c_hash.le_prev = NULL;
 520     }
 521
 522     hfs_chash_unlock(hfsmp);
 523
 524     return (0);
 525 }
 526
 527 /*
 528  * mark a cnode as in transition
 529  */
 530 void
 531 hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp)
 532 {
 533     hfs_chash_lock_spin(hfsmp);
 534
 535     SET(cp->c_hflag, H_TRANSIT);
 536
 537     hfs_chash_unlock(hfsmp);
 538 }