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