4 ms·

I've had lately a look at QEMUs internals and saw their thread safe implementation of a hash table, capable of concurrent reads: qht [0]. If the author sees th

I've had lately a look at QEMUs internals and saw their thread safe implementation of a hash table, capable of concurrent reads: qht [0]. If the author sees this, you might want to take a look at it. [0] https://github.com/qemu/qemu/blob/master/util/qht.c https://github.com/qemu/qemu/blob/master/util/qht.c

torstenvl 3y ago
[flagged]
- Retr0id 3y ago
  That's not how software licenses work.
  - torstenvl 3y ago
    Yes, actually, it is. "Software licenses" aren't their own subject. They are instruments of copyright law. Without copyright, there is nothing to be licensed. And clean room implementations are the best way to ensure that no copyright violation has occurred.
    - Retr0id 3y ago
      A clean room implementation is not the only way to avoid violating copyright.
    - loeg 3y ago
      Looking at GPL code doesn't poison your mind forever. Of course, you cannot directly copy GPL code and call it MIT. And you arguably cannot have GPL code open in one window and write your version in a separate window. Copyright protects a specific set of symbols in some order, not an underlying idea or algorithm. You can look at a GPL hashtable one day and write an MIT one the next, no problem.
      - deleted 3y ago
        [deleted]
      - torstenvl 3y ago
        Yes, that is all correct. However, it is my opinion that having a project posted on HN, being directed to look at the "internals" of another software project (such project being licensed under the GPL), and subsequently modifying your own project with what you've learned, is legally risky. Specifically, if I were corporate counsel at a company looking to use MIT-licensed code in a product of ours, and our due diligence uncovered that just such a thing had happened, I would advise against using that code. The risk—that is, likelihood multiplied by the magnitude of the severity of the consequences—of being compelled to license our software under the GPL would be far too high. As a result, I stand by my assessment that it is probably best—albeit not mandatory—for the OP author not to take a look at how GPL'd code accomplishes what OP author is trying to accomplish.
        deleted 3y ago
        [deleted]
        loeg 3y ago
        > Specifically, if I were corporate counsel at a company looking to use MIT-licensed code in a product of ours, and our due diligence uncovered that just such a thing had happened, I would advise against using that code. I get that corporate counsel is extremely conservative (do you practice in this area?) and often insensitive to the costs of following their advice (as opposed to the costs of not following it) and you may well be right that this is what they would advise if asked explicitly. But I don't think the end result is good advice for an engineer. > The risk—that is, likelihood multiplied by the magnitude of the severity of the consequences—of being compelled to license our software under the GPL would be far too high. I think you're overestimating both likelihood and severity. Likelihood -- I mean, your internal hash table is never going to see GPL enforcement action. Severity -- the least expensive path to remediation is unlikely to be GPL'ing your software. You could replace the component, for example. I appreciate the discussion, by the way. Thanks!
        detrites 3y ago
    - User23 3y ago
      Software licenses are the greatest legal psych out of my lifetime. US law permits anyone who has a legally acquired copy of a piece of software to copy it further[1], such that such a new copy or adaptation is created as an essential step in the utilization of the computer program in conjunction with a machine and that it is used in no other manner As anyone can see, this completely obviates any need to be licensed to use software once the seller has lawfully sold you a copy. It's yours and you can execute it as you see fit. Interestingly, this doesn't really affect the GPL because the GPL doesn't attempt to kick in unless you further redistribute. And that, of course, is not protected by section 117 and does require a license. Of course we live in a regime where the process is the punishment, so if you're high profile you'll probably get hit with a ruinous lawsuit anyhow. C'est la vie. [1] https://www.law.cornell.edu/uscode/text/17/117 https://www.law.cornell.edu/uscode/text/17/117
- haileys 3y ago
  This is such a case of lawyer brain. The OP wrote this as a learning exercise. With the goal of learning in mind, I would suggest that it's probably best for the OP to go and read as much code as they possibly can, no matter the license!
  - rewmie 3y ago
    > This is such a case of lawyer brain. I'm not sure you are fully aware of the implications. In fact, it seems you're dismissing easily avoidable risks by arguing you'd never be caught. You can read plenty of code without risking accusations of license agreement violations.
  - patrick451 3y ago
    Perhaps, but lawyers can ruin your life. If you ask me, it's a travesty that the law is so complex nobody in this thread can agree if this is good advice or paranoia run out of control. That's the world lawyers have created for us, and like it or not, we live in their world.
