Google Summer of Code - 2009

The final deadline for applications for the gsoc is fast approaching. You now have 4 days left, right up until 19:00 UTC on April 3rd. There are so many cool projects available this year, so make sure you apply soon before they're all taken!

Some of my personal favourites would be:
Writing SIMD code in C#
VDPAU VC-1/H.264 Support
Codec Demuxers
A Dirac decoder

And many more! Funnily enough, video encoding is what got me interested in programming in the beginning, so if you students don't snap up those projects, I will ;) Hack on something cool for the summer and earn yourself some cash while you're at it. It'll be great!

We got the grand slam!

We've done it! We've won the Grand Slam for the first time in 61 years. It was the most nail-biting match I've watched in a while. It was so close that the result was actually down to the very last kick of the match, which was a penalty awarded* against Ireland. Thankfully Wales missed it and sealed Irelands victory.

Go on the green!

* The ref made a bad call here and awarded a penalty against Ireland because the ball bounced forward after it was dropped. The rule are pretty clear that this should be a scrum and *not* a penalty. It wasn't the first time he made that mistake either. Still, it didn't matter in the end, woo!

Update: A friend just told me that the ref originally signalled a scrum but then changed it to a penalty. Sounds like an irish guy mouthed off or did something off the ball. Did anyone notice what actually made him change his mind?

MonoTorrent 0.70

With all the excitement going on, I forgot to blog about MonoTorrent 0.70, so here's a belated summary of what went on:

* Fixed an issue for torrents with no trackers
* Optimised the Bitfield class to allow for higher performance piece picking
* Rewrote the piece picking API which resulted in a very extensible, easily testable, less buggy and faster implementation
* Fixed an issue where the announce wouldn't happen immediately after a torrent completes
* Fixed several issues with webseeding and rate limiting
* Fixed an issue which resulted in an incorrect encryption level been chosen in a small proportion of cases
* Ensure that announces to trackers always time out correctly
* Fixed a race condition when stopping a torrent while an incoming connection is being processed
* Increased the performance of disk IO so that hashing a torrent is about 10% faster
* Vastly improved performance of the BanList parser
* Fixed issue where fast pieces could be requested multiple times
* Fixed issue with selective downloading where the start/end indices of files could be offset by 1

A precompiled binary can be found here and the source tarball can be found here. Enjoy!

What does it take to download a torrent?

The simple answer to this question is "All you need is the .torrent file. Stupid n00bs." This is true. The .torrent file contains all the metadata required to A) download the data and B) verify the data. Without this, you can't really do anything. So, do you actually need the .torrent file to begin a download?

No! All you need is the infohash for the .torrent file! The infohash is the SHA1 hash of the metadata in a .torrent file. As such, it can be used as a unique identifier for a particular .torrent file. With this infohash, you can query the BitTorrent DHT for a list of peers downloading that torrent. Then, with the help of the Metadata Exchange extension, you can connect to these peers and request that they send you the metadata from the .torrent file and you're away and downloading. Great!

"But what if some malicious peer sends you corrupt metadata, then you'd never be able to download the torrent properly!", I hear you asking. Well, in a rather beautiful twist, this is next to impossible. As I said earlier, the infohash is generated by putting the metadata in the .torrent file through a SHA1 hash. So all you have to do is hash the metadata once you have received it and then compare the result of that to the SHA1 hash you used to start the download. If they match, then you can be fairly confident that the metadata has not been corrupted/altered in any way.

As of 17:00GMT, March 15th MonoTorrent has completed its first download using only a 20 byte hash to begin the download. This is possible because of some tireless work by Olivier Dufour, who also implemented Peer Exchange, a good few parts of DHT, WebSeeding and SuperSeeding. The code for this still hasn't quite hit SVN, a bit of refactoring remains to be done. It should be in SVN within a week. I'm looking forward to his next patch of awesomenesss now.

The monsoon-devel list

