Triple buffer synchronization primitive


#1

So, I’ve just finished my first nontrivial Rust project by implementing a triple buffer. This is a nonblocking thread synchronization primitive originating from the realm of computer graphics, which is suitable for situations where…

  • There is a single producer thread and a single consumer thread
  • The producer wants to frequently update a shared data value
  • The consumer wants to be able to read the latest produced value at any time

The current interface looks like this:

// Create a triple buffer of any Clone type:
let buf = TripleBuffer::new(0);

// Split it into an input and output interface, to be respectively sent to
// the producer thread and the consumer thread:
let (mut buf_input, mut buf_output) = buf.split();

// The producer can move a value into the buffer at any time
buf_input.write(42);

// The consumer can access the latest value from the producer at any time
let latest_value_ref = buf_output.read();
assert_eq!(*latest_value_ref, 42);

If anyone’s interested, you can have a look at https://github.com/HadrienG2/triple-buffer for some code and additional discussion. The code is currently lacking a license, because I envision submitting it to a synchronization library (see below).

I would be very much interested in any comment on how to improve the quality of this code and make it more idiomatic. On my side, I would have one question: can anyone suggest me some popular libraries of Rust synchronization primitives that I could submit this to?


Is there a way to align data on a cache line boundary?
#2

Here are a couple updates:

  • The README has been greatly improved. Comparison with other synchronization primitives has been cleaned up and expanded, and a section on testing and benchmarking has been added.
  • Module structure and documentation has been improved
  • This is is now a library rather than a binary project, the way things should be :slight_smile:

#3

Without going into the code: why do you want to submit to a ‘bigger’ crate? Why not make your own crate?

Triple buffering, with what limited things I know about it, sounds like a very useful primitive on its own. That’s sort of the definition of “would make a good crate”.

As for good libraries to investigate: Piston
It is one of the go-to libraries for game-dev in Rust. Which sounds like a good fit for a graphics synchronization primitive.

There are also other more “pure” sync libs, but I am not so familiar there.


#4

Well, maybe making it an isolated crate would be the right solution. I’m not familiar enough with the Rust ecosystem to decide. From my point of view, the benefits of contributing to an existing crate instead of making my own would be…

  • Better visibility for potential users
  • Less dependencies for users who care about that

I do not think Piston would be the right choice here, because although I shamelessly stole the idea of triple buffering from computer graphics, I think it has applications beyond this area and I would like to actively push people to consider using it in non-graphics settings.

For example, one application which I’m thinking about (and which will probably become my next library project) is asynchronous operation monitoring: a server, which is carrying out work for a client, periodically updates some asynchronous operation status, which the client can check for progress, errors, and so on.

Note that this is an example of “push” asynchronous communication, rather than the “pull” communication approach used by Tokio & futures-rs. Compared to “pull” communication, “push” communication wastes more bandwidth (the server sends some updates which the client will never read) and prevents some useful optimizations (like automatically eliminating middlemen in message passing), but can achieve much lower latencies (in the best case, the information is there right when the client looks for it, whereas in the pull model the client needs to send a request, then the server needs to process it, and then the server needs to reply).


#5

I think that the nature of rust and cargo make the option of standalone crate a better one.

I sympathize with your motivations of better visibility for other users, but the reduced dependencies really shouldn’t be a factor.

I’d encourage you to publish trible_bufffer as a standalone crate, and solicit feedback from the owners of crates that could benefit from using it to see whether there is interest, and if so, whether the API is appropriate for their general consumption.

If it is useful, it will be used as a transitive dependency far more than if it were bundled in a single larger crate.


#6

Alright, I will trust you on this one :slight_smile:

And… we’re… live! https://crates.io/crates/triple_buffer


#7

Congratulations on your first (?) Crate :slight_smile:


#8

This is really neat, but unfortunately the license chosen will severely restrict it’s utility. Have you considered using the same license as rust? If you do not wish to do so, I understand, but would kindly ask you to reconsider.


#9

In general, I tend to license the code that I develop during my spare time under GPL, because that’s my way of stating that I do not work for free. You want to reuse some code that I wrote? I’m glad, but I would like to ask you to contribute some code back to the community in return. In this way, I encourage people to release more code as open-source, which benefits everyone in the end.

Can you be more specific about situations where you would envision this license being limiting?


#10

Check the license of any projects that might make sense to use triple_buffer, such as Piston.

If those projects are licensed less restrictively (e.g. MIT/Apache2), then there is very little chance that they would use a LGPL library, and no chance of using a GPL one.

I’m not aware of any substantial ecosystem of GPL code in Rust today, so the potential for adoption is quite limited at present.

Also, if you do want your own work to be adopted by existing Rust projects, it’s worth reviewing the licenses and compatibility of the ecosystem as a whole. Check out crate.io license stats (scroll down for one from less than a year ago).

There is a more than 10 to 1 ratio of MIT and/or Apache projects to GPL/LGPL. I’m not casting a moral judgement (you are absolutely free to license your code any way you would like), but as a practical matter, it will be a major barrier to adoption.


