Adventures in FAT32 with 65c02

[barnacle]

Most of the disc activity is reading, which as far as I know isn't a concern for flash lifetime. But the FAT gets a lot of reading _and_ writing, and the writing is concentrated in sectors. And there are two uint32 words in the FSI that get hammered at every write: the next cluster and the clusters remaining. At least I can write them both with a single write.

Two steps forward and two steps back today; nothing significant to report except some rewriting and further testing.

Neil

[jgharston]

barnacle wrote:

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.

Without standing up to grab my DOS 3.10 Technical Refernece Manual....
A FAT entry of zero "points to" the first FAT,
a FAT entry of 1 "points to" the second FAT,
which is why a FAT entry of 2 "points to" the root directory, and why the "number of FATs" entry is also the pointer to the root directory. That is why a blank disk has three entries in the FAT.
As you can never have zero FATs, then the lowest FAT entry is 1, resulting in a FAT entry of zero being used for "unused".

Edit: FAT also reserved the top 16 values for special cases:
(---)FF0-FF6: reserved
(---)FF7 : bad
(---)FF8-FFF: last occupied cluster

I was trying to remember how it indicated "end of chain", it's an entry of FF8+/FFF8+/FFFFFFF8+.
It also shows the largest possible FAT size is one with a maximum entry of FEF/FFEF/FFFFFFEF, so 1.5*FF0 or 2*FFF0 or 4*FFFFFFF0 bytes.

[jgharston]

BigDumbDinosaur wrote:

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.

Again, from memory:
the file system part of the API parses file paths and removes redundancies before following them through the file system, explicity starting from the current directory.
So,
.\this\that\somewhere is internally parsed as: start at csd, look for this\that\somewhere
\topdir\otherwhere is internally parsed as: start at root, look for topdir\otherwhere
dirname\.. is redundant, fred\jim\..\hazel is parsed as fred\hazel

[barnacle]

Yeah, no problem with a pointer of 0 pointing to the first FAT record, and pointer of 1 pointing to the second, and thence that everlasting off-by-two risk (which MS are at great pains to point out in their document). Curiously, their use appears to be to replicate a media type from the VIB (record 0) and a couple of bits to indicate poorly unmounted or potentially faulty hardware.

According MS, Note that a zero-length file—a file that has no data allocated to it—has a first cluster number of 0 placed in its directory entry. This seems odd; it means that no cluster is allocated to a file until it is written to, so you could have a file with a filename listable in a directory search and openable which requires an immediate cluster allocation as soon as any data is written. That has the risk on a full disc that you can create a file successfully but fail as soon as you try to use it. Unless I discover that it won't work, I'm allocating a cluster as soon as the file is created.

Neil

Edit - I suppose it makes the file creation process simpler, but it just kicks the can down the road. And requires a test for zeroes in the cluster pointer.

[jgharston]

barnacle wrote:

According MS, Note that a zero-length file—a file that has no data allocated to it—has a first cluster number of 0 placed in its directory entry. This seems odd; it means that no cluster is allocated to a file until it is written to, so you could have a file with a filename listable in a directory search and openable which requires an immediate cluster allocation as soon as any data is written. That has the risk on a full disc that you can create a file successfully but fail as soon as you try to use it. Unless I discover that it won't work, I'm allocating a cluster as soon as the file is created.

Edit - I suppose it makes the file creation process simpler, but it just kicks the can down the road. And requires a test for zeroes in the cluster pointer.

It does complicate things. As when you search the FAT to find some free space to save to data to, you scan for entries that are zero. What happens if you create multiple zero-length files?
If you create a file that is zero bytes long, it's cluster number in the directory entry will point to a start entry in the FAT, with that entry set to zero. If you create another file, you will again scan the FAT to find an unused cluster to set the file's start cluster to - and will find the same FAT entry! You end up with the files pointing to the same FAT entry.

The caught me when I was first writing my filing system, saving a zero-length file went through the normal process of finding some free space and pointing directory entry to the start of it. Creating another file went through the same process, found the same free space and pointed to it as well. This subsequently prevented the zero-length file from being extended as it then crashed into the second file. The work-around is as MS does: when creating a zero-length file also set the file start in the directory entry to zero, and defer searching for free space to when the file actually had data added to it by checking if the directory entry's start sector is zero.

[barnacle]

