Память: регионы и ссылки

Любая программа должна решать, когда участок памяти можно использовать заново. C даёт malloc и free и полагается на то, что вы правильно их спарите. В Java, Go и Python работает сборщик мусора — часть среды выполнения, которая время от времени просматривает память, находит значения, на которые больше никто не ссылается, и освобождает их. В Rust есть borrow checker: проход компилятора, который следит, какая переменная владеет каждым значением и сколько живёт каждая ссылка на него. kola идёт четвёртым путём. Память группируется в регионы, и компилятор проверяет время жизни региона целиком, а не каждого значения по отдельности. Ни сборщика мусора, ни borrow checker в языке нет.

В основе лежит арена: кусок памяти, из которого выделяют, просто сдвигая указатель, и который освобождается за один шаг. По отдельности из арены ничего не освобождается. Игровые движки и компиляторы пользуются аренами десятилетиями; kola делает их единственным способом выделить память и позволяет проверять, правильно ли ими пользуются.

Регион: блок со своей ареной

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

use std::log;

struct Acc { hits: u32, misses: u32 }

fn main() -> u8 !{alloc(heap), log} {
    region r {
        let acc: &r mut Acc = alloc in r mut Acc { hits: 0, misses: 0 };
        acc.hits = acc.hits + 1;
        log::info(f"hits={acc.hits} misses={acc.misses}");
    }
    0
}

Всё, что вы делаете с памятью в kola, — вариации на эту тему: открыть регион, выделить в нём память через alloc in r ..., работать через полученную ссылку &r T и дать закрывающей скобке всё освободить.

Почему это безопасно и чем за это платим

Если нет ни сборщика мусора, ни borrow checker, что обеспечивает безопасность памяти? Сначала полезно назвать классические ошибки. Use-after-free — чтение или запись памяти после того, как её освободили и, возможно, уже отдали кому-то другому. Double free — повторное освобождение одного и того же блока, которое портит аллокатор. Гонка данных возникает, когда два потока одновременно обращаются к одной памяти и хотя бы один из них пишет. Use-after-free исключён, потому что освободить память можно только закрыв регион, а регион записан в тип каждой ссылки, так что пережить его ссылка не может (ошибку показывает следующий раздел). Double free исключён, потому что free нет. Значения на стеке (локальные переменные функции, которые исчезают при её возврате) живут во встроенном регионе 'local по тому же правилу. Каждое обращение по индексу несёт контракт на границы, который либо доказан, либо проверяется, но никогда не пропускается (Контракты, трапы и тесты). А ссылки никогда не пересекают границу потока, поэтому регион доступен только одному потоку (Потоки и каналы).

Платить приходится дважды. Память остаётся занятой до конца региона, даже если значение было нужно только в начале, поэтому пиковое потребление выше, чем при точечных вызовах free; управляют им, выбирая, где регионы начинаются и заканчиваются. Кроме того, внутри живого региона две ссылки могут указывать на одно значение, и писать можно через обе: общего правила об уникальности &mut в kola нет. Поскольку ссылки не покидают свой поток, это не неопределённое поведение и не гонка. Чего компилятор не поймает, так это логической ошибки: записали через одну ссылку и удивились изменению, увидев его через другую. Правило исключительности в kola есть, но оно действует в пределах одного вызова; о нём ниже.

Правило: ссылка не переживает свой регион

Любая ошибка памяти, о которой сообщает компилятор, сводится к одному: &r T вынесли за конец региона r — вернули из функции или сохранили туда, где тип называет более долгоживущий регион. Здесь ссылку из короткого региона кладут в переменную, принадлежащую heap:

struct Acc { hits: u32, misses: u32 }

fn main() -> u8 !{alloc(heap)} {
    let mut keep: &heap Acc = alloc in heap Acc { hits: 0, misses: 0 };
    region r {
        let acc: &r Acc = alloc in r Acc { hits: 3, misses: 0 };
        keep = acc;   // r ends before keep does
    }
    0
}

error[card §2]: region mismatch: `heap` vs `'r1`
  --> escape.kl:7:16
   |
 7 |         keep = acc;   // r ends before keep does
   |                ^^^

Исправление — выносить наружу данные, а не ссылку. Простые данные вроде u32 копируются свободно. Если регион — последняя инструкция функции, возвращающей значение, его хвост становится результатом функции, и часто это самый аккуратный способ:

struct Acc { hits: u32, misses: u32 }

