OpenBSD Journal

Developer blog: marco

Contributed by marco on from the random-thoughts dept.

Alright more non-news on the ACPI front. Jordan and I just finished a hack session to add more AML methods and AML parsing stuff. We made some pretty good progress but nothing that is useful yet. This AML crap is really really crazy hence the slow going progress. For example, in AML you can express if statements like if (a == b) then do something. Now a and b can be numbers, functions or even other objects. So the actual code is not that hard its finding and dealing with all available combinations that makes it real tricky. This is not aided at all by the vagueness of the spec itself. So nothing interesting to report besides "we are working on it". Stay tuned.

On a different note, besides Jordan visiting, Thomas Nordin (nordin@) also showed up. He is finishing up his PhD and has not been hacking OpenBSD because of that. To keep himself sane he has done some "light reading" on Software Transactional Memory and for good measure he has also written a working implementation of this in user space. What this does is making memory writes to shared data structures behave the same way as a database writes out a record. This is all done without any locks! Here is a simple description:

  1. Open a handle to a shared data structure
  2. If its opened for writing copy the data locally
  3. If its opened for reading read the variables as you would as if you had locks and close the read handle
  4. If no one changed the global data structure from underneath you atomically replace the whole global data structure with your local copy
  5. If someone did change the global data structure restart the transaction
This stuff "feels" very counter intuitive so before you go off on a tangent please read *and* understand the paper. The techniques described in it work and are surprisingly "light". I have now witnessed several conversations at parties at my house where some very bright individuals hear the hypothesis and initially question and "disagree" with it. The remarkable thing is that even the most hard nosed contrarians eventually come around. When this fails they'll throw other questions and theories at it like: "performance will suffer" and "i have this corner case that'll break it" etc. Funny stuff :-)

Anyway the reason i bring this up is because STM might start making its appearance in hardware in the future. The reason why this in interesting is because the current SMP locking mechanisms, big-lock and fine-grained-lock, simply suck. Big-lock hurts performance, fine-grained is too complex and puts the onus on the programmer to do it right. Not everyone can be an (instant) expert on all data structures in any given system. There are complex interactions and idiosyncrasies implicit to any system that can require a long bumpy road to learn and understand. STM does not seem to suffer from these issues. All that said I believe that locking mechanisms are bad and that we need something else. I am not smart enough to determine if it is STM but it sounds at least like a plausible alternative. Enough theoretical mambo-jambo! time will tell.

(Comments are closed)

