/* * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2009, 2013 * The President and Fellows of Harvard College. * * 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 UNIVERSITY 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 UNIVERSITY 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 <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <err.h> #include "compat.h" #include <kern/sfs.h> #include "disk.h" #include "utils.h" #include "ibmacros.h" #include "sfs.h" #include "sb.h" #include "freemap.h" #include "inode.h" #include "passes.h" #include "main.h" static unsigned long count_dirs=0, count_files=0; /* * State for checking indirect blocks. */ struct ibstate { uint32_t ino; /* inode we're doing (constant) */ uint32_t curfileblock; /* current block offset in the file */ uint32_t fileblocks; /* file size in blocks (constant) */ uint32_t volblocks; /* volume size in blocks (constant) */ unsigned pasteofcount; /* number of blocks found past eof */ blockusage_t usagetype; /* how to call freemap_blockinuse() */ }; /* * Traverse an indirect block, recording blocks that are in use, * dropping any entries that are past EOF, and clearing any entries * that point outside the volume. * * XXX: this should be extended to be able to recover from crosslinked * blocks. Currently it just complains in freemap.c and sets * EXIT_UNRECOV. * * The traversal is recursive; the state is maintained in IBS (as * described above). IENTRY is a pointer to the entry in the parent * indirect block (or the inode) that names the block we're currently * scanning. IECHANGEDP should be set to 1 if *IENTRY is changed. * INDIRECTION is the indirection level of this block (1, 2, or 3). */ static void check_indirect_block(struct ibstate *ibs, uint32_t *ientry, int *iechangedp, int indirection) { uint32_t entries[SFS_DBPERIDB]; uint32_t i, ct; uint32_t coveredblocks; int localchanged = 0; int j; if (*ientry > 0 && *ientry < ibs->volblocks) { sfs_readindirect(*ientry, entries); freemap_blockinuse(*ientry, B_IBLOCK, ibs->ino); } else { if (*ientry >= ibs->volblocks) { setbadness(EXIT_RECOV); warnx("Inode %lu: indirect block pointer (level %d) " "for block %lu outside of volume: %lu " "(cleared)\n", (unsigned long)ibs->ino, indirection, (unsigned long)ibs->curfileblock, (unsigned long)*ientry); *ientry = 0; *iechangedp = 1; } coveredblocks = 1; for (j=0; j<indirection; j++) { coveredblocks *= SFS_DBPERIDB; } ibs->curfileblock += coveredblocks; return; } if (indirection > 1) { for (i=0; i<SFS_DBPERIDB; i++) { check_indirect_block(ibs, &entries[i], &localchanged, indirection-1); } } else { assert(indirection==1); for (i=0; i<SFS_DBPERIDB; i++) { if (entries[i] >= ibs->volblocks) { setbadness(EXIT_RECOV); warnx("Inode %lu: direct block pointer for " "block %lu outside of volume: %lu " "(cleared)\n", (unsigned long)ibs->ino, (unsigned long)ibs->curfileblock, (unsigned long)entries[i]); entries[i] = 0; localchanged = 1; } else if (entries[i] != 0) { if (ibs->curfileblock < ibs->fileblocks) { freemap_blockinuse(entries[i], ibs->usagetype, ibs->ino); } else { setbadness(EXIT_RECOV); ibs->pasteofcount++; freemap_blockfree(entries[i]); entries[i] = 0; localchanged = 1; } } ibs->curfileblock++; } } ct=0; for (i=ct=0; i<SFS_DBPERIDB; i++) { if (entries[i]!=0) ct++; } if (ct==0) { if (*ientry != 0) { setbadness(EXIT_RECOV); /* this is not necessarily correct */ /*ibs->pasteofcount++;*/ *iechangedp = 1; freemap_blockfree(*ientry); *ientry = 0; } } else { assert(*ientry != 0); if (localchanged) { sfs_writeindirect(*ientry, entries); } } } /* * Check the blocks belonging to inode INO, whose inode has already * been loaded into SFI. ISDIR is a shortcut telling us if the inode * is a directory. * * Returns nonzero if SFI has been modified and needs to be written * back. */ static int check_inode_blocks(uint32_t ino, struct sfs_dinode *sfi, int isdir) { struct ibstate ibs; uint32_t size, datablock; int changed; int i; size = SFS_ROUNDUP(sfi->sfi_size, SFS_BLOCKSIZE); ibs.ino = ino; /*ibs.curfileblock = 0;*/ ibs.fileblocks = size/SFS_BLOCKSIZE; ibs.volblocks = sb_totalblocks(); ibs.pasteofcount = 0; ibs.usagetype = isdir ? B_DIRDATA : B_DATA; changed = 0; for (ibs.curfileblock=0; ibs.curfileblock<NUM_D; ibs.curfileblock++) { datablock = GET_D(sfi, ibs.curfileblock); if (datablock >= ibs.volblocks) { setbadness(EXIT_RECOV); warnx("Inode %lu: direct block pointer for " "block %lu outside of volume: %lu " "(cleared)\n", (unsigned long)ibs.ino, (unsigned long)ibs.curfileblock, (unsigned long)datablock); SET_D(sfi, ibs.curfileblock) = 0; changed = 1; } else if (datablock > 0) { if (ibs.curfileblock < ibs.fileblocks) { freemap_blockinuse(datablock, ibs.usagetype, ibs.ino); } else { setbadness(EXIT_RECOV); ibs.pasteofcount++; changed = 1; freemap_blockfree(datablock); SET_D(sfi, ibs.curfileblock) = 0; } } } for (i=0; i<NUM_I; i++) { check_indirect_block(&ibs, &SET_I(sfi, i), &changed, 1); } for (i=0; i<NUM_II; i++) { check_indirect_block(&ibs, &SET_II(sfi, i), &changed, 2); } for (i=0; i<NUM_III; i++) { check_indirect_block(&ibs, &SET_III(sfi, i), &changed, 3); } if (ibs.pasteofcount > 0) { warnx("Inode %lu: %u blocks after EOF (freed)", (unsigned long) ibs.ino, ibs.pasteofcount); setbadness(EXIT_RECOV); } return changed; } /* * Do the pass1 inode-level checks on inode INO, which has already * been loaded into SFI. Note that sfi_type has already been * validated. * * Returns nonzero if SFI has been modified and needs to be written * back. */ static int pass1_inode(uint32_t ino, struct sfs_dinode *sfi, int alreadychanged) { int changed = alreadychanged; int isdir = sfi->sfi_type == SFS_TYPE_DIR; if (inode_add(ino, sfi->sfi_type)) { /* Already been here. */ assert(changed == 0); return 1; } freemap_blockinuse(ino, B_INODE, ino); if (checkzeroed(sfi->sfi_waste, sizeof(sfi->sfi_waste))) { warnx("Inode %lu: sfi_waste section not zeroed (fixed)", (unsigned long) ino); setbadness(EXIT_RECOV); changed = 1; } if (check_inode_blocks(ino, sfi, isdir)) { changed = 1; } if (changed) { sfs_writeinode(ino, sfi); } return 0; } /* * Check the directory entry in SFD. INDEX is its offset, and PATH is * its name; these are used for printing messages. */ static int pass1_direntry(const char *path, uint32_t index, struct sfs_direntry *sfd) { int dchanged = 0; uint32_t nblocks; nblocks = sb_totalblocks(); if (sfd->sfd_ino == SFS_NOINO) { if (sfd->sfd_name[0] != 0) { setbadness(EXIT_RECOV); warnx("Directory %s entry %lu has name but no file", path, (unsigned long) index); sfd->sfd_name[0] = 0; dchanged = 1; } } else if (sfd->sfd_ino >= nblocks) { setbadness(EXIT_RECOV); warnx("Directory %s entry %lu has out of range " "inode (cleared)", path, (unsigned long) index); sfd->sfd_ino = SFS_NOINO; sfd->sfd_name[0] = 0; dchanged = 1; } else { if (sfd->sfd_name[0] == 0) { /* XXX: what happens if FSCK.n.m already exists? */ snprintf(sfd->sfd_name, sizeof(sfd->sfd_name), "FSCK.%lu.%lu", (unsigned long) sfd->sfd_ino, (unsigned long) uniqueid()); setbadness(EXIT_RECOV); warnx("Directory %s entry %lu has file but " "no name (fixed: %s)", path, (unsigned long) index, sfd->sfd_name); dchanged = 1; } if (checknullstring(sfd->sfd_name, sizeof(sfd->sfd_name))) { setbadness(EXIT_RECOV); warnx("Directory %s entry %lu not " "null-terminated (fixed)", path, (unsigned long) index); dchanged = 1; } if (checkbadstring(sfd->sfd_name)) { setbadness(EXIT_RECOV); warnx("Directory %s entry %lu contains invalid " "characters (fixed)", path, (unsigned long) index); dchanged = 1; } } return dchanged; } /* * Check a directory. INO is the inode number; PATHSOFAR is the path * to this directory. This traverses the volume directory tree * recursively. */ static void pass1_dir(uint32_t ino, const char *pathsofar) { struct sfs_dinode sfi; struct sfs_direntry *direntries; uint32_t ndirentries, i; int ichanged=0, dchanged=0; sfs_readinode(ino, &sfi); if (sfi.sfi_size % sizeof(struct sfs_direntry) != 0) { setbadness(EXIT_RECOV); warnx("Directory %s has illegal size %lu (fixed)", pathsofar, (unsigned long) sfi.sfi_size); sfi.sfi_size = SFS_ROUNDUP(sfi.sfi_size, sizeof(struct sfs_direntry)); ichanged = 1; } count_dirs++; if (pass1_inode(ino, &sfi, ichanged)) { /* been here before; crosslinked dir, sort it out in pass 2 */ return; } ndirentries = sfi.sfi_size/sizeof(struct sfs_direntry); direntries = domalloc(sfi.sfi_size); sfs_readdir(&sfi, direntries, ndirentries); for (i=0; i<ndirentries; i++) { if (pass1_direntry(pathsofar, i, &direntries[i])) { dchanged = 1; } } for (i=0; i<ndirentries; i++) { if (direntries[i].sfd_ino == SFS_NOINO) { /* nothing */ } else if (!strcmp(direntries[i].sfd_name, ".")) { /* nothing */ } else if (!strcmp(direntries[i].sfd_name, "..")) { /* nothing */ } else { char path[strlen(pathsofar)+SFS_NAMELEN+1]; struct sfs_dinode subsfi; uint32_t subino; subino = direntries[i].sfd_ino; sfs_readinode(subino, &subsfi); snprintf(path, sizeof(path), "%s/%s", pathsofar, direntries[i].sfd_name); switch (subsfi.sfi_type) { case SFS_TYPE_FILE: if (pass1_inode(subino, &subsfi, 0)) { /* been here before */ break; } count_files++; break; case SFS_TYPE_DIR: pass1_dir(subino, path); break; default: setbadness(EXIT_RECOV); warnx("Object %s: Invalid inode type " "(removed)", path); direntries[i].sfd_ino = SFS_NOINO; direntries[i].sfd_name[0] = 0; dchanged = 1; break; } } } if (dchanged) { sfs_writedir(&sfi, direntries, ndirentries); } free(direntries); } /* * Check the root directory, and implicitly everything under it. */ static void pass1_rootdir(void) { struct sfs_dinode sfi; char path[SFS_VOLNAME_SIZE + 2]; sfs_readinode(SFS_ROOTDIR_INO, &sfi); switch (sfi.sfi_type) { case SFS_TYPE_DIR: break; case SFS_TYPE_FILE: warnx("Root directory inode is a regular file (fixed)"); goto fix; default: warnx("Root directory inode has invalid type %lu (fixed)", (unsigned long) sfi.sfi_type); fix: setbadness(EXIT_RECOV); sfi.sfi_type = SFS_TYPE_DIR; sfs_writeinode(SFS_ROOTDIR_INO, &sfi); break; } snprintf(path, sizeof(path), "%s:", sb_volname()); pass1_dir(SFS_ROOTDIR_INO, path); } //////////////////////////////////////////////////////////// // public interface void pass1(void) { pass1_rootdir(); } unsigned long pass1_founddirs(void) { return count_dirs; } unsigned long pass1_foundfiles(void) { return count_files; }