fn tally() -> u32 !{} {
    region r {
        let acc: &r mut Acc = alloc in r mut Acc { hits: 0, misses: 0 };
        acc.hits = acc.hits + 3;
        acc.hits          // u32 копируется наружу как результат функции
    }
}

test tally_copies_the_data_out {
    assert tally() == 3;
}

Правило о выходе за регион действует и для хвоста: вернуть сам acc было бы ошибкой типов. В любом другом месте регион — инструкция, а не выражение: let x = region r { ... }; компилятор отвергнет и подскажет вместо этого присвоить внешней привязке let mut внутри блока. Регионы вкладываются друг в друга, и ссылки на внешний регион остаются годными во внутреннем; запрещено только направление изнутри наружу.

heap — тоже регион

heap — встроенный регион, который живёт всё время работы программы: его закрывающая скобка — завершение процесса. Никакого сборщика за этим именем не прячется, и alloc in heap ... работает так же, как выделение в любом другом регионе. Кладите туда то, что действительно должно жить так долго, а временной работе давайте собственный регион, чтобы память возвращалась на скобке.

На строковых литералах хорошо видна разница между статическими и выделенными данными. Обычный литерал "..." — статические данные программы: он ничего не выделяет и подходит к любому региону, а если ничто не требует меньшего, его тип — &heap str. То же верно для байтовой строки за ссылкой: &b"..." имеет тип &heap [u8].

С интерполированной строкой иначе. f"n={n}" собирается во время выполнения, значит, выделяет память, и компилятору нужно знать где. Он берёт регион, названный в месте назначения, если такой есть (let s: &r str = f"...", возвращаемый тип -> &r str, поле &heap str); иначе — самый внутренний открытый region; иначе литерал отвергается. Молча в heap строка не попадает никогда: демон, который на каждый запрос собирает по сообщению в heap, хранил бы их все вечно. Если нужно именно время жизни программы, напишите heap в месте назначения. f-строка, переданная прямо в вызов, как в log::info(f"x {n}"), ничего не выделяет: её собирают в буфере на стеке на время вызова. По тому же правилу работают f64::to_str и сетевые операции, возвращающие адрес, а параметр, который строку только читает, стоит объявлять ссылкой на время вызова &str (о них ниже).

Функции над любым регионом: [r]

Функции, которая принимает ссылку, обычно всё равно, из какого региона та пришла. Тогда регион становится параметром — именем со строчной буквы в квадратных скобках:

fn first_byte[r](bytes: &r [u8]) -> Option[u8] !{} {
    if bytes.len == 0 { None } else { Some(bytes[0]) }
}

// Структура, которая хранит ссылку, получает параметр-регион.
struct Header[r] { body: &r [u8] }

test first_byte_in_any_region {
    region q {
        let data = alloc in q [7u8, 8u8, 9u8];
        let b = first_byte(data);    // r выводится как q
        assert b == Some(7u8);
    }
}

В вызове регион не пишут никогда. Аргументы-типы и константы указать можно (f[u64](x)), но регион всегда выводится из аргументов, места назначения или объемлющего блока region. А вот тип, обобщённый по региону, сохраняет аргумент-регион везде, где этот тип записан: Header[r], но не голый Header в позиции типа.

Функция, которая выделяет память в r, обязана упомянуть r в параметре или в возвращаемом типе. В сигнатуре вроде fn f[r](n: u64) -> u64 !{alloc(r)} вызывающему нечем связать r, и чекер на это укажет. Если памятью должен владеть вызывающий, передайте её внутрь: fn f[r](out: &r mut Vec[u8], ...). Если память нужна только как черновик на время вызова, откройте region внутри функции.

Вернуть &r T для параметра-региона можно: регион принадлежит вызывающему и переживёт вызов. Так в kola разбирают данные без копирования. Здесь первый байт кадра — длина, а остальное — полезная нагрузка; body возвращает её срезом того же буфера:

// Кадр: [len, payload...]. Вернуть полезную нагрузку без копирования.
fn body[r](frame: &r [u8]) -> &r [u8] !{}
    req frame.len >= 1
{
    frame[1..]
}

test zero_copy_body {
    region r {
        let f = alloc in r [3u8, 10u8, 20u8, 30u8];
        let b = body(f);         // b указывает в тот же буфер
        assert b.len == 3;
        assert b[0] == 10;
    }
}

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

Ссылки на время вызова: &T и &mut T

Ссылка без имени региона, &T или &mut T, бывает только типом параметра. Функция может пользоваться ею, пока длится вызов, но не может ни сохранить, ни вернуть её. Взамен такой параметр принимает что угодно: переменную на стеке, значение в любом регионе, поле структуры. Поэтому count_even(xs: &[u64]) из Основ прекрасно работала с массивом на стеке.

По умолчанию пишите &T, а &r T — только когда функция сохраняет или возвращает ссылку, как body. Имя региона — обещание вызываемой функции, что данные переживут вызов, а &T принимает строго больше вызывающих. Значение на стеке живёт в 'local и никогда не подходит под &r T, так что, увидев region mismatch: 'local vs 'r, сначала меняйте параметр, а не место выделения.

struct Gauge { level: u32 }

// Читаем на время вызова.
fn is_high(g: &Gauge) -> bool !{} {
    g.level > 100
}

// Меняем на месте. Владение остаётся у вызывающего.
fn raise(g: &mut Gauge, by: u32) !{} {
    g.level = g.level +% by;
}

test call_scoped_refs {
    // Переменная на стеке.
    let mut a = Gauge { level: 40 };
    raise(&mut a, 70);
    let hi = is_high(&a);
    assert hi;                    // 110 > 100

    // Значение в регионе. Те же параметры принимают и его.
    region r {
        let g: &r mut Gauge = alloc in r mut Gauge { level: 5 };
        raise(g, 3);
        let lo = is_high(g);
        assert lo == false;       // 8 не больше 100
    }
}

Вернуть ссылку на время вызова нельзя, и ошибка возникает уже на сигнатуре:

struct Gauge { level: u32 }

fn leak(g: &Gauge) -> &Gauge !{} {
    g
}

