07.09.2017 02:20
divan0 2 3500 Источник

В Go есть хорошая поддержка вызова ассемблерных функций, и большое количество очень быстрого криптографического кода в стандартной библиотеке это, на самом деле, хорошо оптимизированный ассемблер, дающий более чем 20-кратный прирост в скорости.


Но писать код на ассемблере, всё же, сложно, анализировать его ещё сложнее, а криптография ошибок не прощает. Разве не было бы замечательно иметь возможность писать эти функции на каком-нибудь более высокоуровневом языке?


Этот пост о слегка неадекватном эксперименте по вызову Rust кода из Go в попытке сделать это настолько быстро, чтобы могло сравнится с вызовом ассемблера. Вам не нужно знать Rust или про внутренности компилятора, достаточно понимать, что такое линкер.


Почему Rust?


Признаюсь сразу — я не знаю Rust и мысль о том, чтобы писать на нём меня не сильно привлекает. Но всё же, я знаю, что Rust очень хорошо настраиваемый и оптимизируемый язык, при этом более читабельный, чем ассемблер. (В конце концов, всё более читабельное, чем ассемблер!)


В Go дефолтные значения принято выбирать так, чтобы они подходили под основные задачи, и включать по умолчанию только те фичи, которые гарантированно быстры — это помогает в постоянной и успешной борьбе с необходимостью иметь кучу параметров. Я люблю его за это. Но то для того, что мы будем делать сегодня, нам нужен будет язык, который и глазом не моргнёт, если мы попросим его сгенерировать stack-only функции с отключенными проверками на безопасность.


И если есть такой язык, который мы могли бы ограничить достаточно, чтобы он вёл себя, как ассемблер, и заоптимизировать его достаточно, чтобы он был также эффективен как ассемблер, это, скорее всего, будет именно Rust.


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


Почему не cgo?


В Go есть из коробки Foreign Function Interface, cgo. cgo позволяет Go программам вызывать C функции самым естественным образом — который, к сожалению, вообще ни разу не естественен. (Я знаю про cgo больше, чем мне хотелось бы, и, поверьте, это совсем не весело).


Используя C ABI как "лингва франка" для FFI, мы можем вызывать что угодно откуда угодно: Rust может скомпилироваться в библиотеку, которая совместима с C ABI, и cgo можем этим воспользоваться. Это тупо, но это работает.


Мы можем сделать даже наоборот — скомпилировать Go в C библиотеку и вызывать её из разных языков, как я, например, сделал с Python в качестве трюка. (Народ, это был лишь трюк, не воспринимайте это серьезно)


Но cgo делает много чего под капотом, чтобы добавить немного Go естественности: он организует стек для С кода, он настроит defer-вызовы, чтобы корректно работали в случае паники в Go вызове… об этом можно отдельный пост написать.


Но как результат, стоимость каждого cgo вызова слишком высока для того случая, о котором мы сегодня говорим — маленькие шустрые функции.


Связываем всё вместе


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


Мы не хотим работать с ним на уровне промежуточного представления IR: компилятор Go конвертирует и Go код и ассемблер в машинный код до того как ликовать ещё начиная с Go 1.3.


Это подтверждается и наличием такого понятия, как "внешняя линковка", когда системный линкер используется, чтобы слинковать программу на Go. Это именно как cgo и работает: сначала С компилируется С компилятором, Go — Go компилятором, и всё это линкуется вместе с помощью clang или gcc. Мы можем даже напрямую передавать флаги линкору через CGO_LDFLAGS.


Под капотом всех всех мер безопасности в cgo, мы, конечно же, найдем сам межязыковой вызов, в конце концов.


Но было бы здорово найти способ это делать без изменения компилятора, конечно. Сначала давайте разберёмся, как можно слинковать Go программу с архивом Rust.


Я не смог найти нормальный способ слинковать с чужеродным бинарном с помощью go build (да и с чего бы?), кроме как использовать #cgo директивы. Но вызов cgo создает .s файлы, которые дальше передаются C компилятору, а не Go, а это значит, друзья, что нам нужен будет ассемблер Go.


К счастью, go/build это всего лишь фронтенд! Go предлагает набор низкоуровневых утилит для компиляции и линковки программ, и go build всего лишь собирает файлы в кучу и запускает эти утилиты. Мы можем проследить, что происходит с помощью флага -x.


Я написал маленький Makefile по аналогии с -x -ldflags "-v -linkmode=external '-extldflags=-v'" вызовом при сборке cgo:


rustgo: rustgo.a  
        go tool link -o rustgo -extld clang -buildmode exe -buildid b01dca11ab1e -linkmode external -v rustgo.a

rustgo.a: hello.go hello.o  
        go tool compile -o rustgo.a -p main -buildid b01dca11ab1e -pack hello.go
        go tool pack r rustgo.a hello.o

hello.o: hello.s  
        go tool asm -I "$(shell go env GOROOT)/pkg/include" -D GOOS_darwin -D GOARCH_amd64 -o hello.o hello.s

Это соберет простенький пакет main, состоящий из одного Go файла (hello.go) и ассемблерного файла Go (hello.s).


