The DOORS StringTable - Unveiled

One of the last mysteries of DXL unveiled - the DOORS string table. Despite my earlier attempts to discuss the string table away (https://www.ibm.com/developerworks/forums/thread.jspa?messageID=14549758) I now publish the code, that will allow you to check for DXL programs for string table littering or just roam around the DOORS string table to find all funny things that are in there.

Okay, so first what is a string table and what is it good for? DXL has no way of freeing a string, once it is created. In C a string is allocated as a character array or by allocating some memory for it. Then the program needs to explicitly free the string once it does not need it anymore, so the memory is not leaked. So in DXL there is no delete (string) function in DXL. So one would think that a DXL program keeps track of the strings in creates, and when it ends it 'garbage collects' the strings and frees the memory. But in that case, the string created by the DXL program must not be used anywhere in the DOORS client anymore. That means, that DOORS would very strictly need to track where a string comes from, from DXL or from an internal function. Imagine you write a string to a DOORS attribute and the client would just take that string without copying it. When the DXL program would end and the string would be freed, then suddenly the module would refer to an invalid memory - crashs and data corruption would then occur. Maybe it is kind of a legacy problem, that strings from DXL are freely used in the internal DOORS client and separating the DXL strings from the internal string is too problematic. Additionally DOORS has this complex design, where a global DXL context is lingering around while several 'child' contexts of DXL programs you launch, DXL Layouts, eval_ code, DXL triggers, DXL GUIs are active somewhere - so that tracking string usage in the whole source code of DOORS, including all foreign libraries included is just to hard.

So, freeing the strings after DXL ends might be problematic. So one use for a string table would be to make sure that each string stays alive, but to avoid completely littering the memory each string is stored only once. If a string already exists, the DXL program will just get a reference to that string, that has already been stored. For this DOORS would need a data structure, where it can quickly check if a string already exists and if not, store it there. And this data structure is the string table. (By the way, this is only speculation. I still find it highly unusual. Anyway at some point one needs to accept that a string table exists for whatever reason.)

Alright, lets take a look at how the DOORS string table is constructed. You can think of the string table like an array of exactly 52021 buckets/bins where each bucket/bin stores a list of strings. A bucket can also be empty if it contains no strings.
 

Bucket    String List 
[1]       "abcd" -> "hello" -> "world"
[2]       empty 
[3]       "orly?" 
...
[52021]   "yarly!" -> "noway!"

So why and how are the strings assigned to buckets? Well the main problem is, that DOORS would need to check if a string already exists in the string table. One could think, well lets keep a sorted list of strings, then we can find if a string is already in there very fast. Well the problem is, that if you want to add a new string in such a list, then you would need to shift the strings in the list to insert a new string, which is time consuming. Another idea would be to use a Skip list. The problem with skip lists is, that they do a full string compare. For long strings this is extremely inefficient. So the string table works differently. Given a string like "Hello World!" a (hash) function will calculate the bucket/bin for that string. This function works extremely fast (its like a checksum). Once you know the bucket for that string in the string table, you only need to search inside the bucket if that "Hello World!" string already exists in there. If not, you just add it to the end of the list of the bucket. So imaging in the above example we would calculate the bucket 3 for the string "Hello World!". Then we would search the bucket for that string - we notice that "orly?" is the only string in there, and "Hello World!" is not in there yet. Therefore we add it to bucket three.

Bucket    String
...
[3]       "orly?" -> "Hello World"
...

Now notice that we already have two strings in the bucket 3. If more and more strings go to bucket 3 then the time for checking if a string is in there will get longer and longer. This is called a clash. So if only one string is in a bucket you got no clash. If there is more, you have a clash, that will slow down your string table. So you can see one of the main goal of the function that assigns buckets is, that it will distribute the strings evenly in the buckets.

Imagine the following code:

string s = "1" 
int i; for (i = 0; i < 100000; i++) s = s "1"

This program will create 100001 different strings "1", "11", "111", ... So if those string would all go to the same bucket, then this code would slow down drastically, since the time to check each string, if it is already in the string table, would become longer and longer. If the strings are distributed totally evenly in the buckets, then the buckets will have a maximum of 2 strings each. This means you would have no slowdown, since checking if the string is already present is still very efficient.

So as general rules for DXL you can take with you:

• The more clashes you have in your string table the slower will DXL become
• large strings in the string table will also slow DOORS down, since the string comparison that takes place will take a longer time, depending on the efficiency of the string compare.

Great, so now you know what the string table is and how it works. Take the attached code and explore for yourself. What I found out by now is, that at least in DOORS 8 / 9 there seems to be a mechanism for freeing DXL strings. If you run the following code multiple times, you will see, that at the next start of the DXL scripts, the number of entries in the string table are back to the value before you started the DXL script:

#include <petools.inc>
#include <stringTable.inc>
 
printStringTable () 
 
string s = "1" 
 
// lets litter the string table
int i; for (i = 0; i < 1000; i++) s = s "1"
 
printStringTable () // 1000 strings have been created.

Now when we pass that string to a DOORS perm now:

#include <src/test/core/petools.inc>
#include <src/test/core/stringTable.inc>
 
printStringTable () 
 
string s = "1" 
 
// lets litter the string table
int i; for (i = 0; i < 1000; i++) {
    s = s "1"
    // pass the string to the richText perm will persist the string
    richText s  
    // passing it to the length perm will not persist the string 
    // length s
 
}
 
printStringTable ()

Then we will find, that the second time we start the script, the string table count will not rise anymore since all strings have been persisted. The good thing is, that as long as we really create the same strings, the string count and the clashes will not rise any more, no matter how often we start the script.

This shows, that DOORS does a cleanup and strings will only be forever in the string table, when you pass them to certain perms. Which perms are those? Find out for yourself! I have no idea. I know that stringOf (Buffer) will do that.

Regards, Mathias

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

Re: The DOORS StringTable - Unveiled
Doug.Zawacki - Thu Oct 25 09:22:09 EDT 2012

Re: The DOORS StringTable - Unveiled
Doug.Zawacki - Thu Oct 25 09:38:04 EDT 2012

Update, After reviewing the code I modified the lines below which doesn't fail.

if ((doorsInfo infoVersion)[0] == '9') // changed from 8 to 9 and it works
{
  p = createPEFile 0x400000 
} 
else 
{
  p = createPEFile 0x10000000
}

Is it safe to assume the address you are passing into createPEFile is just some random address to place your PEFile struct at?

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Fri Oct 26 03:35:55 EDT 2012

if ((doorsInfo infoVersion)[0] == '9') // changed from 8 to 9 and it works
{
  p = createPEFile 0x400000 
} 
else 
{
  p = createPEFile 0x10000000
}

Re: The DOORS StringTable - Unveiled
SystemAdmin - Mon Oct 29 09:42:46 EDT 2012

I'd also like to thank you for posting this.
I was on holiday when you posted it so I didn't see it until the the first reply bumped it up the forum.
So the 'string table' is really just a hash table of strings which 'some' functions cause to persist.

I've tried these so far:

// Persist
    // string ::[] (Buffer, Range_)
    // string ::.. (Buffer, string)
    // string stringOf(Buffer)
    // richText(string)
// No Persist
    // tempStringOf(Buffer)

Re: The DOORS StringTable - Unveiled
llandale - Mon Oct 29 14:12:38 EDT 2012

// Persist
    // string ::[] (Buffer, Range_)
    // string ::.. (Buffer, string)
    // string stringOf(Buffer)
    // richText(string)
// No Persist
    // tempStringOf(Buffer)

Since the string returned from tempStringOf(Buffer) does not persist then you must dispose of it immediately; where "immediately" means before changing or deleting the Buffer. Usually this means:

• compare it to something else
• display on a dialog
• assign to an obj.attr value
• write it to a file.

-Louie

tempStringOf(Buffer) does not respect the "length(Buffer, int)" perm. Below results show "L4" differences.

Buffer buf = create()
 
void PrintIt(string Label)
{  
   print Label "\t" (tempStringOf(buf) == stringOf(buf)) "\t[" tempStringOf(buf) "]\t<">\n"
}
 
buf = "ABCDEFG";      PrintIt("init")
buf += "xyz";         PrintIt("xyz")
length(buf, 4);         PrintIt("L4")
buf     = "";         PrintIt("erase")
buf += "abcdefg";             PrintIt("abc")
buf += "tuv";         PrintIt("tuv")
setempty(buf);          PrintIt("empty")
/*      Results:
init    true    [ABCDEFG]       <ABCDEFG>
xyz     true    [ABCDEFGxyz]    <ABCDEFGxyz>
L4      false   [ABCDEFGxyz]    <ABCD>
erase   true    []      
abc     true    [abcdefg]       <abcdefg>
tuv     true    [abcdefgtuv]    <abcdefgtuv>
empty   true    []      */

Re: The DOORS StringTable - Unveiled
Doug.Zawacki - Mon Oct 29 14:20:25 EDT 2012

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Thu Nov 01 07:26:54 EDT 2012

Buffer buf = create()
 
void PrintIt(string Label)
{  
   print Label "\t" (tempStringOf(buf) == stringOf(buf)) "\t[" tempStringOf(buf) "]\t<">\n"
}
 
buf = "ABCDEFG";      PrintIt("init")
buf += "xyz";         PrintIt("xyz")
length(buf, 4);         PrintIt("L4")
buf     = "";         PrintIt("erase")
buf += "abcdefg";             PrintIt("abc")
buf += "tuv";         PrintIt("tuv")
setempty(buf);          PrintIt("empty")
/*      Results:
init    true    [ABCDEFG]       <ABCDEFG>
xyz     true    [ABCDEFGxyz]    <ABCDEFGxyz>
L4      false   [ABCDEFGxyz]    <ABCD>
erase   true    []      
abc     true    [abcdefg]       <abcdefg>
tuv     true    [abcdefgtuv]    <abcdefgtuv>
empty   true    []      */

I never heard of a large memory aware version of DOORS. Therefore I have no idea on how to detect this version. It seems that it will locate the DOORS.exe at 0x10000000. If you find out on how to detect this DOORS version from DXL code, feel free to post it ;-)

