本项目为 NYU 《操作系统设计》课程的实现代码。
项目要求见instructions/NYU_lab instruction.pdf
。
(instructions/SCU_TinyLinker instruction.doc
中有部分中文说明)
说明:在本版 TinyLinker 中,由于需要用到字符串,变长数组和字典等数据结构,而自行实现容易出现 BUG,因此直接套用 C++ STL 库中的 std::string
, std::vector
, std::map
类。该变化对 VC++ 6.0 下的编译过程无任何影响。
为组织方便,TinyLinker 中设计了一些数据结构,如下表所示。
结构名 | 说明 |
---|---|
ListItem | 单个 Definition / Use 中(S, R)键值对的抽象 |
TextItem | 单个 Program Text 中(type, word)对的抽象 |
ObjectFile | 单个文件的抽象,包含 Definition List, Use List, Program Text |
SymbolItem | Symbol Table 中单个 Symbol 的抽象,并记录错误信息 |
MapItem | Memory Map 中单个 Word 的抽象,并记录错误信息 |
整个运行过程如下:
processOne()
是 Linker 的第一次遍历,用于将全部文件信息存储到文件列表 g_objectFiles 中,形成拓扑,并在存储过程中构造 Symbol Table;processTwo()
是 Linker 的第二次遍历,用于解释各个 Program Text,根据 Symbol Table 计算绝对地址并重定位符号位置,最终通过调用printToOutputFile()
将结果一次性打印到 output 文件中。
在项目需求文档中,提出了一系列附加需求。针对这些需求,TinyLinker 给出了解决方案:
通过 fscanf
指定数据类型,跳过空格和空行,从而正常读取文件。
If a symbol is multiply-defined, print an error message and use the value given in the first definition.
在第一次遍历构造 Symbol Table 时,插入新 Symbol 前检查该变量是否已经在表中,如果存在,记录错误信息(将 SymbolItem::isDuplicated
置为 true
)。
// fill in symbol table
if (g_symbolTable.find(variableName) == g_symbolTable.end()) {
// do not find duplication
g_symbolTable.insert(
std::pair<std::string, SymbolItem>(
variableName, SymbolItem(g_offset + innerOffset, fileIndex)));
}
else {
g_symbolTable[variableName].isDuplicated = true;
}
在第二次遍历通过 Use List 重定位时,尝试检查变量在 Symbol Table 中是否存在,若不存在,记录错误信息(将 MapItem::isNotDefined
置为 true
)后将 word
重置为 1000。
// handle errors
std::map<std::string, SymbolItem>::iterator tryFindSymbol = g_symbolTable.find(useList[k].variableName);
if (tryFindSymbol == g_symbolTable.end()) {
g_memoryMap[g_offset + currentRefIndex].isNotDefined = true;
g_memoryMap[g_offset + currentRefIndex].word = 1000;
g_memoryMap[g_offset + currentRefIndex].variableName = useList[k].variableName;
continue;
}
else {
// now the symbol is used
tryFindSymbol->second.isUsed = true;
}
参见上方代码,如果变量被使用,则将其 SymbolItem::isUsed
置为 true
。在打印结果时,如果发现某一变量的 isUsed
没有被置为 true
,则输出警告信息。
for (std::map<std::string, SymbolItem>::iterator it = g_symbolTable.begin();
it != g_symbolTable.end();
it++) {
if (!it->second.isUsed) {
fprintf(out, "Warning: %s was defined in module %d but never used.\n",
it->first.c_str(), it->second.definedModule);
}
}
If an address appearing in a definition exceeds the size of the module, print an error message and treat the address given as 0 (relative).
在第一次遍历结束时,读取全部 Definition List 中变量并检查是否超出 Program Text 长度,如果出现该类型变量,记录错误信息(将 SymbolItem::isOutsideModule
置为 true
)后将其 SymbolItem::globalOffset
置为 g_offset
(相对地址 0)。
// check if definition of variables are outside the module
for (int k = 0; k < g_objectFiles.back().definitionList.size(); k++) {
std::string variableName = g_objectFiles.back().definitionList[k].variableName;
if (g_objectFiles.back().definitionList[k].offset
>= g_objectFiles.back().programText.size()
&& g_symbolTable[variableName].isDuplicated == false) {
g_symbolTable[variableName].isOutsideModule = true;
// reset address to zero (relative)
g_symbolTable[variableName].globalOffset = g_offset;
}
}
If an address appearing in a use list exceeds the size of the module, print an error message and treat the address as the sentinel ending the list.
在第二次遍历根据 word 信息跳转到下一个使用变量的地址前,检查其是否超出 Program Text 长度,如果出现该类型变量,记录错误信息(将 MapItem::isOutsideModule
置为 true
)后直接结束该变量的重定位过程。
if (programText[currentRefIndex].word % 1000 >= programText.size()
&& programText[currentRefIndex].word % 1000 != 777) {
// reference address is outside the module
g_memoryMap[g_offset + currentRefIndex].isOutsideModule = true;
break;
}
针对每个被重定位的变量,将其 MapItem::isOnChain
置为 true
。
在打印结果时检查,如果变量的 originalType
不为 E,但其 isOnChain
为 true
,说明其在 Use List 中,打印错误信息。
else if (g_memoryMap[i].originalType != 'E' && g_memoryMap[i].isOnChain == true) {
fprintf(out, " Error: %c type address on use chain; treated as E type.\n", g_memoryMap[i].originalType);
}
同上,在打印结果时检查,如果变量的 originalType
为 E
,但其 isOnChain
为 false
,说明其不在 Use List 中,打印错误信息。
else if (g_memoryMap[i].originalType == 'E' && g_memoryMap[i].isOnChain == false) {
fprintf(out, " Error: E type address not on use chain; treated as I type.\n");
}