Libdill: Structured Concurrency for C (2016) | Hacker News Reader

Libdill: Structured Concurrency for C (2016)

libdill.org

232 pointsjgrahamc50 comments

Ok, I'll chime in here since all the comments are missing the point.

If you are excited by golang-style in C, then Mr Sustrik's libmill is for you http://libmill.org/tutorial.html

LibDill is a thin experiment "above" of libmill. The main problem it tries to solve is "cancellations". For the uninitiated, in normal programming languages there is no way to cancel/interrupt a tread/coroutine from outside. Look at the mess in pthread_cancel(3) [1]. In golang as well, there is no way to cancel a coroutine.

Why this is important? Well, read Mr Sustrik's notes [2]. But basically - imagine you want to define the time limit for a completion of some task. Or - imagine what should happen if a HTTP request comes, initiates some actions (SQL quieries?) and then disconnects. Normal programming languages have NO way of expressing that - "client went away, stop processing its sql queries".

Libdill is an attempt to solve this. I must admit, I'm not fully on board with the "structured concurrency" train of thought [3] , but the whole prospect of defining semantics of killing/cancelling coroutines is absolutely amazing.

Also, review the golang "context" mess, which AFAIU tries to work around the same problem. [4]

[1] http://man7.org/linux/man-pages/man3/pthread_cancel.3.html [2] http://250bpm.com/blog:71 [3] http://libdill.org/structured-concurrency.html [4] https://golang.org/pkg/context

Author here. Thanks for the nice summary. You've expressed it better then I would.

I am not 100% sure about the structured concurrency concept myself, but comparing it to structured programming feels reassuring. Basically, a tree structure (whether a syntactic tree or the tree of running coroutines) is probably the most complex way to structuring stuff that's still tractable by a human being. Once you go beyond that, you'll eventually get lost. Thus, tools enforcing a tree-like structure are likely to be helpful to keep the program maintainable.

I like the idea of structured tree-like concurrency, fits my brains.

About your API though.

Why is there a load of inet/ip/socket functions, shouldn't they be in a separate lib? Why is the opposite of the fn int go(expr) the fn int hclose(int) and not the fn int stop(int) or something like it. open/close – go/stop – and so on …

The socket functions were once in a separate library but it's just easier to use like this. Linking with 1 library, not having to care about version mismatches etc.

My recommendation would be to just not use the socket functions and link with the library stitically. That way the unused code will be discarded.

As for hclose() that was just mimicking the POSIX close() function.

Gotcha. Okay.

Not sure why don't you like go's context model. It works pretty well in our production system. I can see people would like to pass the context implicitly. But I don't have a strong opinion. Explicitness is not that bad.

Go context is a step in the very right direction, but we have not yet the destination. First there is legacy libraries that do not implement it. Second even system-level support misses pieces. For an example, try to cancel a read from a pile using it.

Go's context is fine to signal cancellation, but it lacks a way to wait for that cancellation to complete gracefully. And the fact that it is also an arbitrary bag of values is concerning. It worries me that it started "polluting" the stdlib's API without solving those issues first. Dave Cheney wrote a good article about it: https://dave.cheney.net/2017/08/20/context-isnt-for-cancella...

Context is problematic because it infects everything. If a function gains context support, every call to it has to be updated, and if you're going to do it right (and not just use context.Background()), every function calling those functions need to be updated, and so on. And the context has to be passed downwards, too. It's turtles all the way up and down.

There's been talk of adding context to io.Reader and io.Writer, which would of course affect pretty much every single Go codebase. For backwards compatibility/convenience you therefore see a lot of APIs with complementary functions Foo and FooCtx, one which takes a context and one that doesn't. That's awkward, and even less elegant when interfaces are involved.

And the network packages (sockets, etc.), of course, have a parallel, non-complementary mechanism to provide timeouts and cancelation that doesn't use contexts. (The key/value pair context stuff is also unfortunate, in my opinion. It's not typesafe, and results in awkward APIs.)

All of this happened because goroutines, as designed, cannot be forcibly terminated. I don't know what the better solution is. I'm not sure why the runtime cannot provoke a panic at the next context switch, but I bet there's a good technical reason. It's unfortunate.

But it's not unreasonable that a large part of any codebase needs "contexts", and so if everyone wants it, why not make it mandatory? Make it an implicit argument threaded through every function call, a bit like "this" in languages such as C++ and Java. The compiler could optimize it away from those codepaths that are guaranteed not to need it. Go has a lot of built-in generic magic, adding some global helpers to set a scope's context wouldn't be too bad.

The other route is to imitate Erlang's processes, which have their own heap, and so killing a process doesn't leave cruft behind. Given how goroutines are allowed to share memory, that's not likely to happen.

I see. Now I see a strong point of favoring implicitly passing the context - attaching the context to a go routine local variable (no such thing yet), so the aspect of context passing can be decoupled. Of course for some logic we probably still want to do some explicit context stitching, but that won't pollute most of interfaces. Would that address your concern?