error[card §5]: call-scoped `&T` exists only as a parameter type
  --> leak.kl:3:4
   |
 3 | fn leak(g: &Gauge) -> &Gauge !{} {
   |    ^^^^
   = help: to store or return a reference, give it a region: &r T

Корректность таких ссылок держится на двух правилах. Аргумент &mut не может перекрываться ни с другим аргументом &mut, ни с разделяемым аргументом & того же вызова; две разделяемые ссылки могут указывать на одно и то же сколько угодно. И пока представление места ещё используется (ссылка, подсрез, цикл for по Vec), это место нельзя записать, увеличить, уменьшить или переместить ни под каким другим именем. Обычно помогает одно из трёх: сначала дочитать, скопировать значение наружу (let x = v[i];) или запомнить индекс и прочитать место заново после изменения.

Есть и третий вид ссылки, который кладут в регион, и у него своё ключевое слово: представление ресурса, let v: &r Buf = lend buf in r;. Оно замораживает buf до закрытия региона и относится к линейности, поэтому разобрано в главе Ресурсы и линейность.

Массивы, векторы и срезы

Последовательность можно хранить тремя способами:

• Массив [T; N] имеет фиксированную длину, известную при компиляции, и может жить на стеке: let a = [1u64, 2u64, 3u64];.

• Vec[T] растёт. Он может опираться на регион (alloc in r mut Vec::new()), и тогда push и insert выделяют память в r и несут эффект !{alloc(r)}. А может быть владеющим — голый Vec::new(), хранимый по значению; тогда его хранилище — heap, где бы ни лежал сам Vec, и рост обходится в !{alloc(heap)}. Сам Vec::new() ничего не выделяет.

• Срез &[T] — окно в любое из двух предыдущих. Функции, которые читают последовательность, почти всегда принимают именно его.

У Vec есть push, insert(i, x), pop, truncate(n), clear(), swap(i, j), .len и индексация, а также пакетные методы extend_from_slice, resize и copy_from_slice. Память выделяют только те, что могут его увеличить.

Владеющий Vec — это небольшой заголовок над буфером, и копия дала бы два заголовка на один буфер. Поэтому он перемещается: передача по значению, привязка через let или запись в поле отдаёт его, и прочитать старое имя после этого нельзя. То же относится к любому значению, несущему владеющий Vec, например к структуре с полем Vec. Чтобы продолжать пользоваться вектором, заимствуйте его: &Vec[T] для чтения, &mut Vec[T] для записи.

fn sum(xs: &[u64]) -> u64 !{} {
    let mut s: u64 = 0;
    for x in xs {
        s = s +% x;
    }
    s
}

// Растит владеющий Vec, поэтому в ряду эффектов alloc(heap).
fn fill(out: &mut Vec[u64], n: u64) !{alloc(heap)} {
    for i in 0..n {
        out.push(i);
    }
}

test vec_array_slice {
    region r {
        let v: &r mut Vec[u64] = alloc in r mut Vec::new();
        v.push(1u64);
        v.push(2u64);
        assert sum(v) == 3;          // Vec в регионе приводится к срезу
    }
    let mut owned: Vec[u64] = Vec::new();
    fill(&mut owned, 4);             // заимствован, значит, всё ещё наш
    assert sum(&owned) == 6;
    let moved = owned;               // перемещён: `owned` больше не читается
    assert moved.len == 4;

    let a = [5u64, 6u64, 7u64];
    assert sum(&a) == 18;            // массив за ссылкой — тоже срез
    assert sum(&a[1..3]) == 13;      // подсрез: элементы 1 и 2
}

Чтение owned после let moved = owned; компилятор отвергнет как использование после передачи по значению и в подсказке предложит заимствование.

Сколько держит регион: kola test --sim

kola test --sim печатает для каждого региона его пиковую отметку — наибольший объём памяти, который регион когда-либо занимал. На регион списываются две вещи: значение в каждом месте alloc in r ... и рост буфера контейнера. Когда Vec под push удваивается, новый буфер списывается, а старый остаётся в счёте, потому что арена не освобождает элементы по отдельности. Повторное использование бесплатно: clear(), truncate(n) и pop() только сдвигают .len.

test region_watermark {
    region r {
        // Массив: размер известен в месте выделения (24 байта).
        let arr: &r mut [u64; 3] = alloc in r mut [5u64, 6u64, 7u64];

        // Vec: пуст в месте выделения, растёт через push.
        let v: &r mut Vec[u64] = alloc in r mut Vec::new();
        v.push(5u64);
        v.push(6u64);
        v.push(7u64);

        // Повторное использование: clear сохраняет ёмкость, этот push ничего не стоит.
        v.clear();
        v.push(8u64);

        let ok = arr[0] == 5u64;
        assert ok;
        let n = v.len;
        assert n == 1;
    }
}

Запустите его через kola test --sim --interp, и за строкой результата появится цифра для региона:

w.kl: test region_watermark ... ok
    region r: 88 bytes region-charged high-water (arena-faithful)

24 байта из них — массив, остальное — рост вектора. Удалите три вызова push, и цифра упадёт до 24. Удалите clear() и следующий за ним push, и останется 88: так работает правило повторного использования.

Число только растёт, как и арена, которую оно моделирует: оно отвечает на вопрос «насколько большим стал регион», а не «сколько живо сейчас». В интерпретаторе это смоделированный счёт байтов, а нативная сборка списывает байты, которые реально запросила её арена, со своим выравниванием и заполнением. Поэтому при большом запасе оба исполнителя согласны в том, превышен ли бюджет, но не в точном байте, на котором это произошло бы.

Бюджеты памяти

На том же учёте держатся бюджеты. region r from m подкрепляет арену бюджетом памяти m, отрезанным от капабилити Mem (см. Эффекты и капабилити), и каждое списание сверяется с ним. push, который растит вектор сверх бюджета, вызывает трап прямо на push (трап детерминированно останавливает программу в этой точке и сообщает строку):

fn main(mut sys: Sys) -> u8 !{io, block, alloc(heap)} {
    let m: Mem = sys.mem.split(4096);
    region r from m {
        let v: &r mut Vec[u64] = alloc in r mut Vec::new();
        let mut i: usize = 0;
        while i < 1000 {
            v.push(1u64);          // every doubling is charged to m
            i = i + 1;
        }
    }
    sys.mem.absorb(m);
    0
}

$ kola run budget.kl
trap: error[card §7]: memory budget exceeded in region
  --> budget.kl:7:13
   |
 7 |             v.push(1u64);          // every doubling is charged to m
   |             ^^^^^^^^^^^^

Закрываясь, регион возвращает всё, что на него списали, на любом пути выхода, так что регион с бюджетом внутри цикла не истощает бюджет понемногу. Регион держит m до закрывающей скобки, и sys.mem.absorb(m) внутри блока компилятор отвергнет. Обычный region r без from ничем не ограничен, а обычный регион, вложенный в регион с бюджетом, тратит тот же бюджет.

Долгоживущие данные, умирающие по частям: Pool

Лексический регион плохо подходит для долгоживущего состояния, объекты которого появляются и исчезают в произвольном порядке: кэшей, таблиц сессий, графов объектов. Структура, которую перестраивают, а не дополняют, хранила бы все свои старые версии до закрытия региона. Для этого есть Pool[T] — распределитель слотов с освобождением по одному слоту. Pool встроен в компилятор, поэтому в std/ его определения нет; полный список операций — в STD-CARD.

struct Session { id: u64 }

test pool_generations {
    region r {
        let p: &r mut Pool[Session] = alloc in r mut Pool::new(8);
        let h1 = p.insert(Session { id: 1 });
        let h2 = p.insert(Session { id: 2 });
        match p.get(h1) {
            Some(s) => { assert s.id == 1; }
            None => { assert false; }
        }
        assert p.len == 2;            // занятые слоты, а не ёмкость
        p.remove(h1);                 // слот можно занять снова
        assert p.len == 1;
        assert p.get(h1).is_none();
        match p.get(h2) {
            Some(s) => { assert s.id == 2; }
            None => { assert false; }
        }
    }
}

У каждого слота есть номер поколения, а дескриптор Gen[T] помнит поколение, для которого его выдали. remove увеличивает поколение слота, так что все старые дескрипторы разом устаревают, и get по ним возвращает None. Указатель на мёртвый объект превращается в обычный None, который придётся обработать.

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

Ёмкость — часть интерфейса. insert в заполненный пул вызывает трап (вида Capacity), и это правильный ответ, когда сколько будет объектов, решает ваш собственный код. Когда же количество задаёт недоверенная сторона, например собеседник, открывающий сессии, трап означал бы удалённый отказ в обслуживании. Тогда нужен try_insert(v) -> Result[Gen[T], T]. Его Err возвращает вам сам элемент: T может быть ресурсом, и отказ, который его проглотил бы, его бы и потерял. Заполненный пул не остаётся заполненным навсегда: после remove следующий try_insert удаётся.

Ссылкой из get или get_mut нужно перестать пользоваться до remove и любой другой операции, меняющей пул. Если элемент нужен и после изменения, сохраните его Gen и найдите заново либо заранее скопируйте данные.

Пулы ресурсов

Пул ресурсов подчиняется более строгим правилам. Во время выполнения регионы стираются, и пул в регионе мог бы исчезнуть вместе с элементами, а ресурс нельзя терять молча. Поэтому пул, у которого T — ресурс, должен быть владеющей локальной переменной, let mut p: Pool[Conn] = Pool::new(n);, и сам пул становится линейным. Его опустошают, а затем завершают через p.fin(), который вызывает трап, если что-то осталось. drain_next() за один вызов извлекает один произвольный элемент вместе с дескриптором, так что разборка — это один цикл, который компилятор может проверить:

resource struct Link { id: u64 }

impl Link {
    pub fn close(self: Link) -> u64 !{} {
        let Link { id } = self;
        id
    }
}

test drain_a_pool_of_resources {
    let mut p: Pool[Link] = Pool::new(4);
    let _a = p.insert(Link { id: 1 });
    let _b = p.insert(Link { id: 2 });
    let mut sum: u64 = 0;
    loop {
        match p.drain_next() {
            Some((_g, l)) => { sum = sum + l.close(); }
            None => { break; }
        }
    }
    p.fin();                 // ничего не осталось, трапа не будет
    assert sum == 3;
}

insert должен знать, что пулом владеют, поэтому вставку ресурса через параметр &mut Pool компилятор отвергнет: размещение пула там неизвестно. Подсказка называет два исправления: передавать пул по значению (принимать Pool[T] и возвращать его) или обернуть его в resource struct и брать &mut от неё, ведь resource struct никогда не размещается в регионе. get, get_mut и remove через параметр &mut Pool работают.

Pool не может перейти в другой поток. Пул данных копируем, и два потока держали бы одни и те же слоты; пусть им владеет один поток, а остальные обращаются к нему сообщениями (см. Потоки и каналы). Перечислить свои живые дескрипторы пул тоже не умеет. drain_next его опустошает, а если нужно обойти содержимое, ничего не удаляя, храните дескрипторы в Vec[Gen[T]] рядом с пулом.

Нормативное описание — SPEC-CARD §4 и §5 (kola help spec-card), Vec и Pool — в STD-CARD.