6502.org Forum Projects Code Documents Tools Forum
It is currently Fri Nov 22, 2024 8:59 pm

View unanswered posts | View active topics


Board index » 6502.org Users Forum » Programming

All times are UTC




Post new topic Reply to topic  Page 3 of 6
  [ 89 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next
  Previous topic | Next topic 
Author Message
whartung
PostPosted: Mon Apr 01, 2013 9:21 pm 
Offline

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004
BigDumbDinosaur wrote:
I agree. His filesystem is targeted to lightweight (metaphorically speaking) hardware, which is mostly what we 6502.org types like to build.


So, I take it you're designing a FS for the sake of designing an FS rather than porting an existing file system (ext2, ufs, etc.)? Or is it not worth porting since you don't have a C compiler for the '816? Those file systems work on limited hardware, considering how old they are.
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Fri Apr 05, 2013 7:07 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
whartung wrote:
So, I take it you're designing a FS for the sake of designing an FS rather than porting an existing file system (ext2, ufs, etc.)? Or is it not worth porting since you don't have a C compiler for the '816? Those file systems work on limited hardware, considering how old they are.

If you read back far enough you'll find my motivations for designing a new filesystem. This is not a case of porting anything, but taking the basic concepts of an existing filesystem, adapting them to a 65C816-powered system (not just the POC) and adding a bit more robustness in the process.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:24 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Wed Nov 27, 2013 11:22 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
I continue to rationalize my 816NIX filesystem's design with an eye to reducing the amount of overhead in the structure, as well as the amount of grunt work to be done by the MPU in accessing and manipulating the filesystem's structure. The present design consumes only 0.03 percent of the total filesystem size in static overhead, not counting dynamic overhead used in creating directory structures and indirect block lists. So some progress is being achieved.

Attachment:
File comment: 816NIX geometry for a filesystem with 67,000,000 1KB data blocks (approximately 64GB).
fs_geometry.jpg
fs_geometry.jpg [ 2.29 MiB | Viewed 1446 times ]

All storage in the 816NIX filesystem is managed in 1KB "logical blocks," equal to the size of two physical disk blocks, assuming a hard drive with a default format. I arrived at that logical block size by crunching various possibilities to determine how efficient they would be. Using larger logical blocks tend to be more efficient in compute-bound terms—the bitmaps that track storage will tend to be smaller—but less efficient in the use of available storage space. Smaller logical block sizes reduce slack space when many small files are created, but increases SCSI I/O activity when larger files are accessed, since a single SCSI transaction can't transfer as much data as with a larger logical block size.

As disk capacity isn't really much a concern these days, I decided in favor of a larger logical block size to improve SCSI throughput and reduce the processing overhead needed to manage the filesystem structure. 1KB turned out to be a good compromise, especially when working with a 16 bit MPU. Ergo the disk capacity listed in the above picture is approximately 68.37GB, using a 1KB logical block size (the drive is a Seagate ST373307LW, which has an advertised formatted capacity of 73.3GB).

"Filesystem data blocks" is a test value that I used—it can be anything, as long as it will fit within the 816NIX 64GB limit (explanation of that limit follows).

Overhead includes a superblock, an inode allocation map (IAM), a data block allocation map (BAM) and a BAM tag block. The superblock and the IAM account for the "fixed overhead blocks" value—the present design uses a fixed value of 65,535 for the number of inodes available to catalog files, resulting in the IAM being contained in eight contiguous 1KB blocks. When a new file is created, the IAM is scanned to find an unused inode. In order to minimize disk activity during a search for an unallocated inode, a "tag byte" is maintained in the superblock, with each set bit in the tag byte corresponding to an IAM block that points to at least one unallocated inode. Hence disk activity is limited to a single read of the corresponding IAM block, followed by a later write of the same block after the IAM has been updated.

"Computed BAM blocks" refers to the number of blocks in the BAM that will be required to track the usage of the data blocks. The BAM is a essentially a gigantic bitmap, with a one-for-one correspondence between each bit and a data block. A set bit indicates that its data block is unused. As 816NIX logical blocks are 1KB in size, there are 1024 × 8 bits in a block. Hence, each BAM block can track up to 8192 data blocks.

Also associated with the BAM is a "tag block," one logical block in size, with each bit corresponding to a BAM block. If a bit is set in the tag block it means that the corresponding BAM block points to at least one unallocated data block. As with the use of the IAM tag byte, this BAM tag→BAM→data block hierarchy eliminates the need to search the entire BAM to locate an available data block, especially important as the space consumption in the filesystem approaches the maximum. The BAM tag block can map up to 1024 × 8 or 8192 BAM blocks. Therefore, the maximum number of data blocks that can be supported in the 816NIX filesystem is 8192 × 8192, or 67,108,864 1KB blocks, equal to 64GB.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:26 am, edited 2 times in total.

Top
 Profile  
Reply with quote  
Aslak3
PostPosted: Thu Nov 28, 2013 9:53 pm 
Offline

Joined: Mon Aug 05, 2013 10:43 pm
Posts: 258
Location: Southampton, UK
Impressive BDD! Complex filesystems is stuff people just don't do in assembly anymore. It sounds highly ambitious. How far have you got actually implementing this?

I had a similar idea for my 6809 machine, except I went for a ready made filesystem. Nope not ext[234] but MinixFS. It has handy 16bit block counts, giving a maximum filesystem size of 64MByte. Structure is pure UNIX though, with inodes, directory entries, permissions etc. So far I can list directories by inode number and read a file into RAM, again by inode number. "Harddrive" is a CompactFlash attached directly to my machines 8 bit databus. Not nearly as fancy as your system. I'm quite pleased with what I've done so far though, but reading files by filename would be a nice touch. ;) I don't think I'll ever do writing to the filesystem; It looks much too tricky, with bitmaps to update etc.

