# sim161.py
#
# A sys161 and os161 emulation library in Python
# We emulate a subset of the thread and sync primitives in OS161
# so we can play with algorithms, and use the provided deadlock detection
# algorithm to assist debugging.
#
# We implement deadlock detection on Semaphores and Locks, but no on
# condition variables.

# Import python modules
import thread
import threading
import sys

# The deadlock detection algorithm
import deadlock

# Some constants
SPL_HIGH = 1  # Binary interrupt in this code

S_SLEEP  = 0  # Thread states we implement
S_READY  = 1

### SYS161 Simulation State

## Emulate interrupts with a (recursive) python Lock
interrupt_lock = None

### OS161 Simulation State

curspl = 0       # SPL level. Have to be careful with this
sleepers = []    # List of sleepers, indexed by object


### Other state

# A list of all threads, indexed by python internal tid
# Necessary for curthread() implementation below
threadpool = {}

### Helper functions

# Return a reference to the current thread
# This is a global in OS161, but we cannot replicate that here
# Any OS161 code that uses `curthread' should use `curthread'
# in sim161.
def curthread():
    return threadpool[ thread.get_ident() ]

# Panic and quit
def panic( msg ):
    print msg
    exit(1)

###
#
# OS161-like functions
#
###

## Interrupt Handling
# We need to allow recursive interrupt disables
# but at the same time we want to always be able to turn them on
# in one go...
def interrupts_off():
    interrupt_lock.acquire()
    
def interrupts_on():
    # This is a bit of a hack
    interrupt_lock._release_save()
    #interrupt_lock.release()

# We sleep by waiting on our semaphore
def md_switch( t ):

    # We have to turn on interrupts!
    spl = splx(0);
    
    # Sleep us!
    t.make_waiting()

    # Now we're back we can coninue
    # Start by setting interrupts
    splx(spl)

# from schedule.c - add a thread to the run queue
def make_runnable( t ):
    
    # meant to be called with interrupts off
    assert( curspl > 0 )

    # Make that thread runnable
    t.make_runnable()
    
    return 0
 
## Thread 'switching' code
def mi_switch( nextstate ):
    
    assert( curspl > 0 )

    cur = curthread()
         
    # Stash the current thread on whatever list it's supposed to go on.
    if( nextstate == S_READY ):
        result = make_runnable(cur)
    elif( nextstate == S_SLEEP ):
        result = array_add(sleepers, cur)
    else:
        assert( nextstate==S_ZOMB )
        panic( "Thread exit not implemented!" )
        
    # We don't need to call a scheduler - our OS does this for you
        
    # Call the machine-dependent code that actually does the
    # context switch.
    md_switch( cur )


## SPL handling - see the MIPS manual and OS161 code
# splx - modify interrupts
def splx( newspl ):

    global curspl   # icky python syntax

    # Turn interrupts off first, if we need to
    if( newspl > 0 ):
        interrupts_off()
        
    oldspl = curspl
    curspl = newspl

    # We can now turn interrupts on safely
    # We need slightly different code than os161 because without
    # real interrupts we have exposed a race that did not exist in os161
    if( newspl == 0 ):
        interrupts_on()

    return oldspl
    
# splhigh - disable interrupts
def splhigh():
    return splx(SPL_HIGH)

###
#
# OS161-like array functions
#
# Simulate arrays with python lists
# These are identical to the OS161 equivalent
#
###

def array_getnum( a ):
    return len(a)

def array_getguy( a, index ):
    return a[index]

def array_add( a, guy ):
    a.append( guy )

def array_remove( a, index ):
    del a[index]

###
#
# OS161-like Thread implementation
#
###

# OS161 has a big thread struct. This is just a pseudo
# version that will work
#
# We use a class to manage the thread because it maps nicely onto the
# Python thread model.
class Thread161( threading.Thread ):
    def __init__(self, group=None, target=None, \
                 name=None, args=None, kwargs={} ):
        threading.Thread.__init__( self, group=group,
                                   target=self.thread_startup,
                                   name=name, args=args, kwargs=kwargs )
        # Make the system more crash friendly
        self.setDaemon(1)

        # What to call on start
        self.target = target

        ## Configure the actual thread object
        # What we're sleeping on
        self.t_sleepaddr = None

        # our name
        self.t_name = name
        
        # We can't manipulate run queues directly, since we're not the OS
        # so we use a semaphore to sleep
        # Create with 0 so the first V sleeps
        self.sleep_sem = threading.Semaphore(0)

        # Add ourself to the thread pool

        # Now start running
        self.start()

    # Startup function so we can add ourself to the thread pool
    def thread_startup( self, arg=None ):
        # Add this thread to the pool
        threadpool[ thread.get_ident() ] = self

        # Call the actual function
        self.target( arg )


    # 'switch_from' - sleep on our semaphore
    # Equivalent of taking us out of the run queue
    def make_waiting( self ):
        self.sleep_sem.acquire()  # P

    # 'switch_from' - sleep on our semaphore
    # Equivalent of adding us to of the run queue
    def make_runnable( self ):
        self.sleep_sem.release()  # V

