#!/usr/bin/env python

# Some assumptions:
#   - A cache line is 64 bytes.
#   - Every thread has its own cache.
#   - Caches are infinite in size (there's always a copy of the data,
#     recent or not, in the cache).
#   - A cache line is updated locally only when accessing it and when
#     necessary (there's been a write to it from another thread since last
#     accessed).

def get_potential_lines(filename):
    linethreads = {}
    with open(filename, 'r') as trace:
        for access in trace:
            if not (access.startswith("r:") or access.startswith("w:")):
                continue
            access = access.split(':')
            if access[2] != "0":
                cacheline = int(access[2], 16) / 64
                if cacheline not in linethreads:
                    linethreads[cacheline] = set()
                linethreads[cacheline].add(access[3])

    potential_lines = []
    for cacheline, threads in linethreads.iteritems():
        if len(threads) > 1:
            potential_lines.append(cacheline)
    return potential_lines

def get_cacheline_trace(filename, cacheline):
    cacheline_trace = []
    with open(filename, 'r') as trace:
        for access in trace:
            if not (access.startswith("r:") or access.startswith("w:")):
                continue
            access = access.split(':')
            if int(access[2], 16) / 64 != cacheline:
                continue
            cacheline_trace.append({ 'type' : access[0],
                                     'field' : access[1],
                                     'offset' : int(access[2], 16) % 64,
                                     'thread' : access[3]})
    return cacheline_trace

def get_falsely_shared_writes(trace, i):
    writes = []
    j = i + 1
    while j < len(trace):
        if trace[j]['thread'] == trace[i]['thread']:
            break
        elif trace[j]['type'] == 'w':
            writes.append(j)
        j += 1
    if j == len(trace):
        return []

    falsely_shared = []
    for w in writes:
        if trace[w]['offset'] != trace[j]['offset']:
            falsely_shared.append(w)

    return falsely_shared

def is_true_sharing(trace, i):
    if trace[i]['type'] != 'w':
        return False

    j = i + 1
    while j < len(trace):
        if trace[j]['offset'] == trace[i]['offset']:
            if trace[j]['type'] == 'w':
                return False
            elif trace[j]['thread'] != trace[i]['thread']:
                return True
        j += 1

    return False

if __name__ == '__main__':
    tracefile = "trace.txt"
    false_sharing = {}
    for line in get_potential_lines(tracefile):
        trace = get_cacheline_trace(tracefile, line)
        for i in range(len(trace)):
            fs_fields = []
            for j in get_falsely_shared_writes(trace, i):
                if is_true_sharing(trace, j):
                    continue

                # This avoids reporting false sharing for each write to a
                # same field between two accesses by another thread.
                if trace[j]['field'] in fs_fields:
                    continue
                fs_fields.append(trace[j]['field'])

                if trace[j]['field'] not in false_sharing:
                    false_sharing[trace[j]['field']] = 1
                false_sharing[trace[j]['field']] += 1
    print "Number of times false sharing occured per field:"
    for field, count in false_sharing.iteritems():
        print "\t%s: %d" % (field, count)