程序代写 * memlib.c – a module that simulates the memory system. Needed

* memlib.c – a module that simulates the memory system. Needed
* because it allows us to interleave calls from the student’s malloc
* package with the system’s malloc package in libc.
* This version has been updated to enable sparse emulation of very large heaps.

Copyright By PowCoder代写 加微信 powcoder

* Sparse emulation uses the same mmap pages for the normal heap but instead
* uses them as part of a map. Using the same amount of space, designs should
* fit reasonably into both dense and sparse. However, mdriver was modified
* to reduce its writing of payload bytes, as these bytes accounted for
* additional load on the emulation system and pushed some implementations to
* run out of emulation memory.
* map(emulated address / PAGE_SIZE) -> mem_block_t
* map(mem_block_t, emulated address % PAGE_SIZE) -> byte(s)
* This mapping is for a single address; however, accesses can span two blocks
* so the mapping sequence checks accounts for size and can perform two
* lookups if necessary.
* Storing in the sparse emulation goes through the above lookup process and
* then memcpy’s the bytes into the block.
* Loading from the sparse emulation uses the above lookup and then aggregates
* the data into a return value.
* If an emulated access is made to an address outside of the current
* bounds (mem_heap_lo, mem_heap_hi), then the address is assumed to be to
* a non-heap location, such as stack, global variables, etc. For some
* implementations, this access is meant to be to the heap and was “safe”
* in non-emulation, as it was to the same page as actual heap data. But
* sparse emulation has tighter checks. Commonly, the CPU reports a
* BUS ERROR on these accesses, and should be debugged as segmentation faults.
#include
#include
#include
#include
#include
#include
#include
#include
#include

#ifdef USE_ASAN
#include

#ifdef USE_MSAN
#include
void markGlobalsUninit(void);

#include “config.h”
#include “memlib.h”

/* Data structure used to implement pages in sparse memory emulation */
typedef struct MBLK
size_t id; /* Page ID. Counts number of pages from start of heap */
struct MBLK *next; /* Link for hash table */
unsigned char initSet[SPARSE_PAGE_SIZE / 8];
unsigned char bytes[SPARSE_PAGE_SIZE]; /* Page contents */
} mem_block_t;

/* private global variables */
static bool sparse = false; /* Use sparse memory emulation */
static unsigned char *heap; /* Starting address of heap */
static unsigned char *mem_brk; /* Current position of break */
static unsigned char *mem_max_addr; /* Maximum allowable heap address */
static size_t mmap_length =
MAX_DENSE_HEAP; /* Number of bytes allocated by mmap */
static bool show_stats =
false; /* Should program print allocation information? */
static bool stats_printed =
false; /* Has information been printed about allocation */

/* Sparse memory representation */
static mem_block_t *next_free_page = NULL; /* Next free page */
static size_t num_pages = 0; /* Total number of pages */
static size_t num_free_pages = 0; /* Number of free pages */
static mem_block_t **page_table = NULL; /* Hash table from page ID to page */
static size_t num_buckets = 0; /* Number of buckets in page table */

#ifdef NO_CHECK_UB
static const bool checkUB = false;
void setUBCheck(bool val) {}
static bool checkUB = true; /* should sparse check for UB */
void setUBCheck(bool val)
checkUB = val;

#ifdef USE_ASAN
const char *__asan_default_options()
return “abort_on_error=true:detect_leaks=0”;

#ifdef USE_MSAN
const char *__msan_default_options()
return “abort_on_error=true”;

* Forward declarations
static size_t page_id(const void *addr);
static void *page_start(size_t id);
static void *get_mem(const void *addr, size_t, bool);
static void print_stats();

