Hoo Woo!

Sweet momma-mojo of crazy swing + talent + gypsy-styled awesomeness. I caught the Woo Hoo Review tonight at Bar Open by muh-self. I must say, patting-myself-on-the back, awesome choice. I was feeling kinda sleepy/tired/meh. Then ... then the music kicked in. So much so, they had me jigging around, bouncing around is more like it. I'm sold. I think I want to get a RV, Gypsie-styled, and become a nomad of FOSS. Please plplplplpplleeeassee check this band out.

-Matt

Google Go: A Brief Stroll Down GC Lane

The following is a quick summary of the Google compiler, gc, for their language Go. I have recently been hooked onto Go as it is a relatively new language, and my research interests are compilers. Not to mention I have been looking for a compiler to hack on for my PhD research. Oddly enough, I caught a talk about Go where Rob Pike, Go evangelist and developer, gave an awesome presentation on the language, which kinda lured me in. Plus, to benefit my cause, the source is free and open, so I decided to take a stroll down the source code lane to see how Go churns one's source code into an executable.

Note, this is my interpretation of the gc compiler, I cannot say it is 100% accurate, nor am I reviewing the compiler. Since there is relatively little public documentation on how the internals of gc tick, I figured this exploration would be a good learning experience for me. Maybe someone else will find this somewhat useful.

TL;DR: Cool compiler for a cool language Go which focuses on memory safety and easy implementation of parallelization. GC is based on Plan 9 with their specific assembly and object file format.

The following is a brief outline of how a Google Go source file is compiled by the gc compiler taken from the Google repository at revision 6277:ed9fe47b342d (September 14, 2010)

Quick Overview

The gc compiler primarily functions from two spots in the Go source tree, the general non-architecture-specific code in go/src/cmd/gc and the specific architecture based code in the go/src/{5g,6g,8g} directory. The other portions of the build phase are also located in the respected 5l/6l/8l and 5a/6a/8a directories for the linker and assembler. The 5/6/8 prefix denotes the specific architectures ARM, x86 64-Bit, or x86 32-Bit respectively. All three of the aforementioned tools (compiler, assembler, linker) make up the build process.

The gc compiler is derived from the Bell Labs Plan 9 operating-system project. Heck, why start from scratch when part of the Plan 9 team now works at Google :-) Anyways, the main focus of this post is on the compiler, but some mention of the linker will also be made. The Plan 9 errrr go tools (compiler, assembler, and linker) are written in C. What does this mean? Well, for one, the gc compiler for Go is not self-hosting, it does not build itself, but there is good reason for this, mainly bootstrapping and to support the online community who can simply bootstrap with an existing C compiler, e.g. gcc [5]. Most users probably already have the latter.

There is also a GCC front-end for Go, gccgo, which can be obtained from the gcc project's source repository. Consider that since gccgo does utilize the gcc framework, it should be able to use a set of optimizations that gcc provides for their intermediate representation. However, this post focuses on the gc compiler, developed by Google.

From Source to Binary

The system adheres to a common build phase:
Compile --> Assemble (Plan 9 Object Files) --> Link the object files.

Object Files

The object files are not pure binary output from the compiler, rather they have some human-readable text as well. The format is specific to Plan 9 and is not documented properly (publically) as far as I am aware. The information in the object files, later to be assembled and linked, allow for link-time-optimization, roughly known as whole program optimization, or cross translation-unit/compilation-module optimization. I am unaware to the degree of cross-module optimization that takes place, as the Plan 9 Compiler document [2] states: "The loader [linker] is a multiple pass program that reads object files and libraries and produces an executable binary. The loader also does some minimal optimizations and code rewriting."

From Source to Object File

Since this post is mainly concerned with what the compiler is doing, and mostly ignoring the linking phase now, the compiler begins its work in main(), of course, remember, it is written in C. Anyways, src/lib9/main.c is where all the magic kicks-off. From there the source file(s) must be lexed, which is built on the lex/flex and yacc/bison tools. The parser and lexer do their jobs to process the source-code into data that the compiler will use to manipulate and generate object files in three passes. Those being interpreted from the commented source as:

1. The compiler first processes the "const, type, and names and types of funcs".
   
2. Then, in the second pass, the compiler handles "variable assignments."
   
3. Finally, the thrid pass processes function bodies.
   

As mentioned, the final pass is when the functions are processed. This processing starts with a call to the funccompile() routine. The body of the latter is defined in src/cmd/gc/dcl.c and then calls the architecture-specific compile() routine. compile() is specific to either the 5g or 6g compiler. The remainder of this overview assumes the x86-64 6g compiler.

The compiler builds up an internal representation, e.g syntax tree, built of Nodes. The program as a whole is a NodeList (list of Node structures). The Node structure is a mammoth generic structure that represents all constructs in the language. A function body is represented as a Node with internal pointers to more nodes defining the other pieces of that routine. For instance, a statement can be represented as a NodeList, the Nodes in that list are the various components that makeup the statement walkret() in go/src/cmd/gc/walk.c shows a traversal across the function body to find the return statement for that function.

