Search Results: "stone"

16 August 2012

Gunnar Wolf: 19 years of Debian

Happy 19th birthday, Debian! The Debian project is 19 years old now. Following Francesca's invitation (and Rapha l's lead, and using Leandro's image, collaboratively as it always happens here), I will tell a bit of my memories: How I got to Debian. I am a Debian user since ~2000, and a Debian Developer since April 2003. But, just as Rapha l's, my history must go somewhat further back in time. In 1992, I got my first 1200bps modem, and almost immediately became an avid BBS user (what's that? Javier Matuk talks [in Spanish] about BBSes in his newspaper column back in 1994). By mid 1993 I started operating my own BBS, CatarSYS. One of the key points that defined CatarSYS is that my focus was large-scale communication. I started connecting to several BBS networks, allowing messages to be relayed to distant people, mainly in the USA and Spain, and getting some feeds that could be seen as the poor man's Usenet. At some point during the year I kept CatarSYS going, I got connected through a strange set of gateways to pure gold: A UUCP feed! This means, during some months, I operated the first (free, hobbyist) service that offered its users a free Internet mail address in Mexico. Yes, it was completely different to what we are used to today. I tried to connect to my provider at least three times a week, but this meant less than one week turnover time for messages sent to people anywhere in the world! But, back to Debian: Via this UUCP feed, I also got some real Usenet newsgroups Including several on the comp.os category. I remember reading about Linux back then, and learning some commands, but didn't really get hooked into it. I was in Israel from July 1994 to June 1995, doing completely non-computer-related tasks. Came back in 1995, and due to my father being an academic, got dialup internet access at home. WOW, *real* Internet! It didn't take me long to start downloading Linux information and floppy images. One failed after another. But before the end of the year, I found in a bookshop a book (that included a CD-ROM) called "Build your own web server with Linux". WOW again Remember this was still 1995! I bought it, and shortly afterwards, I had a Slackware system (Linux kernel 1.0.9) running. That meant many sleepless nights full of joy and frustration (as getting hardware to work was cloe to impossible). By 1996, I got (within one week) my two first real jobs: A systems administrator at a small ISP and a highschool teacher. At the ISP, I got a spare computer to play with Linux, as of course the Big Server was running with Windows NT 3.51. Poor little machine... By then I was already a part of the Mexican Linux User Group. This group had just printed a batch of Linux CDs RedHat 4.0. This was the first release that really made me happy and allowed me to do good work. Together with a friend I took to work with us, Juan Pablo Romero, we installed over a weekend a full replacement for our buggy NT machine, in much cheaper hardware. Of course, Linux was nowhere near corporate-recognition, and our project remained a project, not touching the Windows machine. Anyway... Several years passed, and I was happy with my RedHat choice. I won't mention the milestones and job changes, as it would get boring and leave the point completely aside. By the year 2000, I was quite more involved with the LUG, as well as with the computer security group in DGSCA-UNAM. I became also an OpenBSD user, and had got so hooked up in free software that I felt the need to collaborate: To be a little part of one of those Big Projects that had given me so much. But which one? I have never been much of a programmer Yes, I can solve my everyday needs and have fun with it, and sometimes a bit beyond that. I enjoy programming. But all of my projects have begun little and stayed little. I wanted to join OpenBSD, as it was a community I really believed in, but given my skillset (and given a flame-prone, aggressive developer community), I lost motivation to do so. By 2000, I had also lost faith in RedHat. I don't have the exact dates, so I might be some months off But after RedHat's IPO, I felt a sharp change. Version 7.0 was really demotivating It tried to offer a polished desktop experience, but was really buggy, unstable, and full of bad decisions. In Mexico, Pepe Neif had taken up the job of making a derivative distribution of RedHat (called LinuxPPP), pressing hundreds of CDs and making a teaching program I was part of several times. Talking with Pepe (who continued to release based on RedHat 6), he told me he was interested in switching over to become a Debian-based distribution, but the job of migrating his installed base made the project stall LinuxPPP reached only version 6.4. But I installed Debian in early 2000, and loved it. I started getting familiar with its social philosophy and foundation documents at the same time I started migrating my servers from RedHat to Debian This must have been by Spring 2000, as I installed Potato while it was frozen but not yet stable. By January 2002 I applied for NM. My process took a long time, as my AM got MIA when he had already approved me (but before sending the AM report), so basically I had to go through AM twice And by April 16, 2003, I got accepted as a DD. Contrary to what is acceptable today, I requested the full process to be done before starting to maintain any packages, as I didn't want to bother people with package sponsorship requests, so my whole process was done evaluating packages I would eventually upload. Since becoming a DD, my main involvement in the project has been in packaging groups (I was a pkg-perl founder and member for many years, and am currently working in the pkg-ruby-extras group). But, as I said, my main strength is not programming So my main involvement in Debian has been more social than technical: I have been a DebConf organizer since 2005, a very interesting, stressing, rewarding and (for some months) time-demanding role, and since 2009 I am part of the keyring maintainence team, which is much easier workload, although carries important ramifications. So, after 19 years of Debian, and after nine years of me being part of it, Debian is clearly my strongest link to the Free Software community, a project I have grown to love and whose way of being I share and enjoy studying and explaining. And it is a technically excellent product, and a great place to start and keep learning both about how every aspect and layer of an operating system works, and how human-to-human interaction works in such a diverse, almost impossible environment happens. Congratulations, Debian!
AttachmentSize
debian-19_500.png149.81 KB

6 August 2012

Vincent Sanders: Education is when you read the fine print. Experience is what you get if you don't.

Given my title I guess I just got a load of "experience" from Gandi. Previously I have written about building the NetSurf Continuous Integration (CI) server and my misjudgement of the resources it would require to be useful.

I contacted Gandi and they confirmed my suspicion that my only options to extend the VPS were to spend a great deal more money. The total spend would have been in excess of 300 per year to get a minimally satisfactory configuration.

So I contacted Mythic Beasts and they offered the NetSurf project a selection of deals they could not refuse. Once we decided on the right deal for us the system was in place, ready to use, within a morning.

Thanks to the generous open source project discount the offering from Mythic is almost double what Gandi were offering for less than half the price. I was, as previously concluded, dumb to go with Gandi in the first place when Mythic were an option.

Once the system was transferred to the shiny new server I went back to Gandi and asked how much my mistake of buying a years service for a single month worth of VPS service was going to cost. The reply was somewhat disappointing I was simply referred to section 8.1.2 of the contract (tl;dr We have your money now, tough luck, your problem). It would appear my mistake was going to cost me the full 114 I had paid.

I was somewhat disheartened at this turn of events but then Daniel Silverstone offered to take on the VPS if I could transfer it to his Gandi handle so he could administer it. this seemed like a good solution, at least the resource would be used and not wasted. Gandi response to this was initially promising but this is the final reply:

I'm really sorry to inform you that my supervisor refused the share transfer request to the other account. He told me that we do not transfer products either in those cases. I deeply apologize since I thought it was possible. I thank you for your confidence in Gandi, and hope that this occurrence does not deter you from continuing with us.
Now I must stress that Gandi are completely within their contractual rights to do this and are not obligated to provide any assistance to help make my blunder less costly to me, but they have firmly shown they have no willingness to be flexible in any way which means I know where I will not be spending my money in future.

Oh and then Pete from Mythic mentioned that they have a full refund and flexible policy on their services and we can always switch to the monthly billing rate and get a refund on the outstanding balance or move it or...

Basically my recommendation for an open source project looking for hosting, VPS or any network services has to be to go talk to the nice people at Mythic and steer clear of Gandi. Maybe in future all providers will realise that they are in a competitive market and certainly a little customer service flexibility might have made this posting much more about my mistake and not the attitude of the suppliers involved.

30 July 2012

Johannes Schauer: port bootstrap build-ordering tool report 4

A copy of this post is sent to soc-coordination@lists.alioth.debian.org as well as to debian-bootstrap@lists.mister-muffin.de.

Diary

July 2
  • playing around with syntactic dependency graphs and how to use them to flatten dependencies

July 4
  • make work with dose 3.0.2
  • add linux-amd64 to source architectures
  • remove printing in build_compile_rounds
  • catch Not_found exception and print warning
  • use the whole installation set in crosseverything.ml instead of flattened dependencies
  • detect infinite loop and quit in crosseverything.ml
  • use globbing in _tags file
  • use wildcards and patsubst in makefile

July 5
  • throw a warning if there exist binary packages without source packages
  • add string_of_list and string_of_pkglist and adapt print_pkg_list and print_pkg_list_full to use them
  • fix and extend flatten_deps - now also tested with Debian Sid

July 6
  • do not exclude the crosscompiled packages from being compiled in crosseverything.ml
  • clean up basebuildsystem.ml, remove old code, use BootstrapCommon code
  • clean up basenocycles.ml, remove unused code and commented out code
  • add option to print statistics about the generated dependency graph
  • implement most_needed_fast_wrong as well as most_needed_slow_correct and make both available through the menu

July 7
  • allow to investigate all scc, not only the full graph and the scc containing the investigated package
  • handle Not_found in src_list_from_bin_list with warning message
  • handle the event of the whole archive actually being buildable
  • replace raise Failure with failwith
  • handle incorrectly typed package names
  • add first version of reduced_dist.ml to create a self-contained mini distribution out of a big one

July 8
  • add script to quickly check for binary packages without source package
  • make Debian Sid default in makefile
  • add *.d.byte files to .gitignore
  • README is helpful now
  • more pattern matching and recursiveness everywhere

July 9
  • fix termination condition of reduced_dist.ml
  • have precise as default ubuntu distribution
  • do not allow to investigate an already installable package

July 10
  • milestone: show all cycles in a graph
  • add copyright info (LGPL3+)

July 11
  • advice to use dose tools in README

July 16
  • write apt_pkg based python filter script replacing grep-dctrl

July 17
  • use Depsolver.listcheck more often
  • add dist_graph.ml
  • refactor dependency graph code into its own module

July 18
  • improve package selection for reduced_dist.ml
  • improve performance of cycle enumeration code

July 20
  • implement buildprofile support into dose3

July 22
  • let dist_graph.ml use commandline arguments

July 23
  • allow dose3 to generate source package lists without Build- Depends Conflicts -Indep

July 29
  • implement crosscompile support into dose3

Results

Readme There is not yet a writeup on how everything works and how all the pieces of the code work together but the current README file provides a short introduction on how to use the tools.
  • build and runtime dependencies
  • compile instructions
  • execution examples for each program
  • step by step guide how to analyze the dependency situation
  • explanation of general commandline options
A detailed writeup about the inner workings of everything will be part of a final documentation stage.

License All my code is now released under the terms of the LGPL either version 3, or (at your option) any later version. A special linking exception is made to the license which can be read at the top of the provided COPYING file. The exception is necessary because Ocaml links statically, which means that without that exception, the conditions of distribution would basically equal GPL3+.

reduced_dist.ml Especially the Debian archive is huge and one might want to work on a reduced selection of packages first. Having a smaller selection of the archive would be significantly faster and would also not add thousands of packages that are not important for an extended base system. I call a reduced distribution a set of source packages A and a set of binary packages B which fulfill the following three properties:
  • all source packages A must be buildable with only binary packages B being available
  • all binary packages B except for architecture:all packages must be buildable from source packages A
The set of binary packages B and source packages A can be retrieved using the reduced_dist program. It allows to either build the most minimal reduced distribution or one that includes a certain package selection. To filter out the package control stanzas for a reduced distribution from a full distribution, I originally used a call to grep-dctrl but later replaced that by a custom python script called filter-packages.py. This script uses python-apt to filter Packages and Sources files for a certain package selection.

dist_graph.ml It soon became obvious that there were not many independent dependency cycle situation but just one big scc that would contain 96% of the packages that are involved in build dependency cycles. Therefor it made sense to write a program that does not iteratively build the dependency graph starting from a single package, but which builds a dependency graph for a whole archive.

Cycles I can now enumerate all cycles in the dependency graph. I covered the theoretical part in another blog post and wrote an email about the achievement to the list. Both resources contain more links to the respective sourcecode. The dependency graph generated for Debian Sid has 39486 vertices. It has only one central scc with 1027 vertices and only eight other scc with 2 to 7 vertices. All the other source and binary packages in the dependency graph for the archive are degenerate components of length one. Obtaining the attached result took 4 hours on my machine (Core i5 @ 2.53GHz). 1.5 h of that were needed to build the dependency graph, the other 2.5 hours were needed to run johnson's algorithm on the result. Memory consumption of the program was at about 700 MB. It is to my joy that apparently the runtime of the cycle finding algorithm for a whole Debian Sid repository as well as the memory requirements are within orders of magnitude that are justifiable when being run on off-the-shelf hardware. It must also be noted that nothing is optimized for performance yet. A list of all cycles in Debian Sid up to length 4 can be retrieved from this email. This cycle analysis assumes that only essential packages, build-essential and dependencies and debhelper are available. Debhelper is not an essential or build-essential package but 79% of the archive build-depends on it. The most interesting cycles are probably those of length 2 that need packages that they build themselves. Noticeable examples for these situations are vala, python, mlton, fpc, sbcl and ghc. Languages seem love to need themselves to be built.

Buildprofiles There is a long discussion of how to encode staged build dependency information in source packages. While the initial idea was to use Build-Depends-StageN fields, this solution would duplicate large parts of the Build-Depends field, which leads to bitrot as well as it is inflexible to possible other build "profiles". To remedy the situation it was proposed to use field names like Build-Depends[stage1 embedded] but this would also duplicate information and would break with the rfc822 format of package description files. A document maintained by Guillem Jover gives even more ideas and details. Internally, Patrick and me decided for another idea of Guillem Jover to annotate staged build dependencies. The format reads like:
Build-Depends: huge (>= 1.0) [i386 arm] <!embedded !bootstrap>, tiny
So each build profile would follow a dependency in <> "brackets" an have a similar format as architecture options. Patrick has a patch for dpkg that implements this functionality while I patched dose3.

Dropping Build-Depends-Indep and Build-Conflicts-Indep When representing the dependencies of a source package, dose3 concatenates its Build-Depends and Build-Depends-Indep dependency information. So up to now, a source package could only be compiled, if it manages to compile all of its binary packages including architecture:all packages. But when bootstrapping a new architecture, it should be sufficient to only build the architecture dependent packages and therefor to only build the build-arch target in debian/rules and not the build-indep target. Only considering the Build-Depends field and dismissing the Build-Depends-Indep field, reduced the main scc from 1027 vertices to 979 vertices. The amount of cycles up to length four reduced from 276 to 206. Especially the cycles containing gtk-doc-tools, doxygen, debiandoc-sgml and texlive-latex-base got much less. Patrick managed to add a Build-Depends-Indep field to four packages so far which reduced the scc further by 14 vertices down to 965 vertices. So besides staged build dependencies and cross building there is now a third method that can be applied to break dependency cycles: add Build-Depends-Indep information to them or update existing information. I submitted a list of packages that have a binary-indep and/or a build-indep target in their debian/rules to the list. I also submitted a patch for dose3 to be able to specify to ignore Build-Depends-Indep and Build-Conflicts-Indep information.

Dose3 crossbuilding So far I only looked at dependency situations in the native case. While the native case contains a huge scc of about 1000 packages, the dependency situation will be much nicer when cross building. But dose3 was so far not able to simulate cross building of source packages. I wrote a patch that implements this functionality and will allow me to write programs that help analyze the cross-situation as well.

Debconf Presentation Wookey was giving a talk at debconf12 for which I was supplying him with slides. The slides in their final version can be downloaded here

Future Patrick maintains a list of "weak" build dependencies. Those are dependencies that are very likely to be droppable in either a staged build or using Build-Depends-Indep. I must make use of this list to make it easier to find packages that can easily be removed of their dependencies. I will have to implement support for resolving the main scc using staged build dependencies. Since it is unlikely that Patrick will be fast enough in supplying me with modified packages, I will need to create myself a database of dummy packages. Another open task is to allow to analyze the crossbuilding dependency situation. What I'm currently more or less waiting on is the inclusion of my patches into dose3 as well as a decision on the buildprofile format. More people need to discuss about it until it can be included into tools as well as policy. Every maintainer of a package can help making bootstrapping easier by making sure that as many dependencies as possible are part of the Build-Depends-Indep field.

25 July 2012

Michal &#268;iha&#345;: Weblate hacking #3

As you can see on github, there are currently no open issues for Weblate's 1.2 milestone. Looks like I've done most of my Hackweek VIII project faster than expected, but I might add some more improvements. Everything went quite smoothly, but anyway I've decided to postpone some issues. The major reason is that I'm not really sure whether these are good ideas and won't implement something until I'll get more feedback. You can find such issues labeled "needs decision". Comments there are especially welcome :-). On the code side, I've improved support for po file headers, did various improvements on maintenance scripts and improved about page. Also current code from git is now deployed at demo.weblate.org, so feel free to test it. I'm especially curious how the simple and stupid spam protection will work in reality. Now it's time for ice cream and then I'll think what to implement next :-).

