[Home]

Issue of the Implementation # S0791

Brief

Regression in hsearch_r(): Segmentation fault over internal invariant violation

Detailed Description

The modifications of hsearch_r() [1] in glibc-2.9 leads to segmentation fault in some circumstances as a consequence of internal invariant violation.

Description of the hsearch_r() in glibc sources reads:

We use an trick to speed up the lookup. The table is created by hcreate with one more element available. This enables us to use the index zero special. This index will never be used because we store the first hash index in the field used where zero means not used. Every other value means used. The used field can be used as a first fast comparison for equality of the stored and the parameter value. This helps to prevent unnecessary expensive calls of strcmp.

But the new version stores hash value in the 'used' field instead of table index, which can be zero. As a result this invariant can be violated and dereference of uninitialized memory may happen. The example below demonstrates this issue.

[1] http://sourceware.org/bugzilla/show_bug.cgi?id=6966

Problem location(s) in the standard

Linux Standard Base Core Specification 3.1, Chapter 13. Base Libraries, 13.3. Interfaces for libc, 13.3.17. Standard Library, 13.3.17.1. Interfaces for Standard Library, Table 13-22. libc - Standard Library Function Interfaces, descriptions of hcreate(), hsearch() and hdestroy() functions.

Example

#include <stdio.h>
#include <search.h>

int main(void)
{
	char * key[] = { "key2", "gda|yvsp", "" };
	char * data = "data";
	int i;
	
	ENTRY item;
	item.data = data;
	
	hcreate(20);
	
	for(i = 0; i < 3; i++){
		item.key = key[i];
		
		printf("try to insert '%s'='%s'\n", item.key, (char *)item.data);
		hsearch(item, ENTER);
		printf("successful\n");
	}
	
	hdestroy();
	return 0;
}

Possible solutions

Quick fix is:

   hval = len;
   count = len;
   while (count-- > 0)
     {
       hval <<= 4;
       hval += item.key[count];
     }
+  /* Make sure hash value is not zero */
+  if (!hval) hval=1; 
 
   /* First hash function: simply take the modul but prevent zero. */
   idx = hval % htab->size + 1;

But if zero table index is not used special in the new scheme, why do we need to allocate extra element? So, long term solution requires some more investigation.

Component

glibc 2.9

Accepted

Red Hat Bugzilla, 10100

Status

Fixed in glibc-2.10

[Home]