Выравнивание структуры данных - Data structure alignment

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

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

Согласование данных выравнивание элементов согласно их естественному расположению. Для обеспечения естественного выравнивания может потребоваться вставить несколько набивка между элементами конструкции или после последнего элемента конструкции. Например, на 32-битной машине структура данных, содержащая 16-битное значение, за которым следует 32-битное значение, может иметь 16 бит набивка между 16-битным значением и 32-битным значением, чтобы выровнять 32-битное значение по 32-битной границе. В качестве альтернативы можно пакет структура без заполнения, что может привести к замедлению доступа, но использует три четверти памяти.

Хотя выравнивание структур данных является фундаментальной проблемой для всех современных компьютеров, многие компьютерные языки и реализации компьютерных языков обрабатывают выравнивание данных автоматически. Ада,[1][2] PL / I,[3] Паскаль,[4] определенный C и C ++ реализации, D,[5] Ржавчина,[6] C #,[7] и язык ассемблера разрешить хотя бы частичный контроль заполнения структуры данных, что может быть полезно в определенных особых обстоятельствах.

Определения

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

Альтернативная формулировка b-бит выровнен обозначает b / 8 байтов с выравниванием адрес (напр. 64-битный выровнено по 8 байтов).

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

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

Обратите внимание, что приведенные выше определения предполагают, что каждый элемент данных имеет длину в два байта. Когда это не так (как в случае с 80-битной плавающей точкой на x86 ) контекст влияет на условия, при которых данные считаются выровненными или нет.

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

Проблемы

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

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

Некоторые конструкции процессоров намеренно избегают такой сложности и вместо этого дают альтернативное поведение в случае неправильного доступа к памяти. Например, реализации архитектуры ARM до ARMv6 ISA требуют обязательного согласованного доступа к памяти для всех многобайтовых инструкций загрузки и сохранения.[8] В зависимости от того, какая конкретная инструкция была выдана, результатом попытки несогласованного доступа может быть округление в меньшую сторону наименее значимых бит неправильного адреса, превращая его в согласованный доступ (иногда с дополнительными предостережениями), или выдача исключения MMU (если оборудование MMU присутствует) или незаметно для получения других потенциально непредсказуемых результатов. Начиная с архитектуры ARMv6, была добавлена ​​поддержка обработки невыровненного доступа во многих, но не обязательно во всех случаях.

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

Заполнение структуры данных

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

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

Хотя C и C ++ не позволяют компилятору переупорядочивать элементы структуры для экономии места, другие языки могут. Также можно указать большинству компиляторов C и C ++ «упаковать» элементы структуры до определенного уровня выравнивания, например «pack (2)» означает выравнивание элементов данных размером больше одного байта по двухбайтовой границе так, чтобы любые элементы заполнения имели длину не более одного байта.

Одно из применений таких «упакованных» структур - экономия памяти. Например, структура, содержащая один байт и четырехбайтовое целое число, потребует трех дополнительных байтов заполнения. Большой массив таких структур потреблял бы на 37,5% меньше памяти, если бы они были упакованы, хотя доступ к каждой структуре может занять больше времени. Этот компромисс можно рассматривать как форму компромисс между пространством и временем.

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

Вычислительная набивка

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

padding = (align - (offset mod align)) mod alignaligned = смещение + padding = смещение + ((align - (offset mod align)) mod align)

Например, отступ, добавляемый к смещению 0x59d для 4-байтовой выровненной структуры, равен 3. Затем структура будет начинаться с 0x5a0, что кратно 4. Однако, когда выравнивание компенсировать уже равен выровнять, второй по модулю (align - (смещение mod align)) mod align вернет ноль, поэтому исходное значение останется без изменений.

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

Следующие формулы производят выровненное смещение (где & это побитовое И и ~ а побитовое НЕ ):

заполнение = (выровнять - (смещение & (выровнять - 1))) & (выровнять - 1) = (-смещение & (выровнять - 1)) выровненное = (смещение + (выровнять - 1)) & ~ (выровнять - 1) = (смещение + (выравнивание - 1)) & -align

