Safe memory usage in C# part 1/2

Update: Part two is now available here.

Usually, the C# garbage collector does a pretty good job. The problem is, however, that you constantly run the risk of running out of memory in the middle of a program.

How big a problem is the dreaded OutOfMemoryError exception?

Well, imagine in the most benign case that you are programming a game. The player accidentally leaves his Oracle server running in the background, and is unaware that he doesn't really have enough memory for the entire game. After playing until the climatic ending with 302 enemies on the screen at once, he is hit in the face with an OutOfMemoryError crash. He is not happy, and will likely whine on your forums for weeks to come.

In the more serious case, imagine that you are running Critical Server Application (I made up that name - it's just an example). The server controls something critical, like the lock on the fire escape door, or a nuclear reactor cooling rod. When the application crashes, you really need it to leave its now uncontrolled fire door or nuclear reactor in a safe state by doing something like unlock the fire door or shut down the reactor.

Yikes! How can I ensure safety?

Turns out, this problem is well known in the game programming industry, and there is a well-known solution to it. Simply allocate a ton of memory up front and do manual memory management yourself!

Really? That easy?

Well, not actually easy; manual memory management is both boring and tricky to do yourself. Doing that for every object in your application would be too much effort for most people. You should aim for a middle ground where you only have critical data in the up-front-heap.

In the game scenario, you can build the game save object in the up-front-heap, so you will always be able to save the game in the event of a crash. Your user can then shut down whatever program is eating up his memory and pick up the game from where it crashed.

In the nuclear reactor scenario, you can carefully utilize only the up-front-heap during safe shutdown. In the event of a program crash, you will always be able to shut down the reactor.

The code

So of course I had to code this. :)

I decided to keep the API close to the well-known C-style memory management functions and use the names "malloc", "free" and "memcpy". The whole linear memory manager is of course implemented as a wholly static class, which looks like this:

// LinearMemory.cs
namespace LinearMemoryEntry {
    using System.Linq;

    static class LinearMemory {
        public static byte[] mem;
        private static bool[] bounds;

        static LinearMemory() {
            // Allocate 10 megabytes initially.
            mem = new byte[1024 * 1024 * 10];
            bounds = new bool[mem.Count()];
            for (int i = 0; i < mem.Count(); bounds[i++] = false) ;
        }

        /// <summary>
        /// Allocate memory.
        /// </summary>
        /// <param name="size">Size of memory to allocate.</param>
        /// <returns>Ptr to newly allocated memory</returns>
        public static int malloc(int size) {
            int ptr = FindArea(0, size);
            bounds[ptr] = true;
            bounds[ptr + size - 1] = true;
            return ptr;
        }

        /// <summary>
        /// Free allocated memory.
        /// </summary>
        /// <param name="ptr">Ptr to allocated memory.</param>
        public static void free(int ptr) {
            bounds[ptr] = false;
            int i = ptr;
            while (!bounds[++i]);
            bounds[i] = false;
        }

        /// <summary>
        /// Copy a chunk of memory.
        /// </summary>
        /// <param name="srcPtr">Memory to copy from.</param>
        /// <param name="tgtPtr">Memory to copy to.</param>
        /// <param name="len">Length of memory chunk.</param>
        public static void memcpy(int srcPtr, int tgtPtr, int len) {
            for (int i = 0; i < len; i++)
                mem[tgtPtr + i] = mem[srcPtr + i];
        }

        private static int FindArea(int from, int size) {
            tryAgain:
            int foundSize = 0;
            int at = from;
            while (foundSize < size) {
                if (at >= mem.Count())
                    throw new OutOfMemoryException();
                if (bounds[at]) {
                    while (!bounds[++at]) ;
                    from = at + 1;
                    goto tryAgain;
                }
                foundSize++;
                at++;
            }
            return from;
        }
    }
}

As with the original C functions, calling malloc() gets you a pointer to a memory area of the requested size and ensures that it will not be returned on another call to malloc() until you free() it.

The memory is accessed via the LinearMemory.mem member which is just an array of bytes. If you have malloc()-ed 5 bytes to pointer p, you can use mem[p+0], mem[p+1] ... mem[p+4] for whatever purpose you want.

Keeping track of which memory is allocated is done via the LinearMemory.bounds member, which is a boolean array of the same length as the LinearMemory.mem byte array. When reserving a chunk of memory from 40 to 49, we simply set up "fenceposts" by setting bounds[40] and bounds[49] to true to mark the area as reserved. This way the malloc() function can just scan for the first big enough chunk of memory that is outside two "fenceposts", and the free() function can just scan along the memory from the given pointer to the next "fencepost" to know exactly which memory chunk to free. Since the bounds array takes up only 1/8 (remember, a boolean need only 1 bit!) of the mem array, it's not much overhead. If we say that the mem array is of size O(n), then the bounds array is of size O(n/8)=O(n).

This gives us a total of O(2n), which is linear. Since you can't go better than linear when dealing with memory, this model is pretty tight.

How do I store my strings and ints in there, then?

In C#, you can convert any data structure to a bunch of bytes. In this post, I will show you how to do this with strings. In the next post, I'll do some more complex data structures:

// LinearMemoryTools.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LinearMemoryEntry {
    /// <summary>
    /// Useful tools for marshalling and unmarshalling data to and from
    /// LinearMemory.
    /// </summary>
    class LinearMemoryTools {
        // An encoding can access the bytes of a string.
        private static Encoding enc = new ASCIIEncoding();

        // Insert byte[] into memory.
        public static void Insert(int ptr, byte[] src) {
            for (int i = 0; i < src.Count(); i++)
                LinearMemory.mem[ptr + i] = src[i];
        }

        /// <summary>
        /// Access the bytes of a string.
        /// </summary>
        /// <param name="s">The string.</param>
        /// <returns></returns>
        public static byte[] StringBytes(string s) {
            return enc.GetBytes(s);
        }

        /// <summary>
        /// Retrieve a string from memory.
        /// </summary>
        /// <param name="ptr">Ptr to string.</param>
        /// <param name="len">Len of string.</param>
        /// <returns></returns>
        public static string BytesString(int ptr, int len) {
            return enc.GetString(LinearMemory.mem, ptr, len);
        }
    }
}

Stringing it all together

Now that we have all we need, let's try a test run with some strings:

// HelloWorldFactory.cs
namespace LinearMemoryEntry {
    using System.Windows.Forms;

    class HelloWorldFactory {
        public static void Run(TextBox stdout) {
            // The string "Hello world!".
            string helloworld = "Hello world!";

            // Allocate memory for our text.
            int p = LinearMemory.malloc(13);

            // Put our text into the linear memory.
            LinearMemoryTools.Insert(
                p, LinearMemoryTools.StringBytes(helloworld));

            // Make some copies!
            int[] p_copy = new int[10];
            for (int i = 0; i < 10; i++) {
                p_copy[i] = LinearMemory.malloc(13);
                LinearMemory.memcpy(p, p_copy[i], 13);
            }

            // Print out all copies.
            for (int i = 0; i < 10; i++) {
                var s = LinearMemoryTools.BytesString(p_copy[i], 13);
                stdout.Text += "\r\nCopy " + (i + 1) + ": " + s;
            }

            // Always remember to free memory when you are finished with it!
            LinearMemory.free(p);
            for (int i = 0; i < 10; LinearMemory.free(i++)) ;
        }
    }
}

Then we create a simple winforms app to run it. The window looks like this:

And this is the codebehind:

// Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace LinearMemoryEntry {
    public partial class ProgramForm : Form {
        public ProgramForm() {
            InitializeComponent();
            this.FormClosed += new FormClosedEventHandler(
                ProgramForm_FormClosed);
        }

        void ProgramForm_FormClosed(object sender, FormClosedEventArgs e) {
            Application.Exit();
        }

        // Run HelloWorld button
        private void button1_Click(object sender, EventArgs e) {
            textBox1.Text += "\r\nRunning HelloWorld...";
            HelloWorldFactory.Run(textBox1);
        }

        // Clear button
        private void button2_Click(object sender, EventArgs e) {
            textBox1.Clear();
        }
    }
}

Don't worry, I will include the full solution with all files in the next post.

Running it gives us:

Nice!

So, what really happened? Well, as you can see from the source code, we have successfully stored the string "Hello world!" in our LinearMemory, copied it 10 times, and retrieved and printed out the copies.

Coming up...

In the next post, I will show you how create, use and retrieve more complex real-world structures whose data live entirely in the LinearMemory. Stay tuned!