Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

11/1 Kernel4: Building kmalloc -- the kernel's malloc implementation

You may have noticed that you were not able to call malloc in Weensy OS. Most real kernels provide a kernel level implementation of malloc called kmalloc and kfree. We're going to help you build a simple implementation of these routines for Weensy. For now, you may assume that you do not need to support allocations larger than a page size (4096). In fact, you can assume that you do not need to support allocations larger than a page size minus some overhead. (If you're not sure what we mean by overhead, think about what you used to manage malloc'd memory in assignment 1 -- you will undoubtedly want some kind of similar structure here.)

In the cs61-exercises repository, you'll find a version of Weensy in kernel4x. The file k-malloc.c contains some test harness code and skeleton functions for kmalloc and kfree. We've set up a structure so that you can write your malloc implementation at user level (directly on the appliance, not on Weensy) and test it there. Once that is working, in theory, you should be able to take the same code and run it inside of Weensy! If you try to do that now (e.g., make run), you'll see a panic telling you that malloc failed -- that isn't too surprising since you haven't implemented it yet.

At the top of the k-malloc.c file, you'll see some code surrounded by #ifdef STANDALONE -- this is what lets you run either at user-level or in Weensy. Do not change anything between the #ifdef and the #endif. Your implementation should be expressed in terms of the macros GETPAGE and FREEPAGE which will get you a chunk of memory of size 4096 bytes. In the user-implementation, we simply call malloc. In the Weensy implementation, we obtain an unused page from the operationg system. You job is to use those blocks relatively efficiently to satisfy the much smaller requests that will be made to malloc.

If you prefer to do this without further hints, go for it now! Use the script testkmalloc.sh to build and test your user-level implementation. (We use valgrind to check that your implementation frees everything it allocates.)

If you're prefer some hints:

1. You'll probably want a static variable or two to keep track of blocks that you've gotten from malloc or the operating system. Additionally, you'll undoubtedly want to design some meta-data structure that you will use to keep track of the space that you've allocated. (Think Problem Set 1).

2. Next, you might want to get kmalloc and kfree working as simply as possible: regardless of the size requested, return the entire page that you get from malloc or the operating system. If you implement both kmalloc and kfree this way, you should be able to run both at user-level and in Weesy, except you'll run out of memory in Weensy -- feel free to change NALLOCS for now, so you can test it. (Don't forget to verify that the caller did not ask for more memory than you can reasonably give out -- after all, you're programming in the kernel now -- you should be defensive!)

3. You might claim that you are now done, but this is a terribly inefficient implementation! Let's get smarter. Modify your implementation so that if the user asks for only a few bytes, you return a small number of bytes (the amount requested plus some overhead). This will undoubtedly require changes in both kmalloc and kfree. Don't worry too much about using every scrap of memory -- get something working!

4. Now you can start to improve your implementation in a couple of ways. You may do some or all of the following:

5. Finally, if you've got an implementation that you like, see if you can modify Weensy to dynamically allocate process structures rather than using a statically allocated, fixed size array!

Solution Video