Типичное выравнивание структур C на x86

Структура данных члены последовательно хранятся в памяти, так что в приведенной ниже структуре элемент Data1 всегда предшествует Data2; и Data2 всегда предшествует Data3:

структура Мои данные{    короткая Данные1;    короткая Данные2;    короткая Данные3;};

Если тип «короткий» хранится в двух байтах памяти, то каждый член структуры данных, изображенной выше, будет выровнен по 2 байта. Data1 будет со смещением 0, Data2 со смещением 2 и Data3 со смещением 4. Размер этой структуры будет 6 байтов.

Тип каждого члена структуры обычно имеет выравнивание по умолчанию, что означает, что он, если иное не требуется программистом, будет выровнен по заранее определенной границе. Следующие типичные выравнивания действительны для компиляторов из Microsoft (Visual C ++ ), Borland /CodeGear (C ++ Builder ), Цифровой Марс (DMC) и GNU (GCC ) при компиляции для 32-битной x86:

  • А символ (один байт) будет выровнен по 1 байту.
  • А короткая (два байта) будут выровнены по 2 байта.
  • An int (четыре байта) будут выровнены по 4 байта.
  • А длинный (четыре байта) будут выровнены по 4 байта.
  • А плавать (четыре байта) будут выровнены по 4 байта.
  • А двойной (восемь байтов) будут выровнены по 8 байтов в Windows и по 4 байтам в Linux (8 байтов с -злокачественный-двойной параметр времени компиляции).
  • А долго долго (восемь байтов) будут выровнены по 4 байта.
  • А длинный двойной (десять байтов с C ++ Builder и DMC, восемь байтов с Visual C ++, двенадцать байтов с GCC) будут 8-байтовыми, выровненными с C ++ Builder, 2-байтовыми с DMC, 8-байтовыми с Visual C ++ и 4 байта с выравниванием по GCC.
  • Любой указатель (четыре байта) будут выровнены по 4 байта. (например: char *, int *)

Единственные заметные различия в выравнивании для LP64 64-битная система по сравнению с 32-битной системой:

  • А длинный (восемь байтов) будут выровнены по 8 байтов.
  • А двойной (восемь байтов) будут выровнены по 8 байтов.
  • А долго долго (восемь байтов) будут выровнены по 8 байтов.
  • А длинный двойной (восемь байтов с Visual C ++, шестнадцать байтов с GCC) будут 8-байтовыми, выровненными с Visual C ++, и 16-байтовыми, выровненными с GCC.
  • Любой указатель (восемь байтов) будут выровнены по 8 байтов.

Некоторые типы данных зависят от реализации.

Вот структура с элементами разных типов, всего 8 байт перед компиляцией:

структура MixedData{    символ Данные1;    короткая Данные2;    int Данные3;    символ Данные4;};

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

структура MixedData  / * После компиляции на 32-битной машине x86 * /{    символ Данные1; / * 1 байт * /    символ Padding1[1]; / * 1 байт для следующего 'короткого' выравнивания по 2-байтовой границепредполагая, что адрес, с которого начинается структура, является четным числом * /    короткая Данные2; / * 2 байта * /    int Данные3;  / * 4 байта - самый большой член структуры * /    символ Данные4; / * 1 байт * /    символ Padding2[3]; / * 3 байта, чтобы общий размер структуры составлял 12 байтов * /};

Скомпилированный размер структуры теперь составляет 12 байт. Важно отметить, что последний член дополняется количеством необходимых байтов, так что общий размер структуры должен быть кратным наибольшему выравниванию любого члена структуры (в данном случае alignment (int), который = 4 на linux-32bit / gcc)[нужна цитата ].

В этом случае 3 байта добавляются к последнему члену для заполнения структуры до размера 12 байтов (выравнивание (int) × 3).

структура FinalPad {  плавать Икс;  символ п[1];};

