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