#11

I see. I think I could improve upon this situation in two different ways:

  • Relicense under LGPL for now, since that is a better compromise in an ecosystem with little GPL-licensed code, which as you pointed out seems to be the case for Rust currently.
  • Provide a commercial option for permissive licensing, aka “pay me for my work and I’ll accomodate your desire not to share code”.

A version of the crate with these licensing adjustments is now live on Github and crates.io.

As for the kind of people, which you referred to, who write BSD/Apache/MIT-licensed code but wouldn’t link with LGPL-licensed code even though the license allows them to, I don’t think that’s something I should worry about.

Software extremists, including licensing ones, will always end up rewriting every piece of code that they rely on anyhow. Examples abound in both the GPL and BSD communities. So there is no point in trying to write shared libraries for this kind of audience.


#13

It depends what you mean by “allows them to”. In the case of your choice of license, LGPL v3.0, it’s ambiguous whether there is any permissible way to release Rust applications that link against LGPL libraries short of including full source code, and even if there is, there are other problems.

The first potential problem is that (like C++) Rust always ‘inlines’ generic code into whichever client crate makes it fully concrete (i.e. chooses values for all the type parameters). In this case, it would not be possible to relink against modified versions (as the LGPL normally requires), so you would have to rely on the header file clause:

  1. Object Code Incorporating Material from Library Header Files.

The object code form of an Application may incorporate material from a header file that is part of the Library. You may convey such object code under terms of your choice, provided that, if the incorporated material is not limited to numerical parameters, data structure layouts and accessors, or small macros, inline functions and templates (ten or fewer lines in length), you do both of the following:

a) Give prominent notice with each copy of the object code that the Library is used in it and that the Library and its use are covered by this License.
b) Accompany the object code with a copy of the GNU GPL and this license document.

But of course, Rust does not have literal “header files”. You would have to make an inference that for the purposes of Rust code, “material from a header file” means anything that would have to go in a header file in C or C++, including all generic code as well as functions marked #[inline]. But it’s unclear to me whether such an inference would be legally justified.

Any non-generic code still has to follow the normal requirements:

d) Do one of the following:

    1. Convey the Minimal Corresponding Source under the terms of this License, and the Corresponding Application Code in a form suitable for, and under terms that permit, the user to recombine or relink the Application with a modified version of the Linked Version to produce a modified Combined Work, in the manner specified by section 6 of the GNU GPL for conveying Corresponding Source.
    1. Use a suitable shared library mechanism for linking with the Library. A suitable mechanism is one that (a) uses at run time a copy of the Library already present on the user’s computer system, and (b) will operate properly with a modified version of the Library that is interface-compatible with the Linked Version.
  1. would only be possible by manual hacking around with object files. 1) is easier, since Rust can compile crates as dylibs … although this is not particularly well supported (issues with rpaths) and prevents the output from being a fully static binary (which is otherwise possible on Linux). But substituting a modified dylib only works if the mangled symbol names are the same. Currently, mangled names depend on absolute paths on the build machine. Luckily, it seems like that will be fixed soon… though even then, since there is no ABI stability guarantee, you’d have to compile the modified library version with the same version of rustc as the original. Which isn’t so bad, except that it means as an application distributor, you have to remember to document which rustc version you use - which is possible but annoying.

Once you’ve gotten past the Rust-specific issues, you’re left with the usual [L]GPLv3 requirements:

  • The LGPL requires “terms[] that, taken together, effectively do not restrict modification of the portions of the Library contained in the Combined Work and reverse engineering for debugging such modifications”. In the FSF’s opinion, this precludes distribution on Apple’s App Stores; in my opinion, it also precludes distribution on Google Play (but nobody seems to have noticed). If you think that iOS is evil, that’s your right, but obviously there are a lot of people interested in writing iOS apps.

  • It also inherits the GPLv3’s requirement for “installation information”, which prohibits use in locked-down systems (somewhat more sympathetic but still a restriction).

  • As well as the patent clauses, some of which arguably apply to the entire program, not just the library.

  • The last two also count as “additional restrictions” for the purpose of the GPLv2, so it is not permissible to link the library into GPLv2 programs.

All of these restrictions can be justified in one way or another, but at the least they’re a bit much for a few hundred lines of code…


#14

In general, I tend to license the code that I develop during my spare time under GPL, because that’s my way of stating that I do not work for free. You want to reuse some code that I wrote? I’m glad, but I would like to ask you to contribute some code back to the community in return. In this way, I encourage people to release more code as open-source, which benefits everyone in the end.

I dislike arguing over licensing since there are usually strong, personal reasons for making a particular choice, and the other respondents have pointed out the difficulties that any strong, copyleft license component will face in adoption.

