aboutsummaryrefslogtreecommitdiffstats
path: root/fs
diff options
context:
space:
mode:
authorArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2011-05-15 04:37:17 -0400
committerArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2011-05-16 03:31:40 -0400
commit074bcb9b5ce698bd7b02ddb469da9cba21fe83fd (patch)
tree98a46a995a17e7199116a9c3970f9299a16effcc /fs
parentaf1dd412646a58b29522f93f7befa944d7d361c0 (diff)
UBIFS: simplify replay
This patch simplifies the replay code and makes it smaller. First of all, we can notice that we do not really need to create bud replay entries and insert them to the replay tree, because the only reason we do this is to set buds lprops correctly at the end. Instead, we can just walk the list of buds at the very end and set lprops for each bud. This allows us to get rid of whole 'insert_ref_node()' function, the 'REPLAY_REF' flag, and several fields in 'struct replay_entry'. Then we can also notice that we do not need the 'flags' 'struct replay_entry' field, because there is only one flag - 'REPLAY_DELETION'. Instead, we can just add a 'deletion' bit fields. As a result, this patch deletes much more lines that in adds. Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/ubifs/replay.c167
1 files changed, 59 insertions, 108 deletions
diff --git a/fs/ubifs/replay.c b/fs/ubifs/replay.c
index ee2f0b240ce0..08f5036a9056 100644
--- a/fs/ubifs/replay.c
+++ b/fs/ubifs/replay.c
@@ -34,32 +34,18 @@
34 34
35#include "ubifs.h" 35#include "ubifs.h"
36 36
37/*
38 * Replay flags.
39 *
40 * REPLAY_DELETION: node was deleted
41 * REPLAY_REF: node is a reference node
42 */
43enum {
44 REPLAY_DELETION = 1,
45 REPLAY_REF = 2,
46};
47
48/** 37/**
49 * struct replay_entry - replay tree entry. 38 * struct replay_entry - replay tree entry.
50 * @lnum: logical eraseblock number of the node 39 * @lnum: logical eraseblock number of the node
51 * @offs: node offset 40 * @offs: node offset
52 * @len: node length 41 * @len: node length
42 * @deletion: non-zero if this entry corresponds to a node deletion
53 * @sqnum: node sequence number 43 * @sqnum: node sequence number
54 * @flags: replay flags
55 * @rb: links the replay tree 44 * @rb: links the replay tree
56 * @key: node key 45 * @key: node key
57 * @nm: directory entry name 46 * @nm: directory entry name
58 * @old_size: truncation old size 47 * @old_size: truncation old size
59 * @new_size: truncation new size 48 * @new_size: truncation new size
60 * @free: amount of free space in a bud
61 * @dirty: amount of dirty space in a bud from padding and deletion nodes
62 * @jhead: journal head number of the bud
63 * 49 *
64 * UBIFS journal replay must compare node sequence numbers, which means it must 50 * UBIFS journal replay must compare node sequence numbers, which means it must
65 * build a tree of node information to insert into the TNC. 51 * build a tree of node information to insert into the TNC.
@@ -68,8 +54,8 @@ struct replay_entry {
68 int lnum; 54 int lnum;
69 int offs; 55 int offs;
70 int len; 56 int len;
57 unsigned int deletion:1;
71 unsigned long long sqnum; 58 unsigned long long sqnum;
72 int flags;
73 struct rb_node rb; 59 struct rb_node rb;
74 union ubifs_key key; 60 union ubifs_key key;
75 union { 61 union {
@@ -78,11 +64,6 @@ struct replay_entry {
78 loff_t old_size; 64 loff_t old_size;
79 loff_t new_size; 65 loff_t new_size;
80 }; 66 };
81 struct {
82 int free;
83 int dirty;
84 int jhead;
85 };
86 }; 67 };
87}; 68};
88 69
@@ -105,28 +86,32 @@ struct bud_entry {
105/** 86/**
106 * set_bud_lprops - set free and dirty space used by a bud. 87 * set_bud_lprops - set free and dirty space used by a bud.
107 * @c: UBIFS file-system description object 88 * @c: UBIFS file-system description object
108 * @r: replay entry of bud 89 * @b: bud entry which describes the bud
90 *
91 * This function makes sure the LEB properties of bud @b are set correctly
92 * after the replay. Returns zero in case of success and a negative error code
93 * in case of failure.
109 */ 94 */
110static int set_bud_lprops(struct ubifs_info *c, struct replay_entry *r) 95static int set_bud_lprops(struct ubifs_info *c, struct bud_entry *b)
111{ 96{
112 const struct ubifs_lprops *lp; 97 const struct ubifs_lprops *lp;
113 int err = 0, dirty; 98 int err = 0, dirty;
114 99
115 ubifs_get_lprops(c); 100 ubifs_get_lprops(c);
116 101
117 lp = ubifs_lpt_lookup_dirty(c, r->lnum); 102 lp = ubifs_lpt_lookup_dirty(c, b->bud->lnum);
118 if (IS_ERR(lp)) { 103 if (IS_ERR(lp)) {
119 err = PTR_ERR(lp); 104 err = PTR_ERR(lp);
120 goto out; 105 goto out;
121 } 106 }
122 107
123 dirty = lp->dirty; 108 dirty = lp->dirty;
124 if (r->offs == 0 && (lp->free != c->leb_size || lp->dirty != 0)) { 109 if (b->bud->start == 0 && (lp->free != c->leb_size || lp->dirty != 0)) {
125 /* 110 /*
126 * The LEB was added to the journal with a starting offset of 111 * The LEB was added to the journal with a starting offset of
127 * zero which means the LEB must have been empty. The LEB 112 * zero which means the LEB must have been empty. The LEB
128 * property values should be lp->free == c->leb_size and 113 * property values should be @lp->free == @c->leb_size and
129 * lp->dirty == 0, but that is not the case. The reason is that 114 * @lp->dirty == 0, but that is not the case. The reason is that
130 * the LEB had been garbage collected before it became the bud, 115 * the LEB had been garbage collected before it became the bud,
131 * and there was not commit inbetween. The garbage collector 116 * and there was not commit inbetween. The garbage collector
132 * resets the free and dirty space without recording it 117 * resets the free and dirty space without recording it
@@ -135,15 +120,15 @@ static int set_bud_lprops(struct ubifs_info *c, struct replay_entry *r)
135 * 120 *
136 * We do not need to adjust free space because the scan has told 121 * We do not need to adjust free space because the scan has told
137 * us the exact value which is recorded in the replay entry as 122 * us the exact value which is recorded in the replay entry as
138 * r->free. 123 * @b->free.
139 * 124 *
140 * However we do need to subtract from the dirty space the 125 * However we do need to subtract from the dirty space the
141 * amount of space that the garbage collector reclaimed, which 126 * amount of space that the garbage collector reclaimed, which
142 * is the whole LEB minus the amount of space that was free. 127 * is the whole LEB minus the amount of space that was free.
143 */ 128 */
144 dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", r->lnum, 129 dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
145 lp->free, lp->dirty); 130 lp->free, lp->dirty);
146 dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", r->lnum, 131 dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
147 lp->free, lp->dirty); 132 lp->free, lp->dirty);
148 dirty -= c->leb_size - lp->free; 133 dirty -= c->leb_size - lp->free;
149 /* 134 /*
@@ -155,10 +140,10 @@ static int set_bud_lprops(struct ubifs_info *c, struct replay_entry *r)
155 */ 140 */
156 if (dirty != 0) 141 if (dirty != 0)
157 dbg_msg("LEB %d lp: %d free %d dirty " 142 dbg_msg("LEB %d lp: %d free %d dirty "
158 "replay: %d free %d dirty", r->lnum, lp->free, 143 "replay: %d free %d dirty", b->bud->lnum,
159 lp->dirty, r->free, r->dirty); 144 lp->free, lp->dirty, b->free, b->dirty);
160 } 145 }
161 lp = ubifs_change_lp(c, lp, r->free, dirty + r->dirty, 146 lp = ubifs_change_lp(c, lp, b->free, dirty + b->dirty,
162 lp->flags | LPROPS_TAKEN, 0); 147 lp->flags | LPROPS_TAKEN, 0);
163 if (IS_ERR(lp)) { 148 if (IS_ERR(lp)) {
164 err = PTR_ERR(lp); 149 err = PTR_ERR(lp);
@@ -166,8 +151,9 @@ static int set_bud_lprops(struct ubifs_info *c, struct replay_entry *r)
166 } 151 }
167 152
168 /* Make sure the journal head points to the latest bud */ 153 /* Make sure the journal head points to the latest bud */
169 err = ubifs_wbuf_seek_nolock(&c->jheads[r->jhead].wbuf, r->lnum, 154 err = ubifs_wbuf_seek_nolock(&c->jheads[b->bud->jhead].wbuf,
170 c->leb_size - r->free, UBI_SHORTTERM); 155 b->bud->lnum, c->leb_size - b->free,
156 UBI_SHORTTERM);
171 157
172out: 158out:
173 ubifs_release_lprops(c); 159 ubifs_release_lprops(c);
@@ -175,6 +161,27 @@ out:
175} 161}
176 162
177/** 163/**
164 * set_buds_lprops - set free and dirty space for all replayed buds.
165 * @c: UBIFS file-system description object
166 *
167 * This function sets LEB properties for all replayed buds. Returns zero in
168 * case of success and a negative error code in case of failure.
169 */
170static int set_buds_lprops(struct ubifs_info *c)
171{
172 struct bud_entry *b;
173 int err;
174
175 list_for_each_entry(b, &c->replay_buds, list) {
176 err = set_bud_lprops(c, b);
177 if (err)
178 return err;
179 }
180
181 return 0;
182}
183
184/**
178 * trun_remove_range - apply a replay entry for a truncation to the TNC. 185 * trun_remove_range - apply a replay entry for a truncation to the TNC.
179 * @c: UBIFS file-system description object 186 * @c: UBIFS file-system description object
180 * @r: replay entry of truncation 187 * @r: replay entry of truncation
@@ -210,24 +217,22 @@ static int trun_remove_range(struct ubifs_info *c, struct replay_entry *r)
210 */ 217 */
211static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r) 218static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
212{ 219{
213 int err, deletion = ((r->flags & REPLAY_DELETION) != 0); 220 int err;
214 221
215 dbg_mnt("LEB %d:%d len %d flgs %d sqnum %llu %s", r->lnum, 222 dbg_mnt("LEB %d:%d len %d deletion %d sqnum %llu %s", r->lnum,
216 r->offs, r->len, r->flags, r->sqnum, DBGKEY(&r->key)); 223 r->offs, r->len, r->deletion, r->sqnum, DBGKEY(&r->key));
217 224
218 /* Set c->replay_sqnum to help deal with dangling branches. */ 225 /* Set c->replay_sqnum to help deal with dangling branches. */
219 c->replay_sqnum = r->sqnum; 226 c->replay_sqnum = r->sqnum;
220 227
221 if (r->flags & REPLAY_REF) 228 if (is_hash_key(c, &r->key)) {
222 err = set_bud_lprops(c, r); 229 if (r->deletion)
223 else if (is_hash_key(c, &r->key)) {
224 if (deletion)
225 err = ubifs_tnc_remove_nm(c, &r->key, &r->nm); 230 err = ubifs_tnc_remove_nm(c, &r->key, &r->nm);
226 else 231 else
227 err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs, 232 err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs,
228 r->len, &r->nm); 233 r->len, &r->nm);
229 } else { 234 } else {
230 if (deletion) 235 if (r->deletion)
231 switch (key_type(c, &r->key)) { 236 switch (key_type(c, &r->key)) {
232 case UBIFS_INO_KEY: 237 case UBIFS_INO_KEY:
233 { 238 {
@@ -250,7 +255,7 @@ static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
250 return err; 255 return err;
251 256
252 if (c->need_recovery) 257 if (c->need_recovery)
253 err = ubifs_recover_size_accum(c, &r->key, deletion, 258 err = ubifs_recover_size_accum(c, &r->key, r->deletion,
254 r->new_size); 259 r->new_size);
255 } 260 }
256 261
@@ -373,11 +378,11 @@ static int insert_node(struct ubifs_info *c, int lnum, int offs, int len,
373 r->lnum = lnum; 378 r->lnum = lnum;
374 r->offs = offs; 379 r->offs = offs;
375 r->len = len; 380 r->len = len;
381 r->deletion = !!deletion;
376 r->sqnum = sqnum; 382 r->sqnum = sqnum;
377 r->flags = (deletion ? REPLAY_DELETION : 0); 383 key_copy(c, key, &r->key);
378 r->old_size = old_size; 384 r->old_size = old_size;
379 r->new_size = new_size; 385 r->new_size = new_size;
380 key_copy(c, key, &r->key);
381 386
382 rb_link_node(&r->rb, parent, p); 387 rb_link_node(&r->rb, parent, p);
383 rb_insert_color(&r->rb, &c->replay_tree); 388 rb_insert_color(&r->rb, &c->replay_tree);
@@ -445,13 +450,13 @@ static int insert_dent(struct ubifs_info *c, int lnum, int offs, int len,
445 r->lnum = lnum; 450 r->lnum = lnum;
446 r->offs = offs; 451 r->offs = offs;
447 r->len = len; 452 r->len = len;
453 r->deletion = !!deletion;
448 r->sqnum = sqnum; 454 r->sqnum = sqnum;
455 key_copy(c, key, &r->key);
449 r->nm.len = nlen; 456 r->nm.len = nlen;
450 memcpy(nbuf, name, nlen); 457 memcpy(nbuf, name, nlen);
451 nbuf[nlen] = '\0'; 458 nbuf[nlen] = '\0';
452 r->nm.name = nbuf; 459 r->nm.name = nbuf;
453 r->flags = (deletion ? REPLAY_DELETION : 0);
454 key_copy(c, key, &r->key);
455 460
456 ubifs_assert(!*p); 461 ubifs_assert(!*p);
457 rb_link_node(&r->rb, parent, p); 462 rb_link_node(&r->rb, parent, p);
@@ -653,58 +658,6 @@ out_dump:
653} 658}
654 659
655/** 660/**
656 * insert_ref_node - insert a reference node to the replay tree.
657 * @c: UBIFS file-system description object
658 * @lnum: node logical eraseblock number
659 * @offs: node offset
660 * @sqnum: sequence number
661 * @free: amount of free space in bud
662 * @dirty: amount of dirty space from padding and deletion nodes
663 * @jhead: journal head number for the bud
664 *
665 * This function inserts a reference node to the replay tree and returns zero
666 * in case of success or a negative error code in case of failure.
667 */
668static int insert_ref_node(struct ubifs_info *c, int lnum, int offs,
669 unsigned long long sqnum, int free, int dirty,
670 int jhead)
671{
672 struct rb_node **p = &c->replay_tree.rb_node, *parent = NULL;
673 struct replay_entry *r;
674
675 dbg_mnt("add ref LEB %d:%d", lnum, offs);
676 while (*p) {
677 parent = *p;
678 r = rb_entry(parent, struct replay_entry, rb);
679 if (sqnum < r->sqnum) {
680 p = &(*p)->rb_left;
681 continue;
682 } else if (sqnum > r->sqnum) {
683 p = &(*p)->rb_right;
684 continue;
685 }
686 ubifs_err("duplicate sqnum in replay tree");
687 return -EINVAL;
688 }
689
690 r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
691 if (!r)
692 return -ENOMEM;
693
694 r->lnum = lnum;
695 r->offs = offs;
696 r->sqnum = sqnum;
697 r->flags = REPLAY_REF;
698 r->free = free;
699 r->dirty = dirty;
700 r->jhead = jhead;
701
702 rb_link_node(&r->rb, parent, p);
703 rb_insert_color(&r->rb, &c->replay_tree);
704 return 0;
705}
706
707/**
708 * replay_buds - replay all buds. 661 * replay_buds - replay all buds.
709 * @c: UBIFS file-system description object 662 * @c: UBIFS file-system description object
710 * 663 *
@@ -714,18 +667,12 @@ static int insert_ref_node(struct ubifs_info *c, int lnum, int offs,
714static int replay_buds(struct ubifs_info *c) 667static int replay_buds(struct ubifs_info *c)
715{ 668{
716 struct bud_entry *b; 669 struct bud_entry *b;
717 int err, uninitialized_var(free), uninitialized_var(dirty); 670 int err;
718 unsigned long long prev_sqnum = 0; 671 unsigned long long prev_sqnum = 0;
719 672
720 list_for_each_entry(b, &c->replay_buds, list) { 673 list_for_each_entry(b, &c->replay_buds, list) {
721 err = replay_bud(c, b->bud->lnum, b->bud->start, b->bud->jhead, 674 err = replay_bud(c, b->bud->lnum, b->bud->start, b->bud->jhead,
722 &free, &dirty); 675 &b->free, &b->dirty);
723 if (err)
724 return err;
725 b->free = free;
726 b->dirty = dirty;
727 err = insert_ref_node(c, b->bud->lnum, b->bud->start, b->sqnum,
728 free, dirty, b->bud->jhead);
729 if (err) 676 if (err)
730 return err; 677 return err;
731 678
@@ -1074,6 +1021,10 @@ int ubifs_replay_journal(struct ubifs_info *c)
1074 if (err) 1021 if (err)
1075 goto out; 1022 goto out;
1076 1023
1024 err = set_buds_lprops(c);
1025 if (err)
1026 goto out;
1027
1077 /* 1028 /*
1078 * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable 1029 * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable
1079 * to roughly estimate index growth. Things like @c->bi.min_idx_lebs 1030 * to roughly estimate index growth. Things like @c->bi.min_idx_lebs