Теперь, если мы хотим слинковать объект на Rust, мы сначала должны собрать его как статическую библиотеку...


libhello.a: hello.rs  
        rustc -g -O --crate-type staticlib hello.rs

… и затем просто сказать внешнему линкеру слинковать их вместе:


rustgo: rustgo.a libhello.a  
        go tool link -o rustgo -extld clang -buildmode exe -buildid b01dca11ab1e -linkmode external -v -extldflags='-lhello -L"$(CURDIR)"' rustgo.a

$ make
go tool asm -I "/usr/local/Cellar/go/1.8.1_1/libexec/pkg/include" -D GOOS_darwin -D GOARCH_amd64 -o hello.o hello.s  
go tool compile -o rustgo.a -p main -buildid b01dca11ab1e -pack hello.go  
go tool pack r rustgo.a hello.o  
rustc --crate-type staticlib hello.rs  
note: link against the following native artifacts when linking against this static library

note: the order and any duplication can be significant on some platforms, and so may need to be preserved

note: library: System

note: library: c

note: library: m

go tool link -o rustgo -extld clang -buildmode exe -buildid b01dca11ab1e -linkmode external -v -extldflags="-lhello -L/Users/filippo/code/misc/rustgo" rustgo.a  
HEADER = -H1 -T0x1001000 -D0x0 -R0x1000  
searching for runtime.a in /usr/local/Cellar/go/1.8.1_1/libexec/pkg/darwin_amd64/runtime.a  
searching for runtime/cgo.a in /usr/local/Cellar/go/1.8.1_1/libexec/pkg/darwin_amd64/runtime/cgo.a  
 0.00 deadcode
 0.00 pclntab=166785 bytes, funcdata total 17079 bytes
 0.01 dodata
 0.01 symsize = 0
 0.01 symsize = 0
 0.01 reloc
 0.01 dwarf
 0.02 symsize = 0
 0.02 reloc
 0.02 asmb
 0.02 codeblk
 0.03 datblk
 0.03 sym
 0.03 headr
 0.06 host link: "clang" "-m64" "-gdwarf-2" "-Wl,-headerpad,1144" "-Wl,-no_pie" "-Wl,-pagezero_size,4000000" "-o" "rustgo" "-Qunused-arguments" "/var/folders/ry/v14gg02d0y9cb2w9809hf6ch0000gn/T/go-link-412633279/go.o" "/var/folders/ry/v14gg02d0y9cb2w9809hf6ch0000gn/T/go-link-412633279/000000.o" "-g" "-O2" "-lpthread" "-lhello" "-L/Users/filippo/code/misc/rustgo"
 0.34 cpu time
12641 symbols  
5764 liveness data

Переходим к Rust


Хорошо, мы слинковали, но символы сами по себе ничего не могут сделать, просто сидя в бинарном файле друг рядом с другом. Мы должны как-то вызвать Rust функцию из нашего Go кода.


Мы уже знаем, как вызвать Go функцию из Go. В ассемблере этот вызов будет выглядеть как CALL hello(SB), где SB это виртуальный регистр, доступный всем глобальным символам.


Если же мы хотим вызвать функцию на ассемблере из Go, мы должны дать знать компилятору о ней — что-то вроде C заголовка, написав просто func hello() без тела функции.


Я перепробовал все вышеописанные комбинации вызовов для внешней Rust функции, но все они жаловались на то, что либо не видят символ, либо тела функции.


Но cgo, который в конце концов всего лишь большой кодогенератор, как-то же умудряется в итоге вызывать эту чужеродную функцию! Но как?


Я наткнулся на ответ несколькими днями позже.


//go:cgo_import_static _cgoPREFIX_Cfunc__Cmalloc
//go:linkname __cgofn__cgoPREFIX_Cfunc__Cmalloc _cgoPREFIX_Cfunc__Cmalloc
var __cgofn__cgoPREFIX_Cfunc__Cmalloc byte  
var _cgoPREFIX_Cfunc__Cmalloc = unsafe.Pointer(&__cgofn__cgoPREFIX_Cfunc__Cmalloc)

Это выглядит как интересная pragma! //go:linkname просто создает алиас на символ в локальной области видимости (которую можно использовать для вызова приватных функций!), и я более чем уверен, что трюк с byte тут всего лишь для каких-то манипуляций с адресом, но вот //go:cgo_import_static… это импортирует внешний символ!


Вооружившись этим новым знанием и вышеприведенным Makefile-ом, у нас есть шанс таки вызвать функцию из Rust(hello.rs)


#[no_mangle]
pub extern fn hello() {  
    println!("Hello, Rust!");
}

(Колдовство с no-mangle/pub/extern взято из этого туториала)


И, вызываем из этой программы на Go (hello.go):


package main

//go:cgo_import_static hello

func trampoline()

func main() {  
    println("Hello, Go!")
    trampoline()
}

С помощью этого примера на ассемблере (hello.s):


TEXT ·trampoline(SB), 0, $2048  
    JMP hello(SB)
    RET

CALL был слишком замудрен для использования, но вот используя простой JMP...


Hello, Go!  
Hello, Rust!  
panic: runtime error: invalid memory address or nil pointer dereference  
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x0]

