diff options
Diffstat (limited to 'fs/ubifs/scan.c')
-rw-r--r-- | fs/ubifs/scan.c | 362 |
1 files changed, 362 insertions, 0 deletions
diff --git a/fs/ubifs/scan.c b/fs/ubifs/scan.c new file mode 100644 index 000000000000..acf5c5fffc60 --- /dev/null +++ b/fs/ubifs/scan.c | |||
@@ -0,0 +1,362 @@ | |||
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)) | ||
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 | } | ||