Saturday 17 April 2010

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!

11 comments:

  1. This is insane. Object pools are not used to prevent out of memory errors. If you need to make sure you always have a bunch of Foo objects, you should just use an object pool instead of rolling your own free and malloc. Your 'safe memory usage' is not safe at all, for the love of Christ.

    ReplyDelete
  2. Don't forget, he has 6 years of system development...

    ReplyDelete
  3. Being a plumber for six years doesn't automagically mean that you're a good plumber.

    ReplyDelete
  4. Oh. My. Procreating. Deity. In what culture is there a seventeenth fool day?

    But if I told you it wouldn't even work, `you'd come up with something more convoluted.

    ReplyDelete
  5. Hi, thanks for the comments. I am glad to see that leaving anonymous comments open was not in vain.

    Anonymous: Nice plumber parable *zing*-er. :) While I know your comment was made in jest, I would like to point out that being a plumber for 6 years does mean you do get quite good at knowing which pipes to use for which occasions.

    peterchen: I can assure you, it *does* work. I would not write up an entire post about this unless I had working test code. :) In the soon-to-come part #2, I will attach the entire solution.

    ReplyDelete
  6. Why do you need a boolean array for every byte? This is a stupid implementation of malloc.

    ReplyDelete
  7. The real problem with this is that this implementation is really naive and inefficient.

    First malloc and free take a long time to finish and second it is a memory hog.

    You should learn some data structures or something. I guess being bad at programming comes with being a C# programmer :D

    ReplyDelete
  8. Wow... Just wow...

    Why don't you try looking at how malloc() works in real systems.

    http://gee.cs.oswego.edu/dl/html/malloc.html

    ReplyDelete
  9. As if the bounds array took only 1/8 of the mem array! Yes, you only need one bit to be set to be true, but each memory address points to a byte. So, unless your bool array uses byte masks to test for truth, the bounds array is actually as big as your mem array. And linear time is not the best you can get with memory management...

    ReplyDelete
  10. Hi Anonymous, and thanks for the comment.

    Please see the msdn documentation for Bit Array http://msdn.microsoft.com/en-us/library/system.collections.bitarray.aspx - it basically says that it pigeonholes 8 bit values into the same byte, so the 1/8 argument stands. :)

    ReplyDelete
  11. I like the fish tank..

    ReplyDelete