Ну, программа упала при попытке выйти. И вот это $2048 значение это весь стек, который дан Rust (если оно вообще стек помещает туда, куда надо) и не спрашивайте меня, что случится, если Rust попробует хоть коснуться кучи… но, черт, я удивлён, что оно вообще работает!


Соглашения о вызовах


Теперь если мы хотим чисто выходить из программы и передавать какие-то аргументы, мы должны более детально посмотреть на соглашения о вызовах в Go и Rust. Эти соглашения определяют, где находятся аргументы и возвратные значения между вызовами функций.


Соглашения о вызовах Go описаны тут и вот тут. Для Rust мы должны будем посмотреть на стандарт для FFI, который просто станадартное соглашение для C.


Чтобы продолжать, нам понадобится дебаггер. (LLDB поддерживает Go, но точки останова глючат на MacOS X, так что я должен был делать это внутри привилегированного Docker-контейнера)



Соглашение о вызовах Go



Соглашение о вызовах в Go по большей части недокументировано, но нам нужно его понять, чтобы продолжать дальше, так что вот, что мы можем выучить из этого листинга дизассемблера (amd64). Давайте посмотрим на очень простую функцию:


// func foo(x, y uint64) uint64
TEXT ·foo(SB), 0, $256-24  
    MOVQ x+0(FP), DX
    MOVQ DX, ret+16(FP)
    RET

У foo есть 256 (0x100) байт локального фрейма, 16 байт аргументов, 8 байт на возвратное значение, и она просто возвращает свой первый аргумент:


func main() {  
    foo(0xf0f0f0f0f0f0f0f0, 0x5555555555555555)

rustgo[0x49d785]:  movabsq $-0xf0f0f0f0f0f0f10, %rax  
rustgo[0x49d78f]:  movq   %rax, (%rsp)  
rustgo[0x49d793]:  movabsq $0x5555555555555555, %rax  
rustgo[0x49d79d]:  movq   %rax, 0x8(%rsp)  
rustgo[0x49d7a2]:  callq  0x49d8a0                  ; main.foo at hello.s:14

Вызывающий код выше делает очень мало: помещает аргументы на стек в обратном порядке, внизу своего фрейма (с rsp до 16(rsp), помним, что стек растёт вниз) и вызывает CALL. Вызов CALL запушит указатель на значение возврата на стек и сделает переход. Никакой очистки вызывающего функцию тут нет, простой RET в конце.


Заметьте, что rsp фиксирован, и у нас тут movq вместо push:


rustgo`main.foo at hello.s:14:  
rustgo[0x49d8a0]:  movq   %fs:-0x8, %rcx  
rustgo[0x49d8a9]:  leaq   -0x88(%rsp), %rax  
rustgo[0x49d8b1]:  cmpq   0x10(%rcx), %rax  
rustgo[0x49d8b5]:  jbe    0x49d8ee                  ; main.foo + 78 at hello.s:14  
                   [...]
rustgo[0x49d8ee]:  callq  0x495d10                  ; runtime.morestack_noctxt at asm_amd64.s:405  
rustgo[0x49d8f3]:  jmp    0x49d8a0                  ; main.foo at hello.s:14

Первые 4 и последние 2 инструкции функции проверяют, достаточно ли места на стеке, и если нет, то вызывают runtime.morestack. Они, скорее всего, пропускаются для функций помеченных NOSPLIT:


rustgo[0x49d8b7]:  subq   $0x108, %rsp  
                   [...]
rustgo[0x49d8e6]:  addq   $0x108, %rsp  
rustgo[0x49d8ed]:  retq

Потом у нас идёт управление rsp, в котором вычитается 0x108, освобождая место для 0x100 байт для фрейма и 8 байт для указателя, за один раз. В итоге rsp указывает на низ (конец) фрейма функции и управляется вызываемой функцией. Перед тем, как возвращать, rsp возвращается в тоже место, где и был (сразу после указателя возврата).


rustgo[0x49d8be]:  movq   %rbp, 0x100(%rsp)  
rustgo[0x49d8c6]:  leaq   0x100(%rsp), %rbp  
                   [...]
rustgo[0x49d8de]:  movq   0x100(%rsp), %rbp

Наконец, указатель на фрейм, который, по сути, помещается в стек сразу после указателя возврата и обновляется в rbp. Получается, что rbp тоже сохраняется вызываемой функцией и должен быть обновлён там где вызываемая функция сохранила rbp, чтобы иметь возможность раскручивать стек.


rustgo[0x49d8ce]:  movq   0x110(%rsp), %rdx  
rustgo[0x49d8d6]:  movq   %rdx, 0x120(%rsp)

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


Виртуальные регистры


В документации Go сказано, что SP и FP это виртуальные регистры, а не просто алиасы для rsp и rbp.


Понятно, когда мы из Go ассемблера обращаемся к SP, все смещения пересчитываются относительно реального регистра rsp так что SP указывает наверх, а не низ фрейма. Это удобно, потому что это означает, что мы можем не менять все смещения при изменении размера фрейма, но это, на самом деле, лишь синтаксический сахар. Голый доступ к регистру (вроде MOV SP, DX) обращается к rsp напрямую.


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


Примечание: Go хранит rbp и указатели на фреймы, чтобы помочь отладке, но затем использует фиксированный rsp и rsp-смещение в стиле omit-stack-pointer для виртуального FP. Вы можете почитать больше про указатели на фреймы и как их не надо использовать в этом посте Адама Лэнгли.


Соглашения о вызовах C


В С стандартным на x86-64 соглашением о вызовах является sysv64, и оно довольно отличается:


  • аргументы передаются через регистры: RDI, RSI, RDX, RCX, R8 и R9
  • значение возврата идёт в RAX
  • некоторые регистры сохраняются вызываемой функцией: RBP, RBX и R12-R15
    • нас это мало интересует, потому что в Go все регистры сохраняются вызываемой функцией
  • стек должен быть выровнен по 16 байт
    • (я думаю это поэтому JMP сработал, а CALL нет — мы не выровняли стек!)

Указатели на фреймы работают аналогично (и генерируются с помощью rustc с -g).


Соединяем всё вместе


Создать простой трамплин между двумя соглашениями не должно быть сложно. Мы можем для вдохновения посмотреть на asmcgocall, посколько она как раз это и делает, только для cgo.


Нужно помнить, что мы хотим Rust функции дать использовать стек нашей ассемблерной функции, поскольку Go за нас гарантирует, что он присутствует. Чтобы сделать это, мы должны вернуть rsp в конец стека.


package main

//go:cgo_import_static increment
func trampoline(arg uint64) uint64

func main() {  
    println(trampoline(41))
}

TEXT ·trampoline(SB), 0, $2048-16  
    MOVQ arg+0(FP), DI // Load the argument before messing with SP
    MOVQ SP, BX        // Save SP in a callee-saved registry
    ADDQ $2048, SP     // Rollback SP to reuse this function's frame
    ANDQ $~15, SP      // Align the stack to 16-bytes
    CALL increment(SB)
    MOVQ BX, SP        // Restore SP
    MOVQ AX, ret+8(FP) // Place the return value on the stack
    RET

#[no_mangle]
pub extern fn increment(a: u64) -> u64 {  
    return a + 1;
}

CALL в macOS


CALL, на самом деле, не очень хорошо дружит с macOS. По какой-то причине, вызов функции был заменен на промежуточный вызов cgo_thread_start, что не так уж странно, учитывая, что мы используем нечто под названием cgo_import_static и CALL тоже виртуозен в Go ассемблере.


callq  0x40a27cd                 ; x_cgo_thread_start + 29

Мы можем обойти эту "помощь" используя колдовство //go:linkname, который мы нашли в стандартной библиотеке, чтобы взять указатель на функцию и затем вызвать указатель функции, вроде такого:


import _ "unsafe"

//go:cgo_import_static increment
//go:linkname increment increment
var increment uintptr  
var _increment = &increment  

    MOVQ ·_increment(SB), AX
    CALL AX

Быстро ли это?


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


Время бенчмарков!


Мы сравним увеличение uint64 переменной в заинлайненом варианте, с //go:noinline директивой, с нашим rustgo вызовом, и с cgo вызовом той самой Rust функции.


Rust был скомпилирован с флагами -g -O и бенчмарки запускались на macOS на 2.9GHz процессоре Intel Code i5.


name                 time/op  
CallOverhead/Inline  1.72ns ± 3%  
CallOverhead/Go      4.60ns ± 2%  
CallOverhead/rustgo  5.11ns ± 4%  
CallOverhead/cgo     73.6ns ± 0%

rustgo на 11% медленнее вызова обычной Go функции и почти в 15 раз быстрее, чем cgo!


Результаты даже лучше на Linux без проблемы с указателем, всего лишь на 2% медленее:


name                 time/op  
CallOverhead/Inline  1.67ns ± 2%  
CallOverhead/Go      4.49ns ± 3%  
CallOverhead/rustgo  4.58ns ± 3%  
CallOverhead/cgo     69.4ns ± 0%

Реальный пример


Для реального примера я выбрал замечательную библиотеку curve25519-dalek и конкретно задачу умножения начальной точки кривой на скаляр и возвращение её Edwards-представления.


Бенчмарки Cargo сильно разнятся между запусками из-за динамического изменения частоты процессора, но примерно они обещают, что операция будет занимать 22.9µs ± 17%.


test curve::bench::basepoint_mult    ... bench:      17,276 ns/iter (+/- 3,057)  
test curve::bench::edwards_compress  ... bench:       5,633 ns/iter (+/- 858)

На стороне Go, мы добавим простое API.


func ScalarBaseMult(dst, in *[32]byte)

На стороне Rust, это не сильно отличается от построения интерфейса для нормального FFI.


Признаюсь честно, у меня ушла вечность, чтобы заставить это работать в Rust:


#![no_std]

extern crate curve25519_dalek;  
use curve25519_dalek::scalar::Scalar;  
use curve25519_dalek::constants;

#[no_mangle]
pub extern fn scalar_base_mult(dst: &mut [u8; 32], k: &[u8; 32]) {  
    let res = &constants::ED25519_BASEPOINT_TABLE * &Scalar(*k);
    dst.clone_from(res.compress_edwards().as_bytes());
}

Чтобы создать .a мы запускаем cargo build --release с Cargo.toml в котором указаны зависимости, включает указатели на фреймы и конфигурирует curve25519-dalek на использование его самой продвинутой математики без стандартной библиотеки.


[package]
name = "ed25519-dalek-rustgo"  
version = "0.0.0"

[lib]
crate-type = ["staticlib"]

[dependencies.curve25519-dalek]
version = "^0.9"  
default-features = false  
features = ["nightly"]

[profile.release]
debug = true

Ну и ещё, мы должны подправить наш трамплин, чтобы он принимал 2 аргумента, и ничего не возвращал:


TEXT ·ScalarBaseMult(SB), 0, $16384-16  
    MOVQ dst+0(FP), DI
    MOVQ in+8(FP), SI

    MOVQ SP, BX
    ADDQ $16384, SP
    ANDQ $~15, SP

    MOVQ ·_scalar_base_mult(SB), AX
    CALL AX

    MOVQ BX, SP
    RET

Результатом будет прозрачный вызов из Go со скоростью, сравнимой с бенчмарком на чистом Go, и почти 6% быстрее cgo!


name            old time/op  new time/op  delta  
RustScalarBaseMult  23.7µs ± 1%  22.3µs ± 4%  -5.88%  (p=0.003 n=5+7)

Для сравнения, аналогичный функционал из Go пакета github.com/agl/ed25519/edwards25519 — чистая Go реализация тратит почти в 3 раза больше времени:


h := &edwards25519.ExtendedGroupElement{}  
edwards25519.GeScalarMultBase(h, &k)  
h.ToBytes(&dst)  

name            time/op  
GoScalarBaseMult  66.1µs ± 2%

Пакуем всё вместе


Теперь мы знаем, что это и вправду работает, отлично! Но чтобы это было реально использовать, решение должно быть в виде пакета, который можно импортировать, а не силой всунуто в package main в помощью мутного процесса сборки.


И вот тут как раз в игру вступает //go:binary-only-package. Эта аннотация позволяет нам сказать проигнорировать исходный код и использовать только собранный ранее .a файл библиотеки из $GOPATH/pkg.


Если мы сможем собрать .a файл, который работает с нативным линкером Go (cmd/link, называемый еще внутренним линкером), мы сможем распространять это и это позволит пользователям импортировать наш пакет, как будто это был нативный код, включая кросс-компиляцию (подразумевая, что мы собрали .a для этой платформы)!


Часто Go проста и пары с ассемблером и Rust у нас уже есть. Мы можем даже добавить документацию, чтобы видно было через go doc:


//go:binary-only-package

// Package edwards25519 implements operations on an Edwards curve that is
// isomorphic to curve25519.
//
// Crypto operations are implemented by calling directly into the Rust
// library curve25519-dalek, without cgo.
//
// You should not actually be using this.
package edwards25519

import _ "unsafe"

//go:cgo_import_static scalar_base_mult
//go:linkname scalar_base_mult scalar_base_mult
var scalar_base_mult uintptr  
var _scalar_base_mult = &scalar_base_mult

// ScalarBaseMult multiplies the scalar in by the curve basepoint, and writes
// the compressed Edwards representation of the resulting point to dst.
func ScalarBaseMult(dst, in *[32]byte)

Makefile слегка изменится, потому что мы больше не собираем библиотеку, мы можем перестать использовать go tool link.


Файл архива .a это всего лишь набор объектных .o файлов в древнем формате вместе с таблицей символов. Если бы мы могли взять символы из libed25519_dalek_rustgo.a в архив edwards25519.a так, чтобы go tool compile их увидел, мы бы достигли цели.


С архивы .a работают с помощью UNIX утилиты ar или внутреннего аналога Go — cmd/pack (через go tool pack). Эти два формата очень незначительно отличаются, конечно. Мы должны будем использовать ar для libed25519_dalek_rustgo.a и cmd/pack для edwards25519.a.


(Например, ar на моей macOS использует соглашения BSD по вызову файлов #1/LEN и затем вставляя имя файла длины LEN а начале этого файла, чтобы обойти 16 байт максимальной длины файла. Это запутало.)


Чтобы связать эти две библиотеки вместе я попробовал сделать простейший (читай: костыль) способ: извлечь libed25519_dalek_rustgo.a во отдельную папку и затем упаковать её объекты назад в edwards25519.a.


edwards25519/edwards25519.a: edwards25519/rustgo.go edwards25519/rustgo.o target/release/libed25519_dalek_rustgo.a  
               go tool compile -N -l -o $@ -p main -pack edwards25519/rustgo.go
               go tool pack r $@ edwards25519/rustgo.o # from edwards25519/rustgo.s
               mkdir -p target/release/libed25519_dalek_rustgo && cd target/release/libed25519_dalek_rustgo &&                        rm -f *.o && ar xv "$(CURDIR)/target/release/libed25519_dalek_rustgo.a"
               go tool pack r $@ target/release/libed25519_dalek_rustgo/*.o

.PHONY: install
install: edwards25519/edwards25519.a  
               mkdir -p "$(shell go env GOPATH)/pkg/darwin_amd64/$(IMPORT_PATH)/"
               cp edwards25519/edwards25519.a "$(shell go env GOPATH)/pkg/darwin_amd64/$(IMPORT_PATH)/"

Представьте моё удивление, когда это сработало!


Имея .a файл в нужном месте, осталось написать простую программу, использующую этот пакет:


package main

import (  
    "bytes"
    "encoding/hex"
    "fmt"
    "testing"

    "github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519"
)

func main() {  
    input, _ := hex.DecodeString("39129b3f7bbd7e17a39679b940018a737fc3bf430fcbc827029e67360aab3707")
    expected, _ := hex.DecodeString("1cc4789ed5ea69f84ad460941ba0491ff532c1af1fa126733d6c7b62f7ebcbcf")

    var dst, k [32]byte
    copy(k[:], input)

    edwards25519.ScalarBaseMult(&dst, &k)
    if !bytes.Equal(dst[:], expected) {
        fmt.Println("rustgo produces a wrong result!")
    }

    fmt.Printf("BenchmarkScalarBaseMult\t%v\n", testing.Benchmark(func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            edwards25519.ScalarBaseMult(&dst, &k)
        }
    }))
}

И запустить go build!


$ go build -ldflags '-linkmode external -extldflags -lresolv'
$ ./ed25519-dalek-rustgo
BenchmarkScalarBaseMult      100000         19914 ns/op

Ну, оно почти заработало. Пришлось немного похимичить. Бинарный файл нес компилировался, пока мы не слинковали с libresolv. Если честно, компилятор Rust пытался это сказать. (Но кто ж случает всё, что компилятор Rust говорит?)


note: link against the following native artifacts when linking against this static library

note: the order and any duplication can be significant on some platforms, and so may need to be preserved

note: library: System

note: library: resolv

note: library: c

note: library: m

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


Но, погодите, lib resolve? Почему это наша no_std, "должно быть как ассемблер", только стек Rust библиотека пытается использовать стандартную библиотеку для резолвинга DNS имён?


Я сказал no_std


Проблема тут в том, что библиотека на самом деле не no_std. Посмотрите на всё, что тут находится! Не нужны нам никакие аллокаторы:


$ ar t target/release/libed25519_dalek_rustgo.a
__.SYMDEF  
ed25519_dalek_rustgo-742a1d9f1c101d86.0.o  
ed25519_dalek_rustgo-742a1d9f1c101d86.crate.allocator.o  
curve25519_dalek-03e3ca0f6d904d88.0.o  
subtle-cd04b61500f6e56a.0.o  
std-72653eb2361f5909.0.o  
panic_unwind-d0b88496572d35a9.0.o  
unwind-da13b913698118f9.0.o  
arrayref-2be0c0ff08ae2c7d.0.o  
digest-f1373d68da35ca45.0.o  
generic_array-95ca86a62dc11ddc.0.o  
nodrop-7df18ca19bb4fc21.0.o  
odds-3bc0ea0bdf8209aa.0.o  
typenum-a61a9024d805e64e.0.o  
rand-e0d585156faee9eb.0.o  
alloc_system-c942637a1f049140.0.o  
libc-e038d130d15e5dae.0.o  
alloc-0e789b712308019f.0.o  
std_unicode-9735142be30abc63.0.o  
compiler_builtins-8a5da980a34153c7.0.o  
absvdi2.o  
absvsi2.o  
absvti2.o  
[... snip ...]
truncsfhf2.o  
ucmpdi2.o  
ucmpti2.o  
core-9077840c2cc91cbf.0.o

Так, как же нам сделать всё же её no_std? Это оказалось отдельным приключением, но я напишу лишь выводы:


  • если любая зависимость не no_std, ваш no_std флаг обнуляется. Одна из зависимостей curve25519-dalek имела эту проблему и cargo update это исправило
  • если сделать no_std статической библиотекой (тоесть библиотекой для внешнего пользования, а не только внутри Rust), то это как сделать `no_std исполняемый бинарник, что намного сложнее, если оно должно быть самодостаточным
  • документация о том как сделать no_std бинарник очень скудная. Я, в основном, использовал старую версию книги по Rust и, в итоге, нашел вот эту секцию по lang_items. Также помог вот этот пост.
  • Для начала, вы должны определить "lang_items" функции, чтобы реализовать функционал, который обычно есть в стандартной библиотеке, вроде panic_fmt.
  • затем вы остаетесь без эквивалентов Rust-ового compiler-rt, поэтому вы должны заимпортировать crate compiler_builtins (rust-lang/rust#43264)
  • затем там проблема с неэкспортированным rust_begin_unwind, которая не спрашивайте меня почему решается пометкой no_mangle на panic_fmt, чему не рад линтер (rust-lang/rust#38281)
  • потом вы остаётесь без memcpy, но, к счастью, есть нативная реализация на Rust в rlibc. Очень полезным оказалось знание, что nm -u покажет, каких символов не хватает в объекте.

Всё это в результате свелось к нескольким линиями вверху нашего lib.rs:


#![no_std]
#![feature(lang_items, compiler_builtins_lib, core_intrinsics)]
use core::intrinsics;  
#[allow(private_no_mangle_fns)] #[no_mangle] // rust-lang/rust#38281
#[lang = "panic_fmt"] fn panic_fmt() -> ! { unsafe { intrinsics::abort() } }
#[lang = "eh_personality"] extern fn eh_personality() {}
extern crate compiler_builtins; // rust-lang/rust#43264  
extern crate rlibc;

И вот теперь, go build заработал (!!!) на macOS.


Linux


А в Linux вообще ничего не работает.


Внешний линкер ругается на fmax и другие отсутствующие символы, и это, похоже, правда:


$ ld -r -o linux.o target/release/libed25519_dalek_rustgo/*.o
$ nm -u linux.o
                 U _GLOBAL_OFFSET_TABLE_
                 U abort
                 U fmax
                 U fmaxf
                 U fmaxl
                 U logb
                 U logbf
                 U logbl
                 U scalbn
                 U scalbnf
                 U scalbnl

К счастью, друг посоветовал проверить, что я использовал --gc-sections для удаление мёртвого кода, который мог указывать на вещи, которые я не использовал. И, конечно же, это сработало (тут три уровня флагов):


$ go build -ldflags '-extld clang -linkmode external -extldflags -Wl,--gc-sections'

Но, хм, в этом Makefile мы не используем линкер вообще, так куда добавить --gc-sections? Ответ в том, чтобы перестать соединять .a файлы и таки прочесть man-страницу линкера.


Мы можем собрать .o, содержащий нужный символ и все символы, на которые он ссылается с помощью ld -r --gc-sections -u $SYMBOL. Параметр -r делает объект доступным для использования и дальнейшей линковки и -u маркирует символ как "нужный", иначе все это будет собрано сборщиком мусора. $SYMBOL это scalar_base_mult в нашем случае.


Почему это не было проблемой на macOS? Это было бы, если бы мы линковали вручную, но оказалось, что компилятор на macOS удаляет мёртвый код по умолчанию.


$ ld -e _scalar_base_mult target/release/libed25519_dalek_rustgo/*.o
Undefined symbols for architecture x86_64:  
  "___assert_rtn", referenced from:
      _compilerrt_abort_impl in int_util.o
  "_copysign", referenced from:
      ___divdc3 in divdc3.o
      ___muldc3 in muldc3.o
  "_copysignf", referenced from:
      ___divsc3 in divsc3.o
      ___mulsc3 in mulsc3.o
  "_copysignl", referenced from:
      ___divxc3 in divxc3.o
      ___mulxc3 in mulxc3.o
  "_fmax", referenced from:
      ___divdc3 in divdc3.o
  "_fmaxf", referenced from:
      ___divsc3 in divsc3.o
  "_fmaxl", referenced from:
      ___divxc3 in divxc3.o
  "_logb", referenced from:
      ___divdc3 in divdc3.o
  "_logbf", referenced from:
      ___divsc3 in divsc3.o
  "_logbl", referenced from:
      ___divxc3 in divxc3.o
  "_scalbn", referenced from:
      ___divdc3 in divdc3.o
  "_scalbnf", referenced from:
      ___divsc3 in divsc3.o
  "_scalbnl", referenced from:
      ___divxc3 in divxc3.o
ld: symbol(s) not found for inferred architecture x86_64  
$ ld -e _scalar_base_mult -dead_strip target/release/libed25519_dalek_rustgo/*.o

Это та часть, где мы болезненно выучили, что macOS добавляет _ ко всем именам символов, просто потому что.


В итоге, вот часть Makefile, которая будет работать с внешней линковкой из коробки:]


edwards25519/edwards25519.a: edwards25519/rustgo.go edwards25519/rustgo.o edwards25519/libed25519_dalek_rustgo.o  
        go tool compile -N -l -o $@ -p main -pack edwards25519/rustgo.go
        go tool pack r $@ edwards25519/rustgo.o edwards25519/libed25519_dalek_rustgo.o

edwards25519/libed25519_dalek_rustgo.o: target/$(TARGET)/release/libed25519_dalek_rustgo.a  
ifeq ($(shell go env GOOS),darwin)  
        $(LD) -r -o $@ -arch x86_64 -u "_$(SYMBOL)" $^
else  
        $(LD) -r -o $@ --gc-sections -u "$(SYMBOL)" $^
endif

Последний недостающий элемент это внутренняя шинковка в Linux. Если кратко, линковка не проходила, даже если компиляция прошла успешно. Релокации не происходили и все CALL инструкции в нашей Rust функции указывали на бессмысленные адреса.


На этом моменте я решил, что это какой-то скрытый баг линкора, последний босс в реализации rustgo, и написал людям, гораздо более умным, чем я. Один из них указал мне на отладку cmd/link (что было потрясающе!), когда Ян Лэнс Тейлор, один из авторов Go, очень помог подсказкой о том, что //cgo:cgo_import_static недостаточно для внутренней линковки, и что мне нужно было еще добавить //cgo:cgo_import_dynamic.


//go:cgo_import_static scalar_base_mult
//go:cgo_import_dynamic scalar_base_mult

Я по прежнему без понятия, почему без этого получается такой результат, но добавление этой строки позволило наконец-то пакету rustgo компилироваться и с внешней и с внутренней линковкой, как на macOS, так и на Linux, из коробки.


Распространение пакета


Теперь, когда мы можем собирать .a, мы можем воспользоваться советом в спецификации //go:binary-only-package и собирать tar-архив с .a архивами для linux_amd64/darwin_amd64 и исходниками пакета, и для инсталляции нужно будет распаковать этот архив:


$ tar tf ed25519-dalek-rustgo_go1.8.3.tar.gz
src/github.com/FiloSottile/ed25519-dalek-rustgo/  
src/github.com/FiloSottile/ed25519-dalek-rustgo/.gitignore  
src/github.com/FiloSottile/ed25519-dalek-rustgo/Cargo.lock  
src/github.com/FiloSottile/ed25519-dalek-rustgo/Cargo.toml  
src/github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519/  
src/github.com/FiloSottile/ed25519-dalek-rustgo/main.go  
src/github.com/FiloSottile/ed25519-dalek-rustgo/Makefile  
src/github.com/FiloSottile/ed25519-dalek-rustgo/release.sh  
src/github.com/FiloSottile/ed25519-dalek-rustgo/src/  
src/github.com/FiloSottile/ed25519-dalek-rustgo/target.go  
src/github.com/FiloSottile/ed25519-dalek-rustgo/src/lib.rs  
src/github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519/rustgo.go  
src/github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519/rustgo.s  
pkg/linux_amd64/github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519.a  
pkg/darwin_amd64/github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519.a

Будучи установленным таким путём, пакет будет работать как обычный родной пакет, в том числе с кросс-компиляцией (так как мы запаковали и наши .a архивы тоже).


Единственная вещь, о которой всё же мы можем заволноваться, это то, что если мы собираем Rust с -Ctarget-cpu=native, код может не заработать на старых процессорах. Благодаря бенчмаркам (и авторам curve25519-dalek authors) мы можем посмотреть что реальная разница только между до- и после Haswell процессорами, поэтому мы можем смело сделать универсальный билд для Haswell:


$ benchstat bench-none.txt bench-haswell.txt
name                   old time/op  new time/op  delta  
ScalarBaseMult/rustgo  22.0µs ± 3%  20.2µs ± 2%  -8.41%  (p=0.001 n=7+6)  
$ benchstat bench-haswell.txt bench-native.txt
name                   old time/op  new time/op  delta  
ScalarBaseMult/rustgo  20.2µs ± 2%  20.1µs ± 2%   ~     (p=0.945 n=6+7)

И в качестве вишенки на торте, я сделал, чтобы Makefile понимал GOOS/GOARCH, конвертируя их в необходимые тройки для Rust, так что если вы настроили Rust для кросс-компиляции, вы даже можете кросс-компилировать сам .a.


Результат можно увидеть тут: github.com/FiloSottile/ed25519-dalek-rustgo/edwards25519
Он даже есть в godoc.


Превращая это в нечто реальное


Ну, это было весело.


Но, для ясности, rustgo это не реальная вещь, который вы должны использовать в продавшее. Например, я подозреваю, что должен был сохранять g перед переходом, размер стека выбран совершенно случайным образом, и уменьшение фрейма трамплина, скорее всего, собъет с толку все дебаггеры. Ну и паника в Rust может сойти с ума.


Чтобы сделать это более применимым для реального использования, я бы начал с вызова morestack вручную из NOSPLIT ассемблерной функции, чтобы убедиться, что у нас достаточно памяти на стеке горутины (вместо отката назад rsp) с размером, полученным, возможно из статического анализа Rust функции (вместо придуманной).


Это может быть проанализировано, сгенерировано и собрано с помощью какой-нибудь "rustgo" утилиты, вместо зашитых значений в Makefile и ассемблере. Cgo сам по себе несколько больше, чем просто кодогенератор всё же. Также может быть смысл запускать его через go:generate, но я знаю кое-кого, кто хочет сделать это командой cargo (наконец-то, спор Go против Rust!). Также коллекция FFI-типов со стороны Rust, вроде GoSlice было бы очень кстати.


#[repr(C)]
struct GoSlice {  
    array: *mut u8,
    len: i32,
    cap: i32,
}

Или может кто-то взрослый из Go или Rust прийдет и скажет нам прекратить, пока мы не поранились.


PS. Прежде, чем кто-то начнет это сравнивать с cgo (в котором масса фич для безопасности) или чистым Go, rustgo не подразумевается заменой ни того, ни другого. Он подразумевался, как замена ассемблерных функций, написанных вручную, на что-то более безопасное и более читабельное, со сравнимой производительностью. А ещё лучше, это подразумевалось, как весёлый эксперимент.

Комментарии (2)


  1. mersinvald
    07.09.2017 19:42
    #10405386
    -9

    Кто-то должен оставить это здесь

    image


    1. divan0 Автор
      07.09.2017 20:01
      #10405428
      +2

      Мне кажется в статье, с большой долей самоиронии, вопрос «зачем?» очень подробно раскрыт :)