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

Question

Я потратил несколько минут, чтобы вручную переупорядочить поля в структуре, чтобы уменьшить эффекты заполнения [1], что выглядит как несколько минут слишком много. Мои интуитивные ощущения говорят о том, что мое время, возможно, лучше потратить на написание сценария Perl или еще чего-нибудь, что бы сделать для меня такую ​​оптимизацию.

Мой вопрос: слишком ли это избыточно? уже есть какой-то инструмент, о котором я не знаю, или какая-то функция компилятора, которую я должен иметь возможность включить [2] для упаковки структур?

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

РЕДАКТИРОВАТЬ: быстрое разъяснение - я хочу переупорядочить поле в исходном коде, чтобы избежать заполнения, а не "упаковать" структуру, как при компиляции без заполнения.

РЕДАКТИРОВАТЬ # 2: Другое осложнение: в зависимости от конфигурации, размеры некоторых типов данных также могут изменяться. Очевидными являются указатели и разностные указатели для разных архитектур, а также типы с плавающей запятой (16, 32 или 64-битные в зависимости от «точности»), контрольные суммы (8 или 16-битные в зависимости от «скорости») и некоторые другие неочевидные вещи.

[1] Рассматриваемая структура создается тысячи раз на встроенном устройстве, поэтому каждое 4-байтовое сокращение структуры может означать разницу между go и no-go для этого проекта.

[2] Доступны следующие компиляторы: GCC 3. * и 4. *, Visual Studio, TCC, ARM ADS 1.2, RVCT 3. * и некоторые другие, более неясные.

Answer 1

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

$ cat foo.h 
struct foo {
    int x;
    char y; 
    int b[5];
    char c;
};

$ pstruct foo.h
struct foo {
  int                foo.x                      0       4
  char               foo.y                      4       1
                     foo.b                      8      20
  char               foo.c                     28       1
}

Answer 2

Если каждое отдельное слово, которое вы можете выжать из хранилища, имеет решающее значение, тогда я должен рекомендовать оптимизировать структуру вручную. Инструмент может подобрать элементы оптимально для вас, но он не знает, например, что это значение, которое вы храните здесь в 16 битах, на самом деле никогда не превышает 1024, поэтому вы можете украсть старшие 6 бит для это значение выше здесь ...

Таким образом, человек почти наверняка победит робота на этой работе.

[Редактировать] Но, похоже, вы действительно не хотите оптимизировать свои структуры вручную для каждой архитектуры. Может, вам действительно нужно поддерживать множество архитектур?

Я думаю, что эта проблема не поддается общему решению, но вы можете закодировать свои знания предметной области в пользовательский скрипт Perl / Python / что-то, что генерирует определение структуры для каждой архитектуры.

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

#define MYSTRUCT_POINTERS      \
    Something*  m_pSomeThing;  \
    OtherThing* m_pOtherThing; 

#define MYSTRUCT_FLOATS        \
    FLOAT m_aFloat;            \
    FLOAT m_bFloat;

#if 64_BIT_POINTERS && 64_BIT_FLOATS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS MYSTRUCT_FLOATS
#else if 64_BIT_POINTERS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS
#else if 64_BIT_FLOATS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_FLOATS
#else
    #define MYSTRUCT_64_BIT_MEMBERS
#endif

// blah blah blah

struct MyStruct
{
    MYSTRUCT_64_BIT_MEMBERS
    MYSTRUCT_32_BIT_MEMBERS
    MYSTRUCT_16_BIT_MEMBERS
    MYSTRUCT_8_BIT_MEMBERS
};

Answer 3

Большинство компиляторов Си не делают этого, основываясь на том факте, что вы можете делать странные вещи (например, взять адрес элемента в структуре и затем использовать магию указателя для доступа к остальным, минуя компилятор). Известным примером являются двойные связанные списки в AmigaOS, которые использовали узлы-хранители в качестве заголовка и хвоста списка (это позволяет избежать ifs при обходе списка). Головной узел-хранитель всегда будет иметь pred == null, а хвостовой узел будет иметь next == null, разработчики свернули два узла в единую структуру с тремя указателями head_next null tail_pred. Используя адрес head_next или null в качестве адреса головного и хвостового узлов, они сохранили четыре байта и одно выделение памяти (поскольку им нужна была вся структура только один раз).

