repair/bmap.c

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