That was my conclusion too: the only way to avoid collision is to search the whole FAT when the space is actually required. Which might make sense if you're filling a floppy, or you're Peter Norton, but I'm not sure it makes sense now. Though there are values for FSI_Free_Count which indicate it should be calculated anew.

It does make the file creation easier: it's just an entry in the directory. But I think I'll allocate the cluster early, and see what dosfsck thinks about it. If it doesn't complain, I shan't worry; otherwise, I can I don't have any windows systems available to me.

Neil

[BigDumbDinosaur]

jgharston wrote:

If you create a file that is zero bytes long, it's cluster number in the directory entry will point to a start entry in the FAT, with that entry set to zero. If you create another file, you will again scan the FAT to find an unused cluster to set the file's start cluster to - and will find the same FAT entry! You end up with the files pointing to the same FAT entry.

Ah, yes...the infamous FAT crosslink problem.  Peter Norton had a big, s**t-eatin’ grin on his face when he figured out how to fix that. 

The UNIX S51K filesystem driver and its descendants (ext2, ext3, etc.) avoid that problem during file creation by first allocating a free inode before writing the directory.  Hence there is no chance of two unrelated directory entries pointing to the same inode...unless, the kernel’s link() function is called.

[barnacle]

It gets even worse if you consider multithreaded multiuser code... it all makes me want to go and lie down in a darkened room.

Neil

[BigDumbDinosaur]

barnacle wrote:

It gets even worse if you consider multithreaded multiuser code... it all makes me want to go and lie down in a darkened room.

I do that almost every night.    Trouble is, I often lie there thinking about stuff I’m working on, when I should be sleeping. 

More seriously, any process that results in filesystem manipulation, e.g., cataloging a new file or finding a cluster to allocate, needs to be atomic in nature.  In a multitasking scenario (which a multiuser system would have to support), it is common for task preemption to occur only at a point where the kernel is about to return control to user space.  That return-to-caller might be following a routine kernel call¹ or following the servicing of an interrupt.  In both cases, the preemption, if scheduled, would be the last step before the exit to user space.

Observing the basic rule that preemption must only occur right before a return to the caller will assist with maintaining atomicity.  In other words, once your kernel embarks on an operation that is going to manipulate the filesystem, it must be carried out to completion, even if preemption is scheduled and an IRQ occurs while the kernel is in control.  Since any IRQ would normally execute the preemption right before exit, one of the rules governing preemption would be that it cannot occur when it is the kernel that has been interrupted.  A flag somewhere in kernel address space that the IRQ back end can test right before it is about to execute the preemption steps would be set by the kernal call front end before running the code specific to the call.  The “no preemption” flag would be cleared as the final step before the kernel returns to the caller.

————————————————————
¹My preferred method of making kernal calls is via a software interrupt using the 65C816’s COP instruction.  This method of calling the kernel makes it possible to use a common return-from-interrupt backend (CRTI) for both kernel calls and IRQ servicing.  A similar thing can be arranged for the 65C02 by using BRK to make kernel calls.

[barnacle]

So today I inadvertently proved that my cf_write routine worked exactly as advertised.

Shame the data I wrote wasn't quite the data I should have writ[1]... which caused quite an atrocity to the file system. So I had to reformat the drive. No doubt there will be other formats required

Neil

[1] The Moving Finger writes; and, having writ,
Moves on: nor all thy Piety nor Wit
Shall lure it back to cancel half a Line,
Nor all thy Tears wash out a Word of it.

Formatting, on the other hand...

[barnacle]

f_create
Taking into account the comments above, f_create takes a string pointer in Y:A and, if there is no matching filename already existing in the current directory, creates a zero length file with no allocated cluster (i.e. cluster zero, as discussed earlier).

This file is happily visible both by f_create, if run a second time with the same filename, and by my linux box:

First run - the test code performs a directory listing before attempting to create the file:

Code: Select all

NeoDOS32 v0.0071                                                                
                                                                                
BIOS.ASM                                                                        
CF.ASM                                                                          
DOS.ASM                                                                         
FILE_SYS.ASM                                                                    
MAIN.ASM                                                                        
MAIN.HEX                                                                        
MAIN.LST                                                                        
U32MATHS.ASM                                                                    
VARS.ASM                                                                        
[TEST]                                                                          
lba = 00000FC1                                                                  
ptr = 02E0  

And on the second attempt:

Code: Select all

