# Array Slices and Interior Pointers

The D programming language has the concept of a slice. Slices are a neat way to do data processing with arrays but have a fundamental flaw, related to garbage collection, that I’ll explain here. I’ll also present a way that this flaw can be fixed.

# Crash Course on Slices

I’m not going to explain slices in all their glory – see this instead. The short story is this: A slice is simply a length + pointer pair. The pointer points to some arbitrary memory and the length specifies how many contiguous elements are at that location in memory. D does not really have arrays in the traditional sense. Consider this code:

`int[] xs = [1, 2, 3, 4, 5];`

The xs variable is not actually an array. It’s a slice with a length of 5 and a pointer to somewhere in memory. We can now do this:

`int[] ys = xs[1 .. 4];`

This is what slicing means and where the name slice comes from. The ys variable is now a slice with a length of 3 and a pointer to the second element in xs. Slices are especially beautiful in string processing code since you can pick off parts of a string easily.

# The Problem with Slices

First, a thing to note: Slices are passed by value. This means that they are effectively a two-word struct being passed around. This is of course for efficiency reasons, since allocating a heap object for every slice would be unreasonably wasteful.

Now, consider that the pointer part of a slice can point to GC-managed memory. This means that the garbage collector has to scan it. This is not bad in itself, but let’s review the code above:

`int[] ys = xs[1 .. 4];`

As said, ys’s pointer is now pointing inside xs’s memory block. We have an interior pointer. This forces the garbage collector to not only scan slices conservatively, but also to assume that their pointer part can be an interior pointer. And this is for every single array/slice in a D program.

This is clearly a huge problem for type-precise garbage collection.

# The Proposed Solution

Given an arbitrary slice pointing to any non-null memory, we want to be able to immediately tell whether that block of memory is GC-managed without having to do a heap range check on the slice’s pointer.

There is fundamentally only one way to solve this problem (without introducing unacceptable overhead) with two variations. It boils down to storing a pointer to the original memory block in the slice. This means that slices will become 3 words long. This is a significant change because it means an extra word to copy around when slices are passed between functions. On the other hand, I think the advantages it gives in garbage collection complexity (or rather, reduction thereof) outweigh that.

So, previously, slices look like this (assuming a word size of 8):

```------  ------------
Offset  Value
------  ------------
0       Length
8       Pointer
------  ------------```

In my scheme, slices look like this:

```------  ------------
Offset  Value
------  ------------
0       Length
8       Base Pointer
16      Pointer
------  ------------```

The base pointer here is the pointer to the start of the memory block. This ensures that the GC can trivially figured out that the memory is live. The pointer is then the (possibly interior) pointer to the relevant part of the memory block as in the old slice representation.

The other variation looks like this:

```------  ------------
Offset  Value
------  ------------
8       Base Pointer
16      Offset
------  ------------```

Here, offset means the offset into the base pointer to get the actual region of memory that the slice points to. This does mean a little extra work when doing indexing. It also assumes that the location the base pointer points to stores the memory block’s length. This scheme allows slices to work with arrays in the Common Language Infrastructure and other virtual machines. It would not work for plain D that compiles to native code, however.

I hope one of these variations can be worked into the D language. The current situation is highly problematic for garbage collection — and also prevents a D port to the .NET ecosystem — and needs to be addressed.

Comments very welcome – if you spot a flaw in the proposed solution, do say so. If something about the new scheme seems confusing or unsound, speak up too – it probably indicates a flaw. Suggestions for a better solution are also appreciated!

# SRP and Primes with OpenSSL

So, I’ve been implementing the Secure Remote Password protocol (SRP) for a game project I’m working on. As you can see on the protocol design page, the protocol needs two values, N and g, in order to function. N (the modulus) must be a large, safe prime number and g (the generator) must be a primitive root of N (and thus also a coprime of it) also called a generator modulo N. In typical SRP speak, there is a key size KS which is the byte length of N. This key size is used in other computations in the protocol (such as when generating random numbers of a certain size) so we want it to be relatively large.

In my case, I’m configuring SRP with a hash function H of SHA-512. I want a prime number with a byte length of 256 (i.e. 2048 bits). I’ll set the generator to 7 (the size of the generator really doesn’t matter in practice, but its value does matter in some regard as we’ll see).

I wanted to learn the OpenSSL API and so I figured I might as well generate my prime using OpenSSL. To that end, I wrote a tool that generates a prime with a specified bit length and verifies that a given generator is indeed a primitive root of it.

For example:

```\$ pgen 7 2048
N = 30817315993488094950063876611235224995197015486777838966039582184466989601737137785061150319729619861304023701874943954720410365155449212378509728297079378161875051028799177659132903881263214197958240731547326531423454481362477841674050050915185206506619708099215010108502376591014173871205694210918500927079807342355799375661000520374063019571782387361197808323622083769298736910284318017757455603510572185239046633686272701011272606841336216587476945751457343136023480297100196085405628980635988198354477091187313063439790470202359125187362725727097509333399354569332837280881731107660517239937731269477580686853163
g = 7
gcd(g, N) = 1```

