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 "xfs/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  */
  87 void
  88 blkmap_free(
  89         blkmap_t        *blkmap)
  90 {
  91         if (!blkmap)
  92                 return;
  93
  94         /* consider more than 100k extents rare */
  95         if (blkmap->naexts < 100 * 1024)
  96                 return;
  97
  98         if (blkmap == pthread_getspecific(dblkmap_key))
  99                 pthread_setspecific(dblkmap_key, NULL);
 100         else
 101                 pthread_setspecific(ablkmap_key, NULL);
 102
 103         free(blkmap);
 104 }
 105
 106 /*
 107  * Get one entry from a block map.
 108  */
 109 xfs_fsblock_t
 110 blkmap_get(
 111         blkmap_t        *blkmap,
 112         xfs_fileoff_t   o)
 113 {
 114         bmap_ext_t      *ext = blkmap->exts;
 115         int             i;
 116
 117         for (i = 0; i < blkmap->nexts; i++, ext++) {
 118                 if (o >= ext->startoff && o < ext->startoff + ext->blockcount)
 119                         return ext->startblock + (o - ext->startoff);
 120         }
 121         return NULLFSBLOCK;
 122 }
 123
 124 /*
 125  * Get a chunk of entries from a block map - only used for reading dirv2 blocks
 126  */
 127 int
 128 blkmap_getn(
 129         blkmap_t        *blkmap,
 130         xfs_fileoff_t   o,
 131         xfs_filblks_t   nb,
 132         bmap_ext_t      **bmpp,
 133         bmap_ext_t      *bmpp_single)
 134 {
 135         bmap_ext_t      *bmp = NULL;
 136         bmap_ext_t      *ext;
 137         int             i;
 138         int             nex;
 139
 140         if (nb == 1) {
 141                 /*
 142                  * in the common case, when mp->m_dirblkfsbs == 1,
 143                  * avoid additional malloc/free overhead
 144                  */
 145                 bmpp_single->startblock = blkmap_get(blkmap, o);
 146                 goto single_ext;
 147         }
 148         ext = blkmap->exts;
 149         nex = 0;
 150         for (i = 0; i < blkmap->nexts; i++, ext++) {
 151
 152                 if (ext->startoff >= o + nb)
 153                         break;
 154                 if (ext->startoff + ext->blockcount <= o)
 155                         continue;
 156
 157                 /*
 158                  * if all the requested blocks are in one extent (also common),
 159                  * use the bmpp_single option as well
 160                  */
 161                 if (!bmp && o >= ext->startoff &&
 162                     o + nb <= ext->startoff + ext->blockcount) {
 163                         bmpp_single->startblock =
 164                                  ext->startblock + (o - ext->startoff);
 165                         goto single_ext;
 166                 }
 167
 168                 /*
 169                  * rare case - multiple extents for a single dir block
 170                  */
 171                 if (!bmp)
 172                         bmp = malloc(nb * sizeof(bmap_ext_t));
 173                 if (!bmp)
 174                         do_error(_("blkmap_getn malloc failed (%" PRIu64 " bytes)\n"),
 175                                                 nb * sizeof(bmap_ext_t));
 176
 177                 bmp[nex].startblock = ext->startblock + (o - ext->startoff);
 178                 bmp[nex].blockcount = MIN(nb, ext->blockcount -
 179                                 (bmp[nex].startblock - ext->startblock));
 180                 o += bmp[nex].blockcount;
 181                 nb -= bmp[nex].blockcount;
 182                 nex++;
 183         }
 184         *bmpp = bmp;
 185         return nex;
 186
 187 single_ext:
 188         bmpp_single->blockcount = nb;
 189         bmpp_single->startoff = 0;      /* not even used by caller! */
 190         *bmpp = bmpp_single;
 191         return (bmpp_single->startblock != NULLFSBLOCK) ? 1 : 0;
 192 }
 193
 194 /*
 195  * Return the last offset in a block map.
 196  */
 197 xfs_fileoff_t
 198 blkmap_last_off(
 199         blkmap_t        *blkmap)
 200 {
 201         bmap_ext_t      *ext;
 202
 203         if (!blkmap->nexts)
 204                 return NULLFILEOFF;
 205         ext = blkmap->exts + blkmap->nexts - 1;
 206         return ext->startoff + ext->blockcount;
 207 }
 208
 209 /**
 210  * blkmap_next_off - Return next logical block offset in a block map.
 211  * @blkmap:     blockmap to use
 212  * @o:          current file logical block number
 213  * @t:          current extent index into blockmap (in/out)
 214  *
 215  * Given a logical block offset in a file, return the next mapped logical offset
 216  * The map index "t" tracks the current extent number in the block map, and
 217  * is updated automatically if the returned offset resides within the next
 218  * mapped extent.
 219  *
 220  * If the blockmap contains no extents, or no more logical offsets are mapped,
 221  * or the extent index exceeds the number of extents in the map,
 222  * return NULLFILEOFF.
 223  *
 224  * If offset o is beyond extent index t, the first offset in the next extent
 225  * after extent t will be returned.
 226  *
 227  * Intended to be called starting with offset 0, index 0, and iterated.
 228  */
 229 xfs_fileoff_t
 230 blkmap_next_off(
 231         blkmap_t        *blkmap,
 232         xfs_fileoff_t   o,
 233         int             *t)
 234 {
 235         bmap_ext_t      *ext;
 236
 237         if (!blkmap->nexts)
 238                 return NULLFILEOFF;
 239         if (o == NULLFILEOFF) {
 240                 *t = 0;
 241                 return blkmap->exts[0].startoff;
 242         }
 243         if (*t >= blkmap->nexts)
 244                 return NULLFILEOFF;
 245         ext = blkmap->exts + *t;
 246         if (o < ext->startoff + ext->blockcount - 1)
 247                 return o + 1;
 248         if (*t == blkmap->nexts - 1)
 249                 return NULLFILEOFF;
 250         (*t)++;
 251         return ext[1].startoff;
 252 }
 253
 254 /*
 255  * Make a block map larger.
 256  */
 257 static blkmap_t *
 258 blkmap_grow(
 259         blkmap_t        *blkmap)
 260 {
 261         pthread_key_t   key = dblkmap_key;
 262         blkmap_t        *new_blkmap;
 263         int             new_naexts;
 264
 265         /* reduce the number of reallocations for large files */
 266         if (blkmap->naexts < 1000)
 267                 new_naexts = blkmap->naexts + 4;
 268         else if (blkmap->naexts < 10000)
 269                 new_naexts = blkmap->naexts + 100;
 270         else
 271                 new_naexts = blkmap->naexts + 1000;
 272
 273         if (pthread_getspecific(key) != blkmap) {
 274                 key = ablkmap_key;
 275                 ASSERT(pthread_getspecific(key) == blkmap);
 276         }
 277
 278 #if (BITS_PER_LONG == 32)       /* on 64-bit platforms this is never true */
 279         if (new_naexts > BLKMAP_NEXTS_MAX) {
 280                 do_error(
 281         _("Number of extents requested in blkmap_grow (%d) overflows 32 bits.\n"
 282           "You need a 64 bit system to repair this filesystem.\n"),
 283                         new_naexts);
 284                 return NULL;
 285         }
 286 #endif
 287         if (new_naexts <= 0) {
 288                 do_error(
 289         _("Number of extents requested in blkmap_grow (%d) overflowed the\n"
 290           "maximum number of supported extents (%d).\n"),
 291                         new_naexts, BLKMAP_NEXTS_MAX);
 292                 return NULL;
 293         }
 294
 295         new_blkmap = realloc(blkmap, BLKMAP_SIZE(new_naexts));
 296         if (!new_blkmap) {
 297                 do_error(_("realloc failed in blkmap_grow\n"));
 298                 return NULL;
 299         }
 300         new_blkmap->naexts = new_naexts;
 301         pthread_setspecific(key, new_blkmap);
 302         return new_blkmap;
 303 }
 304
 305 /*
 306  * Set an extent into a block map.
 307  *
 308  * If this function fails, it leaves the blkmapp untouched so the caller can
 309  * handle the error and free the blkmap appropriately.
 310  */
 311 int
 312 blkmap_set_ext(
 313         blkmap_t        **blkmapp,
 314         xfs_fileoff_t   o,
 315         xfs_fsblock_t   b,
 316         xfs_filblks_t   c)
 317 {
 318         blkmap_t        *blkmap = *blkmapp;
 319         xfs_extnum_t    i;
 320
 321         if (blkmap->nexts == blkmap->naexts) {
 322                 blkmap = blkmap_grow(blkmap);
 323                 if (!blkmap)
 324                         return ENOMEM;
 325                 *blkmapp = blkmap;
 326         }
 327
 328         ASSERT(blkmap->nexts < blkmap->naexts);
 329
 330         if (blkmap->nexts == 0) {
 331                 i = 0;
 332                 goto insert;
 333         }
 334
 335         /*
 336          * The most common insert pattern comes from an ascending offset order
 337          * bmapbt scan. In this case, the extent being added will end up at the
 338          * end of the array. Hence do a reverse order search for the insertion
 339          * point so we don't needlessly scan the entire array on every
 340          * insertion.
 341          *
 342          * Also, use "plus 1" indexing for the loop counter so when we break out
 343          * of the loop we are at the correct index for insertion.
 344          */
 345         for (i = blkmap->nexts; i > 0; i--) {
 346                 if (blkmap->exts[i - 1].startoff < o)
 347                         break;
 348         }
 349
 350         /* make space for the new extent */
 351         memmove(blkmap->exts + i + 1,
 352                 blkmap->exts + i,
 353                 sizeof(bmap_ext_t) * (blkmap->nexts - i));
 354
 355 insert:
 356         blkmap->exts[i].startoff = o;
 357         blkmap->exts[i].startblock = b;
 358         blkmap->exts[i].blockcount = c;
 359         blkmap->nexts++;
 360         return 0;
 361 }