fs/reiser4/tap.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2  * reiser4/README */
   3
   4 /*
   5    Tree Access Pointer (tap).
   6
   7    tap is data structure combining coord and lock handle (mostly). It is
   8    useful when one has to scan tree nodes (for example, in readdir, or flush),
   9    for tap functions allow to move tap in either direction transparently
  10    crossing unit/item/node borders.
  11
  12    Tap doesn't provide automatic synchronization of its fields as it is
  13    supposed to be per-thread object.
  14 */
  15
  16 #include "forward.h"
  17 #include "debug.h"
  18 #include "coord.h"
  19 #include "tree.h"
  20 #include "context.h"
  21 #include "tap.h"
  22 #include "znode.h"
  23 #include "tree_walk.h"
  24
  25 #if REISER4_DEBUG
  26 static int tap_invariant(const tap_t * tap);
  27 static void tap_check(const tap_t * tap);
  28 #else
  29 #define tap_check(tap) noop
  30 #endif
  31
  32 /** load node tap is pointing to, if not loaded already */
  33 int reiser4_tap_load(tap_t * tap)
  34 {
  35         tap_check(tap);
  36         if (tap->loaded == 0) {
  37                 int result;
  38
  39                 result = zload_ra(tap->coord->node, &tap->ra_info);
  40                 if (result != 0)
  41                         return result;
  42                 coord_clear_iplug(tap->coord);
  43         }
  44         ++tap->loaded;
  45         tap_check(tap);
  46         return 0;
  47 }
  48
  49 /** release node tap is pointing to. Dual to tap_load() */
  50 void reiser4_tap_relse(tap_t * tap)
  51 {
  52         tap_check(tap);
  53         if (tap->loaded > 0) {
  54                 --tap->loaded;
  55                 if (tap->loaded == 0) {
  56                         zrelse(tap->coord->node);
  57                 }
  58         }
  59         tap_check(tap);
  60 }
  61
  62 /**
  63  * init tap to consist of @coord and @lh. Locks on nodes will be acquired with
  64  * @mode
  65  */
  66 void reiser4_tap_init(tap_t * tap, coord_t * coord, lock_handle * lh,
  67                       znode_lock_mode mode)
  68 {
  69         tap->coord = coord;
  70         tap->lh = lh;
  71         tap->mode = mode;
  72         tap->loaded = 0;
  73         INIT_LIST_HEAD(&tap->linkage);
  74         reiser4_init_ra_info(&tap->ra_info);
  75 }
  76
  77 /** add @tap to the per-thread list of all taps */
  78 void reiser4_tap_monitor(tap_t * tap)
  79 {
  80         assert("nikita-2623", tap != NULL);
  81         tap_check(tap);
  82         list_add(&tap->linkage, reiser4_taps_list());
  83         tap_check(tap);
  84 }
  85
  86 /* duplicate @src into @dst. Copy lock handle. @dst is not initially
  87  * loaded. */
  88 void reiser4_tap_copy(tap_t * dst, tap_t * src)
  89 {
  90         assert("nikita-3193", src != NULL);
  91         assert("nikita-3194", dst != NULL);
  92
  93         *dst->coord = *src->coord;
  94         if (src->lh->node)
  95                 copy_lh(dst->lh, src->lh);
  96         dst->mode = src->mode;
  97         dst->loaded = 0;
  98         INIT_LIST_HEAD(&dst->linkage);
  99         dst->ra_info = src->ra_info;
 100 }
 101
 102 /** finish with @tap */
 103 void reiser4_tap_done(tap_t * tap)
 104 {
 105         assert("nikita-2565", tap != NULL);
 106         tap_check(tap);
 107         if (tap->loaded > 0)
 108                 zrelse(tap->coord->node);
 109         done_lh(tap->lh);
 110         tap->loaded = 0;
 111         list_del_init(&tap->linkage);
 112         tap->coord->node = NULL;
 113 }
 114
 115 /**
 116  * move @tap to the new node, locked with @target. Load @target, if @tap was
 117  * already loaded.
 118  */
 119 int reiser4_tap_move(tap_t * tap, lock_handle * target)
 120 {
 121         int result = 0;
 122
 123         assert("nikita-2567", tap != NULL);
 124         assert("nikita-2568", target != NULL);
 125         assert("nikita-2570", target->node != NULL);
 126         assert("nikita-2569", tap->coord->node == tap->lh->node);
 127
 128         tap_check(tap);
 129         if (tap->loaded > 0)
 130                 result = zload_ra(target->node, &tap->ra_info);
 131
 132         if (result == 0) {
 133                 if (tap->loaded > 0)
 134                         zrelse(tap->coord->node);
 135                 done_lh(tap->lh);
 136                 copy_lh(tap->lh, target);
 137                 tap->coord->node = target->node;
 138                 coord_clear_iplug(tap->coord);
 139         }
 140         tap_check(tap);
 141         return result;
 142 }
 143
 144 /**
 145  * move @tap to @target. Acquire lock on @target, if @tap was already
 146  * loaded.
 147  */
 148 static int tap_to(tap_t * tap, znode * target)
 149 {
 150         int result;
 151
 152         assert("nikita-2624", tap != NULL);
 153         assert("nikita-2625", target != NULL);
 154
 155         tap_check(tap);
 156         result = 0;
 157         if (tap->coord->node != target) {
 158                 lock_handle here;
 159
 160                 init_lh(&here);
 161                 result = longterm_lock_znode(&here, target,
 162                                              tap->mode, ZNODE_LOCK_HIPRI);
 163                 if (result == 0) {
 164                         result = reiser4_tap_move(tap, &here);
 165                         done_lh(&here);
 166                 }
 167         }
 168         tap_check(tap);
 169         return result;
 170 }
 171
 172 /**
 173  * move @tap to given @target, loading and locking @target->node if
 174  * necessary
 175  */
 176 int tap_to_coord(tap_t * tap, coord_t * target)
 177 {
 178         int result;
 179
 180         tap_check(tap);
 181         result = tap_to(tap, target->node);
 182         if (result == 0)
 183                 coord_dup(tap->coord, target);
 184         tap_check(tap);
 185         return result;
 186 }
 187
 188 /** return list of all taps */
 189 struct list_head *reiser4_taps_list(void)
 190 {
 191         return &get_current_context()->taps;
 192 }
 193
 194 /** helper function for go_{next,prev}_{item,unit,node}() */
 195 int go_dir_el(tap_t * tap, sideof dir, int units_p)
 196 {
 197         coord_t dup;
 198         coord_t *coord;
 199         int result;
 200
 201         int (*coord_dir) (coord_t *);
 202         int (*get_dir_neighbor) (lock_handle *, znode *, int, int);
 203         void (*coord_init) (coord_t *, const znode *);
 204         ON_DEBUG(int (*coord_check) (const coord_t *));
 205
 206         assert("nikita-2556", tap != NULL);
 207         assert("nikita-2557", tap->coord != NULL);
 208         assert("nikita-2558", tap->lh != NULL);
 209         assert("nikita-2559", tap->coord->node != NULL);
 210
 211         tap_check(tap);
 212         if (dir == LEFT_SIDE) {
 213                 coord_dir = units_p ? coord_prev_unit : coord_prev_item;
 214                 get_dir_neighbor = reiser4_get_left_neighbor;
 215                 coord_init = coord_init_last_unit;
 216         } else {
 217                 coord_dir = units_p ? coord_next_unit : coord_next_item;
 218                 get_dir_neighbor = reiser4_get_right_neighbor;
 219                 coord_init = coord_init_first_unit;
 220         }
 221         ON_DEBUG(coord_check =
 222                  units_p ? coord_is_existing_unit : coord_is_existing_item);
 223         assert("nikita-2560", coord_check(tap->coord));
 224
 225         coord = tap->coord;
 226         coord_dup(&dup, coord);
 227         if (coord_dir(&dup) != 0) {
 228                 do {
 229                         /* move to the left neighboring node */
 230                         lock_handle dup;
 231
 232                         init_lh(&dup);
 233                         result =
 234                             get_dir_neighbor(&dup, coord->node, (int)tap->mode,
 235                                              GN_CAN_USE_UPPER_LEVELS);
 236                         if (result == 0) {
 237                                 result = reiser4_tap_move(tap, &dup);
 238                                 if (result == 0)
 239                                         coord_init(tap->coord, dup.node);
 240                                 done_lh(&dup);
 241                         }
 242                         /* skip empty nodes */
 243                 } while ((result == 0) && node_is_empty(coord->node));
 244         } else {
 245                 result = 0;
 246                 coord_dup(coord, &dup);
 247         }
 248         assert("nikita-2564", ergo(!result, coord_check(tap->coord)));
 249         tap_check(tap);
 250         return result;
 251 }
 252
 253 /**
 254  * move @tap to the next unit, transparently crossing item and node
 255  * boundaries
 256  */
 257 int go_next_unit(tap_t * tap)
 258 {
 259         return go_dir_el(tap, RIGHT_SIDE, 1);
 260 }
 261
 262 /**
 263  * move @tap to the previous unit, transparently crossing item and node
 264  * boundaries
 265  */
 266 int go_prev_unit(tap_t * tap)
 267 {
 268         return go_dir_el(tap, LEFT_SIDE, 1);
 269 }
 270
 271 /**
 272  * @shift times apply @actor to the @tap. This is used to move @tap by
 273  * @shift units (or items, or nodes) in either direction.
 274  */
 275 static int rewind_to(tap_t * tap, go_actor_t actor, int shift)
 276 {
 277         int result;
 278
 279         assert("nikita-2555", shift >= 0);
 280         assert("nikita-2562", tap->coord->node == tap->lh->node);
 281
 282         tap_check(tap);
 283         result = reiser4_tap_load(tap);
 284         if (result != 0)
 285                 return result;
 286
 287         for (; shift > 0; --shift) {
 288                 result = actor(tap);
 289                 assert("nikita-2563", tap->coord->node == tap->lh->node);
 290                 if (result != 0)
 291                         break;
 292         }
 293         reiser4_tap_relse(tap);
 294         tap_check(tap);
 295         return result;
 296 }
 297
 298 /** move @tap @shift units rightward */
 299 int rewind_right(tap_t * tap, int shift)
 300 {
 301         return rewind_to(tap, go_next_unit, shift);
 302 }
 303
 304 /** move @tap @shift units leftward */
 305 int rewind_left(tap_t * tap, int shift)
 306 {
 307         return rewind_to(tap, go_prev_unit, shift);
 308 }
 309
 310 #if REISER4_DEBUG
 311 /** debugging function: print @tap content in human readable form */
 312 static void print_tap(const char *prefix, const tap_t * tap)
 313 {
 314         if (tap == NULL) {
 315                 printk("%s: null tap\n", prefix);
 316                 return;
 317         }
 318         printk("%s: loaded: %i, in-list: %i, node: %p, mode: %s\n", prefix,
 319                tap->loaded, (&tap->linkage == tap->linkage.next &&
 320                              &tap->linkage == tap->linkage.prev),
 321                tap->lh->node,
 322                lock_mode_name(tap->mode));
 323         print_coord("\tcoord", tap->coord, 0);
 324 }
 325
 326 /** check [tap-sane] invariant */
 327 static int tap_invariant(const tap_t * tap)
 328 {
 329         /* [tap-sane] invariant */
 330
 331         if (tap == NULL)
 332                 return 1;
 333         /* tap->mode is one of
 334          *
 335          * {ZNODE_NO_LOCK, ZNODE_READ_LOCK, ZNODE_WRITE_LOCK}, and
 336          */
 337         if (tap->mode != ZNODE_NO_LOCK &&
 338             tap->mode != ZNODE_READ_LOCK && tap->mode != ZNODE_WRITE_LOCK)
 339                 return 2;
 340         /* tap->coord != NULL, and */
 341         if (tap->coord == NULL)
 342                 return 3;
 343         /* tap->lh != NULL, and */
 344         if (tap->lh == NULL)
 345                 return 4;
 346         /* tap->loaded > 0 => znode_is_loaded(tap->coord->node), and */
 347         if (!ergo(tap->loaded, znode_is_loaded(tap->coord->node)))
 348                 return 5;
 349         /* tap->coord->node == tap->lh->node if tap->lh->node is not 0 */
 350         if (tap->lh->node != NULL && tap->coord->node != tap->lh->node)
 351                 return 6;
 352         return 0;
 353 }
 354
 355 /** debugging function: check internal @tap consistency */
 356 static void tap_check(const tap_t * tap)
 357 {
 358         int result;
 359
 360         result = tap_invariant(tap);
 361         if (result != 0) {
 362                 print_tap("broken", tap);
 363                 reiser4_panic("nikita-2831", "tap broken: %i\n", result);
 364         }
 365 }
 366 #endif
 367
 368 /* Make Linus happy.
 369    Local variables:
 370    c-indentation-style: "K&R"
 371    mode-name: "LC"
 372    c-basic-offset: 8
 373    tab-width: 8
 374    fill-column: 120
 375    scroll-step: 1
 376    End:
 377 */