Assembly Language Tutorial – The Stack

Unfortunately we’re going to have to be a little theoretical in this post. We’ll be covering how we use memory in our assembly programs, in particular how the stack works.

When we execute our code, it is loaded into a nice big block of contiguous memory. The very first address in this block, address 0, is kept inaccessible from our program. If you have programmed in C before you will be familiar with null pointers. A null pointer is a pointer that points to memory address 0. The fact that this address is inaccessible to our program is why we can define a pointer with numeric value 0 to be null.

After address 0, there are various other things loaded into memory. Our instructions and data is loaded at address 0x0804800. After this there is a big empty space, the last address before this empty space is called the system break. If you try to access either the memory before 0x0804800 or inside the empty space after our instructions you will get a segmentation fault.

At the very top of the memory, is the stack. This is a special region of expandable memory that our code can use to store values on the fly. Reading and writing to the stack is slower than reading and writing to registers, but sometimes we need to use it. We typically use the stack for two different reasons, we don’t have enough space in the registers or we are changing context and want to save the current registers.

When we add new values to the stack it grows downwards into the empty space after our instructions and data. There really is a lot of space there so you shouldn’t worry too much about filling it up. We maintain the stack with a special register rsp, this should always contain the memory address of the top of the stack. We can access the contents of the stack using the rsp pointer directly. When we do this we have to be careful to maintain the value in the register so that it always points to the top of the stack.

We can also access the stack with the popq and pushq instructions. The popq instruction copies the value that the stack pointer currently points at into the register supplied and moves the stack pointer up to the next memory address. Similarly pushq copies the value in the named register into the next address after the current top of the stack and moves the stack pointer forward to this new address.

The stack doesn’t start off empty. When our programs begins the stack will contain the following in order:

  • Various environment variables
  • Command line arguments
  • The name of the program
  • The number of command line arguments

So when our program begins executing, the stack register, rsp, will be pointing at the topmost value in the stack, that is, the memory location containing the number of command line arguments passed.

In our next post we will see how to read command line arguments off the stack.

Don’t Use Objects in Python – part 2

In my previous post I explained that objects in python are really just special wrappers for dictionaries. There is one dictionary that contains the attributes of the object and another dictionary that contains the attributes of the class. Indeed we can really just think of the __init__ method as a static method that adds elements to a dictionary.

Objects in Python do however have one feature that you cannot get by just passing around dictionaries: inheritance.

Let’s suppose we are using some Arbitrary Object-Oriented Language. This language looks and works a lot like C#, Java or C++. We define two classes, Security and Bond in this language. Security has a single field, an integer, called Id:

public class Security
{
   public int Id;
   public Security(int id)
   {
        Id = id;
   }
}

Bond inherits from Security and adds another field, this time a double called Rate:

public class Bond : Security
{
    public double Rate;
    public Bond(int id, double rate) : super(id)
    {
        Rate = rate;
    }
}

What do we get by making Bond a subclass of Security? The most obvious thing we get is that Bond will get a copy of the implementation inside Security. So in this example, as Security has a public field called Id, Bond has one as well. We can think of Security as a user defined type that is built up out of primitive types. By using inheritance Bond extends this type.

In Python we can do something similar. First we define our two classes:

class Security:
    def __init__(self, id):
        self.id = id

and:

class Bond(Security):
    def __init__(self, id, rate):
        self.rate = rate
        Security.__init__(self, id)

Now, this time when we define Bond as a subclass of Security what do we get? Python objects are not composite types like in our object oriented language. In Python objects are really just dictionaries of attributes and these attributes are only distinguished by their names. So our bond class could have a numeric value in it’s Rate attribute, but it could also have a string value, or a list or any other type. When we subclass in python we are not extending a user defined type, we are just re-using some attribute names.

In our Arbitrary Object Oriented language, there is another advantage to making Bond a subclass of Security: the ability to treat Bond as a Security. To understand what this means, suppose we have a function that prints the ids of a list of Securities:

static void printPortfolio(Security[] securities)
{
    string ids = "";
    foreach(Security security in securities)
    {
        ids += (" " + security.id);
    }
    Console.WriteLine(ids);
}

Now, this function specifies it’s single parameter must be an array of Securities. However, by the magic of polymorphism, we can actually pass in an array of types that inherit from Security. When they are passed in they are automatically cast to type Security. This can be pretty useful, in particular it makes it a lot easier to reason about our code.

