Управление памятью C для кроссплатформенной виртуальной машины

Question

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

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

Дело в том, что я не программирую на C, последний раз, когда я писал нетривиальную задачу на C, было более 10 лет назад.Я был программистом на Pascal, Delphi, а теперь на Java и PHP.

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

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

int main(void) {
    // Prepare stack
    int   aStackSize = 1024*4;
    char *aStackData = malloc(aStackSize);

    // Initialise stack
    VMStack aStack;
    VMStack_Initialize(&aStack, (char *)aStackData, aStackSize);

    // Push in the parameters
    char *Params = VMStack_CurrentPointer(&aStack);
    VMStack_Push_int   (&aStack, 10  ); // Push an int
    VMStack_Push_double(&aStack, 15.3); // Push a double

    // Prepare space for the expected return
    char *Result = VMStack_CurrentPointer(&aStack);
    VMStack_Push_double(&aStack, 0.0); // Push an empty double for result

    // Execute
    void (*NativeFunction)(char*, char*) = &Plus;
    NativeFunction(Params, Result); // Call the function

    // Show the result
    double ResultValue = VMStack_Pull_double(&aStack); // Get the result
    printf("Result:  %5.2f\n", ResultValue);               // Print the result

    // Remove the previous parameters
    VMStack_Pull_double(&aStack); // Pull to clear space of the parameter
    VMStack_Pull_int   (&aStack); // Pull to clear space of the parameter

    // Just to be sure, print out the pointer and see if it is `0`
    printf("Pointer: %d\n", aStack.Pointer);

    free(aStackData);
    return EXIT_SUCCESS;
}

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

Для полноты картины (чтобы вы могли попробовать это на своей машине), вот код для Stack:

typedef struct {
    int  Pointer;
    int  Size;
    char *Data;
} VMStack;

inline void   VMStack_Initialize(VMStack *pStack, char *pData, int pSize) __attribute__((always_inline));
inline char   *VMStack_CurrentPointer(VMStack *pStack)                    __attribute__((always_inline));
inline void   VMStack_Push_int(VMStack *pStack, int pData)                __attribute__((always_inline));
inline void   VMStack_Push_double(VMStack *pStack, double pData)          __attribute__((always_inline));
inline int    VMStack_Pull_int(VMStack *pStack)                           __attribute__((always_inline));
inline double VMStack_Pull_double(VMStack *pStack)                        __attribute__((always_inline));

inline void VMStack_Initialize(VMStack *pStack, char *pData, int pSize) {
    pStack->Pointer = 0;
    pStack->Data    = pData;
    pStack->Size    = pSize;
}

inline char *VMStack_CurrentPointer(VMStack *pStack) {
    return (char *)(pStack->Pointer + pStack->Data);
}

inline void VMStack_Push_int(VMStack *pStack, int pData) {
    *(int *)(pStack->Data + pStack->Pointer) = pData;
    pStack->Pointer += sizeof pData; // Should check the overflow
}
inline void VMStack_Push_double(VMStack *pStack, double pData) {
    *(double *)(pStack->Data + pStack->Pointer) = pData;
    pStack->Pointer += sizeof pData; // Should check the overflow
}

inline int VMStack_Pull_int(VMStack *pStack) {
    pStack->Pointer -= sizeof(int);// Should check the underflow
    return *((int *)(pStack->Data + pStack->Pointer));
}
inline double VMStack_Pull_double(VMStack *pStack) {
    pStack->Pointer -= sizeof(double);// Should check the underflow
    return *((double *)(pStack->Data + pStack->Pointer));
}

На стороне собственной функции я создал следующее для целей тестирования:

// These two structures are there so that Plus will not need to access its parameter using
//    arithmetic-pointer operation (to reduce mistake and hopefully for better speed).
typedef struct {
    int    A;
    double B;
} Data;
typedef struct {
    double D;
} DDouble;


// Вот вспомогательная функция для отображения 
аннулировать данные печати (Data * pData, DDouble * предварительный результат) {
    printf("%5.2f + %5.2f = %5.2f \ n", pData-> A*1.0, pData->B, предварительный результат->D);}

// Некоторая встроенная функция 
void плюс(char* pParams, char * pResult) {
    Данные * D = (Data *)pParams;// Доступ к данным без операции с арифметическим указателем
    DDouble *DD = (DDouble *) предварительный результат;// То же самое для возврата
    DD-> D = D-> A + D-> B;Печатные данные (D, DD);}

При выполнении приведенный выше код возвращает:

10.00 + 15.30 = 25.30
Result:  25.30
Pointer: 0

Это хорошо работает на моей машине (Linux x86 32bits GCC-C99).Будет очень приятно, если это сработает и на других ОС / архитектуре.Но есть ПО КРАЙНЕЙ мере три проблемы, связанные с памятью, о которых мы должны знать.

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

2).Порядковый номер - то же самое с размером данных.

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

Мои вопросы таковы:

1).Если я знаю размер типов, есть ли способ изменить функцию push-and-pull для точной синхронизации с заполнением структуры?(измените, чтобы позволить компилятору позаботиться об этом, например, о проблемах Datasize и Endians).

2).Если я упакую структуру по одному (используя #pragma pack(1));(2.1) Будет ли приемлемым штраф за производительность?и (2.2) Будет ли под угрозой стабильность программы?

3).Как насчет увеличения на 2,4 или 8?Что должно быть хорошо для обычной 32- или 64-битной системы?

4).Можете ли вы привести меня к документации по точному алгоритму заполнения, скажем, для GCC на x86?

5).Есть ли лучший способ?

ПРИМЕЧАНИЕ:Кроссплатформенность это не моя конечная цель, но я не могу устоять.Кроме того, производительность не является моей целью, пока она не станет такой уродливой.Все это для развлечения и обучения.

Извините за мой английский и очень длинный пост.

Заранее всем спасибо.

Answer 1

Касательные Комментарии

Эти первые пункты имеют непосредственное отношение к заданным вами вопросам, но...

// Execute
void (*NativeFunction)(char*, char*) = &Plus;
NativeFunction(Params, Result); // Call the function

Я думаю, вам, вероятно, следует использовать здесь 'void *' вместо 'char *'.У меня также был бы typedef для типа указателя функции:

typedef void (*Operator)(void *params, void *result);

Тогда вы можете написать:

Operator NativeFunction = Plus;

Фактическая функция тоже была бы изменена, но лишь очень незначительно:

void Plus(void *pParams, void *pResult)

Кроме того, у вас есть небольшая проблема с именованием - эта функция 'IntPlusDoubleGivesDouble()', а не функция общего назначения 'добавить любые два типа'.

---

Прямые ответы на вопросы

1).Если я знаю размер типов, есть ли способ изменить функцию push-and-pull для точной синхронизации с заполнением структуры?(измените, чтобы позволить компилятору позаботиться об этом, например, о проблемах Datasize и Endians).

Нет простого способа сделать это.Например, рассмотрим:

struct Type1
{
     unsigned char byte;
     int           number;
};
struct Type2
{
     unsigned char byte;
     double        number;
};

На некоторых архитектурах (например, 32-разрядный или 64-разрядный SPARC) структура Type1 будет иметь 'number', выровненный по 4-байтовой границе, но структура Type2 будет иметь 'number', выровненный по 8-байтовой границе (и может иметь 'long double' на 16-байтовой границе).Ваша стратегия "выталкивания отдельных элементов" увеличила бы указатель стека на 1 после нажатия значения "байт" - поэтому вы хотели бы переместить указатель стека на 3 или 7, прежде чем нажимать "число", если указатель стека еще не выровнен надлежащим образом.Частью описания вашей виртуальной машины будут требуемые выравнивания для любого заданного типа;соответствующий код нажатия необходим для обеспечения правильного выравнивания перед нажатием.

2).Если я упакую структуру по одному (используя #pragma pack(1));(2.1) Будет ли приемлемым штраф за производительность?и (2.2) Будет ли под угрозой стабильность программы?

На компьютерах x86 и x86_64, если вы упакуете данные, вы понесете снижение производительности из-за несогласованного доступа к данным.На таких машинах, как SPARC или PowerPC(за меки), вместо этого вы получите ошибку шины или что-то подобное - вы должны получить доступ к данным при их правильном выравнивании.Вы могли бы сэкономить немного места в памяти - за счет снижения производительности.Вам было бы лучше обеспечить производительность (которая здесь включает в себя "правильную работу вместо сбоев") при минимальных затратах в пространстве.

3).Как насчет увеличения на 2,4 или 8?Что должно быть хорошо для обычной 32- или 64-битной системы?

В SPARC вам нужно дополнить N-байтовый базовый тип N-байтовой границей.На x86 вы получите наилучшую производительность, если сделаете то же самое.

4).Можете ли вы указать мне документацию для точного алгоритма заполнения, скажем, для GCC на x86?

Вам пришлось бы прочитать руководство пользователя.

5).Есть ли лучший способ?

Обратите внимание, что трюк 'Type1' с единственным символом, за которым следует тип, дает вам требование к выравниванию - возможно, с использованием макроса 'offsetof()' из <stddef.h>:

offsetof(struct Type1, number)

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

Я также не уверен, что стал бы писать код в операторных функциях, предполагая, что стек содержит структуру.Я бы извлек значения из стека с помощью аргумента Params, зная, каковы правильные смещения и типы.Если бы я нажал целое число и double, то я бы вытащил целое число и double (или, может быть, в обратном порядке - я бы вытащил double и int).Если вы не планируете необычную виртуальную машину, немногие функции будут иметь много аргументов.

