Recent Blog Posts

Row Level Locking in Django

2012-01-16T00:00:00Z

In one of my fixes that I was working at work I had to implement row level locking in Django. Current stable, 1.3, version of Django does not have built-in capability for row level locking on InnoDB tables. The good news are that the development version already has an update in QuerySet API that will let you use select_for_update method to acquire a write lock on rows matching your query. If you can use development version for your project you may stop reading and go upgrade Django, otherwise I will see you at the bottom of the page.

Locking your models

Since you're building your web application with Django it's most likely that you are using Django ORM to access database. However, in order to be able to perform locking queries we will have to write SQL queries ourselves. Which is much easier than you might think (unless you need some complex join across million tables). Assuming you have Article model you acquire row level lock as follows:

article = Article.objects.raw("SELECT * FROM articles WHERE id = 123 FOR UPDATE")[0]

When running the above query an instance of your Django web application will remain blocked until the instance that acquired the lock first releases it or lock wait timeout occurs. One thing to note here is that locking will only work if your code is executing inside of a transaction. Ultimately, you want to have something like this:

from django.db import transaction
from MySQLdb import OperationalError

def hack_article(article):
    # Some magical code that does something with the article.
    pass


@transaction.commit_on_success
def function():
    try:
        article = Article.objects.raw("SELECT * FROM articles WHERE id = 123 "
                                      "FOR UPDATE")[0]
    except IndexError:
        # Handle not found
        return
    except OperationalError:
        # Handle lock timeouts
        return

    hack_article(article)

The write lock will get released once the transaction is committed or aborted, in the above case this happens once we leave the function. There is actually one case (maybe there are more, let me know if I am wrong) where the lock can get released before the transaction is committed or aborted -- when a new transaction is started inside of another transaction. So, the above example would be prone to race conditions if our hack_article function looked like this:

@transaction.commit_on_success
def hack_article(article):
    # Some magical code that does something with the article.
    pass

The reason for this is that locks don't propagate through nested transactions in MySQL.

Wrapping up

Row level locking in Django is easy as 1, 2 and 3 :D

Make sure that your tables use InnoDB engine.
Acquire locks inside of transaction.
Make sure that you are not creating new transactions inside of another transaction which holds the lock.

That's all.

How to establish a P2P connection

2010-12-08T00:00:00Z

I am working on this cool project which I don't want to disclose yet and the essential part for this project is to create a peer-to-peer connection between two computers. Creating a connection is not that difficult; however, it gets complicated when both computers are sitting behind a NAT device. The NAT device will create a private IP address space and be responsible for routing packets into and out from the private network. This means that an IP address and a port number associated with a particular service are not directly accessible from other computer networks and all inbound data packets must be routed by the NAT device. So how do you create a P2P connection when the NAT device is "blocking" access to a peer? The technique I will cover here is very elegant yet very simple --- it's called hole punching. Hole punching a technique that opens a temporary port on the NAT device which is directly mapped to a port on the internal network. There are two types of hole punching: TCP and UDP. In this post I will only cover UDP hole punching because it has better support (82% for UDP and 64% for TCP according to this source) and is easier to implement. Let me illustrate what a UDP hole punching is and then take a look at the implementation.

(the illustration was lost when i moved to posterous, but you can search google images for udp hole punching to get the idea).

As you can see there are only four steps required in order to create a P2P connection. At first, peers have to register with a broker. The broker is a computer with a public IP address; registration process is very simple --- the broker stores peer's id, its external IP address and external port number. When a peer connects to the broker in step 1 the NAT device creates a temporary mapping from the external port to an internal port, that is to say, a hole is punched though the NAT. Next, second peer wants to establish a direct connection with the first peer, but he does not now what is the port number and IP address of that peer. So, it contacts the broker and asks for peer 1 credentials. Once the credentials are received the second peer can make a direct connection to the first peer through the temporarily allocated external port on NAT 1. In theory it does not look hard at all; in practice --- it is exactly the same. I had a trouble finding some simple code examples showing how to implement hole punching, so I wrote a proof of concept code in python to test whether this technique works.

#
# Broker
#
from socket import *

HOST = ''
PORT = 9999

s = socket(AF_INET, SOCK_DGRAM)
s.bind((HOST, PORT))

peers = {}

