Notice: There were several requests for me to more elaborate on my path to Debian and impact on life so here it is. It's going to be a bit long so anyone who isn't interested in my personal Debian journey should skip it. :) In 2007. I enrolled into Faculty of Mechanical Engineering (at first at Department of Industrial Management and later transfered to Department of Mechatronics - this was possible because first 3 semesters are same for both departments). By the end of same year I was finishing my tasks (consisting primarily of calculations, some small graphical designs and write-ups) when famous virus, called by users "RECYCLER", sent my Windows XP machine into oblivion. Not only it took control over machine and just spawned so many processes that system would crash itself, it actually deleted all from hard-disk before it killed the system entirely. I raged - my month old work, full of precise calculations and a lot of design details, was just gone. I started cursing which was always continued with weeping: "Why isn't there an OS that can whithstand all of viruses, even if it looks like old DOS!". At that time, my roommate was my cousin who had used Kubuntu in past and currently was having SUSE dual-booted on his laptop. He called me over, started talking about this thing called Linux and how it's different but de facto has no viruses. Well, show me this Linux and my thought was, it's probably so ancient and not used that it probably looks like from pre Windows 3.1 era, but when SUSE booted up it had so much more beautiful UI look (it was KDE, and compared to XP it looked like the most professional OS ever). So I was thrilled, installed openSUSE, found some rough edges (I knew immediately that my work with professional CAD systems will not be possible on Linux machines) but overall I was bought. After that he even talked to me about distros. Wait, WTF distros?! So, he showed me distrowatch.com. I was amazed. There is not only a better OS then Windows - there where dozens, hundreds of them. After some poking around I installed Debian KDE - and it felt great, working better then openSUSE but now I was as most newbies, on fire to try more distros. So I was going around with Fedora, Mandriva, CentOS, Ubuntu, Mint, PCLinuxOS and in beginning of 2008 I stumbled upon Debian docs which where talking about GNU and GNU Manifesto. To be clear, I was always as a high-school kid very much attached to idea of freedom but started loosing faith by faculty time (Internet was still not taking too much of time here, youth still spent most of the day outside). So the GNU Manifesto was really a big thing for me and Debian is a social bastion of freedom. Debian (now with GNOME2) was being installed on my machine. As all that hackerdom in Debian was around I started trying to dig up some code. I never ever read a book on coding (until this day I still didn't start and finish one) so after a few days I decided to code tetris in C++ with thought that I will finish it in two days at most (the feeling that you are powerful and very bright person) - I ended it after one month in much pain. So instead I learned about keeping Debian system going on, and exploring some new packages. I got thrilled over radiotray, slimvolley (even held a tournament in my dorm room), started helping on #debian, was very active in conversation with others about Debian and even installed it on few laptops (I became de facto technical support for users of those laptops :D ). Then came 2010 which with negative flow that came in second half of 2009, started to crush me badly. I was promised to go to Norway, getting my studies on robotics and professor lied (that same professor is still on faculty even after he was caught in big corruption scandal over buying robots - he bought 15 years old robots from UK, although he got money from Norway to buy new ones). My relationship came to hard end and had big emotional impact on me. I fell a year on faculty. My father stopped financing me and stopped talking to me. My depression came back. Alcohol took over me. I was drunk every day just not to feel anything. Then came the end of 2010, I somehow got to the information that DebConf will be in Banja Luka. WHAT?! DebConf in city where I live. I got into #debconf and in December 2010/January 2011 I became part of the famous "local local organizers". I was still getting hammered by alcohol but at least I was getting out of depression. IIRC I met Holger and Moray in May, had a great day (a drop of rakia that was too much for all of us) and by their way of behaving there was something strange. Beatiful but strange. Both were sending unique energy of liberty although I am not sure they were aware of it. Later, during DebConf I felt that energy from almost all Debian people, which I can't explain. I don't feel it today - not because it's not there, it's because I think I integrated so much into Debian community that it's now a natural feeling which people here, that are close to me are saying that they feel it when I talk about Debian. DebConf time in Banja Luka was awesome - firstly I met Phil Hands and Andrew McMillan which were a crazy team, local local team was working hard (I even threw up during the work in Banski Dvor because of all heat and probably not much of sleep due to excitement), met also crazy Mexican Gunnar (aren't all Mexicans crazy?), played Mao (never again, thank you), was hanging around smart but crazy people (love all) from which I must notice Nattie (a bastion of positive energy), Christian Perrier (which had coordinated our Serbian translation effort), Steve Langasek (which asked me to find physiotherapist for his co-worker Mathias Klose, IIRC), Zach (not at all important guy at that time), Luca Capello (who gifted me a swirl on my birthday) and so many others that this would be a post for itself just naming them. During DebConf it was also a bit of hard time - my grandfather died on 6th July and I couldn't attend the funeral so I was still having that sadness in my heart, and Darjan Prtic, a local team member that came from Vienna, committed suicide on my birthday (23 July). But DebConf as conference was great, but more importantly the Debian community felt like a family and Meike Reichle told me that it was. The night it finished, me and Vedran Novakovic cried. A lot. Even days after, I was getting up in the morning having the feeling I need something to do for DebConf. After a long time I felt alive. By the end of year, I adopted package from Clint Adams and Moray became my sponsor. In last quarter of 2011 and beginning of 2012, I (as part of LUG) held talks about Linux, had Linux installation in Computer Center for the first time ever, and installed Debian on more machines. Now fast forwarding with some details - I was also on DebConf13 in Switzerland, met some great new friends such as Tincho and Santiago (and many many more), Santiago was also my roommate in Portland on the previous DebConf. In Switzerland I had really great and awesome time. Year 2014 - I was also at DebConf14, maintain a bit more packages and have applied for DD, met some new friends among which I must put out Apollon Oikonomopoulos and Costas Drogos which friendship is already deep for such a short time and I already know that they are life-long friends. Also thanks to Steve Langasek, because without his help I wouldn't be in Portland with my family and he also gave me Arduino. :) 2015. - I am currently at my village residence, have a 5 years of working experince as developer due to Debian and still a lot to go, learn and do but my love towards Debian community is by magnitude bigger then when I thought I love it at most. I am also going through my personal evolution and people from Debian showed me to fight for what you care, so I plan to do so. I can't write all and name all the people that I met, and believe me when I say that I remember most and all of you impacted my life for which I am eternally grateful. Debian, and it's community effect literally saved my life, spring new energy into me and changed me for better. Debian social impact is far bigger then technical, and when you know that Debian is a bastion of technical excellence - you can maybe picture the greatness of Debian. Some of greatest minds are in Debian but most important isn't the sheer amount of knowledge but the enormous empathy. I just hope I can in future show to more people what Debian is and to find all lost souls as me to give them the hope, to show them that we can make world a better place and that everyone is capable to live and do what they love. P.S. I am still hoping and waiting to see Bdale writing a book about Debian's history to this day - in which I think many of us would admire the work done by project members, laugh about many situations and have fun reading a book about project that was having nothing to do but fail and yet it stands stronger then ever with roots deep into our minds.

Instances of the for those who care about X snowclone on Debian mailing lists:

• their packages in Ubuntu (the original!)
• lesbians
• Andrew Suffield
• debian-devel-announce
• their packages in klik
• the [GFDL] GR
• stable updates
• bits from [press and events] teams
• glib applications
• experimental
• Debconf
• Policy 7.6
• Switzerland/Liechtenstein
• X
• firmware
• bts-link
• lesbians (reloaded)
• pam-ssh
• Mercurial
• manpages
• their packages in Debian
• unbound
• irker
• [team metrics] statistics

For my GSoC project this year I need to be able to enumerate all elementary circuits of a directed graph. My code is written in Ocaml but neither the ocamlgraph library nor graph libraries for other languages seem to implement a well tested algorithm for this task. In lack of such a well tested solution to the problem, I decided to implement a couple of different algorithms. Since it is unlikely that different algorithms yield the same wrong result, I can be certain enough that each individual algorithm is working correctly in case they all agree on a single solution. As a result I wrote a testsuite, containing an unholy mixture of Python, Ocaml, D and Java code which implements algorithms by D. B. Johnson, R. Tarjan, K. A. Hawick and H. A. James.

Algorithm by R. Tarjan The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

I implemented the pseudocode given in the paper using Python. The git repository can be found here: https://github.com/josch/cycles_tarjan

Algorithm by D. B. Johnson The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

In the worst case, Tarjan's algorithm has a time complexity of O(n e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph. I found two implementations of Johnson's algorithm. One was done by Frank Meyer and can be downloaded as a zip archive. The other was done by Pietro Abate and the code can be found in a blog entry which also points to a git repository. The implementation by Frank Meyer seemed to work flawlessly. I only had to add code so that a graph could be given via commandline. The git repository of my additions can be found here: https://github.com/josch/cycles_johnson_meyer Pietro Abate implemented an iterative and a functional version of Johnson's algorithm. It turned out that both yielded incorrect results as some cycles were missing from the output. A fixed version can be found in this git repository: https://github.com/josch/cycles_johnson_abate

Algorithm by K. A. Hawick and H. A. James The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf

In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices. I do not need this functionality but add the code as additional verification. The paper posts extensive code snippets written in the D programming language. A full, working version with all pieces connected together can be found here: https://github.com/josch/cycles_hawick_james The algorithm was verified using example output given in the paper. The project README states how to reproduce it.

Input format All four codebases have been modified to produce executables that take the same commandline arguments which describes the graphs to investigate. The first argument is the number of vertices of the graph. Subsequent arguments are ordered pairs of comma separated vertices that make up the directed edges of the graph. Lets look at the following graph as an example: The DOT source for this graph is:

digraph G  
  0;
  1;
  2;
  0 -> 1;
  0 -> 2;
  1 -> 0;
  2 -> 0;
  2 -> 1;
   

To generate the list of elementary circuits using Tarjan's algorithm for the graph above, use:

$ python cycles.py 3 0,1 0,2 1,0 2,0 2,1
0 1
0 2
0 2 1

The commandline arguments are the exact same for the other three methods and yield the same result in the same order. If the DOT graph is in a format as simple as above, the following sed construct can be used to generate the commandline argument that represents the graph:

$ echo  sed -n -e '/^\s*[0-9]\+;$/p' graph.dot   wc -l   sed -n -e 's/^\s*\([0-9]\) -> \([0-9]\);$/\1,\2/p' graph.dot 

Testsuite As all four codebases take the same input format and have the same output format, it is now trivial to write a testsuite that compares the individual output of each algorithm for the same input and checks for differences. The code of the testsuite is available via this git repository: https://github.com/josch/cycle_test The other four repositories exist as submodules of the testsuite repository.

$ git clone git://github.com/josch/cycle_test.git
$ cd cycle_test
$ git submodule update --init

A testrun is done via calling:

$ ./test.sh 11

The argument to the shell script is an integer denoting the maximum number N of vertices for which graphs will be generated. The script will compile the Ocaml, Java and D sourcecode of the submodules as well as an ocaml script called rand_graph.ml which generates random graphs from v = 1..N vertices where N is given as a commandline argument. For each number of vertices n, e = 1..M number of edges are chosen where M is maximum number of edges given the number of vertices. For every combination of number of vertices v and number of edges e, a graph is randomly generated using Pack.Digraph.Rand.graph from the ocamlgraph library. Each of those generated graphs is checked for cycles and written to a file graph-v-e.dot if the graph contains a cycle. test.sh then loops over all generated dot files. It uses the above sed expression to convert each dot file to a commandline argument for each of the algorithms. The outputs of each algorithm are then compared with each other and only if they do not differ, does the loop continue. Otherwise the script returns with an exit code. The tested algorithms are the Python implementation of Tarjan's algorithm, the iterative and functional Ocaml implementation as well as the Java implementation of Johnson's algorithm and the D implementation of the algorithm by Hawick and James.

Future developments Running the testsuite with a maximum of 12 vertices takes about 33 minutes on a 2.53GHz Core2Duo and produces graphs with as much as 1.1 million cycles. It seems that all five implementations agree on the output for all 504 generated graphs that were used as input. If there should be another implementation of an algorithm that enumerates all elementary circuits of a directed graph, I would like to add it. There are some more papers that I would like to read but I lack access to epubs.siam.org and ieeexplore.ieee.org and would have to buy them. Benchmarks seem a bit pointless as not only the algorithms are very different from each other (and there are many ways to tweak each of them) but also the programming languages differ. Though for the curious kind, it follows the time each algorithm takes to enumerate all cycles for all generated graphs up to 11 vertices.

algorithm	time (s)
Johnson, Abate, Ocaml, iterative	137
Johnson, Abate, Ocaml, functional	139
Tarjan, Python	153
Hawick, D	175
Johnson, Meyer, Java	357

The iterative Ocaml code performs as well as the functional one. In practice, the iterative code should probably be preferred as the functional code is not tail recursive. On the other hand it is also unlikely that cycles ever grow big enough to make a difference in the used stack space. The Python implementation executes surprisingly fast, given that Tarjan's algorithm is supposedly inferior to Johnson's and given that Python is interpreted but the Python implementation is also the most simple one with the least amount of required datastructures. The D code potentially suffers from the bigger datastructures and other bookkeeping that is required to support multi and self arcs. The java code implements a whole graph library which might explain some of its slowness.

The Linux kernel attempts to protect portions of its memory from unexpected modification (through potential future exploits) by setting areas read-only where the compiler has allowed it (CONFIG_DEBUG_RODATA). This, combined with marking function pointer tables const , reduces the number of easily writable kernel memory targets for attackers. However, modules (which are almost the bulk of kernel code) were not handled, and remained read-write, regardless of compiler markings. In 2.6.38, thanks to the efforts of many people (especially Siarhei Liakh and Matthieu Castet), CONFIG_DEBUG_SET_MODULE_RONX was created (and CONFIG_DEBUG_RODATA expanded). To visualize the effects, I patched Arjan van de Ven s arch/x86/mm/dump_pagetables.c to be a loadable module so I could look at /sys/kernel/debug/kernel_page_tables without needing to rebuild my kernel with CONFIG_X86_PTDUMP. Comparing Lucid (2.6.32), Maverick (2.6.35), and Natty (2.6.38), it s clear to see the effects of the RO/NX improvements, especially in the Modules section which has no NX markings at all before 2.6.38:

lucid-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   grep NX   wc -l
0
maverick-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   grep NX   wc -l
0
natty-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   grep NX   wc -l
76

2.6.38 s memory region is much more granular, since each module has been chopped up for the various segment permissions:

lucid-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   wc -l
53
maverick-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   wc -l
67
natty-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables   wc -l
155

For example, here s the large sunrpc module. RW is read-write, ro is read-only, x is executable, and NX is non-executable:

maverick-amd64# awk '/^'$(awk '/^sunrpc/  print $NF ' /proc/modules)'/','!/GLB/' /sys/kernel/debug/kernel_page_tables
0xffffffffa005d000-0xffffffffa0096000         228K     RW             GLB x  pte
0xffffffffa0096000-0xffffffffa0098000           8K                           pte
natty-amd64# awk '/^'$(awk '/^sunrpc/  print $NF ' /proc/modules)'/','!/GLB/' /sys/kernel/debug/kernel_page_tables
0xffffffffa005d000-0xffffffffa007a000         116K     ro             GLB x  pte
0xffffffffa007a000-0xffffffffa0083000          36K     ro             GLB NX pte
0xffffffffa0083000-0xffffffffa0097000          80K     RW             GLB NX pte
0xffffffffa0097000-0xffffffffa0099000           8K                           pte

The latter looks a whole lot more like a proper ELF (text segment is read-only and executable, rodata segment is read-only and non-executable, and data segment is read-write and non-executable). Just another reason to make sure you re using your CPU s NX bit (via 64bit or 32bit-PAE kernels)! (And no, PAE is not slower in any meaningful way.)

About a week ago, I wrote about doing cross package checks in Lintian. At that time I had only played with looking up manpages in direct dependencies, which I hope will greatly improve the current binary-without-manpage stats (around 677 packages and 2750ish tags incl. overrides). Today, I decided to take on another challenge. Detection of circular dependencies between binary packages (created from the same source). We already have a little library for building dependency relationships; however I ended up not using it, since it has an important limitation. It cannot tell how the circular dependencies relate to each other. Let me demonstrate what I mean with an example. Suppose we have a couple packages that depend on each other like this:
pkg-core => pkg-A, pkg-D
# circle 1: A, B, C
pkg-A => pkg-B
pkg-B => pkg-C
pkg-C => pkg-A # circle 2: D, E, F
pkg-D => pkg-E
pkg-E => pkg-F
pkg-F => pkg-D
In this case, our current tool will be able to tell that all packages (possibly except root I did not check) are in a circular relationship. However, we can find better results by pretending we are trying to find Strongly Connected Components (actually that is exactly what we are trying to do here). So today, I implemented Tarjan s algorithm in Perl to solve this particular issue and committed it to my Lintian branch. If this branch is merged into the Lintian master branch, we can close #316283.

Recently there has been some major developments in DebConf11 organization. In short, I will list some of the most important.

Website

Official DC11 website has finally been completed and now contains a great deal of information for those interested in attending this years conference. Some of the most notable changes include:

Navigation

Frontpage now contains a small menu with links to most important parts of website, like About, Registration, Contact Sidebar menu is now divided in 3 categories:

• The Conference Links to pages which are directly connected with the Conference like About DC, Debian Day, Registration, Call for Papers, Talk Schedules, Payments Most of these links are hidden at the moment, and will be until the registration is open, to avoid any unnecessary confusion.
• More Information Basic information for attendees like Important Dates, Accommodations, Venue, Visa Everything you need to know about your stay in Banja Luka.
• Practical While these pages have almost nothing to do with the Conference itself, they do provide a vast information about city, getting to Bosnia, some practical information, as well as the Map of the whole city made my me :)

New Pages added

• How Can I Help This page contains some basic information for anyone who wants to help out. Weather by volunteering, sponsoring, or just by adding a banner on their website
  DC11: How Can I Help?
• Contact Instead of just sending visitors to mailto, we replaced it by a page which contains ALL contact information, emails AND phone numbers (which will be added just before DebCamp starts).
  DC11: Contact
• Sponsorship Just like with the contact page, we made a page to be more user friendly to any interested parties or individuals, and contains most important info, such as sponsorship levels and contact address.
  DC11: Sponsorship
• About DebConf11 Actually it s just a page with a content copied from frontpage (which is now used for something else).
  DC11: About DebConf11

New features:

• Documentation Is now used to store all important documents and records for public use and sharing, like brochures, official government documents, important public mails, as well as the recordings of all IRC meeting logs. Can be found at:
  DC11: Documentation
• Frontpage: Navigation To ensure the main goal of website, information availability, frontpage has been redesigned to provide maximum accessibility as well as easy access to any part of the website. DC11: Frontpage
• Frontpage: Latest News To keep the public and attendees well informed of any important events and developments, we decided to add latest news section. Note however, that if you want to stay completely informed of any changes and updates, we still recommend subscribing to our mailing list, which can be found under contact page.
  DC11: Frontpage
• Map of Banja Luka Because of lack of data on Google Maps and Open Street Map, as well as some other minor local maps, we made a small map of almost whole city and added around 60 or 70 locations which we consider to be of importance for our attendees. Such locations include hotels, parking spots, restaurants, bars, clubs, petrol stations, taxi stations, etc. This page uses simple JavaScript and is not dragable . Therefore we added Index Location to auto-locate the needed locations, as well as the legend to clarify the category of locations. Pointing your mouse over a certain location will open a small bubble with some info on that location/object. We should also point out that some of this data may not be 100% correct (ie working hours may be off ). Map is available at:
  DC11: Banja Luka City Map

Bosnian language

Site is now available on Bosnian language for native speaking attendees, should they have problems with English version. Every page is available on both languages, which can be changed by clicking on ba/en flag in upper left corner, or DC11: Bosnian Version.

Design

As you may have noticed, the official page received a small face lift. New header with the Government building, a small token of appreciation for all the help the Government is providing; as well as some minor changes in CSS and color scheme. While talking about design, we d like to thank Leandro G mez for his help with the header.

Sponsorship Sponsorship Levels

As agreed on the meeting, which took place on 22. of February, [Meeting logs], following sponsorship levels will be used for this years conference:

• Steel < 1.000
• Bronze > 1.000
• Silver > 5.000
• Gold > 10.000
• Platinum > 20.000

Main reason for lowering amounts is due to last years results of high increase in the same. As for the benefits of these levels, the only thing changed is t-shirts / bags places; we believe t-shirts are much more noticeable than bags, and have therefore been promoted to Silver, while bags have been downgraded to Bronze. For a full list of requirements and benefits, please visit: DC11: Sponsorship Sponsorship Brochure

Sponsorship brochures have finally been completed and are available for a public distribution. The brochures are available in 3 qualities: low, high and original. Low and high quality brochures, ~6Mb and ~8Mb respectively, are for normal distribution to our sponsors, while original quality, at around 240Mb, is intended for maximum quality printing. Just as with the website, each quality is available in both Bosnian and English. Current version of the brochure is 1.1 and is most likely the final one. These brochures are available at Documentation page: DC11: Documentation >> Documents made by Local Team Or download them directly:

• Sponsorship Brochure LQ [en]
• Sponsorship Brochure HQ [en]
• Sponsorship Brochure OQ [en]
• Sponsorship Brochure LQ [ba]
• Sponsorship Brochure HQ [ba]
• Sponsorship Brochure OQ [ba]

Also, I d like to thank Mirosal Remetic for making a great template and Pablo Duboue for some very valuable suggestions regarding the structure of the brochure.

Visas and Customs Rules

Many questions have been raised regarding Bosnian visa regime. We got in contact with the embassy and they clarified who can enter our country with(out) Visa. The list can be found on DC11 Wiki: Visa regime. It also states, which countries have a privilidge of ID-only entrance. If your country is not listed, that means you will need visa. If you want to know what exactly you need to get one, please visit the this official Government page and chose your country from a drop-down menu. As for the visa itself, as well as the list of Customs Rules, please read DC11: Visa.

Also, thanks to Darjan Prtic for getting the list from the Government officials.

So, what s next?

If you think, that is it for now, you are dead wrong. At this very moment following is being organized and developed:

• Registration Registration Team is currently hacking penta and modifying it for this years needs and conditions. We expect to have registrations open by the end of March / beginning of April.
• Travel and getting to Banja Luka Being one of the greatest obstacle, Travel Team is working hard on finding best routes for attendees and mapping the city
• Sponsorship With final decision and agreement for sponsorship levels and brochures ready for public distribution, Sponsorship Team is now actively looking for new sponsors, global and local, preparing various promotional material, as well as planning our advertising strategy.

Final word

Well, these are pretty much the highlights of some recent and some future developments of DebConf11 organizational team. Mind you, there s a lot more going on, but I tried to give a small summary from the inside. Should you be interested in attending, helping out, sponsoring or just have some questions, feel free to ask them on our mailing list at: debconf11-localteam@lists.debconf.org. I should inform you that this is a public mailing list and its archives are available for a broader public. If you do not wish for your mail to be made public, please direct any enquiry directly to me trough the Contact Form or any other member of Core Local Team, Adnan Hodzic or Velimir Iveljic.

Now available for early testing, Ubuntu Karmic Alpha 1 has a kernel feature I ve long wanted in Ubuntu: NX emulation. Basically, if your hardware lacks NX support, the kernel will emulate the feature using memory segment limits and ordering. This was AFAIBT originally developed by PaX, and a similar version (with histories including work by Solar Designer and maybe OpenBSD?) has been carried in RedHat/Fedora for a while now (under the larger project called ExecShield , covering multiple protection technologies). As more and more of the monolithic ExecShield kernel patch has been taken upstream (many thanks to Arjan van de Ven for pushing them), the patch in RedHat has been shrinking. Recently, Dave Jones split up the remaining pieces into logical chunks small enough that I could actually read it without going cross-eyed. From this, I ported the nx-emulation patches to Ubuntu s kernel, and now they re happily live in Karmic. So, instead of this:

$ ./vulnerable-setuid-program $OVERFLOW_AND_SHELLCODE
# id
uid=0(root) gid=0(root) groups=0(root)

We get this:

$ ./vulnerable-setuid-program $OVERFLOW_AND_SHELLCODE
Segmentation fault (core dumped)
$ dmesg tail -n1
[170131.763976] vulnerable-set[16278]: general protection ip:80489c5 sp:bfa3e330 error:0 in vulnerable-setuid-program[8048000+1000]

Though, as always, please just use 64bit instead. :) Update: gave credit to PaX, thanks for the corrections!

