linux/fs/ubifs/scan.c
<<
>>
Prefs
   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 */
  28static 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 */
  57int 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, lnum, offs, quiet, 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, "bad pad node at LEB %d:%d",
  92                                          lnum, offs);
  93                                ubifs_dump_node(c, pad);
  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, "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 */
 125struct 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
 141        err = ubifs_leb_read(c, lnum, sbuf + offs, offs, c->leb_size - offs, 0);
 142        if (err && err != -EBADMSG) {
 143                ubifs_err(c, "cannot read %d bytes from LEB %d:%d, error %d",
 144                          c->leb_size - offs, lnum, offs, err);
 145                kfree(sleb);
 146                return ERR_PTR(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 */
 163void 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 */
 181int 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(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, &ino->key, &snod->key);
 208                break;
 209        default:
 210                invalid_key_init(c, &snod->key);
 211                break;
 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 */
 225void ubifs_scanned_corruption(const struct ubifs_info *c, int lnum, int offs,
 226                              void *buf)
 227{
 228        int len;
 229
 230        ubifs_err(c, "corruption at LEB %d:%d", lnum, offs);
 231        len = c->leb_size - offs;
 232        if (len > 8192)
 233                len = 8192;
 234        ubifs_err(c, "first %d bytes from LEB %d:%d", len, lnum, offs);
 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)
 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 */
 254struct 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(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, "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, "bad node");
 296                        goto corrupted;
 297                default:
 298                        ubifs_err(c, "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, "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, "corrupt empty space at LEB %d:%d",
 329                                          lnum, offs);
 330                        goto corrupted;
 331                }
 332
 333        return sleb;
 334
 335corrupted:
 336        if (!quiet) {
 337                ubifs_scanned_corruption(c, lnum, offs, buf);
 338                ubifs_err(c, "LEB %d scanning failed", lnum);
 339        }
 340        err = -EUCLEAN;
 341        ubifs_scan_destroy(sleb);
 342        return ERR_PTR(err);
 343
 344error:
 345        ubifs_err(c, "LEB %d scanning failed, error %d", lnum, err);
 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 */
 354void 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}
 367