fsck msdos

[tyama501]

I found old fsck FAT source code from BSD.
https://github.com/boundarydevices/fsck_msdos

Is there a chance to porting this?

[ghaerr]

Hello @tyama501,

Wow, nice find! It appears that fsck_msdos is a command that has origins in NetBSD and OpenBSD. This version appears to be very similar to one used in Android, and I found what looks like a more complex version here which was enhanced by the Linux Foundation.

Are you thinking we should port this to ELKS, or just run on Linux or macOS? Just to try it, I was able to compile it and run on macOS using the following changes:

diff --git a/fsutil.h b/fsutil.h
index 7acfdd6..9f2a92f 100644
--- a/fsutil.h
+++ b/fsutil.h
@@ -4,4 +4,7 @@
 #define pwarn printf
 #define pfatal printf
 
+typedef off_t   loff_t;
+#define lseek64 lseek
+
 #endif

Then compile it and test on an ELKS FAT image using:

$ cc -Dlint *.c -o fsck_msdos
$ ./fsck_msdos -pf hd32-fat.img
** hd32-fat.img
** Phase 1 - Read and Compare FATs
Attempting to allocate 62 KB for FAT
Attempting to allocate 62 KB for FAT
** Phase 2 - Check Cluster Chains
** Phase 3 - Checking Directories
** Phase 4 - Checking for Lost Files
326 files, 29541 free (29541 clusters)

I was also able to find a OpenBSD man page for it.

I would say it should be pretty straightforward to port to ELKS, but this needs to be looked at further as it does seem to do lots of mallocs for each directory entry found. I can't guess at this point where it might run out of memory. We might also want to look at what the more complex version does that this version doesn't, although that may use up even more memory on ELKS.

I would suggest playing with this on your PC by compiling it on your OS, then testing against various "bad" FAT disk images to see if it works well fixing them. If you like its operation, I can certainly help port it, or assist you in doing so for ELKS.

Thank you!

[ghaerr]

I got the more enhanced version of fsck_msdos to compile using the following diff. It appears to check or otherwise compare FAT fragments which the original version may not. I think this enhanced version may use a lot more memory than the first, which could be a problem for ELKS.

Nonetheless, it would be interesting to compare this version with the simpler version on the bad FAT images you have, to see the differences.

diff --git a/fatcache.h b/fatcache.h
index 2f01608..9050387 100755
--- a/fatcache.h
+++ b/fatcache.h
@@ -31,8 +31,8 @@
 #include "dosfs.h"
 #include "tree.h"
 #include "stddef.h"
-#include <cutils/log.h>
-#include <android/log.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)
@@ -41,6 +41,7 @@
 #define CLEAR_BIT(x,n)  do{ \
     x &= ~(1<<n);}while(0)
 
+#if 0
 /*
  *print information when handle cluster chain
  */
@@ -52,6 +53,12 @@
 #define fsck_warn       FSCK_SLOGW
 #define fsck_err        FSCK_SLOGE
 #define fsck_debug      FSCK_SLOGD
+#else
+#define fsck_info(...)  printf(__VA_ARGS__)
+#define fsck_warn(...)  printf(__VA_ARGS__)
+#define fsck_err(...)   printf(__VA_ARGS__)
+#define fsck_debug(...) printf(__VA_ARGS__)
+#endif
 
 #ifndef offsetof
 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
