Project 4

Overview

You job is to implement a memory manager using the buddy algorithm as described by Dr. Knuth in The Art of Computer programming Volume 1 - Fundamental Algorithms. You will use the mmap() system call to get a large block of memory to manage. From there on, manage the chunk of memory returned by mmap using your own memory management functions.

Learning Outcomes

• 2.1 Demonstrate how low level memory is managed in user space
• 2.2 Explore the system call interface
• 3.1 Analyze a complex computing problem and apply principles of computing and other relevant disciplines to identify solutions.

Grading Rubric

Make sure and review the class grading rubric so you know how your project will be graded.

Task 1 - Setup

Follow the steps below to get your repository all setup and ready to use. The steps below show you how to use and setup GitHub codespaces. You are not required to use codespaces, all the steps below can be completed in the CS Lab or on your personal machine if you prefer.

Fork the starter repository

1. Fork the starter repository into your personal GitHub account: https://github.com/shanep/makefile-project-starter

2. In the new fork name the repository cs452-p4

Start a new Codespace

We will use GitHub Codespaces to do most of our coding. Codespaces is just VSCode in the cloud. This makes it really easy to setup a developer environment and code from any computer that has a browser and internet connection!

1. If you are asked to install recommended extensions click "install". You may not be asked to install extensions if you are already syncing your account.

You now should have a new repository (forked from the starter template) that is ready to use.

Task 2 - Prepare your repository

The starter repository is a bare bones template that you will need to update with the starter code below.

INFO

This project will be 100% unit test. You will not need to use the file app/main.c all your work will be done int src/lab.c and tests/test-lab.c

src/lab.h

#ifndef LAB_H
#define LAB_H

#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>