erhaetherth 3y ago
Curious why concurrent reads would ever be an issue. As long as there are no writes during those reads... everything should be stable, no?
- rewmie 3y ago
  You don't seem to be very curious because your questions are clarified literally in the very first comment in OP's link.
- marginalia_nu 3y ago
  You can't really know that though. Without appropriate memory barriers, you can end up with an inconsistent view of the memory due to out-of-order execution and other weird stuff the CPU does behind the scenes. There's significant footguns around low level concurrency primitives.
  - ryao 3y ago
    If you are doing locking to protect against writes occurring when reads occur, you get those barriers for free. That said, they are using RCU to allow writers and readers to operate concurrently.
- cryptonector 3y ago
  The real problem is resource management. If you have a threaded GC then you can just read, and the act of reading will cause the value you read to be alive. If you don't have a GC, however, you probably use reference counts, and now you may need to compose an atomic read of a pointer with an atomic reference count increment, but by the time you're doing the second step the object you're referencing may have been destructed.
- jlokier 3y ago
  > As long as there are no writes during those reads... everything should be stable, no? Yes, but how do you ensure there are no writes during those reads? You have to protect the reads against concurrent writes. The simplest way is to use a mutex, but that doesn't support concurrent reads. The next way, which is fairly common, is to use a read-write lock. That allows reads that are concurrent with each other, but only one write at a time, and no concurrency between reads and writes. A standard read-write lock is not particularly fast for concurrent reads. The lock-for-read operation is required so that reads prevent a concurrent write from starting, and wait for a write already started to finish. That's not fast on a multi-core system because it forces cache line bouncing between cores. That is, unless particularly fancy types of read-write locks optimised for mostly reading are used, such as rwlock-per-core, and those are slow for writes. They are somewhat fast for reads on architectures with fast atomic operations, but not as fast as possible. Read-write locks also come in different flavours, depending on whether you want new reads to be blocked and queued when there's a write blocked waiting for current reads to finish. Fairness is an issue. This can get complicated, and bugs in libc rwlocks are not unheard of because of the complication. A seqlock can be used which has fast reads when there are no writes. They are fast on a multi-core system because there's no cache line bouncing between cores when there are only reads. But if there is a high rate of writes in one thread it can block all reads continuously, by causing them to livelock in loops. This is called spinning. More commonly, the writes tend to slow down seqlocked reads by a large factor in some scenarios, without blocking them completely. Just wasting a lot of CPU time and running slowly, out of proportion to the amount of blocking you would expect is necessary. Rather like an over-contended spinlock. Spinlocks, which can come in a mutex flavour or read-write flavour, should rarely be used in threaded code outside a kernel. Because they spin as described above, out of proportion to the amount of blocking that's really required, and the effect is much worse in pre-empted userspace threads than in a non-premptible kernel. It's possible to reduce seqlock and spinlock CPU spinning by transitioning to a different type of lock after some number of spins. Sometimes a dynamically estimated number of spins. This makes them behave better in userspace threaded code outside a kernel. But now your lock is rather complicated, and still not consistently fast at reads. An approach which works really well is RCU. Concurrent reads can be very simple and never spin because there's no loop. There's no multi-core cache line bouncing. Writes are more complicated, and the reads have to adhere to certain patterns because the kind of concurrency allowed between reads and writes is different in RCU than with locks. It works best if your program has some kind of top-level event loop that is returned to often, to provide the "quiescent states" RCU requires. But there are other ways to do it, if there's no top level, they just require reads to do a bit more work than almost nothing. Even RCU requires a little something in reads though, to get correct data. This is a data-dependency memory barrier. These barrier operations require zero instructions on nearly all CPUs because of how memory systems are designed, but are famously not free on the DEC Alpha which shows that it's not a "no operation", it just happens to be a side effect that is usually baked in. Even with zero instructions on nearly all CPUs, they limit which code optimisations the compiler is allowed to do, so have a non-zero average overhead, but it is very small in practice. RCU is what the QEMU hash table uses.