Now let’s define the same function in Python:

def print_portfolio(securities):
    ids = ""
    for security in securities:
        ids += (" " + str(security.id))
    return ids

On the face of it, this is very similar. However we are not really using polymorphism in the same way as we are in our object oriented language. We could actually pass a list of any objects into the print_portfolio function, and, as long as they had a id attribute, this would execute happily. We could, for example, define a completely unrelated class like so:

class Book:
    def __init__(self, id):
        self.id = id

and pass a list of these into our print_portfolio function without any problems. Indeed in Python we can dynamically add attributes to an object, so we could even create an empty class:

class Empty:
    def __init__(self):
        pass

and assign a id attribute to it at runtime, via:

e = Empty()
e.id = "Hello"

and then enclose it in a list [e] and pass it into the print_portfolio function.

There’s one more thing we get with inheritance in an object oriented language: access to protected members. When we mark a method or field as protected it will only be accessible from within objects of that type or types that inherit from it. However in Python there are no protected methods or fields, everything is public.

So there are three reasons why I don’t think inheritance makes sense in Python:

  • Python classes aren’t really composite types, so it doesn’t make sense to extend them
  • Inheritance doesn’t give us extra access to protected methods, as everything in python is public anyway
  • Inheritance in Python doesn’t give us the benefit of polymorphism because in Python there are really no restrictions on what objects we pass around

So, that is why there really is no extra benefit to using an object in Python rather than a dictionary.

Don’t Use Objects In Python – Part 1

Everyone knows Python is object oriented. It’s right there on on page 13 of introducing python, it says as much on Wikipedia. You might have even seen classes, objects, inheritance and polymorphism in python yourself. But is Python really object oriented?

Let’s first ask, what actually is an object in python? We’ll see for ourselves, by creating a simple python class:

class Record:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def is_over_eighteen(self):
        return self.age > 18

this is just a simple class that has two member fields, name and age and a single method is_over_eighteen. Let’s also create an instance of this class:

my_record = Record("Stubborn", 207)

In Python member fields and methods are known as attributes. We can lookup the attributes of our record just like in any other standard object oriented language by my_record.name, my_record.age and my_record.is_over_eighteen.

Our object also has other secret attributes that are created automatically. Their names start with a double underscore. The attribute we are interested in is my_record.__dict__. If we evaluate this we will see that it is a dictionary of the instance attributes:

{'name': 'Stubborn', 'age': 207}

What’s interesting is that this isn’t just a representation of the object as a dictionary. In python an object is backed by an actual dictionary, and this is how we access it. When we look up an attribute of an object with the normal notation, for example my_record.age, the python interpreter converts it to a dictionary lookup.

The same is true of methods, the only difference is that methods are attributes of the class. So if we evaluate: Record.__dict__ we get something like:

mappingproxy({'__module__': '__main__', '__init__': <function Record.__init__ at 0x7f3b7feec710>, 'is_over_eighteen': <function Record.is_over_eighteen at 0x7f3b7feec7a0>, '__dict__': <attribute '__dict__' of 'Record' objects>, '__weakref__': <attribute '__weakref__' of 'Record' objects>, '__doc__': None})

We can access our method from this dictionary via:

Record.__dict__["is_over_eighteen"](my_record)

So a Python object is really just a wrapper for two dictionaries. Which begs the question, why use an object at all, rather than a dictionary? The only functionality objects add on top of dictionaries is inheritance (more on why that is bad in a later post) and a little syntactic sugar for calling methods. In fact there is one way in which python objects are strictly worse than dictionaries, they don’t pretty print. If we evaluate print(my_record) we will see:

<__main__.Record object at 0x7f3b8094dd10>

not very helpful. Now there is a way to make objects pretty print. We do this by implementing the __repr__ method in our Record class. This is the method used by print to represent an object as a string. However, dictionaries already have __repr__ defined so they will pretty print automatically.

Fundamentally, if you think you want to define a class in python, consider just using a dictionary instead.

Assembly Tutorial – I/O Bringing it all Together

We’ve seen in previous posts how to handle errors when writing to files and how to read and write arbitrary numbers of bytes to files. It’s time we put this all together! We are going to write a program that will read an arbitrary number of bytes from the command line and write them to a file. If our program encounters any errors it will gracefully exit with code 1. Here’s the code:

.equ BUFFER_SIZE, 20
.equ NEW_LINE, 10

.section .data
filename:
.string "outputfile\.txt"

.section .bss
.lcomm buffer_data, BUFFER_SIZE

.section .text

.globl _start
_start:

movq $2, %rax
movq $filename, %rdi
movq $0x441, %rsi
movq $0666, %rdx
syscall

cmpq $0, %rax
jl exit_with_error

movq %rax, %r9

read_from_buffer:

movq $0, %rax
movq $0, %rdi
movq $buffer_data, %rsi
movq $BUFFER_SIZE, %rdx
syscall

cmpq $0, %rax
jl exit_with_error

movq %rax, %rbx

movq $1, %rax
movq %r9, %rdi
movq $buffer_data, %rsi
movq %rbx, %rdx
syscall

cmpq $0, %rax
jl exit_with_error

decq %rbx
cmpb $NEW_LINE, buffer_data(,%rbx,1)
je exit

jmp read_from_buffer

exit:
movq $60, %rax
movq $0, %rdi
syscall

exit_with_error:
movq $60, %rax
movq $1, %rdi
syscall

Nothing we have done here is really new. We start by defining some constants and a 20 byte buffer. Then, in the text section, we open the file named “outputfile.txt”.

movq $2, %rax
movq $filename, %rdi
movq $0x441, %rsi
movq $0666, %rdx
syscall

When we open the file we use the flag value 0x441. This flag tells the kernel three things: that we want to open the file in write mode, that we want to create a file if it doesn’t exist and that we want to append to the end of a file if it does exist.

After the open system call, we check if the return value of this system call is negative:

cmpq $0, %rax
jl exit_with_error

movq %rax, %rbx

If so, we jump straight to exit_with_error, otherwise we stash the return value in r9. You have to be careful to stash values you want to keep somewhere they won’t get over written during the next system call. We don’t use rsi, rdi or rdx as we are using to pass values to the kernel. The registers rcx and r11 will, in general, have their values overwritten during a system calls and rax will contain return values. So we choose rbx and r9 as our two stash registers.

Now, once we’ve opened our file, we enter a loop. Our loop starts with the label read_from_buffer. As before, at the end of each loop we check if the last character we have read is a new line and if so, jump to the exit, otherwise we jump back to the loop start:

decq %rbx
cmpb $NEW_LINE, buffer_data(,%rbx,1)
je exit

jmp read_from_buffer

Inside this loop we have our read and write system calls:

movq $0, %rax
movq $0, %rdi
movq $buffer_data, %rsi
movq $BUFFER_SIZE, %rdx
syscall

cmpq $0, %rax
jl exit_with_error

movq %rax, %rbx

movq $1, %rax
movq %r9, %rdi
movq $buffer_data, %rsi
movq %rbx, %rdx
syscall

cmpq $0, %rax
jl exit_with_error

We now have a conditional jump statement after each of these calls. If control returns from either with a negative number in rax we jump straight to exit_with_error.

That’s it, we’ve covered everything we will need to handle input and output in x86 assembly! It’s been quite a journey. In our next few posts we’ll be trying something slightly different.

What is Single Inheritance, and Why is it Bad?

In a previous post we talked about how there are two different notions of inheritance, Interface Inheritance and Implementation Inheritance. In this post we’ll be talking primarily about the latter. That means, we’ll be talking about using inheritance to share actual logic among classes.

Let’s say we defined two base classes. The first is DatabaseAccessor:

class DatabaseAccessor {
   protected:
   bool WriteToDatabase(string query) {
   // Implementation here
   }

   string ReadFromDatabase(string query) {
   // Implementation here
   }
}

which encapsulates our logic for reading from and writing to some database. The second is Logger:

class Logger {
   protected:
   void LogWarning(string message) {
   // Implementation here
   }

   void LogError(string message) {
   // Implementation here
   }
}

this encapsulates our logic for logging errors and warnings. Now, suppose also that we are using a language the supports multiple inheritance, such as C++. If we want to define a class that shares functionality with both of these classes, we can subclass both of them at once:

class SomeUsefulClass : private DatabaseAccessor, private Logger {
   // Some useful code goes here
}

