Jon's FOSS Blog

Anything networking, coding, crypto, or security

[really long code post warning] Studying more concepts related to computer science in general

The code being posted (again with no comments or promise of correctness, sorry!), contains examples of problems associated with programming, mostly threading related, as you can see below. A basic description of each one:

  • search.py – A simple implementation of a Basic Regular Expression (a Deterministic Finite State Machine) which should match a pattern and string
  • webbot.py – A simple HTTP GET script which uses various authentication methods: Basic, Digest, Cookies, and SSL
  • deadlock.py – A thread based example of the “deadlock” problem where 2 threads attempt to perform 2 related actions in reverse order of each other and obtain the locks in a staggered fashion such that they both are now waiting for each other to finish first before proceeding.
    • Example: Thread1 wants to transfer money from Bob to Charlie & Thread2 wants to transfer money from Charlie to Bob. Thread1 first gets a lock on Bob’s account & Thread2 at the same time gets a lock on Charlie’s account. Now Thread1 is waiting to get a lock on Charlie’s account & Thread2 is waiting to get a lock on Bob’s account but they both can’t until one of them releases a lock.
  • livelock.py – A thread based example of the “livelock” problem where 2 threads attempt to perform the same reversed action as above but instead attempt to release their own locks at the same time and then wait for the other to grab their lock for the same amount of time and then re-lock at the same time again causing an infinite loop to occur again.
  • semaphore.py – The lock scenarios above are examples of binary “semaphores” so this is a thread based example of a counting “semaphore”. The implementation is an example where a library has 10 rooms to offer students, however, the front desk only keeps a count of the number of rooms free when a person enters or leaves a room. If no rooms are available, the thread is blocked and added to a simple First In First Out queue waiting for the room count to become positive again.
  • monitor.py – This script is also based on the bank money transfer analogy as above except that it uses a real thread locking mechanism for both withdrawal and deposit actions to prevent both threads from performing different actions at the same time.
  • mutex.py – This script demonstrates both an example of a problem and a “monitor” locking solution for when 2 threads attempt to remove adjacent items (i & i+1) in a Linked-List at the same time. Basically, Thread1 removing i will point i-1 at i+1 when Thread2 is trying to remove i+1 at the same time therefore allowing it to still exist afterwards.

 

search.py

#!/usr/bin/python
import os
import sys
def search(pattern, instr):
	allchars = []
	for x in range(0, 256):
		allchars.append(chr(x))
	# compile: [notflag, charset, numtimes, indexlist]
	# numtimes: {0:"0", 1:"1", ..., -1:"0 or 1", -2:"0 or more"}
	clist = []; clen = 0
	try:
		pidx = 0; plen = len(pattern)
		while (pidx < plen):
			pchar = pattern[pidx]
			if (pchar == "."):
				clist.append([0, allchars, 1, []]); clen += 1
			elif (pchar == "?"):
				clist[clen - 1][2] = -1
			elif (pchar == "*"):
				clist[clen - 1][2] = -2
			elif (pchar == "["):
				notflag = -1; charlist = []
				while (pidx < plen):
					pidx += 1; pchar = pattern[pidx]
					if ((notflag == -1) and (pchar == "^")):
						notflag = 1
					elif (pchar == "]"):
						break
					elif (pchar == "-"):
						for a in range(ord(pattern[pidx - 1]) + 1, ord(pattern[pidx + 1])):
							charlist.append(chr(a))
					else:
						charlist.append(pchar)
				if (notflag == -1):
					notflag = 0
				clist.append([notflag, charlist, 1, []]); clen += 1
			else:
				clist.append([0, [pchar], 1, []]); clen += 1
			pidx += 1
	except:
		return False
	#print(instr, pattern, clist)
	# search
	cidx = 0
	iidx = 0; ilen = len(instr)
	while ((cidx < clen) and (iidx < ilen)):
		#print(cidx,clist[cidx],iidx,instr[iidx])
		inchr = instr[iidx]
		match = (inchr in clist[cidx][1])
		if (clist[cidx][0] == 1):
			match = (not match)
		# match processing
		if (match):
			# if we matched
			# store this related input index and check the next input character (greedy)
			clist[cidx][3].append(iidx); iidx += 1
			if ((clist[cidx][2] == 1) or (clist[cidx][2] == -1)):
				# if this regex match count is ("1" OR "0 or 1") then try the next regex item for matches
				cidx += 1
		else:
			# if we did not match
			if ((clist[cidx][2] == -1) or (clist[cidx][2] == -2)):
				# if the regex match count is ("0 or 1" OR "0 or more") then try the next regex item for matches
				cidx += 1
			elif (len(clist[cidx][3]) > 0):
				# if this regex already has some matched input then try the next regex item for matches
				cidx += 1
			else:
				# last resort check to see if we can roll back to a past (greedy) regex match
				while (1):
					tidx = max(cidx - 1, 0)
					if (len(clist[tidx][3]) > 0):
						# if we found a past (greedy) regex match then use that past input index for this regex and check from there
						iidx = clist[tidx][3].pop()
						break
					cidx = tidx
					if (cidx < 1):
						# if we have gone back to the first regex then move the input index forward (search)
						iidx += 1
						break
	if (cidx >= clen):
		return True
	return False
