Merge into master from pull request #135:
Replace flowtable/gentable checksum XOR operations with add/subtract (https://github.com/floodlight/oftest/pull/135)
diff --git a/tests-1.3/bsn_flow_checksum.py b/tests-1.3/bsn_flow_checksum.py
index 26f40e9..2a21e68 100644
--- a/tests-1.3/bsn_flow_checksum.py
+++ b/tests-1.3/bsn_flow_checksum.py
@@ -29,6 +29,32 @@
random.shuffle(l)
return l
+def add_checksum(a, b):
+ return (a + b) % 2**64
+
+def subtract_checksum(a, b):
+ return (a - b) % 2**64
+
+def bucket_index(num_buckets, checksum):
+ """
+ Use the top bits of the checksum to select a bucket index
+ """
+ return checksum >> (64 - int(math.log(num_buckets, 2)))
+
+def add_bucket_checksum(buckets, checksum):
+ """
+ Add the checksum to the correct bucket
+ """
+ index = bucket_index(len(buckets), checksum)
+ buckets[index] = add_checksum(buckets[index], checksum)
+
+def subtract_bucket_checksum(buckets, checksum):
+ """
+ Subtract the checksum from the correct bucket
+ """
+ index = bucket_index(len(buckets), checksum)
+ buckets[index] = subtract_checksum(buckets[index], checksum)
+
class FlowChecksumBase(base_tests.SimpleProtocol):
"""
Base class that maintains the expected table and bucket checksums
@@ -52,17 +78,14 @@
self.assertEquals(self.get_table_checksum(), self.table_checksum)
self.assertEquals(self.get_checksum_buckets(), self.checksum_buckets)
- def update_checksums(self, checksum):
- self.table_checksum ^= checksum
- checksum_shift = 64 - int(math.log(len(self.checksum_buckets), 2))
- self.checksum_buckets[checksum >> checksum_shift] ^= checksum
-
def insert_checksum(self, checksum):
- self.update_checksums(checksum)
+ self.table_checksum = add_checksum(self.table_checksum, checksum)
+ add_bucket_checksum(self.checksum_buckets, checksum)
self.all_checksums.append(checksum)
def remove_checksum(self, checksum):
- self.update_checksums(checksum)
+ self.table_checksum = subtract_checksum(self.table_checksum, checksum)
+ subtract_bucket_checksum(self.checksum_buckets, checksum)
self.all_checksums.remove(checksum)
def set_buckets_size(self, buckets_size):
@@ -72,10 +95,12 @@
do_barrier(self.controller)
verify_no_errors(self.controller)
+ old_checksums = self.all_checksums
+ self.all_checksums = []
self.checksum_buckets = [0] * buckets_size
self.table_checksum = 0
- for checksum in self.all_checksums:
- self.update_checksums(checksum)
+ for checksum in old_checksums:
+ self.insert_checksum(checksum)
class FlowChecksum(FlowChecksumBase):
"""
diff --git a/tests-1.3/bsn_gentable.py b/tests-1.3/bsn_gentable.py
index 915729c..4c2fc8a 100644
--- a/tests-1.3/bsn_gentable.py
+++ b/tests-1.3/bsn_gentable.py
@@ -31,6 +31,32 @@
assert make_checksum(0xab, 0xcd) == 0xab0000000000000000000000000000cd
+def add_checksum(a, b):
+ return (a + b) % 2**128
+
+def subtract_checksum(a, b):
+ return (a - b) % 2**128
+
+def bucket_index(num_buckets, checksum):
+ """
+ Use the top bits of the checksum to select a bucket index
+ """
+ return checksum >> (128 - int(math.log(num_buckets, 2)))
+
+def add_bucket_checksum(buckets, checksum):
+ """
+ Add the checksum to the correct bucket
+ """
+ index = bucket_index(len(buckets), checksum)
+ buckets[index] = add_checksum(buckets[index], checksum)
+
+def subtract_bucket_checksum(buckets, checksum):
+ """
+ Subtract the checksum from the correct bucket
+ """
+ index = bucket_index(len(buckets), checksum)
+ buckets[index] = subtract_checksum(buckets[index], checksum)
+
class BaseGenTableTest(base_tests.SimpleProtocol):
def setUp(self):
base_tests.SimpleProtocol.setUp(self)
@@ -443,7 +469,7 @@
# Add a bunch of entries, spread among the checksum buckets
for i in range(0, 256):
- table_checksum ^= make_checksum(i, i*31)
+ table_checksum = add_checksum(table_checksum, make_checksum(i, i*31))
self.do_add(vlan_vid=i, ipv4=0x12345678, mac=(0, 1, 2, 3, 4, i),
checksum=make_checksum(i, i*31))
@@ -456,8 +482,8 @@
# Modify an entry, changing its checksum
i = 30
- table_checksum ^= make_checksum(i, i*31) # subtract old checksum
- table_checksum ^= make_checksum(i, i*37) # add new checksum
+ table_checksum = subtract_checksum(table_checksum, make_checksum(i, i*31)) # subtract old checksum
+ table_checksum = add_checksum(table_checksum, make_checksum(i, i*37)) # add new checksum
self.do_add(vlan_vid=i, ipv4=0x12345678, mac=(0, 4, 3, 2, 1, i),
checksum=make_checksum(i, i*37))
@@ -470,7 +496,7 @@
# Delete an entry
i = 87
- table_checksum ^= make_checksum(i, i*31)
+ table_checksum = subtract_checksum(table_checksum, make_checksum(i, i*31))
self.do_delete(vlan_vid=i, ipv4=0x12345678)
do_barrier(self.controller)
@@ -492,15 +518,10 @@
self.assertEquals(entry.checksum, 0)
buckets = [0] * len(entries)
- checksum_bits = int(math.log(len(buckets), 2))
-
- def update_bucket(checksum):
- index = checksum >> (128 - checksum_bits)
- buckets[index] ^= checksum
# Add a bunch of entries, spread among the checksum buckets
for i in range(0, 256):
- update_bucket(make_checksum(i, i*31))
+ add_bucket_checksum(buckets, make_checksum(i, i*31))
self.do_add(vlan_vid=i, ipv4=0x12345678, mac=(0, 1, 2, 3, 4, i),
checksum=make_checksum(i, i*31))
@@ -511,8 +532,8 @@
# Modify an entry, changing its checksum
i = 30
- update_bucket(make_checksum(i, i*31)) # subtract old checksum
- update_bucket(make_checksum(i, i*37)) # add new checksum
+ subtract_bucket_checksum(buckets, make_checksum(i, i*31)) # subtract old checksum
+ add_bucket_checksum(buckets, make_checksum(i, i*37)) # add new checksum
self.do_add(vlan_vid=i, ipv4=0x12345678, mac=(0, 4, 3, 2, 1, i),
checksum=make_checksum(i, i*37))
@@ -526,7 +547,7 @@
# Delete an entry
i = 87
- update_bucket(make_checksum(i, i*31))
+ subtract_bucket_checksum(buckets, make_checksum(i, i*31))
self.do_delete(vlan_vid=i, ipv4=0x12345678)
do_barrier(self.controller)
@@ -580,15 +601,13 @@
buckets32 = [0] * 32
buckets64 = [0] * 64
- def update_bucket(checksum):
- buckets32[checksum >> (128 - int(math.log(32, 2)))] ^= checksum
- buckets64[checksum >> (128 - int(math.log(64, 2)))] ^= checksum
-
# Add a bunch of entries, spread among the checksum buckets
for i in range(0, 256):
- update_bucket(make_checksum(i, i*31))
+ checksum = make_checksum(i, i*31)
+ add_bucket_checksum(buckets32, checksum)
+ add_bucket_checksum(buckets64, checksum)
self.do_add(vlan_vid=i, ipv4=0x12345678, mac=(0, 1, 2, 3, 4, i),
- checksum=make_checksum(i, i*31))
+ checksum=checksum)
entries = self.do_bucket_stats()
self.assertEquals(len(entries), 64)