Jiri's allegedly HelenOS blog

TCP... the truth will be revealed

2011-11-23T08:03:00.000+01:00

I have long before recognized that the current network stack in HelenOS is messed up beyond repair and trying to fix it anymore is a waste of time. Since it's been two years after the master thesis was defended and we still do not have something that would work, it might not be well received by others if I threw everything out and started from zero, though.

So I started with a complete rewrite of TCP. This is arguably the only more complex / non-trivial module in the stack and the part that is obviously most broken.

Despite lack of spare time I have now a new TCP module that is not 100% complete, but complete enough so that it could be test-run against itself over the wire. I implemented it as a completely independent server that has nothing in common with the current networking stack. I tested the functionality using internal loopback in the TCP module and internal clients.

Yesterday I started hooking it into the current network stack, the idea is to create a minimal connector between the two components. After three hours of work there is still some way to go before I can successfully send/receive PDUs to/from IP (I haven't started with the socket interface yet).

During this work I had the chance to fully 'appreciate' the quirks and complexities of the network stack. IP understands sockets and TCP pseudo headers. TCP knows about IP headers and network devices. But who cares about layers or separation of concerns, right?

Since quite a few people claimed that the remainder of the network stack actually works -- to some degree -- I wonder whether I get something at least remotely useful when I plug my TCP implementation into the stack. The truth will be revealed. And then I can maybe throw the rest of the rubbish out.

The first sentence counts

2011-08-10T20:18:00.000+02:00

Of the novels and short stories I've read there were two cases where not only they were works of sheer literary genius, but also written with a humour that sold them to me with the very first sentence.

In the first case the short story Jupiter Five, my favourite by sir A. C. Clarke, partly due to the excellent and slightly unusual Czech translation.

Profesor Forster měl tak drobnou postavu, že pro něho museli vyrobit speciální kosmoskafandr. (Profesor Forster's stature was so small they had to make a special spacesuit for him.)

In the second case this was the (perhaps more widely known) novel Harry Potter and the Philosopher's stone:

Mr. and Mrs. Dursley, of number four, Privet Drive, were proud to say that they were perfectly normal, thank you very much.

When a story starts with a sentence like this, you just know you're in for a treat :-)

Will ARM architecture go 64-bit?

2011-07-08T15:51:00.000+02:00

For some time now I have been thinking about the increasing memory capacities of mobile devices and the fact that the ARM architecture, upon which they are built, is still 32-bit only. This was puzzling for me, so I decided to dig around a little. The results are more than interesting.

Apparently, in November last year (2010) rumors started spreading that ARM holdings is working on a 64-bit ARM processor (see Xbit labs, v3.co.uk). These rumors were denied by ARM CEO Warren East in February 2011.

In an interesting turn of events, before that in January 2011 at the Consumer Electronics Show in Las Vegas Nvidia announced project Denver which aims to create a 64-bit ARM processor powerful enough to compete on the desktop and server market. At the same time Microsoft announced that Windows 8 will run on ARM as well as on x86. You can read a vey nice analysis on Ars Technica or the interview with Nvidia CEO.

Nvidia's plans are very bold. Who knows whether they will succeed. If they do, this could stir the stale waters of x86 deskop quite a bit. Spending the last HelenOS camp finding a bug in the ARM context save/restore routines might not have been a waste of time after all. Who'd have thought? ^_^

How to ride your magic carpet

2011-05-18T05:00:00.000+02:00

Magic carpets are, you know, pretty much commonplace stuff. Everybody rides one, including Prince of Persia and the Rescue Rangers. Now the thing which has always bugged me is the question: How do you control which direction the carpet should fly?

Looks like another big mystery solved. And I didn't have to look far for the answer, too. It's all written in, I am not kidding you, the USB HID specifications. Quoting:

Magic Carpet Simulation Device

CA – Allows a device to be generally classified as one that uses the standard control of a magic carpet. This control is a bar, grasped by both hands, that controls the Yaw, Pitch and Roll of the carpet.

The bar, at which the pilot sits, may be pushed forward or pulled back to cause the carpet to dive or rise, respectively. In the zero position, the carpet is in level flight. Pushing forward on the bar causes the carpet to nose down and generates negative values. Pulling back on the bar causes the carpet to nose up and generates positive values.

Turning the bar turns the carpet. In the zero position, the carpet travels straight ahead. Pulling back on the right side turns the carpet to the right and generates positive values. Pulling back on the left side turns the carpet to the left and generates negative values. Rotating the bar rolls the carpet. In the zero position, the carpet travels level.

Rotating the bar in a clockwise direction rolls the carpet to the right and generates positive values. Rotating the bar in the counterclockwise direction rolls the carpet to the left and generates negative values.

Now fortunately HelenOS will soon get USB HID support. So that means I can run HelenOS on my magic carpet's on board computer and still use the standard controls of the magic carpet, right? Right?

Granumophobia

2011-04-18T22:11:00.000+02:00

Getting dynamic linking to work right is a never-ending series of dumped cores. Today I found two bugs which were actually quite generic (i.e. not architecture-specific) and, to be honest, quite silly.

First a sizeof(ptr) instead of sizeof(*ptr) passed to memset() caused the dyn_info_t structure not to be properly zeroed out. If something in dyn_info_t is not zero, it is assumed to be valid entry present in the dynamic section. Hence mysterious occasional crashes. Luckily thanks to the new memory allocator which has debugging turned on there was a suspicious quantity of dead beef being thrown around which slightly helped me find the problem.

Second, the relocation processing code was dying while trying to fix up references to libc variables in the text segment of the main program, which is stored in a memory area with R-X permissions. Huh? Well, the main program is loaded by loader, instead of dynload. Unlike dynload, loader does not make all loaded segments writable. Bummer.

Dynamic linking takes patience. If you suffer from granumophobia, then stay away.

Base class constructors? Oh my!

2011-03-19T15:14:00.000+01:00

When a person with quite limited exposure to OO programming (like me) gets such a crazy idea like designing an OO programming language (like Sysel), they shouldn't be surprised when they forget about something important. Like invoking base class constructors.

What happened was that while working on constructing the syntax tree in NNPS I was getting exceptions due to accessing nil reference (equivalent of null pointer dereference in C). The problem boils down to the following: we have two classes A and B, B derived from A. Both have constructors, the constructor for A initializes some reference in A. When a new object of class B was created, only constructor for B was called so the reference was not initialized.

When a new object is created, constructors must be called for its class and all base classes. This is easy if the constructors do not have parameters (in this case it can be done implicitly). If the constructors do have parameters, the programmer must explicitly specify them (since the compiler does not know what they should be).

Different languages solve the problem differently. In C++ (and similar languages) the arguments / call to base class constructor(s) appear to be part of the constructor's signature.

class A {
    public: A(int i, int j) { }
};
class B : public A {
    public: B(int i) : A(i,i+1) { }
};

Others, like PHP, require the programmer to call the base class constructor with a syntax similar to a static method invocation:

class A {
   function __construct(i, j) { }
}
class B extends A {
   function __construct() {
       parent::__construct(i, i+1);
   }
}

The strength of the first approach is that it makes it is syntactically enforcible, i.e.
if you forget about it, the compiler can easily tell. In the second case you can do more
complex processing before calling the parent constructor (than just evaluating an expression),
but it is difficult to tell at compile time whether all code paths contain the constructor
invocation (a problem similar to determining if all code paths in a function end in a return statement).

I still need to decide how to implement this in Sysel. Or I could just make my base class constructors parameter-less for the time being.

GSoC - Great System on a Chip? No!

2011-03-19T14:36:00.000+01:00

It seems a little pointless repeating what has already been said, but, wow, is this something special! HelenOS has been accepted as a mentoring organization for 2011 Google Summer of Code.

What more to say? It feels great to be in company of so many well-known open-source projects from areas of OS, desktop, applications, games, scientific software, etc., etc.

Now we need some students!

Observations on HelenOS device drivers framework

2011-01-03T22:38:00.000+01:00

Some time ago we merged Lenka's new Device Drivers Framework (DDF henceforth) to HelenOS mainline. When I finally read through her thesis and had a closer look at the code I promised to do a writeup of my observations. Here it is. A bit of a long read though, be warned.

Let's start with a quick overview. Lenka's contribution can be broken down into several parts. First there is the devman server which (a) manages the physical device topology, driver task life cycle, driver attaching and detaching, (b) maintains a 'logical' device topology (devices grouped by their class).

Second, Lenka proposed that for any IPC communication between two drivers or an application and driver should be strictly defined in terms of function calls and the client- and server-side IPC glue code should be kept strictly separate in a library to be reused by all servers and clients using such code.

Third, when mapping the function calls to IPC, Lenka reserved the first field of the message for an interface id. This allowed her to communicate with a driver using several different protocols, namely a protocol for talking to the driver as such (create new instance) and for talking to the device itself (e.g. read/write, etc.).

As you can see Lenka took on quite a challenge and tried to cover area that extends quite far past mere device management. I will not try to cover it all here, if you are interested, go ahead and read her thesis. I will only focus here on parts that I found particularly interesting, where I found room for improvement or that inspired me somehow.

Summary of my observations. I have some practical concerns about the DDF, as it is implemented now:

Problematic support of pseudo-devices (e.g. file_bd)
Problematic support of 'multi-function' devices (e.g. i8042)

I believe these need to be addressed before we can convert our current drivers to the new driver model. Also, what I don't like is:

Making devices 'special' and making them use different communication than the rest of the system.

There are also two topics which I haven't seen mentioned in the thesis although they are highly relevant:

parallelism in device enumeration
persistent device naming

I have some ideas what could be handled better or differently, which I will outline below.

IPC communication suggestions

The problem

Lenka faced a practical problem when communicating to a driver. Sometimes she needed to control the driver as such using a generic driver protocol (e.g. add_device operation), sometimes she needed to talk to the driver using a device-specific protocol (e.g. char_read, char_write), etc.

For this reason Lenka came up with the idea that a driver could implement multiple different protocols. She reserves the first field of an IPC message for the protocol ID, moving the method ID effectively to the second field of the message.

Lenka envisaged another use of the multiple interface support, namely that a device could support multiple device-specific protocols and that the interfaces and their API stubs could be reused (in a duck-type manner) and combined, possibly for semantically completely different (but syntactically equivalent) sets of operations.

The first thing that I don't like at all is that here devices drivers are made somehow special and they use a communication protocol completely different from the rest of the system services. There is no reason for that, it will just make communication between different types of tasks incompatible.

Better server task model

The proposed mechanism looks useful and something similar could/should be used for all IPC communications, not just to the device drivers!

Recently Martin Děcký pushed some changes where he started a change in order to embed the interface ID (in the same sense as Lenka uses) to the first IPC message field (along with method ID) to use it in general IPC communication.

Great! This is way better for two reasons:

It is generic, applies to all IPC communication equally
It is more space-conscious, does not consume an entire argument

Still, I think we can do much better than that. (I already outlined this in the mailing list, but I'll repeat it here).

First, embedding the interface ID in every message is wasteful, it stays the same for the duration of an exchange, at the minimum.

Second, I think the problem being solved stems from the fact that we are trying to control different entities within the same server task. So, instead of trying to talk different protocols to the same entity, we are, in fact, trying to talk to different entities (each speaking different protocol, incidentally).

The model of a server task can be described in terms of object-oriented programming:

Lenka says: A server task is an object that implements one or more interfaces.
Jiří says: A server task is a collection of objects, each belonging to (exactly one) class (classes form a true inheritance hierarchy).

If we consider the driver to be a collection of objects (driver control object, device control object(s)), it also solves the problem for the case of the device driver.

Another way to look at this is that we add another level of addressing. We can imagine that we access the inside of the server task via different points of access. We can call them ports in analogy with TCP/IP ports (or RM ISO/OSI SAPs) which allow talking to different entities within the same IP interface (IP node, IP address).

One of the benefits of ports is that when a server provides access to a set of resources of some type (e.g. file, device) we can map each individual resource to a port. Then we don't need a special identifier (file descriptor, device descriptor) since the individual resource is already identified by the port (port ID). So we save one message field plus the framework actually understands that this is an identifier.

Port references can be optionally made unforgeable (which is a very useful property). Ports can be implemented in different ways and have numerous other benefits which I will not detail here if just not to scare you off ;-)

Implementation note: To allow the async framework to embed some information (any of interface ID, port ID, virtual path ID) automatically into a request slight changes to the async API are needed (when making a request we should pass a pointer to an exchange instead of integer/phone ID). Nevertheless the conversion of applications and servers is straight-forward and with a split API it can be implemented gradually, if needed.

Better use of message space

When talking to a port, we'll talk the same protocol the entire time. Therefore, we can establish that right upon connecting. Not only we eliminate redundancy, but we can tell that someone does not speak the expected protocol straight away (better than recognizing it upon the first operation).

So rather than embedding interface ID in the message, we can embed the port ID (having established the protocol spoken by a port already).

Still, an entire exchange (see async sessions) will always talk to just one port, so this still seems a little wasteful.

We could instead embed something that would allow us to identify different exchanges and multiplex parallel operations onto a single physical IPC connection.

A good way to implement that seems to embed a virtual path ID. Virtual paths would be set up and torn down by the async framework (session code) on the client side. Each virtual path would be assigned an ID. The server would create a fibril to service each virtual path (within each connection). The session management code would no longer create (kernel-based) IPC connections for concurrent communication, but instead it would create (userspace-based) virtual paths. This provides and alternative (although not necessarily better?) to the current implementation, which creates multiple physical connections.

The session API combines with this in the following way:

A client initiates a session to a server port.
On the session the client performs exchanges as usual.
Internally the async framework creates as many parallel virtual paths (within the physical connection) as necessary
The async framework on the server side creates a handler fibril for each incoming virtual path

Device model suggestions

Current model

In the current model we have two types of device nodes: nexus nodes and leaf nodes. A nexus node ('bus device') consists of several objects:

1 driver control object (generic driver protocol)
1 nexus (bus) device control object (device-specific protocol)
n device attachment points (bus-specific protocol)

A leaf node consists of:

1 driver control object (generic driver protocol)
1 leaf device control object (device-specific protocol)

Important to note is that the driver control object and device control objects always coexist (you can't have one without the other).

Problems

The biggest problem I see in the current model is that it requires a 1:1 relationship between a physical device (something to which you can attach a driver) and its logical functions (services provided by the device), at least for leaf drivers (you can't have one without the other).

Pseudo-driver

Let's call a pseudo-driver any driver whose life-cycle is not naturally controlled by bus enumeration. An example is file_bd whose instance is naturally created when the user types in some command.

If we wanted to port file_bd to the current DDF we would need to also add some special pseudo nexus driver (possibly a special one for file_bd) which the application would tell to attach a new child. Then we would need to somehow communicate the parameters to the child and...aargh!

While the plain devmap-style drivers can be modified to speak a protocol compatible to the devman-style drivers, they are not fully fledged devices. We can't add them to device classes, so if we obtain a list of devices in some class, these pseudo-devices won't be included.

Multifunction device

Let's call a multifunction device any device which behind one physical interface provides access to multiple logical functions.

Buses can be considered multifunction devices (they expose multiple device attachment points). Our concern however are multifunction leaf devices. A typical example is i8042 (which provides two character interfaces) or a (partitioned) disk (which provides multiple block interfaces).

If we wanted to port these drivers to the current DDF, we would need to implement them in terms of a nexus device plus a leaf (connector) device. Even if we implemented both the nexus and connector device inside a single driver binary, it is just unnecessary complication. The connector device would do nothing but forward IPC communication to the nexus device. Why clutter device drivers with completely generic code?

Proposed solution

I propose a more uniform device model, where each (nexus or leaf device) consists of:

1 driver object
1 (physical) device object
n logical functions

Each logical function can be either a external / leaf function (exposed to clients outside of DDF) or internal / non-leaf function to which the DDF can attach more levels of the device hierarchy.

The choice of whether a logical function is external or internal could be up to the (nexus) device driver or, possibly, it could be made to depend on other factors (such as whether a device driver could be attached). Mixed-mode (leaf and nexus) drivers would be possible, if desired.

More importantly, multifunction leaf devices would be easy to implement (just change the flavor of the functions from internal to external and voila). No need for implementing connector device nodes in such driver.

Also we can make it possible for any server to call the DDF and say 'hey, I'm a pseudo driver' and to create logical functions. This enables us to construct (leaf) pseudo-device drivers in a simple and straightforward manner. These don't need to be included in the physical device tree (equivalent of UN*X /devices). Only their logical functions are included in the logical device function name space (equivalent of UN*X /dev).

An interesting problem is the existence of pseudo nexus devices. A pseudo nexus device must be included in the physical device hierarchy (because its children are not pseudo devices in the sense described above). If we choose to allow pseudo nexus drivers, we will need, in the end, some 'pseudo' node in the device tree as a root for them. Still, we will have the benefit of manual device lifetime management. I am not sure whether pseudo nexus devices are useful or not.

As a side note, the operation add logical function is (conceptually) more generic than add child because it does not imply what gets connected to the attachment point (logical function). In a multi-pathed device scenario the device node is not attached directly to the parent node. Instead for some bus B there is a multiplexer which connects to each B host adapter node. All device nodes then attach to this multiplexer. (So their connection to the bus host adapter node is indirect).

Providing device services

Currently devman manages device classes. A device driver will register a device in some class and then applications can e.g. list all devices in some class.

This is not necessarily bad, although it might be an unnecessary complication. If we implement location services in the CORBA sense (naming and trading service), they will provide the same functionality for all IPC services.

(Explanation of what I mean here by LS in the CORBA sense: Any server can register a (non-singleton) service, specifying its name (generated hierarchical unambiguous (string) identifier) and type (hierarchical name of a class/type of the service). Then we can list all services, services by class, etc.)

Now it is perfectly possible to export services provided by some device via the location services instead of implementing a special registry in devman.

So, in the scenario described above, there would seem to be little added value in using a special devman class database, instead of the more generic (and possibly smarter) location services.

Corollary

I described what I see as important limitations of the current HelenOS DDF. Lenka's work inspired me with many interesting ideas, which I described. I proposed a number of improvement proposals either to the DDF itself or in IPC. The proposals form a coherent vision, but many of the individual ideas are to a degree independent and thus they can be implemented individually and gradually.

Thanks for reading.

Mister triple W. meets miss H.

2010-12-28T19:54:00.000+01:00

I think the following image speaks for itself.

After my recent bug fixes, HelenOS is able to serve a web page from inside Qemu. TCP is still shaky, sometimes it works, sometimes it does not. But it's still progress :-). In the past weeks and months I got my hands dirty in the networking stack and I tell you, the code is weird throughout!

The web server is mostly fake, but it does serve its purpose :-) I should be committing it shortly.

A moment to remember

2010-12-03T20:36:00.000+01:00

If you don't understand Czech, turn on CC (captions) in the player before starting the video.

Nuts and bolts

2010-11-30T06:57:00.000+01:00

Today I'm back with a now familiar picture of the Fanatik 1, this time with the major parts labeled.

The system is divided roughly in two halves, the left half being the 'compute' part and the right half being the 'graphic' part.

Let's start with the CP (Central Processor). This is an Atmel AVR microcontroller, specifically ATMega162. This chip acts as the CPU, having access to the system's memory and some of the peripherals.

There are two SRAM memory chips called CMEM and GMEM, CMEM is primarily used for computing, while GMEM holds the video frame buffer.

Fanatik has two analog video outputs, VGA and TV (cinch). These video signals are generated by the GIA (Graphics and Interconnect Array). This is a Xilinx XC9572 CPLD (programmable logic device). The D/A converters are made solely from discrete resistors.

The SP (Supplementary Processor) serves as a clock generator and PS/2 keyboard controller. It can communicate with the CP via three dedicated lines plus over the eight (shared) bus data lines.

The CP is also connected to the RS-232 interface (serial port), the buzzer/speaker output and the tape in/out ports ('mic' and 'ear'). Power (9-12 Volts DC) is provided via a standard DC power connector.

The compute part and the graphics part each have its own bus. These are coupled by the passive bus bridge (array of resistors). This allows the two buses to function independently or as one single bus, as needed.

As you can see the Fanatik relies heavily on programmable hardware. As both the AVR MCUs and the Xilinx CPLDs are in-system-programmable, I can re-program them without unplugging them from the board :-).

Hope you liked today's quick walk-through. Obviously I skipped a lot of details, but you can already see that the Fanatik is a pretty cool device with a decent range of I/O capabilities.

Correct answers from previous quiz

next to the heatsink screw on the top-left: Trashman (left of screw), Sabreman (left and below of screw), diver from Scuba Dive (right and below of screw),

around Fanatik label: Horace (left and above), the knight from Cavelon (below), Jet Man from Jet Pac (right and above)

left edge under the motto: Miner Willy from Manic Miner (top), boy and girl from Quicsilva's Ant Attack (middle), Jack from Jumping Jack (bottom).

bottom edge and right edge: Interstellar Space Slug from Pssst (antagonist, bottom edge) and Kokotoni Wilf (from the eponymous game).

Cookie winner: Jakub (congratulations! ^_^)

New quiz

(This time hopefully simpler.) Try a quick guess at the basic specs of the F-1. Namely try to guess the clock speed, RAM capacity and number of colors supported by the video outputs. Don't try to look it up, just give me the first number that comes to your head. Don't be shy! ;-)

Till next time!

Faster than a speeding Panda

2010-11-17T23:30:00.000+01:00

It's been more than a hundred days since I placed a pre-order on the demonic box. While those guys are still trying to sort out their nubs I certainly haven't been biting my nails idly.

Immediately after placing my order I set upon a quest. A quest to construct my own computing device. An so, after more than three months of planning, designing, etching, drilling and soldering I proudly present to you (lots of drum rolls and dramatic chords..) the one, the only, Fanatik 1!

Fanatik 1 is a one-of-a-kind computer heavily inspired by the classic 80's microcomputers, specifically the ZX Spectrum.

I should get back to you soon with more details on the F-1. I will also present you with a series of quizzes. Today the question is simple: Try to name as many Speccy computer game protagonists as you can recognize etched on the Fanatik board. The winner will receive an original browser cookie.

And you though your dreams were weird

2010-11-06T11:23:00.000+01:00

Last night I dreamt I was trying to provoke William Murdoch into inventing the water turbine. WTH?!

One, two, three... testing!

2010-10-25T09:13:00.000+02:00

Many of you already know I've been busy with a 'top secret' electronics project. Especially Jakub has been nagging me to reveal something. Today I can share with you this photo of some mysterious tests that I've been performing. The results were satisfactory. That's all I will say for now. Mwahahaha!

For those less versed in electronics let me describe the action for you. What you see in the picture are three joined-up breadboards. On the breadboards we see some DIL ICs plus a bunch of wires and other stuff. The thing on the middle breadboard is a surface-mounted IC soldered to a home-made PCB which has pins on the bottom side and allows one to plug the chip into the breadboard.

And yes, the thing on the left side is a Logitronik II because George says every mad scientist should have a Logitronik II in their basement.

Reading for week 32

2010-08-09T19:18:00.000+02:00

The guys from the (presumably dead) TUNES project seem to have liked writing essays more than actually writing code. (At least I was not able to find any). Compared to their cloud-castle project, Sysel seems boring and pure mainstream ^_^.

They seem to have a clear opinion on microkernel OS design (calling it an abstraction inversion) which I recommend reading.

While cannot agree with everything therein, the article (or manifesto or whatever it is) accurately points out the principal weaknesses of microkernel design as such (as well as the faults in existing microkernel-based designs).

Ensnared by the magic box

2010-07-29T21:22:00.000+02:00

The magical Pandora's box surely worked its magic on me. I am now on the waiting list for the Pandora Console having just pre-ordered (and pre-payed) it. Now I just have to bear with the incredibly looong waiting time. (Supposing I do receive the console, it will be a pleasant surprise if I receive it this calendar year. Surprise me.)

When I bought the Neo FreeRunner it was mostly for the sake of porting HelenOS to it as I am not really into smartphones. It is still a cool device, though, thanks to the integrated Wireless Ethernet, GPS and accelerometers (and the openness, of course).

With Pandora the situation is a little different. I really like old games and this is the retro gaming device. The real selling point for me is the keyboard (although it probably is not a great one). Pandora also has gamepad controls, but I don't really like gamepads, anyway. It also has integrated WiFi (just imagine the multiplayer possibilities!) So I definitely want to use it on gaming (you could call it love at first sight).

Porting HelenOS to Pandora should be relatively easy now, I should think, as I've already fixed the bugs that prevented HelenOS from running on a real ARM processor (despite working in emulators). Also, Pandora uses U-Boot just as FreeRunner does, so bootloader should not be a problem either.

Anyway it will be long before I have my Pandora, so I still have plenty of time to improve FreeRunner support :-)

