repair/bmap.c

   1 /*
   2  * Copyright (c) 2000-2001,2005 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  * Block mapping code taken from xfs_db.
  25  */
  26
  27 /*
  28  * Append an extent to the block entry.
  29  */
  30 void
  31 blkent_append(
  32         blkent_t        **entp,
  33         xfs_dfsbno_t    b,
  34         xfs_dfilblks_t  c)
  35 {
  36         blkent_t        *ent;
  37         size_t          size;
  38         int             i;
  39
  40         ent = *entp;
  41         size = BLKENT_SIZE(c + ent->nblks);
  42         if ((*entp = ent = realloc(ent, size)) == NULL) {
  43                 do_warn(_("realloc failed in blkent_append (%u bytes)\n"),
  44                         size);
  45                 return;
  46         }
  47         for (i = 0; i < c; i++)
  48                 ent->blks[ent->nblks + i] = b + i;
  49         ent->nblks += c;
  50 }
  51
  52 /*
  53  * Make a new block entry.
  54  */
  55 blkent_t *
  56 blkent_new(
  57         xfs_dfiloff_t   o,
  58         xfs_dfsbno_t    b,
  59         xfs_dfilblks_t  c)
  60 {
  61         blkent_t        *ent;
  62         int             i;
  63
  64         if ((ent = malloc(BLKENT_SIZE(c))) == NULL) {
  65                 do_warn(_("malloc failed in blkent_new (%u bytes)\n"),
  66                         BLKENT_SIZE(c));
  67                 return ent;
  68         }
  69         ent->nblks = c;
  70         ent->startoff = o;
  71         for (i = 0; i < c; i++)
  72                 ent->blks[i] = b + i;
  73         return ent;
  74 }
  75
  76 /*
  77  * Prepend an extent to the block entry.
  78  */
  79 void
  80 blkent_prepend(
  81         blkent_t        **entp,
  82         xfs_dfsbno_t    b,
  83         xfs_dfilblks_t  c)
  84 {
  85         int             i;
  86         blkent_t        *newent;
  87         blkent_t        *oldent;
  88
  89         oldent = *entp;
  90         if ((newent = malloc(BLKENT_SIZE(oldent->nblks + c))) == NULL) {
  91                 do_warn(_("malloc failed in blkent_prepend (%u bytes)\n"),
  92                         BLKENT_SIZE(oldent->nblks + c));
  93                 *entp = newent;
  94                 return;
  95         }
  96         newent->nblks = oldent->nblks + c;
  97         newent->startoff = oldent->startoff - c;
  98         for (i = 0; i < c; i++)
  99                 newent->blks[i] = b + c;
 100         for (; i < oldent->nblks + c; i++)
 101                 newent->blks[i] = oldent->blks[i - c];
 102         free(oldent);
 103         *entp = newent;
 104 }
 105
 106 /*
 107  * Allocate a block map.
 108  */
 109 blkmap_t *
 110 blkmap_alloc(
 111         xfs_extnum_t    nex)
 112 {
 113         blkmap_t        *blkmap;
 114
 115         if (nex < 1)
 116                 nex = 1;
 117         if ((blkmap = malloc(BLKMAP_SIZE(nex))) == NULL) {
 118                 do_warn(_("malloc failed in blkmap_alloc (%u bytes)\n"),
 119                         BLKMAP_SIZE(nex));
 120                 return blkmap;
 121         }
 122         blkmap->naents = nex;
 123         blkmap->nents = 0;
 124         return blkmap;
 125 }
 126
 127 /*
 128  * Free a block map.
 129  */
 130 void
 131 blkmap_free(
 132         blkmap_t        *blkmap)
 133 {
 134         blkent_t        **entp;
 135         xfs_extnum_t    i;
 136
 137         if (blkmap == NULL)
 138                 return;
 139         for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++)
 140                 free(*entp);
 141         free(blkmap);
 142 }
 143
 144 /*
 145  * Get one entry from a block map.
 146  */
 147 xfs_dfsbno_t
 148 blkmap_get(
 149         blkmap_t        *blkmap,
 150         xfs_dfiloff_t   o)
 151 {
 152         blkent_t        *ent;
 153         blkent_t        **entp;
 154         int             i;
 155
 156         for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++) {
 157                 ent = *entp;
 158                 if (o >= ent->startoff && o < ent->startoff + ent->nblks)
 159                         return ent->blks[o - ent->startoff];
 160         }
 161         return NULLDFSBNO;
 162 }
 163
 164 /*
 165  * Get a chunk of entries from a block map.
 166  */
 167 int
 168 blkmap_getn(
 169         blkmap_t        *blkmap,
 170         xfs_dfiloff_t   o,
 171         xfs_dfilblks_t  nb,
 172         bmap_ext_t      **bmpp,
 173         bmap_ext_t      *bmpp_single)
 174 {
 175         bmap_ext_t      *bmp;
 176         blkent_t        *ent;
 177         xfs_dfiloff_t   ento;
 178         blkent_t        **entp;
 179         int             i;
 180         int             nex;
 181
 182         if (nb == 1) {
 183                 /*
 184                  * in the common case, when mp->m_dirblkfsbs == 1,
 185                  * avoid additional malloc/free overhead
 186                  */
 187                 bmpp_single->startblock = blkmap_get(blkmap, o);
 188                 bmpp_single->blockcount = 1;
 189                 bmpp_single->startoff = 0;
 190                 bmpp_single->flag = 0;
 191                 *bmpp = bmpp_single;
 192                 return (bmpp_single->startblock != NULLDFSBNO) ? 1 : 0;
 193         }
 194         for (i = nex = 0, bmp = NULL, entp = blkmap->ents;
 195              i < blkmap->nents;
 196              i++, entp++) {
 197                 ent = *entp;
 198                 if (ent->startoff >= o + nb)
 199                         break;
 200                 if (ent->startoff + ent->nblks <= o)
 201                         continue;
 202                 for (ento = ent->startoff;
 203                      ento < ent->startoff + ent->nblks && ento < o + nb;
 204                      ento++) {
 205                         if (ento < o)
 206                                 continue;
 207                         if (bmp &&
 208                             bmp[nex - 1].startoff + bmp[nex - 1].blockcount ==
 209                                     ento &&
 210                             bmp[nex - 1].startblock + bmp[nex - 1].blockcount ==
 211                                     ent->blks[ento - ent->startoff])
 212                                 bmp[nex - 1].blockcount++;
 213                         else {
 214                                 bmp = realloc(bmp, ++nex * sizeof(*bmp));
 215                                 if (bmp == NULL) {
 216                                         do_warn(_("blkmap_getn realloc failed"
 217                                                 " (%u bytes)\n"),
 218                                                 nex * sizeof(*bmp));
 219                                         continue;
 220                                 }
 221                                 bmp[nex - 1].startoff = ento;
 222                                 bmp[nex - 1].startblock =
 223                                         ent->blks[ento - ent->startoff];
 224                                 bmp[nex - 1].blockcount = 1;
 225                                 bmp[nex - 1].flag = 0;
 226                         }
 227                 }
 228         }
 229         *bmpp = bmp;
 230         return nex;
 231 }
 232
 233 /*
 234  * Make a block map larger.
 235  */
 236 void
 237 blkmap_grow(
 238         blkmap_t        **blkmapp,
 239         blkent_t        **entp,
 240         blkent_t        *newent)
 241 {
 242         blkmap_t        *blkmap;
 243         size_t          size;
 244         int             i;
 245         int             idx;
 246
 247         blkmap = *blkmapp;
 248         idx = (int)(entp - blkmap->ents);
 249         if (blkmap->naents == blkmap->nents) {
 250                 size = BLKMAP_SIZE(blkmap->nents + 1);
 251                 if ((*blkmapp = blkmap = realloc(blkmap, size)) == NULL) {
 252                         do_warn(_("realloc failed in blkmap_grow (%u bytes)\n"),
 253                                 size);
 254                         return;
 255                 }
 256                 blkmap->naents++;
 257         }
 258         for (i = blkmap->nents; i > idx; i--)
 259                 blkmap->ents[i] = blkmap->ents[i - 1];
 260         blkmap->ents[idx] = newent;
 261         blkmap->nents++;
 262 }
 263
 264 /*
 265  * Return the last offset in a block map.
 266  */
 267 xfs_dfiloff_t
 268 blkmap_last_off(
 269         blkmap_t        *blkmap)
 270 {
 271         blkent_t        *ent;
 272
 273         if (!blkmap->nents)
 274                 return NULLDFILOFF;
 275         ent = blkmap->ents[blkmap->nents - 1];
 276         return ent->startoff + ent->nblks;
 277 }
 278
 279 /*
 280  * Return the next offset in a block map.
 281  */
 282 xfs_dfiloff_t
 283 blkmap_next_off(
 284         blkmap_t        *blkmap,
 285         xfs_dfiloff_t   o,
 286         int             *t)
 287 {
 288         blkent_t        *ent;
 289         blkent_t        **entp;
 290
 291         if (!blkmap->nents)
 292                 return NULLDFILOFF;
 293         if (o == NULLDFILOFF) {
 294                 *t = 0;
 295                 ent = blkmap->ents[0];
 296                 return ent->startoff;
 297         }
 298         entp = &blkmap->ents[*t];
 299         ent = *entp;
 300         if (o < ent->startoff + ent->nblks - 1)
 301                 return o + 1;
 302         entp++;
 303         if (entp >= &blkmap->ents[blkmap->nents])
 304                 return NULLDFILOFF;
 305         (*t)++;
 306         ent = *entp;
 307         return ent->startoff;
 308 }
 309
 310 /*
 311  * Set a block value in a block map.
 312  */
 313 void
 314 blkmap_set_blk(
 315         blkmap_t        **blkmapp,
 316         xfs_dfiloff_t   o,
 317         xfs_dfsbno_t    b)
 318 {
 319         blkmap_t        *blkmap;
 320         blkent_t        *ent;
 321         blkent_t        **entp;
 322         blkent_t        *nextent;
 323
 324         blkmap = *blkmapp;
 325         for (entp = blkmap->ents; entp < &blkmap->ents[blkmap->nents]; entp++) {
 326                 ent = *entp;
 327                 if (o < ent->startoff - 1) {
 328                         ent = blkent_new(o, b, 1);
 329                         blkmap_grow(blkmapp, entp, ent);
 330                         return;
 331                 }
 332                 if (o == ent->startoff - 1) {
 333                         blkent_prepend(entp, b, 1);
 334                         return;
 335                 }
 336                 if (o >= ent->startoff && o < ent->startoff + ent->nblks) {
 337                         ent->blks[o - ent->startoff] = b;
 338                         return;
 339                 }
 340                 if (o > ent->startoff + ent->nblks)
 341                         continue;
 342                 blkent_append(entp, b, 1);
 343                 if (entp == &blkmap->ents[blkmap->nents - 1])
 344                         return;
 345                 ent = *entp;
 346                 nextent = entp[1];
 347                 if (ent->startoff + ent->nblks < nextent->startoff)
 348                         return;
 349                 blkent_append(entp, nextent->blks[0], nextent->nblks);
 350                 blkmap_shrink(blkmap, &entp[1]);
 351                 return;
 352         }
 353         ent = blkent_new(o, b, 1);
 354         blkmap_grow(blkmapp, entp, ent);
 355 }
 356
 357 /*
 358  * Set an extent into a block map.
 359  */
 360 void
 361 blkmap_set_ext(
 362         blkmap_t        **blkmapp,
 363         xfs_dfiloff_t   o,
 364         xfs_dfsbno_t    b,
 365         xfs_dfilblks_t  c)
 366 {
 367         blkmap_t        *blkmap;
 368         blkent_t        *ent;
 369         blkent_t        **entp;
 370         xfs_extnum_t    i;
 371
 372         blkmap = *blkmapp;
 373         if (!blkmap->nents) {
 374                 blkmap->ents[0] = blkent_new(o, b, c);
 375                 blkmap->nents = 1;
 376                 return;
 377         }
 378         entp = &blkmap->ents[blkmap->nents - 1];
 379         ent = *entp;
 380         if (ent->startoff + ent->nblks == o) {
 381                 blkent_append(entp, b, c);
 382                 return;
 383         }
 384         if (ent->startoff + ent->nblks < o) {
 385                 ent = blkent_new(o, b, c);
 386                 blkmap_grow(blkmapp, &blkmap->ents[blkmap->nents], ent);
 387                 return;
 388         }
 389         for (i = 0; i < c; i++)
 390                 blkmap_set_blk(blkmapp, o + i, b + i);
 391 }
 392
 393 /*
 394  * Make a block map smaller.
 395  */
 396 void
 397 blkmap_shrink(
 398         blkmap_t        *blkmap,
 399         blkent_t        **entp)
 400 {
 401         int             i;
 402         int             idx;
 403
 404         free(*entp);
 405         idx = (int)(entp - blkmap->ents);
 406         for (i = idx + 1; i < blkmap->nents; i++)
 407                 blkmap->ents[i] = blkmap->ents[i - 1];
 408         blkmap->nents--;
 409 }