Subversion Repositories Code-Repo

#!/usr/bin/python

#

# Check that build and output of threadpool exercise match expected output

#

# Written for CS3214 Fall 2009 by G. Back (godmar@gmail.com)

# Last Updated Fall 2011

#

import re, os, sys, subprocess, operator, signal

exe = "./threadpool_test"

helgrind = ["/home/courses/cs3214/valgrind-3.7.0-install/bin/valgrind", "--tool=helgrind"]

print "Checking correctness of threadpool exercise."

print "Compiling..."

if os.system("make clean " + exe):

    raise Exception("make failed, run 'make clean " + exe + "' to see why")

if not os.access(exe, os.X_OK):

    raise Exception(exe + " did not build")

print "Ok."

hex = "[0-9A-Fa-f]{8,16}"

print "Checking that threadpool.o does not use global variables...",

allowedsymbols = [ "future_free", "future_get", \

                   "thread_pool_new", "thread_pool_shutdown", 

                   "thread_pool_submit" ] 

symbols = subprocess.Popen(["nm", "threadpool.o"], stdout=subprocess.PIPE)\

    .communicate()[0].split("\n")

for sym in symbols:

    if sym == "" or re.match("\s+U (\S+)", sym):

        continue

    m = re.match(hex + " (\S) (\S+)", sym)

    if not m:

        raise Exception("unexpected line in nm:\n" + sym)

    if m.group(1) == "t":

        continue

    # ignore symbols produced by 'assert()'

    if m.group(1) == "r" and m.group(2).startswith("__PRETTY_FUNCTION__"):

        continue

    if m.group(1) == "T":

        if m.group(2) in allowedsymbols:

            continue

        raise Exception("threadpool.o defines global function '" + m.group(2) 

                        + "'\nallowed functions are: " + str(allowedsymbols));

    raise Exception("threadpool.o must not define any global or "

                    + "static variables, but you define: " + m.group(2))

print "Ok."

# test scenarios (#threads, #tasks)

threads2tasks = [ (4, 4), (4, 2), (4, 1), \

                  (4, 8), (4, 12), \

                  (2, 2), (2, 4), (2, 8), \

                  (1, 2), (1, 4), (1, 8), \

                  (3, 1), (3, 2), (3, 3), (3, 4), (3, 5) \

                ]

for (threads, tasks) in threads2tasks:

    print "Testing", threads, "threads and", tasks, "tasks"

    sp = subprocess.Popen([exe, str(threads), str(tasks)],

                           stdout=subprocess.PIPE)

    output = sp.communicate()[0]

    if sp.returncode < 0:

        signames = dict((k, v) for v, k in signal.__dict__.iteritems() if v.startswith('SIG'))

        signum = -sp.returncode

        raise Exception("Program terminated with signal %d (%s)\n" % (signum, signames[signum]))

    match = re.match("Main thread: 0x("+hex+")\n(.*)\n"\

        "Done\.", output, re.MULTILINE | re.DOTALL)

    if not match:

        raise Exception("Output did not match expected format:\n" + output)

    mainthread = match.group(1)

    futures = []

    for future in match.group(2).split("\n"):

        m = re.match("Future #(\d+) Thread #0x("+hex+") "\

                 "start=(\d+)\.(\d+) end=(\d+)\.(\d+)", future)

        if not m:

            raise Exception("Future did not match expected format:\n" + future)

        futures.append((m.group(1), m.group(2), 

            float(m.group(3)) + float(m.group(4)) / 1e6,

            float(m.group(5)) + float(m.group(6)) / 1e6))

    # print futures

    # consistency checks

    # Futures should be printed in increasing order

    print "Checking correct order of futures...",

    # all is available only in Python 2.5 and up

    def all(l):

        return reduce(lambda x, y: x and y, l, True)

    if not all([ int(futures[i][0]) < int(futures[i+1][0]) \

                for i in range(len(futures)-1) ]):

        raise Exception("Futures are out of order:\n" + output)

    print "Ok."

    print "Checking that correct number of threads were used...",

    threadsused = len(set([ f[1] for f in futures ] + [ mainthread ]))

    threadsexpected = min(threads, tasks) + 1

    if threadsexpected != threadsused:

        raise Exception("Thread pool used " + str(threadsused) 

            + " distinct threads including the main thread, should have used " 

            + str(threadsexpected) + ":\n" + output)

    print "Ok."

    # each pair within each 'threads'-sized chunk of tasks 

    # should have executed in parallel.

    print "Checking tasks were executed in parallel...",

    def inparallel((start0, end0), (start1, end1)):

        return start1 < end0 and start0 < end1

    def allpairs(l):

        return reduce(operator.add, [ [(l[i], e) for e in l[i+1:]] \

                                      for i in range(len(l)-1) ], [])

    for i in range(0, len(futures), threads):

        for (f1, f2) in allpairs(futures[i:i+threads]):

            if not inparallel(f1[2:4], f2[2:4]):

                raise Exception("Future #" + f1[0] + " and #" + f2[0] 

                              + " did not run in parallel:\n" + output)

    print "Ok."

print "You have met minimum requirements.\n"

print "Now checking for race conditions using helgrind"

for (threads, tasks) in threads2tasks:

    cmd = helgrind + [exe, str(threads), str(tasks)]

    print "Running", " ".join(cmd), "...",

    sp = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE)

    stderr = sp.communicate()[1]

    if not re.search("ERROR SUMMARY: 0 errors from 0 contexts", stderr):

        raise Exception("Your program contains race conditions:\n" + stderr)

    print "Ok."

print "Congratulations, you've passed the race condition checker tests.\n"

print "Testing whether your thread pool implementation runs Quicksort"

quicksort = "quicksort"

if os.system("make clean " + quicksort):

    print "make failed, run 'make clean " + quicksort + "' to see why"

    sys.exit(1)

sp = subprocess.Popen("./quicksort -q -s 1 1000000".split(" "), stdout=subprocess.PIPE, stderr=subprocess.PIPE)

stdout = sp.communicate()[0]

if not re.search("Processed 14 segments of sizes: 6316 19753 62328 62520 68838 82083 104576 141938 152189 256767 325607 450365 592305 674390", stdout):

    print "Quicksort did not produce the expected result."

else:

    print "Quicksort appears to work, you can now start measuring parallel speedup."