OpenSSL verifies that the final value of N is probably (i.e. very likely; see the documentation for BN_generate_prime) a prime (that is, it is not composite). The last line showing the result of applying the GCD operation on N and g verifies that g is indeed a generator modulo N (see here for why).

With N and g defined, all random numbers are generated with a byte length of KS such that they are as long as N. It is worth noting that both ends should agree on how the return value of the hash function H is interpreted (consider that the hash function most likely returns a raw byte array). The typical way is to interpret it as an unsigned, little-endian integer with the same byte length as the digest. Everything else in the protocol follows mathematical convention and is trivially implemented.

# Demystifying Garbage Collectors

There seems to be a lot of confusion among developers on how garbage collectors actually work. They really aren’t as magical as some people think; in many ways, some garbage collectors are actually quite crude and — by modern developer standards — evil, unmaintainable, and full of subtle gotchas (the latter is certainly true no matter one’s perspective). In this post, I’ll try to shed some light on how GCs work in a way that (hopefully) any developer can understand. I do assume that the reader is at least familiar with basic computer memory concepts (C knowledge is preferred).

Note: This is a very long blog post. Grab some coffee.

# Reachability Analysis

All garbage collectors are essentially based on one fundamental concept, regardless of whether they support reference counting or similar mechanisms: Reachability analysis (also known as liveness analysis, though this is less common and usually more associated with compiler lingo). The idea is that, given a set of roots, the collector will scan the entire heap (the set AllObjects) recursively, constantly adding to a set LiveObjects those objects that it finds to be live. When the scan is complete, the relative complement of LiveObjects with respect to AllObjects (that is, all objects that are in AllObjects but not in LiveObjects) are considered unreachable, and are thus deallocated (garbage collected). This process is typically referred to as a mark-sweep algorithm.

(The set theoretic terminology is quite intentional, by the way; there can be no duplicate elements.)

We can express the above algorithm as:

```collect()
// First find all live objects.
mark()

sweep()

mark()
// The root set contains pointers to
// static fields that in turn *can*
// contain pointers to objects. They
// can also simply contain a null
// value.
for Field in Roots do
Object = *Field

// If not a null pointer, push
// it into the work list for
// scanning below. Also mark it
// as live immediately.
if Object != null do
push(LiveObjects, Object)
push(WorkList, Object)

// Now start processing the work
// list. It'll eventually become
// empty once the entire heap has
// been scanned.
while !empty(WorkList) do
Object = pop(WorkList)

// Now recursively scan all
// objects for references and
// mark them live, push them
// into the work list, rinse;
// repeat.
for Field in Object do
ReferencedObject = *Field

if ReferencedObject != null and
!contains(LiveObjects, ReferencedObject) do
push(LiveObjects, ReferencedObject)
push(WorkList, ReferencedObject)

sweep()
// The relative complement of
// LiveObjects with respect to

free(Object)

// Since LiveObjects contains
// all the relevant objects
// that are left, we can simply
// assign it to AllObjects.
AllObjects = LiveObjects```

(This algorithm is a variation of the one Jones uses in his Garbage Collection Handbook – which, by the way, is a fantastic book that I fully recommend if you’re interested in garbage collectors.)

So, to reiterate, what this algorithm does is:

1. Marks all roots as live.
2. Populates the initial work list with root objects.
3. Walks the heap recursively marking reachable objects live.
5. Repopulates the AllObjects set with the LiveObjects set.

That’s really all there is to reachability analysis and mark-sweep. Of course, a real GC is more complicated for a number of reasons:

• Simply maintaining sets of objects is not very efficient at all.
• Marking is often implemented via bitmaps or flipping bits directly on objects instead of maintaining an expensive set.
• Scanning thread stacks, thread-local storage (TLS) locations, and registers is much more complex than the above.
• I omitted allocation code entirely – allocation algorithms make up a lot of the complexity in a GC, particularly because lock-free allocation is desirable.
• Most collector types will want to pause all threads when starting a collection, and resume them when done.
• Some GC algorithms will even want to mutate the heap layout (moving and copying collectors).
• Some concurrent (and sometimes even generational) GC algorithms require read and write barriers to be inserted in generated code by the compiler.
• In some cases, a GC has to consider that an object reference can not only be null, but also completely invalid even if non-null.

… And many others. But one thing at a time.

# Memory Layout

We’ll need to discuss the memory layout of garbage collected objects a bit before getting further into the details of garbage collectors.

The memory layout of collector-managed objects varies a lot depending on the language or virtual machine involved. To give some examples:

• C: An object consists purely of what has been declared/explicitly allocated.
• D: An object contains a virtual table, a monitor pointer, and its fields.
• Mono: An object consists of a virtual table, a synchronization block pointer, and then its fields.
• MCI: An object consists of a type info pointer, a word of GC-specific bits, a user-modifiable reference field, and its regular fields.

The reason C doesn’t throw any hidden fields into objects is, of course, because of its very close-to-the-metal memory model. This means that the collector cannot (trivially, at least) store data before an object’s contents.

