9 ms·

Liblfds, a portable, license-free, lock-free data structure library written in C

152 points by striking 12y ago

bhouston 12y ago
Looks interesting. Funny thing I sort of judge projects now by being on github and looking at issues and PRs to see quality and health of the project -- I really would like to get a sense of the number of bugs and the issues people are running into while using it. Thus an independently hosted project like this is thus hard to for me to objectively judge.
anon3_ 12y ago
Why show off about 7.0 when there is none? Where is the VCS?
- michaelmior 12y ago
  Good question. The GitHub account is odd. There appears to be a new repository for each release. https://github.com/liblfds?tab=repositories https://github.com/liblfds?tab=repositories
  - anon3_ 12y ago
    With all due respect, frames on the website? Creating a new repo for version releases? I would like an explanation from the author. Many people judge books by their cover - I say let's see the code. But superficial things like that do matter in people's perceptions. edit: below, frames.
    - michaelmior 12y ago
      I assume you mean frames and not iframes.
- jallmann 12y ago
  > Where is the VCS? There isn't one, at least publicly. The author exports everything from SVN for each release, even though I pointed him towards git-svn for github two years ago. What's painful is that the liblfds API is completely renamed for each release, even minor ones -- all functions prefixed by the version number [1]. According to the author, the intention is to facilitate concurrent use of different liblfds versions. That might be forgivable for major releases, but not minor ones, IMHO. Overall, liblfds worked well (at least the queue, which was the only part I used) until version 6.0 was back-ported with the API rename and totally broke my code. After a couple emails with the author about this, I stopped using the library because I found the release strategy disagreeable enough to be a dead-end. [1] There are ways to sanely achieve this effect with macro expansion of function names, and still maintain a consistent API with #define aliasing... the author didn't seem interested in supporting this.
- deleted 12y ago
  [deleted]
rdtsc 12y ago
I am using this. Has been working well for years in a low latency environment. Great stuff.
cbd1984 12y ago
If it's distributed without a license, it's illegal to redistribute the software, or to distribute modified copies. You can only distribute patch kits which can be applied to the original codebase, which everyone must acquire from the original developers. http://cr.yp.to/softwarelaw.html http://cr.yp.to/softwarelaw.html > Once you've legally downloaded a program, you can compile it. You can run it. You can modify it. You can distribute your patches for other people to use. ... and that's it.
- cbd1984 12y ago
  I read the page: > You are free to use this software in any way, for any purpose. This is a license. It can't possibly be anything else. It's a simple, permissive license, but it's a license. Them claiming it isn't a license is nonsense.
  - distantsounds 12y ago
    ...are you arguing with yourself?
    - cbd1984 12y ago
      > ...are you arguing with yourself? You don't? No, I'm expanding on my thoughts. I explained the general idea first, and then described what was actually going on. The fact they don't know what a license is doesn't invalidate anything I said.
  - anon3_ 12y ago
    Is public domain a license, or is it no license? I'm wondering the same thing.
    - cbd1984 12y ago
      > Is public domain a license, or is it no license? Public domain means nobody owns the copyright to that work. Anyone can use it for any purpose whatsoever, because there's nobody to tell them they can't. So, no, it's not a license. It's putting something in a category where a license wouldn't even make sense.
jvoorhis 12y ago
The blog is amusing..
- watmough 12y ago
  s/amusing./off-putting/
- zaszrespawned 12y ago
  Haha yes, and one can relate to his experience as well.
- laichzeit0 12y ago
  It's like the prelude to an early heart attack.
troymc 12y ago
"If however for legal reasons a licence is required, the license of your choice will be granted." Very well, I want an exclusive license, meaning I'm the only person who can use this software. Also perpetual, of course, so the license never expires. And don't forget to indemnify me. But don't bother indemnifying yourself, so I can sue you if the software doesn't do everything I ever dreamed. And... (I'm being sarcastic here. My point is that you can't get away with not licensing your free software, or saying the equivalent of "I don't care." It's not like there's a dearth of free licenses to choose from.)
- wmf 12y ago
  It seems like a reasonable approach to me; it shifts the burden of choosing the license to those who care about licensing. For example, if you work for a company with uptight lawyers you can just request Apache 2.0 and everybody's happy, rather than getting into arguments about public domain or WTFPL or some other stupid thing.
  - icebraining 12y ago
    But does the author actually send messages granting those licenses, or is the user supposed to "will them into existence"? Because in the first case, the author just bought himself a whole lot of stupid work, and in the second, I don't see how anyone can be sure that will hold up in court.
