xref: /illumos-gate/usr/src/cmd/fs.d/ufs/fsck/dup_avl.c (revision ce37393a)
1355d6bb5Sswilcox /*
2355d6bb5Sswilcox  * CDDL HEADER START
3355d6bb5Sswilcox  *
4355d6bb5Sswilcox  * The contents of this file are subject to the terms of the
5*ce37393aSowenr  * Common Development and Distribution License (the "License").
6*ce37393aSowenr  * You may not use this file except in compliance with the License.
7355d6bb5Sswilcox  *
8355d6bb5Sswilcox  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9355d6bb5Sswilcox  * or http://www.opensolaris.org/os/licensing.
10355d6bb5Sswilcox  * See the License for the specific language governing permissions
11355d6bb5Sswilcox  * and limitations under the License.
12355d6bb5Sswilcox  *
13355d6bb5Sswilcox  * When distributing Covered Code, include this CDDL HEADER in each
14355d6bb5Sswilcox  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15355d6bb5Sswilcox  * If applicable, add the following below this CDDL HEADER, with the
16355d6bb5Sswilcox  * fields enclosed by brackets "[]" replaced with your own identifying
17355d6bb5Sswilcox  * information: Portions Copyright [yyyy] [name of copyright owner]
18355d6bb5Sswilcox  *
19355d6bb5Sswilcox  * CDDL HEADER END
20355d6bb5Sswilcox  */
21355d6bb5Sswilcox /*
22*ce37393aSowenr  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23355d6bb5Sswilcox  * Use is subject to license terms.
24355d6bb5Sswilcox  */
26355d6bb5Sswilcox #pragma ident	"%Z%%M%	%I%	%E% SMI"
28355d6bb5Sswilcox /*
29355d6bb5Sswilcox  * Keep track of duplicate fragment references (elsewhere called
30355d6bb5Sswilcox  * blocks for ancient historical reasons).
31355d6bb5Sswilcox  *
32355d6bb5Sswilcox  * The duplicates are kept in a binary tree to attempt to minimize
33355d6bb5Sswilcox  * search times when checking the block lists of all active inodes
34355d6bb5Sswilcox  * for multiple uses.  This is opposed to using a simple linear list
35355d6bb5Sswilcox  * that is traversed for every block, as is used in the traditional
36355d6bb5Sswilcox  * fsck.  It can be very time-expensive if there's more than just a
37355d6bb5Sswilcox  * very few duplicates, and typically there are either none or lots.
38355d6bb5Sswilcox  *
39355d6bb5Sswilcox  * For each multiply-claimed fragment, we note all of the claiming
40355d6bb5Sswilcox  * inodes and their corresponding logical block numbers.  This allows
41355d6bb5Sswilcox  * reporting exactly which parts of which files were damaged, which
42355d6bb5Sswilcox  * provides at least a chance of recovering the bulk of the data on
43355d6bb5Sswilcox  * a seriously-corrupted filesystem.
44355d6bb5Sswilcox  */
45355d6bb5Sswilcox #include <stdio.h>
46355d6bb5Sswilcox #include <stdlib.h>
47355d6bb5Sswilcox #include <unistd.h>
48355d6bb5Sswilcox #include <sys/avl.h>
49355d6bb5Sswilcox #define	_KERNEL
50355d6bb5Sswilcox #include <sys/fs/ufs_fsdir.h>	/* for struct direct */
51355d6bb5Sswilcox #undef _KERNEL
52355d6bb5Sswilcox #include <sys/debug.h>
53355d6bb5Sswilcox #include "fsck.h"
55355d6bb5Sswilcox #define	OFFSETOF(type, elt) ((size_t)(&((type *)NULL)->elt))
57355d6bb5Sswilcox /*
58355d6bb5Sswilcox  * For each physical fragment with multiple claimants, the specifics
59355d6bb5Sswilcox  * of each claim are recorded. This means there are N+1 AVL trees in
60355d6bb5Sswilcox  * use: one for each fragment's claimant table, plus one that orders
61355d6bb5Sswilcox  * the fragments themselves.
62355d6bb5Sswilcox  *
63355d6bb5Sswilcox  * The table of fragments simply has the physical fragment number
64355d6bb5Sswilcox  * (pfn) and has the root of the tree of the associated claimants.  It
65355d6bb5Sswilcox  * is keyed by the pfn and called dup_frags.
66355d6bb5Sswilcox  *
67355d6bb5Sswilcox  * The subsidiary trees list inodes and logical fragment number (lfn)
68355d6bb5Sswilcox  * for each claimant.  They are keyed first by inode number and then
69355d6bb5Sswilcox  * by lfn.  Both are needed, as it is possible for one inode to have
70355d6bb5Sswilcox  * multiple claims on the same fragment.
71355d6bb5Sswilcox  */
73355d6bb5Sswilcox typedef struct claimant {
74355d6bb5Sswilcox 	fsck_ino_t cl_inode;
75355d6bb5Sswilcox 	daddr32_t cl_lfn;
76355d6bb5Sswilcox 	avl_node_t cl_avl;
77355d6bb5Sswilcox } claimant_t;
79355d6bb5Sswilcox typedef struct fragment {
80355d6bb5Sswilcox 	daddr32_t fr_pfn;
81355d6bb5Sswilcox 	avl_tree_t fr_claimants;
82355d6bb5Sswilcox 	avl_node_t fr_avl;
83355d6bb5Sswilcox } fragment_t;
85355d6bb5Sswilcox typedef struct reference {
86355d6bb5Sswilcox 	daddr32_t ref_lfn;
87355d6bb5Sswilcox 	daddr32_t ref_pfn;
88355d6bb5Sswilcox 	avl_node_t ref_avl;
89355d6bb5Sswilcox } reference_t;
91355d6bb5Sswilcox typedef struct inode_dup {
92355d6bb5Sswilcox 	fsck_ino_t id_ino;
93355d6bb5Sswilcox 	avl_tree_t id_fragments;
94355d6bb5Sswilcox 	avl_node_t id_avl;
95355d6bb5Sswilcox } inode_dup_t;
97355d6bb5Sswilcox static avl_tree_t dup_frags;
99355d6bb5Sswilcox static void free_invert_frags(avl_tree_t *);
100355d6bb5Sswilcox static void report_dup_lfn_pfn(daddr32_t, daddr32_t, daddr32_t, daddr32_t);
101355d6bb5Sswilcox static inode_dup_t *new_inode_dup(fsck_ino_t);
102355d6bb5Sswilcox static void invert_frags(avl_tree_t *, avl_tree_t *);
103355d6bb5Sswilcox static void report_inode_dups(inode_dup_t *);
104355d6bb5Sswilcox static int by_ino_cmp(const void *, const void *);
105355d6bb5Sswilcox static int by_lfn_cmp(const void *, const void *);
106355d6bb5Sswilcox static claimant_t *alloc_claimant(fsck_ino_t, daddr32_t);
107355d6bb5Sswilcox static fragment_t *alloc_dup(daddr32_t);
108355d6bb5Sswilcox static int claimant_cmp(const void *, const void *);
109355d6bb5Sswilcox static int fragment_cmp(const void *, const void *);
110355d6bb5Sswilcox static int decrement_claimant(fragment_t *, fsck_ino_t, daddr32_t);
111355d6bb5Sswilcox static int increment_claimant(fragment_t *, fsck_ino_t, daddr32_t);
113355d6bb5Sswilcox /*
114355d6bb5Sswilcox  * Simple accessor function for the outside world so only we need to
115355d6bb5Sswilcox  * see and interpret our data structures.
116355d6bb5Sswilcox  */
117355d6bb5Sswilcox int
have_dups(void)118355d6bb5Sswilcox have_dups(void)
119355d6bb5Sswilcox {
120355d6bb5Sswilcox 	return (avl_numnodes(&dup_frags) > 0);
121355d6bb5Sswilcox }
123355d6bb5Sswilcox /*
124355d6bb5Sswilcox  * Locates, creates, and deletes a record of a duplicate reference.
125355d6bb5Sswilcox  *
126355d6bb5Sswilcox  * For DB_INCR, returns true if the dup was added to the tree.
127355d6bb5Sswilcox  * For DB_DECR, returns true if the dup was in the tree.
128355d6bb5Sswilcox  */
129355d6bb5Sswilcox int
find_dup_ref(daddr32_t fragno,fsck_ino_t ino,daddr32_t lfn,int flags)130355d6bb5Sswilcox find_dup_ref(daddr32_t fragno, fsck_ino_t ino, daddr32_t lfn, int flags)
131355d6bb5Sswilcox {
132355d6bb5Sswilcox 	fragment_t key;
133355d6bb5Sswilcox 	fragment_t *dup;
134355d6bb5Sswilcox 	avl_index_t where;
135355d6bb5Sswilcox 	int added = 0;
136355d6bb5Sswilcox 	int removed = 0;
138355d6bb5Sswilcox 	if (avl_first(&dup_frags) == NULL) {
139355d6bb5Sswilcox 		if (flags & DB_CREATE)
140355d6bb5Sswilcox 			avl_create(&dup_frags, fragment_cmp,
141355d6bb5Sswilcox 			    sizeof (fragment_t),
142355d6bb5Sswilcox 			    OFFSETOF(fragment_t, fr_avl));
143355d6bb5Sswilcox 		else
144355d6bb5Sswilcox 			return (0);
145355d6bb5Sswilcox 	}
147355d6bb5Sswilcox 	key.fr_pfn = fragno;
148355d6bb5Sswilcox 	dup = avl_find(&dup_frags, (void *)&key, &where);
149355d6bb5Sswilcox 	if ((dup == NULL) & (flags & DB_CREATE)) {
150355d6bb5Sswilcox 		dup = alloc_dup(fragno);
151355d6bb5Sswilcox 		avl_insert(&dup_frags, (void *)dup, where);
152355d6bb5Sswilcox 	}
154355d6bb5Sswilcox 	if (dup != NULL) {
155355d6bb5Sswilcox 		if (flags & DB_INCR) {
156355d6bb5Sswilcox 			if (debug)
157355d6bb5Sswilcox 				(void) printf(
158355d6bb5Sswilcox 				    "adding claim by ino %d as lfn %d\n",
159355d6bb5Sswilcox 				    ino, lfn);
160355d6bb5Sswilcox 			added = increment_claimant(dup, ino, lfn);
161355d6bb5Sswilcox 		} else if (flags & DB_DECR) {
162355d6bb5Sswilcox 			/*
163355d6bb5Sswilcox 			 * Note that dup may be invalidated by this call.
164355d6bb5Sswilcox 			 */
165355d6bb5Sswilcox 			removed = decrement_claimant(dup, ino, lfn);
166355d6bb5Sswilcox 			if (debug)
167355d6bb5Sswilcox 				(void) printf(
168355d6bb5Sswilcox 		    "check for claimant ino %d lfn %d returned %d\n",
169355d6bb5Sswilcox 				    ino, lfn, removed);
170355d6bb5Sswilcox 		}
171355d6bb5Sswilcox 	}
173355d6bb5Sswilcox 	return (added || removed || (dup != NULL));
174355d6bb5Sswilcox }
176355d6bb5Sswilcox /*
177355d6bb5Sswilcox  * Dump the duplicates table in a relatively user-friendly form.
178355d6bb5Sswilcox  * The idea is that the output can be useful when trying to manually
179355d6bb5Sswilcox  * work out which block belongs to which of the claiming inodes.
180355d6bb5Sswilcox  *
181355d6bb5Sswilcox  * What we have is a tree of duplicates indexed by physical
182355d6bb5Sswilcox  * fragment number.  What we want to report is:
183355d6bb5Sswilcox  *
184355d6bb5Sswilcox  *    Inode %d:
185355d6bb5Sswilcox  *        Logical Offset 0x%08llx,             Physical Fragment  %d
186355d6bb5Sswilcox  *        Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d
187355d6bb5Sswilcox  *        ...
188355d6bb5Sswilcox  *    Inode %d:
189355d6bb5Sswilcox  *        Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d
190355d6bb5Sswilcox  *    ...
191355d6bb5Sswilcox  */
192355d6bb5Sswilcox int
report_dups(int quiet)193355d6bb5Sswilcox report_dups(int quiet)
194355d6bb5Sswilcox {
195355d6bb5Sswilcox 	int overlaps;
196355d6bb5Sswilcox 	inode_dup_t *inode;
197355d6bb5Sswilcox 	fragment_t *dup;
198355d6bb5Sswilcox 	avl_tree_t inode_frags;
200355d6bb5Sswilcox 	overlaps = 0;
201355d6bb5Sswilcox 	ASSERT(have_dups());
202355d6bb5Sswilcox 	/*
203355d6bb5Sswilcox 	 * Figure out how many actual dups are still around.
204355d6bb5Sswilcox 	 * This tells us whether or not we can mark the
205355d6bb5Sswilcox 	 * filesystem clean.
206355d6bb5Sswilcox 	 */
207355d6bb5Sswilcox 	dup = avl_first(&dup_frags);
208355d6bb5Sswilcox 	while (dup != NULL) {
209355d6bb5Sswilcox 		if (avl_numnodes(&dup->fr_claimants) > 1) {
210355d6bb5Sswilcox 			overlaps++;
211355d6bb5Sswilcox 			break;
212355d6bb5Sswilcox 		}
213355d6bb5Sswilcox 		dup = AVL_NEXT(&dup_frags, dup);
214355d6bb5Sswilcox 	}
216355d6bb5Sswilcox 	/*
217355d6bb5Sswilcox 	 * Now report on every object that still exists that
218355d6bb5Sswilcox 	 * had *any* dups associated with it.
219355d6bb5Sswilcox 	 */
220355d6bb5Sswilcox 	if (!quiet) {
221355d6bb5Sswilcox 		(void) puts("\nSome blocks that were found to be in "
222*ce37393aSowenr 		    "multiple files are still\nassigned to "
223*ce37393aSowenr 		    "file(s).\nFragments sorted by inode and "
224*ce37393aSowenr 		    "logical offsets:");
226355d6bb5Sswilcox 		invert_frags(&dup_frags, &inode_frags);
227355d6bb5Sswilcox 		inode = avl_first(&inode_frags);
228355d6bb5Sswilcox 		while (inode != NULL) {
229355d6bb5Sswilcox 			report_inode_dups(inode);
230355d6bb5Sswilcox 			inode = AVL_NEXT(&inode_frags, inode);
231355d6bb5Sswilcox 		}
232355d6bb5Sswilcox 		(void) printf("\n");
234355d6bb5Sswilcox 		free_invert_frags(&inode_frags);
235355d6bb5Sswilcox 	}
237355d6bb5Sswilcox 	return (overlaps);
238355d6bb5Sswilcox }
240355d6bb5Sswilcox static void
report_inode_dups(inode_dup_t * inode)241355d6bb5Sswilcox report_inode_dups(inode_dup_t *inode)
242355d6bb5Sswilcox {
243355d6bb5Sswilcox 	reference_t *dup;
244355d6bb5Sswilcox 	daddr32_t first_lfn, last_lfn, first_pfn, last_pfn;
246355d6bb5Sswilcox 	(void) printf("Inode %d:\n", inode->id_ino);
247355d6bb5Sswilcox 	dup = avl_first(&inode->id_fragments);
248355d6bb5Sswilcox 	first_lfn = last_lfn = dup->ref_lfn;
249355d6bb5Sswilcox 	first_pfn = last_pfn = dup->ref_pfn;
250355d6bb5Sswilcox 	while ((dup = AVL_NEXT(&inode->id_fragments, dup)) != NULL) {
251355d6bb5Sswilcox 		if (((last_lfn + 1) != dup->ref_lfn) ||
252355d6bb5Sswilcox 		    ((last_pfn + 1) != dup->ref_pfn)) {
253355d6bb5Sswilcox 			report_dup_lfn_pfn(first_lfn, last_lfn,
254355d6bb5Sswilcox 			    first_pfn, last_pfn);
255355d6bb5Sswilcox 			first_lfn = last_lfn = dup->ref_lfn;
256355d6bb5Sswilcox 			first_pfn = last_pfn = dup->ref_pfn;
257355d6bb5Sswilcox 		}
258355d6bb5Sswilcox 	}
259355d6bb5Sswilcox 	report_dup_lfn_pfn(first_lfn, last_lfn, first_pfn, last_pfn);
260355d6bb5Sswilcox }
262355d6bb5Sswilcox static void
report_dup_lfn_pfn(daddr32_t first_lfn,daddr32_t last_lfn,daddr32_t first_pfn,daddr32_t last_pfn)263355d6bb5Sswilcox report_dup_lfn_pfn(daddr32_t first_lfn, daddr32_t last_lfn,
264355d6bb5Sswilcox 	daddr32_t first_pfn, daddr32_t last_pfn)
265355d6bb5Sswilcox {
266355d6bb5Sswilcox 	if ((first_lfn == last_lfn) && (first_pfn == last_pfn)) {
267355d6bb5Sswilcox 		(void) printf(
268355d6bb5Sswilcox 	    "  Logical Offset  0x%08llx               Physical Fragment  %d\n",
269355d6bb5Sswilcox 		    (longlong_t)first_lfn * sblock.fs_fsize, first_pfn);
270355d6bb5Sswilcox 	} else {
271355d6bb5Sswilcox 		(void) printf(
272355d6bb5Sswilcox 		    "  Logical Offsets 0x%08llx - 0x%08llx, "
273355d6bb5Sswilcox 		    "Physical Fragments %d - %d\n",
274355d6bb5Sswilcox 		    (longlong_t)first_lfn * sblock.fs_fsize,
275355d6bb5Sswilcox 		    (longlong_t)last_lfn * sblock.fs_fsize,
276355d6bb5Sswilcox 		    first_pfn, last_pfn);
277355d6bb5Sswilcox 	}
278355d6bb5Sswilcox }
280355d6bb5Sswilcox /*
281355d6bb5Sswilcox  * Given a tree of fragment_ts, each element of which has an integral
282355d6bb5Sswilcox  * sub-tree of claimant_ts, produce a tree of inode_dup_ts, each element
283355d6bb5Sswilcox  * of which has an integral sub-tree of reference_ts.
284355d6bb5Sswilcox  */
285355d6bb5Sswilcox static void
invert_frags(avl_tree_t * source,avl_tree_t * target)286355d6bb5Sswilcox invert_frags(avl_tree_t *source, avl_tree_t *target)
287355d6bb5Sswilcox {
288355d6bb5Sswilcox 	fragment_t *src_frag;
289355d6bb5Sswilcox 	claimant_t *src_claim;
290355d6bb5Sswilcox 	inode_dup_t *tgt_inode;
291355d6bb5Sswilcox 	inode_dup_t tgt_inode_key;
292355d6bb5Sswilcox 	reference_t *tgt_ref;
293355d6bb5Sswilcox 	reference_t tgt_ref_key;
294355d6bb5Sswilcox 	avl_index_t where;
296355d6bb5Sswilcox 	avl_create(target, by_ino_cmp, sizeof (inode_dup_t),
297355d6bb5Sswilcox 	    OFFSETOF(inode_dup_t, id_avl));
299355d6bb5Sswilcox 	src_frag = avl_first(source);
300355d6bb5Sswilcox 	while (src_frag != NULL) {
301355d6bb5Sswilcox 		src_claim = avl_first(&src_frag->fr_claimants);
302355d6bb5Sswilcox 		while (src_claim != NULL) {
303355d6bb5Sswilcox 			/*
304355d6bb5Sswilcox 			 * Have we seen this inode before?
305355d6bb5Sswilcox 			 */
306355d6bb5Sswilcox 			tgt_inode_key.id_ino = src_claim->cl_inode;
307355d6bb5Sswilcox 			tgt_inode = avl_find(target, (void *)&tgt_inode_key,
308355d6bb5Sswilcox 			    &where);
309355d6bb5Sswilcox 			if (tgt_inode == NULL) {
310355d6bb5Sswilcox 				/*
311355d6bb5Sswilcox 				 * No, so set up a record for it.
312355d6bb5Sswilcox 				 */
313355d6bb5Sswilcox 				tgt_inode = new_inode_dup(src_claim->cl_inode);
314355d6bb5Sswilcox 				avl_insert(target, (void *)tgt_inode, where);
315355d6bb5Sswilcox 			}
316355d6bb5Sswilcox 			/*
317355d6bb5Sswilcox 			 * Now, how about this logical fragment?  In
318355d6bb5Sswilcox 			 * theory, we should never see a duplicate, since
319355d6bb5Sswilcox 			 * a given lfn only exists once for a given inode.
320355d6bb5Sswilcox 			 * As such, we ignore duplicate hits.
321355d6bb5Sswilcox 			 */
322355d6bb5Sswilcox 			tgt_ref_key.ref_lfn = src_claim->cl_lfn;
323355d6bb5Sswilcox 			tgt_ref = avl_find(&tgt_inode->id_fragments,
324355d6bb5Sswilcox 			    (void *)&tgt_ref_key, &where);
325355d6bb5Sswilcox 			if (tgt_ref == NULL) {
326355d6bb5Sswilcox 				/*
327355d6bb5Sswilcox 				 * Haven't seen it, add it.
328355d6bb5Sswilcox 				 */
329355d6bb5Sswilcox 				tgt_ref = (reference_t *)malloc(
330355d6bb5Sswilcox 				    sizeof (reference_t));
331355d6bb5Sswilcox 				if (tgt_ref == NULL)
332355d6bb5Sswilcox 					errexit("Out of memory in "
333355d6bb5Sswilcox 					    "invert_frags\n");
334355d6bb5Sswilcox 				tgt_ref->ref_lfn = src_claim->cl_lfn;
335355d6bb5Sswilcox 				tgt_ref->ref_pfn = src_frag->fr_pfn;
336355d6bb5Sswilcox 				avl_insert(&tgt_inode->id_fragments,
337355d6bb5Sswilcox 				    (void *)tgt_ref, where);
338355d6bb5Sswilcox 			}
339355d6bb5Sswilcox 			src_claim = AVL_NEXT(&src_frag->fr_claimants,
340355d6bb5Sswilcox 			    src_claim);
341355d6bb5Sswilcox 		}
342355d6bb5Sswilcox 		src_frag = AVL_NEXT(source, src_frag);
343355d6bb5Sswilcox 	}
344355d6bb5Sswilcox }
346355d6bb5Sswilcox /*
347355d6bb5Sswilcox  * Discard memory associated with the inverted fragments tree created
348355d6bb5Sswilcox  * by report_dups() via invert_frags().
349355d6bb5Sswilcox  */
350355d6bb5Sswilcox static void
free_invert_frags(avl_tree_t * tree)351355d6bb5Sswilcox free_invert_frags(avl_tree_t *tree)
352355d6bb5Sswilcox {
353355d6bb5Sswilcox 	void *outer = NULL;	/* traversal cookie */
354355d6bb5Sswilcox 	void *inner;		/* traversal cookie */
355355d6bb5Sswilcox 	inode_dup_t *inode_dup;
356355d6bb5Sswilcox 	reference_t *ref_dup;
358355d6bb5Sswilcox 	while ((inode_dup = avl_destroy_nodes(tree, &outer)) != NULL) {
359355d6bb5Sswilcox 		inner = NULL;
360355d6bb5Sswilcox 		while ((ref_dup = avl_destroy_nodes(&inode_dup->id_fragments,
361355d6bb5Sswilcox 		    &inner)) != NULL) {
362355d6bb5Sswilcox 			free((void *)ref_dup);
363355d6bb5Sswilcox 		}
364355d6bb5Sswilcox 		avl_destroy(&inode_dup->id_fragments);
365355d6bb5Sswilcox 		free((void *)inode_dup);
366355d6bb5Sswilcox 	}
367355d6bb5Sswilcox 	avl_destroy(tree);
368355d6bb5Sswilcox }
370355d6bb5Sswilcox /*
371355d6bb5Sswilcox  * Discard all memory allocations associated with the current duplicates
372355d6bb5Sswilcox  * table.
373355d6bb5Sswilcox  */
374355d6bb5Sswilcox void
free_dup_state(void)375355d6bb5Sswilcox free_dup_state(void)
376355d6bb5Sswilcox {
377355d6bb5Sswilcox 	void *dup_cookie = NULL;