Указатели (Часть 2)

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

В этой части посмотрим на более сложную работу с указателями.

Структуры

Давайте объявим несколько переменных, 2 типа char, один типа int, а затем выведем их адреса в памяти.

В памяти они располагаются следующим образом:

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

Давайте повторим действие выше, но теперь сделаем это с помощью структуры examle (или любое другое имя, часто к новому типа прибавляют суффикс ..._t).

Во-первых, мы видим что адрес структуры и первого элемента в структуре совпадает - мы это уже видели на примере массива (адрес массива и адрес первого элемента совпадает). Во-вторых, здесь мы знакомимся с очень важным принципом (обычно о нем говорят в терминах ООП, но его смысл намного шире) - инкапсуляция. Мы взяли 3 переменные и спрятали их в "капсулу"-структуру. Теперь, каждый раз, когда нам нужно обратиться к переменной, мы делаем это через точку (это очень знакомый синтаксис: объект.поле или объект.функция()).

Если мы попробуем вызвать функцию sizeof(struct example), которая возвращает размер в памяти для указанного типа, то мы получим 8 байт. Хотя все переменные занимают 1 + 1 + 4 = 6 байт, компилятор выравнивает расположение некоторых переменных так, чтобы их адреса были кратны 4 (или 8, 16 и т.д.). Для некоторых процессоров это ускоряет доступ к переменным (некоторые процессоры могут обращаться только к памяти по выровненным адресам и если переменная расположена в двух машинных словах, для доступа к такой переменной процессору нужно выполнить 2 чтения. Эту функцию можно отключить). Расположение переменных в структуре выглядит так, 2 байта (белые) просто не используются:

Что делает оператор точка? Она указывает на смещение относительно базового адреса структуры. Если посмотреть на изображение выше, то видно, что переменная i - это переменная (e+4 байта) типа int, т.е. мы можем записать это и без точки (выглядит немного запутанно, но мы просто взяли 4 байта со смещением 4 байта от начала адреса структуры).

Точно также, как и с обычными переменными, мы можем создать указатель на структуру (e_ptr). Для того, чтобы изменить значение элемента структуры, нам нужно сначала разыменовать указатель, а затем использовать оператор точка [1]. Однако это достаточно частая операция, когда нам нужно взять поле, имея только указатель на структуру. Поэтому в языке си есть отдельный оператор "->", который говорит: "разыменуй указатель, а затем сдвинь его на смещение, указанное после "->" " [2].

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

Однако мы уже знаем, как это исправить - передадим в функцию только указатель на структуру, а не саму структуру.

Что такое объект в терминах ООП? Это такая же структура, но у него (обычно) есть заголовок - header (дополнительная область памяти, в котором располагается служебная информация), а также список функций (об этом чуть позже). Например, в Java виртуальная машина HotSpot в header хранит так называемые class word и mark word (для массивов также размер массива). Более подробно о структуре заголовка объекта (на примере HotSpot) можно найти здесь.

Стоит также понимать, что процессор не "понимает" структуры и объекты. Компилятор сделает из структур и объектов отдельные переменные. Но для человека крайне важно собирать и отделять отдельные концепции в единые сущности. Все, что относится к человеку инкапсулировано в структуре/объекте Person, все что относится к http запросу - в структуре/объекте request и т.д.

Динамическая память

В прошлых примерах мы в основном уделяли внимание памяти в сегменте стека. Не менее важным сегментом является сегмент heap или динамической памяти. Именно здесь можно совершить большое количество ошибок.

Еще раз вспомним стандартное расположение работающей программы в памяти.

В языке си есть 3 стандартные функции для выделения памяти в сегменте heap:

• malloc
• calloc
• realloc

Начнем с самой часто используемой - malloc (сокращение от memory allocation - выделение памяти). Хранить в стеке "тяжелые" объекты (десятки, сотни мегабайт и больше) - очень невыгодно. Обычно этот сегмент не располагает большим количеством памяти, а если еще и передавать объекты по значению, то программа будет работать достаточно медленно.

Решение очень простое - мы выделяем память в отдельном сегменте, а в функции передаем только указатель. Функция malloc просто выделяет память указанного размера и гарантирует, что если кто-то попросит память, то она будет выделена в другом месте.

Рассмотрим на примере. Выделим память под 3 переменные - int и 2 массива

Визуально это выглядит так.

Поработав с этой памятью, мы можем вернуть ее heap, чтобы в будущем ее можно было использовать для других целей. Для этого используется функция free, которой нужно передать указатель на тот участок, который нужно освободить. Вызвав free(i_ptr) и free(buffer), мы получим следующую картину в памяти. Если в будущем мы попросим память, и ее размер уместится до занятого участка [3], то будет выделен этот участок. Если нет - то после.

Не будем сильно углубляться как malloc это делает, каждое выделение памяти записывается в структуру malloc_chunk, которая выглядит так. Здесь есть размер чанка, а также, если чанк пустой, указатели на другие чанки для поиска подходящего или объединения двух рядом находящихся чанков в один побольше.

Также хранится список освобожденных чанков памяти, которые можно переиспользовать. Malloc - это один из аллокаторов (общего назначения, т.е. для выделения как 2 байтов, так и 2 гб). Зная особенности своей программы вы можете написать свой аллокатор (например, если у вас почти все объекты занимают условно 64 байта, то можно сократить затраты на хранение указателей соседних чанков, а хранить занятость в битовом массиве).

Функции calloc не отличается от malloc, но возвращаемый участок будет заполнен нулями. Malloc просто возвращает участок памяти с тем "мусором", что там хранится. Функция realloc используется для того, чтобы перевыделить память большего размера. Если это возможно (есть место сразу после данного участка памяти), то указатель не изменится. Если нет, то realloc найдет новое место в heap, скопирует старое значение памяти туда и вернет новый указатель.

Связные списки, деревья, графы

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

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

Остановимся немного поподробнее на связном списке. Для реализации связного списка нам нужна структура, обычно называемая Node (узел). Каждый такой узел хранит 2 важных типа данных - указатель на другой узел (next), и полезную нагрузку (payload), которая в нашем случае также будет указателем на структуру Payload, которая хранит простое число (это может быть любой тип данных).

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

Сначала мы выделяем память в heap для данных и узла, а затем обновляем указатели так, чтобы теперь head (начало списка) ссылался на только что добавленный узел, а next только что добавленного узла ссылалось в null.

Продолжив выполнять операцию добавления мы получим следующую картину

Давайте добавим метод dump, который будет выводить весь список. Когда список заканчивается? Тогда, когда значение next очередного узла равно NULL.

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

Есть различные реализации связных списков (однократно/дважды связанные, отсортированные или нет, кольцевые или нет). В случае с деревьями видов еще больше и мы не будем останавливаться на конкретных видах. Ярким примером деревьев являются бинарные деревья. В таком случае у структуры данных Node есть 2 указателя на Node, которые обычно называют left и right.

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

Указатель на функции

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

Что такое указатель на функцию? Ничего нового, это просто переменная, которая хранит адрес начала функции. Рассмотрим на примере.

Добавим очень простую функцию func

Все функции содержат 3 необходымых элемента:

• тип возвращаемого значения (в данном случае void)
• название функции (в данном случае func)
• список параметров, который может быть пустым (в данном случае int a)

Теперь как объявить указатель на функцию. Все 3 элемента должны быть отражены в указателе. Как уже было сказано, мы можем создать переменную-указатель на функцию. Как взять адрес функции (первого байта первой инструкции)? Точно также, с помощью оператора &, т.е. &func вернет адрес функции в памяти.

Давайте последовательно смотреть как объявить указатель на функцию. Для начала просто запишем все 3 элемента функции друг за другом. Компилятор пожалуется, что после func_ptr должно идти "=", "," или ";". Список параметров может иметь размер больше 1 (а также быть пустым), поэтому нужно явно выделить его в скобки [2]. Т.к. мы создаем указатель на функцию, не забываем про "звездочку" [3], однако в таком случае компилятор воспринимает запись как указатель на void (т.к. void *func_ptr равно void* func_ptr), поэтому мы должны явно выделить то, что это указатель на функцию в скобки. В итоге получится следующий синтаксис:

возвращаемый_тип (*имя_указателя_на_функцию)(список_типов_параметров).

Теперь мы можем вызвать функцию по указателю следующим образом

Полиморфизм

Вспомним как работает полиморфизм на примере языка Java. Создадим 3 класса: А, В и С. Класс В наследуется от А, класс С наследуется от В (т.е. А<-B<-C). Добавим в класс А 2 метода - func1 и func2, в классе В переопределим func1, а в классе С - func2.

Теперь создадим переменную типа А, которой присвоим сначала объект типа А, затем В и наконец С и вызовем оба метода.

То, какой метод будет вызван зависит от типа объекта (если это объект типа А, то class A func1 и class A func2, если В (в котором переопределен метод func1), то class B func1 и class A func2 и т.д.

Как мы можем реализовать такое полиморфное выполнение? С помощью ссылок на функции.

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

Если присмотреться, то можно заметить что есть всего 4 разных метода (они нарисованы внизу: class A func 1, class A func 2, class B func 1 и class C func 2). В зависимости от того, куда ведет указатель структуры v_table класса мы можем вызвать ту или иную функцию.

Добавим все необходимые структуры: таблица виртуальных адресов, классы А, В и С, 4 различные функции и 2 универсальные функции func1 и func2, которые принимают ссылку на объект А в качестве параметра, разыменовывают таблицу виртуальных адресов и вызывают соответствующую функцию.

В результате меняя указатели на функции в таблице виртуальных адресов мы можем получить тот же эффект. Заметим, что во всех примерах мы вызываем функции только func1 и func2, но результат меняется в зависимости от типа (точнее от значения указателя в таблице виртуальных адресов, но это значение зависит от типа в языках, поддерживающих ООП). Вывод ничем не отличается от Java.

Но почему мы можем вместо class_a_t передать class_b_t? Потому что у них одинаковое расположение полей, а также ссылок на функции. Если наложить class_b_t на class_a_t, то (из-за наследования) размер и смещения полей и них совпадают.

Сборщики мусора

До этого мы видели, что память в разделе heap можно выделять и освобождать, однако забыть освободить память достаточно легко. Многие современные языки имеют отдельный компонент, который называется сборщик мусора (garbage collector). Его цель - найти такие объекты, на которые нет ни одной ссылки (а значит к этому участку памяти никто не обратится), и освободить эту память.

Есть множество способов, как это сделать. Например, у каждого объекта хранится количество ссылок, которые указывают на этот объект. Некоторые операции (присваивание, передача ссылки как параметр функции) увеличивают это значение, а другие (выход из функции, присваивание ссылке NULL значения) уменьшают на 1. Когда значение равно 0, значит нет ни одной ссылки на этот объект и эту память можно очистить.

Наиболее популярный способ - остановка всех потоков и рекурсивный проход по всем объектам, проверяющий их достижимость. Рассмотрим на простом примере.

Пусть у нас будет момент в heap, когда есть 3 каких-то объекта. Серым квадратом обозначен header объектов, в нем есть информация о классе, т.е. какие поля, какого размера и с каким смещением находятся в каждом объекте (это называется object layout). В некоторый момент запускается сборщик мусора и останавливаются все потоки приложения. Затем, начиная с корневых точек (например это ссылки в стеке, глобальные и статические переменные) начинается обход по графу объектов на поиск их достижимости. Пусть у нас есть ссылка только на первый объект (в самом верхнем левом углу). Мы переходим по ссылке на этот объект, помечаем его каким-то специальным способом (достаточно 1 отведенного бита в header объекта), узнаем его тип и какие из полей являются ссылочными, а затем рекурсивно повторяем этот процесс.

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

В дальнейшем можно запомнить указатель на объект, размер и изменить указатели на все объекты таким способом, чтобы "сжать" все объекты в памяти, т.е. сделать следующее:

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

Утечки памяти

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

Что в ней плохого? То, что мы потеряли указатель ptr. При выходе из функции этот указатель перестанет существовать (в том смысле, что мы не сможем обратиться к этой переменной), а значит и освободить память по этому указателю не сможем. Такая ситуация, когда память с одной стороны занята, но не нужна, а с другой стороны - не может быть освобождена, называется утечкой памяти (memory leak). Стоит понимать что память буквально никуда не "утекает", ее просто становится все меньше и меньше, и в один момент ее может просто не хватить.

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

Вам может показаться что это проблема только языков с ручным управлением памяти, но это не так. Возьмем простой пример со структурой стек на языке Java. Мы всегда можем работать только с вершиной стека, но сам язык этого не знает. Сами данные хранятся (обычно) или в массиве, или в связном списке.

Представим следующую картину - у нас есть класс BigObject, который занимает очень много памяти (хранит очень много полей или длинный список). По логике приложения мы хотим обрабатывать его как стек, т.е. заносить объект на вершину стека и снимать с вершины (меняя значение top). В какой-то момент мы добавили 5 объектов с помощью push, а затем все их сняли со стека с помощью pop. Но все что мы сделали, это поменяли значение top, а ссылки в самой структуре остались, т.е.

В этот момент мы уже никогда не сможем обратиться по ссылке, которые есть выше top, т.к. следующие вызовы push перезапишут старые данные. Но ссылки все еще ссылаются на объекты, а значит сборщик мусора, перейдя по ссылке самого объекта Stack, затем увидит массив, перейдет по нему, по каждому ссылке в массиве и отметит каждый объект BigObject как достижимый, т.е. не посчитает этот объект мусором. Для того чтобы сборщик мусора смог собрать эти объекты, нужно присвоить ссылке на BigObject значение null в каждой операции pop.

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

Заключение

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

• объявление, инициализация и синтаксис указателей, null значение
• указатели на указатели
• связь указателей и массивов
• передача параметров функции по ссылке/по значению
• разделы работающей программы (stack, heap, global/static)
• динамические структуры данных
• аллокаторы и сборщики мусора
• утечки памяти

- - - - - - - - - - - - - - - -

Для тех, кто дочитал до конца

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

• поделиться ссылкой на канал [ https://t.me/line_of_code ]
• дополнить/уточнить статью в комментариях (я не знаю всего и я могу ошибаться) или предложить интересную тему
• поддержать материально - https://yoomoney.ru/to/4100117706200369