]>
Commit | Line | Data |
---|---|---|
1e51764a AB |
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) { | |
4b3e58a6 | 78 | dbg_scan("hit empty space at LEB %d:%d", lnum, offs); |
1e51764a AB |
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 | ||
79fda517 AB |
88 | dbg_scan("scanning %s at LEB %d:%d", |
89 | dbg_ntype(ch->node_type), lnum, offs); | |
1e51764a | 90 | |
2953e73f | 91 | if (ubifs_check_node(c, buf, lnum, offs, quiet, 1)) |
1e51764a AB |
92 | return SCANNED_A_CORRUPT_NODE; |
93 | ||
94 | if (ch->node_type == UBIFS_PAD_NODE) { | |
95 | struct ubifs_pad_node *pad = buf; | |
96 | int pad_len = le32_to_cpu(pad->pad_len); | |
97 | int node_len = le32_to_cpu(ch->len); | |
98 | ||
99 | /* Validate the padding node */ | |
100 | if (pad_len < 0 || | |
101 | offs + node_len + pad_len > c->leb_size) { | |
102 | if (!quiet) { | |
235c362b | 103 | ubifs_err(c, "bad pad node at LEB %d:%d", |
1e51764a | 104 | lnum, offs); |
edf6be24 | 105 | ubifs_dump_node(c, pad); |
1e51764a AB |
106 | } |
107 | return SCANNED_A_BAD_PAD_NODE; | |
108 | } | |
109 | ||
110 | /* Make the node pads to 8-byte boundary */ | |
111 | if ((node_len + pad_len) & 7) { | |
348709ba | 112 | if (!quiet) |
235c362b | 113 | ubifs_err(c, "bad padding length %d - %d", |
a6aae4dd | 114 | offs, offs + node_len + pad_len); |
1e51764a AB |
115 | return SCANNED_A_BAD_PAD_NODE; |
116 | } | |
117 | ||
4b3e58a6 AB |
118 | dbg_scan("%d bytes padded at LEB %d:%d, offset now %d", pad_len, |
119 | lnum, offs, ALIGN(offs + node_len + pad_len, 8)); | |
1e51764a AB |
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 | * | |
f2b6521a | 134 | * This function returns the scanned information on success and a negative error |
d685c412 | 135 | * code on failure. |
1e51764a AB |
136 | */ |
137 | struct ubifs_scan_leb *ubifs_start_scan(const struct ubifs_info *c, int lnum, | |
138 | int offs, void *sbuf) | |
139 | { | |
140 | struct ubifs_scan_leb *sleb; | |
141 | int err; | |
142 | ||
143 | dbg_scan("scan LEB %d:%d", lnum, offs); | |
144 | ||
145 | sleb = kzalloc(sizeof(struct ubifs_scan_leb), GFP_NOFS); | |
146 | if (!sleb) | |
147 | return ERR_PTR(-ENOMEM); | |
148 | ||
149 | sleb->lnum = lnum; | |
150 | INIT_LIST_HEAD(&sleb->nodes); | |
151 | sleb->buf = sbuf; | |
152 | ||
d304820a | 153 | err = ubifs_leb_read(c, lnum, sbuf + offs, offs, c->leb_size - offs, 0); |
1e51764a | 154 | if (err && err != -EBADMSG) { |
235c362b | 155 | ubifs_err(c, "cannot read %d bytes from LEB %d:%d, error %d", |
79fda517 | 156 | c->leb_size - offs, lnum, offs, err); |
1e51764a AB |
157 | kfree(sleb); |
158 | return ERR_PTR(err); | |
159 | } | |
160 | ||
c7b5bb0b | 161 | /* |
162 | * Note, we ignore integrity errors (EBASMSG) because all the nodes are | |
163 | * protected by CRC checksums. | |
164 | */ | |
1e51764a AB |
165 | return sleb; |
166 | } | |
167 | ||
168 | /** | |
169 | * ubifs_end_scan - update LEB scanning information at end of scan. | |
170 | * @c: UBIFS file-system description object | |
171 | * @sleb: scanning information | |
172 | * @lnum: logical eraseblock number | |
173 | * @offs: offset to start at (usually zero) | |
1e51764a AB |
174 | */ |
175 | void ubifs_end_scan(const struct ubifs_info *c, struct ubifs_scan_leb *sleb, | |
176 | int lnum, int offs) | |
177 | { | |
1e51764a | 178 | dbg_scan("stop scanning LEB %d at offset %d", lnum, offs); |
6eb61d58 | 179 | ubifs_assert(c, offs % c->min_io_size == 0); |
1e51764a AB |
180 | |
181 | sleb->endpt = ALIGN(offs, c->min_io_size); | |
182 | } | |
183 | ||
184 | /** | |
185 | * ubifs_add_snod - add a scanned node to LEB scanning information. | |
186 | * @c: UBIFS file-system description object | |
187 | * @sleb: scanning information | |
188 | * @buf: buffer containing node | |
189 | * @offs: offset of node on flash | |
190 | * | |
191 | * This function returns %0 on success and a negative error code on failure. | |
192 | */ | |
193 | int ubifs_add_snod(const struct ubifs_info *c, struct ubifs_scan_leb *sleb, | |
194 | void *buf, int offs) | |
195 | { | |
196 | struct ubifs_ch *ch = buf; | |
197 | struct ubifs_ino_node *ino = buf; | |
198 | struct ubifs_scan_node *snod; | |
199 | ||
ba2f48f7 | 200 | snod = kmalloc(sizeof(struct ubifs_scan_node), GFP_NOFS); |
1e51764a AB |
201 | if (!snod) |
202 | return -ENOMEM; | |
203 | ||
204 | snod->sqnum = le64_to_cpu(ch->sqnum); | |
205 | snod->type = ch->node_type; | |
206 | snod->offs = offs; | |
207 | snod->len = le32_to_cpu(ch->len); | |
208 | snod->node = buf; | |
209 | ||
210 | switch (ch->node_type) { | |
211 | case UBIFS_INO_NODE: | |
212 | case UBIFS_DENT_NODE: | |
213 | case UBIFS_XENT_NODE: | |
214 | case UBIFS_DATA_NODE: | |
1e51764a AB |
215 | /* |
216 | * The key is in the same place in all keyed | |
217 | * nodes. | |
218 | */ | |
219 | key_read(c, &ino->key, &snod->key); | |
220 | break; | |
ba2f48f7 AB |
221 | default: |
222 | invalid_key_init(c, &snod->key); | |
223 | break; | |
1e51764a AB |
224 | } |
225 | list_add_tail(&snod->list, &sleb->nodes); | |
226 | sleb->nodes_cnt += 1; | |
227 | return 0; | |
228 | } | |
229 | ||
230 | /** | |
231 | * ubifs_scanned_corruption - print information after UBIFS scanned corruption. | |
232 | * @c: UBIFS file-system description object | |
233 | * @lnum: LEB number of corruption | |
234 | * @offs: offset of corruption | |
235 | * @buf: buffer containing corruption | |
236 | */ | |
237 | void ubifs_scanned_corruption(const struct ubifs_info *c, int lnum, int offs, | |
238 | void *buf) | |
239 | { | |
240 | int len; | |
241 | ||
235c362b | 242 | ubifs_err(c, "corruption at LEB %d:%d", lnum, offs); |
1e51764a | 243 | len = c->leb_size - offs; |
086b3640 AB |
244 | if (len > 8192) |
245 | len = 8192; | |
235c362b | 246 | ubifs_err(c, "first %d bytes from LEB %d:%d", len, lnum, offs); |
1e51764a AB |
247 | print_hex_dump(KERN_DEBUG, "", DUMP_PREFIX_OFFSET, 32, 4, buf, len, 1); |
248 | } | |
249 | ||
250 | /** | |
251 | * ubifs_scan - scan a logical eraseblock. | |
252 | * @c: UBIFS file-system description object | |
253 | * @lnum: logical eraseblock number | |
254 | * @offs: offset to start at (usually zero) | |
348709ba AB |
255 | * @sbuf: scan buffer (must be of @c->leb_size bytes in size) |
256 | * @quiet: print no messages | |
1e51764a AB |
257 | * |
258 | * This function scans LEB number @lnum and returns complete information about | |
f2b6521a | 259 | * its contents. Returns the scanned information in case of success and, |
ed43f2f0 AB |
260 | * %-EUCLEAN if the LEB neads recovery, and other negative error codes in case |
261 | * of failure. | |
348709ba AB |
262 | * |
263 | * If @quiet is non-zero, this function does not print large and scary | |
264 | * error messages and flash dumps in case of errors. | |
1e51764a AB |
265 | */ |
266 | struct ubifs_scan_leb *ubifs_scan(const struct ubifs_info *c, int lnum, | |
348709ba | 267 | int offs, void *sbuf, int quiet) |
1e51764a AB |
268 | { |
269 | void *buf = sbuf + offs; | |
270 | int err, len = c->leb_size - offs; | |
271 | struct ubifs_scan_leb *sleb; | |
272 | ||
273 | sleb = ubifs_start_scan(c, lnum, offs, sbuf); | |
274 | if (IS_ERR(sleb)) | |
275 | return sleb; | |
276 | ||
277 | while (len >= 8) { | |
278 | struct ubifs_ch *ch = buf; | |
279 | int node_len, ret; | |
280 | ||
281 | dbg_scan("look at LEB %d:%d (%d bytes left)", | |
282 | lnum, offs, len); | |
283 | ||
284 | cond_resched(); | |
285 | ||
348709ba | 286 | ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet); |
1e51764a AB |
287 | if (ret > 0) { |
288 | /* Padding bytes or a valid padding node */ | |
289 | offs += ret; | |
290 | buf += ret; | |
291 | len -= ret; | |
292 | continue; | |
293 | } | |
294 | ||
295 | if (ret == SCANNED_EMPTY_SPACE) | |
296 | /* Empty space is checked later */ | |
297 | break; | |
298 | ||
299 | switch (ret) { | |
300 | case SCANNED_GARBAGE: | |
235c362b | 301 | ubifs_err(c, "garbage"); |
1e51764a AB |
302 | goto corrupted; |
303 | case SCANNED_A_NODE: | |
304 | break; | |
305 | case SCANNED_A_CORRUPT_NODE: | |
306 | case SCANNED_A_BAD_PAD_NODE: | |
235c362b | 307 | ubifs_err(c, "bad node"); |
1e51764a AB |
308 | goto corrupted; |
309 | default: | |
235c362b | 310 | ubifs_err(c, "unknown"); |
ed43f2f0 AB |
311 | err = -EINVAL; |
312 | goto error; | |
1e51764a AB |
313 | } |
314 | ||
315 | err = ubifs_add_snod(c, sleb, buf, offs); | |
316 | if (err) | |
317 | goto error; | |
318 | ||
319 | node_len = ALIGN(le32_to_cpu(ch->len), 8); | |
320 | offs += node_len; | |
321 | buf += node_len; | |
322 | len -= node_len; | |
323 | } | |
324 | ||
ed43f2f0 | 325 | if (offs % c->min_io_size) { |
348709ba | 326 | if (!quiet) |
235c362b | 327 | ubifs_err(c, "empty space starts at non-aligned offset %d", |
348709ba | 328 | offs); |
822ed64c | 329 | goto corrupted; |
ed43f2f0 | 330 | } |
1e51764a AB |
331 | |
332 | ubifs_end_scan(c, sleb, lnum, offs); | |
333 | ||
334 | for (; len > 4; offs += 4, buf = buf + 4, len -= 4) | |
335 | if (*(uint32_t *)buf != 0xffffffff) | |
336 | break; | |
337 | for (; len; offs++, buf++, len--) | |
338 | if (*(uint8_t *)buf != 0xff) { | |
348709ba | 339 | if (!quiet) |
235c362b | 340 | ubifs_err(c, "corrupt empty space at LEB %d:%d", |
348709ba | 341 | lnum, offs); |
1e51764a AB |
342 | goto corrupted; |
343 | } | |
344 | ||
345 | return sleb; | |
346 | ||
347 | corrupted: | |
348709ba AB |
348 | if (!quiet) { |
349 | ubifs_scanned_corruption(c, lnum, offs, buf); | |
235c362b | 350 | ubifs_err(c, "LEB %d scanning failed", lnum); |
348709ba | 351 | } |
1e51764a | 352 | err = -EUCLEAN; |
348709ba AB |
353 | ubifs_scan_destroy(sleb); |
354 | return ERR_PTR(err); | |
355 | ||
1e51764a | 356 | error: |
235c362b | 357 | ubifs_err(c, "LEB %d scanning failed, error %d", lnum, err); |
1e51764a AB |
358 | ubifs_scan_destroy(sleb); |
359 | return ERR_PTR(err); | |
360 | } | |
361 | ||
362 | /** | |
363 | * ubifs_scan_destroy - destroy LEB scanning information. | |
364 | * @sleb: scanning information to free | |
365 | */ | |
366 | void ubifs_scan_destroy(struct ubifs_scan_leb *sleb) | |
367 | { | |
368 | struct ubifs_scan_node *node; | |
369 | struct list_head *head; | |
370 | ||
371 | head = &sleb->nodes; | |
372 | while (!list_empty(head)) { | |
373 | node = list_entry(head->next, struct ubifs_scan_node, list); | |
374 | list_del(&node->list); | |
375 | kfree(node); | |
376 | } | |
377 | kfree(sleb); | |
378 | } |