Comments

  1. By Stefan Sonnenberg-Carstens (193.22.160.2) on

    What can I do and whom do I have to contact to get my nx8220 going ? Even if acpi is not the turning point ...

    Comments

    1. By phessler (209.204.157.106) on

      undeadly is not for tech support. go check http://openbsd.org/mail.html for the correct place. don't forget to read http://openbsd.org/report.html for the right way to report problems. (Hint: pretend your previous emails don't exist)

  3. By Alejo (212.161.126.5) on

    Developer blogs are great. Please keep doing them. Thanks and have a Happy 2006! Alejo

  4. By Anton Maksimenkov (212.57.174.2) on

    It seems to be very hard to adopt such sheduler as system sheduler. ;) But ideas promise very brave results on SMP area, it is interesting to hear about this from developers (may be you post some fragments here, on undeadly?).

    And where I can see mentioned example (source code) "and for good measure he has also written a working implementation of this in user space"? And as far as it working, may it already be used for some userland programming?

    Comments

    1. By Marco Peereboom (67.64.89.177) marco@peereboom.us on http://www.peereboom.us

      Don't get ahead of yourself now. Nowhere did I say that this was going to be implemented in the scheduler or even in userspace for that matter. OpenBSD uses big-lock and unless someone has the time and skill to replace that with something else, while not breaking any current functionality, this will not be done. The odds are slim because its a huge undertaking.

      I reported this because it is an interesting mind puzzle. I think it would be cute to put this into a userland library though. I'll try to convince nordin@ to do that.

      Comments

      1. By Anton Maksimenkov (212.57.174.2) on

        Ok, all right. By the way, nowhere did I say that I know this _will_ be implemented. I just say that it is very interesting way at least. And if so, it will be very interesting to hear what developers think about this. As you say it is some kind of "unbelievably", maybe someone explain that big lock is not so bad and STM will not bring very big improvements - I just ask. Please don't kick me much. :-)
        Anyhow, as you approve, it will be very interesting in userland arena too. For example, sometimes I avoid to use pthreads because of interlock snare and try to adapt all to some kind of FSM (less effective in some simple cases but with low cost in developing and debugging). But as far as I understand explained technology (STM) in the manner of userland lib may help and increase performance without lock design overhead in such cases.

        And in couple with arising 'rthread' library it may become VERY powerful weapon!

        Comments

        1. By Anonymous Coward (69.36.252.2) on

          What's with the distaste that people have with FSM's? I don't get it. They're simple and elegant, easy to debug, verifiable, extremely fast....
          And when you use them, the remainder of your application tends to fall into place easier.

          They're a little clumsy sometimes when written in particular languages, which is why you find so many people who develop a bad habit of avoiding them. But, they work well within the structure of C programs.

          Today you see many people beatup and tired of writing threaded code. They're writing network daemons again with select()/poll() (or the upgrades: kqueue()/epoll()). And of course, writing FSM's again.

          I suspect STM will find niche uses. A well designed library would go a long way toward quickly developing good practices regarding when and when not to use the method. The library in LibTLX is about the opposite of what I'd consider well designed. Hopefully it's really nothing more than a proof of concept.

          Comments

          1. By djm@ (203.217.30.86) on 

            | | |         The ASCII Fork Campaign
 \|/       against gratuitous use of threads.
  |

          2. By Marco Peereboom (67.64.89.177) marco@peereboom.us on http://www.peereboom.us

            I'd bet a $1 that STM is here to stay. I'd go further to say that its going to get hardware support in the near future.

          3. By tedu (69.12.168.114) on

            for many people, threads are a more natural mapping of real world problems/solutions. unfortunately, in the real world, "threads" (workers) don't exhibit nearly so many problems with concurrency. real dining philosophers rarely starve.

            Comments

            1. By beck (129.128.11.43) beck@openbsd.org on http://www.seizurerobots.com/

              >unfortunately, in the real world, "threads" (workers) don't exhibit
              >nearly so many problems with concurrency. real dining philosophers
              >rarely starve.

              Yes, real dining philisophers don't starve, but in practice they stab each other with their forks. that's the problem - this "natural mapping" s horsehit. workers fight amongst each other - and don't always solve things amicably, they occasionally sabotage each others work or duplicate effort needlessly - the "natural mapping" of threads to "workers" completely ignores this reality.

              "workers" map to threads in a perfect world. In a perfect world I'd be a communist - unfortunately communism only works in a fantasy world where people are not fundamentally lazy and greedy (don't feel bad about it, I don't - it's genetic) - similarly threads only "naturally" map to problems where "workers" can't disagree/ignore/sabotage/duplicate etc. etc. Implementations for perfect worlds cause security/reliability problems when exposed to the cold harsh light of reality.

              Of course there are places where threads, like communists, have their
              redeeming values, they're just over/mis-used at the moment.

    2. By dons@ (220.233.48.34) on

      I don't think it's been explained clearly, but STM is already implemented and widely used in Haskell. You can use it right now with GHC 6.4 or later, which runs nicely on OpenBSD x86 and amd64 (and others with some porting effort).

      One notable real world app already making heavy use of STM is Pugs, the Perl 6 compiler/interpreter written in Haskell. STM is almost certainly going to be the foundation for a new generation of concurrency abstractions emerging in Haskell.

      Some links:
      * The original STM paper
      * The STM API visible to Haskell programmers

  5. By Ober (192.35.232.241) Ober@linbsd.org on http://www.linbsd.org

    Now if we could get all three developers together at a public coffee shop like Mojos, that would be educational. :D

  6. By Amit Kulkarni (67.142.130.13) on http://forestlaw.blogspot.com/

    What happens if the data is changed while reading? How is the inconsistency handled?

    Comments

    1. By igi (83.208.110.151) on

      If no one changed the global data structure from underneath you atomically replace the whole global data structure with your local copy
      data structure cannot be modified during reading. you either read tho whole old version, or the new version. never mix of them since the writing process atomically changes it (e.g. redirecting pointer with a single op mov).

      Comments

      1. By Wouter Coene (213.84.53.206) on http://web.irdc.nl/

        So erm.. how precisely do you atomically replace a datastructure of, say, 512 bytes? I'm having a hard time visualising this in terms of CPU instructions (other than simply locking the bus).

        Or is this left as an exercise for the reader? :)

        Comments

        1. By Wouter Coene (213.84.53.206) on http://web.irdc.nl/

          Oh wait, it's all done with a single pointer. Now I get it. Yes, that could work.

  7. By m0rf (68.104.17.51) on

    sounds like the dirty reads in postgresql and others

    Comments

    1. By Anonymous Coward (70.27.15.123) on

      Sounds like you have no idea what you are talking about.

      Comments

      1. By m0rf (68.104.17.51) on

        "... This means that while querying a database each transaction sees a snapshot of data (a database version) as it was some time ago, regardless of the current state of the underlying data. This protects the transaction from viewing inconsistent data that could be caused by (other) concurrent transaction updates on the same data rows, providing transaction isolation for each database session.

        The main advantage to using the MVCC model of concurrency control rather than locking is that in MVCC locks acquired for querying (reading) data do not conflict with locks acquired for writing data, and so reading never blocks writing and writing never blocks reading. "

        no obviously not

        Comments

        1. By Anonymous Coward (70.27.15.123) on

          Clearly not. You are quite clueless in fact. MVCC prevents dirty reads. A dirty read is where transaction A reads data inserted/updated by transaction B, which has not yet been commited. So if transaction B is rolled back, then transaction A was using incorrect data. MVCC prevents this, since transaction A never sees transaction Bs data until it is committed.

          So no, postgresql does not have a dirty read problem. And if you bothered to read, neither does STM. Writes are atomic, you either read the old data, or the new data, there is no in between.

  8. By Anonymous Coward (162.58.82.244) on

    Yeah, it's DragonflyBSD related, but could be interesting:
    http://leaf.dragonflybsd.org/mailarchive/kernel/2005-12/msg00072.html

    Comments

    1. By Anonymous Coward (203.26.136.135) on

      Then/than, what's the difference... right?

Latest Articles

Credits

Copyright © - Daniel Hartmeier. All rights reserved. Articles and comments are copyright their respective authors, submission implies license to publish on this web site. Contents of the archive prior to as well as images and HTML templates were copied from the fabulous original deadly.org with Jose's and Jim's kind permission. This journal runs as CGI with httpd(8) on OpenBSD, the source code is BSD licensed. undeadly \Un*dead"ly\, a. Not subject to death; immortal. [Obs.]