Как написать (игрушечную) JVM

Статья про KVM оказалась интересной для читателей, поэтому сегодня публикуем новый перевод статьи Serge Zaitsev: как работает Java Virtual Machine под капотом.

Нравится нам это или нет, но Java — один из наиболее распространенных и широко используемых языков программирования. Однако не каждый Java-разработчик настолько любопытен, чтобы заглянуть под капот и посмотреть, как устроена JVM.

Я попытаюсь написать игрушечную (и неполную) JVM, чтобы показать основные принципы ее работы. Надеюсь, эта статья вызовет у вас интерес и вдохновит на дальнейшее изучение JVM.

Наша скромная цель

Начнем с простого:

public class Add {
  public static int add(int a, int b) {
    return a + b;
  }
}

Мы компилируем наш класс с javac Add.java, и в результате получается Add.class. Этот class файл является бинарным файлом, который JVM может выполнять. Всё, что нам осталось сделать, — создать такую JVM, которая бы выполняла его корректно.

Если мы заглянем внутрь Add.class с помощью шестнадцатеричного дампа — мы, скорее всего, будем не слишком впечатлены:

00000000 ca fe ba be 00 00 00 34 00 0f 0a 00 03 00 0c 07 |.......4........|
00000010 00 0d 07 00 0e 01 00 06 3c 69 6e 69 74 3e 01 00 |........<init>..|
00000020 03 28 29 56 01 00 04 43 6f 64 65 01 00 0f 4c 69 |.()V...Code...Li|
00000030 6e 65 4e 75 6d 62 65 72 54 61 62 6c 65 01 00 03 |neNumberTable...|
00000040 61 64 64 01 00 05 28 49 49 29 49 01 00 0a 53 6f |add...(II)I...So|
00000050 75 72 63 65 46 69 6c 65 01 00 08 41 64 64 2e 6a |urceFile...Add.j|
00000060 61 76 61 0c 00 04 00 05 01 00 03 41 64 64 01 00 |ava........Add..|
00000070 10 6a 61 76 61 2f 6c 61 6e 67 2f 4f 62 6a 65 63 |.java/lang/Objec|
00000080 74 00 21 00 02 00 03 00 00 00 00 00 02 00 01 00 |t.!.............|
00000090 04 00 05 00 01 00 06 00 00 00 1d 00 01 00 01 00 |................|
000000a0 00 00 05 2a b7 00 01 b1 00 00 00 01 00 07 00 00 |...*............|
000000b0 00 06 00 01 00 00 00 01 00 09 00 08 00 09 00 01 |................|
000000c0 00 06 00 00 00 1c 00 02 00 02 00 00 00 04 1a 1b |................|
000000d0 60 ac 00 00 00 01 00 07 00 00 00 06 00 01 00 00 |`...............|
000000e0 00 03 00 01 00 0a 00 00 00 02 00 0b |............|

Хотя мы еще не видим здесь четкой структуры, нам нужно найти способ ее разобрать: что значит ()V и (II)I, <init> и почему файл начинается с «cafe babe»?

Вероятно, вы знакомы с другим способом выгрузить class файлы, часто он оказывается более полезным:

$ javap -c Add
Compiled from "Add.java"
public class Add {
public Add();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return

public static int add(int, int);
Code:
0: iload_0
1: iload_1
2: iadd
3: ireturn
}

Теперь мы видим наш класс, его конструктор и метод. И конструктор, и метод содержат несколько инструкций. Становится более-менее ясно, что делает наш метод add(): он загружает два аргумента (iload_0 и iload_1), суммирует их и возвращает результат. JVM — это стековая машина, поэтому в ней нет регистров, все аргументы инструкций хранятся во внутреннем стеке, и результаты также помещаются в стек.

Class loader

Как нам добиться того же результата, который показала программа javap? Как разобрать class файл?

Если обратиться к спецификации JVM, мы узнаем о структуре файлов формата class. Он всегда начинается с 4-байтовой подписи (CAFEBABE), затем 2 + 2 байта для версии. Звучит просто!

Поскольку нам пришлось бы читать байты, short, int и байтовые последовательности из бинарного файла, начнем реализацию нашего загрузчика следующим образом:

type loader struct {
	r   io.Reader
	err error
}

func (l *loader) bytes(n int) []byte {
	b := make([]byte, n, n)
        // мы не хотим обрабатывать ошибки на каждом этапе,
        // поэтому просто сохраним первую найденную ошибку до конца
        // и ничего не делаем, если ошибка была найдена
	if l.err == nil {
		_, l.err = io.ReadFull(l.r, b)
	}
	return b
}
func (l *loader) u1() uint8  { return l.bytes(1)[0] }
func (l *loader) u2() uint16 { return binary.BigEndian.Uint16(l.bytes(2)) }
func (l *loader) u4() uint32 { return binary.BigEndian.Uint32(l.bytes(4)) }
func (l *loader) u8() uint64 { return binary.BigEndian.Uint64(l.bytes(8)) }

// Usage:
f, _ := os.Open("Add.class")
loader := &loader{r: f}
cafebabe := loader.u4()
major := loader.u2()
minor := loader.u2()

Затем спецификация сообщает нам, что необходимо распарсить пул констант. Что это? Так называется специальная часть class файла, которая содержит константы, необходимые для запуска класса. Все строки, числовые константы и ссылки хранятся там, и каждая имеет уникальный индекс uint16 (таким образом, класс может иметь до 64К констант).

В пуле есть несколько типов констант, каждый из которых содержит свой набор значений. Нам могут быть интересны:

• UTF8: простой строковый литерал
• Class: индекс строки, содержащей имя класса (косвенная ссылка)
• Name and type: индекс имени типа и дескриптор, используемый для полей и методов
• Field and method references: индексы, относящиеся к классам и константам типа name and type.

Как видите, константы в пуле часто ссылаются друг на друга. Поскольку мы пишем JVM на языке Go и здесь нет объединения типов (union types), давайте создадим тип Const, который будет содержать в себе различные возможные поля констант:

type Const struct {
	Tag              byte
	NameIndex        uint16
	ClassIndex       uint16
	NameAndTypeIndex uint16
	StringIndex      uint16
	DescIndex        uint16
	String           string
}
type ConstPool []Const

Затем, следуя спецификации JVM, мы могли бы извлечь данные пула констант следующим образом:

func (l *loader) cpinfo() (constPool ConstPool) {
	constPoolCount := l.u2()
	// Валидные индексы пула констант начинаются с 1
	for i := uint16(1); i < constPoolCount; i++ {
		c := Const{Tag: l.u1()}
		switch c.Tag {
		case 0x01: // UTF8 string literal, 2 bytes length + data
			c.String = string(l.bytes(int(l.u2())))
		case 0x07: // Class index
			c.NameIndex = l.u2()
		case 0x08: // String reference index
			c.StringIndex = l.u2()
		case 0x09, 0x0a: // Field and method: class index + NaT index
			c.ClassIndex = l.u2()
			c.NameAndTypeIndex = l.u2()
		case 0x0c: // Name-and-type
			c.NameIndex, c.DescIndex = l.u2(), l.u2()
		default:
			l.err = fmt.Errorf("unsupported tag: %d", c.Tag)
		}
		constPool = append(constPool, c)
	}
	return constPool
}

Сейчас мы сильно упрощаем себе задачу, но в реальной JVM нам пришлось бы обрабатывать типы констант long и double единообразно, вставляя дополнительный неиспользуемый постоянный элемент, как сообщает нам спецификация JVM (поскольку постоянные элементы считаются 32-битными).

Чтобы упростить получение строковых литералов по индексам, реализуем метод Resolve(index uint16) string:

func (cp ConstPool) Resolve(index uint16) string {
	if cp[index-1].Tag == 0x01 {
		return cp[index-1].String
	}
	return ""
}

Теперь нам нужно добавить похожие помощники для анализа списка интерфейсов, полей и методов классов и их атрибутов:

func (l *loader) interfaces(cp ConstPool) (interfaces []string) {
	interfaceCount := l.u2()
	for i := uint16(0); i < interfaceCount; i++ {
		interfaces = append(interfaces, cp.Resolve(l.u2()))
	}
	return interfaces
}

// Тип field используется и для полей и методов
type Field struct {
	Flags      uint16
	Name       string
	Descriptor string 
	Attributes []Attribute 
}

// Атрибуты содержат дополнительную информацию о полях и классах
// Самый полезный - это атрибут Code, который содержит актуальный байтовый код
type Attribute struct {
	Name string
	Data []byte
}

func (l *loader) fields(cp ConstPool) (fields []Field) {
	fieldsCount := l.u2()
	for i := uint16(0); i < fieldsCount; i++ {
		fields = append(fields, Field{
			Flags:      l.u2(),
			Name:       cp.Resolve(l.u2()),
			Descriptor: cp.Resolve(l.u2()),
			Attributes: l.attrs(cp),
		})
	}
	return fields
}

func (l *loader) attrs(cp ConstPool) (attrs []Attribute) {
	attributesCount := l.u2()
	for i := uint16(0); i < attributesCount; i++ {
		attrs = append(attrs, Attribute{
			Name: cp.Resolve(l.u2()),
			Data: l.bytes(int(l.u4())),
		})
	}
	return attrs
}

И поля, и методы представлены как Fields, это очень удобно, позволяет сэкономить время. Наконец, мы можем собрать всё это вместе и полноценно распарсить наш класс:

type Class struct {
	ConstPool  ConstPool
	Name       string
	Super      string
	Flags      uint16
	Interfaces []string
	Fields     []Field
	Methods    []Field
	Attributes []Attribute
}

func Load(r io.Reader) (Class, error) {
	loader := &loader{r: r}
	c := Class{}
	loader.u8()           // magic (u32), minor (u16), major (u16)
	cp := loader.cpinfo() // const pool info
	c.ConstPool = cp
	c.Flags = loader.u2()             // access flags
	c.Name = cp.Resolve(loader.u2())  // this class
	c.Super = cp.Resolve(loader.u2()) // super class
	c.Interfaces = loader.interfaces(cp)
	c.Fields = loader.fields(cp)    // fields
	c.Methods = loader.fields(cp)   // methods
	c.Attributes = loader.attrs(cp) // methods
	return c, loader.err
}

Теперь, если мы посмотрим на полученную информацию о классе, мы увидим, что у него нет полей и два метода — <init>:()V и add:(II)I. Что за римские числа со скобками? Это дескрипторы. Они определяют, какие типы аргументов принимает метод и что он возвращает. В этом случае <init> (синтетический метод, используемый для инициализации объектов при их создании) не принимает аргументов и ничего не возвращает (V=void), в то время как метод «add» принимает два типа данных int (I=int32) и возвращает целое число.

Байт-код

Если присмотреться внимательно, мы поймем, что каждый метод в нашем разобранном классе имеет один атрибут с именем «Code». Этот атрибут содержит часть байтов в качестве полезной нагрузки. Байты:

<init>:
[0 1 0 1 0 0 0 5 42 183 0 1 177 0 0 0 1 0 7 0 0 0 6 0 1 0 0 0 1]
add:
[0 2 0 2 0 0 0 4 26 27 96 172 0 0 0 1 0 7 0 0 0 6 0 1 0 0 0 3]

В спецификации, на этот раз в разделе bytecode, мы прочтем, что атрибут «Code» начинается со значения maxstack (2 байта), затем maxlocals (2 байта), длина кода (4 байта) и затем фактический код. Итак, наши атрибуты можно читать так:

<init>: maxstack: 1, maxlocals: 1, code: [42 183 0 1 177]
add: maxstack: 2, maxlocals: 2, code: [26 27 96 172]

Да, у нас есть только 4 и 5 байтов кода в каждом методе. Что означают эти байты?

Как я уже сказал, JVM — это стековая машина. Каждая инструкция кодируется как один байт, за которым могут следовать дополнительные аргументы. Заглянув в спецификацию, мы увидим, что метод «add» имеет следующие инструкции:

26 = iload_0
27 = iload_1
96 = iadd
172 = ireturn

Точно такие же, как мы видели в выводе javap в начале! Но как это сделать?

Фреймы JVM

Когда метод выполняется внутри JVM, у него есть собственный стек для временных операндов, свои локальные переменные и фрагмент кода для выполнения. Все эти параметры хранятся в едином фрейме выполнения. Кроме того, фреймы содержат указатель текущей инструкции (насколько далеко мы продвинулись при выполнении байт-кода) и указатель на класс, в котором содержится метод. Последний нужен для доступа к пулу констант класса, а также к другим деталям.

Давайте создадим метод, который создает фрейм для конкретного метода, вызванного с заданными аргументами. Я буду использовать здесь тип interface{} в качестве типа Value, хотя использование правильного объединения типов (union types), конечно, было бы более безопасным.

type Frame struct {
	Class  Class
	IP     uint32
	Code   []byte
	Locals []interface{}
	Stack  []interface{}
}

func (c Class) Frame(method string, args ...interface{}) Frame {
	for _, m := range c.Methods {
		if m.Name == method {
			for _, a := range m.Attributes {
				if a.Name == "Code" && len(a.Data) > 8 {
					maxLocals := binary.BigEndian.Uint16(a.Data[2:4])
					frame := Frame{
						Class:  c,
						Code:   a.Data[8:],
						Locals: make(
									[]interface{}, 
									maxLocals, 
									maxLocals
								),
					}
					for i := 0; i < len(args); i++ {
						frame.Locals[i] = args[i]
					}
					return frame
				}
			}
		}
	}
	panic("method not found")
}

Итак, мы получили Frame с инициализированными локальными переменными, пустым стеком и предварительно загруженным байт-кодом. Пришло время выполнить байт-код:

func Exec(f Frame) interface{} {
	for {
		op := f.Code[f.IP]
		log.Printf("OP:%02x STACK:%v", op, f.Stack)
		n := len(f.Stack)
		switch op {
		case 26: // iload_0
			f.Stack = append(f.Stack, f.Locals[0])
		case 27: // iload_1
			f.Stack = append(f.Stack, f.Locals[1])
		case 96:
			a := f.Stack[n-1].(int32)
			b := f.Stack[n-2].(int32)
			f.Stack[n-2] = a + b
			f.Stack = f.Stack[:n-1]
		case 172: // ireturn
			v := f.Stack[n-1]
			f.Stack = f.Stack[:n-1]
			return v
		}
		f.IP++
	}
}

Наконец, мы можем собрать все вместе и запустить, вызвав наш метод add():

f, _ := os.Open("Add.class")
class, _ := Load(f)
frame := class.Frame("add", int32(2), int32(3))
result := Exec(frame)
log.Println(result)

// OUTPUT:
OP:1a STACK:[]
OP:1b STACK:[2]
OP:60 STACK:[2 3]
OP:ac STACK:[5]
5

Итак, всё работает. Да, это очень слабая JVM на минималках, но все же она делает то, что и должна JVM: загружает байт-код и интерпретирует его (конечно, настоящая JVM делает гораздо большее).

Чего не хватает?

Оставшихся 200 инструкций, среды выполнения, системы типов ООП и еще нескольких вещей.

Существует 11 групп инструкций, большинство из которых банальны:

• Constants (помещает null, small number или значения из пула констант на стек).
• Loads (помещает в стек локальные переменные). Подобных инструкций 32.
• Stores (перемещают из стека в локальные переменные). Еще 32 скучных инструкции.
• Stack (pop/dup/swap), как в любой стековой машине.
• Math (add/sub/div/mul/rem/shift/logic). Для разных типов значений, всего 36 инструкций.
• Conversions (int в short, int в float и т.д.).
• Comparisons (eq/ne/le/…). Полезно для создания условных выражений, например с if/else.
• Control (goto/return). Пригодится для циклов и подпрограмм.
• References. Самая интересная часть, поля и методы, исключения и мониторы объекта.
• Extended. На первый взгляд выглядит не очень красивым решением. И, вероятно, со временем это не изменится.
• Reserved. Здесь находится инструкция точки останова 0xca.

Большинство инструкций несложно реализовать: они берут один или два аргумента из стека, выполняют над ними некоторую операцию и отправляют результат. Единственное, что здесь следует иметь в виду, — инструкции для типов long и double предполагают, что каждое значение занимает два слота в стеке, поэтому вам могут потребоваться дополнительные push() и pop(), что затрудняет группировку инструкций.

Для реализации References необходимо подумать об объектной модели: как вы хотите хранить объекты и их классы, как представлять наследование, где хранить поля экземпляров и поля классов. Кроме того, здесь вы должны быть осторожны с диспетчеризацией методов — существует несколько инструкций «invoke», и они ведут себя по-разному:

• invokestatic: вызвать статический метод в классе, никаких сюрпризов.
• invokespecial: вызвать метод экземпляра напрямую, в основном используется для синтетических методов, таких как <init> или приватных методов.
• invokevirtual: вызвать метод экземпляра на основе иерархии классов.
• invokeinterface: вызывает метод интерфейса, аналогичный invokevirtual, но выполняет другие проверки и оптимизацию.
• invokedynamic: вызвать динамически вычисляемый call site, в новой версии Java 7, полезно для динамических методов и MethodHandles.

Если вы создаете JVM на языке без сборки мусора, в таком случае вам следует подумать, как ее выполнить: подсчет ссылок, алгоритм пометок (mark-and-sweep) и т. д. Обработка исключений путем реализации athrow, их распространения через фреймы и обработка с помощью таблиц исключений — еще одна интересная тема.

Наконец, ваша JVM останется бесполезной, если нет runtime классов. Без java/lang/Object вы вряд ли даже увидите, как работает new инструкция при создании новых объектов. Ваша среда выполнения может предоставлять некоторые общие классы JRE из пакетов java.lang, java.io и java.util, или это может быть что-то более специфичное для домена. Скорее всего, некоторые методы в классах должны быть реализованы изначально, а не на Java. Это поднимет вопрос о том, как найти и выполнить такие методы, и станет еще одним крайним случаем для вашей JVM.

Другими словами, создать правильную JVM не так уж и просто, однако разобраться, как именно она работает, — не сложно.

У меня, например, на это ушли всего одни летние выходные. Моей JVM еще предстоит долгий путь, но структура выглядит более или менее ясной: https://github.com/zserge/tojvm (замечания всегда приветствуются!)

Фактические фрагменты кода из этой статьи еще меньше и доступны здесь как gist.

Если появилось желание изучить вопрос лучше, вы можете подумать об использовании небольших JVM:

• Mika: https://github.com/kifferltd/open-mika
• Avian: https://github.com/ReadyTalk/avian
• NanoVM: https://github.com/harbaum/NanoVM
• Luje: https://github.com/davidgiven/luje (прекрасная JVM для LuaJIT)

Надеюсь, эта статья не отбила ваш интерес к Java. Виртуальные машины — это весело, а виртуальная машина Java действительно заслуживает внимательного рассмотрения.

Надеюсь, вам понравилась моя статья. Вы можете следить за моей работой через Github или Twitter, а также подписываться через rss.