Сериализация и кодировки

Сериализация — это превращение значений из памяти в байты для файла или сети и обратный разбор таких байтов. Во многих языках задача решена централизованно: в Rust структуру помечают #[derive(Serialize)], и кодировщик пишет макрос; в Python или Java библиотека перебирает поля объекта во время выполнения (рефлексия). В kola нет ни макросов, ни трейтов, ни рефлексии, а дженерики у неё мономорфные (Модули и стандартная библиотека). Поэтому kola идёт другим путём. Каждый формат передачи в стандартной библиотеке (байты, hex, base64, DER, PEM, JSON, XML, TOML, YAML, кадрирование HTTP/1.1 и HTTP/2, DEFLATE и другие) — это набор обычных функций, которые можно прочитать от начала до конца, а контракты стоят прямо на коде, который касается недоверенных байтов.

Любой парсер начинается со среза байтов &[u8]: это указатель и длина, описывающие последовательность байтов, которой владеет кто-то другой, примерно как const uint8_t * вместе с size_t в C. Если результат должен ссылаться обратно на эти байты, срез записывается как &r [u8]. На выходе получается одна из двух форм. Плоский формат вроде DER или HTTP возвращает простые данные: маленькие структуры со смещениями usize в исходный буфер, так называемые спаны. Ничего не копируется, и чтобы получить исходные байты, достаточно одного среза buf[start..end], пока buf у вас в руках. Древовидный формат вроде JSON или XML размещает настоящие узлы в регионе, который вы передаёте. Регион — это арена: один пул памяти, из которого нарезаются отдельные объекты и который освобождается целиком, а не по узлу за раз. Так что всё разобранное дерево освобождается на одной закрывающей скобке (Память: регионы и ссылки).

Result для внешнего мира, контракты для себя

Байты из сети враждебны. Сертификат, тело JSON или строка HTTP-запроса приходят извне, и некорректные данные — ожидаемый исход, а не ошибка в программе. Каждая функция здесь, которая разбирает такие байты, возвращает Result[T, E]: значение, которое либо Ok с ответом, либо Err с причиной (исключений в kola нет), с небольшим закрытым перечислением ошибок. Трапа она не вызывает никогда; трап в kola — это остановка процесса при проваленной проверке.

Функции доступа, которые работают с уже разобранным значением (der_content, json::span_bytes, http::header_at), следуют обычной дисциплине из главы Контракты, трапы и тесты: у них контракт req — предусловие в сигнатуре, которое компилятор либо доказывает, либо проверяет во время выполнения, — и трап срабатывает, только если вызывающий передал то, чего парсер выдать не мог. Это ошибка программиста, а не враждебный собеседник. Разделение видно по каждой сигнатуре: результат Result значит «здесь читаются недоверенные байты», а обычный результат с req — «здесь читается уже проверенное значение».

bytes: поля фиксированной ширины

Двоичные протоколы хранят многобайтовые числа в фиксированном порядке байтов. Big-endian (его ещё называют сетевым порядком) ставит старший байт первым: 16-битное число 300, в шестнадцатеричной записи 0x012C, превращается в байты 01 2C. Little-endian, который x86 и ARM используют в памяти, ставит их наоборот. std::encoding::bytes читает и пишет скалярные поля в big-endian по указанному смещению. Result эти функции не возвращают вовсе; их контракт — req, что смещение помещается в буфер. Размер поля фиксированной ширины не зависит от атакующего, от него зависит только значение, так что задача здесь арифметическая, а не грамматическая. rd16/rd32/rd64 и wr16/wr32/wr64 (есть и 24-битные варианты) читают и пишут по смещению; hi8/lo8, hi16/lo16 и hi32/lo32 разбирают значение на части. std::encoding::bytes_le — двойник для little-endian.

use std::encoding::bytes;

struct Point { x: u16, y: u16 }

fn write_point[r](buf: &r mut [u8], off: usize, p: Point) !{}
    req off + 4 <= buf.len
{
    bytes::wr16(buf, off, p.x);
    bytes::wr16(buf, off + 2, p.y);
}

