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