• C Programming Assignment 3
  • Goals
  • Synopsis
  • Submission
    • Github
    • Canvas
  • Grading
    • Bonus
    • Note on points
  • Compiler
  • Due date
  • Honor code
  • Use of libraries
  • Coding style
  • References
  • Detailed Instructions
    • Prerequisites
    • Overall goal
    • API Functions
    • Data Structures
    • Static Functions
    • Static Variables
  • Visualization
    • Diagram 1 Before intialization
    • Diagram 2 After initialization
    • Diagram 3 After opening a pool
    • Diagram 4 After one allocation
    • Diagram 5 After two allocations
    • Diagram 6 After a deallocation
    • Diagram 7 After another allocation
  • TODO

dynamic memory management with the C language

Note: cmocka has to be built installed separately and dynamically linked to the project. You can find directions in os-playground. The CMakeLists.txt has entries for Linux (Ubuntu) and MacOS. On Windows with Cigwin/MinGW, it should be similar but the path has to be adjusted. If someone figures it out, please create a pull request for the addition.

1. Practice development in the C programming language.
2. Learn to manage (allocate/deallocate) dynamic memory (aka memory on the heap/free store).
3. Get a feel for the memory management overhead in an operating system.
4. Get a feel for the design tradeoffs in the design and implementation of an operating system.
5. Get a basic understanding of the operation of malloc and the heap.
6. Practice working with a variety of data structures.
7. Practice programming with pointers.
8. Prepare for the development of the Pintos projects.
9. Develop good coding style.

C PA 3 asks you to implement a library for a memory pool manager which allocates dynamic memory blocks from a set pre-allocated region, mimicking the functionality of the C Standard Library function malloc(). You are given a header file (the user API) mem_pool.h and a source file mem_pool.c with data structures for a suggested implementation. You are not supposed to change the header file and are free to use the infrastructure in the source file to implement the user-facing functions in the header, or come up with your own.

C PA 3 is an assignment in the test-driven development (TDD) style. The provided main.c driver file executes a suite of unit tests against your implementation, and your score depends on how many tests your code passes. The tests use the cmocka unit-test framework.

You need to fork this repository and git clone it to your development environment. When you are done and your code works, git commit all your changes and git push to your forked (aka remote) repository. Work in the master branch.

Submissions are one per team. If you haven't done so, create a git account for your team. The name should look like ucd-[course]-[team-color]-s18. For example, ucd-os-orange-s18 or ucd-unix-black-s18. (If you want, you can create an organization but that might be overkill.) Make all team submissions from this account.

Both team members have to make an assignment submission on Canvas before the deadline. You only need to enter the clone URL of your project repository (e.g. https://github.com/ivogeorg/msl-clang-001.git).

Max points: 250 You get 10 points for each test passed, for a maximum total of 250 for the full regular submission.

Bonus tasks may be scored differently from regular submission.

1. Max points: 100. Implement data structure growth.
2. Max points: 50. Pass stress test.
3. Max points: 50. Beat the runtime of the reference implementation. Test will be performed on demand on a third-party machine. Might require additional setup to ensure fairness.
4. Max points: 50. Design a plausible way to perform bounds checking on allocation usage and prevent overwriting.
5. Max points: 250. Implement the library with (4). Might require additional tests.

Points for regular and bonus tasks are all cumulative for your course grade. This means that if a certain number of total points is equivalent to a letter grade of A, it is entirely possible for you to have more points. This allows a form of makeup and smooths out the effect of random life events.

Your program should run on a C11 compatible compiler.

The assignment is due on Sun, Feb 11, 2018, by 23:59 Mountain time. The last commit to your C PA 3 repository before the deadline will be graded.

Free Github repositories are public so you can look at each other's code. Please, don't do that. You can discuss any programming topics and the assignments in general but sharing of solutions diminishes the individual learning experience of others. Assignments might be checked for plagiarism without warning and a plagiarism claim may be raised against you.

For this assignment, no external libraries should be used, except for the ANSI C Standard Library. The implementation of the data structures should be your own. We will use library implementations of data structures and programming primitives in the Pintos assignments.

Familiarize yourself with and start the following coding style guide. While you are not expected to follow every point of it, you should try to follow it enought to get a feel for what is good style and bad style. C code can quickly become unreadable and difficult to maintain.

The C Reference, which you should get confortable consulting.

The ISO C Standards defines the language. A freely available draft C11 Standard, if you want to dig deep.

This C98 Library Reference seems to be the standard reference. You should not expect many changes, though it's always good to work off a latest copy of your library reference, which should be available through the vendor/implementor.

The following compendia of frequently asked questions about C are excellent resources for the dusty corners, non-sequiturs, and best practices in C programming:

1. C Programming FAQs
2. FAQs at CProgramming.com

A long list of C/C++ software resources.

Two guides for implementation of malloc(): here and here.

1. An installation as in cmocka-mem-pool.

The memory pool will work roughly like the dynamic memory management functions malloc, calloc, realloc, free. Unlike the *alloc functions,

• the metadata for allocated blocks will be kept in a separate dynamic memory section;
• there will be multiple independent memory pools to allocate from;
• there is less hiding of (some of) the allocation metadata, to help with debugging and testing.

1. alloc_status mem_init();

   This function should be called first and called only once until a corresponding mem_free(). It initializes the memory pool (manager) store, a data structure which stores records for separate memory pools.

2. alloc_status mem_free();

   This function should be called last and called only once for each corresponding mem_init(). It frees the pool (manager) store memory.

3. pool_pt mem_pool_open(size_t size, alloc_policy policy);

   This function allocates a single memory pool from which separate allocations can be performed. It takes a size in bytes, and an allocation policy, either FIRST_FIT or BEST_FIT.

4. alloc_status mem_pool_close(pool_pt pool);

   This function deallocates a single memory pool.

5. void * mem_new_alloc(pool_pt pool, size_t size);

   This function performs a single allocation of size in bytes from the given memory pool. Allocations from different memory pools are independent. Note: There is no mechanism for bounds-checking on the use of the allocations.

6. alloc_status mem_del_alloc(pool_pt pool, void * alloc);

   This function deallocates the given allocation from the given memory pool.

7. void mem_inspect_pool(pool_pt pool, pool_segment_pt *segments, unsigned *num_segments);

   This function returns a new dynamically allocated array of the pool segments (allocations or gaps) in the order in which they are in the pool. The number of segments is returned in num_segments. The caller is responsible for freeing the array.

1. Memory pool (user facing)

   This is the data structure a pointer to which is returned to the user by the call to mem_pool_open. The pointer to the allocated memory and the policy are contained in the structure, along with some allocation metadata. The user passes the pointer to the structure to the allocation/deallocation functions mem_new_alloc and mem_del_alloc. The user is not responsible for deallocating the structure.

   Structure:

   typedef struct _pool {
      char *mem;
      alloc_policy policy;
      size_t total_size;
      size_t alloc_size;
      unsigned num_allocs;
      unsigned num_gaps;
   } pool_t, *pool_pt;

   Behavior & management:

   1. Passed to all functions that open, allocate on, dealocate from, and close a pool.
   2. The metadata contained in the structure is used by the library, so should not be overwritten by the user. It is provided for testing and debugging.

2. Allocation record (library static)

   The mem pointer is returned to the user. The user passes this pointer and the pointer to the structure of the containing memory pool to the deallocation function mem_del_alloc.

   Structure:

   typedef struct _alloc {
      char *mem;
      size_t size;
   } alloc_t, *alloc_pt;

3. Pool manager (library static)

   This is a data structure that the mem_pool library uses to store the private metadata for a single memory pool. It is hidden from the user.

   Structure:

   typedef struct _pool_mgr {
      pool_t pool;
      node_pt node_heap;
      unsigned total_nodes;
      unsigned used_nodes;
      gap_pt gap_ix;
      unsigned gap_ix_capacity;
   } pool_mgr_t, *pool_mgr_pt;

   Note: Notice that the user facing pool_t structure is at the top of the internal pool_mgr_t structure, meaning that the two structures have the same address, and the same pointer points to both. This allows the pointer to the pool received as an argument to the allocation/deallocation functions to be cast to a pool manager pointer.

   Behavior & management:

   1. The pool manager holds pointers to all the required metadata for the memory allocations for a single pool
   2. The functions which make allocations in a given pool have to pass the pool as their first argument.
   3. The gap_ix_capacity is the capacity of the gap index and used to test if the index has to be expanded. If the index is expanded, gap_ix_capacity is updated as well.

4. (Array-packed linked-list) node heap (library static)

   This is a packed linked list which holds nodes for all the segments (allocations or gaps) in a pool, in ascending order by memory address. That is, the first node is always going to point to the segment that starts at the beginning of the pool. This data structure is hidden from the user, except that the num_allocs and num_gaps variables in the user-facing pool_t structure are in sync with the node heap.

   Structure:

   typedef struct _node {
      alloc_t alloc_record;
      unsigned used;
      unsigned allocated;
      struct _node *next, *prev; // doubly-linked list for gap deletion
   } node_t, *node_pt;

   Behavior & management:

   1. This is a linked list allocated as an array of node__t structures. If a node has used set to 1, it is part of the list; otherwise, it is an unused node which can be used for a new allocation or gap.
   2. The first node is always present and should always point to the top segment of the pool, regardless of the type of segment (allocation or gap).
   3. An active list node (used == 1) is either an allocation (allocated == 1) or a gap (allocated == 0).
   4. The list is doubly-linked to simplify the deallocation of an allocated sector between two gap sectors.
   5. The linked list is initialized with a certain capacity. If necessary, it should be resized. See the corresponding static function and constants in the source file.

5. Gap index (library static)

   This is a simple array of gap_t structures which holds an element for each gap that exists in a given pool and is sorted in an ascending order by size.

   Structure:

   typedef struct _gap {
      size_t size;
      node_pt node;
   } gap_t, *gap_pt;

   Behavior & management:

   1. The gap entries hold the size of the gaps and point to the corresponding nodes in the node heap linked list.
   2. (bonus) The array is initialized with a certain capacity. If necessary, it should be resized. See the corresponding static function and constants.
   3. Use the num_gaps variable in the user-facing pool_t structure as the size of the array and keep it updated.
   4. When deleting entries from the array, pull up the entries that follow and update the size. See the corresponding static function.
   5. When adding entries to the array, add at the bottom. If necessary, bubble up. See the corresponding static function.
   6. There is a separate static function for sorting the array.
   7. (bonus) There is a separate static function for invalidating the array.

6. Pool (manager) store (library static)

   This is an array of pointers to pool_mgr_t structures and so holds the metadata for multiple pools. See the corresponding static variables and functions.

   Behavior & management:

   1. The array is initialized with a certain capacity. If necessary, it should be resized with realloc(). See the corresponding static function and constants in the source file.
   2. Since this array contains pointers, they can be NULL. The size of the array, for which a static variable is used, should be incremented when a new pool is opened and never decremented. The pointer to a new pool should always be added to the end of the array. When a pool is closed, the pointer should be set to NULL.

7. Pool segment (user facing)

   This is a simple structure which represents a pool segment, either an allocation or a gap. Used for pool inspection by the user.

   Structure:

   typedef struct _pool_segment {
      size_t size;
      unsigned long allocated;
   } pool_segment_t, *pool_segment_pt;

   Behavior & management:

   1. An array of such structures is returned by the function mem_inspect_pool() for testing, printing, and debugging.
   2. Note: The returned array should be freed by the user.

The following functions are internal to the library and not exposed to the user. Their names are self-explanatory.

1. (bonus) static alloc_status _mem_resize_pool_store();

   If the pool store's size is within the fill factor of its capacity, expand it by the expand factor using realloc().

2. (bonus) static alloc_status _mem_resize_node_heap(pool_mgr_pt pool_mgr);

   If the node heap's size is within the fill factor of its capacity, expand it by copying over to a larger block of memory. Use malloc() and memcpy(), packing the nodes in the array in order. You will need to rebuild the gap index, as well.

3. (bonus) static alloc_status _mem_resize_gap_ix(pool_mgr_pt pool_mgr);

   If the gap index's size is within the fill factor of its capacity, expand it.

4. static alloc_status _mem_add_to_gap_ix(pool_mgr_pt pool_mgr, size_t size, node_pt node);

   Add a new entry to the gap index. The entry is gap size and node pointer to a node on the node heap of the given pool_mgr.

5. static alloc_status _mem_remove_from_gap_ix(pool_mgr_pt pool_mgr, size_t size, node_pt node);

   Remove an entry from the gap index. The entry is gap size and node pointer to a node on the node heap of the given pool_mgr.

6. static alloc_status _mem_sort_gap_ix(pool_mgr_pt pool_mgr);

   Sort the gap index in ascending order by size. Note: The index always has a length equal to the number of gaps currently in the corresponding pool.

7. static alloc_status _mem_invalidate_gap_ix(pool_mgr_pt pool_mgr);

   Useful during node heap expansion.

The following variables are internal to the library and not exposed to the user. Their names are self-explanatory. They are used to hold the pool store array of pointers to pool_mgr_t structures and are manipulated by the user-facing functions mem_init(), mem_pool_open(), mem_pool_close(), and mem_free(), and the library static function _mem_resize_pool_store().

static pool_mgr_pt *pool_store = NULL;
static unsigned pool_store_size = 0;
static unsigned pool_store_capacity = 0;

Below are 7 diagrams that show the state of the memory pool library data structures after certain library function calls.

Before mem_init()

After mem_init()

After mem_pool_open(1000000, FIRST_FIT)

After mem_new_alloc(0x7fab09804200, 100)

After mem_new_alloc(0x7fab09804200, 1000)

After mem_del_alloc(0x7fab09804200, 0x7fab09404e10)

After mem_new_alloc(0x7fab09804200, 80)

this section concerns future iterations of the project

1. Contents for easy navigation.
2. Refactoring to return mem not alloc to allow pool reallocation and stress testing of multiple large pools and pool growth.
3. Reference implementation of on-demand data structure expansion and bonus tests.
4. Drawings of the metadata and allocation scenarios, and embed in README.
5. cmocka 1.1.1 memory leak detection.
6. Doxygen for headers, which are part of assignment. Documentation. Example.
7. Review TODO-s in the code.
8. Static linking of the cmocka library. Latest release is cmocka 1.1.1. CMakeLists.txt should work on all platforms after platform-specific library installation.