Таким образом, вам лучше всего написать структуры в виде псевдокода, а затем написать скрипт препроцессора, который создает реальные структуры из этого.

Answer 4

У меня была такая же проблема. Как предлагается в другом ответе, pstruct может помочь. Но это дает именно то, что нам нужно. Фактически pstruct использует отладочную информацию, предоставленную gcc. Я написал другой сценарий, основанный на той же идее.

Вам необходимо сгенерировать файлы сборки с отладочной информацией STUBS (-gstubs). (Было бы возможно получить ту же информацию от дварфа, но я использовал тот же метод, что и pstruct). Хороший способ сделать это без изменения процесса компиляции - это добавить "-gstubs -save-temps=obj" к вашим параметрам компиляции.

Следующий скрипт читает файлы сборки и определяет, когда в структуру добавляется дополнительный байт:

    #!/usr/bin/perl -n

    if (/.stabs[\t ]*"([^:]*):T[()0-9,]*=s([0-9]*)(.*),128,0,0,0/) {
       my $struct_name = $1;
       my $struct_size = $2;
       my $desc = $3;
       # Remove unused information from input
       $desc =~ s/=ar\([0-9,]*\);[0-9]*;[-0-9]*;\([-0-9,]*\)//g;
       $desc =~ s/=[a-zA-Z_0-9]+://g;
       $desc =~ s/=[\*f]?\([0-9,]*\)//g;
       $desc =~ s/:\([0-9,]*\)*//g;
       my @members = split /;/, $desc;
       my ($prev_size, $prev_offset, $prev_name) = (0, 0, "");
       for $i (@members) {
          my ($name, $offset, $size) = split /,/, $i;
          my $correct_offset = $prev_offset + $prev_size;
          if ($correct_offset < $offset) {
             my $diff = ($offset - $correct_offset) / 8;
             print "$struct_name.$name looks misplaced: $prev_offset + $prev_size = $correct_offset < $offset (diff = $diff bytes)\n";
          }
          # Skip static members
          if ($offset != 0 || $size != 0) {
            ($prev_name, $prev_offset, $prev_size) = ($name, $offset, $size);
          }
       }
    }

Хороший способ вызвать его:

find . -name *.s | xargs ./detectPaddedStructs.pl | sort | un

Answer 5

Думая о том, как мне сделать такой инструмент ... Думаю, я начну с информации об отладке.

Получение размера каждой структуры из источника - это боль. Это накладывается на большую работу, которую уже выполняет компилятор. Я недостаточно знаком с ELF, чтобы точно сказать, как извлечь информацию о размере структуры из двоичного файла отладки, но я знаю, что информация существует, потому что отладчики могут отображать ее. Возможно, objdump или что-то еще в пакете binutils может получить это для вас тривиально (по крайней мере, для платформ, использующих ELF).

После того, как вы получили информацию, все остальное довольно просто. Упорядочивайте элементы от самых маленьких до самых маленьких, стараясь сохранить как можно больше порядка исходной структуры. С perl или python было бы легко связать его с остальными источниками и, возможно, даже сохранить комментарии или #ifdefs в зависимости от того, насколько чисто они использовались. Самой большой болью будет изменение всех инициализаций структуры во всей кодовой базе. Хлоп.

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

Answer 6

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

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

Answer 7

Это также зависит от платформы / компилятора. Как уже отмечалось, большинство компиляторов дополняют все до 4-байтового выравнивания (или еще хуже!), Поэтому предполагается, что структура состоит из 2 коротких и длинных:

short
long
short

займет 12 байтов (с заполнением 2 * 2 байта).

изменить порядок на

short
short
long

все равно будет занимать 12 байтов, так как компилятор будет дополнять его, чтобы ускорить доступ к данным (что является значением по умолчанию для большинства настольных компьютеров, поскольку они предпочитают быстрый доступ по сравнению с использованием памяти). Ваша встроенная система имеет разные потребности, поэтому вам придется использовать пакет #pragma независимо от того.

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

Answer 8

Посмотрите на #pragma pack. Это меняет способ компиляции элементов в структуре. Вы можете использовать его, чтобы заставить их быть тесно упакованными без пробелов.

Подробнее здесь