Rig 2011/09/16

Second year at UZH looms on the horizon... Let's hope it's gonna be FUN! ;)

I haven't worked on Rig as much as I'd have liked this summer, but here's a quick summary of what did happen:

  • rig_str moved outside main source tree as its own module
  • further work went into testing
  • BS.txt's added, prototype configuration files for a new build-files generator, to maybe substitute CMake
  • improved support for Eclipse CDT 8.0 Static Analysis (awesome feature!)
  • fixed a bug in MurmurHash 3 (from upstream)
  • SMR using HPs was better name-spaced and the retire_mem function split up, to accommodate alternative SMR methods more easily
  • rig_mem_alloc_aligned() now supports additional flags; "RIG_MEM_ALLOC_ALIGN_PAD: pad allocation to next alignment boundary" was added (mostly for cache-line alignment to avoid false-sharing)
  • recursion was made optional for the MLock and the MRWLock, controlled by a flag. MRWLock now fully supports recursion, in both the read and write sides. This requires TLS-based owner checking to be performed, so it's not possible to disable that at compile-time for the MRWLock anymore. Non-recursive locks are the default now.

Next I'll be working on an implementation of Epoch-based SMR, which should offer better performance while traversing lists and ease of usage than HP-based SMR (as well as not having any patents I know of on it).

Posted by Luca Longinotti on 16 Sep 2011 at 14:37
Categories: Rig, C99 Comments

Software patents: WTF?

Disclaimer: I am not a lawyer, the following depicts my understanding of the issues at hand and my opinion. It is not legal counsel.
A discussion on StackOverflow I was having with the author of liblfds quickly went from technical to commercial/legal: software patents were mentioned, and the world became a little less clear...
Basically it boils down to the possibility that maybe, some algorithms/techniques/technologies implemented by Rig may be patented, and thus there might be legal questions about the usability of Rig in the US. I specify US here, because the EU doesn't recognize software patents to the extent of US patent law, where you can theoretically patent anything, which continuously results in totally bogus patents, like this one, if we're talking about data-structures and algorithms. As a Swiss citizen living in Switzerland I didn't even really ever think about this, since here software patents do not exists at all in the form possible in the US, anything purely algorithmic is hardly patentable.
As here we simply don't care about this possibility, if you want to code something, you do, also being part of the academic community, it's almost taken for granted that working on and off others research, improving, implementing etc. is possible and even encouraged, especially in an open-source fashion. So no, I wasn't trying to deceive anyone here, it just never entered my mind as a real concern that needs significant time dedicated to it. But I'm doing that now, so let's address Mr. Douglass' concerns:

A) the BSD license is incompatible with possible patents, meaning the license of code is related to possible patent claims

This is incorrect. License, copyright and patents are different things, even if somewhat related. It is perfectly possible to create code and license it, even if it knowingly violates granted patents, see the LAME case for an obvious example. Usually the license has nothing at all to do with possible patents that said code may be infringing, a code's license attributes the copyright and distribution as well as usage constraints upon the specific code in question. Patents are about ideas and techniques, especially the software ones, they usually just describe a procedure, which can be implemented in many a different way.
Conclusion: licenses relate to the particular code of the particular implementation, they just tell you what kind of restrictions I, as the author of the code, pose upon the code itself, with regards to distribution, use and re-use, linkage, etc.. There are licenses, like the GPL v3.0 and the Apache License, that do have extra bits and pieces that also regulate patent claims. The GPL v2.0, LGPL, BSD and most others don't give you any special rights regarding patents whatsoever, unless the code is specifically released by the owner of the patents in the first place, which may then forbid later patent infringement suits on compliant derivative works. This again very much depends on the exact wording of the license, and the patent still remains an independent entity.

B) RCU is okay to use and there will be no possible patent-related problems, because it's LGPL

