fs/ubifs/scan.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * This file is part of UBIFS.
0004  *
0005  * Copyright (C) 2006-2008 Nokia Corporation
0006  *
0007  * Authors: Adrian Hunter
0008  *          Artem Bityutskiy (Битюцкий Артём)
0009  */
0010
0011 /*
0012  * This file implements the scan which is a general-purpose function for
0013  * determining what nodes are in an eraseblock. The scan is used to replay the
0014  * journal, to do garbage collection. for the TNC in-the-gaps method, and by
0015  * debugging functions.
0016  */
0017
0018 #include "ubifs.h"
0019
0020 /**
0021  * scan_padding_bytes - scan for padding bytes.
0022  * @buf: buffer to scan
0023  * @len: length of buffer
0024  *
0025  * This function returns the number of padding bytes on success and
0026  * %SCANNED_GARBAGE on failure.
0027  */
0028 static int scan_padding_bytes(void *buf, int len)
0029 {
0030     int pad_len = 0, max_pad_len = min_t(int, UBIFS_PAD_NODE_SZ, len);
0031     uint8_t *p = buf;
0032
0033     dbg_scan("not a node");
0034
0035     while (pad_len < max_pad_len && *p++ == UBIFS_PADDING_BYTE)
0036         pad_len += 1;
0037
0038     if (!pad_len || (pad_len & 7))
0039         return SCANNED_GARBAGE;
0040
0041     dbg_scan("%d padding bytes", pad_len);
0042
0043     return pad_len;
0044 }
0045
0046 /**
0047  * ubifs_scan_a_node - scan for a node or padding.
0048  * @c: UBIFS file-system description object
0049  * @buf: buffer to scan
0050  * @len: length of buffer
0051  * @lnum: logical eraseblock number
0052  * @offs: offset within the logical eraseblock
0053  * @quiet: print no messages
0054  *
0055  * This function returns a scanning code to indicate what was scanned.
0056  */
0057 int ubifs_scan_a_node(const struct ubifs_info *c, void *buf, int len, int lnum,
0058               int offs, int quiet)
0059 {
0060     struct ubifs_ch *ch = buf;
0061     uint32_t magic;
0062
0063     magic = le32_to_cpu(ch->magic);
0064
0065     if (magic == 0xFFFFFFFF) {
0066         dbg_scan("hit empty space at LEB %d:%d", lnum, offs);
0067         return SCANNED_EMPTY_SPACE;
0068     }
0069
0070     if (magic != UBIFS_NODE_MAGIC)
0071         return scan_padding_bytes(buf, len);
0072
0073     if (len < UBIFS_CH_SZ)
0074         return SCANNED_GARBAGE;
0075
0076     dbg_scan("scanning %s at LEB %d:%d",
0077          dbg_ntype(ch->node_type), lnum, offs);
0078
0079     if (ubifs_check_node(c, buf, len, lnum, offs, quiet, 1))
0080         return SCANNED_A_CORRUPT_NODE;
0081
0082     if (ch->node_type == UBIFS_PAD_NODE) {
0083         struct ubifs_pad_node *pad = buf;
0084         int pad_len = le32_to_cpu(pad->pad_len);
0085         int node_len = le32_to_cpu(ch->len);
0086
0087         /* Validate the padding node */
0088         if (pad_len < 0 ||
0089             offs + node_len + pad_len > c->leb_size) {
0090             if (!quiet) {
0091                 ubifs_err(c, "bad pad node at LEB %d:%d",
0092                       lnum, offs);
0093                 ubifs_dump_node(c, pad, len);
0094             }
0095             return SCANNED_A_BAD_PAD_NODE;
0096         }
0097
0098         /* Make the node pads to 8-byte boundary */
0099         if ((node_len + pad_len) & 7) {
0100             if (!quiet)
0101                 ubifs_err(c, "bad padding length %d - %d",
0102                       offs, offs + node_len + pad_len);
0103             return SCANNED_A_BAD_PAD_NODE;
0104         }
0105
0106         dbg_scan("%d bytes padded at LEB %d:%d, offset now %d", pad_len,
0107              lnum, offs, ALIGN(offs + node_len + pad_len, 8));
0108
0109         return node_len + pad_len;
0110     }
0111
0112     return SCANNED_A_NODE;
0113 }
0114
0115 /**
0116  * ubifs_start_scan - create LEB scanning information at start of scan.
0117  * @c: UBIFS file-system description object
0118  * @lnum: logical eraseblock number
0119  * @offs: offset to start at (usually zero)
0120  * @sbuf: scan buffer (must be c->leb_size)
0121  *
0122  * This function returns the scanned information on success and a negative error
0123  * code on failure.
0124  */
0125 struct ubifs_scan_leb *ubifs_start_scan(const struct ubifs_info *c, int lnum,
0126                     int offs, void *sbuf)
0127 {
0128     struct ubifs_scan_leb *sleb;
0129     int err;
0130
0131     dbg_scan("scan LEB %d:%d", lnum, offs);
0132
0133     sleb = kzalloc(sizeof(struct ubifs_scan_leb), GFP_NOFS);
0134     if (!sleb)
0135         return ERR_PTR(-ENOMEM);
0136
0137     sleb->lnum = lnum;
0138     INIT_LIST_HEAD(&sleb->nodes);
0139     sleb->buf = sbuf;
0140
0141     err = ubifs_leb_read(c, lnum, sbuf + offs, offs, c->leb_size - offs, 0);
0142     if (err && err != -EBADMSG) {
0143         ubifs_err(c, "cannot read %d bytes from LEB %d:%d, error %d",
0144               c->leb_size - offs, lnum, offs, err);
0145         kfree(sleb);
0146         return ERR_PTR(err);
0147     }
0148
0149     /*
0150      * Note, we ignore integrity errors (EBASMSG) because all the nodes are
0151      * protected by CRC checksums.
0152      */
0153     return sleb;
0154 }
0155
0156 /**
0157  * ubifs_end_scan - update LEB scanning information at end of scan.
0158  * @c: UBIFS file-system description object
0159  * @sleb: scanning information
0160  * @lnum: logical eraseblock number
0161  * @offs: offset to start at (usually zero)
0162  */
0163 void ubifs_end_scan(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
0164             int lnum, int offs)
0165 {
0166     dbg_scan("stop scanning LEB %d at offset %d", lnum, offs);
0167     ubifs_assert(c, offs % c->min_io_size == 0);
0168
0169     sleb->endpt = ALIGN(offs, c->min_io_size);
0170 }
0171
0172 /**
0173  * ubifs_add_snod - add a scanned node to LEB scanning information.
0174  * @c: UBIFS file-system description object
0175  * @sleb: scanning information
0176  * @buf: buffer containing node
0177  * @offs: offset of node on flash
0178  *
0179  * This function returns %0 on success and a negative error code on failure.
0180  */
0181 int ubifs_add_snod(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
0182            void *buf, int offs)
0183 {
0184     struct ubifs_ch *ch = buf;
0185     struct ubifs_ino_node *ino = buf;
0186     struct ubifs_scan_node *snod;
0187
0188     snod = kmalloc(sizeof(struct ubifs_scan_node), GFP_NOFS);
0189     if (!snod)
0190         return -ENOMEM;
0191
0192     snod->sqnum = le64_to_cpu(ch->sqnum);
0193     snod->type = ch->node_type;
0194     snod->offs = offs;
0195     snod->len = le32_to_cpu(ch->len);
0196     snod->node = buf;
0197
0198     switch (ch->node_type) {
0199     case UBIFS_INO_NODE:
0200     case UBIFS_DENT_NODE:
0201     case UBIFS_XENT_NODE:
0202     case UBIFS_DATA_NODE:
0203         /*
0204          * The key is in the same place in all keyed
0205          * nodes.
0206          */
0207         key_read(c, &ino->key, &snod->key);
0208         break;
0209     default:
0210         invalid_key_init(c, &snod->key);
0211         break;
0212     }
0213     list_add_tail(&snod->list, &sleb->nodes);
0214     sleb->nodes_cnt += 1;
0215     return 0;
0216 }
0217
0218 /**
0219  * ubifs_scanned_corruption - print information after UBIFS scanned corruption.
0220  * @c: UBIFS file-system description object
0221  * @lnum: LEB number of corruption
0222  * @offs: offset of corruption
0223  * @buf: buffer containing corruption
0224  */
0225 void ubifs_scanned_corruption(const struct ubifs_info *c, int lnum, int offs,
0226                   void *buf)
0227 {
0228     int len;
0229
0230     ubifs_err(c, "corruption at LEB %d:%d", lnum, offs);
0231     len = c->leb_size - offs;
0232     if (len > 8192)
0233         len = 8192;
0234     ubifs_err(c, "first %d bytes from LEB %d:%d", len, lnum, offs);
0235     print_hex_dump(KERN_DEBUG, "", DUMP_PREFIX_OFFSET, 32, 4, buf, len, 1);
0236 }
0237
0238 /**
0239  * ubifs_scan - scan a logical eraseblock.
0240  * @c: UBIFS file-system description object
0241  * @lnum: logical eraseblock number
0242  * @offs: offset to start at (usually zero)
0243  * @sbuf: scan buffer (must be of @c->leb_size bytes in size)
0244  * @quiet: print no messages
0245  *
0246  * This function scans LEB number @lnum and returns complete information about
0247  * its contents. Returns the scanned information in case of success and,
0248  * %-EUCLEAN if the LEB neads recovery, and other negative error codes in case
0249  * of failure.
0250  *
0251  * If @quiet is non-zero, this function does not print large and scary
0252  * error messages and flash dumps in case of errors.
0253  */
0254 struct ubifs_scan_leb *ubifs_scan(const struct ubifs_info *c, int lnum,
0255                   int offs, void *sbuf, int quiet)
0256 {
0257     void *buf = sbuf + offs;
0258     int err, len = c->leb_size - offs;
0259     struct ubifs_scan_leb *sleb;
0260
0261     sleb = ubifs_start_scan(c, lnum, offs, sbuf);
0262     if (IS_ERR(sleb))
0263         return sleb;
0264
0265     while (len >= 8) {
0266         struct ubifs_ch *ch = buf;
0267         int node_len, ret;
0268
0269         dbg_scan("look at LEB %d:%d (%d bytes left)",
0270              lnum, offs, len);
0271
0272         cond_resched();
0273
0274         ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
0275         if (ret > 0) {
0276             /* Padding bytes or a valid padding node */
0277             offs += ret;
0278             buf += ret;
0279             len -= ret;
0280             continue;
0281         }
0282
0283         if (ret == SCANNED_EMPTY_SPACE)
0284             /* Empty space is checked later */
0285             break;
0286
0287         switch (ret) {
0288         case SCANNED_GARBAGE:
0289             ubifs_err(c, "garbage");
0290             goto corrupted;
0291         case SCANNED_A_NODE:
0292             break;
0293         case SCANNED_A_CORRUPT_NODE:
0294         case SCANNED_A_BAD_PAD_NODE:
0295             ubifs_err(c, "bad node");
0296             goto corrupted;
0297         default:
0298             ubifs_err(c, "unknown");
0299             err = -EINVAL;
0300             goto error;
0301         }
0302
0303         err = ubifs_add_snod(c, sleb, buf, offs);
0304         if (err)
0305             goto error;
0306
0307         node_len = ALIGN(le32_to_cpu(ch->len), 8);
0308         offs += node_len;
0309         buf += node_len;
0310         len -= node_len;
0311     }
0312
0313     if (offs % c->min_io_size) {
0314         if (!quiet)
0315             ubifs_err(c, "empty space starts at non-aligned offset %d",
0316                   offs);
0317         goto corrupted;
0318     }
0319
0320     ubifs_end_scan(c, sleb, lnum, offs);
0321
0322     for (; len > 4; offs += 4, buf = buf + 4, len -= 4)
0323         if (*(uint32_t *)buf != 0xffffffff)
0324             break;
0325     for (; len; offs++, buf++, len--)
0326         if (*(uint8_t *)buf != 0xff) {
0327             if (!quiet)
0328                 ubifs_err(c, "corrupt empty space at LEB %d:%d",
0329                       lnum, offs);
0330             goto corrupted;
0331         }
0332
0333     return sleb;
0334
0335 corrupted:
0336     if (!quiet) {
0337         ubifs_scanned_corruption(c, lnum, offs, buf);
0338         ubifs_err(c, "LEB %d scanning failed", lnum);
0339     }
0340     err = -EUCLEAN;
0341     ubifs_scan_destroy(sleb);
0342     return ERR_PTR(err);
0343
0344 error:
0345     ubifs_err(c, "LEB %d scanning failed, error %d", lnum, err);
0346     ubifs_scan_destroy(sleb);
0347     return ERR_PTR(err);
0348 }
0349
0350 /**
0351  * ubifs_scan_destroy - destroy LEB scanning information.
0352  * @sleb: scanning information to free
0353  */
0354 void ubifs_scan_destroy(struct ubifs_scan_leb *sleb)
0355 {
0356     struct ubifs_scan_node *node;
0357     struct list_head *head;
0358
0359     head = &sleb->nodes;
0360     while (!list_empty(head)) {
0361         node = list_entry(head->next, struct ubifs_scan_node, list);
0362         list_del(&node->list);
0363         kfree(node);
0364     }
0365     kfree(sleb);
0366 }