1. Homepage
  2. Programming
  3. [2021] COMP2017/COMP9017 System Programming - Assignment 3 - friendship ended with malloc

[2021] COMP2017/COMP9017 System Programming - Assignment 3 - friendship ended with malloc

Engage in a Conversation
COMP2017System ProgrammingCUniversity of Sydney

Assignment 3 - friendship ended with malloc

CourseNana.COM

Task description CourseNana.COM

In this assignment you will be implementing a simple dynamic memory allocator with a similar interface to the standard library functions (such as malloc) that you are familiar with. CourseNana.COM

You will be implementing your allocator as a library of functions that can be called by other programs, rather than as a standalone executable. CourseNana.COM

Introduction CourseNana.COM

The standard library and other real world allocator implementations obtain raw areas of memory from the kernel using the mmap and brk syscalls. Under a simplified memory model, these raw areas of memory are described as “the heap”. The allocator implements internal data structures that keep track of which parts of these raw blocks of memory are allocated or not. As you will be familiar, programs use library functions such as malloc and free to request dynamic memory from and return dynamic memory to the allocator. It is the allocator’s responsibility to use its internal data structures to mark memory that is allocated so that it does not overlap with any other allocations made, and to allow memory that is freed to be allocated to future dynamic memory requests. Furthermore, it is the allocator’s responsibility to appropriately call syscalls to obtain further memory from the operating system if required for an allocation, or to return memory to the operating system if it is no longer required. CourseNana.COM

In this assignment, your allocator will manage a virtualised heap using a function we provide that simulates using brk to manipulate a real process heap. When dynamic memory is requested from your allocator, it will allocate it from this virtual “heap”. CourseNana.COM

Memory allocation process CourseNana.COM

Your virtual heap is simply a contiguous region of memory that you have read and write access to. Details on how you manage it are below in “Managing your Virtual Heap Memory”. CourseNana.COM

You will implement a simple buddy allocation algorithm to manage your virtual heap. Buddy allocation fulfils all allocations from a starting block of memory that is 2n bytes in size, where n is a non-negative integer. During the allocation process, the starting memory is repeatedly halved, creating blocks of size 2i bytes where i is a non-negative integer and i < n. i also has a minimum value that we will refer to as MIN. CourseNana.COM

Allocation Algorithm CourseNana.COM

When a request for an allocation of k bytes of memory is made, follow this algorithm: CourseNana.COM


1. If there exists an unallocated block of size 2 bytes such that 2 < k ≤ 2 , allocate and return the leftmost such CourseNana.COM

unallocated block. Exception: if there exists an unallocated block of size 2 , allocate and return the CourseNana.COM

