/*-
 * SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright (c) 1980, 1986, 1993
 *      The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/disk.h>
#include <sys/stat.h>
#define FSTYPENAMES
#include <sys/disklabel.h>
#include <sys/file.h>
#include <sys/sysctl.h>

#include <ufs/ufs/dinode.h>
#include <ufs/ffs/fs.h>

#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <limits.h>
#include <stdint.h>
#include <string.h>

#include "fsck.h"

struct inohash *inphash;               /* hash list of directory inode info */
struct inoinfo **inpsort;              /* disk order list of directory inodes */
struct inode snaplist[FSMAXSNAP + 1];  /* list of active snapshots */
int snapcnt;                           /* number of active snapshots */
char *copybuf;                         /* buffer to copy snapshot blocks */

static int sbhashfailed;
#define POWEROF2(num)   (((num) & ((num) - 1)) == 0)

static void saverecovery(int readfd, int writefd);
static int chkrecovery(int devfd);
static int getlbnblkno(struct inodesc *);
static int checksnapinfo(struct inode *);

/*
 * Read in a superblock finding an alternate if necessary.
 * Return 1 if successful, 0 if unsuccessful, -1 if file system
 * is already clean (ckclean and preen mode only).
 */
int
setup(char *dev)
{
        long i, bmapsize;
        struct inode ip;

        /*
         * We are expected to have an open file descriptor and a superblock.
         */
        if (fsreadfd < 0 || havesb == 0) {
                if (debug) {
                        if (fsreadfd < 0)
                                printf("setup: missing fsreadfd\n");
                        else
                                printf("setup: missing superblock\n");
                }
                return (0);
        }
        if (preen == 0)
                printf("** %s", dev);
        if (bkgrdflag == 0 &&
            (nflag || (fswritefd = open(dev, O_WRONLY)) < 0)) {
                fswritefd = -1;
                if (preen)
                        pfatal("NO WRITE ACCESS");
                printf(" (NO WRITE)");
        }
        if (preen == 0)
                printf("\n");
        if (sbhashfailed != 0) {
                pwarn("SUPERBLOCK CHECK HASH FAILED");
                if (fswritefd == -1)
                        pwarn("OPENED READONLY SO CANNOT CORRECT CHECK HASH\n");
                else if (preen || reply("CORRECT CHECK HASH") != 0) {
                        if (preen)
                                printf(" (CORRECTED)\n");
                        sblock.fs_clean = 0;
                        sbdirty();
                }
        }
        if (skipclean && ckclean && sblock.fs_clean) {
                pwarn("FILE SYSTEM CLEAN; SKIPPING CHECKS\n");
                return (-1);
        }
        maxfsblock = sblock.fs_size;
        maxino = sblock.fs_ncg * sblock.fs_ipg;
        /*
         * Check and potentially fix certain fields in the super block.
         */
        if (sblock.fs_optim != FS_OPTTIME && sblock.fs_optim != FS_OPTSPACE) {
                pfatal("UNDEFINED OPTIMIZATION IN SUPERBLOCK");
                if (reply("SET TO DEFAULT") == 1) {
                        sblock.fs_optim = FS_OPTTIME;
                        sbdirty();
                }
        }
        if ((sblock.fs_minfree < 0 || sblock.fs_minfree > 99)) {
                pfatal("IMPOSSIBLE MINFREE=%d IN SUPERBLOCK",
                        sblock.fs_minfree);
                if (reply("SET TO DEFAULT") == 1) {
                        sblock.fs_minfree = 10;
                        sbdirty();
                }
        }
        if (sblock.fs_magic == FS_UFS1_MAGIC &&
            sblock.fs_old_inodefmt < FS_44INODEFMT) {
                pwarn("Format of file system is too old.\n");
                pwarn("Must update to modern format using a version of fsck\n");
                pfatal("from before 2002 with the command ``fsck -c 2''\n");
                exit(EEXIT);
        }
        if (preen == 0 && yflag == 0 && sblock.fs_magic == FS_UFS2_MAGIC &&
            fswritefd != -1 && chkrecovery(fsreadfd) == 0 &&
            reply("SAVE DATA TO FIND ALTERNATE SUPERBLOCKS") != 0)
                saverecovery(fsreadfd, fswritefd);
        /*
         * allocate and initialize the necessary maps
         */
        bufinit();
        bmapsize = roundup(howmany(maxfsblock, CHAR_BIT), sizeof(short));
        blockmap = Calloc((unsigned)bmapsize, sizeof (char));
        if (blockmap == NULL) {
                printf("cannot alloc %u bytes for blockmap\n",
                    (unsigned)bmapsize);
                goto badsb;
        }
        inostathead = Calloc(sblock.fs_ncg, sizeof(struct inostatlist));
        if (inostathead == NULL) {
                printf("cannot alloc %u bytes for inostathead\n",
                    (unsigned)(sizeof(struct inostatlist) * (sblock.fs_ncg)));
                goto badsb;
        }
        numdirs = sblock.fs_cstotal.cs_ndir;
        dirhash = MAX(numdirs / 2, 1);
        inplast = 0;
        listmax = numdirs + 10;
        inpsort = (struct inoinfo **)Calloc(listmax, sizeof(struct inoinfo *));
        inphash = (struct inohash *)Calloc(dirhash, sizeof(struct inohash));
        if (inpsort == NULL || inphash == NULL) {
                printf("cannot alloc %ju bytes for inphash\n",
                    (uintmax_t)numdirs * sizeof(struct inoinfo *));
                goto badsb;
        }
        if (sblock.fs_flags & FS_DOSOFTDEP)
                usedsoftdep = 1;
        else
                usedsoftdep = 0;
        /*
         * Collect any snapshot inodes so that we can allow them to
         * claim any blocks that we free. The code for doing this is
         * imported here and into inode.c from sys/ufs/ffs/ffs_snapshot.c.
         */
        for (snapcnt = 0; snapcnt < FSMAXSNAP; snapcnt++) {
                if (sblock.fs_snapinum[snapcnt] == 0)
                        break;
                ginode(sblock.fs_snapinum[snapcnt], &ip);
                if ((DIP(ip.i_dp, di_mode) & IFMT) == IFREG &&
                    (DIP(ip.i_dp, di_flags) & SF_SNAPSHOT) != 0 &&
                    checksnapinfo(&ip)) {
                        if (debug)
                                printf("Load snapshot %jd\n",
                                    (intmax_t)sblock.fs_snapinum[snapcnt]);
                        snaplist[snapcnt] = ip;
                        continue;
                }
                printf("Removing non-snapshot inode %ju from snapshot list\n",
                    (uintmax_t)sblock.fs_snapinum[snapcnt]);
                irelse(&ip);
                for (i = snapcnt + 1; i < FSMAXSNAP; i++) {
                        if (sblock.fs_snapinum[i] == 0)
                                break;
                        sblock.fs_snapinum[i - 1] = sblock.fs_snapinum[i];
                }
                sblock.fs_snapinum[i - 1] = 0;
                snapcnt--;
                sbdirty();
        }
        if (snapcnt > 0 && copybuf == NULL) {
                copybuf = Balloc(sblock.fs_bsize);
                if (copybuf == NULL)
                        errx(EEXIT, "cannot allocate space for snapshot "
                            "copy buffer");
        }
        return (1);

badsb:
        ckfini(0);
        return (0);
}

