Hashtable corrupted (.Net bug?)

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

I have a C# Program where multiple threads will operate on a same Hashtable.
This Hashtable is synchronized by using Hashtable.Synchronized(myHashtable)
method, so no further Lock statements are used before adding, removing or
iterating the Hashtable. The program runs in a high workload environment.
After running a few days, now it suddenly catchs this Exception when
inserting a pair of key and object,

stacktrace = System.NullReferenceException: Object reference not set to an
instance of an object.
at Mas.ShortDataTransportService.SdtsMsgKey.Equals(Object obj)
at System.Collections.Hashtable.KeyEquals(Object item, Object key)
at System.Collections.Hashtable.Insert(Object key, Object nvalue, Boolean
add)
at System.Collections.Hashtable.Add(Object key, Object value)
at System.Collections.SyncHashtable.Add(Object key, Object value)
at
Mas.ShortDataTransportService.SdtsManager.InsertIntoPendingAckBuffer(SdtsOutMsgData dataItem)
at Mas.ShortDataTransportService.SdtsManager.HandleSendBufferMsg(Int32&
numSent)
at Mas.ShortDataTransportService.SdtsManager.Transmit()

Here classes under Mas are our self-created classes. It is sure that the
inserted key and object are non-null value, otherwise "ArgumentNullException"
instead of "NullReferenceException" will be caught.
It seems that some key inside the Hashtable has become Null, but how can
this happen? because a key inside a Hashtable can never be null, right? Will
this be a .Net Bug?
 
Ken said:
I have a C# Program where multiple threads will operate on a same Hashtable.
This Hashtable is synchronized by using Hashtable.Synchronized(myHashtable)
method, so no further Lock statements are used before adding, removing or
iterating the Hashtable.
Click to expand...

That's a problem to start with - iteration requires a lock for the
duration of the iteration, otherwise a new value could be inserted
during the iteration, which would break things.

From the docs for Hashtable.Synchronized:

<quote>
Enumerating through a collection is intrinsically not a thread-safe
procedure. Even when a collection is synchronized, other threads could
still modify the collection, which causes the enumerator to throw an
exception. To guarantee thread safety during enumeration, you can
either lock the collection during the entire enumeration or catch the
exceptions resulting from changes made by other threads.
</quote>
 
Hello Ken

From the stack trace you posted, I can see that the exception is thrown in
the Equals method of the Mas.ShortDataTransportService.SdtsMsgKey class. It
seems you are using instances of this class as the key to the hashtable, and
the hashtable would call Equals and GetHashCode methods. The null reference
can be one of the members of the SdtsMsgKey.

The synchronized method will protect the hashtable from being corrupted, but
it is not thread safe. There is the case that Jon mentioned about iterating
the hashtable, but you would get an InvalidOperationException in that case.

There is also the following case:
if(!myHashtable.ContainsKey(myKey))
myHashtable.Add(myKey, myValue);

Although the hashtable may be synchronized using the synchronized method,
another thread can add a pair with the same key between the call to
ContainsKey and Add causing Add to throw an ArgumentException because you
are attempting to insert a duplicate key.

Best regards,
Sherif


Ken said:
I have a C# Program where multiple threads will operate on a same Hashtable.
This Hashtable is synchronized by using Hashtable.Synchronized(myHashtable)
method, so no further Lock statements are used before adding, removing or
iterating the Hashtable. The program runs in a high workload environment.
After running a few days, now it suddenly catchs this Exception when
inserting a pair of key and object,

stacktrace = System.NullReferenceException: Object reference not set to an
instance of an object.
at Mas.ShortDataTransportService.SdtsMsgKey.Equals(Object obj)
at System.Collections.Hashtable.KeyEquals(Object item, Object key)
at System.Collections.Hashtable.Insert(Object key, Object nvalue, Boolean
add)
at System.Collections.Hashtable.Add(Object key, Object value)
at System.Collections.SyncHashtable.Add(Object key, Object value)
at
Click to expand...
Mas.ShortDataTransportService.SdtsManager.InsertIntoPendingAckBuffer(SdtsOut
MsgData dataItem)
 
Hi Sherif,
Thank you for your reply. But from the information, I still can't figure out
the problem. My SdtsMsgKey has no object type inside, the members are either
long or byte, so they can't be null. But I did implement my own GetHashCode
method and Equal method. Here are the implementation:


/// <summary>
/// Serves as a hash function for a particular type,
/// suitable for use in hashing algorithms and data structures like
a hash table.
/// EXPLANATION:
/// ClientID 3 bytes (shift left 3 bytes x 8 bits) bitwise-OR
MsgReference 1 byte
/// Makes 4 bytes exactly an int.
/// </summary>
/// <returns>Hash code</returns>
public override int GetHashCode()
{
return ((int) (ClientID << 24) | (int) MsgReference);
}

/// <summary>
/// Determines whether the specified Object is equal to the current
Object.
/// Required for use in data structures like a hash table.
/// </summary>
/// <param name="obj"></param>
/// <returns></returns>
public override bool Equals(object obj)
{
SdtsMsgKey key = obj as SdtsMsgKey;

return ((this.ClientID == key.ClientID) &&
(this.MsgReference == key.MsgReference));
}

One thing I want to emphasize is that the NullReferenceException happens
after the program running for quite some time. Will that indicate this
problem related to threading issue? But from your description, if the problem
is caused by un-safe Hashtable operation, the exception should be
InvalidOperationException or ArgumentException, but not
NullReferenceException. From the exception trace "at
Mas.ShortDataTransportService.SdtsMsgKey.Equals(Object obj)", I still suspect
the null object is referring to the key that is previously inserted, but not
the one that is going to be inserted because I always created a new key
before I insert the pair of key object:

SdtsMsgKey key = new SdtsMsgKey();
key.ClientID = dataItem.ClientID;
key.MsgReference = dataItem.MsgReference;

PendingAckMsgs.Add(key, dataItem);

But if so, I feel very strange. How can a key in a Hashtable become null?

Thank you for your patience to read this long question.

Best Regards,
Ken
 
Hi Jon,
Thank you very much for your valuable information. Can you look at my reply
to Sherif Elmetainy and give me more suggestion?

Best regards,
weiqin
 
Ken said:
Thank you very much for your valuable information. Can you look at my reply
to Sherif Elmetainy and give me more suggestion?
Click to expand...

Hmm... that does seem very odd. I'll have a look at it more closely
tonight. Do you have a test program which demonstrates the problem
(even after several hours)? Anything to help reproduce it would be
good.
 
Hello

You should add if(key == null) return false; to your Equals method. Because
Equals can be called with a null or an object of different type.
Because your Equals method should do that, I assume that the hashtable
implementation doesn't do that check, because it would be redundant and
would hurt performance, and instead it relies on your Equals implementation
to do that check because it should anyways.

Best regards,
Sherif
 
Hi Sherif,
It is a great suggestion and I will try it. Is it possible to know the
reason why the key in the Hashtable became null after the program running a
long time? Will it be a bug of the .Net framework?

Best regards,
weiqin
 
Hi Jon,
Thank you for your effort. Actually this program is part of our product and
it is running in the product environment. The problem here is we don't know
how to reproduce it. Our suspecion is it could be a bug of .Net Framework
because a Hashtable should not allow a key to be null.

Hope you can find out more indication from the limited information I gave.

Best regards,
Ken
 
Personally, I suspect that there isn't a problem with null key, but rather
with a key of different type. As Sherif mentioned, your Equals function will
crash if it's called with anything else than an object of the same type. The
'as' operator will return null, if the object is of different type, and I
suspect that's the null you're seeing.

Are you absolutely certain that all keys in your hashtable are of the same
type?

HTH,
Stefan
 
Hello

As Jon mentioned it could be another key type that happens to have the same
hash code value not a null key. I don't know if this is possible in your
production application or not, but you can add some diagnostics code to help
you understand the problem better.
if(key == null)
{
if(obj == null)
Trace.WriteLine("Equals method called with a null object");
else
Trace.WriteLine("Equals method called with an object of type " +
obj.GetType().FullName);

return false;
}
Best regards,
Sherif
 
Hi Stefan,
Your suspecion is reasonable, but it is not applicable to our scenario,
because I have made sure that all keys in our hashtable are of the same type.
The only place that inserting key object pair to the Hashtable is

SdtsMsgKey key = new SdtsMsgKey();
key.ClientID = dataItem.ClientID;
key.MsgReference = dataItem.MsgReference;

PendingAckMsgs.Add(key, dataItem);

As we see, a new key SdtsMsgKey is created before interting it into the
Hashtable, so it is not possible to have a different type of key in the
Hashtable.

Regards,
Ken
 
Hi Sherif,
Thank you for your good suggestion, but I don't think it is the root cause
of the current problem for two reasons:

1. As noted in my previous reply, our code will create a new key before
inserting it into the Hashtable. There is no place where a different type of
key is inserted.

2. This NullReferenceException only happened after the application has run
for a long time and under a high workload environment. This indicates that it
is not a obvious code problem.