while 1:
    data, addr = s.recvfrom(128)
    print addr, data
    peers[addr] = True
    if len(peers) > 1:
        peer1 = peers.keys()[0
        peer2 = peers.keys()[1]
        s.sendto("peer " + peer2[0] + " " + str(peer2[1]), peer1)
    else:
        s.sendto("pong", addr)
#
# Peer
#
from socket import *

BROKER_HOST = "broker.host.com"
BROKER_PORT = 9999
BROKER_ADDR = (BROKER_HOST, BROKER_PORT)

sock = socket(AF_INET, SOCK_DGRAM)
# to support two peers on the same machine
try:
    sock.bind(('', 9900))
except:
    sock.bind(('', 9901))

sock.sendto("ping", BROKER_ADDR)

while 1:
    data, addr = sock.recvfrom(128)
    new_data = data.split()
    if new_data[0] == "peer":
        addr = new_data[1]
        port = int(new_data[2])
        sock.sendto("resp test", (addr, port))
    elif new_data[0] == "resp":
        sock.sendto("what goes around comes around", addr)
    print addr, data

This is a very simple code. The broker supports only two peers and must be started on a computer that has a public IP address. A peer will punch a hole by sending a ping message to the broker. In this example peers don't request the address and the port number of another peer, but instead the broker will send this information to the second peer. If everything worked out, one peer will see a "test" message on its screen, whereas, another one will see "what goes around comes around". I was able to test this code where one peer, that would be me, was in the US and another one, my friend, was in Lithuania, and it works.

I am not dead, but only trying something new!

2010-08-25T00:00:00Z

It's been a while since my last post. A few things (small) has changed in my life since then, including the type of information I consume which shifted drastically. I am a very technology oriented person and this makes me kinda geeky by definition. All my friends know that I am good with computers and programming. For those who don't know me, do you think it's because I study hard at college? No, it's because in my childhood I was so attracted to computers that video games were not cutting it anymore, so I found programming and I got hooked. I read so many books and articles on programming and that's what made me so good at it. However, now I try to read technical material as little as possible, and it's not because I don't want to grow, it's because I changed my priorities and I have to grow in a different area of interest. My current area of interest is business. Why did I made such a change? Let's go back to one of my dreams first. About four years ago when I entered the university to study computer science, I thought that college is the last step I have to take, and after I graduate great job awaits me at a big company. Does this sound familiar to you? The main reason why I switched from one topic to another is that I don't like following rules, and a big company will have a huge rule book. So, I changed my dream of becoming a good programmer at a big company to becoming a business owner. For this to work I have to totally change my environment. I can't remember what I read but I memorized the following quote: spend one hour every day on a topic of your interest and after five years you will be a master of that specific topic. So, I started with exposing myself to business related information: books, twitter streams, magazines etc. During the summer I read three books whose titles I would like to share with you.

Getting Real: The smarter, faster, easier way to build a successful web application by 37signals.
REWORK by Jason Fried and David Heinemeier Hansson.
Linchpin: Are you indispensable? by Seth Godin.

All these books are business books. Let's start with Getting Real and REWORK. REWORK actually is a revamped and extended version of Getting Real. If you are planning to buy one of these get REWORK. In REWORK authors talk about common mistakes that startups do. If you are familiar with 37signals practices you know that they go for simplicity and clarity in both their applications and business environment. If you are like me and know nothing about business you must read it -- it will completely change the way you think about starting a business (especially web/software). I was working for a startup this summer and was able to see some of the mistakes that were covered in REWORK. For example, we had meetings twice a week where we had to update our status because there was some higher power involved in the company. The length of a meeting ranged from one to three hours which is a complete waste of time, and REWORK nicely explains why "meetings are toxic". Read this book! Linchpin is another great book. Its main purpose is to make the reader unleash the artist within. As the author says: we've been brainwashed. We are constantly being brainwashed by our friends, family, school, colleagues who say that we have to follow the rules in order to secure our future. The book tries to engrave the exact opposite on the reader's mind. In order to secure your future you have to become an artist: you have to take an extra step that makes your work flawless or brings joy to people. The reason for taking this step is that it's the only thing that keeps you in your job or makes you a competitor of huge companies who have power to deliver goods fast and at low cost. Linchpin is a very inspirational book. I hope you will be able to read these books. They are really worth your time. I have a few more books on my reading list which I am planning to cover here after I finish reading them. I also found this very interesting site called StartupDigest. If you subscribe you will receive an email once in a while with upcoming startup events in your area. Maybe I will meet you in one of these! :)

