For this assignment, you will implement your own versions of the standard library functions malloc() and
free()
. Unlike the standard implementations, your versions will detect common usage errors and report them.
For this assignment, you will create
1.
A library
mymalloc.c
with header
mymalloc.h
, containing the functions and macros described below.
2. A program
memgrind.c
that includes
mymalloc.h
.
3.
Additional test programs that include
mymalloc.h
, along with the necessary Make-files for compiling these programs.
4.
A README file containing the name and netID of both partners, your test plan, descriptions of your test programs (including any arguments they may take), and any design notes you think are worth pointing out. This should be a plain text file.
Submit all files to Canvas in a single Tar archive. Place all files in a directory called “P1”.
We should be able to run the following commands as written (aside from the name of the archive):
$ tar -xf p1.tar
$ cd P1
$ make
$ ./memgrind
1 Background
The
heap
is a region of memory managed by the run-time system through two functions,
malloc() and free()
, which allocate and deallocate portions of the heap for use by client code.
We will model the heap as a sequence of variably sized
chunks
, where a chunk is a contiguous sequence of bytes in the heap and all bytes in the heap belong to exactly one chunk. Each chunk has a size, which is the number of bytes it contains, and may be either allocated (in-use) or deallocated (free).
The number and sizes of the chunks is expected to vary over the run-time of a program. Large chunks can be divided into smaller chunks, and small chunks can coalesce into larger chunks.
We can further model a chunk as having two parts. The
header
contains information the run-time system needs to know about a chunk, such as its size and whether it is allocated. The payload contains the actual object that will be used by client code. We say that the payload contains data, and the header contains metadata.
Note that an object is itself a contiguous sequence of bytes, meaning that the run-time system cannot intermix data and metadata.
To ensure smooth operation, the run-time system and the client code must operate by certain rules:
1.
On success,
malloc()
returns a pointer to the payload of an allocated chunk containing at least the requested number of bytes. The payload does not overlap any other allocated chunks.
2.
The run-time system makes no assumptions about the data written to the payload of a chunk.
In particular, it cannot assume that certain special values are not written to the payload. In other words, the run-time cannot extract any information by looking at the payload of an allocated chunk. Conversely, clients may write to any byte received from malloc()
without causing problems for the run-time system.
3.
The run-time system never writes to the payload of an allocated chunk. Client code may assume that data it writes to an object will remain, unchanged, until the object is explicitly freed.
4. The run-time system never moves or resizes an allocated chunk.
1
5.
The client never reads or writes outside the boundaries of the allocated payloads it receives.
The run-time system can assume that any data it writes to chunk headers or to the payloads of unallocated chunks will be not be read or updated by client code.
malloc()
is called with a single integer, indicating the requested number of bytes. It searches for a free chunk of memory containing at least that many bytes. If it finds a chunk that is large enough, it may divide the chunk into two chunks, the first large enough for the request, and returns a pointer to the first chunk. The second chunk remains free.
free()
is called with a single pointer, which must be a pointer to a chunk created by
malloc()
. free() will mark the chunk free, making it available for subsequent calls to
malloc()
.
1.1 Coalescing free chunks
Consider a case where we repeatedly call
malloc()
and request, say, 24-byte chunks until all of memory has been used. We then free all these chunks and request a 48-byte chunk. To fulfil this request, we must coalesce
two adjacent 24-byte chunks into a single chunk that will have at least 48 bytes.
Coalescing can be done by
malloc()
, when it is unable to find space, but it is usually less error-prone to have free() automatically coalesce adjacent free chunks.
1.2 Alignment
C requires that pointers to data are properly
aligned
: pointers to 2-byte data must be divisible by 2, pointers to 4-byte data must be divisible by 4, and so forth. We will assume that the largest data type our programs will use has 8-byte alignment. To ensure that any object allocated by malloc()
has 8-byte alignment, we will ensure that all offsets from the start of our heap are multiples of 8.
This means that allocations must also be multiples of 8: specifically, the smallest multiple of 8 greater than equal to the requested amount. Thus, a call to malloc()
requesting 20 bytes must actually allocate 24 bytes.2
Note that each chunk must have a length that is a multiple of 8, and its header and payload must also have lengths that are multiples of 8. This means that the smallest possible chunk is 16 bytes.
到了这里,关于CS214 C语言 computer的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!