I am thinking that if this is a bug of the .Net Framwork, the exception
could be created in the following way:
Two threads are operating on the Hashtable. One thread is adding an element
and another is removing an element. As the adding operation will iterate the
existing elements to check for duplicate key (use the Equal method). If now
the adding thread get a reference of an existing element, but the removing
thread happens to remove the element at the same time. So when the adding
thread calls the Equal method, it will pass in a Null reference.

If this is the reason, it is a bug of the .Net framwork because the Add and
Remove method should be synchronized as the Hashtable is Synchronized using
the Synchronized method.

This guessing still can't explain one thing: Each insersion to the Hashtable
will catch the NullReferenceException from some time on, which means the Null
key stay in the Hashtable for a long time.

Do you have any better explaination?

Regards,
Ken
 
Hi Stefan and Jon,
Can you look at my last reply to Sherif? There I provide my gussing on the
reason of the problem.

Regards,
Ken
 
Hello

The race condition you mentioned shouldn't happen if you are adding and
removing items to the the hashtable returned by the Synchronized method.
Note that the original hashtable is still not synchronized.

Hashtable mytable = new Hashtable(); // mytable is not synchronized
Hashtable mysynctable = Hashtable.Synchronized(mytable);

mysynctable.Add(key, item); // will not corrupt hashtable
mytable.Add(key, item); // could corrupt hashtable

Best regards,
Sherif
 
Hi Jon,
I have finally managed to re-produce the problem using my test program. I
paste the program below. Could you please take a look at it? It basically
creates two threads: one adding element to the common Hashtable, and the
other removing element from the Hashtable. The Hashtable is synchronized
using Hashtable.Synchronized(myHashtable). Initially I thought this was the
cause of the problem, but later after I change to use
lock(myHashtable.SyncRoot) before adding or removing element, the problem
still existed, so I suspect this is a bug with the .Net Framework. The
NullReferenceException will happen after the program runing for some time
(within one hour).

//Here is the test program

using System;
using System.Threading;
using System.Collections;
using System.Diagnostics;

namespace HashtableTest
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class HashtableTesting
{
static Hashtable PendingAckMsgs = null;

/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
TextWriterTraceListener myWriter = new
TextWriterTraceListener(System.Console.Out);
Trace.Listeners.Add(myWriter);

Hashtable pendingAckMsgsUnsync = new Hashtable();
PendingAckMsgs = Hashtable.Synchronized(pendingAckMsgsUnsync);

//
// TODO: Add code to start application here
//
Thread addingThread = new Thread(new ThreadStart(AddEle));
Thread removingThread = new Thread(new ThreadStart(RemoveEle));

addingThread.IsBackground = true;
removingThread.IsBackground = true;

addingThread.Start();
removingThread.Start();

Console.ReadLine();
}

static void AddEle()
{
Trace.WriteLine("Start of adding thread.");
try
{
byte refNum = 0;
long clientID = 0;
while (true)
{
SdtsMsgKey key = new SdtsMsgKey();
key.ClientID = clientID;
key.MsgReference = refNum;

PendingAckMsgs.Add(key, "object");

refNum++;
clientID++;

Thread.Sleep(500);
}
}
catch(Exception e)
{
Trace.WriteLine(e.ToString());
}
}

static void RemoveEle()
{
Trace.WriteLine("Start of removing thread.");
try
{
Thread.Sleep(500);

byte refNum = 0;
long clientID = 0;
while (true)
{
SdtsMsgKey key = new SdtsMsgKey();
key.ClientID = clientID;
key.MsgReference = refNum;

PendingAckMsgs.Remove(key);

refNum++;
clientID++;
Thread.Sleep(1000);
}
}
catch(Exception e)
{
Trace.WriteLine(e.ToString());
}
}
}
}


//Here is the self-implemented key class

using System;
using System.Text;