I have no idea where this comes from. The LGPL paragraphs 11 and 12 specifically do not grant you any right whatsoever regarding patents held over what the code (liburcu in this case) does, it actually says that, if faced with patent infringement suits, you must try to comply with both the suit, as well as the license concerning distribution, meaning you either geographically restrict the software in such a case or stop distributing it altogether. Just because there are LGPL implementations of RCU (and others exist under various other licenses, like in the Linux kernel under the GPL v2.0), doesn't automatically mean that you're granted full usage of the patents on the RCU technique, patents which are fully filed, existing and valid, from Wikipedia: "The technique is covered by U.S. software patent 5,442,758, issued August 15, 1995 and assigned to Sequent Computer Systems, as well as by 5,608,893, 5,727,528, 6,219,690, and 6,886,162. The now-expired US Patent 4,809,168 covers a closely related technique."
As such, the fact an LGPL implementation of RCU exists, doesn't automatically grant you any right upon the RCU patents themselves, nor does it make them automatically freely usable for other implementations.
The fact that Paul McKenney provides a GPL implementation in the kernel may be of help here, as the main patent holder, his offering a GPL licensed implementation does protect users of said GPL implementation and derivatives, again under what the GPL defines as such, from any patent claims.
Regarding the GPL: "This means that a patent holder who distributes a software package incorporating his patent can no longer assert that patent against people who distribute that package further or incorporate the package in their own product. Asserting a patent restricts the rights granted by the GPL and therefore is not permitted. This means that a competitor is now free to incorporate that package in his own product without having to pay any royalty to the patent holder. Of course that part of the product (and all other parts based on that part) will have to be made available under the GPL."
If such then directly translates to the LGPL user-space implementation is unclear, but given the involved parties it's very likely. It still doesn't mean any other, new RCU implementation has any rights on the RCU patents, those are still there and valid. You either need to base your work directly on the available GPL/LGPL code and release it under the same license, or get explicit permission from the patent holders.

C) There may be a patent on the non-blocking list or its delete-bit

Harris actually patented the whole thing. I'm not sure at all about the delete-bit alone, it can trivially be shown that the technique of using the unused bits of a pointer to store information was widely known and used before the 2000 patent. Just take a look at Lisp machines and Tagged pointers. Several implementations exist, work on extending this was done by various sources, there is code and books on this ("The Art of Multiprocessor Programming"). I have no idea what this means from a legal point of view. Non-profit use and research seem to be fully okay. My own code is not a 1:1 implementation of what Harris describes, I use a two-dimensional list, providing KeyNodes at intervals to start re-traversal from a shorter, guaranteed point, and I handle restart of traversal differently, trying a tighter path first.

D) There may be a patent on SMR using Hazard Pointers

There is a patent application, no patent. No idea here either, it is used and extended in other papers (RCU+HP, Ref-counts+HP). Several implementations exist, under various licenses, even of the derivative papers... I am using the concepts too.
In any case, I have to compliment Maged Michael for his papers, those are awesome, very clear and well written.

E) I'm intentionally mis-informing and deceiving users of my library

Hell, NO! As I explained above, software patents are just a non-issue here, it's something you just don't really think about, other than to laugh at Slashdot, ArsTechnica & co. news about the latest patent granted in the US on warm water and double-clicking an icon. With this blog post, linked on the library's home-page, I'm remedying this for the concerned US citizen.

