sys/vfs/hammer2/hammer2_cluster.c

   1 /*
   2  * Copyright (c) 2013-2014 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@dragonflybsd.org>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 /*
  35  * The cluster module collects multiple chains representing the same
  36  * information into a single entity.  It allows direct access to media
  37  * data as long as it is not blockref array data.  Meaning, basically,
  38  * just inode and file data.
  39  *
  40  * This module also handles I/O dispatch, status rollup, and various
  41  * mastership arrangements including quorum operations.  It effectively
  42  * presents one topology to the vnops layer.
  43  *
  44  * Many of the API calls mimic chain API calls but operate on clusters
  45  * instead of chains.  Please see hammer2_chain.c for more complete code
  46  * documentation of the API functions.
  47  */
  48 #include <sys/cdefs.h>
  49 #include <sys/param.h>
  50 #include <sys/systm.h>
  51 #include <sys/types.h>
  52 #include <sys/lock.h>
  53 #include <sys/uuid.h>
  54
  55 #include "hammer2.h"
  56
  57 /*
  58  * Returns TRUE if any chain in the cluster needs to be resized.
  59  */
  60 int
  61 hammer2_cluster_need_resize(hammer2_cluster_t *cluster, int bytes)
  62 {
  63         hammer2_chain_t *chain;
  64         int i;
  65
  66         for (i = 0; i < cluster->nchains; ++i) {
  67                 chain = cluster->array[i];
  68                 if (chain && chain->bytes != bytes)
  69                         return 1;
  70         }
  71         return 0;
  72 }
  73
  74 uint8_t
  75 hammer2_cluster_type(hammer2_cluster_t *cluster)
  76 {
  77         return(cluster->focus->bref.type);
  78 }
  79
  80 /*
  81  * NOTE: When modifying a cluster object via hammer2_cluster_wdata()
  82  *       and hammer2_cluster_modsync(), remember that block array
  83  *       entries are not copied to the elements of the cluster.
  84  */
  85 const hammer2_media_data_t *
  86 hammer2_cluster_data(hammer2_cluster_t *cluster)
  87 {
  88         return(cluster->focus->data);
  89 }
  90
  91 hammer2_media_data_t *
  92 hammer2_cluster_wdata(hammer2_cluster_t *cluster)
  93 {
  94         return(cluster->focus->data);
  95 }
  96
  97 int
  98 hammer2_cluster_modified(hammer2_cluster_t *cluster)
  99 {
 100         return((cluster->focus->flags & HAMMER2_CHAIN_MODIFIED) != 0);
 101 }
 102
 103 /*
 104  * Return a bref representative of the cluster.  Any data offset is removed
 105  * (since it would only be applicable to a particular chain in the cluster).
 106  *
 107  * However, the radix portion of data_off is used for many purposes and will
 108  * be retained.
 109  */
 110 void
 111 hammer2_cluster_bref(hammer2_cluster_t *cluster, hammer2_blockref_t *bref)
 112 {
 113         *bref = cluster->focus->bref;
 114         bref->data_off &= HAMMER2_OFF_MASK_RADIX;
 115 }
 116
 117 void
 118 hammer2_cluster_set_chainflags(hammer2_cluster_t *cluster, uint32_t flags)
 119 {
 120         hammer2_chain_t *chain;
 121         int i;
 122
 123         for (i = 0; i < cluster->nchains; ++i) {
 124                 chain = cluster->array[i];
 125                 if (chain)
 126                         atomic_set_int(&chain->flags, flags);
 127         }
 128 }
 129
 130 void
 131 hammer2_cluster_setflush(hammer2_trans_t *trans, hammer2_cluster_t *cluster)
 132 {
 133         hammer2_chain_t *chain;
 134         int i;
 135
 136         for (i = 0; i < cluster->nchains; ++i) {
 137                 chain = cluster->array[i];
 138                 if (chain)
 139                         hammer2_chain_setflush(trans, chain);
 140         }
 141 }
 142
 143 void
 144 hammer2_cluster_setmethod_check(hammer2_trans_t *trans,
 145                                 hammer2_cluster_t *cluster,
 146                                 int check_algo)
 147 {
 148         hammer2_chain_t *chain;
 149         int i;
 150
 151         for (i = 0; i < cluster->nchains; ++i) {
 152                 chain = cluster->array[i];
 153                 if (chain) {
 154                         KKASSERT(chain->flags & HAMMER2_CHAIN_MODIFIED);
 155                         chain->bref.methods &= ~HAMMER2_ENC_CHECK(-1);
 156                         chain->bref.methods |= HAMMER2_ENC_CHECK(check_algo);
 157                 }
 158         }
 159 }
 160
 161 /*
 162  * Create a cluster with one ref from the specified chain.  The chain
 163  * is not further referenced.  The caller typically supplies a locked
 164  * chain and transfers ownership to the cluster.
 165  */
 166 hammer2_cluster_t *
 167 hammer2_cluster_from_chain(hammer2_chain_t *chain)
 168 {
 169         hammer2_cluster_t *cluster;
 170
 171         cluster = kmalloc(sizeof(*cluster), M_HAMMER2, M_WAITOK | M_ZERO);
 172         cluster->array[0] = chain;
 173         cluster->nchains = 1;
 174         cluster->focus = chain;
 175         cluster->pmp = chain->pmp;
 176         cluster->refs = 1;
 177
 178         return cluster;
 179 }
 180
 181 /*
 182  * Allocates a cluster and its underlying chain structures.  The underlying
 183  * chains will be locked.  The cluster and underlying chains will have one
 184  * ref.
 185  */
 186 hammer2_cluster_t *
 187 hammer2_cluster_alloc(hammer2_pfsmount_t *pmp,
 188                       hammer2_trans_t *trans, hammer2_blockref_t *bref)
 189 {
 190         hammer2_cluster_t *cluster;
 191         hammer2_cluster_t *rcluster;
 192         hammer2_chain_t *chain;
 193 #if 0
 194         u_int bytes = 1U << (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
 195 #endif
 196         int i;
 197
 198         KKASSERT(pmp != NULL);
 199
 200         /*
 201          * Construct the appropriate system structure.
 202          */
 203         switch(bref->type) {
 204         case HAMMER2_BREF_TYPE_INODE:
 205         case HAMMER2_BREF_TYPE_INDIRECT:
 206         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 207         case HAMMER2_BREF_TYPE_DATA:
 208         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 209                 /*
 210                  * Chain's are really only associated with the hmp but we
 211                  * maintain a pmp association for per-mount memory tracking
 212                  * purposes.  The pmp can be NULL.
 213                  */
 214                 break;
 215         case HAMMER2_BREF_TYPE_VOLUME:
 216         case HAMMER2_BREF_TYPE_FREEMAP:
 217                 chain = NULL;
 218                 panic("hammer2_cluster_alloc volume type illegal for op");
 219         default:
 220                 chain = NULL;
 221                 panic("hammer2_cluster_alloc: unrecognized blockref type: %d",
 222                       bref->type);
 223         }
 224
 225         cluster = kmalloc(sizeof(*cluster), M_HAMMER2, M_WAITOK | M_ZERO);
 226         cluster->refs = 1;
 227
 228         rcluster = &pmp->iroot->cluster;
 229         for (i = 0; i < rcluster->nchains; ++i) {
 230                 chain = hammer2_chain_alloc(rcluster->array[i]->hmp,
 231                                             pmp, trans, bref);
 232 #if 0
 233                 chain->hmp = rcluster->array[i]->hmp;
 234                 chain->bref = *bref;
 235                 chain->bytes = bytes;
 236                 chain->refs = 1;
 237                 chain->flags = HAMMER2_CHAIN_ALLOCATED;
 238 #endif
 239
 240                 /*
 241                  * NOTE: When loading a chain from backing store or creating a
 242                  *       snapshot, trans will be NULL and the caller is
 243                  *       responsible for setting these fields.
 244                  */
 245                 cluster->array[i] = chain;
 246         }
 247         cluster->nchains = i;
 248         cluster->pmp = pmp;
 249         cluster->focus = cluster->array[0];
 250
 251         return (cluster);
 252 }
 253
 254 /*
 255  * Add a reference to a cluster.
 256  *
 257  * We must also ref the underlying chains in order to allow ref/unlock
 258  * sequences to later re-lock.
 259  */
 260 void
 261 hammer2_cluster_ref(hammer2_cluster_t *cluster)
 262 {
 263         hammer2_chain_t *chain;
 264         int i;
 265
 266         atomic_add_int(&cluster->refs, 1);
 267         for (i = 0; i < cluster->nchains; ++i) {
 268                 chain = cluster->array[i];
 269                 if (chain)
 270                         hammer2_chain_ref(chain);
 271         }
 272 }
 273
 274 /*
 275  * Drop the caller's reference to the cluster.  When the ref count drops to
 276  * zero this function frees the cluster and drops all underlying chains.
 277  */
 278 void
 279 hammer2_cluster_drop(hammer2_cluster_t *cluster)
 280 {
 281         hammer2_chain_t *chain;
 282         int i;
 283
 284         KKASSERT(cluster->refs > 0);
 285         for (i = 0; i < cluster->nchains; ++i) {
 286                 chain = cluster->array[i];
 287                 if (chain) {
 288                         hammer2_chain_drop(chain);
 289                         if (cluster->refs == 1)
 290                                 cluster->array[i] = NULL;
 291                 }
 292         }
 293         if (atomic_fetchadd_int(&cluster->refs, -1) == 1) {
 294                 cluster->focus = NULL;
 295                 kfree(cluster, M_HAMMER2);
 296                 /* cluster = NULL; safety */
 297         }
 298 }
 299
 300 void
 301 hammer2_cluster_wait(hammer2_cluster_t *cluster)
 302 {
 303         tsleep(cluster->focus, 0, "h2clcw", 1);
 304 }
 305
 306 /*
 307  * Lock and ref a cluster.  This adds a ref to the cluster and its chains
 308  * and then locks them.
 309  */
 310 int
 311 hammer2_cluster_lock(hammer2_cluster_t *cluster, int how)
 312 {
 313         hammer2_chain_t *chain;
 314         int i;
 315         int error;
 316
 317         error = 0;
 318         atomic_add_int(&cluster->refs, 1);
 319         for (i = 0; i < cluster->nchains; ++i) {
 320                 chain = cluster->array[i];
 321                 if (chain) {
 322                         error = hammer2_chain_lock(chain, how);
 323                         if (error) {
 324                                 while (--i >= 0)
 325                                         hammer2_chain_unlock(cluster->array[i]);
 326                                 atomic_add_int(&cluster->refs, -1);
 327                                 break;
 328                         }
 329                 }
 330         }
 331         return error;
 332 }
 333
 334 /*
 335  * Replace the contents of dst with src, adding a reference to src's chains.
 336  * dst is assumed to already have a ref and any chains present in dst are
 337  * assumed to be locked and will be unlocked.
 338  *
 339  * If the chains in src are locked, only one of (src) or (dst) should be
 340  * considered locked by the caller after return, not both.
 341  */
 342 void
 343 hammer2_cluster_replace(hammer2_cluster_t *dst, hammer2_cluster_t *src)
 344 {
 345         hammer2_chain_t *chain;
 346         int i;
 347
 348         KKASSERT(dst->refs == 1);
 349         dst->focus = NULL;
 350
 351         for (i = 0; i < src->nchains; ++i) {
 352                 chain = src->array[i];
 353                 if (chain) {
 354                         hammer2_chain_ref(chain);
 355                         if (i < dst->nchains && dst->array[i])
 356                                 hammer2_chain_unlock(dst->array[i]);
 357                         dst->array[i] = chain;
 358                         if (dst->focus == NULL)
 359                                 dst->focus = chain;
 360                 }
 361         }
 362         while (i < dst->nchains) {
 363                 chain = dst->array[i];
 364                 if (chain) {
 365                         hammer2_chain_unlock(chain);
 366                         dst->array[i] = NULL;
 367                 }
 368                 ++i;
 369         }
 370         dst->nchains = src->nchains;
 371 }
 372
 373 /*
 374  * Replace the contents of the locked destination with the contents of the
 375  * locked source.  Destination must have one ref.
 376  *
 377  * Returns with the destination still with one ref and the copied chains
 378  * with an additional lock (representing their state on the destination).
 379  * The original chains associated with the destination are unlocked.
 380  */
 381 void
 382 hammer2_cluster_replace_locked(hammer2_cluster_t *dst, hammer2_cluster_t *src)
 383 {
 384         hammer2_chain_t *chain;
 385         int i;
 386
 387         KKASSERT(dst->refs == 1);
 388
 389         dst->focus = NULL;
 390         for (i = 0; i < src->nchains; ++i) {
 391                 chain = src->array[i];
 392                 if (chain) {
 393                         hammer2_chain_lock(chain, 0);
 394                         if (i < dst->nchains && dst->array[i])
 395                                 hammer2_chain_unlock(dst->array[i]);
 396                         dst->array[i] = src->array[i];
 397                         if (dst->focus == NULL)
 398                                 dst->focus = chain;
 399                 }
 400         }
 401         while (i < dst->nchains) {
 402                 chain = dst->array[i];
 403                 if (chain) {
 404                         hammer2_chain_unlock(chain);
 405                         dst->array[i] = NULL;
 406                 }
 407                 ++i;
 408         }
 409         dst->nchains = src->nchains;
 410 }
 411
 412 /*
 413  * Copy a cluster, returned a ref'd cluster.  All underlying chains
 414  * are also ref'd, but not locked.
 415  *
 416  * If HAMMER2_CLUSTER_COPY_CHAINS is specified, the chains are copied
 417  * to the new cluster and a reference is nominally added to them and to
 418  * the cluster.  The cluster will have 1 ref.
 419  *
 420  * If HAMMER2_CLUSTER_COPY_NOREF is specified along with CHAINS, the chains
 421  * are copied but no additional references are made and the cluster will have
 422  * 0 refs.  Callers must ref the cluster and the chains before dropping it
 423  * (typically by locking it).
 424  *
 425  * If flags are passed as 0 the copy is setup as if it contained the chains
 426  * but the chains will not be copied over, and the cluster will have 0 refs.
 427  * Callers must ref the cluster before dropping it (typically by locking it).
 428  */
 429 hammer2_cluster_t *
 430 hammer2_cluster_copy(hammer2_cluster_t *ocluster, int copy_flags)
 431 {
 432         hammer2_pfsmount_t *pmp = ocluster->pmp;
 433         hammer2_cluster_t *ncluster;
 434         hammer2_chain_t *chain;
 435         int i;
 436
 437         ncluster = kmalloc(sizeof(*ncluster), M_HAMMER2, M_WAITOK | M_ZERO);
 438         ncluster->pmp = pmp;
 439         ncluster->nchains = ocluster->nchains;
 440         ncluster->refs = (copy_flags & HAMMER2_CLUSTER_COPY_NOREF) ? 0 : 1;
 441         if ((copy_flags & HAMMER2_CLUSTER_COPY_NOCHAINS) == 0) {
 442                 ncluster->focus = ocluster->focus;
 443                 for (i = 0; i < ocluster->nchains; ++i) {
 444                         chain = ocluster->array[i];
 445                         ncluster->array[i] = chain;
 446                         if ((copy_flags & HAMMER2_CLUSTER_COPY_NOREF) == 0 &&
 447                             chain) {
 448                                 hammer2_chain_ref(chain);
 449                         }
 450                 }
 451         }
 452         return (ncluster);
 453 }
 454
 455 /*
 456  * Unlock and deref a cluster.  The cluster is destroyed if this is the
 457  * last ref.
 458  */
 459 void
 460 hammer2_cluster_unlock(hammer2_cluster_t *cluster)
 461 {
 462         hammer2_chain_t *chain;
 463         int i;
 464
 465         KKASSERT(cluster->refs > 0);
 466         for (i = 0; i < cluster->nchains; ++i) {
 467                 chain = cluster->array[i];
 468                 if (chain) {
 469                         hammer2_chain_unlock(chain);
 470                         if (cluster->refs == 1)
 471                                 cluster->array[i] = NULL;       /* safety */
 472                 }
 473         }
 474         if (atomic_fetchadd_int(&cluster->refs, -1) == 1) {
 475                 cluster->focus = NULL;
 476                 kfree(cluster, M_HAMMER2);
 477                 /* cluster = NULL; safety */
 478         }
 479 }
 480
 481 /*
 482  * Resize the cluster's physical storage allocation in-place.  This may
 483  * replace the cluster's chains.
 484  */
 485 void
 486 hammer2_cluster_resize(hammer2_trans_t *trans, hammer2_inode_t *ip,
 487                        hammer2_cluster_t *cparent, hammer2_cluster_t *cluster,
 488                        int nradix, int flags)
 489 {
 490         int i;
 491
 492         KKASSERT(cparent->pmp == cluster->pmp);         /* can be NULL */
 493         KKASSERT(cparent->nchains == cluster->nchains);
 494
 495         cluster->focus = NULL;
 496         for (i = 0; i < cluster->nchains; ++i) {
 497                 if (cluster->array[i]) {
 498                         KKASSERT(cparent->array[i]);
 499                         hammer2_chain_resize(trans, ip,
 500                                              cparent->array[i],
 501                                              cluster->array[i],
 502                                              nradix, flags);
 503                         if (cluster->focus == NULL)
 504                                 cluster->focus = cluster->array[i];
 505                 }
 506         }
 507 }
 508
 509 /*
 510  * Set an inode's cluster modified, marking the related chains RW and
 511  * duplicating them if necessary.
 512  *
 513  * The passed-in chain is a localized copy of the chain previously acquired
 514  * when the inode was locked (and possilby replaced in the mean time), and
 515  * must also be updated.  In fact, we update it first and then synchronize
 516  * the inode's cluster cache.
 517  */
 518 hammer2_inode_data_t *
 519 hammer2_cluster_modify_ip(hammer2_trans_t *trans, hammer2_inode_t *ip,
 520                           hammer2_cluster_t *cluster, int flags)
 521 {
 522         atomic_set_int(&ip->flags, HAMMER2_INODE_MODIFIED);
 523         hammer2_cluster_modify(trans, cluster, flags);
 524
 525         hammer2_inode_repoint(ip, NULL, cluster);
 526         if (ip->vp)
 527                 vsetisdirty(ip->vp);
 528         return (&hammer2_cluster_wdata(cluster)->ipdata);
 529 }
 530
 531 /*
 532  * Adjust the cluster's chains to allow modification.
 533  */
 534 void
 535 hammer2_cluster_modify(hammer2_trans_t *trans, hammer2_cluster_t *cluster,
 536                        int flags)
 537 {
 538         int i;
 539
 540         cluster->focus = NULL;
 541         for (i = 0; i < cluster->nchains; ++i) {
 542                 if (cluster->array[i]) {
 543                         hammer2_chain_modify(trans, cluster->array[i], flags);
 544                         if (cluster->focus == NULL)
 545                                 cluster->focus = cluster->array[i];
 546                 }
 547         }
 548 }
 549
 550 /*
 551  * Synchronize modifications with other chains in a cluster.
 552  *
 553  * Nominal front-end operations only edit non-block-table data in a single
 554  * chain.  This code copies such modifications to the other chains in the
 555  * cluster.  Blocktable modifications are handled on a chain-by-chain basis
 556  * by both the frontend and the backend and will explode in fireworks if
 557  * blindly copied.
 558  */
 559 void
 560 hammer2_cluster_modsync(hammer2_cluster_t *cluster)
 561 {
 562         hammer2_chain_t *focus;
 563         hammer2_chain_t *scan;
 564         const hammer2_inode_data_t *ripdata;
 565         hammer2_inode_data_t *wipdata;
 566         int i;
 567
 568         focus = cluster->focus;
 569         KKASSERT(focus->flags & HAMMER2_CHAIN_MODIFIED);
 570
 571         for (i = 0; i < cluster->nchains; ++i) {
 572                 scan = cluster->array[i];
 573                 if (scan == NULL || scan == focus)
 574                         continue;
 575                 KKASSERT(scan->flags & HAMMER2_CHAIN_MODIFIED);
 576                 KKASSERT(focus->bytes == scan->bytes &&
 577                          focus->bref.type == scan->bref.type);
 578                 switch(focus->bref.type) {
 579                 case HAMMER2_BREF_TYPE_INODE:
 580                         ripdata = &focus->data->ipdata;
 581                         wipdata = &scan->data->ipdata;
 582                         if ((ripdata->op_flags &
 583                             HAMMER2_OPFLAG_DIRECTDATA) == 0) {
 584                                 bcopy(ripdata, wipdata,
 585                                       offsetof(hammer2_inode_data_t, u));
 586                                 break;
 587                         }
 588                         /* fall through */
 589                 case HAMMER2_BREF_TYPE_DATA:
 590                         bcopy(focus->data, scan->data, focus->bytes);
 591                         break;
 592                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 593                 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 594                 case HAMMER2_BREF_TYPE_FREEMAP:
 595                 case HAMMER2_BREF_TYPE_VOLUME:
 596                         panic("hammer2_cluster_modsync: illegal node type");
 597                         /* NOT REACHED */
 598                         break;
 599                 default:
 600                         panic("hammer2_cluster_modsync: unknown node type");
 601                         break;
 602                 }
 603         }
 604 }
 605
 606 /*
 607  * Lookup initialization/completion API
 608  */
 609 hammer2_cluster_t *
 610 hammer2_cluster_lookup_init(hammer2_cluster_t *cparent, int flags)
 611 {
 612         hammer2_cluster_t *cluster;
 613         int i;
 614
 615         cluster = kmalloc(sizeof(*cluster), M_HAMMER2, M_WAITOK | M_ZERO);
 616         cluster->pmp = cparent->pmp;                    /* can be NULL */
 617         /* cluster->focus = NULL; already null */
 618
 619         for (i = 0; i < cparent->nchains; ++i) {
 620                 cluster->array[i] = cparent->array[i];
 621                 if (cluster->focus == NULL)
 622                         cluster->focus = cluster->array[i];
 623         }
 624         cluster->nchains = cparent->nchains;
 625
 626         /*
 627          * Independently lock (this will also give cluster 1 ref)
 628          */
 629         if (flags & HAMMER2_LOOKUP_SHARED) {
 630                 hammer2_cluster_lock(cluster, HAMMER2_RESOLVE_ALWAYS |
 631                                               HAMMER2_RESOLVE_SHARED);
 632         } else {
 633                 hammer2_cluster_lock(cluster, HAMMER2_RESOLVE_ALWAYS);
 634         }
 635         return (cluster);
 636 }
 637
 638 void
 639 hammer2_cluster_lookup_done(hammer2_cluster_t *cparent)
 640 {
 641         if (cparent)
 642                 hammer2_cluster_unlock(cparent);
 643 }
 644
 645 /*
 646  * Locate first match or overlap under parent, return a new cluster
 647  */
 648 hammer2_cluster_t *
 649 hammer2_cluster_lookup(hammer2_cluster_t *cparent, hammer2_key_t *key_nextp,
 650                      hammer2_key_t key_beg, hammer2_key_t key_end,
 651                      int flags, int *ddflagp)
 652 {
 653         hammer2_pfsmount_t *pmp;
 654         hammer2_cluster_t *cluster;
 655         hammer2_chain_t *chain;
 656         hammer2_key_t key_accum;
 657         hammer2_key_t key_next;
 658         hammer2_key_t bref_key;
 659         int bref_keybits;
 660         int null_count;
 661         int ddflag;
 662         int i;
 663         uint8_t bref_type;
 664         u_int bytes;
 665
 666         pmp = cparent->pmp;                             /* can be NULL */
 667         key_accum = *key_nextp;
 668         null_count = 0;
 669         bref_type = 0;
 670         bref_key = 0;
 671         bref_keybits = 0;
 672         bytes = 0;
 673
 674         cluster = kmalloc(sizeof(*cluster), M_HAMMER2, M_WAITOK | M_ZERO);
 675         cluster->pmp = pmp;                             /* can be NULL */
 676         cluster->refs = 1;
 677         /* cluster->focus = NULL; already null */
 678         cparent->focus = NULL;
 679         *ddflagp = 0;
 680
 681         for (i = 0; i < cparent->nchains; ++i) {
 682                 key_next = *key_nextp;
 683                 if (cparent->array[i] == NULL) {
 684                         ++null_count;
 685                         continue;
 686                 }
 687                 chain = hammer2_chain_lookup(&cparent->array[i], &key_next,
 688                                              key_beg, key_end,
 689                                              &cparent->cache_index[i],
 690                                              flags, &ddflag);
 691                 if (cparent->focus == NULL)
 692                         cparent->focus = cparent->array[i];
 693                 cluster->array[i] = chain;
 694                 if (chain == NULL) {
 695                         ++null_count;
 696                 } else {
 697                         if (cluster->focus == NULL) {
 698                                 bref_type = chain->bref.type;
 699                                 bref_key = chain->bref.key;
 700                                 bref_keybits = chain->bref.keybits;
 701                                 bytes = chain->bytes;
 702                                 *ddflagp = ddflag;
 703                                 cluster->focus = chain;
 704                         }
 705                         KKASSERT(bref_type == chain->bref.type);
 706                         KKASSERT(bref_key == chain->bref.key);
 707                         KKASSERT(bref_keybits == chain->bref.keybits);
 708                         KKASSERT(bytes == chain->bytes);
 709                         KKASSERT(*ddflagp == ddflag);
 710                 }
 711                 if (key_accum > key_next)
 712                         key_accum = key_next;
 713         }
 714         *key_nextp = key_accum;
 715         cluster->nchains = i;
 716
 717         if (null_count == i) {
 718                 hammer2_cluster_drop(cluster);
 719                 cluster = NULL;
 720         }
 721
 722         return (cluster);
 723 }
 724
 725 /*
 726  * Locate next match or overlap under parent, replace cluster
 727  */
 728 hammer2_cluster_t *
 729 hammer2_cluster_next(hammer2_cluster_t *cparent, hammer2_cluster_t *cluster,
 730                      hammer2_key_t *key_nextp,
 731                      hammer2_key_t key_beg, hammer2_key_t key_end, int flags)
 732 {
 733         hammer2_chain_t *chain;
 734         hammer2_key_t key_accum;
 735         hammer2_key_t key_next;
 736         int null_count;
 737         int i;
 738
 739         key_accum = *key_nextp;
 740         null_count = 0;
 741         cluster->focus = NULL;
 742         cparent->focus = NULL;
 743
 744         for (i = 0; i < cparent->nchains; ++i) {
 745                 key_next = *key_nextp;
 746                 chain = cluster->array[i];
 747                 if (chain == NULL) {
 748                         if (cparent->focus == NULL)
 749                                 cparent->focus = cparent->array[i];
 750                         ++null_count;
 751                         continue;
 752                 }
 753                 if (cparent->array[i] == NULL) {
 754                         if (flags & HAMMER2_LOOKUP_NOLOCK)
 755                                 hammer2_chain_drop(chain);
 756                         else
 757                                 hammer2_chain_unlock(chain);
 758                         ++null_count;
 759                         continue;
 760                 }
 761                 chain = hammer2_chain_next(&cparent->array[i], chain,
 762                                            &key_next, key_beg, key_end,
 763                                            &cparent->cache_index[i], flags);
 764                 if (cparent->focus == NULL)
 765                         cparent->focus = cparent->array[i];
 766                 cluster->array[i] = chain;
 767                 if (chain == NULL) {
 768                         ++null_count;
 769                 } else if (cluster->focus == NULL) {
 770                         cluster->focus = chain;
 771                 }
 772                 if (key_accum > key_next)
 773                         key_accum = key_next;
 774         }
 775
 776         if (null_count == i) {
 777                 hammer2_cluster_drop(cluster);
 778                 cluster = NULL;
 779         }
 780         return(cluster);
 781 }
 782
 783 #if 0
 784 /*
 785  * XXX initial NULL cluster needs reworking (pass **clusterp ?)
 786  *
 787  * The raw scan function is similar to lookup/next but does not seek to a key.
 788  * Blockrefs are iterated via first_chain = (parent, NULL) and
 789  * next_chain = (parent, chain).
 790  *
 791  * The passed-in parent must be locked and its data resolved.  The returned
 792  * chain will be locked.  Pass chain == NULL to acquire the first sub-chain
 793  * under parent and then iterate with the passed-in chain (which this
 794  * function will unlock).
 795  */
 796 hammer2_cluster_t *
 797 hammer2_cluster_scan(hammer2_cluster_t *cparent, hammer2_cluster_t *cluster,
 798                      int flags)
 799 {
 800         hammer2_chain_t *chain;
 801         int null_count;
 802         int i;
 803
 804         null_count = 0;
 805
 806         for (i = 0; i < cparent->nchains; ++i) {
 807                 chain = cluster->array[i];
 808                 if (chain == NULL) {
 809                         ++null_count;
 810                         continue;
 811                 }
 812                 if (cparent->array[i] == NULL) {
 813                         if (flags & HAMMER2_LOOKUP_NOLOCK)
 814                                 hammer2_chain_drop(chain);
 815                         else
 816                                 hammer2_chain_unlock(chain);
 817                         ++null_count;
 818                         continue;
 819                 }
 820
 821                 chain = hammer2_chain_scan(cparent->array[i], chain,
 822                                            &cparent->cache_index[i], flags);
 823                 cluster->array[i] = chain;
 824                 if (chain == NULL)
 825                         ++null_count;
 826         }
 827
 828         if (null_count == i) {
 829                 hammer2_cluster_drop(cluster);
 830                 cluster = NULL;
 831         }
 832         return(cluster);
 833 }
 834
 835 #endif
 836
 837 /*
 838  * Create a new cluster using the specified key
 839  */
 840 int
 841 hammer2_cluster_create(hammer2_trans_t *trans, hammer2_cluster_t *cparent,
 842                      hammer2_cluster_t **clusterp,
 843                      hammer2_key_t key, int keybits,
 844                      int type, size_t bytes, int flags)
 845 {
 846         hammer2_cluster_t *cluster;
 847         hammer2_pfsmount_t *pmp;
 848         int error;
 849         int i;
 850
 851         pmp = trans->pmp;                               /* can be NULL */
 852
 853         if ((cluster = *clusterp) == NULL) {
 854                 cluster = kmalloc(sizeof(*cluster), M_HAMMER2,
 855                                   M_WAITOK | M_ZERO);
 856                 cluster->pmp = pmp;                     /* can be NULL */
 857                 cluster->refs = 1;
 858         }
 859         cluster->focus = NULL;
 860         cparent->focus = NULL;
 861
 862         /*
 863          * NOTE: cluster->array[] entries can initially be NULL.  If
 864          *       *clusterp is supplied, skip NULL entries, otherwise
 865          *       create new chains.
 866          */
 867         for (i = 0; i < cparent->nchains; ++i) {
 868                 if (*clusterp && cluster->array[i] == NULL) {
 869                         if (cparent->focus == NULL)
 870                                 cparent->focus = cparent->array[i];
 871                         continue;
 872                 }
 873                 error = hammer2_chain_create(trans, &cparent->array[i],
 874                                              &cluster->array[i], pmp,
 875                                              key, keybits,
 876                                              type, bytes, flags);
 877                 KKASSERT(error == 0);
 878                 if (cparent->focus == NULL)
 879                         cparent->focus = cparent->array[i];
 880                 if (cluster->focus == NULL)
 881                         cluster->focus = cluster->array[i];
 882         }
 883         cluster->nchains = i;
 884         *clusterp = cluster;
 885
 886         return error;
 887 }
 888
 889 /*
 890  * Rename a cluster to a new parent.
 891  *
 892  * WARNING! Unlike hammer2_chain_rename(), only the key and keybits fields
 893  *          are used from a passed-in non-NULL bref pointer.  All other fields
 894  *          are extracted from the original chain for each chain in the
 895  *          iteration.
 896  */
 897 void
 898 hammer2_cluster_rename(hammer2_trans_t *trans, hammer2_blockref_t *bref,
 899                        hammer2_cluster_t *cparent, hammer2_cluster_t *cluster,
 900                        int flags)
 901 {
 902         hammer2_chain_t *chain;
 903         hammer2_blockref_t xbref;
 904         int i;
 905
 906         cluster->focus = NULL;
 907         cparent->focus = NULL;
 908
 909         for (i = 0; i < cluster->nchains; ++i) {
 910                 chain = cluster->array[i];
 911                 if (chain) {
 912                         if (bref) {
 913                                 xbref = chain->bref;
 914                                 xbref.key = bref->key;
 915                                 xbref.keybits = bref->keybits;
 916                                 hammer2_chain_rename(trans, &xbref,
 917                                                      &cparent->array[i],
 918                                                      chain, flags);
 919                         } else {
 920                                 hammer2_chain_rename(trans, NULL,
 921                                                      &cparent->array[i],
 922                                                      chain, flags);
 923                         }
 924                         cluster->array[i] = chain;
 925                         if (cluster->focus == NULL)
 926                                 cluster->focus = chain;
 927                         if (cparent->focus == NULL)
 928                                 cparent->focus = cparent->array[i];
 929                 } else {
 930                         if (cparent->focus == NULL)
 931                                 cparent->focus = cparent->array[i];
 932                 }
 933         }
 934 }
 935
 936 /*
 937  * Mark a cluster deleted
 938  */
 939 void
 940 hammer2_cluster_delete(hammer2_trans_t *trans, hammer2_cluster_t *cparent,
 941                        hammer2_cluster_t *cluster, int flags)
 942 {
 943         hammer2_chain_t *chain;
 944         hammer2_chain_t *parent;
 945         int i;
 946
 947         if (cparent == NULL) {
 948                 kprintf("cparent is NULL\n");
 949                 return;
 950         }
 951
 952         for (i = 0; i < cluster->nchains; ++i) {
 953                 parent = (i < cparent->nchains) ? cparent->array[i] : NULL;
 954                 chain = cluster->array[i];
 955                 if (chain == NULL)
 956                         continue;
 957                 if (chain->parent != parent) {
 958                         kprintf("hammer2_cluster_delete: parent "
 959                                 "mismatch chain=%p parent=%p against=%p\n",
 960                                 chain, chain->parent, parent);
 961                 } else {
 962                         hammer2_chain_delete(trans, parent, chain, flags);
 963                 }
 964         }
 965 }
 966
 967 /*
 968  * Create a snapshot of the specified {parent, ochain} with the specified
 969  * label.  The originating hammer2_inode must be exclusively locked for
 970  * safety.
 971  *
 972  * The ioctl code has already synced the filesystem.
 973  */
 974 int
 975 hammer2_cluster_snapshot(hammer2_trans_t *trans, hammer2_cluster_t *ocluster,
 976                        hammer2_ioc_pfs_t *pfs)
 977 {
 978         hammer2_mount_t *hmp;
 979         hammer2_cluster_t *ncluster;
 980         const hammer2_inode_data_t *ipdata;
 981         hammer2_inode_data_t *wipdata;
 982         hammer2_inode_t *nip;
 983         size_t name_len;
 984         hammer2_key_t lhc;
 985         struct vattr vat;
 986         uuid_t opfs_clid;
 987         int error;
 988         int i;
 989
 990         kprintf("snapshot %s\n", pfs->name);
 991
 992         name_len = strlen(pfs->name);
 993         lhc = hammer2_dirhash(pfs->name, name_len);
 994
 995         ipdata = &hammer2_cluster_data(ocluster)->ipdata;
 996         opfs_clid = ipdata->pfs_clid;
 997         hmp = ocluster->focus->hmp;
 998
 999         /*
1000          * Create the snapshot directory under the super-root
1001          *
1002          * Set PFS type, generate a unique filesystem id, and generate
1003          * a cluster id.  Use the same clid when snapshotting a PFS root,
1004          * which theoretically allows the snapshot to be used as part of
1005          * the same cluster (perhaps as a cache).
1006          *
1007          * Copy the (flushed) blockref array.  Theoretically we could use
1008          * chain_duplicate() but it becomes difficult to disentangle
1009          * the shared core so for now just brute-force it.
1010          */
1011         VATTR_NULL(&vat);
1012         vat.va_type = VDIR;
1013         vat.va_mode = 0755;
1014         ncluster = NULL;
1015         nip = hammer2_inode_create(trans, hmp->spmp->iroot, &vat,
1016                                    proc0.p_ucred, pfs->name, name_len,
1017                                    &ncluster, &error);
1018
1019         if (nip) {
1020                 wipdata = hammer2_cluster_modify_ip(trans, nip, ncluster, 0);
1021                 wipdata->pfs_type = HAMMER2_PFSTYPE_SNAPSHOT;
1022                 kern_uuidgen(&wipdata->pfs_fsid, 1);
1023                 if (ocluster->focus->flags & HAMMER2_CHAIN_PFSBOUNDARY)
1024                         wipdata->pfs_clid = opfs_clid;
1025                 else
1026                         kern_uuidgen(&wipdata->pfs_clid, 1);
1027
1028                 for (i = 0; i < ncluster->nchains; ++i) {
1029                         if (ncluster->array[i]) {
1030                                 ncluster->array[i]->bref.flags |=
1031                                     HAMMER2_BREF_FLAG_PFSROOT;
1032                         }
1033                 }
1034 #if 0
1035                 /* XXX can't set this unless we do an explicit flush, which
1036                    we also need a pmp assigned to do, else the flush code
1037                    won't flush ncluster because it thinks it is crossing a
1038                    flush boundary */
1039                 hammer2_cluster_set_chainflags(ncluster,
1040                                                HAMMER2_CHAIN_PFSBOUNDARY);
1041 #endif
1042
1043                 /* XXX hack blockset copy */
1044                 /* XXX doesn't work with real cluster */
1045                 KKASSERT(ocluster->nchains == 1);
1046                 wipdata->u.blockset = ocluster->focus->data->ipdata.u.blockset;
1047                 hammer2_cluster_modsync(ncluster);
1048                 for (i = 0; i < ncluster->nchains; ++i) {
1049                         if (ncluster->array[i])
1050                                 hammer2_flush(trans, ncluster->array[i]);
1051                 }
1052                 hammer2_inode_unlock_ex(nip, ncluster);
1053         }
1054         return (error);
1055 }
1056
1057 /*
1058  * Return locked parent cluster given a locked child.  The child remains
1059  * locked on return.
1060  */
1061 hammer2_cluster_t *
1062 hammer2_cluster_parent(hammer2_cluster_t *cluster)
1063 {
1064         hammer2_cluster_t *cparent;
1065         int i;
1066
1067         cparent = hammer2_cluster_copy(cluster, HAMMER2_CLUSTER_COPY_NOCHAINS);
1068         for (i = 0; i < cluster->nchains; ++i) {
1069                 hammer2_chain_t *chain;
1070                 hammer2_chain_t *rchain;
1071
1072                 chain = cluster->array[i];
1073                 if (chain == NULL)
1074                         continue;
1075                 hammer2_chain_ref(chain);
1076                 while ((rchain = chain->parent) != NULL) {
1077                         hammer2_chain_ref(rchain);
1078                         hammer2_chain_unlock(chain);
1079                         hammer2_chain_lock(rchain, HAMMER2_RESOLVE_ALWAYS);
1080                         hammer2_chain_lock(chain, HAMMER2_RESOLVE_ALWAYS);
1081                         hammer2_chain_drop(rchain);
1082                         if (chain->parent == rchain)
1083                                 break;
1084                         hammer2_chain_unlock(rchain);
1085                 }
1086                 hammer2_chain_drop(chain);
1087                 cparent->array[i] = rchain;
1088         }
1089         return cparent;
1090 }
1091
1092 /************************************************************************
1093  *                          NODE FAILURES                               *
1094  ************************************************************************
1095  *
1096  * A node failure can occur for numerous reasons.
1097  *
1098  *      - A read I/O may fail
1099  *      - A write I/O may fail
1100  *      - An unexpected chain might be found (or be missing)
1101  *      - A node might disconnect temporarily and reconnect later
1102  *        (for example, a USB stick could get pulled, or a node might
1103  *        be programmatically disconnected).
1104  *      - A node might run out of space during a modifying operation.
1105  *
1106  * When a read failure or an unexpected chain state is found, the chain and
1107  * parent chain at the failure point for the nodes involved (the nodes
1108  * which we determine to be in error) are flagged as failed and removed
1109  * from the cluster.  The node itself is allowed to remain active.  The
1110  * highest common point (usually a parent chain) is queued to the
1111  * resynchronization thread for action.
1112  *
1113  * When a write I/O fails or a node runs out of space, we first adjust
1114  * as if a read failure occurs but we further disable flushes on the
1115  * ENTIRE node.  Concurrent modifying transactions are allowed to complete
1116  * but any new modifying transactions will automatically remove the node
1117  * from consideration in all related cluster structures and not generate
1118  * any new modified chains.  The ROOT chain for the failed node(s) is queued
1119  * to the resynchronization thread for action.
1120  *
1121  * A temporary disconnect is handled as if a write failure occurred.
1122  *
1123  * Any of these failures might or might not stall related high level VNOPS,
1124  * depending on what has failed, what nodes remain, the type of cluster,
1125  * and the operating state of the cluster.
1126  *
1127  *                          FLUSH ON WRITE-DISABLED NODES
1128  *
1129  * A flush on a write-disabled node is not allowed to write anything because
1130  * we cannot safely update the mirror_tid anywhere on the failed node.  The
1131  * synchronization thread uses mirror_tid to calculate incremental resyncs.
1132  * Dirty meta-data related to the failed node is thrown away.
1133  *
1134  * Dirty buffer cache buffers and inodes are only thrown away if they can be
1135  * retired... that is, if the filesystem still has enough nodes to complete
1136  * the operation.
1137  */
1138
1139 /************************************************************************
1140  *                      SYNCHRONIZATION THREAD                          *
1141  ************************************************************************
1142  *
1143  * This thread is responsible for [re]synchronizing the cluster representing
1144  * a PFS.  Any out-of-sync or failed node starts this thread on a
1145  * node-by-node basis when the failure is detected.
1146  *
1147  * Clusters needing resynchronization are queued at the highest point
1148  * where the parent on the failed node is still valid, or a special
1149  * incremental scan from the ROOT is queued if no parent exists.  This
1150  * thread is also responsible for waiting for reconnections of the failed
1151  * node if the cause was due to a disconnect, and waiting for space to be
1152  * freed up if the cause was due to running out of space.
1153  *
1154  * If the cause is due to a node running out of space, this thread will also
1155  * remove older (unlocked) snapshots to make new space, recover space, and
1156  * then start resynchronization.
1157  *
1158  * Each resynchronization pass virtually snapshots the PFS on the good nodes
1159  * and synchronizes using that snapshot against the target node.  This
1160  * ensures a consistent chain topology and also avoid interference between
1161  * the resynchronization thread and frontend operations.
1162  *
1163  * Since these are per-node threads it is possible to resynchronize several
1164  * nodes at once.
1165  */