namespace HashtableTest
{
/// <summary>
/// Key for outgoing SDTS messages
/// </summary>
public class SdtsMsgKey
{
/// <summary>
/// Destination ISSI
/// </summary>
public long ClientID
{
get
{
return clientID;
}
set
{
clientID = value;
}
}

/// <summary>
/// Message reference is a unique identifier for the messages to
each destination
/// </summary>
public byte MsgReference
{
get
{
return msgReference;
}
set
{
msgReference = value;
}
}

/// <summary>
/// Serves as a hash function for a particular type,
/// suitable for use in hashing algorithms and data structures like
a hash table.
/// EXPLANATION:
/// ClientID 3 bytes (shift left 3 bytes x 8 bits) bitwise-OR
MsgReference 1 byte
/// Makes 4 bytes exactly an int.
/// </summary>
/// <returns>Hash code</returns>
public override int GetHashCode()
{
return ((int) (ClientID << 24) | (int) MsgReference);
}

/// <summary>
/// Determines whether the specified Object is equal to the current
Object.
/// Required for use in data structures like a hash table.
/// </summary>
/// <param name="obj"></param>
/// <returns></returns>
public override bool Equals(object obj)
{
SdtsMsgKey key = obj as SdtsMsgKey;

return ((this.ClientID == key.ClientID) &&
(this.MsgReference == key.MsgReference));
}

/// <summary>
/// Get the string representation of the object.
/// </summary>
/// <returns>String representation of the object</returns>
public override string ToString()
{
StringBuilder msgString = new StringBuilder();
msgString.AppendFormat("ClientID={0}\n", ClientID);
msgString.AppendFormat("MsgReference={0}\n", MsgReference);
return msgString.ToString();
}

private long clientID = 0;
private byte msgReference = 0;
}
}
 
Hi Stefan,
I have finally managed to re-produce the problem. Could you take a look at
my latest reply to Jon's post? (the 1/12/2005 one)

Regards,
Ken
 
Hi Sherif,
I have finally managed to re-produce the problem. Could you take a look at
my latest reply to Jon's post? (the 1/12/2005 one)

Regards,
Ken
 
It really seems to be a bug in the hashtable! It has nothing to do with the
threads though. All you need to crash it, is the following:

1. Add two distinct objects with hashcode 0
2. Remove one of them
3. Add it again

This causes the Hashtable to send it's internal buckets array to the Equals
comparision function, which is certainly a bug, though it won't show if you
have your Equals function written properly (that is, test if the compared
object is of the same type, or for null after an 'as' cast).

Here's a pretty simple code that shows the problem:

using System;
using System.Collections;

namespace HashtableTest
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class HashtableTesting
{
class TestKey
{
int value;

public TestKey(int value) { this.value = value; }

public override int GetHashCode()
{
return 0; // changing this to anything else than zero removes the
problem
}

public override bool Equals(object obj)
{
TestKey key = obj as TestKey;

// uncommeting this also removes the following also removes the problem
//if (key == null)
// return false;

return value == key.value;
}
}

/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
Hashtable test = new Hashtable();

object key0 = new TestKey(0), key1 = new TestKey(1);

test.Add(key0, "object");
test.Add(key1, "object");
test.Remove(key0);
test.Add(key0, "object");
}
}
}

This is apparently fixed in dotnet 2.0 beta 1 (2.0.40607)

HTH,
Stefan
 
Hello

I disagree that this should be considered a bug in hashtable, since Equals
method should return false if the bucket array is passed. Hashtable
implementation just assumes the Equals method is written properly. If the
hashtable makes the check that the bucket array is being passed before it
calls Equals, the check will be redundant since Equals should do it anyways.
So I think they don't make the check for performance reasons. the
documentation for Object.Equals method explicitly says "Implementations of
Equals must not throw exceptions."

Best regards,
Sherif

Stefan Simek said:
It really seems to be a bug in the hashtable! It has nothing to do with the
threads though. All you need to crash it, is the following:

1. Add two distinct objects with hashcode 0
2. Remove one of them
3. Add it again

This causes the Hashtable to send it's internal buckets array to the Equals
comparision function, which is certainly a bug, though it won't show if you
have your Equals function written properly (that is, test if the compared
object is of the same type, or for null after an 'as' cast).

Here's a pretty simple code that shows the problem:

using System;
using System.Collections;

namespace HashtableTest
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class HashtableTesting
{
class TestKey
{
int value;

public TestKey(int value) { this.value = value; }

public override int GetHashCode()
{
return 0; // changing this to anything else than zero removes the
problem
}

public override bool Equals(object obj)
{
TestKey key = obj as TestKey;

// uncommeting this also removes the following also removes the problem
//if (key == null)
// return false;

return value == key.value;
}
}

/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
Hashtable test = new Hashtable();

object key0 = new TestKey(0), key1 = new TestKey(1);

test.Add(key0, "object");
test.Add(key1, "object");
test.Remove(key0);
test.Add(key0, "object");
}
}
}

This is apparently fixed in dotnet 2.0 beta 1 (2.0.40607)

HTH,
Stefan

Ken said:
Hi Stefan,
I have finally managed to re-produce the problem. Could you take a look at
my latest reply to Jon's post? (the 1/12/2005 one)

Regards,
Ken
Click to expand...
Click to expand...
 
Back
Top