Friday, November 18, 2011

Memory leaks when implementing GetHashCode()

 

Hi All,

If you have been following my blog then you know I am trying to list as many possible memory leaks in managed code as possible. Most developers, when told about the garbage collection mechanism in .Net, think that memory leaks cannot happen (at least in pure managed code) but as we seen this is not true. The most common case for such memory leaks are static (or singleton events) but as I shown before, using lambda expressions incorrectly may also cause objects not to be disposed in a timely manner.

We consider a case where a simple object overrides the GetHashCode method to be used in a dictionary later. In our case the object (named Person) will be used as a key for a much larger data chunk (named LargeDataObject). Being a seasoned .Net developer I know that if I override the GetHashCode method I also have to override the Equals method and so I do:

  1. public class Person
  2. {
  3.   public int Age { get; set; }
  4.  
  5.   public override int GetHashCode()
  6.   {
  7.     return Age.GetHashCode();
  8.   }
  9.  
  10.   public override bool Equals(object obj)
  11.   {
  12.     if (!(obj is Person))
  13.       return false;
  14.  
  15.     return (obj as Person).Age == this.Age;
  16.   }
  17. }

In my implementation lies the key to the memory leak (pun intended). We examine the following use of the person class:

  1. Dictionary<Person, LargeDataObject> table = new Dictionary<Person, LargeDataObject>();
  2. Person p1 = new Person() { Age = 10 };
  3. table.Add(p1, new LargeDataObject());
  4.  
  5. Console.Out.WriteLine("Contains P1(10) = {0}", table.ContainsKey(p1));

So far so good, this application would print : Contains P1(10) = True

But now I add the following code:

  1. p1.Age = 20;
  2. Console.Out.WriteLine("Contains P1(20) = {0}", table.ContainsKey(p1));

I changed the age of the person thus changing the hash code of person instance. The GetHashCode and the Equal methods are still in sync but now p1 sits in the wrong bucket within the dictionary! For this case the application would print out : Contains P1(20) = False

In fact you can get to the original p1 instance only by iterating over the keys of this dictionary (but lets face it, you didn’t use dictionary in the first place to iterate over all the keys). What you probably have is something like this in your code:

  1. Person p2 = new Person(){Age=10};
  2.       LargeDataObject dataObject = new LargeDataObject();
  3.       if (table.ContainsKey(p2))
  4.         table[p2] = dataObject;
  5.       else
  6.         table.Add(p2, dataObject);

If we run this code after the previous code then another person (and most importantly LargeDataObject) will be added to the dictionary. This would happen if I try to add a new Person with Age = 20 because of what MSDN tells us (quite correctly) to do:

“If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.”

What happens when you look for a Person with Age = 10: The dictionary goes to the bucket where the hash code is 10 and looks there. It finds p1 and checks if it equals to the current person. The age of p1 is 20 so the current person is not equal p1. Nothing found.

What happens when you look for a Person with Age = 20: The dictionary goes to the bucket where the hash code is 20 and looks there. It finds no items. Nothing found.

Conclusion: If you are implementing GetHashCode and Eqauls make sure they do not depend on mutable properties of an object or this object (if used in a hash based collection) may never be disposed or reached through your code.

Thanks for reading,

Boris.

Friday, November 4, 2011

Writing an Extensible Application – Part 3: IC#Code Addin Tree

 

Hi All,

This is the third part of my extensibility series and this time I would like to describe an open source extensibility mechanism which is part of SharpDevelop called the Addin Tree. To use the Addin Tree all you have to do is to download the latest version of SharpDevelop and reference the file ICSharpCode.Core.dll in your project. For my example I will be using the dll from version 4.1 which can be downloaded from the site.

The Addin Tree (AT for short) is a very simple mechanism based on XML files called Addins. Each Addin file may contain one or more Path elements which maps all child elements of the Path element to a specific node within the AT. The AT is a tree data structure where each node may contain one or more Codons that describe any user data. Each node in the tree can be reached using a path statement of the form “A/B/…/C/D” where A,B,C are the ids of the nodes to pass on the way to node D which is represented by this statement. When the application loads it can read any number of Addins and build the tree. Later, you may access any node of the tree and Build the codons within this node. Each codon is built by a Doozer which is mapped to that specific codon (the core mechanism provides some basic doozers to build elementary program elements).

The addins are defined using XML files that contain the following elements:

  • Root Addin Element which contains some general data on the addin.
  • The Manifest Element which describes the addin file.
  • The Runtime Element which defines the Doozers and the assemblies needed in the addin.
  • The Paths Elements which contain the codons of the addin.

Here is an example of such an Addin file (from SharpDevelop):

  1.         <AddIn name= "AddInScout"
  2.              author= "Satguru P Srivastava"
  3.           copyright= "prj:///doc/copyright.txt"
  4.                 url= "http://home.mchsi.com/~ssatguru"
  5.        description = "Display AddIn Information"
  6.        addInManagerHidden = "preinstalled">
  7.  
  8.   <Manifest>
  9.     <Identity name = "ICSharpCode.AddInScout"/>
  10.   </Manifest>
  11.  
  12.   <Runtime>
  13.     <Import assembly="AddInScout.dll"/>
  14.   </Runtime>
  15.  
  16.   <Path name = "/Workspace/Tools">
  17.     <MenuItem id = "ShowAddInScout"
  18.                   label = "AddIn Scout"
  19.                   class = "AddInScout.AddInScoutCommand"/>
  20.   </Path>
  21. </AddIn>

The Balls Game

Back to our example… To use the Addin tree extensibility I made some small changes. First, the build process now builds the entire game into a single root Bin folder and all the Addins into an Addins folder. This structure is needed for the Runtime mechanism of the AT. I created a main addin file for the application called Main.addin which contains the definition of the three Doozers I will use to support the extensibility of my application. The doozers are defined in the Interfaces project as internal classes and they contain some logic to build the required class from the codon definition. The main addin file looks like this:

  1. <AddIn name="Balls Main Addin"
  2.        author="Boris Kozorovitzky"
  3.        description="The main addin of the game"
  4.        addInManagerHidden="preinstalled">
  5.  
  6.   <Manifest>
  7.     <Identity name="MainAddin"/>
  8.   </Manifest>
  9.  
  10.   <Runtime>
  11.     <Import assembly=":BallsInterfaces">
  12.       <Doozer name="Collider" class="BallsInterfaces.Doozers.ColliderDoozer"/>
  13.       <Doozer name="Mover" class="BallsInterfaces.Doozers.MoverDoozer"/>
  14.       <Doozer name="Drawer" class="BallsInterfaces.Doozers.DrawerDoozer"/>
  15.     </Import>
  16.   </Runtime>
  17. </AddIn>

One important thing to notice here is that the Import element tells the extensibility mechanism where to find the doozers. In this case I use the “:” syntax to tell it that the required assembly is in the Bin folder. You will understand why this is important next.

The extensibility Addin may sit anywhere in the Addin folder (any directory structure) and it looks like this:

  1. <AddIn name="Balls Addin"
  2.        author="Boris Kozorovitzky"
  3.        description="Adds some balls to the game"
  4.        addInManagerHidden="preinstalled">
  5.  
  6.   <Manifest>
  7.     <Identity name="AddinExtensibility"/>
  8.   </Manifest>
  9.  
  10.   <Runtime>
  11.     <Import assembly=":BallsInterfaces"></Import>
  12.     <Import assembly="AddinExtensibility.dll"></Import>
  13.   </Runtime>
  14.  
  15.   <Path name="/Balls/Colliders">
  16.     <Collider type="AddinExtensibility.BasicCollider"></Collider>
  17.     <Collider type="AddinExtensibility.StopperCollider"></Collider>
  18.   </Path>
  19.  
  20.   <Path name="/Balls/Movers">
  21.     <Mover type="AddinExtensibility.BasicMover"></Mover>
  22.     <Mover type="AddinExtensibility.ParabolicMover"></Mover>
  23.  
  24.   </Path>
  25.  
  26.   <Path name="/Balls/Drawers">
  27.     <Drawer type="AddinExtensibility.BasicDrawer" fill="Yellow"></Drawer>
  28.       <Drawer type="AddinExtensibility.BlinkerDrawer"></Drawer>
  29.  
  30.   </Path>
  31.  
  32. </AddIn>

