Troll

Last night was frikkin' awesome. After I did some research towards my PhD, I went to two Ruxmon lectures given by some people I know, Silvio and Laurent. Great talks. After that, I went to Billboards to catch Finntroll's first tour down here in Australia. They played Brisbane last night. And one word ARRRRRRRRGgggGGGHHHHHH. It was frikkin' nuts. Hummpa/folk/black metal from Finnland mostly sung in Sweedish! Lots-o fun, and the two opening acts, the local Obsidieth provided some nice modern thrash with some folkiness to it, while the Perth-based Claim the Throne played some great battle metal/folk metal.

It was the first time I had ever been to a concert, whereby I first give the venue my ticket, a crappy-printed out ticket, and after the gig they hand out true-printed-out tickets, as if you were to have bought the tickets via mail-order... great memorabilia!

-Matt

Region Based Memory Management

Aside from listening and witnessing some of the most righteous of music (I'm listening to Gogol Bordello right now), and caught some Iron Maiden, Primus, and Slayer at Soundwave last week, what have I been researching, is a question one might be asking themselves. Ok yeah that is one nasty grammatically incorrect piece of English. Well what have I been researching?

Region Based Memory Management! That's right, that is what my PhD is focused on. Sure RBMM is not fresh, but my goal is to implement it for Google's Go language. What I think will be the real unique pieces of research will be how we allocate our regions, dealing with parallization (a'la goroutines) and carrying information across multiple modules (cross-module analysis).

Backup just one second cowboy, neee hawwww! What in the name of doo dah is a region? Region based memory management is a way of managing memory at compile time, one might think of it as compile-time garabage collection. However, that is just not correct at all. At compile-time, via static analysis, dynamic memory allocation calls are located. The compiler can then emit code that will allocate objects that have the same lifetime into regions of contiguous memory. So its a neat little tango between compile-time and run-time communication. Anyways, this grouping of objects with similar lifetimes can benefit cache locality, as well as provide a fast way of deallocating objects, all at once, by just killing the region. That is fast. No need to visit each object individually and free it.

Since Go utilizes a garbage collector, we would like to leave it in place for dealing with cases where regions would live for a long, if not infinite time. Such a case would be when a global object aliases something that is dynamically allocated (in Go that would be via a call to 'new' or 'make'). Garbage collection is traditionally a "slow" process. In addition, collectors can be a burden to real-time systems, as they can slow the program's execution (or even stop it) allowing the collector time to clean-up objects that are no longer being used. Of course, there are parallel garbage collectors, which should not require a stop-the-world approach that traditional collectors implement. But, I am unaware of their actual processing capabilities/limitations.

TL;DR my thesis at this time poses to provide an elusive seductive dance between garbage collection and region based memory management. OhhhhHhh yeaaa mmmmmm mm that sounds like the sexxy.

-Matt

That's a weiner!

Soooooo, I felt like I needed to score a new pair of pants, so I went to the closeout-store and got some cheap-o black corduroys. I need to get rid of my other pants that I do not wear too often, to keep things simple. I'm not a fan of acquiring new possessions. Anyways, so after I scored some pants, I decided to go to the little market store deal. As I made my way to the store, I heard some people cheering. Then.... yes.... then.... I saw two dudes pants-less riding their bicycles. Well, ya know, this is Melbourne, so I didn't think too much of it, other than, right on dude! All this craziness while I'm carrying my new pants, because I do not see the need for the store to waste a plastic bag on me. Then... more... a whole parade, women, men, some with pants, some without, frikkin' naked just riding their bikes down the road. I kinda cheered and waved my pants at them. Welcome to Melbourne. Turns out, today is Melbourne's World Naked Bike Ride. Way-cool. I guess it takes some balls to ride a bike in public.

-Matt

I went to church yesterday, SLAYERRRRRRRrrrrrrrrrrrrRRRR (Soundwave was my church)

Being a music fan, and a lover of attending concerts, I often check the music schedules of places when I travel. When I got to Melbourne I soon learned of the most-awesomest musical orgy in this area, the Soundwave music festival. Well, that was my holy-land, and I proclaimed my pilgrimage would start on March the 4th. Well, yesterday, I was successful. For I have witnessed/experienced once more the love of Primus, Slayer, Iron Maiden, and some Rob Zombie. I didn't see all the shows I wanted to see, heck, there were 6 stages, but I had a blast. Note: Soundwave was one way of forcing myself to stay here in Melbs, even if I didn't like it (I scored my ticket pre-sale). So, my bud Mark picked me up at my house, we then picked up our other friend Ian, and made the pilgrimage. While things were already kickin' (the shows started at noon, we arrived at 2PM), we basically saw: DevilDriver, All that Remains, Primus, High on Fire, Murderdolls, Ill Nino, Slayer, Rob Zombie (very little of it), Queens of the Stone Age, and Kylesa.... ohhh yeah almost forgot... Iron Maiden!!!!!!!!!!! Some of the shows I have listed we did not see in entirety. But it was a blast! When Slayer hit the stage, awe man, it was crushing! The likes of data compression would have been impressed on how much space was compressed in so little time. People cover big area, slayer, people now in tightly packed area. Like one giant pulsating organism. Slayer is magic.

Much love

-Matt

Goin' back to...

Just got back from the Mother Land. That's right peoples, I just traveled to the USA. I'm back here in Melbourne now. So, the trip was fast (left Oz last Monday the 21st around noon). The cool piece of this deal was that I left at noon that Monday, arrived in Cali-for-ni-a (the home of the Governator) the same day at 2PM. Like a super-crazy worm-hole. In-fact, many abductees claim the extraterrestrial abduction was responsible for their time shift. But, I am pretty sure, science can explain the loss in hours, I think it was probably do to flying against the international dateline. None-the-less, just a mere 2 hours after I left, I arrived in LA, but on a ~14 hour plane flight. Anyways, flying home that following Thursday, and just got back in today... Saturday... freaky. Anyways, California is mega-sweetness. I crossed over the Golden Gate Bridge.... but no jumpers.

-Matt

Acca Dacca Lane and More

SoooooooOOoOoOoOoOOooOoOo.... posted pictures, I have. Enjoy.
http://www.flickr.com/matt-davis

Linux syscall, vsyscall, and vDSO... Oh My!

The following article is a brief investigation I wrote up, which looks into the system call functionality of the Linux kernel. Mainly, I was trying to clarify the difference between vsyscall and vdso. This was conducted, more or less, on 2.6.32 and 2.6.37 branches, if I recall properly. Anyways here goes:

-= What are System Calls =-

System calls are routines that communicate directly with the operating system in hopes of attaining some specific piece of information, or to make a specific request that the OS needs to fulfill. For example, gettimeofday() is a request often from user-land for an application to obtain the current timing information from the operating system's kernel. In Linux this call is implemented as a system call. Often this interface exists as a means of fulfilling a request by a user for kernel information. This interface allows a lesser privileged application to access higher-privileged kernel information [1, 2].

Often these calls are not even accessed directly by an application, rather they are executed via a wrapper. The GNU C library, glibc, has wrapper functions that do all the handy-dandy wrapping. For instance, a call to gettimeofday() in an application is really just a call to glibc's wrapper for the system call for gettimeofday(). There is no overhead because the wrapper, at link-time, just associates gettimeofday() to the system's appropriate version of the routine. If one were to desire to make a true system call, avoiding the wrapper, Linux provides a syscall() routine allowing such. Both wrapper and the explicit syscall versions of gettimeofday() are demonstrated below:


#include <stdlib.h>
#include <sys/syscall.h>
#include <sys/time.h>

void main(void)
{
    struct timeval tv;

    /* glibc wrapped */
    gettimeofday(&tv, NULL);

    /* Explicit syscall */
    syscall(SYS_gettimeofday, &tv, NULL);

    return 0;
}


System calls are loaded at kernel boot-time. All of these calls are accessed by a number. In the example above SYS_gettimeofday is just a constant integer. And this integer is the index into an array (called an interrupt descriptor table) of system calls that are constructed at boot-time. This table/vector can be thought of as pointers to the actual routines [3]. So at index SYS_gettimeofday is a pointer to a piece of code which is where the actual sys_gettimeofday() routine exists.

-= Overhead =-

Originally, invoking a syscall in Linux was actually a pretty expensive process, as it was implemented as a system interrupt (int 0x80). When the syscall interface was called, via the "int 0x80" instruction, the CPU would pass control to the OS. The OS, would look at what value was passed in, such as SYS_gettimeofday, and then the interrupt vector would be indexed and gettimeofday() would get called. Interrupts force the CPU to save the state of execution just before the system call was executed and the system interrupted. This state is restored after the interrupt (in this case a syscall) completes.

Ok, so interrupts are relatively cheap in execution time. However, the way the kernel is designed does add some overhead when a syscall is executed. Linux is divided into two primary memory segments. User-space and kernel-space (userland, kernelland). User-space memory is that which user applications run in. Kernel-space is where all the kernel services run. This segmentation acts as a security barrier, so that crafty and/or malicious user apps cannot directly access the kernel's memory. Making a syscall, as mentioned previously, is just a bridge, a mere wormhole, between these two segments of memory. It is this hop between address spaces that causes quite some overhead, as the kernel must switch between user and kernel-land memory segments, and then back again as the syscall completes [5, 6]. Changing the memory addressing requires some register shuffling, and just imparts more overhead on the whole syscall process.

-= vsyscall and vDSO =-

To reduce the overhead of hopping between user and kernel spaces, a newer mechanism in Linux allows certain syscalls to be accessed directly from userspace, without the need to cross the user/kernel space barrier. This is just what the vsyscall and vdso (Virtual Dynamic Share Object) interfaces do. At boot-time a page of memory is dedicated to containing a subset of syscalls, deemed safe to execute from
userland, that should not cause a security hole for the kernel. The page of memory where these calls lies is mapped into each running process' user-space. Thus, when a call to one of these syscalls is made, no context switch between the memory regions of user and kernel-space is conducted, thus less overhead.

Another interesting means of reducing syscall overhead comes specific to the underlying CPU architecture. Both the more recent AMD and Intel chips have implemented a fast syscall functionality. Instead of issuing an interrupt, programs can issue instructions (SYSCALL/SYSENTER and SYSRET/SYSEXIT) that act faster than a traditional interrupt. The usage of these are based on object code in the OS. Therefore, a programmer does not have to consider how to implement/request the use of a SYSCALL/SYSENTER over a traditional "int 0x80" [1]. When applications are built, based on the architecture and the system, vsyscall and vdso linkage is done automagically.

As demonstrated above, by using the syscall() routine, a traditional syscall will be conducted, even if there is vDSO support (virtual Dynamically Shared Object). However, despite this fact, that call might still be using the newer SYSCALL/SYSENTER CPU instructions. The glibc wrapped gettimeofday() call is what most programs would use. Since the kernel has been designed to use the most efficient mechanism of syscall, that version has the potential to be a virtualized syscall that is mapped into userspace.

To determine if a specific call is using a virtualized (user-space) syscall or a traditional, memory segment-shuffling, syscall, the strace utility can be used. If a true traditional syscall is being conducted, the routine will be output by strace, will look similar to the following:

gettimeofday({1297472587, 581519}, NULL) = 0


According to comments in glibc-2.12.1: "The vsyscall page is a virtual DSO (Dynamic Shared Object) pre-mapped by the kernel" [7].

vsyscall and vDSO are similar in how they work, however there are some slight differences. vsyscall is limited to 4 entries, and is static in memory. Therefore, any statically linked applications can guarantee where vsyscalls are loaded. On-the-other-hand, vDSO is dynamically loaded into the user process, therefore it is not predictable due to Linux's randomized address space layout. If more than 4 vsyscalls are needed, then a vdso should be used instead [8].
For example, run `cat /proc/self/maps` and look at both the '[vdso]' and '[vsyscall]' entries. If your system supports these, the memory range for vDSO is different for each process issued, and vsyscall is totally predictable. If you dont believe me, run 'cat /proc/self/maps' a few times and note the addresses of vdso and vsyscall. Since this example is looking at '/proc/self/maps' the memory mappings displayed are for that 'cat' process [9, 10].

[1] http://en.wikipedia.org/wiki/System_call
[2] Linux User's Manual: intro(2)
[3] http://www.tldp.org/LDP/khg/HyperNews/get/syscall/syscall86.html
[4] http://en.wikipedia.org/wiki/Interrupt
[5] http://en.wikipedia.org/wiki/Kernel_(computing)
[6] http://www.linux.it/~rubini/docs/ksys/ksys.html
[7] glibc-2.12.1
[8] Linux Kernel 2.6.37 arch/x86/kernel/vsyscall_64.c
[9] http://anomit.com/2010/04/18/examining-the-linux-vdso/
[10] http://www.trilithium.com/johan/2005/08/linux-gate/

-Matt