← Back to branch summary

~ubuntu-branches/ubuntu/maverick/u-boot-omap3/maverick

« back to all changes in this revision

Viewing changes to fs/ubifs/scan.c

  • Committer: Bazaar Package Importer
  • Author(s): Oliver Grawert
  • Date: 2010-03-22 15:06:23 UTC
  • Revision ID: james.westby@ubuntu.com-20100322150623-i21g8rgiyl5dohag
Tags: upstream-2010.3git20100315
ImportĀ upstreamĀ versionĀ 2010.3git20100315

Show diffs side-by-side

added added

removed removed

Lines of Context:
fs/ubifs/scan.c
 
1
/*
 
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 implements the scan which is a general-purpose function for
 
25
 * determining what nodes are in an eraseblock. The scan is used to replay the
 
26
 * journal, to do garbage collection. for the TNC in-the-gaps method, and by
 
27
 * debugging functions.
 
28
 */
 
29
 
 
30
#include "ubifs.h"
 
31
 
 
32
/**
 
33
 * scan_padding_bytes - scan for padding bytes.
 
34
 * @buf: buffer to scan
 
35
 * @len: length of buffer
 
36
 *
 
37
 * This function returns the number of padding bytes on success and
 
38
 * %SCANNED_GARBAGE on failure.
 
39
 */
 
40
static int scan_padding_bytes(void *buf, int len)
 
41
{
 
42
        int pad_len = 0, max_pad_len = min_t(int, UBIFS_PAD_NODE_SZ, len);
 
43
        uint8_t *p = buf;
 
44
 
 
45
        dbg_scan("not a node");
 
46
 
 
47
        while (pad_len < max_pad_len && *p++ == UBIFS_PADDING_BYTE)
 
48
                pad_len += 1;
 
49
 
 
50
        if (!pad_len || (pad_len & 7))
 
51
                return SCANNED_GARBAGE;
 
52
 
 
53
        dbg_scan("%d padding bytes", pad_len);
 
54
 
 
55
        return pad_len;
 
56
}
 
57
 
 
58
/**
 
59
 * ubifs_scan_a_node - scan for a node or padding.
 
60
 * @c: UBIFS file-system description object
 
61
 * @buf: buffer to scan
 
62
 * @len: length of buffer
 
63
 * @lnum: logical eraseblock number
 
64
 * @offs: offset within the logical eraseblock
 
65
 * @quiet: print no messages
 
66
 *
 
67
 * This function returns a scanning code to indicate what was scanned.
 
68
 */
 
69
int ubifs_scan_a_node(const struct ubifs_info *c, void *buf, int len, int lnum,
 
70
                      int offs, int quiet)
 
71
{
 
72
        struct ubifs_ch *ch = buf;
 
73
        uint32_t magic;
 
74
 
 
75
        magic = le32_to_cpu(ch->magic);
 
76
 
 
77
        if (magic == 0xFFFFFFFF) {
 
78
                dbg_scan("hit empty space");
 
79
                return SCANNED_EMPTY_SPACE;
 
80
        }
 
81
 
 
82
        if (magic != UBIFS_NODE_MAGIC)
 
83
                return scan_padding_bytes(buf, len);
 
84
 
 
85
        if (len < UBIFS_CH_SZ)
 
86
                return SCANNED_GARBAGE;
 
87
 
 
88
        dbg_scan("scanning %s", dbg_ntype(ch->node_type));
 
89
 
 
90
        if (ubifs_check_node(c, buf, lnum, offs, quiet, 1))
 
91
                return SCANNED_A_CORRUPT_NODE;
 
92
 
 
93
        if (ch->node_type == UBIFS_PAD_NODE) {
 
94
                struct ubifs_pad_node *pad = buf;
 
95
                int pad_len = le32_to_cpu(pad->pad_len);
 
96
                int node_len = le32_to_cpu(ch->len);
 
97
 
 
98
                /* Validate the padding node */
 
99
                if (pad_len < 0 ||
 
100
                    offs + node_len + pad_len > c->leb_size) {
 
101
                        if (!quiet) {
 
102
                                ubifs_err("bad pad node at LEB %d:%d",
 
103
                                          lnum, offs);
 
104
                                dbg_dump_node(c, pad);
 
105
                        }
 
106
                        return SCANNED_A_BAD_PAD_NODE;
 
107
                }
 
108
 
 
109
                /* Make the node pads to 8-byte boundary */
 
110
                if ((node_len + pad_len) & 7) {
 
111
                        if (!quiet) {
 
112
                                dbg_err("bad padding length %d - %d",
 
113
                                        offs, offs + node_len + pad_len);
 
114
                        }
 
115
                        return SCANNED_A_BAD_PAD_NODE;
 
116
                }
 
117
 
 
118
                dbg_scan("%d bytes padded, offset now %d",
 
119
                         pad_len, ALIGN(offs + node_len + pad_len, 8));
 
120
 
 
121
                return node_len + pad_len;
 
122
        }
 
123
 
 
124
        return SCANNED_A_NODE;
 
125
}
 
