.NET Multi threading Basics

Processors today have reached the limits of sheer speed and manufacturers have instead resorted to increasing the number of cores in processors to continue to advance computing power. This is great, but applications must now be written specifically to take advantage of multiple processors by becoming multi threaded. Thankfully, modern frameworks such as .NET make this easy to manage.

The primary issue with multi threading is how to share resources between threads without them interfering with one another. Resources in this case can be file, network connections or even in memory variables. In a single threaded application, we do not need to worry about these issues as only one line of code will be executing at any one time but in a multi threaded application, there may be many. This can cause some new issues that we need to take into consideration when developing multi threaded applications.

Race Conditions

One of the most likely issues you would face when creating a multi threaded application is a race condition. This occurs when one thread is writing to a variable at the same time another thread is reading from it. The result of doing so is undefined. You might read the correct value without issue, or you might read half of the new value being written and half of the old one. This leads to data corruption and unexpected behaviour in your application.

The main objective when making a variable shared between threads “thread safe” is to ensure that only one thread at a time can access it. There are two main ways of doing this, using atomic operations or using some kind of mutual exclusion mechanism.

Atomic Operations

Atomic operations are operations that are carried out in a single step and are guaranteed not to be interrupted mid operation. In the case of a shared variable being written to by one thread and read by another at the same time, the write would be done in a single step. This would make it impossible for the other thread to read half and half of the old and new values. Atomic operations are usually simple operations such as swapping, incrementing etc.

In the .NET framework, these operations are found in the System.Threading.Interlocked class. It contains static methods for adding, decrementing incrementing etc. One of the most useful methods is the “CompareExchange” method. This allows you to check if two objects are equal, and if so, swap the value to a new object. You could use this to check if an object is null and if so, set it to a new value in a single, uninterrupted operation.

Although atomic operations are fast an easy to use, they are limited by their simplicity.  Atomic operations can only perform simple operations such as increment, decrement swap etc. More complex operations that rely upon multiple shared resources require the use of other methods.

The Lock and SyncLock Keywords

One of the greatest aids to multithreading in the .NET framework are the built-in Lock (C#) and SyncLock(VB.NET) keywords. These keywords accept a single object as a parameter. The object can only have a single lock on it at any one time. This provides safety when it comes to multithreading as it ensures that if multiple threads try to place a lock on the same object at the same time, only one will succeed. If another thread does try to place a lock on an already “locked” object, it will be blocked. This means that the thread will cease execution until the object becomes unlocked and it is able to obtain a lock itself.

These keywords are used to surround a block of code that needs to be executed by a single thread at a time. This is also known as a critical section.

Example:

Object o;
lock(o)
{
Console.WriteLine(o.ToString());
}


In the example above, the object “o” is used as the lock object. Only a single thread at a time will be able to access the “WriteLine” piece of code.

One issue with locks however is that they can degrade performance over using atomic operations, the simple reason being that threads sometimes need to wait to access code within a critical section. The locking process as well also involved some additional overhead to manage the lock. This shouldn’t dissuade you from using locks however as often, they can be the only way to achieve true thread safety.

Deadlock

One issue introduced by locking is known as dead lock. Say we have two resources, A and B. If thread 1 comes along and locks A and thread 2 locks object B. So far so good, each thread successfully obtains its lock. Deadlock occurs however if Thread 1 attempts to lock resource B while it still holds A and thread 2 attempts to lock resource A while it still holds B. Both threads are waiting on each other to unlock a resource and will both wait forever. This is deadlock.

One way to reduce the chance of these deadlocks is to have threads only ever hold one lock at a time. This cannot always be avoided however. Another helpful tip is to always lock objects in the same order, so in this example, always locking A first then B would prevent the deadlock occurring.

Concurrent Collections

The .NET framework contains many more thread synchronisation tools but I want to give special mention to a new addition to the .NET 4 framework that can save a lot of trouble when sharing data across threads, the new concurrent collections. These new collections wrap all the thread safety code such as atomic operations  and locks within the collection classes themselves so the developer does not need to worry about it.  These collections can be found in the System.Collections.Concurrent namespace. Using these collections in single threaded applications should be avoided  though as some of them, such as the ConcurrentDictionary use locking to achieve thread safety which does incur a small overhead.

Conclusion

Threading can dramatically improve application performance by taking advantage of more of its CPU resources. It’s also often necessary in applications with user interfaces as waiting for blocking operations like network I/O will freeze the interface if run on the same thread. Care must always be taken with resources that are shared between threads for issues like deadlock and race conditions however. Good stuff!

Diffie Hellman Key Exchange

Traditionally, most people think of cryptography as using a secret password to encrypt and decrypt data. This is known as Symmetric encryption. The same password, or what is known as the key, is used to encrypt and decrypt. The well known AES algorithm is an example of a symmetric encryption algorithm.

Symmetric algorithms are fast and strong, but they have one major weakness, How do you share the secret key with someone whom you want to communicate, without a 3rd party intercepting it?

Diffie Hellman is  a well known algorithm and one of the earliest solutions to this problem. Conceptualised by Ralph Merkle and Published in 1976 by Whitfield Diffe and Martin Hellman, The algorithm allows two parties to share a secret key across an untrusted communications channel.

The algorithm works by both parties generating their own secret and then combining it with another, shared value before transmitting over the network. The operation to separate the two values once combined is extremely expensive to reverse (on current hardware). Using the mixed values, both sides combine the mixed values they received from the other party with their own secret value to arrive at the same value independently. This means they can both arrive at the same secret without ever having to transmit it across the network.

Diffie Hellman is not an encryption algorithm like RSA, it is a Key Exchange algorithm. Its purpose is not to encrypt data but to allow a secret key to be shared between two parties that is then safe to be used as the key to another algorithm such as AES. The confusion sometimes arises when Diffie Hellman is referred to as a public key technology, The public key in this case being the shared value both parties exchange at the beginning of the algorithm. It is not a public key encryption algorithm however, as it it cannot be used to convert a piece of plain text into cypher text.

There are multiple versions of Diffie Hellman but all follow the same basic principle. The original version uses a multiplicative group of integers modulo p, where p is prime and g is a primitive root modulo p. Another variation used Elliptic curves. The elliptic curve variation Diffie Hellman is easily utilised within the .NET framework using the ECDiffieHellmanCng class.

Summary

Use Diffie Hellman if you need to share a secret for use in key generation across an untrusted communications channel. Diffie Hellman alone, cannot be used to encrypt data. It can be used to share a secret key for use in a symmetric algorithm such as AES.

Secure Password Storage for Websites

Secure password storage is extremely important in today’s on-line world and are often the only thing standing between malicious individuals and our private data. It is vital that your applications do everything they can to store passwords as securely as possible or risk losing the trust and confidence of your users.

So what is secure password storage? We want to have some way of storing users passwords that makes it difficult / impossible for an attacker to recover them. I believe that it is the responsibility of every site that stores a user password, no matter how small to keep that password safe at all costs. People today often use the same password over multiple sites and having your site reveal users passwords is guaranteed to lose their trust. The passwords should also be stored in such a way that even the site administrators cannot recover it, giving users confidence that you yourself are not looking at their private credentials.

Encryption

One, often misguided, way of storing user passwords is to use a symmetric encryption algorithm such as AES. When the user creates their account, they supply a password. The password is encrypted using the servers secret key and stored in the database. AES is currently believed to be unbreakable and is used in many popular technologies today such as HTTPS, so you would think this arrangement would be pretty secure? No, The problem is the passwords are still recoverable and this means that there is always a risk they can be stolen by hackers or browsed by nosy administrators.

Hashing

To truly make the passwords unrecoverable, they must be hashed. Hashing is a one way algorithm, it takes a password as input and outputs the hash. There is no possible function that will accept a hash and return a password. When a user creates an account, their password is hashed and stored in the database. When it comes time for them to login, they again supply their password which is passed through the same hashing algorithm. This new hash is then compared against the one stored in the database to check for a match.

One often raised argument for the use of encryption rather than hashing, is how do we recover the users password if they have forgotten it. The answer is, we don’t. The purpose of a password is to allow the user to prove to you who they are (Authenticate). If they do not have this, you must authenticate them in some different way, perhaps by sending them a password reset link with a time limited token attached. Sending them their own password in an email is dangerous as it leaves their password open to eavesdropping. The key point here is that we should never need to tell a user their password. They either know it and authenticate or we go through some other process to authenticate them and allow them to set a new password.

salt

One problem with hashing functions is that the same password when passed through the hash function will always result in the same hash. This makes sense, but think for a moment, if someone were to create a database of all possible passwords and hashes, you would be able to find the password that matches the hash instantly. Indeed, attackers have been using this for many years, or rather a variant of this idea.

Storing all possible hashes and passwords using a lookup table would quickly gobble up a large amount of memory. Instead, an alternative method known as a rainbow table is used, where an initial value is passed to a series of hashing and retry functions to reconstruct an entire chain of hashes and their corresponding passwords. This allows some memory to be saved at the expense of more CPU time to find the matching hash. An explanation of how these tables work can be found here (http://kestas.kuliukas.com/RainbowTables/)

To defeat rainbow tables, we use a special value known as a salt. The salt is a random piece of data whose purpose is to add additional randomness. Salts are combined with the passwords during the hashing process. The resulting hash is then stored in the database with the salt also being stored alongside it. One common mistake is to go to great lengths to keep the salt a secret. Although it won’t do any harm, this is not the purpose of the salt and trying to keep it secret is almost always a wasted effort. The salt must be different for each user and must be random. The point of this salt is that now, when we put the same password and salt through the hashing function, we will get different values because the salt will be different for each user.

Rainbow tables are becoming less prevalent in favour of incredibly fast dictionary / brute force attacks. To keep passwords safe in the modern age, we need to need to go further.

Key stretching

Although hashes are indeed one way, if someone managed to get hold of the password database, they may be able to find out what the original passwords are by guessing. An attacker could perform the same calculation used to generate the hash for a list of words in a dictionary or for every possible combination of letters and characters. This can be done extremely quickly on modern machines (3367 Million per second on a moderately powerful GPU.) It is therefore quite clear that simply hashing the password is not sufficient.

The way to resolve this issue, or at least make it infeasible, is to increase the amount of work required to compute the hash. One simple method is to take the output from the hash function and pass it back into the hash function, generating a second, new hash. You can continue this process for example 10000 and store the final hash.  This is known as key stretching. Each time a user logs in, their password goes through the same 10000 hash cycle and the final hash compared against that stored in the database. This means that for each guess an attacker makes, they will have to calculate the hash 10000 times making it far slower for them to rapidly guess passwords.

Existing password systems

Storing passwords securely is a tricky business and if the previous two issues I’ve been through haven’t scared you off rolling your own, there are many other problems that can befall a poor password hashing scheme.

Thankfully, there are algorithms out there already that prevent us from having to roll our own password hashing system. Two of the most popular algorithms are PBKDF2 and BCrypt. These algorithms take care of combining the salt and password in a secure manner and also allow you to specify a work factor that increases the number of iterations performed, slowing down the process.

PBKDF2 (Password Based Password Derivation Function 2) is an algorithm that is recommended by NIST. It has a built-in implementation in Microsoft’s .NET framework (see Rfc2898DeriveBytes). Unfortunately, this uses the SHA1 hashing algorithm internally which is now considered to be obsolete by NIST themselves. Using PBKDF2 with a stronger hashing algorithm such as SHA256 or SHA512 is advisable.

BCrypt is another key derivation function based on the blowfish cipher. Bcrypt is preferrable to PBKDF2 in some ways due to the fact that PBKDF2 (Especially using SHA1 internally) is extremely efficient to compute on a graphics card. Normal PBKDF2 hashes will be computed on the CPU but in order to make it as difficult as possible for attackers using custom built password cracking machines (look at this one from 2012), a very high iteration count may need to be used, reducing performance for legitimate users. Bcrypt is much less efficient on a GPU because of its memory access requirements meaning it can be run faster for legitimate users while still proving difficult for attackers to brute force.

A newer algorithm named Scrypt is looking very promising in replacing Bcrypt in the future, it exploits the GPU’s memory access weakness even further by requiring more memory to compute. It also makes it more difficult to compute hashes using Field Programmable Gate Arrays (FPGAs) which are currently being used more and more to attack Bcrypt hashes. Scrypt has been around since 2009 and although it hasn’t “stood the test of time” yet, it will have pretty soon.

The conclusion is that you should use one of the pre-existing systems, PBKDF2, Bcrypt or if you want to go bleeding edge, Scrypt.

Summary

DO:

• Use a key derivation function, preferably Bcrypt or alternatively PBKDF2 or Scrypt.
• Use as large a number of iterations (work factor) as possible without affecting legitimate user login performance greatly.

DON’T:

• Store simply the hash of the password
• Have a single salt for all users
• Roll your own hashing algorithm
• Encrypt passwords

LED Lamp

Playing around with electronics, It’s annoying having to squint and move around a tiny electronic part to see the number on it because the manufacturer thought dark grey on black was a good colour scheme.

To try to light the place up a little, I decided to build a lamp using high power LED’s to illuminate the desk while being able to run on batteries so I can use it outdoors as well.

One of the main problems to overcome is being able to supply the correct current to the high power LED’s.  The problem is that as the LED gets hotter, it’s ability to conduct current increases. This results in the LED getting hotter, conducting more current, getting even hotter etc. until it lets out a puff of smoke and dies.

Normally with LED’s, you would use a resistor to limit the current entering the LED and prevent this. This isn’t ideal however as resistors have a fixed value. This means the LED’s brightness would vary with it’s temperature and could either mean the LED is dim before it warms up or that its bright then blows up once it warms.

To solve this, I had to build a small current regulator to constantly monitor and alter the current flow to keep the LED’s burning up. Luckily, I found a really cheap and easy one to make at instructables (http://www.instructables.com/id/Circuits-for-using-High-Power-LED-s/).

The current regulator still isn’t enough though. The LED junction temperature must be kept under 100 degrees centigrade to prevent damage. This means a heat sink had to be attached to the back of the LED’s to draw the heat away from them.

Super Lamp 1.0

I found a cool looking heat sink in an old computer I had lying around and stuck the LED’s to it using some thermally conductive silicone adhesive. This is some nasty stuff, it came in a large padded box alongside a 23 page safety manual. You don’t want to get this stuff on you!

All in all the lamp turned out pretty well. It puts out an extremely bright white light but the bean is more focused than I would have liked. Turning it on doesn’t light an entire room very well but it works well as a desk lamp. Some sort of lampshade for it may help but  that can be a future project.

Parts List

• 2x  4 AA Battery Holders (And batteries)
• 1X TO220AB MOSFET
• 1x 5w 1.2 ohm resistor (1w would do but this was the only power resistor i had)
• 1x 1/2 Watt XXOhm resistor
• 1x BC548B NPN General Purpose Transistor
• 3x LED Oslon Star White 6000K High power LED
• Perf board
• Heat sink
• Thermal bonding epoxy adhesive

Mini Foundry – Failed Attempt 1

Making things from metal looks interesting but expensive. One way I thought would help me do it “on the cheap,” was to melt down metal cans. Luckily, other people have had the same idea and after a quick browse on YouTube, I found what looks like a cheap, easy to make furnace for melting down aluminium cans. Thanks Grant Thompson! (https://www.youtube.com/watch?v=hHD10DjxM1g)

Something about handling molten metal makes me a little nervous, so I did a little research on safety as well before I start building this thing and found a few things not to do:

Concrete is bad, very bad. Avoid dropping molten metal on it and definitely do not build a furnace from it. Heating concrete to the temperatures involved will make the moisture trapped within it turn to steam and explode, violently. Good if you want to embed fragments of concrete and molten metal in your skin.

Crucibles wear out, be ready incase it does. The crucible in the home-made furnace is made of steel. Steel doesn’t melt until roughly 1370 degrees vs aluminium’s 660 degrees, however, the steel is slowly eroded by the molten aluminium and will eventually result in a leak. Don’t go swinging it around over your feet.

On the building, the parts list for the furnace is a little long and personally, I had difficulty finding some of the parts locally.

3Kg Plaster of Paris – Hobbycraft (£6)
3kg Play sand – Homebase (£2.19 per 15Kg)
14 litre steel bucket – Homebase  (£7.99 Harris Bucket  -Silver – 14L)
5 Litre Plastic bucket – I used an old plant pot and filled in the holes with blu tac.
PVC tube – B&Q £2.00
Metal tube – B&Q £9.27
PVC joint – B&Q £1.08
Old fire extinguisher – Still need to find one

Ruined Mixing bucket

My first attempt at building the foundry was a complete failure. I added the sand and plaster of Paris before adding the water. Once I added the water however, i quickly realised it was too cold for me to actually stir the mixture with my hands. It warmed up after a minute or so but it was too late, the mixture started to harden and I had to get rid of it before it ruined the steel bucket as well. Unfortunately, the plastic bucket I was using to mix the plaster couldn’t be saved.

Next time, I’ll need to use warmer water for mixing and get it mixed up quickly before it starts to harden. I think it might also be a good idea to pre-mix the plaster with the sand a little before adding the water.

Wavefronbt Obj Mesh Loading

I recently wrote a simple loader to read the wavefront .Obj Mesh format and its associated .Mtl Material files. Although fairly straightforward, I did run into some  issues as the format seems to be poorly documented, a couple of which I have listed here.

Objects and groups

My first naive mesh loaded simply read through the file, reading all the vertices, normals and texture coordinates then jammed them all into one massive buffer. I noticed however that there were parts of the mesh that I didn’t want to render all the time. This is where the .OBJ files groups and objects come in handy.

In my implementation, each Mesh is composed of several “sub meshes” that contain all the information needed to render themselves independently from the others. When reading the OBJ file, a new mesh is created for each Object encountered and a new submesh for each group encountered. This allows a single file to contain 3 completely independent models and for each of those models to be split up into different renderable parts.

The main use I found for this is while rendering various models of spacecraft I downloaded for free from TF3DM. These models included detailed interiors which I wasn’t really interested in, and using groups, it was simple for me to turn off rendering these portions of the model.

Faces

Another thing that had me stumped for a bit were faces, and the fact they can contain more than 3 vertices, many more! Both of the following lines are valid.

f 1/1/1 2/2/2 3/3/3
f 1/1/1 2/2/2 3/3/3 4/4/4

I had to alter my original code that assumed that faces were triangles to account for these.

Tips

• Create a simple test mesh first that you know the layout of so you can debug your mesh loader easily. I created a simple cube with vertices, texture coordinates and normals to test mines thoroughly.
• Some free models downloaded from the net are messed up, don’t always trust them.

End Result

In the end I’m happy with the loader, but I’ll probably write a converter to convert them into my own binary format sooner or later as the text format of the OBJ files can be slow to parse on larger models.

OBJ Mesh Ship

OpenTK and C#

I’ve dabbled in the past with C++ and OpenGL but always found myself spending more time creating code to support what I wanted to do, rather than actually building it.

Then I found OpenTK, a managed library for interacting with OpenGL, OpenCL and OpenAL. It has saved me so much time compared to using C++ and OpenGL. The only downside to it is performance and although C# is speedy, it just cant keep pace with native code in all situations. In all honesty though, I haven’t noticed it yet, and I’m not sure I will unless I end up building the next AAA game. It seems to me that C# and OpenTK is the perfect tool combination for indie game developers.

Textured / Lit Model

 

Weak References

Another rarely used but handy C# construct I came across recently are Weak References.

Normally when you’re finished with an object in C#, you set the variable referencing it to null. Once all references to the object have been set to null, the object will be garbage collected at some point in the future.

A weak reference allows you to indicate to the garbage collector that the object may be collected but still allows you to access it until it does so. This can be used when you don’t want a reference to an object to prevent its deletion.

This might be useful as part of a resource management class in a 3D application. The actual manager itself might maintain weak references to loaded 3D assets and return strong references to other parts of the application that need it. If only the manager is left referencing the 3D asset, then it can safely be collected and reloaded again later if it is required.

The following code snippet shows a new Mesh being created, a weak reference of it being added to a dictionary and a strong reference to the Mesh being returned. After the “mesh1” variable is set to null, only the weak reference to it remains in the mesh dictionary and the mesh is open to garbage collection.

class MeshManager
{
    private Dictionary<string,WeakReference<Mesh>> _meshDictionary;

    public Mesh LoadMesh(string filepath)
    {
        Mesh msh = new Mesh(filepath);
                if(_meshDictionary.Contains(filePath))
	    _meshDictionary[filePath] = new WeakReference(msh);
	else
	    _meshDictionary.add(filepath,new WeakReference(msh));
	
	return msh;
    }
	
    public Mesh GetMesh(string filepath)
    {
	WeakReference<Mesh>meshRef = _meshDictionary[filepath];
	return meshRef.Isalive ? meshRef.Target as Mesh :
        LoadMesh(filepath);
    }
}

MeshManager manager = new MeshManager();
Mesh mesh1 = manager.LoadMesh("MyMesh.mdl");
mesh1 = null;
//mesh1 could be garbage collected anytime after here

C# Multiple Using Statements

I always hated the using multiple IDisposable objects at the same time due to the resulting mess that it created with indentation:

using(FileStream file1 = new FileStream("file1.txt",FileMode.Open))
{
    using(FileStream file2 = new FileStream("file1.txt",FileMode.Open))
    {
        //code here
    }
}

What I didn’t realise is that you can have multiple using statements one after the other, saving all the indenting mess.

using(FileStream file1 = new FileStream("file1.txt",FileMode.Open))
using(FileStream file2 = new FileStream("file1.txt",FileMode.Open))
{
        //code here
}

Nice!

GlPrimitiveRestartIndex

Stumbled upon a handy little OpenGL function today, glPrimitiveRestartIndex.

3D applications should try to keep the number of draw calls as low as possible to keep performance high. Primitive restart index allows you to do this by allowing you to render multiple separate pieces of geometry using a single draw call. This would allow you to draw, for example, two cubes with one call.

glPrimitiveRestartIndex takes a single value, the special index value used to specify that the previous element is the last in the current draw  the next element is the start of a new one. You can then plug this value into you list of indices and split it up into as many draw calls as you like.