Adventures in FAT32 with 65c02

[barnacle]

Some untested code to handle the first section of the above process.

f_inc_next_cluster increments the next free cluster link _on disc_ in FSInfo. According to MS, this is in the second reserved sector in the reserved area at the beginning of the partition.

While I'm writing this, I don't want to write to the disc in case either (a) the disc write doesn't work properly or (b) my update code doesn't work properly, and in either case I end up trashing the disc. I suspect I'm going to be formatting and rewriting a lot of CF cards today...

Code: Select all

;-----------------------------------------------------------------------
; f_inc_next_cluster
;
; Increment the next free cluster link in FSInfo.
; Loads the FSInfo sector, reads the free cluster link, increments it,
; saves it to next_free_cluster, and writes the sector back to disc
; NOTE: does not yet check that the new cluster does not exceed the 
;		cluster count
; NOTE: saves and restores LBA

f_inc_next_cluster:
	PUSHLBA					; save current directory
	LYA partition_begin_lba
	jsr u32_tolba
	LYA one
	jsr u32_add				; point to the FSInfo
							; could check for valid signature here, but
							; we'll trust it...
	jsr cf_set_lba
	jsr cf_read				; FSInfo is now in transient
	; the cluster is at offset $01ec in transient
	LYA transient+$1ec
	jsr u32_tolba
	; FIXME check cluster limit/disc size
	LYA one
	jsr u32_add				; increment it
	LYA next_free_cluster
	jsr u32_fromlba			; save it
	LYA transient+$1ec
	jsr u32_fromlba
	LYA partition_begin_lba
	jsr u32_tolba
	LYA one
	jsr u32_add				; point to the FSInfo again
	;;;;;;;;;;;;;;;;;;;;
	;jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;
	LYA next_free_cluster
	jsr hexuint32
	jsr crlf
	POPLBA					; restore lba
	rts

And the steps I have (hopefully) completed in f_create

Code: Select all

;-----------------------------------------------------------------------
; f_create
;
; If the file does not exist in the current directory, create it as a 
; zero length file. 
; The file name is a zero terminated string point to by Y:A
; The current directory sector is in lba on entry

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; FIXME disc writes disabled
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

f_create:
	; step one: check the file doesn't exist
	pha						; FIXME debug
	phy
	jsr puts				; show the string
	ply
	pla
	jsr crlf

	jsr str_to_83			; get the 8.3 version	
	jsr fs_find_first		; seek it
f_cr_01:
		lda (fs_dir_ptr)		; check the first character of name
		beq f_cr_03				; quit if it's zero
		jsr fs_match_83
		bne f_cr_02				
			; the filename exists: quit with zero flag set
			rts						; FIXME one entry point one exit...		
f_cr_02:
		jsr fs_find_next		; not found yet
		bra f_cr_01				; until no more records

f_cr_03:
	; if we get here, the file does not exist so we can progress
	; step two: increment the pointer in FSInfo sector
	jsr f_inc_next_cluster	; also sets next_free_cluster
	SHOWTRANS
	
	; step three: get the appropriate FAT sector into transient
	jsr clus_to_fat_rec		; preloads lba and fat_record
	jsr cf_set_lba
	jsr cf_read				
	SHOWTRANS
	
	; step four: allocate the new cluster with end-of-cluster marker
	ldy #0
	lda #$ff
	sta (fat_record),y		; (fat_record) is record in transient
	iny
	sta (fat_record),y
	iny
	sta (fat_record),y
	iny
	lda #$0f
	sta (fat_record),y		; that's $0FFFFFFF written
	SHOWTRANS
	
	; step five: save transient to the first FAT (sector still in lba)
	;;;;;;;;;;;;;;;;;;;;
	;jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;
	
	; step six: save transient to second FAT to keep synchronised
	LYA sectors_per_fat
	jsr u32_add				; by adding sectors per fat
	jsr cf_set_lba
	;;;;;;;;;;;;;;;;;;;;
	;jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;
	
	; step seven: find a place for the new directory entry
	

	jsr crlf
	lda #1

	rts

