/************************************************************************************
 *
 *                  Micro Benchmark   mbtlb
 *              --------------------------------
 *
 * Filename : mbtlb.c
 * Author   : Yuanhua Yu
 * Date     : 20/12/1999
 *-----------------------------------------------------------------------------
 *
 * Purpose  : This micro-benchmark is used to measure the key parameters of
 *            the TLB such as size, associativity using a sequential access
 *            sequence of pages without repeatition.
 *
 * Methods  : 1. determined_indexing:
 *               the offset inside the accessed pages is sequential from 0.
 *               the offset is computed by:
 *                   i*stride_block+mod(subblock_size*i, stride_block)]
 *               where mod(x,y) = x - y*int(x/y)
 *
 *            2. random_offset:
 *               the offset inside the accessed pages is a random number between
 *               0 and stride_block.
 *               the offset is determined by:
 *                   (long)stride_block*((double)rand()/RAND_MAX))
 *            
 *            3. random_index but determinated offset
 *
 *            4. random_index and offset
 * 
 * History   :First version date to  10/08/1999
 *            Second version date to 12/10/1999
 *            Third version date to  10/12/1999
 *
 * Parameters:arr_size     :  size of the accessed array
 *	          num_pages    :  number of the pages in the accessed array
 *            page_size    :  size of the virtual memory page (assummed)
 *            stride_block :  size of the block in which only one item is accessed
 *                            stride is in terms of pages  
 *
 * Functions :
 *
 * 1. determined_indexing(): build up a accessed addresses sequence of pages
 *                           with sequential offset in the accessed pages.
 *
 * 2. random_offset():       build up a accessed addresses sequence of pages
 *                           with random offset in the accessed block.
 *
 * 3. random_indexing():     build up a random accessing addresses sequence of pages
 *                           with sequential offset in the accessed pages.
 *
 * 4. random_index_offset(): build up a random accessing addresses sequence of pages
 *                           with random offset in the accessed block.
 *
 * 5. set_parameters():      config parameters and store them in TLB_Config.dat
 *
 * 6. get_parameters():      get parameters from TLB_Config.dat
 *
 * 7. write_file_head():     write some given data , test date and time into
 *                           the given file.
 *
 * 8. random_sequence():     build up a random sequence
 *
 ***************************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
#include <string.h>

#define PAGESIZE_START  1024             // bytes
#define PAGESIZE_END    (1024*16)        // bytes              
#define SUBBLOCK_SIZE   32               // bytes
#define ARR_SIZE        (1024*16834*2)   // bytes
#define TOTAL_ACCESSED  (4096*4096*8)    // items in the accessed array

/*-------------------------------------------------------------------------------*/
long mod(long x, long y);

void write_file_head(FILE *fp,char mname[15],long min_page,long max_page,
					 long num_pages,long step,long subblock_size, int option);

void test(FILE *fp,long *array,long num_pages,long step,long stride_block);

void determined_index(long *array,long num_pages,long 
					  stride_block,long subblock_size);

void random_offset(long *array,long num_pages,long stride_block);

void random_index(long *array,long arr_size,long num_pages,
				  long stride_block,long subblock_size);

void random_index_offset(long *array,long arr_size,
						 long num_pages,long stride_block);

void random_sequence(long *array, long max_index);

void set_parameters(char mname[15],long *min_page,long *max_page,long *num_pages,
					long *step,long *subbock_size);

void get_parameters(char mname[15],char fname[25],long *min_page,long *max_page,
					long *num_pages,long *step,long *subbock_size);

/*------------------------------------------------------------------------------*/

