blob: 4378baa6694b11cc092f63509a8251e475b8f3d0 [file] [log] [blame]
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001/*
2 * This file is part of UBIFS.
3 *
4 * Copyright (C) 2006-2008 Nokia Corporation.
5 *
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.
9 *
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
13 * more details.
14 *
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
18 *
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
21 */
22
23/*
24 * This file contains journal replay code. It runs when the file-system is being
25 * mounted and requires no locking.
26 *
27 * The larger is the journal, the longer it takes to scan it, so the longer it
28 * takes to mount UBIFS. This is why the journal has limited size which may be
29 * changed depending on the system requirements. But a larger journal gives
30 * faster I/O speed because it writes the index less frequently. So this is a
31 * trade-off. Also, the journal is indexed by the in-memory index (TNC), so the
32 * larger is the journal, the more memory its index may consume.
33 */
34
35#include "ubifs.h"
Artem Bityutskiydebf12d2011-05-15 12:05:54 +030036#include <linux/list_sort.h>
Artem Bityutskiy1e517642008-07-14 19:08:37 +030037
Artem Bityutskiy1e517642008-07-14 19:08:37 +030038/**
Artem Bityutskiydebf12d2011-05-15 12:05:54 +030039 * struct replay_entry - replay list entry.
Artem Bityutskiy1e517642008-07-14 19:08:37 +030040 * @lnum: logical eraseblock number of the node
41 * @offs: node offset
42 * @len: node length
Artem Bityutskiy074bcb92011-05-15 11:37:17 +030043 * @deletion: non-zero if this entry corresponds to a node deletion
Artem Bityutskiy1e517642008-07-14 19:08:37 +030044 * @sqnum: node sequence number
Artem Bityutskiydebf12d2011-05-15 12:05:54 +030045 * @list: links the replay list
Artem Bityutskiy1e517642008-07-14 19:08:37 +030046 * @key: node key
47 * @nm: directory entry name
48 * @old_size: truncation old size
49 * @new_size: truncation new size
Artem Bityutskiy1e517642008-07-14 19:08:37 +030050 *
Artem Bityutskiydebf12d2011-05-15 12:05:54 +030051 * The replay process first scans all buds and builds the replay list, then
52 * sorts the replay list in nodes sequence number order, and then inserts all
53 * the replay entries to the TNC.
Artem Bityutskiy1e517642008-07-14 19:08:37 +030054 */
55struct replay_entry {
56 int lnum;
57 int offs;
58 int len;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +030059 unsigned int deletion:1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +030060 unsigned long long sqnum;
Artem Bityutskiydebf12d2011-05-15 12:05:54 +030061 struct list_head list;
Artem Bityutskiy1e517642008-07-14 19:08:37 +030062 union ubifs_key key;
63 union {
64 struct qstr nm;
65 struct {
66 loff_t old_size;
67 loff_t new_size;
68 };
Artem Bityutskiy1e517642008-07-14 19:08:37 +030069 };
70};
71
72/**
73 * struct bud_entry - entry in the list of buds to replay.
74 * @list: next bud in the list
75 * @bud: bud description object
Artem Bityutskiy1e517642008-07-14 19:08:37 +030076 * @sqnum: reference node sequence number
Artem Bityutskiyaf1dd412011-05-15 11:14:57 +030077 * @free: free bytes in the bud
78 * @dirty: dirty bytes in the bud
Artem Bityutskiy1e517642008-07-14 19:08:37 +030079 */
80struct bud_entry {
81 struct list_head list;
82 struct ubifs_bud *bud;
Artem Bityutskiy1e517642008-07-14 19:08:37 +030083 unsigned long long sqnum;
Artem Bityutskiyaf1dd412011-05-15 11:14:57 +030084 int free;
85 int dirty;
Artem Bityutskiy1e517642008-07-14 19:08:37 +030086};
87
88/**
89 * set_bud_lprops - set free and dirty space used by a bud.
90 * @c: UBIFS file-system description object
Artem Bityutskiy074bcb92011-05-15 11:37:17 +030091 * @b: bud entry which describes the bud
92 *
93 * This function makes sure the LEB properties of bud @b are set correctly
94 * after the replay. Returns zero in case of success and a negative error code
95 * in case of failure.
Artem Bityutskiy1e517642008-07-14 19:08:37 +030096 */
Artem Bityutskiy074bcb92011-05-15 11:37:17 +030097static int set_bud_lprops(struct ubifs_info *c, struct bud_entry *b)
Artem Bityutskiy1e517642008-07-14 19:08:37 +030098{
99 const struct ubifs_lprops *lp;
100 int err = 0, dirty;
101
102 ubifs_get_lprops(c);
103
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300104 lp = ubifs_lpt_lookup_dirty(c, b->bud->lnum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300105 if (IS_ERR(lp)) {
106 err = PTR_ERR(lp);
107 goto out;
108 }
109
110 dirty = lp->dirty;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300111 if (b->bud->start == 0 && (lp->free != c->leb_size || lp->dirty != 0)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300112 /*
113 * The LEB was added to the journal with a starting offset of
114 * zero which means the LEB must have been empty. The LEB
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300115 * property values should be @lp->free == @c->leb_size and
116 * @lp->dirty == 0, but that is not the case. The reason is that
Artem Bityutskiy7a9c3e32011-05-13 13:02:00 +0300117 * the LEB had been garbage collected before it became the bud,
118 * and there was not commit inbetween. The garbage collector
119 * resets the free and dirty space without recording it
120 * anywhere except lprops, so if there was no commit then
121 * lprops does not have that information.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300122 *
123 * We do not need to adjust free space because the scan has told
124 * us the exact value which is recorded in the replay entry as
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300125 * @b->free.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300126 *
127 * However we do need to subtract from the dirty space the
128 * amount of space that the garbage collector reclaimed, which
129 * is the whole LEB minus the amount of space that was free.
130 */
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300131 dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300132 lp->free, lp->dirty);
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300133 dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300134 lp->free, lp->dirty);
135 dirty -= c->leb_size - lp->free;
136 /*
137 * If the replay order was perfect the dirty space would now be
Artem Bityutskiy7d4e9cc2009-03-20 19:11:12 +0200138 * zero. The order is not perfect because the journal heads
Artem Bityutskiy6edbfaf2008-12-30 20:06:49 +0200139 * race with each other. This is not a problem but is does mean
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300140 * that the dirty space may temporarily exceed c->leb_size
141 * during the replay.
142 */
143 if (dirty != 0)
144 dbg_msg("LEB %d lp: %d free %d dirty "
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300145 "replay: %d free %d dirty", b->bud->lnum,
146 lp->free, lp->dirty, b->free, b->dirty);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300147 }
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300148 lp = ubifs_change_lp(c, lp, b->free, dirty + b->dirty,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300149 lp->flags | LPROPS_TAKEN, 0);
150 if (IS_ERR(lp)) {
151 err = PTR_ERR(lp);
152 goto out;
153 }
Artem Bityutskiy52c6e6f2011-04-25 18:46:31 +0300154
155 /* Make sure the journal head points to the latest bud */
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300156 err = ubifs_wbuf_seek_nolock(&c->jheads[b->bud->jhead].wbuf,
157 b->bud->lnum, c->leb_size - b->free,
158 UBI_SHORTTERM);
Artem Bityutskiy52c6e6f2011-04-25 18:46:31 +0300159
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300160out:
161 ubifs_release_lprops(c);
162 return err;
163}
164
165/**
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300166 * set_buds_lprops - set free and dirty space for all replayed buds.
167 * @c: UBIFS file-system description object
168 *
169 * This function sets LEB properties for all replayed buds. Returns zero in
170 * case of success and a negative error code in case of failure.
171 */
172static int set_buds_lprops(struct ubifs_info *c)
173{
174 struct bud_entry *b;
175 int err;
176
177 list_for_each_entry(b, &c->replay_buds, list) {
178 err = set_bud_lprops(c, b);
179 if (err)
180 return err;
181 }
182
183 return 0;
184}
185
186/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300187 * trun_remove_range - apply a replay entry for a truncation to the TNC.
188 * @c: UBIFS file-system description object
189 * @r: replay entry of truncation
190 */
191static int trun_remove_range(struct ubifs_info *c, struct replay_entry *r)
192{
193 unsigned min_blk, max_blk;
194 union ubifs_key min_key, max_key;
195 ino_t ino;
196
197 min_blk = r->new_size / UBIFS_BLOCK_SIZE;
198 if (r->new_size & (UBIFS_BLOCK_SIZE - 1))
199 min_blk += 1;
200
201 max_blk = r->old_size / UBIFS_BLOCK_SIZE;
202 if ((r->old_size & (UBIFS_BLOCK_SIZE - 1)) == 0)
203 max_blk -= 1;
204
205 ino = key_inum(c, &r->key);
206
207 data_key_init(c, &min_key, ino, min_blk);
208 data_key_init(c, &max_key, ino, max_blk);
209
210 return ubifs_tnc_remove_range(c, &min_key, &max_key);
211}
212
213/**
214 * apply_replay_entry - apply a replay entry to the TNC.
215 * @c: UBIFS file-system description object
216 * @r: replay entry to apply
217 *
218 * Apply a replay entry to the TNC.
219 */
220static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
221{
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300222 int err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300223
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300224 dbg_mnt("LEB %d:%d len %d deletion %d sqnum %llu %s", r->lnum,
225 r->offs, r->len, r->deletion, r->sqnum, DBGKEY(&r->key));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300226
227 /* Set c->replay_sqnum to help deal with dangling branches. */
228 c->replay_sqnum = r->sqnum;
229
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300230 if (is_hash_key(c, &r->key)) {
231 if (r->deletion)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300232 err = ubifs_tnc_remove_nm(c, &r->key, &r->nm);
233 else
234 err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs,
235 r->len, &r->nm);
236 } else {
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300237 if (r->deletion)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300238 switch (key_type(c, &r->key)) {
239 case UBIFS_INO_KEY:
240 {
241 ino_t inum = key_inum(c, &r->key);
242
243 err = ubifs_tnc_remove_ino(c, inum);
244 break;
245 }
246 case UBIFS_TRUN_KEY:
247 err = trun_remove_range(c, r);
248 break;
249 default:
250 err = ubifs_tnc_remove(c, &r->key);
251 break;
252 }
253 else
254 err = ubifs_tnc_add(c, &r->key, r->lnum, r->offs,
255 r->len);
256 if (err)
257 return err;
258
259 if (c->need_recovery)
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300260 err = ubifs_recover_size_accum(c, &r->key, r->deletion,
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300261 r->new_size);
262 }
263
264 return err;
265}
266
267/**
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300268 * replay_entries_cmp - compare 2 replay entries.
269 * @priv: UBIFS file-system description object
270 * @a: first replay entry
271 * @a: second replay entry
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300272 *
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300273 * This is a comparios function for 'list_sort()' which compares 2 replay
274 * entries @a and @b by comparing their sequence numer. Returns %1 if @a has
275 * greater sequence number and %-1 otherwise.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300276 */
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300277static int replay_entries_cmp(void *priv, struct list_head *a,
278 struct list_head *b)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300279{
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300280 struct replay_entry *ra, *rb;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300281
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300282 cond_resched();
283 if (a == b)
284 return 0;
285
286 ra = list_entry(a, struct replay_entry, list);
287 rb = list_entry(b, struct replay_entry, list);
288 ubifs_assert(ra->sqnum != rb->sqnum);
289 if (ra->sqnum > rb->sqnum)
290 return 1;
291 return -1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300292}
293
294/**
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300295 * apply_replay_list - apply the replay list to the TNC.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300296 * @c: UBIFS file-system description object
297 *
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300298 * Apply all entries in the replay list to the TNC. Returns zero in case of
299 * success and a negative error code in case of failure.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300300 */
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300301static int apply_replay_list(struct ubifs_info *c)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300302{
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300303 struct replay_entry *r;
304 int err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300305
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300306 list_sort(c, &c->replay_list, &replay_entries_cmp);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300307
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300308 list_for_each_entry(r, &c->replay_list, list) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300309 cond_resched();
310
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300311 err = apply_replay_entry(c, r);
312 if (err)
313 return err;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300314 }
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300315
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300316 return 0;
317}
318
319/**
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300320 * destroy_replay_list - destroy the replay.
321 * @c: UBIFS file-system description object
322 *
323 * Destroy the replay list.
324 */
325static void destroy_replay_list(struct ubifs_info *c)
326{
327 struct replay_entry *r, *tmp;
328
329 list_for_each_entry_safe(r, tmp, &c->replay_list, list) {
330 if (is_hash_key(c, &r->key))
331 kfree(r->nm.name);
332 list_del(&r->list);
333 kfree(r);
334 }
335}
336
337/**
338 * insert_node - insert a node to the replay list
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300339 * @c: UBIFS file-system description object
340 * @lnum: node logical eraseblock number
341 * @offs: node offset
342 * @len: node length
343 * @key: node key
344 * @sqnum: sequence number
345 * @deletion: non-zero if this is a deletion
346 * @used: number of bytes in use in a LEB
347 * @old_size: truncation old size
348 * @new_size: truncation new size
349 *
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300350 * This function inserts a scanned non-direntry node to the replay list. The
351 * replay list contains @struct replay_entry elements, and we sort this list in
352 * sequence number order before applying it. The replay list is applied at the
353 * very end of the replay process. Since the list is sorted in sequence number
354 * order, the older modifications are applied first. This function returns zero
355 * in case of success and a negative error code in case of failure.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300356 */
357static int insert_node(struct ubifs_info *c, int lnum, int offs, int len,
358 union ubifs_key *key, unsigned long long sqnum,
359 int deletion, int *used, loff_t old_size,
360 loff_t new_size)
361{
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300362 struct replay_entry *r;
363
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300364 dbg_mnt("add LEB %d:%d, key %s", lnum, offs, DBGKEY(key));
365
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300366 if (key_inum(c, key) >= c->highest_inum)
367 c->highest_inum = key_inum(c, key);
368
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300369 r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
370 if (!r)
371 return -ENOMEM;
372
373 if (!deletion)
374 *used += ALIGN(len, 8);
375 r->lnum = lnum;
376 r->offs = offs;
377 r->len = len;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300378 r->deletion = !!deletion;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300379 r->sqnum = sqnum;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300380 key_copy(c, key, &r->key);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300381 r->old_size = old_size;
382 r->new_size = new_size;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300383
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300384 list_add_tail(&r->list, &c->replay_list);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300385 return 0;
386}
387
388/**
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300389 * insert_dent - insert a directory entry node into the replay list.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300390 * @c: UBIFS file-system description object
391 * @lnum: node logical eraseblock number
392 * @offs: node offset
393 * @len: node length
394 * @key: node key
395 * @name: directory entry name
396 * @nlen: directory entry name length
397 * @sqnum: sequence number
398 * @deletion: non-zero if this is a deletion
399 * @used: number of bytes in use in a LEB
400 *
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300401 * This function inserts a scanned directory entry node or an extended
402 * attribute entry to the replay list. Returns zero in case of success and a
403 * negative error code in case of failure.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300404 */
405static int insert_dent(struct ubifs_info *c, int lnum, int offs, int len,
406 union ubifs_key *key, const char *name, int nlen,
407 unsigned long long sqnum, int deletion, int *used)
408{
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300409 struct replay_entry *r;
410 char *nbuf;
411
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300412 dbg_mnt("add LEB %d:%d, key %s", lnum, offs, DBGKEY(key));
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300413 if (key_inum(c, key) >= c->highest_inum)
414 c->highest_inum = key_inum(c, key);
415
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300416 r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
417 if (!r)
418 return -ENOMEM;
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300419
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300420 nbuf = kmalloc(nlen + 1, GFP_KERNEL);
421 if (!nbuf) {
422 kfree(r);
423 return -ENOMEM;
424 }
425
426 if (!deletion)
427 *used += ALIGN(len, 8);
428 r->lnum = lnum;
429 r->offs = offs;
430 r->len = len;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300431 r->deletion = !!deletion;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300432 r->sqnum = sqnum;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300433 key_copy(c, key, &r->key);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300434 r->nm.len = nlen;
435 memcpy(nbuf, name, nlen);
436 nbuf[nlen] = '\0';
437 r->nm.name = nbuf;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300438
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300439 list_add_tail(&r->list, &c->replay_list);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300440 return 0;
441}
442
443/**
444 * ubifs_validate_entry - validate directory or extended attribute entry node.
445 * @c: UBIFS file-system description object
446 * @dent: the node to validate
447 *
448 * This function validates directory or extended attribute entry node @dent.
449 * Returns zero if the node is all right and a %-EINVAL if not.
450 */
451int ubifs_validate_entry(struct ubifs_info *c,
452 const struct ubifs_dent_node *dent)
453{
454 int key_type = key_type_flash(c, dent->key);
455 int nlen = le16_to_cpu(dent->nlen);
456
457 if (le32_to_cpu(dent->ch.len) != nlen + UBIFS_DENT_NODE_SZ + 1 ||
458 dent->type >= UBIFS_ITYPES_CNT ||
459 nlen > UBIFS_MAX_NLEN || dent->name[nlen] != 0 ||
460 strnlen(dent->name, nlen) != nlen ||
461 le64_to_cpu(dent->inum) > MAX_INUM) {
462 ubifs_err("bad %s node", key_type == UBIFS_DENT_KEY ?
463 "directory entry" : "extended attribute entry");
464 return -EINVAL;
465 }
466
467 if (key_type != UBIFS_DENT_KEY && key_type != UBIFS_XENT_KEY) {
468 ubifs_err("bad key type %d", key_type);
469 return -EINVAL;
470 }
471
472 return 0;
473}
474
475/**
476 * replay_bud - replay a bud logical eraseblock.
477 * @c: UBIFS file-system description object
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300478 * @b: bud entry which describes the bud
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300479 *
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300480 * This function replays bud @bud, recovers it if needed, and adds all nodes
481 * from this bud to the replay list. Returns zero in case of success and a
482 * negative error code in case of failure.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300483 */
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300484static int replay_bud(struct ubifs_info *c, struct bud_entry *b)
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300485{
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300486 int err = 0, used = 0, lnum = b->bud->lnum, offs = b->bud->start;
487 int jhead = b->bud->jhead;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300488 struct ubifs_scan_leb *sleb;
489 struct ubifs_scan_node *snod;
490 struct ubifs_bud *bud;
491
Artem Bityutskiyc839e292011-05-13 12:26:54 +0300492 dbg_mnt("replay bud LEB %d, head %d, offs %d", lnum, jhead, offs);
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300493
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300494 if (c->need_recovery)
495 sleb = ubifs_recover_leb(c, lnum, offs, c->sbuf, jhead != GCHD);
496 else
Artem Bityutskiy348709b2009-08-25 15:00:55 +0300497 sleb = ubifs_scan(c, lnum, offs, c->sbuf, 0);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300498 if (IS_ERR(sleb))
499 return PTR_ERR(sleb);
500
501 /*
502 * The bud does not have to start from offset zero - the beginning of
503 * the 'lnum' LEB may contain previously committed data. One of the
504 * things we have to do in replay is to correctly update lprops with
505 * newer information about this LEB.
506 *
507 * At this point lprops thinks that this LEB has 'c->leb_size - offs'
508 * bytes of free space because it only contain information about
509 * committed data.
510 *
511 * But we know that real amount of free space is 'c->leb_size -
512 * sleb->endpt', and the space in the 'lnum' LEB between 'offs' and
513 * 'sleb->endpt' is used by bud data. We have to correctly calculate
514 * how much of these data are dirty and update lprops with this
515 * information.
516 *
517 * The dirt in that LEB region is comprised of padding nodes, deletion
518 * nodes, truncation nodes and nodes which are obsoleted by subsequent
519 * nodes in this LEB. So instead of calculating clean space, we
520 * calculate used space ('used' variable).
521 */
522
523 list_for_each_entry(snod, &sleb->nodes, list) {
524 int deletion = 0;
525
526 cond_resched();
527
528 if (snod->sqnum >= SQNUM_WATERMARK) {
529 ubifs_err("file system's life ended");
530 goto out_dump;
531 }
532
533 if (snod->sqnum > c->max_sqnum)
534 c->max_sqnum = snod->sqnum;
535
536 switch (snod->type) {
537 case UBIFS_INO_NODE:
538 {
539 struct ubifs_ino_node *ino = snod->node;
540 loff_t new_size = le64_to_cpu(ino->size);
541
542 if (le32_to_cpu(ino->nlink) == 0)
543 deletion = 1;
544 err = insert_node(c, lnum, snod->offs, snod->len,
545 &snod->key, snod->sqnum, deletion,
546 &used, 0, new_size);
547 break;
548 }
549 case UBIFS_DATA_NODE:
550 {
551 struct ubifs_data_node *dn = snod->node;
552 loff_t new_size = le32_to_cpu(dn->size) +
553 key_block(c, &snod->key) *
554 UBIFS_BLOCK_SIZE;
555
556 err = insert_node(c, lnum, snod->offs, snod->len,
557 &snod->key, snod->sqnum, deletion,
558 &used, 0, new_size);
559 break;
560 }
561 case UBIFS_DENT_NODE:
562 case UBIFS_XENT_NODE:
563 {
564 struct ubifs_dent_node *dent = snod->node;
565
566 err = ubifs_validate_entry(c, dent);
567 if (err)
568 goto out_dump;
569
570 err = insert_dent(c, lnum, snod->offs, snod->len,
571 &snod->key, dent->name,
572 le16_to_cpu(dent->nlen), snod->sqnum,
573 !le64_to_cpu(dent->inum), &used);
574 break;
575 }
576 case UBIFS_TRUN_NODE:
577 {
578 struct ubifs_trun_node *trun = snod->node;
579 loff_t old_size = le64_to_cpu(trun->old_size);
580 loff_t new_size = le64_to_cpu(trun->new_size);
581 union ubifs_key key;
582
583 /* Validate truncation node */
584 if (old_size < 0 || old_size > c->max_inode_sz ||
585 new_size < 0 || new_size > c->max_inode_sz ||
586 old_size <= new_size) {
587 ubifs_err("bad truncation node");
588 goto out_dump;
589 }
590
591 /*
592 * Create a fake truncation key just to use the same
593 * functions which expect nodes to have keys.
594 */
595 trun_key_init(c, &key, le32_to_cpu(trun->inum));
596 err = insert_node(c, lnum, snod->offs, snod->len,
597 &key, snod->sqnum, 1, &used,
598 old_size, new_size);
599 break;
600 }
601 default:
602 ubifs_err("unexpected node type %d in bud LEB %d:%d",
603 snod->type, lnum, snod->offs);
604 err = -EINVAL;
605 goto out_dump;
606 }
607 if (err)
608 goto out;
609 }
610
611 bud = ubifs_search_bud(c, lnum);
612 if (!bud)
613 BUG();
614
615 ubifs_assert(sleb->endpt - offs >= used);
616 ubifs_assert(sleb->endpt % c->min_io_size == 0);
617
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300618 b->dirty = sleb->endpt - offs - used;
619 b->free = c->leb_size - sleb->endpt;
620 dbg_mnt("bud LEB %d replied: dirty %d, free %d", lnum, b->dirty, b->free);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300621
622out:
623 ubifs_scan_destroy(sleb);
624 return err;
625
626out_dump:
627 ubifs_err("bad node is at LEB %d:%d", lnum, snod->offs);
628 dbg_dump_node(c, snod->node);
629 ubifs_scan_destroy(sleb);
630 return -EINVAL;
631}
632
633/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300634 * replay_buds - replay all buds.
635 * @c: UBIFS file-system description object
636 *
637 * This function returns zero in case of success and a negative error code in
638 * case of failure.
639 */
640static int replay_buds(struct ubifs_info *c)
641{
642 struct bud_entry *b;
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300643 int err;
Artem Bityutskiy7703f092011-05-13 16:02:19 +0300644 unsigned long long prev_sqnum = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300645
646 list_for_each_entry(b, &c->replay_buds, list) {
Artem Bityutskiye76a4522011-05-15 12:34:29 +0300647 err = replay_bud(c, b);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300648 if (err)
649 return err;
Artem Bityutskiy7703f092011-05-13 16:02:19 +0300650
651 ubifs_assert(b->sqnum > prev_sqnum);
652 prev_sqnum = b->sqnum;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300653 }
654
655 return 0;
656}
657
658/**
659 * destroy_bud_list - destroy the list of buds to replay.
660 * @c: UBIFS file-system description object
661 */
662static void destroy_bud_list(struct ubifs_info *c)
663{
664 struct bud_entry *b;
665
666 while (!list_empty(&c->replay_buds)) {
667 b = list_entry(c->replay_buds.next, struct bud_entry, list);
668 list_del(&b->list);
669 kfree(b);
670 }
671}
672
673/**
674 * add_replay_bud - add a bud to the list of buds to replay.
675 * @c: UBIFS file-system description object
676 * @lnum: bud logical eraseblock number to replay
677 * @offs: bud start offset
678 * @jhead: journal head to which this bud belongs
679 * @sqnum: reference node sequence number
680 *
681 * This function returns zero in case of success and a negative error code in
682 * case of failure.
683 */
684static int add_replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
685 unsigned long long sqnum)
686{
687 struct ubifs_bud *bud;
688 struct bud_entry *b;
689
690 dbg_mnt("add replay bud LEB %d:%d, head %d", lnum, offs, jhead);
691
692 bud = kmalloc(sizeof(struct ubifs_bud), GFP_KERNEL);
693 if (!bud)
694 return -ENOMEM;
695
696 b = kmalloc(sizeof(struct bud_entry), GFP_KERNEL);
697 if (!b) {
698 kfree(bud);
699 return -ENOMEM;
700 }
701
702 bud->lnum = lnum;
703 bud->start = offs;
704 bud->jhead = jhead;
705 ubifs_add_bud(c, bud);
706
707 b->bud = bud;
708 b->sqnum = sqnum;
709 list_add_tail(&b->list, &c->replay_buds);
710
711 return 0;
712}
713
714/**
715 * validate_ref - validate a reference node.
716 * @c: UBIFS file-system description object
717 * @ref: the reference node to validate
718 * @ref_lnum: LEB number of the reference node
719 * @ref_offs: reference node offset
720 *
721 * This function returns %1 if a bud reference already exists for the LEB. %0 is
722 * returned if the reference node is new, otherwise %-EINVAL is returned if
723 * validation failed.
724 */
725static int validate_ref(struct ubifs_info *c, const struct ubifs_ref_node *ref)
726{
727 struct ubifs_bud *bud;
728 int lnum = le32_to_cpu(ref->lnum);
729 unsigned int offs = le32_to_cpu(ref->offs);
730 unsigned int jhead = le32_to_cpu(ref->jhead);
731
732 /*
733 * ref->offs may point to the end of LEB when the journal head points
734 * to the end of LEB and we write reference node for it during commit.
735 * So this is why we require 'offs > c->leb_size'.
736 */
737 if (jhead >= c->jhead_cnt || lnum >= c->leb_cnt ||
738 lnum < c->main_first || offs > c->leb_size ||
739 offs & (c->min_io_size - 1))
740 return -EINVAL;
741
742 /* Make sure we have not already looked at this bud */
743 bud = ubifs_search_bud(c, lnum);
744 if (bud) {
745 if (bud->jhead == jhead && bud->start <= offs)
746 return 1;
747 ubifs_err("bud at LEB %d:%d was already referred", lnum, offs);
748 return -EINVAL;
749 }
750
751 return 0;
752}
753
754/**
755 * replay_log_leb - replay a log logical eraseblock.
756 * @c: UBIFS file-system description object
757 * @lnum: log logical eraseblock to replay
758 * @offs: offset to start replaying from
759 * @sbuf: scan buffer
760 *
761 * This function replays a log LEB and returns zero in case of success, %1 if
762 * this is the last LEB in the log, and a negative error code in case of
763 * failure.
764 */
765static int replay_log_leb(struct ubifs_info *c, int lnum, int offs, void *sbuf)
766{
767 int err;
768 struct ubifs_scan_leb *sleb;
769 struct ubifs_scan_node *snod;
770 const struct ubifs_cs_node *node;
771
772 dbg_mnt("replay log LEB %d:%d", lnum, offs);
Artem Bityutskiy348709b2009-08-25 15:00:55 +0300773 sleb = ubifs_scan(c, lnum, offs, sbuf, c->need_recovery);
774 if (IS_ERR(sleb)) {
Artem Bityutskiyed43f2f2009-06-29 17:59:23 +0300775 if (PTR_ERR(sleb) != -EUCLEAN || !c->need_recovery)
776 return PTR_ERR(sleb);
Artem Bityutskiy7d08ae32010-10-17 15:50:19 +0300777 /*
778 * Note, the below function will recover this log LEB only if
779 * it is the last, because unclean reboots can possibly corrupt
780 * only the tail of the log.
781 */
Artem Bityutskiyed43f2f2009-06-29 17:59:23 +0300782 sleb = ubifs_recover_log_leb(c, lnum, offs, sbuf);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300783 if (IS_ERR(sleb))
784 return PTR_ERR(sleb);
785 }
786
787 if (sleb->nodes_cnt == 0) {
788 err = 1;
789 goto out;
790 }
791
792 node = sleb->buf;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300793 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
794 if (c->cs_sqnum == 0) {
795 /*
796 * This is the first log LEB we are looking at, make sure that
797 * the first node is a commit start node. Also record its
798 * sequence number so that UBIFS can determine where the log
799 * ends, because all nodes which were have higher sequence
800 * numbers.
801 */
802 if (snod->type != UBIFS_CS_NODE) {
803 dbg_err("first log node at LEB %d:%d is not CS node",
804 lnum, offs);
805 goto out_dump;
806 }
807 if (le64_to_cpu(node->cmt_no) != c->cmt_no) {
808 dbg_err("first CS node at LEB %d:%d has wrong "
809 "commit number %llu expected %llu",
810 lnum, offs,
811 (unsigned long long)le64_to_cpu(node->cmt_no),
812 c->cmt_no);
813 goto out_dump;
814 }
815
816 c->cs_sqnum = le64_to_cpu(node->ch.sqnum);
817 dbg_mnt("commit start sqnum %llu", c->cs_sqnum);
818 }
819
820 if (snod->sqnum < c->cs_sqnum) {
821 /*
822 * This means that we reached end of log and now
823 * look to the older log data, which was already
824 * committed but the eraseblock was not erased (UBIFS
Artem Bityutskiy6edbfaf2008-12-30 20:06:49 +0200825 * only un-maps it). So this basically means we have to
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300826 * exit with "end of log" code.
827 */
828 err = 1;
829 goto out;
830 }
831
832 /* Make sure the first node sits at offset zero of the LEB */
833 if (snod->offs != 0) {
834 dbg_err("first node is not at zero offset");
835 goto out_dump;
836 }
837
838 list_for_each_entry(snod, &sleb->nodes, list) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300839 cond_resched();
840
841 if (snod->sqnum >= SQNUM_WATERMARK) {
842 ubifs_err("file system's life ended");
843 goto out_dump;
844 }
845
846 if (snod->sqnum < c->cs_sqnum) {
847 dbg_err("bad sqnum %llu, commit sqnum %llu",
848 snod->sqnum, c->cs_sqnum);
849 goto out_dump;
850 }
851
852 if (snod->sqnum > c->max_sqnum)
853 c->max_sqnum = snod->sqnum;
854
855 switch (snod->type) {
856 case UBIFS_REF_NODE: {
857 const struct ubifs_ref_node *ref = snod->node;
858
859 err = validate_ref(c, ref);
860 if (err == 1)
861 break; /* Already have this bud */
862 if (err)
863 goto out_dump;
864
865 err = add_replay_bud(c, le32_to_cpu(ref->lnum),
866 le32_to_cpu(ref->offs),
867 le32_to_cpu(ref->jhead),
868 snod->sqnum);
869 if (err)
870 goto out;
871
872 break;
873 }
874 case UBIFS_CS_NODE:
875 /* Make sure it sits at the beginning of LEB */
876 if (snod->offs != 0) {
877 ubifs_err("unexpected node in log");
878 goto out_dump;
879 }
880 break;
881 default:
882 ubifs_err("unexpected node in log");
883 goto out_dump;
884 }
885 }
886
887 if (sleb->endpt || c->lhead_offs >= c->leb_size) {
888 c->lhead_lnum = lnum;
889 c->lhead_offs = sleb->endpt;
890 }
891
892 err = !sleb->endpt;
893out:
894 ubifs_scan_destroy(sleb);
895 return err;
896
897out_dump:
Adrian Hunter681947d2009-06-24 09:59:38 +0300898 ubifs_err("log error detected while replaying the log at LEB %d:%d",
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300899 lnum, offs + snod->offs);
900 dbg_dump_node(c, snod->node);
901 ubifs_scan_destroy(sleb);
902 return -EINVAL;
903}
904
905/**
906 * take_ihead - update the status of the index head in lprops to 'taken'.
907 * @c: UBIFS file-system description object
908 *
909 * This function returns the amount of free space in the index head LEB or a
910 * negative error code.
911 */
912static int take_ihead(struct ubifs_info *c)
913{
914 const struct ubifs_lprops *lp;
915 int err, free;
916
917 ubifs_get_lprops(c);
918
919 lp = ubifs_lpt_lookup_dirty(c, c->ihead_lnum);
920 if (IS_ERR(lp)) {
921 err = PTR_ERR(lp);
922 goto out;
923 }
924
925 free = lp->free;
926
927 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
928 lp->flags | LPROPS_TAKEN, 0);
929 if (IS_ERR(lp)) {
930 err = PTR_ERR(lp);
931 goto out;
932 }
933
934 err = free;
935out:
936 ubifs_release_lprops(c);
937 return err;
938}
939
940/**
941 * ubifs_replay_journal - replay journal.
942 * @c: UBIFS file-system description object
943 *
944 * This function scans the journal, replays and cleans it up. It makes sure all
945 * memory data structures related to uncommitted journal are built (dirty TNC
946 * tree, tree of buds, modified lprops, etc).
947 */
948int ubifs_replay_journal(struct ubifs_info *c)
949{
950 int err, i, lnum, offs, free;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300951
952 BUILD_BUG_ON(UBIFS_TRUN_KEY > 5);
953
954 /* Update the status of the index head in lprops to 'taken' */
955 free = take_ihead(c);
956 if (free < 0)
957 return free; /* Error code */
958
959 if (c->ihead_offs != c->leb_size - free) {
960 ubifs_err("bad index head LEB %d:%d", c->ihead_lnum,
961 c->ihead_offs);
962 return -EINVAL;
963 }
964
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300965 dbg_mnt("start replaying the journal");
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300966 c->replaying = 1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300967 lnum = c->ltail_lnum = c->lhead_lnum;
968 offs = c->lhead_offs;
969
970 for (i = 0; i < c->log_lebs; i++, lnum++) {
971 if (lnum >= UBIFS_LOG_LNUM + c->log_lebs) {
972 /*
973 * The log is logically circular, we reached the last
974 * LEB, switch to the first one.
975 */
976 lnum = UBIFS_LOG_LNUM;
977 offs = 0;
978 }
Artem Bityutskiy6599fcb2010-10-18 10:00:40 +0300979 err = replay_log_leb(c, lnum, offs, c->sbuf);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300980 if (err == 1)
981 /* We hit the end of the log */
982 break;
983 if (err)
984 goto out;
985 offs = 0;
986 }
987
988 err = replay_buds(c);
989 if (err)
990 goto out;
991
Artem Bityutskiydebf12d2011-05-15 12:05:54 +0300992 err = apply_replay_list(c);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300993 if (err)
994 goto out;
995
Artem Bityutskiy074bcb92011-05-15 11:37:17 +0300996 err = set_buds_lprops(c);
997 if (err)
998 goto out;
999
Artem Bityutskiy6edbfaf2008-12-30 20:06:49 +02001000 /*
Artem Bityutskiyb1375452011-03-29 18:04:05 +03001001 * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable
1002 * to roughly estimate index growth. Things like @c->bi.min_idx_lebs
Artem Bityutskiy6edbfaf2008-12-30 20:06:49 +02001003 * depend on it. This means we have to initialize it to make sure
1004 * budgeting works properly.
1005 */
Artem Bityutskiyb1375452011-03-29 18:04:05 +03001006 c->bi.uncommitted_idx = atomic_long_read(&c->dirty_zn_cnt);
1007 c->bi.uncommitted_idx *= c->max_idx_node_sz;
Artem Bityutskiy6edbfaf2008-12-30 20:06:49 +02001008
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001009 ubifs_assert(c->bud_bytes <= c->max_bud_bytes || c->need_recovery);
1010 dbg_mnt("finished, log head LEB %d:%d, max_sqnum %llu, "
1011 "highest_inum %lu", c->lhead_lnum, c->lhead_offs, c->max_sqnum,
Artem Bityutskiye84461a2008-10-29 12:08:43 +02001012 (unsigned long)c->highest_inum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001013out:
Artem Bityutskiydebf12d2011-05-15 12:05:54 +03001014 destroy_replay_list(c);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001015 destroy_bud_list(c);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001016 c->replaying = 0;
1017 return err;
1018}