辅导CSE 220留学生编程、写作Dynamic Allocator、Python

” 辅导CSE 220留学生编程、写作Dynamic Allocator、PythonCSE 220: Systems ProgrammingProgramming Assignment 4: Dynamic AllocatorIntroductionIn this assignment, you will implement a dynamic memory allocator suitable for replacing malloc() for heapmemory in a Unix process. You will learn about dynamic memory management, pointer manipulation, andpointer casting.The type of allocator you will implement is a pool allocator, using multiple memory pools. Each memorypool consists of allocations of a fixed size. Allocations are served out of the smallest pool that supports theusers request, and allocations too large for any memory pool are requested from the OS directly. The memorypools in this project will contain allocations ranging from 32 bytes to 4096 bytes.Your allocator is designed in such a way that you will be able to use it to run standard Unix binaries! Becauseyou will not be implementing support for concurrency, some programs may fail through no fault of your own;however, many programs will operate correctly. You may find it interesting and enjoyable to use your allocatorimplementation to learn about the memory accesses of standard applications.This document is long, but there is a reason for that. Please read it carefully and in its entirety beforestarting your assignment! There are many subtle requirements in this document that will require criticalthinking about program structure; for example, the relationship between allocation sizes and the free list table.Plan to sit down and draw out your data structures and implementation when you begin. You will not savetime by skipping this step!1 Getting StartedYou should have received a GitHub Classroom invitation for this assignment. Follow it, then check out yourrepository.Chapter 9, Section 9.9 of Computer Systems: A Programmers Perspective describes a dynamic allocator implementationin some detail. You may want to read this section before starting your project, and will certainlywant to read it carefully while implementing your project.Chapter 8, Section 8.7 of The C Programming Language also describes a dynamic allocator of similar structureto that described in CS:APP. This allocator is described in somewhat less detail, but uses techniques (such asdeclaring structures to hold metadata, Rather than using macros and pointer math) that are to be preferredover the approach in CS:APP, so you should Read and try to understand it, as well. Again, you may want to readthis section before you begin, and will certainly want to read it carefully during implementation.You will absolutely need to read man 3 malloc. It is not long. We will not answer questions that are clearlyanswered in man 3 malloc.Some parts of this handout may not make much sense until you have read the above readings.2 Pool AllocatorsPool allocators are designed to allow applications to efficiently allocate, free, and reallocate chunks of memoryin sizes that they use frequently. This is an effective strategy for many applications because it is common foran application to allocate many objects that are the same size for example, nodes in a linked list or tree, orbuffers for communication. Placing such frequently-used objects in a pool where they can be rapidly reallocatedimproves application performance.Allocation pools are maintained by requesting large-ish blocks of memory from the operating system, thenbreaking those blocks up into the allocation size stored in a pool. These free blocks are then used to serveallocations requested by the user. When blocks are freed by the user, they are simply placed back in the pool,preventing future allocations from having to request more memory from the operating system. When an allocationis requested from a pool that does not contain any free blocks, the allocator will request another largechunk from the operating system to be broken up again.1You will be implementing a multi-pool allocator, which will maintain pools containing allocation blocks withsizes of powers of two between 25(32) and 212 (4096). These blocks will be used to serve allocations of 24 (328)to 4088 (4096 8) bytes, using the remaining 8 bytes between these sizes and the power of two to storemetadata. Because the free() function does not accept a size argument, this metadata will be used to store thesize of the block for use by free(). Each allocation request will be served from the smallest block that will storethe allocation; for example, a 1 byte allocation would come out of a 32 byte block, while a 1000 byte allocationwould come out of a 1024 byte block.3 RequirementsYou must implement the following functions in the file src/mm.c: void *malloc(size_t size) void *calloc(size_t nmemb, size_t size) void *realloc(void *ptr, size_t size) void free(void *ptr)Your implementation must satisfy the standard definition of these functions (see man 3 malloc), with the exceptionthat it need not allow for concurrent access from multiple threads, as well as the additional implementationrequirements listed here.Your implementation must be a multi-pool allocator as described in this document. No other type of allocatorimplementation will receive credit. It must use pool allocation as described here to implement all allocationsbetween 1 and 4088 bytes, and a simple bulk allocator (described below) for allocations larger than 4088 bytes.(The discrepancy between 4088 bytes and the even-power-of-two 4096 bytes, mentioned in Section 2, will befurther explained later.)All memory returned by your allocation functions (malloc(), calloc(), and realloc()) must be 8 byte aligned.Failure to maintain this Requirement will not result in functional failures of your allocator on the x86-64 platform(programs using your allocator would continue to work correctly), but may result in degraded performancefor programs using your allocator. On other platforms, failure to maintain this requirement could resultin program crashes.Your implementation must be able to resize an allocation using realloc. Under certain circumstances itshould do this without performing any new allocation, and under other circumstances it should do this byallocating a new block and copying the users data from the old block to the new. If it is possible to perform thereallocation without allocating a new block and moving data, your implementation must do so. This is alwayspossible for reallocations which reduce the size of an allocation, as realloc() can return the existing block, andthe user will simply use less of it. For allocations which increase the size of the allocation, it is possible onlyif the block originally selected to serve the users allocation is also large enough to serve the new allocation.For example, if the user calls malloc(32) to request a 32 byte allocation, your allocator will select a 64 byte blockcontaining 56 usable bytes of memory. If the user later wishes to realloc() this block to 48 bytes, this does notrequire any allocation or copying, as while 48 bytes is more than the original 32 bytes requested, it is less thanthe 56 bytes available in this block.If realloc() cannot resize a block without performing allocation, it must use your allocator to acquire a newblock of the appropriate size (which is necessarily larger than the original block), copy the users data from theold block to the new block, and then free the old block.When changing the size of an allocation using realloc(), your implementation must attempt to resize theallocation in place, if possible. For reallocations that reduce the size of the allocation, this should always succeed.For reallocations that increase the size of the allocation, it should succeed if there is sufficient space in theallocated block after the allocation being resized. Only if this is not the case should a new allocation be createdand the memory of the original allocation be moved to the new location before freeing the original allocation.Requests for an allocation of size 0 to any of the allocator functions may either use the pool allocator tocreate a minimum-size allocation or return NULL, as you prefer. You will probably find that simply returning2NULL is easier, but if for some reason your algorithm benefits from the possibility of returning a minimum-sizeallocation, you may do so.Your allocator must be capable of returning freed memory to the heap and reusing it to serve future allocations.In particular, if a program repeatedly allocates and frees many small objects with a constant upperbound on the number of objects and total space required, your allocator should eventually settle on a heap sizethat requires no additional requests to the operating system for more memory.You must test your own project. The tests provided in Autograder will be incomplete, and you should notrely upon them to give more than a rough estimate of your final score. There is no requirement to submit yourtests for this project.3.1 Metadata and Global SymbolsAs described in CS:APP in Section 9.9, a heap allocator must not use any global state of non-constant size thatcannot be allocated from the heap itself. Therefore, you should declare only primitive global (or static) variablesfor your allocator, and you Must use the heap for any other data required. A clever implementation will add afew constant bytes to each allocation and store the rest of its variably-sized metadata in free blocks, requiringonly a constant allocation at initialization time for its remaining storage.3.1.1 Static VariablesAny global variables or functions declared by your implementation in mm.c should include the keyword static.This will ensure that they are not visible to any other translation units, and that your allocators function cannotbe disrupted by code that May link to it. (See Section 4.6 of KR for more discussion of static variables, and thecompiler.pdf slide deck for a definition of translation units.)3.1.2 Block HeadersThe metadata stored for each block of memory managed by your allocator (allocated or free) should be a 64 bitheader word preceding the allocation (or free block), containing the size of the allocation and some flag bits.Note that the minimum possible block size for the pool-allocated blocks is 25, or 32 bytes, and that all poolallocatedblocks have sizes which are powers of two. Recalling the format of integers in memory, this meansthat the lowest five bits of the integer size of a block, whether it is free or allocated, will always be zero. Thosebits can therefore be used to store flags, and then masked out when retrieving the size of a block. CS:APPexplains this in some detail in Section 9.9.6 (In particular, see Figure 9.35).You should use the lowest-order bit (the ones bit) to indicate whether a block is free or allocated; a onebit will indicate an allocated Block, and a zero bit will indicate a free block. While this is not entirely necessaryto complete this project, it makes the implementation of a heap validator (suggested in Section 5) much moreeffective. Remember to account for this when allocating and freeing bulk-allocated blocks, if necessary. Youwill probably find that bitwise operations are the best way to maintain the allocated bit and other bits in the sizefield, rather than using + 1 and – 1 (which has for some reason proven both a popular technique and a popularsource of bugs in the past).The pointer returned by the allocation functions, and the pointer given to free() or realloc(), is the firstbyte of memory after the header word. Your implementation will have to use pointer math to find the headerword for a block that is passed to free() or realloc(), and perhaps to calculate the address to be returned frommalloc() et al.This metadata is the reason that your allocators effective allocation sizes are 8 bytes smaller than an evenpower of two. The block from which an allocation is drawn is a power of two in size, but there are 8 bytes ofheader used from that block for storing metadata.3.2 The sbrk System CallThe operating system provides two system calls to manipulate the program break between the applicationsheap and the unmapped memory region above the heap: brk() and sbrk(). The brk() system call accepts anabsolute address and immediately sets the program break to that point, while sbrk() accpets a relative size and3adjusts the current program Break by that amount. It is difficult to use brk() correctly and safely, so we will usesbrk() for this assignment.Passing a positive value to sbrk() causes the system to move the program break the requested numberof bytes upward in memory, toward larger addresses. It will then return the old value of the program break,which is a memory address. The newly allocated memory therefore begins at the address returnd by sbrk()and continues for the number of bytes requested by the application.3.3 The Multi-Pool AllocatorYour allocator must use the following pool allocation policy for allocations between 1 and 4088 bytes. All allocationsfrom the pool allocator portion of the heap will be in blocks of size 2y, 5 y 12.All allocations of size 4088 bytes or smaller will be rounded up to the next larger integer size x satisfyingthe equation x = 2y 8, for some y between 5 and 12 (inclusive); that is, 24, 56,120, . . . , 4088. These allocationswill be served out of blocks of memory 8 bytes larger than x, to allow space for your allocator to store metadataabout the allocation. This means that the smallest unit of memory your pool allocator will manage is 32 bytes(including metadata), and the largest unit of memory your pool allocator will manage is 4096 bytes (includingmetadata).The provided function Block_index() will return y (which you may find more convenient than x itself for someoperations), given x. In other words, it will return the log base 2 of the block size required to serve the requestedallocation. You can use this as an index into a table of pools containing free blocks of specific sizes, as discussedin Section 3.5.Your allocator will maintain a separate free list for each of the block sizes described above. Every block onthe free list for a given size will be of that size, and available for allocation. When your allocator attempts toallocate a block of a given size and there are no blocks on the relevant free list, it will request 4096 bytes ofmemory from the OS using the sbrk() system call, break the returned allocation up into blocks of the desiredsize, and place them on the appropriate free list. By calling sbrk() relatively infrequently and serving allocationsout of fixed-size blocks in this fashion, you improve the run-time performance of your allocator at the expenseof some memory overhead.Each allocation in your multi-pool allocator should first attempt to find an existing free allocation block ofthe desired size. If such a block exists, your allocator should use it. If it does not, your allocator should request4096 bytes of memory from the OS as described above, then retry the allocation.3.4 The Bulk AllocatorFor all allocations of larger than 4088 bytes, a bulk allocator must be used that maps a single object into theprocesss memory space directly, and unmaps it on free. The following provided methods should be used toaccomplish this; you will reserve 8 bytes of extra memory for bookkeeping when calling these functions; i.e.,if your allocator is serving a request for 4096 bytes of memory, you will request 4104 bytes from the bulkallocator. These extra 8 bytes will be used to provide a header for bulk allocated objects in the same fashion aspool allocated objects, so that they can be freed easily. void *bulk_alloc(size_t size) void bulk_free(void *ptr, size_t size)The bulk_alloc() function returns a pointer to a contiguous block of memory of at least size bytes, similar tomalloc(). However, unlike malloc(), this allocation cannot be freed with free(). Instead, bulk_free() will free thisblock when provided with Both its address and its size in bytes. You may view the implementations of these functionsin the provided file src/bulk.c, although you should not modify them and you do not need to understandthem. They use the system calls mmap() and munmap() to request specific modifications to the processs memorymap.Note that you must provide the size of the allocation being freed to the bulk allocator. It cannot determine thisitself! This is the purpose of the extra 8 bytes of overhead requested by your allocator.Figure 1: A free list table containing six free blocks of memory. Each block is labeled with its size and free flag.3.5 Free List TableYou must store the free blocks in your allocator in a set of explicit free lists (as opposed to the implicit freelist described in CS:APP). For an explicit free list, the allocation space inside a free block (which is otherwiseunused) is used to store pointers to the next and previous free blocks on the list. You can define a structure,similar to the ListNode structure You used for PA2, that includes the free block header, a next pointer, and aprevious pointer, and then use pointer type casting to map it to the address of a free block on the heap. Youmay find that your PA2 code can be used almost directly for this project!Note that this project requires only that you are able to insert and remove from the head of a list. You shouldnever walk a list. It is important that malloc() and free() are constant-time operations, and for this reason, theirrun time should not depend on the length of free lists. You can likely therefore use singly-linked lists for thisproject. All of the allocation sizes are large enough for doubly-linked lists if you wish to use your PA2 code,however.As explained in CS:APP, Section 9.9, this sort of free list requires no extra space. The pointers that makeup the free list use the space inside the free blocks that would otherwise be used by the application when theblocks are allocated. Make sure that you understand this subtle point. It is critical that you do NOT manipulatethese pointers on an allocated block!By creating a table of these lists indexed by the log base 2 of the size of objects at each entry, you can useblock_index() to very quickly determine whether a free block of a given size is available. The block sizes forthis project were carefully chosen to be precise powers of two for this very reason. Figure 1 shows an exampledepiction of such a table.You must allocate the free list table itself on the heap. To avoid malloc() depending on malloc(), you may wishto allocate it directly using sbrk(); because it will never be freed, this is not a problem, and it does not require aheader or any other allocation structure.4 GuidelinesThere are many aspects of this project that you may choose to implement in a variety of ways. You have examplesof some portions of the project in the form of Section 9.9 of CS:APP and Section 8.7 of KR. This sectioncontains some guidelines on how you might tackle those aspects, as well as general advice to help you succeedin this project.54.1 Structures and TypesComputer Systems: A Programmers Perspective presents an allocator implementation that uses preprocessormacros and raw pointer accesses to extract essentially all of the information from allocation blocks. I do notrecommend this approach. The approach in The C Programming Language is more appropriate, although it usesa union in a way that I do not think is necessary (for portability reasons that we are not currently concernedwith), and stores its fields in a different order than is required in this project.Consider declaring a structure that encompasses the header word, previous, and next pointers for the freelist, and using that structure to access the free list. You can probably use some of your PA2 implementationscode for this purpose.The reason for this recommendation is multi-fold, but the two most important considerations are: The use of macros to implement program functionality can make debugging very difficult. Limiting usage of void pointers and pointer casting as much as possible will help the compiler flag errors,by allowing type errors to indicate logic errors.4.2 Macros and FunctionsThe previous notwithstanding, you will probably still need or want some macros or functions to perform typecasting and certain pointer manipulations reliably and consistently. You absolutely should not have randomadditions and subtractions of fixed values or sizeof() calculations sprinkled all throughout your code! Thismakes it very easy to miss a location where you should have made such a calculation, and did not; a macro orfunction to perform this cast and change is a better solution. In general, prefer functions over macros (becauseof type checking), but in some places macros may be appropriate.4.3 Task DecompositionYou may find that it improves the clarity and flow of your code by breaking the various tasks down into smallerfunctions that may even be used by more than one portion of your implementation. You should absolutely doso! Declare static functions in mm.c to encapsulate such functionality.In particular, the logic for requesting more heap space using sbrk() when necessary and breaking up freeblocks to serve smaller allocations will likely be shared between several functions.Remember also that some operations can be delegated to other required functions in particular, malloc().4.4 Pointer MathYou will do a lot of pointer math in this project! You may find it easiest to do this math by first casting thepointer to void *, then manipulating it using simple arithmetic and sizeof(). Remember that while arithmeticon void * behaves normally, arithmetic on other types operates in increments of the size of the type. Thismeans, for example, that (void *)0 + 1 is 1, while (int *)0 + 1 is 4. Therefore, you may find it less confusing tosimply cast any value to void * before manipulation.5 TestingYou should plan to write a heap validator for your project. This is a function that you can call while debugging tocrawl through your heap structure and verify its correctness. You should be able to use your list_validate()from PA2 as part of this process, but will also want to check other things that are allocator-specific. You maywish to use debug macros such as discussed in class when talking about the C preprocessor to include extrainformation for validation, routinely validate the heap, etc., when a debug symbol is defined. Like drawingyour data structures, you will absolutely not save time by skipping this step. You should consider developingit along side, or even before, your allocator implementation!Your project will be built into a shared object (library) when you run make in the top-level source directory.You can use this library to run standard Unix system utilities using your allocator, or you can link mm.o and6bulk.o against tests that you write. The project Makefile is extensively commented and provides informationabout how to do both of these things.Liberally sprinkling your project with debugging statements and correctness assertions that can be turnedon and off with the preprocessor will make your job easier. When printing debugging statements, you willwant to use fprintf(stderr, …) for a variety of reasons; in addition to the previously-mentioned benefits of thisapproach (such as unbuffered output), this is guaranteed not to allocate memory. When debugging an allocator,that is an important property!The debugger will be indispensable for this project. Plan to use it often to examine pointer values. Rememberthat the gdb print Command will print the value of any expression, including pointer arithmetic andcasting.Some example simple programs to test your library against include ls, w, echo, and ps. These and manyother Unix commands should run under your allocator once it is complete. You can look at their man pagesfor more information, and TAs may be able to help you find other commands to test. If your allocator becomessufficiently robust, large applications such as Emacs will even run! Note that, because your allocator need notsupport multiple threads (we havent yet talked about how to do this), some applications will not run and it isnot your fault. If simple command-line applications fail to run, you should suspect your allocator. If large GUIapplications fail to run, it is probably that they are trying to use threads. (Emacs 25, which is installed on thecourse VM, happens to be single-threaded, so it is an exception to this rule.)TAs and instructors will expect you to have implemented a heap validator and know how to use it on thisproject. Bugs that appear to be easily identified by a working validator will meet a response of what does yourvalidator say? If you need help strengthening your validator, ask!6 SubmissionUse make submission to build a submission tarball, malloc.tar, that you will upload to Autograder. The Autogradertests for this project will be incomplete, but give an indication of the correctness of your project.This is a three week project. It is a three week project because it will take more time and care to implementthan previous projects! Implementing an allocator is a tricky and subtle problem, and you can lose a lot of timeto debugging. Plan to start early and work consistently; you will have much more success with this approachthan you will with sitting Down for a few marathon coding sessions late in the assignment.7 GradingThe handout quiz for this project will be worth 0.5% of your final course grade, and the rubric below will beworth 9.5% of your final course grade, for a total of 10% of your grade. The handout quiz score will not bereflected on Autograder for this project.Your project will be evaluated as follows:Description PointsHandout quiz 1All allocations are 8 byte aligned 1All heap data structures are allocated on the heap 1sbrk() is called for CHUNK_SIZE only 1Pool allocations are for powers of 2 2Bulk allocations are used for large allocations 1malloc(), calloc(), and realloc() use pool allocation 3calloc() properly clears memory 1realloc() can extend (and reduce) allocations 1realloc() copies memory when necessary 1free() returns memory to the heap 2Functions sufficiently to run simple applications 5如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“