int main(char **av, int ac)
{
	long	*array, arr_size, page_size, stride_block;
	long	min_page=1024, max_page=4096, num_pages=128, step=2, subblock_size=32;
	int     option;

	char	file_name[25], machine_name[15];
	FILE	*fp;

	arr_size  = ARR_SIZE/(sizeof(long));     /* number of elements in array    */
	array = (long *)calloc(arr_size, sizeof(long));

	option = 1;
	while(option >=0 && option <6)
	{
	      printf("\n---------- Measuring Parameters of TLB ------------------\n\n");
          printf("        0: All of the test\n");
	      printf("        1: Sequential indexing with incremented offset\n");
          printf("        2: Sequential indexing with random offset\n");
	      printf("        3: Random indexing with incremented offset\n");
	      printf("        4: Random indexing with random offset\n");
		  printf("        5: Set parameters\n");
		  printf("        6: Exit\n");
	      printf("\n---------------------------------------------------------\n");
	      printf("     Option (0-6): ");
	      scanf("%d",&option);
        
	      if(option ==5)
	      {
              set_parameters(machine_name,&min_page,&max_page, 
				             &num_pages,&step, &subblock_size);
			  continue;
	      }

		  get_parameters(machine_name,file_name, &min_page,&max_page, 
				   &num_pages, &step, &subblock_size);	

		  fp = fopen(file_name,"a+");
	      if(fp == NULL)
	      {
		     perror("Error: Can't open file !");
		     exit(1);
	      }
	        
	      subblock_size = subblock_size / sizeof(long); 
		  if (option ==1 || option == 0)
	      {
	          write_file_head(fp,machine_name, min_page,max_page, num_pages, 
				                 step, subblock_size*sizeof(long),  1);
              for(page_size=min_page; page_size<=max_page; page_size*=2)
		      {
		          stride_block = page_size/sizeof(long);  
	              determined_index(array, num_pages, stride_block, subblock_size);
                  test(fp, array, num_pages, step, stride_block);
	          }
		  }

	      if (option ==2 || option == 0)
	      {
	          write_file_head(fp,machine_name, min_page,max_page, num_pages, 
				                 step, subblock_size*sizeof(long),  2);
	          for(page_size=min_page; page_size<=max_page; page_size*=2)
		      {
		          stride_block = page_size/sizeof(long);  
	              random_offset(array, num_pages, stride_block);
                  test(fp, array, num_pages, step, stride_block);
			  }
	      }
		
	      if (option ==3 || option == 0)
	      {
	          write_file_head(fp,machine_name, min_page,max_page, num_pages, 
				                 step, subblock_size*sizeof(long),  3);
	          for(page_size=min_page; page_size<=max_page; page_size*=2)
		      {
		          stride_block = page_size/sizeof(long);  
	              random_index(array, arr_size, num_pages,stride_block,subblock_size);
                  test(fp, array, num_pages, step, stride_block);
			  }
	      }
	   
	      if (option ==4 || option == 0)
	      {
	          write_file_head(fp,machine_name, min_page,max_page, num_pages, 
				                 step, subblock_size*sizeof(long),  4);
	          for(page_size=min_page; page_size<=max_page; page_size*=2)
		      {
		          stride_block = page_size/sizeof(long);  
	              random_index_offset(array, arr_size, num_pages, stride_block);
                  test(fp, array, num_pages, step, stride_block);
			  }
		  }

	}
          
	free(array);
	fclose(fp);

    return 1;
}



long mod(long x, long y)
{
    return (x - y*(int)(x/y));
}


void test(FILE *fp,long *array, long num_pages, long step, long stride_block)
/*---------------------------------------------------------------------------*/
/* Function:  measuring the TLB using the given accessing sequence           */
/*---------------------------------------------------------------------------*/

{
	long    i, j, k;
	double	time_cost_total, time_cost_per_op;
	unsigned long start_time, stop_time;
	
    printf("Pages size(bytes) = :  %d\n",stride_block*sizeof(long));
    fprintf(fp,"Assummed pages size(bytes)= :  %d\n",stride_block*sizeof(long));

	/*--------------------------------------------------------Test Start---*/
	for (k = num_pages; k>0; k = k-step)
	{
		i=array[0];
		for(j=1; j< k-1; j++)     /* Build the accessed-page circle */
	        i=array[i];
		array[i]=0;

		start_time=clock();       /* -------------------Start the clock tick */
		i=array[0];
		for (j=0;j<TOTAL_ACCESSED/16;j++)
		{
		     i=array[i];i=array[i];i=array[i];	i=array[i];
		     i=array[i];i=array[i];i=array[i];	i=array[i];
		     i=array[i];i=array[i];i=array[i];	i=array[i];
		     i=array[i];i=array[i];i=array[i];	i=array[i];
		}
		stop_time=clock();        /* --------------------Stop the clock tick */
		j = i;                    /* avoid to be optimized away              */

		time_cost_total =(double)(stop_time-start_time)/(double)CLOCKS_PER_SEC;
		time_cost_per_op=(double)(1000000000.0/TOTAL_ACCESSED*time_cost_total);

		printf("%12d %10.3f %10.3f %10d\n",k,time_cost_total,time_cost_per_op,j);
		fprintf(fp,"%10d %10.3f\n",k,time_cost_per_op);

	}
	/*----------------------------------------------------------Test End---*/
    fprintf(fp,"\n\n");
    return;
}


