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