leftmost such block (because there are no smaller blocks to allocate)
2. If there exist no such unallocated blocks, create an unallocated block of size 2 bytes (if k ≤ 2
CourseNana.COM

below steps CourseNana.COM

3. Split the leftmost unallocated block of size 2j+1 bytes in half. Allocate and return the left half for this request. The right half becomes a free unallocated block of size 2 . Blocks which are split are not allocatable. The 2 child blocks which result from a split are called buddies of each other. CourseNana.COM

4. If no unallocated block of size 2 on as required, up to splitting the original block of 2n bytes. exists, repeat the last step with the leftmost unallocated block of size 2 , and so CourseNana.COM

5. If no block of suitable size can be found, return an appropriate error as described below in the functions you have to implement CourseNana.COM

Note the following: CourseNana.COM

  • The entire unallocated block is allocated for the request. In buddy allocation, there is often some wasted space because requested memory is less than the appropriate power-of-2 block size.
  • “Left” refers to smaller memory addresses Any area of memory can only be allocated once. If allocation succeeds, callers will expect to have exclusive access, at the pointer you return, to the number of bytes of memory they requested.
  • Sizelimitsaredefinedbythetypeswehavespecifiedforthefunctionsyouimplement.

Deallocation algorithm
When a previously allocated block of memory of size 2
j bytes is requested to be freed, follow this algorithm: CourseNana.COM

1.     If the buddy block of the freed block is also unallocated, merge the two buddies to form an unallocated block of size CourseNana.COM

2.     Repeat the previous step if the buddy block of this new 2j+1 block is also unallocated. Continue until no more unallo- cated buddy blocks can be merged. CourseNana.COM

Note the following: CourseNana.COM

•Unallocated buddy blocks which have been merged  are no longer eligible for allocation, only the new parent unallocated block can be allocated (unless it is split up again) CourseNana.COM

Reallocation algorithm
When an allocated piece of memory is requested to be reallocated, follow this algorithm:
CourseNana.COM

    1. Make a new request for allocation at the new requested size, computing as if the previous piece of memory is freed
    2. If the new allocation succeeds, the original data in the previous piece of memory should be made available at the

new allocated block according to the details for the virtual_realloc function below CourseNana.COM

    1. If the new allocation fails, the original allocation must be unchanged

Managing your Virtual Heap Memory CourseNana.COM

All functions that you have to implement accept a heapstart parameter, which is a pointer to the start of the contiguous region of memory that represents your virtual heap. CourseNana.COM

Your code can call a virtual_sbrk function that you can use to determine and change the size of your virtual heap space, analogously to the real-world sbrk and brk syscalls; its prototype is below. You do not need to use the real sbrk or brk for this assignment. CourseNana.COM

void * virtual_sbrk(int32_t increment); CourseNana.COM

The “program break” of your virtual heap refers to the address of the first byte after the end of your heap. (For the avoidance of doubt, “program break” in this document always refers to your virtual heap, and not any real program break of your process memory layout). CourseNana.COM

The increment parameter indicates the number of bytes to increase (positive increment) or decrease the virtual heap size, by changing the program break by the same amount. If the call is successful, virtual_sbrk returns the previous program break of your virtual heap. If the call is unsuccessful (for example because the virtual heap cannot increase further in size), virtual_sbrk returns (void *)(-1) (errno is not set). CourseNana.COM

If virtual_sbrk indicates it cannot increase your virtual heap space and this would cause your allocation to fail, then you should return the appropriate error for your function. CourseNana.COM

Functions to implement CourseNana.COM

Implement the following functions for your allocator. Do not write any main() function. Other programs will directly call your functions. CourseNana.COM

void init_allocator(void * heapstart, uint8_t initial_size, uint8_t min_size); CourseNana.COM

This function will be called exactly once before any other functions in your allocator are called. CourseNana.COM

In this function, initialise your buddy allocation data structures and complete any preparation in the virtual heap memory you have been provided. This will be passed to each of your allocator functions, using the heapstart pointer only. You cannot pass any other state between your functions other than what is in your virtual heap. You may not use the standard library’s dynamic memory (such as malloc), or global variables, or files (even if you store pointers to external memory within your virtual heap). CourseNana.COM

Your buddy allocator starts with an initial unallocated block of memory of 2initial_size bytes. The minimum size of allocatable CourseNana.COM

min_size
It is up to you how you lay out your data structures in your virtual heap, but it must semantically behave as the buddy allocator CourseNana.COM

described above. Use virtual_sbrk to set your virtual heap size as you require. CourseNana.COM

void * virtual_malloc(void * heapstart, uint32_t size); CourseNana.COM

Request an allocation from your allocator of size bytes. Follow the buddy allocation algorithm outlined to return a pointer to the block of memory that you have allocated for the caller. Return NULL if you cannot fulfil the allocation or if size is 0. Newly allocated memory does not need to be initialised. CourseNana.COM

int virtual_free(void * heapstart, void * ptr); CourseNana.COM

ptr is a pointer to a previously allocated block of memory. Your allocator should free the allocation according to the buddy allocation algorithm above. If successful, return 0. If ptr is not a pointer to a block of memory that was previously allocated, return non-zero. CourseNana.COM

void * virtual_realloc(void * heapstart, void * ptr, uint32_t size); CourseNana.COM

Resize a previously allocated block of memory pointed to by ptr to a new size of size bytes, according to the buddy allocation algorithm above. The contents of the new block of memory should be identical to the old. If the size is smaller, the contents should be truncated. If the size is larger, the newly added memory region does not need to be initialised. Return the pointer to the new allocation (which may be identical to ptr). Return NULL if you cannot fulfil the reallocation. In this case, the previously allocated block of memory should not be freed and should be unchanged. If ptr is NULL, you should behave as if virtual_malloc(size) was called. If size is 0 (including if ptr is NULL in this case), you should behave as if virtual_free(ptr) was called. CourseNana.COM

void virtual_info(void * heapstart); CourseNana.COM

Print out information about the current state of your buddy allocator to standard output. Output one line per allocatable block, allocated or unallocated, from “left” to “right”, in the following format: <allocation status> <size>. Allocation status is either allocated or free and size is in bytes (of the entire block). CourseNana.COM

Example CourseNana.COM

Suppose that heapstart = 0x1000 and init_allocator is called with initial_size = 15 and min_size = 12. The diagram below shows the initial state of the virtual heap. Note that the space and location of your data structures is up to you and depends on your implementation of the buddy allocator. Note that virtual_sbrk has been used to set the virtual program break appropriately to fit what is being placed on the virtual heap. CourseNana.COM

CourseNana.COM

Suppose that virtual_malloc(heapstart, 8000) is called. Therefore, we split the starting block in half twice, then allocate the leftmost block of size 2 The address of this block is returned to the caller. for this request of size 2 , but we only have an unallocated block CourseNana.COM

CourseNana.COM

Suppose that virtual_malloc(heapstart, 10000) is called. 2 214 block and return its address to the caller, so we allocate our only unallocated CourseNana.COM

CourseNana.COM

At this stage, if virtual_info(heapstart) was called, we expect the output: CourseNana.COM

allocated 8192 CourseNana.COM

free 8192 CourseNana.COM

allocated 16384 CourseNana.COM

Suppose the allocated 213 block were freed. It will merge with its unallocated buddy to the right, forming an unallocated 214 size block. However, the buddy of this is not free, so there is no more merging that occurs. If the allocated 214 size block were also freed, it would merge with its buddy to reform the original 215 size block. CourseNana.COM

Restrictions
In your allocator library code: CourseNana.COM

  • You may not access outside the bounds of your virtual heap without using virtual_sbrk to resize it properly
  • You may not use dynamic memory of any kind, including any from the standard library allocator, brk, sbrk, mmap,

alloca or variable-length arrays, except that which you obtain from virtual_sbrk. CourseNana.COM

  • You may not access any files, or use any global or static variables.

In your testing code (code that sets up and runs test cases which call your allocator library code): CourseNana.COM

• The above restrictions do not apply. CourseNana.COM

• Youmayusedynamicmemory.Youmaynotuseallocaorvariable-lengtharrays. If your submission violates any of these restrictions, it may receive 0. CourseNana.COM

Test Cases
You must write test cases for this assignment. Details on execution and marking of your test cases is included below. CourseNana.COM

You will need to create your own virtual heap memory area and write your own virtual_sbrk function in your testing code for your library to access. CourseNana.COM

  CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
COMP2017代写,System Programming代写,C代写,University of Sydney代写,COMP2017代编,System Programming代编,C代编,University of Sydney代编,COMP2017代考,System Programming代考,C代考,University of Sydney代考,COMP2017help,System Programminghelp,Chelp,University of Sydneyhelp,COMP2017作业代写,System Programming作业代写,C作业代写,University of Sydney作业代写,COMP2017编程代写,System Programming编程代写,C编程代写,University of Sydney编程代写,COMP2017programming help,System Programmingprogramming help,Cprogramming help,University of Sydneyprogramming help,COMP2017assignment help,System Programmingassignment help,Cassignment help,University of Sydneyassignment help,COMP2017solution,System Programmingsolution,Csolution,University of Sydneysolution,