Watchen sie die blinkenlichten

2010-06-17T22:44:00.000+02:00

Turn on CC (captions) in the player before starting the video.

GCC: plus plus or not plus plus?

2010-06-04T19:56:00.000+02:00

It appears that GCC has green light to start using C++ in their code. The idea seem to have been under consideration for about two years. This time, however, it has been approved by the GCC steering commitee and the FSF.

The surrounding discussion is is pretty much the old battle between C++ proponents (who point out its many merits) and opponents (who point out its many flaws). Concerns about speed and the need to teach GCC devs to use C++. Concerns about 'misuse of C++ features.' I find the slowness argument especially amusing since Clang/LLVM is written in C++ and it does not appear to be suffer from severe performance problems.

And of course there are those who suggest only to use a subset of C++ that would not incur performance penalty nor contain features that are 'easily misused'. I hear many software projects claiming to use C++ are actually written in different, mutually incompatible subsets of C++ (using or not using exceptions, RTTI, templates, etc.) This seems to be encouraged by the historically bad conformance of C++ compilers to the language standard.

Looking away from the rather amusing bickering, does this change affect me, a mere mortal user? Well normally I couldn't care less. When I compile GCC on Linux this certainly does not present any problem. From HelenOS point of view, this is more interesting.

To make HelenOS self-hosting, we need to be able to have some compiler which can be compiled within the system. Question is, which compiler should it be? Today GCC is still a hot candidate -- it is probably the only compiler supporting all the CPU architectures and other features we need. Another selling point was it being written in C -- which it will now lose. In the future it would be necessary to implement or port the C++ standard library (and STL) to HelenOS in order to compile GCC in it.