Filed under: English Suse Weblate 0 comments Flattr this!

24 July 2012

Michal &#268;iha&#345;: Weblate hacking #2

Second day of Hackweek VIII is over and there has been again great progress on Weblate. I've started with improving documentation. Most of improvements were possible by using djangodocs extension for Sphinx, which allows better documenting of Django admin commands and settings. Then I've focused on handling languages as there were some things which I did not like. Most importantly, Weblate will now try to use existing languages even if used code does not 100% match (eg. cs_CZ and cs-CZ are treated equal). Also with help of locale aliases, some specific variants won't be created and generic one used instead (eg. cs_CZ will use cs, as these are actually same). If there will be need to differentiate them, you still can create language manually and Weblate will use matched one. Last thing is translation locking - translator can now lock translation for exclusive use and nobody else will be able to work on that. This will help in situations where more people started to work on same translation and basically duplicated the effort. There are 3 open issues targeted for 1.2 release, but I'm not sure if some of these are good ideas, let's keep the decision for next days.

Filed under: English Suse Weblate 0 comments Flattr this!

23 July 2012

Michal &#268;iha&#345;: Weblate hacking #1

The first day of Hackweek VIII is about to end for me and it's time to share some of the results. As planned, I've started hacking on Weblate. The most prominent feature from today are email notifications. You can now monitor the translation in various ways - be informed about new strings to translate, new contributor, added suggestion or simply watch all translations. Another bigger change is rearranging of main page, which now provides instant access to per language stats, which were quite hidden before. Rest of time was spent on adding some sort of spam protection (need to deploy this to demo to see how successful it is) and one more promoting widget (88x31 pixels). There are 6 open issues targeted for 1.2 release, so there is still something to do in next days :-).

Filed under: English Suse Weblate 0 comments Flattr this!

21 July 2012

Andrew Pollock: [life] Sarah sans gallbladder

I can't remember exactly when, it was either pre-Zoe heart-related diagnostic imaging or during her pregnancy with Zoe, that it became apparent that Sarah had gall stones. Apparently it's not uncommon for women to develop them after pregnancy, and it turns out that Sarah is slightly more genetically predisposed to getting them to boot. So it wasn't terribly surprising when she started having some pain recently. She had another ultrasound to confirm it, and went off to see a surgeon. Apparently they care more about the symptoms than the number of stones in the gallbladder, and they don't bother removing the stones and keeping the gallbladder, so she was booked in for a cholecystectomy last Thursday. It was a pretty straightforward procedure, she was out of the operating room in just under an hour, and awake a bit over an hour after that. I've had a few friends need to have a cholecystectomy, and the photos on Wikipedia have always fascinated me, particularly this one. It seems so freaky to have a gallbladder full of that much gravel. It can't be comfortable. We're going to be able to pick up Sarah's stones on Monday, so it'll be interesting to see what they look like. Sarah's recovering now. It's one of the few surgeries she's had under general anaesthesia where she hasn't been sick afterwards, so that was a good start. The procedure was done laparoscopically, using four incisions, and to give themselves room to work, they inflate the body with carbon dioxide gas, which then has to work its way out of her body over the following days. So she's dealing with some bloating, bruising and swelling at the moment, but not doing too badly. Apparently if you're vertical for too long, the gas can work its way up to your diaphragm, which causes some shoulder pain, so the trick has been to walk around a bit, then lie down for a bit, and then rinse and repeat. She's not allowed to lift Zoe for 3-4 weeks, which presents a few challenges for us, but nothing insurmountable (hopefully). We converted Zoe's crib to a toddler bed a week before the surgery, and Zoe thought that was just the best thing ever, and has taken to it really well. I'm around at home for breakfast and dinner, so I can take care of the lifting into and out of the high chair for those meals, and Zoe can eat lunch at her little table. Zoe's also pretty good about getting into and out of the car by herself (not that Sarah can drive until she's off the painkillers) and she's normally in daycare two days a week. She's in daycare again on Monday, so Sarah won't have to deal with Zoe on her own until Tuesday, and we have backup daycare arrangements we can fall back on if need be. Zoe's been very good about Sarah not being able to pick her up, and been very gentle. It helped with the explanation that Sarah could show her all of her "owwies". The surgeon was saying that only 1 in 400 people need to alter their diet after removing their gallbladder, so we're hopeful that Sarah will do just fine without it. She'll certainly be more comfortable in the long run.

17 July 2012

Luciano Bello: there is no cabal.. but, what s a cabal?

In my long trip to Nicaragua I made progress in my reading: Quicksilver, by Neal Stephenson. In the Spanish edition the title is Azogue. But I m assuming that you are not a Spanish speaker. Here is a small fragment (in English) I found there:
You must remember that the planters are short-sighted. They re all desperate to get out of Jamaica they wake up every day expecting to find themselves, or their children, in the grip of some tropical fever. To import female Neegers would cost nearly as much as to import males, but the females cannot produce as much sugar particularly when they are breeding. Daniel had finally recognized this voice as belonging to Sir Richard Apthorp the second A in the CABAL.
It s a bit embarrassing when I discovered myself realizing where the word cabal comes from. And I m posting this as a head-up for everyone who know there is no cabal in Debian; but they don t know which is the origin of the word cabal. Stephenson changed the name of the historic cabal, a group of high councillers of King Charles II of England, Scotland and Ireland, in 1668. In the novel, they are: John Comstock (Earl of Epsom), Louis Anglesey (Duke of Gunfleet), Knott Bolstrood (Count Penistone), Sir Richard Apthorp and Hugh Lewis (Duke of Tweed). In the real world they had been:
Thomas Clifford, 1st Baron Clifford of Chudleigh (1630-1673). Henry Bennet, 1st Earl of Arlington (1618-1685). George Villiers, 2nd Duke of Buckingham (1628-1687). Anthony Ashley Cooper, 1st Baron Ashley of Wimborne St Giles (1621-1683). John Maitland, 1st Duke of Lauderdale (1616-1682).
This group shared the effective power in a royal council rather than the King.

15 July 2012

Steve Langasek: For those who care about my foot

Sitting in the airport during a layover on my way back from DebConf is one of the few times of year that time and motivation come together and routinely lead me to blog. Each year's DebConf has been special in its own way. This year at DebConf 12, in addition to the usual routine of catching up with all my far-away Debian friends, and of making new Debian friends in a country I've never been before, I got a special treat: my first opportunity to experience the practice of medicine in a foreign country. Last Saturday after arriving in Managua, I discovered that the very pretty paving stones making up the hotel walkway were also very slippery when wet, and the thin rubber strips that had been helpfully put in place to make them less slippery did not measurably succeed in doing so. So as it was raining that afternoon (as it does nearly every afternoon this time of year in Nicaragua), I slipped, and made the critical error of not falling. Instead, I stopped my slide - as it happens, by using the big toe of my left foot as if it were a roller skate brake. I don't recommend this, particularly if, as in my case, you already had it on your todo list to consult a podiatrist after DebConf regarding an ongoing feeling of weakness in precisely that part of precisely that foot. So while everything seemed fine the next day, Monday I woke up early with excruciating pain in my foot which, having forgotten about the incident two days prior, seemed to come from nowhere. After favoring the foot for another day and trying to keep the pain at bay using just OTC drugs, by Tuesday my foot was quite swollen and a source of concern. So I visited the clinic on the university campus, where the doctor diagnosed me with a dropped arch plus cellulitis due to bacteria entering through some invisible cut. Conclusion: university campus clinics are equally useless the world over. But at least in addition to pointlessly prescribing antibiotics, the doctor also prescribed some anti-inflammatory drugs to help bring the swelling down. Nevertheless, my questionable mobility kept both me and Patty from attending the day trip on Wednesday, which was a real shame as I had been keen to climb a volcano that day with my fellow Debian Developers (which in the end didn't happen for anyone, but that's a story for someone else's blog). Instead I took it easy for the day at the hotel, together with a few others who had opted not to attend the day trip, catching up on email and other work and hoping matters would improve. But by the end of the day the swelling was as bad as ever, if not worse, and I had no idea what was going on. Was it broken? Was something dislocated? And so I decided that the following day I would go to the hospital. The nearest hospital, as given in the DebConf local information page, is the Hospital Militar. It's a strange sort of thing as an American who remembers the 1980s to be seeking medical care from a facility operated by the Nicaraguan military; but accompanied by Fitoria, my native escort from the local team I had nothing to worry about; and besides, as a frequent international traveler I long ago learned the secret truth that people are people everywhere, no matter what flag they were born under. The highlight of the hospital visit was definitely when a member of the hospital staff, in full military uniform, shooed me towards a chair instead of standing to talk to her because "every patient has the right to sit, no matter what country they're in". After six x-rays and a doctor's consult, the conclusion was that it's probably not a broken bone and that it will probably clear up in just a couple of days with an even-better anti-inflammatory prescription and taking care of it by not walking on it. And indeed, my foot was already feeling better by Friday and aside from a little tenderness is now just about 100%. There are plenty of other entries on Planet Debian talking about the conference itself, and I don't think I have much to add to what's already been said there. But as for Nicaragua, I can conclude that it must be one of the best countries in the world to break your foot in - between the help of the hotel staff, the top-notch medical professionals, and above all the support of the DebConf local team (with a very big thank you again to Fitoria!), this is one brand of socialized medicine I can appreciate.

14 July 2012

Rudy Godoy: svn changelist

Not few times I ve come upon the situation where I m working over a Subversion working copy locally and I wanted to commit bits of what I ve already baked and ready to go. Odds are that there s only one file not belonging to such changeset but mostly there are many files scattered around. This situation, I learned, can be managed with a lot more flexibility and fun.
svn changelist is a nice tool for such situation. svn changelist allows you to create a list of files I want to do something with meaning that you can use the changelist on your usual svn operations, read commit, remove, etc. Let s suppose you start with a project myapp, then you start creating three files A, B and C.
dragon% touch A B C
dragon% ls -lh
total 0
-rw-r--r-- 1 rudy rudy 0 Jul 13 20:16 A
-rw-r--r-- 1 rudy rudy 0 Jul 13 20:16 B
-rw-r--r-- 1 rudy rudy 0 Jul 13 20:16 C
dragon% svn add A B C
A A
A B
A C
dragon% svn ci "first commit of A, B and C" .
Adding A
Adding B
Adding C
Transmitting file data ...
Committed revision 1.
Now we want to edit A and add few pieces of text. Then edit B also.
dragon% echo "This file looks empty, so let's put some text inside it" > A
dragon%
dragon% echo "I'm afraid this one also is empty. Just in case" >> B
Now, I need to work on this C file and that implies touching B also. I don t want to commit the changes I ve already made since I haven t made up my mind about them.
dragon% echo "C is a nice name for a source file, but this one doesn't look like one does it?" > C
dragon% echo "I'm going to add few lines to B too" >> B

dragon% svn st
M A
M B
M C
So, let s suppose I m ready to hit the key and commit the 2nd revision. But I m not done on A, so I want to commit just B and C the way they are now. Here svn changelist enters the arena. I can create a changelist for the two files and do several tasks related to them. Let s see.
dragon% svn changelist mylist B C
Path 'B' is now a member of changelist 'mylist'.
Path 'C' is now a member of changelist 'mylist'.
Now I have a changelist named mylist that I can do operations with. For instance,
dragon% svn st
M A
--- Changelist 'mylist':
M B
M C

dragon% svn diff --changelist mylist
Index: B
===================================================================
--- B (revision 1)
+++ B (working copy)
@@ -0,0 +1,2 @@
+I'm afraid this one also is empty. Just in case
+I'm going to add few lines to B too
Index: C
===================================================================
--- C (revision 1)
+++ C (working copy)
@@ -0,0 +1 @@
+C is a nice name for a source file, but this one doesn't look like one does it?
Now let s commit the list.
dragon% svn ci -m "Comitting files from the mylist changelist" --changelist mylist
Sending B
Sending C
Transmitting file data ..
Committed revision 2.

dragon% svn st
M A
Now that I ve committed the files, the changelist mylist vanishes from our working copy. I cannot do any new operations with it. Few things you have to consider when using svn changelist.
changelist s are created in a one-time list, that means you cannot add another file to an existing list. If I type svn changelist mylist A it will define the changelist mylist to have just one member, A. It will not add A to the existing member files, B and C. Now, you are free to remove any file from an existing changelist using svn changelist mylist --remove B, for our previous example. That will make the changelist shrink to just have one element, C. You can also have as many changelists as you want, and member files can be associated to each one of them. Use case for that could be a diff over specific files. For this test project it almost makes no difference using this feature, but when you have lots of file sitting modified on your working copy, this feature will keep your hair on it s place, and maybe save the day. svn changelist is available since Subversion 1.5.

7 July 2012

Keith Packard: FEC

Forward Error Correction with the TI CC1120 Sub-GHz transceiver We re building a new, fancier flight computer and decided to give the new, fancier TI CC1120 chip a try. It has significantly more transmit power (+16dBm) and receive sensitivity (-109dBm) than the transciever built in to the TI CC1111 RF SoC that we ve built our other boards with. Given that we d already decided to use a fancier STM32L processor, using the nicest stand-alone radio chip we could find seemed to make good sense. One of the nice features found in the CC1111 is support for FEC using a 1/2 rate constraint length 4 convolutional code. Both the encoder and the soft-decision Viterbi decoder are built right into the chip; all we had to do was flip a couple of bits and we got error correction, interleaving, data whitening and CRC checking all for free. We assumed that, as the CC1120 was advertised as a better replacement for our CC1111 radio, that it would also include all of these fine features. After we got the chip all soldered down to our first prototype boards, we read through the reference manual looking for the right register values to flip for forward error correction. We found support for CRC computation and data whitening, but no mention of interleaving or forward error correction at all. Thanks, TI. Of course, without the FEC pieces, the other packet handling hardware is worthless you can t exactly do a CRC on the encoded data and expect it to be useful on the other end of the link, and data whitening happens after the CRC. Basic CC1120 driver I assumed I d eventually figure out something to do about the FEC pieces and started writing a basic CC1120 driver AltOS, the operating system used in all of our projects. I started with the transmit side, as that seemed easier as I could use the existing packet hardware by uploading the desired bit sequence using whatever fancy encoding desired and the hardware would happily transmit it. I first tested that using low data-rate bits (2kbps), transmitting an alternating sequence of zeros and ones to generate a 1kHz tone on a regular 70cm receiver. That seemed to work just fine, demonstrating that I had some grasp of the basic operation of the chip. Convolutional Encoding in Software Not to be daunted by a small challenge in software, I set out to replicate the encoding scheme used in the CC1111 chips for use in our CC1120-based design. We obviously want our CC1120 boards to interoperate with the CC1111 boards. Fortunately, TI fully documents the CRC, data whitening, convolutional encoding and interleaving done in the hardware. I created my own implementation of the encoder (licensed, as usual, under the GPLv2) which you can see in the file ao_fec_tx.c It s not quite as flexible as the hardware, it always whitens the data and always appends the CRC bytes to the end of the packet, along with the necessary trellis termination bytes. The core of that code is surprisingly simple:
static const uint8_t ao_fec_encode_table[16] =  
/* next 0  1      state */
    0, 3,   /* 000 */
    1, 2,   /* 001 */
    3, 0,   /* 010 */
    2, 1,   /* 011 */
    3, 0,   /* 100 */
    2, 1,   /* 101 */
    0, 3,   /* 110 */
    1, 2    /* 111 */
 ;
