A2 Allocator.html (5555B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.6 (457297)"/><meta name="altitude" content="-1.684619069099426"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-12-06 18:33:59 +0000"/><meta name="latitude" content="52.33329560521331"/><meta name="longitude" content="4.866571327957702"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-12-09 12:34:11 +0000"/><title>A2 Allocator</title></head><body><div>= Basic info =</div><div>malloc — allocate memory of given size</div><div>free — deallocate memory</div><div>realloc — extend/shrink previously allocated</div><div>calloc — zero-initialised memory</div><div><br/></div><div>first layer:</div><div>allocator manages virtual memory region (heap)</div><div>if free block is available in heap, block is returned</div><div>sometimes run out of space on heap, need more. need to tell OS that more virtual memory is needed — ask OS for more virtual memory using brk() (‘please extend the heap’). mmap() (‘create new virtual region in the address space’) is a generalised brk(). munmap() is undo for mmap().</div><div>every time you need memory, the mmu will try to translate and get page fault, which is done with page fault handler.</div><div>virtual memory regions are basically contract between OS and application on legal ranges of memory that we can access</div><div><br/></div><div>demand paging:</div><ol><li><div>Program calls brk() to grow its heap</div></li><li><div>brk() enlarges virtual memory address space. new pages are not mapped onto physical memory.</div></li><li><div>Program tries to access new memory, processor page faults.</div></li><li><div>Kernel assigns page frame to process, creates page table entry, and resumes execution. Program lives happily ever after in userland.</div></li></ol><div><br/></div><div><span style="font-weight: bold;">assignment</span></div><div>allocate user space allocator. gets memory from kernel, divides that, etc.</div><div><br/></div><div>void *malloc(size_t size) — allocate size bytes. alignment should be 8 bytes.</div><div>void free(void *ptr) — free object starting at ptr</div><div>void *calloc(size_t nmemb, size_t size) — allocate nmem * size bytes, zeroed out</div><div>void *realloc(void *ptr, size_t size) — grow object starting at ptr to size bytes, optionally moving allocation if needed.</div><div><br/></div><div><br/></div><div><span style="text-decoration: underline;">requesting memory from kernel</span></div><div>nmap: allocate arbitrary virtual memory areas</div><div>brk/sbrk: grow/shrink heap area</div><div><br/></div><div>int brk(void *addr) — set program break (end of heap) to addr (if reasonable)</div><div>void *sbrk(intptr_t increment) — grow/shrink heap by increment bytes. returns old brk address.</div><div><br/></div><div><span style="text-decoration: underline;">getting started</span></div><div>void *mymalloc(size_t size) {</div><div> return sbrk(size);</div><div>}</div><div><br/></div><div>problems:</div><ul><li><div>size unaligned. should be aligned to 8 bytes, so have to add some alignment. minimum of 8 bytes.</div></li><li><div>free function is empty. it will run out of memory. how implement free function?</div></li><ul><li><div>determine size of ptr. how big is the object?</div></li><li><div>mark area as free. then malloc can search free areas first.</div></li></ul></ul><div><br/></div><div><span style="text-decoration: underline;">design options</span></div><div>in-band list metadata</div><div><img src="A2%20Allocator.resources/screenshot.png" height="273" width="545"/><br/></div><div>each node contains metadata (size, next, prev, is_free) and space for the object.</div><div>when freeing, merge with adjacent free areas.</div><div>avoid fragmentation — non-contiguous free areas.</div><div><br/></div><div><span style="text-decoration: underline;">list metadata example</span></div><div>struct obj_metadata {</div><div> size_t size;</div><div> struct obj_metadata *next;</div><div> struct obj_metadata *prev;</div><div> int is_free;</div><div>};</div><div><br/></div><div>don’t use artificial limit on max number of objects. should have pointer to heap_start, and pointer to freelist (both void). dynamically grow. would give penalty.</div><div><br/></div><div><span style="text-decoration: underline;">Grading</span></div><div>1 point — showing up (valid submission)</div><div>1 point — malloc</div><div>0.5 pnt — calloc</div><div>2 point — free + reuse</div><div>1 point — realloc (+only when needed)</div><div><br/></div><div>1 point — batch brk: preallocate e.g. 4K of memory, only brk when 4K is full</div><div>2 point — reduce overhead per allocation (brk size vs malloc’d size)</div><div>0.5 pnt — locality (new allocations use least recently freed slots)</div><div>1 point — return memory to kernel (give negative to sbrk). return reasonable sized (e.g. 4K) chunk at end of heap if became free.</div><div>1 point — out-of-band metadata. e.g. slab allocator. this often excludes other points.</div><div>2 point — system malloc. implement malloc without prefix. use with LD_PRELOAD env var. tests run ls, grep, python.</div><div><br/></div></body></html>