fs/reiser4/seal.c

   1 /* Copyright 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2 /* Seals implementation. */
   3 /* Seals are "weak" tree pointers. They are analogous to tree coords in
   4    allowing to bypass tree traversal. But normal usage of coords implies that
   5    node pointed to by coord is locked, whereas seals don't keep a lock (or
   6    even a reference) to znode. In stead, each znode contains a version number,
   7    increased on each znode modification. This version number is copied into a
   8    seal when seal is created. Later, one can "validate" seal by calling
   9    reiser4_seal_validate(). If znode is in cache and its version number is
  10    still the same, seal is "pristine" and coord associated with it can be
  11    re-used immediately.
  12
  13    If, on the other hand, znode is out of cache, or it is obviously different
  14    one from the znode seal was initially attached to (for example, it is on
  15    the different level, or is being removed from the tree), seal is
  16    irreparably invalid ("burned") and tree traversal has to be repeated.
  17
  18    Otherwise, there is some hope, that while znode was modified (and seal was
  19    "broken" as a result), key attached to the seal is still in the node. This
  20    is checked by first comparing this key with delimiting keys of node and, if
  21    key is ok, doing intra-node lookup.
  22
  23    Znode version is maintained in the following way:
  24
  25    there is reiser4_tree.znode_epoch counter. Whenever new znode is created,
  26    znode_epoch is incremented and its new value is stored in ->version field
  27    of new znode. Whenever znode is dirtied (which means it was probably
  28    modified), znode_epoch is also incremented and its new value is stored in
  29    znode->version. This is done so, because just incrementing znode->version
  30    on each update is not enough: it may so happen, that znode get deleted, new
  31    znode is allocated for the same disk block and gets the same version
  32    counter, tricking seal code into false positive.
  33 */
  34
  35 #include "forward.h"
  36 #include "debug.h"
  37 #include "key.h"
  38 #include "coord.h"
  39 #include "seal.h"
  40 #include "plugin/item/item.h"
  41 #include "plugin/node/node.h"
  42 #include "jnode.h"
  43 #include "znode.h"
  44 #include "super.h"
  45
  46 static znode *seal_node(const seal_t *seal);
  47 static int seal_matches(const seal_t *seal, znode * node);
  48
  49 /* initialise seal. This can be called several times on the same seal. @coord
  50    and @key can be NULL.  */
  51 void reiser4_seal_init(seal_t *seal /* seal to initialise */ ,
  52                        const coord_t *coord /* coord @seal will be
  53                                               * attached to */ ,
  54                        const reiser4_key * key UNUSED_ARG /* key @seal will be
  55                                                            * attached to */ )
  56 {
  57         assert("nikita-1886", seal != NULL);
  58         memset(seal, 0, sizeof *seal);
  59         if (coord != NULL) {
  60                 znode *node;
  61
  62                 node = coord->node;
  63                 assert("nikita-1987", node != NULL);
  64                 spin_lock_znode(node);
  65                 seal->version = node->version;
  66                 assert("nikita-1988", seal->version != 0);
  67                 seal->block = *znode_get_block(node);
  68 #if REISER4_DEBUG
  69                 seal->coord1 = *coord;
  70                 if (key != NULL)
  71                         seal->key = *key;
  72 #endif
  73                 spin_unlock_znode(node);
  74         }
  75 }
  76
  77 /* finish with seal */
  78 void reiser4_seal_done(seal_t *seal/* seal to clear */)
  79 {
  80         assert("nikita-1887", seal != NULL);
  81         seal->version = 0;
  82 }
  83
  84 /* true if seal was initialised */
  85 int reiser4_seal_is_set(const seal_t *seal/* seal to query */)
  86 {
  87         assert("nikita-1890", seal != NULL);
  88         return seal->version != 0;
  89 }
  90
  91 #if REISER4_DEBUG
  92 /* helper function for reiser4_seal_validate(). It checks that item at @coord
  93  * has expected key. This is to detect cases where node was modified but wasn't
  94  * marked dirty. */
  95 static inline int check_seal_match(const coord_t *coord /* coord to check */ ,
  96                                    const reiser4_key * k/* expected key */)
  97 {
  98         reiser4_key ukey;
  99
 100         return (coord->between != AT_UNIT) ||
 101             /* FIXME-VS: we only can compare keys for items whose units
 102                represent exactly one key */
 103             ((coord_is_existing_unit(coord))
 104              && (item_is_extent(coord)
 105                  || keyeq(k, unit_key_by_coord(coord, &ukey))))
 106             || ((coord_is_existing_unit(coord)) && (item_is_ctail(coord))
 107                 && keyge(k, unit_key_by_coord(coord, &ukey)));
 108 }
 109 #endif
 110
 111 /* this is used by reiser4_seal_validate. It accepts return value of
 112  * longterm_lock_znode and returns 1 if it can be interpreted as seal
 113  * validation failure. For instance, when longterm_lock_znode returns -EINVAL,
 114  * reiser4_seal_validate returns -E_REPEAT and caller will call tre search.
 115  * We cannot do this in longterm_lock_znode(), because sometimes we want to
 116  * distinguish between -EINVAL and -E_REPEAT. */
 117 static int should_repeat(int return_code)
 118 {
 119         return return_code == -EINVAL;
 120 }
 121
 122 /* (re-)validate seal.
 123
 124    Checks whether seal is pristine, and try to revalidate it if possible.
 125
 126    If seal was burned, or broken irreparably, return -E_REPEAT.
 127
 128    NOTE-NIKITA currently reiser4_seal_validate() returns -E_REPEAT if key we are
 129    looking for is in range of keys covered by the sealed node, but item wasn't
 130    found by node ->lookup() method. Alternative is to return -ENOENT in this
 131    case, but this would complicate callers logic.
 132
 133 */
 134 int reiser4_seal_validate(seal_t *seal /* seal to validate */,
 135                           coord_t *coord /* coord to validate against */,
 136                           const reiser4_key * key /* key to validate against */,
 137                           lock_handle * lh /* resulting lock handle */,
 138                           znode_lock_mode mode /* lock node */,
 139                           znode_lock_request request/* locking priority */)
 140 {
 141         znode *node;
 142         int result;
 143
 144         assert("nikita-1889", seal != NULL);
 145         assert("nikita-1881", reiser4_seal_is_set(seal));
 146         assert("nikita-1882", key != NULL);
 147         assert("nikita-1883", coord != NULL);
 148         assert("nikita-1884", lh != NULL);
 149         assert("nikita-1885", keyeq(&seal->key, key));
 150         assert("nikita-1989", coords_equal(&seal->coord1, coord));
 151
 152         /* obtain znode by block number */
 153         node = seal_node(seal);
 154         if (node != NULL) {
 155                 /* znode was in cache, lock it */
 156                 result = longterm_lock_znode(lh, node, mode, request);
 157                 zput(node);
 158                 if (result == 0) {
 159                         if (seal_matches(seal, node)) {
 160                                 /* if seal version and znode version
 161                                    coincide */
 162                                 ON_DEBUG(coord_update_v(coord));
 163                                 assert("nikita-1990",
 164                                        node == seal->coord1.node);
 165                                 assert("nikita-1898",
 166                                        WITH_DATA_RET(coord->node, 1,
 167                                                      check_seal_match(coord,
 168                                                                       key)));
 169                         } else
 170                                 result = RETERR(-E_REPEAT);
 171                 }
 172                 if (result != 0) {
 173                         if (should_repeat(result))
 174                                 result = RETERR(-E_REPEAT);
 175                         /* unlock node on failure */
 176                         done_lh(lh);
 177                 }
 178         } else {
 179                 /* znode wasn't in cache */
 180                 result = RETERR(-E_REPEAT);
 181         }
 182         return result;
 183 }
 184
 185 /* helpers functions */
 186
 187 /* obtain reference to znode seal points to, if in cache */
 188 static znode *seal_node(const seal_t *seal/* seal to query */)
 189 {
 190         assert("nikita-1891", seal != NULL);
 191         return zlook(current_tree, &seal->block);
 192 }
 193
 194 /* true if @seal version and @node version coincide */
 195 static int seal_matches(const seal_t *seal /* seal to check */ ,
 196                         znode * node/* node to check */)
 197 {
 198         int result;
 199
 200         assert("nikita-1991", seal != NULL);
 201         assert("nikita-1993", node != NULL);
 202
 203         spin_lock_znode(node);
 204         result = (seal->version == node->version);
 205         spin_unlock_znode(node);
 206         return result;
 207 }
 208
 209 /* Make Linus happy.
 210    Local variables:
 211    c-indentation-style: "K&R"
 212    mode-name: "LC"
 213    c-basic-offset: 8
 214    tab-width: 8
 215    fill-column: 120
 216    scroll-step: 1
 217    End:
 218 */