But before we get too far, the typecheck() routine should first be examined. This routine is called for all three passes and occurs before the compiler jumps to the architecture-specific call to the compile() routine. The typecheck() routine acts on a single Node that it is passed. typecheck() first checks to determine if the Node represents an IOTA (in essence an enumerated value). If it is such, its value is changed to a constant. String literals and other constructs are further qualified, and some error checking occurs, such as array boundaries. Basically, further resolution from what the parser gives us and safety checks.

So, after some type-checking is complete by the three passes, it's time to do more architecture-specific compiling via the compile() routine. The width of the construct represented by the Node is first calculated (e.g. data types like float, int, etc). If the value is a string, a flag is flipped here making note of this needed runtime check, similarly the same occurs for some cases of arrays. Next, the arguments are setup for functions.

The walk() routine in go/src/cmd/gc/walk.c is then called which further processes the body of the function including the return statement. Unused variables are also checked. The walk{stmt,expr,switch,select}() routines are called on the function body. The walks add more data to the Nodes that comprise the ultimate representation of the function being compiled. Walking also adds calls and variables as needed. The uniqueness of how the language is implemented and works stem from these walks.

The final phase of compile() is a call to heapmoves() which, according to the source code, "migrates" the funcion input/output values "between the stack and the heap." The latter calls the paramstoheap() routine (also in src/cmd/walk.c), where the function arguments (input) are walked. This portion of compilation "generates" the "code to allocate copies of escaped parameters to the heap." Finally, after the latter call returns, and just before compile() exits, the output arguments of the function being processed (return arguments), are copied to the stack.

*whew* now the compile() is complete, and the object code is assembled in a Go/Plan9 syntax that is dumped to output. To begin this object code production, a call from main() (after funccompile()) in go/src/cmd/gc/lex.c to dumpobj() in go/src/cmd/gc/obj.c is executed. Some of the routines responsible for emitting the object code are 5g/6g compiler specific, for instance dumpdata() and dumpfuncs() located in go/src/cmd/{5g,6g}/gobj.c. The code that is internally assembled by the 5g/6g compiler can be viewed via the compiler's -S argument( e.g. ./6g my_source.go -S). The object file basically contains that information in a binary format, with some metadata for linking.

References

1. Google Go Source Code,
   https://go.googlecode.com/hg (source code)
   Revision 6277:ed9fe47b342d (September 14, 2010)
   
   
2. Ken Thompson, Plan 9 C Compilers,
   http://lsub.org/sys/doc/compiler.ps
   
   
3. Plan 9 Man Pages (9c, 2a)
   
   
4. Google Group for Go:
   http://groups.google.com/group/golang-nuts/
   
   
5. Google Go FAQ:
   http://www.golang.org/doc/go_lang_faq.html
   
   
6. Plan 9 From Bell Labs (Website)
   http://plan9.bell-labs.com/plan9/
   

-Matt

Ostara (Spring Solstice) has Occurred

Ok well the Southern Hemisphere's spring solstice was earlier this week, officially marking the beingging of spring. Outside looked rather welcoming last afternoon, so I decided to go for a stroll and take pics. Mainly I wanted a pic of "mattt" Apparantly there is one that exists. I had been planning on taking a shot of this for sometime now. I know WallyBert will get a kick out-of-it.

Friday night I met up with some of the Ruxcon peeps. Had fun hangin' out with them. The meeting was more of a demo on SQL-injection and remote shell/webshell execution. Louie did a great job with the talk. Afterwards, I went to Lord of The Fries (veggie and vegan friendly fast food joint) and then met back-up with the hackers at a cafe/bar. And last night I went to the Vegie Bar with my boy Dave, and we met a few others there. One dude was in town all the way from Alice Springs, so that was kinda the reason Dave setup the meeting. Great food and good times. We went out for coffee later!

Enjoy some pics.


-Matt

Bitten

So I had a pretty interesting day. It started off with me missing the tram I was hoping to score, and then taking another tram. But, if I didn't take the alternative one, I wouldn't have seen the dude ralphing into the trash can. Definitely an awesome wake-up for the morning! Well, it wasn't a lot of spew, just some orange crap into the trash can. Looked like he was just spitting when I caught him.

THEN! After work I went to the Victorian Skeptics meeting where Lynne Kelly gave her mega-awesomeness thesis on Stonehenge. Freakin' amazing! I was utterly overcome by the way cool research she has conducted. Amazing speaking skills too. I later realized that my research has an easier means of expressing results, numbers! I can show the efforts of my research via measurements and not historical "facts" that are related against multiple cultures!

