开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 嵌入式/单片机编程 > 嵌入式Linux > 查看源码
stree.c
资源名称：SBC-2410X_kernel.tar.gz　[点击查看]
上传用户：lgb322
上传日期：2013-02-24
资源大小：30529k
文件大小：65k
源码类别：

嵌入式Linux

开发平台：

Unix_Linux

stree.c：源码内容
  1. /*
  2.  *  Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
  3.  */
  5. /*
  6.  *  Written by Anatoly P. Pinchuk pap@namesys.botik.ru
  7.  *  Programm System Institute
  8.  *  Pereslavl-Zalessky Russia
  9.  */
  11. /*
  12.  *  This file contains functions dealing with S+tree
  13.  *
  14.  * B_IS_IN_TREE
  15.  * copy_short_key
  16.  * copy_item_head
  17.  * comp_short_keys
  18.  * comp_keys
  19.  * comp_cpu_keys
  20.  * comp_short_le_keys
  21.  * comp_short_cpu_keys
  22.  * cpu_key2cpu_key
  23.  * le_key2cpu_key
  24.  * comp_le_keys
  25.  * bin_search
  26.  * get_lkey
  27.  * get_rkey
  28.  * key_in_buffer
  29.  * decrement_bcount
  30.  * decrement_counters_in_path
  31.  * reiserfs_check_path
  32.  * pathrelse_and_restore
  33.  * pathrelse
  34.  * search_by_key_reada
  35.  * search_by_key
  36.  * search_for_position_by_key
  37.  * comp_items
  38.  * prepare_for_direct_item
  39.  * prepare_for_direntry_item
  40.  * prepare_for_delete_or_cut
  41.  * calc_deleted_bytes_number
  42.  * init_tb_struct
  43.  * padd_item
  44.  * reiserfs_delete_item
  45.  * reiserfs_delete_solid_item
  46.  * reiserfs_delete_object
  47.  * maybe_indirect_to_direct
  48.  * indirect_to_direct_roll_back
  49.  * reiserfs_cut_from_item
  50.  * truncate_directory
  51.  * reiserfs_do_truncate
  52.  * reiserfs_paste_into_item
  53.  * reiserfs_insert_item
  54.  */
  56. #include <linux/config.h>
  57. #include <linux/sched.h>
  58. #include <linux/string.h>
  59. #include <linux/locks.h>
  60. #include <linux/pagemap.h>
  61. #include <linux/reiserfs_fs.h>
  62. #include <linux/smp_lock.h>
  64. /* Does the buffer contain a disk block which is in the tree. */
  65. inline int B_IS_IN_TREE (const struct buffer_head * p_s_bh)
  66. {
  68.   RFALSE( B_LEVEL (p_s_bh) > MAX_HEIGHT,
  69.   "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);
  71.   return ( B_LEVEL (p_s_bh) != FREE_LEVEL );
  72. }
  77. inline void copy_short_key (void * to, const void * from)
  78. {
  79.     memcpy (to, from, SHORT_KEY_SIZE);
  80. }
  82. //
  83. // to gets item head in le form
  84. //
  85. inline void copy_item_head(struct item_head * p_v_to, 
  86.    const struct item_head * p_v_from)
  87. {
  88.   memcpy (p_v_to, p_v_from, IH_SIZE);
  89. }
  92. /* k1 is pointer to on-disk structure which is stored in little-endian
  93.    form. k2 is pointer to cpu variable. For key of items of the same
  94.    object this returns 0.
  95.    Returns: -1 if key1 < key2 
  96.    0 if key1 == key2
  97.    1 if key1 > key2 */
  98. inline int  comp_short_keys (const struct key * le_key, 
  99.      const struct cpu_key * cpu_key)
  100. {
  101.   __u32 * p_s_le_u32, * p_s_cpu_u32;
  102.   int n_key_length = REISERFS_SHORT_KEY_LEN;
  104.   p_s_le_u32 = (__u32 *)le_key;
  105.   p_s_cpu_u32 = (__u32 *)cpu_key;
  106.   for( ; n_key_length--; ++p_s_le_u32, ++p_s_cpu_u32 ) {
  107.     if ( le32_to_cpu (*p_s_le_u32) < *p_s_cpu_u32 )
  108.       return -1;
  109.     if ( le32_to_cpu (*p_s_le_u32) > *p_s_cpu_u32 )
  110.       return 1;
  111.   }
  113.   return 0;
  114. }
  117. /* k1 is pointer to on-disk structure which is stored in little-endian
  118.    form. k2 is pointer to cpu variable.
  119.    Compare keys using all 4 key fields.
  120.    Returns: -1 if key1 < key2 0
  121.    if key1 = key2 1 if key1 > key2 */
  122. inline int  comp_keys (const struct key * le_key, const struct cpu_key * cpu_key)
  123. {
  124.   int retval;
  126.   retval = comp_short_keys (le_key, cpu_key);
  127.   if (retval)
  128.       return retval;
  129.   if (le_key_k_offset (le_key_version(le_key), le_key) < cpu_key_k_offset (cpu_key))
  130.       return -1;
  131.   if (le_key_k_offset (le_key_version(le_key), le_key) > cpu_key_k_offset (cpu_key))
  132.       return 1;
  134.   if (cpu_key->key_length == 3)
  135.       return 0;
  137.   /* this part is needed only when tail conversion is in progress */
  138.   if (le_key_k_type (le_key_version(le_key), le_key) < cpu_key_k_type (cpu_key))
  139.     return -1;
  141.   if (le_key_k_type (le_key_version(le_key), le_key) > cpu_key_k_type (cpu_key))
  142.     return 1;
  144.   return 0;
  145. }
  148. //
  149. // FIXME: not used yet
  150. //
  151. inline int comp_cpu_keys (const struct cpu_key * key1, 
  152.   const struct cpu_key * key2)
  153. {
  154.     if (key1->on_disk_key.k_dir_id < key2->on_disk_key.k_dir_id)
  155. return -1;
  156.     if (key1->on_disk_key.k_dir_id > key2->on_disk_key.k_dir_id)
  157. return 1;
  159.     if (key1->on_disk_key.k_objectid < key2->on_disk_key.k_objectid)
  160. return -1;
  161.     if (key1->on_disk_key.k_objectid > key2->on_disk_key.k_objectid)
  162. return 1;
  164.     if (cpu_key_k_offset (key1) < cpu_key_k_offset (key2))
  165. return -1;
  166.     if (cpu_key_k_offset (key1) > cpu_key_k_offset (key2))
  167. return 1;
  169.     reiserfs_warning ("comp_cpu_keys: type are compared for %k and %kn",
  170.       key1, key2);
  172.     if (cpu_key_k_type (key1) < cpu_key_k_type (key2))
  173. return -1;
  174.     if (cpu_key_k_type (key1) > cpu_key_k_type (key2))
  175. return 1;
  176.     return 0;
  177. }
  179. inline int comp_short_le_keys (const struct key * key1, const struct key * key2)
  180. {
  181.   __u32 * p_s_1_u32, * p_s_2_u32;
  182.   int n_key_length = REISERFS_SHORT_KEY_LEN;
  184.   p_s_1_u32 = (__u32 *)key1;
  185.   p_s_2_u32 = (__u32 *)key2;
  186.   for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
  187.     if ( le32_to_cpu (*p_s_1_u32) < le32_to_cpu (*p_s_2_u32) )
  188.       return -1;
  189.     if ( le32_to_cpu (*p_s_1_u32) > le32_to_cpu (*p_s_2_u32) )
  190.       return 1;
  191.   }
  192.   return 0;
  193. }
  195. inline int comp_short_cpu_keys (const struct cpu_key * key1, 
  196. const struct cpu_key * key2)
  197. {
  198.   __u32 * p_s_1_u32, * p_s_2_u32;
  199.   int n_key_length = REISERFS_SHORT_KEY_LEN;
  201.   p_s_1_u32 = (__u32 *)key1;
  202.   p_s_2_u32 = (__u32 *)key2;
  204.   for( ; n_key_length--; ++p_s_1_u32, ++p_s_2_u32 ) {
  205.     if ( *p_s_1_u32 < *p_s_2_u32 )
  206.       return -1;
  207.     if ( *p_s_1_u32 > *p_s_2_u32 )
  208.       return 1;
  209.   }
  210.   return 0;
  211. }
  215. inline void cpu_key2cpu_key (struct cpu_key * to, const struct cpu_key * from)
  216. {
  217.     memcpy (to, from, sizeof (struct cpu_key));
  218. }
  221. inline void le_key2cpu_key (struct cpu_key * to, const struct key * from)
  222. {
  223.     to->on_disk_key.k_dir_id = le32_to_cpu (from->k_dir_id);
  224.     to->on_disk_key.k_objectid = le32_to_cpu (from->k_objectid);
  225.     
  226.     // find out version of the key
  227.     to->version = le_key_version (from);
  228.     if (to->version == KEY_FORMAT_3_5) {
  229. to->on_disk_key.u.k_offset_v1.k_offset = le32_to_cpu (from->u.k_offset_v1.k_offset);
  230. to->on_disk_key.u.k_offset_v1.k_uniqueness = le32_to_cpu (from->u.k_offset_v1.k_uniqueness);
  231.     } else {
  232. to->on_disk_key.u.k_offset_v2.k_offset = offset_v2_k_offset(&from->u.k_offset_v2);
  233. to->on_disk_key.u.k_offset_v2.k_type = offset_v2_k_type(&from->u.k_offset_v2);
  234.     } 
  235. }
  239. // this does not say which one is bigger, it only returns 1 if keys
  240. // are not equal, 0 otherwise
  241. inline int comp_le_keys (const struct key * k1, const struct key * k2)
  242. {
  243.     return memcmp (k1, k2, sizeof (struct key));
  244. }
  246. /**************************************************************************
  247.  *  Binary search toolkit function                                        *
  248.  *  Search for an item in the array by the item key                       *
  249.  *  Returns:    1 if found,  0 if not found;                              *
  250.  *        *p_n_pos = number of the searched element if found, else the    *
  251.  *        number of the first element that is larger than p_v_key.        *
  252.  **************************************************************************/
  253. /* For those not familiar with binary search: n_lbound is the leftmost item that it
  254.  could be, n_rbound the rightmost item that it could be.  We examine the item
  255.  halfway between n_lbound and n_rbound, and that tells us either that we can increase
  256.  n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
  257.  there are no possible items, and we have not found it. With each examination we
  258.  cut the number of possible items it could be by one more than half rounded down,
  259.  or we find it. */
  260. inline int bin_search (
  261.               const void * p_v_key, /* Key to search for.                   */
  262.       const void * p_v_base,/* First item in the array.             */
  263.       int       p_n_num,    /* Number of items in the array.        */
  264.       int       p_n_width,  /* Item size in the array.
  265.        searched. Lest the reader be
  266.        confused, note that this is crafted
  267.        as a general function, and when it
  268.        is applied specifically to the array
  269.        of item headers in a node, p_n_width
  270.        is actually the item header size not
  271.        the item size.                      */
  272.       int     * p_n_pos     /* Number of the searched for element. */
  273.             ) {
  274.     int   n_rbound, n_lbound, n_j;
  276.    for ( n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0))/2; n_lbound <= n_rbound; n_j = (n_rbound + n_lbound)/2 )
  277.      switch( COMP_KEYS((struct key *)((char * )p_v_base + n_j * p_n_width), (struct cpu_key *)p_v_key) )  {
  278.      case -1: n_lbound = n_j + 1; continue;
  279.      case  1: n_rbound = n_j - 1; continue;
  280.      case  0: *p_n_pos = n_j;     return ITEM_FOUND; /* Key found in the array.  */
  281.         }
  283.     /* bin_search did not find given key, it returns position of key,
  284.         that is minimal and greater than the given one. */
  285.     *p_n_pos = n_lbound;
  286.     return ITEM_NOT_FOUND;
  287. }
  289. #ifdef CONFIG_REISERFS_CHECK
  290. extern struct tree_balance * cur_tb;
  291. #endif
  295. /* Minimal possible key. It is never in the tree. */
  296. const struct key  MIN_KEY = {0, 0, {{0, 0},}};
  298. /* Maximal possible key. It is never in the tree. */
  299. const struct key  MAX_KEY = {0xffffffff, 0xffffffff, {{0xffffffff, 0xffffffff},}};
  302. /* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
  303.    of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
  304.    the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
  305.    case we return a special key, either MIN_KEY or MAX_KEY. */
  306. inline const struct  key * get_lkey  (
  307.                 const struct path         * p_s_chk_path,
  308.                         const struct super_block  * p_s_sb
  309.                       ) {
  310.   int                   n_position, n_path_offset = p_s_chk_path->path_length;
  311.   struct buffer_head  * p_s_parent;
  312.   
  313.   RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET, 
  314.   "PAP-5010: illegal offset in the path");
  316.   /* While not higher in path than first element. */
  317.   while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
  319.     RFALSE( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
  320.     "PAP-5020: parent is not uptodate");
  322.     /* Parent at the path is not in the tree now. */
  323.     if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
  324.       return &MAX_KEY;
  325.     /* Check whether position in the parent is correct. */
  326.     if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
  327.        return &MAX_KEY;
  328.     /* Check whether parent at the path really points to the child. */
  329.     if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
  330.  PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
  331.       return &MAX_KEY;
  332.     /* Return delimiting key if position in the parent is not equal to zero. */
  333.     if ( n_position )
  334.       return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
  335.   }
  336.   /* Return MIN_KEY if we are in the root of the buffer tree. */
  337.   if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
  338.        SB_ROOT_BLOCK (p_s_sb) )
  339.     return &MIN_KEY;
  340.   return  &MAX_KEY;
  341. }
  344. /* Get delimiting key of the buffer at the path and its right neighbor. */
  345. inline const struct  key * get_rkey  (
  346.                 const struct path         * p_s_chk_path,
  347.                         const struct super_block  * p_s_sb
  348.                       ) {
  349.   int                   n_position,
  350.      n_path_offset = p_s_chk_path->path_length;
  351.   struct buffer_head  * p_s_parent;
  353.   RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
  354.   "PAP-5030: illegal offset in the path");
  356.   while ( n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET ) {
  358.     RFALSE( ! buffer_uptodate(PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
  359.     "PAP-5040: parent is not uptodate");
  361.     /* Parent at the path is not in the tree now. */
  362.     if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)) )
  363.       return &MIN_KEY;
  364.     /* Check whether position in the parent is correct. */
  365.     if ( (n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent) )
  366.       return &MIN_KEY;
  367.     /* Check whether parent at the path really points to the child. */
  368.     if ( B_N_CHILD_NUM(p_s_parent, n_position) !=
  369.                                         PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blocknr )
  370.       return &MIN_KEY;
  371.     /* Return delimiting key if position in the parent is not the last one. */
  372.     if ( n_position != B_NR_ITEMS(p_s_parent) )
  373.       return B_N_PDELIM_KEY(p_s_parent, n_position);
  374.   }
  375.   /* Return MAX_KEY if we are in the root of the buffer tree. */
  376.   if ( PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
  377.        SB_ROOT_BLOCK (p_s_sb) )
  378.     return &MAX_KEY;
  379.   return  &MIN_KEY;
  380. }
  383. /* Check whether a key is contained in the tree rooted from a buffer at a path. */
  384. /* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
  385.    the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
  386.    buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
  387.    this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
  388. static  inline  int key_in_buffer (
  389.                       struct path         * p_s_chk_path, /* Path which should be checked.  */
  390.                       const struct cpu_key      * p_s_key,      /* Key which should be checked.   */
  391.                       struct super_block  * p_s_sb        /* Super block pointer.           */
  392.       ) {
  394.   RFALSE( ! p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET ||
  395.   p_s_chk_path->path_length > MAX_HEIGHT,
  396.   "PAP-5050: pointer to the key(%p) is NULL or illegal path length(%d)",
  397.   p_s_key, p_s_chk_path->path_length);
  398.   RFALSE( PATH_PLAST_BUFFER(p_s_chk_path)->b_dev == NODEV,
  399.   "PAP-5060: device must not be NODEV");
  401.   if ( COMP_KEYS(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1 )
  402.     /* left delimiting key is bigger, that the key we look for */
  403.     return 0;
  404.   //  if ( COMP_KEYS(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
  405.   if ( COMP_KEYS(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1 )
  406.     /* p_s_key must be less than right delimitiing key */
  407.     return 0;
  408.   return 1;
  409. }
  412. inline void decrement_bcount(
  413.               struct buffer_head  * p_s_bh
  414.             ) { 
  415.   if ( p_s_bh ) {
  416.     if ( atomic_read (&(p_s_bh->b_count)) ) {
  417.       put_bh(p_s_bh) ;
  418.       return;
  419.     }
  420.     reiserfs_panic(NULL, "PAP-5070: decrement_bcount: trying to free free buffer %b", p_s_bh);
  421.   }
  422. }
  425. /* Decrement b_count field of the all buffers in the path. */
  426. void decrement_counters_in_path (
  427.               struct path * p_s_search_path
  428.             ) {
  429.   int n_path_offset = p_s_search_path->path_length;
  431.   RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
  432.   n_path_offset > EXTENDED_MAX_HEIGHT - 1,
  433.   "PAP-5080: illegal path offset of %d", n_path_offset);
  435.   while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET ) {
  436.     struct buffer_head * bh;
  438.     bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
  439.     decrement_bcount (bh);
  440.   }
  441.   p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
  442. }
  445. int reiserfs_check_path(struct path *p) {
  446.   RFALSE( p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
  447.   "path not properly relsed") ;
  448.   return 0 ;
  449. }
  452. /* Release all buffers in the path. Restore dirty bits clean
  453. ** when preparing the buffer for the log
  454. **
  455. ** only called from fix_nodes()
  456. */
  457. void  pathrelse_and_restore (
  458. struct super_block *s, 
  459.         struct path * p_s_search_path
  460.       ) {
  461.   int n_path_offset = p_s_search_path->path_length;
  463.   RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 
  464.   "clm-4000: illegal path offset");
  465.   
  466.   while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )  {
  467.     reiserfs_restore_prepared_buffer(s, PATH_OFFSET_PBUFFER(p_s_search_path, 
  468.                                      n_path_offset));
  469.     brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
  470.   }
  471.   p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
  472. }
  474. /* Release all buffers in the path. */
  475. void  pathrelse (
  476.         struct path * p_s_search_path
  477.       ) {
  478.   int n_path_offset = p_s_search_path->path_length;
  480.   RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
  481.   "PAP-5090: illegal path offset");
  482.   
  483.   while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )  
  484.     brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
  486.   p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
  487. }
  491. static int is_leaf (char * buf, int blocksize, struct buffer_head * bh)
  492. {
  493.     struct block_head * blkh;
  494.     struct item_head * ih;
  495.     int used_space;
  496.     int prev_location;
  497.     int i;
  498.     int nr;
  500.     blkh = (struct block_head *)buf;
  501.     if ( blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
  502. printk ("is_leaf: this should be caught earliern");
  503. return 0;
  504.     }
  506.     nr = blkh_nr_item(blkh);
  507.     if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
  508. /* item number is too big or too small */
  509. reiserfs_warning ("is_leaf: nr_item seems wrong: %zn", bh);
  510. return 0;
  511.     }
  512.     ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
  513.     used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location (ih));
  514.     if (used_space != blocksize - blkh_free_space(blkh)) {
  515. /* free space does not match to calculated amount of use space */
  516. reiserfs_warning ("is_leaf: free space seems wrong: %zn", bh);
  517. return 0;
  518.     }
  520.     // FIXME: it is_leaf will hit performance too much - we may have
  521.     // return 1 here
  523.     /* check tables of item heads */
  524.     ih = (struct item_head *)(buf + BLKH_SIZE);
  525.     prev_location = blocksize;
  526.     for (i = 0; i < nr; i ++, ih ++) {
  527. if (ih_location (ih) >= blocksize || ih_location (ih) < IH_SIZE * nr) {
  528.     reiserfs_warning ("is_leaf: item location seems wrong: %hn", ih);
  529.     return 0;
  530. }
  531. if (ih_item_len (ih) < 1 || ih_item_len (ih) > MAX_ITEM_LEN (blocksize)) {
  532.     reiserfs_warning ("is_leaf: item length seems wrong: %hn", ih);
  533.     return 0;
  534. }
  535. if (prev_location - ih_location (ih) != ih_item_len (ih)) {
  536.     reiserfs_warning ("is_leaf: item location seems wrong (second one): %hn", ih);
  537.     return 0;
  538. }
  539. prev_location = ih_location (ih);
  540.     }
  542.     // one may imagine much more checks
  543.     return 1;
  544. }
  547. /* returns 1 if buf looks like an internal node, 0 otherwise */
  548. static int is_internal (char * buf, int blocksize, struct buffer_head * bh)
  549. {
  550.     struct block_head * blkh;
  551.     int nr;
  552.     int used_space;
  554.     blkh = (struct block_head *)buf;
  555.     nr = blkh_level(blkh);
  556.     if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
  557. /* this level is not possible for internal nodes */
  558. printk ("is_internal: this should be caught earliern");
  559. return 0;
  560.     }
  561.     
  562.     nr = blkh_nr_item(blkh);
  563.     if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
  564. /* for internal which is not root we might check min number of keys */
  565. reiserfs_warning ("is_internal: number of key seems wrong: %zn", bh);
  566. return 0;
  567.     }
  569.     used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
  570.     if (used_space != blocksize - blkh_free_space(blkh)) {
  571. reiserfs_warning ("is_internal: free space seems wrong: %zn", bh);
  572. return 0;
  573.     }
  575.     // one may imagine much more checks
  576.     return 1;
  577. }
  580. // make sure that bh contains formatted node of reiserfs tree of
  581. // 'level'-th level
  582. static int is_tree_node (struct buffer_head * bh, int level)
  583. {
  584.     if (B_LEVEL (bh) != level) {
  585. printk ("is_tree_node: node level %d does not match to the expected one %dn",
  586. B_LEVEL (bh), level);
  587. return 0;
  588.     }
  589.     if (level == DISK_LEAF_NODE_LEVEL)
  590. return is_leaf (bh->b_data, bh->b_size, bh);
  592.     return is_internal (bh->b_data, bh->b_size, bh);
  593. }
  597. #ifdef SEARCH_BY_KEY_READA
  599. /* The function is NOT SCHEDULE-SAFE! */
  600. static void search_by_key_reada (struct super_block * s, int blocknr)
  601. {
  602.     struct buffer_head * bh;
  603.   
  604.     if (blocknr == 0)
  605. return;
  607.     bh = getblk (s->s_dev, blocknr, s->s_blocksize);
  608.   
  609.     if (!buffer_uptodate (bh)) {
  610. ll_rw_block (READA, 1, &bh);
  611.     }
  612.     bh->b_count --;
  613. }
  615. #endif
  617. /**************************************************************************
  618.  * Algorithm   SearchByKey                                                *
  619.  *             look for item in the Disk S+Tree by its key                *
  620.  * Input:  p_s_sb   -  super block                                        *
  621.  *         p_s_key  - pointer to the key to search                        *
  622.  * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR                         *
  623.  *         p_s_search_path - path from the root to the needed leaf        *
  624.  **************************************************************************/
  626. /* This function fills up the path from the root to the leaf as it
  627.    descends the tree looking for the key.  It uses reiserfs_bread to
  628.    try to find buffers in the cache given their block number.  If it
  629.    does not find them in the cache it reads them from disk.  For each
  630.    node search_by_key finds using reiserfs_bread it then uses
  631.    bin_search to look through that node.  bin_search will find the
  632.    position of the block_number of the next node if it is looking
  633.    through an internal node.  If it is looking through a leaf node
  634.    bin_search will find the position of the item which has key either
  635.    equal to given key, or which is the maximal key less than the given
  636.    key.  search_by_key returns a path that must be checked for the
  637.    correctness of the top of the path but need not be checked for the
  638.    correctness of the bottom of the path */
  639. /* The function is NOT SCHEDULE-SAFE! */
  640. int search_by_key (struct super_block * p_s_sb,
  641.    const struct cpu_key * p_s_key, /* Key to search. */
  642.    struct path * p_s_search_path, /* This structure was
  643.      allocated and initialized
  644.      by the calling
  645.      function. It is filled up
  646.      by this function.  */
  647.    int n_stop_level /* How far down the tree to search. To
  648.                                        stop at leaf level - set to
  649.                                        DISK_LEAF_NODE_LEVEL */
  650.     ) {
  651.     int  n_block_number = SB_ROOT_BLOCK (p_s_sb),
  652.       expected_level = SB_TREE_HEIGHT (p_s_sb),
  653.       n_block_size    = p_s_sb->s_blocksize;
  654.     struct buffer_head  *       p_s_bh;
  655.     struct path_element *       p_s_last_element;
  656.     int n_node_level, n_retval;
  657.     int  right_neighbor_of_leaf_node;
  658.     int fs_gen;
  660. #ifdef CONFIG_REISERFS_CHECK
  661.     int n_repeat_counter = 0;
  662. #endif
  663.     
  664.     PROC_INFO_INC( p_s_sb, search_by_key );
  665.     
  666.     /* As we add each node to a path we increase its count.  This means that
  667.        we must be careful to release all nodes in a path before we either
  668.        discard the path struct or re-use the path struct, as we do here. */
  670.     decrement_counters_in_path(p_s_search_path);
  672.     right_neighbor_of_leaf_node = 0;
  674.     /* With each iteration of this loop we search through the items in the
  675.        current node, and calculate the next current node(next path element)
  676.        for the next iteration of this loop.. */
  677.     while ( 1 ) {
  679. #ifdef CONFIG_REISERFS_CHECK
  680. if ( !(++n_repeat_counter % 50000) )
  681.     reiserfs_warning ("PAP-5100: search_by_key: %s:"
  682.       "there were %d iterations of while loop "
  683.       "looking for key %Kn",
  684.       current->comm, n_repeat_counter, p_s_key);
  685. #endif
  687. /* prep path to have another element added to it. */
  688. p_s_last_element = PATH_OFFSET_PELEMENT(p_s_search_path, ++p_s_search_path->path_length);
  689. fs_gen = get_generation (p_s_sb);
  690. expected_level --;
  692. #ifdef SEARCH_BY_KEY_READA
  693. /* schedule read of right neighbor */
  694. search_by_key_reada (p_s_sb, right_neighbor_of_leaf_node);
  695. #endif
  697. /* Read the next tree node, and set the last element in the path to
  698.            have a pointer to it. */
  699. if ( ! (p_s_bh = p_s_last_element->pe_buffer =
  700. reiserfs_bread(p_s_sb, n_block_number, n_block_size)) ) {
  701.     p_s_search_path->path_length --;
  702.     pathrelse(p_s_search_path);
  703.     return IO_ERROR;
  704. }
  706.   if( fs_changed (fs_gen, p_s_sb) ) {
  707.   PROC_INFO_INC( p_s_sb, search_by_key_fs_changed );
  708.   PROC_INFO_INC( p_s_sb, sbk_fs_changed[ expected_level - 1 ] );
  709.   }
  711. /* It is possible that schedule occurred. We must check whether the key
  712.    to search is still in the tree rooted from the current buffer. If
  713.    not then repeat search from the root. */
  714. if ( fs_changed (fs_gen, p_s_sb) && 
  715.      (!B_IS_IN_TREE (p_s_bh) || !key_in_buffer(p_s_search_path, p_s_key, p_s_sb)) ) {
  716.       PROC_INFO_INC( p_s_sb, search_by_key_restarted );
  717.     PROC_INFO_INC( p_s_sb, sbk_restarted[ expected_level - 1 ] );
  718.     decrement_counters_in_path(p_s_search_path);
  719.     
  720.     /* Get the root block number so that we can repeat the search
  721.                starting from the root. */
  722.     n_block_number = SB_ROOT_BLOCK (p_s_sb);
  723.     expected_level = SB_TREE_HEIGHT (p_s_sb);
  724.     right_neighbor_of_leaf_node = 0;
  725.     
  726.     /* repeat search from the root */
  727.     continue;
  728. }
  730.         /* only check that the key is in the buffer if p_s_key is not
  731.            equal to the MAX_KEY. Latter case is only possible in
  732.            "finish_unfinished()" processing during mount. */
  733.         RFALSE( COMP_KEYS( &MAX_KEY, p_s_key ) && 
  734.                 ! key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
  735. "PAP-5130: key is not in the buffer");
  736. #ifdef CONFIG_REISERFS_CHECK
  737. if ( cur_tb ) {
  738.     print_cur_tb ("5140");
  739.     reiserfs_panic(p_s_sb, "PAP-5140: search_by_key: schedule occurred in do_balance!");
  740. }
  741. #endif
  743. // make sure, that the node contents look like a node of
  744. // certain level
  745. if (!is_tree_node (p_s_bh, expected_level)) {
  746.     reiserfs_warning ("vs-5150: search_by_key: "
  747.       "invalid format found in block %ld. Fsck?n", 
  748.       p_s_bh->b_blocknr);
  749.     pathrelse (p_s_search_path);
  750.     return IO_ERROR;
  751. }
  753. /* ok, we have acquired next formatted node in the tree */
  754. n_node_level = B_LEVEL (p_s_bh);
  756. PROC_INFO_BH_STAT( p_s_sb, p_s_bh, n_node_level - 1 );
  758. RFALSE( n_node_level < n_stop_level,
  759. "vs-5152: tree level (%d) is less than stop level (%d)",
  760. n_node_level, n_stop_level);
  762. n_retval = bin_search( p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
  763.                 B_NR_ITEMS(p_s_bh),
  764.                 ( n_node_level == DISK_LEAF_NODE_LEVEL ) ? IH_SIZE : KEY_SIZE,
  765.                 &(p_s_last_element->pe_position));
  766. if (n_node_level == n_stop_level) {
  767.     return n_retval;
  768. }
  770. /* we are not in the stop level */
  771. if (n_retval == ITEM_FOUND)
  772.     /* item has been found, so we choose the pointer which is to the right of the found one */
  773.     p_s_last_element->pe_position++;
  775. /* if item was not found we choose the position which is to
  776.    the left of the found item. This requires no code,
  777.    bin_search did it already.*/
  779. /* So we have chosen a position in the current node which is
  780.    an internal node.  Now we calculate child block number by
  781.    position in the node. */
  782. n_block_number = B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);
  784. #ifdef SEARCH_BY_KEY_READA
  785. /* if we are going to read leaf node, then calculate its right neighbor if possible */
  786. if (n_node_level == DISK_LEAF_NODE_LEVEL + 1 && p_s_last_element->pe_position < B_NR_ITEMS (p_s_bh))
  787.     right_neighbor_of_leaf_node = B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position + 1);
  788. #endif
  789.     }
  790. }
  793. /* Form the path to an item and position in this item which contains
  794.    file byte defined by p_s_key. If there is no such item
  795.    corresponding to the key, we point the path to the item with
  796.    maximal key less than p_s_key, and *p_n_pos_in_item is set to one
  797.    past the last entry/byte in the item.  If searching for entry in a
  798.    directory item, and it is not found, *p_n_pos_in_item is set to one
  799.    entry more than the entry with maximal key which is less than the
  800.    sought key.
  802.    Note that if there is no entry in this same node which is one more,
  803.    then we point to an imaginary entry.  for direct items, the
  804.    position is in units of bytes, for indirect items the position is
  805.    in units of blocknr entries, for directory items the position is in
  806.    units of directory entries.  */
  808. /* The function is NOT SCHEDULE-SAFE! */
  809. int search_for_position_by_key (struct super_block  * p_s_sb,         /* Pointer to the super block.          */
  810. const struct cpu_key  * p_cpu_key,      /* Key to search (cpu variable)         */
  811. struct path         * p_s_search_path /* Filled up by this function.          */
  812.     ) {
  813.     struct item_head    * p_le_ih; /* pointer to on-disk structure */
  814.     int                   n_blk_size;
  815.     loff_t item_offset, offset;
  816.     struct reiserfs_dir_entry de;
  817.     int retval;
  819.     /* If searching for directory entry. */
  820.     if ( is_direntry_cpu_key (p_cpu_key) )
  821. return  search_by_entry_key (p_s_sb, p_cpu_key, p_s_search_path, &de);
  823.     /* If not searching for directory entry. */
  824.     
  825.     /* If item is found. */
  826.     retval = search_item (p_s_sb, p_cpu_key, p_s_search_path);
  827.     if (retval == IO_ERROR)
  828. return retval;
  829.     if ( retval == ITEM_FOUND )  {
  831. RFALSE( ! ih_item_len(
  832.                 B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
  833.        PATH_LAST_POSITION(p_s_search_path))),
  834.         "PAP-5165: item length equals zero");
  836. pos_in_item(p_s_search_path) = 0;
  837. return POSITION_FOUND;
  838.     }
  840.     RFALSE( ! PATH_LAST_POSITION(p_s_search_path),
  841.     "PAP-5170: position equals zero");
  843.     /* Item is not found. Set path to the previous item. */
  844.     p_le_ih = B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), --PATH_LAST_POSITION(p_s_search_path));
  845.     n_blk_size = p_s_sb->s_blocksize;
  847.     if (comp_short_keys (&(p_le_ih->ih_key), p_cpu_key)) {
  848. return FILE_NOT_FOUND;
  849.     }
  851.     // FIXME: quite ugly this far
  853.     item_offset = le_ih_k_offset (p_le_ih);
  854.     offset = cpu_key_k_offset (p_cpu_key);
  856.     /* Needed byte is contained in the item pointed to by the path.*/
  857.     if (item_offset <= offset &&
  858. item_offset + op_bytes_number (p_le_ih, n_blk_size) > offset) {
  859. pos_in_item (p_s_search_path) = offset - item_offset;
  860. if ( is_indirect_le_ih(p_le_ih) ) {
  861.     pos_in_item (p_s_search_path) /= n_blk_size;
  862. }
  863. return POSITION_FOUND;
  864.     }
  866.     /* Needed byte is not contained in the item pointed to by the
  867.      path. Set pos_in_item out of the item. */
  868.     if ( is_indirect_le_ih (p_le_ih) )
  869. pos_in_item (p_s_search_path) = ih_item_len(p_le_ih) / UNFM_P_SIZE;
  870.     else
  871.         pos_in_item (p_s_search_path) = ih_item_len( p_le_ih );
  872.   
  873.     return POSITION_NOT_FOUND;
  874. }
  877. /* Compare given item and item pointed to by the path. */
  878. int comp_items (const struct item_head * stored_ih, const struct path * p_s_path)
  879. {
  880.     struct buffer_head  * p_s_bh;
  881.     struct item_head    * ih;
  883.     /* Last buffer at the path is not in the tree. */
  884.     if ( ! B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)) )
  885. return 1;
  887.     /* Last path position is invalid. */
  888.     if ( PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh) )
  889. return 1;
  891.     /* we need only to know, whether it is the same item */
  892.     ih = get_ih (p_s_path);
  893.     return memcmp (stored_ih, ih, IH_SIZE);
  894. }
  897. /* unformatted nodes are not logged anymore, ever.  This is safe
  898. ** now
  899. */
  900. #define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)
  902. // block can not be forgotten as it is in I/O or held by someone
  903. #define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))
  907. // prepare for delete or cut of direct item
  908. static inline int prepare_for_direct_item (struct path * path,
  909.    struct item_head * le_ih,
  910.    struct inode * inode,
  911.    loff_t new_file_length,
  912.    int * cut_size)
  913. {
  914.     loff_t round_len;
  917.     if ( new_file_length == max_reiserfs_offset (inode) ) {
  918. /* item has to be deleted */
  919. *cut_size = -(IH_SIZE + ih_item_len(le_ih));
  920. return M_DELETE;
  921.     }
  923.     // new file gets truncated
  924.     if (get_inode_item_key_version (inode) == KEY_FORMAT_3_6) {
  925. // 
  926. round_len = ROUND_UP (new_file_length); 
  927. /* this was n_new_file_length < le_ih ... */
  928. if ( round_len < le_ih_k_offset (le_ih) )  {
  929.     *cut_size = -(IH_SIZE + ih_item_len(le_ih));
  930.     return M_DELETE; /* Delete this item. */
  931. }
  932. /* Calculate first position and size for cutting from item. */
  933. pos_in_item (path) = round_len - (le_ih_k_offset (le_ih) - 1);
  934. *cut_size = -(ih_item_len(le_ih) - pos_in_item(path));
  936. return M_CUT; /* Cut from this item. */
  937.     }
  940.     // old file: items may have any length
  942.     if ( new_file_length < le_ih_k_offset (le_ih) )  {
  943. *cut_size = -(IH_SIZE + ih_item_len(le_ih));
  944. return M_DELETE; /* Delete this item. */
  945.     }
  946.     /* Calculate first position and size for cutting from item. */
  947.     *cut_size = -(ih_item_len(le_ih) -
  948.       (pos_in_item (path) = new_file_length + 1 - le_ih_k_offset (le_ih)));
  949.     return M_CUT; /* Cut from this item. */
  950. }
  953. static inline int prepare_for_direntry_item (struct path * path,
  954.      struct item_head * le_ih,
  955.      struct inode * inode,
  956.      loff_t new_file_length,
  957.      int * cut_size)
  958. {
  959.     if (le_ih_k_offset (le_ih) == DOT_OFFSET && 
  960. new_file_length == max_reiserfs_offset (inode)) {
  961. RFALSE( ih_entry_count (le_ih) != 2,
  962.         "PAP-5220: incorrect empty directory item (%h)", le_ih);
  963. *cut_size = -(IH_SIZE + ih_item_len(le_ih));
  964. return M_DELETE; /* Delete the directory item containing "." and ".." entry. */
  965.     }
  966.     
  967.     if ( ih_entry_count (le_ih) == 1 )  {
  968. /* Delete the directory item such as there is one record only
  969.    in this item*/
  970. *cut_size = -(IH_SIZE + ih_item_len(le_ih));
  971. return M_DELETE;
  972.     }
  973.     
  974.     /* Cut one record from the directory item. */
  975.     *cut_size = -(DEH_SIZE + entry_length (get_last_bh (path), le_ih, pos_in_item (path)));
  976.     return M_CUT; 
  977. }
  980. /*  If the path points to a directory or direct item, calculate mode and the size cut, for balance.
  981.     If the path points to an indirect item, remove some number of its unformatted nodes.
  982.     In case of file truncate calculate whether this item must be deleted/truncated or last
  983.     unformatted node of this item will be converted to a direct item.
  984.     This function returns a determination of what balance mode the calling function should employ. */
  985. static char  prepare_for_delete_or_cut(
  986.        struct reiserfs_transaction_handle *th, 
  987.        struct inode * inode,
  988.        struct path         * p_s_path,
  989.        const struct cpu_key      * p_s_item_key,
  990.        int                 * p_n_removed,      /* Number of unformatted nodes which were removed
  991.   from end of the file. */
  992.        int                 * p_n_cut_size,
  993.        unsigned long long    n_new_file_length /* MAX_KEY_OFFSET in case of delete. */
  994.     ) {
  995.     struct super_block  * p_s_sb = inode->i_sb;
  996.     struct item_head    * p_le_ih = PATH_PITEM_HEAD(p_s_path);
  997.     struct buffer_head  * p_s_bh = PATH_PLAST_BUFFER(p_s_path);
  999.     /* Stat_data item. */
  1000.     if ( is_statdata_le_ih (p_le_ih) ) {
  1002. RFALSE( n_new_file_length != max_reiserfs_offset (inode),
  1003. "PAP-5210: mode must be M_DELETE");
  1005. *p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
  1006. return M_DELETE;
  1007.     }
  1010.     /* Directory item. */
  1011.     if ( is_direntry_le_ih (p_le_ih) )
  1012. return prepare_for_direntry_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
  1014.     /* Direct item. */
  1015.     if ( is_direct_le_ih (p_le_ih) )
  1016. return prepare_for_direct_item (p_s_path, p_le_ih, inode, n_new_file_length, p_n_cut_size);
  1019.     /* Case of an indirect item. */
  1020.     {
  1021. int                   n_unfm_number,    /* Number of the item unformatted nodes. */
  1022.     n_counter,
  1023.     n_blk_size;
  1024. __u32               * p_n_unfm_pointer; /* Pointer to the unformatted node number. */
  1025. __u32 tmp;
  1026. struct item_head      s_ih;           /* Item header. */
  1027. char                  c_mode;           /* Returned mode of the balance. */
  1028. int need_research;
  1031. n_blk_size = p_s_sb->s_blocksize;
  1033. /* Search for the needed object indirect item until there are no unformatted nodes to be removed. */
  1034. do  {
  1035.     need_research = 0;
  1036.             p_s_bh = PATH_PLAST_BUFFER(p_s_path);
  1037.     /* Copy indirect item header to a temp variable. */
  1038.     copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
  1039.     /* Calculate number of unformatted nodes in this item. */
  1040.     n_unfm_number = I_UNFM_NUM(&s_ih);
  1042.     RFALSE( ! is_indirect_le_ih(&s_ih) || ! n_unfm_number ||
  1043.     pos_in_item (p_s_path) + 1 !=  n_unfm_number,
  1044.     "PAP-5240: illegal item %h "
  1045.     "n_unfm_number = %d *p_n_pos_in_item = %d", 
  1046.     &s_ih, n_unfm_number, pos_in_item (p_s_path));
  1048.     /* Calculate balance mode and position in the item to remove unformatted nodes. */
  1049.     if ( n_new_file_length == max_reiserfs_offset (inode) ) {/* Case of delete. */
  1050. pos_in_item (p_s_path) = 0;
  1051. *p_n_cut_size = -(IH_SIZE + ih_item_len(&s_ih));
  1052. c_mode = M_DELETE;
  1053.     }
  1054.     else  { /* Case of truncate. */
  1055. if ( n_new_file_length < le_ih_k_offset (&s_ih) )  {
  1056.     pos_in_item (p_s_path) = 0;
  1057.     *p_n_cut_size = -(IH_SIZE + ih_item_len(&s_ih));
  1058.     c_mode = M_DELETE; /* Delete this item. */
  1059. }
  1060. else  {
  1061.     /* indirect item must be truncated starting from *p_n_pos_in_item-th position */
  1062.     pos_in_item (p_s_path) = (n_new_file_length + n_blk_size - le_ih_k_offset (&s_ih) ) >> p_s_sb->s_blocksize_bits;
  1064.     RFALSE( pos_in_item (p_s_path) > n_unfm_number,
  1065.     "PAP-5250: illegal position in the item");
  1067.     /* Either convert last unformatted node of indirect item to direct item or increase
  1068.        its free space.  */
  1069.     if ( pos_in_item (p_s_path) == n_unfm_number )  {
  1070. *p_n_cut_size = 0; /* Nothing to cut. */
  1071. return M_CONVERT; /* Maybe convert last unformatted node to the direct item. */
  1072.     }
  1073.     /* Calculate size to cut. */
  1074.     *p_n_cut_size = -(ih_item_len(&s_ih) - pos_in_item(p_s_path) * UNFM_P_SIZE);
  1076.     c_mode = M_CUT;     /* Cut from this indirect item. */
  1077. }
  1078.     }
  1080.     RFALSE( n_unfm_number <= pos_in_item (p_s_path),
  1081.     "PAP-5260: illegal position in the indirect item");
  1083.     /* pointers to be cut */
  1084.     n_unfm_number -= pos_in_item (p_s_path);
  1085.     /* Set pointer to the last unformatted node pointer that is to be cut. */
  1086.     p_n_unfm_pointer = (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1 - *p_n_removed;
  1089.     /* We go through the unformatted nodes pointers of the indirect
  1090.        item and look for the unformatted nodes in the cache. If we
  1091.        found some of them we free it, zero corresponding indirect item
  1092.        entry and log buffer containing that indirect item. For this we
  1093.        need to prepare last path element for logging. If some
  1094.        unformatted node has b_count > 1 we must not free this
  1095.        unformatted node since it is in use. */
  1096.     reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
  1097.     // note: path could be changed, first line in for loop takes care
  1098.     // of it
  1100.     for (n_counter = *p_n_removed;
  1101.  n_counter < n_unfm_number; n_counter++, p_n_unfm_pointer-- ) {
  1103. if (item_moved (&s_ih, p_s_path)) {
  1104.     need_research = 1 ;
  1105.     break;
  1106. }
  1107. RFALSE( p_n_unfm_pointer < (__u32 *)B_I_PITEM(p_s_bh, &s_ih) ||
  1108. p_n_unfm_pointer > (__u32 *)B_I_PITEM(p_s_bh, &s_ih) + I_UNFM_NUM(&s_ih) - 1,
  1109. "vs-5265: pointer out of range");
  1111. /* Hole, nothing to remove. */
  1112. if ( ! get_block_num(p_n_unfm_pointer,0) )  { 
  1113. (*p_n_removed)++;
  1114. continue;
  1115. }
  1117. (*p_n_removed)++;
  1119. tmp = get_block_num(p_n_unfm_pointer,0);
  1120. put_block_num(p_n_unfm_pointer, 0, 0);
  1121. journal_mark_dirty (th, p_s_sb, p_s_bh);
  1122. inode->i_blocks -= p_s_sb->s_blocksize / 512;
  1123. reiserfs_free_block(th, tmp);
  1124. if ( item_moved (&s_ih, p_s_path) )  {
  1125. need_research = 1;
  1126. break ;
  1127. }
  1128.     }
  1130.     /* a trick.  If the buffer has been logged, this
  1131.     ** will do nothing.  If we've broken the loop without
  1132.     ** logging it, it will restore the buffer
  1133.     **
  1134.     */
  1135.     reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
  1137.     /* This loop can be optimized. */
  1138. } while ( (*p_n_removed < n_unfm_number || need_research) &&
  1139.   search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND );
  1141. RFALSE( *p_n_removed < n_unfm_number, 
  1142. "PAP-5310: indirect item is not found");
  1143. RFALSE( item_moved (&s_ih, p_s_path), 
  1144. "after while, comp failed, retry") ;
  1146. if (c_mode == M_CUT)
  1147.     pos_in_item (p_s_path) *= UNFM_P_SIZE;
  1148. return c_mode;
  1149.     }
  1150. }
  1153. /* Calculate bytes number which will be deleted or cutted in the balance. */
  1154. int calc_deleted_bytes_number(
  1155.     struct  tree_balance  * p_s_tb,
  1156.     char                    c_mode
  1157.     ) {
  1158.     int                     n_del_size;
  1159.     struct  item_head     * p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);
  1161.     if ( is_statdata_le_ih (p_le_ih) )
  1162. return 0;
  1164.     if ( is_direntry_le_ih (p_le_ih) ) {
  1165. // return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
  1166. // we can't use EMPTY_DIR_SIZE, as old format dirs have a different
  1167. // empty size.  ick. FIXME, is this right?
  1168. //
  1169. return ih_item_len(p_le_ih);
  1170.     }
  1171.     n_del_size = ( c_mode == M_DELETE ) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
  1173.     if ( is_indirect_le_ih (p_le_ih) )
  1174. n_del_size = (n_del_size/UNFM_P_SIZE)*
  1175.   (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size);// - get_ih_free_space (p_le_ih);
  1176.     return n_del_size;
  1177. }
  1179. static void init_tb_struct(
  1180.     struct reiserfs_transaction_handle *th,
  1181.     struct tree_balance * p_s_tb,
  1182.     struct super_block  * p_s_sb,
  1183.     struct path         * p_s_path,
  1184.     int                   n_size
  1185.     ) {
  1186.     memset (p_s_tb,'',sizeof(struct tree_balance));
  1187.     p_s_tb->transaction_handle = th ;
  1188.     p_s_tb->tb_sb = p_s_sb;
  1189.     p_s_tb->tb_path = p_s_path;
  1190.     PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
  1191.     PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
  1192.     p_s_tb->insert_size[0] = n_size;
  1193. }
  1197. void padd_item (char * item, int total_length, int length)
  1198. {
  1199.     int i;
  1201.     for (i = total_length; i > length; )
  1202. item [--i] = 0;
  1203. }
  1206. /* Delete object item. */
  1207. int reiserfs_delete_item (struct reiserfs_transaction_handle *th, 
  1208.   struct path * p_s_path, /* Path to the deleted item. */
  1209.   const struct cpu_key * p_s_item_key, /* Key to search for the deleted item.  */
  1210.   struct inode * p_s_inode,/* inode is here just to update i_blocks */
  1211.   struct buffer_head  * p_s_un_bh)    /* NULL or unformatted node pointer.    */
  1212. {
  1213.     struct super_block * p_s_sb = p_s_inode->i_sb;
  1214.     struct tree_balance   s_del_balance;
  1215.     struct item_head      s_ih;
  1216.     int                   n_ret_value,
  1217. n_del_size,
  1218. n_removed;
  1220. #ifdef CONFIG_REISERFS_CHECK
  1221.     char                  c_mode;
  1222.     int n_iter = 0;
  1223. #endif
  1225.     init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path, 0/*size is unknown*/);
  1227.     while ( 1 ) {
  1228. n_removed = 0;
  1230. #ifdef CONFIG_REISERFS_CHECK
  1231. n_iter++;
  1232. c_mode =
  1233. #endif
  1234.     prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed, &n_del_size, max_reiserfs_offset (p_s_inode));
  1236. RFALSE( c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");
  1238. copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
  1239. s_del_balance.insert_size[0] = n_del_size;
  1241. n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, 0);
  1242. if ( n_ret_value != REPEAT_SEARCH )
  1243.     break;
  1245. // file system changed, repeat search
  1246. n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
  1247. if (n_ret_value == IO_ERROR)
  1248.     break;
  1249. if (n_ret_value == FILE_NOT_FOUND) {
  1250.     reiserfs_warning ("vs-5340: reiserfs_delete_item: "
  1251.       "no items of the file %K foundn", p_s_item_key);
  1252.     break;
  1253. }
  1254.     } /* while (1) */
  1256.     if ( n_ret_value != CARRY_ON ) {
  1257. unfix_nodes(&s_del_balance);
  1258. return 0;
  1259.     }
  1261.     // reiserfs_delete_item returns item length when success
  1262.     n_ret_value = calc_deleted_bytes_number(&s_del_balance, M_DELETE);
  1264.     if ( p_s_un_bh )  {
  1265. int off;
  1266.         char *data ;
  1268. /* We are in direct2indirect conversion, so move tail contents
  1269.            to the unformatted node */
  1270. /* note, we do the copy before preparing the buffer because we
  1271. ** don't care about the contents of the unformatted node yet.
  1272. ** the only thing we really care about is the direct item's data
  1273. ** is in the unformatted node.
  1274. **
  1275. ** Otherwise, we would have to call reiserfs_prepare_for_journal on
  1276. ** the unformatted node, which might schedule, meaning we'd have to
  1277. ** loop all the way back up to the start of the while loop.
  1278. **
  1279. ** The unformatted node must be dirtied later on.  We can't be
  1280. ** sure here if the entire tail has been deleted yet.
  1281.         **
  1282.         ** p_s_un_bh is from the page cache (all unformatted nodes are
  1283.         ** from the page cache) and might be a highmem page.  So, we
  1284.         ** can't use p_s_un_bh->b_data.  But, the page has already been
  1285.         ** kmapped, so we can use page_address()
  1286. ** -clm
  1287. */
  1289.         data = page_address(p_s_un_bh->b_page) ;
  1290. off = ((le_ih_k_offset (&s_ih) - 1) & (PAGE_CACHE_SIZE - 1));
  1291. memcpy(data + off,
  1292.        B_I_PITEM(PATH_PLAST_BUFFER(p_s_path), &s_ih), n_ret_value);
  1293.     }
  1295.     /* Perform balancing after all resources have been collected at once. */ 
  1296.     do_balance(&s_del_balance, NULL, NULL, M_DELETE);
  1298.     /* Return deleted body length */
  1299.     return n_ret_value;
  1300. }
  1303. /* Summary Of Mechanisms For Handling Collisions Between Processes:
  1305.  deletion of the body of the object is performed by iput(), with the
  1306.  result that if multiple processes are operating on a file, the
  1307.  deletion of the body of the file is deferred until the last process
  1308.  that has an open inode performs its iput().
  1310.  writes and truncates are protected from collisions by use of
  1311.  semaphores.
  1313.  creates, linking, and mknod are protected from collisions with other
  1314.  processes by making the reiserfs_add_entry() the last step in the
  1315.  creation, and then rolling back all changes if there was a collision.
  1316.  - Hans
  1317. */
  1320. /* this deletes item which never gets split */
  1321. void reiserfs_delete_solid_item (struct reiserfs_transaction_handle *th,
  1322.  struct key * key)
  1323. {
  1324.     struct tree_balance tb;
  1325.     INITIALIZE_PATH (path);
  1326.     int item_len;
  1327.     int tb_init = 0 ;
  1328.     struct cpu_key cpu_key;
  1329.     int retval;
  1330.     
  1331.     le_key2cpu_key (&cpu_key, key);
  1332.     
  1333.     while (1) {
  1334. retval = search_item (th->t_super, &cpu_key, &path);
  1335. if (retval == IO_ERROR) {
  1336.     reiserfs_warning ("vs-5350: reiserfs_delete_solid_item: "
  1337.       "i/o failure occurred trying to delete %Kn", &cpu_key);
  1338.     break;
  1339. }
  1340. if (retval != ITEM_FOUND) {
  1341.     pathrelse (&path);
  1342.     reiserfs_warning ("vs-5355: reiserfs_delete_solid_item: %k not found",
  1343.       key);
  1344.     break;
  1345. }
  1346. if (!tb_init) {
  1347.     tb_init = 1 ;
  1348.     item_len = ih_item_len( PATH_PITEM_HEAD(&path) );
  1349.     init_tb_struct (th, &tb, th->t_super, &path, - (IH_SIZE + item_len));
  1350. }
  1352. retval = fix_nodes (M_DELETE, &tb, NULL, 0);
  1353. if (retval == REPEAT_SEARCH)
  1354.     continue;
  1356. if (retval == CARRY_ON) {
  1357.     do_balance (&tb, 0, 0, M_DELETE);
  1358.     break;
  1359. }
  1361. // IO_ERROR, NO_DISK_SPACE, etc
  1362. reiserfs_warning ("vs-5360: reiserfs_delete_solid_item: "
  1363.   "could not delete %K due to fix_nodes failuren", &cpu_key);
  1364. unfix_nodes (&tb);
  1365. break;
  1366.     }
  1368.     reiserfs_check_path(&path) ;
  1369. }
  1372. void reiserfs_delete_object (struct reiserfs_transaction_handle *th, struct inode * inode)
  1373. {
  1374.     inode->i_size = 0;
  1376.     /* for directory this deletes item containing "." and ".." */
  1377.     reiserfs_do_truncate (th, inode, NULL, 0/*no timestamp updates*/);
  1378.     
  1379. #if defined( USE_INODE_GENERATION_COUNTER )
  1380.     if( !old_format_only ( th -> t_super ) )
  1381.       {
  1382.        __u32 *inode_generation;
  1383.        
  1384.        inode_generation = 
  1385.          &th -> t_super -> u.reiserfs_sb.s_rs -> s_inode_generation;
  1386.        *inode_generation = cpu_to_le32( le32_to_cpu( *inode_generation ) + 1 );
  1387.       }
  1388. /* USE_INODE_GENERATION_COUNTER */
  1389. #endif
  1390.     reiserfs_delete_solid_item (th, INODE_PKEY (inode));
  1391. }
  1394. static int maybe_indirect_to_direct (struct reiserfs_transaction_handle *th, 
  1395.       struct inode * p_s_inode,
  1396.       struct page *page, 
  1397.       struct path         * p_s_path,
  1398.       const struct cpu_key      * p_s_item_key,
  1399.       loff_t         n_new_file_size,
  1400.       char                * p_c_mode
  1401.       ) {
  1402.     struct super_block * p_s_sb = p_s_inode->i_sb;
  1403.     int n_block_size = p_s_sb->s_blocksize;
  1404.     int cut_bytes;
  1406.     if (n_new_file_size != p_s_inode->i_size)
  1407. BUG ();
  1409.     /* the page being sent in could be NULL if there was an i/o error
  1410.     ** reading in the last block.  The user will hit problems trying to
  1411.     ** read the file, but for now we just skip the indirect2direct
  1412.     */
  1413.     if (atomic_read(&p_s_inode->i_count) > 1 || 
  1414.         !tail_has_to_be_packed (p_s_inode) || 
  1415.         !page || (p_s_inode->u.reiserfs_i.i_flags & i_nopack_mask)) {
  1416. // leave tail in an unformatted node
  1417. *p_c_mode = M_SKIP_BALANCING;
  1418. cut_bytes = n_block_size - (n_new_file_size & (n_block_size - 1));
  1419. pathrelse(p_s_path);
  1420. return cut_bytes;
  1421.     }
  1422.     /* Permorm the conversion to a direct_item. */
  1423.     /*return indirect_to_direct (p_s_inode, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);*/
  1424.     return indirect2direct (th, p_s_inode, page, p_s_path, p_s_item_key, n_new_file_size, p_c_mode);
  1425. }
  1428. /* we did indirect_to_direct conversion. And we have inserted direct
  1429.    item successesfully, but there were no disk space to cut unfm
  1430.    pointer being converted. Therefore we have to delete inserted
  1431.    direct item(s) */
  1432. static void indirect_to_direct_roll_back (struct reiserfs_transaction_handle *th, struct inode * inode, struct path * path)
  1433. {
  1434.     struct cpu_key tail_key;
  1435.     int tail_len;
  1436.     int removed;
  1438.     make_cpu_key (&tail_key, inode, inode->i_size + 1, TYPE_DIRECT, 4);// !!!!
  1439.     tail_key.key_length = 4;
  1441.     tail_len = (cpu_key_k_offset (&tail_key) & (inode->i_sb->s_blocksize - 1)) - 1;
  1442.     while (tail_len) {
  1443. /* look for the last byte of the tail */
  1444. if (search_for_position_by_key (inode->i_sb, &tail_key, path) == POSITION_NOT_FOUND)
  1445.     reiserfs_panic (inode->i_sb, "vs-5615: indirect_to_direct_roll_back: found invalid item");
  1446. RFALSE( path->pos_in_item != ih_item_len(PATH_PITEM_HEAD (path)) - 1,
  1447.         "vs-5616: appended bytes found");
  1448. PATH_LAST_POSITION (path) --;
  1450. removed = reiserfs_delete_item (th, path, &tail_key, inode, 0/*unbh not needed*/);
  1451. RFALSE( removed <= 0 || removed > tail_len,
  1452.         "vs-5617: there was tail %d bytes, removed item length %d bytes",
  1453.                 tail_len, removed);
  1454. tail_len -= removed;
  1455. set_cpu_key_k_offset (&tail_key, cpu_key_k_offset (&tail_key) - removed);
  1456.     }
  1457.     printk ("indirect_to_direct_roll_back: indirect_to_direct conversion has been rolled back due to lack of disk spacen");
  1458.     //mark_file_without_tail (inode);
  1459.     mark_inode_dirty (inode);
  1460. }
  1463. /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */
  1464. int reiserfs_cut_from_item (struct reiserfs_transaction_handle *th, 
  1465.     struct path * p_s_path,
  1466.     struct cpu_key * p_s_item_key,
  1467.     struct inode * p_s_inode,
  1468.     struct page *page, 
  1469.     loff_t n_new_file_size)
  1470. {
  1471.     struct super_block * p_s_sb = p_s_inode->i_sb;
  1472.     /* Every function which is going to call do_balance must first
  1473.        create a tree_balance structure.  Then it must fill up this
  1474.        structure by using the init_tb_struct and fix_nodes functions.
  1475.        After that we can make tree balancing. */
  1476.     struct tree_balance s_cut_balance;
  1477.     int n_cut_size = 0,        /* Amount to be cut. */
  1478. n_ret_value = CARRY_ON,
  1479. n_removed = 0,     /* Number of the removed unformatted nodes. */
  1480. n_is_inode_locked = 0;
  1481.     char                c_mode;            /* Mode of the balance. */
  1482.     int retval2 = -1;
  1483.     
  1484.     
  1485.     init_tb_struct(th, &s_cut_balance, p_s_inode->i_sb, p_s_path, n_cut_size);
  1488.     /* Repeat this loop until we either cut the item without needing
  1489.        to balance, or we fix_nodes without schedule occuring */
  1490.     while ( 1 ) {
  1491. /* Determine the balance mode, position of the first byte to
  1492.    be cut, and size to be cut.  In case of the indirect item
  1493.    free unformatted nodes which are pointed to by the cut
  1494.    pointers. */
  1495.       
  1496. c_mode = prepare_for_delete_or_cut(th, p_s_inode, p_s_path, p_s_item_key, &n_removed, 
  1497.    &n_cut_size, n_new_file_size);
  1498. if ( c_mode == M_CONVERT )  {
  1499.     /* convert last unformatted node to direct item or leave
  1500.                tail in the unformatted node */
  1501.     RFALSE( n_ret_value != CARRY_ON, "PAP-5570: can not convert twice");
  1503.     n_ret_value = maybe_indirect_to_direct (th, p_s_inode, page, p_s_path, p_s_item_key,
  1504.     n_new_file_size, &c_mode);
  1505.     if ( c_mode == M_SKIP_BALANCING )
  1506. /* tail has been left in the unformatted node */
  1507. return n_ret_value;
  1509.     n_is_inode_locked = 1;
  1510.   
  1511.     /* removing of last unformatted node will change value we
  1512.                have to return to truncate. Save it */
  1513.     retval2 = n_ret_value;
  1514.     /*retval2 = p_s_sb->s_blocksize - (n_new_file_size & (p_s_sb->s_blocksize - 1));*/
  1515.   
  1516.     /* So, we have performed the first part of the conversion:
  1517.        inserting the new direct item.  Now we are removing the
  1518.        last unformatted node pointer. Set key to search for
  1519.        it. */
  1520.            set_cpu_key_k_type (p_s_item_key, TYPE_INDIRECT);
  1521.     p_s_item_key->key_length = 4;
  1522.     n_new_file_size -= (n_new_file_size & (p_s_sb->s_blocksize - 1));
  1523.     set_cpu_key_k_offset (p_s_item_key, n_new_file_size + 1);
  1524.     if ( search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_NOT_FOUND ){
  1525. print_block (PATH_PLAST_BUFFER (p_s_path), 3, PATH_LAST_POSITION (p_s_path) - 1, PATH_LAST_POSITION (p_s_path) + 1);
  1526. reiserfs_panic(p_s_sb, "PAP-5580: reiserfs_cut_from_item: item to convert does not exist (%k)", p_s_item_key);
  1527.     }
  1528.     continue;
  1529. }
  1530. if (n_cut_size == 0) {
  1531.     pathrelse (p_s_path);
  1532.     return 0;
  1533. }
  1535. s_cut_balance.insert_size[0] = n_cut_size;
  1537. n_ret_value = fix_nodes(c_mode, &s_cut_balance, NULL, 0);
  1538.        if ( n_ret_value != REPEAT_SEARCH )
  1539.     break;
  1541. n_ret_value = search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path);
  1542. if (n_ret_value == POSITION_FOUND)
  1543.     continue;
  1545. reiserfs_warning ("PAP-5610: reiserfs_cut_from_item: item %K not foundn", p_s_item_key);
  1546. unfix_nodes (&s_cut_balance);
  1547. return (n_ret_value == IO_ERROR) ? -EIO : -ENOENT;
  1548.     } /* while */
  1549.   
  1550.     // check fix_nodes results (IO_ERROR or NO_DISK_SPACE)
  1551.     if ( n_ret_value != CARRY_ON ) {
  1552. if ( n_is_inode_locked ) {
  1553.     // FIXME: this seems to be not needed: we are always able
  1554.     // to cut item
  1555.     indirect_to_direct_roll_back (th, p_s_inode, p_s_path);
  1556. }
  1557. if (n_ret_value == NO_DISK_SPACE)
  1558.     reiserfs_warning ("NO_DISK_SPACE");
  1559. unfix_nodes (&s_cut_balance);
  1560. return -EIO;
  1561.     }
  1563.     /* go ahead and perform balancing */
  1564.     
  1565.     RFALSE( c_mode == M_PASTE || c_mode == M_INSERT, "illegal mode");
  1567.     /* Calculate number of bytes that need to be cut from the item. */
  1568.     if (retval2 == -1)
  1569. n_ret_value = calc_deleted_bytes_number(&s_cut_balance, c_mode);
  1570.     else
  1571. n_ret_value = retval2;
  1572.     
  1573.     if ( c_mode == M_DELETE ) {
  1574. struct item_head * p_le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
  1576. if ( is_direct_le_ih (p_le_ih) && (le_ih_k_offset (p_le_ih) & (p_s_sb->s_blocksize - 1)) == 1 ) {
  1577.     /* we delete first part of tail which was stored in direct
  1578.                item(s) */
  1579.     // FIXME: this is to keep 3.5 happy
  1580.     p_s_inode->u.reiserfs_i.i_first_direct_byte = U32_MAX;
  1581.     p_s_inode->i_blocks -= p_s_sb->s_blocksize / 512;
  1582. }
  1583.     }
  1585. #ifdef CONFIG_REISERFS_CHECK
  1586.     if (n_is_inode_locked) {
  1587. struct item_head * le_ih = PATH_PITEM_HEAD (s_cut_balance.tb_path);
  1588. /* we are going to complete indirect2direct conversion. Make
  1589.            sure, that we exactly remove last unformatted node pointer
  1590.            of the item */
  1591. if (!is_indirect_le_ih (le_ih))
  1592.     reiserfs_panic (p_s_sb, "vs-5652: reiserfs_cut_from_item: "
  1593.     "item must be indirect %h", le_ih);
  1595. if (c_mode == M_DELETE && ih_item_len(le_ih) != UNFM_P_SIZE)
  1596.     reiserfs_panic (p_s_sb, "vs-5653: reiserfs_cut_from_item: "
  1597.     "completing indirect2direct conversion indirect item %h "
  1598.     "being deleted must be of 4 byte long", le_ih);
  1600. if (c_mode == M_CUT && s_cut_balance.insert_size[0] != -UNFM_P_SIZE) {
  1601.     reiserfs_panic (p_s_sb, "vs-5654: reiserfs_cut_from_item: "
  1602.     "can not complete indirect2direct conversion of %h (CUT, insert_size==%d)",
  1603.     le_ih, s_cut_balance.insert_size[0]);
  1604. }
  1605. /* it would be useful to make sure, that right neighboring
  1606.            item is direct item of this file */
  1607.     }
  1608. #endif
  1609.     
  1610.     do_balance(&s_cut_balance, NULL, NULL, c_mode);
  1611.     if ( n_is_inode_locked ) {
  1612. /* we've done an indirect->direct conversion.  when the data block 
  1613. ** was freed, it was removed from the list of blocks that must 
  1614. ** be flushed before the transaction commits, so we don't need to 
  1615. ** deal with it here.
  1616. */
  1617. p_s_inode->u.reiserfs_i.i_flags &= ~i_pack_on_close_mask;
  1618.     }
  1619.     return n_ret_value;
  1620. }
  1623. static void truncate_directory (struct reiserfs_transaction_handle *th, struct inode * inode)
  1624. {
  1625.     if (inode->i_nlink)
  1626. reiserfs_warning ("vs-5655: truncate_directory: link count != 0n");
  1628.     set_le_key_k_offset (KEY_FORMAT_3_5, INODE_PKEY (inode), DOT_OFFSET);
  1629.     set_le_key_k_type (KEY_FORMAT_3_5, INODE_PKEY (inode), TYPE_DIRENTRY);
  1630.     reiserfs_delete_solid_item (th, INODE_PKEY (inode));
  1632.     set_le_key_k_offset (KEY_FORMAT_3_5, INODE_PKEY (inode), SD_OFFSET);
  1633.     set_le_key_k_type (KEY_FORMAT_3_5, INODE_PKEY (inode), TYPE_STAT_DATA);    
  1634. }
  1639. /* Truncate file to the new size. Note, this must be called with a transaction
  1640.    already started */
  1641. void reiserfs_do_truncate (struct reiserfs_transaction_handle *th, 
  1642.    struct  inode * p_s_inode, /* ->i_size contains new
  1643.                                                          size */
  1644.    struct page *page, /* up to date for last block */
  1645.    int update_timestamps  /* when it is called by
  1646.      file_release to convert
  1647.      the tail - no timestamps
  1648.      should be updated */
  1649.     ) {
  1650.     INITIALIZE_PATH (s_search_path);       /* Path to the current object item. */
  1651.     struct item_head    * p_le_ih;         /* Pointer to an item header. */
  1652.     struct cpu_key      s_item_key;     /* Key to search for a previous file item. */
  1653.     loff_t         n_file_size,    /* Old file size. */
  1654. n_new_file_size;/* New file size. */
  1655.     int                   n_deleted;      /* Number of deleted or truncated bytes. */
  1656.     int retval;
  1658.     if ( ! (S_ISREG(p_s_inode->i_mode) || S_ISDIR(p_s_inode->i_mode) || S_ISLNK(p_s_inode->i_mode)) )
  1659. return;
  1661.     if (S_ISDIR(p_s_inode->i_mode)) {
  1662. // deletion of directory - no need to update timestamps
  1663. truncate_directory (th, p_s_inode);
  1664. return;
  1665.     }
  1667.     /* Get new file size. */
  1668.     n_new_file_size = p_s_inode->i_size;
  1670.     // FIXME: note, that key type is unimportant here
  1671.     make_cpu_key (&s_item_key, p_s_inode, max_reiserfs_offset (p_s_inode), TYPE_DIRECT, 3);
  1673.     retval = search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path);
  1674.     if (retval == IO_ERROR) {
  1675. reiserfs_warning ("vs-5657: reiserfs_do_truncate: "
  1676.   "i/o failure occurred trying to truncate %Kn", &s_item_key);
  1677. return;
  1678.     }
  1679.     if (retval == POSITION_FOUND || retval == FILE_NOT_FOUND) {
  1680. pathrelse (&s_search_path);
  1681. reiserfs_warning ("PAP-5660: reiserfs_do_truncate: "
  1682.   "wrong result %d of search for %Kn", retval, &s_item_key);
  1683. return;
  1684.     }
  1686.     s_search_path.pos_in_item --;
  1688.     /* Get real file size (total length of all file items) */
  1689.     p_le_ih = PATH_PITEM_HEAD(&s_search_path);
  1690.     if ( is_statdata_le_ih (p_le_ih) )
  1691. n_file_size = 0;
  1692.     else {
  1693. loff_t offset = le_ih_k_offset (p_le_ih);
  1694. int bytes = op_bytes_number (p_le_ih,p_s_inode->i_sb->s_blocksize);
  1696. /* this may mismatch with real file size: if last direct item
  1697.            had no padding zeros and last unformatted node had no free
  1698.            space, this file would have this file size */
  1699. n_file_size = offset + bytes - 1;
  1700.     }
  1702.     if ( n_file_size == 0 || n_file_size < n_new_file_size ) {
  1703. goto update_and_out ;
  1704.     }
  1706.     /* Update key to search for the last file item. */
  1707.     set_cpu_key_k_offset (&s_item_key, n_file_size);
  1709.     do  {
  1710. /* Cut or delete file item. */
  1711. n_deleted = reiserfs_cut_from_item(th, &s_search_path, &s_item_key, p_s_inode,  page, n_new_file_size);
  1712. if (n_deleted < 0) {
  1713.     reiserfs_warning ("vs-5665: reiserfs_truncate_file: cut_from_item failed");
  1714.     reiserfs_check_path(&s_search_path) ;
  1715.     return;
  1716. }
  1718. RFALSE( n_deleted > n_file_size,
  1719. "PAP-5670: reiserfs_truncate_file returns too big number: deleted %d, file_size %lu, item_key %k",
  1720. n_deleted, n_file_size, &s_item_key);
  1722. /* Change key to search the last file item. */
  1723. n_file_size -= n_deleted;
  1725. set_cpu_key_k_offset (&s_item_key, n_file_size);
  1727. /* While there are bytes to truncate and previous file item is presented in the tree. */
  1729. /*
  1730. ** This loop could take a really long time, and could log 
  1731. ** many more blocks than a transaction can hold.  So, we do a polite
  1732. ** journal end here, and if the transaction needs ending, we make
  1733. ** sure the file is consistent before ending the current trans
  1734. ** and starting a new one
  1735. */
  1736.         if (journal_transaction_should_end(th, th->t_blocks_allocated)) {
  1737.   int orig_len_alloc = th->t_blocks_allocated ;
  1738.   decrement_counters_in_path(&s_search_path) ;
  1740.   if (update_timestamps) {
  1741.       p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
  1742.   } 
  1743.   reiserfs_update_sd(th, p_s_inode) ;
  1745.   journal_end(th, p_s_inode->i_sb, orig_len_alloc) ;
  1746.   journal_begin(th, p_s_inode->i_sb, orig_len_alloc) ;
  1747.   reiserfs_update_inode_transaction(p_s_inode) ;
  1748. }
  1749.     } while ( n_file_size > ROUND_UP (n_new_file_size) &&
  1750.       search_for_position_by_key(p_s_inode->i_sb, &s_item_key, &s_search_path) == POSITION_FOUND )  ;
  1752.     RFALSE( n_file_size > ROUND_UP (n_new_file_size),
  1753.     "PAP-5680: truncate did not finish: new_file_size %Ld, current %Ld, oid %dn",
  1754.     n_new_file_size, n_file_size, s_item_key.on_disk_key.k_objectid);
  1756. update_and_out:
  1757.     if (update_timestamps) {
  1758. // this is truncate, not file closing
  1759. p_s_inode->i_mtime = p_s_inode->i_ctime = CURRENT_TIME;
  1760.     }
  1761.     reiserfs_update_sd (th, p_s_inode);
  1763.     pathrelse(&s_search_path) ;
  1764. }
  1767. #ifdef CONFIG_REISERFS_CHECK
  1768. // this makes sure, that we __append__, not overwrite or add holes
  1769. static void check_research_for_paste (struct path * path, 
  1770.       const struct cpu_key * p_s_key)
  1771. {
  1772.     struct item_head * found_ih = get_ih (path);
  1773.     
  1774.     if (is_direct_le_ih (found_ih)) {
  1775. if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) !=
  1776.     cpu_key_k_offset (p_s_key) ||
  1777.     op_bytes_number (found_ih, get_last_bh (path)->b_size) != pos_in_item (path))
  1778.     reiserfs_panic (0, "PAP-5720: check_research_for_paste: "
  1779.     "found direct item %h or position (%d) does not match to key %K",
  1780.     found_ih, pos_in_item (path), p_s_key);
  1781.     }
  1782.     if (is_indirect_le_ih (found_ih)) {
  1783. if (le_ih_k_offset (found_ih) + op_bytes_number (found_ih, get_last_bh (path)->b_size) != cpu_key_k_offset (p_s_key) || 
  1784.     I_UNFM_NUM (found_ih) != pos_in_item (path) ||
  1785.     get_ih_free_space (found_ih) != 0)
  1786.     reiserfs_panic (0, "PAP-5730: check_research_for_paste: "
  1787.     "found indirect item (%h) or position (%d) does not match to key (%K)",
  1788.     found_ih, pos_in_item (path), p_s_key);
  1789.     }
  1790. }
  1791. #endif /* config reiserfs check */
  1794. /* Paste bytes to the existing item. Returns bytes number pasted into the item. */
  1795. int reiserfs_paste_into_item (struct reiserfs_transaction_handle *th, 
  1796.       struct path         * p_s_search_path, /* Path to the pasted item.          */
  1797.       const struct cpu_key      * p_s_key,         /* Key to search for the needed item.*/
  1798.       const char          * p_c_body,        /* Pointer to the bytes to paste.    */
  1799.       int                   n_pasted_size)   /* Size of pasted bytes.             */
  1800. {
  1801.     struct tree_balance s_paste_balance;
  1802.     int                 retval;
  1804.     init_tb_struct(th, &s_paste_balance, th->t_super, p_s_search_path, n_pasted_size);
  1805.     
  1806.     while ( (retval = fix_nodes(M_PASTE, &s_paste_balance, NULL, p_c_body)) == REPEAT_SEARCH ) {
  1807. /* file system changed while we were in the fix_nodes */
  1808. retval = search_for_position_by_key (th->t_super, p_s_key, p_s_search_path);
  1809. if (retval == IO_ERROR) {
  1810.     retval = -EIO ;
  1811.     goto error_out ;
  1812. }
  1813. if (retval == POSITION_FOUND) {
  1814.     reiserfs_warning ("PAP-5710: reiserfs_paste_into_item: entry or pasted byte (%K) exists", p_s_key);
  1815.     retval = -EEXIST ;
  1816.     goto error_out ;
  1817. }
  1819. #ifdef CONFIG_REISERFS_CHECK
  1820. check_research_for_paste (p_s_search_path, p_s_key);
  1821. #endif
  1822.     }
  1824.     /* Perform balancing after all resources are collected by fix_nodes, and
  1825.        accessing them will not risk triggering schedule. */
  1826.     if ( retval == CARRY_ON ) {
  1827. do_balance(&s_paste_balance, NULL/*ih*/, p_c_body, M_PASTE);
  1828. return 0;
  1829.     }
  1830.     retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
  1831. error_out:
  1832.     /* this also releases the path */
  1833.     unfix_nodes(&s_paste_balance);
  1834.     return retval ;
  1835. }
  1838. /* Insert new item into the buffer at the path. */
  1839. int reiserfs_insert_item(struct reiserfs_transaction_handle *th, 
  1840.  struct path         *  p_s_path,         /* Path to the inserteded item.         */
  1841.  const struct cpu_key      * key,
  1842.  struct item_head    *  p_s_ih,           /* Pointer to the item header to insert.*/
  1843.  const char          *  p_c_body)         /* Pointer to the bytes to insert.      */
  1844. {
  1845.     struct tree_balance s_ins_balance;
  1846.     int                 retval;
  1848.     init_tb_struct(th, &s_ins_balance, th->t_super, p_s_path, IH_SIZE + ih_item_len(p_s_ih));
  1850.     /*
  1851.     if (p_c_body == 0)
  1852.       n_zeros_num = ih_item_len(p_s_ih);
  1853.     */
  1854.     //    le_key2cpu_key (&key, &(p_s_ih->ih_key));
  1856.     while ( (retval = fix_nodes(M_INSERT, &s_ins_balance, p_s_ih, p_c_body)) == REPEAT_SEARCH) {
  1857. /* file system changed while we were in the fix_nodes */
  1858. retval = search_item (th->t_super, key, p_s_path);
  1859. if (retval == IO_ERROR) {
  1860.     retval = -EIO;
  1861.     goto error_out ;
  1862. }
  1863. if (retval == ITEM_FOUND) {
  1864.     reiserfs_warning ("PAP-5760: reiserfs_insert_item: "
  1865.       "key %K already exists in the treen", key);
  1866.     retval = -EEXIST ;
  1867.     goto error_out; 
  1868. }
  1869.     }
  1871.     /* make balancing after all resources will be collected at a time */ 
  1872.     if ( retval == CARRY_ON ) {
  1873. do_balance (&s_ins_balance, p_s_ih, p_c_body, M_INSERT);
  1874. return 0;
  1875.     }
  1877.     retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
  1878. error_out:
  1879.     /* also releases the path */
  1880.     unfix_nodes(&s_ins_balance);
  1881.     return retval; 
  1882. }