f_create should return a non-zero result if it completes successfully, but I haven't thought through a comprehensive error message system yet.

Neil

[barnacle]

We get a little further. A minor debugging of f_create

Code: Select all

f_create:
	; step one: check the file doesn't exist
	jsr str_to_83			; get the 8.3 version of the string
	jsr fs_find_first		; seek it
f_cr_01:
		lda (fs_dir_ptr)		; check the first character of name
		beq f_cr_03				; quit if it's zero
		jsr fs_match_83
		bne f_cr_02				
			; the filename exists: quit with zero flag set
			rts						; FIXME one entry point one exit...		
f_cr_02:
		jsr fs_find_next		; not found yet
		bra f_cr_01				; until no more records

f_cr_03:
	; if we get here, the file does not exist so we can progress
	; step two: increment the pointer in FSInfo sector
	
	jsr f_inc_next_cluster	; also sets next_free_cluster
		
	; step three: get the appropriate FAT sector into transient
	LYA next_free_cluster
	jsr u32_tolba
	; but there is a problem: the offset of two between records and
	; cluster numbers. We need to subtract two from next_free_cluster
	; before we calculate the lba and fat
	LYA two
	jsr u32_sub
	jsr clus_to_fat_rec		; preloads lba and fat_record
	jsr cf_set_lba
	jsr cf_read				
		
	; step four: allocate the new cluster with end-of-cluster marker
	ldy #0
	lda #$ff
	sta (fat_record),y		; (fat_record) is record in transient
	iny
	sta (fat_record),y
	iny
	sta (fat_record),y
	iny
	lda #$0f
	sta (fat_record),y		; that's $0FFFFFFF written
		
	; step five: save transient to the first FAT (sector still in lba)
	;;;;;;;;;;;;;;;;;;;;
	;jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;
	
	; step six: save transient to second FAT to keep synchronised
	LYA sectors_per_fat
	jsr u32_add				; by adding sectors per fat
	jsr cf_set_lba
	;;;;;;;;;;;;;;;;;;;;
	;jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;
	
	; step seven: find a place for the new directory entry

resolves an off-by-two error caused by the difference between record numbers and the cluster to which they relate, and MS's callous indifference in giving them both the name 'cluster'

I still haven't enabled writing to the drive; if I did, at the present state of the art, we'd have a disc with an unrecoverable wasted cluster every time I ran the code.

Next step is to create a standalone routine to search for a given file; that will be handy for no end of other functions. When we get to f_cr_03 we have the correct directory cluster in transient and a pointer to the first empty directory entry in fs_dir_ptr but transient has to be restored with the correct sector before we can add the new entry.

Neil

[BigDumbDinosaur]

barnacle wrote:

MS point out that modern solid state systems are so reliable that the second FAT is rarely if ever used (indeed, there's an option not to have one, though all their systems do).

I’d say Microsoft is a bit overly optimistic.

Solid state storage devices wear out, despite wear-leveling algorithms, and fail just as spectacularly as do mechanical disks, but with even poorer prospects of recovery.  Of course, it isn’t likely that you will encounter that sort of thing in a hobby system, but it happens more than one might expect.  I have had several servers come through my shop whose solid-state disks went south.  What was a bit disconcerting for me was the failures had occurred in a shorter period of operating time than usually seen with server-grade mechanical disks.

As for the value of having the backup FAT, if you never intend to develop a repair tool a la Microsoft’s chkdsk you could probably eliminate the backup FAT and save yourself some code and reduce filesystem manipulation processing time.

Quote:

I'm certainly not going to do a file system check (chkdisc) every time I power up...

I wasn’t implying that you should.  However, a repair tool should be considered an essential if there is any possibility that a loss of consistency could lead to loss of data.  As an aside, writing a repair tool would be an interesting and instructive programming exercise.

Quote:

To be honest - it's a bloody fragile system with too many pointers to pointers going on... And I think anything that uses FAT2 isn't going to be running on the 65c02 - more likely a temporary mount on the linux box.

The entire FAT family of filesystems is “bloody fragile”—as I’ve previously noted, Peter Norton made bank on that fragility.  The backup FAT was something added by Microsoft when it became too hard for them to ignore the ease at which the filesystem could be corrupted.

As to using FAT32 on a 65C02 or 65C816 system, it’s a complicated undertaking to support it on an eight-bit system.  Based on the code you have presented so far, it wouldn’t be a whole lot easier on the 65C816, although somewhat smaller code would be possible.  Despite the complexity, it seems I read a more than a few posts, here and elsewhere, in which the writer describes his or her 65xx system and how he/she intends to support FATxx.  No doubt there is a bit of naivety involved in saying so. 

I will say I commend your efforts to dissect and explain the “how” in reading/writing FAT32 with a 65C02.  FATxx represents, in my mind, the apotheosis of Rube Goldberg design.  I’ve not done the deep dive you have done, but have gagged a bit at what I’ve seen.    If for some reason I ever decide I want to support FATxx on one of my POC contraptions, I will probably purloin some of your code. 

[barnacle]

It may be that a repair function will be required, we'll see. Though by maintaining two FATs I can use a repair program on my Linux box, which defers that to a later date...

What I don't know is how the wear leveling in the CF works. The two parts that get written most often are the FAT sectors and any directories, every time a file is written. The CF doesn't know the first thing about the file system written on it (it amuses me that there's a processor on the CF card which is at least an order of magnitude more powerful than the 65c02). It's so long since I used FAT and DOS that I don't recall how a cross-linked file happened... I hope that my carefully timed and staged writes to the FAT and then the directory limit the chances to provide two FAT entries referring to the same cluster; I think the chances are that it would link just to an empty cluster with no directory record.

My method of duplicating one FAT sector into the other is simple and seems obvious to me: just add the number of sectors in a FAT to the existing sector pointer in lba and write the same sector we just wrote. It does keep the time when different FATs exist to a minimum.

Your point about the 65c816 is noted - though I only know of it from reading here; I've never played with one. It's clear from looking at the FAT system that it was intended to be easily handled with a processor with 16 bit pointers and 16 bit arithmetic: 8080/5 and Z80. Something with a big stack helps, too: 8086. Doubling the size of those pointers for FAT32 wouldn't unduly slow down the earlier processors, and would be a doddle on a 386 or later. Though I think the limiting factor is going to be the available memory on a 65c02 system. I think that opening multiple files is going to require each to have its own copy of transient which will only have its own window into the file opened; transient is just that; things pass through and disappear.

BDD wrote:

I will say I commend your efforts to dissect and explain the “how” in reading/writing FAT32 with a 65C02. FATxx represents, in my mind, the apotheosis of Rube Goldberg design. I’ve not done the deep dive you have done, but have gagged a bit at what I’ve seen. If for some reason I ever decide I want to support FATxx on one of my POC contraptions, I will probably purloin some of your code.

It's kind of you to say so. It's free and clear for anyone, as I state in the first post, so fill your boots

What I should point out, though, is that this is going to be a very partial implementation of a DOS with FAT32. It might be noted more for what I leave out than what I put in... but I am getting closer to my original requirement to be able to read and write interchangeably with another computer.

Neil

[jgharston]

BigDumbDinosaur wrote:

The entire FAT family of filesystems is “bloody fragile”—as I’ve previously noted, Peter Norton made bank on that fragility.  The backup FAT was something added by Microsoft when it became too hard for them to ignore the ease at which the filesystem could be corrupted.

When I first encountered the concept of "a" file allocation table, I was puzzled, then amazed, then horrified. A *SINGLE* table that identifies where *EVERY* filesystem object is located? Every system I'd used before then - and systems I've written since then - the infomation about where a filesystem object's contents are located is located with the filesystem object identifier itself, as part of the directory entry. If you kill that data, you just kill that object, not every single object on the entire disk.

[jgharston]

BigDumbDinosaur wrote:

As to using FAT32 on a 65C02 or 65C816 system, it’s a complicated undertaking to support it on an eight-bit system.  Based on the code you have presented so far, it wouldn’t be a whole lot easier on the 65C816, although somewhat smaller code would be possible.

Dmitry Petrov wrote a basic 6502 DOS filing system for the BBC series in about 6K, about 1K or so of that is the filesystem interface with the API layer, so it's do-able. Robert Sprowson wrote a more comprehensive DOSFS, including Win95 long filename support, in about 12K. see link

[jgharston]

barnacle wrote:

The two parts that get written most often are the FAT sectors and any directories, every time a file is written. The CF doesn't know the first thing about the file system written on it. It's so long since I used FAT and DOS that I don't recall how a cross-linked file happened... I hope that my carefully timed and staged writes to the FAT and then the directory limit the chances to provide two FAT entries referring to the same cluster; I think the chances are that it would link just to an empty cluster with no directory record.

When I wrote a filing system I put a lot of thought into working out the best order of writing the data, writing the updated directory, writing the updated free space map, to optimise the minimisation of a broken filesystem if the sequence was broken. I can't remember what order I did it off the top of my head without checking my code. I'm fairly certain I ordered things so that if it fell over there would just be an inaccessible "hole" in the data space of the disk with no impact on existing or future data.

[barnacle]

This is why I'm not planning on introducing fragmented file: there will be no going back and filling in the gaps of deleted files: that way lies madness. Apart from anything else, the FAT spec talks about the next free cluster word in the FSInfo sector (they call it FSI_Nxt_Free). They state that is a 'hint' for the FAT driver and that 'typically' it contains the cluster number of the last cluster the FAT driver allocated.

Well, yes.

I suppose, strictly, that one should start at FSI_Nxt_Free (FNF for short)and seek forwards in the FAT for the first available space. The code above reads FNF, adds one to get the next free cluster, subtracts two because of those ridiculous unused records, and writes the new number in the right place. That works because we don't have anything in the system after FNF.

What it should do is start at FNF and scan forwards for a cluster marked unused; if it doesn't find one then it starts at the beginning for anything deleted before the current cluster. If there's nothing, the disc is full. But if the disc is full, it has to go to the root directory and recursively look for the first deleted file. Again, if there's nothing, the disc is full. But if it does find a deleted file, it can find the first cluster of the deleted file, mark it unused, and follow it to the end of the chain, marking unused as it goes. Tedious, slow, requires multiple disc reads and writes, and has to be done at every write!

Since my intent is to allow simple compatible file transfer between the 65c02 and a linux box, at least in the short term I can use the linux file tools to tidy things up, if required. (I need a name for this OS: how does NeoDOS32 sound?)

Neil

[BigDumbDinosaur]

jgharston wrote:

When I first encountered the concept of "a" file allocation table, I was puzzled, then amazed, then horrified.  A *SINGLE* table that identifies where *EVERY* filesystem object is located?

That is what makes FAT so fragile.  Even with a backup FAT, there is still an unwise, in my opinion, concentration of information in a single structure.

Quote:

Every system I'd used before then - and systems I've written since then - the infomation about where a filesystem object's contents are located is located with the filesystem object identifier itself, as part of the directory entry.  If you kill that data, you just kill that object, not every single object on the entire disk.

You’re describing the basic philosophy of the UNIX S51K filesystem and its descendants.  The “object identifier” is the inode assigned to each directory and file.  If an inode gets wiped out, one file is lost, not a bunch of them.  Typically, multiple inodes are found in a disk block, the number depending on the inode and block sizes.  Should that block become unreadable, some files may be lost, but the overwhelming majority of them will remain accessible.

The Achilles’ Heel of the S51K filesystem (and descendants) is the superblock.  Without it, filesystem geometry information needed to locate all other structures, e.g., the inode array, would vanish.  Modern implementations include one or more superblock copies at strategic locations in the filesystem in case bare-metal recovery becomes necessary.  On at least one occasion, I have saved an ext3 filesystem by copying one of the backup superblocks into the primary one.

[barnacle]

Today's efforts ended with what appear to be correctly composed FAT and root directory entries for a newly created zero length test file, but sadly nothing appears to have been written. Which probably means that I forgot to set a write address from lba somewhere... oh well, tomorrow.

Neil

[BigDumbDinosaur]

barnacle wrote:

Today's efforts ended with what appear to be correctly composed FAT and root directory entries for a newly created zero length test file, but sadly nothing appears to have been written. Which probably means that I forgot to set a write address from lba somewhere... oh well, tomorrow.

Queue up Natasha Bedingfield. 

[barnacle]

Sadly, "the uploader has not chosen to make this available in your country"

Neil

[barnacle]

More on cluster allocation
I may have to rethink the allocation of new clusters. It depends how fast the CF fills, but it looks like the only 'guaranteed' way to use all available space on the disc requires that, each time a new cluster is required - that is, potentially at every write to CF - is a bit complicated. I assume that MS has done this since FAT12 days, which explains a lot of things...

This is FAT32 deep dive stuff so feel free to skip over

• The FAT _only_ knows which clusters are in use, and which clusters are part of the same cluster chain. It has no idea what the clusters are actually used for.
• The directory entry _only_ knows where the first cluster of the associated file is. It knows that there _are_ other clusters, if the file size is greater than one cluster.
• Clusters are allocated beginning at the start of the disc's data area (pointed to by the VIB contents).
• The only cluster with a defined function is the first: it holds the root directory.
• Apart from the first, directories are just like any other file and can live in any available cluster.

So we have a number of possibilities.

Initially, when the system is formatted, the will be a single allocated but empty cluster: cluster zero, the root directory. That directory will be empty, with the first attribute block set to indicate that there are no more entries. So far, so good.

There will be three records in the FAT: the first two, which are reserved special cases (why didn't they put them in the reserved sectors? I don't know what they do...) and then record #2, which points to cluster #0, our root directory.

Hidden away on a reserved sector is a uint32 called FSI_Nxt_Free. According to MS, this contains a 'hint' to the driver about where to start looking for another cluster to allocate (unless it doesn't, or the moon is in the wrong phase, or it's been set to an odd value). This is because 'a FAT32 FAT is large, it can be rather time consuming if there are a lot of allocated clusters at the start of the FAT and the driver starts looking for a free cluster starting at cluster 2 (another example of MS being confusing with the difference between a cluster number and a cluster record: they mean here the root directory cluster). What I have found so far, on a half full 512MB CF, is that FSI_Nxt_Free holds the value of the last cluster allocated. My simple driver maintains that process when creating a file, which always has a new cluster allocated.

Requesting a new cluster can be a simple process (well, simple apart from the number of 32-bit variables and pointers you have to keep track of):

• Get hold of FSI_Nxt_Free
• Add one
• Check that we haven't gone past the end of the FAT: if we have, we're 'full'
• Get the newly discovered FAT record
• Check that it's zero - if it's not, we're 'full'.
• Otherwise, save this new value to FSI_Nxt_Free and return it for use

If we follow that procedure, then we will end up with a CF full of files stored in sequential clusters, until we can't allocate any more space (my word, this laptop contains approximately seventeen thousand times the storage capacity of my first hard drive, and cost two thirds the price - not accounting for forty year's inflation. But I digress.)

But what if we delete a file?
One of the files on my test system is around a hundred MB in size - it's occupying around twenty-five thousand clusters, a quarter of the drive. If it's deleted, all that happens is that its name in the directory is modified to start with an $E5 byte. The file remains in place, the clusters it's occupying remain marked as in use in the FAT. We can recover it by changing that $E5 byte back to something useful. Another Peter Norton trick, as I recall.

If our drive is otherwise full, then we need to recover that space. We wait until it's full to preserve the deleted file as long as we can, but when we need it, we need it.

This is where it starts to get messy (and Peter Norton gets richer).

First, we have to follow the trail and release all the FAT records, starting with the first and using the internal links as normal, but replacing each record with a zero as we pass it, to indicate that the cluster is now available again. Note that we don't do anything with the directory itself; we can ignore the tiny amount of space that occupies (most directories are unlikely to use more than a handful of clusters, particularly in our case where we're not including long file names).

Then, with a FAT now including some space, we can start at looking for zero records. I don't think we start at FSI_Nxt_Free because we already know that fails; probably best to start at the beginning until we find one. When we do, we can both allocate it with the $0FFFFFFF marker and set that new cluster number in FSI_Nxt_Free.

The next time we need a new cluster, we're starting in a place where there are probably sequential empty sectors, quick to find, or at least any new cluster will be after that point. If there is one.

And don't forget that we need to synchronise the second FAT while we're at it...

Strategy
So here's possible strategy for cluster allocation:

1. Use the simple 'next cluster after FSI_Nxt_Free' approach. Set FSI_Nxt_Free to the new cluster. If it works, we're done.
2. If that fails, search from FSI_Nxt_Free to find a free cluster. Set FSI_Nxt_Free to the new cluster. If that works, we're done.
3. If that fails, find the first erased file and unlink all the associate clusters, allocate the first of these, and set FSI_Nxt_Free to that value.
4. If that fails, the disc is definitely absolutely rammed: there are no remaining deleted files whose space can be recovered, and there are no unallocated clusters. Isn't life tough?

Testing this, if I get this far, is going to be interesting...

Neil

[BigDumbDinosaur]

barnacle wrote:

Sadly, "the uploader has not chosen to make this available in your country"

Well, that’s downright mean of her!

The name of the song in that video is “Unwritten.” 

[BigDumbDinosaur]

barnacle wrote:

• The FAT _only_ knows which clusters are in use, and which clusters are part of the same cluster chain. It has no idea what the clusters are actually used for.

That’s common in most filesystems.  In the case of FAT, the filesystem driver can deduce that sort of information from the directory entry, if knowing such a thing is necessary.

Quote:

• The directory entry _only_ knows where the first cluster of the associated file is. It knows that there _are_ other clusters, if the file size is greater than one cluster.

Therein lies a fundamental weakness of FAT.  A lot of disk activity is required to follow the cluster chain to, for example, position to the end of a file if data is to be appended.  This behavior is a concern with flash media and its wear-out characteristic.

Quote:

Initially, when the system is formatted, the will be a single allocated but empty cluster: cluster zero, the root directory. That directory will be empty, with the first attribute block set to indicate that there are no more entries. So far, so good.

Interestingly, the root directory doesn’t contain the . and .. entries that are seen in subdirectories.  Nevertheless, a reference such as .\<filename> or ..\<filename> is valid even when the root directory is the working directory, suggesting that the DOS or Windows kernel is making assumptions about the meaning of .\ and ..\ in pathnames.

Quote:

There will be three records in the FAT: the first two, which are reserved special cases (why didn't they put them in the reserved sectors? I don't know what they do...) and then record #2, which points to cluster #0, our root directory.

This could merely be a case of someone long ago thought that reserving those clusters is a good idea™, but the next guy or gal who worked on the code forgot about them.

Quote:

But what if we delete a file?
If our drive is otherwise full, then we need to recover that space. We wait until it's full to preserve the deleted file as long as we can, but when we need it, we need it.

This is where it starts to get messy (and Peter Norton gets richer).

Just so you know...in case you don’t, Norton ended up selling his company to Symantec for $70 million.    Dunno about you, but I easily could have drifted aimlessly through life if I had that much in the bank...earning a million APY at today’s interest rates. 

Quote:

First, we have to follow the trail and release all the FAT records, starting with the first and using the internal links as normal, but replacing each record with a zero as we pass it, to indicate that the cluster is now available again...with a FAT now including some space, we can start at looking for zero records...next time we need a new cluster, we're starting in a place where there are probably sequential empty sectors, quick to find, or at least any new cluster will be after that point. If there is one.

And don't forget that we need to synchronise the second FAT while we're at it...

All that disk activity...