After that awesome and quite enjoyable lecture, I decided to walk home. In doing so, I strolled through the Carlton Gardens, it wasn't terribly cold so the walk was rather peaceful. Anyways, I came across two females in the park, apparently possum-whisperers! They were feeding possums in the park! A bunch of Australia-style possums (not the Virginia Possum), some in the tree, the others on the ground. Well, at least one in the tree. One had a baby on its back! Well, I strolled up, quietly, to the girls. I had to greet a possum! One of the ladies gave me an apple to feed the possums. The little critter mistook my finger for the apple and bit me, not hard. It was so cool! It made my night! And you know what, it was a little later after I was back on the trail home, that I realized. Life should have a unique definition per individual. However, as a species, we have a few traits that we have yet to evolve from. Mainly, it seems many of us, including myself, and probably most people in corporate America, turn into robots. Like fearing change, we do the same thing every day. Robot. However, it seems a trait that has been ingrained in our species is that of the enjoyment for sheer experience. So my definition of life is merely the following: experience, and learning. The possums opened my mind!

-Matt

My list of 0x0A Australian Surprises for an American

So I have been here for about 2 months now (arrived on July 16th). I have been asked a few times, what really surprises me about this land. Well, here is just a few, I'll do a non-prioritized list of 0x0A surprises.

0x00: Toilets flush pretty powerful and often have two buttons. This presents a decision to be made when you flush. Press the button for a weak flush or a serious flush. And its all button driven, if there is a user-assisted flushing mechanism. I have even seen pee-walls, which I was not using properly. You stand on the step in front of the wall-urinal and not behind the step. Its not a barrier. Also, the engineering of the flushing system makes testing the Coriolis effect rather difficult.

0x01: It's hard to find free Wi-Fi.

0x02: No corn (high-fructose corn syrup) in Coke. And probably numerous other products. Bread is really easy to buy for a vegan, seems fewer ingredients in the store-bought stuff and they often list the emulsifiers as being "vegetable" emulsifiers.

0x03: Houses do not seem to be insulated. And people comment negatively on this. However, supposedly, newer houses have ameliorated this.

0x04: Maccers. Even McDonalds calls themself this on TV commercials.

0x05: It's called the "toilet," not the restroom or bathroom. So when you gotta burst, you ask for the toilet. Heck, that makes sense. I know it sounds rude, but apparently it's normal and not rude.

0x06: Many seem rather interested in the environment and its wellbeing, environmentally conscious.

0x07: If you have to use the toilet, you best prepare for a walk. A few venues I have been to make finding the ole porcelain beauty a hike, sometimes actually having to go outside the venue to the get to the turd-smuggler.

0x08: DSL is rather common.

0x09: The El Camino style of cars, you know, like a pickup-truck and sedan fornicated and had a hybrid.

0x0A: It's nearly impossible to find brewed coffee at any cafe.

-Matt

I wonder...

Are the constants of the universe signed and susceptible to a negative rollover?

Cap 'n Crunch Frequency

Wow! So I sit here, again, in my room (one of two) in the sharehouse, typing this in vim (no network connection, we just switched DSL providers). The second room I can now have, since Louie moved. That room will probably be my "office." I do have plans to look at two places today. Ideally, I'm willing to part with more money to have a place on my own; however, one of the places is a really cheap apartment (called flat here) with a just one vegetarian guy.

In other news, I went to the local Melbourne 2600 meeting last night! Awesome crew. I had a blast, and a tad different from the HR-2600 meeting (alt site). Difference being that we all met in a cafe/bar, Caffeine at ReVault. Really cool place, about 3 others and myself went out for "cheap" food, which ended up being Thai, and then returned back to the bar/cafe. Tons of Asian places around here. After that we headed back to the cafe/bar, yes I know I just mentioned that (redundancy). Sven (the hostel bud) met up with me there too! Anyways, lots of tech talk, and just meeting people, not unlike the 757 meeting; however it wasn't at a mall, and Tony, the dude running ReVault, keeps the place open till whenever it seems; BTW, he makes a killer long-black coffee. I never put sugar in my coffee, he put some in mine, as it was his version of a long black, I suppose. And you know what, it was really delicious!

Earlier in the week I met up with CapnKernel, Gorilla, and one of my postgrad buds for a local CCHS (hackerspace) meeting, the current space was not available, as the dude who the garage was hosting the meeting was out of town. We had fun, just chilled and chatted stuff at the Jawa Bar (yes a 'w' not a 'v'). I'm such a tight-wad, I didn't spend any money... well I did buy Paul (my postgrad bud) part of a drink. I felt I owed him
since he is so nice and his wife made me awesome pizza (mentioned a few weeks ago in a prior post).

Personal rant follows:
I feel so lame not doing much work on PDFResurrect lately. I have some things in place for a newer version, however I just havent hacked it enough lately mainly to test the idea I have added. Mainly, I want to decompress the XRef tables that PDF's based on spec 1.5 or higher add. This, of course, means adding zlib support. Which is there now, but my handling of the decoded stream is not going as smooth as hoped.

-Matt