Month: July 2015

It’s all about the compiler

Welcome back!

This week our focus was on the FlingOS compiler. We started with an introduction to the compilation process and the compiler itself. We also looked at the CI20 board and booted it up to observe its capabilities of running a full scale Linux operating system on it. This was very exciting!

Introduction to the compiler

I had spent some time learning how the intermediate language generated by MSBuild is translated into architecture specific assembly, especially how calls to methods are handled during this translation. I have observed the output of simple methods, such as adding two integers or displaying colour and text on screen for this purpose. I learned that understanding this process in the context of stack operations is particularly important, such as how arguments to methods and local variables are handled as well as how return values are passed back to the caller and how space is allocated for those return values.

After this introductory session, we jumped right into development tasks. This was related to shifting some architecture specific parts of the compiler into the x86 target architecture library. I learned that it is not desired to have a compiler which is architecture dependent because you may want to compile to different architectures using the same compiler. A generic compiler will make life easier when we port FlingOS onto MIPS.

Making a generic compiler

The task of shifting assembly generation from the compiler to the x86 architecture library has proven to be more difficult than I expected. I realised that I did not have the necessary insight into how the compiler functions at deeper levels. However, with some help from Ed, I was able to complete the tasks. As it turned out, I wasn’t actually that far off from the correct solution. Nevertheless, I felt that I was thrown in at the deep end, and since I almost drowned, Ed decided that I should spend some more time studying the compiler in more detail. He kindly produced a document explaining the structure of the compiler and how the different classes and methods are involved in the compilation process. I have been studying this document along with the code itself to gain a better understanding. By the end of the week, the compiler has been changed to a fully generic version and the MIPS target architecture library has been also added to the project by Ed. Although the actual implementations are yet to be completed in the coming weeks.

Plans for Week 4

Next week, I am going to be continuing to solidify my knowledge of the compiler and soon we will begin working on porting FlingOS onto the MIPS architecture.

See you all next week.

Roland

The future’s so bright, I gotta wear shades…

Welcome back to my weekly update on my journey through the wilderness of OS development.

I’ve had a very enjoyable and productive week. I am still in the training phase of my internship but I can tell you now, within a few weeks, once I know enough about FlingOS, even more exciting things are going to be happening. Before I reveal more, let’s see what we’ve done this week.

Assembly to C

We have started the week by converting blocks of assembly code into C for the purposes of the upcoming tutorials in the context of memory and interrupts. The reason for this is that in the tutorial videos, equivalent implementations of the different development phases will be provided in three different languages; assembly, C and C#. This will be useful in seeing how each steps can be developed using the different languages, therefore you can decide which implementation suits your needs best.

We started by setting up the page directory and the page tables for the purposes of virtual memory management. Once that was achieved (after some frustration with pointers on my part) we set up memory to contain the kernel in the higher-half of the virtual memory space. This has advantages later when multiprocessing is desired. I learned about how to combine C code with assembly by the use of global procedures and data types as well as how one can use inline assembly to inject machine code directly into a C program. Mixing C with assembly can be useful as the implementation of certain tasks can be more straightforward in a high-level language. We have also spent some time setting up the Interrupt Descriptor Table entries in C. By working on this task with Ed, I learned, amongst other things, that the programmer can specify custom bit sizes for data types by using bitfield operators.

Getting to grips with C#

The second half of this week was spent on familiarising myself with C#. For this purpose, I have been looking at online tutorials on TutorialsPoint and on the Microsoft Developer Network site. I enjoyed learning about C#. It seems like a cool language to learn. I particularly like the documentation comment feature of the language. I think it’s very neat that you can leave comments in your code which then can be compiled into professional looking XML documentation resources. I also like the fact that C# is a type-safe language, so no need for pointers (yay from me). On the other hand, if you need to use pointers, you can declare “unsafe” blocks in your code where you can make use of them.

Plans for next week

Next week, I am going to be learning about the structure of the FlingOS compiler. I will be familiarising myself with the internal workings of the compiler by tweaking different parts of it and observing the output it produces. I will be able to put my newly found C# knowledge into good use since the compiler is written in this language. I will also be looking into how the compiler translates C# code into Intermediate Language code and how that IL code is translated into machine instructions. I am looking forward to tweaking the compiler to learn more about FlingOS and its internal workings. So, back to the exciting things I mentioned at the beginning of the post!

“Things are going great, and they’re only getting better”