* mem_init – initialize the memory system model
void mem_init(bool do_sparse)
sparse = do_sparse;
if (sparse)
/* Want sparse total allocation to approximately match the dense heap
/* Account for both page itself and its amortized contribution to the
* page table */
double fbytes_per_page =
sizeof(mem_block_t) + sizeof(mem_block_t *) / HASH_LOAD;
num_pages = (size_t)(MAX_DENSE_HEAP / fbytes_per_page);
num_buckets = num_pages / HASH_LOAD;
mmap_length = num_buckets * sizeof(mem_block_t *) + // Page table
num_pages * sizeof(mem_block_t) + // Pages
sizeof(uint64_t); // Padding
setUBCheck(true);
/* Dense allocation */
next_free_page = NULL;
num_pages = 0;
page_table = NULL;
num_buckets = 0;
mmap_length = MAX_DENSE_HEAP;

int dev_zero = open(“/dev/zero”, O_RDWR);
void *start = sparse ? NULL : TRY_DENSE_HEAP_START;
void *addr = mmap(start, /* suggested start*/
mmap_length, /* length */
PROT_READ | PROT_WRITE, /* permissions */
MAP_PRIVATE, /* private or shared? */
dev_zero, /* fd */
0); /* offset */
if (addr == MAP_FAILED)
fprintf(stderr, “FAILURE. mmap couldn’t allocate space for heap\n”);
if (sparse)
/* Use initial space for page table */
page_table = (mem_block_t **)addr;
heap = SPARSE_HEAP_START;
mem_max_addr = heap + MAX_SPARSE_HEAP;
heap = addr;
mem_max_addr = heap + MAX_DENSE_HEAP;
stats_printed = false;
mem_brk = heap;

* mem_deinit – free the storage used by the memory system model
void mem_deinit(void)
print_stats();
munmap(heap, mmap_length);
next_free_page = NULL;
num_free_pages = 0;
page_table = NULL;
num_buckets = 0;

* mem_reset_brk – reset the simulated brk pointer to make an empty heap
void mem_reset_brk()
print_stats();
if (sparse)
/* Clear page table */
size_t ptb = num_buckets * sizeof(mem_block_t *);
memset((void *)page_table, 0, ptb);
/* First page is just beyond page table */
next_free_page = (mem_block_t *)((unsigned char *)page_table + ptb);
num_free_pages = num_pages;
#ifdef USE_ASAN
/* Mark the entire heap as unaddressable */
__asan_poison_memory_region(heap, MAX_DENSE_HEAP);
#ifdef USE_MSAN
/* Mark global variables as uninitialized */
markGlobalsUninit();

/* Mark heap as uninitialized (though payloads may be overwritten by driver!) */
__msan_allocated_memory(heap, MAX_DENSE_HEAP);
mem_brk = heap;

* mem_sbrk – simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area.
* In this model, the heap cannot be shrunk.
void *mem_sbrk(intptr_t incr)
unsigned char *old_brk = mem_brk;

bool ok = true;
if (incr < 0) ok = false; fprintf(stderr, "ERROR: mem_sbrk failed. Attempt to expand heap by negative " "value %ld\n", (long)incr); else if (mem_brk + incr > mem_max_addr)
ok = false;
size_t alloc = mem_brk – heap + incr;
fprintf(stderr,
“ERROR: mem_sbrk failed. Ran out of memory. Would require ”
“heap size of %zd (0x%zx) bytes\n”,
alloc, alloc);
else if (!sparse && sbrk(incr) == (void *)-1)
ok = false;
“ERROR: mem_sbrk failed. Could not allocate more heap space\n”);

#ifdef USE_ASAN
/* Mark the extended section of the heap as addressable */
__asan_unpoison_memory_region(mem_brk, incr);
mem_brk += incr;
return (void *)old_brk;
errno = ENOMEM;
return (void *)-1;

* mem_heap_lo – return address of the first heap byte
void *mem_heap_lo()
return (void *)heap;

* mem_heap_hi – return address of last heap byte
void *mem_heap_hi()
return (void *)(mem_brk – 1);

* mem_heapsize() – returns the heap size in bytes
size_t mem_heapsize()
return (size_t)(mem_brk – heap);

* mem_pagesize() – returns the page size of the system
size_t mem_pagesize()
return (size_t)getpagesize();

/*************** Memory emulation *******************/