fn read_point[r](buf: &r [u8], off: usize) -> Point !{}
    req off + 4 <= buf.len
{
    Point { x: bytes::rd16(buf, off), y: bytes::rd16(buf, off + 2) }
}

test point_wire_roundtrip {
    region r {
        let buf = alloc in r mut [0u8; 4];
        write_point(buf, 0, Point { x: 300, y: 40000 });
        let p = read_point(buf, 0);
        assert p.x == 300;
        assert p.y == 40000;
        // 300 — это 0x012C, старший байт первым
        assert buf[0] == 0x01 && buf[1] == 0x2C;
    }
}

В том же модуле есть массовые операции над байтовыми буферами: push_bytes, resize, copy (из среза в срез, вперёд), xor и extend_within, которая дописывает байты, взятые из более ранней части того же буфера. Последняя — основной шаг распаковки LZ77 (на ней стоят DEFLATE и gzip), где повторы кодируются как «скопируй n байтов, начиная за k байтов отсюда», и перекрытие здесь — смысл операции: при from = b.len - 1 она повторяет один байт n раз, что не совпадает ни с memcpy, ни с memmove. Для Vec лучше подходят методы v.extend_from_slice(s), v.resize(n, x) и v.copy_from_slice(s).

hex и base64

hex записывает каждый байт двумя символами 0-9a-f; base64 упаковывает каждые три байта в четыре печатных символа — так двоичные данные путешествуют внутри текстовых форматов вроде почты, JSON и PEM. Устроены оба кодека одинаково. Кодирование не может завершиться ошибкой: любые байты — допустимый вход. Декодирование возвращает Result, и ошибка точно говорит, что не так: HexErr — это Len (нечётная длина) или Char (байт вне [0-9a-fA-F]); B64Err — Len, Char или Pad (= не на своём месте). Ни один декодер не пропускает пробелы и не принимает молча второй алфавит.

use std::encoding::hex;

test hex_roundtrip {
    region r {
        let msg = alloc in r b"kola";
        let enc = hex::encode(msg);
        assert enc == &b"6b6f6c61";
        match hex::decode(enc) {
            Ok(dec) => { assert dec == msg; }
            Err(_) => { assert false; }
        }
        match hex::decode(&b"zz") {
            Err(hex::HexErr::Char) => {}
            _ => { assert false; }
        }
    }
}

hex::encode_upper пишет заглавные цифры. В base64 есть encode/decode для стандартного алфавита и encode_url/decode_url (плюс encode_url_nopad) для алфавита, безопасного в URL. Алфавиты различаются всего в двух позициях, и каждый декодер отвергает символы другого:

use std::encoding::base64;

test base64_roundtrip {
    region r {
        let msg = alloc in r b"kola!!";
        let enc = base64::encode(msg);
        assert enc == &b"a29sYSEh";
        match base64::decode(enc) {
            Ok(dec) => { assert dec == msg; }
            Err(_) => { assert false; }
        }
        // байт вне алфавита — это Err, а не трап
        match base64::decode(&b"@@@@") {
            Err(base64::B64Err::Char) => {}
            _ => { assert false; }
        }
    }
}

DER: TLV по запросу и байты, которые покрывает подпись

DER — двоичная кодировка, на которой стоят сертификаты X.509 и большинство форматов ключей. Каждое значение DER состоит из трёх частей, вместе их называют TLV: байт тега, говорящий, что это за значение (целое, последовательность, идентификатор объекта), длина и байты содержимого. Содержимое SEQUENCE — это снова TLV, так что сертификат представляет собой их дерево. der::der_read_tlv читает один заголовок и возвращает Tlv: пять простых полей usize и байт тега, без ссылок, свободно копируемое значение. Дочерние элементы SEQUENCE обходятся по запросу: der_first_child, затем der_more_siblings и der_next_sibling в цикле. Обратного вызова-посетителя нет, потому что в kola нет замыканий; парсер фиксированной схемы проходит известную структуру вручную.

