?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
revert-mm-fix-blkdev-size-calculation-in-generic_write_checks
[linux-2.6/linux-trees-mm.git] / fs / reiser4 / plugin / node / node40.c
blob6a9cc73d3d52d335725837661cf44226ba8c0852
1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
2
3 #include "../../debug.h"
4 #include "../../key.h"
5 #include "../../coord.h"
6 #include "../plugin_header.h"
7 #include "../item/item.h"
8 #include "node.h"
9 #include "node40.h"
10 #include "../plugin.h"
11 #include "../../jnode.h"
12 #include "../../znode.h"
13 #include "../../pool.h"
14 #include "../../carry.h"
15 #include "../../tap.h"
16 #include "../../tree.h"
17 #include "../../super.h"
18 #include "../../reiser4.h"
19
20 #include <asm/uaccess.h>
21 #include <linux/types.h>
22 #include <linux/prefetch.h>
23
24 /* leaf 40 format:
25
26 [node header | item 0, item 1, .., item N-1 | free space | item_head N-1, .. item_head 1, item head 0 ]
27 plugin_id (16) key
28 free_space (16) pluginid (16)
29 free_space_start (16) offset (16)
30 level (8)
31 num_items (16)
32 magic (32)
33 flush_time (32)
34 */
35 /* NIKITA-FIXME-HANS: I told you guys not less than 10 times to not call it r4fs. Change to "ReIs". */
36 /* magic number that is stored in ->magic field of node header */
37 static const __u32 REISER4_NODE_MAGIC = 0x52344653; /* (*(__u32 *)"R4FS"); */
38
39 static int prepare_for_update(znode * left, znode * right,
40 carry_plugin_info * info);
41
42 /* header of node of reiser40 format is at the beginning of node */
43 static inline node40_header *node40_node_header(const znode * node /* node to
44 * query */ )
45 {
46 assert("nikita-567", node != NULL);
47 assert("nikita-568", znode_page(node) != NULL);
48 assert("nikita-569", zdata(node) != NULL);
49 return (node40_header *) zdata(node);
50 }
51
52 /* functions to get/set fields of node40_header */
53 #define nh40_get_magic(nh) le32_to_cpu(get_unaligned(&(nh)->magic))
54 #define nh40_get_free_space(nh) le16_to_cpu(get_unaligned(&(nh)->free_space))
55 #define nh40_get_free_space_start(nh) le16_to_cpu(get_unaligned(&(nh)->free_space_start))
56 #define nh40_get_level(nh) get_unaligned(&(nh)->level)
57 #define nh40_get_num_items(nh) le16_to_cpu(get_unaligned(&(nh)->nr_items))
58 #define nh40_get_flush_id(nh) le64_to_cpu(get_unaligned(&(nh)->flush_id))
59
60 #define nh40_set_magic(nh, value) put_unaligned(cpu_to_le32(value), &(nh)->magic)
61 #define nh40_set_free_space(nh, value) put_unaligned(cpu_to_le16(value), &(nh)->free_space)
62 #define nh40_set_free_space_start(nh, value) put_unaligned(cpu_to_le16(value), &(nh)->free_space_start)
63 #define nh40_set_level(nh, value) put_unaligned(value, &(nh)->level)
64 #define nh40_set_num_items(nh, value) put_unaligned(cpu_to_le16(value), &(nh)->nr_items)
65 #define nh40_set_mkfs_id(nh, value) put_unaligned(cpu_to_le32(value), &(nh)->mkfs_id)
66
67 /* plugin field of node header should be read/set by
68 plugin_by_disk_id/save_disk_plugin */
69
70 /* array of item headers is at the end of node */
71 static inline item_header40 *node40_ih_at(const znode * node, unsigned pos)
72 {
73 return (item_header40 *) (zdata(node) + znode_size(node)) - pos - 1;
74 }
75
76 /* ( page_address( node -> pg ) + PAGE_CACHE_SIZE ) - pos - 1
77 */
78 static inline item_header40 *node40_ih_at_coord(const coord_t * coord)
79 {
80 return (item_header40 *) (zdata(coord->node) +
81 znode_size(coord->node)) - (coord->item_pos) -
82 1;
83 }
84
85 /* functions to get/set fields of item_header40 */
86 #define ih40_get_offset(ih) le16_to_cpu(get_unaligned(&(ih)->offset))
87
88 #define ih40_set_offset(ih, value) put_unaligned(cpu_to_le16(value), &(ih)->offset)
89
90 /* plugin field of item header should be read/set by
91 plugin_by_disk_id/save_disk_plugin */
92
93 /* plugin methods */
94
95 /* plugin->u.node.item_overhead
96 look for description of this method in plugin/node/node.h */
97 size_t
98 item_overhead_node40(const znode * node UNUSED_ARG, flow_t * f UNUSED_ARG)
99 {
100 return sizeof(item_header40);
101 }
102
103 /* plugin->u.node.free_space
104 look for description of this method in plugin/node/node.h */
105 size_t free_space_node40(znode * node)
106 {
107 assert("nikita-577", node != NULL);
108 assert("nikita-578", znode_is_loaded(node));
109 assert("nikita-579", zdata(node) != NULL);
110
111 return nh40_get_free_space(node40_node_header(node));
112 }
113
114 /* private inline version of node40_num_of_items() for use in this file. This
115 is necessary, because address of node40_num_of_items() is taken and it is
116 never inlined as a result. */
117 static inline short node40_num_of_items_internal(const znode * node)
118 {
119 return nh40_get_num_items(node40_node_header(node));
120 }
121
122 #if REISER4_DEBUG
123 static inline void check_num_items(const znode * node)
124 {
125 assert("nikita-2749",
126 node40_num_of_items_internal(node) == node->nr_items);
127 assert("nikita-2746", znode_is_write_locked(node));
128 }
129 #else
130 #define check_num_items(node) noop
131 #endif
132
133 /* plugin->u.node.num_of_items
134 look for description of this method in plugin/node/node.h */
135 int num_of_items_node40(const znode * node)
136 {
137 return node40_num_of_items_internal(node);
138 }
139
140 static void
141 node40_set_num_items(znode * node, node40_header * nh, unsigned value)
142 {
143 assert("nikita-2751", node != NULL);
144 assert("nikita-2750", nh == node40_node_header(node));
145
146 check_num_items(node);
147 nh40_set_num_items(nh, value);
148 node->nr_items = value;
149 check_num_items(node);
150 }
151
152 /* plugin->u.node.item_by_coord
153 look for description of this method in plugin/node/node.h */
154 char *item_by_coord_node40(const coord_t * coord)
155 {
156 item_header40 *ih;
157 char *p;
158
159 /* @coord is set to existing item */
160 assert("nikita-596", coord != NULL);
161 assert("vs-255", coord_is_existing_item(coord));
162
163 ih = node40_ih_at_coord(coord);
164 p = zdata(coord->node) + ih40_get_offset(ih);
165 return p;
166 }
167
168 /* plugin->u.node.length_by_coord
169 look for description of this method in plugin/node/node.h */
170 int length_by_coord_node40(const coord_t * coord)
171 {
172 item_header40 *ih;
173 int result;
174
175 /* @coord is set to existing item */
176 assert("vs-256", coord != NULL);
177 assert("vs-257", coord_is_existing_item(coord));
178
179 ih = node40_ih_at_coord(coord);
180 if ((int)coord->item_pos ==
181 node40_num_of_items_internal(coord->node) - 1)
182 result =
183 nh40_get_free_space_start(node40_node_header(coord->node)) -
184 ih40_get_offset(ih);
185 else
186 result = ih40_get_offset(ih - 1) - ih40_get_offset(ih);
187
188 return result;
189 }
190
191 static pos_in_node_t
192 node40_item_length(const znode * node, pos_in_node_t item_pos)
193 {
194 item_header40 *ih;
195 pos_in_node_t result;
196
197 /* @coord is set to existing item */
198 assert("vs-256", node != NULL);
199 assert("vs-257", node40_num_of_items_internal(node) > item_pos);
200
201 ih = node40_ih_at(node, item_pos);
202 if (item_pos == node40_num_of_items_internal(node) - 1)
203 result =
204 nh40_get_free_space_start(node40_node_header(node)) -
205 ih40_get_offset(ih);
206 else
207 result = ih40_get_offset(ih - 1) - ih40_get_offset(ih);
208
209 return result;
210 }
211
212 /* plugin->u.node.plugin_by_coord
213 look for description of this method in plugin/node/node.h */
214 item_plugin *plugin_by_coord_node40(const coord_t * coord)
215 {
216 item_header40 *ih;
217 item_plugin *result;
218
219 /* @coord is set to existing item */
220 assert("vs-258", coord != NULL);
221 assert("vs-259", coord_is_existing_item(coord));
222
223 ih = node40_ih_at_coord(coord);
224 /* pass NULL in stead of current tree. This is time critical call. */
225 result = item_plugin_by_disk_id(NULL, &ih->plugin_id);
226 return result;
227 }
228
229 /* plugin->u.node.key_at
230 look for description of this method in plugin/node/node.h */
231 reiser4_key *key_at_node40(const coord_t * coord, reiser4_key * key)
232 {
233 item_header40 *ih;
234
235 assert("nikita-1765", coord_is_existing_item(coord));
236
237 /* @coord is set to existing item */
238 ih = node40_ih_at_coord(coord);
239 memcpy(key, &ih->key, sizeof(reiser4_key));
240 return key;
241 }
242
243 /* VS-FIXME-HANS: please review whether the below are properly disabled when debugging is disabled */
244
245 #define NODE_INCSTAT(n, counter) \
246 reiser4_stat_inc_at_level(znode_get_level(n), node.lookup.counter)
247
248 #define NODE_ADDSTAT(n, counter, val) \
249 reiser4_stat_add_at_level(znode_get_level(n), node.lookup.counter, val)
250
251 /* plugin->u.node.lookup
252 look for description of this method in plugin/node/node.h */
253 node_search_result lookup_node40(znode * node /* node to query */ ,
254 const reiser4_key * key /* key to look for */ ,
255 lookup_bias bias /* search bias */ ,
256 coord_t * coord /* resulting coord */ )
257 {
258 int left;
259 int right;
260 int found;
261 int items;
262
263 item_header40 *lefth;
264 item_header40 *righth;
265
266 item_plugin *iplug;
267 item_header40 *bstop;
268 item_header40 *ih;
269 cmp_t order;
270
271 assert("nikita-583", node != NULL);
272 assert("nikita-584", key != NULL);
273 assert("nikita-585", coord != NULL);
274 assert("nikita-2693", znode_is_any_locked(node));
275 cassert(REISER4_SEQ_SEARCH_BREAK > 2);
276
277 items = node_num_items(node);
278
279 if (unlikely(items == 0)) {
280 coord_init_first_unit(coord, node);
281 return NS_NOT_FOUND;
282 }
283
284 /* binary search for item that can contain given key */
285 left = 0;
286 right = items - 1;
287 coord->node = node;
288 coord_clear_iplug(coord);
289 found = 0;
290
291 lefth = node40_ih_at(node, left);
292 righth = node40_ih_at(node, right);
293
294 /* It is known that for small arrays sequential search is on average
295 more efficient than binary. This is because sequential search is
296 coded as tight loop that can be better optimized by compilers and
297 for small array size gain from this optimization makes sequential
298 search the winner. Another, maybe more important, reason for this,
299 is that sequential array is more CPU cache friendly, whereas binary
300 search effectively destroys CPU caching.
301
302 Critical here is the notion of "smallness". Reasonable value of
303 REISER4_SEQ_SEARCH_BREAK can be found by playing with code in
304 fs/reiser4/ulevel/ulevel.c:test_search().
305
306 Don't try to further optimize sequential search by scanning from
307 right to left in attempt to use more efficient loop termination
308 condition (comparison with 0). This doesn't work.
309
310 */
311
312 while (right - left >= REISER4_SEQ_SEARCH_BREAK) {
313 int median;
314 item_header40 *medianh;
315
316 median = (left + right) / 2;
317 medianh = node40_ih_at(node, median);
318
319 assert("nikita-1084", median >= 0);
320 assert("nikita-1085", median < items);
321 switch (keycmp(key, &medianh->key)) {
322 case LESS_THAN:
323 right = median;
324 righth = medianh;
325 break;
326 default:
327 wrong_return_value("nikita-586", "keycmp");
328 case GREATER_THAN:
329 left = median;
330 lefth = medianh;
331 break;
332 case EQUAL_TO:
333 do {
334 --median;
335 /* headers are ordered from right to left */
336 ++medianh;
337 } while (median >= 0 && keyeq(key, &medianh->key));
338 right = left = median + 1;
339 ih = lefth = righth = medianh - 1;
340 found = 1;
341 break;
342 }
343 }
344 /* sequential scan. Item headers, and, therefore, keys are stored at
345 the rightmost part of a node from right to left. We are trying to
346 access memory from left to right, and hence, scan in _descending_
347 order of item numbers.
348 */
349 if (!found) {
350 for (left = right, ih = righth; left >= 0; ++ih, --left) {
351 cmp_t comparison;
352
353 prefetchkey(&(ih + 1)->key);
354 comparison = keycmp(&ih->key, key);
355 if (comparison == GREATER_THAN)
356 continue;
357 if (comparison == EQUAL_TO) {
358 found = 1;
359 do {
360 --left;
361 ++ih;
362 } while (left >= 0 && keyeq(&ih->key, key));
363 ++left;
364 --ih;
365 } else {
366 assert("nikita-1256", comparison == LESS_THAN);
367 }
368 break;
369 }
370 if (unlikely(left < 0))
371 left = 0;
372 }
373
374 assert("nikita-3212", right >= left);
375 assert("nikita-3214",
376 equi(found, keyeq(&node40_ih_at(node, left)->key, key)));
377
378 coord_set_item_pos(coord, left);
379 coord->unit_pos = 0;
380 coord->between = AT_UNIT;
381
382 /* key < leftmost key in a mode or node is corrupted and keys
383 are not sorted */
384 bstop = node40_ih_at(node, (unsigned)left);
385 order = keycmp(&bstop->key, key);
386 if (unlikely(order == GREATER_THAN)) {
387 if (unlikely(left != 0)) {
388 /* screw up */
389 warning("nikita-587", "Key less than %i key in a node",
390 left);
391 reiser4_print_key("key", key);
392 reiser4_print_key("min", &bstop->key);
393 print_coord_content("coord", coord);
394 return RETERR(-EIO);
395 } else {
396 coord->between = BEFORE_UNIT;
397 return NS_NOT_FOUND;
398 }
399 }
400 /* left <= key, ok */
401 iplug = item_plugin_by_disk_id(znode_get_tree(node), &bstop->plugin_id);
402
403 if (unlikely(iplug == NULL)) {
404 warning("nikita-588", "Unknown plugin %i",
405 le16_to_cpu(get_unaligned(&bstop->plugin_id)));
406 reiser4_print_key("key", key);
407 print_coord_content("coord", coord);
408 return RETERR(-EIO);
409 }
410
411 coord_set_iplug(coord, iplug);
412
413 /* if exact key from item header was found by binary search, no
414 further checks are necessary. */
415 if (found) {
416 assert("nikita-1259", order == EQUAL_TO);
417 return NS_FOUND;
418 }
419 if (iplug->b.max_key_inside != NULL) {
420 reiser4_key max_item_key;
421
422 /* key > max_item_key --- outside of an item */
423 if (keygt(key, iplug->b.max_key_inside(coord, &max_item_key))) {
424 coord->unit_pos = 0;
425 coord->between = AFTER_ITEM;
426 /* FIXME-VS: key we are looking for does not fit into
427 found item. Return NS_NOT_FOUND then. Without that
428 the following case does not work: there is extent of
429 file 10000, 10001. File 10000, 10002 has been just
430 created. When writing to position 0 in that file -
431 traverse_tree will stop here on twig level. When we
432 want it to go down to leaf level
433 */
434 return NS_NOT_FOUND;
435 }
436 }
437
438 if (iplug->b.lookup != NULL) {
439 return iplug->b.lookup(key, bias, coord);
440 } else {
441 assert("nikita-1260", order == LESS_THAN);
442 coord->between = AFTER_UNIT;
443 return (bias == FIND_EXACT) ? NS_NOT_FOUND : NS_FOUND;
444 }
445 }
446
447 #undef NODE_ADDSTAT
448 #undef NODE_INCSTAT
449
450 /* plugin->u.node.estimate
451 look for description of this method in plugin/node/node.h */
452 size_t estimate_node40(znode * node)
453 {
454 size_t result;
455
456 assert("nikita-597", node != NULL);
457
458 result = free_space_node40(node) - sizeof(item_header40);
459
460 return (result > 0) ? result : 0;
461 }
462
463 /* plugin->u.node.check
464 look for description of this method in plugin/node/node.h */
465 int check_node40(const znode * node /* node to check */ ,
466 __u32 flags /* check flags */ ,
467 const char **error /* where to store error message */ )
468 {
469 int nr_items;
470 int i;
471 reiser4_key prev;
472 unsigned old_offset;
473 tree_level level;
474 coord_t coord;
475 int result;
476
477 assert("nikita-580", node != NULL);
478 assert("nikita-581", error != NULL);
479 assert("nikita-2948", znode_is_loaded(node));
480
481 if (ZF_ISSET(node, JNODE_HEARD_BANSHEE))
482 return 0;
483
484 assert("nikita-582", zdata(node) != NULL);
485
486 nr_items = node40_num_of_items_internal(node);
487 if (nr_items < 0) {
488 *error = "Negative number of items";
489 return -1;
490 }
491
492 if (flags & REISER4_NODE_DKEYS)
493 prev = *znode_get_ld_key((znode *) node);
494 else
495 prev = *reiser4_min_key();
496
497 old_offset = 0;
498 coord_init_zero(&coord);
499 coord.node = (znode *) node;
500 coord.unit_pos = 0;
501 coord.between = AT_UNIT;
502 level = znode_get_level(node);
503 for (i = 0; i < nr_items; i++) {
504 item_header40 *ih;
505 reiser4_key unit_key;
506 unsigned j;
507
508 ih = node40_ih_at(node, (unsigned)i);
509 coord_set_item_pos(&coord, i);
510 if ((ih40_get_offset(ih) >=
511 znode_size(node) - nr_items * sizeof(item_header40)) ||
512 (ih40_get_offset(ih) < sizeof(node40_header))) {
513 *error = "Offset is out of bounds";
514 return -1;
515 }
516 if (ih40_get_offset(ih) <= old_offset) {
517 *error = "Offsets are in wrong order";
518 return -1;
519 }
520 if ((i == 0) && (ih40_get_offset(ih) != sizeof(node40_header))) {
521 *error = "Wrong offset of first item";
522 return -1;
523 }
524 old_offset = ih40_get_offset(ih);
525
526 if (keygt(&prev, &ih->key)) {
527 *error = "Keys are in wrong order";
528 return -1;
529 }
530 if (!keyeq(&ih->key, unit_key_by_coord(&coord, &unit_key))) {
531 *error = "Wrong key of first unit";
532 return -1;
533 }
534 prev = ih->key;
535 for (j = 0; j < coord_num_units(&coord); ++j) {
536 coord.unit_pos = j;
537 unit_key_by_coord(&coord, &unit_key);
538 if (keygt(&prev, &unit_key)) {
539 *error = "Unit keys are in wrong order";
540 return -1;
541 }
542 prev = unit_key;
543 }
544 coord.unit_pos = 0;
545 if (level != TWIG_LEVEL && item_is_extent(&coord)) {
546 *error = "extent on the wrong level";
547 return -1;
548 }
549 if (level == LEAF_LEVEL && item_is_internal(&coord)) {
550 *error = "internal item on the wrong level";
551 return -1;
552 }
553 if (level != LEAF_LEVEL &&
554 !item_is_internal(&coord) && !item_is_extent(&coord)) {
555 *error = "wrong item on the internal level";
556 return -1;
557 }
558 if (level > TWIG_LEVEL && !item_is_internal(&coord)) {
559 *error = "non-internal item on the internal level";
560 return -1;
561 }
562 #if REISER4_DEBUG
563 if (item_plugin_by_coord(&coord)->b.check
564 && item_plugin_by_coord(&coord)->b.check(&coord, error))
565 return -1;
566 #endif
567 if (i) {
568 coord_t prev_coord;
569 /* two neighboring items can not be mergeable */
570 coord_dup(&prev_coord, &coord);
571 coord_prev_item(&prev_coord);
572 if (are_items_mergeable(&prev_coord, &coord)) {
573 *error = "mergeable items in one node";
574 return -1;
575 }
576
577 }
578 }
579
580 if ((flags & REISER4_NODE_DKEYS) && !node_is_empty(node)) {
581 coord_t coord;
582 item_plugin *iplug;
583
584 coord_init_last_unit(&coord, node);
585 iplug = item_plugin_by_coord(&coord);
586 if ((item_is_extent(&coord) || item_is_tail(&coord)) &&
587 iplug->s.file.append_key != NULL) {
588 reiser4_key mkey;
589
590 iplug->s.file.append_key(&coord, &mkey);
591 set_key_offset(&mkey, get_key_offset(&mkey) - 1);
592 read_lock_dk(current_tree);
593 result = keygt(&mkey, znode_get_rd_key((znode *) node));
594 read_unlock_dk(current_tree);
595 if (result) {
596 *error = "key of rightmost item is too large";
597 return -1;
598 }
599 }
600 }
601 if (flags & REISER4_NODE_DKEYS) {
602 read_lock_tree(current_tree);
603 read_lock_dk(current_tree);
604
605 flags |= REISER4_NODE_TREE_STABLE;
606
607 if (keygt(&prev, znode_get_rd_key((znode *) node))) {
608 if (flags & REISER4_NODE_TREE_STABLE) {
609 *error = "Last key is greater than rdkey";
610 read_unlock_dk(current_tree);
611 read_unlock_tree(current_tree);
612 return -1;
613 }
614 }
615 if (keygt
616 (znode_get_ld_key((znode *) node),
617 znode_get_rd_key((znode *) node))) {
618 *error = "ldkey is greater than rdkey";
619 read_unlock_dk(current_tree);
620 read_unlock_tree(current_tree);
621 return -1;
622 }
623 if (ZF_ISSET(node, JNODE_LEFT_CONNECTED) &&
624 (node->left != NULL) &&
625 !ZF_ISSET(node->left, JNODE_HEARD_BANSHEE) &&
626 ergo(flags & REISER4_NODE_TREE_STABLE,
627 !keyeq(znode_get_rd_key(node->left),
628 znode_get_ld_key((znode *) node)))
629 && ergo(!(flags & REISER4_NODE_TREE_STABLE),
630 keygt(znode_get_rd_key(node->left),
631 znode_get_ld_key((znode *) node)))) {
632 *error = "left rdkey or ldkey is wrong";
633 read_unlock_dk(current_tree);
634 read_unlock_tree(current_tree);
635 return -1;
636 }
637 if (ZF_ISSET(node, JNODE_RIGHT_CONNECTED) &&
638 (node->right != NULL) &&
639 !ZF_ISSET(node->right, JNODE_HEARD_BANSHEE) &&
640 ergo(flags & REISER4_NODE_TREE_STABLE,
641 !keyeq(znode_get_rd_key((znode *) node),
642 znode_get_ld_key(node->right)))
643 && ergo(!(flags & REISER4_NODE_TREE_STABLE),
644 keygt(znode_get_rd_key((znode *) node),
645 znode_get_ld_key(node->right)))) {
646 *error = "rdkey or right ldkey is wrong";
647 read_unlock_dk(current_tree);
648 read_unlock_tree(current_tree);
649 return -1;
650 }
651
652 read_unlock_dk(current_tree);
653 read_unlock_tree(current_tree);
654 }
655
656 return 0;
657 }
658
659 /* plugin->u.node.parse
660 look for description of this method in plugin/node/node.h */
661 int parse_node40(znode * node /* node to parse */ )
662 {
663 node40_header *header;
664 int result;
665 d8 level;
666
667 header = node40_node_header((znode *) node);
668 result = -EIO;
669 level = nh40_get_level(header);
670 if (unlikely(((__u8) znode_get_level(node)) != level))
671 warning("nikita-494", "Wrong level found in node: %i != %i",
672 znode_get_level(node), level);
673 else if (unlikely(nh40_get_magic(header) != REISER4_NODE_MAGIC))
674 warning("nikita-495",
675 "Wrong magic in tree node: want %x, got %x",
676 REISER4_NODE_MAGIC, nh40_get_magic(header));
677 else {
678 node->nr_items = node40_num_of_items_internal(node);
679 result = 0;
680 }
681 return RETERR(result);
682 }
683
684 /* plugin->u.node.init
685 look for description of this method in plugin/node/node.h */
686 int init_node40(znode * node /* node to initialise */ )
687 {
688 node40_header *header;
689
690 assert("nikita-570", node != NULL);
691 assert("nikita-572", zdata(node) != NULL);
692
693 header = node40_node_header(node);
694 memset(header, 0, sizeof(node40_header));
695 nh40_set_free_space(header, znode_size(node) - sizeof(node40_header));
696 nh40_set_free_space_start(header, sizeof(node40_header));
697 /* sane hypothesis: 0 in CPU format is 0 in disk format */
698 /* items: 0 */
699 save_plugin_id(node_plugin_to_plugin(node->nplug),
700 &header->common_header.plugin_id);
701 nh40_set_level(header, znode_get_level(node));
702 nh40_set_magic(header, REISER4_NODE_MAGIC);
703 node->nr_items = 0;
704 nh40_set_mkfs_id(header, reiser4_mkfs_id(reiser4_get_current_sb()));
705
706 /* flags: 0 */
707 return 0;
708 }
709
710 #ifdef GUESS_EXISTS
711 int guess_node40(const znode * node /* node to guess plugin of */ )
712 {
713 node40_header *nethack;
714
715 assert("nikita-1058", node != NULL);
716 nethack = node40_node_header(node);
717 return
718 (nh40_get_magic(nethack) == REISER4_NODE_MAGIC) &&
719 (plugin_by_disk_id(znode_get_tree(node),
720 REISER4_NODE_PLUGIN_TYPE,
721 &nethack->common_header.plugin_id)->h.id ==
722 NODE40_ID);
723 }
724 #endif
725
726 /* plugin->u.node.chage_item_size
727 look for description of this method in plugin/node/node.h */
728 void change_item_size_node40(coord_t * coord, int by)
729 {
730 node40_header *nh;
731 item_header40 *ih;
732 char *item_data;
733 int item_length;
734 unsigned i;
735
736 /* make sure that @item is coord of existing item */
737 assert("vs-210", coord_is_existing_item(coord));
738
739 nh = node40_node_header(coord->node);
740
741 item_data = item_by_coord_node40(coord);
742 item_length = length_by_coord_node40(coord);
743
744 /* move item bodies */
745 ih = node40_ih_at_coord(coord);
746 memmove(item_data + item_length + by, item_data + item_length,
747 nh40_get_free_space_start(node40_node_header(coord->node)) -
748 (ih40_get_offset(ih) + item_length));
749
750 /* update offsets of moved items */
751 for (i = coord->item_pos + 1; i < nh40_get_num_items(nh); i++) {
752 ih = node40_ih_at(coord->node, i);
753 ih40_set_offset(ih, ih40_get_offset(ih) + by);
754 }
755
756 /* update node header */
757 nh40_set_free_space(nh, nh40_get_free_space(nh) - by);
758 nh40_set_free_space_start(nh, nh40_get_free_space_start(nh) + by);
759 }
760
761 static int should_notify_parent(const znode * node)
762 {
763 /* FIXME_JMACD This looks equivalent to znode_is_root(), right? -josh */
764 return !disk_addr_eq(znode_get_block(node),
765 &znode_get_tree(node)->root_block);
766 }
767
768 /* plugin->u.node.create_item
769 look for description of this method in plugin/node/node.h */
770 int
771 create_item_node40(coord_t *target, const reiser4_key *key,
772 reiser4_item_data *data, carry_plugin_info *info)
773 {
774 node40_header *nh;
775 item_header40 *ih;
776 unsigned offset;
777 unsigned i;
778
779 nh = node40_node_header(target->node);
780
781 assert("vs-212", coord_is_between_items(target));
782 /* node must have enough free space */
783 assert("vs-254",
784 free_space_node40(target->node) >=
785 data->length + sizeof(item_header40));
786 assert("vs-1410", data->length >= 0);
787
788 if (coord_set_to_right(target))
789 /* there are not items to the right of @target, so, new item
790 will be inserted after last one */
791 coord_set_item_pos(target, nh40_get_num_items(nh));
792
793 if (target->item_pos < nh40_get_num_items(nh)) {
794 /* there are items to be moved to prepare space for new
795 item */
796 ih = node40_ih_at_coord(target);
797 /* new item will start at this offset */
798 offset = ih40_get_offset(ih);
799
800 memmove(zdata(target->node) + offset + data->length,
801 zdata(target->node) + offset,
802 nh40_get_free_space_start(nh) - offset);
803 /* update headers of moved items */
804 for (i = target->item_pos; i < nh40_get_num_items(nh); i++) {
805 ih = node40_ih_at(target->node, i);
806 ih40_set_offset(ih, ih40_get_offset(ih) + data->length);
807 }
808
809 /* @ih is set to item header of the last item, move item headers */
810 memmove(ih - 1, ih,
811 sizeof(item_header40) * (nh40_get_num_items(nh) -
812 target->item_pos));
813 } else {
814 /* new item will start at this offset */
815 offset = nh40_get_free_space_start(nh);
816 }
817
818 /* make item header for the new item */
819 ih = node40_ih_at_coord(target);
820 memcpy(&ih->key, key, sizeof(reiser4_key));
821 ih40_set_offset(ih, offset);
822 save_plugin_id(item_plugin_to_plugin(data->iplug), &ih->plugin_id);
823
824 /* update node header */
825 nh40_set_free_space(nh,
826 nh40_get_free_space(nh) - data->length -
827 sizeof(item_header40));
828 nh40_set_free_space_start(nh,
829 nh40_get_free_space_start(nh) + data->length);
830 node40_set_num_items(target->node, nh, nh40_get_num_items(nh) + 1);
831
832 /* FIXME: check how does create_item work when between is set to BEFORE_UNIT */
833 target->unit_pos = 0;
834 target->between = AT_UNIT;
835 coord_clear_iplug(target);
836
837 /* initialize item */
838 if (data->iplug->b.init != NULL) {
839 data->iplug->b.init(target, NULL, data);
840 }
841 /* copy item body */
842 if (data->iplug->b.paste != NULL) {
843 data->iplug->b.paste(target, data, info);
844 } else if (data->data != NULL) {
845 if (data->user) {
846 /* AUDIT: Are we really should not check that pointer
847 from userspace was valid and data bytes were
848 available? How will we return -EFAULT of some kind
849 without this check? */
850 assert("nikita-3038", reiser4_schedulable());
851 /* copy data from user space */
852 __copy_from_user(zdata(target->node) + offset,
853 (const char __user *)data->data,
854 (unsigned)data->length);
855 } else
856 /* copy from kernel space */
857 memcpy(zdata(target->node) + offset, data->data,
858 (unsigned)data->length);
859 }
860
861 if (target->item_pos == 0) {
862 /* left delimiting key has to be updated */
863 prepare_for_update(NULL, target->node, info);
864 }
865
866 if (item_plugin_by_coord(target)->b.create_hook != NULL) {
867 item_plugin_by_coord(target)->b.create_hook(target, data->arg);
868 }
869
870 return 0;
871 }
872
873 /* plugin->u.node.update_item_key
874 look for description of this method in plugin/node/node.h */
875 void
876 update_item_key_node40(coord_t * target, const reiser4_key * key,
877 carry_plugin_info * info)
878 {
879 item_header40 *ih;
880
881 ih = node40_ih_at_coord(target);
882 memcpy(&ih->key, key, sizeof(reiser4_key));
883
884 if (target->item_pos == 0) {
885 prepare_for_update(NULL, target->node, info);
886 }
887 }
888
889 /* this bits encode cut mode */
890 #define CMODE_TAIL 1
891 #define CMODE_WHOLE 2
892 #define CMODE_HEAD 4
893
894 struct cut40_info {
895 int mode;
896 pos_in_node_t tail_removed; /* position of item which gets tail removed */
897 pos_in_node_t first_removed; /* position of first the leftmost item among items removed completely */
898 pos_in_node_t removed_count; /* number of items removed completely */
899 pos_in_node_t head_removed; /* position of item which gets head removed */
900
901 pos_in_node_t freed_space_start;
902 pos_in_node_t freed_space_end;
903 pos_in_node_t first_moved;
904 pos_in_node_t head_removed_location;
905 };
906
907 static void init_cinfo(struct cut40_info *cinfo)
908 {
909 cinfo->mode = 0;
910 cinfo->tail_removed = MAX_POS_IN_NODE;
911 cinfo->first_removed = MAX_POS_IN_NODE;
912 cinfo->removed_count = MAX_POS_IN_NODE;
913 cinfo->head_removed = MAX_POS_IN_NODE;
914 cinfo->freed_space_start = MAX_POS_IN_NODE;
915 cinfo->freed_space_end = MAX_POS_IN_NODE;
916 cinfo->first_moved = MAX_POS_IN_NODE;
917 cinfo->head_removed_location = MAX_POS_IN_NODE;
918 }
919
920 /* complete cut_node40/kill_node40 content by removing the gap created by */
921 static void compact(znode * node, struct cut40_info *cinfo)
922 {
923 node40_header *nh;
924 item_header40 *ih;
925 pos_in_node_t freed;
926 pos_in_node_t pos, nr_items;
927
928 assert("vs-1526", (cinfo->freed_space_start != MAX_POS_IN_NODE &&
929 cinfo->freed_space_end != MAX_POS_IN_NODE &&
930 cinfo->first_moved != MAX_POS_IN_NODE));
931 assert("vs-1523", cinfo->freed_space_end >= cinfo->freed_space_start);
932
933 nh = node40_node_header(node);
934 nr_items = nh40_get_num_items(nh);
935
936 /* remove gap made up by removal */
937 memmove(zdata(node) + cinfo->freed_space_start,
938 zdata(node) + cinfo->freed_space_end,
939 nh40_get_free_space_start(nh) - cinfo->freed_space_end);
940
941 /* update item headers of moved items - change their locations */
942 pos = cinfo->first_moved;
943 ih = node40_ih_at(node, pos);
944 if (cinfo->head_removed_location != MAX_POS_IN_NODE) {
945 assert("vs-1580", pos == cinfo->head_removed);
946 ih40_set_offset(ih, cinfo->head_removed_location);
947 pos++;
948 ih--;
949 }
950
951 freed = cinfo->freed_space_end - cinfo->freed_space_start;
952 for (; pos < nr_items; pos++, ih--) {
953 assert("vs-1581", ih == node40_ih_at(node, pos));
954 ih40_set_offset(ih, ih40_get_offset(ih) - freed);
955 }
956
957 /* free space start moved to right */
958 nh40_set_free_space_start(nh, nh40_get_free_space_start(nh) - freed);
959
960 if (cinfo->removed_count != MAX_POS_IN_NODE) {
961 /* number of items changed. Remove item headers of those items */
962 ih = node40_ih_at(node, nr_items - 1);
963 memmove(ih + cinfo->removed_count, ih,
964 sizeof(item_header40) * (nr_items -
965 cinfo->removed_count -
966 cinfo->first_removed));
967 freed += sizeof(item_header40) * cinfo->removed_count;
968 node40_set_num_items(node, nh, nr_items - cinfo->removed_count);
969 }
970
971 /* total amount of free space increased */
972 nh40_set_free_space(nh, nh40_get_free_space(nh) + freed);
973 }
974
975 int shrink_item_node40(coord_t * coord, int delta)
976 {
977 node40_header *nh;
978 item_header40 *ih;
979 pos_in_node_t pos;
980 pos_in_node_t nr_items;
981 char *end;
982 znode *node;
983 int off;
984
985 assert("nikita-3487", coord != NULL);
986 assert("nikita-3488", delta >= 0);
987
988 node = coord->node;
989 nh = node40_node_header(node);
990 nr_items = nh40_get_num_items(nh);
991
992 ih = node40_ih_at_coord(coord);
993 assert("nikita-3489", delta <= length_by_coord_node40(coord));
994 off = ih40_get_offset(ih) + length_by_coord_node40(coord);
995 end = zdata(node) + off;
996
997 /* remove gap made up by removal */
998 memmove(end - delta, end, nh40_get_free_space_start(nh) - off);
999
1000 /* update item headers of moved items - change their locations */
1001 pos = coord->item_pos + 1;
1002 ih = node40_ih_at(node, pos);
1003 for (; pos < nr_items; pos++, ih--) {
1004 assert("nikita-3490", ih == node40_ih_at(node, pos));
1005 ih40_set_offset(ih, ih40_get_offset(ih) - delta);
1006 }
1007
1008 /* free space start moved to left */
1009 nh40_set_free_space_start(nh, nh40_get_free_space_start(nh) - delta);
1010 /* total amount of free space increased */
1011 nh40_set_free_space(nh, nh40_get_free_space(nh) + delta);
1012 /*
1013 * This method does _not_ changes number of items. Hence, it cannot
1014 * make node empty. Also it doesn't remove items at all, which means
1015 * that no keys have to be updated either.
1016 */
1017 return 0;
1018 }
1019
1020 /* this is used by cut_node40 and kill_node40. It analyses input parameters and calculates cut mode. There are 2 types
1021 of cut. First is when a unit is removed from the middle of an item. In this case this function returns 1. All the
1022 rest fits into second case: 0 or 1 of items getting tail cut, 0 or more items removed completely and 0 or 1 item
1023 getting head cut. Function returns 0 in this case */
1024 static int
1025 parse_cut(struct cut40_info *cinfo, const struct cut_kill_params *params)
1026 {
1027 reiser4_key left_key, right_key;
1028 reiser4_key min_from_key, max_to_key;
1029 const reiser4_key *from_key, *to_key;
1030
1031 init_cinfo(cinfo);
1032
1033 /* calculate minimal key stored in first item of items to be cut (params->from) */
1034 item_key_by_coord(params->from, &min_from_key);
1035 /* and max key stored in last item of items to be cut (params->to) */
1036 max_item_key_by_coord(params->to, &max_to_key);
1037
1038 /* if cut key range is not defined in input parameters - define it using cut coord range */
1039 if (params->from_key == NULL) {
1040 assert("vs-1513", params->to_key == NULL);
1041 unit_key_by_coord(params->from, &left_key);
1042 from_key = &left_key;
1043 max_unit_key_by_coord(params->to, &right_key);
1044 to_key = &right_key;
1045 } else {
1046 from_key = params->from_key;
1047 to_key = params->to_key;
1048 }
1049
1050 if (params->from->item_pos == params->to->item_pos) {
1051 if (keylt(&min_from_key, from_key)
1052 && keylt(to_key, &max_to_key))
1053 return 1;
1054
1055 if (keygt(from_key, &min_from_key)) {
1056 /* tail of item is to be cut cut */
1057 cinfo->tail_removed = params->from->item_pos;
1058 cinfo->mode |= CMODE_TAIL;
1059 } else if (keylt(to_key, &max_to_key)) {
1060 /* head of item is to be cut */
1061 cinfo->head_removed = params->from->item_pos;
1062 cinfo->mode |= CMODE_HEAD;
1063 } else {
1064 /* item is removed completely */
1065 cinfo->first_removed = params->from->item_pos;
1066 cinfo->removed_count = 1;
1067 cinfo->mode |= CMODE_WHOLE;
1068 }
1069 } else {
1070 cinfo->first_removed = params->from->item_pos + 1;
1071 cinfo->removed_count =
1072 params->to->item_pos - params->from->item_pos - 1;
1073
1074 if (keygt(from_key, &min_from_key)) {
1075 /* first item is not cut completely */
1076 cinfo->tail_removed = params->from->item_pos;
1077 cinfo->mode |= CMODE_TAIL;
1078 } else {
1079 cinfo->first_removed--;
1080 cinfo->removed_count++;
1081 }
1082 if (keylt(to_key, &max_to_key)) {
1083 /* last item is not cut completely */
1084 cinfo->head_removed = params->to->item_pos;
1085 cinfo->mode |= CMODE_HEAD;
1086 } else {
1087 cinfo->removed_count++;
1088 }
1089 if (cinfo->removed_count)
1090 cinfo->mode |= CMODE_WHOLE;
1091 }
1092
1093 return 0;
1094 }
1095
1096 static void
1097 call_kill_hooks(znode * node, pos_in_node_t from, pos_in_node_t count,
1098 carry_kill_data * kdata)
1099 {
1100 coord_t coord;
1101 item_plugin *iplug;
1102 pos_in_node_t pos;
1103
1104 coord.node = node;
1105 coord.unit_pos = 0;
1106 coord.between = AT_UNIT;
1107 for (pos = 0; pos < count; pos++) {
1108 coord_set_item_pos(&coord, from + pos);
1109 coord.unit_pos = 0;
1110 coord.between = AT_UNIT;
1111 iplug = item_plugin_by_coord(&coord);
1112 if (iplug->b.kill_hook) {
1113 iplug->b.kill_hook(&coord, 0, coord_num_units(&coord),
1114 kdata);
1115 }
1116 }
1117 }
1118
1119 /* this is used to kill item partially */
1120 static pos_in_node_t
1121 kill_units(coord_t * coord, pos_in_node_t from, pos_in_node_t to, void *data,
1122 reiser4_key * smallest_removed, reiser4_key * new_first_key)
1123 {
1124 struct carry_kill_data *kdata;
1125 item_plugin *iplug;
1126
1127 kdata = data;
1128 iplug = item_plugin_by_coord(coord);
1129
1130 assert("vs-1524", iplug->b.kill_units);
1131 return iplug->b.kill_units(coord, from, to, kdata, smallest_removed,
1132 new_first_key);
1133 }
1134
1135 /* call item plugin to cut tail of file */
1136 static pos_in_node_t
1137 kill_tail(coord_t * coord, void *data, reiser4_key * smallest_removed)
1138 {
1139 struct carry_kill_data *kdata;
1140 pos_in_node_t to;
1141
1142 kdata = data;
1143 to = coord_last_unit_pos(coord);
1144 return kill_units(coord, coord->unit_pos, to, kdata, smallest_removed,
1145 NULL);
1146 }
1147
1148 /* call item plugin to cut head of item */
1149 static pos_in_node_t
1150 kill_head(coord_t * coord, void *data, reiser4_key * smallest_removed,
1151 reiser4_key * new_first_key)
1152 {
1153 return kill_units(coord, 0, coord->unit_pos, data, smallest_removed,
1154 new_first_key);
1155 }
1156
1157 /* this is used to cut item partially */
1158 static pos_in_node_t
1159 cut_units(coord_t * coord, pos_in_node_t from, pos_in_node_t to, void *data,
1160 reiser4_key * smallest_removed, reiser4_key * new_first_key)
1161 {
1162 carry_cut_data *cdata;
1163 item_plugin *iplug;
1164
1165 cdata = data;
1166 iplug = item_plugin_by_coord(coord);
1167 assert("vs-302", iplug->b.cut_units);
1168 return iplug->b.cut_units(coord, from, to, cdata, smallest_removed,
1169 new_first_key);
1170 }
1171
1172 /* call item plugin to cut tail of file */
1173 static pos_in_node_t
1174 cut_tail(coord_t * coord, void *data, reiser4_key * smallest_removed)
1175 {
1176 carry_cut_data *cdata;
1177 pos_in_node_t to;
1178
1179 cdata = data;
1180 to = coord_last_unit_pos(cdata->params.from);
1181 return cut_units(coord, coord->unit_pos, to, data, smallest_removed, NULL);
1182 }
1183
1184 /* call item plugin to cut head of item */
1185 static pos_in_node_t
1186 cut_head(coord_t * coord, void *data, reiser4_key * smallest_removed,
1187 reiser4_key * new_first_key)
1188 {
1189 return cut_units(coord, 0, coord->unit_pos, data, smallest_removed,
1190 new_first_key);
1191 }
1192
1193 /* this returns 1 of key of first item changed, 0 - if it did not */
1194 static int
1195 prepare_for_compact(struct cut40_info *cinfo,
1196 const struct cut_kill_params *params, int is_cut,
1197 void *data, carry_plugin_info * info)
1198 {
1199 znode *node;
1200 item_header40 *ih;
1201 pos_in_node_t freed;
1202 pos_in_node_t item_pos;
1203 coord_t coord;
1204 reiser4_key new_first_key;
1205 pos_in_node_t(*kill_units_f) (coord_t *, pos_in_node_t, pos_in_node_t,
1206 void *, reiser4_key *, reiser4_key *);
1207 pos_in_node_t(*kill_tail_f) (coord_t *, void *, reiser4_key *);
1208 pos_in_node_t(*kill_head_f) (coord_t *, void *, reiser4_key *,
1209 reiser4_key *);
1210 int retval;
1211
1212 retval = 0;
1213
1214 node = params->from->node;
1215
1216 assert("vs-184", node == params->to->node);
1217 assert("vs-312", !node_is_empty(node));
1218 assert("vs-297",
1219 coord_compare(params->from, params->to) != COORD_CMP_ON_RIGHT);
1220
1221 if (is_cut) {
1222 kill_units_f = cut_units;
1223 kill_tail_f = cut_tail;
1224 kill_head_f = cut_head;
1225 } else {
1226 kill_units_f = kill_units;
1227 kill_tail_f = kill_tail;
1228 kill_head_f = kill_head;
1229 }
1230
1231 if (parse_cut(cinfo, params) == 1) {
1232 /* cut from the middle of item */
1233 freed =
1234 kill_units_f(params->from, params->from->unit_pos,
1235 params->to->unit_pos, data,
1236 params->smallest_removed, NULL);
1237
1238 item_pos = params->from->item_pos;
1239 ih = node40_ih_at(node, item_pos);
1240 cinfo->freed_space_start =
1241 ih40_get_offset(ih) + node40_item_length(node,
1242 item_pos) - freed;
1243 cinfo->freed_space_end = cinfo->freed_space_start + freed;
1244 cinfo->first_moved = item_pos + 1;
1245 } else {
1246 assert("vs-1521", (cinfo->tail_removed != MAX_POS_IN_NODE ||
1247 cinfo->first_removed != MAX_POS_IN_NODE ||
1248 cinfo->head_removed != MAX_POS_IN_NODE));
1249
1250 switch (cinfo->mode) {
1251 case CMODE_TAIL:
1252 /* one item gets cut partially from its end */
1253 assert("vs-1562",
1254 cinfo->tail_removed == params->from->item_pos);
1255
1256 freed =
1257 kill_tail_f(params->from, data,
1258 params->smallest_removed);
1259
1260 item_pos = cinfo->tail_removed;
1261 ih = node40_ih_at(node, item_pos);
1262 cinfo->freed_space_start =
1263 ih40_get_offset(ih) + node40_item_length(node,
1264 item_pos) -
1265 freed;
1266 cinfo->freed_space_end =
1267 cinfo->freed_space_start + freed;
1268 cinfo->first_moved = cinfo->tail_removed + 1;
1269 break;
1270
1271 case CMODE_WHOLE:
1272 /* one or more items get removed completely */
1273 assert("vs-1563",
1274 cinfo->first_removed == params->from->item_pos);
1275 assert("vs-1564", cinfo->removed_count > 0
1276 && cinfo->removed_count != MAX_POS_IN_NODE);
1277
1278 /* call kill hook for all items removed completely */
1279 if (is_cut == 0)
1280 call_kill_hooks(node, cinfo->first_removed,
1281 cinfo->removed_count, data);
1282
1283 item_pos = cinfo->first_removed;
1284 ih = node40_ih_at(node, item_pos);
1285
1286 if (params->smallest_removed)
1287 memcpy(params->smallest_removed, &ih->key,
1288 sizeof(reiser4_key));
1289
1290 cinfo->freed_space_start = ih40_get_offset(ih);
1291
1292 item_pos += (cinfo->removed_count - 1);
1293 ih -= (cinfo->removed_count - 1);
1294 cinfo->freed_space_end =
1295 ih40_get_offset(ih) + node40_item_length(node,
1296 item_pos);
1297 cinfo->first_moved = item_pos + 1;
1298 if (cinfo->first_removed == 0)
1299 /* key of first item of the node changes */
1300 retval = 1;
1301 break;
1302
1303 case CMODE_HEAD:
1304 /* one item gets cut partially from its head */
1305 assert("vs-1565",
1306 cinfo->head_removed == params->from->item_pos);
1307
1308 freed =
1309 kill_head_f(params->to, data,
1310 params->smallest_removed,
1311 &new_first_key);
1312
1313 item_pos = cinfo->head_removed;
1314 ih = node40_ih_at(node, item_pos);
1315 cinfo->freed_space_start = ih40_get_offset(ih);
1316 cinfo->freed_space_end = ih40_get_offset(ih) + freed;
1317 cinfo->first_moved = cinfo->head_removed + 1;
1318
1319 /* item head is removed, therefore, item key changed */
1320 coord.node = node;
1321 coord_set_item_pos(&coord, item_pos);
1322 coord.unit_pos = 0;
1323 coord.between = AT_UNIT;
1324 update_item_key_node40(&coord, &new_first_key, NULL);
1325 if (item_pos == 0)
1326 /* key of first item of the node changes */
1327 retval = 1;
1328 break;
1329
1330 case CMODE_TAIL | CMODE_WHOLE:
1331 /* one item gets cut from its end and one or more items get removed completely */
1332 assert("vs-1566",
1333 cinfo->tail_removed == params->from->item_pos);
1334 assert("vs-1567",
1335 cinfo->first_removed == cinfo->tail_removed + 1);
1336 assert("vs-1564", cinfo->removed_count > 0
1337 && cinfo->removed_count != MAX_POS_IN_NODE);
1338
1339 freed =
1340 kill_tail_f(params->from, data,
1341 params->smallest_removed);
1342
1343 item_pos = cinfo->tail_removed;
1344 ih = node40_ih_at(node, item_pos);
1345 cinfo->freed_space_start =
1346 ih40_get_offset(ih) + node40_item_length(node,
1347 item_pos) -
1348 freed;
1349
1350 /* call kill hook for all items removed completely */
1351 if (is_cut == 0)
1352 call_kill_hooks(node, cinfo->first_removed,
1353 cinfo->removed_count, data);
1354
1355 item_pos += cinfo->removed_count;
1356 ih -= cinfo->removed_count;
1357 cinfo->freed_space_end =
1358 ih40_get_offset(ih) + node40_item_length(node,
1359 item_pos);
1360 cinfo->first_moved = item_pos + 1;
1361 break;
1362
1363 case CMODE_WHOLE | CMODE_HEAD:
1364 /* one or more items get removed completely and one item gets cut partially from its head */
1365 assert("vs-1568",
1366 cinfo->first_removed == params->from->item_pos);
1367 assert("vs-1564", cinfo->removed_count > 0
1368 && cinfo->removed_count != MAX_POS_IN_NODE);
1369 assert("vs-1569",
1370 cinfo->head_removed ==
1371 cinfo->first_removed + cinfo->removed_count);
1372
1373 /* call kill hook for all items removed completely */
1374 if (is_cut == 0)
1375 call_kill_hooks(node, cinfo->first_removed,
1376 cinfo->removed_count, data);
1377
1378 item_pos = cinfo->first_removed;
1379 ih = node40_ih_at(node, item_pos);
1380
1381 if (params->smallest_removed)
1382 memcpy(params->smallest_removed, &ih->key,
1383 sizeof(reiser4_key));
1384
1385 freed =
1386 kill_head_f(params->to, data, NULL, &new_first_key);
1387
1388 cinfo->freed_space_start = ih40_get_offset(ih);
1389
1390 ih = node40_ih_at(node, cinfo->head_removed);
1391 /* this is the most complex case. Item which got head removed and items which are to be moved
1392 intact change their location differently. */
1393 cinfo->freed_space_end = ih40_get_offset(ih) + freed;
1394 cinfo->first_moved = cinfo->head_removed;
1395 cinfo->head_removed_location = cinfo->freed_space_start;
1396
1397 /* item head is removed, therefore, item key changed */
1398 coord.node = node;
1399 coord_set_item_pos(&coord, cinfo->head_removed);
1400 coord.unit_pos = 0;
1401 coord.between = AT_UNIT;
1402 update_item_key_node40(&coord, &new_first_key, NULL);
1403
1404 assert("vs-1579", cinfo->first_removed == 0);
1405 /* key of first item of the node changes */
1406 retval = 1;
1407 break;
1408
1409 case CMODE_TAIL | CMODE_HEAD:
1410 /* one item get cut from its end and its neighbor gets cut from its tail */
1411 impossible("vs-1576", "this can not happen currently");
1412 break;
1413
1414 case CMODE_TAIL | CMODE_WHOLE | CMODE_HEAD:
1415 impossible("vs-1577", "this can not happen currently");
1416 break;
1417 default:
1418 impossible("vs-1578", "unexpected cut mode");
1419 break;
1420 }
1421 }
1422 return retval;
1423 }
1424
1425 /* plugin->u.node.kill
1426 return value is number of items removed completely */
1427 int kill_node40(struct carry_kill_data *kdata, carry_plugin_info * info)
1428 {
1429 znode *node;
1430 struct cut40_info cinfo;
1431 int first_key_changed;
1432
1433 node = kdata->params.from->node;
1434
1435 first_key_changed =
1436 prepare_for_compact(&cinfo, &kdata->params, 0 /* not cut */ , kdata,
1437 info);
1438 compact(node, &cinfo);
1439
1440 if (info) {
1441 /* it is not called by node40_shift, so we have to take care
1442 of changes on upper levels */
1443 if (node_is_empty(node)
1444 && !(kdata->flags & DELETE_RETAIN_EMPTY))
1445 /* all contents of node is deleted */
1446 prepare_removal_node40(node, info);
1447 else if (first_key_changed) {
1448 prepare_for_update(NULL, node, info);
1449 }
1450 }
1451
1452 coord_clear_iplug(kdata->params.from);
1453 coord_clear_iplug(kdata->params.to);
1454
1455 znode_make_dirty(node);
1456 return cinfo.removed_count == MAX_POS_IN_NODE ? 0 : cinfo.removed_count;
1457 }
1458
1459 /* plugin->u.node.cut
1460 return value is number of items removed completely */
1461 int cut_node40(struct carry_cut_data *cdata, carry_plugin_info * info)
1462 {
1463 znode *node;
1464 struct cut40_info cinfo;
1465 int first_key_changed;
1466
1467 node = cdata->params.from->node;
1468
1469 first_key_changed =
1470 prepare_for_compact(&cinfo, &cdata->params, 1 /* not cut */ , cdata,
1471 info);
1472 compact(node, &cinfo);
1473
1474 if (info) {
1475 /* it is not called by node40_shift, so we have to take care
1476 of changes on upper levels */
1477 if (node_is_empty(node))
1478 /* all contents of node is deleted */
1479 prepare_removal_node40(node, info);
1480 else if (first_key_changed) {
1481 prepare_for_update(NULL, node, info);
1482 }
1483 }
1484
1485 coord_clear_iplug(cdata->params.from);
1486 coord_clear_iplug(cdata->params.to);
1487
1488 znode_make_dirty(node);
1489 return cinfo.removed_count == MAX_POS_IN_NODE ? 0 : cinfo.removed_count;
1490 }
1491
1492 /* this structure is used by shift method of node40 plugin */
1493 struct shift_params {
1494 shift_direction pend; /* when @pend == append - we are shifting to
1495 left, when @pend == prepend - to right */
1496 coord_t wish_stop; /* when shifting to left this is last unit we
1497 want shifted, when shifting to right - this
1498 is set to unit we want to start shifting
1499 from */
1500 znode *target;
1501 int everything; /* it is set to 1 if everything we have to shift is
1502 shifted, 0 - otherwise */
1503
1504 /* FIXME-VS: get rid of read_stop */
1505
1506 /* these are set by estimate_shift */
1507 coord_t real_stop; /* this will be set to last unit which will be
1508 really shifted */
1509
1510 /* coordinate in source node before operation of unit which becomes
1511 first after shift to left of last after shift to right */
1512 union {
1513 coord_t future_first;
1514 coord_t future_last;
1515 } u;
1516
1517 unsigned merging_units; /* number of units of first item which have to
1518 be merged with last item of target node */
1519 unsigned merging_bytes; /* number of bytes in those units */
1520
1521 unsigned entire; /* items shifted in their entirety */
1522 unsigned entire_bytes; /* number of bytes in those items */
1523
1524 unsigned part_units; /* number of units of partially copied item */
1525 unsigned part_bytes; /* number of bytes in those units */
1526
1527 unsigned shift_bytes; /* total number of bytes in items shifted (item
1528 headers not included) */
1529
1530 };
1531
1532 static int item_creation_overhead(coord_t *item)
1533 {
1534 return node_plugin_by_coord(item)->item_overhead(item->node, NULL);
1535 }
1536
1537 /* how many units are there in @source starting from source->unit_pos
1538 but not further than @stop_coord */
1539 static int
1540 wanted_units(coord_t *source, coord_t *stop_coord, shift_direction pend)
1541 {
1542 if (pend == SHIFT_LEFT) {
1543 assert("vs-181", source->unit_pos == 0);
1544 } else {
1545 assert("vs-182",
1546 source->unit_pos == coord_last_unit_pos(source));
1547 }
1548
1549 if (source->item_pos != stop_coord->item_pos) {
1550 /* @source and @stop_coord are different items */
1551 return coord_last_unit_pos(source) + 1;
1552 }
1553
1554 if (pend == SHIFT_LEFT) {
1555 return stop_coord->unit_pos + 1;
1556 } else {
1557 return source->unit_pos - stop_coord->unit_pos + 1;
1558 }
1559 }
1560
1561 /* this calculates what can be copied from @shift->wish_stop.node to
1562 @shift->target */
1563 static void
1564 estimate_shift(struct shift_params *shift, const reiser4_context * ctx)
1565 {
1566 unsigned target_free_space, size;
1567 pos_in_node_t stop_item; /* item which estimating should not consider */
1568 unsigned want; /* number of units of item we want shifted */
1569 coord_t source; /* item being estimated */
1570 item_plugin *iplug;
1571
1572 /* shifting to left/right starts from first/last units of
1573 @shift->wish_stop.node */
1574 if (shift->pend == SHIFT_LEFT) {
1575 coord_init_first_unit(&source, shift->wish_stop.node);
1576 } else {
1577 coord_init_last_unit(&source, shift->wish_stop.node);
1578 }
1579 shift->real_stop = source;
1580
1581 /* free space in target node and number of items in source */
1582 target_free_space = znode_free_space(shift->target);
1583
1584 shift->everything = 0;
1585 if (!node_is_empty(shift->target)) {
1586 /* target node is not empty, check for boundary items
1587 mergeability */
1588 coord_t to;
1589
1590 /* item we try to merge @source with */
1591 if (shift->pend == SHIFT_LEFT) {
1592 coord_init_last_unit(&to, shift->target);
1593 } else {
1594 coord_init_first_unit(&to, shift->target);
1595 }
1596
1597 if ((shift->pend == SHIFT_LEFT) ? are_items_mergeable(&to,
1598 &source) :
1599 are_items_mergeable(&source, &to)) {
1600 /* how many units of @source do we want to merge to
1601 item @to */
1602 want =
1603 wanted_units(&source, &shift->wish_stop,
1604 shift->pend);
1605
1606 /* how many units of @source we can merge to item
1607 @to */
1608 iplug = item_plugin_by_coord(&source);
1609 if (iplug->b.can_shift != NULL)
1610 shift->merging_units =
1611 iplug->b.can_shift(target_free_space,
1612 &source, shift->target,
1613 shift->pend, &size,
1614 want);
1615 else {
1616 shift->merging_units = 0;
1617 size = 0;
1618 }
1619 shift->merging_bytes = size;
1620 shift->shift_bytes += size;
1621 /* update stop coord to be set to last unit of @source
1622 we can merge to @target */
1623 if (shift->merging_units)
1624 /* at least one unit can be shifted */
1625 shift->real_stop.unit_pos =
1626 (shift->merging_units - source.unit_pos -
1627 1) * shift->pend;
1628 else {
1629 /* nothing can be shifted */
1630 if (shift->pend == SHIFT_LEFT)
1631 coord_init_before_first_item(&shift->
1632 real_stop,
1633 source.
1634 node);
1635 else
1636 coord_init_after_last_item(&shift->
1637 real_stop,
1638 source.node);
1639 }
1640 assert("nikita-2081", shift->real_stop.unit_pos + 1);
1641
1642 if (shift->merging_units != want) {
1643 /* we could not copy as many as we want, so,
1644 there is no reason for estimating any
1645 longer */
1646 return;
1647 }
1648
1649 target_free_space -= size;
1650 coord_add_item_pos(&source, shift->pend);
1651 }
1652 }
1653
1654 /* number of item nothing of which we want to shift */
1655 stop_item = shift->wish_stop.item_pos + shift->pend;
1656
1657 /* calculate how many items can be copied into given free
1658 space as whole */
1659 for (; source.item_pos != stop_item;
1660 coord_add_item_pos(&source, shift->pend)) {
1661 if (shift->pend == SHIFT_RIGHT)
1662 source.unit_pos = coord_last_unit_pos(&source);
1663
1664 /* how many units of @source do we want to copy */
1665 want = wanted_units(&source, &shift->wish_stop, shift->pend);
1666
1667 if (want == coord_last_unit_pos(&source) + 1) {
1668 /* we want this item to be copied entirely */
1669 size =
1670 item_length_by_coord(&source) +
1671 item_creation_overhead(&source);
1672 if (size <= target_free_space) {
1673 /* item fits into target node as whole */
1674 target_free_space -= size;
1675 shift->shift_bytes +=
1676 size - item_creation_overhead(&source);
1677 shift->entire_bytes +=
1678 size - item_creation_overhead(&source);
1679 shift->entire++;
1680
1681 /* update shift->real_stop coord to be set to
1682 last unit of @source we can merge to
1683 @target */
1684 shift->real_stop = source;
1685 if (shift->pend == SHIFT_LEFT)
1686 shift->real_stop.unit_pos =
1687 coord_last_unit_pos(&shift->
1688 real_stop);
1689 else
1690 shift->real_stop.unit_pos = 0;
1691 continue;
1692 }
1693 }
1694
1695 /* we reach here only for an item which does not fit into
1696 target node in its entirety. This item may be either
1697 partially shifted, or not shifted at all. We will have to
1698 create new item in target node, so decrease amout of free
1699 space by an item creation overhead. We can reach here also
1700 if stop coord is in this item */
1701 if (target_free_space >=
1702 (unsigned)item_creation_overhead(&source)) {
1703 target_free_space -= item_creation_overhead(&source);
1704 iplug = item_plugin_by_coord(&source);
1705 if (iplug->b.can_shift) {
1706 shift->part_units = iplug->b.can_shift(target_free_space,
1707 &source,
1708 NULL, /* target */
1709 shift->pend,
1710 &size,
1711 want);
1712 } else {
1713 target_free_space = 0;
1714 shift->part_units = 0;
1715 size = 0;
1716 }
1717 } else {
1718 target_free_space = 0;
1719 shift->part_units = 0;
1720 size = 0;
1721 }
1722 shift->part_bytes = size;
1723 shift->shift_bytes += size;
1724
1725 /* set @shift->real_stop to last unit of @source we can merge
1726 to @shift->target */
1727 if (shift->part_units) {
1728 shift->real_stop = source;
1729 shift->real_stop.unit_pos =
1730 (shift->part_units - source.unit_pos -
1731 1) * shift->pend;
1732 assert("nikita-2082", shift->real_stop.unit_pos + 1);
1733 }
1734
1735 if (want != shift->part_units)
1736 /* not everything wanted were shifted */
1737 return;
1738 break;
1739 }
1740
1741 shift->everything = 1;
1742 }
1743
1744 static void
1745 copy_units(coord_t * target, coord_t * source, unsigned from, unsigned count,
1746 shift_direction dir, unsigned free_space)
1747 {
1748 item_plugin *iplug;
1749
1750 assert("nikita-1463", target != NULL);
1751 assert("nikita-1464", source != NULL);
1752 assert("nikita-1465", from + count <= coord_num_units(source));
1753
1754 iplug = item_plugin_by_coord(source);
1755 assert("nikita-1468", iplug == item_plugin_by_coord(target));
1756 iplug->b.copy_units(target, source, from, count, dir, free_space);
1757
1758 if (dir == SHIFT_RIGHT) {
1759 /* FIXME-VS: this looks not necessary. update_item_key was
1760 called already by copy_units method */
1761 reiser4_key split_key;
1762
1763 assert("nikita-1469", target->unit_pos == 0);
1764
1765 unit_key_by_coord(target, &split_key);
1766 node_plugin_by_coord(target)->update_item_key(target,
1767 &split_key, NULL);
1768 }
1769 }
1770
1771 /* copy part of @shift->real_stop.node starting either from its beginning or
1772 from its end and ending at @shift->real_stop to either the end or the
1773 beginning of @shift->target */
1774 static void copy(struct shift_params *shift)
1775 {
1776 node40_header *nh;
1777 coord_t from;
1778 coord_t to;
1779 item_header40 *from_ih, *to_ih;
1780 int free_space_start;
1781 int new_items;
1782 unsigned old_items;
1783 int old_offset;
1784 unsigned i;
1785
1786 nh = node40_node_header(shift->target);
1787 free_space_start = nh40_get_free_space_start(nh);
1788 old_items = nh40_get_num_items(nh);
1789 new_items = shift->entire + (shift->part_units ? 1 : 0);
1790 assert("vs-185",
1791 shift->shift_bytes ==
1792 shift->merging_bytes + shift->entire_bytes + shift->part_bytes);
1793
1794 from = shift->wish_stop;
1795
1796 coord_init_first_unit(&to, shift->target);
1797
1798 /* NOTE:NIKITA->VS not sure what I am doing: shift->target is empty,
1799 hence to.between is set to EMPTY_NODE above. Looks like we want it
1800 to be AT_UNIT.
1801
1802 Oh, wonders of ->betweeness...
1803
1804 */
1805 to.between = AT_UNIT;
1806
1807 if (shift->pend == SHIFT_LEFT) {
1808 /* copying to left */
1809
1810 coord_set_item_pos(&from, 0);
1811 from_ih = node40_ih_at(from.node, 0);
1812
1813 coord_set_item_pos(&to,
1814 node40_num_of_items_internal(to.node) - 1);
1815 if (shift->merging_units) {
1816 /* expand last item, so that plugin methods will see
1817 correct data */
1818 free_space_start += shift->merging_bytes;
1819 nh40_set_free_space_start(nh,
1820 (unsigned)free_space_start);
1821 nh40_set_free_space(nh,
1822 nh40_get_free_space(nh) -
1823 shift->merging_bytes);
1824
1825 /* appending last item of @target */
1826 copy_units(&to, &from, 0, /* starting from 0-th unit */
1827 shift->merging_units, SHIFT_LEFT,
1828 shift->merging_bytes);
1829 coord_inc_item_pos(&from);
1830 from_ih--;
1831 coord_inc_item_pos(&to);
1832 }
1833
1834 to_ih = node40_ih_at(shift->target, old_items);
1835 if (shift->entire) {
1836 /* copy @entire items entirely */
1837
1838 /* copy item headers */
1839 memcpy(to_ih - shift->entire + 1,
1840 from_ih - shift->entire + 1,
1841 shift->entire * sizeof(item_header40));
1842 /* update item header offset */
1843 old_offset = ih40_get_offset(from_ih);
1844 /* AUDIT: Looks like if we calculate old_offset + free_space_start here instead of just old_offset, we can perform one "add" operation less per each iteration */
1845 for (i = 0; i < shift->entire; i++, to_ih--, from_ih--)
1846 ih40_set_offset(to_ih,
1847 ih40_get_offset(from_ih) -
1848 old_offset + free_space_start);
1849
1850 /* copy item bodies */
1851 memcpy(zdata(shift->target) + free_space_start, zdata(from.node) + old_offset, /*ih40_get_offset (from_ih), */
1852 shift->entire_bytes);
1853
1854 coord_add_item_pos(&from, (int)shift->entire);
1855 coord_add_item_pos(&to, (int)shift->entire);
1856 }
1857
1858 nh40_set_free_space_start(nh,
1859 free_space_start +
1860 shift->shift_bytes -
1861 shift->merging_bytes);
1862 nh40_set_free_space(nh,
1863 nh40_get_free_space(nh) -
1864 (shift->shift_bytes - shift->merging_bytes +
1865 sizeof(item_header40) * new_items));
1866
1867 /* update node header */
1868 node40_set_num_items(shift->target, nh, old_items + new_items);
1869 assert("vs-170",
1870 nh40_get_free_space(nh) < znode_size(shift->target));
1871
1872 if (shift->part_units) {
1873 /* copy heading part (@part units) of @source item as
1874 a new item into @target->node */
1875
1876 /* copy item header of partially copied item */
1877 coord_set_item_pos(&to,
1878 node40_num_of_items_internal(to.node)
1879 - 1);
1880 memcpy(to_ih, from_ih, sizeof(item_header40));
1881 ih40_set_offset(to_ih,
1882 nh40_get_free_space_start(nh) -
1883 shift->part_bytes);
1884 if (item_plugin_by_coord(&to)->b.init)
1885 item_plugin_by_coord(&to)->b.init(&to, &from,
1886 NULL);
1887 copy_units(&to, &from, 0, shift->part_units, SHIFT_LEFT,
1888 shift->part_bytes);
1889 }
1890
1891 } else {
1892 /* copying to right */
1893
1894 coord_set_item_pos(&from,
1895 node40_num_of_items_internal(from.node) - 1);
1896 from_ih = node40_ih_at_coord(&from);
1897
1898 coord_set_item_pos(&to, 0);
1899
1900 /* prepare space for new items */
1901 memmove(zdata(to.node) + sizeof(node40_header) +
1902 shift->shift_bytes,
1903 zdata(to.node) + sizeof(node40_header),
1904 free_space_start - sizeof(node40_header));
1905 /* update item headers of moved items */
1906 to_ih = node40_ih_at(to.node, 0);
1907 /* first item gets @merging_bytes longer. free space appears
1908 at its beginning */
1909 if (!node_is_empty(to.node))
1910 ih40_set_offset(to_ih,
1911 ih40_get_offset(to_ih) +
1912 shift->shift_bytes -
1913 shift->merging_bytes);
1914
1915 for (i = 1; i < old_items; i++)
1916 ih40_set_offset(to_ih - i,
1917 ih40_get_offset(to_ih - i) +
1918 shift->shift_bytes);
1919
1920 /* move item headers to make space for new items */
1921 memmove(to_ih - old_items + 1 - new_items,
1922 to_ih - old_items + 1,
1923 sizeof(item_header40) * old_items);
1924 to_ih -= (new_items - 1);
1925
1926 nh40_set_free_space_start(nh,
1927 free_space_start +
1928 shift->shift_bytes);
1929 nh40_set_free_space(nh,
1930 nh40_get_free_space(nh) -
1931 (shift->shift_bytes +
1932 sizeof(item_header40) * new_items));
1933
1934 /* update node header */
1935 node40_set_num_items(shift->target, nh, old_items + new_items);
1936 assert("vs-170",
1937 nh40_get_free_space(nh) < znode_size(shift->target));
1938
1939 if (shift->merging_units) {
1940 coord_add_item_pos(&to, new_items);
1941 to.unit_pos = 0;
1942 to.between = AT_UNIT;
1943 /* prepend first item of @to */
1944 copy_units(&to, &from,
1945 coord_last_unit_pos(&from) -
1946 shift->merging_units + 1,
1947 shift->merging_units, SHIFT_RIGHT,
1948 shift->merging_bytes);
1949 coord_dec_item_pos(&from);
1950 from_ih++;
1951 }
1952
1953 if (shift->entire) {
1954 /* copy @entire items entirely */
1955
1956 /* copy item headers */
1957 memcpy(to_ih, from_ih,
1958 shift->entire * sizeof(item_header40));
1959
1960 /* update item header offset */
1961 old_offset =
1962 ih40_get_offset(from_ih + shift->entire - 1);
1963 /* AUDIT: old_offset + sizeof (node40_header) + shift->part_bytes calculation can be taken off the loop. */
1964 for (i = 0; i < shift->entire; i++, to_ih++, from_ih++)
1965 ih40_set_offset(to_ih,
1966 ih40_get_offset(from_ih) -
1967 old_offset +
1968 sizeof(node40_header) +
1969 shift->part_bytes);
1970 /* copy item bodies */
1971 coord_add_item_pos(&from, -(int)(shift->entire - 1));
1972 memcpy(zdata(to.node) + sizeof(node40_header) +
1973 shift->part_bytes, item_by_coord_node40(&from),
1974 shift->entire_bytes);
1975 coord_dec_item_pos(&from);
1976 }
1977
1978 if (shift->part_units) {
1979 coord_set_item_pos(&to, 0);
1980 to.unit_pos = 0;
1981 to.between = AT_UNIT;
1982 /* copy heading part (@part units) of @source item as
1983 a new item into @target->node */
1984
1985 /* copy item header of partially copied item */
1986 memcpy(to_ih, from_ih, sizeof(item_header40));
1987 ih40_set_offset(to_ih, sizeof(node40_header));
1988 if (item_plugin_by_coord(&to)->b.init)
1989 item_plugin_by_coord(&to)->b.init(&to, &from,
1990 NULL);
1991 copy_units(&to, &from,
1992 coord_last_unit_pos(&from) -
1993 shift->part_units + 1, shift->part_units,
1994 SHIFT_RIGHT, shift->part_bytes);
1995 }
1996 }
1997 }
1998
1999 /* remove everything either before or after @fact_stop. Number of items
2000 removed completely is returned */
2001 static int delete_copied(struct shift_params *shift)
2002 {
2003 coord_t from;
2004 coord_t to;
2005 struct carry_cut_data cdata;
2006
2007 if (shift->pend == SHIFT_LEFT) {
2008 /* we were shifting to left, remove everything from the
2009 beginning of @shift->wish_stop->node upto
2010 @shift->wish_stop */
2011 coord_init_first_unit(&from, shift->real_stop.node);
2012 to = shift->real_stop;
2013
2014 /* store old coordinate of unit which will be first after
2015 shift to left */
2016 shift->u.future_first = to;
2017 coord_next_unit(&shift->u.future_first);
2018 } else {
2019 /* we were shifting to right, remove everything from
2020 @shift->stop_coord upto to end of
2021 @shift->stop_coord->node */
2022 from = shift->real_stop;
2023 coord_init_last_unit(&to, from.node);
2024
2025 /* store old coordinate of unit which will be last after
2026 shift to right */
2027 shift->u.future_last = from;
2028 coord_prev_unit(&shift->u.future_last);
2029 }
2030
2031 cdata.params.from = &from;
2032 cdata.params.to = &to;
2033 cdata.params.from_key = NULL;
2034 cdata.params.to_key = NULL;
2035 cdata.params.smallest_removed = NULL;
2036 return cut_node40(&cdata, NULL);
2037 }
2038
2039 /* something was moved between @left and @right. Add carry operation to @info
2040 list to have carry to update delimiting key between them */
2041 static int
2042 prepare_for_update(znode * left, znode * right, carry_plugin_info * info)
2043 {
2044 carry_op *op;
2045 carry_node *cn;
2046
2047 if (info == NULL)
2048 /* nowhere to send operation to. */
2049 return 0;
2050
2051 if (!should_notify_parent(right))
2052 return 0;
2053
2054 op = node_post_carry(info, COP_UPDATE, right, 1);
2055 if (IS_ERR(op) || op == NULL)
2056 return op ? PTR_ERR(op) : -EIO;
2057
2058 if (left != NULL) {
2059 carry_node *reference;
2060
2061 if (info->doing)
2062 reference = insert_carry_node(info->doing,
2063 info->todo, left);
2064 else
2065 reference = op->node;
2066 assert("nikita-2992", reference != NULL);
2067 cn = reiser4_add_carry(info->todo, POOLO_BEFORE, reference);
2068 if (IS_ERR(cn))
2069 return PTR_ERR(cn);
2070 cn->parent = 1;
2071 cn->node = left;
2072 if (ZF_ISSET(left, JNODE_ORPHAN))
2073 cn->left_before = 1;
2074 op->u.update.left = cn;
2075 } else
2076 op->u.update.left = NULL;
2077 return 0;
2078 }
2079
2080 /* plugin->u.node.prepare_removal
2081 to delete a pointer to @empty from the tree add corresponding carry
2082 operation (delete) to @info list */
2083 int prepare_removal_node40(znode * empty, carry_plugin_info * info)
2084 {
2085 carry_op *op;
2086 reiser4_tree *tree;
2087
2088 if (!should_notify_parent(empty))
2089 return 0;
2090 /* already on a road to Styx */
2091 if (ZF_ISSET(empty, JNODE_HEARD_BANSHEE))
2092 return 0;
2093 op = node_post_carry(info, COP_DELETE, empty, 1);
2094 if (IS_ERR(op) || op == NULL)
2095 return RETERR(op ? PTR_ERR(op) : -EIO);
2096
2097 op->u.delete.child = NULL;
2098 op->u.delete.flags = 0;
2099
2100 /* fare thee well */
2101 tree = znode_get_tree(empty);
2102 read_lock_tree(tree);
2103 write_lock_dk(tree);
2104 znode_set_ld_key(empty, znode_get_rd_key(empty));
2105 if (znode_is_left_connected(empty) && empty->left)
2106 znode_set_rd_key(empty->left, znode_get_rd_key(empty));
2107 write_unlock_dk(tree);
2108 read_unlock_tree(tree);
2109
2110 ZF_SET(empty, JNODE_HEARD_BANSHEE);
2111 return 0;
2112 }
2113
2114 /* something were shifted from @insert_coord->node to @shift->target, update
2115 @insert_coord correspondingly */
2116 static void
2117 adjust_coord(coord_t * insert_coord, struct shift_params *shift, int removed,
2118 int including_insert_coord)
2119 {
2120 /* item plugin was invalidated by shifting */
2121 coord_clear_iplug(insert_coord);
2122
2123 if (node_is_empty(shift->wish_stop.node)) {
2124 assert("vs-242", shift->everything);
2125 if (including_insert_coord) {
2126 if (shift->pend == SHIFT_RIGHT) {
2127 /* set @insert_coord before first unit of
2128 @shift->target node */
2129 coord_init_before_first_item(insert_coord,
2130 shift->target);
2131 } else {
2132 /* set @insert_coord after last in target node */
2133 coord_init_after_last_item(insert_coord,
2134 shift->target);
2135 }
2136 } else {
2137 /* set @insert_coord inside of empty node. There is
2138 only one possible coord within an empty
2139 node. init_first_unit will set that coord */
2140 coord_init_first_unit(insert_coord,
2141 shift->wish_stop.node);
2142 }
2143 return;
2144 }
2145
2146 if (shift->pend == SHIFT_RIGHT) {
2147 /* there was shifting to right */
2148 if (shift->everything) {
2149 /* everything wanted was shifted */
2150 if (including_insert_coord) {
2151 /* @insert_coord is set before first unit of
2152 @to node */
2153 coord_init_before_first_item(insert_coord,
2154 shift->target);
2155 insert_coord->between = BEFORE_UNIT;
2156 } else {
2157 /* @insert_coord is set after last unit of
2158 @insert->node */
2159 coord_init_last_unit(insert_coord,
2160 shift->wish_stop.node);
2161 insert_coord->between = AFTER_UNIT;
2162 }
2163 }
2164 return;
2165 }
2166
2167 /* there was shifting to left */
2168 if (shift->everything) {
2169 /* everything wanted was shifted */
2170 if (including_insert_coord) {
2171 /* @insert_coord is set after last unit in @to node */
2172 coord_init_after_last_item(insert_coord, shift->target);
2173 } else {
2174 /* @insert_coord is set before first unit in the same
2175 node */
2176 coord_init_before_first_item(insert_coord,
2177 shift->wish_stop.node);
2178 }
2179 return;
2180 }
2181
2182 /* FIXME-VS: the code below is complicated because with between ==
2183 AFTER_ITEM unit_pos is set to 0 */
2184
2185 if (!removed) {
2186 /* no items were shifted entirely */
2187 assert("vs-195", shift->merging_units == 0
2188 || shift->part_units == 0);
2189
2190 if (shift->real_stop.item_pos == insert_coord->item_pos) {
2191 if (shift->merging_units) {
2192 if (insert_coord->between == AFTER_UNIT) {
2193 assert("nikita-1441",
2194 insert_coord->unit_pos >=
2195 shift->merging_units);
2196 insert_coord->unit_pos -=
2197 shift->merging_units;
2198 } else if (insert_coord->between == BEFORE_UNIT) {
2199 assert("nikita-2090",
2200 insert_coord->unit_pos >
2201 shift->merging_units);
2202 insert_coord->unit_pos -=
2203 shift->merging_units;
2204 }
2205
2206 assert("nikita-2083",
2207 insert_coord->unit_pos + 1);
2208 } else {
2209 if (insert_coord->between == AFTER_UNIT) {
2210 assert("nikita-1442",
2211 insert_coord->unit_pos >=
2212 shift->part_units);
2213 insert_coord->unit_pos -=
2214 shift->part_units;
2215 } else if (insert_coord->between == BEFORE_UNIT) {
2216 assert("nikita-2089",
2217 insert_coord->unit_pos >
2218 shift->part_units);
2219 insert_coord->unit_pos -=
2220 shift->part_units;
2221 }
2222
2223 assert("nikita-2084",
2224 insert_coord->unit_pos + 1);
2225 }
2226 }
2227 return;
2228 }
2229
2230 /* we shifted to left and there was no enough space for everything */
2231 switch (insert_coord->between) {
2232 case AFTER_UNIT:
2233 case BEFORE_UNIT:
2234 if (shift->real_stop.item_pos == insert_coord->item_pos)
2235 insert_coord->unit_pos -= shift->part_units;
2236 case AFTER_ITEM:
2237 coord_add_item_pos(insert_coord, -removed);
2238 break;
2239 default:
2240 impossible("nikita-2087", "not ready");
2241 }
2242 assert("nikita-2085", insert_coord->unit_pos + 1);
2243 }
2244
2245 static int call_shift_hooks(struct shift_params *shift)
2246 {
2247 unsigned i, shifted;
2248 coord_t coord;
2249 item_plugin *iplug;
2250
2251 assert("vs-275", !node_is_empty(shift->target));
2252
2253 /* number of items shift touches */
2254 shifted =
2255 shift->entire + (shift->merging_units ? 1 : 0) +
2256 (shift->part_units ? 1 : 0);
2257
2258 if (shift->pend == SHIFT_LEFT) {
2259 /* moved items are at the end */
2260 coord_init_last_unit(&coord, shift->target);
2261 coord.unit_pos = 0;
2262
2263 assert("vs-279", shift->pend == 1);
2264 for (i = 0; i < shifted; i++) {
2265 unsigned from, count;
2266
2267 iplug = item_plugin_by_coord(&coord);
2268 if (i == 0 && shift->part_units) {
2269 assert("vs-277",
2270 coord_num_units(&coord) ==
2271 shift->part_units);
2272 count = shift->part_units;
2273 from = 0;
2274 } else if (i == shifted - 1 && shift->merging_units) {
2275 count = shift->merging_units;
2276 from = coord_num_units(&coord) - count;
2277 } else {
2278 count = coord_num_units(&coord);
2279 from = 0;
2280 }
2281
2282 if (iplug->b.shift_hook) {
2283 iplug->b.shift_hook(&coord, from, count,
2284 shift->wish_stop.node);
2285 }
2286 coord_add_item_pos(&coord, -shift->pend);
2287 }
2288 } else {
2289 /* moved items are at the beginning */
2290 coord_init_first_unit(&coord, shift->target);
2291
2292 assert("vs-278", shift->pend == -1);
2293 for (i = 0; i < shifted; i++) {
2294 unsigned from, count;
2295
2296 iplug = item_plugin_by_coord(&coord);
2297 if (i == 0 && shift->part_units) {
2298 assert("vs-277",
2299 coord_num_units(&coord) ==
2300 shift->part_units);
2301 count = coord_num_units(&coord);
2302 from = 0;
2303 } else if (i == shifted - 1 && shift->merging_units) {
2304 count = shift->merging_units;
2305 from = 0;
2306 } else {
2307 count = coord_num_units(&coord);
2308 from = 0;
2309 }
2310
2311 if (iplug->b.shift_hook) {
2312 iplug->b.shift_hook(&coord, from, count,
2313 shift->wish_stop.node);
2314 }
2315 coord_add_item_pos(&coord, -shift->pend);
2316 }
2317 }
2318
2319 return 0;
2320 }
2321
2322 /* shift to left is completed. Return 1 if unit @old was moved to left neighbor */
2323 static int
2324 unit_moved_left(const struct shift_params *shift, const coord_t * old)
2325 {
2326 assert("vs-944", shift->real_stop.node == old->node);
2327
2328 if (shift->real_stop.item_pos < old->item_pos)
2329 return 0;
2330 if (shift->real_stop.item_pos == old->item_pos) {
2331 if (shift->real_stop.unit_pos < old->unit_pos)
2332 return 0;
2333 }
2334 return 1;
2335 }
2336
2337 /* shift to right is completed. Return 1 if unit @old was moved to right
2338 neighbor */
2339 static int
2340 unit_moved_right(const struct shift_params *shift, const coord_t * old)
2341 {
2342 assert("vs-944", shift->real_stop.node == old->node);
2343
2344 if (shift->real_stop.item_pos > old->item_pos)
2345 return 0;
2346 if (shift->real_stop.item_pos == old->item_pos) {
2347 if (shift->real_stop.unit_pos > old->unit_pos)
2348 return 0;
2349 }
2350 return 1;
2351 }
2352
2353 /* coord @old was set in node from which shift was performed. What was shifted
2354 is stored in @shift. Update @old correspondingly to performed shift */
2355 static coord_t *adjust_coord2(const struct shift_params *shift,
2356 const coord_t * old, coord_t * new)
2357 {
2358 coord_clear_iplug(new);
2359 new->between = old->between;
2360
2361 coord_clear_iplug(new);
2362 if (old->node == shift->target) {
2363 if (shift->pend == SHIFT_LEFT) {
2364 /* coord which is set inside of left neighbor does not
2365 change during shift to left */
2366 coord_dup(new, old);
2367 return new;
2368 }
2369 new->node = old->node;
2370 coord_set_item_pos(new,
2371 old->item_pos + shift->entire +
2372 (shift->part_units ? 1 : 0));
2373 new->unit_pos = old->unit_pos;
2374 if (old->item_pos == 0 && shift->merging_units)
2375 new->unit_pos += shift->merging_units;
2376 return new;
2377 }
2378
2379 assert("vs-977", old->node == shift->wish_stop.node);
2380 if (shift->pend == SHIFT_LEFT) {
2381 if (unit_moved_left(shift, old)) {
2382 /* unit @old moved to left neighbor. Calculate its
2383 coordinate there */
2384 new->node = shift->target;
2385 coord_set_item_pos(new,
2386 node_num_items(shift->target) -
2387 shift->entire -
2388 (shift->part_units ? 1 : 0) +
2389 old->item_pos);
2390
2391 new->unit_pos = old->unit_pos;
2392 if (shift->merging_units) {
2393 coord_dec_item_pos(new);
2394 if (old->item_pos == 0) {
2395 /* unit_pos only changes if item got
2396 merged */
2397 new->unit_pos =
2398 coord_num_units(new) -
2399 (shift->merging_units -
2400 old->unit_pos);
2401 }
2402 }
2403 } else {
2404 /* unit @old did not move to left neighbor.
2405
2406 Use _nocheck, because @old is outside of its node.
2407 */
2408 coord_dup_nocheck(new, old);
2409 coord_add_item_pos(new,
2410 -shift->u.future_first.item_pos);
2411 if (new->item_pos == 0)
2412 new->unit_pos -= shift->u.future_first.unit_pos;
2413 }
2414 } else {
2415 if (unit_moved_right(shift, old)) {
2416 /* unit @old moved to right neighbor */
2417 new->node = shift->target;
2418 coord_set_item_pos(new,
2419 old->item_pos -
2420 shift->real_stop.item_pos);
2421 if (new->item_pos == 0) {
2422 /* unit @old might change unit pos */
2423 coord_set_item_pos(new,
2424 old->unit_pos -
2425 shift->real_stop.unit_pos);
2426 }
2427 } else {
2428 /* unit @old did not move to right neighbor, therefore
2429 it did not change */
2430 coord_dup(new, old);
2431 }
2432 }
2433 coord_set_iplug(new, item_plugin_by_coord(new));
2434 return new;
2435 }
2436
2437 /* this is called when shift is completed (something of source node is copied
2438 to target and deleted in source) to update all taps set in current
2439 context */
2440 static void update_taps(const struct shift_params *shift)
2441 {
2442 tap_t *tap;
2443 coord_t new;
2444
2445 for_all_taps(tap) {
2446 /* update only taps set to nodes participating in shift */
2447 if (tap->coord->node == shift->wish_stop.node
2448 || tap->coord->node == shift->target)
2449 tap_to_coord(tap,
2450 adjust_coord2(shift, tap->coord, &new));
2451 }
2452 }
2453
2454 #if REISER4_DEBUG
2455
2456 struct shift_check {
2457 reiser4_key key;
2458 __u16 plugin_id;
2459 union {
2460 __u64 bytes;
2461 __u64 entries;
2462 void *unused;
2463 } u;
2464 };
2465
2466 void *shift_check_prepare(const znode * left, const znode * right)
2467 {
2468 pos_in_node_t i, nr_items;
2469 int mergeable;
2470 struct shift_check *data;
2471 item_header40 *ih;
2472
2473 if (node_is_empty(left) || node_is_empty(right))
2474 mergeable = 0;
2475 else {
2476 coord_t l, r;
2477
2478 coord_init_last_unit(&l, left);
2479 coord_init_first_unit(&r, right);
2480 mergeable = are_items_mergeable(&l, &r);
2481 }
2482 nr_items =
2483 node40_num_of_items_internal(left) +
2484 node40_num_of_items_internal(right) - (mergeable ? 1 : 0);
2485 data =
2486 kmalloc(sizeof(struct shift_check) * nr_items,
2487 reiser4_ctx_gfp_mask_get());
2488 if (data != NULL) {
2489 coord_t coord;
2490 pos_in_node_t item_pos;
2491
2492 coord_init_first_unit(&coord, left);
2493 i = 0;
2494
2495 for (item_pos = 0;
2496 item_pos < node40_num_of_items_internal(left);
2497 item_pos++) {
2498
2499 coord_set_item_pos(&coord, item_pos);
2500 ih = node40_ih_at_coord(&coord);
2501
2502 data[i].key = ih->key;
2503 data[i].plugin_id = le16_to_cpu(get_unaligned(&ih->plugin_id));
2504 switch (data[i].plugin_id) {
2505 case CTAIL_ID:
2506 case FORMATTING_ID:
2507 data[i].u.bytes = coord_num_units(&coord);
2508 break;
2509 case EXTENT_POINTER_ID:
2510 data[i].u.bytes =
2511 reiser4_extent_size(&coord,
2512 coord_num_units(&coord));
2513 break;
2514 case COMPOUND_DIR_ID:
2515 data[i].u.entries = coord_num_units(&coord);
2516 break;
2517 default:
2518 data[i].u.unused = NULL;
2519 break;
2520 }
2521 i++;
2522 }
2523
2524 coord_init_first_unit(&coord, right);
2525
2526 if (mergeable) {
2527 assert("vs-1609", i != 0);
2528
2529 ih = node40_ih_at_coord(&coord);
2530
2531 assert("vs-1589",
2532 data[i - 1].plugin_id ==
2533 le16_to_cpu(get_unaligned(&ih->plugin_id)));
2534 switch (data[i - 1].plugin_id) {
2535 case CTAIL_ID:
2536 case FORMATTING_ID:
2537 data[i - 1].u.bytes += coord_num_units(&coord);
2538 break;
2539 case EXTENT_POINTER_ID:
2540 data[i - 1].u.bytes +=
2541 reiser4_extent_size(&coord,
2542 coord_num_units(&coord));
2543 break;
2544 case COMPOUND_DIR_ID:
2545 data[i - 1].u.entries +=
2546 coord_num_units(&coord);
2547 break;
2548 default:
2549 impossible("vs-1605", "wrong mergeable item");
2550 break;
2551 }
2552 item_pos = 1;
2553 } else
2554 item_pos = 0;
2555 for (; item_pos < node40_num_of_items_internal(right);
2556 item_pos++) {
2557
2558 assert("vs-1604", i < nr_items);
2559 coord_set_item_pos(&coord, item_pos);
2560 ih = node40_ih_at_coord(&coord);
2561
2562 data[i].key = ih->key;
2563 data[i].plugin_id = le16_to_cpu(get_unaligned(&ih->plugin_id));
2564 switch (data[i].plugin_id) {
2565 case CTAIL_ID:
2566 case FORMATTING_ID:
2567 data[i].u.bytes = coord_num_units(&coord);
2568 break;
2569 case EXTENT_POINTER_ID:
2570 data[i].u.bytes =
2571 reiser4_extent_size(&coord,
2572 coord_num_units(&coord));
2573 break;
2574 case COMPOUND_DIR_ID:
2575 data[i].u.entries = coord_num_units(&coord);
2576 break;
2577 default:
2578 data[i].u.unused = NULL;
2579 break;
2580 }
2581 i++;
2582 }
2583 assert("vs-1606", i == nr_items);
2584 }
2585 return data;
2586 }
2587
2588 void shift_check(void *vp, const znode * left, const znode * right)
2589 {
2590 pos_in_node_t i, nr_items;
2591 coord_t coord;
2592 __u64 last_bytes;
2593 int mergeable;
2594 item_header40 *ih;
2595 pos_in_node_t item_pos;
2596 struct shift_check *data;
2597
2598 data = (struct shift_check *)vp;
2599
2600 if (data == NULL)
2601 return;
2602
2603 if (node_is_empty(left) || node_is_empty(right))
2604 mergeable = 0;
2605 else {
2606 coord_t l, r;
2607
2608 coord_init_last_unit(&l, left);
2609 coord_init_first_unit(&r, right);
2610 mergeable = are_items_mergeable(&l, &r);
2611 }
2612
2613 nr_items =
2614 node40_num_of_items_internal(left) +
2615 node40_num_of_items_internal(right) - (mergeable ? 1 : 0);
2616
2617 i = 0;
2618 last_bytes = 0;
2619
2620 coord_init_first_unit(&coord, left);
2621
2622 for (item_pos = 0; item_pos < node40_num_of_items_internal(left);
2623 item_pos++) {
2624
2625 coord_set_item_pos(&coord, item_pos);
2626 ih = node40_ih_at_coord(&coord);
2627
2628 assert("vs-1611", i == item_pos);
2629 assert("vs-1590", keyeq(&ih->key, &data[i].key));
2630 assert("vs-1591",
2631 le16_to_cpu(get_unaligned(&ih->plugin_id)) == data[i].plugin_id);
2632 if ((i < (node40_num_of_items_internal(left) - 1))
2633 || !mergeable) {
2634 switch (data[i].plugin_id) {
2635 case CTAIL_ID:
2636 case FORMATTING_ID:
2637 assert("vs-1592",
2638 data[i].u.bytes ==
2639 coord_num_units(&coord));
2640 break;
2641 case EXTENT_POINTER_ID:
2642 assert("vs-1593",
2643 data[i].u.bytes ==
2644 reiser4_extent_size(&coord,
2645 coord_num_units
2646 (&coord)));
2647 break;
2648 case COMPOUND_DIR_ID:
2649 assert("vs-1594",
2650 data[i].u.entries ==
2651 coord_num_units(&coord));
2652 break;
2653 default:
2654 break;
2655 }
2656 }
2657 if (item_pos == (node40_num_of_items_internal(left) - 1)
2658 && mergeable) {
2659 switch (data[i].plugin_id) {
2660 case CTAIL_ID:
2661 case FORMATTING_ID:
2662 last_bytes = coord_num_units(&coord);
2663 break;
2664 case EXTENT_POINTER_ID:
2665 last_bytes =
2666 reiser4_extent_size(&coord,
2667 coord_num_units(&coord));
2668 break;
2669 case COMPOUND_DIR_ID:
2670 last_bytes = coord_num_units(&coord);
2671 break;
2672 default:
2673 impossible("vs-1595", "wrong mergeable item");
2674 break;
2675 }
2676 }
2677 i++;
2678 }
2679
2680 coord_init_first_unit(&coord, right);
2681 if (mergeable) {
2682 ih = node40_ih_at_coord(&coord);
2683
2684 assert("vs-1589",
2685 data[i - 1].plugin_id == le16_to_cpu(get_unaligned(&ih->plugin_id)));
2686 assert("vs-1608", last_bytes != 0);
2687 switch (data[i - 1].plugin_id) {
2688 case CTAIL_ID:
2689 case FORMATTING_ID:
2690 assert("vs-1596",
2691 data[i - 1].u.bytes ==
2692 last_bytes + coord_num_units(&coord));
2693 break;
2694
2695 case EXTENT_POINTER_ID:
2696 assert("vs-1597",
2697 data[i - 1].u.bytes ==
2698 last_bytes + reiser4_extent_size(&coord,
2699 coord_num_units
2700 (&coord)));
2701 break;
2702
2703 case COMPOUND_DIR_ID:
2704 assert("vs-1598",
2705 data[i - 1].u.bytes ==
2706 last_bytes + coord_num_units(&coord));
2707 break;
2708 default:
2709 impossible("vs-1599", "wrong mergeable item");
2710 break;
2711 }
2712 item_pos = 1;
2713 } else
2714 item_pos = 0;
2715
2716 for (; item_pos < node40_num_of_items_internal(right); item_pos++) {
2717
2718 coord_set_item_pos(&coord, item_pos);
2719 ih = node40_ih_at_coord(&coord);
2720
2721 assert("vs-1612", keyeq(&ih->key, &data[i].key));
2722 assert("vs-1613",
2723 le16_to_cpu(get_unaligned(&ih->plugin_id)) == data[i].plugin_id);
2724 switch (data[i].plugin_id) {
2725 case CTAIL_ID:
2726 case FORMATTING_ID:
2727 assert("vs-1600",
2728 data[i].u.bytes == coord_num_units(&coord));
2729 break;
2730 case EXTENT_POINTER_ID:
2731 assert("vs-1601",
2732 data[i].u.bytes ==
2733 reiser4_extent_size(&coord,
2734 coord_num_units
2735 (&coord)));
2736 break;
2737 case COMPOUND_DIR_ID:
2738 assert("vs-1602",
2739 data[i].u.entries == coord_num_units(&coord));
2740 break;
2741 default:
2742 break;
2743 }
2744 i++;
2745 }
2746
2747 assert("vs-1603", i == nr_items);
2748 kfree(data);
2749 }
2750
2751 #endif
2752
2753 /* plugin->u.node.shift
2754 look for description of this method in plugin/node/node.h */
2755 int shift_node40(coord_t * from, znode * to, shift_direction pend, int delete_child, /* if @from->node becomes empty - it will be
2756 deleted from the tree if this is set to 1 */
2757 int including_stop_coord, carry_plugin_info * info)
2758 {
2759 struct shift_params shift;
2760 int result;
2761 znode *left, *right;
2762 znode *source;
2763 int target_empty;
2764
2765 assert("nikita-2161", coord_check(from));
2766
2767 memset(&shift, 0, sizeof(shift));
2768 shift.pend = pend;
2769 shift.wish_stop = *from;
2770 shift.target = to;
2771
2772 assert("nikita-1473", znode_is_write_locked(from->node));
2773 assert("nikita-1474", znode_is_write_locked(to));
2774
2775 source = from->node;
2776
2777 /* set @shift.wish_stop to rightmost/leftmost unit among units we want
2778 shifted */
2779 if (pend == SHIFT_LEFT) {
2780 result = coord_set_to_left(&shift.wish_stop);
2781 left = to;
2782 right = from->node;
2783 } else {
2784 result = coord_set_to_right(&shift.wish_stop);
2785 left = from->node;
2786 right = to;
2787 }
2788
2789 if (result) {
2790 /* move insertion coord even if there is nothing to move */
2791 if (including_stop_coord) {
2792 /* move insertion coord (@from) */
2793 if (pend == SHIFT_LEFT) {
2794 /* after last item in target node */
2795 coord_init_after_last_item(from, to);
2796 } else {
2797 /* before first item in target node */
2798 coord_init_before_first_item(from, to);
2799 }
2800 }
2801
2802 if (delete_child && node_is_empty(shift.wish_stop.node))
2803 result =
2804 prepare_removal_node40(shift.wish_stop.node, info);
2805 else
2806 result = 0;
2807 /* there is nothing to shift */
2808 assert("nikita-2078", coord_check(from));
2809 return result;
2810 }
2811
2812 target_empty = node_is_empty(to);
2813
2814 /* when first node plugin with item body compression is implemented,
2815 this must be changed to call node specific plugin */
2816
2817 /* shift->stop_coord is updated to last unit which really will be
2818 shifted */
2819 estimate_shift(&shift, get_current_context());
2820 if (!shift.shift_bytes) {
2821 /* we could not shift anything */
2822 assert("nikita-2079", coord_check(from));
2823 return 0;
2824 }
2825
2826 copy(&shift);
2827
2828 /* result value of this is important. It is used by adjust_coord below */
2829 result = delete_copied(&shift);
2830
2831 assert("vs-1610", result >= 0);
2832 assert("vs-1471",
2833 ((reiser4_context *) current->journal_info)->magic ==
2834 context_magic);
2835
2836 /* item which has been moved from one node to another might want to do
2837 something on that event. This can be done by item's shift_hook
2838 method, which will be now called for every moved items */
2839 call_shift_hooks(&shift);
2840
2841 assert("vs-1472",
2842 ((reiser4_context *) current->journal_info)->magic ==
2843 context_magic);
2844
2845 update_taps(&shift);
2846
2847 assert("vs-1473",
2848 ((reiser4_context *) current->journal_info)->magic ==
2849 context_magic);
2850
2851 /* adjust @from pointer in accordance with @including_stop_coord flag
2852 and amount of data which was really shifted */
2853 adjust_coord(from, &shift, result, including_stop_coord);
2854
2855 if (target_empty)
2856 /*
2857 * items were shifted into empty node. Update delimiting key.
2858 */
2859 result = prepare_for_update(NULL, left, info);
2860
2861 /* add update operation to @info, which is the list of operations to
2862 be performed on a higher level */
2863 result = prepare_for_update(left, right, info);
2864 if (!result && node_is_empty(source) && delete_child) {
2865 /* all contents of @from->node is moved to @to and @from->node
2866 has to be removed from the tree, so, on higher level we
2867 will be removing the pointer to node @from->node */
2868 result = prepare_removal_node40(source, info);
2869 }
2870 assert("nikita-2080", coord_check(from));
2871 return result ? result : (int)shift.shift_bytes;
2872 }
2873
2874 /* plugin->u.node.fast_insert()
2875 look for description of this method in plugin/node/node.h */
2876 int fast_insert_node40(const coord_t * coord UNUSED_ARG /* node to query */ )
2877 {
2878 return 1;
2879 }
2880
2881 /* plugin->u.node.fast_paste()
2882 look for description of this method in plugin/node/node.h */
2883 int fast_paste_node40(const coord_t * coord UNUSED_ARG /* node to query */ )
2884 {
2885 return 1;
2886 }
2887
2888 /* plugin->u.node.fast_cut()
2889 look for description of this method in plugin/node/node.h */
2890 int fast_cut_node40(const coord_t * coord UNUSED_ARG /* node to query */ )
2891 {
2892 return 1;
2893 }
2894
2895 /* plugin->u.node.modify - not defined */
2896
2897 /* plugin->u.node.max_item_size */
2898 int max_item_size_node40(void)
2899 {
2900 return reiser4_get_current_sb()->s_blocksize - sizeof(node40_header) -
2901 sizeof(item_header40);
2902 }
2903
2904 /* plugin->u.node.set_item_plugin */
2905 int set_item_plugin_node40(coord_t *coord, item_id id)
2906 {
2907 item_header40 *ih;
2908
2909 ih = node40_ih_at_coord(coord);
2910 put_unaligned(cpu_to_le16(id), &ih->plugin_id);
2911 coord->iplugid = id;
2912 return 0;
2913 }
2914
2915 /*
2916 Local variables:
2917 c-indentation-style: "K&R"
2918 mode-name: "LC"
2919 c-basic-offset: 8
2920 tab-width: 8
2921 fill-column: 120
2922 scroll-step: 1
2923 End:
2924 */
Linux -mm trees (mirror)