Note that the import section references the Dll where all the classes are defined – AddinExtensibility.dll and the BallsInterfaces assembly. The main section of the addin contains three Path elements (I chose the path randomly to something logical) and each path contains Codon which can be built by a specific doozer (see doozer mapping in the main addin file). The collider doozer code will reveal the nice trick which the import does for us:

  1. internal class ColliderDoozer:IDoozer
  2. {
  3.   public object BuildItem(BuildItemArgs args)
  4.   {
  5.     string stringType = args.Codon.Properties["type"];
  6.     object result = args.AddIn.CreateObject(stringType);
  7.     return result;
  8.   }
  9.  
  10.   public bool HandleConditions
  11.   {
  12.     get { return false; }
  13.   }
  14. }

The AT mechanism will call the BuildItem method on any codon which is mapped to that doozer. In this case I expect the element to have a “type” attribute where the type of the object is written. Now that the type is resolved I can call the CreateObject method which will do the magic for us and find the correct type from the assemblies referenced in the Runtime section and thus returning the correct item each time. To show you how the extensibility mechanism can work for us I added two editable properties to the BasicDrawer type. The Drawer doozer calls a new method – Configure which takes the codon and extracts the needed arguments from it. Now we can control the color and the diameter of the basic drawer directly from the addin file!

  1. public class BasicDrawer : IDrawer
  2.   {
  3.     private static double _initialDiameter;
  4.     private static Brush _initialBrush;
  5.  
  6.     public void Initialize(IBall ball)
  7.     {
  8.       ball.Diameter = _initialDiameter;
  9.       ball.Fill = _initialBrush??Brushes.Blue;
  10.     }
  11.  
  12.     public void Tick(IBall ball)
  13.     {
  14.  
  15.     }
  16.  
  17.     public object Clone()
  18.     {
  19.       return new BasicDrawer();
  20.     }
  21.  
  22.  
  23.     public void Configure(ICSharpCode.Core.Codon codon)
  24.     {
  25.       _initialDiameter = 15;
  26.       if (codon.Properties.Contains("diameter"))
  27.       {
  28.         string diameterString = codon.Properties["diameter"];
  29.         double diameter = 15d;
  30.         Double.TryParse(diameterString, out diameter);
  31.         _initialDiameter = diameter;
  32.       }
  33.  
  34.       _initialBrush = null;
  35.       if (codon.Properties.Contains("fill"))
  36.       {
  37.         string fillString = codon.Properties["fill"];
  38.         _initialBrush = (SolidColorBrush)new BrushConverter().ConvertFromString(fillString);
  39.       }
  40.  
  41.     }
  42.   }

In the example I set the color of all the balls created with the BasicDrawer to Yellow but the user may chose to edit this value as he wishes.

The extensibility initialization code changed slightly and now it loads all the addin files from the Addins path:

  1. private void LoadExtensibility()
  2. {
  3.   Assembly applicationAssembly =  Assembly.GetAssembly(GetType());
  4.   string extensibilityPath = System.IO.Path.Combine(System.IO.Path.GetDirectoryName(applicationAssembly.Location), ConfigurationManager.AppSettings["AddinsPath"]);
  5.   string[] addinFiles = System.IO.Directory.GetFiles(extensibilityPath, "*.addin",System.IO.SearchOption.AllDirectories);
  6.   AddInTree.Load(new List<string>(addinFiles), new List<string>());
  7.   foreach (ICollider collider in AddInTree.BuildItems<ICollider>("/Balls/Colliders", null))
  8.     Colliders.Add(new StrategyAdapter(collider));
  9.  
  10.   foreach (IMover mover in AddInTree.BuildItems<IMover>("/Balls/Movers", null))
  11.     Movers.Add(new StrategyAdapter(mover));
  12.  
  13.   foreach (IDrawer drawer in AddInTree.BuildItems<IDrawer>("/Balls/Drawers", null))
  14.     Drawers.Add(new StrategyAdapter(drawer));
  15. }

This extensibility mechanism allows great flexibility and it is simple enough to cover many useful scenarios. In the worst case you can always take a look at the source code to see how things work under the hood. If you are looking for something simple yet powerful to extend your application you should definitely consider the Addin Tree.

Thank you for reading. You can get the new sources from my SkyDrive here:

 

Boris