scala.bythebay.io: Guillaume Bort, Writing a dynamic x86_64 assembler in Scala
Recording: scala.bythebay.io: Guillaume Bort, Writing a dynamic x86_64 assembler in Scala
Hello everyone, welcome to this presentation. My name is Guillaume Bohr, I'm working as a lead software engineer at Criteo. I don't know if you guys know what Criteo is and do so let me just quickly introduce what it is. So basically Criteo is the biggest tech company you've ever seen. It's probably because it's a French company. We do performance advertising, so we display billions of ads every day and we track billions and billions of events. That's the scale of our analytics stack, so I'm working in the analytics stack. We manage more than five petabytes of data in our Hadoop cluster and we do that using Scala, you know with scalding and sometimes more and more Spark
And that's the scale of the rooftop of our main R&D office in Paris, so it's a very good, cool place to work again. And that's the scale of our vacation. So if you are wondering how it is to work for a French company, you can come to see me after the talk. So what I'm going to show you today is totally unsafe and experimental. So it's not something you want to do at work, but I hope it will give you some crazy idea anyway. So I will just write today the add function. That's the signature of the add function in Scala. Not very exciting and the implementation is even more boring
So I'm gonna write this directly using the the native machine bytecode. So who is able to read that? Yeah in the room? Yeah good. So yeah that's actually pretty simple. So the first instruction is move the content of the RGI register to the Rx register. The second instruction is add the content of the RSI register to the Rx register and put the result into the Rx register. And the last instruction is just return. How do I know which register to use? It's because I'm working on a unique system and in its x64 bits system. So it follows this system 5x86 64 application binary interface convention
So it says that the first parameter for a function come in this register, you know RGI, RSI, RDX and so on. And the result it must be stored into the Rx register. So that's exactly what this function does. There will be two parts in this presentation. The first one is I want you to show, I want to show you how I can embed a ISM language into Scala code. So it's like embedding any external DSL language into Scala. So it's mostly focused on Scala. And the second part is more low level
It's how I can actually generate the byte code for this ISM. And how can I load it into memory, making it executable and casting it to a real Scala function so I can use it at runtime. Let's start. So I have my project here. Is the font size okay for everyone? So I have my project here. And it's not SBT. It's run. Okay
So I will start by just writing my assembly code. So it's move. Rx RSI, I guess. No, it's RDI. Okay. Add and write. Okay. So if I want to embed that in my Scala code, I need some data structure for that
So I will just write the data structure for that. You know, the common IDT for that. So I have a register. I have the Rx register. And I have the RxC and Rd. I have the operand. So each instruction, assembly instruction, it has arguments. And these arguments, we call that operand
And there is many types of operand actually. And this one is the simplest one is the register direct. So it means that the value we are operating on is the content of the register. So I have this operand. And I have only one operand for now, which is a register direct. It has a register. And that's all. And I have this
And I need the extend. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end
And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end
And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end
And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end
And I need the end. And I need the end. And I need the end. And I need the end. And I need the end. And I need the end move. It's exactly the same. Okay
So now I have this ADT. And I want to translate that to this data structure. So it's pretty simple to do that in Scala. There is many ways to do it actually. But the way I want to do it is to use a string interpolation. So just to do that. And it allows me to embed assembly language into Scala. So of course here it does not compile because ISM does not exist
So I can easily fix that by providing an extension method for string context. So in line. And I can define ISM here. So it takes some dynamic argument. Because in string interpolation you can do whatever you want with argument. It will return a list of instructions. So and I can return it if I want. So now it should compile
No. It's an implicit class. Okay. It's compiling. Okay. So now how can I effectively translate this? So the code itself is here. You know. It's in the string context parts
And I can just call make string. It's cheating because I don't care about the argument. But okay. And I can split that by line. And I can. Yeah. Let's trim them. Filter the empty line
And now I have this line of text. And I want to translate them into instruction. So how can I do that in Scala? So in Scala, the simplest way is to use a parser combinator. So I will use the built-in. It's not really built-in anymore. But it's the official one. There is many other parser combinator libraries in Scala. So this one is Scala
Util parsing combinator. And I will create an ASM parser. So I will start by my register parser, which is a parser of register. So it's easy actually. If it's Rx, it's Rx. So this parser is easy. Now I need my parser for operand. So it's easy as well
Now it's a parser of operand. And it's basically a register. And we translate that into a register direct operand. And I need a parser for instruction. So... And this one, it's... So the first one is really easy as well. And the move
So it's move. We have an operand. We have a comma. We have another operand. And we... Okay. I can ignore this guy actually. Okay
So it's... Because it's an Intel syntax, the two is before the from. That's right. Yeah. So... And I can create a move instruction from two. And it's exactly the same for the add instruction except that. Okay
So I have this compiler. Why does not... enough argument. Okay. No, it's... Okay. It's a typo. Okay
So here, I can just... You know, I have the input here. And I will use the ASM parser. Parse method. So I have to provide the parser I want to use. So I want to parse instruction. And I give the input. And now, you know, the parsing, it can fail, of course
So I will only collect the success case. Because I don't care with error. I don't care with error right now. So I have the instruction. And... Okay. And that's an array. So, okay
I can call to list. Okay. So... I have my data structure for the assembler or assembly program now. So you see, I can easily embed assembly now into my Scala program using this ASM A string interpolation. And that's cool. So the first part of the job is done. I know how I can embed ASM into my program
But now, I want to make it runnable. So how can I do that? Crash course to assembly encoding. It's actually pretty simple. The main part is the instruction opcode. So for each instruction, we have an opcode. Okay. That's easy. Usually it's one byte
Sometimes it's two bytes. But in our case, it's only one byte. We have this modreg RM byte, which is used to indicate which kind of operand we use. So the simplest case, as I said, is registered direct. And in this case, we don't choose the other one. For more sophisticated operand, we use the other byte. For us, we won't use them. And we have this optional instruction prefix
And we will use them. We will use one byte here in the instruction prefix because we are working on a 64-bit mode. The instruction we are using, we need to add a prefix to say the processor we want to use the 64-bit version. So that's the RECS prefix we use for that. And you put the RECS prefix before the instruction when you want to use 64-bytes operand. Or you want to use an extended register. But in our case, we need to use this prefix. So the first four bits are always that
And we want to put these bits to one when we are using 64-bits. It's not 64-bytes actually. It's 64-bits operand. So we need to put that in front of our instruction. So that's the upcode for our instructions. The return one is the simplest one. And we have these two upcodes for these two instructions. How do I know that? If you can have a look to this website, when you can have all the upcodes for all the instructions supported by a modern processor
And you see that the one I will use, the add, is this one actually. Okay. And the last byte we have to encode is this one. So as I said, for register direct, we put, this is the simplest. We put one and one here. And then we have three bits here to put the code of the first register and three bits here to put the code of the second register. The code are here. You can find them on the OS Dev
And so it's basically, you know, Rx is zero. Rx is six. And Rx is seven. Okay. So that's easy. We'll start here, register. I need a code, which is a byte. So val code is zero
Rx, so I sync Rx is six. As I said, yeah, Rx is six. And for instruction, now I need to add bytes. So bytes will give me the actual code bytes for the instruction. So Rx is the simplest one. The bytes actually are this. Okay. Not even this
Okay. And now I have to implement bytes for add and move. So that's not so difficult. I will start by pattern matching the operand. And so you have this case where my first operand is a register direct. And the second operand is a register direct. And I have the other case and I don't want to support them right now because I don't know how to encode them. So I just fail if it happens
So not supported. Okay. And so in this case, as I said, I need the Rx prefix. So the Rx prefix is this one. So it's. Now I need the opcode. So opcode for add is one. And I need the mod RM bytes, this one
So it's these two bits always. Plus the code of the first register and the code of the second register. So the first register is here. And I have to display the bytes, the bits. And the second register is here. And that's all. I have encoding for this instruction. Why? Let's compile again
And it's actually the same for move. So op. But here it's a different opcode, but it's basically the same. Okay. It's compiling. So I will check that. I can now use that to. get the byte of my program
Okay. It's not really easy to read. So map. I have this byte. And I can format it better. So it's byte. And so it's byte. And so
Okay. So I have this byte for my program. And I want to check that this is correct. So how can I do that? I can use another assembler, real one. And I will check and compare. And I want to check that this is correct. So how can I do that? I can use another assembler, real one. And I will check and compare
And I will check. And compare with mine. So let's. Create the. Add.asm. Which is this. And use. And I will check
And compare with mine. So let's. Create the. Add.asm. Which is this. And use. And I will check. And compare with mine
So let's. Create the. Add.asm. Which is this. And use. And I will check. And compare with mine. So let's
Create the. And compare. And okay. That's correct. I did not make any mistake. So it's good. Okay. I have the bytes
So. Check. And no. I need to load that into memory. And making it executable. And casting it with kind of function. It's a bit more low level. No
I will use two things. So the famous. Unsafe stuff in the GVM that access. That allow you to access. A native of it memory. And I will use. GNA. Which is an alternative for GNE
And it will allow me to. Dynamically. Call my native function. The one I will generate. I just need one more thing. Using Unsafe. I can load some. bytes into memory
But I can't really execute this. I need to call the libc mprotect. To make the region executable. So I need to create a wrapper to the libc. For that. Okay. So the first thing. Is to allocate a page of memory
So yeah. It has to be an aligned. Memory page. Because mprotect in libc. Works only on an aligned. Memory page. You can't just take. Random bits of memory
And mark them executable. It has to be an aligned page. So let's import GNE. And it will return a pointer. And the actual. Pash size for the system. So. I need the Unsafe
And for that. I will just cheat. Because. The code is really. Awful. And I don't want to write that myself. So I have the Unsafe now. And I can ask for the patch size
I can use Unsafe to allocate. So. I have the Unsafe now. And I can ask for the patch size. I can use Unsafe to allocate. Some memory. But. Using Unsafe
In the GVM. I can't really allocate. An aligned page of memory. I can do that. So I have to cheat. I will just allocate. Two times. The patch size
And I will try to find. The right alignment myself. So. It's basically this. Plus. Patch size. Okay. And
It's a conversion. To the native function. And. I can even. Make it generic. Actually. So. And
Take. A. B. Rotter. Int. So. What it does. It
Use the. Unsafe API. To. Invoque the function. Using an. Int. As. A
As. A. As. A. As. A. As. A
As. A. As. A. As. As.