aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ubifs/tnc.c
diff options
context:
space:
mode:
authorAdrian Hunter <ext-adrian.hunter@nokia.com>2008-09-05 04:56:05 -0400
committerArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2008-09-30 04:12:57 -0400
commit2242c689ecc390fb4719f595751351d1ecc5c409 (patch)
treef6116b867d6c65c924e67d9b53024e103d65e207 /fs/ubifs/tnc.c
parent2953e73f1ce4b3284b409aefb9d46bbde6515c37 (diff)
UBIFS: improve znode splitting rules
When inserting into a full znode it is split into two znodes. Because data node keys are usually consecutive, it is better to try to keep them together. This patch does a better job of that. Signed-off-by: Adrian Hunter <ext-adrian.hunter@nokia.com>
Diffstat (limited to 'fs/ubifs/tnc.c')
-rw-r--r--fs/ubifs/tnc.c54
1 files changed, 33 insertions, 21 deletions
diff --git a/fs/ubifs/tnc.c b/fs/ubifs/tnc.c
index 66dc57100bdf..e0878a431b9c 100644
--- a/fs/ubifs/tnc.c
+++ b/fs/ubifs/tnc.c
@@ -1962,7 +1962,7 @@ static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,
1962{ 1962{
1963 struct ubifs_znode *zn, *zi, *zp; 1963 struct ubifs_znode *zn, *zi, *zp;
1964 int i, keep, move, appending = 0; 1964 int i, keep, move, appending = 0;
1965 union ubifs_key *key = &zbr->key; 1965 union ubifs_key *key = &zbr->key, *key1;
1966 1966
1967 ubifs_assert(n >= 0 && n <= c->fanout); 1967 ubifs_assert(n >= 0 && n <= c->fanout);
1968 1968
@@ -2003,20 +2003,33 @@ again:
2003 zn->level = znode->level; 2003 zn->level = znode->level;
2004 2004
2005 /* Decide where to split */ 2005 /* Decide where to split */
2006 if (znode->level == 0 && n == c->fanout && 2006 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
2007 key_type(c, key) == UBIFS_DATA_KEY) { 2007 /* Try not to split consecutive data keys */
2008 union ubifs_key *key1; 2008 if (n == c->fanout) {
2009 2009 key1 = &znode->zbranch[n - 1].key;
2010 /* 2010 if (key_inum(c, key1) == key_inum(c, key) &&
2011 * If this is an inode which is being appended - do not split 2011 key_type(c, key1) == UBIFS_DATA_KEY)
2012 * it because no other zbranches can be inserted between 2012 appending = 1;
2013 * zbranches of consecutive data nodes anyway. 2013 } else
2014 */ 2014 goto check_split;
2015 key1 = &znode->zbranch[n - 1].key; 2015 } else if (appending && n != c->fanout) {
2016 if (key_inum(c, key1) == key_inum(c, key) && 2016 /* Try not to split consecutive data keys */
2017 key_type(c, key1) == UBIFS_DATA_KEY && 2017 appending = 0;
2018 key_block(c, key1) == key_block(c, key) - 1) 2018check_split:
2019 appending = 1; 2019 if (n >= (c->fanout + 1) / 2) {
2020 key1 = &znode->zbranch[0].key;
2021 if (key_inum(c, key1) == key_inum(c, key) &&
2022 key_type(c, key1) == UBIFS_DATA_KEY) {
2023 key1 = &znode->zbranch[n].key;
2024 if (key_inum(c, key1) != key_inum(c, key) ||
2025 key_type(c, key1) != UBIFS_DATA_KEY) {
2026 keep = n;
2027 move = c->fanout - keep;
2028 zi = znode;
2029 goto do_split;
2030 }
2031 }
2032 }
2020 } 2033 }
2021 2034
2022 if (appending) { 2035 if (appending) {
@@ -2046,6 +2059,8 @@ again:
2046 zbr->znode->parent = zn; 2059 zbr->znode->parent = zn;
2047 } 2060 }
2048 2061
2062do_split:
2063
2049 __set_bit(DIRTY_ZNODE, &zn->flags); 2064 __set_bit(DIRTY_ZNODE, &zn->flags);
2050 atomic_long_inc(&c->dirty_zn_cnt); 2065 atomic_long_inc(&c->dirty_zn_cnt);
2051 2066
@@ -2072,14 +2087,11 @@ again:
2072 2087
2073 /* Insert new znode (produced by spitting) into the parent */ 2088 /* Insert new znode (produced by spitting) into the parent */
2074 if (zp) { 2089 if (zp) {
2075 i = n; 2090 if (n == 0 && zi == znode && znode->iip == 0)
2091 correct_parent_keys(c, znode);
2092
2076 /* Locate insertion point */ 2093 /* Locate insertion point */
2077 n = znode->iip + 1; 2094 n = znode->iip + 1;
2078 if (appending && n != c->fanout)
2079 appending = 0;
2080
2081 if (i == 0 && zi == znode && znode->iip == 0)
2082 correct_parent_keys(c, znode);
2083 2095
2084 /* Tail recursion */ 2096 /* Tail recursion */
2085 zbr->key = zn->zbranch[0].key; 2097 zbr->key = zn->zbranch[0].key;