void set_parameters(char mname[15],long *min_page,long *max_page,long *num_pages,
					long *step,long *subblock_size)
/*----------------------------------------------------------------------------*/
/* Function:  Config the needed parameters from keyboard and                  */
/*            form a name for the data file and save the them                 */
/*            in the TLB_Config.data       .                                  */
/*----------------------------------------------------------------------------*/
{
	char	fname[25];
	FILE	*fp;

    printf("                    Input The Machine Name: ");
    scanf("%s",mname);
    printf("        Input the minimum page size(bytes): ");
    scanf("%d",min_page);
    printf("        Input the maximum page size(bytes): ");
    scanf("%d",max_page);
    printf("      Input number of pages to be accessed: ");
    scanf("%d", num_pages);
    printf("                    Input the step (pages): ");
    scanf("%d", step);
    printf("Input the subblock size of L1 cache(bytes): ");
    scanf("%d", subblock_size);

    strcpy(fname,"TLB_");
    strcat(fname,mname);
    strcat(fname,".dat");

 	fp = fopen("TLB_Config.dat","w");
	if(fp == NULL)
	{
		perror("Error: Can't open file !");
		exit(1);
	}
    fprintf(fp,"%s\n",mname);
    fprintf(fp,"%s\n",fname);
	fprintf(fp,"%d %d %d %d %d\n",
		       *min_page,*max_page,*num_pages,*step,*subblock_size);

    fclose(fp);
    return;
}


void get_parameters(char mname[15],char fname[25],long *min_page,long *max_page,
					long *num_pages,long *step,long *subblock_size)
/*---------------------------------------------------------------------------*/
/* Function:  get the parameters needed from file TLB_Config.dat             */
/*---------------------------------------------------------------------------*/
{
	FILE *fp;

 	fp = fopen("TLB_Config.dat","r");
	if(fp == NULL)
	{
		perror("Error: Can't open file !");
		exit(1);
	}
    fscanf(fp,"%s\n",mname);
    fscanf(fp,"%s\n",fname);
	fscanf(fp,"%d %d %d %d %d\n",
		       min_page,max_page,num_pages,step,subblock_size);

	fclose(fp);
    return;
}



void write_file_head(FILE *fp,char mname[15],long min_page,long max_page,
					 long num_pages,long step,long subblock_size, int option)
/*------------------------------------------------------------------------*/
/* Function:  write the given parameters and the time, date               */
/*            into the data file.                                         */
/*------------------------------------------------------------------------*/
{
     time_t tm;
     char time_buf[255];

     time(&tm);
     strcpy(time_buf, ctime(&tm));

     printf("\n---------------------------------------------------------\n");
     printf("\n  Number(pages) Total_T(s)   Access_T(ns) ------ i \n");

     fprintf(fp,"--------------  Measurement of TLB  -----------------\n");
     fprintf(fp,"         Manchine name :  %s\n", mname);
	 fprintf(fp,"  Min-page size (bytes):  %d\n", min_page);
	 fprintf(fp,"  Max-page size (bytes):  %d\n", max_page);
	 fprintf(fp,"Number of pages (pages):  %d\n", num_pages);
     fprintf(fp,"  Subblock size (bytes):  %d\n", subblock_size);
     fprintf(fp,"           Step (pages):  %d\n", step );
     fprintf(fp,"  Test date :  %s",   time_buf );

     if(option == 1)
        fprintf(fp,"      Method : 1. Sequential indexing with incremented offset\n");
     else if(option ==2)
	    fprintf(fp,"      Method : 2. Sequential indexing with random offset\n");
     else if (option == 3)
	    fprintf(fp,"      Method : 3. Random indexing with incremented offset\n");
     else if (option == 4)
	    fprintf(fp,"      Method : 4. Random indexing with random offset\n");
     else ;

     fprintf(fp,"-----------------------------------------------------\n");

     fprintf(fp,"Number(pages) Total_T(s)   Access_T(ns)\n");

}


void determined_index(long *array,long num_pages,long stride_block,long subblock_size)
/*--------------------------------------------------------------------------------*/
/* Function:  build up a accessed addresses sequence of pages                     */
/*            with sequential offset in the accessed pages.                       */
/*--------------------------------------------------------------------------------*/
{
	long i, index, offset1, offset2, tmp;
   
	offset1=0;
	for(i=0;i<num_pages-1;i++)
	{
        tmp = (i+1)*subblock_size;
        offset2 =  tmp - stride_block * (long)(tmp/stride_block);
        index = i*stride_block+offset1;
		array[index] = (i+1)*stride_block + offset2;
		offset1 = offset2;
	}
	array[(num_pages-1)*stride_block+offset1] = 0;

}