I believe patents on ideas and abstract concepts, especially software, are fundamentally wrong, they realistically only protect the lazy implementor. Especially with the situation as it is now in the US, realistically, shut down your computer and search for a new job, maybe something involving nature (but they're patenting that stuff too...), because I'd really like for you to prove that just glibc, Gnome, KDE are completely safe from any patent-related question. Even if you own the patent yourself, you can't be totally sure no-one else has patented something similar before, and even less sure if and what that means for you. Even the big players have no real idea what's going on, just look at the various browser vendors and Google on VP8 / H264, or take a look at this graph and tell me how long it took you to either explode in laughter, amusedly shake your head, or both.

A few more resources on this:

In the meantime, I'll happily continue coding on my open-source library, learning new things, experimenting and benchmarking and having fun. And I hope others find this freely given work useful, and may use the library themselves, because it's there and works and may make their life easier.

Posted by Luca Longinotti on 08 Jul 2011 at 11:57
Categories: Rig, CompSci, Software Comments

SSD crazy fast!

Finally replaced the old HD with a SSD I bought in January on my workstation, an OCZ Vertex 2 in 3.5" format, so that it fits in the hot-swap trays I've got.
It's actually surprising that so few vendors have 3.5" editions, as that's what practically all desktops, workstations and servers do have, especially considering hot-swap trays and similar drive bays.
Sure, with 2.5" you can pack more stuff into new-generation servers, but those are still incredibly expensive, and it makes sense on laptops, but that's pretty much it.
Anyway, the results are there: disk operations are crazy fast compared to before. Boot is incredibly fast, actually with OpenRC now, so fast that getting an IP via DHCP was the dominant factor, and changing to a static IP eliminated that one too.
I'm very satisfied with this, and ext4 with the 'discard' option (TRIM support) seems to work perfectly fine.

On the Rig front, I've not done much: some more work went into testing, the typeinfo stuff was completely removed, and a few more checks with regards to sizes and permitted flags were added.

Another project that I'll probably tackle soon is writing a build system that doesn't suck, and that tries to really be minimal, and not support the world and more, it just needs to generate Makefiles (and Visual Studio/Eclipse support probably too). The build itself is left to the relevant tools, this just really needs to gather info about where we're running and the features we want, make that info available to the user (some header file), and generate appropriate Makefiles, which don't depend back on the generator itself, so that you can also just generate generic Makefiles and not need to have the generator installed on every system with all its dependencies. I mostly want to get rid of CMake and its horrible mess of half-baked modules. Anyone wants to help here? It's going to be in Python, and it should support only C/C++ builds.

Posted by Luca Longinotti on 13 May 2011 at 10:10
Categories: Hardware, Rig, Software Comments

Rig 2011/05/02

This week's Rig status update:

  • MLOCK/MRWLOCK: added functions to discover if a lock is held or not, clarified documentation wrt recursive locking, and fixed a possible wrap-around bug in MLOCK and an incorrect error return in MRWLOCK
  • SMR: ported it to use MLOCK instead of its own micro-lock scheme
  • Changed rig_thread_id() to start at 1 for the main thread and not to use 0 at all. This aligns it with some OS implementations, leads to better performance, and fixes a bug in MLOCK, which uses the 0 ID to signal "no-thread-owns-me"
  • Changed default hash algorithm to MurmurHash 3
  • Added support for tests, using the great Check framework for C Unit-Testing, and using CMake's CTest to run them
  • Added optional testing support to the Gentoo ebuild (USE=test + FEATURES=test)

Posted by Luca Longinotti on 02 May 2011 at 08:00
Categories: Rig, C99 Comments

Micro-Lock, MurmurHash 3, ...

A quick summary of work done on Rig in the past weeks since the release of 0.4.0:

  • added Micro-Lock, a Mutual Exclusion Lock, based on CAS like MRWLock, with support for ownership checking and recursive locking
  • added MurmurHash 3, the new version of this well known hash algorithm, even faster than its predecessor, especially on older systems
  • Atomic_Ops: added support for the SPARCv9 architecture, as well as support for GCC intrinsics (though the membar situation still needs some work there), and further support for emulating certain atomic primitives using others (there's a graph of how this works)

Posted by Luca Longinotti on 26 Apr 2011 at 22:00
Categories: Rig, C99 Comments

Rig 0.4.0 released

Finally, after years of development, the first release of the Rig library is ready.
Rig started out as a safe strings C99 library, but grew to encompass lock-free data structures and other helpful, multiprocessor oriented features. A quick overview:

  • lock-free stack, queue and ordered list, all with the ability to iterate over them, O(1) size
  • memory is correctly reclaimed through the use of the SMR concept, working correctly in the absence of GC (Garbage Collection is not part of the C language)
  • hashing functions
  • atomic counter
  • thread abstraction (currently supporting POSIX Threads, Win32 Threads will follow)
  • Micro-ReadWrite Lock, a minimal RW-Lock, following the concept of Windows's Slim-RW-Locks, fully based on atomic operations, but also taking advantage of TLS to implement advanced features, like owner-checking
  • string/buffer functions (still incomplete, don't use those yet!)

Focus was set on modularity and reusability, meaning some parts of Rig are segregated and can be used by other projects too:

  • Atomic_Ops: atomic operations headers, providing atomic load, store, add, fetch-and-add, CAS (returning the old value or a boolean), swap and various memory barrier types. All operations expect an explicit memory barrier specification, forcing the programmer to think about them.
    A flag-pointer is also provided, an atomic pointer which uses its last bit to save a boolean flag.
    Modern x86-64 (SSE2 and newer) is the only currently supported architecture, others will follow as soon as I get access to hardware for testing (offers are gladly accepted!).
    This work was inspired by OpenPA.
  • SupportDS: support data structures, non-multi-threading-safe, currently there's a hybrid stack.
  • System Includes: a series of headers to parse the predefined macros on your system to discover things like which OS, which compiler, which libc and which architecture you're running on, to influence compilation, and define a few other features in an as portable way as possible, like TLS support or alignment specification.
    This work was inspired by predef.

Rig currently requires GCC and Cmake to compile, as well as the PThreads library.
It can be downloaded here, and following is its SHA256 checksum:
SHA256 0e95e7c643631f378b46c4b9c948f59b48927d5b249e7bb885623a7491ad45ba rig-0.4.0.tar.bz2

Posted by Luca Longinotti on 10 Apr 2011 at 21:20
Categories: Rig, C99 Comments

(Page 1 of 1)