I've started a mailing list for monsoon so that packagers can be kept updated and various interested people can post questions and all that jazz. Basically it's the standard -devel mailing list. That's mostly why it's called "monsoon-devel" ;)

If you're interested in keeping up to date on Monsoon, please join the group at: http://groups.google.com/group/monsoon-devel

Banshee - For all your medical record needs?

I'm sure everyone's familiar with Banshee, the most awesome media player of all time ever ;) So, how does it feel to know it has expanded into the medical record field? Good eh? Next time you go to your doctor do you know what they'll be running? That's right, Banshee - Medical Record Edition. Check out its website here:

http://gnumed.org/index.html

The regular banshee website can be found here:

http://banshee-project.org/

It's fun to open both in tabs and switch between them.

Monsoon 0.20

Monsoon 0.20 has been released and should be in a repository near you soon. Release notes can be found here. Fun stuff!

Excitement abounds!

Next weekend is going to be an interesting one. Several releases are coinciding:

1) MonoTorrent 0.70 is prepped and ready for release. Contains numerous bugfixes and performance enhancements.
2) Monsoon 0.20 will in a repository near you. This will be using MonoTorrent 0.70, so a nice upgrade from the previous 0.40 release.
3) The DBus daemon for monotorrent is ready for its first release. Banshee will be using this to add support for torrent based podcasts.
4) Mono.Nat will be getting it's first official package release too. It's a reasonably mature library which supports UPnP port forwarding/mapping. There's also support for nat-pmp in the library, but it's disabled due to lack of testing. If someone has a nat-pmp capable router, feel free to test the code, fix the few remaining issues and submit a patch.

But for now, it's holiday time for a week ;)

A workaround!

So there exists *one* way and one way only to safely set the Range header when using 64bit indices. This method was found with the help of NotZhila on #mono:

MethodInfo method = typeof(WebHeaderCollection).GetMethod
                        ("AddWithoutValidate", BindingFlags.Instance | BindingFlags.NonPublic);

HttpWebRequest request = (HttpWebRequest) WebRequest.Create ("http://www.example.com/file.exe");

long start = int32.MaxValue;
long end = int32.MaxValue +  100000;

string key = "Range";
string val = string.Format ("bytes={0}-{1}", start, end);

method.Invoke (request.Headers, new object[] { key, val });

You need to call the protected method of the WebHeaderCollection class so you can add the "Range" header without being forced to go through the broken HttpWebRequestAddRange method. I tried about a half dozen more legitimate methods, but the API is so locked down that it was impossible.

For example, HttpWebRequest.Headers is a get/set property, but if you set a new collection, it checks to make sure "Range" isn't there, and then just copies the keys from your new collection into it's internal one and ignores the collection you just gave it. What this means is that:

CustomCollection c = new CustomCollection ();
request.Headers = c;
Console.WriteLine (request.Headers == c);

prints false.

Ouch.

Anyway, the hack works. If you need 64bit indices when downloading files via HttpWebRequest, here's your guaranteed working hack, on both Mono and MS.NET.

System.Net.WebRequest -> System.Net.WebSuck

I can see that throughout the lifetime of the .NET framework, no-one realised that files greater than 2GB exist on the web.

System.Net.WebRequest.AddRange (int startOffset, int endOffset)

Thankfully I don't have to rewrite my own class from scratch, I can cannibalise one from Mono and add in a workaround, though that's likely to be a pain in the ass too :(

PiecePicking and runtime method overriding

Deciding which chunk of data to download next is a pretty complex task in the bittorrent world. You have to take into account a number of factors, such as:
1) You may want to prefer to download rare pieces first, maybe not.
2) You may want to pick a piece randomly, or maybe you want to download from the start of the file and get pieces in order
3) The user may set a higher priority on a certain file, so you should prefer its pieces.
4) The user may want to ignore certain files and never select their pieces.

