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 * decrement_counters_in_path 271da177e4SLinus Torvalds * reiserfs_check_path 281da177e4SLinus Torvalds * pathrelse_and_restore 291da177e4SLinus Torvalds * pathrelse 301da177e4SLinus Torvalds * search_by_key_reada 311da177e4SLinus Torvalds * search_by_key 321da177e4SLinus Torvalds * search_for_position_by_key 331da177e4SLinus Torvalds * comp_items 341da177e4SLinus Torvalds * prepare_for_direct_item 351da177e4SLinus Torvalds * prepare_for_direntry_item 361da177e4SLinus Torvalds * prepare_for_delete_or_cut 371da177e4SLinus Torvalds * calc_deleted_bytes_number 381da177e4SLinus Torvalds * init_tb_struct 391da177e4SLinus Torvalds * padd_item 401da177e4SLinus Torvalds * reiserfs_delete_item 411da177e4SLinus Torvalds * reiserfs_delete_solid_item 421da177e4SLinus Torvalds * reiserfs_delete_object 431da177e4SLinus Torvalds * maybe_indirect_to_direct 441da177e4SLinus Torvalds * indirect_to_direct_roll_back 451da177e4SLinus Torvalds * reiserfs_cut_from_item 461da177e4SLinus Torvalds * truncate_directory 471da177e4SLinus Torvalds * reiserfs_do_truncate 481da177e4SLinus Torvalds * reiserfs_paste_into_item 491da177e4SLinus Torvalds * reiserfs_insert_item 501da177e4SLinus Torvalds */ 511da177e4SLinus Torvalds 521da177e4SLinus Torvalds #include <linux/time.h> 531da177e4SLinus Torvalds #include <linux/string.h> 541da177e4SLinus Torvalds #include <linux/pagemap.h> 551da177e4SLinus Torvalds #include <linux/reiserfs_fs.h> 561da177e4SLinus Torvalds #include <linux/buffer_head.h> 571da177e4SLinus Torvalds #include <linux/quotaops.h> 581da177e4SLinus Torvalds 591da177e4SLinus Torvalds /* Does the buffer contain a disk block which is in the tree. */ 601da177e4SLinus Torvalds inline int B_IS_IN_TREE(const struct buffer_head *p_s_bh) 611da177e4SLinus Torvalds { 621da177e4SLinus Torvalds 631da177e4SLinus Torvalds RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT, 641da177e4SLinus Torvalds "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh); 651da177e4SLinus Torvalds 661da177e4SLinus Torvalds return (B_LEVEL(p_s_bh) != FREE_LEVEL); 671da177e4SLinus Torvalds } 681da177e4SLinus Torvalds 691da177e4SLinus Torvalds // 701da177e4SLinus Torvalds // to gets item head in le form 711da177e4SLinus Torvalds // 721da177e4SLinus Torvalds inline void copy_item_head(struct item_head *p_v_to, 731da177e4SLinus Torvalds const struct item_head *p_v_from) 741da177e4SLinus Torvalds { 751da177e4SLinus Torvalds memcpy(p_v_to, p_v_from, IH_SIZE); 761da177e4SLinus Torvalds } 771da177e4SLinus Torvalds 781da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 791da177e4SLinus Torvalds form. k2 is pointer to cpu variable. For key of items of the same 801da177e4SLinus Torvalds object this returns 0. 811da177e4SLinus Torvalds Returns: -1 if key1 < key2 821da177e4SLinus Torvalds 0 if key1 == key2 831da177e4SLinus Torvalds 1 if key1 > key2 */ 841da177e4SLinus Torvalds inline int comp_short_keys(const struct reiserfs_key *le_key, 851da177e4SLinus Torvalds const struct cpu_key *cpu_key) 861da177e4SLinus Torvalds { 876b9f5829SAl Viro __u32 n; 886b9f5829SAl Viro n = le32_to_cpu(le_key->k_dir_id); 896b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_dir_id) 901da177e4SLinus Torvalds return -1; 916b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_dir_id) 921da177e4SLinus Torvalds return 1; 936b9f5829SAl Viro n = le32_to_cpu(le_key->k_objectid); 946b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_objectid) 956b9f5829SAl Viro return -1; 966b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_objectid) 976b9f5829SAl Viro return 1; 981da177e4SLinus Torvalds return 0; 991da177e4SLinus Torvalds } 1001da177e4SLinus Torvalds 1011da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 1021da177e4SLinus Torvalds form. k2 is pointer to cpu variable. 1031da177e4SLinus Torvalds Compare keys using all 4 key fields. 1041da177e4SLinus Torvalds Returns: -1 if key1 < key2 0 1051da177e4SLinus Torvalds if key1 = key2 1 if key1 > key2 */ 106bd4c625cSLinus Torvalds static inline int comp_keys(const struct reiserfs_key *le_key, 107bd4c625cSLinus Torvalds const struct cpu_key *cpu_key) 1081da177e4SLinus Torvalds { 1091da177e4SLinus Torvalds int retval; 1101da177e4SLinus Torvalds 1111da177e4SLinus Torvalds retval = comp_short_keys(le_key, cpu_key); 1121da177e4SLinus Torvalds if (retval) 1131da177e4SLinus Torvalds return retval; 114bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) < 115bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1161da177e4SLinus Torvalds return -1; 117bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) > 118bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1191da177e4SLinus Torvalds return 1; 1201da177e4SLinus Torvalds 1211da177e4SLinus Torvalds if (cpu_key->key_length == 3) 1221da177e4SLinus Torvalds return 0; 1231da177e4SLinus Torvalds 1241da177e4SLinus Torvalds /* this part is needed only when tail conversion is in progress */ 125bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) < 126bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1271da177e4SLinus Torvalds return -1; 1281da177e4SLinus Torvalds 129bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) > 130bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1311da177e4SLinus Torvalds return 1; 1321da177e4SLinus Torvalds 1331da177e4SLinus Torvalds return 0; 1341da177e4SLinus Torvalds } 1351da177e4SLinus Torvalds 136bd4c625cSLinus Torvalds inline int comp_short_le_keys(const struct reiserfs_key *key1, 137bd4c625cSLinus Torvalds const struct reiserfs_key *key2) 1381da177e4SLinus Torvalds { 1391da177e4SLinus Torvalds __u32 *p_s_1_u32, *p_s_2_u32; 1401da177e4SLinus Torvalds int n_key_length = REISERFS_SHORT_KEY_LEN; 1411da177e4SLinus Torvalds 1421da177e4SLinus Torvalds p_s_1_u32 = (__u32 *) key1; 1431da177e4SLinus Torvalds p_s_2_u32 = (__u32 *) key2; 1441da177e4SLinus Torvalds for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) { 1451da177e4SLinus Torvalds if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32)) 1461da177e4SLinus Torvalds return -1; 1471da177e4SLinus Torvalds if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32)) 1481da177e4SLinus Torvalds return 1; 1491da177e4SLinus Torvalds } 1501da177e4SLinus Torvalds return 0; 1511da177e4SLinus Torvalds } 1521da177e4SLinus Torvalds 1531da177e4SLinus Torvalds inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from) 1541da177e4SLinus Torvalds { 1556b9f5829SAl Viro int version; 1561da177e4SLinus Torvalds to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id); 1571da177e4SLinus Torvalds to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid); 1581da177e4SLinus Torvalds 1591da177e4SLinus Torvalds // find out version of the key 1606b9f5829SAl Viro version = le_key_version(from); 1616b9f5829SAl Viro to->version = version; 1626b9f5829SAl Viro to->on_disk_key.k_offset = le_key_k_offset(version, from); 1636b9f5829SAl Viro to->on_disk_key.k_type = le_key_k_type(version, from); 1641da177e4SLinus Torvalds } 1651da177e4SLinus Torvalds 1661da177e4SLinus Torvalds // this does not say which one is bigger, it only returns 1 if keys 1671da177e4SLinus Torvalds // are not equal, 0 otherwise 168bd4c625cSLinus Torvalds inline int comp_le_keys(const struct reiserfs_key *k1, 169bd4c625cSLinus Torvalds const struct reiserfs_key *k2) 1701da177e4SLinus Torvalds { 1711da177e4SLinus Torvalds return memcmp(k1, k2, sizeof(struct reiserfs_key)); 1721da177e4SLinus Torvalds } 1731da177e4SLinus Torvalds 1741da177e4SLinus Torvalds /************************************************************************** 1751da177e4SLinus Torvalds * Binary search toolkit function * 1761da177e4SLinus Torvalds * Search for an item in the array by the item key * 1771da177e4SLinus Torvalds * Returns: 1 if found, 0 if not found; * 1781da177e4SLinus Torvalds * *p_n_pos = number of the searched element if found, else the * 1791da177e4SLinus Torvalds * number of the first element that is larger than p_v_key. * 1801da177e4SLinus Torvalds **************************************************************************/ 1811da177e4SLinus Torvalds /* For those not familiar with binary search: n_lbound is the leftmost item that it 1821da177e4SLinus Torvalds could be, n_rbound the rightmost item that it could be. We examine the item 1831da177e4SLinus Torvalds halfway between n_lbound and n_rbound, and that tells us either that we can increase 1841da177e4SLinus Torvalds n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that 1851da177e4SLinus Torvalds there are no possible items, and we have not found it. With each examination we 1861da177e4SLinus Torvalds cut the number of possible items it could be by one more than half rounded down, 1871da177e4SLinus Torvalds or we find it. */ 188bd4c625cSLinus Torvalds static inline int bin_search(const void *p_v_key, /* Key to search for. */ 1891da177e4SLinus Torvalds const void *p_v_base, /* First item in the array. */ 1901da177e4SLinus Torvalds int p_n_num, /* Number of items in the array. */ 1911da177e4SLinus Torvalds int p_n_width, /* Item size in the array. 1921da177e4SLinus Torvalds searched. Lest the reader be 1931da177e4SLinus Torvalds confused, note that this is crafted 1941da177e4SLinus Torvalds as a general function, and when it 1951da177e4SLinus Torvalds is applied specifically to the array 1961da177e4SLinus Torvalds of item headers in a node, p_n_width 1971da177e4SLinus Torvalds is actually the item header size not 1981da177e4SLinus Torvalds the item size. */ 1991da177e4SLinus Torvalds int *p_n_pos /* Number of the searched for element. */ 200bd4c625cSLinus Torvalds ) 201bd4c625cSLinus Torvalds { 2021da177e4SLinus Torvalds int n_rbound, n_lbound, n_j; 2031da177e4SLinus Torvalds 204bd4c625cSLinus Torvalds for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2; 205bd4c625cSLinus Torvalds n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2) 206bd4c625cSLinus Torvalds switch (comp_keys 207bd4c625cSLinus Torvalds ((struct reiserfs_key *)((char *)p_v_base + 208bd4c625cSLinus Torvalds n_j * p_n_width), 209bd4c625cSLinus Torvalds (struct cpu_key *)p_v_key)) { 210bd4c625cSLinus Torvalds case -1: 211bd4c625cSLinus Torvalds n_lbound = n_j + 1; 212bd4c625cSLinus Torvalds continue; 213bd4c625cSLinus Torvalds case 1: 214bd4c625cSLinus Torvalds n_rbound = n_j - 1; 215bd4c625cSLinus Torvalds continue; 216bd4c625cSLinus Torvalds case 0: 217bd4c625cSLinus Torvalds *p_n_pos = n_j; 218bd4c625cSLinus Torvalds return ITEM_FOUND; /* Key found in the array. */ 2191da177e4SLinus Torvalds } 2201da177e4SLinus Torvalds 2211da177e4SLinus Torvalds /* bin_search did not find given key, it returns position of key, 2221da177e4SLinus Torvalds that is minimal and greater than the given one. */ 2231da177e4SLinus Torvalds *p_n_pos = n_lbound; 2241da177e4SLinus Torvalds return ITEM_NOT_FOUND; 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds 2271da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 2281da177e4SLinus Torvalds extern struct tree_balance *cur_tb; 2291da177e4SLinus Torvalds #endif 2301da177e4SLinus Torvalds 2311da177e4SLinus Torvalds /* Minimal possible key. It is never in the tree. */ 2321da177e4SLinus Torvalds const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} }; 2331da177e4SLinus Torvalds 2341da177e4SLinus Torvalds /* Maximal possible key. It is never in the tree. */ 23552c1da39SAdrian Bunk static const struct reiserfs_key MAX_KEY = { 2363e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2373e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2383e8962beSAl Viro {{__constant_cpu_to_le32(0xffffffff), 2393e8962beSAl Viro __constant_cpu_to_le32(0xffffffff)},} 2403e8962beSAl Viro }; 2411da177e4SLinus Torvalds 2421da177e4SLinus Torvalds /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom 2431da177e4SLinus Torvalds of the path, and going upwards. We must check the path's validity at each step. If the key is not in 2441da177e4SLinus Torvalds the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this 2451da177e4SLinus Torvalds case we return a special key, either MIN_KEY or MAX_KEY. */ 246fec6d055SJosef "Jeff" Sipek static inline const struct reiserfs_key *get_lkey(const struct treepath 247bd4c625cSLinus Torvalds *p_s_chk_path, 248bd4c625cSLinus Torvalds const struct super_block 249bd4c625cSLinus Torvalds *p_s_sb) 250bd4c625cSLinus Torvalds { 2511da177e4SLinus Torvalds int n_position, n_path_offset = p_s_chk_path->path_length; 2521da177e4SLinus Torvalds struct buffer_head *p_s_parent; 2531da177e4SLinus Torvalds 2541da177e4SLinus Torvalds RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET, 2551da177e4SLinus Torvalds "PAP-5010: invalid offset in the path"); 2561da177e4SLinus Torvalds 2571da177e4SLinus Torvalds /* While not higher in path than first element. */ 2581da177e4SLinus Torvalds while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 2591da177e4SLinus Torvalds 260bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 261bd4c625cSLinus Torvalds (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)), 2621da177e4SLinus Torvalds "PAP-5020: parent is not uptodate"); 2631da177e4SLinus Torvalds 2641da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 265bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 266bd4c625cSLinus Torvalds (p_s_parent = 267bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) 2681da177e4SLinus Torvalds return &MAX_KEY; 2691da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 270bd4c625cSLinus Torvalds if ((n_position = 271bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_chk_path, 272bd4c625cSLinus Torvalds n_path_offset)) > 273bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_parent)) 2741da177e4SLinus Torvalds return &MAX_KEY; 2751da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 2761da177e4SLinus Torvalds if (B_N_CHILD_NUM(p_s_parent, n_position) != 277bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, 278bd4c625cSLinus Torvalds n_path_offset + 1)->b_blocknr) 2791da177e4SLinus Torvalds return &MAX_KEY; 2801da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not equal to zero. */ 2811da177e4SLinus Torvalds if (n_position) 2821da177e4SLinus Torvalds return B_N_PDELIM_KEY(p_s_parent, n_position - 1); 2831da177e4SLinus Torvalds } 2841da177e4SLinus Torvalds /* Return MIN_KEY if we are in the root of the buffer tree. */ 285bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 286bd4c625cSLinus Torvalds b_blocknr == SB_ROOT_BLOCK(p_s_sb)) 2871da177e4SLinus Torvalds return &MIN_KEY; 2881da177e4SLinus Torvalds return &MAX_KEY; 2891da177e4SLinus Torvalds } 2901da177e4SLinus Torvalds 2911da177e4SLinus Torvalds /* Get delimiting key of the buffer at the path and its right neighbor. */ 292fec6d055SJosef "Jeff" Sipek inline const struct reiserfs_key *get_rkey(const struct treepath *p_s_chk_path, 293bd4c625cSLinus Torvalds const struct super_block *p_s_sb) 294bd4c625cSLinus Torvalds { 295bd4c625cSLinus Torvalds int n_position, n_path_offset = p_s_chk_path->path_length; 2961da177e4SLinus Torvalds struct buffer_head *p_s_parent; 2971da177e4SLinus Torvalds 2981da177e4SLinus Torvalds RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET, 2991da177e4SLinus Torvalds "PAP-5030: invalid offset in the path"); 3001da177e4SLinus Torvalds 3011da177e4SLinus Torvalds while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 3021da177e4SLinus Torvalds 303bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 304bd4c625cSLinus Torvalds (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)), 3051da177e4SLinus Torvalds "PAP-5040: parent is not uptodate"); 3061da177e4SLinus Torvalds 3071da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 308bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 309bd4c625cSLinus Torvalds (p_s_parent = 310bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) 3111da177e4SLinus Torvalds return &MIN_KEY; 3121da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 313bd4c625cSLinus Torvalds if ((n_position = 314bd4c625cSLinus Torvalds PATH_OFFSET_POSITION(p_s_chk_path, 315bd4c625cSLinus Torvalds n_path_offset)) > 316bd4c625cSLinus Torvalds B_NR_ITEMS(p_s_parent)) 3171da177e4SLinus Torvalds return &MIN_KEY; 3181da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 3191da177e4SLinus Torvalds if (B_N_CHILD_NUM(p_s_parent, n_position) != 320bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER(p_s_chk_path, 321bd4c625cSLinus Torvalds n_path_offset + 1)->b_blocknr) 3221da177e4SLinus Torvalds return &MIN_KEY; 3231da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not the last one. */ 3241da177e4SLinus Torvalds if (n_position != B_NR_ITEMS(p_s_parent)) 3251da177e4SLinus Torvalds return B_N_PDELIM_KEY(p_s_parent, n_position); 3261da177e4SLinus Torvalds } 3271da177e4SLinus Torvalds /* Return MAX_KEY if we are in the root of the buffer tree. */ 328bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 329bd4c625cSLinus Torvalds b_blocknr == SB_ROOT_BLOCK(p_s_sb)) 3301da177e4SLinus Torvalds return &MAX_KEY; 3311da177e4SLinus Torvalds return &MIN_KEY; 3321da177e4SLinus Torvalds } 3331da177e4SLinus Torvalds 3341da177e4SLinus Torvalds /* Check whether a key is contained in the tree rooted from a buffer at a path. */ 3351da177e4SLinus Torvalds /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in 3361da177e4SLinus Torvalds the path. These delimiting keys are stored at least one level above that buffer in the tree. If the 3371da177e4SLinus Torvalds buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in 3381da177e4SLinus Torvalds this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */ 339fec6d055SJosef "Jeff" Sipek static inline int key_in_buffer(struct treepath *p_s_chk_path, /* Path which should be checked. */ 3401da177e4SLinus Torvalds const struct cpu_key *p_s_key, /* Key which should be checked. */ 3411da177e4SLinus Torvalds struct super_block *p_s_sb /* Super block pointer. */ 342bd4c625cSLinus Torvalds ) 343bd4c625cSLinus Torvalds { 3441da177e4SLinus Torvalds 345bd4c625cSLinus Torvalds RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET 346bd4c625cSLinus Torvalds || p_s_chk_path->path_length > MAX_HEIGHT, 3471da177e4SLinus Torvalds "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)", 3481da177e4SLinus Torvalds p_s_key, p_s_chk_path->path_length); 3491da177e4SLinus Torvalds RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev, 3501da177e4SLinus Torvalds "PAP-5060: device must not be NODEV"); 3511da177e4SLinus Torvalds 3521da177e4SLinus Torvalds if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1) 3531da177e4SLinus Torvalds /* left delimiting key is bigger, that the key we look for */ 3541da177e4SLinus Torvalds return 0; 3551da177e4SLinus Torvalds // if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 ) 3561da177e4SLinus Torvalds if (comp_keys(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1) 3571da177e4SLinus Torvalds /* p_s_key must be less than right delimitiing key */ 3581da177e4SLinus Torvalds return 0; 3591da177e4SLinus Torvalds return 1; 3601da177e4SLinus Torvalds } 3611da177e4SLinus Torvalds 362bd4c625cSLinus Torvalds inline void decrement_bcount(struct buffer_head *p_s_bh) 363bd4c625cSLinus Torvalds { 3641da177e4SLinus Torvalds if (p_s_bh) { 3651da177e4SLinus Torvalds if (atomic_read(&(p_s_bh->b_count))) { 3661da177e4SLinus Torvalds put_bh(p_s_bh); 3671da177e4SLinus Torvalds return; 3681da177e4SLinus Torvalds } 369c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5070", 370c3a9c210SJeff Mahoney "trying to free free buffer %b", p_s_bh); 3711da177e4SLinus Torvalds } 3721da177e4SLinus Torvalds } 3731da177e4SLinus Torvalds 3741da177e4SLinus Torvalds /* Decrement b_count field of the all buffers in the path. */ 375fec6d055SJosef "Jeff" Sipek void decrement_counters_in_path(struct treepath *p_s_search_path) 376bd4c625cSLinus Torvalds { 3771da177e4SLinus Torvalds int n_path_offset = p_s_search_path->path_length; 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET || 3801da177e4SLinus Torvalds n_path_offset > EXTENDED_MAX_HEIGHT - 1, 3811da177e4SLinus Torvalds "PAP-5080: invalid path offset of %d", n_path_offset); 3821da177e4SLinus Torvalds 3831da177e4SLinus Torvalds while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { 3841da177e4SLinus Torvalds struct buffer_head *bh; 3851da177e4SLinus Torvalds 3861da177e4SLinus Torvalds bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--); 3871da177e4SLinus Torvalds decrement_bcount(bh); 3881da177e4SLinus Torvalds } 3891da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 3901da177e4SLinus Torvalds } 3911da177e4SLinus Torvalds 392fec6d055SJosef "Jeff" Sipek int reiserfs_check_path(struct treepath *p) 393bd4c625cSLinus Torvalds { 3941da177e4SLinus Torvalds RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET, 3951da177e4SLinus Torvalds "path not properly relsed"); 3961da177e4SLinus Torvalds return 0; 3971da177e4SLinus Torvalds } 3981da177e4SLinus Torvalds 3991da177e4SLinus Torvalds /* Release all buffers in the path. Restore dirty bits clean 4001da177e4SLinus Torvalds ** when preparing the buffer for the log 4011da177e4SLinus Torvalds ** 4021da177e4SLinus Torvalds ** only called from fix_nodes() 4031da177e4SLinus Torvalds */ 404fec6d055SJosef "Jeff" Sipek void pathrelse_and_restore(struct super_block *s, struct treepath *p_s_search_path) 405bd4c625cSLinus Torvalds { 4061da177e4SLinus Torvalds int n_path_offset = p_s_search_path->path_length; 4071da177e4SLinus Torvalds 4081da177e4SLinus Torvalds RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 4091da177e4SLinus Torvalds "clm-4000: invalid path offset"); 4101da177e4SLinus Torvalds 4111da177e4SLinus Torvalds while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { 412bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer(s, 413bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER 414bd4c625cSLinus Torvalds (p_s_search_path, 4151da177e4SLinus Torvalds n_path_offset)); 4161da177e4SLinus Torvalds brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--)); 4171da177e4SLinus Torvalds } 4181da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 4191da177e4SLinus Torvalds } 4201da177e4SLinus Torvalds 4211da177e4SLinus Torvalds /* Release all buffers in the path. */ 422fec6d055SJosef "Jeff" Sipek void pathrelse(struct treepath *p_s_search_path) 423bd4c625cSLinus Torvalds { 4241da177e4SLinus Torvalds int n_path_offset = p_s_search_path->path_length; 4251da177e4SLinus Torvalds 4261da177e4SLinus Torvalds RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 4271da177e4SLinus Torvalds "PAP-5090: invalid path offset"); 4281da177e4SLinus Torvalds 4291da177e4SLinus Torvalds while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) 4301da177e4SLinus Torvalds brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--)); 4311da177e4SLinus Torvalds 4321da177e4SLinus Torvalds p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 4331da177e4SLinus Torvalds } 4341da177e4SLinus Torvalds 4351da177e4SLinus Torvalds static int is_leaf(char *buf, int blocksize, struct buffer_head *bh) 4361da177e4SLinus Torvalds { 4371da177e4SLinus Torvalds struct block_head *blkh; 4381da177e4SLinus Torvalds struct item_head *ih; 4391da177e4SLinus Torvalds int used_space; 4401da177e4SLinus Torvalds int prev_location; 4411da177e4SLinus Torvalds int i; 4421da177e4SLinus Torvalds int nr; 4431da177e4SLinus Torvalds 4441da177e4SLinus Torvalds blkh = (struct block_head *)buf; 4451da177e4SLinus Torvalds if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) { 44645b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5080", 44745b03d5eSJeff Mahoney "this should be caught earlier"); 4481da177e4SLinus Torvalds return 0; 4491da177e4SLinus Torvalds } 4501da177e4SLinus Torvalds 4511da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 4521da177e4SLinus Torvalds if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) { 4531da177e4SLinus Torvalds /* item number is too big or too small */ 45445b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5081", 45545b03d5eSJeff Mahoney "nr_item seems wrong: %z", bh); 4561da177e4SLinus Torvalds return 0; 4571da177e4SLinus Torvalds } 4581da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1; 4591da177e4SLinus Torvalds used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih)); 4601da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 4611da177e4SLinus Torvalds /* free space does not match to calculated amount of use space */ 46245b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5082", 46345b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 4641da177e4SLinus Torvalds return 0; 4651da177e4SLinus Torvalds } 4661da177e4SLinus Torvalds // FIXME: it is_leaf will hit performance too much - we may have 4671da177e4SLinus Torvalds // return 1 here 4681da177e4SLinus Torvalds 4691da177e4SLinus Torvalds /* check tables of item heads */ 4701da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE); 4711da177e4SLinus Torvalds prev_location = blocksize; 4721da177e4SLinus Torvalds for (i = 0; i < nr; i++, ih++) { 4731da177e4SLinus Torvalds if (le_ih_k_type(ih) == TYPE_ANY) { 47445b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5083", 47545b03d5eSJeff Mahoney "wrong item type for item %h", 476bd4c625cSLinus Torvalds ih); 4771da177e4SLinus Torvalds return 0; 4781da177e4SLinus Torvalds } 479bd4c625cSLinus Torvalds if (ih_location(ih) >= blocksize 480bd4c625cSLinus Torvalds || ih_location(ih) < IH_SIZE * nr) { 48145b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5084", 48245b03d5eSJeff Mahoney "item location seems wrong: %h", 483bd4c625cSLinus Torvalds ih); 4841da177e4SLinus Torvalds return 0; 4851da177e4SLinus Torvalds } 486bd4c625cSLinus Torvalds if (ih_item_len(ih) < 1 487bd4c625cSLinus Torvalds || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) { 48845b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5085", 48945b03d5eSJeff Mahoney "item length seems wrong: %h", 490bd4c625cSLinus Torvalds ih); 4911da177e4SLinus Torvalds return 0; 4921da177e4SLinus Torvalds } 4931da177e4SLinus Torvalds if (prev_location - ih_location(ih) != ih_item_len(ih)) { 49445b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5086", 49545b03d5eSJeff Mahoney "item location seems wrong " 49645b03d5eSJeff Mahoney "(second one): %h", ih); 4971da177e4SLinus Torvalds return 0; 4981da177e4SLinus Torvalds } 4991da177e4SLinus Torvalds prev_location = ih_location(ih); 5001da177e4SLinus Torvalds } 5011da177e4SLinus Torvalds 5021da177e4SLinus Torvalds // one may imagine much more checks 5031da177e4SLinus Torvalds return 1; 5041da177e4SLinus Torvalds } 5051da177e4SLinus Torvalds 5061da177e4SLinus Torvalds /* returns 1 if buf looks like an internal node, 0 otherwise */ 5071da177e4SLinus Torvalds static int is_internal(char *buf, int blocksize, struct buffer_head *bh) 5081da177e4SLinus Torvalds { 5091da177e4SLinus Torvalds struct block_head *blkh; 5101da177e4SLinus Torvalds int nr; 5111da177e4SLinus Torvalds int used_space; 5121da177e4SLinus Torvalds 5131da177e4SLinus Torvalds blkh = (struct block_head *)buf; 5141da177e4SLinus Torvalds nr = blkh_level(blkh); 5151da177e4SLinus Torvalds if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) { 5161da177e4SLinus Torvalds /* this level is not possible for internal nodes */ 51745b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5087", 51845b03d5eSJeff Mahoney "this should be caught earlier"); 5191da177e4SLinus Torvalds return 0; 5201da177e4SLinus Torvalds } 5211da177e4SLinus Torvalds 5221da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 5231da177e4SLinus Torvalds if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) { 5241da177e4SLinus Torvalds /* for internal which is not root we might check min number of keys */ 52545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5088", 52645b03d5eSJeff Mahoney "number of key seems wrong: %z", bh); 5271da177e4SLinus Torvalds return 0; 5281da177e4SLinus Torvalds } 5291da177e4SLinus Torvalds 5301da177e4SLinus Torvalds used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1); 5311da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 53245b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5089", 53345b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 5341da177e4SLinus Torvalds return 0; 5351da177e4SLinus Torvalds } 5361da177e4SLinus Torvalds // one may imagine much more checks 5371da177e4SLinus Torvalds return 1; 5381da177e4SLinus Torvalds } 5391da177e4SLinus Torvalds 5401da177e4SLinus Torvalds // make sure that bh contains formatted node of reiserfs tree of 5411da177e4SLinus Torvalds // 'level'-th level 5421da177e4SLinus Torvalds static int is_tree_node(struct buffer_head *bh, int level) 5431da177e4SLinus Torvalds { 5441da177e4SLinus Torvalds if (B_LEVEL(bh) != level) { 54545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5090", "node level %d does " 54645b03d5eSJeff Mahoney "not match to the expected one %d", 5471da177e4SLinus Torvalds B_LEVEL(bh), level); 5481da177e4SLinus Torvalds return 0; 5491da177e4SLinus Torvalds } 5501da177e4SLinus Torvalds if (level == DISK_LEAF_NODE_LEVEL) 5511da177e4SLinus Torvalds return is_leaf(bh->b_data, bh->b_size, bh); 5521da177e4SLinus Torvalds 5531da177e4SLinus Torvalds return is_internal(bh->b_data, bh->b_size, bh); 5541da177e4SLinus Torvalds } 5551da177e4SLinus Torvalds 5561da177e4SLinus Torvalds #define SEARCH_BY_KEY_READA 16 5571da177e4SLinus Torvalds 5581da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 5591da177e4SLinus Torvalds static void search_by_key_reada(struct super_block *s, 5601da177e4SLinus Torvalds struct buffer_head **bh, 5613ee16670SJeff Mahoney b_blocknr_t *b, int num) 5621da177e4SLinus Torvalds { 5631da177e4SLinus Torvalds int i, j; 5641da177e4SLinus Torvalds 5651da177e4SLinus Torvalds for (i = 0; i < num; i++) { 5661da177e4SLinus Torvalds bh[i] = sb_getblk(s, b[i]); 5671da177e4SLinus Torvalds } 5681da177e4SLinus Torvalds for (j = 0; j < i; j++) { 5691da177e4SLinus Torvalds /* 5701da177e4SLinus Torvalds * note, this needs attention if we are getting rid of the BKL 5711da177e4SLinus Torvalds * you have to make sure the prepared bit isn't set on this buffer 5721da177e4SLinus Torvalds */ 5731da177e4SLinus Torvalds if (!buffer_uptodate(bh[j])) 5741da177e4SLinus Torvalds ll_rw_block(READA, 1, bh + j); 5751da177e4SLinus Torvalds brelse(bh[j]); 5761da177e4SLinus Torvalds } 5771da177e4SLinus Torvalds } 5781da177e4SLinus Torvalds 5791da177e4SLinus Torvalds /************************************************************************** 5801da177e4SLinus Torvalds * Algorithm SearchByKey * 5811da177e4SLinus Torvalds * look for item in the Disk S+Tree by its key * 5821da177e4SLinus Torvalds * Input: p_s_sb - super block * 5831da177e4SLinus Torvalds * p_s_key - pointer to the key to search * 5841da177e4SLinus Torvalds * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR * 5851da177e4SLinus Torvalds * p_s_search_path - path from the root to the needed leaf * 5861da177e4SLinus Torvalds **************************************************************************/ 5871da177e4SLinus Torvalds 5881da177e4SLinus Torvalds /* This function fills up the path from the root to the leaf as it 5891da177e4SLinus Torvalds descends the tree looking for the key. It uses reiserfs_bread to 5901da177e4SLinus Torvalds try to find buffers in the cache given their block number. If it 5911da177e4SLinus Torvalds does not find them in the cache it reads them from disk. For each 5921da177e4SLinus Torvalds node search_by_key finds using reiserfs_bread it then uses 5931da177e4SLinus Torvalds bin_search to look through that node. bin_search will find the 5941da177e4SLinus Torvalds position of the block_number of the next node if it is looking 5951da177e4SLinus Torvalds through an internal node. If it is looking through a leaf node 5961da177e4SLinus Torvalds bin_search will find the position of the item which has key either 5971da177e4SLinus Torvalds equal to given key, or which is the maximal key less than the given 5981da177e4SLinus Torvalds key. search_by_key returns a path that must be checked for the 5991da177e4SLinus Torvalds correctness of the top of the path but need not be checked for the 6001da177e4SLinus Torvalds correctness of the bottom of the path */ 6011da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 602bd4c625cSLinus Torvalds int search_by_key(struct super_block *p_s_sb, const struct cpu_key *p_s_key, /* Key to search. */ 603fec6d055SJosef "Jeff" Sipek struct treepath *p_s_search_path,/* This structure was 6041da177e4SLinus Torvalds allocated and initialized 6051da177e4SLinus Torvalds by the calling 6061da177e4SLinus Torvalds function. It is filled up 6071da177e4SLinus Torvalds by this function. */ 6081da177e4SLinus Torvalds int n_stop_level /* How far down the tree to search. To 6091da177e4SLinus Torvalds stop at leaf level - set to 6101da177e4SLinus Torvalds DISK_LEAF_NODE_LEVEL */ 611bd4c625cSLinus Torvalds ) 612bd4c625cSLinus Torvalds { 6133ee16670SJeff Mahoney b_blocknr_t n_block_number; 6141da177e4SLinus Torvalds int expected_level; 6151da177e4SLinus Torvalds struct buffer_head *p_s_bh; 6161da177e4SLinus Torvalds struct path_element *p_s_last_element; 6171da177e4SLinus Torvalds int n_node_level, n_retval; 6181da177e4SLinus Torvalds int right_neighbor_of_leaf_node; 6191da177e4SLinus Torvalds int fs_gen; 6201da177e4SLinus Torvalds struct buffer_head *reada_bh[SEARCH_BY_KEY_READA]; 6213ee16670SJeff Mahoney b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA]; 6221da177e4SLinus Torvalds int reada_count = 0; 6231da177e4SLinus Torvalds 6241da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 6251da177e4SLinus Torvalds int n_repeat_counter = 0; 6261da177e4SLinus Torvalds #endif 6271da177e4SLinus Torvalds 6281da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, search_by_key); 6291da177e4SLinus Torvalds 6301da177e4SLinus Torvalds /* As we add each node to a path we increase its count. This means that 6311da177e4SLinus Torvalds we must be careful to release all nodes in a path before we either 6321da177e4SLinus Torvalds discard the path struct or re-use the path struct, as we do here. */ 6331da177e4SLinus Torvalds 6341da177e4SLinus Torvalds decrement_counters_in_path(p_s_search_path); 6351da177e4SLinus Torvalds 6361da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6371da177e4SLinus Torvalds 6381da177e4SLinus Torvalds /* With each iteration of this loop we search through the items in the 6391da177e4SLinus Torvalds current node, and calculate the next current node(next path element) 6401da177e4SLinus Torvalds for the next iteration of this loop.. */ 6411da177e4SLinus Torvalds n_block_number = SB_ROOT_BLOCK(p_s_sb); 6421da177e4SLinus Torvalds expected_level = -1; 6431da177e4SLinus Torvalds while (1) { 6441da177e4SLinus Torvalds 6451da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 6461da177e4SLinus Torvalds if (!(++n_repeat_counter % 50000)) 64745b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "PAP-5100", 64845b03d5eSJeff Mahoney "%s: there were %d iterations of " 64945b03d5eSJeff Mahoney "while loop looking for key %K", 650bd4c625cSLinus Torvalds current->comm, n_repeat_counter, 651bd4c625cSLinus Torvalds p_s_key); 6521da177e4SLinus Torvalds #endif 6531da177e4SLinus Torvalds 6541da177e4SLinus Torvalds /* prep path to have another element added to it. */ 655bd4c625cSLinus Torvalds p_s_last_element = 656bd4c625cSLinus Torvalds PATH_OFFSET_PELEMENT(p_s_search_path, 657bd4c625cSLinus Torvalds ++p_s_search_path->path_length); 6581da177e4SLinus Torvalds fs_gen = get_generation(p_s_sb); 6591da177e4SLinus Torvalds 6601da177e4SLinus Torvalds /* Read the next tree node, and set the last element in the path to 6611da177e4SLinus Torvalds have a pointer to it. */ 6621da177e4SLinus Torvalds if ((p_s_bh = p_s_last_element->pe_buffer = 6631da177e4SLinus Torvalds sb_getblk(p_s_sb, n_block_number))) { 6641da177e4SLinus Torvalds if (!buffer_uptodate(p_s_bh) && reada_count > 1) { 6651da177e4SLinus Torvalds search_by_key_reada(p_s_sb, reada_bh, 6661da177e4SLinus Torvalds reada_blocks, reada_count); 6671da177e4SLinus Torvalds } 6681da177e4SLinus Torvalds ll_rw_block(READ, 1, &p_s_bh); 6691da177e4SLinus Torvalds wait_on_buffer(p_s_bh); 6701da177e4SLinus Torvalds if (!buffer_uptodate(p_s_bh)) 6711da177e4SLinus Torvalds goto io_error; 6721da177e4SLinus Torvalds } else { 6731da177e4SLinus Torvalds io_error: 6741da177e4SLinus Torvalds p_s_search_path->path_length--; 6751da177e4SLinus Torvalds pathrelse(p_s_search_path); 6761da177e4SLinus Torvalds return IO_ERROR; 6771da177e4SLinus Torvalds } 6781da177e4SLinus Torvalds reada_count = 0; 6791da177e4SLinus Torvalds if (expected_level == -1) 6801da177e4SLinus Torvalds expected_level = SB_TREE_HEIGHT(p_s_sb); 6811da177e4SLinus Torvalds expected_level--; 6821da177e4SLinus Torvalds 6831da177e4SLinus Torvalds /* It is possible that schedule occurred. We must check whether the key 6841da177e4SLinus Torvalds to search is still in the tree rooted from the current buffer. If 6851da177e4SLinus Torvalds not then repeat search from the root. */ 6861da177e4SLinus Torvalds if (fs_changed(fs_gen, p_s_sb) && 6871da177e4SLinus Torvalds (!B_IS_IN_TREE(p_s_bh) || 6881da177e4SLinus Torvalds B_LEVEL(p_s_bh) != expected_level || 6891da177e4SLinus Torvalds !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) { 6901da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, search_by_key_fs_changed); 6911da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, search_by_key_restarted); 692bd4c625cSLinus Torvalds PROC_INFO_INC(p_s_sb, 693bd4c625cSLinus Torvalds sbk_restarted[expected_level - 1]); 6941da177e4SLinus Torvalds decrement_counters_in_path(p_s_search_path); 6951da177e4SLinus Torvalds 6961da177e4SLinus Torvalds /* Get the root block number so that we can repeat the search 6971da177e4SLinus Torvalds starting from the root. */ 6981da177e4SLinus Torvalds n_block_number = SB_ROOT_BLOCK(p_s_sb); 6991da177e4SLinus Torvalds expected_level = -1; 7001da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 7011da177e4SLinus Torvalds 7021da177e4SLinus Torvalds /* repeat search from the root */ 7031da177e4SLinus Torvalds continue; 7041da177e4SLinus Torvalds } 7051da177e4SLinus Torvalds 7061da177e4SLinus Torvalds /* only check that the key is in the buffer if p_s_key is not 7071da177e4SLinus Torvalds equal to the MAX_KEY. Latter case is only possible in 7081da177e4SLinus Torvalds "finish_unfinished()" processing during mount. */ 7091da177e4SLinus Torvalds RFALSE(comp_keys(&MAX_KEY, p_s_key) && 7101da177e4SLinus Torvalds !key_in_buffer(p_s_search_path, p_s_key, p_s_sb), 7111da177e4SLinus Torvalds "PAP-5130: key is not in the buffer"); 7121da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 7131da177e4SLinus Torvalds if (cur_tb) { 7141da177e4SLinus Torvalds print_cur_tb("5140"); 715c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "PAP-5140", 716c3a9c210SJeff Mahoney "schedule occurred in do_balance!"); 7171da177e4SLinus Torvalds } 7181da177e4SLinus Torvalds #endif 7191da177e4SLinus Torvalds 7201da177e4SLinus Torvalds // make sure, that the node contents look like a node of 7211da177e4SLinus Torvalds // certain level 7221da177e4SLinus Torvalds if (!is_tree_node(p_s_bh, expected_level)) { 723*0030b645SJeff Mahoney reiserfs_error(p_s_sb, "vs-5150", 72445b03d5eSJeff Mahoney "invalid format found in block %ld. " 72545b03d5eSJeff Mahoney "Fsck?", p_s_bh->b_blocknr); 7261da177e4SLinus Torvalds pathrelse(p_s_search_path); 7271da177e4SLinus Torvalds return IO_ERROR; 7281da177e4SLinus Torvalds } 7291da177e4SLinus Torvalds 7301da177e4SLinus Torvalds /* ok, we have acquired next formatted node in the tree */ 7311da177e4SLinus Torvalds n_node_level = B_LEVEL(p_s_bh); 7321da177e4SLinus Torvalds 7331da177e4SLinus Torvalds PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1); 7341da177e4SLinus Torvalds 7351da177e4SLinus Torvalds RFALSE(n_node_level < n_stop_level, 7361da177e4SLinus Torvalds "vs-5152: tree level (%d) is less than stop level (%d)", 7371da177e4SLinus Torvalds n_node_level, n_stop_level); 7381da177e4SLinus Torvalds 7391da177e4SLinus Torvalds n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0), 7401da177e4SLinus Torvalds B_NR_ITEMS(p_s_bh), 741bd4c625cSLinus Torvalds (n_node_level == 742bd4c625cSLinus Torvalds DISK_LEAF_NODE_LEVEL) ? IH_SIZE : 743bd4c625cSLinus Torvalds KEY_SIZE, 7441da177e4SLinus Torvalds &(p_s_last_element->pe_position)); 7451da177e4SLinus Torvalds if (n_node_level == n_stop_level) { 7461da177e4SLinus Torvalds return n_retval; 7471da177e4SLinus Torvalds } 7481da177e4SLinus Torvalds 7491da177e4SLinus Torvalds /* we are not in the stop level */ 7501da177e4SLinus Torvalds if (n_retval == ITEM_FOUND) 7511da177e4SLinus Torvalds /* item has been found, so we choose the pointer which is to the right of the found one */ 7521da177e4SLinus Torvalds p_s_last_element->pe_position++; 7531da177e4SLinus Torvalds 7541da177e4SLinus Torvalds /* if item was not found we choose the position which is to 7551da177e4SLinus Torvalds the left of the found item. This requires no code, 7561da177e4SLinus Torvalds bin_search did it already. */ 7571da177e4SLinus Torvalds 7581da177e4SLinus Torvalds /* So we have chosen a position in the current node which is 7591da177e4SLinus Torvalds an internal node. Now we calculate child block number by 7601da177e4SLinus Torvalds position in the node. */ 761bd4c625cSLinus Torvalds n_block_number = 762bd4c625cSLinus Torvalds B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position); 7631da177e4SLinus Torvalds 7641da177e4SLinus Torvalds /* if we are going to read leaf nodes, try for read ahead as well */ 7651da177e4SLinus Torvalds if ((p_s_search_path->reada & PATH_READA) && 766bd4c625cSLinus Torvalds n_node_level == DISK_LEAF_NODE_LEVEL + 1) { 7671da177e4SLinus Torvalds int pos = p_s_last_element->pe_position; 7681da177e4SLinus Torvalds int limit = B_NR_ITEMS(p_s_bh); 7691da177e4SLinus Torvalds struct reiserfs_key *le_key; 7701da177e4SLinus Torvalds 7711da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7721da177e4SLinus Torvalds limit = 0; 7731da177e4SLinus Torvalds while (reada_count < SEARCH_BY_KEY_READA) { 7741da177e4SLinus Torvalds if (pos == limit) 7751da177e4SLinus Torvalds break; 776bd4c625cSLinus Torvalds reada_blocks[reada_count++] = 777bd4c625cSLinus Torvalds B_N_CHILD_NUM(p_s_bh, pos); 7781da177e4SLinus Torvalds if (p_s_search_path->reada & PATH_READA_BACK) 7791da177e4SLinus Torvalds pos--; 7801da177e4SLinus Torvalds else 7811da177e4SLinus Torvalds pos++; 7821da177e4SLinus Torvalds 7831da177e4SLinus Torvalds /* 7841da177e4SLinus Torvalds * check to make sure we're in the same object 7851da177e4SLinus Torvalds */ 7861da177e4SLinus Torvalds le_key = B_N_PDELIM_KEY(p_s_bh, pos); 7871da177e4SLinus Torvalds if (le32_to_cpu(le_key->k_objectid) != 788bd4c625cSLinus Torvalds p_s_key->on_disk_key.k_objectid) { 7891da177e4SLinus Torvalds break; 7901da177e4SLinus Torvalds } 7911da177e4SLinus Torvalds } 7921da177e4SLinus Torvalds } 7931da177e4SLinus Torvalds } 7941da177e4SLinus Torvalds } 7951da177e4SLinus Torvalds 7961da177e4SLinus Torvalds /* Form the path to an item and position in this item which contains 7971da177e4SLinus Torvalds file byte defined by p_s_key. If there is no such item 7981da177e4SLinus Torvalds corresponding to the key, we point the path to the item with 7991da177e4SLinus Torvalds maximal key less than p_s_key, and *p_n_pos_in_item is set to one 8001da177e4SLinus Torvalds past the last entry/byte in the item. If searching for entry in a 8011da177e4SLinus Torvalds directory item, and it is not found, *p_n_pos_in_item is set to one 8021da177e4SLinus Torvalds entry more than the entry with maximal key which is less than the 8031da177e4SLinus Torvalds sought key. 8041da177e4SLinus Torvalds 8051da177e4SLinus Torvalds Note that if there is no entry in this same node which is one more, 8061da177e4SLinus Torvalds then we point to an imaginary entry. for direct items, the 8071da177e4SLinus Torvalds position is in units of bytes, for indirect items the position is 8081da177e4SLinus Torvalds in units of blocknr entries, for directory items the position is in 8091da177e4SLinus Torvalds units of directory entries. */ 8101da177e4SLinus Torvalds 8111da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 8121da177e4SLinus Torvalds int search_for_position_by_key(struct super_block *p_s_sb, /* Pointer to the super block. */ 8131da177e4SLinus Torvalds const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */ 814fec6d055SJosef "Jeff" Sipek struct treepath *p_s_search_path /* Filled up by this function. */ 815bd4c625cSLinus Torvalds ) 816bd4c625cSLinus Torvalds { 8171da177e4SLinus Torvalds struct item_head *p_le_ih; /* pointer to on-disk structure */ 8181da177e4SLinus Torvalds int n_blk_size; 8191da177e4SLinus Torvalds loff_t item_offset, offset; 8201da177e4SLinus Torvalds struct reiserfs_dir_entry de; 8211da177e4SLinus Torvalds int retval; 8221da177e4SLinus Torvalds 8231da177e4SLinus Torvalds /* If searching for directory entry. */ 8241da177e4SLinus Torvalds if (is_direntry_cpu_key(p_cpu_key)) 825bd4c625cSLinus Torvalds return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path, 826bd4c625cSLinus Torvalds &de); 8271da177e4SLinus Torvalds 8281da177e4SLinus Torvalds /* If not searching for directory entry. */ 8291da177e4SLinus Torvalds 8301da177e4SLinus Torvalds /* If item is found. */ 8311da177e4SLinus Torvalds retval = search_item(p_s_sb, p_cpu_key, p_s_search_path); 8321da177e4SLinus Torvalds if (retval == IO_ERROR) 8331da177e4SLinus Torvalds return retval; 8341da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 8351da177e4SLinus Torvalds 836bd4c625cSLinus Torvalds RFALSE(!ih_item_len 837bd4c625cSLinus Torvalds (B_N_PITEM_HEAD 838bd4c625cSLinus Torvalds (PATH_PLAST_BUFFER(p_s_search_path), 8391da177e4SLinus Torvalds PATH_LAST_POSITION(p_s_search_path))), 8401da177e4SLinus Torvalds "PAP-5165: item length equals zero"); 8411da177e4SLinus Torvalds 8421da177e4SLinus Torvalds pos_in_item(p_s_search_path) = 0; 8431da177e4SLinus Torvalds return POSITION_FOUND; 8441da177e4SLinus Torvalds } 8451da177e4SLinus Torvalds 8461da177e4SLinus Torvalds RFALSE(!PATH_LAST_POSITION(p_s_search_path), 8471da177e4SLinus Torvalds "PAP-5170: position equals zero"); 8481da177e4SLinus Torvalds 8491da177e4SLinus Torvalds /* Item is not found. Set path to the previous item. */ 850bd4c625cSLinus Torvalds p_le_ih = 851bd4c625cSLinus Torvalds B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), 852bd4c625cSLinus Torvalds --PATH_LAST_POSITION(p_s_search_path)); 8531da177e4SLinus Torvalds n_blk_size = p_s_sb->s_blocksize; 8541da177e4SLinus Torvalds 8551da177e4SLinus Torvalds if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) { 8561da177e4SLinus Torvalds return FILE_NOT_FOUND; 8571da177e4SLinus Torvalds } 8581da177e4SLinus Torvalds // FIXME: quite ugly this far 8591da177e4SLinus Torvalds 8601da177e4SLinus Torvalds item_offset = le_ih_k_offset(p_le_ih); 8611da177e4SLinus Torvalds offset = cpu_key_k_offset(p_cpu_key); 8621da177e4SLinus Torvalds 8631da177e4SLinus Torvalds /* Needed byte is contained in the item pointed to by the path. */ 8641da177e4SLinus Torvalds if (item_offset <= offset && 8651da177e4SLinus Torvalds item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) { 8661da177e4SLinus Torvalds pos_in_item(p_s_search_path) = offset - item_offset; 8671da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) { 8681da177e4SLinus Torvalds pos_in_item(p_s_search_path) /= n_blk_size; 8691da177e4SLinus Torvalds } 8701da177e4SLinus Torvalds return POSITION_FOUND; 8711da177e4SLinus Torvalds } 8721da177e4SLinus Torvalds 8731da177e4SLinus Torvalds /* Needed byte is not contained in the item pointed to by the 8741da177e4SLinus Torvalds path. Set pos_in_item out of the item. */ 8751da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 876bd4c625cSLinus Torvalds pos_in_item(p_s_search_path) = 877bd4c625cSLinus Torvalds ih_item_len(p_le_ih) / UNFM_P_SIZE; 8781da177e4SLinus Torvalds else 8791da177e4SLinus Torvalds pos_in_item(p_s_search_path) = ih_item_len(p_le_ih); 8801da177e4SLinus Torvalds 8811da177e4SLinus Torvalds return POSITION_NOT_FOUND; 8821da177e4SLinus Torvalds } 8831da177e4SLinus Torvalds 8841da177e4SLinus Torvalds /* Compare given item and item pointed to by the path. */ 885fec6d055SJosef "Jeff" Sipek int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path) 8861da177e4SLinus Torvalds { 8871da177e4SLinus Torvalds struct buffer_head *p_s_bh; 8881da177e4SLinus Torvalds struct item_head *ih; 8891da177e4SLinus Torvalds 8901da177e4SLinus Torvalds /* Last buffer at the path is not in the tree. */ 8911da177e4SLinus Torvalds if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path))) 8921da177e4SLinus Torvalds return 1; 8931da177e4SLinus Torvalds 8941da177e4SLinus Torvalds /* Last path position is invalid. */ 8951da177e4SLinus Torvalds if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh)) 8961da177e4SLinus Torvalds return 1; 8971da177e4SLinus Torvalds 8981da177e4SLinus Torvalds /* we need only to know, whether it is the same item */ 8991da177e4SLinus Torvalds ih = get_ih(p_s_path); 9001da177e4SLinus Torvalds return memcmp(stored_ih, ih, IH_SIZE); 9011da177e4SLinus Torvalds } 9021da177e4SLinus Torvalds 9031da177e4SLinus Torvalds /* unformatted nodes are not logged anymore, ever. This is safe 9041da177e4SLinus Torvalds ** now 9051da177e4SLinus Torvalds */ 9061da177e4SLinus Torvalds #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1) 9071da177e4SLinus Torvalds 9081da177e4SLinus Torvalds // block can not be forgotten as it is in I/O or held by someone 9091da177e4SLinus Torvalds #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh))) 9101da177e4SLinus Torvalds 9111da177e4SLinus Torvalds // prepare for delete or cut of direct item 912fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direct_item(struct treepath *path, 9131da177e4SLinus Torvalds struct item_head *le_ih, 9141da177e4SLinus Torvalds struct inode *inode, 915bd4c625cSLinus Torvalds loff_t new_file_length, int *cut_size) 9161da177e4SLinus Torvalds { 9171da177e4SLinus Torvalds loff_t round_len; 9181da177e4SLinus Torvalds 9191da177e4SLinus Torvalds if (new_file_length == max_reiserfs_offset(inode)) { 9201da177e4SLinus Torvalds /* item has to be deleted */ 9211da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9221da177e4SLinus Torvalds return M_DELETE; 9231da177e4SLinus Torvalds } 9241da177e4SLinus Torvalds // new file gets truncated 9251da177e4SLinus Torvalds if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) { 9261da177e4SLinus Torvalds // 9271da177e4SLinus Torvalds round_len = ROUND_UP(new_file_length); 9281da177e4SLinus Torvalds /* this was n_new_file_length < le_ih ... */ 9291da177e4SLinus Torvalds if (round_len < le_ih_k_offset(le_ih)) { 9301da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9311da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9321da177e4SLinus Torvalds } 9331da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9341da177e4SLinus Torvalds pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1); 9351da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - pos_in_item(path)); 9361da177e4SLinus Torvalds 9371da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9381da177e4SLinus Torvalds } 9391da177e4SLinus Torvalds 9401da177e4SLinus Torvalds // old file: items may have any length 9411da177e4SLinus Torvalds 9421da177e4SLinus Torvalds if (new_file_length < le_ih_k_offset(le_ih)) { 9431da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9441da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9451da177e4SLinus Torvalds } 9461da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9471da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - 948bd4c625cSLinus Torvalds (pos_in_item(path) = 949bd4c625cSLinus Torvalds new_file_length + 1 - le_ih_k_offset(le_ih))); 9501da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9511da177e4SLinus Torvalds } 9521da177e4SLinus Torvalds 953fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direntry_item(struct treepath *path, 9541da177e4SLinus Torvalds struct item_head *le_ih, 9551da177e4SLinus Torvalds struct inode *inode, 9561da177e4SLinus Torvalds loff_t new_file_length, 9571da177e4SLinus Torvalds int *cut_size) 9581da177e4SLinus Torvalds { 9591da177e4SLinus Torvalds if (le_ih_k_offset(le_ih) == DOT_OFFSET && 9601da177e4SLinus Torvalds new_file_length == max_reiserfs_offset(inode)) { 9611da177e4SLinus Torvalds RFALSE(ih_entry_count(le_ih) != 2, 9621da177e4SLinus Torvalds "PAP-5220: incorrect empty directory item (%h)", le_ih); 9631da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9641da177e4SLinus Torvalds return M_DELETE; /* Delete the directory item containing "." and ".." entry. */ 9651da177e4SLinus Torvalds } 9661da177e4SLinus Torvalds 9671da177e4SLinus Torvalds if (ih_entry_count(le_ih) == 1) { 9681da177e4SLinus Torvalds /* Delete the directory item such as there is one record only 9691da177e4SLinus Torvalds in this item */ 9701da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9711da177e4SLinus Torvalds return M_DELETE; 9721da177e4SLinus Torvalds } 9731da177e4SLinus Torvalds 9741da177e4SLinus Torvalds /* Cut one record from the directory item. */ 975bd4c625cSLinus Torvalds *cut_size = 976bd4c625cSLinus Torvalds -(DEH_SIZE + 977bd4c625cSLinus Torvalds entry_length(get_last_bh(path), le_ih, pos_in_item(path))); 9781da177e4SLinus Torvalds return M_CUT; 9791da177e4SLinus Torvalds } 9801da177e4SLinus Torvalds 98123f9e0f8SAlexander Zarochentzev #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1) 98223f9e0f8SAlexander Zarochentzev 9831da177e4SLinus Torvalds /* If the path points to a directory or direct item, calculate mode and the size cut, for balance. 9841da177e4SLinus Torvalds If the path points to an indirect item, remove some number of its unformatted nodes. 9851da177e4SLinus Torvalds In case of file truncate calculate whether this item must be deleted/truncated or last 9861da177e4SLinus Torvalds unformatted node of this item will be converted to a direct item. 9871da177e4SLinus Torvalds This function returns a determination of what balance mode the calling function should employ. */ 988fec6d055SJosef "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 9891da177e4SLinus Torvalds from end of the file. */ 990bd4c625cSLinus Torvalds int *p_n_cut_size, unsigned long long n_new_file_length /* MAX_KEY_OFFSET in case of delete. */ 991bd4c625cSLinus Torvalds ) 992bd4c625cSLinus Torvalds { 9931da177e4SLinus Torvalds struct super_block *p_s_sb = inode->i_sb; 9941da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path); 9951da177e4SLinus Torvalds struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path); 9961da177e4SLinus Torvalds 9971da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 9981da177e4SLinus Torvalds 9991da177e4SLinus Torvalds /* Stat_data item. */ 10001da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) { 10011da177e4SLinus Torvalds 10021da177e4SLinus Torvalds RFALSE(n_new_file_length != max_reiserfs_offset(inode), 10031da177e4SLinus Torvalds "PAP-5210: mode must be M_DELETE"); 10041da177e4SLinus Torvalds 10051da177e4SLinus Torvalds *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih)); 10061da177e4SLinus Torvalds return M_DELETE; 10071da177e4SLinus Torvalds } 10081da177e4SLinus Torvalds 10091da177e4SLinus Torvalds /* Directory item. */ 10101da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) 1011bd4c625cSLinus Torvalds return prepare_for_direntry_item(p_s_path, p_le_ih, inode, 1012bd4c625cSLinus Torvalds n_new_file_length, 1013bd4c625cSLinus Torvalds p_n_cut_size); 10141da177e4SLinus Torvalds 10151da177e4SLinus Torvalds /* Direct item. */ 10161da177e4SLinus Torvalds if (is_direct_le_ih(p_le_ih)) 1017bd4c625cSLinus Torvalds return prepare_for_direct_item(p_s_path, p_le_ih, inode, 1018bd4c625cSLinus Torvalds n_new_file_length, p_n_cut_size); 10191da177e4SLinus Torvalds 10201da177e4SLinus Torvalds /* Case of an indirect item. */ 10211da177e4SLinus Torvalds { 102223f9e0f8SAlexander Zarochentzev int blk_size = p_s_sb->s_blocksize; 102323f9e0f8SAlexander Zarochentzev struct item_head s_ih; 102423f9e0f8SAlexander Zarochentzev int need_re_search; 102523f9e0f8SAlexander Zarochentzev int delete = 0; 102623f9e0f8SAlexander Zarochentzev int result = M_CUT; 102723f9e0f8SAlexander Zarochentzev int pos = 0; 10281da177e4SLinus Torvalds 102923f9e0f8SAlexander Zarochentzev if ( n_new_file_length == max_reiserfs_offset (inode) ) { 103023f9e0f8SAlexander Zarochentzev /* prepare_for_delete_or_cut() is called by 103123f9e0f8SAlexander Zarochentzev * reiserfs_delete_item() */ 103223f9e0f8SAlexander Zarochentzev n_new_file_length = 0; 103323f9e0f8SAlexander Zarochentzev delete = 1; 103423f9e0f8SAlexander Zarochentzev } 10351da177e4SLinus Torvalds 10361da177e4SLinus Torvalds do { 103723f9e0f8SAlexander Zarochentzev need_re_search = 0; 103823f9e0f8SAlexander Zarochentzev *p_n_cut_size = 0; 10391da177e4SLinus Torvalds p_s_bh = PATH_PLAST_BUFFER(p_s_path); 10401da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 104123f9e0f8SAlexander Zarochentzev pos = I_UNFM_NUM(&s_ih); 10421da177e4SLinus Torvalds 104323f9e0f8SAlexander Zarochentzev while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) { 104487588dd6SAl Viro __le32 *unfm; 104587588dd6SAl Viro __u32 block; 10461da177e4SLinus Torvalds 104723f9e0f8SAlexander Zarochentzev /* Each unformatted block deletion may involve one additional 104823f9e0f8SAlexander Zarochentzev * bitmap block into the transaction, thereby the initial 104923f9e0f8SAlexander Zarochentzev * journal space reservation might not be enough. */ 105023f9e0f8SAlexander Zarochentzev if (!delete && (*p_n_cut_size) != 0 && 105123f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 105223f9e0f8SAlexander Zarochentzev break; 10531da177e4SLinus Torvalds } 10541da177e4SLinus Torvalds 105587588dd6SAl Viro unfm = (__le32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1; 105623f9e0f8SAlexander Zarochentzev block = get_block_num(unfm, 0); 10571da177e4SLinus Torvalds 105823f9e0f8SAlexander Zarochentzev if (block != 0) { 10591da177e4SLinus Torvalds reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1); 106023f9e0f8SAlexander Zarochentzev put_block_num(unfm, 0, 0); 106123f9e0f8SAlexander Zarochentzev journal_mark_dirty (th, p_s_sb, p_s_bh); 106223f9e0f8SAlexander Zarochentzev reiserfs_free_block(th, inode, block, 1); 106323f9e0f8SAlexander Zarochentzev } 10641da177e4SLinus Torvalds 10651da177e4SLinus Torvalds cond_resched(); 106623f9e0f8SAlexander Zarochentzev 10671da177e4SLinus Torvalds if (item_moved (&s_ih, p_s_path)) { 106823f9e0f8SAlexander Zarochentzev need_re_search = 1; 10691da177e4SLinus Torvalds break; 10701da177e4SLinus Torvalds } 10711da177e4SLinus Torvalds 107223f9e0f8SAlexander Zarochentzev pos --; 10731da177e4SLinus Torvalds (*p_n_removed) ++; 107423f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= UNFM_P_SIZE; 10751da177e4SLinus Torvalds 107623f9e0f8SAlexander Zarochentzev if (pos == 0) { 107723f9e0f8SAlexander Zarochentzev (*p_n_cut_size) -= IH_SIZE; 107823f9e0f8SAlexander Zarochentzev result = M_DELETE; 10791da177e4SLinus Torvalds break; 10801da177e4SLinus Torvalds } 10811da177e4SLinus Torvalds } 108223f9e0f8SAlexander Zarochentzev /* a trick. If the buffer has been logged, this will do nothing. If 108323f9e0f8SAlexander Zarochentzev ** we've broken the loop without logging it, it will restore the 108423f9e0f8SAlexander Zarochentzev ** buffer */ 10851da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh); 108623f9e0f8SAlexander Zarochentzev } while (need_re_search && 108723f9e0f8SAlexander Zarochentzev search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND); 108823f9e0f8SAlexander Zarochentzev pos_in_item(p_s_path) = pos * UNFM_P_SIZE; 10891da177e4SLinus Torvalds 109023f9e0f8SAlexander Zarochentzev if (*p_n_cut_size == 0) { 109123f9e0f8SAlexander Zarochentzev /* Nothing were cut. maybe convert last unformatted node to the 109223f9e0f8SAlexander Zarochentzev * direct item? */ 109323f9e0f8SAlexander Zarochentzev result = M_CONVERT; 109423f9e0f8SAlexander Zarochentzev } 109523f9e0f8SAlexander Zarochentzev return result; 10961da177e4SLinus Torvalds } 10971da177e4SLinus Torvalds } 10981da177e4SLinus Torvalds 10991da177e4SLinus Torvalds /* Calculate number of bytes which will be deleted or cut during balance */ 1100bd4c625cSLinus Torvalds static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode) 1101bd4c625cSLinus Torvalds { 11021da177e4SLinus Torvalds int n_del_size; 11031da177e4SLinus Torvalds struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path); 11041da177e4SLinus Torvalds 11051da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 11061da177e4SLinus Torvalds return 0; 11071da177e4SLinus Torvalds 1108bd4c625cSLinus Torvalds n_del_size = 1109bd4c625cSLinus Torvalds (c_mode == 1110bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0]; 11111da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) { 11121da177e4SLinus Torvalds // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */ 11131da177e4SLinus Torvalds // we can't use EMPTY_DIR_SIZE, as old format dirs have a different 11141da177e4SLinus Torvalds // empty size. ick. FIXME, is this right? 11151da177e4SLinus Torvalds // 11161da177e4SLinus Torvalds return n_del_size; 11171da177e4SLinus Torvalds } 11181da177e4SLinus Torvalds 11191da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 1120bd4c625cSLinus 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); 11211da177e4SLinus Torvalds return n_del_size; 11221da177e4SLinus Torvalds } 11231da177e4SLinus Torvalds 1124bd4c625cSLinus Torvalds static void init_tb_struct(struct reiserfs_transaction_handle *th, 11251da177e4SLinus Torvalds struct tree_balance *p_s_tb, 11261da177e4SLinus Torvalds struct super_block *p_s_sb, 1127fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, int n_size) 1128bd4c625cSLinus Torvalds { 11291da177e4SLinus Torvalds 11301da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11311da177e4SLinus Torvalds 11321da177e4SLinus Torvalds memset(p_s_tb, '\0', sizeof(struct tree_balance)); 11331da177e4SLinus Torvalds p_s_tb->transaction_handle = th; 11341da177e4SLinus Torvalds p_s_tb->tb_sb = p_s_sb; 11351da177e4SLinus Torvalds p_s_tb->tb_path = p_s_path; 11361da177e4SLinus Torvalds PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL; 11371da177e4SLinus Torvalds PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0; 11381da177e4SLinus Torvalds p_s_tb->insert_size[0] = n_size; 11391da177e4SLinus Torvalds } 11401da177e4SLinus Torvalds 11411da177e4SLinus Torvalds void padd_item(char *item, int total_length, int length) 11421da177e4SLinus Torvalds { 11431da177e4SLinus Torvalds int i; 11441da177e4SLinus Torvalds 11451da177e4SLinus Torvalds for (i = total_length; i > length;) 11461da177e4SLinus Torvalds item[--i] = 0; 11471da177e4SLinus Torvalds } 11481da177e4SLinus Torvalds 11491da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 11501da177e4SLinus Torvalds char key2type(struct reiserfs_key *ih) 11511da177e4SLinus Torvalds { 11521da177e4SLinus Torvalds if (is_direntry_le_key(2, ih)) 11531da177e4SLinus Torvalds return 'd'; 11541da177e4SLinus Torvalds if (is_direct_le_key(2, ih)) 11551da177e4SLinus Torvalds return 'D'; 11561da177e4SLinus Torvalds if (is_indirect_le_key(2, ih)) 11571da177e4SLinus Torvalds return 'i'; 11581da177e4SLinus Torvalds if (is_statdata_le_key(2, ih)) 11591da177e4SLinus Torvalds return 's'; 11601da177e4SLinus Torvalds return 'u'; 11611da177e4SLinus Torvalds } 11621da177e4SLinus Torvalds 11631da177e4SLinus Torvalds char head2type(struct item_head *ih) 11641da177e4SLinus Torvalds { 11651da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) 11661da177e4SLinus Torvalds return 'd'; 11671da177e4SLinus Torvalds if (is_direct_le_ih(ih)) 11681da177e4SLinus Torvalds return 'D'; 11691da177e4SLinus Torvalds if (is_indirect_le_ih(ih)) 11701da177e4SLinus Torvalds return 'i'; 11711da177e4SLinus Torvalds if (is_statdata_le_ih(ih)) 11721da177e4SLinus Torvalds return 's'; 11731da177e4SLinus Torvalds return 'u'; 11741da177e4SLinus Torvalds } 11751da177e4SLinus Torvalds #endif 11761da177e4SLinus Torvalds 11771da177e4SLinus Torvalds /* Delete object item. */ 1178fec6d055SJosef "Jeff" Sipek int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the deleted item. */ 11791da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, /* Key to search for the deleted item. */ 11801da177e4SLinus Torvalds struct inode *p_s_inode, /* inode is here just to update i_blocks and quotas */ 1181bd4c625cSLinus Torvalds struct buffer_head *p_s_un_bh) 1182bd4c625cSLinus Torvalds { /* NULL or unformatted node pointer. */ 11831da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 11841da177e4SLinus Torvalds struct tree_balance s_del_balance; 11851da177e4SLinus Torvalds struct item_head s_ih; 11861da177e4SLinus Torvalds struct item_head *q_ih; 11871da177e4SLinus Torvalds int quota_cut_bytes; 1188bd4c625cSLinus Torvalds int n_ret_value, n_del_size, n_removed; 11891da177e4SLinus Torvalds 11901da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 11911da177e4SLinus Torvalds char c_mode; 11921da177e4SLinus Torvalds int n_iter = 0; 11931da177e4SLinus Torvalds #endif 11941da177e4SLinus Torvalds 11951da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11961da177e4SLinus Torvalds 1197bd4c625cSLinus Torvalds init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path, 1198bd4c625cSLinus Torvalds 0 /*size is unknown */ ); 11991da177e4SLinus Torvalds 12001da177e4SLinus Torvalds while (1) { 12011da177e4SLinus Torvalds n_removed = 0; 12021da177e4SLinus Torvalds 12031da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 12041da177e4SLinus Torvalds n_iter++; 12051da177e4SLinus Torvalds c_mode = 12061da177e4SLinus Torvalds #endif 1207bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1208bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 1209bd4c625cSLinus Torvalds &n_del_size, 1210bd4c625cSLinus Torvalds max_reiserfs_offset(p_s_inode)); 12111da177e4SLinus Torvalds 12121da177e4SLinus Torvalds RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE"); 12131da177e4SLinus Torvalds 12141da177e4SLinus Torvalds copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path)); 12151da177e4SLinus Torvalds s_del_balance.insert_size[0] = n_del_size; 12161da177e4SLinus Torvalds 12171da177e4SLinus Torvalds n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL); 12181da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 12191da177e4SLinus Torvalds break; 12201da177e4SLinus Torvalds 12211da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, delete_item_restarted); 12221da177e4SLinus Torvalds 12231da177e4SLinus Torvalds // file system changed, repeat search 1224bd4c625cSLinus Torvalds n_ret_value = 1225bd4c625cSLinus Torvalds search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path); 12261da177e4SLinus Torvalds if (n_ret_value == IO_ERROR) 12271da177e4SLinus Torvalds break; 12281da177e4SLinus Torvalds if (n_ret_value == FILE_NOT_FOUND) { 122945b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "vs-5340", 1230bd4c625cSLinus Torvalds "no items of the file %K found", 1231bd4c625cSLinus Torvalds p_s_item_key); 12321da177e4SLinus Torvalds break; 12331da177e4SLinus Torvalds } 12341da177e4SLinus Torvalds } /* while (1) */ 12351da177e4SLinus Torvalds 12361da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 12371da177e4SLinus Torvalds unfix_nodes(&s_del_balance); 12381da177e4SLinus Torvalds return 0; 12391da177e4SLinus Torvalds } 12401da177e4SLinus Torvalds // reiserfs_delete_item returns item length when success 12411da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE); 12421da177e4SLinus Torvalds q_ih = get_ih(p_s_path); 12431da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(q_ih); 12441da177e4SLinus Torvalds 12451da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file 12461da177e4SLinus Torvalds ** has a tail. On tail insert, we allocate quota for 1 unformatted node. 12471da177e4SLinus Torvalds ** We test the offset because the tail might have been 12481da177e4SLinus Torvalds ** split into multiple items, and we only want to decrement for 12491da177e4SLinus Torvalds ** the unfm node once 12501da177e4SLinus Torvalds */ 12511da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(q_ih)) { 12521da177e4SLinus Torvalds if ((le_ih_k_offset(q_ih) & (p_s_sb->s_blocksize - 1)) == 1) { 12531da177e4SLinus Torvalds quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE; 12541da177e4SLinus Torvalds } else { 12551da177e4SLinus Torvalds quota_cut_bytes = 0; 12561da177e4SLinus Torvalds } 12571da177e4SLinus Torvalds } 12581da177e4SLinus Torvalds 12591da177e4SLinus Torvalds if (p_s_un_bh) { 12601da177e4SLinus Torvalds int off; 12611da177e4SLinus Torvalds char *data; 12621da177e4SLinus Torvalds 12631da177e4SLinus Torvalds /* We are in direct2indirect conversion, so move tail contents 12641da177e4SLinus Torvalds to the unformatted node */ 12651da177e4SLinus Torvalds /* note, we do the copy before preparing the buffer because we 12661da177e4SLinus Torvalds ** don't care about the contents of the unformatted node yet. 12671da177e4SLinus Torvalds ** the only thing we really care about is the direct item's data 12681da177e4SLinus Torvalds ** is in the unformatted node. 12691da177e4SLinus Torvalds ** 12701da177e4SLinus Torvalds ** Otherwise, we would have to call reiserfs_prepare_for_journal on 12711da177e4SLinus Torvalds ** the unformatted node, which might schedule, meaning we'd have to 12721da177e4SLinus Torvalds ** loop all the way back up to the start of the while loop. 12731da177e4SLinus Torvalds ** 12741da177e4SLinus Torvalds ** The unformatted node must be dirtied later on. We can't be 12751da177e4SLinus Torvalds ** sure here if the entire tail has been deleted yet. 12761da177e4SLinus Torvalds ** 12771da177e4SLinus Torvalds ** p_s_un_bh is from the page cache (all unformatted nodes are 12781da177e4SLinus Torvalds ** from the page cache) and might be a highmem page. So, we 12791da177e4SLinus Torvalds ** can't use p_s_un_bh->b_data. 12801da177e4SLinus Torvalds ** -clm 12811da177e4SLinus Torvalds */ 12821da177e4SLinus Torvalds 12831da177e4SLinus Torvalds data = kmap_atomic(p_s_un_bh->b_page, KM_USER0); 12841da177e4SLinus Torvalds off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1)); 12851da177e4SLinus Torvalds memcpy(data + off, 1286bd4c625cSLinus Torvalds B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), 1287bd4c625cSLinus Torvalds n_ret_value); 12881da177e4SLinus Torvalds kunmap_atomic(data, KM_USER0); 12891da177e4SLinus Torvalds } 12901da177e4SLinus Torvalds /* Perform balancing after all resources have been collected at once. */ 12911da177e4SLinus Torvalds do_balance(&s_del_balance, NULL, NULL, M_DELETE); 12921da177e4SLinus Torvalds 12931da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1294bd4c625cSLinus Torvalds reiserfs_debug(p_s_sb, REISERFS_DEBUG_CODE, 1295bd4c625cSLinus Torvalds "reiserquota delete_item(): freeing %u, id=%u type=%c", 1296bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, head2type(&s_ih)); 12971da177e4SLinus Torvalds #endif 12981da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 12991da177e4SLinus Torvalds 13001da177e4SLinus Torvalds /* Return deleted body length */ 13011da177e4SLinus Torvalds return n_ret_value; 13021da177e4SLinus Torvalds } 13031da177e4SLinus Torvalds 13041da177e4SLinus Torvalds /* Summary Of Mechanisms For Handling Collisions Between Processes: 13051da177e4SLinus Torvalds 13061da177e4SLinus Torvalds deletion of the body of the object is performed by iput(), with the 13071da177e4SLinus Torvalds result that if multiple processes are operating on a file, the 13081da177e4SLinus Torvalds deletion of the body of the file is deferred until the last process 13091da177e4SLinus Torvalds that has an open inode performs its iput(). 13101da177e4SLinus Torvalds 13111da177e4SLinus Torvalds writes and truncates are protected from collisions by use of 13121da177e4SLinus Torvalds semaphores. 13131da177e4SLinus Torvalds 13141da177e4SLinus Torvalds creates, linking, and mknod are protected from collisions with other 13151da177e4SLinus Torvalds processes by making the reiserfs_add_entry() the last step in the 13161da177e4SLinus Torvalds creation, and then rolling back all changes if there was a collision. 13171da177e4SLinus Torvalds - Hans 13181da177e4SLinus Torvalds */ 13191da177e4SLinus Torvalds 13201da177e4SLinus Torvalds /* this deletes item which never gets split */ 13211da177e4SLinus Torvalds void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, 1322bd4c625cSLinus Torvalds struct inode *inode, struct reiserfs_key *key) 13231da177e4SLinus Torvalds { 13241da177e4SLinus Torvalds struct tree_balance tb; 13251da177e4SLinus Torvalds INITIALIZE_PATH(path); 13261da177e4SLinus Torvalds int item_len = 0; 13271da177e4SLinus Torvalds int tb_init = 0; 13281da177e4SLinus Torvalds struct cpu_key cpu_key; 13291da177e4SLinus Torvalds int retval; 13301da177e4SLinus Torvalds int quota_cut_bytes = 0; 13311da177e4SLinus Torvalds 13321da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 13331da177e4SLinus Torvalds 13341da177e4SLinus Torvalds le_key2cpu_key(&cpu_key, key); 13351da177e4SLinus Torvalds 13361da177e4SLinus Torvalds while (1) { 13371da177e4SLinus Torvalds retval = search_item(th->t_super, &cpu_key, &path); 13381da177e4SLinus Torvalds if (retval == IO_ERROR) { 1339*0030b645SJeff Mahoney reiserfs_error(th->t_super, "vs-5350", 134045b03d5eSJeff Mahoney "i/o failure occurred trying " 134145b03d5eSJeff Mahoney "to delete %K", &cpu_key); 13421da177e4SLinus Torvalds break; 13431da177e4SLinus Torvalds } 13441da177e4SLinus Torvalds if (retval != ITEM_FOUND) { 13451da177e4SLinus Torvalds pathrelse(&path); 13461da177e4SLinus Torvalds // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir 1347bd4c625cSLinus Torvalds if (! 1348bd4c625cSLinus Torvalds ((unsigned long long) 1349bd4c625cSLinus Torvalds GET_HASH_VALUE(le_key_k_offset 1350bd4c625cSLinus Torvalds (le_key_version(key), key)) == 0 1351bd4c625cSLinus Torvalds && (unsigned long long) 1352bd4c625cSLinus Torvalds GET_GENERATION_NUMBER(le_key_k_offset 1353bd4c625cSLinus Torvalds (le_key_version(key), 1354bd4c625cSLinus Torvalds key)) == 1)) 135545b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5355", 135645b03d5eSJeff Mahoney "%k not found", key); 13571da177e4SLinus Torvalds break; 13581da177e4SLinus Torvalds } 13591da177e4SLinus Torvalds if (!tb_init) { 13601da177e4SLinus Torvalds tb_init = 1; 13611da177e4SLinus Torvalds item_len = ih_item_len(PATH_PITEM_HEAD(&path)); 1362bd4c625cSLinus Torvalds init_tb_struct(th, &tb, th->t_super, &path, 1363bd4c625cSLinus Torvalds -(IH_SIZE + item_len)); 13641da177e4SLinus Torvalds } 13651da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path)); 13661da177e4SLinus Torvalds 13671da177e4SLinus Torvalds retval = fix_nodes(M_DELETE, &tb, NULL, NULL); 13681da177e4SLinus Torvalds if (retval == REPEAT_SEARCH) { 13691da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, delete_solid_item_restarted); 13701da177e4SLinus Torvalds continue; 13711da177e4SLinus Torvalds } 13721da177e4SLinus Torvalds 13731da177e4SLinus Torvalds if (retval == CARRY_ON) { 13741da177e4SLinus Torvalds do_balance(&tb, NULL, NULL, M_DELETE); 13751da177e4SLinus Torvalds if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */ 13761da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1377bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 1378bd4c625cSLinus Torvalds "reiserquota delete_solid_item(): freeing %u id=%u type=%c", 1379bd4c625cSLinus Torvalds quota_cut_bytes, inode->i_uid, 1380bd4c625cSLinus Torvalds key2type(key)); 13811da177e4SLinus Torvalds #endif 1382bd4c625cSLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, 1383bd4c625cSLinus Torvalds quota_cut_bytes); 13841da177e4SLinus Torvalds } 13851da177e4SLinus Torvalds break; 13861da177e4SLinus Torvalds } 13871da177e4SLinus Torvalds // IO_ERROR, NO_DISK_SPACE, etc 138845b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5360", 1389bd4c625cSLinus Torvalds "could not delete %K due to fix_nodes failure", 1390bd4c625cSLinus Torvalds &cpu_key); 13911da177e4SLinus Torvalds unfix_nodes(&tb); 13921da177e4SLinus Torvalds break; 13931da177e4SLinus Torvalds } 13941da177e4SLinus Torvalds 13951da177e4SLinus Torvalds reiserfs_check_path(&path); 13961da177e4SLinus Torvalds } 13971da177e4SLinus Torvalds 1398bd4c625cSLinus Torvalds int reiserfs_delete_object(struct reiserfs_transaction_handle *th, 1399bd4c625cSLinus Torvalds struct inode *inode) 14001da177e4SLinus Torvalds { 14011da177e4SLinus Torvalds int err; 14021da177e4SLinus Torvalds inode->i_size = 0; 14031da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 14041da177e4SLinus Torvalds 14051da177e4SLinus Torvalds /* for directory this deletes item containing "." and ".." */ 1406bd4c625cSLinus Torvalds err = 1407bd4c625cSLinus Torvalds reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ ); 14081da177e4SLinus Torvalds if (err) 14091da177e4SLinus Torvalds return err; 14101da177e4SLinus Torvalds 14111da177e4SLinus Torvalds #if defined( USE_INODE_GENERATION_COUNTER ) 1412bd4c625cSLinus Torvalds if (!old_format_only(th->t_super)) { 14133e8962beSAl Viro __le32 *inode_generation; 14141da177e4SLinus Torvalds 14151da177e4SLinus Torvalds inode_generation = 14161da177e4SLinus Torvalds &REISERFS_SB(th->t_super)->s_rs->s_inode_generation; 14179e902df6SMarcin Slusarz le32_add_cpu(inode_generation, 1); 14181da177e4SLinus Torvalds } 14191da177e4SLinus Torvalds /* USE_INODE_GENERATION_COUNTER */ 14201da177e4SLinus Torvalds #endif 14211da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 14221da177e4SLinus Torvalds 14231da177e4SLinus Torvalds return err; 14241da177e4SLinus Torvalds } 14251da177e4SLinus Torvalds 1426bd4c625cSLinus Torvalds static void unmap_buffers(struct page *page, loff_t pos) 1427bd4c625cSLinus Torvalds { 14281da177e4SLinus Torvalds struct buffer_head *bh; 14291da177e4SLinus Torvalds struct buffer_head *head; 14301da177e4SLinus Torvalds struct buffer_head *next; 14311da177e4SLinus Torvalds unsigned long tail_index; 14321da177e4SLinus Torvalds unsigned long cur_index; 14331da177e4SLinus Torvalds 14341da177e4SLinus Torvalds if (page) { 14351da177e4SLinus Torvalds if (page_has_buffers(page)) { 14361da177e4SLinus Torvalds tail_index = pos & (PAGE_CACHE_SIZE - 1); 14371da177e4SLinus Torvalds cur_index = 0; 14381da177e4SLinus Torvalds head = page_buffers(page); 14391da177e4SLinus Torvalds bh = head; 14401da177e4SLinus Torvalds do { 14411da177e4SLinus Torvalds next = bh->b_this_page; 14421da177e4SLinus Torvalds 14431da177e4SLinus Torvalds /* we want to unmap the buffers that contain the tail, and 14441da177e4SLinus Torvalds ** all the buffers after it (since the tail must be at the 14451da177e4SLinus Torvalds ** end of the file). We don't want to unmap file data 14461da177e4SLinus Torvalds ** before the tail, since it might be dirty and waiting to 14471da177e4SLinus Torvalds ** reach disk 14481da177e4SLinus Torvalds */ 14491da177e4SLinus Torvalds cur_index += bh->b_size; 14501da177e4SLinus Torvalds if (cur_index > tail_index) { 14511da177e4SLinus Torvalds reiserfs_unmap_buffer(bh); 14521da177e4SLinus Torvalds } 14531da177e4SLinus Torvalds bh = next; 14541da177e4SLinus Torvalds } while (bh != head); 14551da177e4SLinus Torvalds } 14561da177e4SLinus Torvalds } 14571da177e4SLinus Torvalds } 14581da177e4SLinus Torvalds 14591da177e4SLinus Torvalds static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, 14601da177e4SLinus Torvalds struct inode *p_s_inode, 14611da177e4SLinus Torvalds struct page *page, 1462fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 14631da177e4SLinus Torvalds const struct cpu_key *p_s_item_key, 1464bd4c625cSLinus Torvalds loff_t n_new_file_size, char *p_c_mode) 1465bd4c625cSLinus Torvalds { 14661da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 14671da177e4SLinus Torvalds int n_block_size = p_s_sb->s_blocksize; 14681da177e4SLinus Torvalds int cut_bytes; 14691da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 147014a61442SEric Sesterhenn BUG_ON(n_new_file_size != p_s_inode->i_size); 14711da177e4SLinus Torvalds 14721da177e4SLinus Torvalds /* the page being sent in could be NULL if there was an i/o error 14731da177e4SLinus Torvalds ** reading in the last block. The user will hit problems trying to 14741da177e4SLinus Torvalds ** read the file, but for now we just skip the indirect2direct 14751da177e4SLinus Torvalds */ 14761da177e4SLinus Torvalds if (atomic_read(&p_s_inode->i_count) > 1 || 14771da177e4SLinus Torvalds !tail_has_to_be_packed(p_s_inode) || 14781da177e4SLinus Torvalds !page || (REISERFS_I(p_s_inode)->i_flags & i_nopack_mask)) { 14791da177e4SLinus Torvalds // leave tail in an unformatted node 14801da177e4SLinus Torvalds *p_c_mode = M_SKIP_BALANCING; 1481bd4c625cSLinus Torvalds cut_bytes = 1482bd4c625cSLinus Torvalds n_block_size - (n_new_file_size & (n_block_size - 1)); 14831da177e4SLinus Torvalds pathrelse(p_s_path); 14841da177e4SLinus Torvalds return cut_bytes; 14851da177e4SLinus Torvalds } 14861da177e4SLinus Torvalds /* Permorm the conversion to a direct_item. */ 14871da177e4SLinus Torvalds /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode); */ 1488bd4c625cSLinus Torvalds return indirect2direct(th, p_s_inode, page, p_s_path, p_s_item_key, 1489bd4c625cSLinus Torvalds n_new_file_size, p_c_mode); 14901da177e4SLinus Torvalds } 14911da177e4SLinus Torvalds 14921da177e4SLinus Torvalds /* we did indirect_to_direct conversion. And we have inserted direct 14931da177e4SLinus Torvalds item successesfully, but there were no disk space to cut unfm 14941da177e4SLinus Torvalds pointer being converted. Therefore we have to delete inserted 14951da177e4SLinus Torvalds direct item(s) */ 1496bd4c625cSLinus Torvalds static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, 1497fec6d055SJosef "Jeff" Sipek struct inode *inode, struct treepath *path) 14981da177e4SLinus Torvalds { 14991da177e4SLinus Torvalds struct cpu_key tail_key; 15001da177e4SLinus Torvalds int tail_len; 15011da177e4SLinus Torvalds int removed; 15021da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15031da177e4SLinus Torvalds 15041da177e4SLinus Torvalds make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); // !!!! 15051da177e4SLinus Torvalds tail_key.key_length = 4; 15061da177e4SLinus Torvalds 1507bd4c625cSLinus Torvalds tail_len = 1508bd4c625cSLinus Torvalds (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1; 15091da177e4SLinus Torvalds while (tail_len) { 15101da177e4SLinus Torvalds /* look for the last byte of the tail */ 1511bd4c625cSLinus Torvalds if (search_for_position_by_key(inode->i_sb, &tail_key, path) == 1512bd4c625cSLinus Torvalds POSITION_NOT_FOUND) 1513c3a9c210SJeff Mahoney reiserfs_panic(inode->i_sb, "vs-5615", 1514c3a9c210SJeff Mahoney "found invalid item"); 1515bd4c625cSLinus Torvalds RFALSE(path->pos_in_item != 1516bd4c625cSLinus Torvalds ih_item_len(PATH_PITEM_HEAD(path)) - 1, 15171da177e4SLinus Torvalds "vs-5616: appended bytes found"); 15181da177e4SLinus Torvalds PATH_LAST_POSITION(path)--; 15191da177e4SLinus Torvalds 1520bd4c625cSLinus Torvalds removed = 1521bd4c625cSLinus Torvalds reiserfs_delete_item(th, path, &tail_key, inode, 1522bd4c625cSLinus Torvalds NULL /*unbh not needed */ ); 1523bd4c625cSLinus Torvalds RFALSE(removed <= 0 1524bd4c625cSLinus Torvalds || removed > tail_len, 15251da177e4SLinus Torvalds "vs-5617: there was tail %d bytes, removed item length %d bytes", 15261da177e4SLinus Torvalds tail_len, removed); 15271da177e4SLinus Torvalds tail_len -= removed; 1528bd4c625cSLinus Torvalds set_cpu_key_k_offset(&tail_key, 1529bd4c625cSLinus Torvalds cpu_key_k_offset(&tail_key) - removed); 15301da177e4SLinus Torvalds } 153145b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct " 153245b03d5eSJeff Mahoney "conversion has been rolled back due to " 153345b03d5eSJeff Mahoney "lack of disk space"); 15341da177e4SLinus Torvalds //mark_file_without_tail (inode); 15351da177e4SLinus Torvalds mark_inode_dirty(inode); 15361da177e4SLinus Torvalds } 15371da177e4SLinus Torvalds 15381da177e4SLinus Torvalds /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ 15391da177e4SLinus Torvalds int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, 1540fec6d055SJosef "Jeff" Sipek struct treepath *p_s_path, 15411da177e4SLinus Torvalds struct cpu_key *p_s_item_key, 15421da177e4SLinus Torvalds struct inode *p_s_inode, 1543bd4c625cSLinus Torvalds struct page *page, loff_t n_new_file_size) 15441da177e4SLinus Torvalds { 15451da177e4SLinus Torvalds struct super_block *p_s_sb = p_s_inode->i_sb; 15461da177e4SLinus Torvalds /* Every function which is going to call do_balance must first 15471da177e4SLinus Torvalds create a tree_balance structure. Then it must fill up this 15481da177e4SLinus Torvalds structure by using the init_tb_struct and fix_nodes functions. 15491da177e4SLinus Torvalds After that we can make tree balancing. */ 15501da177e4SLinus Torvalds struct tree_balance s_cut_balance; 15511da177e4SLinus Torvalds struct item_head *p_le_ih; 15521da177e4SLinus Torvalds int n_cut_size = 0, /* Amount to be cut. */ 1553bd4c625cSLinus Torvalds n_ret_value = CARRY_ON, n_removed = 0, /* Number of the removed unformatted nodes. */ 15541da177e4SLinus Torvalds n_is_inode_locked = 0; 15551da177e4SLinus Torvalds char c_mode; /* Mode of the balance. */ 15561da177e4SLinus Torvalds int retval2 = -1; 15571da177e4SLinus Torvalds int quota_cut_bytes; 15581da177e4SLinus Torvalds loff_t tail_pos = 0; 15591da177e4SLinus Torvalds 15601da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15611da177e4SLinus Torvalds 1562bd4c625cSLinus Torvalds init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, 1563bd4c625cSLinus Torvalds n_cut_size); 15641da177e4SLinus Torvalds 15651da177e4SLinus Torvalds /* Repeat this loop until we either cut the item without needing 15661da177e4SLinus Torvalds to balance, or we fix_nodes without schedule occurring */ 15671da177e4SLinus Torvalds while (1) { 15681da177e4SLinus Torvalds /* Determine the balance mode, position of the first byte to 15691da177e4SLinus Torvalds be cut, and size to be cut. In case of the indirect item 15701da177e4SLinus Torvalds free unformatted nodes which are pointed to by the cut 15711da177e4SLinus Torvalds pointers. */ 15721da177e4SLinus Torvalds 1573bd4c625cSLinus Torvalds c_mode = 1574bd4c625cSLinus Torvalds prepare_for_delete_or_cut(th, p_s_inode, p_s_path, 1575bd4c625cSLinus Torvalds p_s_item_key, &n_removed, 15761da177e4SLinus Torvalds &n_cut_size, n_new_file_size); 15771da177e4SLinus Torvalds if (c_mode == M_CONVERT) { 15781da177e4SLinus Torvalds /* convert last unformatted node to direct item or leave 15791da177e4SLinus Torvalds tail in the unformatted node */ 1580bd4c625cSLinus Torvalds RFALSE(n_ret_value != CARRY_ON, 1581bd4c625cSLinus Torvalds "PAP-5570: can not convert twice"); 15821da177e4SLinus Torvalds 1583bd4c625cSLinus Torvalds n_ret_value = 1584bd4c625cSLinus Torvalds maybe_indirect_to_direct(th, p_s_inode, page, 1585bd4c625cSLinus Torvalds p_s_path, p_s_item_key, 15861da177e4SLinus Torvalds n_new_file_size, &c_mode); 15871da177e4SLinus Torvalds if (c_mode == M_SKIP_BALANCING) 15881da177e4SLinus Torvalds /* tail has been left in the unformatted node */ 15891da177e4SLinus Torvalds return n_ret_value; 15901da177e4SLinus Torvalds 15911da177e4SLinus Torvalds n_is_inode_locked = 1; 15921da177e4SLinus Torvalds 15931da177e4SLinus Torvalds /* removing of last unformatted node will change value we 15941da177e4SLinus Torvalds have to return to truncate. Save it */ 15951da177e4SLinus Torvalds retval2 = n_ret_value; 15961da177e4SLinus Torvalds /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1)); */ 15971da177e4SLinus Torvalds 15981da177e4SLinus Torvalds /* So, we have performed the first part of the conversion: 15991da177e4SLinus Torvalds inserting the new direct item. Now we are removing the 16001da177e4SLinus Torvalds last unformatted node pointer. Set key to search for 16011da177e4SLinus Torvalds it. */ 16021da177e4SLinus Torvalds set_cpu_key_k_type(p_s_item_key, TYPE_INDIRECT); 16031da177e4SLinus Torvalds p_s_item_key->key_length = 4; 1604bd4c625cSLinus Torvalds n_new_file_size -= 1605bd4c625cSLinus Torvalds (n_new_file_size & (p_s_sb->s_blocksize - 1)); 16061da177e4SLinus Torvalds tail_pos = n_new_file_size; 16071da177e4SLinus Torvalds set_cpu_key_k_offset(p_s_item_key, n_new_file_size + 1); 1608bd4c625cSLinus Torvalds if (search_for_position_by_key 1609bd4c625cSLinus Torvalds (p_s_sb, p_s_item_key, 1610bd4c625cSLinus Torvalds p_s_path) == POSITION_NOT_FOUND) { 1611bd4c625cSLinus Torvalds print_block(PATH_PLAST_BUFFER(p_s_path), 3, 1612bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) - 1, 1613bd4c625cSLinus Torvalds PATH_LAST_POSITION(p_s_path) + 1); 1614c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "PAP-5580", "item to " 1615c3a9c210SJeff Mahoney "convert does not exist (%K)", 1616bd4c625cSLinus Torvalds p_s_item_key); 16171da177e4SLinus Torvalds } 16181da177e4SLinus Torvalds continue; 16191da177e4SLinus Torvalds } 16201da177e4SLinus Torvalds if (n_cut_size == 0) { 16211da177e4SLinus Torvalds pathrelse(p_s_path); 16221da177e4SLinus Torvalds return 0; 16231da177e4SLinus Torvalds } 16241da177e4SLinus Torvalds 16251da177e4SLinus Torvalds s_cut_balance.insert_size[0] = n_cut_size; 16261da177e4SLinus Torvalds 16271da177e4SLinus Torvalds n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, NULL); 16281da177e4SLinus Torvalds if (n_ret_value != REPEAT_SEARCH) 16291da177e4SLinus Torvalds break; 16301da177e4SLinus Torvalds 16311da177e4SLinus Torvalds PROC_INFO_INC(p_s_sb, cut_from_item_restarted); 16321da177e4SLinus Torvalds 1633bd4c625cSLinus Torvalds n_ret_value = 1634bd4c625cSLinus Torvalds search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path); 16351da177e4SLinus Torvalds if (n_ret_value == POSITION_FOUND) 16361da177e4SLinus Torvalds continue; 16371da177e4SLinus Torvalds 163845b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "PAP-5610", "item %K not found", 1639bd4c625cSLinus Torvalds p_s_item_key); 16401da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16411da177e4SLinus Torvalds return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT; 16421da177e4SLinus Torvalds } /* while */ 16431da177e4SLinus Torvalds 16441da177e4SLinus Torvalds // check fix_nodes results (IO_ERROR or NO_DISK_SPACE) 16451da177e4SLinus Torvalds if (n_ret_value != CARRY_ON) { 16461da177e4SLinus Torvalds if (n_is_inode_locked) { 16471da177e4SLinus Torvalds // FIXME: this seems to be not needed: we are always able 16481da177e4SLinus Torvalds // to cut item 16491da177e4SLinus Torvalds indirect_to_direct_roll_back(th, p_s_inode, p_s_path); 16501da177e4SLinus Torvalds } 16511da177e4SLinus Torvalds if (n_ret_value == NO_DISK_SPACE) 165245b03d5eSJeff Mahoney reiserfs_warning(p_s_sb, "reiserfs-5092", 165345b03d5eSJeff Mahoney "NO_DISK_SPACE"); 16541da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16551da177e4SLinus Torvalds return -EIO; 16561da177e4SLinus Torvalds } 16571da177e4SLinus Torvalds 16581da177e4SLinus Torvalds /* go ahead and perform balancing */ 16591da177e4SLinus Torvalds 16601da177e4SLinus Torvalds RFALSE(c_mode == M_PASTE || c_mode == M_INSERT, "invalid mode"); 16611da177e4SLinus Torvalds 16621da177e4SLinus Torvalds /* Calculate number of bytes that need to be cut from the item. */ 1663bd4c625cSLinus Torvalds quota_cut_bytes = 1664bd4c625cSLinus Torvalds (c_mode == 1665bd4c625cSLinus Torvalds M_DELETE) ? ih_item_len(get_ih(p_s_path)) : -s_cut_balance. 1666bd4c625cSLinus Torvalds insert_size[0]; 16671da177e4SLinus Torvalds if (retval2 == -1) 16681da177e4SLinus Torvalds n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode); 16691da177e4SLinus Torvalds else 16701da177e4SLinus Torvalds n_ret_value = retval2; 16711da177e4SLinus Torvalds 16721da177e4SLinus Torvalds /* For direct items, we only change the quota when deleting the last 16731da177e4SLinus Torvalds ** item. 16741da177e4SLinus Torvalds */ 16751da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path); 16761da177e4SLinus Torvalds if (!S_ISLNK(p_s_inode->i_mode) && is_direct_le_ih(p_le_ih)) { 16771da177e4SLinus Torvalds if (c_mode == M_DELETE && 1678bd4c625cSLinus Torvalds (le_ih_k_offset(p_le_ih) & (p_s_sb->s_blocksize - 1)) == 1679bd4c625cSLinus Torvalds 1) { 16801da177e4SLinus Torvalds // FIXME: this is to keep 3.5 happy 16811da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_first_direct_byte = U32_MAX; 16821da177e4SLinus Torvalds quota_cut_bytes = p_s_sb->s_blocksize + UNFM_P_SIZE; 16831da177e4SLinus Torvalds } else { 16841da177e4SLinus Torvalds quota_cut_bytes = 0; 16851da177e4SLinus Torvalds } 16861da177e4SLinus Torvalds } 16871da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 16881da177e4SLinus Torvalds if (n_is_inode_locked) { 1689bd4c625cSLinus Torvalds struct item_head *le_ih = 1690bd4c625cSLinus Torvalds PATH_PITEM_HEAD(s_cut_balance.tb_path); 16911da177e4SLinus Torvalds /* we are going to complete indirect2direct conversion. Make 16921da177e4SLinus Torvalds sure, that we exactly remove last unformatted node pointer 16931da177e4SLinus Torvalds of the item */ 16941da177e4SLinus Torvalds if (!is_indirect_le_ih(le_ih)) 1695c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5652", 16961da177e4SLinus Torvalds "item must be indirect %h", le_ih); 16971da177e4SLinus Torvalds 16981da177e4SLinus Torvalds if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE) 1699c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5653", "completing " 1700c3a9c210SJeff Mahoney "indirect2direct conversion indirect " 1701c3a9c210SJeff Mahoney "item %h being deleted must be of " 1702c3a9c210SJeff Mahoney "4 byte long", le_ih); 17031da177e4SLinus Torvalds 1704bd4c625cSLinus Torvalds if (c_mode == M_CUT 1705bd4c625cSLinus Torvalds && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) { 1706c3a9c210SJeff Mahoney reiserfs_panic(p_s_sb, "vs-5654", "can not complete " 1707c3a9c210SJeff Mahoney "indirect2direct conversion of %h " 1708c3a9c210SJeff Mahoney "(CUT, insert_size==%d)", 17091da177e4SLinus Torvalds le_ih, s_cut_balance.insert_size[0]); 17101da177e4SLinus Torvalds } 17111da177e4SLinus Torvalds /* it would be useful to make sure, that right neighboring 17121da177e4SLinus Torvalds item is direct item of this file */ 17131da177e4SLinus Torvalds } 17141da177e4SLinus Torvalds #endif 17151da177e4SLinus Torvalds 17161da177e4SLinus Torvalds do_balance(&s_cut_balance, NULL, NULL, c_mode); 17171da177e4SLinus Torvalds if (n_is_inode_locked) { 17181da177e4SLinus Torvalds /* we've done an indirect->direct conversion. when the data block 17191da177e4SLinus Torvalds ** was freed, it was removed from the list of blocks that must 17201da177e4SLinus Torvalds ** be flushed before the transaction commits, make sure to 17211da177e4SLinus Torvalds ** unmap and invalidate it 17221da177e4SLinus Torvalds */ 17231da177e4SLinus Torvalds unmap_buffers(page, tail_pos); 17241da177e4SLinus Torvalds REISERFS_I(p_s_inode)->i_flags &= ~i_pack_on_close_mask; 17251da177e4SLinus Torvalds } 17261da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1727bd4c625cSLinus Torvalds reiserfs_debug(p_s_inode->i_sb, REISERFS_DEBUG_CODE, 1728bd4c625cSLinus Torvalds "reiserquota cut_from_item(): freeing %u id=%u type=%c", 1729bd4c625cSLinus Torvalds quota_cut_bytes, p_s_inode->i_uid, '?'); 17301da177e4SLinus Torvalds #endif 17311da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(p_s_inode, quota_cut_bytes); 17321da177e4SLinus Torvalds return n_ret_value; 17331da177e4SLinus Torvalds } 17341da177e4SLinus Torvalds 1735bd4c625cSLinus Torvalds static void truncate_directory(struct reiserfs_transaction_handle *th, 1736bd4c625cSLinus Torvalds struct inode *inode) 17371da177e4SLinus Torvalds { 17381da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 17391da177e4SLinus Torvalds if (inode->i_nlink) 1740*0030b645SJeff Mahoney reiserfs_error(inode->i_sb, "vs-5655", "link count != 0"); 17411da177e4SLinus Torvalds 17421da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET); 17431da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY); 17441da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 17451da177e4SLinus Torvalds reiserfs_update_sd(th, inode); 17461da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET); 17471da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA); 17481da177e4SLinus Torvalds } 17491da177e4SLinus Torvalds 17501da177e4SLinus Torvalds /* Truncate file to the new size. Note, this must be called with a transaction 17511da177e4SLinus Torvalds already started */ 1752bd4c625cSLinus Torvalds int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *p_s_inode, /* ->i_size contains new 17531da177e4SLinus Torvalds size */ 17541da177e4SLinus Torvalds struct page *page, /* up to date for last block */ 17551da177e4SLinus Torvalds int update_timestamps /* when it is called by 17561da177e4SLinus Torvalds file_release to convert 17571da177e4SLinus Torvalds the tail - no timestamps 17581da177e4SLinus Torvalds should be updated */ 1759bd4c625cSLinus Torvalds ) 1760bd4c625cSLinus Torvalds { 17611da177e4SLinus Torvalds INITIALIZE_PATH(s_search_path); /* Path to the current object item. */ 17621da177e4SLinus Torvalds struct item_head *p_le_ih; /* Pointer to an item header. */ 17631da177e4SLinus Torvalds struct cpu_key s_item_key; /* Key to search for a previous file item. */ 17641da177e4SLinus Torvalds loff_t n_file_size, /* Old file size. */ 17651da177e4SLinus Torvalds n_new_file_size; /* New file size. */ 17661da177e4SLinus Torvalds int n_deleted; /* Number of deleted or truncated bytes. */ 17671da177e4SLinus Torvalds int retval; 17681da177e4SLinus Torvalds int err = 0; 17691da177e4SLinus Torvalds 17701da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 1771bd4c625cSLinus Torvalds if (! 1772bd4c625cSLinus Torvalds (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) 1773bd4c625cSLinus Torvalds || S_ISLNK(p_s_inode->i_mode))) 17741da177e4SLinus Torvalds return 0; 17751da177e4SLinus Torvalds 17761da177e4SLinus Torvalds if (S_ISDIR(p_s_inode->i_mode)) { 17771da177e4SLinus Torvalds // deletion of directory - no need to update timestamps 17781da177e4SLinus Torvalds truncate_directory(th, p_s_inode); 17791da177e4SLinus Torvalds return 0; 17801da177e4SLinus Torvalds } 17811da177e4SLinus Torvalds 17821da177e4SLinus Torvalds /* Get new file size. */ 17831da177e4SLinus Torvalds n_new_file_size = p_s_inode->i_size; 17841da177e4SLinus Torvalds 17851da177e4SLinus Torvalds // FIXME: note, that key type is unimportant here 1786bd4c625cSLinus Torvalds make_cpu_key(&s_item_key, p_s_inode, max_reiserfs_offset(p_s_inode), 1787bd4c625cSLinus Torvalds TYPE_DIRECT, 3); 17881da177e4SLinus Torvalds 1789bd4c625cSLinus Torvalds retval = 1790bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1791bd4c625cSLinus Torvalds &s_search_path); 17921da177e4SLinus Torvalds if (retval == IO_ERROR) { 1793*0030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "vs-5657", 1794bd4c625cSLinus Torvalds "i/o failure occurred trying to truncate %K", 1795bd4c625cSLinus Torvalds &s_item_key); 17961da177e4SLinus Torvalds err = -EIO; 17971da177e4SLinus Torvalds goto out; 17981da177e4SLinus Torvalds } 17991da177e4SLinus Torvalds if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) { 1800*0030b645SJeff Mahoney reiserfs_error(p_s_inode->i_sb, "PAP-5660", 1801bd4c625cSLinus Torvalds "wrong result %d of search for %K", retval, 1802bd4c625cSLinus Torvalds &s_item_key); 18031da177e4SLinus Torvalds 18041da177e4SLinus Torvalds err = -EIO; 18051da177e4SLinus Torvalds goto out; 18061da177e4SLinus Torvalds } 18071da177e4SLinus Torvalds 18081da177e4SLinus Torvalds s_search_path.pos_in_item--; 18091da177e4SLinus Torvalds 18101da177e4SLinus Torvalds /* Get real file size (total length of all file items) */ 18111da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(&s_search_path); 18121da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 18131da177e4SLinus Torvalds n_file_size = 0; 18141da177e4SLinus Torvalds else { 18151da177e4SLinus Torvalds loff_t offset = le_ih_k_offset(p_le_ih); 1816bd4c625cSLinus Torvalds int bytes = 1817bd4c625cSLinus Torvalds op_bytes_number(p_le_ih, p_s_inode->i_sb->s_blocksize); 18181da177e4SLinus Torvalds 18191da177e4SLinus Torvalds /* this may mismatch with real file size: if last direct item 18201da177e4SLinus Torvalds had no padding zeros and last unformatted node had no free 18211da177e4SLinus Torvalds space, this file would have this file size */ 18221da177e4SLinus Torvalds n_file_size = offset + bytes - 1; 18231da177e4SLinus Torvalds } 18241da177e4SLinus Torvalds /* 18251da177e4SLinus Torvalds * are we doing a full truncate or delete, if so 18261da177e4SLinus Torvalds * kick in the reada code 18271da177e4SLinus Torvalds */ 18281da177e4SLinus Torvalds if (n_new_file_size == 0) 18291da177e4SLinus Torvalds s_search_path.reada = PATH_READA | PATH_READA_BACK; 18301da177e4SLinus Torvalds 18311da177e4SLinus Torvalds if (n_file_size == 0 || n_file_size < n_new_file_size) { 18321da177e4SLinus Torvalds goto update_and_out; 18331da177e4SLinus Torvalds } 18341da177e4SLinus Torvalds 18351da177e4SLinus Torvalds /* Update key to search for the last file item. */ 18361da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18371da177e4SLinus Torvalds 18381da177e4SLinus Torvalds do { 18391da177e4SLinus Torvalds /* Cut or delete file item. */ 1840bd4c625cSLinus Torvalds n_deleted = 1841bd4c625cSLinus Torvalds reiserfs_cut_from_item(th, &s_search_path, &s_item_key, 1842bd4c625cSLinus Torvalds p_s_inode, page, n_new_file_size); 18431da177e4SLinus Torvalds if (n_deleted < 0) { 184445b03d5eSJeff Mahoney reiserfs_warning(p_s_inode->i_sb, "vs-5665", 184545b03d5eSJeff Mahoney "reiserfs_cut_from_item failed"); 18461da177e4SLinus Torvalds reiserfs_check_path(&s_search_path); 18471da177e4SLinus Torvalds return 0; 18481da177e4SLinus Torvalds } 18491da177e4SLinus Torvalds 18501da177e4SLinus Torvalds RFALSE(n_deleted > n_file_size, 18511da177e4SLinus Torvalds "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K", 18521da177e4SLinus Torvalds n_deleted, n_file_size, &s_item_key); 18531da177e4SLinus Torvalds 18541da177e4SLinus Torvalds /* Change key to search the last file item. */ 18551da177e4SLinus Torvalds n_file_size -= n_deleted; 18561da177e4SLinus Torvalds 18571da177e4SLinus Torvalds set_cpu_key_k_offset(&s_item_key, n_file_size); 18581da177e4SLinus Torvalds 18591da177e4SLinus Torvalds /* While there are bytes to truncate and previous file item is presented in the tree. */ 18601da177e4SLinus Torvalds 18611da177e4SLinus Torvalds /* 18621da177e4SLinus Torvalds ** This loop could take a really long time, and could log 18631da177e4SLinus Torvalds ** many more blocks than a transaction can hold. So, we do a polite 18641da177e4SLinus Torvalds ** journal end here, and if the transaction needs ending, we make 18651da177e4SLinus Torvalds ** sure the file is consistent before ending the current trans 18661da177e4SLinus Torvalds ** and starting a new one 18671da177e4SLinus Torvalds */ 186823f9e0f8SAlexander Zarochentzev if (journal_transaction_should_end(th, 0) || 186923f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 18701da177e4SLinus Torvalds int orig_len_alloc = th->t_blocks_allocated; 18711da177e4SLinus Torvalds decrement_counters_in_path(&s_search_path); 18721da177e4SLinus Torvalds 18731da177e4SLinus Torvalds if (update_timestamps) { 1874bd4c625cSLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = 1875bd4c625cSLinus Torvalds CURRENT_TIME_SEC; 18761da177e4SLinus Torvalds } 18771da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 18781da177e4SLinus Torvalds 18791da177e4SLinus Torvalds err = journal_end(th, p_s_inode->i_sb, orig_len_alloc); 18801da177e4SLinus Torvalds if (err) 18811da177e4SLinus Torvalds goto out; 18821da177e4SLinus Torvalds err = journal_begin(th, p_s_inode->i_sb, 188323f9e0f8SAlexander Zarochentzev JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ; 18841da177e4SLinus Torvalds if (err) 18851da177e4SLinus Torvalds goto out; 18861da177e4SLinus Torvalds reiserfs_update_inode_transaction(p_s_inode); 18871da177e4SLinus Torvalds } 18881da177e4SLinus Torvalds } while (n_file_size > ROUND_UP(n_new_file_size) && 1889bd4c625cSLinus Torvalds search_for_position_by_key(p_s_inode->i_sb, &s_item_key, 1890bd4c625cSLinus Torvalds &s_search_path) == POSITION_FOUND); 18911da177e4SLinus Torvalds 18921da177e4SLinus Torvalds RFALSE(n_file_size > ROUND_UP(n_new_file_size), 18931da177e4SLinus Torvalds "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d", 18941da177e4SLinus Torvalds n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid); 18951da177e4SLinus Torvalds 18961da177e4SLinus Torvalds update_and_out: 18971da177e4SLinus Torvalds if (update_timestamps) { 18981da177e4SLinus Torvalds // this is truncate, not file closing 18991da177e4SLinus Torvalds p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME_SEC; 19001da177e4SLinus Torvalds } 19011da177e4SLinus Torvalds reiserfs_update_sd(th, p_s_inode); 19021da177e4SLinus Torvalds 19031da177e4SLinus Torvalds out: 19041da177e4SLinus Torvalds pathrelse(&s_search_path); 19051da177e4SLinus Torvalds return err; 19061da177e4SLinus Torvalds } 19071da177e4SLinus Torvalds 19081da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 19091da177e4SLinus Torvalds // this makes sure, that we __append__, not overwrite or add holes 1910fec6d055SJosef "Jeff" Sipek static void check_research_for_paste(struct treepath *path, 19111da177e4SLinus Torvalds const struct cpu_key *p_s_key) 19121da177e4SLinus Torvalds { 19131da177e4SLinus Torvalds struct item_head *found_ih = get_ih(path); 19141da177e4SLinus Torvalds 19151da177e4SLinus Torvalds if (is_direct_le_ih(found_ih)) { 1916bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1917bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1918bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1919bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1920bd4c625cSLinus Torvalds || op_bytes_number(found_ih, 1921bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1922bd4c625cSLinus Torvalds pos_in_item(path)) 1923c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5720", "found direct item " 1924c3a9c210SJeff Mahoney "%h or position (%d) does not match " 1925c3a9c210SJeff Mahoney "to key %K", found_ih, 1926c3a9c210SJeff Mahoney pos_in_item(path), p_s_key); 19271da177e4SLinus Torvalds } 19281da177e4SLinus Torvalds if (is_indirect_le_ih(found_ih)) { 1929bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1930bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1931bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1932bd4c625cSLinus Torvalds cpu_key_k_offset(p_s_key) 1933bd4c625cSLinus Torvalds || I_UNFM_NUM(found_ih) != pos_in_item(path) 1934bd4c625cSLinus Torvalds || get_ih_free_space(found_ih) != 0) 1935c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5730", "found indirect " 1936c3a9c210SJeff Mahoney "item (%h) or position (%d) does not " 1937c3a9c210SJeff Mahoney "match to key (%K)", 19381da177e4SLinus Torvalds found_ih, pos_in_item(path), p_s_key); 19391da177e4SLinus Torvalds } 19401da177e4SLinus Torvalds } 19411da177e4SLinus Torvalds #endif /* config reiserfs check */ 19421da177e4SLinus Torvalds 19431da177e4SLinus Torvalds /* Paste bytes to the existing item. Returns bytes number pasted into the item. */ 1944fec6d055SJosef "Jeff" Sipek int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_search_path, /* Path to the pasted item. */ 19451da177e4SLinus Torvalds const struct cpu_key *p_s_key, /* Key to search for the needed item. */ 19461da177e4SLinus Torvalds struct inode *inode, /* Inode item belongs to */ 19471da177e4SLinus Torvalds const char *p_c_body, /* Pointer to the bytes to paste. */ 1948bd4c625cSLinus Torvalds int n_pasted_size) 1949bd4c625cSLinus Torvalds { /* Size of pasted bytes. */ 19501da177e4SLinus Torvalds struct tree_balance s_paste_balance; 19511da177e4SLinus Torvalds int retval; 19521da177e4SLinus Torvalds int fs_gen; 19531da177e4SLinus Torvalds 19541da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 19551da177e4SLinus Torvalds 19561da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 19571da177e4SLinus Torvalds 19581da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1959bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1960bd4c625cSLinus Torvalds "reiserquota paste_into_item(): allocating %u id=%u type=%c", 1961bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 1962bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 19631da177e4SLinus Torvalds #endif 19641da177e4SLinus Torvalds 19651da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, n_pasted_size)) { 19661da177e4SLinus Torvalds pathrelse(p_s_search_path); 19671da177e4SLinus Torvalds return -EDQUOT; 19681da177e4SLinus Torvalds } 1969bd4c625cSLinus Torvalds init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, 1970bd4c625cSLinus Torvalds n_pasted_size); 19711da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 19721da177e4SLinus Torvalds s_paste_balance.key = p_s_key->on_disk_key; 19731da177e4SLinus Torvalds #endif 19741da177e4SLinus Torvalds 19751da177e4SLinus Torvalds /* DQUOT_* can schedule, must check before the fix_nodes */ 19761da177e4SLinus Torvalds if (fs_changed(fs_gen, inode->i_sb)) { 19771da177e4SLinus Torvalds goto search_again; 19781da177e4SLinus Torvalds } 19791da177e4SLinus Torvalds 1980bd4c625cSLinus Torvalds while ((retval = 1981bd4c625cSLinus Torvalds fix_nodes(M_PASTE, &s_paste_balance, NULL, 1982bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 19831da177e4SLinus Torvalds search_again: 19841da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 19851da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, paste_into_item_restarted); 1986bd4c625cSLinus Torvalds retval = 1987bd4c625cSLinus Torvalds search_for_position_by_key(th->t_super, p_s_key, 1988bd4c625cSLinus Torvalds p_s_search_path); 19891da177e4SLinus Torvalds if (retval == IO_ERROR) { 19901da177e4SLinus Torvalds retval = -EIO; 19911da177e4SLinus Torvalds goto error_out; 19921da177e4SLinus Torvalds } 19931da177e4SLinus Torvalds if (retval == POSITION_FOUND) { 199445b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "PAP-5710", 199545b03d5eSJeff Mahoney "entry or pasted byte (%K) exists", 1996bd4c625cSLinus Torvalds p_s_key); 19971da177e4SLinus Torvalds retval = -EEXIST; 19981da177e4SLinus Torvalds goto error_out; 19991da177e4SLinus Torvalds } 20001da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 20011da177e4SLinus Torvalds check_research_for_paste(p_s_search_path, p_s_key); 20021da177e4SLinus Torvalds #endif 20031da177e4SLinus Torvalds } 20041da177e4SLinus Torvalds 20051da177e4SLinus Torvalds /* Perform balancing after all resources are collected by fix_nodes, and 20061da177e4SLinus Torvalds accessing them will not risk triggering schedule. */ 20071da177e4SLinus Torvalds if (retval == CARRY_ON) { 20081da177e4SLinus Torvalds do_balance(&s_paste_balance, NULL /*ih */ , p_c_body, M_PASTE); 20091da177e4SLinus Torvalds return 0; 20101da177e4SLinus Torvalds } 20111da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 20121da177e4SLinus Torvalds error_out: 20131da177e4SLinus Torvalds /* this also releases the path */ 20141da177e4SLinus Torvalds unfix_nodes(&s_paste_balance); 20151da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2016bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2017bd4c625cSLinus Torvalds "reiserquota paste_into_item(): freeing %u id=%u type=%c", 2018bd4c625cSLinus Torvalds n_pasted_size, inode->i_uid, 2019bd4c625cSLinus Torvalds key2type(&(p_s_key->on_disk_key))); 20201da177e4SLinus Torvalds #endif 20211da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, n_pasted_size); 20221da177e4SLinus Torvalds return retval; 20231da177e4SLinus Torvalds } 20241da177e4SLinus Torvalds 20251da177e4SLinus Torvalds /* Insert new item into the buffer at the path. */ 2026fec6d055SJosef "Jeff" Sipek int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path, /* Path to the inserteded item. */ 2027bd4c625cSLinus Torvalds const struct cpu_key *key, struct item_head *p_s_ih, /* Pointer to the item header to insert. */ 2028bd4c625cSLinus Torvalds struct inode *inode, const char *p_c_body) 2029bd4c625cSLinus Torvalds { /* Pointer to the bytes to insert. */ 20301da177e4SLinus Torvalds struct tree_balance s_ins_balance; 20311da177e4SLinus Torvalds int retval; 20321da177e4SLinus Torvalds int fs_gen = 0; 20331da177e4SLinus Torvalds int quota_bytes = 0; 20341da177e4SLinus Torvalds 20351da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 20361da177e4SLinus Torvalds 20371da177e4SLinus Torvalds if (inode) { /* Do we count quotas for item? */ 20381da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 20391da177e4SLinus Torvalds quota_bytes = ih_item_len(p_s_ih); 20401da177e4SLinus Torvalds 20411da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file has 20421da177e4SLinus Torvalds ** a tail, links are always tails, so there's no guessing needed 20431da177e4SLinus Torvalds */ 20441da177e4SLinus Torvalds if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_s_ih)) { 20451da177e4SLinus Torvalds quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE; 20461da177e4SLinus Torvalds } 20471da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2048bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2049bd4c625cSLinus Torvalds "reiserquota insert_item(): allocating %u id=%u type=%c", 2050bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 20511da177e4SLinus Torvalds #endif 20521da177e4SLinus Torvalds /* We can't dirty inode here. It would be immediately written but 20531da177e4SLinus Torvalds * appropriate stat item isn't inserted yet... */ 20541da177e4SLinus Torvalds if (DQUOT_ALLOC_SPACE_NODIRTY(inode, quota_bytes)) { 20551da177e4SLinus Torvalds pathrelse(p_s_path); 20561da177e4SLinus Torvalds return -EDQUOT; 20571da177e4SLinus Torvalds } 20581da177e4SLinus Torvalds } 2059bd4c625cSLinus Torvalds init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, 2060bd4c625cSLinus Torvalds IH_SIZE + ih_item_len(p_s_ih)); 20611da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 20621da177e4SLinus Torvalds s_ins_balance.key = key->on_disk_key; 20631da177e4SLinus Torvalds #endif 20641da177e4SLinus Torvalds /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */ 20651da177e4SLinus Torvalds if (inode && fs_changed(fs_gen, inode->i_sb)) { 20661da177e4SLinus Torvalds goto search_again; 20671da177e4SLinus Torvalds } 20681da177e4SLinus Torvalds 2069bd4c625cSLinus Torvalds while ((retval = 2070bd4c625cSLinus Torvalds fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, 2071bd4c625cSLinus Torvalds p_c_body)) == REPEAT_SEARCH) { 20721da177e4SLinus Torvalds search_again: 20731da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 20741da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, insert_item_restarted); 20751da177e4SLinus Torvalds retval = search_item(th->t_super, key, p_s_path); 20761da177e4SLinus Torvalds if (retval == IO_ERROR) { 20771da177e4SLinus Torvalds retval = -EIO; 20781da177e4SLinus Torvalds goto error_out; 20791da177e4SLinus Torvalds } 20801da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 208145b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "PAP-5760", 2082bd4c625cSLinus Torvalds "key %K already exists in the tree", 2083bd4c625cSLinus Torvalds key); 20841da177e4SLinus Torvalds retval = -EEXIST; 20851da177e4SLinus Torvalds goto error_out; 20861da177e4SLinus Torvalds } 20871da177e4SLinus Torvalds } 20881da177e4SLinus Torvalds 20891da177e4SLinus Torvalds /* make balancing after all resources will be collected at a time */ 20901da177e4SLinus Torvalds if (retval == CARRY_ON) { 20911da177e4SLinus Torvalds do_balance(&s_ins_balance, p_s_ih, p_c_body, M_INSERT); 20921da177e4SLinus Torvalds return 0; 20931da177e4SLinus Torvalds } 20941da177e4SLinus Torvalds 20951da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 20961da177e4SLinus Torvalds error_out: 20971da177e4SLinus Torvalds /* also releases the path */ 20981da177e4SLinus Torvalds unfix_nodes(&s_ins_balance); 20991da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2100bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 2101bd4c625cSLinus Torvalds "reiserquota insert_item(): freeing %u id=%u type=%c", 2102bd4c625cSLinus Torvalds quota_bytes, inode->i_uid, head2type(p_s_ih)); 21031da177e4SLinus Torvalds #endif 21041da177e4SLinus Torvalds if (inode) 21051da177e4SLinus Torvalds DQUOT_FREE_SPACE_NODIRTY(inode, quota_bytes); 21061da177e4SLinus Torvalds return retval; 21071da177e4SLinus Torvalds } 2108