sys/vfs/hammer/hammer_prune.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_prune.c,v 1.1 2008/05/12 21:17:18 dillon Exp $
  35  */
  36
  37 #include "hammer.h"
  38
  39 /*
  40  * Iterate through the specified range of object ids and remove any
  41  * deleted records that fall entirely within a prune modulo.
  42  *
  43  * A reverse iteration is used to prevent overlapping records from being
  44  * created during the iteration due to alignments.  This also allows us
  45  * to adjust alignments without blowing up the B-Tree.
  46  */
  47 static int check_prune(struct hammer_ioc_prune *prune, hammer_btree_elm_t elm,
  48                         int *realign_cre, int *realign_del);
  49 static int realign_prune(struct hammer_ioc_prune *prune, hammer_cursor_t cursor,
  50                         int realign_cre, int realign_del);
  51
  52 int
  53 hammer_ioc_prune(hammer_transaction_t trans, hammer_inode_t ip,
  54                  struct hammer_ioc_prune *prune)
  55 {
  56         struct hammer_cursor cursor;
  57         hammer_btree_elm_t elm;
  58         int error;
  59         int isdir;
  60         int realign_cre;
  61         int realign_del;
  62
  63         if (prune->nelms < 0 || prune->nelms > HAMMER_MAX_PRUNE_ELMS)
  64                 return(EINVAL);
  65         if (prune->beg_obj_id >= prune->end_obj_id)
  66                 return(EINVAL);
  67         if ((prune->head.flags & HAMMER_IOC_PRUNE_ALL) && prune->nelms)
  68                 return(EINVAL);
  69
  70         prune->cur_obj_id = prune->end_obj_id;
  71         prune->cur_key = HAMMER_MAX_KEY;
  72
  73 retry:
  74         error = hammer_init_cursor(trans, &cursor, NULL, NULL);
  75         if (error) {
  76                 hammer_done_cursor(&cursor);
  77                 return(error);
  78         }
  79         cursor.key_beg.obj_id = prune->beg_obj_id;
  80         cursor.key_beg.key = HAMMER_MIN_KEY;
  81         cursor.key_beg.create_tid = 1;
  82         cursor.key_beg.delete_tid = 0;
  83         cursor.key_beg.rec_type = HAMMER_MIN_RECTYPE;
  84         cursor.key_beg.obj_type = 0;
  85
  86         cursor.key_end.obj_id = prune->cur_obj_id;
  87         cursor.key_end.key = prune->cur_key;
  88         cursor.key_end.create_tid = HAMMER_MAX_TID - 1;
  89         cursor.key_end.delete_tid = 0;
  90         cursor.key_end.rec_type = HAMMER_MAX_RECTYPE;
  91         cursor.key_end.obj_type = 0;
  92
  93         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
  94         cursor.flags |= HAMMER_CURSOR_BACKEND;
  95
  96         /*
  97          * This flag allows the B-Tree code to clean up loose ends while
  98          * it is scanning.
  99          */
 100         cursor.flags |= HAMMER_CURSOR_PRUNING;
 101
 102         error = hammer_btree_last(&cursor);
 103         while (error == 0) {
 104                 elm = &cursor.node->ondisk->elms[cursor.index];
 105                 prune->cur_obj_id = elm->base.obj_id;
 106                 prune->cur_key = elm->base.key;
 107
 108                 if (prune->stat_oldest_tid > elm->leaf.base.create_tid)
 109                         prune->stat_oldest_tid = elm->leaf.base.create_tid;
 110
 111                 if (check_prune(prune, elm, &realign_cre, &realign_del) == 0) {
 112                         if (hammer_debug_general & 0x0200) {
 113                                 kprintf("check %016llx %016llx: DELETE\n",
 114                                         elm->base.obj_id, elm->base.key);
 115                         }
 116
 117                         /*
 118                          * NOTE: This can return EDEADLK
 119                          *
 120                          * Acquiring the sync lock guarantees that the
 121                          * operation will not cross a synchronization
 122                          * boundary (see the flusher).
 123                          */
 124                         isdir = (elm->base.rec_type == HAMMER_RECTYPE_DIRENTRY);
 125
 126                         hammer_lock_ex(&trans->hmp->sync_lock);
 127                         error = hammer_delete_at_cursor(&cursor,
 128                                                         &prune->stat_bytes);
 129                         hammer_unlock(&trans->hmp->sync_lock);
 130                         if (error)
 131                                 break;
 132
 133                         if (isdir)
 134                                 ++prune->stat_dirrecords;
 135                         else
 136                                 ++prune->stat_rawrecords;
 137
 138                         /*
 139                          * The current record might now be the one after
 140                          * the one we deleted, set ATEDISK to force us
 141                          * to skip it (since we are iterating backwards).
 142                          */
 143                         cursor.flags |= HAMMER_CURSOR_ATEDISK;
 144                 } else if (realign_cre >= 0 || realign_del >= 0) {
 145                         hammer_lock_ex(&trans->hmp->sync_lock);
 146                         error = realign_prune(prune, &cursor,
 147                                               realign_cre, realign_del);
 148                         hammer_unlock(&trans->hmp->sync_lock);
 149                         if (error == 0) {
 150                                 cursor.flags |= HAMMER_CURSOR_ATEDISK;
 151                                 if (hammer_debug_general & 0x0200) {
 152                                         kprintf("check %016llx %016llx: "
 153                                                 "REALIGN\n",
 154                                                 elm->base.obj_id,
 155                                                 elm->base.key);
 156                                 }
 157                         }
 158                 } else {
 159                         cursor.flags |= HAMMER_CURSOR_ATEDISK;
 160                         if (hammer_debug_general & 0x0100) {
 161                                 kprintf("check %016llx %016llx: SKIP\n",
 162                                         elm->base.obj_id, elm->base.key);
 163                         }
 164                 }
 165                 ++prune->stat_scanrecords;
 166
 167                 /*
 168                  * Bad hack for now, don't blow out the kernel's buffer
 169                  * cache.  NOTE: We still hold locks on the cursor, we
 170                  * cannot call the flusher synchronously.
 171                  */
 172                 if (trans->hmp->locked_dirty_count > hammer_limit_dirtybufs) {
 173                         hammer_flusher_async(trans->hmp);
 174                         tsleep(trans, 0, "hmrslo", hz / 10);
 175                 }
 176                 error = hammer_signal_check(trans->hmp);
 177                 if (error == 0)
 178                         error = hammer_btree_iterate_reverse(&cursor);
 179         }
 180         if (error == ENOENT)
 181                 error = 0;
 182         hammer_done_cursor(&cursor);
 183         if (error == EDEADLK)
 184                 goto retry;
 185         if (error == EINTR) {
 186                 prune->head.flags |= HAMMER_IOC_HEAD_INTR;
 187                 error = 0;
 188         }
 189         return(error);
 190 }
 191
 192 /*
 193  * Check pruning list.  The list must be sorted in descending order.
 194  */
 195 static int
 196 check_prune(struct hammer_ioc_prune *prune, hammer_btree_elm_t elm,
 197             int *realign_cre, int *realign_del)
 198 {
 199         struct hammer_ioc_prune_elm *scan;
 200         int i;
 201
 202         *realign_cre = -1;
 203         *realign_del = -1;
 204
 205         /*
 206          * If pruning everything remove all records with a non-zero
 207          * delete_tid.
 208          */
 209         if (prune->head.flags & HAMMER_IOC_PRUNE_ALL) {
 210                 if (elm->base.delete_tid != 0)
 211                         return(0);
 212                 return(-1);
 213         }
 214
 215         for (i = 0; i < prune->nelms; ++i) {
 216                 scan = &prune->elms[i];
 217
 218                 /*
 219                  * Locate the scan index covering the create and delete TIDs.
 220                  */
 221                 if (*realign_cre < 0 &&
 222                     elm->base.create_tid >= scan->beg_tid &&
 223                     elm->base.create_tid < scan->end_tid) {
 224                         *realign_cre = i;
 225                 }
 226                 if (*realign_del < 0 && elm->base.delete_tid &&
 227                     elm->base.delete_tid > scan->beg_tid &&
 228                     elm->base.delete_tid <= scan->end_tid) {
 229                         *realign_del = i;
 230                 }
 231
 232                 /*
 233                  * Now check for loop termination.
 234                  */
 235                 if (elm->base.create_tid >= scan->end_tid ||
 236                     elm->base.delete_tid > scan->end_tid) {
 237                         break;
 238                 }
 239
 240                 /*
 241                  * Now determine if we can delete the record.
 242                  */
 243                 if (elm->base.delete_tid &&
 244                     elm->base.create_tid >= scan->beg_tid &&
 245                     elm->base.delete_tid <= scan->end_tid &&
 246                     elm->base.create_tid / scan->mod_tid ==
 247                     elm->base.delete_tid / scan->mod_tid) {
 248                         return(0);
 249                 }
 250         }
 251         return(-1);
 252 }
 253
 254 /*
 255  * Align the record to cover any gaps created through the deletion of
 256  * records within the pruning space.  If we were to just delete the records
 257  * there would be gaps which in turn would cause a snapshot that is NOT on
 258  * a pruning boundary to appear corrupt to the user.  Forcing alignment
 259  * of the create_tid and delete_tid for retained records 'reconnects'
 260  * the previously contiguous space, making it contiguous again after the
 261  * deletions.
 262  *
 263  * The use of a reverse iteration allows us to safely align the records and
 264  * related elements without creating temporary overlaps.  XXX we should
 265  * add ordering dependancies for record buffers to guarantee consistency
 266  * during recovery.
 267  */
 268 static int
 269 realign_prune(struct hammer_ioc_prune *prune,
 270               hammer_cursor_t cursor, int realign_cre, int realign_del)
 271 {
 272         hammer_btree_elm_t elm;
 273         hammer_tid_t delta;
 274         hammer_tid_t mod;
 275         hammer_tid_t tid;
 276         int error;
 277
 278         hammer_cursor_downgrade(cursor);
 279
 280         elm = &cursor->node->ondisk->elms[cursor->index];
 281         ++prune->stat_realignments;
 282
 283         /*
 284          * Align the create_tid.  By doing a reverse iteration we guarantee
 285          * that all records after our current record have already been
 286          * aligned, allowing us to safely correct the right-hand-boundary
 287          * (because no record to our right if otherwise exactly matching
 288          * will have a create_tid to the left of our aligned create_tid).
 289          *
 290          * Ordering is important here XXX but disk write ordering for
 291          * inter-cluster corrections is not currently guaranteed.
 292          */
 293         error = 0;
 294         if (realign_cre >= 0) {
 295                 mod = prune->elms[realign_cre].mod_tid;
 296                 delta = elm->leaf.base.create_tid % mod;
 297                 if (delta) {
 298                         tid = elm->leaf.base.create_tid - delta + mod;
 299
 300                         /* can EDEADLK */
 301                         error = hammer_btree_correct_rhb(cursor, tid + 1);
 302                         if (error == 0) {
 303                                 error = hammer_btree_extract(cursor,
 304                                                      HAMMER_CURSOR_GET_LEAF);
 305                         }
 306                         if (error == 0) {
 307                                 /* can EDEADLK */
 308                                 error = hammer_cursor_upgrade(cursor);
 309                         }
 310                         if (error == 0) {
 311                                 hammer_modify_node(cursor->trans, cursor->node,
 312                                             &elm->leaf.base.create_tid,
 313                                             sizeof(elm->leaf.base.create_tid));
 314                                 elm->leaf.base.create_tid = tid;
 315                                 hammer_modify_node_done(cursor->node);
 316                         }
 317                 }
 318         }
 319
 320         /*
 321          * Align the delete_tid.  This only occurs if the record is historical
 322          * was deleted at some point.  Realigning the delete_tid does not
 323          * move the record within the B-Tree but may cause it to temporarily
 324          * overlap a record that has not yet been pruned.
 325          */
 326         if (error == 0 && realign_del >= 0) {
 327                 mod = prune->elms[realign_del].mod_tid;
 328                 delta = elm->leaf.base.delete_tid % mod;
 329                 if (delta) {
 330                         error = hammer_btree_extract(cursor,
 331                                                      HAMMER_CURSOR_GET_LEAF);
 332                         if (error == 0) {
 333                                 hammer_modify_node(cursor->trans, cursor->node,
 334                                             &elm->leaf.base.delete_tid,
 335                                             sizeof(elm->leaf.base.delete_tid));
 336                                 elm->leaf.base.delete_tid =
 337                                             elm->leaf.base.delete_tid -
 338                                             delta + mod;
 339                                 hammer_modify_node_done(cursor->node);
 340                         }
 341                 }
 342         }
 343         return (error);
 344 }
 345