Then imagine trying to NUnit test all the combinations and you'll find that it becomes very difficult to ensure the implementation is correct and impossible to extend with new behavior because the interactions become too complex.

The basic premise I had when redesigning this area of code was this: When I want to change the picking behaviour, I want to override one single method and then just slot the picker into the pipeline. So here's a reduced version of the PiecePicker class (3 methods instead of 10) and an example of how it's implemented.

public abstract class PiecePicker
{
  protected PiecePicker(PiecePicker picker)
  {
      this.picker = picker;
  }

  void CheckOverriden()
  {
      if (picker == null)
          throw new InvalidOperationException("This method must be overridden");
  }

  public virtual void Initialise(BitField bitfield, TorrentFile[] files, IEnumerable<Piece> requests)
  {
      CheckOverriden();
      picker.Initialise(bitfield, files, requests);
  }

  public virtual bool IsInteresting(BitField bitfield)
  {
      CheckOverriden();
      return picker.IsInteresting(bitfield);
  }

  public virtual MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
  {
      CheckOverriden();
      return picker.PickPiece(id, peerBitfield, otherPeers, startIndex, endIndex, count);
  }
}

    public class RandomisedPicker : PiecePicker
    {
        Random random = new Random();

        public RandomisedPicker(PiecePicker picker)
            :base(picker)
        {

        }

        public override MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
        {
            MessageBundle message;
            int midpoint = random.Next(startIndex, endIndex);
            if ((message = base.PickPiece(id, peerBitfield, otherPeers, midpoint, endIndex, count)) != null)
                return message;
            else
                return base.PickPiece(id, peerBitfield, otherPeers, startIndex, midPoint, count);
        }
    }

Here's a usage example:

// StandardPicker provides an implementation for every method in PiecePicker
PiecePicker p = new RandomisedPicker(new StandardPicker);

So what happens is this:
1) p.PickPiece is called which results in RandomisedPicker.PickPiece being called
2) This splits the range between startIndex/endIndex into two and then makes two calls to base.PickPiece.
3) base.PickPiece will call standardPicker.PickPiece (because the 'picker' is non-null)
4) standardPicker.PickPiece will see if there are any pieces to request, and choose the first available one

Suppose I wanted to be able to ignore all the pieces which I already own, well, that's easy, I just use an IgnoringPicker (not a great name I'll admit):

    public class IgnoringPicker : PiecePicker
    {
        BitField bitfield;
        BitField temp;

        public IgnoringPicker(BitField bitfield, PiecePicker picker)
            : base(picker)
        {
            this.bitfield = bitfield;
            this.temp = new BitField(bitfield.Length);
        }

        public override MessageBundle PickPiece(PeerId id, BitField peerBitfield, List<PeerId> otherPeers, int startIndex, int endIndex, int count)
        {
            // In binary operations: temp = peerBitfield & (~bitfield);
            temp.SetAll(false).Or(peerBitfield).NAnd(bitfield);
            return base.PickPiece(id, temp, otherPeers, startIndex, endIndex, count);
        }

        public override bool IsInteresting(BitField bitfield)
        {
            temp.SetAll(false).Or(bitfield).NAnd(this.bitfield);
            return base.IsInteresting(temp);
        }
    }

Now i just change my usage to:

Picker picker = new StandardPicker ();
picker = new RandomisedPicker (picker);
picker = new IgnoringPicker (myBitfield, picker);

The biggest benefit is that each individual picking logic unit can very easily tested. They can then be combined in any order you want to change the picking behaviour. Random->Rarest->Standard would be different to Rarest->Random->Standard. The former will give you the rarest piece in a random set, the latter will give you a random piece from the rarest set.

The implementation of a logic unit is also trivial - you only have to override the behaviour you want to change rather than implementing a massive interface where for 90% of the methods you end up calling basePicker.Method anyway. So I'm quite happy with this change. This code already passes all the NUnit tests from the old picker as well as all the new tests I've written, so it should be going live in the near future. There's still some more work to be done before it's complete.

MonoTorrent 0.62

MonoTorrent 0.62 has now been released which addresses a few major and minor issues with the 0.60 release. Here's the details:

* Fixed regression in message handling which resulted in 0.60 not transferring properly. Caused by not running the right NUnit tests before tagging.
* Performance optimisation for sending/receiving messages
* Fixed bug creating torrents with 2gb+ files with TorrentCreator
* Fixed issue with udp sockets in the Dht code which could cause dht to stop sending/receiving messages

I'd highly recommend upgrading from 0.60 to 0.62 as soon as possible.

Binary - http://monotorrent.com/Files/0.62/monotorrent-0.62-bin.zip
Source - http://monotorrent.com/Files/0.62/monotorrent-0.62.tar.gz

Are you mapping those dlls?

One of the issues with writing cross platform applications is that if you do P/Invoke into a native library, the name of that library changes depending on the OS. Mono has built in support for selecting the right file at runtime. The problem is that it's hard to ensure that you've correctly mapped all the methods you P/Invoke.

So I wrote a little tool to do that for you. It was inspired by an attempt by Aaron Bockover which parsed the raw cs files. I figured it'd be much better to just parse the compiled assembly ;)

using System;
using System.Collections.Generic;
using System.Xml;
using Mono.Cecil;
using System.IO;

namespace DllImportVerifier
{
    class MainClass
    {
        static void Main (string [] args)
        {
            args = new string [] { Environment.CurrentDirectory };
            if (args.Length != 1) {
                Console.WriteLine ("You must pass the path to the assemblies to be processed as the argument");
                return;
            }

            List<string> assemblies = new List<string> ();

            if (Directory.Exists (args[0])) {
                assemblies.AddRange (Directory.GetFiles (args [0], "*.dll"));
                assemblies.AddRange (Directory.GetFiles (args [0], "*.exe"));
            }
            else if (File.Exists (args [0])) {
                assemblies.Add (args [0]);
            }
            else {
                Console.WriteLine ("{0} is not a valid file or directory", args [0]);
                return;
            }

            foreach (string assembly in assemblies)
                ProcessConfig (assembly);
        }

        static void ProcessConfig (string assemblyName)
        {
            AssemblyDefinition assembly = null;
            try {
                assembly = AssemblyFactory.GetAssembly (assemblyName);
            } catch {
                Console.WriteLine ("{0} is not a valid .NET assembly", Path.GetFileName (assemblyName));
                return;
            }

            List<string> dlls = new List<string> ();
            try {
                XmlTextReader doc = new XmlTextReader (assemblyName + ".config");
                while (doc.Read ()) {
                    if (doc.Name != "dllmap")
                        continue;

                    string dll = doc.GetAttribute ("dll");
                    if (!dlls.Contains (dll))
                        dlls.Add (dll);
                }
            } catch {
                // Ignore malformed or invalid config files. If the config is malformed,
                // drop any successfully parsed dll maps
                dlls.Clear();
            }

            List<string> unreferenced = VerifyReferences (assembly, dlls);
            foreach (string dll in unreferenced)
                Console.WriteLine("Assembly: '{0}' references '{1}' without mapping it", Path.GetFileName (assemblyName), dll);
        }

        static List<string> VerifyReferences (AssemblyDefinition assembly, List<string> dlls)
        {
            List<string> unreferenced = new List<string> ();
            foreach (TypeDefinition type in assembly.MainModule.Types) {
                foreach (MethodDefinition method in type.Methods)  {
                    if (!method.IsPInvokeImpl)
                        continue;
                    
                    string dll = method.PInvokeInfo.Module.Name;
                    if (!dlls.Contains (dll) && !unreferenced.Contains (dll))
                        unreferenced.Add (dll);
                }
            }

            return unreferenced;
        }
    }
}

BarrierHandle

Did you ever have a case where you have a big dataset which can be processed in parallel, so long as all threads finish Step 1 before any thread starts Step 2? Thing is, there's no built in class to handle this case.

AutoResetEvent won't do it because it because it only signals *one* of the waiting threads, not *all* of them. What you need is a manual reset event and some complex handling.

I give you BarrierHandle:

using System;
using System.Threading;
 
class SpectralNorm
{
    public class BarrierHandle : System.Threading.WaitHandle
    {
        int current;
        int threads;
        ManualResetEvent handle = new ManualResetEvent (false);
         
        public BarrierHandle (int threads)
        {
            this.current = threads;
            this.threads = threads;
        }
 
        public override bool WaitOne()
        {
            ManualResetEvent h = handle;
            if (Interlocked.Decrement (ref current) > 0) {
                h.WaitOne ();
            }
            else {
                handle = new ManualResetEvent (false);
                Interlocked.Exchange (ref current, threads);
                h.Set ();
                h.Close ();
            }
 
            return true;
        }
    }
     
    public static void Main(String[] args)
    {
        int threadCount = 5;//Environment.ProcessorCount;
 
        // Lets assume that there's 20 units of data for each thread
        int[] dataset = new int [threadCount * 20];
 
        // This is the handle we use to ensure all threads complete the current step
        // before continuing to the next step
        BarrierHandle barrier = new BarrierHandle(threadCount);
 
        // Fire up the threads
        for (int i = 0; i < threadCount; i++) {
            ThreadPool.QueueUserWorkItem (delegate {
                int jjj = i;
                try {
                    Step1 (dataset, jjj * 20, 20);
                    barrier.WaitOne ();
                    Step2 (dataset, jjj * 20, 20);
                    barrier.WaitOne ();
                    Step3 (dataset, jjj * 20, 20);
                } catch (Exception ex) {
                    Console.WriteLine (ex);
                }
            });
        }
 
        System.Threading.Thread.Sleep (3000);
    }
 
    private static void Step1 (int[] array, int offset, int count)
    {
        Console.WriteLine ("Step1: {0} - {1}", offset, offset + count);
        Thread.Sleep (500);
    }
    private static void Step2 (int[] array, int offset, int count)
    {
        Console.WriteLine ("Step2: {0} - {1}", offset, offset + count);
        Thread.Sleep (500);
    }
    private static void Step3 (int[] array, int offset, int count)
    {
        Console.WriteLine ("Step3: {0} - {1}", offset, offset + count);
        Thread.Sleep (500);
    }
} 

MonoTorrent 0.60

So here are the bugfixes and features for 0.60 as compared to 0.50:

Bug fixes:
* Fixed critical regression in 0.50 whereby transfers would be incredibly slow.
* Fixed issue where announce/scrape requests to offline trackers may never time out
* Added a few memory optimisations when reading piece data from disk.
* Add the ability to report an alternate IP/Port combo to the tracker
* Optimised the encrypted handshake - its now a bit faster
* Fixed bug where wrong message ID was sent for extension messages
* Fixed bug where pieces which do not exist would be requested from webseeds.
* Fixed several bugs in TorrentCreator class where relative paths were used instead of absolute paths.
* Disabled UdpTracker support as the current implementation locked up until a response was received.
* Fixed a possible issue with multi-tier torrents.
* Added the ability to tell whether peers come from PeerExchange, DHT or the tracker.
* Some big performance boosts for webseeds by using a better method of picking pieces.
* Fixed a corner case whereby certain torrents may not get their last piece requested.
* When hosting a tracker,"/announce" is appended when you use the construtor overload which takes an IPEndPoint.

New Features:
* Implemented DHT support.
* Implemented sparse file support on the NTFS file system.

All in all, an awesome release. I have to give a shout out to Matthew Raymer who has been tirelessly testing MonoTorrent for the last few weeks. Without his constant bug reports, some of those bugs would never have been found, such as the one with UdpTrackers. Great stuff.

Packages:
Binary: http://www.monotorrent.com/Files/0.60/monotorrent-0.60-bin.zip
Source: http://www.monotorrent.com/Files/0.60/monotorrent-0.60.tar.gz

There are also packages for openSUSE in the openSUSE Build Service for those of you interested in those.

A hack too far

I was just looking at the PackUriHelper class, with a view to implementing it in Mono. One of it's many methods converts a regular Uri into a 'pack' Uri. For example:

http://www.test.com/main/page.html?query=val#middle

converts to

pack://http:,www.test.com,main,page.html?query=val#middle/

So I says to myself, this is easy, it's just combining two Uris. Simple!

Wrong

Uri original = new Uri ("http://www.test.com/main/page.html?query=val#middle");

Uri complete = new Uri ("pack://" + original.OriginalString); // FAILS
Uri complete = new Uri (new Uri ("pack://", original)); //FAILS
Uri complete = new Uri (new Uri ("pack://", original.OriginalString)); // FAILS

How about escaping the second string...
string escaped = Uri.HexEscape (original.OriginalString);
Uri complete = new Uri ("pack://" + escaped); // FAILS

So at this stage I've lost all faith in humanity, so i try a basic test just to make sure i'm not insane. I'll try create a pack uri object myself, just to prove that it really is possible to parse them.

Uri complete = new Uri ("pack://http:,www.test.com,main,page.html?query=val#middle/");

EPIC FAIL

You can't do that. While they can *generate* that Uri for you, you can't generate one for yourself. Funnily enough, they do register a custom parser for the pack scheme, it's just incapable of parsing pack URI's. Don't ask me why.

After several hours and a lot of wasted time I finally came up with this:

Uri complete = new Uri (new Uri ("pack://"), escaped);

This is the *only* way to create a Pack URI. You have to hex escape the original uri and then call the constructor overload which takes a Uri and a string.

That is one of the stupidest things I've ever seen.

MonoTorrent 0.60

MonoTorrent 0.60 is being prepared for release. 0.50 was released a mere 3 weeks ago, so why 0.60 already?

Well:

1. There was a big regression in 0.50 with regards to download speeds. Transfers were a *lot* slower than 0.40. To backport this fix would be very complex as there have been a lot of changes since 0.50 was branched.
2. DHT support is now good enough for me to activate by default. This was my milestone for releasing 0.60.
3. There have been a number of other important bugs fixed aswell (including a critical one with UdpTrackers) which need to be released.
4. There have been a number memory/performance optimisations since 0.50 which would be nice to release ;)

So, if you're using MonoTorrent, I urge you to check out the branch (when it is created) from http://anonsvn.mono-project.com/source/branches/bitsharp-0.60.

Until I create the branch, check out revision 117059 of monotorrent from svn. If you have any bugs/issues, let me know and I'll try to get a fix in for 0.60.

Walking can be tricky...

Awesome!
(No, it's not just a knee-high stocking with sticky tape, it's a cast)

The big wahooni

Sparsely populated, just the way I like it

The NTFS filesystem has support for sparse files, but this has to be specially enabled when creating a file. I was originally linked to a blog post on the idea, but unfortunately the license pretty much forbids me from using that code.

So I spent most of yesterday evening and this morning googling API documentation and eventually came up with a fairly basic implementation of sparse file support. The only two operations supported are:

1. Creating a sparse file
2. Setting the size of the sparse data.

The benefits of this are seen only on the NTFS filesystem, but what it gives you is the ability to write pieces at arbitrary places in the file without having to preallocate up to that point. There's a bit of overhead, but other than that you only use up the space which you've actually written to, i.e. only the pieces which have been downloaded.

Finally, if you don't have an NTFS filesystem supporting sparse files, you will not be affected by this. Those of you on HFS+ can never get this support, and those of you on ext3, I'm unsure how to enable sparse files. I think it's enabled by default, but if not, any recommendations on setting this up would be appreciated.