Some brief highlights of the last three months of Debian Eee PC development. Thermal and ACPI breakage resolved in 2.6.26-7 We’re pleased to see that in the upload to Sid of linux-image-2.6.26-1-686 version 2.6.26-7, the pair of 2.6.26 bugs we’ve been tracking that have made it difficult for Eee users to upgrade their systems have been resolved. Since then 2.6.26-8 has been uploaded and is expected to enter Lenny this week due to a freeze exception. Once the new kernel has migrated we will move quickly to build and release a new installer that includes it. Ath5k wifi works on Eee PC in Linux 2.6.27 Jean-Christophe reports that ath5k works in Linux 2.6.27 on the Eee PC 701, and just needs a small patch to work with our eeepc-acpi-scripts package. This is good news for those of us with models 701, 900, 900A and 1000HD who have been wanting to get off of the non-free Madwifi drivers and onto DFSG free drivers. New Eee PC model 701SD wifi support in the works Users of the new Eee PC Model 701SD have just started showing up looking for support in mainstream Linux distros. Martin Filtenborg confirmed using our Eee PC Live image with the GPL’d rtl8187se driver from Realtek that we can at least use it to connect to an unencrypted AP, get an IP address and ping other hosts. Of course, it is one thing to have a working vendor-supplied driver and quite another to have mainstream support. We’ll make do with what we have now, but will be seeking a mainstream solution as soon as possible. We’re seeking more testers and developers to work on this. To date, an ITP has not been filed, as it is not yet clear who is going to carry this work forward. Chasing the 5 second boot An interesting discussion on Arjan van de Ven and Auke Kok’s work to get an Eee 901 to boot in 5 seconds took place this month. While the Debian Eee PC team is not making work on this a priority, we’ll keep an eye on it to see if Debian can incorporate some or all of the techniques they used so that our users can benefit without making radical changes to their systems. Working towards mainstream support for rt2860 Our filing of an ITP for rt2860 (the wifi driver for models 901, 1000 and 1000H) was followed by discussion about how to separate out the GPL’d driver from the embedded non-free firmware so that it can at least go into contrib. Glenn Saberton has been working on rewriting the build system around kbuild and separating out the firmware. Numerous improvements to ACPI scripts Since my last progress report, there have been numerous improvements to the eeepc-acpi-scripts package to deal with all of the various models we now support and make the scripts more robust and flexible. Check out the changelog for details.