__int128 mem_read128(const void *addr)
__int128 r;
r = (((__int128)mem_read((char *)addr + 8, 8)) << 64) | mem_read(addr, 8); void mem_write128(void *addr, __int128 val) mem_write(addr, (uint64_t)val, 8); mem_write((char *)addr + 8, (uint64_t)(val >> 64), 8);

/* Read len bytes and return value zero-extended to 64 bits */
uint64_t mem_read(const void *addr, size_t len)
uint64_t rdata;
if (sparse && (unsigned char *)addr >= heap &&
(unsigned char *)addr + len <= mem_brk) /* Heap read. Check if it crosses page boundary */ size_t id = page_id(addr); void *paddr = get_mem(addr, len, false); rdata = *(uint64_t *)paddr; /* Check for split pages */ void *maddr = (void *)((unsigned char *)addr + len - 1); if (id != page_id(maddr)) void *saddr = page_start(id); size_t offset = (unsigned char *)addr - (unsigned char *)saddr; size_t llen = SPARSE_PAGE_SIZE - offset; /* Must zero out upper bytes of data */ uint64_t mask = ((uint64_t)1 << (8 * llen)) - 1; rdata &= mask; void *haddr = (void *)((unsigned char *)addr + llen); void *hpaddr = get_mem(haddr, (len - llen), false); uint64_t hdata = *(uint64_t *)hpaddr; rdata = rdata | (hdata << (8 * llen)); * Read directly from memory. Correct for non-emulation and * if the access is outside of the current heap bounds. * Failure here commonly indicates a garbage pointer value or * not updating the heap bounds properly. memcpy(&rdata, addr, len); if (len < sizeof(uint64_t)) uint64_t mask = ((uint64_t)1 << (8 * len)) - 1; rdata &= mask; return rdata; /* Write lower order len bytes of val to address */ void mem_write(void *addr, uint64_t val, size_t len) if (sparse && (unsigned char *)addr >= heap &&
(unsigned char *)addr + len <= mem_brk) /* Heap write. Check to see if it crosses page boundary */ size_t id = page_id(addr); void *paddr = get_mem(addr, len, true); void *saddr = page_start(id); size_t offset = (unsigned char *)addr - (unsigned char *)saddr; size_t llen = SPARSE_PAGE_SIZE - offset; if (llen < len) /* Two page write */ memcpy(paddr, (void *)&val, llen); size_t ulen = len - llen; void *haddr = (void *)((unsigned char *)addr + llen); void *hpaddr = get_mem(haddr, ulen, true); unsigned char *src = (unsigned char *)&val + llen; memcpy(hpaddr, (void *)src, ulen); /* Single page write */ if (len == sizeof(uint64_t)) *(uint64_t *)paddr = val; memcpy(paddr, (void *)&val, len); * Write directly to memory. Correct for non-emulation and * if the access is outside of the current heap bounds. * Failure here commonly indicates a garbage pointer value or * not updating the heap bounds properly. if (len == sizeof(uint64_t)) *(uint64_t *)addr = val; memcpy(addr, (void *)&val, len); /* Emulation of memcpy */ void *mem_memcpy(void *dst, const void *src, size_t num_bytes) void *savedst = dst; size_t word_size = sizeof(uint64_t); while (num_bytes >= word_size)
uint64_t data = mem_read(src, word_size);
mem_write(dst, data, word_size);
num_bytes -= word_size;
src = (void *)((unsigned char *)src + word_size);
dst = (void *)((unsigned char *)dst + word_size);
if (num_bytes)
uint64_t data = mem_read(src, num_bytes);
mem_write(dst, data, num_bytes);
return savedst;

/* Emulation of memset */
void *mem_memset(void *dst, int c, size_t num_bytes)
void *savedst = dst;
uint64_t byte = c & 0xFF;
uint64_t data = 0;
size_t word_size = sizeof(uint64_t);
for (i = 0; i < word_size; i++) data = data | (byte << (8 * i)); while (num_bytes >= word_size)
mem_write(dst, data, word_size);
num_bytes -= word_size;
dst = (void *)((unsigned char *)dst + word_size);
if (num_bytes)
mem_write(dst, data, num_bytes);
return savedst;