Answer 2

Интересный пост, который показывает, что вы проделали большую работу.Почти идеальный пост SO.

У меня нет готовых ответов, поэтому, пожалуйста, потерпите меня.Мне придется задать еще несколько вопросов :P

1).Если я знаю размер типов, есть ли способ изменить функцию push-and-pull для точной синхронизации с заполнением структуры?(измените, чтобы позволить компилятору позаботиться об этом, например, о проблемах Datasize и Endians).

Это только с точки зрения производительности?Планируете ли вы ввести указатели вместе с собственными арифметическими типами?

2).Если я упакую структуру по одному (используя #pragma pack(1));(2.1) Будет ли приемлемым штраф за производительность?и (2.2) Будет ли под угрозой стабильность программы?

Это вещь, определяемая реализацией.Это не то, на что вы можете рассчитывать на разных платформах.

3).Как насчет увеличения на 2,4 или 8?Что должно быть хорошо для обычной 32- или 64-битной системы?

Значение, совпадающее с собственным размером слова, должно обеспечить вам оптимальную производительность.

4).Можете ли вы привести меня к документации по точному алгоритму заполнения, скажем, для GCC на x86?

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

Обратите внимание, что вы можете укажите атрибуты переменных используя GCC (который также имеет нечто, называемое default_struct __attribute__((packed)) это отключает заполнение).

Answer 3

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

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

Проблем почти бесконечно, они хорошо изучены и, скорее всего, поглотят нас в противостоянии и внутренней непримиримости.если я могу предложить прочитать Домашняя страница Кеннета Лаудена а также руководство по архитектуре Intel.Она у меня есть, я пытался ее прочитать.Выравнивание структуры данных, наряду со многими другими вопросами, которые вы выносите на обсуждение, глубоко укоренились в исторической науке о компиляторах и, скорее всего, заставят вас погрузиться неизвестно во что.( сленг или идиоматическое обозначение непредвиденных последствий )

С учетом сказанного, вот так:

1. Размеры C-типа Какие типоразмеры?
2. Инженер-компьютерщик до перехода на Инженер-программист Вы когда-нибудь изучали микроконтроллеры?Взгляните на некоторые работы Дона Ланкастера.
3. Pascal, Delphi, а теперь Java и PHP программист. Они сравнительно удалены от базовой фундаментальной архитектуры процессоров, хотя множество людей покажут или попытаются показать, как их можно использовать для написания мощных и фундаментальных подпрограмм.Я предлагаю взглянуть на анализатор рекурсивного спуска Дэвида Эка, чтобы точно понять, с чего начать изучение этого вопроса.Кроме того, у Кеннета Лаудена есть реализация "Tiny", которая является настоящим компилятором.Не так давно я нашел кое - что , что , по - моему , называлось asm dot org ...там была доступна для изучения очень продвинутая, очень мощная работа, но начинать писать на ассемблере, намереваясь углубиться в науку о компиляторах, - долгий путь.Кроме того, большинство архитектур имеют различия, которые не согласуются между собой от одного процессора к другому.
4. доступ к существующей библиотеке

Вокруг много библиотек, в Java есть несколько хороших.Я не знаю об остальных.Один из подходов заключается в попытке написать библиотеку.Java имеет хорошую базу и оставляет место для людей, которым нравится пытаться придумать что-то лучшее.Начните с улучшения Кнута-Морриса-Пратта или чего-то в этом роде:Просто нет недостатка в местах, с которых можно начать.Попробуй Каталог Алгоритмов компьютерного программирования и, конечно же, посмотрите на Словарь алгоритмов и структур данных в NIST

5. always_inline всегда в строке

Необязательно, см. Дов Булька - работник имеет докторскую степень в области CS, а также является опытным автором в областях, где временная эффективность / надежность-робастность и так Далее Не подпадают под некоторые парадигмы "бизнес-модели", откуда мы получаем некоторые из "О!это не имеет значения" по вопросам, которые действительно имеют значение.

В заключение отметим, что инструментарий и контроль составляют более 60% реального рынка для опытных программистов, как вы описываете.По какой-то причине мы слышим в основном о бизнес-модели.Позвольте мне поделиться с вами лакомым кусочком, который я получил из надежного источника.От от 10% до 60% или более реальный риск для безопасности и имущества возникает из-за проблем с транспортным средством, а не из-за взлома, кражи и тому подобного.Вы никогда не услышите призывов "90 дней добывать полезные ископаемые на окружных предприятиях по добыче полезных ископаемых!" для штрафов за нарушение правил дорожного движения, на самом деле большинство людей даже не осознают, что ссылки на дорожное движение являются (N.A.- США.) проступок 4-го класса и фактически может быть классифицирован как таковой.

Мне кажется, вы сделали хороший шаг к какой-то хорошей работе, ...