So, we have a subclass named SomeUsefulClass that can use both the DatabaseAccessor and Logger functionality, great!

What if we wanted to do the same thing in a language like C# or Java? Well then we’re out of luck, in C# and Java you cannot inherit from more than one base class. This is called single inheritance. How do we achieve the same effect if we are using either of these languages? Well, one solution would be to chain our subclasses together. We would choose which of DatabaseAccessor and Logger is more fundamental and make it the subclass of the other. Suppose we decided that everything has to log, then the Logger class remains the same and DatabaseAccessor becomes:

class DatabaseAccessor : private Logger {
   protected:
   bool WriteToDatabase(string query) {
   // Implementation here
   }

   string ReadFromDatabase(string query) {
   // Implementation here
   }
}

So now we can subclass DatabaseAccessor and get the Logger functionality as well. Although, what if we really did just want the DatabaseAccessor logic, and we didn’t actually need the Logger implementation? Well tough luck. Now everything that inherits from DatabaseAccessor inherits from Logger as well.

This might not seem like much of a problem with something as trivial as Logger, but in big enterprise applications, it can spiral out of control. You end up in a situation where all the basic re-usable code you might need is locked inside a lengthy chain of subclasses. What if you only need something from the bottom ring of this chain? Unfortunately, you have to pick up all of it’s base classes as well. This makes our code unnecessarily complicated and harder to read and understand. If one of those unwanted base classes does all kinds of heavy weight initialisation on construction, then it will have performance implications as well.

One consolation that is often offered is that both languages allow multiple inheritance of interfaces. This doesn’t really help us though. Implementation inheritance and Interface Inheritance are two completely different things. We can’t convert one of DatabaseAccessor or Logger into an interface. The entire reason we want to inherit from them is to get their implementation!

We could also use composition instead of inheritance. In this case we would inherit from one of the classes, and keep a reference to the other. But, in that case, why even use single inheritance at all? Why not just let our classes keep references to a Logger and a DatabaseAccessor? The language designers have struck a bizarre compromise here, we can use inheritance, but only a little bit. If C# and Java are Object Oriented, then they should allow us to use the full features of object orientation, rather than just a flavour.

The good news is that the people behind C#, Microsoft, have realised the error in their ways. They have released two features that ameliorate the problem of single inheritance, Extension Methods and Default Implementations in Interfaces. More on these in future blog posts.

The Two Different Types of Inheritance

If, like me, you started life as a C++ developer, you will be surprised to learn that there are actually two completely different notions of Inheritance. In C++, these two different notions get squashed together, but they’re still there.

Imagine we are defining a base class to represent a financial security. In C++ it might look something like this:

class Security {
   public:
   virtual double GetPrice(double interestRate) = 0;
}

Any class that inherits from this base class has to implement the GetPrice method. Apart form that, they may have nothing else in common.

Now, suppose we are writing a base class that encapsulates our database access logic. Again, in C++, it might look a little like this:

class DatabaseAccessor {
   private:
   bool WriteToDatabase(string query) {
   // Implementation here
   }

   string ReadFromDatabase(string query) {
   // Implementation here
   }
}

These two examples illustrate the two different notions of inheritance, interface inheritance and implementation inheritance.

Interface inheritance, also known as type inheritance, is when we use inheritance to specify a common api across different classes. In our first example, every class that implements the Security class will have a public GetPrice method that takes a double argument and returns a double. There can be lots of different Security subclasses, that all calculate their price differently. But they all share the same interface for this functionality. This is interface inheritance.

Now, let’s look at our second example. Any class that inherits from DatabaseAccessor will have a shared implementation for reading from and writing to databases. We are using inheritance here to make our code easier to maintain and re-use. This is implementation inheritance.

When we write C++ we don’t normally distinguish between these two things. Indeed we can mix them freely. For example, suppose we had another class:

class RateCurve {
public:
   virtual double GetRateAt(time_t date);
   double Discount(double value, time_t date) {
      return value * GetRateAt(date);
   }
}

The method GetRateAt defines an interface as it’s a virtual function with no implementation. The method Discount comes with an implementation that will be shared between subclasses. So whenever we inherit from RateCure we will be using interface and implementation inheritance at the same time!

