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
= ubi_leb_map(c
->ubi
, 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
);
287 ubifs_ro_mode(c
, err
);
288 mutex_unlock(&c
->log_mutex
);
295 * remove_buds - remove used buds.
296 * @c: UBIFS file-system description object
298 * This function removes use buds from the buds tree. It does not remove the
299 * buds which are pointed to by journal heads.
301 static void remove_buds(struct ubifs_info
*c
)
305 ubifs_assert(list_empty(&c
->old_buds
));
306 c
->cmt_bud_bytes
= 0;
307 spin_lock(&c
->buds_lock
);
308 p
= rb_first(&c
->buds
);
310 struct rb_node
*p1
= p
;
311 struct ubifs_bud
*bud
;
312 struct ubifs_wbuf
*wbuf
;
315 bud
= rb_entry(p1
, struct ubifs_bud
, rb
);
316 wbuf
= &c
->jheads
[bud
->jhead
].wbuf
;
318 if (wbuf
->lnum
== bud
->lnum
) {
320 * Do not remove buds which are pointed to by journal
321 * heads (non-closed buds).
323 c
->cmt_bud_bytes
+= wbuf
->offs
- bud
->start
;
324 dbg_log("preserve %d:%d, jhead %s, bud bytes %d, "
325 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
326 dbg_jhead(bud
->jhead
), wbuf
->offs
- bud
->start
,
328 bud
->start
= wbuf
->offs
;
330 c
->cmt_bud_bytes
+= c
->leb_size
- bud
->start
;
331 dbg_log("remove %d:%d, jhead %s, bud bytes %d, "
332 "cmt_bud_bytes %lld", bud
->lnum
, bud
->start
,
333 dbg_jhead(bud
->jhead
), c
->leb_size
- bud
->start
,
335 rb_erase(p1
, &c
->buds
);
337 * If the commit does not finish, the recovery will need
338 * to replay the journal, in which case the old buds
339 * must be unchanged. Do not release them until post
340 * commit i.e. do not allow them to be garbage
343 list_move(&bud
->list
, &c
->old_buds
);
346 spin_unlock(&c
->buds_lock
);
350 * ubifs_log_start_commit - start commit.
351 * @c: UBIFS file-system description object
352 * @ltail_lnum: return new log tail LEB number
354 * The commit operation starts with writing "commit start" node to the log and
355 * reference nodes for all journal heads which will define new journal after
356 * the commit has been finished. The commit start and reference nodes are
357 * written in one go to the nearest empty log LEB (hence, when commit is
358 * finished UBIFS may safely unmap all the previous log LEBs). This function
359 * returns zero in case of success and a negative error code in case of
362 int ubifs_log_start_commit(struct ubifs_info
*c
, int *ltail_lnum
)
365 struct ubifs_cs_node
*cs
;
366 struct ubifs_ref_node
*ref
;
367 int err
, i
, max_len
, len
;
369 err
= dbg_check_bud_bytes(c
);
373 max_len
= UBIFS_CS_NODE_SZ
+ c
->jhead_cnt
* UBIFS_REF_NODE_SZ
;
374 max_len
= ALIGN(max_len
, c
->min_io_size
);
375 buf
= cs
= kmalloc(max_len
, GFP_NOFS
);
379 cs
->ch
.node_type
= UBIFS_CS_NODE
;
380 cs
->cmt_no
= cpu_to_le64(c
->cmt_no
);
381 ubifs_prepare_node(c
, cs
, UBIFS_CS_NODE_SZ
, 0);
384 * Note, we do not lock 'c->log_mutex' because this is the commit start
385 * phase and we are exclusively using the log. And we do not lock
386 * write-buffer because nobody can write to the file-system at this
390 len
= UBIFS_CS_NODE_SZ
;
391 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
392 int lnum
= c
->jheads
[i
].wbuf
.lnum
;
393 int offs
= c
->jheads
[i
].wbuf
.offs
;
395 if (lnum
== -1 || offs
== c
->leb_size
)
398 dbg_log("add ref to LEB %d:%d for jhead %s",
399 lnum
, offs
, dbg_jhead(i
));
401 ref
->ch
.node_type
= UBIFS_REF_NODE
;
402 ref
->lnum
= cpu_to_le32(lnum
);
403 ref
->offs
= cpu_to_le32(offs
);
404 ref
->jhead
= cpu_to_le32(i
);
406 ubifs_prepare_node(c
, ref
, UBIFS_REF_NODE_SZ
, 0);
407 len
+= UBIFS_REF_NODE_SZ
;
410 ubifs_pad(c
, buf
+ len
, ALIGN(len
, c
->min_io_size
) - len
);
412 /* Switch to the next log LEB */
414 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
418 if (c
->lhead_offs
== 0) {
419 /* Must ensure next LEB has been unmapped */
420 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
425 len
= ALIGN(len
, c
->min_io_size
);
426 dbg_log("writing commit start at LEB %d:0, len %d", c
->lhead_lnum
, len
);
427 err
= ubifs_leb_write(c
, c
->lhead_lnum
, cs
, 0, len
, UBI_SHORTTERM
);
431 *ltail_lnum
= c
->lhead_lnum
;
433 c
->lhead_offs
+= len
;
434 if (c
->lhead_offs
== c
->leb_size
) {
435 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
442 * We have started the commit and now users may use the rest of the log
445 c
->min_log_bytes
= 0;
453 * ubifs_log_end_commit - end commit.
454 * @c: UBIFS file-system description object
455 * @ltail_lnum: new log tail LEB number
457 * This function is called on when the commit operation was finished. It
458 * moves log tail to new position and unmaps LEBs which contain obsolete data.
459 * Returns zero in case of success and a negative error code in case of
462 int ubifs_log_end_commit(struct ubifs_info
*c
, int ltail_lnum
)
467 * At this phase we have to lock 'c->log_mutex' because UBIFS allows FS
468 * writes during commit. Its only short "commit" start phase when
469 * writers are blocked.
471 mutex_lock(&c
->log_mutex
);
473 dbg_log("old tail was LEB %d:0, new tail is LEB %d:0",
474 c
->ltail_lnum
, ltail_lnum
);
476 c
->ltail_lnum
= ltail_lnum
;
478 * The commit is finished and from now on it must be guaranteed that
479 * there is always enough space for the next commit.
481 c
->min_log_bytes
= c
->leb_size
;
483 spin_lock(&c
->buds_lock
);
484 c
->bud_bytes
-= c
->cmt_bud_bytes
;
485 spin_unlock(&c
->buds_lock
);
487 err
= dbg_check_bud_bytes(c
);
489 mutex_unlock(&c
->log_mutex
);
494 * ubifs_log_post_commit - things to do after commit is completed.
495 * @c: UBIFS file-system description object
496 * @old_ltail_lnum: old log tail LEB number
498 * Release buds only after commit is completed, because they must be unchanged
499 * if recovery is needed.
501 * Unmap log LEBs only after commit is completed, because they may be needed for
504 * This function returns %0 on success and a negative error code on failure.
506 int ubifs_log_post_commit(struct ubifs_info
*c
, int old_ltail_lnum
)
510 while (!list_empty(&c
->old_buds
)) {
511 struct ubifs_bud
*bud
;
513 bud
= list_entry(c
->old_buds
.next
, struct ubifs_bud
, list
);
514 err
= ubifs_return_leb(c
, bud
->lnum
);
517 list_del(&bud
->list
);
520 mutex_lock(&c
->log_mutex
);
521 for (lnum
= old_ltail_lnum
; lnum
!= c
->ltail_lnum
;
522 lnum
= ubifs_next_log_lnum(c
, lnum
)) {
523 dbg_log("unmap log LEB %d", lnum
);
524 err
= ubifs_leb_unmap(c
, lnum
);
529 mutex_unlock(&c
->log_mutex
);
534 * struct done_ref - references that have been done.
544 * done_already - determine if a reference has been done already.
545 * @done_tree: rb-tree to store references that have been done
546 * @lnum: LEB number of reference
548 * This function returns %1 if the reference has been done, %0 if not, otherwise
549 * a negative error code is returned.
551 static int done_already(struct rb_root
*done_tree
, int lnum
)
553 struct rb_node
**p
= &done_tree
->rb_node
, *parent
= NULL
;
558 dr
= rb_entry(parent
, struct done_ref
, rb
);
561 else if (lnum
> dr
->lnum
)
567 dr
= kzalloc(sizeof(struct done_ref
), GFP_NOFS
);
573 rb_link_node(&dr
->rb
, parent
, p
);
574 rb_insert_color(&dr
->rb
, done_tree
);
580 * destroy_done_tree - destroy the done tree.
581 * @done_tree: done tree to destroy
583 static void destroy_done_tree(struct rb_root
*done_tree
)
585 struct rb_node
*this = done_tree
->rb_node
;
590 this = this->rb_left
;
592 } else if (this->rb_right
) {
593 this = this->rb_right
;
596 dr
= rb_entry(this, struct done_ref
, rb
);
597 this = rb_parent(this);
599 if (this->rb_left
== &dr
->rb
)
600 this->rb_left
= NULL
;
602 this->rb_right
= NULL
;
609 * add_node - add a node to the consolidated log.
610 * @c: UBIFS file-system description object
611 * @buf: buffer to which to add
612 * @lnum: LEB number to which to write is passed and returned here
613 * @offs: offset to where to write is passed and returned here
616 * This function returns %0 on success and a negative error code on failure.
618 static int add_node(struct ubifs_info
*c
, void *buf
, int *lnum
, int *offs
,
621 struct ubifs_ch
*ch
= node
;
622 int len
= le32_to_cpu(ch
->len
), remains
= c
->leb_size
- *offs
;
625 int sz
= ALIGN(*offs
, c
->min_io_size
), err
;
627 ubifs_pad(c
, buf
+ *offs
, sz
- *offs
);
628 err
= ubifs_leb_change(c
, *lnum
, buf
, sz
, UBI_SHORTTERM
);
631 *lnum
= ubifs_next_log_lnum(c
, *lnum
);
634 memcpy(buf
+ *offs
, node
, len
);
635 *offs
+= ALIGN(len
, 8);
640 * ubifs_consolidate_log - consolidate the log.
641 * @c: UBIFS file-system description object
643 * Repeated failed commits could cause the log to be full, but at least 1 LEB is
644 * needed for commit. This function rewrites the reference nodes in the log
645 * omitting duplicates, and failed CS nodes, and leaving no gaps.
647 * This function returns %0 on success and a negative error code on failure.
649 int ubifs_consolidate_log(struct ubifs_info
*c
)
651 struct ubifs_scan_leb
*sleb
;
652 struct ubifs_scan_node
*snod
;
653 struct rb_root done_tree
= RB_ROOT
;
654 int lnum
, err
, first
= 1, write_lnum
, offs
= 0;
657 dbg_rcvry("log tail LEB %d, log head LEB %d", c
->ltail_lnum
,
659 buf
= vmalloc(c
->leb_size
);
662 lnum
= c
->ltail_lnum
;
665 sleb
= ubifs_scan(c
, lnum
, 0, c
->sbuf
, 0);
670 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
671 switch (snod
->type
) {
672 case UBIFS_REF_NODE
: {
673 struct ubifs_ref_node
*ref
= snod
->node
;
674 int ref_lnum
= le32_to_cpu(ref
->lnum
);
676 err
= done_already(&done_tree
, ref_lnum
);
680 err
= add_node(c
, buf
, &write_lnum
,
690 err
= add_node(c
, buf
, &write_lnum
, &offs
,
698 ubifs_scan_destroy(sleb
);
699 if (lnum
== c
->lhead_lnum
)
701 lnum
= ubifs_next_log_lnum(c
, lnum
);
704 int sz
= ALIGN(offs
, c
->min_io_size
);
706 ubifs_pad(c
, buf
+ offs
, sz
- offs
);
707 err
= ubifs_leb_change(c
, write_lnum
, buf
, sz
, UBI_SHORTTERM
);
710 offs
= ALIGN(offs
, c
->min_io_size
);
712 destroy_done_tree(&done_tree
);
714 if (write_lnum
== c
->lhead_lnum
) {
715 ubifs_err("log is too full");
718 /* Unmap remaining LEBs */
721 lnum
= ubifs_next_log_lnum(c
, lnum
);
722 err
= ubifs_leb_unmap(c
, lnum
);
725 } while (lnum
!= c
->lhead_lnum
);
726 c
->lhead_lnum
= write_lnum
;
727 c
->lhead_offs
= offs
;
728 dbg_rcvry("new log head at %d:%d", c
->lhead_lnum
, c
->lhead_offs
);
732 ubifs_scan_destroy(sleb
);
734 destroy_done_tree(&done_tree
);
739 #ifdef CONFIG_UBIFS_FS_DEBUG
742 * dbg_check_bud_bytes - make sure bud bytes calculation are all right.
743 * @c: UBIFS file-system description object
745 * This function makes sure the amount of flash space used by closed buds
746 * ('c->bud_bytes' is correct). Returns zero in case of success and %-EINVAL in
749 static int dbg_check_bud_bytes(struct ubifs_info
*c
)
752 struct ubifs_bud
*bud
;
753 long long bud_bytes
= 0;
755 if (!(ubifs_chk_flags
& UBIFS_CHK_GEN
))
758 spin_lock(&c
->buds_lock
);
759 for (i
= 0; i
< c
->jhead_cnt
; i
++)
760 list_for_each_entry(bud
, &c
->jheads
[i
].buds_list
, list
)
761 bud_bytes
+= c
->leb_size
- bud
->start
;
763 if (c
->bud_bytes
!= bud_bytes
) {
764 ubifs_err("bad bud_bytes %lld, calculated %lld",
765 c
->bud_bytes
, bud_bytes
);
768 spin_unlock(&c
->buds_lock
);
773 #endif /* CONFIG_UBIFS_FS_DEBUG */