126
 
 
127
/**
 
128
 * ubifs_start_scan - create LEB scanning information at start of scan.
 
129
 * @c: UBIFS file-system description object
 
130
 * @lnum: logical eraseblock number
 
131
 * @offs: offset to start at (usually zero)
 
132
 * @sbuf: scan buffer (must be c->leb_size)
 
133
 *
 
134
 * This function returns %0 on success and a negative error code on failure.
 
135
 */
 
136
struct ubifs_scan_leb *ubifs_start_scan(const struct ubifs_info *c, int lnum,
 
137
                                        int offs, void *sbuf)
 
138
{
 
139
        struct ubifs_scan_leb *sleb;
 
140
        int err;
 
141
 
 
142
        dbg_scan("scan LEB %d:%d", lnum, offs);
 
143
 
 
144
        sleb = kzalloc(sizeof(struct ubifs_scan_leb), GFP_NOFS);
 
145
        if (!sleb)
 
146
                return ERR_PTR(-ENOMEM);
 
147
 
 
148
        sleb->lnum = lnum;
 
149
        INIT_LIST_HEAD(&sleb->nodes);
 
150
        sleb->buf = sbuf;
 
151
 
 
152
        err = ubi_read(c->ubi, lnum, sbuf + offs, offs, c->leb_size - offs);
 
153
        if (err && err != -EBADMSG) {
 
154
                ubifs_err("cannot read %d bytes from LEB %d:%d,"
 
155
                          " error %d", c->leb_size - offs, lnum, offs, err);
 
156
                kfree(sleb);
 
157
                return ERR_PTR(err);
 
158
        }
 
159
 
 
160
        if (err == -EBADMSG)
 
161
                sleb->ecc = 1;
 
162
 
 
163
        return sleb;
 
164
}
 
165
 
 
166
/**
 
167
 * ubifs_end_scan - update LEB scanning information at end of scan.
 
168
 * @c: UBIFS file-system description object
 
169
 * @sleb: scanning information
 
170
 * @lnum: logical eraseblock number
 
171
 * @offs: offset to start at (usually zero)
 
172
 *
 
173
 * This function returns %0 on success and a negative error code on failure.
 
174
 */
 
175
void ubifs_end_scan(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 
176
                    int lnum, int offs)
 
177
{
 
178
        lnum = lnum;
 
179
        dbg_scan("stop scanning LEB %d at offset %d", lnum, offs);
 
180
        ubifs_assert(offs % c->min_io_size == 0);
 
181
 
 
182
        sleb->endpt = ALIGN(offs, c->min_io_size);
 
183
}
 
184
 
 
185
/**
 
186
 * ubifs_add_snod - add a scanned node to LEB scanning information.
 
187
 * @c: UBIFS file-system description object
 
188
 * @sleb: scanning information
 
189
 * @buf: buffer containing node
 
190
 * @offs: offset of node on flash
 
191
 *
 
192
 * This function returns %0 on success and a negative error code on failure.
 
193
 */
 
194
int ubifs_add_snod(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 
195
                   void *buf, int offs)
 
196
{
 
197
        struct ubifs_ch *ch = buf;
 
198
        struct ubifs_ino_node *ino = buf;
 
199
        struct ubifs_scan_node *snod;
 
200
 
 
201
        snod = kzalloc(sizeof(struct ubifs_scan_node), GFP_NOFS);
 
202
        if (!snod)
 
203
                return -ENOMEM;
 
204
 
 
205
        snod->sqnum = le64_to_cpu(ch->sqnum);
 
206
        snod->type = ch->node_type;
 
207
        snod->offs = offs;
 
208
        snod->len = le32_to_cpu(ch->len);
 
209
        snod->node = buf;
 
210
 
 
211
        switch (ch->node_type) {
 
212
        case UBIFS_INO_NODE:
 
213
        case UBIFS_DENT_NODE:
 
214
        case UBIFS_XENT_NODE:
 
215
        case UBIFS_DATA_NODE:
 
216
        case UBIFS_TRUN_NODE:
 
217
                /*
 
218
                 * The key is in the same place in all keyed
 
219
                 * nodes.
 
220
                 */
 
221
                key_read(c, &ino->key, &snod->key);
 
222
                break;
 
223
        }
 
224
        list_add_tail(&snod->list, &sleb->nodes);
 
225
        sleb->nodes_cnt += 1;
 
226
        return 0;
 
227
}
 
228
 
 
229
/**
 
230
 * ubifs_scanned_corruption - print information after UBIFS scanned corruption.
 
231
 * @c: UBIFS file-system description object
 
232
 * @lnum: LEB number of corruption
 
233
 * @offs: offset of corruption
 
234
 * @buf: buffer containing corruption
 
235
 */
 
236
void ubifs_scanned_corruption(const struct ubifs_info *c, int lnum, int offs,
 
237
                              void *buf)
 