Can't wait to see this progress. I wish I had a SCSI controller on my machine...

_________________
8 bit fun and games: https://www.aslak.net/
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Fri Nov 29, 2013 6:52 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
Aslak3 wrote:
Impressive BDD! Complex filesystems is stuff people just don't do in assembly anymore. It sounds highly ambitious. How far have you got actually implementing this?

That screen shot in my last post is from software running on POC V1.1. The display is of the parameters calculated from the input value of 67,000,000 data blocks. When [CR] is pressed at the prompt, the filesystem is generated and is theoretically capable of storing files.

Quote:
I had a similar idea for my 6809 machine, except I went for a ready made filesystem. Nope not ext[234] but MinixFS. It has handy 16bit block counts, giving a maximum filesystem size of 64MByte. Structure is pure UNIX though, with inodes, directory entries, permissions etc.

The Minix filesystem design borrowed from the BSD UNIX filesystem, which in turn, was derived from the UNIX S51K filesystem that came to life in the 1980s. The Minix FS is simplistic (as it was intended to be) and has some problematic areas that resulted in it being supplanted by the EXT series of Linux filesystems (in particular, the block allocation bitmap design is such that the filesystem can be easily corrupted). My 816NIX filesystem is similar to the Acer Fast Filesystem (AFS), but with provisions for longer filenames (up to 30 characters). AFS is also an S51K derivative and was most widely used in SCO UNIX prior to the development of the "extended" Acer Fast Filesystem.

I use an "inverted" bitmap design for inode and data block allocation maps, making the design a bit more resistant to corruption caused by a machine crash (both S51K and Minix FS can be majorly messed up if the machine goes down while the allocation structures are being updated). Also, my design uses tag bitmaps to reduce the number of disk accesses required to locate an unallocated inode or data block. I describe the process I have followed to date in the 816NIX design in this forum topic—reading from the beginning will give you some insight into where I am headed with this.

Quote:
So far I can list directories by inode number and read a file into RAM, again by inode number.

If you have a working mechanism for relating an inode to its corresponding data you're already most of the way to being able to list files by name, as well as display permissions, size, timestamps, etc. It really isn't all that complicated in principle and directories can be simple sequential files listing filenames and associated inodes.