/*
 * Check for valid snapshot information.
 *
 * Each snapshot has a list of blocks that have been copied. This list
 * is consulted before checking the snapshot inode. Its purpose is to
 * speed checking of commonly checked blocks and to avoid recursive
 * checks of the snapshot inode. In particular, the list must contain
 * the superblock, the superblock summary information, and all the
 * cylinder group blocks. The list may contain other commonly checked
 * pointers such as those of the blocks that contain the snapshot inodes.
 * The list is sorted into block order to allow binary search lookup.
 *
 * The twelve direct direct block pointers of the snapshot are always
 * copied, so we test for them first before checking the list itself
 * (i.e., they are not in the list).
 *
 * The checksnapinfo() routine needs to ensure that the list contains at
 * least the super block, its summary information, and the cylinder groups.
 * Here we check the list first for the superblock, zero or more cylinder
 * groups up to the location of the superblock summary information, the
 * summary group information, and any remaining cylinder group maps that
 * follow it. We skip over any other entries in the list.
 */
#define CHKBLKINLIST(chkblk)                                            \
        /* All UFS_NDADDR blocks are copied */                          \
        if ((chkblk) >= UFS_NDADDR) {                                   \
                /* Skip over blocks that are not of interest */         \
                while (*blkp < (chkblk) && blkp < lastblkp)             \
                        blkp++;                                         \
                /* Fail if end of list and not all blocks found */      \
                if (blkp >= lastblkp) {                                 \
                        pwarn("UFS%d snapshot inode %jd failed: "       \
                            "improper block list length (%jd)\n",       \
                            sblock.fs_magic == FS_UFS1_MAGIC ? 1 : 2,   \
                            (intmax_t)snapip->i_number,                 \
                            (intmax_t)(lastblkp - &snapblklist[0]));    \
                        status = 0;                                     \
                }                                                       \
                /* Fail if block we seek is missing */                  \
                else if (*blkp++ != (chkblk)) {                         \
                        pwarn("UFS%d snapshot inode %jd failed: "       \
                            "block list (%jd) != %s (%jd)\n",           \
                            sblock.fs_magic == FS_UFS1_MAGIC ? 1 : 2,   \
                            (intmax_t)snapip->i_number,                 \
                            (intmax_t)blkp[-1], #chkblk,                \
                            (intmax_t)chkblk);                          \
                        status = 0;                                     \
                }                                                       \
        }

static int
checksnapinfo(struct inode *snapip)
{
        struct fs *fs;
        struct bufarea *bp;
        struct inodesc idesc;
        daddr_t *snapblklist, *blkp, *lastblkp, csblkno;
        int cg, loc, len, status;
        ufs_lbn_t lbn;
        size_t size;

        fs = &sblock;
        memset(&idesc, 0, sizeof(struct inodesc));
        idesc.id_type = ADDR;
        idesc.id_func = getlbnblkno;
        idesc.id_number = snapip->i_number;
        lbn = howmany(fs->fs_size, fs->fs_frag);
        idesc.id_parent = lbn;          /* sought after blkno */
        if ((ckinode(snapip->i_dp, &idesc) & FOUND) == 0)
                return (0);
        size = fragroundup(fs,
            DIP(snapip->i_dp, di_size) - lblktosize(fs, lbn));
        bp = getdatablk(idesc.id_parent, size, BT_DATA);
        if (bp->b_errs != 0)
                return (0);
        snapblklist = (daddr_t *)bp->b_un.b_buf;
        /*
         * snapblklist[0] is the size of the list
         * snapblklist[1] is the first element of the list
         *
         * We need to be careful to bound the size of the list and verify
         * that we have not run off the end of it if it or its size has
         * been corrupted.
         */
        blkp = &snapblklist[1];
        lastblkp = &snapblklist[MAX(0,
            MIN(snapblklist[0] + 1, size / sizeof(daddr_t)))];
        status = 1;
        /* Check that the superblock is listed. */
        CHKBLKINLIST(lblkno(fs, fs->fs_sblockloc));
        if (status == 0)
                goto out;
        /*
         * Calculate where the summary information is located.
         * Usually it is in the first cylinder group, but growfs
         * may move it to the first cylinder group that it adds.
         *
         * Check all cylinder groups up to the summary information.
         */
        csblkno = fragstoblks(fs, fs->fs_csaddr);
        for (cg = 0; cg < fs->fs_ncg; cg++) {
                if (fragstoblks(fs, cgtod(fs, cg)) > csblkno)
                        break;
                CHKBLKINLIST(fragstoblks(fs, cgtod(fs, cg)));
                if (status == 0)
                        goto out;
        }
        /* Check the summary information block(s). */
        len = howmany(fs->fs_cssize, fs->fs_bsize);
        for (loc = 0; loc < len; loc++) {
                CHKBLKINLIST(csblkno + loc);
                if (status == 0)
                        goto out;
        }
        /* Check the remaining cylinder groups. */
        for (; cg < fs->fs_ncg; cg++) {
                CHKBLKINLIST(fragstoblks(fs, cgtod(fs, cg)));
                if (status == 0)
                        goto out;
        }
out:
        brelse(bp);
        return (status);
}

/*
 * Return the block number associated with a specified inode lbn.
 * Requested lbn is in id_parent. If found, block is returned in
 * id_parent.
 */
static int
getlbnblkno(struct inodesc *idesc)
{

        if (idesc->id_lbn < idesc->id_parent)
                return (KEEPON);
        idesc->id_parent = idesc->id_blkno;
        return (STOP | FOUND);
}

/*
 * Open a device or file to be checked by fsck.
 */
int
openfilesys(char *dev)
{
        struct stat statb;
        int saved_fsreadfd;

        if (stat(dev, &statb) < 0)
                return (0);
        if ((statb.st_mode & S_IFMT) != S_IFCHR &&
            (statb.st_mode & S_IFMT) != S_IFBLK) {
                if (bkgrdflag != 0 && (statb.st_flags & SF_SNAPSHOT) == 0) {
                        pwarn("BACKGROUND FSCK LACKS A SNAPSHOT\n");
                        return (0);
                }
                if (bkgrdflag != 0) {
                        cursnapshot = statb.st_ino;
                } else {
                        pwarn("%s IS NOT A DISK DEVICE\n", dev);
                        if (preen || reply("CONTINUE") == 0)
                                return (0);
                }
        }
        saved_fsreadfd = fsreadfd;
        if ((fsreadfd = open(dev, O_RDONLY)) < 0) {
                fsreadfd = saved_fsreadfd;
                return (0);
        }
        if (saved_fsreadfd != -1)
                close(saved_fsreadfd);
        return (1);
}

/*
 * Read in the super block and its summary info.
 */
int
readsb(void)
{
        struct fs *fs;

        sbhashfailed = 0;
        readcnt[sblk.b_type]++;
        /*
         * If bflag is given, then check just that superblock.
         */
        if (bflag) {
                switch (sbget(fsreadfd, &fs, bflag * dev_bsize, 0)) {
                case 0:
                        goto goodsb;
                case EINTEGRITY:
                        printf("Check hash failed for superblock at %jd\n",
                            bflag);
                        return (0);
                case ENOENT:
                        printf("%jd is not a file system superblock\n", bflag);
                        return (0);
                case EIO:
                default:
                        printf("I/O error reading %jd\n", bflag);
                        return (0);
                }
        }
        /*
         * Check for the standard superblock and use it if good.
         */
        if (sbget(fsreadfd, &fs, UFS_STDSB, UFS_NOMSG) == 0)
                goto goodsb;
        /*
         * Check if the only problem is a check-hash failure.
         */
        skipclean = 0;
        if (sbget(fsreadfd, &fs, UFS_STDSB, UFS_NOMSG | UFS_NOHASHFAIL) == 0) {
                sbhashfailed = 1;
                goto goodsb;
        }
        /*
         * Do an exhaustive search for a usable superblock.
         */
        switch (sbsearch(fsreadfd, &fs, 0)) {
        case 0:
                goto goodsb;
        case ENOENT:
                printf("SEARCH FOR ALTERNATE SUPER-BLOCK FAILED. "
                    "YOU MUST USE THE\n-b OPTION TO FSCK TO SPECIFY "
                    "THE LOCATION OF AN ALTERNATE\nSUPER-BLOCK TO "
                    "SUPPLY NEEDED INFORMATION; SEE fsck_ffs(8).\n");
                return (0);
        case EIO:
        default:
                printf("I/O error reading a usable superblock\n");
                return (0);
        }

goodsb:
        memcpy(&sblock, fs, fs->fs_sbsize);
        free(fs);
        /*
         * Compute block size that the file system is based on,
         * according to fsbtodb, and adjust superblock block number
         * so we can tell if this is an alternate later.
         */
        dev_bsize = sblock.fs_fsize / fsbtodb(&sblock, 1);
        sblk.b_bno = sblock.fs_sblockactualloc / dev_bsize;
        sblk.b_size = SBLOCKSIZE;
        /*
         * If not yet done, update UFS1 superblock with new wider fields.
         */
        if (sblock.fs_magic == FS_UFS1_MAGIC &&
            sblock.fs_maxbsize != sblock.fs_bsize) {
                sblock.fs_maxbsize = sblock.fs_bsize;
                sblock.fs_time = sblock.fs_old_time;
                sblock.fs_size = sblock.fs_old_size;
                sblock.fs_dsize = sblock.fs_old_dsize;
                sblock.fs_csaddr = sblock.fs_old_csaddr;
                sblock.fs_cstotal.cs_ndir = sblock.fs_old_cstotal.cs_ndir;
                sblock.fs_cstotal.cs_nbfree = sblock.fs_old_cstotal.cs_nbfree;
                sblock.fs_cstotal.cs_nifree = sblock.fs_old_cstotal.cs_nifree;
                sblock.fs_cstotal.cs_nffree = sblock.fs_old_cstotal.cs_nffree;
        }
        havesb = 1;
        return (1);
}

void
sblock_init(void)
{

        fsreadfd = -1;
        fswritefd = -1;
        fsmodified = 0;
        lfdir = 0;
        initbarea(&sblk, BT_SUPERBLK);
        sblk.b_un.b_buf = Balloc(SBLOCKSIZE);
        if (sblk.b_un.b_buf == NULL)
                errx(EEXIT, "cannot allocate space for superblock");
        dev_bsize = secsize = DEV_BSIZE;
}

/*
 * Check to see if recovery information exists.
 * Return 1 if it exists or cannot be created.
 * Return 0 if it does not exist and can be created.
 */
static int
chkrecovery(int devfd)
{
        struct fsrecovery *fsr;
        char *fsrbuf;
        u_int secsize, rdsize;

        /*
         * Could not determine if backup material exists, so do not
         * offer to create it.
         */
        fsrbuf = NULL;
        rdsize = sblock.fs_fsize;
        if (ioctl(devfd, DIOCGSECTORSIZE, &secsize) == -1 ||
            rdsize % secsize != 0 ||
            (fsrbuf = Balloc(rdsize)) == NULL ||
            blread(devfd, fsrbuf, (SBLOCK_UFS2 - rdsize) / dev_bsize,
              rdsize) != 0) {
                free(fsrbuf);
                return (1);
        }
        /*
         * Recovery material has already been created, so do not
         * need to create it again.
         */
        fsr = (struct fsrecovery *)&fsrbuf[rdsize - sizeof *fsr];
        if (fsr->fsr_magic == FS_UFS2_MAGIC) {
                free(fsrbuf);
                return (1);
        }
        /*
         * Recovery material has not been created and can be if desired.
         */
        free(fsrbuf);
        return (0);
}

/*
 * Read the last filesystem-size piece of the boot block, replace the
 * last 20 bytes with the recovery information, then write it back.
 * The recovery information only works for UFS2 filesystems.
 */
static void
saverecovery(int readfd, int writefd)
{
        struct fsrecovery *fsr;
        char *fsrbuf;
        u_int secsize, rdsize;

        fsrbuf = NULL;
        rdsize = sblock.fs_fsize;
        if (sblock.fs_magic != FS_UFS2_MAGIC ||
            ioctl(readfd, DIOCGSECTORSIZE, &secsize) == -1 ||
            rdsize % secsize != 0 ||
            (fsrbuf = Balloc(rdsize)) == NULL ||
            blread(readfd, fsrbuf, (SBLOCK_UFS2 - rdsize) / dev_bsize,
              rdsize) != 0) {
                printf("RECOVERY DATA COULD NOT BE CREATED\n");
                free(fsrbuf);
                return;
        }
        fsr = (struct fsrecovery *)&fsrbuf[rdsize - sizeof *fsr];
        fsr->fsr_magic = sblock.fs_magic;
        fsr->fsr_fpg = sblock.fs_fpg;
        fsr->fsr_fsbtodb = sblock.fs_fsbtodb;
        fsr->fsr_sblkno = sblock.fs_sblkno;
        fsr->fsr_ncg = sblock.fs_ncg;
        blwrite(writefd, fsrbuf, (SBLOCK_UFS2 - rdsize) / dev_bsize, rdsize);
        free(fsrbuf);
}