#ifdef __cplusplus
extern "C"
{
#endif
  /**
   * The default amount of memory that this memory manger will manage unless
   * explicitly set with buddy_init. The number of bytes is calculated as 2^DEFAULT_K
   */
#define DEFAULT_K 30

  /**
   * The minimum size of the buddy memory pool.
   */
#define MIN_K 20

  /**
   * The maximum size of the buddy memory pool. This is 1 larger than needed
   * to allow indexes 1-N instead of 0-N. Internally the maximum amount of
   * memory is MAX_K-1
   */
#define MAX_K 48

  /**
   * The smallest memory block size that can be returned by buddy_malloc value must
   * be large enough to account for the avail header.
   */
#define SMALLEST_K 6

#define BLOCK_AVAIL    1  /*Block is available to allocate*/
#define BLOCK_RESERVED 0  /*Block has been handed to user*/
#define BLOCK_UNUSED   3  /*Block is not used at all*/

  /**
   * Struct to represent the table of all available blocks do not reorder members
   * of this struct because internal calculations depend on the ordering.
   */
  struct avail
  {
    unsigned short int tag;     /*Tag for block status BLOCK_AVAIL, BLOCK_RESERVED*/
    unsigned short int kval;    /*The kval of this block*/
    struct avail *next;         /*next memory block*/
    struct avail *prev;         /*prev memory block*/
  };

  /**
   * The buddy memory pool.
   */
  struct buddy_pool
  {
    size_t kval_m;              /*The max kval of this pool*/
    size_t numbytes;            /*The number of bytes this pool is managing*/
    void *base;                 /*Base address used to scale memory for buddy calculations*/
    struct avail avail[MAX_K];  /*The array of available memory blocks*/
  };

  /**
   * Converts bytes to its equivalent K value defined as bytes <= 2^K
   * @param bytes The bytes needed
   * @return K The number of bytes expressed as 2^K
   */
  size_t btok(size_t bytes);


  /**
   * Find the buddy of a given pointer and kval relative to the base address we got from mmap
   * @param pool The memory pool to work on (needed for the base addresses)
   * @param buddy The memory block that we want to find the buddy for
   * @return A pointer to the buddy
   */
  struct avail *buddy_calc(struct buddy_pool *pool, struct avail *buddy);

  /**
   * Allocates a block of size bytes of memory, returning a pointer to
   * the beginning of the block. The content of the newly allocated block
   * of memory is not initialized, remaining with indeterminate values.
   *
   * If size is zero, the return value will be NULL
   * If pool is NULL, the return value will be NULL
   *
   * @param pool The memory pool to alloc from
   * @param size The size of the user requested memory block in bytes
   * @return A pointer to the memory block
   */
  void *buddy_malloc(struct buddy_pool *pool, size_t size);

  /**
   * A block of memory previously allocated by a call to malloc,
   * calloc or realloc is deallocated, making it available again
   * for further allocations.
   *
   * If ptr does not point to a block of memory allocated with
   * the above functions, it causes undefined behavior.
   *
   * If ptr is a null pointer, the function does nothing.
   * Notice that this function does not change the value of ptr itself,
   * hence it still points to the same (now invalid) location.
   *
   * @param pool The memory pool
   * @param ptr Pointer to the memory block to free
   */
  void buddy_free(struct buddy_pool *pool, void *ptr);

  /**
   * Changes the size of the memory block pointed to by ptr.
   * The function may move the memory block to a new location
   * (whose address is returned by the function).
   * The content of the memory block is preserved up to the
   * lesser of the new and old sizes, even if the block is
   * moved to a new location. If the new size is larger,
   * the value of the newly allocated portion is indeterminate.
   *
   * In case that ptr is a null pointer, the function behaves
   * like malloc, assigning a new block of size bytes and
   * returning a pointer to its beginning.
   *
   * if size is equal to zero, and ptr is not NULL, then the  call
   * is equivalent to free(ptr)
   *
   * @param pool The memory pool
   * @param ptr Pointer to a memory block
   * @param size The new size of the memory block
   * @return Pointer to the new memory block
   */
  void *buddy_realloc(struct buddy_pool *pool, void *ptr, size_t size);

  /**
   * Initialize a new memory pool using the buddy algorithm. Internally,
   * this function uses mmap to get a block of memory to manage so should be
   * portable to any system that implements mmap. This function will round
   * up to the nearest power of two. So if the user requests 503MiB
   * it will be rounded up to 512MiB.
   *
   * Note that if a 0 is passed as an argument then it initializes
   * the memory pool to be of the default size of DEFAULT_K. If the caller
   * specifies an unreasonably small size, then the buddy system may
   * not be able to satisfy any requests.
   *
   * NOTE: Memory pools returned by this function can not be intermingled.
   * Calling buddy_malloc with pool A and then calling buddy_free with
   * pool B will result in undefined behavior.
   *
   * @param size The size of the pool in bytes.
   * @param pool A pointer to the pool to initialize
   */
  void buddy_init(struct buddy_pool *pool, size_t size);

  /**
   * Inverse of buddy_init.
   *
   * Notice that this function does not change the value of pool itself,
   * hence it still points to the same (now invalid) location.
   *
   * @param pool The memory pool to destroy
   */
  void buddy_destroy(struct buddy_pool *pool);

  /**
   * @brief Entry to a main function for testing purposes
   *
   * @param argc system argc
   * @param argv system argv
   * @return exit status
   */
  int myMain(int argc, char** argv);

#ifdef __cplusplus
} //extern "C"
#endif

#endif

tests/test-lab.c

#include <assert.h>
#include <stdlib.h>
#include <time.h>
#ifdef __APPLE__
#include <sys/errno.h>
#else
#include <errno.h>
#endif
#include "harness/unity.h"
#include "../src/lab.h"


void setUp(void) {
  // set stuff up here
}

void tearDown(void) {
  // clean stuff up here
}



/**
 * Check the pool to ensure it is full.
 */