Quote:
"Harddrive" is a CompactFlash attached directly to my machines 8 bit databus. Not nearly as fancy as your system.

Mass storage and filesystems are two separate concepts, and generally should be designed independently of each other. The storage medium dictates the mechanics of how bytes are read and written. The filesystem dictates the organization and meaning of the bytes that are read and written. In other words, what you do is look at raw storage as a black box into which you dump and later on retrieve bytes. Your filesystem primitives determine how to organize the bytes that are dumped and retrieved.

If you make mass storage a separate entity that is only tangentially related to your filesystem, you can adapt your filesystem to any storage device that has adequate capacity, supports random access and does so with a modicum of alacrity. Think of it in terms of using a browser to surf the Web. Your browser makes a request to the remote server and the server sends back a byte stream. The manner in which the remote server honors the request is irrelevant, as long as it provides a byte stream that your browser can organize and intepret.

In the world of SCSI, the terms "initiator" and "target" were long-used to refer to the device that, respectively, initiates service requests and the device that fulfills them. Current standards now use "application client" and "device server" in place of "initiator" and "target" in order to better reflect what is going on. What hasn't changed is that the "application client" doesn't have to know how the "device server" stores and retrieves data, or even where it stores it (which makes iSCSI possible). All that has to be known is how to issue commands and what the possible results will be. Hence, I can write any filesystem I want, and when the filesystem code has to talk to a mass storage device, it only has to call a BIOS or operating system kernel primitive to get service. The filesystem doesn't really care whether the "device server" is a disk, CD-ROM, WORM, etc. It doesn't even care if the "device server" is physically attached to the host (as is the case with POC) or is located in the next city. All that matters is that the "device server" is capable of performing according to the SCSI block device standard.

This is what is meant by the "hardware abstraction layer" (HAL) in some operating systems.

Quote:
I'm quite pleased with what I've done so far though, but reading files by filename would be a nice touch. ;) I don't think I'll ever do writing to the filesystem; It looks much too tricky, with bitmaps to update etc.

It's not that difficult if you think it through and modularize things. At least with the 65C816, manipulating a bitmap isn't too onerous. The rest is merely defining a sequence of steps that must be completed to find and allocate storage, write data into it and update the relevant data structures. Procedure, procedure...

Quote:
Can't wait to see this progress. I wish I had a SCSI controller on my machine...

What are you waiting for? Fire up your schematic editor! :)

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:30 am, edited 2 times in total.

Top
 Profile  
Reply with quote  
Aslak3
PostPosted: Fri Nov 29, 2013 8:34 pm 
Offline

Joined: Mon Aug 05, 2013 10:43 pm
Posts: 258
Location: Southampton, UK
BigDumbDinosaur wrote:
That screen shot in my last post is from software running on POC V1.1. The display is of the parameters calculated from the input value of 67,000,000 data blocks. When [CR] is pressed at the prompt, the filesystem is generated and is theoretically capable of storing files.


So, in UNIX term, you have implemented mkfs. Splendid. :)

Quote:
The Minix filesystem design borrowed from the BSD UNIX filesystem, which in turn, was derived from the UNIX S51K filesystem that came to life in the 1970s. The Minix FS is simplistic (as it was intended to be) and has some problematic areas that resulted in it being supplanted by the EXT series of Linux filesystems (in particular, the allocation bitmap design is such that the filesystem can be easily corrupted). ...


My main requirement was to be able to read files from a removable storage device. Everyone and their cat will use FAT16 as the filesystem of choice. My initial goal was to implement, in 6809 asm, a reader for EXT2, but that filesystem is complex to parse, and used 32bit block pointers. So instead I looked at MinixFS, and because - at least for MinixFS v1 - the pointers are all 16bit, it seemed ideal for my 8/16 bit 6809. Inodes are simple 32byte structures (so 32 per 1KB block), and dir entries are likewise 32bytes - 2 bytes for the inode pointer and 30 bytes for the filename. Nice and convient, for me, as inode block numbers and offsets within the blocks can be calculated with shifting and masking.