Цифровая подпись покрывает точные байты, и для её проверки главная функция — der_raw. Она возвращает тег, длину и содержимое ровно в том виде, в каком они пришли. Проверка подписи не по исходным байтам, а по повторно закодированному разобранному значению — хорошо известный класс уязвимостей. Здесь он случайно не возникнет: сырой спан — это срез исходного буфера.

use std::encoding::der;

test der_walks_a_sequence {
    region r {
        // SEQUENCE { OID 1.2.840.10045.2.1, NULL }: AlgorithmIdentifier
        let buf = alloc in r [
            0x30u8, 0x0Bu8,
            0x06u8, 0x07u8, 0x2Au8, 0x86u8, 0x48u8, 0xCEu8, 0x3Du8, 0x02u8, 0x01u8,
            0x05u8, 0x00u8,
        ];
        match der::der_read_tlv(buf, 0) {
            Ok(seq) => {
                assert seq.tag == der::TAG_SEQUENCE;
                assert der::der_is_constructed(seq);
                match der::der_first_child(buf, seq) {
                    Ok(oid) => {
                        assert oid.tag == der::TAG_OID;
                        // тег, длина, содержимое — ровно как пришли
                        let raw = der::der_raw(buf, oid);
                        assert raw.len == 9;
                        match der::der_next_sibling(buf, seq, oid) {
                            Ok(null_tlv) => {
                                assert null_tlv.tag == der::TAG_NULL;
                                assert !der::der_more_siblings(seq, null_tlv);
                            }
                            Err(_) => { assert false; }
                        }
                    }
                    Err(_) => { assert false; }
                }
            }
            Err(_) => { assert false; }
        }

        match der::der_read_tlv(&b"\x30", 0) {
            Err(der::DerErr::Truncated) => {}
            _ => { assert false; }
        }
    }
}

У DerErr шесть вариантов: Truncated, BadLength, IndefiniteLength (неопределённая длина 0x80 из BER, в DER недопустимая), BadTag, BadInteger (пустое или не минимальное) и UnexpectedTag. Вспомогательные функции вроде der_expect, der_oid_eq, der_int_bytes, der_bit_string_content и der_int_to_fixed[N] покрывают типичные шаги разбора схемы, а семейство функций der_write_* строит DER (der_write_sequence, der_write_integer, der_write_utc_time и другие) в Vec[u8], размещённом в регионе.

PEM: текстовый конверт вокруг DER

DER двоичный, а файлы сертификатов и ключей, которые открывают люди, — текстовые. PEM (RFC 7468) — это конверт: строка -----BEGIN LABEL-----, байты DER в base64 с переносом по 64 символа и парная строка -----END LABEL-----. std::encoding::pem умеет только кодировать, и функция у него одна:

pub fn pem_encode[r](label: &str, der: &r [u8]) -> &r mut Vec[u8] !{alloc(r)}

Метка передаётся параметром, а не зашита как "CERTIFICATE", поэтому та же функция пишет PRIVATE KEY, PUBLIC KEY, CERTIFICATE REQUEST и другие метки из RFC 7468. Парсера PEM в стандартной библиотеке нет.

use std::encoding::pem;

test pem_wraps_der_for_humans {
    region r {
        let der: &r [u8] = alloc in r b"fake-der-bytes-0123";
        let out = pem::pem_encode("CERTIFICATE", der);
        let want = b"-----BEGIN CERTIFICATE-----\nZmFrZS1kZXItYnl0ZXMtMDEyMw==\n-----END CERTIFICATE-----\n";
        assert out == &want;
    }
}

JSON: дерево в вашем регионе и писатель, который не забудет скобку