void random_offset(long *array, long num_pages, long stride_block)
/*-----------------------------------------------------------------------*/
/* Function: *  build up a accessed addresses sequence of pages          */
/*              with random offset in the accessed block.                */
/*           *  subblock_size is not needed in this case.                  */
/*-----------------------------------------------------------------------*/
{
	long i, index, offset1, offset2;
	 	     
	offset1=0;
	for(i=0;i<(num_pages-1)*stride_block;i=i+stride_block)
	{
	    offset2 = (long) ( ( (double)( stride_block)*rand() ) / RAND_MAX ) ;
	    index = i + offset1;
	    array[index] = i + stride_block + offset2;
	    offset1 = offset2;
	}
	array[(num_pages-1)*stride_block+offset1] = 0;
      
    return;
}


void random_index(long *array,long arr_size,long num_pages,
				              long stride_block,long subblock_size)
/*-----------------------------------------------------------------------*/
/* Function: *  build up a randm accessing addresses sequence of pages   */
/*              with different offset in the accessed block.             */
/*           *  subblock_size is needed in this case.                      */
/*-----------------------------------------------------------------------*/
{	
    long i,index, block_no, offset, tmp;
       
	for(i=0; i<arr_size; i++) array[i] = 0;

	index = 0; offset = 0;	
	for(i=1; i<num_pages; i++)
	{	
        for(;;)
        {	
	        block_no = stride_block*(long)(((double)(num_pages)*rand())/RAND_MAX);
	        offset= block_no/stride_block-stride_block
                             *(long)(block_no/stride_block/stride_block);
            offset= mod( offset*subblock_size, stride_block);
		
	        tmp = block_no + offset;
	        if( tmp==0 || tmp==index || array[tmp]>0 )	
	        {
                continue;
	        }
	        else
	        {
	            array[index] = tmp;	
                index = tmp;	
                break;
	        }
        }
    }
    return;
}


void random_index_offset(long *array, long arr_size, long num_pages, long stride_block)
/*-----------------------------------------------------------------------------------*/
/* Function: *  build up a randm accessing addresses sequence of pages               */
/*              with random offset in the accessed block.                            */
/*           *  subblock_size is not needed in this case.                              */
/*-----------------------------------------------------------------------------------*/
{	
    long i, index, block_no, offset, tmp, *flag;
    FILE *fp;
    
	fp = fopen("sss","w");
       
    flag = (long *) calloc(num_pages, sizeof(long));

	for(i=0; i<arr_size; i++) array[i] = 0;
        for(i=0; i<num_pages;i++) flag[i] = 0;

	index = 0; 
	offset = 0;	
	for(i=1; i<num_pages; i++)
	{	
        for (;;)
        {	
	        block_no = (long)( ( (double)(num_pages)*rand()) / RAND_MAX );
	        offset =   (long)( ( (double)(stride_block)*rand()) / RAND_MAX );
		
            tmp = block_no*stride_block + offset;
	
	        if (tmp==0 || tmp==i || flag[block_no] > 0 )	
	        {
                continue;
	        }
	        else
	        {
	            fprintf(fp,"%d\n", tmp);
	            array[index] = tmp;
                flag[block_no] = 1;	
                index = tmp;	
                break;
            }
	    }
	}
	fclose(fp);
    return;
}

void random_sequence(long *array, long max_index)
/*-----------------------------------------------------------------------------*/
/* Function: *  build up a random accessing addresses sequence                 */
/*-----------------------------------------------------------------------------*/
{	
    long i, index, block_no;
	FILE *fp;
	
	fp = fopen("sss","w");
       
	for(i=0; i<max_index; i++) array[i]=0;

	index = 0;
	for(i=1; i<max_index; i++)
	{	
        for(;;)
	    {	
		    block_no = (long)( ( (double)(max_index)*rand()) / RAND_MAX );
		    if( block_no==0 || block_no==index || array[block_no]>0
				                               || block_no >= max_index)	
		    {
                continue;
		    }
		    else
		    {
	            fprintf(fp,"%d\n", block_no);
                array[index] = block_no;	
                index = block_no;	
                break;
		    }
	    }
	}
	fclose(fp);
    return;
}