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