CS2850 Assessed Coursework 2
This assignment must be submitted by Friday, 5 January 2023, at 10 am. Feedback will be provided on the date provided in the coursework grid.
Learning outcomes assessed
In this assignment, you will implement a toy model of a dynamic memory allocator. To complete all the tasks you need to
• declare, define, and update variables and functions in C,
• use pointer arithmetic,
• know how a memory allocator works,
• read from stdin and write to stdout using getchar and printf, and • allocate and free memory using malloc.
Instructions
Submit this assignment using the Moodle submission link 202324 CS2850 CW2: C mini-project by Fri- day, 5 January 2023, at 10 am. The submission system allows you to submit a single archive file, which should contain all your programs. Create a compressed directory, e.g. 202324cs2850.zip, containing the four C files described in the following sections , step1.c, step2.c, step3.c, and step4.c. We suggest you write a separate file, functions.c, with all auxiliary functions. To include it in a task-specific program, e.g. step1.c, by write
#include "functions.c" 1
on top of the file. Your files will be recompiled and run in the submission directory with the compiler available on the teaching server. Be sure your name or ID does not appear anywhere in your submission.
Academic misconduct
Coursework submissions are routinely checked for academic misconduct (working together, copying from sources, etc.). Penalties can range from a 10% deduction of the assignment mark, zero for the assignment or the case being referred to a Senior Vice-Principal to make a decision (for repeat offences). Further details can be found here.
Introduction
In this assignment, you write a program that simulates a dynamic memory allocator. The process address space is represented by an array of characters, memory. Given a size in bytes, len, the allocator scans the array to find a free memory block of size len and returns the index of the start of the block. For simplicity, the program maintains an integer array of the same size as memory to store the sizes of the allocated blocks. The address space is represented by
1
struct space {
};
char *memory; int *sizes; int len;
where memory and sizes are pointers to the first entry of the character and integer arrays and len is their length. In the dynamic version of the program, the program stores an arbitrary number of arbitrary sentences entered by a user on standard input. The size of the memory space grows when needed. At the beginning, the allocator stores all blocks one after the other. When some blocks are freed, allocating new blocks at the end becomes inefficient. The allocator should search the space for the first block compatible with the required size. Your implementation should follow the steps described in the next sections. Save a new C file, step#.c, for each section. Each program should compile without errors and produce the expected output. After completing a section, test your implementation with Valgrind. Even if there are no memory leaks, Valgrind may outline hidden execution errors. Try to understand and fix all of them.
Example. If the initial size of the memory array is 10 and you use an input file, input.txt, containing the following lines
a run of the final program should print
0000000000 1 2 0000000000000000000000000000000000000000000000 3 Brian Kernighan++ 4 17///////////////00000000000000000000000000000 5 Brian Kernighan++CS2850++ 6 17///////////////8///////000000000000000000000 7 Brian Kernighan++ D e n n i s Ritchie++ 8 17///////////////0000000016//////////////00000 9
Brian Kernighan++and++ D e n n i s Ritchie++ 10 17///////////////5////00016//////////////00000 11 12 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 13 Brian Kernighan++and++ Dennis Ritchie++The C Programming Language++ 14 17///////////////5////00016//////////////28//////////////////////////0000000000000000000000000 15 16 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 17
on standard output. Note that the program automatically frees the sentence CS2500. The memory grows when the user enters the sentences Brian Kerninghan and C Programming Language. The allocator saves the sentence and in the first suitable available space. To print memory and sizes, you can use printMemory and printSizes provided in the Appendix of this document or in Supporting code for 202324 CS2850 CW2.
Step 1: Initialization (25 marks)
Create a file with all auxiliary functions called functions.c. On top of it, write the statements for including unistd.h and stdlib.h. Below those, define the following macros,
1 2 3 4
1 2 3 4 5
Brian Kernighan
CS2850
Dennis Ritchie
and
The C Programming Language
1 2 3 4 5
#define BUSY ’+’ #define FREE ’ ’ #define BUSYSIZE --1
#define FREESIZE 0
2
and the structure defined above. You will use BUSY and FREE to mark the allocated and free entries of memory and BUSYSIZE and FREESIZE to mark the allocated (non-starting) and free entries of sizes. The first entry of an allocated block block is marked with the length of the block in sizes. To complete this section’s task you need to implement 2 functions,
1. initializeMemory, which accepts an integer memSize and a pointer to the memory struct, mem,asinputs,allocatestwoblocksofsizememSize * sizeof(char)andmemSize * sizeof(char) using malloc, makes memory and sizes point to these blocks, sets len to memSize, initializes
the arrays by marking all entries with FREE and FREESIZE, and print memory and sizes by calling printMemory and printSizes.
2. cleanMemory, which accepts a pointer to the memory struct, mem, as an input, replace all entries of memory and sizes with FREE and FREESIZE, print memory and sizes by calling printMemory and printSizes, and free the allocated memory by calling free.
Test your implementation by compiling and running q1.c in Supporting code for 202324 CS2850 CW2. The output should be
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
Before proceeding, make sure Valgrind does not detect execution errors or memory leaks.
Step 2: Stack Allocator (25 marks)
In this section, the task is to implement a stack-like allocator and de-allocator. This is different from the heap-like allocator you will implement in the next section because a new memory block is always allocated at the end of the previous one. The de-allocator takes the index of the first entry of the block to be deallocated and removes its content by setting the block entries back to FREE (in memory) and FREE (in FREESIZE). To complete this section’s task, you need to implement two functions,
1. int stackAllocator, which accepts an integer nbytes and a pointer to the memory struct, mem, as inputs, searches for the first entry of sizes marked with FREESIZE, check whether there are nbytes available entries after it, writes nbytes on that entry of sizes, writes BUSYSIZE on the nbytes − 1 following entries of sizes, finds the corresponding nbytes entries in memory and mark them with BUSY, and returns the index of the first entry of the newly allocated block, and
2. void deallocator, which accepts an integers, p, and a pointer to the memory struct, mem, as inputs, find the location corresponding to p in sizes, read the block length, nbytes, from that entry, and sets the nbytes entries of memory starting at p to FREE and the corresponding nbytes entries of sizes to FREESIZE.
If the first entry marked with FREESIZE in sizes is too close to the end of the array, i.e. if there are not nbytes entries of sizes marked with FREESIZE after it, stackAllocator should return mem->len. This allows you to check from the program if the memory has been successfully allocated before writing on it. The deallocator should not return anything. Test your implementation by
3
1 2 3 4 5 6
compiling and running q2.c in Supporting code for 202324 CS2850 CW2. All string facilities are given in the appendix or in Supporting code for 202324 CS2850 CW2. The output of the program should be
1 2 3 4 5 6 7 8 9 10
00000000000000000000000000000000000000000000000000
Brian Kernighan+++++
20//////////////////000000000000000000000000000000 Brian Kernighan+++++CS2850+++++ 20//////////////////11/////////0000000000000000000 Brian Kernighan+++++ 20//////////////////000000000000000000000000000000
00000000000000000000000000000000000000000000000000
The third sentence, Dennis Ritchie, is not allocated because there is not enough available space. Check that the program behaves correctly even in such situations by running the binary with Valgrind.
Step 3: Heap Allocator (25 marks)
In this section, you rewrite the allocator to make it a heap-like allocator, i.e. to let the program allocate memory in the free space left by previous frees. To complete this section’s task, you need to implement two functions,
1. int spaceScanner, which takes an integer, nbytes, and a pointer to the memory structure, mem, as inputs, finds the first entry of sizes that is marked with FREESIZE and has nbytes entries also marked with FREESIZE after it, and returns the index of the corresponding entry of memory if the search is successful and mem->len otherwise, and
2. int heapAllocatorQ3, which has the same inputs as stackAllocation, calls spaceScanner to obtain the start index, p, of a suitable block, sets the nbytes entries of memory after p to FREE and the corresponding nbytes entries of sizes to FREESIZE, and returns p.
Test your implementation by compiling and running q3.c in Supporting code for 202324 CS2850 CW2with memSize set to 50. The output should be
00000000000000000000000000000000000000000000000000 Brian Kernighan++ 17///////////////000000000000000000000000000000000 Brian Kernighan++CS2850++
17///////////////8///////0000000000000000000000000 Brian Kernighan++ D e n n i s Ritchie++ 17///////////////0000000016//////////////000000000 Brian Kernighan++ D e n n i s Ritchie++ 17///////////////0000000016//////////////000000000 Brian Kernighan++and++ D e n n i s Ritchie++
17///////////////5////00016//////////////000000000 00000000000000000000000000000000000000000000000000
The sentence and is now allocated in the free space once occupied by the sentence CS2850. The sentence The C Programming Language is not allocated because the memory is not big enough. You will fix this problem in the next section.
4
1 2 3 4 5 6 7 8 9 10 11 12 13
Step 4: User interactions (25 marks)
Before making the program interactive, you need a function that increases the size of the memory if needed. In a real process, this means requiring the intervention of the Operating System (OS) through a system call. In this toy model, you use mallloc to simulate the OS intervention by reallocating memory and size. You also have to parse the input sentences and save them into strings. As you do not want to restrict the length of a user sentence, you need to buffer it into a dynamically allocated string that grows as new characters arrive. To complete this section’s task, you need two implement two functions
1. void increaseMemory which takes an integer, nbytes, and a pointer to the memory struc- ture, mem, as inputs, computes the length of the new memory, newLen, using
1 2 3
int newLen = mem-->len;
while (newLen -- mem-->len < nbytes)
newLen = 2 * (newLen + 1);
saves the content of memory, sizes, and len into three temporary variables, allocates a new memory space by calling initializeMemory(newLen, mem), copies the content of the temporary variable into the newly initialized memory, and free the old memory using free, and
2. int readString, which takes a pointer to a string, i.e. a pointer to a pointer to a character, s, as an input, calls malloc(1) to allocate a starting string, stores it in *s, gets characters from the terminal by calling getchar until you reach a new line character or EOF, reallocates the string to accommodate each new character through
len++;
*s = malloc(len + 1); char *temp = *s; copyString(temp, s, len); free(temp);
where len is the length of the string before attaching the new character, stores the new character in the len-th entry of *s, null terminates the final string, and returns 1 if the last character is a new line character and 0 if the last character is EOF.
To copy the temporary integer array into the newly allocated size array, sizes, write a function, copyArray(int *old, int *new, int len), by adapting copyString given in the appendix. You also need to modify heapAllocatorQ3. Instead of returning mem->len if spaceScanner does not find a suitable free block, the function should call increaseMemory until such a block becomes available. For example, you can replace the early-return statement of the old implementation with
1 2 3 4 5
int t0;
while ((t0 = spaceScanner(nbytes, mem))== mem-->len) increaseMemory(nbytes, mem
);
Test your implementation by running the following program. Test your implementation by com- piling and running q4.c in Supporting code for 202324 CS2850 CW2. The deallocator removes the second sentence of each group of three sentences after the user enters the third one. A sample output of this program is given in the section called Introduction.
Marking criteria
5
1 2
Full marks will be awarded for correct answers to the above questions. Submissions are assessed on functionality and coding style. Try to write readable, well-formatted and well-commented code. More importantly, all your programs must be compiled using gcc -Wall -Werror -Wpedantic and run without errors on linux.cim.rhul.ac.uk. To spot possible execution issues, run the programs with Valgrind and check that the end of the output is
... == ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 1
Before submitting, test your code with the assignment Moodle Code Checker. Passing all tests, however, will not guarantee you get full marks. Please use the CS2850 Piazza Forum to post any specific questions.
Extensions
This assignment is subject to College policy on extensions. If you believe you require an extension please read the documentation carefully and guidelines here
Extenuating circumstances
If you submit an assessment and believe that the standard of your work was substantially affected by your current circumstance then you can apply for Extenuating Circumstances. Details on how to apply for this can be found here. Read the accompanying documentation on the above link carefully. Please note decisions on Extenuating Circumstances are made at the end of the academic year.
Late Submission
In the absence of acceptable extenuating cause, late submission of work will be penalised as follows: 1. for work submitted up to 24 hours late, the mark will be reduced by ten percentage marks; 2. for work submitted more than 24 hours late, the maximum mark will be zero.
A Auxiliary functions
Here you can find a possible implementation of the string-handling and printing facilities you need for this assignment. The code is also available in Supporting code for 202324 CS2850 CW2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
void copyString(char *sIn, char *sOut, int len) { int t = 0;
while (t < len) {
*(sOut + t) = *(sIn + t);
} }
int stringLen(char *s) { int t = 0;
t++;
}
while (*(s + t) != ’\0’) t++; return t;
void printMemory(struct space *mem) { int i = 0;
6
while (i < mem-->len) {
}
printf("%c", *(mem-->memory + i)); i++;
} printf("\n");
void printSizes(struct space *mem) { int i = 0;
int c;
while (i < mem-->len) {
int n = *(mem-->sizes + i);
int t = 10000; while (n > 9) {
c = n/t;
n = n -- c * t; t = t / 10;
if (c) {
} }
c= n%10+’0’;
c= c%10+’0’; printf("%c", c); i++;
}
printf("%c", c);
i++;
} printf("\n");
The plain text version of all codes in this document is available on the assignment Moodle page 202324 CS2850 CW2: C mini-project.
B Pseudocode
Here you can find the pseudocode of the functions you need to implement in this assignment.
1: function void initializeMemory(int len, struct space *mem)
2: let mem->memory point to a dynamically allocated array of length len* sizeof(char)
3: let mem->sizes point to a dynamically allocated array of length len * sizeof(int)
4: set mem->len to len
5: i←0
6: while i is smaller than mem->len do
7: set the i-th entry of mem->memory to FREE
8: set the i-th entry of mem->sizes to FREESIZE
9: i←i+1
10: print mem->memory using printMemory
11: print mem->sizes using printSizes
1: function void cleanMemory(struct space *mem) 7
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
2: 3: 4: 5: 6: 7: 8: 9:
10:
1: 2: 3:
4: 5:
6: 7: 8: 9:
10: 11: 12: 13:
1: 2: 3: 4: 5: 6: 7: 8: 9:
1: 2: 3: 4: 5: 6:
7:
i←0
while i is smaller than mem->len do
set the i-th entry of mem->memory to FREE
set the i-th entry of mem->sizes to FREESIZE i←i+1
print mem->memory using printMemory print mem->sizes using printSizes free mem->memory
free mem->sizes
function int stackAllocator(int nbytes, struct space *mem) t0 ← 0
while t0 + nbytes is smaller than mem->len and the t0-th entry of mem->sizes is not FREESIZE do
t0 ← t0 + 1
if t0+ nbytes equals mem->len then
return mem->len t←0
while t is smaller than nbytes and t0 + t is smaller than mem->len do set the (t0 + t)-th entry of mem->memory to BUSY
set the (t0 + t)-th entry of mem->sizes to BUSYSIZE
t←t+1
set the t0-th entry of mem->sizes to nbytes return t0
function void deallocator(t0, struct space *mem) if t0 equals mem->len or is negative then
return
let nbytes be the value stored in the t0-th location of mem->sizes t←0
while t is smaller than nbytes do
set the (t0 + t)-th entry of mem->memory to FREE
set the (t0 + t)-th entry of mem->sizes to FREESIZE t←t+1
function int spaceScanner(int nbytes, struct space *mem) t0 ← 0
do
s←0
while s = 0 and t0 is smaller than mem->len do
t←0
while t0 +t is smaller than mem->len and the (t0 +t)-th entry of mem->sizes is FREESIZE
t←t+1
8
8:
9: 10: 11: 12:
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11:
1: 2: 3: 4:
5: 6: 7: 8: 9:
10: 11: 12: 13:
1: 2: 3: 4: 5:
6: 7: 8: 9:
10:
if t is larger than nbytes then s←1
else
t0 ← t0 + 1 return t0
function int heapAllocatorQ3(int nbytes, struct space *mem) (for Q3) t0 ← spaceScanner(nbytes, mem)
if t0 = mem->len then
return t0 t←0
while t is smaller than nbytes do
set the (t0 + t)-th entry of mem->memory to BUSY
set the (t0 + t)-th entry of mem->sizes to BUSYSIZE t←t+1
set the t0-th entry of mem->sizes to nbytes return t0
function void increaseMemory(int nbytes, struct space *mem)
t ← mem->len
while the difference between t and mem->len is smaller than nbytes do
t ← 2(t + 1)
let s be a pointer to char s ←mem->memory
let a be a pointer to int a ←mem->sizes
l ←mem->len
call initializeMemory with arguments t and mem
copy the content of the character array pointed by s into mem->memory using copyString copy the content of the integer array pointed by a into mem->sizes using copyArray freesanda
function int heapAllocator(int nbytes, struct space *mem) (for Q4) t0 ←spaceScanner(nbytes, mem)
while t0 equals mem->len do
increaseMemory(nbytes, mem)
t0 ← spaceScanner(nbytes, mem)
t←0
while t is smaller than nbytes do
set the (t0 + t)-th entry of mem->memory to BUSY
set the (t0 + t)-th entry of mem->sizes to BUSYSIZE t←t+1
9
11: set the t0-th entry of mem->sizes to nbytes
12: return t0
1: function int readString(char **s)
2: t←0
3: c ← getchar()
4: allocate 1 byte in the heap using malloc
5: let *s point to the newly allocated memory
6: let **s be the null character
7: while c is not a new line character or EOF do
8: p ←*s
9: t←t+1
10: allocate a character array of t + 1 bytes in the heap using malloc
11: let *s point to the newly allocated memory
12: copy the content of the character array pointed by p into ∗s
13: free p
14: set the t-th entry of the newly allocated character array to c
15: set the (t + 1)-th entry of the newly allocated character array to the null character
16: c ← getchar()
17: ifcisEOFthen
18: return 0
19: return 1
10