I've always wanted to work on support for STT_GNU_IFUNC symbols on sparc. This is going to solve a real problem distribution makers have faced on sparc64 for quite some time.

What is STT_GNU_IFUNC?

Well, normally a symbol is resolved by the dynamic linker based upon information in the symbol table of the objects involved. This is after taking into consideration things like symbol visibility, where it is defined, etc.

The difference with STT_GNU_IFUNC is that the resolution of the reference can be made based upon other criteria. For example, based upon the capabilities of the cpu we are executing on. The most obvious place this would be very useful is in libc, where you can pick the most optimized memcpy() implementation.

Normally the symbol table entry points to the actual symbol location, but STT_GNU_IFUNC symbols point to the location of a "resolver" function. This function returns the symbol location that should be used for references to this symbol.

So when the dynamic linker resolves a reference to a STT_GNU_IFUNC type symbol "foo". It calls the resolver function recorded in the symbol table entry, and uses the return value as the resolved address.

Simple example:

void * memcpy_ifunc (void) __asm__ ("memcpy");
__asm__(".type foo, %gnu_indirect_function");

void *
memcpy_ifunc (void)
{
  switch (cpu_type)
    {
  case cpu_A:
    return memcpy_A;
  case cpu_B:
    return memcpy_B;
  default:
    return memcpy_default;
    }
}

So, references to 'memcpy' will be resolved as determined by the logic in memcpy_ifunc().

These magic ifunc things even work in static executables. How is that possible?

First, even though the final image is static, the linker arranges to still create PLT entries and dynamic sections for the STT_GNU_IFUNC relocations.

Next, the CRT files for static executables walk through the relocations in the static binary and resolve the STT_GNU_IFUNC symbols.

There are some thorny issues wrt. function pointer equality. To make that work static references to STT_GNU_IFUNC symbols use the PLT address whereas non-static references do not (they get fully resolved).

Back to the reason I was so eager to implement this. On sparc we have four different sets of optimized memcpy/memset implementations in glibc (UltraSPARC-I/II, UltraSPARC-III, Niagara-T1, Niagara-T2). Right now the distributions have to thus build glibc four times each for 32-bit and 64-bit (for a total of 8 times).

With STT_GNU_IFUNC they will only need to build it once for 32-bit and once for 64-bit.

I've just recently posted patches for full support of STT_GNU_IFUNC symbols to the binutils and glibc lists.

In recent news, the Symbian Foundation announced that "All 108 packages containing the source code of the Symbian platform can now be downloaded from Symbian's developer web site". This is great news!

This morning I tried to look at the parts most interesting to me: phonesrv (implementing call engine, cell broadcast and SIM toolkit APIs) and poc (implementing push-to-talk). Their pages don't have the usual "source code" tab at the bottom right which links to mercurial and tarball download pages!

Either I'm too stupid, or I am unable to find any source code for those two components. I'm quite sure something essential like the API's for making phone calls are considered part of the Symbian platform. So how does that match with the statement that all packages containing the Symbian platform can now be downloaded?

I decided that every day I would review some code in ctdb.  I never spend enough time reading code, and yet it’s the only way to really get to know a project.  And I decided to start easy: with the popt library in ctdb.

popt is the command-line parsing library included with the RPM source, and used by SAMBA.  I vaguely recall Tridge telling me years ago how good it was.  I started with the man page, and it is an excellent and useful library: it does enough to make the simple cases less code that getopt_long, yet allows flexibility for complex cases.

The idea is simple: similar to getopt_long, you create an array describing the possible options.  Unlike getopt, however, simple integers and flags are handled automatically.  So you set up the context with the commandline, then hand that context to poptGetNextOpt() to do the parsing.  That keeps parsing args until it hits an error or you’ve marked an argument to return a value for special handling.  The manual page is excellent and made me feel really comfortable with using the code.

Now, the code itself.  Even before you notice the four-space tabs and bumpyCaps, you see the lint annotations and docbook-style comments cluttering the source.  It does make the code annoying to read, breaking CCAN’s Golden Rule.  Typedefs of structs, typedefs to pointers, and several #ifdef  __cplusplus complete my minor gripes.

The code is old and cross-platform: the header test for features we’d simply assume in a modern Linux.  It has a simple set of bitmap macros (taken from pbm, judging from the name), a helper routine to find an executable in $PATH (using alloca!) .  These are the kinds of things which would be in separate modules, were this in CCAN.

The definition of _free() to be a (redundantly-NULL-taking) free() which always returns NULL is used to effect throughout the code:

    defs = _free(defs);

Here is a trick I hadn’t seen before to zero an onstack var, and really don’t recommend:

poptDone done = memset(alloca(sizeof(*done)), 0, sizeof(*done));

The help-printing code is in a separate file, popthelp.c.  It’s actually about half 1/3 of the code!  That’s mainly because it takes pains to pretty-print, and it’s done by manually tracking the column number through the routines (aka ‘cursor’).  These days we’d asprintf into a temp buffer and strlen() to figure out if we should start a new line and indent before printing this.  Or even better, create a struct with the FILE * and the column number, and create a fprintf variant which updated the column number and figured out wrapping for us. Routines like maxArgWidth() which iterates the table(s) to figure how much to indent will still suck however: probably simplest to build all the strings in the help table in memory and then dump at the end.

I thought I found a buffer overrun, but a test program disproved it: the singleOptionHelp() uses its maxLeftCol (plus some extra stuff) to size a buffer.  This works because maxLeftCol is previously calculated as the worst-case size of the argument help.  Now, the code is unclear (AFAICT maxLeftCol must always be sufficient, so the extra bytes are wasted), but not buggy.

In summary, this is excellent code.  Talloc would help it, as would modern printf usage (%.*s for example), but generally the code is in really good shape.  I know that the popt code in RPM is a little updated, but I can’t imagine that much has changed in such an obviously-stable codebase. The temptation to rewrite it is thus very low: who knows what the testsuite would miss?

After slightly disastrous preparation  (my left knee in a brace as detailed for the perversely-curious here) my week went well.  I tried to get back to my hotel room early each evening to rest as per doctor’s orders (and managed it except Friday night), but polishing my Friday talk tended to take a few hours every day.

Sunday

The Newcomer’s Session was well attended, but Jacinta and I were slack with preparation so it was unbalanced for my tastes.  I raced to the post-session pub assuming my crutches would ensure I’d be the trailer, to find that I was wrong.  It would have been better to explicitly and immediately drag people towards the pub, because that’s (seriously) the most important part of the introduction to LCA.

Monday

Miniconf time, and I started in the Open Programming Languages miniconf.  There was some interestingly random language stuff there: it’s one of my few opportunities to get exposure to higher level languages.  The miniconf talks were enthusiastic and unpolished as such things are supposed to be.  Haskell, and all the wonderful things it doesn’t let you do by Stephen Blackheath was interesting,  but lacked solid examples. Introducing Gearman — Distributed server for all languages by Giuseppe Maxia was a great short intro into an unknown project. vcs-pkg.org by Martin F. Krafft was classic work-in-progress talk with insights into a mundane but critical infrastructure problem (standards and practices for coordinating upstream and across distributions using distributed revision control).

Die Flash Die – SVG has arrived by Andy Fitzsimon gave classic bling talk with a message about the animation potential for SVG.  Useful content, too, for those dealing with this, and I was blown away to hear of Gordon, a FOSS Flash™ runtime written in JavaScript.

How to Use FOSS Graphics Tools to Pay for College by Elizabeth Garbee was an insight into the US education system and a chance to find out what my friend Edale (I know she hates that meme!) was doing.  But her talk didn’t quite gel for this audience. Unfortunately using the words “did you spot the head-fake?” riles me.  You are suddenly telling me that you’ve been using your intellect to compete with me rather than to inform and enrich me.

Then came my own Talloc: Pick Up Your Own Garbage! talk, which was delayed by my miscalculation of transit time on crutches. A mediocre rehash of my previous talloc talks, but I wanted to put it in front of this group because it really offers fresh view into a program’s data structures at runtime.

Writing Facebook Applications in Perl by Paul Fenwick was a nice little introduction to the FB API from a Perl point of view, but he kept his powder dry for his awesome lightening talk on Friday.

Tuesday

I peered in at the tail end of the keynote which was apparently excellent.  I woke a little early then did some more work on my presentation, and by the time I had breakfast I was incurably late. One person admitted to me that they watched the live stream from their hotel room, but I wasn’t that clever.

This this day was all hallway track for me, catching up with many people I haven’t seen since last year. Then the Speaker’s Dinner at Museum of New Zealand: Te Papa Tongarewa. This is also a fun time to chat with everyone, but I was disappointed that my crutches forced me to forgo learning a traditional Haka. It was also the first chance to greet the two chief organizers, who had been sick the first two days of the conference.  Edale and I also had fun playing with their very-past-bedtime hyper 2 yo Brooke (until we were told not to stir her up any more!)

Wednesday

The keynote by Benjamin Mako Hill was a little chaotic but made his point about antifeatures well: how such things are only viable when consumers don’t have freedom of choice (in particular, ability to examine, modify and share the software they’re using).  I then headed to Introduction to game programming by Richard Jones, where I struggled with pyglet before giving up and paying half-attention.  I did learn some things though, and everyone who was active seemed to get great satisfaction from the tutorial.

Open Sourcing the Accountants by Jethro Carr lacked density.  It takes a great deal of work to give a thorough comparison of different accounting packages, and his insights into how accountants think were insufficient to make that the backbone of his talk either.

subunit: Testing across boundaries for fun and profit by Robert Collins was slightly familiar ground for me, but as libtap maintainer he wanted me to attend.  It was a good bread-and-butter talk, which perhaps could have benefited from a few more snazzy real-life examples (making testing sexy is hard though!).  He semi-seriously suggested I should take over the C output implementation for subunit; still thinking…

I caught the questions at Teaching FOSS at universities by Andrew Tridgell and Robert (Bob) Edwards, which I will watch seriously once the videos are uploaded.

Then was one compulsory-attendance presentation of the week: The World’s Worst Inventions by Paul Fenwick. I had made a comment to Paul earlier in the week that I was concerned that my talk lacked substance.  His reply was “I won’t comment how much substance is in my talk”.  And any conclusions were left to the minds of the audience as full-costumed Paul took us through a series of invention disasters.  I teased him about it later, but let’s be honest: if I could present like that I wouldn’t have worried about content either!

That evening was the HackOff.  I’ve never tried competitive programming, so when we came up with the plan of a SAMBA team, I heartily endorsed it :)  Intimidation is important at these events, and the tweet from Adam Harvey was promising: At the #lca2010 HackOff. There’s a table with Rusty, Tridge, Anthony Towns and Andrew Bartlett. We’re fucked. However, despite having the largest team (with 6 of us), we only just squeaked in by 2 minutes.  Subtract any one of the team and we wouldn’t have won, though with fewer we might not have tried to brute-force the final question.

Thursday

Glyn Moody’s keynote was excellent. Then I lost some more hallway time before emerging in The Elephant in the Room: Microsoft and Free Software by Jeremy Allison. I thought it was a worthwhile and balanced presentation; of course it had a few cheap laughs in it, but the examination of Microsoft’s actions wrt FOSS is a worthwhile exercise if we want to assess their potential impact.

