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             (cp->uOpenLookupRefCount == 0) ||
 197             (vp->uValidNodeMagic1 == VALID_NODE_BADMAGIC) ||
 198             (vp->uValidNodeMagic2 == VALID_NODE_BADMAGIC))
 199         {
 200             int renamed = 0;
 201             if (cp->c_flag & C_RENAMED)
 202                 renamed = 1;
 203             if (!skiplock)
 204             {
 205                 hfs_unlock(cp);
 206             }
 207
 208             if (vp != NULL)
 209             {
 210                 vnode_rele(vp);
 211             }
 212             else
 213             {
 214                 hfs_chashwakeup(hfsmp, cp, H_ATTACH);
 215                 *hflags &= ~H_ATTACH;
 216             }
 217
 218             vp = NULL;
 219             cp = NULL;
 220             if (renamed)
 221             {
 222                 *out_flags = GNV_CHASH_RENAMED;
 223             }
 224         }
 225
 226         if (cp) hfs_chash_raise_OpenLookupCounter(cp);
 227         hfs_chash_broadcast_and_unlock(hfsmp,cp);
 228         *vpp = vp;
 229         return (cp);
 230     }
 231
 232     /*
 233      * Allocate a new cnode
 234      */
 235     if (skiplock && !wantrsrc)
 236     {
 237         LFHFS_LOG(LEVEL_ERROR, "hfs_chash_getcnode: should never get here when skiplock is set \n");
 238         hfs_assert(0);
 239     }
 240
 241     if (ncp == NULL)
 242     {
 243         hfs_chash_unlock(hfsmp);
 244
 245         ncp = hfs_mallocz(sizeof(struct cnode));
 246         if (ncp == NULL)
 247         {
 248             return ncp;
 249         }
 250         /*
 251          * since we dropped the chash lock,
 252          * we need to go back and re-verify
 253          * that this node hasn't come into
 254          * existence...
 255          */
 256         goto loop;
 257     }
 258
 259     bzero(ncp, sizeof(*ncp));
 260
 261     SET(ncp->c_hflag, H_ALLOC);
 262     *hflags |= H_ALLOC;
 263     ncp->c_fileid = (cnid_t) inum;
 264     TAILQ_INIT(&ncp->c_hintlist); /* make the list empty */
 265     TAILQ_INIT(&ncp->c_originlist);
 266
 267     lf_lck_rw_init(&ncp->c_rwlock);
 268     lf_cond_init(&ncp->c_cacsh_cond);
 269
 270     if (!skiplock)
 271     {
 272         (void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT);
 273     }
 274
 275     /* Insert the new cnode with it's H_ALLOC flag set */
 276     LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash);
 277     hfs_chash_raise_OpenLookupCounter(ncp);
 278     hfs_chash_unlock(hfsmp);
 279     *vpp = NULL;
 280     return (ncp);
 281 }
 282
 283 void
 284 hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags)
 285 {
 286     hfs_chash_lock_spin(hfsmp);
 287
 288     CLR(cp->c_hflag, hflags);
 289
 290     if (ISSET(cp->c_hflag, H_WAITING)) {
 291         CLR(cp->c_hflag, H_WAITING);
 292         pthread_cond_broadcast(&cp->c_cacsh_cond);
 293     }
 294
 295     hfs_chash_unlock(hfsmp);
 296 }
 297
 298 /*
 299  * Remove a cnode from the hash table and wakeup any waiters.
 300  */
 301 void
 302 hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp)
 303 {
 304     hfs_chash_lock_spin(hfsmp);
 305
 306     LIST_REMOVE(cp, c_hash);
 307     cp->c_hash.le_next = NULL;
 308     cp->c_hash.le_prev = NULL;
 309
 310     CLR(cp->c_hflag, H_ATTACH | H_ALLOC);
 311     if (ISSET(cp->c_hflag, H_WAITING))
 312     {
 313         CLR(cp->c_hflag, H_WAITING);
 314         pthread_cond_broadcast(&cp->c_cacsh_cond);
 315     }
 316     hfs_chash_unlock(hfsmp);
 317 }
 318
 319 /*
 320  * Use the device, inum pair to find the incore cnode.
 321  *
 322  * If it is in core, but locked, wait for it.
 323  */
 324 struct vnode *
 325 hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock, int allow_deleted)
 326 {
 327     struct cnode *cp;
 328     struct vnode *vp;
 329
 330     /*
 331      * Go through the hash list
 332      * If a cnode is in the process of being cleaned out or being
 333      * allocated, wait for it to be finished and then try again.
 334      */
 335 loop:
 336     hfs_chash_lock_spin(hfsmp);
 337
 338     for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 339         if (cp->c_fileid != inum)
 340             continue;
 341         /* Wait if cnode is being created or reclaimed. */
 342         if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 343             SET(cp->c_hflag, H_WAITING);
 344             hfs_chash_broadcast_and_unlock(hfsmp,cp);
 345             usleep(100);
 346             goto loop;
 347         }
 348         /* Obtain the desired vnode. */
 349         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 350         if (vp == NULL)
 351         {
 352             goto exit;
 353         }
 354
 355         if (!skiplock)
 356         {
 357             if (hfs_lock(cp, HFS_TRY_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS))
 358             {
 359                 SET(cp->c_hflag, H_WAITING);
 360                 hfs_chash_broadcast_and_unlock(hfsmp,cp);
 361                 usleep(100);
 362                 goto loop;
 363             }
 364         }
 365         vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
 366
 367         /*
 368          * Skip cnodes that are not in the name space anymore
 369          * we need to check with the cnode lock held because
 370          * we may have blocked acquiring the vnode ref or the
 371          * lock on the cnode which would allow the node to be
 372          * unlinked
 373          */
 374         if (!allow_deleted) {
 375             if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
 376                 if (!skiplock) hfs_unlock(cp);
 377                 goto exit;
 378             }
 379         }
 380
 381         hfs_chash_raise_OpenLookupCounter(cp);
 382         hfs_chash_broadcast_and_unlock(hfsmp,cp);
 383         return (vp);
 384     }
 385 exit:
 386     hfs_chash_unlock(hfsmp);
 387     return (NULL);
 388 }
 389
 390 int
 391 hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int existence_only,
 392                 int (*callout)(const cnode_t *cp, void *), void * arg)
 393 {
 394     struct cnode *cp;
 395     int result = ENOENT;
 396
 397     /*
 398      * Go through the hash list
 399      * If a cnode is in the process of being cleaned out or being
 400      * allocated, wait for it to be finished and then try again.
 401      */
 402     hfs_chash_lock(hfsmp);
 403
 404     for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
 405         if (cp->c_fileid != inum)
 406             continue;
 407
 408         /*
 409          * Under normal circumstances, we would want to return ENOENT if a cnode is in
 410          * the hash and it is marked C_NOEXISTS or C_DELETED.  However, if the CNID
 411          * namespace has wrapped around, then we have the possibility of collisions.
 412          * In that case, we may use this function to validate whether or not we
 413          * should trust the nextCNID value in the hfs mount point.
 414          *
 415          * If we didn't do this, then it would be possible for a cnode that is no longer backed
 416          * by anything on-disk (C_NOEXISTS) to still exist in the hash along with its
 417          * vnode.  The cat_create routine could then create a new entry in the catalog
 418          * re-using that CNID.  Then subsequent hfs_getnewvnode calls will repeatedly fail
 419          * trying to look it up/validate it because it is marked C_NOEXISTS.  So we want
 420          * to prevent that from happening as much as possible.
 421          */
 422         if (existence_only) {
 423             result = 0;
 424             break;
 425         }
 426
 427         /* Skip cnodes that have been removed from the catalog */
 428         if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
 429             result = EACCES;
 430             break;
 431         }
 432
 433         /* Skip cnodes being created or reclaimed. */
 434         if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 435             result = callout(cp, arg);
 436         }
 437         break;
 438     }
 439     hfs_chash_unlock(hfsmp);
 440
 441     return (result);
 442 }
 443
 444 /* Search a cnode in the hash.  This function does not return cnode which
 445  * are getting created, destroyed or in transition.  Note that this function
 446  * does not acquire the cnode hash mutex, and expects the caller to acquire it.
 447  * On success, returns pointer to the cnode found.  On failure, returns NULL.
 448  */
 449 static
 450 struct cnode *
 451 hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid)
 452 {
 453     struct cnode *cp;
 454
 455     for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
 456         if (cp->c_fileid == cnid) {
 457             break;
 458         }
 459     }
 460
 461     /* If cnode is being created or reclaimed, return error. */
 462     if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
 463         cp = NULL;
 464     }
 465
 466     return cp;
 467 }
 468
 469 /* Search a cnode corresponding to given device and ID in the hash.  If the
 470  * found cnode has kHFSHasChildLinkBit cleared, set it.  If the cnode is not
 471  * found, no new cnode is created and error is returned.
 472  *
 473  * Return values -
 474  *    -1 : The cnode was not found.
 475  *      0 : The cnode was found, and the kHFSHasChildLinkBit was already set.
 476  *     1 : The cnode was found, the kHFSHasChildLinkBit was not set, and the
 477  *         function had to set that bit.
 478  */
 479 int
 480 hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid)
 481 {
 482     int retval = -1;
 483     struct cnode *cp;
 484
 485     hfs_chash_lock_spin(hfsmp);
 486
 487     cp = hfs_chash_search_cnid(hfsmp, cnid);
 488     if (cp) {
 489         if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
 490             retval = 0;
 491         } else {
 492             cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
 493             retval = 1;
 494         }
 495     }
 496     hfs_chash_unlock(hfsmp);
 497
 498     return retval;
 499 }
 500
 501 /*
 502  * Remove a cnode from the hash table.
 503  * Need to lock cache from caller
 504  */
 505 int
 506 hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp)
 507 {
 508     hfs_chash_lock_spin(hfsmp);
 509
 510     /* Check if a vnode is getting attached */
 511     if (ISSET(cp->c_hflag, H_ATTACH)) {
 512         hfs_chash_unlock(hfsmp);
 513         return (EBUSY);
 514     }
 515     if (cp->c_hash.le_next || cp->c_hash.le_prev) {
 516         LIST_REMOVE(cp, c_hash);
 517         cp->c_hash.le_next = NULL;
 518         cp->c_hash.le_prev = NULL;
 519     }
 520
 521     hfs_chash_unlock(hfsmp);
 522
 523     return (0);
 524 }
 525
 526 /*
 527  * mark a cnode as in transition
 528  */
 529 void
 530 hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp)
 531 {
 532     hfs_chash_lock_spin(hfsmp);
 533
 534     SET(cp->c_hflag, H_TRANSIT);
 535
 536     hfs_chash_unlock(hfsmp);
 537 }