Wireshark · Wireshark-dev: Re: [Wireshark-dev] [Wireshark-commits] rev 44380: /trunk/epan/ /trunk/epan/: emem.c

[Gerald Combs <gerald@xxxxxxxxxxxxx>]

Attached is a patch that iterates over the key data instead of using
recursion. Valgrind is happier with it but I'm not yet sure it functions
correctly.

On 8/9/12 1:33 PM, mmann78@xxxxxxxxxxxx wrote:
> Does this patch help?  If not, I would consider blaming guids_add_guid
> for not initializing the key member of the emem_tree_key_t structure. 
> Even though I think either would be caught by
> the DISSECTOR_ASSERT_NOT_REACHED macro. Also, are there warning for
> emem_tree_lookup32_array() as well?
> -----Original Message-----
> From: Jeff Morriss <jeff.morriss.ws@xxxxxxxxx>
> To: wireshark-dev <wireshark-dev@xxxxxxxxxxxxx>
> Sent: Thu, Aug 9, 2012 4:06 pm
> Subject: Re: [Wireshark-dev] [Wireshark-commits] rev 44380: /trunk/epan/
> /trunk/epan/: emem.c
> 
> mmann@xxxxxxxxxxxxx <mailto:mmann@xxxxxxxxxxxxx> wrote:
>> http://anonsvn.wireshark.org/viewvc/viewvc.cgi?view=rev&revision=44380
>> 
>> User: mmann
>> Date: 2012/08/09 06:59 AM
>> 
>> Log:
>>  Make emem_tree_*32_array functions non-destructive.
> 
> With this change Valgrind issues many, many warnings as Wireshark starts:
> 
> ==10126== Conditional jump or move depends on uninitialised value(s)
> ==10126==    at 0x6071DEF: emem_tree_insert32_array (emem.c:1887)
> ==10126==    by 0x607874E: guids_add_guid (guid-utils.c:117)
> ==10126==    by 0x62638CE: dcerpc_init_uuid (packet-dcerpc.c:830)
> ==10126==    by 0x69E3061: register_all_protocol_handoffs (register.c:1360)
> ==10126==    by 0x6085CA2: proto_init (proto.c:401)
> ==10126==    by 0x6073565: epan_init (epan.c:113)
> ==10126==    by 0x418AE5: main (tshark.c:963)
> ==10126==
> ==10126== More than 100 errors detected.  Subsequent errors
> ==10126== will still be recorded, but in less detail than before.
> 
> ___________________________________________________________________________
> Sent via:    Wireshark-dev mailing list <wireshark-dev@xxxxxxxxxxxxx <mailto:wireshark-dev@xxxxxxxxxxxxx>>
> Archives:    http://www.wireshark.org/lists/wireshark-dev
> Unsubscribe: https://wireshark.org/mailman/options/wireshark-dev
>              mailto:wireshark-dev-request@xxxxxxxxxxxxx?subject=unsubscribe
> 
> 
> 
> ___________________________________________________________________________
> Sent via:    Wireshark-dev mailing list <wireshark-dev@xxxxxxxxxxxxx>
> Archives:    http://www.wireshark.org/lists/wireshark-dev
> Unsubscribe: https://wireshark.org/mailman/options/wireshark-dev
>              mailto:wireshark-dev-request@xxxxxxxxxxxxx?subject=unsubscribe
> 

Index: epan/emem.c
===================================================================
--- epan/emem.c	(revision 44398)
+++ epan/emem.c	(working copy)
@@ -1841,185 +1841,112 @@
 
 /* insert a new node in the tree. if this node matches an already existing node
  * then just replace the data for that node */
-static void
-emem_tree_insert32_array_local(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
-{
-	emem_tree_t *next_tree;
 
-	if((key[0].length<1)||(key[0].length>100)){
-		DISSECTOR_ASSERT_NOT_REACHED();
-	}
-	if((key[0].length==1)&&(key[1].length==0)){
-		emem_tree_insert32(se_tree, *key[0].key, data);
-		return;
-	}
-
-	next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
-
-	if(key[0].length==1){
-		key++;
-	} else {
-		key[0].length--;
-		key[0].key++;
-	}
-	emem_tree_insert32_array_local(next_tree, key, data);
-}
-
 void
 emem_tree_insert32_array(emem_tree_t *se_tree, emem_tree_key_t *key, void *data)
 {
-	int key_count = 0;
-	emem_tree_key_t *local_key = key,
-					*copy_key;
+	emem_tree_t *insert_tree = NULL;
+	emem_tree_key_t *cur_key;
+	guint32 i, insert_key32;
 
-	if((key[0].length<1)||(key[0].length>100)){
-		DISSECTOR_ASSERT_NOT_REACHED();
-	}
+	if(!se_tree || !key) return;
 
-	/* Make a copy of the keys so the length isn't destroyed */
-	while ((local_key->key != NULL) && (local_key->length != 0)) {
-		key_count++;
-		local_key++;
+	for (cur_key = key; cur_key->length > 0; cur_key++) {
+		if(cur_key->length > 100) {
+			DISSECTOR_ASSERT_NOT_REACHED();
+		}
+
+		for (i = 0; i < cur_key->length; i++) {
+			/* Insert using the previous key32 */
+			if (!insert_tree) {
+				insert_tree = se_tree;
+			} else {
+				insert_tree = lookup_or_insert32(insert_tree, insert_key32, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
+			}
+			insert_key32 = cur_key->key[i];
+		}
 	}
 
-	copy_key = ep_alloc(sizeof(emem_tree_key_t)*(key_count+1));
-	local_key = copy_key;
-	while ((key->key != NULL) && (key->length != 0)) {
-		copy_key->length = key->length;
-		copy_key->key = key->key;
-		key++;
-		copy_key++;
+	if(!insert_tree) {
+		/* We didn't get valid data. Should we return NULL instead? */
+		DISSECTOR_ASSERT_NOT_REACHED();
 	}
 
-	/* "NULL terminate" the key */
-	copy_key->length = 0;
-	copy_key->key = NULL;
+	emem_tree_insert32(insert_tree, insert_key32, data);
 
-	emem_tree_insert32_array_local(se_tree, local_key, data);
 }
 
-static void *
-emem_tree_lookup32_array_local(emem_tree_t *se_tree, emem_tree_key_t *key)
-{
-	emem_tree_t *next_tree;
-
-	if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
-
-	if((key[0].length<1)||(key[0].length>100)){
-		DISSECTOR_ASSERT_NOT_REACHED();
-	}
-	if((key[0].length==1)&&(key[1].length==0)){
-		return emem_tree_lookup32(se_tree, *key[0].key);
-	}
-	next_tree=emem_tree_lookup32(se_tree, *key[0].key);
-	if(!next_tree){
-		return NULL;
-	}
-	if(key[0].length==1){
-		key++;
-	} else {
-		key[0].length--;
-		key[0].key++;
-	}
-	return emem_tree_lookup32_array_local(next_tree, key);
-}
-
 void *
 emem_tree_lookup32_array(emem_tree_t *se_tree, emem_tree_key_t *key)
 {
-	int key_count = 0;
-	emem_tree_key_t *local_key = key,
-					*copy_key;
+	emem_tree_t *lookup_tree = NULL;
+	emem_tree_key_t *cur_key;
+	guint32 i, lookup_key32;
 
 	if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
 
-	if((key[0].length<1)||(key[0].length>100)){
-		DISSECTOR_ASSERT_NOT_REACHED();
-	}
+	for (cur_key = key; cur_key->length > 0; cur_key++) {
+		if(cur_key->length > 100) {
+			DISSECTOR_ASSERT_NOT_REACHED();
+		}
 
-	/* Make a copy of the keys so the length isn't destroyed */
-	while ((local_key->key != NULL) && (local_key->length != 0)) {
-		key_count++;
-		local_key++;
+		for (i = 0; i < cur_key->length; i++) {
+			/* Lookup using the previous key32 */
+			if (!lookup_tree) {
+				lookup_tree = se_tree;
+			} else {
+				lookup_tree = emem_tree_lookup32(lookup_tree, lookup_key32);
+				if (!lookup_tree) {
+					return NULL;
+				}
+			}
+			lookup_key32 = cur_key->key[i];
+		}
 	}
 
-	copy_key = ep_alloc(sizeof(emem_tree_key_t)*(key_count+1));
-	local_key = copy_key;
-	while ((key->key != NULL) && (key->length != 0)) {
-		copy_key->length = key->length;
-		copy_key->key = key->key;
-		key++;
-		copy_key++;
-	}
-
-	/* "NULL terminate" the key */
-	copy_key->length = 0;
-	copy_key->key = NULL;
-
-	return emem_tree_lookup32_array_local(se_tree, local_key);
-}
-
-static void *
-emem_tree_lookup32_array_le_local(emem_tree_t *se_tree, emem_tree_key_t *key)
-{
-	emem_tree_t *next_tree;
-
-	if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
-
-	if((key[0].length<1)||(key[0].length>100)){
+	if(!lookup_tree) {
+		/* We didn't get valid data. Should we return NULL instead? */
 		DISSECTOR_ASSERT_NOT_REACHED();
 	}
-	if((key[0].length==1)&&(key[1].length==0)){ /* last key in key array */
-		return emem_tree_lookup32_le(se_tree, *key[0].key);
-	}
-	next_tree=emem_tree_lookup32(se_tree, *key[0].key);
-	/* key[0].key not found so find le and return */
-	if(!next_tree)
-		return emem_tree_lookup32_le(se_tree, *key[0].key);
 
-	/* key[0].key found so inc key pointer and try again */
-	if(key[0].length==1){
-		key++;
-	} else {
-		key[0].length--;
-		key[0].key++;
-	}
-	return emem_tree_lookup32_array_le_local(next_tree, key);
+	return emem_tree_lookup32(lookup_tree, lookup_key32);
 }
 
 void *
 emem_tree_lookup32_array_le(emem_tree_t *se_tree, emem_tree_key_t *key)
 {
-	int key_count = 0;
-	emem_tree_key_t *local_key = key,
-					*copy_key;
+	emem_tree_t *lookup_tree = NULL;
+	emem_tree_key_t *cur_key;
+	guint32 i, lookup_key32;
 
 	if(!se_tree || !key) return NULL; /* prevent searching on NULL pointer */
 
-	if((key[0].length<1)||(key[0].length>100)){
-		DISSECTOR_ASSERT_NOT_REACHED();
-	}
+	for (cur_key = key; cur_key->length > 0; cur_key++) {
+		if(cur_key->length > 100) {
+			DISSECTOR_ASSERT_NOT_REACHED();
+		}
 
-	/* Make a copy of the keys so the length isn't destroyed */
-	while ((local_key->key != NULL) && (local_key->length != 0)) {
-		key_count++;
-		local_key++;
+		for (i = 0; i < cur_key->length; i++) {
+			/* Lookup using the previous key32 */
+			if (!lookup_tree) {
+				lookup_tree = se_tree;
+			} else {
+				lookup_tree = emem_tree_lookup32_le(lookup_tree, lookup_key32);
+				if (!lookup_tree) {
+					return NULL;
+				}
+			}
+			lookup_key32 = cur_key->key[i];
+		}
 	}
 
-	copy_key = ep_alloc(sizeof(emem_tree_key_t)*(key_count+1));
-	local_key = copy_key;
-	while ((key->key != NULL) && (key->length != 0)) {
-		copy_key->length = key->length;
-		copy_key->key = key->key;
-		key++;
-		copy_key++;
+	if(!lookup_tree) {
+		/* We didn't get valid data. Should we return NULL instead? */
+		DISSECTOR_ASSERT_NOT_REACHED();
 	}
 
-	/* "NULL terminate" the key */
-	copy_key->length = 0;
-	copy_key->key = NULL;
+	return emem_tree_lookup32_le(lookup_tree, lookup_key32);
 
-	return emem_tree_lookup32_array_le_local(se_tree, local_key);
 }
 
 /* Strings are stored as an array of uint32 containing the string characters