Си без UB/ID: Две кучи и GC, как?

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

как-то непонятно, что у тебя за кучи, о которых тебе самому ничего не известно.

Мне точно известны адреса и размеры heap1, heap2. Только мне нужно определить принадлежит ли элемент (его адрес и размер тоже известен) к heap1 или к heap2.

Но в стандартном С не допускается сравнение указателя с heap1, если указатель указывает на самом деле на heap2, это может вернуть true для in_heap(heap1, heap1_size, p).

Короче проблема в том что функция которую я написал в ОП-посте, она не по стандарту.

Готов перейти на дескрипторы вместо указателей, но это не должно тормозить.

Например выравнивать все адреса на границы 2**n и несколько младших бит использовать для флагов. n и так как минимум 2 в любом современном аллокаторе.

В p[-1] клади маркировку кучи

если у тебя кучи - это непрерывные куски памяти, то кто тебе запретил сравнивать указатели?

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

У меня структуры не требуют выравнивания, поля организуют «выравненный размер». У меня такой подход на 40% увеличит расход памяти.

Но такой подход хорошо подходит если нарушить стандарт, и если структуры в основном имеют padding в конце, получилась бы бесплатная маркировка.

char *heap1 = malloc(100);
char *heap2 = malloc(100);
void *p = heap1 + 50;

// Вот так мне запретил делать стандарт
bool in_heap2 = p >= heap2 && p < heap2 + 100; 

Указатели можно сравнивать только если они указывают на один объект.

если у тебя данные выделяются как попало, то ты не определишь, какие надо освобождать. обычно ручные пулы - это некие куски памяти, которые помечены, как занятые или свободные. либо там счётчики ссылок, например, и GC помечает блоки с нулевым счётчиком как свободные. я пока не понимаю саму проблему. мне кажется, ты начал есть слона не с той стороны.

Круто, а malloc распиши, как он должен гарантировать твою хотелку? Интересный кейс.

если у тебя данные выделяются как попало, то ты не определишь, какие надо освобождать.

У меня трассирующий GC, и есть корни. Так что я знаю какие объекты еще нужны, а какие нет.

обычно ручные пулы - это некие куски памяти, которые помечены, как занятые или свободные. либо там счётчики ссылок

У меня нету состояния элемента в пуле, или счетчика ссылок.

я пока не понимаю саму проблему.

Я хочу пройтись GC по второй куче, от общих корней, но что бы удалились только элементы из второй кучи.

а чего вдруг? ты можешь сравнивать что угодно с чем угодно. если ты сам понимаешь, куда указывают твои указатели.

а чего вдруг? ты можешь сравнивать что угодно с чем угодно. если ты сам понимаешь, куда указывают твои указатели.

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

When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object,pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

Перепиши вопрос, я не понял.

• К intptr_t кастануть
• Явно залукапить в таблице аллокаций второй кучи

К intptr_t кастануть

intptr_t нельзя сравнивать вообще, это на RISC-V CHERI не будет работать. Там в числовое представление включаются и всякие теги, которые помешают сравнению.

Явно залукапить в таблице аллокаций второй кучи

Очень медленно.

тогда ты знаешь и адреса этих объектов. malloc тебе вернёт адрес на непрерывный блок памяти. если не сможет выделить - вернёт ошибку. непонятно, в чём проблема.

Ну а если выделить память одним куском, к которому уже обращаться, как к двум кучам? Или принципиально иметь два места?

Ну вот смотри, у меня есть функция heap_free_ptr, которая освобождает элемент в пуле.

Я прохожусь по корням рекурсивно и определяю неиспользуемые элементы.

Теперь я для каждого элемента который должен быть собран GC, вызываю функцию remove_ptr_only_if_ptr_from_heap2, которая должна освободить элемент ТОЛЬКО если он из heap2. Вот тебе заглушка:

extern char *heap1;
extern size_t heap1_size;

extern char *heap2;
extern size_t heap2_size;

void remove_ptr_only_if_ptr_from_heap2(char *p)
{
  // Вместо многоточия нужен код
  bool is_from_heap2 = ...;

  if (is_from_heap2) {
    heap_free_ptr(heap2, p);
  }
}

У тебя пространство единое линейное? Ну и в чём тогда проблема, сравнивай указатели.

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

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

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

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

Поэтому стандартом сишечки не покрывается.

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

