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

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

Тут надо понимать, что этот тип опциональный. Т.е. его вообще может не быть в stdint.h.

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

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

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

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

Наличие таких расшрений говорит о том, что стандарт сам по себе не полон и требует доработок.

короче, утыкаться рогом в «стандарт» - значит противеречить мировой практике. И проще поменять «стандарт», чем эту самую практику.

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

Вообще-то, нет. Это нужно для взаимооднозначного соответствия всего возможного множества указателей некоторому множеству неотрицательных (или просто целых в случае с intptr_t) чисел.

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

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

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

Конкретно под GNU/Linux + gcc английским в ASCII сказано:

The C standard says the two pointers must point within the same object in memory, but on GNU/Linux systems these operations simply compare the numeric values of the pointers.

А так?

bool in_heap2 = (ulong)p >= (ulong)heap2 && (ulong)p < (ulong)heap2 + 100;

Что за кучи? Двоичные кучи? Фибоначчивы кучи? Или это динамическая память в «куче»?

А если так:

ssize_t off = p - heap;
return (off < heap_size) && (off >= 0);

Добавь бит в начало слова для маркировки. Нечетных адресов на основных платформах не бывает. Прочитал о таком приеме из книги по языку Rust

Ну, зависит от размера слова, конечно. Если не байты. Короче, добавь бит (в начало, или в конец), а потом по нему смотри

n и так как минимум 2 в любом современном аллокаторе.

Я бы сказал – все 4: https://en.cppreference.com/w/c/types/max_align_t.html

Впрочем, возможно это не про «любой современный», а только про стандартный malloc().

автор тут про CHERI рассказывает, но гораздо более осязаемый пример того, где наивная арифметика на intptr сломается, это arm64 PAC. Стоит так же напомнить про разнообразные варианты top byte ignore, которые есть и у arm и у вендоров x86

А если просто

char *memory = malloc(heap1_sz + heap2_sz);
char *heap1 = memory;
char *heap2 = memory + heap1_sz;

И тогда in_heap на любые адреса из memory прекрасно работают.

Где-то ТС писал, что такое ему не надо, т.к он еще и изменять размер heap’ов хочет.

Тогда только использовать вместо указателей индекс внутри кучи. А во второй куче в индексе использовать 1 бит для указания номера кучи.

Он троллит сишников чтением стандарта, пока я в бане :D

Багиня уже ведётся вон.

По теме: используй тегированные указатели.

Ну, никто не мешает ТС’у одну из куч увеличивать вниз от общего указателя, либо мапить нужные страницы себе по нужным адресам. mmap() конечно в стандарт Си не входит, но на стандартном Си ничего особо интересного и не напишешь. Крайне убогонький говноязычок.

Вот кстати очевидно, что UNIX не работает на стандартном С, значит вносит какие то дополнительные требования на компиляторы, где бы их прочесть?

Ядро просто конвертирует указатель к u64. Например, тут: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/io_uring/rsrc.c#n96

Если ядро может, ты тоже можешь.

я тебе ничего не обязана показывать, детка. код под NDA.

Твой код под N/A. Потому что его не существует.

Вот кстати очевидно, что UNIX не работает на стандартном С, значит вносит какие то дополнительные требования на компиляторы, где бы их прочесть?

Примерно нигде. Весь сишный код пишется по принципу «мы пытаемся на%;ать компилятор и надеемся, что это прокатит».

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

Конкретно под GNU/Linux + gcc английским в ASCII сказано:

The C standard says the two pointers must point within the same object in memory, but on GNU/Linux systems these operations simply compare the numeric values of the pointers.

ДА ТЫ Ж МОЙ СЛАДЕНЬКИЙ!

Just because two pointers print the same and have the same bit-pattern doesn’t mean they need to compare equal

Из этого следует, что если он в рантайме принял состояние со значением 0, то в NULL состояние он не переходит.

А это где так? В msvc по крайней мере вроде было даже, что #define NULL 0. Я поэтому очень обрадовался, когда в плюсы завезли nullptr, не нравился мне этот NULL никогда.

А это где так?

Думаю на любой платформе где NULL указатель в реальности указывает не на 0.

… представим что массив «a» находится в сегменте 1, а массив «b» в сегменте 2. Сравнивая близкие указатели мы можем получить вообще равные значения и ничего не переместить.

В защиту MOPKOBKA скажу, что это действительно так, не без нюансов, но в целом да.

По теме вопроса, на мой взгляд, вариантов решений всего два:

1. Тэгированный указатель, вместо обычного char *p, но это сложно и программа станет залоченной на конкретный процессор (его максимальное значение адреса). Вариант «тегирования» в виде своей структуры и признака к какой куче относится указатель, вместо обычного char *p, который будет работать везде:

typedef struct
{
    bool HeapIndex;
    char *Ptr;
} HeapPtr_t;

HeapPtr_t VarFoo, VarBar;

VarFoo = malloc_heap1(100);
VarBar = malloc_heap2(100);

VarFoo.Ptr[0] = 'A';
VarFoo.Ptr[1] = (char)0;

VarBar.Ptr[0] = 'B';
VarBar.Ptr[1] = (char)0;

free_heaps(&VarVarFoo);
free_heaps(&VarBar);

// Претензии на счет памяти не принимаются, т.к. если из-за увеличения места под хранение HeapPtr_t вместо char *p, программа не помещается в память - значит, либо не правильно выбрано железо, на котором это всё будет работать, либо не годится решение с двумя кучами для данного железа. Без вариантов.

2. Хардкор в коде, что эта переменная выделена в куче1, а эта в куче2, и потом не перепутай при освобождении.

но по стандарту только константой можно указатель сделать NULL

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

Тэгированный указатель, вместо обычного char *p, но это сложно и программа станет залоченной на конкретный процессор

Не обязательно.

char *heap1, *heap2;

char* deref(uintptr_t fat_pointer)
{
  char *base = fat_pointer & 1 ? heap1 : heap2;
  return &base[fat_pointer >> 1];
}

uintptr_t heap1_ref(char *ptr)
{
  return (ptr-heap1) * 2 + 1;
}

uintptr_t heap2_ref(char *ptr)
{
  return (ptr-heap2) * 2;
}

Подобные варианты предлагались автору чуть выше, но он сам указал, что речь не о Linux, а об «универсальном» решении.

return &base[fat_pointer >> 1]; … return (ptr-heap2) * 2;

Такой код не будет работать там, где ОЗУ располагается в старших адресах адресного пространства, например, с 0x80000000. Поэтому я и указал, что программа станет залоченной на конкретный процессор.

Такой код не будет работать там, где ОЗУ располагается в старших адресах адресного пространства, например, с 0x80000000.

Что помешает? Ну будет у тебя base = 0x854000000, например, и что?

Код не будет работать только в том случае, если в одной из куч получено больше UINTPTR_MAX / 2 байтов.

Стандарт C ничего не говорит о структуре uintptr_t. И даже не гарантирует его наличия в принципе, это опциональный тип. Ты пытаешься использовать младший бит, предполагая, что он неиспользуемый. Но стандарт не даёт никаких оснований для таких предположений.

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

void *p1 = get_p();
uintptr_t u = (uintptr_t) p1;
void *p2 = (void *) u;
if (p1 != p2) {
  // This cannot be!
}

void *p1 = get_p1();
void *p2 = get_p2();
uintptr_t u1 = (uintptr_t) p1;
uintptr_t u2 = (uintptr_t) p2;
if (p1 == p2 && u1 != u2) {
  // This can be!
}

может там си вообще не реализуем?

Ну на embedded world дум на cheri linux пускают, а дум-то на сях написан.

Стандарт C ничего не говорит о структуре uintptr_t.

Он говорит, что это беззнаковое число.

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

uintptr_t u1 = (uintptr_t) p1;

Я вообще не преобразую указатель в него. У меня младший бит числа = идентификатор кучи. Остальные биты = число-индекс байта в куче.

Если я знаю, что в куче не больше 100 элементов, могу вместо uintptr_t использовать unsigned char, будет однобайтовый «указатель».

