Pages

Saturday, August 31, 2013

Cheers Mate

Man! The past three years (a little more) have been amazing. I have met some of the brightest and nicest people on the planet. So, I am moving back to the US. In fact, I sit here now in the Auckland, New Zeeeland airport clicking this out. It's sad to leave, but I can't want to turn on a new adventure. Matt 3.0.

I left with a nice bang though! Last night was the monthly Ruxmonsecurity/hacker talks in Melbourne, and I delivered a talk: "An Organized Talk on Disorder: Defeating Address Randomization to Make the Universe Boring." I must say that it was one of the best talks I have ever delivered. I talked about a technique I discovered to defeat address space layout randomization. Anyways, I have not publicly published anything on this... yet.

I love Melbourne, Ruxmon, and having made some of the best friends, I will miss this/that place. But In three years, I only saw two kangaroos in the wild, no snakes, no drop bears, one big-ass monster spider, and killed a single jar of Vegemite. Good on me mate.

-Matt

Wednesday, August 14, 2013

Non-deterministic Trash Pick-up, or Why a Garbage Collector Might Influence Itself

Determinism is a sexxy property for software verification. Given a known input a deterministic program should produce the same output, consistently. This makes testing trivial, simply match the program's output with what has been previously been determined as the correct output. If the two outputs match, *bang bang* we passed output verification and the PHB is pleased. This is, of course, assuming that the program is void of any side effects that would cause some bit of non-pure/non-deterministic output. For a deterministic program, any unexpected output is a clear sign of a bug. For other types of programs, non-deterministic output can result from the program relying on clock values, random values, or other input which can be hard to replicate in testing (such as mouse or other device interrupts). However, a proper verification setup should have a way to statically set such variables so that the program can have a proper output testing. For instance, seeding the random number generator used in the program to a known value during testing.

