🔎 Creating a VM for fun - Part 3: C virtual stack

Table of Contents

Custom VM - This article is part of a series.

Part 1: 🔎 Creating a VM for fun - Part 1: ASM

Part 2: 🔎 Creating a VM for fun - Part 2: C

Part 3: This Article

Part 4: 🔎 Creating a VM for fun - Part 4: Implementation and refacto

The code is here: https://github.com/OxNinja/C-VM

First stack implementation #

This is propably the most difficult thing in this project for me, as I had to figure out how to implement a virtual stack and related stuff.

I first thought about using a pointer to a malloced chunck as the stack, where I could store pointers to the values, so here is the struct:

 1typedef struct Stack {
 2  // LIFO stack
 3
 4  // max size of the stack
 5  int max_size;
 6
 7  // pointers for the stack
 8  int *stack, *stack_base, *stack_end, **stack_pointer;
 9  
10} Stack;

A few explanations about this propably cursed struct:

max_size is the size of the stack (max number of pointer that could be stored in it).
*stack is a pointer to the allocated chunk in memory to store the pointers.
*stack_base is a pointer to the base of the stack (the first place to store pointers at).
*stack_end is a pointer to the end of the stack (the limit of its size).
**stack_pointer is a pointer of the current “cursor” in the stack, pointing to the stored pointer in it.

flowchart LR subgraph Stack direction LR subgraph *stack direction LR 0x00 --> 0x55ff1111 0x08 --> 0x55ff2222 0x10 --> 0x55ff3333 0x18 --> 0x55ff4444 ... --> 0x... max_size --> ??? end **stack_pointer --> 0x18 *stack_base --> 0x00 *stack_end --> max_size end

Feel free to visit the project’s repo to check if I finished this implementation, but by now I am for sure struggling with this.

In fact with this virtual stack the VM is now able to push & pop and all that stuff, here is how I implemented them:

 1void my_push(Registers *regs, Stack *stack, int shellcode) {
 2  // get the value to push
 3  int value = shellcode & 0x00ffffff;
 4  // get a pointer to the value
 5  int *pointer = &value;
 6  // make the stack pointer pointing to the pointer 🧠 👉 👈
 7  *stack->stack_pointer = pointer;
 8  // increment the cursor for the top of the stack
 9  stack_inc(stack);
10}

The same goes for the pop, except that we first decrement the stack pointer index, as we incremented it last, and then we store the value pointed into the corresponding register.

I then stumbled upon other bugs in my code, which discouraged me to continue further.

Second attempt #

Maybe one year later or so I deceided to continue this project.

I settled for a more kernel-like approach: using chained list instead of mallocing a big chunk of memory.

Here is my go:

flowchart LR subgraph list direction LR a[*first] --> a1[0xff5500aa] b[*last] --> b1[0xff5500bb] subgraph "node @0xff5500aa" direction LR A1[*prev] --> D1[NULL] B1[data] --> 0 C1[*next] --> E1[0xff5500bb] end subgraph "node @0xff5500bb" direction LR A2[*prev] --> E2[0xff5500aa] B2[data] --> 1 C2[*next] --> D2[NULL] end end

Which might be simpler to code, and to understand.

Here are the associated structs:

 1struct node {
 2  struct node *prev;
 3  struct node *next;
 4  int data;
 5} typedef node;
 6
 7struct list {
 8  struct node *first;
 9  struct node *last;
10} typedef list;

Very basic, therefore effective.

The idea afterwards is to create the list pointer, which will be our LIFO stack. All the new nodes will be allocated in the heap for us – the real heap, not our VM’s.

Code #

As a PoC for this new stack concept, here is how I did it, plus some performance indicators:

main.h #

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4struct node {
 5    struct node *prev;
 6    struct node *next;
 7    int data;
 8} typedef node;
 9
10struct list {
11    struct node *first;
12    struct node *last;
13} typedef list;
14
15node * node_create(int d) {
16    node *p = (node*) calloc(1, sizeof(node));
17    p->prev = NULL;
18    p->data = d;
19    p->next = NULL;
20
21    return p;
22}
23
24void node_print(node *p) {
25    printf("%d\n", p->data);
26}
27
28list * list_create(void) {
29    node *n = node_create(0);
30    list *p = (list*) calloc(1, sizeof(list));
31    p->first = n;
32    p->last = n;
33
34    return p;
35}
36
37int list_push(list *l, int d) {
38    int err = 1;
39
40    node *n = node_create(d);
41    node *last = l->last;
42
43    n->prev = last;
44    last->next = n;
45    l->last = n;
46
47    err = 0;
48    return err;
49}
50
51int list_pop(list *l) {
52    int err = 1;
53
54    node *last = l->last;
55    node *slast = last->prev;
56
57    slast->next = NULL;
58    l->last = slast;
59    free(last);
60
61    err = 0;
62    return err;
63}
64
65void list_print(list *l) {
66    printf("===== (%p)\nlist first ->\t%p\nlist last ->\t%p\n", l, l->first, l->last);
67    node *p = l->first;
68    while(p != NULL) {
69        printf("(%p)\nprev -> %p\ndata -> %d\nnext -> %p\n-----\n", p, p->prev, p->data, p->next);
70        p = p->next;
71    }
72
73    printf("\n");
74}

main.c #

 1#include "main.h" 
 2
 3int main(void) {
 4    list *l = list_create();
 5
 6    int i = 1;        
 7    while(i<2000000) {      
 8        list_push(l, i);
 9        i++;
10    }          
11
12    while(i>1) {      
13        list_pop(l);
14        i--;
15    }                       
16
17    list_print(l);          
18
19    return 0;   
20}

For pushing, then poping 2M nodes on my list it took no time:

time ./bin.out
===== (0x55ab7ff042c0)
list first ->	0x55ab7ff042a0
list last ->	0x55ab7ff042a0
(0x55ab7ff042a0)
prev -> (nil)
data -> 0
next -> (nil)
-----

./bin.out  0.10s user 0.02s system 99% cpu 0.121 total