tag:blogger.com,1999:blog-53516156743553488142024-02-08T16:38:36.329+11:00DavisDoesDownUnderTesting gravity on the other side of the sphereMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.comBlogger153125tag:blogger.com,1999:blog-5351615674355348814.post-39081971772131319562013-08-31T16:27:00.000+10:002013-08-31T16:27:59.089+10:00Cheers MateMan! 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.
<p>
I left with a nice bang though! Last night was the monthly <a href="http://www.ruxmon.com">Ruxmon</a>security/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.
<p>
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.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com3tag:blogger.com,1999:blog-5351615674355348814.post-64320224317786755302013-08-14T22:01:00.001+10:002013-08-14T22:09:22.753+10:00Non-deterministic Trash Pick-up, or Why a Garbage Collector Might Influence ItselfDeterminism 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 <a
href="http://en.wikipedia.org/wiki/Pointy-haired_Boss">PHB</a> 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.
<p>
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 <a href="http://www.golang.org">Go</a> and then comparing my work against the stable garbage collector that Go
ships with.
<p>
Anyways, I was able to replicate the effect I had previously
witnessed in a simpler test (below) using the Go runtime provided by
<a href="http://gcc.gnu.org">gcc-4.8.1</a>.
Remember that Go is garbage collected, thus its garbage collector was
producing different collection counts (NumGC below) for each execution of the
test.
<pre>
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)
}
</pre>
<p>
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:
<pre>
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);
}
}
</pre>
<p>
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()
<pre>
runtime.MemProfileRate = 0
</pre>
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).
<p>
-Matt
Matthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com4tag:blogger.com,1999:blog-5351615674355348814.post-21319823751646092562013-07-11T09:54:00.006+10:002013-07-11T09:54:58.381+10:0011 YearsThat'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)!
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com1tag:blogger.com,1999:blog-5351615674355348814.post-75535405566640899912013-07-09T15:49:00.004+10:002013-07-09T15:51:02.582+10:00First Class, and I Don't Mean DataAfter 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.
<p>
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 <a href="http://en.wikipedia.org/wiki/Non-stop_flight#Longest_flights">wikipedia's entry on longest non-stop flights</a>.
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!).
<p>
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.
<p>
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.
<p>
-Matt
<br/>Matthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-12811640545199283542013-06-19T14:40:00.000+10:002013-06-19T14:40:52.899+10:00I met... GCusThe 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 <a href="http://gchandbook.org/">Richard Jones</a> at <a href="http://pldi2013.ucombinator.org/">PLDI</a> 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 <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Hans Boehm</a> 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.
<br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com1tag:blogger.com,1999:blog-5351615674355348814.post-17661693865572755252013-06-17T04:12:00.001+10:002013-06-17T04:21:15.530+10:00jmp 0xSeattleWow! 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 <a href="http://www.imdb.com/title/tt1285016/">The Social Network</a> and Tarintino's more recent <a href="http://www.imdb.com/title/tt1853728/">Django Unchained</a>. 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 <a href="comparch.gatech.edu/hparch/mspc2013/program.php">Memory Systems Performance and Correctness (MSPC)</a> 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.
<br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-50771204253181682752013-05-14T09:50:00.001+10:002013-05-14T16:52:38.158+10:00Monkeys like LogsSo 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 <a href="https://github.com/enferex/treetop/">TreeTop which you can snag here</a>. "Monkeys like trees, climb to the top."
<br/><br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-90203169532186778562013-04-30T22:45:00.001+10:002013-04-30T22:47:46.798+10:00Seattle and NachoWell, the paper my advisers and self have been laboring over was submitted and accepted to the <a href="http://comparch.gatech.edu/hparch/mspc2013/index.php">ACM SIGPLAN Workshop on Memory Systems Performance and Correctness</a> (which is in Seattle this year). More so, I wrote the original draft (with some incomplete pieces). It ended-up being rewritten by my advisers (and a ton of things were added!). Needless to say, it represents hours and hours of work, and composes ideas from their genius. It was great to work on this paper with them, and I am humbled that it was accepted. I have been implementing code for ages now to represent these ideas, basically a combination of region-based memory management and garbage collection.
<br/><br/>
On another front, I have been working on more PDF hackery. I wanted to make a PDF-grepping utility. I have a basic implementation cooked-up but the key piece is the simplistic PDF text-extraction library that I wrote (note that it is not fully featured and does not account for all encodings and compression schemes). I present upon the world <i>libnachopdf</i> because it ain't yo' PDF. Well, maybe it is your PDF, but that doesn't matter. <a href="https://github.com/enferex/libnachopdf">Get 'yo nacho on over here</a>.
<br />
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-30883576142005352032013-04-15T10:28:00.000+10:002013-04-15T16:06:16.506+10:00I miss industry...So many of you are probably wondering, because I know I am the keystone in your lives, what is Matt up to? Well, not much, just some thesis writing and stuff. Yes, I am being vague. Anyways, I am ready to knock this PhD out. I have had fun, but personally I find industry more fulfilling, and I long for the day where I can return to that. With that said, here is what trying-to-get-a-PhD looks like.
<a href="http://i.qkme.me/3twske.jpg" imageanchor="1" ><img border="0" src="http://i.qkme.me/3twske.jpg" /></a>
<br/>-Matt
Matthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com1tag:blogger.com,1999:blog-5351615674355348814.post-48768221749489320582013-03-16T12:00:00.000+11:002013-03-16T12:06:18.209+11:00UniWireless and ArchLinuxNo, this is not a memory-management related post. With that said, I decided to actually spend some time and try to get my Linux box running on the the <a href="https://its.unimelb.edu.au/help/networks-access/networks-internet/connect-wireless/uniwireless">University of Melbourne's wireless network</a>, as they do not have much help regarding low-level settings, at least I didn't seem to find too much help on the aforementioned site. The links at the end of this post are what got me rocking. Personally, I run <a href="http://archlinux.org/">ArchLinux</a> with <a href="https://wiki.archlinux.org/index.php/Netctl">netctl</a> (as a replacement for <a href="https://wiki.archlinux.org/index.php/Netcfg">netcfg</a>). The syntax that both of the aforementioned network configuration utilities use is similar. Simply, here is my config, I have a feeling this is going to be similar for many other institutions. Please note that I have not spent any time to tweak or remove any redundant options below.
<br />
<pre style="color:white;background-color:grey;">Interface=wlan0
Connection=wireless
Security=wpa-configsection
IP=dhcp
ESSID=UniWireless
WPAConfigSection=(
'scan_ssid=1'
'ssid="UniWireless"'
'key_mgmt=WPA-EAP'
'eap=PEAP'
'identity="MrSexxy"'
'password="ILikeGoats"'
)
</pre>
And that's it. Of course, you will need to use your proper uni username and password (the same one you use when logging into the library's online database). Please make sure the permissions on this file are proper so that any-old user cannot read your password.
<br /><br />
The <a href="https://its.unimelb.edu.au/help/networks-access/networks-internet/connect-wireless/uniwireless/guides">uni's website</a> mentions that students can use either a manual or automatic proxy. I choose the manual, which will also request your username/password again. With that said chromium supports both th automatic (pac) proxy configuration and the old-school manual configuration (as follows):
<br />
<pre style="color:white;background-color:grey;">chromium --proxy-server=wwwproxy.student.unimelb.edu.au:8000</pre>
... Now fire them torrents up (oh, yeah, I'm pretty sure you are being watched).
<br />
Special thanks to these very insightful/helpful posts.
<br />
<ul>
<li><a href="https://github.com/joukewitteveen/netctl/blob/master/docs/examples/wireless-wpa-configsection">https://github.com/joukewitteveen/netctl/blob/master/docs/examples/wireless-wpa-configsection</a>
</li>
<li><a href="https://bbs.archlinux.org/viewtopic.php?id=150701">https://bbs.archlinux.org/viewtopic.php?id=150701</a>
</li>
</ul>
<br />
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com2tag:blogger.com,1999:blog-5351615674355348814.post-23423428375864384532013-03-10T08:48:00.000+11:002013-03-10T08:59:46.104+11:00From the MothershipLast night I went to see the god of funk, <a href="http://georgeclinton.com">George Clinton, along with the Parliament Funkadelic</a> at <a href="http://www.billboardthevenue.com.au/">Billboard</a>. Fantastic show. It's funny, I was thinking, due to being asked: What is it about funk/soul that I like... I mean, I am a metal head, love some blues, and have an inner hippie in me (I dig jam rock). Well, I don't think humans know why they <i>really</i> like something. Sure, I like music that was generated using some bit of talent, and sprinkled with creativity. But, really, why does a person really "like" something? I think it's hard to answer in words... "I like it just because!" It's probably the result of some brain/chemical order in the head.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com1tag:blogger.com,1999:blog-5351615674355348814.post-84223834122406604062013-03-03T23:13:00.003+11:002013-03-03T23:13:29.297+11:00Bird Trajectory MiscalculationI personally believe that we as humans take many things in nature for granted, or we just totally ignore them. I have to say, I do not believe that many people consider how awesome birds are. But, they are not perfect. Have you ever wondered: do birds ever screw-up? Surely they must. They are not born bad-ass fliers. They have to learn. They are animal, as we are too. With that said, I am sure that even the most experienced of our avian friends mess-up their calculations on occasion. I am sure that it is not uncommon for an experienced bird to over-correct, or possibly approach a landing site too fast. Do their wings ever get cramped mid-flight and just stop functioning like a <a href="http://en.wikipedia.org/wiki/Boeing_777">Boeing 777 </a>down a man and running on one engine? Sure, they are animals, and subject to some kind of mean-time between failure. Well, as I was leaving uni today a bird just hit me in the head. It wasn't firm or painful, more like a bump. Maybe it was an accident? I should have contacted FAA. Anyways, my hair is a bit frazzled, but it doesn't really look like a nest. Now, it is common for magpies (and other birds) here to attack dogs and people (especially cyclists). In fact, the gov't maintains a <a href="http://www.dse.vic.gov.au/plants-and-animals/native-plants-and-animals/problem-wildlife/swooping-birds/swoop-off-kit">"Swoop-off" website</a> where you can download eye pictures to put on your cycling helmet. Often, you will see cyclists with zip-ties sticking out of their helmets for protection from the swoop. Well, I was walking, no helmet, and no eyes on my head. This little bird either decided to attack me, miscalculted one of the numerous variables required for safe and accurate flight, or got a cramp. Either way, I was humbled as nature ran into me.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com1tag:blogger.com,1999:blog-5351615674355348814.post-12329086534234112072013-02-12T11:28:00.001+11:002013-02-12T11:42:32.471+11:00Picking up the Trash and Caller vs Callee Saved RegistersSo there are a few posts around the internet about caller vs callee saved
registers. Just check my references at the end of this post. Basically, I
want to define in a concise way what the difference is and why I'm blabbering
about stuff that most developers do not have to consider.
<p>
To me the difference between caller and callee saved registers matters. Why is
that? Well, for one, I am writing a garbage collector and registers along with
stack variables and global variables make up the root-set. The root-set is a
set of variables that the garbage collector knows about and it is where the
collector begins tracing. In short, for each variable in the root set, the
collector follows any pointers that variable might have. For any variable that
can be reached, starting from the root-set, that variable is said to be alive, and
its memory cannot be reclaimed. Any variables not found through tracing can
have their memory reclaimed. There it is, garbage collector 101, see you next
semester.
<p>
As I mentioned, registers make up the root-set. Since the registers can contain
pointers to data that was allocated, it is necessary to trace them at garbage
collection time. If that allocated data can't be reached, the collector can recycle it and
conserve memory resources. But an interesting thing occurs, and this is based on calling
convention, how the compiler (or assembly-level programmer) constructs calls to
functions. Some registers must be traced and some should be ignored. This, my
friends, is the difference between caller and callee saved registers. The callee-saved registers must be traced. You will see why in just a jiffy!
<p>
These caller vs. callee registers are
defined by the calling convention such as the Sys-V ABI for Intel Processors
and/or another calling convention standard. For instance, the former is similar
to the cdecl calling convention, and is the convention we will investigate here,
as my work space is gcc and it constructs programs in a somewhat similar manner (similar enough to convey the message in this post). These conventions specify how certain registers are to be used. Since registers
are global, all functions can see and access/modify them. So, it goes to say
that specifying which registers a callee (subroutine) function can manipulate
and which registers a caller must save is probably a good thing. As there are
times where a caller wants to reclaim data it never stored on the stack, but
left lying around in a register.
<p>
A <i><b>caller-saved register</b></i> is a register that a calling function must save before
it calls any other function. As the other function, the callee, can use this fiddle
with the register. These are "volatile" and if the data is not stored
elsewhere before a function call, they could be lost. That is why these
registers are typically stored on the stack.
<p>
A <i><b>callee-saved register</i></b> is a register that a callee must preserve if it wants to
further use the register to store other information. A non-volatile register.
<p>
Given my environment (linux on a x86-64bit CPU and compile using gcc), and according to my references the caller and callee saved registers for such a configuration are as follows:<br/>
<b><i>Caller-saved registers:</i></b> rax, rcx, rdx<br/>
<b><i>Callee-saved registers:</i></b> rbp, rsp, rdi, rsi, rbx, r12, r13, r14, r15, rip
<p>
This is a pretty clear distinction, but a simple example goes a long way... here
goes, in pseudo-assembly code. The function foo adds 123 to 456 and then calls
bar. The result of calling bar is then added to 123 + 456:
<pre>
# Comments:
foo: # Function foo entry
mov 123, rax # rax = 123
add rax, 456 # rax = 123 + 456
push rax # Caller saved
call bar # bar()
pop rbx # Restore the saved value (123 + 456 or 579)
add rax, rbx # rax = rax + rbx (whatever bar returned + 579)
</pre>
The common calling convention here cdecl, which is similar to the SysV ABI for
Intel and what gcc uses, mentions that return values are stored in the rax
register. rax is a caller-saved register, it's volatile. If foo
doesn't save it, bar might fiddle with it and change its value. While I don't
show a body for bar, suppose it uses register r12 to do some of its math.
r12 is a callee-saved register, meaning that the data in r12 is preserved by
the callee. Suppose bar looks like:
<pre>
bar:
push r12 # Saving whatever is in r12
mov 789, r12 # r12 = 789
add r12, 42 # r12 = r12 + 42
mov r12, rax # rax = r12
pop r12 # Restore r12
return # return rax
</pre>
A keen eye will notice that r12 is being used in bar as a callee-saved
register, as what the calling convention requires. bar is free to use r12 but
it must restore it before it returns. This means that foo does not have to push
anything to the stack, in fact foo could be written as follows:
<pre>
foo: # Function foo entry
mov 123, rax # rax = 123
add rax, 456 # rax = 123 + 456
mov rax, r12 # rax is caller saved
call bar # bar()
mov r12, rbx # Restore the saved value (123 + 456 or 579)
add rax, rbx # rax = rax + rbx (whatever bar returned + 579)
</pre>
Instead of pushing to the stack, foo in this case knows that r12 is a callee-saved, non-volatile, register and makes use of that fact. Now, a keener eye might be saying, well... foo might be a callee of another function. Maybe main called foo well, yes, foo should follow convention and preserve r12.
<p>
This is the message for garbage collectors. The garbage collection function is called (probably from the memory allocator, when it notices that memory is low). When the collector function begins to execute, it knows of the callee-saved registers as the caller should have already stashed the data it cared about on its stack or in a callee-saved register.
<p>
A few ways to programmatically access the registers is via the setjmp, sigsetjmp, and/or ucontext glibc function calls.
For instance, the sigsetjmp is one method that the Bohem collector uses to access registers for his garbage collector (libgc). If you were to look at the setjmp family you would learn that it returns only callee-saved registers, and not the full register
set. Why is that? setjmp stores the environment into a structure. This includes just the callee-saved registers, since the caller should have preserved its caller-saved registers onto the onto the stack or in a callee-saved
register. Consider the flow: main() --> functionA() --> functionB() --> setjmp(). setjmp would return the callee-saved registers and functionA can make use of these. As the registers values relevant for main, and functionA would be
stored elsewhere (stack or callee-saved).
<p>
I am pretty sure this post is not free from flaws, but I hope it made sense, or that any flaws do not crush the integrity of the data in this post. Thanks for reading.
<h2>Resources:</h2>
<ul>
<li> Defined: <a href="http://zhongshugu.wordpress.com/2011/02/23/caller-save-registers-and-callee-save-registers/">http://zhongshugu.wordpress.com/2011/02/23/caller-save-registers-and-callee-save-registers/</a>
<li> Defined: <a href="http://msdn.microsoft.com/en-us/library/6t169e9c(v=vs.90).aspx">http://msdn.microsoft.com/en-us/library/6t169e9c(v=vs.90).aspx</a>
<li> Defined: <a href="http://stackoverflow.com/questions/9268586/whats-are-callee-and-caller-saved-registers">http://stackoverflow.com/questions/9268586/whats-are-callee-and-caller-saved-registers</a>
<li> Defined: <a href="http://pdos.csail.mit.edu/6.828/2004/lec/l2.html">http://pdos.csail.mit.edu/6.828/2004/lec/l2.html</a>
<li> Calling Convention:<a href=" http://en.wikipedia.org/wiki/X86_calling_conventions#cdecl"> http://en.wikipedia.org/wiki/X86_calling_conventions#cdecl</a>
<li> Calling Convention: <a href="http://www.delorie.com/djgpp/doc/ug/asm/calling.html">http://www.delorie.com/djgpp/doc/ug/asm/calling.html</a>
<li> ABI: SystemV Application Binary Interface for Intel386 Architecture
Processor Supplement, Fourth Edition
<li> Bohem Collector: <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/#details">http://www.hpl.hp.com/personal/Hans_Boehm/gc/#details</a>
<li> <a href="http://www.gnu.org/software/libc/">glibc-2.14 Source Code</a>
</ul>Matthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-17879911471656535662013-02-04T20:18:00.000+11:002013-02-04T20:18:20.083+11:00TBL in MelbSo I was lucky enough to hear the highly regarded <a href="http://en.wikipedia.org/wiki/Tim_Berners-Lee">Tim Berners-Lee</a> speak here in Melbourne today. In fact, it's kinda neat that I have his name hyper-linked in the previous sentence. His talk covered openness of data and the <a href="http://en.wikipedia.org/wiki/Aaron_Swartz">Aaron Swartz</a> story. I wanted to ask a few questions, but I held off. I wanted to know what browser he uses, and what are the content/site(s) he has loaded-up in his browser. I also wanted to ask if he composes html-formatted email (a sure sign of the devil). Anyways, that's it for this post.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com2tag:blogger.com,1999:blog-5351615674355348814.post-5793398584477539022013-01-14T21:40:00.000+11:002013-01-15T10:01:29.754+11:00History LessonSo I caught up with some Swedish badassery last night. That's right my sexxies (you the reader) I got my ass handed to me by <a href="http://www.sabaton.net">Sabaton</a>. Ok, in all honesty, I didn't rock out too hard, I took it easy, no mosh pits for me. I just chilled and enjoyed watching everyone else rock their asses off. It was like a history lesson, delivered in metal. Take the song <a href="http://www.youtube.com/watch?v=oOCe2Y7iVF8">Cliffs of Gallipoli</a>, which has a <a href="http://en.wikipedia.org/wiki/Gallipoli_Campaign">special significance to Australians</a>. Great show! The openers, <a href="http://www.eyefear.com">Eyefear</a> and <a href="http://www.blackmajesty.com/">Black Majesty</a>, both whom I have seen before, also kicked ass. Lots of asses, lots of kicking. Oh, and to the dude dressed as a WWI ANZAC soldier: your uniform kicked butt!
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-78121823126937345122012-12-31T11:27:00.003+11:002012-12-31T11:30:26.930+11:003...2..1... Collect the Trash!Ok so y'all probably remember wayyyyy back in October when I was discussing
writing a garbage collector. Well, I really don't expect you to remember that.
"You" being the pronoun referring to my two subscribers (one being a stalker). Ok,
yeah I flatter myself, in reality, it's probably not a stalker of physical
attraction, rather a psychotic blood thirsty individual. *waves*
<p>
Well, why do I want to dance with a garbage collector? Isn't that the
evil-bastard-child/antithesis to region based memory management (RBMM), what I
have been working on the past two years or so? Nope! Garbage collection can
be a compliment. See, RBMM works by analyzing a program at compile-time (my
system uses a gcc-plugin). From this analysis the compiler can insert
memory allocation and reclaim calls (think malloc/free) at compile time. My
system automatically free's memory, based on which objects point to which other
objects. These groupings of objects can come from the same region of memory. A
region cannot be reclaimed until all objects in it are no longer needed. Then,
in one quick swoop, the memory of the region (the space that all the objects
take-up) can be reclaimed. This fast memory reclaim is a key benefit of
RBMM, as there is no need to visit each object and reclaim its memory
individually.
<p>
Unfortunately, not all object lifetimes can be decided at compile time, such as
global variables, or values pointed to/aliased by globals. This means that some
objects cannot be reclaimed based on a compile-time static analysis. If these
undecidable-lifetime objects are in a region, then that region lives for the
entire lifetime of the program. Static analysis cannot force a region to die,
unless it can be 100% sure that the region contents (objects) are never
needed again. Global nastyness creates region bloat, as some objects might be
reclaimable, and not others. As I previously mentioned, a region cannot be
removed until ALL of its objects are no longer alive. If a global variable pops
into the region, then that region now lives forever. Like a virus.
<p>
The above issue means that a garbage collector can actually benefit an RBMM
system. That is what I have been working on: a combining of RBMM and garbage
collection. This is not unique, and has been done before; however, the way we
implement our collector is unique, but that is not discussed in this post.
<p>
Disclaimer: Grammar nuts please note that this is a blog post, so I am immediately relieved of any misuse of narrative modes. This is a design for my PhD and something that I have worked on with my advisers quite a bit (the "we"). The code is mine.
<p>
What I want to discuss in this post is how we locate stack variables. Stack
variables form a subset of the root-set. The root-set being a collection of
variables that are live at the time of garbage collection. If any data is
accessible through the root-set then that object is also alive and must survive
garbage collection. Else, the memory for data/objects that is not reachable can
be collected. I will not go into details, or even the collector type I have
chosen (e.g. mark-sweep, or copy, etc). Instead, I just want to talk about
finding the stack variables; as I said a sub-set of the root set. Globals and
registers also can be part of the root-set, but this post is only about stack
variables </redundancy>.
<p>
When the garbage collector kicks-in the collector needs to start somewhere. It
starts by scanning the root-set. Well, how does the collector get this root
set? Specifically, what this post is concerned with is obtaining a sub-set of the roots,
the stack variables. If you are familiar with stack-frames or activation
records, the values there in the stack must be scanned. If any of those
variables point to objects dynamically allocated (e.g. heap variables or
variables from a region), then such objects must survive collection, and
their memory cannot be recycled.
<p>
I have implemented a compiler modification (gcc-plugin) which provides hints to
the garbage collector as to how to trace the stack of the program. This is how
the collector gets the subset of the root-set, the stack variables. Actually,
it is so cool and nifty I warranted this entire blog post to the notion.
<p>
My aim is to provide, at compile-time, a table that can be read by the garbage
collector at runtime. During compile-time, as the source-code is being
processed my plugin locates all function calls in the program. At the return of
each function call a label is inserted (think assembly goto/label). This label
is unique for each callsite, and makes up the key into a table that I am
building. This key points
to information about the function that the label is inside. For the example
just below, the three labels are unique, but all point to the same function
information. Information about my_function(), which specifies what local
variables it has (x, y, z), if the variables are pointers, and how big the
variables are.
<pre>
void my_function(void)
{
int x;
float y;
double z;
foo();
__label0:
bar();
__label1:
baz();
__label2;
}
</pre>
The function above has three callees (foo, bar, baz). At each call site,
my plugin inserts a label. Now, why do I insert labels? Well, at runtime we
need a way of associating the return point for each function call (foo, bar,
baz). At compile time I do not have any addresses to use, hell, addresses are
created by the OS when the executable is loaded; we haven't even finished
compiling the source code yet! The solution is to insert a
label which can be used at compile time to build a table of stack-variable
information. The loader will fix-up the addresses, and at runtime the labels
will have the correct address that the function call returns to. Recall that
each time a function is called, the return instruction pointer RIP or return
address will be stored on the stack. This value will be the same as the
respected label. For instance, consider that my_function() is being executed,
and the line which calls bar() is executed. When bar() gets called, the return
point, which now happens to also match __label1, is placed onto the stack. And
when bar() returns, the return point is now the same as __label1. The only
thing we have done so far is insert labels. No big deal. Note: I doubt anyone except for maybe one person has read this far, if you do, email me, you kick so much ass, that next time we meet, I will buy you coffee produced from the most lavish and rare of coffee seeds: unicorn digested coffee. I will then serenade you with a ear-piercing song and proclaim you Captain Badassery and dance around bear-chested wearing a Burger-King crown and throw pennies at your feet.
<p>
As mentioned, the labels are entries into a table that contains function
information (variables, stack size, etc). When the garbage collector
kicks-in, it looks at the stack and locates the return point. That value is
a key into a function table my plugin generated, remember the RIP coincides
with the added labels. The collector uses the RIP/label as a key to get
function information, and then processes
the variables (figuring out which heap values can be accessed though the local
variables in that function). Once that function is scanned, its caller
function is scanned, and so on... it's turtles all the way down... until the collector
hits main(). Then this portion of garbage collection is complete.
<p>
TLDR; Anyways, the above diatribe is an expose into the use of labels for providing a
means of accessing stack variables, and providing a compile-time generated way
of performing a runtime stack trace.
<p>
Have an awesome New Year and may all of your garbage be collected properly!
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com2tag:blogger.com,1999:blog-5351615674355348814.post-28474680582306484642012-12-24T11:27:00.001+11:002012-12-24T15:49:44.713+11:00Have a Happy Astrophysical Season!Happy holidays. Just to inform y'all, my true holiday, the science holiday (which I totally forgot to celebrate), the solstice, was 3 days ago. It happens to be that the aforementioned day also marks the start of the Summer down here in the underworld. And... whooo whee, yesterday, the second day of summer was a blaze. So, frikkin' hot; it was as if you could just bottle up the heat, and drink it. Anyways. Much love, enjoy whatever holiday you celebrate.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-16595015785570080762012-12-04T21:23:00.000+11:002012-12-04T21:23:16.796+11:00What What?! More Graffiti!So, I decided to change pace this past Sunday and go out in the morning, grab coffee, chill, and take some pics. I ended up lounging out at Federation Square, listening to an acoustic guitarist at the Fair Trade Festival. On my way there, I went down Hosier Lane and took some pics of the awesome graffiti. Check out the pics on <a href="http://www.flickr.com/photos/matt-davis/">my flickr (pictures uploaded on December 4, 2012)</a>.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-89279491076011961072012-11-30T12:04:00.000+11:002012-11-30T12:04:00.871+11:00New Version of PDFResurrect... Now with enhanced EOF locating.The title, while any computer scientist will immediately think is a joke... is in-fact not a joke. The latest release (Version 0.12) is a bug fix release and is now available <a href="http://757labs.org/wiki/Projects/pdfresurrect">here</a>. The main fix regards how the tool was locating the EOF token that PDF writing utilities place at the end of different versions of PDFs. Previously, if an EOF token was split across a 256-byte boundary, then Mr. Resurrect would not have found it. The new algorithm might be a tad slower; however, it is more precise.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-55105970774406993192012-11-26T22:40:00.001+11:002012-11-26T22:40:09.161+11:00Answering a begging question... what does the heap look like?So I was curious. What does a process' heap look like? If I were to take a hint from conservative garbage collectors, and scan the memory of a process, what would it look like? Well, to answer this, I threw together some software <a href="http://github.com/enferex/heaptropy">here</a>, and ran a few GNU programs to see what they look like. I then try to relate memory allocation calls with the heap layout. The conservative garbage collector hint I used was merely the following. When my tool scans the heap, address by address, if the value at each address looks like another address residing in the heap, then my tool says the heap address points to the other address. Anyways the results are munged to crap out a .dot file. More details and such are <a href="http://users.757.org/~enferex/heapscan/">here</a>.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-24610677974682065702012-11-18T17:24:00.001+11:002012-11-18T17:24:42.914+11:00Syntax Party 2012Wow. So I decided to make it down to the <a href="http://www.syntaxparty.org">Syntax</a> party 2012... a Melbourne demoscene party. It's nice to see the creativity that people put into their productions, and to see that a demoscene is still rocking.
<p>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-76146963900925747992012-11-12T22:02:00.000+11:002012-11-13T13:46:41.170+11:00Go Go Gadget Now().Nanosecond()<p>
Before I even get started, the "issue" I discuss below was <a href="http://code.google.com/p/go/source/detail?r=42c8d3aadc40">resolved just three days ago</a>. Of course, there will still be some time before this makes it to the next release of Go and also when GCC updates their libraries. Thanks Brad for pointing this out! I had no idea. Well, I don't want to delete this post... so for historical reasons it follows:
<p>
Time. It is such an unusual thing. I suppose it is "unusal" as it being
such an abstract quantity. I cannot just reach out into the air and pull down
some time. Yet, we humans try to quantize the abstract. After all, humans like
to understand how things work. And we like to measure the things that do work,
or measure things to figure out why they work the way they do. In other
words: we quantize time, break it up into distinct bits and pieces, so that
we can measure and understand it.
<p>
The more we chop-up time, the more accurate we can define something in all four
dimensions (three dimensions of space, and one of time). For instance, I can tell a
person to meet me at a particular location on the earth, which has 3 dimensions
(e.g. meet me on floor 4 of the building at corner of Foo and Bar streets). But
when should my acquaintance meet me? Well, I tell them a time. Possibly a
really really precise time, at 7PM and 4 seconds and 3001 nanoseconds. I'm a
robot. Anyways, I am digressing from the purpose of this post.
<p>
It is not uncommon for programming languages to provide a way (library) to
access time. This time comes from the system that is executing the program.
For instance, "gettimeofday()" and "clock_gettime()" are just two such functions
that ask a POSIX (e.g. Linux, BSD...) system for what the time is. These two
functions return a value that represents time. But how precise the result is, defines how fine you can
measure an event. I want to look at the time routine provided by the <a
href="http://www.golang.org">Go</a> programming language.
<p>
The following is my analysis of the Go 1 "time" package's "Now()" function, as provided by gcc 4.7.1 and 4.7.2 for a 64bit x86 architecture. We investigate the possible lack of precision from the resulting Nanosecond member. This
is <b>not</b> an analysis of how the Google 6g compiler and provided Go 1 "time"
package implements things. I did peer through the Go 1 "time" package provided
by the 6g Google Go compiler version 1.0.3. It seems that their routine works
similarly, so for all intensive purposes, we can assume what I write below for
gcc is similar to the 6g compiler.
<p>
Firstly, I notice that the Go API provides a function
for getting the nanoseconds from the current time of day. That's nifty. The
following code <i>should</i> accomplish this.
<pre>
package main
import "time"
func main() {
println("The current nanosecond is:", time.Now().Nanosecond())
}
</pre>
<p>
The above function obtains the current time, and then returns which nanosecond of the
current second the time is. See, time, in this case the second, can be divided into
smaller increments. The API says that the nanosecond returned is the
nanosecond of the current second of time. Now, recall that a nanosecond
represents just 1^-9 (0.000000001) of a second. That's a pretty darn small
increment of time. This means that the "time" package (library) of
Go should use a data structure large enough to contain 1^9 or
1000000000 values.
<p>
Well, a look at the Go runtime library (gcc and 6g)
uses a 32-bit signed integer (int) to represent the current
nanosecond of the current second. As any good data-structure-athiest-skeptic
needs to ask is: "Are 32-bits large enough to hold a value of 1000000000?"
Actually, is the "int" data type wide enough to contain the maximum value of a
nanosecond? Remember that an "int" is signed, so one bit does not represent a time,
rather that single bit is dedicated to representing a positive/negative
(signedness) state of the value. I can't imagine a negative time, and
zombie-Einstein might puke if you were to venture into the past.
<p>
The time library for Go provided by gcc uses the "gettimeofday()" system call, or virtual dynamic shared object <i>vDSO</i>, function provided by the operating system. A POSIX compliant operating system should provide the latter routine which obtains the time from the system. The Go "time" library calls this routine to obtain time. Go will then (convert) the returned value into a Go structure of time. I did
not see in the Google 6g version of the library where they make an explicit call
to "gettimeofday()." However, I did see where
the library accesses members of the result, which are similar as to what "gettimeofday()"
returns.
<p>
An integer can hold a range of values and has to be large enough to at least contain the values of such a range. 31-bits of
value and one to represent signedness. Go implements "int" as being 32-bits, is is the data structure used for storing nanoseconds. So 2^31 - 1 or a maximum value of 2147483647. Which... YES... is large enough to contain enough nanoseconds for a second. (I had a typo in my original post and I thank the anonymous poster who cleared that up for me).
<p>
The POSIX standard defines that the "gettimeofday()" function returns
seconds and MICROSECONDS... I'll say that again, microseconds, since the epoch of
bell-bottoms and afro-sheen (January 1, 1970). In fact, the POSIX standard is a
bit loose, and says it should return at least seconds and microseconds (leaving
the doors open for other values). But, a browse of the code in gcc and 6g shows that they take a microsecond value and treat that as a base for nanoseconds.
<p>
So, what then is the Go "time" library doing? Well, when we call "Now()" we get a "Time" object. This object is initialized by an architecture specific routine which queries the system (using a system call) and sets-up the "Time" object, including the nanosecond member, from the result of that system call. What the x86 64-bit Linux implementations seems to be doing, for the "Now()" routine is effectively querying "gettimeofday()" and then taking the microsecond value and multiplying it by 1000 to represent nanoseconds. So, for those using the nanosecond value returned by a "Time" object created by "Now()", the last three digits will be zero. This "Time" object can be further manipulated (e.g. using "time.Add()", "time.Date(), or "time.Unix()") which might modify the nanosecond value, presenting a more precise representation of nanoseconds. This means that the initial return of time from "Now()" will have a nanosecond value that is always missing the lower three digits (and bits) of the value. Well, it turns out that 999999000, the maximum value of nanoseconds Go can return by the "Time" object created by "Now()" is still .99 of a second, but it's just not the high precision that might be desired. See, the lower three bits are missing... that latter value
converted to binary: 0b111011100110101100011000011000
<p>
For most people this is not a big deal. But being aware is always a good thing. However, if you are using "Now()" for nanoseconds, you might in fact be looking for a high precision version of time.
<p>
<b>TLDR;</b> The Go runtime "time" package returns a scaled microsecond value to
represent nanoseconds and not the actual nanoseconds to a high granularity, when time is created using the "Now()" library function. The
lower three digits (1000 values) are always zero.
<br/><br/>
-Matt
<p>
Additionl Resources:
<br/><a href="http://gcc.gnu.org">GCC</a>
<br/><a href="http://www.golang.org">Go (and Google Go 6g Compiler)</a>
<br/><a href="http://pubs.opengroup.org/onlinepubs/009695399/functions/gettimeofday.html">gettimeofday()</a>
<br/><a href=" http://www.open-std.org/jtc1/sc22/wg14/">C Standards Website</a>Matthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com4tag:blogger.com,1999:blog-5351615674355348814.post-63583401620237306642012-11-11T08:56:00.002+11:002012-11-11T09:15:29.852+11:00Brian CoxLast Friday night the amazing physicist from <a href="http://www.apolloschildren.com/brian/">Manchester University</a>, and once-music-star of <a href="http://en.wikipedia.org/wiki/D:Ream">D:Ream</a>, <a href="http://www.ted.com/talks/brian_cox_why_we_need_the_explorers.html">Brian Cox</a> gave a talk about the universe and life, from the infinitesimal to the very very large. Note that this was not a TED event, and the latter link is just a video from a TED talk he gave (I wanted to show the uninformed how bad-ass he is). To top it off, it was <a href="http://en.wikipedia.org/wiki/Carl_Sagan">Carl Sagan's</a> birthday. Truly an amazing evening. I have said it many times, but I think a sign of genius is having the ability to communicate and explain incredibly complicated subjects with the utmost elegance. Brian does this... like the greats of <a href="http://en.wikipedia.org/wiki/Richard_Feynman">Feynman</a> and Sagan.
<br/>
<br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0tag:blogger.com,1999:blog-5351615674355348814.post-15554985113042081682012-11-09T23:18:00.000+11:002012-11-10T00:13:00.706+11:00Devil Hands: The Wonders of a Loosely Typed Compiler <a href="http://gcc.gnu.org">GCC</a> has been something that has captured my attention for years. It seems there
is a set of chosen developers whom have bowed to the darklord himself, to
create a tool which is just mind-blowingly fascinating. gcc takes text and makes
binaries! Sure, that's what most compilers do, but gcc just towered over me with as
being, almost, a pinnacle of hackery. It's just shear black magic! And I like
the dark arts.
<p>
For years I have enjoyed being a software developer; however, I wanted to get my
hands dirty on a lower-level than just application development. For some
reason, I wanted to work on tools that others use to construct their tools (and
applications). Enter the realm of compilers. Since gcc is open source, and
many people and organizations rely on it, I felt I would sell my soul.
After all, idle hands do the devil's work. So, I decided to put my devil hands
to work.
<p>
Well, part of my wanting to get into compilers eventually led me towards a
PhD... still working on it. Well, I should be working on it, but I am writing
this post instead. Anyways, during a PhD meeting the other day, one of my
advisers mentioned that gcc has something like over 100 different
representations for a certain data structure used inside the compiler. This
structure is used to represent various things about the program that gcc is
compiling. Things like variables, statements, declarations, etc.
This adviser is right, in fact, he is never wrong. No, really, he knows all.
<p>
Well, I have been dipping my hands in the secret sauce that is gcc for a while
now. In fact, one of the reasons I wanted to get a PhD was to hack on
gcc. So my compiler driven region based memory management uses GCC-plugins to
accomplish the research. Anyways, I have mentioned to my advisors many times
that, yes, in fact the "tree" node data structure in gcc can be anything!
<p>
So what is the big deal if a data structure, used inside the compiler, can
represent anything? Isn't that polymorphism at its finest? Well... no.
It means that the internals of gcc are
essentially untyped. Heck, a "tree" is defined as a union consisting of 41
structures. To top it off, there is another file (tree.def) that defines about
195 (in gcc 4.7.1) different "things" a tree can be! This is all fine and
dandy, if you know what you are doing. But it means one must be an 31337 ninja
when writing gcc code. The danger comes in referencing data inside the tree
node. If accessed improperly, the data will not have the correct meaning.
While there are a handful of data structure inside a "tree" node, there are over
a hundred of possibilities which use certain fields or not. And if you do not
ask the type, at runtime, what the type is, and perform your reading of the data
properly then *boom* you get bad data. This is what I call a type bomb. The
result of a lack of typing on a data structure. In other words, you have a grey
box, and you basically have two things you can do, before pulling data out of
it. It has structure, but certain parts are not always populated. Either you
can ask the black box what is inside it, or you can assume what is inside it. A
lack of type safety makes reading data can be dangerous. Since it permits the
possibility that you can read the data incorrectly. But, I like this, it makes
playing with gcc kinda fun, in a masochistic way.
<p>
To reiterate, how you read data in a "tree" instance can vastly change. Suppose
that you want to check that whatever the "tree" represents is a global (e.g.
global variable). Well, you can use the "is_global_var()" predicate.
Just pass a tree instance to it, and it will return true or false. But, one must be
very cautious. See, "is_global_var()" only works on declaration nodes, and not
the handful of other "things" a "tree" can represent. I can pass a variable
declaration "tree" node and the predicate will produce a proper truth value.
However, if I pass it a particular instance of a variable, such as given by a
SSA representation, then the result is not sound. Since the predicate will
always return true-or-false, a value will be returned, it just might be wrong.
<p>
Consider the following block of C code:
<pre>
void foo(void)
{
int x;
x = 1;
}
</pre>
<p>
During a walk over the statements in this code, well actually, gcc will be
walking a more verbose representation, its intermediate (GIMPLE) representation.
Anyways, suppose your compiler pass wants to check if the 'x'
variable in the declaration statement 'int x;' is global. The "is_global_var()"
will return a proper truth value. However, if you pass the 'x' in the 'x = 1;'
assignment statement, the value returned by the predicate cannot be
trusted. Since a tree node can be thought of as an opaque type kinda (like a
"void *") you can read a "variable" type as if it were a "declaration." And
there is nothing wrong with that, no compiler warning.
The "is_global_var()" does not check first what type of "tree" node it was
passed, and will just report the result if the node were a declaration. This is
dangerous, and is what causes the lack of sanity. The type enforcement comes in
the comment above the "is_global_var()":
<br/>
From gcc-4.7.1:
<pre>
/* Return true if T (assumed to be a DECL) is a global variable.
A variable is considered global if its storage is not automatic. */
</pre>
<p>
TLDR; Untyped data structures are convenient, but require that the programmer
be an omniscient monkey-saurus and know what is up with the data they are
flinging. Tread lightly young warriors. Oh, and to get an idea of what
"things" a tree can be, check <a href="http://users.757.org/~enferex/many_things.txt">here</a>. From gcc 4.7.1.
<br/>
<br/>
<b>Resources</b>: <a href="http://gcc.gnu.org">gcc-4.7.1</a>
<br/>
<br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com3tag:blogger.com,1999:blog-5351615674355348814.post-58940417516883147812012-11-04T16:58:00.002+11:002012-11-04T16:58:29.887+11:00Pickin' up the TrashI assume a few of y'all are wondering what I have been up to. Well, I am working less hours on the timing stuff and more hours on my PhD. In fact, I just wrote a pretty basic garbage collector. I want to weave it into my region memory allocator. In fact, after some more thought, this collector is not entirely complete. It does collect unused data, but it makes a few assumptions, mainly that a pointer does not point into the middle of an array/allocated chunk of memory. This is a horribly bad assumption, especially for what I want, a precise (as opposed to a conservative) collector. My collector works by collecting type and function call data at compile time (gcc plugin that I wrote). Then the collector runtime logic is linked into the resulting binary. The logic behind the allocator is a variation of <a href="http://en.wikipedia.org/wiki/Cheney's_algorithm">Cheney's Copying Collector Algorithm</a>. Anyways, I'm proud of the collector. The assumption I have made is part of the problem, and corresponding solution, that my advisers and myself want to write-up for a paper. I hope that goes well. And me? Well, I have a few more months (July is when my scholarships die). So I hope I can start thesis writing soon.
<br/><br/>
-MattMatthttp://www.blogger.com/profile/04709610615390095921noreply@blogger.com0