repair/bmap.c

   1 /*
   2  * Copyright (c) 2000-2001,2005,2008 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18
  19 #include "libxfs.h"
  20 #include "err_protos.h"
  21 #include "bmap.h"
  22
  23 /*
  24  * Track the logical to physical block mapping for inodes.
  25  *
  26  * Repair only processes one inode at a given time per thread, and the
  27  * block map does not have to outlive the processing of a single inode.
  28  *
  29  * The combination of those factors means we can use pthreads thread-local
  30  * storage to store the block map, and we can re-use the allocation over
  31  * and over again.
  32  */
  33
  34 pthread_key_t   dblkmap_key;
  35 pthread_key_t   ablkmap_key;
  36
  37 blkmap_t *
  38 blkmap_alloc(
  39         xfs_extnum_t    nex,
  40         int             whichfork)
  41 {
  42         pthread_key_t   key;
  43         blkmap_t        *blkmap;
  44
  45         ASSERT(whichfork == XFS_DATA_FORK || whichfork == XFS_ATTR_FORK);
  46
  47         if (nex < 1)
  48                 nex = 1;
  49
  50 #if (BITS_PER_LONG == 32)       /* on 64-bit platforms this is never true */
  51         if (nex > BLKMAP_NEXTS_MAX) {
  52                 do_warn(
  53         _("Number of extents requested in blkmap_alloc (%d) overflows 32 bits.\n"
  54           "If this is not a corruption, then you will need a 64 bit system\n"
  55           "to repair this filesystem.\n"),
  56                         nex);
  57                 return NULL;
  58         }
  59 #endif
  60
  61         key = whichfork ? ablkmap_key : dblkmap_key;
  62         blkmap = pthread_getspecific(key);
  63         if (!blkmap || blkmap->naexts < nex) {
  64                 blkmap = realloc(blkmap, BLKMAP_SIZE(nex));
  65                 if (!blkmap) {
  66                         do_warn(_("malloc failed in blkmap_alloc (%zu bytes)\n"),
  67                                 BLKMAP_SIZE(nex));
  68                         return NULL;
  69                 }
  70                 pthread_setspecific(key, blkmap);
  71                 blkmap->naexts = nex;
  72         }
  73
  74         blkmap->nexts = 0;
  75         return blkmap;
  76 }
  77
  78 /*
  79  * Free a block map.
  80  *
  81  * If the map is a large, uncommon size (say for hundreds of thousands of
  82  * extents) then free it to release the memory. This prevents us from pinning
  83  * large tracts of memory due to corrupted fork values or one-off fragmented
  84  * files. Otherwise we have nothing to do but keep the memory around for the
  85  * next inode.
  86  * When the thread is done, it should do an unconditional, final free.
  87  */
  88 void
  89 blkmap_free(
  90         blkmap_t        *blkmap)
  91 {
  92         if (!blkmap)
  93                 return;
  94
  95         /* consider more than 100k extents rare */
  96         if (blkmap->naexts < 100 * 1024)
  97                 return;
  98
  99         if (blkmap == pthread_getspecific(dblkmap_key))
 100                 pthread_setspecific(dblkmap_key, NULL);
 101         else
 102                 pthread_setspecific(ablkmap_key, NULL);
 103
 104         free(blkmap);
 105 }
 106
 107 void
 108 blkmap_free_final(void)
 109 {
 110         blkmap_t        *blkmap;
 111
 112         blkmap = pthread_getspecific(dblkmap_key);
 113         pthread_setspecific(dblkmap_key, NULL);
 114         free(blkmap);
 115
 116         blkmap = pthread_getspecific(ablkmap_key);
 117         pthread_setspecific(ablkmap_key, NULL);
 118         free(blkmap);
 119 }
 120
 121 /*
 122  * Get one entry from a block map.
 123  */
 124 xfs_fsblock_t
 125 blkmap_get(
 126         blkmap_t        *blkmap,
 127         xfs_fileoff_t   o)
 128 {
 129         bmap_ext_t      *ext = blkmap->exts;
 130         int             i;
 131
 132         for (i = 0; i < blkmap->nexts; i++, ext++) {
 133                 if (o >= ext->startoff && o < ext->startoff + ext->blockcount)
 134                         return ext->startblock + (o - ext->startoff);
 135         }
 136         return NULLFSBLOCK;
 137 }
 138
 139 /*
 140  * Get a chunk of entries from a block map - only used for reading dirv2 blocks
 141  */
 142 int
 143 blkmap_getn(
 144         blkmap_t        *blkmap,
 145         xfs_fileoff_t   o,
 146         xfs_filblks_t   nb,
 147         bmap_ext_t      **bmpp,
 148         bmap_ext_t      *bmpp_single)
 149 {
 150         bmap_ext_t      *bmp = NULL;
 151         bmap_ext_t      *ext;
 152         int             i;
 153         int             nex;
 154
 155         if (nb == 1) {
 156                 /*
 157                  * in the common case, when mp->m_dirblkfsbs == 1,
 158                  * avoid additional malloc/free overhead
 159                  */
 160                 bmpp_single->startblock = blkmap_get(blkmap, o);
 161                 goto single_ext;
 162         }
 163         ext = blkmap->exts;
 164         nex = 0;
 165         for (i = 0; i < blkmap->nexts; i++, ext++) {
 166
 167                 if (ext->startoff >= o + nb)
 168                         break;
 169                 if (ext->startoff + ext->blockcount <= o)
 170                         continue;
 171
 172                 /*
 173                  * if all the requested blocks are in one extent (also common),
 174                  * use the bmpp_single option as well
 175                  */
 176                 if (!bmp && o >= ext->startoff &&
 177                     o + nb <= ext->startoff + ext->blockcount) {
 178                         bmpp_single->startblock =
 179                                  ext->startblock + (o - ext->startoff);
 180                         goto single_ext;
 181                 }
 182
 183                 /*
 184                  * rare case - multiple extents for a single dir block
 185                  */
 186                 if (!bmp)
 187                         bmp = malloc(nb * sizeof(bmap_ext_t));
 188                 if (!bmp)
 189                         do_error(_("blkmap_getn malloc failed (%" PRIu64 " bytes)\n"),
 190                                                 nb * sizeof(bmap_ext_t));
 191
 192                 bmp[nex].startblock = ext->startblock + (o - ext->startoff);
 193                 bmp[nex].blockcount = MIN(nb, ext->blockcount -
 194                                 (bmp[nex].startblock - ext->startblock));
 195                 o += bmp[nex].blockcount;
 196                 nb -= bmp[nex].blockcount;
 197                 nex++;
 198         }
 199         *bmpp = bmp;
 200         return nex;
 201
 202 single_ext:
 203         bmpp_single->blockcount = nb;
 204         bmpp_single->startoff = 0;      /* not even used by caller! */
 205         *bmpp = bmpp_single;
 206         return (bmpp_single->startblock != NULLFSBLOCK) ? 1 : 0;
 207 }
 208
 209 /*
 210  * Return the last offset in a block map.
 211  */
 212 xfs_fileoff_t
 213 blkmap_last_off(
 214         blkmap_t        *blkmap)
 215 {
 216         bmap_ext_t      *ext;
 217
 218         if (!blkmap->nexts)
 219                 return NULLFILEOFF;
 220         ext = blkmap->exts + blkmap->nexts - 1;
 221         return ext->startoff + ext->blockcount;
 222 }
 223
 224 /**
 225  * blkmap_next_off - Return next logical block offset in a block map.
 226  * @blkmap:     blockmap to use
 227  * @o:          current file logical block number
 228  * @t:          current extent index into blockmap (in/out)
 229  *
 230  * Given a logical block offset in a file, return the next mapped logical offset
 231  * The map index "t" tracks the current extent number in the block map, and
 232  * is updated automatically if the returned offset resides within the next
 233  * mapped extent.
 234  *
 235  * If the blockmap contains no extents, or no more logical offsets are mapped,
 236  * or the extent index exceeds the number of extents in the map,
 237  * return NULLFILEOFF.
 238  *
 239  * If offset o is beyond extent index t, the first offset in the next extent
 240  * after extent t will be returned.
 241  *
 242  * Intended to be called starting with offset 0, index 0, and iterated.
 243  */
 244 xfs_fileoff_t
 245 blkmap_next_off(
 246         blkmap_t        *blkmap,
 247         xfs_fileoff_t   o,
 248         int             *t)
 249 {
 250         bmap_ext_t      *ext;
 251
 252         if (!blkmap->nexts)
 253                 return NULLFILEOFF;
 254         if (o == NULLFILEOFF) {
 255                 *t = 0;
 256                 return blkmap->exts[0].startoff;
 257         }
 258         if (*t >= blkmap->nexts)
 259                 return NULLFILEOFF;
 260         ext = blkmap->exts + *t;
 261         if (o < ext->startoff + ext->blockcount - 1)
 262                 return o + 1;
 263         if (*t == blkmap->nexts - 1)
 264                 return NULLFILEOFF;
 265         (*t)++;
 266         return ext[1].startoff;
 267 }
 268
 269 /*
 270  * Make a block map larger.
 271  */
 272 static blkmap_t *
 273 blkmap_grow(
 274         blkmap_t        *blkmap)
 275 {
 276         pthread_key_t   key = dblkmap_key;
 277         blkmap_t        *new_blkmap;
 278         int             new_naexts;
 279
 280         /* reduce the number of reallocations for large files */
 281         if (blkmap->naexts < 1000)
 282                 new_naexts = blkmap->naexts + 4;
 283         else if (blkmap->naexts < 10000)
 284                 new_naexts = blkmap->naexts + 100;
 285         else
 286                 new_naexts = blkmap->naexts + 1000;
 287
 288         if (pthread_getspecific(key) != blkmap) {
 289                 key = ablkmap_key;
 290                 ASSERT(pthread_getspecific(key) == blkmap);
 291         }
 292
 293 #if (BITS_PER_LONG == 32)       /* on 64-bit platforms this is never true */
 294         if (new_naexts > BLKMAP_NEXTS_MAX) {
 295                 do_error(
 296         _("Number of extents requested in blkmap_grow (%d) overflows 32 bits.\n"
 297           "You need a 64 bit system to repair this filesystem.\n"),
 298                         new_naexts);
 299                 return NULL;
 300         }
 301 #endif
 302         if (new_naexts <= 0) {
 303                 do_error(
 304         _("Number of extents requested in blkmap_grow (%d) overflowed the\n"
 305           "maximum number of supported extents (%d).\n"),
 306                         new_naexts, BLKMAP_NEXTS_MAX);
 307                 return NULL;
 308         }
 309
 310         new_blkmap = realloc(blkmap, BLKMAP_SIZE(new_naexts));
 311         if (!new_blkmap) {
 312                 do_error(_("realloc failed in blkmap_grow\n"));
 313                 return NULL;
 314         }
 315         new_blkmap->naexts = new_naexts;
 316         pthread_setspecific(key, new_blkmap);
 317         return new_blkmap;
 318 }
 319
 320 /*
 321  * Set an extent into a block map.
 322  *
 323  * If this function fails, it leaves the blkmapp untouched so the caller can
 324  * handle the error and free the blkmap appropriately.
 325  */
 326 int
 327 blkmap_set_ext(
 328         blkmap_t        **blkmapp,
 329         xfs_fileoff_t   o,
 330         xfs_fsblock_t   b,
 331         xfs_filblks_t   c)
 332 {
 333         blkmap_t        *blkmap = *blkmapp;
 334         xfs_extnum_t    i;
 335
 336         if (blkmap->nexts == blkmap->naexts) {
 337                 blkmap = blkmap_grow(blkmap);
 338                 if (!blkmap)
 339                         return ENOMEM;
 340                 *blkmapp = blkmap;
 341         }
 342
 343         ASSERT(blkmap->nexts < blkmap->naexts);
 344
 345         if (blkmap->nexts == 0) {
 346                 i = 0;
 347                 goto insert;
 348         }
 349
 350         /*
 351          * The most common insert pattern comes from an ascending offset order
 352          * bmapbt scan. In this case, the extent being added will end up at the
 353          * end of the array. Hence do a reverse order search for the insertion
 354          * point so we don't needlessly scan the entire array on every
 355          * insertion.
 356          *
 357          * Also, use "plus 1" indexing for the loop counter so when we break out
 358          * of the loop we are at the correct index for insertion.
 359          */
 360         for (i = blkmap->nexts; i > 0; i--) {
 361                 if (blkmap->exts[i - 1].startoff < o)
 362                         break;
 363         }
 364
 365         /* make space for the new extent */
 366         memmove(blkmap->exts + i + 1,
 367                 blkmap->exts + i,
 368                 sizeof(bmap_ext_t) * (blkmap->nexts - i));
 369
 370 insert:
 371         blkmap->exts[i].startoff = o;
 372         blkmap->exts[i].startblock = b;
 373         blkmap->exts[i].blockcount = c;
 374         blkmap->nexts++;
 375         return 0;
 376 }