Подсчёт ссылок обычно предлагается как самый простой способ автоматического управления памятью в языках программирования. Он избавляет программиста от необходимости вставлять в свой код free(), delete и тому подобное, следить за висячими указателями и утечками памяти. Принцип действительно звучит очень просто: каждый выделенный в куче блок памяти наделяется счётчиком ссылок на него. Каждая переменная, через которую можно добраться до этого блока, олицетворяет одну ссылку. Блок освобождается тогда, когда счётчик ссылок доходит до нуля.
В своём статически типизированном скриптовом языке Umka я решил воспользоваться именно этим способом. Его простота подкупала. Альтернативы вроде трассирующего сборщика мусора отпугнули непредсказуемыми задержками при исполнении программ. Ну а теперь пришло время рассказать про подводную часть этого невинного айсберга. Не сомневаюсь, что где-то в тысячах опубликованных статей такие айсберги описаны во всех деталях, но найти их там непросто и небыстро, особенно когда уже полным ходом идёшь на ледяную глыбу.
Итак, обсудим четыре ключевых практических проблемы, с которыми пришлось столкнуться при реализации подсчёта ссылок в языке Umka.
Проблема первая. Обход потомков
Начнём с канонического описания метода в книге Garbage Collection (судя по всему, авторы сочли метод слишком примитивным, чтобы надолго на нём задерживаться):
Функция Update(R, S) описывает действия, которые необходимо предпринять при присвоении *R = S. Предполагается, что и R, и &S указывают в кучу. Из этого псевдокода уже можно извлечь маленький урок: перед любым присвоением сначала нужно увеличивать счётчик ссылок правой части RC(S), а лишь затем уменьшать счётчик левой части, иначе при присвоении *R = *R правая часть рискует быть уничтожена ещё до присвоения.
Однако основной интерес здесь представляет функция delete(T), которая описывает уменьшение счётчика при уничтожении одной ссылки на блок памяти по указателю T, например, при вышеописанном присвоении или при выходе переменной-ссылки T из области видимости. Кроме очевидного декремента счётчика RC(T), она предписывает рекурсивно пройти по всем потомкам T, если уничтожается последняя ссылка на T. Это логично: T был одним из способов добраться до потомка, а теперь его не будет, значит, счётчик ссылок потомка нужно уменьшить. Но что такое "потомки" на практике?
Я начинал с наивного представления: потомки статического или динамического массива - это его члены, потомки структуры - её поля. Казалось, все инструкции виртуальной машины Umka, отвечающие за инкремент/декремент счётчиков ссылок, можно легко сгенерировать при компиляции в байт-код. Сама виртуальная машина при этом сохранила бы замечательное свойство, возникающее благодаря статической типизации языка: ничего не ведать об иерархии типов данных в исходной программе.
Красивая картина рассыпалась, как только я подумал про списки и деревья. В них потомками становится содержимое памяти по соответствующим указателям в каждом узле. При этом необходимо обойти всю иерархию потомков в соответствии с фактическими типами узлов и остановиться лишь там, где потомок окажется null. Предсказать этот null на этапе компиляции невозможно, поэтому весь код обхода потомков, увы, переехал из кодогенератора Umka в виртуальную машину, которой пришлось узнать и о типах данных. Элегантность статической типизации оказалась слегка подпорченной. Однако такое решение стало выглядеть неизбежным, как только в язык добавились ещё и интерфейсы в стиле Go - это вообще царство динамической типизации, ибо фактический тип содержимого интерфейса становится известен лишь при исполнении программы. В общем, в язык Umka пришёл RTTI (runtime type information) и уходить больше не собирается.
Приключения с обходом потомков на этом не закончились. Обход, основанный на рекурсии, довольно быстро съедает стек (имеется в виду системный стек, а не тот, которым оперирует виртуальная машина). Тем самым ограничивается глубина списков и деревьев, допускающих корректное освобождение. Возможно, предстоит довольно мучительное переписывание рекурсии в цикл.
Проблема вторая. Результаты функций
При возвращении из функции все локальные переменные выходят из области видимости и, если они являются указателями или содержат указатели, подлежат декременту своих счётчиков ссылок. Однако возвращаемое значение функции должно пережить смерть функции и дожить по крайней мере до присвоения результата какой-то переменной в точке вызова: y = f(x). Соответственно, выражение после return рассматривается точно так же, как правая часть присвоения, и требует инкремента счётчика ссылок. Однако кто будет держателем этой новой ссылки? Выражение f(x) - это не переменная, и на роль держателя не годится (хотя бы потому, что то же самое f(x) строчкой ниже может давать уже совершенно другое значение).
В Umka использован следующий подход: результат функции f(x) присваивается не только переменной y, но и новой неявной локальной переменной: __temp0 = f(x). Эта переменная становится держателем ссылки и умирает при выходе из того блока {...}, где вызывается f(x). Каждый новый вызов функции, даже в пределах одного блока, требует новой неявной переменной: __temp0, __temp1 и т. д. Конечно, было бы ещё лучше убивать эти переменные, как только состоялось присвоение y = f(x), но это создаёт некоторую путаницу с областями видимости.
Проблема третья. Указатели на середину структуры
Будучи во многом вдохновлён Go, язык Umka ориентирован на работу с классическими структурами (struct), которые могут вкладываться друг в друга целиком, а не в виде указателей. Это даёт замечательные преимущества при использовании Umka как встраиваемого скриптового языка в связке с C/C++. В отличие от Lua, Umka позволяет легко перекидывать структуры в программу на C/C++ и обратно, сохраняя при этом раскладку полей структуры в памяти.
Однако за такое удобство приходится платить и свою цену, о которой, кстати, не раз говорили и создатели Go. Любая структура вроде struct {x, y: int} может лежать не в стеке, а в куче, и быть доступной по указателю p. С точки зрения подсчёта ссылок, это означает следующее: где-то в куче выделено место под заголовок, в котором хранится счётчик ссылок и размер размещаемой структуры, а непосредственно за этим заголовком - место для самой структуры, на которую и указывает p. Имея p, всегда можно найти заголовок, отступив назад на размер этого заголовка. В заголовке, в свою очередь, можно найти счётчик ссылок. Однако никто не запрещает взять указатель на любое поле структуры: &p.y. Он, скорее всего, не совпадает с p. Как тогда по этому указателю отыскать заголовок?
В Umka сделано так. Память в куче выделяется страницами. Каждая страница разбита на блоки. Их размер фиксирован в пределах страницы, но отличается для разных страниц. Можно сказать, что размер блока - это основная неизменная характеристика страницы. Когда приходит время выделить место под структуру (вернее, заголовок + структуру), отыскивается страница с наиболее подходящим размером блока, в которой остался хотя бы один свободный блок. "Подходящий размер" означает: не меньше суммарного размера заголовка + структуры, но с наименьшим излишком. Если такой страницы нет, выделяется новая.
Когда размер блока фиксирован, это позволяет легко найти заголовок и счётчик ссылок по указателю на середину структуры:
Определяется страница, на которую попадает указатель
&p.y.Восстанавливается указатель на начало заголовка. Для этого смещение указателя
&p.yот начала страницы округляется в меньшую сторону до величины, кратной размеру блока.Считывается заголовок блока.
В заголовке отыскивается (а при необходимости - изменяется) счётчик ссылок.
При этом одновременно с счётчиками ссылок на блоки меняется и общий счётчик ссылок на страницу (сумма счётчиков ссылок на все её блоки). Когда счётчик ссылок страницы доходит до нуля, она удаляется.
Проблема четвёртая. Циклические ссылки
На закуску остаётся классическая проблема циклических ссылок. С ней приходится иметь дело всем, кто захотел использовать подсчёт ссылок. Насколько мне известно, эта проблема стала так раздражать разработчиков Python, что в дополнение к подсчёту ссылок они ввели трассирующую сборку мусора (был бы благодарен знатокам Python за подробности этой истории).
Возьмём код (Umka использует синтаксис Pascal для указателей):
type (
S = struct {t: ^T}
T = struct {s: ^S}
)
p := new(S)
q := new(T)
p.t = q
q.s = pВ нём счётчики ссылок на p и q никогда не обнулятся, поскольку p ссылается на q, а q ссылается на p. В результате возникает утечка памяти.
Решение в Umka столь же классическое, сколь и сама проблема: слабые (weak) указатели, то есть указатели, наличие которых не учитывается в счётчике ссылок и не препятствует удалению блока памяти. Один из указателей, составляющих цикл, делается слабым, другой остаётся сильным:
type (
S = struct {t: weak ^T}
T = struct {s: ^S}
)
p := new(S)
q := new(T)
p.t = q
q.s = pРазумеется, по своей природе слабый указатель может оказаться висячим и указывать на уже освобождённый блок памяти, поэтому слабые указатели в Umka запрещено разыменовывать напрямую. Вместо этого его нужно сначала привести к сильному указателю. Висячий слабый указатель при таком приведении превратится в null.
Заключение
Спустя более чем год работы над Umka я по-прежнему ощущаю, что управление памятью остаётся самой сложной частью проекта, несмотря на кажущуюся простоту выбранного подхода. Баги, связанные с утечками памяти и висячими указателями, приходилось исправлять на протяжении всей работы. Начало практического применения языка и появление первых сторонних пользователей (которые подчас пишут на Umka смелее и решительнее меня) неплохо форсировало этот процесс.
Комментарии (51)
Metotron0
25.07.2021 14:34+2Простите, что придираюсь, но айсберг с КДПВ так плавать не будет, он упадёт на бок в силу физических законов. Где-то видел движение за корректное изображение айсбергов, и считаю, что это неплохая задумка. Вот, поддерживаю.
Tereshkov Автор
25.07.2021 14:43+1Вот уж никогда не знаешь, с какой стороны придёт удар :)
Но согласен, айсберг должен расширяться книзу. На подлинных фотографиях это отчётливо видно. Ну и да, такой айсберг, как у меня, вряд ли бы угрожал кораблям своей подводной частью.
alsoijw
27.07.2021 12:18Довольно низкоуровневый скриптовый язык получается.
Альтернативы вроде трассирующего сборщика мусора отпугнули непредсказуемыми задержками при исполнении программ.
Были тесты, или это просто общее впечатление?Элегантность статической типизации оказалась слегка подпорченной. Однако такое решение стало выглядеть неизбежным, как только в язык добавились ещё и интерфейсы в стиле Go — это вообще царство динамической типизации, ибо фактический тип содержимого интерфейса становится известен лишь при исполнении программы. В общем, в язык Umka пришёл RTTI (runtime type information) и уходить больше не собирается.
Насколько часто придётся сталкиваться Object(или местным аналогом)?Это даёт замечательные преимущества при использовании Umka как встраиваемого скриптового языка в связке с C/C++.
На чём основан такой выбор? Это полностью прозрачно, или как в go некоторые вещи недоступны из си кода?Разумеется, по своей природе слабый указатель может оказаться висячим и указывать на уже освобождённый блок памяти, поэтому слабые указатели в Umka запрещено разыменовывать напрямую. Вместо этого его нужно сначала привести к сильному указателю. Висячий слабый указатель при таком приведении превратится в null.
Большая часть статьи довольно очевидна(как минимум, когда начинаешь об этом размышлять, но вот реализация слабых указателей практически не описана — как именно они устроены и как ими пользоваться в умке.Баги, связанные с утечками памяти и висячими указателями, приходилось исправлять на протяжении всей работы.
Управление памятью полностью самописное? Были ли проблемы с использованием уже освобождённой памяти? Если да, то как они были решены?
Язык уже полностью готов, или ещё есть вещи, всё ещё не реализованые? Какие преимущества перед существующими языками, кроме скорости компиляции? Что с библиотеками, например, если я захочу обрабатывать js, то какие у меня варианты, кроме написания парсера с нуля? Знаком ли автор с ocaml?Tereshkov Автор
27.07.2021 17:18Довольно низкоуровневый скриптовый язык получается.
Так и задумывалось.
Были тесты, или это просто общее впечатление?
Общее впечатление. Здравый смысл подсказывает, что общие накладные расходы в случае подсчёта ссылок и трассирующей сборки мусора примерно одинаковы, однако при подсчёте ссылок они более равномерно "размазаны" и гарантированно не дают подвисаний. В конце концов, обход потомков, про который я писал, - это практически то же, что делает трассирующий сборщик, только разбитое на мелкие кусочки. А чтобы делать тесты, нужно было реализовать оба варианта. Я этого не делал.
Насколько часто придётся сталкиваться Object(или местным аналогом)?
Насколько я понимаю, речь идёт о пустом интерфейсе
interface{}. По опыту практического использования, встречается не очень часто, но за неимением обобщённых типов - несколько чаще, чем хотелось бы.На чём основан такой выбор? Это полностью прозрачно, или как в go некоторые вещи недоступны из си кода?
Не совсем понял вопрос. Но во избежание недоразумений подчеркну, что речь идёт не об FFI, позволяющем вызывать любую функцию, а о функциях с заранее оговорённой сигнатурой. Точно так же сделано в Lua: "When we say that Lua can call C functions, this does not mean that Lua can call any C function... As we saw previously, when C calls a Lua function, it must follow a simple protocol to pass the arguments and to get the results." Ну и конечно, из C недоступно то, что относится к подсчёту ссылок.
реализация слабых указателей практически не описана — как именно они устроены и как ими пользоваться в умке.
Это как раз совершенно классическая тема, где я не придумал ничего оригинального. Так же сделан
std::weak_ptrв C++ и всё управление памятью в Swift. Слабый указатель - такой, который при навешивании на объект не меняет его счётчика ссылок. Следовательно, он не мешает довести счётчик ссылок до нуля и уничтожить объект, поэтому сам рискует оказаться висячим. Так что пытаться разыменовывать слабый указатель опасно.Управление памятью полностью самописное?
Да, полностью самописное. В основном оно сводится к тому, что при присвоении рекурсивно вызывается функция обхода потомков, меняющая их счётчики.
Были ли проблемы с использованием уже освобождённой памяти? Если да, то как они были решены?
Имеется в виду обращение по висячим указателям, память из-под которых уже очистили? Проблемы были, но только по недомыслию и невнимательности (например, как правильно менять счётчики при вызове
append()для динамического массива).Язык уже полностью готов, или ещё есть вещи, всё ещё не реализованые?
Языком вполне можно пользоваться. Из интересного не готовы замыкания (хотя безымянные функции есть), поддержка Unicode (она работает сейчас ровно настолько, насколько это поддерживает терминал и локаль в C). Обобщённые типы - пока только на дальнем горизонте (их ещё и в Go не сделали).
Какие преимущества перед существующими языками, кроме скорости компиляции?
О преимуществах я говорил. В нише доминирует Lua. По сравнению с ним, имеем раннее обнаружение ошибок типов (с понятным сообщением об ошибке) и хорошую "стыкуемость" типов с типами C: целые/дробные разной длины, массивы, структуры. А скорость компиляции (имеется в виду, в байт-код перед запуском?) - здесь не очень интересный параметр. И кстати, ничего особенного я тут и не заявлял.
Что с библиотеками, например, если я захочу обрабатывать js, то какие у меня варианты, кроме написания парсера с нуля?
Библиотеки пока не особо обширные: мои и сторонние (среди последних есть разбор JSON, но если хотите JavaScript - то, боюсь, с нуля).
Знаком ли автор с ocaml?
Практически нет.
qw1
27.07.2021 18:34+1дравый смысл подсказывает, что общие накладные расходы в случае подсчёта ссылок и трассирующей сборки мусора примерно одинаковы
Подсчёт ссылок добавляет ненужный memory traffic, постоянно происходит запись на обычной передаче ссылок. Особенно всё плохо в многопоточных задачах, когда объекты используются из разных ядер (например, мы из общего кеша берём объекты). Поэтому современные среды, нацеленные на производительность и масштабируемость, уходят к обычному GC.В конце концов, обход потомков, про который я писал, — это практически то же, что делает трассирующий сборщик, только разбитое на мелкие кусочки
Но у GC есть ухищрения, как часть работы сделать в другом потоке. Учитывая, что ядер в процессорах дофига, экономия получается.
alsoijw
27.07.2021 19:09Здравый смысл подсказывает, что общие накладные расходы в случае подсчёта ссылок и трассирующей сборки мусора примерно одинаковы, однако при подсчёте ссылок они более равномерно «размазаны» и гарантированно не дают подвисаний
Сборщик мусора делает перемещение объектов бесплатным, но к сожалению, найти статью в которой это обсуждалось не могу.А чтобы делать тесты, нужно было реализовать оба варианта. Я этого не делал.
Есть библиотечные реализации, думаю подключить библиотеку будет проще уже проделанной работы.Не совсем понял вопрос.
Насколько помню, передать из go в си интерфейс невозможно.Следовательно, он не мешает довести счётчик ссылок до нуля и уничтожить объект, поэтому сам рискует оказаться висячим. Так что пытаться разыменовывать слабый указатель опасно.
Здесь имелся в виду пример с приведением слабого указателя к сильному в синтаксисе умки, а так же вопрос борьбы с висячими указателями, чтобы, например, при удалении одного объекта, и создании нового, нельзя было бы по старому указателю обратится к новому объекту.Tereshkov Автор
27.07.2021 20:06Есть библиотечные реализации, думаю подключить библиотеку будет проще уже проделанной работы.
Не совсем понимаю, как они работают. Ведь они должны иметь доступ к типам данных разрабатываемого языка (что я и обозначил "первой проблемой"). Без этого обходится, среди известного мне, только сборщик Бёма, но его принцип действия мне по сей день кажется странным: любая последовательность байт, которая выглядит как указатель, является указателем. Для C сгодится и это, коль скоро программа на C при всём желании не сообщит ничего о типах. Для других языков - сомнительное решение.
Насколько помню, передать из go в си интерфейс невозможно.
Скорее всего так, поскольку там появляются указатели, сборка мусора и таблицы методов. В Umka тоже нельзя.
Здесь имелся в виду пример с приведением слабого указателя к сильному в синтаксисе умки
a := 42 var p: weak ^int = &a if q := ^int(p); q != null { printf(repr(q^) + '\n') }а так же вопрос борьбы с висячими указателями, чтобы, например, при удалении одного объекта, и создании нового, нельзя было бы по старому указателю обратится к новому объекту.
Ситуация маловероятная, но нет уверенности, что невозможная. Стоит подумать.
alsoijw
28.07.2021 15:52Для других языков — сомнительное решение.
А чем другие языки принципиально отличаются? Они лишь добавляют синтаксического сахара и возможных гарантий.
Чем продиктован данный выбор, в частности почему проект не написан на c++ с использованием библиотечной реализации(std) или же какой-то другой библиотеки, даже для си?Управление памятью полностью самописное?
Да, полностью самописное.Tereshkov Автор
28.07.2021 16:49А чем другие языки принципиально отличаются? Они лишь добавляют синтаксического сахара и возможных гарантий.
Когда в языке сборщик мусора полностью интегрирован в runtime-библиотеку, он может (и должен) получать и использовать информацию о типах, чтобы точно знать, где указатель, где нет. В C эта интеграция невозможна, сборщик Бёма вынужден догадываться сам и поэтому не гарантирует отсутствия утечек. Т.е., строго говоря, он некорректен.
Чем продиктован данный выбор, в частности почему проект не написан на c++ с использованием библиотечной реализации(std) или же какой-то другой библиотеки, даже для си?
Ради отсутствия внешних зависимостей и лёгкости встраивания в основную программу на C. Так же сделаны Lua и Wren.
alsoijw
28.07.2021 19:40сборщик Бёма вынужден догадываться сам и поэтому не гарантирует отсутствия утечек. Т.е., строго говоря, он некорректен.
У вас есть возможность выделять память, с указанием того, где находятся указатели.Ради отсутствия внешних зависимостей и лёгкости встраивания в основную программу на C.
Полагаю, что в данном случае усилия, направленные на встраивание, полностью бы окупились использованием библиотечного кода, за счёт экономии ручной реализации умных указателей.Tereshkov Автор
28.07.2021 20:26У вас есть возможность выделять память, с указанием того, где находятся указатели.
Как-то не впечатлился. Притащить увесистую внешнюю зависимость, но при этом всё равно вручную перекодировать всю иерархию типов в битовые поля. Да ещё и не решить проблему указателей на середину структуры (или теперь у Бёма это тоже можно?).
qw1
28.07.2021 22:34Слишком много вы уделяете внимания «указателям в середину структуры». Оно у вас реально так часто используется? Имхо, это для каких-то жутких извращений может быть надо. А для скриптового языка вообще не принципиально. Запретить на уровне синтаксиса, и забыть.
Tereshkov Автор
28.07.2021 22:58Уделяю ровно столько внимания, сколько потребовалось бы в любом языке, признающем классические структуры с полями-значениям (снова упомяну Go). Встречается это сплошь это и рядом. И если вы предлагаете "запретить на уровне синтаксиса" такой код, то я вас не понимаю:
type ( Pt = struct {x, y: int} ClrPt = struct { clr: uint32 p: Pt } ) fn getPt(p: ^Pt) { p.x = 5 p.y = 7 } fn main() { cp := new(ClrPt) getPt(&cp.p) // <-- interior pointer printf(repr(cp^) + '\n') }qw1
28.07.2021 23:48Тут можно переписать на
ClrPt = struct { clr: uint32 p: ^Pt }
Да, чуть менее оптимально и у нас 2 аллокации вместо одной. Но для скриптового языка вообще не важно.
Tereshkov Автор
29.07.2021 00:27Не только чуть менее оптимально, но и вызывает много вопросов о времени жизни указателя при передаче в C.
По сути, вы предлагаете вычеркнуть классические структуры. Нет. Ради них всё и затевалось.
qw1
29.07.2021 01:12То есть, обратно в C вы передаёте только структуры без ссылок? Всё-таки, сильно специализированная задача у вас.
alsoijw
29.07.2021 19:42Довольно плохой пример, поскольку в данном случае, время жизни cp в main не меньше чему у cp.p, и это даже без каких-то ухищрений будет работать
Tereshkov Автор
29.07.2021 20:56Довольно плохой пример
Напомню, это был пример повсеместности указателей на середину структуры. Чем он плох в этом качестве, я так и не понял. Для полноты картины туда стоит добавить какую-нибудь функцию в программе на C, которая требует именно ClrPt как есть (чтобы совсем отбить соблазн заменять указателем).
Что касается времени жизни - да, в данном случае будет работать. Немного изменится скрипт - и уже не будет. В любом случае, я не собирался демонстрировать этим примером трудности анализа времени жизни указателей.
alsoijw
29.07.2021 19:39Притащить увесистую внешнюю зависимость
В чём эта «увесистость» заключается? std::weak_ptr тоже в тяжёлую зависимость записали?но при этом всё равно вручную перекодировать всю иерархию типов в битовые поля
Почему вручную? У вас же интерпретатор есть, пусть сам считает.(или теперь у Бёма это тоже можно?).
Здесь сказаноAt the beginning of the mark phase, all root segments (as described above) are pushed on the stack by GC_push_roots. (Registers and eagerly processed stack sections are processed by pushing the referenced objects instead of the stack section itself.) If ALL_INTERIOR_PTRS is not defined, then stack roots require special treatment. In this case, the normal marking code ignores interior pointers, but GC_push_all_stack explicitly checks for interior pointers and pushes descriptors for target objects.
kengur8
27.07.2021 20:51А чем ваш проект отличается от Lua?
Tereshkov Автор
27.07.2021 23:15+1Об этом я много раз говорил, и даже в комментариях под этим постом :) Не поленюсь повторить:
Статическая типизация: делает намерения программиста более ясными, позволяет обнаруживать несовместимости типов ещё на этапе компиляции скрипта и выдавать понятные сообщения об ошибках. Lua - динамически типизированный язык, ошибки типов обнаруживаются лишь случайно во время исполнения скрипта.
Типы данных, совместимые с типами C: позволяют скрипту легко обмениваться структурами данных с основной программой на C/C++, сохраняя при этом раскладку полей структур в памяти. Lua использует типы, совершенно чуждые C, и предлагает громоздкий механизм
userdata.
kengur8
28.07.2021 20:26Но есть такие вот тайпскрипты https://github.com/andremm/typedlua например. Хотя структуры данных это хорошо. Питонист во мне одобряет. Успехов.
OCTAGRAM
15.09.2021 00:06Интересно узнать, как у вас сделано зануление слабых ссылок. С этим проблема из-за того, что они по своей природе обязаны быть потокобезопасными. Разные потоки чего только не координируют, вот только не освобождение объектов. И образуется зазор, когда содержимое слабой ссылки уже зачитано в регистр, но ещё не произошёл AddRef. Прямо в этот момент объект может испариться, а на его месте появится другой или, чаще, мусор.
В Delphi эта проблема не решена. Чтоб пощупать, можно сделать Delay(10) в AddRef и Release, и попытаться работать из разных потоков в стиле, приближенном к естественному. Надёжная реализация слабых ссылок обалдеет, но честно покрутится в спинлоке, пока работает долгий AddRef. Delphi так не делает и разваливается. Я решение нашёл только в том, чтоб атомарной заменой перезаписывать саму ячейку, где лежит слабая ссылка, пока не отработает AddRef, и пока в ней признак блокировки, занулятор слабых ссылок крутится и ждёт.
Другое решение относится к архитектуре, когда для слабых ссылок отдельный более долгоживущий объект создаётся. Счётчик ссылок можно перенести в этот объект, и тогда CAS на нём заменяет более муторную схему со спинлоком на слабой ссылке.
Думал, как ещё можно устранить зазор. Неприятно, что для нативных потоков в общем нет какого-то взгляда Бога, нельзя увидеть, что поток уже зачитал слабую ссылку в регистр. Или можно? Напрашивается ещё такая схема: каждый поток регистрируется и получает TLS. В этот TLS он журналирует: я сейчас собираюсь получить такую-то слабую ссылку, а потом убеждается, что она всё ещё там, в ячейке, и только после этого идёт в AddRef. Деструктор не может отработать, пока есть поток, зачитавший указатель, но ещё не понявший, что дело идёт к концу.
Tereshkov Автор
15.09.2021 00:25И образуется зазор, когда содержимое слабой ссылки уже зачитано в регистр, но ещё не произошёл AddRef. Прямо в этот момент объект может испариться, а на его месте появится другой или, чаще, мусор.
Если я правильно вас понял, то эта проблема возникает только когда потоки переключает некий внешний планировщик. В Umka нет поддержки "родных" потоков операционной системы; виртуальная машина Umka работает всегда в одном системном потоке. Внутри виртуальной машины может быть множество её собственных "потоков", но за их переключение отвечает сам программист, вызывая
fibercall(). Этот подход я позаимствовал из Lua и Wren.
qw1
15.09.2021 10:20Я решение нашёл только в том, чтоб атомарной заменой перезаписывать саму ячейку, где лежит слабая ссылка, пока не отработает AddRef, и пока в ней признак блокировки, занулятор слабых ссылок крутится и ждёт
У объекта может быть много слабых ссылок. Пока занулили первую, вторая уже могла прочитать свою ссылку в регистр. Нужна критическая секция. Если нет конфликта входа в неё, она очень дешёвая (один compare-and-swap). Критическая секция нужна, т.к. объект хранит вектор своих слабых ссылок (чтобы обнулить их при своём удалении), и добавление в вектор без критической секции сделать непросто. Причём, в секцию надо заходить при
— создании новой слабой ссылки
— удалении слабой ссылки
— разыменовывании слабой ссылки
— в методе Release, если текущий счётчик = 1 (т.е. потенциально возможно удаление объекта и зануление слабых ссылок)
В методе AddRef в секцию заходить не надо, достаточно InterlockedIncrement
Объект так и
maxim_ge
А почему нельзя из адреса поля вычесть размеры предыдущих полей с учетом выравнивания?
Судя по исходнику требуется два параметра — указатель на страницу и указатель на поле.
khim
А почему нельзя из адреса поля вычесть размеры предыдущих полей с учетом выравнивания?А откуда у вас возьмётся информация о том, какие там вообще поля имеются? Вот есть у вас ссылка на какой-нибудь int. Ну int и int, как узнать какой структоре он принадлежит?
P.S. А вообще развитие IT идёт, как положено, по спирали… только вот не по той спирали. Каждое следующее поколение умудряется решить ту же задачу, какую решали до них, только хуже и менее эффективно. В большинстве случаев. Впрочем я как-то говорил с математиками, у них та же история: процент людей, изобретающих что-то новое ничтожен, большая часть работ — это то, что было до них, только “с перламутровыми пуговицами”.
MacIn
Мне кажется, более корректным будет объявить такие ссылки запрещенным приемом. Если мы имеем указатель на объект в структуре (или массив, структуру и т.д. — то, что требует нестандартного удаления, вызова деструкторов и т.д.), то у нас будет две ссылки на объект — от структуры и от типизированного указателя, а счетчик ссылок будет не в структуре, а в самом объекте.
А уж если мы ссылаемся на int, который просто будет выкинут на мороз, когда удалится структура — это уже из области ССЗБ.
Меня посещало дежавю — полуавтоматическое управление памятью в Delphi.
khim
А уж если мы ссылаемся на int, который просто будет выкинут на мороз, когда удалится структура — это уже из области ССЗБ.А тогда нафига вообще огород городить, если несмотря на “автоматическое управление памятью” у вас всё равно никаких гарантий ничего нету?
Меня посещало дежавю — полуавтоматическое управление памятью в Delphi.Ну да, масса языков через это проходят: C++, Delphi, всякие Operon'ы.
Обычно всё кончается либо “побитием горшков”, отказом от прямой совместимости с C, и прикручиванием трассирующего GC (с которым потом приходится бороться вечно), либо введением явного понятия “времени жизни” для переменных и развлекухой вокруг этого всего.
Пока только горстка языков прошли путь до конца и добрался до чего-то, на чём не страшно писать программу для управления ядерным реактором: Rust и Swift из больших
Большинство же как Delphi: у вас всё будет отлично… только если не вы не будете писать сложного кода… но для простого-то кода хватает “джентельменского набора” BASICа (классического: числа, строки, массивы… всё, хватит, наслаждайтесь)!
MacIn
Почему никаких гарантий нету? Есть гарантия, что пока на структуру есть ссылка, её поля валидны. А залазить через указатель «в кишки» — это уже запрещенный прием КМК. Ну, или надо примитивы box'ить, чтобы они тоже были refcounted. Но это — да, уже отказ от совместимости.
А так — зачем — затем, что это удобнее и зачастую безопаснее. Ну да, есть ряд ограничений «как нельзя делать, чтобы не выстрелить в ногу».
Я бы сказал, что с распространением интерфейсов в Delphi (в понимании именно этого языка, т.е. с refcount'ом по области видимости), спектр возможностей качественно расширился. Потому что и shared ptr'ы делаются, и stream-style collection'ы и пр. сложные вещи довольно просто, именно за счет полу-автоматического управления памятью.
qw1
Всё равно кривенько получается. Вроде как мы хотим иметь возможность взять указатель любой на int так же, как на int, отдельно выделенный в куче. Но кто мешает взять указатель на int, переданный параметром (в регистре или в стеке), и тогда уж точно ничто не спасёт от краха.
Согласен с комментатором выше. Надо делить типы на Value и Reference, как в C#. Тогда указатель (как Reference тип) на int будет просто невозможен. Указатель на середину структуры — тоже.
AnthonyMikh
Вот не надо, пожалуйста. Это — та самая вещь, которую лично мне в голове абсолютно не хочется держать. Да и с обобщённым программированием это дружит плохо.
Tereshkov Автор
Добавлю, что в Umka, как и в Go, не различаются классы и структуры (такое различение мне вообще кажется абсолютно искусственным). Методы навешиваются на структуры. Тогда каким типом должна являться структура: value или reference? Лично мне требуется value - для естественного взаимодействия с C.
qw1
Если нужно, чтобы язык автоматически управлял памятью, рантайму нужно понимать, кто владеет каждым из указателей.
А в Go можно сделать указатель на середину структуры?
Tereshkov Автор
Можно, конечно. И сами создатели не раз говорили об этом и анализировали проистекающие отсюда сложности: https://blog.golang.org/ismmkeynote
Tereshkov Автор
Не совсем понятное замечание. Вас не устраивает подсчёт ссылок как таковой? А что предпочитаете взамен?
khim
Я не вижу просто смысла изобретать ещё один какашкоязык непонятно для чего.
Если бы это была курсовая или даже дипломная работа — это можно было бы понять… хотя нет, всё равно нельзя: там обычно новизна требуется. Но какая цель вообще достигается этим велосипедом? Вроде как заявляется как скриптовый язык, но при этом структуры, совместимые с C, и списки. То есть вроде как что-то простое, но на самом деле нет.
Самое смешное, что я даже не говорю, что это не взлетит. Как раз если не влетит — так ещё полбеды, всё что случится — вы потеряете некое количество времени на бессмысленную работу.
А вот если взлетит — получим ещё несколько тысяч (или десятков тысяч) разработчиков, вынужденных тратить время и силы на то, что уже до них много раз сделали. На других языках.
Цель у этого всего какая? Куда это всё? Что вы умеете делать лучше, чем другие, те же Go, Lua, Haskell или Rust со Swift ом?
Tereshkov Автор
Я вижу, вы взялись унижать и оскорблять. Жаль. Ожидал более квалифицированной дискуссии. Особенно с учётом того, что когда-то в далёком прошлом вы, кажется, публиковали достойные материалы.
На оскорбления отвечать не стану. А вот на конкретные замечания не поленюсь ответить, хотя уже много раз это делал.
Именно так. Мне был нужен скриптовый язык, в котором я мог бы перекидывать структуры целиком в C и обратно. Это для меня фактор комфорта. Как и статическая типизация, которая делает намного более ясными намерения программиста и избавляет от огромного числа ошибок, с которыми я сталкиваюсь, например, в Python и ещё более в JS. Сейчас Umka используется у меня на работе в симуляторе динамики трактора.
Упоминание Go, Haskell, Rust, Swift я считаю вообще неуместным, поскольку всё это языки совершенно иного назначения. Остаётся Lua. Ну а преимущества относительно Lua я перечислил выше. Если же вопрос касался не языка в целом, а управления памятью, то моя задача тут не "делать лучше", а "делать достойно". Этого для начала вполне достаточно.
qw1
Tereshkov Автор
Структуры, содержащие указатели - разумеется, нельзя передать. Более того, я в принципе не представляю себе этого хоть в каком-нибудь скриптовом языке, коль скоро в C нет никакого автоматического управления памятью. Так что в таком виде эта "цель" и недостижима.
Но все прочие структуры - передавать можно и нужно. И таких в моей практике было большинство: векторы, матрицы, показания датчиков, наборы настроек. Ср. с использованием
userdataв Lua. Удобство очевидно.khim
Ну то есть я угадал? Вам нужна была “Lua с перламутровыми пуговоцами”?
Ну что ж… будет интересно посмотреть когда вы свой язык забросите и что будете делать с завязанными на него проектами.
Всяческих узбеков.
qw1
1. список структур SYSTEM_PROCESS_INFORMATION, получаемый через QuerySystemInformation(SystemProcessInformation). Там следующая структура начинается по оффсету, указанному в предыдущей.
2. список любых бинарных структур, прочитанных из файла в буфер одним большим куском.
Прямо в таком виде буфер нельзя отдать в umka, потому что как только будет выполнено в скрипте присваивание указателя, память перед объектом (где umka ожидает заголовок со счётчиком ссылок) будет испорчена.
То есть, вы какую-то свою частную задачу решаете. Думаю, проще было в тот же LUA прикрутить сериализатор из Си-объекта в lua-таблицу и назад. Копирование это не так страшно по производительности. В «больших» системах данные постоянно по сети гоняются, и ничего страшного.
Tereshkov Автор
Возможны алгоритмы со списками/деревьями, которые на выходе дают число/массив/структуру, которые уже вполне пригодны для передачи.
Не совсем понял. "Список" в узком смысле слова (с указателями) в файле хранить и нельзя. По-любому понадобится замена указателей на файловые смещения. "Список" в широком смысле слова (по сути, массив) передать можно вполне. Umka вовсе не требует наличия заголовка со счётчиком перед каждым куском, на который есть указатель. Возможны указатели на глобальные или стековые переменные, на переменные C. Требование наличия заголовка касается только памяти, выделяемой в куче Umka.
А что такое "общая задача"? Универсальных языков всё равно нет. Я решал на Umka свою задачу, какие-то чешские энтузиасты - свою и т.д. В каких-то задачах Umka удобен, в каких-то - нет. Для меня вот до сих пор поразительно, что предназначенный для сопряжения с C язык Lua имеет типы данных, вообще никак не стыкующиеся с типами C.
qw1
malloc, то и подсчёт ссылок выключается?Наверное, так можно. Но если в куче рантайме много страниц, это не очень оптимально будет, при каждой манипуляцией с указателем опеределять, попадает ли он в какую-то страницу кучи.
Tereshkov Автор
Именно так и сделано. И вот тут как раз было бы интересно понять, насколько это отличается, например, от того, что сделано в Go.
WASD1
Подождите только сейчас возник вопрос: а как вы планируете внутри Umka заводить указатели на переданные вам C-структуры?
Или всё это надо заворачивать в копирование данных "из C-структур в umka-структуры и обратно"?
Tereshkov Автор
Не очень понятен вопрос. В Umka передаётся структура или указатель на структуру? Если структура, то у неё есть адрес в стеке Umka, и ничто не мешает этот адрес взять. Если указатель на структуру (вам очень не хочется копировать в стек саму структуру), то в принципе вы и тут можете пользоваться этим указателем из Umka, но на свой страх и риск: Umka не управляет памятью по этому указателю.
WASD1
Да имел в виду второй случай, но не лишне было бы уточнить.
А как вы берёте указатель на стек?
Просто определяете, что это указатель на стек и не считаете ссылки?
Tereshkov Автор
Да. Если указатель не попадает ни на одну выделенную страницу кучи, значит и ссылки для него не считаются.
Другое дело, что иногда приходится и сам кадр для локальных переменных устраивать не в стеке, а в куче. Но это нюансы.
khim
Я вижу, вы взялись унижать и оскорблять.Где, кого, как? Какашкоязык — это, в принципе, состояние любого нового языка сразу после релиза, “микроязыка” — в особенности. Даже на каком-нибудь оригинальном Pascal (где не было указателей на функций) мало чего можно написать.
Уж сколько я этих поделок видел. Конечных состояний в 99% случаев — ровно два: либо язык удовлетворяет потребности автора, но не позволяет решать почти никаких других задач (выпиливается из соотвествующих проектов при первой же возможности как только отттуда свалит автор), либо, что куда хуже, им начинают пользоваться, по необходимости, многие — а в результате получаем многоуровневые слои костылей (что-нибудь типа такого).
В очень редких случаях языку-таки везёт и, вбухав в него тысячи человеко-лет, его доводят до состояния, когда при работе с ним не очень тошнит (хорошо известные примеры — Java, JavaScript, PHP, Python), но как-то странно затевать что-то новое в рассчёте на то, что с вашим языков такое произойдёт.
Особенно с учётом того, что когда-то в далёком прошлом вы, кажется, публиковали достойные материалы.Было дело. Когда казалось, что на Хабре есть люди, которым было бы интересно чему-то научиться. Однако большинство — они ж чукчи-писатели, не чукчи-читатели. Ваш пример — как раз очень показателен.
Упоминание Go, Haskell, Rust, Swift я считаю вообще неуместным, поскольку всё это языки совершенно иного назначения.Это с какого перепугу? Вот вам скрипты на Go в системе сборки Android, Haskell используется для скриптов настолько часто (инструкция), что любители даже PureScript изобрели, чтобы всё это в браузере использовать, Swift тоже можно, было бы желание. Вот Rust да, в последнее время на нём как-то перестали скрипты писать.
Остаётся Lua. Ну а преимущества относительно Lua я перечислил выше.Ну то есть мотивация в стиле “ничего, кроме C и Lua я толком не знаю, но я ж не гений, я не мегагений, я омегагений — ща как создам… все ахнут”.
Таким путём можно создать только какашкоязык. Если вы “попадёте в струю” (как один известный товарищ сумел), то ваш язык, возможно, подхватят другие (как с PHP случилось) и превратят его… ну не в конфетку, конечно, но хотя бы во что-то, от чего при первом взгляде сразу глаза слезиться не будут.
Но это сродни выигрышу в лотерею, вряд ли вы на это рассчитываете.
Вот потому я и пытаюсь понять — зачем?
Этого для начала вполне достаточно.Для начала чего, извините? Чтобы вы сами смогли свой язык использовать? Для этого вообще почти ничего не нужно: вы-то всё про него знаете и “делать странного” не будете.
А вот когда им начнут пользоваться другие… вот тут-то и начинаются чудеса: либо вам приходится составлять талмуды на тысячи страниц с сотнями правил на тему “как правильно держать наш телефон” (C и С++ прекрасные примеры), либо потребуется в ваш язык кому-то вбухать сотни (или, скорее, тысячи) человеко-лет разработки.
Tereshkov Автор
Получается вычислительная сложность, линейно растущая с количеством полей. Ну и если вообразить "матрёшку" вложенных типов, то требуется обратный проход по ней -- изнутри наружу. Такой возможности нет, да и не совсем понятно, как реализовать.
Да. Посмотрите на мой список из четырёх шагов. Первый шаг как раз даёт страницу, второй шаг -- указатель на заголовок, когда страница уже найдена. Вы говорите о втором шаге.