This feed omits posts by rms. Just 'cause.

Posted Sat Aug 19 05:56:18 2017 Tags:
Options for neo-Nazis on the internet are starting to shrink

Yet the decision of web providers yanking services and ejecting Nazi scumbags is apparently a controversial and unprecedented issue. It would appear that until now, like Trump, internet companies like Facebook and Cloudflare have not shared the instinctive moral revulsion most Americans, Europeans, and British feel toward white supremacists and neo-Nazis. [...]

It should be noted that press has simultaneously noted that hate groups and white supremacist memes "thrive, even in wide open, public communities" on Facebook. Don't worry, it's still a clean, well-lit place for fascism: Facebook still defends Holocaust denial as free speech as its policy, despite the fact that it is illegal in 16 countries because it is linked to violence against Jews. [...]

The problem is that the same companies we're cheering at to take a bite out of Nazi privilege and access are the same companies whose takedown and censorship processes are muddy -- which is what gives them play to censor people they simply don't want on their services. Like people who work in the sex industry, and LGBT people, who are most often silenced at the censorship end of these policies. One need only read the news over the past several years to see that legitimate voices get silenced online far more than those of aging skinheads and young Nazis.

Previously, previously, previously, previously, previously, previously.

Posted Fri Aug 18 20:24:25 2017 Tags:
DNA Lounge update, wherein it's "Best Of" time, we have some great shows, and I list certain grievances.
Posted Fri Aug 18 19:57:55 2017 Tags:
I just rewatched Cleopatra 2525 and I'm here to tell you that it's still awesome.

It's Kung-Fu Barbarella. So much wire-fighting. So much Cyberdog. Floating shape-shifting robots have chased humanity underground, occasionally attacking with T-1000s with blaster arms. Everyone has Spider-Man web-shooters, and there's an evil clown. It's got everything! But the thing that makes it work is that it's a comedy but almost every character in it fully commits to being in an action movie. They are So Very Serious.

It does, however, have a theme song that is possibly worse than Enterprise. Don't let that put you off.

It ends on an extremely frustrating cliffhanger and a final episode that seems to have stopped production halfway through. Yet Arrow gets six seasons. I would trade the entirety of Game of Thrones for one more season of Cleopatra 2525.

Here, here, watch. It looks like the whole thing is on Youtube too, but in varying quality.

Previously, previously, previously.

Posted Thu Aug 17 19:19:32 2017 Tags:
Kali Diaries - Entry #3