238
{
 
239
        int len;
 
240
 
 
241
        ubifs_err("corrupted data at LEB %d:%d", lnum, offs);
 
242
        if (dbg_failure_mode)
 
243
                return;
 
244
        len = c->leb_size - offs;
 
245
        if (len > 4096)
 
246
                len = 4096;
 
247
        dbg_err("first %d bytes from LEB %d:%d", len, lnum, offs);
 
248
        print_hex_dump(KERN_DEBUG, "", DUMP_PREFIX_OFFSET, 32, 4, buf, len, 1);
 
249
}
 
250
 
 
251
/**
 
252
 * ubifs_scan - scan a logical eraseblock.
 
253
 * @c: UBIFS file-system description object
 
254
 * @lnum: logical eraseblock number
 
255
 * @offs: offset to start at (usually zero)
 
256
 * @sbuf: scan buffer (must be c->leb_size)
 
257
 *
 
258
 * This function scans LEB number @lnum and returns complete information about
 
259
 * its contents. Returns an error code in case of failure.
 
260
 */
 
261
struct ubifs_scan_leb *ubifs_scan(const struct ubifs_info *c, int lnum,
 
262
                                  int offs, void *sbuf)
 
263
{
 
264
        void *buf = sbuf + offs;
 
265
        int err, len = c->leb_size - offs;
 
266
        struct ubifs_scan_leb *sleb;
 
267
 
 
268
        sleb = ubifs_start_scan(c, lnum, offs, sbuf);
 
269
        if (IS_ERR(sleb))
 
270
                return sleb;
 
271
 
 
272
        while (len >= 8) {
 
273
                struct ubifs_ch *ch = buf;
 
274
                int node_len, ret;
 
275
 
 
276
                dbg_scan("look at LEB %d:%d (%d bytes left)",
 
277
                         lnum, offs, len);
 
278
 
 
279
                cond_resched();
 
280
 
 
281
                ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 0);
 
282
 
 
283
                if (ret > 0) {
 
284
                        /* Padding bytes or a valid padding node */
 
285
                        offs += ret;
 
286
                        buf += ret;
 
287
                        len -= ret;
 
288
                        continue;
 
289
                }
 
290
 
 
291
                if (ret == SCANNED_EMPTY_SPACE)
 
292
                        /* Empty space is checked later */
 
293
                        break;
 
294
 
 
295
                switch (ret) {
 
296
                case SCANNED_GARBAGE:
 
297
                        dbg_err("garbage");
 
298
                        goto corrupted;
 
299
                case SCANNED_A_NODE:
 
300
                        break;
 
301
                case SCANNED_A_CORRUPT_NODE:
 
302
                case SCANNED_A_BAD_PAD_NODE:
 
303
                        dbg_err("bad node");
 
304
                        goto corrupted;
 
305
                default:
 
306
                        dbg_err("unknown");
 
307
                        goto corrupted;
 
308
                }
 
309
 
 
310
                err = ubifs_add_snod(c, sleb, buf, offs);
 
311
                if (err)
 
312
                        goto error;
 
313
 
 
314
                node_len = ALIGN(le32_to_cpu(ch->len), 8);
 
315
                offs += node_len;
 
316
                buf += node_len;
 
317
                len -= node_len;
 
318
        }
 
319
 
 
320
        if (offs % c->min_io_size)
 
321
                goto corrupted;
 
322
 
 
323
        ubifs_end_scan(c, sleb, lnum, offs);
 
324
 
 
325
        for (; len > 4; offs += 4, buf = buf + 4, len -= 4)
 
326
                if (*(uint32_t *)buf != 0xffffffff)
 
327
                        break;
 
328
        for (; len; offs++, buf++, len--)
 
329
                if (*(uint8_t *)buf != 0xff) {
 
330
                        ubifs_err("corrupt empty space at LEB %d:%d",
 
331
                                  lnum, offs);
 
332
                        goto corrupted;
 
333
                }
 
334
 
 
335
        return sleb;
 
336
 
 
337
corrupted:
 
338
        ubifs_scanned_corruption(c, lnum, offs, buf);
 
339
        err = -EUCLEAN;
 
340
error:
 
341
        ubifs_err("LEB %d scanning failed", lnum);
 
342
        ubifs_scan_destroy(sleb);
 
343
        return ERR_PTR(err);
 
344
}
 
345
 
 
346
/**
 
347
 * ubifs_scan_destroy - destroy LEB scanning information.
 
348
 * @sleb: scanning information to free
 
349
 */
 
350
void ubifs_scan_destroy(struct ubifs_scan_leb *sleb)
 
351
{
 
352
        struct ubifs_scan_node *node;
 
353
        struct list_head *head;
 
354
 
 
355
        head = &sleb->nodes;
 
356
        while (!list_empty(head)) {
 
357
                node = list_entry(head->next, struct ubifs_scan_node, list);
 
358
                list_del(&node->list);
 
359
                kfree(node);
 
360
        }
 
361
        kfree(sleb);
 
362
}