1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * This file is part of UBIFS. |
4 | * |
5 | * Copyright (C) 2006-2008 Nokia Corporation |
6 | * |
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) { |
66 | dbg_scan("hit empty space at LEB %d:%d" , lnum, offs); |
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 | |
76 | dbg_scan("scanning %s at LEB %d:%d" , |
77 | dbg_ntype(ch->node_type), lnum, offs); |
78 | |
79 | if (ubifs_check_node(c, buf, len, lnum, offs, quiet, must_chk_crc: 1)) |
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) { |
91 | ubifs_err(c, fmt: "bad pad node at LEB %d:%d" , |
92 | lnum, offs); |
93 | ubifs_dump_node(c, node: pad, node_len: len); |
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) { |
100 | if (!quiet) |
101 | ubifs_err(c, fmt: "bad padding length %d - %d" , |
102 | offs, offs + node_len + pad_len); |
103 | return SCANNED_A_BAD_PAD_NODE; |
104 | } |
105 | |
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)); |
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 | * |
122 | * This function returns the scanned information on success and a negative error |
123 | * code on failure. |
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(size: sizeof(struct ubifs_scan_leb), GFP_NOFS); |
134 | if (!sleb) |
135 | return ERR_PTR(error: -ENOMEM); |
136 | |
137 | sleb->lnum = lnum; |
138 | INIT_LIST_HEAD(list: &sleb->nodes); |
139 | sleb->buf = sbuf; |
140 | |
141 | err = ubifs_leb_read(c, lnum, buf: sbuf + offs, offs, len: c->leb_size - offs, even_ebadmsg: 0); |
142 | if (err && err != -EBADMSG) { |
143 | ubifs_err(c, fmt: "cannot read %d bytes from LEB %d:%d, error %d" , |
144 | c->leb_size - offs, lnum, offs, err); |
145 | kfree(objp: sleb); |
146 | return ERR_PTR(error: err); |
147 | } |
148 | |
149 | /* |
150 | * Note, we ignore integrity errors (EBASMSG) because all the nodes are |
151 | * protected by CRC checksums. |
152 | */ |
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) |
162 | */ |
163 | void ubifs_end_scan(const struct ubifs_info *c, struct ubifs_scan_leb *sleb, |
164 | int lnum, int offs) |
165 | { |
166 | dbg_scan("stop scanning LEB %d at offset %d" , lnum, offs); |
167 | ubifs_assert(c, offs % c->min_io_size == 0); |
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 | |
188 | snod = kmalloc(size: sizeof(struct ubifs_scan_node), GFP_NOFS); |
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: |
203 | /* |
204 | * The key is in the same place in all keyed |
205 | * nodes. |
206 | */ |
207 | key_read(c, from: &ino->key, to: &snod->key); |
208 | break; |
209 | default: |
210 | invalid_key_init(c, key: &snod->key); |
211 | break; |
212 | } |
213 | list_add_tail(new: &snod->list, head: &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 | |
230 | ubifs_err(c, fmt: "corruption at LEB %d:%d" , lnum, offs); |
231 | len = c->leb_size - offs; |
232 | if (len > 8192) |
233 | len = 8192; |
234 | ubifs_err(c, fmt: "first %d bytes from LEB %d:%d" , len, lnum, offs); |
235 | print_hex_dump(KERN_DEBUG, prefix_str: "" , prefix_type: DUMP_PREFIX_OFFSET, rowsize: 32, groupsize: 4, buf, len, ascii: 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) |
243 | * @sbuf: scan buffer (must be of @c->leb_size bytes in size) |
244 | * @quiet: print no messages |
245 | * |
246 | * This function scans LEB number @lnum and returns complete information about |
247 | * its contents. Returns the scanned information in case of success and, |
248 | * %-EUCLEAN if the LEB neads recovery, and other negative error codes in case |
249 | * of failure. |
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. |
253 | */ |
254 | struct ubifs_scan_leb *ubifs_scan(const struct ubifs_info *c, int lnum, |
255 | int offs, void *sbuf, int quiet) |
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(ptr: 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 | |
274 | ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet); |
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: |
289 | ubifs_err(c, fmt: "garbage" ); |
290 | goto corrupted; |
291 | case SCANNED_A_NODE: |
292 | break; |
293 | case SCANNED_A_CORRUPT_NODE: |
294 | case SCANNED_A_BAD_PAD_NODE: |
295 | ubifs_err(c, fmt: "bad node" ); |
296 | goto corrupted; |
297 | default: |
298 | ubifs_err(c, fmt: "unknown" ); |
299 | err = -EINVAL; |
300 | goto error; |
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 | |
313 | if (offs % c->min_io_size) { |
314 | if (!quiet) |
315 | ubifs_err(c, fmt: "empty space starts at non-aligned offset %d" , |
316 | offs); |
317 | goto corrupted; |
318 | } |
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) { |
327 | if (!quiet) |
328 | ubifs_err(c, fmt: "corrupt empty space at LEB %d:%d" , |
329 | lnum, offs); |
330 | goto corrupted; |
331 | } |
332 | |
333 | return sleb; |
334 | |
335 | corrupted: |
336 | if (!quiet) { |
337 | ubifs_scanned_corruption(c, lnum, offs, buf); |
338 | ubifs_err(c, fmt: "LEB %d scanning failed" , lnum); |
339 | } |
340 | err = -EUCLEAN; |
341 | ubifs_scan_destroy(sleb); |
342 | return ERR_PTR(error: err); |
343 | |
344 | error: |
345 | ubifs_err(c, fmt: "LEB %d scanning failed, error %d" , lnum, err); |
346 | ubifs_scan_destroy(sleb); |
347 | return ERR_PTR(error: 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(entry: &node->list); |
363 | kfree(objp: node); |
364 | } |
365 | kfree(objp: sleb); |
366 | } |
367 | |