My internship: the experience and achievements

In this last post of the summer, which also marks the end of my summer internship, I would like to write a bit about my experience working for FlingOS™. Also, I would like to give you a summary of what has been achieved in the last nine weeks.

The experience

The internship has been a great experience. I have learnt a great deal about the x86 and MIPS32 processor architectures. Learning about these two very different designs alongside each other was truly valuable in recognising the merits of each approach and in learning about low-level development in general. Working on the IL to assembly conversion was fairly challenging but nevertheless fun. I also had a chance at writing and debugging substantial amounts of assembly code, which definitely worth the effort. Using Visual Studio and C# has given me a valuable experience in using the .NET framework as well. The internship provided me with skills I wouldn’t have learnt on my undergraduate course because most of the topics we covered during the summer are either not included or not discussed in such detail. So overall the experience with FlingOS™ has been a great addition to my studies. Although I was slightly intimidated by the amount of new information at the start, I think I managed to do well, with thanks to Ed for his patience and good teaching skills.

Achievements

During my internship, I helped to produce the resources for the upcoming tutorials, we achieved compiler support for MIPS and an extensive verification kernel has been created. The new kernel turned out to be very useful as we uncovered some errors from earlier implementations that caused problems in the compiler. The testing kernel, on which we have been working the last three weeks, has been a supreme success. It was great to see that the implementations worked as intended and also to detect a few corner-case bugs. To sum up, we not only have achieved what we have set out to do at the beginning but were also able to produce the verification kernel, which will definitely help future developments and improve the stability of FlingOS™.

Future plans

This week, my summer internship has come to an end, however, this does not mean farewell. Our plan is that I will continue to work for the project, during the coming academic year, as much as possible. I will also try and post here frequently to keep you up-to-date on what is happening here at FlingOS™, so you will definitely be seeing me around in the future.

Thank you for your interest in the project and thank you FlingOS™ for the great experience, it has been a great summer.

See you soon…

Roland

MIPS compiler support completed

For the last three weeks, we have been working towards completing the MIPS target architecture library. Finally this week, all the IL to ASM conversions have been added to the compiler. The implementations have been tested and we can confirm that we have compiler support for the MIPS32 processor architecture. So how did the testing go?

Testing

Some operations are fairly simple to test along the way, such as Add, Sub, Mul, Div, Shl etc., i.e. operations that use value types, since all we need to check is the result produced by a particular IL operation. The correctness of these operations can easily be verified without the need for a complete library. This is not the case for more complex operations, such as the ones related to objects, arrays and strings, i.e. reference types.

In order to check whether reference types function correctly, many different IL operations have to be implemented (NewObj, InitObj, Ldobj, Isinst etc), so we did not start testing these until the whole library was completed. The functionality of objects can be tested by creating a test class with some methods and fields within it. If these types initialise as expected then we can try to create a new instance of the class. If all these have been a success then we can test whether values passed to the class from outside return to the calling environment correctly. The testing of arrays and strings is a little more straight forward. In order to test arrays and strings, we can try to declare a new instance of these types and apply some basic array or string related manipulation to them and inspect the results.

During the testing process, some issues were uncovered. These issues were mainly related to the differences between the x86 and the MIPS architectures. On MIPS, only values contained in registers can be pushed onto the stack, while x86 lets the programmer push labels and immediate values directly, this is not available on MIPS acheter viagra en pharmacie sans ordonnance. This is due to the CISC vs RISC architecture differences between x86 and MIPS. On MIPS, if we want to push a label onto the stack, we must first load the address of that label into a register, using the La instruction and then push that value from the register onto the stack. The same is true for immediate values; first we must move the value into a register then finally push that register onto the stack.

In many cases it is required to push the value zero onto the stack, but to do this we do not need to move zero to a general purpose register because MIPS has a $zero register which is fixed to the value zero. On MIPS there isn’t a Push or Pop assembly instruction as on x86, we need to simulate these operations with store/load instructions followed by adding to the stack pointer register using the Addi instruction.

There is another important thing to keep in mind when programming on MIPS. Data stored in memory must be aligned in such a way that an object’s address must start at a value that is some multiple of their own size in bytes, e.g. a 4-byte word must be 4-byte aligned but a single byte needs no alignment (a.k.a. single byte alignment). So if we want to load from/store to memory using an offset, we need to either make sure the data is aligned or access the data in multiple parts to avoid the alignment issues.

We never need to worry about this when accessing the stack through $sp or $fp since the compiler guarantees these are always 4-byte aligned. For other memory accesses, the FlingOS Compiler does not require memory to be aligned (for compatibility with other architectures). Instead, it uses runtime checks to load memory from or store memory to unaligned addresses. This means C# code can be written more generically, with less for the programmer to worry about but does create a small performance hit at runtime.

What’s next?

What we would like to do during the remainder of this summer is to add a unit testing framework to the project that formalises test cases for current and possible future architectures. This way we can ensure that the current supports for x86 and MIPS are stable and also, if the project is to be extended with a new target architecture library, then implementing that library can be done in an efficient way which is easily testable.

Thank you for reading this and if you are interested in the upcoming Launch Event then please subscribe on the FlingOS homepage.

See you soon…

Roland

Left shifting 64-bit values using 32-bit registers

Yesterday, while working on the implementation of the left shift IL operation (shl) for MIPS, we came across some challenges related to shifting 64-bit values using 32-bit registers. The solution is a bit tricky, so we thought it would be useful if I produced an article discussing how it can be done.

In order to shift a string of bits, we need two operands; the data itself and a value specifying the distance we want the data to be shifted. The shift value can either be a constant or a value stored in a register. Although in this article we assume that the values are in registers, the same technique can be adapted to be used with the assembly instructions that use constant values. There are four different cases we need to consider in terms of operand sizes:

  • 4-byte data, 4-byte shift value,
  • 4-byte data, 8-byte shift value (this is unsupported by C#),
  • 8-byte data, 4-byte shift value,
  • 8-byte data, 8-byte shift value.

The 4-8 case is unsupported by C#, so in this scenario the compiler throws an exception. The 4-4 case uses a single left shift assembly instruction (sllv) so there isn’t much explanation needed there.

8 – 4 case

In the 8-4 case, the 8-byte sized data is shifted by a value that is represented by a 4-byte binary number. Since we only have 32-bit (4-byte) registers, we need to store the data in two separate registers. One register contains the low bytes ($t0) while the other contains the high bytes ($t1). In this example, I store the shift value in $t2.

1

2

Consider a 1-byte left shift, i.e. $t2 contains the value of 8. Now we have a problem because the top byte of $t0 must replace the bottom byte of $t1 as well as the rest of the data must be shifted correctly. So how do we shift an 8-byte value using 4-byte registers? I will show you how by going through some examples. There are two variations of the 8-4 case; one where $t2 < 32 and another where $t2 >= 32.

The method ($t2 < 32)

Let’s say we want to left shift this data by 1 byte (1 byte can be represented by two hexadecimal digits):

3

Somehow we want the result to end up looking like this:

4

1.      Left shift high bytes by $t2

First, we want to left shift the high 4 bytes ($t1) of the original data by the value carried by $t2, which is 1-byte. The low 4 bytes remain unchanged for now. So we have:

5

2.      Right shift low bytes by (32 – $t2) into temporary

The next step is to logical right shift (not arithmetic right shift!) $t0 by (32 – $t2) into a register which we will use as a temporary storage, say $t4. Since $t2’s value in bits is 8, we right shift $t0 by 24 into $t4. This way we get the proportion of $t0 which we then want to copy into $t1. $t0 and $t1 remain unchanged at this point.

6

 

3.      OR temporary with high bytes

Here we can combine $t1 and $t4 using the logical OR operation to get the correct result for the high 4 bytes which we store back to $t1.

7

 

4.      Left shift low bytes by $t2

There is only one thing to do, left shifting the low 4 bytes ($t0) by $t2.

 

8

Now the algorithm is complete. If we compare this result with the desired result above, we can see that they are identical.

The method ($t2 >= 32)

If $t2 >= 32 then we are left shifting the data by 32 or more bits which means that the least significant bit (little endian) of the data is pushed beyond the low bytes into the high bytes. In all cases where the shift value is greater than or equal to 32, $t0 ends up filled with zeros and the content of $t1 are lost completely. But in what form does $t0 take over $t1? Let me show you step-by-step as before. Now let’s assume that we are left shifting by 40 bits and we have the same original data as before.

 

3

But this time we want the result to be this:

9

 

1.      Move low bytes into high bytes

We copy the contents of the low bytes into the high bytes. We do this to save the contents of $t0 into $t1. The original data becomes:

10

 

2.      Fill low bytes with zeros

Since the data is pushed all the way beyond the low bytes, we can fill the $t0 with zeros.

11

 

3.      Left shift high bytes by ($t2 – 32)

The final step is to left shift $t1 by ($t2 – 32) which is 8 in our case. So the desired result is achieved as expected.

12

 8 – 8 case

In the 8-8 case, both the data and the shift values are 8 bytes in size. There is one important observation we must make; shifting a 64-bit value by 64 bits or more is pointless since the result will always be zero. We also know that the number 64 is represented by this binary number: 0b0100 0000 which can easily be contained in the low bytes of the shift value ($t2). Actually any non-zero value beyond the 6th bit would yield a zero result but let’s just consider 4 bytes to be the smallest size we can manage.

 1 

13

To conclude, if $t3 is non-zero then the result of the left shift will definitely be zero, while if $t3 is zero then we can proceed the same way as in the 8-4 case by simply ignoring $t3.

I hope you found this article helpful. Please leave a comment if you think I missed something or if you have anything to add and I will do my best to respond.

See you around.

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