Captain Kerbal

Category: Coding

Dell? Dell??

Since I told Dell that the second battery was also broken, I heard this reply:

If this is the case then we shall assume there could be some hardware faults on the system board of your Vostro 1510 system.

I wasn’t ready to accept that as a reply – how come my machine works if given a known good battery, then, and the new battery also does not work in another known good machine? – so I’ve emailed back a few times since then, and still haven’t heard back. My next port of call is to take the time to phone Dell, and ask for an update…

In other news, I’ve been playing around with ozone-wayland, trying to create a PKGBUILD for HEAD that doesn’t download too much. Apparently 22GB is required if you use the method described in the README for the project, which is far too much! ozone-wayland releases only need ~250MB of downloads to build, partially because they are built against a certain release of chromium.

I also looked at Wren – specifically, I asked a question on the google group re creating loadable bindings to C libraries for wren. The answer (at the moment) is “not possible”, but if I have a chance I plan on seeing what I can do with the patch set someone else posted.

I’ve also been making slow but steady progress on SSS mk.2, with “slow” being the key word. I’m hoping that I will have finished it by the end of the year!

When a 2SAT problem isn’t actually a 2SAT problem.

Answer: When I get it wrong.

I asserted that I was trying to solve a 2SAT problem for my SSS2 program. I was wrong.

Specifically, the problem I was trying to solve is actually a more general boolean satisfiability problem. I can’t apply Tarjun’s SCC algorithm, which is sad, because I’ve just coded one up. The root of the issue is that I allowed OR statements, which you can not have. At least not how I was doing them.

I discovered this, because I was thinking about how I was going to create the implication graph. I can create an implication graph, but it will not be solvable through apply a SCC algorithm. Here’s an example of why:

‘a’ is a variable. It is true.

‘b’ is also a variable. It is true if all of [‘a’] is true.

Now, in this case, it should work fine. But if I construct an implication graph for the more general instance, then it doesn’t work. The implications are that, if ‘b’ is true, ‘a’ must also be true. And if ‘a’ is false, then ‘b’ must also be false. Which is not enough to run a depth first search on, or a SCC algorithm – at least not how I currently understand it.

The problem lies in the ‘all’ statement. It’s easy to create indeterminate statements using ‘all’ – for instance:

‘a’ is a variable. It is true.

‘b’  is also a variable. It is true if all of [‘a’, ‘c’] is true.

‘c’ is also a variable. It is true if all of [‘a’, ‘b’] is true.

Are both ‘b’ and ‘c’ true? Or are they both false? Without additional inputs, the graph is indeterminate.

I believe that, to avoid this, I’ll have to make sure that the set of operators is not functionally complete.

Or, I might (still) have the wrong end of the stick…

Why shell sucks

I’ve written a few toy programs in shell – I’m marginally proficient, at least. Or, too put it another way, I’ve found where the manual is…

I’ve been considering a new build system for Takahe Linux, or at least a refreshed version, so I was wondering what to write it in. Currently, I’m using a shell script that works. That’s about the only positive thing I can say for it!

Actually, it’s not too bad. The problem is that I can’t see any half-decent way of adding some features I’d like – namely, dependency handling – without making a mess of what is a relatively simple shell script.

Anyway, I ended up writing a list of things I disliked about shell scripts – a list of things that make shell scripting suck. Some are just annoying; others can cause catastrophic failures (read – data loss, corruption, general pain)!

  • No array datatype! Actually, having everything as a string can be annoying, too.
  • Unassigned variables can be accessed.
  • Lack of clear namespaces.
  • Lack of multiple return variables.
  • Too many interactive functions (just general language bloating…).
  • Awkward (arguably non-existent) multi-threading support.
  • Syntax is not at all forgiving – forgetting to quote something properly can be bad, for instance. And it can even work, until that moment where it doesn’t… and you suddenly loose files because a directory had a space in it’s name!
  • Slow. This is not really an issue…
  • Error checking is weird. For instance, by default, failures in a pipeline are silently ignored in Bash.
  • There are many, many different shells. All of which behave differently for different things…
  • Colour is nice. Until it breaks another script…
  • Parsing the output of commands is inherently prone to breakage!
  • You have to learn the syntax of lots of sub commands just to get something to work. Or languages within languages; sed, for instance!
  • There are no libraries. You have to use commands instead. Which can be really inflexible (how do you propose to pass <insert complex datatype here> to that command, and how are you going to parse the complex output in a sensible way?).

Just to show that I’m not completely against shell scripts, here’s why I do use them:

  • Light. Bash has a 4MB memory overhead on my system; dash 2MB. Python uses 10MB… on a good day.
  • Simple. Kind of. For some things…
  • File-orientated, which can be quite nice.
  • High level. Writing some of the simple stuff in C would be even worse than writing it in shell…

Generally, though, I’d like a scripting language that was a ‘real’ language – with proper datatypes, better error handling, and so forth. So I went looking for ‘sane’ alternatives.

Here’s some that I found:

rc is lightweight (1MB RSS), and it supports arrays. It still is a shell-based language, though…

