blob: d2b25e1ba6e9739c5bd49b58945d50a7956fb74d [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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_item_head
16 * comp_short_keys
17 * comp_keys
18 * comp_short_le_keys
19 * le_key2cpu_key
20 * comp_le_keys
21 * bin_search
22 * get_lkey
23 * get_rkey
24 * key_in_buffer
25 * decrement_bcount
26 * decrement_counters_in_path
27 * reiserfs_check_path
28 * pathrelse_and_restore
29 * pathrelse
30 * search_by_key_reada
31 * search_by_key
32 * search_for_position_by_key
33 * comp_items
34 * prepare_for_direct_item
35 * prepare_for_direntry_item
36 * prepare_for_delete_or_cut
37 * calc_deleted_bytes_number
38 * init_tb_struct
39 * padd_item
40 * reiserfs_delete_item
41 * reiserfs_delete_solid_item
42 * reiserfs_delete_object
43 * maybe_indirect_to_direct
44 * indirect_to_direct_roll_back
45 * reiserfs_cut_from_item
46 * truncate_directory
47 * reiserfs_do_truncate
48 * reiserfs_paste_into_item
49 * reiserfs_insert_item
50 */
51
52#include <linux/config.h>
53#include <linux/time.h>
54#include <linux/string.h>
55#include <linux/pagemap.h>
56#include <linux/reiserfs_fs.h>
57#include <linux/smp_lock.h>
58#include <linux/buffer_head.h>
59#include <linux/quotaops.h>
60
61/* Does the buffer contain a disk block which is in the tree. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070062inline int B_IS_IN_TREE(const struct buffer_head *p_s_bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -070063{
64
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070065 RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT,
66 "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -070067
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070068 return (B_LEVEL(p_s_bh) != FREE_LEVEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070069}
70
71//
72// to gets item head in le form
73//
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070074inline void copy_item_head(struct item_head *p_v_to,
75 const struct item_head *p_v_from)
Linus Torvalds1da177e2005-04-16 15:20:36 -070076{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070077 memcpy(p_v_to, p_v_from, IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -070078}
79
Linus Torvalds1da177e2005-04-16 15:20:36 -070080/* k1 is pointer to on-disk structure which is stored in little-endian
81 form. k2 is pointer to cpu variable. For key of items of the same
82 object this returns 0.
83 Returns: -1 if key1 < key2
84 0 if key1 == key2
85 1 if key1 > key2 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070086inline int comp_short_keys(const struct reiserfs_key *le_key,
87 const struct cpu_key *cpu_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -070088{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070089 __u32 n;
90 n = le32_to_cpu(le_key->k_dir_id);
91 if (n < cpu_key->on_disk_key.k_dir_id)
92 return -1;
93 if (n > cpu_key->on_disk_key.k_dir_id)
94 return 1;
95 n = le32_to_cpu(le_key->k_objectid);
96 if (n < cpu_key->on_disk_key.k_objectid)
97 return -1;
98 if (n > cpu_key->on_disk_key.k_objectid)
99 return 1;
100 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101}
102
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103/* k1 is pointer to on-disk structure which is stored in little-endian
104 form. k2 is pointer to cpu variable.
105 Compare keys using all 4 key fields.
106 Returns: -1 if key1 < key2 0
107 if key1 = key2 1 if key1 > key2 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700108static inline int comp_keys(const struct reiserfs_key *le_key,
109 const struct cpu_key *cpu_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700111 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700113 retval = comp_short_keys(le_key, cpu_key);
114 if (retval)
115 return retval;
116 if (le_key_k_offset(le_key_version(le_key), le_key) <
117 cpu_key_k_offset(cpu_key))
118 return -1;
119 if (le_key_k_offset(le_key_version(le_key), le_key) >
120 cpu_key_k_offset(cpu_key))
121 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700123 if (cpu_key->key_length == 3)
124 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700126 /* this part is needed only when tail conversion is in progress */
127 if (le_key_k_type(le_key_version(le_key), le_key) <
128 cpu_key_k_type(cpu_key))
129 return -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700131 if (le_key_k_type(le_key_version(le_key), le_key) >
132 cpu_key_k_type(cpu_key))
133 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700135 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136}
137
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700138inline int comp_short_le_keys(const struct reiserfs_key *key1,
139 const struct reiserfs_key *key2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700141 __u32 *p_s_1_u32, *p_s_2_u32;
142 int n_key_length = REISERFS_SHORT_KEY_LEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700144 p_s_1_u32 = (__u32 *) key1;
145 p_s_2_u32 = (__u32 *) key2;
146 for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) {
147 if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32))
148 return -1;
149 if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32))
150 return 1;
151 }
152 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153}
154
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700155inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700157 int version;
158 to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
159 to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);
160
161 // find out version of the key
162 version = le_key_version(from);
163 to->version = version;
164 to->on_disk_key.k_offset = le_key_k_offset(version, from);
165 to->on_disk_key.k_type = le_key_k_type(version, from);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166}
167
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168// this does not say which one is bigger, it only returns 1 if keys
169// are not equal, 0 otherwise
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700170inline int comp_le_keys(const struct reiserfs_key *k1,
171 const struct reiserfs_key *k2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700172{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700173 return memcmp(k1, k2, sizeof(struct reiserfs_key));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174}
175
176/**************************************************************************
177 * Binary search toolkit function *
178 * Search for an item in the array by the item key *
179 * Returns: 1 if found, 0 if not found; *
180 * *p_n_pos = number of the searched element if found, else the *
181 * number of the first element that is larger than p_v_key. *
182 **************************************************************************/
183/* For those not familiar with binary search: n_lbound is the leftmost item that it
184 could be, n_rbound the rightmost item that it could be. We examine the item
185 halfway between n_lbound and n_rbound, and that tells us either that we can increase
186 n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
187 there are no possible items, and we have not found it. With each examination we
188 cut the number of possible items it could be by one more than half rounded down,
189 or we find it. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700190static inline int bin_search(const void *p_v_key, /* Key to search for. */
191 const void *p_v_base, /* First item in the array. */
192 int p_n_num, /* Number of items in the array. */
193 int p_n_width, /* Item size in the array.
194 searched. Lest the reader be
195 confused, note that this is crafted
196 as a general function, and when it
197 is applied specifically to the array
198 of item headers in a node, p_n_width
199 is actually the item header size not
200 the item size. */
201 int *p_n_pos /* Number of the searched for element. */
202 )
203{
204 int n_rbound, n_lbound, n_j;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700206 for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2;
207 n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2)
208 switch (comp_keys
209 ((struct reiserfs_key *)((char *)p_v_base +
210 n_j * p_n_width),
211 (struct cpu_key *)p_v_key)) {
212 case -1:
213 n_lbound = n_j + 1;
214 continue;
215 case 1:
216 n_rbound = n_j - 1;
217 continue;
218 case 0:
219 *p_n_pos = n_j;
220 return ITEM_FOUND; /* Key found in the array. */
221 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700223 /* bin_search did not find given key, it returns position of key,
224 that is minimal and greater than the given one. */
225 *p_n_pos = n_lbound;
226 return ITEM_NOT_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227}
228
229#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700230extern struct tree_balance *cur_tb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700231#endif
232
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233/* Minimal possible key. It is never in the tree. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700234const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235
236/* Maximal possible key. It is never in the tree. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700237static const struct reiserfs_key MAX_KEY = {
Al Viro3e8962b2005-05-01 08:59:18 -0700238 __constant_cpu_to_le32(0xffffffff),
239 __constant_cpu_to_le32(0xffffffff),
240 {{__constant_cpu_to_le32(0xffffffff),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700241 __constant_cpu_to_le32(0xffffffff)},}
Al Viro3e8962b2005-05-01 08:59:18 -0700242};
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244/* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
245 of the path, and going upwards. We must check the path's validity at each step. If the key is not in
246 the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
247 case we return a special key, either MIN_KEY or MAX_KEY. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700248static inline const struct reiserfs_key *get_lkey(const struct path
249 *p_s_chk_path,
250 const struct super_block
251 *p_s_sb)
252{
253 int n_position, n_path_offset = p_s_chk_path->path_length;
254 struct buffer_head *p_s_parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700256 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
257 "PAP-5010: invalid offset in the path");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700259 /* While not higher in path than first element. */
260 while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700262 RFALSE(!buffer_uptodate
263 (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
264 "PAP-5020: parent is not uptodate");
265
266 /* Parent at the path is not in the tree now. */
267 if (!B_IS_IN_TREE
268 (p_s_parent =
269 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
270 return &MAX_KEY;
271 /* Check whether position in the parent is correct. */
272 if ((n_position =
273 PATH_OFFSET_POSITION(p_s_chk_path,
274 n_path_offset)) >
275 B_NR_ITEMS(p_s_parent))
276 return &MAX_KEY;
277 /* Check whether parent at the path really points to the child. */
278 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
279 PATH_OFFSET_PBUFFER(p_s_chk_path,
280 n_path_offset + 1)->b_blocknr)
281 return &MAX_KEY;
282 /* Return delimiting key if position in the parent is not equal to zero. */
283 if (n_position)
284 return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
285 }
286 /* Return MIN_KEY if we are in the root of the buffer tree. */
287 if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
288 b_blocknr == SB_ROOT_BLOCK(p_s_sb))
289 return &MIN_KEY;
290 return &MAX_KEY;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291}
292
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293/* Get delimiting key of the buffer at the path and its right neighbor. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700294inline const struct reiserfs_key *get_rkey(const struct path *p_s_chk_path,
295 const struct super_block *p_s_sb)
296{
297 int n_position, n_path_offset = p_s_chk_path->path_length;
298 struct buffer_head *p_s_parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700300 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
301 "PAP-5030: invalid offset in the path");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700303 while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700304
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700305 RFALSE(!buffer_uptodate
306 (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
307 "PAP-5040: parent is not uptodate");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700309 /* Parent at the path is not in the tree now. */
310 if (!B_IS_IN_TREE
311 (p_s_parent =
312 PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
313 return &MIN_KEY;
314 /* Check whether position in the parent is correct. */
315 if ((n_position =
316 PATH_OFFSET_POSITION(p_s_chk_path,
317 n_path_offset)) >
318 B_NR_ITEMS(p_s_parent))
319 return &MIN_KEY;
320 /* Check whether parent at the path really points to the child. */
321 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
322 PATH_OFFSET_PBUFFER(p_s_chk_path,
323 n_path_offset + 1)->b_blocknr)
324 return &MIN_KEY;
325 /* Return delimiting key if position in the parent is not the last one. */
326 if (n_position != B_NR_ITEMS(p_s_parent))
327 return B_N_PDELIM_KEY(p_s_parent, n_position);
328 }
329 /* Return MAX_KEY if we are in the root of the buffer tree. */
330 if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
331 b_blocknr == SB_ROOT_BLOCK(p_s_sb))
332 return &MAX_KEY;
333 return &MIN_KEY;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334}
335
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336/* Check whether a key is contained in the tree rooted from a buffer at a path. */
337/* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
338 the path. These delimiting keys are stored at least one level above that buffer in the tree. If the
339 buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
340 this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700341static inline int key_in_buffer(struct path *p_s_chk_path, /* Path which should be checked. */
342 const struct cpu_key *p_s_key, /* Key which should be checked. */
343 struct super_block *p_s_sb /* Super block pointer. */
344 )
345{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700347 RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
348 || p_s_chk_path->path_length > MAX_HEIGHT,
349 "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
350 p_s_key, p_s_chk_path->path_length);
351 RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev,
352 "PAP-5060: device must not be NODEV");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700354 if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1)
355 /* left delimiting key is bigger, that the key we look for */
356 return 0;
357 // if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
358 if (comp_keys(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1)
359 /* p_s_key must be less than right delimitiing key */
360 return 0;
361 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362}
363
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700364inline void decrement_bcount(struct buffer_head *p_s_bh)
365{
366 if (p_s_bh) {
367 if (atomic_read(&(p_s_bh->b_count))) {
368 put_bh(p_s_bh);
369 return;
370 }
371 reiserfs_panic(NULL,
372 "PAP-5070: decrement_bcount: trying to free free buffer %b",
373 p_s_bh);
374 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700375}
376
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377/* Decrement b_count field of the all buffers in the path. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700378void decrement_counters_in_path(struct path *p_s_search_path)
379{
380 int n_path_offset = p_s_search_path->path_length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700382 RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
383 n_path_offset > EXTENDED_MAX_HEIGHT - 1,
384 "PAP-5080: invalid path offset of %d", n_path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700386 while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
387 struct buffer_head *bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700389 bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
390 decrement_bcount(bh);
391 }
392 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393}
394
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700395int reiserfs_check_path(struct path *p)
396{
397 RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
398 "path not properly relsed");
399 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400}
401
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402/* Release all buffers in the path. Restore dirty bits clean
403** when preparing the buffer for the log
404**
405** only called from fix_nodes()
406*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700407void pathrelse_and_restore(struct super_block *s, struct path *p_s_search_path)
408{
409 int n_path_offset = p_s_search_path->path_length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700411 RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
412 "clm-4000: invalid path offset");
413
414 while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
415 reiserfs_restore_prepared_buffer(s,
416 PATH_OFFSET_PBUFFER
417 (p_s_search_path,
418 n_path_offset));
419 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
420 }
421 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422}
423
424/* Release all buffers in the path. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700425void pathrelse(struct path *p_s_search_path)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700427 int n_path_offset = p_s_search_path->path_length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700429 RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
430 "PAP-5090: invalid path offset");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
433 brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700434
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700435 p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436}
437
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700438static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
439{
440 struct block_head *blkh;
441 struct item_head *ih;
442 int used_space;
443 int prev_location;
444 int i;
445 int nr;
446
447 blkh = (struct block_head *)buf;
448 if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
449 reiserfs_warning(NULL,
450 "is_leaf: this should be caught earlier");
451 return 0;
452 }
453
454 nr = blkh_nr_item(blkh);
455 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
456 /* item number is too big or too small */
457 reiserfs_warning(NULL, "is_leaf: nr_item seems wrong: %z", bh);
458 return 0;
459 }
460 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
461 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
462 if (used_space != blocksize - blkh_free_space(blkh)) {
463 /* free space does not match to calculated amount of use space */
464 reiserfs_warning(NULL, "is_leaf: free space seems wrong: %z",
465 bh);
466 return 0;
467 }
468 // FIXME: it is_leaf will hit performance too much - we may have
469 // return 1 here
470
471 /* check tables of item heads */
472 ih = (struct item_head *)(buf + BLKH_SIZE);
473 prev_location = blocksize;
474 for (i = 0; i < nr; i++, ih++) {
475 if (le_ih_k_type(ih) == TYPE_ANY) {
476 reiserfs_warning(NULL,
477 "is_leaf: wrong item type for item %h",
478 ih);
479 return 0;
480 }
481 if (ih_location(ih) >= blocksize
482 || ih_location(ih) < IH_SIZE * nr) {
483 reiserfs_warning(NULL,
484 "is_leaf: item location seems wrong: %h",
485 ih);
486 return 0;
487 }
488 if (ih_item_len(ih) < 1
489 || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
490 reiserfs_warning(NULL,
491 "is_leaf: item length seems wrong: %h",
492 ih);
493 return 0;
494 }
495 if (prev_location - ih_location(ih) != ih_item_len(ih)) {
496 reiserfs_warning(NULL,
497 "is_leaf: item location seems wrong (second one): %h",
498 ih);
499 return 0;
500 }
501 prev_location = ih_location(ih);
502 }
503
504 // one may imagine much more checks
505 return 1;
506}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700507
508/* returns 1 if buf looks like an internal node, 0 otherwise */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700509static int is_internal(char *buf, int blocksize, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700511 struct block_head *blkh;
512 int nr;
513 int used_space;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700515 blkh = (struct block_head *)buf;
516 nr = blkh_level(blkh);
517 if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
518 /* this level is not possible for internal nodes */
519 reiserfs_warning(NULL,
520 "is_internal: this should be caught earlier");
521 return 0;
522 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700523
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700524 nr = blkh_nr_item(blkh);
525 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
526 /* for internal which is not root we might check min number of keys */
527 reiserfs_warning(NULL,
528 "is_internal: number of key seems wrong: %z",
529 bh);
530 return 0;
531 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700533 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
534 if (used_space != blocksize - blkh_free_space(blkh)) {
535 reiserfs_warning(NULL,
536 "is_internal: free space seems wrong: %z", bh);
537 return 0;
538 }
539 // one may imagine much more checks
540 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541}
542
Linus Torvalds1da177e2005-04-16 15:20:36 -0700543// make sure that bh contains formatted node of reiserfs tree of
544// 'level'-th level
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700545static int is_tree_node(struct buffer_head *bh, int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700546{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700547 if (B_LEVEL(bh) != level) {
548 reiserfs_warning(NULL,
549 "is_tree_node: node level %d does not match to the expected one %d",
550 B_LEVEL(bh), level);
551 return 0;
552 }
553 if (level == DISK_LEAF_NODE_LEVEL)
554 return is_leaf(bh->b_data, bh->b_size, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700556 return is_internal(bh->b_data, bh->b_size, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557}
558
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559#define SEARCH_BY_KEY_READA 16
560
561/* The function is NOT SCHEDULE-SAFE! */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700562static void search_by_key_reada(struct super_block *s,
563 struct buffer_head **bh,
564 unsigned long *b, int num)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700566 int i, j;
567
568 for (i = 0; i < num; i++) {
569 bh[i] = sb_getblk(s, b[i]);
570 }
571 for (j = 0; j < i; j++) {
572 /*
573 * note, this needs attention if we are getting rid of the BKL
574 * you have to make sure the prepared bit isn't set on this buffer
575 */
576 if (!buffer_uptodate(bh[j]))
577 ll_rw_block(READA, 1, bh + j);
578 brelse(bh[j]);
579 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700580}
581
582/**************************************************************************
583 * Algorithm SearchByKey *
584 * look for item in the Disk S+Tree by its key *
585 * Input: p_s_sb - super block *
586 * p_s_key - pointer to the key to search *
587 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR *
588 * p_s_search_path - path from the root to the needed leaf *
589 **************************************************************************/
590
591/* This function fills up the path from the root to the leaf as it
592 descends the tree looking for the key. It uses reiserfs_bread to
593 try to find buffers in the cache given their block number. If it
594 does not find them in the cache it reads them from disk. For each
595 node search_by_key finds using reiserfs_bread it then uses
596 bin_search to look through that node. bin_search will find the
597 position of the block_number of the next node if it is looking
598 through an internal node. If it is looking through a leaf node
599 bin_search will find the position of the item which has key either
600 equal to given key, or which is the maximal key less than the given
601 key. search_by_key returns a path that must be checked for the
602 correctness of the top of the path but need not be checked for the
603 correctness of the bottom of the path */
604/* The function is NOT SCHEDULE-SAFE! */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700605int search_by_key(struct super_block *p_s_sb, const struct cpu_key *p_s_key, /* Key to search. */
606 struct path *p_s_search_path, /* This structure was
607 allocated and initialized
608 by the calling
609 function. It is filled up
610 by this function. */
611 int n_stop_level /* How far down the tree to search. To
612 stop at leaf level - set to
613 DISK_LEAF_NODE_LEVEL */
614 )
615{
616 int n_block_number;
617 int expected_level;
618 struct buffer_head *p_s_bh;
619 struct path_element *p_s_last_element;
620 int n_node_level, n_retval;
621 int right_neighbor_of_leaf_node;
622 int fs_gen;
623 struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
624 unsigned long reada_blocks[SEARCH_BY_KEY_READA];
625 int reada_count = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626
627#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700628 int n_repeat_counter = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700631 PROC_INFO_INC(p_s_sb, search_by_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700632
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700633 /* As we add each node to a path we increase its count. This means that
634 we must be careful to release all nodes in a path before we either
635 discard the path struct or re-use the path struct, as we do here. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700637 decrement_counters_in_path(p_s_search_path);
638
639 right_neighbor_of_leaf_node = 0;
640
641 /* With each iteration of this loop we search through the items in the
642 current node, and calculate the next current node(next path element)
643 for the next iteration of this loop.. */
644 n_block_number = SB_ROOT_BLOCK(p_s_sb);
645 expected_level = -1;
646 while (1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647
648#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700649 if (!(++n_repeat_counter % 50000))
650 reiserfs_warning(p_s_sb, "PAP-5100: search_by_key: %s:"
651 "there were %d iterations of while loop "
652 "looking for key %K",
653 current->comm, n_repeat_counter,
654 p_s_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655#endif
656
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700657 /* prep path to have another element added to it. */
658 p_s_last_element =
659 PATH_OFFSET_PELEMENT(p_s_search_path,
660 ++p_s_search_path->path_length);
661 fs_gen = get_generation(p_s_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700663 /* Read the next tree node, and set the last element in the path to
664 have a pointer to it. */
665 if ((p_s_bh = p_s_last_element->pe_buffer =
666 sb_getblk(p_s_sb, n_block_number))) {
667 if (!buffer_uptodate(p_s_bh) && reada_count > 1) {
668 search_by_key_reada(p_s_sb, reada_bh,
669 reada_blocks, reada_count);
670 }
671 ll_rw_block(READ, 1, &p_s_bh);
672 wait_on_buffer(p_s_bh);
673 if (!buffer_uptodate(p_s_bh))
674 goto io_error;
675 } else {
676 io_error:
677 p_s_search_path->path_length--;
678 pathrelse(p_s_search_path);
679 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700681 reada_count = 0;
682 if (expected_level == -1)
683 expected_level = SB_TREE_HEIGHT(p_s_sb);
684 expected_level--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700686 /* It is possible that schedule occurred. We must check whether the key
687 to search is still in the tree rooted from the current buffer. If
688 not then repeat search from the root. */
689 if (fs_changed(fs_gen, p_s_sb) &&
690 (!B_IS_IN_TREE(p_s_bh) ||
691 B_LEVEL(p_s_bh) != expected_level ||
692 !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) {
693 PROC_INFO_INC(p_s_sb, search_by_key_fs_changed);
694 PROC_INFO_INC(p_s_sb, search_by_key_restarted);
695 PROC_INFO_INC(p_s_sb,
696 sbk_restarted[expected_level - 1]);
697 decrement_counters_in_path(p_s_search_path);
698
699 /* Get the root block number so that we can repeat the search
700 starting from the root. */
701 n_block_number = SB_ROOT_BLOCK(p_s_sb);
702 expected_level = -1;
703 right_neighbor_of_leaf_node = 0;
704
705 /* repeat search from the root */
706 continue;
707 }
708
709 /* only check that the key is in the buffer if p_s_key is not
710 equal to the MAX_KEY. Latter case is only possible in
711 "finish_unfinished()" processing during mount. */
712 RFALSE(comp_keys(&MAX_KEY, p_s_key) &&
713 !key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
714 "PAP-5130: key is not in the buffer");
715#ifdef CONFIG_REISERFS_CHECK
716 if (cur_tb) {
717 print_cur_tb("5140");
718 reiserfs_panic(p_s_sb,
719 "PAP-5140: search_by_key: schedule occurred in do_balance!");
720 }
721#endif
722
723 // make sure, that the node contents look like a node of
724 // certain level
725 if (!is_tree_node(p_s_bh, expected_level)) {
726 reiserfs_warning(p_s_sb, "vs-5150: search_by_key: "
727 "invalid format found in block %ld. Fsck?",
728 p_s_bh->b_blocknr);
729 pathrelse(p_s_search_path);
730 return IO_ERROR;
731 }
732
733 /* ok, we have acquired next formatted node in the tree */
734 n_node_level = B_LEVEL(p_s_bh);
735
736 PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1);
737
738 RFALSE(n_node_level < n_stop_level,
739 "vs-5152: tree level (%d) is less than stop level (%d)",
740 n_node_level, n_stop_level);
741
742 n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
743 B_NR_ITEMS(p_s_bh),
744 (n_node_level ==
745 DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
746 KEY_SIZE,
747 &(p_s_last_element->pe_position));
748 if (n_node_level == n_stop_level) {
749 return n_retval;
750 }
751
752 /* we are not in the stop level */
753 if (n_retval == ITEM_FOUND)
754 /* item has been found, so we choose the pointer which is to the right of the found one */
755 p_s_last_element->pe_position++;
756
757 /* if item was not found we choose the position which is to
758 the left of the found item. This requires no code,
759 bin_search did it already. */
760
761 /* So we have chosen a position in the current node which is
762 an internal node. Now we calculate child block number by
763 position in the node. */
764 n_block_number =
765 B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);
766
767 /* if we are going to read leaf nodes, try for read ahead as well */
768 if ((p_s_search_path->reada & PATH_READA) &&
769 n_node_level == DISK_LEAF_NODE_LEVEL + 1) {
770 int pos = p_s_last_element->pe_position;
771 int limit = B_NR_ITEMS(p_s_bh);
772 struct reiserfs_key *le_key;
773
774 if (p_s_search_path->reada & PATH_READA_BACK)
775 limit = 0;
776 while (reada_count < SEARCH_BY_KEY_READA) {
777 if (pos == limit)
778 break;
779 reada_blocks[reada_count++] =
780 B_N_CHILD_NUM(p_s_bh, pos);
781 if (p_s_search_path->reada & PATH_READA_BACK)
782 pos--;
783 else
784 pos++;
785
786 /*
787 * check to make sure we're in the same object
788 */
789 le_key = B_N_PDELIM_KEY(p_s_bh, pos);
790 if (le32_to_cpu(le_key->k_objectid) !=
791 p_s_key->on_disk_key.k_objectid) {
792 break;
793 }
794 }
795 }
796 }
797}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798
799/* Form the path to an item and position in this item which contains
800 file byte defined by p_s_key. If there is no such item
801 corresponding to the key, we point the path to the item with
802 maximal key less than p_s_key, and *p_n_pos_in_item is set to one
803 past the last entry/byte in the item. If searching for entry in a
804 directory item, and it is not found, *p_n_pos_in_item is set to one
805 entry more than the entry with maximal key which is less than the
806 sought key.
807
808 Note that if there is no entry in this same node which is one more,
809 then we point to an imaginary entry. for direct items, the
810 position is in units of bytes, for indirect items the position is
811 in units of blocknr entries, for directory items the position is in
812 units of directory entries. */
813
814/* The function is NOT SCHEDULE-SAFE! */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700815int search_for_position_by_key(struct super_block *p_s_sb, /* Pointer to the super block. */
816 const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */
817 struct path *p_s_search_path /* Filled up by this function. */
818 )
819{
820 struct item_head *p_le_ih; /* pointer to on-disk structure */
821 int n_blk_size;
822 loff_t item_offset, offset;
823 struct reiserfs_dir_entry de;
824 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700826 /* If searching for directory entry. */
827 if (is_direntry_cpu_key(p_cpu_key))
828 return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path,
829 &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700830
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700831 /* If not searching for directory entry. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700833 /* If item is found. */
834 retval = search_item(p_s_sb, p_cpu_key, p_s_search_path);
835 if (retval == IO_ERROR)
836 return retval;
837 if (retval == ITEM_FOUND) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700839 RFALSE(!ih_item_len
840 (B_N_PITEM_HEAD
841 (PATH_PLAST_BUFFER(p_s_search_path),
842 PATH_LAST_POSITION(p_s_search_path))),
843 "PAP-5165: item length equals zero");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700845 pos_in_item(p_s_search_path) = 0;
846 return POSITION_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700849 RFALSE(!PATH_LAST_POSITION(p_s_search_path),
850 "PAP-5170: position equals zero");
851
852 /* Item is not found. Set path to the previous item. */
853 p_le_ih =
854 B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
855 --PATH_LAST_POSITION(p_s_search_path));
856 n_blk_size = p_s_sb->s_blocksize;
857
858 if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) {
859 return FILE_NOT_FOUND;
860 }
861 // FIXME: quite ugly this far
862
863 item_offset = le_ih_k_offset(p_le_ih);
864 offset = cpu_key_k_offset(p_cpu_key);
865
866 /* Needed byte is contained in the item pointed to by the path. */
867 if (item_offset <= offset &&
868 item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) {
869 pos_in_item(p_s_search_path) = offset - item_offset;
870 if (is_indirect_le_ih(p_le_ih)) {
871 pos_in_item(p_s_search_path) /= n_blk_size;
872 }
873 return POSITION_FOUND;
874 }
875
876 /* Needed byte is not contained in the item pointed to by the
877 path. Set pos_in_item out of the item. */
878 if (is_indirect_le_ih(p_le_ih))
879 pos_in_item(p_s_search_path) =
880 ih_item_len(p_le_ih) / UNFM_P_SIZE;
881 else
882 pos_in_item(p_s_search_path) = ih_item_len(p_le_ih);
883
884 return POSITION_NOT_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885}
886
Linus Torvalds1da177e2005-04-16 15:20:36 -0700887/* Compare given item and item pointed to by the path. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700888int comp_items(const struct item_head *stored_ih, const struct path *p_s_path)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700890 struct buffer_head *p_s_bh;
891 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700893 /* Last buffer at the path is not in the tree. */
894 if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)))
895 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700897 /* Last path position is invalid. */
898 if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh))
899 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700901 /* we need only to know, whether it is the same item */
902 ih = get_ih(p_s_path);
903 return memcmp(stored_ih, ih, IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904}
905
Linus Torvalds1da177e2005-04-16 15:20:36 -0700906/* unformatted nodes are not logged anymore, ever. This is safe
907** now
908*/
909#define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
910
911// block can not be forgotten as it is in I/O or held by someone
912#define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
913
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914// prepare for delete or cut of direct item
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700915static inline int prepare_for_direct_item(struct path *path,
916 struct item_head *le_ih,
917 struct inode *inode,
918 loff_t new_file_length, int *cut_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700919{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700920 loff_t round_len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700922 if (new_file_length == max_reiserfs_offset(inode)) {
923 /* item has to be deleted */
924 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
925 return M_DELETE;
926 }
927 // new file gets truncated
928 if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
929 //
930 round_len = ROUND_UP(new_file_length);
931 /* this was n_new_file_length < le_ih ... */
932 if (round_len < le_ih_k_offset(le_ih)) {
933 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
934 return M_DELETE; /* Delete this item. */
935 }
936 /* Calculate first position and size for cutting from item. */
937 pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
938 *cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700940 return M_CUT; /* Cut from this item. */
941 }
942
943 // old file: items may have any length
944
945 if (new_file_length < le_ih_k_offset(le_ih)) {
946 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
947 return M_DELETE; /* Delete this item. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948 }
949 /* Calculate first position and size for cutting from item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700950 *cut_size = -(ih_item_len(le_ih) -
951 (pos_in_item(path) =
952 new_file_length + 1 - le_ih_k_offset(le_ih)));
953 return M_CUT; /* Cut from this item. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954}
955
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700956static inline int prepare_for_direntry_item(struct path *path,
957 struct item_head *le_ih,
958 struct inode *inode,
959 loff_t new_file_length,
960 int *cut_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700961{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700962 if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
963 new_file_length == max_reiserfs_offset(inode)) {
964 RFALSE(ih_entry_count(le_ih) != 2,
965 "PAP-5220: incorrect empty directory item (%h)", le_ih);
966 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
967 return M_DELETE; /* Delete the directory item containing "." and ".." entry. */
968 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700970 if (ih_entry_count(le_ih) == 1) {
971 /* Delete the directory item such as there is one record only
972 in this item */
973 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
974 return M_DELETE;
975 }
976
977 /* Cut one record from the directory item. */
978 *cut_size =
979 -(DEH_SIZE +
980 entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
981 return M_CUT;
982}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -0800984#define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
985
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986/* If the path points to a directory or direct item, calculate mode and the size cut, for balance.
987 If the path points to an indirect item, remove some number of its unformatted nodes.
988 In case of file truncate calculate whether this item must be deleted/truncated or last
989 unformatted node of this item will be converted to a direct item.
990 This function returns a determination of what balance mode the calling function should employ. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700991static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct path *p_s_path, const struct cpu_key *p_s_item_key, int *p_n_removed, /* Number of unformatted nodes which were removed
992 from end of the file. */
993 int *p_n_cut_size, unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */
994 )
995{
996 struct super_block *p_s_sb = inode->i_sb;
997 struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path);
998 struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001000 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001001
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001002 /* Stat_data item. */
1003 if (is_statdata_le_ih(p_le_ih)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001004
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001005 RFALSE(n_new_file_length != max_reiserfs_offset(inode),
1006 "PAP-5210: mode must be M_DELETE");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001007
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001008 *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
1009 return M_DELETE;
1010 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001011
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001012 /* Directory item. */
1013 if (is_direntry_le_ih(p_le_ih))
1014 return prepare_for_direntry_item(p_s_path, p_le_ih, inode,
1015 n_new_file_length,
1016 p_n_cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001017
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001018 /* Direct item. */
1019 if (is_direct_le_ih(p_le_ih))
1020 return prepare_for_direct_item(p_s_path, p_le_ih, inode,
1021 n_new_file_length, p_n_cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001023 /* Case of an indirect item. */
1024 {
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001025 int blk_size = p_s_sb->s_blocksize;
1026 struct item_head s_ih;
1027 int need_re_search;
1028 int delete = 0;
1029 int result = M_CUT;
1030 int pos = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001032 if ( n_new_file_length == max_reiserfs_offset (inode) ) {
1033 /* prepare_for_delete_or_cut() is called by
1034 * reiserfs_delete_item() */
1035 n_new_file_length = 0;
1036 delete = 1;
1037 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001038
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001039 do {
1040 need_re_search = 0;
1041 *p_n_cut_size = 0;
1042 p_s_bh = PATH_PLAST_BUFFER(p_s_path);
1043 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1044 pos = I_UNFM_NUM(&s_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001045
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001046 while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) {
1047 __u32 *unfm, block;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001048
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001049 /* Each unformatted block deletion may involve one additional
1050 * bitmap block into the transaction, thereby the initial
1051 * journal space reservation might not be enough. */
1052 if (!delete && (*p_n_cut_size) != 0 &&
1053 reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
1054 break;
1055 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001057 unfm = (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1;
1058 block = get_block_num(unfm, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001060 if (block != 0) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001061 reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001062 put_block_num(unfm, 0, 0);
1063 journal_mark_dirty (th, p_s_sb, p_s_bh);
1064 reiserfs_free_block(th, inode, block, 1);
1065 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001067 cond_resched();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001068
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001069 if (item_moved (&s_ih, p_s_path)) {
1070 need_re_search = 1;
1071 break;
1072 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001074 pos --;
1075 (*p_n_removed) ++;
1076 (*p_n_cut_size) -= UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001077
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001078 if (pos == 0) {
1079 (*p_n_cut_size) -= IH_SIZE;
1080 result = M_DELETE;
1081 break;
1082 }
1083 }
1084 /* a trick. If the buffer has been logged, this will do nothing. If
1085 ** we've broken the loop without logging it, it will restore the
1086 ** buffer */
1087 reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
1088 } while (need_re_search &&
1089 search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND);
1090 pos_in_item(p_s_path) = pos * UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001091
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001092 if (*p_n_cut_size == 0) {
1093 /* Nothing were cut. maybe convert last unformatted node to the
1094 * direct item? */
1095 result = M_CONVERT;
1096 }
1097 return result;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001098 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099}
1100
1101/* Calculate number of bytes which will be deleted or cut during balance */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001102static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001103{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001104 int n_del_size;
1105 struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001107 if (is_statdata_le_ih(p_le_ih))
1108 return 0;
1109
1110 n_del_size =
1111 (c_mode ==
1112 M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
1113 if (is_direntry_le_ih(p_le_ih)) {
1114 // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
1115 // we can't use EMPTY_DIR_SIZE, as old format dirs have a different
1116 // empty size. ick. FIXME, is this right?
1117 //
1118 return n_del_size;
1119 }
1120
1121 if (is_indirect_le_ih(p_le_ih))
1122 n_del_size = (n_del_size / UNFM_P_SIZE) * (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size); // - get_ih_free_space (p_le_ih);
1123 return n_del_size;
1124}
1125
1126static void init_tb_struct(struct reiserfs_transaction_handle *th,
1127 struct tree_balance *p_s_tb,
1128 struct super_block *p_s_sb,
1129 struct path *p_s_path, int n_size)
1130{
1131
1132 BUG_ON(!th->t_trans_id);
1133
1134 memset(p_s_tb, '\0', sizeof(struct tree_balance));
1135 p_s_tb->transaction_handle = th;
1136 p_s_tb->tb_sb = p_s_sb;
1137 p_s_tb->tb_path = p_s_path;
1138 PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1139 PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
1140 p_s_tb->insert_size[0] = n_size;
1141}
1142
1143void padd_item(char *item, int total_length, int length)
1144{
1145 int i;
1146
1147 for (i = total_length; i > length;)
1148 item[--i] = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001149}
1150
1151#ifdef REISERQUOTA_DEBUG
1152char key2type(struct reiserfs_key *ih)
1153{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001154 if (is_direntry_le_key(2, ih))
1155 return 'd';
1156 if (is_direct_le_key(2, ih))
1157 return 'D';
1158 if (is_indirect_le_key(2, ih))
1159 return 'i';
1160 if (is_statdata_le_key(2, ih))
1161 return 's';
1162 return 'u';
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163}
1164
1165char head2type(struct item_head *ih)
1166{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001167 if (is_direntry_le_ih(ih))
1168 return 'd';
1169 if (is_direct_le_ih(ih))
1170 return 'D';
1171 if (is_indirect_le_ih(ih))
1172 return 'i';
1173 if (is_statdata_le_ih(ih))
1174 return 's';
1175 return 'u';
Linus Torvalds1da177e2005-04-16 15:20:36 -07001176}
1177#endif
1178
1179/* Delete object item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001180int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct path *p_s_path, /* Path to the deleted item. */
1181 const struct cpu_key *p_s_item_key, /* Key to search for the deleted item. */
1182 struct inode *p_s_inode, /* inode is here just to update i_blocks and quotas */
1183 struct buffer_head *p_s_un_bh)
1184{ /* NULL or unformatted node pointer. */
1185 struct super_block *p_s_sb = p_s_inode->i_sb;
1186 struct tree_balance s_del_balance;
1187 struct item_head s_ih;
1188 struct item_head *q_ih;
1189 int quota_cut_bytes;
1190 int n_ret_value, n_del_size, n_removed;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001191
1192#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001193 char c_mode;
1194 int n_iter = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195#endif
1196
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001197 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001199 init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path,
1200 0 /*size is unknown */ );
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001202 while (1) {
1203 n_removed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001204
1205#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001206 n_iter++;
1207 c_mode =
Linus Torvalds1da177e2005-04-16 15:20:36 -07001208#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001209 prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
1210 p_s_item_key, &n_removed,
1211 &n_del_size,
1212 max_reiserfs_offset(p_s_inode));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001213
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001214 RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001216 copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
1217 s_del_balance.insert_size[0] = n_del_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001219 n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
1220 if (n_ret_value != REPEAT_SEARCH)
1221 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001223 PROC_INFO_INC(p_s_sb, delete_item_restarted);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001225 // file system changed, repeat search
1226 n_ret_value =
1227 search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1228 if (n_ret_value == IO_ERROR)
1229 break;
1230 if (n_ret_value == FILE_NOT_FOUND) {
1231 reiserfs_warning(p_s_sb,
1232 "vs-5340: reiserfs_delete_item: "
1233 "no items of the file %K found",
1234 p_s_item_key);
1235 break;
1236 }
1237 } /* while (1) */
1238
1239 if (n_ret_value != CARRY_ON) {
1240 unfix_nodes(&s_del_balance);
1241 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001242 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001243 // reiserfs_delete_item returns item length when success
1244 n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
1245 q_ih = get_ih(p_s_path);
1246 quota_cut_bytes = ih_item_len(q_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001247
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001248 /* hack so the quota code doesn't have to guess if the file
1249 ** has a tail. On tail insert, we allocate quota for 1 unformatted node.
1250 ** We test the offset because the tail might have been
1251 ** split into multiple items, and we only want to decrement for
1252 ** the unfm node once
1253 */
1254 if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) {
1255 if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) {
1256 quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
1257 } else {
1258 quota_cut_bytes = 0;
1259 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001261
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001262 if (p_s_un_bh) {
1263 int off;
1264 char *data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001265
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001266 /* We are in direct2indirect conversion, so move tail contents
1267 to the unformatted node */
1268 /* note, we do the copy before preparing the buffer because we
1269 ** don't care about the contents of the unformatted node yet.
1270 ** the only thing we really care about is the direct item's data
1271 ** is in the unformatted node.
1272 **
1273 ** Otherwise, we would have to call reiserfs_prepare_for_journal on
1274 ** the unformatted node, which might schedule, meaning we'd have to
1275 ** loop all the way back up to the start of the while loop.
1276 **
1277 ** The unformatted node must be dirtied later on. We can't be
1278 ** sure here if the entire tail has been deleted yet.
1279 **
1280 ** p_s_un_bh is from the page cache (all unformatted nodes are
1281 ** from the page cache) and might be a highmem page. So, we
1282 ** can't use p_s_un_bh->b_data.
1283 ** -clm
1284 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001285
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001286 data = kmap_atomic(p_s_un_bh->b_page, KM_USER0);
1287 off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
1288 memcpy(data + off,
1289 B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih),
1290 n_ret_value);
1291 kunmap_atomic(data, KM_USER0);
1292 }
1293 /* Perform balancing after all resources have been collected at once. */
1294 do_balance(&s_del_balance, NULL, NULL, M_DELETE);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295
1296#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001297 reiserfs_debug(p_s_sb, REISERFS_DEBUG_CODE,
1298 "reiserquota delete_item(): freeing %u, id=%u type=%c",
1299 quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001300#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001301 DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001302
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001303 /* Return deleted body length */
1304 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305}
1306
Linus Torvalds1da177e2005-04-16 15:20:36 -07001307/* Summary Of Mechanisms For Handling Collisions Between Processes:
1308
1309 deletion of the body of the object is performed by iput(), with the
1310 result that if multiple processes are operating on a file, the
1311 deletion of the body of the file is deferred until the last process
1312 that has an open inode performs its iput().
1313
1314 writes and truncates are protected from collisions by use of
1315 semaphores.
1316
1317 creates, linking, and mknod are protected from collisions with other
1318 processes by making the reiserfs_add_entry() the last step in the
1319 creation, and then rolling back all changes if there was a collision.
1320 - Hans
1321*/
1322
Linus Torvalds1da177e2005-04-16 15:20:36 -07001323/* this deletes item which never gets split */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001324void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th,
1325 struct inode *inode, struct reiserfs_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001326{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001327 struct tree_balance tb;
1328 INITIALIZE_PATH(path);
1329 int item_len = 0;
1330 int tb_init = 0;
1331 struct cpu_key cpu_key;
1332 int retval;
1333 int quota_cut_bytes = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001334
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001335 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001337 le_key2cpu_key(&cpu_key, key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001338
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001339 while (1) {
1340 retval = search_item(th->t_super, &cpu_key, &path);
1341 if (retval == IO_ERROR) {
1342 reiserfs_warning(th->t_super,
1343 "vs-5350: reiserfs_delete_solid_item: "
1344 "i/o failure occurred trying to delete %K",
1345 &cpu_key);
1346 break;
1347 }
1348 if (retval != ITEM_FOUND) {
1349 pathrelse(&path);
1350 // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir
1351 if (!
1352 ((unsigned long long)
1353 GET_HASH_VALUE(le_key_k_offset
1354 (le_key_version(key), key)) == 0
1355 && (unsigned long long)
1356 GET_GENERATION_NUMBER(le_key_k_offset
1357 (le_key_version(key),
1358 key)) == 1))
1359 reiserfs_warning(th->t_super,
1360 "vs-5355: reiserfs_delete_solid_item: %k not found",
1361 key);
1362 break;
1363 }
1364 if (!tb_init) {
1365 tb_init = 1;
1366 item_len = ih_item_len(PATH_PITEM_HEAD(&path));
1367 init_tb_struct(th, &tb, th->t_super, &path,
1368 -(IH_SIZE + item_len));
1369 }
1370 quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path));
1371
1372 retval = fix_nodes(M_DELETE, &tb, NULL, NULL);
1373 if (retval == REPEAT_SEARCH) {
1374 PROC_INFO_INC(th->t_super, delete_solid_item_restarted);
1375 continue;
1376 }
1377
1378 if (retval == CARRY_ON) {
1379 do_balance(&tb, NULL, NULL, M_DELETE);
1380 if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001381#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001382 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
1383 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1384 quota_cut_bytes, inode->i_uid,
1385 key2type(key));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001387 DQUOT_FREE_SPACE_NODIRTY(inode,
1388 quota_cut_bytes);
1389 }
1390 break;
1391 }
1392 // IO_ERROR, NO_DISK_SPACE, etc
1393 reiserfs_warning(th->t_super,
1394 "vs-5360: reiserfs_delete_solid_item: "
1395 "could not delete %K due to fix_nodes failure",
1396 &cpu_key);
1397 unfix_nodes(&tb);
1398 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001399 }
1400
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001401 reiserfs_check_path(&path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001402}
1403
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001404int reiserfs_delete_object(struct reiserfs_transaction_handle *th,
1405 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001406{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001407 int err;
1408 inode->i_size = 0;
1409 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001411 /* for directory this deletes item containing "." and ".." */
1412 err =
1413 reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ );
1414 if (err)
1415 return err;
1416
Linus Torvalds1da177e2005-04-16 15:20:36 -07001417#if defined( USE_INODE_GENERATION_COUNTER )
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001418 if (!old_format_only(th->t_super)) {
1419 __le32 *inode_generation;
1420
1421 inode_generation =
1422 &REISERFS_SB(th->t_super)->s_rs->s_inode_generation;
1423 *inode_generation =
1424 cpu_to_le32(le32_to_cpu(*inode_generation) + 1);
1425 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426/* USE_INODE_GENERATION_COUNTER */
1427#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001428 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001430 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001431}
1432
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001433static void unmap_buffers(struct page *page, loff_t pos)
1434{
1435 struct buffer_head *bh;
1436 struct buffer_head *head;
1437 struct buffer_head *next;
1438 unsigned long tail_index;
1439 unsigned long cur_index;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001440
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001441 if (page) {
1442 if (page_has_buffers(page)) {
1443 tail_index = pos & (PAGE_CACHE_SIZE - 1);
1444 cur_index = 0;
1445 head = page_buffers(page);
1446 bh = head;
1447 do {
1448 next = bh->b_this_page;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001450 /* we want to unmap the buffers that contain the tail, and
1451 ** all the buffers after it (since the tail must be at the
1452 ** end of the file). We don't want to unmap file data
1453 ** before the tail, since it might be dirty and waiting to
1454 ** reach disk
1455 */
1456 cur_index += bh->b_size;
1457 if (cur_index > tail_index) {
1458 reiserfs_unmap_buffer(bh);
1459 }
1460 bh = next;
1461 } while (bh != head);
1462 if (PAGE_SIZE == bh->b_size) {
1463 clear_page_dirty(page);
1464 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001466 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001467}
1468
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001469static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th,
1470 struct inode *p_s_inode,
1471 struct page *page,
1472 struct path *p_s_path,
1473 const struct cpu_key *p_s_item_key,
1474 loff_t n_new_file_size, char *p_c_mode)
1475{
1476 struct super_block *p_s_sb = p_s_inode->i_sb;
1477 int n_block_size = p_s_sb->s_blocksize;
1478 int cut_bytes;
1479 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001480
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001481 if (n_new_file_size != p_s_inode->i_size)
1482 BUG();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001484 /* the page being sent in could be NULL if there was an i/o error
1485 ** reading in the last block. The user will hit problems trying to
1486 ** read the file, but for now we just skip the indirect2direct
1487 */
1488 if (atomic_read(&p_s_inode->i_count) > 1 ||
1489 !tail_has_to_be_packed(p_s_inode) ||
1490 !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) {
1491 // leave tail in an unformatted node
1492 *p_c_mode = M_SKIP_BALANCING;
1493 cut_bytes =
1494 n_block_size - (n_new_file_size & (n_block_size - 1));
1495 pathrelse(p_s_path);
1496 return cut_bytes;
1497 }
1498 /* Permorm the conversion to a direct_item. */
1499 /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */
1500 return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key,
1501 n_new_file_size, p_c_mode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001502}
1503
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504/* we did indirect_to_direct conversion. And we have inserted direct
1505 item successesfully, but there were no disk space to cut unfm
1506 pointer being converted. Therefore we have to delete inserted
1507 direct item(s) */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001508static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th,
1509 struct inode *inode, struct path *path)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001510{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001511 struct cpu_key tail_key;
1512 int tail_len;
1513 int removed;
1514 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001515
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001516 make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); // !!!!
1517 tail_key.key_length = 4;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001518
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001519 tail_len =
1520 (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1521 while (tail_len) {
1522 /* look for the last byte of the tail */
1523 if (search_for_position_by_key(inode->i_sb, &tail_key, path) ==
1524 POSITION_NOT_FOUND)
1525 reiserfs_panic(inode->i_sb,
1526 "vs-5615: indirect_to_direct_roll_back: found invalid item");
1527 RFALSE(path->pos_in_item !=
1528 ih_item_len(PATH_PITEM_HEAD(path)) - 1,
1529 "vs-5616: appended bytes found");
1530 PATH_LAST_POSITION(path)--;
1531
1532 removed =
1533 reiserfs_delete_item(th, path, &tail_key, inode,
1534 NULL /*unbh not needed */ );
1535 RFALSE(removed <= 0
1536 || removed > tail_len,
1537 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1538 tail_len, removed);
1539 tail_len -= removed;
1540 set_cpu_key_k_offset(&tail_key,
1541 cpu_key_k_offset(&tail_key) - removed);
1542 }
1543 reiserfs_warning(inode->i_sb,
1544 "indirect_to_direct_roll_back: indirect_to_direct conversion has been rolled back due to lack of disk space");
1545 //mark_file_without_tail (inode);
1546 mark_inode_dirty(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547}
1548
Linus Torvalds1da177e2005-04-16 15:20:36 -07001549/* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001550int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th,
1551 struct path *p_s_path,
1552 struct cpu_key *p_s_item_key,
1553 struct inode *p_s_inode,
1554 struct page *page, loff_t n_new_file_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001555{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001556 struct super_block *p_s_sb = p_s_inode->i_sb;
1557 /* Every function which is going to call do_balance must first
1558 create a tree_balance structure. Then it must fill up this
1559 structure by using the init_tb_struct and fix_nodes functions.
1560 After that we can make tree balancing. */
1561 struct tree_balance s_cut_balance;
1562 struct item_head *p_le_ih;
1563 int n_cut_size = 0, /* Amount to be cut. */
1564 n_ret_value = CARRY_ON, n_removed = 0, /* Number of the removed unformatted nodes. */
1565 n_is_inode_locked = 0;
1566 char c_mode; /* Mode of the balance. */
1567 int retval2 = -1;
1568 int quota_cut_bytes;
1569 loff_t tail_pos = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001570
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001571 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001573 init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path,
1574 n_cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001576 /* Repeat this loop until we either cut the item without needing
1577 to balance, or we fix_nodes without schedule occurring */
1578 while (1) {
1579 /* Determine the balance mode, position of the first byte to
1580 be cut, and size to be cut. In case of the indirect item
1581 free unformatted nodes which are pointed to by the cut
1582 pointers. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001584 c_mode =
1585 prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
1586 p_s_item_key, &n_removed,
1587 &n_cut_size, n_new_file_size);
1588 if (c_mode == M_CONVERT) {
1589 /* convert last unformatted node to direct item or leave
1590 tail in the unformatted node */
1591 RFALSE(n_ret_value != CARRY_ON,
1592 "PAP-5570: can not convert twice");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001593
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001594 n_ret_value =
1595 maybe_indirect_to_direct(th, p_s_inode, page,
1596 p_s_path, p_s_item_key,
1597 n_new_file_size, &c_mode);
1598 if (c_mode == M_SKIP_BALANCING)
1599 /* tail has been left in the unformatted node */
1600 return n_ret_value;
1601
1602 n_is_inode_locked = 1;
1603
1604 /* removing of last unformatted node will change value we
1605 have to return to truncate. Save it */
1606 retval2 = n_ret_value;
1607 /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1)); */
1608
1609 /* So, we have performed the first part of the conversion:
1610 inserting the new direct item. Now we are removing the
1611 last unformatted node pointer. Set key to search for
1612 it. */
1613 set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT);
1614 p_s_item_key->key_length = 4;
1615 n_new_file_size -=
1616 (n_new_file_size & (p_s_sb->s_blocksize - 1));
1617 tail_pos = n_new_file_size;
1618 set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1);
1619 if (search_for_position_by_key
1620 (p_s_sb, p_s_item_key,
1621 p_s_path) == POSITION_NOT_FOUND) {
1622 print_block(PATH_PLAST_BUFFER(p_s_path), 3,
1623 PATH_LAST_POSITION(p_s_path) - 1,
1624 PATH_LAST_POSITION(p_s_path) + 1);
1625 reiserfs_panic(p_s_sb,
1626 "PAP-5580: reiserfs_cut_from_item: item to convert does not exist (%K)",
1627 p_s_item_key);
1628 }
1629 continue;
1630 }
1631 if (n_cut_size == 0) {
1632 pathrelse(p_s_path);
1633 return 0;
1634 }
1635
1636 s_cut_balance.insert_size[0] = n_cut_size;
1637
1638 n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL);
1639 if (n_ret_value != REPEAT_SEARCH)
1640 break;
1641
1642 PROC_INFO_INC(p_s_sb, cut_from_item_restarted);
1643
1644 n_ret_value =
1645 search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
1646 if (n_ret_value == POSITION_FOUND)
1647 continue;
1648
1649 reiserfs_warning(p_s_sb,
1650 "PAP-5610: reiserfs_cut_from_item: item %K not found",
1651 p_s_item_key);
1652 unfix_nodes(&s_cut_balance);
1653 return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
1654 } /* while */
1655
1656 // check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
1657 if (n_ret_value != CARRY_ON) {
1658 if (n_is_inode_locked) {
1659 // FIXME: this seems to be not needed: we are always able
1660 // to cut item
1661 indirect_to_direct_roll_back(th, p_s_inode, p_s_path);
1662 }
1663 if (n_ret_value == NO_DISK_SPACE)
1664 reiserfs_warning(p_s_sb, "NO_DISK_SPACE");
1665 unfix_nodes(&s_cut_balance);
1666 return -EIO;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001667 }
1668
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001669 /* go ahead and perform balancing */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001670
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001671 RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001672
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001673 /* Calculate number of bytes that need to be cut from the item. */
1674 quota_cut_bytes =
1675 (c_mode ==
1676 M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance.
1677 insert_size[0];
1678 if (retval2 == -1)
1679 n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
1680 else
1681 n_ret_value = retval2;
1682
1683 /* For direct items, we only change the quota when deleting the last
1684 ** item.
1685 */
1686 p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path);
1687 if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) {
1688 if (c_mode == M_DELETE &&
1689 (le_ih_k_offset(p_le_ih) & (p_s_sb->s_blocksize - 1)) ==
1690 1) {
1691 // FIXME: this is to keep 3.5 happy
1692 REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX;
1693 quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE;
1694 } else {
1695 quota_cut_bytes = 0;
1696 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001697 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001698#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001699 if (n_is_inode_locked) {
1700 struct item_head *le_ih =
1701 PATH_PITEM_HEAD(s_cut_balance.tb_path);
1702 /* we are going to complete indirect2direct conversion. Make
1703 sure, that we exactly remove last unformatted node pointer
1704 of the item */
1705 if (!is_indirect_le_ih(le_ih))
1706 reiserfs_panic(p_s_sb,
1707 "vs-5652: reiserfs_cut_from_item: "
1708 "item must be indirect %h", le_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001709
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001710 if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
1711 reiserfs_panic(p_s_sb,
1712 "vs-5653: reiserfs_cut_from_item: "
1713 "completing indirect2direct conversion indirect item %h "
1714 "being deleted must be of 4 byte long",
1715 le_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001716
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001717 if (c_mode == M_CUT
1718 && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
1719 reiserfs_panic(p_s_sb,
1720 "vs-5654: reiserfs_cut_from_item: "
1721 "can not complete indirect2direct conversion of %h (CUT, insert_size==%d)",
1722 le_ih, s_cut_balance.insert_size[0]);
1723 }
1724 /* it would be useful to make sure, that right neighboring
1725 item is direct item of this file */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001726 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001727#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001728
1729 do_balance(&s_cut_balance, NULL, NULL, c_mode);
1730 if (n_is_inode_locked) {
1731 /* we've done an indirect->direct conversion. when the data block
1732 ** was freed, it was removed from the list of blocks that must
1733 ** be flushed before the transaction commits, make sure to
1734 ** unmap and invalidate it
1735 */
1736 unmap_buffers(page, tail_pos);
1737 REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask;
1738 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001739#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001740 reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE,
1741 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
1742 quota_cut_bytes, p_s_inode->i_uid, '?');
Linus Torvalds1da177e2005-04-16 15:20:36 -07001743#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001744 DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes);
1745 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001746}
1747
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001748static void truncate_directory(struct reiserfs_transaction_handle *th,
1749 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001750{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001751 BUG_ON(!th->t_trans_id);
1752 if (inode->i_nlink)
1753 reiserfs_warning(inode->i_sb,
1754 "vs-5655: truncate_directory: link count != 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001756 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET);
1757 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY);
1758 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1759 reiserfs_update_sd(th, inode);
1760 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET);
1761 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001762}
1763
Linus Torvalds1da177e2005-04-16 15:20:36 -07001764/* Truncate file to the new size. Note, this must be called with a transaction
1765 already started */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001766int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode, /* ->i_size contains new
1767 size */
1768 struct page *page, /* up to date for last block */
1769 int update_timestamps /* when it is called by
1770 file_release to convert
1771 the tail - no timestamps
1772 should be updated */
1773 )
1774{
1775 INITIALIZE_PATH(s_search_path); /* Path to the current object item. */
1776 struct item_head *p_le_ih; /* Pointer to an item header. */
1777 struct cpu_key s_item_key; /* Key to search for a previous file item. */
1778 loff_t n_file_size, /* Old file size. */
1779 n_new_file_size; /* New file size. */
1780 int n_deleted; /* Number of deleted or truncated bytes. */
1781 int retval;
1782 int err = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001783
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001784 BUG_ON(!th->t_trans_id);
1785 if (!
1786 (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode)
1787 || S_ISLNK(p_s_inode->i_mode)))
1788 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001789
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001790 if (S_ISDIR(p_s_inode->i_mode)) {
1791 // deletion of directory - no need to update timestamps
1792 truncate_directory(th, p_s_inode);
1793 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001794 }
1795
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001796 /* Get new file size. */
1797 n_new_file_size = p_s_inode->i_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001798
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001799 // FIXME: note, that key type is unimportant here
1800 make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode),
1801 TYPE_DIRECT, 3);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001802
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001803 retval =
1804 search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
1805 &s_search_path);
1806 if (retval == IO_ERROR) {
1807 reiserfs_warning(p_s_inode->i_sb,
1808 "vs-5657: reiserfs_do_truncate: "
1809 "i/o failure occurred trying to truncate %K",
1810 &s_item_key);
1811 err = -EIO;
1812 goto out;
1813 }
1814 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
1815 reiserfs_warning(p_s_inode->i_sb,
1816 "PAP-5660: reiserfs_do_truncate: "
1817 "wrong result %d of search for %K", retval,
1818 &s_item_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001819
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001820 err = -EIO;
1821 goto out;
1822 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001823
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001824 s_search_path.pos_in_item--;
1825
1826 /* Get real file size (total length of all file items) */
1827 p_le_ih = PATH_PITEM_HEAD(&s_search_path);
1828 if (is_statdata_le_ih(p_le_ih))
1829 n_file_size = 0;
1830 else {
1831 loff_t offset = le_ih_k_offset(p_le_ih);
1832 int bytes =
1833 op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize);
1834
1835 /* this may mismatch with real file size: if last direct item
1836 had no padding zeros and last unformatted node had no free
1837 space, this file would have this file size */
1838 n_file_size = offset + bytes - 1;
1839 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001840 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001841 * are we doing a full truncate or delete, if so
1842 * kick in the reada code
1843 */
1844 if (n_new_file_size == 0)
1845 s_search_path.reada = PATH_READA | PATH_READA_BACK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001847 if (n_file_size == 0 || n_file_size < n_new_file_size) {
1848 goto update_and_out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001849 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001850
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001851 /* Update key to search for the last file item. */
1852 set_cpu_key_k_offset(&s_item_key, n_file_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001853
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001854 do {
1855 /* Cut or delete file item. */
1856 n_deleted =
1857 reiserfs_cut_from_item(th, &s_search_path, &s_item_key,
1858 p_s_inode, page, n_new_file_size);
1859 if (n_deleted < 0) {
1860 reiserfs_warning(p_s_inode->i_sb,
1861 "vs-5665: reiserfs_do_truncate: reiserfs_cut_from_item failed");
1862 reiserfs_check_path(&s_search_path);
1863 return 0;
1864 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001865
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001866 RFALSE(n_deleted > n_file_size,
1867 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
1868 n_deleted, n_file_size, &s_item_key);
1869
1870 /* Change key to search the last file item. */
1871 n_file_size -= n_deleted;
1872
1873 set_cpu_key_k_offset(&s_item_key, n_file_size);
1874
1875 /* While there are bytes to truncate and previous file item is presented in the tree. */
1876
1877 /*
1878 ** This loop could take a really long time, and could log
1879 ** many more blocks than a transaction can hold. So, we do a polite
1880 ** journal end here, and if the transaction needs ending, we make
1881 ** sure the file is consistent before ending the current trans
1882 ** and starting a new one
1883 */
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001884 if (journal_transaction_should_end(th, 0) ||
1885 reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001886 int orig_len_alloc = th->t_blocks_allocated;
1887 decrement_counters_in_path(&s_search_path);
1888
1889 if (update_timestamps) {
1890 p_s_inode->i_mtime = p_s_inode->i_ctime =
1891 CURRENT_TIME_SEC;
1892 }
1893 reiserfs_update_sd(th, p_s_inode);
1894
1895 err = journal_end(th, p_s_inode->i_sb, orig_len_alloc);
1896 if (err)
1897 goto out;
1898 err = journal_begin(th, p_s_inode->i_sb,
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001899 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001900 if (err)
1901 goto out;
1902 reiserfs_update_inode_transaction(p_s_inode);
1903 }
1904 } while (n_file_size > ROUND_UP(n_new_file_size) &&
1905 search_for_position_by_key(p_s_inode->i_sb, &s_item_key,
1906 &s_search_path) == POSITION_FOUND);
1907
1908 RFALSE(n_file_size > ROUND_UP(n_new_file_size),
1909 "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d",
1910 n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);
1911
1912 update_and_out:
1913 if (update_timestamps) {
1914 // this is truncate, not file closing
1915 p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC;
1916 }
1917 reiserfs_update_sd(th, p_s_inode);
1918
1919 out:
1920 pathrelse(&s_search_path);
1921 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001922}
1923
Linus Torvalds1da177e2005-04-16 15:20:36 -07001924#ifdef CONFIG_REISERFS_CHECK
1925// this makes sure, that we __append__, not overwrite or add holes
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001926static void check_research_for_paste(struct path *path,
1927 const struct cpu_key *p_s_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001929 struct item_head *found_ih = get_ih(path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001930
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001931 if (is_direct_le_ih(found_ih)) {
1932 if (le_ih_k_offset(found_ih) +
1933 op_bytes_number(found_ih,
1934 get_last_bh(path)->b_size) !=
1935 cpu_key_k_offset(p_s_key)
1936 || op_bytes_number(found_ih,
1937 get_last_bh(path)->b_size) !=
1938 pos_in_item(path))
1939 reiserfs_panic(NULL,
1940 "PAP-5720: check_research_for_paste: "
1941 "found direct item %h or position (%d) does not match to key %K",
1942 found_ih, pos_in_item(path), p_s_key);
1943 }
1944 if (is_indirect_le_ih(found_ih)) {
1945 if (le_ih_k_offset(found_ih) +
1946 op_bytes_number(found_ih,
1947 get_last_bh(path)->b_size) !=
1948 cpu_key_k_offset(p_s_key)
1949 || I_UNFM_NUM(found_ih) != pos_in_item(path)
1950 || get_ih_free_space(found_ih) != 0)
1951 reiserfs_panic(NULL,
1952 "PAP-5730: check_research_for_paste: "
1953 "found indirect item (%h) or position (%d) does not match to key (%K)",
1954 found_ih, pos_in_item(path), p_s_key);
1955 }
1956}
1957#endif /* config reiserfs check */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001958
1959/* Paste bytes to the existing item. Returns bytes number pasted into the item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001960int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct path *p_s_search_path, /* Path to the pasted item. */
1961 const struct cpu_key *p_s_key, /* Key to search for the needed item. */
1962 struct inode *inode, /* Inode item belongs to */
1963 const char *p_c_body, /* Pointer to the bytes to paste. */
1964 int n_pasted_size)
1965{ /* Size of pasted bytes. */
1966 struct tree_balance s_paste_balance;
1967 int retval;
1968 int fs_gen;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001969
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001970 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001971
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001972 fs_gen = get_generation(inode->i_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001973
1974#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001975 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
1976 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
1977 n_pasted_size, inode->i_uid,
1978 key2type(&(p_s_key->on_disk_key)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001979#endif
1980
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001981 if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) {
1982 pathrelse(p_s_search_path);
1983 return -EDQUOT;
1984 }
1985 init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path,
1986 n_pasted_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001987#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001988 s_paste_balance.key = p_s_key->on_disk_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001989#endif
1990
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001991 /* DQUOT_* can schedule, must check before the fix_nodes */
1992 if (fs_changed(fs_gen, inode->i_sb)) {
1993 goto search_again;
1994 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001995
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001996 while ((retval =
1997 fix_nodes(M_PASTE, &s_paste_balance, NULL,
1998 p_c_body)) == REPEAT_SEARCH) {
1999 search_again:
2000 /* file system changed while we were in the fix_nodes */
2001 PROC_INFO_INC(th->t_super, paste_into_item_restarted);
2002 retval =
2003 search_for_position_by_key(th->t_super, p_s_key,
2004 p_s_search_path);
2005 if (retval == IO_ERROR) {
2006 retval = -EIO;
2007 goto error_out;
2008 }
2009 if (retval == POSITION_FOUND) {
2010 reiserfs_warning(inode->i_sb,
2011 "PAP-5710: reiserfs_paste_into_item: entry or pasted byte (%K) exists",
2012 p_s_key);
2013 retval = -EEXIST;
2014 goto error_out;
2015 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002016#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002017 check_research_for_paste(p_s_search_path, p_s_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002018#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002019 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002020
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002021 /* Perform balancing after all resources are collected by fix_nodes, and
2022 accessing them will not risk triggering schedule. */
2023 if (retval == CARRY_ON) {
2024 do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE);
2025 return 0;
2026 }
2027 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2028 error_out:
2029 /* this also releases the path */
2030 unfix_nodes(&s_paste_balance);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002031#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002032 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2033 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
2034 n_pasted_size, inode->i_uid,
2035 key2type(&(p_s_key->on_disk_key)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002036#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002037 DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size);
2038 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002039}
2040
Linus Torvalds1da177e2005-04-16 15:20:36 -07002041/* Insert new item into the buffer at the path. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002042int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct path *p_s_path, /* Path to the inserteded item. */
2043 const struct cpu_key *key, struct item_head *p_s_ih, /* Pointer to the item header to insert. */
2044 struct inode *inode, const char *p_c_body)
2045{ /* Pointer to the bytes to insert. */
2046 struct tree_balance s_ins_balance;
2047 int retval;
2048 int fs_gen = 0;
2049 int quota_bytes = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002050
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002051 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002052
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002053 if (inode) { /* Do we count quotas for item? */
2054 fs_gen = get_generation(inode->i_sb);
2055 quota_bytes = ih_item_len(p_s_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002056
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002057 /* hack so the quota code doesn't have to guess if the file has
2058 ** a tail, links are always tails, so there's no guessing needed
2059 */
2060 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) {
2061 quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE;
2062 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002063#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002064 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2065 "reiserquota insert_item(): allocating %u id=%u type=%c",
2066 quota_bytes, inode->i_uid, head2type(p_s_ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002067#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002068 /* We can't dirty inode here. It would be immediately written but
2069 * appropriate stat item isn't inserted yet... */
2070 if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) {
2071 pathrelse(p_s_path);
2072 return -EDQUOT;
2073 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002074 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002075 init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path,
2076 IH_SIZE + ih_item_len(p_s_ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002077#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002078 s_ins_balance.key = key->on_disk_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002079#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002080 /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */
2081 if (inode && fs_changed(fs_gen, inode->i_sb)) {
2082 goto search_again;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002083 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002084
2085 while ((retval =
2086 fix_nodes(M_INSERT, &s_ins_balance, p_s_ih,
2087 p_c_body)) == REPEAT_SEARCH) {
2088 search_again:
2089 /* file system changed while we were in the fix_nodes */
2090 PROC_INFO_INC(th->t_super, insert_item_restarted);
2091 retval = search_item(th->t_super, key, p_s_path);
2092 if (retval == IO_ERROR) {
2093 retval = -EIO;
2094 goto error_out;
2095 }
2096 if (retval == ITEM_FOUND) {
2097 reiserfs_warning(th->t_super,
2098 "PAP-5760: reiserfs_insert_item: "
2099 "key %K already exists in the tree",
2100 key);
2101 retval = -EEXIST;
2102 goto error_out;
2103 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002104 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002105
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002106 /* make balancing after all resources will be collected at a time */
2107 if (retval == CARRY_ON) {
2108 do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
2109 return 0;
2110 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002111
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002112 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
2113 error_out:
2114 /* also releases the path */
2115 unfix_nodes(&s_ins_balance);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002116#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002117 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
2118 "reiserquota insert_item(): freeing %u id=%u type=%c",
2119 quota_bytes, inode->i_uid, head2type(p_s_ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002120#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002121 if (inode)
2122 DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes);
2123 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002124}