- cbd1984 12y ago
  > My point is that you can't get away with not licensing your free software djb did, before he released everything (or practically everything?) into the public domain. Look for my other comment thread to see the practical results of that.
  - MichaelGG 12y ago
    Huh? djb had some sort of requirements, otherwise maintainers wouldn't have had the big tiff they did about his directory ideas (arguably better, but not in isolation). They couldn't package qmail up to use their distro-specific ways. Public domain fixed this, of course.
zaszrespawned 12y ago
This guys blog is hilarious~!
jedbrown 12y ago
Why choose this over Concurrency Kit (http://concurrencykit.org/ http://concurrencykit.org/)?
- jedisct1 12y ago
  +1. Concurrencykit is awesome and really well-maintained.
  - MordodeMaru 12y ago
    Both look good. See if we can support them in biicode.
  - ExpiredLink 12y ago
    and it even has a license!
- sbahra 12y ago
  <3
  - lfds-admin 12y ago
    "sbahra" here for those of you who do not know is the author of CK.
haberman 12y ago
The first two questions I want to know when I see a lock-free library: - how does it handle the ABA problem? - how does it handle the safe memory reclamation problem? The answers to these questions were not easy to find for this library. It appears that it solves the ABA problem by requiring DCAS (double-compare-and-swap). This rules out some platforms: "Note that the Alpha, IA64, MIPS, PowerPC and SPARC architectures do not provide contigious double-word compare-and-swap and as such, liblfds cannot be ported to those architectures." --http://liblfds.org/documentation/mediawiki/index.php?title=r6.1.1:Porting_Guide_(lfds)#Detailed_Platform_Requirements http://liblfds.org/documentation/mediawiki/index.php?title=r... An earlier release had a note that the library could theoretically be ported to an architecture supporting LL/SC instead (load-linked/store-conditional), but this note seems to have been removed in later versions: "Currently, liblfds has been ported only to platforms which provide a contigious double-word compare-and-swap (x86, x64 and ARM). It is entirely possible to port to a platform which instead provides load-link/conditional-store where non-load-linked loads can be performed inside the LL/SC pair (this is how ABA is solved using single word LL/SC) but this has not yet been done and it is not reasonable to ask a third party to undertake such a port until I've done it and documented it." --http://liblfds.org/documentation/mediawiki/index.php?title=r6:Porting_Guide#Detailed_Platform_Requirements http://liblfds.org/documentation/mediawiki/index.php?title=r... I could not readily find an answer to the question of how safe memory reclamation is handled. When elements are removed they are placed on a freelist, but there's no indication that the freelist is protected from prematurely deleting things at all. Perhaps the library is using DCAS somehow to ensure that deleted nodes are never dereferenced.
- ah- 12y ago
  While reading the rather hilarious blog of his, I stumbled upon this possible explanation why that sentence is gone: I'm going to ditch LL/SC implementations, in part because they're just too unreliable and in part because they prevent the library from being able to simply offer the caller a choice - "garbage collection or not?" which in turn removes a TON of stuff which otherwise has to be explained to the end user. http://www.liblfds.org/blog/index.php?entry=Quick-update http://www.liblfds.org/blog/index.php?entry=Quick-update
- TorKlingberg 12y ago
lfds-admin 12y ago
Hej. I am the author. I understand there are a range of simple and well understood licenses, such as the MIT license, which can be used. However, this implies the I agree with and abide by the notion of licensing as it exists today. This is not quite the case. I think property rights are correct, but I think freedom (all contracts must be voluntary and well-informed, except in self-defence) is correct, and so the situation as it stands, where other people decide the law regarding licensing and we have no choice but to adhere to it, this is unethical. Be clear here - it is not so much the purpose of licensing which I disagree with (for it fairly closely implements property rights, which I profoundly agree with) but rather the method of implementation - there is a single set of law, decided by others, and we have to obey that law. This violates my idea of freedom. So with regard to the licensing text on the library, I am attempting to meet the legal needs of users by giving them a carte blanche; they can know their (reasonable, sane) licensing needs will be met, and this I hope simply removes the issue as far as they are concerned, while honouring my ethical views.
- TheLoneWolfling 12y ago
  The problem with this approach is that your definition of "reasonable, sane" may not line up with someone else's.
- nine_k 12y ago
  It's sort of like not to check the values of parameters passed to a function, expecting than only reasonable, sane values will be provided, and no one will try to exploit the function. This may be a fine assumption for a private function. But for a public interface, be it a function or a license, you have to program defensively.
  - vegedor 12y ago
    Why would the function take parameters at all? As I see it, it only returns value :)