@Louie: tempStringOf is a case of its own. It will return a string that points to the string memory of the buffer. This memory should be stable as long you do not do any changes to the buffer, but that is not proven. However the important point that I wanted to make in my post is, that NOT ALL strings you create in DXL will be in the string table forever.

• There are functions that will create a temporary string table entry (string concatenation), that will be removed from the string table after the DXL ends
• There are perms that will create a permanent string table entry (e.g. string stringOf(Buffer))
• and well ... tempStringOf will of course not create a real string at all, it only returns a type casted buffer memory pointer, which will a) as you showed not take into account buffer length b) will become invalid when the buffer reallocates its memory.

So if we would take the work and for every perm in DXL that takes or returns a string would find out, whether it creates no, a temporary or a permanent string table entry, developers could tune their programs for string table optimization. It is probable that all functions returning a new string will create a string table entry. Interestingly substring s0:3 or concatenation s = s "123" will only generate a temporary string table entry. Passing the string to another function that will return a string like utf8 will make the existing string permanent. Interestingly some perms will also create permanent string table entries even though they do not handle strings at all:

For example if a developer does:

#include <c:/tmp/petools.inc>
#include <c:/tmp/stringTable.inc>
 
printStringTable () 
 
Project p 
for p in database do {  }
 
printStringTable ()

