summaryrefslogtreecommitdiffstats
path: root/dis/original/random_walk.c
diff options
context:
space:
mode:
Diffstat (limited to 'dis/original/random_walk.c')
-rw-r--r--dis/original/random_walk.c550
1 files changed, 550 insertions, 0 deletions
diff --git a/dis/original/random_walk.c b/dis/original/random_walk.c
new file mode 100644
index 0000000..9f907bb
--- /dev/null
+++ b/dis/original/random_walk.c
@@ -0,0 +1,550 @@
1#include <sys/time.h>
2#include <sys/mman.h>
3
4#include <stdio.h>
5#include <stdlib.h>
6#include <unistd.h>
7#include <time.h>
8#include <string.h>
9#include <inttypes.h>
10#include <assert.h>
11#include <limits.h>
12#include <fcntl.h>
13#include <errno.h>
14/*
15#include "litmus.h"
16#include "common.h"
17*/
18/* CPU time consumed so far in seconds */
19double cputime(void)
20{
21 struct timespec ts;
22 int err;
23 err = clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
24 if (err != 0)
25 perror("clock_gettime");
26 return (ts.tv_sec + 1E-9 * ts.tv_nsec);
27}
28
29/* wall-clock time in seconds */
30double wctime(void)
31{
32 struct timeval tv;
33 gettimeofday(&tv, NULL);
34 return (tv.tv_sec + 1E-6 * tv.tv_usec);
35}
36
37void bail_out(const char* msg)
38{
39 perror(msg);
40 exit(-1 * errno);
41}
42
43#include "extra.h"
44
45#define PAGE_SIZE (4096)
46#define CACHELINE_SIZE 64
47#define INTS_IN_CACHELINE (CACHELINE_SIZE/sizeof(int))
48#define CACHELINES_IN_1KB (1024 / sizeof(cacheline_t))
49#define INTS_IN_1KB (1024 / sizeof(int))
50
51typedef struct cacheline
52{
53 int line[INTS_IN_CACHELINE];
54} __attribute__((aligned(CACHELINE_SIZE))) cacheline_t;
55
56static volatile cacheline_t* arena = NULL;
57
58#define UNCACHE_DEV "/dev/litmus/uncache"
59#define FAKE_DEV "/dev/litmus/fakedev0"
60
61static cacheline_t* alloc_arena(size_t size, int use_huge_pages, int use_uncache_pages)
62{
63 int flags = MAP_PRIVATE | MAP_POPULATE;
64 cacheline_t* arena = NULL;
65 int fd;
66
67 if(use_huge_pages)
68 flags |= MAP_HUGETLB;
69
70 if(use_uncache_pages == 1) {
71 fd = open(UNCACHE_DEV, O_RDWR|O_SYNC);
72 if (fd == -1)
73 bail_out("Failed to open uncache device. Are you running the LITMUS^RT kernel?");
74 } else if (use_uncache_pages == 2) {
75 fd = open(FAKE_DEV, O_RDWR|O_SYNC);
76 if (fd == -1)
77 bail_out("Failed to open fake device. Are you running the LITMUS^RT kernel?");
78 } else {
79 fd = -1;
80 flags |= MAP_ANONYMOUS;
81 }
82
83 arena = (cacheline_t*)mmap(0, size, PROT_READ | PROT_WRITE, flags, fd, 0);
84
85 if(use_uncache_pages)
86 close(fd);
87
88 assert(arena);
89
90 return arena;
91}
92
93static void dealloc_arena(cacheline_t* arena, size_t size)
94{
95 int ret = munmap((void*)arena, size);
96 if(ret != 0)
97 bail_out("munmap() error");
98}
99
100static int randrange(int min, int max)
101{
102 // Range is [min, max)
103 assert(max - min - 1 <= RAND_MAX);
104 return rand() % (max - min) + min;
105 //return (rand() % (max - min + 1)) + min;
106 /* generate a random number on the range [min, max) w/o skew */
107 /*int limit = max - min;
108 int devisor = RAND_MAX/limit;
109 int retval;
110
111 do {
112 retval = rand() / devisor;
113 } while(retval == limit);
114 retval += min;
115
116 return retval;*/
117}
118
119static void init_arena(volatile cacheline_t* arena, size_t size)
120{
121 int i;
122 size_t num_arena_elem = size / sizeof(cacheline_t);
123
124 /* Generate a cycle among the cache lines using Sattolo's algorithm.
125 Every int in the cache line points to the same cache line.
126 Note: Sequential walk doesn't care about these values. */
127 for (i = 0; i < num_arena_elem; i++) {
128 int j;
129 for(j = 0; j < INTS_IN_CACHELINE; j++)
130 arena[i].line[j] = i;
131 arena[i].line[1] = 0;
132 }
133 /*while(1 < i--) {
134 int j = randrange(0, i);
135 cacheline_t temp = arena[j];
136 arena[j] = arena[i];
137 arena[i] = temp;
138 }*/
139 for (int j = 0; j < num_arena_elem-1; j++) {
140 int k = randrange(j+1, num_arena_elem);
141 cacheline_t temp = arena[j];
142 arena[j] = arena[k];
143 arena[k] = temp;
144 }
145}
146
147/* Random walk around the arena in cacheline-sized chunks.
148 Cacheline-sized chucks ensures the same utilization of each
149 hit line as sequential read. (Otherwise, our utilization
150 would only be 1/INTS_IN_CACHELINE.) */
151static int random_walk(volatile cacheline_t *mem, int wss, int write_cycle)
152{
153 /* a random cycle among the cache lines was set up by init_arena(). */
154 int sum, i, next;
155
156 // Always do the same number of hops
157 int numlines = 33554432 / CACHELINE_SIZE;//wss * CACHELINES_IN_1KB;
158
159 sum = 0;
160
161 /* contents of arena is structured s.t. offsets are all
162 w.r.t. to start of arena, so compute the initial offset */
163 next = mem - arena;
164
165 if (write_cycle == 0) {
166 for (i = 0; i < numlines; i++) {
167 next = arena[next].line[0];
168 arena[next].line[1] = 1; // Record that we touched this line
169 sum += next;
170 for (int j = 2; j < INTS_IN_CACHELINE; j++)
171 arena[next].line[j]++;
172 }
173 } else {
174 int w, which_line;
175 for (i = 0, w = 0; i < numlines; i++) {
176 which_line = next;
177 next = arena[next].line[0];
178 if((w % write_cycle) != (write_cycle - 1)) { // This is equivalent to 1 % 1 != 1 - 1 which is always false
179 sum += next;
180 }
181 else {
182 // I /think/ that this just writes back to the address it read from
183 arena[which_line].line[0] = next;
184 }
185 }
186 }
187 return sum;
188}
189
190volatile static cacheline_t* random_start(int wss)
191{
192 return arena + randrange(0, ((wss * 1024)/sizeof(cacheline_t)));
193}
194/*
195static int sequential_walk(cacheline_t *_mem, int wss, int write_cycle)
196{
197 int sum = 0, i;
198 int* mem = (int*)_mem; // treat as raw buffer of ints
199 int num_ints = wss * INTS_IN_1KB;
200
201 if (write_cycle > 0) {
202 for (i = 0; i < num_ints; i++) {
203 if (i % write_cycle == (write_cycle - 1))
204 mem[i]++;
205 else
206 sum += mem[i];
207 }
208 } else {