We use D fibers. When we want to cancel a fiber we throw an exception at it. When it next wakes up, it'll throw (much like sending an exception to a Python generator) -- which will make sure RAII cleanups take place and are not missed.

Getting that right at the implementation level is quite hard; it also requires support at the OS level that isn't always there (e.g. interrupting a blocking system call).

Then avoid blocking system calls.

When you can't, defer them to a thread that can be ignored.

That's a huge footgun in an environment where blocking calls are the default way to get almost anything done, and some calls cannot be made non-blocking.

True, but we don't have much trouble with it though. We don't directly call syscalls but use our own wrappers that take care of this for us.

Sorry for the late reply, but I just saw this reply. Can you share who "we" are? I'm always interested in new practical systems for concurrency.

>There is currently no support for Windows. Cygwin is very broken. It doesn't support AF_UNIX properly, and so no further development will be done for this platform.

Boy do I have good news for whoever wrote this:

https://blogs.msdn.microsoft.com/commandline/2017/12/19/af_u...

Doesn't sound great if a coroutine library has resorted to passing messages across sockets. I was expecting something that implemented multiple stacks and some abstraction of some synchronization.

Looking at the source, AF_UNIX is used only for IPC and in DNS support, which is sensible.

It appears to do that: https://github.com/sustrik/libdill/blob/master/stack.c

Correct. It does that. The IPC, on the other hand, is there for you to use if you want to talk to other processes on the same machine.

I really liked the Linda concept for concurrency but it doesn't seem to have caught on in general. It isn't the same as what is being presented here but it side steps the threads issues, the multiple cpu issues, all that falls out for free. Seemed pretty cool and I suppose you could layer on cancellations (but I suspect it would be a mess like pthread_cancel()).

https://en.wikipedia.org/wiki/Linda_(coordination_language)

http://linuxtuples.sourceforge.net/

Anyone else like that stuff? Or have any insight why it isn't more widely used? Maybe it's because it was a commercial thing?

I was confused -- how can a library add a keyword like "coroutine" to C. It didn't look like macros were powerful enough to do that (I expected to at least some context having to be passed to the worker, or so).

It turns out that a coroutine is just a function that the compiler should not inline: https://github.com/sustrik/libmill/blob/master/libmill.h#L24...

Yes, it's just a normal function. What go() macro does is that it switches the stack, then lets compiler-generated code put the args of the function at the top of the new stack. Obviously, if the function was inlined, the above would not work.

The fact that this is all on one cpu seems like a problem, does it not?

Does someone have a mental model of how to take advantage of multiple cpus without creating a mess? If so, can you explain it like I'm 5 (or more like I'm 55 and tired)?

Yes. Either use threadsafe queues/ringbuffers to transfer data between threads. Or triple-buffer it and swap buffers in a threadsafe manner. Those are the best approaches.

Don't start a thread per work item. Start worker threads and distribute work among them. Never ever block a GUI thread.

Always know which thread works on which data structures and don't even make more variables accessible in your worker threads. Keep the variables multiple threads can access to an absolute minimum and make sure access is always protected by a mutex.

If you repect these rules, threading is safe and fun.

I think the environment is a bit different now than it was once.

You typically have a cluster of machines, so you have to be able to run multiple instances of your application simultaneously to use all the processing power. And once you can run mutliple instances of the application in parallel you can as well run 16 instances of it on a 16-core box.

The upside is that you don't have two levels of granularity (threads, machines) but only a single one (processes) which makes both the coding and the ops as well as stuff like capacity planning much easier.

Even absent the cluster of machines I found this to be very useful. Several years ago, I would use zeromq (thank you, btw) for communication and if the socket overhead was found to be an issue, I would merge two processes and switch from tcp:// to inproc://. Many "corrupt the world" type bugs are isolated from each other by processes, and it made it very hard to accidentally share state (the file system of course is a giant hunk of share state, but you very rarely accidentally write to a file).

Message passing without mutable shared state seems to be the least messy way. There are a lot of useful concurrent patterns that can be represented this way, and it is much more tractable than having to manage mutual exclusion manually.

Now different tools work differently for this. If you use multiprocessing, then you have no implicit shared state (you can use the filesystem or shm &c. to share state, but not much is shared by default). Clojure e.g. defaults to no mutability, so you can share state safely by default.

That covers concurrency. For parallelism, there are some useful structures to. In Common Lisp, I usually write a program single-threaded, then I profile, and add use lparallel[1] to parallelize the slow part. 99% of the time the slow part is a loop, so making it parallel is fairly straightforward. If it's a series of possibly interdependent calculations, then the calculations can usually be represented as a tree, and lparallel has a tool for that as well.

There is absolutely nothing lisp-specific in lparallel, any language with first-class functions and some form of thread-local variables could implement all that it does. It's not a silver bullet but it does solve the "My cores stopped getting faster, but I have more cores now" problem about 80% of the time.

1: https://lparallel.org/

Probably because people get taught how to use low level primitives like mutexes and then proceed to have shared mutable state (aka two threads write to one memory location). For the vast majority of applications the complexity of shared mutable state isn't worth it. They should instead restrict themselves to only having one thread per memory location that is allowed to write to it.

For 99% of applications that means you take your favourite threadsafe queue implementation for your specific language and launch threads and only communicate this way. The messages should preferably be immutable, copies or at the very least marked readonly via const if copying is too expensive.

I'd recommend you to take a look at Erlang.

Also remember that there is no magic pixie dust. Functional programming languages are not inherently better than non functional programming languages at concurrency and parallelism. They merely leverage the "no multiple writer" principle by default. Immutable data is threadsafe primarily because it's guaranteed that there is only a single writer.

I took a peek at the source briefly. There is a lot more going on than I was expecting and was pleasantly surprised. I was expecting to find a simple wrapper around setjmp/longjmp, but this is much more. Kudos.

> coroutine void worker(const char *text) {

At first I read 'goroutine' and thought something is wrong with my mind and that I have coded too much Go. But then I saw this:

> go(worker("Hello!"));

Now I am pretty sure someone got inspired by Golang ;-) Nice to see some backporting of Go features to C.

Note: That doesn't mean that Go is the only language that supports easy concurrent patterns, but that the creators of Go wanted to improve C and while not everybody agrees that all they have done are improvements, making concurrency easier most certainly is one.

I think it's fair to say that Go was hardly the first language to implement the concept of coroutines[1]. Probably the only merit of Go here is the short and convenient name of the 'run' method.

[1] https://en.wikipedia.org/wiki/Coroutine#Implementations

    > libmill was a project that aimed to copy Go's
    > concurrency model to C 1:1 [...]

    > libdill is a follow-up project that experiments with
    > structured concurrency and diverges from the Go model.

http://libdill.org/documentation.html

I would say the main advantage is being able to pass couroutine arguments as if it was a simple function. In other coroutine implementations in C (e.g. libtask) you have to make a struct containing all the args and pass that to the run function.

libmill, the pre-cursor to libdill, was directly inspired by an implementation of nanomsg written in go (called mango I believe). Martin had struggled with the state machine approach he had been using and the coroutine approach of golang was a lot easier to reason about in practice.

libdill was a development on libmill in two main ways: it was more idiomatically C and it supports structured concurrency. The latter is, in my opinion, very interesting. Martin has a blog post on it [0].

BTW I've got all this from following the nanomsg threads and reading Martin's blog. I'm not an active participant, so I may have some details wrong, but I think it's fairly accurate.

[0] http://250bpm.com/blog:71

I'll add a link to the (to my mind) canonical articulation of why coroutines are superior to state machines: https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

I'll also add a shameless plug to my recent 'port' of this essay for a VM with first-class continuation support: http://akkartik.name/coroutines-in-mu

Very nice!! I look forward to reading through all the structured concurrency stuff later.

so what is this different from pthread? how can I decide to pick one of them?

the new C11 has thread built-in but not used widely yet.

I read that NodeJS is written in C with the same concept in its core - asynchronous on one core (thread) with interruptions. How does it compare to libdill?

Node runs on top of libuv. https://nikhilm.github.io/uvbook/basics.html#hello-world

So it looks like libuv could use libdill, right?

Could have, possibly, but makes no sense at all to retrofit libuv with libdill at this point

Sure, I understand. Was just curious about how they both relate, and now I get it.

Shameless(-ish) plug: https://github.com/piscisaureus/wepoll is not a fat abstraction layer but it could help with windows support.

Libuv supports windows and in some ways only exists because windows support is needed; on Unix/Linux where Node started, libev was sufficient; libuv was created to facilitate the windows port of node - though it is now standing in its own right.

I know - I am one of the authors of libuv. However libuv is pretty big and imposes its own asynchronous i/o model onto your application.

Later I discovered that it is possible to do efficient epoll emulation on windows so then I wrote wepoll. With it you can just stick to the good ol' epoll/kqueue model and still support windows.

How does it work? It's not obvious how epoll could be built on top of IOCP.

It uses an ioctl that boils down to 'an overlapped version of poll()'. So the call doesn't block - instead when an event like POLLIN or POLLOUT happens, a completion is posted to the completion port.

Call this overlapped-poll function on every monitored socket individually so you don't inherit poll()s scalability problems.

See https://github.com/piscisaureus/wepoll/blob/437fb2f24ce197b4...

This is as much of an explanation I can type on my phone - I'll add more detail to the wepoll readme later.

> So it looks like libuv could use libdill, right?

libuv, has the follow (iirc) genealogy :

        libevent -> libev -> libuv

like its predecessors (with the exception of libev i think) it has grown to be quite large, but its core is still centered on the concept of an event loop. the event-loop itself is hidden, and 'user' code interacts with it via callback event handlers.

given this context, i still don't quite understand how/where libdill might play a role here ?

fwiw, almost all of these event-processing libraries, supports multiple event loops, and thus an event loop is a first class citizen within the library, and implement functions for creating/destroying/starting/stopping loops. multiple event loops find their uses specifically in the context of multi-threaded servers for example.

Reply on news.ycombinator.com