torstenvl 3y ago

[flagged]

Retr0id 3y ago
That's not how software licenses work.
- torstenvl 3y ago
  Yes, actually, it is. "Software licenses" aren't their own subject. They are instruments of copyright law. Without copyright, there is nothing to be licensed. And clean room implementations are the best way to ensure that no copyright violation has occurred.
  - Retr0id 3y ago
    A clean room implementation is not the only way to avoid violating copyright.
  - loeg 3y ago
    Looking at GPL code doesn't poison your mind forever. Of course, you cannot directly copy GPL code and call it MIT. And you arguably cannot have GPL code open in one window and write your version in a separate window. Copyright protects a specific set of symbols in some order, not an underlying idea or algorithm. You can look at a GPL hashtable one day and write an MIT one the next, no problem.
    - deleted 3y ago
      [deleted]
    - torstenvl 3y ago
      Yes, that is all correct. However, it is my opinion that having a project posted on HN, being directed to look at the "internals" of another software project (such project being licensed under the GPL), and subsequently modifying your own project with what you've learned, is legally risky. Specifically, if I were corporate counsel at a company looking to use MIT-licensed code in a product of ours, and our due diligence uncovered that just such a thing had happened, I would advise against using that code. The risk—that is, likelihood multiplied by the magnitude of the severity of the consequences—of being compelled to license our software under the GPL would be far too high. As a result, I stand by my assessment that it is probably best—albeit not mandatory—for the OP author not to take a look at how GPL'd code accomplishes what OP author is trying to accomplish.
      - deleted 3y ago
        [deleted]
      - loeg 3y ago
        > Specifically, if I were corporate counsel at a company looking to use MIT-licensed code in a product of ours, and our due diligence uncovered that just such a thing had happened, I would advise against using that code. I get that corporate counsel is extremely conservative (do you practice in this area?) and often insensitive to the costs of following their advice (as opposed to the costs of not following it) and you may well be right that this is what they would advise if asked explicitly. But I don't think the end result is good advice for an engineer. > The risk—that is, likelihood multiplied by the magnitude of the severity of the consequences—of being compelled to license our software under the GPL would be far too high. I think you're overestimating both likelihood and severity. Likelihood -- I mean, your internal hash table is never going to see GPL enforcement action. Severity -- the least expensive path to remediation is unlikely to be GPL'ing your software. You could replace the component, for example. I appreciate the discussion, by the way. Thanks!
      - detrites 3y ago
  - User23 3y ago
    Software licenses are the greatest legal psych out of my lifetime. US law permits anyone who has a legally acquired copy of a piece of software to copy it further[1], such that such a new copy or adaptation is created as an essential step in the utilization of the computer program in conjunction with a machine and that it is used in no other manner As anyone can see, this completely obviates any need to be licensed to use software once the seller has lawfully sold you a copy. It's yours and you can execute it as you see fit. Interestingly, this doesn't really affect the GPL because the GPL doesn't attempt to kick in unless you further redistribute. And that, of course, is not protected by section 117 and does require a license. Of course we live in a regime where the process is the punishment, so if you're high profile you'll probably get hit with a ruinous lawsuit anyhow. C'est la vie. [1] https://www.law.cornell.edu/uscode/text/17/117 https://www.law.cornell.edu/uscode/text/17/117
haileys 3y ago
This is such a case of lawyer brain. The OP wrote this as a learning exercise. With the goal of learning in mind, I would suggest that it's probably best for the OP to go and read as much code as they possibly can, no matter the license!
- rewmie 3y ago
  > This is such a case of lawyer brain. I'm not sure you are fully aware of the implications. In fact, it seems you're dismissing easily avoidable risks by arguing you'd never be caught. You can read plenty of code without risking accusations of license agreement violations.