I was a bit late to Building a Xapian index of Wikipedia in less time than this talk takes by Olly Betts, but it was too unprepared for my tastes and I went in not knowing what Xapian was (though I picked it up from context). Tux on the Moon: FOSS hardware and software in space by Jonathan Oxer was good, but another one I was late to (15 minutes between talks seems to give me enough time to start conversations, but not enough to finish them).

Simplicity Through Optimization by Paul McKenney was a good talk if you didn’t know your RCU.  For me I would have liked to hear more what the various lines of code were doing (before they were excised by the optimized implementation).  But being deeply familiar with the theory and somewhat familiar with the practice, I’m probably in a minority.

By this stage I was exhausted, and Using Functional Programming Techniques In Your Favourite Language by Malcolm Tredinnick was in the same room so I stayed.  This talk was a disappointment to me (and, I think, Malcolm) because it didn’t quite contain the general insights he’d believed were there when he proposed the talk. Nice for me to get an refreshing exposure to functional programming though.

Dinner at an Indian restaurant with the SAMBA people, which meant I was right near the PDNS, so I dropped in briefly then returned to my hotel room for an early night.

Friday

Nat Torkington’s keynote contained the classic “heckle Rusty” factor and was delightfully punchy. He rolled over to a very very strong set of lightning talks; a format which works so well at these geek-rich events.  Paul Fenwick’s “Unfriendly” Facebook app was an awesome way to close.

Patent defence for free software by Andrew Tridgell (late again!) was familiar ground for me, but I wanted to see how he presented such a dry area.  Lots of text: I would have included some more diagrams (claim dependencies are well represented by a tree, for example). But the audience were rapt, so I’m clearly too picky!

Last minute prep for my talk: I decided the previous night that I would use Notes View, only to find that noone could get it to work.  Both notes and presentation appeared on the projector screen, fortunately as I was about to give up and run without notes, someone suggested I simply drag the notes view back onto my laptop screen!  Sometimes the low-tech approaches evade our over-complicated minds.

FOSS Fun With A Wiimote by Rusty Russell was well-received. I didn’t go as far with the project as I had intended, due to personal time contraints and time lost wrangling with actual hardware, but sometimes that’s instructive too.

The presentation itself was flawed in three places.  Firstly, my intro slide appeared all at once rather than clicking in one point at a time, destroying my carefully practiced routine at that point.  Secondly, noone knew what LED throwies were: (an open source graffiti technology developed at the Graffiti Research Lab) and I so that slide was completely lost.  Finally, I should have set up my replacement two-year-old on the stage where the audience and the cameras could see her clearly.

The closing announced Brisbane for lca2011, and I handed the virtual speakers’ gift to the organisers.  That done, I was ready to relax at the Penguin Dinner.  Most years I don’t even drink, knowing that I’ll have to do the auction.  But as there was no auction I sat next to Nat Torkington to guarantee great conversation and was ready to chill. I did some singing, didn’t try the Haga (again). I even got a cuddle with the organiser’s very well-behaved 5-month-old son Adam.

Unfortunately, events conspired against me and I was dragged into a pledging war for a prize I didn’t want to win (and at which my doctor would be aghast). I thought we could get more money from the Wenches For Winching, who were weasonably wealthy and weally wanted to win. Ted Ts’o had a similar idea. Unfortunately the prospect of crippled Rusty being “rescued” (after being dropped: that was the no way part) was too alluring for many, and I had to work hard to ensure I didn’t win.

A good time had by all, though exhausting after a long week.

Saturday

Briefly peered into the Open Day, which was buzzing with setup and opening, before heading home, spent. I did find out that wild weather had wuined the winching of wenches; but there is a standing offer when they find themselves in Wellington again.

Summary

Absolutely on par with previous awesome conferences; there were no organisational disappointments for me the entire week. I was particularly happy to see people digging in and fixing things when they were wrong instead of simply complaining.

A great achievement, everyone!

I've been busy day and night, hacking away on my latest pet project in the GSM field. In fact, it's been a long time since I've been able to dedicate so much time and energy into one particular project, without many distractions at all. The project is now finally looking quite promising and making nice progress throughout the last three weeks.

If progress continues, I hope in another week I'll be able to reveal what this is all about. I haven't felt this level of excitement since the early days of Openmoko :)

Many people have pointed out the MagicJack Femtocell product that has been announced at CES. I cannot really understand the big hype and news about it. Why? read further...

On the technical side, there is hardly anything new. Using projects like OpenBTS or OpenBSC, you can run your own GSM network and connect it to VoIP. Sure, the retail price of the MagicJack is much lower, but that's the economics of scale. As soon as OpenBSC support for one of the recent femtocells is done, we also have a much lower cost solution to the same problem.

On the legal and business side, I can see many problems for MagicJack:

• To operate equipment in the GSM or 3G spectrum, you need a license. Since a nationwide GSM operator license is very expensive in about any country of the world, it is economically not an option. Selling the MagicJack devices without a license and leaving the spectrum license to the user will not work, or at least not long, since regulatory authorities and commercial operators are not going to let anyone deploy systems that interfere with their networks.
• If you keep the Operator's SIM in the phone, and use that SIM on your own network you might at least violate the terms of services of the operator. The SIM card normally belongs to the operator, and it is part of the users business relationship with that operator. As such, you can not really use it with other networks. Sure, if you do this at home with your OpenBTS/OpenBSC installation, nobody will care. But if somebody is doing this commercially, and in a way that affects the sale of talk time of the regular operators, again it will not take long until the commercial operator will sue you.
• Security. If you run your phone with a "foreign" SIM, you do not know the Ki on the SIM and thus cannot do cryptographic authentication and/or encryption. This is a big security issue. It is once again not an issue in your personal testbed setup, but it is going to be one if you do this at large scale as a mass market product.

So, as you can see: It's neither technically something exceptionally new, nor is it something that has a very promising business or legal outlook. The only way how a product like this would work is if it is authorized by the respective operator. But why would the operator authorize something that will take talk time away from his network and thus his revenue stream?

I've finally found enough spare time to work on detailed plans for a GSM development board. The idea here is to have a 100% open hardware design with 100% free software that provides an inexpensive platform for GSM related R&D.

Initially the focus is on having a board that can behave like a GSM cellphone, next steps would be to have a multi-channel frequency-hopping receiver, and finally the option of using it as a BTS.

The idea is fairly simple: Take a commercial off-the-shelf analog baseband and RF circuit for GSM and attach it to a general purpose DSP, add some glue logic and go ahead. But the devil is in the details:

• You want something where you can still find the parts on the market, but which still has sufficient leaked documentation that you can write an open source driver for it.
• The requirements for a MS and a BTS are quite different. A phone never needs to continuously receive and transmit in all timeslots, e.g.
• The requirement for a multi-channel frequency-hopping receiver is mainly a high number of receiver circuits, so the solution needs to scale to a larger number of receivers.
• The analog baseband circuits often have quite obscure control interfaces which need to be driven. Custom peripherals in programmable logic (CPLD/FPGA) are required.
• The TDMA nature has strict timing requirements. Normal processors and software-based mechanisms are not sufficient to trigger the required events and their sequencing at a high enough precision.

Anyway, there is sort of a first plan now, and the next weeks and months will be spent with refining the plans and building a first proof-of-concept prototype. Once that has proven to work, we want to go ahead with finishing the design for a real board, to be manufactured in sufficient quantities for interested parties.

Unless you have worked in GSM phone or base station hardware design or have a similar level of EE and DSP skills, please refrain from contacting me right now about how to join the project. We want to focus on getting things going first, then make a public release at a point where there is something that works sufficiently well that we can support a larger community of developers.

Mikey blogs about linux-next workload with pretty graphs.  Ideally, we should all have our patches marshalled before the freeze, and there should be no pre-merge-window peak.  I’ve gotten close to this in recent times, by being lazy and being content to wait for the next cycle if I miss one. Rushing things in tends to imply we skimped on review and testing.

So on that basis 2.6.30 looks like a winner:  it has the smallest “peak of crap”.

If you want to actually measure how much work Stephen is having to do, you would have to figure out what changes he is seeing.  Approximately, that would be the changes in Linus’ tree that did not come from linux-next, plus any new work entering linux-next itself.  Anyone?

I will freely admit that kernel work has dropped in my priority list. But that didn’t excuse sloppy work like my ae1b22f6e46 commit which sought to sidestep an issue for lguest without me having to do much work.

There’s a 64 bit atomic exchange instruction on x86 called cmpxchg8b.  This isn’t supported on pre-586 processors, so we have cmpxchg8b_emu, but that implementation isn’t paravirtualized so won’t run under lguest.  That’s OK, we used to never run it except on machines which didn’t support that cmpxchg8b instruction and I’ve never received a report.  Then at some point we started doing so: the easiest mod I could see was to switch emulation off except for kernels specifically compiled for 386 or 486.  But I missed Linus’ commit which had set the archs on which emulation was skipped:

Note, this patch only adds CMPXCHG8B for the obvious Intel CPU’s, not for others. (There was something really messy about cmpxchg8b and clone CPU’s, so if you enable it on other CPUs later, do it carefully.)

Now, I could blame Linus for putting that in a commit message, not in the Kconfig.cpu file where anyone changing it was going to see it.  But you should always double-check when you think you’re “fixing” something, and I didn’t.

(I get annoyed when developers don’t detail exactly what commit introduced a problem: it’s not just for convenient reading, but such research often prevents reintroducing subtle bugs! Like, say, Cyrix 6×86 not booting…)

The German radio station Deutschlandradio Kultur has invited Constanze Kurz (46halbe) and myself for interviews during today's Breitband radio show. We'll be talking about the 26C3, the Chaos Computer Club and - of course - GSM [in]security.

So far, OpenBSC already implemented mobility management, i.e. keeping track of which location area a mobile phone is locate in. However, this only works during idle mode, i.e. while there is no actual phone call in progress.

Throughout the last week, I've been working on getting real handover support into OpenBSC. This is now actually working very well! You can move from one cell into another cell while your phone call continues just like it is supposed to do.

The signalling part is actually not all that hard to implement. However, it has some dependencies on things like measurement reports, which in turn require us to send proper neighbor lists, which in turn requires proper generation of system information messages, etc.

The actual order of events in a successful handover case is as follows:

• OpenBSC send the neighbor cell information in the BCCH and SACCH
• OpenBSC regularly receives measurement reports from the phone, where it tells us how well neighbor cells are being received. OpenBSC then averages those measurements and decides
if or not to make a hand-over. If it decides so, it

allocates a channel on the new BTS

waits until the BTS acknowledges this

sends a HANDOVER COMMAND to the phone through the old BTS

waits for HANDOVER ACCESS bursts and a HANDOVER COMPLETE on the new BTS

closes the old channel on the old BTS

takes care of re-routing the voice channels

As indicated, the signalling part was relatively easy, and once the measurement processing and neighbor lists were in place, this worked really quick. What turned out to be a much bigger PITA was the handling of the actual voice streams.

Let's assume you have a call from A to B, where B is changing cells and now becomes B*. In this case, after switching cells, the speech frames from A need to be re-routed to B* instead of B. That's simple and works very easy. In the other direction, switching off B is easy. However, a completely new channel B* suddenly sends speech frames to A. In case of classic TRAU frames on E1 that is simple as they don't have any context.

In the case of ip.access nanoBTS, the speech frames are transported using RTP. Changing the source of your stream will change its CSRC (synchronization source identifier), timestamps and sequence numbers. The receiver in BTS A is not happy at all about this. So with handover, it is no longer possible to send RTP streams directly between BTS's, but OpenBSC's RTP proxy needs to process the RTP packets and hide the details of the changed source.

This is further complicated by the fact that during handover you are losing speech frames, somewhere between 10 and 40 in the cases that I've seen. This means that when sending the new RTP frames from B*, the sequence number and timestamp needs to account for those lost frames, i.e. incremented by the respective loss count. Otherwise the RTP receiver in BTS A will think it is only receiving old frames and will discard all of them.

Luckily, all of this seems to have been sorted out now and I'm confident we will have actual full handover at the GSM network at 26th annual Chaos Communication Congress in a few days from now. We'll be running 3 BTS's with a total number of 5 TRX's inside the conference building.

Today I've taken one day off work in order to attend the publich hearing of Germany's constitutional c ourt on several constitutional complaints against a German national law on data retention of telecommunications data. As the topic is likely only relevant to Germans, and due to the fact that I am not very confident with my English legalese outside of copyright law, I'll switch to German for this blog post - which I believe is unprecedented in this blog so far.

Tja, da war ich also heute einer der wenigen auserkorenen Besucher beim BVerfG. Immerhin haben mehr als 34.000 Leute Verfassungsbeschwerde eingelegt, auch wenn rein formal heute nur eine Hand voll exemplarische Beschwerden verhandelt wurden. Diesen Trick hat sich das BVerfG wohl ausgedacht, um nicht vor dem Problem zu stehen dass jeder Beschwerdefuehrer sicher ein Recht haette, persoenlich vor Gericht anwesend zu sein.

Der Gerichtssaal des BVerfG ist sehr klein. So klein, dass bei besonders bedeutungsvollen Verfahren kaum mehr Platz fuer Besucher ist. Der eigentliche Gerichtssaal war schon durch die Beschwerdefuehrer, die zahlreichen Vertreter des Gesetzgebers und der Behoerden und Amstraeger (BKA, Polizeipraesidenten, Richter an diversen Gerichten, Bundes- und Landesdatenschutzbeauftragte, Mitglieder des Bundestags und nicht zuletzt die zahlreichen wissenschaftlichen Mitarbeiter des Bundesverfassungsgerichts selbst belegt. Hinten waren noch zwei Reihen fuer Besucher frei.

Diese beiden Reihen wurden durch Studentengruppen belegt - oder vielleicht koennte man fast sagen "verschwendet". Ein nicht unerheblicher Teil dieser Studenten (u.a. der TU Darmstadt) hatte tatsaechlich geschlafen. Was fuer eine Ungeheuerlichkeit, nicht nur ein Mangel an Respekt gegenueber dem hoechsten Gericht des Landes und dem Thema gegenueber - sondern auch eine unverschaemtheit gegenueber den vielen vmtl. hunderten von interessierten Buergern die gerne der Verhandlung beigewohnt haetten, aber einfach keinen Platz mehr bekommen haben. Freunde von mir haben am 2. Tag nach der Terminankuendigung versucht noch einen Platz zu bekommen - vergebens.

Da haben wir also die nahezu perverse Situation, dass das hoechste Gericht zwar faktisch von jedem Buerger angerufen werden kann, dies auch eine fuenfstellige Zahl an Buergern wahrnimmt - dann aber die eigentliche Verhandlung nur fuer eine kleine Elite zugaenglich ist, und Aufzeichnungen oder Uebertragungen nicht gestattet sind. Das erscheint mir doch irgendwie ungerecht.

Doch nun zur Sache:

Der 1. Senat unter dem Vorsitzenden Richter Papier hat die Anhoerung im Allgemeinen sehr souveraen geleitet. Es gab ein paar amuesante Momente, als z.B. die Vertreterin des Justizministeriums das Wort an den Prozessbevollmaechtigten der Bundesregierung uebergeben hat, obwohl doch das Gericht normalerweise das Wort erteilt, und nicht andersherum ;)

Wie auch schon bei der letzten Verhandlung: Die Beitraege der geladenen Sachverstaendigen waren bisweilen der interessanteste Teil, vor allem eben die diversen Fragen des Gerichts. Diese Fragen erlauben einerseits einen Blick hinter die Ueberlegungen der Richter - andererseits aber auch in wie weit die technischen Zusammenhaenge und deren Folgen vom Gericht bereits verstanden werden. Das jetzt bitte nicht falsch verstehen: Ich habe tiefsten Respekt vor dem Gericht, und es ist i.d.R. sehr erstaunlich wie weit sich die Richter in das jeweilige Fachgebiet einarbeiten. Wie auch schon bei der Verhandlung zu den Wahlcomputern lassen die Vertreter der Regierung bzw. der untergeordneten Behoerden da oft deutlich weniger umfassende Kenntnisse durchblicken.

Die ganze Debatte zur VDS (Vorratsdatenspeicherung) ist verzwickt. Wir haben da historisch einen Bundestag, der keine VDS will, einen Rat der EU-Innenminister der das dann einfach als EU-Richtlinie beschliesst, und einen Bundestag, der in Folge die exzellente Ausrede hat, dass er die Richtline ja umsetzen muesse, um von der EU kein Verfahren angehaengt bekommt.

Die EU-Richtline heisst nun eben auch, dass das BVerfG nun nicht nur in der Sache zur VDS entscheiden kann, sondern sich eben noch mit der Frage beschaeftigen muss, was denn passiert wenn eine EU-Richtline mit dem Deutschen Grundgesetz in Konflikt steht.

Ein paar voellig ungeordnete aber fuer mich bemerkenswerte Punkte der Verhandlung heute:

• Es gibt keine empirisch/wissenschaftliche Grundlage die belegt, dass die VDS zur bekaempfung von Terroristischen Anschlaegen geeignet ist (das war ja nach Dem 11.9. sowie den Anschlaegen von Madrid und London die Begruendung).
• Der Chef der Bundesnetzagentur hat mehrfach ganz unuebersehbar nicht auf eine wiederholte Frage des BVerfG geantwortet: Gibt es Unternehmen, die gesetzlich zur VDS verpflichtet sind, aber andererseits keinerlei Verpflichtung zur erstellung oder Abgabe eines Sicherheitskonzepts zur Sicherheit dieser Daten haben? (Meine Auffassung: Ja, die gibt es!)
• Die Bundesnetzagentur macht, wie sie selbst sagt, im wesentlichen Pruefungen der Sicherheitskonzepte am Schreibtisch. Das muss ja mit der Realitaet in den Unternehmen nicht viel zu tun haben.
• Einer der Beschwerdefuehrer, Minister A.D. Dr. Burkhard Hirsch hat wohl die lebhaftesten und unverbluemtesten Redebeitraege gehalten; sehr erfrischend.
• Der Polizeipraesident von Muenchen wurde gebeten, konkret zu begruenden, wie die VDS der polizeilichen Ermittlungsarbeit in Muenchen hilft. Fast alle seiner Beispiele waren ungeeignet, da sie auch ohne VDS aber z.B. mittels einer telefonischen Fangschaltung oder einer Verbindungsdatenspeicherung nach expliziter Aufforderung durch die Polizei (und nicht auf Vorrat) moeglich gewesen weaeren. Zwei seiner Beispiele haben sich zudem generell als falscher Alarm herausgestellt (Journalist macht einn Testanruf; gelangweilter Schueler kuendigt aus Spass Amoklauf an). Das klang alles eher nach Stammtischgeschichten als nach fundierter Ermittlungsarbeit in wichtiger Sache.
• Die Sicherheitsanforderungen an die Speicherung der VDS-Daten ist derzeit offensichtlich nicht hoeher als an alle anderen Daten innerhalb des Fernmeldegeheimnisses insgesamt. Also der gleiche Sicherheitslevel, der uns zu den Datenschutzskandalen wie z.B. bei der Telekom gefuehrt hat. Das ist ja mal echt vertrauenerweckend.
• Der Chef der Bundesnetzagentur spricht gerne vom "bill shock", was laut ihm eine ueberhoehte Telefonrechnung nach unabsichtlicher Nutzung der teuren Auslandsroaming-Tarife im Mobilfunk ist.
• Ein kleiner Schmunzler am Rande war dann noch Burkhard Hirsch's "Blueberry", als er den Blackberry meinte ;) Ja, klar, jeder weiss was er meint und niemand nimmt es ihm uebel - aber es zeigt einfach, wie unsicher die "alte Garde" mit den Begrifflichkeiten der heutigen Alltagswelt umgeht.
• Die qualitaet der Richterlichen Anordnungen laesst offensichtlich sehr zu wuenschen uebrig. Es ist aufgabe des jeweiligen Richters, einzuschraenken genau welche Daten denn vom TK-Dienstleister uebergeben werden sollen. Laut dem Vertreter des Verbands der Internetwirtschaft (eco e.V.) kommen hier anscheinend recht allgemeine Anordnungen im Stil von "geben Sie uns mal alles was Sie haben" vor. Das geht so natuerlich nicht!
• Es kam zur Sprache, dass deutlich mehr Leute jetzt ihre eigenen e-mail Server betreiben wollen (privat und bei Firmen), weil man sich damit der e-mail VDS entziehen kann. Ist ja schoen, dass es den Trend gibt, und gut dass das auch mal auf dieser Ebene zur Sprache kommt. (Fuer mich kaeme etwas anderes niemals in Frage. Meine Daten gehoeren mir. Ich wuerde weder die Speicherung meiner Mails noch jeglicher anderer Daten jemals einer anderen Person anvertrauen, weder einem Privatunternehmen noch einer staatlichen Stelle). Das ist genau einer der vielen Tricks, mit denen die "digitale Elite" (und garantiert auch die vermeintlich zu bekaempfende organisierte Kriminalitaet oder der Terrorismus) arbeitet. Letztlich trifft man dann nur den Otto-Normalverbraucher, und benutzt die Daten dann fuer harmlose Beleidungsdelikte oder Urheberrechtsverletzungen im privaten Bereich.

Issue 77 of the regular publication "DFN Mitteilungen" of the German National Research Network (DFN) reports on Open Source software for GSM networks, specifically OpenBTS and OpenBSC.

I'm happy to see that at least some parts in academia are now discovering this software and use it for research purpose. That's great news!

There is yet another really exciting book that I've been reading lately: GSM and UMTS: The Creation of Global Mobile Communication. It's a book on the history of GSM. From the early days at CEPT, through the creation of ETSI and the GSM MoU Organization, the 3GPP, ...

It puts the development into historical context, indicates who were the key participants at that time, political aspects of the European PTTs that initiated the project, the role of the European Commission, etc.

I've always been looking for this kind of information online anywhere, but there really is nothing that provides any level of detail. Wikipedia e.g. has only two paragraphs (which I believe to be even partially incorrect) on GSM's history. Contrast that with the many writings on the history of the Internet.

The book is accompanied by a CD-ROM with many old meeting notes and other documents from the various stages of the GSM development process.

As you can see in this techworld post.

Apparently they are using the GPL licensed muPDF library and link it against their proprietary PDF viewing application. If that is true, then it would be a very straight-forward, FAQ-type violation. muPDF is not LGPL but GPL licensed, thus you cannot create derivative works without licensing them under GPL, too.

The whole license management and even software release management at Palm seems to be very sloppy. For example, based on the object code and disassembly, I can prove that the source code for libpurpleadapter on opensource.palm.com does not (or no longer) correspond to the object code that they ship.

What's particularly surprising is that Palm actually is forcing Artifex to go to court over this issue. You would expect such a straight-forward issue to be resolved fairly quickly and settled out of court, before it ever escalates or turns into a PR disaster.

You would expect a company that is regularly building and releasing firmware images to have an automatic process that packages the source code as part of the build process. In fact, Palm uses OpenEmbedded to build their images, and it is a standard feature of OpenEmbedded to create the corresponding source tarballs for everything it builds.

Furthermore, the Palm kernel contains several binary-only modules that indicate MODULE_LICENSE("GPL") in it - which is clearly not true. If you inquire about the sources, they will respond that they will not provide the sources.

Especially since the 1.3.1 WebOS release, you can easily see the lack of success of the official Palm App Catalog: Only about 60 Applications are available to me from there. Why is that? Because the default setting in the app catalog for any developer uploading the application is "US Only", i.e. people who bought their Pre in other countries like Germany will not see the majority of applications. That's really weird considering how much effort Palm is spending in trying to convince people to write applications for WebOS to increase the attractivity of their product. Now they artificially reduce that for everyone outside the US.

So that's even one more reason to use the alternative package installer called Preware which is available from webos-internals.org. This alternative installer supports any number of feeds. It removes the single-point of failure that an official Palm App catalog creates, and replaces it with a proper community-driven approach. Anyone can write and publish applications, anyone can distribute them to the users, just like anyone is able to distribute/install MacOS, Windows or Linux applications on the PC!

About 4-5 years ago I first discovered Project Blacksphere, a group of hackers who were working on reverse engineering debug interfaces, as well as the actual phone firmware and hardware of Nokia DCT-3 phones like the 3310. Unfortunately, those projects have meanwhile been discontinued and seem to have died off.

When I last looked at that project, the status was still very limited with regard to the actual GSM side of things. You could run MADos on your phone and run some games inside it. Sure, being able to use the battery charger, keypad, LCM, etc. from your own software on an undocumented device is already great achievement, but if I want a small device without GSM then I just simply use any random PDA or build something myself.

The point about reverse engineering an actual phone is exactly to get what you cannot get from any other piece of hardware: Get access to the lower layers of the GSM protocol stack. Since MADos still looked quite far away from that, I didn't find it particularly interesting at that time.

Today I found a mirror of the project blacksphere, and discovered that apparently they had come much further with reverse engineering the interface between the DSP and the CPU, which is the interface between layer 1 and layer 2 in the GSM stack. If you fully understand that interface, you can write your own GSM stack on the phone and have a true open source phone. The code and information available is not quite at that stage at yet, but very close!

So since I have some 3310 phones (I constantly use them for OpenBSC testing) and the FBUS and MBUS cables, I am definitely going to play a bit with MADos and nlib in its latest known state. It might be the easiest way to write a MS-side layer2 + layer 3 GSM protocol implementation and put it onto an existing Layer 1.

I've arrived in India to attend FOSS.in/2009 in Bangalore. It's always great to be here and get in touch with Indian Free Software developers.

Unfortunately I'm suffering from lack of sleep during the flight and jetlag, so I had to miss large parts of the first day of the event :(

My keynote on Ooening up Closed Domains went fine and was apparently fairly well received. The main points being:

• There are many areas in computing, beyond the desktop PC, where there's still no freedom and openness due to a lack of Free and Open Source Software
• There's no real reason preventing developers to bring FOSS into those areas
• As can be seen by existing projects like OpenPCD, OpenBTS, OpenBSC: Very small teams of developers can make a big difference

During the flight to Bangalore I kept working on the system_information branch of OpenBSC. This branch has been lingering in git for quite some time, but I haven't yet felt confident enough to merge it into the official master.

In OpenBSC so far, the SYSTEM INFORMATION messages (type 1 through 6) are not really generated by actual code. Rather, we use some templates that are patched here and there with actual operational parameters such as the ARFCN of the current cell. This has been easy for the very early start of the project, but it has started to become more of a problem lately.

One example are neighbor cell lists. If you operate a network with multiple cells, then of course you want to provide proper neighbor cell lists. At HAR2009, we solved the problem by manually hard-coding the respective bitmasks. That's of course not a proper solution.

Another problem is the notoriously complex encoding of the rest octets, which culminates in the SI13 REST OCTETS describing the GPRS parameters of a cell.

After a couple of hours in-flight hacking at the code in the sytem_information branch, I am now confident that it provides superior quality SI messages and rest octets than the hard-coded templates we used to have before.

Neighbor Cell lists and even SI13 rest octets are looking great when checking them in the wireshark dissectors. I think it's ready for prime time now, and the code should get merged into the master branch ASAP.

Now I am only left with one question: Should I consider this the first part of the FOSS.in GSM workout? ;)

I'm just about to go to the airport and leave for FOSS.in/2009. Most of my time there will again be spent working out on GSM protocol analysis, i.e. the airprobe project.

The workout wiki doesn't really have any content yet, and I shall fix that as soon as I get the password for the Workout Wiki (apparently passwords from las year don't work anymore).

It's going to be fun to meet all my Indian friends again - and at the same time I'm happy that a large international community will be present, including Stefan Schmidt, Holger Freyther and Andy Green of Openmoko fame, as well as people like Milosch and Brita Meriac from projects like OpenPCD, OpenBeacon and txtr, James Morris of netfilter/iptables and SELinux, Lennart Poettering of avahi and pulseaudio.

During the last weeks, I've read the book The Emperor's Codes: The Breaking of Japan's Secret Ciphers. As you can guess from the title, the book relates to the various UK, American and Australian code breaker teams working on breaking the encrypted communication of Japan during the second world war.

There have been plenty of books about the history of breaking Germany's Enigma ciphering machine, but information on how the Japanese codes were broken so far didn't seem to be as widespread - despite the resepective archives being opened up during the last decades.

It has been a most interesting reading. As you can imagine, at that time almost nobody had a sufficient understanding of the Japanese language, not even thinking about how to encode Japanese writing into morse code.

Nonetheless, all of the Japanese merchant, diplomatic, army and navy codes have been broken during the war. And surprisingly, the Japanese never really assumed something is wrong with their actual encryption method. All they did is to replace the codebook or the additive codebook.

Also, just like in today's GSM (A5/1) crypto attacks, even back then the importance of known plaintext could not be underestimated. The verbosity of Japanese soldiers addressing a superior officer and the stereotypical nature of reports on weather or troop movements gave the cryptographers plenty of known plaintext for many of their intercepted message.

What was also new to me is the fact that the British even back then demanded that Cable+Wireless provides copies of all telegraphs through their network. And that's some 70-80 years before data retention on communications networks becomes a big topic ;)

Overall, definitely a very interesting book. I can recommend it to anyone with an interest in security, secret services, WW2 history and/or cryptography.

Dieter Spaar had pointed out this book some months ago when I first raised some questions regarding frequency hopping and the orthogonal nature of hopping sequences with the same HSN but different MAIO.

Last week while David Burgess was with me, he also indicated that this book was great and he unfortunately didn't think of bringing it along with him.

Meanwhile, I have immediately ordered the book and am already at something like 30% completion. It is a most interesting book to read, approaching GSM from an advanced network planning angle, with a specific focus on the effects of frequency hopping, uplink/downlink power control and DTX on the overall system performance of a GSM network.

The theoretical foundations are always put in a GSM network simulator with detailed channel model, but also actually implemented in a real-world GSM network in Denmark.

Next to all the GSM specifications with their plethora of options and operator dependent settings, this book gives a detailed (but still very technical) background on how and why an Operator would configure his network to maximize the service quality offered to his subscribers.

From the results, you can for example very clearly see that

• frequency hopping over a cyclic sequence gives higher gain improvement than random hopping, especially if the number of channels in the mobile allocation is low
• frequency hopping gain is very dependent on the speed at which the MS moves. At 3kph, the gain when hopping over 8 channels can be 7dB, while at 50kph the same hopping will only provide 1.5dB
• MAIO management (using different MAIO but same HSN) for all sectors in a cell gives significant FER improvements
• handover algorithms differ quite a bit between non-frequency-hopping and frequency-hopping networks

In the end, it seems, network planning is never about allocating your channels in a way they don't overlap. That would limit the network capacity way too much. Network planning seems to only be about averaging out the interference that cells inevitably have with each other and ensure that the quality of the system only degrades with increasing load.

In order to support some real cryptographic authentication in OpenBSC, we have to use SIM cards with a known Ki (secret key). For cards that are issued by a real GSM operator, the Ki is only stored in the SIM and in the Authentication center of the network. Since we cannot obtain it from either of those two sources, we have to program our own SIM cards.

Unfortunately, SIM cards with privileges and/or documentation how to set Ki, IMSI and other data are not readily available on the open market. There are a couple of other solutions, though:

• Use one of the old/cheap 6-in-1 / 16-in-1 SIM cards from the SIM cloning scene
• Implement the GSM 11.11 SIM card spec on a programmable card such as a PIC microcontroller card or Java Card
• Use something like the Bladox products to implement a SIM card or a SIM card proxy

The cheapest option with little R&D overhead is to use the so-called 16-in-1 SIM cards. They allow the user to set some of the interesting bits (Ki, PMLNsel, ICCID, IMSI, SMSP): Sufficient for authentication, but not sufficient for doing arbitrary tricks with the SIM.

Today I spent the better part of the day reverse engineering how both the SIM card as well as the included SIM card reader work. The result can be found in the OpenBSC wiki.

As I've already implemented+tested general authentication and encryption support in OpenBSC, all that is left to be done is some integration, configuration and testing. With some luck we can soon operate OpenBSC with full authentication and encryption support. This in turn will of course help with cryptanalysis and other experiments in a controlled environment :)

On Friday, David Burgess of the OpenBTS project has come to visit me in Berlin. We're working on the final preparation of the two-day Deepsec 2009 GSM Security Workshop which will happen in Vienna next week.

David has more than 10 years experience in implementing GSM Layer 1 as well as the higher-layer protocols, so it's always great to talk with him and tap into his experience. Unfortunately the preparations for the workshop kept us too busy to work on some actual code.

The more than 200 slides for the workshop will be published after the workshop is over.

This is not really current news, as it was released much earlier this year. However, I'm not following Indian news that closely so it has slipped my attention:

India's COAI is setting up hundreds of service centers where end users can have an IMEI programmed into their phone. This apparently relates to the fact that there are plenty of phones of Chinese origin with an all-zero IMEI in India.

Since there is a government law that requires every phone to have an unique IMEI number, operators have been ordered to refuse phones with an all-zero IMEI onto their network.

I personally find all of this very funny:

• Firstly, what law enforcement typically cares about is the subscriber identity (the SIM). Persons are identified by their phone number. The phone number in turn is associated with the SIM. The SIM is issued by the operator and has a world-wide unique number called IMSI. So why would you care about the phone serial number? People can switch their phones much more easily than they can switch their SIM card, since the latter would always mean using a different number.
• Secondly, for most common phones (and particularly the cheaper Chinese phones), tools to program/reset the IMEI are readily available on the Internet. So what's the point for a government initiative to even create more such software, distributed widely across the country. Chances are high that software leaks.
• Finally, if I get a COAI-issued IMEI programmed into my phone, I can at any time erase it again and go back to the COAI to have a new IMEI programmed into it.

So from a real IT security point of view, this entire exercise is nothing but an annoyance to keep people busy and create employment for the staff operating those IMEI programmers.

Tho those involved: Work smarter, not harder ;)

Anyone in the Portland area interested in a fun and creative event is invited to the 1st Timbertalkers Powerpoint® Karoke contest on Tuesday 11/24 at noon.

Meeting location is: 9403-B SW Nimbus Ave., Beaverton, Oregon

If you have never done PPTK, here are the rules:

• Topic is draw from set of 30 topics. Probably 10 to 15 slides
  
• Speaker will have 2 to 3 minutes
  
• Prizes awarded
  

In spirit of open source, it will really be a OpenOffice Impress contest, and the slides will be drawn from Creative Commons licensed decks.

Some 9 months after some idiots have put my car on fire, the german news site Spiegel Online reports on a court trial unrelated to my car, but showing a video of my car.

Quite funny how they always dig out that footage. The court case was about an alleged failed attempt to torch a car, so showing two completely burnt cars in that article is not really sensible anyway.

As you can see from the article, there' already more than 250 burnt vehicles this year in Berlin.

Some weeks ago I was attending Embedded Linux Conference Europe. My personal highlight at this event was the excellent Android Mythbusters presentation given by Matt Porter.

As you may know, Matt Porter was heavily involved in the MIPS and PPC ports of Android, so he and his team have seen the lowest levels of Android, more and deeper than even cellphone manufacturers ever have to look into it.

The slides of his presentation are now available for download. I would personally recommend this as mandatory reading material for everyone who has some interest in Android.

The presentation explains in detail why Android is not what most people refer to when they say Linux. What most people mean when they say Linux is the GNU/Linux system with it's standard userspace tools, not only the kernel.

The presentation shows how Google has simply thrown 5-10 years of Linux userspace evolution into the trashcan and re-implemented it partially for no reason. Things like hard-coded device lists/permissions in object code rather than config files, the lack of support for hot-plugging devices (udev), the lack of kernel headers. A libc that throws away System V IPC that every unix/Linux software developer takes for granted. The lack of complete POSIX threads. I could continue this list, but hey, you should read those slides. now!

Just one more practical example: You cannot even plug a USB drive to an android system, since /dev/sd* is not an expected device name in their hardcoded hotplug management.

Executive summary: Android is a screwed, hard-coded, non-portable abomination.

I can't wait until somebody rips it apart and replaces the system layer with a standard GNU/Linux distribution with Dalvik and some Android API simulation layer on top. To me, that seems the only way to thoroughly fix the problem...

One of my main complaints about the palm Pre is that there is no support for the major IM protocol's such as jabber, icq, aim, msn, ...

As I discovered, they're actually using a library (libpurple) that supports all those protocols. It's just the UI and the intermediate LibpurpleAdapter program which artificially restrict the features that this library offers.

So it sounds to me like palm is getting money or other favors from Google to artificially restrict the capabilities of the Webos messenger.

As I have described in this mail to the webos-internals mailing list, you can actually use a very simple one-byte binary patch to LibpurpleAdapter to enable jabber support.

After that binary patch, you can add jabber contacts with the regular user@jabber-server.doma.in address and use the regular messenger application for keeping in touch with your jabber contacts. Just like how it is supposed to be.

Legal notice: Making this binary patch is legal, since LibpurpleAdapter is actually released under LGPL. If you have a working build environment for the Pre with all the libpurple headers, you can of course modify the source code and recompile it (as explained in the mail).

Side note: The libpurple-adapter source code that Palm has published on opensource.palm.com does not correspond to the actual binary code. This is a LGPL violation. However, since palm is the copyright holder, nobody can really do anything about it. But it once again shows that the software build/release process does not automatically generate the source code packages and that there is an erroneous manual process involved :(

As has been reported at telecomtiger.com, the Commerce Ministry of India has banned the import of mobile phones with no IMEI.

This is somewhat funny, as the IMEI is stored in flash memory in all the phones that I have seen in recent years. Tools to erase or change the IMEI can be found for many popular phones, including (but not limited) to the many MTK based inexpensive phones from China.

So sure, you can now no longer import a device legally with no IMEI, but well, any self-respecting organized criminal will find a way to erase or alter the IMEI anyway ;)

Ubuntu has never been the easiest distribution to do kernel development, but it looks like with 9.10 it has made things too painful. I need to build and install kernels all the time, and usually just update grub menu manually. But now with grub 2 in Ubuntu 9.10 they have wrapped the grub menu in grub-mkconfig. Why?

It would be great if the system was setup so just doing 'make install' in the kernel source put in the kernel and updated the grub.cfg, but no that would make too much sense.

P.s: they managed to break the sky2 driver somehow, the connection won't come up and negotiates the wrong speed. It turned out not to be a kernel problem; wiring issue (speed), combined with some Network Manager changes

So, with my recent evangelizing of Bloom Filters, Tridge decided to try to apply them on a problem he was having.  An array of several thousand of unsorted strings, each maybe 100 bytes, which needed checking for duplicates.  In the normal case, we’d expect few or no duplicates.

A Bloom Filter for this is quite simple: Wikipedia tells you how to calculate the optimal number of hashes to use and the optimal number of bits given (say) a 1 in a million chance of a false positive.

I handed Tridge some example code and he put it in alongside a naive qsort implementation.  It’s in his junkcode dir.  The result?  qsort scales better, and is about 100x faster.  The reason?  Sorting usually only has to examine the first few characters, but creating N hashes means (in my implementation using the always-awesome Jenkins lookup3 hash) passing over the whole string N/2 times.  That’s always going to lose: even if I coded a single-pass multihash, it’s still having to look at the whole string.

Sometimes, simplicity and standard routines are not just clearer, but faster.

I haven’t used an iPhone in anger so I can’t compare, but I got this so I could use Google Maps to navigate public transport: Adelaide’s integration is excellent, and as I have no car it’s important for Arabella and me.

The Good

• Typing on anything that size is suboptimal, but clever auto predict and correct are well done.
• Google maps integration is nice: knowing my location makes getting public transport directions really sweet.
• Since I pay 15c/MB 1.5c/MB for data on the phone network, grabbing onto my home WiFi network where possible is good.
• Google Calendar and contacts storage means I fear obsolete/lost phone much less.
• Plugging in as a USB mass-storage makes transferring music and pictures of Arabella from Linux really easy.
• Some neat features, like turning a map search into a contact (and then easily using a contact when looking for directions).

The Bad

• Intermittent bugs, such as no characters showing up for SMS when the keyboard is in landscape mode, I discovered can be solved by power-cycle.
• My calendar notifications are completely silent.  I’ve played with every option, but when a calendar event comes due, there’s nothing but a glowing trackball to indicate it.  This seems to be a bug, but I’m reluctant to factory reset to see if that fixes it.
• Calendar entries default to My Calendar: if you forget to flip that to your google account when first creating the entry, it won’t be shared.  I want everything mirrored to Google, so several times I’ve had to delete and recreate laboriously-entered appointments.
• I wish the screen would flip faster; landscape makes a better kbd, but portrait often better browsing.
• Sometimes slowness makes it think I held down a key (giving a special character) when I didn’t, and the autopredict/correct seems to give up if you held a key down.
• I have access to Internode’s hotspots around the city, but as that needs a username/password logon, it’s not useful automatically.
• Battery life (in this stage of intense use) is 1-2 days.

I got it from Portagadgets.com, who were efficient (A$487 + $36 shipping, done via local bank transfer).  Getting an account and new SIM from Exetel took longer.

Conclusion: it’s definitely usable by non-geeks, and has raised my expectations of future phones.  There are some things (such as writing this post) which are much easier on my laptop.  But for reading Facebook or Wikipedia, finding your way on Google Maps, or having SMS conversations it’s excellent.

During the last week or so, I've been spending way too much time implementing the network-side GPRS protocol stack as part of an effort to not only provide GSM voice + SMS but also GPRS+EDGE data services with OpenBSC

GPRS is fundamentally very different from the classic circuit-switched domain of voice calls and CSD (circuit switched data). Not only conceptually and on the protocol level, but also in the actual system architecture. They way it was added on top of the existing GSM spec is by making no modification to the BSC and MSC, and only the minimal necessary modifications to the BTS. They then added a new Gb interface to the BTS, and the SGSN and GGSN core network components, who in turn talk to HLR/VLR/AUC.

So in the most primitive GPRS network, you can have the GSM and GRPS domains completely independent, only using the same databases for subscriber records and authentication keys. This goes to the extreme end that your phone would actually independently register with the GSM network (ISMI ATTACH / LOCATION UPDATING) and to the GPRS network (GPRS ATTACH / ROUTING AREA UPDATE). While both of the requests get sent to the same BTS, the BTS will send the GSM part to the BSC (and successively MSC), and the GPRS part to the SGSN.

Also, the actual software architecture looks completely different. In the GSM circuit-switched domain you always have a dedicated channel when you talk to a phone. The number of dedicated channels is limited by the transceiver capacity and the channel configuration. In OpenBSC I chose to simply attach a lot of state to the data structure representing such a dedicated channel. In the packet-switched domain this obviously no longer works. Many phones can and will use the same on-air timeslot and there is no fixed limit on how many phones can share a radio resource.

What's further important to note: The protocol stack is very deep. If you look at the GPRS related output on an ip.access nanoBTS while your mobile phone makes a HTTP request, the stack is something like HTTP-TCP-IP-PPP-SNDCP-LLC-BSSGP-NS-UDP-IP-Ethernet, while the first HTTP-TCP-IP-PPP is obvious, I would not have expected that many layers on the underlying network. Especailly if you look at the almost zero functionality that NS (GSM TS 08.16) seems to add to this stack. Also, the headers within the protocol can actually be quite big. If we only count the number of bytes between the two IP layers in this stack: 8 bytes UDP, 4 bytes NS, 20 bytes BSSGP, 6 bytes LLC and 4 byte SNDCP. That's a total of 42 extra bytes. And that for every small packet like TCP SYN, SYN/ACK or the like! No wonder that mobile data plans have been prohibitively expensive all those years ;)

So with regard to the actual GPRS implementation in OpenBSC, the following things had (or still have) to be done

• Add support for generating System Information 3 + 4 rest octets and System Information 13

This is a very time-consuming bit-fucking experience, encoded relative to the padding pattern of 0x2b. Without this, the phones would not realize that the cell actually supports GPRS. DONE.

• Add support for the ip.access extensions to the A-bis OML (TS 12.21) layer

This is needed to configure the GPRS parameters such as channel configuration, coding schemes or the IP and NS/BSSGP parameters for the link to the SGSN (OpenBSC). Without it, the BTS would not even start to speak NS/BSSGP, i.e. not connect to OpenBSC for GPRS services. DONE.

• Implement the NS protocol (GSM TS 08.16)

Turns out this was really simple, as NS doesn't really do much anyway. DONE.

• Implement the BSSGP protocol (GSM TS 08.18)

This protocol is - among other things - responsible for the flow control. Both globally for the BTS as well as individually for each MS. I've implemented the basic functionality to be able to send/receive signalling and user data, but no flow control yet.

• Implement the LLC protocol (GSM TS 04.64)

This is actually the protocol that is terminated between the MS and the SGSN, so we have moved beyond the BTS level here. Actual data from/to the mobile phone. I've implemented a minimal subset of it, including the CRC24 checksumming. I'm not taking care of packet loss, retransmissions or fragmentation yet. Just simple S, UI or U frames.

• Implement the GPRS mobility management (GSM TS 04.08)

This is pretty much work in progress, but GPRS ATTACH and ROUTING AREA UPDATE is already handled. More work needed here, especially with regard to persistent storage of P-TMSI allocations as well as the last-seen position of every MS in a database.

• Implement the GPRS session management (GSM TS 04.08)

This is the messages for activating and de-activating PDP contexts. Work has not started yet.

• Implement GGSN functionality (PPP tunnel endpoints

After all, we need to terminate the PPP sessions that the phones establish somewhere. Work has not started yet

Once all that full stack has reached a level where it works to a minimal extent, issues like BSSGP flow-control as well as LLC re-transmission, fragmentation and [selective] acknowledgement have to be dealt with.

Finally, if somebody is bored enough, he could also work on things like combined GSM/GPRS attach, or SMS over GPRS.

As you can see, it's quite a large task. But we need to start somewhere, and a lot of this will still be needed when moving into the 3G and 3.5G domain. Even if not at the lower level protocols, but from the software architecture point.

If you're into communications protocol development and don't mind our ascetic 'plain old C language' approach and are interested to contribute, feel free to introduce yourself on the OpenBSC mailing list.

In the last couple of months, I've met numerous people with varying background all sharing one misconception about cellular networks. Even I was not very clear on this until recently: GPRS encryption is very different from GSM encryption. Most people know it uses different algorithms, sure. But it also operates on a completely different layer in the protocol, and is between two different entities.

Encryption in GSM networks happens on the Layer 1 of the Um interface between the MS and the BTS. It is a simple point-to-point encryption of only one particular network interface. There is no more encryption as soon as the signalling, voice and SMS data leaves the BTS (on a microwave link or actual land line) to the BSC, MSC, SMSC and other network elements.

In GPRS, the encryption is not on the Layer 1, but on the Layer 2 (LLC) of the Um interface. As the LLC layer is not terminated at the BTS but at the SGSN, the data is still encrypted when it leaves the BTS.

This means, among other things, that things like eavesdropping on unencrypted microwave links does not work for GPRS anymore.

On December 15, there will be a court hearing by the German Constitutional Court (Bundesverfassungsgericht) on the law on data retention which was enacted in 2007 and has been valid since January 1st, 2008.

This law requires any communications network operator to keep digital records of every voice call and e-mail, including sender and all recipient addresses.

This law was required by the European Union Directive 2006/24/EG, one of those paranoid reactions against the perceived threat of terrorism. Laws implementing this directive in the EU members Romania and Bulgaria have already been invalidated by their respective constitutional court.

In Germany, more than 34,000 (I'm not kidding) people have filed a constitutional complaints against this law. This is the first time that such a significant number of individual citizens has ever made constitutional complaint. Only the documents about power of attorney have filled 12 large boxes, each with many folders. As you could probably guess by now, I'm one of those plaintiffs.

As an interim solution, the constitutional court has already decided on March 19, 2008 that such data can only be used under special circumstances, such as only certain criminal offenses, and only if there is already a very strong initial suspicion, and if there is close to no other way to prove or deny the allegations brought forward by the prosecutor.

I hope the court hearing on December 15 will bring the court closer to actually ruling on this case. This has been dragging on for a long time now.

Just like when the constitutional court had a hearing on voting computers, I am planning to be in the audience and want to see live what the constitutional court does with regard to matters that I strongly care about. I hope my registration will make it in time... given the number of plaintiffs I suppose there will be many more people interested in attending the hearing than they have space. Which raises another interesting issue: I suppose if you are an actual plaintiff, it would be weird if a court refuses you to be at the actual hearing. But which court would hold > 34.000 plaintiffs? ;)

Had an old copy of the “Google Analytics For WordPress” lying around (which didn’t seem to put anything in my blog source), but after upgrading it it kept saying “Google Analytics settings reset to default” whenever I tried to change anything.

See this thread which talks about the problem and waves at the solution.  Here’s what you need to do, if like me you’re not a WordPress/MySQL junkie and want simple instructions:

1. Find your wordpress config file.  Mine, on a Debian system, was in /etc/wordpress/config-rusty.ozlabs.org.php
2. It will contain lines like this:

   define('DB_NAME', 'rustyozlabsorg');

   define('DB_USER', 'rustyozlabsorg');

   define('DB_PASSWORD', 'g1812fbsa');

3. You need to open the mysql database, we’re going to do some brain surgery to remove the old cruft:

   $ mysql --user=rustyozlabsorg --password=g1812fbsa rustyozlabsorg

4. This should give you a “mysql>” prompt, where you type the following:

   DELETE FROM wp_options where option_name='GoogleAnalyticsPP';

5. It should say something like “Query OK, 1 row affected (0.00 sec)”. Then type

   quit;

6. You’re done.  Reload your setting page and try again.

Hope that gets into Google and helps someone else who can’t figure out what’s going on!

Jeff Waugh long ago suggested I switch to Wordpress.  I had a few toy blogs with WP, and it worked well, but the final motivation to stop banging out raw HTML and feeding it to blosxom was that I have a new Android phone (I lost my second-hand one sometime at the last farm visit, so it was time to ask the Ozlabbians who know this stuff what to get: the answer was the HTC Magic).  And being able to blog on the train increases the chance that I’ll actually blog regularly.

As several news sites have been reporting (here a report from LinuxDevices.com), Qualcomm has announced the launch of an Open Source Subsidiary.

As usual, I very much welcome such a move. Qualcomm is one of those companies who have a very bad reputation in the Open Source and particularly Linux community. They have so far failed to provide user manuals or other reference documentation for any of their parts. They haven't even managed to publish reference documentation on the external interfaces such as the AT command dialect or the binary shared memory protocols that are used to interface the GSM/CDMA/WCDMA baseband in their product.

So when it comes to an Open Source project that wants to interoperate with Qualcomms hardware, they have so far been doing everything to make that as hard as possible. Neither the community as large has access to the information that it needs, nor do the Qualcomm customers get the respective document under a license that allows them to actually contribute to Open Source projects.

If that documentation was available, or if Qualcomm was actually working on FOSS licensed drivers and contributing those mainline, the support for Qualcomm's hardware in Linux would be much better - resulting in less time to market for companies interested in using Qualcomms parts in their products.

The actual press release does not indicate that this newly-founded subsidiary truly understands this. It speaks of hardware-optimizing the performance of mobile operating systems. That sounds like "we'll take the existing code, make a fork, do non-portable micro-optimizations and ship that to our customers". It does not mention actually contributing to the community or understanding the benefit that the Open Source development model.

I remain to be convinced. Let's hope Qualcomm has scored somebody with a lot of actual hands-on Open Source community experience to advise them properly.

Using the Palm Pre: Everything but an exciting experience :(

During the last week I've started to use my new Palm Pre (for those of you who're living under a rock: The Palm Pre is a smartphone powered by an Operating System called WebOS, which is in turn powered by the Linux kernel and lots of other "standard" Linux programs like glibc, alsa, udev, ...

This adherence to a more standard Linux userland makes the Pre much more attractive than the Android based products out there. Android is reinventing the wheel everywhere, and things that Linux users and developers have been taking for granted during the last five to ten years simply don't exist on Android.

To be honest, the experience was everything but exciting. More about that later. Lets' start with the positive side of things. Yes, I like the device for the following facts:

• it's using a not-too-ancient Linux kernel
• it uses a fairly standard Linux userland, that
• the development tools are also running on Linux (albeit proprietary)
• there is an easy way to access the command line of the device via USB
• there is software for re-flashing the phone in case it is bricked
• the WebOS "distribution" is built using OE and uses the ipk packet format
• they did not try to lock the device down from their users. You can easily be root on your phone, install additional ipks from third parties and own your phone

Which is what got me excited and made me buy one of those expensive devices.

However, looking at it from a strict user point of view, I am not very happy with it. It simply lacks so much in functionality that it is not even funny.

• No RSS reader

The Nokia web tablets had a working, built-in RSS reader even many years ago when the n770 was released. Given the importance of RSS feeds and blogs in todays web, I'm surprised that webOS does not ship with a RSS reader. To make it even worse, I could not find any third-party RSS reader for it!

• No Jabber / ICQ / AIM support

The messenger supports only SMS and Google Talk. WTF?!? What about the millions of Jabber, ICQ, YIM, MSN and other users? Don't you think they want to use their default messenger application with those accounts? This is particularly funny, since they're using libpurple for the actual messenger protocols, which is a LGPL'd library of the pidgin chat client. So the library has all those capabilities, but Palm decided to arbitrarily remove them in their LibpurpleAdapter program. Luckily that one is LGPL'd too, so removing the restriction is relatively easy. But not for a regular user!

• Some applications always want to use the cellular network, even when wifi is available

This is particularly stupid when using their e-mail client. While I'm at home or in some other area with wifi coverage, I don't want to squeeze every bit through a high-latency cellular network. Why not simply make that decision a per-application property that the user can set?

• Cheap mechanical quality

The mechanical quality is really disappointing for a device that sells for EUR 481. It's much lower than what one is used to from Nokia, Blackberry or HTC devices in a similar price range. As one example, the entire plastic of the device squeaks every time I carefully push one of the keys on the keyboard.

• E-Mail client does not support pre-downloaded messages in subscribed IMAP folders

A standard feature that every desktop e-mail program has: Pre-download and cache the message headers for fast listing / browsing through a mailbox. Not on the Palm Pre, where the interactivity of the mail program is close to zero, fetching every bit over a high-latency link. The entire point of using IMAP is to have local copies/caches and to not suffer the latency/interactivity penalty of e.g. webmail!

• Calendar offers no integration with standard calendar formats/servers

There is no way how you can simply feed data from ical or xcal calender data into the Palm Pre calendar. You can synchronize with Google and Exchange. WTF? Why do we have [more or less] standard file formats for calendar data? Exactly for enabling interoperability.

• No support for standards-compliant address books

You can import your contacts from Facebook, but you cannot import contacts from vcard files, or let's say from a LDAP based address book. Great. So I first need to disclose all the personal contact details from all my contacts, put those into Facebook (into the US jurisdiction and a company that I don't trust) to simply get my contacts on the phone ?!?

• Too low battery life

I can barely make it through one day even without making phone calls, simply having the e-mail client running. The battery is too small. I would not mind a bigger/heavier device in exchange for more power!

That is simply the user point of view. I also have many more technical points from a developer perspective, but that is probably better kept for another post. Meanwhile I'm not sure if the Pre was all that much of a good idea. The N900 is coming up next, and will be much closer to the standard Linux userland stack (including X11, GTK, Qt, ...) than the Palm Pre is.

As most people have noticed by now, The Symbian Foundation has released the source code of their microcernel under an open source license. While any open source release of formerly proprietary software is something I warmly welcome, I doubt that it will take of as an actual open source project.

There's a difference between releasing software under a FOSS license and running a successful FOSS project. The latter involves a sufficiently large community of developers, ways how they can contribute, ...

Especially with special purpose code such as an operating system (kernel) for mobile devices, very few people will show interest as long as there is no actual hardware where they can run the software, without or with custom modifications. Sure, there will be academic interest and people who will look at the source code to find ways to exploit potentially existing security weaknesses, but no community of people who work on it since they will practically use it on their own device.

So what I'd do if I was the Symbian Foundation: I would release an actual mobile phone which is open enough for people to run (modified or unmodified) recompiled parts of the Symbian codebase which are now available as open source. This way it will be much more appealing. However, even at that point, many other parts of the system are (or even will forever be?) closed, limiting the amount of impact. Furthermore, since modified versions cannot be installed on any other regular non-developer phones, the impact of any contribution to the codebase can not be to the benefit of many people. Just compare that with contributing to the mainline Linux kernel, where a contribution will be used on at least almost every server/workstation/laptop after the next distribution (and thus kernel) update.

Another issue that I really was shocked is the following quote by Andrew S. Tanenbaum: 'I would like to congratulate Symbian for not only making the source code of its kernel open source, but also the compiler and simulation environment,' said Andrew S. Tanenbaum'

However, the compiler was not made open source. It is released as proprietary binary code, and is only "free as in beer" for organizations up to 20 employees. So either Tanenbaum did not really look at the hard facts of what was being released, or he was misquoted in a really bad way! That should not have made it into the final release, as it's now a damaging statement for both the Symbian Foundation and Mr. Tanenbaum.

By the way, according to a lwn.net comment thread, they're working on making it able to compile under gcc, and they're actually accepting patches, which is of course great.

Despite my negative comments: I wish them as much luck and success as possible with their new open source Symbian kernel. I personally just am not seeing it turning into a vibrant, community-maintained project - and I hope the founders of the Symbian Foundation did not start the project based on that assumption and will in the end perceive it as a negative experience when evaluating the open source move some years down the road.

One final note: The fact that they chose the EPL as license is really strange, as it prevents exchange of code with the major existing FOSS kernel projects (Linux, *BSD). Not that I think there is much to be exchanged, given the microkernel approach...

So two weeks back was the Official Handing Over Of The SAMBA Team T-shirt! Since then I have done my first serious push to the git tree, and received spam from the build farm about it (false positives, AFAICT).

I'm still maintinging virtio and the module and parameter code of course. But the kernel has slowly morphed into a complicated and hairy place. Formality has crept in, and the pile of prerequisites grows higher (eg. git, checkpatch.pl, Signed-off-by). This is maturity, but it raises the question: when will some neat lean OS without all this baggage come along?

SMP, micro-optimizations, multithreading and extreme portability are responsible for much of the added coding burdens, but also hyper-distributed development means many coders shy away from changes which would break APIs. The suboptimality accretes and this method of working becomes the new norm. BUG_ON() for API misuse is now seen as unduly harsh, but undefined APIs make the next change harder, and WARN_ON() tends to stay around forever.

SAMBA has some brilliant ideas which coding a joy (talloc chief among them, but there are other gems to be found). Hell, it even has a testsuite! But of course it has its own issues; the SAMBA 3/4 split, lack of the kernel's massive human resources and the inevitable code quality issues. Ask me again in a few years to do a comparison...

In case you have been sleeping throughout last week: On October 16, The FOSS.in Call for Participation had been released.

FOSS.in is one of my regular conferences, and probably the only event aside from the Chaos Communication Congress that I managed to visit in five consecutive years. I'm looking forward for this year's incarnation, and I'll definitely do my part to make the event more interesting :)

I hope everyone will now hurry to submit their proposals for talks, workshops and work-outs! It's a collaborative event, and it lives by your contribution.

cnet.com reports some researchers succeeding in performing a differential power analysis (DPA) on a mobile phone in order to "steal cryptographic keys that are used to encrypt communications and authenticate users on mobile devices".

This sounds fishy. At least on GSM phones, the keys for authentication are stored inside the SIM card. And somebody claiming that within a mobile phone with it's many analog RF and digital circuits (causing interference and noise) he can still perform a DPA on the SIM card just simply sounds unreasonable.

I would like to see those results being fully disclosed and independently reproduced before giving them much credibility.

The current encryption session key is not used for authentication, it is very short lived (typically 1 to 5 calls before a new key is negotiated), and it is not considered very safe anyway. The phone writes it to the SIM card, and malware programs installed on the phone are likely to get access to that key anyway. So no need for a DPA here...

I mentioned in my previous post that we had seen tdb corruption (despite the carefully written syncing transaction code) when power failures occurred.

I mentioned (from my previous experience with trying to test virtio_blk) that ext3 doesn't use barriers by default, and that the filesystems should be mounted with "barrier=1". (The IBM engineers on the call were horrified that this wasn't the default: I remember the exact same feeling when I found out!).

I had my tdb_check() routine now, so I patched it into tdbtool and modified tdbtorture to take a -t ("do everything inside transactions") option: killing the box should still allow tdb_check() to pass when it came back. I thought using virtualization, but this isn't easy: killing kvm still causes outstanding writes to be completed by the host kernel (nested virtualization would work). So instead, it was time to use my physical test box.

First with standard ext3. Three times I started tdbtorture -t, then pulled the cord out the back. The first two times, sure enough, the tdb was corrupt. The third time, the root filesystem mounted read only and I fscked, rebooted, same thing, fscked again, rebooted happy. Sure enough, the tdb was corrupt (and one of my previous saved corrupted tdbs was lost, another was in lost+found). I should have forced a fsck on every reboot.

So I edited /etc/fstab to put barrier=1 in, and pulled the plug during tdbtorture again. Surprisingly, I got a journal error and r/o remount again, which shouldn't happen. Still, when I did another double-fsck, the tdb was clean! Two more times (no more fs corruption), and two more clean tdbs.

So it seems, lack of barriers was the culprit. But also note that tdbtorture was 4.8 seconds without barriers, 20 or 28 seconds with them (and this slowdown itself might make errors less likely). This is worse than the 10% that googling suggested, but then tdbtorture is pretty perverse. Three processes all doing three fsyncs per commit, and a commit happening about every 10 db operations.

As can be found here, Knowledge Ecology International, the Open Rights Group and Richard Stallman have issued a joint letter to the European Commission asking it to disapprove the acquisition of MySQL by Oracle.

I very much welcome this move. There clearly is a conflict of interest between Oracle's own proprietary database software offerings and MySQL. Sure, the community could always fork MySQL, but at what cost? Potential disputes about the trademark, being forced to rename itself, and confusion among the millions of users world wide (well, might just be hundreds of thousands).

I am giving three talks: 1) routing performance, 2) staging drivers, 3) Vyatta CLI.
So if you are attending JLS please stop by and give me support.

Last night I got an e-mail by palm, that following-up to my request, the source code releases for the WebOS 1.1.2 and 1.1.3 releases have been uploaded to opensource.palm.com.

I think the response time was very quick, and I thank them for that. However, still sad that one has to remind them of it. Let's hope with future releases they have a fully automatic process for that.

Just to be very clear: The GPL does not state that you have to automatically have the source code on a web site. But the way how Palm's written offer is phrased, they say that you should visit the website to download the sources. In that case, the web site of course needs to contain the sources...

Additionally they also offer the source code on a storage medium, if you write them snail mail to a specific address - which is a good safeguard since the GPL says it has to be made available on a storage medium commonly used for software interchange.

Today, the Berlin-baased start-up txtr has released more technical details on their first e-book reader.

They have also released their developer website including a wiki and access to a svn server with sources as well as fedora11 based source and binary RPM's.

What's also interesting is that they have disclosed a hardware block diagram and a PCB footprint on their developer website before the product even starts shipping to the mass market.

As few of you will know, some my friends and colleagues are behind the system-level software and hardware R&D. The electrical engineering is done by Milosch and Brita of bitmanufaktur, with whom I've had the pleasure to work on OpenOCD, OpenPICC, OpenBeacon as well as for a dedicated assignment inside Openmoko. Andy Green of Openmoko kernel + bootloader hacking fame has also been involved... last but not least for porting Qi (originally developed for the never manufactured Openmoko GTA03 based on the Samsung S3C6410) to the Freescale i.MX31.

Apparently, TI has been trying to use the DMCA and U.S. copyright to stop third-party developers from working on or distributing alternative operating systems for some of their calculators.

The stock OS that TI is shipping uses a cryptographic signature process to prevent the user from booting any non-TI operating system. However, the signature verification was broken and people have managed to run their own software, developed independent from TI's software.

TI is not claiming that the DMCA DRM restrictions are applicable to this case, and that the signature process constitutes a DRM system. This is obviously bogus to any technical person. The TI firmware is not encrypted, and you can copy and run it on other hardware or an emulator if you please. The protection mechanism is rather the other way around: The hardware authenticates the OS.

The Electronic Frontier Foundation has taken up the case and is defending some of the affected people from the community against TI.

As you can see from the EFF letter to TI, the EFF cites a number of precedent cases where the courts have ruled in very similar cases that such mechanism is not a DRM system on the software.

That precedent summarized in the EFF letter is actually very exciting to me. It is directly applicable to all kinds of locked-down devices. Let's assume we're talking about a Linux-powered device like the Tivo, Motorola MAGX phones, the G1 phone (non ADP-Version). They all use GPL Licensed software that is cryptographically signed to prevent the user from exercising his Freedom to run modified versions of the GPL licensed program.

Precedent that indicates that such a system does not constitute DRM as protected by the DMCA means there is a lot more freedom for people to break such systems and freely talk about how it was performed, as well as distribute alternate software images for the respective devices - as long as the code they use is either their own or Free Software and does not contain proprietary bits of the device vendor.

Today, I had the honor to hold the opening keynote of the ST Ericsson Community Workshop 2009.

At this event, ST-Ericsson presented their Nomadik STn8815 SoC, as well as their work on getting the u-boot and kernel ports submitted back into the upstream/mainline projects.

As anyone following the linux-arm-kernel list will have noticed: For the last months, they have worked hard on cleaning up and submitting the code for this SoC. Like many people in the community, I personally appreciate this very much. Finally, ARM SoC vendors actively putting resources to become a "first class" member of the community.

The STn8815 is a ARM926EJ-S core based SoC, including a ST DSP for video codec acceleration as well as a number of standard peripherals such as I2C, SPI, UART, SDIO, etc.

The STn8815 reference software that they released today, includes 100% open source drivers for everything that runs within Linux, inside Linux or on top of Linux on the application processor. The codec implementations inside the DSP are closed source / proprietary. However, the infrastructure to communicate with the DSP, as well as the gstreamer/ffmpeg integration on the Linux side is fully open source.

The attendees of the workshop are receiving the NHK-15 reference boards, which have the STn8815 SoC plus a total of 384MByte NAND flash and 128MByte of DDR memory. There's also a number of peripherals that you expect in such a product, including LCM, SD card slot, Bluetooth, Audio Codec, and Wifi.

Unfortunately, the Wifi driver is closed source. However, the Wifi is a dedicated peripheral component. The use/choice of this Wifi chip on the NHK-15 is probably a bad design choice from an open source point of view. But: This proprietary Wifi does not affect the openness of the actual STn8815 SoC.

Included with the kit for the attendees also a full programming manual as well as register-level specification for the STn8815, as well as the complete schematics of the development board. No NDA required :)

As a summary: I welcome ST-Ericsson to join the Linux community and to provide Open Source friendly solutions, provide the documentation and holding this workshop. However, the STn8815 is already quite 'old' hardware, as it is still ARM9 based - while much of the competition is shipping ARM11 or Cortex-A8 today. Let's hope at some point in the future we will have more competitive hardware with just as much openness.

One great example of why we need more open source based mobile phones is that we can actually discover all the undocumented "features" of the devices that we use every day.

If I use a device for personal things like my private communication, my scheduling, contact information and similar, then I have to put a certain amount of trust into that device. I trust that the vendor selling this device will provide a device that is safe for me to use and where my information is stored securely.

However, the amount of closedness and control that equipment vendors and GSM operators traditionally have in the mobile world is a big conflict with my personal interest for privacy and security.

You can see this reflected by SIM Toolkit specifications that allow the operator to read and modify your phonebook, or with flash over the air where the operator is able to modify the software on your device.

In fact, in such cases the operators treat the device like they own the device, when in fact the customer has bought the device and owns it.

Since Palm's WebOS is [to a large extend] based on Free / Open Source software, we can analyze in more detail what they are doing. As it was pointed out in this blog post two months ago, they seem to regularly receive information when you were using which application, as well as the GPS coordinates of the phone!

This is outrageous, especially without any way for the user to switch it off - or even better: Have an opt-in, i.e. off by default but who wants it can enable it.

Palm has responded to it, but as that very same posting indicates: The Palm Privacy Policy is not even completely listing the information for which it is applicable.

I don't think Palm is particularly worse than other companies. But the question is: How do we know? How does the user know what his phone wants to communicate to the operator or the manufacturer without his knowledge or authorization? The only two ways I can imagine are:

• by having more open source software on the phone, so users can study the code, determine what it is doing and then modify the software to remove such privacy invading surveillance features
• by having more people with their own GSM/GPRS networks with projects like OpenBSC, where we can actually see from the network side what the phone is trying to do. Unfortunately GPRS support is still not finished in OpenBSC, but work is ongoing.

Since the Palm Pre units so far (CDMA and GSM) are not locked down, i.e. you can become root and modify the software, it will be much easier to have "custom ROMs" (where the name ROM is stupid since it is flash, ...)

I can only hope that people will quickly come up with custom Linux based firmware images for the Palm excluding the surveillance features.

In addition, everyone should write a letter to Palm, complaining about those features and the fact there is no way to opt out of them.

Some 4 months ago, I wrote about Palm shipping the Palm Pre CDMA version in a GPL incompliant way. You should assume that the company has learned about their mistakes and created opensource.palm.com as a site to host their source code, compliant with the GPL and other Free Software licenses

Yesterday, the Palm Pre GSM model started to ship in Germany through O2 Telefonica. The WebOS version installed on the device is 1.1.2, and they are doing an OTA upgrade to 1.1.3.

Both of those versions are not available on the Palm opensource website!

Again the same mistake!

I wonder how much this tells us about the development procedures and release management inside Palm. We know they use OpenEmbedded to build their packages and filesystem image. OpenEmbedded can automatically generate the source code tarballs (+ patches), so the entire process of putting them up at the website could and should be automatized. No manual intervention, no mistakes, no license violations.

I have asked my lawyers to send a letter to Palm, demanding immediate release of the complete corresponding source code. If they do not comply, I am prepared to take legal action against O2 who is distributing the devices in Germany. I desperately hope we do not have to escalate to this point. If we go there, I'd better not imagine how upset O2 will be about Palm and how this will affect their business relationship.

It is so easy for Palm to have that source code on their website. We know that for technical reasons (see above). Why are they deliberately exposing themselves to the legal risk? Why are they willing to accept all the negative PR from them not respecting copyright and the GPL?

Please don't get me wrong. I am not set out to continuously complain about Palm. I would like to see more Linux phones. But why do they have to do everything wrong they can do wrong? Why do they not have somebody to advise them on playing nicely with the legal requirements of the technology they use?

I've finally finished the report on the GSM test network at HAR2009, which we operated with OpenBSC in August.

A few years back at a netconf, someone (Robert Olsson maybe? Jamal Salim?) got excited about Bloom Filters. It was my first exposure.

The idea is simple: imagine a zeroed bit array. To put a value in the filter you hash it to some bit, and set that bit. Later on, to check if something is in the filter, you hash it and check that bit. Of course this is a pretty poor filter: it never gives false negatives, but has at about {num entries} in {num bits} chance of giving false positives. The trick is to use more than one hash, and the chances of all those bits being set drops rapidly.

It can be used to accelerate lookups, but we never found a good use for it. Still, it sat in the back of my head for a few years until I came across a completely different use for the same idea.

TDB (the Trivial DataBase) is a simple key/value pair database in a file (think Berkley DB). It has a free list head and set of hash chain heads at the start, and each record is single-threaded (via a "next" entry) on one of these lists. My problem is that even though TDB supports transactions, there were reports of corruption on power failure (see next post!); we wanted a fast consistency check of the database. In particular, this was for ctdb: if the db is corrupt you just delete it and get a complete copy from the other nodes.

A single linear scan would be fastest, rather than seeking around the file. Checking each record is easy, but how do we check that it's in the right hash chain (or the free list), and that each record only appears once? The particular corrupt tdb I was given contained such an infinite loop, which is a nasty failure mode. The obvious thing to do is to seek through and record all the next pointers, and the actual record offsets, then sort the next pointers and see that the two lists match. But that involves a sort and would take 8 bytes per record (TDB is 32 bit, so that's 4 bytes for the next pointer and 4 bytes to remember the actual record offset).

How would we do this in fixed space, even though we don't know how many records there are? What if, instead, we allocate two Bloom filters for each hash chain (and one for the free list)? We put next pointers in the first Bloom filter, and actual located records in the second. At the end, the two should match!

But we can do better than this. Say we use 8 hashes, and 256 bits of bitmap. First off, if the 8 hashes of a value overlap already-set bits, it has no effect and we won't be able to tell if it's missing from the other filter. And if seven bits overlap others (so it only sets one unique bit) then we can't detect a "bad" value which sets that same bit and no other unique bits.

So instead of setting bits, we can flip bits in the bitmap. This means that we can detect a single extra value in one list unless it happens to cancel out its own bits (ie. the hash values all happen to form pairs), and if two values are different they'd need to hit precisely the same bits. This is astronomically unlikely (it's a bit more than 1 in 256! / (8! * 248!), but its still a very small number).

The best bit, of course is that you don't need two bitmaps: a single one will do. Since the two sets of values should be equal, it should be all zero bits when finished!

In practice, all the corrupt TDBs I've gathered have had much more gross errors. But it's nice to finally use Bloom's ideas! The code can be found in the CCAN repository.

For years, I've been working with the GSM specifications by now. My contributions to wireshark, airprobe and most of all the creation of OpenBSC about one year ago further forced me to become very intimate with the various GSM related protocols.

Over the last month or so, I've been looking into some 3G/UMTS specific protocols such as RANAP, as well as more recently at various LTE protocols. It seems like they're more or less all specified in ASN.1 and use a variety of encodings, e.g. PER aligned and unaligned.

Not having useful tools like a code generator for parsing and formatting messages as per those ASN.1 specifications is a major turn-off for starting any Free Software or Open Source project in this area.

It's like having to start from designing tires if you want to build a car. asn1c is a start, but it does not support all the required encodings and even ASN.1 syntax that is used in the 3GPP specs.

I really see a big demand here, otherwise Free and Open Source software development in this area will be severely hampered by the lack of required tools for even more time.

If anyone is interested in helping out to change this, please contact me!

Two days ago, Netgear has announced the so-called "Open Source" WNR3500L router, together with an equally "Open Source" MyOpenRouter community.

The problem with this Open Source router is: It ships with binary-only kernel modules. Not only is this extremely Closed Source, but it also

• has very practical security implications: You can never update your Linux kernel to get the latest security fixes, but have to run vulnerable old kernel versions
• is a very questionable legal practise. Netgear as the vendor is simply relying on the fact that none of the authors who have written parts of the kernel against which their binary-only module links will ever make copyright claims against them

One would have hoped that Netgear did thoroughly study the Open Source market that they're trying to address. Apparently they either did not do that, or they chose to ignore the values/rules by which this community works, or they had somebody with limited understanding to advise them on this.

If anyone has a relationship with Netgear and contacts to the product manager responsible for this product, I would like to ask them for an introduction to that product manager. I would be very happy to help them understand the embarrassment and PR impact that they are putting themselves into by releasing an "Open Source" product that is in fact legally questionable and proprietary.

There are people in the various communities (like OpenWRT or OpenMoko) who have a very clear understanding of what it takes to create a true Open Source product to address the Open Source market. Why are they not asking those experts?

Netgear, you can do much better than that!

As has been described at TechCrunch, Palm has announced to fix their most prominent issues that many bloggers, including myself, palm has realized that they need to fix some issues with the way they are trying to over-control webOs development.

According to the TechCrunch article, Palm will allow people to write and distribute their own applications (though still you need some kind of URL forward from Palm), and there will be no registration or other fees for people who write open source software for webOs.

This is definitely good news. Let's hope the respective changes will be implemented soon.

It's been a while, but I find myself hacking to 3am tonight (virtio_blk needed some love, and it was easier to patch it myself than explain The Right Thing to the patch submitter).

Am seriously tempted to do that tdb hacking now, but I get Arabella tomorrow and I definitely want to face her fully refreshed!

As you can see in this post by Jamie Zawinski, Palm is doing as much as they can to prevent any Free / Open Source application development on their WebOS.

One really has to ask himself whether they have completely lost their mind. This very Free Software and Open Source development model has created the kernel, libc and many other components of their software stack. So Palm can clearly see and experience the benefit this model has to them.

Yet they chose to deprive all third party developers and their users from that very same freedom by

• Not providing a way to install applications from third party websites or even physical storage media, thus
• forcing all application programmers to use their application store, and
• requiring that those application programmers do not disclose the software source or object code on any other website

This is so screwed, I literally want to bang my head on the wall for this level of stupidity. Can somebody please get some sense into Palm? They seem to have not only forgotten what has made their old PalmOS so successful (thousands of 3rd party apps that anyone could write + distribute), but also seem to lack any understanding of Free and Open Source software.