sys/vfs/hammer/hammer_undo.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
  35 /*
  36  * HAMMER undo - undo buffer/FIFO management.
  37  */
  38
  39 #include "hammer.h"
  40
  41 static int
  42 hammer_und_rb_compare(hammer_undo_t node1, hammer_undo_t node2)
  43 {
  44         if (node1->offset < node2->offset)
  45                 return(-1);
  46         if (node1->offset > node2->offset)
  47                 return(1);
  48         return(0);
  49 }
  50
  51 RB_GENERATE2(hammer_und_rb_tree, hammer_undo, rb_node,
  52              hammer_und_rb_compare, hammer_off_t, offset);
  53
  54 /*
  55  * Convert a zone-3 undo offset into a zone-2 buffer offset.
  56  */
  57 hammer_off_t
  58 hammer_undo_lookup(hammer_mount_t hmp, hammer_off_t zone3_off, int *errorp)
  59 {
  60         hammer_volume_t root_volume;
  61         hammer_blockmap_t undomap __debugvar;
  62         hammer_off_t result_offset;
  63         int i;
  64
  65         KKASSERT(hammer_is_zone_undo(zone3_off));
  66         root_volume = hammer_get_root_volume(hmp, errorp);
  67         if (*errorp)
  68                 return(0);
  69         undomap = &hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
  70         KKASSERT(HAMMER_ZONE_DECODE(undomap->alloc_offset) == HAMMER_ZONE_UNDO_INDEX);
  71         KKASSERT(zone3_off < undomap->alloc_offset);
  72
  73         /*
  74          * undo offsets[i] in zone-2 +
  75          * big-block offset of zone-3 address
  76          * which results zone-2 address
  77          */
  78         i = HAMMER_OFF_SHORT_ENCODE(zone3_off) / HAMMER_BIGBLOCK_SIZE;
  79         result_offset = root_volume->ondisk->vol0_undo_array[i] +
  80                         (zone3_off & HAMMER_BIGBLOCK_MASK64);
  81
  82         hammer_rel_volume(root_volume, 0);
  83         return(result_offset);
  84 }
  85
  86 /*
  87  * Generate UNDO record(s) for the block of data at the specified zone1
  88  * or zone2 offset.
  89  *
  90  * The recovery code will execute UNDOs in reverse order, allowing overlaps.
  91  * All the UNDOs are executed together so if we already laid one down we
  92  * do not have to lay another one down for the same range.
  93  *
  94  * For HAMMER version 4+ UNDO a 512 byte boundary is enforced and a PAD
  95  * will be laid down for any unused space.  UNDO FIFO media structures
  96  * will implement the hdr_seq field (it used to be reserved01), and
  97  * both flush and recovery mechanics will be very different.
  98  *
  99  * WARNING!  See also hammer_generate_redo() in hammer_redo.c
 100  */
 101 int
 102 hammer_generate_undo(hammer_transaction_t trans,
 103                      hammer_off_t zone_off, void *base, int len)
 104 {
 105         hammer_mount_t hmp;
 106         hammer_volume_t root_volume;
 107         hammer_blockmap_t undomap;
 108         hammer_buffer_t buffer = NULL;
 109         hammer_fifo_undo_t undo;
 110         hammer_fifo_tail_t tail;
 111         hammer_off_t next_offset;
 112         int error;
 113         int bytes;
 114         int n;
 115
 116         hmp = trans->hmp;
 117
 118         /*
 119          * A SYNC record may be required before we can lay down a general
 120          * UNDO.  This ensures that the nominal recovery span contains
 121          * at least one SYNC record telling the recovery code how far
 122          * out-of-span it must go to run the REDOs.
 123          */
 124         if ((hmp->flags & HAMMER_MOUNT_REDO_SYNC) == 0 &&
 125             hmp->version >= HAMMER_VOL_VERSION_FOUR) {
 126                 hammer_generate_redo_sync(trans);
 127         }
 128
 129         /*
 130          * Enter the offset into our undo history.  If there is an existing
 131          * undo we do not have to generate a new one.
 132          */
 133         if (hammer_enter_undo_history(hmp, zone_off, len) == EALREADY)
 134                 return(0);
 135
 136         root_volume = trans->rootvol;
 137         undomap = &hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 138
 139         /* no undo recursion */
 140         hammer_modify_volume_noundo(NULL, root_volume);
 141         hammer_lock_ex(&hmp->undo_lock);
 142
 143         /* undo had better not roll over (loose test) */
 144         if (hammer_undo_space(trans) < len + HAMMER_BUFSIZE*3)
 145                 hpanic("insufficient UNDO/REDO FIFO space for undo!");
 146
 147         /*
 148          * Loop until the undo for the entire range has been laid down.
 149          */
 150         while (len) {
 151                 /*
 152                  * Fetch the layout offset in the UNDO FIFO, wrap it as
 153                  * necessary.
 154                  */
 155                 if (undomap->next_offset == undomap->alloc_offset)
 156                         undomap->next_offset = HAMMER_ENCODE_UNDO(0);
 157                 next_offset = undomap->next_offset;
 158
 159                 /*
 160                  * This is a tail-chasing FIFO, when we hit the start of a new
 161                  * buffer we don't have to read it in.
 162                  */
 163                 if ((next_offset & HAMMER_BUFMASK) == 0) {
 164                         undo = hammer_bnew(hmp, next_offset, &error, &buffer);
 165                         hammer_format_undo(undo, hmp->undo_seqno ^ 0x40000000);
 166                 } else {
 167                         undo = hammer_bread(hmp, next_offset, &error, &buffer);
 168                 }
 169                 if (error)
 170                         break;
 171                 /* no undo recursion */
 172                 hammer_modify_buffer_noundo(NULL, buffer);
 173
 174                 /*
 175                  * Calculate how big a media structure fits up to the next
 176                  * alignment point and how large a data payload we can
 177                  * accomodate.
 178                  *
 179                  * If n calculates to 0 or negative there is no room for
 180                  * anything but a PAD.
 181                  */
 182                 bytes = HAMMER_UNDO_ALIGN -
 183                         ((int)next_offset & HAMMER_UNDO_MASK);
 184                 n = bytes -
 185                     (int)sizeof(struct hammer_fifo_undo) -
 186                     (int)sizeof(struct hammer_fifo_tail);
 187
 188                 /*
 189                  * If available space is insufficient for any payload
 190                  * we have to lay down a PAD.
 191                  *
 192                  * The minimum PAD is 8 bytes and the head and tail will
 193                  * overlap each other in that case.  PADs do not have
 194                  * sequence numbers or CRCs.
 195                  *
 196                  * A PAD may not start on a boundary.  That is, every
 197                  * 512-byte block in the UNDO/REDO FIFO must begin with
 198                  * a record containing a sequence number.
 199                  */
 200                 if (n <= 0) {
 201                         KKASSERT(bytes >= sizeof(struct hammer_fifo_tail));
 202                         KKASSERT(((int)next_offset & HAMMER_UNDO_MASK) != 0);
 203                         tail = (void *)((char *)undo + bytes - sizeof(*tail));
 204                         if ((void *)undo != (void *)tail) {
 205                                 tail->tail_signature = HAMMER_TAIL_SIGNATURE;
 206                                 tail->tail_type = HAMMER_HEAD_TYPE_PAD;
 207                                 tail->tail_size = bytes;
 208                         }
 209                         undo->head.hdr_signature = HAMMER_HEAD_SIGNATURE;
 210                         undo->head.hdr_type = HAMMER_HEAD_TYPE_PAD;
 211                         undo->head.hdr_size = bytes;
 212                         /* NO CRC OR SEQ NO */
 213                         undomap->next_offset += bytes;
 214                         hammer_modify_buffer_done(buffer);
 215                         hammer_stats_undo += bytes;
 216                         continue;
 217                 }
 218
 219                 /*
 220                  * Calculate the actual payload and recalculate the size
 221                  * of the media structure as necessary.
 222                  */
 223                 if (n > len) {
 224                         n = len;
 225                         bytes = ((n + HAMMER_HEAD_ALIGN_MASK) &
 226                                  ~HAMMER_HEAD_ALIGN_MASK) +
 227                                 (int)sizeof(struct hammer_fifo_undo) +
 228                                 (int)sizeof(struct hammer_fifo_tail);
 229                 }
 230                 if (hammer_debug_general & 0x0080) {
 231                         hdkprintf("undo %016jx %d %d\n",
 232                                 (intmax_t)next_offset, bytes, n);
 233                 }
 234
 235                 undo->head.hdr_signature = HAMMER_HEAD_SIGNATURE;
 236                 undo->head.hdr_type = HAMMER_HEAD_TYPE_UNDO;
 237                 undo->head.hdr_size = bytes;
 238                 undo->head.hdr_seq = hmp->undo_seqno++;
 239                 undo->head.hdr_crc = 0;
 240                 undo->undo_offset = zone_off;
 241                 undo->undo_data_bytes = n;
 242                 bcopy(base, undo + 1, n);
 243
 244                 tail = (void *)((char *)undo + bytes - sizeof(*tail));
 245                 tail->tail_signature = HAMMER_TAIL_SIGNATURE;
 246                 tail->tail_type = HAMMER_HEAD_TYPE_UNDO;
 247                 tail->tail_size = bytes;
 248
 249                 KKASSERT(bytes >= sizeof(undo->head));
 250                 hammer_crc_set_fifo_head(&undo->head, bytes);
 251                 undomap->next_offset += bytes;
 252                 hammer_stats_undo += bytes;
 253
 254                 /*
 255                  * Before we finish off the buffer we have to deal with any
 256                  * junk between the end of the media structure we just laid
 257                  * down and the UNDO alignment boundary.  We do this by laying
 258                  * down a dummy PAD.  Even though we will probably overwrite
 259                  * it almost immediately we have to do this so recovery runs
 260                  * can iterate the UNDO space without having to depend on
 261                  * the indices in the volume header.
 262                  *
 263                  * This dummy PAD will be overwritten on the next undo so
 264                  * we do not adjust undomap->next_offset.
 265                  */
 266                 bytes = HAMMER_UNDO_ALIGN -
 267                         ((int)undomap->next_offset & HAMMER_UNDO_MASK);
 268                 if (bytes != HAMMER_UNDO_ALIGN) {
 269                         KKASSERT(bytes >= sizeof(struct hammer_fifo_tail));
 270                         undo = (void *)(tail + 1);
 271                         tail = (void *)((char *)undo + bytes - sizeof(*tail));
 272                         if ((void *)undo != (void *)tail) {
 273                                 tail->tail_signature = HAMMER_TAIL_SIGNATURE;
 274                                 tail->tail_type = HAMMER_HEAD_TYPE_PAD;
 275                                 tail->tail_size = bytes;
 276                         }
 277                         undo->head.hdr_signature = HAMMER_HEAD_SIGNATURE;
 278                         undo->head.hdr_type = HAMMER_HEAD_TYPE_PAD;
 279                         undo->head.hdr_size = bytes;
 280                         /* NO CRC OR SEQ NO */
 281                 }
 282                 hammer_modify_buffer_done(buffer);
 283
 284                 /*
 285                  * Adjust for loop
 286                  */
 287                 len -= n;
 288                 base = (char *)base + n;
 289                 zone_off += n;
 290         }
 291         hammer_modify_volume_done(root_volume);
 292         hammer_unlock(&hmp->undo_lock);
 293
 294         if (buffer)
 295                 hammer_rel_buffer(buffer, 0);
 296         return(error);
 297 }
 298
 299 /*
 300  * Preformat a new UNDO block.  We could read the old one in but we get
 301  * better performance if we just pre-format a new one.
 302  *
 303  * The recovery code always works forwards so the caller just makes sure the
 304  * seqno is not contiguous with prior UNDOs or ancient UNDOs now being
 305  * overwritten.
 306  *
 307  * The preformatted UNDO headers use the smallest possible sector size
 308  * (512) to ensure that any missed media writes are caught.
 309  *
 310  * NOTE: Also used by the REDO code.
 311  */
 312 void
 313 hammer_format_undo(void *base, uint32_t seqno)
 314 {
 315         hammer_fifo_head_t head;
 316         hammer_fifo_tail_t tail;
 317         int i;
 318         int bytes = HAMMER_UNDO_ALIGN;
 319
 320         bzero(base, HAMMER_BUFSIZE);
 321
 322         for (i = 0; i < HAMMER_BUFSIZE; i += bytes) {
 323                 head = (void *)((char *)base + i);
 324                 tail = (void *)((char *)head + bytes - sizeof(*tail));
 325
 326                 head->hdr_signature = HAMMER_HEAD_SIGNATURE;
 327                 head->hdr_type = HAMMER_HEAD_TYPE_DUMMY;
 328                 head->hdr_size = bytes;
 329                 head->hdr_seq = seqno++;
 330                 head->hdr_crc = 0;
 331
 332                 tail->tail_signature = HAMMER_TAIL_SIGNATURE;
 333                 tail->tail_type = HAMMER_HEAD_TYPE_DUMMY;
 334                 tail->tail_size = bytes;
 335
 336                 hammer_crc_set_fifo_head(head, bytes);
 337         }
 338 }
 339
 340 /*
 341  * HAMMER version 4+ conversion support.
 342  *
 343  * Convert a HAMMER version < 4 UNDO FIFO area to a 4+ UNDO FIFO area.
 344  * The 4+ UNDO FIFO area is backwards compatible.  The conversion is
 345  * needed to initialize the sequence space and place headers on the
 346  * new 512-byte undo boundary.
 347  */
 348 int
 349 hammer_upgrade_undo_4(hammer_transaction_t trans)
 350 {
 351         hammer_mount_t hmp;
 352         hammer_volume_t root_volume;
 353         hammer_blockmap_t undomap;
 354         hammer_buffer_t buffer = NULL;
 355         hammer_fifo_head_t head;
 356         hammer_fifo_tail_t tail;
 357         hammer_off_t next_offset;
 358         uint32_t seqno;
 359         int error;
 360         int bytes;
 361
 362         hmp = trans->hmp;
 363
 364         root_volume = trans->rootvol;
 365
 366         /* no undo recursion */
 367         hammer_lock_ex(&hmp->undo_lock);
 368         hammer_modify_volume_noundo(NULL, root_volume);
 369
 370         /*
 371          * Adjust the in-core undomap and the on-disk undomap.
 372          */
 373         next_offset = HAMMER_ENCODE_UNDO(0);
 374         undomap = &hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 375         undomap->next_offset = next_offset;
 376         undomap->first_offset = next_offset;
 377
 378         undomap = &root_volume->ondisk->vol0_blockmap[HAMMER_ZONE_UNDO_INDEX];
 379         undomap->next_offset = next_offset;
 380         undomap->first_offset = next_offset;
 381
 382         /*
 383          * Loop over the entire UNDO space creating DUMMY entries.  Sequence
 384          * numbers are assigned.
 385          */
 386         seqno = 0;
 387         bytes = HAMMER_UNDO_ALIGN;
 388
 389         while (next_offset != undomap->alloc_offset) {
 390                 head = hammer_bnew(hmp, next_offset, &error, &buffer);
 391                 if (error)
 392                         break;
 393                 hammer_modify_buffer_noundo(NULL, buffer);
 394                 tail = (void *)((char *)head + bytes - sizeof(*tail));
 395
 396                 head->hdr_signature = HAMMER_HEAD_SIGNATURE;
 397                 head->hdr_type = HAMMER_HEAD_TYPE_DUMMY;
 398                 head->hdr_size = bytes;
 399                 head->hdr_seq = seqno;
 400                 head->hdr_crc = 0;
 401
 402                 tail = (void *)((char *)head + bytes - sizeof(*tail));
 403                 tail->tail_signature = HAMMER_TAIL_SIGNATURE;
 404                 tail->tail_type = HAMMER_HEAD_TYPE_DUMMY;
 405                 tail->tail_size = bytes;
 406
 407                 hammer_crc_set_fifo_head(head, bytes);
 408                 hammer_modify_buffer_done(buffer);
 409
 410                 hammer_stats_undo += bytes;
 411                 next_offset += HAMMER_UNDO_ALIGN;
 412                 ++seqno;
 413         }
 414
 415         /*
 416          * The sequence number will be the next sequence number to lay down.
 417          */
 418         hmp->undo_seqno = seqno;
 419         hmkprintf(hmp, "version upgrade seqno start %08x\n", seqno);
 420
 421         hammer_modify_volume_done(root_volume);
 422         hammer_unlock(&hmp->undo_lock);
 423
 424         if (buffer)
 425                 hammer_rel_buffer(buffer, 0);
 426         return (error);
 427 }
 428
 429 /*
 430  * UNDO HISTORY API
 431  *
 432  * It is not necessary to layout an undo record for the same address space
 433  * multiple times.  Maintain a cache of recent undo's.
 434  */
 435
 436 /*
 437  * Enter an undo into the history.  Return EALREADY if the request completely
 438  * covers a previous request.
 439  */
 440 int
 441 hammer_enter_undo_history(hammer_mount_t hmp, hammer_off_t offset, int bytes)
 442 {
 443         hammer_undo_t node;
 444         hammer_undo_t onode __debugvar;
 445
 446         node = RB_LOOKUP(hammer_und_rb_tree, &hmp->rb_undo_root, offset);
 447         if (node) {
 448                 TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry);
 449                 TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry);
 450                 if (bytes <= node->bytes)
 451                         return(EALREADY);
 452                 node->bytes = bytes;
 453                 return(0);
 454         }
 455         if (hmp->undo_alloc != HAMMER_MAX_UNDOS) {
 456                 node = &hmp->undos[hmp->undo_alloc++];
 457         } else {
 458                 node = TAILQ_FIRST(&hmp->undo_lru_list);
 459                 TAILQ_REMOVE(&hmp->undo_lru_list, node, lru_entry);
 460                 RB_REMOVE(hammer_und_rb_tree, &hmp->rb_undo_root, node);
 461         }
 462         node->offset = offset;
 463         node->bytes = bytes;
 464         TAILQ_INSERT_TAIL(&hmp->undo_lru_list, node, lru_entry);
 465         onode = RB_INSERT(hammer_und_rb_tree, &hmp->rb_undo_root, node);
 466         KKASSERT(onode == NULL);
 467         return(0);
 468 }
 469
 470 void
 471 hammer_clear_undo_history(hammer_mount_t hmp)
 472 {
 473         RB_INIT(&hmp->rb_undo_root);
 474         TAILQ_INIT(&hmp->undo_lru_list);
 475         hmp->undo_alloc = 0;
 476 }
 477
 478 /*
 479  * Return how much of the undo FIFO has been used
 480  *
 481  * The calculation includes undo FIFO space still reserved from a previous
 482  * flush (because it will still be run on recovery if a crash occurs and
 483  * we can't overwrite it yet).
 484  */
 485 int64_t
 486 hammer_undo_used(hammer_transaction_t trans)
 487 {
 488         hammer_blockmap_t cundomap;
 489         hammer_blockmap_t dundomap;
 490         int64_t max_bytes __debugvar;
 491         int64_t bytes;
 492
 493         cundomap = &trans->hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 494         dundomap = &trans->rootvol->ondisk->
 495                                 vol0_blockmap[HAMMER_ZONE_UNDO_INDEX];
 496
 497         if (dundomap->first_offset <= cundomap->next_offset) {
 498                 bytes = cundomap->next_offset - dundomap->first_offset;
 499         } else {
 500                 bytes = cundomap->alloc_offset - dundomap->first_offset +
 501                         HAMMER_OFF_LONG_ENCODE(cundomap->next_offset);
 502         }
 503         max_bytes = HAMMER_OFF_SHORT_ENCODE(cundomap->alloc_offset);
 504         KKASSERT(bytes <= max_bytes);
 505         return(bytes);
 506 }
 507
 508 /*
 509  * Return how much of the undo FIFO is available for new records.
 510  */
 511 int64_t
 512 hammer_undo_space(hammer_transaction_t trans)
 513 {
 514         hammer_blockmap_t rootmap;
 515         int64_t max_bytes;
 516
 517         rootmap = &trans->hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 518         max_bytes = HAMMER_OFF_SHORT_ENCODE(rootmap->alloc_offset);
 519         return(max_bytes - hammer_undo_used(trans));
 520 }
 521
 522 int64_t
 523 hammer_undo_max(hammer_mount_t hmp)
 524 {
 525         hammer_blockmap_t rootmap;
 526         int64_t max_bytes;
 527
 528         rootmap = &hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 529         max_bytes = HAMMER_OFF_SHORT_ENCODE(rootmap->alloc_offset);
 530
 531         return(max_bytes);
 532 }
 533
 534 /*
 535  * Returns 1 if the undo buffer should be reclaimed on release.  The
 536  * only undo buffer we do NOT want to reclaim is the one at the current
 537  * append offset.
 538  */
 539 int
 540 hammer_undo_reclaim(hammer_io_t io)
 541 {
 542         hammer_blockmap_t undomap;
 543         hammer_off_t next_offset;
 544
 545         undomap = &io->hmp->blockmap[HAMMER_ZONE_UNDO_INDEX];
 546         next_offset = undomap->next_offset & ~HAMMER_BUFMASK64;
 547         if (HAMMER_ITOB(io)->zoneX_offset == next_offset)
 548                 return(0);
 549         return(1);
 550 }