Quote:
... I describe the process I have followed to date in the 816NIX design in this forum topic—reading from the beginning will give you some insight into where I am headed with this.


I shall certainly go back and give it a good old read. I love the detail you go into with most of what you write. :)

Quote:
If you have a working mechanism for relating an inode to its corresponding data you're already most of the way to being able to list files by name, as well as display permissions, size, timestamps, etc. It really isn't all that complicated in principle and directories can be simple sequential files listing filenames and associated inodes.


Sorry I should have been more clear. I can list a directory by inode and view inode numbers, permissions, file sizes, and filenames. Like this:

Code:
Monitor: > m
Partition starts at: 0020                                                       
Magic is: 138F                                                                 
Start of inodes at block: 000D                                                 
Monitor: > l 0001                                                                                                                       
0001 41ED 00E0 .                                                               
0001 41ED 00E0 ..                                                               
0002 81ED 154D article4.txt                                                     
0003 81A4 0139 settime.bin                                                     
0004 81A4 00A5 showtime.bin                                                     
0005 81A4 0037 testprog.bin                                                     
0006 81A4 001C type.bin


Columns are: inode, type/perms, filesize and filename. My next task is to write a directory parser then can find the named file and return its inode number. Then I can hook the directory and file reading commands to use that.

Quote:
Mass storage and filesystems are two separate concepts, and generally should be designed independently of each other. The storage medium dictates the mechanics of how bytes are read and written. The filesystem dictates the organization and meaning of the bytes that are read and written. In other words, what you do is look at raw storage as a black box into which you dump and later on retrieve bytes. Your filesystem primitives determine how to organize the bytes that are dumped and retrieved.
...


Yes indeed. For my IDE/CompactFlash reading code, I started off with "raw" I/O on 512byte disk bytes, reading those into memory and so on. My MinixFS reading code uses those same functions. Now, I haven't gone "all out" and written a proper abstraction layer. Are you doing that? It would not be too hard to do; just decide on a block-device layer API and stick to it. For each different block device driver, a different jump table could be slotted in.

While on the subject of APIs, are you planning on writing a full user filesystem API? By that I mean a mechanism to handle "open" files, with file handles, seek operations and so on? I'm not sure how far along the rest of your system-level code is. Implementing a full OS with multi-tasking, filesystem drivers, serial drivers, etc sounds like an awesome undertaking though!

Quote:
Quote:
I'm quite pleased with what I've done so far though, but reading files by filename would be a nice touch. ;) I don't think I'll ever do writing to the filesystem; It looks much too tricky, with bitmaps to update etc.


It's not that difficult if you think it through and modularize things. At least with the 65C816, manipulating a bitmap isn't too onerous. The rest is merely defining a sequence of steps that must be completed to find and allocate storage, write data into it and update the relevant data structures. Procedure, procedure...


I might have a look at writing to the filesystem at some point. Creating new files, or rewriting an entire new file, might be *reasonably* straightforward. Appending to files, though... sounds really fiddly.

Quote:
Quote:
Can't wait to see this progress. I wish I had a SCSI controller on my machine...

What are you waiting for? Fire up your schematic editor! :)


I think your skills are quite beyond mine. ;)

Check out my blog if you're board... The filesystem stuff is roughly described here: http://aslak3.blogspot.co.uk/2013/11/sound-and-running-programs-from-cf.html

_________________
8 bit fun and games: https://www.aslak.net/
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Sat Nov 30, 2013 5:11 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
Aslak3 wrote:
BigDumbDinosaur wrote:
That screen shot in my last post is from software running on POC V1.1. The display is of the parameters calculated from the input value of 67,000,000 data blocks. When [CR] is pressed at the prompt, the filesystem is generated and is theoretically capable of storing files.

So, in UNIX term, you have implemented mkfs. Splendid. :)

