Building a Simple Memory Allocator

Learning Objectives

• Demonstrate the impact that the quality of a dynamic memory allocation library can have on application performance.

• Implement a simple fixed-size allocator

• Explain how your allocator could be a piece of a more comprehensive allocator

A Simple Fixed Sized Allocator

Pull today's code from the cs61-exercises repository. It is in the l05 directory. As explained in the README.txt file:

membench.c

    A program for benchmarking different malloc implementations.
`     We allocate 4096 `memnode` objects, then, NOPERATIONS times `
    (which defaults to 10,000,000), free one object and allocate
`     another. `memnode` is declared in `membench.h`. `

    membench uses an "arena" for its allocations. An arena is an
    object that encapsulates a set of allocations and frees. You
    can use arenas just to capture statistics or to encapsulate
    state for a specialized allocator.

    membench links with different allocator libraries. The simplest
`     is mb-malloc.c, which implements the `memnode_alloc()` `
`     functions with malloc and free. Run this with `./membench-malloc`. `
    Run a different number of allocations and/or simultaneous
`     threads with `./membench-malloc NOPERATIONS NTHREADS`. `
    But it's more interesting to see how much time a run takes.
`     For this, use the `time` program: `
        time ./membench-malloc

A memnode allocator

In today's exercise, you will develop an allocator for memnode structures, described in membench.h. Since your allocator is always going to be called upon to allocate objects of the same size, one would expect that you can build something much faster than the general purpose allocator that malloc uses.

Given the declaration in membench.h, how large are memnodes?

Read the comments at the beginning of mb-arena.h describing how we are going to represent the arena (the storage in which we'll store our memnodes). Before we get into the details of your allocator design, we ought to be able to write several of the functions you need to complete.

You will build your implementation by typing make membench-arena.

Creating the Arena

Fill in the function memnode_arena_new. It need not actually allocate space for the memnodes. It simply needs to set up the arena so that the first time memnode_alloc is called, the right thing happens. You may use malloc to create space for your memnode_arena and memnode_group structures.

Once you have written memnode_arena_new, you should also be able to write memnode_arena_free.

Tip: Compile early and often! Make sure your code compiles with the new functions you've written.

Tip: Test early and often! Although membench requires a fully working implementation to run completely, there are a number of ways you might test your code right now. You can write a separate program. You can add a call to memnode_arena_free right after you allocate the arena and then exit. You can run things in the debugger. Try a variety of these techniques, but whatever you do, test each piece as you develop it. (Note: the tests in assignment 1 were designed to provide incremental testing to your debugging malloc implementation so that you didn't need to have everything fully functional at once. This "test early; test often" philosophy is critical to building good software.)

Designing Free Space Management

You now have one major design decision to make -- how will you keep track of which memnodes are in use (e.g., have been allocated) and which are available for allocation. Here are some questions to think about when you design this.

1. When will you need to allocate a new memnode_group ? (You need not worry about freeing memnode_group structures until you free the arena.)

2. Is there a way to design management of the free/allocated space so that it will take you constant time to allocate/free a node?

3. How much space will you require to manage your free/allocated space? What fields will you need to add to your existing structures?

Use scratch paper or your whiteboards to illustrate your design. When you think you've got a good method for tracking your free/allocated memnodes, raise your hand and run your design past a member of the course staff.

Go ahead and code it up

Once a staff member has checked your design, go ahead and complete your implementation. You will probably need to:

1. Modify new and free to initialize and clean up any new fields you added. (And then test this.)

2. Implement memnode_alloc. You can test this before moving on to memnode_free. You may not be able to run the test to completion, but you should be able to get through the set of initial allocations.

3. Now implement memnode_free

At this point, you'll need to spend some time testing. Try running membench with different parameters. When everything is working, you can compare your fixed-size allocator to malloc by comparing the timed output of membench-arena with membench-malloc. Run each one multiple times.

Should you finish early

If you have extra time, design a second, completely different method to track free and allocated memnodes. Be sure to save your original so that you can compare your two implementations.

Before you Leave

Shockingly, we have another survey for you to complete!