In D, things are quite different: Since the language is built with GC as the default memory allocation mechanism, the compiler reserves two words of memory in the header of all objects. The first is a simple pointer to a virtual table (i.e. your run-of-the-mill virtual function dispatch table). This virtual table also happens to point to a type information structure that the GC can make use of. The second is a pointer to a so-called monitor. This is just fancy terminology for a mutex. This monitor structure, though, happens to also be used by the GC for registering object finalizers (more on that further into the post). So, all in all, the D compiler helps the GC a lot by providing type information and places to store information.

In the Mono virtual machine, things are quite similar to D. The first word of an object is a pointer to a virtual table, which contains a type information structure and function addresses like in D. The second word points to the synchronization block. This one is a bit of a beast: It’s used to store a monitor (the entire thing, not just a mutex pointer), cache hash values (necessary for moving/copying collectors), and a few other things. For objects that don’t implement GetHashCode, their hash is calculated from their address. This poses a problem when objects are moved around in memory (and thus change addresses). The purpose of the cached hash field is thus to remember the hash value even when the object is moved. This is a reasonable approach (really, the only not-incredibly-complicated one) because, at worst, some objects will have equal hash codes occasionally.

In MCI, the design of object headers is quite different from other virtual machines. Since the VM has no particular support for virtual function dispatch (but certainly lets you implement it in the code you pass to it), the first word simply points to a type information structure (which also contains a bitmap of the physical type layout – used for faster scanning). The second word is completely opaque and the use is specific to the garbage collector that the VM is started with. The third word is a user-modifiable field that can contain any reference type (managed objects, arrays, and vectors all allow this). This field is always scanned by the GC. The motivation for that was to make implementation of some higher-level language features like virtual dispatch easier.

In general, in an environment where objects contain information usable by the GC, the GC is going to be more efficient and/or more precise. The GC will have an even better time if the compiler emits load/store GC barriers (not to be confused with memory barriers). More on those and type precision further into the post.

For now, we’ll assume concurrent garbage collectors don’t exist (which is not the case, but ignorance is bliss). Let’s look at how so-called stop-the-world (STW) collectors work.

For non-concurrent, STW collectors, it is absolutely essential that all non-collector threads are stopped before a collection starts. This is so because if other threads were running while the collector is scanning the heap, it might miss objects that were recently made live and end up freeing them, which is clearly a Bad Thing (TM). For moving and copying collectors, things could get even worse – some parts of the heap (or roots) might end up with lingering references!

So, a non-concurrent GC generally performs a collection like this:

1. A thread attempts to allocate memory, but none is available.
2. The collector hijacks the allocating thread.
3. All other threads are suspended (typically via POSIX signals; Windows has a SuspendThread function).
4. A collection is performed.
5. Memory is allocated, either via newly freed memory or by asking the OS for more memory.
6. All other threads are resumed (again, POSIX signals; ResumeThread on Windows).
7. Any pending finalizers are executed (either on the hijacked thread or on a dedicated asynchronous thread).
8. The GC returns the hijacked thread to the allocation site, with the newly allocated memory.
9. The program continues on…

There are some things worth noting here: First, step 7 may not actually return any memory; if the GC failed to allocate memory one way or another, it would likely throw an exception or return a null pointer. Second, in step 3, the GC may actually skip some threads that it uses internally. This is the case for collectors that do parallel marking of the heap. Third, never mind finalization for now. We’ll get to it.

Probably the most prominent criticism of STW collectors is exactly that: They’re STW. There are several problems with this property:

• Programs can stop at (practically) arbitrary locations/times.
• Pause times are unbounded (for most collectors – real time collectors do exist, but are rare).
• The programmer must take care that low-level threading code cannot be disrupted by pauses.

All of these make concurrent collectors generally more preferable than STW collectors, but concurrent collectors are significantly harder to implement – we’ll also get to that.

Finally, regardless of what collector type is in use, whenever a thread is started, the collector must be notified in such a way that it can add the thread’s TLS areas to its roots (and remove them when the thread goes down). Some languages and virtual machines take this to a whole other level; for example, the Erlang VM exclusively does per-process garbage collection, which significantly speeds up collection overall (keep in mind that Erlang processes are extremely small). Erlang can get away with this because there is no global state that needs to be garbage collected. It is very likely that the Rust language will go with a similar model.

# Finalization

There is often a need to perform some kind of user-defined cleanup when an object is collected. Most garbage collected languages have features that allow this in some form or another.

C#:

```class Foo
{
~Foo()
{
PerformCleanup();
}
}```

D:

```class Foo
{
~this()
{
performCleanup();
}
}```

Rust:

```struct Foo
{
drop
{
perform_cleanup();
}
}```

Some languages call them destructors, but the universal term used in GC lingo is finalizer; it finalizes the object’s lifetime.

Exactly when a finalizer runs is very specific to the language or virtual machine. To name a few approaches that exist:

• An object is finalized whenever nothing has references to it. This means that two objects pointing to each other can create a cycle in which no finalizers are invoked on the two objects, ever. Worse yet, even an object holding a pointer to itself can prevent finalization.
• An object is finalized whenever nothing has references to it, except itself. This is a variation of the above aforementioned approach which is slightly safer. Cycles between multiple objects are still problematic.
• An object is finalized whenever nothing has references to it, except itself or other dead objects. This permits both cycles and self pointers.

The last approach is arguably the safest, but it does also mean that a finalizer cannot assume anything about the state of other objects that the finalizer’s object refers to. This is by far the most common kind of finalization used in programming languages, due to its safety traits.

As I mentioned earlier, finalizers are executed just before the GC transfers control of the calling thread back to the application. Again, depending on the language and virtual machine, finalizers are executed either on the calling thread or on an asynchronous finalization thread (or multiple, in some cases). For implementations where finalizers are executed on the calling thread, the finalized objects can be trivially deallocated right after finalization. For those that enqueue finalizers on a separate thread, things go like this:

1. The object is enqueued on a separate thread.
2. The GC resumes program execution.
3. The finalization thread finalizes the object.
4. The object is deallocated.

If the garbage collector implements the third (and safest) finalization technique mentioned before, it can choose to do some extra work to make finalizers less prone to looking at objects with an invalid state (because they have been finalized before). This is fairly trivial: Given a finalizable object, go over all of its reference fields and set them to a null value. This will in all likelihood result in some kind of null reference exception, should the finalizer attempt to access these fields, thereby making it clear to the programmer what went wrong. This is not commonly done, however; for instance, the Java and C# GCs do not do this.

Finally, consider this piece of C# code:

```static Foo F;

class Foo
{
~Foo()
{
F = this;
}
}```

When Foo’s finalizer is executed, it assigns itself to a global variable, effectively making itself reachable again – this is called resurrection. In most implementations, this makes the object perfectly reachable and live, but when the object again becomes unreachable, its finalizer will not run again. Typically, an implementation will provide a function to register an object for finalization again for these cases.

That’s it. Finalization is actually rather simple at its core; the only confusing aspect of it is that everyone does it differently in some way. I’m of the opinion that the third finalization approach is always the right one, but changing implementations to use that once they’ve already settled on another technique would of course be a very breaking change…

# Weak References

When memory is scarce, a common technique in garbage collected languages is to use weak references to refer to non-essential resources. A weak reference is much like a regular reference except that the collector is free to collect the pointed-to object. That may seem insane, but it’s important to note that when the collector deallocates a weakly referenced object, it sets weak references to a null value such that no lingering references will stick around. Objects that are strongly referenced and weakly referenced will not be collected.

When an allocation attempt happens and the GC is out of memory, it can either do a collection cycle, then check if some memory has become free and return that, or it can choose to allocate from the OS immediately. Either way, if no memory is available, it’ll have to consult the OS. Now, the point of weak references is that after having scanned the heap, the collector can choose to deallocate a few weakly referenced objects in order to make space, instead of consulting the OS for more memory.

A common use of weak references is to maintain in-memory caches that are allowed to lose data.

# Moving and Copying

One problem that typical mark-sweep collectors face is heap fragmentation. GCs typically allocate and deallocate memory from the OS in pages (which usually translates to 4096 bytes). So, imagine that you allocate a bunch of objects which all get put into a page. All but one of these objects eventually become unreachable and are deallocated. Now you have one object, possibly not bigger than a couple of bytes, keeping an entire page (4096 bytes) alive! This is clearly bad when thousands (or even millions) of objects are allocated over time in a program: Not only is redundant memory reserved, the OS will eventually run out of memory and resort to swapping because it can’t allocate more pages – meanwhile the GC is holding onto lots of pages with plenty of space, but a couple of objects happen to keep them committed.

Most garbage collectors deal with this problem by using heap compaction. Heap compaction algorithms can largely be separated into two categories: Moving algorithms, which move objects around to maximize use of page space, and copying algorithms, which copy between two separate heaps on every collection cycle, automatically gaining compaction. The latter is the one typically used in production garbage collectors today (especially in the young generation of generational collectors).

Describing all of the various compaction algorithms is out of scope for this blog post, but I’ll describe the fundamental ideas behind each category.

Moving compaction is based on simply pushing objects back into the beginning of the heap on every collection cycle. The goal is to make as efficient use of page space as possible to (try to) eliminate gaps. Once done, the collector can choose to either return excess empty pages to the OS or keep them around to serve allocation requests.

The purpose of copying compaction is to be faster than moving compaction at the expense of space. The heap is split up into two so-called semispaces called from-space and to-space. All allocation requests happen into to-space. When no more memory is available and the collector has to do a collection cycle, it flips the roles of the two semispaces; that is, the to-space is now from-space and vice versa. Then, the collector starts scanning the from-space. All objects that are found to be live are copied over to to-space in a simple bump pointer style. All remaining objects in from-space are effectively dead and can be deallocated in bulk. The advantage of this algorithm lies in the copying being very fast due to simply incrementing a pointer in to-space, while the obvious disadvantage is that two equally-sized heaps must be maintained even though one is largely unused until a collection cycle occurs.

It’s clear that both moving and copying algorithms have overhead compared to simple mark-sweep algorithms, but they are essential in long-running applications that must not go down due to a fragmented heap.

The above seems simple enough, but consider that when we copy and move objects, we effectively invalidate all pointers that point to them! This is not an unsolvable problem: The collector must simply update all pointers accordingly. This, as it turns out, is very simple in a type precise environment, while in an uncooperative environment (e.g. in C), it is practically impossible. More on that when we get to type precision.

# Pinning

When interoperating with external, non-garbage collected code, it is essential to be able to tell the garbage collector that an object must not be collected even if it appears to be dead. This process is called pinning; that is, the object is pinned in place. The term actually originates from moving and copying collectors, because there it also means that the collector is not allowed to move or copy the object.

Let’s go with an example in pseudocode:

```work()
managed_func_1()
managed_func_2()

managed_func_1()
Object = new()

// Pin the object since it will
// be hidden in a global variable
// not scanned by the GC.
pin(Object)

unmanaged_func_1(Object)

unmanaged_func_1(Object)
// The object is logically live
// because a reference exists,
// but the GC can't see it, hence
// the pinning above.
GlobalVariable = Object

managed_func_2()
Object = unmanaged_func_2()

// Unpin the object so the GC
// knows the object is eligible
// for collection again.
unpin(Object)

unmanaged_func_2()
Object = GlobalVariable

// Null out the global variable
// so we don't have a lingering
// reference hanging around.
GlobalVariable = null

return Object```

This is a little pathological, but it illustrates the point of pinning: Keeping an object alive when the GC can’t see it.

# Type Precision

Type precision is probably one of the most important aspects of modern garbage collectors. Without precise type information, it is impossible to tell whether something in memory is a plain integer or a pointer. Conservative garbage collectors (such as the Boehm-Demers-Weiser collector for C and C++) have no type information to work with, so they must conservatively assume that any integer that could be a pointer to a managed object is a pointer to a managed object. This can result in so-called false pointers that keep dead objects alive. This isn’t a huge problem on 64-bit systems due to the significantly larger address space, but on 32-bit systems, it can be a showstopper for some types of applications.

But that’s not the only use for type information. Moving and copying collectors are, in practice, impossible to implement without type information because they don’t know where to update pointers in the program. If no type information is available, the collector could easily end up overwriting a plain integer, actively altering program semantics. This would obviously (also) be a Bad Thing (TM).

Type information does not have to be completely precise about exactly what kind of data type is in every possible memory location – it suffices to know what memory locations hold managed references (and should thus be scanned and possibly rewritten by the collector). A collector isn’t concerned with any other data types (such as integers and floats), so those can be left out in the information provided by the compiler or virtual machine.

Now, type information makes precise heap scanning trivial, but what about the stack and machine registers? In practice, keeping track of when a reference is in a register is very hard and often not worth the effort, so scanning registers conservatively is a universally acceptable approach. The same goes for all roots (global variables, TLS data, and so on), though providing type information for those would be trivial too.

The stack is where things get interesting: The compiler can work out what slots in a stack frame can contain references when it generates code. It (or a virtual machine, for that matter) can then emit a so-called stack map that the garbage collector can use. The garbage collector will walk the call stack of stopped threads, working out exactly what’s present in the various slots. This makes stack scanning much more precise than usual – consider that, given a 2 MB stack, there are 524288 unique storage slots (on a 32-bit machine). That’s quite a few false pointers if the garbage collector is not precise.

On the other hand, the likelihood of these slots holding values that would actually keep objects alive is relatively low. It’s also worth considering that stack maps consume a lot of space by themselves, so using them may not always be desirable. This is particularly true in a JIT-compiling virtual machine where a lot of data structures already have to be maintained, eating quite some memory.

# Concurrency and Barriers

In applications that run on workstations, it is desirable for the program not to have long pause times. This is not a problem for server applications and the like, but a user doesn’t want to sit and wait for an application to react to their input. Concurrent garbage collectors solve this problem by performing garbage collection while the program is running and never actually pausing any threads. This does mean that some processing time is lost due to synchronization between program threads and GC threads, but on the other hand, the application will be much smoother to work with.

Since concurrent GCs run on one or several separate threads from the main program, it is clear that there would not be much to gain if the machine the program is running on doesn’t have SMP. While that wouldn’t prevent a concurrent GC from working with the same semantics as on an SMP machine, it would be significantly slower than just using a plain STW collector. Thankfully, lack of SMP isn’t much of a problem in this day and age.

Probably the biggest problem with concurrent garbage collectors is maintaining collector invariants (that is, conditions that must hold throughout garbage collector logic). Since the program runs concurrently with the collector, it could easily race against the collector, resulting in lingering references and other nasty things. The solution to this problem is GC barriers: These are very small code stubs that are inserted into the program at locations where various memory operations are performed. They perform small, usually atomic, operations that help maintain invariants in the face of concurrent mutation and scanning of the heap.

Barriers require compiler or virtual machine support. One problem with barriers and static compilers is that they essentially form a very strict ABI between the program and the garbage collector, giving little flexibility to run the same program with different collectors without recompiling. JIT-compiling virtual machines are more flexible in this regard because they can simply mutate the intermediate representation of the program to insert barriers just before emitting native code.

What barriers do varies a lot depending on the GC implementation, and where they are inserted varies even more. Most commonly, they can be inserted for memory loads/stores, array loads/stores, field loads/stores, and so on.

To see an example of a real world barrier implementation, take a look at this paper.

# Optimization

A lot of people are skeptical of the performance of garbage collectors – and rightfully so. Given all of the above, it’s not hard to imagine how much work an actual GC implementation has to do when performing collections. But, as with any other technology, you must optimize for the technology you’re using, not the technology you wish you were using.

A few guidelines to go by:

• If your data structure is smaller than 16 (or so) bytes, it probably shouldn’t be an object.
• Recycle objects that you create many instances of (object pooling).
• Never allocate during intensive work where throughput is important.
• Avoid boxing like the plague if you can.
• Prefer mutable data structures over immutable ones when performance is essential.
• Prefer a concurrent GC for workstation programs; an STW GC for server programs.
• Use weak references for non-essential data.
• Avoid pinning too many objects as it can severely inhibit the garbage collector’s work.
• Don’t use finalizers if you don’t have to.

# Conclusion

While this post is fairly abstract in comparison to actual GC implementations, I hope it has shed some light on how garbage collectors work. If you understand the things in this post, that’s enough to understand how to work with a garbage collector and optimize for it, in practice – you don’t have to know every little implementation detail.

If there’s anything you find unclear in this post or perhaps completely unanswered, please leave a comment! It’s entirely possible that I forgot something due to the lengthy nature of this post.

# But, But, Internals?!

Sorry, but actual garbage collector implementations are complex beasts full of clever and subtle optimizations and algorithms. Even describing the algorithms behind a single implementation would have made this blog post — quite literally — 10 times as long as it is now.

If you’re interested in garbage collector implementations, I recommend taking a look at some open source code:

Many others exist out there. These are just the ones I happen to be familiar with.

Also, again, I really recommend the Garbage Collection Handbook.

# I Hate x86

And here’s why:

• No standard calling convention across all operating systems. Yes, this is x86′s fault. It should be specified in the manual.
• Two-address instructions. RISC is good.
• Too few registers.
• Random instructions like to operate on, or store their value in, specific registers.
• Too many extensions. Just read this and you’ll understand.
• Floating point stack. Like, seriously, wat.
• Too much deprecated crap. It would not be an overstatement to say that half of the Intel manual could be removed if the deprecated instructions and features were removed.
• Insane instruction encoding. I invite you to read this.

I have no idea if anything will ever replace x86, but I sure hope so.

# Grunt Auth Misconceptions

This is in response to this blog post.

First of all, the “NLS” protocol mentioned in the post has basically nothing to do with Battle.net. It is the so-called Grunt protocol. This protocol is a hacky, ad-hoc protocol that most Blizzard games used up until around World of Warcraft’s Wrath of the Lich King expansion. After that came the Battle.net 2.0 protocol (which still seems to differ across games). Battle.net 2.0, as opposed to Grunt, actually brings authentication together with Battle.net features like chatting, friend lists, etc. Battle.net 2.0 uses SRP v6a and uses SHA-256 instead of SHA-1. That’s not all — the process is much more involved (even involves the server sending the client raw machine code modules that the client then executes; similar to, but not quite the same as, Warden) — but the details are beyond the scope of this post.

Grunt is entirely unused by World of Warcraft, Starcraft 2, and Diablo 3 today. The World of Warcraft client does still have the code necessary to perform authentication using Grunt, but it takes some binary patching to get there (most WoW 3.x private servers do this). In other words, the aforementioned blog post sheds light on a protocol that is almost entirely unused today, and the information is therefore not relevant to understanding modern Blizzard games’ authentication processes.

The Grunt protocol was reverse engineered years ago, and has been reversed further as Blizzard added more stuff to it. The results have always been public in just about every World of Warcraft emulator ever, such as MaNGOS, TrinityCore, WCell, etc. One example of an implementation can be found here and here. Further, the opcodes are defined here. This stuff is not exactly revolutionary. Also, the packet names you see in those sources are what they are actually called in the client.

I really don’t want to appear to be a giant dick, but this stuff is not news, nor are the results published on the aforementioned blog and wiki entirely accurate.

(All this being said, the author of the aforementioned blog post is correct in his analysis of SRP.)

# C#/Mono: Playing with Pointers

I haven’t blogged in a while. Let’s fix that!

So, I’ve been programming a lot in D lately, which means systems programming, which means pointers! Pointers are amazing. You can do all sorts of crazy and awesome hacks with them. C# and the .NET Framework try to abstract pointers away from us. But fear not, for there are ways around this safety nonsense!

It turns out that on Mono, you can pin an object even if it contains managed data. This makes it safe to modify an object’s internal layout even in the presence of a moving GC (well, kinda, sorta). You can’t take the address of the object, however, which means we must resort to some IL hackery.

Thus, the code:

```using System;
using System.Reflection.Emit;
using System.Runtime.InteropServices;

public unsafe delegate void PointerAction(byte* pointer);

public static class ObjectExtensions
{
private static object _lock = new object();

{
lock (_lock)
{
{
var dm = new DynamicMethod(string.Empty, typeof(IntPtr), new[] { typeof(object) },
typeof(ObjectExtensions), true);

var il = dm.GetILGenerator();

il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Conv_I);
il.Emit(OpCodes.Ret);

}
}

}

public static unsafe byte* ToPointer(this object obj)
{
if (obj == null)
throw new ArgumentNullException("obj");

GCHandle handle;

try
{
handle = GCHandle.Alloc(obj, GCHandleType.Pinned);

}
finally
{
if (handle.IsAllocated)
handle.Free();
}
}

public static unsafe void WithPointer(this object obj, PointerAction action)
{
if (obj == null)
throw new ArgumentNullException("obj");

if (action == null)
throw new ArgumentNullException("action");

GCHandle handle;

try
{
handle = GCHandle.Alloc(obj, GCHandleType.Pinned);

}
finally
{
if (handle.IsAllocated)
handle.Free();
}
}
}```

(Kudos to ki9a on #mono for coming up with the dynamic method IL!)

Now, don’t try to run that on Microsoft .NET. It will blow up.

Now that we can get at the internals of objects, let’s try it out:

```static class Program
{
static unsafe void Main()
{
var str = "foo!";
object obj = new { foo = 0, bar = (object)null }; // create an object with an int32 field and a reference field

void* vtable = null;
void* sync = null;
int length = 0;
void* chars = null;

str.WithPointer(ptr =>
{
vtable = *(void**)ptr;
sync = *(void**)(ptr + sizeof(void*));
length = *(int*)(ptr + sizeof(void*) * 2);
chars = *(void**)(ptr + sizeof(void*) * 2 + sizeof(int));
});

obj.WithPointer(ptr =>
{
*(void**)ptr = vtable;
*(void**)(ptr + sizeof(void*)) = sync;
*(int*)(ptr + sizeof(void*) * 2) = length;
*(void**)(ptr + sizeof(void*) * 2 + sizeof(int)) = chars;
});

Console.WriteLine((string)obj); // prints "foo!"
}
}```

Oh boy. Some explanation is probably in order.

First of all, let me explain the layout of objects in Mono. Every object has a header consisting of two machine words. The first word points to the object’s VTable, which describes its type, methods, etc. The second word holds the so-called synchronization block, which is used to implement monitors (C# lock). Now, strings have two extra fields: One 32-bit field which holds the string’s length, and one machine word field which points to the raw characters backing the string.

Now look at this line:

`object obj = new { foo = 0, bar = (object)null }; // create an object with an int32 field and a reference field`

What we’re doing here is creating an anonymous object with a physical structure similar to that of a string. Needless to say, whether it actually is similar is completely implementation-defined. The runtime may decide to reorder fields as it sees fit, and may even make the foo field a 64-bit integer on a 64-bit system. But, what’s important here is that the resulting object has enough space to hold the contents of a string object.

Now we get to the fun stuff:

```str.WithPointer(ptr =>
{
vtable = *(void**)ptr;
sync = *(void**)(ptr + sizeof(void*));
length = *(int*)(ptr + sizeof(void*) * 2);
chars = *(void**)(ptr + sizeof(void*) * 2 + sizeof(int));
});```

Here, we read out the VTable, synchronization block, length, and character array fields of the “foo!” string object. It is (more or less) safe, since the WithPointer method ensures that the object is pinned while we do our stuff.

Next:

```obj.WithPointer(ptr =>
{
*(void**)ptr = vtable;
*(void**)(ptr + sizeof(void*)) = sync;
*(int*)(ptr + sizeof(void*) * 2) = length;
*(void**)(ptr + sizeof(void*) * 2 + sizeof(int)) = chars;
});```

Here we assign the values we read out from the string object earlier to the object we created with a similar physical layout to that of string objects. Our anonymously-typed object is now effectively a string.

Let’s prove that:

`Console.WriteLine((string)obj); // prints "foo!"`

Note two things here: First, the cast succeeded. It would normally have resulted in an InvalidCastException. So far so good. Second, the call actually prints what we expect. This means that we got the physical layout of the string object right.

Note that all of this was done on an x86 machine running 64-bit Linux with Mono 2.10.8. I have no idea whether it will work with any other Mono version, architecture, bitness, or operating system.

Will this break the runtime? Possibly! Will the GC explode? Likely! Will it leak memory? Definitely!

Don’t do this in production code. Like, seriously, don’t.

Update: As lupus points out, I actually got the string layout wrong! The characters of a string are embedded directly in the object. This code just turned out to work because of word size on 64-bit x86. I’ll leave it as an exercise to the reader to adapt the code to arbitrary amounts of embedded characters. ;)

# GithubSharp with ServiceStack.Text

At Xamarin, we’ve been using GithubSharp to access the GitHub API for some time. We ran into some issues with it, however, because the JSON serializers in .NET are buggy as hell (one had trouble deserializing a simple dictionary; another couldn’t handle large payloads). Therefore, we forked and branched the project and made it use ServiceStack.Text, which works nicely (and has the added effect of working on Mono).

Note that our branch is for version 2.0 of the GitHub API; the author of GithubSharp, Erik Zaadi, is now working on GithubSharp for GitHub’s 3.0 API, using ServiceStack.Text.

As some of you may know, I’m working on a compiler infrastructure written in D. While the framework itself is rather high-level (it’s very close to actually being half of a compiler front end), an actual compiler implementation is needed to see if the whole thing will work out as well as I hope.

Thus, Tony and I set out to design a simplistic functional programming language. It is heavily inspired by Haskell and OCaml, and has many similarities, though it does not have much in the way of OOP. In short, it’s a language with first-class functions, generics, records/discriminated unions, and finally, treats everything as a value (much like most FP languages). We call it Cesura.

So far, nothing of what I’ve mentioned is particularly new or innovative. In fact, very few FP languages don’t have the features I mentioned. However, one interesting feature that we thought up (and which, to our knowledge, hasn’t been used in any other language) is what we call overloaded functional types. I’ll spare you from any category theory and jump straight to the problem.

You’re given this code:

```sqr x : Int -> Int = x * x
sqr x : Float -> Float = x * x
f = sqr```

The problem is immediately obvious: Which of the two functions does f refer to?

You could perhaps solve the problem by doing:

`f : Float -> Float = sqr`

This, however, completely defeats type inference and has lots of corner cases. If you passed sqr directly to a function, what would you do then?

We came to the conclusion that in order to maintain type inference and still have overloaded functions, we’d need to carry the overloads directly in the type system. This means:

`f = sqr // The type of f is now: Int -> Int | Float -> Float`

Here, we introduce the concept of an overload set. The type of f is a function that has an overload set consisting of Int -> Int and Float -> Float.

There are several advantages in this sort of type system. One of them is the fact that any function value is implicitly convertible to any function type whose overload set is a subset of the overload set of the function value’s function type.

But that’s not all. You might ask: What happens if I try to call f (from above)? How will the compiler know which function in the overload set I intend to call? The answer to this question is actually very simple:

```x = f 2
y = f 4.0```

Given this code, look at what’s passed to f in the first call. Clearly, it’s an integer. Thus, we know that a call to the Int -> Int overload was intended. In the second call, we’re passing a floating-point value, and therefore we’re calling the Float -> Float overload. So, x is of type Int and y is of type Float.

You might ask why we didn’t just choose to incorporate type classes, considering I claim that we’re heavily inspired by Haskell. The answer to this boils down to simplicity: Cesura needs to be a simple language utilizing as many features of the MCI framework as possible. We’re creating a simple, practical language, not a language utilizing extremely complex (but certainly beautiful) type system techniques.

Lastly, we’d really like some input on this approach. We’re still not entirely sure that it is the right way to go about this, though it does seem to be the most promising solution that isn’t overly complicated to implement. Also, if you know of some other language that uses this technique, please let us know!

# C#: Dynamic and Extension Methods

What does the following program do?

```namespace DynamicExtensionMethods
{
internal static class Program
{
private static int Square(this int i)
{
return i * i;
}

private static void Main()
{
((dynamic)1).Square();
}
}
}```

`Unhandled Exception: Microsoft.CSharp.RuntimeBinder.RuntimeBinderException: 'int' does not contain a definition for 'Square'`

Apparently, RuntimeBinder doesn’t take extension methods into account. On one hand, it’s surprising because the dynamic binder supposedly acts like the C# compiler’s binder. On the other, RuntimeBinder is a framework thing and extension methods are a language feature. This makes me wonder if there would be any problematic corner cases with supporting extension methods in dynamic method calls…

# Three Reasons I Love Functional Programming

I realize a lot of people reading my blog are imperative programmers who haven’t looked into functional programming before. I figured I’d write a bit about why I find functional programming interesting and worthwhile.

You might think that I like functional programming because of first-class functions. You might think that I like it because of purity and immutability. Hell, you might even think that I like it because of natural recursion and tail calls. But no. Below are the three reasons I like the paradigm.

Everything is an expression: Typing return everywhere is a pain in the ass. The fact that the last expression in a function will be its result really cuts down on typing and reading. Additionally, this means that what you would usually call an if statement is actually an if expression. This implies that the last expression in the true/false paths are the result of the if expression. The same goes for match expressions, loop expressions, and so on. This makes it possible to write very clear code compared to the imperative equivalent.

Pattern matching: Basically the switch statement on steroids. Some (me being among them) will argue that this is what the switch statement always should have been, and that the switch statement in its current form is a language design mistake. Being able to match any value against any value makes for much more readable code, as compared to an if/else forest.

Discriminated unions: Ever wanted C unions but with less insanity and more safety? DUs allow you to use any type for your cases and with well-defined behavior. That alone is already great, but DUs truly shine when combined with fluent pattern matching syntax.

Most of the features I described here are present in all functional languages in one form or another, but they are particularly important in F# and Erlang which are the functional languages I take most interest in.

It might surprise some people that I didn’t list first-class functions and immutability. I like those concepts too, but I don’t think they’re what makes functional programming truly beautiful. This is ironic, because they’re probably the most basic traits of a functional programming language. But, in the time I’ve worked with functional languages, I haven’t found those two features to be the most appealing to me (don’t take that the wrong way; they are still great).