blob: 5feacd689241e25f346756ee2528b4b42b845d42 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5/*
6 * Written by Anatoly P. Pinchuk pap@namesys.botik.ru
7 * Programm System Institute
8 * Pereslavl-Zalessky Russia
9 */
10
Linus Torvalds1da177e2005-04-16 15:20:36 -070011#include <linux/time.h>
12#include <linux/string.h>
13#include <linux/pagemap.h>
Al Virof466c6f2012-03-17 01:16:43 -040014#include "reiserfs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070015#include <linux/buffer_head.h>
16#include <linux/quotaops.h>
17
18/* Does the buffer contain a disk block which is in the tree. */
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -040019inline int B_IS_IN_TREE(const struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -070020{
21
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -040022 RFALSE(B_LEVEL(bh) > MAX_HEIGHT,
23 "PAP-1010: block (%b) has too big level (%z)", bh, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -070024
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -040025 return (B_LEVEL(bh) != FREE_LEVEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070026}
27
Jeff Mahoney098297b2014-04-23 10:00:36 -040028/* to get item head in le form */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -040029inline void copy_item_head(struct item_head *to,
30 const struct item_head *from)
Linus Torvalds1da177e2005-04-16 15:20:36 -070031{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -040032 memcpy(to, from, IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -070033}
34
Jeff Mahoney098297b2014-04-23 10:00:36 -040035/*
36 * k1 is pointer to on-disk structure which is stored in little-endian
37 * form. k2 is pointer to cpu variable. For key of items of the same
38 * object this returns 0.
39 * Returns: -1 if key1 < key2
40 * 0 if key1 == key2
41 * 1 if key1 > key2
42 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070043inline int comp_short_keys(const struct reiserfs_key *le_key,
44 const struct cpu_key *cpu_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -070045{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070046 __u32 n;
47 n = le32_to_cpu(le_key->k_dir_id);
48 if (n < cpu_key->on_disk_key.k_dir_id)
49 return -1;
50 if (n > cpu_key->on_disk_key.k_dir_id)
51 return 1;
52 n = le32_to_cpu(le_key->k_objectid);
53 if (n < cpu_key->on_disk_key.k_objectid)
54 return -1;
55 if (n > cpu_key->on_disk_key.k_objectid)
56 return 1;
57 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070058}
59
Jeff Mahoney098297b2014-04-23 10:00:36 -040060/*
61 * k1 is pointer to on-disk structure which is stored in little-endian
62 * form. k2 is pointer to cpu variable.
63 * Compare keys using all 4 key fields.
64 * Returns: -1 if key1 < key2 0
65 * if key1 = key2 1 if key1 > key2
66 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070067static inline int comp_keys(const struct reiserfs_key *le_key,
68 const struct cpu_key *cpu_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -070069{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070070 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -070071
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070072 retval = comp_short_keys(le_key, cpu_key);
73 if (retval)
74 return retval;
75 if (le_key_k_offset(le_key_version(le_key), le_key) <
76 cpu_key_k_offset(cpu_key))
77 return -1;
78 if (le_key_k_offset(le_key_version(le_key), le_key) >
79 cpu_key_k_offset(cpu_key))
80 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070081
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070082 if (cpu_key->key_length == 3)
83 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070084
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070085 /* this part is needed only when tail conversion is in progress */
86 if (le_key_k_type(le_key_version(le_key), le_key) <
87 cpu_key_k_type(cpu_key))
88 return -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070090 if (le_key_k_type(le_key_version(le_key), le_key) >
91 cpu_key_k_type(cpu_key))
92 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070093
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070094 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070095}
96
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070097inline int comp_short_le_keys(const struct reiserfs_key *key1,
98 const struct reiserfs_key *key2)
Linus Torvalds1da177e2005-04-16 15:20:36 -070099{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400100 __u32 *k1_u32, *k2_u32;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400101 int key_length = REISERFS_SHORT_KEY_LEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400103 k1_u32 = (__u32 *) key1;
104 k2_u32 = (__u32 *) key2;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400105 for (; key_length--; ++k1_u32, ++k2_u32) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400106 if (le32_to_cpu(*k1_u32) < le32_to_cpu(*k2_u32))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700107 return -1;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400108 if (le32_to_cpu(*k1_u32) > le32_to_cpu(*k2_u32))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700109 return 1;
110 }
111 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112}
113
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700114inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700115{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700116 int version;
117 to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
118 to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);
119
Jeff Mahoney098297b2014-04-23 10:00:36 -0400120 /* find out version of the key */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700121 version = le_key_version(from);
122 to->version = version;
123 to->on_disk_key.k_offset = le_key_k_offset(version, from);
124 to->on_disk_key.k_type = le_key_k_type(version, from);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125}
126
Jeff Mahoney098297b2014-04-23 10:00:36 -0400127/*
128 * this does not say which one is bigger, it only returns 1 if keys
129 * are not equal, 0 otherwise
130 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700131inline int comp_le_keys(const struct reiserfs_key *k1,
132 const struct reiserfs_key *k2)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700134 return memcmp(k1, k2, sizeof(struct reiserfs_key));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700135}
136
137/**************************************************************************
138 * Binary search toolkit function *
139 * Search for an item in the array by the item key *
140 * Returns: 1 if found, 0 if not found; *
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400141 * *pos = number of the searched element if found, else the *
142 * number of the first element that is larger than key. *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143 **************************************************************************/
Jeff Mahoney098297b2014-04-23 10:00:36 -0400144/*
145 * For those not familiar with binary search: lbound is the leftmost item
146 * that it could be, rbound the rightmost item that it could be. We examine
147 * the item halfway between lbound and rbound, and that tells us either
148 * that we can increase lbound, or decrease rbound, or that we have found it,
149 * or if lbound <= rbound that there are no possible items, and we have not
150 * found it. With each examination we cut the number of possible items it
151 * could be by one more than half rounded down, or we find it.
152 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400153static inline int bin_search(const void *key, /* Key to search for. */
154 const void *base, /* First item in the array. */
155 int num, /* Number of items in the array. */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400156 /*
157 * Item size in the array. searched. Lest the
158 * reader be confused, note that this is crafted
159 * as a general function, and when it is applied
160 * specifically to the array of item headers in a
161 * node, width is actually the item header size
162 * not the item size.
163 */
164 int width,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400165 int *pos /* Number of the searched for element. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700166 )
167{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400168 int rbound, lbound, j;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169
Jeff Mahoneyee939612009-03-30 14:02:50 -0400170 for (j = ((rbound = num - 1) + (lbound = 0)) / 2;
171 lbound <= rbound; j = (rbound + lbound) / 2)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700172 switch (comp_keys
Jeff Mahoneyee939612009-03-30 14:02:50 -0400173 ((struct reiserfs_key *)((char *)base + j * width),
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400174 (struct cpu_key *)key)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700175 case -1:
Jeff Mahoneyee939612009-03-30 14:02:50 -0400176 lbound = j + 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700177 continue;
178 case 1:
Jeff Mahoneyee939612009-03-30 14:02:50 -0400179 rbound = j - 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700180 continue;
181 case 0:
Jeff Mahoneyee939612009-03-30 14:02:50 -0400182 *pos = j;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700183 return ITEM_FOUND; /* Key found in the array. */
184 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185
Jeff Mahoney098297b2014-04-23 10:00:36 -0400186 /*
187 * bin_search did not find given key, it returns position of key,
188 * that is minimal and greater than the given one.
189 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400190 *pos = lbound;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700191 return ITEM_NOT_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192}
193
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195/* Minimal possible key. It is never in the tree. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700196const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700197
198/* Maximal possible key. It is never in the tree. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700199static const struct reiserfs_key MAX_KEY = {
Fabian Frederickafd54c62014-05-03 22:33:24 +0200200 cpu_to_le32(0xffffffff),
201 cpu_to_le32(0xffffffff),
202 {{cpu_to_le32(0xffffffff),
203 cpu_to_le32(0xffffffff)},}
Al Viro3e8962b2005-05-01 08:59:18 -0700204};
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205
Jeff Mahoney098297b2014-04-23 10:00:36 -0400206/*
207 * Get delimiting key of the buffer by looking for it in the buffers in the
208 * path, starting from the bottom of the path, and going upwards. We must
209 * check the path's validity at each step. If the key is not in the path,
210 * there is no delimiting key in the tree (buffer is first or last buffer
211 * in tree), and in this case we return a special key, either MIN_KEY or
212 * MAX_KEY.
213 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400214static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path,
215 const struct super_block *sb)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700216{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400217 int position, path_offset = chk_path->path_length;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400218 struct buffer_head *parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219
Jeff Mahoneyee939612009-03-30 14:02:50 -0400220 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700221 "PAP-5010: invalid offset in the path");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700223 /* While not higher in path than first element. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400224 while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700226 RFALSE(!buffer_uptodate
Jeff Mahoneyee939612009-03-30 14:02:50 -0400227 (PATH_OFFSET_PBUFFER(chk_path, path_offset)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700228 "PAP-5020: parent is not uptodate");
229
230 /* Parent at the path is not in the tree now. */
231 if (!B_IS_IN_TREE
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400232 (parent =
Jeff Mahoneyee939612009-03-30 14:02:50 -0400233 PATH_OFFSET_PBUFFER(chk_path, path_offset)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700234 return &MAX_KEY;
235 /* Check whether position in the parent is correct. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400236 if ((position =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400237 PATH_OFFSET_POSITION(chk_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400238 path_offset)) >
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400239 B_NR_ITEMS(parent))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700240 return &MAX_KEY;
241 /* Check whether parent at the path really points to the child. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400242 if (B_N_CHILD_NUM(parent, position) !=
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400243 PATH_OFFSET_PBUFFER(chk_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400244 path_offset + 1)->b_blocknr)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700245 return &MAX_KEY;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400246 /*
247 * Return delimiting key if position in the parent
248 * is not equal to zero.
249 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400250 if (position)
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400251 return internal_key(parent, position - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700252 }
253 /* Return MIN_KEY if we are in the root of the buffer tree. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400254 if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)->
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400255 b_blocknr == SB_ROOT_BLOCK(sb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700256 return &MIN_KEY;
257 return &MAX_KEY;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258}
259
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260/* Get delimiting key of the buffer at the path and its right neighbor. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400261inline const struct reiserfs_key *get_rkey(const struct treepath *chk_path,
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400262 const struct super_block *sb)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700263{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400264 int position, path_offset = chk_path->path_length;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400265 struct buffer_head *parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266
Jeff Mahoneyee939612009-03-30 14:02:50 -0400267 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700268 "PAP-5030: invalid offset in the path");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269
Jeff Mahoneyee939612009-03-30 14:02:50 -0400270 while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700272 RFALSE(!buffer_uptodate
Jeff Mahoneyee939612009-03-30 14:02:50 -0400273 (PATH_OFFSET_PBUFFER(chk_path, path_offset)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700274 "PAP-5040: parent is not uptodate");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700276 /* Parent at the path is not in the tree now. */
277 if (!B_IS_IN_TREE
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400278 (parent =
Jeff Mahoneyee939612009-03-30 14:02:50 -0400279 PATH_OFFSET_PBUFFER(chk_path, path_offset)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700280 return &MIN_KEY;
281 /* Check whether position in the parent is correct. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400282 if ((position =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400283 PATH_OFFSET_POSITION(chk_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400284 path_offset)) >
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400285 B_NR_ITEMS(parent))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700286 return &MIN_KEY;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400287 /*
288 * Check whether parent at the path really points
289 * to the child.
290 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400291 if (B_N_CHILD_NUM(parent, position) !=
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400292 PATH_OFFSET_PBUFFER(chk_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400293 path_offset + 1)->b_blocknr)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700294 return &MIN_KEY;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400295
296 /*
297 * Return delimiting key if position in the parent
298 * is not the last one.
299 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400300 if (position != B_NR_ITEMS(parent))
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400301 return internal_key(parent, position);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700302 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400303
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700304 /* Return MAX_KEY if we are in the root of the buffer tree. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400305 if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)->
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400306 b_blocknr == SB_ROOT_BLOCK(sb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700307 return &MAX_KEY;
308 return &MIN_KEY;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309}
310
Jeff Mahoney098297b2014-04-23 10:00:36 -0400311/*
312 * Check whether a key is contained in the tree rooted from a buffer at a path.
313 * This works by looking at the left and right delimiting keys for the buffer
314 * in the last path_element in the path. These delimiting keys are stored
315 * at least one level above that buffer in the tree. If the buffer is the
316 * first or last node in the tree order then one of the delimiting keys may
317 * be absent, and in this case get_lkey and get_rkey return a special key
318 * which is MIN_KEY or MAX_KEY.
319 */
320static inline int key_in_buffer(
321 /* Path which should be checked. */
322 struct treepath *chk_path,
323 /* Key which should be checked. */
324 const struct cpu_key *key,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400325 struct super_block *sb
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700326 )
327{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400329 RFALSE(!key || chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
330 || chk_path->path_length > MAX_HEIGHT,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700331 "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400332 key, chk_path->path_length);
333 RFALSE(!PATH_PLAST_BUFFER(chk_path)->b_bdev,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700334 "PAP-5060: device must not be NODEV");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700335
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400336 if (comp_keys(get_lkey(chk_path, sb), key) == 1)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700337 /* left delimiting key is bigger, that the key we look for */
338 return 0;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400339 /* if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */
340 if (comp_keys(get_rkey(chk_path, sb), key) != 1)
341 /* key must be less than right delimitiing key */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700342 return 0;
343 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344}
345
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -0800346int reiserfs_check_path(struct treepath *p)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700347{
348 RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
349 "path not properly relsed");
350 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700351}
352
Jeff Mahoney098297b2014-04-23 10:00:36 -0400353/*
354 * Drop the reference to each buffer in a path and restore
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400355 * dirty bits clean when preparing the buffer for the log.
Jeff Mahoney098297b2014-04-23 10:00:36 -0400356 * This version should only be called from fix_nodes()
357 */
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400358void pathrelse_and_restore(struct super_block *sb,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400359 struct treepath *search_path)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700360{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400361 int path_offset = search_path->path_length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362
Jeff Mahoneyee939612009-03-30 14:02:50 -0400363 RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700364 "clm-4000: invalid path offset");
365
Jeff Mahoneyee939612009-03-30 14:02:50 -0400366 while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400367 struct buffer_head *bh;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400368 bh = PATH_OFFSET_PBUFFER(search_path, path_offset--);
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400369 reiserfs_restore_prepared_buffer(sb, bh);
370 brelse(bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700371 }
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400372 search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700373}
374
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400375/* Drop the reference to each buffer in a path */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400376void pathrelse(struct treepath *search_path)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400378 int path_offset = search_path->path_length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379
Jeff Mahoneyee939612009-03-30 14:02:50 -0400380 RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700381 "PAP-5090: invalid path offset");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700382
Jeff Mahoneyee939612009-03-30 14:02:50 -0400383 while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
384 brelse(PATH_OFFSET_PBUFFER(search_path, path_offset--));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400386 search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387}
388
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700389static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
390{
391 struct block_head *blkh;
392 struct item_head *ih;
393 int used_space;
394 int prev_location;
395 int i;
396 int nr;
397
398 blkh = (struct block_head *)buf;
399 if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400400 reiserfs_warning(NULL, "reiserfs-5080",
401 "this should be caught earlier");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700402 return 0;
403 }
404
405 nr = blkh_nr_item(blkh);
406 if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
407 /* item number is too big or too small */
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400408 reiserfs_warning(NULL, "reiserfs-5081",
409 "nr_item seems wrong: %z", bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700410 return 0;
411 }
412 ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
413 used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
Jeff Mahoney098297b2014-04-23 10:00:36 -0400414
415 /* free space does not match to calculated amount of use space */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700416 if (used_space != blocksize - blkh_free_space(blkh)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400417 reiserfs_warning(NULL, "reiserfs-5082",
418 "free space seems wrong: %z", bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700419 return 0;
420 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400421 /*
422 * FIXME: it is_leaf will hit performance too much - we may have
423 * return 1 here
424 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700425
426 /* check tables of item heads */
427 ih = (struct item_head *)(buf + BLKH_SIZE);
428 prev_location = blocksize;
429 for (i = 0; i < nr; i++, ih++) {
430 if (le_ih_k_type(ih) == TYPE_ANY) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400431 reiserfs_warning(NULL, "reiserfs-5083",
432 "wrong item type for item %h",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700433 ih);
434 return 0;
435 }
436 if (ih_location(ih) >= blocksize
437 || ih_location(ih) < IH_SIZE * nr) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400438 reiserfs_warning(NULL, "reiserfs-5084",
439 "item location seems wrong: %h",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700440 ih);
441 return 0;
442 }
443 if (ih_item_len(ih) < 1
444 || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400445 reiserfs_warning(NULL, "reiserfs-5085",
446 "item length seems wrong: %h",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700447 ih);
448 return 0;
449 }
450 if (prev_location - ih_location(ih) != ih_item_len(ih)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400451 reiserfs_warning(NULL, "reiserfs-5086",
452 "item location seems wrong "
453 "(second one): %h", ih);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700454 return 0;
455 }
456 prev_location = ih_location(ih);
457 }
458
Jeff Mahoney098297b2014-04-23 10:00:36 -0400459 /* one may imagine many more checks */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700460 return 1;
461}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462
463/* returns 1 if buf looks like an internal node, 0 otherwise */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700464static int is_internal(char *buf, int blocksize, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700466 struct block_head *blkh;
467 int nr;
468 int used_space;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700470 blkh = (struct block_head *)buf;
471 nr = blkh_level(blkh);
472 if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
473 /* this level is not possible for internal nodes */
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400474 reiserfs_warning(NULL, "reiserfs-5087",
475 "this should be caught earlier");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700476 return 0;
477 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700479 nr = blkh_nr_item(blkh);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400480 /* for internal which is not root we might check min number of keys */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700481 if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400482 reiserfs_warning(NULL, "reiserfs-5088",
483 "number of key seems wrong: %z", bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700484 return 0;
485 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700487 used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
488 if (used_space != blocksize - blkh_free_space(blkh)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400489 reiserfs_warning(NULL, "reiserfs-5089",
490 "free space seems wrong: %z", bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700491 return 0;
492 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400493
494 /* one may imagine many more checks */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700495 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700496}
497
Jeff Mahoney098297b2014-04-23 10:00:36 -0400498/*
499 * make sure that bh contains formatted node of reiserfs tree of
500 * 'level'-th level
501 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700502static int is_tree_node(struct buffer_head *bh, int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700503{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700504 if (B_LEVEL(bh) != level) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400505 reiserfs_warning(NULL, "reiserfs-5090", "node level %d does "
506 "not match to the expected one %d",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700507 B_LEVEL(bh), level);
508 return 0;
509 }
510 if (level == DISK_LEAF_NODE_LEVEL)
511 return is_leaf(bh->b_data, bh->b_size, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700513 return is_internal(bh->b_data, bh->b_size, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514}
515
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516#define SEARCH_BY_KEY_READA 16
517
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200518/*
519 * The function is NOT SCHEDULE-SAFE!
520 * It might unlock the write lock if we needed to wait for a block
521 * to be read. Note that in this case it won't recover the lock to avoid
522 * high contention resulting from too much lock requests, especially
523 * the caller (search_by_key) will perform other schedule-unsafe
524 * operations just after calling this function.
525 *
Jeff Mahoney278f6672013-08-08 17:34:46 -0400526 * @return depth of lock to be restored after read completes
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200527 */
Jeff Mahoney278f6672013-08-08 17:34:46 -0400528static int search_by_key_reada(struct super_block *s,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700529 struct buffer_head **bh,
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700530 b_blocknr_t *b, int num)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700532 int i, j;
Jeff Mahoney278f6672013-08-08 17:34:46 -0400533 int depth = -1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700534
535 for (i = 0; i < num; i++) {
536 bh[i] = sb_getblk(s, b[i]);
537 }
Frederic Weisbecker09eb47a2009-05-08 14:21:33 +0200538 /*
539 * We are going to read some blocks on which we
540 * have a reference. It's safe, though we might be
541 * reading blocks concurrently changed if we release
542 * the lock. But it's still fine because we check later
543 * if the tree changed
544 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700545 for (j = 0; j < i; j++) {
546 /*
547 * note, this needs attention if we are getting rid of the BKL
Jeff Mahoney098297b2014-04-23 10:00:36 -0400548 * you have to make sure the prepared bit isn't set on this
549 * buffer
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700550 */
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200551 if (!buffer_uptodate(bh[j])) {
Jeff Mahoney278f6672013-08-08 17:34:46 -0400552 if (depth == -1)
553 depth = reiserfs_write_unlock_nested(s);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700554 ll_rw_block(READA, 1, bh + j);
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200555 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700556 brelse(bh[j]);
557 }
Jeff Mahoney278f6672013-08-08 17:34:46 -0400558 return depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559}
560
Jeff Mahoney098297b2014-04-23 10:00:36 -0400561/*
562 * This function fills up the path from the root to the leaf as it
563 * descends the tree looking for the key. It uses reiserfs_bread to
564 * try to find buffers in the cache given their block number. If it
565 * does not find them in the cache it reads them from disk. For each
566 * node search_by_key finds using reiserfs_bread it then uses
567 * bin_search to look through that node. bin_search will find the
568 * position of the block_number of the next node if it is looking
569 * through an internal node. If it is looking through a leaf node
570 * bin_search will find the position of the item which has key either
571 * equal to given key, or which is the maximal key less than the given
572 * key. search_by_key returns a path that must be checked for the
573 * correctness of the top of the path but need not be checked for the
574 * correctness of the bottom of the path
575 */
576/*
577 * search_by_key - search for key (and item) in stree
578 * @sb: superblock
579 * @key: pointer to key to search for
580 * @search_path: Allocated and initialized struct treepath; Returned filled
581 * on success.
582 * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to
583 * stop at leaf level.
584 *
585 * The function is NOT SCHEDULE-SAFE!
586 */
587int search_by_key(struct super_block *sb, const struct cpu_key *key,
588 struct treepath *search_path, int stop_level)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700589{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400590 b_blocknr_t block_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700591 int expected_level;
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400592 struct buffer_head *bh;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400593 struct path_element *last_element;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400594 int node_level, retval;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700595 int right_neighbor_of_leaf_node;
596 int fs_gen;
597 struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700598 b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700599 int reada_count = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600
601#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyee939612009-03-30 14:02:50 -0400602 int repeat_counter = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700604
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400605 PROC_INFO_INC(sb, search_by_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700606
Jeff Mahoney098297b2014-04-23 10:00:36 -0400607 /*
608 * As we add each node to a path we increase its count. This means
609 * that we must be careful to release all nodes in a path before we
610 * either discard the path struct or re-use the path struct, as we
611 * do here.
612 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700613
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400614 pathrelse(search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700615
616 right_neighbor_of_leaf_node = 0;
617
Jeff Mahoney098297b2014-04-23 10:00:36 -0400618 /*
619 * With each iteration of this loop we search through the items in the
620 * current node, and calculate the next current node(next path element)
621 * for the next iteration of this loop..
622 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400623 block_number = SB_ROOT_BLOCK(sb);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700624 expected_level = -1;
625 while (1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626
627#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyee939612009-03-30 14:02:50 -0400628 if (!(++repeat_counter % 50000))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400629 reiserfs_warning(sb, "PAP-5100",
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400630 "%s: there were %d iterations of "
631 "while loop looking for key %K",
Jeff Mahoneyee939612009-03-30 14:02:50 -0400632 current->comm, repeat_counter,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400633 key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634#endif
635
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700636 /* prep path to have another element added to it. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400637 last_element =
638 PATH_OFFSET_PELEMENT(search_path,
639 ++search_path->path_length);
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400640 fs_gen = get_generation(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700641
Jeff Mahoney098297b2014-04-23 10:00:36 -0400642 /*
643 * Read the next tree node, and set the last element
644 * in the path to have a pointer to it.
645 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400646 if ((bh = last_element->pe_buffer =
Jeff Mahoneyee939612009-03-30 14:02:50 -0400647 sb_getblk(sb, block_number))) {
Jeff Mahoney278f6672013-08-08 17:34:46 -0400648
649 /*
650 * We'll need to drop the lock if we encounter any
651 * buffers that need to be read. If all of them are
652 * already up to date, we don't need to drop the lock.
653 */
654 int depth = -1;
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200655
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400656 if (!buffer_uptodate(bh) && reada_count > 1)
Jeff Mahoney278f6672013-08-08 17:34:46 -0400657 depth = search_by_key_reada(sb, reada_bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700658 reada_blocks, reada_count);
Jeff Mahoney278f6672013-08-08 17:34:46 -0400659
660 if (!buffer_uptodate(bh) && depth == -1)
661 depth = reiserfs_write_unlock_nested(sb);
662
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400663 ll_rw_block(READ, 1, &bh);
664 wait_on_buffer(bh);
Frederic Weisbecker2ac62692009-05-14 02:56:39 +0200665
Jeff Mahoney278f6672013-08-08 17:34:46 -0400666 if (depth != -1)
667 reiserfs_write_lock_nested(sb, depth);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400668 if (!buffer_uptodate(bh))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700669 goto io_error;
670 } else {
Jeff Mahoneycf776a72014-04-23 10:00:41 -0400671io_error:
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400672 search_path->path_length--;
673 pathrelse(search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700674 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700676 reada_count = 0;
677 if (expected_level == -1)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400678 expected_level = SB_TREE_HEIGHT(sb);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700679 expected_level--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680
Jeff Mahoney098297b2014-04-23 10:00:36 -0400681 /*
682 * It is possible that schedule occurred. We must check
683 * whether the key to search is still in the tree rooted
684 * from the current buffer. If not then repeat search
685 * from the root.
686 */
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400687 if (fs_changed(fs_gen, sb) &&
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400688 (!B_IS_IN_TREE(bh) ||
689 B_LEVEL(bh) != expected_level ||
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400690 !key_in_buffer(search_path, key, sb))) {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400691 PROC_INFO_INC(sb, search_by_key_fs_changed);
692 PROC_INFO_INC(sb, search_by_key_restarted);
693 PROC_INFO_INC(sb,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700694 sbk_restarted[expected_level - 1]);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400695 pathrelse(search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700696
Jeff Mahoney098297b2014-04-23 10:00:36 -0400697 /*
698 * Get the root block number so that we can
699 * repeat the search starting from the root.
700 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400701 block_number = SB_ROOT_BLOCK(sb);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700702 expected_level = -1;
703 right_neighbor_of_leaf_node = 0;
704
705 /* repeat search from the root */
706 continue;
707 }
708
Jeff Mahoney098297b2014-04-23 10:00:36 -0400709 /*
710 * only check that the key is in the buffer if key is not
711 * equal to the MAX_KEY. Latter case is only possible in
712 * "finish_unfinished()" processing during mount.
713 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400714 RFALSE(comp_keys(&MAX_KEY, key) &&
715 !key_in_buffer(search_path, key, sb),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700716 "PAP-5130: key is not in the buffer");
717#ifdef CONFIG_REISERFS_CHECK
Frederic Weisbecker08f14fc2009-05-16 19:10:38 +0200718 if (REISERFS_SB(sb)->cur_tb) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700719 print_cur_tb("5140");
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400720 reiserfs_panic(sb, "PAP-5140",
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400721 "schedule occurred in do_balance!");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700722 }
723#endif
724
Jeff Mahoney098297b2014-04-23 10:00:36 -0400725 /*
726 * make sure, that the node contents look like a node of
727 * certain level
728 */
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400729 if (!is_tree_node(bh, expected_level)) {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -0400730 reiserfs_error(sb, "vs-5150",
Jeff Mahoney0030b642009-03-30 14:02:28 -0400731 "invalid format found in block %ld. "
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400732 "Fsck?", bh->b_blocknr);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400733 pathrelse(search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700734 return IO_ERROR;
735 }
736
737 /* ok, we have acquired next formatted node in the tree */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400738 node_level = B_LEVEL(bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700739
Jeff Mahoneyee939612009-03-30 14:02:50 -0400740 PROC_INFO_BH_STAT(sb, bh, node_level - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700741
Jeff Mahoneyee939612009-03-30 14:02:50 -0400742 RFALSE(node_level < stop_level,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700743 "vs-5152: tree level (%d) is less than stop level (%d)",
Jeff Mahoneyee939612009-03-30 14:02:50 -0400744 node_level, stop_level);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700745
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400746 retval = bin_search(key, item_head(bh, 0),
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400747 B_NR_ITEMS(bh),
Jeff Mahoneyee939612009-03-30 14:02:50 -0400748 (node_level ==
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700749 DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
750 KEY_SIZE,
Jeff Mahoneya228bf82014-04-23 10:00:42 -0400751 &last_element->pe_position);
Jeff Mahoneyee939612009-03-30 14:02:50 -0400752 if (node_level == stop_level) {
753 return retval;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700754 }
755
756 /* we are not in the stop level */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400757 /*
758 * item has been found, so we choose the pointer which
759 * is to the right of the found one
760 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400761 if (retval == ITEM_FOUND)
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400762 last_element->pe_position++;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700763
Jeff Mahoney098297b2014-04-23 10:00:36 -0400764 /*
765 * if item was not found we choose the position which is to
766 * the left of the found item. This requires no code,
767 * bin_search did it already.
768 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700769
Jeff Mahoney098297b2014-04-23 10:00:36 -0400770 /*
771 * So we have chosen a position in the current node which is
772 * an internal node. Now we calculate child block number by
773 * position in the node.
774 */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400775 block_number =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400776 B_N_CHILD_NUM(bh, last_element->pe_position);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700777
Jeff Mahoney098297b2014-04-23 10:00:36 -0400778 /*
779 * if we are going to read leaf nodes, try for read
780 * ahead as well
781 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400782 if ((search_path->reada & PATH_READA) &&
Jeff Mahoneyee939612009-03-30 14:02:50 -0400783 node_level == DISK_LEAF_NODE_LEVEL + 1) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400784 int pos = last_element->pe_position;
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400785 int limit = B_NR_ITEMS(bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700786 struct reiserfs_key *le_key;
787
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400788 if (search_path->reada & PATH_READA_BACK)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700789 limit = 0;
790 while (reada_count < SEARCH_BY_KEY_READA) {
791 if (pos == limit)
792 break;
793 reada_blocks[reada_count++] =
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400794 B_N_CHILD_NUM(bh, pos);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400795 if (search_path->reada & PATH_READA_BACK)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700796 pos--;
797 else
798 pos++;
799
800 /*
801 * check to make sure we're in the same object
802 */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400803 le_key = internal_key(bh, pos);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700804 if (le32_to_cpu(le_key->k_objectid) !=
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400805 key->on_disk_key.k_objectid) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700806 break;
807 }
808 }
809 }
810 }
811}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700812
Jeff Mahoney098297b2014-04-23 10:00:36 -0400813/*
814 * Form the path to an item and position in this item which contains
815 * file byte defined by key. If there is no such item
816 * corresponding to the key, we point the path to the item with
817 * maximal key less than key, and *pos_in_item is set to one
818 * past the last entry/byte in the item. If searching for entry in a
819 * directory item, and it is not found, *pos_in_item is set to one
820 * entry more than the entry with maximal key which is less than the
821 * sought key.
822 *
823 * Note that if there is no entry in this same node which is one more,
824 * then we point to an imaginary entry. for direct items, the
825 * position is in units of bytes, for indirect items the position is
826 * in units of blocknr entries, for directory items the position is in
827 * units of directory entries.
828 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829/* The function is NOT SCHEDULE-SAFE! */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400830int search_for_position_by_key(struct super_block *sb,
831 /* Key to search (cpu variable) */
832 const struct cpu_key *p_cpu_key,
833 /* Filled up by this function. */
834 struct treepath *search_path)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700835{
836 struct item_head *p_le_ih; /* pointer to on-disk structure */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400837 int blk_size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700838 loff_t item_offset, offset;
839 struct reiserfs_dir_entry de;
840 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700842 /* If searching for directory entry. */
843 if (is_direntry_cpu_key(p_cpu_key))
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400844 return search_by_entry_key(sb, p_cpu_key, search_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700845 &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700847 /* If not searching for directory entry. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700849 /* If item is found. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400850 retval = search_item(sb, p_cpu_key, search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700851 if (retval == IO_ERROR)
852 return retval;
853 if (retval == ITEM_FOUND) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700855 RFALSE(!ih_item_len
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400856 (item_head
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400857 (PATH_PLAST_BUFFER(search_path),
858 PATH_LAST_POSITION(search_path))),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700859 "PAP-5165: item length equals zero");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400861 pos_in_item(search_path) = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700862 return POSITION_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700864
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400865 RFALSE(!PATH_LAST_POSITION(search_path),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700866 "PAP-5170: position equals zero");
867
868 /* Item is not found. Set path to the previous item. */
869 p_le_ih =
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400870 item_head(PATH_PLAST_BUFFER(search_path),
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400871 --PATH_LAST_POSITION(search_path));
Jeff Mahoneyee939612009-03-30 14:02:50 -0400872 blk_size = sb->s_blocksize;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700873
Jeff Mahoneya228bf82014-04-23 10:00:42 -0400874 if (comp_short_keys(&p_le_ih->ih_key, p_cpu_key))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700875 return FILE_NOT_FOUND;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400876
877 /* FIXME: quite ugly this far */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700878
879 item_offset = le_ih_k_offset(p_le_ih);
880 offset = cpu_key_k_offset(p_cpu_key);
881
882 /* Needed byte is contained in the item pointed to by the path. */
883 if (item_offset <= offset &&
Jeff Mahoneyee939612009-03-30 14:02:50 -0400884 item_offset + op_bytes_number(p_le_ih, blk_size) > offset) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400885 pos_in_item(search_path) = offset - item_offset;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700886 if (is_indirect_le_ih(p_le_ih)) {
Jeff Mahoneyee939612009-03-30 14:02:50 -0400887 pos_in_item(search_path) /= blk_size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700888 }
889 return POSITION_FOUND;
890 }
891
Jeff Mahoney098297b2014-04-23 10:00:36 -0400892 /*
893 * Needed byte is not contained in the item pointed to by the
894 * path. Set pos_in_item out of the item.
895 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700896 if (is_indirect_le_ih(p_le_ih))
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400897 pos_in_item(search_path) =
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700898 ih_item_len(p_le_ih) / UNFM_P_SIZE;
899 else
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400900 pos_in_item(search_path) = ih_item_len(p_le_ih);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700901
902 return POSITION_NOT_FOUND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903}
904
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905/* Compare given item and item pointed to by the path. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400906int comp_items(const struct item_head *stored_ih, const struct treepath *path)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400908 struct buffer_head *bh = PATH_PLAST_BUFFER(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700909 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700911 /* Last buffer at the path is not in the tree. */
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -0400912 if (!B_IS_IN_TREE(bh))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700913 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700915 /* Last path position is invalid. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400916 if (PATH_LAST_POSITION(path) >= B_NR_ITEMS(bh))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700917 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700919 /* we need only to know, whether it is the same item */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400920 ih = tp_item_head(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700921 return memcmp(stored_ih, ih, IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922}
923
Jeff Mahoney098297b2014-04-23 10:00:36 -0400924/* unformatted nodes are not logged anymore, ever. This is safe now */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700925#define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
926
Jeff Mahoney098297b2014-04-23 10:00:36 -0400927/* block can not be forgotten as it is in I/O or held by someone */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700928#define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
929
Jeff Mahoney098297b2014-04-23 10:00:36 -0400930/* prepare for delete or cut of direct item */
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -0800931static inline int prepare_for_direct_item(struct treepath *path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700932 struct item_head *le_ih,
933 struct inode *inode,
934 loff_t new_file_length, int *cut_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700935{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700936 loff_t round_len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700938 if (new_file_length == max_reiserfs_offset(inode)) {
939 /* item has to be deleted */
940 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
941 return M_DELETE;
942 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400943 /* new file gets truncated */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700944 if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700945 round_len = ROUND_UP(new_file_length);
Jeff Mahoneyee939612009-03-30 14:02:50 -0400946 /* this was new_file_length < le_ih ... */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700947 if (round_len < le_ih_k_offset(le_ih)) {
948 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
949 return M_DELETE; /* Delete this item. */
950 }
951 /* Calculate first position and size for cutting from item. */
952 pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
953 *cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700955 return M_CUT; /* Cut from this item. */
956 }
957
Jeff Mahoney098297b2014-04-23 10:00:36 -0400958 /* old file: items may have any length */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700959
960 if (new_file_length < le_ih_k_offset(le_ih)) {
961 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
962 return M_DELETE; /* Delete this item. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400964
Linus Torvalds1da177e2005-04-16 15:20:36 -0700965 /* Calculate first position and size for cutting from item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700966 *cut_size = -(ih_item_len(le_ih) -
967 (pos_in_item(path) =
968 new_file_length + 1 - le_ih_k_offset(le_ih)));
969 return M_CUT; /* Cut from this item. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970}
971
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -0800972static inline int prepare_for_direntry_item(struct treepath *path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700973 struct item_head *le_ih,
974 struct inode *inode,
975 loff_t new_file_length,
976 int *cut_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700977{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700978 if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
979 new_file_length == max_reiserfs_offset(inode)) {
980 RFALSE(ih_entry_count(le_ih) != 2,
981 "PAP-5220: incorrect empty directory item (%h)", le_ih);
982 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
Jeff Mahoney098297b2014-04-23 10:00:36 -0400983 /* Delete the directory item containing "." and ".." entry. */
984 return M_DELETE;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700985 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700987 if (ih_entry_count(le_ih) == 1) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400988 /*
989 * Delete the directory item such as there is one record only
990 * in this item
991 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700992 *cut_size = -(IH_SIZE + ih_item_len(le_ih));
993 return M_DELETE;
994 }
995
996 /* Cut one record from the directory item. */
997 *cut_size =
998 -(DEH_SIZE +
999 entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
1000 return M_CUT;
1001}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001003#define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)
1004
Jeff Mahoney098297b2014-04-23 10:00:36 -04001005/*
1006 * If the path points to a directory or direct item, calculate mode
1007 * and the size cut, for balance.
1008 * If the path points to an indirect item, remove some number of its
1009 * unformatted nodes.
1010 * In case of file truncate calculate whether this item must be
1011 * deleted/truncated or last unformatted node of this item will be
1012 * converted to a direct item.
1013 * This function returns a determination of what balance mode the
1014 * calling function should employ.
1015 */
1016static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th,
1017 struct inode *inode,
1018 struct treepath *path,
1019 const struct cpu_key *item_key,
1020 /*
1021 * Number of unformatted nodes
1022 * which were removed from end
1023 * of the file.
1024 */
1025 int *removed,
1026 int *cut_size,
1027 /* MAX_KEY_OFFSET in case of delete. */
1028 unsigned long long new_file_length
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001029 )
1030{
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001031 struct super_block *sb = inode->i_sb;
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001032 struct item_head *p_le_ih = tp_item_head(path);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001033 struct buffer_head *bh = PATH_PLAST_BUFFER(path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001035 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001037 /* Stat_data item. */
1038 if (is_statdata_le_ih(p_le_ih)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039
Jeff Mahoneyee939612009-03-30 14:02:50 -04001040 RFALSE(new_file_length != max_reiserfs_offset(inode),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001041 "PAP-5210: mode must be M_DELETE");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001042
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001043 *cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001044 return M_DELETE;
1045 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001046
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001047 /* Directory item. */
1048 if (is_direntry_le_ih(p_le_ih))
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001049 return prepare_for_direntry_item(path, p_le_ih, inode,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001050 new_file_length,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001051 cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001052
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001053 /* Direct item. */
1054 if (is_direct_le_ih(p_le_ih))
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001055 return prepare_for_direct_item(path, p_le_ih, inode,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001056 new_file_length, cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001058 /* Case of an indirect item. */
1059 {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001060 int blk_size = sb->s_blocksize;
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001061 struct item_head s_ih;
1062 int need_re_search;
1063 int delete = 0;
1064 int result = M_CUT;
1065 int pos = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066
Jeff Mahoneyee939612009-03-30 14:02:50 -04001067 if ( new_file_length == max_reiserfs_offset (inode) ) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001068 /*
1069 * prepare_for_delete_or_cut() is called by
1070 * reiserfs_delete_item()
1071 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001072 new_file_length = 0;
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001073 delete = 1;
1074 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001075
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001076 do {
1077 need_re_search = 0;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001078 *cut_size = 0;
1079 bh = PATH_PLAST_BUFFER(path);
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001080 copy_item_head(&s_ih, tp_item_head(path));
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001081 pos = I_UNFM_NUM(&s_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
Jeff Mahoneyee939612009-03-30 14:02:50 -04001083 while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > new_file_length) {
Al Viro87588dd2007-07-26 17:47:03 +01001084 __le32 *unfm;
1085 __u32 block;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001086
Jeff Mahoney098297b2014-04-23 10:00:36 -04001087 /*
1088 * Each unformatted block deletion may involve
1089 * one additional bitmap block into the transaction,
1090 * thereby the initial journal space reservation
1091 * might not be enough.
1092 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001093 if (!delete && (*cut_size) != 0 &&
1094 reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD)
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001095 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001097 unfm = (__le32 *)ih_item_body(bh, &s_ih) + pos - 1;
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001098 block = get_block_num(unfm, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001100 if (block != 0) {
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001101 reiserfs_prepare_for_journal(sb, bh, 1);
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001102 put_block_num(unfm, 0, 0);
Jeff Mahoney09f1b802014-04-23 10:00:39 -04001103 journal_mark_dirty(th, bh);
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001104 reiserfs_free_block(th, inode, block, 1);
1105 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106
Jeff Mahoney278f6672013-08-08 17:34:46 -04001107 reiserfs_cond_resched(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001109 if (item_moved (&s_ih, path)) {
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001110 need_re_search = 1;
1111 break;
1112 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001113
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001114 pos --;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001115 (*removed)++;
1116 (*cut_size) -= UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001117
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001118 if (pos == 0) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001119 (*cut_size) -= IH_SIZE;
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001120 result = M_DELETE;
1121 break;
1122 }
1123 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001124 /*
1125 * a trick. If the buffer has been logged, this will
1126 * do nothing. If we've broken the loop without logging
1127 * it, it will restore the buffer
1128 */
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001129 reiserfs_restore_prepared_buffer(sb, bh);
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001130 } while (need_re_search &&
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001131 search_for_position_by_key(sb, item_key, path) == POSITION_FOUND);
1132 pos_in_item(path) = pos * UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001133
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001134 if (*cut_size == 0) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001135 /*
1136 * Nothing was cut. maybe convert last unformatted node to the
1137 * direct item?
1138 */
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001139 result = M_CONVERT;
1140 }
1141 return result;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001142 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143}
1144
1145/* Calculate number of bytes which will be deleted or cut during balance */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001146static int calc_deleted_bytes_number(struct tree_balance *tb, char mode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001147{
Jeff Mahoneyee939612009-03-30 14:02:50 -04001148 int del_size;
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001149 struct item_head *p_le_ih = tp_item_head(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001151 if (is_statdata_le_ih(p_le_ih))
1152 return 0;
1153
Jeff Mahoneyee939612009-03-30 14:02:50 -04001154 del_size =
1155 (mode ==
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001156 M_DELETE) ? ih_item_len(p_le_ih) : -tb->insert_size[0];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001157 if (is_direntry_le_ih(p_le_ih)) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001158 /*
1159 * return EMPTY_DIR_SIZE; We delete emty directories only.
1160 * we can't use EMPTY_DIR_SIZE, as old format dirs have a
1161 * different empty size. ick. FIXME, is this right?
1162 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001163 return del_size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001164 }
1165
1166 if (is_indirect_le_ih(p_le_ih))
Jeff Mahoneyee939612009-03-30 14:02:50 -04001167 del_size = (del_size / UNFM_P_SIZE) *
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001168 (PATH_PLAST_BUFFER(tb->tb_path)->b_size);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001169 return del_size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001170}
1171
1172static void init_tb_struct(struct reiserfs_transaction_handle *th,
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001173 struct tree_balance *tb,
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001174 struct super_block *sb,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001175 struct treepath *path, int size)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001176{
1177
1178 BUG_ON(!th->t_trans_id);
1179
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001180 memset(tb, '\0', sizeof(struct tree_balance));
1181 tb->transaction_handle = th;
1182 tb->tb_sb = sb;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001183 tb->tb_path = path;
1184 PATH_OFFSET_PBUFFER(path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
1185 PATH_OFFSET_POSITION(path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001186 tb->insert_size[0] = size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001187}
1188
1189void padd_item(char *item, int total_length, int length)
1190{
1191 int i;
1192
1193 for (i = total_length; i > length;)
1194 item[--i] = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195}
1196
1197#ifdef REISERQUOTA_DEBUG
1198char key2type(struct reiserfs_key *ih)
1199{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001200 if (is_direntry_le_key(2, ih))
1201 return 'd';
1202 if (is_direct_le_key(2, ih))
1203 return 'D';
1204 if (is_indirect_le_key(2, ih))
1205 return 'i';
1206 if (is_statdata_le_key(2, ih))
1207 return 's';
1208 return 'u';
Linus Torvalds1da177e2005-04-16 15:20:36 -07001209}
1210
1211char head2type(struct item_head *ih)
1212{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001213 if (is_direntry_le_ih(ih))
1214 return 'd';
1215 if (is_direct_le_ih(ih))
1216 return 'D';
1217 if (is_indirect_le_ih(ih))
1218 return 'i';
1219 if (is_statdata_le_ih(ih))
1220 return 's';
1221 return 'u';
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222}
1223#endif
1224
Jeff Mahoney098297b2014-04-23 10:00:36 -04001225/*
1226 * Delete object item.
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001227 * th - active transaction handle
1228 * path - path to the deleted item
1229 * item_key - key to search for the deleted item
1230 * indode - used for updating i_blocks and quotas
1231 * un_bh - NULL or unformatted node pointer
1232 */
1233int reiserfs_delete_item(struct reiserfs_transaction_handle *th,
1234 struct treepath *path, const struct cpu_key *item_key,
1235 struct inode *inode, struct buffer_head *un_bh)
1236{
Jeff Mahoney995c7622009-03-30 14:02:47 -04001237 struct super_block *sb = inode->i_sb;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001238 struct tree_balance s_del_balance;
1239 struct item_head s_ih;
1240 struct item_head *q_ih;
1241 int quota_cut_bytes;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001242 int ret_value, del_size, removed;
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001243 int depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244
1245#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyee939612009-03-30 14:02:50 -04001246 char mode;
1247 int iter = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248#endif
1249
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001250 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001251
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001252 init_tb_struct(th, &s_del_balance, sb, path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001253 0 /*size is unknown */ );
Linus Torvalds1da177e2005-04-16 15:20:36 -07001254
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001255 while (1) {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001256 removed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001257
1258#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyee939612009-03-30 14:02:50 -04001259 iter++;
1260 mode =
Linus Torvalds1da177e2005-04-16 15:20:36 -07001261#endif
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001262 prepare_for_delete_or_cut(th, inode, path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001263 item_key, &removed,
1264 &del_size,
Jeff Mahoney995c7622009-03-30 14:02:47 -04001265 max_reiserfs_offset(inode));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266
Jeff Mahoneyee939612009-03-30 14:02:50 -04001267 RFALSE(mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001269 copy_item_head(&s_ih, tp_item_head(path));
Jeff Mahoneyee939612009-03-30 14:02:50 -04001270 s_del_balance.insert_size[0] = del_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271
Jeff Mahoneyee939612009-03-30 14:02:50 -04001272 ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
1273 if (ret_value != REPEAT_SEARCH)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001274 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001275
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001276 PROC_INFO_INC(sb, delete_item_restarted);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001277
Jeff Mahoney098297b2014-04-23 10:00:36 -04001278 /* file system changed, repeat search */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001279 ret_value =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001280 search_for_position_by_key(sb, item_key, path);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001281 if (ret_value == IO_ERROR)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001282 break;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001283 if (ret_value == FILE_NOT_FOUND) {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001284 reiserfs_warning(sb, "vs-5340",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001285 "no items of the file %K found",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001286 item_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001287 break;
1288 }
1289 } /* while (1) */
1290
Jeff Mahoneyee939612009-03-30 14:02:50 -04001291 if (ret_value != CARRY_ON) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001292 unfix_nodes(&s_del_balance);
1293 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001295
1296 /* reiserfs_delete_item returns item length when success */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001297 ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001298 q_ih = tp_item_head(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001299 quota_cut_bytes = ih_item_len(q_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001300
Jeff Mahoney098297b2014-04-23 10:00:36 -04001301 /*
1302 * hack so the quota code doesn't have to guess if the file has a
1303 * tail. On tail insert, we allocate quota for 1 unformatted node.
1304 * We test the offset because the tail might have been
1305 * split into multiple items, and we only want to decrement for
1306 * the unfm node once
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001307 */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001308 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(q_ih)) {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001309 if ((le_ih_k_offset(q_ih) & (sb->s_blocksize - 1)) == 1) {
1310 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001311 } else {
1312 quota_cut_bytes = 0;
1313 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001314 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001316 if (un_bh) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001317 int off;
1318 char *data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Jeff Mahoney098297b2014-04-23 10:00:36 -04001320 /*
1321 * We are in direct2indirect conversion, so move tail contents
1322 * to the unformatted node
1323 */
1324 /*
1325 * note, we do the copy before preparing the buffer because we
1326 * don't care about the contents of the unformatted node yet.
1327 * the only thing we really care about is the direct item's
1328 * data is in the unformatted node.
1329 *
1330 * Otherwise, we would have to call
1331 * reiserfs_prepare_for_journal on the unformatted node,
1332 * which might schedule, meaning we'd have to loop all the
1333 * way back up to the start of the while loop.
1334 *
1335 * The unformatted node must be dirtied later on. We can't be
1336 * sure here if the entire tail has been deleted yet.
1337 *
1338 * un_bh is from the page cache (all unformatted nodes are
1339 * from the page cache) and might be a highmem page. So, we
1340 * can't use un_bh->b_data.
1341 * -clm
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001342 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001343
Cong Wang883da602011-11-25 23:14:35 +08001344 data = kmap_atomic(un_bh->b_page);
Kirill A. Shutemov09cbfea2016-04-01 15:29:47 +03001345 off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_SIZE - 1));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001346 memcpy(data + off,
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001347 ih_item_body(PATH_PLAST_BUFFER(path), &s_ih),
Jeff Mahoneyee939612009-03-30 14:02:50 -04001348 ret_value);
Cong Wang883da602011-11-25 23:14:35 +08001349 kunmap_atomic(data);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001350 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001351
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001352 /* Perform balancing after all resources have been collected at once. */
1353 do_balance(&s_del_balance, NULL, NULL, M_DELETE);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001354
1355#ifdef REISERQUOTA_DEBUG
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001356 reiserfs_debug(sb, REISERFS_DEBUG_CODE,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001357 "reiserquota delete_item(): freeing %u, id=%u type=%c",
Jeff Mahoney995c7622009-03-30 14:02:47 -04001358 quota_cut_bytes, inode->i_uid, head2type(&s_ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001360 depth = reiserfs_write_unlock_nested(inode->i_sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001361 dquot_free_space_nodirty(inode, quota_cut_bytes);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001362 reiserfs_write_lock_nested(inode->i_sb, depth);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001364 /* Return deleted body length */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001365 return ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366}
1367
Jeff Mahoney098297b2014-04-23 10:00:36 -04001368/*
1369 * Summary Of Mechanisms For Handling Collisions Between Processes:
1370 *
1371 * deletion of the body of the object is performed by iput(), with the
1372 * result that if multiple processes are operating on a file, the
1373 * deletion of the body of the file is deferred until the last process
1374 * that has an open inode performs its iput().
1375 *
1376 * writes and truncates are protected from collisions by use of
1377 * semaphores.
1378 *
1379 * creates, linking, and mknod are protected from collisions with other
1380 * processes by making the reiserfs_add_entry() the last step in the
1381 * creation, and then rolling back all changes if there was a collision.
1382 * - Hans
Linus Torvalds1da177e2005-04-16 15:20:36 -07001383*/
1384
Linus Torvalds1da177e2005-04-16 15:20:36 -07001385/* this deletes item which never gets split */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001386void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th,
1387 struct inode *inode, struct reiserfs_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001388{
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001389 struct super_block *sb = th->t_super;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001390 struct tree_balance tb;
1391 INITIALIZE_PATH(path);
1392 int item_len = 0;
1393 int tb_init = 0;
1394 struct cpu_key cpu_key;
1395 int retval;
1396 int quota_cut_bytes = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001398 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001399
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001400 le_key2cpu_key(&cpu_key, key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001402 while (1) {
1403 retval = search_item(th->t_super, &cpu_key, &path);
1404 if (retval == IO_ERROR) {
Jeff Mahoney0030b642009-03-30 14:02:28 -04001405 reiserfs_error(th->t_super, "vs-5350",
1406 "i/o failure occurred trying "
1407 "to delete %K", &cpu_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001408 break;
1409 }
1410 if (retval != ITEM_FOUND) {
1411 pathrelse(&path);
Jeff Mahoney098297b2014-04-23 10:00:36 -04001412 /*
1413 * No need for a warning, if there is just no free
1414 * space to insert '..' item into the
1415 * newly-created subdir
1416 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001417 if (!
1418 ((unsigned long long)
1419 GET_HASH_VALUE(le_key_k_offset
1420 (le_key_version(key), key)) == 0
1421 && (unsigned long long)
1422 GET_GENERATION_NUMBER(le_key_k_offset
1423 (le_key_version(key),
1424 key)) == 1))
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001425 reiserfs_warning(th->t_super, "vs-5355",
1426 "%k not found", key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001427 break;
1428 }
1429 if (!tb_init) {
1430 tb_init = 1;
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001431 item_len = ih_item_len(tp_item_head(&path));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001432 init_tb_struct(th, &tb, th->t_super, &path,
1433 -(IH_SIZE + item_len));
1434 }
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001435 quota_cut_bytes = ih_item_len(tp_item_head(&path));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001436
1437 retval = fix_nodes(M_DELETE, &tb, NULL, NULL);
1438 if (retval == REPEAT_SEARCH) {
1439 PROC_INFO_INC(th->t_super, delete_solid_item_restarted);
1440 continue;
1441 }
1442
1443 if (retval == CARRY_ON) {
1444 do_balance(&tb, NULL, NULL, M_DELETE);
Jeff Mahoney098297b2014-04-23 10:00:36 -04001445 /*
1446 * Should we count quota for item? (we don't
1447 * count quotas for save-links)
1448 */
1449 if (inode) {
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001450 int depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001451#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001452 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
1453 "reiserquota delete_solid_item(): freeing %u id=%u type=%c",
1454 quota_cut_bytes, inode->i_uid,
1455 key2type(key));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001456#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001457 depth = reiserfs_write_unlock_nested(sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001458 dquot_free_space_nodirty(inode,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001459 quota_cut_bytes);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001460 reiserfs_write_lock_nested(sb, depth);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001461 }
1462 break;
1463 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001464
1465 /* IO_ERROR, NO_DISK_SPACE, etc */
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001466 reiserfs_warning(th->t_super, "vs-5360",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001467 "could not delete %K due to fix_nodes failure",
1468 &cpu_key);
1469 unfix_nodes(&tb);
1470 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001471 }
1472
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001473 reiserfs_check_path(&path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474}
1475
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001476int reiserfs_delete_object(struct reiserfs_transaction_handle *th,
1477 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001478{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001479 int err;
1480 inode->i_size = 0;
1481 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001482
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001483 /* for directory this deletes item containing "." and ".." */
1484 err =
1485 reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ );
1486 if (err)
1487 return err;
1488
Linus Torvalds1da177e2005-04-16 15:20:36 -07001489#if defined( USE_INODE_GENERATION_COUNTER )
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001490 if (!old_format_only(th->t_super)) {
1491 __le32 *inode_generation;
1492
1493 inode_generation =
1494 &REISERFS_SB(th->t_super)->s_rs->s_inode_generation;
Marcin Slusarz9e902df2008-04-28 02:16:20 -07001495 le32_add_cpu(inode_generation, 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001496 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001497/* USE_INODE_GENERATION_COUNTER */
1498#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001499 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001500
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001501 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001502}
1503
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001504static void unmap_buffers(struct page *page, loff_t pos)
1505{
1506 struct buffer_head *bh;
1507 struct buffer_head *head;
1508 struct buffer_head *next;
1509 unsigned long tail_index;
1510 unsigned long cur_index;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001511
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001512 if (page) {
1513 if (page_has_buffers(page)) {
Kirill A. Shutemov09cbfea2016-04-01 15:29:47 +03001514 tail_index = pos & (PAGE_SIZE - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001515 cur_index = 0;
1516 head = page_buffers(page);
1517 bh = head;
1518 do {
1519 next = bh->b_this_page;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001520
Jeff Mahoney098297b2014-04-23 10:00:36 -04001521 /*
1522 * we want to unmap the buffers that contain
1523 * the tail, and all the buffers after it
1524 * (since the tail must be at the end of the
1525 * file). We don't want to unmap file data
1526 * before the tail, since it might be dirty
1527 * and waiting to reach disk
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001528 */
1529 cur_index += bh->b_size;
1530 if (cur_index > tail_index) {
1531 reiserfs_unmap_buffer(bh);
1532 }
1533 bh = next;
1534 } while (bh != head);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001535 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001536 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001537}
1538
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001539static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th,
Jeff Mahoney995c7622009-03-30 14:02:47 -04001540 struct inode *inode,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001541 struct page *page,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001542 struct treepath *path,
1543 const struct cpu_key *item_key,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001544 loff_t new_file_size, char *mode)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001545{
Jeff Mahoney995c7622009-03-30 14:02:47 -04001546 struct super_block *sb = inode->i_sb;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001547 int block_size = sb->s_blocksize;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001548 int cut_bytes;
1549 BUG_ON(!th->t_trans_id);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001550 BUG_ON(new_file_size != inode->i_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001551
Jeff Mahoney098297b2014-04-23 10:00:36 -04001552 /*
1553 * the page being sent in could be NULL if there was an i/o error
1554 * reading in the last block. The user will hit problems trying to
1555 * read the file, but for now we just skip the indirect2direct
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001556 */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001557 if (atomic_read(&inode->i_count) > 1 ||
1558 !tail_has_to_be_packed(inode) ||
1559 !page || (REISERFS_I(inode)->i_flags & i_nopack_mask)) {
Jeff Mahoney0222e652009-03-30 14:02:44 -04001560 /* leave tail in an unformatted node */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001561 *mode = M_SKIP_BALANCING;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001562 cut_bytes =
Jeff Mahoneyee939612009-03-30 14:02:50 -04001563 block_size - (new_file_size & (block_size - 1));
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001564 pathrelse(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001565 return cut_bytes;
1566 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001567
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001568 /* Perform the conversion to a direct_item. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001569 return indirect2direct(th, inode, page, path, item_key,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001570 new_file_size, mode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001571}
1572
Jeff Mahoney098297b2014-04-23 10:00:36 -04001573/*
1574 * we did indirect_to_direct conversion. And we have inserted direct
1575 * item successesfully, but there were no disk space to cut unfm
1576 * pointer being converted. Therefore we have to delete inserted
1577 * direct item(s)
1578 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001579static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th,
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -08001580 struct inode *inode, struct treepath *path)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001581{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001582 struct cpu_key tail_key;
1583 int tail_len;
1584 int removed;
1585 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001586
Jeff Mahoney098297b2014-04-23 10:00:36 -04001587 make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001588 tail_key.key_length = 4;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001590 tail_len =
1591 (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
1592 while (tail_len) {
1593 /* look for the last byte of the tail */
1594 if (search_for_position_by_key(inode->i_sb, &tail_key, path) ==
1595 POSITION_NOT_FOUND)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001596 reiserfs_panic(inode->i_sb, "vs-5615",
1597 "found invalid item");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001598 RFALSE(path->pos_in_item !=
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001599 ih_item_len(tp_item_head(path)) - 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001600 "vs-5616: appended bytes found");
1601 PATH_LAST_POSITION(path)--;
1602
1603 removed =
1604 reiserfs_delete_item(th, path, &tail_key, inode,
1605 NULL /*unbh not needed */ );
1606 RFALSE(removed <= 0
1607 || removed > tail_len,
1608 "vs-5617: there was tail %d bytes, removed item length %d bytes",
1609 tail_len, removed);
1610 tail_len -= removed;
1611 set_cpu_key_k_offset(&tail_key,
1612 cpu_key_k_offset(&tail_key) - removed);
1613 }
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001614 reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct "
1615 "conversion has been rolled back due to "
1616 "lack of disk space");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001617 mark_inode_dirty(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001618}
1619
Linus Torvalds1da177e2005-04-16 15:20:36 -07001620/* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001621int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001622 struct treepath *path,
1623 struct cpu_key *item_key,
Jeff Mahoney995c7622009-03-30 14:02:47 -04001624 struct inode *inode,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001625 struct page *page, loff_t new_file_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001626{
Jeff Mahoney995c7622009-03-30 14:02:47 -04001627 struct super_block *sb = inode->i_sb;
Jeff Mahoney098297b2014-04-23 10:00:36 -04001628 /*
1629 * Every function which is going to call do_balance must first
1630 * create a tree_balance structure. Then it must fill up this
1631 * structure by using the init_tb_struct and fix_nodes functions.
1632 * After that we can make tree balancing.
1633 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001634 struct tree_balance s_cut_balance;
1635 struct item_head *p_le_ih;
Jeff Mahoney098297b2014-04-23 10:00:36 -04001636 int cut_size = 0; /* Amount to be cut. */
1637 int ret_value = CARRY_ON;
1638 int removed = 0; /* Number of the removed unformatted nodes. */
1639 int is_inode_locked = 0;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001640 char mode; /* Mode of the balance. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001641 int retval2 = -1;
1642 int quota_cut_bytes;
1643 loff_t tail_pos = 0;
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001644 int depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001645
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001646 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001647
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001648 init_tb_struct(th, &s_cut_balance, inode->i_sb, path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001649 cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001650
Jeff Mahoney098297b2014-04-23 10:00:36 -04001651 /*
1652 * Repeat this loop until we either cut the item without needing
1653 * to balance, or we fix_nodes without schedule occurring
1654 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001655 while (1) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001656 /*
1657 * Determine the balance mode, position of the first byte to
1658 * be cut, and size to be cut. In case of the indirect item
1659 * free unformatted nodes which are pointed to by the cut
1660 * pointers.
1661 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001662
Jeff Mahoneyee939612009-03-30 14:02:50 -04001663 mode =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001664 prepare_for_delete_or_cut(th, inode, path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001665 item_key, &removed,
1666 &cut_size, new_file_size);
1667 if (mode == M_CONVERT) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001668 /*
1669 * convert last unformatted node to direct item or
1670 * leave tail in the unformatted node
1671 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001672 RFALSE(ret_value != CARRY_ON,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001673 "PAP-5570: can not convert twice");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001674
Jeff Mahoneyee939612009-03-30 14:02:50 -04001675 ret_value =
Jeff Mahoney995c7622009-03-30 14:02:47 -04001676 maybe_indirect_to_direct(th, inode, page,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001677 path, item_key,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001678 new_file_size, &mode);
1679 if (mode == M_SKIP_BALANCING)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001680 /* tail has been left in the unformatted node */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001681 return ret_value;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001682
Jeff Mahoneyee939612009-03-30 14:02:50 -04001683 is_inode_locked = 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001684
Jeff Mahoney098297b2014-04-23 10:00:36 -04001685 /*
1686 * removing of last unformatted node will
1687 * change value we have to return to truncate.
1688 * Save it
1689 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001690 retval2 = ret_value;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001691
Jeff Mahoney098297b2014-04-23 10:00:36 -04001692 /*
1693 * So, we have performed the first part of the
1694 * conversion:
1695 * inserting the new direct item. Now we are
1696 * removing the last unformatted node pointer.
1697 * Set key to search for it.
1698 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001699 set_cpu_key_k_type(item_key, TYPE_INDIRECT);
1700 item_key->key_length = 4;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001701 new_file_size -=
1702 (new_file_size & (sb->s_blocksize - 1));
1703 tail_pos = new_file_size;
1704 set_cpu_key_k_offset(item_key, new_file_size + 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001705 if (search_for_position_by_key
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001706 (sb, item_key,
1707 path) == POSITION_NOT_FOUND) {
1708 print_block(PATH_PLAST_BUFFER(path), 3,
1709 PATH_LAST_POSITION(path) - 1,
1710 PATH_LAST_POSITION(path) + 1);
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001711 reiserfs_panic(sb, "PAP-5580", "item to "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001712 "convert does not exist (%K)",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001713 item_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001714 }
1715 continue;
1716 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04001717 if (cut_size == 0) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001718 pathrelse(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001719 return 0;
1720 }
1721
Jeff Mahoneyee939612009-03-30 14:02:50 -04001722 s_cut_balance.insert_size[0] = cut_size;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001723
Jeff Mahoneyee939612009-03-30 14:02:50 -04001724 ret_value = fix_nodes(mode, &s_cut_balance, NULL, NULL);
1725 if (ret_value != REPEAT_SEARCH)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001726 break;
1727
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001728 PROC_INFO_INC(sb, cut_from_item_restarted);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001729
Jeff Mahoneyee939612009-03-30 14:02:50 -04001730 ret_value =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001731 search_for_position_by_key(sb, item_key, path);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001732 if (ret_value == POSITION_FOUND)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001733 continue;
1734
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001735 reiserfs_warning(sb, "PAP-5610", "item %K not found",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001736 item_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001737 unfix_nodes(&s_cut_balance);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001738 return (ret_value == IO_ERROR) ? -EIO : -ENOENT;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001739 } /* while */
1740
Jeff Mahoney098297b2014-04-23 10:00:36 -04001741 /* check fix_nodes results (IO_ERROR or NO_DISK_SPACE) */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001742 if (ret_value != CARRY_ON) {
1743 if (is_inode_locked) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001744 /*
1745 * FIXME: this seems to be not needed: we are always
1746 * able to cut item
1747 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001748 indirect_to_direct_roll_back(th, inode, path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001749 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04001750 if (ret_value == NO_DISK_SPACE)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001751 reiserfs_warning(sb, "reiserfs-5092",
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001752 "NO_DISK_SPACE");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001753 unfix_nodes(&s_cut_balance);
1754 return -EIO;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001755 }
1756
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001757 /* go ahead and perform balancing */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001758
Jeff Mahoneyee939612009-03-30 14:02:50 -04001759 RFALSE(mode == M_PASTE || mode == M_INSERT, "invalid mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001761 /* Calculate number of bytes that need to be cut from the item. */
1762 quota_cut_bytes =
Jeff Mahoneyee939612009-03-30 14:02:50 -04001763 (mode ==
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001764 M_DELETE) ? ih_item_len(tp_item_head(path)) : -s_cut_balance.
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001765 insert_size[0];
1766 if (retval2 == -1)
Jeff Mahoneyee939612009-03-30 14:02:50 -04001767 ret_value = calc_deleted_bytes_number(&s_cut_balance, mode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001768 else
Jeff Mahoneyee939612009-03-30 14:02:50 -04001769 ret_value = retval2;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001770
Jeff Mahoney098297b2014-04-23 10:00:36 -04001771 /*
1772 * For direct items, we only change the quota when deleting the last
1773 * item.
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001774 */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001775 p_le_ih = tp_item_head(s_cut_balance.tb_path);
Jeff Mahoney995c7622009-03-30 14:02:47 -04001776 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_le_ih)) {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001777 if (mode == M_DELETE &&
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001778 (le_ih_k_offset(p_le_ih) & (sb->s_blocksize - 1)) ==
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001779 1) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001780 /* FIXME: this is to keep 3.5 happy */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001781 REISERFS_I(inode)->i_first_direct_byte = U32_MAX;
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001782 quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001783 } else {
1784 quota_cut_bytes = 0;
1785 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001786 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001787#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyee939612009-03-30 14:02:50 -04001788 if (is_inode_locked) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001789 struct item_head *le_ih =
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001790 tp_item_head(s_cut_balance.tb_path);
Jeff Mahoney098297b2014-04-23 10:00:36 -04001791 /*
1792 * we are going to complete indirect2direct conversion. Make
1793 * sure, that we exactly remove last unformatted node pointer
1794 * of the item
1795 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001796 if (!is_indirect_le_ih(le_ih))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001797 reiserfs_panic(sb, "vs-5652",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001798 "item must be indirect %h", le_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799
Jeff Mahoneyee939612009-03-30 14:02:50 -04001800 if (mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001801 reiserfs_panic(sb, "vs-5653", "completing "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001802 "indirect2direct conversion indirect "
1803 "item %h being deleted must be of "
1804 "4 byte long", le_ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001805
Jeff Mahoneyee939612009-03-30 14:02:50 -04001806 if (mode == M_CUT
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001807 && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04001808 reiserfs_panic(sb, "vs-5654", "can not complete "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001809 "indirect2direct conversion of %h "
1810 "(CUT, insert_size==%d)",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001811 le_ih, s_cut_balance.insert_size[0]);
1812 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001813 /*
1814 * it would be useful to make sure, that right neighboring
1815 * item is direct item of this file
1816 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001817 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001818#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001819
Jeff Mahoneyee939612009-03-30 14:02:50 -04001820 do_balance(&s_cut_balance, NULL, NULL, mode);
1821 if (is_inode_locked) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001822 /*
1823 * we've done an indirect->direct conversion. when the
1824 * data block was freed, it was removed from the list of
1825 * blocks that must be flushed before the transaction
1826 * commits, make sure to unmap and invalidate it
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001827 */
1828 unmap_buffers(page, tail_pos);
Jeff Mahoney995c7622009-03-30 14:02:47 -04001829 REISERFS_I(inode)->i_flags &= ~i_pack_on_close_mask;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001830 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831#ifdef REISERQUOTA_DEBUG
Jeff Mahoney995c7622009-03-30 14:02:47 -04001832 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001833 "reiserquota cut_from_item(): freeing %u id=%u type=%c",
Jeff Mahoney995c7622009-03-30 14:02:47 -04001834 quota_cut_bytes, inode->i_uid, '?');
Linus Torvalds1da177e2005-04-16 15:20:36 -07001835#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001836 depth = reiserfs_write_unlock_nested(sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001837 dquot_free_space_nodirty(inode, quota_cut_bytes);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001838 reiserfs_write_lock_nested(sb, depth);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001839 return ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001840}
1841
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001842static void truncate_directory(struct reiserfs_transaction_handle *th,
1843 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001844{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001845 BUG_ON(!th->t_trans_id);
1846 if (inode->i_nlink)
Jeff Mahoney0030b642009-03-30 14:02:28 -04001847 reiserfs_error(inode->i_sb, "vs-5655", "link count != 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001848
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001849 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET);
1850 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY);
1851 reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode));
1852 reiserfs_update_sd(th, inode);
1853 set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET);
1854 set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001855}
1856
Jeff Mahoney098297b2014-04-23 10:00:36 -04001857/*
1858 * Truncate file to the new size. Note, this must be called with a
1859 * transaction already started
1860 */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001861int reiserfs_do_truncate(struct reiserfs_transaction_handle *th,
Jeff Mahoney098297b2014-04-23 10:00:36 -04001862 struct inode *inode, /* ->i_size contains new size */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001863 struct page *page, /* up to date for last block */
Jeff Mahoney098297b2014-04-23 10:00:36 -04001864 /*
1865 * when it is called by file_release to convert
1866 * the tail - no timestamps should be updated
1867 */
1868 int update_timestamps
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001869 )
1870{
1871 INITIALIZE_PATH(s_search_path); /* Path to the current object item. */
1872 struct item_head *p_le_ih; /* Pointer to an item header. */
Jeff Mahoney098297b2014-04-23 10:00:36 -04001873
1874 /* Key to search for a previous file item. */
1875 struct cpu_key s_item_key;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001876 loff_t file_size, /* Old file size. */
1877 new_file_size; /* New file size. */
1878 int deleted; /* Number of deleted or truncated bytes. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001879 int retval;
1880 int err = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001881
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001882 BUG_ON(!th->t_trans_id);
1883 if (!
Jeff Mahoney995c7622009-03-30 14:02:47 -04001884 (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode)
1885 || S_ISLNK(inode->i_mode)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001886 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001887
Jeff Mahoney098297b2014-04-23 10:00:36 -04001888 /* deletion of directory - no need to update timestamps */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001889 if (S_ISDIR(inode->i_mode)) {
Jeff Mahoney995c7622009-03-30 14:02:47 -04001890 truncate_directory(th, inode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001891 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001892 }
1893
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001894 /* Get new file size. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001895 new_file_size = inode->i_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001896
Jeff Mahoney098297b2014-04-23 10:00:36 -04001897 /* FIXME: note, that key type is unimportant here */
Jeff Mahoney995c7622009-03-30 14:02:47 -04001898 make_cpu_key(&s_item_key, inode, max_reiserfs_offset(inode),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001899 TYPE_DIRECT, 3);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001900
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001901 retval =
Jeff Mahoney995c7622009-03-30 14:02:47 -04001902 search_for_position_by_key(inode->i_sb, &s_item_key,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001903 &s_search_path);
1904 if (retval == IO_ERROR) {
Jeff Mahoney995c7622009-03-30 14:02:47 -04001905 reiserfs_error(inode->i_sb, "vs-5657",
Jeff Mahoney0030b642009-03-30 14:02:28 -04001906 "i/o failure occurred trying to truncate %K",
1907 &s_item_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001908 err = -EIO;
1909 goto out;
1910 }
1911 if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
Jeff Mahoney995c7622009-03-30 14:02:47 -04001912 reiserfs_error(inode->i_sb, "PAP-5660",
Jeff Mahoney0030b642009-03-30 14:02:28 -04001913 "wrong result %d of search for %K", retval,
1914 &s_item_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001915
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001916 err = -EIO;
1917 goto out;
1918 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001919
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001920 s_search_path.pos_in_item--;
1921
1922 /* Get real file size (total length of all file items) */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001923 p_le_ih = tp_item_head(&s_search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001924 if (is_statdata_le_ih(p_le_ih))
Jeff Mahoneyee939612009-03-30 14:02:50 -04001925 file_size = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001926 else {
1927 loff_t offset = le_ih_k_offset(p_le_ih);
1928 int bytes =
Jeff Mahoney995c7622009-03-30 14:02:47 -04001929 op_bytes_number(p_le_ih, inode->i_sb->s_blocksize);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001930
Jeff Mahoney098297b2014-04-23 10:00:36 -04001931 /*
1932 * this may mismatch with real file size: if last direct item
1933 * had no padding zeros and last unformatted node had no free
1934 * space, this file would have this file size
1935 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001936 file_size = offset + bytes - 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001937 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001938 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001939 * are we doing a full truncate or delete, if so
1940 * kick in the reada code
1941 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001942 if (new_file_size == 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001943 s_search_path.reada = PATH_READA | PATH_READA_BACK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001944
Jeff Mahoneyee939612009-03-30 14:02:50 -04001945 if (file_size == 0 || file_size < new_file_size) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001946 goto update_and_out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001947 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001948
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001949 /* Update key to search for the last file item. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001950 set_cpu_key_k_offset(&s_item_key, file_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001951
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001952 do {
1953 /* Cut or delete file item. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001954 deleted =
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001955 reiserfs_cut_from_item(th, &s_search_path, &s_item_key,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001956 inode, page, new_file_size);
1957 if (deleted < 0) {
Jeff Mahoney995c7622009-03-30 14:02:47 -04001958 reiserfs_warning(inode->i_sb, "vs-5665",
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001959 "reiserfs_cut_from_item failed");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001960 reiserfs_check_path(&s_search_path);
1961 return 0;
1962 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001963
Jeff Mahoneyee939612009-03-30 14:02:50 -04001964 RFALSE(deleted > file_size,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001965 "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K",
Jeff Mahoneyee939612009-03-30 14:02:50 -04001966 deleted, file_size, &s_item_key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001967
1968 /* Change key to search the last file item. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001969 file_size -= deleted;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001970
Jeff Mahoneyee939612009-03-30 14:02:50 -04001971 set_cpu_key_k_offset(&s_item_key, file_size);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001972
Jeff Mahoney098297b2014-04-23 10:00:36 -04001973 /*
1974 * While there are bytes to truncate and previous
1975 * file item is presented in the tree.
1976 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001977
1978 /*
Jeff Mahoney098297b2014-04-23 10:00:36 -04001979 * This loop could take a really long time, and could log
1980 * many more blocks than a transaction can hold. So, we do
1981 * a polite journal end here, and if the transaction needs
1982 * ending, we make sure the file is consistent before ending
1983 * the current trans and starting a new one
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001984 */
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001985 if (journal_transaction_should_end(th, 0) ||
1986 reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04001987 pathrelse(&s_search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001988
1989 if (update_timestamps) {
Jeff Mahoney995c7622009-03-30 14:02:47 -04001990 inode->i_mtime = CURRENT_TIME_SEC;
1991 inode->i_ctime = CURRENT_TIME_SEC;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001992 }
Jeff Mahoney995c7622009-03-30 14:02:47 -04001993 reiserfs_update_sd(th, inode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001994
Jeff Mahoney58d85422014-04-23 10:00:38 -04001995 err = journal_end(th);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001996 if (err)
1997 goto out;
Jeff Mahoney995c7622009-03-30 14:02:47 -04001998 err = journal_begin(th, inode->i_sb,
Alexander Zarochentzev23f9e0f2006-03-25 03:06:57 -08001999 JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002000 if (err)
2001 goto out;
Jeff Mahoney995c7622009-03-30 14:02:47 -04002002 reiserfs_update_inode_transaction(inode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002003 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04002004 } while (file_size > ROUND_UP(new_file_size) &&
Jeff Mahoney995c7622009-03-30 14:02:47 -04002005 search_for_position_by_key(inode->i_sb, &s_item_key,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002006 &s_search_path) == POSITION_FOUND);
2007
Jeff Mahoneyee939612009-03-30 14:02:50 -04002008 RFALSE(file_size > ROUND_UP(new_file_size),
Fabian Frederick53872ed2014-08-08 14:21:10 -07002009 "PAP-5680: truncate did not finish: new_file_size %lld, current %lld, oid %d",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002010 new_file_size, file_size, s_item_key.on_disk_key.k_objectid);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002011
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002012update_and_out:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002013 if (update_timestamps) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04002014 /* this is truncate, not file closing */
Jeff Mahoney995c7622009-03-30 14:02:47 -04002015 inode->i_mtime = CURRENT_TIME_SEC;
2016 inode->i_ctime = CURRENT_TIME_SEC;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002017 }
Jeff Mahoney995c7622009-03-30 14:02:47 -04002018 reiserfs_update_sd(th, inode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002019
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002020out:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002021 pathrelse(&s_search_path);
2022 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002023}
2024
Linus Torvalds1da177e2005-04-16 15:20:36 -07002025#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoney098297b2014-04-23 10:00:36 -04002026/* this makes sure, that we __append__, not overwrite or add holes */
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -08002027static void check_research_for_paste(struct treepath *path,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002028 const struct cpu_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002029{
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04002030 struct item_head *found_ih = tp_item_head(path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002031
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002032 if (is_direct_le_ih(found_ih)) {
2033 if (le_ih_k_offset(found_ih) +
2034 op_bytes_number(found_ih,
2035 get_last_bh(path)->b_size) !=
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002036 cpu_key_k_offset(key)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002037 || op_bytes_number(found_ih,
2038 get_last_bh(path)->b_size) !=
2039 pos_in_item(path))
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002040 reiserfs_panic(NULL, "PAP-5720", "found direct item "
2041 "%h or position (%d) does not match "
2042 "to key %K", found_ih,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002043 pos_in_item(path), key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002044 }
2045 if (is_indirect_le_ih(found_ih)) {
2046 if (le_ih_k_offset(found_ih) +
2047 op_bytes_number(found_ih,
2048 get_last_bh(path)->b_size) !=
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002049 cpu_key_k_offset(key)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002050 || I_UNFM_NUM(found_ih) != pos_in_item(path)
2051 || get_ih_free_space(found_ih) != 0)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002052 reiserfs_panic(NULL, "PAP-5730", "found indirect "
2053 "item (%h) or position (%d) does not "
2054 "match to key (%K)",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002055 found_ih, pos_in_item(path), key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002056 }
2057}
2058#endif /* config reiserfs check */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002059
Jeff Mahoney098297b2014-04-23 10:00:36 -04002060/*
2061 * Paste bytes to the existing item.
2062 * Returns bytes number pasted into the item.
2063 */
2064int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th,
2065 /* Path to the pasted item. */
2066 struct treepath *search_path,
2067 /* Key to search for the needed item. */
2068 const struct cpu_key *key,
2069 /* Inode item belongs to */
2070 struct inode *inode,
2071 /* Pointer to the bytes to paste. */
2072 const char *body,
2073 /* Size of pasted bytes. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002074 int pasted_size)
Jeff Mahoney098297b2014-04-23 10:00:36 -04002075{
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002076 struct super_block *sb = inode->i_sb;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002077 struct tree_balance s_paste_balance;
2078 int retval;
2079 int fs_gen;
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002080 int depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002081
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002082 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002083
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002084 fs_gen = get_generation(inode->i_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002085
2086#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002087 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2088 "reiserquota paste_into_item(): allocating %u id=%u type=%c",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002089 pasted_size, inode->i_uid,
Jeff Mahoneya228bf82014-04-23 10:00:42 -04002090 key2type(&key->on_disk_key));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002091#endif
2092
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002093 depth = reiserfs_write_unlock_nested(sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002094 retval = dquot_alloc_space_nodirty(inode, pasted_size);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002095 reiserfs_write_lock_nested(sb, depth);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002096 if (retval) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002097 pathrelse(search_path);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002098 return retval;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002099 }
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002100 init_tb_struct(th, &s_paste_balance, th->t_super, search_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04002101 pasted_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002102#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002103 s_paste_balance.key = key->on_disk_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002104#endif
2105
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002106 /* DQUOT_* can schedule, must check before the fix_nodes */
2107 if (fs_changed(fs_gen, inode->i_sb)) {
2108 goto search_again;
2109 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002110
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002111 while ((retval =
2112 fix_nodes(M_PASTE, &s_paste_balance, NULL,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002113 body)) == REPEAT_SEARCH) {
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002114search_again:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002115 /* file system changed while we were in the fix_nodes */
2116 PROC_INFO_INC(th->t_super, paste_into_item_restarted);
2117 retval =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002118 search_for_position_by_key(th->t_super, key,
2119 search_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002120 if (retval == IO_ERROR) {
2121 retval = -EIO;
2122 goto error_out;
2123 }
2124 if (retval == POSITION_FOUND) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04002125 reiserfs_warning(inode->i_sb, "PAP-5710",
2126 "entry or pasted byte (%K) exists",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002127 key);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002128 retval = -EEXIST;
2129 goto error_out;
2130 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002131#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002132 check_research_for_paste(search_path, key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002133#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002134 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002135
Jeff Mahoney098297b2014-04-23 10:00:36 -04002136 /*
2137 * Perform balancing after all resources are collected by fix_nodes,
2138 * and accessing them will not risk triggering schedule.
2139 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002140 if (retval == CARRY_ON) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002141 do_balance(&s_paste_balance, NULL /*ih */ , body, M_PASTE);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002142 return 0;
2143 }
2144 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002145error_out:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002146 /* this also releases the path */
2147 unfix_nodes(&s_paste_balance);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002148#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002149 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2150 "reiserquota paste_into_item(): freeing %u id=%u type=%c",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002151 pasted_size, inode->i_uid,
Jeff Mahoneya228bf82014-04-23 10:00:42 -04002152 key2type(&key->on_disk_key));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002153#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002154 depth = reiserfs_write_unlock_nested(sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002155 dquot_free_space_nodirty(inode, pasted_size);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002156 reiserfs_write_lock_nested(sb, depth);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002157 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002158}
2159
Jeff Mahoney098297b2014-04-23 10:00:36 -04002160/*
2161 * Insert new item into the buffer at the path.
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002162 * th - active transaction handle
2163 * path - path to the inserted item
2164 * ih - pointer to the item header to insert
2165 * body - pointer to the bytes to insert
2166 */
2167int reiserfs_insert_item(struct reiserfs_transaction_handle *th,
2168 struct treepath *path, const struct cpu_key *key,
2169 struct item_head *ih, struct inode *inode,
2170 const char *body)
2171{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002172 struct tree_balance s_ins_balance;
2173 int retval;
2174 int fs_gen = 0;
2175 int quota_bytes = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002176
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002177 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002178
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002179 if (inode) { /* Do we count quotas for item? */
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002180 int depth;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002181 fs_gen = get_generation(inode->i_sb);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002182 quota_bytes = ih_item_len(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002183
Jeff Mahoney098297b2014-04-23 10:00:36 -04002184 /*
2185 * hack so the quota code doesn't have to guess
2186 * if the file has a tail, links are always tails,
2187 * so there's no guessing needed
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002188 */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002189 if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(ih))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002190 quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002191#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002192 reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE,
2193 "reiserquota insert_item(): allocating %u id=%u type=%c",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002194 quota_bytes, inode->i_uid, head2type(ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002195#endif
Jeff Mahoney098297b2014-04-23 10:00:36 -04002196 /*
2197 * We can't dirty inode here. It would be immediately
2198 * written but appropriate stat item isn't inserted yet...
2199 */
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002200 depth = reiserfs_write_unlock_nested(inode->i_sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002201 retval = dquot_alloc_space_nodirty(inode, quota_bytes);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002202 reiserfs_write_lock_nested(inode->i_sb, depth);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002203 if (retval) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002204 pathrelse(path);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002205 return retval;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002206 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002207 }
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002208 init_tb_struct(th, &s_ins_balance, th->t_super, path,
2209 IH_SIZE + ih_item_len(ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002210#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002211 s_ins_balance.key = key->on_disk_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002212#endif
Jeff Mahoney098297b2014-04-23 10:00:36 -04002213 /*
2214 * DQUOT_* can schedule, must check to be sure calling
2215 * fix_nodes is safe
2216 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002217 if (inode && fs_changed(fs_gen, inode->i_sb)) {
2218 goto search_again;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002219 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002220
2221 while ((retval =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002222 fix_nodes(M_INSERT, &s_ins_balance, ih,
2223 body)) == REPEAT_SEARCH) {
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002224search_again:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002225 /* file system changed while we were in the fix_nodes */
2226 PROC_INFO_INC(th->t_super, insert_item_restarted);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002227 retval = search_item(th->t_super, key, path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002228 if (retval == IO_ERROR) {
2229 retval = -EIO;
2230 goto error_out;
2231 }
2232 if (retval == ITEM_FOUND) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04002233 reiserfs_warning(th->t_super, "PAP-5760",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002234 "key %K already exists in the tree",
2235 key);
2236 retval = -EEXIST;
2237 goto error_out;
2238 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002239 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002240
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002241 /* make balancing after all resources will be collected at a time */
2242 if (retval == CARRY_ON) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002243 do_balance(&s_ins_balance, ih, body, M_INSERT);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002244 return 0;
2245 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002246
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002247 retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
Jeff Mahoneycf776a72014-04-23 10:00:41 -04002248error_out:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002249 /* also releases the path */
2250 unfix_nodes(&s_ins_balance);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002251#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002252 reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE,
2253 "reiserquota insert_item(): freeing %u id=%u type=%c",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002254 quota_bytes, inode->i_uid, head2type(ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002255#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002256 if (inode) {
2257 int depth = reiserfs_write_unlock_nested(inode->i_sb);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05002258 dquot_free_space_nodirty(inode, quota_bytes);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04002259 reiserfs_write_lock_nested(inode->i_sb, depth);
2260 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002261 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002262}