LINUX.ORG.RU

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

 ,


0

6

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

Для второй кучи я собрался написать GC, но как я могу отделить элементы первой кучи, от элементов второй кучи?

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

bool in_heap(char *heap, ssize_t heap_size, char *p)
{
  return p >= heap && p < heap + heap_size;
}

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

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

★★★★★

Последнее исправление: MOPKOBKA (всего исправлений: 3)
Ответ на: комментарий от MOPKOBKA

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

начать можно с того, что на большинстве платформ (а большинством будут не мейнстримные ОСи, а множество мелких контроллеров) нет никаких потоков, например.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

но вот универсальный переносимый memmove или malloc написать нельзя, который будет работать на любом предполагаемом компиляторе совместимым по стандарту на 100%.

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

https://cppreference.com/w/c/language/memory_model.html

The data storage (memory) available to a C program is one or more contiguous sequences of bytes. Each byte in memory has a unique address. 
alysnix ★★★
()
Ответ на: комментарий от MOPKOBKA

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

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

uintptr_t

Тред не читал.

LamerOk ★★★★★
()
Ответ на: комментарий от alysnix

Тут есть две проблемы:

1) memmove может работать на двух разных массивах

2) привилегия перемещать данные побайтно есть только у встроенных функций, типа memcpy и memmove

memmove можно написать для работы на одном массиве с использованием memcpy. Урезанную версию написать можно.

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 1)
Ответ на: комментарий от LamerOk

Прочти заголовок треда, это ID, на некоторых платформах его сравнение даст непонятно что. Я предполагаю что такой платформой будет RISC-V CHERI.

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 3)
Ответ на: комментарий от MOPKOBKA

и что. ты утверждаешь, что memmove «нарушает стандарт». а я говорю, что memmove орудует в рамках модели памяти си и ничего не нарушает.

memmove может работать на двух разных массивах

тут не понял. он вообще принимает void* и про какие-то массивы не знает ничего. и запросто стравнивает адреса, и не заморачивается как ты.

alysnix ★★★
()
Ответ на: комментарий от alysnix

а я говорю, что memmove орудует в рамках модели памяти си и ничего не нарушает.

Ему нужно сравнить указатели. Вот смотри:

char a[2];
char b[2];
memmove(a, b, 2);
Если тут вместо memmove будет my_memmove, то ты начнешь сравнивать указатели из разных массивов, и нарушишь стандарт. Что бы ввести это в реальность, представим что массив «a» находится в сегменте 1, а массив «b» в сегменте 2. Сравнивая близкие указатели мы можем получить вообще равные значения и ничего не переместить.

MOPKOBKA ★★★★★
() автор топика

Выдели обе кучи одним куском. Посредине поставь разделитель. Будет по стандарту.

Альтернативно, можешь на ассемблере написать свой in_heap. Там нет UB.

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

vbr ★★★★★
()
Последнее исправление: vbr (всего исправлений: 1)
Ответ на: комментарий от vbr

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

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

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

У RISC-V CHERI этот тип больше size_t, и не является обычным.

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от MOPKOBKA

построй свои кучи на массиве байт… :)

то ты начнешь сравнивать указатели из разных массивов

функция принимает void* то есть тупо физ адрес, а даже если там сегментная адресация - это будет segment:offset. и их сравнение будет делаться через вычисление плоского длинного адреса. но это будет уже «другой си». такой «си» уж точно не стандартен.

alysnix ★★★
()
Ответ на: комментарий от MOPKOBKA

Я думаю, в рамках стандарта C ничего лучше не придумать. Все варианты, укладывающиеся в стандарт (типа хранить пару "номер кучи + сдвиг/указатель) будут тормозить абсолютно без нужды на обычных архитектурах. Т.е. ради RISC-V CHERI, про который ты, вероятно, знаешь только из любознательности, ты будешь жертвовать производительностью на тех компьютерах, где программа реально будет работать. Если, конечно, задача не теоретическая. А что там делать на RISC-V CHERI - я не знаю, видимо какой-то специфический код под эту архитектуру писать.

vbr ★★★★★
()
Последнее исправление: vbr (всего исправлений: 1)
Ответ на: комментарий от firkax

вред форуму приносят и юзеры типа того автора, на что у меня очевидно негативная реакция

Ты наверное удивился бы, если бы не был поехавшим агрессором (это не оскорбление), но вред форуму приносят люди типа тебя. Человек спрашивает про апач - ты приходишь со своим ценным мнением, что апач не нужен «и депрекейтед». Ты это слово выбрал только потому что оно звучит как-то? Дед, прими таблетки.

Зачем ты ходишь в треды про докер и рассказываешь что докер не нужен? Тебя же не спрашивали. И в остальных вопросах так.

У тебя нет опыта реальной работы

У тебя есть локалхост под кроватью по заветам спуфинга

У тебя нет опыта программирования (да, все видели твой код уже. Лучше бы не видели).

Дед, не засоряй наш лор.

anonymous
()
Ответ на: комментарий от Iron_Bug

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

причем тут она…вообще непонятно.

alysnix ★★★
()
Ответ на: комментарий от alysnix

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

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от alysnix

функция принимает void* то есть тупо физ адрес

Компилятор на основе того что ты сравниваешь внутри src и dst должен по хорошему сгенерировать функцию как принимающую только близкие указатели. Потому что сравнение src и dst означает что это может быть только один объект. (предположим что объект всегда лежит в одном сегменте).

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от alysnix

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

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

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от MOPKOBKA

Нашел c/c++ programming manual для CHERI, там сравнивать uintptr_t можно нормально, для него в компиляторе перегружены операции, и хоть он и хранит теги, плюс, минус, сравнения генерируют особые команды которые не учитывают ничего кроме байтового адреса: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-947.pdf

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от Iron_Bug

а морковкин не ищет легких путей. вот он придумал 2 кучи, и застрял на неведомой архитектуре (которую в жизни не увидит - CHERI), потому что там память с прибабахом. и нам мозги пудрит тут.

alysnix ★★★
()
Ответ на: комментарий от Iron_Bug

и писать про какую-то «лёгкую многозадачность» в контроллерах - ну, это бред.

Это твоя ограниченность. Ты говорила что и GC на С никто не использует. Я показал что это не так.

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

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от alysnix

memmove везде работает, это же builtin. Зато на CHERI такой код не работает:

void heap_realloc(size_t new_size)
{
  heap_t *old_ptr, *new_ptr;

  old_ptr = heap1;
  new_ptr = realloc(old_ptr, new_size);
  fix_offsets(heap1, (ptrdiff_t)old_ptr - (ptrdiff_t)new_ptr);
}

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от MOPKOBKA

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

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

vbr ★★★★★
()
Ответ на: комментарий от alysnix

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

vbr ★★★★★
()
Ответ на: комментарий от Iron_Bug

Откуда тебе знать про «крупные проекты»? Если ты конвексу что-то писала, это не крупный проект :) у тебя же нет реального опыта хайлоад, ну серьезно.

anonymous
()
Ответ на: комментарий от anonymous

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

тогда как каст в длинные и любые потом сравнения ничто не нарушают.

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

alysnix ★★★
()
Ответ на: комментарий от vbr

Просто на этом форуме профессиональных программистов почти нет.

Были, пока их местная модерация не выкинула. В итоге мы поменяли условного mv на димеза, хоббита который формочки на кутях рисует, и срх (графоман хз откуда взялся на моем лоре).

Ну и что в итоге? Люди без реального опыта разработки и спуфинги с локалхостами.

anonymous
()
Ответ на: комментарий от alysnix

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

Можно, «Правда такая ерунда получается...».

а эта чудаковатая архитектура нерелевантна

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

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 2)
Ответ на: комментарий от anonymous

Даже Эдик, простите уж за прямоту, был полезным участником форума. Технарь, кодер (ну тоже не особо, но он хотя б примерно понимал).

Покажите мне может патч от лоровца в крупный проект (AP не считается). Где ваш код?

anonymous
()
Ответ на: комментарий от MOPKOBKA

Можно, «Правда такая ерунда получается…».

Ну вообще-то undefined behavior это, таки, нельзя. Компилятор, например, может тупо выкинуть этот код, если сможет это понять. Типа если ты сравниваешь несравнимое, значит сюда управление вообще не должно было доходить, значит код генерировать не будем, а куда там управление пойдёт - вообще плевать. Я с таким сталкивался, когда while (true){} C++-ный компилятор выкидывал вместе с эпилогом функции. Была полная ржака - вызываешь функцию и управление просто переходит на следующую функцию (со слегка попердоленным стеком).

vbr ★★★★★
()
Ответ на: комментарий от MOPKOBKA

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

значит решение найдено, и «теги» больше не нужны? вся проблема была в поиске - куда правильно кастовать чтобы сравнить?

alysnix ★★★
()
Ответ на: комментарий от vbr

Ну вообще-то undefined behavior это, таки, нельзя.

Что именно? alysnix про каст в uintptr_t и сравнение уже его. Сравнить можно, это же «наследник» unsigned integer. Но там будет битовый шаблон адреса, где могут быть и теги, и что угодно.

MOPKOBKA ★★★★★
() автор топика
Ответ на: комментарий от MOPKOBKA

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

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

vbr ★★★★★
()
Ответ на: комментарий от vbr

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

Именно про это я и пишу почти весь тред.

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

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

MOPKOBKA ★★★★★
() автор топика
Последнее исправление: MOPKOBKA (всего исправлений: 3)