CSAPP: malloc lab 文档及解答

《深入理解计算机系统》一书的配套lab之malloc lab。学生用来实现自己的malloc, realloc和free函数。 Students implement their own versions of malloc, free, and realloc. This lab gives students a clear understanding of data layout and organization, and requires them to evaluate different trade-offs between space and time efficiency. One of our favorite labs. When students finish this one, they really understand pointers!

/* 
 * clock.c - Routines for using the cycle counters on x86 
 *           Alpha and Sparc boxes.
 * 
 * Copyright （c） 2002 R. Bryant and D. O‘Hallaron All rights reserved.
 * May not be used modified or copied without permission.
 */

#include 
#include 
#include 
#include 
#include “clock.h“


/******************************************************* 
 * Machine dependent functions 
 *
 * Note: the constants __i386__ and  __alpha
 * are set by GCC when it calls the C preprocessor
 * You can verify this for yourself using gcc -v.
 *******************************************************/

#if defined（__i386__）  
/*******************************************************
 * Pentium versions of start_counter（） and get_counter（）
 *******************************************************/


/* $begin x86cyclecounter */
/* Initialize the cycle counter */
static unsigned cyc_hi = 0;
static unsigned cyc_lo = 0;


/* Set *hi and *lo to the high and low order bits  of the cycle counter.  
   Implementation requires assembly code to use the rdtsc instruction. */
void access_counter（unsigned *hi unsigned *lo）
{
    asm（“rdtsc; movl %%edx%0; movl %%eax%1“   /* Read cycle counter */
	: “=r“ （*hi） “=r“ （*lo）                /* and move results to */
	: /* No input */                        /* the two outputs */
	: “%edx“ “%eax“）;
}

/* Record the current value of the cycle counter. */
void start_counter（）
{
    access_counter（&cyc_hi &cyc_lo）;
}

/* Return the number of cycles since the last call to start_counter. */
double get_counter（）
{
    unsigned ncyc_hi ncyc_lo;
    unsigned hi lo borrow;
    double result;

    /* Get cycle counter */
    access_counter（&ncyc_hi &ncyc_lo）;

    /* Do double precision subtraction */
    lo = ncyc_lo - cyc_lo;
    borrow = lo > ncyc_lo;
    hi = ncyc_hi - cyc_hi - borrow;
    result = （double） hi * （1 << 30） * 4 + lo;
    if （result < 0） {
	fprintf（stderr “Error: counter returns neg value: %.0f\n“ result）;
    }
    return result;
}
/* $end x86cyclecounter */

#elif defined（__alpha）

/****************************************************
 * Alpha versions of start_counter（） and get_counter（）
 ***************************************************/

/* Initialize the cycle counter */
static unsigned cyc_hi = 0;
static unsigned cyc_lo = 0;


/* Use Alpha cycle timer to compute cycles.  Then use
   measured clock speed to compute seconds 
*/

/*
 * counterRoutine is an array of Alpha instructions to access 
 * the Alpha‘s processor cycle counter. It uses the rpcc 
 * instruction to access the counter. This 64 bit register is 
 * divided into two parts. The lower 32 bits are the cycles 
 * used by the current process. The upper 32 bits are wall 
 * clock cycles. These instructions read the counter and 
 * convert the lower 32 bits into an unsigned int - this is the 
 * user space counter value.
 * NOTE: The counter has a very limited time span. With a 
 * 450MhZ clock the c