]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/ubifs/log.c
2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * SPDX-License-Identifier: GPL-2.0+
8 * Authors: Artem Bityutskiy (Битюцкий Артём)
13 * This file is a part of UBIFS journal implementation and contains various
14 * functions which manipulate the log. The log is a fixed area on the flash
15 * which does not contain any data but refers to buds. The log is a part of the
20 #include <linux/err.h>
24 static int dbg_check_bud_bytes(struct ubifs_info
*c
);
27 * ubifs_search_bud - search bud LEB.
28 * @c: UBIFS file-system description object
29 * @lnum: logical eraseblock number to search
31 * This function searches bud LEB @lnum. Returns bud description object in case
32 * of success and %NULL if there is no bud with this LEB number.
34 struct ubifs_bud
*ubifs_search_bud(struct ubifs_info
*c
, int lnum
)
37 struct ubifs_bud
*bud
;
39 spin_lock(&c
->buds_lock
);
42 bud
= rb_entry(p
, struct ubifs_bud
, rb
);
45 else if (lnum
> bud
->lnum
)
48 spin_unlock(&c
->buds_lock
);
52 spin_unlock(&c
->buds_lock
);
57 * ubifs_get_wbuf - get the wbuf associated with a LEB, if there is one.
58 * @c: UBIFS file-system description object
59 * @lnum: logical eraseblock number to search
61 * This functions returns the wbuf for @lnum or %NULL if there is not one.
63 struct ubifs_wbuf
*ubifs_get_wbuf(struct ubifs_info
*c
, int lnum
)
66 struct ubifs_bud
*bud
;
72 spin_lock(&c
->buds_lock
);
75 bud
= rb_entry(p
, struct ubifs_bud
, rb
);
78 else if (lnum
> bud
->lnum
)
82 spin_unlock(&c
->buds_lock
);
83 return &c
->jheads
[jhead
].wbuf
;
86 spin_unlock(&c
->buds_lock
);
91 * empty_log_bytes - calculate amount of empty space in the log.
92 * @c: UBIFS file-system description object
94 static inline long long empty_log_bytes(const struct ubifs_info
*c
)
98 h
= (long long)c
->lhead_lnum
* c
->leb_size
+ c
->lhead_offs
;
99 t
= (long long)c
->ltail_lnum
* c
->leb_size
;
102 return c
->log_bytes
- h
+ t
;
105 else if (c
->lhead_lnum
!= c
->ltail_lnum
)
112 * ubifs_add_bud - add bud LEB to the tree of buds and its journal head list.
113 * @c: UBIFS file-system description object
114 * @bud: the bud to add
116 void ubifs_add_bud(struct ubifs_info
*c
, struct ubifs_bud
*bud
)
118 struct rb_node
**p
, *parent
= NULL
;
120 struct ubifs_jhead
*jhead
;
122 spin_lock(&c
->buds_lock
);
123 p
= &c
->buds
.rb_node
;
126 b
= rb_entry(parent
, struct ubifs_bud
, rb
);
127 ubifs_assert(bud
->lnum
!= b
->lnum
);
128 if (bud
->lnum
< b
->lnum
)
134 rb_link_node(&bud
->rb
, parent
, p
);
135 rb_insert_color(&bud
->rb
, &c
->buds
);
137 jhead
= &c
->jheads
[bud
->jhead
];
138 list_add_tail(&bud
->list
, &jhead
->buds_list
);
140 ubifs_assert(c
->replaying
&& c
->ro_mount
);
143 * Note, although this is a new bud, we anyway account this space now,
144 * before any data has been written to it, because this is about to
145 * guarantee fixed mount time, and this bud will anyway be read and
148 c
->bud_bytes
+= c
->leb_size
- bud
->start
;
150 dbg_log("LEB %d:%d, jhead %s, bud_bytes %lld", bud
->lnum
,
151 bud
->start
, dbg_jhead(bud
->jhead
), c
->bud_bytes
);
152 spin_unlock(&c
->buds_lock
);
156 * ubifs_add_bud_to_log - add a new bud to the log.
157 * @c: UBIFS file-system description object
158 * @jhead: journal head the bud belongs to
159 * @lnum: LEB number of the bud
160 * @offs: starting offset of the bud
162 * This function writes reference node for the new bud LEB @lnum it to the log,
163 * and adds it to the buds tress. It also makes sure that log size does not
164 * exceed the 'c->max_bud_bytes' limit. Returns zero in case of success,
165 * %-EAGAIN if commit is required, and a negative error codes in case of
168 int ubifs_add_bud_to_log(struct ubifs_info
*c
, int jhead
, int lnum
, int offs
)
171 struct ubifs_bud
*bud
;
172 struct ubifs_ref_node
*ref
;
174 bud
= kmalloc(sizeof(struct ubifs_bud
), GFP_NOFS
);
177 ref
= kzalloc(c
->ref_node_alsz
, GFP_NOFS
);
183 mutex_lock(&c
->log_mutex
);
184 ubifs_assert(!c
->ro_media
&& !c
->ro_mount
);
190 /* Make sure we have enough space in the log */
191 if (empty_log_bytes(c
) - c
->ref_node_alsz
< c
->min_log_bytes
) {
192 dbg_log("not enough log space - %lld, required %d",
193 empty_log_bytes(c
), c
->min_log_bytes
);
194 ubifs_commit_required(c
);
200 * Make sure the amount of space in buds will not exceed the
201 * 'c->max_bud_bytes' limit, because we want to guarantee mount time
204 * It is not necessary to hold @c->buds_lock when reading @c->bud_bytes
205 * because we are holding @c->log_mutex. All @c->bud_bytes take place
206 * when both @c->log_mutex and @c->bud_bytes are locked.
208 if (c
->bud_bytes
+ c
->leb_size
- offs
> c
->max_bud_bytes
) {
209 dbg_log("bud bytes %lld (%lld max), require commit",
210 c
->bud_bytes
, c
->max_bud_bytes
);
211 ubifs_commit_required(c
);
217 * If the journal is full enough - start background commit. Note, it is
218 * OK to read 'c->cmt_state' without spinlock because integer reads
219 * are atomic in the kernel.
221 if (c
->bud_bytes
>= c
->bg_bud_bytes
&&
222 c
->cmt_state
== COMMIT_RESTING
) {
223 dbg_log("bud bytes %lld (%lld max), initiate BG commit",
224 c
->bud_bytes
, c
->max_bud_bytes
);
225 ubifs_request_bg_commit(c
);
232 ref
->ch
.node_type
= UBIFS_REF_NODE
;
233 ref
->lnum
= cpu_to_le32(bud
->lnum
);
234 ref
->offs
= cpu_to_le32(bud
->start
);
235 ref
->jhead
= cpu_to_le32(jhead
);
237 if (c
->lhead_offs
> c
->leb_size
- c
->ref_node_alsz
) {
238 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
239 ubifs_assert(c
->lhead_lnum
!= c
->ltail_lnum
);
243 if (c
->lhead_offs
== 0) {
244 /* Must ensure next log LEB has been unmapped */
245 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
250 if (bud
->start
== 0) {
252 * Before writing the LEB reference which refers an empty LEB
253 * to the log, we have to make sure it is mapped, because
254 * otherwise we'd risk to refer an LEB with garbage in case of
255 * an unclean reboot, because the target LEB might have been
256 * unmapped, but not yet physically erased.
258 err
= ubifs_leb_map(c
, bud
->lnum
);
263 dbg_log("write ref LEB %d:%d",
264 c
->lhead_lnum
, c
->lhead_offs
);
265 err
= ubifs_write_node(c
, ref
, UBIFS_REF_NODE_SZ
, c
->lhead_lnum
,
270 c
->lhead_offs
+= c
->ref_node_alsz
;
272 ubifs_add_bud(c
, bud
);
274 mutex_unlock(&c
->log_mutex
);
279 mutex_unlock(&c
->log_mutex
);
286 * remove_buds - remove used buds.
287 * @c: UBIFS file-system description object
289 * This function removes use buds from the buds tree. It does not remove the
290 * buds which are pointed to by journal heads.
292 static void remove_buds(struct ubifs_info
*c
)
296 ubifs_assert(list_empty(&c
->old_buds
));
297 c
->cmt_bud_bytes
= 0;
298 spin_lock(&c
->buds_lock
);
299 p
= rb_first(&c
->buds
);
301 struct rb_node
*p1
= p
;
302 struct ubifs_bud
*bud
;
303 struct ubifs_wbuf
*wbuf
;
306 bud
= rb_entry(p1
, struct ubifs_bud
, rb
);
307 wbuf
= &c
->jheads
[bud
->jhead
].wbuf
;
309 if (wbuf
->lnum
== bud
->lnum
) {
311 * Do not remove buds which are pointed to by journal
312 * heads (non-closed buds).
314 c
->cmt_bud_bytes
+= wbuf
->offs
- bud
->start
;
315 dbg_log("preserve %d:%d, jhead %s, bud bytes %d, cmt_bud_bytes %lld",
316 bud
->lnum
, bud
->start
, dbg_jhead(bud
->jhead
),
317 wbuf
->offs
- bud
->start
, c
->cmt_bud_bytes
);
318 bud
->start
= wbuf
->offs
;
320 c
->cmt_bud_bytes
+= c
->leb_size
- bud
->start
;
321 dbg_log("remove %d:%d, jhead %s, bud bytes %d, cmt_bud_bytes %lld",
322 bud
->lnum
, bud
->start
, dbg_jhead(bud
->jhead
),
323 c
->leb_size
- bud
->start
, c
->cmt_bud_bytes
);
324 rb_erase(p1
, &c
->buds
);
326 * If the commit does not finish, the recovery will need
327 * to replay the journal, in which case the old buds
328 * must be unchanged. Do not release them until post
329 * commit i.e. do not allow them to be garbage
332 list_move(&bud
->list
, &c
->old_buds
);
335 spin_unlock(&c
->buds_lock
);
339 * ubifs_log_start_commit - start commit.
340 * @c: UBIFS file-system description object
341 * @ltail_lnum: return new log tail LEB number
343 * The commit operation starts with writing "commit start" node to the log and
344 * reference nodes for all journal heads which will define new journal after
345 * the commit has been finished. The commit start and reference nodes are
346 * written in one go to the nearest empty log LEB (hence, when commit is
347 * finished UBIFS may safely unmap all the previous log LEBs). This function
348 * returns zero in case of success and a negative error code in case of
351 int ubifs_log_start_commit(struct ubifs_info
*c
, int *ltail_lnum
)
354 struct ubifs_cs_node
*cs
;
355 struct ubifs_ref_node
*ref
;
356 int err
, i
, max_len
, len
;
358 err
= dbg_check_bud_bytes(c
);
362 max_len
= UBIFS_CS_NODE_SZ
+ c
->jhead_cnt
* UBIFS_REF_NODE_SZ
;
363 max_len
= ALIGN(max_len
, c
->min_io_size
);
364 buf
= cs
= kmalloc(max_len
, GFP_NOFS
);
368 cs
->ch
.node_type
= UBIFS_CS_NODE
;
369 cs
->cmt_no
= cpu_to_le64(c
->cmt_no
);
370 ubifs_prepare_node(c
, cs
, UBIFS_CS_NODE_SZ
, 0);
373 * Note, we do not lock 'c->log_mutex' because this is the commit start
374 * phase and we are exclusively using the log. And we do not lock
375 * write-buffer because nobody can write to the file-system at this
379 len
= UBIFS_CS_NODE_SZ
;
380 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
381 int lnum
= c
->jheads
[i
].wbuf
.lnum
;
382 int offs
= c
->jheads
[i
].wbuf
.offs
;
384 if (lnum
== -1 || offs
== c
->leb_size
)
387 dbg_log("add ref to LEB %d:%d for jhead %s",
388 lnum
, offs
, dbg_jhead(i
));
390 ref
->ch
.node_type
= UBIFS_REF_NODE
;
391 ref
->lnum
= cpu_to_le32(lnum
);
392 ref
->offs
= cpu_to_le32(offs
);
393 ref
->jhead
= cpu_to_le32(i
);
395 ubifs_prepare_node(c
, ref
, UBIFS_REF_NODE_SZ
, 0);
396 len
+= UBIFS_REF_NODE_SZ
;
399 ubifs_pad(c
, buf
+ len
, ALIGN(len
, c
->min_io_size
) - len
);
401 /* Switch to the next log LEB */
403 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
404 ubifs_assert(c
->lhead_lnum
!= c
->ltail_lnum
);
408 /* Must ensure next LEB has been unmapped */
409 err
= ubifs_leb_unmap(c
, c
->lhead_lnum
);
413 len
= ALIGN(len
, c
->min_io_size
);
414 dbg_log("writing commit start at LEB %d:0, len %d", c
->lhead_lnum
, len
);
415 err
= ubifs_leb_write(c
, c
->lhead_lnum
, cs
, 0, len
);
419 *ltail_lnum
= c
->lhead_lnum
;
421 c
->lhead_offs
+= len
;
422 if (c
->lhead_offs
== c
->leb_size
) {
423 c
->lhead_lnum
= ubifs_next_log_lnum(c
, c
->lhead_lnum
);
430 * We have started the commit and now users may use the rest of the log
433 c
->min_log_bytes
= 0;
441 * ubifs_log_end_commit - end commit.
442 * @c: UBIFS file-system description object
443 * @ltail_lnum: new log tail LEB number
445 * This function is called on when the commit operation was finished. It
446 * moves log tail to new position and updates the master node so that it stores
447 * the new log tail LEB number. Returns zero in case of success and a negative
448 * error code in case of failure.
450 int ubifs_log_end_commit(struct ubifs_info
*c
, int ltail_lnum
)
455 * At this phase we have to lock 'c->log_mutex' because UBIFS allows FS
456 * writes during commit. Its only short "commit" start phase when
457 * writers are blocked.
459 mutex_lock(&c
->log_mutex
);
461 dbg_log("old tail was LEB %d:0, new tail is LEB %d:0",
462 c
->ltail_lnum
, ltail_lnum
);
464 c
->ltail_lnum
= ltail_lnum
;
466 * The commit is finished and from now on it must be guaranteed that
467 * there is always enough space for the next commit.
469 c
->min_log_bytes
= c
->leb_size
;
471 spin_lock(&c
->buds_lock
);
472 c
->bud_bytes
-= c
->cmt_bud_bytes
;
473 spin_unlock(&c
->buds_lock
);
475 err
= dbg_check_bud_bytes(c
);
479 err
= ubifs_write_master(c
);
482 mutex_unlock(&c
->log_mutex
);
487 * ubifs_log_post_commit - things to do after commit is completed.
488 * @c: UBIFS file-system description object
489 * @old_ltail_lnum: old log tail LEB number
491 * Release buds only after commit is completed, because they must be unchanged
492 * if recovery is needed.
494 * Unmap log LEBs only after commit is completed, because they may be needed for
497 * This function returns %0 on success and a negative error code on failure.
499 int ubifs_log_post_commit(struct ubifs_info
*c
, int old_ltail_lnum
)
503 while (!list_empty(&c
->old_buds
)) {
504 struct ubifs_bud
*bud
;
506 bud
= list_entry(c
->old_buds
.next
, struct ubifs_bud
, list
);
507 err
= ubifs_return_leb(c
, bud
->lnum
);
510 list_del(&bud
->list
);
513 mutex_lock(&c
->log_mutex
);
514 for (lnum
= old_ltail_lnum
; lnum
!= c
->ltail_lnum
;
515 lnum
= ubifs_next_log_lnum(c
, lnum
)) {
516 dbg_log("unmap log LEB %d", lnum
);
517 err
= ubifs_leb_unmap(c
, lnum
);
522 mutex_unlock(&c
->log_mutex
);
527 * struct done_ref - references that have been done.
537 * done_already - determine if a reference has been done already.
538 * @done_tree: rb-tree to store references that have been done
539 * @lnum: LEB number of reference
541 * This function returns %1 if the reference has been done, %0 if not, otherwise
542 * a negative error code is returned.
544 static int done_already(struct rb_root
*done_tree
, int lnum
)
546 struct rb_node
**p
= &done_tree
->rb_node
, *parent
= NULL
;
551 dr
= rb_entry(parent
, struct done_ref
, rb
);
554 else if (lnum
> dr
->lnum
)
560 dr
= kzalloc(sizeof(struct done_ref
), GFP_NOFS
);
566 rb_link_node(&dr
->rb
, parent
, p
);
567 rb_insert_color(&dr
->rb
, done_tree
);
573 * destroy_done_tree - destroy the done tree.
574 * @done_tree: done tree to destroy
576 static void destroy_done_tree(struct rb_root
*done_tree
)
578 struct done_ref
*dr
, *n
;
580 rbtree_postorder_for_each_entry_safe(dr
, n
, done_tree
, rb
)
585 * add_node - add a node to the consolidated log.
586 * @c: UBIFS file-system description object
587 * @buf: buffer to which to add
588 * @lnum: LEB number to which to write is passed and returned here
589 * @offs: offset to where to write is passed and returned here
592 * This function returns %0 on success and a negative error code on failure.
594 static int add_node(struct ubifs_info
*c
, void *buf
, int *lnum
, int *offs
,
597 struct ubifs_ch
*ch
= node
;
598 int len
= le32_to_cpu(ch
->len
), remains
= c
->leb_size
- *offs
;
601 int sz
= ALIGN(*offs
, c
->min_io_size
), err
;
603 ubifs_pad(c
, buf
+ *offs
, sz
- *offs
);
604 err
= ubifs_leb_change(c
, *lnum
, buf
, sz
);
607 *lnum
= ubifs_next_log_lnum(c
, *lnum
);
610 memcpy(buf
+ *offs
, node
, len
);
611 *offs
+= ALIGN(len
, 8);
616 * ubifs_consolidate_log - consolidate the log.
617 * @c: UBIFS file-system description object
619 * Repeated failed commits could cause the log to be full, but at least 1 LEB is
620 * needed for commit. This function rewrites the reference nodes in the log
621 * omitting duplicates, and failed CS nodes, and leaving no gaps.
623 * This function returns %0 on success and a negative error code on failure.
625 int ubifs_consolidate_log(struct ubifs_info
*c
)
627 struct ubifs_scan_leb
*sleb
;
628 struct ubifs_scan_node
*snod
;
629 struct rb_root done_tree
= RB_ROOT
;
630 int lnum
, err
, first
= 1, write_lnum
, offs
= 0;
633 dbg_rcvry("log tail LEB %d, log head LEB %d", c
->ltail_lnum
,
635 buf
= vmalloc(c
->leb_size
);
638 lnum
= c
->ltail_lnum
;
641 sleb
= ubifs_scan(c
, lnum
, 0, c
->sbuf
, 0);
646 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
647 switch (snod
->type
) {
648 case UBIFS_REF_NODE
: {
649 struct ubifs_ref_node
*ref
= snod
->node
;
650 int ref_lnum
= le32_to_cpu(ref
->lnum
);
652 err
= done_already(&done_tree
, ref_lnum
);
656 err
= add_node(c
, buf
, &write_lnum
,
666 err
= add_node(c
, buf
, &write_lnum
, &offs
,
674 ubifs_scan_destroy(sleb
);
675 if (lnum
== c
->lhead_lnum
)
677 lnum
= ubifs_next_log_lnum(c
, lnum
);
680 int sz
= ALIGN(offs
, c
->min_io_size
);
682 ubifs_pad(c
, buf
+ offs
, sz
- offs
);
683 err
= ubifs_leb_change(c
, write_lnum
, buf
, sz
);
686 offs
= ALIGN(offs
, c
->min_io_size
);
688 destroy_done_tree(&done_tree
);
690 if (write_lnum
== c
->lhead_lnum
) {
691 ubifs_err(c
, "log is too full");
694 /* Unmap remaining LEBs */
697 lnum
= ubifs_next_log_lnum(c
, lnum
);
698 err
= ubifs_leb_unmap(c
, lnum
);
701 } while (lnum
!= c
->lhead_lnum
);
702 c
->lhead_lnum
= write_lnum
;
703 c
->lhead_offs
= offs
;
704 dbg_rcvry("new log head at %d:%d", c
->lhead_lnum
, c
->lhead_offs
);
708 ubifs_scan_destroy(sleb
);
710 destroy_done_tree(&done_tree
);
716 * dbg_check_bud_bytes - make sure bud bytes calculation are all right.
717 * @c: UBIFS file-system description object
719 * This function makes sure the amount of flash space used by closed buds
720 * ('c->bud_bytes' is correct). Returns zero in case of success and %-EINVAL in
723 static int dbg_check_bud_bytes(struct ubifs_info
*c
)
726 struct ubifs_bud
*bud
;
727 long long bud_bytes
= 0;
729 if (!dbg_is_chk_gen(c
))
732 spin_lock(&c
->buds_lock
);
733 for (i
= 0; i
< c
->jhead_cnt
; i
++)
734 list_for_each_entry(bud
, &c
->jheads
[i
].buds_list
, list
)
735 bud_bytes
+= c
->leb_size
- bud
->start
;
737 if (c
->bud_bytes
!= bud_bytes
) {
738 ubifs_err(c
, "bad bud_bytes %lld, calculated %lld",
739 c
->bud_bytes
, bud_bytes
);
742 spin_unlock(&c
->buds_lock
);