diff --git a/fragment.c b/fragment.c
index 19750b1..0b81568 100755
--- a/fragment.c
+++ b/fragment.c
@@ -26,7 +26,6 @@
 *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)
 {
diff --git a/fsutil.h b/fsutil.h
index 11eed1c..5ace108 100755
--- a/fsutil.h
+++ b/fsutil.h
@@ -4,4 +4,10 @@
 #define pwarn  printf
 #define pfatal printf
 
+#include <sys/types.h>
+#include <stdlib.h>
+#include <unistd.h>
+typedef off_t   loff_t;
+#define lseek64 lseek
+
 #endif

Running produces:

./fsck_msdos -pf hd32-fat.img 
** /hd32-fat.img
sectors Per cluster :2 
boot->ClusterOffset :277 
FAT16 Fielsystem
Using cluster_chain_descriptor
Total clusters 31613 
** Phase 1 - Read and Compare FATs
Attempting to allocate 62 KB for FAT
Attempting to allocate 62 KB for FAT
Begin to compare FAT
** Phase 2 - Check Cluster Chains 
Begin to handle the cluster chain
** Phase 3 - Checking Directories
rootDir->head :0
** Phase 4 - Checking for Lost Files
Verify Filesystem information
326 files, 29541 free (29541 clusters)
free_rb_tree 
free_fragment_tree
free_fragment_tree
free_fragment_tree: rb_tree is empty 

[tyama501]

Thank you! I will try it.

[toncho11]

In the extended version there is a:

#define FAT_COMPARE_MAX_KB 4096

Maybe we can set it to 300 KBs (to be compatible with a system with 640 KB of memory) on ELKS and hopefully the rest will work OK.
I think having it on ELKS is a good idea.

[ghaerr]

In the extended version there is a:
#define FAT_COMPARE_MAX_KB 4096

Good catch. I now see the entire FAT is mallocd and read into. This means that, without lots of __far modifications to source code, the max FAT size would be 64k minus heap+stack = ~52k. For a FAT16 volume, that would limit the max FAT volume size to (52k / 2 * 512 =) ~13MB. So, basically only good for floppies, if ported to run on ELKS. The tool could be useful as part of the ELKS tool set for running on the host however.

If ~300k of RAM were allocated into far memory, that would only increase the max FAT volume checkable to be 72MB, smaller than most all FAT32 volumes out there. It appears the 4096k current FAT size limit would allow for max FAT32 volume size of (4096k / 4 * 512) = 524MB. Still not very large, although the 4096k define could be easily increased on 32- or 64-bit hosts.

The following source comment was kind of funny:

/*
 * If the FAT > this size then skip comparing, lest we risk
 * OOMing the framework. in the future we need to just re-write
 * this whole thing and optimize for less memory
 */
#define FAT_COMPARE_MAX_KB 4096

Rewriting software... the story of our lives? Lol.

We'll see what @tyama501 reports as to whether it can repair his corrupted floppies... ?

[toncho11]

But 72 MBs will still be good. ELKS' HDD images are 30 MBs if I remember correctly. So it could be used for self-repair from ELKS?

[ghaerr]

The max MINIX v1 image is 65Mb, but there are lots of much larger FAT images out there.

Out of curiosity, how big are the non-floppy FAT HDD's or USB drives you have? Any under 13M? Many under 72M?

One of the best attributes of the FAT32 filesystem for ELKS is its ability to hold far more data than MINIX v1 can.

Looking further at the source, there are lots of additional calloc and malloc allocations, one for every directory entry as well, so the usable volume size is going to be much smaller than my initial estimate. The program would have to be painstakingly rewritten.

We might luck out and find it work for 1.44M floppy images on ELKS without a rewrite though.

If you'd like to rewrite it, I'll help, but almost every char * will have to be rewritten char __far *, and even then the user will find it won't work with their large USB thumb drive. It appears we have yet to find a chkdsk that works as-is for any FAT filesystem in real mode, like DOS. Perhaps rewriting the actual DOS chkdsk might be a better idea (IIRC it was written in ASM though)?

[tyama501]

Thank you for the discussions.

I tried first one (boundarydevices/fsck_msdos) on FreeBSD.
Unfortunately, it didn't worked saying bad signature for fd1232-pc98.img but it worked for fd1440-pc98.img!

Initial image,
df Used 1074

I created Bad clusters with vi. (creating file and removing it)
df Used 1077

Then I run the fsck_msck on FreeBSD. Fixing FAT difference and clusters.

Check it again in ELKS.
Here it is.
df Used 1074 again!

It would be nice if we could port this to ELKS (and supporting 1232.img)

Thank you!

[ghaerr]

Thank you for the quick testing! It sounds like the program could work unmodified on ELKS if limited to only 1440k floppies. I would think that could be a pretty straight-forward port. It would likely immediately die or crash on any volume larger than 2880k though.

It is nice that the simple version (boundarydevices/fsck_msdos) corrected the lost cluster chain from the vi bug.

The errors that it picks up from the differences between FAT 0 and FAT 1 will always appear - ELKS does not maintain the second FAT copy, for speed reasons (this should not be a big deal, but the error will always show and be corrected).

if we could port this to ELKS (and supporting 1232.img)

I suspect the problem with PC-98 1232k volumes are that the sector size is 1K rather than 512, unless there are also differences in the PC-98 BPB?

If the program were ported to ELKS for floppies only, you might be able to figure out the changes for 1232k support?

[tyama501]

The errors that it picks up from the differences between FAT 0 and FAT 1 will always appear - ELKS does not maintain the second FAT ?>copy, for speed reasons (this should not be a big deal, but the error will always show and be corrected).

Yes, I know.

Signature is not in 512Byte border. Well, may be we can bypass that.
I will try porting when I got more time!
Thank you!

[ghaerr]

Signature is not in 512Byte border. Well, may be we can bypass that.

Got it, its at byte 1022 and 1023. Here's the failing code, did you get this error message?:

int
readboot(dosfs, boot)
    int dosfs;
    struct bootblock *boot;
{
    u_char block[DOSBOOTBLOCKSIZE];
    u_char fsinfo[2 * DOSBOOTBLOCKSIZE];
    u_char backup[DOSBOOTBLOCKSIZE];
    int ret = FSOK;

    if (read(dosfs, block, sizeof block) < sizeof block) {
        perror("could not read boot block");
                exit(2);
    }

    if (block[510] != 0x55 || block[511] != 0xaa) {
        pfatal("Invalid signature in boot block: %02x%02x", block[511], block[510]);
                exit(2);
    }

I will try porting when I got more time!

If you think its worthwhile to have this running for 1440k floppies only on ELKS, I could take an initial pass at it, and you could modify for PC-98. I was initially thinking, replying to @toncho11 that it should work for HDDs as well, but I suppose it would be useful for just floppies, given our current vi bug.

[tyama501]

That's great! Thank you.
Yes, I think I saw that message.

[ghaerr]

Well, I ported fsck_msdos to 16-bit ELKS as fsck-dos. It took about an hour, the biggest issue was generating BSD-style uint_t types and dealing with overflow-to-zero operations on int (16-bit for ELKS) when shifting left 16 or 24 bits.

After that, the program was too large (at 24k, only seven larger) to fit on our 1440k floppy, so rebuilt it on a 2880k floppy. The program ran out of memory trying to check that floppy size. Thinking it might work on our 1.4M floppy, programs were removed to make space on the 1440k floppy and tested. No luck, it seems I much underestimated the amount of memory required. fsck-dos won't run on ELKS, even on our basic boot floppy, without conversion to using __far data model, which will be lots of work.

Here's the 1440k disk showing memory requirements being exceeded:

Conclusion: even though fsck_msdos seemed like a small program easily portable to a 16-bit OS, it was written assuming large amounts of free memory are available, in typical 32-bit programming style. Unfortunately too much memory is required for operation on ELKS 1440k floppy without a large porting effort, which even then won't work for typically seen FAT volume sizes.

[toncho11]

Can we skip some of the Phase checks? It looks like it fails at Phase 3. Would it be still useful without Phase 3?

[ghaerr]

One would have to dig into the program to understand how it works. I would not think that removing filesystem checks would be a good idea for a filesystem checker though - this could lead users into thinking that a volume was OK after being checked by our diminished fsck-dos, when in fact it was corrupted.

[ghaerr]

It seems a proper CHKDSK is pretty complicated... the MSDOS 2.0 CHKDSK source, written in ASM is three files: CHKDSK.ASM (900 lines), CHKPROC.ASM (1400 lines) and CHKMES.ASM (475 lines). I also found FreeDOS chkdsk which is huge: 7 main C source files and 10 additional directories of library routines, all included in the checker. I'm not sure how either of them work, but am imagining that both use much more than 64K data in order to function.

If we had large model support allowing for all __far pointers and automatic far memory allocation, things would be a lot easier, but that's another even larger problem and would likely require porting the Watcom C compiler to produce ELKS executables, along with a specially-created large model version of our C library - a lot of work.

Another idea would be to create and/or run a 386-based kernel on our ancient systems (386+ only, of course). This would allow for full 32-bit protected mode, even on very old systems (but still newer than 8086 and 80286). I have been investigating such a thing if anyone is interested.

[tyama501]

Thank you!
I will think about the far pointer,
but just from curiosity,
are we have chance to use "unreal mode" for 386?
(although I don't have working 386/486 real machine now)

[tyama501]

https://github.com/ghaerr/elks/blob/master/elks/arch/i86/lib/unreal.S

Even if we could enter to the unreal mode by this code, we don't have way to make 32 bits elks application with gcc-ia16, right?

[ghaerr]

are we have chance to use "unreal mode" for 386?

The ELKS kernel already uses 386+ unreal mode when configured for XMS. However, this won't work for applications programs, and the kernel knows nothing about loading or managing 32-bit executables.

we don't have way to make 32 bits elks application with gcc-ia16, right?

gcc-ia16 may be able to produce 32-bit ELF output, but in general there are all kinds of problems going this route, as the unreal mode segment registers are only setup once for XMS, not each time slice for when a 32-bit application runs. (In a typical 32-bit kernel, the CPU CR3 register is reset to point to an entirely new GDT each time a process context switch occurs. The GDT contains the memory mapping specific for that process).

I will think about the far pointer

I am reading the source, it would be a good idea to study a bit. It seems that all struct fatEntry and struct dosDirEntry will likely have to be allocated in far mem. This will be a little bit expensive, due to the overhead of fmemalloc allocations. I think there's a 16-byte overhead for each, which will be very wasteful. It is possible it can't be made to work without huge memory use, as it looks like each FAT entry allocates a struct fatEntry (32 bytes+16 overhead = 48 bytes) and every directory entry (the whole tree) allocates a struct dosDirEntry (28+14+256+16 = 314 bytes). The 256 byte entry is for the DOS long filename, which I see now answers why so much memory is used. That could possibly be shortened, given that ELKS only handles 26 character long filenames max.

[EDIT: I just shorted the max DOS filename to 26 in the dosDirEntry struct and now it's not running out of memory... but having some other issues. Will report more likely in subsequent PR.]

[ghaerr]

Good news @tyama501, I was able to get fsck-dos to run on 1440k floppies without running out of RAM, and seemingly working properly. PR #1820 adds the changes to the distribution for testing.

[tyama501]

Wow, great! Thank you!

[tyama501]

Hello @ghaerr ,

I used the same corrupted image by vi for testing.
fsck-dos -pf /dev/fd1
It seems that 6 Cluster(s) lost are FIXED,
but some memory error occurred after that.

No increase to the Free space,
so I assume writing back failed.

Thank you.

[ghaerr]

Aw, shoot. Let me take another pass and see whether I can get it to work with less memory somehow. Can you post your 1440k image, or is it easy to create by just running vi and exiting?

[tyama501]

Here you are.
fd1440-pc98_vi_fsck.zip

[ghaerr]

May be I can try allocating far memory here,

Yes - but all instances of buffer being passed to other functions etc have to be chased down; it is a bit complicated. I suggest using wrappers as described above for this path. We will see, perhaps it will be required to use far memory to get this to work, I had hoped I had solved it for small floppies!

[tyama501]

Now Used 1077 blocks.
It should be 1074 after fixed.

[ghaerr]

Ok @tyama501, I have hopefully fixed the out-of-memory error in #1822.

[tyama501]

Hello @ghaerr ,

I could reproduce another broken FAT using "mv".
fd1440-pc98_mv.zip

Well, I just moved multiple files as before...

Before mv the Used 1186.
Then I move all the files from root/ to /lib/fonts.
Now used is 1297 after all files are moved.

I tried fsck-dos from another elks.
fsck-dos -pf /dev/fd1
A lot of FIXED.

Then booted with the image again.
Great!
I don't know why the mv broke it, but
now it is Used 1187. (almost back)

Thank you!

[ghaerr]

Thank you for testing. I would say it confirms a definite bug with mv on FAT volumes that is not present with using cp and rm. I will look at the mv source to try to understand further.

I was wondering what is the difference of "-p" and "-y" for all yes,
but according to OpenBSD man it seems that "-p" is for fixing while booting without question and quit for serious errors?

Yes - it seems that -p (or -fp) is useful for a quick minor check of a filesystem, with automatic fixing of small errors, but stopping on larger errors (not sure exactly what constitutes small errors, but adding lost chains back to freelist is included in small errors). This would be useful in a boot shell script, perhaps /etc/mount.cfg, where minor errors would be quickly corrected without deleting data from serious errors.

The other option -f alone will check all errors including major not handled by -p, and ask whether to fix them. If -fy is specified, then the fixes will be automatic.

Thus, it would seem that most (automatic) fixes would be performed either using -fp or -fy options to force minor or major check.

[tyama501]

Thank you!

https://github.com/ghaerr/elks/blob/master/elkscmd/file_utils/mv.c
remove should be done with this code?

	if (unlink(srcname) < 0)
		perror(srcname);

[ghaerr]

remove should be done with this code?

Yes. I'm looking at the code now, which does remove the "foo" when mv foo .. is used after the copy to ../foo, for instance. I suppose it is possible that it is the unlink system call on FAT that is removing a directory entry but not releasing the FAT chains? I will look into that.

[ghaerr]

@tyama501, I finally chased this down and fixed it in #1824. Perhaps after this it may be hard to create lost cluster chains in the future on FAT! :)

[tyama501]

Wow! Great, thank you!

And we were lucky that we could create lost clusters and test new fat-dos before the fix:)

[tyama501]

It seems that the boot sector off FAT12/16/32 need to have boot signature of 0xAA55 at offset 510, even the sector size is over 512 Bytes.
http://elm-chan.org/docs/fat.html#bpb

So, I think I need to add it in the boot sector of PC-98, but the boot code is already full and no space for the 2 bytes...
I need to shrink it somehow...

[tyama501]

Hello @ghaerr ,

I could read elks disk fd1232 from DOS 6.2 by just changing the single Byte in FAT[0] from 0xF0 to 0xFE.

[ghaerr]

I could read elks disk fd1232 from DOS 6.2 by just changing the single Byte in FAT[0] from 0xF0 to 0xFE.

Very interesting and good news! Let me try to find some documentation the required/allowed values and meanings for the FAT[0] byte. I'm pretty sure all the FAT disks ELKS produces are created using the external mtools-4.0.24 package. We may require a custom version of it in order to change this byte for PC-98 1232 disks.

Do you have any documentation that shows the requirement for 0xFE as the FAT[0] media byte?

[ghaerr]

Also can you lookup the value of the BPB media byte at offset 21 (decimal) of the boot sector? I am interested to know if this is also 0xFE, or something else.

[ghaerr]

@tyama501:

It looks like we may be able to set the media byte (in both the FAT[0] position, apparently called FAT ID as well as in the BPB, called media descriptor byte) to 0xFE by the mformat command used by ELKS when creating the PC-98 1232k floppy. In order to do this, edit the file images/Make.defs and try changing from:

ifdef CONFIG_IMG_FD1232
FAT_MKFSOPTS = -s 8 -h 2 -t 77 -M 1024 -d 2 -L 2 -r 6 -k -N 0 -c 1

to (adding -m 0xfe to the end):

ifdef CONFIG_IMG_FD1232
FAT_MKFSOPTS = -s 8 -h 2 -t 77 -M 1024 -d 2 -L 2 -r 6 -k -N 0 -c 1 -m 0xfe

I don't think ELKS looks at the media descriptor byte nor FAT ID, so this should be OK. If this works, please include this in your PR, along with what you learn about the need for checking for the boot signature at offset 510.

Thank you!

[tyama501]

Thank you!
#1851 (comment)