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