跨平台虚拟机的C内存管理

6

我曾经提出了一个关于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;

// 这是一个用于显示的辅助函数 void PrintData(Data *pData, DDouble *pResult) { printf("%5.2f + %5.2f = %5.2f\n", pData->A*1.0, pData->B, pResult->D); }

// 一些本地函数 void Plus(char* pParams, char* pResult) { Data *D = (Data *)pParams; // 不需要算术指针操作即可访问数据 DDouble *DD = (DDouble *)pResult; // 返回值同样如此 DD->D = D->A + D->B; PrintData(D, DD); }

执行上述代码后,将返回:

10.00 + 15.30 = 25.30
Result:  25.30
Pointer: 0

这在我的机器上(Linux x86 32位GCC-C99)运行良好。如果其他操作系统/架构也能运行,那就太好了。但是我们必须注意至少三个与内存相关的问题。
1). 数据大小 - 如果我在同一架构上使用相同的编译器编译VM和本地函数,则大小类型应该相同。
2). 字节序 - 同样适用于数据大小。
3). 内存对齐 - 这是一个问题,因为结构体中可能会添加填充字节,但在准备参数堆栈时很难进行同步(除了硬编码外没有其他方法可以知道如何添加填充)。
我的问题是:
1). 如果我知道类型的大小,是否有一种方法可以修改push和pull函数以确切地与结构填充同步? (修改以使编译器像数据大小和字节序问题一样处理它)。
2). 如果我将结构体打包为1(使用#pragma pack(1)); (2.1)性能惩罚是否可接受?以及(2.2)程序稳定性是否存在风险?
3). 填充2、4或8个字节怎么样?哪个对于一般的32位或64位系统最好?
4). 您能指导我参考文献,例如针对x86上的GCC的确切填充算法吗?
5). 是否有更好的方法?
注意:跨平台不是我的最终目标,但我无法抗拒。只要不太丑陋,性能不是我的目标。所有这些都是为了乐趣和学习。
对于我的英语和非常长的帖子,我很抱歉。
提前感谢大家。

2
+1,我希望在 Stack Overflow 上有更多类似这样的问题。 - Tim Post
3个回答

2

侧面评论

以下内容与您提出的问题有些侧面关联,但是...

// 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和pull函数以与结构填充完全同步?(修改为让编译器像Datasize和Endians问题一样处理它)。

没有简单的方法来做到这一点。例如,请考虑:

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

在某些体系结构上(例如32位或64位SPARC),Type1结构将在4字节边界处对齐'number',但Type2结构将在8字节边界上对齐'number'(并且可能在16字节边界上有“long double”)。如果堆栈指针没有适当对齐,则您的“推送单个元素”策略将在推送“byte”值后使堆栈指针增加1-因此,在推送“number”之前,如果堆栈指针不已经适当对齐,则需要将堆栈指针移动3或7。您的VM描述的一部分将是给定类型的所需对齐方式;相应的推送代码将需要在推送之前确保正确的对齐。

2)。 如果我使用#pragma pack(1)按照一个(1)打包结构; (2.1)这样做会产生可接受的性能损失吗?以及(2.2)程序稳定性是否面临风险?

在x86和x86_64机器上,如果打包数据,则会因访问不对齐的数据而产生性能损失。在像SPARC 或PowerPC(per mecki)这样的机器上,您将获得总线错误或类似的东西-您必须以适当的对齐方式访问数据。您可能会节省一些内存空间-以牺牲性能为代价。最好确保性能(这里包括“正确执行而不是崩溃”)的边际成本。

3). 对于一般的32位或64位系统,填充2,4或8如何?哪一个应该很好?

在SPARC上,需要将N字节基本类型填充到N字节边界。在x86上,如果执行相同操作,则会获得最佳性能。

4). 您是否可以指导我查找有关例如在x86上使用GCC的确切填充算法的文档?

您需要阅读手册

5). 是否有更好的方法?

请注意,“Type1”技巧使用单个字符后跟类型可为您提供对齐要求-可能使用来自<stddef.h>的“offsetof()”宏:

offsetof(struct Type1, number)

我不会将数据打包到堆栈上 - 我会使用本地对齐,因为这样可以获得最佳性能。编译器作者不会随意向结构中添加填充;他们之所以这样做是因为它在架构上最有效。如果你认为自己更懂,那么你可能会面临通常的后果 - 程序运行缓慢,有时会失败,并且不太可移植。

我也不确定是否应该在操作函数中编写代码以假定堆栈包含结构。我会通过Params参数从堆栈中提取值,知道正确的偏移和类型。如果我推送了一个整数和一个双精度浮点数,那么我会提取一个整数和一个双精度浮点数(或者,也许反过来 - 我会提取一个双精度浮点数和一个整数)。除非你计划使用不寻常的虚拟机,否则很少会有许多参数的函数。


在我的看法中,它并不是“离题”的,而恰恰是楼主所要求的,或者引出了正是被要求的内容。 - Nicholas Jordan
谢谢你的回答:-D。看起来似乎不是很容易实现。我会查看offsetof宏,看看我能做些什么。此外,我不认为我知道如何更好地做到这一点。问题在于VM代码需要将数据传递给一个未知的函数(指的是VM本身,但是编译运行在VM上执行本地函数的代码知道该函数)。这个参数的传递需要被泛化并且容易被本地代码访问(这样可以减少从复杂的访问过程中产生的错误,并且这就是我使用结构的原因)。 - NawaMan
还有一件事要补充,我计划使用这种方式来访问现有的本地库,例如fopen、fputs等。操作符可以直接由虚拟机处理,这是最好的,因为编译器将确保正确的操作。再次感谢您的回答。我会尝试看看如何使用offsetof和其他委托此本地访问工作给编译器的方法。加油!:D - NawaMan
在 PPC 上不会出现总线错误;PPC 可以处理不对齐(PPC 不是 Motorola 68000),只是会损失一些性能。顺便说一下,在 x86 上的性能惩罚相当小,比大多数其他平台要小得多。如果您使用 GCC 打包属性并仅通过结构字段访问结构,则 GCC 会生成代码,确保永远不会发生不对齐读取(例如,分步读取字段而不是一次读取)。 - Mecki

1

有趣的帖子,显示出你已经付出了很多努力。几乎是理想的SO帖子。

我没有准备好的答案,所以请耐心等待。我将不得不问一些更多的问题:P

1)如果我知道类型的大小,是否有一种方法可以修改push和pull函数,使其与结构填充完全同步?(修改让编译器像数据大小和端点问题一样处理它)。

这只是从性能角度考虑吗?您是否计划引入指针以及本机算术类型?

2)如果我通过一个(使用#pragma pack(1))打包结构;(2.1)性能惩罚是否可接受? (2.2)程序稳定性是否会受到威胁?

这是一个实现定义的事情。不能在各个平台上都保证。

3)关于填充2、4或8,怎么样才适合一般的32位或64位系统?

与本机字长匹配的值应该为您提供最佳性能。

4)您能指导我查找确切的填充算法文档,比如针对x86上的GCC?

我脑海中没有想起来的例子。但是我见过类似于this的代码被使用。

请注意,你可以使用GCC来指定变量的属性(它还有一个叫做default_struct __attribute__((packed))的东西,可以关闭填充)。


感谢您的帖子。 :D 1). 嗯,正如我所说,拥有良好的性能是很好的,但我最关心的是会破坏内存。:p 至于指针,如果一切顺利,我肯定会添加进去的。2). 那真是个坏消息。3). 我也这么认为。4). 我会查看链接的。再次感谢 :D - NawaMan

1

这里有一些非常好的问题,其中许多问题会陷入一些重要的设计问题,但对于我们大多数人来说 - 我们可以看到你正在努力实现什么(当我写这篇文章时,dirkgently刚刚发布了,所以你可以看到你正在引起兴趣),我们可以理解你的英语足够好,你正在处理一些编译器问题和一些语言设计问题 - 这使得问题变得困难,但既然你已经在JNI中工作,就有希望...

首先,我会尝试摆脱pragma;许多人,非常多会不同意这一点。关于为什么,请参见D语言对此问题的正当性讨论。另外,在你的代码中有一个16位指针。

这些问题几乎是无穷无尽的,经过深入研究,很可能会让我们陷入反对和内部顽固的境地。如果我可以建议阅读 Kenneth Louden's Home Page以及英特尔架构手册。我有它,我曾试图阅读它。数据结构对齐,以及你提出的许多其他问题都深深地埋藏在历史编译器科学中,很可能会让你陷入不可预见的后果中(俚语或习惯用语)。

话虽如此,下面开始:

  1. C类型大小 指的是哪种类型的大小?
  2. 计算机工程师转型软件工程师 曾经学过微控制器吗?可以看看Don Lancaster的一些作品。
  3. Pascal、Delphi,现在是Java和PHP程序员。 这些语言相对于处理器的基本架构来说有些偏离,尽管很多人会展示或试图展示它们如何用于编写强大而基础的例程。我建议看看David Eck的递归下降解析器,以了解如何开始研究这个问题。此外,Kenneth Louden有一个名为“Tiny”的实际编译器实现。我不久前发现了一个叫做asm dot org的东西……那里提供了非常先进、非常强大的工作可供研究,但要想开始编写汇编语言并打算进入编译器科学领域,需要付出很长时间的努力。此外,大多数架构之间存在不一致的差异。
  4. 访问现有库

有很多库可供选择,Java 有一些不错的库。其他方面我就不太清楚了。一种方法是尝试编写一个库。Java 有一个良好的基础,并为像你这样的人留出了改进的空间。从改进 Knuth-Morris-Pratt 算法或其他算法开始:只要愿意去尝试,就会发现到处都是可以改进的地方。建议查看计算机程序算法目录,当然,还要去参考 NIST 的 算法和数据结构字典

  1. always_inline

不一定,参考 Dov Bulka - 这位工人拥有计算机科学博士学位,并且在时间效率/可靠性等方面是一名熟练的作者,这些领域并不受某些“商业模式”范式的约束,在这些领域中,“哦!那没关系”的问题其实是有关紧要的。

作为结束语,仪器和控制占据了实际编程技能市场的60%以上,正如您所描述的那样。出于某种原因,我们主要听到的是商业模式。让我与您分享一些来自可靠消息来源的内部消息。从车辆问题而非盗窃、失窃等方面,实际安全和财产风险从10%到60%甚至更高。你永远不会听到有人呼吁“在县矿物提取设施挖矿90天!”以应对交通罚单,事实上,大多数人甚至没有意识到交通违章行为是(N.A. - U.S.A.)四级轻罪,实际上可以归类为这种罪行。
听起来您已经朝着一些好的工作迈出了一步...

感谢您的发布。关于16位指针,如果您在谈论堆栈中的指针字段,则它是一个偏移指针。我希望这对堆栈有用。关于内联函数,似乎这是我在启用C99时使内联函数工作的唯一方法。还有,谢谢您提供的链接。 - NawaMan
它会变得太复杂了,我刚刚因为某些事情而受到了打击,这就像让猫跟随发出吱吱声的开罐器一样 - 太多人不会做深入的工作,看看Dov Bulka的书并阅读有关ipp的内容......内联和一堆其他问题只有通过学习编译器科学才能真正显露出来。阅读Dov Bulka的书以及Addison-Wesley专业印记上任何带有“Effective”字样的内容。我们无法通过注释脚本工具传递足够的信息。 - Nicholas Jordan
NawaMan - 我一直在思考这个问题,我想让你做的是获取《现代密码学》(Wenbo Mao著,hp印刷)ISBN:0-13-066943-1的副本,并阅读作者在前言中对事物的看法。大多数图书馆都有找到这本书的方法——这是一家主要硬件供应商的内部出版物。此外,还需要获取《D编程语言》(Andrei Alexandrescu著)Addison-Wesley Professional的副本……我可以看出你的方向,你需要退后一步,重新审视概述。 - Nicholas Jordan
谢谢您,尼古拉斯。我会仔细查看它们的 :-D。 - NawaMan

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接