Pull to refresh

Хардкорные Java/JVM задачки

Reading time 10 min
Views 24K

Перформансные задачи от Контура уже были, настала и наша очередь: представляем хардкорные задачи с Java-конференции JBreak 2018, aka «ад от Excelsior».


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


Задача 1


Ваш коллега начитался Java Language Specification и написал следующее:


void playWithRef() {
    Object obj = new Object();
    WeakReference<Object> ref = new WeakReference<>(obj);
    System.out.println(ref.get() != null);
    System.gc();
    System.out.println(ref.get() != null);
}

А разгребать вам: какие результаты исполнения возможны?


  • A: false, false
  • B: false, true
  • C: true, false
  • D: true, true

Ответ и решение

Правильный ответ: A, C, D.


Решение

Область видимости переменной obj — весь метод, а область жизни заканчивается после выхода из конструктора WeakReference (на самом деле, даже чуть раньше — во внутренностях конструктора). И именно область жизни влияет на то, может ли GC уничтожить этот объект.


Однако иногда VM может продлевать область жизни переменных, если ей это удобно. Например, интерпретатор HotSpot сообщает GC, что переменные живы, пока они видимы (именно это можно наблюдать в отладчике). То есть вариант D легко достигается при запуске примера без каких-либо дополнительных опций на HotSpot VM (или с явным -Xint).


Результат C достигается на многих компиляторах (например, HotSpot C1/C2, Excelsior JET JIT & AOT, ...). Компиляторы достаточно умные, чтобы вычислить, что переменная obj не используется и уже к первому вызову get() ничто не мешает GC уничтожить объект. Однако чаще всего GC придет только при явном вызове System.gc(), это поведение проявляется на HotSpot VM с -Xcomp или на Excelsior JET в любом режиме.


Вариант A теоретически достижим, если GC придет, например, в конце исполнения конструктора WeakReference.


Задачка основана на баге в коде JDK 8, где аргумент метода неаккуратно сохранялся в WeakReference и умирал во время исполнения метода. Про это есть отдельный развернутый пост в нашем техническом блоге.


Задача 2


Злой хакер удалил исходный Java-файл и перемешал куски вашего класс-файла:


A: 0700 0401 0001 4300 2000 0300 0100 0000
B: 0000 0000 00
C: 6a61 7661 2f6c 616e 672f 4f62 6a65 6374
D: cafe babe 0000 0031 0005 0700 0201 0010

Переставьте их таким образом, чтобы получился верифицируемый класс-файл.


Ответ и решение

Правильный ответ: D, C, A, B.


Решение

Эта задача скорее на смекалку, но все же учит чему-то новому.


Широко известно, что класс-файл начинается с четырехбайтового заголовка 0xCAFEBABE, значит D точно идет первым. Здравый смысл подсказывает, что короткий кусок B идет последним — это хвост.


Далее можно было вспомнить, что в класс-файле имеется ConstantPool, в котором имеются строковые константы состоящие из двухбайтовой длины и собственно строки, закодированной в UTF-8. Единственным куском, похожим на UTF-8 является кусок C — это UTF-8 представление строки java/lang/Object (ссылка на супер-класс нашего класса). Значит перед ней должны быть байты 0x0010 (строка имеет длину 16), и единственный подходящий вариант — D, то есть C — вторая.


Альтернативно можно было заметить, что вся последняя строка B состоит из нулей, значит и предпоследняя должна оканчиваться на нули, то есть это A!


Вывод javap
class C
  minor version: 0
  major version: 49
  flags: ACC_SUPER
Constant pool:
  #1 = Class   #2                // java/lang/Object
  #2 = Utf8    java/lang/Object
  #3 = Class   #4                // C
  #4 = Utf8    C
{
}

Задача 3


Прослушав очередной доклад про Graal, вдохновенно посмотрев на JVM Compiler Interface, вы решили написать свой компилятор для Java! И решили начать с генерации x86_64 кода для метода:


static boolean invert(boolean x) {
    return !x;
}

Какой сгенерированный код будет корректным для такого метода?


Легенда: используется Intel-синтаксис, соглашение о вызовах таково, что на регистре rcx лежит аргумент, на rax — результат.


A:      test ecx, ecx
        jnz True
        mov eax, 1
        ret
True:   mov eax, 0
        ret

B:      xor eax, eax
        test ecx, ecx
        jnz End
        add eax, 1
End:    ret

C:      mov eax, 1
        sub eax, ecx
        ret

D:      mov eax, ecx
        xor eax, 1
        ret

Ответ и решение

Правильный ответ: A, B.


Решение

