Date: Mon, 1 Jan 2001 21:02:46 -0700 (MST) From: Kevin Van Maren <vanmaren@fast.cs.utah.edu> To: jhb@FreeBSD.ORG, julian@elischer.org Cc: archie@FreeBSD.ORG, smp@FreeBSD.ORG Subject: Re: looking for locking advice.. Message-ID: <200101020402.VAA12154@fast.cs.utah.edu>
next in thread | raw e-mail | index | archive | help
Reader/Writer Locks (or SIX Locks): Julian, I downloaded your code yesterday from the web. I really like your reader/writer queue implementation. You basically use mutexes to protect a "busy flag" and a jobs queue, and support running several "read-only" jobs at once. Your implementation is truly "fair" (keeps requests in order). You don't hold the mutexes for long, so there should be little chance of a thread blocking on the mutex. An adaptive (spin-then- sleep) mutex should be perfect to build them on (I know you want them parallel to mtx, not built on them). There was also your comment: "I have also for data going through...on failure, simply queue... never block". Since you must acquire the mutex that protects the queue, I assume you mean you won't block anywhere else, and are describing the model I mention above? This is very similar to what I've been trying to get added to the UDI execution environment. Maybe in 1.02. [www.project-udi.org]** While not exactly "problems", I think you should explicitly mention the behavior patterns of your implementation: When there is a pending/active writer, the queue provides "fan-in" (put all requests on a single Q), but there is no way to "fan out" the queue to a pool of "reader threads" when the writer completes. Almost like you need a condition variable for idle reader threads to sleep on, which you signal whenever a writer completes (all while avoiding N CPUs pounding the mutex at exactly the same time...). But this probably isn't a problem: eventually the queue will empty, and it will empty read-only requests faster if more requests come in (each with another context to run items). So it will just start emptying them perhaps a little slower than it could, but saves a lot of overhead and complexity. If there are a lot of reader threads trying to run, a writer thread could possibly "livelock" before it gets to execute because a fastrack thread can break the condition for the writer thread to execute. Yes, the reader thread will then dequeue, but a new reader thread could break the condition for *that* thread. [Atomic-compare-and-swap could be used in acquire_read, but that would livelock the readers instead of a possible writer. More on atomic ops in a following email.] I also think a reader/writer implementation should provide an API to "upgrade" a reader lock to a writer lock, and to "downgrade" a writer lock to a reader lock. While I don't expect upgrades/ downgrades to occur often, they are sometimes necessary. For example, if I process incomming packets and pass them on, but I queue out-of-order packets internally, I need to upgrade to a writer lock to append the packet to my Q. I don't like the "hack" of resending it to myself marked as a writer... Since it isn't always possible to know in advance if writer permissions are required, make it easy on people. Looking over your code, there were a few things that bothered me a little. The first was your not using the STAILQ macros, so I re-wrote it to use them instead of your manually-inlined expansions. Even if you save an instruction, the macros are SO much easier to read... I may have changed the behavior slightly (I went more by your comments than the pointer-munging code). STAILQ macros are properly protected the the mutex, just like your code. I also re-wrote the code to make "cpp" do the math: instead of relying on a binary carry to set the correct bit, I add the correct value and subtract the old one. Code gen is the same, but the C source is more readable and doesn't require the special bit placements. Atomic "set" and "clear" operations could also be used, but then it might require two operations (second to increment the reader count). Since I got "flag" and "flags" mixed up once, I renamed them to make it clear which was which (q_flags, el_flags; still not happy with the names). Fixed a couple spelling typos while I was at it. I noticed that "dummy" assumed that inputs were always read-only. Modified it to check and acquire writer perms if they were needed (since writers come in *somewhere*; I know it is just example code, but I wanted it to be more "real"). Once I did all that, it was much easier for me to "see" what was going on with the code. I think I've found a race condition in the code that can lead to a writer AND a reader being active at the same time: the problem is the queue flags are both manipulated by (multiple) atomic operations and protected by the mutex. It appears possible that while a thread is in acquire_write(), after the check ((ngq->q_flags & ~SINGLE_THREAD_ONLY) == 0) is true, but before WRITER_ACTIVE is added to q_flags, a fastrack reader can come in, atomically add READER_INCREMENT, and verify that there isn't a writer active. Then, the writer becomes active and executes. I'm sending my modified version to Julian off-line. He can take as many of my changes as he wants. Email him or me if you'd like a copy. Kevin ** [I work on UDI drivers (and some on the spec) during the day. UDI's execution environment is a little "strange", but consists of only a single non-blocking request active in a "region" at a time. I want to extend it to allow multiple "read only" requests or a single writer request. A "read-only" request in UDI probably looks different from in netgraph or FreeBSD, though. One problem with RW locks in UDI is that there is typically a single "writer" operation required: add or remove an element from a queue, which is protected by the execution environment.] To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-smp" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200101020402.VAA12154>