Ок, невнимательно код прочитал, извини. Тогда непонятно, зачем ты вообще используешь этот тип, он тут ни к селу, ни к городу. Тебе надо использовать тип ptrdiff_t. Правда не факт, что при умножении на 2 он не переполнится, это лучше проверить.

Тебе надо использовать тип ptrdiff_t.

Мне беззнаковый надо. Хотя согласен, лучше size_t.

Правда не факт, что при умножении на 2 он не переполнится, это лучше проверить.

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

if(x < n) return &heap1[x] else return &heap2[x-n].

Мне беззнаковый надо. Хотя согласен, лучше size_t.

Или нет. На сегментной модели памяти size_t и ptrdiff_t могут быть ограничены размером одного сегмента, а uintptr_t всё-таки размером всего адресного пространства.

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

Что помешает? Ну будет у тебя base = 0x854000000, например, и что?

Код не будет работать только в том случае, если в одной из куч получено больше UINTPTR_MAX / 2 байтов.

Ок, принимается.

А как будешь кодировать отсутствие адреса (NULL) в uintptr_t?

uintptr_t

Это просто целое беззнаковое число, monk просто ввел свой уникальный тип (для куч heap1 и heap2), который хранит смещение относительно одного из двух базовых адресов этих куч. Часть бит типа uint отводится под номер кучи, а часть под смещение в куче с заданным номером.

typedef unsigned int uintptr_t;

При выделении памяти в одной из куч программист сам назначает к какой куче относится адрес с помощью heap1_ref() или heap2_ref(). Но смещение потом нельзя использовать без преобразования к адресу, для этого придется добавлять переменную и делать ей deref() или сразу подставлять deref() в код. Понятно, что тут показана идея, но в реальности deref() должен быть более защищен и сложен, учитывать и проверять размер куч и возвращать NULL при выходе за границы куч.

Плюс не учтен UINT_PTR_NULL (число, аналог NULL-а для обычных адресов, но только для uintptr_t), этот аналог не должен принадлежать ни одной из куч, и deref(UINT_PTR_NULL) = NULL. Смещение 0 занято для первой кучи, так что простой ноль в текущей вариации использовать нельзя.

Но очень хочется, чтобы UINT_PTR_NULL = 0, для паттерна:

uintptr_t VarRefPtr = UINT_PTR_NULL;
...
if (!VarRefPtr)
  return;

Значит надо больше бит под номер кучи и меньше под смещения (под максимальный размер куч). Т.е. реальный код, вероятнее всего, будет работать на размерах куч UINTPTR_MAX / 4 байтов.

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

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

Тогда так:

size_t n;

heap1 = malloc(n);
heap2 = malloc(...);

char* deref(uintptr_t x)
{
  if(!x) return NULL;
  x--;
  if(x < n) return &heap1[x] else return &heap2[x-n].
}

ТС писал:

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

Так что без размера кучи было более корректно.

PS. Как я понял, вопрос был праздный ради дискуса за какой-то из ISO-стандартов на Си, т.е. ТС уже давно сделал как хотел да и всё.

Aho Alfred V. Hopcroft, John E. Ullman, Jeffrey D. - Data Structures and Algorithms (1983, Pearson)

смотри position как способ сокрытия raw адресов ( в примере реализации списков и интерфейса к ним)

ваще «абстрактная» алгебра

даже не алгебра как таковая

а чисто понимание о множествах и невозможности конечным множеством перенумеровать множество большее на 1 элемент взаимно-однозначно

от сюда вот эти вот ad-hoc с «ошибкой Хоара» и наворачиваем особых случаев особых случаев в стандарте(ибо «мне и Ленин не икона»)

очередные шашечки или ехать

в целом Сяшка это целевой язык - писать на ней это признаватся что находишься в настолько трудной жизненной ситуации -

ибо есть Ада есть (экстримисткий?) Rust

есть Coq

крч писать на правильном языке и транслировать копулятором в ассемблер (С как вариант ассемблера как и JS)

LLVM и прочий mlir вот путь

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

Покажи свой код.

уважающие себя люди не пишут опенсорс