lua is not designed for shell scripting, so it’s a bit awkward. In terms of performance, it’s one of the best interpreted languages, and uses ~2MB RSS on my system.

perl is well known as being a messy language – even more so than shell. It is, however, heavily designed to be a replacement for shell scripting, so it’s possibly the best fit. On the other hand, if perl, why not rc? Perl is about 4 times as ‘heavy’…


Generally, none of those options sound attractive. Lua’s probably the best bet, because it places value on correctness, at least in comparison, but shell scripts directly translated into lua are very verbose!

What I’ll probably do is see whether I can make make work. Or perhaps just become really frustrated…

How cool is that? – Tarjun’s SCC algorithm

I worked through an implementation of a Tarjun’s SCC algorithm to solve a version of the 2SAT problem fairly recently, for an online course. It was a fairly complex assignment, with no real direct analogue for me, so it took a while to work through!

One thing I definitely did not expect was for it to have a direct practical application within a few months of completing my version. Given that we covered a wide range of algorithms, I would have thought one of the other ones that I had at least heard of before would have come up first!

Still, I’m glad I know about it. Strictly speaking, I could achieve the same purpose with a similar, simpler algorithm, but I gain a few nice ‘features’ with Tarjun’s SCC algorithm, and it can be implemented in linear time – which is surely a good thing. Plus, I’ll get to explore a practical application of it, which is always fun 🙂

“What practical application?” you may be asking. If you read this far, that is. It turns out that I’m solving a problem that can be expressed as a 2SAT problem in my SSS2 project. Specifically, I would like to have a set of files, each describing a ‘state’ (say, having mpv installed), which are either included, or not included. There can also be relationships between files – like “only install this configuration file if this program is installed”. Finally, there can be relationships between variables and files – “only install xf86-video-nouveau if ‘this machine runs X’ and ‘this machine has X installed'”. All of those relationships would, preferably, be able to be described by a logical statement, where all the variables are represented by files.

This is a 2SAT problem – each file is either ‘on’ or ‘off’ (true or false), and the relationships between the files use the standard logical operators. If I create an implication graph from the files, and then run Tarjun’s SCC, I can solve the problem, load all of the files that are ‘on’ into a single, combined ‘state’, and pass that to the rest of the program.

The above is a bit of a simplification, but that’s pretty much what will happen.

There are a few “limitations” with this approach:

  • Tarjun’s SCC is a bit of an overkill. I believe could actually implement a solution using DFS; however, Tarjun’s SSC does give me a bit more information, allowing me to set all unrestricted ‘states’ to ‘on’ as needed, for example.
  • I cannot generate requirements automatically. This is something that would be hard to remedy!
  • Variables are represented by ‘meta-files’. This is… imperfect. But it’s probably the easiest way.

Generally, though, I think it’ll be pretty flexible, and hopefully easy enough to write.

One design decision that I’m not completely sure about is how I’ll create the implication graph. My current idea is that each file will have at least two variables; IsAny and IsAnd. Both will be a list of other files, with Any translating to an “or” relationship, and And translating to an “and” relationship. I’m not sure whether I’ll have another couple of variables that are the Not equivalents, or whether I’ll just use an ‘!’ infront of the filenames. I’ll also need meta-files, which could get a bit messy… but I’m already doing that for groups, and the alternative is parsing a custom logic string, which sounds even more messy to me!

Tentative SSS progress

Well, I’ve made some progress on SSS2. I think.

I’ve mostly been working on implementing the testing framework so I can have the degree of safety automated testing provides. Along with that, I’ve come across a couple of posts about CM systems in general, that I think are relevant to what I’m trying to do. Specifically, the part on the ideal management system is pretty close to what I’m trying to achieve – I hope to glean some ideas from it as to what I need.

I’ve also been considering how best to implement the recipes – the files that describe what the system needs to do to find out and change the current ‘state’ of the system. Currently I’m just executing some scripts and using standard argument passing and so forth to communicate. That’s ugly, but it works. I went looking for alternatives and discovered that, since Go does not support dynamic module loading, I’m going to have to stick with it. However, I may resort to using a more complicated argument passing layer instead – either encoding the arguments, or passing them as environmental variables, or through a couple of pipes, or something else like that.

So, progress is being made. Slowly. I’ll get back to it now…

DSDT, ACPI, and specifications galore

As of late, I have been fiddling around with the Toshiba, with the aim of getting a few more things working. It’s been a somewhat productive period, since I’ve made some good progress on some fronts.

What I’ve been doing can be split into about 3 areas:

  • Trying to get the hard drive controller to work at a decent speed.
  • Looking at the ACPI specification and the DSDT table from the Toshiba to try to figure out what is supported and what is not.
  • Generally optimizing the kernel.

The first area is fairly self explanatory. I’ve discovered (after perusing the source code) that the pata_legacy driver is dropping back to using PIO0 – that is, PIO ‘zero’, which is limiting the speed to 3MB/s. If that. In theory, according to the DSDT table, the controller should be capable of at least DMA2, which is capable of more than twice that. To complicate matters, the PATA chipset is ‘special’, and hides itself inside the PCI host bridge. The PCI device ID is 0601, which is not supported in the kernel… however, Alan Cox made a couple of mentions on the mailing lists suggesting that the chip, was, in fact, a Toshiba Piccolo controller. I both have the documentation (now) for the Piccolo controller (series, apparently), and there is support in the kernel (albeit not for my particular chip), so I should be ready to go. Right?

