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 * next_log_lnum - switch to the next log LEB.
104 * @c: UBIFS file-system description object
105 * @lnum: current log LEB
107 static inline int next_log_lnum(const struct ubifs_info
*c
, int lnum
)
110 if (lnum
> c
->log_last
)
111 lnum
= UBIFS_LOG_LNUM
;
117 * empty_log_bytes - calculate amount of empty space in the log.
118 * @c: UBIFS file-system description object
120 static inline long long empty_log_bytes(const struct ubifs_info
*c
)
124 h
= (long long)c
->lhead_lnum
* c
->leb_size
+ c
->lhead_offs
;
125 t
= (long long)c
->ltail_lnum
* c
->leb_size
;
128 return c
->log_bytes
- h
+ t
;
134 * ubifs_add_bud - add bud LEB to the tree of buds and its journal head list.
135 * @c: UBIFS file-system description object
136 * @bud: the bud to add
138 void ubifs_add_bud(struct ubifs_info
*c
, struct ubifs_bud
*bud
)
140 struct rb_node
**p
, *parent
= NULL
;
142 struct ubifs_jhead
*jhead
;
144 spin_lock(&c
->buds_lock
);
145 p
= &c
->buds
.rb_node
;
148 b
= rb_entry(parent
, struct ubifs_bud
, rb
);
149 ubifs_assert(bud
->lnum
!= b
->lnum
);
150 if (bud
->lnum
< b
->lnum
)
156 rb_link_node(&bud
->rb
, parent
, p
);
157 rb_insert_color(&bud
->rb
, &c
->buds
);
159 jhead
= &c
->jheads
[bud
->jhead
];
160 list_add_tail(&bud
->list
, &jhead
->buds_list
);
162 ubifs_assert(c
->replaying
&& c
->ro_mount
);
165 * Note, although this is a new bud, we anyway account this space now,
166 * before any data has been written to it, because this is about to
167 * guarantee fixed mount time, and this bud will anyway be read and
170 c
->bud_bytes
+= c
->leb_size
- bud
->start
;
172 dbg_log("LEB %d:%d, jhead %s, bud_bytes %lld", bud
->lnum
,
173 bud
->start
, dbg_jhead(bud
->jhead
), c
->bud_bytes
);
174 spin_unlock(&c
->buds_lock
);
178 * ubifs_add_bud_to_log - add a new bud to the log.
179 * @c: UBIFS file-system description object
180 * @jhead: journal head the bud belongs to
181 * @lnum: LEB number of the bud
182 * @offs: starting offset of the bud
184 * This function writes reference node for the new bud LEB @lnum it to the log,
185 * and adds it to the buds tress. It also makes sure that log size does not
186 * exceed the 'c->max_bud_bytes' limit. Returns zero in case of success,
187 * %-EAGAIN if commit is required, and a negative error codes in case of
190 int ubifs_add_bud_to_log(struct ubifs_info
*c
, int jhead
, int lnum
, int offs
)
193 struct ubifs_bud
*bud
;
194 struct ubifs_ref_node
*ref
;
196 bud
= kmalloc(sizeof(struct ubifs_bud
), GFP_NOFS
);
199 ref
= kzalloc(c
->ref_node_alsz
, GFP_NOFS
);
205 mutex_lock(&c
->log_mutex
);
206 ubifs_assert(!c
->ro_media
&& !c
->ro_mount
);
212 /* Make sure we have enough space in the log */
213 if (empty_log_bytes(c
) - c
->ref_node_alsz
< c
->min_log_bytes
) {
214 dbg_log("not enough log space - %lld, required %d",
215 empty_log_bytes(c
), c
->min_log_bytes
);
216 ubifs_commit_required(c
);
222 * Make sure the amount of space in buds will not exceed the
223 * 'c->max_bud_bytes' limit, because we want to guarantee mount time
226 * It is not necessary to hold @c->buds_lock when reading @c->bud_bytes
227 * because we are holding @c->log_mutex. All @c->bud_bytes take place
228 * when both @c->log_mutex and @c->bud_bytes are locked.
230 if (c
->bud_bytes
+ c
->leb_size
- offs
> c
->max_bud_bytes
) {
231 dbg_log("bud bytes %lld (%lld max), require commit",
232 c
->bud_bytes
, c
->max_bud_bytes
);
233 ubifs_commit_required(c
);
239 * If the journal is full enough - start background commit. Note, it is
240 * OK to read 'c->cmt_state' without spinlock because integer reads
241 * are atomic in the kernel.
243 if (c
->bud_bytes
>= c
->bg_bud_bytes
&&
244 c
->cmt_state
== COMMIT_RESTING
) {
245 dbg_log("bud bytes %lld (%lld max), initiate BG commit",
246 c
->bud_bytes
, c
->max_bud_bytes
);
247 ubifs_request_bg_commit(c
);
254 ref
->ch
.node_type
= UBIFS_REF_NODE
;
255 ref
->lnum
= cpu_to_le32(bud
->lnum
);
256 ref
->offs
= cpu_to_le32(bud
->start
);
257 ref
->jhead
= cpu_to_le32(jhead
);
259 if (c
->lhead_offs
> c
->leb_size
- c
->ref_node_alsz
) {
260 c
->lhead_lnum
= next_log_lnum(c
, c
->lhead_lnum
);
264 if (c
->lhead_offs
== 0) {
265 /* Must ensure next log LEB has been unmapped */
266 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
271 if (bud
->start
== 0) {
273 * Before writing the LEB reference which refers an empty LEB
274 * to the log, we have to make sure it is mapped, because
275 * otherwise we'd risk to refer an LEB with garbage in case of
276 * an unclean reboot, because the target LEB might have been
277 * unmapped, but not yet physically erased.
279 err
= ubi_leb_map(c
->ubi
, bud
->lnum
, UBI_SHORTTERM
);
284 dbg_log("write ref LEB %d:%d",
285 c
->lhead_lnum
, c
->lhead_offs
);
286 err
= ubifs_write_node(c
, ref
, UBIFS_REF_NODE_SZ
, c
->lhead_lnum
,
287 c
->lhead_offs
, UBI_SHORTTERM
);
291 c
->lhead_offs
+= c
->ref_node_alsz
;
293 ubifs_add_bud(c
, bud
);
295 mutex_unlock(&c
->log_mutex
);
301 ubifs_ro_mode(c
, err
);
302 mutex_unlock(&c
->log_mutex
);
309 * remove_buds - remove used buds.
310 * @c: UBIFS file-system description object
312 * This function removes use buds from the buds tree. It does not remove the
313 * buds which are pointed to by journal heads.
315 static void remove_buds(struct ubifs_info
*c
)
319 ubifs_assert(list_empty(&c
->old_buds
));
320 c
->cmt_bud_bytes
= 0;
321 spin_lock(&c
->buds_lock
);
322 p
= rb_first(&c
->buds
);
324 struct rb_node
*p1
= p
;
325 struct ubifs_bud
*bud
;
326 struct ubifs_wbuf
*wbuf
;
329 bud
= rb_entry(p1
, struct ubifs_bud
, rb
);
330 wbuf
= &c
->jheads
[bud
->jhead
].wbuf
;
332 if (wbuf
->lnum
== bud
->lnum
) {
334 * Do not remove buds which are pointed to by journal
335 * heads (non-closed buds).
337 c
->cmt_bud_bytes
+= wbuf
->offs
- bud
->start
;
338 dbg_log("preserve %d:%d, jhead %s, bud bytes %d, "
339 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
340 dbg_jhead(bud
->jhead
), wbuf
->offs
- bud
->start
,
342 bud
->start
= wbuf
->offs
;
344 c
->cmt_bud_bytes
+= c
->leb_size
- bud
->start
;
345 dbg_log("remove %d:%d, jhead %s, bud bytes %d, "
346 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
347 dbg_jhead(bud
->jhead
), c
->leb_size
- bud
->start
,
349 rb_erase(p1
, &c
->buds
);
351 * If the commit does not finish, the recovery will need
352 * to replay the journal, in which case the old buds
353 * must be unchanged. Do not release them until post
354 * commit i.e. do not allow them to be garbage
357 list_move(&bud
->list
, &c
->old_buds
);
360 spin_unlock(&c
->buds_lock
);
364 * ubifs_log_start_commit - start commit.
365 * @c: UBIFS file-system description object
366 * @ltail_lnum: return new log tail LEB number
368 * The commit operation starts with writing "commit start" node to the log and
369 * reference nodes for all journal heads which will define new journal after
370 * the commit has been finished. The commit start and reference nodes are
371 * written in one go to the nearest empty log LEB (hence, when commit is
372 * finished UBIFS may safely unmap all the previous log LEBs). This function
373 * returns zero in case of success and a negative error code in case of
376 int ubifs_log_start_commit(struct ubifs_info
*c
, int *ltail_lnum
)
379 struct ubifs_cs_node
*cs
;
380 struct ubifs_ref_node
*ref
;
381 int err
, i
, max_len
, len
;
383 err
= dbg_check_bud_bytes(c
);
387 max_len
= UBIFS_CS_NODE_SZ
+ c
->jhead_cnt
* UBIFS_REF_NODE_SZ
;
388 max_len
= ALIGN(max_len
, c
->min_io_size
);
389 buf
= cs
= kmalloc(max_len
, GFP_NOFS
);
393 cs
->ch
.node_type
= UBIFS_CS_NODE
;
394 cs
->cmt_no
= cpu_to_le64(c
->cmt_no
);
395 ubifs_prepare_node(c
, cs
, UBIFS_CS_NODE_SZ
, 0);
398 * Note, we do not lock 'c->log_mutex' because this is the commit start
399 * phase and we are exclusively using the log. And we do not lock
400 * write-buffer because nobody can write to the file-system at this
404 len
= UBIFS_CS_NODE_SZ
;
405 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
406 int lnum
= c
->jheads
[i
].wbuf
.lnum
;
407 int offs
= c
->jheads
[i
].wbuf
.offs
;
409 if (lnum
== -1 || offs
== c
->leb_size
)
412 dbg_log("add ref to LEB %d:%d for jhead %s",
413 lnum
, offs
, dbg_jhead(i
));
415 ref
->ch
.node_type
= UBIFS_REF_NODE
;
416 ref
->lnum
= cpu_to_le32(lnum
);
417 ref
->offs
= cpu_to_le32(offs
);
418 ref
->jhead
= cpu_to_le32(i
);
420 ubifs_prepare_node(c
, ref
, UBIFS_REF_NODE_SZ
, 0);
421 len
+= UBIFS_REF_NODE_SZ
;
424 ubifs_pad(c
, buf
+ len
, ALIGN(len
, c
->min_io_size
) - len
);
426 /* Switch to the next log LEB */
428 c
->lhead_lnum
= next_log_lnum(c
, c
->lhead_lnum
);
432 if (c
->lhead_offs
== 0) {
433 /* Must ensure next LEB has been unmapped */
434 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
439 len
= ALIGN(len
, c
->min_io_size
);
440 dbg_log("writing commit start at LEB %d:0, len %d", c
->lhead_lnum
, len
);
441 err
= ubifs_leb_write(c
, c
->lhead_lnum
, cs
, 0, len
, UBI_SHORTTERM
);
445 *ltail_lnum
= c
->lhead_lnum
;
447 c
->lhead_offs
+= len
;
448 if (c
->lhead_offs
== c
->leb_size
) {
449 c
->lhead_lnum
= next_log_lnum(c
, c
->lhead_lnum
);
456 * We have started the commit and now users may use the rest of the log
459 c
->min_log_bytes
= 0;
467 * ubifs_log_end_commit - end commit.
468 * @c: UBIFS file-system description object
469 * @ltail_lnum: new log tail LEB number
471 * This function is called on when the commit operation was finished. It
472 * moves log tail to new position and unmaps LEBs which contain obsolete data.
473 * Returns zero in case of success and a negative error code in case of
476 int ubifs_log_end_commit(struct ubifs_info
*c
, int ltail_lnum
)
481 * At this phase we have to lock 'c->log_mutex' because UBIFS allows FS
482 * writes during commit. Its only short "commit" start phase when
483 * writers are blocked.
485 mutex_lock(&c
->log_mutex
);
487 dbg_log("old tail was LEB %d:0, new tail is LEB %d:0",
488 c
->ltail_lnum
, ltail_lnum
);
490 c
->ltail_lnum
= ltail_lnum
;
492 * The commit is finished and from now on it must be guaranteed that
493 * there is always enough space for the next commit.
495 c
->min_log_bytes
= c
->leb_size
;
497 spin_lock(&c
->buds_lock
);
498 c
->bud_bytes
-= c
->cmt_bud_bytes
;
499 spin_unlock(&c
->buds_lock
);
501 err
= dbg_check_bud_bytes(c
);
503 mutex_unlock(&c
->log_mutex
);
508 * ubifs_log_post_commit - things to do after commit is completed.
509 * @c: UBIFS file-system description object
510 * @old_ltail_lnum: old log tail LEB number
512 * Release buds only after commit is completed, because they must be unchanged
513 * if recovery is needed.
515 * Unmap log LEBs only after commit is completed, because they may be needed for
518 * This function returns %0 on success and a negative error code on failure.
520 int ubifs_log_post_commit(struct ubifs_info
*c
, int old_ltail_lnum
)
524 while (!list_empty(&c
->old_buds
)) {
525 struct ubifs_bud
*bud
;
527 bud
= list_entry(c
->old_buds
.next
, struct ubifs_bud
, list
);
528 err
= ubifs_return_leb(c
, bud
->lnum
);
531 list_del(&bud
->list
);
534 mutex_lock(&c
->log_mutex
);
535 for (lnum
= old_ltail_lnum
; lnum
!= c
->ltail_lnum
;
536 lnum
= next_log_lnum(c
, lnum
)) {
537 dbg_log("unmap log LEB %d", lnum
);
538 err
= ubifs_leb_unmap(c
, lnum
);
543 mutex_unlock(&c
->log_mutex
);
548 * struct done_ref - references that have been done.
558 * done_already - determine if a reference has been done already.
559 * @done_tree: rb-tree to store references that have been done
560 * @lnum: LEB number of reference
562 * This function returns %1 if the reference has been done, %0 if not, otherwise
563 * a negative error code is returned.
565 static int done_already(struct rb_root
*done_tree
, int lnum
)
567 struct rb_node
**p
= &done_tree
->rb_node
, *parent
= NULL
;
572 dr
= rb_entry(parent
, struct done_ref
, rb
);
575 else if (lnum
> dr
->lnum
)
581 dr
= kzalloc(sizeof(struct done_ref
), GFP_NOFS
);
587 rb_link_node(&dr
->rb
, parent
, p
);
588 rb_insert_color(&dr
->rb
, done_tree
);
594 * destroy_done_tree - destroy the done tree.
595 * @done_tree: done tree to destroy
597 static void destroy_done_tree(struct rb_root
*done_tree
)
599 struct rb_node
*this = done_tree
->rb_node
;
604 this = this->rb_left
;
606 } else if (this->rb_right
) {
607 this = this->rb_right
;
610 dr
= rb_entry(this, struct done_ref
, rb
);
611 this = rb_parent(this);
613 if (this->rb_left
== &dr
->rb
)
614 this->rb_left
= NULL
;
616 this->rb_right
= NULL
;
623 * add_node - add a node to the consolidated log.
624 * @c: UBIFS file-system description object
625 * @buf: buffer to which to add
626 * @lnum: LEB number to which to write is passed and returned here
627 * @offs: offset to where to write is passed and returned here
630 * This function returns %0 on success and a negative error code on failure.
632 static int add_node(struct ubifs_info
*c
, void *buf
, int *lnum
, int *offs
,
635 struct ubifs_ch
*ch
= node
;
636 int len
= le32_to_cpu(ch
->len
), remains
= c
->leb_size
- *offs
;
639 int sz
= ALIGN(*offs
, c
->min_io_size
), err
;
641 ubifs_pad(c
, buf
+ *offs
, sz
- *offs
);
642 err
= ubifs_leb_change(c
, *lnum
, buf
, sz
, UBI_SHORTTERM
);
645 *lnum
= next_log_lnum(c
, *lnum
);
648 memcpy(buf
+ *offs
, node
, len
);
649 *offs
+= ALIGN(len
, 8);
654 * ubifs_consolidate_log - consolidate the log.
655 * @c: UBIFS file-system description object
657 * Repeated failed commits could cause the log to be full, but at least 1 LEB is
658 * needed for commit. This function rewrites the reference nodes in the log
659 * omitting duplicates, and failed CS nodes, and leaving no gaps.
661 * This function returns %0 on success and a negative error code on failure.
663 int ubifs_consolidate_log(struct ubifs_info
*c
)
665 struct ubifs_scan_leb
*sleb
;
666 struct ubifs_scan_node
*snod
;
667 struct rb_root done_tree
= RB_ROOT
;
668 int lnum
, err
, first
= 1, write_lnum
, offs
= 0;
671 dbg_rcvry("log tail LEB %d, log head LEB %d", c
->ltail_lnum
,
673 buf
= vmalloc(c
->leb_size
);
676 lnum
= c
->ltail_lnum
;
679 sleb
= ubifs_scan(c
, lnum
, 0, c
->sbuf
, 0);
684 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
685 switch (snod
->type
) {
686 case UBIFS_REF_NODE
: {
687 struct ubifs_ref_node
*ref
= snod
->node
;
688 int ref_lnum
= le32_to_cpu(ref
->lnum
);
690 err
= done_already(&done_tree
, ref_lnum
);
694 err
= add_node(c
, buf
, &write_lnum
,
704 err
= add_node(c
, buf
, &write_lnum
, &offs
,
712 ubifs_scan_destroy(sleb
);
713 if (lnum
== c
->lhead_lnum
)
715 lnum
= next_log_lnum(c
, lnum
);
718 int sz
= ALIGN(offs
, c
->min_io_size
);
720 ubifs_pad(c
, buf
+ offs
, sz
- offs
);
721 err
= ubifs_leb_change(c
, write_lnum
, buf
, sz
, UBI_SHORTTERM
);
724 offs
= ALIGN(offs
, c
->min_io_size
);
726 destroy_done_tree(&done_tree
);
728 if (write_lnum
== c
->lhead_lnum
) {
729 ubifs_err("log is too full");
732 /* Unmap remaining LEBs */
735 lnum
= next_log_lnum(c
, lnum
);
736 err
= ubifs_leb_unmap(c
, lnum
);
739 } while (lnum
!= c
->lhead_lnum
);
740 c
->lhead_lnum
= write_lnum
;
741 c
->lhead_offs
= offs
;
742 dbg_rcvry("new log head at %d:%d", c
->lhead_lnum
, c
->lhead_offs
);
746 ubifs_scan_destroy(sleb
);
748 destroy_done_tree(&done_tree
);
753 #ifdef CONFIG_UBIFS_FS_DEBUG
756 * dbg_check_bud_bytes - make sure bud bytes calculation are all right.
757 * @c: UBIFS file-system description object
759 * This function makes sure the amount of flash space used by closed buds
760 * ('c->bud_bytes' is correct). Returns zero in case of success and %-EINVAL in
763 static int dbg_check_bud_bytes(struct ubifs_info
*c
)
766 struct ubifs_bud
*bud
;
767 long long bud_bytes
= 0;
769 if (!(ubifs_chk_flags
& UBIFS_CHK_GEN
))
772 spin_lock(&c
->buds_lock
);
773 for (i
= 0; i
< c
->jhead_cnt
; i
++)
774 list_for_each_entry(bud
, &c
->jheads
[i
].buds_list
, list
)
775 bud_bytes
+= c
->leb_size
- bud
->start
;
777 if (c
->bud_bytes
!= bud_bytes
) {
778 ubifs_err("bad bud_bytes %lld, calculated %lld",
779 c
->bud_bytes
, bud_bytes
);
782 spin_unlock(&c
->buds_lock
);
787 #endif /* CONFIG_UBIFS_FS_DEBUG */