json::parse строит дерево JVal[r] с вариантами Null, Bool, Num, Str, Arr(&r Vec[&r JVal[r]]) и Obj(&r Vec[JMember[r]]), и каждый узел размещается в текущем регионе. Строки и числа хранятся как спаны во входных данных. Число проверяется по полной грамматике RFC 8259, так что корректный документ никогда не отвергается из-за 1.5e3, но ни во что не преобразуется. Числовая функция доступа — num_i64, и она строгая: дробная часть, экспонента или значение вне i64 дают Err(NotInt), а не обрезание. obj_get ищет по упорядоченному списку членов, и выигрывает последний совпавший ключ; повторяющиеся ключи в JSON допустимы, и дерево их сохраняет.

parse принимает предел вложенности параметром и за ним отвечает Err(JsonErr::TooDeep). Рекомендуемое значение — json::MAX_DEPTH (32): с ним глубоко вложенный вход остаётся далеко от предела стека самого интерпретатора. Сервис, который разбирает враждебный вход, передаёт это число или своё, поменьше. У JsonErr тринадцать вариантов, от Eof и BadNumber до Trailing и NotInt.

use std::encoding::json;

test json_tree_in_a_region {
    region r {
        let doc = b"{\"name\": \"kola\", \"stable\": false, \"stars\": 42}";
        match json::parse(&doc, json::MAX_DEPTH) {
            Ok(v) => {
                match json::obj_get(&doc, v, &b"stars") {
                    Some(n) => {
                        match json::num_i64(&doc, n) {
                            Ok(i) => { assert i == 42; }
                            Err(_) => { assert false; }
                        }
                    }
                    None => { assert false; }
                }
                match json::obj_get(&doc, v, &b"name") {
                    Some(s) => {
                        match json::str_span(s) {
                            Some(sp) => { assert json::span_bytes(&doc, sp) == &b"kola"; }
                            None => { assert false; }
                        }
                    }
                    None => { assert false; }
                }
                assert json::obj_get(&doc, v, &b"missing").is_none();
            }
            Err(_) => { assert false; }
        }

        // висячая запятая не входит в грамматику RFC 8259
        match json::parse(&b"{\"a\": 1,}", json::MAX_DEPTH) {
            Err(_) => {}
            Ok(_) => { assert false; }
        }
    }
}

Спан строки хранит сырые, ещё экранированные байты; json::str_unescape декодирует их в буфер. arr_len, arr_get и obj_len обходят массивы и объекты, а write_val сериализует разобранное дерево обратно.

Для создания JSON есть потоковый писатель: он пишет документ в буфер по частям, не строя сначала дерево. json::writer() возвращает JsonW, и это ресурс. Вы вызываете obj_begin, key, str_val, u64_val и остальные функции, а писатель сам ставит запятые и двоеточия и экранирует строки. То, что писатель — ресурс, закрывает ошибку, которую обычная структура закрыть не может: забытую закрывающую скобку. Обычный способ израсходовать писатель — json::finish(w), чей req требует законченного документа, а функция, которая вообще забыла его израсходовать, не компилируется. На пути ошибки json::discard(w) завершает писатель явно.

use std::encoding::json;

fn render[o](out: &o mut Vec[u8]) !{alloc(o)} {
    let mut w = json::writer();
    json::obj_begin(&mut w, out);
    json::key(&mut w, out, &b"name");
    json::str_val(&mut w, out, &b"kola");
    json::key(&mut w, out, &b"stars");
    json::u64_val(&mut w, out, 42);
    json::obj_end(&mut w, out);
    json::finish(w);
}

test writer_emits_a_whole_document {
    region r {
        let out: &r mut Vec[u8] = alloc in r mut Vec::new();
        render(out);
        assert out == &b"{\"name\":\"kola\",\"stars\":42}";
    }
}

Если удалить строку json::finish(w);, чекер ответит ошибкой card §2: «resource w is not consumed on this path».

XML: та же форма дерева

std::encoding::xml повторяет форму JSON (элементы, атрибуты и текст как данные в регионе) над намеренно узкой грамматикой. DOCTYPE и DTD отвергаются сразу, с XmlErr::Doctype. В DTD можно определить сущности, которые раскрываются в другие сущности, и несколько сотен байтов раскрываются в гигабайты (атака «billion laughs»); раз DTD не поддерживается, этой атаке не на что опереться. Пространства имён не разрешаются, : — обычный байт имени. Вложенность ограничена xml::MAX_DEPTH (64), дальше — TooDeep, так что враждебный вход получает Err, а стек не исчерпывается.

