Captain Kerbal

Category: SSS

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!

Advertisements

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…

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…

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…

SSS mk.2 – Possible architecture

The aims of the proposed successor of SSS, SSS mk.2 (or another name…), are detailed in this post.

Currently, I visualise it something like this:

Applicator:

Generates a state from a set of plaintext files, checks for deviations from the state, and fixes them as required. Kind of like Make, but more specialised.

Syncer:

Syncs the state files across computers. The best method would see to be to use Git over SSH – the advantage over immix is that I can have multiple branches.

Timer:

Runs the syncer and applicator every few hours/minutes/seconds. This could be as simple as a script hooked up to a systemd/launchd/init service file, or a cron job.


The most complex part is the applicator. Generating the state from a set of plaintext files would be challenging, so would checking for deviations and applying them.

The state would probably be defined in a set of plaintext files, with the target state declared within.

For instance, to make sure some packages were installed, the file would include:

installed_packages = lynx,vim,fbpdf,other

Or something like that. Add in if statements, include statements, variables, and some commands, and the resulting basic declarative language should be able to define the target state, including understanding the host OS and changing accordingly (launchd vs. systemd service files, for instance), the current architecture, the specifics of the host system, and the hostname (in essence, the computer ID). I will look to see whether my chosen language has a library that could handle this part for me, but otherwise I think it should be within my grasp to create something that worked.

One additional challenge would be some sanity checking – checking that a package was not both required and forbidden, for instance. I’m not sure where that would fit, but it would probably be the most challenging task.

Checking for deviations would be hard, but not insurmountable. For instance, depending on the package manager, the command for checking for a program being installed would vary. On Mac OSX, the simplest method would be to try to find the program binary, since there is not native package manager, and resort to macports or homebrew as required for installing. Being able to define behaviour – like how to check that a package is installed – in the declarative language would be a must. Actually checking the state should be reasonably easy – run through each of the proposed state variables and check with the method defined for that particular system/architecture/OS whether they are satisfied. After creating a list of unsatisfied substates, the checker could pass the list on to the applicator.

Applying the unsatisfied substates would be reasonably easy. Like checking for deviations, provided the way to resolve the issue was defined somewhere – how to change the relevant config file, how to install packages, how to add a user – SSS mk.2 would just have to apply that method, doing something if it failed (printing an error, logging, messaging the user, or similar).


Some expected challenges include:

  • Local vs global changes. On computers that only I use, I’d want the changes to be global. However, on shared computers – such as the Mac I occasionally have to use – the changes would have to be local only, and because I don’t have super user rights, I’d have to install software locally, as well as changing the configuration locally.
  • Depending on how much my chosen language handles low level details, writing a powerful declarative language for the configuration could be challenging. So much so, that I might need to consider an alternative method. I hope not… in Python it would be reasonably easy!
  • Working on computers with different directory structures. My computers all run Arch Linux, so they are easy. However, sometimes the directory structures can be radically different. I’d have to be careful to make sure all locations were not hard coded and instead referenced back to an OS-specific config file. Especially if I ever do manage to make a specialised distro for the Toshiba.

Happy Holidays

Holidays are nearly here!

Well, almost. Several weeks away, in fact. But I’m looking forward to them 🙂

I have been doing some planning, however. The plan so far involves:

  • Creating the iMac case
  • Working on my syncing system, specifically the mk.2 version
  • Bringing cling to a state of basic completion
  • Work on the specialised distro for my Toshiba

Of course, there are other goals as well, but they are outside the scope of this blog 🙂

I’ll see how far I get…


I’ve also managed to make some progress on cling. To date, I’ve added the very basic functionality, and have cleaned it up. The next steps are to finish cleaning the current code up, write some tests, write some CLI binaries using libcling to test that I have the basics covered, and then release 1.0!

Good progress so far 🙂