aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ubifs/gc.c
diff options
context:
space:
mode:
authorAdrian Hunter <ext-adrian.hunter@nokia.com>2008-09-11 05:57:49 -0400
committerArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2008-09-30 04:12:59 -0400
commit46773be497a05010a2873e9ad96d739fb352c1e4 (patch)
treebea239e6e44de33fd8c562e21e38df71eefa2fc7 /fs/ubifs/gc.c
parentbed79935de9a658678f44b88a097367d3b26429f (diff)
UBIFS: improve garbage collection
Make garbage collection try to keep data nodes from the same inode together and in ascending order. This improves performance when reading those nodes especially when bulk-read is used. Signed-off-by: Adrian Hunter <ext-adrian.hunter@nokia.com>
Diffstat (limited to 'fs/ubifs/gc.c')
-rw-r--r--fs/ubifs/gc.c82
1 files changed, 72 insertions, 10 deletions
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index a6b633a5629f..0bef6501d58a 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -96,6 +96,48 @@ static int switch_gc_head(struct ubifs_info *c)
96} 96}
97 97
98/** 98/**
99 * joinup - bring data nodes for an inode together.
100 * @c: UBIFS file-system description object
101 * @sleb: describes scanned LEB
102 * @inum: inode number
103 * @blk: block number
104 * @data: list to which to add data nodes
105 *
106 * This function looks at the first few nodes in the scanned LEB @sleb and adds
107 * them to @data if they are data nodes from @inum and have a larger block
108 * number than @blk. This function returns %0 on success and a negative error
109 * code on failure.
110 */
111static int joinup(struct ubifs_info *c, struct ubifs_scan_leb *sleb, ino_t inum,
112 unsigned int blk, struct list_head *data)
113{
114 int err, cnt = 6, lnum = sleb->lnum, offs;
115 struct ubifs_scan_node *snod, *tmp;
116 union ubifs_key *key;
117
118 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
119 key = &snod->key;
120 if (key_inum(c, key) == inum &&
121 key_type(c, key) == UBIFS_DATA_KEY &&
122 key_block(c, key) > blk) {
123 offs = snod->offs;
124 err = ubifs_tnc_has_node(c, key, 0, lnum, offs, 0);
125 if (err < 0)
126 return err;
127 list_del(&snod->list);
128 if (err) {
129 list_add_tail(&snod->list, data);
130 blk = key_block(c, key);
131 } else
132 kfree(snod);
133 cnt = 6;
134 } else if (--cnt == 0)
135 break;
136 }
137 return 0;
138}
139
140/**
99 * move_nodes - move nodes. 141 * move_nodes - move nodes.
100 * @c: UBIFS file-system description object 142 * @c: UBIFS file-system description object
101 * @sleb: describes nodes to move 143 * @sleb: describes nodes to move
@@ -116,16 +158,21 @@ static int switch_gc_head(struct ubifs_info *c)
116static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb) 158static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
117{ 159{
118 struct ubifs_scan_node *snod, *tmp; 160 struct ubifs_scan_node *snod, *tmp;
119 struct list_head large, medium, small; 161 struct list_head data, large, medium, small;
120 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; 162 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
121 int avail, err, min = INT_MAX; 163 int avail, err, min = INT_MAX;
164 unsigned int blk = 0;
165 ino_t inum = 0;
122 166
167 INIT_LIST_HEAD(&data);
123 INIT_LIST_HEAD(&large); 168 INIT_LIST_HEAD(&large);
124 INIT_LIST_HEAD(&medium); 169 INIT_LIST_HEAD(&medium);
125 INIT_LIST_HEAD(&small); 170 INIT_LIST_HEAD(&small);
126 171
127 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { 172 while (!list_empty(&sleb->nodes)) {
128 struct list_head *lst; 173 struct list_head *lst = sleb->nodes.next;
174
175 snod = list_entry(lst, struct ubifs_scan_node, list);
129 176
130 ubifs_assert(snod->type != UBIFS_IDX_NODE); 177 ubifs_assert(snod->type != UBIFS_IDX_NODE);
131 ubifs_assert(snod->type != UBIFS_REF_NODE); 178 ubifs_assert(snod->type != UBIFS_REF_NODE);
@@ -136,7 +183,6 @@ static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
136 if (err < 0) 183 if (err < 0)
137 goto out; 184 goto out;
138 185
139 lst = &snod->list;
140 list_del(lst); 186 list_del(lst);
141 if (!err) { 187 if (!err) {
142 /* The node is obsolete, remove it from the list */ 188 /* The node is obsolete, remove it from the list */
@@ -145,15 +191,30 @@ static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
145 } 191 }
146 192
147 /* 193 /*
148 * Sort the list of nodes so that large nodes go first, and 194 * Sort the list of nodes so that data nodes go first, large
149 * small nodes go last. 195 * nodes go second, and small nodes go last.
150 */ 196 */
151 if (snod->len > MEDIUM_NODE_WM) 197 if (key_type(c, &snod->key) == UBIFS_DATA_KEY) {
152 list_add(lst, &large); 198 if (inum != key_inum(c, &snod->key)) {
199 if (inum) {
200 /*
201 * Try to move data nodes from the same
202 * inode together.
203 */
204 err = joinup(c, sleb, inum, blk, &data);
205 if (err)
206 goto out;
207 }
208 inum = key_inum(c, &snod->key);
209 blk = key_block(c, &snod->key);
210 }
211 list_add_tail(lst, &data);
212 } else if (snod->len > MEDIUM_NODE_WM)
213 list_add_tail(lst, &large);
153 else if (snod->len > SMALL_NODE_WM) 214 else if (snod->len > SMALL_NODE_WM)
154 list_add(lst, &medium); 215 list_add_tail(lst, &medium);
155 else 216 else
156 list_add(lst, &small); 217 list_add_tail(lst, &small);
157 218
158 /* And find the smallest node */ 219 /* And find the smallest node */
159 if (snod->len < min) 220 if (snod->len < min)
@@ -164,6 +225,7 @@ static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
164 * Join the tree lists so that we'd have one roughly sorted list 225 * Join the tree lists so that we'd have one roughly sorted list
165 * ('large' will be the head of the joined list). 226 * ('large' will be the head of the joined list).
166 */ 227 */
228 list_splice(&data, &large);
167 list_splice(&medium, large.prev); 229 list_splice(&medium, large.prev);
168 list_splice(&small, large.prev); 230 list_splice(&small, large.prev);
169 231