Avoiding an NP-Complete Problem by Recycling Multics’ Answer

Go can be trapped into an NP-complete problem, that of handing mutually contradictory library dependencies, if we fail to render the problem impossible.

Multics started in a world where such contradictions could exist, but refused to stay there. The Multicians responded by making the problem impossible by construction. This wheel was re-invented in Solaris, and once again in Linux.

The question here is whether preventing NP problems by construction is also an appropriate answer to the equivalent problem in a language, in this case Go.

In the time leading up to proposals for Go 2, we have once again experienced this common problem. To resolve it, there have been several competing proposals. This is a report of how three historical communities addressed the same problem, to provide understanding and insight to the Go community considering specific proposals.

1 Considering a Compatibility Guarantee

One way to understand the problem is task ourselves with re implementing a Go norm in a new context.

Let us ask ourselves how we might provide Go libraries with the same kind of compatibility guarantee as with the language itself. Applications that ran with previous releases will run with new releases. At the same time, libraries are updated and may contain new, improved interfaces.

Sound contradictory? Well, not quite. If I use an old interface that lacks options but don’t need the options, then I don’t care that there is a new version. When I’m writing new programs on the other hand, I’ll use the newest interface, but I don’t care to go back and fix all my older programs just because something new is available.

2 The Solaris Experience

In principle, both are achievable, but how?

This was the problem that we were faced with at (the late, lamented) Sun Microsystems around the time of SunOS 4.1.3. I was on the ABI Stability team, and our shared libraries contained a moderate number of interfaces that had gone through several versions, typically by adding capabilities, fixing bugs or disambiguating the requirements. And we started to find “impossible” problems.

A classic example was memcpy(), which originally was understood to be a pure left-to-right copy from source to destination. That meant copies with overlapping source and destinations were well-defined.

After spirited debate, the c-language definition of memcpy was changed to allow some optimizations that forbade overlapping source and destination. At which point we had a problem. If we supported the optimizations, new programs would be improved, but (some) old ones would be broken.

3 The Multics Approach

Back before Unix, much less Linux or Solaris, the Multics team faced the very same problem. Their answer was that programs should use the interfaces they were written to use. If someone introduced a new version of an interface, that was fine, but they weren’t to discard the old one. Instead, they should provide “updaters” that allowed old interface to call new ones, or “downdaters” to implement new interfaces in terms of older ones.

And, because history always repeat itself, the Linux glibc team encountered the very same problem as we did, and found they needed to implement old-style memcpy in terms of a downdater that calls memmove, which provided the required left-to-right semantics. In SunOS 5 (Solaris 2) we provided both versions, with version control in a “.spec” file, and eventually in the elf libraries as version sections, which Linux uses.

That avoided us from having to play in a NP-complete world. More details are described in a blog post at leaflesslessca.wordpress.com/2017/02/12/dll-hell-and-avoiding-an-np-complete-problem/ and a couple of academic papers by My Smarter Colleagues, Paul Stachour and David J. Brown, cited there.

4 Applicability to Go

Solaris and Linux versioning was strictly based on shared libraries, and could hide the fact that there were several different implementations from programmers and from the program source files. That’s not necessarily the case in Go, which has different aims and mechanisms than C and its friends.

One of the things Go cares about, instead, is stupid excessive effort: paraphrasing Russ Cox and Sam Boyer, this can be “slow compilers, slow programmers, or slow execution”.

  1. Slow version selection – with the problem of version selection being an NP-complete problem, finding a suitable set of versions can take forever at compile- and link-time.
  2. Slow release cycles – maintainers spending time trying to maintain forward compatibility and avoid being tossed in the NP morass.
  3. Slow ecosystem growth, with authors madly corresponding with one another to coordinate versions, and
  4. (courtesy of Sam) slow, unlimited growth of bugs that versioning doesn’t do a bit to address.

None of these are desirable, so how do we stay out of the morass? Well, let’s consider some possible approaches and see if there are obvious advantages for some.

Let’s use memcpy as our example, and imagine you write a program A that uses the newest version, and uses a library, B that requires the older version.

Surprise, program A’s not going to work!

5 Courses of Action

0. The zero’th course is to do nothing.

If we don’t allow more than one version of an interface, then the developer of A has a problem. They need

  • to change their program to use the old memcpy, or
  • to find a replacement B that uses the new memcpy, or
  • to change B to use the new memcpy, or
  • to convince the authors of B to change to use the new memcpy.

The last two run afoul of Sam’s factor #3, slow programmers, with extra work fixing someone else’s bug or cajoling them into fixing it. The second is almost as bad, as it slows development, just not to two unrelated development teams. And the first is evil: you’re coding in terms of a bug, and could then end up depending on it.

1. Allow different versions by “fixing” the bad libraries.

If you “bound” library B with a copy of the old library, then its call to memcpy would be satisfied, but the main program would not “see” any of the old entry points, and could happily call the new memcpy from the new libraries.

A “binder” is also a Multics term, and is little more than a v6-style static linker that can take two shared libraries and create one from them with the entry points from the second made unavailable. This fixes B, but in something like the sense one fixes a cat, and at the expense of the user of B.

This requires the authors of B to clearly indicate the version it requires, and may encourage them to stay current. If they don’t identify versions, then the person using B gets to debug it, chase the authors of B and finally bind themselves a B΄ that will work with their program. Yet another case of #3, slow programmers!

2. Allow different versions in different trees

If the dependency tool was aware of versioning constraints at the time B was built with a version N.M memcpy, then B would be shipped with a constraint. The dependency tool could then arrange to get the correct libraries linked at compile time. This is more mechanized and less painful than doing so manually, but it trips over case #1. You get slow execution because the linker has to walk a tree to avoid the NP morass.

If the versions aren’t encoded as library B is built, then we fall straight into the case of the user of the library having to debug and version it, #3 again.

Incidentally, I’m not sure how one does that with current linkers. Presumably it’s possible in some cases, if Rust indeed does it’s magic via linkage tricks.

3. Require incompatible versions remain in the library

This is the Solaris/glibc approach I described in the leafless blog. The interfaces are the things that have versions, and anyone writing a library for others bumps the version number when an incompatible change happens.

The risk is of #2: the maintainers have to write a new version, test it and not break the old one. To stay out of the NP morass, they have to not throw away the old code.

This doesn’t mean that every bug-fix is a new version, only cases where the new interface has the same structure but a new behavior that is not correct for some previous use case. We expect a structural change to be an incompatible change, but we don’t expect a bug fix to be incompatible. On good days, bug fixes just improve the behavior of the interface, or add a new use case to it. Only where someone is depending on the bug must we mark the change incompatible.

And, as I might have mentioned before, depending on bugs is evil.

5. Force the library maintainers to stay current

A strange version of “do nothing” is to make the library authors do all the work. If a new version of memcpy comes out, the whole world has a flag-day as they stop work and go back to integrate memcpy every place they ever used it. That will be the worst kind of cause for slow release cycles, problem #2.

And some folks won’t know, and downstream applications will crash when they don’t fix their brand new bug. This is a relative of Sam’s #4, in that bugs not related to versioning itself force extra work to avoid versioning.

As an aside, “flag days” were one of the things that made me version-aware, and Edsel Adap and I did the full Multics version/updater/downdater process between two parts of a program suite we were working on. That’s one of the reason’s I’m enthusiastic about it: it saved me time in a constantly-late project.

Other Considerations

This is not a complete proposal, but only an experience report. Open questions include:

6.1 Updating

This approach does not require one to update after encountering a case where you need to use an old interface. In principle, someone could leave a version statement unchanged forever and accumulate unlimited technical debt. We hope people don’t do that, but this proposal doesn’t do anything to avoid it.

6.2 Notation

We will need a notation and config-file similar to the other versioning proposals. I have no particular suggestions, but I do find the Go confg-file proposals substantially nicer than the old Solaris notation. I suspect we only need a format for a non-default interface.

6.3 Vendoring

There is an open question here: do we require keeping vendoring, for libraries that aren’t semantically versioned, that are ill-maintained, or that need to be forked and maintained?

6.4 Library maintenance improvement

There is a pleasant effect for library maintainers (me!) here. Instead of releasing a whole new library, update the version number, write a new interface, and mark the old interface with the old version. To avoid code-bloat and cut-and-paste, write updaters or downdaters. Respectively, take a call to the old interface and map it to the new, or take a call to the new interface and map it to the old, whichever produces better code.

6.5 Pushback

As this changes people’s basic working assumptions, we might well see pushback from teams who imagine they need not provide backwards of forwards compatibility. I suspect this proposal might require a significant buy-in from the core library maintainers. Dep, and specifically vgo, only require convincing the community to use semantic versioning.

7 Conclusions

My own experience in using versioned interfaces were as a library designer and maintainer [Collier-Brown]. The first time Edsel Adap and I didn’t have to have a flag-day because one of our multiple back ends needed an extra parameter paid for the extra discussion about how to do interface versioning in an application. That we avoided code duplication and parallel maintenance was a bonus.

From both historical observation and personal experience, I found it a desirable approach.

I urge the Go community to consider it as a way to “strength reduce” an intractable problem to a manageable one, by transforming it into a solved problem in computer science


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s