e2fsck/ea_refcount.c

   1 /*
   2  * ea_refcount.c
   3  *
   4  * Copyright (C) 2001 Theodore Ts'o.  This file may be
   5  * redistributed under the terms of the GNU Public License.
   6  */
   7
   8 #if HAVE_UNISTD_H
   9 #include <unistd.h>
  10 #endif
  11 #include <string.h>
  12 #include <stdio.h>
  13
  14 #include "e2fsck.h"
  15
  16 /*
  17  * The strategy we use for keeping track of EA refcounts is as
  18  * follows.  We keep a sorted array of first EA blocks and its
  19  * reference counts.  Once the refcount has dropped to zero, it is
  20  * removed from the array to save memory space.  Once the EA block is
  21  * checked, its bit is set in the block_ea_map bitmap.
  22  */
  23 struct ea_refcount_el {
  24         blk_t   ea_blk;
  25         int     ea_count;
  26 };
  27
  28 struct ea_refcount {
  29         blk_t           count;
  30         blk_t           size;
  31         int             cursor;
  32         struct ea_refcount_el   *list;
  33 };
  34
  35 void ea_refcount_free(ext2_refcount_t refcount)
  36 {
  37         if (!refcount)
  38                 return;
  39
  40         if (refcount->list)
  41                 ext2fs_free_mem((void **) &refcount->list);
  42         ext2fs_free_mem((void **) &refcount);
  43 }
  44
  45 errcode_t ea_refcount_create(int size, ext2_refcount_t *ret)
  46 {
  47         ext2_refcount_t refcount;
  48         errcode_t       retval;
  49         size_t          bytes;
  50
  51         retval = ext2fs_get_mem(sizeof(struct ea_refcount),
  52                                 (void **) &refcount);
  53         if (retval)
  54                 return retval;
  55         memset(refcount, 0, sizeof(struct ea_refcount));
  56
  57         if (!size)
  58                 size = 500;
  59         refcount->size = size;
  60         bytes = (size_t) (size * sizeof(struct ea_refcount_el));
  61 #ifdef DEBUG
  62         printf("Refcount allocated %d entries, %d bytes.\n",
  63                refcount->size, bytes);
  64 #endif
  65         retval = ext2fs_get_mem(bytes, (void **) &refcount->list);
  66         if (retval)
  67                 goto errout;
  68         memset(refcount->list, 0, bytes);
  69
  70         refcount->count = 0;
  71         refcount->cursor = 0;
  72
  73         *ret = refcount;
  74         return 0;
  75
  76 errout:
  77         ea_refcount_free(refcount);
  78         return(retval);
  79 }
  80
  81 /*
  82  * collapse_refcount() --- go through the refcount array, and get rid
  83  * of any count == zero entries
  84  */
  85 static void refcount_collapse(ext2_refcount_t refcount)
  86 {
  87         int     i, j;
  88         struct ea_refcount_el   *list;
  89
  90         list = refcount->list;
  91         for (i = 0, j = 0; i < refcount->count; i++) {
  92                 if (list[i].ea_count) {
  93                         if (i != j)
  94                                 list[j] = list[i];
  95                         j++;
  96                 }
  97         }
  98 #if defined(DEBUG) || defined(TEST_PROGRAM)
  99         printf("Refcount_collapse: size was %d, now %d\n",
 100                refcount->count, j);
 101 #endif
 102         refcount->count = j;
 103 }
 104
 105
 106 /*
 107  * insert_refcount_el() --- Insert a new entry into the sorted list at a
 108  *      specified position.
 109  */
 110 static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount,
 111                                                  blk_t blk, int pos)
 112 {
 113         struct ea_refcount_el   *el;
 114         errcode_t               retval;
 115         blk_t                   new_size = 0;
 116         int                     num;
 117
 118         if (refcount->count >= refcount->size) {
 119                 new_size = refcount->size + 100;
 120 #ifdef DEBUG
 121                 printf("Reallocating refcount %d entries...\n", new_size);
 122 #endif
 123                 retval = ext2fs_resize_mem((size_t) refcount->size *
 124                                            sizeof(struct ea_refcount_el),
 125                                            (size_t) new_size *
 126                                            sizeof(struct ea_refcount_el),
 127                                            (void **) &refcount->list);
 128                 if (retval)
 129                         return 0;
 130                 refcount->size = new_size;
 131         }
 132         num = (int) refcount->count - pos;
 133         if (num < 0)
 134                 return 0;       /* should never happen */
 135         if (num) {
 136                 memmove(&refcount->list[pos+1], &refcount->list[pos],
 137                         sizeof(struct ea_refcount_el) * num);
 138         }
 139         refcount->count++;
 140         el = &refcount->list[pos];
 141         el->ea_count = 0;
 142         el->ea_blk = blk;
 143         return el;
 144 }
 145
 146
 147 /*
 148  * get_refcount_el() --- given an block number, try to find refcount
 149  *      information in the sorted list.  If the create flag is set,
 150  *      and we can't find an entry, create one in the sorted list.
 151  */
 152 static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount,
 153                                               blk_t blk, int create)
 154 {
 155         float   range;
 156         int     low, high, mid;
 157         blk_t   lowval, highval;
 158
 159         if (!refcount || !refcount->list)
 160                 return 0;
 161 retry:
 162         low = 0;
 163         high = (int) refcount->count-1;
 164         if (create && ((refcount->count == 0) ||
 165                        (blk > refcount->list[high].ea_blk))) {
 166                 if (refcount->count >= refcount->size)
 167                         refcount_collapse(refcount);
 168
 169                 return insert_refcount_el(refcount, blk,
 170                                           (unsigned) refcount->count);
 171         }
 172         if (refcount->count == 0)
 173                 return 0;
 174
 175         if (refcount->cursor >= refcount->count)
 176                 refcount->cursor = 0;
 177         if (blk == refcount->list[refcount->cursor].ea_blk)
 178                 return &refcount->list[refcount->cursor++];
 179 #ifdef DEBUG
 180         printf("Non-cursor get_refcount_el: %u\n", blk);
 181 #endif
 182         while (low <= high) {
 183 #if 0
 184                 mid = (low+high)/2;
 185 #else
 186                 if (low == high)
 187                         mid = low;
 188                 else {
 189                         /* Interpolate for efficiency */
 190                         lowval = refcount->list[low].ea_blk;
 191                         highval = refcount->list[high].ea_blk;
 192
 193                         if (blk < lowval)
 194                                 range = 0;
 195                         else if (blk > highval)
 196                                 range = 1;
 197                         else
 198                                 range = ((float) (blk - lowval)) /
 199                                         (highval - lowval);
 200                         mid = low + ((int) (range * (high-low)));
 201                 }
 202 #endif
 203                 if (blk == refcount->list[mid].ea_blk) {
 204                         refcount->cursor = mid+1;
 205                         return &refcount->list[mid];
 206                 }
 207                 if (blk < refcount->list[mid].ea_blk)
 208                         high = mid-1;
 209                 else
 210                         low = mid+1;
 211         }
 212         /*
 213          * If we need to create a new entry, it should be right at
 214          * low (where high will be left at low-1).
 215          */
 216         if (create) {
 217                 if (refcount->count >= refcount->size) {
 218                         refcount_collapse(refcount);
 219                         if (refcount->count < refcount->size)
 220                                 goto retry;
 221                 }
 222                 return insert_refcount_el(refcount, blk, low);
 223         }
 224         return 0;
 225 }
 226
 227 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk,
 228                                 int *ret)
 229 {
 230         struct ea_refcount_el   *el;
 231
 232         el = get_refcount_el(refcount, blk, 0);
 233         if (!el) {
 234                 *ret = 0;
 235                 return 0;
 236         }
 237         *ret = el->ea_count;
 238         return 0;
 239 }
 240
 241 errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret)
 242 {
 243         struct ea_refcount_el   *el;
 244
 245         el = get_refcount_el(refcount, blk, 1);
 246         if (!el)
 247                 return EXT2_ET_NO_MEMORY;
 248         el->ea_count++;
 249
 250         if (ret)
 251                 *ret = el->ea_count;
 252         return 0;
 253 }
 254
 255 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret)
 256 {
 257         struct ea_refcount_el   *el;
 258
 259         el = get_refcount_el(refcount, blk, 0);
 260         if (!el || el->ea_count == 0)
 261                 return EXT2_ET_INVALID_ARGUMENT;
 262
 263         el->ea_count--;
 264
 265         if (ret)
 266                 *ret = el->ea_count;
 267         return 0;
 268 }
 269
 270 errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count)
 271 {
 272         struct ea_refcount_el   *el;
 273
 274         /*
 275          * Get the refcount element
 276          */
 277         el = get_refcount_el(refcount, blk, count ? 1 : 0);
 278         if (!el)
 279                 return count ? EXT2_ET_NO_MEMORY : 0;
 280         el->ea_count = count;
 281         return 0;
 282 }
 283
 284 blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount)
 285 {
 286         if (!refcount)
 287                 return 0;
 288
 289         return refcount->size;
 290 }
 291
 292 void ea_refcount_intr_begin(ext2_refcount_t refcount)
 293 {
 294         refcount->cursor = 0;
 295 }
 296
 297
 298 blk_t ea_refcount_intr_next(ext2_refcount_t refcount,
 299                                 int *ret)
 300 {
 301         struct ea_refcount_el   *list;
 302
 303         while (1) {
 304                 if (refcount->cursor >= refcount->count)
 305                         return 0;
 306                 list = refcount->list;
 307                 if (list[refcount->cursor].ea_count) {
 308                         if (ret)
 309                                 *ret = list[refcount->cursor].ea_count;
 310                         return list[refcount->cursor++].ea_blk;
 311                 }
 312                 refcount->cursor++;
 313         }
 314 }
 315
 316
 317 #ifdef TEST_PROGRAM
 318
 319 errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out)
 320 {
 321         errcode_t       ret = 0;
 322         int             i;
 323         const char *bad = "bad refcount";
 324
 325         if (refcount->count > refcount->size) {
 326                 fprintf(out, "%s: count > size\n", bad);
 327                 return EXT2_ET_INVALID_ARGUMENT;
 328         }
 329         for (i=1; i < refcount->count; i++) {
 330                 if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) {
 331                         fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n",
 332                                 bad, i-1, refcount->list[i-1].ea_blk,
 333                                 i, refcount->list[i].ea_blk);
 334                         ret = EXT2_ET_INVALID_ARGUMENT;
 335                 }
 336         }
 337         return ret;
 338 }
 339
 340 #define BCODE_END       0
 341 #define BCODE_CREATE    1
 342 #define BCODE_FREE      2
 343 #define BCODE_STORE     3
 344 #define BCODE_INCR      4
 345 #define BCODE_DECR      5
 346 #define BCODE_FETCH     6
 347 #define BCODE_VALIDATE  7
 348 #define BCODE_LIST      8
 349 #define BCODE_COLLAPSE 9
 350
 351 int bcode_program[] = {
 352         BCODE_CREATE, 5,
 353         BCODE_STORE, 3, 3,
 354         BCODE_STORE, 4, 4,
 355         BCODE_STORE, 1, 1,
 356         BCODE_STORE, 8, 8,
 357         BCODE_STORE, 2, 2,
 358         BCODE_STORE, 4, 0,
 359         BCODE_STORE, 2, 0,
 360         BCODE_STORE, 6, 6,
 361         BCODE_VALIDATE,
 362         BCODE_STORE, 4, 4,
 363         BCODE_STORE, 2, 2,
 364         BCODE_FETCH, 1,
 365         BCODE_FETCH, 2,
 366         BCODE_INCR, 3,
 367         BCODE_INCR, 3,
 368         BCODE_DECR, 4,
 369         BCODE_STORE, 4, 4,
 370         BCODE_VALIDATE,
 371         BCODE_STORE, 20, 20,
 372         BCODE_STORE, 40, 40,
 373         BCODE_STORE, 30, 30,
 374         BCODE_STORE, 10, 10,
 375         BCODE_DECR, 30,
 376         BCODE_FETCH, 30,
 377         BCODE_DECR, 2,
 378         BCODE_DECR, 2,
 379         BCODE_COLLAPSE,
 380         BCODE_LIST,
 381         BCODE_VALIDATE,
 382         BCODE_FREE,
 383         BCODE_END
 384 };
 385
 386 int main(int argc, char **argv)
 387 {
 388         int     i = 0;
 389         ext2_refcount_t refcount;
 390         int             size, arg;
 391         blk_t           blk;
 392         errcode_t       retval;
 393
 394         while (1) {
 395                 switch (bcode_program[i++]) {
 396                 case BCODE_END:
 397                         exit(0);
 398                 case BCODE_CREATE:
 399                         size = bcode_program[i++];
 400                         retval = ea_refcount_create(size, &refcount);
 401                         if (retval) {
 402                                 com_err("ea_refcount_create",
 403                                         retval, "");
 404                                 exit(1);
 405                         } else
 406                                 printf("Creating refcount with size %d\n",
 407                                        size);
 408                         break;
 409                 case BCODE_FREE:
 410                         ea_refcount_free(refcount);
 411                         refcount = 0;
 412                         printf("Freeing refcount\n");
 413                         break;
 414                 case BCODE_STORE:
 415                         blk = (blk_t) bcode_program[i++];
 416                         arg = bcode_program[i++];
 417                         retval = ea_refcount_store(refcount, blk, arg);
 418                         printf("Storing blk %u with value %d\n", blk, arg);
 419                         if (retval)
 420                                 com_err("ea_refcount_store", retval, "");
 421                         break;
 422                 case BCODE_FETCH:
 423                         blk = (blk_t) bcode_program[i++];
 424                         retval = ea_refcount_fetch(refcount, blk, &arg);
 425                         if (retval)
 426                                 com_err("ea_refcount_fetch", retval, "");
 427                         else
 428                                 printf("bcode_fetch(%u) returns %d\n",
 429                                        blk, arg);
 430                         break;
 431                 case BCODE_INCR:
 432                         blk = (blk_t) bcode_program[i++];
 433                         retval = ea_refcount_increment(refcount, blk,
 434                                                            &arg);
 435                         if (retval)
 436                                 com_err("ea_refcount_increment", retval,
 437                                         "");
 438                         else
 439                                 printf("bcode_increment(%u) returns %d\n",
 440                                        blk, arg);
 441                         break;
 442                 case BCODE_DECR:
 443                         blk = (blk_t) bcode_program[i++];
 444                         retval = ea_refcount_decrement(refcount, blk,
 445                                                            &arg);
 446                         if (retval)
 447                                 com_err("ea_refcount_decrement", retval,
 448                                         "while decrementing blk %u", blk);
 449                         else
 450                                 printf("bcode_decrement(%u) returns %d\n",
 451                                        blk, arg);
 452                         break;
 453                 case BCODE_VALIDATE:
 454                         retval = ea_refcount_validate(refcount, stderr);
 455                         if (retval)
 456                                 com_err("ea_refcount_validate",
 457                                         retval, "");
 458                         else
 459                                 printf("Refcount validation OK.\n");
 460                         break;
 461                 case BCODE_LIST:
 462                         ea_refcount_intr_begin(refcount);
 463                         while (1) {
 464                                 blk = ea_refcount_intr_next(refcount,
 465                                                                 &arg);
 466                                 if (!blk)
 467                                         break;
 468                                 printf("\tblk=%u, count=%d\n", blk,
 469                                        arg);
 470                         }
 471                         break;
 472                 case BCODE_COLLAPSE:
 473                         refcount_collapse(refcount);
 474                         break;
 475                 }
 476
 477         }
 478 }
 479
 480 #endif