Yesterday, 10 July, was the due date for the second milestone of my work on DebGraph. I am happy to report that we are roughly two weeks ahead of schedule, so meeting this milestone was not a cause for worry. We now have support for the following graph operators:

• Difference
• Intersection
• Filter (by properties)
• Find Cycles (via Tarjan's algorithm)
• Find Dependencies
• Find Reverse Dependencies
• Symmetric Difference (XOR)
• Union

The next milestone includes the development of a high-level language (or integration with an existing extension language) that streamlines the construction of complex queries using the operators listed above. We can build arbitrarily complex queries using the C++ operators, but dealing with the static typing and compiler toolchain can be very clunky. As such, I have spent the past week working on Lua bindings for DebGraph, which will enable us to query the graph of Debian packages from a clean, dynamically typed language. Lua has a powerful C API that exposes the Lua stack and lets us move DebGraph information to and from the Lua interpreter. I'm writing documentation that outlines how to use DebGraph from both C++ and Lua in order to make this work accessible to more folks. Sneak peak
As an example, we can utilize the FindCycles operator in Lua as follows:

libdg = package.loadlib("./libdebgraph.so",
"luaopen_libdebgraph")
libdg()
LoadPackages('cache')
-- 'g' is the main graph of unstable binary-arm packages
cycles = FindCycles(g)
print("Found " .. #fc .. " cycles")
for comp_key,comp in pairs(cycles) do
    comp_nodes = ""
    for node_key,node in pairs(comp) do
        prop = GetProperty(node, "Package")
        comp_nodes = comp_nodes .. prop .. " "
    end
    print("* " .. comp_nodes)
end

The above Lua script produces the following result:

reading cache/unstable/main/binary-arm/Packages
Found 61 cycles
* debconf-english debconf-i18n debconf
* perl-modules perl 
* cdebconf fontconfig-config fontconfig gsfonts-x11
libcairo2 libfontconfig1 libgtk2.0-0 libpango1.0-0
libpango1.0-common libxft2 ucf x11-utils xutils
[...]

These are the package names in the strongly connected components, shown in alphabetical order. There is still a lot of work to do before the Lua binding will achieve feature parity with the core library, but we have now laid the foundation (and a brick or two).

My previous entry was somewhat misleading in one respect - the discussion of the power consumption of a downclocked processor. The problem is that nowadays, halving your CPU frequency doesn't halve the power consumption (see the figures in Arjan's slides from OSCON last year, for instance). I'm assuming that this is due to the cache size on modern hardware being sufficiently large that it dominates the power consumption of the processor. Dropping the frequency doesn't reduce the amount of power required to keep the contents of the cache alive, so the saving is less than you'd expect. Deeper C states disable the cache and save much more power.

So, if halving your speed means everything takes twice as long but doesn't even halve your power consumption, what's the point in having P states at all? There's a certain amount of latency and power involved in moving between C states, and if the choice is between rapidly cycling between full speed and C4 or just sticking at low speed and maybe dropping into C1 or C2, then executing code at the lower performance state may be beneficial. The ondemand governor takes this into account by looking at the amount of load on the processor over time, so if this doesn't hit a threshold value it'll assume that you're better off staying at the lower performance level.

It’s interesting to see how far, and yet how much more work we need to do on power management for Linux. I recently got a new laptop — a Lenovo Thinkpad X61s — and using the powertop tool, I was able to configure my system to the point where in what I can “airplane mail reading mode” (mailbox preloaded into memory, USB disabled, wireless and ethernet disabled, backlight down to 30% brightness, sloppily written power hogs like Firefox and Notes — every single application writer should be forced to run powertap and explain why their program feels it necessary to constantly wake up the CPU), I can get my usage down to about 9.8 watts. Using the 8 hours extended battery, that’s 8 hours of battery life, although granted doing very little. On the flip side, if I’m doing a major kernel compile, I can drive up utilization up to almost 30 watts, which means less than 3 hours of battery life. So that’s definitely the good news; Linux can sharply reduce its power consumption to the point where it is highly competitive with Windows. (And probably better than Vista, just because that OS is so heavy and bloated.) So thanks and and a tip of the hat to Intel and to Arjan van de Ven for making such a useful tool like Powertop available. So now for the bad news. Getting down to this level of power saving thriftness, where the laptop is carefully sipping only the minimal amounts of power from the battery, is definitely a work in progress. First of all, you can only get this level of power savings by unloading a specific USB driver, uhci_hcd. This will disable low speed devices (including unfortunately the fingerprint reader and the EVDO WWAN device if you were silly enough to buy one that was built into the laptop as opposed to a stand-alone card that you can swap between laptops and lend out to friends as necessary). But how many users are going to open up a terminal window, su to root and type the command “rmmod uhci_hcd”? And know how to reload the driver using “modprobe uhci_hcd” when they need to use the USB devices again? A similar problem exists for Network Manager; when the user disables the network by right-clicking on the applet, why doesn’t it automatically bring down the interface, instead of forcing the user to manually su to root and then type the command “ifconfig eth0 down; ifconfig wlan0 down”? A more serious problem is the Intel Wireless driver for the 4965. Even with the wlan0 interface configured down, and with the RF kill switch enabled, keeping the iwl4965 driver loaded will still cost you an extra full watt of power. When you’re down to 9.6 watts, that means that keeping the iwl4965 driver loaded when you don’t need it will cost you a 10% reduction in your battery life! That’s just sloppy, and hopefully it will be fixed in a future update to the iwl4965 driver, but as long as you don’t mind manually removing and reloading it, you can work around this power-saving oversight. A bigger issue, though, one for which no workaround exists, is that unlike the ipw3945 drivers, which at least had private, non-standard iwpriv commands to engage the 802.11’s power-saving features, the iwl4965 driver has neither the non-standard Intel iwpriv interfaces, nor the standard iwconfig interfaces for enabling any kind of powersaving features, including changing the transmit power of the card. So while powertop deserves plenty of kudos, iwl4965 deserves a wag of the finger from a power saving viewpoint. No doubt Intel just needs to allocate more money to its Open Source Technology Center so it get more of its crack developers to work improving Linux support for their processors and chipsets. Speaking of which, I’m still waiting for an Intel x.org 965GM driver that can support compiz/beryl and simultaneously show video clips at the same time… And being able turn off the 50 interrupts/second generated by the video card when they aren’t needed because 3-d graphics aren’t currently in use, without requiring a restart of the X server, would also be a nice touch. The bottom line is that Linux power savings and Linux support for laptops in general is much better than it was a year ago, and a lot of credit has to go to the efforts of Intel’s teams producing such good work as powertop, their wireless drivers, and their open X server drivers. We still have a lot of work left to be done, though!

So, last week was a bit bumpy since I was sick for a couple of days, and then had a power outage on Friday and Saturday, thus not being able to keep up with my daily RC bug fixing, but I've been catching up since then. I've uploaded patches done by Arjan Oosting, for packages that wouldn't compile with autoconf2.6: #379812 (kde-style-polyester), #379813 (kxmleditor) and #379815 (klog).

I uploaded a patch by Mart n Ferrari for lilo: #374477 (use MAKEDEV instead of mknod at postinst), and another patch by Mart n for courier-authlib #378571 (fixing the permissions of /var/run/courier/authdaemon).

I uploaded a patch by Andreas Jochens for ntlmaps: #379700 (fixing the build-dependency). A patch by Luca Bruno for predict: #379495 (fixing a change of location of forms.h). And a patch by Mike O'Connor for stardict: #379152 (fixing a misuse of size_t that made it fail in 64bit architectures).
Stardict had a problem with rpath that made me get to know the LIBTOOL_IS_A_FOOL hack, and I had to apply that, so that the binaries were not screwed up.

I also uploaded a fixed version of yacas, that included patches from Arjan Oosting (fixing #379261 and #379895) and Braun Gabor (fixing non-RC #295413). However, it's not like the only thing I've done is upload patches done by others. I've also done some patches myself:

• #379275, fixing fillets-ng's FTBFS.
• #379486, fixing a bashism in cbuild.
• #379200, changing PWD for CURDIR so that sudo works for building bluez-utils.
• #377781, fixing monotone so that it builds with the latest gcc, although it took a new upstream release for it to build in hppa.
• #378173, adding some checks for NULL, so that the new libsdl1.2-image does not make programs segfault
• #381248, dropping PAGE_SIZE in favour of sysconf(_SC_PAGESIZE) in libsdl1.2 so that it builds in powerpc

The amount of bugs currently affecting the next release is 247. It's not a secret that we are a bit behind the schedule (we should be at less than 200 bugs by now). But it's also totally possible to get back on track if we work together on fixing the current bugs and we stop uploading unneeded new releases that trigger new transitions.

That's nice. Apparently SUSE/Novell are planning to no longer include any proprietary (kernel) drivers in their Linux distributions. (Most of) the kernel developers dislike binary drivers in the kernel and SUSE/Novell are clearly supporting the developers with their move. Although they plan a system for including binary drivers from userspace somehow, I still think this is a good sign. I hope it will help to convince some hardware manufacturers to release the source code of some of their (now) proprietary drivers... This whole debate was started by Arjan van de Ven's original post to the LKML in December 2005, AFAIK. (via Heise)