def main():
	for line in sys.stdin.readlines():
		line = line.rstrip()
		if (search(sys.argv[1], line)):
			print(line)
if (__name__ == "__main__"):
	main()

webbot.py

#!/usr/bin/python

import base64
import hashlib
import os
import random
import ssl
import socket
import sys
import time

def parse_headers(httpresp):
	httphead = {}
	
	for httpline in httpresp.split("\n"):
		httpline = httpline.strip()
		if (not httpline):
			break
		headlist = httpline.split(":", 1)
		if (len(headlist) != 2):
			continue
		httphead[headlist[0].lower()] = headlist[1].strip()
	
	if ("www-authenticate" in httphead.keys()):
		httpauth = {}
		authlist = httphead["www-authenticate"].split(" ", 1)
		httpauth["type"] = authlist[0]
		flag = 0; keyn = ""; temp = ""
		for achr in authlist[1]:
			if (achr == '='):
				keyn = temp; temp = ""
				flag = 1
			elif ((achr == "'") or (achr == '"')):
				if (flag == 1):
					temp = ""
				if (flag == 2):
					httpauth[keyn] = temp; temp = ""
				flag += 1
			elif (achr == ','):
				if (temp != ""):
					httpauth[keyn] = temp; temp = ""
				flag = 3
			elif ((flag != 2) and (achr == ' ')):
				pass
			else:
				temp += achr
		if (temp != ""):
			httpauth[keyn] = temp; temp = ""
		httphead["www-auth"] = httpauth
	
	return httphead