Within the next few weeks, we are hoping to get started with porting a scaled down version of FlingOS onto our sponsor’s Creator CI20 development board. This means the translation of the existing x86 based code into code suitable for the MIPS32 architecture. A large part of the translation process involves converting CISC assembly instructions (x86) to RISC machine code used by MIPS32. Porting FlingOS onto the Ci20 board will be an exciting challenge and I will provide you with the details once we get started so you can consider developing your own OS on this great piece of kit.

That’s it from me, please come back next week for more info.

Roland

My first week as an intern!

This is the first of the weekly posts I am going to be sharing with you about my experience working with Ed during the 9 weeks of my summer internship. I will try to post as frequently as possible but I will produce a post at least once a week to let you know about the progress I make and the plans we have for the coming weeks. Before I say more about how the first week of my first ever internship has been, I thought I’ll introduce myself and my background (only briefly).

Introduction

I was born in Hungary where I spent the first 19 years of my life living in Budapest. It is a great city to visit and there is a lot more to it than just eating Goulash :). In 2005, after finishing secondary education in Hungary I moved to the UK to learn English. I always wanted to study at university but as a 19 year old guy in a new country enjoying his freedom and doing what most 19 year olds want to do, I did not think much about going back to school. After some years working in a restaurant I realised that something was missing from my life, so I decided that I will pursue my childhood interest (which is, of course, computers). So I went to college to gain an IT Diploma after which I faced the biggest challenge of my life, studying computer science at university level. So here I am, a student at the University of Bristol starting my third year in September. Never been happier (and more exhausted)!

Never been happier (and more exhausted)!

My first week

These first few days with FlingOS have been very exciting. In only four days, I learned more about operating systems development than I did in my entire life. We covered topics, such as Booting, Initialisation, Memory Management and Interrupts. We have started to produce resources for the tutorial videos and articles which are planned to be released by the end of the summer so you can have a go at developing your own operating system as well. Producing the resources for the tutorials is a great way for me to learn about OS development. Most of the implementations we looked at are done in assembly language with which I’ve had some experience from previous university courseworks but definitely not at this level. Learning more about how to program in assembly is a great way of realising how the actual hardware works and how the computer is able to generate useful applications for the user from all those ones and zeros.

Future Plan

It is planned that I will be spending the first three weeks of the internship learning about FlingOS and OS development in general, mainly focusing on the x86 architecture on which FlingOS is based. At the end of the three week training period we will have the scripts with all the resources (code snippets, diagrams) ready so the production of the tutorial videos can be under way. The remaining six weeks will be spent on the development of FlingOS, more specifically writing device drivers using C#. I am really looking forward to the coming weeks to learn more from Ed and to make contributions to the project.

I would like to end this week’s post with a thank you to Ed for giving me the opportunity and taking me on-board, also a huge thanks to Imagination Technologies^® for supporting the project and making this internship possible for me.

See you very soon and please check back for updates…
Roland

Poor Design: A subjective statement

60 lines of code changed. 100 times faster.

By changing just 50 lines of code, I was able to make FlingOS™ read files from a FAT file system 64 times faster. Add just ten more lines and reading files from FAT on a USB stick is up to 100 times faster. But how can such small changes lead to such a large increase?

Progression: From good design to better design

The simple answer is: poor design. FlingOS is designed to be easy to understand both in terms of reading the code and in terms of overall structure and control flows. Unfortunately, this can lead to massive inefficiencies. FAT file systems, USB Mass Storage devices and EHCI Controllers are by no means simple, so writing clean code is difficult. Furthermore, writing code you can just jump-into without knowing the rest of the system is even harder. But that is what I have attempted with FlingOS (and hopefully achieved). So how can I call my original code both a poor design and a good design?

When I was first writing the code for USB Mass Storage devices, I decided that reading one sector was easier than multiple sectors. So I implemented the basic code for reading a single sector and that was that. Originally, therefore, the design was very good for simplicity and readability – the key things which make code understandable. But from a performance view it was highly inefficient (for both hardware and software). From one perspective my original design was good and from the other it was poor.

As the features of FlingOS have expanded (conforming to standards along the way), the underlying USB code has become capable of reading multiple sectors in a single request. The USB code has grown somewhat in complexity (by necessity) but remains understandable. With the new capability of reading multiple sectors all at once, suddenly my original design looks poor from both perspectives. Because reading one sector at a time makes no sense if you can just as easily read many at once. This reduces how easy the USB Mass Storage code is to understand because it adds a layer of confusion. As a result, it has become necessary to updater the USB MSD driver code.