More-or-less. Right now I'm hard-coding the filesystem size into the program for testing purposes, since test code is run from the M/L monitor's prompt, which can't parse for command line arguments. The "mkfs" program takes a filesystem size value in kilobytes (minimum of 16,395 KB, maximum of 67,125,258 KB), computes the geometry that corresponds to that size, displays the pertinent values and then awaits user confirmation. If told to continue, the program generates the inode and data block allocation maps, writes a superblock and updates the filesystem table in physical block zero of the disk. If no valid boot block exists, the program prompts the user to create one.

The program is somewhat time-consuming to debug and test, as I have to manually examine disk blocks from within the M/L monitor to see what was written. However, once I have verified that everything works as it should, the code can be readily expanded to produce the full effect of mkfs.

Quote:
My main requirement was to be able to read files from a removable storage device. Everyone and their cat will use FAT16 as the filesystem of choice.

Not this cat...er...dinosaur. FAT16 is an inefficient and fragile filesystem. Peter Norton became wealthy because of FAT16.

Quote:
My initial goal was to implement, in 6809 asm, a reader for EXT2, but that filesystem is complex to parse, and used 32bit block pointers. So instead I looked at MinixFS, and because - at least for MinixFS v1 - the pointers are all 16bit, it seemed ideal for my 8/16 bit 6809. Inodes are simple 32byte structures (so 32 per 1KB block), and dir entries are likewise 32bytes - 2 bytes for the inode pointer and 30 bytes for the filename. Nice and convient, for me, as inode block numbers and offsets within the blocks can be calculated with shifting and masking.

In my implementation, I'm using an on-disk inode size of 128 bytes, with an enlarged table of contents that moves the indirect addressing threshold from ~10KB to 22KB, which will make usage of small files more efficient. The in-core inode is larger because it also includes several status flags that prevent process contention during file I/O. All filesystem computations are 32 bits, done with an integer math package I wrote to do the grunt work.

Quote:
Sorry I should have been more clear. I can list a directory by inode and view inode numbers, permissions, file sizes, and filenames. Like this:

Code:
Monitor: > m
Partition starts at: 0020                                                       
Magic is: 138F                                                                 
Start of inodes at block: 000D                                                 
Monitor: > l 0001                                                                                                                       
0001 41ED 00E0 .                                                               
0001 41ED 00E0 ..                                                               
0002 81ED 154D article4.txt                                                     
0003 81A4 0139 settime.bin                                                     
0004 81A4 00A5 showtime.bin                                                     
0005 81A4 0037 testprog.bin                                                     
0006 81A4 001C type.bin


Columns are: inode, type/perms, filesize and filename. My next task is to write a directory parser then can find the named file and return its inode number. Then I can hook the directory and file reading commands to use that.

Can you get it to display the file attributes in a human-readable format along the lines of what one would see with an ls -l style display?

Quote:
Now, I haven't gone "all out" and written a proper abstraction layer. Are you doing that?

I'm getting there, although right now the abstraction is split between the BIOS ROM and the application that requests access to the SCSI device. Owing to space limitations in the ROM, it can only provide a SCSI command executive, to which the calling function has to supply a command descriptor block. That aspect is contained in a function structured as a subroutine, to which parameters such as buffer address, logical block address, number of blocks to read, etc., are passed on the stack. It's still pretty low-level but can be called via macros, making is seem less primitive.

Quote:
While on the subject of APIs, are you planning on writing a full user filesystem API? By that I mean a mechanism to handle "open" files, with file handles, seek operations and so on? I'm not sure how far along the rest of your system-level code is. Implementing a full OS with multi-tasking, filesystem drivers, serial drivers, etc sounds like an awesome undertaking though!

The eventual goal is a preemptive, multitasking kernel that provides buffered and unbuffered device access, along with facilities to open, close, create, link and unlink files. It will be an extensive project, but that's the point.

Quote:
I might have a look at writing to the filesystem at some point. Creating new files, or rewriting an entire new file, might be *reasonably* straightforward. Appending to files, though... sounds really fiddly.