def main():
	print("[Basic Auth]");print("")
	
	hostname = "httpbin.org"
	filename = "/basic-auth/baseuser/basepass"
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("baseuser:basepass")))
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[Digest Auth]");print("")
	
	username = ("dig%duser%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
	password = ("dig%dpass%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
	hostname = "httpbin.org"
	filename = ("/digest-auth/auth/%s/%s" % (username, password))
	
	authhead = ""
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	nc = "00000001"; cn = "13377331"
	hao = hashlib.md5(username + ":" + headlist["www-auth"]["realm"] + ":" + password).hexdigest()
	hat = hashlib.md5("GET" + ":" + filename).hexdigest()
	har = hashlib.md5(hao + ":" + headlist["www-auth"]["nonce"] + ":" + nc + ":" + cn + ":" + "auth" + ":" + hat).hexdigest()
	
	authhead = ("Authorization: Digest username=\"%s\", realm=\"%s\", nonce=\"%s\", uri=\"%s\", qop=auth, nc=%s, cnonce=\"%s\", response=\"%s\", opaque=\"%s\"\r\n" % (username, headlist["www-auth"]["realm"], headlist["www-auth"]["nonce"], filename, nc, cn, har, headlist["www-auth"]["opaque"]))
	cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[Cookie Auth]");print("")
	
	hostname = "www.httpwatch.com"
	filename = "/httpgallery/authentication/authenticatedimage/default.aspx"
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:abcd")))
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:efgh")))
	cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[SSL Auth]");print("")
	
	hostname = "www.google.ca"
	filename = "/images/srpr/logo11w.png"
	
	authhead = ""
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sslsocko = ssl.wrap_socket(sockobjc)
	sslsocko.connect((hostname, 443))
	sslsocko.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sslsocko.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)

if (__name__ == "__main__"):
	main()

deadlock.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount):
		self.lock = 0
		self.exit = 0
		self.balance = amount
	
	def withdraw(self, amount):
		self.balance -= amount
	
	def deposit(self, amount):
		self.balance += amount
	
	def sync(self):
		while (self.lock == 1):
			if (self.exit == 1):
				print("deadlock exit triggered")
				sys.exit(0)
			time.sleep(0.5)
		self.lock = 1
		print("got lock on",self)
	
	def release(self):
		self.lock = 0
	
	def transfer(self, Accto, amount):
		self.sync()
		Accto.sync()
		
		self.withdraw(amount)
		Accto.deposit(amount)
		
		Accto.release()
		self.release()
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
		print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
		print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())

bank = {"bob":Account(100), "charlie":Account(200)}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1

livelock.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount):
		self.lock = 0
		self.exit = 0
		self.balance = amount
	
	def withdraw(self, amount):
		self.balance -= amount
	
	def deposit(self, amount):
		self.balance += amount
	
	def setlocks(self, linked):
		self.lock = 1
		waittime = 0.01
		print("setlocks started")
		while (1):
			if (linked.lock != 1):
				break
			if (self.exit == 1):
				print("livelock exit triggered")
				sys.exit(0)
			time.sleep(waittime)
			self.lock = 0
			time.sleep(waittime)
			self.lock = 1
			time.sleep(waittime)
		linked.lock = 1
	
	def dellocks(self, linked):
		linked.lock = 0
		self.lock = 0
	
	def transfer(self, Accto, amount):
		self.setlocks(Accto)
		
		self.withdraw(amount)
		Accto.deposit(amount)
		
		self.dellocks(Accto)
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
		print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
		print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())

bank = {"bob":Account(100), "charlie":Account(200)}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1

semaphore.py

#!/usr/bin/python

import os
import random
import sys
import threading
import time

class Library:
	def __init__(self):
		self.rooms = ([None]*10)
		self.numb = 10
		self.queue = []
	
	def wait(self, caller):
		self.queue.append(caller)
		while ((self.numb < 1) or (self.queue[0] != caller)):
			time.sleep(0.1)
		self.numb -= 1
		for x in range(0, 10):
			if (self.rooms[x] == None):
				self.rooms[x] = caller
				self.queue.pop(0)
				return x
		sys.stderr.write("ERROR: wait() - Could not find a room!\n")
		sys.exit(1)
		return -1
	
	def signal(self, caller):
		for x in range(0, 10):
			if (self.rooms[x] == caller):
				self.rooms[x] = None
				self.numb += 1
				return x
		sys.stderr.write("ERROR: signal() - Could not find our room!\n")
		sys.exit(1)
		return -1
	
	def show(self):
		return self.numb
	
	def disp(self):
		o = ""
		o += ("rooms / time:%d\n" % (int(time.time())))
		for x in range(0, 10):
			if (self.rooms[x] == None):
				o += ("room[%d]=None\n" % (x))
			else:
				o += ("room[%d]=%s/%d\n" % (x, self.rooms[x].name, self.rooms[x].init + self.rooms[x].secs))
		o += ("\n")
		o += ("num[%d] / queue[%d] = " % (self.numb, len(self.queue)))
		for item in self.queue:
			o += ("%s, " % (item.name))
		o += ("\n")
		sys.stdout.write(("\n"*50) + o.strip() + "\n\n")

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.library = data
	
	def run(self):
		self.init = int(time.time())
		self.secs = random.randint(1, 9)
		room = self.library.wait(self)
		time.sleep(self.secs)
		left = self.library.signal(self)
		sys.exit(0)