Maybe not. I added the PCI ID to the list of supported chipsets for the piccolo driver, recompiled the kernel, and watched with baited breath. It crashed… and I can’t read what happened, because the PgUp button is broken. EDIT: I’ve fixed the PgUp button. It has a little ‘cap’ inside which had moved out of it’s socket, preventing it from working. That is now fixed…

I also tried the ‘ata-generic’ driver, and the ‘pata_acpi’ driver, both of which failed. I have yet to try the ‘pata_of_platform’ driver, which I’m not holding my breath over, or ‘pata_isapnp’, which might work but appears to be limited to PIO, albeit not PIO0.

So, the next step is to purchase a serial cable, setting the logging verbosity as high as it can go, and trying to figure out what is really happening… some additional printk’s might be involved!

As a side-effect of trying to get the hard drive controller to work, I discovered that ACPI actually works! I can now read the battery charge, shutdown properly, and see a whole bunch of ‘extra’ ACPI connected devices 🙂

It didn’t help with the pata_acpi driver, though, despite a HDD and CDROM entry in the DSDT, claiming to be generic ISA/PCI controllers. :/

Also, the backlight does not work. I’ll try the toshiba_acpi driver and see what happens…

While I was fiddling, I did tune the kernel somewhat. Boot times are now improved, although not by much, and things generally work better.

Overall, reasonably productive. Now, let’s see what I can do about that hard drive controller…

SSS2 design ideas

I thought that I would write down the ideas that have been slowly gelling in my head with regard to SSS Mk.2, the replacement for my current syncing system.

The basic requirements for the syncing system, as of now:

  • Lightweight. To run on the Toshiba, preferably less than 6MB of RSS when running, and written in a compiled language to minimise overheads. It also needs to be small to be a manageable project!
  • Provides all of the features of my current system:
    • Installed package management via ‘tasks’ or similar
    • Configuration file management (patches, custom files, and merging with pacnew files)
    • Enabled services management
    • User management. This would be a real improvement over the ‘hacked’ form used in my current meta-package based system.
  • Adds new features:
    • Git based states. This would allow state roll backs, branches for testing, and ‘sane’ state syncing across computers. I’d have to make sure that the number of branches was manageable, though, since merging would be purely manual.
    • No dependence on Pacman. This would hopefully allow me to also roll out a similar system on the other computers I use that I might not have admin rights to, and which aren’t Arch Linux based.
    • Automatic updating over the local network, or as a fall back, from an online git repo. That’s possibly a job for a dedicated daemon, though.
    • Simpler roll out (how?)
    • A simpler way to add new changes?
  • Easy to extend! This would be accomplished by having all of the information on how to change state – recipes to check, enable, or disable states – stored in plaintext files. If I wanted to add a new recipe, for instance, to add udev (or similar) rules, I could easily create a new recipe that did so. Although that particular example would be better served by just creating a new file…

I am aiming to end up with something like bcfg2, but designed to be suited to smaller networks, and written in a lighter language than python. But otherwise, something pretty similar!

I will consider other options, rather than a pure config file based system – one of the strong points of the existing system is that it leveraged existing code. This did lead to some limitations, but I’m trying not to reinvent the wheel…

If I did go down the purely config file based route, the system itself could be split into groups:

  • State parser: Parses the state description files and returns a state object containing information on the target state
  • State database: Holds information on the state at the last update
  • Logger: Interacts with the journal or log system… locally if required
  • Recipe runner: Runs the required recipes
  • State finder: Figures out the current system state using the recipes (how would this work for generic recipes?)
  • State comparer: Compares the current, old, and target states, and returns a ‘diff’
  • State updater: Runs the required recipes to fix the problems shown by the state comparer

Then there is the optional extras:

  • Command line tools: Updater, diff generator, other?
  • State description and recipe syncer, probably git based
  • Mailer interaction?
  • Monitor, for disk space, system health, etc (should really be another project?)
  • Group updater (after testing an update, roll it out?)
  • Group monitoring tools (host X,Y,Z are fine, host W has an issue)

The optional extras should, perhaps, belong to another group…


For the parser (both for the recipe and state description files), I either need to write my own or use a pre-existing language. Because I need conditionals, a simple scripting language would really be good, although it is probably over the top for what I am trying to do – conditionals are fairly simple, and lists would be nice, but other control structures are probably OTT!

I was also considering what I wanted to do with regards to config file management, since the current system relies on a shell script that is less than stable.

I did find some additional software that might help:

  • Augeas: Basically, a substantially more complex version of patchman, which is (potentially) better suited to what I want to do. It looks quite similar to the replacement that I had vaguely considered…
  • Lua: A lightweight scripting language. Overly complex for my needs, but better than bash, and with more features than dash, such as arrays.

I’ll evaluate each one and make a choice. Both seem lightweight, with minimal dependencies. However, they may be more complex than I need…