355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * CDDL HEADER START
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * The contents of this file are subject to the terms of the
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * Common Development and Distribution License (the "License").
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * You may not use this file except in compliance with the License.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * See the License for the specific language governing permissions
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * and limitations under the License.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * When distributing Covered Code, include this CDDL HEADER in each
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * If applicable, add the following below this CDDL HEADER, with the
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * fields enclosed by brackets "[]" replaced with your own identifying
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * information: Portions Copyright [yyyy] [name of copyright owner]
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * CDDL HEADER END
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Use is subject to license terms.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox#pragma ident "%Z%%M% %I% %E% SMI"
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Keep track of duplicate fragment references (elsewhere called
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * blocks for ancient historical reasons).
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * The duplicates are kept in a binary tree to attempt to minimize
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * search times when checking the block lists of all active inodes
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * for multiple uses. This is opposed to using a simple linear list
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * that is traversed for every block, as is used in the traditional
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * fsck. It can be very time-expensive if there's more than just a
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * very few duplicates, and typically there are either none or lots.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * For each multiply-claimed fragment, we note all of the claiming
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * inodes and their corresponding logical block numbers. This allows
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * reporting exactly which parts of which files were damaged, which
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * provides at least a chance of recovering the bulk of the data on
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * a seriously-corrupted filesystem.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox#include <sys/fs/ufs_fsdir.h> /* for struct direct */
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox#define OFFSETOF(type, elt) ((size_t)(&((type *)NULL)->elt))
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * For each physical fragment with multiple claimants, the specifics
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * of each claim are recorded. This means there are N+1 AVL trees in
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * use: one for each fragment's claimant table, plus one that orders
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * the fragments themselves.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * The table of fragments simply has the physical fragment number
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * (pfn) and has the root of the tree of the associated claimants. It
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * is keyed by the pfn and called dup_frags.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * The subsidiary trees list inodes and logical fragment number (lfn)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * for each claimant. They are keyed first by inode number and then
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * by lfn. Both are needed, as it is possible for one inode to have
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * multiple claims on the same fragment.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic void report_dup_lfn_pfn(daddr32_t, daddr32_t, daddr32_t, daddr32_t);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic void invert_frags(avl_tree_t *, avl_tree_t *);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int by_ino_cmp(const void *, const void *);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int by_lfn_cmp(const void *, const void *);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic claimant_t *alloc_claimant(fsck_ino_t, daddr32_t);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int claimant_cmp(const void *, const void *);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int fragment_cmp(const void *, const void *);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int decrement_claimant(fragment_t *, fsck_ino_t, daddr32_t);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxstatic int increment_claimant(fragment_t *, fsck_ino_t, daddr32_t);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Simple accessor function for the outside world so only we need to
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * see and interpret our data structures.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Locates, creates, and deletes a record of a duplicate reference.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * For DB_INCR, returns true if the dup was added to the tree.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * For DB_DECR, returns true if the dup was in the tree.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxfind_dup_ref(daddr32_t fragno, fsck_ino_t ino, daddr32_t lfn, int flags)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox return (0);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox "adding claim by ino %d as lfn %d\n",
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Note that dup may be invalidated by this call.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox "check for claimant ino %d lfn %d returned %d\n",
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Dump the duplicates table in a relatively user-friendly form.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * The idea is that the output can be useful when trying to manually
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * work out which block belongs to which of the claiming inodes.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * What we have is a tree of duplicates indexed by physical
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * fragment number. What we want to report is:
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Inode %d:
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Logical Offset 0x%08llx, Physical Fragment %d
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Inode %d:
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Figure out how many actual dups are still around.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * This tells us whether or not we can mark the
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * filesystem clean.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Now report on every object that still exists that
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * had *any* dups associated with it.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox (void) puts("\nSome blocks that were found to be in "
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr "multiple files are still\nassigned to "
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr "file(s).\nFragments sorted by inode and "
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr "logical offsets:");
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox while ((dup = AVL_NEXT(&inode->id_fragments, dup)) != NULL) {
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox report_dup_lfn_pfn(first_lfn, last_lfn, first_pfn, last_pfn);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxreport_dup_lfn_pfn(daddr32_t first_lfn, daddr32_t last_lfn,
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox if ((first_lfn == last_lfn) && (first_pfn == last_pfn)) {
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox " Logical Offset 0x%08llx Physical Fragment %d\n",
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox (longlong_t)first_lfn * sblock.fs_fsize, first_pfn);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox " Logical Offsets 0x%08llx - 0x%08llx, "
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox "Physical Fragments %d - %d\n",
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Given a tree of fragment_ts, each element of which has an integral
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * sub-tree of claimant_ts, produce a tree of inode_dup_ts, each element
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * of which has an integral sub-tree of reference_ts.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox avl_create(target, by_ino_cmp, sizeof (inode_dup_t),
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Have we seen this inode before?
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox tgt_inode = avl_find(target, (void *)&tgt_inode_key,
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * No, so set up a record for it.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Now, how about this logical fragment? In
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * theory, we should never see a duplicate, since
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * a given lfn only exists once for a given inode.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * As such, we ignore duplicate hits.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Haven't seen it, add it.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox "invert_frags\n");
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Discard memory associated with the inverted fragments tree created
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * by report_dups() via invert_frags().
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox while ((inode_dup = avl_destroy_nodes(tree, &outer)) != NULL) {
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox while ((ref_dup = avl_destroy_nodes(&inode_dup->id_fragments,
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Discard all memory allocations associated with the current duplicates
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox while ((fragv = avl_destroy_nodes(&dup_frags, &dup_cookie)) != NULL) {
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox while ((claimv = avl_destroy_nodes(&fragv->fr_claimants,
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * If the given claimant has not been seen before, add it to DUP's
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * list of them. It's not fatal for the same PFN/INODE/LFN to get
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * added twice, because pass1b() will add the same dups that pass1()
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * did, plus one.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxincrement_claimant(fragment_t *dup, fsck_ino_t ino, daddr32_t lfn)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox claimant = avl_find(&dup->fr_claimants, &key, &where);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox avl_insert(&dup->fr_claimants, (void *)claimant, where);
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * If the inode is to be cleared and has zero links then remove
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * the zero link bit as it will be cleared anyway. If INZLINK
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * is being removed and it's a directory inode then add the
ce37393aa5dacd7677a7e930e35a5dead0b3d507owenr * inode to the orphan directory list.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * If the given claimant is on DUP's list, remove it. It is not
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * an error for the claimant to not be on the list.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcoxdecrement_claimant(fragment_t *dup, fsck_ino_t ino, daddr32_t lfn)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox claimant = avl_find(&dup->fr_claimants, &key, &where);
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox claimant_t *new = (claimant_t *)malloc(sizeof (claimant_t));
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox fragment_t *new = (fragment_t *)malloc(sizeof (fragment_t));
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox avl_create(&new->fr_claimants, claimant_cmp, sizeof (fragment_t),
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Compare two fragment_t instances for avl_find(). It requires a
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * return value of -1/0/1, so we can't just hand back left - right.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox else if (cmp > 0)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * Compare two claimant_t instances for avl_find(). It requires a
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * return value of -1/0/1, so we can't just hand back left - right.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox if (cmp == 0) {
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox * lfn < 0 is a wildcard lfn match.
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox else if (cmp > 0)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox else if (cmp > 0)
355d6bb5e62a215a9bcf820ac85c1fc62bed2f3fswilcox else if (cmp > 0)