# os161 has a very complex thread_fork primitive
# This one is just easier to implement, and does what we need
# Creates a thread named `name', at functions `func' with a single
# argument `arg'.
def thread_create( name, func, arg ):

    # Keep track of it in the deadlock algorithm!
    deadlock.add_process( name )

    # Create us a thread descriptor object
    thread = Thread161( name=name, target=func, args=(arg,) )

    return thread

# Cause all threads sleeping on the specified object to wake up.
# Interrupts must be disabled.
#
# void thread_wakeup(const void *addr);

def thread_wakeup( addr ):
    
    # meant to be called with interrupts off
    assert( curspl > 0 )

    # python does loops differently to C. We need to track the number
    # of items removed.
    remcount = 0

    # This is inefficient. Feel free to improve it.
    for i in range( 0, array_getnum(sleepers) ):
        t = array_getguy( sleepers, i - remcount );
        if (t.t_sleepaddr == addr ):
            # Remove from list
            array_remove(sleepers, i - remcount);
                        
            # must look at the same sleepers[i] again
            remcount += 1;

            # Because we preallocate during thread_fork,
            # this should never fail.
            result = make_runnable(t)
            assert( result == 0 )


# Wake up *at most* one thread who is sleeping on "sleep address"
# ADDR.
#
# void thread_wakeone(const void *addr)

def thread_wakeone( addr ):
	
    # meant to be called with interrupts off
    assert( curspl > 0 )
	
    # This is inefficient. Feel free to improve it.
    for i in range( 0, array_getnum( sleepers ) ):
        t = array_getguy( sleepers, i )
        if( t.t_sleepaddr == addr ):
			
            # Remove from list
            array_remove( sleepers, i )
			
            result = make_runnable( t )
            assert( result == 0 )

            # got one, we're done
            break


# Yield the cpu to another process, and go to sleep, on "sleep
# address" ADDR. Subsequent calls to thread_wakeup with the same
# value of ADDR will make the thread runnable again. The address is
# not interpreted. Typically it's the address of a synchronization
# primitive or data structure.
#
# Note that (1) interrupts must be off (if they aren't, you can
# end up sleeping forever), and (2) you cannot sleep in an 
# interrupt handler.
#
# void thread_sleep(const void *addr)

def thread_sleep( addr ):
        curthread().t_sleepaddr = addr
        mi_switch( S_SLEEP )
        curthread().t_sleepaddr = None


###
#
# OS161-like Semaphore implementation
#
###

# Python class like the C struct
# struct semaphore {
#         char *name;
#         volatile int count;
# };

# Python equivalent of 'struct semaphore'
# We use a different name to avoid confusion with python semaphores :)
class Sem161:
    # This gets configured dynamically by sem_create
    # Members from os161:
    #   name:  the name of this semaphore
    #   count: current value of the semaphore
    pass

# sem_create: Create a semaphore (duh)
# C-decl:
# struct semaphore * sem_create(const char *namearg, int initial_count)
def sem_create( namearg, initial_count ):

    # Create the semaphore
    sem = Sem161()

    # Configure it
    sem.name = namearg
    sem.count = initial_count

    # Make sure we track the resouce in the deadlock algorithm
    deadlock.add_resource( namearg, initial_count )

    return sem

# P - wait on a semaphore
# See os161 source, textbook, lecture notes, google for more details
# C-decl:
# void              P(struct semaphore *);
def P( sem ):
    # disable 'interrupts'
    spl = splhigh()

    # Sleep on the semaphore, and check when we wake up
    while( sem.count == 0 ):
        # At this point we know we're about to go to sleep
        # Which could mean deadlock if our algorithm is wrong
        deadlock.acquire_resource_wait( curthread().t_name, sem.name )

        # Actually go to sleep
        thread_sleep(sem)

        # We are no longer waiting on the resource
        deadlock.release_resource_wait( curthread().t_name, sem.name )
        
    # Actually mark it as taken
    deadlock.acquire_resource( curthread().t_name, sem.name )
        
    # Sanity check the semaphore count
    assert( sem.count > 0 )

    # Now we can decrement
    sem.count -= 1

    # Re-enable 'interrupts'
    splx(spl)

# V - signal a semaphore
# See os161 source, textbook, lecture notes, google for more details
# C-decl:
# void              V(struct semaphore *);
def V( sem ):

    # disable 'interrupts'
    spl = splhigh()

    # Increment the count
    sem.count += 1

    # Let the algorithm tracking know we're done
    deadlock.release_resource( curthread().t_name, sem.name )
        
    # Sanity check the count
    assert( sem.count > 0 )

    # Wakeup any sleeping threads
    thread_wakeup(sem)

    # Re-enable 'interrupts'
    splx( spl )


###
#
# OS161-like Lock implementation
#
###

# Python equivalent of 'struct lock'
# We use a different name to avoid confusion with python locks
class Lock161:
    # This gets configured dynamically by lock_create
    # Members from os161:
    #   name:  the name of this lock
    #   holder: the holder of this lock
    pass

# struct lock * lock_create(const char *name)
def lock_create( name ):

    # Create a new lock
    lock = Lock161()

    # Set name
    lock.name = name

    # Set the lock to `None' - python equivalent of NULL
    lock.holder = None

    # Make sure we track the resouce in the deadlock algorithm
    deadlock.add_resource( name, 1 )

    return lock

# void lock_acquire(struct lock *lock)
def lock_acquire( lock ):

    # Turn off interrupts so we can work atomically. 
    spl = splhigh()

    # If we already hold the lock, it's bad.
    # We don't need this check because we have fancier deadlock
    # detection in this system
    #if( lock_do_i_hold(lock) ):
    #    panic("lock_acquire: lock %s: Deadlock.\n" % lock.name )

    # Wait for it to become free.
    while( lock.holder != None  ):
        # Check if we will deadlock if we sleep
        deadlock.acquire_resource_wait( curthread().t_name, lock.name )
        thread_sleep(lock)
        deadlock.release_resource_wait( curthread().t_name, lock.name )

    # We will actually get it
    deadlock.acquire_resource( curthread().t_name, lock.name )
    
    # Now acquire it for ourselves.
    lock.holder = curthread()

    # Return interrupts to previous level.
    splx(spl)

# void lock_release(struct lock *lock)
def lock_release( lock ):
    # Turn off interrupts.
    spl = splhigh()
    
    # Must hold the lock to be allowed to release it.
    if( lock.holder != curthread() ):
        panic("lock_release: lock %s: Not holder.\n" % lock.name )

    # Release the resource
    deadlock.release_resource( curthread().t_name, lock.name )
    
    # Release the lock.
    lock.holder = None

    # By waking up everyone on the lock, we allow the scheduler
    # to make priority-based decisions about who runs next
    # (avoiding priority inversion).  This is worth the overhead
    # of all threads who don't acquire the lock waking up and
    # immediately going back to sleep.
    thread_wakeup(lock);

    # Return interrupts to previous level.
    splx( spl )

# int lock_do_i_hold(struct lock *lock)
def lock_do_i_hold( lock ):
    
    # Turn off interrupts.
    spl = splhigh()

    # Yay for unreadable code
    ret = (lock.holder == curthread())
    
    # Return interrupts to previous level.
    splx(spl)

    return ret

###
#
# OS161-like Condition Variable implementation
#
###

#struct cv {
#	char *name;
#	// nothing else needed here
#};

# Python equivalent of 'struct cv'
# We use a different name to avoid confusion with python locks
class CV161:
    # This gets configured dynamically by cv_create
    # Members from os161:
    #   name:  the name of this cv
    pass

# struct cv * cv_create(const char *name)
def cv_create( name ):

    # Allocate the CV object
    cv = CV161()

    # Set the name
    cv.name = name

    return cv


# void cv_wait(struct cv *cv, struct lock *lock)
def cv_wait( cv, lock ):
	
    # Turn off interrupts.
    spl = splhigh()

    # Must hold before waiting
    # Don't need to check this, because lock_release does.
    # assert(lock_do_i_hold(lock));

    # Let go of the lock.
    lock_release(lock)

    # Sleep until someone signals or broadcasts on the CV.
    thread_sleep(cv)
    
    # Get the lock back.
    lock_acquire(lock)
	
    # Return interrupts to previous level.
    splx(spl)


# void cv_signal(struct cv *cv, struct lock *lock)
def cv_signal( cv, lock ):

    # Turn off interrupts.
    spl = splhigh()

    # Must hold the lock to signal.
    if( not lock_do_i_hold( lock ) ) :
        panic( "cv_signal: cv %s, lock %s : Not holder.\n" \
               % (cv.name, lock.name) )

    # Just wake one thread up.
    thread_wakeone( cv )

    # Return interrupts to previous level.
    splx( spl )

# void cv_broadcast(struct cv *cv, struct lock *lock)
def cv_broadcast( cv, lock ):
    # Turn off interrupts.
    spl = splhigh()

    # Must hold the lock to broadcast.
    if( not lock_do_i_hold(lock) ):
        panic( "cv_broadcast: cv %s, lock %s: Not holder.\n" % \
		      cv.name, lock.name )

    # Wake 'em all.
    thread_wakeup( cv )

    # Return interrupts to previous level.
    splx(spl)


##
#
# Exit support functions
#
# Python seems to be a bit uncooperative to do with exiting and CTRL+C
# when we have multiple threads. This is a HACK. The correct way to do it
# involves using signals
#
##

# The exit lock
exit_val = 0

# Exit the emulaor
def exit( code ):
    global exit_val
    exit_val = 1
    sys.exit( code )

# Wait until the emulator exits
# Unfortunately if we want to be able to CTRL+C our running program nicely
# we need to spin in this function. Obviously this is very bad design.
def wait_for_exit():
    while( exit_val == 0 ):
        pass

##
#
# Module setup code
#
##

# Called when we import this module
if __name__ == "sim161":
    print "Initialising sim161 module"

    # Setup OS161 Emulation
    # We need a recursive lock to emulate interrupts.
    interrupt_lock = threading.RLock()

    # make the deadlock module call our exit function
    deadlock.exit = exit
