fs/reiser4/estimate.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2    reiser4/README */
   3
   4 #include "debug.h"
   5 #include "dformat.h"
   6 #include "tree.h"
   7 #include "carry.h"
   8 #include "inode.h"
   9 #include "plugin/cluster.h"
  10 #include "plugin/item/ctail.h"
  11
  12 /* This returns how many nodes might get dirty and added nodes if @children
  13    nodes are dirtied
  14
  15    Amount of internals which will get dirty or get allocated we estimate as 5%
  16    of the childs + 1 balancing. 1 balancing is 2 neighbours, 2 new blocks and
  17    the current block on the leaf level, 2 neighbour nodes + the current (or 1
  18    neighbour and 1 new and the current) on twig level, 2 neighbour nodes on
  19    upper levels and 1 for a new root. So 5 for leaf level, 3 for twig level,
  20    2 on upper + 1 for root.
  21
  22    Do not calculate the current node of the lowest level here - this is overhead
  23    only.
  24
  25    children is almost always 1 here. Exception is flow insertion
  26 */
  27 static reiser4_block_nr
  28 max_balance_overhead(reiser4_block_nr childen, tree_level tree_height)
  29 {
  30         reiser4_block_nr ten_percent;
  31
  32         ten_percent = ((103 * childen) >> 10);
  33
  34         /* If we have too many balancings at the time, tree height can raise on
  35            more then 1. Assume that if tree_height is 5, it can raise on 1 only.
  36         */
  37         return ((tree_height < 5 ? 5 : tree_height) * 2 + (4 + ten_percent));
  38 }
  39
  40 /* this returns maximal possible number of nodes which can be modified plus
  41    number of new nodes which can be required to perform insertion of one item
  42    into the tree */
  43 /* it is only called when tree height changes, or gets initialized */
  44 reiser4_block_nr calc_estimate_one_insert(tree_level height)
  45 {
  46         return 1 + max_balance_overhead(1, height);
  47 }
  48
  49 reiser4_block_nr estimate_one_insert_item(reiser4_tree * tree)
  50 {
  51         return tree->estimate_one_insert;
  52 }
  53
  54 /* this returns maximal possible number of nodes which can be modified plus
  55    number of new nodes which can be required to perform insertion of one unit
  56    into an item in the tree */
  57 reiser4_block_nr estimate_one_insert_into_item(reiser4_tree * tree)
  58 {
  59         /* estimate insert into item just like item insertion */
  60         return tree->estimate_one_insert;
  61 }
  62
  63 reiser4_block_nr estimate_one_item_removal(reiser4_tree * tree)
  64 {
  65         /* on item removal reiser4 does not try to pack nodes more complact, so,
  66            only one node may be dirtied on leaf level */
  67         return tree->estimate_one_insert;
  68 }
  69
  70 /* on leaf level insert_flow may add CARRY_FLOW_NEW_NODES_LIMIT new nodes and
  71    dirty 3 existing nodes (insert point and both its neighbors).
  72    Max_balance_overhead should estimate number of blocks which may change/get
  73    added on internal levels */
  74 reiser4_block_nr estimate_insert_flow(tree_level height)
  75 {
  76         return 3 + CARRY_FLOW_NEW_NODES_LIMIT + max_balance_overhead(3 +
  77                                                                      CARRY_FLOW_NEW_NODES_LIMIT,
  78                                                                      height);
  79 }
  80
  81 /* returnes max number of nodes can be occupied by disk cluster */
  82 static reiser4_block_nr estimate_cluster(struct inode *inode, int unprepped)
  83 {
  84         int per_cluster;
  85         per_cluster = (unprepped ? 1 : cluster_nrpages(inode));
  86         return 3 + per_cluster +
  87                 max_balance_overhead(3 + per_cluster,
  88                                      REISER4_MAX_ZTREE_HEIGHT);
  89 }
  90
  91 /* how many nodes might get dirty and added
  92    during insertion of a disk cluster */
  93 reiser4_block_nr estimate_insert_cluster(struct inode *inode)
  94 {
  95         return estimate_cluster(inode, 1); /* 24 */
  96 }
  97
  98 /* how many nodes might get dirty and added
  99    during update of a (prepped or unprepped) disk cluster */
 100 reiser4_block_nr estimate_update_cluster(struct inode *inode)
 101 {
 102         return estimate_cluster(inode, 0); /* 44, for 64K-cluster */
 103 }
 104
 105 /* How many nodes occupied by a disk cluster might get dirty.
 106    Note that this estimation is not precise (i.e. disk cluster
 107    can occupy more nodes).
 108    Q: Why we don't use precise estimation?
 109    A: 1.Because precise estimation is fairly bad: 65536 nodes
 110         for 64K logical cluster, it means 256M of dead space on
 111         a partition
 112       2.It is a very rare case when disk cluster occupies more
 113         nodes then this estimation returns.
 114 */
 115 reiser4_block_nr estimate_dirty_cluster(struct inode *inode)
 116 {
 117         return cluster_nrpages(inode) + 4;
 118 }
 119
 120 /* Make Linus happy.
 121    Local variables:
 122    c-indentation-style: "K&R"
 123    mode-name: "LC"
 124    c-basic-offset: 8
 125    tab-width: 8
 126    fill-column: 120
 127    scroll-step: 1
 128    End:
 129 */