Stash version with no consistent noise in eviction test

4 files changed, 76 insertions, 59 deletions

diff --git a/kmod/cachepc.c b/kmod/cachepc.c
index 4e07f32..df8ea0e 100755
--- a/kmod/cachepc.c
+++ b/kmod/cachepc.c
@@ -284,8 +284,9 @@ remove_cache_group_set(void *ptr)
  * and D = Associativity = | cache set |
  */
 cacheline *build_cache_ds(cache_ctx *ctx, cacheline **cl_ptr_arr) {
+	cacheline **first_cl_in_sets, **last_cl_in_sets;
 	cacheline **cl_ptr_arr_sorted;
-	cacheline *curr_cl, *next_cl;
+	cacheline *curr_cl;
 	cacheline *cache_ds;
 	uint32_t *idx_per_set;
 	uint32_t idx_curr_set, set_offset;
@@ -319,17 +320,30 @@ cacheline *build_cache_ds(cache_ctx *ctx, cacheline **cl_ptr_arr) {
 
 	gen_random_indices(idx_map, ctx->sets);
 
-	curr_cl = cl_ptr_arr_sorted[idx_map[0] * set_len]->prev;
-	for (j = 0; j < ctx->sets; ++j) {
-		curr_cl->next = cl_ptr_arr_sorted[idx_map[(j + 1) % ctx->sets] * set_len];
-		next_cl = curr_cl->next->prev;
-		curr_cl->next->prev = curr_cl;
-		curr_cl = next_cl;
+	first_cl_in_sets = kzalloc(ctx->sets * sizeof(cacheline *), GFP_KERNEL);
+	BUG_ON(first_cl_in_sets == NULL);
+
+	last_cl_in_sets  = kzalloc(ctx->sets * sizeof(cacheline *), GFP_KERNEL);
+	BUG_ON(last_cl_in_sets == NULL);
+
+	for (j = 0; j < ctx->nr_of_cachelines; ++j) {
+		curr_cl = cl_ptr_arr_sorted[j];
+		if (IS_FIRST(curr_cl->flags))
+			first_cl_in_sets[curr_cl->cache_set] = curr_cl;
+		if (IS_LAST(curr_cl->flags))
+			last_cl_in_sets[curr_cl->cache_set] = curr_cl;
 	}
 
-	cache_ds = cl_ptr_arr_sorted[idx_map[0] * set_len];
+	/* connect up sets */
+	for (i = 0; i < ctx->sets; ++i) {
+		last_cl_in_sets[idx_map[i]]->next = first_cl_in_sets[idx_map[(i + 1) % ctx->sets]];
+		first_cl_in_sets[idx_map[(i + 1) % ctx->sets]]->prev = last_cl_in_sets[idx_map[i]];
+	}
+	cache_ds = first_cl_in_sets[idx_map[0]];
 
 	kfree(cl_ptr_arr_sorted);
+	kfree(first_cl_in_sets);
+	kfree(last_cl_in_sets);
 	kfree(idx_per_set);
 	kfree(idx_map);
 
@@ -361,7 +375,7 @@ void build_randomized_list_for_cache_set(cache_ctx *ctx, cacheline **cacheline_p
 			curr_cl->flags = SET_FIRST(DEFAULT_FLAGS);
 			curr_cl->prev->flags = SET_LAST(DEFAULT_FLAGS);
 		} else {
-			curr_cl->flags = curr_cl->flags | DEFAULT_FLAGS;
+			curr_cl->flags |= DEFAULT_FLAGS;
 		}
 	}
 
diff --git a/kmod/cachepc.h b/kmod/cachepc.h
index 97746ec..0e02678 100755
--- a/kmod/cachepc.h
+++ b/kmod/cachepc.h
@@ -49,16 +49,21 @@ extern cacheline *cachepc_ds;
 cacheline *
 cachepc_prime(cacheline *head)
 {
-    cacheline *curr_cl;
+	cacheline *curr_cl;
 
-    //cachepc_cpuid();
-    curr_cl = head;
-    do {
-        curr_cl = curr_cl->next;
-    } while(curr_cl != head);
-    //cachepc_cpuid();
+	cachepc_mfence();
+	cachepc_cpuid();
+	
+	curr_cl = head;
+	do {
+		curr_cl = curr_cl->next;
+	} while (curr_cl != head);
+	curr_cl = curr_cl->prev;
 
-    return curr_cl->prev;
+	cachepc_mfence();
+	cachepc_cpuid();
+
+	return curr_cl;
 }
 
 /*
@@ -78,16 +83,20 @@ cachepc_prime(cacheline *head)
 cacheline *
 cachepc_prime_rev(cacheline *head)
 {
-    cacheline *curr_cl;
+	cacheline *curr_cl;
 
-    //cachepc_cpuid();
-    curr_cl = head;
-    do {
-        curr_cl = curr_cl->prev;
-    } while(curr_cl != head);
-    //cachepc_cpuid();
+	cachepc_mfence();
+	cachepc_cpuid();
+
+	curr_cl = head;
+	do {
+		curr_cl = curr_cl->prev;
+	} while(curr_cl != head);
+
+	cachepc_mfence();
+	cachepc_cpuid();
 
-    return curr_cl->prev;
+	return curr_cl->prev;
 }
 
 cacheline *
@@ -97,6 +106,9 @@ cachepc_probe(cacheline *start_cl)
 	cacheline *next_cl;
 	cacheline *curr_cl;
 
+	cachepc_mfence();
+	cachepc_cpuid();
+
 	curr_cl = start_cl;
 
 	do {
@@ -134,21 +146,32 @@ cachepc_probe(cacheline *start_cl)
 		curr_cl = next_cl;
 	} while (__builtin_expect(curr_cl != start_cl, 1));
 
+	cachepc_mfence();
+	cachepc_cpuid();
+
 	return curr_cl->next;
 }
 
 void
 cachepc_victim(void *p)
 {
-	cachepc_cpuid();
 	cachepc_mfence();
+	cachepc_cpuid();
+
 	cachepc_readq(p);
+
+	cachepc_mfence();
+	cachepc_cpuid();
 }
 
 uint64_t
 cachepc_read_pmc(uint64_t event)
 {
 	uint32_t lo, hi;
+	uint64_t res;
+
+	cachepc_mfence();
+	cachepc_cpuid();
 
 	event = 0xC0010201 + 2 * event;
 
@@ -157,6 +180,10 @@ cachepc_read_pmc(uint64_t event)
 		: "=a" (lo), "=d" (hi)
 		: "c"(event)
 	);
+	res = ((uint64_t) hi << 32) | (uint64_t) lo;
+
+	cachepc_mfence();
+	cachepc_cpuid();
 
-	return ((uint64_t) hi << 32) | (uint64_t) lo;
+	return res;
 }
diff --git a/kmod/util.c b/kmod/util.c
index 1932c9b..de87d3b 100755
--- a/kmod/util.c
+++ b/kmod/util.c
@@ -1,41 +1,18 @@
 #include "util.h"
 
-static size_t random_pos = 0;
-static uint8_t random[] = { 90, 227, 179, 229, 27, 117, 69, 81, 188, 253, 129, 140, 140, 180, 191, 152, 194, 98, 169, 205, 254, 155, 249, 81, 208, 245, 186, 80, 81, 50, 63, 67, 200, 108, 70, 32, 239, 158, 38, 234, 183, 130, 141, 175, 39, 230, 107, 199, 59, 43, 238, 122, 103, 25, 184, 66, 31, 239, 57, 92, 119, 101, 147, 188, 171, 112, 209, 227, 92, 224, 9, 150, 220, 10, 154, 92, 86, 39, 154, 140, 65, 57, 158, 47, 142, 168, 222, 200, 69, 183, 160, 249, 103, 45, 241, 112, 49, 85, 2, 73, 255, 16, 132, 215, 190, 143, 215, 128, 119, 75, 136, 112, 67, 27, 213, 78, 127, 1, 197, 18, 122, 216, 123, 244, 11, 154, 124, 212, 171, 29, 184, 45, 42, 128, 124, 168, 112, 191, 139, 136, 20, 127, 169, 75, 220, 4, 162, 207, 80, 147, 25, 39, 232, 219, 100, 13, 199, 88, 19, 40, 141, 2, 16, 109, 40, 127, 47, 60, 221, 151, 156, 115, 182, 198, 231, 193, 36, 89, 127, 31, 187, 47, 109, 70, 75, 115, 221, 236, 46, 65, 151, 48, 185, 157, 177, 152, 134, 38, 246, 146, 15, 67, 80, 192, 74, 244, 250, 194, 21, 19, 151, 199, 124, 9, 174, 171, 239, 146, 213, 214, 226, 137, 237, 13, 92, 87, 10, 144, 21, 143, 158, 130, 129, 176, 40, 25, 247, 182, 90, 226, 14, 199, 219, 242, 52, 225, 154, 218, 242, 191, 53, 253, 36, 62, 154, 13, 145, 182, 72, 234, 140, 166, 125, 93, 236, 14, 40, 183, 48, 138, 240, 243, 100, 119, 160, 73, 182, 204, 130, 108, 80, 226, 13, 36, 118, 245, 85, 205, 131, 110, 69, 116, 130, 211, 243, 182, 180, 28, 197, 224, 245, 78, 122, 135, 194, 31, 138, 178, 194, 150, 42, 190, 7, 217, 100, 19, 161, 154, 237, 76, 135, 63, 2, 33, 229, 164, 223, 175, 0, 51, 177, 78, 13, 241, 198, 152, 109, 166, 92, 226, 42, 213, 148, 149, 144, 39, 20, 51, 239, 153, 56, 198, 190, 165, 243, 108, 66, 132, 127, 179, 182, 211, 207, 107, 223, 188, 198, 103, 147, 127, 87, 187, 137, 123, 72, 141, 156, 28, 76, 234, 244, 108, 176, 227, 221, 26, 110, 81, 28, 187, 14, 24, 82, 218, 201, 156, 20, 184, 105, 117, 188, 132, 243, 11, 13, 188, 243, 181, 98, 136, 124, 152, 254, 228, 221, 114, 140, 103, 44, 55, 147, 227, 241, 96, 198, 27, 98, 35, 179, 6, 244, 17, 152, 128, 44, 75, 8, 18, 122, 79, 244, 210, 8, 168, 99, 80, 19, 100, 38, 6, 243, 216, 200, 105, 164, 29, 171, 232, 247, 218, 17, 133, 232, 68, 140, 100, 106, 49, 17, 90, 178, 38, 69, 238, 23, 174, 180, 90, 18, 12, 71, 45, 101, 200, 83, 77, 95, 218, 91, 176, 63, 179, 203, 125, 56, 171, 218, 98, 135, 127, 214, 63, 41, 151, 197, 157, 192, 152, 67, 67, 157, 54, 123, 111, 118, 45, 94, 15, 81, 123, 125, 169, 67, 50, 150, 113, 147, 13, 16, 86, 2, 135, 129, 88, 154, 246, 170, 223, 47, 247, 190, 187, 35, 213, 194, 67, 226, 181, 208, 135, 75, 30, 233, 136, 45, 222, 121, 60, 157, 48, 171, 244, 52, 40, 187, 8, 23, 173, 41, 157, 165, 158, 92, 139, 22, 95, 72, 164, 142, 213, 156, 102, 196, 108, 228, 203, 99, 72, 254, 173, 37, 212, 150, 145, 104, 76, 117, 242, 185, 180, 108, 50, 188, 206, 40, 52, 55, 147, 240, 89, 248, 203, 110, 237, 24, 88, 63, 99, 224, 121, 229, 90, 253, 12, 72, 24, 3, 247, 127, 35, 178, 198, 80, 151, 223, 243, 195, 114, 5, 134, 250, 85, 182, 154, 206, 41, 53, 50, 59, 174, 117, 203, 200, 33, 182, 230, 147, 101, 36, 111, 23, 187, 130, 16, 211, 90, 102, 207, 154, 140, 123, 212, 66, 45, 35, 165, 139, 109, 169, 226, 210, 115, 16, 92, 196, 31, 245, 154, 110, 181, 161, 126, 184, 177, 237, 125, 181, 71, 120, 86, 222, 179, 133, 113, 72, 206, 157, 89, 162, 80, 164, 223, 38, 17, 238, 114, 188, 125, 69, 1, 28, 126, 249, 180, 189, 144, 215, 152, 89, 92, 62, 98, 151, 242, 46, 48, 162, 3, 95, 211, 122, 217, 36, 235, 109, 100, 94, 233, 173, 150, 71, 125, 201, 168, 4, 180, 248, 249, 240, 50, 206, 242, 169, 201, 31, 137, 198, 93, 241, 219, 11, 9, 1, 229, 249, 194, 67, 41, 143, 117, 103, 238, 247, 72, 178, 21, 193, 146, 119, 159, 21, 253, 206, 66, 186, 60, 200, 102, 179, 117, 103, 32, 0, 116, 31, 133, 129, 127, 38, 5, 177, 195, 25, 23, 86, 29, 222, 53, 0, 140, 179, 118, 239, 141, 237, 122, 80, 200, 92, 47, 15, 58, 167, 26, 37, 146, 254, 3, 74, 148, 159, 221, 38, 68, 110, 98, 82, 16, 171, 232, 139, 72, 87, 114, 113, 61, 210, 82, 180, 196, 8, 14, 249, 185, 159, 253, 166, 200, 82, 176, 112, 173, 246, 40, 22, 202, 140, 76, 60, 92, 225, 10, 198, 41, 26, 223, 250, 181, 135, 196, 230, 10, 103, 197, 128, 155, 148, 121, 150, 51, 196, 143, 183, 153, 229, 93, 118, 12, 235, 237, 105, 73, 27, 24, 86, 248, 39, 190, 71, 184, 212, 74, 196, 181, 46, 140, 9, 18, 168, 110, 30, 93, 166, 44, 153, 88, 82, 148, 237, 146, 173, 158, 29, 215, 202, 3, 224, 240, 186, 202, 52, 123, 244, 226, 109, 79, 174, 245, 35, 242, 82, 187, 101, 69, 245, 104, 139, 118, 134, 236, 135, 243, 10, 149, 162, 212, 245, 132, 3, 90, 38, 96, 28, 98, 200, 80, 141, 252, 40, 214, 80, 152, 221, 239, 166, 135, 104, 105, 227, 248, 102, 53, 78, 186, 95, 15, 97, 58, 129, 98, 219, 233, 167, 89, 198, 175, 98, 77, 20, 182, 112, 104, 165, 34 };
-
-void
-prng_bytes(uint8_t *dst, size_t size)
-{
-	size_t i;
-
-	if (random_pos + size > sizeof(random))
-		random_pos = 0;
-
-	for (i = 0; i < size; i++)
-		dst[i] = random[random_pos + i];
-
-	random_pos += size;
-}
-
 void
 random_perm(uint32_t *arr, uint32_t arr_len)
 {
-	uint32_t i, mid; // idx, tmp;
+	uint32_t i, mid;
 
-	/* defeat stream prefetcher by preventing access direction */
-	mid = arr_len / 2;
-	for (i = 0; i < arr_len; i++) {
-		arr[i] = mid + (i % 2 ? -1 : 1) * ((i + 1) / 2);
-	}
-
-	// for (i = arr_len - 1; i > 0; --i) {
-	// 	prng_bytes((void*)&idx, 4);
-	// 	idx = idx % i;
+	/* no special ordering needed when prefetcher is disabled */
+	for (i = 0; i < arr_len; i++)
+		arr[i] = i;
 
-	// 	tmp = arr[idx];
-	// 	arr[idx] = arr[i];
-	// 	arr[i] = tmp;
-	// }
+	// /* prevent stream prefetching by alternating access direction */
+	// mid = arr_len / 2;
+	// for (i = 0; i < arr_len; i++)
+	// 	arr[i] = mid + (i % 2 ? -1 : 1) * ((i + 1) / 2);
 }
 
 void
diff --git a/kmod/util.h b/kmod/util.h
index 7b543aa..a0ff8be 100755
--- a/kmod/util.h
+++ b/kmod/util.h
@@ -2,7 +2,6 @@
 
 #include <linux/kernel.h>
 
-void gen_rand_bytes(unsigned char *arr, uint32_t arr_len);
 void random_perm(uint32_t *arr, uint32_t arr_len);
 void gen_random_indices(uint32_t *arr, uint32_t arr_len);