In a language like C# things are quite different. Interface and Implementation inheritance are handled explicitly and separately. If you would like to share implementation you inherit from a class. If you would like to use a common API you implement an interface. Interfaces are defined like so:

public interface ISecurity {
   public double GetPrice(double rate);
}

An interface cannot contain any fields, and (at least up to C# 8.0) interface methods cannot have implementations. This all means that it is a little bit easier to reason about our code. The disadvantage is that we cannot use both interface and implementation inheritance at the same time.

Assembly Tutorial – Input and Output the Right way

Up until now, whenever we’ve read from or written to a file, we’ve just put an upper bound on the number of bytes we were reading or writing. For example in our original simple echo program we used a buffer of 500 bytes, and we put the value 500 into the rdx buffer when making the read and write system calls. If we carry on this way, we’ll always have to put a maximum size on input and output. Let’s learn how to do this properly!

We are going to write another simple echo program. However, this time, we’ll use a loop to read and write the input. We’ll also use a register to store a memory address like a pointer.

Ok, let’s look at some code:

.equ BUFFER_SIZE, 20
.equ NEW_LINE, 10

.section .data
.section .bss
.lcomm buffer_data, BUFFER_SIZE

.section .text

.globl _start
_start:

read_from_buffer:

movq $0, %rax
movq $0, %rdi
movq $buffer_data, %rsi
movq $BUFFER_SIZE, %rdx
syscall

movq %rax, %rbx

movq $1, %rax
movq $1, %rdi
movq $buffer_data, %rsi
movq %rbx, %rdx
syscall

decq %rbx
cmpb $NEW_LINE, buffer_data(,%rbx,1)
je exit

jmp read_from_buffer

exit:
movq $60, %rax
movq $0, %rdi
syscall

The first two lines of this program introduce some new syntax. The equ keyword allows us to define a constant that will be substituted by the assembler. This is just like the #define pre-processor directive in C or C++. Here we define two constants:

.equ BUFFER_SIZE, 2o
.equ NEW_LINE, 10

The first, BUFFER_SIZE, is the size of the buffer we will be using, in this case 20 bytes. The second, NEW_LINE is just the ascii character code for a newline. Defining constants like this makes our code more readable and maintainable. Next, in the bss section we define a buffer named buffer_data of length buffer_size.

Now we have the meat of our program: a loop that starts with the label read_from_buffer. Inside this loop we have a read system call, a write system call, and a conditional jump.

The read system call:

movq $0, %rax
movq $0, %rdi
movq $buffer_data, %rsi
movq $BUFFER_SIZE, %rdx
syscall

reads BUFFER_SIZE worth of data from stdin to our buffer buffer_data. When control returns from the read system call the kernel will leave a return value in the register rax. This value will either be the number of bytes that the kernel read or a negative number indicating an error. For now, we ignore the error case. So, we move the value in rax into rbx to save it. Then we perform a write system call:

movq $1, %rax
movq $1, %rdi
movq $buffer_data, %rsi
movq %rbx, %rdx
syscall

The only new point here is that we move the value in rbx into rdx. This means we only ask the kernel to write the number of bytes that were actually read. Now, we do a conditional jump:

decq %rbx
cmpb $NEW_LINE, buffer_data(,%rbx,1)
je exit

We are checking to see if the final character we have read from stdin is a newline. The register rbx, contains the number of bytes we have read. So, to get the index of the last byte that we read, we decrement it. Then we use index addressing mode, buffer_data(,%rbx,1), to get the value of the last byte that we have read. This tells the cpu to read the value in rbx and count that many bytes past the start of buffer_data and load the value it finds. We compare this value with the ascii value for a newline. If the final character was a newline, we jump to the usual exit with code 0. Otherwise, the next instruction is the unconditional jump jmp read_from_buffer which brings us back to the start of the loop.

When we assemble, link and run this code, once it hits the first input system call, the shell will prompt the user for input on the command line. Suppose the user enters some text and hits enter. The kernel stores this text in the stdin file. In our system call we only asked for 20 bytes, so the kernel copies (at most) 20 bytes into our buffer, and discards them from stdin. The rest of the text that was input persists in stdin. Once we’ve written these bytes to stdout we can go back and read the next chunk from stdin. However, the user only gets prompted once, even though our code reads from the stdin file multiple times.

So now we know how to read and write input the proper way!