void check_buddy_pool_full(struct buddy_pool *pool)
{
  //A full pool should have all values 0-(kval-1) as empty
  for (size_t i = 0; i < pool->kval_m; i++)
    {
      assert(pool->avail[i].next == &pool->avail[i]);
      assert(pool->avail[i].prev == &pool->avail[i]);
      assert(pool->avail[i].tag == BLOCK_UNUSED);
      assert(pool->avail[i].kval == i);
    }

  //The avail array at kval should have the base block
  assert(pool->avail[pool->kval_m].next->tag == BLOCK_AVAIL);
  assert(pool->avail[pool->kval_m].next->next == &pool->avail[pool->kval_m]);
  assert(pool->avail[pool->kval_m].prev->prev == &pool->avail[pool->kval_m]);

  //Check to make sure the base address points to the starting pool
  //If this fails either buddy_init is wrong or we have corrupted the
  //buddy_pool struct.
  assert(pool->avail[pool->kval_m].next == pool->base);
}

/**
 * Check the pool to ensure it is empty.
 */
void check_buddy_pool_empty(struct buddy_pool *pool)
{
  //An empty pool should have all values 0-(kval) as empty
  for (size_t i = 0; i <= pool->kval_m; i++)
    {
      assert(pool->avail[i].next == &pool->avail[i]);
      assert(pool->avail[i].prev == &pool->avail[i]);
      assert(pool->avail[i].tag == BLOCK_UNUSED);
      assert(pool->avail[i].kval == i);
    }
}

/**
 * Test allocating 1 byte to make sure we split the blocks all the way down
 * to MIN_K size. Then free the block and ensure we end up with a full
 * memory pool again
 */
void test_buddy_malloc_one_byte(void)
{
  fprintf(stderr, "->Test allocating and freeing 1 byte\n");
  struct buddy_pool pool;
  int kval = MIN_K;
  size_t size = UINT64_C(1) << kval;
  buddy_init(&pool, size);
  void *mem = buddy_malloc(&pool, 1);
  //Make sure correct kval was allocated
  buddy_free(&pool, mem);
  check_buddy_pool_full(&pool);
  buddy_destroy(&pool);
}

/**
 * Tests the allocation of one massive block that should consume the entire memory
 * pool and makes sure that after the pool is empty we correctly fail subsequent calls.
 */
void test_buddy_malloc_one_large(void)
{
  fprintf(stderr, "->Testing size that will consume entire memory pool\n");
  struct buddy_pool pool;
  size_t bytes = UINT64_C(1) << MIN_K;
  buddy_init(&pool, bytes);

  //Ask for an exact K value to be allocated. This test makes assumptions on
  //the internal details of buddy_init.
  size_t ask = bytes - sizeof(struct avail);
  void *mem = buddy_malloc(&pool, ask);
  assert(mem != NULL);

  //Move the pointer back and make sure we got what we expected
  struct avail *tmp = (struct avail *)mem - 1;
  assert(tmp->kval == MIN_K);
  assert(tmp->tag == BLOCK_RESERVED);
  check_buddy_pool_empty(&pool);

  //Verify that a call on an empty tool fails as expected and errno is set to ENOMEM.
  void *fail = buddy_malloc(&pool, 5);
  assert(fail == NULL);
  assert(errno = ENOMEM);

  //Free the memory and then check to make sure everything is OK
  buddy_free(&pool, mem);
  check_buddy_pool_full(&pool);
  buddy_destroy(&pool);
}

/**
 * Tests to make sure that the struct buddy_pool is correct and all fields
 * have been properly set kval_m, avail[kval_m], and base pointer after a
 * call to init
 */
void test_buddy_init(void)
{
  fprintf(stderr, "->Testing buddy init\n");
  //Loop through all kval MIN_k-DEFAULT_K and make sure we get the correct amount allocated.
  //We will check all the pointer offsets to ensure the pool is all configured correctly
  for (size_t i = MIN_K; i <= DEFAULT_K; i++)
    {
      size_t size = UINT64_C(1) << i;
      struct buddy_pool pool;
      buddy_init(&pool, size);
      check_buddy_pool_full(&pool);
      buddy_destroy(&pool);
    }
}


int main(void) {
  time_t t;
  unsigned seed = (unsigned)time(&t);
  fprintf(stderr, "Random seed:%d\n", seed);
  srand(seed);
  printf("Running memory tests.\n");

  UNITY_BEGIN();
  RUN_TEST(test_buddy_init);
  RUN_TEST(test_buddy_malloc_one_byte);
  RUN_TEST(test_buddy_malloc_one_large);
return UNITY_END();
}

