6 ms·

An insane idea on reference counting [pdf]

58 points by _kp6z 12y ago

mmastrac 12y ago
Is the RCU patent really still an issue?
- gregkh 12y ago
  Why wouldn't it be?
  - shmerl 12y ago
    Why is it patentable?
    - WildUtah 12y ago
      The Patent Office considers everything patentable. Last month they issued a patent on literally calling up two pharmacies to pick the one that offered your drug cheaper. They even fast tracked that application and didn't ask a single follow up question about it.
      - dpe82 12y ago
        I hadn't heard of that one and can't find anything about it. Do you have a source?
        WildUtah 12y ago
        Patent: http://www.google.com/patents/US8712797 http://www.google.com/patents/US8712797 Discussion: http://patentlyo.com/patent/2014/05/business-method-patent.html http://patentlyo.com/patent/2014/05/business-method-patent.h...
      - axman6 12y ago
        Urgh, no, they don't. If you're ignorant about an issue, you should ask questions, not speak authoritatively about it. And yes, you are clearly ignorant about the issue. I'd guess you would also believe "Amazon just got a patent for taking a photo of something in front of a white background", right?
        Natsu 12y ago
        If you mean this [1], then they convinced the USPTO that their process for taking pictures with a white background and making it look good (F-stops, ISO settings, etc.) was patentable. And of course, the patent says "It should be emphasized that the above-described embodiments of the present disclosure are merely possible examples of implementations set forth for a clear understanding of the principles of the disclosure." Because you could, of course, use other F-stops, ISO settings, etc. That would be really obvious. The whole set it up with good settings a normal photographer might use? That's the original part. This reminds me of Apple's design patent on a design where "rounded corners" were basically the only feature anyone could name that was similar to Samsung's. So technically they didn't patent rounded corners... they just accused Samsung in court of infringing it with a phone where that was the primary similarity. This is all part of a big game where patent lawyers find meaningless "limitations" like this to distinguish themselves from the prior art to the USPTO, then come back to the federal courts and demonstrate just how meaningless they are as they assert what might as well be as bad a patent as is the popular understanding. [1] http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-adv.htm&r=1&f=G&l=50&d=PALL&S1=08676045&OS=PN/08676045&RS=PN/08676045 http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=H...
        axman6 12y ago
        I don't think I could agree with you less. The Amazon patent claims are EXTREMELY narrow and specific; any deviation from what's claimed (changing F-stop, ISO, number of lights, etc.) is not within the scope of the claim and is therefore not patented and free to be used. You emphasised that making such changes would be obvious, and yes, I agree, but that's irrelevant unless someone tries to patent a similar process with some of those changes made. "It should be emphasized that the above-described embodiments of the present disclosure are merely possible examples of implementations set forth for a clear understanding of the principles of the disclosure." Please read the above link about how to read a patent. That has absolutely no baring on the scope the pqatent covers. It's just there to cover the lawyer's arse when the examiner tries to say "Your claims don't match your examples so it's not [reasonably based on the description]#". Examples are necessary in a patent application, but should not be used to limit the scope of the actual invention defined by the claims if all the information to produce all embodiments of the invention would be reasonable ascertained from the description. Again, why on earth bring up the Apple DESIGN patent? They are practically unrelated topics. It's like saying a Nissan GT-R is a shitty car because you don't like the Tiida (hmm, does that geolocate me too much?). just because they both have patent in the name does not mean that one is related to the other. # I'm not sure what the US term here is, in most of the world it's "fully supported by the description"
  - mmastrac 12y ago
    It must be getting close to expiry at this point -- wasn't it filed in the mid 90s? EDIT: I did a little digging and some calculations in the USPTO's horrible, horrible expiry calculator and the list of patents in wikipedia (which TBH, I haven't dug into to figure out how relevant they are but the list below is roughly ordered from "fundamental" to "interesting things you can do with RCU"): http://www.google.com/patents/US5442758 http://www.google.com/patents/US5442758 -- should have expired last year http://www.google.com/patents/US5608893 http://www.google.com/patents/US5608893 -- will expire very shortly, but is noted as "lapsed" due to non-payment of fees http://www.google.com/patents/US5727209 http://www.google.com/patents/US5727209 -- will expire next year https://www.google.com/patents/US6219690 https://www.google.com/patents/US6219690 -- this one will be a few more years http://www.google.com/patents/US6886162 http://www.google.com/patents/US6886162 -- even longer
    - gregkh 12y ago
      Good digging. If the original RCU patents are expired, it might make more sense for the BSDs to start to use RCU, it makes things much easier in the long run, and should scale a lot better than this proposed solution.
      - JoshTriplett 12y ago
        > If the original RCU patents are expired, it might make more sense for the BSDs to start to use RCU, it makes things much easier in the long run, and should scale a lot better than this proposed solution. Optimizations and new versions of RCU are patented as well: preemptible variations, scalability optimizations, tiny/embedded variations, and many common data structures. However, I agree that even the most basic RCU implementation will scale far better than referencing counting for many applications.
      - kev009 12y ago
        Greg, if you know anybody that has some pull on these kinds of things within IBM, can you contact The FreeBSD Foundation? We might need some kind of "FreeBSD and derivative" exemption or an interpretation of the unexpired patents effects on an RCU implementation. Justin Gibbs said last time he tried to contact IBM he got directed immediately to legal staff and does not have a good contact within IBM.
- JoshTriplett 12y ago
  > Is the RCU patent really still an issue? Only for BSDs; RCU is free to use under LGPL and GPL. (It was originally only usable under GPL. Later on, after Mathieu Desnoyers implemented a userspace version "liburcu", IBM granted permission to use RCU under LGPL to allow liburcu to use that license, making it more universally usable by arbitrary userspace software.)
sbahra 12y ago
The work gleb is showing here pretty much looks to be proxy collection, which also has a whole parade of patents. An interesting mechanism with good performance characteristics is defined at http://concurrencykit.org/presentations/ebr.pdf http://concurrencykit.org/presentations/ebr.pdf and is easily pluggable into an RCU implementation.
- citrin_ru 12y ago
  Do you know more about this patents?
colanderman 12y ago
If writes are infrequent and readers issuing atomic operations on the same word is expensive, why not use a set of read-write locks? Reader contention on any given lock would be amortized over the set; the cost is eaten by writers who must write-lock all the locks.
mzs 12y ago
Could something like tokens from dragonfly BSD be adapted in the way that Matt mentions: http://lists.dragonflybsd.org/pipermail/kernel/2004-February/082569.html http://lists.dragonflybsd.org/pipermail/kernel/2004-February...

58 points by _kp6z 12y ago

mmastrac 12y ago

Is the RCU patent really still an issue?

gregkh 12y ago
Why wouldn't it be?
- shmerl 12y ago
  Why is it patentable?
  - WildUtah 12y ago
    The Patent Office considers everything patentable. Last month they issued a patent on literally calling up two pharmacies to pick the one that offered your drug cheaper. They even fast tracked that application and didn't ask a single follow up question about it.
    - dpe82 12y ago
      I hadn't heard of that one and can't find anything about it. Do you have a source?
      - WildUtah 12y ago
        Patent: http://www.google.com/patents/US8712797 http://www.google.com/patents/US8712797 Discussion: http://patentlyo.com/patent/2014/05/business-method-patent.html http://patentlyo.com/patent/2014/05/business-method-patent.h...
    - axman6 12y ago
      Urgh, no, they don't. If you're ignorant about an issue, you should ask questions, not speak authoritatively about it. And yes, you are clearly ignorant about the issue. I'd guess you would also believe "Amazon just got a patent for taking a photo of something in front of a white background", right?
      - Natsu 12y ago
        If you mean this [1], then they convinced the USPTO that their process for taking pictures with a white background and making it look good (F-stops, ISO settings, etc.) was patentable. And of course, the patent says "It should be emphasized that the above-described embodiments of the present disclosure are merely possible examples of implementations set forth for a clear understanding of the principles of the disclosure." Because you could, of course, use other F-stops, ISO settings, etc. That would be really obvious. The whole set it up with good settings a normal photographer might use? That's the original part. This reminds me of Apple's design patent on a design where "rounded corners" were basically the only feature anyone could name that was similar to Samsung's. So technically they didn't patent rounded corners... they just accused Samsung in court of infringing it with a phone where that was the primary similarity. This is all part of a big game where patent lawyers find meaningless "limitations" like this to distinguish themselves from the prior art to the USPTO, then come back to the federal courts and demonstrate just how meaningless they are as they assert what might as well be as bad a patent as is the popular understanding. [1] http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-adv.htm&r=1&f=G&l=50&d=PALL&S1=08676045&OS=PN/08676045&RS=PN/08676045 http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=H...
        axman6 12y ago
        I don't think I could agree with you less. The Amazon patent claims are EXTREMELY narrow and specific; any deviation from what's claimed (changing F-stop, ISO, number of lights, etc.) is not within the scope of the claim and is therefore not patented and free to be used. You emphasised that making such changes would be obvious, and yes, I agree, but that's irrelevant unless someone tries to patent a similar process with some of those changes made. "It should be emphasized that the above-described embodiments of the present disclosure are merely possible examples of implementations set forth for a clear understanding of the principles of the disclosure." Please read the above link about how to read a patent. That has absolutely no baring on the scope the pqatent covers. It's just there to cover the lawyer's arse when the examiner tries to say "Your claims don't match your examples so it's not [reasonably based on the description]#". Examples are necessary in a patent application, but should not be used to limit the scope of the actual invention defined by the claims if all the information to produce all embodiments of the invention would be reasonable ascertained from the description. Again, why on earth bring up the Apple DESIGN patent? They are practically unrelated topics. It's like saying a Nissan GT-R is a shitty car because you don't like the Tiida (hmm, does that geolocate me too much?). just because they both have patent in the name does not mean that one is related to the other. # I'm not sure what the US term here is, in most of the world it's "fully supported by the description"
- mmastrac 12y ago
  It must be getting close to expiry at this point -- wasn't it filed in the mid 90s? EDIT: I did a little digging and some calculations in the USPTO's horrible, horrible expiry calculator and the list of patents in wikipedia (which TBH, I haven't dug into to figure out how relevant they are but the list below is roughly ordered from "fundamental" to "interesting things you can do with RCU"): http://www.google.com/patents/US5442758 http://www.google.com/patents/US5442758 -- should have expired last year http://www.google.com/patents/US5608893 http://www.google.com/patents/US5608893 -- will expire very shortly, but is noted as "lapsed" due to non-payment of fees http://www.google.com/patents/US5727209 http://www.google.com/patents/US5727209 -- will expire next year https://www.google.com/patents/US6219690 https://www.google.com/patents/US6219690 -- this one will be a few more years http://www.google.com/patents/US6886162 http://www.google.com/patents/US6886162 -- even longer
  - gregkh 12y ago
    Good digging. If the original RCU patents are expired, it might make more sense for the BSDs to start to use RCU, it makes things much easier in the long run, and should scale a lot better than this proposed solution.
    - JoshTriplett 12y ago
      > If the original RCU patents are expired, it might make more sense for the BSDs to start to use RCU, it makes things much easier in the long run, and should scale a lot better than this proposed solution. Optimizations and new versions of RCU are patented as well: preemptible variations, scalability optimizations, tiny/embedded variations, and many common data structures. However, I agree that even the most basic RCU implementation will scale far better than referencing counting for many applications.
    - kev009 12y ago
      Greg, if you know anybody that has some pull on these kinds of things within IBM, can you contact The FreeBSD Foundation? We might need some kind of "FreeBSD and derivative" exemption or an interpretation of the unexpired patents effects on an RCU implementation. Justin Gibbs said last time he tried to contact IBM he got directed immediately to legal staff and does not have a good contact within IBM.
JoshTriplett 12y ago
> Is the RCU patent really still an issue? Only for BSDs; RCU is free to use under LGPL and GPL. (It was originally only usable under GPL. Later on, after Mathieu Desnoyers implemented a userspace version "liburcu", IBM granted permission to use RCU under LGPL to allow liburcu to use that license, making it more universally usable by arbitrary userspace software.)

sbahra 12y ago

The work gleb is showing here pretty much looks to be proxy collection, which also has a whole parade of patents. An interesting mechanism with good performance characteristics is defined at http://concurrencykit.org/presentations/ebr.pdf http://concurrencykit.org/presentations/ebr.pdf and is easily pluggable into an RCU implementation.

citrin_ru 12y ago
Do you know more about this patents?

colanderman 12y ago

If writes are infrequent and readers issuing atomic operations on the same word is expensive, why not use a set of read-write locks? Reader contention on any given lock would be amortized over the set; the cost is eaten by writers who must write-lock all the locks.

mzs 12y ago

Could something like tokens from dragonfly BSD be adapted in the way that Matt mentions: http://lists.dragonflybsd.org/pipermail/kernel/2004-February/082569.html http://lists.dragonflybsd.org/pipermail/kernel/2004-February...