My personal philosophy is that I contribute to every community under whatever license that community has generally adopted. However, I will simply leave you with a few things to consider:

  • Which is of greater potential value; a personal, commercial interest in code that has been written or the potential growth of the rust community? Every crate, snippet, etc. provided for use by the general rust community contributes to its overall adoption and growth.

  • The implication here that a specific license is required to ensure contribution back to the community overlooks the fact that many people have and do contribute to the overall rust community without a license that requires them to do so. Whether their contributions are to the rust compiler itself, writing documentation, community interactions, testing, or contributing to other community crates, they are contributing to the overall adoption and growth of the rust community.

In the end, it is your personal decision, and I will respect that, so I have nothing further to offer on this matter. I greatly appreciate you taking the time to carefully and thoughtfully consider your contributions to the rust community.


#15

@comex: I am unfortunately not passionate enough about legal matters to give your post the level of detailed reply that it deserves. So I’ll only be able to provide a minimal reply to some of your points:

  • If you are sure that the current GPL wording is incompatible with monomorphized generics or the Rust source file/library model, I think that this is a matter that the FSF lawyers would be happy to hear about, and that they could be convinced to adjust the language in a manner that fixes this for (L)GPLv4. Do get in touch with them if you can find some time/willingness to do so.
  • Regarding the Apple/Google app stores… I really think it’s their mess to fix. I mean, creating a software repository with distribution terms that are incompatible with some of the most popular software/library licenses of your times is incredibly short-sighted, and one should not let them get away with throwing their hands up in the air and asking us developers to work around their own mistakes. I don’t see Debian, SUSE and Redhat whining all the time about how difficult it is to distribute GPL software, even though they have maintained for decades software repositories comparable in size to Apple’s and Google’s… and arguably with a much better (useful stuff) / (fart app) ratio!

#16

@binarycrusader: To be frank, I also dislike arguing over licensing. To me, that’s an extremely uninteresting legal technicality, and I would much rather be arguing about matters of higher interest to me such as lock-free algorithms, parallelism, and asynchronous IO. In the end, I’m really a developer, not a lawyer…

That being said, here are tentative replies to both of your points:

  • In my view, the use of copyleft licenses should not significantly hamper the growth of the Rust community. Many of the key pillars of the Linux ecosystem are GPL- or LGPL-licensed, and that didn’t prevent that ecosystem from being enormously successful. In this respect, I think that you and others largely overestimate the drawbacks of copyleft…
  • …while underestimating its benefits. Sure, sometimes when faced with a permissive license people will do the right thing. But if you’re an optimistic programmer who assumes that everything will always go in the best possible direction, you write your code in something like PHP or Javascript, not Rust. “Pessimistic” tools like strong static typing, Rust’s borrow checker and copyleft software licenses are built because we know that humans are highly imperfect, things will go wrong, and we want to have safety nets around when they do.

Note that here, I’m focusing only on the concept of copyleft, rather that on its unpleasant legalese implementation that is the (L)GPL. If, as comex suggested, there are issues with this implementation in the context of Rust, I believe that this is an issue that needs fixing. I don’t care about it enough to fix it myself, but I strongly encourage anyone who feels strongly enough about legal matters to do so.


#17

If you want a license that ensures that all your code remains open source, but without preventing people from being able to create their own closed source applications, you may be interested in the Mozilla Public License.


#18

@retep998: Thanks! It’s been on my radar as well. I think I’ll stick with a Qt-like LGPL + commercial dual license model for now, as it seems to strike the best balance between third party usability and my personal moral objectives, but I’ll keep that one in mind for future projects.


#19

The discussion above is why I :heart: this community
Respectful of each other’s preferences, detailed technical/legal knowledge is exchanged, and a friendly conclusion that all involved parties have legitimate concerns that lead to different-but-valid decisions in the trade-offs.

Without calling names, I regularly read mailinglists and forums where a licensing discussion would have involved at least one slur or deprecating remark before post three, and at least three dogmatic flames.
After my experiences with the delightful Rust community, I’m increasingly wondering why I spend my time on those other sites… :heart_exclamation:

P.s. sorry for not contributing any technical content to this otherwise excellent thread; I hope the warm-fuzzy-feeling I intended to share makes up for the noise my post added.


#20

Just as a quick update, I figured out a way to simplify my synchronization protocol in a manner that should improve performance on architectures with weak memory consistency like ARM and POWER. If someone having access to such hardware could compare the performance of v0.2.2 and v0.2.1 through the benchmarking procedure described in the README, it would be much appreciated.

For the curious, the previous design required…

  • For the producer, 1 atomic swap and 1 atomic write, each with a release barrier
  • For the consumer, 1 atomic read and possibly 1 atomic swap, each with an acquire barrier

…whereas the new design requires:

  • For the producer, 1 atomic swap with a release barrier
  • For the consumer, 1 relaxed atomic read and possibly 1 atomic swap with an acquire barrier
  • Some bit fiddling… which isn’t atomic, and should thus have limited performance impact :stuck_out_tongue:

#21

Actually, since the new design has no memory fence nor writes during clean reads (when the producer has not submitted any update), I suspect that it could be faster than mutexes in scenarios where the shared state is rarely updated and efficiently movable.