Once you have updated all the starter code lets make your first commit so everything is saved. Open up a terminal and lets make a commit!

git add --all
git commit -m "Added in starter code"

Task 3 - Implement Buddy

Implement the Buddy Algorithm.

WARNING

You are NOT allowed to use any functions from the math library! You are required to use bit shifting and masking for your calculations. So this means no pow() or log2() functions should be found in your code.

Task 4 - Write Unit tests

Follow the instructions in the project README to run the code coverage tool. Add enough tests beyond what the professor has given you to get as close to 100% coverage as possible.

Additional Resources

From the example in Knuth’s book we can calculate the buddy of a block of size 16. With the table above we know that a block of size 16 is K=4 so we will have 4 zeros at the right. Using the XOR operator we can calculate the buddy as follows:

   101110010110000
 ^ 000000000010000
------------------
   101110010100000

Knuth notation to C syntax quick reference

struct buddy_pool *pool;
struct avail *L;

Knuth notation	C syntax
AVAILF[k]	pool->avail[k].next
AVAILB[k]	pool->avail[k].prev
LOC(AVAIL[k])	&pool->avail[k]
LINKF(L)	L->next
LINKB(L)	L->prev
TAG(L)	L->tag
KVAL(L)	L->kval
buddyk(L)	buddy_calc(pool, L);

Power of 2 quick reference

As specified in the algorithm in order for everything to work you must work in powers of two! This includes the address that you get back from mmap. You will need to scale the address appropriately or you will calculate invalid buddy values. You can use the table below for a quick reference for up to K=40.

Power (k value)	Bytes	KiB/MiB/GiB/TiB
2^0	1
1	2
2	4
3	8
4	16
5	32
6	64
7	128
8	256
9	512
10	1,024	1 KiB
11	2,048	2 KiB
12	4,096	4 KiB
13	8,192	8 KiB
14	16,384	16 KiB
15	32,768	32 KiB
16	65,536	64 KiB
17	131,072	128 KiB
18	262,144	256 KiB
19	524,288	512 KiB
20	1,048,576	1 MiB
21	2,097,152	2 MiB
22	4,194,304	4 MiB
23	8,388,608	8 MiB
24	16,777,216	16 MiB
25	33,554,432	32 MiB
26	67,108,864	64 MiB
27	134,217,728	128 MiB
28	268,435,456	256 MiB
29	536,870,912	512 MiB
30	1,073,714,824	1 GiB
31	2,147,483,648	2 GiB
32	4,294,967,296	4 GiB
33	8,589,934,592	8 GiB
34	17,179,869,184	16 GiB
35	34,359,738,368	32 GiB
36	68,719,476,736	64 GiB
37	137,438,953,472	128 GiB
38	274,877,906,944	256 GiB
39	549,755,813,888	512 GiB
40	1,099,511,627,776	1 TiB

Hints

• There should be no hard coded constants in your code. You will need to use the macros defined in the C99 standard to get the correct width. For example to calculate a K value 64bit system you would write UINT64_C(1) << kval NOT 1 << kval
• Remember to take into account the size of your header when calculating your K value. If a user asked for 32 bytes you will need to use K=6 not K=5 to account for the header size.
• If the memory cannot be allocated, then your buddy_calloc or buddy_malloc functions should set errno to ENOMEM (which is defined in errno.h header file) and return NULL.
• You can’t use malloc/free/realloc/calloc from the C standard library.
• You will need to make extensive use of pointer arithmetic! When you are dealing with raw (untyped) memory make sure and cast the pointer to the correct type so it is moved the correct amount.
• Be mindful of the differences between sizeof(struct foo) and sizeof(struct foo*). The first instance give you the size of the struct while the second gives you the size of a pointer. If the size of the struct just happens to be the same as a pointer your code will appear to work until you either add a new member to foo OR you move to a system where the sizes of pointers are different. For example moving from a 64bit system to a 32 bit system or vice versa!
• Read Chapter 14 - Interlude: Memory API