В этом примере общий размер конструкции размер (FinalPad) == 8, а не 5 (так что размер кратен 4 (выравнивание числа с плавающей запятой)).

структура FinalPadShort {  короткая s;  символ п[3];};

В этом примере общий размер конструкции размер (FinalPadShort) == 6, а не 5 (не 8) (так что размер кратен 2 (alignment (short) = 2 на linux-32bit / gcc)).

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

структура MixedData  / * после переупорядочивания * /{    символ Данные1;    символ Данные4;   / * переупорядочен * /    короткая Данные2;    int Данные3;};

Скомпилированный размер структуры теперь соответствует предварительно скомпилированному размеру 8 байт. Обратите внимание, что Padding1 [1] был заменен (и таким образом исключен) на Данные4 и Padding2 [3] больше не требуется, поскольку структура уже выровнена по размеру длинного слова.

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

Хотя стандартного способа определения выравнивания элементов структуры не существует, некоторые компиляторы используют #pragma директивы для указания упаковки внутри исходных файлов. Вот пример:

#pragma pack (нажать) / * помещаем текущее выравнивание в стек * /#pragma pack (1) / * устанавливаем выравнивание по границе 1 байта * /структура MyPackedData{    символ Данные1;    длинный Данные2;    символ Данные3;};#pragma pack (поп) / * восстанавливаем исходное выравнивание из стека * /

Эта структура будет иметь скомпилированный размер 6 байт в 32-битной системе. Вышеуказанные директивы доступны в компиляторах из Microsoft,[9] Borland, GNU,[10] и много других.

Другой пример:

структура MyPackedData{    символ Данные1;    длинный Данные2;    символ Данные3;} __атрибут__((упакованный));

Упаковка по умолчанию и #pragma pack

В некоторых компиляторах Microsoft, особенно для процессоров RISC, существует неожиданная взаимосвязь между упаковкой проекта по умолчанию (директива / Zp) и #pragma pack директива. В #pragma pack директива может использоваться только для уменьшать размер упаковки конструкции из упаковки проекта по умолчанию.[11] Это приводит к проблемам взаимодействия с заголовками библиотек, которые используют, например, #pragma pack (8), если упаковка проекта меньше этой. По этой причине установка для упаковки проекта любого значения, кроме 8 байтов по умолчанию, нарушит #pragma pack директивы, используемые в заголовках библиотек, и приводят к двоичной несовместимости между структурами. Это ограничение отсутствует при компиляции для x86.

Выделение памяти, выровненной по строкам кеша

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

#включают <stdlib.h>двойной *фу(пустота) {   двойной *вар;// создаем массив размером 10   int     Ok;   Ok = posix_memalign((пустота**)&вар, 64, 10*размер(двойной));   если (Ok != 0)     возвращаться НОЛЬ;   возвращаться вар;}

Аппаратное значение требований к выравниванию

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

Например, в 32-битной операционной системе 4KiB Страница (4096 байт) - это не просто произвольный блок данных размером 4 КиБ. Вместо этого обычно это область памяти, которая выровнена по границе 4 КиБ. Это связано с тем, что выравнивание страницы по границе размера страницы позволяет оборудованию сопоставлять виртуальный адрес с физическим адресом, заменяя старшие биты в адресе, а не выполнять сложные арифметические операции.

Пример: предположим, что у нас есть сопоставление TLB виртуального адреса 0x2CFC7000 с физическим адресом 0x12345000. (Обратите внимание, что оба этих адреса выровнены по границам 4 КиБ.) Доступ к данным, расположенным по виртуальному адресу va = 0x2CFC7ABC, приводит к разрешению TLB от 0x2CFC7 до 0x12345 для выдачи физического доступа к pa = 0x12345ABC. Здесь разделение 20/12 битов, к счастью, совпадает с разделением шестнадцатеричного представления в 5/3 цифр. Аппаратное обеспечение может реализовать эту трансляцию, просто объединив первые 20 бит физического адреса (0x12345) и последние 12 бит виртуального адреса (0xABC). Это также называется виртуально индексированным (ABC), физически помеченным (12345).