I was recently surprised to find one of my memory management test cases producing non-deterministic output, even though the program is trivial and relies on little or few external libraries, and no obvious random or non-deterministic input. Actually, I discovered this a while back, but recently revisited it. Simply, I was gathering data for my thesis work, region-based memory management (RBMM), and found that the garbage collector I was comparing my RBMM system against kept producing different collection counts (the number of times the collector executed during my test case's run). See, both garbage collection and RBMM are forms of automatic memory management and I wanted to see how well my RBMM system compares to the more common garbage collection. My research is based on implementing an RBMM system in Go and then comparing my work against the stable garbage collector that Go ships with.

Anyways, I was able to replicate the effect I had previously witnessed in a simpler test (below) using the Go runtime provided by gcc-4.8.1. Remember that Go is garbage collected, thus its garbage collector was producing different collection counts (NumGC below) for each execution of the test.

package main
import "runtime"

func main() {
    for i:=0; i<10000000; i++ {
        f := new(float64)
        *f++
    }

    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    println("NumGC: ", m.NumGC)
}

Why would Go's collector be producing non-deterministic collection counts? This program obviously does the same thing every execution, and generates the same amount of garbage each execution. Well, a couple things could be happening. Perhaps Go's collector was looking at overall system resources, and not just for the test case, and deciding when to collect. Or, perhaps it uses a random value which might affect collection. As it turns out, the latter was the case. Go, by default, enables some statistics/profiling information during runtime. What tipped me off was that I ran a grep for "rand" within the runtime source and I found the following in its memory allocation function "runtime_mallocgc" located in gcc-4.8.1/libgo/runtime/malloc.goc. Note that I modified the whitespace some:

if(!(flag & FlagNoProfiling) && (rate = runtime_MemProfileRate) > 0) {
    if(size >= (uint32) rate)
        goto profile;
    if((uint32) m->mcache->next_sample > size)
 m->mcache->next_sample -= size;
    else {
        // pick next profile time
 // If you change this, also change allocmcache.
 if(rate > 0x3fffffff) // make 2*rate not overflow
     rate = 0x3fffffff;
 m->mcache->next_sample = runtime_fastrand1() % (2*rate);
 profile:
     runtime_setblockspecial(v, true);
     runtime_MProf_Malloc(v, size);
    }
}

So their profiler is having an affect on the amount of memory pressure on the garbage collector, thus causing the collector to kick-in more often than a non-profiled runtime. So, what does this mean? Well, if you do not need any profiling support (probably not if you are running production) then disable the profiler! What I did, was just that, and then executed my simple test multiple times. Bingo! With the profiler disabled I was able to achieve consistent predictable garbage collection counts from Go's collector. To disable the profiler, simply add this line to your main()

    runtime.MemProfileRate = 0
The latter flag will set the profiling rate to zero, thus the runtime will not collect allocation metadata. Otherwise, this collection of metadata will influence the garbage collector, and that probably is not wanted if you run a production executable (or are performing some verification/testing).

-Matt

Thursday, July 11, 2013

11 Years

That's right faithful readers (all two of you). You have been digesting my blabberings for three years now. I have been in Melbourne for 3 years as of yesterday (July 10)!

-Matt

Tuesday, July 9, 2013

First Class, and I Don't Mean Data

After my trip to Seattle to present at MSPC 2013, which I think went "OK," I headed back to the 757 to chill for a bit, visit my ole dentist, recharge my batteries (I am a machine... duh), and to well just get "home" for a tad. With that said, I did think about garbage collection some, and continued to work on my thesis. But that's probably not a good topic for this post, since the title mentions "First Class," and I don't mean higher-order language constructs.

So the story goes like this: When I was heading back to Melbourne, my flight plan took me from Norfolk, VA to Dallas, and from Dallas to Brisbane. The latter leg, by the way, is the 6th longest non-stop flight according to the wikipedia's entry on longest non-stop flights. Anyways, my Norfolk to Dallas ticket had no seating assignment. I was a bit baffled, but continued to play the game. Anyways, as I get ready to board, the ticket agent at the gate handed me a first class ticket! WTF?!? REALLY!?! Sometimes, you just take things and ask questions later. Anyways, this free upgrade comes with decent coffee in a ceramic mug, a steamed towel to wash my face with (travelling first class is hard work), and a free dinner. I rejected the dinner, because I had a prepared hummus sandwich awaiting me, and they didn't have much vegan awesomeness except for some nuts and salad. Oh, and the nuts come in a ceramic ramekin. The salad was pretty damn first class... and it came with a cloth napkin, freshly pressed rainbow milk straight from the nipples of an albino unicorn, a free yoga lesson, and shiatsu massage given by supermodels on their way to Maui for a photo-shoot. (Just lying about the milk (I'm vegan duh!).

So how did this first class upgrade happen? Maybe they oversold crap-class and had to choose a few suckers to ride pimp style? In fact, my neighbor is pretty cool here. But first class still doesn't score you free wifi. Oh, hold on, the lovely flight attendant is now offering a desert... I have to say no; I think I'll go for more coffee, because my bladder is definitely of infinite volume.

Anyways, I must say that I think the people in first class looked at me and were wondering if I were some rich famous musician, or hacker seeking asylum. I can't really say I am dressed to the nines here. And... my coffee is here; yet another ceramic mug! Oh, and the seat is spacious and I have enough leg-room for me to not even think about using the recliner feature on my chair. Just to think, my butt cheeks are sitting in the same seat that a thousand other well-off cheeks have graced. I am spoiled.

-Matt

Wednesday, June 19, 2013

I met... GCus

The title in this post is pronounced GCus like jesus but with GC. The latter being the abbreviation for Garbage Collection. This post is just to say that I met Richard Jones at PLDI this year (he is the guru of garbage collection) and his work has made up a huge portion of my thesis. He deserves infinite beers. I also chatted a bit with Hans Boehm again. I also met David Gay and Emery Berger, both whom I have cited in my thesis work. It's way cool to see these people, notable names of memory management! Way cool! Oh, and I had Mr. Jones sign a piece of trash for me, effectively he "marked some garbage" ... but since it has been marked, it shouldn't be reclaimed.
-Matt

Monday, June 17, 2013

jmp 0xSeattle

Wow! So that was one helluva flight. Actually, the flights were nice, since the Uni hooked me up with Quantas (I am a cheapskate and probably would have gone with a cheaper option if it were my wallet being genocided-upon by the airline industry). I finally got the chance to watch The Social Network and Tarintino's more recent Django Unchained. All I gotta say is that I was thoroughly entertained and I think I need to see more Tarintino flicks. Anyways, I am in Seattle for the Memory Systems Performance and Correctness (MSPC) workshop to present our research into garbage collection and region-based memory management, black magic, and the digital alchemical fusion of these two aforementioned dark sciences. Anyways, I think I'll go stroll around this city! My stomach cannot hold any more caffeinated beverages.
-Matt

Tuesday, May 14, 2013

Monkeys like Logs

So I needed a way to fight boredom this weekend. So I decided to start work on a new side project. I had an idea that evolved into a pretty simple concept, to create a console program that monitors text files (log files) and displays their most recent line. It was an excuse to do more curses hackery and to take a break from garbage collection and memory management (which I still hacked on anyways :-). With that said, I have an alpha version of the aforementioned log-viewer TreeTop which you can snag here. "Monkeys like trees, climb to the top."

-Matt