//
// Pointer chasing
//
//
// Author: P.J. Drongowski
// 2 June 2013
//
// Copyright (c) 2013 Paul. J. Drongowski
//
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include "../test_common/rpi_pmu.h"
#include "../test_common/test_common.h"
#define RESULT_FILE_NAME "chase.txt"
#define TEST_ITERATIONS 8192
//
// Default values for the pointer array and the cache line size
//
#define ARRAY_ELEMENTS (16 * 1024)
#define POINTER_SIZE (sizeof(void*))
#define LINE_SIZE 32
#define POINTERS_PER_LINE (LINE_SIZE / POINTER_SIZE)
typedef struct _CacheLine
{
struct _CacheLine* ptrCacheLine[POINTERS_PER_LINE] ;
} CacheLine ;
long int array_elements = ARRAY_ELEMENTS ;
long int line_size = LINE_SIZE ;
long int pointer_size = POINTER_SIZE ;
long int pointers_per_line = POINTERS_PER_LINE ;
//
// The program allocates an array of CacheLine structures. The number
// of elements (cache lines) is determined by the variable array_elements.
// The array is initialized such that it forms a linked list of elements.
// Elements in the upper half of the array point to elements in the
// lower half, and vice versa. Thus, access will ping-pong between
// the upper and lower halves when the linked list is walked (pointers
// are chased.)
//
CacheLine* array = NULL ;
//
// The program has two phases: initialization and pointer chasing.
// The process-to-core affinity is set at the beginning of each phase.
// Windows uses a first touch physical allocation scheme, so it's
// possible to force physical allocation of the pointer array to a
// particular core and to force chasing on the same or different core.
// This should support NUMA experiments.
//
int initialization_core = 0 ; // Core (CPU) for array allocation/initialization
int chase_core = 0 ; // Core (CPU) for pointer chasing
//
// Run options (some not implemented)
//
int a_flag = 0 ; // Set core for array allocation/initialization
int c_flag = 0 ; // Measure L1 data cache events
int e_flag = 0 ; // Measure explicit external data access events
int i_flag = 0 ; // Measure instruction and cycle events
int l_flag = 0 ; // Set cache line size
int n_flag = 0 ; // Set the number of tests (iterattion count)
int p_flag = 0 ; // Set core for pointer chasing
int s_flag = 0 ; // Set array size (in units of 1024 elements)
int t_flag = 0 ; // Measure TLB events
#define OPTIONS "dhi:v" // Currently unimplemented (getopt)
char *usage_strings[] = {
" -a N Allocate/initialize array on core N",
" -c Measure L1 data cache events",
" -d Display debugging information",
" -e Measure explicit external data access events",
" -h Display usage information",
" -i Measure instruction and cycle events",
" -l N Set the cache line size to N bytes",
" -n N Set the number of tests (iteration count)",
" -p N Perform pointer chasing on core N",
" -s N Allocate an array with N * 1024 elements",
" -t Measure TLB events",
" -v Display more information (verbose output)",
NULL
} ;
//
// Allocate and initialize the test array
//
void initialize_array()
{
long int steps ; // Number of initialization setps
long int top ; // Index of top cache line
long int bottom ; // Index of bottom cache line
long int i ; // Array index counter
int j ; // Pointer index counter
if ((array = (CacheLine*) malloc(array_elements * line_size)) == NULL) {
fprintf(stderr, "Couldn't allocate test array\n") ;
exit( EXIT_FAILURE ) ;
}
//
// Set the entire array to zero.
//
for (i = 0 ; i < array_elements ; i++) {
for (j = 0 ; j < pointers_per_line ; j++) {
array[i].ptrCacheLine[j] = NULL ;
}
}
//
// The test array is divided into two halves: top and
// bottom. Set the pointers
// so that memory accesses ping-pong between the two
// halves of the array. Ping-pong between cache lines.
//
steps = array_elements / 2 ;
bottom = 0 ;
top = steps ;
for (i = 0 ; i < steps ; i++) {
array[bottom].ptrCacheLine[0] = &array[top] ;
array[top].ptrCacheLine[0] = &array[bottom+1] ;
top++ ;
bottom++ ;
}
//
// Terminate the linked list
//
array[(array_elements-1)].ptrCacheLine[0] = NULL ;
if (d_flag) {
for (i = 0 ; i < array_elements ; i++) {
// fprintf(result_file, "%16" FMT64 "x\n", array[i].ptrCacheLine[0]) ;
fprintf(result_file, "%d %8lx %8lx\n",
i, &array[i].ptrCacheLine[0], array[i].ptrCacheLine[0]) ;
}
}
}
//
// Examine the assembler code generated for test_loop_prototype
// to guide implementation of the assembly language test code
//
void test_loop_prototype(CacheLine* array)
{
CacheLine* p ;
for(p = array ; p != NULL ; p = p->ptrCacheLine[0]) ;
}
//
// Perform the test itself. Since all of the test-related
// activity starts in this function, it should be easier to
// track samples back to the test itself.
//
void run_no_events(int iteration_count)
{
int i ;
for (i = iteration_count ; i > 0 ; i--) {
test_loop_prototype(array) ;
}
}
void run_external(int iteration_count)
{
int i ;
start_counting(ARMV6_EVENT_EXPL_D_ACCESS, ARMV6_EVENT_DDEP_STALL) ;
for (i = iteration_count ; i > 0 ; i--) {
test_loop_prototype(array) ;
}
stop_counting() ;
}
void run_ipc(int iteration_count)
{
int i ;
start_counting(ARMV6_EVENT_INSTR_EXEC, ARMV6_EVENT_CPU_CYCLES) ;
for (i = iteration_count ; i > 0 ; i--) {
test_loop_prototype(array) ;
}
stop_counting() ;
}
void run_cache(int iteration_count)
{
int i ;
start_counting(ARMV6_EVENT_DCACHE_CACCESS, ARMV6_EVENT_DCACHE_MISS) ;
for (i = iteration_count ; i > 0 ; i--) {
test_loop_prototype(array) ;
}
stop_counting() ;
}
void run_tlb(int iteration_count)
{
int i ;
start_counting(ARMV6_EVENT_DTLB_MISS, ARMV6_EVENT_MAIN_TLB_MISS) ;
for (i = iteration_count ; i > 0 ; i--) {
test_loop_prototype(array) ;
}
stop_counting() ;
}
//
// Handle command line arguments, bind the process to a
// particular CPU, run the test and write the results to
// the results file.
//
int main(int argc, char *argv[])
{
int arg_count ;
pid_t my_process_id ;
float cpu_clock ;
//
// Variables to hold the run parameters. These could be
// modified by command line arguments (if command line
// parsing is ever implemented. :-)
//
int iteration_count = TEST_ITERATIONS ;
//
// Variables for measuring expired CPU cycles
//
unsigned long long int before ; // Perf counter at start of test
unsigned long long int after ; // Oerf counter at end of test
unsigned long long int total_cycles ; // Cycles consumed by test
//
// Variables for computing expected results
//
unsigned long long int total_retires ; // Total retire events
unsigned long long int total_dtlb_misses ; // Total DTLB miss events
unsigned long long int total_dc_accesses ; // Total DC access events
unsigned long long int total_dc_misses ; // Total DC miss events
unsigned long long int expected_cycle_samples ; // Expected cycle samples
unsigned long long int expected_retire_samples ; // Expected ret samples
unsigned long long int expected_dc_access_samples ; // Exp DC access samples
unsigned long long int expected_dc_miss_samples ; // Exp DC miss samples
unsigned long long int expected_dtlb_miss_samples ; // Exp DTLB miss samples
#ifdef _DEBUG
d_flag = 1 ;
#endif
// Parse any command line arguments. Use simple one character
// option names preceded by a '-' character.
for (arg_count = 1 ; arg_count < argc ; arg_count++)
{
if( argv[arg_count][0] == '-' )
{
switch( argv[arg_count][1] )
{
case 'a' :
{
// Set processor core for array allocation and initialization
fprintf(stderr, "*warning* -a is UNIMPLEMENTED\n") ;
a_flag = 1 ;
arg_count++ ;
if (arg_count < argc)
{
initialization_core = atoi(argv[arg_count]) ;
}
break ;
}
case 'c' :
{
// Measure L1 data cache (DC) events
c_flag = 1 ;
break ;
}
case 'd' :
{
// Enable debug output
d_flag = 1 ;
break ;
}
case 'e' :
{
// Measure explicit external data access events
e_flag = 1 ;
break ;
}
case 'h' :
{
// Display usage information
display_usage_info(argv[0], usage_strings) ;
h_flag = 1 ;
break ;
}
case 'i' :
{
// Measure instructions per cycle (IPC)
i_flag = 1 ;
break ;
}
case 'l' :
{
// Set cache line size to N bytes
l_flag = 1 ;
arg_count++ ;
if (arg_count < argc)
{
line_size = LINE_SIZE ;
// line_size = atoi(argv[arg_count]) ;
// pointers_per_line = (line_size / pointer_size) ;
}
break ;
}
case 'n' :
{
// Set iteration count (number of tests)
n_flag = 1 ;
arg_count++ ;
if (arg_count < argc)
{
iteration_count = atoi(argv[arg_count]) ;
}
break ;
}
case 'p' :
{
// Set processor core for pointer chasing
fprintf(stderr, "*warning* -p is UNIMPLEMENTED\n") ;
p_flag = 1 ;
arg_count++ ;
if (arg_count < argc)
{
chase_core = atoi(argv[arg_count]) ;
}
break ;
}
case 's' :
{
// Set array size to N elements
s_flag = 1 ;
arg_count++ ;
if (arg_count < argc)
{
long int elements = ARRAY_ELEMENTS ;
elements = atoi(argv[arg_count]) ;
array_elements = elements ;
}
break ;
}
case 't' :
{
// Measure translation lookaside buffer (TLB) events
t_flag = 1 ;
break ;
}
case 'v' :
{
v_flag = 1 ;
break ;
}
default:
{
printf("Illegal option: %c\n", argv[arg_count][1]) ;
break ;
}
}
}
}
// Get ID of current process and CPU clock speed
my_process_id = getpid() ;
cpu_clock = 1000000.0f * (float)get_cpu_speed() ;
if (create_result_file(RESULT_FILE_NAME) == 0) {
exit( EXIT_FAILURE ) ;
}
// Allocate and initialize the pointer chasing array
initialize_array() ;
// Snap performance counter and TOD at start of test run
before = getTimeStamp() ;
// Perform pointer chasing
if (c_flag) {
run_cache(iteration_count) ;
} else if (e_flag) {
run_external(iteration_count) ;
} else if (i_flag) {
run_ipc(iteration_count) ;
} else if (t_flag) {
run_tlb(iteration_count) ;
} else {
run_no_events(iteration_count) ;
}
// Snap performance counter after the test loop
after = getTimeStamp() ;
total_cycles = after - before ;
if (d_flag) {
printf("*debug* Before: %16" FMT64 "d\n", before) ;
printf("*debug* After: %16" FMT64 "d\n", after) ;
}
// Display estimated results
print_heading("Pointer chasing test") ;
print_system_info() ;
fprintf(result_file,"Run information\n") ;
fprintf(result_file," PID: %16d\n", my_process_id) ;
fprintf(result_file," Allocation core: %16d\n", initialization_core) ;
fprintf(result_file," Chase core: %16d\n", chase_core) ;
fprintf(result_file," CPU clock speed (GHz): %16.4f\n", (float)(cpu_clock / 1000000000.0)) ;
fprintf(result_file," Number of test iterations: %16d\n", iteration_count) ;
fprintf(result_file," Array elements/cache lines: %16d\n", array_elements) ;
fprintf(result_file," Array size/bytes: %16d\n", array_elements * line_size) ;
fprintf(result_file," Cache line size: %16d\n", line_size) ;
fprintf(result_file," Pointer size: %16d\n", pointer_size) ;
fprintf(result_file," Pointers per line: %16d\n", pointers_per_line) ;
if (c_flag || e_flag || i_flag || t_flag) {
fprintf(result_file,"Performance Monitor events\n") ;
print_counts(result_file) ;
}
fprintf(result_file, "Run execution summary\n") ;
print_process_times() ;
print_elapsed_time() ;
close_result_file() ;
return( EXIT_SUCCESS ) ;
}