Блок данных размером 2(п + 1) - 1 всегда имеет один подблок размера 2п выровнено по 2п байты.

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

// Пример: получить 4096 байт, выровненных в 4096-байтовом буфере с помощью malloc ()// невыровненный указатель на большую областьпустота *вверх = маллок((1 << 13) - 1);// хорошо выровненный указатель на 4 КиБпустота *ap = aligntonext(вверх, 12);

где aligntonext (п, р) работает, добавляя выровненное приращение, а затем очищая р наименее значимые биты п. Возможная реализация

// Предположим, что `uint32_t p, bits;` для удобства чтения#define alignto (p, биты) (((p) >> биты) << биты)#define aligntonext (p, биты) alignto (((p) + (1 << бит) - 1), биты)

Рекомендации

  1. ^ "Положения и прагмы представления Ada". Справочное руководство GNAT документация 7.4.0w. Получено 2015-08-30.
  2. ^ «F.8 Положения о заверениях». Руководство программиста SPARCompiler Ada (PDF). Получено 2015-08-30.
  3. ^ Спецификации языка PL / I операционной системы IBM System / 360 (PDF). IBM. Июль 1966. С. 55–56. C28-6571-3.
  4. ^ Никлаус Вирт (Июль 1973 г.). «Язык программирования Паскаль (исправленный отчет)» (PDF). п. 12.
  5. ^ «Атрибуты - язык программирования D: выровнять атрибут». Получено 2012-04-13.
  6. ^ «Рустономикон - альтернативные представления». Получено 2016-06-19.
  7. ^ "LayoutKind Enum (System.Runtime.InteropServices)". docs.microsoft.com. Получено 2019-04-01.
  8. ^ Куруса, Левенте (27 декабря 2016 г.). «Любопытный случай невыровненного доступа на ARM». Середина. Получено 2019-08-07.
  9. ^ пакет
  10. ^ 6.58.8 Прагмы Structure-Packing
  11. ^ «Работа с упаковочными конструкциями». Библиотека MSDN. Microsoft. 2007-07-09. Получено 2011-01-11.

дальнейшее чтение

  • Брайант, Рэндал Э.; Дэвид, О'Халларон (2003). Компьютерные системы: взгляд программиста (Издание 2003 г.). Река Аппер Сэдл, Нью-Джерси, США: Pearson Education. ISBN  0-13-034074-X.
  • «1. Введение: выравнивание сегментов». Утилиты семейства 8086 - Руководство пользователя систем разработки на базе 8080/8085 (PDF). Редакция E (A620 / 5821 6K DD ed.). Санта-Клара, Калифорния, США: Корпорация Intel. Май 1982 [1980, 1978]. С. 1-6, 3-5. Номер заказа: 9800639-04. Архивировано (PDF) из оригинала на 2020-02-29. Получено 2020-02-29. […] Сегмент может иметь один (а в случае атрибута inpage - два) из пяти атрибутов выравнивания: […] Байт, что означает, что сегмент может располагаться по любому адресу. […] Слово, которое означает, что сегмент может быть расположен только по адресу, кратному двум, начиная с адреса 0H. […] Абзац, который означает, что сегмент может быть расположен только по адресу, кратному 16, начиная с адреса 0. […] Страница, что означает, что сегмент может быть расположен только по адресу, кратному 256 , начиная с адреса 0. […] Inpage, что означает, что сегмент может быть расположен в любом из предшествующих атрибутов, плюс должен быть расположен так, чтобы он не пересекал границу страницы […] Коды выравнивания: […] B - байт […] W - слово […] G - абзац […] xR - inpage […] P - page […] A - absolute […] x в коде выравнивания страницы может быть любым другим кодом выравнивания. […] Сегмент может иметь атрибут inpage, что означает, что он должен находиться в пределах 256-байтовой страницы и может иметь атрибут word, что означает, что он должен располагаться в байте с четным номером. […]

внешняя ссылка