x = 0
study = Library()
while (1):
	thread = myThread(x, "Thread-%d" % (x), study)
	thread.start()
	secs = 0.5
	study.disp()
	time.sleep(secs)
	x += 1

monitor.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount, iden):
		self.balance = amount
		self.name = iden
	
	def withdraw(self, amount):
		threadLock.acquire()
		print(time.ctime(time.time())+" withdraw "+" from "+self.name+" : "+str(self.balance)+" - "+str(amount)+" = "+str(self.balance-amount))
		if (self.balance >= amount):
			self.balance -= amount
		threadLock.release()
	
	def deposit(self, amount):
		threadLock.acquire()
		print(time.ctime(time.time())+" deposit "+" to "+self.name+" : "+str(self.balance)+" + "+str(amount)+" = "+str(self.balance+amount))
		if (amount > 0):
			self.balance += amount
		threadLock.release()
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		#threadLock.acquire()
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		for x in range(0, 3):
			bank[src].withdraw(5 * self.threadID)
			bank[to].deposit(5 * self.threadID)
			time.sleep(self.threadID)
		#threadLock.release()

threadLock = threading.Lock()
threads = []
bank = {"bob":Account(100, "bob"), "charlie":Account(200, "charlie")}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

threads.append(thread1)
threads.append(thread2)

for t in threads:
	t.join()

mutex.py

#!/usr/bin/python

import os
import sys
import threading
import time

class LinkedList:
	def __init__(self, data):
		self.data = data
		self.next = None
	
	def getnext(self):
		return self.next
	
	def setnext(self, next):
		self.next = next
	
	def getdata(self):
		return self.data
	
	def add(self, data):
		temp = self
		while (temp.next != None):
			temp = temp.next
		temp.next = LinkedList(data)
	
	def get(self):
		o = []
		temp = self
		while (1):
			o.append(temp)
			if (temp.next == None):
				break
			temp = temp.next
		return o

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.person = data
	
	def run(self):
		if (self.threadID > 1):
			threadLock.acquire()
		if ((self.threadID % 2) == 0):
			i = (len(self.person) - 1 - 4)
		if ((self.threadID % 2) == 1):
			i = (len(self.person) - 1 - 3)
		self.person[i-1].next = self.person[i+1]
		time.sleep(0.1)
		self.person.pop(i)
		if (self.threadID > 1):
			threadLock.release()

threadLock = threading.Lock()
threads = []
person = LinkedList("Bob")
person.add("Charlie")
person.add("Dave")
person.add("Earl")
person.add("Frank")
person.add("George")
person.add("Hal")
person.add("Ian")
person.add("Jon")

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" without threadlock")

thread0 = myThread(0, "Thread-0", l)
thread1 = myThread(1, "Thread-1", l)

thread0.start()
thread1.start()

threads.append(thread0)
threads.append(thread1)

for t in threads:
	t.join()

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" with threadlock")

thread2 = myThread(2, "Thread-0", l)
thread3 = myThread(3, "Thread-1", l)

thread2.start()
thread3.start()

threads.append(thread2)
threads.append(thread3)

for t in threads:
	t.join()

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

About these ads

2 responses to “[really long code post warning] Studying more concepts related to computer science in general

  1. ardian March 18, 2014 at 21:34

    I get the idea of your post, and find those lines of code very useful, would it be ok if I create a repo on github with these, surely I will send a link to the post,

    Ardian

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: