summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorjianfeng <jianfeng@codeaurora.org>2012-06-19 19:53:15 +0800
committerAdnan Begovic <adnan@cyngn.com>2015-10-07 17:39:54 -0700
commite00bc4e14c6388ff4b49ea2cb4eda3c316691ee5 (patch)
tree8f39fc21b7128a04537494d9e6f3d14f1a4eb9e1
parent17a1471db8c528cd9d44ec4385d2eb3614138856 (diff)
downloadandroid_external_fsck_msdos-e00bc4e14c6388ff4b49ea2cb4eda3c316691ee5.tar.gz
android_external_fsck_msdos-e00bc4e14c6388ff4b49ea2cb4eda3c316691ee5.tar.bz2
android_external_fsck_msdos-e00bc4e14c6388ff4b49ea2cb4eda3c316691ee5.zip
Change algorithm of cluster chain organization.
fsck_msdos will cause crash on low-memory device and 64GB FAT32 SD cards, so change algorithm of cluster chain organization and fix the issue that 64GB SDCARD can't be recognized. Change-Id: I7bcdd138ac76c7f83d9cf3a292b3a0ba8ac78efd
Diffstat
-rw-r--r--Android.mk5
-rw-r--r--boot.c29
-rw-r--r--check.c81
-rw-r--r--dir.c274
-rw-r--r--dosfs.h28
-rw-r--r--ext.h23
-rw-r--r--fat.c774
-rw-r--r--fatcache.c309
-rw-r--r--fatcache.h86
-rw-r--r--fragment.c78
-rw-r--r--fragment.h49
-rw-r--r--fsutil.h4
-rw-r--r--main.c5
-rw-r--r--tree.h769
14 files changed, 2059 insertions, 455 deletions
diff --git a/Android.mk b/Android.mk
index bafd757..d959325 100644
--- a/Android.mk
+++ b/Android.mk
@@ -1,8 +1,7 @@
LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES := boot.c check.c dir.c fat.c main.c
+LOCAL_SRC_FILES := fragment.c fatcache.c boot.c check.c dir.c fat.c main.c
LOCAL_C_INCLUDES := external/fsck_msdos/
@@ -10,6 +9,6 @@ LOCAL_CFLAGS := -O2 -g -W -Wall -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64
LOCAL_MODULE := fsck_msdos
LOCAL_MODULE_TAGS :=
-LOCAL_SYSTEM_SHARED_LIBRARIES := libc
+LOCAL_SYSTEM_SHARED_LIBRARIES := libc libcutils
include $(BUILD_EXECUTABLE)
diff --git a/boot.c b/boot.c
index 5326a45..48c4afe 100644
--- a/boot.c
+++ b/boot.c
@@ -45,6 +45,7 @@ static const char rcsid[] =
#include <unistd.h>
#include "ext.h"
+#include "fatcache.h"
#include "fsutil.h"
int
@@ -73,6 +74,7 @@ readboot(dosfs, boot)
/* decode bios parameter block */
boot->BytesPerSec = block[11] + (block[12] << 8);
boot->SecPerClust = block[13];
+ fsck_debug("sectors Per cluster :%d \n",boot->SecPerClust);
boot->ResSectors = block[14] + (block[15] << 8);
boot->FATs = block[16];
boot->RootDirEnts = block[17] + (block[18] << 8);
@@ -86,6 +88,16 @@ readboot(dosfs, boot)
boot->FATsecs = boot->FATsmall;
+ /* This variable is 0 in some filesystems such as exFat.
+ * It will cause divided by zero error in the following
+ * steps. Just return in this case.
+ */
+ if (boot->BytesPerSec == 0) {
+ fsck_err("Invalid sector size: %u", boot->BytesPerSec);
+ exit(2);
+ return FSFATAL;
+ }
+
if (!boot->RootDirEnts)
boot->flags |= FAT32;
if (boot->flags & FAT32) {
@@ -212,6 +224,12 @@ readboot(dosfs, boot)
/* Check backup FSInfo? XXX */
}
+ boot->ClusterOffset = (boot->RootDirEnts * 32 + boot->BytesPerSec - 1)
+ / boot->BytesPerSec
+ + boot->ResSectors
+ + boot->FATs * boot->FATsecs
+ - CLUST_FIRST * boot->SecPerClust;
+ fsck_debug("boot->ClusterOffset :%d \n",boot->ClusterOffset);
if (boot->BytesPerSec % DOSBOOTBLOCKSIZE != 0) {
pfatal("Invalid sector size: %u", boot->BytesPerSec);
return FSFATAL;
@@ -220,10 +238,6 @@ readboot(dosfs, boot)
pfatal("Invalid cluster size: %u", boot->SecPerClust);
return FSFATAL;
}
- if (boot->BytesPerSec == 0) {
- pfatal("Invalid sector size: %u", boot->BytesPerSec);
- return FSFATAL;
- }
if (boot->FATs == 0) {
pfatal("Invalid number of FATs: %u", boot->FATs);
return FSFATAL;
@@ -233,13 +247,6 @@ readboot(dosfs, boot)
boot->NumSectors = boot->Sectors;
} else
boot->NumSectors = boot->HugeSectors;
-
- boot->ClusterOffset = (boot->RootDirEnts * 32 + boot->BytesPerSec - 1)
- / boot->BytesPerSec
- + boot->ResSectors
- + boot->FATs * boot->FATsecs
- - CLUST_FIRST * boot->SecPerClust;
-
boot->NumClusters = (boot->NumSectors - boot->ClusterOffset) / boot->SecPerClust;
if (boot->flags&FAT32)
diff --git a/check.c b/check.c
index fab2d91..409f591 100644
--- a/check.c
+++ b/check.c
@@ -47,7 +47,8 @@ static const char rcsid[] =
#include "ext.h"
#include "fsutil.h"
-
+#include "fatcache.h"
+#include "fragment.h"
/*
* If the FAT > this size then skip comparing, lest we risk
* OOMing the framework. in the future we need to just re-write
@@ -60,13 +61,12 @@ checkfilesys(const char *fname)
{
int dosfs;
struct bootblock boot;
- struct fatEntry *fat = NULL;
+ u_char *fat ,*fat2;
int i, finish_dosdirsection=0;
int mod = 0;
int ret = 8;
- int quiet = 0;
- int skip_fat_compare = 0;
-
+ int quiet = 0;
+ int skip_fat_compare = 0;
rdonly = alwaysno;
if (!quiet)
printf("** %s", fname);
@@ -89,10 +89,22 @@ checkfilesys(const char *fname)
if (readboot(dosfs, &boot) == FSFATAL) {
close(dosfs);
- printf("\n");
return 8;
}
+ switch(boot.ClustMask){
+ case CLUST32_MASK:
+ fsck_info("FAT32 Filesystem\n");
+ break;
+ case CLUST16_MASK:
+ fsck_info("FAT16 Fielsystem\n");
+ break;
+ default:
+ fsck_info("FAT12 Filesystem\n");
+ break;
+ }
+ fsck_debug("Using cluster_chain_descriptor\n");
+ fsck_info("Total clusters %u \n",boot.NumClusters);
if (skipclean && preen && checkdirty(dosfs, &boot)) {
printf("%s: ", fname);
printf("FILESYSTEM CLEAN; SKIPPING CHECKS\n");
@@ -100,7 +112,7 @@ checkfilesys(const char *fname)
goto out;
}
- if (((boot.FATsecs * boot.BytesPerSec) / 1024) > FAT_COMPARE_MAX_KB)
+ if (((boot.FATsecs * boot.BytesPerSec) / 1024) > FAT_COMPARE_MAX_KB)
skip_fat_compare = 1;
if (!quiet) {
@@ -112,68 +124,62 @@ checkfilesys(const char *fname)
printf("** Phase 1 - Read FAT\n");
}
- mod |= readfat(dosfs, &boot, boot.ValidFat >= 0 ? boot.ValidFat : 0, &fat);
- if (mod & FSFATAL) {
- printf("Fatal error during readfat()\n");
- close(dosfs);
- return 8;
+ ret = !_readfat(dosfs, &boot,boot.ValidFat >= 0 ? boot.ValidFat : 0,&fat);
+ if (ret) {
+ fsck_debug("Fatal error during _readfat() for comparison\n");
+ goto out;
}
if (!skip_fat_compare && boot.ValidFat < 0)
for (i = 1; i < (int)boot.FATs; i++) {
- struct fatEntry *currentFat;
+ //just check the FAT
+ ret = !_readfat(dosfs, &boot,i,&fat2);
- mod |= readfat(dosfs, &boot, i, &currentFat);
-
- if (mod & FSFATAL) {
- printf("Fatal error during readfat() for comparison\n");
+ if (ret) {
+ printf("Fatal error during _readfat() for comparison\n");
goto out;
}
-
- mod |= comparefat(&boot, fat, currentFat, i);
- free(currentFat);
+ /*have modified comparefat() and subfunction clustdiffer*/
+ mod |= comparefat(&boot, fat, fat2, i);
+ free(fat2);
if (mod & FSFATAL) {
printf("Fatal error during FAT comparison\n");
goto out;
}
}
-
- if (!quiet)
- printf("** Phase 2 - Check Cluster Chains\n");
-
- mod |= checkfat(&boot, fat);
+ fsck_info("** Phase 2 - Check Cluster Chains \n");
+ mod |= checkfat(dosfs, &boot, boot.ValidFat >= 0 ? boot.ValidFat : 0, fat);
if (mod & FSFATAL) {
- printf("Fatal error during FAT check\n");
- goto out;
+ fsck_info("Fatal error during checkfat()\n");
+ close(dosfs);
+ return 8;
}
/* delay writing FATs */
if (!quiet)
printf("** Phase 3 - Checking Directories\n");
-
- mod |= resetDosDirSection(&boot, fat);
+ mod |= resetDosDirSection(&boot);
finish_dosdirsection = 1;
if (mod & FSFATAL) {
printf("Fatal error during resetDosDirSection()\n");
goto out;
}
/* delay writing FATs */
-
- mod |= handleDirTree(dosfs, &boot, fat);
+ mod |= handleDirTree(dosfs, &boot);
if (mod & FSFATAL)
goto out;
if (!quiet)
printf("** Phase 4 - Checking for Lost Files\n");
- mod |= checklost(dosfs, &boot, fat);
+ mod |= checklost(dosfs, &boot);
if (mod & FSFATAL)
goto out;
/* now write the FATs */
if (mod & FSFATMOD) {
if (ask(1, "Update FATs")) {
- mod |= writefat(dosfs, &boot, fat, mod & FSFIXFAT);
+ mod |= writefat(dosfs, &boot, mod & FSFIXFAT);
if (mod & FSFATAL) {
printf("Fatal error during writefat()\n");
goto out;
@@ -199,7 +205,7 @@ checkfilesys(const char *fname)
if (mod & FSDIRTY) {
pwarn("MARKING FILE SYSTEM CLEAN\n");
- mod |= writefat(dosfs, &boot, fat, 1);
+ mod |= writefat(dosfs, &boot, 1);
} else {
pwarn("\n***** FILE SYSTEM IS LEFT MARKED AS DIRTY *****\n");
mod |= FSERROR; /* file system not clean */
@@ -212,12 +218,13 @@ checkfilesys(const char *fname)
ret = 0;
- out:
+out:
+ free_rb_tree();
+ free_fragment_tree(&rb_free_root);
+ free_fragment_tree(&rb_bad_root);
if (finish_dosdirsection)
finishDosDirSection();
- free(fat);
close(dosfs);
-
if (mod & (FSFATMOD|FSDIRMOD)) {
pwarn("\n***** FILE SYSTEM WAS MODIFIED *****\n");
return 4;
diff --git a/dir.c b/dir.c
index 7e4a567..c3a485a 100644
--- a/dir.c
+++ b/dir.c
@@ -34,6 +34,8 @@
#include <sys/cdefs.h>
+#include "fatcache.h"
+#include "fragment.h"
#ifndef lint
__RCSID("$NetBSD: dir.c,v 1.14 1998/08/25 19:18:15 ross Exp $");
static const char rcsid[] =
@@ -52,7 +54,7 @@ static const char rcsid[] =
#include "ext.h"
#include "fsutil.h"
-
+#include "dosfs.h"
#define SLOT_EMPTY 0x00 /* slot has never been used */
#define SLOT_E5 0x05 /* the real value is 0xe5 */
#define SLOT_DELETED 0xe5 /* file in this slot deleted */
@@ -99,13 +101,13 @@ static struct dirTodoNode *newDirTodo(void);
static void freeDirTodo(struct dirTodoNode *);
static char *fullpath(struct dosDirEntry *);
static u_char calcShortSum(u_char *);
-static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
+static int delete(int, struct bootblock *,struct cluster_chain_descriptor* ,cl_t, int,
cl_t, int, int);
-static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
+static int removede(int, struct bootblock *, struct cluster_chain_descriptor*,u_char *,
u_char *, cl_t, cl_t, cl_t, char *, int);
-static int checksize(struct bootblock *, struct fatEntry *, u_char *,
+static int checksize(struct bootblock *, u_char *,
struct dosDirEntry *);
-static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
+static int readDosDirSection(int, struct bootblock *,
struct dosDirEntry *);
/*
@@ -221,12 +223,13 @@ static struct dosDirEntry *lostDir;
* Init internal state for a new directory scan.
*/
int
-resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
+resetDosDirSection(struct bootblock *boot)
{
int b1, b2;
- cl_t cl;
int ret = FSOK;
-
+ struct cluster_chain_descriptor *fat,tofind,*insert;
+ struct fragment *frag,tofind_frag;
+ struct fatcache *cache;
b1 = boot->RootDirEnts * 32;
b2 = boot->SecPerClust * boot->BytesPerSec;
@@ -243,30 +246,50 @@ resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
boot->RootCl);
return FSFATAL;
}
- cl = fat[boot->RootCl].next;
- if (cl < CLUST_FIRST
- || (cl >= CLUST_RSRVD && cl< CLUST_EOFS)
- || fat[boot->RootCl].head != boot->RootCl) {
- if (cl == CLUST_FREE)
- pwarn("Root directory starts with free cluster\n");
- else if (cl >= CLUST_RSRVD)
- pwarn("Root directory starts with cluster marked %s\n",
- rsrvdcltype(cl));
- else {
- pfatal("Root directory doesn't start a cluster chain");
- return FSFATAL;
- }
- if (ask(1, "Fix")) {
- fat[boot->RootCl].next = CLUST_FREE;
+ //In fat12 and fat16, the boot->RootCl is zero,you can not find its chain
+ tofind.head = boot->RootCl;
+ fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ /*we have check the cluster chain in readfatAndcheckfat*/
+ if(!fat){
+ pwarn("can not find Root direntory in cluster chain\n");
+ if(ask(1, "Fix")){
+ tofind_frag.head = boot->RootCl;
+ frag = RB_FIND(FSCK_MSDOS_FRAGMENT,&rb_free_root,&tofind_frag);
+ if(!frag){
+ fsck_err("can not find Root direntory in free chain\n");
+ ret = FSFATAL;
+ goto out;
+ }
+ /*find it in free rb tree,now move it to cluster chain*/
+ fat = New_fatentry();
+ if(!fat)
+ return FSFATAL;
+ fat->head = boot->RootCl;
+ fat->head = 1;
+ cache = New_fatcache();
+ if(!cache)
+ return FSFATAL;
+ cache->head = boot->RootCl;
+ cache->length = 1;
+ add_fatcache_To_ClusterChain(fat,cache);
+ insert = RB_INSERT(FSCK_MSDOS_CACHE,&rb_root,fat);
+ if(insert){
+ fsck_err("%s:fatentry(head:0x%x) exist\n",__func__,fat->head);
+ return FSFATAL;
+ }
+ RB_REMOVE(FSCK_MSDOS_FRAGMENT,&rb_free_root,frag);
+ free(frag);
ret = FSFATMOD;
- } else
+ goto out;
+ }else{
ret = FSFATAL;
+ goto out;
+ }
}
-
- fat[boot->RootCl].flags |= FAT_USED;
+ fat->flag |= FAT_USED;
rootDir->head = boot->RootCl;
}
-
+out:
return ret;
}
@@ -304,15 +327,20 @@ finishDosDirSection(void)
* Delete directory entries between startcl, startoff and endcl, endoff.
*/
static int
-delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
+delete(int f, struct bootblock *boot, struct cluster_chain_descriptor *fat,cl_t startcl,
int startoff, cl_t endcl, int endoff, int notlast)
{
u_char *s, *e;
loff_t off;
int clsz = boot->SecPerClust * boot->BytesPerSec;
-
+ struct fatcache *cache;
+ fsck_debug("delete: %u:%u -->> %u:%u\n",startcl,startoff,endcl,endoff);
s = delbuf + startoff;
e = delbuf + clsz;
+ if(!fat){
+ pwarn("Can't find cl %d in cluster chain\n",startcl);
+ return FSFATAL;
+ }
while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
if (startcl == endcl) {
if (notlast)
@@ -322,7 +350,6 @@ delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
off = startcl * boot->SecPerClust + boot->ClusterOffset;
off *= boot->BytesPerSec;
if (lseek64(f, off, SEEK_SET) != off) {
- printf("off = %llu\n", off);
perror("Unable to lseek64");
return FSFATAL;
}
@@ -335,7 +362,6 @@ delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
s += 32;
}
if (lseek64(f, off, SEEK_SET) != off) {
- printf("off = %llu\n", off);
perror("Unable to lseek64");
return FSFATAL;
}
@@ -345,16 +371,20 @@ delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
}
if (startcl == endcl)
break;
- startcl = fat[startcl].next;
+ //if startcl = 0.it means no next cluster
+ cache = Find_nextclus(fat,startcl,&startcl);
+ if(!cache && !startcl)
+ return FSFATAL;
s = delbuf;
}
return FSOK;
}
static int
-removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
+removede(int f, struct bootblock *boot,struct cluster_chain_descriptor *fat, u_char *start,
u_char *end, cl_t startcl, cl_t endcl, cl_t curcl, char *path, int type)
{
+ fsck_debug("removede : %u:%u --->> %u:%u \n",startcl,start,endcl,end);
switch (type) {
case 0:
pwarn("Invalid long filename entry for %s\n", path);
@@ -365,6 +395,8 @@ removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
case 2:
pwarn("Invalid long filename entry for volume label\n");
break;
+ case 3:
+ pwarn("Can't find the associated cluster chain\n");
}
if (ask(1, "Remove")) {
if (startcl != curcl) {
@@ -387,12 +419,14 @@ removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
* Check an in-memory file entry
*/
static int
-checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
+checksize(struct bootblock *boot, u_char *p,
struct dosDirEntry *dir)
{
/*
* Check size on ordinary files
*/
+ struct cluster_chain_descriptor *fat,tofind;
+ struct fatcache *cache;
int32_t physicalSize;
if (dir->head == CLUST_FREE)
@@ -400,11 +434,18 @@ checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
else {
if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
return FSERROR;
- physicalSize = fat[dir->head].length * boot->ClusterSize;
+ tofind.head = dir->head;
+ fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ if(!fat){
+ pwarn("Can't find the cluster chain with head(%u) \n",dir->head);
+ return FSERROR;
+ }
+ physicalSize = fat->length * boot->ClusterSize;
}
if (physicalSize < dir->size) {
pwarn("size of %s is %u, should at most be %u\n",
fullpath(dir), dir->size, physicalSize);
+ fsck_debug("physicalSize:%d ,dir->size = %d ,dir->head:0x%x\n",physicalSize,dir->size,dir->head);
if (ask(1, "Truncate")) {
dir->size = physicalSize;
p[28] = (u_char)physicalSize;
@@ -417,14 +458,26 @@ checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
} else if (physicalSize - dir->size >= boot->ClusterSize) {
pwarn("%s has too many clusters allocated\n",
fullpath(dir));
+ fsck_debug("physicalSize:%d ,dir->size = %d ,dir->head:0x%x\n",physicalSize,dir->size,dir->head);
if (ask(1, "Drop superfluous clusters")) {
cl_t cl;
u_int32_t sz = 0;
- for (cl = dir->head; (sz += boot->ClusterSize) < dir->size;)
- cl = fat[cl].next;
- clearchain(boot, fat, fat[cl].next);
- fat[cl].next = CLUST_EOF;
+ for (cl = dir->head; (sz += boot->ClusterSize) < dir->size;){
+ cache = Find_nextclus(fat,cl,&cl);
+ if(!cl )
+ return FSERROR;
+ if(cl == CLUST_EOF)
+ break;
+ }
+ //cache = Find_nextclus(fat,cl,&cl);
+ if(!cache && !cl)
+ return FSERROR;
+ //TODO: i don't no why exec clearchain here.when cl != fat.head,clear do nothing
+ //clearchain(boot, fat,cl);
+ //if trunc it ,when next fsck ,the rest will locate in LOST.DIR
+ Trunc(fat,cl);
+ fsck_debug("after truncate ,fat->length = %d \n",fat->length);
return FSFATMOD;
} else
return FSERROR;
@@ -440,22 +493,27 @@ static u_char dot_dot_header[16]={0x2E, 0x2E, 0x20, 0x20, 0x20, 0x20, 0x20, 0x2
* Check for missing or broken '.' and '..' entries.
*/
static int
-check_dot_dot(int f, struct bootblock *boot, struct fatEntry *fat,struct dosDirEntry *dir)
+check_dot_dot(int f, struct bootblock *boot,struct dosDirEntry *dir)
{
u_char *p, *buf;
loff_t off;
int last;
cl_t cl;
int rc=0, n_count;
-
+ struct cluster_chain_descriptor *fat,tofind;
+ struct fatcache *cache;
int dot, dotdot;
dot = dotdot = 0;
cl = dir->head;
-
if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
return rc;
}
-
+ tofind.head = dir->head;
+ fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ if(!fat){
+ pwarn("%s:cannot find cluster chain(%d)\n",__func__,dir->head);
+ return FSFATAL;
+ }
do {
if (!(boot->flags & FAT32) && !dir->parent) {
last = boot->RootDirEnts * 32;
@@ -472,14 +530,11 @@ check_dot_dot(int f, struct bootblock *boot, struct fatEntry *fat,struct dosDirE
return FSFATAL;
}
if (lseek64(f, off, SEEK_SET) != off) {
- printf("off = %llu\n", off);
perror("Unable to lseek64");
- free(buf);
return FSFATAL;
}
if (read(f, buf, last) != last) {
perror("Unable to read");
- free(buf);
return FSFATAL;
}
last /= 32;
@@ -502,7 +557,10 @@ check_dot_dot(int f, struct bootblock *boot, struct fatEntry *fat,struct dosDirE
if(!rc)
dotdot=1;
free(buf);
- } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
+ cache = Find_nextclus(fat,cl,&cl);
+ if(!cache && !cl)
+ return FSFATAL;
+ } while (cl >= CLUST_FIRST && cl < boot->NumClusters);
if (!dot || !dotdot) {
if (!dot)
@@ -522,7 +580,7 @@ check_dot_dot(int f, struct bootblock *boot, struct fatEntry *fat,struct dosDirE
* - push directories onto the todo-stack
*/
static int
-readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
+readDosDirSection(int f, struct bootblock *boot,
struct dosDirEntry *dir)
{
struct dosDirEntry dirent, *d;
@@ -534,10 +592,9 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
u_int lidx = 0;
int shortSum;
int mod = FSOK;
- int n_count=0;
- int rc=0;
+ struct cluster_chain_descriptor *fat = NULL,tofind;
+ struct fatcache *cache = NULL;
#define THISMOD 0x8000 /* Only used within this routine */
-
cl = dir->head;
if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
/*
@@ -549,8 +606,17 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
vallfn = invlfn = empty = NULL;
int dot,dotdot;
dot = dotdot = 0;
-
+ //FAT32 has boot->Rootcl
+ if((boot->ClustMask == CLUST32_MASK) || dir->parent){
+ tofind.head = dir->head;
+ fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ if(!fat){
+ fsck_err("%s:can not find cluster chain(head = %u)\n",__func__,dir->head);
+ return FSFATMOD;
+ }
+ }
do {
+ struct cluster_chain_descriptor *c_fat;
if (!(boot->flags & FAT32) && !dir->parent) {
last = boot->RootDirEnts * 32;
off = boot->ResSectors + boot->FATs * boot->FATsecs;
@@ -763,9 +829,6 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
mod |= THISMOD;
}
- vallfn = NULL; /* not used any longer */
- invlfn = NULL;
-
if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
if (dirent.head != 0) {
pwarn("%s has clusters, but size 0\n",
@@ -774,7 +837,12 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
p[26] = p[27] = 0;
if (boot->ClustMask == CLUST32_MASK)
p[20] = p[21] = 0;
- clearchain(boot, fat, dirent.head);
+ tofind.head = dirent.head;
+ c_fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ if(c_fat)
+ clearchain(c_fat, dirent.head);
+ else
+ mod |= FSERROR;
dirent.head = 0;
mod |= THISMOD|FSDIRMOD|FSFATMOD;
} else
@@ -789,10 +857,8 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
*/
} else if (dirent.head < CLUST_FIRST
|| dirent.head >= boot->NumClusters
- || fat[dirent.head].next == CLUST_FREE
- || (fat[dirent.head].next >= CLUST_RSRVD
- && fat[dirent.head].next < CLUST_EOFS)
- || fat[dirent.head].head != dirent.head) {
+ )
+ {
if (dirent.head == 0)
pwarn("%s has no clusters\n",
fullpath(&dirent));
@@ -801,16 +867,7 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
pwarn("%s starts with cluster out of range(%u)\n",
fullpath(&dirent),
dirent.head);
- else if (fat[dirent.head].next == CLUST_FREE)
- pwarn("%s starts with free cluster\n",
- fullpath(&dirent));
- else if (fat[dirent.head].next >= CLUST_RSRVD)
- pwarn("%s starts with cluster marked %s\n",
- fullpath(&dirent),
- rsrvdcltype(fat[dirent.head].next));
- else
- pwarn("%s doesn't start a cluster chain\n",
- fullpath(&dirent));
+
if (dirent.flags & ATTR_DIRECTORY) {
if (ask(1, "Remove")) {
*p = SLOT_DELETED;
@@ -831,8 +888,26 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
}
}
- if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
- fat[dirent.head].flags |= FAT_USED;
+ if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters){
+ tofind.head = dirent.head;
+ c_fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ if (c_fat) {
+ c_fat->flag |= FAT_USED;
+ }
+ else{
+ fsck_warn("can't find cluster chain(head:0x%x) of file:%s \n",dirent.head,fullpath(&dirent));
+ if (vallfn || invlfn) {
+ fsck_warn("Invalid long directory deleted\n");
+ mod |= removede(f, boot, fat,invlfn ? invlfn : vallfn, p,invlfn ? invcl : valcl, -1, 0,fullpath(dir), 3);
+ } else {
+ fsck_warn("Invalid short directory deleted\n");
+ *p = SLOT_DELETED;
+ }
+ return FSDIRMOD;
+ }
+ }
+ vallfn = NULL; /* not used any longer */
+ invlfn = NULL;
if (dirent.flags & ATTR_DIRECTORY) {
/*
@@ -918,7 +993,7 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
a dot (.) entry that points to itself, and a dot-dot (..)
entry that points to its parent.
*/
- if (check_dot_dot(f,boot,fat,&dirent)) {
+ if (check_dot_dot(f,boot,&dirent)) {
//mark directory entry as deleted.
if (ask(1, "Remove")) {
*p = SLOT_DELETED;
@@ -926,7 +1001,7 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
} else
mod |= FSERROR;
continue;
- }
+ }
}
/* create directory tree node */
@@ -937,10 +1012,6 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
memcpy(d, &dirent, sizeof(struct dosDirEntry));
/* link it into the tree */
dir->child = d;
-#if 0
- printf("%s: %s : 0x%02x:head %d, next 0x%0x parent 0x%0x child 0x%0x\n",
- __func__,d->name,d->flags,d->head,d->next,d->parent,d->child);
-#endif
/* Enter this directory into the todo list */
if (!(n = newDirTodo())) {
perror("No space for todo list");
@@ -950,7 +1021,7 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
n->dir = d;
pendingDirectories = n;
} else {
- mod |= k = checksize(boot, fat, p, &dirent);
+ mod |= k = checksize(boot, p, &dirent);
if (k & FSDIRMOD)
mod |= THISMOD;
}
@@ -965,7 +1036,14 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
}
mod &= ~THISMOD;
}
- } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
+ if(boot->ClustMask == CLUST32_MASK || dir->parent){
+ cache = Find_nextclus(fat,cl,&cl);
+ if(!cache && !cl){
+ fsck_err("%s :Find nextclus error \n",__func__);
+ return FSFATAL;
+ }
+ }
+ } while (cl >= CLUST_FIRST && cl < boot->NumClusters);
if (invlfn || vallfn)
mod |= removede(f, boot, fat,
invlfn ? invlfn : vallfn, p,
@@ -975,14 +1053,13 @@ readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
}
int
-handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
+handleDirTree(int dosfs, struct bootblock *boot)
{
int mod;
-
- mod = readDosDirSection(dosfs, boot, fat, rootDir);
+ fsck_debug("rootDir->head :%d\n",rootDir->head);
+ mod = readDosDirSection(dosfs, boot, rootDir);
if (mod & FSFATAL)
return FSFATAL;
-
/*
* process the directory todo list
*/
@@ -1000,11 +1077,10 @@ handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
/*
* handle subdirectory
*/
- mod |= readDosDirSection(dosfs, boot, fat, dir);
+ mod |= readDosDirSection(dosfs, boot, dir);
if (mod & FSFATAL)
return FSFATAL;
}
-
return mod;
}
@@ -1014,20 +1090,25 @@ handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
static u_char *lfbuf;
static cl_t lfcl;
static loff_t lfoff;
-
+static struct cluster_chain_descriptor *lostdirfat;
int
-reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
+reconnect(int dosfs, struct bootblock *boot, struct cluster_chain_descriptor *fat, cl_t head)
{
struct dosDirEntry d;
+ struct fatcache *cache = NULL;
+ struct cluster_chain_descriptor tofind;
u_char *p;
if (!ask(1, "Reconnect"))
return FSERROR;
-
+ //find the lost dir in root directory
if (!lostDir) {
for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
- if (!strcmp(lostDir->name, LOSTDIR))
+ if (!strcmp(lostDir->name, LOSTDIR)){
+ tofind.head = lostDir->head;
+ lostdirfat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
break;
+ }
}
if (!lostDir) { /* Create LOSTDIR? XXX */
pwarn("No %s directory\n", LOSTDIR);
@@ -1045,13 +1126,20 @@ reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
p = lfbuf;
while (1) {
if (p)
+ //find an empty or deleted direntry in lostdir
for (; p < lfbuf + boot->ClusterSize; p += 32)
if (*p == SLOT_EMPTY
|| *p == SLOT_DELETED)
break;
if (p && p < lfbuf + boot->ClusterSize)
break;
- lfcl = p ? fat[lfcl].next : lostDir->head;
+ if(p){
+ cache = Find_nextclus(lostdirfat,lfcl,&lfcl);
+ }
+ else{
+ lfcl = lostDir->head;
+ }
+ // lfcl = p ? fat[lfcl].next : lostDir->head;
if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
/* Extend LOSTDIR? XXX */
pwarn("No space in %s\n", LOSTDIR);
@@ -1074,7 +1162,7 @@ reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
(void)snprintf(d.name, sizeof(d.name), "%u", head);
d.flags = 0;
d.head = head;
- d.size = fat[head].length * boot->ClusterSize;
+ d.size = fat->length * boot->ClusterSize;
memset(p, 0, 32);
memset(p, ' ', 11);
@@ -1089,7 +1177,7 @@ reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
p[29] = (u_char)(d.size >> 8);
p[30] = (u_char)(d.size >> 16);
p[31] = (u_char)(d.size >> 24);
- fat[head].flags |= FAT_USED;
+ fat->flag |= FAT_USED;
if (lseek64(dosfs, lfoff, SEEK_SET) != lfoff
|| write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
perror("could not write LOST.DIR");
diff --git a/dosfs.h b/dosfs.h
index 5420e25..0d9f600 100644
--- a/dosfs.h
+++ b/dosfs.h
@@ -38,9 +38,10 @@
#define DOSFS_H
#define DOSBOOTBLOCKSIZE 512
-
-typedef u_int32_t cl_t; /* type holding a cluster number */
-
+#include "tree.h"
+typedef unsigned int cl_t; /* type holding a cluster number */
+typedef unsigned int u_int;
+typedef unsigned int u_int32_t;
/*
* architecture independent description of all the info stored in a
* FAT boot block.
@@ -86,11 +87,18 @@ struct bootblock {
u_int NumBad; /* # of bad clusters */
};
-struct fatEntry {
- cl_t next; /* pointer to next cluster */
- cl_t head; /* pointer to start of chain */
- u_int32_t length; /* number of clusters on chain */
- int flags; /* see below */
+
+struct fatcache {
+ struct fatcache *next;
+ cl_t head;
+ u_int32_t length;
+};
+struct cluster_chain_descriptor {
+ struct fatcache* child;
+ cl_t head; /* pointer to start of chain */
+ u_int32_t length; /* how many cluster this file contains*/
+ RB_ENTRY(cluster_chain_descriptor) rb;
+ u_int32_t flag;
};
#define CLUST_FREE 0 /* 0 means cluster is free */
@@ -124,10 +132,10 @@ struct dosDirEntry {
*child; /* if this is a directory */
char name[8+1+3+1]; /* alias name first part */
char lname[DOSLONGNAMELEN]; /* real name */
- uint flags; /* attributes */
+ u_int32_t flags; /* attributes */
cl_t head; /* cluster no */
u_int32_t size; /* filesize in bytes */
- uint fsckflags; /* flags during fsck */
+ u_int32_t fsckflags; /* flags during fsck */
};
/* Flags in fsckflags: */
#define DIREMPTY 1
diff --git a/ext.h b/ext.h
index 6d183e9..17f5326 100644
--- a/ext.h
+++ b/ext.h
@@ -56,7 +56,7 @@ extern struct dosDirEntry *rootDir;
* function declarations
*/
int ask(int, const char *, ...);
-
+int _readfat(int fs, struct bootblock *boot, int no, u_char **buffer);
/*
* Check the dirty flag. If the file system is clean, then return 1.
* Otherwise, return 0 (this includes the case of FAT12 file systems --
@@ -80,6 +80,7 @@ int checkfilesys(const char *);
#define FSFATAL 16 /* Some unrecoverable error occured */
#define FSDIRTY 32 /* File system is dirty */
#define FSFIXFAT 64 /* Fix file system FAT */
+#define FSOOM 128 /* the check may cause system OOM */
/*
* read a boot block in a machine independend fashion and translate
@@ -96,30 +97,27 @@ int writefsinfo(int, struct bootblock *);
* Read one of the FAT copies and return a pointer to the new
* allocated array holding our description of it.
*/
-int readfat(int, struct bootblock *, int, struct fatEntry **);
/*
* Check two FAT copies for consistency and merge changes into the
* first if neccessary.
*/
-int comparefat(struct bootblock *, struct fatEntry *, struct fatEntry *, int);
-
+int comparefat(struct bootblock *, u_char *, u_char *, int);
/*
* Check a FAT
*/
-int checkfat(struct bootblock *, struct fatEntry *);
-
+int checkfat(int fs, struct bootblock *boot, int no,u_char *buffer);
/*
* Write back FAT entries
*/
-int writefat(int, struct bootblock *, struct fatEntry *, int);
+int writefat(int, struct bootblock *, int);
/*
* Read a directory
*/
-int resetDosDirSection(struct bootblock *, struct fatEntry *);
+int resetDosDirSection(struct bootblock *);
void finishDosDirSection(void);
-int handleDirTree(int, struct bootblock *, struct fatEntry *);
+int handleDirTree(int, struct bootblock *);
/*
* Cross-check routines run after everything is completely in memory
@@ -127,11 +125,11 @@ int handleDirTree(int, struct bootblock *, struct fatEntry *);
/*
* Check for lost cluster chains
*/
-int checklost(int, struct bootblock *, struct fatEntry *);
+int checklost(int, struct bootblock *);
/*
* Try to reconnect a lost cluster chain
*/
-int reconnect(int, struct bootblock *, struct fatEntry *, cl_t);
+int reconnect(int, struct bootblock *, struct cluster_chain_descriptor *, cl_t);
void finishlf(void);
/*
@@ -145,6 +143,5 @@ char *rsrvdcltype(cl_t);
/*
* Clear a cluster chain in a FAT
*/
-void clearchain(struct bootblock *, struct fatEntry *, cl_t);
-
+void clearchain(struct cluster_chain_descriptor *, cl_t);
#endif
diff --git a/fat.c b/fat.c
index 9b58ffb..05454a6 100644
--- a/fat.c
+++ b/fat.c
@@ -29,9 +29,11 @@
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-
-
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
#include <sys/cdefs.h>
+#include <assert.h>
#ifndef lint
__RCSID("$NetBSD: fat.c,v 1.12 2000/10/10 20:24:52 is Exp $");
static const char rcsid[] =
@@ -46,12 +48,14 @@ static const char rcsid[] =
#include "ext.h"
#include "fsutil.h"
-
-static int checkclnum(struct bootblock *, int, cl_t, cl_t *);
-static int clustdiffer(cl_t, cl_t *, cl_t *, int);
-static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
-static int _readfat(int, struct bootblock *, int, u_char **);
-
+#include "fatcache.h"
+#include "fragment.h"
+static int checkclnum(struct bootblock *, cl_t, cl_t *);
+static int clustdiffer(cl_t, cl_t *, cl_t *, int,int *);
+static int tryclear(struct cluster_chain_descriptor *, cl_t, cl_t *);
+int _readfat(int, struct bootblock *, int, u_char **);
+
+static cl_t firstfreecl = 0xFFFFFFFF;
/*-
* The first 2 FAT entries contain pseudo-cluster numbers with the following
* layout:
@@ -134,27 +138,75 @@ err:
/*
* Check a cluster number for valid value
*/
-static int
-checkclnum(struct bootblock *boot, int fat, cl_t cl, cl_t *next)
+static struct fragment *lastfree= NULL;
+static struct fragment *lastbad= NULL;
+int checkclnum(struct bootblock *boot, cl_t cl, cl_t *next)
{
- if (*next >= (CLUST_RSRVD&boot->ClustMask))
+ struct fragment *frag;
+ struct fragment *insert;
+ if((*next >= (CLUST_EOFS & boot->ClustMask)) && (*next <= (CLUST_EOF & boot->ClustMask)))
+ return FSOK;
+ if(*next >= (CLUST_RSRVD & boot->ClustMask)){
*next |= ~boot->ClustMask;
+ }
+ /*if it is a free cluster,add to rb_free_root tree*/
if (*next == CLUST_FREE) {
boot->NumFree++;
+ /*find the first free cluster ,this value will be used to update fsinfo*/
+ if(firstfreecl > cl)
+ firstfreecl = cl;
+ if(lastfree){
+ if( cl == (lastfree->head + lastfree->length)){
+ lastfree->length += 1;
+ return FSOK;
+ }
+ }
+ frag = New_fragment();
+ if(!frag){
+ fsck_info("No space \n");
+ return FSERROR;
+ }
+ frag->head = cl;
+ frag->length = 1;
+ insert = RB_INSERT(FSCK_MSDOS_FRAGMENT,&rb_free_root,frag);
+ if(insert){
+ fsck_info("%s:fragment(head:0x%x) exist\n",__func__,frag->head);
+ return FSERROR;
+ }
+ lastfree = frag;
return FSOK;
}
+ /*if it is a bad cluster ,add to rb_bad_root tree*/
if (*next == CLUST_BAD) {
boot->NumBad++;
+ if(lastbad){
+ if(cl == (lastbad->head + lastbad->length)){
+ lastbad->length += 1;
+ return FSOK;
+ }
+ }
+ frag = New_fragment();
+ if(!frag){
+ fsck_info("No Space\n");
+ return FSERROR;
+ }
+ frag->head = cl;
+ frag->length = 1;
+ insert = RB_INSERT(FSCK_MSDOS_FRAGMENT,&rb_bad_root,frag);
+ if(insert){
+ fsck_info("%s:fragment(head:0x%x) exist\n",__func__,frag->head);
+ return FSERROR;
+ }
+ lastbad = frag;
return FSOK;
}
- if (*next < CLUST_FIRST
- || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
- pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n",
- cl, fat,
+ if (*next < CLUST_FIRST || (*next >= boot->NumClusters && *next < (CLUST_EOFS & boot->ClustMask))) {
+ pwarn("Cluster %u in FAT continues with %s cluster number %u\n",
+ cl,
*next < CLUST_RSRVD ? "out of range" : "reserved",
*next&boot->ClustMask);
if (ask(1, "Truncate")) {
- *next = CLUST_EOF;
+ /*do nothing about truncate*/
return FSFATMOD;
}
return FSERROR;
@@ -165,7 +217,7 @@ checkclnum(struct bootblock *boot, int fat, cl_t cl, cl_t *next)
/*
* Read a FAT from disk. Returns 1 if successful, 0 otherwise.
*/
-static int
+int
_readfat(int fs, struct bootblock *boot, int no, u_char **buffer)
{
off_t off;
@@ -203,26 +255,21 @@ _readfat(int fs, struct bootblock *boot, int no, u_char **buffer)
/*
* Read a FAT and decode it into internal format
*/
-int
-readfat(int fs, struct bootblock *boot, int no, struct fatEntry **fp)
+unsigned int *fat_bitmap;
+int checkfat(int fs, struct bootblock *boot, int no,u_char *buffer)
{
- struct fatEntry *fat;
- u_char *buffer, *p;
- cl_t cl;
- int ret = FSOK;
-
+ struct cluster_chain_descriptor *fat = NULL,*nextcl_fat,*insert,*remove,tofind;
+ struct fatcache *cache = NULL;
+ u_char *p;
+ cl_t cl,prevcl = 0, nextclus;
+ int len = 0;
+ int ret = FSOK,err = 0;
boot->NumFree = boot->NumBad = 0;
-
- if (!_readfat(fs, boot, no, &buffer))
- return FSFATAL;
-
- fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
- if (fat == NULL) {
- perror("No space for FAT");
- free(buffer);
+ fat_bitmap = calloc(boot->NumClusters/32+1,sizeof(unsigned int));
+ if(!fat_bitmap){
+ fsck_err("NO space left\n");
return FSFATAL;
}
-
if (buffer[0] != boot->Media
|| buffer[1] != 0xff || buffer[2] != 0xff
|| (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
@@ -272,49 +319,247 @@ readfat(int fs, struct bootblock *boot, int no, struct fatEntry **fp)
ret |= FSFIXFAT;
}
}
- switch (boot->ClustMask) {
- case CLUST32_MASK:
- p = buffer + 8;
- break;
- case CLUST16_MASK:
- p = buffer + 4;
- break;
- default:
- p = buffer + 3;
- break;
- }
- for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
+ fsck_info("Begin to handle the cluster chain\n");
+ for (cl = CLUST_FIRST; cl < boot->NumClusters;cl++) {
+ /*have handled it by cluster chain*/
+ if(BIT(fat_bitmap[cl/32],cl%32))
+ continue;
+ prevcl = nextclus = cl;
+ len = 0;
switch (boot->ClustMask) {
- case CLUST32_MASK:
- fat[cl].next = p[0] + (p[1] << 8)
- + (p[2] << 16) + (p[3] << 24);
- fat[cl].next &= boot->ClustMask;
- ret |= checkclnum(boot, no, cl, &fat[cl].next);
- cl++;
- p += 4;
- break;
- case CLUST16_MASK:
- fat[cl].next = p[0] + (p[1] << 8);
- ret |= checkclnum(boot, no, cl, &fat[cl].next);
- cl++;
- p += 2;
- break;
- default:
- fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
- ret |= checkclnum(boot, no, cl, &fat[cl].next);
- cl++;
- if (cl >= boot->NumClusters)
+ case CLUST32_MASK:
+ p = buffer + 4*cl;
+ break;
+ case CLUST16_MASK:
+ p = buffer + 2*cl;
+ break;
+ default:
+ p = buffer + 3*(cl/2);
break;
- fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
- ret |= checkclnum(boot, no, cl, &fat[cl].next);
- cl++;
- p += 3;
- break;
}
- }
+ while(nextclus >= CLUST_FIRST && nextclus < boot->NumClusters){
- free(buffer);
- *fp = fat;
+ switch (boot->ClustMask) {
+ case CLUST32_MASK:
+ nextclus = p[0] + (p[1] << 8)
+ + (p[2] << 16) + (p[3] << 24);
+ nextclus &= boot->ClustMask;
+ p = buffer + 4*nextclus;
+ break;
+ case CLUST16_MASK:
+ nextclus = p[0] + (p[1] << 8);
+ p = buffer + 2*nextclus;
+ break;
+ /*FAT12 is special*/
+ default:
+ /* odd */
+ if(!(nextclus & 0x1))
+ nextclus = (p[0] + (p[1] << 8)) & 0x0fff;
+ else
+ nextclus = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
+ p = buffer + 3*(nextclus/2);
+ break;
+ }
+ ret = checkclnum(boot,prevcl,&nextclus);
+ if(ret == FSERROR)
+ return -1;
+ //truncate the rest clusters
+ if(ret == FSFATMOD)
+ break;
+ len++;
+ /*
+ *TODO:because this cluster chain is special,such as
+ *fatentry->fatcache->fatcache->fatcache->NULL
+ *so you should treat the first fatcache specially
+ */
+ if(len == 1){
+ if(nextclus == CLUST_FREE || nextclus == CLUST_BAD ){
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ break;
+ }
+ }
+ /*last cluster*/
+ if((nextclus >= (CLUST_EOFS & boot->ClustMask)) && (nextclus <= (CLUST_EOF & boot->ClustMask)) && (len != 1)){
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ break;
+ }
+ /*rsrvd*/
+ if(nextclus == CLUST_FREE || ((nextclus >= (CLUST_RSRVD & boot->ClustMask)) && (nextclus < (CLUST_EOFS & boot->ClustMask)))){
+ fsck_warn("Cluster chain starting at %u ends with cluster marked %s,cl = %d ,nextclus = %d\n",cl,rsrvdcltype(nextclus),cl,nextclus);
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ /*if the next cluster is free or reversed ,just clear the existing cluster chain ,let this free or reversed cluster alone*/
+ ret |= tryclear(fat,cl,&prevcl);
+ break;
+ }
+ /*out of range*/
+ if(nextclus < CLUST_FIRST ||(( nextclus >= boot->NumClusters) && (nextclus < (CLUST_EOFS & boot->ClustMask)))){
+ fsck_warn("Clusters chain starting at %u ends with cluster out of range (%u) \n",cl,nextclus);
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ ret |= tryclear(fat,cl,&prevcl);
+ break;
+ }
+
+ if((nextclus >= CLUST_FIRST && nextclus < boot->NumClusters)&& BIT(fat_bitmap[nextclus/32],nextclus%32)){
+ /*
+ *it is interesting,because 0x3->0x34->0x35->EOF,then you find 0x100->0x3.
+ *it is right here,must merge them
+ */
+ tofind.head = nextclus;
+ nextcl_fat = RB_FIND(FSCK_MSDOS_CACHE,&rb_root,&tofind);
+ /*if nextcl_fat == fat ,unfortunately ,it is a cluster loop,such as 0x2->0x3->0x4->0x2*/
+ if(nextcl_fat && (nextcl_fat != fat)){
+ if(len == 1){
+ /*the first one ,you should malloc both fatEntry and fatcache*/
+ fat = New_fatentry();
+ if(!fat)
+ return FSFATAL;
+ fat->head = prevcl;
+ fat->length = 1;
+ /*
+ *i was puzzled whether check the pointer insert here
+ *if some error,there is a exsting fatentry in rb tree.NOT check maybe a good choice
+ */
+ insert = RB_INSERT(FSCK_MSDOS_CACHE,&rb_root,fat);
+ if(insert){
+ fsck_err("%s:fatentry(head:0x%x) exist\n",__func__,fat->head);
+ return FSFATAL;
+ }
+ cache = New_fatcache();
+ if(!cache)
+ return FSFATAL;
+ cache->head = prevcl;
+ cache->length = 1;
+ err = add_fatcache_To_ClusterChain(fat,cache);
+ if(err){
+ fsck_err("add_fatcache_To_ClusterChain ,err = %d \n",err);
+ return FSFATAL;
+ }
+ /*merge nextcl_fat chain to new one*/
+ cache->next = nextcl_fat->child;
+ fat->length += nextcl_fat->length;
+ }else{
+ /*
+ *we use fat directly here,after handling a cluster chain ,must set fat = NULL,
+ *otherwise ,the fat is prev cluster chain
+ */
+ add_fatcache_Totail(fat,nextcl_fat->child);
+ fat->length += nextcl_fat->length;
+ }
+ nextcl_fat->child = NULL;
+ /*now delete nextcl_fat entry ,because have merge its child to fat*/
+ remove = RB_REMOVE(FSCK_MSDOS_CACHE,&rb_root,nextcl_fat);
+ free(nextcl_fat);
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ break;
+ }
+ /*
+ *it is very complex here,if a cluster has been handled ,but it is not a head of a cluster chain,there are some cases:
+ *case 1:Due to some error ,this cluster has been removed from rb tree by tryclear()
+ *case 2:clsuter chains linked
+ *case 3:cluster loop
+ *whatever ,i think tryclear() is a simplest solution
+ */
+ fsck_err("Cluster chian is wrong\n");
+ Dump_fatentry(fat);
+ Dump_fatentry(nextcl_fat);
+ /*sometimes ,fat == NULL here,it means this cluster chain haven't be insert to rb tree,ok,do nothing here*/
+ if(!fat)
+ break;
+ if(ask(1,"Clear chain starting at %u",nextclus)){
+ /*
+ *compare with orginal code,i delete some codes here
+ *because i handle fat chain by chain here,
+ *it never appear situation that three or more cluster chains linked
+ */
+ ret |= tryclear(fat,cl,&prevcl);
+ break;
+ }
+ }
+ /*it is a legal cluster ,add it*/
+ SET_BIT(fat_bitmap[prevcl/32],prevcl%32);
+ if(len == 1){
+ /*TODO:
+ *that is the first cluster of this legal chain
+ *it is special ,normally, we just add nextcluster to chain
+ *but if it is first one ,we must add both two.
+ */
+ fat = New_fatentry();
+ if(!fat){
+ fsck_err("No space \n");
+ return FSFATAL;
+ }
+ fat->head = cl;
+ insert = RB_INSERT(FSCK_MSDOS_CACHE,&rb_root,fat);
+ if(insert){
+ fsck_err("%s:fatentry(head:0x%x) exist\n",__func__,fat->head);
+ return FSFATAL;
+ }
+ cache = New_fatcache();
+ if(!cache){
+ fsck_err("No space \n");
+ return FSFATAL;
+ }
+ cache->head = prevcl;
+ cache->length = 1;
+ err = add_fatcache_To_ClusterChain(fat,cache);
+ if(err){
+ fsck_err("add_fatcache_To_ClusterChain ,err = %d \n",err);
+ }
+ if(nextclus >= (CLUST_EOFS & boot->ClustMask) && nextclus <= (CLUST_EOF & boot->ClustMask)){
+ break;
+ }
+ if(prevcl + 1 == nextclus){
+ cache->length += 1;
+ fat->length += 1;
+ prevcl = nextclus;
+ continue;
+ }else{
+ cache = New_fatcache();
+ if(!cache){
+ fsck_err("No space\n");
+ return FSFATAL;
+ }
+ cache->head = nextclus;
+ cache->length = 1;
+ err = add_fatcache_To_ClusterChain(fat,cache);
+ if(err){
+ fsck_err("add_fatcache_To_ClusterChain ,err = %d \n",err);
+ }
+ }
+ }else{
+ if(nextclus >= (CLUST_EOFS & boot->ClustMask) && nextclus <= (CLUST_EOF & boot->ClustMask)){
+ break;
+ }
+ if( prevcl + 1 == nextclus){
+ /*if it is continuous ,just modify the length*/
+ cache->length += 1;
+ fat->length += 1;
+ }else{
+ cache = New_fatcache();
+ if(!cache){
+ fsck_err("No Space\n");
+ return FSFATAL;
+ }
+ cache->head = nextclus;
+ cache->length = 1;
+ err = add_fatcache_To_ClusterChain(fat,cache);
+ if(err){
+ fsck_err("add_fatcache_To_ClusterChain ,err = %d \n",err);
+ }
+ }
+ }
+ prevcl = nextclus;
+ }
+ /*set fat = NULL,otherwise this fat pointer will impact the next process*/
+ fat = NULL;
+ }
+#if 0
+ fsck_info("Dump cluster chains\n");
+ RB_FOREACH(fat, FSCK_MSDOS_CACHE,&rb_root){
+ fsck_info("head:0x%x:length:0x%x\n",fat->head,fat->length);
+ }
+#endif
+ free(fat_bitmap);
return ret;
}
@@ -332,10 +577,14 @@ rsrvdcltype(cl_t cl)
return "as EOF";
return "bad";
}
-
+/*
+ *if *res = 1,that means *cp1 = *cp2
+ *if *res = 0 ,means *cp2 = *cp1;
+ */
static int
-clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
+clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum, int *res)
{
+ fsck_debug("clustdiff:%u : %u \n",*cp1,*cp2);
if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
@@ -344,7 +593,7 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
pwarn("Cluster %u is marked %s with different indicators\n",
cl, rsrvdcltype(*cp1));
if (ask(1, "Fix")) {
- *cp2 = *cp1;
+ *res = 0;
return FSFATMOD;
}
return FSFATAL;
@@ -352,11 +601,11 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
if (ask(1, "Use FAT 0's entry")) {
- *cp2 = *cp1;
+ *res = 0;
return FSFATMOD;
}
if (ask(1, "Use FAT %d's entry", fatnum)) {
- *cp1 = *cp2;
+ *res = 1;
return FSFATMOD;
}
return FSFATAL;
@@ -364,11 +613,11 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
cl, rsrvdcltype(*cp1), *cp2, fatnum);
if (ask(1, "Use continuation from FAT %d", fatnum)) {
- *cp1 = *cp2;
+ *res = 1;
return FSFATMOD;
}
if (ask(1, "Use mark from FAT 0")) {
- *cp2 = *cp1;
+ *res = 0;
return FSFATMOD;
}
return FSFATAL;
@@ -377,11 +626,11 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
cl, *cp1, rsrvdcltype(*cp2), fatnum);
if (ask(1, "Use continuation from FAT 0")) {
- *cp2 = *cp1;
+ *res = 0;
return FSFATMOD;
}
if (ask(1, "Use mark from FAT %d", fatnum)) {
- *cp1 = *cp2;
+ *res = 1;
return FSFATMOD;
}
return FSERROR;
@@ -389,11 +638,11 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
cl, *cp1, *cp2, fatnum);
if (ask(1, "Use continuation from FAT 0")) {
- *cp2 = *cp1;
+ *res = 0;
return FSFATMOD;
}
if (ask(1, "Use continuation from FAT %d", fatnum)) {
- *cp1 = *cp2;
+ *res = 1;
return FSFATMOD;
}
return FSERROR;
@@ -404,168 +653,136 @@ clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
* into the first one.
*/
int
-comparefat(struct bootblock *boot, struct fatEntry *first,
- struct fatEntry *second, int fatnum)
+comparefat(struct bootblock *boot, u_char*first, u_char *second, int fatnum)
{
cl_t cl;
- int ret = FSOK;
+ u_char *sp,*fp,*wp;
+ int ret = FSOK,res = 0;
+ cl_t first_cl,second_cl,w_cl;
+ fsck_info("Begin to compare FAT\n");
+ for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++){
+ switch(boot->ClustMask){
+ case CLUST32_MASK:
+ fp = first + 4*cl;
+ sp = second + 4*cl;
+ first_cl = (fp[0] + (fp[1]<<8) + (fp[2]<<16) + (fp[3]<<24)) & boot->ClustMask;
+ second_cl = (sp[0] + (sp[1]<<8) + (sp[2]<<16) + (sp[3]<<24)) & boot->ClustMask;
+ break;
+
+ case CLUST16_MASK:
+ fp = first + 2*cl;
+ sp = second + 2*cl;
+ first_cl = (fp[0] + (fp[1] << 8)) & boot->ClustMask;
+ second_cl = (sp[0] + (sp[1] << 8)) & boot->ClustMask;
+ break;
+
+ default:
+ fp = first + 3*(cl/2);
+ sp = second + 3*(cl/2);
+ if(cl & 0x1){
+ first_cl = ((fp[1]>>4) + (fp[2]<<4)) & 0x0fff;
+ second_cl = ((sp[1]>>4) + (sp[2]<<4)) & 0x0fff;
+ }else{
+ first_cl = (fp[0] + (fp[1] << 8)) & 0x0fff;
+ second_cl = (sp[0] + (sp[1] << 8)) & 0x0fff;
+ }
+ break;
+ }
+ if(first_cl == second_cl)
+ continue;
+ fsck_warn("%u is not same(%u ; %u)\n",cl,first_cl,second_cl);
+ ret |= clustdiffer(cl, &first_cl,&second_cl, fatnum,&res);
+ if(res){
+ wp = fp;
+ w_cl = second_cl;
+ }else{
+ wp = sp;
+ w_cl = first_cl;
+ }
+ /* fisrt_cl = second_cl */
+ switch(boot->ClustMask){
+ case CLUST32_MASK:
+ *wp++ = (u_char)w_cl;
+ *wp++ = (u_char)(w_cl >>8);
+ *wp++ = (u_char)(w_cl >> 16);
+ *wp &= 0xf0;
+ *wp |= (w_cl >>24) &0x0f;
+ break;
+
+ case CLUST16_MASK:
+ *wp++ = (u_char)w_cl;
+ *wp = (u_char)(w_cl >> 8);
+ break;
- for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
- if (first[cl].next != second[cl].next)
- ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
+ default:
+ if(cl & 0x1){
+ /* wp[1] ,wp[2]*/
+ wp++;
+ *wp++ |= (u_char)((w_cl << 4) & 0xf0);
+ *wp = (u_char)(w_cl >> 4);
+ }else{
+ /* wp[0] ,wp[1]*/
+ *wp++ = (u_char)w_cl;
+ *wp |= (u_char)((w_cl >> 8) & 0x0f);
+ }
+ break;
+ }
+ }
return ret;
}
void
-clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
+clearchain(struct cluster_chain_descriptor *fat, cl_t head)
{
- cl_t p, q;
-
- for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
- if (fat[p].head != head)
- break;
- q = fat[p].next;
- fat[p].next = fat[p].head = CLUST_FREE;
- fat[p].length = 0;
- }
+ fsck_debug("%s:fat:%p , head(%d) ,length(%d)\n",__func__,fat,fat->head,fat->length);
+ assert(fat);
+ if(fat->head != head)
+ return ;
+ /*must remove from rb tree before free*/
+ RB_REMOVE(FSCK_MSDOS_CACHE,&rb_root,fat);
+ free(fat);
}
int
-tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *trunc)
+tryclear(struct cluster_chain_descriptor *fat, cl_t head, cl_t *trunc)
{
+ fsck_debug("fat:%p ,head :%d ,trunc :%d \n",fat,head,*trunc);
+ if(!fat || !trunc){
+ pwarn("%s :null pointer\n",__func__);
+ return FSERROR;
+ }
if (ask(1, "Clear chain starting at %u", head)) {
- clearchain(boot, fat, head);
+ clearchain(fat, head);
return FSFATMOD;
} else if (ask(1, "Truncate")) {
- *trunc = CLUST_EOF;
+ Trunc(fat,*trunc);
return FSFATMOD;
} else
return FSERROR;
}
/*
- * Check a complete FAT in-memory for crosslinks
- */
-int
-checkfat(struct bootblock *boot, struct fatEntry *fat)
-{
- cl_t head, p, h, n, wdk;
- u_int len;
- int ret = 0;
- int conf;
-
- /*
- * pass 1: figure out the cluster chains.
- */
- for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
- /* find next untravelled chain */
- if (fat[head].head != 0 /* cluster already belongs to some chain */
- || fat[head].next == CLUST_FREE
- || fat[head].next == CLUST_BAD)
- continue; /* skip it. */
-
- /* follow the chain and mark all clusters on the way */
- for (len = 0, p = head;
- p >= CLUST_FIRST && p < boot->NumClusters;
- p = fat[p].next) {
- /* we have to check the len, to avoid infinite loop */
- if (len > boot->NumClusters) {
- printf("detect cluster chain loop: head %u for p %u\n", head, p);
- break;
- }
-
- fat[p].head = head;
- len++;
- }
-
- /* the head record gets the length */
- fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
- }
-
- /*
- * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
- * we didn't know the real start of the chain then - would have treated partial
- * chains as interlinked with their main chain)
- */
- for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
- /* find next untravelled chain */
- if (fat[head].head != head)
- continue;
-
- /* follow the chain to its end (hopefully) */
- /* also possible infinite loop, that's why I insert wdk counter */
- for (p = head,wdk=boot->NumClusters;
- (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters && wdk;
- p = n,wdk--) {
- if (fat[n].head != head)
- break;
- }
-
- if (n >= CLUST_EOFS)
- continue;
-
- if (n == CLUST_FREE || n >= CLUST_RSRVD) {
- pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
- head, rsrvdcltype(n));
- ret |= tryclear(boot, fat, head, &fat[p].next);
- continue;
- }
- if (n < CLUST_FIRST || n >= boot->NumClusters) {
- pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
- head, n);
- ret |= tryclear(boot, fat, head, &fat[p].next);
- continue;
- }
- pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
- head, fat[n].head, n);
- conf = tryclear(boot, fat, head, &fat[p].next);
- if (ask(1, "Clear chain starting at %u", h = fat[n].head)) {
- if (conf == FSERROR) {
- /*
- * Transfer the common chain to the one not cleared above.
- */
- for (p = n;
- p >= CLUST_FIRST && p < boot->NumClusters;
- p = fat[p].next) {
- if (h != fat[p].head) {
- /*
- * Have to reexamine this chain.
- */
- head--;
- break;
- }
- fat[p].head = head;
- }
- }
- clearchain(boot, fat, h);
- conf |= FSFATMOD;
- }
- ret |= conf;
- }
-
- return ret;
-}
-
-/*
* Write out FATs encoding them from the internal format
*/
int
-writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
+writefat(int fs, struct bootblock *boot, int correct_fat)
{
u_char *buffer, *p;
cl_t cl;
- int i;
+ unsigned int i;
u_int32_t fatsz;
off_t off;
int ret = FSOK;
-
+ struct cluster_chain_descriptor *fat;
+ struct fatcache* cache,*next_cache;
+ struct fragment *frag;
+ fsck_debug("begin to writefat \n");
buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
if (buffer == NULL) {
perror("No space for FAT");
return FSFATAL;
}
memset(buffer, 0, fatsz);
- boot->NumFree = 0;
p = buffer;
if (correct_fat) {
*p++ = (u_char)boot->Media;
@@ -610,38 +827,45 @@ writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
free(old_fat);
p += count;
}
-
- for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
- switch (boot->ClustMask) {
- case CLUST32_MASK:
- if (fat[cl].next == CLUST_FREE)
- boot->NumFree++;
- *p++ = (u_char)fat[cl].next;
- *p++ = (u_char)(fat[cl].next >> 8);
- *p++ = (u_char)(fat[cl].next >> 16);
- *p &= 0xf0;
- *p++ |= (fat[cl].next >> 24)&0x0f;
- break;
- case CLUST16_MASK:
- if (fat[cl].next == CLUST_FREE)
- boot->NumFree++;
- *p++ = (u_char)fat[cl].next;
- *p++ = (u_char)(fat[cl].next >> 8);
- break;
- default:
- if (fat[cl].next == CLUST_FREE)
- boot->NumFree++;
- if (cl + 1 < boot->NumClusters
- && fat[cl + 1].next == CLUST_FREE)
- boot->NumFree++;
- *p++ = (u_char)fat[cl].next;
- *p++ = (u_char)((fat[cl].next >> 8) & 0xf)
- |(u_char)(fat[cl+1].next << 4);
- *p++ = (u_char)(fat[++cl].next >> 4);
- break;
+
+ fsck_info("begin to write FAT\n");
+ fat = RB_MIN(FSCK_MSDOS_CACHE,&rb_root);
+ if(!fat){
+ fsck_info("%s:rb tree is empty\n",__func__);
+ return FSFATAL;
+ }
+ fsck_info("write valid cluster chain\n");
+ while(fat){
+ cache = fat->child;
+ while(cache){
+ cl = cache->head;
+ for( i = 0 ; i < (cache->length - 1);i++)
+ SetNextClusToFAT(boot,buffer,cl+i ,cl+i+1);
+ next_cache = cache->next;
+ if(next_cache)
+ SetNextClusToFAT(boot,buffer,cl+cache->length -1,next_cache->head);
+ else
+ SetNextClusToFAT(boot,buffer,cl+cache->length -1,CLUST_EOF);
+ cache = next_cache;
}
+ fat = RB_NEXT(FSCK_MSDOS_CACHE,0,fat);
+ }
+ /*the FreeNumber may be not correct*/
+ fsck_info("write free cluster\n");
+ RB_FOREACH(frag, FSCK_MSDOS_FRAGMENT,&rb_free_root){
+ cl = frag->head;
+ for(i = 0 ; i < frag->length ;i++)
+ SetNextClusToFAT(boot,buffer,cl+i ,CLUST_FREE);
}
+ fsck_info("write bad cluster\n");
+ RB_FOREACH(frag, FSCK_MSDOS_FRAGMENT,&rb_bad_root){
+ cl = frag->head;
+ for(i = 0 ; i < frag->length ;i++)
+ SetNextClusToFAT(boot,buffer,cl+i ,CLUST_BAD);
+ }
+ fsck_debug("write FATs\n");
for (i = 0; i < boot->FATs; i++) {
+ fsck_debug("write FAT copy %d \n",i);
off = boot->ResSectors + i * boot->FATsecs;
off *= boot->BytesPerSec;
if (lseek(fs, off, SEEK_SET) != off
@@ -658,40 +882,42 @@ writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
* Check a complete in-memory FAT for lost cluster chains
*/
int
-checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
+checklost(int dosfs, struct bootblock *boot)
{
- cl_t head;
int mod = FSOK;
int ret;
-
- for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
- /* find next untravelled chain */
- if (fat[head].head != head
- || fat[head].next == CLUST_FREE
- || (fat[head].next >= CLUST_RSRVD
- && fat[head].next < CLUST_EOFS)
- || (fat[head].flags & FAT_USED))
+ struct cluster_chain_descriptor *fat ;
+ fat = RB_MIN(FSCK_MSDOS_CACHE,&rb_root);
+ if(!fat){
+ fsck_err("%s:rb_root tree is empty\n",__func__);
+ return FSFATAL;
+ }
+ while(fat){
+ if(fat->flag & FAT_USED){
+ fat = RB_NEXT(FSCK_MSDOS_CACHE,0,fat);
continue;
-
- pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
- head, fat[head].length);
- mod |= ret = reconnect(dosfs, boot, fat, head);
+ }
+ fsck_info("Lost cluster chain at head %u ,%d Cluster(s) lost\n",fat->head, fat->length);
+ mod |= ret = reconnect(dosfs, boot,fat, fat->head);
if (mod & FSFATAL) {
/* If the reconnect failed, then just clear the chain */
pwarn("Error reconnecting chain - clearing\n");
mod &= ~FSFATAL;
- clearchain(boot, fat, head);
+ clearchain(fat,fat->head);
mod |= FSFATMOD;
+ fat = RB_NEXT(FSCK_MSDOS_CACHE,0,fat);
continue;
}
if (ret == FSERROR && ask(1, "Clear")) {
- clearchain(boot, fat, head);
+ clearchain(fat, fat->head);
mod |= FSFATMOD;
}
+ fat = RB_NEXT(FSCK_MSDOS_CACHE,0,fat);
}
finishlf();
-
- if (boot->FSInfo) {
+ fsck_debug("Verify Filesystem information\n");
+ //verify the fs infomation
+ if (boot->FSInfo){
ret = 0;
if (boot->FSFree != boot->NumFree) {
pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
@@ -703,37 +929,19 @@ checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
}
if (boot->NumFree) {
- if ((boot->FSNext >= boot->NumClusters) || (fat[boot->FSNext].next != CLUST_FREE)) {
- pwarn("Next free cluster in FSInfo block (%u) not free\n",
- boot->FSNext);
- if (ask(1, "Fix"))
- for (head = CLUST_FIRST; head < boot->NumClusters; head++)
- if (fat[head].next == CLUST_FREE) {
- boot->FSNext = head;
- ret = 1;
- break;
- }
+ if ((boot->FSNext >= boot->NumClusters)) {
+ pwarn("Next free cluster in FSInfo block out of range\n");
+ if (ask(1, "Fix")){
+ boot->FSNext = firstfreecl;
+ ret = 1;
+ }
}
- }
-
- if (boot->FSNext > boot->NumClusters ) {
+ }
+ if (boot->FSNext > boot->NumClusters || boot->FSNext < CLUST_FIRST) {
pwarn("FSNext block (%d) not correct NumClusters (%d)\n",
boot->FSNext, boot->NumClusters);
boot->FSNext=CLUST_FIRST; // boot->FSNext can have -1 value.
- }
-
- if (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE) {
- pwarn("Next free cluster in FSInfo block (%u) not free\n",
- boot->FSNext);
- if (ask(1, "Fix"))
- for (head = CLUST_FIRST; head < boot->NumClusters; head++)
- if (fat[head].next == CLUST_FREE) {
- boot->FSNext = head;
- ret = 1;
- break;
- }
- }
-
+ }
if (ret)
mod |= writefsinfo(dosfs, boot);
}
diff --git a/fatcache.c b/fatcache.c
new file mode 100644
index 0000000..2842f83
--- /dev/null
+++ b/fatcache.c
@@ -0,0 +1,309 @@
+/*
+*Copyright (c) 2012, The Linux Foundation. All rights reserved.
+*Redistribution and use in source and binary forms, with or without
+*modification, are permitted provided that the following conditions are
+*met:
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of The Linux Foundation nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
+*/
+#include <string.h>
+#include "dosfs.h"
+#include "ext.h"
+#include "fatcache.h"
+#include "fsutil.h"
+#include <stdio.h>
+#include <unistd.h>
+#include "tree.h"
+int fsck_msdos_cache_compare(struct cluster_chain_descriptor *fat1,struct cluster_chain_descriptor *fat2)
+{
+ if(fat1->head > fat2->head)
+ return 1;
+ else if(fat1->head < fat2->head)
+ return -1;
+ else
+ return 0;
+}
+struct FSCK_MSDOS_CACHE rb_root;
+RB_GENERATE(FSCK_MSDOS_CACHE,cluster_chain_descriptor,rb,fsck_msdos_cache_compare);
+unsigned int GetNextClusFromFAT( struct bootblock*boot,u_char*fatable,unsigned int clust)
+{
+ unsigned int nextclus;
+ if(!fatable){
+ fsck_err("%s:No FAT table \n",__func__);
+ return 0;
+ }
+ switch(boot->ClustMask){
+ case CLUST32_MASK:
+ nextclus = fatable[4*clust] + (fatable[4*clust+1]<<8) + (fatable[4*clust+2]<<16) + (fatable[4*clust+3]<<24);
+ nextclus &= boot->ClustMask;
+ break;
+
+ case CLUST16_MASK:
+ nextclus = fatable[2*clust] + (fatable[2*clust+1]<<8);
+ nextclus &= boot->ClustMask;
+ break;
+
+ default:
+ if(clust & 0x1)
+ nextclus = ((fatable[3*(clust/2)+1]>>4) + (fatable[3*(clust/2)+2]<<4)) & 0x0fff;
+ else
+ nextclus = (fatable[3*(clust/2)] + (fatable[3*(clust/2)+1]<<8)) & 0x0fff;
+ break;
+ }
+ return nextclus;
+}
+
+void SetNextClusToFAT(struct bootblock*boot,u_char*fat ,unsigned int cl ,unsigned int next)
+{
+ /*fat must point to the head of FAT*/
+ u_char* p;
+ if(!fat){
+ fsck_err("%s :No FAT table \n",__func__);
+ return ;
+ }
+ switch(boot->ClustMask){
+ case CLUST32_MASK:
+ p = fat + 4*cl;
+ *p++ = (u_char)next;
+ *p++ = (u_char)(next >>8);
+ *p++ = (u_char)(next >> 16);
+ *p &= 0xf0;
+ *p = (next >> 24) & 0x0f;
+ break;
+
+ case CLUST16_MASK:
+ p = fat + 2*cl;
+ *p++ = (u_char)next;
+ *p = (u_char)(next >> 8);
+ break;
+
+ default:
+ p = fat + 3*(cl/2);
+ if(cl & 0x1){
+ p++;
+ *p++ |= (u_char)(next << 4);
+ *p = (u_char)(next >> 4);
+ }else{
+ *p++ = (u_char)next;
+ *p |= (next >> 8) & 0x0f;
+ }
+ break;
+
+ }
+}
+
+/*
+ *dump a cluster chain for test
+ */
+void Dump_fatentry(struct cluster_chain_descriptor *fat)
+{
+ struct fatcache *cache;
+ if(!fat){
+ fsck_warn("%s;NULL pointer\n",__func__);
+ return ;
+ }
+ fsck_info("head: 0x%d:",fat->head);
+ cache = fat->child;
+ while(cache){
+ fsck_info(" 0x%d:0x%d ->" ,cache->head,cache->length);
+ cache = cache->next;
+ }
+ fsck_info("EOF\n");
+}
+
+int add_fatcache_To_ClusterChain(struct cluster_chain_descriptor *fatentry ,struct fatcache *new)
+{
+ struct fatcache *cache = fatentry->child;
+ if(!fatentry || !new){
+ fsck_warn("%s:NULL pointer\n",__func__);
+ return -1;
+ }
+ /*NULL*/
+ if(!cache){
+ fatentry->child = new;
+ new->next = NULL;
+ fatentry->head = new->head;
+ fatentry->length = new->length;
+ return 0;
+ }
+ /*DO NOT sort,just add to the tail*/
+ while(cache->next){
+ cache = cache->next;
+ }
+ cache->next = new;
+ new->next = NULL;
+ fatentry->length += new->length;
+ return 0;
+}
+/*
+ *Function : add_fatcache_Totail
+ *this function is used to merge two existing cluster chain
+ *It just add a fatcache to the tail of another fatentry
+ */
+int add_fatcache_Totail(struct cluster_chain_descriptor *fatentry ,struct fatcache *new)
+{
+ struct fatcache *cache;
+ if(!fatentry || !new || !fatentry->child){
+ fsck_warn("%s:NULL pointer\n",__func__);
+ return -1;
+ }
+ cache = fatentry->child;
+ while(cache->next){
+ cache = cache->next;
+ }
+ cache->next = new;
+ return 0;
+}
+/*
+ *NOTE:
+ *if *prev_cache = return cache,that means the cache we find in cluster chain is the first one
+ */
+struct fatcache *Find_cache(struct cluster_chain_descriptor *fat,unsigned int cl ,struct fatcache**prev_cache)
+{
+ struct fatcache *cache = fat->child,*prev;
+ prev = cache;
+ while(cache){
+ if( cl >= cache->head && cl < (cache->head + cache->length)){
+ *prev_cache = prev;
+ return cache;
+ }
+ prev = cache;
+ cache = cache->next;
+ }
+ return EMPTY_CACHE;
+}
+
+/*
+*find the next cluster from fatentry
+*/
+struct fatcache* Find_nextclus(struct cluster_chain_descriptor* fat,unsigned int clus, unsigned int* cl)
+{
+ struct fatcache* cache = fat->child;
+ *cl = 0x0;
+ if(!cache){
+ fsck_warn("Not find the cluster after cluster %d\n",clus);
+ return (struct fatcache*)0;
+ }
+ if(clus < fat->head){
+ fsck_warn("out of range,clus: %d ,fat->head:%d\n",clus,fat->head);
+ return (struct fatcache*)0;
+ }
+ while(cache){
+ if(clus >= cache->head && clus <= cache->head + cache->length -2 ){
+ *cl = clus + 1;
+ return cache;
+ }
+ if(clus == cache->head + cache->length -1 ){
+ cache = cache->next;
+ if(cache){
+ *cl = cache->head;
+ return cache;
+ }else{
+ *cl = CLUST_EOF;
+ return (struct fatcache*)0;
+ }
+ }
+ cache = cache->next;
+ }
+ return EMPTY_CACHE;
+}
+int delete_fatcache_below(struct cluster_chain_descriptor * fatentry,struct fatcache*cache)
+{
+ struct fatcache *curr = cache,*next,*last;
+ last = cache;
+ if(!cache || !fatentry){
+ fsck_warn("%s:NULL pointer\n",__func__);
+ return -1;
+ }
+ next = curr->next;
+ if(!next)
+ return 0;
+ while(next){
+ curr = next;
+ next = next->next;
+ fatentry->length -= curr->length;
+ free((void*)curr);
+ }
+ last->next = NULL;
+ return 0;
+}
+
+/*remove clusters after cl*/
+void Trunc(struct cluster_chain_descriptor *fat, unsigned int cl)
+{
+ fsck_info("fat :%p ,cl : %d \n",fat,cl);
+ struct fatcache*prev ;
+ struct fatcache*cache = Find_cache(fat,cl,&prev);
+ if(!cache)
+ return ;
+ delete_fatcache_below(fat,cache);
+ cache->length = cl - cache->head + 1;
+ fat->length -= (cache->length - (cl - cache->head) - 1);
+}
+
+struct cluster_chain_descriptor* New_fatentry(void)
+{
+ struct cluster_chain_descriptor *fat;
+ fat = calloc(1,sizeof(struct cluster_chain_descriptor));
+ if(!fat){
+ fsck_warn("No space\n");
+ return fat;
+ }
+ RB_SET(fat, NULL, rb);
+ return fat;
+}
+
+struct fatcache* New_fatcache(void)
+{
+ struct fatcache *cache;
+ cache = calloc(1,sizeof(struct fatcache));
+ if(!cache)
+ fsck_warn("No space \n");
+ return cache;
+}
+
+void free_rb_tree(void)
+{
+ struct cluster_chain_descriptor *fat ,*next_fat;
+ struct fatcache *cache ,*next_cache;
+ fsck_info("%s \n",__func__);
+ fat = RB_MIN(FSCK_MSDOS_CACHE,&rb_root);
+ if(!fat){
+ fsck_info("%s :rb tree is empty\n",__func__);
+ return ;
+ }
+ while(fat){
+ cache = fat->child;
+ if(!cache)
+ continue;
+ while(cache->next){
+ next_cache = cache->next;
+ free(cache);
+ cache = next_cache;
+ }
+ next_fat = RB_NEXT(FSCK_MSDOS_CACHE,0,fat);
+ /*must remove from rb tree before free*/
+ RB_REMOVE(FSCK_MSDOS_CACHE,&rb_root,fat);
+ free(fat);
+ fat = next_fat;
+ }
+}
diff --git a/fatcache.h b/fatcache.h
new file mode 100644
index 0000000..ea8d5ff
--- /dev/null
+++ b/fatcache.h
@@ -0,0 +1,86 @@
+/*
+*Copyright (c) 2012, The Linux Foundation. All rights reserved.
+*Redistribution and use in source and binary forms, with or without
+*modification, are permitted provided that the following conditions are
+*met:
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of The Linux Foundation nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
+*/
+
+#ifndef _FATCACHE_H_
+#define _FATCACHE_H_
+#include "dosfs.h"
+#include "tree.h"
+#include "stddef.h"
+#include <cutils/log.h>
+#include <android/log.h>
+#define EMPTY_FAT (( struct cluster_chain_descriptor*)0)
+#define EMPTY_CACHE (( struct fatcache*)0)
+#define BIT(x,n) (((x)>>(n)) & 0x1)
+#define SET_BIT(x,n) do{ \
+ x |= 1<<n;}while(0)
+#define CLEAR_BIT(x,n) do{ \
+ x &= ~(1<<n);}while(0)
+
+/*
+ *print information when handle cluster chain
+ */
+#define FSCK_SLOGI(...) ((void)__android_log_buf_print(LOG_ID_SYSTEM, ANDROID_LOG_INFO,"fsck_msdos", __VA_ARGS__))
+#define FSCK_SLOGW(...) ((void)__android_log_buf_print(LOG_ID_SYSTEM, ANDROID_LOG_WARN,"fsck_msdos", __VA_ARGS__))
+#define FSCK_SLOGE(...) ((void)__android_log_buf_print(LOG_ID_SYSTEM, ANDROID_LOG_ERROR,"fsck_msdos", __VA_ARGS__))
+#define FSCK_SLOGD(...) ((void)__android_log_buf_print(LOG_ID_SYSTEM, ANDROID_LOG_DEBUG,"fsck_msdos", __VA_ARGS__))
+#define fsck_info FSCK_SLOGI
+#define fsck_warn FSCK_SLOGW
+#define fsck_err FSCK_SLOGE
+#define fsck_debug FSCK_SLOGD
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+#define container_of(ptr, type, member) \
+ ((type *)((unsigned long)(ptr) - offsetof(type, member)))
+int fsck_msdos_cache_compare(struct cluster_chain_descriptor *fat1,struct cluster_chain_descriptor *fat2);
+RB_HEAD(FSCK_MSDOS_CACHE,cluster_chain_descriptor);
+extern RB_FIND(name, x, y);
+extern RB_REMOVE(name, x, y);
+extern RB_NEXT(name, x, y);
+extern RB_INSERT(name, x, y);
+extern struct FSCK_MSDOS_CACHE rb_root;
+extern unsigned int * fat_bitmap;
+typedef unsigned char u_char;
+/*if necessary ,we can find the nextclust from FAT table*/
+unsigned int GetNextClusFromFAT(struct bootblock *boot,u_char*fatable,unsigned int clust);
+/*set the next cluster in FAT table*/
+void SetNextClusToFAT(struct bootblock*boot,u_char*fat ,unsigned int cl ,unsigned int next);
+struct cluster_chain_descriptor* New_fatentry(void);
+struct fatcache* New_fatcache(void);
+/*insert an new fatcache to fatentry . if exist ,merge it*/
+int add_fatcache_To_ClusterChain(struct cluster_chain_descriptor *fatentry ,struct fatcache *new);
+/*add an new fatcache to the tail of fatentry*/
+int add_fatcache_Totail(struct cluster_chain_descriptor *fatentry ,struct fatcache *new);
+/*find the cache which the cl is belong to ,cache2 return the prev fatcache*/
+struct fatcache *Find_cache(struct cluster_chain_descriptor *fat,unsigned int cl,struct fatcache**cache2);
+/*find the next cluster*/
+struct fatcache *Find_nextclus(struct cluster_chain_descriptor* fat,unsigned int clus, unsigned int* cl);
+int delete_fatcache_below(struct cluster_chain_descriptor* fatentry,struct fatcache*cache);
+void Trunc(struct cluster_chain_descriptor *fat, unsigned int cl);
+void free_rb_tree(void);
+/*for test*/
+void Dump_fatentry(struct cluster_chain_descriptor *fat);
+#endif
diff --git a/fragment.c b/fragment.c
new file mode 100644
index 0000000..53b9271
--- /dev/null
+++ b/fragment.c
@@ -0,0 +1,78 @@
+/*
+*Copyright (c) 2012, The Linux Foundation. All rights reserved.
+*Redistribution and use in source and binary forms, with or without
+*modification, are permitted provided that the following conditions are
+*met:
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of The Linux Foundation nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
+*/
+#include "fragment.h"
+#include "malloc.h"
+#include "fatcache.h"
+static int fsck_msdos_fragment_compare(struct fragment *frag1 ,struct fragment *frag2)
+{
+ if(frag1->head > frag2->head)
+ return 1;
+ else if(frag1->head < frag2->head)
+ return -1;
+ else
+ return 0;
+}
+RB_GENERATE(FSCK_MSDOS_FRAGMENT,fragment,rb,fsck_msdos_fragment_compare);
+struct fragment* New_fragment(void)
+{
+ struct fragment *frag;
+ frag = calloc(1,sizeof(struct fragment));
+ if(!frag){
+ fsck_warn("%s,No space left \n",__func__);
+ return EMPTY_FRAGMENT;
+ }
+ RB_SET(frag,NULL,rb);
+ return frag;
+}
+
+
+void free_fragment_tree(struct FSCK_MSDOS_FRAGMENT* head)
+{
+ struct fragment * frag,*next_frag;
+ /*
+ *avoid using function RB_FOREACH here
+ *RB_FOREACH(frag, FSCK_MSDOS_FRAGMENT,head)
+ * free(frag);
+ * is dangerous here
+ */
+ fsck_info("free_fragment_tree\n");
+ frag = RB_MIN(FSCK_MSDOS_FRAGMENT,head);
+ if(!frag){
+ fsck_info("%s: rb_tree is empty \n",__func__);
+ return ;
+ }
+ while(frag){
+ next_frag = RB_NEXT(FSCK_MSDOS_FRAGMENT,0,frag);
+ /*before free it ,must remove it from the rb_tree*/
+ RB_REMOVE(FSCK_MSDOS_FRAGMENT,head,frag);
+ free(frag);
+ frag = next_frag;
+ }
+}
+
+struct FSCK_MSDOS_FRAGMENT rb_free_root,rb_bad_root;
diff --git a/fragment.h b/fragment.h
new file mode 100644
index 0000000..b98f1e0
--- /dev/null
+++ b/fragment.h
@@ -0,0 +1,49 @@
+/*
+*Copyright (c) 2012, The Linux Foundation. All rights reserved.
+*Redistribution and use in source and binary forms, with or without
+*modification, are permitted provided that the following conditions are
+*met:
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of The Linux Foundation nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
+*/
+
+#ifndef _FRAGMENT_H_
+#define _FRAGMENT_H_
+#include "tree.h"
+#include "fsutil.h"
+#include "stddef.h"
+#include "stdio.h"
+struct fragment {
+ unsigned int head;
+ unsigned int length;
+ RB_ENTRY(fragment) rb;
+};
+#define EMPTY_FRAGMENT ((struct fragment*)0)
+RB_HEAD(FSCK_MSDOS_FRAGMENT,fragment) ;
+extern struct FSCK_MSDOS_FRAGMENT rb_free_root,rb_bad_root;
+void free_fragment_tree(struct FSCK_MSDOS_FRAGMENT* head);
+struct fragment* New_fragment(void);
+extern RB_FIND(name, x, y);
+extern RB_REMOVE(name, x, y);
+extern RB_NEXT(name, x, y);
+extern RB_INSERT(name, x, y);
+#endif
diff --git a/fsutil.h b/fsutil.h
index 7acfdd6..a4b3979 100644
--- a/fsutil.h
+++ b/fsutil.h
@@ -1,7 +1,7 @@
#ifndef _FS_UTIL_H
#define _FS_UTIL_H
-#define pwarn printf
-#define pfatal printf
+#define pwarn FSCK_SLOGW
+#define pfatal FSCK_SLOGE
#endif
diff --git a/main.c b/main.c
index 4938227..1c6d514 100644
--- a/main.c
+++ b/main.c
@@ -48,13 +48,12 @@ static const char rcsid[] =
#include "fsutil.h"
#include "ext.h"
-
+#include "fatcache.h"
int alwaysno; /* assume "no" for all questions */
int alwaysyes; /* assume "yes" for all questions */
int preen; /* set when preening */
int rdonly; /* device is opened read only (supersedes above) */
int skipclean; /* skip clean file systems if preening */
-
static void usage(void);
static void
@@ -135,7 +134,7 @@ ask(int def, const char *fmt, ...)
char prompt[256];
int c;
-
+ fsck_info("%s ? \n",fmt);
if (preen) {
if (rdonly)
def = 0;
diff --git a/tree.h b/tree.h
new file mode 100644
index 0000000..58309d5
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,769 @@
+/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
+/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
+/* $FreeBSD$ */
+
+/*-
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_TREE_H_
+#define _SYS_TREE_H_
+
+#include <sys/cdefs.h>
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure. Every operation
+ * on the tree causes a splay to happen. The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree. On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n). The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute. It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ * same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type) \
+struct name { \
+ struct type *sph_root; /* root of the tree */ \
+}
+
+#define SPLAY_INITIALIZER(root) \
+ { NULL }
+
+#define SPLAY_INIT(root) do { \
+ (root)->sph_root = NULL; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ENTRY(type) \
+struct { \
+ struct type *spe_left; /* left element */ \
+ struct type *spe_right; /* right element */ \
+}
+
+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
+#define SPLAY_ROOT(head) (head)->sph_root
+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do { \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do { \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp) \
+void name##_SPLAY(struct name *, struct type *); \
+void name##_SPLAY_MINMAX(struct name *, int); \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
+ \
+/* Finds the node with the same key as elm */ \
+static __inline struct type * \
+name##_SPLAY_FIND(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) \
+ return NULL; \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) \
+ return head->sph_root; \
+ return NULL; \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_NEXT(struct name *head, struct type *elm) \
+{ \
+ name##_SPLAY(head, elm); \
+ if (SPLAY_RIGHT(elm, field) != NULL) { \
+ elm = SPLAY_RIGHT(elm, field); \
+ while (SPLAY_LEFT(elm, field) != NULL) { \
+ elm = SPLAY_LEFT(elm, field); \
+ } \
+ } else \
+ elm = NULL; \
+ return elm; \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_MIN_MAX(struct name *head, int val) \
+{ \
+ name##_SPLAY_MINMAX(head, val); \
+ return SPLAY_ROOT(head); \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return (head)->sph_root; \
+ } \
+ (head)->sph_root = (elm); \
+ return NULL; \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return NULL; \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return elm; \
+ } \
+ return NULL; \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+ int __comp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) > 0){ \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+} \
+ \
+/* Splay with either the minimum or the maximum element \
+ * Used to find minimum or maximum element in tree. \
+ */ \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while (1) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp > 0) { \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+}
+
+#define SPLAY_NEGINF -1
+#define SPLAY_INF 1
+
+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head) \
+ for ((x) = SPLAY_MIN(name, head); \
+ (x) != NULL; \
+ (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type) \
+struct name { \
+ struct type *rbh_root; /* root of the tree */ \
+}
+
+#define RB_INITIALIZER(root) \
+ { NULL }
+
+#define RB_INIT(root) do { \
+ (root)->rbh_root = NULL; \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_BLACK 0
+#define RB_RED 1
+#define RB_ENTRY(type) \
+struct { \
+ struct type *rbe_left; /* left element */ \
+ struct type *rbe_right; /* right element */ \
+ struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
+}
+
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ROOT(head) (head)->rbh_root
+#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do { \
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_SET_BLACKRED(black, red, field) do { \
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x) do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ RB_RIGHT(elm, field) = RB_LEFT(tmp, field); \
+ if (RB_RIGHT(elm, field) != NULL) { \
+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ RB_PARENT(tmp, field) = RB_PARENT(elm, field); \
+ if (RB_PARENT(tmp, field) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ RB_LEFT(elm, field) = RB_RIGHT(tmp, field); \
+ if (RB_LEFT(elm, field) != NULL) { \
+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ RB_PARENT(tmp, field) = RB_PARENT(elm, field); \
+ if (RB_PARENT(tmp, field) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+#define RB_PROTOTYPE(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
+attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
+attr struct type *name##_RB_INSERT(struct name *, struct type *); \
+attr struct type *name##_RB_FIND(struct name *, struct type *); \
+attr struct type *name##_RB_NFIND(struct name *, struct type *); \
+attr struct type *name##_RB_NEXT(struct type *); \
+attr struct type *name##_RB_PREV(struct type *); \
+attr struct type *name##_RB_MINMAX(struct name *, int); \
+ \
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define RB_GENERATE(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define RB_GENERATE_STATIC(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+attr void \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = RB_PARENT(elm, field)) != NULL && \
+ RB_COLOR(parent, field) == RB_RED) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RIGHT(parent, field) == elm) { \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_LEFT(parent, field) == elm) { \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+} \
+ \
+attr void \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
+ elm != RB_ROOT(head)) { \
+ if (RB_LEFT(parent, field) == elm) { \
+ tmp = RB_RIGHT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+ struct type *oleft; \
+ oleft = RB_LEFT(tmp, field); \
+ if (oleft != NULL) \
+ RB_COLOR(oleft, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_RIGHT(tmp, field)) \
+ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = RB_LEFT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+ struct type *oright; \
+ oright = RB_RIGHT(tmp, field); \
+ if (oright != NULL) \
+ RB_COLOR(oright, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_LEFT(head, tmp, oright, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_LEFT(tmp, field)) \
+ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ RB_COLOR(elm, field) = RB_BLACK; \
+} \
+ \
+attr struct type * \
+name##_RB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (RB_LEFT(elm, field) == NULL) \
+ child = RB_RIGHT(elm, field); \
+ else if (RB_RIGHT(elm, field) == NULL) \
+ child = RB_LEFT(elm, field); \
+ else { \
+ struct type *left; \
+ elm = RB_RIGHT(elm, field); \
+ while ((left = RB_LEFT(elm, field)) != NULL) \
+ elm = left; \
+ child = RB_RIGHT(elm, field); \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+ if (RB_PARENT(elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (RB_PARENT(old, field)) { \
+ if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+ RB_LEFT(RB_PARENT(old, field), field) = elm;\
+ else \
+ RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+ RB_AUGMENT(RB_PARENT(old, field)); \
+ } else \
+ RB_ROOT(head) = elm; \
+ RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ if (RB_RIGHT(old, field)) \
+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \
+ if (parent) { \
+ left = parent; \
+ do { \
+ RB_AUGMENT(left); \
+ } while ((left = RB_PARENT(left, field)) != NULL); \
+ } \
+ goto color; \
+ } \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+color: \
+ if (color == RB_BLACK) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
+ return old; \
+} \
+ \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_RB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = RB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return tmp; \
+ } \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ return NULL; \
+} \
+ \
+/* Finds the node with the same key as elm */ \
+attr struct type * \
+name##_RB_FIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return tmp; \
+ } \
+ return NULL; \
+} \
+ \
+/* Finds the first node greater than or equal to the search key */ \
+attr struct type * \
+name##_RB_NFIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = RB_LEFT(tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return tmp; \
+ } \
+ return res; \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_NEXT(struct type *elm) \
+{ \
+ if (RB_RIGHT(elm, field)) { \
+ elm = RB_RIGHT(elm, field); \
+ while (RB_LEFT(elm, field)) \
+ elm = RB_LEFT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return elm; \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_PREV(struct type *elm) \
+{ \
+ if (RB_LEFT(elm, field)) { \
+ elm = RB_LEFT(elm, field); \
+ while (RB_RIGHT(elm, field)) \
+ elm = RB_RIGHT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return elm; \
+} \
+ \
+attr struct type * \
+name##_RB_MINMAX(struct name *head, int val) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else \
+ tmp = RB_RIGHT(tmp, field); \
+ } \
+ return parent; \
+}
+
+#define RB_NEGINF -1
+#define RB_INF 1
+
+#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
+#define RB_PREV(name, x, y) name##_RB_PREV(y)
+#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head) \
+ for ((x) = RB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = RB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#endif /* _SYS_TREE_H_ */
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 00:24:14 +0000