Extra Fun Reading

• Appendix B. Index to Notations
• C99 Standard

Debugging Raw memory

In the C programming language we can allocate a chunk of memory on the heap and treat that chunk of memory as an array. If you are working on debugging a problem and want to inspect the contents of the array using the GUI debugger interface in VSCode you may have to tell the debugger (with a cast) that a pointer is actually pointing to a dynamically allocated array not a single variable. This example walks through how to display a pointer as an array that is embedded within a struct.

More reading about C and GDB.

• Reading C Declarations
• GDB Artificial Arrays
• GDB to LLDB usage
• VSCode Data inspection

Consider the struct declaration buddy_pool shown below. The avail member is a pointer that we must dynamically allocate and want to display in the debugger as an array. We can allocate the a buddy_pool struct (in the stack or data segment) and then dynamically allocate the avail array using malloc.

struct avail
{
    int tag;
    int kval;
    struct avail *next;
    struct avail *prev;
}
struct buddy_pool
{
    size_t kval_m;
    uintptr_t base;
    struct avail *avail; /*pointer to the start of the avail array*/
};
struct buddy_pool pool;
pool.kval = 9;
pool.base = 0;
pool.avail = malloc(sizeof(struct avail) * 9);

If we run the debugger we will see the variable pool with the element avail is displayed as a single variable not an array of 9 structs as we expected.

The element avail is just a pointer to the memory address of element and the debugger can’t determine the size of the array and thus will display it as a single struct instead of an array as expected.

Fortunately, all is not lost! Most debuggers allow you to set a watch on a memory location and you can force the debugger to cast the memory to a certain type. Both gdb and lldb have specific commands to display a memory block as an array. However, using casting works regardless of what debugger you are using.

If we add a new watch on a variable and then force the debugger to display the memory block as an array instead of a single variable we can easily inspect the data and track down any issues you are experiencing.

(struct avail(*) [9])pool->avail

For a plain old dynamic array you can add a watch expression that is set to to the desired type.

*(int(*)[10])A

Final Task - Submit your code

Now that you have completed all the tasks the only thing left to do is to submit your code as a patch so you can receive a grade for all your hard work.

Turn on Two Factor

Turn on Two factor authentication for your Boise State provided email account

DANGER

Do NOT skip this step. Boise State University uses Gmail as their email provider and Gmail requires you to use two factor authentication in order to generate an app password.

You need to use your Boise State University issued email account to send the email and you must have two factor authentication turned on.

Generate an app password

INFO

If you are working in GitHub codespaces you will need to setup SMTP for EACH project. This is because each codespace is tied to a specific repository and the settings are not shared. However, if you are working on your own personal machine or in the CS Lab then you will only have to setup SMTP once!

In order to use git send-email you will need to generate an app password. Navigate to https://security.google.com/settings/security/apppasswords and generate a new app password. Make sure and copy the password before you close the window because you will not be able to see it again.

I can't generate a password

If you get the error shown below it typically means that you have not enabled two factor authentication. Follow these steps to resolve the issue:

1. Go back and ensure you have two factor authentication enabled.
2. Log out of your Gmail account
3. Log back into your Gmail account and make sure you did have to use two factor authentication
4. If the steps above fail then open an incognito tab and go back to the first step
5. If you still have issues reboot your machine and go back to the first step

Setup SMTP

1. Open up a terminal in codespaces

2. In the terminal type git config --global --edit and modify the file with the info listed below. You will need to change the info listed below to match your own name, email and App Password that you generated in the previous step.

[User]
	name =  YOUR NAME
	email = YOURNAME@u.boisestate.edu
[sendemail]
	smtpserver = smtp.gmail.com
	smtpuser = YOURNAME@u.boisestate.edu
	smtpPass = xxxx xxxx xxxx xxxx
	smtpencryption = ssl
	smtpserverport = 465

Congrats you should be all setup to send code patch's over email. Now lets create a patch!

