Работа с Heap, Из любопытства, но для понимания Опции

[SasaVitebsk]

Столкнулся с интересным феноменом. Я его не понимаю. Может кто объяснит популярно.
Сначала приведу пример:

Есть два варианта:
1)

Код

   OW_Rom_Device=CurrentAddr=malloc(8);            // Çàðåçåðâèðîâàòü ïàìÿòü ïîä ROM

2)

Код

   OW_Rom_Device=malloc(0);
....
   CurrentAddr=malloc(8);            // Çàðåçåðâèðîâàòü ïàìÿòü ïîä ROM

В первом случае адреса OW_Rom_Device и CurrentAddr - одинаковы.
Во втором CurrentAddr больше на 2 байта.

Вопросы: почему и зачем?
(Пояснения:между данными операторами с кучей никто не работает; если вместо malloc(0) ввести malloc(1) разница будет 3 байта)

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

[makc]

Разница между адресами во втором варианте будет зависеть от реализации malloc'a.
Никто не обещает, что malloc должен возвращать последовательные или, вообще говоря, связанные адреса. Единственно что гарантируется - если память выделена, то вернется указатель на ее начало.

[_Bill]

Столкнулся с интересным феноменом. Я его не понимаю. Может кто объяснит популярно.
Сначала приведу пример:

Есть два варианта:
1)

Код

   OW_Rom_Device=CurrentAddr=malloc(8);            // Çàðåçåðâèðîâàòü ïàìÿòü ïîä ROM

2)

Код

   OW_Rom_Device=malloc(0);
....
   CurrentAddr=malloc(8);            // Çàðåçåðâèðîâàòü ïàìÿòü ïîä ROM

В первом случае адреса OW_Rom_Device и CurrentAddr - одинаковы.
Во втором CurrentAddr больше на 2 байта.

Вопросы: почему и зачем?
(Пояснения:между данными операторами с кучей никто не работает; если вместо malloc(0) ввести malloc(1) разница будет 3 байта)

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

Само собой. Адрес нужен для корректного освобождения динамеской памяти по функции free. Фактически отдельные фрагменты "кучи" представляют собой элементы списка. У K&R функция malloc подробно расписана. Можете там посмотреть.

[Сергей Борщ]

Во втором CurrentAddr больше на 2 байта.
Вопросы: почему и зачем?

Добавлю к сказанному makc. На каждый вызов malloc() вы получаете участок памяти который обязаны вернуть в кучу. В первом случае у вас один вызов malloc() и один раз вы возвращаете память. Все нормально. Во втором случае вы делаете два вызова, получаете два участка и должны их оба вернуть. Если бы вы получили одинаковые значения указателя вы бы делая free() дважды вернули бы одну и ту же область. Зарезервированные 2 байта (скорее всего = размеру указателя) позволяют корректно отработать возврат в кучу.

P.S. пока отвлекся на телефон - уже ответили...

[zltigo]

Зарезервированные 2 байта (скорее всего = размеру указателя) позволяют корректно отработать возврат в кучу.

Так называемый Memory Control Block. Правда два байта это очень страно, ибо кроме указателя еще размер
как минимум размер должен быть. Это в самом примитивнейшем менеджере Heap c одним списком свободных и занятыми блоками болтающимися сами по себе. Дальше улучшения - занятые тоже в список.
дальше наченаем бороться с фрагментацией - самый простой и надежный вариант - все блоки в один список в порядке возрастания адреса, но к указателю на следующий и размеру у MCB добавляется маркер занят/свободен. Для ускорения поиска естественным образом добавляется указатель на предыдущий блок. В общем случае приличный менеджер имеет в MCB два указателя + размер +
флаг занятости. Для полного счастья для отладочных целей в системе - адрес Task Control Block задачи которая его запросила и признак типа блока (стек, очередь......). На невосьмибитовых архитектурах размер MCB по правильному - выравнивается как минимум до разрядности контроллера.

[SasaVitebsk]

В общем-то спасибо за теорию. Познавательно. 2 zltigo всё это я себе примерно так и представлял по "приличному менеджеру", но давайте попытаемся вернуться на землю и уйти от теории. Дефрагментация даже в Delfi не реализована. Если честно, то я как-то не думал, что данные по работе с кучей находятся в ней самой, хотя теперь мне это кажется вполне разумным.

И всё же "ближе к телу", как говорил Мо Пасан. Начинаю Вам всем возражать. Разбейте меня в пух и прах. Я на веру ничего не принимаю. И если у меня в голове не укладывается, то пока не уложится.

(говорим о IAR for AVR)

1) По функции free я должен явно указать адрес начиная с которого освобождается куча.
То есть я могу выделить 10 +10 +10 байт, а потом освободить 15 к примеру. Я понимаю, конечно, Вас когда я выделяю память под переменную и потом освобождаю. Но здесь я не могу себе такого позволить.
Допустим есть у меня три массива A,B,C и я выделяю последовательно под них место. Так вот я потом не могу освободить место из под B! Только сразу B и C! Так зачем эти пляски с бубном? При таком построении кучи необходимо только контролировать свободное место и всё! Приведите мне пример зачем необходимо хранить этот адрес в куче.

2) Ещё информация к размышлению.
На самом деле я забираю участок памяти не два раза! Переменная OW_Rom_Device указывает мне адрес с какого память выделяется а потом освобождается, а переменная CurrentAddr - это текущий адрес по которому размещается данные датчика. И память там выделяется столько раз сколько датчиков. И идут данные неразрывно. Это можно видеть по формуле вычисления адреса текущего датчика.
for(addr=OW_Rom_Device+numb_dev*7;addr<OW_Rom_Device+numb_dev*7+7;addr++)

Причина правда может быть связана со способом выделения памяти

CurrentAddr +=7; // Ñëåäóþùèé àäðåñ
malloc(7); // Çàðåçåðâèðîâàòü ïàìÿòü ïîä ROM


Но всё равно. Непонятно зачем компилятор указывает в куче этот адрес. Как он потом его использует.

[zltigo]

Дефрагментация даже в Delfi не реализована.

Даже ну просто аРГУМЕНТ
Дефрагментации может или не быть вообще или быть хоть начального уровня - как минимум склейка
освободившихся блоков, оптимальные алгоритммы поиска выделяемого блока в уже фрагментированной памяти, менеджер памяти второго уровня для работы с блоками памяти фиксированного размера....

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

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

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

Это Ваши проблемы. Но все Ваши фантазии НИКАКОГО отношения к поведению даже минимальных реализаций malloc() realloc() free() не имеют.

[Сергей Борщ]

(говорим о IAR for AVR)
1) По функции free я должен явно указать адрес начиная с которого освобождается куча.
То есть я могу выделить 10 +10 +10 байт, а потом освободить 15 к примеру

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

Допустим есть у меня три массива A,B,C и я выделяю последовательно под них место. Так вот я потом не могу освободить место из под B! Только сразу B и C! Так зачем эти пляски с бубном?

Как это?

Код

  mytype *A = malloc(sizeof(mytype) * ELEMENTS_A);
  mytype *B = malloc(sizeof(mytype) * ELEMENTS_B);
  mytype *C = malloc(sizeof(mytype) * ELEMENTS_C);
  .....
  free(B);

2) Ещё информация к размышлению.
На самом деле я забираю участок памяти не два раза! Переменная OW_Rom_Device указывает мне адрес с какого память выделяется а потом освобождается, а переменная CurrentAddr - это текущий адрес по которому размещается данные датчика. И память там выделяется столько раз сколько датчиков. И идут данные неразрывно. Это можно видеть по формуле вычисления адреса текущего датчика.

Боюсь что то, что вы хотели сделать и то, что у вас получилось это несколько разные вещи. Никто не гарантирует, что последовательные вызовы malloc() дадут вам смежные блоки памяти. Поэтому в случаях, подобных вашему организуется не массив, а список из выделенных блоков. Это требует некоторых расходов и памяти на хранение указателей и процессорного времени на перемещение по списку, но, увы, это плата за удобство выделения памяти именно тогда, когда она нужна. Массивы, конечно, быстрее, но нужно заранее знать размер.

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

[zltigo]

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

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

[SasaVitebsk]

Перечитал ещё раз free и теперь всё уложилось в голове.

Всё то, о чём Вы писали, для меня было понятно. Просто я решил, что конкретная реализация для AVR в используемом компиляторе - упрощена. На эту мысль меня подтолкнула функция free (точнее даже то, что её аргументом является указатель). Прочитал невнимательно, и ошибочно решил, что указатель указывает на адрес, начиная с какого нужно память освободить. Ну а воображение вмиг дорисовало всё остальное. Раз так, то всё просто. По malloc забираю по free освобождаю. А данные идут одним куском.
Кроме того, в принципе всё согласовалось. Такой способ возможен и в паскале к примеру (getmem/freemem). Я для приличия поискал другой способ освобождения памяти, но для Си - ненашёл. Ну и успокоился, отнеся данный недостаток на Embedded системы. В общем то решил, что при необходимости пишется свой диспетчер кучи и там - делай что хочешь. Или что хочет zltigo к примеру.

Теперь трохи понятно как поступил компилятор.

1) Оператор

Код

OW_Rom_Device=CurrentAddr=malloc(8);

он разложил на два. Первый выделение под объект под указателем CurrentAddr 8 байт (и пометил его указателем в куче хотя я его не увидел так как он был в самой вершине). А вторым оператором просто присвоил значение указателя CurrentAddr указателю OW_Rom_Device. Таким образом разрыва не было, так как не было двух malloc.
2) Поскольку я вызывал функцию malloc без присваивания, то, соответственно нет объекта по которому может осуществляться free, и компилятор (какой умный) продолжил выделение памяти сплошным куском. Ну а я оставался в блаженном неведении своего невежества.

Теперь я понимаю и разделяю возмущение zltigo "почему только два байта". Надо же как-то пометить конец данных. Я бы действительно указал размер зарезервированной области. А то, возвращаясь к примеру с A,B,C, - если я после освобождения B попытаюсь опять зарезервировать область памяти и она вполне влезет в "дырку", то как компилятор это чухнет. Или он при удалении весь блок сдвинет? Надо будет попробовать, как по свободнее буду.

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

[zltigo]

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

А ему какое дело где ему память выделят?

Или он при удалении весь блок сдвинет? Надо будет попробовать, как по свободнее буду.

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

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

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

при необходимости пишется свой диспетчер кучи и там - делай что хочешь. Или что хочет zltigo к примеру.

Я в любом случае обеспечиваю полную совместимость с malloc() realloc() free() и за счет знания внутренней структуры имею дополнительные ранее упомянутые функциональные возможности
не зависящие от библиотек какого либо компилятора.

[SasaVitebsk]

Или он при удалении весь блок сдвинет? Надо будет попробовать, как по свободнее буду.

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

Да, всё таки иногда надо думать. Придётся с этим смириться.

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

А ему какое дело где ему память выделят?

Вот тут я не понял. (Опять не укладывается ).

Итак давайте сначала.

Резервируем три области по 10б к примеру. A,B,C.
Компилятор в куче на каждую размещает один указатель и 10б и уменьшает размер кучи на 36 байт соответственно.

Освобождаю переменную B.
Компилятор
а) может освободить просто 10 байт и сохранить указатель на дырку. Тогда по разнице указателей, он может высчитать размер дыры, что обеспечит нормальное выделение/освобождение памяти. Правда при длительной работе и разноразмерных переменных может возникнуть ситуация с большим количеством дырок и отсутствием - необходимого размера. Так сказать проблема OS CP/M, решаемая только дефрагментацией кучи по временам, но тут возникают проблемы описанные выше.
б) может освободить все 12 байт памяти, но не увеличивать размер кучи. Я не вижу способа работы таким образом.

Короче у меня тупик.

Если не надоело, то может кто ответит.

[zltigo]

а) может освободить просто 10 байт и сохранить указатель на дырку.

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

[Сергей Борщ]

Если не надоело, то может кто ответит.

У Кнута в первом томе рассматриваются различные варианты менеджеров памяти. Почитайте, многое прояснится. В том числе и по фрагментации.

[SasaVitebsk]

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

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

Может на пенсии. Переписываясь с Вами.