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. */ 591da177e4SLinus Torvalds inline int B_IS_IN_TREE(const struct buffer_head *p_s_bh) 601da177e4SLinus Torvalds { 611da177e4SLinus Torvalds 621da177e4SLinus Torvalds RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT, 631da177e4SLinus Torvalds "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh); 641da177e4SLinus Torvalds 651da177e4SLinus Torvalds return (B_LEVEL(p_s_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 248bd4c625cSLinus Torvalds *p_s_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)-> 285bd4c625cSLinus Torvalds b_blocknr == SB_ROOT_BLOCK(p_s_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, 292bd4c625cSLinus Torvalds const struct super_block *p_s_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)-> 328bd4c625cSLinus Torvalds b_blocknr == SB_ROOT_BLOCK(p_s_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. */ 3401da177e4SLinus Torvalds struct super_block *p_s_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 3511da177e4SLinus Torvalds if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1) 3521da177e4SLinus Torvalds /* left delimiting key is bigger, that the key we look for */ 3531da177e4SLinus Torvalds return 0; 3541da177e4SLinus Torvalds // if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 ) 3551da177e4SLinus Torvalds if (comp_keys(get_rkey(p_s_chk_path, p_s_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 368*3cd6dbe6SJeff Mahoney /* Drop the reference to each buffer in a path and restore 369*3cd6dbe6SJeff Mahoney * dirty bits clean when preparing the buffer for the log. 370*3cd6dbe6SJeff Mahoney * This version should only be called from fix_nodes() */ 371*3cd6dbe6SJeff Mahoney void pathrelse_and_restore(struct super_block *sb, 372*3cd6dbe6SJeff 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) { 380*3cd6dbe6SJeff Mahoney struct buffer_head *bh; 381*3cd6dbe6SJeff Mahoney bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--); 382*3cd6dbe6SJeff Mahoney reiserfs_restore_prepared_buffer(sb, bh); 383*3cd6dbe6SJeff Mahoney brelse(bh); 3841da177e4SLinus Torvalds } 3851da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 3861da177e4SLinus Torvalds } 3871da177e4SLinus Torvalds 388*3cd6dbe6SJeff 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 * 5491da177e4SLinus Torvalds * Input: p_s_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! */ 569bd4c625cSLinus Torvalds int search_by_key(struct super_block *p_s_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; 5821da177e4SLinus Torvalds struct buffer_head *p_s_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 5951da177e4SLinus Torvalds PROC_INFO_INC(p_s_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 601*3cd6dbe6SJeff 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.. */ 6081da177e4SLinus Torvalds n_block_number = SB_ROOT_BLOCK(p_s_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)) 61445b03d5eSJeff Mahoney reiserfs_warning(p_s_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); 6251da177e4SLinus Torvalds fs_gen = get_generation(p_s_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. */ 6291da177e4SLinus Torvalds if ((p_s_bh = p_s_last_element->pe_buffer = 6301da177e4SLinus Torvalds sb_getblk(p_s_sb, n_block_number))) { 6311da177e4SLinus Torvalds if (!buffer_uptodate(p_s_bh) && reada_count > 1) { 6321da177e4SLinus Torvalds search_by_key_reada(p_s_sb, reada_bh, 6331da177e4SLinus Torvalds reada_blocks, reada_count); 6341da177e4SLinus Torvalds } 6351da177e4SLinus Torvalds ll_rw_block(READ, 1, &p_s_bh); 6361da177e4SLinus Torvalds wait_on_buffer(p_s_bh); 6371da177e4SLinus Torvalds if (!buffer_uptodate(p_s_bh)) 6381da177e4SLinus Torvalds goto io_error; 6391da177e4SLinus Torvalds } else { 6401da177e4SLinus Torvalds io_error: 6411da177e4SLinus Torvalds p_s_search_path->path_length--; 6421da177e4SLinus Torvalds pathrelse(p_s_search_path); 6431da177e4SLinus Torvalds return IO_ERROR; 6441da177e4SLinus Torvalds } 6451da177e4SLinus Torvalds reada_count = 0; 6461da177e4SLinus Torvalds if (expected_level == -1) 6471da177e4SLinus Torvalds expected_level = SB_TREE_HEIGHT(p_s_sb); 6481da177e4SLinus Torvalds expected_level--; 6491da177e4SLinus Torvalds 6501da177e4SLinus Torvalds /* It is possible that schedule occurred. We must check whether the key 6511da177e4SLinus Torvalds to search is still in the tree rooted from the current buffer. If 6521da177e4SLinus Torvalds not then repeat search from the root. */ 6531da177e4SLinus Torvalds if (fs_changed(fs_gen, p_s_sb) && 6541da177e4SLinus Torvalds (!B_IS_IN_TREE(p_s_bh) || 6551da177e4SLinus Torvalds B_LEVEL(p_s_bh) != expected_level || 6561da177e4SLinus Torvalds !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) { 6571da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, search_by_key_fs_changed); 6581da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, search_by_key_restarted); 659bd4c625cSLinus Torvalds PROC_INFO_INC(p_s_sb, 660bd4c625cSLinus Torvalds sbk_restarted[expected_level - 1]); 661*3cd6dbe6SJeff Mahoney pathrelse(p_s_search_path); 6621da177e4SLinus Torvalds 6631da177e4SLinus Torvalds /* Get the root block number so that we can repeat the search 6641da177e4SLinus Torvalds starting from the root. */ 6651da177e4SLinus Torvalds n_block_number = SB_ROOT_BLOCK(p_s_sb); 6661da177e4SLinus Torvalds expected_level = -1; 6671da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6681da177e4SLinus Torvalds 6691da177e4SLinus Torvalds /* repeat search from the root */ 6701da177e4SLinus Torvalds continue; 6711da177e4SLinus Torvalds } 6721da177e4SLinus Torvalds 6731da177e4SLinus Torvalds /* only check that the key is in the buffer if p_s_key is not 6741da177e4SLinus Torvalds equal to the MAX_KEY. Latter case is only possible in 6751da177e4SLinus Torvalds "finish_unfinished()" processing during mount. */ 6761da177e4SLinus Torvalds RFALSE(comp_keys(&MAX_KEY, p_s_key) && 6771da177e4SLinus Torvalds !key_in_buffer(p_s_search_path, p_s_key, p_s_sb), 6781da177e4SLinus Torvalds "PAP-5130: key is not in the buffer"); 6791da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 6801da177e4SLinus Torvalds if (cur_tb) { 6811da177e4SLinus Torvalds print_cur_tb("5140"); 682c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "PAP-5140", 683c3a9c210SJeff Mahoney "schedule occurred in do_balance!"); 6841da177e4SLinus Torvalds } 6851da177e4SLinus Torvalds #endif 6861da177e4SLinus Torvalds 6871da177e4SLinus Torvalds // make sure, that the node contents look like a node of 6881da177e4SLinus Torvalds // certain level 6891da177e4SLinus Torvalds if (!is_tree_node(p_s_bh, expected_level)) { 6900030b645SJeff Mahoney reiserfs_error(p_s_sb, "vs-5150", 69145b03d5eSJeff Mahoney "invalid format found in block %ld. " 69245b03d5eSJeff Mahoney "Fsck?", p_s_bh->b_blocknr); 6931da177e4SLinus Torvalds pathrelse(p_s_search_path); 6941da177e4SLinus Torvalds return IO_ERROR; 6951da177e4SLinus Torvalds } 6961da177e4SLinus Torvalds 6971da177e4SLinus Torvalds /* ok, we have acquired next formatted node in the tree */ 6981da177e4SLinus Torvalds n_node_level = B_LEVEL(p_s_bh); 6991da177e4SLinus Torvalds 7001da177e4SLinus Torvalds PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1); 7011da177e4SLinus Torvalds 7021da177e4SLinus Torvalds RFALSE(n_node_level < n_stop_level, 7031da177e4SLinus Torvalds "vs-5152: tree level (%d) is less than stop level (%d)", 7041da177e4SLinus Torvalds n_node_level, n_stop_level); 7051da177e4SLinus Torvalds 7061da177e4SLinus Torvalds n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0), 7071da177e4SLinus Torvalds B_NR_ITEMS(p_s_bh), 708bd4c625cSLinus Torvalds (n_node_level == 709bd4c625cSLinus Torvalds DISK_LEAF_NODE_LEVEL) ? IH_SIZE : 710bd4c625cSLinus Torvalds KEY_SIZE, 7111da177e4SLinus Torvalds &(p_s_last_element->pe_position)); 7121da177e4SLinus Torvalds if (n_node_level == n_stop_level) { 7131da177e4SLinus Torvalds return n_retval; 7141da177e4SLinus Torvalds } 7151da177e4SLinus Torvalds 7161da177e4SLinus Torvalds /* we are not in the stop level */ 7171da177e4SLinus Torvalds if (n_retval == ITEM_FOUND) 7181da177e4SLinus Torvalds /* item has been found, so we choose the pointer which is to the right of the found one */ 7191da177e4SLinus Torvalds p_s_last_element->pe_position++; 7201da177e4SLinus Torvalds 7211da177e4SLinus Torvalds /* if item was not found we choose the position which is to 7221da177e4SLinus Torvalds the left of the found item. This requires no code, 7231da177e4SLinus Torvalds bin_search did it already. */ 7241da177e4SLinus Torvalds 7251da177e4SLinus Torvalds /* So we have chosen a position in the current node which is 7261da177e4SLinus Torvalds an internal node. Now we calculate child block number by 7271da177e4SLinus Torvalds position in the node. */ 728bd4c625cSLinus Torvalds n_block_number = 729bd4c625cSLinus Torvalds B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position); 7301da177e4SLinus Torvalds 7311da177e4SLinus Torvalds /* if we are going to read leaf nodes, try for read ahead as well */ 7321da177e4SLinus Torvalds if ((p_s_search_path->reada & PATH_READA) && 733bd4c625cSLinus Torvalds n_node_level == DISK_LEAF_NODE_LEVEL + 1) { 7341da177e4SLinus Torvalds int pos = p_s_last_element->pe_position; 7351da177e4SLinus Torvalds int limit = B_NR_ITEMS(p_s_bh); 7361da177e4SLinus Torvalds struct reiserfs_key *le_key; 7371da177e4SLinus Torvalds 7381da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7391da177e4SLinus Torvalds limit = 0; 7401da177e4SLinus Torvalds while (reada_count < SEARCH_BY_KEY_READA) { 7411da177e4SLinus Torvalds if (pos == limit) 7421da177e4SLinus Torvalds break; 743bd4c625cSLinus Torvalds reada_blocks[reada_count++] = 744bd4c625cSLinus Torvalds B_N_CHILD_NUM(p_s_bh, pos); 7451da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7461da177e4SLinus Torvalds pos--; 7471da177e4SLinus Torvalds else 7481da177e4SLinus Torvalds pos++; 7491da177e4SLinus Torvalds 7501da177e4SLinus Torvalds /* 7511da177e4SLinus Torvalds * check to make sure we're in the same object 7521da177e4SLinus Torvalds */ 7531da177e4SLinus Torvalds le_key = B_N_PDELIM_KEY(p_s_bh, pos); 7541da177e4SLinus Torvalds if (le32_to_cpu(le_key->k_objectid) != 755bd4c625cSLinus Torvalds p_s_key->on_disk_key.k_objectid) { 7561da177e4SLinus Torvalds break; 7571da177e4SLinus Torvalds } 7581da177e4SLinus Torvalds } 7591da177e4SLinus Torvalds } 7601da177e4SLinus Torvalds } 7611da177e4SLinus Torvalds } 7621da177e4SLinus Torvalds 7631da177e4SLinus Torvalds /* Form the path to an item and position in this item which contains 7641da177e4SLinus Torvalds file byte defined by p_s_key. If there is no such item 7651da177e4SLinus Torvalds corresponding to the key, we point the path to the item with 7661da177e4SLinus Torvalds maximal key less than p_s_key, and *p_n_pos_in_item is set to one 7671da177e4SLinus Torvalds past the last entry/byte in the item. If searching for entry in a 7681da177e4SLinus Torvalds directory item, and it is not found, *p_n_pos_in_item is set to one 7691da177e4SLinus Torvalds entry more than the entry with maximal key which is less than the 7701da177e4SLinus Torvalds sought key. 7711da177e4SLinus Torvalds 7721da177e4SLinus Torvalds Note that if there is no entry in this same node which is one more, 7731da177e4SLinus Torvalds then we point to an imaginary entry. for direct items, the 7741da177e4SLinus Torvalds position is in units of bytes, for indirect items the position is 7751da177e4SLinus Torvalds in units of blocknr entries, for directory items the position is in 7761da177e4SLinus Torvalds units of directory entries. */ 7771da177e4SLinus Torvalds 7781da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 7791da177e4SLinus Torvalds int search_for_position_by_key(struct super_block *p_s_sb, /* Pointer to the super block. */ 7801da177e4SLinus Torvalds const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */ 781fec6d055SJosef "Jeff" Sipek struct treepath *p_s_search_path /* Filled up by this function. */ 782bd4c625cSLinus Torvalds ) 783bd4c625cSLinus Torvalds { 7841da177e4SLinus Torvalds struct item_head *p_le_ih; /* pointer to on-disk structure */ 7851da177e4SLinus Torvalds int n_blk_size; 7861da177e4SLinus Torvalds loff_t item_offset, offset; 7871da177e4SLinus Torvalds struct reiserfs_dir_entry de; 7881da177e4SLinus Torvalds int retval; 7891da177e4SLinus Torvalds 7901da177e4SLinus Torvalds /* If searching for directory entry. */ 7911da177e4SLinus Torvalds if (is_direntry_cpu_key(p_cpu_key)) 792bd4c625cSLinus Torvalds return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path, 793bd4c625cSLinus Torvalds &de); 7941da177e4SLinus Torvalds 7951da177e4SLinus Torvalds /* If not searching for directory entry. */ 7961da177e4SLinus Torvalds 7971da177e4SLinus Torvalds /* If item is found. */ 7981da177e4SLinus Torvalds retval = search_item(p_s_sb, p_cpu_key, p_s_search_path); 7991da177e4SLinus Torvalds if (retval == IO_ERROR) 8001da177e4SLinus Torvalds return retval; 8011da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 8021da177e4SLinus Torvalds 803bd4c625cSLinus Torvalds RFALSE(!ih_item_len 804bd4c625cSLinus Torvalds (B_N_PITEM_HEAD 805bd4c625cSLinus Torvalds (PATH_PLAST_BUFFER(p_s_search_path), 8061da177e4SLinus Torvalds PATH_LAST_POSITION(p_s_search_path))), 8071da177e4SLinus Torvalds "PAP-5165: item length equals zero"); 8081da177e4SLinus Torvalds 8091da177e4SLinus Torvalds pos_in_item(p_s_search_path) = 0; 8101da177e4SLinus Torvalds return POSITION_FOUND; 8111da177e4SLinus Torvalds } 8121da177e4SLinus Torvalds 8131da177e4SLinus Torvalds RFALSE(!PATH_LAST_POSITION(p_s_search_path), 8141da177e4SLinus Torvalds "PAP-5170: position equals zero"); 8151da177e4SLinus Torvalds 8161da177e4SLinus Torvalds /* Item is not found. Set path to the previous item. */ 817bd4c625cSLinus Torvalds p_le_ih = 818bd4c625cSLinus Torvalds B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), 819bd4c625cSLinus Torvalds --PATH_LAST_POSITION(p_s_search_path)); 8201da177e4SLinus Torvalds n_blk_size = p_s_sb->s_blocksize; 8211da177e4SLinus Torvalds 8221da177e4SLinus Torvalds if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) { 8231da177e4SLinus Torvalds return FILE_NOT_FOUND; 8241da177e4SLinus Torvalds } 8251da177e4SLinus Torvalds // FIXME: quite ugly this far 8261da177e4SLinus Torvalds 8271da177e4SLinus Torvalds item_offset = le_ih_k_offset(p_le_ih); 8281da177e4SLinus Torvalds offset = cpu_key_k_offset(p_cpu_key); 8291da177e4SLinus Torvalds 8301da177e4SLinus Torvalds /* Needed byte is contained in the item pointed to by the path. */ 8311da177e4SLinus Torvalds if (item_offset <= offset && 8321da177e4SLinus Torvalds item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) { 8331da177e4SLinus Torvalds pos_in_item(p_s_search_path) = offset - item_offset; 8341da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) { 8351da177e4SLinus Torvalds pos_in_item(p_s_search_path) /= n_blk_size; 8361da177e4SLinus Torvalds } 8371da177e4SLinus Torvalds return POSITION_FOUND; 8381da177e4SLinus Torvalds } 8391da177e4SLinus Torvalds 8401da177e4SLinus Torvalds /* Needed byte is not contained in the item pointed to by the 8411da177e4SLinus Torvalds path. Set pos_in_item out of the item. */ 8421da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 843bd4c625cSLinus Torvalds pos_in_item(p_s_search_path) = 844bd4c625cSLinus Torvalds ih_item_len(p_le_ih) / UNFM_P_SIZE; 8451da177e4SLinus Torvalds else 8461da177e4SLinus Torvalds pos_in_item(p_s_search_path) = ih_item_len(p_le_ih); 8471da177e4SLinus Torvalds 8481da177e4SLinus Torvalds return POSITION_NOT_FOUND; 8491da177e4SLinus Torvalds } 8501da177e4SLinus Torvalds 8511da177e4SLinus Torvalds /* Compare given item and item pointed to by the path. */ 852fec6d055SJosef "Jeff" Sipek int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path) 8531da177e4SLinus Torvalds { 8541da177e4SLinus Torvalds struct buffer_head *p_s_bh; 8551da177e4SLinus Torvalds struct item_head *ih; 8561da177e4SLinus Torvalds 8571da177e4SLinus Torvalds /* Last buffer at the path is not in the tree. */ 8581da177e4SLinus Torvalds if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path))) 8591da177e4SLinus Torvalds return 1; 8601da177e4SLinus Torvalds 8611da177e4SLinus Torvalds /* Last path position is invalid. */ 8621da177e4SLinus Torvalds if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh)) 8631da177e4SLinus Torvalds return 1; 8641da177e4SLinus Torvalds 8651da177e4SLinus Torvalds /* we need only to know, whether it is the same item */ 8661da177e4SLinus Torvalds ih = get_ih(p_s_path); 8671da177e4SLinus Torvalds return memcmp(stored_ih, ih, IH_SIZE); 8681da177e4SLinus Torvalds } 8691da177e4SLinus Torvalds 8701da177e4SLinus Torvalds /* unformatted nodes are not logged anymore, ever. This is safe 8711da177e4SLinus Torvalds ** now 8721da177e4SLinus Torvalds */ 8731da177e4SLinus Torvalds #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1) 8741da177e4SLinus Torvalds 8751da177e4SLinus Torvalds // block can not be forgotten as it is in I/O or held by someone 8761da177e4SLinus Torvalds #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh))) 8771da177e4SLinus Torvalds 8781da177e4SLinus Torvalds // prepare for delete or cut of direct item 879fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direct_item(struct treepath *path, 8801da177e4SLinus Torvalds struct item_head *le_ih, 8811da177e4SLinus Torvalds struct inode *inode, 882bd4c625cSLinus Torvalds loff_t new_file_length, int *cut_size) 8831da177e4SLinus Torvalds { 8841da177e4SLinus Torvalds loff_t round_len; 8851da177e4SLinus Torvalds 8861da177e4SLinus Torvalds if (new_file_length == max_reiserfs_offset(inode)) { 8871da177e4SLinus Torvalds /* item has to be deleted */ 8881da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 8891da177e4SLinus Torvalds return M_DELETE; 8901da177e4SLinus Torvalds } 8911da177e4SLinus Torvalds // new file gets truncated 8921da177e4SLinus Torvalds if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) { 8931da177e4SLinus Torvalds // 8941da177e4SLinus Torvalds round_len = ROUND_UP(new_file_length); 8951da177e4SLinus Torvalds /* this was n_new_file_length < le_ih ... */ 8961da177e4SLinus Torvalds if (round_len < le_ih_k_offset(le_ih)) { 8971da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 8981da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 8991da177e4SLinus Torvalds } 9001da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9011da177e4SLinus Torvalds pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1); 9021da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - pos_in_item(path)); 9031da177e4SLinus Torvalds 9041da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9051da177e4SLinus Torvalds } 9061da177e4SLinus Torvalds 9071da177e4SLinus Torvalds // old file: items may have any length 9081da177e4SLinus Torvalds 9091da177e4SLinus Torvalds if (new_file_length < le_ih_k_offset(le_ih)) { 9101da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9111da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9121da177e4SLinus Torvalds } 9131da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9141da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - 915bd4c625cSLinus Torvalds (pos_in_item(path) = 916bd4c625cSLinus Torvalds new_file_length + 1 - le_ih_k_offset(le_ih))); 9171da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9181da177e4SLinus Torvalds } 9191da177e4SLinus Torvalds 920fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direntry_item(struct treepath *path, 9211da177e4SLinus Torvalds struct item_head *le_ih, 9221da177e4SLinus Torvalds struct inode *inode, 9231da177e4SLinus Torvalds loff_t new_file_length, 9241da177e4SLinus Torvalds int *cut_size) 9251da177e4SLinus Torvalds { 9261da177e4SLinus Torvalds if (le_ih_k_offset(le_ih) == DOT_OFFSET && 9271da177e4SLinus Torvalds new_file_length == max_reiserfs_offset(inode)) { 9281da177e4SLinus Torvalds RFALSE(ih_entry_count(le_ih) != 2, 9291da177e4SLinus Torvalds "PAP-5220: incorrect empty directory item (%h)", le_ih); 9301da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9311da177e4SLinus Torvalds return M_DELETE; /* Delete the directory item containing "." and ".." entry. */ 9321da177e4SLinus Torvalds } 9331da177e4SLinus Torvalds 9341da177e4SLinus Torvalds if (ih_entry_count(le_ih) == 1) { 9351da177e4SLinus Torvalds /* Delete the directory item such as there is one record only 9361da177e4SLinus Torvalds in this item */ 9371da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9381da177e4SLinus Torvalds return M_DELETE; 9391da177e4SLinus Torvalds } 9401da177e4SLinus Torvalds 9411da177e4SLinus Torvalds /* Cut one record from the directory item. */ 942bd4c625cSLinus Torvalds *cut_size = 943bd4c625cSLinus Torvalds -(DEH_SIZE + 944bd4c625cSLinus Torvalds entry_length(get_last_bh(path), le_ih, pos_in_item(path))); 9451da177e4SLinus Torvalds return M_CUT; 9461da177e4SLinus Torvalds } 9471da177e4SLinus Torvalds 94823f9e0f8SAlexander Zarochentzev #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1) 94923f9e0f8SAlexander Zarochentzev 9501da177e4SLinus Torvalds /* If the path points to a directory or direct item, calculate mode and the size cut, for balance. 9511da177e4SLinus Torvalds If the path points to an indirect item, remove some number of its unformatted nodes. 9521da177e4SLinus Torvalds In case of file truncate calculate whether this item must be deleted/truncated or last 9531da177e4SLinus Torvalds unformatted node of this item will be converted to a direct item. 9541da177e4SLinus Torvalds This function returns a determination of what balance mode the calling function should employ. */ 955fec6d055SJosef "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 9561da177e4SLinus Torvalds from end of the file. */ 957bd4c625cSLinus Torvalds int *p_n_cut_size, unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */ 958bd4c625cSLinus Torvalds ) 959bd4c625cSLinus Torvalds { 9601da177e4SLinus Torvalds struct super_block *p_s_sb = inode->i_sb; 9611da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path); 9621da177e4SLinus Torvalds struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path); 9631da177e4SLinus Torvalds 9641da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 9651da177e4SLinus Torvalds 9661da177e4SLinus Torvalds /* Stat_data item. */ 9671da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) { 9681da177e4SLinus Torvalds 9691da177e4SLinus Torvalds RFALSE(n_new_file_length != max_reiserfs_offset(inode), 9701da177e4SLinus Torvalds "PAP-5210: mode must be M_DELETE"); 9711da177e4SLinus Torvalds 9721da177e4SLinus Torvalds *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih)); 9731da177e4SLinus Torvalds return M_DELETE; 9741da177e4SLinus Torvalds } 9751da177e4SLinus Torvalds 9761da177e4SLinus Torvalds /* Directory item. */ 9771da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) 978bd4c625cSLinus Torvalds return prepare_for_direntry_item(p_s_path, p_le_ih, inode, 979bd4c625cSLinus Torvalds n_new_file_length, 980bd4c625cSLinus Torvalds p_n_cut_size); 9811da177e4SLinus Torvalds 9821da177e4SLinus Torvalds /* Direct item. */ 9831da177e4SLinus Torvalds if (is_direct_le_ih(p_le_ih)) 984bd4c625cSLinus Torvalds return prepare_for_direct_item(p_s_path, p_le_ih, inode, 985bd4c625cSLinus Torvalds n_new_file_length, p_n_cut_size); 9861da177e4SLinus Torvalds 9871da177e4SLinus Torvalds /* Case of an indirect item. */ 9881da177e4SLinus Torvalds { 98923f9e0f8SAlexander Zarochentzev int blk_size = p_s_sb->s_blocksize; 99023f9e0f8SAlexander Zarochentzev struct item_head s_ih; 99123f9e0f8SAlexander Zarochentzev int need_re_search; 99223f9e0f8SAlexander Zarochentzev int delete = 0; 99323f9e0f8SAlexander Zarochentzev int result = M_CUT; 99423f9e0f8SAlexander Zarochentzev int pos = 0; 9951da177e4SLinus Torvalds 99623f9e0f8SAlexander Zarochentzev if ( n_new_file_length == max_reiserfs_offset (inode) ) { 99723f9e0f8SAlexander Zarochentzev /* prepare_for_delete_or_cut() is called by 99823f9e0f8SAlexander Zarochentzev * reiserfs_delete_item() */ 99923f9e0f8SAlexander Zarochentzev n_new_file_length = 0; 100023f9e0f8SAlexander Zarochentzev delete = 1; 100123f9e0f8SAlexander Zarochentzev } 10021da177e4SLinus Torvalds 10031da177e4SLinus Torvalds do { 100423f9e0f8SAlexander Zarochentzev need_re_search = 0; 100523f9e0f8SAlexander Zarochentzev *p_n_cut_size = 0; 10061da177e4SLinus Torvalds p_s_bh = PATH_PLAST_BUFFER(p_s_path); 10071da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 100823f9e0f8SAlexander Zarochentzev pos = I_UNFM_NUM(&s_ih); 10091da177e4SLinus Torvalds 101023f9e0f8SAlexander Zarochentzev while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) { 101187588dd6SAl Viro __le32 *unfm; 101287588dd6SAl Viro __u32 block; 10131da177e4SLinus Torvalds 101423f9e0f8SAlexander Zarochentzev /* Each unformatted block deletion may involve one additional 101523f9e0f8SAlexander Zarochentzev * bitmap block into the transaction, thereby the initial 101623f9e0f8SAlexander Zarochentzev * journal space reservation might not be enough. */ 101723f9e0f8SAlexander Zarochentzev if (!delete && (*p_n_cut_size) != 0 && 101823f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 101923f9e0f8SAlexander Zarochentzev break; 10201da177e4SLinus Torvalds } 10211da177e4SLinus Torvalds 102287588dd6SAl Viro unfm = (__le32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1; 102323f9e0f8SAlexander Zarochentzev block = get_block_num(unfm, 0); 10241da177e4SLinus Torvalds 102523f9e0f8SAlexander Zarochentzev if (block != 0) { 10261da177e4SLinus Torvalds reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1); 102723f9e0f8SAlexander Zarochentzev put_block_num(unfm, 0, 0); 102823f9e0f8SAlexander Zarochentzev journal_mark_dirty (th, p_s_sb, p_s_bh); 102923f9e0f8SAlexander Zarochentzev reiserfs_free_block(th, inode, block, 1); 103023f9e0f8SAlexander Zarochentzev } 10311da177e4SLinus Torvalds 10321da177e4SLinus Torvalds cond_resched(); 103323f9e0f8SAlexander Zarochentzev 10341da177e4SLinus Torvalds if (item_moved (&s_ih, p_s_path)) { 103523f9e0f8SAlexander Zarochentzev need_re_search = 1; 10361da177e4SLinus Torvalds break; 10371da177e4SLinus Torvalds } 10381da177e4SLinus Torvalds 103923f9e0f8SAlexander Zarochentzev pos --; 10401da177e4SLinus Torvalds (*p_n_removed) ++; 104123f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= UNFM_P_SIZE; 10421da177e4SLinus Torvalds 104323f9e0f8SAlexander Zarochentzev if (pos == 0) { 104423f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= IH_SIZE; 104523f9e0f8SAlexander Zarochentzev result = M_DELETE; 10461da177e4SLinus Torvalds break; 10471da177e4SLinus Torvalds } 10481da177e4SLinus Torvalds } 104923f9e0f8SAlexander Zarochentzev /* a trick. If the buffer has been logged, this will do nothing. If 105023f9e0f8SAlexander Zarochentzev ** we've broken the loop without logging it, it will restore the 105123f9e0f8SAlexander Zarochentzev ** buffer */ 10521da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh); 105323f9e0f8SAlexander Zarochentzev } while (need_re_search && 105423f9e0f8SAlexander Zarochentzev search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND); 105523f9e0f8SAlexander Zarochentzev pos_in_item(p_s_path) = pos * UNFM_P_SIZE; 10561da177e4SLinus Torvalds 105723f9e0f8SAlexander Zarochentzev if (*p_n_cut_size == 0) { 105823f9e0f8SAlexander Zarochentzev /* Nothing were cut. maybe convert last unformatted node to the 105923f9e0f8SAlexander Zarochentzev * direct item? */ 106023f9e0f8SAlexander Zarochentzev result = M_CONVERT; 106123f9e0f8SAlexander Zarochentzev } 106223f9e0f8SAlexander Zarochentzev return result; 10631da177e4SLinus Torvalds } 10641da177e4SLinus Torvalds } 10651da177e4SLinus Torvalds 10661da177e4SLinus Torvalds /* Calculate number of bytes which will be deleted or cut during balance */ 1067bd4c625cSLinus Torvalds static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode) 1068bd4c625cSLinus Torvalds { 10691da177e4SLinus Torvalds int n_del_size; 10701da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path); 10711da177e4SLinus Torvalds 10721da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 10731da177e4SLinus Torvalds return 0; 10741da177e4SLinus Torvalds 1075bd4c625cSLinus Torvalds n_del_size = 1076bd4c625cSLinus Torvalds (c_mode == 1077bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0]; 10781da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) { 10791da177e4SLinus Torvalds // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */ 10801da177e4SLinus Torvalds // we can't use EMPTY_DIR_SIZE, as old format dirs have a different 10811da177e4SLinus Torvalds // empty size. ick. FIXME, is this right? 10821da177e4SLinus Torvalds // 10831da177e4SLinus Torvalds return n_del_size; 10841da177e4SLinus Torvalds } 10851da177e4SLinus Torvalds 10861da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 1087bd4c625cSLinus 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); 10881da177e4SLinus Torvalds return n_del_size; 10891da177e4SLinus Torvalds } 10901da177e4SLinus Torvalds 1091bd4c625cSLinus Torvalds static void init_tb_struct(struct reiserfs_transaction_handle *th, 10921da177e4SLinus Torvalds struct tree_balance *p_s_tb, 10931da177e4SLinus Torvalds struct super_block *p_s_sb, 1094fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, int n_size) 1095bd4c625cSLinus Torvalds { 10961da177e4SLinus Torvalds 10971da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 10981da177e4SLinus Torvalds 10991da177e4SLinus Torvalds memset(p_s_tb, '\0', sizeof(struct tree_balance)); 11001da177e4SLinus Torvalds p_s_tb->transaction_handle = th; 11011da177e4SLinus Torvalds p_s_tb->tb_sb = p_s_sb; 11021da177e4SLinus Torvalds p_s_tb->tb_path = p_s_path; 11031da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL; 11041da177e4SLinus Torvalds PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0; 11051da177e4SLinus Torvalds p_s_tb->insert_size[0] = n_size; 11061da177e4SLinus Torvalds } 11071da177e4SLinus Torvalds 11081da177e4SLinus Torvalds void padd_item(char *item, int total_length, int length) 11091da177e4SLinus Torvalds { 11101da177e4SLinus Torvalds int i; 11111da177e4SLinus Torvalds 11121da177e4SLinus Torvalds for (i = total_length; i > length;) 11131da177e4SLinus Torvalds item[--i] = 0; 11141da177e4SLinus Torvalds } 11151da177e4SLinus Torvalds 11161da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 11171da177e4SLinus Torvalds char key2type(struct reiserfs_key *ih) 11181da177e4SLinus Torvalds { 11191da177e4SLinus Torvalds if (is_direntry_le_key(2, ih)) 11201da177e4SLinus Torvalds return 'd'; 11211da177e4SLinus Torvalds if (is_direct_le_key(2, ih)) 11221da177e4SLinus Torvalds return 'D'; 11231da177e4SLinus Torvalds if (is_indirect_le_key(2, ih)) 11241da177e4SLinus Torvalds return 'i'; 11251da177e4SLinus Torvalds if (is_statdata_le_key(2, ih)) 11261da177e4SLinus Torvalds return 's'; 11271da177e4SLinus Torvalds return 'u'; 11281da177e4SLinus Torvalds } 11291da177e4SLinus Torvalds 11301da177e4SLinus Torvalds char head2type(struct item_head *ih) 11311da177e4SLinus Torvalds { 11321da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) 11331da177e4SLinus Torvalds return 'd'; 11341da177e4SLinus Torvalds if (is_direct_le_ih(ih)) 11351da177e4SLinus Torvalds return 'D'; 11361da177e4SLinus Torvalds if (is_indirect_le_ih(ih)) 11371da177e4SLinus Torvalds return 'i'; 11381da177e4SLinus Torvalds if (is_statdata_le_ih(ih)) 11391da177e4SLinus Torvalds return 's'; 11401da177e4SLinus Torvalds return 'u'; 11411da177e4SLinus Torvalds } 11421da177e4SLinus Torvalds #endif 11431da177e4SLinus Torvalds 11441da177e4SLinus Torvalds /* Delete object item. */ 1145fec6d055SJosef "Jeff" Sipek int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the deleted item. */ 11461da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, /* Key to search for the deleted item. */ 11471da177e4SLinus Torvalds struct inode *p_s_inode, /* inode is here just to update i_blocks and quotas */ 1148bd4c625cSLinus Torvalds struct buffer_head *p_s_un_bh) 1149bd4c625cSLinus Torvalds { /* NULL or unformatted node pointer. */ 11501da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 11511da177e4SLinus Torvalds struct tree_balance s_del_balance; 11521da177e4SLinus Torvalds struct item_head s_ih; 11531da177e4SLinus Torvalds struct item_head *q_ih; 11541da177e4SLinus Torvalds int quota_cut_bytes; 1155bd4c625cSLinus Torvalds int n_ret_value, n_del_size, n_removed; 11561da177e4SLinus Torvalds 11571da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 11581da177e4SLinus Torvalds char c_mode; 11591da177e4SLinus Torvalds int n_iter = 0; 11601da177e4SLinus Torvalds #endif 11611da177e4SLinus Torvalds 11621da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11631da177e4SLinus Torvalds 1164bd4c625cSLinus Torvalds init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path, 1165bd4c625cSLinus Torvalds 0 /*size is unknown */ ); 11661da177e4SLinus Torvalds 11671da177e4SLinus Torvalds while (1) { 11681da177e4SLinus Torvalds n_removed = 0; 11691da177e4SLinus Torvalds 11701da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 11711da177e4SLinus Torvalds n_iter++; 11721da177e4SLinus Torvalds c_mode = 11731da177e4SLinus Torvalds #endif 1174bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1175bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 1176bd4c625cSLinus Torvalds &n_del_size, 1177bd4c625cSLinus Torvalds max_reiserfs_offset(p_s_inode)); 11781da177e4SLinus Torvalds 11791da177e4SLinus Torvalds RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE"); 11801da177e4SLinus Torvalds 11811da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 11821da177e4SLinus Torvalds s_del_balance.insert_size[0] = n_del_size; 11831da177e4SLinus Torvalds 11841da177e4SLinus Torvalds n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL); 11851da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 11861da177e4SLinus Torvalds break; 11871da177e4SLinus Torvalds 11881da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, delete_item_restarted); 11891da177e4SLinus Torvalds 11901da177e4SLinus Torvalds // file system changed, repeat search 1191bd4c625cSLinus Torvalds n_ret_value = 1192bd4c625cSLinus Torvalds search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path); 11931da177e4SLinus Torvalds if (n_ret_value == IO_ERROR) 11941da177e4SLinus Torvalds break; 11951da177e4SLinus Torvalds if (n_ret_value == FILE_NOT_FOUND) { 119645b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "vs-5340", 1197bd4c625cSLinus Torvalds "no items of the file %K found", 1198bd4c625cSLinus Torvalds p_s_item_key); 11991da177e4SLinus Torvalds break; 12001da177e4SLinus Torvalds } 12011da177e4SLinus Torvalds } /* while (1) */ 12021da177e4SLinus Torvalds 12031da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 12041da177e4SLinus Torvalds unfix_nodes(&s_del_balance); 12051da177e4SLinus Torvalds return 0; 12061da177e4SLinus Torvalds } 12071da177e4SLinus Torvalds // reiserfs_delete_item returns item length when success 12081da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE); 12091da177e4SLinus Torvalds q_ih = get_ih(p_s_path); 12101da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(q_ih); 12111da177e4SLinus Torvalds 12121da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file 12131da177e4SLinus Torvalds ** has a tail. On tail insert, we allocate quota for 1 unformatted node. 12141da177e4SLinus Torvalds ** We test the offset because the tail might have been 12151da177e4SLinus Torvalds ** split into multiple items, and we only want to decrement for 12161da177e4SLinus Torvalds ** the unfm node once 12171da177e4SLinus Torvalds */ 12181da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) { 12191da177e4SLinus Torvalds if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) { 12201da177e4SLinus Torvalds quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE; 12211da177e4SLinus Torvalds } else { 12221da177e4SLinus Torvalds quota_cut_bytes = 0; 12231da177e4SLinus Torvalds } 12241da177e4SLinus Torvalds } 12251da177e4SLinus Torvalds 12261da177e4SLinus Torvalds if (p_s_un_bh) { 12271da177e4SLinus Torvalds int off; 12281da177e4SLinus Torvalds char *data; 12291da177e4SLinus Torvalds 12301da177e4SLinus Torvalds /* We are in direct2indirect conversion, so move tail contents 12311da177e4SLinus Torvalds to the unformatted node */ 12321da177e4SLinus Torvalds /* note, we do the copy before preparing the buffer because we 12331da177e4SLinus Torvalds ** don't care about the contents of the unformatted node yet. 12341da177e4SLinus Torvalds ** the only thing we really care about is the direct item's data 12351da177e4SLinus Torvalds ** is in the unformatted node. 12361da177e4SLinus Torvalds ** 12371da177e4SLinus Torvalds ** Otherwise, we would have to call reiserfs_prepare_for_journal on 12381da177e4SLinus Torvalds ** the unformatted node, which might schedule, meaning we'd have to 12391da177e4SLinus Torvalds ** loop all the way back up to the start of the while loop. 12401da177e4SLinus Torvalds ** 12411da177e4SLinus Torvalds ** The unformatted node must be dirtied later on. We can't be 12421da177e4SLinus Torvalds ** sure here if the entire tail has been deleted yet. 12431da177e4SLinus Torvalds ** 12441da177e4SLinus Torvalds ** p_s_un_bh is from the page cache (all unformatted nodes are 12451da177e4SLinus Torvalds ** from the page cache) and might be a highmem page. So, we 12461da177e4SLinus Torvalds ** can't use p_s_un_bh->b_data. 12471da177e4SLinus Torvalds ** -clm 12481da177e4SLinus Torvalds */ 12491da177e4SLinus Torvalds 12501da177e4SLinus Torvalds data = kmap_atomic(p_s_un_bh->b_page, KM_USER0); 12511da177e4SLinus Torvalds off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1)); 12521da177e4SLinus Torvalds memcpy(data + off, 1253bd4c625cSLinus Torvalds B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), 1254bd4c625cSLinus Torvalds n_ret_value); 12551da177e4SLinus Torvalds kunmap_atomic(data, KM_USER0); 12561da177e4SLinus Torvalds } 12571da177e4SLinus Torvalds /* Perform balancing after all resources have been collected at once. */ 12581da177e4SLinus Torvalds do_balance(&s_del_balance, NULL, NULL, M_DELETE); 12591da177e4SLinus Torvalds 12601da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1261bd4c625cSLinus Torvalds reiserfs_debug(p_s_sb, REISERFS_DEBUG_CODE, 1262bd4c625cSLinus Torvalds "reiserquota delete_item(): freeing %u, id=%u type=%c", 1263bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih)); 12641da177e4SLinus Torvalds #endif 12651da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 12661da177e4SLinus Torvalds 12671da177e4SLinus Torvalds /* Return deleted body length */ 12681da177e4SLinus Torvalds return n_ret_value; 12691da177e4SLinus Torvalds } 12701da177e4SLinus Torvalds 12711da177e4SLinus Torvalds /* Summary Of Mechanisms For Handling Collisions Between Processes: 12721da177e4SLinus Torvalds 12731da177e4SLinus Torvalds deletion of the body of the object is performed by iput(), with the 12741da177e4SLinus Torvalds result that if multiple processes are operating on a file, the 12751da177e4SLinus Torvalds deletion of the body of the file is deferred until the last process 12761da177e4SLinus Torvalds that has an open inode performs its iput(). 12771da177e4SLinus Torvalds 12781da177e4SLinus Torvalds writes and truncates are protected from collisions by use of 12791da177e4SLinus Torvalds semaphores. 12801da177e4SLinus Torvalds 12811da177e4SLinus Torvalds creates, linking, and mknod are protected from collisions with other 12821da177e4SLinus Torvalds processes by making the reiserfs_add_entry() the last step in the 12831da177e4SLinus Torvalds creation, and then rolling back all changes if there was a collision. 12841da177e4SLinus Torvalds - Hans 12851da177e4SLinus Torvalds */ 12861da177e4SLinus Torvalds 12871da177e4SLinus Torvalds /* this deletes item which never gets split */ 12881da177e4SLinus Torvalds void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, 1289bd4c625cSLinus Torvalds struct inode *inode, struct reiserfs_key *key) 12901da177e4SLinus Torvalds { 12911da177e4SLinus Torvalds struct tree_balance tb; 12921da177e4SLinus Torvalds INITIALIZE_PATH(path); 12931da177e4SLinus Torvalds int item_len = 0; 12941da177e4SLinus Torvalds int tb_init = 0; 12951da177e4SLinus Torvalds struct cpu_key cpu_key; 12961da177e4SLinus Torvalds int retval; 12971da177e4SLinus Torvalds int quota_cut_bytes = 0; 12981da177e4SLinus Torvalds 12991da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 13001da177e4SLinus Torvalds 13011da177e4SLinus Torvalds le_key2cpu_key(&cpu_key, key); 13021da177e4SLinus Torvalds 13031da177e4SLinus Torvalds while (1) { 13041da177e4SLinus Torvalds retval = search_item(th->t_super, &cpu_key, &path); 13051da177e4SLinus Torvalds if (retval == IO_ERROR) { 13060030b645SJeff Mahoney reiserfs_error(th->t_super, "vs-5350", 130745b03d5eSJeff Mahoney "i/o failure occurred trying " 130845b03d5eSJeff Mahoney "to delete %K", &cpu_key); 13091da177e4SLinus Torvalds break; 13101da177e4SLinus Torvalds } 13111da177e4SLinus Torvalds if (retval != ITEM_FOUND) { 13121da177e4SLinus Torvalds pathrelse(&path); 13131da177e4SLinus Torvalds // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir 1314bd4c625cSLinus Torvalds if (! 1315bd4c625cSLinus Torvalds ((unsigned long long) 1316bd4c625cSLinus Torvalds GET_HASH_VALUE(le_key_k_offset 1317bd4c625cSLinus Torvalds (le_key_version(key), key)) == 0 1318bd4c625cSLinus Torvalds && (unsigned long long) 1319bd4c625cSLinus Torvalds GET_GENERATION_NUMBER(le_key_k_offset 1320bd4c625cSLinus Torvalds (le_key_version(key), 1321bd4c625cSLinus Torvalds key)) == 1)) 132245b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5355", 132345b03d5eSJeff Mahoney "%k not found", key); 13241da177e4SLinus Torvalds break; 13251da177e4SLinus Torvalds } 13261da177e4SLinus Torvalds if (!tb_init) { 13271da177e4SLinus Torvalds tb_init = 1; 13281da177e4SLinus Torvalds item_len = ih_item_len(PATH_PITEM_HEAD(&path)); 1329bd4c625cSLinus Torvalds init_tb_struct(th, &tb, th->t_super, &path, 1330bd4c625cSLinus Torvalds -(IH_SIZE + item_len)); 13311da177e4SLinus Torvalds } 13321da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path)); 13331da177e4SLinus Torvalds 13341da177e4SLinus Torvalds retval = fix_nodes(M_DELETE, &tb, NULL, NULL); 13351da177e4SLinus Torvalds if (retval == REPEAT_SEARCH) { 13361da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, delete_solid_item_restarted); 13371da177e4SLinus Torvalds continue; 13381da177e4SLinus Torvalds } 13391da177e4SLinus Torvalds 13401da177e4SLinus Torvalds if (retval == CARRY_ON) { 13411da177e4SLinus Torvalds do_balance(&tb, NULL, NULL, M_DELETE); 13421da177e4SLinus Torvalds if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */ 13431da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1344bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 1345bd4c625cSLinus Torvalds "reiserquota delete_solid_item(): freeing %u id=%u type=%c", 1346bd4c625cSLinus Torvalds quota_cut_bytes, inode->i_uid, 1347bd4c625cSLinus Torvalds key2type(key)); 13481da177e4SLinus Torvalds #endif 1349bd4c625cSLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, 1350bd4c625cSLinus Torvalds quota_cut_bytes); 13511da177e4SLinus Torvalds } 13521da177e4SLinus Torvalds break; 13531da177e4SLinus Torvalds } 13541da177e4SLinus Torvalds // IO_ERROR, NO_DISK_SPACE, etc 135545b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5360", 1356bd4c625cSLinus Torvalds "could not delete %K due to fix_nodes failure", 1357bd4c625cSLinus Torvalds &cpu_key); 13581da177e4SLinus Torvalds unfix_nodes(&tb); 13591da177e4SLinus Torvalds break; 13601da177e4SLinus Torvalds } 13611da177e4SLinus Torvalds 13621da177e4SLinus Torvalds reiserfs_check_path(&path); 13631da177e4SLinus Torvalds } 13641da177e4SLinus Torvalds 1365bd4c625cSLinus Torvalds int reiserfs_delete_object(struct reiserfs_transaction_handle *th, 1366bd4c625cSLinus Torvalds struct inode *inode) 13671da177e4SLinus Torvalds { 13681da177e4SLinus Torvalds int err; 13691da177e4SLinus Torvalds inode->i_size = 0; 13701da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 13711da177e4SLinus Torvalds 13721da177e4SLinus Torvalds /* for directory this deletes item containing "." and ".." */ 1373bd4c625cSLinus Torvalds err = 1374bd4c625cSLinus Torvalds reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ ); 13751da177e4SLinus Torvalds if (err) 13761da177e4SLinus Torvalds return err; 13771da177e4SLinus Torvalds 13781da177e4SLinus Torvalds #if defined( USE_INODE_GENERATION_COUNTER ) 1379bd4c625cSLinus Torvalds if (!old_format_only(th->t_super)) { 13803e8962beSAl Viro __le32 *inode_generation; 13811da177e4SLinus Torvalds 13821da177e4SLinus Torvalds inode_generation = 13831da177e4SLinus Torvalds &REISERFS_SB(th->t_super)->s_rs->s_inode_generation; 13849e902df6SMarcin Slusarz le32_add_cpu(inode_generation, 1); 13851da177e4SLinus Torvalds } 13861da177e4SLinus Torvalds /* USE_INODE_GENERATION_COUNTER */ 13871da177e4SLinus Torvalds #endif 13881da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 13891da177e4SLinus Torvalds 13901da177e4SLinus Torvalds return err; 13911da177e4SLinus Torvalds } 13921da177e4SLinus Torvalds 1393bd4c625cSLinus Torvalds static void unmap_buffers(struct page *page, loff_t pos) 1394bd4c625cSLinus Torvalds { 13951da177e4SLinus Torvalds struct buffer_head *bh; 13961da177e4SLinus Torvalds struct buffer_head *head; 13971da177e4SLinus Torvalds struct buffer_head *next; 13981da177e4SLinus Torvalds unsigned long tail_index; 13991da177e4SLinus Torvalds unsigned long cur_index; 14001da177e4SLinus Torvalds 14011da177e4SLinus Torvalds if (page) { 14021da177e4SLinus Torvalds if (page_has_buffers(page)) { 14031da177e4SLinus Torvalds tail_index = pos & (PAGE_CACHE_SIZE - 1); 14041da177e4SLinus Torvalds cur_index = 0; 14051da177e4SLinus Torvalds head = page_buffers(page); 14061da177e4SLinus Torvalds bh = head; 14071da177e4SLinus Torvalds do { 14081da177e4SLinus Torvalds next = bh->b_this_page; 14091da177e4SLinus Torvalds 14101da177e4SLinus Torvalds /* we want to unmap the buffers that contain the tail, and 14111da177e4SLinus Torvalds ** all the buffers after it (since the tail must be at the 14121da177e4SLinus Torvalds ** end of the file). We don't want to unmap file data 14131da177e4SLinus Torvalds ** before the tail, since it might be dirty and waiting to 14141da177e4SLinus Torvalds ** reach disk 14151da177e4SLinus Torvalds */ 14161da177e4SLinus Torvalds cur_index += bh->b_size; 14171da177e4SLinus Torvalds if (cur_index > tail_index) { 14181da177e4SLinus Torvalds reiserfs_unmap_buffer(bh); 14191da177e4SLinus Torvalds } 14201da177e4SLinus Torvalds bh = next; 14211da177e4SLinus Torvalds } while (bh != head); 14221da177e4SLinus Torvalds } 14231da177e4SLinus Torvalds } 14241da177e4SLinus Torvalds } 14251da177e4SLinus Torvalds 14261da177e4SLinus Torvalds static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, 14271da177e4SLinus Torvalds struct inode *p_s_inode, 14281da177e4SLinus Torvalds struct page *page, 1429fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 14301da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, 1431bd4c625cSLinus Torvalds loff_t n_new_file_size, char *p_c_mode) 1432bd4c625cSLinus Torvalds { 14331da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 14341da177e4SLinus Torvalds int n_block_size = p_s_sb->s_blocksize; 14351da177e4SLinus Torvalds int cut_bytes; 14361da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 143714a61442SEric Sesterhenn BUG_ON(n_new_file_size != p_s_inode->i_size); 14381da177e4SLinus Torvalds 14391da177e4SLinus Torvalds /* the page being sent in could be NULL if there was an i/o error 14401da177e4SLinus Torvalds ** reading in the last block. The user will hit problems trying to 14411da177e4SLinus Torvalds ** read the file, but for now we just skip the indirect2direct 14421da177e4SLinus Torvalds */ 14431da177e4SLinus Torvalds if (atomic_read(&p_s_inode->i_count) > 1 || 14441da177e4SLinus Torvalds !tail_has_to_be_packed(p_s_inode) || 14451da177e4SLinus Torvalds !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) { 14461da177e4SLinus Torvalds // leave tail in an unformatted node 14471da177e4SLinus Torvalds *p_c_mode = M_SKIP_BALANCING; 1448bd4c625cSLinus Torvalds cut_bytes = 1449bd4c625cSLinus Torvalds n_block_size - (n_new_file_size & (n_block_size - 1)); 14501da177e4SLinus Torvalds pathrelse(p_s_path); 14511da177e4SLinus Torvalds return cut_bytes; 14521da177e4SLinus Torvalds } 14531da177e4SLinus Torvalds /* Permorm the conversion to a direct_item. */ 14541da177e4SLinus Torvalds /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */ 1455bd4c625cSLinus Torvalds return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key, 1456bd4c625cSLinus Torvalds n_new_file_size, p_c_mode); 14571da177e4SLinus Torvalds } 14581da177e4SLinus Torvalds 14591da177e4SLinus Torvalds /* we did indirect_to_direct conversion. And we have inserted direct 14601da177e4SLinus Torvalds item successesfully, but there were no disk space to cut unfm 14611da177e4SLinus Torvalds pointer being converted. Therefore we have to delete inserted 14621da177e4SLinus Torvalds direct item(s) */ 1463bd4c625cSLinus Torvalds static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, 1464fec6d055SJosef "Jeff" Sipek struct inode *inode, struct treepath *path) 14651da177e4SLinus Torvalds { 14661da177e4SLinus Torvalds struct cpu_key tail_key; 14671da177e4SLinus Torvalds int tail_len; 14681da177e4SLinus Torvalds int removed; 14691da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 14701da177e4SLinus Torvalds 14711da177e4SLinus Torvalds make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); // !!!! 14721da177e4SLinus Torvalds tail_key.key_length = 4; 14731da177e4SLinus Torvalds 1474bd4c625cSLinus Torvalds tail_len = 1475bd4c625cSLinus Torvalds (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1; 14761da177e4SLinus Torvalds while (tail_len) { 14771da177e4SLinus Torvalds /* look for the last byte of the tail */ 1478bd4c625cSLinus Torvalds if (search_for_position_by_key(inode->i_sb, &tail_key, path) == 1479bd4c625cSLinus Torvalds POSITION_NOT_FOUND) 1480c3a9c210SJeff Mahoney reiserfs_panic(inode->i_sb, "vs-5615", 1481c3a9c210SJeff Mahoney "found invalid item"); 1482bd4c625cSLinus Torvalds RFALSE(path->pos_in_item != 1483bd4c625cSLinus Torvalds ih_item_len(PATH_PITEM_HEAD(path)) - 1, 14841da177e4SLinus Torvalds "vs-5616: appended bytes found"); 14851da177e4SLinus Torvalds PATH_LAST_POSITION(path)--; 14861da177e4SLinus Torvalds 1487bd4c625cSLinus Torvalds removed = 1488bd4c625cSLinus Torvalds reiserfs_delete_item(th, path, &tail_key, inode, 1489bd4c625cSLinus Torvalds NULL /*unbh not needed */ ); 1490bd4c625cSLinus Torvalds RFALSE(removed <= 0 1491bd4c625cSLinus Torvalds || removed > tail_len, 14921da177e4SLinus Torvalds "vs-5617: there was tail %d bytes, removed item length %d bytes", 14931da177e4SLinus Torvalds tail_len, removed); 14941da177e4SLinus Torvalds tail_len -= removed; 1495bd4c625cSLinus Torvalds set_cpu_key_k_offset(&tail_key, 1496bd4c625cSLinus Torvalds cpu_key_k_offset(&tail_key) - removed); 14971da177e4SLinus Torvalds } 149845b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct " 149945b03d5eSJeff Mahoney "conversion has been rolled back due to " 150045b03d5eSJeff Mahoney "lack of disk space"); 15011da177e4SLinus Torvalds //mark_file_without_tail (inode); 15021da177e4SLinus Torvalds mark_inode_dirty(inode); 15031da177e4SLinus Torvalds } 15041da177e4SLinus Torvalds 15051da177e4SLinus Torvalds /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ 15061da177e4SLinus Torvalds int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, 1507fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 15081da177e4SLinus Torvalds struct cpu_key *p_s_item_key, 15091da177e4SLinus Torvalds struct inode *p_s_inode, 1510bd4c625cSLinus Torvalds struct page *page, loff_t n_new_file_size) 15111da177e4SLinus Torvalds { 15121da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 15131da177e4SLinus Torvalds /* Every function which is going to call do_balance must first 15141da177e4SLinus Torvalds create a tree_balance structure. Then it must fill up this 15151da177e4SLinus Torvalds structure by using the init_tb_struct and fix_nodes functions. 15161da177e4SLinus Torvalds After that we can make tree balancing. */ 15171da177e4SLinus Torvalds struct tree_balance s_cut_balance; 15181da177e4SLinus Torvalds struct item_head *p_le_ih; 15191da177e4SLinus Torvalds int n_cut_size = 0, /* Amount to be cut. */ 1520bd4c625cSLinus Torvalds n_ret_value = CARRY_ON, n_removed = 0, /* Number of the removed unformatted nodes. */ 15211da177e4SLinus Torvalds n_is_inode_locked = 0; 15221da177e4SLinus Torvalds char c_mode; /* Mode of the balance. */ 15231da177e4SLinus Torvalds int retval2 = -1; 15241da177e4SLinus Torvalds int quota_cut_bytes; 15251da177e4SLinus Torvalds loff_t tail_pos = 0; 15261da177e4SLinus Torvalds 15271da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15281da177e4SLinus Torvalds 1529bd4c625cSLinus Torvalds init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, 1530bd4c625cSLinus Torvalds n_cut_size); 15311da177e4SLinus Torvalds 15321da177e4SLinus Torvalds /* Repeat this loop until we either cut the item without needing 15331da177e4SLinus Torvalds to balance, or we fix_nodes without schedule occurring */ 15341da177e4SLinus Torvalds while (1) { 15351da177e4SLinus Torvalds /* Determine the balance mode, position of the first byte to 15361da177e4SLinus Torvalds be cut, and size to be cut. In case of the indirect item 15371da177e4SLinus Torvalds free unformatted nodes which are pointed to by the cut 15381da177e4SLinus Torvalds pointers. */ 15391da177e4SLinus Torvalds 1540bd4c625cSLinus Torvalds c_mode = 1541bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1542bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 15431da177e4SLinus Torvalds &n_cut_size, n_new_file_size); 15441da177e4SLinus Torvalds if (c_mode == M_CONVERT) { 15451da177e4SLinus Torvalds /* convert last unformatted node to direct item or leave 15461da177e4SLinus Torvalds tail in the unformatted node */ 1547bd4c625cSLinus Torvalds RFALSE(n_ret_value != CARRY_ON, 1548bd4c625cSLinus Torvalds "PAP-5570: can not convert twice"); 15491da177e4SLinus Torvalds 1550bd4c625cSLinus Torvalds n_ret_value = 1551bd4c625cSLinus Torvalds maybe_indirect_to_direct(th, p_s_inode, page, 1552bd4c625cSLinus Torvalds p_s_path, p_s_item_key, 15531da177e4SLinus Torvalds n_new_file_size, &c_mode); 15541da177e4SLinus Torvalds if (c_mode == M_SKIP_BALANCING) 15551da177e4SLinus Torvalds /* tail has been left in the unformatted node */ 15561da177e4SLinus Torvalds return n_ret_value; 15571da177e4SLinus Torvalds 15581da177e4SLinus Torvalds n_is_inode_locked = 1; 15591da177e4SLinus Torvalds 15601da177e4SLinus Torvalds /* removing of last unformatted node will change value we 15611da177e4SLinus Torvalds have to return to truncate. Save it */ 15621da177e4SLinus Torvalds retval2 = n_ret_value; 15631da177e4SLinus Torvalds /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1)); */ 15641da177e4SLinus Torvalds 15651da177e4SLinus Torvalds /* So, we have performed the first part of the conversion: 15661da177e4SLinus Torvalds inserting the new direct item. Now we are removing the 15671da177e4SLinus Torvalds last unformatted node pointer. Set key to search for 15681da177e4SLinus Torvalds it. */ 15691da177e4SLinus Torvalds set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT); 15701da177e4SLinus Torvalds p_s_item_key->key_length = 4; 1571bd4c625cSLinus Torvalds n_new_file_size -= 1572bd4c625cSLinus Torvalds (n_new_file_size & (p_s_sb->s_blocksize - 1)); 15731da177e4SLinus Torvalds tail_pos = n_new_file_size; 15741da177e4SLinus Torvalds set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1); 1575bd4c625cSLinus Torvalds if (search_for_position_by_key 1576bd4c625cSLinus Torvalds (p_s_sb, p_s_item_key, 1577bd4c625cSLinus Torvalds p_s_path) == POSITION_NOT_FOUND) { 1578bd4c625cSLinus Torvalds print_block(PATH_PLAST_BUFFER(p_s_path), 3, 1579bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) - 1, 1580bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) + 1); 1581c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "PAP-5580", "item to " 1582c3a9c210SJeff Mahoney "convert does not exist (%K)", 1583bd4c625cSLinus Torvalds p_s_item_key); 15841da177e4SLinus Torvalds } 15851da177e4SLinus Torvalds continue; 15861da177e4SLinus Torvalds } 15871da177e4SLinus Torvalds if (n_cut_size == 0) { 15881da177e4SLinus Torvalds pathrelse(p_s_path); 15891da177e4SLinus Torvalds return 0; 15901da177e4SLinus Torvalds } 15911da177e4SLinus Torvalds 15921da177e4SLinus Torvalds s_cut_balance.insert_size[0] = n_cut_size; 15931da177e4SLinus Torvalds 15941da177e4SLinus Torvalds n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL); 15951da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 15961da177e4SLinus Torvalds break; 15971da177e4SLinus Torvalds 15981da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, cut_from_item_restarted); 15991da177e4SLinus Torvalds 1600bd4c625cSLinus Torvalds n_ret_value = 1601bd4c625cSLinus Torvalds search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path); 16021da177e4SLinus Torvalds if (n_ret_value == POSITION_FOUND) 16031da177e4SLinus Torvalds continue; 16041da177e4SLinus Torvalds 160545b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "PAP-5610", "item %K not found", 1606bd4c625cSLinus Torvalds p_s_item_key); 16071da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16081da177e4SLinus Torvalds return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT; 16091da177e4SLinus Torvalds } /* while */ 16101da177e4SLinus Torvalds 16111da177e4SLinus Torvalds // check fix_nodes results (IO_ERROR or NO_DISK_SPACE) 16121da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 16131da177e4SLinus Torvalds if (n_is_inode_locked) { 16141da177e4SLinus Torvalds // FIXME: this seems to be not needed: we are always able 16151da177e4SLinus Torvalds // to cut item 16161da177e4SLinus Torvalds indirect_to_direct_roll_back(th, p_s_inode, p_s_path); 16171da177e4SLinus Torvalds } 16181da177e4SLinus Torvalds if (n_ret_value == NO_DISK_SPACE) 161945b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "reiserfs-5092", 162045b03d5eSJeff Mahoney "NO_DISK_SPACE"); 16211da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16221da177e4SLinus Torvalds return -EIO; 16231da177e4SLinus Torvalds } 16241da177e4SLinus Torvalds 16251da177e4SLinus Torvalds /* go ahead and perform balancing */ 16261da177e4SLinus Torvalds 16271da177e4SLinus Torvalds RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode"); 16281da177e4SLinus Torvalds 16291da177e4SLinus Torvalds /* Calculate number of bytes that need to be cut from the item. */ 1630bd4c625cSLinus Torvalds quota_cut_bytes = 1631bd4c625cSLinus Torvalds (c_mode == 1632bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance. 1633bd4c625cSLinus Torvalds insert_size[0]; 16341da177e4SLinus Torvalds if (retval2 == -1) 16351da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode); 16361da177e4SLinus Torvalds else 16371da177e4SLinus Torvalds n_ret_value = retval2; 16381da177e4SLinus Torvalds 16391da177e4SLinus Torvalds /* For direct items, we only change the quota when deleting the last 16401da177e4SLinus Torvalds ** item. 16411da177e4SLinus Torvalds */ 16421da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path); 16431da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) { 16441da177e4SLinus Torvalds if (c_mode == M_DELETE && 1645bd4c625cSLinus Torvalds (le_ih_k_offset(p_le_ih) & (p_s_sb->s_blocksize - 1)) == 1646bd4c625cSLinus Torvalds 1) { 16471da177e4SLinus Torvalds // FIXME: this is to keep 3.5 happy 16481da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX; 16491da177e4SLinus Torvalds quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE; 16501da177e4SLinus Torvalds } else { 16511da177e4SLinus Torvalds quota_cut_bytes = 0; 16521da177e4SLinus Torvalds } 16531da177e4SLinus Torvalds } 16541da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 16551da177e4SLinus Torvalds if (n_is_inode_locked) { 1656bd4c625cSLinus Torvalds struct item_head *le_ih = 1657bd4c625cSLinus Torvalds PATH_PITEM_HEAD(s_cut_balance.tb_path); 16581da177e4SLinus Torvalds /* we are going to complete indirect2direct conversion. Make 16591da177e4SLinus Torvalds sure, that we exactly remove last unformatted node pointer 16601da177e4SLinus Torvalds of the item */ 16611da177e4SLinus Torvalds if (!is_indirect_le_ih(le_ih)) 1662c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5652", 16631da177e4SLinus Torvalds "item must be indirect %h", le_ih); 16641da177e4SLinus Torvalds 16651da177e4SLinus Torvalds if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE) 1666c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5653", "completing " 1667c3a9c210SJeff Mahoney "indirect2direct conversion indirect " 1668c3a9c210SJeff Mahoney "item %h being deleted must be of " 1669c3a9c210SJeff Mahoney "4 byte long", le_ih); 16701da177e4SLinus Torvalds 1671bd4c625cSLinus Torvalds if (c_mode == M_CUT 1672bd4c625cSLinus Torvalds && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) { 1673c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5654", "can not complete " 1674c3a9c210SJeff Mahoney "indirect2direct conversion of %h " 1675c3a9c210SJeff Mahoney "(CUT, insert_size==%d)", 16761da177e4SLinus Torvalds le_ih, s_cut_balance.insert_size[0]); 16771da177e4SLinus Torvalds } 16781da177e4SLinus Torvalds /* it would be useful to make sure, that right neighboring 16791da177e4SLinus Torvalds item is direct item of this file */ 16801da177e4SLinus Torvalds } 16811da177e4SLinus Torvalds #endif 16821da177e4SLinus Torvalds 16831da177e4SLinus Torvalds do_balance(&s_cut_balance, NULL, NULL, c_mode); 16841da177e4SLinus Torvalds if (n_is_inode_locked) { 16851da177e4SLinus Torvalds /* we've done an indirect->direct conversion. when the data block 16861da177e4SLinus Torvalds ** was freed, it was removed from the list of blocks that must 16871da177e4SLinus Torvalds ** be flushed before the transaction commits, make sure to 16881da177e4SLinus Torvalds ** unmap and invalidate it 16891da177e4SLinus Torvalds */ 16901da177e4SLinus Torvalds unmap_buffers(page, tail_pos); 16911da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask; 16921da177e4SLinus Torvalds } 16931da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1694bd4c625cSLinus Torvalds reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE, 1695bd4c625cSLinus Torvalds "reiserquota cut_from_item(): freeing %u id=%u type=%c", 1696bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, '?'); 16971da177e4SLinus Torvalds #endif 16981da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 16991da177e4SLinus Torvalds return n_ret_value; 17001da177e4SLinus Torvalds } 17011da177e4SLinus Torvalds 1702bd4c625cSLinus Torvalds static void truncate_directory(struct reiserfs_transaction_handle *th, 1703bd4c625cSLinus Torvalds struct inode *inode) 17041da177e4SLinus Torvalds { 17051da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 17061da177e4SLinus Torvalds if (inode->i_nlink) 17070030b645SJeff Mahoney reiserfs_error(inode->i_sb, "vs-5655", "link count != 0"); 17081da177e4SLinus Torvalds 17091da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET); 17101da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY); 17111da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 17121da177e4SLinus Torvalds reiserfs_update_sd(th, inode); 17131da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET); 17141da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA); 17151da177e4SLinus Torvalds } 17161da177e4SLinus Torvalds 17171da177e4SLinus Torvalds /* Truncate file to the new size. Note, this must be called with a transaction 17181da177e4SLinus Torvalds already started */ 1719bd4c625cSLinus Torvalds int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode, /* ->i_size contains new 17201da177e4SLinus Torvalds size */ 17211da177e4SLinus Torvalds struct page *page, /* up to date for last block */ 17221da177e4SLinus Torvalds int update_timestamps /* when it is called by 17231da177e4SLinus Torvalds file_release to convert 17241da177e4SLinus Torvalds the tail - no timestamps 17251da177e4SLinus Torvalds should be updated */ 1726bd4c625cSLinus Torvalds ) 1727bd4c625cSLinus Torvalds { 17281da177e4SLinus Torvalds INITIALIZE_PATH(s_search_path); /* Path to the current object item. */ 17291da177e4SLinus Torvalds struct item_head *p_le_ih; /* Pointer to an item header. */ 17301da177e4SLinus Torvalds struct cpu_key s_item_key; /* Key to search for a previous file item. */ 17311da177e4SLinus Torvalds loff_t n_file_size, /* Old file size. */ 17321da177e4SLinus Torvalds n_new_file_size; /* New file size. */ 17331da177e4SLinus Torvalds int n_deleted; /* Number of deleted or truncated bytes. */ 17341da177e4SLinus Torvalds int retval; 17351da177e4SLinus Torvalds int err = 0; 17361da177e4SLinus Torvalds 17371da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 1738bd4c625cSLinus Torvalds if (! 1739bd4c625cSLinus Torvalds (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) 1740bd4c625cSLinus Torvalds || S_ISLNK(p_s_inode->i_mode))) 17411da177e4SLinus Torvalds return 0; 17421da177e4SLinus Torvalds 17431da177e4SLinus Torvalds if (S_ISDIR(p_s_inode->i_mode)) { 17441da177e4SLinus Torvalds // deletion of directory - no need to update timestamps 17451da177e4SLinus Torvalds truncate_directory(th, p_s_inode); 17461da177e4SLinus Torvalds return 0; 17471da177e4SLinus Torvalds } 17481da177e4SLinus Torvalds 17491da177e4SLinus Torvalds /* Get new file size. */ 17501da177e4SLinus Torvalds n_new_file_size = p_s_inode->i_size; 17511da177e4SLinus Torvalds 17521da177e4SLinus Torvalds // FIXME: note, that key type is unimportant here 1753bd4c625cSLinus Torvalds make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode), 1754bd4c625cSLinus Torvalds TYPE_DIRECT, 3); 17551da177e4SLinus Torvalds 1756bd4c625cSLinus Torvalds retval = 1757bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1758bd4c625cSLinus Torvalds &s_search_path); 17591da177e4SLinus Torvalds if (retval == IO_ERROR) { 17600030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "vs-5657", 1761bd4c625cSLinus Torvalds "i/o failure occurred trying to truncate %K", 1762bd4c625cSLinus Torvalds &s_item_key); 17631da177e4SLinus Torvalds err = -EIO; 17641da177e4SLinus Torvalds goto out; 17651da177e4SLinus Torvalds } 17661da177e4SLinus Torvalds if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) { 17670030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "PAP-5660", 1768bd4c625cSLinus Torvalds "wrong result %d of search for %K", retval, 1769bd4c625cSLinus Torvalds &s_item_key); 17701da177e4SLinus Torvalds 17711da177e4SLinus Torvalds err = -EIO; 17721da177e4SLinus Torvalds goto out; 17731da177e4SLinus Torvalds } 17741da177e4SLinus Torvalds 17751da177e4SLinus Torvalds s_search_path.pos_in_item--; 17761da177e4SLinus Torvalds 17771da177e4SLinus Torvalds /* Get real file size (total length of all file items) */ 17781da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(&s_search_path); 17791da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 17801da177e4SLinus Torvalds n_file_size = 0; 17811da177e4SLinus Torvalds else { 17821da177e4SLinus Torvalds loff_t offset = le_ih_k_offset(p_le_ih); 1783bd4c625cSLinus Torvalds int bytes = 1784bd4c625cSLinus Torvalds op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize); 17851da177e4SLinus Torvalds 17861da177e4SLinus Torvalds /* this may mismatch with real file size: if last direct item 17871da177e4SLinus Torvalds had no padding zeros and last unformatted node had no free 17881da177e4SLinus Torvalds space, this file would have this file size */ 17891da177e4SLinus Torvalds n_file_size = offset + bytes - 1; 17901da177e4SLinus Torvalds } 17911da177e4SLinus Torvalds /* 17921da177e4SLinus Torvalds * are we doing a full truncate or delete, if so 17931da177e4SLinus Torvalds * kick in the reada code 17941da177e4SLinus Torvalds */ 17951da177e4SLinus Torvalds if (n_new_file_size == 0) 17961da177e4SLinus Torvalds s_search_path.reada = PATH_READA | PATH_READA_BACK; 17971da177e4SLinus Torvalds 17981da177e4SLinus Torvalds if (n_file_size == 0 || n_file_size < n_new_file_size) { 17991da177e4SLinus Torvalds goto update_and_out; 18001da177e4SLinus Torvalds } 18011da177e4SLinus Torvalds 18021da177e4SLinus Torvalds /* Update key to search for the last file item. */ 18031da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18041da177e4SLinus Torvalds 18051da177e4SLinus Torvalds do { 18061da177e4SLinus Torvalds /* Cut or delete file item. */ 1807bd4c625cSLinus Torvalds n_deleted = 1808bd4c625cSLinus Torvalds reiserfs_cut_from_item(th, &s_search_path, &s_item_key, 1809bd4c625cSLinus Torvalds p_s_inode, page, n_new_file_size); 18101da177e4SLinus Torvalds if (n_deleted < 0) { 181145b03d5eSJeff Mahoney reiserfs_warning(p_s_inode->i_sb, "vs-5665", 181245b03d5eSJeff Mahoney "reiserfs_cut_from_item failed"); 18131da177e4SLinus Torvalds reiserfs_check_path(&s_search_path); 18141da177e4SLinus Torvalds return 0; 18151da177e4SLinus Torvalds } 18161da177e4SLinus Torvalds 18171da177e4SLinus Torvalds RFALSE(n_deleted > n_file_size, 18181da177e4SLinus Torvalds "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K", 18191da177e4SLinus Torvalds n_deleted, n_file_size, &s_item_key); 18201da177e4SLinus Torvalds 18211da177e4SLinus Torvalds /* Change key to search the last file item. */ 18221da177e4SLinus Torvalds n_file_size -= n_deleted; 18231da177e4SLinus Torvalds 18241da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18251da177e4SLinus Torvalds 18261da177e4SLinus Torvalds /* While there are bytes to truncate and previous file item is presented in the tree. */ 18271da177e4SLinus Torvalds 18281da177e4SLinus Torvalds /* 18291da177e4SLinus Torvalds ** This loop could take a really long time, and could log 18301da177e4SLinus Torvalds ** many more blocks than a transaction can hold. So, we do a polite 18311da177e4SLinus Torvalds ** journal end here, and if the transaction needs ending, we make 18321da177e4SLinus Torvalds ** sure the file is consistent before ending the current trans 18331da177e4SLinus Torvalds ** and starting a new one 18341da177e4SLinus Torvalds */ 183523f9e0f8SAlexander Zarochentzev if (journal_transaction_should_end(th, 0) || 183623f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 18371da177e4SLinus Torvalds int orig_len_alloc = th->t_blocks_allocated; 1838*3cd6dbe6SJeff Mahoney pathrelse(&s_search_path); 18391da177e4SLinus Torvalds 18401da177e4SLinus Torvalds if (update_timestamps) { 1841bd4c625cSLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = 1842bd4c625cSLinus Torvalds CURRENT_TIME_SEC; 18431da177e4SLinus Torvalds } 18441da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 18451da177e4SLinus Torvalds 18461da177e4SLinus Torvalds err = journal_end(th, p_s_inode->i_sb, orig_len_alloc); 18471da177e4SLinus Torvalds if (err) 18481da177e4SLinus Torvalds goto out; 18491da177e4SLinus Torvalds err = journal_begin(th, p_s_inode->i_sb, 185023f9e0f8SAlexander Zarochentzev JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ; 18511da177e4SLinus Torvalds if (err) 18521da177e4SLinus Torvalds goto out; 18531da177e4SLinus Torvalds reiserfs_update_inode_transaction(p_s_inode); 18541da177e4SLinus Torvalds } 18551da177e4SLinus Torvalds } while (n_file_size > ROUND_UP(n_new_file_size) && 1856bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1857bd4c625cSLinus Torvalds &s_search_path) == POSITION_FOUND); 18581da177e4SLinus Torvalds 18591da177e4SLinus Torvalds RFALSE(n_file_size > ROUND_UP(n_new_file_size), 18601da177e4SLinus Torvalds "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d", 18611da177e4SLinus Torvalds n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid); 18621da177e4SLinus Torvalds 18631da177e4SLinus Torvalds update_and_out: 18641da177e4SLinus Torvalds if (update_timestamps) { 18651da177e4SLinus Torvalds // this is truncate, not file closing 18661da177e4SLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC; 18671da177e4SLinus Torvalds } 18681da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 18691da177e4SLinus Torvalds 18701da177e4SLinus Torvalds out: 18711da177e4SLinus Torvalds pathrelse(&s_search_path); 18721da177e4SLinus Torvalds return err; 18731da177e4SLinus Torvalds } 18741da177e4SLinus Torvalds 18751da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 18761da177e4SLinus Torvalds // this makes sure, that we __append__, not overwrite or add holes 1877fec6d055SJosef "Jeff" Sipek static void check_research_for_paste(struct treepath *path, 18781da177e4SLinus Torvalds const struct cpu_key *p_s_key) 18791da177e4SLinus Torvalds { 18801da177e4SLinus Torvalds struct item_head *found_ih = get_ih(path); 18811da177e4SLinus Torvalds 18821da177e4SLinus Torvalds if (is_direct_le_ih(found_ih)) { 1883bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1884bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1885bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1886bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1887bd4c625cSLinus Torvalds || op_bytes_number(found_ih, 1888bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1889bd4c625cSLinus Torvalds pos_in_item(path)) 1890c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5720", "found direct item " 1891c3a9c210SJeff Mahoney "%h or position (%d) does not match " 1892c3a9c210SJeff Mahoney "to key %K", found_ih, 1893c3a9c210SJeff Mahoney pos_in_item(path), p_s_key); 18941da177e4SLinus Torvalds } 18951da177e4SLinus Torvalds if (is_indirect_le_ih(found_ih)) { 1896bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1897bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1898bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1899bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1900bd4c625cSLinus Torvalds || I_UNFM_NUM(found_ih) != pos_in_item(path) 1901bd4c625cSLinus Torvalds || get_ih_free_space(found_ih) != 0) 1902c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5730", "found indirect " 1903c3a9c210SJeff Mahoney "item (%h) or position (%d) does not " 1904c3a9c210SJeff Mahoney "match to key (%K)", 19051da177e4SLinus Torvalds found_ih, pos_in_item(path), p_s_key); 19061da177e4SLinus Torvalds } 19071da177e4SLinus Torvalds } 19081da177e4SLinus Torvalds #endif /* config reiserfs check */ 19091da177e4SLinus Torvalds 19101da177e4SLinus Torvalds /* Paste bytes to the existing item. Returns bytes number pasted into the item. */ 1911fec6d055SJosef "Jeff" Sipek int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_search_path, /* Path to the pasted item. */ 19121da177e4SLinus Torvalds const struct cpu_key *p_s_key, /* Key to search for the needed item. */ 19131da177e4SLinus Torvalds struct inode *inode, /* Inode item belongs to */ 19141da177e4SLinus Torvalds const char *p_c_body, /* Pointer to the bytes to paste. */ 1915bd4c625cSLinus Torvalds int n_pasted_size) 1916bd4c625cSLinus Torvalds { /* Size of pasted bytes. */ 19171da177e4SLinus Torvalds struct tree_balance s_paste_balance; 19181da177e4SLinus Torvalds int retval; 19191da177e4SLinus Torvalds int fs_gen; 19201da177e4SLinus Torvalds 19211da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 19221da177e4SLinus Torvalds 19231da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 19241da177e4SLinus Torvalds 19251da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1926bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1927bd4c625cSLinus Torvalds "reiserquota paste_into_item(): allocating %u id=%u type=%c", 1928bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 1929bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 19301da177e4SLinus Torvalds #endif 19311da177e4SLinus Torvalds 19321da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) { 19331da177e4SLinus Torvalds pathrelse(p_s_search_path); 19341da177e4SLinus Torvalds return -EDQUOT; 19351da177e4SLinus Torvalds } 1936bd4c625cSLinus Torvalds init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, 1937bd4c625cSLinus Torvalds n_pasted_size); 19381da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 19391da177e4SLinus Torvalds s_paste_balance.key = p_s_key->on_disk_key; 19401da177e4SLinus Torvalds #endif 19411da177e4SLinus Torvalds 19421da177e4SLinus Torvalds /* DQUOT_* can schedule, must check before the fix_nodes */ 19431da177e4SLinus Torvalds if (fs_changed(fs_gen, inode->i_sb)) { 19441da177e4SLinus Torvalds goto search_again; 19451da177e4SLinus Torvalds } 19461da177e4SLinus Torvalds 1947bd4c625cSLinus Torvalds while ((retval = 1948bd4c625cSLinus Torvalds fix_nodes(M_PASTE, &s_paste_balance, NULL, 1949bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 19501da177e4SLinus Torvalds search_again: 19511da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 19521da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, paste_into_item_restarted); 1953bd4c625cSLinus Torvalds retval = 1954bd4c625cSLinus Torvalds search_for_position_by_key(th->t_super, p_s_key, 1955bd4c625cSLinus Torvalds p_s_search_path); 19561da177e4SLinus Torvalds if (retval == IO_ERROR) { 19571da177e4SLinus Torvalds retval = -EIO; 19581da177e4SLinus Torvalds goto error_out; 19591da177e4SLinus Torvalds } 19601da177e4SLinus Torvalds if (retval == POSITION_FOUND) { 196145b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "PAP-5710", 196245b03d5eSJeff Mahoney "entry or pasted byte (%K) exists", 1963bd4c625cSLinus Torvalds p_s_key); 19641da177e4SLinus Torvalds retval = -EEXIST; 19651da177e4SLinus Torvalds goto error_out; 19661da177e4SLinus Torvalds } 19671da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 19681da177e4SLinus Torvalds check_research_for_paste(p_s_search_path, p_s_key); 19691da177e4SLinus Torvalds #endif 19701da177e4SLinus Torvalds } 19711da177e4SLinus Torvalds 19721da177e4SLinus Torvalds /* Perform balancing after all resources are collected by fix_nodes, and 19731da177e4SLinus Torvalds accessing them will not risk triggering schedule. */ 19741da177e4SLinus Torvalds if (retval == CARRY_ON) { 19751da177e4SLinus Torvalds do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE); 19761da177e4SLinus Torvalds return 0; 19771da177e4SLinus Torvalds } 19781da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 19791da177e4SLinus Torvalds error_out: 19801da177e4SLinus Torvalds /* this also releases the path */ 19811da177e4SLinus Torvalds unfix_nodes(&s_paste_balance); 19821da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1983bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1984bd4c625cSLinus Torvalds "reiserquota paste_into_item(): freeing %u id=%u type=%c", 1985bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 1986bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 19871da177e4SLinus Torvalds #endif 19881da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size); 19891da177e4SLinus Torvalds return retval; 19901da177e4SLinus Torvalds } 19911da177e4SLinus Torvalds 19921da177e4SLinus Torvalds /* Insert new item into the buffer at the path. */ 1993fec6d055SJosef "Jeff" Sipek int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the inserteded item. */ 1994bd4c625cSLinus Torvalds const struct cpu_key *key, struct item_head *p_s_ih, /* Pointer to the item header to insert. */ 1995bd4c625cSLinus Torvalds struct inode *inode, const char *p_c_body) 1996bd4c625cSLinus Torvalds { /* Pointer to the bytes to insert. */ 19971da177e4SLinus Torvalds struct tree_balance s_ins_balance; 19981da177e4SLinus Torvalds int retval; 19991da177e4SLinus Torvalds int fs_gen = 0; 20001da177e4SLinus Torvalds int quota_bytes = 0; 20011da177e4SLinus Torvalds 20021da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 20031da177e4SLinus Torvalds 20041da177e4SLinus Torvalds if (inode) { /* Do we count quotas for item? */ 20051da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 20061da177e4SLinus Torvalds quota_bytes = ih_item_len(p_s_ih); 20071da177e4SLinus Torvalds 20081da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file has 20091da177e4SLinus Torvalds ** a tail, links are always tails, so there's no guessing needed 20101da177e4SLinus Torvalds */ 20111da177e4SLinus Torvalds if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) { 20121da177e4SLinus Torvalds quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE; 20131da177e4SLinus Torvalds } 20141da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2015bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2016bd4c625cSLinus Torvalds "reiserquota insert_item(): allocating %u id=%u type=%c", 2017bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 20181da177e4SLinus Torvalds #endif 20191da177e4SLinus Torvalds /* We can't dirty inode here. It would be immediately written but 20201da177e4SLinus Torvalds * appropriate stat item isn't inserted yet... */ 20211da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) { 20221da177e4SLinus Torvalds pathrelse(p_s_path); 20231da177e4SLinus Torvalds return -EDQUOT; 20241da177e4SLinus Torvalds } 20251da177e4SLinus Torvalds } 2026bd4c625cSLinus Torvalds init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, 2027bd4c625cSLinus Torvalds IH_SIZE + ih_item_len(p_s_ih)); 20281da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 20291da177e4SLinus Torvalds s_ins_balance.key = key->on_disk_key; 20301da177e4SLinus Torvalds #endif 20311da177e4SLinus Torvalds /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */ 20321da177e4SLinus Torvalds if (inode && fs_changed(fs_gen, inode->i_sb)) { 20331da177e4SLinus Torvalds goto search_again; 20341da177e4SLinus Torvalds } 20351da177e4SLinus Torvalds 2036bd4c625cSLinus Torvalds while ((retval = 2037bd4c625cSLinus Torvalds fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, 2038bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 20391da177e4SLinus Torvalds search_again: 20401da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 20411da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, insert_item_restarted); 20421da177e4SLinus Torvalds retval = search_item(th->t_super, key, p_s_path); 20431da177e4SLinus Torvalds if (retval == IO_ERROR) { 20441da177e4SLinus Torvalds retval = -EIO; 20451da177e4SLinus Torvalds goto error_out; 20461da177e4SLinus Torvalds } 20471da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 204845b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "PAP-5760", 2049bd4c625cSLinus Torvalds "key %K already exists in the tree", 2050bd4c625cSLinus Torvalds key); 20511da177e4SLinus Torvalds retval = -EEXIST; 20521da177e4SLinus Torvalds goto error_out; 20531da177e4SLinus Torvalds } 20541da177e4SLinus Torvalds } 20551da177e4SLinus Torvalds 20561da177e4SLinus Torvalds /* make balancing after all resources will be collected at a time */ 20571da177e4SLinus Torvalds if (retval == CARRY_ON) { 20581da177e4SLinus Torvalds do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT); 20591da177e4SLinus Torvalds return 0; 20601da177e4SLinus Torvalds } 20611da177e4SLinus Torvalds 20621da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 20631da177e4SLinus Torvalds error_out: 20641da177e4SLinus Torvalds /* also releases the path */ 20651da177e4SLinus Torvalds unfix_nodes(&s_ins_balance); 20661da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2067bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 2068bd4c625cSLinus Torvalds "reiserquota insert_item(): freeing %u id=%u type=%c", 2069bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 20701da177e4SLinus Torvalds #endif 20711da177e4SLinus Torvalds if (inode) 20721da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes); 20731da177e4SLinus Torvalds return retval; 20741da177e4SLinus Torvalds } 2075