Пользователь
0,0
рейтинг
12 ноября 2012 в 21:03

Разработка → Как malloc память ест

C++*, C*
Нет, здесь не будет ничего из серии «Аааа, я сделал malloc (new), и забыл сделать free (delete)!»
Здесь будет нечто изощренное: мы будем отрезать кусочки памяти по чуть-чуть, прятать их в укромное место… А когда операционная система заплатит выкуп скажет «Хватит!», мы попробуем вернуть все обратно. Казалось бы, простейшая операция выделения и освобождения памяти — ничего не предвещает беды.
Тем кому интересно как уничтожить забить память — прошу под хабракат


Немножко предыстории


По долгу службы приходится много работать с большими буфферами памяти (представьте себе изображение 5000x40000 пиксел). Порой (из-за фрагментации) не получается выделять непрерывный кусок памяти для всего. Поэтому был написан некоторый менеджер памяти, который выделял сколько есть, возможно, несколькими кусками. Естественно, менеджер памяти должен как выделять, так и удалять. Тогда была обнаружена следующая интересная вещь: Task Manager после освобождения показывает уровень использования памяти такой же как и до выделения блока. Однако никакой новый блок памяти в программе не может быть выделен. Использование средств анализа виртуальной памяти (VMMap от Марка Русиновича) показывает, что память остается занята несмотря на ее освобождение в коде и несмотря на показания TM.

Анализ


Напишем быстренько какую-нибудь программку, которая выделяет и освобождает память. Что нибудь такое, сродни «Hello, World!»:
int main(void)
{
  const int blockCount = 1024;
  const int blockSize = 1024*1024;
  char **buf;
  printf("Hit something...\n");
  getchar();
  buf = (char**)malloc(blockCount*sizeof(char*));
  for (int i=0; i<blockCount; i++)
  {
    buf[i] = (char*)malloc(blockSize*sizeof(char));
  }
  printf("Memory allocated\n");
  printf("Hit something...\n");
  getchar();
  for (int i=0; i<blockCount; i++)
  {
    free(buf[i]);
  }
  free(buf);
  printf("Hit something...\n");
  printf("Memory freed\n");
  getchar();
  return 0;
}

Несложными подсчетами можно убедиться, что программа должна выделить 1 ГБ памяти, а затем все освободить. После запуска и проверки вся память освобождается. Хм, кажется, система шантажу не поддается. Впрочем, мы резали большие куски.

Теперь возьмем и немножко поправим исходный код:
const int blockSize = 520133 //К примеру...;

В этом случае мы получим, что память выделилась, но не освободилась:
До «Memory freed»:

После «Memory freed»:


Пытливый ум программиста не остановился на достигнутом! Я начал искать пороговое значение, при котором возникает такой эффект. После недолгого бинарного подбора выяснилось, что при размере равном
  • 520168 байт и выше — освобождение проходит нормально
  • 520167 байт и ниже — имеем описанную проблему

Забегая вперед скажу, что никаким образом подобное значение порога я объяснить не смог. Оно не делится даже на 1024!

Возможное объяснение


После длительных бдений за гуглом и изучения форумов я пришел к следующим выводам.
Оказывается что после выделения памяти с помощью функций malloc/new в том случае если выделяется маленький кусок, то память не освобождается функциями free/delete, а переходит из разряда committed в разряд reserved. И если мы обращаемся к данной памяти тут же после удаления (по всей видимости в рамках одного хипа), то она может быть выделена повторно. Однако при попытке выделить память из другого класса (либо статической функции) мы получим исключение — не достаточно памяти. По всей видимости при выделении памяти из статической функции память выделяется не в том же хипе, что и при обычном выделении изнутри класса приложения.
В результате после создания большого блока памяти (из маленьких кусочков) мы исчерпываем память и не можем в дальнейшем выделить себе еще немножко ну хоть чуть-чуть! памяти.

Неправильное решение


Использование функций VirtualAlloc/VirtualFree (MSDN) решает данную проблему, память полностью возвращается процессу после использования (ключ MEM_RELEASE), однако при использовании VirtualAlloc происходит сильная фрагментация памяти, и где-то 800Мб памяти не доступно для использования, т.к. максимальный размер свободного блока — 28Кб. Классический malloc в этом плане работает лучше, т.к. там есть некоторый дефрагментатор.

Окончательное решение


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

Ремарки


Под ОС *NIX (Ubuntu, Debian, CentOS) повторить проблему не удалось)
Под ОС Windows проблема была воспроизведена на Windows Server 2003 x64, Windows 7 x64, Windows XP x32.
Не стоит прямо так сразу доверять давно проверенным функциям, в них может крыться подвох.

UPD: Для компиляции на Windows используется MS VS 2010
Андрей @serenheit
карма
20,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (48)

  • +14
    > 520168 байт и выше — освобождение проходит нормально

    Вы бы сначала почитали как работают аллокаторы памяти прежде чем писать «разгромную» статью. Это же классическое поведение аллокатора: маленькие объекты выделяются в общей куче, а за большими — обращаемся к системному аллокатору.
    • +4
      Но это не повод так глючить. Ведь выделение маленькими блоками типично для классических (учебных) алгоритмов на списках, графах и т.п.
      • –5
        А то, что не производится нормальная дефрагментация кучи — это конечно же баг.

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

        Также интересно что автор имел ввиду. Или его компилятор действительно вызывает разные malloc() в этих случаях (в чём я сомневаюсь), или написанное не соответствует наблюдениям.
  • +6
    Вообще практически все стандартные реализации malloc/free не возвращают память операционке, а придерживают ее для «своего» процесса. Таким образом овобожденная память в таск менеджере не видна, но достпупна для malloc'a.

    Учите матчасть вобщем.

    >>Однако при попытке выделить память из другого класса (либо статической функции) мы получим исключение
    Бред, такого быть не может, т.к. не может быть никогда. Память либо доступна в рамках всего процесса, либо нет, точка.
    • +3
      > Бред, такого быть не может, т.к. не может быть никогда.

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

      > Память либо доступна в рамках всего процесса, либо нет, точка.

      Вообще-то есть thread-aware аллокаторы.
    • +3
      А вот в Стандартной библиотеке C++, к примеру, можно хоть каждый std::vector создавать со своим собственным аллокатором.

      Я к тому, что в программе вполне могут уживаться вместе несколько разных аллокаторов, иногда — даже незаметно для программиста.
    • 0
      Как раз в Task Manager она видна как освобожденная.
    • +1
      >> Бред, такого быть не может, т.к. не может быть никогда. Память либо доступна в рамках всего процесса, либо нет, точка.
      А если выделить пытались из другой арены? Тогда всё сходится, система процессу памяти больше не даёт, свободных мест в нужной арене нету, а из других арен по какой-то причине не получается взять свободный кусок.
  • +7
    Эм, рекомендую обратиться к функции _heapmin(). Эта функция соответственно зовет HeapCompact(), которая освобождает в систему пустые страницы из хипа. Обратите внимание — не все выделенное, а только те страницы, которые не содержат выделенных кусочков.

    Как подсказывает мне мой склероз, это известная шутка микрософтовских программистов под названием «память в системе бесконечна», и существует она с начала времен. В NT 3.5 уже было именно такое поведение, емнип.
    • 0
      Которая, к сожалению, не обеспечивает красивого кросс-платформенного кода.
      Хотя VirtualAlloc ее тоже не обеспечивает…
      • +1
        Хех, если б это было единственной проблемой. А так даже время получить — и то задача для #ifdef. Ну вот к примеру

        #include "timeval.h"
        
        #ifndef HAVE_GETTIMEOFDAY
        #ifdef WIN32
        #include <mmsystem.h>
        static int gettimeofday(struct timeval *tp, void *nothing)
        {
        #ifdef WITHOUT_MM_LIB
          SYSTEMTIME st;
          time_t tt;
          struct tm tmtm;
          /* mktime converts local to UTC */
          GetLocalTime (&st);
          tmtm.tm_sec = st.wSecond;
        ...
          tmtm.tm_year = st.wYear - 1900;
          tmtm.tm_isdst = -1;
          tt = mktime (&tmtm);
          tp->tv_sec = tt;
          tp->tv_usec = st.wMilliseconds * 1000;
        #else
          /** Time calculations using GetLocalTime had a time resolution of 10ms.The timeGetTime, part
           ** of multimedia apis offer a better time resolution of 1ms.Need to link against winmm.lib **/
          unsigned long Ticks = 0;
          unsigned long Sec =0;
          unsigned long Usec = 0;
          Ticks = timeGetTime();
        
          Sec = Ticks/1000;
          Usec = (Ticks - (Sec*1000))*1000;
          tp->tv_sec = Sec;
          tp->tv_usec = Usec;
        #endif /* WITHOUT_MM_LIB */
          (void)nothing;
          return 0;
        }
        #else /* WIN32 */
        /* non-win32 version of Curl_gettimeofday() */
        static int gettimeofday(struct timeval *tp, void *nothing)
        {
          (void)nothing; /* we don't support specific time-zones */
          tp->tv_sec = (long)time(NULL);
          tp->tv_usec = 0;
          return 0;
        }
        #endif /* WIN32 */
        #endif /* HAVE_GETTIMEOFDAY */
        
        


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

          LARGE_INTEGER li;
          FILETIME ft;
        
          GetSystemTimeAsFileTime(&ft);
          li.HighPart = ft.dwHighDateTime;
          li.LowPart = ft.dwLowDateTime;
          tp->tv_sec = (long)(li.QuadPart / 10000000LL); // 10^7 as in 100ns units
          tp->tv_usec = (long)((li.QuadPart % 10000000LL) / 10);
        


        Это Curl.
        • 0
          Знакомые строки…
          Но хотелось всегда красивого.

          В итоге обычно все обрамляется #ifdef, а потом вся некрасивость прячется :-)
  • 0
    Ну, насколько я понимаю, в линуксах с управлением памятью сильно проще: brk(), да юзай. malloc всего лишь надстройка над этим.
    • +2
      … только все используют mmap().
      • 0
        А в чём профит использоания mmap с MAP_ANONYMOUS? (я так понял, речь про него). Всё равно же адресное пространство выделять надо (т.е. brk двигать).
        • 0
          Нет никакого brk. Есть замапленые и незамапленые страницы. А преимущество например, в том, что с mmap() может быть несколько аллокаторов, а с sbrk() только один.
          • +1
            Ничего не понимаю. Что такое «замапленные страницы»? Давайте для начала определимся, мы про файлы, или про анонимный мапинг?

            Полагаю, что таки анонимный.

            При вызове анонимного мапинга нужно передать свой указатель на доступный виртуальный адрес. Чтобы адрес стал доступным, надо его разрешить — то есть поднять break point.

            Насчёт sbrk — с ним могут работать несколько аллокаторов сразу, правда, dallocate при этом не получится, да.
            • +2
              > Ничего не понимаю. Что такое «замапленные страницы»? Давайте для начала определимся, мы про файлы, или про анонимный мапинг?

              Нет принципиальной разницы. В файловом маппинге backing store — файл, в анонимном — swap.

              Есть страницы замапленные (cat /proc/self/maps) и незамапленные, обращение к которым ведёт к segfault.

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

              И передача этого адреса является только советом для mmap() и ничего не гарантирует. Этот адрес может быть не замаплен, но, например, ОС решила запретить его мапить (например, нулевой адрес — см. sysctl vm.mmap_min_addr) или процессор может не поддерживать его мапить (http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details).

              > Чтобы адрес стал доступным, надо его разрешить — то есть поднять break point.

              Нет единственного break point. Посмотрите /proc/self/maps у чего-нибудь посложнее, чем ls (например firefox). Страницы данных мапятся вплоть до гранулярности в 1 страницу.

              > Насчёт sbrk — с ним могут работать несколько аллокаторов сразу, правда, dallocate при этом не получится, да.

              Только если нет TOCTOU гонки между проверкой текущего break и установкой нового.
              • 0
                Ок, возможно, я что-то не понимаю.

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

                У программы есть brk, который двигает end_data_segment. В пределах этой памяти приложение может писать куда угодно (ну, не считая адресов, отведённых под text).

                Теперь программа хочет сделать mmap. Она передаёт адрес, который больше end_data_segement с этого момента [addr;addr+length] становится доступным (в соотв. с флагами) для приложения?

                Т.е. в сегменте данных образуется дыра? А что тогда sbrk() после очередного mmap()'а «глубоко вверх» вернёт?
                • +2
                  Теперь программа хочет сделать mmap. Она передаёт адрес, который больше end_data_segement с этого момента [addr;addr+length] становится доступным (в соотв. с флагами) для приложения?
                  Адрес — это совет. Какой именно адрес вернёт mmap — это решает система. И он не обязан начинаться сразу за концом «сегмента данных».

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

                  Допустим, располагается она «далеко» от «сегмента данных» — в чём проблема-то?
                • +1
                  > Значит, у нас есть сегмент кода, данных, стека и т.д.

                  Нет. Это в исполняемом файле есть секции кода и данных. Они мапятся в плоское адресное пространство. Плоское (flat) адресное пространство плоское потому что у нас всего один *сегмент*, на который указывают все сегментные регистры (cs, ds, ss). Поэтому для интерпретации адреса не нужно знать из какого он сегмента, потому что сегмент один и тот же.

                  Но кроме исполняемого файла есть, например, библиотеки со своими сегментами. И всё это посегментно мапится в адресное пространство. При этом сегменты кода, естественно, не идут последовательно. И сегменты данных тоже. (см. опять таки /proc/PID/maps)

                  > У программы есть brk, который двигает end_data_segment.

                  Эмм… С точки зрения программиста — да, системный вызов brk что-то там двигает. На практике — он просто мапит/анмапит страницы в конец того что вы называете «сегментом данных».

                  brk [1] вызывает do_brk [2], который в результате создаёт anonymous mapping.

                  [1] lxr.linux.no/#linux+v3.6.6/mm/mmap.c#L246
                  [2] lxr.linux.no/#linux+v3.6.6/mm/mmap.c#L2161
                  • 0
                    Ого, спасибо.
                  • 0
                    > Но кроме исполняемого файла есть, например, библиотеки со своими сегментами. И всё это посегментно мапится в адресное пространство.

                    сегментами -> секциями.
  • +1
    а какая связь между malloc и операционной системой? аллокатор же не в ОС в данном случае, а в libc.
  • +3
    Подобная проблема проявляется при работе node.js под высокими нагрузками. Если процесс нагружается задачами, которые он не успевает выполнять (например запросы приходят быстрее чем процесс успевает отвечать на них), процесс node.js начинает выделять память, RSS и Heap растут параллельно. Когда нагрузка спадает и процесс разруливает оставшиеся задачи, GC очищает heap, а RSS память не освобождается. При следующей подобной нагрузке Heap и RSS опять растут параллельно, но после освобождения Heap (при падении нагрузки) RSS остаётся на занятом уровне и так далее. Многих очень волнует такое поведение node.js. Я создавал баг-репорт относительно этой проблемы с небольшим примером, на котором она воспроизводится.

    Однако Ben Noordhuis написал, что это не баг, а известная стратегия работы malloc и привёл небольшой пример на С++, иллюстрирующий это поведение. Конечно понятно, что ситуация приведённая в моём примере синтетическая и встречаться в хорошо написанных приложениях не должна, но бывает, что она встречается. Это может быть не самый оптимальный код или DDoS атака или просто резкий набор популярности, на который приложение не рассчитано. Так или иначе, это странно, что память после этого не возвращается системе. Когда Heap занимает 80Mb, а RSS — 3Гб появляются вопросы «а нормально ли это?» и «что делать?».

    Было бы здорово, если бы кто-то из хабралюдей, более близкий к C++ смог понятнее разъяснить данное поведение malloc node.js (V8), в частности.
  • +1
    А не проще было бы уже заmmapится на что-то большое и работать там уже себе спокойно?
    • +2
      Это большое самому пилить на кусочки разных размеров?
      • +1
        Пространства памяти?
  • 0
    При работе с большим количеством объектов всегда возникают ситуации, когда стандартные библиотечные решения «в лоб» не работают или работают неудовлетворительно. Например, как-то я сканировал дерево каталогов диска и хранил в памяти имена всех файлов. На большом диске львиную долю времени стали занимать операции создания и уничтожения std::string; кроме того, стало не хватать памяти. Пришлось делать собственную реализацию контейнера строк большого размера, который работал, выделяя куски памяти размером порядка мегабайта и размещая строки в них. Но все равно, контейнер std::map, в котором хранились просто указатели на все эти строки, создавался и уничтожался несколько минут реального времени. Так что пришлось и этот контейнер переделывать, адаптируя его под решаемую задачу.
    • 0
      У std-шных контейнеров можно указать свой аллокатор
  • –1
    Это «нестандартное поведение» зовется windows memory manager, и описано в документации. Почитайте на досуге — узнаете для себя много интересного… Нормальной работе системы оно не мешает (окромя тормозов, и задержки на garbage при завершении программы), зато позволяет например уменьшить количество access violation, при недобросовестном использовании.
    Довольно часто, для вещей пользующих много памяти маленькими кусками пишется собственный ММ.
    • 0
      Как видно, мне помешала и довольно сильно…
      За наводку спасибо, поизучаю.
    • +1
      зато позволяет например уменьшить количество access violation, при недобросовестном использовании.


      Это не «зато», а «увы».
      За «недобросовестное использование» надо бить по рукам через AV чем раньше, тем лучше.
      И баг быстрее выявится, и потенциальных дыр с чтением чужих освобождённых данных меньше.
      • 0
        Где-то видел что-то вроде блога об истории windows, где было прямо сказано, что подобное поведение в своё время было ещё в Win 95 как раз ради какой-то игры с подобным недобросовестным кодом.
        Т.е. «в теории» можно было педантично исправить, но на практике оказалось бы, что эта игра запускается под DOS но вылетает на Windows. И тогда поведение менеджера памяти сознательно сделали таким — ради совместимости с этой игрой.
        • +3
          Вы плохо помните, работа менеджера менялась ТОЛЬКО для старой игры.
      • –2
        Дак я не сказал, что это есть хорошо… и не в коем случае не оправдываю MS за это.
        Хотя опять же с какой стороны смотреть — в windows очень много стороннего не опенсорсного proprietary — хотите ли вы, чтоб ваша программа, использующая что-то из того, обвалилась в никуда, причем у вас нет возможности заглянуть в источники.
        Второй момент, что многие средства разработки предоставляют механизмы словить такой доступ к памяти на стадии разработки — например VS при дебаге в free забивает освобожденную память определенной дрянью, как раз чтобы проще и быстрее выявить такой доступ к ней познее. Проблема в том, что не все из этой области (seg fault) можно поймать на стадии разработки и/или в дебаге.
        Добавим сюда многопоточность и т.д. и т.п. — тогда я вам уже не скажу, какое из двух зол я бы выбрал в продакшн.
        • 0
          > в windows очень много стороннего не опенсорсного proprietary — хотите ли вы, чтоб ваша программа, использующая что-то из того, обвалилась в никуда

          О, интересно: проприетарностью кода оправдывают «невысокое» качество этого «кода».

          > Второй момент, что многие средства разработки предоставляют механизмы словить такой доступ к памяти на стадии разработки — например VS при дебаге в free забивает освобожденную память определенной дрянью

          Ага, позволяют. Только пример неудачный: забивать память определённым паттерном — это прошлый век. Берите современные инструменты, например, AddressSanitizer.
          • 0
            О, интересно: проприетарностью кода оправдывают «невысокое» качество этого «кода».
            А вот передергивать не надо — где я это написал? — проприетарность кода часто есть невозможность заглянуть в исходники. Остальное ваши домыслы…
            … это прошлый век. Берите современные инструменты, например, AddressSanitizer.
            Вы это мне? Вы там слово например видимо незаметили.
            К слову, (незаметив ваше «например») для сей/сей++ под виндами использую Rational Purify — ваш Sanitizer там даже близко не лежал.
            • 0
              > Остальное ваши домыслы…

              Вот только не нужно пытаться исправиться. Вы сказали то, что сказали:

              > в windows очень много стороннего не опенсорсного proprietary — хотите ли вы, чтоб ваша программа, использующая что-то из того, обвалилась в никуда,

              > для сей/сей++ под виндами использую Rational Purify — ваш Sanitizer там даже близко не лежал.

              И какой оверхед у Purify, использующего динамическое инструментирование?
              • –1
                Оверхед, как оверхед — ест больше памяти, прога работает чуть медленнее, иногда заметно медленнее и ест заметно больше памяти. Стек вроде не жрет, так как Sanitizer. Тут можно почитать, что они сами думают, правда из доки от solaris. Для винды такого линка не нашел.
    • +1
      > зато позволяет например уменьшить количество access violation

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

      Неужели это правда? Как-то это противоречит современной тенденции пользоваться везде, где можно, готовыми библиотеками и не изобретать велосипеды.
  • 0
    Огда я прикручивал Доуг Ли аллокатор к одной из своих либ, то читал что это стандартный маллок, используемый в гцц. Возможно поэтому на линуксах все нормально отработало.
    • 0
      Тогда он должен быть подвергнут излишней фрагментации…
      Попробую на досуге протестировать или глянуть исходник.
  • 0
    Чтобы понять, если ли утечка памяти или нет, необходимо в большом цикле повторить выделение/освобождение памяти. Если память потечет — это будет отчетливо видно в диспетчере задач. А то, что аллокатор закэшировал кусок памяти — это ни о чем не говорит. Как было написано, он может использовать этот буфер для выделения маленьких блоков.

    Код получится типа такого:
    int main(void)
    {
    	const int blockCount = 1024;
    	const int blockSize = 1024*1024;
    	char **buf;
    	for (int q=0; i<100000; i++)
    	{
    		buf = (char**)malloc(blockCount*sizeof(char*));
    		for (int i=0; i<size; i++)
    		{
    			buf[i] = (char*)malloc(blockSize*sizeof(char));
    		}
    		for (int i=0; i<size; i++)
    		{
    			free(buf[i]);
    		}
    		free(buf);
    	}
    	printf("Hit something...\n");
    	printf("Memory freed\n");
    	getchar();
    	return 0;
    }
    


    --Владимир
  • +1
    Полностью согласен с первым комментатором. Статья демонстрирует явное непонимание матчасти. Автору топика могу посоветовать прочитать книгу «Внутренне устройство Windows» Руссиновича. Тогда все вопросы сразу отпадут. Там есть просто замечательный раздел, описывающий диспетчер памяти. В кратце — runtime-библиотека C++ выделяет память большими блоками методом VirtualAlloc, а потом «пилит» эти блоки на мелкие кусочки, при помощи внутренних структур данных, содержащих списки «маленьких» выделенных блоков. На количество зарезервированной памяти вообще смотреть не стоит, по тому что есть механизм подкачки страниц. Обращать внимание нужно только на рабочий набор. C++ аллокатор в праве освобождать зарезервированные VirtualAlloc'ом участки тогда, когда посчитает нужным. Механизм подкачки в праве выгружать страницы тогда, когда посчитает это оптимальным. В общем это сложная система, и проще один раз прочитать раздел книги.

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