This makes GCC drop closer to Clang/LLVM on our suitability ladder. (Clang/LLVM is also written in C++). Practically the only remaining deficiency of Clang/LLVM w.r.t GCC is that unlike LLVM itself, which should have good support for several architectures, Clang currently only has good support for i386/x86_64. It should not be hard to improve Clang support for other targets, but still there must be sufficient demand to drive the development (Apple does not need it).

Another player in the field is the Portable C Compiler. It is written in C, but it is a relatively small project and supports only a few CPU architectures. (Interestingly neither LLVM nor PCC support Intel Itanium architecture). I have some misgivings against depending on such project whose future is not very certain.

In any case, the choice of a (first) C compiler to run in HelenOS remains open for now.

Hash or dash?

2010-03-05T09:47:00.000+01:00

I am pleased to say that SBI (Sysel Bootstrap Interpreter) is making good progress. You can already create object instances, play with the variadic built-in function Exec, raise and handle exceptions, etc.

Now I know you might think I am just being silly, but I still haven't decided on how to write comments. Basically I am oscillating between hash (as you saw in previous posts) and dash (--), i.e. double hyphen, for denoting comments.

Hash is easier for me to type, because I can type hash with my left hand and use arrow keys with my right hand at the same time. For double hyphen I either need to use the little finger of my right hand, or lift the hand and move it towards the minus key.

