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 Friday, 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
1 #include "functions.c"
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
1 struct space {
2 char *memory;
3 int *sizes;
4 int len;
5 };
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
1 Brian Kernighan
2 CS2850
3 Dennis Ritchie
4 and
5 The C Programming Language
a run of the final program should print
1 0000000000
2
3 0000000000000000000000000000000000000000000000
4 Brian Kernighan++
5 17///////////////00000000000000000000000000000
6 Brian Kernighan++CS2850++
7 17///////////////8///////000000000000000000000
8 Brian Kernighan++ D e n n i s Ritchie++
9 17///////////////0000000016//////////////00000
10 Brian Kernighan++and++ Dennis Ritchie++
11 17///////////////5////00016//////////////00000
12
13 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
14 Brian Kernighan++and++ Dennis Ritchie++The C Programming Language++
15 17///////////////5////00016//////////////28//////////////////////////0000000000000000000000000
16
17 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
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 #define BUSY ’+’
2 #define FREE ’ ’
3 #define BUSYSIZE --1
4 #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, as inputs, allocates two blocks of size memSize * sizeof(char) and memSize * 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
1
2 00000000000000000000000000000000000000000000000000
3
4 00000000000000000000000000000000000000000000000000
5
6 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
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 00000000000000000000000000000000000000000000000000
3 Brian Kernighan+++++
4 20//////////////////000000000000000000000000000000
5 Brian Kernighan+++++CS2850+++++
6 20//////////////////11/////////0000000000000000000
7 Brian Kernighan+++++
8 20//////////////////000000000000000000000000000000
9
10 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
1 00000000000000000000000000000000000000000000000000
2 Brian Kernighan++
3 17///////////////000000000000000000000000000000000
4 Brian Kernighan++CS2850++
5 17///////////////8///////0000000000000000000000000
6 Brian Kernighan++ D e n n i s Ritchie++
7 17///////////////0000000016//////////////000000000
8 Brian Kernighan++ D e n n i s Ritchie++
9 17///////////////0000000016//////////////000000000
10 Brian Kernighan++and++ Dennis Ritchie++
11 17///////////////5////00016//////////////000000000
12
13 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
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 structure, mem, as inputs, computes the length of the new memory, newLen, using
1 int newLen = mem-->len;
2 while (newLen -- mem-->len < nbytes)
3 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
1 len++;
2 *s = malloc(len + 1);
3 char *temp = *s;
4 copyString(temp, s, len);
5 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 int t0;
2 while ((t0 = spaceScanner(nbytes, mem))== mem-->len) increaseMemory(nbytes, mem
);
Test your implementation by running the following program. Test your implementation by compiling 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
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
1 ... == ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
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 void copyString(char *sIn, char *sOut, int len) {
2 int t = 0;
3 while (t < len) {
4 *(sOut + t) = *(sIn + t);
5 t++;
6 }
7 }
8
9 int stringLen(char *s) {
10 int t = 0;
11 while (*(s + t) != ’\0’) t++;
12 return t;
13 }
14
15 void printMemory(struct space *mem) {
16 int i = 0;
6
17 while (i < mem-->len) {
18 printf("%c", *(mem-->memory + i));
19 i++;
20 }
21 printf("\n");
22 }
23
24 void printSizes(struct space *mem) {
25 int i = 0;
26 int c;
27 while (i < mem-->len) {
28 int n = *(mem-->sizes + i);
29 int t = 10000;
30 while (n > 9) {
31 c = n/t;
32 n = n -- c * t;
33 t = t / 10;
34 if (c) {
35 c = c % 10 + ’0’;
36 printf("%c", c);
37 i++;
38 }
39 }
40 c = n % 10 + ’0’;
41 printf("%c", c);
42 i++;
43 }
44 printf("\n");
45 }
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
2: i ← 0
3: while i is smaller than mem->len do
4: set the i-th entry of mem->memory to FREE
5: set the i-th entry of mem->sizes to FREESIZE
6: i ← i + 1
7: print mem->memory using printMemory
8: print mem->sizes using printSizes
9: free mem->memory
10: free mem->sizes
1: function int stackAllocator(int nbytes, struct space *mem)
2: t0 ← 0
3: while t0 + nbytes is smaller than mem->len and the t0-th entry of mem->sizes is not
FREESIZE do
4: t0 ← t0 + 1
5: if t0+ nbytes equals mem->len then
6: return mem->len
7: t ← 0
8: while t is smaller than nbytes and t0 + t is smaller than mem->len do
9: set the (t0 + t)-th entry of mem->memory to BUSY
10: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE
11: t ← t + 1
12: set the t0-th entry of mem->sizes to nbytes
13: return t0
1: function void deallocator(t0, struct space *mem)
2: if t0 equals mem->len or is negative then
3: return
4: let nbytes be the value stored in the t0-th location of mem->sizes
5: t ← 0
6: while t is smaller than nbytes do
7: set the (t0 + t)-th entry of mem->memory to FREE
8: set the (t0 + t)-th entry of mem->sizes to FREESIZE
9: t ← t + 1
1: function int spaceScanner(int nbytes, struct space *mem)
2: t0 ← 0
3: s ← 0
4: while s = 0 and t0 is smaller than mem->len do
5: t ← 0
6: while t0+t is smaller than mem->len and the (t0+t)-th entry of mem->sizes is FREESIZE
do
7: t ← t + 1
8
8: if t is larger than nbytes then
9: s ← 1
10: else
11: t0 ← t0 + 1
12: return t0
1: function int heapAllocatorQ3(int nbytes, struct space *mem) (for Q3)
2: t0 ← spaceScanner(nbytes, mem)
3: if t0 = mem->len then
4: return t0
5: t ← 0
6: while t is smaller than nbytes do
7: set the (t0 + t)-th entry of mem->memory to BUSY
8: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE
9: t ← t + 1
10: set the t0-th entry of mem->sizes to nbytes
11: return t0
1: function void increaseMemory(int nbytes, struct space *mem)
2: t ← mem->len
3: while the difference between t and mem->len is smaller than nbytes do
4: t ← 2(t + 1)
5: let s be a pointer to char
6: s ←mem->memory
7: let a be a pointer to int
8: a ←mem->sizes
9: ℓ ←mem->len
10: call initializeMemory with arguments t and mem
11: copy the content of the character array pointed by s into mem->memory using copyString
12: copy the content of the integer array pointed by a into mem->sizes using copyArray
13: free s and a
1: function int heapAllocator(int nbytes, struct space *mem) (for Q4)
2: t0 ←spaceScanner(nbytes, mem)
3: while t0 equals mem->len do
4: increaseMemory(nbytes, mem)
5: t0 ← spaceScanner(nbytes, mem)
6: t ← 0
7: while t is smaller than nbytes do
8: set the (t0 + t)-th entry of mem->memory to BUSY
9: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE
10: 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: if c is EOF then
18: return 0
19: return 1
10