summaryrefslogtreecommitdiffstats
path: root/fs/ubifs/gc.c
diff options
context:
space:
mode:
authorAdrian Hunter <ext-adrian.hunter@nokia.com>2008-09-11 12:57:49 +0300
committerArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2008-09-30 11:12:59 +0300
commit46773be497a05010a2873e9ad96d739fb352c1e4 (patch)
treebea239e6e44de33fd8c562e21e38df71eefa2fc7 /fs/ubifs/gc.c
parentbed79935de9a658678f44b88a097367d3b26429f (diff)
downloadlinux-46773be497a05010a2873e9ad96d739fb352c1e4.tar.gz
linux-46773be497a05010a2873e9ad96d739fb352c1e4.tar.bz2
linux-46773be497a05010a2873e9ad96d739fb352c1e4.zip
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)
}
/**
+ * joinup - bring data nodes for an inode together.
+ * @c: UBIFS file-system description object
+ * @sleb: describes scanned LEB
+ * @inum: inode number
+ * @blk: block number
+ * @data: list to which to add data nodes
+ *
+ * This function looks at the first few nodes in the scanned LEB @sleb and adds
+ * them to @data if they are data nodes from @inum and have a larger block
+ * number than @blk. This function returns %0 on success and a negative error
+ * code on failure.
+ */
+static int joinup(struct ubifs_info *c, struct ubifs_scan_leb *sleb, ino_t inum,
+ unsigned int blk, struct list_head *data)
+{
+ int err, cnt = 6, lnum = sleb->lnum, offs;
+ struct ubifs_scan_node *snod, *tmp;
+ union ubifs_key *key;
+
+ list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
+ key = &snod->key;
+ if (key_inum(c, key) == inum &&
+ key_type(c, key) == UBIFS_DATA_KEY &&
+ key_block(c, key) > blk) {
+ offs = snod->offs;
+ err = ubifs_tnc_has_node(c, key, 0, lnum, offs, 0);
+ if (err < 0)
+ return err;
+ list_del(&snod->list);
+ if (err) {
+ list_add_tail(&snod->list, data);
+ blk = key_block(c, key);
+ } else
+ kfree(snod);
+ cnt = 6;
+ } else if (--cnt == 0)
+ break;
+ }
+ return 0;
+}
+
+/**
* move_nodes - move nodes.
* @c: UBIFS file-system description object
* @sleb: describes nodes to move
@@ -116,16 +158,21 @@ static int switch_gc_head(struct ubifs_info *c)
static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
{
struct ubifs_scan_node *snod, *tmp;
- struct list_head large, medium, small;
+ struct list_head data, large, medium, small;
struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
int avail, err, min = INT_MAX;
+ unsigned int blk = 0;
+ ino_t inum = 0;
+ INIT_LIST_HEAD(&data);
INIT_LIST_HEAD(&large);
INIT_LIST_HEAD(&medium);
INIT_LIST_HEAD(&small);
- list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
- struct list_head *lst;
+ while (!list_empty(&sleb->nodes)) {
+ struct list_head *lst = sleb->nodes.next;
+
+ snod = list_entry(lst, struct ubifs_scan_node, list);
ubifs_assert(snod->type != UBIFS_IDX_NODE);
ubifs_assert(snod->type != UBIFS_REF_NODE);
@@ -136,7 +183,6 @@ static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
if (err < 0)
goto out;
- lst = &snod->list;
list_del(lst);
if (!err) {
/* 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)
}
/*
- * Sort the list of nodes so that large nodes go first, and
- * small nodes go last.
+ * Sort the list of nodes so that data nodes go first, large
+ * nodes go second, and small nodes go last.
*/
- if (snod->len > MEDIUM_NODE_WM)
- list_add(lst, &large);
+ if (key_type(c, &snod->key) == UBIFS_DATA_KEY) {
+ if (inum != key_inum(c, &snod->key)) {
+ if (inum) {
+ /*
+ * Try to move data nodes from the same
+ * inode together.
+ */
+ err = joinup(c, sleb, inum, blk, &data);
+ if (err)
+ goto out;
+ }
+ inum = key_inum(c, &snod->key);
+ blk = key_block(c, &snod->key);
+ }
+ list_add_tail(lst, &data);
+ } else if (snod->len > MEDIUM_NODE_WM)
+ list_add_tail(lst, &large);
else if (snod->len > SMALL_NODE_WM)
- list_add(lst, &medium);
+ list_add_tail(lst, &medium);
else
- list_add(lst, &small);
+ list_add_tail(lst, &small);
/* And find the smallest node */
if (snod->len < min)
@@ -164,6 +225,7 @@ static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
* Join the tree lists so that we'd have one roughly sorted list
* ('large' will be the head of the joined list).
*/
+ list_splice(&data, &large);
list_splice(&medium, large.prev);
list_splice(&small, large.prev);