sys/vfs/hammer2/hammer2_freemap.c

   1 /*
   2  * Copyright (c) 2011-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  * by Venkatesh Srinivas <vsrinivas@dragonflybsd.org>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  * 3. Neither the name of The DragonFly Project nor the names of its
  19  *    contributors may be used to endorse or promote products derived
  20  *    from this software without specific, prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  26  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  30  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  31  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  32  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35 #include <sys/param.h>
  36 #include <sys/systm.h>
  37 #include <sys/kernel.h>
  38 #include <sys/fcntl.h>
  39 #include <sys/buf.h>
  40 #include <sys/proc.h>
  41 #include <sys/namei.h>
  42 #include <sys/mount.h>
  43 #include <sys/vnode.h>
  44 #include <sys/mountctl.h>
  45
  46 #include "hammer2.h"
  47
  48 #define FREEMAP_DEBUG   0
  49
  50 struct hammer2_fiterate {
  51         hammer2_off_t   bpref;
  52         hammer2_off_t   bnext;
  53         int             loops;
  54 };
  55
  56 typedef struct hammer2_fiterate hammer2_fiterate_t;
  57
  58 static int hammer2_freemap_try_alloc(hammer2_trans_t *trans,
  59                         hammer2_chain_t **parentp, hammer2_blockref_t *bref,
  60                         int radix, hammer2_fiterate_t *iter);
  61 static void hammer2_freemap_init(hammer2_trans_t *trans, hammer2_mount_t *hmp,
  62                         hammer2_key_t key, hammer2_chain_t *chain);
  63 static int hammer2_bmap_alloc(hammer2_trans_t *trans, hammer2_mount_t *hmp,
  64                         hammer2_bmap_data_t *bmap, uint16_t class,
  65                         int n, int radix, hammer2_key_t *basep);
  66 static int hammer2_freemap_iterate(hammer2_trans_t *trans,
  67                         hammer2_chain_t **parentp, hammer2_chain_t **chainp,
  68                         hammer2_fiterate_t *iter);
  69
  70 static __inline
  71 int
  72 hammer2_freemapradix(int radix)
  73 {
  74         return(radix);
  75 }
  76
  77 /*
  78  * Calculate the device offset for the specified FREEMAP_NODE or FREEMAP_LEAF
  79  * bref.  Return a combined media offset and physical size radix.  Freemap
  80  * chains use fixed storage offsets in the 4MB reserved area at the
  81  * beginning of each 2GB zone
  82  *
  83  * Rotate between four possibilities.  Theoretically this means we have three
  84  * good freemaps in case of a crash which we can use as a base for the fixup
  85  * scan at mount-time.
  86  */
  87 #define H2FMBASE(key, radix)    ((key) & ~(((hammer2_off_t)1 << (radix)) - 1))
  88 #define H2FMSHIFT(radix)        ((hammer2_off_t)1 << (radix))
  89
  90 static
  91 int
  92 hammer2_freemap_reserve(hammer2_trans_t *trans, hammer2_chain_t *chain,
  93                         int radix)
  94 {
  95         hammer2_blockref_t *bref = &chain->bref;
  96         hammer2_off_t off;
  97         int index;
  98         size_t bytes;
  99
 100         /*
 101          * Physical allocation size -> radix.  Typically either 256 for
 102          * a level 0 freemap leaf or 65536 for a level N freemap node.
 103          *
 104          * NOTE: A 256 byte bitmap represents 256 x 8 x 1024 = 2MB of storage.
 105          *       Do not use hammer2_allocsize() here as it has a min cap.
 106          */
 107         bytes = 1 << radix;
 108
 109         /*
 110          * Calculate block selection index 0..7 of current block.
 111          */
 112         if ((bref->data_off & ~HAMMER2_OFF_MASK_RADIX) == 0) {
 113                 index = 0;
 114         } else {
 115                 off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX &
 116                       (((hammer2_off_t)1 << HAMMER2_FREEMAP_LEVEL1_RADIX) - 1);
 117                 off = off / HAMMER2_PBUFSIZE;
 118                 KKASSERT(off >= HAMMER2_ZONE_FREEMAP_00 &&
 119                          off < HAMMER2_ZONE_FREEMAP_END);
 120                 index = (int)(off - HAMMER2_ZONE_FREEMAP_00) / 4;
 121                 KKASSERT(index >= 0 && index < HAMMER2_ZONE_FREEMAP_COPIES);
 122         }
 123
 124         /*
 125          * Calculate new index (our 'allocation').  We have to be careful
 126          * here as there can be two different transaction ids running
 127          * concurrently when a flush is in-progress.
 128          *
 129          * We also want to make sure, for algorithmic repeatability, that
 130          * the index sequences are monotonic with transaction ids.  Some
 131          * skipping is allowed as long as we ensure that all four volume
 132          * header backups have consistent freemaps.
 133          *
 134          * FLUSH  NORMAL FLUSH  NORMAL FLUSH  NORMAL FLUSH  NORMAL
 135          * N+=1   N+=2
 136          * (0->1) (1->3) (3->4) (4->6) (6->7) (7->9) (9->10) (10->12)
 137          *
 138          * [-concurrent-][-concurrent-][-concurrent-][-concurrent-]
 139          *
 140          * (alternative first NORMAL might be 0->2 if flush had not yet
 141          *  modified the chain, this is the worst case).
 142          */
 143         if ((trans->flags & HAMMER2_TRANS_ISFLUSH) == 0) {
 144                 /*
 145                  * Normal transactions always run with the highest TID.
 146                  * But if a flush is in-progress we want to reserve a slot
 147                  * for the flush with a lower TID running concurrently to
 148                  * do a delete-duplicate.
 149                  */
 150                 index = (index + 2) % HAMMER2_ZONE_FREEMAP_COPIES;
 151         } else if (trans->flags & HAMMER2_TRANS_ISALLOCATING) {
 152                 /*
 153                  * Flush transaction, hammer2_freemap.c itself is doing a
 154                  * delete-duplicate during an allocation within the freemap.
 155                  */
 156                 index = (index + 1) % HAMMER2_ZONE_FREEMAP_COPIES;
 157         } else {
 158                 /*
 159                  * Flush transaction, hammer2_flush.c is doing a
 160                  * delete-duplicate on the freemap while flushing
 161                  * hmp->fchain.
 162                  */
 163                 index = (index + 1) % HAMMER2_ZONE_FREEMAP_COPIES;
 164         }
 165
 166         /*
 167          * Calculate the block offset of the reserved block.  This will
 168          * point into the 4MB reserved area at the base of the appropriate
 169          * 2GB zone, once added to the FREEMAP_x selection above.
 170          */
 171         switch(bref->keybits) {
 172         /* case HAMMER2_FREEMAP_LEVEL5_RADIX: not applicable */
 173         case HAMMER2_FREEMAP_LEVEL4_RADIX:      /* 2EB */
 174                 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
 175                 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
 176                 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL4_RADIX) +
 177                       (index * 4 + HAMMER2_ZONE_FREEMAP_00 +
 178                        HAMMER2_ZONEFM_LEVEL4) * HAMMER2_PBUFSIZE;
 179                 break;
 180         case HAMMER2_FREEMAP_LEVEL3_RADIX:      /* 2PB */
 181                 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
 182                 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
 183                 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL3_RADIX) +
 184                       (index * 4 + HAMMER2_ZONE_FREEMAP_00 +
 185                        HAMMER2_ZONEFM_LEVEL3) * HAMMER2_PBUFSIZE;
 186                 break;
 187         case HAMMER2_FREEMAP_LEVEL2_RADIX:      /* 2TB */
 188                 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
 189                 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
 190                 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL2_RADIX) +
 191                       (index * 4 + HAMMER2_ZONE_FREEMAP_00 +
 192                        HAMMER2_ZONEFM_LEVEL2) * HAMMER2_PBUFSIZE;
 193                 break;
 194         case HAMMER2_FREEMAP_LEVEL1_RADIX:      /* 2GB */
 195                 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF);
 196                 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
 197                 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
 198                       (index * 4 + HAMMER2_ZONE_FREEMAP_00 +
 199                        HAMMER2_ZONEFM_LEVEL1) * HAMMER2_PBUFSIZE;
 200                 break;
 201         default:
 202                 panic("freemap: bad radix(2) %p %d\n", bref, bref->keybits);
 203                 /* NOT REACHED */
 204                 off = (hammer2_off_t)-1;
 205                 break;
 206         }
 207         bref->data_off = off | radix;
 208 #if FREEMAP_DEBUG
 209         kprintf("FREEMAP BLOCK TYPE %d %016jx/%d DATA_OFF=%016jx\n",
 210                 bref->type, bref->key, bref->keybits, bref->data_off);
 211 #endif
 212         return (0);
 213 }
 214
 215 /*
 216  * Normal freemap allocator
 217  *
 218  * Use available hints to allocate space using the freemap.  Create missing
 219  * freemap infrastructure on-the-fly as needed (including marking initial
 220  * allocations using the iterator as allocated, instantiating new 2GB zones,
 221  * and dealing with the end-of-media edge case).
 222  *
 223  * ip and bpref are only used as a heuristic to determine locality of
 224  * reference.  bref->key may also be used heuristically.
 225  *
 226  * WARNING! When called from a flush we have to use the 'live' sync_tid
 227  *          and not the flush sync_tid.  The live sync_tid is the flush
 228  *          sync_tid + 1.  That is, freemap allocations which occur during
 229  *          a flush are not part of the flush.  Crash-recovery will restore
 230  *          any lost allocations.
 231  */
 232 int
 233 hammer2_freemap_alloc(hammer2_trans_t *trans, hammer2_chain_t *chain,
 234                       size_t bytes)
 235 {
 236         hammer2_mount_t *hmp = chain->hmp;
 237         hammer2_blockref_t *bref = &chain->bref;
 238         hammer2_chain_t *parent;
 239         int radix;
 240         int error;
 241         unsigned int hindex;
 242         hammer2_fiterate_t iter;
 243
 244         /*
 245          * Validate the allocation size.  It must be a power of 2.
 246          *
 247          * For now require that the caller be aware of the minimum
 248          * allocation (1K).
 249          */
 250         radix = hammer2_getradix(bytes);
 251         KKASSERT((size_t)1 << radix == bytes);
 252
 253         /*
 254          * Freemap blocks themselves are simply assigned from the reserve
 255          * area, not allocated from the freemap.
 256          */
 257         if (bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
 258             bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
 259                 return (hammer2_freemap_reserve(trans, chain, radix));
 260         }
 261
 262 #if 0
 263         /*
 264          * (this mechanic is no longer used, DOMAYFREE is used only by
 265          * the bulk freemap scan now).
 266          *
 267          * Mark previously allocated block as possibly freeable.  There might
 268          * be snapshots and other races so we can't just mark it fully free.
 269          * (XXX optimize this for the current-transaction create+delete case)
 270          */
 271         if (bref->data_off & ~HAMMER2_OFF_MASK_RADIX) {
 272                 hammer2_freemap_adjust(trans, hmp, bref,
 273                                        HAMMER2_FREEMAP_DOMAYFREE);
 274         }
 275 #endif
 276
 277         /*
 278          * Setting ISALLOCATING ensures correct operation even when the
 279          * flusher itself is making allocations.
 280          */
 281         KKASSERT(bytes >= HAMMER2_MIN_ALLOC && bytes <= HAMMER2_MAX_ALLOC);
 282         KKASSERT((trans->flags & HAMMER2_TRANS_ISALLOCATING) == 0);
 283         atomic_set_int(&trans->flags, HAMMER2_TRANS_ISALLOCATING);
 284         if (trans->flags & (HAMMER2_TRANS_ISFLUSH | HAMMER2_TRANS_PREFLUSH))
 285                 ++trans->sync_tid;
 286
 287         /*
 288          * Calculate the starting point for our allocation search.
 289          *
 290          * Each freemap leaf is dedicated to a specific freemap_radix.
 291          * The freemap_radix can be more fine-grained than the device buffer
 292          * radix which results in inodes being grouped together in their
 293          * own segment, terminal-data (16K or less) and initial indirect
 294          * block being grouped together, and then full-indirect and full-data
 295          * blocks (64K) being grouped together.
 296          *
 297          * The single most important aspect of this is the inode grouping
 298          * because that is what allows 'find' and 'ls' and other filesystem
 299          * topology operations to run fast.
 300          */
 301 #if 0
 302         if (bref->data_off & ~HAMMER2_OFF_MASK_RADIX)
 303                 bpref = bref->data_off & ~HAMMER2_OFF_MASK_RADIX;
 304         else if (trans->tmp_bpref)
 305                 bpref = trans->tmp_bpref;
 306         else if (trans->tmp_ip)
 307                 bpref = trans->tmp_ip->chain->bref.data_off;
 308         else
 309 #endif
 310         /*
 311          * Heuristic tracking index.  We would like one for each distinct
 312          * bref type if possible.  heur_freemap[] has room for two classes
 313          * for each type.  At a minimum we have to break-up our heuristic
 314          * by device block sizes.
 315          */
 316         hindex = hammer2_devblkradix(radix) - HAMMER2_MINIORADIX;
 317         KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_NRADIX);
 318         hindex += bref->type * HAMMER2_FREEMAP_HEUR_NRADIX;
 319         hindex &= HAMMER2_FREEMAP_HEUR_TYPES * HAMMER2_FREEMAP_HEUR_NRADIX - 1;
 320         KKASSERT(hindex < HAMMER2_FREEMAP_HEUR);
 321
 322         iter.bpref = hmp->heur_freemap[hindex];
 323
 324         /*
 325          * Make sure bpref is in-bounds.  It's ok if bpref covers a zone's
 326          * reserved area, the try code will iterate past it.
 327          */
 328         if (iter.bpref > hmp->voldata.volu_size)
 329                 iter.bpref = hmp->voldata.volu_size - 1;
 330
 331         /*
 332          * Iterate the freemap looking for free space before and after.
 333          */
 334         parent = &hmp->fchain;
 335         hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS);
 336         error = EAGAIN;
 337         iter.bnext = iter.bpref;
 338         iter.loops = 0;
 339
 340         while (error == EAGAIN) {
 341                 error = hammer2_freemap_try_alloc(trans, &parent, bref,
 342                                                   radix, &iter);
 343         }
 344         hmp->heur_freemap[hindex] = iter.bnext;
 345         hammer2_chain_unlock(parent);
 346
 347         atomic_clear_int(&trans->flags, HAMMER2_TRANS_ISALLOCATING);
 348         if (trans->flags & (HAMMER2_TRANS_ISFLUSH | HAMMER2_TRANS_PREFLUSH))
 349                 --trans->sync_tid;
 350
 351         return (error);
 352 }
 353
 354 static int
 355 hammer2_freemap_try_alloc(hammer2_trans_t *trans, hammer2_chain_t **parentp,
 356                           hammer2_blockref_t *bref, int radix,
 357                           hammer2_fiterate_t *iter)
 358 {
 359         hammer2_mount_t *hmp = (*parentp)->hmp;
 360         hammer2_off_t l0size;
 361         hammer2_off_t l1size;
 362         hammer2_off_t l1mask;
 363         hammer2_key_t key_dummy;
 364         hammer2_chain_t *chain;
 365         hammer2_off_t key;
 366         size_t bytes;
 367         uint16_t class;
 368         int error = 0;
 369         int cache_index = -1;
 370         int ddflag;
 371
 372
 373         /*
 374          * Calculate the number of bytes being allocated, the number
 375          * of contiguous bits of bitmap being allocated, and the bitmap
 376          * mask.
 377          *
 378          * WARNING! cpu hardware may mask bits == 64 -> 0 and blow up the
 379          *          mask calculation.
 380          */
 381         bytes = (size_t)1 << radix;
 382         class = (bref->type << 8) | hammer2_devblkradix(radix);
 383
 384         /*
 385          * Lookup the level1 freemap chain, creating and initializing one
 386          * if necessary.  Intermediate levels will be created automatically
 387          * when necessary by hammer2_chain_create().
 388          */
 389         key = H2FMBASE(iter->bnext, HAMMER2_FREEMAP_LEVEL1_RADIX);
 390         l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 391         l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 392         l1mask = l1size - 1;
 393
 394         chain = hammer2_chain_lookup(parentp, &key_dummy, key, key + l1mask,
 395                                      &cache_index,
 396                                      HAMMER2_LOOKUP_ALWAYS |
 397                                      HAMMER2_LOOKUP_MATCHIND, &ddflag);
 398
 399         if (chain == NULL) {
 400                 /*
 401                  * Create the missing leaf, be sure to initialize
 402                  * the auxillary freemap tracking information in
 403                  * the bref.check.freemap structure.
 404                  */
 405 #if 0
 406                 kprintf("freemap create L1 @ %016jx bpref %016jx\n",
 407                         key, iter->bpref);
 408 #endif
 409                 error = hammer2_chain_create(trans, parentp, &chain,
 410                                      key, HAMMER2_FREEMAP_LEVEL1_RADIX,
 411                                      HAMMER2_BREF_TYPE_FREEMAP_LEAF,
 412                                      HAMMER2_FREEMAP_LEVELN_PSIZE);
 413                 KKASSERT(error == 0);
 414                 if (error == 0) {
 415                         hammer2_chain_modify(trans, &chain, 0);
 416                         bzero(&chain->data->bmdata[0],
 417                               HAMMER2_FREEMAP_LEVELN_PSIZE);
 418                         chain->bref.check.freemap.bigmask = (uint32_t)-1;
 419                         chain->bref.check.freemap.avail = l1size;
 420                         /* bref.methods should already be inherited */
 421
 422                         hammer2_freemap_init(trans, hmp, key, chain);
 423                 }
 424         } else if ((chain->bref.check.freemap.bigmask & (1 << radix)) == 0) {
 425                 /*
 426                  * Already flagged as not having enough space
 427                  */
 428                 error = ENOSPC;
 429         } else {
 430                 /*
 431                  * Modify existing chain to setup for adjustment.
 432                  */
 433                 hammer2_chain_modify(trans, &chain, 0);
 434         }
 435
 436         /*
 437          * Scan 2MB entries.
 438          */
 439         if (error == 0) {
 440                 hammer2_bmap_data_t *bmap;
 441                 hammer2_key_t base_key;
 442                 int count;
 443                 int start;
 444                 int n;
 445
 446                 KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF);
 447                 start = (int)((iter->bnext - key) >>
 448                               HAMMER2_FREEMAP_LEVEL0_RADIX);
 449                 KKASSERT(start >= 0 && start < HAMMER2_FREEMAP_COUNT);
 450                 hammer2_chain_modify(trans, &chain, 0);
 451
 452                 error = ENOSPC;
 453                 for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) {
 454                         if (start + count >= HAMMER2_FREEMAP_COUNT &&
 455                             start - count < 0) {
 456                                 break;
 457                         }
 458                         n = start + count;
 459                         bmap = &chain->data->bmdata[n];
 460                         if (n < HAMMER2_FREEMAP_COUNT && bmap->avail &&
 461                             (bmap->class == 0 || bmap->class == class)) {
 462                                 base_key = key + n * l0size;
 463                                 error = hammer2_bmap_alloc(trans, hmp, bmap,
 464                                                            class, n, radix,
 465                                                            &base_key);
 466                                 if (error != ENOSPC) {
 467                                         key = base_key;
 468                                         break;
 469                                 }
 470                         }
 471                         n = start - count;
 472                         bmap = &chain->data->bmdata[n];
 473                         if (n >= 0 && bmap->avail &&
 474                             (bmap->class == 0 || bmap->class == class)) {
 475                                 base_key = key + n * l0size;
 476                                 error = hammer2_bmap_alloc(trans, hmp, bmap,
 477                                                            class, n, radix,
 478                                                            &base_key);
 479                                 if (error != ENOSPC) {
 480                                         key = base_key;
 481                                         break;
 482                                 }
 483                         }
 484                 }
 485                 if (error == ENOSPC)
 486                         chain->bref.check.freemap.bigmask &= ~(1 << radix);
 487                 /* XXX also scan down from original count */
 488         }
 489
 490         if (error == 0) {
 491                 /*
 492                  * Assert validity.  Must be beyond the static allocator used
 493                  * by newfs_hammer2 (and thus also beyond the aux area),
 494                  * not go past the volume size, and must not be in the
 495                  * reserved segment area for a zone.
 496                  */
 497                 KKASSERT(key >= hmp->voldata.allocator_beg &&
 498                          key + bytes <= hmp->voldata.volu_size);
 499                 KKASSERT((key & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG);
 500                 bref->data_off = key | radix;
 501
 502 #if 0
 503                 kprintf("alloc cp=%p %016jx %016jx using %016jx\n",
 504                         chain,
 505                         bref->key, bref->data_off, chain->bref.data_off);
 506 #endif
 507         } else if (error == ENOSPC) {
 508                 /*
 509                  * Return EAGAIN with next iteration in iter->bnext, or
 510                  * return ENOSPC if the allocation map has been exhausted.
 511                  */
 512                 error = hammer2_freemap_iterate(trans, parentp, &chain, iter);
 513         }
 514
 515         /*
 516          * Cleanup
 517          */
 518         if (chain)
 519                 hammer2_chain_unlock(chain);
 520         return (error);
 521 }
 522
 523 /*
 524  * Allocate (1<<radix) bytes from the bmap whos base data offset is (*basep).
 525  *
 526  * If the linear iterator is mid-block we use it directly (the bitmap should
 527  * already be marked allocated), otherwise we search for a block in the bitmap
 528  * that fits the allocation request.
 529  *
 530  * A partial bitmap allocation sets the minimum bitmap granularity (16KB)
 531  * to fully allocated and adjusts the linear allocator to allow the
 532  * remaining space to be allocated.
 533  */
 534 static
 535 int
 536 hammer2_bmap_alloc(hammer2_trans_t *trans, hammer2_mount_t *hmp,
 537                    hammer2_bmap_data_t *bmap,
 538                    uint16_t class, int n, int radix, hammer2_key_t *basep)
 539 {
 540         hammer2_io_t *dio;
 541         size_t size;
 542         size_t bsize;
 543         int bmradix;
 544         uint32_t bmmask;
 545         int offset;
 546         int error;
 547         int i;
 548         int j;
 549
 550         /*
 551          * Take into account 2-bits per block when calculating bmradix.
 552          */
 553         size = (size_t)1 << radix;
 554
 555         if (radix <= HAMMER2_FREEMAP_BLOCK_RADIX) {
 556                 bmradix = 2;
 557                 bsize = HAMMER2_FREEMAP_BLOCK_SIZE;
 558                 /* (16K) 2 bits per allocation block */
 559         } else {
 560                 bmradix = 2 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX);
 561                 bsize = size;
 562                 /* (32K-256K) 4, 8, 16, 32 bits per allocation block */
 563         }
 564
 565         /*
 566          * Use the linear iterator to pack small allocations, otherwise
 567          * fall-back to finding a free 16KB chunk.  The linear iterator
 568          * is only valid when *NOT* on a freemap chunking boundary (16KB).
 569          * If it is the bitmap must be scanned.  It can become invalid
 570          * once we pack to the boundary.  We adjust it after a bitmap
 571          * allocation only for sub-16KB allocations (so the perfectly good
 572          * previous value can still be used for fragments when 16KB+
 573          * allocations are made).
 574          *
 575          * Beware of hardware artifacts when bmradix == 32 (intermediate
 576          * result can wind up being '1' instead of '0' if hardware masks
 577          * bit-count & 31).
 578          *
 579          * NOTE: j needs to be even in the j= calculation.  As an artifact
 580          *       of the /2 division, our bitmask has to clear bit 0.
 581          *
 582          * NOTE: TODO this can leave little unallocatable fragments lying
 583          *       around.
 584          */
 585         if (((uint32_t)bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) + size <=
 586             HAMMER2_FREEMAP_BLOCK_SIZE &&
 587             (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) &&
 588             bmap->linear < HAMMER2_SEGSIZE) {
 589                 KKASSERT(bmap->linear >= 0 &&
 590                          bmap->linear + size <= HAMMER2_SEGSIZE &&
 591                          (bmap->linear & (HAMMER2_MIN_ALLOC - 1)) == 0);
 592                 offset = bmap->linear;
 593                 i = offset / (HAMMER2_SEGSIZE / 8);
 594                 j = (offset / (HAMMER2_FREEMAP_BLOCK_SIZE / 2)) & 30;
 595                 bmmask = (bmradix == 32) ?
 596                          0xFFFFFFFFU : (1 << bmradix) - 1;
 597                 bmmask <<= j;
 598                 bmap->linear = offset + size;
 599         } else {
 600                 for (i = 0; i < 8; ++i) {
 601                         bmmask = (bmradix == 32) ?
 602                                  0xFFFFFFFFU : (1 << bmradix) - 1;
 603                         for (j = 0; j < 32; j += bmradix) {
 604                                 if ((bmap->bitmap[i] & bmmask) == 0)
 605                                         goto success;
 606                                 bmmask <<= bmradix;
 607                         }
 608                 }
 609                 /*fragments might remain*/
 610                 /*KKASSERT(bmap->avail == 0);*/
 611                 return (ENOSPC);
 612 success:
 613                 offset = i * (HAMMER2_SEGSIZE / 8) +
 614                          (j * (HAMMER2_FREEMAP_BLOCK_SIZE / 2));
 615                 if (size & HAMMER2_FREEMAP_BLOCK_MASK)
 616                         bmap->linear = offset + size;
 617         }
 618
 619         KKASSERT(i >= 0 && i < 8);      /* 8 x 16 -> 128 x 16K -> 2MB */
 620
 621         /*
 622          * Optimize the buffer cache to avoid unnecessary read-before-write
 623          * operations.
 624          *
 625          * The device block size could be larger than the allocation size
 626          * so the actual bitmap test is somewhat more involved.  We have
 627          * to use a compatible buffer size for this operation.
 628          */
 629         if ((bmap->bitmap[i] & bmmask) == 0 &&
 630             hammer2_devblksize(size) != size) {
 631                 size_t psize = hammer2_devblksize(size);
 632                 hammer2_off_t pmask = (hammer2_off_t)psize - 1;
 633                 int pbmradix = 2 << (hammer2_devblkradix(radix) -
 634                                      HAMMER2_FREEMAP_BLOCK_RADIX);
 635                 uint32_t pbmmask;
 636                 int pradix = hammer2_getradix(psize);
 637
 638                 pbmmask = (pbmradix == 32) ? 0xFFFFFFFFU : (1 << pbmradix) - 1;
 639                 while ((pbmmask & bmmask) == 0)
 640                         pbmmask <<= pbmradix;
 641
 642 #if 0
 643                 kprintf("%016jx mask %08x %08x %08x (%zd/%zd)\n",
 644                         *basep + offset, bmap->bitmap[i],
 645                         pbmmask, bmmask, size, psize);
 646 #endif
 647
 648                 if ((bmap->bitmap[i] & pbmmask) == 0) {
 649                         error = hammer2_io_newq(hmp,
 650                                                 (*basep + (offset & ~pmask)) |
 651                                                  pradix,
 652                                                 psize, &dio);
 653                         hammer2_io_bqrelse(&dio);
 654                 }
 655         }
 656
 657 #if 0
 658         /*
 659          * When initializing a new inode segment also attempt to initialize
 660          * an adjacent segment.  Be careful not to index beyond the array
 661          * bounds.
 662          *
 663          * We do this to try to localize inode accesses to improve
 664          * directory scan rates.  XXX doesn't improve scan rates.
 665          */
 666         if (size == HAMMER2_INODE_BYTES) {
 667                 if (n & 1) {
 668                         if (bmap[-1].radix == 0 && bmap[-1].avail)
 669                                 bmap[-1].radix = radix;
 670                 } else {
 671                         if (bmap[1].radix == 0 && bmap[1].avail)
 672                                 bmap[1].radix = radix;
 673                 }
 674         }
 675 #endif
 676
 677         /*
 678          * Adjust the linear iterator, set the radix if necessary (might as
 679          * well just set it unconditionally), adjust *basep to return the
 680          * allocated data offset.
 681          */
 682         bmap->bitmap[i] |= bmmask;
 683         bmap->class = class;
 684         bmap->avail -= size;
 685         *basep += offset;
 686
 687         hammer2_voldata_lock(hmp);
 688         hmp->voldata.allocator_free -= size;  /* XXX */
 689         hammer2_voldata_unlock(hmp, 1);
 690
 691         return(0);
 692 }
 693
 694 static
 695 void
 696 hammer2_freemap_init(hammer2_trans_t *trans, hammer2_mount_t *hmp,
 697                      hammer2_key_t key, hammer2_chain_t *chain)
 698 {
 699         hammer2_off_t l1size;
 700         hammer2_off_t lokey;
 701         hammer2_off_t hikey;
 702         hammer2_bmap_data_t *bmap;
 703         int count;
 704
 705         l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 706
 707         /*
 708          * Calculate the portion of the 2GB map that should be initialized
 709          * as free.  Portions below or after will be initialized as allocated.
 710          * SEGMASK-align the areas so we don't have to worry about sub-scans
 711          * or endianess when using memset.
 712          *
 713          * (1) Ensure that all statically allocated space from newfs_hammer2
 714          *     is marked allocated.
 715          *
 716          * (2) Ensure that the reserved area is marked allocated (typically
 717          *     the first 4MB of the 2GB area being represented).
 718          *
 719          * (3) Ensure that any trailing space at the end-of-volume is marked
 720          *     allocated.
 721          *
 722          * WARNING! It is possible for lokey to be larger than hikey if the
 723          *          entire 2GB segment is within the static allocation.
 724          */
 725         lokey = (hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) &
 726                 ~HAMMER2_SEGMASK64;
 727
 728         if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
 729                   HAMMER2_ZONE_SEG64) {
 730                 lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
 731                         HAMMER2_ZONE_SEG64;
 732         }
 733
 734         hikey = key + H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 735         if (hikey > hmp->voldata.volu_size) {
 736                 hikey = hmp->voldata.volu_size & ~HAMMER2_SEGMASK64;
 737         }
 738
 739         chain->bref.check.freemap.avail =
 740                 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 741         bmap = &chain->data->bmdata[0];
 742
 743         for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) {
 744                 if (key < lokey || key >= hikey) {
 745                         memset(bmap->bitmap, -1,
 746                                sizeof(bmap->bitmap));
 747                         bmap->avail = 0;
 748                         bmap->linear = HAMMER2_SEGSIZE;
 749                         chain->bref.check.freemap.avail -=
 750                                 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 751                 } else {
 752                         bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 753                 }
 754                 key += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 755                 ++bmap;
 756         }
 757 }
 758
 759 /*
 760  * The current Level 1 freemap has been exhausted, iterate to the next
 761  * one, return ENOSPC if no freemaps remain.
 762  *
 763  * XXX this should rotate back to the beginning to handle freed-up space
 764  * XXX or use intermediate entries to locate free space. TODO
 765  */
 766 static int
 767 hammer2_freemap_iterate(hammer2_trans_t *trans, hammer2_chain_t **parentp,
 768                         hammer2_chain_t **chainp, hammer2_fiterate_t *iter)
 769 {
 770         hammer2_mount_t *hmp = (*parentp)->hmp;
 771
 772         iter->bnext &= ~(H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX) - 1);
 773         iter->bnext += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 774         if (iter->bnext >= hmp->voldata.volu_size) {
 775                 iter->bnext = 0;
 776                 if (++iter->loops == 2)
 777                         return (ENOSPC);
 778         }
 779         return(EAGAIN);
 780 }
 781
 782 /*
 783  * Adjust the bit-pattern for data in the freemap bitmap according to
 784  * (how).  This code is called from on-mount recovery to fixup (mark
 785  * as allocated) blocks whos freemap upates might not have been committed
 786  * in the last crash and is used by the bulk freemap scan to stage frees.
 787  *
 788  * XXX currently disabled when how == 0 (the normal real-time case).  At
 789  * the moment we depend on the bulk freescan to actually free blocks.  It
 790  * will still call this routine with a non-zero how to stage possible frees
 791  * and to do the actual free.
 792  *
 793  * WARNING! When called from a flush we have to use the 'live' sync_tid
 794  *          and not the flush sync_tid.  The live sync_tid is the flush
 795  *          sync_tid + 1.  That is, freemap allocations which occur during
 796  *          a flush are not part of the flush.  Crash-recovery will restore
 797  *          any lost allocations.
 798  */
 799 void
 800 hammer2_freemap_adjust(hammer2_trans_t *trans, hammer2_mount_t *hmp,
 801                        hammer2_blockref_t *bref, int how)
 802 {
 803         hammer2_off_t data_off = bref->data_off;
 804         hammer2_chain_t *chain;
 805         hammer2_chain_t *parent;
 806         hammer2_bmap_data_t *bmap;
 807         hammer2_key_t key;
 808         hammer2_key_t key_dummy;
 809         hammer2_off_t l0size;
 810         hammer2_off_t l1size;
 811         hammer2_off_t l1mask;
 812         uint32_t *bitmap;
 813         const uint32_t bmmask00 = 0;
 814         uint32_t bmmask01;
 815         uint32_t bmmask10;
 816         uint32_t bmmask11;
 817         size_t bytes;
 818         uint16_t class;
 819         int radix;
 820         int start;
 821         int count;
 822         int modified = 0;
 823         int cache_index = -1;
 824         int error;
 825         int ddflag;
 826
 827         radix = (int)data_off & HAMMER2_OFF_MASK_RADIX;
 828         data_off &= ~HAMMER2_OFF_MASK_RADIX;
 829         KKASSERT(radix <= HAMMER2_MAX_RADIX);
 830
 831         bytes = (size_t)1 << radix;
 832         class = (bref->type << 8) | hammer2_devblkradix(radix);
 833
 834         /*
 835          * We can't adjust thre freemap for data allocations made by
 836          * newfs_hammer2.
 837          */
 838         if (data_off < hmp->voldata.allocator_beg)
 839                 return;
 840
 841         KKASSERT((data_off & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG);
 842         KKASSERT((trans->flags & HAMMER2_TRANS_ISALLOCATING) == 0);
 843         atomic_set_int(&trans->flags, HAMMER2_TRANS_ISALLOCATING);
 844         if (trans->flags & (HAMMER2_TRANS_ISFLUSH | HAMMER2_TRANS_PREFLUSH))
 845                 ++trans->sync_tid;
 846
 847         /*
 848          * Lookup the level1 freemap chain.  The chain must exist.
 849          */
 850         key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL1_RADIX);
 851         l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 852         l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX);
 853         l1mask = l1size - 1;
 854
 855         parent = &hmp->fchain;
 856         hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS);
 857
 858         chain = hammer2_chain_lookup(&parent, &key_dummy, key, key + l1mask,
 859                                      &cache_index,
 860                                      HAMMER2_LOOKUP_ALWAYS |
 861                                      HAMMER2_LOOKUP_MATCHIND, &ddflag);
 862
 863         /*
 864          * Stop early if we are trying to free something but no leaf exists.
 865          */
 866         if (chain == NULL && how != HAMMER2_FREEMAP_DORECOVER) {
 867                 kprintf("hammer2_freemap_adjust: %016jx: no chain\n",
 868                         (intmax_t)bref->data_off);
 869                 goto done;
 870         }
 871
 872         /*
 873          * Create any missing leaf(s) if we are doing a recovery (marking
 874          * the block(s) as being allocated instead of being freed).  Be sure
 875          * to initialize the auxillary freemap tracking info in the
 876          * bref.check.freemap structure.
 877          */
 878         if (chain == NULL && how == HAMMER2_FREEMAP_DORECOVER) {
 879                 error = hammer2_chain_create(trans, &parent, &chain,
 880                                      key, HAMMER2_FREEMAP_LEVEL1_RADIX,
 881                                      HAMMER2_BREF_TYPE_FREEMAP_LEAF,
 882                                      HAMMER2_FREEMAP_LEVELN_PSIZE);
 883
 884                 if (hammer2_debug & 0x0040) {
 885                         kprintf("fixup create chain %p %016jx:%d\n",
 886                                 chain, chain->bref.key, chain->bref.keybits);
 887                 }
 888
 889                 if (error == 0) {
 890                         hammer2_chain_modify(trans, &chain, 0);
 891                         bzero(&chain->data->bmdata[0],
 892                               HAMMER2_FREEMAP_LEVELN_PSIZE);
 893                         chain->bref.check.freemap.bigmask = (uint32_t)-1;
 894                         chain->bref.check.freemap.avail = l1size;
 895                         /* bref.methods should already be inherited */
 896
 897                         hammer2_freemap_init(trans, hmp, key, chain);
 898                 }
 899                 /* XXX handle error */
 900         }
 901
 902 #if FREEMAP_DEBUG
 903         kprintf("FREEMAP ADJUST TYPE %d %016jx/%d DATA_OFF=%016jx\n",
 904                 chain->bref.type, chain->bref.key,
 905                 chain->bref.keybits, chain->bref.data_off);
 906 #endif
 907
 908         /*
 909          * Calculate the bitmask (runs in 2-bit pairs).
 910          */
 911         start = ((int)(data_off >> HAMMER2_FREEMAP_BLOCK_RADIX) & 15) * 2;
 912         bmmask01 = 1 << start;
 913         bmmask10 = 2 << start;
 914         bmmask11 = 3 << start;
 915
 916         /*
 917          * Fixup the bitmap.  Partial blocks cannot be fully freed unless
 918          * a bulk scan is able to roll them up.
 919          */
 920         if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) {
 921                 count = 1;
 922                 if (how == HAMMER2_FREEMAP_DOREALFREE)
 923                         how = HAMMER2_FREEMAP_DOMAYFREE;
 924         } else {
 925                 count = 1 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX);
 926         }
 927
 928         /*
 929          * [re]load the bmap and bitmap pointers.  Each bmap entry covers
 930          * a 2MB swath.  The bmap itself (LEVEL1) covers 2GB.
 931          *
 932          * Be sure to reset the linear iterator to ensure that the adjustment
 933          * is not ignored.
 934          */
 935 again:
 936         bmap = &chain->data->bmdata[(int)(data_off >> HAMMER2_SEGRADIX) &
 937                                     (HAMMER2_FREEMAP_COUNT - 1)];
 938         bitmap = &bmap->bitmap[(int)(data_off >> (HAMMER2_SEGRADIX - 3)) & 7];
 939         bmap->linear = 0;
 940
 941         while (count) {
 942                 KKASSERT(bmmask11);
 943                 if (how == HAMMER2_FREEMAP_DORECOVER) {
 944                         /*
 945                          * Recovery request, mark as allocated.
 946                          */
 947                         if ((*bitmap & bmmask11) != bmmask11) {
 948                                 if (modified == 0) {
 949                                         hammer2_chain_modify(trans, &chain, 0);
 950                                         modified = 1;
 951                                         goto again;
 952                                 }
 953                                 if ((*bitmap & bmmask11) == bmmask00)
 954                                         bmap->avail -= 1 << radix;
 955                                 if (bmap->class == 0)
 956                                         bmap->class = class;
 957                                 *bitmap |= bmmask11;
 958                                 if (hammer2_debug & 0x0040) {
 959                                         kprintf("hammer2_freemap_recover: "
 960                                                 "fixup type=%02x "
 961                                                 "block=%016jx/%zd\n",
 962                                                 bref->type, data_off, bytes);
 963                                 }
 964                         } else {
 965                                 /*
 966                                 kprintf("hammer2_freemap_recover:  good "
 967                                         "type=%02x block=%016jx/%zd\n",
 968                                         bref->type, data_off, bytes);
 969                                 */
 970                         }
 971                 } else if ((*bitmap & bmmask11) == bmmask11) {
 972                         /*
 973                          * Mayfree/Realfree request and bitmap is currently
 974                          * marked as being fully allocated.
 975                          */
 976                         if (!modified) {
 977                                 hammer2_chain_modify(trans, &chain, 0);
 978                                 modified = 1;
 979                                 goto again;
 980                         }
 981                         if (how == HAMMER2_FREEMAP_DOREALFREE)
 982                                 *bitmap &= ~bmmask11;
 983                         else
 984                                 *bitmap = (*bitmap & ~bmmask11) | bmmask10;
 985                 } else if ((*bitmap & bmmask11) == bmmask10) {
 986                         /*
 987                          * Mayfree/Realfree request and bitmap is currently
 988                          * marked as being possibly freeable.
 989                          */
 990                         if (how == HAMMER2_FREEMAP_DOREALFREE) {
 991                                 if (!modified) {
 992                                         hammer2_chain_modify(trans, &chain, 0);
 993                                         modified = 1;
 994                                         goto again;
 995                                 }
 996                                 *bitmap &= ~bmmask11;
 997                         }
 998                 } else {
 999                         /*
1000                          * 01 - Not implemented, currently illegal state
1001                          * 00 - Not allocated at all, illegal free.
1002                          */
1003                         panic("hammer2_freemap_adjust: "
1004                               "Illegal state %08x(%08x)",
1005                               *bitmap, *bitmap & bmmask11);
1006                 }
1007                 --count;
1008                 bmmask01 <<= 2;
1009                 bmmask10 <<= 2;
1010                 bmmask11 <<= 2;
1011         }
1012         if (how == HAMMER2_FREEMAP_DOREALFREE && modified) {
1013                 bmap->avail += 1 << radix;
1014                 KKASSERT(bmap->avail <= HAMMER2_SEGSIZE);
1015                 if (bmap->avail == HAMMER2_SEGSIZE &&
1016                     bmap->bitmap[0] == 0 &&
1017                     bmap->bitmap[1] == 0 &&
1018                     bmap->bitmap[2] == 0 &&
1019                     bmap->bitmap[3] == 0 &&
1020                     bmap->bitmap[4] == 0 &&
1021                     bmap->bitmap[5] == 0 &&
1022                     bmap->bitmap[6] == 0 &&
1023                     bmap->bitmap[7] == 0) {
1024                         key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL0_RADIX);
1025                         kprintf("Freeseg %016jx\n", (intmax_t)key);
1026                         bmap->class = 0;
1027                 }
1028         }
1029
1030         /*
1031          * chain->bref.check.freemap.bigmask (XXX)
1032          *
1033          * Setting bigmask is a hint to the allocation code that there might
1034          * be something allocatable.  We also set this in recovery... it
1035          * doesn't hurt and we might want to use the hint for other validation
1036          * operations later on.
1037          */
1038         if (modified)
1039                 chain->bref.check.freemap.bigmask |= 1 << radix;
1040
1041         hammer2_chain_unlock(chain);
1042 done:
1043         hammer2_chain_unlock(parent);
1044         atomic_clear_int(&trans->flags, HAMMER2_TRANS_ISALLOCATING);
1045         if (trans->flags & (HAMMER2_TRANS_ISFLUSH | HAMMER2_TRANS_PREFLUSH))
1046                 --trans->sync_tid;
1047 }