sys/vfs/hammer/hammer_blockmap.c

   1 /*
   2  * Copyright (c) 2008 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   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  * $DragonFly: src/sys/vfs/hammer/hammer_blockmap.c,v 1.23 2008/07/03 04:24:51 dillon Exp $
  35  */
  36
  37 /*
  38  * HAMMER blockmap
  39  */
  40 #include "hammer.h"
  41
  42 static int hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2);
  43 static int hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv,
  44                         hammer_off_t zone2_offset);
  45
  46
  47 /*
  48  * Reserved big-blocks red-black tree support
  49  */
  50 RB_GENERATE2(hammer_res_rb_tree, hammer_reserve, rb_node,
  51              hammer_res_rb_compare, hammer_off_t, zone_offset);
  52
  53 static int
  54 hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2)
  55 {
  56         if (res1->zone_offset < res2->zone_offset)
  57                 return(-1);
  58         if (res1->zone_offset > res2->zone_offset)
  59                 return(1);
  60         return(0);
  61 }
  62
  63 /*
  64  * Allocate bytes from a zone
  65  */
  66 hammer_off_t
  67 hammer_blockmap_alloc(hammer_transaction_t trans, int zone,
  68                       int bytes, int *errorp)
  69 {
  70         hammer_mount_t hmp;
  71         hammer_volume_t root_volume;
  72         hammer_blockmap_t blockmap;
  73         hammer_blockmap_t freemap;
  74         hammer_reserve_t resv;
  75         struct hammer_blockmap_layer1 *layer1;
  76         struct hammer_blockmap_layer2 *layer2;
  77         hammer_buffer_t buffer1 = NULL;
  78         hammer_buffer_t buffer2 = NULL;
  79         hammer_buffer_t buffer3 = NULL;
  80         hammer_off_t tmp_offset;
  81         hammer_off_t next_offset;
  82         hammer_off_t result_offset;
  83         hammer_off_t layer1_offset;
  84         hammer_off_t layer2_offset;
  85         hammer_off_t base_off;
  86         int loops = 0;
  87         int offset;             /* offset within big-block */
  88
  89         hmp = trans->hmp;
  90
  91         /*
  92          * Deal with alignment and buffer-boundary issues.
  93          *
  94          * Be careful, certain primary alignments are used below to allocate
  95          * new blockmap blocks.
  96          */
  97         bytes = (bytes + 15) & ~15;
  98         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
  99         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 100
 101         /*
 102          * Setup
 103          */
 104         root_volume = trans->rootvol;
 105         *errorp = 0;
 106         blockmap = &hmp->blockmap[zone];
 107         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 108         KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
 109
 110         next_offset = blockmap->next_offset;
 111 again:
 112         /*
 113          * Check for wrap
 114          */
 115         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
 116                 if (++loops == 2) {
 117                         result_offset = 0;
 118                         *errorp = ENOSPC;
 119                         goto failed;
 120                 }
 121                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
 122         }
 123
 124         /*
 125          * The allocation request may not cross a buffer boundary.  Special
 126          * large allocations must not cross a large-block boundary.
 127          */
 128         tmp_offset = next_offset + bytes - 1;
 129         if (bytes <= HAMMER_BUFSIZE) {
 130                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
 131                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
 132                         goto again;
 133                 }
 134         } else {
 135                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
 136                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
 137                         goto again;
 138                 }
 139         }
 140         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
 141
 142         /*
 143          * Dive layer 1.
 144          */
 145         layer1_offset = freemap->phys_offset +
 146                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
 147         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
 148         KKASSERT(*errorp == 0);
 149
 150         /*
 151          * Check CRC.
 152          */
 153         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 154                 Debugger("CRC FAILED: LAYER1");
 155         }
 156
 157         /*
 158          * If we are at a big-block boundary and layer1 indicates no
 159          * free big-blocks, then we cannot allocate a new bigblock in
 160          * layer2, skip to the next layer1 entry.
 161          */
 162         if (offset == 0 && layer1->blocks_free == 0) {
 163                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
 164                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
 165                 goto again;
 166         }
 167         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 168
 169         /*
 170          * Dive layer 2, each entry represents a large-block.
 171          */
 172         layer2_offset = layer1->phys_offset +
 173                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
 174         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
 175         KKASSERT(*errorp == 0);
 176
 177         /*
 178          * Check CRC.
 179          */
 180         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 181                 Debugger("CRC FAILED: LAYER2");
 182         }
 183
 184         /*
 185          * Skip the layer if the zone is owned by someone other then us.
 186          */
 187         if (layer2->zone && layer2->zone != zone) {
 188                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
 189                 goto again;
 190         }
 191         if (offset < layer2->append_off) {
 192                 next_offset += layer2->append_off - offset;
 193                 goto again;
 194         }
 195
 196         /*
 197          * We need the lock from this point on.  We have to re-check zone
 198          * ownership after acquiring the lock and also check for reservations.
 199          */
 200         hammer_lock_ex(&hmp->blkmap_lock);
 201
 202         if (layer2->zone && layer2->zone != zone) {
 203                 hammer_unlock(&hmp->blkmap_lock);
 204                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
 205                 goto again;
 206         }
 207         if (offset < layer2->append_off) {
 208                 hammer_unlock(&hmp->blkmap_lock);
 209                 next_offset += layer2->append_off - offset;
 210                 goto again;
 211         }
 212
 213         /*
 214          * The bigblock might be reserved by another zone.  If it is reserved
 215          * by our zone we may have to move next_offset past the append_off.
 216          */
 217         base_off = (next_offset &
 218                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
 219                     HAMMER_ZONE_RAW_BUFFER;
 220         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
 221         if (resv) {
 222                 if (resv->zone != zone) {
 223                         hammer_unlock(&hmp->blkmap_lock);
 224                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
 225                                       ~HAMMER_LARGEBLOCK_MASK64;
 226                         goto again;
 227                 }
 228                 if (offset < resv->append_off) {
 229                         hammer_unlock(&hmp->blkmap_lock);
 230                         next_offset += resv->append_off - offset;
 231                         goto again;
 232                 }
 233         }
 234
 235         /*
 236          * Ok, we can allocate out of this layer2 big-block.  Assume ownership
 237          * of the layer for real.  At this point we've validated any
 238          * reservation that might exist and can just ignore resv.
 239          */
 240         if (layer2->zone == 0) {
 241                 /*
 242                  * Assign the bigblock to our zone
 243                  */
 244                 hammer_modify_buffer(trans, buffer1,
 245                                      layer1, sizeof(*layer1));
 246                 --layer1->blocks_free;
 247                 layer1->layer1_crc = crc32(layer1,
 248                                            HAMMER_LAYER1_CRCSIZE);
 249                 hammer_modify_buffer_done(buffer1);
 250                 hammer_modify_buffer(trans, buffer2,
 251                                      layer2, sizeof(*layer2));
 252                 layer2->zone = zone;
 253                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
 254                 KKASSERT(layer2->append_off == 0);
 255                 hammer_modify_volume_field(trans, trans->rootvol,
 256                                            vol0_stat_freebigblocks);
 257                 --root_volume->ondisk->vol0_stat_freebigblocks;
 258                 hmp->copy_stat_freebigblocks =
 259                         root_volume->ondisk->vol0_stat_freebigblocks;
 260                 hammer_modify_volume_done(trans->rootvol);
 261         } else {
 262                 hammer_modify_buffer(trans, buffer2,
 263                                      layer2, sizeof(*layer2));
 264         }
 265         KKASSERT(layer2->zone == zone);
 266
 267         layer2->bytes_free -= bytes;
 268         KKASSERT(layer2->append_off <= offset);
 269         layer2->append_off = offset + bytes;
 270         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 271         hammer_modify_buffer_done(buffer2);
 272         KKASSERT(layer2->bytes_free >= 0);
 273
 274         if (resv) {
 275                 KKASSERT(resv->append_off <= offset);
 276                 resv->append_off = offset + bytes;
 277         }
 278
 279         /*
 280          * If we are allocating from the base of a new buffer we can avoid
 281          * a disk read by calling hammer_bnew().
 282          */
 283         if ((next_offset & HAMMER_BUFMASK) == 0) {
 284                 hammer_bnew_ext(trans->hmp, next_offset, bytes,
 285                                 errorp, &buffer3);
 286         }
 287         result_offset = next_offset;
 288
 289         /*
 290          * Process allocated result_offset
 291          */
 292         hammer_modify_volume(NULL, root_volume, NULL, 0);
 293         blockmap->next_offset = next_offset + bytes;
 294         hammer_modify_volume_done(root_volume);
 295         hammer_unlock(&hmp->blkmap_lock);
 296 failed:
 297
 298         /*
 299          * Cleanup
 300          */
 301         if (buffer1)
 302                 hammer_rel_buffer(buffer1, 0);
 303         if (buffer2)
 304                 hammer_rel_buffer(buffer2, 0);
 305         if (buffer3)
 306                 hammer_rel_buffer(buffer3, 0);
 307
 308         return(result_offset);
 309 }
 310
 311 /*
 312  * Frontend function - Reserve bytes in a zone.
 313  *
 314  * This code reserves bytes out of a blockmap without committing to any
 315  * meta-data modifications, allowing the front-end to directly issue disk
 316  * write I/O for large blocks of data
 317  *
 318  * The backend later finalizes the reservation with hammer_blockmap_finalize()
 319  * upon committing the related record.
 320  */
 321 hammer_reserve_t
 322 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
 323                         hammer_off_t *zone_offp, int *errorp)
 324 {
 325         hammer_volume_t root_volume;
 326         hammer_blockmap_t blockmap;
 327         hammer_blockmap_t freemap;
 328         struct hammer_blockmap_layer1 *layer1;
 329         struct hammer_blockmap_layer2 *layer2;
 330         hammer_buffer_t buffer1 = NULL;
 331         hammer_buffer_t buffer2 = NULL;
 332         hammer_buffer_t buffer3 = NULL;
 333         hammer_off_t tmp_offset;
 334         hammer_off_t next_offset;
 335         hammer_off_t layer1_offset;
 336         hammer_off_t layer2_offset;
 337         hammer_off_t base_off;
 338         hammer_reserve_t resv;
 339         hammer_reserve_t resx;
 340         int loops = 0;
 341         int offset;
 342
 343         /*
 344          * Setup
 345          */
 346         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 347         root_volume = hammer_get_root_volume(hmp, errorp);
 348         if (*errorp)
 349                 return(NULL);
 350         blockmap = &hmp->blockmap[zone];
 351         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 352         KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
 353
 354         /*
 355          * Deal with alignment and buffer-boundary issues.
 356          *
 357          * Be careful, certain primary alignments are used below to allocate
 358          * new blockmap blocks.
 359          */
 360         bytes = (bytes + 15) & ~15;
 361         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
 362
 363         next_offset = blockmap->next_offset;
 364 again:
 365         resv = NULL;
 366         /*
 367          * Check for wrap
 368          */
 369         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
 370                 if (++loops == 2) {
 371                         *errorp = ENOSPC;
 372                         goto failed;
 373                 }
 374                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
 375         }
 376
 377         /*
 378          * The allocation request may not cross a buffer boundary.  Special
 379          * large allocations must not cross a large-block boundary.
 380          */
 381         tmp_offset = next_offset + bytes - 1;
 382         if (bytes <= HAMMER_BUFSIZE) {
 383                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
 384                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
 385                         goto again;
 386                 }
 387         } else {
 388                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
 389                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
 390                         goto again;
 391                 }
 392         }
 393         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
 394
 395         /*
 396          * Dive layer 1.
 397          */
 398         layer1_offset = freemap->phys_offset +
 399                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
 400         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
 401         KKASSERT(*errorp == 0);
 402
 403         /*
 404          * Check CRC.
 405          */
 406         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 407                 Debugger("CRC FAILED: LAYER1");
 408         }
 409
 410         /*
 411          * If we are at a big-block boundary and layer1 indicates no
 412          * free big-blocks, then we cannot allocate a new bigblock in
 413          * layer2, skip to the next layer1 entry.
 414          */
 415         if ((next_offset & HAMMER_LARGEBLOCK_MASK) == 0 &&
 416             layer1->blocks_free == 0) {
 417                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
 418                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
 419                 goto again;
 420         }
 421         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 422
 423         /*
 424          * Dive layer 2, each entry represents a large-block.
 425          */
 426         layer2_offset = layer1->phys_offset +
 427                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
 428         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
 429         KKASSERT(*errorp == 0);
 430
 431         /*
 432          * Check CRC if not allocating into uninitialized space (which we
 433          * aren't when reserving space).
 434          */
 435         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 436                 Debugger("CRC FAILED: LAYER2");
 437         }
 438
 439         /*
 440          * Skip the layer if the zone is owned by someone other then us.
 441          */
 442         if (layer2->zone && layer2->zone != zone) {
 443                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
 444                 goto again;
 445         }
 446         if (offset < layer2->append_off) {
 447                 next_offset += layer2->append_off - offset;
 448                 goto again;
 449         }
 450
 451         /*
 452          * We need the lock from this point on.  We have to re-check zone
 453          * ownership after acquiring the lock and also check for reservations.
 454          */
 455         hammer_lock_ex(&hmp->blkmap_lock);
 456
 457         if (layer2->zone && layer2->zone != zone) {
 458                 hammer_unlock(&hmp->blkmap_lock);
 459                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
 460                 goto again;
 461         }
 462         if (offset < layer2->append_off) {
 463                 hammer_unlock(&hmp->blkmap_lock);
 464                 next_offset += layer2->append_off - offset;
 465                 goto again;
 466         }
 467
 468         /*
 469          * The bigblock might be reserved by another zone.  If it is reserved
 470          * by our zone we may have to move next_offset past the append_off.
 471          */
 472         base_off = (next_offset &
 473                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
 474                     HAMMER_ZONE_RAW_BUFFER;
 475         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
 476         if (resv) {
 477                 if (resv->zone != zone) {
 478                         hammer_unlock(&hmp->blkmap_lock);
 479                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
 480                                       ~HAMMER_LARGEBLOCK_MASK64;
 481                         goto again;
 482                 }
 483                 if (offset < resv->append_off) {
 484                         hammer_unlock(&hmp->blkmap_lock);
 485                         next_offset += resv->append_off - offset;
 486                         goto again;
 487                 }
 488                 ++resv->refs;
 489                 resx = NULL;
 490         } else {
 491                 resx = kmalloc(sizeof(*resv), M_HAMMER,
 492                                M_WAITOK | M_ZERO | M_USE_RESERVE);
 493                 resx->refs = 1;
 494                 resx->zone = zone;
 495                 resx->zone_offset = base_off;
 496                 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
 497                 KKASSERT(resv == NULL);
 498                 resv = resx;
 499                 ++hammer_count_reservations;
 500         }
 501         resv->append_off = offset + bytes;
 502
 503         /*
 504          * If we are not reserving a whole buffer but are at the start of
 505          * a new block, call hammer_bnew() to avoid a disk read.
 506          *
 507          * If we are reserving a whole buffer (or more), the caller will
 508          * probably use a direct read, so do nothing.
 509          */
 510         if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
 511                 hammer_bnew(hmp, next_offset, errorp, &buffer3);
 512         }
 513
 514         /*
 515          * Adjust our iterator and alloc_offset.  The layer1 and layer2
 516          * space beyond alloc_offset is uninitialized.  alloc_offset must
 517          * be big-block aligned.
 518          */
 519         blockmap->next_offset = next_offset + bytes;
 520         hammer_unlock(&hmp->blkmap_lock);
 521
 522 failed:
 523         if (buffer1)
 524                 hammer_rel_buffer(buffer1, 0);
 525         if (buffer2)
 526                 hammer_rel_buffer(buffer2, 0);
 527         if (buffer3)
 528                 hammer_rel_buffer(buffer3, 0);
 529         hammer_rel_volume(root_volume, 0);
 530         *zone_offp = next_offset;
 531
 532         return(resv);
 533 }
 534
 535 /*
 536  * A record with a storage reservation calls this function when it is
 537  * being freed.  The storage may or may not have actually been allocated.
 538  *
 539  * This function removes the lock that prevented other entities from
 540  * allocating out of the storage or removing the zone assignment.
 541  */
 542 void
 543 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
 544 {
 545         KKASSERT(resv->refs > 0);
 546         if (--resv->refs == 0) {
 547                 KKASSERT((resv->flags & HAMMER_RESF_ONDELAY) == 0);
 548                 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
 549                 kfree(resv, M_HAMMER);
 550                 --hammer_count_reservations;
 551         }
 552 }
 553
 554 /*
 555  * This ensures that no data reallocations will take place at the specified
 556  * zone2_offset (pointing to the base of a bigblock) for 2 flush cycles,
 557  * preventing deleted data space, which has no UNDO, from being reallocated
 558  * too quickly.
 559  */
 560 static int
 561 hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv,
 562                         hammer_off_t zone2_offset)
 563 {
 564         int error;
 565
 566         if (resv == NULL) {
 567                 resv = kmalloc(sizeof(*resv), M_HAMMER,
 568                                M_WAITOK | M_ZERO | M_USE_RESERVE);
 569                 resv->refs = 1; /* ref for on-delay list */
 570                 resv->zone_offset = zone2_offset;
 571                 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
 572                 if (RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv)) {
 573                         error = EAGAIN;
 574                         kfree(resv, M_HAMMER);
 575                 } else {
 576                         error = 0;
 577                         ++hammer_count_reservations;
 578                 }
 579         } else if (resv->flags & HAMMER_RESF_ONDELAY) {
 580                 --hmp->rsv_fromdelay;
 581                 resv->flags &= ~HAMMER_RESF_ONDELAY;
 582                 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
 583                 resv->flush_group = hmp->flusher.next + 1;
 584                 error = 0;
 585         } else {
 586                 ++resv->refs;   /* ref for on-delay list */
 587                 error = 0;
 588         }
 589         if (error == 0) {
 590                 ++hmp->rsv_fromdelay;
 591                 resv->flags |= HAMMER_RESF_ONDELAY;
 592                 resv->flush_group = hmp->flusher.next + 1;
 593                 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
 594         }
 595         return(error);
 596 }
 597
 598 void
 599 hammer_reserve_clrdelay(hammer_mount_t hmp, hammer_reserve_t resv)
 600 {
 601         KKASSERT(resv->flags & HAMMER_RESF_ONDELAY);
 602         resv->flags &= ~HAMMER_RESF_ONDELAY;
 603         TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
 604         --hmp->rsv_fromdelay;
 605         hammer_blockmap_reserve_complete(hmp, resv);
 606 }
 607
 608 /*
 609  * Backend function - free (offset, bytes) in a zone.
 610  */
 611 void
 612 hammer_blockmap_free(hammer_transaction_t trans,
 613                      hammer_off_t zone_offset, int bytes)
 614 {
 615         hammer_mount_t hmp;
 616         hammer_volume_t root_volume;
 617         hammer_reserve_t resv;
 618         hammer_blockmap_t blockmap;
 619         hammer_blockmap_t freemap;
 620         struct hammer_blockmap_layer1 *layer1;
 621         struct hammer_blockmap_layer2 *layer2;
 622         hammer_buffer_t buffer1 = NULL;
 623         hammer_buffer_t buffer2 = NULL;
 624         hammer_off_t layer1_offset;
 625         hammer_off_t layer2_offset;
 626         hammer_off_t base_off;
 627         int error;
 628         int zone;
 629
 630         if (bytes == 0)
 631                 return;
 632         hmp = trans->hmp;
 633
 634         /*
 635          * Alignment
 636          */
 637         bytes = (bytes + 15) & ~15;
 638         KKASSERT(bytes <= HAMMER_XBUFSIZE);
 639         KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) &
 640                   ~HAMMER_LARGEBLOCK_MASK64) == 0);
 641
 642         /*
 643          * Basic zone validation & locking
 644          */
 645         zone = HAMMER_ZONE_DECODE(zone_offset);
 646         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 647         root_volume = trans->rootvol;
 648         error = 0;
 649
 650         blockmap = &hmp->blockmap[zone];
 651         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 652
 653         /*
 654          * Dive layer 1.
 655          */
 656         layer1_offset = freemap->phys_offset +
 657                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 658         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
 659         KKASSERT(error == 0);
 660         KKASSERT(layer1->phys_offset &&
 661                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 662         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 663                 Debugger("CRC FAILED: LAYER1");
 664         }
 665
 666         /*
 667          * Dive layer 2, each entry represents a large-block.
 668          */
 669         layer2_offset = layer1->phys_offset +
 670                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 671         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
 672         KKASSERT(error == 0);
 673         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 674                 Debugger("CRC FAILED: LAYER2");
 675         }
 676
 677         hammer_lock_ex(&hmp->blkmap_lock);
 678
 679         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
 680
 681         /*
 682          * Freeing previously allocated space
 683          */
 684         KKASSERT(layer2->zone == zone);
 685         layer2->bytes_free += bytes;
 686         KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
 687         if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
 688                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
 689 again:
 690                 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
 691                                  base_off);
 692                 if (resv) {
 693                         /*
 694                          * Portions of this block have been reserved, do
 695                          * not free it.
 696                          *
 697                          * Make sure the reservation remains through
 698                          * the next flush cycle so potentially undoable
 699                          * data is not overwritten.
 700                          */
 701                         KKASSERT(resv->zone == zone);
 702                         hammer_reserve_setdelay(hmp, resv, base_off);
 703                 } else if ((blockmap->next_offset ^ zone_offset) &
 704                             ~HAMMER_LARGEBLOCK_MASK64) {
 705                         /*
 706                          * Our iterator is not in the now-free big-block
 707                          * and we can release it.
 708                          *
 709                          * Make sure the reservation remains through
 710                          * the next flush cycle so potentially undoable
 711                          * data is not overwritten.
 712                          */
 713                         if (hammer_reserve_setdelay(hmp, resv, base_off))
 714                                 goto again;
 715                         KKASSERT(layer2->zone == zone);
 716                         hammer_del_buffers(hmp,
 717                                            zone_offset &
 718                                               ~HAMMER_LARGEBLOCK_MASK64,
 719                                            base_off,
 720                                            HAMMER_LARGEBLOCK_SIZE);
 721                         layer2->zone = 0;
 722                         layer2->append_off = 0;
 723                         hammer_modify_buffer(trans, buffer1,
 724                                              layer1, sizeof(*layer1));
 725                         ++layer1->blocks_free;
 726                         layer1->layer1_crc = crc32(layer1,
 727                                                    HAMMER_LAYER1_CRCSIZE);
 728                         hammer_modify_buffer_done(buffer1);
 729                         hammer_modify_volume_field(trans,
 730                                         trans->rootvol,
 731                                         vol0_stat_freebigblocks);
 732                         ++root_volume->ondisk->vol0_stat_freebigblocks;
 733                         hmp->copy_stat_freebigblocks =
 734                            root_volume->ondisk->vol0_stat_freebigblocks;
 735                         hammer_modify_volume_done(trans->rootvol);
 736                 }
 737         }
 738
 739         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 740         hammer_modify_buffer_done(buffer2);
 741         hammer_unlock(&hmp->blkmap_lock);
 742
 743         if (buffer1)
 744                 hammer_rel_buffer(buffer1, 0);
 745         if (buffer2)
 746                 hammer_rel_buffer(buffer2, 0);
 747 }
 748
 749 /*
 750  * Backend function - finalize (offset, bytes) in a zone.
 751  *
 752  * Allocate space that was previously reserved by the frontend.
 753  */
 754 void
 755 hammer_blockmap_finalize(hammer_transaction_t trans,
 756                          hammer_off_t zone_offset, int bytes)
 757 {
 758         hammer_mount_t hmp;
 759         hammer_volume_t root_volume;
 760         hammer_blockmap_t blockmap;
 761         hammer_blockmap_t freemap;
 762         struct hammer_blockmap_layer1 *layer1;
 763         struct hammer_blockmap_layer2 *layer2;
 764         hammer_buffer_t buffer1 = NULL;
 765         hammer_buffer_t buffer2 = NULL;
 766         hammer_off_t layer1_offset;
 767         hammer_off_t layer2_offset;
 768         int error;
 769         int zone;
 770         int offset;
 771
 772         if (bytes == 0)
 773                 return;
 774         hmp = trans->hmp;
 775
 776         /*
 777          * Alignment
 778          */
 779         bytes = (bytes + 15) & ~15;
 780         KKASSERT(bytes <= HAMMER_XBUFSIZE);
 781
 782         /*
 783          * Basic zone validation & locking
 784          */
 785         zone = HAMMER_ZONE_DECODE(zone_offset);
 786         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 787         root_volume = trans->rootvol;
 788         error = 0;
 789
 790         blockmap = &hmp->blockmap[zone];
 791         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 792
 793         /*
 794          * Dive layer 1.
 795          */
 796         layer1_offset = freemap->phys_offset +
 797                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 798         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
 799         KKASSERT(error == 0);
 800         KKASSERT(layer1->phys_offset &&
 801                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 802         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 803                 Debugger("CRC FAILED: LAYER1");
 804         }
 805
 806         /*
 807          * Dive layer 2, each entry represents a large-block.
 808          */
 809         layer2_offset = layer1->phys_offset +
 810                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 811         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
 812         KKASSERT(error == 0);
 813         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 814                 Debugger("CRC FAILED: LAYER2");
 815         }
 816
 817         hammer_lock_ex(&hmp->blkmap_lock);
 818
 819         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
 820
 821         /*
 822          * Finalize some or all of the space covered by a current
 823          * reservation.  An allocation in the same layer may have
 824          * already assigned ownership.
 825          */
 826         if (layer2->zone == 0) {
 827                 hammer_modify_buffer(trans, buffer1,
 828                                      layer1, sizeof(*layer1));
 829                 --layer1->blocks_free;
 830                 layer1->layer1_crc = crc32(layer1,
 831                                            HAMMER_LAYER1_CRCSIZE);
 832                 hammer_modify_buffer_done(buffer1);
 833                 layer2->zone = zone;
 834                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
 835                 KKASSERT(layer2->append_off == 0);
 836                 hammer_modify_volume_field(trans,
 837                                 trans->rootvol,
 838                                 vol0_stat_freebigblocks);
 839                 --root_volume->ondisk->vol0_stat_freebigblocks;
 840                 hmp->copy_stat_freebigblocks =
 841                    root_volume->ondisk->vol0_stat_freebigblocks;
 842                 hammer_modify_volume_done(trans->rootvol);
 843         }
 844         if (layer2->zone != zone)
 845                 kprintf("layer2 zone mismatch %d %d\n", layer2->zone, zone);
 846         KKASSERT(layer2->zone == zone);
 847         layer2->bytes_free -= bytes;
 848
 849         /*
 850          * Finalizations can occur out of order, or combined with allocations.
 851          * append_off must be set to the highest allocated offset.
 852          */
 853         offset = ((int)zone_offset & HAMMER_LARGEBLOCK_MASK) + bytes;
 854         if (layer2->append_off < offset)
 855                 layer2->append_off = offset;
 856
 857         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 858         hammer_modify_buffer_done(buffer2);
 859         hammer_unlock(&hmp->blkmap_lock);
 860
 861         if (buffer1)
 862                 hammer_rel_buffer(buffer1, 0);
 863         if (buffer2)
 864                 hammer_rel_buffer(buffer2, 0);
 865 }
 866
 867 /*
 868  * Return the number of free bytes in the big-block containing the
 869  * specified blockmap offset.
 870  */
 871 int
 872 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t zone_offset,
 873                         int *curp, int *errorp)
 874 {
 875         hammer_volume_t root_volume;
 876         hammer_blockmap_t blockmap;
 877         hammer_blockmap_t freemap;
 878         struct hammer_blockmap_layer1 *layer1;
 879         struct hammer_blockmap_layer2 *layer2;
 880         hammer_buffer_t buffer = NULL;
 881         hammer_off_t layer1_offset;
 882         hammer_off_t layer2_offset;
 883         int bytes;
 884         int zone;
 885
 886         zone = HAMMER_ZONE_DECODE(zone_offset);
 887         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 888         root_volume = hammer_get_root_volume(hmp, errorp);
 889         if (*errorp) {
 890                 *curp = 0;
 891                 return(0);
 892         }
 893         blockmap = &hmp->blockmap[zone];
 894         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 895
 896         /*
 897          * Dive layer 1.
 898          */
 899         layer1_offset = freemap->phys_offset +
 900                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 901         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
 902         KKASSERT(*errorp == 0);
 903         KKASSERT(layer1->phys_offset);
 904         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 905                 Debugger("CRC FAILED: LAYER1");
 906         }
 907
 908         /*
 909          * Dive layer 2, each entry represents a large-block.
 910          */
 911         layer2_offset = layer1->phys_offset +
 912                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 913         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
 914         KKASSERT(*errorp == 0);
 915         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 916                 Debugger("CRC FAILED: LAYER2");
 917         }
 918         KKASSERT(layer2->zone == zone);
 919
 920         bytes = layer2->bytes_free;
 921
 922         if ((blockmap->next_offset ^ zone_offset) & ~HAMMER_LARGEBLOCK_MASK64)
 923                 *curp = 0;
 924         else
 925                 *curp = 1;
 926         if (buffer)
 927                 hammer_rel_buffer(buffer, 0);
 928         hammer_rel_volume(root_volume, 0);
 929         if (hammer_debug_general & 0x0800) {
 930                 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
 931                         zone_offset, bytes);
 932         }
 933         return(bytes);
 934 }
 935
 936
 937 /*
 938  * Lookup a blockmap offset.
 939  */
 940 hammer_off_t
 941 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t zone_offset,
 942                        int *errorp)
 943 {
 944         hammer_volume_t root_volume;
 945         hammer_blockmap_t freemap;
 946         struct hammer_blockmap_layer1 *layer1;
 947         struct hammer_blockmap_layer2 *layer2;
 948         hammer_buffer_t buffer = NULL;
 949         hammer_off_t layer1_offset;
 950         hammer_off_t layer2_offset;
 951         hammer_off_t result_offset;
 952         hammer_off_t base_off;
 953         hammer_reserve_t resv;
 954         int zone;
 955
 956         /*
 957          * Calculate the zone-2 offset.
 958          */
 959         zone = HAMMER_ZONE_DECODE(zone_offset);
 960         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 961
 962         result_offset = (zone_offset & ~HAMMER_OFF_ZONE_MASK) |
 963                         HAMMER_ZONE_RAW_BUFFER;
 964
 965         /*
 966          * We can actually stop here, normal blockmaps are now direct-mapped
 967          * onto the freemap and so represent zone-2 addresses.
 968          */
 969         if (hammer_verify_zone == 0) {
 970                 *errorp = 0;
 971                 return(result_offset);
 972         }
 973
 974         /*
 975          * Validate the allocation zone
 976          */
 977         root_volume = hammer_get_root_volume(hmp, errorp);
 978         if (*errorp)
 979                 return(0);
 980         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 981         KKASSERT(freemap->phys_offset != 0);
 982
 983         /*
 984          * Dive layer 1.
 985          */
 986         layer1_offset = freemap->phys_offset +
 987                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 988         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
 989         KKASSERT(*errorp == 0);
 990         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 991         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 992                 Debugger("CRC FAILED: LAYER1");
 993         }
 994
 995         /*
 996          * Dive layer 2, each entry represents a large-block.
 997          */
 998         layer2_offset = layer1->phys_offset +
 999                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1000         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1001
