repair/bmap.c

   1 /*
   2  * Copyright (c) 2000 Silicon Graphics, Inc.  All Rights Reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of version 2 of the GNU General Public License as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it would be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11  *
  12  * Further, this software is distributed without any warranty that it is
  13  * free of the rightful claim of any third person regarding infringement
  14  * or the like.  Any license provided herein, whether implied or
  15  * otherwise, applies only to this software file.  Patent licenses, if
  16  * any, provided herein do not apply to combinations of this program with
  17  * other software, or any other product whatsoever.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write the Free Software Foundation, Inc., 59
  21  * Temple Place - Suite 330, Boston MA 02111-1307, USA.
  22  *
  23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24  * Mountain View, CA  94043, or:
  25  *
  26  * http://www.sgi.com
  27  *
  28  * For further information regarding this notice, see:
  29  *
  30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31  */
  32
  33 #include <libxfs.h>
  34 #include "err_protos.h"
  35 #include "bmap.h"
  36
  37 /*
  38  * Block mapping code taken from xfs_db.
  39  */
  40
  41 /*
  42  * Append an extent to the block entry.
  43  */
  44 void
  45 blkent_append(
  46         blkent_t        **entp,
  47         xfs_dfsbno_t    b,
  48         xfs_dfilblks_t  c)
  49 {
  50         blkent_t        *ent;
  51         size_t          size;
  52         int             i;
  53
  54         ent = *entp;
  55         size = BLKENT_SIZE(c + ent->nblks);
  56         if ((*entp = ent = realloc(ent, size)) == NULL) {
  57                 do_warn("realloc failed in blkent_append (%u bytes)\n", size);
  58                 return;
  59         }
  60         for (i = 0; i < c; i++)
  61                 ent->blks[ent->nblks + i] = b + i;
  62         ent->nblks += c;
  63 }
  64
  65 /*
  66  * Make a new block entry.
  67  */
  68 blkent_t *
  69 blkent_new(
  70         xfs_dfiloff_t   o,
  71         xfs_dfsbno_t    b,
  72         xfs_dfilblks_t  c)
  73 {
  74         blkent_t        *ent;
  75         int             i;
  76
  77         if ((ent = malloc(BLKENT_SIZE(c))) == NULL) {
  78                 do_warn("malloc failed in blkent_new (%u bytes)\n",
  79                         BLKENT_SIZE(c));
  80                 return ent;
  81         }
  82         ent->nblks = c;
  83         ent->startoff = o;
  84         for (i = 0; i < c; i++)
  85                 ent->blks[i] = b + i;
  86         return ent;
  87 }
  88
  89 /*
  90  * Prepend an extent to the block entry.
  91  */
  92 void
  93 blkent_prepend(
  94         blkent_t        **entp,
  95         xfs_dfsbno_t    b,
  96         xfs_dfilblks_t  c)
  97 {
  98         int             i;
  99         blkent_t        *newent;
 100         blkent_t        *oldent;
 101
 102         oldent = *entp;
 103         if ((newent = malloc(BLKENT_SIZE(oldent->nblks + c))) == NULL) {
 104                 do_warn("malloc failed in blkent_prepend (%u bytes)\n",
 105                         BLKENT_SIZE(oldent->nblks + c));
 106                 *entp = newent;
 107                 return;
 108         }
 109         newent->nblks = oldent->nblks + c;
 110         newent->startoff = oldent->startoff - c;
 111         for (i = 0; i < c; i++)
 112                 newent->blks[i] = b + c;
 113         for (; i < oldent->nblks + c; i++)
 114                 newent->blks[i] = oldent->blks[i - c];
 115         free(oldent);
 116         *entp = newent;
 117 }
 118
 119 /*
 120  * Allocate a block map.
 121  */
 122 blkmap_t *
 123 blkmap_alloc(
 124         xfs_extnum_t    nex)
 125 {
 126         blkmap_t        *blkmap;
 127
 128         if (nex < 1)
 129                 nex = 1;
 130         if ((blkmap = malloc(BLKMAP_SIZE(nex))) == NULL) {
 131                 do_warn("malloc failed in blkmap_alloc (%u bytes)\n",
 132                         BLKMAP_SIZE(nex));
 133                 return blkmap;
 134         }
 135         blkmap->naents = nex;
 136         blkmap->nents = 0;
 137         return blkmap;
 138 }
 139
 140 /*
 141  * Free a block map.
 142  */
 143 void
 144 blkmap_free(
 145         blkmap_t        *blkmap)
 146 {
 147         blkent_t        **entp;
 148         xfs_extnum_t    i;
 149
 150         if (blkmap == NULL)
 151                 return;
 152         for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++)
 153                 free(*entp);
 154         free(blkmap);
 155 }
 156
 157 /*
 158  * Get one entry from a block map.
 159  */
 160 xfs_dfsbno_t
 161 blkmap_get(
 162         blkmap_t        *blkmap,
 163         xfs_dfiloff_t   o)
 164 {
 165         blkent_t        *ent;
 166         blkent_t        **entp;
 167         int             i;
 168
 169         for (i = 0, entp = blkmap->ents; i < blkmap->nents; i++, entp++) {
 170                 ent = *entp;
 171                 if (o >= ent->startoff && o < ent->startoff + ent->nblks)
 172                         return ent->blks[o - ent->startoff];
 173         }
 174         return NULLDFSBNO;
 175 }
 176
 177 /*
 178  * Get a chunk of entries from a block map.
 179  */
 180 int
 181 blkmap_getn(
 182         blkmap_t        *blkmap,
 183         xfs_dfiloff_t   o,
 184         xfs_dfilblks_t  nb,
 185         bmap_ext_t      **bmpp)
 186 {
 187         bmap_ext_t      *bmp;
 188         blkent_t        *ent;
 189         xfs_dfiloff_t   ento;
 190         blkent_t        **entp;
 191         int             i;
 192         int             nex;
 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("realloc failed in blkmap_getn"
 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 }