Lauren Mary Kim (who doubles Elektra in Marvel's Daredevil & Defenders) VS. Amy Johnston (who is one of Black Widow's stunt doubles in Marvel's Avengers) Fight features daggers and JKD. Choreographed by Tsuyoshi Abe. Fight Coordinator, Camera and Edit by Bryan Sloyer.


Posted Thu Aug 17 00:29:28 2017 Tags:
When all those Confederate monuments and statues were erected:

Yes, these monuments were put up to honor Confederate leaders. But the timing of the monument building makes it pretty clear what the real motivation was: to physically symbolize white terror against blacks. They were mostly built during times when Southern whites were engaged in vicious campaigns of subjugation against blacks, and during those campaigns the message sent by a statue of Robert E. Lee in front of a courthouse was loud and clear.

No one should think that these statues were meant to be somber postbellum reminders of a brutal war. They were built much later, and most of them were explicitly created to accompany organized and violent efforts to subdue blacks and maintain white supremacy in the South. I wouldn't be surprised if even a lot of Southerners don't really understand this, but they should learn. There's a reason blacks consider these statues to be symbols of bigotry and terror. It's because they are.

Wikipedia: President of the Confederate States of America: List of presidents:

"Confederate States Accidental Election, 2017"

Posted Wed Aug 16 20:13:50 2017 Tags:

"We fought a war over this, you cocksuckers!" the robot was heard to say.

Previously, previously, previously, previously.

Posted Tue Aug 15 20:42:39 2017 Tags:

How big should your queue be, and what should you do when it fills up? Many times, we implement or even deploy a networking system before we have answered those questions. Luckily, recent research has given us some guidelines. Here's what we know:

  1. There are two ways to deal with a full queue: drop packets, or throttle incoming packets (backpressure).

  2. Most network queues are mostly empty. The only exceptions are caused by burstiness (uneven incoming packet rates), and bottlenecks (exactly one slowest queue per network path).

  3. Queues exist only to handle burstiness. If traffic flowed at a constant rate, every queue would be empty except the bottleneck, which would be full (bufferbloat), no matter its limit.

    • Corollary: limit queue length to a statistically large burst (eg. 99th percentile).
  4. Backpressure may be implicit. For example, if an ethernet driver is slow to pull packets from the Linux netdev queue x into the device's ring buffer y, then there is implicit backpressure from y to x even though no signal is sent to x.

  5. Dropping packets should be intentional. An ethernet device will tail-drop incoming packets if its (usually fixed-size) receive ring buffer is exhausted, leaving software no control over what to drop. To take control, we could add a big software queue and unload the device's receive ring buffer to it as quickly as possible.

  6. Burstiness can come from inside a router or switch. Examples: It's more CPU-efficient to process 100 packets at a time instead of one. TSO/GSO are getting popular, and can produce, eg., bursts of 40+ packets from a single 64k buffer. (Pacing leaves time between 64k bursts.) Frame aggregation does the same on wifi. (Wifi nodes can negotiate reduced aggregation sizes if their buffers are small.)

  7. Use backpressure when muxing. In our diagram, from i to x, it is best to use backpressure from x to i so that i can drop packets from individual queues.

    • Prioritized handling of incoming packets is equivalent to muxing. Multiple priority queues are drained by a single CPU, creating an implicit single queue. Draining them too slowly creates implicit backpressure.
  8. Drop packets when demuxing. From y to o, it's best to drop packets at o rather than use backpressure from o to y. Otherwise, a single full output queue could starve the others by stopping y. (Example: imagine if a full queue to a 1 Mbps wifi station could stop traffic to a 100 Mbps wifi station. Some Linux wifi drivers suffer from this.)

    • Prioritizing outgoing packets is demuxing. You must prioritize first, then drop packets from the low-priority queues. Prioritizing too slowly creates backpressure on all packets, which would punish high priority packets.
  9. Tail drop is worst drop. There are several variants of AQM (active queue management) with different tradeoffs, but almost all are better than dropping the newest packet when a queue is full. Even the opposite ("head drop") is better in many cases. (Later TCP ACKs encompass all the information from previous ACKs, so if you have to drop one, it might as well be the oldest one.) CoDel is a more refined AQM. Most AQMs are the same speed or only slightly slower than tail drop.

  10. Some queues are way too short, and you have to design around it. For example, consumer-grade ethernet switches might have only one or two packets of queue space per port. Burstiness must be artificially reduced in order for these switches to protect traffic when busy. This leads to inventions like TCP pacing and TCP BBR.

  11. Ethernet "pause" frames usually make things worse. A general-purpose ethernet switch looks like our diagram: a mux and a demux chained together. At the mux, you want backpressure on the individual queues i. At the demux, you want to drop packets when queues o get full. Unfortunately, the latter prevents the former; since o drops packets, x and y are always empty, so there is no backpressure to apply to i. Unfortunately that's correct behaviour. Imagine incoming port i1 wants to send traffic alternately to ports o1 and o2. It would be wrong to pause i1 just because o1 is full, because that will starve o2. There is no "correct" solution except adequate buffering (for transients) on o1 and o2.

    • "Pause" frames work when the bottleneck is x or y rather than o. For example, we connected the input to a 400 Mbps MoCA chip to one output port on our switch via gigabit RGMII. The MoCA chip may be connected to many other MoCA targets, but it is not a demux: all traffic goes out on the shared MoCA bus, which acts like queue y in our diagram. The MoCA chip should apply backpressure so that better decisions can be made at i.

      (However, it would be wrong to further propagate backpressure from individual MoCA targets back to y. The MoCA bus itself acts as an implicit zero-queue demux o; individual targets will have to drop packets if they can't handle them.)

  12. "Fair" queueing is undefinable, but we have to try. All of the above helps get you to an optimal point where you eventually need to drop packets at i or o. Unfortunately, deciding which streams to drop is impossible in the general case. In the simple example of a server where i1 is very heavy but i2 has only a trickle of traffic, and queue space is exhausted, should you drop traffic from i1? What if i1 has 100 users behind a NAT but i2 has only one user? There is no answer that works in all situations.

(Sorry this is so dense. I challenged myself to make this into a "two pager" that I could send to people at work. But sometimes two pages is harder to read than five pages...)

Posted Fri Aug 11 08:08:36 2017 Tags:

Last November I went to an IETF meeting for the first time. The IETF is an interesting place; it seems to be about 1/3 maintenance grunt work, 1/3 extending existing stuff, and 1/3 blue sky insanity. I attended mostly because I wanted to see how people would react to TCP BBR, which was being presented there for the first time. (Answer: mostly positively, but with suspicion. It kinda seemed too good to be true.)

Anyway, the IETF meetings contain lots and lots of presentations about IPv6, the thing that was supposed to replace IPv4, which is what the Internet runs on. (Some would say IPv4 is already being replaced; some would say it has already happened.) Along with those presentations about IPv6, there were lots of people who think it's great, the greatest thing ever, and they're pretty sure it will finally catch on Any Day Now, and IPv4 is just a giant pile of hacks that really needs to die so that the Internet can be elegant again.

I thought this would be a great chance to really try to figure out what was going on. Why is IPv6 such a complicated mess compared to IPv4? Wouldn't it be better if it had just been IPv4 with more address bits? But it's not, oh goodness, is it ever not. So I started asking around. Here's what I found.

Buses ruined everything

Once upon a time, there was the telephone network, which used physical circuit switching. Essentially, that meant moving connectors around so that your phone connection was literally just a very long wire ("OSI layer 1"). A "leased line" was a very long wire that you leased from the phone company. You would put bits in one end of the wire, and they'd come out the other end, a fixed amount of time later. You didn't need addresses because there was exactly one machine at each end.

Eventually the phone company optimized that a bit. Time-division multiplexing (TDM) and "virtual circuit switching" was born. The phone company could transparently take the bits at a slower bit rate from multiple lines, group them together with multiplexers and demultiplexers, and let them pass through the middle of the phone system using fewer wires than before. Making that work was a little complicated, but as far as we modem users were concerned, you still put bits in one end and they came out the other end. No addresses needed.

The Internet (not called the Internet at the time) was built on top of this circuit switching concept. You had a bunch of wires that you could put bits into and have them come out the other side. If one computer had two or three interfaces, then it could, if given the right instructions, forward bits from one line to another, and you could do something a lot more efficient than a separate line between each pair of computers. And so IP addresses ("layer 3"), subnets, and routing were born. Even then, with these point-to-point links, you didn't need MAC addresses, because once a packet went into the wire, there was only one place it could come out. You used IP addresses to decide where it should go after that.

Meanwhile, LANs got invented as an alternative. If you wanted to connect computers (or terminals and a mainframe) together at your local site, it was pretty inconvenient to need multiple interfaces, one for each wire to each satellite computer, arranged in a star configuration. To save on electronics, people wanted to have a "bus" network (also known as a "broadcast domain," a name that will be important later) where multiple stations could just be plugged into a single wire, and talk to any other station plugged into the same wire. These were not the same people as the ones building the Internet, so they didn't use IP addresses for this. They all invented their own scheme ("layer 2").

One of the early local bus networks was arcnet, which is dear to my heart (I wrote the first Linux arcnet driver and arcnet poetry way back in the 1990s, long after arcnet was obsolete). Arcnet layer 2 addresses were very simplistic: just 8 bits, set by jumpers or DIP switches on the back of the network card. As the network owner, it was your job to configure the addresses and make sure you didn't have any duplicates, or all heck would ensue. This was kind of a pain, but arcnet networks were usually pretty small, so it was only kind of a pain.

A few years later, ethernet came along and solved that problem once and for all, by using many more bits (48, in fact) in the layer 2 address. That's enough bits that you can assign a different (sharded-sequential) address to every device that has ever been manufactured, and not have any overlaps. And that's exactly what they did! Thus the ethernet MAC address was born.

Various LAN technologies came and went, including one of my favourites, IPX (Internetwork Packet Exchange, though it had nothing to do with the "real" Internet) and Netware, which worked great as long as all the clients and servers were on a single bus network. You never had to configure any addresses, ever. It was beautiful, and reliable, and worked. The golden age of networking, basically.

Of course, someone had to ruin it: big company/university networks. They wanted to have so many computers that sharing 10 Mbps of a single bus network between them all became a huge bottleneck, so they needed a way to have multiple buses, and then interconnect - "internetwork," if you will - those buses together. You're probably thinking, of course! Use the Internet Protocol for that, right? Ha ha, no. The Internet protocol, still not called that, wasn't mature or popular back then, and nobody took it seriously. Netware-over-IPX (and the many other LAN protocols at the time) were serious business, so as serious businesses do, they invented their own thing(s) to extend the already-popular thing, ethernet. Devices on ethernet already had addresses, MAC addresses, which were about the only thing the various LAN protocol people could agree on, so they decided to use ethernet addresses as the keys for their routing mechanisms. (Actually they called it bridging and switching instead of routing.)

The problem with ethernet addresses is they're assigned sequentially at the factory, so they can't be hierarchical. That means the "bridging table" is not as nice as a modern IP routing table, which can talk about the route for a whole subnet at a time. In order to do efficient bridging, you had to remember which network bus each MAC address could be found on. And humans didn't want to configure each of those by hand, so it needed to figure itself out automatically. If you had a complex internetwork of bridges, this could get a little complicated. As I understand it, that's what led to the spanning tree poem, and I think I'll just leave it at that. Poetry is very important in networking.

Anyway, it mostly worked, but it was a bit of a mess, and you got broadcast floods every now and then, and the routes weren't always optimal, and it was pretty much impossible to debug. (You definitely couldn't write something like traceroute for bridging, because none of the tools you need to make it work - such as the ability for an intermediate bridge to even have an address - exist in plain ethernet.)

On the other hand, all these bridges were hardware-optimized. The whole system was invented by hardware people, basically, as a way of fooling the software, which had no idea about multiple buses and bridging between them, into working better on large networks. Hardware bridging means the bridging could go really really fast - as fast as the ethernet could go. Nowadays that doesn't sound very special, but at the time, it was a big deal. Ethernet was 10 Mbps, because you could maybe saturate it by putting a bunch of computers on the network all at once, not because any one computer could saturate 10 Mbps. That was crazy talk.

Anyway, the point is, bridging was a mess, and impossible to debug, but it was fast.

Internet over buses

While all that was happening, those Internet people were getting busy, and were of course not blind to the invention of cool cheap LAN technologies. I think it might have been around this time that the ARPANET got actually renamed to the Internet, but I'm not sure. Let's say it was, because the story is better if I sound confident.

At some point, things progressed from connecting individual Internet computers over point-to-point long distance links, to the desire to connect whole LANs together, over point-to-point links. Basically, you wanted a long-distance bridge.

You might be thinking, hey, no big deal, why not just build a long distance bridge and be done with it? Sounds good, doesn't work. I won't go into the details right now, but basically the problem is congestion control. The deep dark secret of ethernet bridging is that it assumes all your links are about the same speed, and/or completely uncongested, because they have no way to slow down. You just blast data as fast as you can, and expect it to arrive. But when your ethernet is 10 Mbps and your point-to-point link is 0.128 Mbps, that's completely hopeless. Separately, the idea of figuring out your routes by flooding all the links to see which one is right - this is the actual way bridging typically works - is hugely wasteful for slow links. And sub-optimal routing, an annoyance on local networks with low latency and high throughput, is nasty on slow, expensive long-distance links. It just doesn't scale.

Luckily, those Internet people (if it was called the Internet yet) had been working on that exact set of problems. If we could just use Internet stuff to connect ethernet buses together, we'd be in great shape.

And so they designed a "frame format" for Internet packets over ethernet (and arcnet, for that matter, and every other kind of LAN).

And that's when everything started to go wrong.

The first problem that needed solving was that now, when you put an Internet packet onto a wire, it was no longer clear which machine was supposed to "hear" it and maybe forward it along. If multiple Internet routers were on the same ethernet segment, you couldn't have them all picking it up and trying to forward it; that way lies packet storms and routing loops. No, you had to choose which router on the ethernet bus is supposed to pick it up. We can't just use the IP destination field for that, because we're already using that for the final destination, not the router destination. Instead, we identify the desired router using its MAC address in the ethernet frame.

So basically, to set up your local IP routing table, you want to be able to say something like, "send packets to IP address via the router at MAC address 11:22:33:44:55:66." That's the actual thing you want to express. This is important! Your destination is an IP address, but your router is a MAC address. But if you've ever configured a routing table, you might have noticed that nobody writes it like that. Instead, because the writers of your operating system's TCP/IP stack are stubborn, you write something like "send packets to IP address via the router at IP address"

In truth, that really is just complicating things. Now your operating system has to first look up the ethernet address of, find out it's 11:22:33:44:55:66, and finally generate a packet with destination ethernet address 11:22:33:44:55:66 and destination IP address shows up nowhere in the packet; it's just an abstraction at the human level.

To do that pointless intermediate step, you need to add ARP (address resolution protocol), a simple non-IP protocol whose job it is to convert IP addresses to ethernet addresses. It does this by broadcasting to everyone on the local ethernet bus, asking them all to answer if they own that particular IP address. If you have bridges, they all have to forward all the ARP packets to all their interfaces, because they're ethernet broadcast packets, and that's what broadcasting means. On a big, busy ethernet with lots of interconnected LANs, excessive broadcasts start becoming one of your biggest nightmares. It's especially bad on wifi. As time went on, people started making bridges/switches with special hacks to avoid forwarding ARP as far as it's technically supposed to go, to try to cut down on this problem. Some devices (especially wifi access points) just make fake ARP answers to try to help. But doing any of that is a hack, albeit sometimes a necessary hack.

Death by legacy

Time passed. Eventually (and this actually took quite a while), people pretty much stopped using non-IP protocols on ethernet at all. So basically all networks became a physical wire (layer 1), with multiple stations on a bus (layer 2), with multiple buses connected over bridges (gotcha! still layer 2!), and those inter-buses connected over IP routers (layer 3).

After a while, people got tired of manually configuring IP addresses, arcnet style, and wanted them to auto-configure, ethernet style, except it was too late to literally do it ethernet style, because a) the devices had already been manufactured with ethernet addresses, not IP addresses, and b) IP addresses were only 32 bits, which is not enough to just manufacture them forever with no overlaps, and c) just assigning IP addresses sequentially instead of using subnets would bring us back to square one: it would just be ethernet over again, and we already have ethernet.

So that's where bootp and DHCP came from. Those protocols, by the way, are special kinda like ARP is special (except they pretend not to be special, by technically being IP packets). They have to be special, because an IP node has to be able to transmit them before it has an IP address, which is of course impossible, so it just fills the IP headers with essentially nonsense (albeit nonsense specified by an RFC), so the headers might as well have been left out. (You know these "IP" headers are nonsense because the DHCP server has to open a raw socket and fill them in by hand; the kernel IP layer can't do it.) But nobody would feel nice if they were inventing a whole new protocol that wasn't IP, so they pretended it was IP, and then they felt nice. Well, as nice as one can feel when one is inventing DHCP.

Anyway, I digress. The salient detail here is that unlike real IP services, bootp and DHCP need to know about ethernet addresses, because after all, it's their job to hear your ethernet address and assign you an IP address to go with it. They're basically the reverse of ARP, except we can't say that, because there's a protocol called RARP that is literally the reverse of ARP. Actually, RARP worked quite fine and did the same thing as bootp and DHCP while being much simpler, but we don't talk about that.

The point of all this is that ethernet and IP were getting further and further intertwined. They're nowadays almost inseparable. It's hard to imagine a network interface (except ppp0) without a 48-bit MAC address, and it's hard to imagine that network interface working without an IP address. You write your IP routing table using IP addresses, but of course you know you're lying when you name the router by IP address; you're just indirectly saying that you want to route via a MAC address. And you have ARP, which gets bridged but not really, and DHCP, which is an IP packet but is really an ethernet protocol, and so on.

Moreover, we still have both bridging and routing, and they both get more and more complicated as the LANs and the Internet get more and more complicated, respectively. Bridging is still, mostly, hardware based and defined by IEEE, the people who control the ethernet standards. Routing is still, mostly, software based and defined by the IETF, the people who control the Internet standards. Both groups still try to pretend the other group doesn't exist. Network operators basically choose bridging vs routing based on how fast they want it to go and how much they hate configuring DHCP servers, which they really hate very much, which means they use bridging as much as possible and routing when they have to.

In fact, bridging has gotten so completely out of control that people decided to extract the layer 2 bridging decisions out completely to a higher level (with configuration exchanged between bridges using a protocol layered over IP, of course!) so it can be centrally managed. That's called software-defined networking (SDN). It helps a lot, compared to letting your switches and bridges just do whatever they want, but it's also fundamentally silly, because you know what's software defined networking? IP. It is literally and has always been the software-defined network you use for interconnecting networks that have gotten too big. But the problem is, IPv4 was initially too hard to hardware accelerate, and anyway, it didn't get hardware accelerated, and configuring DHCP really is a huge pain, so network operators just learned how to bridge bigger and bigger things. And nowadays big data centers are basically just SDNed, and you might as well not be using IP in the data center at all, because nobody's routing the packets. It's all just one big virtual bus network.

It is, in short, a mess.

Now forget I said all that...

Great story, right? Right. Now pretend none of that happened, and we're back in the early 1990s, when most of that had in fact already happened, but people at the IETF were anyway pretending that it hadn't happened and that the "upcoming" disaster could all be avoided. This is the good part!

There's one thing I forgot to mention in that big long story above: somewhere in that whole chain of events, we completely stopped using bus networks. Ethernet is not actually a bus anymore. It just pretends to be a bus. Basically, we couldn't get ethernet's famous CSMA/CD to keep working as speeds increased, so we went back to the good old star topology. We run bundles of cables from the switch, so that we can run one cable from each station all the way back to the center point. Walls and ceilings and floors are filled with big, thick, expensive bundles of ethernet, because we couldn't figure out how to make buses work well... at layer 1. It's kinda funny actually when you think about it. If you find sad things funny.

In fact, in a bonus fit of insanity, even wifi - the ultimate bus network, right, where literally everybody is sharing the same open-air "bus" - we almost universally use wifi in a mode, called "infrastructure mode," which simulates a giant star topology. If you have two wifi stations connected to the same access point, they don't talk to each other directly, even when they can hear each other just fine. They send a packet to the access point, but addressed to the MAC address of the other node. The access point then bounces it back out to the destination node.

HOLD THE HORSES LET ME JUST REVIEW THAT FOR YOU. There's a little catch there. When node X wants to send to Internet node Z, via IP router Y, via wifi access point A, what does the packet look like? Just to draw a picture, here's what we want to happen:

X -> [wifi] -> A -> [wifi] -> Y -> [internet] -> Z

Z is the IP destination, so obviously the IP destination field has to be Z. Y is the router, which we learned above that we specify by using its ethernet MAC address in the ethernet destination field. But in wifi, X can't just send out a packet to Y, for various reasons (including that they don't know each other's encryption keys). We have to send to A. Where do we put A's address, you might ask?

No problem! 802.11 has a thing called 3-address mode. They add a third ethernet MAC address to every frame, so they can talk about the real ethernet destination, and the intermediate ethernet destination. On top of that, there are bit fields called "to-AP" and "from-AP," which tell you if the packet is going from a station to an AP, or from an AP to a station, respectively. But actually they can both be true at the same time, because that's how you make wifi repeaters (APs send packets to APs).

Speaking of wifi repeaters! If A is a repeater, it has to send back to the base station, B, along the way, which looks like this:

X -> [wifi] -> A -> [wifi-repeater] -> B -> [wifi] -> Y -> [internet] -> Z

X->A uses three-address mode, but A->B has a problem: the ethernet source address is X, and the ethernet destination address is Y, but the packet on the air is actually being sent from A to B; X and Y aren't involved at all. Suffice it to say that there's a thing called 4-address mode, and it works pretty much like you think.

(In 802.11s mesh networks, there's a 6-address mode, and that's about where I gave up trying to understand.)

Avery, I was promised IPv6, and you haven't even mentioned IPv6

Oh, oops. This post went a bit off the rails, didn't it?

Here's the point of the whole thing. The IETF people, when they were thinking about IPv6, saw this mess getting made - and maybe predicted some of the additional mess that would happen, though I doubt they could have predicted SDN and wifi repeater modes - and they said, hey wait a minute, stop right there. We don't need any of this crap! What if instead the world worked like this?

  • No more physical bus networks (already done!)
  • No more layer 2 internetworks (that's what layer 3 is for)
  • No more broadcasts (layer 2 is always point-to-point, so where would you send the broadcast to? replace it with multicast instead)
  • No more MAC addresses (on a point-to-point network, it's obvious who the sender and receiver are, and you can do multicast using IP addresses)
  • No more ARP and DHCP (no MAC addresses, no so mapping IP addresses to MAC addresses)
  • No more complexity in IP headers (so you can hardware accelerate IP routing)
  • No more IP address shortages (so we can go back to routing big subnets again)
  • No more manual IP address configuration except at the core (and there are so many IP addresses that we can recursively hand out subnets down the tree from there)

Imagine that we lived in such a world: wifi repeaters would just be IPv6 routers. So would wifi access points. So would ethernet switches. So would SDN. ARP storms would be gone. "IGMP snooping bridges" would be gone. Bridging loops would be gone. Every routing problem would be traceroute-able. And best of all, we could drop 12 bytes (source/dest ethernet addresses) from every ethernet packet, and 18 bytes (source/dest/AP addresses) from every wifi packet. Sure, IPv6 adds an extra 24 bytes of address (vs IPv4), but you're dropping 12 bytes of ethernet, so the added overhead is only 12 bytes - pretty comparable to using two 64-bit IP addresses but having to keep the ethernet header. The idea that we could someday drop ethernet addresses helped to justify the oversized IPv6 addresses.

It would have been beautiful. Except for one problem: it never happened.

Requiem for a dream

One person at work put it best: "layers are only ever added, never removed."

All this wonderfulness depended on the ability to start over and throw away the legacy cruft we had built up. And that is, unfortunately, pretty much impossible. Even if IPv6 hits 99% penetration, that doesn't mean we'll be rid of IPv4. And if we're not rid of IPv4, we won't be rid of ethernet addresses, or wifi addresses. And if we have to keep the IEEE 802.3 and 802.11 framing standards, we're never going to save those bytes. So we will always need the "IPv6 neighbour discovery" protocol, which is just a more complicated ARP. Even though we no longer have bus networks, we'll always need some kind of simulator for broadcasts, because that's how ARP works. We'll need to keep running a local DHCP server at home so that our obsolete IPv4 light bulbs keep working. We'll keep needing NAT so that our obsolete IPv4 light bulbs can keep reaching the Internet.

And that's not the worst of it. The worst of it is we still need the infinite abomination that is layer 2 bridging, because of one more mistake the IPv6 team forgot to fix. Unfortunately, while they were blue-skying IPv6 back in the 1990s, they neglected to solve the "mobile IP" problem. As I understand it, the idea was to get IPv6 deployed first - it should only take a few years - and then work on it after IPv4 and MAC addresses had been eliminated, at which time it should be much easier to solve, and meanwhile, nobody really has a "mobile IP" device yet anyway. I mean, what would that even mean, like carrying your laptop around and plugging into a series of one ethernet port after another while you ftp a file? Sounds dumb.

The killer app: mobile IP

Of course, with a couple more decades of history behind us, now we know a few use cases for carrying around a computer - your phone - and letting it plug into one ethernet port wireless access point after another. We do it all the time. And with LTE, it even mostly works! With wifi, it works sometimes. Good, right?

Not really, because of the Internet's secret shame: all that stuff only works because of layer 2 bridging. Internet routing can't handle mobility - at all. If you move around on an IP network, your IP address changes, and that breaks any connections you have open.

Corporate wifi networks fake it for you, bridging their whole LAN together at layer 2, so that the giant central DHCP server always hands you the same IP address no matter which corporate wifi access point you join, and then gets your packets to you, with at most a few seconds of confusion while the bridge reconfigures. Those newfangled home wifi systems with multiple extenders/repeaters do the same trick. But if you switch from one wifi network to another as you walk down the street - like if there's a "Public Wifi" service in a series of stores - well, too bad. Each of those gives you a new IP address, and each time your IP address changes, you kill all your connections.

LTE tries even harder. You keep your IP address (usually an IPv6 address in the case of mobile networks), even if you travel miles and miles and hop between numerous cell towers. How? Well... they typically just tunnel all your traffic back to a central location, where it all gets bridged together (albeit with lots of firewalling) into one super-gigantic virtual layer 2 LAN. And your connections keep going. At the expense of a ton of complexity, and a truly embarrassing amount of extra latency, which they would really like to fix, but it's almost impossible.

Making mobile IP actually work1

So okay, this has been a long story, but I managed to extract it from those IETF people eventually. When we got to this point - the problem of mobile IP - I couldn't help but ask. What went wrong? Why can't we make it work?

The answer, it turns out, is surprisingly simple. The great design flaw was in how the famous "4-tuple" (source ip, source port, destination ip, destination port) was defined. We use the 4-tuple to identify a given TCP or UDP session; if a packet has those four fields the same, then it belongs to a given session, and we can deliver it to whatever socket is handling that session. But the 4-tuple crosses two layers: internetwork (layer 3) and transport (layer 4). If, instead, we had identified sessions using only layer 4 data, then mobile IP would have worked perfectly.

Let's do a quick example. X port 1111 is talking to Y port 80, so it sends a packet with 4-tuple (X,1111,Y,80). The response comes back with (Y,80,X,1111), and the kernel delivers it to the socket that generated the original packet. When X sends more packets tagged (X,1111,Y,80), then Y delivers them all to the same server socket, and so on.

Then, if X hops IP addresses, it gets a new name, say Q. Now it'll start sending packets with (Q,1111,Y,80). Y has no idea what that means, and throws it away. Meanwhile, if Y sends packets tagged (Y,80,X,1111), they get lost, because there is no longer an X to receive them.

Imagine now that we tagged sockets without reference to their IP address. For that to work, we'd need much bigger port numbers (which are currently 16 bits). Let's make them, say, 128 or 256 bits, some kind of unique hash.

Now X sends out packets to Y with tag (uuid,80). Note, the packets themselves still contain the (X,Y) addressing information, down at layer 3 - that's how they get routed to the right machine in the first place. But the kernel doesn't use the layer 3 information to decide which socket to deliver to; it just uses the uuid. The destination port (80 in this case) is only needed to initiate a new session, to identify what service you want to connect to, and can be ignored or left out after that.

For the return direction, Y's kernel caches the fact that packets for (uuid) go to IP address X, which is the address it most recently received (uuid) packets from.

Now imagine that X changes addresses to Q. It still sends out packets tagged with (uuid,80), to IP address Y, but now those packets come from address Q. On machine Y, it receives the packet and matches it to the socket associated with (uuid), notes that the packets for that socket are now coming from address Q, and updates its cache. Its return packets can now be sent, tagged as (uuid), back to Q instead of X. Everything works! (Modulo some care to prevent connection hijacking by impostors.2)

There's only one catch: that's not how UDP and TCP work, and it's too late to update them. Updating UDP and TCP would be like updating IPv4 to IPv6; a project that sounded simple, back in the 1990s, but decades later, is less than half accomplished (and the first half was the easy part; the long tail is much harder).

The positive news is we may be able to hack around it with yet another layering violation. If we throw away TCP - it's getting rather old anyway - and instead use QUIC over UDP, then we can just stop using the UDP 4-tuple as a connection identifier at all. Instead, if the UDP port number is the "special mobility layer" port, we unwrap the content, which can be another packet with a proper uuid tag, match it to the right session, and deliver those packets to the right socket.

There's even more good news: the experimental QUIC protocol already, at least in theory, has the right packet structure to work like this. It turns out you need unique session identifiers (keys) anyhow if you want to use stateless packet encryption and authentication, which QUIC does. So, perhaps with not much work, QUIC could support transparent roaming. What a world that would be!

At that point, all we'd have to do is eliminate all remaining UDP and TCP from the Internet, and then we would definitely not need layer 2 bridging anymore, for real this time, and then we could get rid of broadcasts and MAC addresses and SDN and DHCP and all that stuff.

And then the Internet would be elegant again.

1 Edit 2017-08-16: It turns out that nothing in this section requires IPv6. It would work fine with IPv4 and NAT, even roaming across multiple NATs.

2 Edit 2017-08-15: Some people asked what "some care to prevent connection hijacking" might look like. There are various ways to do it, but the simplest would be to do something like the SYN-ACK-SYNACK exchange TCP does at connection startup. If Y just trusts the first packet from the new host Q, then it's too easy for any attacker to take over the X->Y connection by simply sending a packet to Y from anywhere on the Internet. (Although it's a bit hard to guess which 256-bit uuid to fill in.) But if Y sends back a cookie that Q must receive and process and send back to Y, that ensures that Q is at least a man-in-the-middle and not just an outside attacker (which is all TCP would guarantee anyway). If you're using an encrypted protocol (like QUIC), the handshake can also be protected by your session key.

Posted Thu Aug 10 11:32:26 2017 Tags:

I just gave $100 to James Damore’s official fundraiser.

Damore, for any of you who have been hiding under a rock, is the guy who wrote a completely sane and reasonable memorandum, objecting on principled and scientific grounds to the assumptions behind “diversity”.

He’s been fired and is, of course, the target of a full-blown SJW rage-mob.

The full version of the memo is here. Note that much of the negative public discussion seems to have been based on redacted versions from which references and charts were omitted.

Please give generously. Because the thought police must be stopped.

Posted Wed Aug 9 04:00:12 2017 Tags:

Six months ago, I wrote Hey, Democrats! We need you to get your act together!, a plea to the opposition to get its act together.

A month ago, a Democratic activist attempting a mass political assassination shot Steve Scalise through the hip. Today, Gallup’s job creation index at +37 in July—a record high.

In my previous post I stayed away from values arguments about policy and considered only the practical politics of the Democrats’ positioning. I will continue that here.

In brief: Democrats, when you’re in a hole, stop digging!

How has the Democratic party’s self-destruction been pursued since Trump’s election? Let me count some of the ways…

The new party vice-chair, Keith Ellison, has a notorious history of anti-white racism and anti-Semitism, about which the Republicans are now carefully holding fire, is certain to be hung around the party’s neck in the 2018 midterms. A few quotes from his days in the Nation of Islam are all it’s going to take. Anyone who doesn’t expect this to tip the GOP the balance in a couple of flyover-country states is delusional.

At a time when 59% of Americans (including 74% of independent swing voters) favor President Trump’s proposed immigration restrictions, Democrats are doubling down on support for “sanctuary city” laws.

Americans’ Trust in Mass Media Sinks to New Low; in late May, a Republican Congressional candidate who body-slammed a reporter won a special election less than 24 hours later. Yet Democratic reliance on media partisans to make its political case has been increasing rather than decreasing since Election Night, often in bizarre and theatrical ways (cue CNN co-host Kathy Griffin’s display of a mock severed head of the President).

Do you want more Trump? Because this is how you get more Trump.

Dammit, Democrats, your country still needs an opposition that is smarter than this! But every time you temporarily abandon one suicidal obsession (like, say, gun control) you seem to latch onto another, like hamstringing the ICE. News flash: even legal immigrants to the U.S. are overwhelmingly in favor of an illegal-immigration crackdown.

Whether that’s good policy by some abstract technocratic measure is not the point here; the point is that you are choosing to fight Trump on an issue where public opinion is already heavily on his side. You can’t win that kind of fight with him; he’s way too good at making you look like out of touch let-them-eat-cake elitists even when you have a case.

You need to reconnect with the Middle Americans that are on Trump’s train. If the election should have taught you anything, it’s that the way to do that does not go through endless establishment-media tirades and celebrity endorsements and moralistic scolding about the deplorability of anyone in a MAGA hat. Yet this behavior is the lesser half of your post-election mistakes.

The greater half is your embrace of radicals advocating and many cases practicing political violence. BAMN. BLM. Linda Sarsour. Antifa. The voters you lost think that these people and organizations are their enemies, and they’re not wrong, and even if they were wrong the perception is what matters. You can have By Any Means Necessary in your coalition, or you can have the kind of people who attend Rotary meetings in the Midwest. You can’t have both.

Related: Every time Democrats are seen screaming and cursing and acting out in public, Trump wins. It’s no good pointing out that Trump himself is vulgar, boorish, profane, and often infantile in his presentation; his voters think “he fights!” and have already priced in his visible character defects. When you fail to look like the adults in the room, you don’t hurt Trump; instead, you disqualify yourselves from being seen as a better alternative.

But there is a mistake that may be even worse (though subtler) than playing footsie with violent radicals. And that is believing that only your messaging needs to change.

Every time I near a Democrat saying anything equivalent to “if we’d just gotten our message out better…” I wince. No. You didn’t lose because the people of the majority of the states in the Electoral College failed to understand your program; given the spin of a largely Democratic-leaning establishment media, there is no way they can’t have seen its best possible face in endless repetition.

What you have to process is that they did understand…and rejected it. Continuing to believe that you merely suffered from bad messaging is an excuse that will only prevent the real self-examination you need to go through.

I have watched in vain for any sign of that self-examination. I’ve seen no more than occasional flashes of humility from the Democratic leadership, always rapidly sniffed out by a shrill replay of talking points that are anything but humble.

Given the friction costs of substantive change, you’re running out of time before the 2018 midterms. And, as I began this post by noting, Trump has seized the high ground by actually moving on pocketbook issues. You may not think “regulatory relief” is a big deal, but that and the high-profile commitments to in-U.S. manufacturing by outfits like Foxconn matter a lot to an electorate who has seen way too many blighted small towns and deserted malls.

Finally: in my earlier post I noted that you need to banish the words “racism” and “sexism” from your vocabulary, and take a strap to any Democratic partisan who uses the phrase “angry white man”. I observed that these tags are traps that impede your ability to speak or even think in terms Trump’s base won’t reject as demonizing and toxic. Well…in the ensuing six months, it has been easy to identify two more such labels.

Those are “nationalist” (especially in the compound “white nationalist”) and “alt-right”. As I’ve explained before, when you talk about the alt-right, you create the thing you fear. And in order to win against Trump, you cannot repudiate “nationalism” – that won’t fly. not outside the deepest blue of blue-tribe areas. No. To win against Trump, you need to take nationalism away from him..

Posted Mon Aug 7 15:47:12 2017 Tags:

I’m back from vacation – World Boardgaming Championships, where this year I earned laurels in Ticket To Ride and Terra Mystica..

Catching up on some releases I needed to do:

* Open Adventure 1.3: Only minor bugfixes in this one, it’s pretty stable now. We gave 100% coverage in the test suite now, an achievement I’ll probably write about in a future post.

* ascii 1.18: By popular demand, this can now generate a 4×16 as well as 16×4 table, This is especially useful in conjuction with the new -b option to display binary code points.

* Things Every Hacker Once Knew: With new sections on the slow birth of distributed development and the forgotten history of early bitmap displays.

Posted Wed Aug 2 03:06:30 2017 Tags:

A few days ago, I pushed code for button debouncing into libinput, scheduled for libinput 1.9. What is button debouncing you ask? Well, I'm glad you asked, because otherwise typing this blog post would've been a waste of time :)

Over in Utopia, when you press the button on a device, you get a press event from the hardware. When you release said button, you get a release event from the hardware. Together, they form the button click interaction we have come to learn and love over the last couple of decades. Life is generally merry and the sunshine to rainbow to lollipop ratio is good. Meanwhile, over here in the real world, buttons can be quite dodgy, don't always work like they're supposed to, lollipops are unhealthy and boy, have you seen that sunburn the sunshine gave me? One way how buttons may not work is that they can lose contact for a fraction of a second and send release events even though the button is being held down. The device usually detects that the button is still being down in the next hardware cycle (~8ms on most devices) and thus sends another button press.

For us, there are not a lot of hints that this is bad hardware besides the timestamps. It's not possible for a user to really release and press a button within 8ms, so we can take this as a signal for dodgy hardware. But at least that's someting. All we need to do is ignore the release event (and subsequent button event) and only release when the button is released properly. This requires timeouts and delays of the event, something we generally want to avoid unless absolutely necessary. So the behaviour libinput has now is enabled but inactive button debouncing on all devices. We monitor button release and button press timestamps, but otherwise leave the events as-is, so no delays are introduced. Only if a device sends release/press combos with unfeasably short timeouts, activate button debouncing. Once active, we filter all button release events and instead set a timer. Once the timer expires, we send the button release event. But if at any time before then another button press is detected, the scheduled release is discarded, the button press is filtered and no event is sent. Thus, we paper over the release/press combo the hardware gives us and to anyone using libinput, it will look like the button was held down for the whole time.

There's one downside with this approach - the very first button debounce to happen on a device will still trigger an erroneous button release event. It remains to be seen whether this is a problem in real-world scenarios. That's the cost of having it as an auto-enabling feature rather than an explicit configuration option.

If you do have a mouse that suffers from button bouncing, I recommend you try libinput's master branch and file any issues if the debouncing doesn't work as it should. Might as well get any issues fixed before we have a release.

Posted Thu Jul 27 11:52:00 2017 Tags:
An effort to clean up several messes simultaneously. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs
Posted Sun Jul 23 13:37:46 2017 Tags:
News regarding the SUPERCOP benchmarking system, and more recommendations to NIST. #benchmarking #supercop #nist #pqcrypto
Posted Wed Jul 19 18:15:13 2017 Tags:

This might become a new major section in Things Every Hacker Once Knew, but before I merge it I’m putting it out for comment and criticism.

Nowadays we take for granted a public infrastructure of distributed version control and a lot of practices for distributed teamwork that go with it – including development teams that never physically have to meet. But these tools, and awareness of how to use them, were a long time developing. They replace whole layers of earlier practices that were once general but are now half- or entirely forgotten.

The earliest practice I can identify that was directly ancestral was the DECUS tapes. DECUS was the Digital Equipment Corporation User Group, chartered in 1961. One of its principal activities was circulating magnetic tapes of public-domain software shared by DEC users. The early history of these tapes is not well-documented, but the habit was well in place by 1976.

One trace of the DECUS tapes seems to be the README convention. While it entered the Unix world through USENET in the early 1980s, it seems to have spread there from DECUS tapes. The DECUS tapes begat the USENET source-code groups, which were the incubator of the practices that later became “open source”. Unix hackers used to watch for interesting new stuff on comp.sources.unix as automatically as they drank their morning coffee.

The DECUS tapes and the USENET sources groups were more of a publishing channel than a collaboration medium, though. Three pieces were missing to fully support that: version control, patching, and forges.

Version control was born in 1972, though SCCS (Source Code Control System) didn’t escape Bell Labs until 1977. The proprietary licensing of SCCS slowed its uptake; one response was the freely reusable RCS (Revision Control System) in 1982.

The first real step towards across-network collaboration was the patch(1) utility in 1984. The concept seems so obvious now that even hackers who predate patch(1) have trouble remembering what it was like when we only knew how to pass around source-code changes as entire altered files. But that’s how it was.

Even with SCCS/RCS/patch the friction costs of distributed development over the Internet were still so high that some years passed before anyone thought to try it seriously. I have looked for, but not found, examples earlier than nethack. This was a roguelike game launched in 1987. Nethack developers passed around whole files – and later patches – by email, sometimes using SCCS or RCS to manage local copies. footnote[I was an early nethack devteam member. I did not at the time understand how groundbreaking what we were doing actually was.].

Distributed development could not really get going until the third major step in version control. That was CVS (Concurrent Version System) in 1990, the oldest VCS still in wide use at time of writing in 2017. Though obsolete and now half-forgotten, CVS was the first version-control system to become so ubiquitous that every hacker once knew it. CVS, however, had significant design flaws; it fell out of use rapidly when better alternatives became available.

Between around 1989 and the breakout of mass-market Internet in 1993-1994, fast Internet became available enough to hackers that distributed development in the modern style began to become thinkable. The next major steps were not technical changes but cultural ones.

In 1991 Linus Torvalds announced Linux as a distributed collaborative effort. It is now easy to forget that early Linux development used the same patch-by-email method as nethack – there were no public Linux repositories yet. The idea that there ought to be public repositories as a normal practice for major projects wouldn’t really take hold until after I published “The Cathedral and the Bazaar” in 1997. While CatB was influential in promoting distributed development via shared public repositories, the technical weaknesses of CVS were in hindsight probably an important reason this practice did not become established sooner and faster.

The first dedicated software forge was not spun up until 1999. That was SourceForge, still extant today. At first it supported only CVS, but it sped up the adoption of the (greatly superior) Subversion, launched in 2000 by a group of former CVS developers.

Between 2000 and 2005 Subversion became ubiquitous common knowledge. But in 2005 Linus Torvalds invented git, which would fairly rapidly obsolesce all previous version-control systems and is a thing every hacker now knows.

Questions for reviewers:

(1) Can anyone identify a conscious attempt to organize a distributed development team before nethack (1987)?

(2) Can anyone tell me more about the early history of the DECUS tapes?

(3) What other questions should I be asking?

Posted Wed Jul 19 12:02:10 2017 Tags:

The craft of programming is not a thing easily taught. It’s not so much that the low level details like language syntaxes are difficult to convey, it’s more that (as I’ve written before) “the way of the hacker is a posture of mind”.

The posture of mind is more essential than the details. I only know one way to teach that, and it looks like this…

19:51:23 esr | You know, at some point you should build Open Adventure and play it. For that geek heritage experience, like admiring Classical temple friezes.

ianbruene | note to self: play advent

19:53:56 esr | I actually think this should count as (a very minor) part of your training, though I’m not sure I can fully articulate why. Mumble mumble something mimesis and mindset. It was written by two guys with the mindset of great hackers. If playing that game gets you inside their heads even a little bit, you’ll have gained value…

19:55:08 ianbruene | I already had a flag set to fix the non-human-readable save problem someday, if no one else got to it first. Kind of hard to do that without playing at least *some* of the game.

19:55:15 esr | :-)

19:55:29 ianbruene | (non human readable saves irk me)

19:55:35 esr | An excellently chosen exercise, apprentice!

19:57:57 esr | Since you’ve brought it up, let’s think through some of the tradeoffs.

19:58:16 ianbruene |

19:59:25 esr | You are right, in general, to dislike non-eyeball-friendly save formats, especially for small-scale applications.

19:59:54 esr | But: There are two reasons to like the way it’s done now.

20:00:27 esr | Care to guess at them? You can ask me questions about the code context to develop your answer.

20:00:12 ianbruene | anti-cheat being the obvious one

20:00:48 * | ianbruene pulls up advent page

20:00:51 esr | Right – it’s a low barrier, but not a completely useless one.

20:02:02 esr | That is, it hits a nice sweet spot between “too easily editable” and “putting in extra work for something that in principle can always be circumvented no matter what you do”.

20:02:19 esr | Speed bump.

20:02:31 esr | That’s reason #1. What’s #2?

20:02:49 esr | (Don’t overthink it.)

20:03:16 ianbruene | ok, just seeing the first couple functions the comments mention twiddling a few things to prevent savescumming. falls under anti-cheat I assume?

20:03:24 esr | Yes.

20:03:44 esr | No, there’s something else much more basic.

20:04:29 ianbruene | um…. well restore() is just a memcopy……. that seems almost too simple

20:04:41 esr | You’re warm.

20:04:43 ianbruene | also incredibly fragile

20:05:20 esr | I guess you’re close enough.

20:05:36 esr | Reason #2: IT’S *SIMPLE*.

20:06:17 esr | Not a consideration to be despised. Smart programmers do as little work as possible on unimportant things, so they can save brainpower and effort for important things.

20:06:43 ianbruene | am I right in thinking that this is considered ok because 1. very early: the field hadn’t really developed yet

20:07:07 ianbruene | and 2. no need for interop, or devastating if data lost

20:07:21 ianbruene | unlike a certain *cough* MS Word *cough*

20:07:32 esr | Pretty much correct.

20:07:45 esr | However, note 2 subtle points:

20:08:09 ianbruene | ok, *readjusts utility function for memdump fileformat tradeoff*

20:08:20 esr | 1. Format is rather less fragile than you think (I’ll explain that).

20:08:33 ianbruene | I only knew of the ludicrous example of the MS formats previously

20:09:27 esr | 2. The FORTRAN save/restore code was really nasty and complicated. It doesn’t get as simple as it now is unless you have fread/fwrite and a language with structs.

20:10:07 esr | Now, why this isn’t as bad a choice as you think:

20:10:31 ianbruene | (pre-guess: everything is pre-swizzled)

20:11:56 esr | No. It’s because any processor this is likely to run on uses the same set of struct-member aligment rules, what’s called “self-aligned” members. So padding won’t bite you, just endianness and word size.

20:12:54 ianbruene | *blink* oh…. another win from the intervening steamroller of standardization

20:13:17 esr | Precisely, another steamroller win.

(Editor’s note: ianbruene is aware that at the time the original ADVENT was written, greater diversity in processor architectures meant that the structure member alignment rules were more variable and more difficult to predict. So you took a harder portability hit from using a structure dump as a save format then.)

20:12:19 esr | Wait, I want to give you a pointer

20:12:58 esr | Read this, if you haven’t:

20:13:26 ianbruene | read it before, been quite a while (and didn’t have anything to put it into practice)

20:14:22 esr | So, reread with this save format in mind. Go through the reasoning to satisfy yourself about what I just claimed.

20:14:32 esr | It won’t take long.

20:16:06 esr | Now, this does *not* mean a memory dump would be a good format for anything much more complex than this game state. We’re sort of just below the max-complexity threshold here.

20:16:44 esr | And we do get screwed by endianness and word-size differences.

20:17:39 esr | But…let’s get real, how often are these save files going to move between machines? This is not data with a long service lifetime!

20:19:49 esr | OK. Continuation of exercise:

20:20:28 esr | What’s the simplest way you can think of to design an eyeballable save format?

20:21:14 ianbruene | *thinks* (given that I know nothing of the internal structure of advent)

20:22:45 esr | You don’t need to. Look at the structure definition.

20:23:47 * | ianbruene looking up struct

20:28:34 ianbruene | well *one* simple way of doing it would be to do a (I forget what the format is called) var=value\n format, with the save function being a giant printf of doom and the load function being a giant switch of doom.

20:28:44 ianbruene | I don’t think that is *the* simple one though

20:30:06 esr | That sort of thing is generally called a “keyword/value” format. It is the most obvious choice here. Can you think of a simpler one?

20:30:42 esr | (I’m not sure I can.)

20:31:16 ianbruene | ok, we know the struct “shape”, could arrange for all of type X, all of type Y, etc. to be in contiguous spans. Sequence either hardcoded or using a build time generator for the var names. Hmmmmmmmm….. while it has a certain elegance it seems brittle and complex

20:31:25 esr | Yes. It would be that.

20:31:38 esr | Pretty classic example of “too clever by half”, there.

20:33:35 ianbruene | ok, ignore assuming a shape, it would be *possible* for a code generator to simply look at the struct and create a pair of load/save functions from it, using either the internal names, or special comments in the definition

20:33:59 ianbruene | I don’t think the format itself can get any simpler than key=value though

20:34:12 ianbruene | there isn’t much complex structure in the save.

20:34:21 esr | I think you’re right.

20:34:33 ianbruene | it isn’t a bunch of logical blocks of different rooms and characters

20:35:09 ianbruene | if there were there would be useful tradeoffs in how you grouped things

20:35:45 esr | Good! That was a sound insight, there.

20:34:59 esr | Now, you’ve correctly described a way to implement dump as a giant printf.

20:35:27 esr | Do you as yet know enough C to sketch restore?

20:35:39 ianbruene | *thinks*

20:36:24 ianbruene | ok, the template I’m thinking is similar to the packet handling code for mode 6 (python side). but it is more complicated due to C

20:37:29 ianbruene | read until get a token, slice off the token, feed the token into the Switch of Doom

20:37:47 ianbruene | the SoD sets any vars it gets tokens for

20:38:07 ianbruene | if the file is well formed you get all the data you need

20:39:49 esr | Alas, you’ll find actually doing restore in C is a PITA for a couple reasons. One is that you can’t switch on a string’s content, only its start address – C switch only accepts scalars.

20:40:31 ianbruene | grrrr, so you have a big ugly set of str compares in if statements

20:40:37 esr | Indeed, you’re going to write a big fscking if () with a whole bunch of strcmp() guards.

(Editor’s note: There’s another way to do it, driven from iterating through a table of struct initializers, that would be slightly more elegant but no simpler.)

20:40:38 ianbruene | I forgot about that

20:41:29 ianbruene | this is something where your code style becomes *very* important or it will be an ugly, incomprehensible mess

20:41:45 esr | Yes. Now you begin to see why I went to stupid fread/fwrite and stayed there.

20:42:31 ianbruene | and the obvious way to do it in something like python (magic introspection to class elements or dict keys) doesn’t work here

20:43:03 esr | Right. Replacing this binary dump with something clean and textual is not a terrible idea, but really only justifies itself as a finger exercise for a trainee, like playing scales to learn an instrument.

20:43:17 ianbruene | I see

20:43:39 ianbruene | hence why you mentioned in the blog that it was very low priority

20:43:46 esr | Right. The absence of introspection is the other lack in C that makes it a PITA.

20:44:17 esr | And you’ve extracted most of the value of the finger exercise by thinking through the design issues.

20:45:02 ianbruene | when you get to do it introspection is a gigantic win, makes it difficult to remember how bad it is when you don’t get it

20:45:08 esr | Yes.

20:46:05 esr | Those of us who started in LISP learned this early. Took forty years for the rest of the world to catch up, and they’re only getting there now.

20:46:40 ianbruene | I have done only the barest toying with lisp, barely even hello world level

20:47:00 ianbruene | but even that (coupled with some reading of a lisp book) changed the way I thought

20:47:35 ianbruene | plenty of times I’ve hit a snag of “this would be *so much easier* if I could do a lisp macro in python”

20:47:52 esr | Indeed.

20:48:33 ianbruene | incidentally, has GvR used lisp at all? the impression I’ve heard is that he doesn’t like the lispy features?

20:49:11 esr | He doesn’t. Back in the late ’90s I practically had to arm-wrestle him into not killing lambdas.

20:49:45 ianbruene | [insert rant against anyone who thinks lambdas are useless]

20:51:37 esr | I think I might edit this dialog into a blog post. Start it with the Heinlein quote about the ideal university: a log with a teacher on one end and a student on the other.

20:51:51 * | ianbruene grins

The foregoing was transcribed from IRC and lightly edited to fix typos, fill out sentence fragments, and complete 80%-articulated ideas we mutually glarked from context. A few exchanges have been slightly reordered.

Posted Mon Jul 17 04:09:19 2017 Tags: