File: /usr/src/linux/fs/reiserfs/stree.c
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5 /*
6 * Written by Anatoly P. Pinchuk pap@namesys.botik.ru
7 * Programm System Institute
8 * Pereslavl-Zalessky Russia
9 */
10
11 /*
12 * This file contains functions dealing with S+tree
13 *
14 * B_IS_IN_TREE
15 * copy_short_key
16 * copy_item_head
17 * comp_short_keys
18 * comp_keys
19 * comp_cpu_keys
20 * comp_short_le_keys
21 * comp_short_cpu_keys
22 * cpu_key2cpu_key
23 * le_key2cpu_key
24 * comp_le_keys
25 * bin_search
26 * get_lkey
27 * get_rkey
28 * key_in_buffer
29 * decrement_bcount
30 * decrement_counters_in_path
31 * reiserfs_check_path
32 * pathrelse_and_restore
33 * pathrelse
34 * search_by_key_reada
35 * search_by_key
36 * search_for_position_by_key
37 * comp_items
38 * prepare_for_direct_item
39 * prepare_for_direntry_item
40 * prepare_for_delete_or_cut
41 * calc_deleted_bytes_number
42 * init_tb_struct
43 * padd_item
44 * reiserfs_delete_item
45 * reiserfs_delete_solid_item
46 * reiserfs_delete_object
47 * maybe_indirect_to_direct
48 * indirect_to_direct_roll_back
49 * reiserfs_cut_from_item
50 * truncate_directory
51 * reiserfs_do_truncate
52 * reiserfs_paste_into_item
53 * reiserfs_insert_item
54 */
55
56 #include <linux/config.h>
57 #include <linux/sched.h>
58 #include <linux/string.h>
59 #include <linux/locks.h>
60 #include <linux/pagemap.h>
61 #include <linux/reiserfs_fs.h>
62 #include <linux/smp_lock.h>
63
64 /* Does the buffer contain a disk block which is in the tree. */
65 inline int B_IS_IN_TREE (struct buffer_head * p_s_bh)
66 {
67
68 #ifdef CONFIG_REISERFS_CHECK
69
70 if ( B_LEVEL (p_s_bh) > MAX_HEIGHT ) {
71 reiserfs_panic(0, "PAP-1010: B_IS_IN_TREE: block (%b) has too big level (%z)",
72 p_s_bh, p_s_bh);
73 }
74 #endif
75
76 return ( B_LEVEL (p_s_bh) != FREE_LEVEL );
77 }
78
79
80
81
82 inline void copy_short_key (void * to, void * from)
83 {
84 memcpy (to, from, SHORT_KEY_SIZE);
85 }
86
87 //
88 // to gets item head in le form
89 //
90 inline void copy_item_head(void * p_v_to, void * p_v_from)
91 {
92 memcpy (p_v_to, p_v_from, IH_SIZE);
93 }
94
95
96 /* k1 is pointer to on-disk structure which is stored in little-endian
97 form. k2 is pointer to cpu variable. For key of items of the same
98 object this returns 0.
99 Returns: -1 if key1 < key2
100 0 if key1 == key2
101 1 if key1 > key2 */
102 inline int comp_short_keys (struct key * le_key, struct cpu_key * cpu_key)
103 {
104 __u32 * p_s_le_u32, * p_s_cpu_u32;
105 int n_key_length = REISERFS_SHORT_KEY_LEN;
106
107 p_s_le_u32 = (__u32 *)le_key;
108 p_s_cpu_u32 = (__u32 *)cpu_key;
109 for( ; n_key_length--; ++p_s_le_u32, ++p_s_cpu_u32 ) {
110 if ( le32_to_cpu (*p_s_le_u32) < *p_s_cpu_u32 )
111 return -1;
112 if ( le32_to_cpu (*p_s_le_u32) > *p_s_cpu_u32 )
113 return 1;
114 }
115
116 return 0;
117 }
118
119
120 /* k1 is pointer to on-disk structure which is stored in little-endian
121 form. k2 is pointer to cpu variable.
122 Compare keys using all 4 key fields.
123 Returns: -1 if key1 < key2 0
124 if key1 = key2 1 if key1 > key2 */
125 inline int comp_keys (struct key * le_key, struct cpu_key * cpu_key)
126 {
127 int retval;
128
129 retval = comp_short_keys (le_key, cpu_key);
130 if (retval)
131 return retval;
132 if (le_key_k_offset (cpu_key->version, le_key) < cpu_key_k_offset (cpu_key))
133 return -1;
134 if (le_key_k_offset (cpu_key->version, le_key) > cpu_key_k_offset (cpu_key))
135 return 1;
136
137 if (cpu_key->key_length == 3)
138 return 0;
139
140 /* this part is needed only when tail conversion is in progress */
141 if (le_key_k_type (cpu_key->version, le_key) < cpu_key_k_type (cpu_key))
142 return -1;
143
144 if (le_key_k_type (cpu_key->version, le_key) > cpu_key_k_type (cpu_key))
145 return 1;
146
147 return 0;
148 }
149
150
151 //
152 // FIXME: not used yet
153 //
154 inline int comp_cpu_keys (struct cpu_key * key1, struct cpu_key * key2)
155 {
156 if (key1->on_disk_key.k_dir_id < key2->on_disk_key.k_dir_id)
157 return -1;
158 if (key1->on_disk_key.k_dir_id > key2->on_disk_key.k_dir_id)
159 return 1;
160
161 if (key1->on_disk_key.k_objectid < key2->on_disk_key.k_objectid)
162 return -1;
163 if (key1->on_disk_key.k_objectid > key2->on_disk_key.k_objectid)
164 return 1;
165
166 if (cpu_key_k_offset (key1) < cpu_key_k_offset (key2))
167 return -1;
168 if (cpu_key_k_offset (key1) > cpu_key_k_offset (key2))
169 return 1;
170
171 reiserfs_warning ("comp_cpu_keys: type are compared for %k and %k\n",
172 key1, key2);
173
174 if (cpu_key_k_type (key1) < cpu_key_k_type (key2))
175 return -1;
176 if (cpu_key_k_type (key1) > cpu_key_k_type (key2))
177 return 1;
178 return 0;
179 }
180
181 inline int comp_short_le_keys (struct key * key1, struct key * key2)
182 {
183 __u32 * p_s_1_u32, * p_s_2_u32;
184 int n_key_length = REISERFS_SHORT_KEY_LEN;
185
186 p_s_1_u32 = (__u32 *)key1;
187 p_s_2_u32 = (__u32 *)key2;
188 for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
189 if ( le32_to_cpu (*p_s_1_u32) < le32_to_cpu (*p_s_2_u32) )
190 return -1;
191 if ( le32_to_cpu (*p_s_1_u32) > le32_to_cpu (*p_s_2_u32) )
192 return 1;
193 }
194 return 0;
195 }
196
197 inline int comp_short_cpu_keys (struct cpu_key * key1,
198 struct cpu_key * key2)
199 {
200 __u32 * p_s_1_u32, * p_s_2_u32;
201 int n_key_length = REISERFS_SHORT_KEY_LEN;
202
203 p_s_1_u32 = (__u32 *)key1;
204 p_s_2_u32 = (__u32 *)key2;
205
206 for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
207 if ( *p_s_1_u32 < *p_s_2_u32 )
208 return -1;
209 if ( *p_s_1_u32 > *p_s_2_u32 )
210 return 1;
211 }
212 return 0;
213 }
214
215
216
217 inline void cpu_key2cpu_key (struct cpu_key * to, struct cpu_key * from)
218 {
219 memcpy (to, from, sizeof (struct cpu_key));
220 }
221
222
223 inline void le_key2cpu_key (struct cpu_key * to, struct key * from)
224 {
225 to->on_disk_key.k_dir_id = le32_to_cpu (from->k_dir_id);
226 to->on_disk_key.k_objectid = le32_to_cpu (from->k_objectid);
227
228 // find out version of the key
229 to->version = le_key_version (from);
230 if (to->version == ITEM_VERSION_1) {
231 to->on_disk_key.u.k_offset_v1.k_offset = le32_to_cpu (from->u.k_offset_v1.k_offset);
232 to->on_disk_key.u.k_offset_v1.k_uniqueness = le32_to_cpu (from->u.k_offset_v1.k_uniqueness);
233 } else {
234 to->on_disk_key.u.k_offset_v2.k_offset = le64_to_cpu (from->u.k_offset_v2.k_offset);
235 to->on_disk_key.u.k_offset_v2.k_type = le16_to_cpu (from->u.k_offset_v2.k_type);
236 }
237 }
238
239
240
241 // this does not say which one is bigger, it only returns 1 if keys
242 // are not equal, 0 otherwise
243 inline int comp_le_keys (struct key * k1, struct key * k2)
244 {
245 return memcmp (k1, k2, sizeof (struct key));
246 }
247
248 /**************************************************************************
249 * Binary search toolkit function *
250 * Search for an item in the array by the item key *
251 * Returns: 1 if found, 0 if not found; *
252 * *p_n_pos = number of the searched element if found, else the *
253 * number of the first element that is larger than p_v_key. *
254 **************************************************************************/
255 /* For those not familiar with binary search: n_lbound is the leftmost item that it
256 could be, n_rbound the rightmost item that it could be. We examine the item
257 halfway between n_lbound and n_rbound, and that tells us either that we can increase
258 n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
259 there are no possible items, and we have not found it. With each examination we
260 cut the number of possible items it could be by one more than half rounded down,
261 or we find it. */
262 inline int bin_search (
263 void * p_v_key, /* Key to search for. */
264 void * p_v_base, /* First item in the array. */
265 int p_n_num, /* Number of items in the array. */
266 int p_n_width, /* Item size in the array.
267 searched. Lest the reader be
268 confused, note that this is crafted
269 as a general function, and when it
270 is applied specifically to the array
271 of item headers in a node, p_n_width
272 is actually the item header size not
273 the item size. */
274 int * p_n_pos /* Number of the searched for element. */
275 ) {
276 int n_rbound, n_lbound, n_j;
277
278 for ( n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0))/2; n_lbound <= n_rbound; n_j = (n_rbound + n_lbound)/2 )
279 switch( COMP_KEYS((struct key *)((char * )p_v_base + n_j * p_n_width), (struct cpu_key *)p_v_key) ) {
280 case -1: n_lbound = n_j + 1; continue;
281 case 1: n_rbound = n_j - 1; continue;
282 case 0: *p_n_pos = n_j; return ITEM_FOUND; /* Key found in the array. */
283 }
284
285 /* bin_search did not find given key, it returns position of key,
286 that is minimal and greater than the given one. */
287 *p_n_pos = n_lbound;
288 return ITEM_NOT_FOUND;
289 }
290
291 #ifdef CONFIG_REISERFS_CHECK
292 extern struct tree_balance * cur_tb;
293 #endif
294
295
296
297 /* Minimal possible key. It is never in the tree. */
298 struct key MIN_KEY = {0, 0, {{0, 0},}};
299
300 /* Maximal possible key. It is never in the tree. */
301 struct key MAX_KEY = {0xffffffff, 0xffffffff, {{0xffffffff, 0xffffffff},}};
302
303
304 /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
305 of the path, and going upwards. We must check the path's validity at each step. If the key is not in
306 the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
307 case we return a special key, either MIN_KEY or MAX_KEY. */
308 inline struct key * get_lkey (
309 struct path * p_s_chk_path,
310 struct super_block * p_s_sb
311 ) {
312 int n_position, n_path_offset = p_s_chk_path->path_length;
313 struct buffer_head * p_s_parent;
314
315 #ifdef CONFIG_REISERFS_CHECK
316 if ( n_path_offset < FIRST_PATH_ELEMENT_OFFSET )
317 reiserfs_panic(p_s_sb,"PAP-5010: get_lkey: illegal offset in the path");
318 #endif
319
320 /* While not higher in path than first element. */
321 while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
322
323 #ifdef CONFIG_REISERFS_CHECK
324 if ( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
325 reiserfs_panic(p_s_sb, "PAP-5020: get_lkey: parent is not uptodate");
326 #endif
327
328 /* Parent at the path is not in the tree now. */
329 if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
330 return &MAX_KEY;
331 /* Check whether position in the parent is correct. */
332 if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
333 return &MAX_KEY;
334 /* Check whether parent at the path really points to the child. */
335 if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
336 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
337 return &MAX_KEY;
338 /* Return delimiting key if position in the parent is not equal to zero. */
339 if ( n_position )
340 return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
341 }
342 /* Return MIN_KEY if we are in the root of the buffer tree. */
343 if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
344 SB_ROOT_BLOCK (p_s_sb) )
345 return &MIN_KEY;
346 return &MAX_KEY;
347 }
348
349
350 /* Get delimiting key of the buffer at the path and its right neighbor. */
351 inline struct key * get_rkey (
352 struct path * p_s_chk_path,
353 struct super_block * p_s_sb
354 ) {
355 int n_position,
356 n_path_offset = p_s_chk_path->path_length;
357 struct buffer_head * p_s_parent;
358
359 #ifdef CONFIG_REISERFS_CHECK
360 if ( n_path_offset < FIRST_PATH_ELEMENT_OFFSET )
361 reiserfs_panic(p_s_sb,"PAP-5030: get_rkey: illegal offset in the path");
362 #endif
363
364 while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
365
366 #ifdef CONFIG_REISERFS_CHECK
367 if ( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
368 reiserfs_panic(p_s_sb, "PAP-5040: get_rkey: parent is not uptodate");
369 #endif
370
371 /* Parent at the path is not in the tree now. */
372 if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
373 return &MIN_KEY;
374 /* Check whether position in the parent is correct. */
375 if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
376 return &MIN_KEY;
377 /* Check whether parent at the path really points to the child. */
378 if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
379 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
380 return &MIN_KEY;
381 /* Return delimiting key if position in the parent is not the last one. */
382 if ( n_position != B_NR_ITEMS(p_s_parent) )
383 return B_N_PDELIM_KEY(p_s_parent, n_position);
384 }
385 /* Return MAX_KEY if we are in the root of the buffer tree. */
386 if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
387 SB_ROOT_BLOCK (p_s_sb) )
388 return &MAX_KEY;
389 return &MIN_KEY;
390 }
391
392
393 /* Check whether a key is contained in the tree rooted from a buffer at a path. */
394 /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
395 the path. These delimiting keys are stored at least one level above that buffer in the tree. If the
396 buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
397 this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
398 static inline int key_in_buffer (
399 struct path * p_s_chk_path, /* Path which should be checked. */
400 struct cpu_key * p_s_key, /* Key which should be checked. */
401 struct super_block * p_s_sb /* Super block pointer. */
402 ) {
403
404 #ifdef CONFIG_REISERFS_CHECK
405 if ( ! p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET ||
406 p_s_chk_path->path_length > MAX_HEIGHT )
407 reiserfs_panic(p_s_sb, "PAP-5050: key_in_buffer: pointer to the key(%p) is NULL or illegal path length(%d)",
408 p_s_key, p_s_chk_path->path_length);
409
410 if ( PATH_PLAST_BUFFER(p_s_chk_path)->b_dev == NODEV )
411 reiserfs_panic(p_s_sb, "PAP-5060: key_in_buffer: device must not be NODEV");
412 #endif
413
414 if ( COMP_KEYS(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1 )
415 /* left delimiting key is bigger, that the key we look for */
416 return 0;
417 // if ( COMP_KEYS(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
418 if ( COMP_KEYS(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1 )
419 /* p_s_key must be less than right delimitiing key */
420 return 0;
421 return 1;
422 }
423
424
425 inline void decrement_bcount(
426 struct buffer_head * p_s_bh
427 ) {
428 if ( p_s_bh ) {
429 if ( atomic_read (&(p_s_bh->b_count)) ) {
430 put_bh(p_s_bh) ;
431 return;
432 }
433 reiserfs_panic(NULL, "PAP-5070: decrement_bcount: trying to free free buffer %b", p_s_bh);
434 }
435 }
436
437
438 /* Decrement b_count field of the all buffers in the path. */
439 void decrement_counters_in_path (
440 struct path * p_s_search_path
441 ) {
442 int n_path_offset = p_s_search_path->path_length;
443
444 #ifdef CONFIG_REISERFS_CHECK
445 if ( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
446 n_path_offset > EXTENDED_MAX_HEIGHT - 1 )
447 reiserfs_panic(NULL, "PAP-5080: decrement_counters_in_path: illegal path offset of %d", n_path_offset);
448 #endif
449
450 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {
451 struct buffer_head * bh;
452
453 bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
454 decrement_bcount (bh);
455 }
456 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
457 }
458
459
460 int reiserfs_check_path(struct path *p) {
461 #ifdef CONFIG_REISERFS_CHECK
462 if (p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET) {
463 reiserfs_warning("check_path, path not properly relsed\n") ;
464 BUG() ;
465 }
466 #endif
467 return 0 ;
468 }
469
470
471 /* Release all buffers in the path. Restore dirty bits clean
472 ** when preparing the buffer for the log
473 **
474 ** only called from fix_nodes()
475 */
476 void pathrelse_and_restore (
477 struct super_block *s,
478 struct path * p_s_search_path
479 ) {
480 int n_path_offset = p_s_search_path->path_length;
481
482 #ifdef CONFIG_REISERFS_CHECK
483 if ( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET )
484 reiserfs_panic(NULL, "clm-4000: pathrelse: illegal path offset");
485 #endif
486
487 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {
488 reiserfs_restore_prepared_buffer(s, PATH_OFFSET_PBUFFER(p_s_search_path,
489 n_path_offset));
490 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
491 }
492 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
493 }
494
495 /* Release all buffers in the path. */
496 void pathrelse (
497 struct path * p_s_search_path
498 ) {
499 int n_path_offset = p_s_search_path->path_length;
500
501 #ifdef CONFIG_REISERFS_CHECK
502 if ( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET )
503 reiserfs_panic(NULL, "PAP-5090: pathrelse: illegal path offset");
504 #endif
505
506 while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )
507 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
508
509 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
510 }
511
512
513
514 static int is_leaf (char * buf, int blocksize, struct buffer_head * bh)
515 {
516 struct block_head * blkh;
517 struct item_head * ih;
518 int used_space;
519 int prev_location;
520 int i;
521 int nr;
522
523 blkh = (struct block_head *)buf;
524 if (le16_to_cpu (blkh->blk_level) != DISK_LEAF_NODE_LEVEL) {
525 printk ("is_leaf: this should be caught earlier\n");
526 return 0;
527 }
528
529 nr = le16_to_cpu (blkh->blk_nr_item);
530 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
531 /* item number is too big or too small */
532 reiserfs_warning ("is_leaf: nr_item seems wrong: %z\n", bh);
533 return 0;
534 }
535 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
536 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location (ih));
537 if (used_space != blocksize - le16_to_cpu (blkh->blk_free_space)) {
538 /* free space does not match to calculated amount of use space */
539 reiserfs_warning ("is_leaf: free space seems wrong: %z\n", bh);
540 return 0;
541 }
542
543 // FIXME: it is_leaf will hit performance too much - we may have
544 // return 1 here
545
546 /* check tables of item heads */
547 ih = (struct item_head *)(buf + BLKH_SIZE);
548 prev_location = blocksize;
549 for (i = 0; i < nr; i ++, ih ++) {
550 if (ih_location (ih) >= blocksize || ih_location (ih) < IH_SIZE * nr) {
551 reiserfs_warning ("is_leaf: item location seems wrong: %h\n", ih);
552 return 0;
553 }
554 if (ih_item_len (ih) < 1 || ih_item_len (ih) > MAX_ITEM_LEN (blocksize)) {
555 reiserfs_warning ("is_leaf: item length seems wrong: %h\n", ih);
556 return 0;
557 }
558 if (prev_location - ih_location (ih) != ih_item_len (ih)) {
559 reiserfs_warning ("is_leaf: item location seems wrong (second one): %h\n", ih);
560 return 0;
561 }
562 prev_location = ih_location (ih);
563 }
564
565 // one may imagine much more checks
566 return 1;
567 }
568
569
570 /* returns 1 if buf looks like an internal node, 0 otherwise */
571 static int is_internal (char * buf, int blocksize, struct buffer_head * bh)
572 {
573 struct block_head * blkh;
574 int nr;
575 int used_space;
576
577 blkh = (struct block_head *)buf;
578 if (le16_to_cpu (blkh->blk_level) <= DISK_LEAF_NODE_LEVEL ||
579 le16_to_cpu (blkh->blk_level) > MAX_HEIGHT) {
580 /* this level is not possible for internal nodes */
581 printk ("is_internal: this should be caught earlier\n");
582 return 0;
583 }
584
585 nr = le16_to_cpu (blkh->blk_nr_item);
586 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
587 /* for internal which is not root we might check min number of keys */
588 reiserfs_warning ("is_internal: number of key seems wrong: %z\n", bh);
589 return 0;
590 }
591
592 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
593 if (used_space != blocksize - le16_to_cpu (blkh->blk_free_space)) {
594 reiserfs_warning ("is_internal: free space seems wrong: %z\n", bh);
595 return 0;
596 }
597
598 // one may imagine much more checks
599 return 1;
600 }
601
602
603 // make sure that bh contains formatted node of reiserfs tree of
604 // 'level'-th level
605 static int is_tree_node (struct buffer_head * bh, int level)
606 {
607 if (B_LEVEL (bh) != level) {
608 printk ("is_tree_node: node level %d does not match to the expected one %d\n",
609 B_LEVEL (bh), level);
610 return 0;
611 }
612 if (level == DISK_LEAF_NODE_LEVEL)
613 return is_leaf (bh->b_data, bh->b_size, bh);
614
615 return is_internal (bh->b_data, bh->b_size, bh);
616 }
617
618
619
620 #ifdef SEARCH_BY_KEY_READA
621
622 /* The function is NOT SCHEDULE-SAFE! */
623 static void search_by_key_reada (struct super_block * s, int blocknr)
624 {
625 struct buffer_head * bh;
626
627 if (blocknr == 0)
628 return;
629
630 bh = reiserfs_getblk (s->s_dev, blocknr, s->s_blocksize);
631
632 if (!buffer_uptodate (bh)) {
633 ll_rw_block (READA, 1, &bh);
634 }
635 bh->b_count --;
636 }
637
638 #endif
639
640 /**************************************************************************
641 * Algorithm SearchByKey *
642 * look for item in the Disk S+Tree by its key *
643 * Input: p_s_sb - super block *
644 * p_s_key - pointer to the key to search *
645 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR *
646 * p_s_search_path - path from the root to the needed leaf *
647 **************************************************************************/
648
649 /* This function fills up the path from the root to the leaf as it
650 descends the tree looking for the key. It uses reiserfs_bread to
651 try to find buffers in the cache given their block number. If it
652 does not find them in the cache it reads them from disk. For each
653 node search_by_key finds using reiserfs_bread it then uses
654 bin_search to look through that node. bin_search will find the
655 position of the block_number of the next node if it is looking
656 through an internal node. If it is looking through a leaf node
657 bin_search will find the position of the item which has key either
658 equal to given key, or which is the maximal key less than the given
659 key. search_by_key returns a path that must be checked for the
660 correctness of the top of the path but need not be checked for the
661 correctness of the bottom of the path */
662 /* The function is NOT SCHEDULE-SAFE! */
663 int search_by_key (struct super_block * p_s_sb,
664 struct cpu_key * p_s_key, /* Key to search. */
665 struct path * p_s_search_path, /* This structure was
666 allocated and initialized
667 by the calling
668 function. It is filled up
669 by this function. */
670 int n_stop_level /* How far down the tree to search. To
671 stop at leaf level - set to
672 DISK_LEAF_NODE_LEVEL */
673 ) {
674 kdev_t n_dev = p_s_sb->s_dev;
675 int n_block_number = SB_ROOT_BLOCK (p_s_sb),
676 expected_level = SB_TREE_HEIGHT (p_s_sb),
677 n_block_size = p_s_sb->s_blocksize;
678 struct buffer_head * p_s_bh;
679 struct path_element * p_s_last_element;
680 int n_node_level, n_retval;
681 int right_neighbor_of_leaf_node;
682 int fs_gen;
683
684 #ifdef CONFIG_REISERFS_CHECK
685 int n_repeat_counter = 0;
686 #endif
687
688 /* As we add each node to a path we increase its count. This means that
689 we must be careful to release all nodes in a path before we either
690 discard the path struct or re-use the path struct, as we do here. */
691
692 decrement_counters_in_path(p_s_search_path);
693
694 right_neighbor_of_leaf_node = 0;
695
696 /* With each iteration of this loop we search through the items in the
697 current node, and calculate the next current node(next path element)
698 for the next iteration of this loop.. */
699 while ( 1 ) {
700
701 #ifdef CONFIG_REISERFS_CHECK
702 if ( !(++n_repeat_counter % 50000) )
703 reiserfs_warning ("PAP-5100: search_by_key: %s:"
704 "there were %d iterations of while loop "
705 "looking for key %K\n",
706 current->comm, n_repeat_counter, p_s_key);
707 #endif
708
709 /* prep path to have another element added to it. */
710 p_s_last_element = PATH_OFFSET_PELEMENT(p_s_search_path, ++p_s_search_path->path_length);
711 fs_gen = get_generation (p_s_sb);
712 expected_level --;
713
714 #ifdef SEARCH_BY_KEY_READA
715 /* schedule read of right neighbor */
716 search_by_key_reada (p_s_sb, right_neighbor_of_leaf_node);
717 #endif
718
719 /* Read the next tree node, and set the last element in the path to
720 have a pointer to it. */
721 if ( ! (p_s_bh = p_s_last_element->pe_buffer =
722 reiserfs_bread(n_dev, n_block_number, n_block_size)) ) {
723 p_s_search_path->path_length --;
724 pathrelse(p_s_search_path);
725 return IO_ERROR;
726 }
727
728 /* It is possible that schedule occurred. We must check whether the key
729 to search is still in the tree rooted from the current buffer. If
730 not then repeat search from the root. */
731 if ( fs_changed (fs_gen, p_s_sb) &&
732 (!B_IS_IN_TREE (p_s_bh) || !key_in_buffer(p_s_search_path, p_s_key, p_s_sb)) ) {
733 decrement_counters_in_path(p_s_search_path);
734
735 /* Get the root block number so that we can repeat the search
736 starting from the root. */
737 n_block_number = SB_ROOT_BLOCK (p_s_sb);
738 expected_level = SB_TREE_HEIGHT (p_s_sb);
739 right_neighbor_of_leaf_node = 0;
740
741 /* repeat search from the root */
742 continue;
743 }
744
745 #ifdef CONFIG_REISERFS_CHECK
746
747 if ( ! key_in_buffer(p_s_search_path, p_s_key, p_s_sb) )
748 reiserfs_panic(p_s_sb, "PAP-5130: search_by_key: key is not in the buffer");
749 if ( cur_tb ) {
750 print_cur_tb ("5140");
751 reiserfs_panic(p_s_sb, "PAP-5140: search_by_key: schedule occurred in do_balance!");
752 }
753
754 #endif
755
756 // make sure, that the node contents look like a node of
757 // certain level
758 if (!is_tree_node (p_s_bh, expected_level)) {
759 reiserfs_warning ("vs-5150: search_by_key: "
760 "invalid format found in block %d. Fsck?\n", p_s_bh->b_blocknr);
761 pathrelse (p_s_search_path);
762 return IO_ERROR;
763 }
764
765 /* ok, we have acquired next formatted node in the tree */
766 n_node_level = B_LEVEL (p_s_bh);
767
768 #ifdef CONFIG_REISERFS_CHECK
769
770 if (n_node_level < n_stop_level)
771 reiserfs_panic (p_s_sb, "vs-5152: search_by_key: tree level is less than stop level (%d)",
772 n_node_level, n_stop_level);
773
774 #endif
775
776 n_retval = bin_search (p_s_key, B_N_PITEM_HEAD(p_s_bh, 0), B_NR_ITEMS(p_s_bh),
777 ( n_node_level == DISK_LEAF_NODE_LEVEL ) ? IH_SIZE : KEY_SIZE, &(p_s_last_element->pe_position));
778 if (n_node_level == n_stop_level) {
779 return n_retval;
780 }
781
782 /* we are not in the stop level */
783 if (n_retval == ITEM_FOUND)
784 /* item has been found, so we choose the pointer which is to the right of the found one */
785 p_s_last_element->pe_position++;
786
787 /* if item was not found we choose the position which is to
788 the left of the found item. This requires no code,
789 bin_search did it already.*/
790
791 /* So we have chosen a position in the current node which is
792 an internal node. Now we calculate child block number by
793 position in the node. */
794 n_block_number = B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);
795
796 #ifdef SEARCH_BY_KEY_READA
797 /* if we are going to read leaf node, then calculate its right neighbor if possible */
798 if (n_node_level == DISK_LEAF_NODE_LEVEL + 1 && p_s_last_element->pe_position < B_NR_ITEMS (p_s_bh))
799 right_neighbor_of_leaf_node = B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position + 1);
800 #endif
801 }
802 }
803
804
805 /* Form the path to an item and position in this item which contains
806 file byte defined by p_s_key. If there is no such item
807 corresponding to the key, we point the path to the item with
808 maximal key less than p_s_key, and *p_n_pos_in_item is set to one
809 past the last entry/byte in the item. If searching for entry in a
810 directory item, and it is not found, *p_n_pos_in_item is set to one
811 entry more than the entry with maximal key which is less than the
812 sought key.
813
814 Note that if there is no entry in this same node which is one more,
815 then we point to an imaginary entry. for direct items, the
816 position is in units of bytes, for indirect items the position is
817 in units of blocknr entries, for directory items the position is in
818 units of directory entries. */
819
820 /* The function is NOT SCHEDULE-SAFE! */
821 int search_for_position_by_key (struct super_block * p_s_sb, /* Pointer to the super block. */
822 struct cpu_key * p_cpu_key, /* Key to search (cpu variable) */
823 struct path * p_s_search_path /* Filled up by this function. */
824 ) {
825 struct item_head * p_le_ih; /* pointer to on-disk structure */
826 int n_blk_size;
827 loff_t item_offset, offset;
828 struct reiserfs_dir_entry de;
829 int retval;
830
831 /* If searching for directory entry. */
832 if ( is_direntry_cpu_key (p_cpu_key) )
833 return search_by_entry_key (p_s_sb, p_cpu_key, p_s_search_path, &de);
834
835 /* If not searching for directory entry. */
836
837 /* If item is found. */
838 retval = search_item (p_s_sb, p_cpu_key, p_s_search_path);
839 if (retval == IO_ERROR)
840 return retval;
841 if ( retval == ITEM_FOUND ) {
842
843 #ifdef CONFIG_REISERFS_CHECK
844 if ( ! B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
845 PATH_LAST_POSITION(p_s_search_path))->ih_item_len )
846 reiserfs_panic(p_s_sb, "PAP-5165: search_for_position_by_key: item length equals zero");
847 #endif
848
849 pos_in_item(p_s_search_path) = 0;
850 return POSITION_FOUND;
851 }
852
853 #ifdef CONFIG_REISERFS_CHECK
854 if ( ! PATH_LAST_POSITION(p_s_search_path) )
855 reiserfs_panic(p_s_sb, "PAP-5170: search_for_position_by_key: position equals zero");
856 #endif
857
858 /* Item is not found. Set path to the previous item. */
859 p_le_ih = B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), --PATH_LAST_POSITION(p_s_search_path));
860 n_blk_size = p_s_sb->s_blocksize;
861
862 if (comp_short_keys (&(p_le_ih->ih_key), p_cpu_key)) {
863 return FILE_NOT_FOUND;
864 }
865
866 #if 0
867 /*#ifdef CONFIG_REISERFS_CHECK*/
868
869 /* we expect to find stat data or item of the same type */
870 if ( ! is_statdata_le_ih(p_le_ih) && ((is_indirect_cpu_key(p_cpu_key) && ! is_indirect_le_ih(p_le_ih)) ||
871 (is_direct_cpu_key(p_cpu_key) && ! is_direct_le_ih(p_le_ih))) ) {
872 print_block (PATH_PLAST_BUFFER(p_s_search_path), PRINT_LEAF_ITEMS,
873 PATH_LAST_POSITION (p_s_search_path) - 2,
874 PATH_LAST_POSITION (p_s_search_path) + 2);
875 reiserfs_panic(p_s_sb, "PAP-5190: search_for_position_by_key: "
876 "found item %h type does not match to the expected one %k",
877 p_le_ih, p_cpu_key);
878 }
879 /*#endif*/
880 #endif
881
882 // FIXME: quite ugly this far
883
884 item_offset = le_ih_k_offset (p_le_ih);
885 offset = cpu_key_k_offset (p_cpu_key);
886
887 /* Needed byte is contained in the item pointed to by the path.*/
888 if (item_offset <= offset &&
889 item_offset + op_bytes_number (p_le_ih, n_blk_size) > offset) {
890 pos_in_item (p_s_search_path) = offset - item_offset;
891 if ( is_indirect_le_ih(p_le_ih) ) {
892 pos_in_item (p_s_search_path) /= n_blk_size;
893 }
894 return POSITION_FOUND;
895 }
896
897 /* Needed byte is not contained in the item pointed to by the
898 path. Set pos_in_item out of the item. */
899 if ( is_indirect_le_ih (p_le_ih) )
900 pos_in_item (p_s_search_path) = le16_to_cpu (p_le_ih->ih_item_len) / UNFM_P_SIZE;
901 else
902 pos_in_item (p_s_search_path) = le16_to_cpu (p_le_ih->ih_item_len);
903
904 return POSITION_NOT_FOUND;
905 }
906
907
908 /* Compare given item and item pointed to by the path. */
909 int comp_items (struct item_head * stored_ih, struct path * p_s_path)
910 {
911 struct buffer_head * p_s_bh;
912 struct item_head * ih;
913
914 /* Last buffer at the path is not in the tree. */
915 if ( ! B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)) )
916 return 1;
917
918 /* Last path position is invalid. */
919 if ( PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh) )
920 return 1;
921
922 /* we need only to know, whether it is the same item */
923 ih = get_ih (p_s_path);
924 return memcmp (stored_ih, ih, IH_SIZE);
925
926 #if 0
927 /* Get item at the path. */
928 p_s_path_item = PATH_PITEM_HEAD(p_s_path);
929 /* Compare keys. */
930 if ( COMP_KEYS(&(p_s_path_item->ih_key), &(p_cpu_ih->ih_key)) )
931 return 1;
932
933 /* Compare other items fields. */
934 if ( le16_to_cpu (p_s_path_item->u.ih_entry_count) != p_cpu_ih->u.ih_entry_count ||
935 le16_to_cpu (p_s_path_item->ih_item_len) != p_cpu_ih->ih_item_len ||
936 le16_to_cpu ( p_s_path_item->ih_item_location) != p_cpu_ih->ih_item_location )
937 return 1;
938
939 /* Items are equal. */
940 return 0;
941 #endif
942 }
943
944
945 /* unformatted nodes are not logged anymore, ever. This is safe
946 ** now
947 */
948 #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
949
950 // block can not be forgotten as it is in I/O or held by someone
951 #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
952
953
954
955 // prepare for delete or cut of direct item
956 static inline int prepare_for_direct_item (struct path * path,
957 struct item_head * le_ih,
958 struct inode * inode,
959 loff_t new_file_length,
960 int * cut_size)
961 {
962 loff_t round_len;
963
964
965 if ( new_file_length == max_reiserfs_offset (inode) ) {
966 /* item has to be deleted */
967 *cut_size = -(IH_SIZE + le16_to_cpu (le_ih->ih_item_len));
968 return M_DELETE;
969 }
970
971 // new file gets truncated
972 if (inode_items_version (inode) == ITEM_VERSION_2) {
973 //
974 round_len = ROUND_UP (new_file_length);
975 /* this was n_new_file_length < le_ih ... */
976 if ( round_len < le_ih_k_offset (le_ih) ) {
977 *cut_size = -(IH_SIZE + le16_to_cpu (le_ih->ih_item_len));
978 return M_DELETE; /* Delete this item. */
979 }
980 /* Calculate first position and size for cutting from item. */
981 pos_in_item (path) = round_len - (le_ih_k_offset (le_ih) - 1);
982 *cut_size = -(le16_to_cpu (le_ih->ih_item_len) - pos_in_item(path));
983
984 return M_CUT; /* Cut from this item. */
985 }
986
987
988 // old file: items may have any length
989
990 if ( new_file_length < le_ih_k_offset (le_ih) ) {
991 *cut_size = -(IH_SIZE + le16_to_cpu (le_ih->ih_item_len));
992 return M_DELETE; /* Delete this item. */
993 }
994 /* Calculate first position and size for cutting from item. */
995 *cut_size = -(le16_to_cpu (le_ih->ih_item_len) -
996 (pos_in_item (path) = new_file_length + 1 - le_ih_k_offset (le_ih)));
997 return M_CUT; /* Cut from this item. */
998 }
999
1000
1001 static inline int prepare_for_direntry_item (struct path * path,
1002 struct item_head * le_ih,
1003 struct inode * inode,
1004 loff_t new_file_length,
1005 int * cut_size)
1006 {
1007 if (le_ih_k_offset (le_ih) == DOT_OFFSET &&
1008 new_file_length == max_reiserfs_offset (inode)) {
1009 #ifdef CONFIG_REISERFS_CHECK
1010 if (ih_entry_count (le_ih) != 2)
1011 reiserfs_panic(inode->i_sb,"PAP-5220: prepare_for_delete_or_cut: "
1012 "incorrect empty directory item (%h)", le_ih);
1013 #endif
1014 *cut_size = -(IH_SIZE + le16_to_cpu (le_ih->ih_item_len));
1015 return M_DELETE; /* Delete the directory item containing "." and ".." entry. */
1016 }
1017
1018 if ( ih_entry_count (le_ih) == 1 ) {
1019 /* Delete the directory item such as there is one record only
1020 in this item*/
1021 *cut_size = -(IH_SIZE + le16_to_cpu (le_ih->ih_item_len));
1022 return M_DELETE;
1023 }
1024
1025 /* Cut one record from the directory item. */
1026 *cut_size = -(DEH_SIZE + entry_length (get_last_bh (path), le_ih, pos_in_item (path)));
1027 return M_CUT;
1028 }
1029
1030
1031 /* If the path points to a directory or direct item, calculate mode and the size cut, for balance.
1032 If the path points to an indirect item, remove some number of its unformatted nodes.
1033 In case of file truncate calculate whether this item must be deleted/truncated or last
1034 unformatted node of this item will be converted to a direct item.
1035 This function returns a determination of what balance mode the calling function should employ. */
1036 static char prepare_for_delete_or_cut(
1037 struct reiserfs_transaction_handle *th,
1038 struct inode * inode,
1039 struct path * p_s_path,
1040 struct cpu_key * p_s_item_key,
1041 int * p_n_removed, /* Number of unformatted nodes which were removed
1042 from end of the file. */
1043 int * p_n_cut_size,
1044 unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */
1045 ) {
1046 struct super_block * p_s_sb = inode->i_sb;
1047 struct item_head * p_le_ih = PATH_PITEM_HEAD(p_s_path);
1048 struct buffer_head * p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1049
1050 #ifdef CONFIG_REISERFS_CHECK
1051 int n_repeat_counter = 0;
1052 #endif
1053
1054 /* Stat_data item. */
1055 if ( is_statdata_le_ih (p_le_ih) ) {
1056
1057 #ifdef CONFIG_REISERFS_CHECK
1058 if ( n_new_file_length != max_reiserfs_offset (inode) )
1059 reiserfs_panic(p_s_sb, "PAP-5210: prepare_for_delete_or_cut: mode must be M_DELETE");
1060 #endif
1061
1062 *p_n_cut_size = -(IH_SIZE + le16_to_cpu (p_le_ih->ih_item_len));
1063 return M_DELETE;
1064 }
1065
1066
1067 /* Directory item. */
1068 if ( is_direntry_le_ih (p_le_ih) )
1069 return prepare_for_direntry_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
1070
1071 /* Direct item. */
1072 if ( is_direct_le_ih (p_le_ih) )
1073 return prepare_for_direct_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
1074
1075
1076 /* Case of an indirect item. */
1077 {
1078 int n_unfm_number, /* Number of the item unformatted nodes. */
1079 n_counter,
1080 n_retry, /* Set to one if there is unformatted node buffer in use. */
1081 n_blk_size;
1082 __u32 * p_n_unfm_pointer; /* Pointer to the unformatted node number. */
1083 __u32 tmp;
1084 struct item_head s_ih; /* Item header. */
1085 char c_mode; /* Returned mode of the balance. */
1086 struct buffer_head * p_s_un_bh;
1087 int need_research;
1088
1089
1090 n_blk_size = p_s_sb->s_blocksize;
1091
1092 /* Search for the needed object indirect item until there are no unformatted nodes to be removed. */
1093 do {
1094 need_research = 0;
1095 p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1096 /* Copy indirect item header to a temp variable. */
1097 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1098 /* Calculate number of unformatted nodes in this item. */
1099 n_unfm_number = I_UNFM_NUM(&s_ih);
1100
1101 #ifdef CONFIG_REISERFS_CHECK
1102 if ( ! is_indirect_le_ih(&s_ih) || ! n_unfm_number ||
1103 pos_in_item (p_s_path) + 1 != n_unfm_number ) {
1104 printk("n_unfm_number = %d *p_n_pos_in_item = %d\n",n_unfm_number, pos_in_item (p_s_path));
1105 reiserfs_panic(p_s_sb, "PAP-5240: prepare_for_delete_or_cut: illegal item %h", &s_ih);
1106 }
1107 #endif
1108
1109 /* Calculate balance mode and position in the item to remove unformatted nodes. */
1110 if ( n_new_file_length == max_reiserfs_offset (inode) ) {/* Case of delete. */
1111 pos_in_item (p_s_path) = 0;
1112 *p_n_cut_size = -(IH_SIZE + le16_to_cpu (s_ih.ih_item_len));
1113 c_mode = M_DELETE;
1114 }
1115 else { /* Case of truncate. */
1116 if ( n_new_file_length < le_ih_k_offset (&s_ih) ) {
1117 pos_in_item (p_s_path) = 0;
1118 *p_n_cut_size = -(IH_SIZE + le16_to_cpu (s_ih.ih_item_len));
1119 c_mode = M_DELETE; /* Delete this item. */
1120 }
1121 else {
1122 /* indirect item must be truncated starting from *p_n_pos_in_item-th position */
1123 pos_in_item (p_s_path) = (n_new_file_length + n_blk_size - le_ih_k_offset (&s_ih) ) >> p_s_sb->s_blocksize_bits;
1124
1125 #ifdef CONFIG_REISERFS_CHECK
1126 if ( pos_in_item (p_s_path) > n_unfm_number )
1127 reiserfs_panic(p_s_sb, "PAP-5250: prepare_for_delete_or_cut: illegal position in the item");
1128 #endif
1129
1130 /* Either convert last unformatted node of indirect item to direct item or increase
1131 its free space. */
1132 if ( pos_in_item (p_s_path) == n_unfm_number ) {
1133 *p_n_cut_size = 0; /* Nothing to cut. */
1134 return M_CONVERT; /* Maybe convert last unformatted node to the direct item. */
1135 }
1136 /* Calculate size to cut. */
1137 *p_n_cut_size = -(s_ih.ih_item_len - pos_in_item (p_s_path) * UNFM_P_SIZE);
1138
1139 c_mode = M_CUT; /* Cut from this indirect item. */
1140 }
1141 }
1142
1143 #ifdef CONFIG_REISERFS_CHECK
1144 if ( n_unfm_number <= pos_in_item (p_s_path) )
1145 reiserfs_panic(p_s_sb, "PAP-5260: prepare_for_delete_or_cut: illegal position in the indirect item");
1146 #endif
1147
1148 /* pointers to be cut */
1149 n_unfm_number -= pos_in_item (p_s_path);
1150 /* Set pointer to the last unformatted node pointer that is to be cut. */
1151 p_n_unfm_pointer = (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1 - *p_n_removed;
1152
1153
1154 /* We go through the unformatted nodes pointers of the indirect
1155 item and look for the unformatted nodes in the cache. If we
1156 found some of them we free it, zero corresponding indirect item
1157 entry and log buffer containing that indirect item. For this we
1158 need to prepare last path element for logging. If some
1159 unformatted node has b_count > 1 we must not free this
1160 unformatted node since it is in use. */
1161 reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
1162 // note: path could be changed, first line in for loop takes care
1163 // of it
1164
1165 for ( n_retry = 0, n_counter = *p_n_removed;
1166 n_counter < n_unfm_number; n_counter++, p_n_unfm_pointer-- ) {
1167
1168 if (item_moved (&s_ih, p_s_path)) {
1169 need_research = 1 ;
1170 break;
1171 }
1172 #ifdef CONFIG_REISERFS_CHECK
1173 if (p_n_unfm_pointer < (__u32 *)B_I_PITEM(p_s_bh, &s_ih) ||
1174 p_n_unfm_pointer > (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1)
1175 reiserfs_panic (p_s_sb, "vs-5265: prepare_for_delete_or_cut: pointer out of range");
1176 #endif
1177
1178 if ( ! *p_n_unfm_pointer ) { /* Hole, nothing to remove. */
1179 if ( ! n_retry )
1180 (*p_n_removed)++;
1181 continue;
1182 }
1183 /* Search for the buffer in cache. */
1184 p_s_un_bh = get_hash_table(p_s_sb->s_dev, *p_n_unfm_pointer, n_blk_size);
1185
1186 if (p_s_un_bh) {
1187 mark_buffer_clean(p_s_un_bh) ;
1188 if (buffer_locked(p_s_un_bh)) {
1189 __wait_on_buffer(p_s_un_bh) ;
1190 }
1191 /* even if the item moves, the block number of the
1192 ** unformatted node we want to cut won't. So, it was
1193 ** safe to clean the buffer here, this block _will_
1194 ** get freed during this call to prepare_for_delete_or_cut
1195 */
1196 if ( item_moved (&s_ih, p_s_path) ) {
1197 need_research = 1;
1198 brelse(p_s_un_bh) ;
1199 break ;
1200 }
1201 }
1202 if ( p_s_un_bh && block_in_use (p_s_un_bh)) {
1203 /* Block is locked or held more than by one holder and by
1204 journal. */
1205
1206 #ifdef CONFIG_REISERFS_CHECK
1207 if (n_repeat_counter && (n_repeat_counter % 100000) == 0) {
1208 printk("prepare_for_delete, waiting on buffer %lu, b_count %d, %s%cJDIRTY %cJDIRTY_WAIT\n",
1209 p_s_un_bh->b_blocknr, atomic_read (&p_s_un_bh->b_count),
1210 buffer_locked (p_s_un_bh) ? "locked, " : "",
1211 buffer_journaled(p_s_un_bh) ? ' ' : '!',
1212 buffer_journal_dirty(p_s_un_bh) ? ' ' : '!') ;
1213
1214 }
1215 #endif
1216 n_retry = 1;
1217 brelse (p_s_un_bh);
1218 continue;
1219 }
1220
1221 if ( ! n_retry )
1222 (*p_n_removed)++;
1223
1224 #ifdef CONFIG_REISERFS_CHECK
1225 if ( p_s_un_bh && (*p_n_unfm_pointer != p_s_un_bh->b_blocknr ))
1226 // note: minix_truncate allows that. As truncate is
1227 // protected by down (inode->i_sem), two truncates can not
1228 // co-exist
1229 reiserfs_panic(p_s_sb, "PAP-5280: prepare_for_delete_or_cut: blocks numbers are different");
1230 #endif
1231
1232 tmp = *p_n_unfm_pointer;
1233 *p_n_unfm_pointer = 0;
1234 journal_mark_dirty (th, p_s_sb, p_s_bh);
1235 bforget (p_s_un_bh);
1236 inode->i_blocks -= p_s_sb->s_blocksize / 512;
1237 reiserfs_free_block(th, tmp);
1238 if ( item_moved (&s_ih, p_s_path) ) {
1239 need_research = 1;
1240 break ;
1241 }
1242 }
1243
1244 /* a trick. If the buffer has been logged, this
1245 ** will do nothing. If we've broken the loop without
1246 ** logging it, it will restore the buffer
1247 **
1248 */
1249 reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
1250
1251 if ( n_retry ) {
1252 /* There is block in use. Wait, they should release it soon */
1253
1254 #ifdef CONFIG_REISERFS_CHECK
1255 if ( *p_n_removed >= n_unfm_number )
1256 reiserfs_panic(p_s_sb, "PAP-5290: prepare_for_delete_or_cut: illegal case");
1257 if ( !(++n_repeat_counter % 500000) ) {
1258 reiserfs_warning("PAP-5300: prepare_for_delete_or_cut: (pid %u): "
1259 "could not delete item %k in (%d) iterations. New file length %Lu. (inode %Ld), Still trying\n",
1260 current->pid, p_s_item_key, n_repeat_counter, n_new_file_length, inode->i_size);
1261 if (n_repeat_counter == 5000000) {
1262 print_block (PATH_PLAST_BUFFER(p_s_path), 3,
1263 PATH_LAST_POSITION (p_s_path) - 2, PATH_LAST_POSITION (p_s_path) + 2);
1264 reiserfs_panic(p_s_sb, "PAP-5305: prepare_for_delete_or_cut: key %k, new_file_length %Ld",
1265 p_s_item_key, n_new_file_length);
1266 }
1267 }
1268 #endif
1269
1270 run_task_queue(&tq_disk);
1271 current->policy |= SCHED_YIELD;
1272 schedule();
1273 }
1274 /* This loop can be optimized. */
1275 } while ( (*p_n_removed < n_unfm_number || need_research) &&
1276 search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND );
1277
1278 #ifdef CONFIG_REISERFS_CHECK
1279 if ( *p_n_removed < n_unfm_number )
1280 reiserfs_panic(p_s_sb, "PAP-5310: prepare_for_delete_or_cut: indirect item is not found");
1281
1282 if (item_moved (&s_ih, p_s_path) ) {
1283 printk("prepare_for_delete_or_cut: after while, comp failed, retry\n") ;
1284 BUG ();
1285 }
1286 #endif
1287
1288 if (c_mode == M_CUT)
1289 pos_in_item (p_s_path) *= UNFM_P_SIZE;
1290 return c_mode;
1291 }
1292 }
1293
1294
1295 /* Calculate bytes number which will be deleted or cutted in the balance. */
1296 int calc_deleted_bytes_number(
1297 struct tree_balance * p_s_tb,
1298 char c_mode
1299 ) {
1300 int n_del_size;
1301 struct item_head * p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);
1302
1303 if ( is_statdata_le_ih (p_le_ih) )
1304 return 0;
1305
1306 if ( is_direntry_le_ih (p_le_ih) ) {
1307 // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
1308 // we can't use EMPTY_DIR_SIZE, as old format dirs have a different
1309 // empty size. ick. FIXME, is this right?
1310 //
1311 return le16_to_cpu(p_le_ih->ih_item_len) ;
1312 }
1313 n_del_size = ( c_mode == M_DELETE ) ? le16_to_cpu (p_le_ih->ih_item_len) : -p_s_tb->insert_size[0];
1314
1315 if ( is_indirect_le_ih (p_le_ih) )
1316 n_del_size = (n_del_size/UNFM_P_SIZE)*
1317 (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size);// - get_ih_free_space (p_le_ih);
1318 return n_del_size;
1319 }
1320
1321 static void init_tb_struct(
1322 struct reiserfs_transaction_handle *th,
1323 struct tree_balance * p_s_tb,
1324 struct super_block * p_s_sb,
1325 struct path * p_s_path,
1326 int n_size
1327 ) {
1328 memset (p_s_tb,'\0',sizeof(struct tree_balance));
1329 p_s_tb->transaction_handle = th ;
1330 p_s_tb->tb_sb = p_s_sb;
1331 p_s_tb->tb_path = p_s_path;
1332 PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1333 PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
1334 p_s_tb->insert_size[0] = n_size;
1335 }
1336
1337
1338
1339 void padd_item (char * item, int total_length, int length)
1340 {
1341 int i;
1342
1343 for (i = total_length; i > length; )
1344 item [--i] = 0;
1345 }
1346
1347
1348 /* Delete object item. */
1349 int reiserfs_delete_item (struct reiserfs_transaction_handle *th,
1350 struct path * p_s_path, /* Path to the deleted item. */
1351 struct cpu_key * p_s_item_key, /* Key to search for the deleted item. */
1352 struct inode * p_s_inode,/* inode is here just to update i_blocks */
1353 struct buffer_head * p_s_un_bh) /* NULL or unformatted node pointer. */
1354 {
1355 struct super_block * p_s_sb = p_s_inode->i_sb;
1356 struct tree_balance s_del_balance;
1357 struct item_head s_ih;
1358 int n_ret_value,
1359 n_del_size,
1360 n_removed;
1361
1362 #ifdef CONFIG_REISERFS_CHECK
1363 char c_mode;
1364 int n_iter = 0;
1365 #endif
1366
1367 init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path, 0/*size is unknown*/);
1368
1369 while ( 1 ) {
1370 n_removed = 0;
1371
1372 #ifdef CONFIG_REISERFS_CHECK
1373 n_iter++;
1374 c_mode =
1375 #endif
1376 prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed, &n_del_size, max_reiserfs_offset (p_s_inode));
1377
1378 #ifdef CONFIG_REISERFS_CHECK
1379 if ( c_mode != M_DELETE )
1380 reiserfs_panic(p_s_sb, "PAP-5320: reiserfs_delete_item: mode must be M_DELETE");
1381 #endif
1382
1383 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1384 s_del_balance.insert_size[0] = n_del_size;
1385
1386 n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, 0);
1387 if ( n_ret_value != REPEAT_SEARCH )
1388 break;
1389
1390 // file system changed, repeat search
1391 n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1392 if (n_ret_value == IO_ERROR)
1393 break;
1394 if (n_ret_value == FILE_NOT_FOUND) {
1395 reiserfs_warning ("vs-5340: reiserfs_delete_item: "
1396 "no items of the file %K found\n", p_s_item_key);
1397 break;
1398 }
1399 } /* while (1) */
1400
1401 if ( n_ret_value != CARRY_ON ) {
1402 unfix_nodes(&s_del_balance);
1403 return 0;
1404 }
1405
1406 // reiserfs_delete_item returns item length when success
1407 n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
1408
1409 if ( p_s_un_bh ) {
1410 int off;
1411 char *data ;
1412
1413 /* We are in direct2indirect conversion, so move tail contents
1414 to the unformatted node */
1415 /* note, we do the copy before preparing the buffer because we
1416 ** don't care about the contents of the unformatted node yet.
1417 ** the only thing we really care about is the direct item's data
1418 ** is in the unformatted node.
1419 **
1420 ** Otherwise, we would have to call reiserfs_prepare_for_journal on
1421 ** the unformatted node, which might schedule, meaning we'd have to
1422 ** loop all the way back up to the start of the while loop.
1423 **
1424 ** The unformatted node must be dirtied later on. We can't be
1425 ** sure here if the entire tail has been deleted yet.
1426 **
1427 ** p_s_un_bh is from the page cache (all unformatted nodes are
1428 ** from the page cache) and might be a highmem page. So, we
1429 ** can't use p_s_un_bh->b_data. But, the page has already been
1430 ** kmapped, so we can use page_address()
1431 ** -clm
1432 */
1433
1434 data = page_address(p_s_un_bh->b_page) ;
1435 off = ((le_ih_k_offset (&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
1436 memcpy(data + off,
1437 B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), n_ret_value);
1438 }
1439
1440 /* Perform balancing after all resources have been collected at once. */
1441 do_balance(&s_del_balance, NULL, NULL, M_DELETE);
1442
1443 /* Return deleted body length */
1444 return n_ret_value;
1445 }
1446
1447
1448 /* Summary Of Mechanisms For Handling Collisions Between Processes:
1449
1450 deletion of the body of the object is performed by iput(), with the
1451 result that if multiple processes are operating on a file, the
1452 deletion of the body of the file is deferred until the last process
1453 that has an open inode performs its iput().
1454
1455 writes and truncates are protected from collisions by use of
1456 semaphores.
1457
1458 creates, linking, and mknod are protected from collisions with other
1459 processes by making the reiserfs_add_entry() the last step in the
1460 creation, and then rolling back all changes if there was a collision.
1461 - Hans
1462 */
1463
1464
1465 /* this deletes item which never gets split */
1466 static void reiserfs_delete_solid_item (struct reiserfs_transaction_handle *th,
1467 struct key * key)
1468 {
1469 struct tree_balance tb;
1470 INITIALIZE_PATH (path);
1471 int item_len;
1472 int tb_init = 0 ;
1473 struct cpu_key cpu_key;
1474 int retval;
1475
1476 le_key2cpu_key (&cpu_key, key);
1477
1478 while (1) {
1479 retval = search_item (th->t_super, &cpu_key, &path);
1480 if (retval == IO_ERROR) {
1481 reiserfs_warning ("vs-: reiserfs_delete_solid_item: "
1482 "i/o failure occurred trying to delete %K\n", &cpu_key);
1483 break;
1484 }
1485 if (retval != ITEM_FOUND) {
1486 pathrelse (&path);
1487 reiserfs_warning ("vs-: reiserfs_delete_solid_item: %k not found",
1488 key);
1489 break;
1490 }
1491 if (!tb_init) {
1492 tb_init = 1 ;
1493 item_len = le16_to_cpu (PATH_PITEM_HEAD (&path)->ih_item_len);
1494 init_tb_struct (th, &tb, th->t_super, &path, - (IH_SIZE + item_len));
1495 }
1496
1497 retval = fix_nodes (M_DELETE, &tb, NULL, 0);
1498 if (retval == REPEAT_SEARCH)
1499 continue;
1500
1501 if (retval == CARRY_ON) {
1502 do_balance (&tb, 0, 0, M_DELETE);
1503 break;
1504 }
1505
1506 // IO_ERROR, NO_DISK_SPACE, etc
1507 reiserfs_warning ("vs-: reiserfs_delete_solid_item: "
1508 "could not delete %K due to fix_nodes failure\n", &cpu_key);
1509 unfix_nodes (&tb);
1510 break;
1511 }
1512
1513 reiserfs_check_path(&path) ;
1514 }
1515
1516
1517 void reiserfs_delete_object (struct reiserfs_transaction_handle *th, struct inode * inode)
1518 {
1519 inode->i_size = 0;
1520
1521 /* for directory this deletes item containing "." and ".." */
1522 reiserfs_do_truncate (th, inode, NULL, 0/*no timestamp updates*/);
1523
1524 /* delete stat data */
1525 /* this debug code needs to go away. Trying to find a truncate race
1526 ** -- clm -- 4/1/2000
1527 */
1528 #if 0
1529 if (inode->i_nlink != 0) {
1530 reiserfs_warning("clm-4001: deleting inode with link count==%d\n", inode->i_nlink) ;
1531 }
1532 #endif
1533 #if defined( USE_INODE_GENERATION_COUNTER )
1534 if( !old_format_only ( th -> t_super ) )
1535 {
1536 __u32 *inode_generation;
1537
1538 inode_generation =
1539 &th -> t_super -> u.reiserfs_sb.s_rs -> s_inode_generation;
1540 *inode_generation = cpu_to_le32( le32_to_cpu( *inode_generation ) + 1 );
1541 }
1542 /* USE_INODE_GENERATION_COUNTER */
1543 #endif
1544 reiserfs_delete_solid_item (th, INODE_PKEY (inode));
1545 }
1546
1547
1548 static int maybe_indirect_to_direct (struct reiserfs_transaction_handle *th,
1549 struct inode * p_s_inode,
1550 struct page *page,
1551 struct path * p_s_path,
1552 struct cpu_key * p_s_item_key,
1553 loff_t n_new_file_size,
1554 char * p_c_mode
1555 ) {
1556 struct super_block * p_s_sb = p_s_inode->i_sb;
1557 int n_block_size = p_s_sb->s_blocksize;
1558 int cut_bytes;
1559
1560 if (n_new_file_size != p_s_inode->i_size)
1561 BUG ();
1562
1563 /* the page being sent in could be NULL if there was an i/o error
1564 ** reading in the last block. The user will hit problems trying to
1565 ** read the file, but for now we just skip the indirect2direct
1566 */
1567 if (atomic_read(&p_s_inode->i_count) > 1 ||
1568 !tail_has_to_be_packed (p_s_inode) ||
1569 !page || p_s_inode->u.reiserfs_i.nopack) {
1570 // leave tail in an unformatted node
1571 *p_c_mode = M_SKIP_BALANCING;
1572 cut_bytes = n_block_size - (n_new_file_size & (n_block_size - 1));
1573 pathrelse(p_s_path);
1574 return cut_bytes;
1575 }
1576 /* Permorm the conversion to a direct_item. */
1577 /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);*/
1578 return indirect2direct (th, p_s_inode, page, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);
1579 }
1580
1581
1582 /* we did indirect_to_direct conversion. And we have inserted direct
1583 item successesfully, but there were no disk space to cut unfm
1584 pointer being converted. Therefore we have to delete inserted
1585 direct item(s) */
1586 static void indirect_to_direct_roll_back (struct reiserfs_transaction_handle *th, struct inode * inode, struct path * path)
1587 {
1588 struct cpu_key tail_key;
1589 int tail_len;
1590 int removed;
1591
1592 make_cpu_key (&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);// !!!!
1593 tail_key.key_length = 4;
1594
1595 tail_len = (cpu_key_k_offset (&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1596 while (tail_len) {
1597 /* look for the last byte of the tail */
1598 if (search_for_position_by_key (inode->i_sb, &tail_key, path) == POSITION_NOT_FOUND)
1599 reiserfs_panic (inode->i_sb, "vs-5615: indirect_to_direct_roll_back: found invalid item");
1600 #ifdef CONFIG_REISERFS_CHECK
1601 if (path->pos_in_item != PATH_PITEM_HEAD (path)->ih_item_len - 1)
1602 reiserfs_panic (inode->i_sb, "vs-5616: indirect_to_direct_roll_back: appended bytes found");
1603 #endif
1604 PATH_LAST_POSITION (path) --;
1605
1606 removed = reiserfs_delete_item (th, path, &tail_key, inode, 0/*unbh not needed*/);
1607 #ifdef CONFIG_REISERFS_CHECK
1608 if (removed <= 0 || removed > tail_len)
1609 reiserfs_panic (inode->i_sb, "vs-5617: indirect_to_direct_roll_back: "
1610 "there was tail %d bytes, removed item length %d bytes",
1611 tail_len, removed);
1612 #endif
1613 tail_len -= removed;
1614 set_cpu_key_k_offset (&tail_key, cpu_key_k_offset (&tail_key) - removed);
1615 }
1616 printk ("indirect_to_direct_roll_back: indirect_to_direct conversion has been rolled back due to lack of disk space\n");
1617 //mark_file_without_tail (inode);
1618 mark_inode_dirty (inode);
1619 }
1620
1621
1622 /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
1623 int reiserfs_cut_from_item (struct reiserfs_transaction_handle *th,
1624 struct path * p_s_path,
1625 struct cpu_key * p_s_item_key,
1626 struct inode * p_s_inode,
1627 struct page *page,
1628 loff_t n_new_file_size)
1629 {
1630 struct super_block * p_s_sb = p_s_inode->i_sb;
1631 /* Every function which is going to call do_balance must first
1632 create a tree_balance structure. Then it must fill up this
1633 structure by using the init_tb_struct and fix_nodes functions.
1634 After that we can make tree balancing. */
1635 struct tree_balance s_cut_balance;
1636 int n_cut_size = 0, /* Amount to be cut. */
1637 n_ret_value = CARRY_ON,
1638 n_removed = 0, /* Number of the removed unformatted nodes. */
1639 n_is_inode_locked = 0;
1640 char c_mode; /* Mode of the balance. */
1641 int retval2 = -1;
1642
1643
1644 init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, n_cut_size);
1645
1646
1647 /* Repeat this loop until we either cut the item without needing
1648 to balance, or we fix_nodes without schedule occuring */
1649 while ( 1 ) {
1650 /* Determine the balance mode, position of the first byte to
1651 be cut, and size to be cut. In case of the indirect item
1652 free unformatted nodes which are pointed to by the cut
1653 pointers. */
1654
1655 c_mode = prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed,
1656 &n_cut_size, n_new_file_size);
1657 if ( c_mode == M_CONVERT ) {
1658 /* convert last unformatted node to direct item or leave
1659 tail in the unformatted node */
1660 #ifdef CONFIG_REISERFS_CHECK
1661 if ( n_ret_value != CARRY_ON )
1662 reiserfs_panic (p_s_sb, "PAP-5570: reiserfs_cut_from_item: can not convert twice");
1663 #endif
1664
1665 n_ret_value = maybe_indirect_to_direct (th, p_s_inode, page, p_s_path, p_s_item_key,
1666 n_new_file_size, &c_mode);
1667 if ( c_mode == M_SKIP_BALANCING )
1668 /* tail has been left in the unformatted node */
1669 return n_ret_value;
1670
1671 n_is_inode_locked = 1;
1672
1673 /* removing of last unformatted node will change value we
1674 have to return to truncate. Save it */
1675 retval2 = n_ret_value;
1676 /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1));*/
1677
1678 /* So, we have performed the first part of the conversion:
1679 inserting the new direct item. Now we are removing the
1680 last unformatted node pointer. Set key to search for
1681 it. */
1682 set_cpu_key_k_type (p_s_item_key, TYPE_INDIRECT);
1683 p_s_item_key->key_length = 4;
1684 n_new_file_size -= (n_new_file_size & (p_s_sb->s_blocksize - 1));
1685 set_cpu_key_k_offset (p_s_item_key, n_new_file_size + 1);
1686 if ( search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_NOT_FOUND ){
1687 print_block (PATH_PLAST_BUFFER (p_s_path), 3, PATH_LAST_POSITION (p_s_path) - 1, PATH_LAST_POSITION (p_s_path) + 1);
1688 reiserfs_panic(p_s_sb, "PAP-5580: reiserfs_cut_from_item: item to convert does not exist (%k)", p_s_item_key);
1689 }
1690 continue;
1691 }
1692 if (n_cut_size == 0) {
1693 pathrelse (p_s_path);
1694 return 0;
1695 }
1696
1697 s_cut_balance.insert_size[0] = n_cut_size;
1698
1699 n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, 0);
1700 if ( n_ret_value != REPEAT_SEARCH )
1701 break;
1702
1703 n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1704 if (n_ret_value == POSITION_FOUND)
1705 continue;
1706
1707 reiserfs_warning ("PAP-5610: reiserfs_cut_from_item: item %K not found\n", p_s_item_key);
1708 unfix_nodes (&s_cut_balance);
1709 return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
1710 } /* while */
1711
1712 // check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
1713 if ( n_ret_value != CARRY_ON ) {
1714 if ( n_is_inode_locked ) {
1715 // FIXME: this seems to be not needed: we are always able
1716 // to cut item
1717 indirect_to_direct_roll_back (th, p_s_inode, p_s_path);
1718 }
1719 if (n_ret_value == NO_DISK_SPACE)
1720 reiserfs_warning ("");
1721 unfix_nodes (&s_cut_balance);
1722 return -EIO;
1723 }
1724
1725 /* go ahead and perform balancing */
1726
1727 #ifdef CONFIG_REISERFS_CHECK
1728 if ( c_mode == M_PASTE || c_mode == M_INSERT )
1729 reiserfs_panic (p_s_sb, "PAP-5640: reiserfs_cut_from_item: illegal mode");
1730 #endif
1731
1732 /* Calculate number of bytes that need to be cut from the item. */
1733 if (retval2 == -1)
1734 n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
1735 else
1736 n_ret_value = retval2;
1737
1738 if ( c_mode == M_DELETE ) {
1739 struct item_head * p_le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
1740
1741 if ( is_direct_le_ih (p_le_ih) && (le_ih_k_offset (p_le_ih) & (p_s_sb->s_blocksize - 1)) == 1 ) {
1742 /* we delete first part of tail which was stored in direct
1743 item(s) */
1744 // FIXME: this is to keep 3.5 happy
1745 p_s_inode->u.reiserfs_i.i_first_direct_byte = U32_MAX;
1746 p_s_inode->i_blocks -= p_s_sb->s_blocksize / 512;
1747 }
1748 }
1749
1750 #ifdef CONFIG_REISERFS_CHECK
1751 if (n_is_inode_locked) {
1752 struct item_head * le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
1753 /* we are going to complete indirect2direct conversion. Make
1754 sure, that we exactly remove last unformatted node pointer
1755 of the item */
1756 if (!is_indirect_le_ih (le_ih))
1757 reiserfs_panic (p_s_sb, "vs-5652: reiserfs_cut_from_item: "
1758 "item must be indirect %h", le_ih);
1759
1760 if (c_mode == M_DELETE && le16_to_cpu (le_ih->ih_item_len) != UNFM_P_SIZE)
1761 reiserfs_panic (p_s_sb, "vs-5653: reiserfs_cut_from_item: "
1762 "completing indirect2direct conversion indirect item %h"
1763 "being deleted must be of 4 byte long", le_ih);
1764
1765 if (c_mode == M_CUT && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
1766 reiserfs_panic (p_s_sb, "vs-5654: reiserfs_cut_from_item: "
1767 "can not complete indirect2direct conversion of %h (CUT, insert_size==%d)",
1768 le_ih, s_cut_balance.insert_size[0]);
1769 }
1770 /* it would be useful to make sure, that right neighboring
1771 item is direct item of this file */
1772 }
1773 #endif
1774
1775 do_balance(&s_cut_balance, NULL, NULL, c_mode);
1776 if ( n_is_inode_locked ) {
1777 /* we've done an indirect->direct conversion. when the data block
1778 ** was freed, it was removed from the list of blocks that must
1779 ** be flushed before the transaction commits, so we don't need to
1780 ** deal with it here.
1781 */
1782 p_s_inode->u.reiserfs_i.i_pack_on_close = 0 ;
1783 }
1784 return n_ret_value;
1785 }
1786
1787
1788 static void truncate_directory (struct reiserfs_transaction_handle *th, struct inode * inode)
1789 {
1790 if (inode->i_nlink)
1791 reiserfs_warning ("vs-5655: truncate_directory: link count != 0");
1792
1793 set_le_key_k_offset (ITEM_VERSION_1, INODE_PKEY (inode), DOT_OFFSET);
1794 set_le_key_k_type (ITEM_VERSION_1, INODE_PKEY (inode), TYPE_DIRENTRY);
1795 reiserfs_delete_solid_item (th, INODE_PKEY (inode));
1796
1797 set_le_key_k_offset (ITEM_VERSION_1, INODE_PKEY (inode), SD_OFFSET);
1798 set_le_key_k_type (ITEM_VERSION_1, INODE_PKEY (inode), TYPE_STAT_DATA);
1799 }
1800
1801
1802
1803
1804 /* Truncate file to the new size. Note, this must be called with a transaction
1805 already started */
1806 void reiserfs_do_truncate (struct reiserfs_transaction_handle *th,
1807 struct inode * p_s_inode, /* ->i_size contains new
1808 size */
1809 struct page *page, /* up to date for last block */
1810 int update_timestamps /* when it is called by
1811 file_release to convert
1812 the tail - no timestamps
1813 should be updated */
1814 ) {
1815 INITIALIZE_PATH (s_search_path); /* Path to the current object item. */
1816 struct item_head * p_le_ih; /* Pointer to an item header. */
1817 struct cpu_key s_item_key; /* Key to search for a previous file item. */
1818 loff_t n_file_size, /* Old file size. */
1819 n_new_file_size;/* New file size. */
1820 int n_deleted; /* Number of deleted or truncated bytes. */
1821 int retval;
1822
1823 if ( ! (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) || S_ISLNK(p_s_inode->i_mode)) )
1824 return;
1825
1826 if (S_ISDIR(p_s_inode->i_mode)) {
1827 // deletion of directory - no need to update timestamps
1828 truncate_directory (th, p_s_inode);
1829 return;
1830 }
1831
1832 /* Get new file size. */
1833 n_new_file_size = p_s_inode->i_size;
1834
1835 // FIXME: note, that key type is unimportant here
1836 make_cpu_key (&s_item_key, p_s_inode, max_reiserfs_offset (p_s_inode), TYPE_DIRECT, 3);
1837
1838 retval = search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path);
1839 if (retval == IO_ERROR) {
1840 reiserfs_warning ("vs-5657: reiserfs_do_truncate: "
1841 "i/o failure occurred trying to truncate %K\n", &s_item_key);
1842 return;
1843 }
1844 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
1845 pathrelse (&s_search_path);
1846 reiserfs_warning ("PAP-5660: reiserfs_do_truncate: "
1847 "wrong result %d of search for %K\n", retval, &s_item_key);
1848 return;
1849 }
1850
1851 s_search_path.pos_in_item --;
1852
1853 /* Get real file size (total length of all file items) */
1854 p_le_ih = PATH_PITEM_HEAD(&s_search_path);
1855 if ( is_statdata_le_ih (p_le_ih) )
1856 n_file_size = 0;
1857 else {
1858 loff_t offset = le_ih_k_offset (p_le_ih);
1859 int bytes = op_bytes_number (p_le_ih,p_s_inode->i_sb->s_blocksize);
1860
1861 /* this may mismatch with real file size: if last direct item
1862 had no padding zeros and last unformatted node had no free
1863 space, this file would have this file size */
1864 n_file_size = offset + bytes - 1;
1865 }
1866
1867 if ( n_file_size == 0 || n_file_size < n_new_file_size ) {
1868 pathrelse(&s_search_path);
1869 return;
1870 }
1871 /* Update key to search for the last file item. */
1872 set_cpu_key_k_offset (&s_item_key, n_file_size);
1873
1874 do {
1875 /* Cut or delete file item. */
1876 n_deleted = reiserfs_cut_from_item(th, &s_search_path, &s_item_key, p_s_inode, page, n_new_file_size);
1877 if (n_deleted < 0) {
1878 reiserfs_warning ("vs-5665: reiserfs_truncate_file: cut_from_item failed");
1879 reiserfs_check_path(&s_search_path) ;
1880 return;
1881 }
1882
1883 #ifdef CONFIG_REISERFS_CHECK
1884 if ( n_deleted > n_file_size ){
1885 reiserfs_panic (p_s_inode->i_sb, "PAP-5670: reiserfs_truncate_file: "
1886 "reiserfs_truncate_file returns too big number: deleted %d, file_size %lu, item_key %k",
1887 n_deleted, n_file_size, &s_item_key);
1888 }
1889 #endif
1890
1891 /* Change key to search the last file item. */
1892 n_file_size -= n_deleted;
1893
1894 set_cpu_key_k_offset (&s_item_key, n_file_size);
1895
1896 /* While there are bytes to truncate and previous file item is presented in the tree. */
1897
1898 /*
1899 ** This loop could take a really long time, and could log
1900 ** many more blocks than a transaction can hold. So, we do a polite
1901 ** journal end here, and if the transaction needs ending, we make
1902 ** sure the file is consistent before ending the current trans
1903 ** and starting a new one
1904 */
1905 if (journal_transaction_should_end(th, th->t_blocks_allocated)) {
1906 int orig_len_alloc = th->t_blocks_allocated ;
1907 decrement_counters_in_path(&s_search_path) ;
1908
1909 if (update_timestamps) {
1910 p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
1911 // FIXME: sd gets wrong size here
1912 }
1913 reiserfs_update_sd(th, p_s_inode) ;
1914
1915 journal_end(th, p_s_inode->i_sb, orig_len_alloc) ;
1916 journal_begin(th, p_s_inode->i_sb, orig_len_alloc) ;
1917 }
1918 } while ( n_file_size > ROUND_UP (n_new_file_size) &&
1919 search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path) == POSITION_FOUND ) ;
1920
1921 #ifdef CONFIG_REISERFS_CHECK
1922 if ( n_file_size > ROUND_UP (n_new_file_size) )
1923 reiserfs_panic (p_s_inode->i_sb, "PAP-5680: reiserfs_truncate_file: "
1924 "truncate did not finish: new_file_size %Ld, current %Ld, oid %d\n",
1925 n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);
1926 #endif
1927
1928 if (update_timestamps) {
1929 // this is truncate, not file closing
1930 p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
1931 }
1932 reiserfs_update_sd (th, p_s_inode);
1933
1934 pathrelse(&s_search_path) ;
1935 }
1936
1937
1938 #ifdef CONFIG_REISERFS_CHECK
1939 // this makes sure, that we __append__, not overwrite or add holes
1940 static void check_research_for_paste (struct path * path, struct cpu_key * p_s_key)
1941 {
1942 struct item_head * found_ih = get_ih (path);
1943
1944 if (is_direct_le_ih (found_ih)) {
1945 if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) !=
1946 cpu_key_k_offset (p_s_key) ||
1947 op_bytes_number (found_ih, get_last_bh (path)->b_size) != pos_in_item (path))
1948 reiserfs_panic (0, "PAP-5720: check_research_for_paste: "
1949 "found direct item %h or position (%d) does not match to key %K",
1950 found_ih, pos_in_item (path), p_s_key);
1951 }
1952 if (is_indirect_le_ih (found_ih)) {
1953 if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) != cpu_key_k_offset (p_s_key) ||
1954 I_UNFM_NUM (found_ih) != pos_in_item (path) ||
1955 get_ih_free_space (found_ih) != 0)
1956 reiserfs_panic (0, "PAP-5730: check_research_for_paste: "
1957 "found indirect item (%h) or position (%d) does not match to key (%K)",
1958 found_ih, pos_in_item (path), p_s_key);
1959 }
1960 }
1961 #endif /* config reiserfs check */
1962
1963
1964 /* Paste bytes to the existing item. Returns bytes number pasted into the item. */
1965 int reiserfs_paste_into_item (struct reiserfs_transaction_handle *th,
1966 struct path * p_s_search_path, /* Path to the pasted item. */
1967 struct cpu_key * p_s_key, /* Key to search for the needed item.*/
1968 const char * p_c_body, /* Pointer to the bytes to paste. */
1969 int n_pasted_size) /* Size of pasted bytes. */
1970 {
1971 struct tree_balance s_paste_balance;
1972 int retval;
1973
1974 init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, n_pasted_size);
1975
1976 while ( (retval = fix_nodes(M_PASTE, &s_paste_balance, NULL, p_c_body)) == REPEAT_SEARCH ) {
1977 /* file system changed while we were in the fix_nodes */
1978 retval = search_for_position_by_key (th->t_super, p_s_key, p_s_search_path);
1979 if (retval == IO_ERROR) {
1980 retval = -EIO ;
1981 goto error_out ;
1982 }
1983 if (retval == POSITION_FOUND) {
1984 reiserfs_warning ("PAP-5710: reiserfs_paste_into_item: entry or pasted byte (%K) exists", p_s_key);
1985 retval = -EEXIST ;
1986 goto error_out ;
1987 }
1988
1989 #ifdef CONFIG_REISERFS_CHECK
1990 check_research_for_paste (p_s_search_path, p_s_key);
1991 #endif
1992 }
1993
1994 /* Perform balancing after all resources are collected by fix_nodes, and
1995 accessing them will not risk triggering schedule. */
1996 if ( retval == CARRY_ON ) {
1997 do_balance(&s_paste_balance, NULL/*ih*/, p_c_body, M_PASTE);
1998 return 0;
1999 }
2000 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2001 error_out:
2002 /* this also releases the path */
2003 unfix_nodes(&s_paste_balance);
2004 return retval ;
2005 }
2006
2007
2008 /* Insert new item into the buffer at the path. */
2009 int reiserfs_insert_item(struct reiserfs_transaction_handle *th,
2010 struct path * p_s_path, /* Path to the inserteded item. */
2011 struct cpu_key * key,
2012 struct item_head * p_s_ih, /* Pointer to the item header to insert.*/
2013 const char * p_c_body) /* Pointer to the bytes to insert. */
2014 {
2015 struct tree_balance s_ins_balance;
2016 int retval;
2017
2018 init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, IH_SIZE + p_s_ih->ih_item_len);
2019
2020 /*
2021 if (p_c_body == 0)
2022 n_zeros_num = p_s_ih->ih_item_len;
2023 */
2024 // le_key2cpu_key (&key, &(p_s_ih->ih_key));
2025
2026 while ( (retval = fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, p_c_body)) == REPEAT_SEARCH) {
2027 /* file system changed while we were in the fix_nodes */
2028 retval = search_item (th->t_super, key, p_s_path);
2029 if (retval == IO_ERROR) {
2030 retval = -EIO;
2031 goto error_out ;
2032 }
2033 if (retval == ITEM_FOUND) {
2034 reiserfs_warning ("PAP-5760: reiserfs_insert_item: "
2035 "key %K already exists in the tree\n", key);
2036 retval = -EEXIST ;
2037 goto error_out;
2038 }
2039 }
2040
2041 /* make balancing after all resources will be collected at a time */
2042 if ( retval == CARRY_ON ) {
2043 do_balance (&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
2044 return 0;
2045 }
2046
2047 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2048 error_out:
2049 /* also releases the path */
2050 unfix_nodes(&s_ins_balance);
2051 return retval;
2052 }
2053
2054
2055
2056
2057