fs/reiser4/plugin/item/extent_item_ops.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2
   3 #include "item.h"
   4 #include "../../inode.h"
   5 #include "../../tree_walk.h"    /* check_sibling_list() */
   6 #include "../../page_cache.h"
   7 #include "../../carry.h"
   8
   9 #include <linux/quotaops.h>
  10
  11 /* item_plugin->b.max_key_inside */
  12 reiser4_key *max_key_inside_extent(const coord_t * coord, reiser4_key * key)
  13 {
  14         item_key_by_coord(coord, key);
  15         set_key_offset(key, get_key_offset(reiser4_max_key()));
  16         return key;
  17 }
  18
  19 /* item_plugin->b.can_contain_key
  20    this checks whether @key of @data is matching to position set by @coord */
  21 int
  22 can_contain_key_extent(const coord_t * coord, const reiser4_key * key,
  23                        const reiser4_item_data * data)
  24 {
  25         reiser4_key item_key;
  26
  27         if (item_plugin_by_coord(coord) != data->iplug)
  28                 return 0;
  29
  30         item_key_by_coord(coord, &item_key);
  31         if (get_key_locality(key) != get_key_locality(&item_key) ||
  32             get_key_objectid(key) != get_key_objectid(&item_key) ||
  33             get_key_ordering(key) != get_key_ordering(&item_key))
  34                 return 0;
  35
  36         return 1;
  37 }
  38
  39 /* item_plugin->b.mergeable
  40    first item is of extent type */
  41 /* Audited by: green(2002.06.13) */
  42 int mergeable_extent(const coord_t * p1, const coord_t * p2)
  43 {
  44         reiser4_key key1, key2;
  45
  46         assert("vs-299", item_id_by_coord(p1) == EXTENT_POINTER_ID);
  47         /* FIXME-VS: Which is it? Assert or return 0 */
  48         if (item_id_by_coord(p2) != EXTENT_POINTER_ID) {
  49                 return 0;
  50         }
  51
  52         item_key_by_coord(p1, &key1);
  53         item_key_by_coord(p2, &key2);
  54         if (get_key_locality(&key1) != get_key_locality(&key2) ||
  55             get_key_objectid(&key1) != get_key_objectid(&key2) ||
  56             get_key_ordering(&key1) != get_key_ordering(&key2) ||
  57             get_key_type(&key1) != get_key_type(&key2))
  58                 return 0;
  59         if (get_key_offset(&key1) +
  60             reiser4_extent_size(p1, nr_units_extent(p1)) !=
  61             get_key_offset(&key2))
  62                 return 0;
  63         return 1;
  64 }
  65
  66 /* item_plugin->b.nr_units */
  67 pos_in_node_t nr_units_extent(const coord_t * coord)
  68 {
  69         /* length of extent item has to be multiple of extent size */
  70         assert("vs-1424",
  71                (item_length_by_coord(coord) % sizeof(reiser4_extent)) == 0);
  72         return item_length_by_coord(coord) / sizeof(reiser4_extent);
  73 }
  74
  75 /* item_plugin->b.lookup */
  76 lookup_result
  77 lookup_extent(const reiser4_key * key, lookup_bias bias UNUSED_ARG,
  78               coord_t * coord)
  79 {                               /* znode and item_pos are
  80                                    set to an extent item to
  81                                    look through */
  82         reiser4_key item_key;
  83         reiser4_block_nr lookuped, offset;
  84         unsigned i, nr_units;
  85         reiser4_extent *ext;
  86         unsigned blocksize;
  87         unsigned char blocksize_bits;
  88
  89         item_key_by_coord(coord, &item_key);
  90         offset = get_key_offset(&item_key);
  91
  92         /* key we are looking for must be greater than key of item @coord */
  93         assert("vs-414", keygt(key, &item_key));
  94
  95         assert("umka-99945",
  96                !keygt(key, max_key_inside_extent(coord, &item_key)));
  97
  98         ext = extent_item(coord);
  99         assert("vs-1350", (char *)ext == (zdata(coord->node) + coord->offset));
 100
 101         blocksize = current_blocksize;
 102         blocksize_bits = current_blocksize_bits;
 103
 104         /* offset we are looking for */
 105         lookuped = get_key_offset(key);
 106
 107         nr_units = nr_units_extent(coord);
 108         /* go through all extents until the one which address given offset */
 109         for (i = 0; i < nr_units; i++, ext++) {
 110                 offset += (extent_get_width(ext) << blocksize_bits);
 111                 if (offset > lookuped) {
 112                         /* desired byte is somewhere in this extent */
 113                         coord->unit_pos = i;
 114                         coord->between = AT_UNIT;
 115                         return CBK_COORD_FOUND;
 116                 }
 117         }
 118
 119         /* set coord after last unit */
 120         coord->unit_pos = nr_units - 1;
 121         coord->between = AFTER_UNIT;
 122         return CBK_COORD_FOUND;
 123 }
 124
 125 /* item_plugin->b.paste
 126    item @coord is set to has been appended with @data->length of free
 127    space. data->data contains data to be pasted into the item in position
 128    @coord->in_item.unit_pos. It must fit into that free space.
 129    @coord must be set between units.
 130 */
 131 int
 132 paste_extent(coord_t * coord, reiser4_item_data * data,
 133              carry_plugin_info * info UNUSED_ARG)
 134 {
 135         unsigned old_nr_units;
 136         reiser4_extent *ext;
 137         int item_length;
 138
 139         ext = extent_item(coord);
 140         item_length = item_length_by_coord(coord);
 141         old_nr_units = (item_length - data->length) / sizeof(reiser4_extent);
 142
 143         /* this is also used to copy extent into newly created item, so
 144            old_nr_units could be 0 */
 145         assert("vs-260", item_length >= data->length);
 146
 147         /* make sure that coord is set properly */
 148         assert("vs-35",
 149                ((!coord_is_existing_unit(coord))
 150                 || (!old_nr_units && !coord->unit_pos)));
 151
 152         /* first unit to be moved */
 153         switch (coord->between) {
 154         case AFTER_UNIT:
 155                 coord->unit_pos++;
 156         case BEFORE_UNIT:
 157                 coord->between = AT_UNIT;
 158                 break;
 159         case AT_UNIT:
 160                 assert("vs-331", !old_nr_units && !coord->unit_pos);
 161                 break;
 162         default:
 163                 impossible("vs-330", "coord is set improperly");
 164         }
 165
 166         /* prepare space for new units */
 167         memmove(ext + coord->unit_pos + data->length / sizeof(reiser4_extent),
 168                 ext + coord->unit_pos,
 169                 (old_nr_units - coord->unit_pos) * sizeof(reiser4_extent));
 170
 171         /* copy new data from kernel space */
 172         assert("vs-556", data->user == 0);
 173         memcpy(ext + coord->unit_pos, data->data, (unsigned)data->length);
 174
 175         /* after paste @coord is set to first of pasted units */
 176         assert("vs-332", coord_is_existing_unit(coord));
 177         assert("vs-333",
 178                !memcmp(data->data, extent_by_coord(coord),
 179                        (unsigned)data->length));
 180         return 0;
 181 }
 182
 183 /* item_plugin->b.can_shift */
 184 int
 185 can_shift_extent(unsigned free_space, coord_t * source,
 186                  znode * target UNUSED_ARG, shift_direction pend UNUSED_ARG,
 187                  unsigned *size, unsigned want)
 188 {
 189         *size = item_length_by_coord(source);
 190         if (*size > free_space)
 191                 /* never split a unit of extent item */
 192                 *size = free_space - free_space % sizeof(reiser4_extent);
 193
 194         /* we can shift *size bytes, calculate how many do we want to shift */
 195         if (*size > want * sizeof(reiser4_extent))
 196                 *size = want * sizeof(reiser4_extent);
 197
 198         if (*size % sizeof(reiser4_extent) != 0)
 199                 impossible("vs-119", "Wrong extent size: %i %zd", *size,
 200                            sizeof(reiser4_extent));
 201         return *size / sizeof(reiser4_extent);
 202
 203 }
 204
 205 /* item_plugin->b.copy_units */
 206 void
 207 copy_units_extent(coord_t * target, coord_t * source,
 208                   unsigned from, unsigned count,
 209                   shift_direction where_is_free_space, unsigned free_space)
 210 {
 211         char *from_ext, *to_ext;
 212
 213         assert("vs-217", free_space == count * sizeof(reiser4_extent));
 214
 215         from_ext = item_body_by_coord(source);
 216         to_ext = item_body_by_coord(target);
 217
 218         if (where_is_free_space == SHIFT_LEFT) {
 219                 assert("vs-215", from == 0);
 220
 221                 /* At this moment, item length was already updated in the item
 222                    header by shifting code, hence nr_units_extent() will
 223                    return "new" number of units---one we obtain after copying
 224                    units.
 225                  */
 226                 to_ext +=
 227                     (nr_units_extent(target) - count) * sizeof(reiser4_extent);
 228         } else {
 229                 reiser4_key key;
 230                 coord_t coord;
 231
 232                 assert("vs-216",
 233                        from + count == coord_last_unit_pos(source) + 1);
 234
 235                 from_ext += item_length_by_coord(source) - free_space;
 236
 237                 /* new units are inserted before first unit in an item,
 238                    therefore, we have to update item key */
 239                 coord = *source;
 240                 coord.unit_pos = from;
 241                 unit_key_extent(&coord, &key);
 242
 243                 node_plugin_by_node(target->node)->update_item_key(target, &key,
 244                                                                    NULL /*info */);
 245         }
 246
 247         memcpy(to_ext, from_ext, free_space);
 248 }
 249
 250 /* item_plugin->b.create_hook
 251    @arg is znode of leaf node for which we need to update right delimiting key */
 252 int create_hook_extent(const coord_t * coord, void *arg)
 253 {
 254         coord_t *child_coord;
 255         znode *node;
 256         reiser4_key key;
 257         reiser4_tree *tree;
 258
 259         if (!arg)
 260                 return 0;
 261
 262         child_coord = arg;
 263         tree = znode_get_tree(coord->node);
 264
 265         assert("nikita-3246", znode_get_level(child_coord->node) == LEAF_LEVEL);
 266
 267         write_lock_tree(tree);
 268         write_lock_dk(tree);
 269         /* find a node on the left level for which right delimiting key has to
 270            be updated */
 271         if (coord_wrt(child_coord) == COORD_ON_THE_LEFT) {
 272                 assert("vs-411", znode_is_left_connected(child_coord->node));
 273                 node = child_coord->node->left;
 274         } else {
 275                 assert("vs-412", coord_wrt(child_coord) == COORD_ON_THE_RIGHT);
 276                 node = child_coord->node;
 277                 assert("nikita-3314", node != NULL);
 278         }
 279
 280         if (node != NULL) {
 281                 znode_set_rd_key(node, item_key_by_coord(coord, &key));
 282
 283                 assert("nikita-3282", check_sibling_list(node));
 284                 /* break sibling links */
 285                 if (ZF_ISSET(node, JNODE_RIGHT_CONNECTED) && node->right) {
 286                         ON_DEBUG(node->right->left_version =
 287                                  atomic_inc_return(&delim_key_version);
 288                                  node->right_version =
 289                                  atomic_inc_return(&delim_key_version););
 290
 291                         node->right->left = NULL;
 292                         node->right = NULL;
 293                 }
 294         }
 295         write_unlock_dk(tree);
 296         write_unlock_tree(tree);
 297         return 0;
 298 }
 299
 300 #define ITEM_TAIL_KILLED 0
 301 #define ITEM_HEAD_KILLED 1
 302 #define ITEM_KILLED 2
 303
 304 /* item_plugin->b.kill_hook
 305    this is called when @count units starting from @from-th one are going to be removed
 306    */
 307 int
 308 kill_hook_extent(const coord_t * coord, pos_in_node_t from, pos_in_node_t count,
 309                  struct carry_kill_data *kdata)
 310 {
 311         reiser4_extent *ext;
 312         reiser4_block_nr start, length;
 313         const reiser4_key *pfrom_key, *pto_key;
 314         struct inode *inode;
 315         reiser4_tree *tree;
 316         pgoff_t from_off, to_off, offset, skip;
 317         int retval;
 318
 319         /* these are located in memory kmalloc-ed by kill_node_content */
 320         reiser4_key *min_item_key, *max_item_key, *from_key, *to_key, *key;
 321         coord_t *dup, *next;
 322
 323         assert("zam-811", znode_is_write_locked(coord->node));
 324         assert("nikita-3315", kdata != NULL);
 325         assert("vs-34", kdata->buf != NULL);
 326
 327         /* map structures to kdata->buf */
 328         min_item_key = (reiser4_key *) (kdata->buf);
 329         max_item_key = min_item_key + 1;
 330         from_key = max_item_key + 1;
 331         to_key = from_key + 1;
 332         key = to_key + 1;
 333         dup = (coord_t *) (key + 1);
 334         next = dup + 1;
 335
 336         item_key_by_coord(coord, min_item_key);
 337         max_item_key_by_coord(coord, max_item_key);
 338
 339         if (kdata->params.from_key) {
 340                 pfrom_key = kdata->params.from_key;
 341                 pto_key = kdata->params.to_key;
 342         } else {
 343                 assert("vs-1549", from == coord->unit_pos);
 344                 unit_key_by_coord(coord, from_key);
 345                 pfrom_key = from_key;
 346
 347                 coord_dup(dup, coord);
 348                 dup->unit_pos = from + count - 1;
 349                 max_unit_key_by_coord(dup, to_key);
 350                 pto_key = to_key;
 351         }
 352
 353         if (!keylt(pto_key, max_item_key)) {
 354                 if (!keygt(pfrom_key, min_item_key)) {
 355                         znode *left, *right;
 356
 357                         /* item is to be removed completely */
 358                         assert("nikita-3316", kdata->left != NULL
 359                                && kdata->right != NULL);
 360
 361                         left = kdata->left->node;
 362                         right = kdata->right->node;
 363
 364                         tree = current_tree;
 365                         /* we have to do two things:
 366                          *
 367                          *     1. link left and right formatted neighbors of
 368                          *        extent being removed, and
 369                          *
 370                          *     2. update their delimiting keys.
 371                          *
 372                          * atomicity of these operations is protected by
 373                          * taking dk-lock and tree-lock.
 374                          */
 375                         /* if neighbors of item being removed are znodes -
 376                          * link them */
 377                         write_lock_tree(tree);
 378                         write_lock_dk(tree);
 379                         link_left_and_right(left, right);
 380                         if (left) {
 381                                 /* update right delimiting key of left
 382                                  * neighbor of extent item */
 383                                 /*coord_t next;
 384                                    reiser4_key key; */
 385
 386                                 coord_dup(next, coord);
 387
 388                                 if (coord_next_item(next))
 389                                         *key = *znode_get_rd_key(coord->node);
 390                                 else
 391                                         item_key_by_coord(next, key);
 392                                 znode_set_rd_key(left, key);
 393                         }
 394                         write_unlock_dk(tree);
 395                         write_unlock_tree(tree);
 396
 397                         from_off =
 398                             get_key_offset(min_item_key) >> PAGE_CACHE_SHIFT;
 399                         to_off =
 400                             (get_key_offset(max_item_key) +
 401                              1) >> PAGE_CACHE_SHIFT;
 402                         retval = ITEM_KILLED;
 403                 } else {
 404                         /* tail of item is to be removed */
 405                         from_off =
 406                             (get_key_offset(pfrom_key) + PAGE_CACHE_SIZE -
 407                              1) >> PAGE_CACHE_SHIFT;
 408                         to_off =
 409                             (get_key_offset(max_item_key) +
 410                              1) >> PAGE_CACHE_SHIFT;
 411                         retval = ITEM_TAIL_KILLED;
 412                 }
 413         } else {
 414                 /* head of item is to be removed */
 415                 assert("vs-1571", keyeq(pfrom_key, min_item_key));
 416                 assert("vs-1572",
 417                        (get_key_offset(pfrom_key) & (PAGE_CACHE_SIZE - 1)) ==
 418                        0);
 419                 assert("vs-1573",
 420                        ((get_key_offset(pto_key) + 1) & (PAGE_CACHE_SIZE -
 421                                                          1)) == 0);
 422
 423                 if (kdata->left->node) {
 424                         /* update right delimiting key of left neighbor of extent item */
 425                         /*reiser4_key key; */
 426
 427                         *key = *pto_key;
 428                         set_key_offset(key, get_key_offset(pto_key) + 1);
 429
 430                         write_lock_dk(current_tree);
 431                         znode_set_rd_key(kdata->left->node, key);
 432                         write_unlock_dk(current_tree);
 433                 }
 434
 435                 from_off = get_key_offset(pfrom_key) >> PAGE_CACHE_SHIFT;
 436                 to_off = (get_key_offset(pto_key) + 1) >> PAGE_CACHE_SHIFT;
 437                 retval = ITEM_HEAD_KILLED;
 438         }
 439
 440         inode = kdata->inode;
 441         assert("vs-1545", inode != NULL);
 442         if (inode != NULL)
 443                 /* take care of pages and jnodes corresponding to part of item being killed */
 444                 reiser4_invalidate_pages(inode->i_mapping, from_off,
 445                                          to_off - from_off,
 446                                          kdata->params.truncate);
 447
 448         ext = extent_item(coord) + from;
 449         offset =
 450             (get_key_offset(min_item_key) +
 451              reiser4_extent_size(coord, from)) >> PAGE_CACHE_SHIFT;
 452
 453         assert("vs-1551", from_off >= offset);
 454         assert("vs-1552", from_off - offset <= extent_get_width(ext));
 455         skip = from_off - offset;
 456         offset = from_off;
 457
 458         while (offset < to_off) {
 459                 length = extent_get_width(ext) - skip;
 460                 if (state_of_extent(ext) == HOLE_EXTENT) {
 461                         skip = 0;
 462                         offset += length;
 463                         ext++;
 464                         continue;
 465                 }
 466
 467                 if (offset + length > to_off) {
 468                         length = to_off - offset;
 469                 }
 470
 471                 DQUOT_FREE_BLOCK_NODIRTY(inode, length);
 472
 473                 if (state_of_extent(ext) == UNALLOCATED_EXTENT) {
 474                         /* some jnodes corresponding to this unallocated extent */
 475                         fake_allocated2free(length, 0 /* unformatted */ );
 476
 477                         skip = 0;
 478                         offset += length;
 479                         ext++;
 480                         continue;
 481                 }
 482
 483                 assert("vs-1218", state_of_extent(ext) == ALLOCATED_EXTENT);
 484
 485                 if (length != 0) {
 486                         start = extent_get_start(ext) + skip;
 487
 488                         /* BA_DEFER bit parameter is turned on because blocks which get freed are not safe to be freed
 489                            immediately */
 490                         reiser4_dealloc_blocks(&start, &length,
 491                                                0 /* not used */ ,
 492                                                BA_DEFER
 493                                                /* unformatted with defer */ );
 494                 }
 495                 skip = 0;
 496                 offset += length;
 497                 ext++;
 498         }
 499         return retval;
 500 }
 501
 502 /* item_plugin->b.kill_units */
 503 int
 504 kill_units_extent(coord_t * coord, pos_in_node_t from, pos_in_node_t to,
 505                   struct carry_kill_data *kdata, reiser4_key * smallest_removed,
 506                   reiser4_key * new_first)
 507 {
 508         reiser4_extent *ext;
 509         reiser4_key item_key;
 510         pos_in_node_t count;
 511         reiser4_key from_key, to_key;
 512         const reiser4_key *pfrom_key, *pto_key;
 513         loff_t off;
 514         int result;
 515
 516         assert("vs-1541",
 517                ((kdata->params.from_key == NULL && kdata->params.to_key == NULL)
 518                 || (kdata->params.from_key != NULL
 519                     && kdata->params.to_key != NULL)));
 520
 521         if (kdata->params.from_key) {
 522                 pfrom_key = kdata->params.from_key;
 523                 pto_key = kdata->params.to_key;
 524         } else {
 525                 coord_t dup;
 526
 527                 /* calculate key range of kill */
 528                 assert("vs-1549", from == coord->unit_pos);
 529                 unit_key_by_coord(coord, &from_key);
 530                 pfrom_key = &from_key;
 531
 532                 coord_dup(&dup, coord);
 533                 dup.unit_pos = to;
 534                 max_unit_key_by_coord(&dup, &to_key);
 535                 pto_key = &to_key;
 536         }
 537
 538         item_key_by_coord(coord, &item_key);
 539
 540 #if REISER4_DEBUG
 541         {
 542                 reiser4_key max_item_key;
 543
 544                 max_item_key_by_coord(coord, &max_item_key);
 545
 546                 if (new_first) {
 547                         /* head of item is to be cut */
 548                         assert("vs-1542", keyeq(pfrom_key, &item_key));
 549                         assert("vs-1538", keylt(pto_key, &max_item_key));
 550                 } else {
 551                         /* tail of item is to be cut */
 552                         assert("vs-1540", keygt(pfrom_key, &item_key));
 553                         assert("vs-1543", !keylt(pto_key, &max_item_key));
 554                 }
 555         }
 556 #endif
 557
 558         if (smallest_removed)
 559                 *smallest_removed = *pfrom_key;
 560
 561         if (new_first) {
 562                 /* item head is cut. Item key will change. This new key is calculated here */
 563                 assert("vs-1556",
 564                        (get_key_offset(pto_key) & (PAGE_CACHE_SIZE - 1)) ==
 565                        (PAGE_CACHE_SIZE - 1));
 566                 *new_first = *pto_key;
 567                 set_key_offset(new_first, get_key_offset(new_first) + 1);
 568         }
 569
 570         count = to - from + 1;
 571         result = kill_hook_extent(coord, from, count, kdata);
 572         if (result == ITEM_TAIL_KILLED) {
 573                 assert("vs-1553",
 574                        get_key_offset(pfrom_key) >=
 575                        get_key_offset(&item_key) +
 576                        reiser4_extent_size(coord, from));
 577                 off =
 578                     get_key_offset(pfrom_key) -
 579                         (get_key_offset(&item_key) +
 580                          reiser4_extent_size(coord, from));
 581                 if (off) {
 582                         /* unit @from is to be cut partially. Its width decreases */
 583                         ext = extent_item(coord) + from;
 584                         extent_set_width(ext,
 585                                          (off + PAGE_CACHE_SIZE -
 586                                           1) >> PAGE_CACHE_SHIFT);
 587                         count--;
 588                 }
 589         } else {
 590                 __u64 max_to_offset;
 591                 __u64 rest;
 592
 593                 assert("vs-1575", result == ITEM_HEAD_KILLED);
 594                 assert("", from == 0);
 595                 assert("",
 596                        ((get_key_offset(pto_key) + 1) & (PAGE_CACHE_SIZE -
 597                                                          1)) == 0);
 598                 assert("",
 599                        get_key_offset(pto_key) + 1 >
 600                        get_key_offset(&item_key) +
 601                        reiser4_extent_size(coord, to));
 602                 max_to_offset =
 603                     get_key_offset(&item_key) +
 604                         reiser4_extent_size(coord, to + 1) - 1;
 605                 assert("", get_key_offset(pto_key) <= max_to_offset);
 606
 607                 rest =
 608                     (max_to_offset -
 609                      get_key_offset(pto_key)) >> PAGE_CACHE_SHIFT;
 610                 if (rest) {
 611                         /* unit @to is to be cut partially */
 612                         ext = extent_item(coord) + to;
 613
 614                         assert("", extent_get_width(ext) > rest);
 615
 616                         if (state_of_extent(ext) == ALLOCATED_EXTENT)
 617                                 extent_set_start(ext,
 618                                                  extent_get_start(ext) +
 619                                                  (extent_get_width(ext) -
 620                                                   rest));
 621
 622                         extent_set_width(ext, rest);
 623                         count--;
 624                 }
 625         }
 626         return count * sizeof(reiser4_extent);
 627 }
 628
 629 /* item_plugin->b.cut_units
 630    this is too similar to kill_units_extent */
 631 int
 632 cut_units_extent(coord_t * coord, pos_in_node_t from, pos_in_node_t to,
 633                  struct carry_cut_data *cdata, reiser4_key * smallest_removed,
 634                  reiser4_key * new_first)
 635 {
 636         reiser4_extent *ext;
 637         reiser4_key item_key;
 638         pos_in_node_t count;
 639         reiser4_key from_key, to_key;
 640         const reiser4_key *pfrom_key, *pto_key;
 641         loff_t off;
 642
 643         assert("vs-1541",
 644                ((cdata->params.from_key == NULL && cdata->params.to_key == NULL)
 645                 || (cdata->params.from_key != NULL
 646                     && cdata->params.to_key != NULL)));
 647
 648         if (cdata->params.from_key) {
 649                 pfrom_key = cdata->params.from_key;
 650                 pto_key = cdata->params.to_key;
 651         } else {
 652                 coord_t dup;
 653
 654                 /* calculate key range of kill */
 655                 coord_dup(&dup, coord);
 656                 dup.unit_pos = from;
 657                 unit_key_by_coord(&dup, &from_key);
 658
 659                 dup.unit_pos = to;
 660                 max_unit_key_by_coord(&dup, &to_key);
 661
 662                 pfrom_key = &from_key;
 663                 pto_key = &to_key;
 664         }
 665
 666         assert("vs-1555",
 667                (get_key_offset(pfrom_key) & (PAGE_CACHE_SIZE - 1)) == 0);
 668         assert("vs-1556",
 669                (get_key_offset(pto_key) & (PAGE_CACHE_SIZE - 1)) ==
 670                (PAGE_CACHE_SIZE - 1));
 671
 672         item_key_by_coord(coord, &item_key);
 673
 674 #if REISER4_DEBUG
 675         {
 676                 reiser4_key max_item_key;
 677
 678                 assert("vs-1584",
 679                        get_key_locality(pfrom_key) ==
 680                        get_key_locality(&item_key));
 681                 assert("vs-1585",
 682                        get_key_type(pfrom_key) == get_key_type(&item_key));
 683                 assert("vs-1586",
 684                        get_key_objectid(pfrom_key) ==
 685                        get_key_objectid(&item_key));
 686                 assert("vs-1587",
 687                        get_key_ordering(pfrom_key) ==
 688                        get_key_ordering(&item_key));
 689
 690                 max_item_key_by_coord(coord, &max_item_key);
 691
 692                 if (new_first != NULL) {
 693                         /* head of item is to be cut */
 694                         assert("vs-1542", keyeq(pfrom_key, &item_key));
 695                         assert("vs-1538", keylt(pto_key, &max_item_key));
 696                 } else {
 697                         /* tail of item is to be cut */
 698                         assert("vs-1540", keygt(pfrom_key, &item_key));
 699                         assert("vs-1543", keyeq(pto_key, &max_item_key));
 700                 }
 701         }
 702 #endif
 703
 704         if (smallest_removed)
 705                 *smallest_removed = *pfrom_key;
 706
 707         if (new_first) {
 708                 /* item head is cut. Item key will change. This new key is calculated here */
 709                 *new_first = *pto_key;
 710                 set_key_offset(new_first, get_key_offset(new_first) + 1);
 711         }
 712
 713         count = to - from + 1;
 714
 715         assert("vs-1553",
 716                get_key_offset(pfrom_key) >=
 717                get_key_offset(&item_key) + reiser4_extent_size(coord, from));
 718         off =
 719             get_key_offset(pfrom_key) - (get_key_offset(&item_key) +
 720                                          reiser4_extent_size(coord, from));
 721         if (off) {
 722                 /* tail of unit @from is to be cut partially. Its width decreases */
 723                 assert("vs-1582", new_first == NULL);
 724                 ext = extent_item(coord) + from;
 725                 extent_set_width(ext, off >> PAGE_CACHE_SHIFT);
 726                 count--;
 727         }
 728
 729         assert("vs-1554",
 730                get_key_offset(pto_key) <=
 731                get_key_offset(&item_key) +
 732                reiser4_extent_size(coord, to + 1) - 1);
 733         off =
 734                 (get_key_offset(&item_key) +
 735                  reiser4_extent_size(coord, to + 1) - 1) -
 736                 get_key_offset(pto_key);
 737         if (off) {
 738                 /* @to_key is smaller than max key of unit @to. Unit @to will not be removed. It gets start increased
 739                    and width decreased. */
 740                 assert("vs-1583", (off & (PAGE_CACHE_SIZE - 1)) == 0);
 741                 ext = extent_item(coord) + to;
 742                 if (state_of_extent(ext) == ALLOCATED_EXTENT)
 743                         extent_set_start(ext,
 744                                          extent_get_start(ext) +
 745                                          (extent_get_width(ext) -
 746                                           (off >> PAGE_CACHE_SHIFT)));
 747
 748                 extent_set_width(ext, (off >> PAGE_CACHE_SHIFT));
 749                 count--;
 750         }
 751         return count * sizeof(reiser4_extent);
 752 }
 753
 754 /* item_plugin->b.unit_key */
 755 reiser4_key *unit_key_extent(const coord_t * coord, reiser4_key * key)
 756 {
 757         assert("vs-300", coord_is_existing_unit(coord));
 758
 759         item_key_by_coord(coord, key);
 760         set_key_offset(key,
 761                        (get_key_offset(key) +
 762                         reiser4_extent_size(coord, coord->unit_pos)));
 763
 764         return key;
 765 }
 766
 767 /* item_plugin->b.max_unit_key */
 768 reiser4_key *max_unit_key_extent(const coord_t * coord, reiser4_key * key)
 769 {
 770         assert("vs-300", coord_is_existing_unit(coord));
 771
 772         item_key_by_coord(coord, key);
 773         set_key_offset(key,
 774                        (get_key_offset(key) +
 775                         reiser4_extent_size(coord, coord->unit_pos + 1) - 1));
 776         return key;
 777 }
 778
 779 /* item_plugin->b.estimate
 780    item_plugin->b.item_data_by_flow */
 781
 782 #if REISER4_DEBUG
 783
 784 /* item_plugin->b.check
 785    used for debugging, every item should have here the most complete
 786    possible check of the consistency of the item that the inventor can
 787    construct
 788 */
 789 int reiser4_check_extent(const coord_t * coord /* coord of item to check */,
 790                          const char **error /* where to store error message */)
 791 {
 792         reiser4_extent *ext, *first;
 793         unsigned i, j;
 794         reiser4_block_nr start, width, blk_cnt;
 795         unsigned num_units;
 796         reiser4_tree *tree;
 797         oid_t oid;
 798         reiser4_key key;
 799         coord_t scan;
 800
 801         assert("vs-933", REISER4_DEBUG);
 802
 803         if (znode_get_level(coord->node) != TWIG_LEVEL) {
 804                 *error = "Extent on the wrong level";
 805                 return -1;
 806         }
 807         if (item_length_by_coord(coord) % sizeof(reiser4_extent) != 0) {
 808                 *error = "Wrong item size";
 809                 return -1;
 810         }
 811         ext = first = extent_item(coord);
 812         blk_cnt = reiser4_block_count(reiser4_get_current_sb());
 813         num_units = coord_num_units(coord);
 814         tree = znode_get_tree(coord->node);
 815         item_key_by_coord(coord, &key);
 816         oid = get_key_objectid(&key);
 817         coord_dup(&scan, coord);
 818
 819         for (i = 0; i < num_units; ++i, ++ext) {
 820                 __u64 index;
 821
 822                 scan.unit_pos = i;
 823                 index = extent_unit_index(&scan);
 824
 825 #if 0
 826                 /* check that all jnodes are present for the unallocated
 827                  * extent */
 828                 if (state_of_extent(ext) == UNALLOCATED_EXTENT) {
 829                         for (j = 0; j < extent_get_width(ext); j++) {
 830                                 jnode *node;
 831
 832                                 node = jlookup(tree, oid, index + j);
 833                                 if (node == NULL) {
 834                                         print_coord("scan", &scan, 0);
 835                                         *error = "Jnode missing";
 836                                         return -1;
 837                                 }
 838                                 jput(node);
 839                         }
 840                 }
 841 #endif
 842
 843                 start = extent_get_start(ext);
 844                 if (start < 2)
 845                         continue;
 846                 /* extent is allocated one */
 847                 width = extent_get_width(ext);
 848                 if (start >= blk_cnt) {
 849                         *error = "Start too large";
 850                         return -1;
 851                 }
 852                 if (start + width > blk_cnt) {
 853                         *error = "End too large";
 854                         return -1;
 855                 }
 856                 /* make sure that this extent does not overlap with other
 857                    allocated extents extents */
 858                 for (j = 0; j < i; j++) {
 859                         if (state_of_extent(first + j) != ALLOCATED_EXTENT)
 860                                 continue;
 861                         if (!
 862                             ((extent_get_start(ext) >=
 863                               extent_get_start(first + j) +
 864                               extent_get_width(first + j))
 865                              || (extent_get_start(ext) +
 866                                  extent_get_width(ext) <=
 867                                  extent_get_start(first + j)))) {
 868                                 *error = "Extent overlaps with others";
 869                                 return -1;
 870                         }
 871                 }
 872
 873         }
 874
 875         return 0;
 876 }
 877
 878 #endif                          /* REISER4_DEBUG */
 879
 880 /*
 881    Local variables:
 882    c-indentation-style: "K&R"
 883    mode-name: "LC"
 884    c-basic-offset: 8
 885    tab-width: 8
 886    fill-column: 120
 887    scroll-step: 1
 888    End:
 889 */