#####################################################################
# CS:APP Malloc Lab
# Handout files for students
#
# Copyright (c) 2002, R. Bryant and D. O'Hallaron, All rights reserved.
# May not be used, modified, or copied without permission.
#
######################################################################

***********
Main Files:
***********

mm.{c,h}	
	Your solution malloc package. mm.c is the file that you
	will be handing in, and is the only file you should modify.

mdriver.c	
	The malloc driver that tests your mm.c file

short{1,2}-bal.rep
	Two tiny tracefiles to help you get started. 

Makefile	
	Builds the driver

**********************************
Other support files for the driver
**********************************

config.h     Configures the malloc lab driver
fsecs.{c,h}  Wrapper function for the different timer packages
clock.{c,h}  Routines for accessing the Pentium and Alpha cycle counters
fcyc.{c,h}   Timer functions based on cycle counters
ftimer.{c,h} Timer functions based on interval timers and gettimeofday()
memlib.{c,h} Models the heap and sbrk function

*******************************
Building and running the driver
*******************************
To build the driver, type "make" to the shell.

To run the driver on a tiny test trace:

	unix> mdriver -V -f short1-bal.rep

The -V option prints out helpful tracing and summary information.

To get a list of the driver flags:

	unix> mdriver -h

********************************
The performance index
********************************

The performance index (pindex) is a linear combination of space
utilization and throughput. It is computed as

	p1 = UTIL_WEIGHT * avg_mm_util;
	if (avg_mm_throughput > AVG_LIBC_THRUPUT) {
	    p2 = (double)(1.0 - UTIL_WEIGHT);
	} 
	else {
	    p2 = ((double) (1.0 - UTIL_WEIGHT)) * 
		(avg_mm_throughput/AVG_LIBC_THRUPUT);
	}
	pindex = (p1 + p2)*100.0;
	
- UTIL_WEIGHT and AVG_LIBC_THRUPUT are defined in config.h. Change
them according to taste.

- UTIL_WEIGHT is a value between 0 and 1 that gives the contribution
of space utilization (UTIL_WEIGHT) and throughput (1-UTIL_WEIGHT) to
the performance index. Through trial and error we have found that a
UTIL_WEIGHT of around 0.6 works well; optimizing too much for speed at
the expense of space utilization leads to rather stupid
implmentations. A higher value of UTIL_WEIGHT tends to discourage
this, with the result that more intelligent implementations get better
scores.

- AVG_LIBC_THRUPUT is an estimate of the througput of the libc malloc
on your system. Its only purpose is to cap the contribution of
throughput to the performance index. Once the students surpass the
AVG_LIBC_THRUPUT, they get no further benefit to their score.  This
deters students from building extremely fast, but extremely stupid
malloc packages. We use a constant here rather than a measured value
to make the index more stable.

- avg_mm_util is the average measured space utilization of the
student's malloc package.  The idea is to remember the high water mark
"hwm" of the heap for an optimal allocator, i.e., where the heap has
no gaps and no internal fragmentation.  Utilization then is the ratio
hwm/heapsize, where heapsize is the size of the heap in bytes after
running the student's malloc package on the trace. Note that our
implementation of mem_sbrk() doesn't allow the students to decrement
the brk pointer, so brk is always the high water mark of the heap.

- avg_mm_throughput is the average measured throughput (ops/second) of
the student's malloc package on all of the traces.

********************************
Example solutions
********************************

For each solution, we give a brief description and (as a sanity check)
its performance index on a gcc/Linux/Pentium III system.

mm-naive.c	
	The simplest solution.  Malloc simply sbrk's and writes
	a size header. Free does nothing. Realloc is implemented
	directly with malloc and free. This solution has great
	throughput but terrible space utilization, and thus fails on
	many traces because it exhausts memory. This is the solution
	that is given to the students initially.

	Perf index: None, because some of the traces fail when the
	mm_malloc and mm_realloc run out of memory.

mm-implicit.c	
	Solution based on implicit free list. Simple implicit free
	list w/boundary tag coaelescing. This is the simplest
	"reasonable" package. It is described in detail in the CS:APP
	book. Can be compiled to do either first fit or next fit.

	Perf index (first fit) = 44 (util) + 1 (thru) = 45/100
	Perf index (next fit) = 44 (util) + 1 (thru) = 44/100

mm-test.c	
	A buggy malloc that produces overlapping blocks. Used for
	testing the driver.

mm.{c,h}
	This is the file that is linked into the driver. In the src/
	directory, it is always a symbolic link to one the solutions
	described above. The makefile has rules for installing the
	different versions. For example, "make naive" will install
	mm-naive as the	default by creating a symbolic link from it
	to mm.c:

	unix> rm -f mm.c mm.o; ln -s mm-naive.c mm.c

******************
Platform issues
******************

The driver and the various solutions (mm-xxx.c) have been tested on
Linux/Pentium and Solaris/Sparc systems, using gcc 2.95.2.

A lot of old Sparc systems out there don't have cycle counters. So we
didn't include cycle counter routines for the Sparc like we did for
the Pentium and Alpha. If you are using Solaris machines, you can add
your own Sparc cycle counter routines to clock.c, or you can select a
more portable timing mechanism such as interval timers or gettimeofday
by editing the config.h file.