use std::encoding::xml;

test xml_walks_an_element_tree {
    region r {
        let doc = b"<pack name=\"gossip\"><version>3</version></pack>";
        match xml::parse(&doc) {
            Ok(root) => {
                assert xml::span_eq(&doc, root.name, &b"pack");
                match xml::attr_get(&doc, root, &b"name") {
                    Some(sp) => { assert xml::span_eq(&doc, sp, &b"gossip"); }
                    None => { assert false; }
                }
                match xml::child_elem(&doc, root, &b"version") {
                    Some(v) => { assert v.kids.len == 1; }
                    None => { assert false; }
                }
            }
            Err(_) => { assert false; }
        }

        match xml::parse(&b"<!DOCTYPE x><a/>") {
            Err(xml::XmlErr::Doctype) => {}
            _ => { assert false; }
        }
    }
}

xml::unescape декодирует спан текста или атрибута, а write_elem и write_node сериализуют дерево.

От текста к байтам и обратно

Вызывать эти кодеки удобно благодаря двум возможностям языка. Байтовый литерал b"GET / HTTP/1.1\r\n" — это обычный массив [u8; N] из статических данных, поэтому &b"..." имеет тип &heap [u8] и подходит к любому региону. Внутри допустимы печатные символы ASCII и экранирования \n \t \r \\ \" \0 \xNN. А у каждой str есть представление .bytes: те же байты UTF-8 в виде &[u8], в том же регионе, без копирования.

use std::encoding::hex;

test byte_string_and_str_bytes_bridge {
    region r {
        let wire = b"kola";
        let name = "kola";
        // байты str и байтовая строка сравниваются поэлементно
        assert name.bytes == &wire;
        let enc = hex::encode(name.bytes);
        assert enc.len == 8;
    }
}

Обратный путь уже. Все кодеки на этой странице возвращают байты или спан, но не str, а единственный способ получить str из байтов — std::text::utf8::to_str. Приведения типа, которое могло бы это сделать, в kola нет.

pub fn to_str[r](b: &r [u8]) -> Option[&r str] !{}

to_str строго проверяет UTF-8 (избыточные формы, суррогаты и кодовые точки вне диапазона отвергаются) и при неудаче отвечает None. Результат — представление b: ничего не выделяется, и str живёт ровно столько же, сколько b. Если текст должен пережить свой буфер, utf8::to_str_copy копирует его в выбранный вами регион. Байт NUL — обычный символ: str — это указатель и длина, так что "a\0b".len равно 3. Там, где str уходит в API, ожидающее C-строку, например в путь к файлу, операция отвергает её как Invalid, а не работает с обрезанной строкой.

use std::text::utf8;

test to_str_is_the_only_door {
    region r {
        let good: &r [u8] = alloc in r b"kola";
        match utf8::to_str(good) {
            Some(s) => { assert s == "kola"; }
            None => { assert false; }
        }

        // одиночный байт продолжения — не UTF-8
        let bad: &r [u8] = alloc in r [0x80u8];
        assert utf8::to_str(bad) == None;

        // U+0000 — корректный UTF-8 и обычный символ
        let nul: &r [u8] = alloc in r [107u8, 0u8, 108u8];
        match utf8::to_str(nul) {
            Some(s) => { assert s.len == 3; }
            None => { assert false; }
        }
    }
}

HTTP/1.1: кадрирование без сокетов

std::encoding::http разбирает заголовки запросов и ответов и тела с фрагментированной передачей (chunked) по RFC 9110 и 9112. Капабилити у него нет, о сокетах он ничего не знает. parse_request_head и parse_response_head принимают срез байтов и два бюджета, max_headers и max_head_bytes (http::MAX_HEAD_BYTES равен 8192), и возвращают заголовочную часть и число использованных байтов. Программа, которой нужен сервер, сама подключает кодек к настоящему сокету.

