1. Field
Embodiments of the invention relate to garbage collection in string tables having strings that are no longer referenced.
2. Description of the Related Art
String interning is a commonly used technique in which a string table is used to reduce the space required for strings and to make string comparisons faster. String interning may be described as a technique of storing one copy of each distinct string value. Each string is replaced with an integer (or pointer) which is associated with that unique string. String comparisons are reduced to single integer comparisons. The space used by many copies of the same string is reduced to the space used by just the single copy in the string table. An interned string table may be described as a string table for which string interning is performed.
Thus, with some techniques, strings may be interned into a string table such that interned references to the same string (or string value) reference the same in-memory instance. That is, the reference refers to the string. In particular, if the integer or pointer for the interned string is stored, that integer or pointer is called a reference. Also, a reference may be described as a handle stored somewhere, but the reference refers to the string. That is, computer code may make use of the string, so the string can not be deleted. While string tables may provide memory and performance advantages, the string tables may overfill with strings (i.e., the string table may run out of space) or the integer type (which could be a 16-bit short word) may run out of codes if there are too many unique strings. This may lead to a denial of service vulnerability if the strings which are interned arrive over a network because an attacker need only send many unique strings to the server until the string table is full or out of codes. As another example, for an XML document having a large number of names, storing the names in a string table may cause the string table to overflow. If used carelessly, a string-table overflow may lead to poor table lookup performance, may exhaust a fixed-size handle pool, or may even exhaust system memory, resulting in performance and/or stability problems.
These problems can be solved with some form of garbage collection of the string table, in which strings which are no longer referenced are discarded.
In environments with manual memory management or when stricter control over the string table size or lifecycle is desired, recovery of unused strings is complex and specialized string table garbage collection may be required. In particular, in the absence of a system-wide module to determine reachability of the string table entries, the string table has to maintain its own data on the strings in use. This can be done with reference counts, but that will incur penalties in performance, and possibly memory, since the string table users will constantly be updating reference counts on the strings, and since such reference-counting mechanisms often depend on heavier-weight structures to deal with the reference-count update. In a system where interned strings or string handles are used extensively and passed around among various modules, the overhead of reference count updates may reduce the performance advantage that the string table provides.
In environments (i.e., platforms, languages, and/or frameworks) that provide native garbage collection, especially those with support for weak references, a well-designed string table may allow its entries to be freed by the system garbage collector, allowing free use of the string table without risking overflow. However, even in environments where native garbage collection is available, a performance-sensitive or memory-sensitive application may want to use lighter-weight references to the strings, such as small integers, or may wish to have greater control over the size of string-table or the life-cycle of the entries. For example, using a smaller fixed-size table may prove to be easier to tune for performance, but may become exhausted before the system garbage collector decides to free the entries. Similarly, using small-integer handles for strings may allow optimization of other handle-keyed tables throughout the system.
With concurrent garbage collection, other processing does not have to stop while garbage collection is underway. However, with existing garbage collection techniques, none are completely concurrent. For example, some existing garbage collection techniques lock the root set (i.e., the stack) during part of the garbage collection.
In a distributed environment having multiple nodes, memory addresses can not be used as the integer keys because the various nodes do not share the same main memory or virtual memory address spaces. Thus, the nodes can not allocate an entry in the string table for a new string without first synchronizing and checking that no other nodes have already allocated a string at that memory location. The overhead of synchronizing these memory addresses alone would be high-cost and high-complexity. Some systems run completely separate processes on the various nodes and pass the full strings between nodes. This has the drawback that the optimized data structures used on one node can't be passed between nodes.
Thus, there is a need for improved garbage collection techniques.