Если в указателе есть «лишние» биты, это в любом случае требуется знать, сишечки сама по себе это не решает.

В общем, если тебе не нравится UB, то обмазываемся ifdef-ами на предмет платформы и компилятора и сравниваем указатели ассемблерными вставками.

я не знаю, что ты там интерпретировал как «стандарт». в Си таких ограничений точно не было и нет. потому что иначе там бы не работало вообще ничего. начиная от массивов и работы со строками и заканчивая всем управлением пулами вообще.

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

Ты когда объекты создаешь разве не знаешь где они лежать должны? Храни прямо в объекте.

проверку на диапазоны адресов, естессна

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

обысно при освобождении блока при вызове функции освобождения памяти в пуле пометка блока как свободного делается сразу.

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

ты пытаешься натянуть сову (какие-то конструкты из других ЯП) на глобус(сишечку). а они несовместимы

В ядре rcu используют, тоже самое.

Если ты сам держишь свои кучи, то компилятор не в курсе, что это разные кучи.

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

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

Знаю, но это увеличит размер занимаемой памяти, у меня много маленьких элементов. Сделал пометку в ОП-посте.

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

с указателями это единственный способ, каст в числа не УБ а только ИБ, придётся #ifdef-ить( сишка страдать), т.е. выключаешь теги и сравниваешь Ну или выделить массивы и сравнивать индексы, можно будет на размерах этих индексов память сэкономить

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

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

с указателями это единственный способ, каст в числа не УБ

Я не говорил что каст числа это UB. Я говорил что это число может представлять собой что угодно, и поэтому нет никакого смысла его сравнивать.

Ну или выделить массивы и сравнивать индексы, можно будет на размерах этих индексов память сэкономить

Тогда придется две арены выделять в одном массиве, и при увеличении первой, сдвигать всю вторую арену. Придется еще считать два смещения, один от божественного массива, второй от арены в этом массиве.

либо выделение и удаление объекта в какой-то момент, когда ты знаешь. что он больше тебе не нужен

Я не знаю, в это время над объектом может работать другой поток вообще, может мне он сейчас и не нужен больше, но другому потоку нужен.

либо счётчики ссылок

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

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

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

Я говорил что это число может представлять собой что угодно,

тебе же их только сравнить, главное чтобы одназначность с исходным указателем сохранялась

Тогда придется две арены выделять в одном массиве

не надо ничего сдвигать, просто два отдельных независимых массива

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

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

Мьютексы тормозят, я хочу быструю программу, а не медленную, поэтому выбрал трассирующий GC.

и всё равно непонятно, при чём тут какой-то GC. никак он не привязывается к пулам, как ни натягивай.

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

тебе же их только сравнить, главное чтобы одназначность с исходным указателем сохранялась

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

не надо ничего сдвигать, просто два отдельных независимых массива

А как понять что некий индекс принадлежит массиву 1, а не массиву 2?

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

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

Интересно. Либо ты усложняешь задачу, либо это и правда что-то серьёзное.

Так спинлоки тут не помогут, вот я вызову из треда #1 свой element_free(), и он будет крутить спинлок еще 10 дней, пока тред #2 использует эти данные.

А трассирующий GC в отдельном потоке, просто идет от корня и записывает все элементы которые найдет, а потом удаляет все элементы которые не были записаны в его список. Это просто, и производительно.

Короче GC это идеально подходящий вариант для моей динамической структуры которая часто переиспользует элементы.

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

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

Решение которое не работает в стандартом С:

если у тебя своя куча, то она должна строиться на некоем диапазоне адресов. то есть не парься и бери просто диапазон.

я всегда так делал и жив до сил пор:)

Вот заговорил я про Ast, и вспомнил что в GCC есть GC: https://gcc.gnu.org/onlinedocs/gccint/User-GC.html

то делай счётчики. счётчик уменьшился и всё.

На второй круг пошли, я уже писал что счетчик тормозит (и занимает память), и не работает с зацикленными структурами. Для маркировки GC достаточно одного бита на объект, ну или два если цвета два, биты можно хранить в битовой карте, а счетчик он 4 байта к примеру. В 32 раза меньше памяти нужно хранить на объект.

Разнообразь жизнь, придумай решение которое не нарушает стандарт!

Могут быть зашиты теги например.

Учитываешь эти теги, в доке к компилятору должны быть описаны раз это ИБ

А как понять что некий индекс принадлежит массиву 1, а не массиву 2?

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