1002         KKASSERT(*errorp == 0);
1003         if (layer2->zone == 0) {
1004                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
1005                 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
1006                                  base_off);
1007                 KKASSERT(resv && resv->zone == zone);
1008
1009         } else if (layer2->zone != zone) {
1010                 panic("hammer_blockmap_lookup: bad zone %d/%d\n",
1011                         layer2->zone, zone);
1012         }
1013         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1014                 Debugger("CRC FAILED: LAYER2");
1015         }
1016
1017         if (buffer)
1018                 hammer_rel_buffer(buffer, 0);
1019         hammer_rel_volume(root_volume, 0);
1020         if (hammer_debug_general & 0x0800) {
1021                 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
1022                         zone_offset, result_offset);
1023         }
1024         return(result_offset);
1025 }
1026
1027
1028 /*
1029  * Check space availability
1030  */
1031 int
1032 hammer_checkspace(hammer_mount_t hmp, int slop)
1033 {
1034         const int in_size = sizeof(struct hammer_inode_data) +
1035                             sizeof(union hammer_btree_elm);
1036         const int rec_size = (sizeof(union hammer_btree_elm) * 2);
1037         int64_t usedbytes;
1038
1039         /*
1040          * Hopefully a quick and fast check.
1041          */
1042         if (hmp->copy_stat_freebigblocks * HAMMER_LARGEBLOCK_SIZE >=
1043             (int64_t)hidirtybufspace * 4 + 10 * HAMMER_LARGEBLOCK_SIZE) {
1044                 hammer_count_extra_space_used = -1;
1045                 return(0);
1046         }
1047
1048         /*
1049          * Do a more involved check
1050          */
1051         usedbytes = hmp->rsv_inodes * in_size +
1052                     hmp->rsv_recs * rec_size +
1053                     hmp->rsv_databytes +
1054                     hmp->rsv_fromdelay * HAMMER_LARGEBLOCK_SIZE +
1055                     hidirtybufspace +
1056                     slop * HAMMER_LARGEBLOCK_SIZE;
1057
1058         hammer_count_extra_space_used = usedbytes;
1059
1060         if (hmp->copy_stat_freebigblocks >= usedbytes / HAMMER_LARGEBLOCK_SIZE)
1061                 return(0);
1062         return (ENOSPC);
1063 }
1064