But what about reading files from FAT? For that, FlingOS uses the FATFileStream class. Again, this is a story of progression. It started (and remained for a long time) totally simple. It just read one cluster at a time till it had read all the data that was requested. This was largely because reading multiple sectors at a time wasn’t supported by the underlying device drivers, so it was pointless to request more than one cluster at a time. But since the underlying device drivers (the USB Mass Storage driver, PATA driver and PATAPI driver) all now supported multiple-sector reads, why not? In fact, you can increase read speed by requesting as many contiguous clusters as possible. The algorithm for doing so is actually just as easy to understand as reading one sector at a time.

Today, therefore, I finally implemented the USB MSD multiple sector read and FAT File Stream multiple cluster read. It changed just 60 lines of code to utilise the new, underlying features. The result? Up to 64 (contiguous) clusters can be read at once and there’s no specific software cap on number of sectors to read at once. The overall effect of which is the code runs around 100 times faster (over small files. Possibly even faster for large ones due to other factors). This makes drivers loaded from a USB stick much more viable (which is what FlingOS is currently working towards).

Judging a design

So I’d like to leave you with this:

Calling code “bad” or “good” are highly subjective judgements.

You may call one piece of code very poor. Someone else may say it’s the best in the world. It all depends on how you’re judging it – be that by performance, readability, memory efficiency (which itself has many factors), lines-of-code used (ugh…) or any other measurement you care to make. All code will compromise (or excel) at something; you just have to work out what. When you’re judging someone’s code (even your own), remember to state what factors you took into consideration. What was your perspective.

The bug that went undetected for over a year…

Yesterday I announced that:

Just fixed a bug which has existed since the first week that I wrote FlingOS – so excited!!

I promised a blog post would follow, so here is that blog post – it’s going to be a good one. So sit back, relax and read on as I take you through the history of this bug.

When I first started writing FlingOS I had somewhere between no idea and less than no idea what I was doing. Seriously, all I knew was the structure of a C# to native compiler – I had worked on Cosmos for about 5 months but for various reasons I decided I wanted to write my own C# OS, with a different structure. I had my own compiler working relatively quickly and the next step was to implement basic features that would underpin the entire OS.

It’s probably reasonable to say that if something is going to underpin your entire system, you want to get it right, lest it have any nasty, invisible side effects later on. One such underpinning component was the Heap. Ahh the Heap… The heap implementation has caused much confusion and difficulty. This is not because a heap is difficult to understand or use, it’s just fiddly and crops up all over the place such that slight errors kill the entire OS. Some such errors have included not using spin locks (after I introduced multi-threading a few months back) and not allocating the heap enough space. (The heap space use to be allocated in the .TEXT section of the code! 120MiB .ISO files ;D With the new drivers compiler I shifted it to .BSS where it should be.)

When I first looked at implementing a heap, I wasn’t too interested in the internal workings. I knew what a heap did, I knew there were lots of ways of implementing them, each with pros and cons. I just wanted something simple and easy that I could use. Of course, FlingOS being one of only three active C# operating systems worldwide, there aren’t many (if any) suitable heap implementations floating around. However, there are lots of samples in C. The one I lumped for was a simple one from OSDev.

Over time I have adapted and updated the implementation to add things like allocation on or avoiding a boundary (as required by USB). The main Alloc function, however, has remained the same. Entirely the same. And this is where the issue lies. Early on in my development I found that with a 10MiB heap, my OS regularly seemed to run out of allocatable memory resulting in seemingly random page faults. My somewhat ignorant solution at the time was? : Make the heap 100MiB! This seemed to fix the problem, even though 90% of the heap was never allocated.

As time has gone on, page faults have appeared and disappeared sporadically until recently when I started trying to read large files from USB sticks. This used a lot of heap memory and suddenly the page faults were happening all the time. Not having really had to deal with page faults before I had no idea what was causing it. My instinct said that a page fault is due to unmapped memory, so something must be allocating an invalid pointer. But the heap wasn’t anywhere near out of memory. Unfortunately, with so many compiler changes going on in the past few months, there was no consistency to the issue. Even in the past few days the faulting address (or even instruction address) was not reproducible. It was seemingly random.

I investigated everything from interrupts to memory leaks to who knows what trying to trace this. Eventually I realised I wasn’t going to be able to unless I had a better view of two things:

The sequence of events which lead to the page fault (and subsequent crash)
The layout of all memory so I could see where things might be going wrong

For point (1) I had previously just outputted stuff to the screen through FlingOS’s BasicConsole class. But this wasn’t enough. I needed traceability and the ability to go back more than a screen’s worth of information. So I implemented a new Serial class and hooked into the BasicConsole to redirect the output to a file on my host machine. As it turns out, I never needed to implement anything for point (2) – I realised what was going on before I got that far.

I realised the issue was to do with USB code, so I turned on all the trace code for the USB stack and inspected the output. The output contained the key piece of information : virtual and physical addresses of the memory the heap was allocating. They were invalid. They were valid addresses, but they didn’t fit inside the heap’s allotted block of memory! They were overrunning the end of the heap. I’d found my one, consistent piece of information.

Naturally I went looking for what could be overwritten by code writing to space beyond the end of the heap. Sure enough, immediately the heap memory were the unprotected page tables. And because USB uses physical addresses, there was no way I could have protected the page tables. I tested by allocating padding space between the page tables and the heap – sure enough the code took far longer to crash.

So the issue was in the heap. But the OSDev implementation looked pretty solid and many people had tested it. So I must’ve converted the code incorrectly to C#. In the 18 months I’ve been doing low-level programming my understanding of pointers and pointer manipulation has grown – a lot. I went back to look at the heap in detail and found this spurious line of code:

void* result = (void*)(x * b->bsize + (UInt32*)(&b[1]));

This line of code is supposed to calculate the address of a block (x) with block size (b->bsize) and offset from the start of the heap (&b[1]). For those who understand pointer arithmetic they will easily see my mistake from when I converted the code – UInt32* will result in the pointer being multiplied by 4 (because UInt32 is 4 bytes in size). In my defence, however, the original line of code was thus:

return (void*)(x * b->bsize + (uintptr)&b[1]);

I asked a number of experienced programmers what they would expect uintptr to be a type for and all but one said: pointer to a uint (i.e. UInt32*). Only one was able to give me the actual definition (as per C99, which I found online) which is:

In C99, uintptr is “an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer”.

Great…so uintptr is not UInt32* it is in fact just UInt32 in C#.

Here’s a few caveats for those pedantic types amongst you:

Yes, pointers can be 8, 16, 32 or 64-bit. So it shouldn’t be UInt32 it should be some other form of UInt that allows agnostic size. However, FlingOS is entirely a 32-bit OS and C# doesn’t have a useful equivalent for uintptr (see next point).
Yes, C# has an IntPtr type – but it is intended for managed pointers and doesn’t play easily with most of the low-level code I’m trying to write for FlingOS. I may start using it in future, I may not. It might need some compiler updates to support it.

Detecting ATAPI drives

In the past few days I’ve been tackling a problem I’ve had for a while now – how to make ATAPI detection and retrieving device information reliable. I found that if I confined myself to a virtual machine then the existing code was pretty stable. However, with the large range of real-hardware I now have available to me, “it works in a VM” just wasn’t satisfactory. So I started testing and researching.

What I found was that I could reliably detect CD / DVD drives on all hardware. However, almost completely consistently, issuing the Device Identify Packet command resulted in the error bit being set. Yet my code worked exactly the same as many other people’s online examples. I reached the following conclusions:

My code wasn’t doing something properly. It must be missing a step that would allow the ATAPI disc to respond properly.
Other people’s code clearly hadn’t been tested on real hardware. There were various other indications of this which I won’t go into detail about here.

What I realised, however, was that once an ATA device has reported an error, it does not clear the error flag until you send it a new command. I also noted that part of the process of detecting an ATAPI disc, involves issuing the Identify command and then checking various registers to look for the PATAPI/SATA/SATAPI signatures. You check for the signatures even if the device reports an error.

So what was happening was some devices flagged up an error for the Identify command and some didn’t. The ones which did, required an additional command to be sent prior to the Identify Device Packet command otherwise it would still report an error. I went looking for a reset command and found one. Technically it only affects PATA/SATA not PATAPI/SATAPI devices. However, because it reset everything on the bus, and ATAPI devices have to be ATA responsive, ATAPI devices count this as a command. Thus issuing the Reset command clears the error flag. The problem was solved 🙂

Head over to this file on my dev branch in FlingOS’s BitBucket repository for sample Reset method code and usage.

Apply now for a sneak-preview of the tutorials…

The tutorial scripts are written and the resources are coming along nicely! FlingOS is about to enter the recording stage for its upcoming tutorial video series but if you’re excited to learn OS dev today, you can apply for a sneak-preview of the scripts! All we ask in return is that you provide some useful feedback on style, content coverage and perhaps the odd grammatical error too. Apply today by commenting below or emailing flingos@outlook.com or post on our Facebook page.