Considering how to implement a directory listing system, I can load files if I know what they're called, but it would be nice to be able to enumerate them. Also finishing the FAT implementation of Delete would be handy so that I can overwrite files. Oh, and the streams, always the streams.
2010-02-25
2010-02-25 - Debugging
A bit of debugging today and found why it was broken ... it helps if you don't overwrite your own stack when reading data. Fixed that and I now have "OS-in-a-Bochs".
Considering how to implement a directory listing system, I can load files if I know what they're called, but it would be nice to be able to enumerate them. Also finishing the FAT implementation of Delete would be handy so that I can overwrite files. Oh, and the streams, always the streams.
Considering how to implement a directory listing system, I can load files if I know what they're called, but it would be nice to be able to enumerate them. Also finishing the FAT implementation of Delete would be handy so that I can overwrite files. Oh, and the streams, always the streams.
2010-02-24
2010-02-24 - Bootloading from a FAT Filesystem
Finished entering the code that I came up with last night, added a few tweaks to improve it, and also fixed some invalid pushes and pops. First test suggests that it was successful, but an examination of the memory says it wasn't. This problem was quickly tracked down to not having reset BX (the buffer address) back to 0, so it should have gone to 0x0600:0600 (or 0x06600). After fixing that and a quick test, it loads the block successfully. \ o /
Next I need to put a disk to the bootblock so that it is complete. I think actually putting a kernel on may be a good start, and a load of other files just so that I can tell if sectors have loaded (instead of all zeroes).
The calculations for the start and length in blocks of the root directory have been successful, but the load is failing. Going to examine the parameters being passed to the BIOS INT 0x13 call
The Drive and Head parameters were the wrong way round in DX. Fixed that. It's now loading the Root directory correctly, searching for the file, then loading the FAT correctly. I don't think the search is quite correct though, it found the file even when I changed the filename to something wrong.
With one small exception, the first draft is complete, using 440 bytes of 512
First block of the file is being loaded correctly, but the FAT read to find the next cluster seems to have yielded incorrect results.
Fixed up the FAT reading code, there were a number of errors, and it seems to have read all the sectors of the Kernel into memory. Just need to get the counter incrementing correctly so that they are not all written on top of each other, and it will be done.
Also need to test reading beyond Cylinder 0
\ o / The counter is now incrementing correctly, and the kernel had been loaded, and I've put in the call to jump to the Kernel, and it's loaded up ... with 40 bytes of bootblock to spare
I am limited to the first 8Gb for loading the kernel by the BIOS, and I am also limited to 43'690 clusters by the cluster computation algorithm. In fairness though, FAT12 is going to give up long before my code does.
As for performance, not so much. The primary problem here is that I load the entire root directory into memory, scan that, then load the entire FAT into memory and scan that whilst loading the kernel. Given that loading sectors from a disk is going to be quite slow, this may well be a significant performance hit.
Having done "the math" against a Windows XP formatted 1.44Mb floppy, the FAT occupies 9 sectors and the Root Directory occupies 14, so the "entire data" load that I was worried about clocks in at just under 12Kb, less than 0.5% of the disk ... so meh.
I still need to add retry code and a few failure paths, so I'll probably eat my 40 bytes fairly quickly.
In any case, I'm happy, I have a full FAT12 file finder and loader in 389 bytes of code (with some more for data)
The other avenue that this presents is the possibility that I could create a small FAT12 Partition on the Hard drive in my test machine and put my boot block in the first block of the partition, then have my OS booting from the hard drive (with a few tweaks). I could then PXE boot a new kernel, and then get the kernel to save itself out of memory onto the disk. It's no Windows Update ... but then again, this would work
Looks like I have some more debugging to do, just dropped the latest (~85Kb) kernel onto the disk image and it's failing to load. Could be either filesize, or the location of the sectors, or both. :S Back to the debugging ...
It has loaded 66 sectors, it is about to try to load cluster 0x034C, which I think is block 875, but I have tried to test them individually, and them seem to work.
Next I need to put a disk to the bootblock so that it is complete. I think actually putting a kernel on may be a good start, and a load of other files just so that I can tell if sectors have loaded (instead of all zeroes).
The calculations for the start and length in blocks of the root directory have been successful, but the load is failing. Going to examine the parameters being passed to the BIOS INT 0x13 call
The Drive and Head parameters were the wrong way round in DX. Fixed that. It's now loading the Root directory correctly, searching for the file, then loading the FAT correctly. I don't think the search is quite correct though, it found the file even when I changed the filename to something wrong.
With one small exception, the first draft is complete, using 440 bytes of 512
First block of the file is being loaded correctly, but the FAT read to find the next cluster seems to have yielded incorrect results.
Fixed up the FAT reading code, there were a number of errors, and it seems to have read all the sectors of the Kernel into memory. Just need to get the counter incrementing correctly so that they are not all written on top of each other, and it will be done.
Also need to test reading beyond Cylinder 0
\ o / The counter is now incrementing correctly, and the kernel had been loaded, and I've put in the call to jump to the Kernel, and it's loaded up ... with 40 bytes of bootblock to spare
I am limited to the first 8Gb for loading the kernel by the BIOS, and I am also limited to 43'690 clusters by the cluster computation algorithm. In fairness though, FAT12 is going to give up long before my code does.
As for performance, not so much. The primary problem here is that I load the entire root directory into memory, scan that, then load the entire FAT into memory and scan that whilst loading the kernel. Given that loading sectors from a disk is going to be quite slow, this may well be a significant performance hit.
Having done "the math" against a Windows XP formatted 1.44Mb floppy, the FAT occupies 9 sectors and the Root Directory occupies 14, so the "entire data" load that I was worried about clocks in at just under 12Kb, less than 0.5% of the disk ... so meh.
I still need to add retry code and a few failure paths, so I'll probably eat my 40 bytes fairly quickly.
In any case, I'm happy, I have a full FAT12 file finder and loader in 389 bytes of code (with some more for data)
The other avenue that this presents is the possibility that I could create a small FAT12 Partition on the Hard drive in my test machine and put my boot block in the first block of the partition, then have my OS booting from the hard drive (with a few tweaks). I could then PXE boot a new kernel, and then get the kernel to save itself out of memory onto the disk. It's no Windows Update ... but then again, this would work
Looks like I have some more debugging to do, just dropped the latest (~85Kb) kernel onto the disk image and it's failing to load. Could be either filesize, or the location of the sectors, or both. :S Back to the debugging ...
It has loaded 66 sectors, it is about to try to load cluster 0x034C, which I think is block 875, but I have tried to test them individually, and them seem to work.
2010-02-23
2010-02-23 - Bootblock Development
Bootblock:
1) Correct the origin issue. My code has to run with an Origin of 0 so that I can relocate it to 0x7A00 with ease
2) Set the DS register correctly, it is needed for accessing the memory.
3) Remember that sector 0 is invalid
4) Read to the end of the chain, not to the end of the file. File size is irrelevant, truncation is futile, the sectors will be assimilated
5) The teletype function is INT 0x10,AH=0x0E
6) Add LBA-CHS conversion to the sector loader. Means one register for sector numbers up to 65536 (32Mb disk)
Because I am loading the code at 7C00 then copying it to 7A00 out of the way, there is no meaningful value I can use for the Origin of the file except zero. Anything else and I either need to add an offset to each jump and memory reference before the 7A00 switch, or to everything after it.
I have gotten the code to work now using an Origin of zero. The code segment I was loading was a power of 16 out. Never can remember that Segment:Address syntax.
If I use a single 16-bit register (in real mode) to represent my sector address on disk, that gives me only 65536 sectors which means a limit of a 32Mb disk with a common 512-byte sector size, or rather, that we can only read the first 32 Mb of the disk.
Given that the CHS translation of the BIOS allows us to read the first 8Gb, I'd like to extend the LBA mapping to use two 16-bit registers to store the value.
However, in order to then compute the CHS values from the LBA value, I need to perform "long division" and "long modulo" on the two registers separately and then combine the result.
So just trying to compute the algorithm now.
Hmm, upon further investigation, the DIV instruction actually works against a 32-bit register pair anyway, specifically DX:AX, and would allow me to address 2Tb of drive, not that FAT12 can effectively support a drive that big, nor that the BIOS CHS can actually address a drive that big.
Anyway, given that the INT 0x13 command requires specific values in specific registers, and that the 32-bit DIV instruction requires the use of other specific registers, I shall try to write a LBA-CHS conversion algorithm that takes advantage of these whilst being efficient.
1) Correct the origin issue. My code has to run with an Origin of 0 so that I can relocate it to 0x7A00 with ease
2) Set the DS register correctly, it is needed for accessing the memory.
3) Remember that sector 0 is invalid
4) Read to the end of the chain, not to the end of the file. File size is irrelevant, truncation is futile, the sectors will be assimilated
5) The teletype function is INT 0x10,AH=0x0E
6) Add LBA-CHS conversion to the sector loader. Means one register for sector numbers up to 65536 (32Mb disk)
Because I am loading the code at 7C00 then copying it to 7A00 out of the way, there is no meaningful value I can use for the Origin of the file except zero. Anything else and I either need to add an offset to each jump and memory reference before the 7A00 switch, or to everything after it.
I have gotten the code to work now using an Origin of zero. The code segment I was loading was a power of 16 out. Never can remember that Segment:Address syntax.
If I use a single 16-bit register (in real mode) to represent my sector address on disk, that gives me only 65536 sectors which means a limit of a 32Mb disk with a common 512-byte sector size, or rather, that we can only read the first 32 Mb of the disk.
Given that the CHS translation of the BIOS allows us to read the first 8Gb, I'd like to extend the LBA mapping to use two 16-bit registers to store the value.
However, in order to then compute the CHS values from the LBA value, I need to perform "long division" and "long modulo" on the two registers separately and then combine the result.
So just trying to compute the algorithm now.
Hmm, upon further investigation, the DIV instruction actually works against a 32-bit register pair anyway, specifically DX:AX, and would allow me to address 2Tb of drive, not that FAT12 can effectively support a drive that big, nor that the BIOS CHS can actually address a drive that big.
Anyway, given that the INT 0x13 command requires specific values in specific registers, and that the 32-bit DIV instruction requires the use of other specific registers, I shall try to write a LBA-CHS conversion algorithm that takes advantage of these whilst being efficient.
2010-02-22
2010-02-22 - Bootblock Development
Ok, change of tac for today ... using assembly to find and load a file from a FAT drive. Should allow me to create kernel files and drop them onto a disk to be able to demonstrate on Bochs or a real machine, whilst also being able to take the same file and PXE boot it still.
Going to assume a file in the root directory with a known name that is within the reach of the BIOS functions
Wow, didn't realise how rusty I am on Assembly, four hours of development and I have fewer than 100 lines to show for it
Going to assume a file in the root directory with a known name that is within the reach of the BIOS functions
Wow, didn't realise how rusty I am on Assembly, four hours of development and I have fewer than 100 lines to show for it
2010-02-21
2010-02-21 - DosDevices and Filesystems
Work is progressing on the Dos Abstraction layer. The mountlist parser is finished, and the filesystem and device are being looked up by the library loader and accessed. If found, they are being put into a DosDevice structure and added to the list of devices.
I have just finished the abstracted version of LoadFile (which used to be implemented by the FAT driver dierctly to load from the "current" FAT volume) so that it looks up the dos device in question("BOOT:"), find the Filesystem attached to it, and call the LoadFile routine on that filesystem, passing it the path of the file.
Onoes! /o\ A memory leak has developed somewhere within the Dos_Loadfile routine. It's leaking 32 bytes, but it is cause the available space for the file to drift by 544 bytes each time. Something must be done! One scheme is to modify MM_Malloc() so that it records the return address of the call to MM_Malloc(), that way, the address of the instruction that allocated the space will be on record.
Success! With a little inline assembly, I have been able to read the address of the instruction that is calling MM_Malloc() and store it along with the used block entry. When my used block is full (and the system is therefore going into a controlled fail) it writes out the top entries in the memory list so that I can see what the block size is and where it was allocated, and can track it down.
My file searching function (that finds the first directory entry that matches the filename) was being called, but the returned entry was not being freed in all cases. That was fixed, and now it is looping the load quite happily with no leak. \ o /
Memory leaks and allocators aside, I need to finish off changing the Fat driver so that it uses the Context and not any global variables. A good place to start would be to remove all the global variables and then see where we are :)
Ok, so I have spent most of the evening re-writing the Fat driver to use a structure for its state instead of global variables. This way it will be able to handle multiple Fat volumes at once.
Damn, that's why it doesn't work. I need to implement the mountlist parsing within the Ram driver. It needs to read the parameters and make sense of them. However, on the up side, it did remind me the LoadFile routine needs to test for a DosDevice being passed, a FileSystemContext within that DosDevice, and for the Context to be flagged as valid.
\ o / A quick implementation of the versatile strtol() string-to-long converter and I'm able to finish parsing the mountlist values into the ram driver, and it has found the disk image in memory correctly, and FAT has deemed that it is valid.
Now ... why is it throwing an interrupt 6 (Invalid OpCode) when I try to read the drive?
Fixed the invalid opcode ( was passing 0 instead of the context ) and put in the appropriate exception path for that too, and then fixed the general protection fault that it hit after that. I was using a ternary operator without the correct parenthesis. Instead of allocating 1024 bytes, it was allocating 2, then using 1022 bytes of other allocation's space with "predictable" results.
You can now request that the Dos layer load a file such as "Boot:test~1.lib" and it will look up "BOOT:" in the device list, find the FileSystem attached to it and tell it to open "test~1.lib", which will then use the BlockDeviceDriver in the DosDevice to read the "disk".
I have just finished the abstracted version of LoadFile (which used to be implemented by the FAT driver dierctly to load from the "current" FAT volume) so that it looks up the dos device in question("BOOT:"), find the Filesystem attached to it, and call the LoadFile routine on that filesystem, passing it the path of the file.
Onoes! /o\ A memory leak has developed somewhere within the Dos_Loadfile routine. It's leaking 32 bytes, but it is cause the available space for the file to drift by 544 bytes each time. Something must be done! One scheme is to modify MM_Malloc() so that it records the return address of the call to MM_Malloc(), that way, the address of the instruction that allocated the space will be on record.
Success! With a little inline assembly, I have been able to read the address of the instruction that is calling MM_Malloc() and store it along with the used block entry. When my used block is full (and the system is therefore going into a controlled fail) it writes out the top entries in the memory list so that I can see what the block size is and where it was allocated, and can track it down.
My file searching function (that finds the first directory entry that matches the filename) was being called, but the returned entry was not being freed in all cases. That was fixed, and now it is looping the load quite happily with no leak. \ o /
Memory leaks and allocators aside, I need to finish off changing the Fat driver so that it uses the Context and not any global variables. A good place to start would be to remove all the global variables and then see where we are :)
Ok, so I have spent most of the evening re-writing the Fat driver to use a structure for its state instead of global variables. This way it will be able to handle multiple Fat volumes at once.
Damn, that's why it doesn't work. I need to implement the mountlist parsing within the Ram driver. It needs to read the parameters and make sense of them. However, on the up side, it did remind me the LoadFile routine needs to test for a DosDevice being passed, a FileSystemContext within that DosDevice, and for the Context to be flagged as valid.
\ o / A quick implementation of the versatile strtol() string-to-long converter and I'm able to finish parsing the mountlist values into the ram driver, and it has found the disk image in memory correctly, and FAT has deemed that it is valid.
Now ... why is it throwing an interrupt 6 (Invalid OpCode) when I try to read the drive?
Fixed the invalid opcode ( was passing 0 instead of the context ) and put in the appropriate exception path for that too, and then fixed the general protection fault that it hit after that. I was using a ternary operator without the correct parenthesis. Instead of allocating 1024 bytes, it was allocating 2, then using 1022 bytes of other allocation's space with "predictable" results.
You can now request that the Dos layer load a file such as "Boot:test~1.lib" and it will look up "BOOT:" in the device list, find the FileSystem attached to it and tell it to open "test~1.lib", which will then use the BlockDeviceDriver in the DosDevice to read the "disk".
2010-02-20
2010-02-20 - Streams and DosDevices
Investigated streams more, and I have created a "FILE" structure that actually just creates a queue buffer similar to those I already have. It means that I can now use generic functions to interact with them, and improve their complexity later on.
Looking now at expanding the definitions of the device and file system drivers to head toward my previously designed Dos abstraction layer.
If I'm going to have to parse this mountlist in order to derive all the required information, it would make sense to implement the C library strtok function, which is what I'm doing now.
Ok, String_strtok() seems to work, and I copied the example mountlist in to test in on that. A few tweaks and I should have the routine to parse the mountlist for the devices.
Dropped strtok because it won't work in this situation. It would be valid to have no space between the name and the equals sign, which would leave us no room for the null terminator. I have instead parsed the mountlist by hand into a "sanitised" mountlist string. The sanitised string is then being parsed again and copied into the appropriate Dos device structure. Now I need to change the Library loader so that it can return a reference to the library if it is already loaded, then get the Dos system to find the library (filesystem driver, device driver) specified in the entry and initialise the device.
I've updated the Fat driver and the Ram driver to expose their interface structures with a name that won't clash with other things, and I've added them both as entries in the Kernel library so that they can be found by name when referenced by the mountlist
The Dos system is now pulling the device and the filesystem out of the mountist definition and looking them up in the library. I also have them calling the CreateContext routines and passing the definition. Now I need to get the CreateContext functions to create the appropriate context element from the settings in the mountlist.
Looking now at expanding the definitions of the device and file system drivers to head toward my previously designed Dos abstraction layer.
If I'm going to have to parse this mountlist in order to derive all the required information, it would make sense to implement the C library strtok function, which is what I'm doing now.
Ok, String_strtok() seems to work, and I copied the example mountlist in to test in on that. A few tweaks and I should have the routine to parse the mountlist for the devices.
Dropped strtok because it won't work in this situation. It would be valid to have no space between the name and the equals sign, which would leave us no room for the null terminator. I have instead parsed the mountlist by hand into a "sanitised" mountlist string. The sanitised string is then being parsed again and copied into the appropriate Dos device structure. Now I need to change the Library loader so that it can return a reference to the library if it is already loaded, then get the Dos system to find the library (filesystem driver, device driver) specified in the entry and initialise the device.
I've updated the Fat driver and the Ram driver to expose their interface structures with a name that won't clash with other things, and I've added them both as entries in the Kernel library so that they can be found by name when referenced by the mountlist
The Dos system is now pulling the device and the filesystem out of the mountist definition and looking them up in the library. I also have them calling the CreateContext routines and passing the definition. Now I need to get the CreateContext functions to create the appropriate context element from the settings in the mountlist.
2010-02-19
2010-02-19 - Streams and Lists
Ok, a few more ideas. The library loader should, could and would (will) be easily adaptable to load executables. They would be loaded into memory in exactly the same way, except instead of being linked into the library list, we just need to identify an entry point (main?), call it, then free the memory afterwards. Perhaps some investigation of an executable COFF (like how to make one with DJGPP) would be good.
Started to lay down some code for the stream. I've planned a small number of functions from the standard C library that should allow me to re-implement some of the buffers (such as the keyboard scancode, command, and video output buffers) using C standard. This should also allow the stdin, stdout and stderr streams to be passable into files which can then use them as required.
Lists have been made doubly-linked, so that items can be added to the end. They have also gained the ability to allocate "containers" to reduce memory allocations. Each list will contain a linked list of containers within it, and each container holds a header and a number of list entries. The list entries themselves are still doubly linked. Currently, each container holds 18 entries (so the total size comes in just under 256 bytes) and so that will be 18 times fewer allocations for list entries.
Time spent this evening debugging the list improvements which were programmed blind. The NextIndex wasn't being updated, and I wasn't setting the ListHead pointer in the add if it was the first element. Should implement Remove as well. The interrupt handler would benefit from this technology.
I should create a filesystem driver for Amiga OFS, and device drivers for the floppy drive. However, both of these should be delayed until I have the Dos abstraction layer in place and have settled on the basic block device and filesystem driver entry points and structures.
Ok, so I was looking at the newly working doubly linked list and decided that a bubble sort algorithm (for functionality, not efficiency) would be beneficial. A little while later, the system reminded me that I had improved the interrupt handler with a display of the registers at the time of the interrupt ... of course this meant the sort code was not 100% functional.
Success! The bubble sort on the doubly linked list is complete. A minor speed increase was gained by changing the sort so that it swapped only the values on the elements instead of the elements themselves. Now back to the streams.
Started to lay down some code for the stream. I've planned a small number of functions from the standard C library that should allow me to re-implement some of the buffers (such as the keyboard scancode, command, and video output buffers) using C standard. This should also allow the stdin, stdout and stderr streams to be passable into files which can then use them as required.
Lists have been made doubly-linked, so that items can be added to the end. They have also gained the ability to allocate "containers" to reduce memory allocations. Each list will contain a linked list of containers within it, and each container holds a header and a number of list entries. The list entries themselves are still doubly linked. Currently, each container holds 18 entries (so the total size comes in just under 256 bytes) and so that will be 18 times fewer allocations for list entries.
Time spent this evening debugging the list improvements which were programmed blind. The NextIndex wasn't being updated, and I wasn't setting the ListHead pointer in the add if it was the first element. Should implement Remove as well. The interrupt handler would benefit from this technology.
I should create a filesystem driver for Amiga OFS, and device drivers for the floppy drive. However, both of these should be delayed until I have the Dos abstraction layer in place and have settled on the basic block device and filesystem driver entry points and structures.
Ok, so I was looking at the newly working doubly linked list and decided that a bubble sort algorithm (for functionality, not efficiency) would be beneficial. A little while later, the system reminded me that I had improved the interrupt handler with a display of the registers at the time of the interrupt ... of course this meant the sort code was not 100% functional.
Success! The bubble sort on the doubly linked list is complete. A minor speed increase was gained by changing the sort so that it swapped only the values on the elements instead of the elements themselves. Now back to the streams.
2010-02-18
2010-02-18 - Library Loading
The Library Initialise routine is in place, and is exposing the String_kprintf function, brilliant, so now all I need to do is lookup that symbol and I get the routine out, so, to call Library_FindSymbol() ... oh wait ...
For historical reasons, it seems sensible to use memory address 4
For historical reasons, it seems sensible to use memory address 4
2010-02-17
2010-02-17 - Library Loading
Pah, the library loader is broken. Having determimned much more information about the COFF format (the second time around), I stated work on the Library Loader V2, and it was going well. After fixing a few little problems, it turns out the allocation is completely messed up; the data area's on the test area, and the bss is nowhere to be seen. Oh, and everything is a variable, no functions in sight. Damn!
After just writing an article about how the section table was one-based, I forgot. The symbols were looking up their sections assuming they were zero-based. This is why all the symbols were variables and not functions, and also why they were using the wrong pointer as their relative point and ending up on top of each other.
Success! The test was successful and the DEADBEEF was returned ... Now how to use this technology?
I think I need to change the Command system to use a list instead of an array, and add the ability to add commands on the fly. Modify the library initialiser to create a Kernel library with an entry point to the add command routine. Have loaded libraries auto-initialise and add commands.
After just writing an article about how the section table was one-based, I forgot. The symbols were looking up their sections assuming they were zero-based. This is why all the symbols were variables and not functions, and also why they were using the wrong pointer as their relative point and ending up on top of each other.
Success! The test was successful and the DEADBEEF was returned ... Now how to use this technology?
I think I need to change the Command system to use a list instead of an array, and add the ability to add commands on the fly. Modify the library initialiser to create a Kernel library with an entry point to the add command routine. Have loaded libraries auto-initialise and add commands.
2010-02-16
2010-02-16 - Atomicity So Far
Kernel codenamed "Atomicity".
Current situation:
Plans
Current situation:
- The kernel is still monolithic and being delivered over PXE.
- No streams yet, although they have been planned.
- Process code is in this kernel, and has been working, but is currently disconnected.
- The List code is singly-linked and works a treat.
- The Fat driver is working well after some teething troubles (the sector pointer wasn't advancing)
- The block device is currently a RAM drive pointing to an image being loaded after the kernel.
- Focus has moved away from the FAT driver.
- Focus has moved toward the library loader to again attempt to break out of monolithicism.
Plans
- Change the List to be a doubly-linked list
- Implement stream functions
Subscribe to:
Posts (Atom)