Bank holiday, Again!

These UK bank holidays are really nice. Its the third one this year, and I'll make the best out of it. Today (Saturday) I've finished reading SLOS and the GNU As manual. The manual itself is 250 pages, however its a manual. So I skipped all the bits unrelated to ARM, and it wasn't that long. I also went through the parts I read before. I made a sketch of the memory map of E7T, and also how SLOS uses it in the book. SLOS is very simple, just for illustrative purposes, it sets a TCB for each task, sets task stacks, installs an IRQ, a timer for preemptive scheduler (being reminded of how simple this is, its amazing how a big company like Apple managed a cooperative scheduler so long) and that's more or less it. The tasks are static, and linked with the OS, which itself only merely exists.

I feel more competent now with binaries, loading the interrupt handler etc. My intention is to get more familiar with assembly using GAs, and practice a bit on OS implementation. So I am going to write something like SLOS, but with a default prompt through UART, and tasks will be loaded (well merely copied as is) from flash into SRAM. I will also have a simple malloc, statically linked in to tasks. Lets see how it goes.

NetBSD and L4 built

Today (well 5 minutes ago), I built both NetBSD2.0 and L4::Pistachio 0.4 kernels on my AMD64-linux host. It was suprisingly easy, as I had no errors, and I didn't prepare a toolchain or anyhting. Well, I had an arm-elf and arm-none-eabi toolchains ready, but chances were that I had to set a CC variable etc. but I didn't. NetBSD built its own arm-netbsd-elf toolchain in the first place. I think its the courtesy of NetBSD people who did the build system such that it built with no hassles. I'm not that suprised with L4 as its just 10,000 lines of code anyway.

Now two lucky things for me: The first is that NetBSD supports Integrator platform. Its lucky because I have a much easier task now to try and enhance the support. The second good thing is that L4 supports ARM926EJS. This is also very nice, because I'm not going to have to set up a VM system from scratch. This would have been difficult since I never wrote/implemented code that uses VM and caches. So it's easy to learn from a readily-made, yet simple and compact example such as L4.

3rd thing today: I found out about Greg-KH's blog. Its interesting reading. What I like about him is that he doesn't seem to be arrogant, he answers questions in kernelnewbies and spends his time answering new starters. He answered back to me twice too.

Second best thing

It was not until last year that I have discovered reading books is the ultimate way to learn things fast. If you don't read, you can't know, and if you don't know, it looks difficult. From then on I am on a reading frenzy. This helped quite a lot and I read books/papers mainly on C programming, CPU architectures, and FPGAs. End of last year I could read a bit of OS books.

It was also last year that I discovered things aren't as difficult as they seemed. If you don't know, it looks difficult. But it actually isn't, after you understand it. Maybe its complicated/detailed, but its not "that clever" as it seemed. If you have a certain level of understanding things, its your short term memory that is the limiting factor, not how cleverly things are designed. In fact, the more complicated a design is, the less well-designed it is. Anyway, this is a topic of another post maybe.

Now I think apart from learning by reading, one other thing that helps a lot is to ask questions. Even if you're going to look stupid with your question, you should ask it. You should ask and ask, in various subjects in various mailing lists - just make good use of your question asking bandwidth. A Chinese phrase: "If you ask, you're stupid for once, if you don't, you're stupid forever." I think its very true. The 20 unknown things you asked this month won't bother your mind the next month and the one after. Its really a relief. I think I look fairly stupid when I ask various simple things that simply don't make sense for me. It has happened many times, and I used to be conservative in asking such questions, but I really don't care anymore and shouldn't. What matters is that you _learn_.

Dijkstra's paper and XVPI

1)I read dijkstra's paper mentioned in a previous post. Its amazing that serious projects such as OS360 had no notion of protection from race conditions. Its also amazing that people of the time had no mathematical solution to concurrency, and they were solving racing conditions by accurately timing the tasks and debugging the designs depending on the timing of events.

2) Now that I got a bit more beefy in device drivers and hardware peripherals, I came back to the original idea of harnessing an FPGA under a driver. Yesterday I read the paper I wrote last year on runtime reconfiguration. What I wrote now makes more sense. I read a few papers that I read last year to write my paper, they also make more sense, now that I know more on devices and their drivers. In a nutshell, a Virtex Device is configured using a bunch of pins. Xilinx Virtex Portable Interface is an API written in C that's built around a single register that maps those pins. And XHWIF is a layer on top of XVPI. That's it. So what I needed to know here was how to get a well defined FPGA run-time reconfiguration interface (via a set of registers as in USB or EHCI). I wanted it because the registers of a device is the best interface a C programmer can get for a device. So XVPI already does this. Glad I learned that. Last year I wasn't very aware of how XHWIF would work, as I didn't have any experience in real code that does the work. Now that at least I can have a first go at it.

Graduation

This wednesday was my graduation ceremony. Royal Albert Hall was full of graduates in London. It was an interesting afternoon. After the ceremony I went on a vacation for 3 days with my mother. On the way through the Portsmouth - Brighton - London triangle, I had occasional breaks to do some reading.

Maintanence of OS configurability is fairly important, especially in an embedded system where high configurabiity is necessary. This further reflects into performance/size and correctness. The way L4 source base handles this is that, it is divided into several conceptual dimensions, such as the architecture, the api used etc. L4 source base is seperated into various files depending on these differentiating dimensions, and the build system can pick appropriate member functions of objects depending on these dimensional variables. However this produces duplicates in these seperated files if there are common functions/fields for all architectures. Another approach to this is to use preoprocessor help as in eCos. But this makes the code significantly harder to follow, and also one must take care of 2^hundreds of compiled combinations of code. I think this will be the biggest trouble eCos developers will face as the time goes by. So what they experiment in L4 is MI + class flattening to get rid of virtual function overheads. By MI all these dimensions are represented in class-level, and thus the job is left to the compiler rather than makefiles. In my opinion MI would solve lots of issues in the code complexity, because the compiler works much more succinctly and precisely compared to a build script, but I'm not sure if class flattening would be the ultimate solution for vtables. There must be a solution though, as noone would want maintainable but slow code (well, I wouldn't at least). I'll look into that later. Configurability interests me a big deal, and I think one must see the eCos build process to see the point. The post I meant to make quite short has in fact become one of the longest.

OS Review Vol 39, Number 2

Today I received Operating Systems review Vol39, No2. I took off the plastic wrapper, and one title that caught my attention was "My recollections of OS design" by E.W. Dijkstra in the cover page. I opened a random page in the booklet, and I was surprised by the pages and pages of handwriting included. One expects articles with the usual abstract, introduction, conclusion etc. you know. It always has been so. But this one is like an essay by a high-school student. Of course it was this article I mentioned, by Dijkstra. If I had contributed so many things to computer science as him, I would have also published such a stylish article on ACM OS Review.

But anyways, this just reminded me that I really need to read the CSP book by Tony Hoare. I know about locks semaphores etc. but I still don't have a mathematical background on concurrency and its time to learn it from experts. Also I remember that about Tony Hoare's work, my supervisor said to me one day - well here's what he said, I quote it from an email: "Interestingly I went to the conference dinner last night of a two-day event to honour Prof Tony Hoare and the 25 year history of his CSP theory, and its use in the development of the occam language and the transputer. This was an attempt (probably 25 years ahead of its time) to put embedded systems onto a scientific basis. There is a bit of me that believes that there is hope that some of this work will be taken up again, but what I mostly see is embedded people making exactly the same mistakes that the mainstream computer folks made decades before, and not learning from the experience of others."

So, I should learn from the experience of others, and to do that, first understand the CSP. I'm sure there's a lot to adopt from it for a microkernel project such as L4.

L4 - 2

I got the L4 0.4 sources. It doesn't look like aggressive C++. In fact its fairly light C++, with some bits in C, and assembly.

The most important thing about it for me is that, it's a micro-kernel architecture that has a managable size code-base for reading/understanding, it's already ported to ARM, already implements FASS, and its designed well after Mach and derivatives.

I was thinking that OSX would be good example for me after linux, since it includes features from both FreeBSD and Mach, and its a re-engineered, re-designed version. However if I'm to be rational, it wouldn't form a good initial base for me to start. It's probably too big to handle in a short time, and I would most likely get lost in the details. Also porting it to ARM or things like that would be pointless, let alone the fact that most low-level code is PowerPC specific.

I shouldn't touch this issue because I haven't read enough to compare the two yet, but probably L4's design is superior to Mach, as it's a 2nd generation micro-kernel design that started from the failings of Mach and the like.

Conclusion: L4 seems to be the best place to start to play with.

Anyways, I read the GAS manual today to get started with assembler directives etc. It covers quite a bit on ld too! Its nice that you can control the linking process a big deal from the assembler.

L4

I just checked L4 again, and remembered why I had a quick look at it before but left it without any further investigation. It has a fast IPC within 100-300 cycles, and "clean design". One idea I liked is a special page that maps all system calls such that you don't depend on sys-call offsets, where linker support comes in. I'm not sure how it works yet, so I'll find out. Yes, the downside of L4 is that its fully written in C++ and CORBA IDL. I'm not very inclined on IDL and CORBA, if not C++. Eric Raymonds' "The Art of UNIX Programming" adds to that of course. KDE is one project that abandoned IDL stuff due to complexity of management. I'm not sure about what went on with KDE as I really dislike it and don't care much about it.

Also I checked NYU research on OS, and a teacher there, is working on C extensions, which is what I'm more inclined to. C really lacks certain construct supports, one of which being "foreach" and you can encounter lots more issues in the linux kernel. Also various safety and cleanliness features can be added without introducing any language run-time.

How should I experience kernels

