Когда malloc очищает память

http://www.dataved.ru/2014/07/malloc-returns-cleared-memory.html

Jul 11th 2014, 18:26

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

   Сюжет, про который пойдет речь в данной статье — почему аллокатор malloc сегодня возвращает очищенную память. Более точное утверждение — чистую память возвращают аллокаторы, которые вызываются до первой команды free. Благодаря этому замечательному обстоятельству память, которую процесс qemu/kvm выделяет для создаваемой виртуальной машины, заполнена нулями. Тем самым, создаваемая виртуальная машина не может получить доступ к данным гипервизора или других виртуальных машин.

Основные понятия механизмов распределения памяти

  В данном разделе определяются основные понятия управления памятью, необходимые для понимания механизма выделения памяти пользовательским процессам и виртуальным машинам. [дальше пока редактируется]   

Аллокаторы и деаллокаторы

   Для размещения и удаления объектов в куче используются примитивы создать объект и удалить объект, или аллокаторы и деаллокаторы. Библиотечные вызовы malloc и free, соответствующие этим примитивам, определяются в <stdlib.h>. Реализовать перераспределение памяти может любая прикладная или системная программа. Тем не менее изначально память необходимо запросить страницы памяти у операционной системы. В современных версиях Linux запрос страниц памяти у операционной системы происходит с помощью системного вызова mmap, реализующего анонимное отображение памяти.   Процесс qemu/kvm выделяет память, как нормальный процесс Linux — использует библиотечный вызов malloc. Например, для выделения 1 Гб памяти виртуальной машине, qemu/kvm вызывает malloc(1<<30). Данный вызов запускает mmap(start, 1<<30, int prot , int flags, int fd, off_t offset); ???. Тем самым для того, чтобы разобраться, почему же процесс получает обнуленную память, достаточно понять, почему анонимное отображение памяти очищает память.

      Быстрый эмулятор QEMU QEMU (Quick EMUlator) — свободная программа с открытым исходным кодом для эмуляции аппаратного обеспечения различных платформ. Автор программы — гениальный французский программист Фабрис        Беллар, создатель популярной библиотеки libavcodec, эмулятора процессора в браузере, загружающего Линукс, и многих других чудесных произведений. Включает в себя эмуляцию процессоров Intel x86 и устройств ввода-вывода, а также других процессоров. Идет разработка поддержки технологий аппаратной виртуализации (Intel VT и AMD SVM) на x86-совместимых процессорах Intel и AMD.

    Виртуальная машина (ВМ, VM, virtual machine) — программная система, эмулирующая аппаратное обеспечение некоторой гостевой платформы (target — целевая, или гостевая платформа) и исполняющая программы для target-платформы на host-платформе (host — хост-платформа, платформа-хозяин) или виртуализирующая некоторую платформу и создающая на ней среды, изолирующие друг от друга программы и даже операционные системы (см.: песочница); также спецификация некоторой вычислительной среды (например: «виртуальная машина языка программирования Си»).

    Виртуальная машина исполняет машинный код реального процессора x. Помимо процессора, ВМ может эмулировать работу как отдельных компонентов аппаратного обеспечения, так и целого реального компьютера (включая BIOS, оперативную память, жёсткий диск и другие периферийные устройства). В последнем случае в ВМ, как и на реальный компьютер, можно устанавливать операционные системы (например, Windows можно запускать в виртуальной машине под Linux или наоборот). На одном компьютере может функционировать несколько виртуальных машин (это может использоваться для имитации нескольких серверов на одном реальном сервере с целью оптимизации использования ресурсов сервера).     Например, процесс не может определить, монопольно ли он использует процессор или же в режиме мультипрограммирования вместе с другими процессами. В виртуальной машине ни один процесс не может монопольно использовать никакой ресурс, и все системные ресурсы считаются ресурсами потенциально совместного использования. Кроме того, использование виртуальных машин обеспечивает развязку между несколькими пользователями, работающими в одной вычислительной системе, обеспечивая определённый уровень защиты данных.  Идея виртуальной машины лежит в основе целого ряда операционных систем, в частности, IBM VM/CMS (и её советского клона СВМ) и DEC VAX/VMS.  Важным случаем применения виртуальных машин является их использование для защиты информации и ограничения возможностей программ.  

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

    Гостевая операционная система — это операционная система, устанавливаемая на виртуальную машину. Гостевой она называется в отличие от ОС гипервизора, устанавливаемой на физический сервер.  Динамическое распределение памяти

    Динамическое распределение памяти — способ выделения оперативной памяти компьютера для объектов в программе, при котором выделение памяти под объект осуществляется во время выполнения программы. При динамическом распределении памяти объекты размещаются в куче: при конструировании объекта указывается размер запрашиваемой под объект памяти, и, в случае успеха, выделенная область памяти, условно говоря, «изымается» из «кучи», становясь недоступной при последующих операциях выделения памяти. Противоположная по смыслу операция — освобождение занятой ранее под какой-либо объект памяти: освобождаемая память, также условно говоря, возвращается в «кучу» и становится доступной при дальнейших операциях выделения памяти.  По мере создания в программе новых объектов, количество доступной памяти уменьшается. Отсюда вытекает необходимость постоянно освобождать ранее выделенную память. В идеальной ситуации программа должна полностью освободить всю память, которая потребовалась для работы. По аналогии с этим, каждая процедура (функция или подпрограмма) должна обеспечить освобождение всей памяти, выделенной в ходе выполнении процедуры. Некорректное распределение памяти приводит к т.н. «утечкам» памяти, когда выделенная память не освобождается. Многократные утечки памяти могут привести к исчерпанию всей оперативной памяти и нарушить работу операционной системы. Другая проблема — это проблема фрагментации памяти. Выделение памяти происходит блоками — непрерывными фрагментами оперативной памяти (таким образом, каждый блок — это несколько идущих подряд байтов). В какой-то момент, в куче попросту может не оказаться блока подходящего размера и, даже, если свободная память достаточна для размещения объекта, операция выделения памяти окончится неудачей.  Для управления динамическим распределением памяти используется «сборщик мусора» — программный объект, который следит за выделением памяти и обеспечивает её своевременное освобождение. Сборщик мусора также следит за тем, чтобы свободные блоки имели максимальный размер, и, при необходимости, осуществляет дефрагментацию памяти.  Для размещения и удаления объектов в куче используются примитивы «создать объект» и «удалить объект».    Кроме того, перед началом работы программы выполняется инициализация кучи, в ходе которой вся изначально выделенная под кучу память отмечается как свободная. При размещении объекта реализация примитива «создать объект» просматривает доступную куче свободную память в поисках возможности разместить в ней объект требуемого размера. Многие реализации примитивов кучи могут в случае нехватки собственной свободной памяти запросить дополнительную память у операционной системы. В случае, если по тем или иным причинам разместить объект невозможно, примитив «создать объект» сообщает об ошибке (например, malloc возвращает NULL). В случае успеха выбранная область памяти отмечается как занятая. Примитив возвращает адрес начала выделенной области. При удалении объекта реализация примитива «удалить объект» отмечает, что область, ранее использованная удаляемым объектом, теперь свободна.  

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

    В промежутках между вызовами примитивов «создать объект» и «удалить объект» выделенная под объект область памяти не может быть отдана ни под какой другой объект. Поэтому приложение может свободно пользоваться выделенной ему областью памяти. В то же время после вызова примитива «удалить объект» освобождённая область может быть использована повторно или отдана операционной системе, поэтому использование указателя, полученного ранее от примитива «создать объект», будет приводить к сбоям или непредсказуемой работе программы.  Алгоритмы кучи и производительность   Куча — это длинный отрезок адресов памяти, поделенный на идущие подряд блоки различных размеров. Блоки бывают свободные и занятые. Для возможности выделения памяти путем повторного использования свободного блока (без дорогостоящего увеличения кучи в целом — требует системного вызова) в том или ином виде нужен список свободных блоков. Для сокращения списка свободных блоков с целью уменьшения времени его обхода всегда имеет смысл сливать 2 или 3 идущих подряд свободных блока в один. Если свободен последующий блок, то его легко найти, отступив вперед на размер освобождаемого блока. С предыдущим блоком все сложнее, и потому имеет смысл хранить размер предыдущего блока (для его поиска) в заголовке любого блока. Список свободных блоков может быть организован по-разному, и от его организации прямо зависит производительность кучи. Дело в том, что большая часть времени в операции выделения тратится именно на поиск в этом списке.   Очень хорошей реализацией является несколько списков, каждый для своего размера. Это позволяет быстро проигнорировать заведомо слишком маленькие свободные блоки целыми списками, без проверки каждого персонально.    

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

    Отложенная (ленивая) инициализация (lazy initialization) — прием в программировании, когда некоторая ресурсоемкая операция (создание объекта, вычисление значения) выполняется непосредственно перед тем, как будет использован ее результат. Таким образом, инициализация выполняется по требованию, а не заблаговременно. Аналогичная идея находит применение в самых разных областях: например, при компиляции на лету метод компилируется непосредственно перед исполнением, при использовании отображения в память файла страница загружается с диска только когда к ней происходит обращение.

     Отображение в память. Вызов mmap — POSIX-совместимый системный вызов Linux, позволяющий выполнить отображение файла или устройства на память. Может использоваться как для ленивого ввода-вывода, так и в анонимном режиме как менеджер памяти для выделения страниц по запросу.

      Анонимные отображения — отображения пространства виртуальной памяти процесса, а не файла в пространстве файловой системы. По этой причине анонимное отображение схоже с функцией malloc и используется в некоторых реализациях malloc для определённых размещений. Следует заметить, что анонимные отображения не являются частью стандарта POSIX, хотя и реализованы почти во всех POSIX-системах.Файловые отображения позволяют отобразить файл в виртуальной памяти (практически это буферизация чтения/записи конкретного файла с прямым — по адресам памяти — доступом к буферу, как области отображения файла в памяти). Доступ к этим участкам памяти приводит к чтению/записи файла. Если отображение распределено между процессами, запись в это пространство в одном процессе окажет воздействие на другие процессы. Если используется частное (private) отображение, то изменения не будут видны другим процессам и не будут записаны в файл.Процесс чтения/записи в отображенный в виртуальную оперативную память файл не всегда приводит к ожидаемому результату, поскольку сегменты файла копируются в оперативную память и периодически выгружаются на диск, однако синхронизация может быть форсирована с помощью системного вызова msync.mmap файлов может значительно снизить нагрузку на диск для нескольких программ-приложений, обращающихся к одному и тому же файлу. Если файл отображён в памяти, программы-приложения могут разделять сегмент памяти, являющийся отображением файла в памяти, вместо загрузки файла для каждой прогаммы-приложения, желающей обратиться к данному файлу.К памяти, распределённой с помощью mmap, можно осуществлять доступ из дочерних процессов.mmap можно использовать для реализации межпроцессного взаимодействия (IPC). В современных операционных системах mmap обычно предпочтительней взаимодействию через распределённую память в стиле System V. Память mmap не сохраняется между запусками прикладных программ, если отображение не зарезервировано в файле — сегмент памяти, созданный mmap, автоматически удаляется ядром системы, когда завершатся все использующие его программы-приложения.

   Cервер управления доступом FreeIPA Сервер управления доступом IPA (Identity, Policy and Audit) это свободный программный продукт для создания централизованной системы для идентификации пользователей и задания политик доступа, система обеспечения безопасности в средах виртуализации. Cистема управления виртуализацией oVirt oVirt — свободная, кроссплатформенная система управления виртуализацией. Позволяет управлять гипервизором и образами виртуальных машин на базе технологии KVM посредством веб-интерфейса, используя для администрирования библиотеку libvirt.   

    Среда виртуализации. Red Hat Enterprise Virtualization Red Hat Enterprise Virtualization (RHEV) — корпоративный продукт, обеспечивающий возможности виртуализации. Основан на свободных продуктах: гипервизоре KVM, сервере управления доступом FreeIPA и веб-приложении управления виртуализацией oVirt.   

Механизм выделения памяти для виртуальных машин

   Once the guest is running, it sees that malloc()'d memory area as being its physical memory. If the guest's kernel were to access what it sees as physical address 0x0, it will see the first page of that malloc() done by the qemu/kvm process. It used to be that every time a KVM guest changed its page tables, the host had to be involved. The host would validate that the entries the guest put in its page tables were valid and that they did not access any memory which was not allowed. It did this with two mechanisms. One was that the actual set of page tables being used by the virtualization hardware are separate from the page tables that the guest *thought* were being used. The guest first makes a change in its page tables. Later, the host notices this change, verifies it, and then makes a real page table which is accessed by the hardware. The guest software is not allowed to directly manipulate the page tables accessed by the hardware. This concept is called shadow page tables and it is a very common technique in virtualization. The second part was that the VMX/AMD-V extensions allowed the host to trap whenever the guest tried to set the register pointing to the base page table (CR3). This technique works fine. But, it has some serious performance implications. A single access to a guest page can take up to 25 memory accesses to complete, which gets very costly. See this paper: http://developer.amd.com/assets/NPT-WP-1%201-final-T... for more information. The basic problem is that every access to memory must go through both the page tables of the guest and then the page tables of the host. The two-dimensional part comes in because the page tables of the guest must *themselves* go through the page tables of the host. It can also be very costly for the host to verify and maintain the shadow page tables. Both AMD and Intel sought solutions to these problems and came up with similar answers called EPT and NPT. They specify a set of structures recognized by the hardware which can quickly translate guest physical addresses to host physical addresses *without* going through the host page tables. This shortcut removes the costly two-dimensional page table walks. The problem with this is that the host page tables are what we use to enforce things like process separation. If a page was to be unmapped from the host (when it is swapped, for instance), it then we *must* coordinate that change with these new hardware EPT/NPT structures. The solution in software is something Linux calls mmu_notifiers. Since the qemu/kvm memory is normal Linux memory (from the host Linux kernel's perspective) the kernel may try to swap it, replace it, or even free it just like normal memory. But, before the pages are actually given back to the host kernel for other use, the kvm/qemu guest is notified of the host's intentions. The kvm/qemu guest can then remove the page from the shadow page tables or the NPT/EPT structures. After the kvm/qemu guest has done this, the host kernel is then free to do what it wishes with the page. A day in the life of a KVM guest physical page: Fault-in path QEMU calls malloc() and allocates virtual space for the page, but no backing physical page The guest process touches what it thinks is a physical address, but this traps into the host since the memory is unallocated The host kernel sees a page fault, calls do_page_fault() in the area that was malloc()'d, and if all goes well, allocates some memory to back it. The host kernel creates a pte_t to connect the malloc()'d virtual address to a host physical address, makes rmap entries, puts it on the LRU, etc... mmu_notifier change_pte()?? is called, which allows KVM to create an NPT/EPT entry for the new page. (and an spte entry??) Host returns from page fault, guest execution resumes Swap-out path Now, let's say the host is under memory pressure. The page from above has gone through the Linux LRU and has found itself on the inactive list. The kernel decides that it wants the page back: The host kernel uses rmap structures to find out in which VMA (vm_area_struct) the page is mapped. The host kernel looks up the mm_struct associated with that VMA, and walks down the Linux page tables to find the host hardware page table entry (pte_t) for the page. The host kernel swaps out the page and clears out the pte_t (let's assume that this page was only used in a single place). But, before freeing the page: The host kernel calls the mmu_notifier invalidate_page(). This looks up the page's entry in the NPT/EPT structures and removes it. Now, any subsequent access to the page will trap into the host ((2) in the fault-in path above)

    Процесс qemu/kvm выделяет память, как нормальный процесс Linux — использует библиотечный вызовmalloc. Например, для выделения 1 Гб памяти виртуальной машине, qemu/kvm вызываетmalloc(1<<30). Данный вызов запускает mmap(start, 1<<30, int prot , int flags, int fd, off_t offset); ???. Тем самым для того, чтобы разобраться, почему же процесс получает обнуленную память, достаточно понять, почему анонимное отображение памяти очищает память.

______________________________________

© Мария Федотова, Свободное общество dataved.ru