From aesthetic point of view... I just don't know. Most of the time I seem to prefer dash, although it clashes with the bullet point hyphens in the BSD license in the HelenOS format (but an alternative form could be used for that).

What I am quite confident with is that the commonly used comments should be single-line comments, where comments blocks would be created by typing in a series of single-line comments. Multi-line comments would only be used for disabling sections of code (typically for debugging purposes).

Doc-blocks will be started by a special single-line comment (such as ## or ---) and continued by regular single-line comments (such as # or --).

An interesting idea here pertains to the way of denoting the 'brief' part of the doc block. The common methods include: (1) up to the first period (.), (2) the first paragraph, (3) the first paragraph if marked with some special tag (such as @brief). Another way which came to my mind is that if the 'brief' part spanned more than one line, all these lines would use the same doc-comment mark. Example:


## First line of doc brief and
## this is the second line.
# 
# This is no longer part of
# the brief.


--- First line of doc brief and
--- this is the second line.
- 
- This is no longer part of
- the brief.

Do you like one of these comment styles better than the other? If so, why? Or would you recommend yet another one? Let's hear ye!

Watch out HelenOS, here comes Sysel!

2010-02-23T21:39:00.000+01:00

It is alive! I had to put in some hacks to avoid name conflicts and I had to implement fgets() in the HelenOS C library, but SBI now works in HelenOS. It's not really a big deal, as SBI still doesn't do so much, but it's still nice.

If you're eager to try it, check out this Bazaar branch.

Build the system as usual and boot it. There are some really trivial demos in the sysel/ directory. Just run SBI with the source file pathname as argument. For example:


# sbi sysel/hello.sy

Well... back to work!

A Rodent is Born

2010-02-22T22:49:00.000+01:00

I guess I cannot pretend it's a secret anymore. I am working on Sysel. What is sysel? Well, sysel is the Czech name for the European ground squirrel, or, in layman's terms, the European gopher.

Sysel with capital S is a programming language, however. From the previous posts you should already have some idea how Sysel should look like. Right now (in the 'first phase') I am developing Sysel Bootstrap Interpreter (or SBI for short). This is an interpreter of Sysel written in C.

The main purpose of SBI is to bootstrap the prospective self-hosting Sysel compiler, as well as serving as a testbed and refining the language design. Nevertheless, SBI will run under both POSIX-based systems and, of course, HelenOS. SBI as well as other Sysel tools that I will produce will be available under the same BSD-like license that is used by HelenOS.

Only real geeks develop alternative operating systems. Therefore, hopefully, by creating an alternative programming language to develop an alternative operating system in, I will be able to achieve whole new levels of geekiness.

I have created a project on Launchpad where you can now track my progress. I will also publish a HelenOS+SBI branch when that's ready.

Stay tuned!

Inheritance Quiz

2010-02-14T12:05:00.000+01:00

Now pay attention, class! Try to guess what does this fine C# program do?

using System;

public class A {
        public static void hello()
        {
                Console.WriteLine("Hello World!");
        }
        public class B : A {
        }
}

class Test {
        public static void Main(string[] args)
        {
                A.hello();
                A.B.hello();
                A.B.B.hello();
                A.B.B.B.hello();
                A.B.B.B.B.hello();
        }
}

I'll give you a few options. This C# program, when compiled with GMCS will:

(a) Compile without error and print "Hello World!" five times.
(b) Compile without error, but abort with a runtime error.
(c) Abort compilation because of the cyclic inheritance.
(d) Abort compilation because A.B is not defined.
(e) Abort compilation because A.B.B is not defined.
(f) Crash the compiler.

No cheating, please!

Syntax Silliness

2010-02-03T21:44:00.000+01:00

I started to play around with the Mono C# compiler. Since all my previous experience with C# has been just passive (i.e. reading tutorials), I started with something very simple: a class implementing a generic doubly linked list. (It's completely brain dead, but should be sufficient for this example.)

I thought it would be fun to convert it to an alternative syntax, so here it is. Note for example the syntax for type parameters. I also added some more specific ideas, like translatable strings with annotations, Python-like for loop, or the with-except-finally statement. The snippet is rather long, which is good, as it should deliver a more authentic experience. For the most part, this a transcription of real C# code, while some of it is completely constructed. If you don't know C# please be careful not to credit me with its inventions.

What I like about this syntactic style is that it avoid C#'s sort of 'German' word order. Public static override void ... wait, where was I? Here, the name of the object being declared is reasonably close to the beginning (just the second word). Also the first word let's us know what kind of object we are dealing with (function, variable, class, etc.).

My fingers didn't really object. Even though 'end' has three characters while '}' has one, short keywords are actually easier to write than special symbols which require Shift to type. My eyes were O.K with it, too -- each declaration is visibly anchored and appears to be balanced. So I am reasonably happy with this creation.

What about you? Do you like it?


## Generic list type.
#
# Really just an example of program syntax style. This list can be
# appended to or prepended. It implements an enumerator and an
# indexer. Backwards or random-direction iteration is not possible.
#
# This class has one generic parameter (t), implements the
# IEnumerable interface. t is subject to the constraint t : class
# (t is a reference type) and the class MyList't is public.
#
# Note that this is meant only to demonstrate syntax style and
# it's almost 1-1 translation of a C# program. (But some special
# syntactic ideas are also demonstrated.
#
class MyList't : IEnumerable, where t : class, public is

        class Node, protected is
                var prev, next : Node, public;
                var data : t, public;

                constructor(new_data : t), public is
                        data = new_data;
                end

                fun insertBetween(a, b : Node), public is
                        prev = a; next = b;
                        a.next = this; b.prev = this;
                end
        end

        var head : Node, public;

        constructor(), public is
                head = new Node(null);
                head.prev = head;
                head.next = next;
        end

        fun append(data : t), public is
                var e : Node;

                e = new Node(data);
                e.insertBetween(head.prev, head);
        end

        fun prepend(data: t), public is
                var e : Node = new Node(data);
                e.insertBetween(head, head.next);
        end

        fun printNodes(), public is
                for data : t in this do
                        Console.writeLine(data.toString());
                end
        end

        fun getLength() : int, protected is
                var len : int;

                len = 0;
                for data : t in this do
                        len += 1;
                end
        end

        ## Get the node at the specified index.
        #
        # @param pos    Index (0 = first, 1 = second, etc)
        # @return       Node at the specified position.
        #
        fun getNodeAt(pos : int) : Node, protected is
                var e : Node;
                var i : int;

                i = 0;
                e = head.next;
                while true do
                        if e == head then
                                raise new Exception();
                        end
                        if i == pos then
                                break;
                        end
                        i += 1;
                        e = e.next;
                end

                return e;
        end

        ## Number of nodes in the list.
        #
        # Property - looks like a member variable, but assigning
        # to it or reading from it can have side effects.
        #
        prop length : int, public is
                get is
                        return getLength();
                end
        end

        ## Indexer
        #
        # This a simpler variant of [] operator overloading. Here
        # we can define the effects of reading from / writing to
        # an object of this class with index (e.g. list[3]).
        #
        prop this[pos : int], public is
                get is
                        return getNodeAt(pos).data;
                end
                set is
                        getNodeAt(pos).data = value;
                end
        end

        fun toString() : string, public, override is
                var s, sep : string;

                s = ""; sep = "";
                for data : t in this do
                        s = s + sep + data.toString();
                        sep = ",";
                end

                return "[" + s + "]";
        end

        generator is
                var e : Node;

                e = head.next;
                while e != head do
                        yield e.data;
                end
        end

end

#
# An example how a variadic function might be declared (var
# attribute). The + means that the argument must not be null.
# The whole piece of code is disabled using a multi-line 'comment'
# block. Only single-line comments are meant to be used for comments
# per se, while multi-line blocks are meant for disabling sections
# of code quickly.
#

#{
class PrintFormatted, public is
        fun format(fmt : +string; args : (+object)[], var) : string is
                ...
        end
end
#}

class Test is
        fun Main(args : string[]), public, static is
                # Using a generic class
                var list : MyList'string;

                # Translatable string literal.
                Console.writeLine("Hello World!"@);

                # Translatable strings with annotations (these
                # are used when have equal strings which are to
                # be translated differently.
                Console.writeLine("bug"@software);
                Console.writeLine("bug"@insect);

                list = new MyList'string();
                list.append(1.toString());
                list.append("hello"@greeting);

                Console.writeLine("Objects in list:"@);

                # It's really better always to iterate over some
                # list. We don't need a C-style for(;;) so no need
                # to call this foreach.
                for o : string in list do
                        Console.writeLine("Node " + o);
                end

                # Instead of for (i = 0; i < 10; ++i)
                for i : int in range(0, 9) do
                        Console.writeLine(i);
                end

                #
                # It would be possible to combine a context-
                # management statement with a try block. So,
                # try/except/finally can be thought of as a special
                # case where we do not need to guard any resources
                # with the 'with' statement.
                #
                with f : TextFile = TextFile.OpenFile("test.txt") do
                        # If any exception happens here, f is cleaned up
                        # gracefully via f.dispose() (or similar)
                        var line : string = f.readLine();
                        Console.writeLine(line);
                except e : Exception do
                        # And likely we also want to handle the exception
                        Console.writeLine("Error reading file.");
                finally
                        Console.writeLine("Done");
                end
        end
end

Lua's syntax

2010-01-20T20:39:00.000+01:00

In search of inspiration for language syntax style I remembered Lua. It takes the third major path apart from curly braces (C) and off-side rule (Python). It is thus reminiscent of the Algol family, especially Ada, UNIX shell syntax or Karel (at least some incarnations thereof).

Lua is (mostly) free-form and uses what I call in my head (inappropriately, perhaps) implicit block delimiters. Where a declaration of some program element in C might look like


declaration {
        element;
        element;
        ...
}

in Lua it is instead


declaration
        element;
        element;
        ...
end

What I like about the latter case is that programmer is freed of the choice whether or not to use curly braces to delimit a single statement in control flow expressions such as if, for, while. Still, the language remains free-form and the code looks visually balanced to my eyes. For some reason I feel the cosmic balance disturbed if the beginning end end statement are not both marked, with the same indentation. In Python the blocks feel– incomplete– without the final delimiter. Of course, which style has better signal-to-noise ratio, can be disputed.

Here, Lua is somewhat more concise than Ada or Fortran where we annotate what kind of block we are ending (e.g. if ... then ... else ... end if) in hope of helping the programmer match the delimiters more easily (and to help the compiler spot bracketing errors).

One design element of Lua syntax that I don't really like is the freedom to or not to terminate any statement with a semicolon. Instead a statement can be terminated with a newline. On one hand this allows us to avoid using punctuation unless necessary, on the other hand the language is not fully free-form. Quoting from the reference manual, the code