Все чаще на Java-конференциях можно увидеть ассемблерные листинги, но на случай, если вы еще не знакомы с системой команд Intel x86, ниже представлен эквивалентный C код:


A: res = (arg == 0) ? 1 : 0;
B: res = 0; if (arg == 0) res += 1;
C: res = 1; res -= arg;
D: res = arg; res ^= 1;

На самом деле все эти алгоритмы инвертирования корректно работают, пока входной аргумент принимает привычные логические значения 0 и 1.


Далее начинается интересное. С точки зрения верификатора все короткие целочисленные типы (boolean, byte, char, short) эквиваленты типу int. Более того, boolean-специфичных байт-кодных инструкций и вовсе не существует. Например, байт-кодные инструкции исследуемого метода таковы:


public static boolean invert(boolean);
  0: iload_0
  1: ifne      8
  4: iconst_1
  5: goto      9
  8: iconst_0
  9: ireturn

Таким образом, метод, принимающий boolean, должен быть готов работать с любым int-ом, причем любое ненулевое значение трактуется как true. В этом случае «оптимизированные» варианты C и D начинают вести себя некорректно C(2) = -1 и D(2) = 3, а более прямолинейные A и B продолжают работать A(2) = B(2) = 0.


Чтобы проиллюстрировать эти тонкости придется манипулировать байт-кодом. Пример доступен на GitHub: в метод invert передаются числа 0, 1, 2, 3, -1 и выводится результат, сопровождаемый вызовами println(boolean) и println(int).


Любопытный факт: в JDK 8 компилятор HotSpot C2 генерировал вариант D, а в JDK 9 шаблон генерации поменялся на более корректный.


Код, генерируемый HotSpot C2 на Intel x86_64

В JDK 8 хорошо виден шаблон D и выдаваемый некорректный результат:


$ jdk8/bin/java -Xcomp -Xbatch -XX:-TieredCompilation -XX:CompileCommand=print,Inverter.invert -XX:+UnlockDiagnosticVMOptions -XX:PrintAssemblyOptions=intel BooleanHell

...
Compiled method (c2)    1216  533             Inverter::invert (10 bytes)
...
  # {method} {0x0000000012600d08} 'invert' '(Z)Z' in 'Inverter'
  # parm0:    rdx       = boolean
  #           [sp+0x20]  (sp of caller)
  0x00000000057d7ac0: sub    rsp,0x18
  0x00000000057d7ac7: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - Inverter::invert@-1 (line 3)

  0x00000000057d7acc: mov    eax,edx
  0x00000000057d7ace: xor    eax,0x1            ;*ireturn
                                                ; - Inverter::invert@9 (line 3)

  0x00000000057d7ad1: add    rsp,0x10
  0x00000000057d7ad5: pop    rbp
  0x00000000057d7ad6: test   DWORD PTR [rip+0xfffffffffdf58524],eax        # 0x0000000003730000
                                                ;   {poll_return}
  0x00000000057d7adc: ret
...

false (0) -> true (1)
true (1) -> false (0)
true (2) -> true (3)
true (3) -> true (2)
true (-1) -> true (-2)

В JDK 9 улучшили нормализацию boolean значений: добавилось приведение входного аргумента к диапазону {0, 1} (инструкции test и setne) и результат стал корректным:


$ jdk9/bin/java -Xcomp -Xbatch -XX:-TieredCompilation -XX:CompileCommand=print,Inverter.invert -XX:+UnlockDiagnosticVMOptions -XX:PrintAssemblyOptions=intel BooleanHell

...
Compiled method (c2)    4702 1496             Inverter::invert (10 bytes)
...
  # {method} {0x000001fa974d2dc0} 'invert' '(Z)Z' in 'Inverter'
  # {method} {0x000001fa974d2dc0} 'invert' '(Z)Z' in 'Inverter'
  # parm0:    rdx       = boolean
  #           [sp+0x20]  (sp of caller)
  0x000001fafcb57720: sub    rsp,0x18
  0x000001fafcb57727: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - Inverter::invert@-1 (line 3)

  0x000001fafcb5772c: test   edx,edx
  0x000001fafcb5772e: setne  al
  0x000001fafcb57731: movzx  eax,al
  0x000001fafcb57734: xor    eax,0x1            ;*ireturn {reexecute=0 rethrow=0 return_oop=0}
                                                ; - Inverter::invert@9 (line 3)

  0x000001fafcb57737: add    rsp,0x10
  0x000001fafcb5773b: pop    rbp
  0x000001fafcb5773c: test   DWORD PTR [rip+0xfffffffffdf688be],eax        # 0x000001fafaac0000
                                                ;   {poll_return}
  0x000001fafcb57742: ret
...

false (0) -> true (1)
true (1) -> false (0)
true (2) -> false (0)
true (3) -> false (0)
true (-1) -> false (0)

Задача 4


Неожиданно вы поняли, что вам очень интересно, что может вывести вызов такого метода:


void guessWhat(Iterable<?> x) {
    System.out.println(x.getClass());
}

  • A: class java.util.ArrayList
  • B: null
  • C: interface java.lang.Iterable
  • D: class java.lang.Integer

Ответ и решение

Правильный ответ: A, D.


Решение

Варианты B и C невозможны, так как Object.getClass() всегда возвращает ненулевой класс, а экземпляров интерфейсного типа не бывает. Вариант A легко реализуется: guessWhat(new ArrayList<Object>()).


Однако и вариант D достижим: Integer не реализует интерфейс Iterable, но тем не менее его экземпляр может прийти в этот метод. Разгадка в том, что строгость типовой системы языка Java снова пала под слабостью типовой системы верификатора JVM: любой ссылочный тип совместим по присваиванию с любым интерфейсом. То есть почти всюду, где ожидают интерфейсный тип (включая параметры, возвращаемое значение, поля), можно передать любое ссылочное значение (то есть произвольные классы и массивы).


Этот эффект можно продемонстрировать либо с помощью манипуляций с байт-кодом, либо с помощью частичной перекомпиляции класс-файлов.


Задача 5


В очередной раз поверив в непогрешимость javac, вы решили поэкспериментировать:


class C {
    private boolean getBoolean() {
        return false;
    }
}

interface I {
    default boolean getBoolean() {
        return true;
    }
}

class D extends C implements I {}

public class Test {
    public static void main(String[] a) {
        foo(new D());
    }

    public static void foo(I i) {
        System.out.println(i.getBoolean());
    }
}

Что случится при попытке скомпилировать и запустить класс Test?


  • A: Не скомпилируется
  • B: Выбросится java.lang.IllegalAccessError
  • C: Напечатается «true»
  • D: Напечатается «false»

Ответ и решение

Правильный ответ: B.


Решение

Многие верят, что IllegalAccessError — это удел тех, кто перемудрил с частичной перекомпиляцией или обфускацией. Так было и у нас, когда ProGuard во время обфускации дал двум разным методам (один private, другой default) одинаковые имена, и результирующее приложение стало выбрасывать IllegalAccessError.


Однако оказалось, что если два таких метода будут иметь одинаковые имена сразу в исходном коде, то javac скомпилирует их без каких-либо предупреждений, а во время исполнения также выбросится IllegalAccessError.


Такое поведение JVM объясняется тем, как происходит поиск целевого метода для инструкции invokeinterface. Согласно спецификации, в первую очередь просматриваются instance-методы класса и всех супер-классов, и только затем ищется подходящий default метод среди супер-интерфейсов, при этом приватность найденного метода проверяется только после завершения всего процесса.


Таким образом, поиск заканчивается на private методе getBoolean из супер-класса C, который встал на пути поиска default метода getBoolean из супер-интерфейса I. После этого уже логично выбрасывается IllegalAccessError.


Интересно, что в Java 11 это планируется изменить, и в процессе поиска пропускать приватные методы.


Задача 6


Внезапно вы обнаруживаете себя отлаживающим нативный код скомпилированного Java приложения. У вас нет исходников, но вы уже нашли проблемный метод, вот он:


1:     lea   rax, [rel _Test_foo]
2:     push  rax
3:     mov   eax, dword [rcx+0FH]
4:     idiv  dword [rdx+0FH]
5:     mov   rbx, qword [rel _Test_array]
6:     mov   ebx, dword [rbx+3BH]
7:     add   eax, ebx
8:     ret   8

Вы заподозрили, что исполнение этого метода может спровоцировать выброс Java исключений различных типов. Осталось понять, какие инструкции могут быть виноваты (укажите их номера)?


  • StackOverflowError: _________
  • NullPointerException: _________
  • ArithmeticException: _________
  • IndexOutOfBoundsException: _________

Ответ и решение

Правильный ответ:


  • StackOverflowError: 2
  • NullPointerException: 3, 4, 6
  • ArithmeticException: 4
  • IndexOutOfBoundsException: никакая

Решение

Компилятор может генерировать проверки исключительных ситуаций разными способами. Например, перед обращением к полю объекта можно сгенерировать явную проверку объекта на отличие от null с выбросом исключения в случае провала. Однако, такие явные проверки негативно влияют на производительность и размер кода. Поэтому компилятор старается обходиться неявными проверками: генерируется только код разыменования указателя, который в случае нулевого указателя приведет к возникновению аппаратного исключения, которое JVM перехватит, распознает и перевыбросит как соответствующее Java-исключение.


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


StackOverflowError возникает при попытке записать/прочитать очередной стековый слот за пределами разрешенного диапазона. Это может происходить в инструкции push rax.


На выброс неявного ArithmeticException есть также единственный кандидат: инструкция целочисленного деления idiv dword [rdx+0FH]. Если разыменованное значение равно нулю, случится аппаратное деление на ноль с последующим выбросом ArithmeticException.


Неявные проверки, где может быть выброшено NullPointerException, очень популярны в Java-коде. Чтобы найти их, достаточно рассмотреть все места, где что-либо разыменовывается. Инструкция mov rbx, qword [rel _Test_array] разыменовывает статические данные по относительному адресу, поэтому никогда не может приводить к ошибкам. А вот инструкции mov eax, dword [rcx+0FH], idiv dword [rdx+0FH], mov ebx, dword [rbx+3BH] разыменовывают параметры метода и прочитанные статические данные, то есть могут выбросить NullPointerException.


Интересно, что инструкция idiv dword [rdx+0FH] содержит сразу две неявные проверки, что порой может доставлять массу проблем JVM.


Неявная проверка на IndexOutOfBoundsException должна быть в инструкции, обращающейся к элементу массива. Подсказкой служит чтение некоего _Test_array на регистр и его разыменование в инструкциях 5 и 6. Однако нужно заметить, что при таком шаблоне генерации доступа к элементу массива, индексы, выходящие за допустимый диапазон, будут просто обращаться к памяти в куче, соседней с массивом, что не провоцирует никаких аппаратных исключений. Поэтому на большинстве процессорных архитектур проверки на IndexOutOfBoundsException генерируются явно. Однако в редких случаях компилятор может доказать, что такая проверка и вовсе не нужна, что и происходит в данной задаче. То есть тут вообще не может быть выброшено IndexOutOfBoundsException.


Задача 7


Злой хакер снова взломал ваш компьютер и отредактировал в hex-редакторе Helper.class таким образом, что концовка метода sayC стала неверифицируема:


public class Main {
    public static void main(String[] args) {
        System.out.print("A");
        Helper.sayB();
        Helper.sayC();
    }
}

public class Helper {
    public static void sayB() {
        System.out.print("B");
    }

    public static void sayC() {
        System.out.print("C");
        // bad bytecode goes here
    }
}

Что произойдет при запуске класса Main?


  • A: Выбросится VerifyError
  • B: Напечатается «A» и выбросится VerifyError
  • C: Напечатается «AB» и выбросится VerifyError
  • D: Напечатается «ABC» и выбросится VerifyError

Ответ и решение

Правильный ответ: B.


Решение

Верификация байт-кода некоторого класса отрабатывает до того, как какой-либо метод этого класса исполнится. В классе Helper есть неверифицируемый метод sayC, значит и весь класс целиком неверифицируемый. Таким образом варианты C и D точно неправильные: исполнение никогда не дойдет до метода sayB.


Далее нужно понять, в какой момент выбрасывается VerifyError. По спецификации, ошибки разрешения ссылок должны выбрасываться тогда, когда ссылка требуется при исполнении, даже если у JVM разрешение ссылок энергичное (все ссылки разрешаются сразу при загрузке класса). В данной задаче ссылка на Helper нужна только после вывода «A», поэтому правильный ответ — B.


Наглядный пример демонстрирует описанное поведение. Неверифицируемый байт-код получен с помощью ручных манипуляций.


Подробнее про верификацию Java байт-кода рассказывал Никита Липский aka pjBooms на JBreak 2018 (пока только слайды) и на JPoint 2017 (есть видео).


Заключение


Хотя на конференции некоторые пугались от вида ассемблера, нашлось довольно много людей, решивших погрузиться в тонкости работы JVM: всем, сдавшим задачи на наш стенд, мы проводили экспресс-курс про тонкости байт-кода, верификатора и неявных исключений. Надеюсь, и вы, прочитав решения, узнали что-то новое. Если так, то наша цель достигнута!

Only registered users can participate in poll. Log in, please.
И напоследок опрос. Какие задачи вам понравились?
73.95% 1 про WeakReference 88
32.77% 2 про перемешанный класс-файл 39
35.29% 3 про генерацию !x 42
57.14% 4 про интерфейсные переменные 68
65.55% 5 про default и private методы 78
31.09% 6 про неявные исключения 37
42.02% 7 про верификатор 50
119 users voted. 72 users abstained.
Tags:
Hubs:
+30
Comments 23
Comments Comments 23

Articles