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 #include "config.h"
   9 #if HAVE_UNISTD_H
  10 #include <unistd.h>
  11 #endif
  12 #include <string.h>
  13 #include <stdio.h>
  14
  15 #ifdef TEST_PROGRAM
  16 #undef ENABLE_NLS
  17 #endif
  18 #include "e2fsck.h"
  19 #include "ext2fs/rbtree.h"
  20
  21 /*
  22  * The strategy we use for keeping track of EA refcounts is as
  23  * follows.  We keep the first EA blocks and its reference counts
  24  * in the rb-tree.  Once the refcount has dropped to zero, it is
  25  * removed from the rb-tree to save memory space.  Once the EA block is
  26  * checked, its bit is set in the block_ea_map bitmap.
  27  */
  28 struct ea_refcount_el {
  29         struct rb_node  node;
  30         /* ea_key could either be an inode number or block number. */
  31         ea_key_t        ea_key;
  32         ea_value_t      ea_value;
  33 };
  34
  35 struct ea_refcount {
  36         struct rb_root  root;
  37         struct rb_node  *cursor;
  38 };
  39
  40 void ea_refcount_free(ext2_refcount_t refcount)
  41 {
  42         struct ea_refcount_el *el;
  43         struct rb_node *node, *next;
  44
  45         if (!refcount)
  46                 return;
  47
  48         for (node = ext2fs_rb_first(&refcount->root); node; node = next) {
  49                 next = ext2fs_rb_next(node);
  50                 el = ext2fs_rb_entry(node, struct ea_refcount_el, node);
  51                 ext2fs_rb_erase(node, &refcount->root);
  52                 ext2fs_free_mem(&el);
  53         }
  54         ext2fs_free_mem(&refcount);
  55 }
  56
  57 errcode_t ea_refcount_create(ext2_refcount_t *ret)
  58 {
  59         ext2_refcount_t refcount;
  60         errcode_t       retval;
  61
  62         retval = ext2fs_get_memzero(sizeof(struct ea_refcount), &refcount);
  63         if (retval)
  64                 return retval;
  65         refcount->root = RB_ROOT;
  66
  67         *ret = refcount;
  68         return 0;
  69 }
  70
  71 /*
  72  * get_refcount_el() --- given an block number, try to find refcount
  73  *      information in the rb-tree.  If the create flag is set,
  74  *      and we can't find an entry, create and add it to rb-tree.
  75  */
  76 static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount,
  77                                               ea_key_t ea_key, int create)
  78 {
  79         struct rb_node          **node;
  80         struct rb_node          *parent = NULL;
  81         struct ea_refcount_el   *el;
  82         errcode_t               retval;
  83
  84         if (!refcount)
  85                 return 0;
  86
  87         node = &refcount->root.rb_node;
  88         while (*node) {
  89                 el = ext2fs_rb_entry(*node, struct ea_refcount_el, node);
  90
  91                 parent = *node;
  92                 if (ea_key < el->ea_key)
  93                         node = &(*node)->rb_left;
  94                 else if (ea_key > el->ea_key)
  95                         node = &(*node)->rb_right;
  96                 else
  97                         return el;
  98         }
  99
 100         if (!create)
 101                 return 0;
 102
 103         retval = ext2fs_get_memzero(sizeof(struct ea_refcount_el), &el);
 104         if (retval)
 105                 return 0;
 106
 107         el->ea_key = ea_key;
 108         el->ea_value = 0;
 109         ext2fs_rb_link_node(&el->node, parent, node);
 110         ext2fs_rb_insert_color(&el->node, &refcount->root);
 111
 112         return el;
 113 }
 114
 115 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, ea_key_t ea_key,
 116                             ea_value_t *ret)
 117 {
 118         struct ea_refcount_el   *el;
 119
 120         el = get_refcount_el(refcount, ea_key, 0);
 121         if (!el) {
 122                 *ret = 0;
 123                 return 0;
 124         }
 125         *ret = el->ea_value;
 126         return 0;
 127 }
 128
 129 errcode_t ea_refcount_increment(ext2_refcount_t refcount, ea_key_t ea_key,
 130                                 ea_value_t *ret)
 131 {
 132         struct ea_refcount_el   *el;
 133
 134         el = get_refcount_el(refcount, ea_key, 1);
 135         if (!el)
 136                 return EXT2_ET_NO_MEMORY;
 137         el->ea_value++;
 138
 139         if (ret)
 140                 *ret = el->ea_value;
 141         return 0;
 142 }
 143
 144 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, ea_key_t ea_key,
 145                                 ea_value_t *ret)
 146 {
 147         struct ea_refcount_el   *el;
 148
 149         el = get_refcount_el(refcount, ea_key, 0);
 150         if (!el)
 151                 return EXT2_ET_INVALID_ARGUMENT;
 152
 153         el->ea_value--;
 154
 155         if (ret)
 156                 *ret = el->ea_value;
 157
 158         if (el->ea_value == 0) {
 159                 ext2fs_rb_erase(&el->node, &refcount->root);
 160                 ext2fs_free_mem(&el);
 161         }
 162         return 0;
 163 }
 164
 165 errcode_t ea_refcount_store(ext2_refcount_t refcount, ea_key_t ea_key,
 166                             ea_value_t ea_value)
 167 {
 168         struct ea_refcount_el   *el;
 169
 170         /*
 171          * Get the refcount element
 172          */
 173         el = get_refcount_el(refcount, ea_key, ea_value ? 1 : 0);
 174         if (!el)
 175                 return ea_value ? EXT2_ET_NO_MEMORY : 0;
 176         el->ea_value = ea_value;
 177         if (el->ea_value == 0) {
 178                 ext2fs_rb_erase(&el->node, &refcount->root);
 179                 ext2fs_free_mem(&el);
 180         }
 181         return 0;
 182 }
 183
 184 void ea_refcount_intr_begin(ext2_refcount_t refcount)
 185 {
 186         refcount->cursor = 0;
 187 }
 188
 189 ea_key_t ea_refcount_intr_next(ext2_refcount_t refcount,
 190                                 ea_value_t *ret)
 191 {
 192         struct ea_refcount_el   *el;
 193         struct rb_node          *node = refcount->cursor;
 194
 195         if (node == NULL)
 196                 node = ext2fs_rb_first(&refcount->root);
 197         else
 198                 node = ext2fs_rb_next(node);
 199
 200         if (node) {
 201                 refcount->cursor = node;
 202                 el = ext2fs_rb_entry(node, struct ea_refcount_el, node);
 203                 if (ret)
 204                         *ret = el->ea_value;
 205                 return el->ea_key;
 206         }
 207
 208         return 0;
 209 }
 210
 211
 212 #ifdef TEST_PROGRAM
 213
 214 errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out)
 215 {
 216         struct ea_refcount_el   *el;
 217         struct rb_node          *node;
 218         ea_key_t                prev;
 219         int                     prev_valid = 0;
 220         const char *bad = "bad refcount";
 221
 222         for (node = ext2fs_rb_first(&refcount->root); node != NULL;
 223              node = ext2fs_rb_next(node)) {
 224                 el = ext2fs_rb_entry(node, struct ea_refcount_el, node);
 225                 if (prev_valid && prev >= el->ea_key) {
 226                         fprintf(out,
 227                                 "%s: prev.ea_key=%llu, curr.ea_key=%llu\n",
 228                                 bad,
 229                                 (unsigned long long) prev,
 230                                 (unsigned long long) el->ea_key);
 231                         return EXT2_ET_INVALID_ARGUMENT;
 232                 }
 233                 prev = el->ea_key;
 234                 prev_valid = 1;
 235         }
 236
 237         return 0;
 238 }
 239
 240 #define BCODE_END       0
 241 #define BCODE_CREATE    1
 242 #define BCODE_FREE      2
 243 #define BCODE_STORE     3
 244 #define BCODE_INCR      4
 245 #define BCODE_DECR      5
 246 #define BCODE_FETCH     6
 247 #define BCODE_VALIDATE  7
 248 #define BCODE_LIST      8
 249
 250 int bcode_program[] = {
 251         BCODE_CREATE,
 252         BCODE_STORE, 3, 3,
 253         BCODE_STORE, 4, 4,
 254         BCODE_STORE, 1, 1,
 255         BCODE_STORE, 8, 8,
 256         BCODE_STORE, 2, 2,
 257         BCODE_STORE, 4, 0,
 258         BCODE_STORE, 2, 0,
 259         BCODE_STORE, 6, 6,
 260         BCODE_VALIDATE,
 261         BCODE_STORE, 4, 4,
 262         BCODE_STORE, 2, 2,
 263         BCODE_FETCH, 1,
 264         BCODE_FETCH, 2,
 265         BCODE_INCR, 3,
 266         BCODE_INCR, 3,
 267         BCODE_DECR, 4,
 268         BCODE_STORE, 4, 4,
 269         BCODE_VALIDATE,
 270         BCODE_STORE, 20, 20,
 271         BCODE_STORE, 40, 40,
 272         BCODE_STORE, 30, 30,
 273         BCODE_STORE, 10, 10,
 274         BCODE_DECR, 30,
 275         BCODE_FETCH, 30,
 276         BCODE_DECR, 2,
 277         BCODE_DECR, 2,
 278         BCODE_LIST,
 279         BCODE_VALIDATE,
 280         BCODE_FREE,
 281         BCODE_END
 282 };
 283
 284 int main(int argc, char **argv)
 285 {
 286         int     i = 0;
 287         ext2_refcount_t refcount;
 288         ea_key_t        ea_key;
 289         ea_value_t      arg;
 290         errcode_t       retval;
 291
 292         while (1) {
 293                 switch (bcode_program[i++]) {
 294                 case BCODE_END:
 295                         exit(0);
 296                 case BCODE_CREATE:
 297                         retval = ea_refcount_create(&refcount);
 298                         if (retval) {
 299                                 com_err("ea_refcount_create", retval,
 300                                         "while creating refcount");
 301                                 exit(1);
 302                         } else
 303                                 printf("Creating refcount\n");
 304                         break;
 305                 case BCODE_FREE:
 306                         ea_refcount_free(refcount);
 307                         refcount = 0;
 308                         printf("Freeing refcount\n");
 309                         break;
 310                 case BCODE_STORE:
 311                         ea_key = (size_t) bcode_program[i++];
 312                         arg = bcode_program[i++];
 313                         printf("Storing ea_key %llu with value %llu\n",
 314                                (unsigned long long) ea_key,
 315                                (unsigned long long) arg);
 316                         retval = ea_refcount_store(refcount, ea_key, arg);
 317                         if (retval)
 318                                 com_err("ea_refcount_store", retval,
 319                                         "while storing ea_key %llu",
 320                                         (unsigned long long) ea_key);
 321                         break;
 322                 case BCODE_FETCH:
 323                         ea_key = (size_t) bcode_program[i++];
 324                         retval = ea_refcount_fetch(refcount, ea_key, &arg);
 325                         if (retval)
 326                                 com_err("ea_refcount_fetch", retval,
 327                                         "while fetching ea_key %llu",
 328                                         (unsigned long long) ea_key);
 329                         else
 330                                 printf("bcode_fetch(%llu) returns %llu\n",
 331                                        (unsigned long long) ea_key,
 332                                        (unsigned long long) arg);
 333                         break;
 334                 case BCODE_INCR:
 335                         ea_key = (size_t) bcode_program[i++];
 336                         retval = ea_refcount_increment(refcount, ea_key, &arg);
 337                         if (retval)
 338                                 com_err("ea_refcount_increment", retval,
 339                                         "while incrementing ea_key %llu",
 340                                         (unsigned long long) ea_key);
 341                         else
 342                                 printf("bcode_increment(%llu) returns %llu\n",
 343                                        (unsigned long long) ea_key,
 344                                        (unsigned long long) arg);
 345                         break;
 346                 case BCODE_DECR:
 347                         ea_key = (size_t) bcode_program[i++];
 348                         retval = ea_refcount_decrement(refcount, ea_key, &arg);
 349                         if (retval)
 350                                 com_err("ea_refcount_decrement", retval,
 351                                         "while decrementing ea_key %llu",
 352                                         (unsigned long long) ea_key);
 353                         else
 354                                 printf("bcode_decrement(%llu) returns %llu\n",
 355                                        (unsigned long long) ea_key,
 356                                        (unsigned long long) arg);
 357                         break;
 358                 case BCODE_VALIDATE:
 359                         retval = ea_refcount_validate(refcount, stderr);
 360                         if (retval)
 361                                 com_err("ea_refcount_validate", retval,
 362                                         "while validating");
 363                         else
 364                                 printf("Refcount validation OK.\n");
 365                         break;
 366                 case BCODE_LIST:
 367                         ea_refcount_intr_begin(refcount);
 368                         while (1) {
 369                                 ea_key = ea_refcount_intr_next(refcount, &arg);
 370                                 if (!ea_key)
 371                                         break;
 372                                 printf("\tea_key=%llu, count=%llu\n",
 373                                        (unsigned long long) ea_key,
 374                                        (unsigned long long) arg);
 375                         }
 376                         break;
 377                 }
 378
 379         }
 380 }
 381
 382 #endif