Именно отсутствие капабилити позволяет кодеку работать с настоящим сокетом. TCP доставляет поток байтов, а не сообщения, поэтому одно чтение может принести половину запроса или полтора. Поэтому parse_request_head отвечает Result[Option[(&r RequestHead[r], usize)], HttpErr]. Err значит, что вход некорректен. Ok(None) — что пока всё корректно, но данных не хватает: вызовите снова, когда придут новые байты. Ok(Some((head, consumed))) — что заголовочная часть получена целиком. Состояния между вызовами парсер не хранит и каждый раз разбирает буфер с нулевого байта.

use std::encoding::http;
use std::encoding::http::HttpVersion;

test http_incremental_parse {
    region r {
        let rq = b"POST /upload HTTP/1.1\r\nHost: kola.dev\r\nContent-Length: 5\r\n\r\nhello";

        // Первое чтение: пришла только строка запроса.
        match http::parse_request_head(rq[0..24], 16, http::MAX_HEAD_BYTES) {
            Ok(opt) => {
                match opt {
                    None => {}
                    Some(_) => { assert false; }
                }
            }
            Err(_) => { assert false; }
        }

        // Второе чтение: заголовки получены целиком.
        match http::parse_request_head(&rq, 16, http::MAX_HEAD_BYTES) {
            Ok(opt) => {
                match opt {
                    Some(t) => {
                        let head = t.0;
                        let consumed = t.1;
                        assert head.version == HttpVersion::Http11;
                        match http::determine_request_body_framing(&rq, head) {
                            Ok(bf) => {
                                match bf {
                                    http::BodyFraming::Fixed(n) => { assert n == 5u64; }
                                    _ => { assert false; }
                                }
                            }
                            Err(_) => { assert false; }
                        }
                        // всё после заголовков — тело
                        assert rq[consumed..].len == 5;
                    }
                    None => { assert false; }
                }
            }
            Err(_) => { assert false; }
        }
    }
}

BodyFraming — это NoBody, Fixed(u64), Chunked или UntilClose. Кодек заодно закрывает известную атаку. При контрабанде запросов (request smuggling) атакующий посылает запрос, длину которого два сервера читают по-разному (один доверяет Content-Length, другой — Transfer-Encoding), и прокси с сервером за ним расходятся во мнении, где кончается один запрос и начинается следующий. RFC 9112 §6.3 называет такой запрос неоднозначным, и кодек его отвергает: запрос, где есть и Transfer-Encoding: chunked, и Content-Length, даёт Err(ConflictingFraming), и пути, где один заголовок молча предпочитается другому, нет. Всего у HttpErr десять вариантов. Для записи есть write_request_line, write_status_line, write_header, end_headers и функции для фрагментов, которые собирают заголовки в Vec[u8].

Всё семейство

Распаковщики принимают предел max_out на объём выхода, так что маленький враждебный вход не может раздуться в неограниченную память.

Чего нет намеренно

Нет derive. Макросов в kola нет, поэтому в кодеке столько строк, сколько полей в формате, и все они — тела обычных функций. Нет и фреймворка в духе serde: без трейтов нет интерфейса Serializer, к которому подключались бы форматы, и каждый кодек — отдельный модуль со своим перечислением ошибок, так что решения, специфичные для формата (числа JSON как спаны, сырые байты DER для подписей), не прячутся за общей абстракцией. И нет рефлексии во время выполнения: каждое обращение к полю в каждом кодеке — имя, написанное в исходнике и проверенное компилятором.

Причина — рецензирование. Написать кодек дёшево: модель выдаст вызовы rd16 и wr16 по RFC за секунды. Дорого проверить, что кодек побайтно согласуется с форматом, и именно эту часть derive-макрос или сериализатор на рефлексии убирает с глаз. Если же кодек написан явно, а компилятор держит каждое смещение под контрактом, этот код остаётся там, где его читает рецензент.