The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/vfs/hammer/hammer_blockmap.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 
   35 /*
   36  * HAMMER blockmap
   37  */
   38 #include "hammer.h"
   39 
   40 static int hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2);
   41 static void hammer_reserve_setdelay_offset(hammer_mount_t hmp,
   42                                     hammer_off_t base_offset, int zone,
   43                                     struct hammer_blockmap_layer2 *layer2);
   44 static void hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv);
   45 static int update_bytes_free(hammer_reserve_t resv, int bytes);
   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, int bytes,
   68                       hammer_off_t hint, 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         int use_hint;
   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         /*
  112          * Use the hint if we have one.
  113          */
  114         if (hint && HAMMER_ZONE_DECODE(hint) == zone) {
  115                 next_offset = (hint + 15) & ~(hammer_off_t)15;
  116                 use_hint = 1;
  117         } else {
  118                 next_offset = blockmap->next_offset;
  119                 use_hint = 0;
  120         }
  121 again:
  122 
  123         /*
  124          * use_hint is turned off if we leave the hinted big-block.
  125          */
  126         if (use_hint && ((next_offset ^ hint) & ~HAMMER_HINTBLOCK_MASK64)) {
  127                 next_offset = blockmap->next_offset;
  128                 use_hint = 0;
  129         }
  130 
  131         /*
  132          * Check for wrap
  133          */
  134         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
  135                 if (++loops == 2) {
  136                         result_offset = 0;
  137                         *errorp = ENOSPC;
  138                         goto failed;
  139                 }
  140                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
  141         }
  142 
  143         /*
  144          * The allocation request may not cross a buffer boundary.  Special
  145          * large allocations must not cross a large-block boundary.
  146          */
  147         tmp_offset = next_offset + bytes - 1;
  148         if (bytes <= HAMMER_BUFSIZE) {
  149                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
  150                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
  151                         goto again;
  152                 }
  153         } else {
  154                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
  155                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
  156                         goto again;
  157                 }
  158         }
  159         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
  160 
  161         /*
  162          * Dive layer 1.
  163          */
  164         layer1_offset = freemap->phys_offset +
  165                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
  166 
  167         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
  168         if (*errorp) {
  169                 result_offset = 0;
  170                 goto failed;
  171         }
  172 
  173         /*
  174          * Check CRC.
  175          */
  176         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
  177                 hammer_lock_ex(&hmp->blkmap_lock);
  178                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
  179                         panic("CRC FAILED: LAYER1");
  180                 hammer_unlock(&hmp->blkmap_lock);
  181         }
  182 
  183         /*
  184          * If we are at a big-block boundary and layer1 indicates no 
  185          * free big-blocks, then we cannot allocate a new bigblock in
  186          * layer2, skip to the next layer1 entry.
  187          */
  188         if (offset == 0 && layer1->blocks_free == 0) {
  189                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
  190                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
  191                 goto again;
  192         }
  193         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
  194 
  195         /*
  196          * Skip this layer1 entry if it is pointing to a layer2 big-block
  197          * on a volume that we are currently trying to remove from the
  198          * file-system. This is used by the volume-del code together with
  199          * the reblocker to free up a volume.
  200          */
  201         if ((int)HAMMER_VOL_DECODE(layer1->phys_offset) ==
  202             hmp->volume_to_remove) {
  203                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
  204                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
  205                 goto again;
  206         }
  207 
  208         /*
  209          * Dive layer 2, each entry represents a large-block.
  210          */
  211         layer2_offset = layer1->phys_offset +
  212                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
  213         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
  214         if (*errorp) {
  215                 result_offset = 0;
  216                 goto failed;
  217         }
  218 
  219         /*
  220          * Check CRC.  This can race another thread holding the lock
  221          * and in the middle of modifying layer2.
  222          */
  223         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
  224                 hammer_lock_ex(&hmp->blkmap_lock);
  225                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
  226                         panic("CRC FAILED: LAYER2");
  227                 hammer_unlock(&hmp->blkmap_lock);
  228         }
  229 
  230         /*
  231          * Skip the layer if the zone is owned by someone other then us.
  232          */
  233         if (layer2->zone && layer2->zone != zone) {
  234                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
  235                 goto again;
  236         }
  237         if (offset < layer2->append_off) {
  238                 next_offset += layer2->append_off - offset;
  239                 goto again;
  240         }
  241 
  242 #if 0
  243         /*
  244          * If operating in the current non-hint blockmap block, do not
  245          * allow it to get over-full.  Also drop any active hinting so
  246          * blockmap->next_offset is updated at the end.
  247          *
  248          * We do this for B-Tree and meta-data allocations to provide
  249          * localization for updates.
  250          */
  251         if ((zone == HAMMER_ZONE_BTREE_INDEX ||
  252              zone == HAMMER_ZONE_META_INDEX) &&
  253             offset >= HAMMER_LARGEBLOCK_OVERFILL &&
  254             !((next_offset ^ blockmap->next_offset) & ~HAMMER_LARGEBLOCK_MASK64)
  255         ) {
  256                 if (offset >= HAMMER_LARGEBLOCK_OVERFILL) {
  257                         next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
  258                         use_hint = 0;
  259                         goto again;
  260                 }
  261         }
  262 #endif
  263 
  264         /*
  265          * We need the lock from this point on.  We have to re-check zone
  266          * ownership after acquiring the lock and also check for reservations.
  267          */
  268         hammer_lock_ex(&hmp->blkmap_lock);
  269 
  270         if (layer2->zone && layer2->zone != zone) {
  271                 hammer_unlock(&hmp->blkmap_lock);
  272                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
  273                 goto again;
  274         }
  275         if (offset < layer2->append_off) {
  276                 hammer_unlock(&hmp->blkmap_lock);
  277                 next_offset += layer2->append_off - offset;
  278                 goto again;
  279         }
  280 
  281         /*
  282          * The bigblock might be reserved by another zone.  If it is reserved
  283          * by our zone we may have to move next_offset past the append_off.
  284          */
  285         base_off = (next_offset &
  286                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | 
  287                     HAMMER_ZONE_RAW_BUFFER;
  288         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
  289         if (resv) {
  290                 if (resv->zone != zone) {
  291                         hammer_unlock(&hmp->blkmap_lock);
  292                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
  293                                       ~HAMMER_LARGEBLOCK_MASK64;
  294                         goto again;
  295                 }
  296                 if (offset < resv->append_off) {
  297                         hammer_unlock(&hmp->blkmap_lock);
  298                         next_offset += resv->append_off - offset;
  299                         goto again;
  300                 }
  301                 ++resv->refs;
  302         }
  303 
  304         /*
  305          * Ok, we can allocate out of this layer2 big-block.  Assume ownership
  306          * of the layer for real.  At this point we've validated any
  307          * reservation that might exist and can just ignore resv.
  308          */
  309         if (layer2->zone == 0) {
  310                 /*
  311                  * Assign the bigblock to our zone
  312                  */
  313                 hammer_modify_buffer(trans, buffer1,
  314                                      layer1, sizeof(*layer1));
  315                 --layer1->blocks_free;
  316                 layer1->layer1_crc = crc32(layer1,
  317                                            HAMMER_LAYER1_CRCSIZE);
  318                 hammer_modify_buffer_done(buffer1);
  319                 hammer_modify_buffer(trans, buffer2,
  320                                      layer2, sizeof(*layer2));
  321                 layer2->zone = zone;
  322                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
  323                 KKASSERT(layer2->append_off == 0);
  324                 hammer_modify_volume_field(trans, trans->rootvol,
  325                                            vol0_stat_freebigblocks);
  326                 --root_volume->ondisk->vol0_stat_freebigblocks;
  327                 hmp->copy_stat_freebigblocks =
  328                         root_volume->ondisk->vol0_stat_freebigblocks;
  329                 hammer_modify_volume_done(trans->rootvol);
  330         } else {
  331                 hammer_modify_buffer(trans, buffer2,
  332                                      layer2, sizeof(*layer2));
  333         }
  334         KKASSERT(layer2->zone == zone);
  335 
  336         /*
  337          * NOTE: bytes_free can legally go negative due to de-dup.
  338          */
  339         layer2->bytes_free -= bytes;
  340         KKASSERT(layer2->append_off <= offset);
  341         layer2->append_off = offset + bytes;
  342         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
  343         hammer_modify_buffer_done(buffer2);
  344 
  345         /*
  346          * We hold the blockmap lock and should be the only ones
  347          * capable of modifying resv->append_off.  Track the allocation
  348          * as appropriate.
  349          */
  350         KKASSERT(bytes != 0);
  351         if (resv) {
  352                 KKASSERT(resv->append_off <= offset);
  353                 resv->append_off = offset + bytes;
  354                 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
  355                 hammer_blockmap_reserve_complete(hmp, resv);
  356         }
  357 
  358         /*
  359          * If we are allocating from the base of a new buffer we can avoid
  360          * a disk read by calling hammer_bnew().
  361          */
  362         if ((next_offset & HAMMER_BUFMASK) == 0) {
  363                 hammer_bnew_ext(trans->hmp, next_offset, bytes,
  364                                 errorp, &buffer3);
  365         }
  366         result_offset = next_offset;
  367 
  368         /*
  369          * If we weren't supplied with a hint or could not use the hint
  370          * then we wound up using blockmap->next_offset as the hint and
  371          * need to save it.
  372          */
  373         if (use_hint == 0) {
  374                 hammer_modify_volume(NULL, root_volume, NULL, 0);
  375                 blockmap->next_offset = next_offset + bytes;
  376                 hammer_modify_volume_done(root_volume);
  377         }
  378         hammer_unlock(&hmp->blkmap_lock);
  379 failed:
  380 
  381         /*
  382          * Cleanup
  383          */
  384         if (buffer1)
  385                 hammer_rel_buffer(buffer1, 0);
  386         if (buffer2)
  387                 hammer_rel_buffer(buffer2, 0);
  388         if (buffer3)
  389                 hammer_rel_buffer(buffer3, 0);
  390 
  391         return(result_offset);
  392 }
  393 
  394 /*
  395  * Frontend function - Reserve bytes in a zone.
  396  *
  397  * This code reserves bytes out of a blockmap without committing to any
  398  * meta-data modifications, allowing the front-end to directly issue disk
  399  * write I/O for large blocks of data
  400  *
  401  * The backend later finalizes the reservation with hammer_blockmap_finalize()
  402  * upon committing the related record.
  403  */
  404 hammer_reserve_t
  405 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
  406                         hammer_off_t *zone_offp, int *errorp)
  407 {
  408         hammer_volume_t root_volume;
  409         hammer_blockmap_t blockmap;
  410         hammer_blockmap_t freemap;
  411         struct hammer_blockmap_layer1 *layer1;
  412         struct hammer_blockmap_layer2 *layer2;
  413         hammer_buffer_t buffer1 = NULL;
  414         hammer_buffer_t buffer2 = NULL;
  415         hammer_buffer_t buffer3 = NULL;
  416         hammer_off_t tmp_offset;
  417         hammer_off_t next_offset;
  418         hammer_off_t layer1_offset;
  419         hammer_off_t layer2_offset;
  420         hammer_off_t base_off;
  421         hammer_reserve_t resv;
  422         hammer_reserve_t resx;
  423         int loops = 0;
  424         int offset;
  425 
  426         /*
  427          * Setup
  428          */
  429         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
  430         root_volume = hammer_get_root_volume(hmp, errorp);
  431         if (*errorp)
  432                 return(NULL);
  433         blockmap = &hmp->blockmap[zone];
  434         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
  435         KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
  436 
  437         /*
  438          * Deal with alignment and buffer-boundary issues.
  439          *
  440          * Be careful, certain primary alignments are used below to allocate
  441          * new blockmap blocks.
  442          */
  443         bytes = (bytes + 15) & ~15;
  444         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
  445 
  446         next_offset = blockmap->next_offset;
  447 again:
  448         resv = NULL;
  449         /*
  450          * Check for wrap
  451          */
  452         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
  453                 if (++loops == 2) {
  454                         *errorp = ENOSPC;
  455                         goto failed;
  456                 }
  457                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
  458         }
  459 
  460         /*
  461          * The allocation request may not cross a buffer boundary.  Special
  462          * large allocations must not cross a large-block boundary.
  463          */
  464         tmp_offset = next_offset + bytes - 1;
  465         if (bytes <= HAMMER_BUFSIZE) {
  466                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
  467                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
  468                         goto again;
  469                 }
  470         } else {
  471                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
  472                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
  473                         goto again;
  474                 }
  475         }
  476         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
  477 
  478         /*
  479          * Dive layer 1.
  480          */
  481         layer1_offset = freemap->phys_offset +
  482                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
  483         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
  484         if (*errorp)
  485                 goto failed;
  486 
  487         /*
  488          * Check CRC.
  489          */
  490         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
  491                 hammer_lock_ex(&hmp->blkmap_lock);
  492                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
  493                         panic("CRC FAILED: LAYER1");
  494                 hammer_unlock(&hmp->blkmap_lock);
  495         }
  496 
  497         /*
  498          * If we are at a big-block boundary and layer1 indicates no 
  499          * free big-blocks, then we cannot allocate a new bigblock in
  500          * layer2, skip to the next layer1 entry.
  501          */
  502         if ((next_offset & HAMMER_LARGEBLOCK_MASK) == 0 &&
  503             layer1->blocks_free == 0) {
  504                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
  505                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
  506                 goto again;
  507         }
  508         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
  509 
  510         /*
  511          * Dive layer 2, each entry represents a large-block.
  512          */
  513         layer2_offset = layer1->phys_offset +
  514                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
  515         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
  516         if (*errorp)
  517                 goto failed;
  518 
  519         /*
  520          * Check CRC if not allocating into uninitialized space (which we
  521          * aren't when reserving space).
  522          */
  523         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
  524                 hammer_lock_ex(&hmp->blkmap_lock);
  525                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
  526                         panic("CRC FAILED: LAYER2");
  527                 hammer_unlock(&hmp->blkmap_lock);
  528         }
  529 
  530         /*
  531          * Skip the layer if the zone is owned by someone other then us.
  532          */
  533         if (layer2->zone && layer2->zone != zone) {
  534                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
  535                 goto again;
  536         }
  537         if (offset < layer2->append_off) {
  538                 next_offset += layer2->append_off - offset;
  539                 goto again;
  540         }
  541 
  542         /*
  543          * We need the lock from this point on.  We have to re-check zone
  544          * ownership after acquiring the lock and also check for reservations.
  545          */
  546         hammer_lock_ex(&hmp->blkmap_lock);
  547 
  548         if (layer2->zone && layer2->zone != zone) {
  549                 hammer_unlock(&hmp->blkmap_lock);
  550                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
  551                 goto again;
  552         }
  553         if (offset < layer2->append_off) {
  554                 hammer_unlock(&hmp->blkmap_lock);
  555                 next_offset += layer2->append_off - offset;
  556                 goto again;
  557         }
  558 
  559         /*
  560          * The bigblock might be reserved by another zone.  If it is reserved
  561          * by our zone we may have to move next_offset past the append_off.
  562          */
  563         base_off = (next_offset &
  564                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
  565                     HAMMER_ZONE_RAW_BUFFER;
  566         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
  567         if (resv) {
  568                 if (resv->zone != zone) {
  569                         hammer_unlock(&hmp->blkmap_lock);
  570                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
  571                                       ~HAMMER_LARGEBLOCK_MASK64;
  572                         goto again;
  573                 }
  574                 if (offset < resv->append_off) {
  575                         hammer_unlock(&hmp->blkmap_lock);
  576                         next_offset += resv->append_off - offset;
  577                         goto again;
  578                 }
  579                 ++resv->refs;
  580                 resx = NULL;
  581         } else {
  582                 resx = kmalloc(sizeof(*resv), hmp->m_misc,
  583                                M_WAITOK | M_ZERO | M_USE_RESERVE);
  584                 resx->refs = 1;
  585                 resx->zone = zone;
  586                 resx->zone_offset = base_off;
  587                 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
  588                         resx->flags |= HAMMER_RESF_LAYER2FREE;
  589                 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
  590                 KKASSERT(resv == NULL);
  591                 resv = resx;
  592                 ++hammer_count_reservations;
  593         }
  594         resv->append_off = offset + bytes;
  595 
  596         /*
  597          * If we are not reserving a whole buffer but are at the start of
  598          * a new block, call hammer_bnew() to avoid a disk read.
  599          *
  600          * If we are reserving a whole buffer (or more), the caller will
  601          * probably use a direct read, so do nothing.
  602          *
  603          * If we do not have a whole lot of system memory we really can't
  604          * afford to block while holding the blkmap_lock!
  605          */
  606         if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
  607                 if (!vm_page_count_min(HAMMER_BUFSIZE / PAGE_SIZE))
  608                         hammer_bnew(hmp, next_offset, errorp, &buffer3);
  609         }
  610 
  611         /*
  612          * Adjust our iterator and alloc_offset.  The layer1 and layer2
  613          * space beyond alloc_offset is uninitialized.  alloc_offset must
  614          * be big-block aligned.
  615          */
  616         blockmap->next_offset = next_offset + bytes;
  617         hammer_unlock(&hmp->blkmap_lock);
  618 
  619 failed:
  620         if (buffer1)
  621                 hammer_rel_buffer(buffer1, 0);
  622         if (buffer2)
  623                 hammer_rel_buffer(buffer2, 0);
  624         if (buffer3)
  625                 hammer_rel_buffer(buffer3, 0);
  626         hammer_rel_volume(root_volume, 0);
  627         *zone_offp = next_offset;
  628 
  629         return(resv);
  630 }
  631 
  632 /*
  633  * Frontend function - Dedup bytes in a zone.
  634  *
  635  * Dedup reservations work exactly the same as normal write reservations
  636  * except we only adjust bytes_free field and don't touch append offset.
  637  * Finalization mechanic for dedup reservations is also the same as for
  638  * normal write ones - the backend finalizes the reservation with
  639  * hammer_blockmap_finalize().
  640  */
  641 hammer_reserve_t
  642 hammer_blockmap_reserve_dedup(hammer_mount_t hmp, int zone, int bytes,
  643                               hammer_off_t zone_offset, int *errorp)
  644 {
  645         hammer_volume_t root_volume;
  646         hammer_blockmap_t freemap;
  647         struct hammer_blockmap_layer1 *layer1;
  648         struct hammer_blockmap_layer2 *layer2;
  649         hammer_buffer_t buffer1 = NULL;
  650         hammer_buffer_t buffer2 = NULL;
  651         hammer_off_t layer1_offset;
  652         hammer_off_t layer2_offset;
  653         hammer_off_t base_off;
  654         hammer_reserve_t resv = NULL;
  655         hammer_reserve_t resx = NULL;
  656 
  657         /*
  658          * Setup
  659          */
  660         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
  661         root_volume = hammer_get_root_volume(hmp, errorp);
  662         if (*errorp)
  663                 return (NULL);
  664         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
  665         KKASSERT(freemap->phys_offset != 0);
  666 
  667         bytes = (bytes + 15) & ~15;
  668         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
  669 
  670         /*
  671          * Dive layer 1.
  672          */
  673         layer1_offset = freemap->phys_offset +
  674                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
  675         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
  676         if (*errorp)
  677                 goto failed;
  678 
  679         /*
  680          * Check CRC.
  681          */
  682         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
  683                 hammer_lock_ex(&hmp->blkmap_lock);
  684                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
  685                         panic("CRC FAILED: LAYER1");
  686                 hammer_unlock(&hmp->blkmap_lock);
  687         }
  688         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
  689 
  690         /*
  691          * Dive layer 2, each entry represents a large-block.
  692          */
  693         layer2_offset = layer1->phys_offset +
  694                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
  695         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
  696         if (*errorp)
  697                 goto failed;
  698 
  699         /*
  700          * Check CRC.
  701          */
  702         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
  703                 hammer_lock_ex(&hmp->blkmap_lock);
  704                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
  705                         panic("CRC FAILED: LAYER2");
  706                 hammer_unlock(&hmp->blkmap_lock);
  707         }
  708 
  709         /*
  710          * Fail if the zone is owned by someone other than us.
  711          */
  712         if (layer2->zone && layer2->zone != zone)
  713                 goto failed;
  714 
  715         /*
  716          * We need the lock from this point on.  We have to re-check zone
  717          * ownership after acquiring the lock and also check for reservations.
  718          */
  719         hammer_lock_ex(&hmp->blkmap_lock);
  720 
  721         if (layer2->zone && layer2->zone != zone) {
  722                 hammer_unlock(&hmp->blkmap_lock);
  723                 goto failed;
  724         }
  725 
  726         base_off = (zone_offset &
  727                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
  728                     HAMMER_ZONE_RAW_BUFFER;
  729         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
  730         if (resv) {
  731                 if (resv->zone != zone) {
  732                         hammer_unlock(&hmp->blkmap_lock);
  733                         resv = NULL;
  734                         goto failed;
  735                 }
  736                 /*
  737                  * Due to possible big block underflow we can't simply
  738                  * subtract bytes from bytes_free.
  739                  */
  740                 if (update_bytes_free(resv, bytes) == 0) {
  741                         hammer_unlock(&hmp->blkmap_lock);
  742                         resv = NULL;
  743                         goto failed;
  744                 }
  745                 ++resv->refs;
  746                 resx = NULL;
  747         } else {
  748                 resx = kmalloc(sizeof(*resv), hmp->m_misc,
  749                                M_WAITOK | M_ZERO | M_USE_RESERVE);
  750                 resx->refs = 1;
  751                 resx->zone = zone;
  752                 resx->bytes_free = layer2->bytes_free;
  753                 /*
  754                  * Due to possible big block underflow we can't simply
  755                  * subtract bytes from bytes_free.
  756                  */
  757                 if (update_bytes_free(resx, bytes) == 0) {
  758                         hammer_unlock(&hmp->blkmap_lock);
  759                         kfree(resx, hmp->m_misc);
  760                         goto failed;
  761                 }
  762                 resx->zone_offset = base_off;
  763                 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
  764                 KKASSERT(resv == NULL);
  765                 resv = resx;
  766                 ++hammer_count_reservations;
  767         }
  768 
  769         hammer_unlock(&hmp->blkmap_lock);
  770 
  771 failed:
  772         if (buffer1)
  773                 hammer_rel_buffer(buffer1, 0);
  774         if (buffer2)
  775                 hammer_rel_buffer(buffer2, 0);
  776         hammer_rel_volume(root_volume, 0);
  777 
  778         return(resv);
  779 }
  780 
  781 static int
  782 update_bytes_free(hammer_reserve_t resv, int bytes)
  783 {
  784         int32_t temp;
  785 
  786         /*
  787          * Big-block underflow check
  788          */
  789         temp = resv->bytes_free - HAMMER_LARGEBLOCK_SIZE * 2;
  790         cpu_ccfence(); /* XXX do we really need it ? */
  791         if (temp > resv->bytes_free) {
  792                 kprintf("BIGBLOCK UNDERFLOW\n");
  793                 return (0);
  794         }
  795 
  796         resv->bytes_free -= bytes;
  797         return (1);
  798 }
  799 
  800 /*
  801  * Dereference a reservation structure.  Upon the final release the
  802  * underlying big-block is checked and if it is entirely free we delete
  803  * any related HAMMER buffers to avoid potential conflicts with future
  804  * reuse of the big-block.
  805  */
  806 void
  807 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
  808 {
  809         hammer_off_t base_offset;
  810         int error;
  811 
  812         KKASSERT(resv->refs > 0);
  813         KKASSERT((resv->zone_offset & HAMMER_OFF_ZONE_MASK) ==
  814                  HAMMER_ZONE_RAW_BUFFER);
  815 
  816         /*
  817          * Setting append_off to the max prevents any new allocations
  818          * from occuring while we are trying to dispose of the reservation,
  819          * allowing us to safely delete any related HAMMER buffers.
  820          *
  821          * If we are unable to clean out all related HAMMER buffers we
  822          * requeue the delay.
  823          */
  824         if (resv->refs == 1 && (resv->flags & HAMMER_RESF_LAYER2FREE)) {
  825                 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
  826                 base_offset = resv->zone_offset & ~HAMMER_OFF_ZONE_MASK;
  827                 base_offset = HAMMER_ZONE_ENCODE(resv->zone, base_offset);
  828                 if (!TAILQ_EMPTY(&hmp->dedup_lru_list))
  829                         hammer_dedup_cache_inval(hmp, base_offset);
  830                 error = hammer_del_buffers(hmp, base_offset,
  831                                            resv->zone_offset,
  832                                            HAMMER_LARGEBLOCK_SIZE,
  833                                            1);
  834                 if (hammer_debug_general & 0x20000) {
  835                         kprintf("hammer: dellgblk %016jx error %d\n",
  836                                 (intmax_t)base_offset, error);
  837                 }
  838                 if (error)
  839                         hammer_reserve_setdelay(hmp, resv);
  840         }
  841         if (--resv->refs == 0) {
  842                 if (hammer_debug_general & 0x20000) {
  843                         kprintf("hammer: delresvr %016jx zone %02x\n",
  844                                 (intmax_t)resv->zone_offset, resv->zone);
  845                 }
  846                 KKASSERT((resv->flags & HAMMER_RESF_ONDELAY) == 0);
  847                 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
  848                 kfree(resv, hmp->m_misc);
  849                 --hammer_count_reservations;
  850         }
  851 }
  852 
  853 /*
  854  * Prevent a potentially free big-block from being reused until after
  855  * the related flushes have completely cycled, otherwise crash recovery
  856  * could resurrect a data block that was already reused and overwritten.
  857  *
  858  * The caller might reset the underlying layer2 entry's append_off to 0, so
  859  * our covering append_off must be set to max to prevent any reallocation
  860  * until after the flush delays complete, not to mention proper invalidation
  861  * of any underlying cached blocks.
  862  */
  863 static void
  864 hammer_reserve_setdelay_offset(hammer_mount_t hmp, hammer_off_t base_offset,
  865                         int zone, struct hammer_blockmap_layer2 *layer2)
  866 {
  867         hammer_reserve_t resv;
  868 
  869         /*
  870          * Allocate the reservation if necessary.
  871          *
  872          * NOTE: need lock in future around resv lookup/allocation and
  873          * the setdelay call, currently refs is not bumped until the call.
  874          */
  875 again:
  876         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_offset);
  877         if (resv == NULL) {
  878                 resv = kmalloc(sizeof(*resv), hmp->m_misc,
  879                                M_WAITOK | M_ZERO | M_USE_RESERVE);
  880                 resv->zone = zone;
  881                 resv->zone_offset = base_offset;
  882                 resv->refs = 0;
  883                 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
  884 
  885                 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
  886                         resv->flags |= HAMMER_RESF_LAYER2FREE;
  887                 if (RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv)) {
  888                         kfree(resv, hmp->m_misc);
  889                         goto again;
  890                 }
  891                 ++hammer_count_reservations;
  892         } else {
  893                 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
  894                         resv->flags |= HAMMER_RESF_LAYER2FREE;
  895         }
  896         hammer_reserve_setdelay(hmp, resv);
  897 }
  898 
  899 /*
  900  * Enter the reservation on the on-delay list, or move it if it
  901  * is already on the list.
  902  */
  903 static void
  904 hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv)
  905 {
  906         if (resv->flags & HAMMER_RESF_ONDELAY) {
  907                 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
  908                 resv->flush_group = hmp->flusher.next + 1;
  909                 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
  910         } else {
  911                 ++resv->refs;
  912                 ++hmp->rsv_fromdelay;
  913                 resv->flags |= HAMMER_RESF_ONDELAY;
  914                 resv->flush_group = hmp->flusher.next + 1;
  915                 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
  916         }
  917 }
  918 
  919 /*
  920  * Reserve has reached its flush point, remove it from the delay list
  921  * and finish it off.  hammer_blockmap_reserve_complete() inherits
  922  * the ondelay reference.
  923  */
  924 void
  925 hammer_reserve_clrdelay(hammer_mount_t hmp, hammer_reserve_t resv)
  926 {
  927         KKASSERT(resv->flags & HAMMER_RESF_ONDELAY);
  928         resv->flags &= ~HAMMER_RESF_ONDELAY;
  929         TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
  930         --hmp->rsv_fromdelay;
  931         hammer_blockmap_reserve_complete(hmp, resv);
  932 }
  933 
  934 /*
  935  * Backend function - free (offset, bytes) in a zone.
  936  *
  937  * XXX error return
  938  */
  939 void
  940 hammer_blockmap_free(hammer_transaction_t trans,
  941                      hammer_off_t zone_offset, int bytes)
  942 {
  943         hammer_mount_t hmp;
  944         hammer_volume_t root_volume;
  945         hammer_blockmap_t freemap;
  946         struct hammer_blockmap_layer1 *layer1;
  947         struct hammer_blockmap_layer2 *layer2;
  948         hammer_buffer_t buffer1 = NULL;
  949         hammer_buffer_t buffer2 = NULL;
  950         hammer_off_t layer1_offset;
  951         hammer_off_t layer2_offset;
  952         hammer_off_t base_off;
  953         int error;
  954         int zone;
  955 
  956         if (bytes == 0)
  957                 return;
  958         hmp = trans->hmp;
  959 
  960         /*
  961          * Alignment
  962          */
  963         bytes = (bytes + 15) & ~15;
  964         KKASSERT(bytes <= HAMMER_XBUFSIZE);
  965         KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) & 
  966                   ~HAMMER_LARGEBLOCK_MASK64) == 0);
  967 
  968         /*
  969          * Basic zone validation & locking
  970          */
  971         zone = HAMMER_ZONE_DECODE(zone_offset);
  972         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
  973         root_volume = trans->rootvol;
  974         error = 0;
  975 
  976         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
  977 
  978         /*
  979          * Dive layer 1.
  980          */
  981         layer1_offset = freemap->phys_offset +
  982                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
  983         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
  984         if (error)
  985                 goto failed;
  986         KKASSERT(layer1->phys_offset &&
  987                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
  988         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
  989                 hammer_lock_ex(&hmp->blkmap_lock);
  990                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
  991                         panic("CRC FAILED: LAYER1");
  992                 hammer_unlock(&hmp->blkmap_lock);
  993         }
  994 
  995         /*
  996          * Dive layer 2, each entry represents a large-block.
  997          */
  998         layer2_offset = layer1->phys_offset +
  999                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 1000         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
 1001         if (error)
 1002                 goto failed;
 1003         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 1004                 hammer_lock_ex(&hmp->blkmap_lock);
 1005                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
 1006                         panic("CRC FAILED: LAYER2");
 1007                 hammer_unlock(&hmp->blkmap_lock);
 1008         }
 1009 
 1010         hammer_lock_ex(&hmp->blkmap_lock);
 1011 
 1012         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
 1013 
 1014         /*
 1015          * Free space previously allocated via blockmap_alloc().
 1016          *
 1017          * NOTE: bytes_free can be and remain negative due to de-dup ops
 1018          *       but can never become larger than HAMMER_LARGEBLOCK_SIZE.
 1019          */
 1020         KKASSERT(layer2->zone == zone);
 1021         layer2->bytes_free += bytes;
 1022         KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
 1023 
 1024         /*
 1025          * If a big-block becomes entirely free we must create a covering
 1026          * reservation to prevent premature reuse.  Note, however, that
 1027          * the big-block and/or reservation may still have an append_off
 1028          * that allows further (non-reused) allocations.
 1029          *
 1030          * Once the reservation has been made we re-check layer2 and if
 1031          * the big-block is still entirely free we reset the layer2 entry.
 1032          * The reservation will prevent premature reuse.
 1033          *
 1034          * NOTE: hammer_buffer's are only invalidated when the reservation
 1035          * is completed, if the layer2 entry is still completely free at
 1036          * that time.  Any allocations from the reservation that may have
 1037          * occured in the mean time, or active references on the reservation
 1038          * from new pending allocations, will prevent the invalidation from
 1039          * occuring.
 1040          */
 1041         if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
 1042                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
 1043 
 1044                 hammer_reserve_setdelay_offset(hmp, base_off, zone, layer2);
 1045                 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
 1046                         layer2->zone = 0;
 1047                         layer2->append_off = 0;
 1048                         hammer_modify_buffer(trans, buffer1,
 1049                                              layer1, sizeof(*layer1));
 1050                         ++layer1->blocks_free;
 1051                         layer1->layer1_crc = crc32(layer1,
 1052                                                    HAMMER_LAYER1_CRCSIZE);
 1053                         hammer_modify_buffer_done(buffer1);
 1054                         hammer_modify_volume_field(trans,
 1055                                         trans->rootvol,
 1056                                         vol0_stat_freebigblocks);
 1057                         ++root_volume->ondisk->vol0_stat_freebigblocks;
 1058                         hmp->copy_stat_freebigblocks =
 1059                            root_volume->ondisk->vol0_stat_freebigblocks;
 1060                         hammer_modify_volume_done(trans->rootvol);
 1061                 }
 1062         }
 1063         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 1064         hammer_modify_buffer_done(buffer2);
 1065         hammer_unlock(&hmp->blkmap_lock);
 1066 
 1067 failed:
 1068         if (buffer1)
 1069                 hammer_rel_buffer(buffer1, 0);
 1070         if (buffer2)
 1071                 hammer_rel_buffer(buffer2, 0);
 1072 }
 1073 
 1074 int
 1075 hammer_blockmap_dedup(hammer_transaction_t trans,
 1076                      hammer_off_t zone_offset, int bytes)
 1077 {
 1078         hammer_mount_t hmp;
 1079         hammer_blockmap_t freemap;
 1080         struct hammer_blockmap_layer1 *layer1;
 1081         struct hammer_blockmap_layer2 *layer2;
 1082         hammer_buffer_t buffer1 = NULL;
 1083         hammer_buffer_t buffer2 = NULL;
 1084         hammer_off_t layer1_offset;
 1085         hammer_off_t layer2_offset;
 1086         int32_t temp;
 1087         int error;
 1088         int zone __debugvar;
 1089 
 1090         if (bytes == 0)
 1091                 return (0);
 1092         hmp = trans->hmp;
 1093 
 1094         /*
 1095          * Alignment
 1096          */
 1097         bytes = (bytes + 15) & ~15;
 1098         KKASSERT(bytes <= HAMMER_LARGEBLOCK_SIZE);
 1099         KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) &
 1100                   ~HAMMER_LARGEBLOCK_MASK64) == 0);
 1101 
 1102         /*
 1103          * Basic zone validation & locking
 1104          */
 1105         zone = HAMMER_ZONE_DECODE(zone_offset);
 1106         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 1107         error = 0;
 1108 
 1109         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 1110 
 1111         /*
 1112          * Dive layer 1.
 1113          */
 1114         layer1_offset = freemap->phys_offset +
 1115                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 1116         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
 1117         if (error)
 1118                 goto failed;
 1119         KKASSERT(layer1->phys_offset &&
 1120                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 1121         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 1122                 hammer_lock_ex(&hmp->blkmap_lock);
 1123                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
 1124                         panic("CRC FAILED: LAYER1");
 1125                 hammer_unlock(&hmp->blkmap_lock);
 1126         }
 1127 
 1128         /*
 1129          * Dive layer 2, each entry represents a large-block.
 1130          */
 1131         layer2_offset = layer1->phys_offset +
 1132                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 1133         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
 1134         if (error)
 1135                 goto failed;
 1136         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 1137                 hammer_lock_ex(&hmp->blkmap_lock);
 1138                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
 1139                         panic("CRC FAILED: LAYER2");
 1140                 hammer_unlock(&hmp->blkmap_lock);
 1141         }
 1142 
 1143         hammer_lock_ex(&hmp->blkmap_lock);
 1144 
 1145         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
 1146 
 1147         /*
 1148          * Free space previously allocated via blockmap_alloc().
 1149          *
 1150          * NOTE: bytes_free can be and remain negative due to de-dup ops
 1151          *       but can never become larger than HAMMER_LARGEBLOCK_SIZE.
 1152          */
 1153         KKASSERT(layer2->zone == zone);
 1154         temp = layer2->bytes_free - HAMMER_LARGEBLOCK_SIZE * 2;
 1155         cpu_ccfence(); /* prevent gcc from optimizing temp out */
 1156         if (temp > layer2->bytes_free) {
 1157                 error = ERANGE;
 1158                 goto underflow;
 1159         }
 1160         layer2->bytes_free -= bytes;
 1161 
 1162         KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
 1163 
 1164         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 1165 underflow:
 1166         hammer_modify_buffer_done(buffer2);
 1167         hammer_unlock(&hmp->blkmap_lock);
 1168 
 1169 failed:
 1170         if (buffer1)
 1171                 hammer_rel_buffer(buffer1, 0);
 1172         if (buffer2)
 1173                 hammer_rel_buffer(buffer2, 0);
 1174         return (error);
 1175 }
 1176 
 1177 /*
 1178  * Backend function - finalize (offset, bytes) in a zone.
 1179  *
 1180  * Allocate space that was previously reserved by the frontend.
 1181  */
 1182 int
 1183 hammer_blockmap_finalize(hammer_transaction_t trans,
 1184                          hammer_reserve_t resv,
 1185                          hammer_off_t zone_offset, int bytes)
 1186 {
 1187         hammer_mount_t hmp;
 1188         hammer_volume_t root_volume;
 1189         hammer_blockmap_t freemap;
 1190         struct hammer_blockmap_layer1 *layer1;
 1191         struct hammer_blockmap_layer2 *layer2;
 1192         hammer_buffer_t buffer1 = NULL;
 1193         hammer_buffer_t buffer2 = NULL;
 1194         hammer_off_t layer1_offset;
 1195         hammer_off_t layer2_offset;
 1196         int error;
 1197         int zone;
 1198         int offset;
 1199 
 1200         if (bytes == 0)
 1201                 return(0);
 1202         hmp = trans->hmp;
 1203 
 1204         /*
 1205          * Alignment
 1206          */
 1207         bytes = (bytes + 15) & ~15;
 1208         KKASSERT(bytes <= HAMMER_XBUFSIZE);
 1209 
 1210         /*
 1211          * Basic zone validation & locking
 1212          */
 1213         zone = HAMMER_ZONE_DECODE(zone_offset);
 1214         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 1215         root_volume = trans->rootvol;
 1216         error = 0;
 1217 
 1218         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 1219 
 1220         /*
 1221          * Dive layer 1.
 1222          */
 1223         layer1_offset = freemap->phys_offset +
 1224                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 1225         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
 1226         if (error)
 1227                 goto failed;
 1228         KKASSERT(layer1->phys_offset &&
 1229                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 1230         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 1231                 hammer_lock_ex(&hmp->blkmap_lock);
 1232                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
 1233                         panic("CRC FAILED: LAYER1");
 1234                 hammer_unlock(&hmp->blkmap_lock);
 1235         }
 1236 
 1237         /*
 1238          * Dive layer 2, each entry represents a large-block.
 1239          */
 1240         layer2_offset = layer1->phys_offset +
 1241                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 1242         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
 1243         if (error)
 1244                 goto failed;
 1245         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 1246                 hammer_lock_ex(&hmp->blkmap_lock);
 1247                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
 1248                         panic("CRC FAILED: LAYER2");
 1249                 hammer_unlock(&hmp->blkmap_lock);
 1250         }
 1251 
 1252         hammer_lock_ex(&hmp->blkmap_lock);
 1253 
 1254         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
 1255 
 1256         /*
 1257          * Finalize some or all of the space covered by a current
 1258          * reservation.  An allocation in the same layer may have
 1259          * already assigned ownership.
 1260          */
 1261         if (layer2->zone == 0) {
 1262                 hammer_modify_buffer(trans, buffer1,
 1263                                      layer1, sizeof(*layer1));
 1264                 --layer1->blocks_free;
 1265                 layer1->layer1_crc = crc32(layer1,
 1266                                            HAMMER_LAYER1_CRCSIZE);
 1267                 hammer_modify_buffer_done(buffer1);
 1268                 layer2->zone = zone;
 1269                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
 1270                 KKASSERT(layer2->append_off == 0);
 1271                 hammer_modify_volume_field(trans,
 1272                                 trans->rootvol,
 1273                                 vol0_stat_freebigblocks);
 1274                 --root_volume->ondisk->vol0_stat_freebigblocks;
 1275                 hmp->copy_stat_freebigblocks =
 1276                    root_volume->ondisk->vol0_stat_freebigblocks;
 1277                 hammer_modify_volume_done(trans->rootvol);
 1278         }
 1279         if (layer2->zone != zone)
 1280                 kprintf("layer2 zone mismatch %d %d\n", layer2->zone, zone);
 1281         KKASSERT(layer2->zone == zone);
 1282         KKASSERT(bytes != 0);
 1283         layer2->bytes_free -= bytes;
 1284 
 1285         if (resv) {
 1286                 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
 1287         }
 1288 
 1289         /*
 1290          * Finalizations can occur out of order, or combined with allocations.
 1291          * append_off must be set to the highest allocated offset.
 1292          */
 1293         offset = ((int)zone_offset & HAMMER_LARGEBLOCK_MASK) + bytes;
 1294         if (layer2->append_off < offset)
 1295                 layer2->append_off = offset;
 1296 
 1297         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
 1298         hammer_modify_buffer_done(buffer2);
 1299         hammer_unlock(&hmp->blkmap_lock);
 1300 
 1301 failed:
 1302         if (buffer1)
 1303                 hammer_rel_buffer(buffer1, 0);
 1304         if (buffer2)
 1305                 hammer_rel_buffer(buffer2, 0);
 1306         return(error);
 1307 }
 1308 
 1309 /*
 1310  * Return the approximate number of free bytes in the big-block
 1311  * containing the specified blockmap offset.
 1312  *
 1313  * WARNING: A negative number can be returned if data de-dup exists,
 1314  *          and the result will also not represent he actual number
 1315  *          of free bytes in this case.
 1316  *
 1317  *          This code is used only by the reblocker.
 1318  */
 1319 int
 1320 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t zone_offset,
 1321                         int *curp, int *errorp)
 1322 {
 1323         hammer_volume_t root_volume;
 1324         hammer_blockmap_t blockmap;
 1325         hammer_blockmap_t freemap;
 1326         struct hammer_blockmap_layer1 *layer1;
 1327         struct hammer_blockmap_layer2 *layer2;
 1328         hammer_buffer_t buffer = NULL;
 1329         hammer_off_t layer1_offset;
 1330         hammer_off_t layer2_offset;
 1331         int32_t bytes;
 1332         int zone;
 1333 
 1334         zone = HAMMER_ZONE_DECODE(zone_offset);
 1335         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 1336         root_volume = hammer_get_root_volume(hmp, errorp);
 1337         if (*errorp) {
 1338                 *curp = 0;
 1339                 return(0);
 1340         }
 1341         blockmap = &hmp->blockmap[zone];
 1342         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 1343 
 1344         /*
 1345          * Dive layer 1.
 1346          */
 1347         layer1_offset = freemap->phys_offset +
 1348                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 1349         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
 1350         if (*errorp) {
 1351                 bytes = 0;
 1352                 goto failed;
 1353         }
 1354         KKASSERT(layer1->phys_offset);
 1355         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 1356                 hammer_lock_ex(&hmp->blkmap_lock);
 1357                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
 1358                         panic("CRC FAILED: LAYER1");
 1359                 hammer_unlock(&hmp->blkmap_lock);
 1360         }
 1361 
 1362         /*
 1363          * Dive layer 2, each entry represents a large-block.
 1364          *
 1365          * (reuse buffer, layer1 pointer becomes invalid)
 1366          */
 1367         layer2_offset = layer1->phys_offset +
 1368                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 1369         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
 1370         if (*errorp) {
 1371                 bytes = 0;
 1372                 goto failed;
 1373         }
 1374         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 1375                 hammer_lock_ex(&hmp->blkmap_lock);
 1376                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
 1377                         panic("CRC FAILED: LAYER2");
 1378                 hammer_unlock(&hmp->blkmap_lock);
 1379         }
 1380         KKASSERT(layer2->zone == zone);
 1381 
 1382         bytes = layer2->bytes_free;
 1383 
 1384         if ((blockmap->next_offset ^ zone_offset) & ~HAMMER_LARGEBLOCK_MASK64)
 1385                 *curp = 0;
 1386         else
 1387                 *curp = 1;
 1388 failed:
 1389         if (buffer)
 1390                 hammer_rel_buffer(buffer, 0);
 1391         hammer_rel_volume(root_volume, 0);
 1392         if (hammer_debug_general & 0x0800) {
 1393                 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
 1394                         (long long)zone_offset, bytes);
 1395         }
 1396         return(bytes);
 1397 }
 1398 
 1399 
 1400 /*
 1401  * Lookup a blockmap offset.
 1402  */
 1403 hammer_off_t
 1404 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t zone_offset,
 1405                        int *errorp)
 1406 {
 1407         hammer_volume_t root_volume;
 1408         hammer_blockmap_t freemap;
 1409         struct hammer_blockmap_layer1 *layer1;
 1410         struct hammer_blockmap_layer2 *layer2;
 1411         hammer_buffer_t buffer = NULL;
 1412         hammer_off_t layer1_offset;
 1413         hammer_off_t layer2_offset;
 1414         hammer_off_t result_offset;
 1415         hammer_off_t base_off;
 1416         hammer_reserve_t resv __debugvar;
 1417         int zone;
 1418 
 1419         /*
 1420          * Calculate the zone-2 offset.
 1421          */
 1422         zone = HAMMER_ZONE_DECODE(zone_offset);
 1423         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
 1424 
 1425         result_offset = (zone_offset & ~HAMMER_OFF_ZONE_MASK) |
 1426                         HAMMER_ZONE_RAW_BUFFER;
 1427 
 1428         /*
 1429          * We can actually stop here, normal blockmaps are now direct-mapped
 1430          * onto the freemap and so represent zone-2 addresses.
 1431          */
 1432         if (hammer_verify_zone == 0) {
 1433                 *errorp = 0;
 1434                 return(result_offset);
 1435         }
 1436 
 1437         /*
 1438          * Validate the allocation zone
 1439          */
 1440         root_volume = hammer_get_root_volume(hmp, errorp);
 1441         if (*errorp)
 1442                 return(0);
 1443         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
 1444         KKASSERT(freemap->phys_offset != 0);
 1445 
 1446         /*
 1447          * Dive layer 1.
 1448          */
 1449         layer1_offset = freemap->phys_offset +
 1450                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
 1451         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
 1452         if (*errorp)
 1453                 goto failed;
 1454         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
 1455         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
 1456                 hammer_lock_ex(&hmp->blkmap_lock);
 1457                 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
 1458                         panic("CRC FAILED: LAYER1");
 1459                 hammer_unlock(&hmp->blkmap_lock);
 1460         }
 1461 
 1462         /*
 1463          * Dive layer 2, each entry represents a large-block.
 1464          */
 1465         layer2_offset = layer1->phys_offset +
 1466                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
 1467         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
 1468 
 1469         if (*errorp)
 1470                 goto failed;
 1471         if (layer2->zone == 0) {
 1472                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
 1473                 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
 1474                                  base_off);
 1475                 KKASSERT(resv && resv->zone == zone);
 1476 
 1477         } else if (layer2->zone != zone) {
 1478                 panic("hammer_blockmap_lookup: bad zone %d/%d",
 1479                         layer2->zone, zone);
 1480         }
 1481         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
 1482                 hammer_lock_ex(&hmp->blkmap_lock);
 1483                 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
 1484                         panic("CRC FAILED: LAYER2");
 1485                 hammer_unlock(&hmp->blkmap_lock);
 1486         }
 1487 
 1488 failed:
 1489         if (buffer)
 1490                 hammer_rel_buffer(buffer, 0);
 1491         hammer_rel_volume(root_volume, 0);
 1492         if (hammer_debug_general & 0x0800) {
 1493                 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
 1494                         (long long)zone_offset, (long long)result_offset);
 1495         }
 1496         return(result_offset);
 1497 }
 1498 
 1499 
 1500 /*
 1501  * Check space availability
 1502  *
 1503  * MPSAFE - does not require fs_token
 1504  */
 1505 int
 1506 _hammer_checkspace(hammer_mount_t hmp, int slop, int64_t *resp)
 1507 {
 1508         const int in_size = sizeof(struct hammer_inode_data) +
 1509                             sizeof(union hammer_btree_elm);
 1510         const int rec_size = (sizeof(union hammer_btree_elm) * 2);
 1511         int64_t usedbytes;
 1512 
 1513         usedbytes = hmp->rsv_inodes * in_size +
 1514                     hmp->rsv_recs * rec_size +
 1515                     hmp->rsv_databytes +
 1516                     ((int64_t)hmp->rsv_fromdelay << HAMMER_LARGEBLOCK_BITS) +
 1517                     ((int64_t)hammer_limit_dirtybufspace) +
 1518                     (slop << HAMMER_LARGEBLOCK_BITS);
 1519 
 1520         hammer_count_extra_space_used = usedbytes;      /* debugging */
 1521         if (resp)
 1522                 *resp = usedbytes;
 1523 
 1524         if (hmp->copy_stat_freebigblocks >=
 1525             (usedbytes >> HAMMER_LARGEBLOCK_BITS)) {
 1526                 return(0);
 1527         }
 1528         return (ENOSPC);
 1529 }
 1530 

Cache object: 22848e3ac406007c8c441775739fbf38


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.