Friday, July 9, 2010

Info - File Information in Bittorrent

The information about files is stored in the info section of the .torrent file. There is a slight difference in this structure if the torrent contains one file or whether it contains more than one file. To make handling some of that information a tad easier, I have a collection of methods for common tasks and to hide the single/multiple file differences.

Subtle Differences
The structure of the info data is different depending on whether it's a torrent containing one file or many. This makes for a large number of "if" conditions when handling the info data, and it's just easier if this is hidden away. The old Firepuddle Firefox/Bittorrent extension didn't get around to handling multiple files; the info data is just the tip of the iceberg of pain that multiple file torrents can be.

Common Functions
The methods the service I've written provides are fairly simple; though partly that's to keep the handling of different info data structures in one place. listFiles(in nsIVariant decodedInfo) returns an array of file paths. A single file has its path stored in a torrent file as an array, for example ["foldername","foldername","filename"] which avoids the issue of an OS specific directory separator character. Handy. So, that means the result of listFiles is an array of arrays of strings. fileCount(in nsIVariant decodedInfo) returns the number of files. fileSize(in nsIVariant decodedInfo, in long fileIndex) returns the size in bytes of a file, given an index from the list. I should note, the ordering of the listFiles function is that provided by the info data.

Not so necessary functions
A couple of functions I don't believe I've used for handling the downloading/uploading of a torrent, but I've needed for another application of bittorrent are fileInTorrent(in nsIVariant decodedInfo, in nsIVariant filePathArray) returning a boolean result (the file path array is expected to be an array of strings, as described previously), and findFile(in nsIVariant decodedInfo, in nsIVariant filePathArray) to provide the index in the fileList of a particular file path. -1 if not found, as normal.

Tetris Block functions
During a session the content of torrent is transferred as a series of blocks, in no pre-ordained order. These blocks are some subsection of the torrent, and one block may end up split into multiple files.
To figure out where a block belongs, blockToFileParts(in nsIVariant decodedInfo, in long offset, in long blockLength) returns an array of objects. Each object specifies a fileIndex, the offset in the file, and how many bytes from the offset belong to that file. The structure of this returned data is like so: [{index:...,offset:...,size:...},...].
The torrent is split into a series of pieces that have a checksum. Sometimes not all files in a torrent are desired, so not all pieces will be needed. To find out which pieces are needed for a particular file piecesInFile(in nsIVariant decodedInfo, in long fileIndex) will return an array of numbers, each number representing a piece index necessary for the file specified by the fileIndex parameter.

Implementation of FileInfo XPCOM component
IDL for FileInfo XPCOM component

Example:

var service = Components.
classes["@wikiscraps.com/fileinfo;1"].
getService(Components.interfaces.btIBittorrentFileInfo);
var fakeInfo = {
files : [
{ length : 10, path : ["a"] },
{ length : 10, path : ["b"] },
{ length : 10, path : ["c"] },
{ length : 10, path : ["d"] },
{ length : 10, path : ["e"] }
]
};
// Add piece length later, because it has a space in it's key.
fakeInfo["piece length"] = 6;
// Check service methods
// Check the list files/file count/file size/file in torrent/find file
var fileList = service.listFiles(fakeInfo);
service.fileCount(fakeInfo); // 5
service.fileSize(fakeInfo, 0); // 10
service.fileInTorrent(fakeInfo, ["a"]); // this will return true
service.fileInTorrent(fakeInfo, ["z"]); // this will return false
service.findFile(fakeInfo, ["c"]); // this will return 2
service.findFile(fakeInfo, ["z"]); // this will return -1 (not in torrent)
service.blockToFileParts(fakeInfo, 10, 9); // returns [{index:1,offset:0,size:9}]
service.piecesInFile(fakeInfo, 1); // returns [1,2,3] (pieces are indexed from 0)

Note that none of this code deals with the relationship between pieces and hashes. At the moment I don't think that's needed in this service, though I might consider a verify piece against hash method at some point. This service will probably change by the time I've finished refactoring.

More information on the .torrent structure (Theory.org) Bittorrent Protocol Specification (BEP0003)
The bencoding XPCOM component.
The bittorrent tracker XPCOM component.

Thursday, July 8, 2010

XPCOM Generating SHA1 hash on a string

Reading some old code, thought this would be interesting. I tend to comment a fair bit, particularly when I'm frustrated or think I'll forget something. What follows are my comments from December 2008, and some updated SHA1 code.
/*****
* Generate a SHA1 hash of some data.
* Sources:
* Mainly based on example from https://developer.mozilla.org/en/NsICryptoHash
* With a conversion from string to array of numbers from http://www.cozmixng.org/retro/projects/piro/diff/backforwardthumbnail/trunk/content/backforwardthumbnail/backforwardthumbnail.js?compare_with=1438&format=diff&rev=1440
*
* Discussion:
* The basis of this function is the Mozilla documentation for nsICryptoHash,
* which does include a demonstration of generating a hash for a string -
* but it won't work (at least in this case). The Mozilla docs do some
* Unicode handling, however this generates an incorrect hash for our
* purposes. Instead, I found if I saved the data to a file, and then
* opened that file and passed the stream to nsICryptoHash, I would get the
* correct result. So, ignore the Unicode handling. Saving then opening a
* file is crazy, so a different stream was needed. StringInputStream was
* considered, and is used by FastServicesJavaScript (1) and Flock (2),
* but XUL Planet docs mention that the incoming string shouldn't contain
* null. This condition can't be guaranteed with the data we're handling,
* so another option was needed. The update method for nsICryptoHash can
* take an array of bytes. How can we convert a string to an array of
* bytes? Apparently, easily. Just create an array of the character's
* ordinal value using charCodeAt. This technique was found from
* cozmixng (3), and is a cut-and-paste of 3 lines.
* 1 - 2008/DEC http://wiki.fastmail.fm/index.php?title=FastServicesJavascript
* 2 - 2008/DEC https://lists.flock.com/pipermail/svn-commits/2007-September/012334.html
* 3 - 2008/DEC http://www.cozmixng.org/retro/projects/piro/diff/backforwardthumbnail/trunk/content/backforwardthumbnail/backforwardthumbnail.js?compare_with=1438&format=diff&rev=1440
* (3) is licensed under MPL, GPL & LGPL
* http://www.cozmixng.org/retro/projects/piro/browse/backforwardthumbnail/trunk/content/backforwardthumbnail/license.txt?rev=1429
********/

SHA1 = function (data) {
var hash = Components.classes["@mozilla.org/security/hash;1"]
.createInstance(Components.interfaces.nsICryptoHash);
hash.init(hash.SHA1);
// cozmixng split/map call
var byteArray = data.split('').map(function(c) { return c.charCodeAt(0); });
hash.update(byteArray, byteArray.length);
return hash.finish(false);
}

It's interesting re-reading this. I have found XPCOM components to be weird beasts, particularly when used in JavaScript. Looking back, this is partly from lack of understanding. I find understanding anything Mozilla will provide a headache; confirming a bug for example. It seems to me that once someone comes to understand anything in Mozilla, it is best if they blurt out that knowledge lest it be lost.

I really miss XUL Planet's documentation on sockets, that good old Pushing and Pulling. I feel lucky to have been able to catch that, and read their XPCOM reference before XUL Planet reached a decision to drop the content.

A few explanations on the SHA1 function, if this helps others. I tend to read data from sockets, and use nsIBinaryInputStream to do it. I don't use nsIScriptableInputStream, in fact I will probably never again use nsIScriptableInputStream simply because it doesn't handle null values. In the past, I've used the readBytes method (of nsIBinaryInputStream) which provides the result as a string in JavaScript. This may have been a good idea, maybe a bad one. Regardless, it is the reason for the above need to call split() on a string. The string is really just a collection of bytes, but now it's in JavaScript so everything has become a little odd, so we need to change the appearance of the string into an array of numbers (split to an array, map to numbers), and then let XPCOM handle the conversion so nsICryptoHash receives an array of bytes.

It seems so bloody obvious now, but reading the comments above replays part of the journey it took to get there.

Wednesday, July 7, 2010

Liking getService over createInstance (plus some xpcshell unit tests for bittorrent extension)

So, I've finished the tracker code as a service, instead of creating an object for each tracker we communicate with. I like it. Next, I'm writing a service to simplify interpreting the info section of a .torrent file (once this data has been bedecoded). Actually, the info section is really easy to understand, as seen in Theory.org's Bittorrent Protocol documentation. It's just that the common things I want to know are not always easy to infer directly from the info section.

If we receive a block 100 bytes long that belongs at offset 3,000 in the torrent, what part of which files does this represent? I like to have a function that given the offset and block length will convert this to an array of objects each containing the filename, offset in the file, and how many bytes to write. You know? Something like blockToFileParts(decodedInfo,offset,blockLength) returning [{file:...,offset:...,size:...},...]. Now I can start taking chunks from the received block and placing them in the correct places in files.

Sooo, that's what's next. I've been testing it with a bunch of unit tests, which have proven quite valuable. I've caught several bugs in a controlled situation, which is much easier than debugging using a network sniffer and the good old pen and paper calculator. Here's a peak at the tests, I'll see about dropping the component tomorrow. It's obviously very much a specialised utility class, it doesn't appear obviously useful to anyone but myself at this time.


function fileInfoTests(){
do_check_eq("Now testing fileInfo", "Now testing fileInfo");
// Check class loaded
do_check_true("@wikiscraps.com/fileinfo;1" in Components.classes);
// Check interface exists
do_check_true("btIBittorrentFileInfo" in Components.interfaces);
// Grab the service object.
var service = Components.
classes["@wikiscraps.com/fileinfo;1"].
getService(Components.interfaces.btIBittorrentFileInfo);
var fakeInfo = {
files : [
{ length : 10, path : ["a"] },
{ length : 10, path : ["b"] },
{ length : 10, path : ["c"] },
{ length : 10, path : ["d"] },
{ length : 10, path : ["e"] }
]
};
// Add piece length later, because it has a space in it's key.
fakeInfo["piece length"] = 6;
// Check service methods
// Check the list files/file count/file size/file in torrent/find file
var fileList = service.listFiles(fakeInfo);
do_check_eq(fileList.length,5);
do_check_eq(service.fileCount(fakeInfo),5);
do_check_eq(service.fileSize(fakeInfo, 0),10);
do_check_true(service.fileInTorrent(fakeInfo, ["a"]));
do_check_false(service.fileInTorrent(fakeInfo, ["a","a"]));
do_check_false(service.fileInTorrent(fakeInfo, ["z"]));
do_check_eq(service.findFile(fakeInfo, ["a"]),0);
do_check_eq(service.findFile(fakeInfo, ["a","a"]),-1);
do_check_eq(service.findFile(fakeInfo, ["z"]),-1);
// Check the blockToFileParts method
// For a block spanning all of one file
var fileParts = service.blockToFileParts(fakeInfo, 0, 10);
do_check_eq(fileParts.length, 1);
do_check_eq(fileParts[0].index, 0);
do_check_eq(fileParts[0].offset, 0);
do_check_eq(fileParts[0].size, 10);
// For a block spanning two files
fileParts = service.blockToFileParts(fakeInfo, 0, 11);
do_check_eq(fileParts.length, 2);
do_check_eq(fileParts[0].index, 0);
do_check_eq(fileParts[0].offset, 0);
do_check_eq(fileParts[0].size, 10);
do_check_eq(fileParts[1].index, 1);
do_check_eq(fileParts[1].offset, 0);
do_check_eq(fileParts[1].size, 1);
// For a block of one byte near the beginning of a file
fileParts = service.blockToFileParts(fakeInfo, 10, 1);
do_check_eq(fileParts.length, 1);
do_check_eq(fileParts[0].index, 1);
do_check_eq(fileParts[0].offset, 0);
do_check_eq(fileParts[0].size, 1);
// For a block of one byte near the end of a file
fileParts = service.blockToFileParts(fakeInfo, 9, 1);
do_check_eq(fileParts.length, 1);
do_check_eq(fileParts[0].index, 0);
do_check_eq(fileParts[0].offset, 9);
do_check_eq(fileParts[0].size, 1);

// PieceList check
// With a pieceLength of 6 & file sizes of 10:
// File 0 contains piece 0 & 1 (4 bytes)
// File 1 contains pieces 1 (2 bytes), 2, 3 (2 bytes)
// File 2 contains pieces 3 (4 bytes), 4
// File 3 contains pieces 5, 6 (4 bytes)
// File 4 contains pieces 6 (2 bytes), 7, 8 (2 bytes, irregular sized piece)
var pieceList = service.piecesInFile(fakeInfo, 0);
do_check_eq(pieceList.length, 2);
do_check_eq(pieceList[0], 0);
do_check_eq(pieceList[1], 1);
pieceList = service.piecesInFile(fakeInfo, 1);
do_check_eq(pieceList.length, 3);
do_check_eq(pieceList[0], 1);
do_check_eq(pieceList[1], 2);
do_check_eq(pieceList[2], 3);
/* check pieceIndex 4 (5th piece) is correctly allocated to fileIndex 2 (3rd file) */
pieceList = service.piecesInFile(fakeInfo, 2);
do_check_eq(pieceList.length, 2);
do_check_eq(pieceList[1], 4);
pieceList = service.piecesInFile(fakeInfo, 3);
do_check_eq(pieceList.length, 2);
do_check_eq(pieceList[0], 5);
// Tests missing:
// when piece is shared between 3 files (piecesize > middle file size)
// Files at end of torrent
}

Hmm. Okay, so a few of those methods aren't clear without understanding what the parameters mean. Here's the IDL:


[scriptable, uuid(463206c3-74dd-44f4-b6bf-dc8fbc198993)]
interface btIBittorrentFileInfo : nsISupports
{
nsIVariant listFiles(in nsIVariant decodedInfo);
long fileCount(in nsIVariant decodedInfo);
long fileSize(in nsIVariant decodedInfo, in long fileIndex);
boolean fileInTorrent(in nsIVariant decodedInfo, in nsIVariant filePathArray);
long findFile(in nsIVariant decodedInfo, in nsIVariant filePathArray);
nsIVariant blockToFileParts(in nsIVariant decodedInfo, in long offset, in long blockLength);
nsIVariant piecesInFile(in nsIVariant decodedInfo, in long fileIndex);
};


This again isn't completely useful, because I've used nsIVariant where arrays or objects would be. Ugh... I can see documentation would be shorter way to enlightenment.

Tuesday, July 6, 2010

Info - Bittorrent Tracker (and XPCOM component)

The tracker is a web service that when given an id of a torrent will respond with a list of IP addresses/ports of other peers interested in that torrent.

Torrent Identity
The identity of a torrent (the 'infoHash') is generated from a hash using SHA1 on the section of the .torrent file describing the list of files & checksums. This means that the rest of the .torrent file can be edited, while the torrent identity will remain unchanged. The editing may be the addition or removal of a tracker for the torrent, or some other meta data that itself is not the 'contents' of the torrent.

Finding Trackers
The .torrent file will contain at least one tracker, identified as 'announce'. Additional trackers may appear in the .torrent file as 'announce-list'.

Talking to Trackers
Trackers are given a HTTP GET request with information passed via the query string. The payload in the response is usually a bencoded dictionary listing other peers in the torrent, though this is an optimal response. Sometimes it's a string describing an error such as not accepting requests without compact=1 (the format of the peers list may be a compact string, or a list of dictionaries; the component defaults to compact=1 to avoid this issue). Darn.

Talking to Trackers, again
A subsequent call to a tracker may occur, to get more peers or to update the tracker on progress. The original tracker response may have included a minimum timeout to use before making this follow up call, and also a Tracker Id which should be sent as part of the follow up call.


Implementation of Tracker XPCOM component
IDL for Tracker XPCOM component

Example:
var trackerCaller = Components.
classes["@wikiscraps.com/tracker;1"].
getService(Components.interfaces.btIBittorrentTracker);
// Get a list of peers
trackerCaller.start(
// infohash of http://www.mininova.org/det/3194273
"\x72\xc2\x4e\x55\xc3\x2c\xde\xf7\x23\x78\x12\xf1\x69\x4d\xad\xd1\xe7\x13\x19\x97",
// announceURI
"http://tracker.mininova.org/announce",
"", // tracker Id
"-YY0000-000000000000", // peer id (should've generated & recorded this)
6881, // local bittorrent port
-1, // maximumPeers (-1 means use default)
0, // uploaded bytes
0, // downloaded bytes
0, // remaining bytes...
{
onResponse : function(peers, interval, trackerId) {
// got a list of peers
alert("Look! Peers!\n" +peers);
// the interval before another request to the tracker can be made
alert
("Timeout (in seconds) before next tracker request:\n" +interval);
// the id to use for subsequent calls to the tracker
alert("Tracker's Id:\n" + trackerId);
},
onError : function(serverResponse) {
// darn.
alert("Unknown error, tracker component response was:\n" + serverResponse);
}
});

More information on the .torrent structure (Theory.org) Bittorrent Protocol Specification (BEP0003)
More information on the tracker response (Theory.org) Bittorrent Protocol Spec (BEP0003)
The bencoding XPCOM component.

Monday, July 5, 2010

Leak due to XPCOM service held in global variable

I've been running some xpcshell tests. I'm testing the bittorrent tracker code, which is asynchronous so that's kinda fun. It means that I call do_test_pending(); before starting the tracker request. Oh, let's show a test:

function run_test() {
// Just check we're running tests okay
do_check_true(true);
// Check the interface has been loaded correctly
do_check_true("btIBittorrentTracker" in Components.interfaces);
// Check the component has been registered correctly
do_check_true("@wikiscraps.com/tracker;1" in Components.classes);
// Grab the service
var trackerService = Components.
classes["@wikiscraps.com/tracker;1"].
getService(Components.interfaces.btIBittorrentTracker);
do_test_pending();
// Make a request to the tracker
trackerService.start(
// infohash of http://www.mininova.org/det/3194273
"\x72\xc2\x4e\x55\xc3\x2c\xde\xf7\x23\x78\x12\xf1\x69\x4d\xad\xd1\xe7\x13\x19\x97",
// announceURI
"http://tracker.mininova.org/announce",
"", // tracker Id
// peer id (should've generated & recorded this)
"-YY0000-000003030303",
6881, // local bittorrent port
-1, // maximumPeers (-1 means use default)
0, // uploaded bytes
0, // downloaded bytes
0, // remaining bytes...
{
onResponse : function(peers, interval, trackerId) {
// got a list of peers
do_check_true(peers instanceof Array);
// finished tests
do_test_finished();
},
onError : function(serverResponse) {
// darn. Fail the test.
do_throw("Unknown error, server response was:\n" + serverResponse);
do_test_finished();
}
});
}

So you pass the tracker service the information needed to make a call to the tracker, and some kind of observer/callback to use when there's a result known. Okay? Got it? Cool.
Anyways, I started seeing a BloatView report after running this test. It didn't appear originally, so I assume it only appears when some kind of leak occurs.

== BloatView: ALL (cumulative) LEAK STATISTICS

|<----------------Class--------------->|<-----Bytes------>|<----------------Objects---------------->|<--------------References-------------->|
Per-Inst Leaked Total Rem Mean StdDev Total Rem Mean StdDev
0 TOTAL 27 520 24783 11 ( 183.34 +/- 238.02) 80546 13 ( 263.14 +/- 337.35)
2 BackstagePass 24 24 1 1 ( 1.00 +/- 0.00) 6366 4 ( 148.79 +/- 78.75)
19 XPCNativeScriptableShared 112 112 1053 1 ( 12.21 +/- 1.38) 0 0 ( 0.00 +/- 0.00)
22 XPCWrappedNative 56 168 1322 3 ( 661.75 +/- 381.27) 8044 3 ( 682.46 +/- 383.57)
23 XPCWrappedNativeProto 32 64 519 2 ( 260.00 +/- 149.61) 0 0 ( 0.00 +/- 0.00)
100 nsJSID 36 36 116 1 ( 58.25 +/- 33.42) 499 1 ( 117.51 +/- 67.79)
135 nsStringBuffer 8 8 2600 1 ( 435.41 +/- 266.14) 4832 1 ( 413.00 +/- 254.37)
144 nsSystemPrincipal 36 36 1 1 ( 1.00 +/- 0.00) 347 1 ( 4.72 +/- 1.09)
147 nsThread 72 72 3 1 ( 1.80 +/- 0.84) 4598 3 ( 571.22 +/- 379.54)

nsTraceRefcntImpl::DumpStatistics: 180 entries

Ouch. So, going back over what I'd done recently, I found this:

if (Tracker.prototype._bencoding == false) {
try {
Tracker.prototype._bencoding = Components.
classes["@wikiscraps.com/encoding/bencoding;1"].
getService(Components.interfaces.Bencoding);
} catch(e) {
callback.onError("Bencoding component not loaded");
return;
}
}

It seems loading a XPCOM service, and then leaving it in a 'global' variable and never explicitly releasing it caused a leak. Whoops. The BloatView goes away if I switch to using local variables and acquire the service each time it's needed, so it seems I can call that fixed?

More information on testing a JavaScript Add-on with XPCShell (Interfaces and components!).
More information on writing XPCShell unit tests.

Friday, July 2, 2010

Bittorrent Tracker ... again

Some time ago I was talking about implementing an object to communicate with bittorrent trackers (the server or servers which provide an initial list of peers).
This week I've been revisiting that code, finishing it yesterday. Aaaand today I'll scrap the code.
I had gotten a platform independent Firefox bittorrent extension working long ago, with a major memory leak which led to wasted time and disinterest. I started breaking the extension into individual components that could be re-used and tested independently, the first release being the encoding/decoding component (with XPIDL and all that). I liked that release, the code is really a translation to JavaScript of the 'official' bittorrent clients bencoding, attributed to Petru Paler and remaining licensed with the Bittorrent Open Source License.
Finishing the tracker code, I looked back and saw I had been attempting to create classes that could be extended, and in turn objects that held state. The idea being that this could be a base tracker class, extended to provide additional abilities. I've looked back at the code with some disgust. I really don't think I should've approached the design that way. Sure, part of the reason for the approach was to make it easier for someone to extend the code, but predicting where/how it needs to be flexible was a waste (in this case).
I'm rewriting the code to be like the bencoding component. The object will hold no state, everything relevant is passed as part of method calls. In this case, there's a networking issue that requires asynchronous activity so I'll provide a callback parameter. If the code is useful for someone in the future, great, take the code and someone else can design for flexibility, I'll just try to focus on cohesion.

Tuesday, January 26, 2010

Australian Government, leading the blind

Why the odd background today? The Australian Government are not acting in it's citizens best interest. They're moving to mandatory filter what citizens are allowed to see, promoting it under the guise of protecting children. It's *exactly* like what repressed countries do - and is irresponsible on a global scale. They answer 'protecting children' not with trying to actually tackle abuse as part of an international community, but with covering the eyes of their citizens - which can't be good for our future. Check out http://www.internetblackout.com.au/ and read a bit on Wikipedia http://en.wikipedia.org/wiki/Internet_censorship#Pervasive