Like talking to a stranger

Now that I'm on planet Linux Australia too I thought I'd write up a brief howdee post. My main open source project is libferris which is a virtual filesystem with metadata extraction and index+search functionality. It also does a bunch of other interesting stuff, but as I've been writing it for what is getting close to 10 years now, one would imagine it has a few facets.

I mainly package libferris for Fedora and maemo because these are the platforms I tend to use it with myself. A while ago I did some packages for openSUSE and Ubuntu, but its hard to keep motivation for those when I don't use the distro personally. Plus on modern desktop or servers, stuffing ferris on a virtual Fedora machine isn't much of a hassle, given the price of even DDR3 RAM.

I'm also trying to stuff libferris itself into the main Fedora repository. But we'll see how that goes.

If you want to hear about libferris and other filesystem crack then you should come along to this NLUUG event in May. I'll be there presenting libferris and what I think the intranet metadata and search stuff should be doing (and probably will be doing in the libferris world) over the next few years.

As my blog description states, my posts are mainly about libferris but also include maemo stuff and generic C++, XML, RDF, and relational database topics. I seem to waffle on unmerciful about indexing, or so I've been told. Which is hardly surprising given the chunk of libferris devoted to implementing filesystem search through various techniques.

Also, if anybody is looking for user space virtual filesystem hacking or index and search work, then drop me a line :)

Tracker: Reading it both ways :(

Normally I refrain from criticising other projects that are "competing" with my little hobby -- libferris. I mention competing in quotes because hobbies don't really compete in a commercial sense. But having read this post recently on planet maemo about Tracker progress I was a little overwhelmed, wondering, was the Tracker code really so bad a year ago?

"In this last year, we refactor (well, almost rewrote) the daemon"

and talks about replacing the crawler code wholesale. Sure progress sometimes includes churn of functionality: reimplementing stuff with the benefit of 20/20 hindsight. But this seemed a little dramatic...

Slow as a tree

Hmm, nepomuk integration as the core of amarok's collection manager... now if only flacs without seek tables were not so inconvenient in amarok it would be damn cool.

http://lists.kde.org/?l=amarok&m=120671838014374&q=p3

Finally it seems RDF is making its merry way into the core position of (meta) data sharing on the desktop. A good time to be a semantic hacker.

Keeping an index up to date... quickly?

Most of the index engine implementations in libferris will detect when you try to add the same file again, and when it hasn't changed in a meaningful way will just skip reindexing it. This makes it really easy to just use the below command to update the index for a specific filesystem.

$ find /Data | feaindexadd --filelist-stdin

The trick comes in when /Data is an NFS share with 400,000 files on it that you are accessing from a Nokia n810. Or when /Data is a file server that you are indexing from your laptop over wifi or another sluggish, higher latency network.

feaindexadd can be told to directly traverse one or more directories and so you don't have to use find in the above command. But separating out the find from the indexing has a really big advantage: you can update indexes of extremely large, but infrequently changing NFS shares very quickly -- Even over slow networks.

The trick is to do the filesystem traversal on the server side, and just pump the URLs that are interesting to the client machine:

ssh lowaccess@server 'find /Data -mtime -10' \
| feaindexadd --filelist-stdin

Of course, this relies on /Data being the same filesystem on both the server and the client. Otherwise you're in for some fun with sed or awk to mangle the paths to be what the client expects.
And the 10 in the above means that you'll have to run the command from cron within 10 days to maintain a complete index. You might find that doing a "time find /Data" on the client and server has significant performance differences, particularly if the filesystem has many files.

You can always store and search the index from the file server, but for disconnected searching, you really need to have the index itself stored on the maemo device.

Searching indexes on a maemo device: a customized solution

In a previous post I had a video showing one of the libferris inverted file metadata index plugins on maemo. Unfortunately that implementation was designed for a desktop machine, meaning for many many more files, slow disk head seeks, blazingly fast CPU(s).

While these videos are not as snazzy as some others, I make them so folks can get an idea of the real performance of the software. Saying its "acceptably fast" or takes less than a second is all well and good, but seeing the snail or rabbit move gives an immediate gut feeling if its "fast enough".

The new maemo custom designed metadata architecture uses the mmap() design. I always have my reservations about mmap() because it encourages data structure and algo choices that are directed at an in-memory world. That is all great if you can cache the entire memory mapped file in main memory, but often leads to kittens crying when there isn't enough RAM for that. For maemo with 128mb total RAM this is also an issue, but with the much faster disk seeks of flash storage the relatively poor data clustering of mmap()ed designs is a bit less important for performance. But of course, data clustering and physical layout is always interesting when playing the indexing game.


libferris maemo audio search by regex on URL from Ben Martin on Vimeo.

Shown in the video above is a search using the new "custom mobile device" libferris metadata index. As I continue to type a regular expression to match against the URL, libferris gives some search results on each character entered. Note that this is against an index with over 10,000 URLs in it. This index format will be available in libferris 1.2.7+. The index format sports a probabilistic regular expression prefilter for URL matching. This means that the results of the prefilter might include some false positives, but anything the filter drops out is definitely not a match. You have to run the regex itself on all results of the prefilter to drop out the false positives. The prefilter can drop the number of times a regular expression is evaluated down to less than 100 in 10,000 URLs given only a 3-4 character regex. This helps out oodles when you want to run raw regex searches on big (for a portable device) indexes and you want your results asap.

An unfortunate current side effect of the mmap() design is that the index is architecture dependant. Mainly because some secondary offset-pointer information is 64 or 32 bit width dependant, so its a matter of tracking those peskies down and clamping them to a fixed width. To get around that for now, I indexed the 10,000 odd audio files over NFS from an n810.

Some information for those looking to play, if you are using boost to memory map, you may well discover that atomic_cas32() calls __sync_val_compare_and_swap() which is not actually available on the maemo device (for me). This is with a modified scratchbox using gcc version 4.2.1.
I'm not sure if there is an accepted cas et al library for maemo/armel. I leave the hacks for __sync_val_compare_and_swap() to the reader and their accepted level of concurrency control risk.

Searching for audio files on an NFS share from maemo

Searching for audio files on an NFS share from maemo from Ben Martin on Vimeo.

The n810 only has one memory slot. With an 8gb card in there you might fit 1,000 ogg files onto your storage. That was quite boaring, so I instead indexed an NFS share that is over 10x larger ;) I'm using one of the libferris inverted file backends for the index, which is more targeted at the desktop machine assumptions of having a faster CPU and expensive disk head seeks. Needless to say, I'm hacking on a custom index implementation for maemo which will be more oriented at a slower CPU with much much less expensive disk seeks for flash based storage.

Note that the time after I run ferris-music-search to when the first message appears on the console "Using index..." is fairly much all wasted in dynamic linking. A major slowdown that I've yet to sweep away for running apps on maemo.

The artist and title info is taken from the ID3 tags in the audio files. Indexing time is roughly 3 to 10 milliseconds per file when performed on the desktop. The inverted file index format is portable from desktop to maemo device. I plan to make the new explicit maemo format portable too, so you can make indexes on powerful machines and rsync them over to the maemo device. Assuming you are indexing stuff that is stored on your file server, not the maemo device.

During the typing for the first search on title, possible completions are shown by taking your input as a substring of the title you seek. This is more effective if you keep it in mind because you can choose just a few keys in a substring of the title. All searches are performed using regex matching on strings, which is much slower than direct equality because of the huge complications it introduces for indexing. But it is interesting, even with modestly 10x the number of files you can cram onto an n810, using nasty slow regex searching, the performance is acceptable for much of the time. There are a few cases that I'll improve, particularly regex searching on whole URLs.

Notice that the name and URL are shown as columns, so you can easily "group by" when you click on the appropriate header. I need to also include the artist, title etc ID3 fields into the results,. Oh, and have the ability to click on a few files and see the whole ID3 and metadata of those files "side-by-side" so you do not have to try to read it from the results list.

So now when I see a CD in the shops, I wont have to wonder how many of those Mozart tracks I have already, I can know for sure :-p

Accelerometers hit Canola2 and PDF viewing

Of course, if a unit comes out with an embedded accelerometer in it then using a "slightly clunky" wiimote will no longer be needed as the source of motion data. I recently added the ability for libsixdof to control closed source applications as well as properly patched open source ones. This was mainly to let Google Earth finally take some advantage of proper sixdof devices, but it works equally well for Canola2 on maemo.


Controlling Canola2 using libsixdof and a wiimote from Ben Martin on Vimeo.

Two big features that libsixdof brings is the ability to configure what happens when the controller is moved on an axis, and how frequently that happens. So, if you don't like your images flicking past at 20 images / second in Canola, you can limit it to whatever / second. In the video, having maximum axis movement will only ever scroll 3 images / second. So when I hold the unit causing a continual next image movement I can still see what is happening and Canola2 does not get overloaded with events.


Flipping pages in a PDF by moving the n810 from Ben Martin on Vimeo.

Again the wiimote is actaully held behind the device. I'm sort of getting the hang of the controlling code etc so that you can use more subtle rotations of the device to issue commands to the running program. This is using the same stuff that the Canola2 video did, I could patch a PDF viewer, but for discrete events like next-page it doesn't really make a huge difference. Panning is the big thing that screams out for patching.