KnightOS Filesystem Specification 2.x

[SirCmpwn]

Attached is the KnightOS Filesytem Specification 2.0, or KFS.  Please review it and tell me if you have any suggestions, questions, or other ideas.  Version 2.1 is coming soon, with more information specific to it's implementation in KnightOS.
You may feel free to use this in your own 3rd party OS project (hell, you can use it in a first party project, if TI's watching )

Also, at the moment, this requires two swap sectors on the TI-83+ BE.  If anyone can think of a better way, please tell me about it.

[DJ Omnimaga]

I unfortunately am not familiar with assembly and that low level stuff, but it seems well explained from what I could gather.

[graphmastur]

Just an idea that I was talking to you about in IRC.  If say page 6 is a FAT table (starts with 0xF0), and page 5 has a file that starts with the byte 0xF0, then you get problems.  I suggest something like 0xF1 or something at least to show you that it is FST.  (Actually, I would do 0xF1 for the FAT and 0xF0 for FST)

[SirCmpwn]

That's a good point, I'll add a page identifier for FST pages as well.

[SirCmpwn]

Okay, here is the revised spec.

[christop]

I noticed that Garbage Dir has ID 0x01 and Directory has ID 0xFE. For deleting a directory or file, is the idea to mark it as deleted by clearing some of the bits in the ID? If so, you won't be able to get an ID of 0x01 by clearing some bits from 0xFE, since bit 0 is already clear in 0xFE. For deleted directory you could use the ID 0x02 instead.

Also, the way the swapping is done is pretty wasteful. It wears down FlashROM at least twice as fast as needed, and takes twice as long too. The way I would do it is to use a floating swap page rather than a fixed swap page. What this means is, instead of copying a page to the swap page and then back to the original page, copy a page to the swap page and then make the old page the new swap page.

To implement this you might have to use virtual page numbers. The first byte of each real page can contain the virtual page number for that page. So, for example, if real page 5 is virtual page 9, then all references to page 9 (say, a file entry with the file contents on page 9) will read from or write to the real page number 5. When you need to swap that page, then you can move the whole virtual page to the swap page easily and make real page 5 the new swap page. This adds a little bit of overhead but gives you much better performance overall.

Additionally, for a little bit of protection against incomplete page erases, you could add a few bytes (a magic value like "KFS") to the beginning/end of a page after it is erased. If your routines read a page that doesn't contain that magic value, then you know that the page wasn't erased properly. Erase the page and write the magic value (and virtual page number) to it.

The rest of the spec looks decent, but it is kind of a shame that only one writable stream can be open at a time. It's cool to see that it supports nested directories and long file names, though.

Good luck with this project!

[SirCmpwn]

Thanks for pointing out the directory problem.  I hate using hex for that kind of thing, I always make a mistake like that.
As for virtual pages, it sounds like a great idea to start.  However, it would get pretty inefficient, pretty fast.  Imagine you're several GCs into the usage of the filesystem.  The virtual pages end up completely different then the normal ones.  When looking for file entries, or reading from a stream, crossing page boundaries becomes very slow - you'd have to swap through every physical page until you find the virtual one you need.  That worries me, since you already need to search all entries to find the last file added.  It would be even worse for garbage collection.  Plus, the flash chip is a tough puppy.  I've only ever heard of one calculator's flash dying.

[calc84maniac]

Thanks for pointing out the directory problem.  I hate using hex for that kind of thing, I always make a mistake like that.
As for virtual pages, it sounds like a great idea to start.  However, it would get pretty inefficient, pretty fast.  Imagine you're several GCs into the usage of the filesystem.  The virtual pages end up completely different then the normal ones.  When looking for file entries, or reading from a stream, crossing page boundaries becomes very slow - you'd have to swap through every physical page until you find the virtual one you need.  That worries me, since you already need to search all entries to find the last file added.  It would be even worse for garbage collection.  Plus, the flash chip is a tough puppy.  I've only ever heard of one calculator's flash dying.

Are files allowed to cross sector boundaries? If not, you could go with virtual sectors, and crossing pages can still be done in a sequential manner.

Edit:
Also, I see a problem with directories being 0xFE and garbage directories being 0x01. You can't set bit 0, right?
Edit2:
Oops, that was already mentioned
Edit3:
Now that I look closer, files can be >65536 bytes large, so never mind. Ignore this entire post

[SirCmpwn]

Nice
Yes, a single file may take up the entire calculator's memory if you wanted.

[Goplat]

Thanks for pointing out the directory problem.  I hate using hex for that kind of thing, I always make a mistake like that.
As for virtual pages, it sounds like a great idea to start.  However, it would get pretty inefficient, pretty fast.  Imagine you're several GCs into the usage of the filesystem.  The virtual pages end up completely different then the normal ones.  When looking for file entries, or reading from a stream, crossing page boundaries becomes very slow - you'd have to swap through every physical page until you find the virtual one you need.

Could you keep a copy of the virtual->physical mapping as a table in RAM? With a 1-byte entry per 64kB sector, it should only take 32 bytes.

[christop]

As for virtual pages, it sounds like a great idea to start.  However, it would get pretty inefficient, pretty fast.  Imagine you're several GCs into the usage of the filesystem.  The virtual pages end up completely different then the normal ones.  When looking for file entries, or reading from a stream, crossing page boundaries becomes very slow - you'd have to swap through every physical page until you find the virtual one you need.

You can scan the pages at boot time and keep a table in RAM to map virtual pages to real pages. This can be as simple as an array of bytes, the size being determined by the number of Flash pages (how many pages are there anyway? 32?). To find the real page number for a given virtual page number, just use the virtual page number as an index into the array, and read the byte at that position. That byte is the real page number. When you swap pages (as in, use the floating swap page), you just have to update a couple of bytes in the array.

If you align your array on a 256-byte boundary, the code to translate virtual to real page numbers can be this simple (note: I haven't tested this code):

Code: Select All | Copy To Clipboard

1 2 3 4

ld h,virtual_page_table/256 ld l,a  ; a is the virtual page number ld a,(hl) ; now a is the real page number

You would want to add some bounds checking on the virtual page number and such in a real system, of course.

EDIT: curses! Goplat beat me by 8 seconds!

[SirCmpwn]

Thanks for clarifying your point.  I think that I'll use the current system in this version, look into virtual pages for 3.0.  I'm definitely interested in the idea, but it's just not on the time table right now.

[graphmastur]

Virtual pages do sound interesting. How's 2.2 going?

[SirCmpwn]

Fine, and it's pretty much done.  I just want to get it implemented in KnightOS before releasing it.

[graphmastur]

Fine, and it's pretty much done.  I just want to get it implemented in KnightOS before releasing it.

MMK, that's actually even better.  I can't wait!  Well, I guess I could wait since I'll have to wait, but... You get the idea.