- patrick451 3y ago
  Perhaps, but lawyers can ruin your life. If you ask me, it's a travesty that the law is so complex nobody in this thread can agree if this is good advice or paranoia run out of control. That's the world lawyers have created for us, and like it or not, we live in their world.

erhaetherth 3y ago

Curious why concurrent reads would ever be an issue. As long as there are no writes during those reads... everything should be stable, no?

rewmie 3y ago
You don't seem to be very curious because your questions are clarified literally in the very first comment in OP's link.
marginalia_nu 3y ago
You can't really know that though. Without appropriate memory barriers, you can end up with an inconsistent view of the memory due to out-of-order execution and other weird stuff the CPU does behind the scenes. There's significant footguns around low level concurrency primitives.
- ryao 3y ago
  If you are doing locking to protect against writes occurring when reads occur, you get those barriers for free. That said, they are using RCU to allow writers and readers to operate concurrently.
cryptonector 3y ago
The real problem is resource management. If you have a threaded GC then you can just read, and the act of reading will cause the value you read to be alive. If you don't have a GC, however, you probably use reference counts, and now you may need to compose an atomic read of a pointer with an atomic reference count increment, but by the time you're doing the second step the object you're referencing may have been destructed.
jlokier 3y ago
> As long as there are no writes during those reads... everything should be stable, no? Yes, but how do you ensure there are no writes during those reads? You have to protect the reads against concurrent writes. The simplest way is to use a mutex, but that doesn't support concurrent reads. The next way, which is fairly common, is to use a read-write lock. That allows reads that are concurrent with each other, but only one write at a time, and no concurrency between reads and writes. A standard read-write lock is not particularly fast for concurrent reads. The lock-for-read operation is required so that reads prevent a concurrent write from starting, and wait for a write already started to finish. That's not fast on a multi-core system because it forces cache line bouncing between cores. That is, unless particularly fancy types of read-write locks optimised for mostly reading are used, such as rwlock-per-core, and those are slow for writes. They are somewhat fast for reads on architectures with fast atomic operations, but not as fast as possible. Read-write locks also come in different flavours, depending on whether you want new reads to be blocked and queued when there's a write blocked waiting for current reads to finish. Fairness is an issue. This can get complicated, and bugs in libc rwlocks are not unheard of because of the complication. A seqlock can be used which has fast reads when there are no writes. They are fast on a multi-core system because there's no cache line bouncing between cores when there are only reads. But if there is a high rate of writes in one thread it can block all reads continuously, by causing them to livelock in loops. This is called spinning. More commonly, the writes tend to slow down seqlocked reads by a large factor in some scenarios, without blocking them completely. Just wasting a lot of CPU time and running slowly, out of proportion to the amount of blocking you would expect is necessary. Rather like an over-contended spinlock. Spinlocks, which can come in a mutex flavour or read-write flavour, should rarely be used in threaded code outside a kernel. Because they spin as described above, out of proportion to the amount of blocking that's really required, and the effect is much worse in pre-empted userspace threads than in a non-premptible kernel. It's possible to reduce seqlock and spinlock CPU spinning by transitioning to a different type of lock after some number of spins. Sometimes a dynamically estimated number of spins. This makes them behave better in userspace threaded code outside a kernel. But now your lock is rather complicated, and still not consistently fast at reads. An approach which works really well is RCU. Concurrent reads can be very simple and never spin because there's no loop. There's no multi-core cache line bouncing. Writes are more complicated, and the reads have to adhere to certain patterns because the kind of concurrency allowed between reads and writes is different in RCU than with locks. It works best if your program has some kind of top-level event loop that is returned to often, to provide the "quiescent states" RCU requires. But there are other ways to do it, if there's no top level, they just require reads to do a bit more work than almost nothing. Even RCU requires a little something in reads though, to get correct data. This is a data-dependency memory barrier. These barrier operations require zero instructions on nearly all CPUs because of how memory systems are designed, but are famously not free on the DEC Alpha which shows that it's not a "no operation", it just happens to be a side effect that is usually baked in. Even with zero instructions on nearly all CPUs, they limit which code optimisations the compiler is allowed to do, so have a non-zero average overhead, but it is very small in practice. RCU is what the QEMU hash table uses.