a = f
(g).x(a)

would be mistaken for two statements. Gorgeous ^_^.

In Ada all statements (and other program elements) are terminated with a semicolon. The Prosody IM software written in Lua seems to have adopted a coding style where every simple statement is terminated with a semicolon, while any compound statement or element ending with the end keyword is not.

Conclusion: While Lua syntax style need not be perfect, it demonstrates that even this syntactic style does not have to be excessively verbose. I like it enough to consider its style as a primary source of inspiration.

Note: When will I actually post anything related to HelenOS?

The woes of C II: Attack of the Teenade Mutant Cabbage

2010-01-04T21:48:00.000+01:00

Anyway, I can hardly imagine a supercalifragilisticexpialidocious operating system such as HelenOS can be 0.70710678118654757 as supercalifragilisticexpialidocious if it is written in C. Rather than using an existing programming language which is not s32s enough, I'd much rather design my own programming language.

There are two cons: (1) bigger adoption barrier, (2) designing a language and writing the compiler is not a small job. (As a starting point for an estimate, the C compiler I wrote a few years ago while I was still at Uni took me (very roughly) 300 hours before it could compile itself. In this case I would have to design the language and write two compilers. The first compiler (or interpreter) would have to be written in an existing language to bootstrap the new language and the other one a native compiler (i.e. written in the language itself).

I have some idea of the main semantic features the language should have. The most important difference from C#, the basic integer type should allow for arbitrary-size numbers, as in Python. That's one important step Microsoft did not take.

I am still looking for a good inspiration for the syntax though. I'd rather not go into curly braces. I like a lot of ideas from Python's syntax a lot. However, in a statically typed language the lines can get longer and this might not work as well. I also consider taking inspiration from functional languages such as Haskell for function-call syntax (i.e. 'f x y' instead of 'f(x, y)') although this might not work well with passing keyword arguments (passing arguments with names explicitly specified).

In case you are wondering, yes, I already have designed a completely useless programming language (and wrote a compiler for it) and not published it. So I definitely do know I am perfectly capable of just that. Again.

There you have it, I spent the whole evening babbling. However, if the sum of time other people spend reading these posts exceeds the time I spend writing them, then vengeance will be mine! Maybe next time I will cover some less revolutionary, boring and virtual topic. Or not.

The woes of C

2010-01-04T20:56:00.000+01:00

If I wanted to make this article look interesting, I would title it C considered harmful, but I will not. HelenOS is written in C. C is a programming language created at the beginning of 1970's. It's creation is closely tied with the birth of UNIX. At the time of its creation, C was a simple and yet extremely powerful programming language.

C maps (or can map) rather closely to the hardware. Originally it required no or very little run-time support. (What this means: a piece of code using only the core language -- not library routines -- can be compiled directly to machine code and does not require additional libraries or other support to execute).

For quite some time C has been showing its age. Both the core language and the standard library are becoming more and more inadequate for implementation of applications.

Working with strings has always been an extreme pain in C, but with multi-byte encoding (i.e. UCS/Unicode) it has become a nightmare. In HelenOS we decided to drop the standard C99 way of handling multi-byte strings altogether and implement our own. Needles to say, it's only a little better, the language won't allow us more. I demand automatic memory management! I demand user-defined operators!

String formatting in C is a chapter on its own. While this could be re-implemented in the standard library to be extensible (i.e. allow the consumer to register a formatting function for their custom type) we cannot really do away with the need to provide the type of argument in the formatting string, at least not in a sensible way. I demand virtual methods!

What usually drives me mad is the complexity involved in using a hash table in HelenOS. I need to implement several callbacks just to get my int->pointer map. I want generics! I demand collections!

There is a plan to implement a graphical user interface for HelenOS. Having to implement it in C is just giving me the Willies. We would probably end up with some monstrosity like GTK... or worse. I demand inheritance!

I demand a language worthy of the 21st century!

... to be continued.

What this blog is about

2010-01-04T20:28:00.000+01:00

Now wait a minute... this blog has existed for a few months already, but the first post is dated today?! That can mean only two things: either (a) I am the laziest person in the solar system or (b) I prefer coding to writing about coding.

This blog shall deal mostly with my contributions and ideas for HelenOS. If you don't know what HelenOS is by the time you've finished reading this sentence, then you obviously have not followed the hyperlink embedded within it. Redo from start. Now you know HelenOS is a supercalifragilisticexpialidocious operating system.

This information is mostly targeted at fellow HelenOS developers and enthusiasts so I will probably not bother to explain all background for the average passer-by most of the time.

I might also blog here about other geeky stuff not related or vaguely related to HelenOS. That is, if I manage to blog at all. Because of (a) or (b).

Hey Jakub, I blogged! Jakub's been persuading me to blog about HelenOS for some time. So there. I've blogged. Blogo ergo sum. Although I don't have a MySpace account. So I don't exist. And I don't have FaceBook account nor a Twitter account nor a Peprnet acount and omega other accounts. So the cardinality of my non-existence set is omega. Doh.