uint8_t
ao_fec_encode(const uint8_t *in, uint8_t len, uint8_t *out)
 
    uint8_t     extra[AO_FEC_PREPARE_EXTRA];
    uint8_t     extra_len;
    uint32_t    encode, interleave;
    uint8_t     pair, byte, bit;
    uint16_t    fec = 0;
    const uint8_t   *whiten = ao_fec_whiten_table;
    extra_len = ao_fec_prepare(in, len, extra);
    for (pair = 0; pair < len + extra_len; pair += 2)  
        encode = 0;
        for (byte = 0; byte < 2; byte++)  
            if (pair + byte == len)
                in = extra;
            fec  = *in++ ^ *whiten++;
            for (bit = 0; bit < 8; bit++)  
                encode = encode << 2   ao_fec_encode_table[fec >> 7];
                fec = (fec << 1) & 0x7ff;
             
         
        interleave = 0;
        for (bit = 0; bit < 4 * 4; bit++)  
            uint8_t byte_shift = (bit & 0x3) << 3;
            uint8_t bit_shift = (bit & 0xc) >> 1;
            interleave = (interleave << 2)   ((encode >> (byte_shift + bit_shift)) & 0x3);
         
        *out++ = interleave >> 24;
        *out++ = interleave >> 16;
        *out++ = interleave >> 8;
        *out++ = interleave >> 0;
     
    return (len + extra_len) * 2;
 
ao_fec_encode_table takes care of the convolutional piece, ao_fec_whiten_table (not shown) contains the data whitening codes while the little loop at the bottom does the interleaving. I didn t spend a lot of time optimizing this as it seemed to run plenty fast on the 32MHz processor. With the bits all nicely encoded, I passed them to my simple CC1120 driver and let it send them along to our CC1111 receiver. Much to my delight, with only a few bugs fixed, it worked just fine! I d managed to get one direction working, validating the hardware and making it clear that we d at least be able to use the board in flight for telemetry. Getting Soft-decision data out of the CC1120 In packet mode, the CC1120 receiver converts the incoming GFSK stream directly into bits, making its best guess as to whether the detected value was a one or zero. Of course, like any FM modulation, the receiver will be producing intermediate values, especially when the signal is weak or masked by interference. A Viterbi decoder can make good use of this information;these noisy intermediate values are less influential in the final resulting path cost which allows the strong 0/1 values to pull the solution to the right one. Soft decision decoding yields a theoretical 2dB gain over hard decision decoders, and given our desire for maximum packet reception over long distances, it seemed important to make this work. The CC1120 has a way to recover the soft decision values, but only one 8-bit value at a time. It does, however, helpfully provide a GPIO wire which can be programmed to interrupt the CPU when the soft decision data has arrived. So, I hooked up a GPIO line on the processor to the GPIO line on the CC1120 and let it interrupt once per bit time, or 38400 times per second, to read this valuable soft decision data out of the radio part. According to TI support, this is the only way to make this work, and that they generally recommend that developers use the packet mode stuff and throw away this valueable source of data. I was happily surprised to learn that the STM32L can in fact survive this interrupt rate, and by setting interrupt priorities appropriately, I manage to reliably capture an entire packets worth of data without dropping a single bit. I set up a simple packet dumping function to run on the prototype board and captured raw encoded bytes from our CC1111-based flight computer so that I d have some real data to work from. Soft-decision Viterbi Decoding The sample encoding implementation from TI made that piece fairly straightforward. Lacking a similar sample for the decoding piece meant that I d be starting from scratch. And, implementing something that seemed like magic to me when I started. I started by reading a few articles on Viterbi decoding: I found Chip Fleming s tutorial very useful as it included a bunch of worked examples using a convolutional encoders with constraint length (k) of 3 instead of 4; this makes all of the trellis diagrams half the size. I also sent my friend, Phil Karn, a query about this process, and he responded with a bunch of helpful suggestions, while also recommending that I just steal his DSP and FEC library implementation. Of course, I don t like using code that I can t understand, and his code only implements much longer codes than I needed, so I d have to understand it anyways to make it work for me. Phil s code is a marvel, but it s not exactly comprehensible to someone who doesn t even know what a Viterbi decoder is supposed to do. So, with Chip s tutorial on my screen, I wrote a primitive Viterbi decoder. This did only the Viterbi step, and split that into two phases. The first computed the cost for each state in the system for every received pair of symbols received. It also tracked the chain of states through the entire decode process:
    for (state = 0; state < 8; state++)  
        struct ao_soft_sym zero = ao_soft_sym(ao_fec_encode_table[state * 2 + 0]);
        struct ao_soft_sym one = ao_soft_sym(ao_fec_encode_table[state * 2 + 1]);
        uint8_t zero_state = ao_next_state(state, 0);
        uint8_t one_state = ao_next_state(state, 1);
        int zero_cost = ao_cost(s, zero);
        int one_cost = ao_cost(s, one);
        zero_cost += cost[b][state];
        one_cost += cost[b][state];
        if (zero_cost < cost[b+1][zero_state])  
            prev[b+1][zero_state] = state;
            cost[b+1][zero_state] = zero_cost;
         
        if (one_cost < cost[b+1][one_state])  
            prev[b+1][one_state] = state;
            cost[b+1][one_state] = one_cost;
         
     
At the end of the packet, it found the least costly path and walked that from back to front, generating output bits (yes, one bit per element of the bits array):
for (state = 1; state < 8; state++)  
    if (cost[b][state] < c)  
        c = cost[b][state];
        min_state = state;
     
 
for (b = len/2; b > 0; b--)  
    bits[b-1] = min_state & 1;
    min_state = prev[b][min_state];
 
Completely separate from this code were the interleaving and data whitening stages. Keeping those separate allowed them to be tested independently, which made debugging them far easier. None of this code ever ran on the STM32L processor, it was instead run in a test framework on my laptop. I first got this working with data generated by the software convolutional encoder, then I managed to get it to decode the raw packets that I had recorded directly from the receiver it self. This marked a significant milestone in my mind I d managed to replace, in software, the CC1111 FEC encoder and decoder. However, the decoder performance was not fast enough to manage back-to-back packets yet. Having something in hand that worked meant that further development would be directly comparable to something that did work, making optimization much easier. Yet another lesson in making it work, and then making it work fast. Optimizing the Viterbi Decoder The first step was to reduce memory usage within the decoder. While it s best to defer computing the path until the very last bit has been received, it s also true that the chances of a bit affecting old data reduces as the distance between the new and old data increases. With the rule of thumb being a distance of k 6 or k 7, I saved 32 output bits for each state and wrote the oldest of 8 each time the buffer filled up, making a distance of 24 bits between the newest saved data and the current decoding position. That meant a fixed amount of storage was needed for an arbitrarily long packet. I tested a variety of different history sizes from 8 to 56 bits (cooresponding to 16, 32 and 64 bits of saved data for each state). With 100000 random packets generated that had gaussian noise added to each bit, here are the error rates for the different history lengths:
History LengthTotal PacketsCorrectIncorrect
8 bits10000090520 (90.52%)9480 (9.48%)
24 bits10000093614 (93.61%)6386 (6.39%)
56 bits10000093620 (93.62%)6380 (6.38%)
The performance of the 8-bit history and 16-bit history versions turned out to be essentially identical (given the 32-bit nature of the STM32L, that shouldn t be too surprising). The performance of the 56-bit version, which manipulated uint64_t data types was sigificantly slower, and given the very modest benefit, deemed not worth it. If we move to a larger constraint length (k > 4), or started using a punctured convolutional encoding, we would want to re-measure this. The next step was to combine the de-interleaving, decoding, de-whitening and CRC computation into a single loop. This would eliminate a pile of data copying and extra memory usage. Nothing fancy here, but it made enough of a difference that I could decode most of the incoming packets now, dropping only about 25% of them. To get to being able to decode every packet, I needed to start decoding the packet while it was being received. Because of interleaving, I had to have 32 bits of data to be able to decode anything, so it was a simple matter of having my per-soft-value interrupt handler start the decoder going after each interleave block of data was received. With this in place, I was able to decode a 76-byte payload (160 transmitted bits) in 14.7 ms, or just about 50% of the time it took to transmit the packet. Unrolling one of the inner decoding loops eliminated a bunch of computation and sped this up even more, decoding packets in 9.5ms. Success at last, a solid 100% of packets received were being decoded, as long as the CPU was otherwise idle. Finally, I went and re-read Phil Karn s code and pondered over how it works. It was opaque until I wrote a message back to Phil asking how it worked and pointing out sections that were confusing. Fortunately, simply phrasing my confusion in words made me understand how the code works. Here s my original code for computing the per-state cost metric:
/* Metric for a zero bit */
uint32_t    bitcost = ((uint32_t) (s0 ^ ao_fec_decode_table[(state<<1)]) +
               (uint32_t) (s1 ^ ao_fec_decode_table[(state<<1)+1]));
 
    /* Total path metric and state for a zero bit */
    uint32_t    cost0 = cost[p][state] + bitcost;
    uint8_t     state0 = ao_next_state(state, 0);
    /* Compare the total path metric against all existing
     * metrics heading into the same new state, choosing
     * the least expensive and killing the others.  Record
     * the new lowest cost and output bit.
     */
    if (cost0 < cost[n][state0])  
        cost[n][state0] = cost0;
        bits[n][state0] = (bits[p][state] << 1)   (state & 1);
     
 
 
    /* Total path metric and state for a one bit.  Because
     * encoding a one is always exactly the opposite of
     * encoding a zero from any state, this cost is
     * 255*2 - bitcost
     */
    uint32_t    cost1 = cost[p][state] + 510 - bitcost;
    uint8_t     state1 = ao_next_state(state, 1);
    if (cost1 < cost[n][state1])  
        cost[n][state1] = cost1;
        bits[n][state1] = (bits[p][state] << 1)   (state & 1);
     
 
Before this loop is run, I have to initialize cost[n] to a large value so that the comparisons will be true for the first case to reach each state. Phil s code, in contrast, doesn t have to initialize cost[n] as we know which two states can reach any possible new state. His code looks like this:
/* Metric for a zero bit */
bitcost = ((uint32_t) (s0 ^ ao_fec_decode_table[(state<<1)]) +
       (uint32_t) (s1 ^ ao_fec_decode_table[(state<<1) 1]));
/* Only state and state+4 reach state<<1 with a zero bit */
/* Cost from state to state<<1 for a zero bit*/
m0 = cost[p][state] + bitcost;
/* Cost from state+4 to state<<1 for a zero bit */
m1 = cost[p][state+4] + (510 - bitcost);
/* Which source state is cheaper? */
bit = m0 > m1;
/* Record the cheaper cost and the add to the path of bits */
cost[n][state<<1] = bit ? m1 : m0;
bits[n][state<<1] = (bits[p][state + (bit<<2)] << 1)   (state&1);
/* State and state+4 reach (state<<1)+1 with a one bit */
/* Cost from state to (state<<1)+1 for a one bit */
m0 -= (bitcost+bitcost-510);
/* Cost from state+4 to (state<<1)+1 for a one bit */
m1 += (bitcost+bitcost-510);
/* Which source state is cheaper? */
bit = m0 > m1;
/* Record cheaper cost and add to the path of bits */
cost[n][(state<<1)+1] = bit ? m1 : m0;
bits[n][(state<<1)+1] = (bits[p][state + (bit<<2)] << 1)   (state&1);
This code does two states at a time, and so while it s slightly longer than the above, it only needs to run half as many times. The resulting code now decodes packets in 5.7ms. The final version of the code can be see in ao_fec_rx.c The whole AltOS operating system, with many drivers and support for CC1111, AVR and STM32L processirs is available, under the GPLv2 from git://git.gag.com/scm/git/fw/altos

