pass2a.c revision 355d6bb5e62a215a9bcf820ac85c1fc62bed2f3f
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Use is subject to license terms.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/* Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/* All Rights Reserved */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Copyright (c) 1980, 1986, 1990 The Regents of the University of California.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * All rights reserved.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling *
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Redistribution and use in source and binary forms are permitted
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * provided that: (1) source distributions retain this entire copyright
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * notice and comment, and (2) distributions including binaries display
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * the following acknowledgement: ``This product includes software
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * developed by the University of California, Berkeley and its contributors''
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * in the documentation or other materials provided with the distribution
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * and in all advertising materials mentioning features or use of this
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * software. Neither the name of the University nor the names of its
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * contributors may be used to endorse or promote products derived
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * from this software without specific prior written permission.
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
8c04a1fa3f7d569d48fe9b5342d0bd4c533179b9Gary Mills * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#pragma ident "%Z%%M% %I% %E% SMI"
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <stdio.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <stdlib.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <strings.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <sys/types.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <sys/fs/ufs_fs.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include <sys/fs/ufs_fsdir.h>
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling#include "fsck.h"
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/* XXX should convert pass2a to using avl tree */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Directory contents table is keyed first by name length, and
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * then the actual name.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingtypedef struct dirtree {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling caddr_t name;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling int len;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling fsck_ino_t ino;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling} dirtree_t;
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Tree of contents of directory currently being traversed.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Elements are pointers to dirtree_t instances.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling */
7802d7bf98dec568dadf72286893b1fe5abd8602Matthew Ahrensstatic void *contents;
7802d7bf98dec568dadf72286893b1fe5abd8602Matthew Ahrens
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingstatic int pass2acheck(struct inodesc *);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingstatic void discard_contents(void);
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrensstatic int dirtree_cmp(const void *, const void *);
1825bc56e5a1f7ef6f0dc3137f3b35f5850c1100Nav Ravindranath
1825bc56e5a1f7ef6f0dc3137f3b35f5850c1100Nav Ravindranath/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Make sure directories don't contain duplicate names.
44ecc5327ab4ce0750dcca2a17e05566bf2812e2George Wilson */
44ecc5327ab4ce0750dcca2a17e05566bf2812e2George Wilsonvoid
44ecc5327ab4ce0750dcca2a17e05566bf2812e2George Wilsonpass2a(void)
44ecc5327ab4ce0750dcca2a17e05566bf2812e2George Wilson{
44ecc5327ab4ce0750dcca2a17e05566bf2812e2George Wilson struct inodesc idesc;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling struct inoinfo *inp, **inpp, **inpend;
cde58dbc6a23d4d38db7c8866312be83221c765fMatthew Ahrens struct dinode *dp;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling inpend = &inpsort[inplast];
7fd05ac4dec0c343d2f68f310d3718b715ecfbafMatthew Ahrens for (inpp = inpsort; inpp < inpend; inpp++) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling inp = *inpp;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
af3465da8fa420c4ec701e3e57704d537a6f755bMax Grossman if (inp->i_isize == 0)
af3465da8fa420c4ec701e3e57704d537a6f755bMax Grossman continue;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling /* != DSTATE also covers case of == USTATE */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (((statemap[inp->i_number] & STMASK) != DSTATE) ||
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling ((statemap[inp->i_number] & INCLEAR) == INCLEAR))
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling continue;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling dp = ginode(inp->i_number);
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson init_inodesc(&idesc);
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson idesc.id_filesize = dp->di_size;
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson idesc.id_type = DATA;
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson idesc.id_func = pass2acheck;
139510fb6efa97dbe5f5479594b308d940cab8d1George Wilson idesc.id_number = inp->i_number;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling idesc.id_parent = inp->i_parent;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling idesc.id_fix = NOFIX;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling (void) ckinode(dp, &idesc, CKI_TRAVERSE);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling discard_contents();
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling}
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling/*
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * Used to scan a particular directory, noting what entries it contains.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * If a duplicate entry is found, it is reported and the user given
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling * the option of clearing said entry.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling */
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingstatic int
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingpass2acheck(struct inodesc *idesc)
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling{
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling struct direct *dirp = idesc->id_dirp;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling dirtree_t key;
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson void **foundp;
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson dirtree_t *firstp;
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson int retval = KEEPON;
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson /*
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson * We've reached the end of the valid part of the directory.
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson */
2acef22db7808606888f8f92715629ff3ba555b9Matthew Ahrens if (idesc->id_blkno == 0) {
4a92375985c37d61406d66cd2b10ee642eb1f5e7George Wilson return (STOP);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (dirp->d_ino != 0) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling key.name = dirp->d_name;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling key.len = dirp->d_namlen;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling foundp = tfind((void *)&key, &contents, dirtree_cmp);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if ((foundp != NULL) && (*foundp != NULL)) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling firstp = (dirtree_t *)*foundp;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling pfatal(
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling "Duplicate entries in dir I=%d for ``%s'': I=%d and I=%d",
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling idesc->id_number, dirp->d_name,
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling firstp->ino, dirp->d_ino);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (reply("Clear second entry") == 1) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling dirp->d_ino = 0;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling retval |= ALTERED;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling } else {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling iscorrupt = 1;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling } else {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling firstp = (dirtree_t *)malloc(sizeof (dirtree_t));
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if ((firstp == NULL) ||
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling ((firstp->name = strdup(dirp->d_name)) == NULL)) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling goto nomem;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling firstp->len = dirp->d_namlen;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling firstp->ino = dirp->d_ino;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (tsearch((void *)firstp,
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling &contents, dirtree_cmp) == NULL) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling goto nomem;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling return (retval);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingnomem:
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (firstp != NULL) {
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (firstp->name != NULL)
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling free(firstp->name);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling free(firstp);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling pfatal(
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling "Out of memory while looking for duplicate names in directory I=%d",
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling idesc->id_number);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (reply("SKIP REST OF DUP NAME CHECK") == 0)
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling errexit("Program terminated.");
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling discard_contents();
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling retval |= STOP;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling return (retval);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling}
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingstatic void
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingdiscard_contents(void)
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling{
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling dirtree_t *victim;
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling while (contents != NULL) {
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens victim = *(dirtree_t **)contents;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling (void) tdelete((void *)victim, &contents, dirtree_cmp);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling free((void *)victim->name);
be6fd75a69ae679453d9cda5bff3326111e6d1caMatthew Ahrens free((void *)victim);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling }
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling}
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingstatic int
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Lingdirtree_cmp(const void *left, const void *right)
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens{
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling int cmp;
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens const dirtree_t *lp = (const dirtree_t *)left;
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens const dirtree_t *rp = (const dirtree_t *)right;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling cmp = lp->len - rp->len;
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling if (cmp == 0)
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling cmp = strcmp(lp->name, rp->name);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling return (cmp);
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling}
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling