Luke Shumaker's Web Log

Announcing: btrfs-rec: Recover (data from) a broken btrfs filesystem

2023-07-10T00:00:00+00:00

Announcing: btrfs-rec: Recover (data from) a broken btrfs filesystem

I originally sent this email on 2023-07-10, but it has been caught by their bogofilter. Yes, it was plaintext. No, I didn't use GMail. Yes, I've successfully participated in vger lists in the past. Yes, I've reached out to postmaster; no, I haven't received a reply yet (as of 2023-07-14).

To: linux-btrfs@vger.kernel.org
 From: Luke T. Shumaker
<lukeshu@lukeshu.com>
 Subject: btrfs-rec: Recover (data from)
a broken btrfs filesystem
 Date: Mon, 10 Jul 2023 21:23:41
-0600
 Message-ID:
<87jzv7uo5e.wl-lukeshu@lukeshu.com>

Inspired by a mis-typed dd command, for the last year I've been working on a tool for recovering corrupt btrfs filesystems; at first idly here and there, but more actively in the last few months. I hope to get it incorporated into btrfs-progs, though perhaps that is problematic for a few reasons I'll get to. If the code can't be incorporated into btrfs-progs, at least the ideas and algorithms should be.

https://git.lukeshu.com/btrfs-progs-ng/

Highlights:

In general, it's more tolerant of corrupt filesystems than btrfs check --repair, btrfs rescue or btrfs restore.
btrfs-rec inspect rebuild-mappings is a better btrfs rescue chunk-recover.
btrfs-rec inspect rebuild-trees can re-attach lost branches to broken B+ trees.
btrfs-rec inspect mount is a read-only FUSE implementation of btrfs. This is conceptually a replacement for btrfs restore.
It's entirely written in Go. I'm not saying that's a good thing, but it's an interesting thing.

Hopefully some folks will find it useful, or at least neat!

1. Motivation
2. Overview of use
3. Prior art
4. Internals/Design
4.1. Overview of the source tree layout
4.2. Base decisions: CLI structure, Go, JSON
4.3. Algorithms
4.3.1. The rebuild-mappings algorithm
4.3.2. The --rebuild algorithm
4.3.2.1. rebuilt forrest behavior
4.3.2.2. rebuilt individual tree behavior
4.3.3. The rebuild-trees algorithm
4.3.3.1. initialization
4.3.3.2. the main loop
4.3.3.3. graph callbacks
5. Future work
6. Problems for merging this code into btrfs-progs

1. Motivation

Have you ever ended up with a corrupt btrfs filesystem (through no fault of btrfs itself, but perhaps a failing drive, or a mistaken dd invocation)? Surely losing less than 100MB of data from a drive should not render hundreds of GB of perfectly intact data unreadable! And yet, the existing tools are unable to even attempt to read that data:

$ btrfs check --repair --force dump-zero.1.img
enabling repair mode
Opening filesystem to check...
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
ERROR: cannot open file system

$ btrfs check --init-extent-tree --force dump-zero.1.img
Opening filesystem to check...
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
ERROR: cannot open file system

$ btrfs check --init-csum-tree --force dump-zero.1.img
Creating a new CRC tree
Opening filesystem to check...
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
ERROR: cannot open file system

$ btrfs rescue chunk-recover dump-zero.1.img
Scanning: DONE in dev0
corrupt node: root=1 block=160410271744 slot=0, corrupt node: root=1 block=160410271744, nritems too large, have 39 expect range [1,0]
Couldn't read tree root
open with broken chunk error

$ btrfs rescue zero-log dump-zero.1.img
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
ERROR: cannot read chunk root
ERROR: could not open ctree

$ mkdir out
$ btrfs restore dump-zero.1.img out
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
Could not open root, trying backup super
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
Could not open root, trying backup super
ERROR: superblock bytenr 274877906944 is larger than device size 256060514304
Could not open root, trying backup super

$ btrfs restore --list-roots dump-zero.1.img
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
Could not open root, trying backup super
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
checksum verify failed on 1048576 wanted 0xf81c950a found 0xd66a46e0
bad tree block 1048576, bytenr mismatch, want=1048576, have=11553381380038442733
ERROR: cannot read chunk root
Could not open root, trying backup super
ERROR: superblock bytenr 274877906944 is larger than device size 256060514304
Could not open root, trying backup super

$ btrfs-find-root dump-zero.1.img
WARNING: cannot read chunk root, continue anyway
Superblock thinks the generation is 6596071
Superblock thinks the level is 1

Well, have I got a tool for you!

(FWIW, I also tried manipulating the filesystem and patching to tools to try to get past those errors, only to get a different set of errors. Some of these patches I am separately submitting to btrfs-progs.)

2. Overview of use

There are two btrfs-rec sub-command groups: btrfs-rec inspect SUBCMD and btrfs-rec repair SUBCMD, and you can find out about various sub-commands with btrfs-rec help. These are both told about devices or images with the --pv flag.

btrfs-rec inspect SUBCMD commands open the filesystem read-only, and (generally speaking) write extracted or rebuilt information to stdout. btrfs-rec repair SUBCMD commands open the filesystem read+write, and consume information from btrfs-rec inspect SUBCMD commands to actually repair the filesystem (except I haven't actually implemented any repair commands yet... despite the lack of repair commands, I believe that btrfs-rec is already a useful because of the btrfs-rec inspect mount command to get data out of the broken filesystem). This split allows you to try things without being scared by WARNINGs about not using these tools unless you're an expert or have been told to by a developer.

In the broken dump-zero.1.img example above (which has a perfectly intact superblock, but a totally broken CHUNK_TREE), to "repair" it I'd:

Start by using btrfs-rec inspect rebuild-mappings to rebuild the broken chunk/dev/blockgroup trees:
```
$ btrfs-rec inspect rebuild-mappings \
    --pv=dump-zero.1.img \
    > mappings-1.json
```
If it only mostly succeeds, but on stderr tells us about a few regions of the image that it wasn't able to figure out the chunks for. Using some human-level knowledge, you can write those yourself, inserting them into the generated mappings.json, and ask rebuild-mappings to normalize what you wrote:
```
$ btrfs-rec inspect rebuild-mappings \
    --pv=dump-zero.1.img \
    --mappings=<(sed <mappings-1.json \
        -e '2a{"LAddr":5242880,"PAddr":{"Dev":1,"Addr":5242880},"Size":1},' \
        -e '2a{"LAddr":13631488,"PAddr":{"Dev":1,"Addr":13631488},"Size":1},') \
    > mappings-2.json
```
Now that it has functioning chunk/dev/blockgroup trees, we can use btrfs-rec inspect rebuild-trees to rebuild other trees that rely on those:
```
$ btrfs-rec inspect rebuild-mappings \
    --pv=dump-zero.1.img \
    --mappings=mappings-2.json \
    > trees.json
```
Now that (hopefully) everything that was damaged has been reconstructed, we can use btrfs-rec inspect mount to mount the filesystem read-only and copy out our data:
```
$ mkdir mnt
$ sudo btrfs-rec inspect mount \
    --pv=dump-zero.1.img \
    --mappings=mappings-2.json \
    --trees=trees.json \
    ./mnt
```

This example is fleshed out more (and the manual edits to mappings.json explained more) in ./examples/main.sh.

3. Prior art

Comparing btrfs-rec inspect mount with the existing https://github.com/adam900710/btrfs-fuse project:

Again, mine has better fault tolerance
Mine is read-only
Mine supports xattrs ("TODO" in Adam's)
Mine supports separate inode address spaces for subvolumes; Adam's doesn't due to limitations in FUSE, mine works around this by lazily setting up separate mountpoints for each subvolume (though this does mean that the process needs to run as root, which is a bummer).

4. Internals/Design

4.1. Overview of the source tree layout

examples/ has example scripts showing how to use btrfs-rec.
lib/btrfs/ is the core btrfs implementation.
lib/btrfscheck/ and lib/btrfsutil/ are libraries for "btrfs-progs" type programs, that are userland-y things that I thought should be separate from the core implementation; something that frustrated me about libbtrfs was having to figure out "is this thing here in support of btrfs bits-on-disk, or in support of a higher-level 'how btrfs-progs wants to think about things'?"
cmd/btrfs-rec/ is where the command implementations live. If a sub-command fits in a single file, it's cmd/btrfs-rec/inspect_SUBCMD.go, otherwise, it's in a separate cmd/btrfs-rec/inspect/SUBCMD/ package.
lib/textui/ is reasonably central to how the commands implement a text/CLI user-interface.
lib/binstruct/, lib/diskio/, and lib/streamio/ are non-btrfs-specific libraries related to the problem domain.
lib/containers/, lib/fmtutil/, lib/maps/, lib/slices/, and lib/profile/ are all generic Go libraries that have nothing to do with btrfs or the problem domain, but weren't in the Go standard library and I didn't find/know-of exiting implementations that I liked. Of these, all but containers are pretty simple utility libraries. Also, some of these things have been added to the standard library since I started the project.

4.2. Base decisions: CLI structure, Go, JSON

I started with trying to enhance btrfs-progs, but ended up writing a wholy new program in Go, for several reasons:

writing a new thing: I was having to learn both the btrfs-progs codebase and how btrfs-bits-on-disk work, and it got to the point that I decided I should just focus on learning btrfs-bits-on-disk.
writing a new thing: It was becoming increasingly apparent to me that it was going to be an uphill-fight of having recovery-tools share the same code as the main-tools, as the routines used by the main-tools rightly have validity checks, where recovery-tools want to say "yes, I know it's invalid, can you give it to me anyway?".
writing it in not-C: I love me some C, but higher level languages are good for productivity. And I was trying to write a whole lot of code at once, I needed a productivity boost.
writing it in not-C: This forced me to learn btrfs-bits-on-disk better, instead of just cribbing from btrfs-progs. That knowledge is particularly important for having ideas on how to deal with corrupt bits-on-disk.
writing it in Go: At the time I started, my day job was writing Go, so I had Go swapped into my brain. And Go still feels close to C but provides a lot of niceness and safety over C.

It turned out that Go was perhaps not the best choice, but we'll come back to that.

I wanted to separate things into a pipeline. For instance: Instead of btrfs rescue chunk-recover trying to do everything to rebuild a broken chunk tree, I wanted to separate I/O from computation from repairs. So I have btrfs-rec inspect rebuild-mappings scan that reads all the info necessary to rebuild the chunk tree, then dump that as a 2GB glob of JSON. Then I can feed that JSON to btrfs-rec inspect rebuild-mappings process which actually rebuilds the mappings in the chunk tree, and dumps them as JSON. And then other commands can consume that mappings.json to use that instead of trying to read the chunk tree from the actual FS, so that you don't have to make potentially destructive writes to inspect an FS with a broken chunk tree, and can inspect it more forensically. Or then use btrfs-rec repair SOME_SUBCMD_I_HAVENT_WRITTEN_YET to write that chunk tree in mappings.json back to the filesystem.

(But also, the separate steps thing was useful just so I could iterate on the algorithms of rebuild-mappings process separately from having to scan the entire FS)

So, I made the decision that btrfs-rec inspect SUBCMD commands should all only open the FS read-only, and output their work to a separate file; that writing that info back to the FS should be separate in btrfs-rec repair SUBCMD.

For connecting those parts of the pipeline, I chose JSON, for a few reasons:

I wanted something reasonably human-readable, so that I could debug it easier.
I wanted something reasonably human-readable, so that human end-users could make manual edits; for example, in examples/main.sh I have an example of manually editing mappings.json to resolve a region that the algorithm couldn't figure out, but with knowledge of what caused the corruption a human can.
I didn't want to invent my own DSL and have to handle writing a parser. (This part didn't pay off! See below.)
I wanted something that I thought would have good support in a variety of languages, so that if Go is problematic for getting things merged upstream it could be rewritten in C (or maybe Rust?) piece-meal where each subcommand can be rewritten one at a time.

It turned out that JSON was perhaps not the best choice.

OK, so: Go and/or JSON maybe being mistakes:

I spent a lot of time getting the garbage collector to not just kill performance.
The btrfs-rec inspect rebuild-mappings SUBCMD subcommands all throw a lot of data through the JSON encoder/decoder, and I learned that the Go stdlib encoding/json package has memory use that grows O(n^2) (-ish? I didn't study the implementation, but that's what the curve looks like just observing it) on the size of the data being shoved through it, so I had to go take a break and go write https://pkg.go.dev/git.lukeshu.com/go/lowmemjson which is a mostly-drop-in-replacement that tries to be as close-as possible to O(1) memory use. So I did end up having to write my own parser anyway :(

4.3. Algorithms

There are 3 algorithms of note in btrfs-rec, that I think are worth getting into mainline btrfs-progs even if the code of btrfs-rec doesn't get in:

The btrfs-rec inspect rebuild-mappings algoritithm to rebuild information from the CHUNK_TREE, DEV_TREE, and BLOCK_GROUP_TREE.
The btrfs-rec --rebuild algorithm to cope with reading broken B+ trees.
The btrfs-rec inspect rebuild-trees algorithm to re-attach lost branches to broken B+ trees.

4.3.1. The `rebuild-mappings` algorithm

(This step-zero scan is btrfs-rec inspect rebuild-mappings scan, and principally lives in ./lib/btrfsutil/scan.go and ./cmd/btrfs-rec/inspect/rebuildmappings/scan.go)

Similar to btrfs rescue chunk-recover, scan each device for things that look like nodes; keep track of:
- Checksums of every block on the device
- Which physical addresses contain nodes that claim to be at a given logical addess.
- Any found Chunk items, BlockGroup items, DevExtent, and CSum items. Keep track of the key for each of these, and for CSum items also track the generation.

Create a bucket of the data from Chunks, DevExtents, and BlockGroups; since these are mostly a Chunk and a DevExtent+BlockGroup store pretty much the same information; we can use one to reconstruct the other. How we "merge" these and handle conflicts is in ./lib/btrfs/btrfsvol/lvm.go:addMapping(), I don't think this part is particularly clever, but given that btrfs rescue chunk-recover crashes if it encounters two overlapping chunks, I suppose I should spell it out:

A "mapping" is represented as a group of 4 things:
- logical address
- a list of 1 or more physical addresses (device ID and offset)
- size, and a Boolean indicator of whether the size is "locked"
- block group flags, and a Boolean presence-indicator
Mappings must be merged if their logical or physical regions overlap.
If a mapping has a "locked" size, then when merging it may subsume smaller mappings with unlocked sizes, but its size cannot be changed; trying to merge a locked-size mapping with another mapping that is not for a subset region should return an error.
If a mapping has block group flags present, then those flags may not be changed; it may only be merged with another mapping that does not have flags present, or has identical flags.
When returning an error because of overlapping non-mergeable mappings, just log an error on stderr and keep going. That's an important design thing that is different than normal filesystem code; if there's an error, yeah, detect and notify about it, but don't bail out of the whole routine. Just skip that one item or whatever.

Now that we know how to "add a mapping", let's do that:

(The following main-steps are btrfs-rec inspect rebuild-mappings process, and principally live in ./cmd/btrfs-rec/inspect/rebuildmappings/process.go)

Add all found Chunks.
Add all found DevExtents.
Add a phyical:logical mapping of length nodesize for each node that was found.
Any mappings from steps 2 or 3 that are missing blockgroup flags (that is: they weren't able to be merged with a mapping from step 1), use the found BlockGroups to fill in those flags.
Now we'll merge all found CSum items into a map of the sums of the logical address space. Sort all of the csum items by generation, then by address. Loop over them in that order, inserting their sums into the map. If two csum items overlap, but agree about the sums of the overlapping region, that's fine, just take their union. For overlaps that disagree, items with a newer generation kick out items with an older generation. If disagreeing items have the same generation... I don't think that can happen except by a filesystem bug (i.e. not by a failing drive or other external corruption), so I wasn't too concerned about it, so I just log an error on stderr and skip the later-processed item. See ./cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go.

Look at regions of the logical address space that meet all the 3 criteria:
- we have CSum items for them
- we have a BlockGroup for them
- we don't have a Chunk/DevExtent mapping them to the pysical address space.
Pair those CSums up with BlockGroups, and for each BlockGroup, search the list of checksums of physical blocks to try to find a physical region that matches the logical csums (and isn't already mapped to a different logical region). I used a Knuth-Morris-Pratt search, modified to handle holes in the logical csum list as wildcards.

Insert any found mappings into our bucket of mappings.
Do the same again, but with a fuzzy search (we can re-use the csum map of the logical address space). My implementation of this is comparatively time and space intensive; I just walk over the entire unmapped physical address space, noting what % of match each BlockGroup has if placed at that location. I keep track of the best 2 matches for each BlockGroup. If the best match is better than a 50% match, and the second best is less than a 50% match, then I add the best match. In my experience, the best match is >90% (or at whatever the maximum percent is for how much of the BlockGroup has logical sums), and the second best is 0% or 1%. The point of tracking both is that if there isn't a clear-cut winner, I don't want it to commit to a potentially wrong choice.

4.3.2. The `--rebuild` algorithm

The --rebuild flag is implied by the --trees=trees.json flag, and triggers an algorithm that allows "safely" reading from a broken B+ tree, rather than the usual B+ tree lookup and search functions. I probably should have tried to understand the btrfs restore algorithm, maybe I reinvented the wheel...

This algorithm requires a list of all nodes on the filesystem; we find these using the same scan as above (./lib/btrfsutil/scan.go), the same procedure as btrfs rescue chunk-recover.

We walk all of those nodes, and build a reasonably lightweight in-memory graph of all nodes (./lib/btrfsutil/graph.go), tracking

each node's
- logical address
- level
- generation
- tree
- each item's key and size
each keypointer's
- source node
- source slot within the node
- tree of the source node
- destination node
- destination level implied by the level of the source node
- destination key
- destination generation
logical addresses and error messages for nodes that are pointed to by a keypointer or the superblock, but can't be read (because that logical address isn't mapped, or it doesn't look like a node, or...)
an index such that for a given node we can quickly list both keypointers both originating at that node and pointing to that node.

4.3.2.1. rebuilt forrest behavior (looking up trees)

(see: ./lib/btrfsutil/rebuilt_forrest.go)

The ROOT_TREE, CHUNK_TREE, TREE_LOG, and BLOCK_GROUP_TREE (the trees pointed to directy by the superblock) work as you'd expect.
For other trees, we (as you'd expect) look up the root item in the rebuilt ROOT_TREE, and then (if rootitem.ParentUUID is non-zero) eagerly also look up the parent tree (recursing on ourself). We try to use the UUID_TREE tree to help with this, but fall back to just doing a linear scan over the ROOT_TREE. If we fail to look up the parent tree (or its parent, or a more distant ancestor), then (depending on a flag) we either make a note of that, or error out and fail to look up the child tree. For --rebuild and --trees=trees.json we are permissive of this error, and just make note of it; but we'll re-use this algorithm in the rebuild-trees algorithm below, and it needs the more strict handling.
When creating the rebuilt individual tree, we start by adding the root node specified by the superblock/root-item. But we may also add additional root nodes grafted on to the tree by the --trees=trees.json flag or by the rebuild-trees algorithm below. So a tree may have more than 1 root node.

4.3.2.2. rebuilt individual tree behavior

(see: ./lib/btrfsutil/rebuilt_tree.go)

In order to read from a tree, we first have to build a few indexes. We store these indexes in an Adaptive Replacement Cache; they are all re-buildable based on the tree's list of roots and the above graph; if we have a bunch of trees we don't need to keep all of this in memory at once. Note that this is done 100% with the in-memory graph, we don't need to read anything from the filesystem during these procedures.

The first index we build is the "node index". This is an index that for every node tells us what root(s) the tree would need to have in order for the tree to include that node, and also what the highest item key would be acceptable in the node if the tree includes that root. We track both a loMaxItem and a hiMaxItem, in case the tree is real broken and there are multiple paths from the root to the node; as these different paths may imply different max-item constraints. Put more concretely, the type of the index is:
```
map[ nodeID → map[ rootNodeID → {loMaxItem, hiMaxItem} ] ]
```
We'll do a loop over the graph, using dynamic-programming memoization to figure out ordering and avoid processing the same node twice; for each node we'll
- Check whether the owner-tree is this tree or one of this tree's ancestors (and if it's an ancestor, that the node's generation isn't after the point that the child tree was forked from the parent tree). If not, we are done processing that node (record an empty/nil set of roots for it).
- Create an empty map of rootID → {loMaxItem, hiMaxItem}.
- Look at each keypointer that that points at the node and:
  - Skip the keypointer if its expectations of the node aren't met: if the level, generation, and min-key constraints don't match up. If the keypointer isn't in the last slot in the source node, we also go ahead and include checking that the destination node's max-key is under the min-key of the keypointer in the next slot, since that's cheap to do now.
  - Skip the keypointer if its source node's owner-tree isn't this tree or one of this tree's ancestors (and if it's an ancestor, that the node's generation isn't after the point that the child tree was forked from the parent tree).
  - dynamic-programming recurse and index the keypointer's source node.
  - for every root that would result in the keypointer's source node being included in the tree:
    
    . If the keypointer is in the last slot, look at what the what the source node's last-item constraints would be if that root is included, and can now check the max-item of our destination node. We check against the hiMaxItem; as if there is any valid path from the root to this node, then we want to be permissive and include it. If that check fails, then we're done with this keypointer. Also, make node of those loMaxItem and hiMaxItem values, we'll use them again in just a moment.
    
    . Otherwise, set both loMaxItem and hiMaxItem to 1-under the min-item of the keypointer in the next slot.
    
    . Insert that loMaxItem and hiMaxItem pair into the rootID → {loMaxItem, hiMaxItem} map we created above. If an entry already exists for this root (since a broken tree might have multiple paths from the root to our node), then set loMaxItem to the min of the existing entry and our value, and hiMaxItem to the max.
- If that rootID → {loMaxItem, hiMaxItem} map is still empty, then consider this node to be a (potential) root, and insert rootID=thisNode -> {loMaxItem=maxKey, hiMaxItem=maxKey} (where maxKey is the maximum value of the key datatype).
- Take that rootID → {loMaxItem, hiMaxItem} map and insert it into the index as the entry for this node.
The next index we build is the "item index". This is a "sorted map" (implemented as a red-black tree, supporting sub-range iteration) of key → {nodeID, slotNumber}; a map that for each key tells us where to find the item with that key.
- Loop over the node index, and for each node check if both (a) it has level==0 (is a leaf node containing items), and (b) its set of roots that would include it has any overlap with the tree's set of roots.
- Loop over each of those included leaf nodes, and loop over the items in each node. Insert the key → {nodeId, slot} into our sorted map. If there is already an entry for that key, decide which one wins by:
  - Use the one from the node with the owner-tree that is closer to this tree; node with owner=thisTree wins over a node with owner=thisTree.parent, which would win over a node with owner.thisTree.parent.parent. If that's a tie, then...
  - Use the one from the node with the higher generation. If that's a tie, then...
  - I don't know, I have the code panic:
```
// TODO: This is a panic because I'm not really sure what the
// best way to handle this is, and so if this happens I want the
// program to crash and force me to figure out how to handle it.
panic(fmt.Errorf("dup nodes in tree=%v: old=%v=%v ; new=%v=%v",
    tree.ID,
    oldNode, tree.forrest.graph.Nodes[oldNode],
    newNode, tree.forrest.graph.Nodes[newNode]))
```
Note that this algorithm means that for a given node we may use a few items from that node, while having other items from that same node be overridden by another node.
The final index we build is the "error index". This is an index of what errors correspond to which range of keys, so that we can report them, and give an idea of "there may be entries missing from this directory" and similar.

For each error, we'll track the min-key and max-key of the range it applies to, the node it came from, and what the error string is. We'll store these into an interval tree keyed on that min-key/max-key range.
- Create an empty set nodesToProcess. Now populate it:
  - Once again, we'll loop over the node index, but this time we'll only check that there's overlap between the set of roots that would include the node and the tree's set of roots. The nodes that are included in this tree, insert both that node itself and all node IDs that it has keypointers pointing to into the nodesToProcess set.
  - Also insert all of the tree's roots into nodesToProcess; this is in case the superblock/root-item points to an invalid node that we couldn't read.
- Now loop over nodesToProcess. For each node, create an empty list of errors. Use the keypointers pointing to and the min loMaxItem from the node index to construct a set of expectations for the node; this should be reasonably straight-forward, given:
  - If different keypointers have disagreeing levels, insert an error in to the list, and don't bother with checking the node's level.
  - If different keypointers have disagreeing generations, insert an error in to the list, and don't bother with checking the node's generation.
  - If different keypointers have different min-item expectations, use the max of them.
  Then:
  - If the node is a "bad node" in the graph, insert the error message associated with it. Otherwise, check those expectations against the node in the graph.
  If the list of error messages is non-empty, then insert their concatenation into the interval tree, with the range set to the min of the min-item expectations from the keypointers through the max of the hiMaxItems from the node index. If the min min-item expectation turns out to be higher than the max hiMaxItem, then set the range to the zero-key through the max-key.

From there, it should be trivial to implement the usual B+ tree operations using those indexes; exact-lookup using the item index, and range-lookups and walks using the item index together with the error index. Efficiently searching the CSUM_TREE requires knowing item sizes, so that's why we recorded the item sizes into the graph.

4.3.3. The `rebuild-trees` algorithm

The btrfs inspect rebuild-trees algorithm finds nodes to attach as extra roots to trees. I think that conceptually it's the the simplest of the 3 algorithms, but turned out to be the hardest to get right. So... maybe more than the others reference the source code too (./cmd/btrfs-rec/inspect/rebuildtrees/) because I might forget some small but important detail.

The core idea here is that we're just going to walk each tree, inspecting each item in the tree, and checking for any items that are implied by other items (e.g.: a dir entry item implies the existence of inode item for the inode that it points at). If an implied item is not in the tree, but is in some other node, then we look at which potential roots we could add to the tree that would add that other node. Then, after we've processed all of the items in the filesystem, we go add those various roots to the various trees, keeping track of which items are added or updated. If any of those added/updated items have a version with a newer generation on a different node, see what roots we could add to get that newer version. Then add those roots, keeping track of items that are added/updated. Once we reach steady-state with the newest version of each item has been added, loop back and inspect all added/updated items for implied items, keeping track of roots we could add. Repeat until a steady-state is reached.

There are lots of little details in that process, some of which are for correctness, and some of which are for "it should run in hours instead of weeks."

4.3.3.1. initialization

First up, we're going to build and in-memory graph, same as above. But this time, while we're reading the nodes to do that, we're also going to watch for some specific items and record a few things about them.

(see: ./cmd/btrfs-rec/inspect/rebuildtrees/scan.go)

For each {nodeID, slotNumber} pair that matches one of these item types, we're going to record:

flags:
- INODE_ITEMs: whether it has the INODE_NODATASUM flag set
names:
- DIR_INDEX items: the file's name
sizes:
- EXTENT_CSUM items: the number of bytes that this is a sum for (i.e. the item size over the checksum size, times the block size)
- EXTENT_DATA items: the number of bytes in this extent (i.e. either the item size minus offsetof(btrfs_file_extent_item.disk_bytenr) if FILE_EXTENT_INLINE, or else the item's num_bytes).
data backrefs:
- EXTENT_ITEMs and METADATA_ITEMs: a list of the same length as the number of refs embedded in the item; for embeded ExtentDataRefs, the list entry is the subvolume tree ID that the ExtentDataRef points at, otherwise it is zero.
- EXTENT_DATA_REF items: a list of length 1, with the sole member being the subvolume tree ID that the ExtentDataRef points at.

4.3.3.2. the main loop

(see: ./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go)

Start with that scan data (graph + info about items), and also a rebuilt forrest from the above algorithm, but with:

the flag set so that it refuses to look up a tree if it can't look up all of that tree's ancestors
an additional "potential-item index" that is similar to the item index. It is generated the same way and can cache/evict the same way; the difference is that we invert the check for if the set of roots for a node has overlap with the tree's set of roots; we're looking for potential nodes that we could add to this tree.
some callbacks; we'll get to what we do in these callbacks in a bit, but for now, what the callbacks are:
- a callback that is called for each added/updated item when we add a root.
- a callback that is called whenever we add a root
- a callback that intercepts looking up a root item
- a callback that intercepts resolving an UUID to an object ID.

(The callbacks are in ./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go)

We have 5 unordered queues ("work lists"?); these are sets that when it's time to drain them we'll sort the members and process them in that order.

the tree queue: a list of tree IDs that we need to crawl
the retry-item queue: for each tree ID, a set of items that we should re-process if we add a root to that tree
the added-item queue: a set of key/tree pairs identifying items that have been added by adding a root to a tree
the settled-item-queue: a set of key/tree pairs that have have not just been added by adding a root, but we've also verified that they are the newest-generation item with that key that we could add to the tree.
the augment queue: for each item that we want to add to a tree, the list of roots that we could add to get that item.

The roots all start out empty, except for the tree queue, which we seed with the ROOT_TREE, the CHUNK_TREE, and the BLOCK_GROUP_TREE (It is a "TODO" task that it should probably also be seeded with the TREE_LOG, but as I will say below in the "future work" section, I don't actually understand the TREE_LOG, so I couldn't implement it).

Now we're going to loop until the tree queue, added-item queue, settled-item queue, and augment queue are all empty (all queues except for the retry-item queue). Each loop "pass" has 3 substeps:

Crawl the trees (drain the tree queue, fill the added-item queue).
Either:
1. if the added-item queue is non-empty: "settle" those items (drain the added-item queue, fill the augment queue and the settled-item queue).
2. otherwise: process items (drain the settled-item queue, fill the augment queue and the tree queue)
Apply augments (drain the augment queue and maybe the retry-item queue, fill the added-item queue).

OK, let's look at those 3 substeps in more detail:

Crawl the trees; drain the tree queue, fill the added-item queue.

We just look up the tree in the rebuilt forrest, which will (per the above --rebuild algorithm) will either fail to look up the tree, or succeed, and add to that tree the root node from the superblock/root-item. Because we set an item-added callback, when adding that root it will loop over the nodes added by that root, and call our callback for each item in one of the added nodes. Our callback inserts each item into the added-item queue. The forrest also calls our root-added callback, but because of the way this algorithm works, that turns out to be a no-op at this step.

I mentioned that we added callbacks to intercept the forrest's looking up of root items and resolving UUIDs; we override the forrest's "lookup root item" routine and "resolve UUID" routine to instead of doing normal lookups on the ROOT_TREE and UUID_TREE, use the above WantXXX routines that we'll define below in the "graph callbacks" section.

It shouldn't matter what order this queue is processed in, but I sort tree IDs numerically.

The crawling is fairly fast because it's just in-memory, the only accesses to disk are looking up root items and resolving UUIDs.
Either:
1. Settle items from the added-item queue to the settled-item queue (and fill the augment queue).
  
  For each item in the queue, we look in the tree's item index to get the {node, slot} pair for it, then we do the same in the tree's potential-item index. If the potential-item index contains an entry for the item's key, then we check if the potential-item's node should "win" over the queue item's node, deciding the "winner" using the same routine as when building the item index. If the potential-item's node wins, then we add the potential node's set of roots to the augment queue. If the queue-item's node wins, then we add the item to the settled-item queue (except, as an optimization, if the item is of a type that cannot possibly imply the existence of another item, then we just drop it and don't add it to the settled-item queue).
  
  It shouldn't matter what order this queue is processed in, but I sort it numerically by treeID and then by item key.
  
  This step is fairly fast because it's entirely in-memory, making no accesses to disk.
2. Process items from the settled-item queue (drain the settled-item queue, fill the augment queue and the tree queue).
  
  This step accesses disk, and so the order we process the queue in turns out to be pretty important in order to keep our disk access patterns cache-friendly. For the most part, we just sort each queue item by tree, then by key. But, we have special handling for EXTENT_ITEMs, METADATA_ITEMs, and EXTENT_DATA_REF items: We break EXTENT_ITEMs and METADATA_ITEMs in to "sub-items", treating each ref embedded in them as a separate item. For those embedded items that are EXTENT_DATA_REFs, and for stand-alone EXTENT_DATA_REF items, we sort them not with the EXTENT_TREE items, but with the items of the tree that the extent data ref points at. Recall that during the intitial scan step, we took note of which tree every extent data ref points at, so we can perform this sort without accessing disk yet. This splitting does mean that we may visit/read an EXTENT_ITEM or METADATA_ITEM multiple times as we process the queue, but to do otherwise is to solve MinLA, which is NP-hard and also an optimal MinLA solution I still think would perform worse than this; there is a reasonably lengthy discussion of this in a comment in ./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:sortSettledItemQueue().
  
  Now we loop over that sorted queue. In the code, this loop is deceptively simple. Read the item, then pass it to a function that tells us what other items are implied by it. That function is large, but simple; it's just a giant table. The trick is how it tells us about implied items; we give it set of callbacks that it calls to tell us these things; the real complexity is in the callbacks. These "graph callbacks" will be discussed in detail below, but as an illustrative example: It may call .WantOff() with a tree ID, object ID, item type, and offset to specify a precise item that it believes should exist.
  
  If we encounter a ROOT_ITEM, add the tree described by that item to the tree queue.
(Both the "can this item even imply the existence of another item" check and the "what items are implied by this item" routine are in ./lib/btrfscheck/graph.go)
Apply augments; drain the augment queue (and maybe the retry-item queue), fill the added-item queuee.

It is at this point that I call out that the augment queue isn't implemented as a simple map/set like the others, the treeAugmentQueue struct has special handling for sets of different sizes; optimizing the space for empty and len()==1 sized sets, and falling back to normal the usual implementation for larger sets; this is important because those small sets are the overwhelming majority, and otherwise there's no way the program would be able to run on my 32GB RAM laptop. Now that I think about it, I bet it would even be worth it to add optimized storage for len()==2 sized sets.

The reason is that each "want" from above is tracked in the queue separately; if we were OK merging them, then this optimized storage wouldn't be nescessary. But we keep them separate, so that:
- For all "wants", including ones with empty sets, graph callbacks can check if a want has already been processed; avoiding re-doing any work (see the description of the graph callbacks below).
- For "wants" with non-empty sets, we can see how many different "wants" could be satisfied with a given root, in order to decide which root to choose.
Anyway, we loop over the trees in the augment queue. For each tree we look at that tree's augment queue and look at all the choices of root nodes to add (below), and decide on a list to add. The we add each of those roots to the tree; the adding of each root triggers several calls to our item-added callback (filling the added-item queue), and our root-added callback. The root-added callback moves any items from the retry-item queue for this tree to the added-item queue.

How do we decide between choices of root nodes to add? ./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:resolveTreeAugments() has a good comment explaining the criteria we'd like to optimize for, and then code that does an OK-ish job of actually optimizing for that:
- It loops over the augment queue for that tree, building a list of possible roots, for each possible root making note of 3 things:
  1. how many "wants" that root satisfies,
  2. how far from treee the root's owner is (owner=tree is a distance of 0, owner=tree.parent is a distance of 1, owner=tree.parent.parent is a distance of 2, and so on), and
  3. what the generation of that root is.
- We sort that list first by highest-count-first, then by lowest-distance-first, then by highest-generation-first.
- We create a "return" set and an "illegal" set. We loop over the sorted list; for each possible root if it is in the illegal set, we skip it, otherwise we insert it into the return set and for each "want" that includes this root we all all roots that satisfy that want to the illegal list.

It is important that the rebuilt forrest have the flag set so that it refuses to look up a tree if it can't look up all of that tree's ancestors; otherwise the potential-items index would be garbage as we wouldn't have a good idea of which nodes are OK to consider; but this does have the downside that it won't even attempt to improve a tree with a missing parent. Perhaps the algorithm should flip the flag once the loop terminates, and then re-seed the tree queue with each ROOT_ITEM from the ROOT_TREE?

4.3.3.3. graph callbacks

(see: ./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go)

The graph callbacks are what tie the above together.

For each of these callbacks, whenever I say that it looks up something in a tree's item index or potential-item index, that implies looking the tree up from the forrest; if the forrest cannot look up that tree, then the callback returns early, after either:

if we are in substep 1 and are processing a tree: we add the tree that is being processed to the tree queue. (TODO: Wait, this assumes that an augment will be applied to the ROOT_TREE before the next pass... if that isn't the case, this will result in the loop never terminating... I guess I need to add a separate retry-tree queue?)
if we are in substep 2 and are processing an item: we add the item that is being processed to the retry-item queue for the tree that cannot be looked up

The 6 methods in the brfscheck.GraphCallbacks interface are:

FSErr(): There's an error with the filesystem; this callback just spits it out on stderr. I say such a trivial matter because, again, for a recovery tool I think it's worth putting care in to how you handle errors and where you expect them: We expect them here, so we have to check for them to avoid reading invalid data or whatever, but we don't actually need to do anything other than watch our step.
Want(): We want an item in a given tree with a given object ID and item type, but we don't care about what the item's offset is.

The callback works by searching the item index to see if it can find such an item; if so, it has nothing else to do and returns. Otherwise, it searches the potential-item index; for each matching item it finds it looks in the node index for the node containing that item, and adds the roots that would add that node, and adds those roots to a set. Once it has finished searching the potential-item index, it adds that set to the augment queue (even if that set is still empty).
WantOff(): The same, but we want a specific offset.
WantDirIndex(): We want a DIR_INDEX item for a given inode and filename, but we don't know what the offset of that item is.

First we scan over the item index, looking at all DIR_INDEX items for that inode number. For each item, we can check the scan data to see what the filename in that DIR_INDEX is, so we can see if the item satisfies this want without accessing the disk. If there's a match, then there is nothing else to do, so we return. Otherwise, we do that same search over the potential-item index; if we find any matches, then we build the set of roots to add to the augment queue the same as in Want.
WantFileExt(): We want 1 or more DATA_EXTENT items in the given tree for the given inode, and we want them to cover from 0 to a given size bytes of that file.

First we walk that range in the item index, to build a list of the gaps that we need to fill ("Step 1" in rebuild_wantcb.go:_wantRange()). This walk (rebuild_wantcb.go:_walkRange()) requires knowing the size of each file extent; so doing this quickly without hitting disk is why we recorded the size of each file extent in our initialization step.

Then ("Step 2" in _wantRange()) we iterate over each of the gaps, and for each gap do a very similar walk (again, by calling _walkRange(), but this time over the potential-item index. For each file extent we find that has is entirely within the gap, we "want" that extent, and move the beginning of of the gap forward to the end of that extent. This algorithm is dumb and greedy, potentially making sub-optimal selections; and so could probably stand to be improved; but in my real-world use, it seems to be "good enough".
WantCSum(): We want 1 or more EXTENT_CSUM items to cover the half-open interval [lo_logical_addr, hi_logical_addr). Well, maybe. It also takes a subvolume ID and an inode number; and looks up in the scan data whether that inode has the INODE_NODATASUM flag set; if it does have the flag set, then it returns early without looking for any EXTENT_CSUM items. If it doesn't return early, then it performs the same want-range routine as WantFileExt, but with the appropriate tree, object ID, and item types for csums as opposed to data extents.

For each of these callbacks, we generate a "wantKey", a tuple representing the function and its arguments; we check the augment-queue to see if we've already enqueued a set of roots for that want, and if so, that callback can return early without checking the potential-item index.

5. Future work

It's in a reasonably useful place, I think; and so now I'm going to take a break from it for a while. But there's still lots of work to do:

RAID almost certainly doesn't work.
Encryption is not implemented.
It doesn't understand (ignores) the TREE_LOG (because I don't understand the TREE_LOG).
btrfs-rec inspect mount should add "lost+found" directories for inodes that are included in the subvolume's tree but aren't reachable from the tree's root inode
I still need to implement btrfs-rec repair SUBCMD subcommands to write rebuilt-information from btrfs-rec inspect back to the filesystem.
I need to figure out the error handling/reporting story for mount.
It needs a lot more tests
- I'd like to get the existing btrfs-progs fsck tests to run on it.
In the process of writing this email, I realized that I probably need to add a retry-tree queue; see the "graph callbacks" section in the description of the rebuild-trees algorithm above.
Shere are a number of "TODO" comments or panics in the code:
- Some of them definitely need done.
- Some of them are panic("TODO") on the basis that if it's seeing something on the filesystem that it doesn't recognize, it's probably that I didn't get to implementing that thing/situation, but it's possible that the thing is just corrupt. This should only be for situations that the node passed the checksum test, so it being corrupt would have to be caused by a bug in btrfs rather than a failing drive or other corruption; I wasn't too worried about btrfs bugs.
btrfs-rec inspect rebuild-trees is slow, and can probably be made a lot faster.

Just to give you an idea of the speeds, the run-times for the various steps on my ThinkPad E15 for a 256GB disk image are as follows:
```
 btrfs-rec inspect rebuild-mappings scan       :     7m 31s
 btrfs-rec inspect rebuild-mappings list-nodes :        47s
 btrfs-rec inspect rebuild-mappings process    :     8m 22s
 btrfs-rec inspect rebuild-trees               : 1h  4m 55s
 btrfs-rec inspect ls-files                    :    29m 55s
 btrfs-rec inspect ls-trees                    :     8m 40s
```
For the most part, it's all single-threaded (with the main exception that in several places I/O has been moved to a separate thread from the main CPU-heavy thread), but a lot of the algorithms could be parallelized.
There are a lot of "tunable" values that I haven't really spent time tuning. These are all annotated with textui.Tunable(). I sort-of intended for them to be adjustable on the CLI.
Perhaps the btrfs inspect rebuild-trees algorithm could be adjusted to also try to rebuild trees with missing parents; see the above discussion of the algorithm.

6. Problems for merging this code into btrfs-progs

It's written in Go, not C.
It's effectively GPLv3+ (not GPLv2-only or GPLv2+) because of use of some code under the Apache 2.0 license (2 files in the codebase itself that are based off of Apache-licensed code, and use of unmodified 3rd-party libraries).
It uses ARC (Adaptive Replacement Cache), which is patented by IBM, and the patent doesn't expire for another 7 months. An important property of ARC over LRU is that it is scan-resistant; the above algorithms do a lot of scanning. On that note, now that RedHat is owned by IBM: who in the company do we need to get to talk to eachother so that we can get ARC into the Linux kernel before then?

-- 
 Happy hacking,
 ~ Luke Shumaker

POSIX pricing and availability; or: Do you really need the PDF?

2018-02-09T00:00:00+00:00

POSIX pricing and availability; or: Do you really need the PDF?

The Open Group and IEEE are weird about POSIX pricing. They’re protective of the PDF, making you pay hundreds of dollars for the PDF; but will happily post an HTML version for free both online, and (with free account creation) download as a a .zip.

They also offer a special license to the “Linux man-pages” project, allowing them to distribute the man page portions of POSIX (most of it is written as a series of man pages) for free; so on a GNU/Linux box, you probably have most of POSIX already downloaded in manual sections 0p, 1p, and 3p.

Anyway, the only thing you aren’t getting with the free HTML version is a line number next to every line of text. It’s generated from the same troff sources. So, in an article or in a discussion, I’m not cheating you out of specification details by citing the webpage.

If you’re concerned that you’re looking at the correct version of the webpage or man pages, the current version (as of February 2018) of POSIX is “POSIX-2008, 2016 edition.”

GNU/Linux Keyboard Maps: xmodmap

2018-02-09T00:00:00+00:00

GNU/Linux Keyboard Maps: xmodmap

The modmap subsystem is part of the core X11 protocol. However, it has been replaced by the X Keyboard (XKB) Extension to the protocol, which defines a facade that emulates the legacy modmap subsystem so that old programs still work—including those that manipulate the modmap directly!

For people who like to Keep It Stupid Simple, the XKB extension looks horribly complicated and gross—even ignoring protocol details, the configuration syntax is a monstrosity! There’s no way to say something like “I’d like to remap Caps-Lock to be Control”, you have to copy and edit the entire keyboard definition, which includes mucking with vector graphics of the physical keyboard layout! So it’s very tempting to pretend that XKB doesn’t exist, and it’s still using modmap.

However, this is a leaky abstraction; for instance: when running the xmodmap command to manipulate the modmap, if you have multiple keyboards plugged in, the result can depend on which keyboard you used to press “enter” after typing the command!

Despite only existing as a compatibility shim today, I think it is important to understand the modmap subsystem to understand modern XKB.

Conceptual overview

There are 3 fundamental tasks that the modmap subsystem performs:

keyboard: map keycode -> keysym (client-side)
keyboard: map keycode -> modifier bitmask (server-side)
pointer: map physical button -> logical button (server-side)

You’re thinking: “Great, so the X server does these things for us!” Nope! Not entirely, anyway. It does the keycode->modifier lookup, and the mouse-button lookup, but the keycode->keysym lookup must be done client-side by querying the mapping stored on the server. Generally, this is done automatically inside of libX11/libxcb, and the actual client application code doesn’t need to worry about it.

So, what’s the difference between a keycode and a keysym, and how’s the modifier bitmask work?

keycode: A numeric ID for a hardware button; this is as close the the hardware as X11 modmaps let us get. These are conceptually identical to Linux kernel keycodes, but the numbers don’t match up. Xorg keycodes are typically linux_keycode+8.
keysym: A 29-bit integer code that is meaningful to applications. A mapping of these to symbolic names is defined in <X11/keysymdef.h> and augmented by /usr/share/X11/XKeysymDB. See: XStringToKeysym() and XKeysymToString(). We will generally use the symbolic name in the modmap file. The symbolic names are case-sensitive.

Modifier state: An 8-bit bitmask of modifier keys (names are case-insensitive):

1 << 0 : shift
1 << 1 : lock
1 << 2 : control
1 << 3 : mod1
1 << 4 : mod2
1 << 5 : mod3
1 << 6 : mod4
1 << 7 : mod5

With that knowledge, and the libX11/libxcb API docs, you can probably figure out how to interact with the modmap subsystem from C, but who does that? Everyone just uses the xmodmap(1) command.

The X11 protocol

As I said, the modifier and button lookup is handled server-side; each of the input events ({Key,Button}{Press,Release}, and MotionNotify) and pointer window events ({Enter,Leave}Notify) include a bitmask of active keyboard modifiers and pointer buttons. Each are given an 8-bit bitmask—hence 8 key modifiers. For some reason, only up to Button5 is included in the bitmask; the upper 3 bits are always zero; but the Button{Press,Release} events will happily deliver events for up to Button255!

The X11 protocol has 6 request types for dealing with these 3 mappings; an accessor and a mutator pair for each. Since the 2 of the mappings are done server-side, of these, most clients will only use GetKeyboardMapping. Anyway, let’s look at those 6 requests, grouped by the mappings that they work with (pardon the Java-like pseudo-code syntax for indicating logical argument and return types):

keyboard: map keycode -> keysym
- GetKeyboardMapping :: List<keycode> -> Map<keycode,List<keysym>>
- ChangeKeyboardMapping :: Map<keycode,List<keysym>> -> ()
GetKeyboardMapping returns the keycode->keysym mappings for the requested keycodes; this way clients can choose to look up only the keycodes that they need to handle (the ones that got sent to them). Each keycode gets a list of keysyms; which keysym they should use from that list depends on which modifiers are pressed. ChangeKeyboardMapping changes the mapping for the given keycodes; not all keycodes must be given, any keycodes that aren’t included in the request aren’t changed.
keyboard: map keycode -> modifier bitmask
- GetModifierMapping :: () -> Map<modifier,List<keycode>>
- SetModifierMapping :: Map<modifier,List<keycode>> -> ()
The modifiers mapping is a lot smaller than the keysym mapping; you must operate on the entire mapping at once. For each modifier bit, there’s a list of keycodes that will cause that modifier bit to be flipped in the events that are delivered while it is pressed.
pointer: map physical button -> logical button
- GetPointerMapping () -> List<logicalButton> (indexed by physicalButton-1)
- SetPointerMapping List<logicalButton> -> () (indexed by physicalButton-1)
Like the modifier mapping, the button mapping is expected to be small, most mice only have 5-7 buttons (left, middle, right, scroll up, scroll down, scroll left, scroll right—that’s right, X11 handles scroll events as button presses), though some fancy gaming mice have more than that, but not much more.

I mentioned earlier that the keycode->keysym mapping isn’t actually done by the X server, and is done in the client; whenever a client receives a key event or pointer button event, it must do a Get*Mapping request to see what that translates to. Of course, doing a that for every keystroke would be crazy; but at the same time, the each client is expected to know about changes to the mappings that happen at run-time. So, each of the “set”/“change” commands generate a MappingNotify event that is sent to all clients, so they know when they must dump their cache of mappings.

For completeness, if you are looking at this as background for understanding XKB, I should also mention:

The `xmodmap` command

The xmodmap command reads a configuration file and modifies the maps in the X server to match. The xmodmap config file has its own little quirky syntax. For one, the comment character is ! (and comments may only start at the beginning of the line, but that’s fairly common).

There are 8 commands that xmodmap recognizes. Let’s look at those, grouped by the 3 tasks that the modmap subsystem performs:

keyboard: map keycode -> keysym
- keycode KEYCODE = PLAIN [SHIFT [MODE_SWITCH [MODE_SWITCH+SHIFT ]]]
  
  Actually takes a list of up to 8 keysyms, but only the first 4 have standard uses.
- keysym OLD_KEYSYM = NEW_KEYSYMS...
  
  Takes the keycodes mapped to OLD_KEYSYM and maps them to NEW_KEYSYM.
- keysym any = KEYSYMS...
  
  Finds an otherwise unused keycode, and has it map to the specified keysyms.
keyboard: map keycode -> modifier bitmask
- clear MODIFIER
- add MODIFIERNAME = KEYSYMS...
- remove MODIFIERNAME = KEYSYMS...
Wait, the modmap subsystem maps keycodes to modifiers, but the commands take keysyms? Yup! When executing one of these commands, it first looks up those keysyms in the keyboard map to translate them in to a set of keycodes, then associates those keycodes with that modifier. But how does it look up keysym->keycode; the protocol only supports querying keycode->keysym? It loops over every keycode finding all the matches.
pointer: map physical button -> logical button
- pointer = default
  
  This is equivalent to pointer = 1 2 3 4 5 6... where the list is as long as the number of buttons that there are.
- pointer = NUMBERS...
  
  pointer = A B C D... sets the physical button 1 to logical button A, physical button 2 to logical button B, and so on. Setting a physical button to logical button 0 disables that button.

Appendix:

I use this snippet in my Emacs configuration to make editing xmodmap files nicer:

;; http://www.emacswiki.org/emacs/XModMapMode
(when (not (fboundp 'xmodmap-mode))
  (define-generic-mode 'xmodmap-mode
    '(?!)
    '("add" "clear" "keycode" "keysym" "pointer" "remove")
    nil
    '("[xX]modmap\\(rc\\)?\\'")
    nil
    "Simple mode for xmodmap files."))

The interesting architecture of crt.sh

2018-02-09T00:00:00+00:00

The interesting architecture of crt.sh

A while back I wrote myself a little dashboard for monitoring TLS certificates for my domains. Right now it works by talking to https://crt.sh/. Sometimes this works great, but sometimes crt.sh is really slow. Plus, it’s another thing that could be compromised.

So, I started looking at how crt.sh works. It’s kinda cool.

There are only 3 separate processes:

Cron
- ct_monitor is program that uses libcurl to get CT log changes and libpq to put them into the database.
PostgreSQL
- certwatch_db is the core web application, written in PL/pgSQL. It even includes the HTML templating and query parameter handling. Of course, there are a couple of things not entirely done in pgSQL…
- libx509pq adds a set of x509_* functions callable from pgSQL for parsing X509 certificates.
- libcablintpq adds the cablint_embedded(bytea) function to pgSQL.
- libx509lintpq adds the x509lint_embedded(bytea,integer) function to pgSQL.
Apache HTTPD
- mod_certwatch is a pretty thin wrapper that turns every HTTP request into an SQL statement sent to PostgreSQL, via…
- mod_pgconn, which manages PostgreSQL connections.

The interface exposes HTML, ATOM, and JSON. All from code written in SQL.

And then I guess it’s behind an nginx-based load-balancer or somesuch (based on the 504 Gateway Timout messages it’s given me). But that’s not interesting.

The actual website is run from a read-only slave of the master DB that the ct_monitor cron-job updates; which makes several security considerations go away, and makes horizontal scaling easy.

Anyway, I thought it was neat that so much of it runs inside the database; you don’t see that terribly often. I also thought the little shims to make that possible were neat. I didn’t get deep enough in to it to end up running my own instance or clone, but I thought my notes on it were worth sharing.

Notes on subtleties of HTTP implementation

2016-09-30T00:00:00+00:00

Notes on subtleties of HTTP implementation

I may add to this as time goes on, but I’ve written up some notes on subtleties HTTP/1.1 message syntax as specified in RFC 2730.

Why the absolute-form is used for proxy requests

RFC7230§5.3.2 says that a (non-CONNECT) request to an HTTP proxy should look like

GET http://authority/path HTTP/1.1

rather than the usual

GET /path HTTP/1.1
Host: authority

And doesn’t give a hint as to why the message syntax is different here.

A blog post by Parsia Hakimian claims that the reason is that it’s a legacy behavior inherited from HTTP/1.0, which had proxies, but not the Host header field. Which is mostly true. But we can also realize that the usual syntax does not allow specifying a URI scheme, which means that we cannot specify a transport. Sure, the only two HTTP transports we might expect to use today are TCP (scheme: http) and TLS (scheme: https), and TLS requires we use a CONNECT request to the proxy, meaning that the only option left is a TCP transport; but that is no reason to avoid building generality into the protocol.

On taking short-cuts based on early header field values

RFC7230§3.2.2 says:

The order in which header fields with differing field names are
received is not significant.  However, it is good practice to send
header fields that contain control data first, such as Host on
requests and Date on responses, so that implementations can decide
when not to handle a message as early as possible.

Which is great! We can make an optimization!

This is only a valid optimization for deciding to not handle a message. You cannot use it to decide to route to a backend early based on this. Part of the reason is that §5.4 tells us we must inspect the entire header field set to know if we need to respond with a 400 status code:

A server MUST respond with a 400 (Bad Request) status code to any
HTTP/1.1 request message that lacks a Host header field and to any
request message that contains more than one Host header field or a
Host header field with an invalid field-value.

However, if I decide not to handle a request based on the Host header field, the correct thing to do is to send a 404 status code. Which implies that I have parsed the remainder of the header field set to validate the message syntax. We need to parse the entire field-set to know if we need to send a 400 or a 404. Did this just kill the possibility of using the optimization?

Well, there are a number of “A server MUST respond with a XXX code if” rules that can all be triggered on the same request. So we get to choose which to use. And fortunately for optimizing implementations, §3.2.5 gave us:

A server that receives a            ...           set of fields,
larger than it wishes to process MUST respond with an appropriate 4xx
(Client Error) status code.

Since the header field set is longer than we want to process (since we want to short-cut processing), we are free to respond with whichever 4XX status code we like!

On normalizing target URIs

An implementer is tempted to normalize URIs all over the place, just for safety and sanitation. After all, RFC3986§6.1 says it’s safe!

Unfortunately, most URI normalization implementations will normalize an empty path to “/”. Which is not always safe; RFC7230§2.7.3, which defines this “equivalence”, actually says:

                                        When not being used in
absolute form as the request target of an OPTIONS request, an empty
path component is equivalent to an absolute path of "/", so the
normal form is to provide a path of "/" instead.

Which means we can’t use the usual normalization implementation if we are making an OPTIONS request!

Why is that? Well, if we turn to §5.3.4, we find the answer. One of the special cases for when the request target is not a URI, is that we may use “*” as the target for an OPTIONS request to request information about the origin server itself, rather than a resource on that server.

However, as discussed above, the target in a request to a proxy must be an absolute URI (and §5.3.2 says that the origin server must also understand this syntax). So, we must define a way to map “*” to an absolute URI.

Naively, one might be tempted to use “/*” as the path. But that would make it impossible to have a resource actually named “/*”. So, we must define a special case in the URI syntax that doesn’t obstruct a real path.

If we didn’t have this special case in the URI normalization rules, and we handled the “/” path as the same as empty in the OPTIONS handler of the last proxy server, then it would be impossible to request OPTIONS for the “/” resources, as it would get translated into “*” and treated as OPTIONS for the entire server.

My X11 setup with systemd

2016-02-28T00:00:00+00:00

My X11 setup with systemd

Somewhere along the way, I decided to use systemd user sessions to manage the various parts of my X11 environment would be a good idea. If that was a good idea or not… we’ll see.

I’ve sort-of been running this setup as my daily-driver for a bit over a year, continually tweaking it though.

My setup is substantially different than the one on ArchWiki, because the ArchWiki solution assumes that there is only ever one X server for a user; I like the ability to run Xorg on my real monitor, and also have Xvnc running headless, or start my desktop environment on a remote X server. Though, I would like to figure out how to use systemd socket activation for the X server, as the ArchWiki solution does.

This means that all of my graphical units take DISPLAY as an @ argument. To get this to all work out, this goes in each .service file, unless otherwise noted:

[Unit]
After=X11@%i.target
Requisite=X11@%i.target
[Service]
Environment=DISPLAY=%I

We’ll get to X11@.target later, what it says is “I should only be running if X11 is running”.

I eschew complex XDMs or startx wrapper scripts, opting for the more simple xinit, which I either run on login for some boxes (my media station), or type xinit when I want X11 on others (most everything else). Essentially, what xinit does is run ~/.xserverrc (or /etc/X11/xinit/xserverrc) to start the server, then once the server is started (which it takes a substantial amount of magic to detect) it runs run ~/.xinitrc (or /etc/X11/xinit/xinitrc) to start the clients. Once .xinitrc finishes running, it stops the X server and exits. Now, when I say “run”, I don’t mean execute, it passes each file to the system shell (/bin/sh) as input.

Xorg requires a TTY to run on; if we log in to a TTY with logind, it will give us the XDG_VTNR variable to tell us which one we have, so I pass this to X in my .xserverrc:

#!/hint/sh
if [ -z "$XDG_VTNR" ]; then
  exec /usr/bin/X -nolisten tcp "$@"
else
  exec /usr/bin/X -nolisten tcp "$@" vt$XDG_VTNR
fi

This was the default for a while in Arch, to support logind, but was later removed in part because startx (which calls xinit) started adding it as an argument as well, so vt$XDG_VTNR was being listed as an argument twice, which is an error. IMO, that was a problem in startx, and they shouldn’t have removed it from the default system xserverrc, but that’s just me. So I copy/pasted it into my user xserverrc.

That’s the boring part, though. Where the magic starts happening is in my .xinitrc:

#!/hint/sh

if [ -z "$XDG_RUNTIME_DIR" ]; then
    printf "XDG_RUNTIME_DIR isn't set\n" >&2
    exit 6
fi

_DISPLAY="$(systemd-escape -- "$DISPLAY")"
trap "rm -f $(printf '%q' "${XDG_RUNTIME_DIR}/x11-wm@${_DISPLAY}")" EXIT
mkfifo "${XDG_RUNTIME_DIR}/x11-wm@${_DISPLAY}"

cat < "${XDG_RUNTIME_DIR}/x11-wm@${_DISPLAY}" &
systemctl --user start "X11@${_DISPLAY}.target" &
wait
systemctl --user stop "X11@${_DISPLAY}.target"

There are two contracts/interfaces here: the X11@DISPLAY.target systemd target, and the ${XDG_RUNTIME_DIR}/x11-wm@DISPLAY named pipe. The systemd .target should be pretty self explanatory; the most important part is that it starts the window manager. The named pipe is just a hacky way of blocking until the window manager exits (“traditional” .xinitrc files end with the line exec your-window-manager, so this mimics that behavior). It works by assuming that the window manager will open the pipe at startup, and keep it open (without necessarily writing anything to it); when the window manager exits, the pipe will get closed, sending EOF to the waited-for cat, allowing it to exit, letting the script resume. The window manager (WMII) is made to have the pipe opened by executing it this way in its .service file:

ExecStart=/usr/bin/env bash -c 'exec 8>${XDG_RUNTIME_DIR}/x11-wm@%I; exec wmii'

which just opens the file on file descriptor 8, then launches the window manager normally. The only further logic required by the window manager with regard to the pipe is that in the window manager configuration, I should close that file descriptor after forking any process that isn’t “part of” the window manager:

runcmd() (
    ...
    exec 8>&- # xinit/systemd handshake
    ...
)

So, back to the X11@DISPLAY.target; I configure what it “does” with symlinks in the .requires and .wants directories:

.config/systemd/user/
- X11@.target
- X11@.target.requires/
  - wmii@.service -> ../wmii@.service
- X11@.target.wants/
  - xmodmap@.service -> ../xmodmap@.service
  - xresources-dpi@.service -> ../xresources-dpi@.service
  - xresources@.service -> ../xresources@.service

The .requires directory is how I configure which window manager it starts. This would allow me to configure different window managers on different displays, by creating a .requires directory with the DISPLAY included, e.g. X11@:2.requires.

The .wants directory is for general X display setup; it’s analogous to /etc/X11/xinit/xinitrc.d/. All of the files in it are simple Type=oneshot service files. The xmodmap and xresources files are pretty boring, they’re just systemd versions of the couple lines that just about every traditional .xinitrc contains, the biggest difference being that they look at ~/.config/X11/modmap and ~/.config/X11/resources instead of the traditional locations ~/.xmodmap and ~/.Xresources.

What’s possibly of note is xresources-dpi@.service. In X11, there are two sources of DPI information, the X display resolution, and the XRDB Xft.dpi setting. It isn’t defined which takes precedence (to my knowledge), and even if it were (is), application authors wouldn’t be arsed to actually do the right thing. For years, Firefox (well, Iceweasel) happily listened to the X display resolution, but recently it decided to only look at Xft.dpi, which objectively seems a little silly, since the X display resolution is always present, but Xft.dpi isn’t. Anyway, Mozilla’s change drove me to to create a script to make the Xft.dpi setting match the X display resolution. Disclaimer: I have no idea if it works if the X server has multiple displays (with possibly varying resolution).

#!/usr/bin/env bash
dpi=$(LC_ALL=C xdpyinfo|sed -rn 's/^\s*resolution:\s*(.*) dots per inch$/\1/p')
xrdb -merge <<<"Xft.dpi: ${dpi}"

Since we want XRDB to be set up before any other programs launch, we give both of the xresources units Before=X11@%i.target (instead of After= like everything else). Also, two programs writing to xrdb at the same time has the same problem as two programs writing to the same file; one might trash the other’s changes. So, I stuck Conflicts=xresources@:i.service into xresources-dpi.service.

And that’s the “core” of my X11 systemd setup. But, you generally want more things running than just the window manager, like a desktop notification daemon, a system panel, and an X composition manager (unless your window manager is bloated and has a composition manager built in). Since these things are probably window-manager specific, I’ve stuck them in a directory wmii@.service.wants:

.config/systemd/user/
- wmii@.service.wants/
  - dunst@.service -> ../dunst@.service # a notification daemon
  - lxpanel@.service -> ../lxpanel@.service # a system panel
  - rbar@97_acpi.service -> ../rbar@.service # wmii stuff
  - rbar@99_clock.service -> ../rbar@.service # wmii stuff
  - xcompmgr@.service -> ../xcompmgr@.service # an X composition manager

For the window manager .service, I could just say Type=simple and call it a day (and I did for a while). But, I like to have lxpanel show up on all of my WMII tags (desktops), so I have my WMII configuration stick this in the WMII /rules:

/panel/ tags=/.*/ floating=always

Unfortunately, for this to work, lxpanel must be started after that gets inserted into WMII’s rules. That wasn’t a problem pre-systemd, because lxpanel was started by my WMII configuration, so ordering was simple. For systemd to get this right, I must have a way of notifying systemd that WMII’s fully started, and it’s safe to start lxpanel. So, I stuck this in my WMII .service file:

# This assumes that you write READY=1 to $NOTIFY_SOCKET in wmiirc
Type=notify
NotifyAccess=all

and this in my WMII configuration:

systemd-notify --ready || true

Now, this setup means that NOTIFY_SOCKET is set for all the children of wmii; I’d rather not have it leak into the applications that I start from the window manager, so I also stuck unset NOTIFY_SOCKET after forking a process that isn’t part of the window manager:

runcmd() (
    ...
    unset NOTIFY_SOCKET # systemd
    ...
    exec 8>&- # xinit/systemd handshake
    ...
)

Unfortunately, because of a couple of bugs and race conditions in systemd, systemd-notify isn’t reliable. If systemd can’t receive the READY=1 signal from my WMII configuration, there are two consequences:

lxpanel will never start, because it will always be waiting for wmii to be ready, which will never happen.
After a couple of minutes, systemd will consider wmii to be timed out, which is a failure, so then it will kill wmii, and exit my X11 session. That’s no good!

Using socat to send the message to systemd instead of systemd-notify “should” always work, because it tries to read from both ends of the bi-directional stream, and I can’t imagine that getting EOF from the UNIX-SENDTO end will ever be faster than the systemd manager from handling the datagram that got sent. Which is to say, “we work around the race condition by being slow and shitty.”

socat STDIO UNIX-SENDTO:"$NOTIFY_SOCKET" <<<READY=1 || true

But, I don’t like that. I’d rather write my WMII configuration to the world as I wish it existed, and have workarounds encapsulated elsewhere; “If you have to cut corners in your project, do it inside the implementation, and wrap a very good interface around it.”. So, I wrote a systemd-notify compatible function that ultimately calls socat:

##
# Just like systemd-notify(1), but slower, which is a shitty
# workaround for a race condition in systemd.
##
systemd-notify() {
    local args
    args="$(getopt -n systemd-notify -o h -l help,version,ready,pid::,status:,booted -- "$@")"
    ret=$?; [[ $ret == 0 ]] || return $ret
    eval set -- "$args"

    local arg_ready=false
    local arg_pid=0
    local arg_status=
    while [[ $# -gt 0 ]]; do
        case "$1" in
            -h|--help) command systemd-notify --help; return $?;;
            --version) command systemd-notify --version; return $?;;
            --ready) arg_ready=true; shift 1;;
            --pid) arg_pid=${2:-$$}; shift 2;;
            --status) arg_status=$2; shift 2;;
            --booted) command systemd-notify --booted; return $?;;
            --) shift 1; break;;
        esac
    done

    local our_env=()
    if $arg_ready; then
        our_env+=("READY=1")
    fi
    if [[ -n "$arg_status" ]]; then
        our_env+=("STATUS=$arg_status")
    fi
    if [[ "$arg_pid" -gt 0 ]]; then
        our_env+=("MAINPID=$arg_pid")
    fi
    our_env+=("$@")
    local n
    printf -v n '%s\n' "${our_env[@]}"
    socat STDIO UNIX-SENDTO:"$NOTIFY_SOCKET" <<<"$n"
}

So, one day when the systemd bugs have been fixed (and presumably the Linux kernel supports passing the cgroup of a process as part of its credentials), I can remove that from workarounds.sh, and not have to touch anything else in my WMII configuration (I do use systemd-notify in a couple of other, non-essential, places too; this wasn’t to avoid having to change just 1 line).

So, now that wmii@.service properly has Type=notify, I can just stick After=wmii@.service into my lxpanel@.service, right? Wrong! Well, I could, but my lxpanel service has nothing to do with WMII; why should I couple them? Instead, I create wm-running@.target that can be used as a synchronization point:

# wmii@.service
Before=wm-running@%i.target

# lxpanel@.service
After=X11@%i.target wm-running@%i.target
Requires=wm-running@%i.target

Finally, I have my desktop started and running. Now, I’d like for programs that aren’t part of the window manager to not dump their stdout and stderr into WMII’s part of the journal, like to have a record of which graphical programs crashed, and like to have a prettier cgroup/process graph. So, I use systemd-run to run external programs from the window manager:

runcmd() (
    ...
    unset NOTIFY_SOCKET # systemd
    ...
    exec 8>&- # xinit/systemd handshake
    exec systemd-run --user --scope -- sh -c "$*"
)

I run them as a scope instead of a service so that they inherit environment variables, and don’t have to mess with getting DISPLAY or XAUTHORITY into their units (as I don’t want to make them global variables in my systemd user session).

I’d like to get lxpanel to also use systemd-run when launching programs, but it’s a low priority because I don’t really actually use lxpanel to launch programs, I just have the menu there to make sure that I didn’t break the icons for programs that I package (I did that once back when I was Parabola’s packager for Iceweasel and IceCat).

And that’s how I use systemd with X11.

My favorite bug: segfaults in Java (redux)

2016-02-28T00:00:00+00:00

My favorite bug: segfaults in Java (redux)

Two years ago, I wrote about one of my favorite bugs that I’d squashed two years before that. About a year after that, someone posted it on Hacker News.

There was some fun discussion about it, but also some confusion. After finishing a season of mentoring team 4272, I’ve decided that it would be fun to re-visit the article, and dig up the old actual code, instead of pseudo-code, hopefully improving the clarity (and providing a light introduction for anyone wanting to get into modifying the current SmartDashbaord).

The context

In 2012, I was a high school senior, and lead programmer programmer on the FIRST Robotics Competition team 1024. For the unfamiliar, the relevant part of the setup is that there are 2 minute and 15 second matches in which you have a 120 pound robot that sometimes runs autonomously, and sometimes is controlled over WiFi from a person at a laptop running stock “driver station” software and modifiable “dashboard” software.

That year, we mostly used the dashboard software to allow the human driver and operator to monitor sensors on the robot, one of them being a video feed from a web-cam mounted on it. This was really easy because the new standard dashboard program had a click-and drag interface to add stock widgets; you just had to make sure the code on the robot was actually sending the data.

That’s great, until when debugging things, the dashboard would suddenly vanish. If it was run manually from a terminal (instead of letting the driver station software launch it), you would see a core dump indicating a segmentation fault.

This wasn’t just us either; I spoke with people on other teams, everyone who was streaming video had this issue. But, because it only happened every couple of minutes, and a match is only 2:15, it didn’t need to run very long, they just crossed their fingers and hoped it didn’t happen during a match.

The dashboard was written in Java, and the source was available (under a 3-clause BSD license) via read-only SVN at http://firstforge.wpi.edu/svn/repos/smart_dashboard/trunk (which is unfortunately no longer online, fortunately I’d posted some snapshots on the web). So I dove in, hunting for the bug.

The repository was divided into several NetBeans projects (not exhaustively listed):

client/smartdashboard: The main dashboard program, has a plugin architecture.
WPIJavaCV: A higher-level wrapper around JavaCV, itself a Java Native Interface (JNI) wrapper to talk to OpenCV (C and C++).
extensions/camera/WPICameraExtension: The standard camera feed plugin, processes the video through WPIJavaCV.

I figured that the bug must be somewhere in the C or C++ code that was being called by JavaCV, because that’s the language where segfaults happen. It was especially a pain to track down the pointers that were causing the issue, because it was hard with native debuggers to see through all of the JVM stuff to the OpenCV code, and the OpenCV stuff is opaque to Java debuggers.

Eventually the issue lead me back into the WPICameraExtension, then into WPIJavaCV—there was a native pointer being stored in a Java variable; Java code called the native routine to free() the structure, but then tried to feed it to another routine later. This lead to difficulty again—tracking objects with Java debuggers was hard because they don’t expect the program to suddenly segfault; it’s Java code, Java doesn’t segfault, it throws exceptions!

With the help of println() I was eventually able to see that some code was executing in an order that straight didn’t make sense.

The bug

The basic flow of WPIJavaCV is you have a WPICamera, and you call .getNewImage() on it, which gives you a WPIImage, which you could do all kinds of fancy OpenCV things on, but then ultimately call .getBufferedImage(), which gives you a java.awt.image.BufferedImage that you can pass to Swing to draw on the screen. You do this every for frame. Which is exactly what WPICameraExtension.java did, except that “all kinds of fancy OpenCV things” consisted only of:

public WPIImage processImage(WPIColorImage rawImage) {
    return rawImage;
}

The idea was that you would extend the class, overriding that one method, if you wanted to do anything fancy.

One of the neat things about WPIJavaCV was that every OpenCV object class extended had a finalize() method (via inheriting from the abstract class WPIDisposable) that freed the underlying C/C++ memory, so you didn’t have to worry about memory leaks like in plain JavaCV. To inherit from WPIDisposable, you had to write a disposed() method that actually freed the memory. This was better than writing finalize() directly, because it did some safety with NULL pointers and idempotency if you wanted to manually free something early.

Now, edu.wpi.first.WPIImage.disposed() called com.googlecode.javacv.cpp.opencv_core.IplImage.release(), which called (via JNI) IplImage:::release(), which called libc free():

@Override
protected void disposed() {
    image.release();
}

Elsewhere, the C buffer for the image was copied into a Java buffer via a similar chain kicked off by edu.wpi.first.WPIImage.getBufferedImage():

/**
 * Copies this {@link WPIImage} into a {@link BufferedImage}.
 * This method will always generate a new image.
 * @return a copy of the image
 */
public BufferedImage getBufferedImage() {
    validateDisposed();

    return image.getBufferedImage();
}

The println() output I saw that didn’t make sense was that someFrame.finalize() was running before someFrame.getBuffereImage() had returned!

You see, if it is waiting for the return value of a method m() of object a, and code in m() that is yet to be executed doesn’t access any other methods or properties of a, then it will go ahead and consider a eligible for garbage collection before m() has finished running.

Put another way, this is passed to a method just like any other argument. If a method is done accessing this, then it’s “safe” for the JVM to go ahead and garbage collect it.

That is normally a safe “optimization” to make… except for when a destructor method (finalize()) is defined for the object; the destructor can have side effects, and Java has no way to know whether it is safe for them to happen before m() has finished running.

I’m not entirely sure if this is a “bug” in the compiler or the language specification, but I do believe that it’s broken behavior.

Anyway, in this case it’s unsafe with WPI’s code.

My work-around

My work-around was to change this function in WPIImage:

public BufferedImage getBufferedImage() {
    validateDisposed();

    return image.getBufferedImage(); // `this` may get garbage collected before it returns!
}

In the above code, this is a WPIImage, and it may get garbage collected between the time that image.getBufferedImage() is dispatched, and the time that image.getBufferedImage() accesses native memory. When it is garbage collected, it calls image.release(), which free()s that native memory. That seems pretty unlikely to happen; that’s a very small gap of time. However, running 30 times a second, eventually bad luck with the garbage collector happens, and the program crashes.

The work-around was to insert a bogus call to this to keep this around until after we were also done with image:

to this:

public BufferedImage getBufferedImage() {
    validateDisposed();
    BufferedImage ret = image.getBufferedImage();
    getWidth(); // bogus call to keep `this` around
    return ret;
}

Yeah. After spending weeks wading through though thousands of lines of Java, C, and C++, a bogus call to a method I didn’t care about was the fix.

TheLoneWolfling on Hacker News noted that they’d be worried about the JVM optimizing out the call to getWidth(). I’m not, because WPIImage.getWidth() calls IplImage.width(), which is declared as native; the JVM must run it because it might have side effects. On the other hand, looking back, I think I just shrunk the window for things to go wrong: it may be possible for the garbage collection to trigger in the time between getWidth() being dispatched and width() running. Perhaps there was something in the C/C++ code that made it safe, I don’t recall, and don’t care quite enough to dig into OpenCV internals again. Or perhaps I’m mis-remembering the fix (which I don’t actually have a file of), and I called some other method that could get optimized out (though I do believe that it was either getWidth() or getHeight()).

WPI’s fix

Four years later, the SmartDashboard is still being used! But it no longer has this bug, and it’s not using my workaround. So, how did the WPILib developers fix it?

Well, the code now lives in git at collab.net, so I decided to take a look.

The stripped out WPIJavaCV from the main video feed widget, and now use a purely Java implementation of MPJPEG streaming.

However, the old video feed widget is still available as an extension (so that you can still do cool things with processImage), and it also no longer has this bug. Their fix was to put a mutex around all accesses to image, which should have been the obvious solution to me.

An Nginx configuration for MediaWiki

2015-05-19T00:00:00+00:00

An Nginx configuration for MediaWiki

There are several example Nginx configurations for MediaWiki floating around the web. Many of them don’t block the user from accessing things like /serialized/. Many of them also don’t correctly handle a wiki page named FAQ, since that is a name of a file in the MediaWiki root! In fact, the configuration used on the official Nginx Wiki has both of those issues!

This is because most of the configurations floating around basically try to pass all requests through, and blacklist certain requests, either denying them, or passing them through to index.php.

It’s my view that blacklisting is inferior to whitelisting in situations like this. So, I developed the following configuration that instead works by whitelisting certain paths.

root /path/to/your/mediawiki; # obviously, change this line

index index.php;
location /                     { try_files /var/empty @rewrite; }
location /images/              { try_files $uri $uri/ @rewrite; }
location /skins/               { try_files $uri $uri/ @rewrite; }
location /api.php              { try_files /var/empty @php; }
location /api.php5             { try_files /var/empty @php; }
location /img_auth.php         { try_files /var/empty @php; }
location /img_auth.php5        { try_files /var/empty @php; }
location /index.php            { try_files /var/empty @php; }
location /index.php5           { try_files /var/empty @php; }
location /load.php             { try_files /var/empty @php; }
location /load.php5            { try_files /var/empty @php; }
location /opensearch_desc.php  { try_files /var/empty @php; }
location /opensearch_desc.php5 { try_files /var/empty @php; }
location /profileinfo.php      { try_files /var/empty @php; }
location /thumb.php            { try_files /var/empty @php; }
location /thumb.php5           { try_files /var/empty @php; }
location /thumb_handler.php    { try_files /var/empty @php; }
location /thumb_handler.php5   { try_files /var/empty @php; }
location /wiki.phtml           { try_files /var/empty @php; }

location @rewrite {
    rewrite ^/(.*)$ /index.php?title=$1&$args;
}

location @php {
    # obviously, change this according to your PHP setup
    include fastcgi.conf;
    fastcgi_pass unix:/run/php-fpm/wiki.sock;
}

We are now using this configuration on ParabolaWiki, but with an alias for location = /favicon.ico to the correct file in the skin, and with FastCGI caching for PHP.

The only thing I don’t like about this is the try_files /var/emtpy bits—surely there is a better way to have it go to one of the @ location blocks, but I couldn’t figure it out.

I took some videos at LibrePlanet

2015-03-22T00:00:00+00:00

I took some videos at LibrePlanet

I’m at LibrePlanet, and have been loving the talks. For most of yesterday, there was a series of short “lightning” talks in room 144. I decided to hang out in that room for the later part of the day, because while most of the talks were live streamed and recorded, there were no cameras in room 144; so I couldn’t watch them later.

Way too late in the day, I remembered that I have the capability to record videos, so I cought the last two talks in 144.

I appologize for the changing orientation.

Here’s the video I took.

Building Bash 1.14.7 on a modern system

2015-03-18T00:00:00+00:00

Building Bash 1.14.7 on a modern system

In a previous revision of my Bash arrays post, I wrote:

Bash 1.x won’t compile with modern GCC, so I couldn’t verify how it behaves.

I recall spending a little time fighting with it, but apparently I didn’t try very hard: getting Bash 1.14.7 to build on a modern box is mostly just adjusting it to use stdarg instead of the no-longer-implemented varargs. There’s also a little fiddling with the pre-autoconf automatic configuration.

stdarg

Converting to stdarg is pretty simple: For each variadic function (functions that take a variable number of arguments), follow these steps:

Replace #include <varargs.h> with #include <stdarg.h>
Replace function_name (va_alist) va_dcl with function_name (char *format, ...).
Removing the declaration and assignment for format from the function body.
Replace va_start (args); with va_start (args, format); in the function bodies.
Replace function_name (); with function_name (char *, ...) in header files and/or at the top of C files.

There’s one function that uses the variable name control instead of format.

I’ve prepared a patch that does this.

Configuration

Instead of using autoconf-style tests to test for compiler and platform features, Bash 1 used the file machines.h that had #ifdefs and a huge database of of different operating systems for different platforms. It’s gross. And quite likely won’t handle your modern operating system.

I made these two small changes to machines.h to get it to work correctly on my box:

Replace #if defined (i386) with #if defined (i386) || defined (__x86_64__). The purpose of this is obvious.
Add #define USE_TERMCAP_EMULATION to the section for Linux [sic] on i386 (# if !defined (done386) && (defined (__linux__) || defined (linux))). What this does is tell it to link against libcurses to use curses termcap emulation, instead of linking against libtermcap (which doesn’t exist on modern GNU/Linux systems).

Again, I’ve prepared a patch that does this.

Building

With those adjustments, it should build, but with quite a few warnings. Making a couple of changes to CFLAGS should fix that:

make CFLAGS='-O -g -Werror -Wno-int-to-pointer-cast -Wno-pointer-to-int-cast -Wno-deprecated-declarations -include stdio.h -include stdlib.h -include string.h -Dexp2=bash_exp2'

That’s a doozy! Let’s break it down:

-O -g The default value for CFLAGS (defined in cpp-Makefile)
-Werror Treat warnings as errors; force us to deal with any issues.
-Wno-int-to-pointer-cast -Wno-pointer-to-int-cast Allow casting between integers and pointers. Unfortunately, the way this version of Bash was designed requires this.
-Wno-deprecated-declarations The getwd function in unistd.h is considered deprecated (use getcwd instead). However, if getcwd is available, Bash uses it’s own getwd wrapper around getcwd (implemented in general.c), and only uses the signature from unistd.h, not the actuall implementation from libc.
-include stdio.h -include stdlib.h -include string.h Several files are missing these header file includes. If not for -Werror, the default function signature fallbacks would work.
-Dexp2=bash_exp2 Avoid a conflict between the parser’s exp2 helper function and math.h’s base-2 exponential function.

Have fun, software archaeologists!

Customizing your login on Purdue CS computers (WIP, but updated)

2015-02-06T00:00:00+00:00

This article is currently a Work-In-Progress. Other than the one place where I say “I’m not sure”, the GDM section is complete. The network shares section is a mess, but has some good information.

Most CS students at Purdue spend a lot of time on the lab boxes, but don’t know a lot about them. This document tries to fix that.

The lab boxes all run Gentoo.

GDM, the Gnome Display Manager

The boxes run gdm (Gnome Display Manager) 2.20.11 for the login screen. This is an old version, and has a couple behaviors that are slightly different than new versions, but here are the important bits:

System configuration:

/usr/share/gdm/defaults.conf (lower precidence)
/etc/X11/gdm/custom.conf (higher precidence)

User configuration:

~/.dmrc (more recent versions use ~/.desktop, but Purdue boxes aren’t running more recent versions)

Purdue’s GDM configuration

Now, custom.conf sets

BaseXsession=/usr/local/share/xsessions/Xsession
SessionDesktopDir=/usr/local/share/xsessions/

This is important, because there are multiple locations that look like these files; I take it that they were used at sometime in the past. Don’t get tricked into thinking that it looks at /etc/X11/gdm/Xsession (which exists, and is where it would look by default).

If you look at the GDM login screen, it has a “Sessions” button that opens a prompt where you can select any of several sessions:

Last session
1. MATE (mate.desktop; Exec=mate-session)
2. CS Default Session (default.desktop; Exec=default)
3. Custom Session (custom.desktop; Exec=custom)
4. FVWM2 (fvwm2.desktop; Exec=fvwm2)
5. gnome.desktop (gnome.desktop; Exec=gnome-session)
6. KDE (kde.desktop, Exec=startkde)
Failsafe MATE (ShowGnomeFailsafeSession=true)
Failsafe Terminal (ShowXtermFailsafeSession=true)

The main 6 are configured by the .desktop files in SessionDesktopDir=/usr/local/share/xsessions; the last 2 are auto-generated. The reason ShowGnomeFailsafeSession correctly generates a Mate session instead of a Gnome session is because of the patch /p/portage/*/overlay/gnome-base/gdm/files/gdm-2.20.11-mate.patch.

I’m not sure why Gnome shows up as gnome.desktop instead of GNOME as specified by gnome.desktop:Name. I imagine it might be something related to the aforementioned patch, but I can’t find anything in the patch that looks like it would screw that up; at least not without a better understanding of GDM’s code.

Which of the main 6 is used by default (“Last Session”) is configured with ~/.dmrc:Session, which contains the basename of the associated .desktop file (that is, without any directory part or file extension).

Every one of the .desktop files sets Type=XSession, which means that instead of running the argument in Exec= directly, it passes it as arguments to the Xsession program (in the location configured by BaseXsession).

Xsession

So, now we get to read /usr/local/share/xsessions/Xsession.

Before it does anything else, it:

. /etc/profile.env
unset ROOTPATH
Try to set up logging to one of ~/.xsession-errors, $TMPDIR/xses-$USER, or /tmp/xses-$USER (it tries them in that order).
xsetroot -default
Fiddles with the maximum number of processes.

After that, it handles these 3 “special” arguments that were given to it by various .desktop Exec= lines:

failsafe: Runs a single xterm window. NB: This is NOT run by either of the failsafe options. It is likey a vestiage from a prior configuration.
startkde: Displays a message saying KDE is no longer available.
gnome-session: Displays a message saying GNOME has been replaced by MATE.

Assuming that none of those were triggered, it then does:

source ~/.xprofile
xrdb -merge ~/.Xresources
xmodmap ~/.xmodmaprc

Finally, it has a switch statement over the arguments given to it by the various .desktop Exec= lines:

custom: Executes ~/.xsession.
default: Executes ~/.Xrc.cs.
mate-session: It has this whole script to start DBus, run the mate-session command, then cleanup when it’s done.
* (fvwm2): Runs eval exec "$@", which results in it executing the fvwm2 command.

Network Shares

Your data is on various hosts. I believe most undergrads have their data on data.cs.purdue.edu (or just data). Others have theirs on antor or tux (that I know of).

Most of the boxes with tons of storage have many network cards; each with a different IP; a single host’s IPs are mostly the same, but with varying 3rd octets. For example, data is 128.10.X.13. If you need a particular value of X, but don’t want to remember the other octets; they are individually addressed with BASENAME-NUMBER.cs.purdue.edu. For example, data-25.cs.purdu.edu is 128.10.25.13.

They use AutoFS quite extensively. The maps are generated dynamically by /etc/autofs/*.map, which are all symlinks to /usr/libexec/amd2autofs. As far as I can tell, amd2autofs is custom to Purdue. Its source lives in /p/portage/*/overlay/net-fs/autofs/files/amd2autofs.c. The name appears to be a misnomer; seems to claim to dynamically translate from the configuration of Auto Mounter Daemon (AMD) to AutoFS, but it actually talks to NIS. It does so using the yp interface, which is in Glibc for compatibility, but is undocumented. For documentation for that interface, look at the one of the BSDs, or Mac OS X. From the comments in the file, it appears that it once did look at the AMD configuration, but has since been changed.

There are 3 mountpoints using AutoFS: /homes, /p, and /u. /homes creates symlinks on-demand from /homes/USERNAME to /u/BUCKET/USERNAME. /u mounts NFS shares to /u/SERVERNAME on-demand, and creates symlinks from /u/BUCKET to /u/SERVERNAME/BUCKET on-demand. /p mounts on-demand various NFS shares that are organized by topic; the Xinu/MIPS tools are in /p/xinu, the Portage tree is in /p/portage.

I’m not sure how scratch works; it seems to be heterogenous between different servers and families of lab boxes. Sometimes it’s in /u, sometimes it isn’t.

This 3rd-party documentation was very helpful to me: http://www.linux-consulting.com/Amd_AutoFS/ It’s where Gentoo points for the AutoFS homepage, as it doesn’t have a real homepage. Arch just points to FreshMeat. Debian points to kernel.org.

Lore

lore

Lore is a SunOS 5.10 box running on Sun-Fire V445 (sun4u) hardware. SunOS is NOT GNU/Linux, and sun4u is NOT x86.

Instead of /etc/fstab it is /etc/mnttab.

A memoization routine for GNU Make functions

2014-11-20T00:00:00+00:00

A memoization routine for GNU Make functions

I’m a big fan of GNU Make. I’m pretty knowledgeable about it, and was pretty active on the help-make mailing list for a while. Something that many experienced make-ers know of is John Graham-Cumming’s “GNU Make Standard Library”, or GMSL.

I don’t like to use it, as I’m capable of defining macros myself as I need them instead of pulling in a 3rd party dependency (and generally like to stay away from the kind of Makefile that would lean heavily on something like GMSL).

However, one really neat thing that GMSL offers is a way to memoize expensive functions (such as those that shell out). I was considering pulling in GMSL for one of my projects, almost just for the memoize function.

However, John’s memoize has a couple short-comings that made it unsuitable for my needs.

Only allows functions that take one argument.
Considers empty values to be unset; for my needs, an empty string is a valid value that should be cached.

So, I implemented my own, more flexible memoization routine for Make.

# This definition of `rest` is equivalent to that in GMSL
rest = $(wordlist 2,$(words $1),$1)

# How to use: Define 2 variables (the type you would pass to $(call):
# `_NAME_main` and `_NAME_hash`.  Now, `_NAME_main` is the function getting
# memoized, and _NAME_hash is a function that hashes the function arguments
# into a string suitable for a variable name.
#
# Then, define the final function like:
#
#     NAME = $(foreach func,NAME,$(memoized))

_main = $(_$(func)_main)
_hash = __memoized_$(_$(func)_hash)
memoized = $(if $($(_hash)),,$(eval $(_hash) := _ $(_main)))$(call rest,$($(_hash)))

However, I later removed it from the Makefile, as I re-implemented the bits that it memoized in a more efficient way, such that memoization was no longer needed, and the whole thing was faster.

Later, I realized that my memoized routine could have been improved by replacing func with $0, which would simplify how the final function is declared:

# This definition of `rest` is equivalent to that in GMSL
rest = $(wordlist 2,$(words $1),$1)

# How to use:
#
#     _NAME_main = your main function to be memoized
#     _NAME_hash = your hash function for parameters
#     NAME = $(memoized)
#
# The output of your hash function should be a string following
# the same rules that variable names follow.

_main = $(_$0_main)
_hash = __memoized_$(_$0_hash)
memoized = $(if $($(_hash)),,$(eval $(_hash) := _ $(_main)))$(call rest,$($(_hash)))

Now, I’m pretty sure that should work, but I have only actually tested the first version.

TL;DR

Avoid doing things in Make that would make you lean on complex solutions like an external memoize function.

However, if you do end up needing a more flexible memoize routine, I wrote one that you can use.

I'm excited about the new RYF-certified routers from ThinkPenguin

2014-09-12T00:00:00+00:00

I’m excited about the new RYF-certified routers from ThinkPenguin

I just learned that on Wednesday, the FSF awarded the RYF certification to the Think Penguin TPE-NWIFIROUTER wireless router.

I didn’t find this information directly published up front, but simply: It is a re-branded TP-Link TL-841ND modded to be running libreCMC.

I’ve been a fan of the TL-841/740 line of routers for several years now. They are dirt cheap (if you go to Newegg and sort by “cheapest,” it’s frequently the TL-740N), are extremely reliable, and run OpenWRT like a champ. They are my go-to routers.

(And they sure beat the snot out of the Arris TG862 that it seems like everyone has in their homes now. I hate that thing, it even has buggy packet scheduling.)

So this announcement is ~~doubly~~triply exciting for me:

I have a solid recommendation for a router that doesn’t require me or them to manually install an after-market firmware (buy it from ThinkPenguin).
If it’s for me, or someone technical, I can cut costs by getting a stock TP-Link from Newegg, installing libreCMC ourselves.
I can install a 100% libre distribution on my existing routers (until recently, they were not supported by any of the libre distributions, not for technical reasons, but lack of manpower).

I hope to get libreCMC installed on my boxes this weekend!

What I'm working on (Fall 2014)

2014-09-11T00:00:00+00:00

What I’m working on (Fall 2014)

I realized today that I haven’t updated my log in a while, and I don’t have any “finished” stuff to show off right now, but I should just talk about all the cool stuff I’m working on right now.

Static parsing of subshells

Last year I wrote a shell (for my Systems Programming class); however, I went above-and-beyond and added some really novel features. In my opinion, the most significant is that it parses arbitrarily deep subshells in one pass, instead of deferring them until execution. No shell that I know of does this.

At first this sounds like a really difficult, but minor feature. Until you think about scripting, and maintenance of those scripts. Being able to do a full syntax check of a script is crucial for long-term maintenance, yet it’s something that is missing from every major shell. I’d love to get this code merged into bash. It would be incredibly useful for some software I maintain.

Anyway, I’m trying to publish this code, but because of a recent kerfuffle with a student publishing all of his projects on the web (and other students trying to pass it off as their own), I’m being cautious with this and making sure Purdue is alright with what I’m putting online.

Stateless user configuration for PAM/NSS

Parabola GNU/Linux-libre users know that over this summer, we had a mess with server outages. One of the servers is still out (due to things out of our control), and we don’t have some of the data on it (because volunteer developers are terrible about back-ups, apparently).

This has caused us to look at how we manage our servers, back-ups, and several other things.

One thing that I’ve taken on as my pet project is making sure that if a server goes down, or we need to migrate (for example, Jon is telling us that he wants us to hurry up and switch to the new 64 bit hardware so he can turn off the 32 bit box), we can spin up a new server from scratch pretty easily. Part of that is making configurations stateless, and dynamic based on external data; having data be located in one place instead of duplicated across 12 config files and 3 databases… on the same box.

Right now, that’s looking like some custom software interfacing with OpenLDAP and OpenSSH via sockets (OpenLDAP being a middle-man between us and PAM (Linux) and NSS (libc)). However, the OpenLDAP documentation is… inconsistent and frustrating. I might end up hacking up the LDAP modules for NSS and PAM to talk to our system directly, and cut OpenLDAP out of the picture. We’ll see!

PS: Pablo says that tomorrow we should be getting out-of-band access to the drive of the server that is down, so that we can finally restore those services on a different server.

Project Leaguer

Last year, some friends and I began writing some “eSports tournament management software”, primarily targeting League of Legends (though it has a module system that will allow it to support tons of different data sources). We mostly got it done last semester, but it had some rough spots and sharp edges we need to work out. Because we were all out of communication for the summer, we didn’t work on it very much (but we did a little!). It’s weird that I care about this, because I’m not a gamer. Huh, I guess coding with friends is just fun.

Anyway, this year, Andrew, Davis, and I are planning to get it to a polished state by the end of the semester. We could probably do it faster, but we’d all also like to focus on classes and other projects a little more.

C+=1

People tend to lump C and C++ together, which upsets me, because I love C, but have a dislike for C++. That’s not to say that C++ is entirely bad; it has some good features. My “favorite” code is actually code that is basically C, but takes advantage of a couple C++ features, while still being idiomatic C, not C++.

Anyway, with the perspective of history (what worked and what didn’t), and a slightly opinionated view on language design (I’m pretty much a Rob Pike fan-boy), I thought I’d try to tackle “object-oriented C” with roughly the same design criteria as Stroustrup had when designing C++. I’m calling mine C+=1, for obvious reasons.

I haven’t published anything yet, because calling it “working” would be stretching the truth. But I am using it for my assignments in CS 334 (Intro to Graphics), so it should move along fairly quickly, as my grade depends on it.

I’m not taking it too seriously; I don’t expect it to be much more than a toy language, but it is an excuse to dive into the GCC internals.

Projects that I’ve put on the back-burner

I’ve got several other projects that I’m putting on hold for a while.

maven-dist (was hosted with Parabola, apparently I haven’t pushed it anywhere except the server that is down): A tool to build Apache Maven from source. That sounds easy, it’s open source, right? Well, except that Maven is the build system from hell. It doesn’t support cyclic dependencies, yet uses them internally to build itself. It loves to just get binaries from Maven Central to “optimize” the build process. It depends on code that depends on compiler bugs that no longer exist (which I guess means that no one has tried to build it from source after it was originally published). I’ve been working on-and-off on this for more than a year. My favorite part of it was writing a sed script that translates a JFlex grammar specification into a JLex grammar, which is used to bootstrap JFlex; its both gross and delightful at the same time.
Integration between dbscripts and abslibre. If you search IRC logs, mailing lists, and ParabolaWiki, you can find numerous rants by me against dbscripts:db-sync. I just hate the data-flow, it is almost designed to make things get out of sync, and broken. I mean, does this look like a simple diagram? For contrast, here’s a rough (slightly incomplete) diagram of what I want to replace it with.
Git backend for MediaWiki (or, pulling out the rendering module of MediaWiki). I’ve made decent progress on that front, but there is crazy de-normalization going on in the MediaWiki schema that makes this very difficult. I’m sure some of it is for historical reasons, and some of it for performance, but either way it is a mess for someone trying to neatly gut that part of the codebase.

Other

I should consider doing a write-up of deterministic-tar behavior (something that I’ve been implementing in Parabola for a while, meanwhile the Debian people have also been working on it).

I should also consider doing a “post-mortem” of PBS, which never actually got used, but launched XBS (part of the dbscripts/abslibre integration mentioned above), as well as serving as a good test-bed for features that did get implemented.

I over-use the word “anyway.”

Miscellaneous ways to improve your Rails experience

2014-05-08T00:00:00+00:00

Miscellaneous ways to improve your Rails experience

Recently, I’ve been working on a Rails web application, that’s really the baby of a friend of mine. Anyway, through its development, I’ve come up with a couple things that should make your interactions with Rails more pleasant.

Auto-(re)load classes from other directories than `app/`

The development server automatically loads and reloads files from the app/ directory, which is extremely nice. However, most web applications are going to involve modules that aren’t in that directory; and editing those files requires re-starting the server for the changes to take effect.

Adding the following lines to your config/application.rb will allow it to automatically load and reload files from the lib/ directory. You can of course change this to whichever directory/ies you like.

module YourApp
    class Application < Rails::Application
        …
        config.autoload_paths += ["#{Rails.root}/lib"]
        config.watchable_dirs["#{Rails.root}/lib"] = [:rb]
        …
    end
end

Have `submit_tag` generate a button instead of an input

In HTML, the <input type="submit"> tag styles slightly differently than other inputs or buttons. It is impossible to precisely controll the hight via CSS, which makes designing forms a pain. This is particularly noticable if you use Bootstrap 3, and put it next to another button; the submit button will be slightly shorter vertically.

The obvious fix here is to use <button type="submit"> instead. The following code will modify the default Rails form helpers to generate a button tag instead of an input tag. Just stick the code in config/initializers/form_improvements.rb; it will override ActionView::Hlepers::FormTagHelper#submit_tag. It is mostly the standard definition of the function, except for the last line, which has changed.

# -*- ruby-indent-level: 2; indent-tabs-mode: nil -*-
module ActionView
  module Helpers
    module FormTagHelper

      # This is modified from actionpack-4.0.2/lib/action_view/helpers/form_tag_helper.rb#submit_tag
      def submit_tag(value = "Save changes", options = {})
        options = options.stringify_keys

        if disable_with = options.delete("disable_with")
          message = ":disable_with option is deprecated and will be removed from Rails 4.1. " \
                    "Use 'data: { disable_with: \'Text\' }' instead."
          ActiveSupport::Deprecation.warn message

          options["data-disable-with"] = disable_with
        end

        if confirm = options.delete("confirm")
          message = ":confirm option is deprecated and will be removed from Rails 4.1. " \
                    "Use 'data: { confirm: \'Text\' }' instead'."
          ActiveSupport::Deprecation.warn message

          options["data-confirm"] = confirm
        end

        content_tag(:button, value, { "type" => "submit", "name" => "commit", "value" => value }.update(options))
      end

    end
  end
end

I’ll probably update this page as I tweak other things I don’t like.

Bash redirection

2014-02-13T00:00:00+00:00

Bash redirection

Apparently, too many people don’t understand Bash redirection. They might get the basic syntax, but they think of the process as declarative; in Bourne-ish shells, it is procedural.

In Bash, streams are handled in terms of “file descriptors” of “FDs”. FD 0 is stdin, FD 1 is stdout, and FD 2 is stderr. The equivalence (or lack thereof) between using a numeric file descriptor, and using the associated file in /dev/* and /proc/* is interesting, but beyond the scope of this article.

Step 1: Pipes

To quote the Bash manual:

A 'pipeline' is a sequence of simple commands separated by one of the
control operators '|' or '|&'.

   The format for a pipeline is
     [time [-p]] [!] COMMAND1 [ [| or |&] COMMAND2 ...]

Now, |& is just shorthand for 2>&1 |, the pipe part happens here, but the 2>&1 part doesn’t happen until step 2.

First, if the command is part of a pipeline, the pipes are set up. For every instance of the | metacharacter, Bash creates a pipe (pipe(3)), and duplicates (dup2(3)) the write end of the pipe to FD 1 of the process on the left side of the |, and duplicate the read end of the pipe to FD 0 of the process on the right side.

Step 2: Redirections

After the initial FD 0 and FD 1 fiddling by pipes is done, Bash looks at the redirections. This means that redirections can override pipes.

Redirections are read left-to-right, and are executed as they are read, using dup2(right-side, left-side). This is where most of the confusion comes from, people think of them as declarative, which leads to them doing the first of these, when they mean to do the second:

cmd 2>&1 >file # stdout goes to file, stderr goes to stdout
cmd >file 2>&1 # both stdout and stderr go to file

My favorite bug: segfaults in Java

2014-01-13T00:00:00+00:00

My favorite bug: segfaults in Java

Update: Two years later, I wrote a more detailed version of this article: My favorite bug: segfaults in Java (redux).

I’ve told this story orally a number of times, but realized that I have never written it down. This is my favorite bug story; it might not be my hardest bug, but it is the one I most like to tell.

The context

In 2012, I was a Senior programmer on the FIRST Robotics Competition team 1024. For the unfamiliar, the relevant part of the setup is that there are 2 minute and 15 second matches in which you have a 120 pound robot that sometimes runs autonomously, and sometimes is controlled over WiFi from a person at a laptop running stock “driver station” software and modifiable “dashboard” software.

The dashboard was written in Java, and the source was available (under a 3-clause BSD license), so I dove in, hunting for the bug. Now, the program did use Java Native Interface to talk to OpenCV, which the video ran through; so I figured that it must be a bug in the C/C++ code that was being called. It was especially a pain to track down the pointers that were causing the issue, because it was hard with native debuggers to see through all of the JVM stuff to the OpenCV code, and the OpenCV stuff is opaque to Java debuggers.

Eventually the issue lead me back into the Java code—there was a native pointer being stored in a Java variable; Java code called the native routine to free() the structure, but then tried to feed it to another routine later. This lead to difficulty again—tracking objects with Java debuggers was hard because they don’t expect the program to suddenly segfault; it’s Java code, Java doesn’t segfault, it throws exceptions!

With the help of println() I was eventually able to see that some code was executing in an order that straight didn’t make sense.

The bug

The issue was that Java was making an unsafe optimization (I never bothered to figure out if it is the compiler or the JVM making the mistake, I was satisfied once I had a work-around).

Java was doing something similar to tail-call optimization with regard to garbage collection. You see, if it is waiting for the return value of a method m() of object o, and code in m() that is yet to be executed doesn’t access any other methods or properties of o, then it will go ahead and consider o eligible for garbage collection before m() has finished running.

That is normally a safe optimization to make… except for when a destructor method (finalize()) is defined for the object; the destructor can have side effects, and Java has no way to know whether it is safe for them to happen before m() has finished running.

The work-around

The routine that the segmentation fault was occurring in was something like:

public type1 getFrame() {
    type2 child = this.getChild();
    type3 var = this.something();
    // `this` may now be garbage collected
    return child.somethingElse(var); // segfault comes here
}

Where the destructor method of this calls a method that will free() native memory that is also accessed by child; if this is garbage collected before child.somethingElse() runs, the backing native code will try to access memory that has been free()ed, and receive a segmentation fault. That usually didn’t happen, as the routines were pretty fast. However, running 30 times a second, eventually bad luck with the garbage collector happens, and the program crashes.

The work-around was to insert a bogus call to this to keep this around until after we were also done with child:

public type1 getFrame() {
    type2 child = this.getChild();
    type3 var = this.something();
    type1 ret = child.somethingElse(var);
    this.getSize(); // bogus call to keep `this` around
    return ret;
}

Yeah. After spending weeks wading through though thousands of lines of Java, C, and C++, a bogus call to a method I didn’t care about was the fix.

Bash arrays

2013-10-13T00:00:00+00:00

Bash arrays

Way too many people don’t understand Bash arrays. Many of them argue that if you need arrays, you shouldn’t be using Bash. If we reject the notion that one should never use Bash for scripting, then thinking you don’t need Bash arrays is what I like to call “wrong”. I don’t even mean real scripting; even these little stubs in /usr/bin:

#!/bin/sh
java -jar /…/something.jar $* # WRONG!

Command line arguments are exposed as an array, that little $* is accessing it, and is doing the wrong thing (for the lazy, the correct thing is -- "$@"). Arrays in Bash offer a safe way preserve field separation.

One of the main sources of bugs (and security holes) in shell scripts is field separation. That’s what arrays are about.

What? Field separation?

Field separation is just splitting a larger unit into a list of “fields”. The most common case is when Bash splits a “simple command” (in the Bash manual’s terminology) into a list of arguments. Understanding how this works is an important prerequisite to understanding arrays, and even why they are important.

Dealing with lists is something that is very common in Bash scripts; from dealing with lists of arguments, to lists of files; they pop up a lot, and each time, you need to think about how the list is separated. In the case of $PATH, the list is separated by colons. In the case of $CFLAGS, the list is separated by whitespace. In the case of actual arrays, it’s easy, there’s no special character to worry about, just quote it, and you’re good to go.

Bash word splitting

When Bash reads a “simple command”, it splits the whole thing into a list of “words”. “The first word specifies the command to be executed, and is passed as argument zero. The remaining words are passed as arguments to the invoked command.” (to quote bash(1))

It is often hard for those unfamiliar with Bash to understand when something is multiple words, and when it is a single word that just contains a space or newline. To help gain an intuitive understanding, I recommend using the following command to print a bullet list of words, to see how Bash splits them up:

printf ' -> %s\n' words… -> word one
 -> multiline
word
 -> third word

In a simple command, in absence of quoting, Bash separates the “raw” input into words by splitting on spaces and tabs. In other places, such as when expanding a variable, it uses the same process, but splits on the characters in the $IFS variable (which has the default value of space/tab/newline). This process is, creatively enough, called “word splitting”.

In most discussions of Bash arrays, one of the frequent criticisms is all the footnotes and “gotchas” about when to quote things. That’s because they usually don’t set the context of word splitting. Double quotes (") inhibit Bash from doing word splitting. That’s it, that’s all they do. Arrays are already split into words; without wrapping them in double quotes Bash re-word splits them, which is almost never what you want; otherwise, you wouldn’t be working with an array.

Normal array syntax

Setting an array

`words…` is expanded and subject to word splitting based on `$IFS`.
`array=(words…)`	Set the contents of the entire array.
`array+=(words…)`	Appends `words…` to the end of the array.
`array[n]=word`	Sets an individual entry in the array, the first entry is at `n`=0.

Now, for accessing the array. The most important things to understanding arrays is to quote them, and understanding the difference between @ and *.

Getting an entire array

Unless these are wrapped in double quotes, they are subject to word splitting, which defeats the purpose of arrays.

I guess it's worth mentioning that if you don't quote them, and word splitting is applied, `@` and `*` end up being equivalent.

With `*`, when joining the elements into a single string, the elements are separated by the first character in `$IFS`, which is, by default, a space.
`"${array[@]}"`	Evaluates to every element of the array, as a separate words.
`"${array[*]}"`	Evaluates to every element of the array, as a single word.

It’s really that simple—that covers most usages of arrays, and most of the mistakes made with them.

To help you understand the difference between @ and *, here is a sample of each:

@ *

`@`	`*`
Input: `#!/bin/bash array=(foo bar baz) for item in "${array[@]}"; do echo " - <${item}>" done`	Input: `#!/bin/bash array=(foo bar baz) for item in "${array[*]}"; do echo " - <${item}>" done`
Output: `- <foo> - <bar> - <baz>`	Output: `- <foo bar baz>`

Input:

#!/bin/bash
array=(foo bar baz)
for item in "${array[@]}"; do
        echo " - <${item}>"
done

Input:

#!/bin/bash
array=(foo bar baz)
for item in "${array[*]}"; do
        echo " - <${item}>"
done

Output:

 - <foo>
 - <bar>
 - <baz>

Output:

 - <foo bar baz>

In most cases, @ is what you want, but * comes up often enough too.

To get individual entries, the syntax is ${array[n]}, where n starts at 0.

Getting a single entry from an array

Also subject to word splitting if you don't wrap it in quotes.
`"${array[n]}"`	Evaluates to the `n`^th entry of the array, where the first entry is at `n`=0.

To get a subset of the array, there are a few options:

Getting subsets of an array

Substitute `*` for `@` to get the subset as a `$IFS`-separated string instead of separate words, as described above.

Again, if you don't wrap these in double quotes, they are subject to word splitting, which defeats the purpose of arrays.
`"${array[@]:start}"`	Evaluates to the entries from `n`=`start` to the end of the array.
`"${array[@]:start:count}"`	Evaluates to `count` entries, starting at `n`=`start`.
`"${array[@]::count}"`	Evaluates to `count` entries from the beginning of the array.

Notice that "${array[@]}" is equivalent to "${array[@]:0}".

Getting the length of an array

The is the only situation with arrays where quoting doesn't make a difference.

True to my earlier statement, when unquoted, there is no difference between `@` and `*`.
`${#array[@]}` or `${#array[*]}`	Evaluates to the length of the array

Argument array syntax

Accessing the arguments is mostly that simple, but that array doesn’t actually have a variable name. It’s special. Instead, it is exposed through a series of special variables (normal variables can only start with letters and underscore), that mostly match up with the normal array syntax.

Setting the arguments array, on the other hand, is pretty different. That’s fine, because setting the arguments array is less useful anyway.

Accessing the arguments array

Note that for values of `n` with more than 1 digit, you need to wrap it in `{}`. Otherwise, `"$10"` would be parsed as `"${1}0"`.
Individual entries
`${array[0]}`	`$0`
`${array[1]}`	`$1`
…
`${array[9]}`	`$9`
`${array[10]}`	`${10}`
…
`${array[n]}`	`${n}`
Subset arrays (array)
`"${array[@]}"`	`"${@:0}"`
`"${array[@]:1}"`	`"$@"`
`"${array[@]:pos}"`	`"${@:pos}"`
`"${array[@]:pos:len}"`	`"${@:pos:len}"`
`"${array[@]::len}"`	`"${@::len}"`
Subset arrays (string)
`"${array[*]}"`	`"${*:0}"`
`"${array[*]:1}"`	`"$*"`
`"${array[*]:pos}"`	`"${*:pos}"`
`"${array[*]:pos:len}"`	`"${*:pos:len}"`
`"${array[*]::len}"`	`"${*::len}"`
Array length
`${#array[@]}`	`$#` + 1
Setting the array
`array=("${array[0]}" words…)`	`set -- words…`
`array=("${array[0]}" "${array[@]:2}")`	`shift`
`array=("${array[0]}" "${array[@]:n+1}")`	`shift n`

Did you notice what was inconsistent? The variables $*, $@, and $# behave like the n=0 entry doesn’t exist.

Inconsistencies
`@` or `*`
`"${array[@]}"`	→	`"${array[@]:0}"`
`"${@}"`	→	`"${@:1}"`
`#`
`"${#array[@]}"`	→	length
`"${#}"`	→	length-1

These make sense because argument 0 is the name of the script—we almost never want that when parsing arguments. You’d spend more code getting the values that it currently gives you.

Now, for an explanation of setting the arguments array. You cannot set argument n=0. The set command is used to manipulate the arguments passed to Bash after the fact—similarly, you could use set -x to make Bash behave like you ran it as bash -x; like most GNU programs, the -- tells it to not parse any of the options as flags. The shift command shifts each entry n spots to the left, using n=1 if no value is specified; and leaving argument 0 alone.

But you mentioned “gotchas” about quoting!

But I explained that quoting simply inhibits word splitting, which you pretty much never want when working with arrays. If, for some odd reason, you do what word splitting, then that’s when you don’t quote. Simple, easy to understand.

I think possibly the only case where you do want word splitting with an array is when you didn’t want an array, but it’s what you get (arguments are, by necessity, an array). For example:

# Usage: path_ls PATH1 PATH2…
# Description:
#   Takes any number of PATH-style values; that is,
#   colon-separated lists of directories, and prints a
#   newline-separated list of executables found in them.
# Bugs:
#   Does not correctly handle programs with a newline in the name,
#   as the output is newline-separated.
path_ls() {
    local IFS dirs
    IFS=:
    dirs=($@) # The odd-ball time that it needs to be unquoted
    find -L "${dirs[@]}" -maxdepth 1 -type f -executable \
        -printf '%f\n' 2>/dev/null | sort -u
}

Logically, there shouldn’t be multiple arguments, just a single $PATH value; but, we can’t enforce that, as the array can have any size. So, we do the robust thing, and just act on the entire array, not really caring about the fact that it is an array. Alas, there is still a field-separation bug in the program, with the output.

I still don’t think I need arrays in my scripts

Consider the common code:

ARGS=' -f -q'
…
command $ARGS  # unquoted variables are a bad code-smell anyway

Here, $ARGS is field-separated by $IFS, which we are assuming has the default value. This is fine, as long as $ARGS is known to never need an embedded space; which you do as long as it isn’t based on anything outside of the program. But wait until you want to do this:

ARGS=' -f -q'
…
if [[ -f "$filename" ]]; then
    ARGS+=" -F $filename"
fi
…
command $ARGS

Now you’re hosed if $filename contains a space! More than just breaking, it could have unwanted side effects, such as when someone figures out how to make filename='foo --dangerous-flag'.

Compare that with the array version:

ARGS=(-f -q)
…
if [[ -f "$filename" ]]; then
    ARGS+=(-F "$filename")
fi
…
command "${ARGS[@]}"

What about portability?

Except for the little stubs that call another program with "$@" at the end, trying to write for multiple shells (including the ambiguous /bin/sh) is not a task for mere mortals. If you do try that, your best bet is probably sticking to POSIX. Arrays are not POSIX; except for the arguments array, which is; though getting subset arrays from $@ and $* is not (tip: use set -- to re-purpose the arguments array).

Writing for various versions of Bash, though, is pretty do-able. Everything here works all the way back in bash-2.0 (December 1996), with the following exceptions:

The += operator wasn’t added until Bash 3.1.
- As a work-around, use array[${#array[*]}]=word to append a single element.
Accessing subset arrays of the arguments array is inconsistent if pos=0 in ${@:pos:len}.
- In Bash 2.x and 3.x, it works as expected, except that argument 0 is silently missing. For example ${@:0:3} gives arguments 1 and 2; where ${@:1:3} gives arguments 1, 2, and 3. This means that if pos=0, then only len-1 arguments are given back.
- In Bash 4.0, argument 0 can be accessed, but if pos=0, then it only gives back len-1 arguments. So, ${@:0:3} gives arguments 0 and 1.
- In Bash 4.1 and higher, it works in the way described in the main part of this document.

Now, Bash 1.x doesn’t have arrays at all. $@ and $* work, but using : to select a range of elements from them doesn’t. Good thing most boxes have been updated since 1996!

A git pre-commit hook for automatically formatting Go code

2013-10-12T00:00:00+00:00

A git pre-commit hook for automatically formatting Go code

One of the (many) wonderful things about the Go programming language is the gofmt tool, which formats your source in a canonical way. I thought it would be nice to integrate this in my git workflow by adding it in a pre-commit hook to automatically format my source code when I committed it.

The Go distribution contains a git pre-commit hook that checks whether the source code is formatted, and aborts the commit if it isn’t. I don’t remember if I was aware of this at the time (or if it even existed at the time, or if it is new), but I wanted it to go ahead and format the code for me.

I found a few solutions online, but they were all missing something—support for partial commits. I frequently use git add -p/git gui to commit a subset of the changes I’ve made to a file, the existing solutions would end up adding the entire set of changes to my commit.

I ended up writing a solution that only formats the version of the that is staged for commit; here’s my .git/hooks/pre-commit:

#!/bin/bash

# This would only loop over files that are already staged for commit.
#     git diff --cached --numstat |
#     while read add del file; do
#         …
#     done

shopt -s globstar
for file in **/*.go; do
    tmp="$(mktemp "$file.bak.XXXXXXXXXX")"
    mv "$file" "$tmp"
    git checkout "$file"
    gofmt -w "$file"
    git add "$file"
    mv "$tmp" "$file"
done

It’s still not perfect. It will try to operate on every *.go file—which might do weird things if you have a file that hasn’t been checked in at all. This also has the effect of formatting files that were checked in without being formatted, but weren’t modified in this commit.

I don’t remember why I did that—as you can see from the comment, I knew how to only select files that were staged for commit. I haven’t worked on any projects in Go in a while—if I return to one of them, and remember why I did that, I will update this page.

`dprintf`: print formatted text directly to a file descriptor

2013-10-12T00:00:00+00:00

`dprintf`: print formatted text directly to a file descriptor

This already existed as dprintf(3). I now feel stupid for having Implemented fd_printf.

The original post is as follows:

I wrote this while debugging some code, and thought it might be useful to others:

#define _GNU_SOURCE     /* vasprintf() */
#include <stdarg.h>     /* va_start()/va_end() */
#include <stdio.h>      /* vasprintf() */
#include <stdlib.h>     /* free() */
#include <unistd.h>     /* write() */

int
fd_printf(int fd, const char *format, ...)
{
    va_list arg;
    int len;
    char *str;

    va_start(arg, format);
    len = vasprintf(&str, format, arg);
    va_end(arg);

    write(fd, str, len);

    free(str);
    return len;
}

It is a version of printf that prints to a file descriptor—where fprintf prints to a FILE* data structure.

The appeal of this is that FILE* I/O is buffered—which means mixing it with raw file descriptor I/O is going to produce weird results.

Emacs as an operating system

2013-08-29T00:00:00+00:00

Emacs as an operating system

This was originally published on Hacker News on 2013-08-29.

Calling Emacs an OS is dubious, it certainly isn’t a general purpose OS, and won’t run on real hardware. But, let me make the case that Emacs is an OS.

Emacs has two parts, the C part, and the Emacs Lisp part.

The C part isn’t just a Lisp interpreter, it is a Lisp Machine emulator. It doesn’t particularly resemble any of the real Lisp machines. The TCP, Keyboard/Mouse, display support, and filesystem are done at the hardware level (the operations to work with these things are among the primitive operations provided by the hardware). Of these, the display being handled by the hardware isn’t particularly uncommon, historically; the filesystem is a little stranger.

The Lisp part of Emacs is the operating system that runs on that emulated hardware. It’s not a particularly powerful OS, it not a multitasking system. It has many packages available for it (though not until recently was there a official package manager). It has reasonably powerful IPC mechanisms. It has shells, mail clients (MUAs and MSAs), web browsers, web servers and more, all written entirely in Emacs Lisp.

You might say, “but a lot of that is being done by the host operating system!” Sure, some of it is, but all of it is sufficiently low level. If you wanted to share the filesystem with another OS running in a VM, you might do it by sharing it as a network filesystem; this is necessary when the VM OS is not designed around running in a VM. However, because Emacs OS will always be running in the Emacs VM, we can optimize it by having the Emacs VM include processor features mapping the native OS, and have the Emacs OS be aware of them. It would be slower and more code to do that all over the network.

A summary of Emacs' bundled shell and terminal modes

2013-04-09T00:00:00+00:00

A summary of Emacs’ bundled shell and terminal modes

This is based on a post on reddit, published on 2013-04-09.

Emacs comes bundled with a few different shell and terminal modes. It can be hard to keep them straight. What’s the difference between M-x term and M-x ansi-term?

Here’s a good breakdown of the different bundled shells and terminals for Emacs, from dumbest to most Emacs-y.

term-mode

Your VT100-esque terminal emulator; it does what most terminal programs do. Ncurses-things work OK, but dumping large amounts of text can be slow. By default it asks you which shell to run, defaulting to the environmental variable $SHELL (/bin/bash for me). There are two modes of operation:

char mode: Keys are sent immediately to the shell (including keys that are normally Emacs keystrokes), with the following exceptions:
- (term-escape-char) (term-escape-char) sends (term-escape-char) to the shell (see above for what the default value is).
- (term-escape-char) <anything-else> is like doing equates to C-x <anything-else> in normal Emacs.
- (term-escape-char) C-j switches to line mode.
line mode: Editing is done like in a normal Emacs buffer, <enter> sends the current line to the shell. This is useful for working with a program’s output.
- C-c C-k switches to char mode.

This mode is activated with

; Creates or switches to an existing "*terminal*" buffer.
; The default 'term-escape-char' is "C-c"
M-x term

; Creates a new "*ansi-term*" or "*ansi-term*<n>" buffer.
; The default 'term-escape-char' is "C-c" and "C-x"
M-x ansi-term

shell-mode

The name is a misnomer; shell-mode is a terminal emulator, not a shell; it’s called that because it is used for running a shell (bash, zsh, …). The idea of this mode is to use an external shell, but make it Emacs-y. History is not handled by the shell, but by Emacs; M-p and M-n access the history, while arrows/C-p/C-n move the point (which is is consistent with other Emacs REPL-type interfaces). It ignores VT100-type terminal colors, and colorizes things itself (it inspects words to see if they are directories, in the case of ls). This has the benefit that it does syntax highlighting on the currently being typed command. Ncurses programs will of course not work. This mode is activated with:

M-x shell

eshell-mode

This is a shell+terminal, entirely written in Emacs lisp. (Interestingly, it doesn’t set $SHELL, so that will be whatever it was when you launched Emacs). This won’t even be running zsh or bash, it will be running “esh”, part of Emacs.

An explanation of common terminal emulator color codes

2013-03-21T00:00:00+00:00

An explanation of common terminal emulator color codes

This is based on a post on reddit, published on 2013-03-21.

So all terminals support the same 256 colors? What about 88 color mode: is that a subset?

TL;DR: yes

Terminal compatibility is crazy complex, because nobody actually reads the spec, they just write something that is compatible for their tests. Then things have to be compatible with that terminal’s quirks.

But, here’s how 8-color, 16-color, and 256 color work. IIRC, 88 color is a subset of the 256 color scheme, but I’m not sure.

8 colors: (actually 9) First we had 8 colors (9 with “default”, which doesn’t have to be one of the 8). These are always roughly the same color: black, red, green, yellow/orange, blue, purple, cyan, and white, which are colors 0–7 respectively. Color 9 is default.

16 colors: (actually 18) Later, someone wanted to add more colors, so they added a “bright” attribute. So when bright is on, you get “bright red” instead of “red”. Hence 8*2=16 (plus two more for “default” and “bright default”).

256 colors: (actually 274) You may have noticed, colors 0–7 and 9 are used, but 8 isn’t. So, someone decided that color 8 should put the terminal into 256 color mode. In this mode, it reads another byte, which is an 8-bit RGB value (2 bits for red, 2 for green, 2 for blue). The bright property has no effect on these colors. However, a terminal can display 256-color-mode colors and 16-color-mode colors at the same time, so you actually get 256+18 colors.

An explanation of how "copyleft" licensing works

2013-02-21T00:00:00+00:00

An explanation of how “copyleft” licensing works

This is based on a post on reddit, published on 2013-02-21.

While reading the man page for readline I noticed the copyright section said “Readline is Copyright (C) 1989-2011 Free Software Foundation Inc”. How can software be both licensed under GNU and copyrighted to a single group? It was my understanding that once code became free it didn’t belong to any particular group or individual.

[LiveCode is GPLv3, but also sells non-free licenses] Can you really have the same code under two conflicting licenses? Once licensed under GPL3 wouldn’t they too be required to adhere to its rules?

I believe that GNU/the FSF has an FAQ that addresses this, but I can’t find it, so here we go.

Glossary:

“Copyright” is the right to control how copies are made of something.
Something for which no one holds the copyright is in the “public domain”, because anyone (“the public”) is allowed to do anything with it.
A “license” is basically a legal document that says “I promise not to sue you if make copies in these specific ways.”
A “non-free” license basically says “There are no conditions under which you can make copies that I won’t sue you.”
A “permissive” (type of free) license basically says “You can do whatever you want, BUT have to give me credit”, and is very similar to the public domain. If the copyright holder didn’t have the copyright, they couldn’t sue you to make sure that you gave them credit, and nobody would have to give them credit.
A “copyleft” (type of free) license basically says, “You can do whatever you want, BUT anyone who gets a copy from you has to be able to do whatever they want too.” If the copyright holder didn’t have the copyright, they couldn’t sue you to make sure that you gave the source to people go got it from you, and non-free versions of these programs would start to exist.

Specific questions:

Readline: The GNU GPL is a copyleft license. If you make a modified version of Readline, and give it to others without letting them have the source code, the FSF will sue you. They can do this because they have the copyright on Readline, and in the GNU GPL (the license they used) it only says that they won’t sue you if you distribute the source with the modified version. If they didn’t have the copyright, they couldn’t sue you, and the GNU GPL would be worthless.

LiveCode: The copyright holder for something is not required to obey the license—the license is only a promise not to sue you; of course they won’t sue themselves. They can also offer different terms to different people. They can tell most people “I won’t sue you as long as you share the source,” but if someone gave them a little money, they might say, “I also promise not sue sue this guy, even if he doesn’t give out the source.”

A quick overview of usage of the Pacman package manager

2013-01-23T00:00:00+00:00

A quick overview of usage of the Pacman package manager

This was originally published on Hacker News on 2013-01-23.

Note: I’ve over-done quotation marks to make it clear when precise wording matters.

pacman is a little awkward, but I prefer it to apt/dpkg, which have sub-commands, each with their own flags, some of which are undocumented. pacman, on the other hand, has ALL options documented in one fairly short man page.

The trick to understanding pacman is to understand how it maintains databases of packages, and what it means to “sync”.

There are several “databases” that pacman deals with:

“the database”, (/var/lib/pacman/local/)
The database of currently installed packages
“package databases”, (/var/lib/pacman/sync/${repo}.db)
There is one of these for each repository. It is a file that is fetched over plain http(s) from the server; it is not modified locally, only updated.

The “operation” of pacman is set with a capital flag, one of “DQRSTU” (plus -V and -h for version and help). Of these, “DTU” are “low-level” (analogous to dpkg) and “QRS” are “high-level” (analogous to apt).

To give a brief explanation of cover the “high-level” operations, and which databases they deal with:

“Q” Queries “the database” of locally installed packages.
“S” deals with “package databases”, and Syncing “the database” with them; meaning it installs/updates packages that are in package databases, but not installed on the local system.
“R” Removes packages “the database”; removing them from the local system.

The biggest “gotcha” is that “S” deals with all operations with “package databases”, not just syncing “the database” with them.

Why documentation on GNU/Linux sucks

2012-09-12T00:00:00+00:00

Why documentation on GNU/Linux sucks

This is based on a post on reddit, published on 2012-09-12.

The documentation situation on GNU/Linux based operating systems is right now a mess. In the world of documentation, there are basically 3 camps, the “UNIX” camp, the “GNU” camp, and the “GNU/Linux” camp.

The UNIX camp is the man page camp, they have quality, terse but informative man pages, on everything, including the system’s design and all system files. If it was up to the UNIX camp, man grub.cfg, man grub.d, and man grub-mkconfig_lib would exist and actually be helpful. The man page would either include inline examples, or point you to a directory. If I were to print off all of the man pages, it would actually be a useful manual for the system.

Then GNU camp is the info camp. They basically thought that each piece of software was more complex than a man page could handle. They essentially think that some individual pieces software warrant a book. So, they developed the info system. The info pages are usually quite high quality, but are very long, and a pain if you just want a quick look. The info system can generate good HTML (and PDF, etc.) documentation. But the standard info is awkward as hell to use for non-Emacs users.

Then we have the “GNU/Linux” camp, they use GNU software, but want to use man pages. This means that we get low-quality man pages for GNU software, and then we don’t have a good baseline for documentation, developers each try to create their own. The documentation that gets written is frequently either low-quality, or non-standard. A lot of man pages are auto-generated from --help output or info pages, meaning they are either not helpful, or overly verbose with low information density. This camp gets the worst of both worlds, and a few problems of its own.

What Arch Linux's switch to systemd means for users

2012-09-11T00:00:00+00:00

What Arch Linux’s switch to systemd means for users

This is based on a post on reddit, published on 2012-09-11.

systemd is a replacement for UNIX System V-style init; instead of having /etc/init.d/* or /etc/rc.d/* scripts, systemd runs in the background to manage them.

This has the advantages that there is proper dependency tracking, easing the life of the administrator and allowing for things to be run in parallel safely. It also uses “targets” instead of “init levels”, which just makes more sense. It also means that a target can be started or stopped on the fly, such as mounting or unmounting a drive, which has in the past only been done at boot up and shut down.

The downside is that it is (allegedly) big, bloated¹, and does (arguably) more than it should. Why is there a dedicated systemd-fsck? Why does systemd encapsulate the functionality of syslog? That, and it means somebody is standing on my lawn.

The changes an Arch user needs to worry about is that everything is being moved out of /etc/rc.conf. Arch users will still have the choice between systemd and SysV-init, but rc.conf is becoming the SysV-init configuration file, rather than the general system configuration file. If you will still be using SysV-init, basically the only thing in rc.conf will be DAEMONS.² For now there is compatibility for the variables that used to be there, but that is going away.

I don’t think it’s bloated, but that is the criticism. Basically, I discount any argument that uses “bloated” without backing it up. I was trying to say that it takes a lot of heat for being bloated, and that there is be some truth to that (the systemd-fsck and syslog comments), but that these claims are largely unsubstantiated, and more along the lines of “I would have done it differently”. Maybe your ideas are better, but you haven’t written the code.

I personally don’t have an opinion either way about SysV-init vs systemd. I recently migrated my boxes to systemd, but that was because the SysV init scripts for NFSv4 in Arch are problematic. I suppose this is another advantage I missed: people generally consider systemd “units” to be more robust and easier to write than SysV “scripts”.

I’m actually not a fan of either. If I had more time on my hands, I’d be running a make-based init system based on a research project IBM did a while ago. So I consider myself fairly objective; my horse isn’t in this race.↩︎
You can still have USEDMRAID, USELVM, interface, address, netmask, and gateway. But those are minor.↩︎

Luke Shumaker's Web Log

Announcing: btrfs-rec: Recover (data from) a broken btrfs filesystem

Announcing: btrfs-rec: Recover (data from) a broken btrfs filesystem

1. Motivation

2. Overview of use

3. Prior art

4. Internals/Design

4.1. Overview of the source tree layout

4.2. Base decisions: CLI structure, Go, JSON

4.3. Algorithms

4.3.1. The rebuild-mappings algorithm

4.3.2. The --rebuild algorithm

4.3.2.1. rebuilt forrest behavior (looking up trees)

4.3.2.2. rebuilt individual tree behavior

4.3.3. The rebuild-trees algorithm

4.3.3.1. initialization

4.3.3.2. the main loop

4.3.3.3. graph callbacks

5. Future work

6. Problems for merging this code into btrfs-progs

POSIX pricing and availability; or: Do you really need the PDF?

POSIX pricing and availability; or: Do you really need the PDF?

GNU/Linux Keyboard Maps: xmodmap

GNU/Linux Keyboard Maps: xmodmap

Conceptual overview

The X11 protocol

The xmodmap command

Appendix:

The interesting architecture of crt.sh

The interesting architecture of crt.sh

Notes on subtleties of HTTP implementation

Notes on subtleties of HTTP implementation

Why the absolute-form is used for proxy requests

On taking short-cuts based on early header field values

On normalizing target URIs

My X11 setup with systemd

My X11 setup with systemd

My favorite bug: segfaults in Java (redux)

My favorite bug: segfaults in Java (redux)

The context

The bug

My work-around

WPI’s fix

An Nginx configuration for MediaWiki

An Nginx configuration for MediaWiki

I took some videos at LibrePlanet

I took some videos at LibrePlanet

Building Bash 1.14.7 on a modern system

Building Bash 1.14.7 on a modern system

stdarg

Configuration

Building

Customizing your login on Purdue CS computers (WIP, but updated)

Customizing your login on Purdue CS computers (WIP, but updated)

GDM, the Gnome Display Manager

Purdue’s GDM configuration

Xsession

Network Shares

Lore

A memoization routine for GNU Make functions

A memoization routine for GNU Make functions

TL;DR

I'm excited about the new RYF-certified routers from ThinkPenguin

I’m excited about the new RYF-certified routers from ThinkPenguin

What I'm working on (Fall 2014)

What I’m working on (Fall 2014)

Static parsing of subshells

Stateless user configuration for PAM/NSS

Project Leaguer

C+=1

Projects that I’ve put on the back-burner

Other

Miscellaneous ways to improve your Rails experience

Miscellaneous ways to improve your Rails experience

Auto-(re)load classes from other directories than app/

Have submit_tag generate a button instead of an input

Bash redirection

Bash redirection

Step 1: Pipes

Step 2: Redirections

4.3.1. The `rebuild-mappings` algorithm

4.3.2. The `--rebuild` algorithm

4.3.3. The `rebuild-trees` algorithm

The `xmodmap` command

Auto-(re)load classes from other directories than `app/`

Have `submit_tag` generate a button instead of an input

`dprintf`: print formatted text directly to a file descriptor