Realloc переразместить блок памяти


Содержание

Функция realloc

Действие функции realloc() в версии С99 немного отличается от ее работы o С89, хотя конечный результат одинаков. В С89 функция realloc() изменяет размер блока ранее выделенной памяти, адресуемой указателем ptr в соответствии с заданным размером size . Значение параметра size может быть больше или меньше, чем перераспределяемая область. Функция realloc() возвращает указатель на блок памяти, по скольку не исключена необходимость перемещения этого блока (например при увеличении размера блока памяти). В этом случае содержимое старого блока (до size байтов) копируется в новый блок.

В версии С99 блок памяти, адресуемый параметром ptr , освобождается, а вместо него выделяется новый блок. Содержимое нового блока совпадает с содержимым исходного (по крайней мере совпадают первые size байтов). Функция возвращает указатель на новый блок. Причем допускается, чтобы новый и старый блоки начинались с одинакового адреса (т.е. указатель, возвращаемый функцией realloc() , может совпадать с указателем, переданным в параметре ptr ).

Если указатель ptr нулевой, функция realloc() просто выделяет size байтов памяти и возвращает указатель на эту память. Если значение параметра size равно нулю, память, адресуемая параметром ptr , освобождается.

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

Пример

Эта программа сначала выделяет блок памяти для 17 символов, копирует в них строку «Это — 17 символов», а затем использует realloc() для увеличения размера блока до 18 символов, чтобы разместить в конце точку.

Динамическое выделение памяти в Си

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

  • выделение памяти под статический массив, содержащий максимально возможное число элементов, однако в этом случае память расходуется не рационально;
  • динамическое выделение памяти для хранение массива данных.

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

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

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

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

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

Функции динамического распределения памяти:

Для использования функций динамического распределения памяти необходимо подключение библиотеки :

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

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

Память, динамически выделенная с использованием функций calloc(), malloc() , может быть освобождена с использованием функции

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

Динамическое выделение памяти для одномерных массивов

Форма обращения к элементам массива с помощью указателей имеет следующий вид:

Пример на Си : Организация динамического одномерного массива и ввод его элементов.

Результат выполнения программы:

Динамическое выделение памяти для двумерных массивов

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

index = i*m+j;

где i — номер текущей строки; j — номер текущего столбца.

Рассмотрим матрицу 3×4 (см. рис.)

Индекс выделенного элемента определится как

index = 1*4+2=6

Объем памяти, требуемый для размещения двумерного массива, определится как

n·m·(размер элемента)

Однако поскольку при таком объявлении компилятору явно не указывается количество элементов в строке и столбце двумерного массива, традиционное обращение к элементу путем указания индекса строки и индекса столбца является некорректным:

Правильное обращение к элементу с использованием указателя будет выглядеть как

  • p — указатель на массив,
  • m — количество столбцов,
  • i — индекс строки,
  • j — индекс столбца.

Пример на Си Ввод и вывод значений динамического двумерного массива

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

  • выделить блок оперативной памяти под массив указателей;
  • выделить блоки оперативной памяти под одномерные массивы, представляющие собой строки искомой матрицы;
  • записать адреса строк в массив указателей.

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

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

Результат выполнения программы аналогичен предыдущему случаю.

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

Для размещения в оперативной памяти матрицы со строками разной длины необходимо ввести дополнительный массив m , в котором будут храниться размеры строк.

Пример на Си : Свободный массив

Перераспределение памяти

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

  • Выделить блок памяти размерности n+1 (на 1 больше текущего размера массива)
  • Скопировать все значения, хранящиеся в массиве во вновь выделенную область памяти
  • Освободить память, выделенную ранее для хранения массива
  • Переместить указатель начала массива на начало вновь выделенной области памяти
  • Дополнить массив последним введенным значением

Все перечисленные выше действия (кроме последнего) выполняет функция

  • ptr — указатель на блок ранее выделенной памяти функциями malloc() , calloc() или realloc() для перемещения в новое место. Если этот параметр равен NULL , то выделяется новый блок, и функция возвращает на него указатель.
  • size — новый размер, в байтах, выделяемого блока памяти. Если size = 0 , ранее выделенная память освобождается и функция возвращает нулевой указатель, ptr устанавливается в NULL .

Размер блока памяти, на который ссылается параметр ptr изменяется на size байтов. Блок памяти может уменьшаться или увеличиваться в размере. Содержимое блока памяти сохраняется даже если новый блок имеет меньший размер, чем старый. Но отбрасываются те данные, которые выходят за рамки нового блока. Если новый блок памяти больше старого, то содержимое вновь выделенной памяти будет неопределенным.

Пример на Си Выделить память для ввода массива целых чисел. После ввода каждого значения задавать вопрос о вводе следующего значения.

Как обновить другие указатели, когда realloc перемещает блок памяти?

calloc (4)

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

Ссылка на realloc гласит:

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

Означает ли это, что если я сделаю это:

тогда cptr может стать недействительным, если realloc перемещает блок?

Если да, то сигнализирует ли realloc, что он переместит блок, чтобы я мог что-то сделать, чтобы cptr не стал недействительным?

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

Используйте int new = 10; ptr[new] = something; int new = 10; ptr[new] = something;

Да, cptr становится недействительным, если realloc перемещает блок.

Да, cptr станет недействительным, поскольку realloc перемещает блок! И нет, нет никаких упоминаний о том, что вам нужно сказать, что он перемещает блок памяти. Кстати, ваш код выглядит ненадежно . читайте дальше . пожалуйста, посмотрите мой answer на другой вопрос и очень внимательно прочитайте код о том, как он использует realloc . Общее согласие таково, если вы сделаете это:

Чтобы обойти это, используйте временный указатель и используйте его, как показано ниже:

Редактировать: Спасибо, Secure, за указание на гремлина, который закрался, когда я набирал это ранее.

Как обновить другие указатели, когда realloc перемещает блок памяти?

Ссылка realloc говорит:

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

Означает ли это, что если я это сделаю:

тогда cptr может стать недействительным, если realloc перемещает блок?

Если да, то realloc сигнализирует каким-либо образом, что он будет перемещать блок, так что я могу сделать что-то, чтобы предотвратить cptr стать недействительным?

5 ответов

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

Вместо vo > *newPtr = something;

Использовать int new = 10;
ptr[new] = something;

Да, cptr становится недействительным, если realloc перемещает блок.

Да, cptr станет недействительным, если realloc перемещает блок.

Нет, нет никакого сигнала. Необходимо проверить возвращаемое значение относительно исходного ptr расположения.

Да, cptr станет недействительным, как realloc движется блок! И нет, нет никакого упоминания о сигнале к вам, чтобы сказать, что он движется блок памяти. Кстати, твой код выглядит не очень…читайте дальше… пожалуйста, посмотрите мой ответ на другой вопрос и внимательно прочитайте код о том, как он используется realloc . Общий консенсус, если вы это сделаете:

Илон Маск рекомендует:  Что такое код udm_free_ispell_data

Способ обойти это-использовать временный указатель и использовать его, как показано:

Edit: спасибо Secure за то, что указал на гремлин, который подкрался, когда я печатал это ранее.

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

Безопасно ли перераспределять память, выделенную новой?

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

Из того, что написано Вот , realloc может переместить блок памяти в новое место. Если свободное хранилище и куча — это два разных пространства памяти, значит ли это, что это проблема?

В частности, я хотел бы знать, безопасно ли использовать

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

Решение

Ты можешь только realloc то, что было выделено через malloc (или семья, как calloc ).

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

Это скорее всего но ни в коем случае не гарантируется, что C ++ new и С malloc использовать тот же базовый распределитель, в этом случае realloc может работать на обоих. Но формально это в UB-земле. И на практике это просто излишне рискованно.

C ++ не предлагает функциональность, соответствующую realloc ,

Наиболее близким является автоматическое перераспределение (внутренних буферов) контейнеров, таких как std::vector ,

Контейнеры C ++ страдают от того, что их дизайн исключает использование realloc ,

Вместо представленного кода

Однако, если вам абсолютно необходима общая эффективность realloc и если вы должны принять new для первоначального распределения, тогда единственным выходом для эффективности является использование средств, специфичных для компилятора, знание того, что realloc безопасно с этим компилятором.

В противном случае, если вам абсолютно необходима общая эффективность realloc но не вынужден принимать new тогда вы можете использовать malloc а также realloc , Использование умных указателей позволяет вам получить большую часть безопасности, аналогичную контейнерам C ++.

Другие решения

Единственное, возможно, соответствующее ограничение C ++ добавляет к realloc в том, что С ++ malloc / calloc / realloc не должны быть реализованы с точки зрения ::operator new , И его free не должны быть реализованы с точки зрения ::operator delete (согласно C ++ 14 [c.malloc] p3-4).

Это означает, что гарантия, которую вы ищете, не существует в C ++. Это также означает, однако, что вы можете реализовать ::operator new с точки зрения malloc , И если вы это сделаете, то в теории, ::operator new результат может быть передан realloc ,

На практике вы должны быть обеспокоены тем, что new результат не совпадает ::operator new результат. Компиляторы C ++ могут, например, объединить несколько new выражения для использования одного ::operator new вызов. Это то, что компиляторы уже делали, когда стандарт не разрешал этого, IIRC, и теперь стандарт это позволяет (согласно C ++ 14 [expr.new] p10). Это означает, что даже если вы пойдете по этому пути, у вас все еще нет гарантии, что new указатели на realloc делает что-либо значимое, даже если это больше не неопределенное поведение.

В общем, не делай этого. Если вы используете пользовательские типы с нетривиальная инициализация, в случае перераспределения-освобождения от копирования, деструктор ваших объектов не будет вызван от realloc , Копия конструктор не будет вызван тоже при копировании. Это может привести к неопределенному поведению из-за неправильного использования время жизни объекта (увидеть Стандарт C ++ §3.8 Время жизни объекта, [basic.life]).

1 Время жизни объекта является свойством среды выполнения объекта. Говорят, что объект имеет нетривиальную инициализацию, если он имеет класс или агрегатный тип, и он или один из его членов инициализируются конструктором, отличным от тривиального конструктора по умолчанию. [Примечание: инициализация тривиальным конструктором копирования / перемещения является нетривиальной инициализацией. —Конечная записка]

Время жизни объекта типа T начинается, когда:

— получается хранилище с правильным выравниванием и размером для типа T, и

— если объект имеет нетривиальную инициализацию, его инициализация завершена.

Время жизни объекта типа T заканчивается, когда:

— если T является типом класса с нетривиальным деструктором (12.4), начинается вызов деструктора, или

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

И позже (акцент мой):

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

Итак, вы действительно не хотите использовать объект вне его жизни.

Это небезопасно и не элегантно.

Может быть возможно переопределить new / delete для поддержки перераспределения, но тогда вы можете также рассмотреть возможность использования контейнеров.

Да, если new на самом деле называется malloc в первую очередь (например, это как VC ++ new работает).

Нет иначе. обратите внимание, что как только вы решите перераспределить память (потому что new называется malloc ), ваш код зависит от компилятора и больше не переносится между компиляторами.

(Я знаю, что этот ответ может расстроить многих разработчиков, но я отвечаю, зависит от реальных фактов, а не только от идиоматизма).

Это не безопасно. Сначала указатель, который вы передаете realloc должно быть получено от malloc или же realloc : http://en.cppreference.com/w/cpp/memory/c/realloc .

Во-вторых, результат new int [3] не обязательно должны быть такими же, как результат функции выделения — может быть выделено дополнительное пространство для хранения количества элементов.

(И для более сложных типов, чем int , realloc не будет безопасным, поскольку не вызывает копирования или перемещения конструкторов.)

Вы можете быть в состоянии (не во всех случаях), но вы не должны. Если вам нужно изменить размер таблицы данных, вы должны использовать std::vector вместо.

Подробности о том, как его использовать, перечислены в другом ТАК вопрос .

Есть множество вещей, которые нужно держать, чтобы сделать его безопасным:

  1. Побитовое копирование типа и отказ от источника должны быть безопасными.
  2. Деструктор должен быть тривиальным, иначе вы должны уничтожить элементы, которые хотите освободить.
  3. Либо конструктор тривиален, либо вы должны создавать новые элементы на месте.

Тривиальные типы удовлетворяют вышеуказанным требованиям.

  1. new[] -функция должна передать запрос на malloc без каких-либо изменений, и не делать никакой бухгалтерии на стороне. Вы можете форсировать это, заменив global new [] и delete [] или те, что в соответствующих классах.
  2. Компилятор не должен запрашивать больше памяти, чтобы сохранить количество выделенных элементов или что-либо еще.
    Нет никакого способа заставить это, хотя компилятор не должен сохранять такую ​​информацию, если тип имеет тривиальный деструктор Качество реализации.

Вызовет ли realloc утечку памяти?

Доброго времени суток! Есть код:

Я так понимаю, что утечка будет, если realloc переместит блок при возрастании размера, так ли это?

UPD

Исправил выход за границы массива.

2 ответа 2


В своем коде вы должны рассчитывать на то, что realloc будет всегда перемещать блок, независимо от того, увеличивается ли его размер, уменьшается ли или вообще не меняется. Эти решения принимаются на основе неподконтрольных вам обстоятельств. То, что он может иногда и не переместиться — не более чем редкая и непредсказуемая удача.

Утечка у вас образуется из-за того, что новое значение указателя _dest в наружный код никак не возвращается. Память, выделенная вашим realloc в общем случае становится утечкой всегда. Либо возвращайте новый _dest из функции через возвращаемое значение, либо работайте с ним «по ссылке», т.е. делайте его mry_char** параметром.

(Да, если в результате работы realloc значение указателя _dest не изменилось, то формально возвращать его «не нужно», но ожидать этого в реальном коде — это полная белиберда. В общем случае значение указателя будет меняться.)

Дополнительно, в связи именно c realloc утечка также может возникнуть, если realloc не сможет выделить память вообще. Тогда он вернет null-указатель, но старую память не освободит, т.е. внутри функции доступ к памяти, изначально указываемой _dest , вы потеряете. (Будет ли это полноценной утечкой зависит от того, сохранили ли вы еще какой-то путь доступа к этой памяти. Из вашего кода этого не видно.)

Также, почему памяти выделяется только под dl + sl элементов, если потом делается _dest[dl + sl] = ‘\0’ ? Явный вылет за пределы выделенной памяти.

Как обновить другие указатели, когда realloc перемещает блок памяти?

Ссылка перераспределить говорит:

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

Означает ли это, что если я это сделать:

тогда CPTR может стать недействительным, если перераспределить перемещает блок?

Если да, то каким-либо образом передается сигнал realloc, чтобы он перемещал блок, чтобы я мог что-то сделать, чтобы cptr не стал недействительным?

Создан 31 янв. 10 2010-01-31 15:04:03 zajcev

Это хороший вопрос +1 от меня, поскольку он подчеркивает фундаментальную кривую обучения, включающую realloc . – t0mm13b 31 янв. 10 2010-01-31 15:45:28

5 ответов

Да, cptr станет недействительным, так как realloc перемещает блок! И нет, нет упоминания о том, что вы сигнализируете о том, что он перемещает блок памяти. Кстати, ваш код выглядит iffy . читайте дальше . см. Мой answer на другой вопрос и очень внимательно прочитайте код о том, как он использует realloc . Общее мнение таково, если вы сделаете это:

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

Edit: Благодаря Secure за то, что указал гремлин, который закрался, когда я печатал это раньше.

Создан 31 янв. 10 2010-01-31 15:15:00 t0mm13b

Это не настоящий код — это просто что-то, чтобы показать, что я собираюсь делать. Итак, есть ли способ изменить размер существующего блока памяти, не перемещая его (или сообщить программе, что это невозможно?). Если я вызову realloc, и это удастся, переместив блок, то возможно ли каким-то образом сохранить старые адреса, чтобы я мог «отменить» realloc? – zajcev 31 янв. 10 2010-01-31 15:39:37

Илон Маск рекомендует:  Что такое код mcal_append_event

Нет! Вы не можете этого сделать . это зависит от компилятора/компоновщика/времени выполнения. И нет, вы не можете сохранить старые адреса, так как куча будет фрагментирована по курсу и продолжительности жизни программы. Короче говоря, вы не можете полностью привязать старые адреса, поскольку сама суть указателей основана на динамической адресации . и нет, вы не можете отменить realloc . – t0mm13b 31 янв. 10 2010-01-31 15:43:28

Это самый бесполезный перевод возвращаемого значения malloc I ‘ когда-либо видел. И почему вы возвращаете malloc, но не возвращаете realloc? – Secure 31 янв. 10 2010-01-31 17:35:55

@ Обязательно: извините, что это старое программирование на языке C . и прочно укоренилось в моем мозгу . когда-либо работало со стандартом C 89 в начале 90-х, тогда вы бы знали, о чем я говорю! :)t0mm13b 31 янв. 10 2010-01-31 17:51:46

@Secure: старый malloc возвратил void * следовательно, актерский состав, я просто забыл положить это для realloc .. – t0mm13b 31 янв. 10 2010-01-31 18:13:55

@ tommieb75, я предполагаю, что вы имеете в виду компиляторы pre-ANSI, которые использовали char * для возврата malloc. Иначе ваш второй комментарий не имеет смысла, отбрасывая пустоту * в пустоту * . – Secure 31 янв. 10 2010-01-31 18:31:29

@ Обязательно: не pre-ansi, Ansi C 89 standard . как для вашего комментария — хорошая точка . Будет редактировать это соответственно . – t0mm13b 31 янв. 10 2010-01-31 18:32:45

@ Обязательно: Отредактирован ответ! Надеюсь, это имеет смысл! :) Спасибо за ваш отзыв. :)t0mm13b 31 янв. 10 2010-01-31 18:34:46

Я нашел способ сделать это — его конкретный Linux, но это все, что мне нужно. В linux есть функции mmap и mremap, которые можно использовать для выделения памяти (см. Флаг MAP_ANONYMUS), а затем измените размер, гарантируя, что он не будет перемещен. – zajcev 31 янв. 10 2010-01-31 20:19:57

@zajcev: Я не уверен, что следую за вами, mmap больше подходит для IPC, а не для чего-то еще, он не делает то же самое, что делает C retimeoc runtime, mmap — это функция POSIX, а не функция времени выполнения ANSI C. .. – t0mm13b 31 янв. 10 2010-01-31 20:27:40

mmap можно также использовать для выделения памяти, и mremap попытается перераспределить память на месте и переместить блок только в том случае, если установлен флаг. – zajcev 03 фев. 10 2010-02-03 18:16:17

@zajcev: Мне любопытно, могу ли я увидеть источник этой информации как таковой для меня новый? Спасибо за этот интересный лакомый кусочек . :)t0mm13b 03 фев. 10 2010-02-03 18:54:03

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

Использование int new = 10; ptr[new] = something;

Создан 31 янв. 10 2010-01-31 15:06:15 Mahmoud Al-Qudsi

Да, CPTR становится недействительным, если перераспределить перемещает блок.

Создан 31 янв. 10 2010-01-31 15:07:00 bmargulies

сожалеет о крике, но это помогло получить короткий ответ за минимальное требование длины. – bmargulies 31 янв. 10 2010-01-31 15:07:29

Да, cptr станет недействительным, если realloc перемещает блок.

Нет, сигнала нет. Вам нужно будет проверить возвращаемое значение в исходном местоположении ptr .

Создан 31 янв. 10 2010-01-31 15:07:08 Mitch Wheat

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

Создан 05 окт. 10 2010-10-05 04:06:35 R..

Жаль, что у меня это было до того, как я написал свое текущее задание. Я также думаю, что это часть ответа на ОПЗ Зайцева, объясняя, что он может с этим поделать. – gone 12 апр. 14 2014-04-12 06:59:07

История про realloc (и лень)

Простой макрос

Все началось с простого макроса: (приблизительный код)

Для тех, кто не знаком с языком программирования C, поясню: этот простой макрос добавляет байт «C» в динамически выделяемый буфер (buffer), размер которого (в байтах) равен capa. Следующая позиция для записи определяется при помощи параметра offset. При каждом заполнении буфера происходит двукратное увеличение его объема (начиная с минимального размера в 16 байт).

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

Но как понять, насколько эффективна стратегия перераспределения? Если вы посмотрите на эту проблему с точки зрения сложности, принимая сложность realloc() равной O(N), то сразу поймете, что добавление одного байта имеет сложность в среднем O(1), что вполне неплохо.

Но какова сложность в наихудшем случае — если требуется перераспределение памяти под буфер?

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

Я: Хм… Честно говоря, никогда не задумывался над этим… Но уверен, все не так страшно. Система должна успешно справиться с этой задачей.

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

Я: Да нет, это пустая трата времени.

Ах вот так, значит?!

Ладно, придется обосновать свою позицию. Как и все программисты, я весьма ленив. Точнее: «Как подобает программисту, я весьма ленив». Лень — отличный стимул стать умнее и эффективнее. Вы слишком ленивы для того, чтобы решать повторяющиеся или рутинные задачи; вам нужно что-то более интеллектуальное, что-то максимально быстрое. Да, именно это иногда называют ленью. Но, по-моему, это не что иное, как эффективность.

Связанный список блоков для хранения буфера — несколько громоздкое решение. Я не говорю, что это невозможно. «Невозможно — не французское слово», — говаривал Наполеон (правда, кончил он плохо). Решение возможно, но оно громоздкое. Копирование подмассива или сохранение его на диск потребует некоторых усилий. Нам, вероятно, пришлось бы поддерживать индекс указателей на начало каждого массива, брать логарифм по основанию два, чтобы получить адрес начала блока и еще много всякой нудятины… Ух, я уже устал…

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

Кстати, что такое realloc()?

Это обычная функция, соответствующая стандарту POSIX, которая реализована в библиотеке C. В случае с Linux это библиотека libc.so, в ней же находятся и родственные realloc функции malloc и free:

Для тех, кому это действительно интересно: «T» означает «text symbol» (текстовый символ), заглавная буква используется, чтобы показать, что символ этот общедоступный и видимый; текстовый сегмент программы — это код, сегмент данных — инициализированные данные (переменные), а сегмент bss — неинициализированные данные (переменные), а точнее данные (переменные), получившие в качестве начального значения ноль).

Для выделения, перераспределения и освобождения памяти используется распределитель памяти (спасибо, Капитан Очевидность!). Таких распределителей много (самый известный — buddy allocator).

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

[Примечание. Как справедливо заметил один из читателей Hacker News, здесь нужно значение old_size, которое, например, можно было записать в начало блока после того, как блок был выделен. Но нет, мы не должны были освободить исходный блок в случае ошибок в работе realloc :)]

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

Чтобы понять, что происходит с большими блоками, нам придется поближе познакомиться с Glibc на Linux.

Знакомство с Glibc

Просто скачайте последнюю версию glibc и изучите дерево исходного кода.
Там есть один интересный каталог malloc. Найдите в нем файл malloc.c и откройте его в редакторе.

Нас больше всего интересует вот эта часть: «Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются».

Порог в 128 Кб настраивается функцией mallopt():

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

В сущности, это означает, что:

  • malloc будет реализована с использованием mmap;
  • free будет реализована с использованием munmap;
  • realloc будет реализована с использованием mremap (Что?! Такого в POSIX еще нет? Серьезно?)

Ладно, давайте чуть-чуть расширим свои познания о mremap.

Итак, что мы знаем о man mremap:

Ага, очень эффективный realloc. Насколько эффективный?

Во-первых, mmap, munmap и mremap описаны в библиотеке glibc. На самом деле, только точки входа:

Обратите внимание на то, что точки входа по умолчанию — это в данном случае «слабые» символы. То есть они могут быть переопределены кем-то другим во время динамической компоновки. Например:

… символы могут быть переопределены библиотекой linux-vdso.so.1 — это волшебная библиотека, которая отображается во всех программах под Linux и позволяет ускорить некоторые вызовы, включая системные вызовы.
В любом случае наши символы в библиотеке glibc — это только каналы к вызовам ядра системы (syscall), будь то glibc или vdso (см. реализации по умолчанию: sysdeps/unix/sysv/linux/mmap64.c). Например:

Итак, наш первоначальный вопрос уже связан не с glibc, а с ядром Linux.

Знакомство с ядром

Скачайте последнюю версию ядра, и давайте кратко рассмотрим принципы работы mremap.

Заглянув в руководство (The Linux Kernel Howto), вы найдете очень интересный каталог:

Каталог mm содержит весь необходимый код для работы с памятью. Код управления памятью, специфичный для конкретной архитектуры, размещается в каталогах вида arch/*/mm/, например arch/i386/mm/fault.c.

Отлично. Они-то нам и нужны!
Вот интересный файл: mm/mremap.c. В нем вы найдете точку входа для системного вызова функции mremap. Вот здесь:

Именно здесь мы входим в ядро при выполнении соответствующего системного вызова в пользовательском коде (через glibc или соответствующий канал vdso).

Илон Маск рекомендует:  Что такое код muscat_setup

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

Затем ядро попытается расширить отображенную область путем ее увеличения (то же самое делал бы распределитель в библиотеке C при помощи sbrk). В случае успешного расширения функция возвращает результат.

Все эти тривиальные случаи реализованы со сложностью O(1) (даже если учитывать затраты на вход в ядро — они будут меньше, поскольку прерывания больше не используются, но все равно будут).

А что в наихудшем случае?

На первый взгляд, ядро делает то же самое, что делаем мы в своем простом распределителе:

  • выделяет новую область;
  • копирует исходную область в новую, а затем освобождает ее (т. е. выполняется операция перемещения).

Но давайте посмотрим повнимательнее.

Вот вызов move_vma:

Здесь есть два интересных вызова:

  • copy_vma;
  • move_page_tables.

Функция copy_vma описана в файле mm/mmap.c; она перемещает структуру типа vm_area_struct — это внутренняя структура ядра, описывающая блок памяти.

Определение можно найти здесь: include/linux/mm_types.h. Эта небольшая структура содержит всю информацию об области: начальный и конечный адрес, файл на диске (если область памяти используется для отображения файла) и т. д.

Итак, эта операция перемещения достаточно проста — O(1).

А что делает функция move_page_tables?

Самое интересное, похоже, вот в этом цикле:

Этот код несколько сложноват (кроме того, нет комментариев), но в основном это базовые арифметические операции и расчеты.

Функция move_ptes содержит внутренний цикл самого нижнего уровня:

Так что же в этом цикле происходит?! Мы просто перемещаем строки таблицы страниц (PTE, Page Table Entries), соответствующие области памяти, в другое место. По сути, это целые числа, назначенные каждой странице.

Итак, что мы имеем: фактически ядро не притрагивалось к данным из нашего сопоставленного блока; для перемещения всей области достаточно было поменять местами несколько битов.
Формально сложность по-прежнему O(N), но

  • вместо копирования целых страниц по 4 Кб (или 2 Мб для очень больших страниц), мы меняем местами целые числа внутри структуры ядра;
  • мы работаем с «горячей» памятью ядра, не притрагиваясь к «холодной» и тем более к данным, вытолкнутым в файл подкачки.

Поэтому мы используем O(N), но с огромным отличием.

Да, кстати, вы знаете, что O(N) во многих случаях сбивает с толку?

В нашем случае максимальным значением N является 2 48 (максимальный размер виртуального пространства). Большинство компьютеров работают лишь с несколькими гигабайтами памяти — не более 64 Гб для большинства архитектур (то есть 2 36 байт). Большая станица — это 2 21 байт, максимальное число операций составляет 2 15 для move_ptes (да, это всего лишь 32 768 операций).

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

Также рекомендую к прочтению: книгу Understanding the Linux Virtual Memory Manager Мела Гормана (Mel Gorman).

«Ниасилил многабукаф»? Не парьтесь. Лень и realloc — наше все.

Как обновить другие указатели, когда realloc перемещает блок памяти?

Ссылка на realloc гласит:

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

Означает ли это, что если я сделаю это:

тогда cptr может стать недействительным, если realloc перемещает блок?

Если да, то сигнализирует ли realloc, что он переместит блок, чтобы я мог что-то сделать, чтобы cptr не стал недействительным?

5 ответов

Да, cptr станет недействительным, поскольку realloc перемещает блок! И нет, нет никаких упоминаний о том, что вам нужно сказать, что он перемещает блок памяти. Кстати, ваш код выглядит ненадежно. читайте дальше. пожалуйста, посмотрите мой ответ на другой вопрос и внимательно прочитайте код о том, как он используется realloc , Общее согласие таково, если вы сделаете это:

Чтобы обойти это, используйте временный указатель и используйте его, как показано ниже:

Редактировать: Спасибо, Secure, за указание на гремлина, который закрался, когда я набирал это ранее.

Realloc переразместить блок памяти

В этом уроке научимся работать с динамической памятью микроконтроллера. Прежде всего нужно ознакомиться с распределением памяти и понять, как оно работает и что мы вообще будем делать. Перед вами схема распределения памяти в МК от AVR, которые стоят на Arduino:

Память – это по сути большой массив, каждая ячейка которого имеет свой адрес, адрес растёт слева направо (по картинке выше). Первым идёт Flash, она же программная память, память, в которой хранится сам код. Во время работы программы этот код не меняется (есть способы сделать это, но это не относится к теме урока). Сегодня нас интересует динамическая память, SRAM, которая на схеме представлена совокупностью синей, зелёной, розовой и оранжевой областей, а также белой областью со стрелочками между розовой и оранжевой. Рассмотрим подробнее:

  • Globals (синий и зелёный) – в этой области живут глобальные и статические переменные. размер этой области известен на момент запуска программы и не меняется в процессе её выполнения, т.к. глобальные и статические переменные объявлены, их размер и количество известны.
  • Heap (розовый), она же куча – из этой области мы можем выделить память под свои нужды. Размер этой области может меняться во время выполнения программы, куча “растёт” в сторону увеличения адресов, слева направо, что показано стрелкой на схеме. В этой области мы можем самостоятельно выделять память под свои нужды и освобождать её, опять же самостоятельно. Важно: процессор не даст вам выделить область, если свободной памяти под неё недостаточно, т.е. наползание кучи на стек очень маловероятно.
  • Stack, он же стек – в этой области живут локальные переменные и параметры, которые передаются функциям (формальные переменные). Размер этой области меняется во время выполнения программы, стек растёт от конца области памяти в сторону уменьшения адресов, навстречу куче (см. стрелку на схеме). Переменные, которые тут живут, называются автоматическими: программа сама выделяет память (при создании локальной переменной при входе в функцию), и сама эту память освобождает (локальная переменная удаляется при выходе из функции). Важно: процессор не контролирует размер стека, то есть во время работы стек может врезаться в кучу и перезаписать находящиеся там данные. Если вы эти данные туда помещали.
  • Available – доступная, свободная память. Как только она заканчивается, т.е. сталкиваются куча и стек – программа с большой долей вероятности зависает. Если стек самостоятельно контролирует свой размер, то с динамической памятью нужно быть аккуратнее: не забывать освобождать её, если она больше не нужна.

Выделение памяти

Для выделения и освобождения динамической памяти “из кучи” у нас есть две функции: malloc() и free() соответственно. Также есть операторы new и delete , которые делают то же самое. При выделении памяти мы получаем адрес на первый байт выделенной области, поэтому рекомендую почитать урок про адреса и указатели.

  • malloc(количество) – выделяет количество байт динамической памяти (из кучи) и возвращает адрес на первый байт выделенной области. Если свободной памяти недостаточно для выделения – возвращает “нулевой указатель” – NULL .
  • free(ptr) – освобождает память, на которую указывает ptr, назад в кучу. Адрес мы получаем в результате работы malloc() при выделении. Освободить можно только память, выделенную при помощи функций malloc(), realloc() или calloc(). В выделяемой области хранится размер этой области (+2 байта), и при освобождении функция free знает, какой размер освобождать.
  • new и delete – технически то же самое, разница в применении (см. пример ниже)

Рассмотрим пример с выделением и освобождением памяти при помощи malloc/free и new/delete. Примеры абсолютно одинаковые с точки зрения происходящего, отличаются только функциями:

malloc/free

new/delete

Таким образом мы выделили себе память, с этой памятью можем взаимодействовать (как с обычной переменной), и потом её освободить. Напомню, что освобождать крайне желательно в обратном порядке, чтобы память освобождалась последовательно, не оставляя дыр.

Есть ещё две функции: calloc и realloc :

  • calloc(количество, размер) – выделяет память под количество элементов с размером размер каждый (в байтах). Тот же malloc, но чуть удобнее использовать: в примере выше мы умножали, чтобы получить нужное количество байт для хранения int malloc(20 * sizeof(int)) , а можно было вызвать calloc(20, sizeof(int)); – заменив знак умножения на запятую =)
  • realloc(ptr, размер) – изменяет величину выделенной памяти, на которую указывает ptr, на новую величину, задаваемую параметром размер. Величина размер задается в байтах и может быть больше или меньше оригинала. Возвращается указатель на блок памяти, поскольку может возникнуть необходимость переместить блок при возрастании его размера. В таком случае содержимое старого блока копируется в новый блок и информация не теряется.

Пакетное управление памятью

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

  • memset(ptr, значение, количество) – заполняет область памяти, на которую указывает ptr, байтами значение, в количестве количество штук. Часто используется для задания начальных значений выделенной области памяти. Внимание! Заполняем только байтами, 0-255.
  • memcpy(ptr1, ptr2, количество) – переписывает байты из области ptr2 в ptr1 в количестве количество. Грубо говоря переписывает один массив в другой. Внимание! Работает с байтами!

Зачем?

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

Также есть такой момент: среда Arduino IDE может примерно прикинуть размер занимаемой SRAM памяти на этапе компиляции, глобальные переменные она увидит, а вот создаваемые в процессе работы массивы – нет, и предсказать “а сколько там осталось” – сложно. С динамической памятью нужно работать аккуратно, не забывать её очищать и помнить о фрагментации. Динамическая память удобна в тех случаях, когда нужно поместить какой-то объём данных в буфер, который обладает большой областью видимости, в отличие от локальной переменной. С этим буфером можно взаимодействовать из разных уголков программы (передавая его адрес), а потом освободить память. А так, работа с динамической памятью вам скорее всего не пригодится, но помнить о таком инструменте полезно.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL