1*355d6bb5Sswilcox /* 2*355d6bb5Sswilcox * CDDL HEADER START 3*355d6bb5Sswilcox * 4*355d6bb5Sswilcox * The contents of this file are subject to the terms of the 5*355d6bb5Sswilcox * Common Development and Distribution License, Version 1.0 only 6*355d6bb5Sswilcox * (the "License"). You may not use this file except in compliance 7*355d6bb5Sswilcox * with the License. 8*355d6bb5Sswilcox * 9*355d6bb5Sswilcox * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*355d6bb5Sswilcox * or http://www.opensolaris.org/os/licensing. 11*355d6bb5Sswilcox * See the License for the specific language governing permissions 12*355d6bb5Sswilcox * and limitations under the License. 13*355d6bb5Sswilcox * 14*355d6bb5Sswilcox * When distributing Covered Code, include this CDDL HEADER in each 15*355d6bb5Sswilcox * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*355d6bb5Sswilcox * If applicable, add the following below this CDDL HEADER, with the 17*355d6bb5Sswilcox * fields enclosed by brackets "[]" replaced with your own identifying 18*355d6bb5Sswilcox * information: Portions Copyright [yyyy] [name of copyright owner] 19*355d6bb5Sswilcox * 20*355d6bb5Sswilcox * CDDL HEADER END 21*355d6bb5Sswilcox */ 22*355d6bb5Sswilcox /* 23*355d6bb5Sswilcox * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24*355d6bb5Sswilcox * Use is subject to license terms. 25*355d6bb5Sswilcox */ 26*355d6bb5Sswilcox 27*355d6bb5Sswilcox #pragma ident "%Z%%M% %I% %E% SMI" 28*355d6bb5Sswilcox 29*355d6bb5Sswilcox /* 30*355d6bb5Sswilcox * Keep track of duplicate fragment references (elsewhere called 31*355d6bb5Sswilcox * blocks for ancient historical reasons). 32*355d6bb5Sswilcox * 33*355d6bb5Sswilcox * The duplicates are kept in a binary tree to attempt to minimize 34*355d6bb5Sswilcox * search times when checking the block lists of all active inodes 35*355d6bb5Sswilcox * for multiple uses. This is opposed to using a simple linear list 36*355d6bb5Sswilcox * that is traversed for every block, as is used in the traditional 37*355d6bb5Sswilcox * fsck. It can be very time-expensive if there's more than just a 38*355d6bb5Sswilcox * very few duplicates, and typically there are either none or lots. 39*355d6bb5Sswilcox * 40*355d6bb5Sswilcox * For each multiply-claimed fragment, we note all of the claiming 41*355d6bb5Sswilcox * inodes and their corresponding logical block numbers. This allows 42*355d6bb5Sswilcox * reporting exactly which parts of which files were damaged, which 43*355d6bb5Sswilcox * provides at least a chance of recovering the bulk of the data on 44*355d6bb5Sswilcox * a seriously-corrupted filesystem. 45*355d6bb5Sswilcox */ 46*355d6bb5Sswilcox #include <stdio.h> 47*355d6bb5Sswilcox #include <stdlib.h> 48*355d6bb5Sswilcox #include <unistd.h> 49*355d6bb5Sswilcox #include <sys/avl.h> 50*355d6bb5Sswilcox #define _KERNEL 51*355d6bb5Sswilcox #include <sys/fs/ufs_fsdir.h> /* for struct direct */ 52*355d6bb5Sswilcox #undef _KERNEL 53*355d6bb5Sswilcox #include <sys/debug.h> 54*355d6bb5Sswilcox #include "fsck.h" 55*355d6bb5Sswilcox 56*355d6bb5Sswilcox #define OFFSETOF(type, elt) ((size_t)(&((type *)NULL)->elt)) 57*355d6bb5Sswilcox 58*355d6bb5Sswilcox /* 59*355d6bb5Sswilcox * For each physical fragment with multiple claimants, the specifics 60*355d6bb5Sswilcox * of each claim are recorded. This means there are N+1 AVL trees in 61*355d6bb5Sswilcox * use: one for each fragment's claimant table, plus one that orders 62*355d6bb5Sswilcox * the fragments themselves. 63*355d6bb5Sswilcox * 64*355d6bb5Sswilcox * The table of fragments simply has the physical fragment number 65*355d6bb5Sswilcox * (pfn) and has the root of the tree of the associated claimants. It 66*355d6bb5Sswilcox * is keyed by the pfn and called dup_frags. 67*355d6bb5Sswilcox * 68*355d6bb5Sswilcox * The subsidiary trees list inodes and logical fragment number (lfn) 69*355d6bb5Sswilcox * for each claimant. They are keyed first by inode number and then 70*355d6bb5Sswilcox * by lfn. Both are needed, as it is possible for one inode to have 71*355d6bb5Sswilcox * multiple claims on the same fragment. 72*355d6bb5Sswilcox */ 73*355d6bb5Sswilcox 74*355d6bb5Sswilcox typedef struct claimant { 75*355d6bb5Sswilcox fsck_ino_t cl_inode; 76*355d6bb5Sswilcox daddr32_t cl_lfn; 77*355d6bb5Sswilcox avl_node_t cl_avl; 78*355d6bb5Sswilcox } claimant_t; 79*355d6bb5Sswilcox 80*355d6bb5Sswilcox typedef struct fragment { 81*355d6bb5Sswilcox daddr32_t fr_pfn; 82*355d6bb5Sswilcox avl_tree_t fr_claimants; 83*355d6bb5Sswilcox avl_node_t fr_avl; 84*355d6bb5Sswilcox } fragment_t; 85*355d6bb5Sswilcox 86*355d6bb5Sswilcox typedef struct reference { 87*355d6bb5Sswilcox daddr32_t ref_lfn; 88*355d6bb5Sswilcox daddr32_t ref_pfn; 89*355d6bb5Sswilcox avl_node_t ref_avl; 90*355d6bb5Sswilcox } reference_t; 91*355d6bb5Sswilcox 92*355d6bb5Sswilcox typedef struct inode_dup { 93*355d6bb5Sswilcox fsck_ino_t id_ino; 94*355d6bb5Sswilcox avl_tree_t id_fragments; 95*355d6bb5Sswilcox avl_node_t id_avl; 96*355d6bb5Sswilcox } inode_dup_t; 97*355d6bb5Sswilcox 98*355d6bb5Sswilcox static avl_tree_t dup_frags; 99*355d6bb5Sswilcox 100*355d6bb5Sswilcox static void free_invert_frags(avl_tree_t *); 101*355d6bb5Sswilcox static void report_dup_lfn_pfn(daddr32_t, daddr32_t, daddr32_t, daddr32_t); 102*355d6bb5Sswilcox static inode_dup_t *new_inode_dup(fsck_ino_t); 103*355d6bb5Sswilcox static void invert_frags(avl_tree_t *, avl_tree_t *); 104*355d6bb5Sswilcox static void report_inode_dups(inode_dup_t *); 105*355d6bb5Sswilcox static int by_ino_cmp(const void *, const void *); 106*355d6bb5Sswilcox static int by_lfn_cmp(const void *, const void *); 107*355d6bb5Sswilcox static claimant_t *alloc_claimant(fsck_ino_t, daddr32_t); 108*355d6bb5Sswilcox static fragment_t *alloc_dup(daddr32_t); 109*355d6bb5Sswilcox static int claimant_cmp(const void *, const void *); 110*355d6bb5Sswilcox static int fragment_cmp(const void *, const void *); 111*355d6bb5Sswilcox static int decrement_claimant(fragment_t *, fsck_ino_t, daddr32_t); 112*355d6bb5Sswilcox static int increment_claimant(fragment_t *, fsck_ino_t, daddr32_t); 113*355d6bb5Sswilcox 114*355d6bb5Sswilcox /* 115*355d6bb5Sswilcox * Simple accessor function for the outside world so only we need to 116*355d6bb5Sswilcox * see and interpret our data structures. 117*355d6bb5Sswilcox */ 118*355d6bb5Sswilcox int 119*355d6bb5Sswilcox have_dups(void) 120*355d6bb5Sswilcox { 121*355d6bb5Sswilcox return (avl_numnodes(&dup_frags) > 0); 122*355d6bb5Sswilcox } 123*355d6bb5Sswilcox 124*355d6bb5Sswilcox /* 125*355d6bb5Sswilcox * Locates, creates, and deletes a record of a duplicate reference. 126*355d6bb5Sswilcox * 127*355d6bb5Sswilcox * For DB_INCR, returns true if the dup was added to the tree. 128*355d6bb5Sswilcox * For DB_DECR, returns true if the dup was in the tree. 129*355d6bb5Sswilcox */ 130*355d6bb5Sswilcox int 131*355d6bb5Sswilcox find_dup_ref(daddr32_t fragno, fsck_ino_t ino, daddr32_t lfn, int flags) 132*355d6bb5Sswilcox { 133*355d6bb5Sswilcox fragment_t key; 134*355d6bb5Sswilcox fragment_t *dup; 135*355d6bb5Sswilcox avl_index_t where; 136*355d6bb5Sswilcox int added = 0; 137*355d6bb5Sswilcox int removed = 0; 138*355d6bb5Sswilcox 139*355d6bb5Sswilcox if (avl_first(&dup_frags) == NULL) { 140*355d6bb5Sswilcox if (flags & DB_CREATE) 141*355d6bb5Sswilcox avl_create(&dup_frags, fragment_cmp, 142*355d6bb5Sswilcox sizeof (fragment_t), 143*355d6bb5Sswilcox OFFSETOF(fragment_t, fr_avl)); 144*355d6bb5Sswilcox else 145*355d6bb5Sswilcox return (0); 146*355d6bb5Sswilcox } 147*355d6bb5Sswilcox 148*355d6bb5Sswilcox key.fr_pfn = fragno; 149*355d6bb5Sswilcox dup = avl_find(&dup_frags, (void *)&key, &where); 150*355d6bb5Sswilcox if ((dup == NULL) & (flags & DB_CREATE)) { 151*355d6bb5Sswilcox dup = alloc_dup(fragno); 152*355d6bb5Sswilcox avl_insert(&dup_frags, (void *)dup, where); 153*355d6bb5Sswilcox } 154*355d6bb5Sswilcox 155*355d6bb5Sswilcox if (dup != NULL) { 156*355d6bb5Sswilcox if (flags & DB_INCR) { 157*355d6bb5Sswilcox if (debug) 158*355d6bb5Sswilcox (void) printf( 159*355d6bb5Sswilcox "adding claim by ino %d as lfn %d\n", 160*355d6bb5Sswilcox ino, lfn); 161*355d6bb5Sswilcox added = increment_claimant(dup, ino, lfn); 162*355d6bb5Sswilcox } else if (flags & DB_DECR) { 163*355d6bb5Sswilcox /* 164*355d6bb5Sswilcox * Note that dup may be invalidated by this call. 165*355d6bb5Sswilcox */ 166*355d6bb5Sswilcox removed = decrement_claimant(dup, ino, lfn); 167*355d6bb5Sswilcox if (debug) 168*355d6bb5Sswilcox (void) printf( 169*355d6bb5Sswilcox "check for claimant ino %d lfn %d returned %d\n", 170*355d6bb5Sswilcox ino, lfn, removed); 171*355d6bb5Sswilcox } 172*355d6bb5Sswilcox } 173*355d6bb5Sswilcox 174*355d6bb5Sswilcox return (added || removed || (dup != NULL)); 175*355d6bb5Sswilcox } 176*355d6bb5Sswilcox 177*355d6bb5Sswilcox /* 178*355d6bb5Sswilcox * Dump the duplicates table in a relatively user-friendly form. 179*355d6bb5Sswilcox * The idea is that the output can be useful when trying to manually 180*355d6bb5Sswilcox * work out which block belongs to which of the claiming inodes. 181*355d6bb5Sswilcox * 182*355d6bb5Sswilcox * What we have is a tree of duplicates indexed by physical 183*355d6bb5Sswilcox * fragment number. What we want to report is: 184*355d6bb5Sswilcox * 185*355d6bb5Sswilcox * Inode %d: 186*355d6bb5Sswilcox * Logical Offset 0x%08llx, Physical Fragment %d 187*355d6bb5Sswilcox * Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d 188*355d6bb5Sswilcox * ... 189*355d6bb5Sswilcox * Inode %d: 190*355d6bb5Sswilcox * Logical Offsets 0x%08llx - 0x%08llx, Physical Fragments %d - %d 191*355d6bb5Sswilcox * ... 192*355d6bb5Sswilcox */ 193*355d6bb5Sswilcox int 194*355d6bb5Sswilcox report_dups(int quiet) 195*355d6bb5Sswilcox { 196*355d6bb5Sswilcox int overlaps; 197*355d6bb5Sswilcox inode_dup_t *inode; 198*355d6bb5Sswilcox fragment_t *dup; 199*355d6bb5Sswilcox avl_tree_t inode_frags; 200*355d6bb5Sswilcox 201*355d6bb5Sswilcox overlaps = 0; 202*355d6bb5Sswilcox ASSERT(have_dups()); 203*355d6bb5Sswilcox /* 204*355d6bb5Sswilcox * Figure out how many actual dups are still around. 205*355d6bb5Sswilcox * This tells us whether or not we can mark the 206*355d6bb5Sswilcox * filesystem clean. 207*355d6bb5Sswilcox */ 208*355d6bb5Sswilcox dup = avl_first(&dup_frags); 209*355d6bb5Sswilcox while (dup != NULL) { 210*355d6bb5Sswilcox if (avl_numnodes(&dup->fr_claimants) > 1) { 211*355d6bb5Sswilcox overlaps++; 212*355d6bb5Sswilcox break; 213*355d6bb5Sswilcox } 214*355d6bb5Sswilcox dup = AVL_NEXT(&dup_frags, dup); 215*355d6bb5Sswilcox } 216*355d6bb5Sswilcox 217*355d6bb5Sswilcox /* 218*355d6bb5Sswilcox * Now report on every object that still exists that 219*355d6bb5Sswilcox * had *any* dups associated with it. 220*355d6bb5Sswilcox */ 221*355d6bb5Sswilcox if (!quiet) { 222*355d6bb5Sswilcox (void) puts("\nSome blocks that were found to be in " 223*355d6bb5Sswilcox "multiple files are still\nassigned to " 224*355d6bb5Sswilcox "file(s).\nFragments sorted by inode and " 225*355d6bb5Sswilcox "logical offsets:"); 226*355d6bb5Sswilcox 227*355d6bb5Sswilcox invert_frags(&dup_frags, &inode_frags); 228*355d6bb5Sswilcox inode = avl_first(&inode_frags); 229*355d6bb5Sswilcox while (inode != NULL) { 230*355d6bb5Sswilcox report_inode_dups(inode); 231*355d6bb5Sswilcox inode = AVL_NEXT(&inode_frags, inode); 232*355d6bb5Sswilcox } 233*355d6bb5Sswilcox (void) printf("\n"); 234*355d6bb5Sswilcox 235*355d6bb5Sswilcox free_invert_frags(&inode_frags); 236*355d6bb5Sswilcox } 237*355d6bb5Sswilcox 238*355d6bb5Sswilcox return (overlaps); 239*355d6bb5Sswilcox } 240*355d6bb5Sswilcox 241*355d6bb5Sswilcox static void 242*355d6bb5Sswilcox report_inode_dups(inode_dup_t *inode) 243*355d6bb5Sswilcox { 244*355d6bb5Sswilcox reference_t *dup; 245*355d6bb5Sswilcox daddr32_t first_lfn, last_lfn, first_pfn, last_pfn; 246*355d6bb5Sswilcox 247*355d6bb5Sswilcox (void) printf("Inode %d:\n", inode->id_ino); 248*355d6bb5Sswilcox dup = avl_first(&inode->id_fragments); 249*355d6bb5Sswilcox first_lfn = last_lfn = dup->ref_lfn; 250*355d6bb5Sswilcox first_pfn = last_pfn = dup->ref_pfn; 251*355d6bb5Sswilcox while ((dup = AVL_NEXT(&inode->id_fragments, dup)) != NULL) { 252*355d6bb5Sswilcox if (((last_lfn + 1) != dup->ref_lfn) || 253*355d6bb5Sswilcox ((last_pfn + 1) != dup->ref_pfn)) { 254*355d6bb5Sswilcox report_dup_lfn_pfn(first_lfn, last_lfn, 255*355d6bb5Sswilcox first_pfn, last_pfn); 256*355d6bb5Sswilcox first_lfn = last_lfn = dup->ref_lfn; 257*355d6bb5Sswilcox first_pfn = last_pfn = dup->ref_pfn; 258*355d6bb5Sswilcox } 259*355d6bb5Sswilcox } 260*355d6bb5Sswilcox report_dup_lfn_pfn(first_lfn, last_lfn, first_pfn, last_pfn); 261*355d6bb5Sswilcox } 262*355d6bb5Sswilcox 263*355d6bb5Sswilcox static void 264*355d6bb5Sswilcox report_dup_lfn_pfn(daddr32_t first_lfn, daddr32_t last_lfn, 265*355d6bb5Sswilcox daddr32_t first_pfn, daddr32_t last_pfn) 266*355d6bb5Sswilcox { 267*355d6bb5Sswilcox if ((first_lfn == last_lfn) && (first_pfn == last_pfn)) { 268*355d6bb5Sswilcox (void) printf( 269*355d6bb5Sswilcox " Logical Offset 0x%08llx Physical Fragment %d\n", 270*355d6bb5Sswilcox (longlong_t)first_lfn * sblock.fs_fsize, first_pfn); 271*355d6bb5Sswilcox } else { 272*355d6bb5Sswilcox (void) printf( 273*355d6bb5Sswilcox " Logical Offsets 0x%08llx - 0x%08llx, " 274*355d6bb5Sswilcox "Physical Fragments %d - %d\n", 275*355d6bb5Sswilcox (longlong_t)first_lfn * sblock.fs_fsize, 276*355d6bb5Sswilcox (longlong_t)last_lfn * sblock.fs_fsize, 277*355d6bb5Sswilcox first_pfn, last_pfn); 278*355d6bb5Sswilcox } 279*355d6bb5Sswilcox } 280*355d6bb5Sswilcox 281*355d6bb5Sswilcox /* 282*355d6bb5Sswilcox * Given a tree of fragment_ts, each element of which has an integral 283*355d6bb5Sswilcox * sub-tree of claimant_ts, produce a tree of inode_dup_ts, each element 284*355d6bb5Sswilcox * of which has an integral sub-tree of reference_ts. 285*355d6bb5Sswilcox */ 286*355d6bb5Sswilcox static void 287*355d6bb5Sswilcox invert_frags(avl_tree_t *source, avl_tree_t *target) 288*355d6bb5Sswilcox { 289*355d6bb5Sswilcox fragment_t *src_frag; 290*355d6bb5Sswilcox claimant_t *src_claim; 291*355d6bb5Sswilcox inode_dup_t *tgt_inode; 292*355d6bb5Sswilcox inode_dup_t tgt_inode_key; 293*355d6bb5Sswilcox reference_t *tgt_ref; 294*355d6bb5Sswilcox reference_t tgt_ref_key; 295*355d6bb5Sswilcox avl_index_t where; 296*355d6bb5Sswilcox 297*355d6bb5Sswilcox avl_create(target, by_ino_cmp, sizeof (inode_dup_t), 298*355d6bb5Sswilcox OFFSETOF(inode_dup_t, id_avl)); 299*355d6bb5Sswilcox 300*355d6bb5Sswilcox src_frag = avl_first(source); 301*355d6bb5Sswilcox while (src_frag != NULL) { 302*355d6bb5Sswilcox src_claim = avl_first(&src_frag->fr_claimants); 303*355d6bb5Sswilcox while (src_claim != NULL) { 304*355d6bb5Sswilcox /* 305*355d6bb5Sswilcox * Have we seen this inode before? 306*355d6bb5Sswilcox */ 307*355d6bb5Sswilcox tgt_inode_key.id_ino = src_claim->cl_inode; 308*355d6bb5Sswilcox tgt_inode = avl_find(target, (void *)&tgt_inode_key, 309*355d6bb5Sswilcox &where); 310*355d6bb5Sswilcox if (tgt_inode == NULL) { 311*355d6bb5Sswilcox /* 312*355d6bb5Sswilcox * No, so set up a record for it. 313*355d6bb5Sswilcox */ 314*355d6bb5Sswilcox tgt_inode = new_inode_dup(src_claim->cl_inode); 315*355d6bb5Sswilcox avl_insert(target, (void *)tgt_inode, where); 316*355d6bb5Sswilcox } 317*355d6bb5Sswilcox /* 318*355d6bb5Sswilcox * Now, how about this logical fragment? In 319*355d6bb5Sswilcox * theory, we should never see a duplicate, since 320*355d6bb5Sswilcox * a given lfn only exists once for a given inode. 321*355d6bb5Sswilcox * As such, we ignore duplicate hits. 322*355d6bb5Sswilcox */ 323*355d6bb5Sswilcox tgt_ref_key.ref_lfn = src_claim->cl_lfn; 324*355d6bb5Sswilcox tgt_ref = avl_find(&tgt_inode->id_fragments, 325*355d6bb5Sswilcox (void *)&tgt_ref_key, &where); 326*355d6bb5Sswilcox if (tgt_ref == NULL) { 327*355d6bb5Sswilcox /* 328*355d6bb5Sswilcox * Haven't seen it, add it. 329*355d6bb5Sswilcox */ 330*355d6bb5Sswilcox tgt_ref = (reference_t *)malloc( 331*355d6bb5Sswilcox sizeof (reference_t)); 332*355d6bb5Sswilcox if (tgt_ref == NULL) 333*355d6bb5Sswilcox errexit("Out of memory in " 334*355d6bb5Sswilcox "invert_frags\n"); 335*355d6bb5Sswilcox tgt_ref->ref_lfn = src_claim->cl_lfn; 336*355d6bb5Sswilcox tgt_ref->ref_pfn = src_frag->fr_pfn; 337*355d6bb5Sswilcox avl_insert(&tgt_inode->id_fragments, 338*355d6bb5Sswilcox (void *)tgt_ref, where); 339*355d6bb5Sswilcox } 340*355d6bb5Sswilcox src_claim = AVL_NEXT(&src_frag->fr_claimants, 341*355d6bb5Sswilcox src_claim); 342*355d6bb5Sswilcox } 343*355d6bb5Sswilcox src_frag = AVL_NEXT(source, src_frag); 344*355d6bb5Sswilcox } 345*355d6bb5Sswilcox } 346*355d6bb5Sswilcox 347*355d6bb5Sswilcox /* 348*355d6bb5Sswilcox * Discard memory associated with the inverted fragments tree created 349*355d6bb5Sswilcox * by report_dups() via invert_frags(). 350*355d6bb5Sswilcox */ 351*355d6bb5Sswilcox static void 352*355d6bb5Sswilcox free_invert_frags(avl_tree_t *tree) 353*355d6bb5Sswilcox { 354*355d6bb5Sswilcox void *outer = NULL; /* traversal cookie */ 355*355d6bb5Sswilcox void *inner; /* traversal cookie */ 356*355d6bb5Sswilcox inode_dup_t *inode_dup; 357*355d6bb5Sswilcox reference_t *ref_dup; 358*355d6bb5Sswilcox 359*355d6bb5Sswilcox while ((inode_dup = avl_destroy_nodes(tree, &outer)) != NULL) { 360*355d6bb5Sswilcox inner = NULL; 361*355d6bb5Sswilcox while ((ref_dup = avl_destroy_nodes(&inode_dup->id_fragments, 362*355d6bb5Sswilcox &inner)) != NULL) { 363*355d6bb5Sswilcox free((void *)ref_dup); 364*355d6bb5Sswilcox } 365*355d6bb5Sswilcox avl_destroy(&inode_dup->id_fragments); 366*355d6bb5Sswilcox free((void *)inode_dup); 367*355d6bb5Sswilcox } 368*355d6bb5Sswilcox avl_destroy(tree); 369*355d6bb5Sswilcox } 370*355d6bb5Sswilcox 371*355d6bb5Sswilcox /* 372*355d6bb5Sswilcox * Discard all memory allocations associated with the current duplicates 373*355d6bb5Sswilcox * table. 374*355d6bb5Sswilcox */ 375*355d6bb5Sswilcox void 376*355d6bb5Sswilcox free_dup_state(void) 377*355d6bb5Sswilcox { 378*355d6bb5Sswilcox void *dup_cookie = NULL; 379*355d6bb5Sswilcox void *claim_cookie; 380*355d6bb5Sswilcox fragment_t *fragv; 381*355d6bb5Sswilcox claimant_t *claimv; 382*355d6bb5Sswilcox 383*355d6bb5Sswilcox while ((fragv = avl_destroy_nodes(&dup_frags, &dup_cookie)) != NULL) { 384*355d6bb5Sswilcox claim_cookie = NULL; 385*355d6bb5Sswilcox while ((claimv = avl_destroy_nodes(&fragv->fr_claimants, 386*355d6bb5Sswilcox &claim_cookie)) != NULL) { 387*355d6bb5Sswilcox free((void *)claimv); 388*355d6bb5Sswilcox } 389*355d6bb5Sswilcox avl_destroy(&fragv->fr_claimants); 390*355d6bb5Sswilcox free((void *)fragv); 391*355d6bb5Sswilcox } 392*355d6bb5Sswilcox avl_destroy(&dup_frags); 393*355d6bb5Sswilcox } 394*355d6bb5Sswilcox 395*355d6bb5Sswilcox /* 396*355d6bb5Sswilcox * If the given claimant has not been seen before, add it to DUP's 397*355d6bb5Sswilcox * list of them. It's not fatal for the same PFN/INODE/LFN to get 398*355d6bb5Sswilcox * added twice, because pass1b() will add the same dups that pass1() 399*355d6bb5Sswilcox * did, plus one. 400*355d6bb5Sswilcox */ 401*355d6bb5Sswilcox static int 402*355d6bb5Sswilcox increment_claimant(fragment_t *dup, fsck_ino_t ino, daddr32_t lfn) 403*355d6bb5Sswilcox { 404*355d6bb5Sswilcox avl_index_t where; 405*355d6bb5Sswilcox claimant_t *claimant; 406*355d6bb5Sswilcox claimant_t key; 407*355d6bb5Sswilcox int added = 0; 408*355d6bb5Sswilcox 409*355d6bb5Sswilcox key.cl_inode = ino; 410*355d6bb5Sswilcox key.cl_lfn = lfn; 411*355d6bb5Sswilcox claimant = avl_find(&dup->fr_claimants, &key, &where); 412*355d6bb5Sswilcox if (claimant == NULL) { 413*355d6bb5Sswilcox if (debug) 414*355d6bb5Sswilcox (void) printf("inserting claimant\n"); 415*355d6bb5Sswilcox claimant = alloc_claimant(ino, lfn); 416*355d6bb5Sswilcox avl_insert(&dup->fr_claimants, (void *)claimant, where); 417*355d6bb5Sswilcox statemap[ino] |= INCLEAR; 418*355d6bb5Sswilcox added = 1; 419*355d6bb5Sswilcox } 420*355d6bb5Sswilcox 421*355d6bb5Sswilcox return (added); 422*355d6bb5Sswilcox } 423*355d6bb5Sswilcox 424*355d6bb5Sswilcox /* 425*355d6bb5Sswilcox * If the given claimant is on DUP's list, remove it. It is not 426*355d6bb5Sswilcox * an error for the claimant to not be on the list. 427*355d6bb5Sswilcox */ 428*355d6bb5Sswilcox static int 429*355d6bb5Sswilcox decrement_claimant(fragment_t *dup, fsck_ino_t ino, daddr32_t lfn) 430*355d6bb5Sswilcox { 431*355d6bb5Sswilcox avl_index_t where; 432*355d6bb5Sswilcox claimant_t *claimant; 433*355d6bb5Sswilcox claimant_t key; 434*355d6bb5Sswilcox int busy = 0; 435*355d6bb5Sswilcox 436*355d6bb5Sswilcox key.cl_inode = ino; 437*355d6bb5Sswilcox key.cl_lfn = lfn; 438*355d6bb5Sswilcox claimant = avl_find(&dup->fr_claimants, &key, &where); 439*355d6bb5Sswilcox if (claimant != NULL) { 440*355d6bb5Sswilcox avl_remove(&dup->fr_claimants, claimant); 441*355d6bb5Sswilcox if (avl_numnodes(&dup->fr_claimants) == 0) { 442*355d6bb5Sswilcox avl_destroy(&dup->fr_claimants); 443*355d6bb5Sswilcox avl_remove(&dup_frags, (void *)dup); 444*355d6bb5Sswilcox free((void *)dup); 445*355d6bb5Sswilcox } else { 446*355d6bb5Sswilcox busy = 1; 447*355d6bb5Sswilcox } 448*355d6bb5Sswilcox } 449*355d6bb5Sswilcox 450*355d6bb5Sswilcox return (busy); 451*355d6bb5Sswilcox } 452*355d6bb5Sswilcox 453*355d6bb5Sswilcox static claimant_t * 454*355d6bb5Sswilcox alloc_claimant(fsck_ino_t inode, daddr32_t lfn) 455*355d6bb5Sswilcox { 456*355d6bb5Sswilcox claimant_t *new = (claimant_t *)malloc(sizeof (claimant_t)); 457*355d6bb5Sswilcox 458*355d6bb5Sswilcox if (new == NULL) 459*355d6bb5Sswilcox errexit("Out of memory in alloc_claimant()\n"); 460*355d6bb5Sswilcox 461*355d6bb5Sswilcox new->cl_inode = inode; 462*355d6bb5Sswilcox new->cl_lfn = lfn; 463*355d6bb5Sswilcox 464*355d6bb5Sswilcox return (new); 465*355d6bb5Sswilcox } 466*355d6bb5Sswilcox 467*355d6bb5Sswilcox static fragment_t * 468*355d6bb5Sswilcox alloc_dup(daddr32_t pfn) 469*355d6bb5Sswilcox { 470*355d6bb5Sswilcox fragment_t *new = (fragment_t *)malloc(sizeof (fragment_t)); 471*355d6bb5Sswilcox 472*355d6bb5Sswilcox if (new == NULL) 473*355d6bb5Sswilcox errexit("Out of memory in alloc_dup()\n"); 474*355d6bb5Sswilcox 475*355d6bb5Sswilcox new->fr_pfn = pfn; 476*355d6bb5Sswilcox avl_create(&new->fr_claimants, claimant_cmp, sizeof (fragment_t), 477*355d6bb5Sswilcox OFFSETOF(claimant_t, cl_avl)); 478*355d6bb5Sswilcox 479*355d6bb5Sswilcox return (new); 480*355d6bb5Sswilcox } 481*355d6bb5Sswilcox 482*355d6bb5Sswilcox /* 483*355d6bb5Sswilcox * Compare two fragment_t instances for avl_find(). It requires a 484*355d6bb5Sswilcox * return value of -1/0/1, so we can't just hand back left - right. 485*355d6bb5Sswilcox */ 486*355d6bb5Sswilcox static int 487*355d6bb5Sswilcox fragment_cmp(const void *vlp, const void *vrp) 488*355d6bb5Sswilcox { 489*355d6bb5Sswilcox const fragment_t *lp = (const fragment_t *)vlp; 490*355d6bb5Sswilcox const fragment_t *rp = (const fragment_t *)vrp; 491*355d6bb5Sswilcox int cmp = lp->fr_pfn - rp->fr_pfn; 492*355d6bb5Sswilcox 493*355d6bb5Sswilcox if (cmp < 0) 494*355d6bb5Sswilcox cmp = -1; 495*355d6bb5Sswilcox else if (cmp > 0) 496*355d6bb5Sswilcox cmp = 1; 497*355d6bb5Sswilcox 498*355d6bb5Sswilcox return (cmp); 499*355d6bb5Sswilcox } 500*355d6bb5Sswilcox 501*355d6bb5Sswilcox /* 502*355d6bb5Sswilcox * Compare two claimant_t instances for avl_find(). It requires a 503*355d6bb5Sswilcox * return value of -1/0/1, so we can't just hand back left - right. 504*355d6bb5Sswilcox */ 505*355d6bb5Sswilcox static int 506*355d6bb5Sswilcox claimant_cmp(const void *vlp, const void *vrp) 507*355d6bb5Sswilcox { 508*355d6bb5Sswilcox const claimant_t *lp = (const claimant_t *)vlp; 509*355d6bb5Sswilcox const claimant_t *rp = (const claimant_t *)vrp; 510*355d6bb5Sswilcox int cmp; 511*355d6bb5Sswilcox 512*355d6bb5Sswilcox cmp = lp->cl_inode - rp->cl_inode; 513*355d6bb5Sswilcox if (cmp == 0) { 514*355d6bb5Sswilcox /* 515*355d6bb5Sswilcox * lfn < 0 is a wildcard lfn match. 516*355d6bb5Sswilcox */ 517*355d6bb5Sswilcox if ((lp->cl_lfn >= 0) && (rp->cl_lfn >= 0)) 518*355d6bb5Sswilcox cmp = lp->cl_lfn - rp->cl_lfn; 519*355d6bb5Sswilcox } 520*355d6bb5Sswilcox 521*355d6bb5Sswilcox if (cmp < 0) 522*355d6bb5Sswilcox cmp = -1; 523*355d6bb5Sswilcox else if (cmp > 0) 524*355d6bb5Sswilcox cmp = 1; 525*355d6bb5Sswilcox 526*355d6bb5Sswilcox return (cmp); 527*355d6bb5Sswilcox } 528*355d6bb5Sswilcox 529*355d6bb5Sswilcox static int 530*355d6bb5Sswilcox by_ino_cmp(const void *vlp, const void *vrp) 531*355d6bb5Sswilcox { 532*355d6bb5Sswilcox const inode_dup_t *lp = (const inode_dup_t *)vlp; 533*355d6bb5Sswilcox const inode_dup_t *rp = (const inode_dup_t *)vrp; 534*355d6bb5Sswilcox int cmp; 535*355d6bb5Sswilcox 536*355d6bb5Sswilcox cmp = lp->id_ino - rp->id_ino; 537*355d6bb5Sswilcox 538*355d6bb5Sswilcox if (cmp < 0) 539*355d6bb5Sswilcox cmp = -1; 540*355d6bb5Sswilcox else if (cmp > 0) 541*355d6bb5Sswilcox cmp = 1; 542*355d6bb5Sswilcox 543*355d6bb5Sswilcox return (cmp); 544*355d6bb5Sswilcox } 545*355d6bb5Sswilcox 546*355d6bb5Sswilcox static int 547*355d6bb5Sswilcox by_lfn_cmp(const void *vlp, const void *vrp) 548*355d6bb5Sswilcox { 549*355d6bb5Sswilcox const reference_t *lp = (const reference_t *)vlp; 550*355d6bb5Sswilcox const reference_t *rp = (const reference_t *)vrp; 551*355d6bb5Sswilcox int cmp; 552*355d6bb5Sswilcox 553*355d6bb5Sswilcox cmp = lp->ref_lfn - rp->ref_lfn; 554*355d6bb5Sswilcox 555*355d6bb5Sswilcox if (cmp < 0) 556*355d6bb5Sswilcox cmp = -1; 557*355d6bb5Sswilcox else if (cmp > 0) 558*355d6bb5Sswilcox cmp = 1; 559*355d6bb5Sswilcox 560*355d6bb5Sswilcox return (cmp); 561*355d6bb5Sswilcox } 562*355d6bb5Sswilcox 563*355d6bb5Sswilcox static inode_dup_t * 564*355d6bb5Sswilcox new_inode_dup(fsck_ino_t inode) 565*355d6bb5Sswilcox { 566*355d6bb5Sswilcox inode_dup_t *new; 567*355d6bb5Sswilcox 568*355d6bb5Sswilcox new = (inode_dup_t *)malloc(sizeof (inode_dup_t)); 569*355d6bb5Sswilcox if (new == NULL) 570*355d6bb5Sswilcox errexit("Out of memory in new_inode_dup\n"); 571*355d6bb5Sswilcox new->id_ino = inode; 572*355d6bb5Sswilcox avl_create(&new->id_fragments, by_lfn_cmp, sizeof (reference_t), 573*355d6bb5Sswilcox OFFSETOF(reference_t, ref_avl)); 574*355d6bb5Sswilcox 575*355d6bb5Sswilcox return (new); 576*355d6bb5Sswilcox } 577