/* Function to aid in viewing contents of heap */
void hprobe(void *ptr, int offset, size_t count)
unsigned char *cptr = (unsigned char *)ptr;
unsigned char *cptr_lo = cptr + offset;
unsigned char *cptr_hi = cptr_lo + count – 1;
unsigned char *iptr;
if ((void *)cptr_lo < mem_heap_lo()) fprintf(stderr, "Invalid probe. Address %p is below start of heap\n", if ((void *)cptr_hi > mem_heap_hi())
fprintf(stderr, “Invalid probe. Address %p is beyond end of heap\n”,
printf(“Bytes %p…%p: 0x”, cptr_hi, cptr_lo);

bool cUBVal = checkUB;
setUBCheck(false);
for (iptr = cptr_hi; iptr >= cptr_lo; iptr–)
printf(“%.2x”, (unsigned)mem_read((void *)iptr, 1));
setUBCheck(cUBVal);
printf(“\n”);

/*************** Private Functions *******************/

static void print_stats()
size_t vbytes = mem_heapsize();
if (!show_stats || vbytes == 0 || stats_printed)
if (sparse)
size_t ppages = num_pages – num_free_pages;
size_t pbytes = ppages * SPARSE_PAGE_SIZE;
printf(“Allocated %zu/%zu pages (%zu bytes) to cover %zu heap bytes ”
“(%.4f%% density). Max address = %p\n”,
ppages, num_pages, pbytes, vbytes, 100.0 * pbytes / vbytes,
printf(“Allocated %zu heap bytes. Max address = %p\n”, vbytes,
stats_printed = true;

/* Given an address, compute the ID of its page */
static size_t page_id(const void *addr)
size_t offset = (unsigned char *)addr – (unsigned char *)SPARSE_HEAP_START;
return offset / SPARSE_PAGE_SIZE;

/* Given a page ID, compute its starting address */
static void *page_start(size_t id)
size_t offset = id * SPARSE_PAGE_SIZE;
return (void *)((unsigned char *)SPARSE_HEAP_START + offset);

/* Get memory to store value. Allocate page if necessary */
static void *get_mem(const void *addr, size_t size, bool isWrite)
size_t id = page_id(addr);
size_t b = id % num_buckets; // A very simple hash function
unsigned int i;

mem_block_t *block = page_table[b];
while (block && block->id != id)
block = block->next;
if (!block)
/* Need to allocate a new block */
if (num_free_pages == 0)
* This will often fail due to student code that either accesses
* too many memory locations, such as checking every byte in a
* block. Or more commonly due to poor utilization, such as
* leaking or not finding the huge allocations.
fprintf(stderr, “FAILURE. Ran out of memory for emulation\n”);
block = next_free_page++;
num_free_pages–;
block->id = id;
block->next = page_table[b];
for (i = 0; i < (SPARSE_PAGE_SIZE / 8); i++) block->initSet[i] = 0;
page_table[b] = block;

// Convert an emulated address into an offset
void *saddr = page_start(id);
size_t offset = (unsigned char *)addr – (unsigned char *)saddr;

#ifndef NO_CHECK_UB
// Compute the bit vector lookup for this ‘offset’
size_t offsetIdx = offset / 8;
size_t offsetBit = offset & 0x7;

// For each byte in this access, update the bitvector that tracks
// the use / initialization of emulated bytes.
for (i = 0; i < size; i++) if (isWrite) block->initSet[offsetIdx] |= (0x1 << offsetBit); else if (checkUB && (block->initSet[offsetIdx] & (0x1 << offsetBit)) == 0) // The student code has attempted to read an address that was // never written to. Students should set a breakpoint on this // line / check and then backtrace to where their code has // made the memory access. fprintf(stderr, "Attempt to read uninitialized address %p, see %s:%d for " "details\n", (addr + i), __FILE__, __LINE__); offsetBit++; if (offsetBit == 8) offsetBit = 0; offsetIdx++; if (offsetIdx == (SPARSE_PAGE_SIZE / 8)) return (void *)&block->bytes[offset];

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com