5 July 2012

Joey Hess: git-annex-assistant milestone

I reached a nice milestone on my git-annex assistant in my first day's work at DebCamp in Nicaragua. Here's a screencast demoing it. <video controls="controls" src="http://joeyh.name/screencasts/git-annex-assistant.ogg"></video> git-annex-assistant.ogg (12 MB) By the way, the weather, food, and people here are all excellent.

2 July 2012

Johannes Schauer: port bootstrap build-ordering tool report 3

A copy of this post is sent to soc-coordination@lists.alioth.debian.org as well as to debian-bootstrap@lists.mister-muffin.de.

Diary

June 18 Pietro suggests a faster way to generate installation sets for a list of packages. In my case, I need an installation set for every source package in the archive to find out how often a binary package is needed to build a source package. As a result, the speed is doubled in contrast to the original approach.

June 19
  • adapt code to work with new dose release 3.0
  • remove unneeded parts of code
  • add different possibilities to find amount of source packages that need a binary package
  • add code to get multiple installation sets using Depsolver_int.solve

June 20
  • add ~global_constraints:false to Depsolver.listcheck, Depsolver.trim and Depsolver.edos_install calls
  • adapt output graph to limited xdot capabilities

June 21 I formulate an email to the list, reporting of dependency graphs of debhelper, cdbs, pkg-config and libgtk2.0-dev. My current technique gets an installation set for a source package, removes all those that are already installable and adds the others as a dependency of that source package. This dependency will include an installation set of that binary as well minus all packages that are already available. The problem with that approach are dependency cycles created by long dependency chains. Example: src:A needs B needs C needs A. B and C would both be added as a dependency of src:A. B as well as C would also include their installation set which in both cases includes A. So now there are two cycles: src:A->B->A and src:A->C->A. For a real life example, look at the following situation of cdbs and src:sqlite3. cdbs old situation It is created because src:sqlite3 needs cdbs needs python-scour needs python needs python2.7 needs libsqlite3-0. Therfor libsqlite3-0 is in the installation set of cdbs, python-scour, python and python2.7. This creates five cycles in the graph even though there is only one. It would be better to reduce the dependencies added to src:sqlite3 to its direct dependency which is cdbs. Package dependencies are disjunctions from which the solver chooses one or the other to build an installation set. To solve the problem above I would need to know which disjunction the solver chose and then only add the direct dependency of a package to the dependency graph.
  • improve build_compile_rounds performance
  • big overhaul of menu structure
  • fix subgraph extraction code

June 22
  • do not create a universe if not needed - use hashtables instead
  • for sorting packages, generating difference of package sets and otherwise comparing packages, always use CudfAdd.compare
  • as a custom list membership function, use List.exists instead of trying List.find
  • more speedup for build_compile_rounds
  • the number of source packages that can be built does NOT include the cross built packages
  • print closure members in graph
  • refactor code and move common functions to bootstrapCommon.ml
  • add breakcycles.ml for future code to break cycles using staged build dependencies
  • use more extlib functionality
  • extended package list input format

June 23 After several emails with Pietro I learn about syntactic dependency graphs. To document my progress and prove my efforts I committed the code as commit 6684c13. But this code was soon found out to be unecessary so it will be removed later and just serves as documentation.

June 24 I came up with another (better?) solution to get the chosen disjunctions. It simply uses the calculated installation set to decide for each disjunction which one was taken by the solver. I reported that important step and the open questions involved with it in an email to the list. The problem always was, that an installation set can easily contain more than one package of a disjunction. In this case it is not clear which branch was chosen by the solver. I found, that in Ubuntu Natty there are only 6 such packages and for each of them the situation can be solved. It can be solved because in all of those cases it is that either one package of a disjunction provides the other or that both packages depend upon each other, which means that both have to be included.

June 27
  • use installation set to flatten build dependencies of source packages
  • refactor code and move common functions to bootstrapCommon.ml

June 25 I have to have an algorithm that finds all circuits in a given graph. This is necessary so that:
  1. cycles can be enumerated for huge dependency graphs where cycles are hard to see
  2. cycles can be enumerated to find a cycle that can be broken using staged build dependencies
It seems that Johnson's algorithm is the best way to do this complexity wise and Pietro already blogged about the problem together with an implementation of the algorithm in ocaml. Unfortunately it turns out that his code doesnt implement the algorithm correctly and hence misses out on some cycles. The fix seems not to be too trivial so I'm still investigating it.

June 28
  • add crosseverything.ml to obtain a list of source packages that, if cross compiled, would make the whole archive available

Results While the first week was productive as usual, I had to work some time on a University project during the second week as well as attend a family meeting. I will catch up with the lost time over the course of the next week.

dose3 Using dose 3.0 (which fixes a bug about essential packages) the output of the algorithms is now likely less wrong then before.

performance Performance was improved in the generation of installation sets as well as in the code that tries out how many packages can be built in multiple rounds. This was achieved by more caching, less unnecessary operations in looping constructs, replacing lists with hashtables, not creating universes where not necessary.

user interface The main program, basenocycles.ml now has a much better menu structure.

input format The programs take two package file inputs. The list of source packages that has to be cross built for a minimal build system and the list of source packages that was chosen to be cross compiled in addition to that. Both files list one source package per line and now allow comments.

refactoring As more and more scripts are added, more and more functionality is moved to bootstrapCommon.ml which makes each script much cleaner.

what to test for cross building As discussed in the "Future" section of the last report, I now automated the process of finding out which packages, if they were cross compiled, would make the whole archive available because they break all cycles and allow native compilation of the rest. The outcome: to build 3333 out of 3339 packages in natty natively, at most 186 source packages must be cross compiled. The other six cannot be compiled because of version mismatches in the Natty Sources.bz2 and Packages.bz2. The code can be run from crosseverything.ml.

limit source dependencies to direct dependencies Reducing the dependencies of source packages from their full installation set to their direct dependencies by finding out which disjunction of their dependency list were taken, greatly simplifies the dependency graphs. The dependency graph created for libgtk2.0-dev could be reduced from 491 to 247 vertices for a depth of three. For cdbs it is now clearly visible that cdbs depends on libsqlite3-0 which builds from src:sqlite3 which depends on cdbs. Before: cdbs old situation After: cdbs new situation For pkg-config the graph also has been reduced to the one single cycle that matters: src:pkg-config needs libglib2.0-dev which depends on pkg-config which builds from src:pkg-config. Before: pkg-config old situation After: pkg-config old situation

Future I will prepare content for wookey's debconf talk on crossbuilding and bootstrapping. As this will include directions how to use the current code, I will kill two birds with one stone and write some proper documentation for my current source. The following two lists will be displayed after a dependency graph is calculated and reduced to its scc:
  • those source packages that have the least build dependencies not fulfilled. Those might be candidates for easy staged build dependencies. Since the source package is part of the scc, it will definitely be involved in some cycle somewhere.
  • those binary packages that most source packages depend upon. Those could be candidates for cross compilation as it might be easier to cross compile the source package than using staged build dependencies.
Patrick managed to cross build packages with sbuild now. So the list of packages that crosseverything.ml produces can now be checked efficiently for cross buildability. With this list, potentially more cycles can be broken out of the box. A feature will be added that allows the user to remove all packages from a dependency graph that can be cross compiled without any additional effort. Version mismatches between source and binary packages in Sources.bz2 and Packages.bz2 respectively in Ubuntu make the scripts fail and/or produce wrong results. Debian (even Sid) doesnt have this problem so I should find out where to report this problem to Ubuntu. I need to write a working version of Johnson's algorithm because much functionality depends upon it. I have the option to improve Pietro's version or write one from scratch. Writing one from scratch might be easier as I have Pietro's code as template as well as a Java implementation of Johnson's algorithm which seems to work. The following functionalities need working cycle enumeration:
  • given source packages with staged build dependencies, an enumeration of cycles is needed to find out which cycles can be broken by building packages staged. It makes less sense to blindly build a package stage and then check if this makes more packages available.
  • display cycles of a dependency graph to the user. After obtaining all cycles in the graph it makes sense to sort them by their length. The user would then investigate the situation of the smallest cycles first. This makes sense because breaking small cycles can potentially break bigger cycles. Since in the end, all cycles have to be eliminated anyway, it makes sense for the user to first tackle the small ones.
  • display the feedback arc set to the user. The packages in the feedback arc set might be very good candidates for reduced build dependencies or cross compilation.

27 June 2012

Michal &#268;iha&#345;: Weblate - over 20000 translations in 3 months

Today, I wondered how much translations were done using Weblate since it was born. Of course I can give only numbers for services I maintain, the biggest one being translation server for phpMyAdmin, Gammu and Weblate. Looking at the logs, the server l10n.cihar.com helped to contribute over 20000 (actually little bit more as tracked are only changes after releasing Weblate 0.8), what is quite impressive number. Of course biggest amount of contributions came in time of preparing phpMyAdmin 3.5.0 release, where I gave it huge amount of publicity (AKA spamming my blog), but number of people accessing the website still grows since then (still number of submitted translations is slightly lower). Now as 1.0 release proved to be quite stable, it's time to focus on 1.1 development, which will bring offloading of fulltext indexing (it was proven to be unreliable to update index online for bigger sites). Almost all issues targeted for 1.1 are already fixed and all what needs to be done is testing in real life situations.

Filed under: English Phpmyadmin Weblate 0 comments Flattr this!

8 June 2012

Lars Wirzenius: Obnam 1.0 (backup software); a story in many words

tl;dr: Version 1.0 of Obnam, my snapshotting, de-duplicating, encrypting backup program is released. See the end of this announcement for the details. Where we see the hero in his formative years; parental influence From the very beginning, my computing life has involved backups. In 1984, when I was 14, my father was an independent telecommunications consultant, which meant he needed a personal computer for writing reports. He bought a Luxor ABC-802, a Swedish computer with a Z80 microprocessor and two floppy drives. My father also taught me how to use it. When I needed to save files, he gave me not one, but two floppies, and explained that I should store my files one one, and then copy them to the other one every now and then. Later on, over the years, I've made backups from a hard disk (30 megabytes!) to a stack of floppies, to a tape drive installed into a floppy interface (400 megabytes!), to a DAT drive, and various other media. It was always a bit tedious. The start of the quest; lengthy justification for NIH In 2004, I decided to do a full backup, by burning a copy of all my files onto CD-R disks. It took me most of the day. Afterwards, I sat admiring the large stack of disks, and realized that I would not ever do that again. I'm too lazy for that. That I had done it once was an aberration in the space-time continuum. Switching to DVD-Rs instead CD-Rs would reduce to the number of disks to burn, but not enough: it would still take a stack of them. I needed something much better. I had a little experience with tape drives, and that was enough to convince me that I didn't want them. Tape drives are expensive hardware, and the tapes also cost money. If the drive goes bad, you have to get a compatible one, or all your backups are toast. The price per gigabyte was coming down fast for hard drives, and it was clear that they were about to be very competitive with tapes for price. I looked for backup programs that I could use for disk based backups. rsync, of course, was the obvious choice, but there were others. I ended up doing what many geeks do: I wrote my own wrapper around rsync. There's hundred, possibly thousands, of such wrappers around the Internet. I also got the idea that doing a startup to provide online backup space would be a really cool thing. However, I didn't really do anything about that until 2007. More on that later. The rsync wrapper script I wrote used hardlinked directory trees to provide a backup history, though not in the smart way that backuppc does it. The hardlinks were wonderful, because they were cheap, and provided de-duplication. They were also quite cumbersome, when I needed to move my backups to a new disk the first time. It turned out that a lot of tools deal very badly with directory trees with large numbers of hardlinks. I also decided I wanted encrypted backups. This led me to find duplicity, which is a nice program that does encrypted backups, but I had issues with some of its limitations. To fix those limitations, I would have had to re-design and possibly re-implement the entire program. The biggest limitation was that it treated backups as full backup, plus a sequence of incremental backups, which were deltas against the previous backup. Delta based incrementals make sense for tape drives. You run a full backup once, then incremental deltas for every day. When enough time has passed since the full backup, you do a new full backup, and then future incrementals are based on that. Repeat forever. I decided that this makes no sense for disk based backups. If I already have backed up a file, there's no point in making me backup it again, since it's already there on the same hard disk. It makes even less sense for online backups, since doing a new full backup would require me to transmit all the data all over again, even though it's already on the server. The first battle I could not find a program that did what I wanted to do, and like every good NIHolic, I started writing my own. After various aborted attempts, I started for real in 2006. Here is the first commit message:
revno: 1
committer: Lars Wirzenius <liw@iki.fi>
branch nick: wibbr
timestamp: Wed 2006-09-06 18:35:52 +0300
message:
  Initial commit.
wibbr was the placeholder name for Obnam until we came up with something better. We was myself and Richard Braakman, who was going to be doing the backup startup with me. We eventually founded the company near the end of 2006, and started doing business in 2007. However, we did not do very much business, and ran out of money in September 2007. We ended the backup startup experiment. That's when I took a job with Canonical, and Obnam became a hobby project of mine: I still wanted a good backup tool. In September 2007, Obnam was working, but it was not very good. For example, it was quite slow and wasteful of backup space. That version of Obnam used deltas, based on the rsync algorithm, to backup only changes. It did not require the user to do full and incremental backups manually, but essentially created an endless sequence of incrementals. It was possible to remove any generation, and Obnam would manage the deltas as necessary, keeping the ones needed for the remaining generations, and removing the rest. Obnam made it look as if each generation was independent of each other. The wasteful part was the way in which metadata about files was stored: each generation stored the full list of filenames and their permissions and other inode fields. This turned out to be bigger than my daily delta. The lost years; getting lost in the forest For the next two years, I did a little work on Obnam, but I did not make progress very fast. I changed the way metadata was stored, for example, but I picked another bad way of doing it: the new way was essentially building a tree of directory and file nodes, and any unchanged subtrees were shared between generations. This reduced the space overhead per generation, but made it quite slow to look up the metadata for any one file. The final battle; finding cows in the forest In 2009 I decided to leave Canonical and after that, my Obnam hobby picked up in speed again. Below is a table of the number of commits per year, from the very first commit (bzr log -n0 awk '/timestamp:/ print $3 ' sed 's/-.*//' uniq -c awk ' print $2, $1 ' tac):
2006 466
2007 353
2008 402
2009 467
2010 616
2011 790
2012 282
During most of 2010 and 2011 I was unemployed, and happily hacking Obnam, while moving to another country twice. I don't recommend that as a way to hack on hobby projects, but it worked for me. After Canonical, I decided to tackle the way Obnam stores data from a new angle. Richard told me about the copy-on-write (or COW) B-trees that btrfs uses, originally designed by Ohad Rodeh (see his paper for details), and I started reading about that. It turned out that they're pretty ideal for backups: each B-tree stores data about one generation. To start a new generation, you clone the previous generation's B-tree, and make any modifications you need. I implemented the B-tree library myself, in Python. I wanted something that was flexible about how and where I stored data, which the btrfs implementation did not seem to give me. (Also, I worship at the altar of NIH.) With the B-trees, doing file deltas from the previous generation no longer made any sense. I realized that it was, in any case, a better idea to store file data in chunks, and re-use chunks in different generations as needed. This makes it much easier to manage changes to files: with deltas, you need to keep a long chain of deltas and apply many deltas to reconstruct a particular version. With lists of chunks, you just get the chunks you need. The spin-off franchise; lost in a maze of dependencies, all alike In the process of developing Obnam, I have split off a number of helper programs and libraries: I have found it convenient to keep these split off, since I've been able to use them in other projects as well. However, it turns out that those installing Obnam don't like this: it would probably make sense to have a fat release with Obnam and all dependencies, but I haven't bothered to do that yet. The blurb; readers advised about blatant marketing The strong points of Obnam are, I think: Backups may be stored on local hard disks (e.g., USB drives), any locally mounted network file shares (NFS, SMB, almost anything with remotely Posix-like semantics), or on any SFTP server you have access to. What's not so strong is backing up online over SFTP, particularly with long round trip times to the server, or many small files to back up. That performance is Obnam's weakest part. I hope to fix that in the future, but I don't want to delay 1.0 for it. The big news; readers sighing in relief I am now ready to release version 1.0 of Obnam. Finally. It's been a long project, much longer than I expected, and much longer than was really sensible. However, it's ready now. It's not bug free, and it's not as fast as I would like, but it's time to declare it ready for general use. If nothing else, this will get more people to use it, and they'll find the remaining problems faster than I can do on my own. I have packaged Obnam for Debian, and it is in unstable, and will hopefully get into wheezy before the Debian freeze. I provide packages built for squeeze on my own repository, see the download page. The changes in the 1.0 release compared to the previous one: The future; not including winning lottery numbers I expect to get a flurry of bug reports in the near future as new people try Obnam. It will take a bit of effort dealing with that. Help is, of course, welcome! After that, I expect to be mainly working on Obnam performance for the foreseeable future. There may also be a FUSE filesystem interface for restoring from backups, and a continous backup version of Obnam. Plus other features, too. I make no promises about how fast new features and optimizations will happen: Obnam is a hobby project for me, and I work on it only in my free time. Also, I have a bunch of things that are on hold until I get Obnam into shape, and I may decide to do one of those things before the next big Obnam push. Where; the trail of an errant hacker I've developed Obnam in a number of physical locations, and I thought it might be interesting to list them: Espoo, Helsinki, Vantaa, Kotka, Raahe, Oulu, Tampere, Cambridge, Boston, Plymouth, London, Los Angeles, Auckland, Wellington, Christchurch, Portland, New York, Edinburgh, Manchester, San Giorgio di Piano. I've also hacked on Obnam in trains, on planes, and once on a ship, but only for a few minutes on the ship before I got seasick. Thank you; sincerely SEE ALSO

5 June 2012

Anand Kumria: Internet-o! Or why the Internode Business SLA is not worth a damn.

Last week (28th May), I had five Internet services across two countries. This week, I have seven (7), with two new ones in Australia. It all begin, when Internode decided that in their own best interest to migrate me from my existing DSLAM to one of their own infrastructure. They had sent an email indicating when it was likely to occur. And they were sending invoices to the same address. Naturally, they would send the date of the migration to the same address they had used for the past 9 months to communicate to me with, right? Wrong. Internode still do not understand why they never sent the notification email, as it turns out. Compare the response time, update times, and restore times they specify to what actually occurred.
2012-05-28 12:05 BST
I'm informed of an outage. In the past, the problem has been at my end, so I run through the standard diagnostic procedure. Everything seems to be normal, so I call Internode. Sure enough, our service dropped off the Internet. According to Timothy, that happened at 11:15 AEST because of a migration to their own DSLAM. After some diagnosis from Internode, they realise that whilst the migration has successfully disconnected the service, they have not reconnected anything. There is no sync. Ticket #454448 raised - which is when I'm informed that I'm on the business SLA. I've asked for updated to both an Australian and UK mobile. "Not a problem". Estimated time of resolution: 48 hours. Yes, 48 hours. There goes the first SLA milestone.
2012-05-30 07:28 BST
I ring and speak with Carl. He indicates that as best he knows, the service is to be 7pm. for those keeping score, no updates have occurred during this time. To either number. I query him about the SLA period. He says the response time is 2hrs and restore time is 10hrs. He also indicates that this can all be checked online and that we can apply for a refund.
2012-05-30 10:27 BST
I ring, again, and this time speak with Justin. I ask why I've not have an updated, since 7pm AEST has well and truly gone. He authenticates me and places me on hold to investigate. Advises that the issue is fixed, says he sees sync on the line. I indicate that I do not. He asks me to turn off the ADSL modem, we do, and he still sees sync. on the line. Believes there is another problem at the exchange, another issue raised with wholesaler. No ticket number issues to me. ETA to fix 7pm 2nd June. Note:This was a 1 hour International call
2012-06-01 04:00 BST
I happened to check, and notice I have connectivity to the external interfaces (and thus, obviously, line sync.) again. No notification though.
2012-06-01 14:31 BST
Amidst all this, I also have to to source two external connections - Telstra & Optus, get them setup, reconfigure routing, email delivery and other network services so that the businesses which are relying on the Internet, still work. Not fun. Especially when I have no access to the routers. I had to get multiple people on site.
2012-06-04 11:XX CEST
I'm told that the second site has gone done. Inexplicably. After some round-trip and diagnosis, we determine that the routing change has occurred. However it has been done incorrectly. And, of course, no notice / or update occurred either. Multiple tickets are raised by multiple people, amongst them: #4562559 from my mobile phone whilst I am in Zurich.
2012-06-04 16:56 CEST
I am informed, and it is confirmed, that the attempted routing change has been reverted and we are back to how things were on 2012-06-01.
2012-06-05 05:44 CEST
I wake up, and find out that of at least three hours ago, they appear to have called (finally!) and actually fixed the routing to both sites. That is a week of down time, multiple people (4 people) around in various countries around the World and hundreds of dollars in calls between us all to get things working. Now, to look into compensation.
2012-06-05 09:43 CEST
I receive a missed call, which I later learn is Internode actually calling me (for once!). At that moment, I'm actually giving a lightening talk on Django-PaaS
And that, dear reader, is why Internode Business SLA is a waste of money. The services were broken by a change of no net benefit to me, was over a week ago. Also, during this process. My UK home Internet went down. My UK Three post-paid service "ran out of money" and Vodafone has a service outage for half a day. A perfect storm of Internet dis-connectivity. So, if you have been wondering, that is why I've been offline for various parts of the last week.

4 June 2012

Steve McIntyre: Visiting my grandfather in Hong Kong

I never met my father's father, as he died many years before I was born. He was a soldier in the British Army and was killed in an accident in Burma in the 1950s. I'm told that back then the Army did not repatriate casualties as a matter of course like they do today, so none of the family got to see his funeral or even visit the grave. Like many of the military casualties in the Far East, he was buried in the Colonial Cemetery in Hong Kong. A few photographs were sent to my grandmother of the ceremony and the headstone, but that's all we ever saw.

telegramfuneral Fast forward to 2012. I travelled to Hong Kong for a conference (Linaro Connect, more about that later...). I looked up the details of where grandad was laid to rest, and found a major coincidence. He was killed on 27th May 1952, almost exactly 60 years ago! I resolved to go to find him on 27th May 2012 to make the most of this lucky anniversary. Wikipedia told me that in the intervening years the Colonial Cemetery had been renamed to Happy Valley Cemetery, then simply Hong Kong Cemetery, and repurposed from military to civilian use. Jo and I bought some flowers and headed over to Happy Valley on Hong Kong Island on Sunday afternoon. We found a very large cemetery with a helpful map posted to show the different sections, but nothing to tell us where we should be looking. One of the attendants at the office on site looked at the details we had and shrugged to say "sorry, can't help". Ah well, nobody said this was going to be very easy... What we found after a few minutes was that the graves weren't laid out in any obviously logical fashion. In any given small area, you'd find people buried from roughly the same period, but people for any given period could (and would) be scattered across multiple sections at all corners of the site. Great, time for an exhaustive search then. I started combing the site, checking all the markers I could find that looked anything like the tiny grainy black and white photo we had of grandad's headstone.

cemeteryheadstone Almost two hours later, I eventually found him. Two hours of heavy work: the cemetery is built on the side of quite a steep hill, and the prevailing weather was very hot with 100% humidity. But, I forgot all that as we eventually stumbled across the correct grave in (no exaggeration!) the very last part of the last section of the site, 20a.

grave I was relieved at this point: as things had taken so long, I had started to worry that maybe the grave had been moved or the headstone damaged and lost. But no, I found the man who had gone off to war leaving my dad and aunt as small children. We took some photos and took note of where we had found the final resting place of Sergeant William Alexander McIntyre of the Royal Signals, a man I never met in life but clearly a very important member of our family.

1 June 2012

Pietro Abate: apt-get with external solvers : call for testers

Last year we invited David to work with us for a few days to add a generic interface to apt to call external solvers. After a few iterations, this patch finally landed in master and recently (about 3 months ago), in debian unstable.
  [ David Kalnischkies ]
  * [ABI-Break] Implement EDSP in libapt-pkg so that all front-ends which
    use the internal resolver can now be used also with external
    ones as the usage is hidden in between the old API
  * provide two edsp solvers in apt-utils:
    - 'dump' to quickly output a complete scenario and
    - 'apt' to use the internal as an external resolver
Today the new version of apt-cudf was upload in unstable and with it the latest bug fixes that makes it ready for daily use. I've used it quite a lot myself to upgrade my machine and it seems working pretty well so far... The most important difference with the old version is the support for multi-arch enabled machines. This marks an important milestone in our efforts to integrate external solvers, built using different technologies, directly into apt. From a user prospective, this means that (s)he will have the possibility to check if there exists a better (best ?) solution to an installation problem then what proposed by the internal apt solver. Moreover, even if apt-get gives very satisfactory answers, there are occasions where it fails miserably, leaving the user wondering how to unravel the complex web of dependencies to accomplish his task. Available cudf solvers in debian are at the moment : aspcud, mccs and packup. From an architectural point of view this is accomplished by abstracting the installation problem via a simple textual protocol (EDSP) and using an external tool to do the heavy duty translation. Since all solvers now available in debian are not meant to be debian-specific, using them involve a two step translation. The EDSP protocol specification is for the moment "hidden" in the apt documentation. I hope to find a better place for it soon : it would be cool if other package managers as smart or cupt could add an implementation on EDSP in their code so to automatically benefit of this technology. To make it happen, Apt first creates an EDSP file that is then handled to apt-cudf that takes care of the translation to cudf and back into EDSP that is then read back by apt. Apt-cudf is the bridge between edsp and the external solvers and takes care of doing the book keeping and to select the right optimization criteria. Roberto recently wrote a very nice article explaining how to use apt-get with an external solver. In a nutshell, if you want to try this out you just need to install apt-cudf, one external solver like aspcud from the university of Pasdam and then call apt-get using the --solver option (that is not yet documented #67442 ). For example :
apt-get install -s gnome --solver aspcud
This will install gnome while using the a optimization criteria that tries to minimizing the changes on the system. Various other optimization criteria for all apt-get default actions can be specified in the apt-cudf configuration file /etc/apt-cudf.conf I hope the new release of apt-cudf make it into testing before the freeze. Time to test !!!

31 May 2012

Matthew Garrett: Implementing UEFI Secure Boot in Fedora

Edit 16:17EDT 31/5/12: Clarification of who gets the $99
Edit 02:10EDT 01/6/12: Clarification that it's a one-off payment

(Brief disclaimer - while I work for Red Hat, I'm only going to be talking about Fedora here. Anything written below represents only my opinions and my work on Fedora, not Red Hat's opinions or future plans)

Fedora 17 was released this week. It's both useful and free, and serves as a welcome addition to any family gathering. Do give it a go. But it's also noteworthy for another reason - it's the last Fedora release in the pre-UEFI secure boot era. Fedora 18 will be released at around the same time as Windows 8, and as previously discussed all Windows 8 hardware will be shipping with secure boot enabled by default. While Microsoft have modified their original position and all x86 Windows machines will be required to have a firmware option to disable this or to permit users to enrol their own keys, it's not really an option to force all our users to play with hard to find firmware settings before they can run Fedora. We've been working on a plan for dealing with this. It's not ideal, but of all the approaches we've examined we feel that this one offers the best balance between letting users install Fedora while still permitting user freedom.

Getting the machine booted
Most hardware you'll be able to buy towards the end of the year will be Windows 8 certified. That means that it'll be carrying a set of secure boot keys, and if it comes with Windows 8 pre-installed then secure boot will be enabled by default. This set of keys isn't absolutely fixed and will probably vary between manufacturers, but anything with a Windows logo will carry the Microsoft key[1].

We explored the possibility of producing a Fedora key and encouraging hardware vendors to incorporate it, but turned it down for a couple of reasons. First, while we had a surprisingly positive response from the vendors, there was no realistic chance that we could get all of them to carry it. That would mean going back to the bad old days of scouring compatibility lists before buying hardware, and that's fundamentally user-hostile. Secondly, it would put Fedora in a privileged position. As one of the larger distributions, we have more opportunity to talk to hardware manufacturers than most distributions do. Systems with a Fedora key would boot Fedora fine, but would they boot Mandriva? Arch? Mint? Mepis? Adopting a distribution-specific key and encouraging hardware companies to adopt it would have been hostile to other distributions. We want to compete on merit, not because we have better links to OEMs.

An alternative was producing some sort of overall Linux key. It turns out that this is also difficult, since it would mean finding an entity who was willing to take responsibility for managing signing or key distribution. That means having the ability to keep the root key absolutely secure and perform adequate validation of people asking for signing. That's expensive. Like millions of dollars expensive. It would also take a lot of time to set up, and that's not really time we had. And, finally, nobody was jumping at the opportunity to volunteer. So no generic Linux key.

The last option wasn't hugely attractive, but is probably the least worst. Microsoft will be offering signing services through their sysdev portal. It's not entirely free (there's a one-off $99 fee to gain access edit: The $99 goes to Verisign, not Microsoft - further edit: once paid you can sign as many binaries as you want), but it's cheaper than any realistic alternative would have been. It ensures compatibility with as wide a range of hardware as possible and it avoids Fedora having any special privileges over other Linux distributions. If there are better options then we haven't found them. So, in all probability, this is the approach we'll take. Our first stage bootloader will be signed with a Microsoft key.

Bootloaders
We've decided to take a multi-layer approach to our signing for a fairly simple reason. Signing through the Microsoft signing service is a manual process, and that's a pain. We don't want to have bootloader updates delayed because someone needs to find a copy of Internet Explorer and a smartcard and build packages by hand. Instead we're writing a very simple bootloader[2]. This will do nothing other than load a real bootloader (grub 2), validate that it's signed with a Fedora signing key and then execute it. Using the Fedora signing key there means that we can build grub updates in our existing build infrastructure and sign them ourselves. The first stage bootloader should change very rarely, and we don't envisage updating it more than once per release cycle. It shouldn't be much of a burden on release management.

What about grub? We've already switched Fedora 18 over to using grub 2 by default on EFI systems, but it still needs some work before it's ready for secure boot. The first thing is that we'll be disabling the module loading. Right now you can load arbitrary code into grub 2 at runtime, and that defeats the point of secure boot. So that'll be disabled. Next we'll be adding support for verifying that the kernel it's about to boot is signed with a trusted key. And finally we'll be sanitising the kernel command line to avoid certain bits of functionality that would permit an attacker to cause even a signed kernel to launch arbitrary code. These restrictions will all vanish if secure boot is disabled.

Kernel
Secure boot is built on the idea that all code that can touch the hardware directly is trusted, and any untrusted code must go through the trusted code. This can be circumvented if users can execute arbitrary code in the kernel. So, we'll be moving to requiring signed kernel modules and locking down certain aspects of kernel functionality. The most obvious example is that it won't be possible to access PCI regions directly from userspace, which means all graphics cards will need kernel drivers. Userspace modesetting will be a thing of the past. Again, disabling secure boot will disable these restrictions.

Signed modules are obviously troubling from a user perspective. We'll be signing all the drivers that we ship, but what about out of tree drivers? We don't have a good answer for that yet. As before, we don't want any kind of solution that works for us but doesn't work for other distributions. Fedora-only or Ubuntu-only drivers are the last thing anyone wants, and this really needs to be handled in a cross-distribution way.

Wait signed what
Secure boot is designed to protect against malware code running before the operating system. This isn't a hypothetical threat. Pre-boot malware exists in the wild, and some of it is nastier than you expect. So obviously bootloaders need to be signed, since otherwise you'd just replace the signed bootloader with an unsigned one that installed malware and booted your OS.

But what about the kernel? The kernel is just code. If I take a signed Linux bootloader and then use it to boot something that looks like an unsigned Linux kernel, I've instead potentially just booted a piece of malware. And if that malware can attack Windows then the signed Linux bootloader is no longer just a signed Linux bootloader, it's a signed Windows malware launcher and that's the kind of thing that results in that bootloader being added to the list of blacklisted binaries and suddenly your signed Linux bootloader isn't even a signed Linux bootloader. So kernels need to be signed.

And modules? Again, modules are just code. It's a little trickier, but if your signed kernel loads an unsigned module then that unsigned module can set up a fake UEFI environment and chain into a compromised OS bootloader. Now the attacker just has to include a signed kernel and a minimal initramfs that loads their malware module. It'd slow down boot by a couple of seconds, but other than that it'd be undetectable. X? If you can access the registers on a GPU then you can get the GPU to DMA over the kernel and execute arbitrary code. Trickier again, but still achievable - and if you've locked down every other avenue of attack, it's even attractive.

If we produce signed code that can be used to attack other operating systems then those other operating systems are justified in blacklisting us. That doesn't seem like a good outcome.

Customisation
A lot of our users want to build their own kernels. Some even want to build their own distributions. Signing our bootloader and kernel is an impediment to that. We'll be providing all the tools we use for signing our binaries, but for obvious reasons we can't hand out our keys. There's three approaches here. The first is for a user to generate their own key and enrol it in their system firmware. We'll trust anything that's signed with a key that's present in the firmware. The second is to rebuild the shim loader with their own key installed and then pay $99 and sign that with Microsoft. That means that they'll be able to give copies to anyone else and let them install it without any fiddling. The third is to just disable secure boot entirely, at which point the machine should return to granting the same set of freedoms as it currently does.

But I don't trust Microsoft
A system in custom mode should allow you to delete all existing keys and replace them with your own. After that it's just a matter of re-signing the Fedora bootloader (like I said, we'll be providing tools and documentation for that) and you'll have a computer that will boot Fedora but which will refuse to boot any Microsoft code. It may be a little more awkward for desktops because you may have to handle the Microsoft-signed UEFI drivers on your graphics and network cards, but this is also solvable. I'm looking at ways to implement a tool to allow you to automatically whitelist the installed drivers. Barring firmware backdoors, it's possible to configure secure boot such that your computer will only run software you trust. Freedom means being allowed to run the software you want to run, but it also means being able to choose the software you don't want to run.

