fs/reiser4/estimate.c

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