Project
CS 350 Operating Systems, Fall 2021 Programming project 4 (PROJ4) Out: 11/21/2021, SUN Due date: 12/11/2021, SAT 23:59:59 In this project, you will implement a memory allocator library for managing heap memory. The goal of this project is to practice the concepts and techniques of free-space management which you learned during class. This project contributes 7% toward the final grading. 1 Baseline source code In this project, you will be working on the baseline code that needs to be cloned/downloaded from your own private GitHub repository. Please make sure you read this whole section, as well as the grading guidelines (Section 5), before going to the following link at the end of this section. • Go to the link at the end of this section to accept the assignment. • Once the import process finishes, you can clone or download the repository into your com- puter and start working By clicking the following link and accepting this programming assignment, you agree that you will not put the baseline code and this project specification on any public domains (e.g., public GitHub repository etc.). Assignment link: https://classroom.github.com/a/U9I6jdlq (Continue to next page ...) 1 https://classroom.github.com/a/U9I6jdlq 2 Implementing a heap memory allocator library The heap memory allocator library is used to allocate and manage a (large) chunk of heap memory that is pre-allocated from the system. Your job here is to implement the functionalities of free- space management you learned in class which include: • managing allocated memory blocks; • managing free blocks using free list; • supporting different memory allocation policies for the free-list-based free memory manage- ment, such as first-fit allocation and best-fit allocation; and • detecting invalid free requests (e.g., double free) and allocated block corruption. The following library functions are provided by this library. (1) int my mem allocator init(void): function to initialize the memory allocator. (2) void my mem allocator destroy(void): function to deconstruct the memory alloca- tor. (3) void set alloc policy(ALLOC POLICY policy): function to set the memory alloca- tion policy. (4) void *my malloc(size t size): function to allocate heap memory, which is similar to the malloc() function provided in a C library. (5) void my free(void *ptr): function to free an allocated block of memory, which is sim- ilar to the free() function provided in a C library. (6) void *my realloc(void *ptr, size t size): function to change an allocated block of memory, which is similar to the realloc() function provided in a C library. The above library functions are implemented in the following files of the base code. 2.1 File my mem allocator.c This file implements the first three library functions above and some helper functions which are used in the test code. The library functions implemented in this file are explained as follows. • my mem allocator init() initializes the memory allocator by pre-allocating a chunk of heap memory, which is the memory space this allocator manages, using the system malloc() function. The size of the pre-allocated memory is configured by the MY HEAP SIZE macro. Then it constructs the free list by inserting a giant free block which contains all the usable memory. The header structure of a free block is defined in my mem allocator.h: 2 // free/allocated block header typedef struct _block_header{ int size; // for free block: size of the usable space in the free block // for allocated block: size of the mem space returned to user void * next; // for free block: pointer to the next free block // for allocated block: magic number }BLOCK_HDR; Note that allocated blocks share the same header structure as free blocks. Re call that we have discussed how free blocks and allocated blocks are converted to each other as blocks are allocated/freed. • my mem allocator destroy() deconstructs the memory allocator by calling the system free() function on the pre-allocated heap memory space. • set alloc policy() sets the memory allocation policy: first fit or best fit. The above functions have been implemented. The helper functions for test code are also imple- mented in this file. You may read the implementations of the helper functions and how they are used in the test code to help you better test your implementation. Do not add your implementation to this file (i.e., my mem allocator.h ) and my mem allocator.h. When grading, these two files will be replaced with the original ones. 2.2 File my malloc.c Your implementtion of the my malloc() function goes here. If none of the free blocks in the free list is large enough to satisfy an allocation request, report such an error and return NULL to the caller. Otherwise return the address of the space allocated to the caller. When the allocator allocates space of a requested size from a free block, there are two scenarios which should be taken care of as follows: • If the remaining space in the free block is enough to accommodate a block header plus one byte, the free block should be split into an allocated block as requested and a new free block. Refer to the next subsection for the requirements of how a new free block should be added to the free list. • Otherwise, the whole free block can be used to satisfy the allocation request (i.e., splitting is not needed). When splitting is needed, the allocated space is taken from the front of the free block, which is the same as the example shown in class. Please refer to the course slides and the textbook chapter for the details. The allocator should support two different allocation policies for selecting a free block: first fit, which is the default, and best fit. Again, please refer to the course slides and the textbook chapter if you forget the details. 3 2.3 File my free.c Your implementtion of the my free() function goes here. When a allocate block is freed, it is turned to a free block and is added to the free list. The following to requirements should be satisified when adding a free block to the free list: • The free blocks in the free list should be sorted from low to high based on their addresses all the time. In other words, the free block should be inserted to the free list in an address- ascending manner. • After a free block is added to the free list, if it is adjacent to its neighboring block(s) in space, coalecging should be performed to turn the blocks to a larger one. Your implemenation of the my free() should be able to detect free anormalies, such as double free, invalid free address, and header corruption, by using the magic number. We have discussed this technique in details in class. 2.4 File my realloc.c Your implementtion of the my realloc() function goes here. void *my realloc(void *ptr, size t size) behaves similarly to the void *realloc(void *ptr, size t size), which changes the size of the memory block pointed to by ptr to size bytes and returns the address of the new block to the caller. Here you only need to take care of the following two scenarios: • If the new size is smaller than the originial size, return the orginial address of the allcoated space to the caller. If the difference between the original size and the new size is enough to hold a block header plus one byte, change the allocated block to the new size, turn the freed-up space to a new free block and add it to the free list. Otherwise, nonthing needs to be done on the allocated block for the realloc request. • If the new size is larger than the original size, allocate the requested space from a free block, which should be selected using the first fit policy, following the same way of my alloc(). Then copy the content of the old allcated space to the new one, free the old allocated space, and return the address of the new allocated space to the caller. (Continue to next page ...) 4 3 Testing your implementatioin The test code has been given in the base code. We will use the same test cases for grading except that we may change memory allocation request sizes in some of the test cases. The test cases are summarized as follows. You may read the code for the details of different test cases. • test1-4.c implements test cases 1 to 4, which test normal mallocs, normal frees without coalescing, and normal frees with coalescing. • test5-7.c implements test cases 5 to 7, which test the two allocation policies. • test8-10.c implements test cases 8 to 10, which test different anormaly situtations of malloc and free. • test11-14.c implements test cases 11 to 14, which test the my realloc() implemen- tation. A sample memory allocator library (“my mem lib sample.a”) implemented by the instructor is provided with this project specification in Brightspace. You can use the Makefile provided in the Brightspace to link the (provided or your own) test code with the sample library to see what the expected outputs are for different test cases. (Continue to next page ...) 5 4 Submit your work Once your code in your GitHub private repository is ready for grading, submit a text file named “DONE” to the assignment link in Brightspace. You can include the following info in this file: • The status of your implementation (especially, if not fully complete). • A description of how your code works, if that is not completely clear by reading the code (note that this should not be necessary, ideally your code should be self-documenting). • Possibly a log of test cases which work and which don’t work. • Any other material you believe is relevant to the grading of your project. Please note that you code in GitHub will not be graded until we see the “DONE” file in Brightspace. Suggestion: Test your code thoroughly on a CS machine before submitting. 6 5 Grading The following are the general grading guidelines for this and all future projects. (1) The code in your repository will not be graded until a “DONE” file is submitted to Brightspace. (2) The submission time of the “DONE” file shown on the Brightspace will be used to determine if your submission is on time or to calculate the number of late days. Late penalty is 10% of the points scored for each of the first two days late, and 20% for each of the days thereafter. (3) If the submitted patch cannot successfully patched to the baseline source code, or the patched code does not compile: 1 TA will try to fix the problem (for no more than 3 minutes); 2 if (problem solved) 3 1%-10% points off (based on how complex the fix is, TA’s discretion); 4 else 5 TA may contact the student by email or schedule a demo to fix the problem; 6 if (problem