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