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