NeoDOS32 v0.0072     
           
BIOS.ASM         
CF.ASM                                                                          
DOS.ASM                                                                         
FILE_SYS.ASM                                                                    
MAIN.ASM                                                                        
MAIN.HEX                                                                        
MAIN.LST                                                                        
U32MATHS.ASM                                                                    
VARS.ASM                                                                        
[TEST]                                                                          
ANOTHER.TXT                                                                     
Failed

in which the listing shows the file is already present, and so the create fails.

The calling code:

Code: Select all

	LYA new_file
	jsr f_create			; returns zero set if create worked
	bne m1
	PRINT "File created"
	jsr crlf
	bra m2
m1:
	PRINT "Failed"
	jsr crlf
m2:

	lda #'+'
	jsr putchar

	bra *					; wait forever

and f_create, still with all sorts of debug code in.

Code: Select all

f_create:
	; step one: check the file doesn't already exist. 	
	jsr f_find_file
	beq f_crt_1
		jmp f_crt_ex
f_crt_1:	
	; if we get here, the file does not already exist so we can progress
	; lba points to the directory entry, fs_dir_ptr points into
	; transient which contains the sector
	
	PRINT "lba = "
	LYA lba
	jsr hexuint32
	jsr crlf
	
	PRINT "ptr = "
	lda fs_dir_ptr+1
	jsr hex2out
	lda fs_dir_ptr
	jsr hex2out
	jsr crlf

	; we need to populate the directory entry
	ldy #0
f_crt_2:
	lda str_83,y
	sta (fs_dir_ptr),y
	iny
	cpy # 11				; eleven characters as the file name
	bne f_crt_2
	; now the attribute byte
	; we want a default file (to create a dir, we will modify the attrib
	; byte later) with today's date and time for everything and a size 
	; of zero
	lda #attr_arc
	sta (fs_dir_ptr),y		; attributes
	iny
	lda #0
	sta (fs_dir_ptr),y		; nt reserved byte
	iny
	sta (fs_dir_ptr),y		; creation time hundredths, zero for now
	iny
	lda time				; it's fake, for now!
	sta (fs_dir_ptr),y		; creation time 
	iny
	lda time+1			
	sta (fs_dir_ptr),y		; creation time
	iny
	lda date				; so is this!
	sta (fs_dir_ptr),y		; creation date
	iny
	lda date+1
	sta (fs_dir_ptr),y		; creation date
	iny
	lda date
	sta (fs_dir_ptr),y		; last access date
	iny
	lda date+1
	sta (fs_dir_ptr),y		; last access date
	iny
	lda #0
	sta (fs_dir_ptr),y		; high cluster, low byte, zero
	iny
	sta (fs_dir_ptr),y		; high cluster, high byte, zero
	iny
	lda time
	sta (fs_dir_ptr),y		; last write time
	iny
	lda time+1
	sta (fs_dir_ptr),y		; last write time
	iny
	lda date
	sta (fs_dir_ptr),y		; last write date
	iny
	lda date+1
	sta (fs_dir_ptr),y		; last write date
	iny
	lda #0
	sta (fs_dir_ptr),y		; low cluster, low byte, zero
	iny
	sta (fs_dir_ptr),y		; low cluster, high byte, zero
	iny
	sta (fs_dir_ptr),y		; file size, should be zero
	iny
	sta (fs_dir_ptr),y
	iny
	sta (fs_dir_ptr),y
	iny
	sta (fs_dir_ptr),y		; four bytes
	
	SHOWTRANS
	
	;;;;;;;;;;;;;;;;;;;;
	jsr cf_set_lba
	LYA lba
	jsr hexuint32
	jsr crlf
	jsr cf_write			; write it to the disc
	;;;;;;;;;;;;;;;;;;;;

	jsr crlf

	PRINT "end of create"
	jsr crlf
	lda #0
f_crt_ex:
	rts

Neil

[barnacle]

An estimate of reading speed
I chose a file from Gutenberg approximately 336kB in length (The Extraordinary Adventures of Arsène Lupin, Gentleman-Burglar ), read the file from the CF, and output it to the serial port, where it is displayed in miniterm as UTF-8.

This takes thirty seconds.

For comparison, 'cat'ing the same file to a terminal on this laptop completes before I can get my finger off the return key, let alone time it.

At first glance, then, a read speed of 11200 bytes per second. But we have to consider the transmission time at 115200 baud, or 11520 bytes per second. 336k/115.2k ~= 3 seconds, so we can subtract that from the initial time; that's obviously not part of the read time, so now we're looking at 336k/27 seconds = 12400 bytes per second.

And I fear that's about as fast as it's going to go, for a few reasons: firstly, in this example, I'm dealing directly with the transient area into which all sectors are read before display. In the final version, every open file is going to require its own buffer, to allow operation without affecting other files. That's going to take some time to move the data (it might be faster, but won't be easier) to rewrite the CF handling routines to use a variably defined buffer. I need to think about that.

There's obviously a lot of games being played with the FAT. Even with this file, which is in pretty much linear order with sequential clusters, at the end of each cluster I have to go back to the FAT with fs_next_cluster (and through it, clus_to_1st_sector) with multiple sectors being read before I get to the cluster/sector I need - in case it's _not_ the next one.

Finally, there's a chunk of code that has to happen between each character being read and output: I need to increment a 32-bit file pointer _and_ check whether it equals the file size:

Code: Select all

		bne f_cat_11		; else increment the file pointer
			inc f_cat_ptr+1
			bne f_cat_11
				inc f_cat_ptr+2
				bne f_cat_11
					inc f_cat_ptr+3
f_cat_11:

and

Code: Select all

f_eof:
	lda f_cat_ptr			; lsb most likely to be different, so first
	cmp f_cat_size
	bne f_eof_x
	lda f_cat_ptr+1
	cmp f_cat_size+1
	bne f_eof_x
	lda f_cat_ptr+2
	cmp f_cat_size+2
	bne f_eof_x
	lda f_cat_ptr+3
	cmp f_cat_size+3
f_eof_x:
	rts

Even though both code fragments are intended to run as quickly as possible (starting with the low byte and ignoring the others if not required for the increment, and testing the low byte first as being the most likely not to match), I'm guesstimating that there's a couple of seconds minimum just in those two fragments.

Oh well, not as fast as I had hoped, but not as bad as it might be.

For file pointer operations, I'm thinking of a double slot. I want the per-file buffer to start on a page boundary for obvious reason, but I also need a small structure of perhaps 64 bytes (not sure yet) which can be allocated wherever. One entry in the cluster might be a pointer to the buffer... though I fear the 65c02 is not well suited to efficient pointers-to-pointers nor to 32 bit arithmetic.

But allocating this way might use the top couple of pages of RAM for the first buffer, part of the next page down for the file pointer info:

Code: Select all

$7E00   [buffer 1, $200 bytes]
$7DC0   [file pointer 1, $40 bytes]
$7D80   [file pointer 2, $40 bytes]
$7D40   [file pointer 3, $40 bytes]
$7B00   [buffer 2, $200 bytes]
$7900   [buffer 3, $200 bytes]

and so on. Possibly limiting things to a maximum of four, or maybe eight, files at a time. I really _don't_ want to get into malloc()...

Neil

Edit: I dropped a decimal place: the serial data rate is 11520 bytes per second, not 115200 - that's bits per second. So the transmission time is 336k/11.5k = 29 seconds... which is excellent news. The access is taking only a second or so.

[leepivonka]

Assuming your serial port is implemented as a UART with at least 1 char of buffering, all you can say is your read file routines are on average at least as fast as your serial port.
While the serial port is processing the last TX char, the CPU can compute up to 1 char time (maybe 1 start bit, 8 data bits, 1 stop bit) without slowing down the "cat" program.

A better speed test would be to read each char from the file like "cat", but just discard it instead of transmitting it. Send a message at end-of-file so you know when it's done.

[barnacle]

Yes, that's my next test. You're quite right, of course: it could simply be that there is effectively no waiting for the serial port to be ready because that time is being taken by the file access.

It's what I get for posting late at night after a day calibrating and certifying the new electric paraglider winch (i.e. helping the designer do it; but now it can be used for flight, which is nice). Nonetheless it is encouraging.

Neil

[barnacle]

And so, after that minor mathematical misdemeanour, I tried it with the call to putchar removed. It now takes ten seconds to complete (mechanically timed with an analogue stopwatch!) so I'm reading 33.6kB/second. Which feels like it could be fast enough for something like virtual memory for a file editor or similar, and certainly not an issue for file save/load for files that will fit into the 64k memory space.

Neil