Bug 234460

Description Jonathan West 2008-05-28 14:29:33 EDT

There are four hashtable.c implementations in the agent controller, each of which originated from a file of the same name that was contributed to TPTP by Scapa as part of Perfmon. Three of the four implementations are used by Perfmon soley, while the fourth is provided for use to the AC codebase by the TPTPUtil component.

This HashTable implementation is used in the tptpProcessController, namedPipeTL, sharedMemTL, socketTL, and TPTPAgentCompTL/TPTPClientCompTL through BaseTL.

The HashTable has no fixed size, and grows when a certain load factor is reached (hardcoded to 75% of capacity, initial capacity is 101). 

Unfortunately, the _TPTPUtil version of HashTable.c_ contains a bug in it's tableRehash(...) function: Whenever the hashtable rehashes (after a certain number of entries are added to it) one of its entries is unintentionally dropped from the table. That is, when the HashTable reaches its load factor, the array size of the table is doubled, all entries are rehashed and copied, and in doing so one entry fails to get copied to the new array.

The _original version_ of the TPTP code, and all other implementations _presently_ in use (e.g. PerfMon) look like this:


	for (i = oldCapacity; i-- > 0;) {
		for (old = oldMap[i]; old != NULL; ) {
			(.... rehash code: copy oldMap[i] into newMap ...)
		}
		oldMap[i] = NULL;
	}



The _present version_ of the TPTP hashtable.c file looks like this:

	for (i = oldCapacity-1; i-- > 0;) {
		for (old = oldMap[i]; old != NULL; ) {
			(.... rehash code: copy oldMap[i] into newMap ...)
		}
		oldMap[i] = NULL;
	}


Notice that 'oldCapacity' has become 'oldCapacity-1'. The contributor misread the for statement semantics: for(a;b;c) { d } will execute a,b,(d,c) and not a,d,c,b. Thus i will start at oldCapacity-2, and not oldCapacity-1 as it should.

The change was made as part of bug 134361 by Kevin P O'Leary at Intel in April 2006. 

Every hashtable in use has an initialCapacity of 101, and will be rehashed when 76 entries are contained in the table. Most of the AC tables will never reach this capacity. However, BaseTL (and therefore ClientCompTL) does not remove connections from its hashtable when they are completed, and thus will inevitably trigger this behaviour after 76 or so Hyades client connections.

Unfortunately, this is the cause of bug 221278, and has also been observed as a contributing factor to other critical/blocker bugs as well.

Because we are late into the TPTP release period, my recommendation to reduce the risk associated with this change is as follows:
1. Fix the rehash function (return oldCapacity to its original value)
2. Increase the capacity of the hashtable, in order to reduce the incidence of the rehash code being called (thereby reducing the inherent risk of late delivery of this change into the code)
3. Trace through the hashtable code, by hand, to ensure correctness.

For the first recommendation, this bug blocks (at least) 1 critical bug, and thus IMHO should be delivered into 4.5.

For the second recommendation, the thinking here is that by increasing the hashtable size ten fold (to 1001, or perhaps more) we nearly eliminate calls to the the rehash function for most users. This is a temporary measure until we can run the corrected rehash function through a full development test pass (post 4.5). There are only ten or so hashtable instances in the agent controller, and this increase would add approximately (4 bytes per pointer * 900 additional entries * 10 entries) 36,000 bytes, or about 35 kilobytes to the agent controller footprint (double on 64-bit systems).

The third is an additional check to ensure code correctness.