讲解CSE 109、讲解C/C++编程设计、辅导Systems Programming、辅导C/C++ 调试Web开发|辅导Python编程

CSE 109: Systems Programming
Fall 2018
Program 4: Due on Sunday, October 21st at 9pm on CourseSite.
Checkpoint Due: Due on Monday, October 15th at 9pm via checkpointer.
Collaboration Reminder:
1. You must submit your own work.
2. In particular, you may not:
(a) Show your code to any of your classmates
(b) Look at or copy anyone else’s code
(c) Copy material found on the internet
(d) Work together on an assignment
Assignment: Preparation
1. Make a Prog4 directory in your class folder.
2. Create the files Allocator.c, Allocator.h, Allocation.c and Allocation.h
3. You can use whatever tester you want for this. We will provide a
prog4.o that you can link to your code for testing purposes.
4. We also will provide an object and header file that you must link to
your code to provide the Allocator::printAllocations(...) function (see
printAllocations.h and printAllocations.o).
5. All source code files must have the comment block as shown at the end
of this document. All files must be contained in your Prog4 directory.
Assignment:
You will be creating a basic memory allocator, non-optimized, that
can fulfill memory requests made by users.
11. Allocation.h and Allocation.c. Make sure you put the appropriate
material into each file.
(a) Each Allocation t object will contain a size t to represent the
starting offset of the allocation as well as the size of the allocation.
(b) void makeAllocation(struct Allocation t* it, size t start, size t
size): Constructs the allocation object with the given values.
Note that the Allocation t objects are not aware of the constraints
of the allocator and must not care either. We won’t return
anything - just modify that space you are pointed to. Nothing
should stop the user from making an invalid allocation, they
must use doesOverlap to ensure this does not happen.
(c) void freeAllocation(struct Allocation t* it): Destroys the contents
of the Allocation t object. User is responsible for assigning
to NULL afterwards, therefore, we return nothing and do not free
the actual Allocation t object.
(d) size t getStart(struct Allocation t* it): Returns the starting location
of the allocation.
(e) size t getEnd(struct Allocation t* it): Returns the ending location
of the allocation (not inclusive).
(f) size t getSize(struct Allocation t* it): Returns the size of the
allocation.
(g) int doesOverlap(struct Allocation t* it, size t start, size t size):
Returns 1 if theAllocation t object would overlap with the given
range. Returns 0 otherwise. Use this before creating a new Allocation
t object to validate that start and size do not conflict
with any existing Allocation t object.
2. Allocator.h and Allocator.c. Make sure you put the appropriate material
into each file.
(a) Define the Allocator t structure.
i. It must contain a void* called memory that points to the
chunk of memory that the Allocator t object is using.
ii. A size t to represent the capacity of the allocator.
This must be a multiple of 16.
This reflects alignment for long double on a 64-bit Intel
machine.
2iii. A dynamically resizable list of Allocation t objects as well as
size t fields to represent size and capacity of this list.
When expanding, expand by doubling capacity and then
adding 1.
iv. The amount of memory used by the Allocator t object to
track allocations must scale linearly with the number of active
allocations, not the amount of total memory.
(b) void makeAllocator(struct Allocator t* it, size t capacity): Constructs
an Allocator t object using the given capacity. Since the
capacity must be a multiple of 16, round up to the nearest multiple
of 16, if necessary. This will call malloc once, to create the
memory space specified by the capacity. The list of Allocation t
objects will initially be empty and there shall be no mallocs associated
with it at this point. Make sure that you only allocate
memory once at this point: this may be explicitly tested. You
will also keep track of the sum of the allocations made in a size t.
(c) void freeAllocator(struct Allocator t* it): Destroys the given Allocator
t object. User is responsible for freeing and assigning to
NULL afterwards, therefore, we return nothing. This must handle
freeing memory as well as any Allocation t objects we may
have and the list that contained them.
(d) void* allocate(struct Allocator t* it, size t amt): Requests an
allocation from the allocator. The allocator will determine a region
of space within memory that satisfies the request but has
not been allocated already. Note that amt must be rounded up
to the nearest multiple of 16. Track the allocation of this space
and then return a pointer to the region of space within memory
that satisfies this request. If no such space exists, return NULL.
The memory location you return must be that with the lowest
possible address within your allocation - if you always scan
from the beginning of memory to find where to allocate, you will
do this implicitly.
You are required to use Allocation t objects to track the usage
of memory within the allocator.
(e) void deallocate(struct Allocator t* it, void* ptr): Deallocates
the given allocation. If we are given NULL, ignore the request.
Otherwise, search through our list of allocations and remove the
matching allocation. If there is no matching allocation, print an
error to standard error (a bunch of garbage with numbers would
3be appropriate and funny but not necessary, ”Corruption in free”
is sufficient.) and call exit(1) to terminate the program. When
the user tries to deallocate something that we didn’t allocate for
them, we punish them severely.
(f) void* getBase(struct Allocator t* it): Returns a pointer to the
allocator’s memory. You won’t use this for anything in particular
but the tester expects it.
(g) size t getUsed(struct Allocator t* it): Returns the amount of
space used by the allocations in the allocator.
(h) size t getCapacity(struct Allocator t* it): Returns the capacity
of the allocator.
(i) void printAllocations(struct Allocator t* it, FILE* fd): This is
given to you, precompiled. This prints all of the allocations made
by the allocator in a ”nice” format to the FILE* specified by fd.
This requires the following two functions (getAllocation, numAllocations)
which would be private if that was allowable in C.
(j) struct Allocation t* getAllocation(struct Allocator t* it, size t
index): Returns the allocation specified by index. Returns a
NULL if out of bounds.
(k) size t numAllocations(struct Allocator t* it): Returns the number
of allocations that are currently tracked by the allocator.
(l) void* riskyAlloc(struct Allocator t*, size t size): Same as allocate
except in the case that we don’t have enough memory available,
use realloc to get more memory. This is completely unsafe in some
cases. If the reallocation was safe, you now have a larger capacity
and need to adjust accordingly. If the reallocation was not safe,
meaning that the pointers that had been given to the user in the
past are now all invalid, print ”Bad realloc” to standard error
and then return NULL.
Checkpointing:
1. The Allocation object, in its entirety (Allocation.h and Allocation.c)
are due for the checkpoint.
2. You may call other functions, etc, as long as everything is included in
your checkpoint submission.
3. To submit your checkpoint:
4cp Allocation.h checkpoint4.c
cat Allocation.c >> checkpoint4.c
~jloew/CSE109/submitCheckpoint.pl 4
That is lowercase PL, followed by the number 4.
4. You may submit your Checkpoint up to ten times total, this includes
after the checkpoint is due as well.
5. Ideally, it will tell you which functions are incorrect. It is possible
that the functions are incorrect but pass the checkpoint. Although,
they should be mostly correct or completely correct if they pass the
checkpoint.
6. The checkpoint will not check for memory corruption or leaks. You
will need to handle that yourself.
Style:
For assignments, we follow the Allman style of braces and indentation.
1. Review the Style document on Coursesite
Testing:
1. You will need to use multiple steps to compile your code since you will
have more than one .c source file.
You can provide a Makefile if you want, it will not be used during
our testing.
module load gcc-7.1.0
gcc -Werror -Wall -g -c Allocation.c
gcc -Werror -Wall -g -c Allocator.c
gcc -Werror -Wall -g -o prog4 Allocation.o Allocator.o prog4.o
2. Your final executable will be called prog4.
3. Make sure to test cases where you run out of memory - note that when
you run out of memory, you may memory leak in that case without
penalty.
54. For your own testing you will need to link printAllocations:
module load gcc-7.1.0
gcc -Werror -Wall -g -c Allocation.c
gcc -Werror -Wall -g -c Allocator.c
gcc -Werror -Wall -g -c prog4.c
gcc -Werror -Wall -g -o prog4 Allocation.o Allocator.o printAllocations.o
prog4.o
Submission:
1. Your code must have the functionality as specified by the assignment
and you absolutely must not break encapsulation unless it is otherwise
not possible to do so. This is because we can replace your Allocator
and/or Allocation code with our own and everything should still work.
2. Once ready to submit, you can package up the assignment as a .tgz
file
tar -czvf Prog4.tgz Prog4
You must use this command in the directory that contains the
Prog4 folder, not within the directory.
3. Transfer Prog4.tgz to the Program 4 submission area of CourseSite.
Comment Block:
/*
CSE 109: Fall 2018

Program #4
*/