aboutsummaryrefslogtreecommitdiff
path: root/final/runtime/src/extractExternal.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'final/runtime/src/extractExternal.cpp')
-rw-r--r--final/runtime/src/extractExternal.cpp483
1 files changed, 483 insertions, 0 deletions
diff --git a/final/runtime/src/extractExternal.cpp b/final/runtime/src/extractExternal.cpp
new file mode 100644
index 0000000..b3e55b5
--- /dev/null
+++ b/final/runtime/src/extractExternal.cpp
@@ -0,0 +1,483 @@
+/*
+ * extractExternal.cpp
+ */
+
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <stdlib.h>
+#include <string>
+#include <strstream>
+
+/* Given a set of n object files h ('external' object files) and a set of m
+ object files o ('internal' object files),
+ 1. Determines r, the subset of h that o depends on, directly or indirectly
+ 2. Removes the files in h - r from the file system
+ 3. For each external symbol defined in some file in r, rename it in r U o
+ by prefixing it with "__kmp_external_"
+ Usage:
+ hide.exe <n> <filenames for h> <filenames for o>
+
+ Thus, the prefixed symbols become hidden in the sense that they now have a
+ special prefix.
+*/
+
+using namespace std;
+
+void stop(char *errorMsg) {
+ printf("%s\n", errorMsg);
+ exit(1);
+}
+
+// an entry in the symbol table of a .OBJ file
+class Symbol {
+public:
+ __int64 name;
+ unsigned value;
+ unsigned short sectionNum, type;
+ char storageClass, nAux;
+};
+
+class _rstream : public istrstream {
+private:
+ const char *buf;
+
+protected:
+ _rstream(pair<const char *, streamsize> p)
+ : istrstream(p.first, p.second), buf(p.first) {}
+ ~_rstream() { delete[] buf; }
+};
+
+// A stream encapuslating the content of a file or the content of a string,
+// overriding the >> operator to read various integer types in binary form,
+// as well as a symbol table entry.
+class rstream : public _rstream {
+private:
+ template <class T> inline rstream &doRead(T &x) {
+ read((char *)&x, sizeof(T));
+ return *this;
+ }
+ static pair<const char *, streamsize> getBuf(const char *fileName) {
+ ifstream raw(fileName, ios::binary | ios::in);
+ if (!raw.is_open())
+ stop("rstream.getBuf: Error opening file");
+ raw.seekg(0, ios::end);
+ streampos fileSize = raw.tellg();
+ if (fileSize < 0)
+ stop("rstream.getBuf: Error reading file");
+ char *buf = new char[fileSize];
+ raw.seekg(0, ios::beg);
+ raw.read(buf, fileSize);
+ return pair<const char *, streamsize>(buf, fileSize);
+ }
+
+public:
+ // construct from a string
+ rstream(const char *buf, streamsize size)
+ : _rstream(pair<const char *, streamsize>(buf, size)) {}
+ // construct from a file whole content is fully read once to initialize the
+ // content of this stream
+ rstream(const char *fileName) : _rstream(getBuf(fileName)) {}
+ rstream &operator>>(int &x) { return doRead(x); }
+ rstream &operator>>(unsigned &x) { return doRead(x); }
+ rstream &operator>>(short &x) { return doRead(x); }
+ rstream &operator>>(unsigned short &x) { return doRead(x); }
+ rstream &operator>>(Symbol &e) {
+ read((char *)&e, 18);
+ return *this;
+ }
+};
+
+// string table in a .OBJ file
+class StringTable {
+private:
+ map<string, unsigned> directory;
+ size_t length;
+ char *data;
+
+ // make <directory> from <length> bytes in <data>
+ void makeDirectory(void) {
+ unsigned i = 4;
+ while (i < length) {
+ string s = string(data + i);
+ directory.insert(make_pair(s, i));
+ i += s.size() + 1;
+ }
+ }
+ // initialize <length> and <data> with contents specified by the arguments
+ void init(const char *_data) {
+ unsigned _length = *(unsigned *)_data;
+
+ if (_length < sizeof(unsigned) || _length != *(unsigned *)_data)
+ stop("StringTable.init: Invalid symbol table");
+ if (_data[_length - 1]) {
+ // to prevent runaway strings, make sure the data ends with a zero
+ data = new char[length = _length + 1];
+ data[_length] = 0;
+ } else {
+ data = new char[length = _length];
+ }
+ *(unsigned *)data = length;
+ KMP_MEMCPY(data + sizeof(unsigned), _data + sizeof(unsigned),
+ length - sizeof(unsigned));
+ makeDirectory();
+ }
+
+public:
+ StringTable(rstream &f) {
+ // Construct string table by reading from f.
+ streampos s;
+ unsigned strSize;
+ char *strData;
+
+ s = f.tellg();
+ f >> strSize;
+ if (strSize < sizeof(unsigned))
+ stop("StringTable: Invalid string table");
+ strData = new char[strSize];
+ *(unsigned *)strData = strSize;
+ // read the raw data into <strData>
+ f.read(strData + sizeof(unsigned), strSize - sizeof(unsigned));
+ s = f.tellg() - s;
+ if (s < strSize)
+ stop("StringTable: Unexpected EOF");
+ init(strData);
+ delete[] strData;
+ }
+ StringTable(const set<string> &strings) {
+ // Construct string table from given strings.
+ char *p;
+ set<string>::const_iterator it;
+ size_t s;
+
+ // count required size for data
+ for (length = sizeof(unsigned), it = strings.begin(); it != strings.end();
+ ++it) {
+ size_t l = (*it).size();
+
+ if (l > (unsigned)0xFFFFFFFF)
+ stop("StringTable: String too long");
+ if (l > 8) {
+ length += l + 1;
+ if (length > (unsigned)0xFFFFFFFF)
+ stop("StringTable: Symbol table too long");
+ }
+ }
+ data = new char[length];
+ *(unsigned *)data = length;
+ // populate data and directory
+ for (p = data + sizeof(unsigned), it = strings.begin(); it != strings.end();
+ ++it) {
+ const string &str = *it;
+ size_t l = str.size();
+ if (l > 8) {
+ directory.insert(make_pair(str, p - data));
+ KMP_MEMCPY(p, str.c_str(), l);
+ p[l] = 0;
+ p += l + 1;
+ }
+ }
+ }
+ ~StringTable() { delete[] data; }
+ // Returns encoding for given string based on this string table. Error if
+ // string length is greater than 8 but string is not in the string table
+ // -- returns 0.
+ __int64 encode(const string &str) {
+ __int64 r;
+
+ if (str.size() <= 8) {
+ // encoded directly
+ ((char *)&r)[7] = 0;
+ KMP_STRNCPY_S((char *)&r, sizeof(r), str.c_str(), 8);
+ return r;
+ } else {
+ // represented as index into table
+ map<string, unsigned>::const_iterator it = directory.find(str);
+ if (it == directory.end())
+ stop("StringTable::encode: String now found in string table");
+ ((unsigned *)&r)[0] = 0;
+ ((unsigned *)&r)[1] = (*it).second;
+ return r;
+ }
+ }
+ // Returns string represented by x based on this string table. Error if x
+ // references an invalid position in the table--returns the empty string.
+ string decode(__int64 x) const {
+ if (*(unsigned *)&x == 0) {
+ // represented as index into table
+ unsigned &p = ((unsigned *)&x)[1];
+ if (p >= length)
+ stop("StringTable::decode: Invalid string table lookup");
+ return string(data + p);
+ } else {
+ // encoded directly
+ char *p = (char *)&x;
+ int i;
+
+ for (i = 0; i < 8 && p[i]; ++i)
+ ;
+ return string(p, i);
+ }
+ }
+ void write(ostream &os) { os.write(data, length); }
+};
+
+// for the named object file, determines the set of defined symbols and the set
+// of undefined external symbols and writes them to <defined> and <undefined>
+// respectively
+void computeExternalSymbols(const char *fileName, set<string> *defined,
+ set<string> *undefined) {
+ streampos fileSize;
+ size_t strTabStart;
+ unsigned symTabStart, symNEntries;
+ rstream f(fileName);
+
+ f.seekg(0, ios::end);
+ fileSize = f.tellg();
+
+ f.seekg(8);
+ f >> symTabStart >> symNEntries;
+ // seek to the string table
+ f.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
+ if (f.eof()) {
+ printf("computeExternalSymbols: fileName='%s', fileSize = %lu, symTabStart "
+ "= %u, symNEntries = %u\n",
+ fileName, (unsigned long)fileSize, symTabStart, symNEntries);
+ stop("computeExternalSymbols: Unexpected EOF 1");
+ }
+ StringTable stringTable(f); // read the string table
+ if (f.tellg() != fileSize)
+ stop("computeExternalSymbols: Unexpected data after string table");
+
+ f.clear();
+ f.seekg(symTabStart); // seek to the symbol table
+
+ defined->clear();
+ undefined->clear();
+ for (int i = 0; i < symNEntries; ++i) {
+ // process each entry
+ Symbol e;
+
+ if (f.eof())
+ stop("computeExternalSymbols: Unexpected EOF 2");
+ f >> e;
+ if (f.fail())
+ stop("computeExternalSymbols: File read error");
+ if (e.nAux) { // auxiliary entry: skip
+ f.seekg(e.nAux * 18, ios::cur);
+ i += e.nAux;
+ }
+ // if symbol is extern and defined in the current file, insert it
+ if (e.storageClass == 2)
+ if (e.sectionNum)
+ defined->insert(stringTable.decode(e.name));
+ else
+ undefined->insert(stringTable.decode(e.name));
+ }
+}
+
+// For each occurrence of an external symbol in the object file named by
+// by <fileName> that is a member of <hide>, renames it by prefixing
+// with "__kmp_external_", writing back the file in-place
+void hideSymbols(char *fileName, const set<string> &hide) {
+ static const string prefix("__kmp_external_");
+ set<string> strings; // set of all occurring symbols, appropriately prefixed
+ streampos fileSize;
+ size_t strTabStart;
+ unsigned symTabStart, symNEntries;
+ int i;
+ rstream in(fileName);
+
+ in.seekg(0, ios::end);
+ fileSize = in.tellg();
+
+ in.seekg(8);
+ in >> symTabStart >> symNEntries;
+ in.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
+ if (in.eof())
+ stop("hideSymbols: Unexpected EOF");
+ StringTable stringTableOld(in); // read original string table
+
+ if (in.tellg() != fileSize)
+ stop("hideSymbols: Unexpected data after string table");
+
+ // compute set of occurring strings with prefix added
+ for (i = 0; i < symNEntries; ++i) {
+ Symbol e;
+
+ in.seekg(symTabStart + i * 18);
+ if (in.eof())
+ stop("hideSymbols: Unexpected EOF");
+ in >> e;
+ if (in.fail())
+ stop("hideSymbols: File read error");
+ if (e.nAux)
+ i += e.nAux;
+ const string &s = stringTableOld.decode(e.name);
+ // if symbol is extern and found in <hide>, prefix and insert into strings,
+ // otherwise, just insert into strings without prefix
+ strings.insert(
+ (e.storageClass == 2 && hide.find(s) != hide.end()) ? prefix + s : s);
+ }
+
+ ofstream out(fileName, ios::trunc | ios::out | ios::binary);
+ if (!out.is_open())
+ stop("hideSymbols: Error opening output file");
+
+ // make new string table from string set
+ StringTable stringTableNew = StringTable(strings);
+
+ // copy input file to output file up to just before the symbol table
+ in.seekg(0);
+ char *buf = new char[symTabStart];
+ in.read(buf, symTabStart);
+ out.write(buf, symTabStart);
+ delete[] buf;
+
+ // copy input symbol table to output symbol table with name translation
+ for (i = 0; i < symNEntries; ++i) {
+ Symbol e;
+
+ in.seekg(symTabStart + i * 18);
+ if (in.eof())
+ stop("hideSymbols: Unexpected EOF");
+ in >> e;
+ if (in.fail())
+ stop("hideSymbols: File read error");
+ const string &s = stringTableOld.decode(e.name);
+ out.seekp(symTabStart + i * 18);
+ e.name = stringTableNew.encode(
+ (e.storageClass == 2 && hide.find(s) != hide.end()) ? prefix + s : s);
+ out.write((char *)&e, 18);
+ if (out.fail())
+ stop("hideSymbols: File write error");
+ if (e.nAux) {
+ // copy auxiliary symbol table entries
+ int nAux = e.nAux;
+ for (int j = 1; j <= nAux; ++j) {
+ in >> e;
+ out.seekp(symTabStart + (i + j) * 18);
+ out.write((char *)&e, 18);
+ }
+ i += nAux;
+ }
+ }
+ // output string table
+ stringTableNew.write(out);
+}
+
+// returns true iff <a> and <b> have no common element
+template <class T> bool isDisjoint(const set<T> &a, const set<T> &b) {
+ set<T>::const_iterator ita, itb;
+
+ for (ita = a.begin(), itb = b.begin(); ita != a.end() && itb != b.end();) {
+ const T &ta = *ita, &tb = *itb;
+ if (ta < tb)
+ ++ita;
+ else if (tb < ta)
+ ++itb;
+ else
+ return false;
+ }
+ return true;
+}
+
+// PRE: <defined> and <undefined> are arrays with <nTotal> elements where
+// <nTotal> >= <nExternal>. The first <nExternal> elements correspond to the
+// external object files and the rest correspond to the internal object files.
+// POST: file x is said to depend on file y if undefined[x] and defined[y] are
+// not disjoint. Returns the transitive closure of the set of internal object
+// files, as a set of file indexes, under the 'depends on' relation, minus the
+// set of internal object files.
+set<int> *findRequiredExternal(int nExternal, int nTotal, set<string> *defined,
+ set<string> *undefined) {
+ set<int> *required = new set<int>;
+ set<int> fresh[2];
+ int i, cur = 0;
+ bool changed;
+
+ for (i = nTotal - 1; i >= nExternal; --i)
+ fresh[cur].insert(i);
+ do {
+ changed = false;
+ for (set<int>::iterator it = fresh[cur].begin(); it != fresh[cur].end();
+ ++it) {
+ set<string> &s = undefined[*it];
+
+ for (i = 0; i < nExternal; ++i) {
+ if (required->find(i) == required->end()) {
+ if (!isDisjoint(defined[i], s)) {
+ // found a new qualifying element
+ required->insert(i);
+ fresh[1 - cur].insert(i);
+ changed = true;
+ }
+ }
+ }
+ }
+ fresh[cur].clear();
+ cur = 1 - cur;
+ } while (changed);
+ return required;
+}
+
+int main(int argc, char **argv) {
+ int nExternal, nInternal, i;
+ set<string> *defined, *undefined;
+ set<int>::iterator it;
+
+ if (argc < 3)
+ stop("Please specify a positive integer followed by a list of object "
+ "filenames");
+ nExternal = atoi(argv[1]);
+ if (nExternal <= 0)
+ stop("Please specify a positive integer followed by a list of object "
+ "filenames");
+ if (nExternal + 2 > argc)
+ stop("Too few external objects");
+ nInternal = argc - nExternal - 2;
+ defined = new set<string>[argc - 2];
+ undefined = new set<string>[argc - 2];
+
+ // determine the set of defined and undefined external symbols
+ for (i = 2; i < argc; ++i)
+ computeExternalSymbols(argv[i], defined + i - 2, undefined + i - 2);
+
+ // determine the set of required external files
+ set<int> *requiredExternal =
+ findRequiredExternal(nExternal, argc - 2, defined, undefined);
+ set<string> hide;
+
+ // determine the set of symbols to hide--namely defined external symbols of
+ // the required external files
+ for (it = requiredExternal->begin(); it != requiredExternal->end(); ++it) {
+ int idx = *it;
+ set<string>::iterator it2;
+ // We have to insert one element at a time instead of inserting a range
+ // because the insert member function taking a range doesn't exist on
+ // Windows* OS, at least at the time of this writing.
+ for (it2 = defined[idx].begin(); it2 != defined[idx].end(); ++it2)
+ hide.insert(*it2);
+ }
+
+ // process the external files--removing those that are not required and hiding
+ // the appropriate symbols in the others
+ for (i = 0; i < nExternal; ++i)
+ if (requiredExternal->find(i) != requiredExternal->end())
+ hideSymbols(argv[2 + i], hide);
+ else
+ remove(argv[2 + i]);
+ // hide the appropriate symbols in the internal files
+ for (i = nExternal + 2; i < argc; ++i)
+ hideSymbols(argv[i], hide);
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 02:05:59 +0000