Running this code a first time and a second time will show an increase in string table entries the first time, the second time the string table entries will stay at the high level. Therefore the loop created permanent string table entries. My conclusion is that to avoid string table entries of course one has to use Buffers wherever possible - the fact that string operations only produce temporary string table entries is not very useful, since you can do all that with Buffers which produces no string table entries. However the indication that all functions that return a string (except the string operators) produce a permanent string table entry is rather disapointing, because it leaves no way for optimizing. It is clear that eval_ is of no use for those. Therefore it would be interesting to find out, if there is any other function despite the string operations that will only produce temporary string table entries (which would allow optimization using eval_). Additionally it would be interesting if any of the functions that operate on Buffers will create string table residuals.

Regards, Mathias

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

Re: The DOORS StringTable - Unveiled
EHcnck - Wed Sep 24 19:20:27 EDT 2014

Are you able to upload the code again for the string table, I'm unable to download the current version? Thank you.

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Thu Sep 25 04:09:56 EDT 2014

Here you go - but I cannot imagine what problem you got with downloading? The download worked for me ...

Please note, that this (and all other hacky code, like MemoryManagement, etc. ) will not work on DOORS 9.6 (64bit), since all memory offsets changed in there due to the word length increase to 8 bytes and due to massive changes inside the interpreter.

Regards, Mathias

Re: The DOORS StringTable - Unveiled
Wolfgang Uhr - Thu Sep 25 06:28:23 EDT 2014

