11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 31da177e4SLinus Torvalds */ 41da177e4SLinus Torvalds 51da177e4SLinus Torvalds /* 61da177e4SLinus Torvalds * Written by Anatoly P. Pinchuk pap@namesys.botik.ru 71da177e4SLinus Torvalds * Programm System Institute 81da177e4SLinus Torvalds * Pereslavl-Zalessky Russia 91da177e4SLinus Torvalds */ 101da177e4SLinus Torvalds 111da177e4SLinus Torvalds /* 121da177e4SLinus Torvalds * This file contains functions dealing with S+tree 131da177e4SLinus Torvalds * 141da177e4SLinus Torvalds * B_IS_IN_TREE 151da177e4SLinus Torvalds * copy_item_head 161da177e4SLinus Torvalds * comp_short_keys 171da177e4SLinus Torvalds * comp_keys 181da177e4SLinus Torvalds * comp_short_le_keys 191da177e4SLinus Torvalds * le_key2cpu_key 201da177e4SLinus Torvalds * comp_le_keys 211da177e4SLinus Torvalds * bin_search 221da177e4SLinus Torvalds * get_lkey 231da177e4SLinus Torvalds * get_rkey 241da177e4SLinus Torvalds * key_in_buffer 251da177e4SLinus Torvalds * decrement_bcount 261da177e4SLinus Torvalds * reiserfs_check_path 271da177e4SLinus Torvalds * pathrelse_and_restore 281da177e4SLinus Torvalds * pathrelse 291da177e4SLinus Torvalds * search_by_key_reada 301da177e4SLinus Torvalds * search_by_key 311da177e4SLinus Torvalds * search_for_position_by_key 321da177e4SLinus Torvalds * comp_items 331da177e4SLinus Torvalds * prepare_for_direct_item 341da177e4SLinus Torvalds * prepare_for_direntry_item 351da177e4SLinus Torvalds * prepare_for_delete_or_cut 361da177e4SLinus Torvalds * calc_deleted_bytes_number 371da177e4SLinus Torvalds * init_tb_struct 381da177e4SLinus Torvalds * padd_item 391da177e4SLinus Torvalds * reiserfs_delete_item 401da177e4SLinus Torvalds * reiserfs_delete_solid_item 411da177e4SLinus Torvalds * reiserfs_delete_object 421da177e4SLinus Torvalds * maybe_indirect_to_direct 431da177e4SLinus Torvalds * indirect_to_direct_roll_back 441da177e4SLinus Torvalds * reiserfs_cut_from_item 451da177e4SLinus Torvalds * truncate_directory 461da177e4SLinus Torvalds * reiserfs_do_truncate 471da177e4SLinus Torvalds * reiserfs_paste_into_item 481da177e4SLinus Torvalds * reiserfs_insert_item 491da177e4SLinus Torvalds */ 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds #include <linux/time.h> 521da177e4SLinus Torvalds #include <linux/string.h> 531da177e4SLinus Torvalds #include <linux/pagemap.h> 541da177e4SLinus Torvalds #include <linux/reiserfs_fs.h> 551da177e4SLinus Torvalds #include <linux/buffer_head.h> 561da177e4SLinus Torvalds #include <linux/quotaops.h> 571da177e4SLinus Torvalds 581da177e4SLinus Torvalds /* Does the buffer contain a disk block which is in the tree. */ 59*ad31a4fcSJeff Mahoney inline int B_IS_IN_TREE(const struct buffer_head *bh) 601da177e4SLinus Torvalds { 611da177e4SLinus Torvalds 62*ad31a4fcSJeff Mahoney RFALSE(B_LEVEL(bh) > MAX_HEIGHT, 63*ad31a4fcSJeff Mahoney "PAP-1010: block (%b) has too big level (%z)", bh, bh); 641da177e4SLinus Torvalds 65*ad31a4fcSJeff Mahoney return (B_LEVEL(bh) != FREE_LEVEL); 661da177e4SLinus Torvalds } 671da177e4SLinus Torvalds 681da177e4SLinus Torvalds // 691da177e4SLinus Torvalds // to gets item head in le form 701da177e4SLinus Torvalds // 711da177e4SLinus Torvalds inline void copy_item_head(struct item_head *p_v_to, 721da177e4SLinus Torvalds const struct item_head *p_v_from) 731da177e4SLinus Torvalds { 741da177e4SLinus Torvalds memcpy(p_v_to, p_v_from, IH_SIZE); 751da177e4SLinus Torvalds } 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 781da177e4SLinus Torvalds form. k2 is pointer to cpu variable. For key of items of the same 791da177e4SLinus Torvalds object this returns 0. 801da177e4SLinus Torvalds Returns: -1 if key1 < key2 811da177e4SLinus Torvalds 0 if key1 == key2 821da177e4SLinus Torvalds 1 if key1 > key2 */ 831da177e4SLinus Torvalds inline int comp_short_keys(const struct reiserfs_key *le_key, 841da177e4SLinus Torvalds const struct cpu_key *cpu_key) 851da177e4SLinus Torvalds { 866b9f5829SAl Viro __u32 n; 876b9f5829SAl Viro n = le32_to_cpu(le_key->k_dir_id); 886b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_dir_id) 891da177e4SLinus Torvalds return -1; 906b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_dir_id) 911da177e4SLinus Torvalds return 1; 926b9f5829SAl Viro n = le32_to_cpu(le_key->k_objectid); 936b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_objectid) 946b9f5829SAl Viro return -1; 956b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_objectid) 966b9f5829SAl Viro return 1; 971da177e4SLinus Torvalds return 0; 981da177e4SLinus Torvalds } 991da177e4SLinus Torvalds 1001da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 1011da177e4SLinus Torvalds form. k2 is pointer to cpu variable. 1021da177e4SLinus Torvalds Compare keys using all 4 key fields. 1031da177e4SLinus Torvalds Returns: -1 if key1 < key2 0 1041da177e4SLinus Torvalds if key1 = key2 1 if key1 > key2 */ 105bd4c625cSLinus Torvalds static inline int comp_keys(const struct reiserfs_key *le_key, 106bd4c625cSLinus Torvalds const struct cpu_key *cpu_key) 1071da177e4SLinus Torvalds { 1081da177e4SLinus Torvalds int retval; 1091da177e4SLinus Torvalds 1101da177e4SLinus Torvalds retval = comp_short_keys(le_key, cpu_key); 1111da177e4SLinus Torvalds if (retval) 1121da177e4SLinus Torvalds return retval; 113bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) < 114bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1151da177e4SLinus Torvalds return -1; 116bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) > 117bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1181da177e4SLinus Torvalds return 1; 1191da177e4SLinus Torvalds 1201da177e4SLinus Torvalds if (cpu_key->key_length == 3) 1211da177e4SLinus Torvalds return 0; 1221da177e4SLinus Torvalds 1231da177e4SLinus Torvalds /* this part is needed only when tail conversion is in progress */ 124bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) < 125bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1261da177e4SLinus Torvalds return -1; 1271da177e4SLinus Torvalds 128bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) > 129bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1301da177e4SLinus Torvalds return 1; 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds return 0; 1331da177e4SLinus Torvalds } 1341da177e4SLinus Torvalds 135bd4c625cSLinus Torvalds inline int comp_short_le_keys(const struct reiserfs_key *key1, 136bd4c625cSLinus Torvalds const struct reiserfs_key *key2) 1371da177e4SLinus Torvalds { 1381da177e4SLinus Torvalds __u32 *p_s_1_u32, *p_s_2_u32; 1391da177e4SLinus Torvalds int n_key_length = REISERFS_SHORT_KEY_LEN; 1401da177e4SLinus Torvalds 1411da177e4SLinus Torvalds p_s_1_u32 = (__u32 *) key1; 1421da177e4SLinus Torvalds p_s_2_u32 = (__u32 *) key2; 1431da177e4SLinus Torvalds for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) { 1441da177e4SLinus Torvalds if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32)) 1451da177e4SLinus Torvalds return -1; 1461da177e4SLinus Torvalds if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32)) 1471da177e4SLinus Torvalds return 1; 1481da177e4SLinus Torvalds } 1491da177e4SLinus Torvalds return 0; 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 1521da177e4SLinus Torvalds inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from) 1531da177e4SLinus Torvalds { 1546b9f5829SAl Viro int version; 1551da177e4SLinus Torvalds to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id); 1561da177e4SLinus Torvalds to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid); 1571da177e4SLinus Torvalds 1581da177e4SLinus Torvalds // find out version of the key 1596b9f5829SAl Viro version = le_key_version(from); 1606b9f5829SAl Viro to->version = version; 1616b9f5829SAl Viro to->on_disk_key.k_offset = le_key_k_offset(version, from); 1626b9f5829SAl Viro to->on_disk_key.k_type = le_key_k_type(version, from); 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds // this does not say which one is bigger, it only returns 1 if keys 1661da177e4SLinus Torvalds // are not equal, 0 otherwise 167bd4c625cSLinus Torvalds inline int comp_le_keys(const struct reiserfs_key *k1, 168bd4c625cSLinus Torvalds const struct reiserfs_key *k2) 1691da177e4SLinus Torvalds { 1701da177e4SLinus Torvalds return memcmp(k1, k2, sizeof(struct reiserfs_key)); 1711da177e4SLinus Torvalds } 1721da177e4SLinus Torvalds 1731da177e4SLinus Torvalds /************************************************************************** 1741da177e4SLinus Torvalds * Binary search toolkit function * 1751da177e4SLinus Torvalds * Search for an item in the array by the item key * 1761da177e4SLinus Torvalds * Returns: 1 if found, 0 if not found; * 1771da177e4SLinus Torvalds * *p_n_pos = number of the searched element if found, else the * 1781da177e4SLinus Torvalds * number of the first element that is larger than p_v_key. * 1791da177e4SLinus Torvalds **************************************************************************/ 1801da177e4SLinus Torvalds /* For those not familiar with binary search: n_lbound is the leftmost item that it 1811da177e4SLinus Torvalds could be, n_rbound the rightmost item that it could be. We examine the item 1821da177e4SLinus Torvalds halfway between n_lbound and n_rbound, and that tells us either that we can increase 1831da177e4SLinus Torvalds n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that 1841da177e4SLinus Torvalds there are no possible items, and we have not found it. With each examination we 1851da177e4SLinus Torvalds cut the number of possible items it could be by one more than half rounded down, 1861da177e4SLinus Torvalds or we find it. */ 187bd4c625cSLinus Torvalds static inline int bin_search(const void *p_v_key, /* Key to search for. */ 1881da177e4SLinus Torvalds const void *p_v_base, /* First item in the array. */ 1891da177e4SLinus Torvalds int p_n_num, /* Number of items in the array. */ 1901da177e4SLinus Torvalds int p_n_width, /* Item size in the array. 1911da177e4SLinus Torvalds searched. Lest the reader be 1921da177e4SLinus Torvalds confused, note that this is crafted 1931da177e4SLinus Torvalds as a general function, and when it 1941da177e4SLinus Torvalds is applied specifically to the array 1951da177e4SLinus Torvalds of item headers in a node, p_n_width 1961da177e4SLinus Torvalds is actually the item header size not 1971da177e4SLinus Torvalds the item size. */ 1981da177e4SLinus Torvalds int *p_n_pos /* Number of the searched for element. */ 199bd4c625cSLinus Torvalds ) 200bd4c625cSLinus Torvalds { 2011da177e4SLinus Torvalds int n_rbound, n_lbound, n_j; 2021da177e4SLinus Torvalds 203bd4c625cSLinus Torvalds for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2; 204bd4c625cSLinus Torvalds n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2) 205bd4c625cSLinus Torvalds switch (comp_keys 206bd4c625cSLinus Torvalds ((struct reiserfs_key *)((char *)p_v_base + 207bd4c625cSLinus Torvalds n_j * p_n_width), 208bd4c625cSLinus Torvalds (struct cpu_key *)p_v_key)) { 209bd4c625cSLinus Torvalds case -1: 210bd4c625cSLinus Torvalds n_lbound = n_j + 1; 211bd4c625cSLinus Torvalds continue; 212bd4c625cSLinus Torvalds case 1: 213bd4c625cSLinus Torvalds n_rbound = n_j - 1; 214bd4c625cSLinus Torvalds continue; 215bd4c625cSLinus Torvalds case 0: 216bd4c625cSLinus Torvalds *p_n_pos = n_j; 217bd4c625cSLinus Torvalds return ITEM_FOUND; /* Key found in the array. */ 2181da177e4SLinus Torvalds } 2191da177e4SLinus Torvalds 2201da177e4SLinus Torvalds /* bin_search did not find given key, it returns position of key, 2211da177e4SLinus Torvalds that is minimal and greater than the given one. */ 2221da177e4SLinus Torvalds *p_n_pos = n_lbound; 2231da177e4SLinus Torvalds return ITEM_NOT_FOUND; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 2271da177e4SLinus Torvalds extern struct tree_balance *cur_tb; 2281da177e4SLinus Torvalds #endif 2291da177e4SLinus Torvalds 2301da177e4SLinus Torvalds /* Minimal possible key. It is never in the tree. */ 2311da177e4SLinus Torvalds const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} }; 2321da177e4SLinus Torvalds 2331da177e4SLinus Torvalds /* Maximal possible key. It is never in the tree. */ 23452c1da39SAdrian Bunk static const struct reiserfs_key MAX_KEY = { 2353e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2363e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2373e8962beSAl Viro {{__constant_cpu_to_le32(0xffffffff), 2383e8962beSAl Viro __constant_cpu_to_le32(0xffffffff)},} 2393e8962beSAl Viro }; 2401da177e4SLinus Torvalds 2411da177e4SLinus Torvalds /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom 2421da177e4SLinus Torvalds of the path, and going upwards. We must check the path's validity at each step. If the key is not in 2431da177e4SLinus Torvalds the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this 2441da177e4SLinus Torvalds case we return a special key, either MIN_KEY or MAX_KEY. */ 245fec6d055SJosef "Jeff" Sipek static inline const struct reiserfs_key *get_lkey(const struct treepath 246bd4c625cSLinus Torvalds *p_s_chk_path, 247bd4c625cSLinus Torvalds const struct super_block 248a9dd3643SJeff Mahoney *sb) 249bd4c625cSLinus Torvalds { 2501da177e4SLinus Torvalds int n_position, n_path_offset = p_s_chk_path->path_length; 2511da177e4SLinus Torvalds struct buffer_head *p_s_parent; 2521da177e4SLinus Torvalds 2531da177e4SLinus Torvalds RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET, 2541da177e4SLinus Torvalds "PAP-5010: invalid offset in the path"); 2551da177e4SLinus Torvalds 2561da177e4SLinus Torvalds /* While not higher in path than first element. */ 2571da177e4SLinus Torvalds while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 2581da177e4SLinus Torvalds 259bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 260bd4c625cSLinus Torvalds (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)), 2611da177e4SLinus Torvalds "PAP-5020: parent is not uptodate"); 2621da177e4SLinus Torvalds 2631da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 264bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 265bd4c625cSLinus Torvalds (p_s_parent = 266bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) 2671da177e4SLinus Torvalds return &MAX_KEY; 2681da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 269bd4c625cSLinus Torvalds if ((n_position = 270bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_chk_path, 271bd4c625cSLinus Torvalds n_path_offset)) > 272bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_parent)) 2731da177e4SLinus Torvalds return &MAX_KEY; 2741da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 2751da177e4SLinus Torvalds if (B_N_CHILD_NUM(p_s_parent, n_position) != 276bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, 277bd4c625cSLinus Torvalds n_path_offset + 1)->b_blocknr) 2781da177e4SLinus Torvalds return &MAX_KEY; 2791da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not equal to zero. */ 2801da177e4SLinus Torvalds if (n_position) 2811da177e4SLinus Torvalds return B_N_PDELIM_KEY(p_s_parent, n_position - 1); 2821da177e4SLinus Torvalds } 2831da177e4SLinus Torvalds /* Return MIN_KEY if we are in the root of the buffer tree. */ 284bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 285a9dd3643SJeff Mahoney b_blocknr == SB_ROOT_BLOCK(sb)) 2861da177e4SLinus Torvalds return &MIN_KEY; 2871da177e4SLinus Torvalds return &MAX_KEY; 2881da177e4SLinus Torvalds } 2891da177e4SLinus Torvalds 2901da177e4SLinus Torvalds /* Get delimiting key of the buffer at the path and its right neighbor. */ 291fec6d055SJosef "Jeff" Sipek inline const struct reiserfs_key *get_rkey(const struct treepath *p_s_chk_path, 292a9dd3643SJeff Mahoney const struct super_block *sb) 293bd4c625cSLinus Torvalds { 294bd4c625cSLinus Torvalds int n_position, n_path_offset = p_s_chk_path->path_length; 2951da177e4SLinus Torvalds struct buffer_head *p_s_parent; 2961da177e4SLinus Torvalds 2971da177e4SLinus Torvalds RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET, 2981da177e4SLinus Torvalds "PAP-5030: invalid offset in the path"); 2991da177e4SLinus Torvalds 3001da177e4SLinus Torvalds while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 3011da177e4SLinus Torvalds 302bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 303bd4c625cSLinus Torvalds (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)), 3041da177e4SLinus Torvalds "PAP-5040: parent is not uptodate"); 3051da177e4SLinus Torvalds 3061da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 307bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 308bd4c625cSLinus Torvalds (p_s_parent = 309bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) 3101da177e4SLinus Torvalds return &MIN_KEY; 3111da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 312bd4c625cSLinus Torvalds if ((n_position = 313bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_chk_path, 314bd4c625cSLinus Torvalds n_path_offset)) > 315bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_parent)) 3161da177e4SLinus Torvalds return &MIN_KEY; 3171da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 3181da177e4SLinus Torvalds if (B_N_CHILD_NUM(p_s_parent, n_position) != 319bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, 320bd4c625cSLinus Torvalds n_path_offset + 1)->b_blocknr) 3211da177e4SLinus Torvalds return &MIN_KEY; 3221da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not the last one. */ 3231da177e4SLinus Torvalds if (n_position != B_NR_ITEMS(p_s_parent)) 3241da177e4SLinus Torvalds return B_N_PDELIM_KEY(p_s_parent, n_position); 3251da177e4SLinus Torvalds } 3261da177e4SLinus Torvalds /* Return MAX_KEY if we are in the root of the buffer tree. */ 327bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 328a9dd3643SJeff Mahoney b_blocknr == SB_ROOT_BLOCK(sb)) 3291da177e4SLinus Torvalds return &MAX_KEY; 3301da177e4SLinus Torvalds return &MIN_KEY; 3311da177e4SLinus Torvalds } 3321da177e4SLinus Torvalds 3331da177e4SLinus Torvalds /* Check whether a key is contained in the tree rooted from a buffer at a path. */ 3341da177e4SLinus Torvalds /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in 3351da177e4SLinus Torvalds the path. These delimiting keys are stored at least one level above that buffer in the tree. If the 3361da177e4SLinus Torvalds buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in 3371da177e4SLinus Torvalds this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */ 338fec6d055SJosef "Jeff" Sipek static inline int key_in_buffer(struct treepath *p_s_chk_path, /* Path which should be checked. */ 3391da177e4SLinus Torvalds const struct cpu_key *p_s_key, /* Key which should be checked. */ 340a9dd3643SJeff Mahoney struct super_block *sb /* Super block pointer. */ 341bd4c625cSLinus Torvalds ) 342bd4c625cSLinus Torvalds { 3431da177e4SLinus Torvalds 344bd4c625cSLinus Torvalds RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET 345bd4c625cSLinus Torvalds || p_s_chk_path->path_length > MAX_HEIGHT, 3461da177e4SLinus Torvalds "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)", 3471da177e4SLinus Torvalds p_s_key, p_s_chk_path->path_length); 3481da177e4SLinus Torvalds RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev, 3491da177e4SLinus Torvalds "PAP-5060: device must not be NODEV"); 3501da177e4SLinus Torvalds 351a9dd3643SJeff Mahoney if (comp_keys(get_lkey(p_s_chk_path, sb), p_s_key) == 1) 3521da177e4SLinus Torvalds /* left delimiting key is bigger, that the key we look for */ 3531da177e4SLinus Torvalds return 0; 354a9dd3643SJeff Mahoney // if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, sb)) != -1 ) 355a9dd3643SJeff Mahoney if (comp_keys(get_rkey(p_s_chk_path, sb), p_s_key) != 1) 3561da177e4SLinus Torvalds /* p_s_key must be less than right delimitiing key */ 3571da177e4SLinus Torvalds return 0; 3581da177e4SLinus Torvalds return 1; 3591da177e4SLinus Torvalds } 3601da177e4SLinus Torvalds 361fec6d055SJosef "Jeff" Sipek int reiserfs_check_path(struct treepath *p) 362bd4c625cSLinus Torvalds { 3631da177e4SLinus Torvalds RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET, 3641da177e4SLinus Torvalds "path not properly relsed"); 3651da177e4SLinus Torvalds return 0; 3661da177e4SLinus Torvalds } 3671da177e4SLinus Torvalds 3683cd6dbe6SJeff Mahoney /* Drop the reference to each buffer in a path and restore 3693cd6dbe6SJeff Mahoney * dirty bits clean when preparing the buffer for the log. 3703cd6dbe6SJeff Mahoney * This version should only be called from fix_nodes() */ 3713cd6dbe6SJeff Mahoney void pathrelse_and_restore(struct super_block *sb, 3723cd6dbe6SJeff Mahoney struct treepath *p_s_search_path) 373bd4c625cSLinus Torvalds { 3741da177e4SLinus Torvalds int n_path_offset = p_s_search_path->path_length; 3751da177e4SLinus Torvalds 3761da177e4SLinus Torvalds RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 3771da177e4SLinus Torvalds "clm-4000: invalid path offset"); 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { 3803cd6dbe6SJeff Mahoney struct buffer_head *bh; 3813cd6dbe6SJeff Mahoney bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--); 3823cd6dbe6SJeff Mahoney reiserfs_restore_prepared_buffer(sb, bh); 3833cd6dbe6SJeff Mahoney brelse(bh); 3841da177e4SLinus Torvalds } 3851da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 3861da177e4SLinus Torvalds } 3871da177e4SLinus Torvalds 3883cd6dbe6SJeff Mahoney /* Drop the reference to each buffer in a path */ 389fec6d055SJosef "Jeff" Sipek void pathrelse(struct treepath *p_s_search_path) 390bd4c625cSLinus Torvalds { 3911da177e4SLinus Torvalds int n_path_offset = p_s_search_path->path_length; 3921da177e4SLinus Torvalds 3931da177e4SLinus Torvalds RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 3941da177e4SLinus Torvalds "PAP-5090: invalid path offset"); 3951da177e4SLinus Torvalds 3961da177e4SLinus Torvalds while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) 3971da177e4SLinus Torvalds brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--)); 3981da177e4SLinus Torvalds 3991da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 4001da177e4SLinus Torvalds } 4011da177e4SLinus Torvalds 4021da177e4SLinus Torvalds static int is_leaf(char *buf, int blocksize, struct buffer_head *bh) 4031da177e4SLinus Torvalds { 4041da177e4SLinus Torvalds struct block_head *blkh; 4051da177e4SLinus Torvalds struct item_head *ih; 4061da177e4SLinus Torvalds int used_space; 4071da177e4SLinus Torvalds int prev_location; 4081da177e4SLinus Torvalds int i; 4091da177e4SLinus Torvalds int nr; 4101da177e4SLinus Torvalds 4111da177e4SLinus Torvalds blkh = (struct block_head *)buf; 4121da177e4SLinus Torvalds if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) { 41345b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5080", 41445b03d5eSJeff Mahoney "this should be caught earlier"); 4151da177e4SLinus Torvalds return 0; 4161da177e4SLinus Torvalds } 4171da177e4SLinus Torvalds 4181da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 4191da177e4SLinus Torvalds if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) { 4201da177e4SLinus Torvalds /* item number is too big or too small */ 42145b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5081", 42245b03d5eSJeff Mahoney "nr_item seems wrong: %z", bh); 4231da177e4SLinus Torvalds return 0; 4241da177e4SLinus Torvalds } 4251da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1; 4261da177e4SLinus Torvalds used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih)); 4271da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 4281da177e4SLinus Torvalds /* free space does not match to calculated amount of use space */ 42945b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5082", 43045b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 4311da177e4SLinus Torvalds return 0; 4321da177e4SLinus Torvalds } 4331da177e4SLinus Torvalds // FIXME: it is_leaf will hit performance too much - we may have 4341da177e4SLinus Torvalds // return 1 here 4351da177e4SLinus Torvalds 4361da177e4SLinus Torvalds /* check tables of item heads */ 4371da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE); 4381da177e4SLinus Torvalds prev_location = blocksize; 4391da177e4SLinus Torvalds for (i = 0; i < nr; i++, ih++) { 4401da177e4SLinus Torvalds if (le_ih_k_type(ih) == TYPE_ANY) { 44145b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5083", 44245b03d5eSJeff Mahoney "wrong item type for item %h", 443bd4c625cSLinus Torvalds ih); 4441da177e4SLinus Torvalds return 0; 4451da177e4SLinus Torvalds } 446bd4c625cSLinus Torvalds if (ih_location(ih) >= blocksize 447bd4c625cSLinus Torvalds || ih_location(ih) < IH_SIZE * nr) { 44845b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5084", 44945b03d5eSJeff Mahoney "item location seems wrong: %h", 450bd4c625cSLinus Torvalds ih); 4511da177e4SLinus Torvalds return 0; 4521da177e4SLinus Torvalds } 453bd4c625cSLinus Torvalds if (ih_item_len(ih) < 1 454bd4c625cSLinus Torvalds || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) { 45545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5085", 45645b03d5eSJeff Mahoney "item length seems wrong: %h", 457bd4c625cSLinus Torvalds ih); 4581da177e4SLinus Torvalds return 0; 4591da177e4SLinus Torvalds } 4601da177e4SLinus Torvalds if (prev_location - ih_location(ih) != ih_item_len(ih)) { 46145b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5086", 46245b03d5eSJeff Mahoney "item location seems wrong " 46345b03d5eSJeff Mahoney "(second one): %h", ih); 4641da177e4SLinus Torvalds return 0; 4651da177e4SLinus Torvalds } 4661da177e4SLinus Torvalds prev_location = ih_location(ih); 4671da177e4SLinus Torvalds } 4681da177e4SLinus Torvalds 4691da177e4SLinus Torvalds // one may imagine much more checks 4701da177e4SLinus Torvalds return 1; 4711da177e4SLinus Torvalds } 4721da177e4SLinus Torvalds 4731da177e4SLinus Torvalds /* returns 1 if buf looks like an internal node, 0 otherwise */ 4741da177e4SLinus Torvalds static int is_internal(char *buf, int blocksize, struct buffer_head *bh) 4751da177e4SLinus Torvalds { 4761da177e4SLinus Torvalds struct block_head *blkh; 4771da177e4SLinus Torvalds int nr; 4781da177e4SLinus Torvalds int used_space; 4791da177e4SLinus Torvalds 4801da177e4SLinus Torvalds blkh = (struct block_head *)buf; 4811da177e4SLinus Torvalds nr = blkh_level(blkh); 4821da177e4SLinus Torvalds if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) { 4831da177e4SLinus Torvalds /* this level is not possible for internal nodes */ 48445b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5087", 48545b03d5eSJeff Mahoney "this should be caught earlier"); 4861da177e4SLinus Torvalds return 0; 4871da177e4SLinus Torvalds } 4881da177e4SLinus Torvalds 4891da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 4901da177e4SLinus Torvalds if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) { 4911da177e4SLinus Torvalds /* for internal which is not root we might check min number of keys */ 49245b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5088", 49345b03d5eSJeff Mahoney "number of key seems wrong: %z", bh); 4941da177e4SLinus Torvalds return 0; 4951da177e4SLinus Torvalds } 4961da177e4SLinus Torvalds 4971da177e4SLinus Torvalds used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1); 4981da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 49945b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5089", 50045b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 5011da177e4SLinus Torvalds return 0; 5021da177e4SLinus Torvalds } 5031da177e4SLinus Torvalds // one may imagine much more checks 5041da177e4SLinus Torvalds return 1; 5051da177e4SLinus Torvalds } 5061da177e4SLinus Torvalds 5071da177e4SLinus Torvalds // make sure that bh contains formatted node of reiserfs tree of 5081da177e4SLinus Torvalds // 'level'-th level 5091da177e4SLinus Torvalds static int is_tree_node(struct buffer_head *bh, int level) 5101da177e4SLinus Torvalds { 5111da177e4SLinus Torvalds if (B_LEVEL(bh) != level) { 51245b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5090", "node level %d does " 51345b03d5eSJeff Mahoney "not match to the expected one %d", 5141da177e4SLinus Torvalds B_LEVEL(bh), level); 5151da177e4SLinus Torvalds return 0; 5161da177e4SLinus Torvalds } 5171da177e4SLinus Torvalds if (level == DISK_LEAF_NODE_LEVEL) 5181da177e4SLinus Torvalds return is_leaf(bh->b_data, bh->b_size, bh); 5191da177e4SLinus Torvalds 5201da177e4SLinus Torvalds return is_internal(bh->b_data, bh->b_size, bh); 5211da177e4SLinus Torvalds } 5221da177e4SLinus Torvalds 5231da177e4SLinus Torvalds #define SEARCH_BY_KEY_READA 16 5241da177e4SLinus Torvalds 5251da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 5261da177e4SLinus Torvalds static void search_by_key_reada(struct super_block *s, 5271da177e4SLinus Torvalds struct buffer_head **bh, 5283ee16670SJeff Mahoney b_blocknr_t *b, int num) 5291da177e4SLinus Torvalds { 5301da177e4SLinus Torvalds int i, j; 5311da177e4SLinus Torvalds 5321da177e4SLinus Torvalds for (i = 0; i < num; i++) { 5331da177e4SLinus Torvalds bh[i] = sb_getblk(s, b[i]); 5341da177e4SLinus Torvalds } 5351da177e4SLinus Torvalds for (j = 0; j < i; j++) { 5361da177e4SLinus Torvalds /* 5371da177e4SLinus Torvalds * note, this needs attention if we are getting rid of the BKL 5381da177e4SLinus Torvalds * you have to make sure the prepared bit isn't set on this buffer 5391da177e4SLinus Torvalds */ 5401da177e4SLinus Torvalds if (!buffer_uptodate(bh[j])) 5411da177e4SLinus Torvalds ll_rw_block(READA, 1, bh + j); 5421da177e4SLinus Torvalds brelse(bh[j]); 5431da177e4SLinus Torvalds } 5441da177e4SLinus Torvalds } 5451da177e4SLinus Torvalds 5461da177e4SLinus Torvalds /************************************************************************** 5471da177e4SLinus Torvalds * Algorithm SearchByKey * 5481da177e4SLinus Torvalds * look for item in the Disk S+Tree by its key * 549a9dd3643SJeff Mahoney * Input: sb - super block * 5501da177e4SLinus Torvalds * p_s_key - pointer to the key to search * 5511da177e4SLinus Torvalds * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR * 5521da177e4SLinus Torvalds * p_s_search_path - path from the root to the needed leaf * 5531da177e4SLinus Torvalds **************************************************************************/ 5541da177e4SLinus Torvalds 5551da177e4SLinus Torvalds /* This function fills up the path from the root to the leaf as it 5561da177e4SLinus Torvalds descends the tree looking for the key. It uses reiserfs_bread to 5571da177e4SLinus Torvalds try to find buffers in the cache given their block number. If it 5581da177e4SLinus Torvalds does not find them in the cache it reads them from disk. For each 5591da177e4SLinus Torvalds node search_by_key finds using reiserfs_bread it then uses 5601da177e4SLinus Torvalds bin_search to look through that node. bin_search will find the 5611da177e4SLinus Torvalds position of the block_number of the next node if it is looking 5621da177e4SLinus Torvalds through an internal node. If it is looking through a leaf node 5631da177e4SLinus Torvalds bin_search will find the position of the item which has key either 5641da177e4SLinus Torvalds equal to given key, or which is the maximal key less than the given 5651da177e4SLinus Torvalds key. search_by_key returns a path that must be checked for the 5661da177e4SLinus Torvalds correctness of the top of the path but need not be checked for the 5671da177e4SLinus Torvalds correctness of the bottom of the path */ 5681da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 569a9dd3643SJeff Mahoney int search_by_key(struct super_block *sb, const struct cpu_key *p_s_key, /* Key to search. */ 570fec6d055SJosef "Jeff" Sipek struct treepath *p_s_search_path,/* This structure was 5711da177e4SLinus Torvalds allocated and initialized 5721da177e4SLinus Torvalds by the calling 5731da177e4SLinus Torvalds function. It is filled up 5741da177e4SLinus Torvalds by this function. */ 5751da177e4SLinus Torvalds int n_stop_level /* How far down the tree to search. To 5761da177e4SLinus Torvalds stop at leaf level - set to 5771da177e4SLinus Torvalds DISK_LEAF_NODE_LEVEL */ 578bd4c625cSLinus Torvalds ) 579bd4c625cSLinus Torvalds { 5803ee16670SJeff Mahoney b_blocknr_t n_block_number; 5811da177e4SLinus Torvalds int expected_level; 582*ad31a4fcSJeff Mahoney struct buffer_head *bh; 5831da177e4SLinus Torvalds struct path_element *p_s_last_element; 5841da177e4SLinus Torvalds int n_node_level, n_retval; 5851da177e4SLinus Torvalds int right_neighbor_of_leaf_node; 5861da177e4SLinus Torvalds int fs_gen; 5871da177e4SLinus Torvalds struct buffer_head *reada_bh[SEARCH_BY_KEY_READA]; 5883ee16670SJeff Mahoney b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA]; 5891da177e4SLinus Torvalds int reada_count = 0; 5901da177e4SLinus Torvalds 5911da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 5921da177e4SLinus Torvalds int n_repeat_counter = 0; 5931da177e4SLinus Torvalds #endif 5941da177e4SLinus Torvalds 595a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key); 5961da177e4SLinus Torvalds 5971da177e4SLinus Torvalds /* As we add each node to a path we increase its count. This means that 5981da177e4SLinus Torvalds we must be careful to release all nodes in a path before we either 5991da177e4SLinus Torvalds discard the path struct or re-use the path struct, as we do here. */ 6001da177e4SLinus Torvalds 6013cd6dbe6SJeff Mahoney pathrelse(p_s_search_path); 6021da177e4SLinus Torvalds 6031da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6041da177e4SLinus Torvalds 6051da177e4SLinus Torvalds /* With each iteration of this loop we search through the items in the 6061da177e4SLinus Torvalds current node, and calculate the next current node(next path element) 6071da177e4SLinus Torvalds for the next iteration of this loop.. */ 608a9dd3643SJeff Mahoney n_block_number = SB_ROOT_BLOCK(sb); 6091da177e4SLinus Torvalds expected_level = -1; 6101da177e4SLinus Torvalds while (1) { 6111da177e4SLinus Torvalds 6121da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 6131da177e4SLinus Torvalds if (!(++n_repeat_counter % 50000)) 614a9dd3643SJeff Mahoney reiserfs_warning(sb, "PAP-5100", 61545b03d5eSJeff Mahoney "%s: there were %d iterations of " 61645b03d5eSJeff Mahoney "while loop looking for key %K", 617bd4c625cSLinus Torvalds current->comm, n_repeat_counter, 618bd4c625cSLinus Torvalds p_s_key); 6191da177e4SLinus Torvalds #endif 6201da177e4SLinus Torvalds 6211da177e4SLinus Torvalds /* prep path to have another element added to it. */ 622bd4c625cSLinus Torvalds p_s_last_element = 623bd4c625cSLinus Torvalds PATH_OFFSET_PELEMENT(p_s_search_path, 624bd4c625cSLinus Torvalds ++p_s_search_path->path_length); 625a9dd3643SJeff Mahoney fs_gen = get_generation(sb); 6261da177e4SLinus Torvalds 6271da177e4SLinus Torvalds /* Read the next tree node, and set the last element in the path to 6281da177e4SLinus Torvalds have a pointer to it. */ 629*ad31a4fcSJeff Mahoney if ((bh = p_s_last_element->pe_buffer = 630a9dd3643SJeff Mahoney sb_getblk(sb, n_block_number))) { 631*ad31a4fcSJeff Mahoney if (!buffer_uptodate(bh) && reada_count > 1) 632a9dd3643SJeff Mahoney search_by_key_reada(sb, reada_bh, 6331da177e4SLinus Torvalds reada_blocks, reada_count); 634*ad31a4fcSJeff Mahoney ll_rw_block(READ, 1, &bh); 635*ad31a4fcSJeff Mahoney wait_on_buffer(bh); 636*ad31a4fcSJeff Mahoney if (!buffer_uptodate(bh)) 6371da177e4SLinus Torvalds goto io_error; 6381da177e4SLinus Torvalds } else { 6391da177e4SLinus Torvalds io_error: 6401da177e4SLinus Torvalds p_s_search_path->path_length--; 6411da177e4SLinus Torvalds pathrelse(p_s_search_path); 6421da177e4SLinus Torvalds return IO_ERROR; 6431da177e4SLinus Torvalds } 6441da177e4SLinus Torvalds reada_count = 0; 6451da177e4SLinus Torvalds if (expected_level == -1) 646a9dd3643SJeff Mahoney expected_level = SB_TREE_HEIGHT(sb); 6471da177e4SLinus Torvalds expected_level--; 6481da177e4SLinus Torvalds 6491da177e4SLinus Torvalds /* It is possible that schedule occurred. We must check whether the key 6501da177e4SLinus Torvalds to search is still in the tree rooted from the current buffer. If 6511da177e4SLinus Torvalds not then repeat search from the root. */ 652a9dd3643SJeff Mahoney if (fs_changed(fs_gen, sb) && 653*ad31a4fcSJeff Mahoney (!B_IS_IN_TREE(bh) || 654*ad31a4fcSJeff Mahoney B_LEVEL(bh) != expected_level || 655a9dd3643SJeff Mahoney !key_in_buffer(p_s_search_path, p_s_key, sb))) { 656a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key_fs_changed); 657a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key_restarted); 658a9dd3643SJeff Mahoney PROC_INFO_INC(sb, 659bd4c625cSLinus Torvalds sbk_restarted[expected_level - 1]); 6603cd6dbe6SJeff Mahoney pathrelse(p_s_search_path); 6611da177e4SLinus Torvalds 6621da177e4SLinus Torvalds /* Get the root block number so that we can repeat the search 6631da177e4SLinus Torvalds starting from the root. */ 664a9dd3643SJeff Mahoney n_block_number = SB_ROOT_BLOCK(sb); 6651da177e4SLinus Torvalds expected_level = -1; 6661da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6671da177e4SLinus Torvalds 6681da177e4SLinus Torvalds /* repeat search from the root */ 6691da177e4SLinus Torvalds continue; 6701da177e4SLinus Torvalds } 6711da177e4SLinus Torvalds 6721da177e4SLinus Torvalds /* only check that the key is in the buffer if p_s_key is not 6731da177e4SLinus Torvalds equal to the MAX_KEY. Latter case is only possible in 6741da177e4SLinus Torvalds "finish_unfinished()" processing during mount. */ 6751da177e4SLinus Torvalds RFALSE(comp_keys(&MAX_KEY, p_s_key) && 676a9dd3643SJeff Mahoney !key_in_buffer(p_s_search_path, p_s_key, sb), 6771da177e4SLinus Torvalds "PAP-5130: key is not in the buffer"); 6781da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 6791da177e4SLinus Torvalds if (cur_tb) { 6801da177e4SLinus Torvalds print_cur_tb("5140"); 681a9dd3643SJeff Mahoney reiserfs_panic(sb, "PAP-5140", 682c3a9c210SJeff Mahoney "schedule occurred in do_balance!"); 6831da177e4SLinus Torvalds } 6841da177e4SLinus Torvalds #endif 6851da177e4SLinus Torvalds 6861da177e4SLinus Torvalds // make sure, that the node contents look like a node of 6871da177e4SLinus Torvalds // certain level 688*ad31a4fcSJeff Mahoney if (!is_tree_node(bh, expected_level)) { 689a9dd3643SJeff Mahoney reiserfs_error(sb, "vs-5150", 69045b03d5eSJeff Mahoney "invalid format found in block %ld. " 691*ad31a4fcSJeff Mahoney "Fsck?", bh->b_blocknr); 6921da177e4SLinus Torvalds pathrelse(p_s_search_path); 6931da177e4SLinus Torvalds return IO_ERROR; 6941da177e4SLinus Torvalds } 6951da177e4SLinus Torvalds 6961da177e4SLinus Torvalds /* ok, we have acquired next formatted node in the tree */ 697*ad31a4fcSJeff Mahoney n_node_level = B_LEVEL(bh); 6981da177e4SLinus Torvalds 699*ad31a4fcSJeff Mahoney PROC_INFO_BH_STAT(sb, bh, n_node_level - 1); 7001da177e4SLinus Torvalds 7011da177e4SLinus Torvalds RFALSE(n_node_level < n_stop_level, 7021da177e4SLinus Torvalds "vs-5152: tree level (%d) is less than stop level (%d)", 7031da177e4SLinus Torvalds n_node_level, n_stop_level); 7041da177e4SLinus Torvalds 705*ad31a4fcSJeff Mahoney n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(bh, 0), 706*ad31a4fcSJeff Mahoney B_NR_ITEMS(bh), 707bd4c625cSLinus Torvalds (n_node_level == 708bd4c625cSLinus Torvalds DISK_LEAF_NODE_LEVEL) ? IH_SIZE : 709bd4c625cSLinus Torvalds KEY_SIZE, 7101da177e4SLinus Torvalds &(p_s_last_element->pe_position)); 7111da177e4SLinus Torvalds if (n_node_level == n_stop_level) { 7121da177e4SLinus Torvalds return n_retval; 7131da177e4SLinus Torvalds } 7141da177e4SLinus Torvalds 7151da177e4SLinus Torvalds /* we are not in the stop level */ 7161da177e4SLinus Torvalds if (n_retval == ITEM_FOUND) 7171da177e4SLinus Torvalds /* item has been found, so we choose the pointer which is to the right of the found one */ 7181da177e4SLinus Torvalds p_s_last_element->pe_position++; 7191da177e4SLinus Torvalds 7201da177e4SLinus Torvalds /* if item was not found we choose the position which is to 7211da177e4SLinus Torvalds the left of the found item. This requires no code, 7221da177e4SLinus Torvalds bin_search did it already. */ 7231da177e4SLinus Torvalds 7241da177e4SLinus Torvalds /* So we have chosen a position in the current node which is 7251da177e4SLinus Torvalds an internal node. Now we calculate child block number by 7261da177e4SLinus Torvalds position in the node. */ 727bd4c625cSLinus Torvalds n_block_number = 728*ad31a4fcSJeff Mahoney B_N_CHILD_NUM(bh, p_s_last_element->pe_position); 7291da177e4SLinus Torvalds 7301da177e4SLinus Torvalds /* if we are going to read leaf nodes, try for read ahead as well */ 7311da177e4SLinus Torvalds if ((p_s_search_path->reada & PATH_READA) && 732bd4c625cSLinus Torvalds n_node_level == DISK_LEAF_NODE_LEVEL + 1) { 7331da177e4SLinus Torvalds int pos = p_s_last_element->pe_position; 734*ad31a4fcSJeff Mahoney int limit = B_NR_ITEMS(bh); 7351da177e4SLinus Torvalds struct reiserfs_key *le_key; 7361da177e4SLinus Torvalds 7371da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7381da177e4SLinus Torvalds limit = 0; 7391da177e4SLinus Torvalds while (reada_count < SEARCH_BY_KEY_READA) { 7401da177e4SLinus Torvalds if (pos == limit) 7411da177e4SLinus Torvalds break; 742bd4c625cSLinus Torvalds reada_blocks[reada_count++] = 743*ad31a4fcSJeff Mahoney B_N_CHILD_NUM(bh, pos); 7441da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7451da177e4SLinus Torvalds pos--; 7461da177e4SLinus Torvalds else 7471da177e4SLinus Torvalds pos++; 7481da177e4SLinus Torvalds 7491da177e4SLinus Torvalds /* 7501da177e4SLinus Torvalds * check to make sure we're in the same object 7511da177e4SLinus Torvalds */ 752*ad31a4fcSJeff Mahoney le_key = B_N_PDELIM_KEY(bh, pos); 7531da177e4SLinus Torvalds if (le32_to_cpu(le_key->k_objectid) != 754bd4c625cSLinus Torvalds p_s_key->on_disk_key.k_objectid) { 7551da177e4SLinus Torvalds break; 7561da177e4SLinus Torvalds } 7571da177e4SLinus Torvalds } 7581da177e4SLinus Torvalds } 7591da177e4SLinus Torvalds } 7601da177e4SLinus Torvalds } 7611da177e4SLinus Torvalds 7621da177e4SLinus Torvalds /* Form the path to an item and position in this item which contains 7631da177e4SLinus Torvalds file byte defined by p_s_key. If there is no such item 7641da177e4SLinus Torvalds corresponding to the key, we point the path to the item with 7651da177e4SLinus Torvalds maximal key less than p_s_key, and *p_n_pos_in_item is set to one 7661da177e4SLinus Torvalds past the last entry/byte in the item. If searching for entry in a 7671da177e4SLinus Torvalds directory item, and it is not found, *p_n_pos_in_item is set to one 7681da177e4SLinus Torvalds entry more than the entry with maximal key which is less than the 7691da177e4SLinus Torvalds sought key. 7701da177e4SLinus Torvalds 7711da177e4SLinus Torvalds Note that if there is no entry in this same node which is one more, 7721da177e4SLinus Torvalds then we point to an imaginary entry. for direct items, the 7731da177e4SLinus Torvalds position is in units of bytes, for indirect items the position is 7741da177e4SLinus Torvalds in units of blocknr entries, for directory items the position is in 7751da177e4SLinus Torvalds units of directory entries. */ 7761da177e4SLinus Torvalds 7771da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 778a9dd3643SJeff Mahoney int search_for_position_by_key(struct super_block *sb, /* Pointer to the super block. */ 7791da177e4SLinus Torvalds const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */ 780fec6d055SJosef "Jeff" Sipek struct treepath *p_s_search_path /* Filled up by this function. */ 781bd4c625cSLinus Torvalds ) 782bd4c625cSLinus Torvalds { 7831da177e4SLinus Torvalds struct item_head *p_le_ih; /* pointer to on-disk structure */ 7841da177e4SLinus Torvalds int n_blk_size; 7851da177e4SLinus Torvalds loff_t item_offset, offset; 7861da177e4SLinus Torvalds struct reiserfs_dir_entry de; 7871da177e4SLinus Torvalds int retval; 7881da177e4SLinus Torvalds 7891da177e4SLinus Torvalds /* If searching for directory entry. */ 7901da177e4SLinus Torvalds if (is_direntry_cpu_key(p_cpu_key)) 791a9dd3643SJeff Mahoney return search_by_entry_key(sb, p_cpu_key, p_s_search_path, 792bd4c625cSLinus Torvalds &de); 7931da177e4SLinus Torvalds 7941da177e4SLinus Torvalds /* If not searching for directory entry. */ 7951da177e4SLinus Torvalds 7961da177e4SLinus Torvalds /* If item is found. */ 797a9dd3643SJeff Mahoney retval = search_item(sb, p_cpu_key, p_s_search_path); 7981da177e4SLinus Torvalds if (retval == IO_ERROR) 7991da177e4SLinus Torvalds return retval; 8001da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 8011da177e4SLinus Torvalds 802bd4c625cSLinus Torvalds RFALSE(!ih_item_len 803bd4c625cSLinus Torvalds (B_N_PITEM_HEAD 804bd4c625cSLinus Torvalds (PATH_PLAST_BUFFER(p_s_search_path), 8051da177e4SLinus Torvalds PATH_LAST_POSITION(p_s_search_path))), 8061da177e4SLinus Torvalds "PAP-5165: item length equals zero"); 8071da177e4SLinus Torvalds 8081da177e4SLinus Torvalds pos_in_item(p_s_search_path) = 0; 8091da177e4SLinus Torvalds return POSITION_FOUND; 8101da177e4SLinus Torvalds } 8111da177e4SLinus Torvalds 8121da177e4SLinus Torvalds RFALSE(!PATH_LAST_POSITION(p_s_search_path), 8131da177e4SLinus Torvalds "PAP-5170: position equals zero"); 8141da177e4SLinus Torvalds 8151da177e4SLinus Torvalds /* Item is not found. Set path to the previous item. */ 816bd4c625cSLinus Torvalds p_le_ih = 817bd4c625cSLinus Torvalds B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), 818bd4c625cSLinus Torvalds --PATH_LAST_POSITION(p_s_search_path)); 819a9dd3643SJeff Mahoney n_blk_size = sb->s_blocksize; 8201da177e4SLinus Torvalds 8211da177e4SLinus Torvalds if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) { 8221da177e4SLinus Torvalds return FILE_NOT_FOUND; 8231da177e4SLinus Torvalds } 8241da177e4SLinus Torvalds // FIXME: quite ugly this far 8251da177e4SLinus Torvalds 8261da177e4SLinus Torvalds item_offset = le_ih_k_offset(p_le_ih); 8271da177e4SLinus Torvalds offset = cpu_key_k_offset(p_cpu_key); 8281da177e4SLinus Torvalds 8291da177e4SLinus Torvalds /* Needed byte is contained in the item pointed to by the path. */ 8301da177e4SLinus Torvalds if (item_offset <= offset && 8311da177e4SLinus Torvalds item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) { 8321da177e4SLinus Torvalds pos_in_item(p_s_search_path) = offset - item_offset; 8331da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) { 8341da177e4SLinus Torvalds pos_in_item(p_s_search_path) /= n_blk_size; 8351da177e4SLinus Torvalds } 8361da177e4SLinus Torvalds return POSITION_FOUND; 8371da177e4SLinus Torvalds } 8381da177e4SLinus Torvalds 8391da177e4SLinus Torvalds /* Needed byte is not contained in the item pointed to by the 8401da177e4SLinus Torvalds path. Set pos_in_item out of the item. */ 8411da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 842bd4c625cSLinus Torvalds pos_in_item(p_s_search_path) = 843bd4c625cSLinus Torvalds ih_item_len(p_le_ih) / UNFM_P_SIZE; 8441da177e4SLinus Torvalds else 8451da177e4SLinus Torvalds pos_in_item(p_s_search_path) = ih_item_len(p_le_ih); 8461da177e4SLinus Torvalds 8471da177e4SLinus Torvalds return POSITION_NOT_FOUND; 8481da177e4SLinus Torvalds } 8491da177e4SLinus Torvalds 8501da177e4SLinus Torvalds /* Compare given item and item pointed to by the path. */ 851fec6d055SJosef "Jeff" Sipek int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path) 8521da177e4SLinus Torvalds { 853*ad31a4fcSJeff Mahoney struct buffer_head *bh = PATH_PLAST_BUFFER(p_s_path); 8541da177e4SLinus Torvalds struct item_head *ih; 8551da177e4SLinus Torvalds 8561da177e4SLinus Torvalds /* Last buffer at the path is not in the tree. */ 857*ad31a4fcSJeff Mahoney if (!B_IS_IN_TREE(bh)) 8581da177e4SLinus Torvalds return 1; 8591da177e4SLinus Torvalds 8601da177e4SLinus Torvalds /* Last path position is invalid. */ 861*ad31a4fcSJeff Mahoney if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(bh)) 8621da177e4SLinus Torvalds return 1; 8631da177e4SLinus Torvalds 8641da177e4SLinus Torvalds /* we need only to know, whether it is the same item */ 8651da177e4SLinus Torvalds ih = get_ih(p_s_path); 8661da177e4SLinus Torvalds return memcmp(stored_ih, ih, IH_SIZE); 8671da177e4SLinus Torvalds } 8681da177e4SLinus Torvalds 8691da177e4SLinus Torvalds /* unformatted nodes are not logged anymore, ever. This is safe 8701da177e4SLinus Torvalds ** now 8711da177e4SLinus Torvalds */ 8721da177e4SLinus Torvalds #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1) 8731da177e4SLinus Torvalds 8741da177e4SLinus Torvalds // block can not be forgotten as it is in I/O or held by someone 8751da177e4SLinus Torvalds #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh))) 8761da177e4SLinus Torvalds 8771da177e4SLinus Torvalds // prepare for delete or cut of direct item 878fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direct_item(struct treepath *path, 8791da177e4SLinus Torvalds struct item_head *le_ih, 8801da177e4SLinus Torvalds struct inode *inode, 881bd4c625cSLinus Torvalds loff_t new_file_length, int *cut_size) 8821da177e4SLinus Torvalds { 8831da177e4SLinus Torvalds loff_t round_len; 8841da177e4SLinus Torvalds 8851da177e4SLinus Torvalds if (new_file_length == max_reiserfs_offset(inode)) { 8861da177e4SLinus Torvalds /* item has to be deleted */ 8871da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 8881da177e4SLinus Torvalds return M_DELETE; 8891da177e4SLinus Torvalds } 8901da177e4SLinus Torvalds // new file gets truncated 8911da177e4SLinus Torvalds if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) { 8921da177e4SLinus Torvalds // 8931da177e4SLinus Torvalds round_len = ROUND_UP(new_file_length); 8941da177e4SLinus Torvalds /* this was n_new_file_length < le_ih ... */ 8951da177e4SLinus Torvalds if (round_len < le_ih_k_offset(le_ih)) { 8961da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 8971da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 8981da177e4SLinus Torvalds } 8991da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9001da177e4SLinus Torvalds pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1); 9011da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - pos_in_item(path)); 9021da177e4SLinus Torvalds 9031da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9041da177e4SLinus Torvalds } 9051da177e4SLinus Torvalds 9061da177e4SLinus Torvalds // old file: items may have any length 9071da177e4SLinus Torvalds 9081da177e4SLinus Torvalds if (new_file_length < le_ih_k_offset(le_ih)) { 9091da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9101da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9111da177e4SLinus Torvalds } 9121da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9131da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - 914bd4c625cSLinus Torvalds (pos_in_item(path) = 915bd4c625cSLinus Torvalds new_file_length + 1 - le_ih_k_offset(le_ih))); 9161da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9171da177e4SLinus Torvalds } 9181da177e4SLinus Torvalds 919fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direntry_item(struct treepath *path, 9201da177e4SLinus Torvalds struct item_head *le_ih, 9211da177e4SLinus Torvalds struct inode *inode, 9221da177e4SLinus Torvalds loff_t new_file_length, 9231da177e4SLinus Torvalds int *cut_size) 9241da177e4SLinus Torvalds { 9251da177e4SLinus Torvalds if (le_ih_k_offset(le_ih) == DOT_OFFSET && 9261da177e4SLinus Torvalds new_file_length == max_reiserfs_offset(inode)) { 9271da177e4SLinus Torvalds RFALSE(ih_entry_count(le_ih) != 2, 9281da177e4SLinus Torvalds "PAP-5220: incorrect empty directory item (%h)", le_ih); 9291da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9301da177e4SLinus Torvalds return M_DELETE; /* Delete the directory item containing "." and ".." entry. */ 9311da177e4SLinus Torvalds } 9321da177e4SLinus Torvalds 9331da177e4SLinus Torvalds if (ih_entry_count(le_ih) == 1) { 9341da177e4SLinus Torvalds /* Delete the directory item such as there is one record only 9351da177e4SLinus Torvalds in this item */ 9361da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9371da177e4SLinus Torvalds return M_DELETE; 9381da177e4SLinus Torvalds } 9391da177e4SLinus Torvalds 9401da177e4SLinus Torvalds /* Cut one record from the directory item. */ 941bd4c625cSLinus Torvalds *cut_size = 942bd4c625cSLinus Torvalds -(DEH_SIZE + 943bd4c625cSLinus Torvalds entry_length(get_last_bh(path), le_ih, pos_in_item(path))); 9441da177e4SLinus Torvalds return M_CUT; 9451da177e4SLinus Torvalds } 9461da177e4SLinus Torvalds 94723f9e0f8SAlexander Zarochentzev #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1) 94823f9e0f8SAlexander Zarochentzev 9491da177e4SLinus Torvalds /* If the path points to a directory or direct item, calculate mode and the size cut, for balance. 9501da177e4SLinus Torvalds If the path points to an indirect item, remove some number of its unformatted nodes. 9511da177e4SLinus Torvalds In case of file truncate calculate whether this item must be deleted/truncated or last 9521da177e4SLinus Torvalds unformatted node of this item will be converted to a direct item. 9531da177e4SLinus Torvalds This function returns a determination of what balance mode the calling function should employ. */ 954fec6d055SJosef "Jeff" Sipek static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *p_s_path, const struct cpu_key *p_s_item_key, int *p_n_removed, /* Number of unformatted nodes which were removed 9551da177e4SLinus Torvalds from end of the file. */ 956bd4c625cSLinus Torvalds int *p_n_cut_size, unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */ 957bd4c625cSLinus Torvalds ) 958bd4c625cSLinus Torvalds { 959a9dd3643SJeff Mahoney struct super_block *sb = inode->i_sb; 9601da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path); 961*ad31a4fcSJeff Mahoney struct buffer_head *bh = PATH_PLAST_BUFFER(p_s_path); 9621da177e4SLinus Torvalds 9631da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 9641da177e4SLinus Torvalds 9651da177e4SLinus Torvalds /* Stat_data item. */ 9661da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) { 9671da177e4SLinus Torvalds 9681da177e4SLinus Torvalds RFALSE(n_new_file_length != max_reiserfs_offset(inode), 9691da177e4SLinus Torvalds "PAP-5210: mode must be M_DELETE"); 9701da177e4SLinus Torvalds 9711da177e4SLinus Torvalds *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih)); 9721da177e4SLinus Torvalds return M_DELETE; 9731da177e4SLinus Torvalds } 9741da177e4SLinus Torvalds 9751da177e4SLinus Torvalds /* Directory item. */ 9761da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) 977bd4c625cSLinus Torvalds return prepare_for_direntry_item(p_s_path, p_le_ih, inode, 978bd4c625cSLinus Torvalds n_new_file_length, 979bd4c625cSLinus Torvalds p_n_cut_size); 9801da177e4SLinus Torvalds 9811da177e4SLinus Torvalds /* Direct item. */ 9821da177e4SLinus Torvalds if (is_direct_le_ih(p_le_ih)) 983bd4c625cSLinus Torvalds return prepare_for_direct_item(p_s_path, p_le_ih, inode, 984bd4c625cSLinus Torvalds n_new_file_length, p_n_cut_size); 9851da177e4SLinus Torvalds 9861da177e4SLinus Torvalds /* Case of an indirect item. */ 9871da177e4SLinus Torvalds { 988a9dd3643SJeff Mahoney int blk_size = sb->s_blocksize; 98923f9e0f8SAlexander Zarochentzev struct item_head s_ih; 99023f9e0f8SAlexander Zarochentzev int need_re_search; 99123f9e0f8SAlexander Zarochentzev int delete = 0; 99223f9e0f8SAlexander Zarochentzev int result = M_CUT; 99323f9e0f8SAlexander Zarochentzev int pos = 0; 9941da177e4SLinus Torvalds 99523f9e0f8SAlexander Zarochentzev if ( n_new_file_length == max_reiserfs_offset (inode) ) { 99623f9e0f8SAlexander Zarochentzev /* prepare_for_delete_or_cut() is called by 99723f9e0f8SAlexander Zarochentzev * reiserfs_delete_item() */ 99823f9e0f8SAlexander Zarochentzev n_new_file_length = 0; 99923f9e0f8SAlexander Zarochentzev delete = 1; 100023f9e0f8SAlexander Zarochentzev } 10011da177e4SLinus Torvalds 10021da177e4SLinus Torvalds do { 100323f9e0f8SAlexander Zarochentzev need_re_search = 0; 100423f9e0f8SAlexander Zarochentzev *p_n_cut_size = 0; 1005*ad31a4fcSJeff Mahoney bh = PATH_PLAST_BUFFER(p_s_path); 10061da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 100723f9e0f8SAlexander Zarochentzev pos = I_UNFM_NUM(&s_ih); 10081da177e4SLinus Torvalds 100923f9e0f8SAlexander Zarochentzev while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) { 101087588dd6SAl Viro __le32 *unfm; 101187588dd6SAl Viro __u32 block; 10121da177e4SLinus Torvalds 101323f9e0f8SAlexander Zarochentzev /* Each unformatted block deletion may involve one additional 101423f9e0f8SAlexander Zarochentzev * bitmap block into the transaction, thereby the initial 101523f9e0f8SAlexander Zarochentzev * journal space reservation might not be enough. */ 101623f9e0f8SAlexander Zarochentzev if (!delete && (*p_n_cut_size) != 0 && 101723f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 101823f9e0f8SAlexander Zarochentzev break; 10191da177e4SLinus Torvalds } 10201da177e4SLinus Torvalds 1021*ad31a4fcSJeff Mahoney unfm = (__le32 *)B_I_PITEM(bh, &s_ih) + pos - 1; 102223f9e0f8SAlexander Zarochentzev block = get_block_num(unfm, 0); 10231da177e4SLinus Torvalds 102423f9e0f8SAlexander Zarochentzev if (block != 0) { 1025*ad31a4fcSJeff Mahoney reiserfs_prepare_for_journal(sb, bh, 1); 102623f9e0f8SAlexander Zarochentzev put_block_num(unfm, 0, 0); 1027*ad31a4fcSJeff Mahoney journal_mark_dirty(th, sb, bh); 102823f9e0f8SAlexander Zarochentzev reiserfs_free_block(th, inode, block, 1); 102923f9e0f8SAlexander Zarochentzev } 10301da177e4SLinus Torvalds 10311da177e4SLinus Torvalds cond_resched(); 103223f9e0f8SAlexander Zarochentzev 10331da177e4SLinus Torvalds if (item_moved (&s_ih, p_s_path)) { 103423f9e0f8SAlexander Zarochentzev need_re_search = 1; 10351da177e4SLinus Torvalds break; 10361da177e4SLinus Torvalds } 10371da177e4SLinus Torvalds 103823f9e0f8SAlexander Zarochentzev pos --; 10391da177e4SLinus Torvalds (*p_n_removed) ++; 104023f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= UNFM_P_SIZE; 10411da177e4SLinus Torvalds 104223f9e0f8SAlexander Zarochentzev if (pos == 0) { 104323f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= IH_SIZE; 104423f9e0f8SAlexander Zarochentzev result = M_DELETE; 10451da177e4SLinus Torvalds break; 10461da177e4SLinus Torvalds } 10471da177e4SLinus Torvalds } 104823f9e0f8SAlexander Zarochentzev /* a trick. If the buffer has been logged, this will do nothing. If 104923f9e0f8SAlexander Zarochentzev ** we've broken the loop without logging it, it will restore the 105023f9e0f8SAlexander Zarochentzev ** buffer */ 1051*ad31a4fcSJeff Mahoney reiserfs_restore_prepared_buffer(sb, bh); 105223f9e0f8SAlexander Zarochentzev } while (need_re_search && 1053a9dd3643SJeff Mahoney search_for_position_by_key(sb, p_s_item_key, p_s_path) == POSITION_FOUND); 105423f9e0f8SAlexander Zarochentzev pos_in_item(p_s_path) = pos * UNFM_P_SIZE; 10551da177e4SLinus Torvalds 105623f9e0f8SAlexander Zarochentzev if (*p_n_cut_size == 0) { 105723f9e0f8SAlexander Zarochentzev /* Nothing were cut. maybe convert last unformatted node to the 105823f9e0f8SAlexander Zarochentzev * direct item? */ 105923f9e0f8SAlexander Zarochentzev result = M_CONVERT; 106023f9e0f8SAlexander Zarochentzev } 106123f9e0f8SAlexander Zarochentzev return result; 10621da177e4SLinus Torvalds } 10631da177e4SLinus Torvalds } 10641da177e4SLinus Torvalds 10651da177e4SLinus Torvalds /* Calculate number of bytes which will be deleted or cut during balance */ 1066bd4c625cSLinus Torvalds static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode) 1067bd4c625cSLinus Torvalds { 10681da177e4SLinus Torvalds int n_del_size; 10691da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path); 10701da177e4SLinus Torvalds 10711da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 10721da177e4SLinus Torvalds return 0; 10731da177e4SLinus Torvalds 1074bd4c625cSLinus Torvalds n_del_size = 1075bd4c625cSLinus Torvalds (c_mode == 1076bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0]; 10771da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) { 10781da177e4SLinus Torvalds // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */ 10791da177e4SLinus Torvalds // we can't use EMPTY_DIR_SIZE, as old format dirs have a different 10801da177e4SLinus Torvalds // empty size. ick. FIXME, is this right? 10811da177e4SLinus Torvalds // 10821da177e4SLinus Torvalds return n_del_size; 10831da177e4SLinus Torvalds } 10841da177e4SLinus Torvalds 10851da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 1086bd4c625cSLinus Torvalds n_del_size = (n_del_size / UNFM_P_SIZE) * (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size); // - get_ih_free_space (p_le_ih); 10871da177e4SLinus Torvalds return n_del_size; 10881da177e4SLinus Torvalds } 10891da177e4SLinus Torvalds 1090bd4c625cSLinus Torvalds static void init_tb_struct(struct reiserfs_transaction_handle *th, 10911da177e4SLinus Torvalds struct tree_balance *p_s_tb, 1092a9dd3643SJeff Mahoney struct super_block *sb, 1093fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, int n_size) 1094bd4c625cSLinus Torvalds { 10951da177e4SLinus Torvalds 10961da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 10971da177e4SLinus Torvalds 10981da177e4SLinus Torvalds memset(p_s_tb, '\0', sizeof(struct tree_balance)); 10991da177e4SLinus Torvalds p_s_tb->transaction_handle = th; 1100a9dd3643SJeff Mahoney p_s_tb->tb_sb = sb; 11011da177e4SLinus Torvalds p_s_tb->tb_path = p_s_path; 11021da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL; 11031da177e4SLinus Torvalds PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0; 11041da177e4SLinus Torvalds p_s_tb->insert_size[0] = n_size; 11051da177e4SLinus Torvalds } 11061da177e4SLinus Torvalds 11071da177e4SLinus Torvalds void padd_item(char *item, int total_length, int length) 11081da177e4SLinus Torvalds { 11091da177e4SLinus Torvalds int i; 11101da177e4SLinus Torvalds 11111da177e4SLinus Torvalds for (i = total_length; i > length;) 11121da177e4SLinus Torvalds item[--i] = 0; 11131da177e4SLinus Torvalds } 11141da177e4SLinus Torvalds 11151da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 11161da177e4SLinus Torvalds char key2type(struct reiserfs_key *ih) 11171da177e4SLinus Torvalds { 11181da177e4SLinus Torvalds if (is_direntry_le_key(2, ih)) 11191da177e4SLinus Torvalds return 'd'; 11201da177e4SLinus Torvalds if (is_direct_le_key(2, ih)) 11211da177e4SLinus Torvalds return 'D'; 11221da177e4SLinus Torvalds if (is_indirect_le_key(2, ih)) 11231da177e4SLinus Torvalds return 'i'; 11241da177e4SLinus Torvalds if (is_statdata_le_key(2, ih)) 11251da177e4SLinus Torvalds return 's'; 11261da177e4SLinus Torvalds return 'u'; 11271da177e4SLinus Torvalds } 11281da177e4SLinus Torvalds 11291da177e4SLinus Torvalds char head2type(struct item_head *ih) 11301da177e4SLinus Torvalds { 11311da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) 11321da177e4SLinus Torvalds return 'd'; 11331da177e4SLinus Torvalds if (is_direct_le_ih(ih)) 11341da177e4SLinus Torvalds return 'D'; 11351da177e4SLinus Torvalds if (is_indirect_le_ih(ih)) 11361da177e4SLinus Torvalds return 'i'; 11371da177e4SLinus Torvalds if (is_statdata_le_ih(ih)) 11381da177e4SLinus Torvalds return 's'; 11391da177e4SLinus Torvalds return 'u'; 11401da177e4SLinus Torvalds } 11411da177e4SLinus Torvalds #endif 11421da177e4SLinus Torvalds 11431da177e4SLinus Torvalds /* Delete object item. */ 1144fec6d055SJosef "Jeff" Sipek int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the deleted item. */ 11451da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, /* Key to search for the deleted item. */ 11461da177e4SLinus Torvalds struct inode *p_s_inode, /* inode is here just to update i_blocks and quotas */ 1147bd4c625cSLinus Torvalds struct buffer_head *p_s_un_bh) 1148bd4c625cSLinus Torvalds { /* NULL or unformatted node pointer. */ 1149a9dd3643SJeff Mahoney struct super_block *sb = p_s_inode->i_sb; 11501da177e4SLinus Torvalds struct tree_balance s_del_balance; 11511da177e4SLinus Torvalds struct item_head s_ih; 11521da177e4SLinus Torvalds struct item_head *q_ih; 11531da177e4SLinus Torvalds int quota_cut_bytes; 1154bd4c625cSLinus Torvalds int n_ret_value, n_del_size, n_removed; 11551da177e4SLinus Torvalds 11561da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 11571da177e4SLinus Torvalds char c_mode; 11581da177e4SLinus Torvalds int n_iter = 0; 11591da177e4SLinus Torvalds #endif 11601da177e4SLinus Torvalds 11611da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11621da177e4SLinus Torvalds 1163a9dd3643SJeff Mahoney init_tb_struct(th, &s_del_balance, sb, p_s_path, 1164bd4c625cSLinus Torvalds 0 /*size is unknown */ ); 11651da177e4SLinus Torvalds 11661da177e4SLinus Torvalds while (1) { 11671da177e4SLinus Torvalds n_removed = 0; 11681da177e4SLinus Torvalds 11691da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 11701da177e4SLinus Torvalds n_iter++; 11711da177e4SLinus Torvalds c_mode = 11721da177e4SLinus Torvalds #endif 1173bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1174bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 1175bd4c625cSLinus Torvalds &n_del_size, 1176bd4c625cSLinus Torvalds max_reiserfs_offset(p_s_inode)); 11771da177e4SLinus Torvalds 11781da177e4SLinus Torvalds RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE"); 11791da177e4SLinus Torvalds 11801da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 11811da177e4SLinus Torvalds s_del_balance.insert_size[0] = n_del_size; 11821da177e4SLinus Torvalds 11831da177e4SLinus Torvalds n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL); 11841da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 11851da177e4SLinus Torvalds break; 11861da177e4SLinus Torvalds 1187a9dd3643SJeff Mahoney PROC_INFO_INC(sb, delete_item_restarted); 11881da177e4SLinus Torvalds 11891da177e4SLinus Torvalds // file system changed, repeat search 1190bd4c625cSLinus Torvalds n_ret_value = 1191a9dd3643SJeff Mahoney search_for_position_by_key(sb, p_s_item_key, p_s_path); 11921da177e4SLinus Torvalds if (n_ret_value == IO_ERROR) 11931da177e4SLinus Torvalds break; 11941da177e4SLinus Torvalds if (n_ret_value == FILE_NOT_FOUND) { 1195a9dd3643SJeff Mahoney reiserfs_warning(sb, "vs-5340", 1196bd4c625cSLinus Torvalds "no items of the file %K found", 1197bd4c625cSLinus Torvalds p_s_item_key); 11981da177e4SLinus Torvalds break; 11991da177e4SLinus Torvalds } 12001da177e4SLinus Torvalds } /* while (1) */ 12011da177e4SLinus Torvalds 12021da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 12031da177e4SLinus Torvalds unfix_nodes(&s_del_balance); 12041da177e4SLinus Torvalds return 0; 12051da177e4SLinus Torvalds } 12061da177e4SLinus Torvalds // reiserfs_delete_item returns item length when success 12071da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE); 12081da177e4SLinus Torvalds q_ih = get_ih(p_s_path); 12091da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(q_ih); 12101da177e4SLinus Torvalds 12111da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file 12121da177e4SLinus Torvalds ** has a tail. On tail insert, we allocate quota for 1 unformatted node. 12131da177e4SLinus Torvalds ** We test the offset because the tail might have been 12141da177e4SLinus Torvalds ** split into multiple items, and we only want to decrement for 12151da177e4SLinus Torvalds ** the unfm node once 12161da177e4SLinus Torvalds */ 12171da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) { 1218a9dd3643SJeff Mahoney if ((le_ih_k_offset(q_ih) & (sb->s_blocksize - 1)) == 1) { 1219a9dd3643SJeff Mahoney quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 12201da177e4SLinus Torvalds } else { 12211da177e4SLinus Torvalds quota_cut_bytes = 0; 12221da177e4SLinus Torvalds } 12231da177e4SLinus Torvalds } 12241da177e4SLinus Torvalds 12251da177e4SLinus Torvalds if (p_s_un_bh) { 12261da177e4SLinus Torvalds int off; 12271da177e4SLinus Torvalds char *data; 12281da177e4SLinus Torvalds 12291da177e4SLinus Torvalds /* We are in direct2indirect conversion, so move tail contents 12301da177e4SLinus Torvalds to the unformatted node */ 12311da177e4SLinus Torvalds /* note, we do the copy before preparing the buffer because we 12321da177e4SLinus Torvalds ** don't care about the contents of the unformatted node yet. 12331da177e4SLinus Torvalds ** the only thing we really care about is the direct item's data 12341da177e4SLinus Torvalds ** is in the unformatted node. 12351da177e4SLinus Torvalds ** 12361da177e4SLinus Torvalds ** Otherwise, we would have to call reiserfs_prepare_for_journal on 12371da177e4SLinus Torvalds ** the unformatted node, which might schedule, meaning we'd have to 12381da177e4SLinus Torvalds ** loop all the way back up to the start of the while loop. 12391da177e4SLinus Torvalds ** 12401da177e4SLinus Torvalds ** The unformatted node must be dirtied later on. We can't be 12411da177e4SLinus Torvalds ** sure here if the entire tail has been deleted yet. 12421da177e4SLinus Torvalds ** 12431da177e4SLinus Torvalds ** p_s_un_bh is from the page cache (all unformatted nodes are 12441da177e4SLinus Torvalds ** from the page cache) and might be a highmem page. So, we 12451da177e4SLinus Torvalds ** can't use p_s_un_bh->b_data. 12461da177e4SLinus Torvalds ** -clm 12471da177e4SLinus Torvalds */ 12481da177e4SLinus Torvalds 12491da177e4SLinus Torvalds data = kmap_atomic(p_s_un_bh->b_page, KM_USER0); 12501da177e4SLinus Torvalds off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1)); 12511da177e4SLinus Torvalds memcpy(data + off, 1252bd4c625cSLinus Torvalds B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), 1253bd4c625cSLinus Torvalds n_ret_value); 12541da177e4SLinus Torvalds kunmap_atomic(data, KM_USER0); 12551da177e4SLinus Torvalds } 12561da177e4SLinus Torvalds /* Perform balancing after all resources have been collected at once. */ 12571da177e4SLinus Torvalds do_balance(&s_del_balance, NULL, NULL, M_DELETE); 12581da177e4SLinus Torvalds 12591da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1260a9dd3643SJeff Mahoney reiserfs_debug(sb, REISERFS_DEBUG_CODE, 1261bd4c625cSLinus Torvalds "reiserquota delete_item(): freeing %u, id=%u type=%c", 1262bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih)); 12631da177e4SLinus Torvalds #endif 12641da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 12651da177e4SLinus Torvalds 12661da177e4SLinus Torvalds /* Return deleted body length */ 12671da177e4SLinus Torvalds return n_ret_value; 12681da177e4SLinus Torvalds } 12691da177e4SLinus Torvalds 12701da177e4SLinus Torvalds /* Summary Of Mechanisms For Handling Collisions Between Processes: 12711da177e4SLinus Torvalds 12721da177e4SLinus Torvalds deletion of the body of the object is performed by iput(), with the 12731da177e4SLinus Torvalds result that if multiple processes are operating on a file, the 12741da177e4SLinus Torvalds deletion of the body of the file is deferred until the last process 12751da177e4SLinus Torvalds that has an open inode performs its iput(). 12761da177e4SLinus Torvalds 12771da177e4SLinus Torvalds writes and truncates are protected from collisions by use of 12781da177e4SLinus Torvalds semaphores. 12791da177e4SLinus Torvalds 12801da177e4SLinus Torvalds creates, linking, and mknod are protected from collisions with other 12811da177e4SLinus Torvalds processes by making the reiserfs_add_entry() the last step in the 12821da177e4SLinus Torvalds creation, and then rolling back all changes if there was a collision. 12831da177e4SLinus Torvalds - Hans 12841da177e4SLinus Torvalds */ 12851da177e4SLinus Torvalds 12861da177e4SLinus Torvalds /* this deletes item which never gets split */ 12871da177e4SLinus Torvalds void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, 1288bd4c625cSLinus Torvalds struct inode *inode, struct reiserfs_key *key) 12891da177e4SLinus Torvalds { 12901da177e4SLinus Torvalds struct tree_balance tb; 12911da177e4SLinus Torvalds INITIALIZE_PATH(path); 12921da177e4SLinus Torvalds int item_len = 0; 12931da177e4SLinus Torvalds int tb_init = 0; 12941da177e4SLinus Torvalds struct cpu_key cpu_key; 12951da177e4SLinus Torvalds int retval; 12961da177e4SLinus Torvalds int quota_cut_bytes = 0; 12971da177e4SLinus Torvalds 12981da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 12991da177e4SLinus Torvalds 13001da177e4SLinus Torvalds le_key2cpu_key(&cpu_key, key); 13011da177e4SLinus Torvalds 13021da177e4SLinus Torvalds while (1) { 13031da177e4SLinus Torvalds retval = search_item(th->t_super, &cpu_key, &path); 13041da177e4SLinus Torvalds if (retval == IO_ERROR) { 13050030b645SJeff Mahoney reiserfs_error(th->t_super, "vs-5350", 130645b03d5eSJeff Mahoney "i/o failure occurred trying " 130745b03d5eSJeff Mahoney "to delete %K", &cpu_key); 13081da177e4SLinus Torvalds break; 13091da177e4SLinus Torvalds } 13101da177e4SLinus Torvalds if (retval != ITEM_FOUND) { 13111da177e4SLinus Torvalds pathrelse(&path); 13121da177e4SLinus Torvalds // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir 1313bd4c625cSLinus Torvalds if (! 1314bd4c625cSLinus Torvalds ((unsigned long long) 1315bd4c625cSLinus Torvalds GET_HASH_VALUE(le_key_k_offset 1316bd4c625cSLinus Torvalds (le_key_version(key), key)) == 0 1317bd4c625cSLinus Torvalds && (unsigned long long) 1318bd4c625cSLinus Torvalds GET_GENERATION_NUMBER(le_key_k_offset 1319bd4c625cSLinus Torvalds (le_key_version(key), 1320bd4c625cSLinus Torvalds key)) == 1)) 132145b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5355", 132245b03d5eSJeff Mahoney "%k not found", key); 13231da177e4SLinus Torvalds break; 13241da177e4SLinus Torvalds } 13251da177e4SLinus Torvalds if (!tb_init) { 13261da177e4SLinus Torvalds tb_init = 1; 13271da177e4SLinus Torvalds item_len = ih_item_len(PATH_PITEM_HEAD(&path)); 1328bd4c625cSLinus Torvalds init_tb_struct(th, &tb, th->t_super, &path, 1329bd4c625cSLinus Torvalds -(IH_SIZE + item_len)); 13301da177e4SLinus Torvalds } 13311da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path)); 13321da177e4SLinus Torvalds 13331da177e4SLinus Torvalds retval = fix_nodes(M_DELETE, &tb, NULL, NULL); 13341da177e4SLinus Torvalds if (retval == REPEAT_SEARCH) { 13351da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, delete_solid_item_restarted); 13361da177e4SLinus Torvalds continue; 13371da177e4SLinus Torvalds } 13381da177e4SLinus Torvalds 13391da177e4SLinus Torvalds if (retval == CARRY_ON) { 13401da177e4SLinus Torvalds do_balance(&tb, NULL, NULL, M_DELETE); 13411da177e4SLinus Torvalds if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */ 13421da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1343bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 1344bd4c625cSLinus Torvalds "reiserquota delete_solid_item(): freeing %u id=%u type=%c", 1345bd4c625cSLinus Torvalds quota_cut_bytes, inode->i_uid, 1346bd4c625cSLinus Torvalds key2type(key)); 13471da177e4SLinus Torvalds #endif 1348bd4c625cSLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, 1349bd4c625cSLinus Torvalds quota_cut_bytes); 13501da177e4SLinus Torvalds } 13511da177e4SLinus Torvalds break; 13521da177e4SLinus Torvalds } 13531da177e4SLinus Torvalds // IO_ERROR, NO_DISK_SPACE, etc 135445b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5360", 1355bd4c625cSLinus Torvalds "could not delete %K due to fix_nodes failure", 1356bd4c625cSLinus Torvalds &cpu_key); 13571da177e4SLinus Torvalds unfix_nodes(&tb); 13581da177e4SLinus Torvalds break; 13591da177e4SLinus Torvalds } 13601da177e4SLinus Torvalds 13611da177e4SLinus Torvalds reiserfs_check_path(&path); 13621da177e4SLinus Torvalds } 13631da177e4SLinus Torvalds 1364bd4c625cSLinus Torvalds int reiserfs_delete_object(struct reiserfs_transaction_handle *th, 1365bd4c625cSLinus Torvalds struct inode *inode) 13661da177e4SLinus Torvalds { 13671da177e4SLinus Torvalds int err; 13681da177e4SLinus Torvalds inode->i_size = 0; 13691da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 13701da177e4SLinus Torvalds 13711da177e4SLinus Torvalds /* for directory this deletes item containing "." and ".." */ 1372bd4c625cSLinus Torvalds err = 1373bd4c625cSLinus Torvalds reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ ); 13741da177e4SLinus Torvalds if (err) 13751da177e4SLinus Torvalds return err; 13761da177e4SLinus Torvalds 13771da177e4SLinus Torvalds #if defined( USE_INODE_GENERATION_COUNTER ) 1378bd4c625cSLinus Torvalds if (!old_format_only(th->t_super)) { 13793e8962beSAl Viro __le32 *inode_generation; 13801da177e4SLinus Torvalds 13811da177e4SLinus Torvalds inode_generation = 13821da177e4SLinus Torvalds &REISERFS_SB(th->t_super)->s_rs->s_inode_generation; 13839e902df6SMarcin Slusarz le32_add_cpu(inode_generation, 1); 13841da177e4SLinus Torvalds } 13851da177e4SLinus Torvalds /* USE_INODE_GENERATION_COUNTER */ 13861da177e4SLinus Torvalds #endif 13871da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 13881da177e4SLinus Torvalds 13891da177e4SLinus Torvalds return err; 13901da177e4SLinus Torvalds } 13911da177e4SLinus Torvalds 1392bd4c625cSLinus Torvalds static void unmap_buffers(struct page *page, loff_t pos) 1393bd4c625cSLinus Torvalds { 13941da177e4SLinus Torvalds struct buffer_head *bh; 13951da177e4SLinus Torvalds struct buffer_head *head; 13961da177e4SLinus Torvalds struct buffer_head *next; 13971da177e4SLinus Torvalds unsigned long tail_index; 13981da177e4SLinus Torvalds unsigned long cur_index; 13991da177e4SLinus Torvalds 14001da177e4SLinus Torvalds if (page) { 14011da177e4SLinus Torvalds if (page_has_buffers(page)) { 14021da177e4SLinus Torvalds tail_index = pos & (PAGE_CACHE_SIZE - 1); 14031da177e4SLinus Torvalds cur_index = 0; 14041da177e4SLinus Torvalds head = page_buffers(page); 14051da177e4SLinus Torvalds bh = head; 14061da177e4SLinus Torvalds do { 14071da177e4SLinus Torvalds next = bh->b_this_page; 14081da177e4SLinus Torvalds 14091da177e4SLinus Torvalds /* we want to unmap the buffers that contain the tail, and 14101da177e4SLinus Torvalds ** all the buffers after it (since the tail must be at the 14111da177e4SLinus Torvalds ** end of the file). We don't want to unmap file data 14121da177e4SLinus Torvalds ** before the tail, since it might be dirty and waiting to 14131da177e4SLinus Torvalds ** reach disk 14141da177e4SLinus Torvalds */ 14151da177e4SLinus Torvalds cur_index += bh->b_size; 14161da177e4SLinus Torvalds if (cur_index > tail_index) { 14171da177e4SLinus Torvalds reiserfs_unmap_buffer(bh); 14181da177e4SLinus Torvalds } 14191da177e4SLinus Torvalds bh = next; 14201da177e4SLinus Torvalds } while (bh != head); 14211da177e4SLinus Torvalds } 14221da177e4SLinus Torvalds } 14231da177e4SLinus Torvalds } 14241da177e4SLinus Torvalds 14251da177e4SLinus Torvalds static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, 14261da177e4SLinus Torvalds struct inode *p_s_inode, 14271da177e4SLinus Torvalds struct page *page, 1428fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 14291da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, 1430bd4c625cSLinus Torvalds loff_t n_new_file_size, char *p_c_mode) 1431bd4c625cSLinus Torvalds { 1432a9dd3643SJeff Mahoney struct super_block *sb = p_s_inode->i_sb; 1433a9dd3643SJeff Mahoney int n_block_size = sb->s_blocksize; 14341da177e4SLinus Torvalds int cut_bytes; 14351da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 143614a61442SEric Sesterhenn BUG_ON(n_new_file_size != p_s_inode->i_size); 14371da177e4SLinus Torvalds 14381da177e4SLinus Torvalds /* the page being sent in could be NULL if there was an i/o error 14391da177e4SLinus Torvalds ** reading in the last block. The user will hit problems trying to 14401da177e4SLinus Torvalds ** read the file, but for now we just skip the indirect2direct 14411da177e4SLinus Torvalds */ 14421da177e4SLinus Torvalds if (atomic_read(&p_s_inode->i_count) > 1 || 14431da177e4SLinus Torvalds !tail_has_to_be_packed(p_s_inode) || 14441da177e4SLinus Torvalds !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) { 14450222e657SJeff Mahoney /* leave tail in an unformatted node */ 14461da177e4SLinus Torvalds *p_c_mode = M_SKIP_BALANCING; 1447bd4c625cSLinus Torvalds cut_bytes = 1448bd4c625cSLinus Torvalds n_block_size - (n_new_file_size & (n_block_size - 1)); 14491da177e4SLinus Torvalds pathrelse(p_s_path); 14501da177e4SLinus Torvalds return cut_bytes; 14511da177e4SLinus Torvalds } 14521da177e4SLinus Torvalds /* Permorm the conversion to a direct_item. */ 14531da177e4SLinus Torvalds /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */ 1454bd4c625cSLinus Torvalds return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key, 1455bd4c625cSLinus Torvalds n_new_file_size, p_c_mode); 14561da177e4SLinus Torvalds } 14571da177e4SLinus Torvalds 14581da177e4SLinus Torvalds /* we did indirect_to_direct conversion. And we have inserted direct 14591da177e4SLinus Torvalds item successesfully, but there were no disk space to cut unfm 14601da177e4SLinus Torvalds pointer being converted. Therefore we have to delete inserted 14611da177e4SLinus Torvalds direct item(s) */ 1462bd4c625cSLinus Torvalds static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, 1463fec6d055SJosef "Jeff" Sipek struct inode *inode, struct treepath *path) 14641da177e4SLinus Torvalds { 14651da177e4SLinus Torvalds struct cpu_key tail_key; 14661da177e4SLinus Torvalds int tail_len; 14671da177e4SLinus Torvalds int removed; 14681da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 14691da177e4SLinus Torvalds 14701da177e4SLinus Torvalds make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); // !!!! 14711da177e4SLinus Torvalds tail_key.key_length = 4; 14721da177e4SLinus Torvalds 1473bd4c625cSLinus Torvalds tail_len = 1474bd4c625cSLinus Torvalds (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1; 14751da177e4SLinus Torvalds while (tail_len) { 14761da177e4SLinus Torvalds /* look for the last byte of the tail */ 1477bd4c625cSLinus Torvalds if (search_for_position_by_key(inode->i_sb, &tail_key, path) == 1478bd4c625cSLinus Torvalds POSITION_NOT_FOUND) 1479c3a9c210SJeff Mahoney reiserfs_panic(inode->i_sb, "vs-5615", 1480c3a9c210SJeff Mahoney "found invalid item"); 1481bd4c625cSLinus Torvalds RFALSE(path->pos_in_item != 1482bd4c625cSLinus Torvalds ih_item_len(PATH_PITEM_HEAD(path)) - 1, 14831da177e4SLinus Torvalds "vs-5616: appended bytes found"); 14841da177e4SLinus Torvalds PATH_LAST_POSITION(path)--; 14851da177e4SLinus Torvalds 1486bd4c625cSLinus Torvalds removed = 1487bd4c625cSLinus Torvalds reiserfs_delete_item(th, path, &tail_key, inode, 1488bd4c625cSLinus Torvalds NULL /*unbh not needed */ ); 1489bd4c625cSLinus Torvalds RFALSE(removed <= 0 1490bd4c625cSLinus Torvalds || removed > tail_len, 14911da177e4SLinus Torvalds "vs-5617: there was tail %d bytes, removed item length %d bytes", 14921da177e4SLinus Torvalds tail_len, removed); 14931da177e4SLinus Torvalds tail_len -= removed; 1494bd4c625cSLinus Torvalds set_cpu_key_k_offset(&tail_key, 1495bd4c625cSLinus Torvalds cpu_key_k_offset(&tail_key) - removed); 14961da177e4SLinus Torvalds } 149745b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct " 149845b03d5eSJeff Mahoney "conversion has been rolled back due to " 149945b03d5eSJeff Mahoney "lack of disk space"); 15001da177e4SLinus Torvalds //mark_file_without_tail (inode); 15011da177e4SLinus Torvalds mark_inode_dirty(inode); 15021da177e4SLinus Torvalds } 15031da177e4SLinus Torvalds 15041da177e4SLinus Torvalds /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ 15051da177e4SLinus Torvalds int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, 1506fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 15071da177e4SLinus Torvalds struct cpu_key *p_s_item_key, 15081da177e4SLinus Torvalds struct inode *p_s_inode, 1509bd4c625cSLinus Torvalds struct page *page, loff_t n_new_file_size) 15101da177e4SLinus Torvalds { 1511a9dd3643SJeff Mahoney struct super_block *sb = p_s_inode->i_sb; 15121da177e4SLinus Torvalds /* Every function which is going to call do_balance must first 15131da177e4SLinus Torvalds create a tree_balance structure. Then it must fill up this 15141da177e4SLinus Torvalds structure by using the init_tb_struct and fix_nodes functions. 15151da177e4SLinus Torvalds After that we can make tree balancing. */ 15161da177e4SLinus Torvalds struct tree_balance s_cut_balance; 15171da177e4SLinus Torvalds struct item_head *p_le_ih; 15181da177e4SLinus Torvalds int n_cut_size = 0, /* Amount to be cut. */ 1519bd4c625cSLinus Torvalds n_ret_value = CARRY_ON, n_removed = 0, /* Number of the removed unformatted nodes. */ 15201da177e4SLinus Torvalds n_is_inode_locked = 0; 15211da177e4SLinus Torvalds char c_mode; /* Mode of the balance. */ 15221da177e4SLinus Torvalds int retval2 = -1; 15231da177e4SLinus Torvalds int quota_cut_bytes; 15241da177e4SLinus Torvalds loff_t tail_pos = 0; 15251da177e4SLinus Torvalds 15261da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15271da177e4SLinus Torvalds 1528bd4c625cSLinus Torvalds init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, 1529bd4c625cSLinus Torvalds n_cut_size); 15301da177e4SLinus Torvalds 15311da177e4SLinus Torvalds /* Repeat this loop until we either cut the item without needing 15321da177e4SLinus Torvalds to balance, or we fix_nodes without schedule occurring */ 15331da177e4SLinus Torvalds while (1) { 15341da177e4SLinus Torvalds /* Determine the balance mode, position of the first byte to 15351da177e4SLinus Torvalds be cut, and size to be cut. In case of the indirect item 15361da177e4SLinus Torvalds free unformatted nodes which are pointed to by the cut 15371da177e4SLinus Torvalds pointers. */ 15381da177e4SLinus Torvalds 1539bd4c625cSLinus Torvalds c_mode = 1540bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1541bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 15421da177e4SLinus Torvalds &n_cut_size, n_new_file_size); 15431da177e4SLinus Torvalds if (c_mode == M_CONVERT) { 15441da177e4SLinus Torvalds /* convert last unformatted node to direct item or leave 15451da177e4SLinus Torvalds tail in the unformatted node */ 1546bd4c625cSLinus Torvalds RFALSE(n_ret_value != CARRY_ON, 1547bd4c625cSLinus Torvalds "PAP-5570: can not convert twice"); 15481da177e4SLinus Torvalds 1549bd4c625cSLinus Torvalds n_ret_value = 1550bd4c625cSLinus Torvalds maybe_indirect_to_direct(th, p_s_inode, page, 1551bd4c625cSLinus Torvalds p_s_path, p_s_item_key, 15521da177e4SLinus Torvalds n_new_file_size, &c_mode); 15531da177e4SLinus Torvalds if (c_mode == M_SKIP_BALANCING) 15541da177e4SLinus Torvalds /* tail has been left in the unformatted node */ 15551da177e4SLinus Torvalds return n_ret_value; 15561da177e4SLinus Torvalds 15571da177e4SLinus Torvalds n_is_inode_locked = 1; 15581da177e4SLinus Torvalds 15591da177e4SLinus Torvalds /* removing of last unformatted node will change value we 15601da177e4SLinus Torvalds have to return to truncate. Save it */ 15611da177e4SLinus Torvalds retval2 = n_ret_value; 1562a9dd3643SJeff Mahoney /*retval2 = sb->s_blocksize - (n_new_file_size & (sb->s_blocksize - 1)); */ 15631da177e4SLinus Torvalds 15641da177e4SLinus Torvalds /* So, we have performed the first part of the conversion: 15651da177e4SLinus Torvalds inserting the new direct item. Now we are removing the 15661da177e4SLinus Torvalds last unformatted node pointer. Set key to search for 15671da177e4SLinus Torvalds it. */ 15681da177e4SLinus Torvalds set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT); 15691da177e4SLinus Torvalds p_s_item_key->key_length = 4; 1570bd4c625cSLinus Torvalds n_new_file_size -= 1571a9dd3643SJeff Mahoney (n_new_file_size & (sb->s_blocksize - 1)); 15721da177e4SLinus Torvalds tail_pos = n_new_file_size; 15731da177e4SLinus Torvalds set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1); 1574bd4c625cSLinus Torvalds if (search_for_position_by_key 1575a9dd3643SJeff Mahoney (sb, p_s_item_key, 1576bd4c625cSLinus Torvalds p_s_path) == POSITION_NOT_FOUND) { 1577bd4c625cSLinus Torvalds print_block(PATH_PLAST_BUFFER(p_s_path), 3, 1578bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) - 1, 1579bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) + 1); 1580a9dd3643SJeff Mahoney reiserfs_panic(sb, "PAP-5580", "item to " 1581c3a9c210SJeff Mahoney "convert does not exist (%K)", 1582bd4c625cSLinus Torvalds p_s_item_key); 15831da177e4SLinus Torvalds } 15841da177e4SLinus Torvalds continue; 15851da177e4SLinus Torvalds } 15861da177e4SLinus Torvalds if (n_cut_size == 0) { 15871da177e4SLinus Torvalds pathrelse(p_s_path); 15881da177e4SLinus Torvalds return 0; 15891da177e4SLinus Torvalds } 15901da177e4SLinus Torvalds 15911da177e4SLinus Torvalds s_cut_balance.insert_size[0] = n_cut_size; 15921da177e4SLinus Torvalds 15931da177e4SLinus Torvalds n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL); 15941da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 15951da177e4SLinus Torvalds break; 15961da177e4SLinus Torvalds 1597a9dd3643SJeff Mahoney PROC_INFO_INC(sb, cut_from_item_restarted); 15981da177e4SLinus Torvalds 1599bd4c625cSLinus Torvalds n_ret_value = 1600a9dd3643SJeff Mahoney search_for_position_by_key(sb, p_s_item_key, p_s_path); 16011da177e4SLinus Torvalds if (n_ret_value == POSITION_FOUND) 16021da177e4SLinus Torvalds continue; 16031da177e4SLinus Torvalds 1604a9dd3643SJeff Mahoney reiserfs_warning(sb, "PAP-5610", "item %K not found", 1605bd4c625cSLinus Torvalds p_s_item_key); 16061da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16071da177e4SLinus Torvalds return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT; 16081da177e4SLinus Torvalds } /* while */ 16091da177e4SLinus Torvalds 16101da177e4SLinus Torvalds // check fix_nodes results (IO_ERROR or NO_DISK_SPACE) 16111da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 16121da177e4SLinus Torvalds if (n_is_inode_locked) { 16131da177e4SLinus Torvalds // FIXME: this seems to be not needed: we are always able 16141da177e4SLinus Torvalds // to cut item 16151da177e4SLinus Torvalds indirect_to_direct_roll_back(th, p_s_inode, p_s_path); 16161da177e4SLinus Torvalds } 16171da177e4SLinus Torvalds if (n_ret_value == NO_DISK_SPACE) 1618a9dd3643SJeff Mahoney reiserfs_warning(sb, "reiserfs-5092", 161945b03d5eSJeff Mahoney "NO_DISK_SPACE"); 16201da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16211da177e4SLinus Torvalds return -EIO; 16221da177e4SLinus Torvalds } 16231da177e4SLinus Torvalds 16241da177e4SLinus Torvalds /* go ahead and perform balancing */ 16251da177e4SLinus Torvalds 16261da177e4SLinus Torvalds RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode"); 16271da177e4SLinus Torvalds 16281da177e4SLinus Torvalds /* Calculate number of bytes that need to be cut from the item. */ 1629bd4c625cSLinus Torvalds quota_cut_bytes = 1630bd4c625cSLinus Torvalds (c_mode == 1631bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance. 1632bd4c625cSLinus Torvalds insert_size[0]; 16331da177e4SLinus Torvalds if (retval2 == -1) 16341da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode); 16351da177e4SLinus Torvalds else 16361da177e4SLinus Torvalds n_ret_value = retval2; 16371da177e4SLinus Torvalds 16381da177e4SLinus Torvalds /* For direct items, we only change the quota when deleting the last 16391da177e4SLinus Torvalds ** item. 16401da177e4SLinus Torvalds */ 16411da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path); 16421da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) { 16431da177e4SLinus Torvalds if (c_mode == M_DELETE && 1644a9dd3643SJeff Mahoney (le_ih_k_offset(p_le_ih) & (sb->s_blocksize - 1)) == 1645bd4c625cSLinus Torvalds 1) { 16461da177e4SLinus Torvalds // FIXME: this is to keep 3.5 happy 16471da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX; 1648a9dd3643SJeff Mahoney quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 16491da177e4SLinus Torvalds } else { 16501da177e4SLinus Torvalds quota_cut_bytes = 0; 16511da177e4SLinus Torvalds } 16521da177e4SLinus Torvalds } 16531da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 16541da177e4SLinus Torvalds if (n_is_inode_locked) { 1655bd4c625cSLinus Torvalds struct item_head *le_ih = 1656bd4c625cSLinus Torvalds PATH_PITEM_HEAD(s_cut_balance.tb_path); 16571da177e4SLinus Torvalds /* we are going to complete indirect2direct conversion. Make 16581da177e4SLinus Torvalds sure, that we exactly remove last unformatted node pointer 16591da177e4SLinus Torvalds of the item */ 16601da177e4SLinus Torvalds if (!is_indirect_le_ih(le_ih)) 1661a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5652", 16621da177e4SLinus Torvalds "item must be indirect %h", le_ih); 16631da177e4SLinus Torvalds 16641da177e4SLinus Torvalds if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE) 1665a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5653", "completing " 1666c3a9c210SJeff Mahoney "indirect2direct conversion indirect " 1667c3a9c210SJeff Mahoney "item %h being deleted must be of " 1668c3a9c210SJeff Mahoney "4 byte long", le_ih); 16691da177e4SLinus Torvalds 1670bd4c625cSLinus Torvalds if (c_mode == M_CUT 1671bd4c625cSLinus Torvalds && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) { 1672a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5654", "can not complete " 1673c3a9c210SJeff Mahoney "indirect2direct conversion of %h " 1674c3a9c210SJeff Mahoney "(CUT, insert_size==%d)", 16751da177e4SLinus Torvalds le_ih, s_cut_balance.insert_size[0]); 16761da177e4SLinus Torvalds } 16771da177e4SLinus Torvalds /* it would be useful to make sure, that right neighboring 16781da177e4SLinus Torvalds item is direct item of this file */ 16791da177e4SLinus Torvalds } 16801da177e4SLinus Torvalds #endif 16811da177e4SLinus Torvalds 16821da177e4SLinus Torvalds do_balance(&s_cut_balance, NULL, NULL, c_mode); 16831da177e4SLinus Torvalds if (n_is_inode_locked) { 16841da177e4SLinus Torvalds /* we've done an indirect->direct conversion. when the data block 16851da177e4SLinus Torvalds ** was freed, it was removed from the list of blocks that must 16861da177e4SLinus Torvalds ** be flushed before the transaction commits, make sure to 16871da177e4SLinus Torvalds ** unmap and invalidate it 16881da177e4SLinus Torvalds */ 16891da177e4SLinus Torvalds unmap_buffers(page, tail_pos); 16901da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask; 16911da177e4SLinus Torvalds } 16921da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1693bd4c625cSLinus Torvalds reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE, 1694bd4c625cSLinus Torvalds "reiserquota cut_from_item(): freeing %u id=%u type=%c", 1695bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, '?'); 16961da177e4SLinus Torvalds #endif 16971da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 16981da177e4SLinus Torvalds return n_ret_value; 16991da177e4SLinus Torvalds } 17001da177e4SLinus Torvalds 1701bd4c625cSLinus Torvalds static void truncate_directory(struct reiserfs_transaction_handle *th, 1702bd4c625cSLinus Torvalds struct inode *inode) 17031da177e4SLinus Torvalds { 17041da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 17051da177e4SLinus Torvalds if (inode->i_nlink) 17060030b645SJeff Mahoney reiserfs_error(inode->i_sb, "vs-5655", "link count != 0"); 17071da177e4SLinus Torvalds 17081da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET); 17091da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY); 17101da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 17111da177e4SLinus Torvalds reiserfs_update_sd(th, inode); 17121da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET); 17131da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA); 17141da177e4SLinus Torvalds } 17151da177e4SLinus Torvalds 17161da177e4SLinus Torvalds /* Truncate file to the new size. Note, this must be called with a transaction 17171da177e4SLinus Torvalds already started */ 1718bd4c625cSLinus Torvalds int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode, /* ->i_size contains new 17191da177e4SLinus Torvalds size */ 17201da177e4SLinus Torvalds struct page *page, /* up to date for last block */ 17211da177e4SLinus Torvalds int update_timestamps /* when it is called by 17221da177e4SLinus Torvalds file_release to convert 17231da177e4SLinus Torvalds the tail - no timestamps 17241da177e4SLinus Torvalds should be updated */ 1725bd4c625cSLinus Torvalds ) 1726bd4c625cSLinus Torvalds { 17271da177e4SLinus Torvalds INITIALIZE_PATH(s_search_path); /* Path to the current object item. */ 17281da177e4SLinus Torvalds struct item_head *p_le_ih; /* Pointer to an item header. */ 17291da177e4SLinus Torvalds struct cpu_key s_item_key; /* Key to search for a previous file item. */ 17301da177e4SLinus Torvalds loff_t n_file_size, /* Old file size. */ 17311da177e4SLinus Torvalds n_new_file_size; /* New file size. */ 17321da177e4SLinus Torvalds int n_deleted; /* Number of deleted or truncated bytes. */ 17331da177e4SLinus Torvalds int retval; 17341da177e4SLinus Torvalds int err = 0; 17351da177e4SLinus Torvalds 17361da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 1737bd4c625cSLinus Torvalds if (! 1738bd4c625cSLinus Torvalds (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) 1739bd4c625cSLinus Torvalds || S_ISLNK(p_s_inode->i_mode))) 17401da177e4SLinus Torvalds return 0; 17411da177e4SLinus Torvalds 17421da177e4SLinus Torvalds if (S_ISDIR(p_s_inode->i_mode)) { 17431da177e4SLinus Torvalds // deletion of directory - no need to update timestamps 17441da177e4SLinus Torvalds truncate_directory(th, p_s_inode); 17451da177e4SLinus Torvalds return 0; 17461da177e4SLinus Torvalds } 17471da177e4SLinus Torvalds 17481da177e4SLinus Torvalds /* Get new file size. */ 17491da177e4SLinus Torvalds n_new_file_size = p_s_inode->i_size; 17501da177e4SLinus Torvalds 17511da177e4SLinus Torvalds // FIXME: note, that key type is unimportant here 1752bd4c625cSLinus Torvalds make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode), 1753bd4c625cSLinus Torvalds TYPE_DIRECT, 3); 17541da177e4SLinus Torvalds 1755bd4c625cSLinus Torvalds retval = 1756bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1757bd4c625cSLinus Torvalds &s_search_path); 17581da177e4SLinus Torvalds if (retval == IO_ERROR) { 17590030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "vs-5657", 1760bd4c625cSLinus Torvalds "i/o failure occurred trying to truncate %K", 1761bd4c625cSLinus Torvalds &s_item_key); 17621da177e4SLinus Torvalds err = -EIO; 17631da177e4SLinus Torvalds goto out; 17641da177e4SLinus Torvalds } 17651da177e4SLinus Torvalds if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) { 17660030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "PAP-5660", 1767bd4c625cSLinus Torvalds "wrong result %d of search for %K", retval, 1768bd4c625cSLinus Torvalds &s_item_key); 17691da177e4SLinus Torvalds 17701da177e4SLinus Torvalds err = -EIO; 17711da177e4SLinus Torvalds goto out; 17721da177e4SLinus Torvalds } 17731da177e4SLinus Torvalds 17741da177e4SLinus Torvalds s_search_path.pos_in_item--; 17751da177e4SLinus Torvalds 17761da177e4SLinus Torvalds /* Get real file size (total length of all file items) */ 17771da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(&s_search_path); 17781da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 17791da177e4SLinus Torvalds n_file_size = 0; 17801da177e4SLinus Torvalds else { 17811da177e4SLinus Torvalds loff_t offset = le_ih_k_offset(p_le_ih); 1782bd4c625cSLinus Torvalds int bytes = 1783bd4c625cSLinus Torvalds op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize); 17841da177e4SLinus Torvalds 17851da177e4SLinus Torvalds /* this may mismatch with real file size: if last direct item 17861da177e4SLinus Torvalds had no padding zeros and last unformatted node had no free 17871da177e4SLinus Torvalds space, this file would have this file size */ 17881da177e4SLinus Torvalds n_file_size = offset + bytes - 1; 17891da177e4SLinus Torvalds } 17901da177e4SLinus Torvalds /* 17911da177e4SLinus Torvalds * are we doing a full truncate or delete, if so 17921da177e4SLinus Torvalds * kick in the reada code 17931da177e4SLinus Torvalds */ 17941da177e4SLinus Torvalds if (n_new_file_size == 0) 17951da177e4SLinus Torvalds s_search_path.reada = PATH_READA | PATH_READA_BACK; 17961da177e4SLinus Torvalds 17971da177e4SLinus Torvalds if (n_file_size == 0 || n_file_size < n_new_file_size) { 17981da177e4SLinus Torvalds goto update_and_out; 17991da177e4SLinus Torvalds } 18001da177e4SLinus Torvalds 18011da177e4SLinus Torvalds /* Update key to search for the last file item. */ 18021da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18031da177e4SLinus Torvalds 18041da177e4SLinus Torvalds do { 18051da177e4SLinus Torvalds /* Cut or delete file item. */ 1806bd4c625cSLinus Torvalds n_deleted = 1807bd4c625cSLinus Torvalds reiserfs_cut_from_item(th, &s_search_path, &s_item_key, 1808bd4c625cSLinus Torvalds p_s_inode, page, n_new_file_size); 18091da177e4SLinus Torvalds if (n_deleted < 0) { 181045b03d5eSJeff Mahoney reiserfs_warning(p_s_inode->i_sb, "vs-5665", 181145b03d5eSJeff Mahoney "reiserfs_cut_from_item failed"); 18121da177e4SLinus Torvalds reiserfs_check_path(&s_search_path); 18131da177e4SLinus Torvalds return 0; 18141da177e4SLinus Torvalds } 18151da177e4SLinus Torvalds 18161da177e4SLinus Torvalds RFALSE(n_deleted > n_file_size, 18171da177e4SLinus Torvalds "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K", 18181da177e4SLinus Torvalds n_deleted, n_file_size, &s_item_key); 18191da177e4SLinus Torvalds 18201da177e4SLinus Torvalds /* Change key to search the last file item. */ 18211da177e4SLinus Torvalds n_file_size -= n_deleted; 18221da177e4SLinus Torvalds 18231da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18241da177e4SLinus Torvalds 18251da177e4SLinus Torvalds /* While there are bytes to truncate and previous file item is presented in the tree. */ 18261da177e4SLinus Torvalds 18271da177e4SLinus Torvalds /* 18281da177e4SLinus Torvalds ** This loop could take a really long time, and could log 18291da177e4SLinus Torvalds ** many more blocks than a transaction can hold. So, we do a polite 18301da177e4SLinus Torvalds ** journal end here, and if the transaction needs ending, we make 18311da177e4SLinus Torvalds ** sure the file is consistent before ending the current trans 18321da177e4SLinus Torvalds ** and starting a new one 18331da177e4SLinus Torvalds */ 183423f9e0f8SAlexander Zarochentzev if (journal_transaction_should_end(th, 0) || 183523f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 18361da177e4SLinus Torvalds int orig_len_alloc = th->t_blocks_allocated; 18373cd6dbe6SJeff Mahoney pathrelse(&s_search_path); 18381da177e4SLinus Torvalds 18391da177e4SLinus Torvalds if (update_timestamps) { 1840bd4c625cSLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = 1841bd4c625cSLinus Torvalds CURRENT_TIME_SEC; 18421da177e4SLinus Torvalds } 18431da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 18441da177e4SLinus Torvalds 18451da177e4SLinus Torvalds err = journal_end(th, p_s_inode->i_sb, orig_len_alloc); 18461da177e4SLinus Torvalds if (err) 18471da177e4SLinus Torvalds goto out; 18481da177e4SLinus Torvalds err = journal_begin(th, p_s_inode->i_sb, 184923f9e0f8SAlexander Zarochentzev JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ; 18501da177e4SLinus Torvalds if (err) 18511da177e4SLinus Torvalds goto out; 18521da177e4SLinus Torvalds reiserfs_update_inode_transaction(p_s_inode); 18531da177e4SLinus Torvalds } 18541da177e4SLinus Torvalds } while (n_file_size > ROUND_UP(n_new_file_size) && 1855bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1856bd4c625cSLinus Torvalds &s_search_path) == POSITION_FOUND); 18571da177e4SLinus Torvalds 18581da177e4SLinus Torvalds RFALSE(n_file_size > ROUND_UP(n_new_file_size), 18591da177e4SLinus Torvalds "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d", 18601da177e4SLinus Torvalds n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid); 18611da177e4SLinus Torvalds 18621da177e4SLinus Torvalds update_and_out: 18631da177e4SLinus Torvalds if (update_timestamps) { 18641da177e4SLinus Torvalds // this is truncate, not file closing 18651da177e4SLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC; 18661da177e4SLinus Torvalds } 18671da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 18681da177e4SLinus Torvalds 18691da177e4SLinus Torvalds out: 18701da177e4SLinus Torvalds pathrelse(&s_search_path); 18711da177e4SLinus Torvalds return err; 18721da177e4SLinus Torvalds } 18731da177e4SLinus Torvalds 18741da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 18751da177e4SLinus Torvalds // this makes sure, that we __append__, not overwrite or add holes 1876fec6d055SJosef "Jeff" Sipek static void check_research_for_paste(struct treepath *path, 18771da177e4SLinus Torvalds const struct cpu_key *p_s_key) 18781da177e4SLinus Torvalds { 18791da177e4SLinus Torvalds struct item_head *found_ih = get_ih(path); 18801da177e4SLinus Torvalds 18811da177e4SLinus Torvalds if (is_direct_le_ih(found_ih)) { 1882bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1883bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1884bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1885bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1886bd4c625cSLinus Torvalds || op_bytes_number(found_ih, 1887bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1888bd4c625cSLinus Torvalds pos_in_item(path)) 1889c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5720", "found direct item " 1890c3a9c210SJeff Mahoney "%h or position (%d) does not match " 1891c3a9c210SJeff Mahoney "to key %K", found_ih, 1892c3a9c210SJeff Mahoney pos_in_item(path), p_s_key); 18931da177e4SLinus Torvalds } 18941da177e4SLinus Torvalds if (is_indirect_le_ih(found_ih)) { 1895bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1896bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1897bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1898bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1899bd4c625cSLinus Torvalds || I_UNFM_NUM(found_ih) != pos_in_item(path) 1900bd4c625cSLinus Torvalds || get_ih_free_space(found_ih) != 0) 1901c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5730", "found indirect " 1902c3a9c210SJeff Mahoney "item (%h) or position (%d) does not " 1903c3a9c210SJeff Mahoney "match to key (%K)", 19041da177e4SLinus Torvalds found_ih, pos_in_item(path), p_s_key); 19051da177e4SLinus Torvalds } 19061da177e4SLinus Torvalds } 19071da177e4SLinus Torvalds #endif /* config reiserfs check */ 19081da177e4SLinus Torvalds 19091da177e4SLinus Torvalds /* Paste bytes to the existing item. Returns bytes number pasted into the item. */ 1910fec6d055SJosef "Jeff" Sipek int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_search_path, /* Path to the pasted item. */ 19111da177e4SLinus Torvalds const struct cpu_key *p_s_key, /* Key to search for the needed item. */ 19121da177e4SLinus Torvalds struct inode *inode, /* Inode item belongs to */ 19131da177e4SLinus Torvalds const char *p_c_body, /* Pointer to the bytes to paste. */ 1914bd4c625cSLinus Torvalds int n_pasted_size) 1915bd4c625cSLinus Torvalds { /* Size of pasted bytes. */ 19161da177e4SLinus Torvalds struct tree_balance s_paste_balance; 19171da177e4SLinus Torvalds int retval; 19181da177e4SLinus Torvalds int fs_gen; 19191da177e4SLinus Torvalds 19201da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 19211da177e4SLinus Torvalds 19221da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 19231da177e4SLinus Torvalds 19241da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1925bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1926bd4c625cSLinus Torvalds "reiserquota paste_into_item(): allocating %u id=%u type=%c", 1927bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 1928bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 19291da177e4SLinus Torvalds #endif 19301da177e4SLinus Torvalds 19311da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) { 19321da177e4SLinus Torvalds pathrelse(p_s_search_path); 19331da177e4SLinus Torvalds return -EDQUOT; 19341da177e4SLinus Torvalds } 1935bd4c625cSLinus Torvalds init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, 1936bd4c625cSLinus Torvalds n_pasted_size); 19371da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 19381da177e4SLinus Torvalds s_paste_balance.key = p_s_key->on_disk_key; 19391da177e4SLinus Torvalds #endif 19401da177e4SLinus Torvalds 19411da177e4SLinus Torvalds /* DQUOT_* can schedule, must check before the fix_nodes */ 19421da177e4SLinus Torvalds if (fs_changed(fs_gen, inode->i_sb)) { 19431da177e4SLinus Torvalds goto search_again; 19441da177e4SLinus Torvalds } 19451da177e4SLinus Torvalds 1946bd4c625cSLinus Torvalds while ((retval = 1947bd4c625cSLinus Torvalds fix_nodes(M_PASTE, &s_paste_balance, NULL, 1948bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 19491da177e4SLinus Torvalds search_again: 19501da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 19511da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, paste_into_item_restarted); 1952bd4c625cSLinus Torvalds retval = 1953bd4c625cSLinus Torvalds search_for_position_by_key(th->t_super, p_s_key, 1954bd4c625cSLinus Torvalds p_s_search_path); 19551da177e4SLinus Torvalds if (retval == IO_ERROR) { 19561da177e4SLinus Torvalds retval = -EIO; 19571da177e4SLinus Torvalds goto error_out; 19581da177e4SLinus Torvalds } 19591da177e4SLinus Torvalds if (retval == POSITION_FOUND) { 196045b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "PAP-5710", 196145b03d5eSJeff Mahoney "entry or pasted byte (%K) exists", 1962bd4c625cSLinus Torvalds p_s_key); 19631da177e4SLinus Torvalds retval = -EEXIST; 19641da177e4SLinus Torvalds goto error_out; 19651da177e4SLinus Torvalds } 19661da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 19671da177e4SLinus Torvalds check_research_for_paste(p_s_search_path, p_s_key); 19681da177e4SLinus Torvalds #endif 19691da177e4SLinus Torvalds } 19701da177e4SLinus Torvalds 19711da177e4SLinus Torvalds /* Perform balancing after all resources are collected by fix_nodes, and 19721da177e4SLinus Torvalds accessing them will not risk triggering schedule. */ 19731da177e4SLinus Torvalds if (retval == CARRY_ON) { 19741da177e4SLinus Torvalds do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE); 19751da177e4SLinus Torvalds return 0; 19761da177e4SLinus Torvalds } 19771da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 19781da177e4SLinus Torvalds error_out: 19791da177e4SLinus Torvalds /* this also releases the path */ 19801da177e4SLinus Torvalds unfix_nodes(&s_paste_balance); 19811da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1982bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1983bd4c625cSLinus Torvalds "reiserquota paste_into_item(): freeing %u id=%u type=%c", 1984bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 1985bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 19861da177e4SLinus Torvalds #endif 19871da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size); 19881da177e4SLinus Torvalds return retval; 19891da177e4SLinus Torvalds } 19901da177e4SLinus Torvalds 19911da177e4SLinus Torvalds /* Insert new item into the buffer at the path. */ 1992fec6d055SJosef "Jeff" Sipek int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the inserteded item. */ 1993bd4c625cSLinus Torvalds const struct cpu_key *key, struct item_head *p_s_ih, /* Pointer to the item header to insert. */ 1994bd4c625cSLinus Torvalds struct inode *inode, const char *p_c_body) 1995bd4c625cSLinus Torvalds { /* Pointer to the bytes to insert. */ 19961da177e4SLinus Torvalds struct tree_balance s_ins_balance; 19971da177e4SLinus Torvalds int retval; 19981da177e4SLinus Torvalds int fs_gen = 0; 19991da177e4SLinus Torvalds int quota_bytes = 0; 20001da177e4SLinus Torvalds 20011da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 20021da177e4SLinus Torvalds 20031da177e4SLinus Torvalds if (inode) { /* Do we count quotas for item? */ 20041da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 20051da177e4SLinus Torvalds quota_bytes = ih_item_len(p_s_ih); 20061da177e4SLinus Torvalds 20071da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file has 20081da177e4SLinus Torvalds ** a tail, links are always tails, so there's no guessing needed 20091da177e4SLinus Torvalds */ 20101da177e4SLinus Torvalds if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) { 20111da177e4SLinus Torvalds quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE; 20121da177e4SLinus Torvalds } 20131da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2014bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2015bd4c625cSLinus Torvalds "reiserquota insert_item(): allocating %u id=%u type=%c", 2016bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 20171da177e4SLinus Torvalds #endif 20181da177e4SLinus Torvalds /* We can't dirty inode here. It would be immediately written but 20191da177e4SLinus Torvalds * appropriate stat item isn't inserted yet... */ 20201da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) { 20211da177e4SLinus Torvalds pathrelse(p_s_path); 20221da177e4SLinus Torvalds return -EDQUOT; 20231da177e4SLinus Torvalds } 20241da177e4SLinus Torvalds } 2025bd4c625cSLinus Torvalds init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, 2026bd4c625cSLinus Torvalds IH_SIZE + ih_item_len(p_s_ih)); 20271da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 20281da177e4SLinus Torvalds s_ins_balance.key = key->on_disk_key; 20291da177e4SLinus Torvalds #endif 20301da177e4SLinus Torvalds /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */ 20311da177e4SLinus Torvalds if (inode && fs_changed(fs_gen, inode->i_sb)) { 20321da177e4SLinus Torvalds goto search_again; 20331da177e4SLinus Torvalds } 20341da177e4SLinus Torvalds 2035bd4c625cSLinus Torvalds while ((retval = 2036bd4c625cSLinus Torvalds fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, 2037bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 20381da177e4SLinus Torvalds search_again: 20391da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 20401da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, insert_item_restarted); 20411da177e4SLinus Torvalds retval = search_item(th->t_super, key, p_s_path); 20421da177e4SLinus Torvalds if (retval == IO_ERROR) { 20431da177e4SLinus Torvalds retval = -EIO; 20441da177e4SLinus Torvalds goto error_out; 20451da177e4SLinus Torvalds } 20461da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 204745b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "PAP-5760", 2048bd4c625cSLinus Torvalds "key %K already exists in the tree", 2049bd4c625cSLinus Torvalds key); 20501da177e4SLinus Torvalds retval = -EEXIST; 20511da177e4SLinus Torvalds goto error_out; 20521da177e4SLinus Torvalds } 20531da177e4SLinus Torvalds } 20541da177e4SLinus Torvalds 20551da177e4SLinus Torvalds /* make balancing after all resources will be collected at a time */ 20561da177e4SLinus Torvalds if (retval == CARRY_ON) { 20571da177e4SLinus Torvalds do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT); 20581da177e4SLinus Torvalds return 0; 20591da177e4SLinus Torvalds } 20601da177e4SLinus Torvalds 20611da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 20621da177e4SLinus Torvalds error_out: 20631da177e4SLinus Torvalds /* also releases the path */ 20641da177e4SLinus Torvalds unfix_nodes(&s_ins_balance); 20651da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2066bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 2067bd4c625cSLinus Torvalds "reiserquota insert_item(): freeing %u id=%u type=%c", 2068bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 20691da177e4SLinus Torvalds #endif 20701da177e4SLinus Torvalds if (inode) 20711da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes); 20721da177e4SLinus Torvalds return retval; 20731da177e4SLinus Torvalds } 2074