11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README 31da177e4SLinus Torvalds */ 41da177e4SLinus Torvalds 51da177e4SLinus Torvalds /* 61da177e4SLinus Torvalds * Written by Anatoly P. Pinchuk pap@namesys.botik.ru 71da177e4SLinus Torvalds * Programm System Institute 81da177e4SLinus Torvalds * Pereslavl-Zalessky Russia 91da177e4SLinus Torvalds */ 101da177e4SLinus Torvalds 111da177e4SLinus Torvalds /* 121da177e4SLinus Torvalds * This file contains functions dealing with S+tree 131da177e4SLinus Torvalds * 141da177e4SLinus Torvalds * B_IS_IN_TREE 151da177e4SLinus Torvalds * copy_item_head 161da177e4SLinus Torvalds * comp_short_keys 171da177e4SLinus Torvalds * comp_keys 181da177e4SLinus Torvalds * comp_short_le_keys 191da177e4SLinus Torvalds * le_key2cpu_key 201da177e4SLinus Torvalds * comp_le_keys 211da177e4SLinus Torvalds * bin_search 221da177e4SLinus Torvalds * get_lkey 231da177e4SLinus Torvalds * get_rkey 241da177e4SLinus Torvalds * key_in_buffer 251da177e4SLinus Torvalds * decrement_bcount 261da177e4SLinus Torvalds * reiserfs_check_path 271da177e4SLinus Torvalds * pathrelse_and_restore 281da177e4SLinus Torvalds * pathrelse 291da177e4SLinus Torvalds * search_by_key_reada 301da177e4SLinus Torvalds * search_by_key 311da177e4SLinus Torvalds * search_for_position_by_key 321da177e4SLinus Torvalds * comp_items 331da177e4SLinus Torvalds * prepare_for_direct_item 341da177e4SLinus Torvalds * prepare_for_direntry_item 351da177e4SLinus Torvalds * prepare_for_delete_or_cut 361da177e4SLinus Torvalds * calc_deleted_bytes_number 371da177e4SLinus Torvalds * init_tb_struct 381da177e4SLinus Torvalds * padd_item 391da177e4SLinus Torvalds * reiserfs_delete_item 401da177e4SLinus Torvalds * reiserfs_delete_solid_item 411da177e4SLinus Torvalds * reiserfs_delete_object 421da177e4SLinus Torvalds * maybe_indirect_to_direct 431da177e4SLinus Torvalds * indirect_to_direct_roll_back 441da177e4SLinus Torvalds * reiserfs_cut_from_item 451da177e4SLinus Torvalds * truncate_directory 461da177e4SLinus Torvalds * reiserfs_do_truncate 471da177e4SLinus Torvalds * reiserfs_paste_into_item 481da177e4SLinus Torvalds * reiserfs_insert_item 491da177e4SLinus Torvalds */ 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds #include <linux/time.h> 521da177e4SLinus Torvalds #include <linux/string.h> 531da177e4SLinus Torvalds #include <linux/pagemap.h> 54f466c6fdSAl Viro #include "reiserfs.h" 551da177e4SLinus Torvalds #include <linux/buffer_head.h> 561da177e4SLinus Torvalds #include <linux/quotaops.h> 571da177e4SLinus Torvalds 581da177e4SLinus Torvalds /* Does the buffer contain a disk block which is in the tree. */ 59ad31a4fcSJeff Mahoney inline int B_IS_IN_TREE(const struct buffer_head *bh) 601da177e4SLinus Torvalds { 611da177e4SLinus Torvalds 62ad31a4fcSJeff Mahoney RFALSE(B_LEVEL(bh) > MAX_HEIGHT, 63ad31a4fcSJeff Mahoney "PAP-1010: block (%b) has too big level (%z)", bh, bh); 641da177e4SLinus Torvalds 65ad31a4fcSJeff Mahoney return (B_LEVEL(bh) != FREE_LEVEL); 661da177e4SLinus Torvalds } 671da177e4SLinus Torvalds 681da177e4SLinus Torvalds // 691da177e4SLinus Torvalds // to gets item head in le form 701da177e4SLinus Torvalds // 71d68caa95SJeff Mahoney inline void copy_item_head(struct item_head *to, 72d68caa95SJeff Mahoney const struct item_head *from) 731da177e4SLinus Torvalds { 74d68caa95SJeff Mahoney memcpy(to, from, IH_SIZE); 751da177e4SLinus Torvalds } 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 781da177e4SLinus Torvalds form. k2 is pointer to cpu variable. For key of items of the same 791da177e4SLinus Torvalds object this returns 0. 801da177e4SLinus Torvalds Returns: -1 if key1 < key2 811da177e4SLinus Torvalds 0 if key1 == key2 821da177e4SLinus Torvalds 1 if key1 > key2 */ 831da177e4SLinus Torvalds inline int comp_short_keys(const struct reiserfs_key *le_key, 841da177e4SLinus Torvalds const struct cpu_key *cpu_key) 851da177e4SLinus Torvalds { 866b9f5829SAl Viro __u32 n; 876b9f5829SAl Viro n = le32_to_cpu(le_key->k_dir_id); 886b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_dir_id) 891da177e4SLinus Torvalds return -1; 906b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_dir_id) 911da177e4SLinus Torvalds return 1; 926b9f5829SAl Viro n = le32_to_cpu(le_key->k_objectid); 936b9f5829SAl Viro if (n < cpu_key->on_disk_key.k_objectid) 946b9f5829SAl Viro return -1; 956b9f5829SAl Viro if (n > cpu_key->on_disk_key.k_objectid) 966b9f5829SAl Viro return 1; 971da177e4SLinus Torvalds return 0; 981da177e4SLinus Torvalds } 991da177e4SLinus Torvalds 1001da177e4SLinus Torvalds /* k1 is pointer to on-disk structure which is stored in little-endian 1011da177e4SLinus Torvalds form. k2 is pointer to cpu variable. 1021da177e4SLinus Torvalds Compare keys using all 4 key fields. 1031da177e4SLinus Torvalds Returns: -1 if key1 < key2 0 1041da177e4SLinus Torvalds if key1 = key2 1 if key1 > key2 */ 105bd4c625cSLinus Torvalds static inline int comp_keys(const struct reiserfs_key *le_key, 106bd4c625cSLinus Torvalds const struct cpu_key *cpu_key) 1071da177e4SLinus Torvalds { 1081da177e4SLinus Torvalds int retval; 1091da177e4SLinus Torvalds 1101da177e4SLinus Torvalds retval = comp_short_keys(le_key, cpu_key); 1111da177e4SLinus Torvalds if (retval) 1121da177e4SLinus Torvalds return retval; 113bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) < 114bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1151da177e4SLinus Torvalds return -1; 116bd4c625cSLinus Torvalds if (le_key_k_offset(le_key_version(le_key), le_key) > 117bd4c625cSLinus Torvalds cpu_key_k_offset(cpu_key)) 1181da177e4SLinus Torvalds return 1; 1191da177e4SLinus Torvalds 1201da177e4SLinus Torvalds if (cpu_key->key_length == 3) 1211da177e4SLinus Torvalds return 0; 1221da177e4SLinus Torvalds 1231da177e4SLinus Torvalds /* this part is needed only when tail conversion is in progress */ 124bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) < 125bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1261da177e4SLinus Torvalds return -1; 1271da177e4SLinus Torvalds 128bd4c625cSLinus Torvalds if (le_key_k_type(le_key_version(le_key), le_key) > 129bd4c625cSLinus Torvalds cpu_key_k_type(cpu_key)) 1301da177e4SLinus Torvalds return 1; 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds return 0; 1331da177e4SLinus Torvalds } 1341da177e4SLinus Torvalds 135bd4c625cSLinus Torvalds inline int comp_short_le_keys(const struct reiserfs_key *key1, 136bd4c625cSLinus Torvalds const struct reiserfs_key *key2) 1371da177e4SLinus Torvalds { 138d68caa95SJeff Mahoney __u32 *k1_u32, *k2_u32; 139ee93961bSJeff Mahoney int key_length = REISERFS_SHORT_KEY_LEN; 1401da177e4SLinus Torvalds 141d68caa95SJeff Mahoney k1_u32 = (__u32 *) key1; 142d68caa95SJeff Mahoney k2_u32 = (__u32 *) key2; 143ee93961bSJeff Mahoney for (; key_length--; ++k1_u32, ++k2_u32) { 144d68caa95SJeff Mahoney if (le32_to_cpu(*k1_u32) < le32_to_cpu(*k2_u32)) 1451da177e4SLinus Torvalds return -1; 146d68caa95SJeff Mahoney if (le32_to_cpu(*k1_u32) > le32_to_cpu(*k2_u32)) 1471da177e4SLinus Torvalds return 1; 1481da177e4SLinus Torvalds } 1491da177e4SLinus Torvalds return 0; 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds 1521da177e4SLinus Torvalds inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from) 1531da177e4SLinus Torvalds { 1546b9f5829SAl Viro int version; 1551da177e4SLinus Torvalds to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id); 1561da177e4SLinus Torvalds to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid); 1571da177e4SLinus Torvalds 1581da177e4SLinus Torvalds // find out version of the key 1596b9f5829SAl Viro version = le_key_version(from); 1606b9f5829SAl Viro to->version = version; 1616b9f5829SAl Viro to->on_disk_key.k_offset = le_key_k_offset(version, from); 1626b9f5829SAl Viro to->on_disk_key.k_type = le_key_k_type(version, from); 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds // this does not say which one is bigger, it only returns 1 if keys 1661da177e4SLinus Torvalds // are not equal, 0 otherwise 167bd4c625cSLinus Torvalds inline int comp_le_keys(const struct reiserfs_key *k1, 168bd4c625cSLinus Torvalds const struct reiserfs_key *k2) 1691da177e4SLinus Torvalds { 1701da177e4SLinus Torvalds return memcmp(k1, k2, sizeof(struct reiserfs_key)); 1711da177e4SLinus Torvalds } 1721da177e4SLinus Torvalds 1731da177e4SLinus Torvalds /************************************************************************** 1741da177e4SLinus Torvalds * Binary search toolkit function * 1751da177e4SLinus Torvalds * Search for an item in the array by the item key * 1761da177e4SLinus Torvalds * Returns: 1 if found, 0 if not found; * 177d68caa95SJeff Mahoney * *pos = number of the searched element if found, else the * 178d68caa95SJeff Mahoney * number of the first element that is larger than key. * 1791da177e4SLinus Torvalds **************************************************************************/ 180ee93961bSJeff Mahoney /* For those not familiar with binary search: lbound is the leftmost item that it 181ee93961bSJeff Mahoney could be, rbound the rightmost item that it could be. We examine the item 182ee93961bSJeff Mahoney halfway between lbound and rbound, and that tells us either that we can increase 183ee93961bSJeff Mahoney lbound, or decrease rbound, or that we have found it, or if lbound <= rbound that 1841da177e4SLinus Torvalds there are no possible items, and we have not found it. With each examination we 1851da177e4SLinus Torvalds cut the number of possible items it could be by one more than half rounded down, 1861da177e4SLinus Torvalds or we find it. */ 187d68caa95SJeff Mahoney static inline int bin_search(const void *key, /* Key to search for. */ 188d68caa95SJeff Mahoney const void *base, /* First item in the array. */ 189d68caa95SJeff Mahoney int num, /* Number of items in the array. */ 190d68caa95SJeff Mahoney int width, /* Item size in the array. 1911da177e4SLinus Torvalds searched. Lest the reader be 1921da177e4SLinus Torvalds confused, note that this is crafted 1931da177e4SLinus Torvalds as a general function, and when it 1941da177e4SLinus Torvalds is applied specifically to the array 195d68caa95SJeff Mahoney of item headers in a node, width 1961da177e4SLinus Torvalds is actually the item header size not 1971da177e4SLinus Torvalds the item size. */ 198d68caa95SJeff Mahoney int *pos /* Number of the searched for element. */ 199bd4c625cSLinus Torvalds ) 200bd4c625cSLinus Torvalds { 201ee93961bSJeff Mahoney int rbound, lbound, j; 2021da177e4SLinus Torvalds 203ee93961bSJeff Mahoney for (j = ((rbound = num - 1) + (lbound = 0)) / 2; 204ee93961bSJeff Mahoney lbound <= rbound; j = (rbound + lbound) / 2) 205bd4c625cSLinus Torvalds switch (comp_keys 206ee93961bSJeff Mahoney ((struct reiserfs_key *)((char *)base + j * width), 207d68caa95SJeff Mahoney (struct cpu_key *)key)) { 208bd4c625cSLinus Torvalds case -1: 209ee93961bSJeff Mahoney lbound = j + 1; 210bd4c625cSLinus Torvalds continue; 211bd4c625cSLinus Torvalds case 1: 212ee93961bSJeff Mahoney rbound = j - 1; 213bd4c625cSLinus Torvalds continue; 214bd4c625cSLinus Torvalds case 0: 215ee93961bSJeff Mahoney *pos = j; 216bd4c625cSLinus Torvalds return ITEM_FOUND; /* Key found in the array. */ 2171da177e4SLinus Torvalds } 2181da177e4SLinus Torvalds 2191da177e4SLinus Torvalds /* bin_search did not find given key, it returns position of key, 2201da177e4SLinus Torvalds that is minimal and greater than the given one. */ 221ee93961bSJeff Mahoney *pos = lbound; 2221da177e4SLinus Torvalds return ITEM_NOT_FOUND; 2231da177e4SLinus Torvalds } 2241da177e4SLinus Torvalds 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds /* Minimal possible key. It is never in the tree. */ 2271da177e4SLinus Torvalds const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} }; 2281da177e4SLinus Torvalds 2291da177e4SLinus Torvalds /* Maximal possible key. It is never in the tree. */ 23052c1da39SAdrian Bunk static const struct reiserfs_key MAX_KEY = { 2313e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2323e8962beSAl Viro __constant_cpu_to_le32(0xffffffff), 2333e8962beSAl Viro {{__constant_cpu_to_le32(0xffffffff), 2343e8962beSAl Viro __constant_cpu_to_le32(0xffffffff)},} 2353e8962beSAl Viro }; 2361da177e4SLinus Torvalds 2371da177e4SLinus Torvalds /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom 2381da177e4SLinus Torvalds of the path, and going upwards. We must check the path's validity at each step. If the key is not in 2391da177e4SLinus Torvalds the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this 2401da177e4SLinus Torvalds case we return a special key, either MIN_KEY or MAX_KEY. */ 241ee93961bSJeff Mahoney static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path, 242ee93961bSJeff Mahoney const struct super_block *sb) 243bd4c625cSLinus Torvalds { 244ee93961bSJeff Mahoney int position, path_offset = chk_path->path_length; 245d68caa95SJeff Mahoney struct buffer_head *parent; 2461da177e4SLinus Torvalds 247ee93961bSJeff Mahoney RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET, 2481da177e4SLinus Torvalds "PAP-5010: invalid offset in the path"); 2491da177e4SLinus Torvalds 2501da177e4SLinus Torvalds /* While not higher in path than first element. */ 251ee93961bSJeff Mahoney while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 2521da177e4SLinus Torvalds 253bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 254ee93961bSJeff Mahoney (PATH_OFFSET_PBUFFER(chk_path, path_offset)), 2551da177e4SLinus Torvalds "PAP-5020: parent is not uptodate"); 2561da177e4SLinus Torvalds 2571da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 258bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 259d68caa95SJeff Mahoney (parent = 260ee93961bSJeff Mahoney PATH_OFFSET_PBUFFER(chk_path, path_offset))) 2611da177e4SLinus Torvalds return &MAX_KEY; 2621da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 263ee93961bSJeff Mahoney if ((position = 264d68caa95SJeff Mahoney PATH_OFFSET_POSITION(chk_path, 265ee93961bSJeff Mahoney path_offset)) > 266d68caa95SJeff Mahoney B_NR_ITEMS(parent)) 2671da177e4SLinus Torvalds return &MAX_KEY; 2681da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 269ee93961bSJeff Mahoney if (B_N_CHILD_NUM(parent, position) != 270d68caa95SJeff Mahoney PATH_OFFSET_PBUFFER(chk_path, 271ee93961bSJeff Mahoney path_offset + 1)->b_blocknr) 2721da177e4SLinus Torvalds return &MAX_KEY; 2731da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not equal to zero. */ 274ee93961bSJeff Mahoney if (position) 275ee93961bSJeff Mahoney return B_N_PDELIM_KEY(parent, position - 1); 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds /* Return MIN_KEY if we are in the root of the buffer tree. */ 278d68caa95SJeff Mahoney if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 279a9dd3643SJeff Mahoney b_blocknr == SB_ROOT_BLOCK(sb)) 2801da177e4SLinus Torvalds return &MIN_KEY; 2811da177e4SLinus Torvalds return &MAX_KEY; 2821da177e4SLinus Torvalds } 2831da177e4SLinus Torvalds 2841da177e4SLinus Torvalds /* Get delimiting key of the buffer at the path and its right neighbor. */ 285d68caa95SJeff Mahoney inline const struct reiserfs_key *get_rkey(const struct treepath *chk_path, 286a9dd3643SJeff Mahoney const struct super_block *sb) 287bd4c625cSLinus Torvalds { 288ee93961bSJeff Mahoney int position, path_offset = chk_path->path_length; 289d68caa95SJeff Mahoney struct buffer_head *parent; 2901da177e4SLinus Torvalds 291ee93961bSJeff Mahoney RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET, 2921da177e4SLinus Torvalds "PAP-5030: invalid offset in the path"); 2931da177e4SLinus Torvalds 294ee93961bSJeff Mahoney while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { 2951da177e4SLinus Torvalds 296bd4c625cSLinus Torvalds RFALSE(!buffer_uptodate 297ee93961bSJeff Mahoney (PATH_OFFSET_PBUFFER(chk_path, path_offset)), 2981da177e4SLinus Torvalds "PAP-5040: parent is not uptodate"); 2991da177e4SLinus Torvalds 3001da177e4SLinus Torvalds /* Parent at the path is not in the tree now. */ 301bd4c625cSLinus Torvalds if (!B_IS_IN_TREE 302d68caa95SJeff Mahoney (parent = 303ee93961bSJeff Mahoney PATH_OFFSET_PBUFFER(chk_path, path_offset))) 3041da177e4SLinus Torvalds return &MIN_KEY; 3051da177e4SLinus Torvalds /* Check whether position in the parent is correct. */ 306ee93961bSJeff Mahoney if ((position = 307d68caa95SJeff Mahoney PATH_OFFSET_POSITION(chk_path, 308ee93961bSJeff Mahoney path_offset)) > 309d68caa95SJeff Mahoney B_NR_ITEMS(parent)) 3101da177e4SLinus Torvalds return &MIN_KEY; 3111da177e4SLinus Torvalds /* Check whether parent at the path really points to the child. */ 312ee93961bSJeff Mahoney if (B_N_CHILD_NUM(parent, position) != 313d68caa95SJeff Mahoney PATH_OFFSET_PBUFFER(chk_path, 314ee93961bSJeff Mahoney path_offset + 1)->b_blocknr) 3151da177e4SLinus Torvalds return &MIN_KEY; 3161da177e4SLinus Torvalds /* Return delimiting key if position in the parent is not the last one. */ 317ee93961bSJeff Mahoney if (position != B_NR_ITEMS(parent)) 318ee93961bSJeff Mahoney return B_N_PDELIM_KEY(parent, position); 3191da177e4SLinus Torvalds } 3201da177e4SLinus Torvalds /* Return MAX_KEY if we are in the root of the buffer tree. */ 321d68caa95SJeff Mahoney if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)-> 322a9dd3643SJeff Mahoney b_blocknr == SB_ROOT_BLOCK(sb)) 3231da177e4SLinus Torvalds return &MAX_KEY; 3241da177e4SLinus Torvalds return &MIN_KEY; 3251da177e4SLinus Torvalds } 3261da177e4SLinus Torvalds 3271da177e4SLinus Torvalds /* Check whether a key is contained in the tree rooted from a buffer at a path. */ 3281da177e4SLinus Torvalds /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in 3291da177e4SLinus Torvalds the path. These delimiting keys are stored at least one level above that buffer in the tree. If the 3301da177e4SLinus Torvalds buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in 3311da177e4SLinus Torvalds this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */ 332d68caa95SJeff Mahoney static inline int key_in_buffer(struct treepath *chk_path, /* Path which should be checked. */ 333d68caa95SJeff Mahoney const struct cpu_key *key, /* Key which should be checked. */ 334d68caa95SJeff Mahoney struct super_block *sb 335bd4c625cSLinus Torvalds ) 336bd4c625cSLinus Torvalds { 3371da177e4SLinus Torvalds 338d68caa95SJeff Mahoney RFALSE(!key || chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET 339d68caa95SJeff Mahoney || chk_path->path_length > MAX_HEIGHT, 3401da177e4SLinus Torvalds "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)", 341d68caa95SJeff Mahoney key, chk_path->path_length); 342d68caa95SJeff Mahoney RFALSE(!PATH_PLAST_BUFFER(chk_path)->b_bdev, 3431da177e4SLinus Torvalds "PAP-5060: device must not be NODEV"); 3441da177e4SLinus Torvalds 345d68caa95SJeff Mahoney if (comp_keys(get_lkey(chk_path, sb), key) == 1) 3461da177e4SLinus Torvalds /* left delimiting key is bigger, that the key we look for */ 3471da177e4SLinus Torvalds return 0; 348d68caa95SJeff Mahoney /* if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */ 349d68caa95SJeff Mahoney if (comp_keys(get_rkey(chk_path, sb), key) != 1) 350d68caa95SJeff Mahoney /* key must be less than right delimitiing key */ 3511da177e4SLinus Torvalds return 0; 3521da177e4SLinus Torvalds return 1; 3531da177e4SLinus Torvalds } 3541da177e4SLinus Torvalds 355fec6d055SJosef "Jeff" Sipek int reiserfs_check_path(struct treepath *p) 356bd4c625cSLinus Torvalds { 3571da177e4SLinus Torvalds RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET, 3581da177e4SLinus Torvalds "path not properly relsed"); 3591da177e4SLinus Torvalds return 0; 3601da177e4SLinus Torvalds } 3611da177e4SLinus Torvalds 3623cd6dbe6SJeff Mahoney /* Drop the reference to each buffer in a path and restore 3633cd6dbe6SJeff Mahoney * dirty bits clean when preparing the buffer for the log. 3643cd6dbe6SJeff Mahoney * This version should only be called from fix_nodes() */ 3653cd6dbe6SJeff Mahoney void pathrelse_and_restore(struct super_block *sb, 366d68caa95SJeff Mahoney struct treepath *search_path) 367bd4c625cSLinus Torvalds { 368ee93961bSJeff Mahoney int path_offset = search_path->path_length; 3691da177e4SLinus Torvalds 370ee93961bSJeff Mahoney RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 3711da177e4SLinus Torvalds "clm-4000: invalid path offset"); 3721da177e4SLinus Torvalds 373ee93961bSJeff Mahoney while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { 3743cd6dbe6SJeff Mahoney struct buffer_head *bh; 375ee93961bSJeff Mahoney bh = PATH_OFFSET_PBUFFER(search_path, path_offset--); 3763cd6dbe6SJeff Mahoney reiserfs_restore_prepared_buffer(sb, bh); 3773cd6dbe6SJeff Mahoney brelse(bh); 3781da177e4SLinus Torvalds } 379d68caa95SJeff Mahoney search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 3801da177e4SLinus Torvalds } 3811da177e4SLinus Torvalds 3823cd6dbe6SJeff Mahoney /* Drop the reference to each buffer in a path */ 383d68caa95SJeff Mahoney void pathrelse(struct treepath *search_path) 384bd4c625cSLinus Torvalds { 385ee93961bSJeff Mahoney int path_offset = search_path->path_length; 3861da177e4SLinus Torvalds 387ee93961bSJeff Mahoney RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 3881da177e4SLinus Torvalds "PAP-5090: invalid path offset"); 3891da177e4SLinus Torvalds 390ee93961bSJeff Mahoney while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) 391ee93961bSJeff Mahoney brelse(PATH_OFFSET_PBUFFER(search_path, path_offset--)); 3921da177e4SLinus Torvalds 393d68caa95SJeff Mahoney search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; 3941da177e4SLinus Torvalds } 3951da177e4SLinus Torvalds 3961da177e4SLinus Torvalds static int is_leaf(char *buf, int blocksize, struct buffer_head *bh) 3971da177e4SLinus Torvalds { 3981da177e4SLinus Torvalds struct block_head *blkh; 3991da177e4SLinus Torvalds struct item_head *ih; 4001da177e4SLinus Torvalds int used_space; 4011da177e4SLinus Torvalds int prev_location; 4021da177e4SLinus Torvalds int i; 4031da177e4SLinus Torvalds int nr; 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds blkh = (struct block_head *)buf; 4061da177e4SLinus Torvalds if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) { 40745b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5080", 40845b03d5eSJeff Mahoney "this should be caught earlier"); 4091da177e4SLinus Torvalds return 0; 4101da177e4SLinus Torvalds } 4111da177e4SLinus Torvalds 4121da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 4131da177e4SLinus Torvalds if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) { 4141da177e4SLinus Torvalds /* item number is too big or too small */ 41545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5081", 41645b03d5eSJeff Mahoney "nr_item seems wrong: %z", bh); 4171da177e4SLinus Torvalds return 0; 4181da177e4SLinus Torvalds } 4191da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1; 4201da177e4SLinus Torvalds used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih)); 4211da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 4221da177e4SLinus Torvalds /* free space does not match to calculated amount of use space */ 42345b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5082", 42445b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 4251da177e4SLinus Torvalds return 0; 4261da177e4SLinus Torvalds } 4271da177e4SLinus Torvalds // FIXME: it is_leaf will hit performance too much - we may have 4281da177e4SLinus Torvalds // return 1 here 4291da177e4SLinus Torvalds 4301da177e4SLinus Torvalds /* check tables of item heads */ 4311da177e4SLinus Torvalds ih = (struct item_head *)(buf + BLKH_SIZE); 4321da177e4SLinus Torvalds prev_location = blocksize; 4331da177e4SLinus Torvalds for (i = 0; i < nr; i++, ih++) { 4341da177e4SLinus Torvalds if (le_ih_k_type(ih) == TYPE_ANY) { 43545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5083", 43645b03d5eSJeff Mahoney "wrong item type for item %h", 437bd4c625cSLinus Torvalds ih); 4381da177e4SLinus Torvalds return 0; 4391da177e4SLinus Torvalds } 440bd4c625cSLinus Torvalds if (ih_location(ih) >= blocksize 441bd4c625cSLinus Torvalds || ih_location(ih) < IH_SIZE * nr) { 44245b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5084", 44345b03d5eSJeff Mahoney "item location seems wrong: %h", 444bd4c625cSLinus Torvalds ih); 4451da177e4SLinus Torvalds return 0; 4461da177e4SLinus Torvalds } 447bd4c625cSLinus Torvalds if (ih_item_len(ih) < 1 448bd4c625cSLinus Torvalds || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) { 44945b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5085", 45045b03d5eSJeff Mahoney "item length seems wrong: %h", 451bd4c625cSLinus Torvalds ih); 4521da177e4SLinus Torvalds return 0; 4531da177e4SLinus Torvalds } 4541da177e4SLinus Torvalds if (prev_location - ih_location(ih) != ih_item_len(ih)) { 45545b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5086", 45645b03d5eSJeff Mahoney "item location seems wrong " 45745b03d5eSJeff Mahoney "(second one): %h", ih); 4581da177e4SLinus Torvalds return 0; 4591da177e4SLinus Torvalds } 4601da177e4SLinus Torvalds prev_location = ih_location(ih); 4611da177e4SLinus Torvalds } 4621da177e4SLinus Torvalds 4631da177e4SLinus Torvalds // one may imagine much more checks 4641da177e4SLinus Torvalds return 1; 4651da177e4SLinus Torvalds } 4661da177e4SLinus Torvalds 4671da177e4SLinus Torvalds /* returns 1 if buf looks like an internal node, 0 otherwise */ 4681da177e4SLinus Torvalds static int is_internal(char *buf, int blocksize, struct buffer_head *bh) 4691da177e4SLinus Torvalds { 4701da177e4SLinus Torvalds struct block_head *blkh; 4711da177e4SLinus Torvalds int nr; 4721da177e4SLinus Torvalds int used_space; 4731da177e4SLinus Torvalds 4741da177e4SLinus Torvalds blkh = (struct block_head *)buf; 4751da177e4SLinus Torvalds nr = blkh_level(blkh); 4761da177e4SLinus Torvalds if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) { 4771da177e4SLinus Torvalds /* this level is not possible for internal nodes */ 47845b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5087", 47945b03d5eSJeff Mahoney "this should be caught earlier"); 4801da177e4SLinus Torvalds return 0; 4811da177e4SLinus Torvalds } 4821da177e4SLinus Torvalds 4831da177e4SLinus Torvalds nr = blkh_nr_item(blkh); 4841da177e4SLinus Torvalds if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) { 4851da177e4SLinus Torvalds /* for internal which is not root we might check min number of keys */ 48645b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5088", 48745b03d5eSJeff Mahoney "number of key seems wrong: %z", bh); 4881da177e4SLinus Torvalds return 0; 4891da177e4SLinus Torvalds } 4901da177e4SLinus Torvalds 4911da177e4SLinus Torvalds used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1); 4921da177e4SLinus Torvalds if (used_space != blocksize - blkh_free_space(blkh)) { 49345b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5089", 49445b03d5eSJeff Mahoney "free space seems wrong: %z", bh); 4951da177e4SLinus Torvalds return 0; 4961da177e4SLinus Torvalds } 4971da177e4SLinus Torvalds // one may imagine much more checks 4981da177e4SLinus Torvalds return 1; 4991da177e4SLinus Torvalds } 5001da177e4SLinus Torvalds 5011da177e4SLinus Torvalds // make sure that bh contains formatted node of reiserfs tree of 5021da177e4SLinus Torvalds // 'level'-th level 5031da177e4SLinus Torvalds static int is_tree_node(struct buffer_head *bh, int level) 5041da177e4SLinus Torvalds { 5051da177e4SLinus Torvalds if (B_LEVEL(bh) != level) { 50645b03d5eSJeff Mahoney reiserfs_warning(NULL, "reiserfs-5090", "node level %d does " 50745b03d5eSJeff Mahoney "not match to the expected one %d", 5081da177e4SLinus Torvalds B_LEVEL(bh), level); 5091da177e4SLinus Torvalds return 0; 5101da177e4SLinus Torvalds } 5111da177e4SLinus Torvalds if (level == DISK_LEAF_NODE_LEVEL) 5121da177e4SLinus Torvalds return is_leaf(bh->b_data, bh->b_size, bh); 5131da177e4SLinus Torvalds 5141da177e4SLinus Torvalds return is_internal(bh->b_data, bh->b_size, bh); 5151da177e4SLinus Torvalds } 5161da177e4SLinus Torvalds 5171da177e4SLinus Torvalds #define SEARCH_BY_KEY_READA 16 5181da177e4SLinus Torvalds 5192ac62695SFrederic Weisbecker /* 5202ac62695SFrederic Weisbecker * The function is NOT SCHEDULE-SAFE! 5212ac62695SFrederic Weisbecker * It might unlock the write lock if we needed to wait for a block 5222ac62695SFrederic Weisbecker * to be read. Note that in this case it won't recover the lock to avoid 5232ac62695SFrederic Weisbecker * high contention resulting from too much lock requests, especially 5242ac62695SFrederic Weisbecker * the caller (search_by_key) will perform other schedule-unsafe 5252ac62695SFrederic Weisbecker * operations just after calling this function. 5262ac62695SFrederic Weisbecker * 527278f6679SJeff Mahoney * @return depth of lock to be restored after read completes 5282ac62695SFrederic Weisbecker */ 529278f6679SJeff Mahoney static int search_by_key_reada(struct super_block *s, 5301da177e4SLinus Torvalds struct buffer_head **bh, 5313ee16670SJeff Mahoney b_blocknr_t *b, int num) 5321da177e4SLinus Torvalds { 5331da177e4SLinus Torvalds int i, j; 534278f6679SJeff Mahoney int depth = -1; 5351da177e4SLinus Torvalds 5361da177e4SLinus Torvalds for (i = 0; i < num; i++) { 5371da177e4SLinus Torvalds bh[i] = sb_getblk(s, b[i]); 5381da177e4SLinus Torvalds } 53909eb47a7SFrederic Weisbecker /* 54009eb47a7SFrederic Weisbecker * We are going to read some blocks on which we 54109eb47a7SFrederic Weisbecker * have a reference. It's safe, though we might be 54209eb47a7SFrederic Weisbecker * reading blocks concurrently changed if we release 54309eb47a7SFrederic Weisbecker * the lock. But it's still fine because we check later 54409eb47a7SFrederic Weisbecker * if the tree changed 54509eb47a7SFrederic Weisbecker */ 5461da177e4SLinus Torvalds for (j = 0; j < i; j++) { 5471da177e4SLinus Torvalds /* 5481da177e4SLinus Torvalds * note, this needs attention if we are getting rid of the BKL 5491da177e4SLinus Torvalds * you have to make sure the prepared bit isn't set on this buffer 5501da177e4SLinus Torvalds */ 5512ac62695SFrederic Weisbecker if (!buffer_uptodate(bh[j])) { 552278f6679SJeff Mahoney if (depth == -1) 553278f6679SJeff Mahoney depth = reiserfs_write_unlock_nested(s); 5541da177e4SLinus Torvalds ll_rw_block(READA, 1, bh + j); 5552ac62695SFrederic Weisbecker } 5561da177e4SLinus Torvalds brelse(bh[j]); 5571da177e4SLinus Torvalds } 558278f6679SJeff Mahoney return depth; 5591da177e4SLinus Torvalds } 5601da177e4SLinus Torvalds 5611da177e4SLinus Torvalds /************************************************************************** 5621da177e4SLinus Torvalds * Algorithm SearchByKey * 5631da177e4SLinus Torvalds * look for item in the Disk S+Tree by its key * 564a9dd3643SJeff Mahoney * Input: sb - super block * 565d68caa95SJeff Mahoney * key - pointer to the key to search * 5661da177e4SLinus Torvalds * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR * 567d68caa95SJeff Mahoney * search_path - path from the root to the needed leaf * 5681da177e4SLinus Torvalds **************************************************************************/ 5691da177e4SLinus Torvalds 5701da177e4SLinus Torvalds /* This function fills up the path from the root to the leaf as it 5711da177e4SLinus Torvalds descends the tree looking for the key. It uses reiserfs_bread to 5721da177e4SLinus Torvalds try to find buffers in the cache given their block number. If it 5731da177e4SLinus Torvalds does not find them in the cache it reads them from disk. For each 5741da177e4SLinus Torvalds node search_by_key finds using reiserfs_bread it then uses 5751da177e4SLinus Torvalds bin_search to look through that node. bin_search will find the 5761da177e4SLinus Torvalds position of the block_number of the next node if it is looking 5771da177e4SLinus Torvalds through an internal node. If it is looking through a leaf node 5781da177e4SLinus Torvalds bin_search will find the position of the item which has key either 5791da177e4SLinus Torvalds equal to given key, or which is the maximal key less than the given 5801da177e4SLinus Torvalds key. search_by_key returns a path that must be checked for the 5811da177e4SLinus Torvalds correctness of the top of the path but need not be checked for the 5821da177e4SLinus Torvalds correctness of the bottom of the path */ 5831da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 584d68caa95SJeff Mahoney int search_by_key(struct super_block *sb, const struct cpu_key *key, /* Key to search. */ 585d68caa95SJeff Mahoney struct treepath *search_path,/* This structure was 5861da177e4SLinus Torvalds allocated and initialized 5871da177e4SLinus Torvalds by the calling 5881da177e4SLinus Torvalds function. It is filled up 5891da177e4SLinus Torvalds by this function. */ 590ee93961bSJeff Mahoney int stop_level /* How far down the tree to search. To 5911da177e4SLinus Torvalds stop at leaf level - set to 5921da177e4SLinus Torvalds DISK_LEAF_NODE_LEVEL */ 593bd4c625cSLinus Torvalds ) 594bd4c625cSLinus Torvalds { 595ee93961bSJeff Mahoney b_blocknr_t block_number; 5961da177e4SLinus Torvalds int expected_level; 597ad31a4fcSJeff Mahoney struct buffer_head *bh; 598d68caa95SJeff Mahoney struct path_element *last_element; 599ee93961bSJeff Mahoney int node_level, retval; 6001da177e4SLinus Torvalds int right_neighbor_of_leaf_node; 6011da177e4SLinus Torvalds int fs_gen; 6021da177e4SLinus Torvalds struct buffer_head *reada_bh[SEARCH_BY_KEY_READA]; 6033ee16670SJeff Mahoney b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA]; 6041da177e4SLinus Torvalds int reada_count = 0; 6051da177e4SLinus Torvalds 6061da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 607ee93961bSJeff Mahoney int repeat_counter = 0; 6081da177e4SLinus Torvalds #endif 6091da177e4SLinus Torvalds 610a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key); 6111da177e4SLinus Torvalds 6121da177e4SLinus Torvalds /* As we add each node to a path we increase its count. This means that 6131da177e4SLinus Torvalds we must be careful to release all nodes in a path before we either 6141da177e4SLinus Torvalds discard the path struct or re-use the path struct, as we do here. */ 6151da177e4SLinus Torvalds 616d68caa95SJeff Mahoney pathrelse(search_path); 6171da177e4SLinus Torvalds 6181da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6191da177e4SLinus Torvalds 6201da177e4SLinus Torvalds /* With each iteration of this loop we search through the items in the 6211da177e4SLinus Torvalds current node, and calculate the next current node(next path element) 6221da177e4SLinus Torvalds for the next iteration of this loop.. */ 623ee93961bSJeff Mahoney block_number = SB_ROOT_BLOCK(sb); 6241da177e4SLinus Torvalds expected_level = -1; 6251da177e4SLinus Torvalds while (1) { 6261da177e4SLinus Torvalds 6271da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 628ee93961bSJeff Mahoney if (!(++repeat_counter % 50000)) 629a9dd3643SJeff Mahoney reiserfs_warning(sb, "PAP-5100", 63045b03d5eSJeff Mahoney "%s: there were %d iterations of " 63145b03d5eSJeff Mahoney "while loop looking for key %K", 632ee93961bSJeff Mahoney current->comm, repeat_counter, 633d68caa95SJeff Mahoney key); 6341da177e4SLinus Torvalds #endif 6351da177e4SLinus Torvalds 6361da177e4SLinus Torvalds /* prep path to have another element added to it. */ 637d68caa95SJeff Mahoney last_element = 638d68caa95SJeff Mahoney PATH_OFFSET_PELEMENT(search_path, 639d68caa95SJeff Mahoney ++search_path->path_length); 640a9dd3643SJeff Mahoney fs_gen = get_generation(sb); 6411da177e4SLinus Torvalds 6421da177e4SLinus Torvalds /* Read the next tree node, and set the last element in the path to 6431da177e4SLinus Torvalds have a pointer to it. */ 644d68caa95SJeff Mahoney if ((bh = last_element->pe_buffer = 645ee93961bSJeff Mahoney sb_getblk(sb, block_number))) { 646278f6679SJeff Mahoney 647278f6679SJeff Mahoney /* 648278f6679SJeff Mahoney * We'll need to drop the lock if we encounter any 649278f6679SJeff Mahoney * buffers that need to be read. If all of them are 650278f6679SJeff Mahoney * already up to date, we don't need to drop the lock. 651278f6679SJeff Mahoney */ 652278f6679SJeff Mahoney int depth = -1; 6532ac62695SFrederic Weisbecker 654ad31a4fcSJeff Mahoney if (!buffer_uptodate(bh) && reada_count > 1) 655278f6679SJeff Mahoney depth = search_by_key_reada(sb, reada_bh, 6561da177e4SLinus Torvalds reada_blocks, reada_count); 657278f6679SJeff Mahoney 658278f6679SJeff Mahoney if (!buffer_uptodate(bh) && depth == -1) 659278f6679SJeff Mahoney depth = reiserfs_write_unlock_nested(sb); 660278f6679SJeff Mahoney 66109eb47a7SFrederic Weisbecker ll_rw_block(READ, 1, &bh); 662ad31a4fcSJeff Mahoney wait_on_buffer(bh); 6632ac62695SFrederic Weisbecker 664278f6679SJeff Mahoney if (depth != -1) 665278f6679SJeff Mahoney reiserfs_write_lock_nested(sb, depth); 666ad31a4fcSJeff Mahoney if (!buffer_uptodate(bh)) 6671da177e4SLinus Torvalds goto io_error; 6681da177e4SLinus Torvalds } else { 6691da177e4SLinus Torvalds io_error: 670d68caa95SJeff Mahoney search_path->path_length--; 671d68caa95SJeff Mahoney pathrelse(search_path); 6721da177e4SLinus Torvalds return IO_ERROR; 6731da177e4SLinus Torvalds } 6741da177e4SLinus Torvalds reada_count = 0; 6751da177e4SLinus Torvalds if (expected_level == -1) 676a9dd3643SJeff Mahoney expected_level = SB_TREE_HEIGHT(sb); 6771da177e4SLinus Torvalds expected_level--; 6781da177e4SLinus Torvalds 6791da177e4SLinus Torvalds /* It is possible that schedule occurred. We must check whether the key 6801da177e4SLinus Torvalds to search is still in the tree rooted from the current buffer. If 6811da177e4SLinus Torvalds not then repeat search from the root. */ 682a9dd3643SJeff Mahoney if (fs_changed(fs_gen, sb) && 683ad31a4fcSJeff Mahoney (!B_IS_IN_TREE(bh) || 684ad31a4fcSJeff Mahoney B_LEVEL(bh) != expected_level || 685d68caa95SJeff Mahoney !key_in_buffer(search_path, key, sb))) { 686a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key_fs_changed); 687a9dd3643SJeff Mahoney PROC_INFO_INC(sb, search_by_key_restarted); 688a9dd3643SJeff Mahoney PROC_INFO_INC(sb, 689bd4c625cSLinus Torvalds sbk_restarted[expected_level - 1]); 690d68caa95SJeff Mahoney pathrelse(search_path); 6911da177e4SLinus Torvalds 6921da177e4SLinus Torvalds /* Get the root block number so that we can repeat the search 6931da177e4SLinus Torvalds starting from the root. */ 694ee93961bSJeff Mahoney block_number = SB_ROOT_BLOCK(sb); 6951da177e4SLinus Torvalds expected_level = -1; 6961da177e4SLinus Torvalds right_neighbor_of_leaf_node = 0; 6971da177e4SLinus Torvalds 6981da177e4SLinus Torvalds /* repeat search from the root */ 6991da177e4SLinus Torvalds continue; 7001da177e4SLinus Torvalds } 7011da177e4SLinus Torvalds 702d68caa95SJeff Mahoney /* only check that the key is in the buffer if key is not 7031da177e4SLinus Torvalds equal to the MAX_KEY. Latter case is only possible in 7041da177e4SLinus Torvalds "finish_unfinished()" processing during mount. */ 705d68caa95SJeff Mahoney RFALSE(comp_keys(&MAX_KEY, key) && 706d68caa95SJeff Mahoney !key_in_buffer(search_path, key, sb), 7071da177e4SLinus Torvalds "PAP-5130: key is not in the buffer"); 7081da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 70908f14fc8SFrederic Weisbecker if (REISERFS_SB(sb)->cur_tb) { 7101da177e4SLinus Torvalds print_cur_tb("5140"); 711a9dd3643SJeff Mahoney reiserfs_panic(sb, "PAP-5140", 712c3a9c210SJeff Mahoney "schedule occurred in do_balance!"); 7131da177e4SLinus Torvalds } 7141da177e4SLinus Torvalds #endif 7151da177e4SLinus Torvalds 7161da177e4SLinus Torvalds // make sure, that the node contents look like a node of 7171da177e4SLinus Torvalds // certain level 718ad31a4fcSJeff Mahoney if (!is_tree_node(bh, expected_level)) { 719a9dd3643SJeff Mahoney reiserfs_error(sb, "vs-5150", 72045b03d5eSJeff Mahoney "invalid format found in block %ld. " 721ad31a4fcSJeff Mahoney "Fsck?", bh->b_blocknr); 722d68caa95SJeff Mahoney pathrelse(search_path); 7231da177e4SLinus Torvalds return IO_ERROR; 7241da177e4SLinus Torvalds } 7251da177e4SLinus Torvalds 7261da177e4SLinus Torvalds /* ok, we have acquired next formatted node in the tree */ 727ee93961bSJeff Mahoney node_level = B_LEVEL(bh); 7281da177e4SLinus Torvalds 729ee93961bSJeff Mahoney PROC_INFO_BH_STAT(sb, bh, node_level - 1); 7301da177e4SLinus Torvalds 731ee93961bSJeff Mahoney RFALSE(node_level < stop_level, 7321da177e4SLinus Torvalds "vs-5152: tree level (%d) is less than stop level (%d)", 733ee93961bSJeff Mahoney node_level, stop_level); 7341da177e4SLinus Torvalds 735ee93961bSJeff Mahoney retval = bin_search(key, B_N_PITEM_HEAD(bh, 0), 736ad31a4fcSJeff Mahoney B_NR_ITEMS(bh), 737ee93961bSJeff Mahoney (node_level == 738bd4c625cSLinus Torvalds DISK_LEAF_NODE_LEVEL) ? IH_SIZE : 739bd4c625cSLinus Torvalds KEY_SIZE, 740d68caa95SJeff Mahoney &(last_element->pe_position)); 741ee93961bSJeff Mahoney if (node_level == stop_level) { 742ee93961bSJeff Mahoney return retval; 7431da177e4SLinus Torvalds } 7441da177e4SLinus Torvalds 7451da177e4SLinus Torvalds /* we are not in the stop level */ 746ee93961bSJeff Mahoney if (retval == ITEM_FOUND) 7471da177e4SLinus Torvalds /* item has been found, so we choose the pointer which is to the right of the found one */ 748d68caa95SJeff Mahoney last_element->pe_position++; 7491da177e4SLinus Torvalds 7501da177e4SLinus Torvalds /* if item was not found we choose the position which is to 7511da177e4SLinus Torvalds the left of the found item. This requires no code, 7521da177e4SLinus Torvalds bin_search did it already. */ 7531da177e4SLinus Torvalds 7541da177e4SLinus Torvalds /* So we have chosen a position in the current node which is 7551da177e4SLinus Torvalds an internal node. Now we calculate child block number by 7561da177e4SLinus Torvalds position in the node. */ 757ee93961bSJeff Mahoney block_number = 758d68caa95SJeff Mahoney B_N_CHILD_NUM(bh, last_element->pe_position); 7591da177e4SLinus Torvalds 7601da177e4SLinus Torvalds /* if we are going to read leaf nodes, try for read ahead as well */ 761d68caa95SJeff Mahoney if ((search_path->reada & PATH_READA) && 762ee93961bSJeff Mahoney node_level == DISK_LEAF_NODE_LEVEL + 1) { 763d68caa95SJeff Mahoney int pos = last_element->pe_position; 764ad31a4fcSJeff Mahoney int limit = B_NR_ITEMS(bh); 7651da177e4SLinus Torvalds struct reiserfs_key *le_key; 7661da177e4SLinus Torvalds 767d68caa95SJeff Mahoney if (search_path->reada & PATH_READA_BACK) 7681da177e4SLinus Torvalds limit = 0; 7691da177e4SLinus Torvalds while (reada_count < SEARCH_BY_KEY_READA) { 7701da177e4SLinus Torvalds if (pos == limit) 7711da177e4SLinus Torvalds break; 772bd4c625cSLinus Torvalds reada_blocks[reada_count++] = 773ad31a4fcSJeff Mahoney B_N_CHILD_NUM(bh, pos); 774d68caa95SJeff Mahoney if (search_path->reada & PATH_READA_BACK) 7751da177e4SLinus Torvalds pos--; 7761da177e4SLinus Torvalds else 7771da177e4SLinus Torvalds pos++; 7781da177e4SLinus Torvalds 7791da177e4SLinus Torvalds /* 7801da177e4SLinus Torvalds * check to make sure we're in the same object 7811da177e4SLinus Torvalds */ 782ad31a4fcSJeff Mahoney le_key = B_N_PDELIM_KEY(bh, pos); 7831da177e4SLinus Torvalds if (le32_to_cpu(le_key->k_objectid) != 784d68caa95SJeff Mahoney key->on_disk_key.k_objectid) { 7851da177e4SLinus Torvalds break; 7861da177e4SLinus Torvalds } 7871da177e4SLinus Torvalds } 7881da177e4SLinus Torvalds } 7891da177e4SLinus Torvalds } 7901da177e4SLinus Torvalds } 7911da177e4SLinus Torvalds 7921da177e4SLinus Torvalds /* Form the path to an item and position in this item which contains 793d68caa95SJeff Mahoney file byte defined by key. If there is no such item 7941da177e4SLinus Torvalds corresponding to the key, we point the path to the item with 795d68caa95SJeff Mahoney maximal key less than key, and *pos_in_item is set to one 7961da177e4SLinus Torvalds past the last entry/byte in the item. If searching for entry in a 797d68caa95SJeff Mahoney directory item, and it is not found, *pos_in_item is set to one 7981da177e4SLinus Torvalds entry more than the entry with maximal key which is less than the 7991da177e4SLinus Torvalds sought key. 8001da177e4SLinus Torvalds 8011da177e4SLinus Torvalds Note that if there is no entry in this same node which is one more, 8021da177e4SLinus Torvalds then we point to an imaginary entry. for direct items, the 8031da177e4SLinus Torvalds position is in units of bytes, for indirect items the position is 8041da177e4SLinus Torvalds in units of blocknr entries, for directory items the position is in 8051da177e4SLinus Torvalds units of directory entries. */ 8061da177e4SLinus Torvalds 8071da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */ 808a9dd3643SJeff Mahoney int search_for_position_by_key(struct super_block *sb, /* Pointer to the super block. */ 8091da177e4SLinus Torvalds const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */ 810d68caa95SJeff Mahoney struct treepath *search_path /* Filled up by this function. */ 811bd4c625cSLinus Torvalds ) 812bd4c625cSLinus Torvalds { 8131da177e4SLinus Torvalds struct item_head *p_le_ih; /* pointer to on-disk structure */ 814ee93961bSJeff Mahoney int blk_size; 8151da177e4SLinus Torvalds loff_t item_offset, offset; 8161da177e4SLinus Torvalds struct reiserfs_dir_entry de; 8171da177e4SLinus Torvalds int retval; 8181da177e4SLinus Torvalds 8191da177e4SLinus Torvalds /* If searching for directory entry. */ 8201da177e4SLinus Torvalds if (is_direntry_cpu_key(p_cpu_key)) 821d68caa95SJeff Mahoney return search_by_entry_key(sb, p_cpu_key, search_path, 822bd4c625cSLinus Torvalds &de); 8231da177e4SLinus Torvalds 8241da177e4SLinus Torvalds /* If not searching for directory entry. */ 8251da177e4SLinus Torvalds 8261da177e4SLinus Torvalds /* If item is found. */ 827d68caa95SJeff Mahoney retval = search_item(sb, p_cpu_key, search_path); 8281da177e4SLinus Torvalds if (retval == IO_ERROR) 8291da177e4SLinus Torvalds return retval; 8301da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 8311da177e4SLinus Torvalds 832bd4c625cSLinus Torvalds RFALSE(!ih_item_len 833bd4c625cSLinus Torvalds (B_N_PITEM_HEAD 834d68caa95SJeff Mahoney (PATH_PLAST_BUFFER(search_path), 835d68caa95SJeff Mahoney PATH_LAST_POSITION(search_path))), 8361da177e4SLinus Torvalds "PAP-5165: item length equals zero"); 8371da177e4SLinus Torvalds 838d68caa95SJeff Mahoney pos_in_item(search_path) = 0; 8391da177e4SLinus Torvalds return POSITION_FOUND; 8401da177e4SLinus Torvalds } 8411da177e4SLinus Torvalds 842d68caa95SJeff Mahoney RFALSE(!PATH_LAST_POSITION(search_path), 8431da177e4SLinus Torvalds "PAP-5170: position equals zero"); 8441da177e4SLinus Torvalds 8451da177e4SLinus Torvalds /* Item is not found. Set path to the previous item. */ 846bd4c625cSLinus Torvalds p_le_ih = 847d68caa95SJeff Mahoney B_N_PITEM_HEAD(PATH_PLAST_BUFFER(search_path), 848d68caa95SJeff Mahoney --PATH_LAST_POSITION(search_path)); 849ee93961bSJeff Mahoney blk_size = sb->s_blocksize; 8501da177e4SLinus Torvalds 8511da177e4SLinus Torvalds if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) { 8521da177e4SLinus Torvalds return FILE_NOT_FOUND; 8531da177e4SLinus Torvalds } 8541da177e4SLinus Torvalds // FIXME: quite ugly this far 8551da177e4SLinus Torvalds 8561da177e4SLinus Torvalds item_offset = le_ih_k_offset(p_le_ih); 8571da177e4SLinus Torvalds offset = cpu_key_k_offset(p_cpu_key); 8581da177e4SLinus Torvalds 8591da177e4SLinus Torvalds /* Needed byte is contained in the item pointed to by the path. */ 8601da177e4SLinus Torvalds if (item_offset <= offset && 861ee93961bSJeff Mahoney item_offset + op_bytes_number(p_le_ih, blk_size) > offset) { 862d68caa95SJeff Mahoney pos_in_item(search_path) = offset - item_offset; 8631da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) { 864ee93961bSJeff Mahoney pos_in_item(search_path) /= blk_size; 8651da177e4SLinus Torvalds } 8661da177e4SLinus Torvalds return POSITION_FOUND; 8671da177e4SLinus Torvalds } 8681da177e4SLinus Torvalds 8691da177e4SLinus Torvalds /* Needed byte is not contained in the item pointed to by the 8701da177e4SLinus Torvalds path. Set pos_in_item out of the item. */ 8711da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 872d68caa95SJeff Mahoney pos_in_item(search_path) = 873bd4c625cSLinus Torvalds ih_item_len(p_le_ih) / UNFM_P_SIZE; 8741da177e4SLinus Torvalds else 875d68caa95SJeff Mahoney pos_in_item(search_path) = ih_item_len(p_le_ih); 8761da177e4SLinus Torvalds 8771da177e4SLinus Torvalds return POSITION_NOT_FOUND; 8781da177e4SLinus Torvalds } 8791da177e4SLinus Torvalds 8801da177e4SLinus Torvalds /* Compare given item and item pointed to by the path. */ 881d68caa95SJeff Mahoney int comp_items(const struct item_head *stored_ih, const struct treepath *path) 8821da177e4SLinus Torvalds { 883d68caa95SJeff Mahoney struct buffer_head *bh = PATH_PLAST_BUFFER(path); 8841da177e4SLinus Torvalds struct item_head *ih; 8851da177e4SLinus Torvalds 8861da177e4SLinus Torvalds /* Last buffer at the path is not in the tree. */ 887ad31a4fcSJeff Mahoney if (!B_IS_IN_TREE(bh)) 8881da177e4SLinus Torvalds return 1; 8891da177e4SLinus Torvalds 8901da177e4SLinus Torvalds /* Last path position is invalid. */ 891d68caa95SJeff Mahoney if (PATH_LAST_POSITION(path) >= B_NR_ITEMS(bh)) 8921da177e4SLinus Torvalds return 1; 8931da177e4SLinus Torvalds 8941da177e4SLinus Torvalds /* we need only to know, whether it is the same item */ 895d68caa95SJeff Mahoney ih = get_ih(path); 8961da177e4SLinus Torvalds return memcmp(stored_ih, ih, IH_SIZE); 8971da177e4SLinus Torvalds } 8981da177e4SLinus Torvalds 8991da177e4SLinus Torvalds /* unformatted nodes are not logged anymore, ever. This is safe 9001da177e4SLinus Torvalds ** now 9011da177e4SLinus Torvalds */ 9021da177e4SLinus Torvalds #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1) 9031da177e4SLinus Torvalds 9041da177e4SLinus Torvalds // block can not be forgotten as it is in I/O or held by someone 9051da177e4SLinus Torvalds #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh))) 9061da177e4SLinus Torvalds 9071da177e4SLinus Torvalds // prepare for delete or cut of direct item 908fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direct_item(struct treepath *path, 9091da177e4SLinus Torvalds struct item_head *le_ih, 9101da177e4SLinus Torvalds struct inode *inode, 911bd4c625cSLinus Torvalds loff_t new_file_length, int *cut_size) 9121da177e4SLinus Torvalds { 9131da177e4SLinus Torvalds loff_t round_len; 9141da177e4SLinus Torvalds 9151da177e4SLinus Torvalds if (new_file_length == max_reiserfs_offset(inode)) { 9161da177e4SLinus Torvalds /* item has to be deleted */ 9171da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9181da177e4SLinus Torvalds return M_DELETE; 9191da177e4SLinus Torvalds } 9201da177e4SLinus Torvalds // new file gets truncated 9211da177e4SLinus Torvalds if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) { 9221da177e4SLinus Torvalds // 9231da177e4SLinus Torvalds round_len = ROUND_UP(new_file_length); 924ee93961bSJeff Mahoney /* this was new_file_length < le_ih ... */ 9251da177e4SLinus Torvalds if (round_len < le_ih_k_offset(le_ih)) { 9261da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9271da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9281da177e4SLinus Torvalds } 9291da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9301da177e4SLinus Torvalds pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1); 9311da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - pos_in_item(path)); 9321da177e4SLinus Torvalds 9331da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9341da177e4SLinus Torvalds } 9351da177e4SLinus Torvalds 9361da177e4SLinus Torvalds // old file: items may have any length 9371da177e4SLinus Torvalds 9381da177e4SLinus Torvalds if (new_file_length < le_ih_k_offset(le_ih)) { 9391da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9401da177e4SLinus Torvalds return M_DELETE; /* Delete this item. */ 9411da177e4SLinus Torvalds } 9421da177e4SLinus Torvalds /* Calculate first position and size for cutting from item. */ 9431da177e4SLinus Torvalds *cut_size = -(ih_item_len(le_ih) - 944bd4c625cSLinus Torvalds (pos_in_item(path) = 945bd4c625cSLinus Torvalds new_file_length + 1 - le_ih_k_offset(le_ih))); 9461da177e4SLinus Torvalds return M_CUT; /* Cut from this item. */ 9471da177e4SLinus Torvalds } 9481da177e4SLinus Torvalds 949fec6d055SJosef "Jeff" Sipek static inline int prepare_for_direntry_item(struct treepath *path, 9501da177e4SLinus Torvalds struct item_head *le_ih, 9511da177e4SLinus Torvalds struct inode *inode, 9521da177e4SLinus Torvalds loff_t new_file_length, 9531da177e4SLinus Torvalds int *cut_size) 9541da177e4SLinus Torvalds { 9551da177e4SLinus Torvalds if (le_ih_k_offset(le_ih) == DOT_OFFSET && 9561da177e4SLinus Torvalds new_file_length == max_reiserfs_offset(inode)) { 9571da177e4SLinus Torvalds RFALSE(ih_entry_count(le_ih) != 2, 9581da177e4SLinus Torvalds "PAP-5220: incorrect empty directory item (%h)", le_ih); 9591da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9601da177e4SLinus Torvalds return M_DELETE; /* Delete the directory item containing "." and ".." entry. */ 9611da177e4SLinus Torvalds } 9621da177e4SLinus Torvalds 9631da177e4SLinus Torvalds if (ih_entry_count(le_ih) == 1) { 9641da177e4SLinus Torvalds /* Delete the directory item such as there is one record only 9651da177e4SLinus Torvalds in this item */ 9661da177e4SLinus Torvalds *cut_size = -(IH_SIZE + ih_item_len(le_ih)); 9671da177e4SLinus Torvalds return M_DELETE; 9681da177e4SLinus Torvalds } 9691da177e4SLinus Torvalds 9701da177e4SLinus Torvalds /* Cut one record from the directory item. */ 971bd4c625cSLinus Torvalds *cut_size = 972bd4c625cSLinus Torvalds -(DEH_SIZE + 973bd4c625cSLinus Torvalds entry_length(get_last_bh(path), le_ih, pos_in_item(path))); 9741da177e4SLinus Torvalds return M_CUT; 9751da177e4SLinus Torvalds } 9761da177e4SLinus Torvalds 97723f9e0f8SAlexander Zarochentzev #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1) 97823f9e0f8SAlexander Zarochentzev 9791da177e4SLinus Torvalds /* If the path points to a directory or direct item, calculate mode and the size cut, for balance. 9801da177e4SLinus Torvalds If the path points to an indirect item, remove some number of its unformatted nodes. 9811da177e4SLinus Torvalds In case of file truncate calculate whether this item must be deleted/truncated or last 9821da177e4SLinus Torvalds unformatted node of this item will be converted to a direct item. 9831da177e4SLinus Torvalds This function returns a determination of what balance mode the calling function should employ. */ 984d68caa95SJeff Mahoney static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *path, const struct cpu_key *item_key, int *removed, /* Number of unformatted nodes which were removed 9851da177e4SLinus Torvalds from end of the file. */ 986ee93961bSJeff Mahoney int *cut_size, unsigned long long new_file_length /* MAX_KEY_OFFSET in case of delete. */ 987bd4c625cSLinus Torvalds ) 988bd4c625cSLinus Torvalds { 989a9dd3643SJeff Mahoney struct super_block *sb = inode->i_sb; 990d68caa95SJeff Mahoney struct item_head *p_le_ih = PATH_PITEM_HEAD(path); 991d68caa95SJeff Mahoney struct buffer_head *bh = PATH_PLAST_BUFFER(path); 9921da177e4SLinus Torvalds 9931da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 9941da177e4SLinus Torvalds 9951da177e4SLinus Torvalds /* Stat_data item. */ 9961da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) { 9971da177e4SLinus Torvalds 998ee93961bSJeff Mahoney RFALSE(new_file_length != max_reiserfs_offset(inode), 9991da177e4SLinus Torvalds "PAP-5210: mode must be M_DELETE"); 10001da177e4SLinus Torvalds 1001d68caa95SJeff Mahoney *cut_size = -(IH_SIZE + ih_item_len(p_le_ih)); 10021da177e4SLinus Torvalds return M_DELETE; 10031da177e4SLinus Torvalds } 10041da177e4SLinus Torvalds 10051da177e4SLinus Torvalds /* Directory item. */ 10061da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) 1007d68caa95SJeff Mahoney return prepare_for_direntry_item(path, p_le_ih, inode, 1008ee93961bSJeff Mahoney new_file_length, 1009d68caa95SJeff Mahoney cut_size); 10101da177e4SLinus Torvalds 10111da177e4SLinus Torvalds /* Direct item. */ 10121da177e4SLinus Torvalds if (is_direct_le_ih(p_le_ih)) 1013d68caa95SJeff Mahoney return prepare_for_direct_item(path, p_le_ih, inode, 1014ee93961bSJeff Mahoney new_file_length, cut_size); 10151da177e4SLinus Torvalds 10161da177e4SLinus Torvalds /* Case of an indirect item. */ 10171da177e4SLinus Torvalds { 1018a9dd3643SJeff Mahoney int blk_size = sb->s_blocksize; 101923f9e0f8SAlexander Zarochentzev struct item_head s_ih; 102023f9e0f8SAlexander Zarochentzev int need_re_search; 102123f9e0f8SAlexander Zarochentzev int delete = 0; 102223f9e0f8SAlexander Zarochentzev int result = M_CUT; 102323f9e0f8SAlexander Zarochentzev int pos = 0; 10241da177e4SLinus Torvalds 1025ee93961bSJeff Mahoney if ( new_file_length == max_reiserfs_offset (inode) ) { 102623f9e0f8SAlexander Zarochentzev /* prepare_for_delete_or_cut() is called by 102723f9e0f8SAlexander Zarochentzev * reiserfs_delete_item() */ 1028ee93961bSJeff Mahoney new_file_length = 0; 102923f9e0f8SAlexander Zarochentzev delete = 1; 103023f9e0f8SAlexander Zarochentzev } 10311da177e4SLinus Torvalds 10321da177e4SLinus Torvalds do { 103323f9e0f8SAlexander Zarochentzev need_re_search = 0; 1034d68caa95SJeff Mahoney *cut_size = 0; 1035d68caa95SJeff Mahoney bh = PATH_PLAST_BUFFER(path); 1036d68caa95SJeff Mahoney copy_item_head(&s_ih, PATH_PITEM_HEAD(path)); 103723f9e0f8SAlexander Zarochentzev pos = I_UNFM_NUM(&s_ih); 10381da177e4SLinus Torvalds 1039ee93961bSJeff Mahoney while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > new_file_length) { 104087588dd6SAl Viro __le32 *unfm; 104187588dd6SAl Viro __u32 block; 10421da177e4SLinus Torvalds 104323f9e0f8SAlexander Zarochentzev /* Each unformatted block deletion may involve one additional 104423f9e0f8SAlexander Zarochentzev * bitmap block into the transaction, thereby the initial 104523f9e0f8SAlexander Zarochentzev * journal space reservation might not be enough. */ 1046d68caa95SJeff Mahoney if (!delete && (*cut_size) != 0 && 1047d68caa95SJeff Mahoney reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) 104823f9e0f8SAlexander Zarochentzev break; 10491da177e4SLinus Torvalds 1050ad31a4fcSJeff Mahoney unfm = (__le32 *)B_I_PITEM(bh, &s_ih) + pos - 1; 105123f9e0f8SAlexander Zarochentzev block = get_block_num(unfm, 0); 10521da177e4SLinus Torvalds 105323f9e0f8SAlexander Zarochentzev if (block != 0) { 1054ad31a4fcSJeff Mahoney reiserfs_prepare_for_journal(sb, bh, 1); 105523f9e0f8SAlexander Zarochentzev put_block_num(unfm, 0, 0); 1056ad31a4fcSJeff Mahoney journal_mark_dirty(th, sb, bh); 105723f9e0f8SAlexander Zarochentzev reiserfs_free_block(th, inode, block, 1); 105823f9e0f8SAlexander Zarochentzev } 10591da177e4SLinus Torvalds 1060278f6679SJeff Mahoney reiserfs_cond_resched(sb); 106123f9e0f8SAlexander Zarochentzev 1062d68caa95SJeff Mahoney if (item_moved (&s_ih, path)) { 106323f9e0f8SAlexander Zarochentzev need_re_search = 1; 10641da177e4SLinus Torvalds break; 10651da177e4SLinus Torvalds } 10661da177e4SLinus Torvalds 106723f9e0f8SAlexander Zarochentzev pos --; 1068d68caa95SJeff Mahoney (*removed)++; 1069d68caa95SJeff Mahoney (*cut_size) -= UNFM_P_SIZE; 10701da177e4SLinus Torvalds 107123f9e0f8SAlexander Zarochentzev if (pos == 0) { 1072d68caa95SJeff Mahoney (*cut_size) -= IH_SIZE; 107323f9e0f8SAlexander Zarochentzev result = M_DELETE; 10741da177e4SLinus Torvalds break; 10751da177e4SLinus Torvalds } 10761da177e4SLinus Torvalds } 107723f9e0f8SAlexander Zarochentzev /* a trick. If the buffer has been logged, this will do nothing. If 107823f9e0f8SAlexander Zarochentzev ** we've broken the loop without logging it, it will restore the 107923f9e0f8SAlexander Zarochentzev ** buffer */ 1080ad31a4fcSJeff Mahoney reiserfs_restore_prepared_buffer(sb, bh); 108123f9e0f8SAlexander Zarochentzev } while (need_re_search && 1082d68caa95SJeff Mahoney search_for_position_by_key(sb, item_key, path) == POSITION_FOUND); 1083d68caa95SJeff Mahoney pos_in_item(path) = pos * UNFM_P_SIZE; 10841da177e4SLinus Torvalds 1085d68caa95SJeff Mahoney if (*cut_size == 0) { 108623f9e0f8SAlexander Zarochentzev /* Nothing were cut. maybe convert last unformatted node to the 108723f9e0f8SAlexander Zarochentzev * direct item? */ 108823f9e0f8SAlexander Zarochentzev result = M_CONVERT; 108923f9e0f8SAlexander Zarochentzev } 109023f9e0f8SAlexander Zarochentzev return result; 10911da177e4SLinus Torvalds } 10921da177e4SLinus Torvalds } 10931da177e4SLinus Torvalds 10941da177e4SLinus Torvalds /* Calculate number of bytes which will be deleted or cut during balance */ 1095ee93961bSJeff Mahoney static int calc_deleted_bytes_number(struct tree_balance *tb, char mode) 1096bd4c625cSLinus Torvalds { 1097ee93961bSJeff Mahoney int del_size; 1098a063ae17SJeff Mahoney struct item_head *p_le_ih = PATH_PITEM_HEAD(tb->tb_path); 10991da177e4SLinus Torvalds 11001da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 11011da177e4SLinus Torvalds return 0; 11021da177e4SLinus Torvalds 1103ee93961bSJeff Mahoney del_size = 1104ee93961bSJeff Mahoney (mode == 1105a063ae17SJeff Mahoney M_DELETE) ? ih_item_len(p_le_ih) : -tb->insert_size[0]; 11061da177e4SLinus Torvalds if (is_direntry_le_ih(p_le_ih)) { 1107ee93961bSJeff Mahoney /* return EMPTY_DIR_SIZE; We delete emty directoris only. 1108ee93961bSJeff Mahoney * we can't use EMPTY_DIR_SIZE, as old format dirs have a different 1109ee93961bSJeff Mahoney * empty size. ick. FIXME, is this right? */ 1110ee93961bSJeff Mahoney return del_size; 11111da177e4SLinus Torvalds } 11121da177e4SLinus Torvalds 11131da177e4SLinus Torvalds if (is_indirect_le_ih(p_le_ih)) 1114ee93961bSJeff Mahoney del_size = (del_size / UNFM_P_SIZE) * 1115a063ae17SJeff Mahoney (PATH_PLAST_BUFFER(tb->tb_path)->b_size); 1116ee93961bSJeff Mahoney return del_size; 11171da177e4SLinus Torvalds } 11181da177e4SLinus Torvalds 1119bd4c625cSLinus Torvalds static void init_tb_struct(struct reiserfs_transaction_handle *th, 1120a063ae17SJeff Mahoney struct tree_balance *tb, 1121a9dd3643SJeff Mahoney struct super_block *sb, 1122ee93961bSJeff Mahoney struct treepath *path, int size) 1123bd4c625cSLinus Torvalds { 11241da177e4SLinus Torvalds 11251da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11261da177e4SLinus Torvalds 1127a063ae17SJeff Mahoney memset(tb, '\0', sizeof(struct tree_balance)); 1128a063ae17SJeff Mahoney tb->transaction_handle = th; 1129a063ae17SJeff Mahoney tb->tb_sb = sb; 1130d68caa95SJeff Mahoney tb->tb_path = path; 1131d68caa95SJeff Mahoney PATH_OFFSET_PBUFFER(path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL; 1132d68caa95SJeff Mahoney PATH_OFFSET_POSITION(path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0; 1133ee93961bSJeff Mahoney tb->insert_size[0] = size; 11341da177e4SLinus Torvalds } 11351da177e4SLinus Torvalds 11361da177e4SLinus Torvalds void padd_item(char *item, int total_length, int length) 11371da177e4SLinus Torvalds { 11381da177e4SLinus Torvalds int i; 11391da177e4SLinus Torvalds 11401da177e4SLinus Torvalds for (i = total_length; i > length;) 11411da177e4SLinus Torvalds item[--i] = 0; 11421da177e4SLinus Torvalds } 11431da177e4SLinus Torvalds 11441da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 11451da177e4SLinus Torvalds char key2type(struct reiserfs_key *ih) 11461da177e4SLinus Torvalds { 11471da177e4SLinus Torvalds if (is_direntry_le_key(2, ih)) 11481da177e4SLinus Torvalds return 'd'; 11491da177e4SLinus Torvalds if (is_direct_le_key(2, ih)) 11501da177e4SLinus Torvalds return 'D'; 11511da177e4SLinus Torvalds if (is_indirect_le_key(2, ih)) 11521da177e4SLinus Torvalds return 'i'; 11531da177e4SLinus Torvalds if (is_statdata_le_key(2, ih)) 11541da177e4SLinus Torvalds return 's'; 11551da177e4SLinus Torvalds return 'u'; 11561da177e4SLinus Torvalds } 11571da177e4SLinus Torvalds 11581da177e4SLinus Torvalds char head2type(struct item_head *ih) 11591da177e4SLinus Torvalds { 11601da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) 11611da177e4SLinus Torvalds return 'd'; 11621da177e4SLinus Torvalds if (is_direct_le_ih(ih)) 11631da177e4SLinus Torvalds return 'D'; 11641da177e4SLinus Torvalds if (is_indirect_le_ih(ih)) 11651da177e4SLinus Torvalds return 'i'; 11661da177e4SLinus Torvalds if (is_statdata_le_ih(ih)) 11671da177e4SLinus Torvalds return 's'; 11681da177e4SLinus Torvalds return 'u'; 11691da177e4SLinus Torvalds } 11701da177e4SLinus Torvalds #endif 11711da177e4SLinus Torvalds 1172d68caa95SJeff Mahoney /* Delete object item. 1173d68caa95SJeff Mahoney * th - active transaction handle 1174d68caa95SJeff Mahoney * path - path to the deleted item 1175d68caa95SJeff Mahoney * item_key - key to search for the deleted item 1176d68caa95SJeff Mahoney * indode - used for updating i_blocks and quotas 1177d68caa95SJeff Mahoney * un_bh - NULL or unformatted node pointer 1178d68caa95SJeff Mahoney */ 1179d68caa95SJeff Mahoney int reiserfs_delete_item(struct reiserfs_transaction_handle *th, 1180d68caa95SJeff Mahoney struct treepath *path, const struct cpu_key *item_key, 1181d68caa95SJeff Mahoney struct inode *inode, struct buffer_head *un_bh) 1182d68caa95SJeff Mahoney { 1183995c762eSJeff Mahoney struct super_block *sb = 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; 1188ee93961bSJeff Mahoney int ret_value, del_size, removed; 1189*d2d0395fSJeff Mahoney int depth; 11901da177e4SLinus Torvalds 11911da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 1192ee93961bSJeff Mahoney char mode; 1193ee93961bSJeff Mahoney int iter = 0; 11941da177e4SLinus Torvalds #endif 11951da177e4SLinus Torvalds 11961da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 11971da177e4SLinus Torvalds 1198d68caa95SJeff Mahoney init_tb_struct(th, &s_del_balance, sb, path, 1199bd4c625cSLinus Torvalds 0 /*size is unknown */ ); 12001da177e4SLinus Torvalds 12011da177e4SLinus Torvalds while (1) { 1202ee93961bSJeff Mahoney removed = 0; 12031da177e4SLinus Torvalds 12041da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 1205ee93961bSJeff Mahoney iter++; 1206ee93961bSJeff Mahoney mode = 12071da177e4SLinus Torvalds #endif 1208d68caa95SJeff Mahoney prepare_for_delete_or_cut(th, inode, path, 1209ee93961bSJeff Mahoney item_key, &removed, 1210ee93961bSJeff Mahoney &del_size, 1211995c762eSJeff Mahoney max_reiserfs_offset(inode)); 12121da177e4SLinus Torvalds 1213ee93961bSJeff Mahoney RFALSE(mode != M_DELETE, "PAP-5320: mode must be M_DELETE"); 12141da177e4SLinus Torvalds 1215d68caa95SJeff Mahoney copy_item_head(&s_ih, PATH_PITEM_HEAD(path)); 1216ee93961bSJeff Mahoney s_del_balance.insert_size[0] = del_size; 12171da177e4SLinus Torvalds 1218ee93961bSJeff Mahoney ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL); 1219ee93961bSJeff Mahoney if (ret_value != REPEAT_SEARCH) 12201da177e4SLinus Torvalds break; 12211da177e4SLinus Torvalds 1222a9dd3643SJeff Mahoney PROC_INFO_INC(sb, delete_item_restarted); 12231da177e4SLinus Torvalds 12241da177e4SLinus Torvalds // file system changed, repeat search 1225ee93961bSJeff Mahoney ret_value = 1226d68caa95SJeff Mahoney search_for_position_by_key(sb, item_key, path); 1227ee93961bSJeff Mahoney if (ret_value == IO_ERROR) 12281da177e4SLinus Torvalds break; 1229ee93961bSJeff Mahoney if (ret_value == FILE_NOT_FOUND) { 1230a9dd3643SJeff Mahoney reiserfs_warning(sb, "vs-5340", 1231bd4c625cSLinus Torvalds "no items of the file %K found", 1232d68caa95SJeff Mahoney item_key); 12331da177e4SLinus Torvalds break; 12341da177e4SLinus Torvalds } 12351da177e4SLinus Torvalds } /* while (1) */ 12361da177e4SLinus Torvalds 1237ee93961bSJeff Mahoney if (ret_value != CARRY_ON) { 12381da177e4SLinus Torvalds unfix_nodes(&s_del_balance); 12391da177e4SLinus Torvalds return 0; 12401da177e4SLinus Torvalds } 12411da177e4SLinus Torvalds // reiserfs_delete_item returns item length when success 1242ee93961bSJeff Mahoney ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE); 1243d68caa95SJeff Mahoney q_ih = get_ih(path); 12441da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(q_ih); 12451da177e4SLinus Torvalds 12461da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file 12471da177e4SLinus Torvalds ** has a tail. On tail insert, we allocate quota for 1 unformatted node. 12481da177e4SLinus Torvalds ** We test the offset because the tail might have been 12491da177e4SLinus Torvalds ** split into multiple items, and we only want to decrement for 12501da177e4SLinus Torvalds ** the unfm node once 12511da177e4SLinus Torvalds */ 1252995c762eSJeff Mahoney if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(q_ih)) { 1253a9dd3643SJeff Mahoney if ((le_ih_k_offset(q_ih) & (sb->s_blocksize - 1)) == 1) { 1254a9dd3643SJeff Mahoney quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 12551da177e4SLinus Torvalds } else { 12561da177e4SLinus Torvalds quota_cut_bytes = 0; 12571da177e4SLinus Torvalds } 12581da177e4SLinus Torvalds } 12591da177e4SLinus Torvalds 1260d68caa95SJeff Mahoney if (un_bh) { 12611da177e4SLinus Torvalds int off; 12621da177e4SLinus Torvalds char *data; 12631da177e4SLinus Torvalds 12641da177e4SLinus Torvalds /* We are in direct2indirect conversion, so move tail contents 12651da177e4SLinus Torvalds to the unformatted node */ 12661da177e4SLinus Torvalds /* note, we do the copy before preparing the buffer because we 12671da177e4SLinus Torvalds ** don't care about the contents of the unformatted node yet. 12681da177e4SLinus Torvalds ** the only thing we really care about is the direct item's data 12691da177e4SLinus Torvalds ** is in the unformatted node. 12701da177e4SLinus Torvalds ** 12711da177e4SLinus Torvalds ** Otherwise, we would have to call reiserfs_prepare_for_journal on 12721da177e4SLinus Torvalds ** the unformatted node, which might schedule, meaning we'd have to 12731da177e4SLinus Torvalds ** loop all the way back up to the start of the while loop. 12741da177e4SLinus Torvalds ** 12751da177e4SLinus Torvalds ** The unformatted node must be dirtied later on. We can't be 12761da177e4SLinus Torvalds ** sure here if the entire tail has been deleted yet. 12771da177e4SLinus Torvalds ** 1278d68caa95SJeff Mahoney ** un_bh is from the page cache (all unformatted nodes are 12791da177e4SLinus Torvalds ** from the page cache) and might be a highmem page. So, we 1280d68caa95SJeff Mahoney ** can't use un_bh->b_data. 12811da177e4SLinus Torvalds ** -clm 12821da177e4SLinus Torvalds */ 12831da177e4SLinus Torvalds 1284883da600SCong Wang data = kmap_atomic(un_bh->b_page); 12851da177e4SLinus Torvalds off = ((le_ih_k_offset(&s_ih) - 1) & (PAGE_CACHE_SIZE - 1)); 12861da177e4SLinus Torvalds memcpy(data + off, 1287d68caa95SJeff Mahoney B_I_PITEM(PATH_PLAST_BUFFER(path), &s_ih), 1288ee93961bSJeff Mahoney ret_value); 1289883da600SCong Wang kunmap_atomic(data); 12901da177e4SLinus Torvalds } 12911da177e4SLinus Torvalds /* Perform balancing after all resources have been collected at once. */ 12921da177e4SLinus Torvalds do_balance(&s_del_balance, NULL, NULL, M_DELETE); 12931da177e4SLinus Torvalds 12941da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1295a9dd3643SJeff Mahoney reiserfs_debug(sb, REISERFS_DEBUG_CODE, 1296bd4c625cSLinus Torvalds "reiserquota delete_item(): freeing %u, id=%u type=%c", 1297995c762eSJeff Mahoney quota_cut_bytes, inode->i_uid, head2type(&s_ih)); 12981da177e4SLinus Torvalds #endif 1299*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(inode->i_sb); 13005dd4056dSChristoph Hellwig dquot_free_space_nodirty(inode, quota_cut_bytes); 1301*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(inode->i_sb, depth); 13021da177e4SLinus Torvalds 13031da177e4SLinus Torvalds /* Return deleted body length */ 1304ee93961bSJeff Mahoney return ret_value; 13051da177e4SLinus Torvalds } 13061da177e4SLinus Torvalds 13071da177e4SLinus Torvalds /* Summary Of Mechanisms For Handling Collisions Between Processes: 13081da177e4SLinus Torvalds 13091da177e4SLinus Torvalds deletion of the body of the object is performed by iput(), with the 13101da177e4SLinus Torvalds result that if multiple processes are operating on a file, the 13111da177e4SLinus Torvalds deletion of the body of the file is deferred until the last process 13121da177e4SLinus Torvalds that has an open inode performs its iput(). 13131da177e4SLinus Torvalds 13141da177e4SLinus Torvalds writes and truncates are protected from collisions by use of 13151da177e4SLinus Torvalds semaphores. 13161da177e4SLinus Torvalds 13171da177e4SLinus Torvalds creates, linking, and mknod are protected from collisions with other 13181da177e4SLinus Torvalds processes by making the reiserfs_add_entry() the last step in the 13191da177e4SLinus Torvalds creation, and then rolling back all changes if there was a collision. 13201da177e4SLinus Torvalds - Hans 13211da177e4SLinus Torvalds */ 13221da177e4SLinus Torvalds 13231da177e4SLinus Torvalds /* this deletes item which never gets split */ 13241da177e4SLinus Torvalds void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, 1325bd4c625cSLinus Torvalds struct inode *inode, struct reiserfs_key *key) 13261da177e4SLinus Torvalds { 1327*d2d0395fSJeff Mahoney struct super_block *sb = th->t_super; 13281da177e4SLinus Torvalds struct tree_balance tb; 13291da177e4SLinus Torvalds INITIALIZE_PATH(path); 13301da177e4SLinus Torvalds int item_len = 0; 13311da177e4SLinus Torvalds int tb_init = 0; 13321da177e4SLinus Torvalds struct cpu_key cpu_key; 13331da177e4SLinus Torvalds int retval; 13341da177e4SLinus Torvalds int quota_cut_bytes = 0; 13351da177e4SLinus Torvalds 13361da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 13371da177e4SLinus Torvalds 13381da177e4SLinus Torvalds le_key2cpu_key(&cpu_key, key); 13391da177e4SLinus Torvalds 13401da177e4SLinus Torvalds while (1) { 13411da177e4SLinus Torvalds retval = search_item(th->t_super, &cpu_key, &path); 13421da177e4SLinus Torvalds if (retval == IO_ERROR) { 13430030b645SJeff Mahoney reiserfs_error(th->t_super, "vs-5350", 134445b03d5eSJeff Mahoney "i/o failure occurred trying " 134545b03d5eSJeff Mahoney "to delete %K", &cpu_key); 13461da177e4SLinus Torvalds break; 13471da177e4SLinus Torvalds } 13481da177e4SLinus Torvalds if (retval != ITEM_FOUND) { 13491da177e4SLinus Torvalds pathrelse(&path); 13501da177e4SLinus Torvalds // No need for a warning, if there is just no free space to insert '..' item into the newly-created subdir 1351bd4c625cSLinus Torvalds if (! 1352bd4c625cSLinus Torvalds ((unsigned long long) 1353bd4c625cSLinus Torvalds GET_HASH_VALUE(le_key_k_offset 1354bd4c625cSLinus Torvalds (le_key_version(key), key)) == 0 1355bd4c625cSLinus Torvalds && (unsigned long long) 1356bd4c625cSLinus Torvalds GET_GENERATION_NUMBER(le_key_k_offset 1357bd4c625cSLinus Torvalds (le_key_version(key), 1358bd4c625cSLinus Torvalds key)) == 1)) 135945b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5355", 136045b03d5eSJeff Mahoney "%k not found", key); 13611da177e4SLinus Torvalds break; 13621da177e4SLinus Torvalds } 13631da177e4SLinus Torvalds if (!tb_init) { 13641da177e4SLinus Torvalds tb_init = 1; 13651da177e4SLinus Torvalds item_len = ih_item_len(PATH_PITEM_HEAD(&path)); 1366bd4c625cSLinus Torvalds init_tb_struct(th, &tb, th->t_super, &path, 1367bd4c625cSLinus Torvalds -(IH_SIZE + item_len)); 13681da177e4SLinus Torvalds } 13691da177e4SLinus Torvalds quota_cut_bytes = ih_item_len(PATH_PITEM_HEAD(&path)); 13701da177e4SLinus Torvalds 13711da177e4SLinus Torvalds retval = fix_nodes(M_DELETE, &tb, NULL, NULL); 13721da177e4SLinus Torvalds if (retval == REPEAT_SEARCH) { 13731da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, delete_solid_item_restarted); 13741da177e4SLinus Torvalds continue; 13751da177e4SLinus Torvalds } 13761da177e4SLinus Torvalds 13771da177e4SLinus Torvalds if (retval == CARRY_ON) { 13781da177e4SLinus Torvalds do_balance(&tb, NULL, NULL, M_DELETE); 13791da177e4SLinus Torvalds if (inode) { /* Should we count quota for item? (we don't count quotas for save-links) */ 1380*d2d0395fSJeff Mahoney int depth; 13811da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1382bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 1383bd4c625cSLinus Torvalds "reiserquota delete_solid_item(): freeing %u id=%u type=%c", 1384bd4c625cSLinus Torvalds quota_cut_bytes, inode->i_uid, 1385bd4c625cSLinus Torvalds key2type(key)); 13861da177e4SLinus Torvalds #endif 1387*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(sb); 13885dd4056dSChristoph Hellwig dquot_free_space_nodirty(inode, 1389bd4c625cSLinus Torvalds quota_cut_bytes); 1390*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(sb, depth); 13911da177e4SLinus Torvalds } 13921da177e4SLinus Torvalds break; 13931da177e4SLinus Torvalds } 13941da177e4SLinus Torvalds // IO_ERROR, NO_DISK_SPACE, etc 139545b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "vs-5360", 1396bd4c625cSLinus Torvalds "could not delete %K due to fix_nodes failure", 1397bd4c625cSLinus Torvalds &cpu_key); 13981da177e4SLinus Torvalds unfix_nodes(&tb); 13991da177e4SLinus Torvalds break; 14001da177e4SLinus Torvalds } 14011da177e4SLinus Torvalds 14021da177e4SLinus Torvalds reiserfs_check_path(&path); 14031da177e4SLinus Torvalds } 14041da177e4SLinus Torvalds 1405bd4c625cSLinus Torvalds int reiserfs_delete_object(struct reiserfs_transaction_handle *th, 1406bd4c625cSLinus Torvalds struct inode *inode) 14071da177e4SLinus Torvalds { 14081da177e4SLinus Torvalds int err; 14091da177e4SLinus Torvalds inode->i_size = 0; 14101da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 14111da177e4SLinus Torvalds 14121da177e4SLinus Torvalds /* for directory this deletes item containing "." and ".." */ 1413bd4c625cSLinus Torvalds err = 1414bd4c625cSLinus Torvalds reiserfs_do_truncate(th, inode, NULL, 0 /*no timestamp updates */ ); 14151da177e4SLinus Torvalds if (err) 14161da177e4SLinus Torvalds return err; 14171da177e4SLinus Torvalds 14181da177e4SLinus Torvalds #if defined( USE_INODE_GENERATION_COUNTER ) 1419bd4c625cSLinus Torvalds if (!old_format_only(th->t_super)) { 14203e8962beSAl Viro __le32 *inode_generation; 14211da177e4SLinus Torvalds 14221da177e4SLinus Torvalds inode_generation = 14231da177e4SLinus Torvalds &REISERFS_SB(th->t_super)->s_rs->s_inode_generation; 14249e902df6SMarcin Slusarz le32_add_cpu(inode_generation, 1); 14251da177e4SLinus Torvalds } 14261da177e4SLinus Torvalds /* USE_INODE_GENERATION_COUNTER */ 14271da177e4SLinus Torvalds #endif 14281da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 14291da177e4SLinus Torvalds 14301da177e4SLinus Torvalds return err; 14311da177e4SLinus Torvalds } 14321da177e4SLinus Torvalds 1433bd4c625cSLinus Torvalds static void unmap_buffers(struct page *page, loff_t pos) 1434bd4c625cSLinus Torvalds { 14351da177e4SLinus Torvalds struct buffer_head *bh; 14361da177e4SLinus Torvalds struct buffer_head *head; 14371da177e4SLinus Torvalds struct buffer_head *next; 14381da177e4SLinus Torvalds unsigned long tail_index; 14391da177e4SLinus Torvalds unsigned long cur_index; 14401da177e4SLinus Torvalds 14411da177e4SLinus Torvalds if (page) { 14421da177e4SLinus Torvalds if (page_has_buffers(page)) { 14431da177e4SLinus Torvalds tail_index = pos & (PAGE_CACHE_SIZE - 1); 14441da177e4SLinus Torvalds cur_index = 0; 14451da177e4SLinus Torvalds head = page_buffers(page); 14461da177e4SLinus Torvalds bh = head; 14471da177e4SLinus Torvalds do { 14481da177e4SLinus Torvalds next = bh->b_this_page; 14491da177e4SLinus Torvalds 14501da177e4SLinus Torvalds /* we want to unmap the buffers that contain the tail, and 14511da177e4SLinus Torvalds ** all the buffers after it (since the tail must be at the 14521da177e4SLinus Torvalds ** end of the file). We don't want to unmap file data 14531da177e4SLinus Torvalds ** before the tail, since it might be dirty and waiting to 14541da177e4SLinus Torvalds ** reach disk 14551da177e4SLinus Torvalds */ 14561da177e4SLinus Torvalds cur_index += bh->b_size; 14571da177e4SLinus Torvalds if (cur_index > tail_index) { 14581da177e4SLinus Torvalds reiserfs_unmap_buffer(bh); 14591da177e4SLinus Torvalds } 14601da177e4SLinus Torvalds bh = next; 14611da177e4SLinus Torvalds } while (bh != head); 14621da177e4SLinus Torvalds } 14631da177e4SLinus Torvalds } 14641da177e4SLinus Torvalds } 14651da177e4SLinus Torvalds 14661da177e4SLinus Torvalds static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, 1467995c762eSJeff Mahoney struct inode *inode, 14681da177e4SLinus Torvalds struct page *page, 1469d68caa95SJeff Mahoney struct treepath *path, 1470d68caa95SJeff Mahoney const struct cpu_key *item_key, 1471ee93961bSJeff Mahoney loff_t new_file_size, char *mode) 1472bd4c625cSLinus Torvalds { 1473995c762eSJeff Mahoney struct super_block *sb = inode->i_sb; 1474ee93961bSJeff Mahoney int block_size = sb->s_blocksize; 14751da177e4SLinus Torvalds int cut_bytes; 14761da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 1477ee93961bSJeff Mahoney BUG_ON(new_file_size != inode->i_size); 14781da177e4SLinus Torvalds 14791da177e4SLinus Torvalds /* the page being sent in could be NULL if there was an i/o error 14801da177e4SLinus Torvalds ** reading in the last block. The user will hit problems trying to 14811da177e4SLinus Torvalds ** read the file, but for now we just skip the indirect2direct 14821da177e4SLinus Torvalds */ 1483995c762eSJeff Mahoney if (atomic_read(&inode->i_count) > 1 || 1484995c762eSJeff Mahoney !tail_has_to_be_packed(inode) || 1485995c762eSJeff Mahoney !page || (REISERFS_I(inode)->i_flags & i_nopack_mask)) { 14860222e657SJeff Mahoney /* leave tail in an unformatted node */ 1487d68caa95SJeff Mahoney *mode = M_SKIP_BALANCING; 1488bd4c625cSLinus Torvalds cut_bytes = 1489ee93961bSJeff Mahoney block_size - (new_file_size & (block_size - 1)); 1490d68caa95SJeff Mahoney pathrelse(path); 14911da177e4SLinus Torvalds return cut_bytes; 14921da177e4SLinus Torvalds } 1493d68caa95SJeff Mahoney /* Perform the conversion to a direct_item. */ 1494d68caa95SJeff Mahoney /* return indirect_to_direct(inode, path, item_key, 1495ee93961bSJeff Mahoney new_file_size, mode); */ 1496d68caa95SJeff Mahoney return indirect2direct(th, inode, page, path, item_key, 1497ee93961bSJeff Mahoney new_file_size, mode); 14981da177e4SLinus Torvalds } 14991da177e4SLinus Torvalds 15001da177e4SLinus Torvalds /* we did indirect_to_direct conversion. And we have inserted direct 15011da177e4SLinus Torvalds item successesfully, but there were no disk space to cut unfm 15021da177e4SLinus Torvalds pointer being converted. Therefore we have to delete inserted 15031da177e4SLinus Torvalds direct item(s) */ 1504bd4c625cSLinus Torvalds static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, 1505fec6d055SJosef "Jeff" Sipek struct inode *inode, struct treepath *path) 15061da177e4SLinus Torvalds { 15071da177e4SLinus Torvalds struct cpu_key tail_key; 15081da177e4SLinus Torvalds int tail_len; 15091da177e4SLinus Torvalds int removed; 15101da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15111da177e4SLinus Torvalds 15121da177e4SLinus Torvalds make_cpu_key(&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4); // !!!! 15131da177e4SLinus Torvalds tail_key.key_length = 4; 15141da177e4SLinus Torvalds 1515bd4c625cSLinus Torvalds tail_len = 1516bd4c625cSLinus Torvalds (cpu_key_k_offset(&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1; 15171da177e4SLinus Torvalds while (tail_len) { 15181da177e4SLinus Torvalds /* look for the last byte of the tail */ 1519bd4c625cSLinus Torvalds if (search_for_position_by_key(inode->i_sb, &tail_key, path) == 1520bd4c625cSLinus Torvalds POSITION_NOT_FOUND) 1521c3a9c210SJeff Mahoney reiserfs_panic(inode->i_sb, "vs-5615", 1522c3a9c210SJeff Mahoney "found invalid item"); 1523bd4c625cSLinus Torvalds RFALSE(path->pos_in_item != 1524bd4c625cSLinus Torvalds ih_item_len(PATH_PITEM_HEAD(path)) - 1, 15251da177e4SLinus Torvalds "vs-5616: appended bytes found"); 15261da177e4SLinus Torvalds PATH_LAST_POSITION(path)--; 15271da177e4SLinus Torvalds 1528bd4c625cSLinus Torvalds removed = 1529bd4c625cSLinus Torvalds reiserfs_delete_item(th, path, &tail_key, inode, 1530bd4c625cSLinus Torvalds NULL /*unbh not needed */ ); 1531bd4c625cSLinus Torvalds RFALSE(removed <= 0 1532bd4c625cSLinus Torvalds || removed > tail_len, 15331da177e4SLinus Torvalds "vs-5617: there was tail %d bytes, removed item length %d bytes", 15341da177e4SLinus Torvalds tail_len, removed); 15351da177e4SLinus Torvalds tail_len -= removed; 1536bd4c625cSLinus Torvalds set_cpu_key_k_offset(&tail_key, 1537bd4c625cSLinus Torvalds cpu_key_k_offset(&tail_key) - removed); 15381da177e4SLinus Torvalds } 153945b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "reiserfs-5091", "indirect_to_direct " 154045b03d5eSJeff Mahoney "conversion has been rolled back due to " 154145b03d5eSJeff Mahoney "lack of disk space"); 15421da177e4SLinus Torvalds //mark_file_without_tail (inode); 15431da177e4SLinus Torvalds mark_inode_dirty(inode); 15441da177e4SLinus Torvalds } 15451da177e4SLinus Torvalds 15461da177e4SLinus Torvalds /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ 15471da177e4SLinus Torvalds int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, 1548d68caa95SJeff Mahoney struct treepath *path, 1549d68caa95SJeff Mahoney struct cpu_key *item_key, 1550995c762eSJeff Mahoney struct inode *inode, 1551ee93961bSJeff Mahoney struct page *page, loff_t new_file_size) 15521da177e4SLinus Torvalds { 1553995c762eSJeff Mahoney struct super_block *sb = inode->i_sb; 15541da177e4SLinus Torvalds /* Every function which is going to call do_balance must first 15551da177e4SLinus Torvalds create a tree_balance structure. Then it must fill up this 15561da177e4SLinus Torvalds structure by using the init_tb_struct and fix_nodes functions. 15571da177e4SLinus Torvalds After that we can make tree balancing. */ 15581da177e4SLinus Torvalds struct tree_balance s_cut_balance; 15591da177e4SLinus Torvalds struct item_head *p_le_ih; 1560ee93961bSJeff Mahoney int cut_size = 0, /* Amount to be cut. */ 1561ee93961bSJeff Mahoney ret_value = CARRY_ON, removed = 0, /* Number of the removed unformatted nodes. */ 1562ee93961bSJeff Mahoney is_inode_locked = 0; 1563ee93961bSJeff Mahoney char mode; /* Mode of the balance. */ 15641da177e4SLinus Torvalds int retval2 = -1; 15651da177e4SLinus Torvalds int quota_cut_bytes; 15661da177e4SLinus Torvalds loff_t tail_pos = 0; 1567*d2d0395fSJeff Mahoney int depth; 15681da177e4SLinus Torvalds 15691da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 15701da177e4SLinus Torvalds 1571d68caa95SJeff Mahoney init_tb_struct(th, &s_cut_balance, inode->i_sb, path, 1572ee93961bSJeff Mahoney cut_size); 15731da177e4SLinus Torvalds 15741da177e4SLinus Torvalds /* Repeat this loop until we either cut the item without needing 15751da177e4SLinus Torvalds to balance, or we fix_nodes without schedule occurring */ 15761da177e4SLinus Torvalds while (1) { 15771da177e4SLinus Torvalds /* Determine the balance mode, position of the first byte to 15781da177e4SLinus Torvalds be cut, and size to be cut. In case of the indirect item 15791da177e4SLinus Torvalds free unformatted nodes which are pointed to by the cut 15801da177e4SLinus Torvalds pointers. */ 15811da177e4SLinus Torvalds 1582ee93961bSJeff Mahoney mode = 1583d68caa95SJeff Mahoney prepare_for_delete_or_cut(th, inode, path, 1584ee93961bSJeff Mahoney item_key, &removed, 1585ee93961bSJeff Mahoney &cut_size, new_file_size); 1586ee93961bSJeff Mahoney if (mode == M_CONVERT) { 15871da177e4SLinus Torvalds /* convert last unformatted node to direct item or leave 15881da177e4SLinus Torvalds tail in the unformatted node */ 1589ee93961bSJeff Mahoney RFALSE(ret_value != CARRY_ON, 1590bd4c625cSLinus Torvalds "PAP-5570: can not convert twice"); 15911da177e4SLinus Torvalds 1592ee93961bSJeff Mahoney ret_value = 1593995c762eSJeff Mahoney maybe_indirect_to_direct(th, inode, page, 1594d68caa95SJeff Mahoney path, item_key, 1595ee93961bSJeff Mahoney new_file_size, &mode); 1596ee93961bSJeff Mahoney if (mode == M_SKIP_BALANCING) 15971da177e4SLinus Torvalds /* tail has been left in the unformatted node */ 1598ee93961bSJeff Mahoney return ret_value; 15991da177e4SLinus Torvalds 1600ee93961bSJeff Mahoney is_inode_locked = 1; 16011da177e4SLinus Torvalds 16021da177e4SLinus Torvalds /* removing of last unformatted node will change value we 16031da177e4SLinus Torvalds have to return to truncate. Save it */ 1604ee93961bSJeff Mahoney retval2 = ret_value; 1605ee93961bSJeff Mahoney /*retval2 = sb->s_blocksize - (new_file_size & (sb->s_blocksize - 1)); */ 16061da177e4SLinus Torvalds 16071da177e4SLinus Torvalds /* So, we have performed the first part of the conversion: 16081da177e4SLinus Torvalds inserting the new direct item. Now we are removing the 16091da177e4SLinus Torvalds last unformatted node pointer. Set key to search for 16101da177e4SLinus Torvalds it. */ 1611d68caa95SJeff Mahoney set_cpu_key_k_type(item_key, TYPE_INDIRECT); 1612d68caa95SJeff Mahoney item_key->key_length = 4; 1613ee93961bSJeff Mahoney new_file_size -= 1614ee93961bSJeff Mahoney (new_file_size & (sb->s_blocksize - 1)); 1615ee93961bSJeff Mahoney tail_pos = new_file_size; 1616ee93961bSJeff Mahoney set_cpu_key_k_offset(item_key, new_file_size + 1); 1617bd4c625cSLinus Torvalds if (search_for_position_by_key 1618d68caa95SJeff Mahoney (sb, item_key, 1619d68caa95SJeff Mahoney path) == POSITION_NOT_FOUND) { 1620d68caa95SJeff Mahoney print_block(PATH_PLAST_BUFFER(path), 3, 1621d68caa95SJeff Mahoney PATH_LAST_POSITION(path) - 1, 1622d68caa95SJeff Mahoney PATH_LAST_POSITION(path) + 1); 1623a9dd3643SJeff Mahoney reiserfs_panic(sb, "PAP-5580", "item to " 1624c3a9c210SJeff Mahoney "convert does not exist (%K)", 1625d68caa95SJeff Mahoney item_key); 16261da177e4SLinus Torvalds } 16271da177e4SLinus Torvalds continue; 16281da177e4SLinus Torvalds } 1629ee93961bSJeff Mahoney if (cut_size == 0) { 1630d68caa95SJeff Mahoney pathrelse(path); 16311da177e4SLinus Torvalds return 0; 16321da177e4SLinus Torvalds } 16331da177e4SLinus Torvalds 1634ee93961bSJeff Mahoney s_cut_balance.insert_size[0] = cut_size; 16351da177e4SLinus Torvalds 1636ee93961bSJeff Mahoney ret_value = fix_nodes(mode, &s_cut_balance, NULL, NULL); 1637ee93961bSJeff Mahoney if (ret_value != REPEAT_SEARCH) 16381da177e4SLinus Torvalds break; 16391da177e4SLinus Torvalds 1640a9dd3643SJeff Mahoney PROC_INFO_INC(sb, cut_from_item_restarted); 16411da177e4SLinus Torvalds 1642ee93961bSJeff Mahoney ret_value = 1643d68caa95SJeff Mahoney search_for_position_by_key(sb, item_key, path); 1644ee93961bSJeff Mahoney if (ret_value == POSITION_FOUND) 16451da177e4SLinus Torvalds continue; 16461da177e4SLinus Torvalds 1647a9dd3643SJeff Mahoney reiserfs_warning(sb, "PAP-5610", "item %K not found", 1648d68caa95SJeff Mahoney item_key); 16491da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 1650ee93961bSJeff Mahoney return (ret_value == IO_ERROR) ? -EIO : -ENOENT; 16511da177e4SLinus Torvalds } /* while */ 16521da177e4SLinus Torvalds 16531da177e4SLinus Torvalds // check fix_nodes results (IO_ERROR or NO_DISK_SPACE) 1654ee93961bSJeff Mahoney if (ret_value != CARRY_ON) { 1655ee93961bSJeff Mahoney if (is_inode_locked) { 16561da177e4SLinus Torvalds // FIXME: this seems to be not needed: we are always able 16571da177e4SLinus Torvalds // to cut item 1658d68caa95SJeff Mahoney indirect_to_direct_roll_back(th, inode, path); 16591da177e4SLinus Torvalds } 1660ee93961bSJeff Mahoney if (ret_value == NO_DISK_SPACE) 1661a9dd3643SJeff Mahoney reiserfs_warning(sb, "reiserfs-5092", 166245b03d5eSJeff Mahoney "NO_DISK_SPACE"); 16631da177e4SLinus Torvalds unfix_nodes(&s_cut_balance); 16641da177e4SLinus Torvalds return -EIO; 16651da177e4SLinus Torvalds } 16661da177e4SLinus Torvalds 16671da177e4SLinus Torvalds /* go ahead and perform balancing */ 16681da177e4SLinus Torvalds 1669ee93961bSJeff Mahoney RFALSE(mode == M_PASTE || mode == M_INSERT, "invalid mode"); 16701da177e4SLinus Torvalds 16711da177e4SLinus Torvalds /* Calculate number of bytes that need to be cut from the item. */ 1672bd4c625cSLinus Torvalds quota_cut_bytes = 1673ee93961bSJeff Mahoney (mode == 1674d68caa95SJeff Mahoney M_DELETE) ? ih_item_len(get_ih(path)) : -s_cut_balance. 1675bd4c625cSLinus Torvalds insert_size[0]; 16761da177e4SLinus Torvalds if (retval2 == -1) 1677ee93961bSJeff Mahoney ret_value = calc_deleted_bytes_number(&s_cut_balance, mode); 16781da177e4SLinus Torvalds else 1679ee93961bSJeff Mahoney ret_value = retval2; 16801da177e4SLinus Torvalds 16811da177e4SLinus Torvalds /* For direct items, we only change the quota when deleting the last 16821da177e4SLinus Torvalds ** item. 16831da177e4SLinus Torvalds */ 16841da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(s_cut_balance.tb_path); 1685995c762eSJeff Mahoney if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(p_le_ih)) { 1686ee93961bSJeff Mahoney if (mode == M_DELETE && 1687a9dd3643SJeff Mahoney (le_ih_k_offset(p_le_ih) & (sb->s_blocksize - 1)) == 1688bd4c625cSLinus Torvalds 1) { 16891da177e4SLinus Torvalds // FIXME: this is to keep 3.5 happy 1690995c762eSJeff Mahoney REISERFS_I(inode)->i_first_direct_byte = U32_MAX; 1691a9dd3643SJeff Mahoney quota_cut_bytes = sb->s_blocksize + UNFM_P_SIZE; 16921da177e4SLinus Torvalds } else { 16931da177e4SLinus Torvalds quota_cut_bytes = 0; 16941da177e4SLinus Torvalds } 16951da177e4SLinus Torvalds } 16961da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 1697ee93961bSJeff Mahoney if (is_inode_locked) { 1698bd4c625cSLinus Torvalds struct item_head *le_ih = 1699bd4c625cSLinus Torvalds PATH_PITEM_HEAD(s_cut_balance.tb_path); 17001da177e4SLinus Torvalds /* we are going to complete indirect2direct conversion. Make 17011da177e4SLinus Torvalds sure, that we exactly remove last unformatted node pointer 17021da177e4SLinus Torvalds of the item */ 17031da177e4SLinus Torvalds if (!is_indirect_le_ih(le_ih)) 1704a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5652", 17051da177e4SLinus Torvalds "item must be indirect %h", le_ih); 17061da177e4SLinus Torvalds 1707ee93961bSJeff Mahoney if (mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE) 1708a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5653", "completing " 1709c3a9c210SJeff Mahoney "indirect2direct conversion indirect " 1710c3a9c210SJeff Mahoney "item %h being deleted must be of " 1711c3a9c210SJeff Mahoney "4 byte long", le_ih); 17121da177e4SLinus Torvalds 1713ee93961bSJeff Mahoney if (mode == M_CUT 1714bd4c625cSLinus Torvalds && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) { 1715a9dd3643SJeff Mahoney reiserfs_panic(sb, "vs-5654", "can not complete " 1716c3a9c210SJeff Mahoney "indirect2direct conversion of %h " 1717c3a9c210SJeff Mahoney "(CUT, insert_size==%d)", 17181da177e4SLinus Torvalds le_ih, s_cut_balance.insert_size[0]); 17191da177e4SLinus Torvalds } 17201da177e4SLinus Torvalds /* it would be useful to make sure, that right neighboring 17211da177e4SLinus Torvalds item is direct item of this file */ 17221da177e4SLinus Torvalds } 17231da177e4SLinus Torvalds #endif 17241da177e4SLinus Torvalds 1725ee93961bSJeff Mahoney do_balance(&s_cut_balance, NULL, NULL, mode); 1726ee93961bSJeff Mahoney if (is_inode_locked) { 17271da177e4SLinus Torvalds /* we've done an indirect->direct conversion. when the data block 17281da177e4SLinus Torvalds ** was freed, it was removed from the list of blocks that must 17291da177e4SLinus Torvalds ** be flushed before the transaction commits, make sure to 17301da177e4SLinus Torvalds ** unmap and invalidate it 17311da177e4SLinus Torvalds */ 17321da177e4SLinus Torvalds unmap_buffers(page, tail_pos); 1733995c762eSJeff Mahoney REISERFS_I(inode)->i_flags &= ~i_pack_on_close_mask; 17341da177e4SLinus Torvalds } 17351da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1736995c762eSJeff Mahoney reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1737bd4c625cSLinus Torvalds "reiserquota cut_from_item(): freeing %u id=%u type=%c", 1738995c762eSJeff Mahoney quota_cut_bytes, inode->i_uid, '?'); 17391da177e4SLinus Torvalds #endif 1740*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(sb); 17415dd4056dSChristoph Hellwig dquot_free_space_nodirty(inode, quota_cut_bytes); 1742*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(sb, depth); 1743ee93961bSJeff Mahoney return ret_value; 17441da177e4SLinus Torvalds } 17451da177e4SLinus Torvalds 1746bd4c625cSLinus Torvalds static void truncate_directory(struct reiserfs_transaction_handle *th, 1747bd4c625cSLinus Torvalds struct inode *inode) 17481da177e4SLinus Torvalds { 17491da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 17501da177e4SLinus Torvalds if (inode->i_nlink) 17510030b645SJeff Mahoney reiserfs_error(inode->i_sb, "vs-5655", "link count != 0"); 17521da177e4SLinus Torvalds 17531da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), DOT_OFFSET); 17541da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_DIRENTRY); 17551da177e4SLinus Torvalds reiserfs_delete_solid_item(th, inode, INODE_PKEY(inode)); 17561da177e4SLinus Torvalds reiserfs_update_sd(th, inode); 17571da177e4SLinus Torvalds set_le_key_k_offset(KEY_FORMAT_3_5, INODE_PKEY(inode), SD_OFFSET); 17581da177e4SLinus Torvalds set_le_key_k_type(KEY_FORMAT_3_5, INODE_PKEY(inode), TYPE_STAT_DATA); 17591da177e4SLinus Torvalds } 17601da177e4SLinus Torvalds 17611da177e4SLinus Torvalds /* Truncate file to the new size. Note, this must be called with a transaction 17621da177e4SLinus Torvalds already started */ 1763995c762eSJeff Mahoney int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, 1764995c762eSJeff Mahoney struct inode *inode, /* ->i_size contains new size */ 17651da177e4SLinus Torvalds struct page *page, /* up to date for last block */ 17661da177e4SLinus Torvalds int update_timestamps /* when it is called by 17671da177e4SLinus Torvalds file_release to convert 17681da177e4SLinus Torvalds the tail - no timestamps 17691da177e4SLinus Torvalds should be updated */ 1770bd4c625cSLinus Torvalds ) 1771bd4c625cSLinus Torvalds { 17721da177e4SLinus Torvalds INITIALIZE_PATH(s_search_path); /* Path to the current object item. */ 17731da177e4SLinus Torvalds struct item_head *p_le_ih; /* Pointer to an item header. */ 17741da177e4SLinus Torvalds struct cpu_key s_item_key; /* Key to search for a previous file item. */ 1775ee93961bSJeff Mahoney loff_t file_size, /* Old file size. */ 1776ee93961bSJeff Mahoney new_file_size; /* New file size. */ 1777ee93961bSJeff Mahoney int deleted; /* Number of deleted or truncated bytes. */ 17781da177e4SLinus Torvalds int retval; 17791da177e4SLinus Torvalds int err = 0; 17801da177e4SLinus Torvalds 17811da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 1782bd4c625cSLinus Torvalds if (! 1783995c762eSJeff Mahoney (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) 1784995c762eSJeff Mahoney || S_ISLNK(inode->i_mode))) 17851da177e4SLinus Torvalds return 0; 17861da177e4SLinus Torvalds 1787995c762eSJeff Mahoney if (S_ISDIR(inode->i_mode)) { 17881da177e4SLinus Torvalds // deletion of directory - no need to update timestamps 1789995c762eSJeff Mahoney truncate_directory(th, inode); 17901da177e4SLinus Torvalds return 0; 17911da177e4SLinus Torvalds } 17921da177e4SLinus Torvalds 17931da177e4SLinus Torvalds /* Get new file size. */ 1794ee93961bSJeff Mahoney new_file_size = inode->i_size; 17951da177e4SLinus Torvalds 17961da177e4SLinus Torvalds // FIXME: note, that key type is unimportant here 1797995c762eSJeff Mahoney make_cpu_key(&s_item_key, inode, max_reiserfs_offset(inode), 1798bd4c625cSLinus Torvalds TYPE_DIRECT, 3); 17991da177e4SLinus Torvalds 1800bd4c625cSLinus Torvalds retval = 1801995c762eSJeff Mahoney search_for_position_by_key(inode->i_sb, &s_item_key, 1802bd4c625cSLinus Torvalds &s_search_path); 18031da177e4SLinus Torvalds if (retval == IO_ERROR) { 1804995c762eSJeff Mahoney reiserfs_error(inode->i_sb, "vs-5657", 1805bd4c625cSLinus Torvalds "i/o failure occurred trying to truncate %K", 1806bd4c625cSLinus Torvalds &s_item_key); 18071da177e4SLinus Torvalds err = -EIO; 18081da177e4SLinus Torvalds goto out; 18091da177e4SLinus Torvalds } 18101da177e4SLinus Torvalds if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) { 1811995c762eSJeff Mahoney reiserfs_error(inode->i_sb, "PAP-5660", 1812bd4c625cSLinus Torvalds "wrong result %d of search for %K", retval, 1813bd4c625cSLinus Torvalds &s_item_key); 18141da177e4SLinus Torvalds 18151da177e4SLinus Torvalds err = -EIO; 18161da177e4SLinus Torvalds goto out; 18171da177e4SLinus Torvalds } 18181da177e4SLinus Torvalds 18191da177e4SLinus Torvalds s_search_path.pos_in_item--; 18201da177e4SLinus Torvalds 18211da177e4SLinus Torvalds /* Get real file size (total length of all file items) */ 18221da177e4SLinus Torvalds p_le_ih = PATH_PITEM_HEAD(&s_search_path); 18231da177e4SLinus Torvalds if (is_statdata_le_ih(p_le_ih)) 1824ee93961bSJeff Mahoney file_size = 0; 18251da177e4SLinus Torvalds else { 18261da177e4SLinus Torvalds loff_t offset = le_ih_k_offset(p_le_ih); 1827bd4c625cSLinus Torvalds int bytes = 1828995c762eSJeff Mahoney op_bytes_number(p_le_ih, inode->i_sb->s_blocksize); 18291da177e4SLinus Torvalds 18301da177e4SLinus Torvalds /* this may mismatch with real file size: if last direct item 18311da177e4SLinus Torvalds had no padding zeros and last unformatted node had no free 18321da177e4SLinus Torvalds space, this file would have this file size */ 1833ee93961bSJeff Mahoney file_size = offset + bytes - 1; 18341da177e4SLinus Torvalds } 18351da177e4SLinus Torvalds /* 18361da177e4SLinus Torvalds * are we doing a full truncate or delete, if so 18371da177e4SLinus Torvalds * kick in the reada code 18381da177e4SLinus Torvalds */ 1839ee93961bSJeff Mahoney if (new_file_size == 0) 18401da177e4SLinus Torvalds s_search_path.reada = PATH_READA | PATH_READA_BACK; 18411da177e4SLinus Torvalds 1842ee93961bSJeff Mahoney if (file_size == 0 || file_size < new_file_size) { 18431da177e4SLinus Torvalds goto update_and_out; 18441da177e4SLinus Torvalds } 18451da177e4SLinus Torvalds 18461da177e4SLinus Torvalds /* Update key to search for the last file item. */ 1847ee93961bSJeff Mahoney set_cpu_key_k_offset(&s_item_key, file_size); 18481da177e4SLinus Torvalds 18491da177e4SLinus Torvalds do { 18501da177e4SLinus Torvalds /* Cut or delete file item. */ 1851ee93961bSJeff Mahoney deleted = 1852bd4c625cSLinus Torvalds reiserfs_cut_from_item(th, &s_search_path, &s_item_key, 1853ee93961bSJeff Mahoney inode, page, new_file_size); 1854ee93961bSJeff Mahoney if (deleted < 0) { 1855995c762eSJeff Mahoney reiserfs_warning(inode->i_sb, "vs-5665", 185645b03d5eSJeff Mahoney "reiserfs_cut_from_item failed"); 18571da177e4SLinus Torvalds reiserfs_check_path(&s_search_path); 18581da177e4SLinus Torvalds return 0; 18591da177e4SLinus Torvalds } 18601da177e4SLinus Torvalds 1861ee93961bSJeff Mahoney RFALSE(deleted > file_size, 18621da177e4SLinus Torvalds "PAP-5670: reiserfs_cut_from_item: too many bytes deleted: deleted %d, file_size %lu, item_key %K", 1863ee93961bSJeff Mahoney deleted, file_size, &s_item_key); 18641da177e4SLinus Torvalds 18651da177e4SLinus Torvalds /* Change key to search the last file item. */ 1866ee93961bSJeff Mahoney file_size -= deleted; 18671da177e4SLinus Torvalds 1868ee93961bSJeff Mahoney set_cpu_key_k_offset(&s_item_key, file_size); 18691da177e4SLinus Torvalds 18701da177e4SLinus Torvalds /* While there are bytes to truncate and previous file item is presented in the tree. */ 18711da177e4SLinus Torvalds 18721da177e4SLinus Torvalds /* 18731da177e4SLinus Torvalds ** This loop could take a really long time, and could log 18741da177e4SLinus Torvalds ** many more blocks than a transaction can hold. So, we do a polite 18751da177e4SLinus Torvalds ** journal end here, and if the transaction needs ending, we make 18761da177e4SLinus Torvalds ** sure the file is consistent before ending the current trans 18771da177e4SLinus Torvalds ** and starting a new one 18781da177e4SLinus Torvalds */ 187923f9e0f8SAlexander Zarochentzev if (journal_transaction_should_end(th, 0) || 188023f9e0f8SAlexander Zarochentzev reiserfs_transaction_free_space(th) <= JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) { 18811da177e4SLinus Torvalds int orig_len_alloc = th->t_blocks_allocated; 18823cd6dbe6SJeff Mahoney pathrelse(&s_search_path); 18831da177e4SLinus Torvalds 18841da177e4SLinus Torvalds if (update_timestamps) { 1885995c762eSJeff Mahoney inode->i_mtime = CURRENT_TIME_SEC; 1886995c762eSJeff Mahoney inode->i_ctime = CURRENT_TIME_SEC; 18871da177e4SLinus Torvalds } 1888995c762eSJeff Mahoney reiserfs_update_sd(th, inode); 18891da177e4SLinus Torvalds 1890995c762eSJeff Mahoney err = journal_end(th, inode->i_sb, orig_len_alloc); 18911da177e4SLinus Torvalds if (err) 18921da177e4SLinus Torvalds goto out; 1893995c762eSJeff Mahoney err = journal_begin(th, inode->i_sb, 189423f9e0f8SAlexander Zarochentzev JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD + JOURNAL_PER_BALANCE_CNT * 4) ; 18951da177e4SLinus Torvalds if (err) 18961da177e4SLinus Torvalds goto out; 1897995c762eSJeff Mahoney reiserfs_update_inode_transaction(inode); 18981da177e4SLinus Torvalds } 1899ee93961bSJeff Mahoney } while (file_size > ROUND_UP(new_file_size) && 1900995c762eSJeff Mahoney search_for_position_by_key(inode->i_sb, &s_item_key, 1901bd4c625cSLinus Torvalds &s_search_path) == POSITION_FOUND); 19021da177e4SLinus Torvalds 1903ee93961bSJeff Mahoney RFALSE(file_size > ROUND_UP(new_file_size), 19041da177e4SLinus Torvalds "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %d", 1905ee93961bSJeff Mahoney new_file_size, file_size, s_item_key.on_disk_key.k_objectid); 19061da177e4SLinus Torvalds 19071da177e4SLinus Torvalds update_and_out: 19081da177e4SLinus Torvalds if (update_timestamps) { 19091da177e4SLinus Torvalds // this is truncate, not file closing 1910995c762eSJeff Mahoney inode->i_mtime = CURRENT_TIME_SEC; 1911995c762eSJeff Mahoney inode->i_ctime = CURRENT_TIME_SEC; 19121da177e4SLinus Torvalds } 1913995c762eSJeff Mahoney reiserfs_update_sd(th, inode); 19141da177e4SLinus Torvalds 19151da177e4SLinus Torvalds out: 19161da177e4SLinus Torvalds pathrelse(&s_search_path); 19171da177e4SLinus Torvalds return err; 19181da177e4SLinus Torvalds } 19191da177e4SLinus Torvalds 19201da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 19211da177e4SLinus Torvalds // this makes sure, that we __append__, not overwrite or add holes 1922fec6d055SJosef "Jeff" Sipek static void check_research_for_paste(struct treepath *path, 1923d68caa95SJeff Mahoney const struct cpu_key *key) 19241da177e4SLinus Torvalds { 19251da177e4SLinus Torvalds struct item_head *found_ih = get_ih(path); 19261da177e4SLinus Torvalds 19271da177e4SLinus Torvalds if (is_direct_le_ih(found_ih)) { 1928bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1929bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1930bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1931d68caa95SJeff Mahoney cpu_key_k_offset(key) 1932bd4c625cSLinus Torvalds || op_bytes_number(found_ih, 1933bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1934bd4c625cSLinus Torvalds pos_in_item(path)) 1935c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5720", "found direct item " 1936c3a9c210SJeff Mahoney "%h or position (%d) does not match " 1937c3a9c210SJeff Mahoney "to key %K", found_ih, 1938d68caa95SJeff Mahoney pos_in_item(path), key); 19391da177e4SLinus Torvalds } 19401da177e4SLinus Torvalds if (is_indirect_le_ih(found_ih)) { 1941bd4c625cSLinus Torvalds if (le_ih_k_offset(found_ih) + 1942bd4c625cSLinus Torvalds op_bytes_number(found_ih, 1943bd4c625cSLinus Torvalds get_last_bh(path)->b_size) != 1944d68caa95SJeff Mahoney cpu_key_k_offset(key) 1945bd4c625cSLinus Torvalds || I_UNFM_NUM(found_ih) != pos_in_item(path) 1946bd4c625cSLinus Torvalds || get_ih_free_space(found_ih) != 0) 1947c3a9c210SJeff Mahoney reiserfs_panic(NULL, "PAP-5730", "found indirect " 1948c3a9c210SJeff Mahoney "item (%h) or position (%d) does not " 1949c3a9c210SJeff Mahoney "match to key (%K)", 1950d68caa95SJeff Mahoney found_ih, pos_in_item(path), key); 19511da177e4SLinus Torvalds } 19521da177e4SLinus Torvalds } 19531da177e4SLinus Torvalds #endif /* config reiserfs check */ 19541da177e4SLinus Torvalds 19551da177e4SLinus Torvalds /* Paste bytes to the existing item. Returns bytes number pasted into the item. */ 1956d68caa95SJeff Mahoney int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, struct treepath *search_path, /* Path to the pasted item. */ 1957d68caa95SJeff Mahoney const struct cpu_key *key, /* Key to search for the needed item. */ 19581da177e4SLinus Torvalds struct inode *inode, /* Inode item belongs to */ 1959d68caa95SJeff Mahoney const char *body, /* Pointer to the bytes to paste. */ 1960ee93961bSJeff Mahoney int pasted_size) 1961bd4c625cSLinus Torvalds { /* Size of pasted bytes. */ 1962*d2d0395fSJeff Mahoney struct super_block *sb = inode->i_sb; 19631da177e4SLinus Torvalds struct tree_balance s_paste_balance; 19641da177e4SLinus Torvalds int retval; 19651da177e4SLinus Torvalds int fs_gen; 1966*d2d0395fSJeff Mahoney int depth; 19671da177e4SLinus Torvalds 19681da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 19691da177e4SLinus Torvalds 19701da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 19711da177e4SLinus Torvalds 19721da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 1973bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 1974bd4c625cSLinus Torvalds "reiserquota paste_into_item(): allocating %u id=%u type=%c", 1975ee93961bSJeff Mahoney pasted_size, inode->i_uid, 1976d68caa95SJeff Mahoney key2type(&(key->on_disk_key))); 19771da177e4SLinus Torvalds #endif 19781da177e4SLinus Torvalds 1979*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(sb); 19805dd4056dSChristoph Hellwig retval = dquot_alloc_space_nodirty(inode, pasted_size); 1981*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(sb, depth); 19825dd4056dSChristoph Hellwig if (retval) { 1983d68caa95SJeff Mahoney pathrelse(search_path); 19845dd4056dSChristoph Hellwig return retval; 19851da177e4SLinus Torvalds } 1986d68caa95SJeff Mahoney init_tb_struct(th, &s_paste_balance, th->t_super, search_path, 1987ee93961bSJeff Mahoney pasted_size); 19881da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 1989d68caa95SJeff Mahoney s_paste_balance.key = key->on_disk_key; 19901da177e4SLinus Torvalds #endif 19911da177e4SLinus Torvalds 19921da177e4SLinus Torvalds /* DQUOT_* can schedule, must check before the fix_nodes */ 19931da177e4SLinus Torvalds if (fs_changed(fs_gen, inode->i_sb)) { 19941da177e4SLinus Torvalds goto search_again; 19951da177e4SLinus Torvalds } 19961da177e4SLinus Torvalds 1997bd4c625cSLinus Torvalds while ((retval = 1998bd4c625cSLinus Torvalds fix_nodes(M_PASTE, &s_paste_balance, NULL, 1999d68caa95SJeff Mahoney body)) == REPEAT_SEARCH) { 20001da177e4SLinus Torvalds search_again: 20011da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 20021da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, paste_into_item_restarted); 2003bd4c625cSLinus Torvalds retval = 2004d68caa95SJeff Mahoney search_for_position_by_key(th->t_super, key, 2005d68caa95SJeff Mahoney search_path); 20061da177e4SLinus Torvalds if (retval == IO_ERROR) { 20071da177e4SLinus Torvalds retval = -EIO; 20081da177e4SLinus Torvalds goto error_out; 20091da177e4SLinus Torvalds } 20101da177e4SLinus Torvalds if (retval == POSITION_FOUND) { 201145b03d5eSJeff Mahoney reiserfs_warning(inode->i_sb, "PAP-5710", 201245b03d5eSJeff Mahoney "entry or pasted byte (%K) exists", 2013d68caa95SJeff Mahoney key); 20141da177e4SLinus Torvalds retval = -EEXIST; 20151da177e4SLinus Torvalds goto error_out; 20161da177e4SLinus Torvalds } 20171da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK 2018d68caa95SJeff Mahoney check_research_for_paste(search_path, key); 20191da177e4SLinus Torvalds #endif 20201da177e4SLinus Torvalds } 20211da177e4SLinus Torvalds 20221da177e4SLinus Torvalds /* Perform balancing after all resources are collected by fix_nodes, and 20231da177e4SLinus Torvalds accessing them will not risk triggering schedule. */ 20241da177e4SLinus Torvalds if (retval == CARRY_ON) { 2025d68caa95SJeff Mahoney do_balance(&s_paste_balance, NULL /*ih */ , body, M_PASTE); 20261da177e4SLinus Torvalds return 0; 20271da177e4SLinus Torvalds } 20281da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 20291da177e4SLinus Torvalds error_out: 20301da177e4SLinus Torvalds /* this also releases the path */ 20311da177e4SLinus Torvalds unfix_nodes(&s_paste_balance); 20321da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2033bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2034bd4c625cSLinus Torvalds "reiserquota paste_into_item(): freeing %u id=%u type=%c", 2035ee93961bSJeff Mahoney pasted_size, inode->i_uid, 2036d68caa95SJeff Mahoney key2type(&(key->on_disk_key))); 20371da177e4SLinus Torvalds #endif 2038*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(sb); 20395dd4056dSChristoph Hellwig dquot_free_space_nodirty(inode, pasted_size); 2040*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(sb, depth); 20411da177e4SLinus Torvalds return retval; 20421da177e4SLinus Torvalds } 20431da177e4SLinus Torvalds 2044d68caa95SJeff Mahoney /* Insert new item into the buffer at the path. 2045d68caa95SJeff Mahoney * th - active transaction handle 2046d68caa95SJeff Mahoney * path - path to the inserted item 2047d68caa95SJeff Mahoney * ih - pointer to the item header to insert 2048d68caa95SJeff Mahoney * body - pointer to the bytes to insert 2049d68caa95SJeff Mahoney */ 2050d68caa95SJeff Mahoney int reiserfs_insert_item(struct reiserfs_transaction_handle *th, 2051d68caa95SJeff Mahoney struct treepath *path, const struct cpu_key *key, 2052d68caa95SJeff Mahoney struct item_head *ih, struct inode *inode, 2053d68caa95SJeff Mahoney const char *body) 2054d68caa95SJeff Mahoney { 20551da177e4SLinus Torvalds struct tree_balance s_ins_balance; 20561da177e4SLinus Torvalds int retval; 20571da177e4SLinus Torvalds int fs_gen = 0; 20581da177e4SLinus Torvalds int quota_bytes = 0; 20591da177e4SLinus Torvalds 20601da177e4SLinus Torvalds BUG_ON(!th->t_trans_id); 20611da177e4SLinus Torvalds 20621da177e4SLinus Torvalds if (inode) { /* Do we count quotas for item? */ 2063*d2d0395fSJeff Mahoney int depth; 20641da177e4SLinus Torvalds fs_gen = get_generation(inode->i_sb); 2065d68caa95SJeff Mahoney quota_bytes = ih_item_len(ih); 20661da177e4SLinus Torvalds 20671da177e4SLinus Torvalds /* hack so the quota code doesn't have to guess if the file has 20681da177e4SLinus Torvalds ** a tail, links are always tails, so there's no guessing needed 20691da177e4SLinus Torvalds */ 2070d68caa95SJeff Mahoney if (!S_ISLNK(inode->i_mode) && is_direct_le_ih(ih)) 20711da177e4SLinus Torvalds quota_bytes = inode->i_sb->s_blocksize + UNFM_P_SIZE; 20721da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2073bd4c625cSLinus Torvalds reiserfs_debug(inode->i_sb, REISERFS_DEBUG_CODE, 2074bd4c625cSLinus Torvalds "reiserquota insert_item(): allocating %u id=%u type=%c", 2075d68caa95SJeff Mahoney quota_bytes, inode->i_uid, head2type(ih)); 20761da177e4SLinus Torvalds #endif 20771da177e4SLinus Torvalds /* We can't dirty inode here. It would be immediately written but 20781da177e4SLinus Torvalds * appropriate stat item isn't inserted yet... */ 2079*d2d0395fSJeff Mahoney depth = reiserfs_write_unlock_nested(inode->i_sb); 20805dd4056dSChristoph Hellwig retval = dquot_alloc_space_nodirty(inode, quota_bytes); 2081*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(inode->i_sb, depth); 20825dd4056dSChristoph Hellwig if (retval) { 2083d68caa95SJeff Mahoney pathrelse(path); 20845dd4056dSChristoph Hellwig return retval; 20851da177e4SLinus Torvalds } 20861da177e4SLinus Torvalds } 2087d68caa95SJeff Mahoney init_tb_struct(th, &s_ins_balance, th->t_super, path, 2088d68caa95SJeff Mahoney IH_SIZE + ih_item_len(ih)); 20891da177e4SLinus Torvalds #ifdef DISPLACE_NEW_PACKING_LOCALITIES 20901da177e4SLinus Torvalds s_ins_balance.key = key->on_disk_key; 20911da177e4SLinus Torvalds #endif 20921da177e4SLinus Torvalds /* DQUOT_* can schedule, must check to be sure calling fix_nodes is safe */ 20931da177e4SLinus Torvalds if (inode && fs_changed(fs_gen, inode->i_sb)) { 20941da177e4SLinus Torvalds goto search_again; 20951da177e4SLinus Torvalds } 20961da177e4SLinus Torvalds 2097bd4c625cSLinus Torvalds while ((retval = 2098d68caa95SJeff Mahoney fix_nodes(M_INSERT, &s_ins_balance, ih, 2099d68caa95SJeff Mahoney body)) == REPEAT_SEARCH) { 21001da177e4SLinus Torvalds search_again: 21011da177e4SLinus Torvalds /* file system changed while we were in the fix_nodes */ 21021da177e4SLinus Torvalds PROC_INFO_INC(th->t_super, insert_item_restarted); 2103d68caa95SJeff Mahoney retval = search_item(th->t_super, key, path); 21041da177e4SLinus Torvalds if (retval == IO_ERROR) { 21051da177e4SLinus Torvalds retval = -EIO; 21061da177e4SLinus Torvalds goto error_out; 21071da177e4SLinus Torvalds } 21081da177e4SLinus Torvalds if (retval == ITEM_FOUND) { 210945b03d5eSJeff Mahoney reiserfs_warning(th->t_super, "PAP-5760", 2110bd4c625cSLinus Torvalds "key %K already exists in the tree", 2111bd4c625cSLinus Torvalds key); 21121da177e4SLinus Torvalds retval = -EEXIST; 21131da177e4SLinus Torvalds goto error_out; 21141da177e4SLinus Torvalds } 21151da177e4SLinus Torvalds } 21161da177e4SLinus Torvalds 21171da177e4SLinus Torvalds /* make balancing after all resources will be collected at a time */ 21181da177e4SLinus Torvalds if (retval == CARRY_ON) { 2119d68caa95SJeff Mahoney do_balance(&s_ins_balance, ih, body, M_INSERT); 21201da177e4SLinus Torvalds return 0; 21211da177e4SLinus Torvalds } 21221da177e4SLinus Torvalds 21231da177e4SLinus Torvalds retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO; 21241da177e4SLinus Torvalds error_out: 21251da177e4SLinus Torvalds /* also releases the path */ 21261da177e4SLinus Torvalds unfix_nodes(&s_ins_balance); 21271da177e4SLinus Torvalds #ifdef REISERQUOTA_DEBUG 2128bd4c625cSLinus Torvalds reiserfs_debug(th->t_super, REISERFS_DEBUG_CODE, 2129bd4c625cSLinus Torvalds "reiserquota insert_item(): freeing %u id=%u type=%c", 2130d68caa95SJeff Mahoney quota_bytes, inode->i_uid, head2type(ih)); 21311da177e4SLinus Torvalds #endif 2132*d2d0395fSJeff Mahoney if (inode) { 2133*d2d0395fSJeff Mahoney int depth = reiserfs_write_unlock_nested(inode->i_sb); 21345dd4056dSChristoph Hellwig dquot_free_space_nodirty(inode, quota_bytes); 2135*d2d0395fSJeff Mahoney reiserfs_write_lock_nested(inode->i_sb, depth); 2136*d2d0395fSJeff Mahoney } 21371da177e4SLinus Torvalds return retval; 21381da177e4SLinus Torvalds } 2139