fs/reiser4/plugin/item/internal.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2
   3 /* Implementation of internal-item plugin methods. */
   4
   5 #include "../../forward.h"
   6 #include "../../debug.h"
   7 #include "../../dformat.h"
   8 #include "../../key.h"
   9 #include "../../coord.h"
  10 #include "internal.h"
  11 #include "item.h"
  12 #include "../node/node.h"
  13 #include "../plugin.h"
  14 #include "../../jnode.h"
  15 #include "../../znode.h"
  16 #include "../../tree_walk.h"
  17 #include "../../tree_mod.h"
  18 #include "../../tree.h"
  19 #include "../../super.h"
  20 #include "../../block_alloc.h"
  21
  22 /* see internal.h for explanation */
  23
  24 /* plugin->u.item.b.mergeable */
  25 int mergeable_internal(const coord_t * p1 UNUSED_ARG /* first item */ ,
  26                        const coord_t * p2 UNUSED_ARG /* second item */ )
  27 {
  28         /* internal items are not mergeable */
  29         return 0;
  30 }
  31
  32 /* ->lookup() method for internal items */
  33 lookup_result lookup_internal(const reiser4_key * key /* key to look up */ ,
  34                               lookup_bias bias UNUSED_ARG /* lookup bias */ ,
  35                               coord_t * coord /* coord of item */ )
  36 {
  37         reiser4_key ukey;
  38
  39         switch (keycmp(unit_key_by_coord(coord, &ukey), key)) {
  40         default:
  41                 impossible("", "keycmp()?!");
  42         case LESS_THAN:
  43                 /* FIXME-VS: AFTER_ITEM used to be here. But with new coord
  44                    item plugin can not be taken using coord set this way */
  45                 assert("vs-681", coord->unit_pos == 0);
  46                 coord->between = AFTER_UNIT;
  47         case EQUAL_TO:
  48                 return CBK_COORD_FOUND;
  49         case GREATER_THAN:
  50                 return CBK_COORD_NOTFOUND;
  51         }
  52 }
  53
  54 /* return body of internal item at @coord */
  55 static internal_item_layout *internal_at(const coord_t * coord  /* coord of
  56                                                                  * item */ )
  57 {
  58         assert("nikita-607", coord != NULL);
  59         assert("nikita-1650",
  60                item_plugin_by_coord(coord) ==
  61                item_plugin_by_id(NODE_POINTER_ID));
  62         return (internal_item_layout *) item_body_by_coord(coord);
  63 }
  64
  65 void reiser4_update_internal(const coord_t * coord,
  66                              const reiser4_block_nr * blocknr)
  67 {
  68         internal_item_layout *item = internal_at(coord);
  69         assert("nikita-2959", reiser4_blocknr_is_sane(blocknr));
  70
  71         put_unaligned(cpu_to_le64(*blocknr), &item->pointer);
  72 }
  73
  74 /* return child block number stored in the internal item at @coord */
  75 static reiser4_block_nr pointer_at(const coord_t * coord /* coord of item */ )
  76 {
  77         assert("nikita-608", coord != NULL);
  78         return le64_to_cpu(get_unaligned(&internal_at(coord)->pointer));
  79 }
  80
  81 /* get znode pointed to by internal @item */
  82 static znode *znode_at(const coord_t * item /* coord of item */ ,
  83                        znode * parent /* parent node */ )
  84 {
  85         return child_znode(item, parent, 1, 0);
  86 }
  87
  88 /* store pointer from internal item into "block". Implementation of
  89     ->down_link() method */
  90 void down_link_internal(const coord_t * coord /* coord of item */ ,
  91                         const reiser4_key * key UNUSED_ARG      /* key to get
  92                                                                  * pointer for */ ,
  93                         reiser4_block_nr * block /* resulting block number */ )
  94 {
  95         ON_DEBUG(reiser4_key item_key);
  96
  97         assert("nikita-609", coord != NULL);
  98         assert("nikita-611", block != NULL);
  99         assert("nikita-612", (key == NULL) ||
 100                /* twig horrors */
 101                (znode_get_level(coord->node) == TWIG_LEVEL)
 102                || keyle(item_key_by_coord(coord, &item_key), key));
 103
 104         *block = pointer_at(coord);
 105         assert("nikita-2960", reiser4_blocknr_is_sane(block));
 106 }
 107
 108 /* Get the child's block number, or 0 if the block is unallocated. */
 109 int
 110 utmost_child_real_block_internal(const coord_t * coord, sideof side UNUSED_ARG,
 111                                  reiser4_block_nr * block)
 112 {
 113         assert("jmacd-2059", coord != NULL);
 114
 115         *block = pointer_at(coord);
 116         assert("nikita-2961", reiser4_blocknr_is_sane(block));
 117
 118         if (reiser4_blocknr_is_fake(block)) {
 119                 *block = 0;
 120         }
 121
 122         return 0;
 123 }
 124
 125 /* Return the child. */
 126 int
 127 utmost_child_internal(const coord_t * coord, sideof side UNUSED_ARG,
 128                       jnode ** childp)
 129 {
 130         reiser4_block_nr block = pointer_at(coord);
 131         znode *child;
 132
 133         assert("jmacd-2059", childp != NULL);
 134         assert("nikita-2962", reiser4_blocknr_is_sane(&block));
 135
 136         child = zlook(znode_get_tree(coord->node), &block);
 137
 138         if (IS_ERR(child)) {
 139                 return PTR_ERR(child);
 140         }
 141
 142         *childp = ZJNODE(child);
 143
 144         return 0;
 145 }
 146
 147 #if REISER4_DEBUG
 148
 149 static void check_link(znode * left, znode * right)
 150 {
 151         znode *scan;
 152
 153         for (scan = left; scan != right; scan = scan->right) {
 154                 if (ZF_ISSET(scan, JNODE_RIP))
 155                         break;
 156                 if (znode_is_right_connected(scan) && scan->right != NULL) {
 157                         if (ZF_ISSET(scan->right, JNODE_RIP))
 158                                 break;
 159                         assert("nikita-3285",
 160                                znode_is_left_connected(scan->right));
 161                         assert("nikita-3265",
 162                                ergo(scan != left,
 163                                     ZF_ISSET(scan, JNODE_HEARD_BANSHEE)));
 164                         assert("nikita-3284", scan->right->left == scan);
 165                 } else
 166                         break;
 167         }
 168 }
 169
 170 int check__internal(const coord_t * coord, const char **error)
 171 {
 172         reiser4_block_nr blk;
 173         znode *child;
 174         coord_t cpy;
 175
 176         blk = pointer_at(coord);
 177         if (!reiser4_blocknr_is_sane(&blk)) {
 178                 *error = "Invalid pointer";
 179                 return -1;
 180         }
 181         coord_dup(&cpy, coord);
 182         child = znode_at(&cpy, cpy.node);
 183         if (child != NULL) {
 184                 znode *left_child;
 185                 znode *right_child;
 186
 187                 left_child = right_child = NULL;
 188
 189                 assert("nikita-3256", znode_invariant(child));
 190                 if (coord_prev_item(&cpy) == 0 && item_is_internal(&cpy)) {
 191                         left_child = znode_at(&cpy, cpy.node);
 192                         if (left_child != NULL) {
 193                                 read_lock_tree(znode_get_tree(child));
 194                                 check_link(left_child, child);
 195                                 read_unlock_tree(znode_get_tree(child));
 196                                 zput(left_child);
 197                         }
 198                 }
 199                 coord_dup(&cpy, coord);
 200                 if (coord_next_item(&cpy) == 0 && item_is_internal(&cpy)) {
 201                         right_child = znode_at(&cpy, cpy.node);
 202                         if (right_child != NULL) {
 203                                 read_lock_tree(znode_get_tree(child));
 204                                 check_link(child, right_child);
 205                                 read_unlock_tree(znode_get_tree(child));
 206                                 zput(right_child);
 207                         }
 208                 }
 209                 zput(child);
 210         }
 211         return 0;
 212 }
 213
 214 #endif  /*  REISER4_DEBUG  */
 215
 216 /* return true only if this item really points to "block" */
 217 /* Audited by: green(2002.06.14) */
 218 int has_pointer_to_internal(const coord_t * coord /* coord of item */ ,
 219                             const reiser4_block_nr * block      /* block number to
 220                                                                  * check */ )
 221 {
 222         assert("nikita-613", coord != NULL);
 223         assert("nikita-614", block != NULL);
 224
 225         return pointer_at(coord) == *block;
 226 }
 227
 228 /* hook called by ->create_item() method of node plugin after new internal
 229    item was just created.
 230
 231    This is point where pointer to new node is inserted into tree. Initialize
 232    parent pointer in child znode, insert child into sibling list and slum.
 233
 234 */
 235 int create_hook_internal(const coord_t * item /* coord of item */ ,
 236                          void *arg /* child's left neighbor, if any */ )
 237 {
 238         znode *child;
 239         __u64 child_ptr;
 240
 241         assert("nikita-1252", item != NULL);
 242         assert("nikita-1253", item->node != NULL);
 243         assert("nikita-1181", znode_get_level(item->node) > LEAF_LEVEL);
 244         assert("nikita-1450", item->unit_pos == 0);
 245
 246         /*
 247          * preparing to item insertion build_child_ptr_data sets pointer to
 248          * data to be inserted to jnode's blocknr which is in cpu byte
 249          * order. Node's create_item simply copied those data. As result we
 250          * have child pointer in cpu's byte order. Convert content of internal
 251          * item to little endian byte order.
 252          */
 253         child_ptr = get_unaligned((__u64 *)item_body_by_coord(item));
 254         reiser4_update_internal(item, &child_ptr);
 255
 256         child = znode_at(item, item->node);
 257         if (child != NULL && !IS_ERR(child)) {
 258                 znode *left;
 259                 int result = 0;
 260                 reiser4_tree *tree;
 261
 262                 left = arg;
 263                 tree = znode_get_tree(item->node);
 264                 write_lock_tree(tree);
 265                 write_lock_dk(tree);
 266                 assert("nikita-1400", (child->in_parent.node == NULL)
 267                        || (znode_above_root(child->in_parent.node)));
 268                 ++item->node->c_count;
 269                 coord_to_parent_coord(item, &child->in_parent);
 270                 sibling_list_insert_nolock(child, left);
 271
 272                 assert("nikita-3297", ZF_ISSET(child, JNODE_ORPHAN));
 273                 ZF_CLR(child, JNODE_ORPHAN);
 274
 275                 if ((left != NULL) && !keyeq(znode_get_rd_key(left),
 276                                              znode_get_rd_key(child))) {
 277                         znode_set_rd_key(child, znode_get_rd_key(left));
 278                 }
 279                 write_unlock_dk(tree);
 280                 write_unlock_tree(tree);
 281                 zput(child);
 282                 return result;
 283         } else {
 284                 if (child == NULL)
 285                         child = ERR_PTR(-EIO);
 286                 return PTR_ERR(child);
 287         }
 288 }
 289
 290 /* hook called by ->cut_and_kill() method of node plugin just before internal
 291    item is removed.
 292
 293    This is point where empty node is removed from the tree. Clear parent
 294    pointer in child, and mark node for pending deletion.
 295
 296    Node will be actually deleted later and in several installations:
 297
 298     . when last lock on this node will be released, node will be removed from
 299     the sibling list and its lock will be invalidated
 300
 301     . when last reference to this node will be dropped, bitmap will be updated
 302     and node will be actually removed from the memory.
 303
 304 */
 305 int kill_hook_internal(const coord_t * item /* coord of item */ ,
 306                        pos_in_node_t from UNUSED_ARG /* start unit */ ,
 307                        pos_in_node_t count UNUSED_ARG /* stop unit */ ,
 308                        struct carry_kill_data *p UNUSED_ARG)
 309 {
 310         znode *child;
 311
 312         assert("nikita-1222", item != NULL);
 313         assert("nikita-1224", from == 0);
 314         assert("nikita-1225", count == 1);
 315
 316         child = znode_at(item, item->node);
 317         if (IS_ERR(child))
 318                 return PTR_ERR(child);
 319         else if (node_is_empty(child)) {
 320                 reiser4_tree *tree;
 321
 322                 assert("nikita-1397", znode_is_write_locked(child));
 323                 assert("nikita-1398", child->c_count == 0);
 324                 assert("nikita-2546", ZF_ISSET(child, JNODE_HEARD_BANSHEE));
 325
 326                 tree = znode_get_tree(item->node);
 327                 write_lock_tree(tree);
 328                 init_parent_coord(&child->in_parent, NULL);
 329                 --item->node->c_count;
 330                 write_unlock_tree(tree);
 331                 zput(child);
 332                 return 0;
 333         } else {
 334                 warning("nikita-1223",
 335                         "Cowardly refuse to remove link to non-empty node");
 336                 zput(child);
 337                 return RETERR(-EIO);
 338         }
 339 }
 340
 341 /* hook called by ->shift() node plugin method when iternal item was just
 342    moved from one node to another.
 343
 344    Update parent pointer in child and c_counts in old and new parent
 345
 346 */
 347 int shift_hook_internal(const coord_t * item /* coord of item */ ,
 348                         unsigned from UNUSED_ARG /* start unit */ ,
 349                         unsigned count UNUSED_ARG /* stop unit */ ,
 350                         znode * old_node /* old parent */ )
 351 {
 352         znode *child;
 353         znode *new_node;
 354         reiser4_tree *tree;
 355
 356         assert("nikita-1276", item != NULL);
 357         assert("nikita-1277", from == 0);
 358         assert("nikita-1278", count == 1);
 359         assert("nikita-1451", item->unit_pos == 0);
 360
 361         new_node = item->node;
 362         assert("nikita-2132", new_node != old_node);
 363         tree = znode_get_tree(item->node);
 364         child = child_znode(item, old_node, 1, 0);
 365         if (child == NULL)
 366                 return 0;
 367         if (!IS_ERR(child)) {
 368                 write_lock_tree(tree);
 369                 ++new_node->c_count;
 370                 assert("nikita-1395", znode_parent(child) == old_node);
 371                 assert("nikita-1396", old_node->c_count > 0);
 372                 coord_to_parent_coord(item, &child->in_parent);
 373                 assert("nikita-1781", znode_parent(child) == new_node);
 374                 assert("nikita-1782",
 375                        check_tree_pointer(item, child) == NS_FOUND);
 376                 --old_node->c_count;
 377                 write_unlock_tree(tree);
 378                 zput(child);
 379                 return 0;
 380         } else
 381                 return PTR_ERR(child);
 382 }
 383
 384 /* plugin->u.item.b.max_key_inside - not defined */
 385
 386 /* plugin->u.item.b.nr_units - item.c:single_unit */
 387
 388 /* Make Linus happy.
 389    Local variables:
 390    c-indentation-style: "K&R"
 391    mode-name: "LC"
 392    c-basic-offset: 8
 393    tab-width: 8
 394    fill-column: 120
 395    End:
 396 */