Creating a personal virtual machine for code obfuscation purposes

2010-01-04T00:00:00Z

When talking about the protection of intellectual property, virtual machines and custom instruction set can play a very important role in the field. One of the ways to protect your algorithm from curious eyes is to use code obfuscation techniques. These can range from a simple instruction reordering to a more sophisticated control flow modifications and added layer of custom instruction set, or a combination of both. Recently I've watched a video about virtual machines for code obfuscation from RECON video archives. The speaker said that his implementation is available for download at his website for those who want to experiment; however, I could not find it so I've decided to implement my own compiler and virtual machine (vm).

The code of the compiler and testing version of the vm is available for download from github. I am not going to explain how they are implemented but I will explain how one can create his custom instruction set by extending the compiler and how to write code that compiler understands.

The compiler was written in python because it makes the work with text and strings trivial. There are three files: compiler.py, vmc.py and myis.py. The compiler.py is basically the class that provides all the logic: lexical analysis, compiling, linking, etc. The parser in the compiler does not support comments. So, if you are going to write anything longer than my factorial example you may get lost in the code. The compiler only supports 7 types of tokens where each token is separated by a white space:

instruction -- an instruction (see myis.py instructions variable).
register -- a register (see myis.py registers variable).
@register -- a register that holds memory address and will be dereferenced by the virtual machine.
immediate -- an immediate value. Syntax: int(<number>) where <number> can be a number in any format supported by python.
label -- a label. Syntax <name>:
reference -- any name that does not fall under the instruction and register categories. Usually a label without a colon.
string -- a sequence of bytes. Syntax str(<string>) where <string> is any string supported by python.

A sample program that computes factorial can be found at github with the rest of the code; the syntax should become more clear by looking at it. However, you should be aware when using int() and str(); whatever will be inside the parenthesis is going to be evaluated by the python interpreter. Furthermore, int() and str() cannot take an argument with white space. For example, instead of str("hello world") you should use str("hello\x20world").

First let's look how one can extend the instruction set by modifying myis.py.

registers = ["eax", "ebx", "ecx", "edx", "esp", "ebp", "esi", "edi"]
instructions = {
"push"  : [{"opcode" : 0x00, "format" : "<cc", "params" : ["reg"]}],
"pop"   : [{"opcode" : 0x01, "format" : "<cc", "params" : ["reg"]}],
"mov"   : [{"opcode" : 0x02, "format" : "<ccI", "params" : ["reg", "imm"]},
           {"opcode" : 0x03, "format" : "<ccc", "params" : ["reg", "reg"]},
           {"opcode" : 0x04, "format" : "<ccc", "params" : ["reg", "@reg"]},
           {"opcode" : 0x05, "format" : "<ccc", "params" : ["@reg", "reg"]},
           {"opcode" : 0x06, "format" : "<ccI", "params" : ["reg", "ref"]}
],
...
}

Above you can see an excerpt from myis.py which contains two variables: registers and instructions. The registers variable is a list containing all valid registers that tokenizer will recognize. If the order of registers is changed the compiler will generate different instruction opcodes because it refers to registers by their position in the array. The instruction variable is a map table (dictionary in python terms) where each keyword is a name of an instruction mapping to a list that contains one or more dictionaries. Each inner dictionary has three keys:

opcode -- an opcode number.
format -- an instruction encoding format. See python struct.
params -- a list of parameters (in exact order) the instruction takes. Valid values are: reg, @reg, ref, imm, str. See tokens above for more details.

Sometimes an instruction can have multiple dictionaries as mov does in the above example. This should be only the case when instruction can take different set of arguments; then the compiler will iterate through till it finds the right match. There is also a special instruction defined in the myis.py - emit. The emit takes a string as an argument and emits bytes into the code. This can be useful if you want to make code overlap, reserve space for variables, or just manually inject bytes in the code. When using references as arguments the address of the reference will be translated to an offset relative to the instruction pointer. Simply by modifying myis.py you can introduce new instructions to the compiler; then write the code and compile it with vmc.py.

Once you have the bytecode the final step is to write a vm that will read it and execute the encoded instructions. Among the source files I have included a very basic sample vm that will execute the factorial program. The implementation is pretty straightforward.

Hopefully I have covered everything and didn't miss any parts of the compiler's logic. The source code I provide is highly experimental and it should have tons of bugs; nevertheless, it should give a good starting base to those who would like to write their own compiler and a vm.