Appending is not a big deal. You open the file and seek to the end. The number of bytes in the file is the "end pointer." If the file is empty, the end pointer is zero. Once you've seeked, start writing.

Quote:
Quote:
Quote:
Can't wait to see this progress. I wish I had a SCSI controller on my machine...

What are you waiting for? Fire up your schematic editor! :)

I think your skills are quite beyond mine. ;)

My skills are average. :)

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:36 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Wed Mar 19, 2014 6:18 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
This project has languished as of late. Too much stuff to do and, as usual, not enough time in which to do it. I'm currently writing a major system proposal for a new client—this despite wanting to scale back business activities. :lol:

However, I do periodically revisit what I've accomplished to date. I probably won't resume on my 816NIX filesystem and kernel code until after I have built and debugged POC V2.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:36 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
Rob Finch
PostPosted: Fri Apr 11, 2014 4:03 am 
Offline
User avatar

Joined: Sun Dec 29, 2002 8:56 pm
Posts: 460
Location: Canada
Just wanted to say I had some interest in this topic. I'd like to port a filesystem to my system at some point. My system has an HD SD-Card interface so there's potentially many GB's of storage.
One thing I noticed is with potentially 24 bit inode pointers, perhaps the filenames could be limited to 29 characters ? So that there are three bytes avilable for the node pointer.

_________________
http://www.finitron.ca
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Fri Apr 11, 2014 5:40 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
Rob Finch wrote:
Just wanted to say I had some interest in this topic. I'd like to port a filesystem to my system at some point. My system has an HD SD-Card interface so there's potentially many GB's of storage.
One thing I noticed is with potentially 24 bit inode pointers, perhaps the filenames could be limited to 29 characters ? So that there are three bytes avilable for the node pointer.

Yes, 24 bit inode numbers could allow up 16,777,215 files per filesystem with only a trivial reduction in filename size, as you note. Given that really high capacity mass storage is readily available, your suggestion has merit and has me giving the 816NIX filesystem some more thought.

Increasing the inode number size to 24 bits somewhat complicates inode management. Part of it has to do with the fact that 24 bit integer arithmetic with the 65C816 is actually a clumsy undertaking. Ironically, 32 bit integer arithmetic on the 65C816 takes no more effort than does 16 bit integer arithmetic with a 65C02 and uses fewer clock cycles per operation than manipulating 24 bit values. So in-core inode numbers would be most efficiently managed as 32 bit values, increasing the amount of storage used by open file tables and other structures.

Also to be considered is that the inode allocation bitmap would be substantially larger and hence more complicated to manage. Assuming the 16,777,215 file limit, that's 16,777,216 bits to be managed (inode $000000, while assigned a spot in the bitmap, doesn't actually exist). A total of 2,097,152 bitmap bytes would be required (not counting overhead) or 2048 logical (1024 byte) disk blocks. Where the complication comes in is that when a file is created, the bitmap has to be scanned to find an available inode. Clearly, a sequential search from the start of the bitmap would be too slow to be practical—if the first available inode is in the last block, 2047 other blocks have to be loaded and scanned. Even at SCSI speeds that would take too much time.

In order to avoid a lot of disk gyrations, a tag map would have to be used to determine which of the bitmap blocks has at least one available inode. Since there would be 2048 bitmap blocks, the tag map would need 2048 bits, or 256 bytes. I could probably shoehorn that into the tail end of the filesystem's superblock, practical because the 816NIX filesystem uses a 1K logical block size and my design doesn't fill up the superblock with a linked list like the old S51K filesystem did (note that when a filesystem has been mounted the superblock will always be resident in RAM).

The search for an inode would commence with scanning the tag map until a byte is found with at least one set bit. That set bit would point to an inode bitmap block that points to at least one available inode. That block would be loaded and scanned to find the first byte with a set bit. That would point to the available inode. Provisions would have to be made to reconcile the tag map with the inode bitmap during file system consistency checks. I already use the tag principle to manage the data block allocation map, which is many times larger than the inode allocation map. So the code to manage both would be similar in structure and in fact, may be sharable.

When I get back on this I will do the necessary engineering to figure out how to make it work.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:38 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
Rob Finch
PostPosted: Fri Apr 11, 2014 12:31 pm 
Offline
User avatar

Joined: Sun Dec 29, 2002 8:56 pm
Posts: 460
Location: Canada
The file system I was working on (DNF-24?) was planned around a 64GB SDCard as an example. That's a 36 bit address space to map into.

; 64GB card
; 36 address bits
; 9 bits for 512 byte block size
; 27 bits for block number (this is too many > 24 bits)
; 4kB cluster size = 3 bits (so we use a cluster approach)
; 24 bit cluster number
; 2MB bitmap of allocated clusters ( contained in 512 clusters)
; 512 super bitmap bits
;
Although 24 bits is enough for 16M inodes, I was planning on using only 1M inodes or 20 bits so the allocation map is only 128kB. I assume this sort of thing should be stored as a parameter in the super block ?
Also I was planning on using a logical block size of 4kB (eight sectors). This could also be called a cluster and could also be a parameter.

FS layout:
; $00000000 super block
; $00000001 inode allocation map (128kB)
; $00000101 inode array (1M x 128 byte entries)
; $00040101 super bitmap bits (512 bits)
; $00040102 cluster allocation map (2MB)
; $00041102 start of data clusters

One thing I thought of (since suggesting 29 chars) was to have the higher order bits of the inode numbers stored as part of directory information, so that the 64k file limit becomes a 64k file limit per directory. All the files in a directory would share the same high order bits. The inode map would then be partitioned into a number of directories. This would allow 30 chars for the filename then. It'd also be backwards compatible with 816NIX. For a 24 bit space, There would be 256 root directory slots available. The number of inodes that need to be searched for availability is then still limited to 64k.

_________________
http://www.finitron.ca
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Fri Apr 11, 2014 4:44 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
I'm not wild about using clusters to allocate data storage. With a 4KB cluster size, for example, a one byte file takes up 4KB of storage, plus an inode. Generate enough one and two byte files and all your storage is used up, even though there's plenty of storage that is not in use (the slack space in each cluster). To a lesser extent, this could be a problem with the 1KB logical block filesystem I plan to use, but would take four times as many one byte files to achieve, so there is some improvement.

As for "partitioning" directories in the way you are considering, it's been my experience that directories seldom collect more than 300-500 entries en toto. The main concern with large directories is the need to use indirect addressing during a search for a filename. The threshold for that in my 816NIX filesystem would be 641 filenames. Clearly, artificially limiting a directory size to 64KB filenames wouldn't have any effect on search times. The kernel would be into doubly indirect addressing at that point.

Something that I have entertained at times is the notion of structuring a directory as a B-tree, with master, coarse and fine levels. The search for any filename would require no more than three disk accesses per directory, as compared to a linear search through a "flat" directory, which could entail a lot of disk accesses if the directory has hundreds of filenames. Hence the directory size would not have any significant effect on filename search times. The downside, of course, would be that creating, renaming, linking or deleting a file would entail significant grunt work on the part of the kernel to maintain the B-tree structure. Also, programs that work with directories could not simply open one and read from it the way it could be done with a flat directory structure.

Due to the nature of a B-tree, a sequential retrieval of filenames from the directory, as would be done when listing the directory (e.g., ls -l), would be automatically sorted in ascending alphanumeric order. In most cases, that is how directories are displayed, so the ls program would not have to do a sort prior to display, resulting in a performance improvement. Using bidirectional links in each level of the B-tree, reverse listings would be just as fast and efficient as forward listings. Of course, secondary sorting would be required to list filenames in something other than alphanumeric order, e.g., in last mod time order.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:41 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
Tor
PostPosted: Sat Apr 12, 2014 1:18 am 
Offline

