Monday, December 22, 2008

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.

Saturday, December 20, 2008

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 :(

Wednesday, December 17, 2008

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.

Hit Counter