diff options
author | Adrian Hunter <ext-adrian.hunter@nokia.com> | 2008-09-05 04:56:05 -0400 |
---|---|---|
committer | Artem Bityutskiy <Artem.Bityutskiy@nokia.com> | 2008-09-30 04:12:57 -0400 |
commit | 2242c689ecc390fb4719f595751351d1ecc5c409 (patch) | |
tree | f6116b867d6c65c924e67d9b53024e103d65e207 /fs | |
parent | 2953e73f1ce4b3284b409aefb9d46bbde6515c37 (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')
-rw-r--r-- | fs/ubifs/tnc.c | 54 |
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) | 2018 | check_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 | ||
2062 | do_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; |