Today I had lunch with Philippe. He told me that L4 has a good, clean design, and many OS'es that are advertised as micro-kernels are actually not so. I'm into micro-kernels and I will have a look at L4 soon. So far I couldn't find the best way to experience a kernel. The thing is I can't, and actually don't want to try booting NetBSD, OpenBSD etc. on my host PC for that. It was my earlier intention. I haven't been able to do it so far due to time/hassle issues, but now I think that its also pointless. What am I going to run on my AMD64 with the usual PC motherboard, PCI bridge etc. it's irrelevant. I have Linux for that already. It's not gonna give me any broad perspective about the kernel itself. Instead, I think I should get a decent cross-toolchain, compile and try to run them on ARM directly. But before that I need to get more experienced on porting/booting Linux with ICE aid first.

Remote-gdb/ld/gas/elf/loading

Today the weather was well-dodgy, but interesting to observe. The rain clouds were coming and leaving one by one and it was sunny/raining in every 10 minutes or so.

I havent finished with the vector handlers. But I'm sure its not that hard once I get the big picture of everything. I set up my E7T. Compiled a few things and tried gdb in cmdline mode. I'd never tried it by commands and I should have already done it long ago. I also read a bit on memory remapping/layout in E7T, ld command switches to get a flat binary - the csdos article on flat binaries was really useful. I should have already learned the elf format and become a binutils expert, so reading on relocation and ld scripts was a good start. The plan is now to do a bit of reading on ld scripts, elf, crt0 etc. Also gas syntax, gcc constraining on inline assembler. Bill Gatliff knows everything I would want to know practically on this embedded stuff, and his website articles have the very overlapping subject headings with my learning intentions, but unfortunately they're just headings, and all are incomplete.

Today

Today after summarising my last year in the UK, I'm going to do a bit of ARM Assembly.

Nowadays my interests are in the exception vectors of the ARM processor. I am experimenting things to see it work in action. Yesterday late at work I discovered that software interrupt instructions are intercepted by the debugger if you tell it to do so (well, something not very unusual). So basically you can't see what the "real" SWI is, because all you see is a usual jump to the next instruction. Now I'm gonna change that, write a program in gnu as, that sets up stacks for all exception modes, and installs various handlers - stuff that early dos viruses did. Now, there's a linking problem here as well, you have to link each handler into a specific address, such that when the loader loads your elf image, it automatically copies the handlers to their desired addresses, and your usual main() code that sets up stacks, to a default usual program address. So this will also initiate my first tweaking with the linker. Also I'll go deeper in experimenting with readelf and objdump to see if my linking worked correctly.

First Blog

This is my first blog message. I am keeping a blog so that I can get a structured record of everything I've done in the past. I'll keep this one a bit long since it's a summary of my last year.

Currently I'm living in Cambridge, UK. Cambridge is a cute, small and boring town. Apart from work, I usually spend my time at home doing computing work, lots of reading, drinking coffee and staring at the fantastic flower garden in front of me so its not too bad.

Last year I was a graduate who had written a lot of exams; on cryptography, computer architecture(Itanium2!), prolog(I always wondered how they schedule class timetables), OOP (virtual function tables in MI, JVM execution were the only interesting bits for me) , program analysis (data flow analysis set-theory notation), parallel algorithms(thought me what scalability really is) to name a few. I had also done an independent study option on run-time reconfiguration methods of FPGAs. As a summer project I converted a C++ motion estimation algorithm into Handel-C, a C-like language my supervisor developed earlier in Oxford University Hardware Compilation group. Handel-C basically converts C constructs into hardware, so you write code with hardware awareness, pipelining etc. My version was a "debug" version of the algorithm, totally unoptimised for hardware. But it was a good start.

Now, the problem was that I had no OS design courses/reading whatsoever. Nor I had the time to do any reading on that. So, in the summer I've read Andrew Tanenbaum's OS book on and on. Again. I also had to freshen up my C skills after doing all those long Prolog assignments. It was the time that I really decided not to do anything apart from programming in C rest of my computing life. Oh, also in 24th of February, (my birthday) in the unsuccessful interview with ARM, it turned out that I really dont know much about linking. Although it seems its a dull process, I think linking is very important because it helps you understand how memory works. So as a result I've also went half-way through "Linkers and Loaders". Unfortunately its the only book that covers the topic that I'm aware of, and its such a practical topic that you feel a bit like you're lacking hands-on experience while reading it.

Finally before my employment started here, I went to Gokova in Turkey with my mother for vacation. There's a restaurant called Azmakkapi. There, the river is on your one side, the trees to your right. A cat in your lap, ducks playing in the water, delicious (as always) Turkish stir-fry in front, and hot, sunny weather with a warm breeze. In this lovely environment, I've read the initial chapters of The Design and Implementation of 4.4BSD Operating System. It started to make sense. I began reading that book because I thought its the most reasonable Unix OS book to read after reading Tanenbaum's one. So that's how my last year ended.