Date: Thu, 05 Sep 2002 00:55:29 -0700 From: Terry Lambert <tlambert2@mindspring.com> To: Julian Elischer <julian@elischer.org> Cc: Giorgos Keramidas <keramida@ceid.upatras.gr>, Bruce Evans <bde@zeta.org.au>, arch@FreeBSD.ORG Subject: Re: Process/thread states. Message-ID: <3D770DF1.623A84B0@mindspring.com> References: <Pine.BSF.4.21.0209042235470.34499-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Julian Elischer wrote:
> the state of being on the sleep queue can occur in parallel with the other
> states, e.g. on the run queue, or running or on the suspend queue.
> Sleeping is really only being on the sleep queue without any other
> state taking precedence.
> This means that to truely represent the queue and run states of a thread
> the state variable consists of a state field with several values
> and a separate bit that represents the background reality of it also being
> on the sleep queue, and thus able to be awoken. There are also
> possibilities that a thread having been swapped out (as part of a process)
> that must also be kept orthogonal to whether the thread is suspended or
> sleeping or runnable. if this really does turn out to be the case
> REAL thread state tracking requires 3 orthognal tests. For this reason I
> want touse a macro to allow,
> 1/ experimentation on how thisis best done
> 2/ hiding of the sometime messy tests with meaningful named abstractions.
To me this seems to introduce a bitfield/other-field-contents
synchroniztion problem that wasn't there before. Effectively,
you are saying that the value of the bit follows the change from
NULL-to-non-NULL and non-NULL-to-NULL. There is an implicit race
that happens, unless both objects are protected by the same mutex.
In the case of a direct compare with the object itself, then there
is not race in the following field.
Bruce made the point that debugging such macros is arbitrarily
hard. This is true because, even if you ensure that the order
of operation is always set A/set B, unset B/unset A, your macro
used in the comparator functions has to be consistent... and also
used consistently. In other words, there is an implied semantic
on use, when there is a combined state comparison, which is not
explicit in the transitions between states themselves (assuming
your state is represented by the "and" or "xor" of two pieces of
information). There are several cases in the code in question
where there are comparisons which fail. Specifically, the negation
of the macro operation requires inverse ordering of the compared
values, in order to avoid introducing a "follower" race window.
It's possible to get this right, but it also means a lot of work;
IMO, it's not worth the implied semantics to get the simplified
"if" statements; you would basically need two macros, with one
order for the assertion, and the other order for the assertion
of the negation. The compiler can't enforce the use of the
correct semantics here, so it's easy for programmers to make
errors, e.g.:
if (!ASSERTION_STATEMENT(x))
vs.
if (NEGATION_STATEMENT(x))
that end up introducing incredibly small -- but still there --
race windows in the code, which will pop up as unrepeatable
errors suffered by one or two users, which "disappear" when a
printf() (or other timing-changing function) is introduced,
etc..
To my mind, it is better to multiply the states explicitly,
and use the product of the multiplication in the code. For
anything more than a two-by-two, this introduces more states
(2x3 := 5->6, 4x5 := 9->20, etc.). This means that a lot of
care will have to be taken in the code. On the plus side, it
means that someone who comes after you is not going to screw
things up accidently by missing some required semantics that
the compiler is unable to enforce. It's also possible to
reduce the total number of states by eliminating "impossible"
states (e.g. with a Karnot map), so the increase in total
states is not necessarily really any greater than it would
have been the other way.
> > Neither one of these works properly if there is more than
> > one bit hidden in either of these; you have to get a lot more
> > complicated:
>
> this one could be real:
> if ((td->td_wchan == 0) && (td->td_state & TD_ST_MASK == TDS_UNQUEUED) &&
> ((td->td_state & TDS_SWAPPED) == 0))
> setrunnable(td);
>
> I'd rather make it
>
> if (td_on_sleepq_only(td) && !td_is_swapped(td))
> setrunnable(td);
>
> Isn't that somewhat easier to understand?
Yes. But it falls into the negation case race problem. A similar
condition elsewhere:
if (!td_on_sleepq_only(td) || td_is_swapped(td))
do_something(td);
is actually a potential race, unless it's:
if(td_is_swapped(td) || !td_on_sleepq_only(td))
...but it's worse than that. By compressing the state compare into a
single macro, you lock the order of operation. The only legitimate
way to do this is if you have a mutex that protects the contents of
td->td_state, since there is no way that you can guarantee that both
elements will be updated atomically otherwise. The order of the
update becomes important, if the condition is not exactly equal to
the example. Further, I would argue that the use of a lowercase
macro obfuscates the idea of atmoicity -- atomicity is implied, but
not actually guaranteed over (possible) kernel preemption (e.g. a
thread on another CPU explcitly killing the thread in question
between one compare of td->td_state contents, and the other).
> > That *still* doesn't work if, say, TDS_XXX is a superset of the
> > bits in TDS_SUSPENDED.
>
> > I personally dislike the idea omf combined bits, without explicit
> > equality tests.
>
> I have no idea what you mean by that.
When you defined your manifest constants, you defined them as the
logical OR of a number of bits in your enumerated type declaration;
this means that one set of bits could be a subset of another. Even
if you have a mask and two flag bits on a value, this is a problem.
To make something up:
enum {
foo = 75 | 0x10000000,
fum = 75 | 0x10000000 | 0x20000000,
...
}
This is actually *likely*, given that people will tend to add bits
as time goes on.
> > The problem that's trying to be solved here is the one of how
> > do you represent a combinatorial state in a single comparison,
> > and the equivalency of one combinatorial state and another for
> > the purposes of whether or not some code should be run (as in
> > this specific case).
> >
> > The reality is probably that this state should be explicitly
> > multiplied out in the code, so that it becomes a single value
> > compare.
>
> sometimes you want otherwise.. e.g.
> What is the base state REGARDLESS of whether it is on the sleep queue.
I would argue that the compare of the sleep queue entry pointer
to NULL is the *ideal* was to get this information. 8-).
-- Terry
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3D770DF1.623A84B0>