2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 * Authors: Artem Bityutskiy (Битюцкий Артём)
24 * This file is a part of UBIFS journal implementation and contains various
25 * functions which manipulate the log. The log is a fixed area on the flash
26 * which does not contain any data but refers to buds. The log is a part of the
32 #ifdef CONFIG_UBIFS_FS_DEBUG
33 static int dbg_check_bud_bytes(struct ubifs_info
*c
);
35 #define dbg_check_bud_bytes(c) 0
39 * ubifs_search_bud - search bud LEB.
40 * @c: UBIFS file-system description object
41 * @lnum: logical eraseblock number to search
43 * This function searches bud LEB @lnum. Returns bud description object in case
44 * of success and %NULL if there is no bud with this LEB number.
46 struct ubifs_bud
*ubifs_search_bud(struct ubifs_info
*c
, int lnum
)
49 struct ubifs_bud
*bud
;
51 spin_lock(&c
->buds_lock
);
54 bud
= rb_entry(p
, struct ubifs_bud
, rb
);
57 else if (lnum
> bud
->lnum
)
60 spin_unlock(&c
->buds_lock
);
64 spin_unlock(&c
->buds_lock
);
69 * ubifs_get_wbuf - get the wbuf associated with a LEB, if there is one.
70 * @c: UBIFS file-system description object
71 * @lnum: logical eraseblock number to search
73 * This functions returns the wbuf for @lnum or %NULL if there is not one.
75 struct ubifs_wbuf
*ubifs_get_wbuf(struct ubifs_info
*c
, int lnum
)
78 struct ubifs_bud
*bud
;
84 spin_lock(&c
->buds_lock
);
87 bud
= rb_entry(p
, struct ubifs_bud
, rb
);
90 else if (lnum
> bud
->lnum
)
94 spin_unlock(&c
->buds_lock
);
95 return &c
->jheads
[jhead
].wbuf
;
98 spin_unlock(&c
->buds_lock
);
103 * empty_log_bytes - calculate amount of empty space in the log.
104 * @c: UBIFS file-system description object
106 static inline long long empty_log_bytes(const struct ubifs_info
*c
)
110 h
= (long long)c
->lhead_lnum
* c
->leb_size
+ c
->lhead_offs
;
111 t
= (long long)c
->ltail_lnum
* c
->leb_size
;
114 return c
->log_bytes
- h
+ t
;
120 * ubifs_add_bud - add bud LEB to the tree of buds and its journal head list.
121 * @c: UBIFS file-system description object
122 * @bud: the bud to add
124 void ubifs_add_bud(struct ubifs_info
*c
, struct ubifs_bud
*bud
)
126 struct rb_node
**p
, *parent
= NULL
;
128 struct ubifs_jhead
*jhead
;
130 spin_lock(&c
->buds_lock
);
131 p
= &c
->buds
.rb_node
;
134 b
= rb_entry(parent
, struct ubifs_bud
, rb
);
135 ubifs_assert(bud
->lnum
!= b
->lnum
);
136 if (bud
->lnum
< b
->lnum
)
142 rb_link_node(&bud
->rb
, parent
, p
);
143 rb_insert_color(&bud
->rb
, &c
->buds
);
145 jhead
= &c
->jheads
[bud
->jhead
];
146 list_add_tail(&bud
->list
, &jhead
->buds_list
);
148 ubifs_assert(c
->replaying
&& c
->ro_mount
);
151 * Note, although this is a new bud, we anyway account this space now,
152 * before any data has been written to it, because this is about to
153 * guarantee fixed mount time, and this bud will anyway be read and
156 c
->bud_bytes
+= c
->leb_size
- bud
->start
;
158 dbg_log("LEB %d:%d, jhead %s, bud_bytes %lld", bud
->lnum
,
159 bud
->start
, dbg_jhead(bud
->jhead
), c
->bud_bytes
);
160 spin_unlock(&c
->buds_lock
);
164 * ubifs_add_bud_to_log - add a new bud to the log.
165 * @c: UBIFS file-system description object
166 * @jhead: journal head the bud belongs to
167 * @lnum: LEB number of the bud
168 * @offs: starting offset of the bud
170 * This function writes reference node for the new bud LEB @lnum it to the log,
171 * and adds it to the buds tress. It also makes sure that log size does not
172 * exceed the 'c->max_bud_bytes' limit. Returns zero in case of success,
173 * %-EAGAIN if commit is required, and a negative error codes in case of
176 int ubifs_add_bud_to_log(struct ubifs_info
*c
, int jhead
, int lnum
, int offs
)
179 struct ubifs_bud
*bud
;
180 struct ubifs_ref_node
*ref
;
182 bud
= kmalloc(sizeof(struct ubifs_bud
), GFP_NOFS
);
185 ref
= kzalloc(c
->ref_node_alsz
, GFP_NOFS
);
191 mutex_lock(&c
->log_mutex
);
192 ubifs_assert(!c
->ro_media
&& !c
->ro_mount
);
198 /* Make sure we have enough space in the log */
199 if (empty_log_bytes(c
) - c
->ref_node_alsz
< c
->min_log_bytes
) {
200 dbg_log("not enough log space - %lld, required %d",
201 empty_log_bytes(c
), c
->min_log_bytes
);
202 ubifs_commit_required(c
);
208 * Make sure the amount of space in buds will not exceed the
209 * 'c->max_bud_bytes' limit, because we want to guarantee mount time
212 * It is not necessary to hold @c->buds_lock when reading @c->bud_bytes
213 * because we are holding @c->log_mutex. All @c->bud_bytes take place
214 * when both @c->log_mutex and @c->bud_bytes are locked.
216 if (c
->bud_bytes
+ c
->leb_size
- offs
> c
->max_bud_bytes
) {
217 dbg_log("bud bytes %lld (%lld max), require commit",
218 c
->bud_bytes
, c
->max_bud_bytes
);
219 ubifs_commit_required(c
);
225 * If the journal is full enough - start background commit. Note, it is
226 * OK to read 'c->cmt_state' without spinlock because integer reads
227 * are atomic in the kernel.
229 if (c
->bud_bytes
>= c
->bg_bud_bytes
&&
230 c
->cmt_state
== COMMIT_RESTING
) {
231 dbg_log("bud bytes %lld (%lld max), initiate BG commit",
232 c
->bud_bytes
, c
->max_bud_bytes
);
233 ubifs_request_bg_commit(c
);
240 ref
->ch
.node_type
= UBIFS_REF_NODE
;
241 ref
->lnum
= cpu_to_le32(bud
->lnum
);
242 ref
->offs
= cpu_to_le32(bud
->start
);
243 ref
->jhead
= cpu_to_le32(jhead
);
245 if (c
->lhead_offs
> c
->leb_size
- c
->ref_node_alsz
) {
246 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
250 if (c
->lhead_offs
== 0) {
251 /* Must ensure next log LEB has been unmapped */
252 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
257 if (bud
->start
== 0) {
259 * Before writing the LEB reference which refers an empty LEB
260 * to the log, we have to make sure it is mapped, because
261 * otherwise we'd risk to refer an LEB with garbage in case of
262 * an unclean reboot, because the target LEB might have been
263 * unmapped, but not yet physically erased.
265 err
= ubifs_leb_map(c
, bud
->lnum
, UBI_SHORTTERM
);
270 dbg_log("write ref LEB %d:%d",
271 c
->lhead_lnum
, c
->lhead_offs
);
272 err
= ubifs_write_node(c
, ref
, UBIFS_REF_NODE_SZ
, c
->lhead_lnum
,
273 c
->lhead_offs
, UBI_SHORTTERM
);
277 c
->lhead_offs
+= c
->ref_node_alsz
;
279 ubifs_add_bud(c
, bud
);
281 mutex_unlock(&c
->log_mutex
);
286 mutex_unlock(&c
->log_mutex
);
293 * remove_buds - remove used buds.
294 * @c: UBIFS file-system description object
296 * This function removes use buds from the buds tree. It does not remove the
297 * buds which are pointed to by journal heads.
299 static void remove_buds(struct ubifs_info
*c
)
303 ubifs_assert(list_empty(&c
->old_buds
));
304 c
->cmt_bud_bytes
= 0;
305 spin_lock(&c
->buds_lock
);
306 p
= rb_first(&c
->buds
);
308 struct rb_node
*p1
= p
;
309 struct ubifs_bud
*bud
;
310 struct ubifs_wbuf
*wbuf
;
313 bud
= rb_entry(p1
, struct ubifs_bud
, rb
);
314 wbuf
= &c
->jheads
[bud
->jhead
].wbuf
;
316 if (wbuf
->lnum
== bud
->lnum
) {
318 * Do not remove buds which are pointed to by journal
319 * heads (non-closed buds).
321 c
->cmt_bud_bytes
+= wbuf
->offs
- bud
->start
;
322 dbg_log("preserve %d:%d, jhead %s, bud bytes %d, "
323 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
324 dbg_jhead(bud
->jhead
), wbuf
->offs
- bud
->start
,
326 bud
->start
= wbuf
->offs
;
328 c
->cmt_bud_bytes
+= c
->leb_size
- bud
->start
;
329 dbg_log("remove %d:%d, jhead %s, bud bytes %d, "
330 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
331 dbg_jhead(bud
->jhead
), c
->leb_size
- bud
->start
,
333 rb_erase(p1
, &c
->buds
);
335 * If the commit does not finish, the recovery will need
336 * to replay the journal, in which case the old buds
337 * must be unchanged. Do not release them until post
338 * commit i.e. do not allow them to be garbage
341 list_move(&bud
->list
, &c
->old_buds
);
344 spin_unlock(&c
->buds_lock
);
348 * ubifs_log_start_commit - start commit.
349 * @c: UBIFS file-system description object
350 * @ltail_lnum: return new log tail LEB number
352 * The commit operation starts with writing "commit start" node to the log and
353 * reference nodes for all journal heads which will define new journal after
354 * the commit has been finished. The commit start and reference nodes are
355 * written in one go to the nearest empty log LEB (hence, when commit is
356 * finished UBIFS may safely unmap all the previous log LEBs). This function
357 * returns zero in case of success and a negative error code in case of
360 int ubifs_log_start_commit(struct ubifs_info
*c
, int *ltail_lnum
)
363 struct ubifs_cs_node
*cs
;
364 struct ubifs_ref_node
*ref
;
365 int err
, i
, max_len
, len
;
367 err
= dbg_check_bud_bytes(c
);
371 max_len
= UBIFS_CS_NODE_SZ
+ c
->jhead_cnt
* UBIFS_REF_NODE_SZ
;
372 max_len
= ALIGN(max_len
, c
->min_io_size
);
373 buf
= cs
= kmalloc(max_len
, GFP_NOFS
);
377 cs
->ch
.node_type
= UBIFS_CS_NODE
;
378 cs
->cmt_no
= cpu_to_le64(c
->cmt_no
);
379 ubifs_prepare_node(c
, cs
, UBIFS_CS_NODE_SZ
, 0);
382 * Note, we do not lock 'c->log_mutex' because this is the commit start
383 * phase and we are exclusively using the log. And we do not lock
384 * write-buffer because nobody can write to the file-system at this
388 len
= UBIFS_CS_NODE_SZ
;
389 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
390 int lnum
= c
->jheads
[i
].wbuf
.lnum
;
391 int offs
= c
->jheads
[i
].wbuf
.offs
;
393 if (lnum
== -1 || offs
== c
->leb_size
)
396 dbg_log("add ref to LEB %d:%d for jhead %s",
397 lnum
, offs
, dbg_jhead(i
));
399 ref
->ch
.node_type
= UBIFS_REF_NODE
;
400 ref
->lnum
= cpu_to_le32(lnum
);
401 ref
->offs
= cpu_to_le32(offs
);
402 ref
->jhead
= cpu_to_le32(i
);
404 ubifs_prepare_node(c
, ref
, UBIFS_REF_NODE_SZ
, 0);
405 len
+= UBIFS_REF_NODE_SZ
;
408 ubifs_pad(c
, buf
+ len
, ALIGN(len
, c
->min_io_size
) - len
);
410 /* Switch to the next log LEB */
412 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
416 if (c
->lhead_offs
== 0) {
417 /* Must ensure next LEB has been unmapped */
418 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
423 len
= ALIGN(len
, c
->min_io_size
);
424 dbg_log("writing commit start at LEB %d:0, len %d", c
->lhead_lnum
, len
);
425 err
= ubifs_leb_write(c
, c
->lhead_lnum
, cs
, 0, len
, UBI_SHORTTERM
);
429 *ltail_lnum
= c
->lhead_lnum
;
431 c
->lhead_offs
+= len
;
432 if (c
->lhead_offs
== c
->leb_size
) {
433 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
440 * We have started the commit and now users may use the rest of the log
443 c
->min_log_bytes
= 0;
451 * ubifs_log_end_commit - end commit.
452 * @c: UBIFS file-system description object
453 * @ltail_lnum: new log tail LEB number
455 * This function is called on when the commit operation was finished. It
456 * moves log tail to new position and unmaps LEBs which contain obsolete data.
457 * Returns zero in case of success and a negative error code in case of
460 int ubifs_log_end_commit(struct ubifs_info
*c
, int ltail_lnum
)
465 * At this phase we have to lock 'c->log_mutex' because UBIFS allows FS
466 * writes during commit. Its only short "commit" start phase when
467 * writers are blocked.
469 mutex_lock(&c
->log_mutex
);
471 dbg_log("old tail was LEB %d:0, new tail is LEB %d:0",
472 c
->ltail_lnum
, ltail_lnum
);
474 c
->ltail_lnum
= ltail_lnum
;
476 * The commit is finished and from now on it must be guaranteed that
477 * there is always enough space for the next commit.
479 c
->min_log_bytes
= c
->leb_size
;
481 spin_lock(&c
->buds_lock
);
482 c
->bud_bytes
-= c
->cmt_bud_bytes
;
483 spin_unlock(&c
->buds_lock
);
485 err
= dbg_check_bud_bytes(c
);
487 mutex_unlock(&c
->log_mutex
);
492 * ubifs_log_post_commit - things to do after commit is completed.
493 * @c: UBIFS file-system description object
494 * @old_ltail_lnum: old log tail LEB number
496 * Release buds only after commit is completed, because they must be unchanged
497 * if recovery is needed.
499 * Unmap log LEBs only after commit is completed, because they may be needed for
502 * This function returns %0 on success and a negative error code on failure.
504 int ubifs_log_post_commit(struct ubifs_info
*c
, int old_ltail_lnum
)
508 while (!list_empty(&c
->old_buds
)) {
509 struct ubifs_bud
*bud
;
511 bud
= list_entry(c
->old_buds
.next
, struct ubifs_bud
, list
);
512 err
= ubifs_return_leb(c
, bud
->lnum
);
515 list_del(&bud
->list
);
518 mutex_lock(&c
->log_mutex
);
519 for (lnum
= old_ltail_lnum
; lnum
!= c
->ltail_lnum
;
520 lnum
= ubifs_next_log_lnum(c
, lnum
)) {
521 dbg_log("unmap log LEB %d", lnum
);
522 err
= ubifs_leb_unmap(c
, lnum
);
527 mutex_unlock(&c
->log_mutex
);
532 * struct done_ref - references that have been done.
542 * done_already - determine if a reference has been done already.
543 * @done_tree: rb-tree to store references that have been done
544 * @lnum: LEB number of reference
546 * This function returns %1 if the reference has been done, %0 if not, otherwise
547 * a negative error code is returned.
549 static int done_already(struct rb_root
*done_tree
, int lnum
)
551 struct rb_node
**p
= &done_tree
->rb_node
, *parent
= NULL
;
556 dr
= rb_entry(parent
, struct done_ref
, rb
);
559 else if (lnum
> dr
->lnum
)
565 dr
= kzalloc(sizeof(struct done_ref
), GFP_NOFS
);
571 rb_link_node(&dr
->rb
, parent
, p
);
572 rb_insert_color(&dr
->rb
, done_tree
);
578 * destroy_done_tree - destroy the done tree.
579 * @done_tree: done tree to destroy
581 static void destroy_done_tree(struct rb_root
*done_tree
)
583 struct rb_node
*this = done_tree
->rb_node
;
588 this = this->rb_left
;
590 } else if (this->rb_right
) {
591 this = this->rb_right
;
594 dr
= rb_entry(this, struct done_ref
, rb
);
595 this = rb_parent(this);
597 if (this->rb_left
== &dr
->rb
)
598 this->rb_left
= NULL
;
600 this->rb_right
= NULL
;
607 * add_node - add a node to the consolidated log.
608 * @c: UBIFS file-system description object
609 * @buf: buffer to which to add
610 * @lnum: LEB number to which to write is passed and returned here
611 * @offs: offset to where to write is passed and returned here
614 * This function returns %0 on success and a negative error code on failure.
616 static int add_node(struct ubifs_info
*c
, void *buf
, int *lnum
, int *offs
,
619 struct ubifs_ch
*ch
= node
;
620 int len
= le32_to_cpu(ch
->len
), remains
= c
->leb_size
- *offs
;
623 int sz
= ALIGN(*offs
, c
->min_io_size
), err
;
625 ubifs_pad(c
, buf
+ *offs
, sz
- *offs
);
626 err
= ubifs_leb_change(c
, *lnum
, buf
, sz
, UBI_SHORTTERM
);
629 *lnum
= ubifs_next_log_lnum(c
, *lnum
);
632 memcpy(buf
+ *offs
, node
, len
);
633 *offs
+= ALIGN(len
, 8);
638 * ubifs_consolidate_log - consolidate the log.
639 * @c: UBIFS file-system description object
641 * Repeated failed commits could cause the log to be full, but at least 1 LEB is
642 * needed for commit. This function rewrites the reference nodes in the log
643 * omitting duplicates, and failed CS nodes, and leaving no gaps.
645 * This function returns %0 on success and a negative error code on failure.
647 int ubifs_consolidate_log(struct ubifs_info
*c
)
649 struct ubifs_scan_leb
*sleb
;
650 struct ubifs_scan_node
*snod
;
651 struct rb_root done_tree
= RB_ROOT
;
652 int lnum
, err
, first
= 1, write_lnum
, offs
= 0;
655 dbg_rcvry("log tail LEB %d, log head LEB %d", c
->ltail_lnum
,
657 buf
= vmalloc(c
->leb_size
);
660 lnum
= c
->ltail_lnum
;
663 sleb
= ubifs_scan(c
, lnum
, 0, c
->sbuf
, 0);
668 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
669 switch (snod
->type
) {
670 case UBIFS_REF_NODE
: {
671 struct ubifs_ref_node
*ref
= snod
->node
;
672 int ref_lnum
= le32_to_cpu(ref
->lnum
);
674 err
= done_already(&done_tree
, ref_lnum
);
678 err
= add_node(c
, buf
, &write_lnum
,
688 err
= add_node(c
, buf
, &write_lnum
, &offs
,
696 ubifs_scan_destroy(sleb
);
697 if (lnum
== c
->lhead_lnum
)
699 lnum
= ubifs_next_log_lnum(c
, lnum
);
702 int sz
= ALIGN(offs
, c
->min_io_size
);
704 ubifs_pad(c
, buf
+ offs
, sz
- offs
);
705 err
= ubifs_leb_change(c
, write_lnum
, buf
, sz
, UBI_SHORTTERM
);
708 offs
= ALIGN(offs
, c
->min_io_size
);
710 destroy_done_tree(&done_tree
);
712 if (write_lnum
== c
->lhead_lnum
) {
713 ubifs_err("log is too full");
716 /* Unmap remaining LEBs */
719 lnum
= ubifs_next_log_lnum(c
, lnum
);
720 err
= ubifs_leb_unmap(c
, lnum
);
723 } while (lnum
!= c
->lhead_lnum
);
724 c
->lhead_lnum
= write_lnum
;
725 c
->lhead_offs
= offs
;
726 dbg_rcvry("new log head at %d:%d", c
->lhead_lnum
, c
->lhead_offs
);
730 ubifs_scan_destroy(sleb
);
732 destroy_done_tree(&done_tree
);
737 #ifdef CONFIG_UBIFS_FS_DEBUG
740 * dbg_check_bud_bytes - make sure bud bytes calculation are all right.
741 * @c: UBIFS file-system description object
743 * This function makes sure the amount of flash space used by closed buds
744 * ('c->bud_bytes' is correct). Returns zero in case of success and %-EINVAL in
747 static int dbg_check_bud_bytes(struct ubifs_info
*c
)
750 struct ubifs_bud
*bud
;
751 long long bud_bytes
= 0;
753 if (!dbg_is_chk_gen(c
))
756 spin_lock(&c
->buds_lock
);
757 for (i
= 0; i
< c
->jhead_cnt
; i
++)
758 list_for_each_entry(bud
, &c
->jheads
[i
].buds_list
, list
)
759 bud_bytes
+= c
->leb_size
- bud
->start
;
761 if (c
->bud_bytes
!= bud_bytes
) {
762 ubifs_err("bad bud_bytes %lld, calculated %lld",
763 c
->bud_bytes
, bud_bytes
);
766 spin_unlock(&c
->buds_lock
);
771 #endif /* CONFIG_UBIFS_FS_DEBUG */