Joined: Sun Apr 10, 2011 8:29 am
Posts: 597
Location: Norway/Japan
99.9% of my 'ls' usage on *nix is a variant of exactly that: Last mod time order. It's way more useful than alphabethical sorting. Specifically, I use 'ls -lrt' almost always. For those not speaking *nix, it means 'long' (display the time), 'reverse', 'time' sorted: List the latest-modfied files last. So an 'ls -lrt' in my terminal window will leave me with the latest files at the bottom and those are often what I'm most interested in. And if not, I page backwards from there until I get far enough back in time.
I almost never need the standard alphabetical sorting. I use alphabetical sorting elsewhere, e.g. for the output from the tool which shows me available new software packages. But not for 'ls'. I'm not sure what other people prefer though. However, with more files in a directory than what fits inside a terminal window (or file manager screen for that matter) it's difficult to see any better way to quickly find the files you're currently working on.

-Tor
Top
 Profile  
Reply with quote  
BigDumbDinosaur
PostPosted: Sat Apr 12, 2014 1:58 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8506
Location: Midwestern USA
Tor wrote:
99.9% of my 'ls' usage on *nix is a variant of exactly that: Last mod time order. It's way more useful than alphabethical sorting. Specifically, I use 'ls -lrt' almost always. For those not speaking *nix, it means 'long' (display the time), 'reverse', 'time' sorted: List the latest-modfied files last. So an 'ls -lrt' in my terminal window will leave me with the latest files at the bottom and those are often what I'm most interested in. And if not, I page backwards from there until I get far enough back in time.
I almost never need the standard alphabetical sorting. I use alphabetical sorting elsewhere, e.g. for the output from the tool which shows me available new software packages. But not for 'ls'. I'm not sure what other people prefer though. However, with more files in a directory than what fits inside a terminal window (or file manager screen for that matter) it's difficult to see any better way to quickly find the files you're currently working on.

-Tor

I don't often request a full directory listing, as I'm almost always looking for a specific file or name pattern. However, I often use the -rt option when determining when I last modified a file version, e.g., ls -lrt 816nix*.

That said, the internals of a filesystem are separate from how programs access it and are of no direct concern to the user, since s/he can't normally access the raw filesystem structure. Whether a directory is a B-tree or a flat series of bytes only matters to any program that would access it. As I said, the B-tree structure results in a relatively constant amount of disk access to search for a specific filename, whereas the flat space search could result in many disk accesses. So there is a performance benefit to the B-tree layout. I also anticipate that the B-tree layout would help performance when a pattern has been given to the shell, as in the aforementioned ls -lrt 816nix*, the reason being that the search starts at the first entry in the directory that matches 816nix. Obviously, something like ls -l *.src would not benefit from the B-tree, since the search would have to start with the first entry in the directory, essentially producing the same amount of disk activity as with a flat space directory.

An alternate directory lister sort, as would be generated with ls -lrt, would be primarily a compute-bound operation and in fact, could be accomplished with an insertion sort, using pointers to the filenames to avoid having to shift character strings when an insertion has to occur. Doing so, however, would set a limit on how many names could be sorted, since at least with the 65C816, physical RAM in which to construct a pointer table and store filenames and their associated inode numbers would be limited. Dunno about you, but I have no plans to build a 65C816 machine with a virtual memory architecture. I don't think I would live long enough to work out all of the details, let alone actually implement them. :lol:

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Tue Mar 15, 2022 2:44 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
cr1901
PostPosted: Sun Jun 01, 2014 7:49 pm 
Offline

Joined: Wed Feb 05, 2014 7:02 pm
Posts: 158
Is it in your plans to make this file-system POSIX-compliant (to an extent)?

Also, re: not porting a filesystem from the C world- if any of them rely of GNU C extensions, then it isn't possible to port it, and gcc doesn't exist for the '816 anymore.
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 3 of 6
  [ 89 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next

Board index » 6502.org Users Forum » Programming

All times are UTC


Who is online

Users browsing this forum: No registered users and 24 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
6502.org is an ongoing project by Mike Naberezny and contributors.