lfds-admin 12y ago
To answer various questions people have asked and to make one or two notes of my own; 1. The current version of the library contains a profound design flaw - it allocates memory. This is not viable in any way. The next release (which is very close to completion, but has been deferred for the last month due to a crisis project at work) does not. Regarding ConcurrencyKit, it is an excellent project, and I know Samy (I was involved in him getting his last job); he is an excellent programmer. He said to me about four years ago I needed to make a new release :-) 2. Regarding ABA and memory reclaimation. There is a comment noting that it is hard to find this information in the docs. I apologise. It is indeed not particularly explained. The docs were written with a view to a non-lock-free informed user wishing to use the API, so technical information regarding the internal implementation is lacking. In the current release ABA is resolved by the use of DCAS (limiting the library to ARM and Intel), and there is no memory reclaimation. In the next release, memory reclaimation has been implemented (removing the limit of ARM and Intel). I also implemented on ARM LL/SC versions of the algorithms, but these have been removed, because it's too hard to know which platforms they will or will not work on. ARM is still supported of course, but by using LL/SC to emulate CAS. 3. The blog, ah, yes. It's where I let off steam in the heat of frustration, which is off course not always pleasent - however, it's nice to vent. I am thinking of getting rid of it though, because it's not very professional. 4. The reason for a new github repo on each release, and the naming strategy, is to permit the concurrent use of multiple releases of the library. By allowing a new release to be used in parallel with old releases, existing code does not have to be modified. This minimizes work and risk. For minor releases and bug releases, where APIs do not change, a global search and replace will permit a full change to the new version. 5. Regarding frames. The site uses a number of third-party applications, such as a forum and a blog. These all emit HTML which assumes they are generating the whole page - they have a <HTML> tag in their output. Their output then has to exist in a frame. If I capture it and send it to a DIV, the DIV renders incorrectly. Finally, please note the forum (which is fairly new) needs to be upgraded to reduce spam attacks (I've been too busy to do so). Currently I see hundreds of attempts each day, by robots, to generate accounts and so it is impractical to continually scan the lists of requests to find any real requests. The forum does now offer a captch for this, and as soon as I get time (one or two weeks) I will upgrade to this.
- 12y ago

152 points by striking 12y ago

Looks interesting. Funny thing I sort of judge projects now by being on github and looking at issues and PRs to see quality and health of the project -- I really would like to get a sense of the number of bugs and the issues people are running into while using it. Thus an independently hosted project like this is thus hard to for me to objectively judge.

anon3_ 12y ago

Why show off about 7.0 when there is none? Where is the VCS?

michaelmior 12y ago
Good question. The GitHub account is odd. There appears to be a new repository for each release. https://github.com/liblfds?tab=repositories https://github.com/liblfds?tab=repositories
- anon3_ 12y ago
  With all due respect, frames on the website? Creating a new repo for version releases? I would like an explanation from the author. Many people judge books by their cover - I say let's see the code. But superficial things like that do matter in people's perceptions. edit: below, frames.
  - michaelmior 12y ago
    I assume you mean frames and not iframes.
jallmann 12y ago
> Where is the VCS? There isn't one, at least publicly. The author exports everything from SVN for each release, even though I pointed him towards git-svn for github two years ago. What's painful is that the liblfds API is completely renamed for each release, even minor ones -- all functions prefixed by the version number [1]. According to the author, the intention is to facilitate concurrent use of different liblfds versions. That might be forgivable for major releases, but not minor ones, IMHO. Overall, liblfds worked well (at least the queue, which was the only part I used) until version 6.0 was back-ported with the API rename and totally broke my code. After a couple emails with the author about this, I stopped using the library because I found the release strategy disagreeable enough to be a dead-end. [1] There are ways to sanely achieve this effect with macro expansion of function names, and still maintain a consistent API with #define aliasing... the author didn't seem interested in supporting this.
deleted 12y ago
[deleted]

rdtsc 12y ago

I am using this. Has been working well for years in a low latency environment. Great stuff.

cbd1984 12y ago

If it's distributed without a license, it's illegal to redistribute the software, or to distribute modified copies. You can only distribute patch kits which can be applied to the original codebase, which everyone must acquire from the original developers. http://cr.yp.to/softwarelaw.html http://cr.yp.to/softwarelaw.html > Once you've legally downloaded a program, you can compile it. You can run it. You can modify it. You can distribute your patches for other people to use. ... and that's it.

cbd1984 12y ago
I read the page: > You are free to use this software in any way, for any purpose. This is a license. It can't possibly be anything else. It's a simple, permissive license, but it's a license. Them claiming it isn't a license is nonsense.
- distantsounds 12y ago
  ...are you arguing with yourself?
  - cbd1984 12y ago
    > ...are you arguing with yourself? You don't? No, I'm expanding on my thoughts. I explained the general idea first, and then described what was actually going on. The fact they don't know what a license is doesn't invalidate anything I said.
- anon3_ 12y ago
  Is public domain a license, or is it no license? I'm wondering the same thing.
  - cbd1984 12y ago
    > Is public domain a license, or is it no license? Public domain means nobody owns the copyright to that work. Anyone can use it for any purpose whatsoever, because there's nobody to tell them they can't. So, no, it's not a license. It's putting something in a category where a license wouldn't even make sense.

jvoorhis 12y ago

The blog is amusing..

watmough 12y ago
s/amusing./off-putting/
zaszrespawned 12y ago
Haha yes, and one can relate to his experience as well.
laichzeit0 12y ago
It's like the prelude to an early heart attack.

troymc 12y ago

"If however for legal reasons a licence is required, the license of your choice will be granted." Very well, I want an exclusive license, meaning I'm the only person who can use this software. Also perpetual, of course, so the license never expires. And don't forget to indemnify me. But don't bother indemnifying yourself, so I can sue you if the software doesn't do everything I ever dreamed. And... (I'm being sarcastic here. My point is that you can't get away with not licensing your free software, or saying the equivalent of "I don't care." It's not like there's a dearth of free licenses to choose from.)

wmf 12y ago
It seems like a reasonable approach to me; it shifts the burden of choosing the license to those who care about licensing. For example, if you work for a company with uptight lawyers you can just request Apache 2.0 and everybody's happy, rather than getting into arguments about public domain or WTFPL or some other stupid thing.
- icebraining 12y ago
  But does the author actually send messages granting those licenses, or is the user supposed to "will them into existence"? Because in the first case, the author just bought himself a whole lot of stupid work, and in the second, I don't see how anyone can be sure that will hold up in court.
cbd1984 12y ago
> My point is that you can't get away with not licensing your free software djb did, before he released everything (or practically everything?) into the public domain. Look for my other comment thread to see the practical results of that.
- MichaelGG 12y ago
  Huh? djb had some sort of requirements, otherwise maintainers wouldn't have had the big tiff they did about his directory ideas (arguably better, but not in isolation). They couldn't package qmail up to use their distro-specific ways. Public domain fixed this, of course.

zaszrespawned 12y ago

This guys blog is hilarious~!

jedbrown 12y ago

Why choose this over Concurrency Kit (http://concurrencykit.org/ http://concurrencykit.org/)?

jedisct1 12y ago
+1. Concurrencykit is awesome and really well-maintained.
- MordodeMaru 12y ago
  Both look good. See if we can support them in biicode.
- ExpiredLink 12y ago
  and it even has a license!
sbahra 12y ago
<3
- lfds-admin 12y ago
  "sbahra" here for those of you who do not know is the author of CK.

haberman 12y ago

The first two questions I want to know when I see a lock-free library: - how does it handle the ABA problem? - how does it handle the safe memory reclamation problem? The answers to these questions were not easy to find for this library. It appears that it solves the ABA problem by requiring DCAS (double-compare-and-swap). This rules out some platforms: "Note that the Alpha, IA64, MIPS, PowerPC and SPARC architectures do not provide contigious double-word compare-and-swap and as such, liblfds cannot be ported to those architectures." --http://liblfds.org/documentation/mediawiki/index.php?title=r6.1.1:Porting_Guide_(lfds)#Detailed_Platform_Requirements http://liblfds.org/documentation/mediawiki/index.php?title=r... An earlier release had a note that the library could theoretically be ported to an architecture supporting LL/SC instead (load-linked/store-conditional), but this note seems to have been removed in later versions: "Currently, liblfds has been ported only to platforms which provide a contigious double-word compare-and-swap (x86, x64 and ARM). It is entirely possible to port to a platform which instead provides load-link/conditional-store where non-load-linked loads can be performed inside the LL/SC pair (this is how ABA is solved using single word LL/SC) but this has not yet been done and it is not reasonable to ask a third party to undertake such a port until I've done it and documented it." --http://liblfds.org/documentation/mediawiki/index.php?title=r6:Porting_Guide#Detailed_Platform_Requirements http://liblfds.org/documentation/mediawiki/index.php?title=r... I could not readily find an answer to the question of how safe memory reclamation is handled. When elements are removed they are placed on a freelist, but there's no indication that the freelist is protected from prematurely deleting things at all. Perhaps the library is using DCAS somehow to ensure that deleted nodes are never dereferenced.

ah- 12y ago
While reading the rather hilarious blog of his, I stumbled upon this possible explanation why that sentence is gone: I'm going to ditch LL/SC implementations, in part because they're just too unreliable and in part because they prevent the library from being able to simply offer the caller a choice - "garbage collection or not?" which in turn removes a TON of stuff which otherwise has to be explained to the end user. http://www.liblfds.org/blog/index.php?entry=Quick-update http://www.liblfds.org/blog/index.php?entry=Quick-update
TorKlingberg 12y ago

lfds-admin 12y ago

Hej. I am the author. I understand there are a range of simple and well understood licenses, such as the MIT license, which can be used. However, this implies the I agree with and abide by the notion of licensing as it exists today. This is not quite the case. I think property rights are correct, but I think freedom (all contracts must be voluntary and well-informed, except in self-defence) is correct, and so the situation as it stands, where other people decide the law regarding licensing and we have no choice but to adhere to it, this is unethical. Be clear here - it is not so much the purpose of licensing which I disagree with (for it fairly closely implements property rights, which I profoundly agree with) but rather the method of implementation - there is a single set of law, decided by others, and we have to obey that law. This violates my idea of freedom. So with regard to the licensing text on the library, I am attempting to meet the legal needs of users by giving them a carte blanche; they can know their (reasonable, sane) licensing needs will be met, and this I hope simply removes the issue as far as they are concerned, while honouring my ethical views.

TheLoneWolfling 12y ago
The problem with this approach is that your definition of "reasonable, sane" may not line up with someone else's.
nine_k 12y ago
It's sort of like not to check the values of parameters passed to a function, expecting than only reasonable, sane values will be provided, and no one will try to exploit the function. This may be a fine assumption for a private function. But for a public interface, be it a function or a license, you have to program defensively.
- vegedor 12y ago
  Why would the function take parameters at all? As I see it, it only returns value :)

lfds-admin 12y ago

To answer various questions people have asked and to make one or two notes of my own; 1. The current version of the library contains a profound design flaw - it allocates memory. This is not viable in any way. The next release (which is very close to completion, but has been deferred for the last month due to a crisis project at work) does not. Regarding ConcurrencyKit, it is an excellent project, and I know Samy (I was involved in him getting his last job); he is an excellent programmer. He said to me about four years ago I needed to make a new release :-) 2. Regarding ABA and memory reclaimation. There is a comment noting that it is hard to find this information in the docs. I apologise. It is indeed not particularly explained. The docs were written with a view to a non-lock-free informed user wishing to use the API, so technical information regarding the internal implementation is lacking. In the current release ABA is resolved by the use of DCAS (limiting the library to ARM and Intel), and there is no memory reclaimation. In the next release, memory reclaimation has been implemented (removing the limit of ARM and Intel). I also implemented on ARM LL/SC versions of the algorithms, but these have been removed, because it's too hard to know which platforms they will or will not work on. ARM is still supported of course, but by using LL/SC to emulate CAS. 3. The blog, ah, yes. It's where I let off steam in the heat of frustration, which is off course not always pleasent - however, it's nice to vent. I am thinking of getting rid of it though, because it's not very professional. 4. The reason for a new github repo on each release, and the naming strategy, is to permit the concurrent use of multiple releases of the library. By allowing a new release to be used in parallel with old releases, existing code does not have to be modified. This minimizes work and risk. For minor releases and bug releases, where APIs do not change, a global search and replace will permit a full change to the new version. 5. Regarding frames. The site uses a number of third-party applications, such as a forum and a blog. These all emit HTML which assumes they are generating the whole page - they have a <HTML> tag in their output. Their output then has to exist in a frame. If I capture it and send it to a DIV, the DIV renders incorrectly. Finally, please note the forum (which is fairly new) needs to be upgraded to reduce spam attacks (I've been too busy to do so). Currently I see hundreds of attempts each day, by robots, to generate accounts and so it is impractical to continually scan the lists of requests to find any real requests. The forum does now offer a captch for this, and as soon as I get time (one or two weeks) I will upgrade to this.

12y ago