Create a patch file

We are now going to do what is called a squash merge and then create a patch file with all our changes in one commit.

1. First lets fetch the upstream branch. This is the branch that you originally forked from at the start of the project

git fetch upstream

2. Checkout a new branch named submit from the upstream/master branch.

git checkout upstream/master -b submit

3. Now we will do a squash merge all the commits we did onto our new submit branch.

git merge --squash master

4. Now commit those new changes to your submit branch

git commit -m "Submit project"

5. Push your submit branch to GitHub

git push -u origin

6. Open up a web browser and navigate to your repository on GitHub and confirm that your submit branch is correctly pushed. Open up the files and make sure that everything looks good before going to the next step.

Install Libraries

If you are working on codespaces you will need to install the required dependencies before you attempt to email out your patch file.

make install-deps

Email Patch File

First make sure you are still on the submit branch that you created. If you type git branch you should see a star next to the submit branch that indicates you are currently on the submit branch.

$ git branch
  master
* submit

WARNING

You MUST test your patch by emailing it to yourself first! You will go through all the steps below with your own email. After you have sent the email to yourself and tested it you can then email your submission to the class mailing list!

Finally we can create our patch to email out!

git send-email --to youremail@u.boisestate.edu HEAD^

You should see results similar to what is show below.

$ git send-email --to youremail@u.boisestate.edu HEAD^
/tmp/T/NWEw4f1sIj/0001-Submit-project-2.patch

From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

The Cc list above has been expanded by additional
addresses found in the patch commit message. By default
send-email prompts before sending whenever this occurs.
This behavior is controlled by the sendemail.confirm
configuration setting.

For additional information, run 'git send-email --help'.
To retain the current behavior, but squelch this message,
run 'git config --global sendemail.confirm auto'.

Send this email? ([y]es|[n]o|[e]dit|[q]uit|[a]ll): y
OK. Log says:
Server: smtp.gmail.com
MAIL FROM:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project 2
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

Result: 250

You should now be able to check your email and see your patch. Be aware that sometimes email delivery is slightly delayed so you may have to wait a few minutes for it to show up. Make sure and check your spam folder if you don't see any mail.

Test your patch

You can now get your patch from Gmail and test it to make sure that everything works and your patch was correct.

1. Checkout a new branch named test-patch from the upstream/master branch

git checkout upstream/master -b test-patch

2. Push your new test-patch branch to your repo instead of the upstream

 git push -u origin

3. Get the patch file from Gmail

4. Copy the email to your clip board

5. Create a new file and paste the contents that you just copied and save it in the root folder in a file named my-patch.txt.

6. Make sure you saved the file correctly. It should show up in the file explorer as shown below.

7. Now apply that patch to your new test-patch branch

git am my-patch.txt

8. Commit your patch

git commit -m "Testing my email patch"

9. Push your test patch branch to your Github Account

git push

10. After you have successfully applied the patch you can delete the file my-patch.txt. Don't commit the file my-patch.txt it is just a temporary file that you don't want to save.

11. Finally open up the browser again and make sure you have 3 branches master, submit, and test-patch. The submit and test-patch branches should be identical. Each should have exactly 1 commit from you with all your changes.

Submit your Patch for grading

Assuming you have successfully completed all the steps above with your own email and everything looked good you can now submit your patch for grading.

DANGER

Do not use the class mailing list to test your patch. You should only send an email to email is in the syllabus after you have tested the process with your own email. Spamming the mailing list with excessive patches will result in a lower grade.

When you submit to the mailing list you will automatically be cc'd on the email so you will have a copy in your own email as proof that you completed the assignment.

You are allowed to submit up to 3 times without penalty.

Open a terminal and submit your patch.

git checkout submit
git send-email --to email is in the syllabus HEAD^

Assuming all went well you are now complete! You have created a patch file from a squash merge, emailed it and tested the resulting patch. You are well on your way to becoming an advanced git user!

Submitting

You do not need to submit anything to canvas for this assignment. Your email is your submission, your grade will be updated after the due date (and late window) have passed.