Когда в последний раз Вы задумывались, как выделяется память на самом низком уровне? Пытались ли Вы изобрести этот «велосипед» с нуля? Простой ли это «велосипед»?

В данной серии публикаций я постараюсь рассказать про выделение памяти в операционной системе Linux 6-й версии ядра с картинками и источниками, а также рассказать про особенности ее работы со стандартной библиотекой C. Целью данной серии публикаций является выявление связи вызова malloc, структур ядра, системных вызовов и выделений физических страниц процессам.

Ну что, пошлите смотреть, из чего сделан «велосипед» памяти?

Основная часть

Начнем с главного: структур ядра, системных вызовов Linux и виртуального адресного пространства. Сначала немного слов про физическую память и виртуальную. Ядра операционных систем управляют именно физической памятью, когда процессам выдается так называемое «виртуальное адресное пространство». Память, не важно какая, формируется в страницы, размер которых в нынешних версиях ОС равен 4096 байт или просто 4 КБ.

Процессы и память

В дескрипторе процесса task_struct имеется указатель mm. Процессы, обладающие адресным пространством, содержат указатель mm не равный NULL.

Часть листинга структуры task_struct:

 struct task_struct {
 ...
         struct mm_struct		mm;
         struct mm_struct		active_mm;
         struct address_space		*faults_disabled_mapping;
         int				exit_state;
         int				exit_code;
         int				exit_signal;
 ...
 };

Адресные пространства процессов определяются структурой mm_struct. Это означает, что для каждого процесса существует только один её экземпляр, который разделяется между пользовательскими потоками. Немного про mm_struct:

struct mm_struct {
        struct vm_area_struct  *mmap;               /* list of memory areas */
        struct rb_root         mm_rb;               /* red-black tree of VMAs */
        struct vm_area_struct  *mmap_cache;         /* last used memory area */
        unsigned long          free_area_cache;     /* 1st address space hole */
        pgd_t                  *pgd;                /* page global directory */
        atomic_t               mm_users;            /* address space users */
        atomic_t               mm_count;            /* primary usage counter */
        int                    map_count;           /* number of memory areas */
        struct rw_semaphore    mmap_sem;            /* memory area semaphore */
        spinlock_t             page_table_lock;     /* page table lock */
        struct list_head       mmlist;              /* list of all mm_structs */
        unsigned long          start_code;          /* start address of code */
        unsigned long          end_code;            /* final address of code */
        unsigned long          start_data;          /* start address of data */
        unsigned long          end_data;            /* final address of data */
        unsigned long          start_brk;           /* start address of heap */
        unsigned long          brk;                 /* final address of heap */
        unsigned long          start_stack;         /* start address of stack */
        unsigned long          arg_start;           /* start of arguments */
        unsigned long          arg_end;             /* end of arguments */
        unsigned long          env_start;           /* start of environment */
        unsigned long          env_end;             /* end of environment */
        unsigned long          rss;                 /* pages allocated */
        unsigned long          total_vm;            /* total number of pages */
        unsigned long          locked_vm;           /* number of locked pages */
        unsigned long          def_flags;           /* default access flags */
        unsigned long          cpu_vm_mask;         /* lazy TLB switch mask */
        unsigned long          swap_address;        /* last scanned address */
        unsigned               dumpable:1;          /* can this mm core dump? */
        int                    used_hugetlb;        /* used hugetlb pages? */
        mm_context_t           context;             /* arch-specific data */
        int                    core_waiters;        /* thread core dump waiters */
        struct completion      *core_startup_done;  /* core start completion */
        struct completion      core_done;           /* core end completion */
        rwlock_t               ioctx_list_lock;     /* AIO I/O list lock */
        struct kioctx          *ioctx_list;         /* AIO I/O list */
        struct kioctx          default_kioctx;      /* AIO default I/O context */
};

Современные 64 разрядные системы на операционной системе Linux обеспечивают адресное пространство размером в 256 терабайт, используя 48 битную адресацию. Так как каждый процесс имеет свое виртуальное адресное пространство, то его размер также составляет 256 терабайт. На рисунке ниже показано адресное пространство процесса. Процесс может адресовать адреса до 0x0000 7FFF FFFF F000, что обеспечивает адресацию 128ТБ. Регион памяти 0x0000 7FFF FFFF F000-0xFFFF FFFF FFFF FFFF используется операционной системой и имеет адресуемый размер в 128ТБ.

В адресном пространстве процесса задействованы отдельные регионы. Полностью адресное пространство редко используется. Каждый регион выделен структурой vm_area_struct, которые никогда не перекрываются и представляют собой последовательность адресов с одинаковой защитой и назначением. Регион адресного пространства определяется границами в виртуальном адресном пространстве. Границы региона памяти представлены двумя полями в структуре vm_area_struct: vm_start и vm_end. На рисунке ниже показан классический пример границ региона виртуального адресного пространства. Регион может быть представлен в виде разделяемой библиотеки, некоторой области кучи, коду, сегменту данных, отображенному файлу. Так как регион виртуальный, то одна его часть может быть загружена в память, а другая - нет. Если регион памяти связан с файлом, то поле vm_file не равно NULL.

Структура vm_area_struct:

struct vm_area_struct {
        struct mm_struct             *vm_mm;        /* associated mm_struct */
        unsigned long                vm_start;      /* VMA start, inclusive */
        unsigned long                vm_end;        /* VMA end , exclusive */
        struct vm_area_struct        *vm_next;      /* list of VMA's */
        pgprot_t                     vm_page_prot;  /* access permissions */
        unsigned long                vm_flags;      /* flags */
        struct rb_node               vm_rb;         /* VMA's node in the tree */
        union {         /* links to address_space->i_mmap or i_mmap_nonlinear */
                struct {
                        struct list_head        list;
                        void                    *parent;
                        struct vm_area_struct   *head;
                } vm_set;
                struct prio_tree_node prio_tree_node;
        } shared;
        struct list_head             anon_vma_node;     /* anon_vma entry */
        struct anon_vma              *anon_vma;         /* anonymous VMA object */
        struct vm_operations_struct  *vm_ops;           /* associated ops */
        unsigned long                vm_pgoff;          /* offset within file */
        struct file                  *vm_file;          /* mapped file, if any */
        void                         *vm_private_data;  /* private data */
};

На рисунке ниже показана связь структур mm_struct и vm_area_struct. В mm_struct указатель mmap указывает на первый vm_area_struct в виртуальном адресном пространстве. Структуры vm_area_struct составляют односвязный список в каждой mm_struct. Каждое vm_area_struct имеет указатель на mm_struct через поле vm_next.

На рисунке ниже представлена связь структуры vm_area_struct и file. Если указатель vm_file не равен NULL, то vm_area_struct связана с файлом.

Теперь к маленьким выводам и дополнениям.

Разрядность системы — это разрядность ЦПУ. Все современные ЦПУ используют 64 бита для вычислений, когда достаточно древние ЦПУ используют 32 бита. Если уж говорить и про 16-ти битные ЦПУ, то рассматриваются ЦПУ 20-го века. Эти биты позволяют использовать значений. Так как указатель — это переменная, по объему разрядности которая 64 бита, 8 байт, то и указывает она на байт. В ОС Linux используется 48 бит для адресации в виртуальном адресном пространстве.

Теперь про разницу виртуальной и физической памяти. С точки зрения ядра (НЕ цитировать!) вся физическая память — одно единое адресное пространство. То есть ядро видит все, что лежит в каждой плашке ОЗУ. Виртуальное адресное пространство на то и виртуальное, что на самом деле не является действительным. Оно выдается каждому процессу, чтобы процесс считал, что у него находится ВСЯ память вычислительной системы. Действительно используется лишь малая часть этого пространства. Каждая страница такого адресного пространства называется виртуальной. Особенностью виртуальной страницы относительно изучаемой темы является ее резидентность. Резидентная страница — это виртуальная страница, которая выгружена в физическую память, то есть находится таблице страниц. Причем все виртуальные страницы при выделении остаются выгруженными (не в оперативной памяти) до тех пор, пока к ним не произойдет обращение, что вызовет страничное прерывание.

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

Последний важный вывод: процесс не обладает памятью. Процесс имеет виртуальное адресное пространство.

Анализ системных вызовов brk и mmap

Можно спросить себя: как тогда выделяется память обычным процессам? На этот вопрос отвечают два системных вызова: brk и mmap.

Системные вызовы brk и mmap/munmap предназначены для управления регионами в виртуальном адресном пространстве.

Системный вызов brk используется в большинстве случаев для изменения одной из границ региона памяти vm_area_struct. Однако если простое расширение региона памяти является невозможным, будет создана новая vm_area_struct.

Системные вызовы mmap и munmap нужны для управления отображениями в виртуальном адресном пространстве процесса. При вызове mmap создается новый vm_area_struct для одного отображения. Системный вызов munmap используется для удаления vm_area_struct. При вызове mmap возвращает указатель на отображенные данные. Поддерживается флаг MAP_ANONYMOUS, позволяющий реализовывать анонимные отображения. Анонимное отображение --- это отображение пространства виртуальной памяти процесса, а не файла в пространстве файловой системы. Анонимные отображения не являются частью стандарта POSIX, однако реализованы во многих системах

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

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

Теперь переварим сказанное. Системный вызов brk используется для изменения границы особой vm_area_struct. При чем эта vm_area_struct связана с кучей процесса (Heap) и изменяется именно граница, связанная с названием "разрыв программы" (program BReaK, отсюда и название системного вызова brk). Системный вызов mmap создает совершенно новый vm_area_struct в виртуальном адресном пространстве, то есть ничего не расширяет, а создает новый регион памяти.

Виртуальная память также выделяется страницами, как и физическая память.

Другой важный вывод заключается в выделении памяти. Виртуальная память выделяется МОМЕНТАЛЬНО при вызове. Виртуальная страница памяти будет загружена в физическую память только при первом обращении к ней.

Заключение

В данной серии публикации мы рассмотрели каркас нашего «велосипеда». Однако до сих пор мы не ответили на вопросы «что делать с системными вызовами?». В следующей серии публикаций будем рассматривать механизмы управления памятью в виртуальном адресном пространстве. Рассмотрим часть реализации библиотеки Glibc и ее аллокатора ptmalloc2.

Источники

• Описание физической памяти в Linux

• Документация ядра Linux. Управление физической памятью