You've sold out
We've been working on this for months. This isn't an attractive solution, but it is a workable one. We came to the conclusion that every other approach was unworkable. The cause of free software isn't furthered by making it difficult or impossible for unskilled users to run Linux, and while this approach does have its downsides it does also avoid us ending up where we were in the 90s. Users will retain the freedom to run modified software and we wouldn't have accepted any solution that made that impossible.

But is this a compromise? Of course. There's already inequalities between Fedora and users - trademarks prevent the distribution of the Fedora artwork with modified distributions, and much of the Fedora infrastructure is licensed such that some people have more power than others. This adds to that inequality. It's not the ideal outcome for anyone, and I'm genuinely sorry that we weren't able to come up with a solution that was better. This isn't as bad as I feared it would be, but nor is it as good as I hoped it would be.

What about ARM
Microsoft's certification requirements for ARM machines forbid vendors from offering the ability to disable secure boot or enrol user keys. While we could support secure boot in the same way as we plan to on x86, it would prevent users from running modified software unless they paid money for a signing key. We don't find that acceptable and so have no plans to support it.

Thankfully this shouldn't be anywhere near as much of a problem as it would be in the x86 world. Microsoft have far less influence over the ARM market, and the only machines affected by this will be the ones explicitly designed to support Windows. If you want to run Linux on ARM then there'll be no shortage of hardware available to you.

Is this all set in stone?
No. We've spent some time thinking about all of this and are happy that we can implement it in the Fedora 18 timescale, but there's always the possibility that we've missed something or that a new idea will come up. If we can increase user freedom without making awful compromises somewhere else then we'll do it.

[1] In fact, chances are that everything will carry the Microsoft key. Secure boot requires that UEFI drivers also be signed. The signing format only permits a single signature per binary. For compatibility, approximately all add-on hardware shipped will be signed with Microsoft's key, and that means that all system vendors have to recognise Microsoft's key in order to permit that hardware to run on their systems.
[2] Current source is here. It relies on a port of the UEFI crypto library and OpenSSL that I have building with some handholding, and which I'll upload as soon as possible.

comment count unavailable comments

19 May 2012

Richard Hartmann: Mongolia

I will start linking to places we stayed at etc, from now on. On the one hand, we already left those places so my paranoid self can rest assured that no one will come hunt us down, on the other hand, I decided to only to name and link to those places which really deserve a mention. If they are linked here, I can whole-heartedly recommend them. Mongolia After leaving through the Russian border fortifications, Mongolia was an instant and welcome change. Trees growing right next to the tracks, branches forming a bit of a natural tunnel; the trains passing by keeping branches at bay, but the trees free to grow wherever else they pleased. A few hundred meters later below a rocky ledge, a cow had apparently fallen down and died. Partially decomposed flesh still clinging halfway to its rib-cage, it proved to be a sign of the (mostly) more laid-back attitude Mongolians tend to take. After finally getting our passports back and being allowed to leave the train, we first headed to the station to get some money. At ~1800:1, the exchange rate for Tugruk against Euro speaks volumes about inflation; imagine my surprise that the MNT 20,000 note is the largest one. It's also the one and only amount any and all ATMs will default to. We were quite surprised by how cheap everything was, even in the one single store within the station directly behind the border. In Russia, travellers expect to pay hefty markups when shopkeepers know they can charge them, not so in Mongolia. The woman in the trash Upon returning from the station, our waggon was just merrily being driving away on its own by a lone engine, something we had not anticipated or appreciated a whole lot. A woman (we hadn't noticed her before) who was busy scavenging a trash container for food for herself and her scrawny-looking son happily stopped what she was doing and, with a big smile, moved her hands around and smacked them back together, signalling us that our waggon would be attached to a different train for the subsequent journey. To put it mildly, I was stunned; we had met people eating from the trash in Russia as well (yes, I always make a point of giving them enough for a few decent meals; anyone eating out of the trash actually needs and definitely deserves something good happening to them), but they were glum and disheartened. Here, there was someone who not only had to look out for herself, but for a three or four year old boy as well, and still was just so... positive... I don't know if I would have it in me to act the same way... As an aside, even though we were just a few kilometers across the border from Russia, she did not actually take the money from me, she cupped her hands to receive it by having me place it into her hands; this is a very Asian thing in my experience and something we would see both in Mongolia and China consistently. Later, when we were back in our waggon, she passed by and happened to see the Spot Messgenger 2 dangling in front of our window, its lights blinking every five seconds. For a solid twenty minutes, until the train started moving again, she squatted down with her son, oggling the Spot. I have no idea what she was thinking it was and I had no chance to explain it to her, but she was really fascinated and just kept staring and staring. When we finally left the station, we waved to and smiled at each other, she ran after us, and then she was gone. All in all, this was one the more memorable things which happened to us. Mongolian Infrastructure When I say that Mongolians as a whole tend to be a lot more laid back than Russians, this extends to infrastructure as well, but not in the good way. Ulan Bator Little Dhingis Khan We arrived in Ulan Bator at six in the morning and started haggling with taxi drivers. Our hostel had (stale, it turned out) information about acceptable fare from station to their place on their website, 5,000 MNT was supposedly OK. Our driver tried to get 20,000, then 15,000, then 12,000, then 10,000, went down to 7,000 and finally settled for 5,000, all this interspersed with frequent "no" by us and walking away. Once on the road, he wanted to convince me that we had agreed upon 5,000 per person, something that did not quite work out for him. When we arrived, he started to tell me that he was good friends with the hostel manager and that said manager would surely want us to pay more; again, that did not work too well. He made the mistake of getting our luggage out of his trunk immediately (we always kept all our stuff in the passenger area afterwards...) before I paid and even though I only had a 10,000 or 20,000 note, I insisted on correct change. The same old dance began anew, with him edging closer to the correct change in steps of 1,000 MNT. He tried to get away several times, but I stood in his door and held it open; if he had just driven off, I couldn't have stopped him, but that thankfully didn't occur to him. After he shoved all small change (MNT is bill only, no coins) he had with him at me and wanted to make off yet again, I was close to throwing all the small crap at him, but after he, a man of maybe 1.65 meter and sitting down, tried to signal his willingness for a fist fight and me, a man of 1.94 meter and standing started laughing, he gave me 2,000 more and drove off cursing. In case you forgot, at that exchange rate, we argued about two to three Euro, but as he tried to cheat, it became a matter of principle. The Hostel, part one All parking lots and other property in Ulan Bator have a small watchtower with private 24/7 guards; said guard ambled down, let us in and woke the poor woman who was forced to let us check in. As she was Mongolian as well, we were a bit surprised when she switched from broken English to perfect German, but the owners of the OASIS are a German-Austrian couple so I guess that makes sense. Fighting through the war Traffic in Ulan Bator is war. Lonely Planet talks about the city being too newly motorized and that it did not have to develop a culture of driving, yet. This is a euphemism for "no one has any qualms maiming or killing you". Everyone is driving like mad, nudging and racing their way in front of each other. If a driver has an oppurtunity to get ahead by a few centimeters with his small car, thereby blocking the way for several buses, making a whole parking lot grind to a halt and thereby deadlocking themselves, they will take said opportunity, and gladly. Red lights are gentle suggestions, there to be mainly ignored; police will not drive over red lights, but they will not stop anybody else from doing so, either. A hearse will have a dozen or more cars following it, all driving in a tight pack, aggressively attacking anyone who dares to wedge in between them and expecting all other traffic to make way even if they are driving over a red light. Crossing a main street in Ulan Bator as a pedestrian is hell. There are a few traffic lights and they help to some extent, but you still need to be extremely careful when crossing a street. Thailand, India, Russia, China, no matter where it's supposedly hard to cross a street by foot, I never had any issues weaseling through. In UB, it takes planning, determination, and a lot of attention, especially as there are stretches where there's not a traffic light in sight. While maintaining eye contact with a driver usually ensures that they will try not to hit you, this does not work in the least in UB. In the evening, I took to shining a high-powered flashlight at the ground to the oncoming traffic's side to mark ourselves and decrease the likelihood of being hit. This worked well in combination with sprinting through gaps in the traffic, except for one guy who actively aimed for us and did not slow down. He even changed lanes, just to keep us in front of his car... Shining the flashlight directly at him in highest mode made him break quite violently though; a good thing, as he may have hit us had he not slowed down. UB itself Ulan Bator is weird. It has clear signs of westernization, but it's still very much an old city. There is one large store which would fit into any random shopping center in Germany (which are tiny when compared to most other countries) and which carries most goods, if with a limited selection. Its supermarket is extremely well stocked with food and drink from all other the world and laughably cheap (for us) prices. While its infrastructure is definitely crumbling, the city is clean, especially when compared to Russia. Two girls from Stuttgart who we met during our Trans-Siberian travels commented on how clean Russian cities were when compared to home, but that may be more of a statement about Stuttgart than about Russia... Anyway, in Mongolia in general and in UB in particular, there's a concise effort to make what they have look nice and clean. There is no trash in the streets, loose gravel and earth is removed from the curb by dedicated workers, all areas of packed earth are sieved and all large stones removed. All in all, it's a lot cleaner (if more dusty and sandy) than Russian cities if somewhat older and more shabby-looking. That being said, Mongolia's countryside is littered There were several street stalls consisting of nothing more than a cardboard box on a stool selling single chewing gums and cigarettes from the original packaging; it's normal for people to buy one cigarette or one piece of chewing gum and walk on. The sights of UB were nice, but nothing too special. Outlook In the next part, I'll cover "The Hostel, part disaster" and generally talk more about excrement than I thought one could write before moving on to China (were I am located at the time of this writing).

Next.

Previous.