What do you think, did IBM reduce the problem or did they only paint it with a different color?

Re: The DOORS StringTable - Unveiled
Arlo - Wed Apr 27 05:06:24 EDT 2016

Mathias,

I have tried downloading your stringTable.zip but it appears to be empty.  Given that this was posted 18mths ago I'm not sure whether it has been removed or whether I have an issue at my end.  Are you able to repost it or send it to me somehow.

Thanks

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Wed Apr 27 05:58:36 EDT 2016

I just downloaded the file and it seems to be perfectly fine. This should be some browser or firewall issue on your side. Regards, Mathias

Re: The DOORS StringTable - Unveiled
Arlo - Wed Apr 27 06:41:15 EDT 2016

Problem solved. It looks like it was a compatibility issue with the unzip utility I was using.

Many thanks

Steve

Re: The DOORS StringTable - Unveiled
Twonky - Thu Aug 04 03:51:25 EDT 2016

Since the hacky code does not work on DOORS 9.6 -- is there any replacement? I liked to use that code when running benchmark tests on my DXL code and will miss it now as we're moving on to 9.6.

Cheers,

Rene

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Thu Aug 04 08:01:13 EDT 2016

I ported the PEFile class to 64 bit, but I need to find a more stable way to locate the string table in memory. This is not so easy and I do not know when I can take time for this. If anyone with good reverse engineering skills wants to chime in, feel free to contact me ;-) Regards, Mathias

Re: The DOORS StringTable - Unveiled
Wolfgang Uhr - Thu Aug 04 09:39:58 EDT 2016

Therefore you need a doors licence isn't it?
 

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Thu Aug 04 18:30:20 EDT 2016

I tested on DOORS 9.6.0.0 64 Bit. Usage: 

#include <64bit.inc>
#include <petools.inc>
#include <stringTable.inc>

printStringTable()

Exception or other DXL Error = bad. 

Note: This will not run under any other DOORS version than 9.6 (64 Bit) for now.  Consider this experimental and unfinished.

Re: The DOORS StringTable - Unveiled
Twonky - Mon Oct 31 05:51:33 EDT 2016

#include <64bit.inc>
#include <petools.inc>
#include <stringTable.inc>

printStringTable()

The show just goes on. Is there a solution for DOORS Client 9.6.1.6?

I run into this error condition:

    int stSearch[] = { 0x50545448 }
    int *loc = searchSection(getDOORSPE(), ".data", stSearch)
    if (loc == nullPtr) { error "String Table could not be found!"; halt }

Cheers,
Rene

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Mon Oct 31 08:27:41 EDT 2016

    int stSearch[] = { 0x50545448 }
    int *loc = searchSection(getDOORSPE(), ".data", stSearch)
    if (loc == nullPtr) { error "String Table could not be found!"; halt }

There sure is. Unfortunately I do not have the time to take care of it currently. Therefore I suggest for debugging 64 bit code stay with DOORS 9.6.0 for now, until someone can find a reliable way to locate the string table in memory. If anyone with some reverse engineering skills wants to some instructions for doing this work, contact me. Regards, Mathias

Re: The DOORS StringTable - Unveiled
Gustavo Delfino - Wed Nov 09 10:45:41 EST 2016

Mathias,

Thank you for your effort in helping understand the string table. I am using DOORS 9.6.1.6. Is your tool supposed to work with this version?

When I try to run this:

#include <C:/tmp/64bit.inc>
#include <C:/tmp/petools.inc>
#include <C:/tmp/stringTable.inc>
printStringTable()

I am getting this failure:

-R-E- DXL: <C:/tmp/stringTable.inc:73> String Table could not be found!
-I- DXL: execution halted

Thanks

Re: The DOORS StringTable - Unveiled
Mathias Mamsch - Thu Nov 10 03:05:35 EST 2016

#include <C:/tmp/64bit.inc>
#include <C:/tmp/petools.inc>
#include <C:/tmp/stringTable.inc>
printStringTable()

-R-E- DXL: <C:/tmp/stringTable.inc:73> String Table could not be found!
-I- DXL: execution halted

As I said - I did not find a reliable way for locating the string table in memory yet for 64 bit versions. The modification I posted seems only to locate the string table correctly for DOORS 9.6.0.0. If someone with reverse engineering skills wants to chime in - currently I cannot find any time for the investigations. Regards, Mathias