Re: Lock EVERYTHING (for testing) [was: Re: Scaling noise]

Re: Lock EVERYTHING (for testing) [was: Re: Scaling noise]

[John Bradford]

> The analogy for Linux is this:  At a machine level, we add a check to 
> EVERY access.  The check is there to ensure that every memory access is 
> properly locked.  So, if some access is made where there isn't a proper 
> lock applied, then we can print a warning with the line number or drop 
> out into kdb or something of that sort.
>
> I'm betting there's another solution to this, otherwise, I wouldn't 
> suggest such an idea, because of the relative amount of work versus 
> benefit.  But it may require massive modifications to GCC to add this 
> code in at the machine level.

Couldn't Valgrind be modified to do this for the kernel?

http://developer.kde.org/~sewardj/

John.

Re: Lock EVERYTHING (for testing) [was: Re: Scaling noise]

[Jeremy Fitzhardinge]

On Wed, 2003-09-10 at 08:47, John Bradford wrote:
> > The analogy for Linux is this:  At a machine level, we add a check to 
> > EVERY access.  The check is there to ensure that every memory access is 
> > properly locked.  So, if some access is made where there isn't a proper 
> > lock applied, then we can print a warning with the line number or drop 
> > out into kdb or something of that sort.
> >
> > I'm betting there's another solution to this, otherwise, I wouldn't 
> > suggest such an idea, because of the relative amount of work versus 
> > benefit.  But it may require massive modifications to GCC to add this 
> > code in at the machine level.
> 
> Couldn't Valgrind be modified to do this for the kernel?
> 
> http://developer.kde.org/~sewardj/

I have a UML-under-Valgrind project on the backburner.  Valgrind has an
instrumentation mode which checks to see every memory access is covered
by appropriate locks in an MT program.  I'm afraid it will generate a
lot of noise in the kernel though, since there's a lot of code which
does unlocked memory access (probably correctly).

	J

Scaling noise

[Larry McVoy]

I've frequently tried to make the point that all the scaling for lots of
processors is nonsense.  Mr Dell says it better:

    "Eight-way (servers) are less than 1 percent of the market and shrinking
    pretty dramatically," Dell said. "If our competitors want to claim
    they're No. 1 in eight-ways, that's fine. We want to lead the market
    with two-way and four-way (processor machines)."

Tell me again that it is a good idea to screw up uniprocessor performance
for 64 way machines.  Great idea, that.  Go Dinosaurs!
-- 
---
Larry McVoy              lm at bitmover.com          http://www.bitmover.com/lm

Re: Scaling noise

[Martin J. Bligh]

> Err, when did I ever say it wasn't SSI?  If you look at what I said it's
> clearly SSI.  Unified process, device, file, and memory namespaces.

I think it was the bit when you suggested using bitkeeper to sync multiple
/etc/passwd files when I really switched off ... perhaps you were just
joking ;-) Perhaps we just had a massive communication disconnect.
 
> I'm pretty sure people were so eager to argue with my lovely personality
> that they never bothered to understand the architecture.  It's _always_
> been SSI.  I have slides going back at least 4 years that state this:
> 
> 	http://www.bitmover.com/talks/smp-clusters
> 	http://www.bitmover.com/talks/cliq

I can go back and re-read them, if I misread them last time than I apologise.
I've also shifted perspectives on SSI clusters somewhat over the last year. 
Yes, if it's SSI, I'd agree for the most part ... once it's implemented ;-)

I'd rather start with everything separate (one OS instance per node), and
bind things back together, than split everything up. However, I'm really
not sure how feasible it is until we actually have something that works.

I have a rough plan of how to go about it mapped out, in small steps that
might be useful by themselves. It's a lot of fairly complex hard work ;-)

>> Numbers would be cool ... particularly if people can refrain from the
>> "it's worse, therefore it must be some scalability change that's at fault"
>> insta-moron-leap-of-logic.
> 
> It's really easy to claim that scalability isn't the problem.  Scaling
> changes in general cause very minute differences, it's just that there
> are a lot of them.  There is constant pressure to scale further and people
> think it's cool.  You can argue you all you want that scaling done right
> isn't a problem but nobody has ever managed to do it right.  I know it's
> politically incorrect to say this group won't either but there is no 
> evidence that they will.

Let's not go into that one again, we've both dragged that over the coals
already. Time to agree to disagree. All the significant degredations I
looked at that people screamed were scalability changes turned out to
be something else completely. 
 
> Instead of doggedly following the footsteps down a path that hasn't worked
> before, why not do something cool?  The CC stuff is a fun place to work,
> it's the last paradigm shift that will ever happen in OS, it's a chance 
> for Linux to actually do something new.  I harp all the time that open
> source is a copying mechanism and you are playing right into my hands.
> Make me wrong.  Do something new.  Don't like this design?  OK, then come
> up with a better design.

I'm cool with doing SSI clusters over NUMA on a per-node basis. But it's
still vapourware ... yes, I'd love to work on that full time to try and
change that if I can get funding to do so.

M.

Re: Scaling noise

[Larry McVoy]

On Wed, Sep 03, 2003 at 08:50:46AM -0700, Martin J. Bligh wrote:
> > Err, when did I ever say it wasn't SSI?  If you look at what I said it's
> > clearly SSI.  Unified process, device, file, and memory namespaces.
> 
> I think it was the bit when you suggested using bitkeeper to sync multiple
> /etc/passwd files when I really switched off ... perhaps you were just
> joking ;-) Perhaps we just had a massive communication disconnect.

I wasn't joking, but that has nothing to do with clusters.  The BK license
has a "single user is free" mode because I wanted very much to allow distros
to use BK to control their /etc files.  It would be amazingly useful if you
could do an upgrade and merge your config changes with their config changes.
Instead we're still in the 80's in terms of config files.

By the way, I could care less if it were BK, CVS, SVN, SCCS, RCS,
whatever.  The config files need to be under version control and you
need to be able to merge in your changes.  BK is what I'd like because
I understand it and know it would work, but it's not a BK thing at all,
I'd happily do work on RCS or whatever to make this happen.  It's just
amazingly painful that these files aren't under version control, it's
stupid, there is an obviously better answer and the distros aren't
seeing it.  Bummer.

But this has nothing to do with clusters.

> > I'm pretty sure people were so eager to argue with my lovely personality
> > that they never bothered to understand the architecture.  It's _always_
> > been SSI.  I have slides going back at least 4 years that state this:
> > 
> > 	http://www.bitmover.com/talks/smp-clusters
> > 	http://www.bitmover.com/talks/cliq
> 
> I can go back and re-read them, if I misread them last time than I apologise.
> I've also shifted perspectives on SSI clusters somewhat over the last year. 
> Yes, if it's SSI, I'd agree for the most part ... once it's implemented ;-)

Cool!

> I'd rather start with everything separate (one OS instance per node), and
> bind things back together, than split everything up. However, I'm really
> not sure how feasible it is until we actually have something that works.

I'm in 100% agreement.  It's much better to have a bunch of OS's and pull
them together than have one and try and pry it apart.

> I have a rough plan of how to go about it mapped out, in small steps that
> might be useful by themselves. It's a lot of fairly complex hard work ;-)

I've spent quite a bit of time thinking about this and if it started going
anywhere it would be easy for you to tell me to put up or shut up.  I'd 
be happy to do some real work on this.  Maybe it would just be doing the 
architecture stuff but I strongly suspect there are few people out there
masochistic enough to make controlling tty semantics work properly in this
environment.  I don't want to do it, I'd love someone else to do it, but 
if noone steps up to the bat I will.  I did all the POSIX crud in SunOS,
I understand the issues, I can do it here and it is part of the least fun
work so if I'm pushing the model I should be willing to put some work into
the non fun part.

The VM work is a lot more fun, I'd like to play there but I suspect that if
we got rolling there are far more talented people who would push me aside.
That's cool, the best people should do the work.
-- 
---
Larry McVoy              lm at bitmover.com          http://www.bitmover.com/lm

Re: Scaling noise

[Daniel Phillips]

On Thursday 04 September 2003 02:49, Larry McVoy wrote:
> It's much better to have a bunch of OS's and pull
> them together than have one and try and pry it apart.

This is bogus.  The numbers clearly don't work if the ccCluster is made of 
uniprocessors, so obviously the SMP locking has to be implemented anyway, to 
get each node up to the size just below the supposed knee in the scaling 
curve.  This eliminates the argument about saving complexity and/or work.

The way Linux scales now, the locking stays out of the range where SSI could 
compete up to, what?  128 processors?  More?  Maybe we'd better ask SGI about 
that, but we already know what the answer is for 32: boring old SMP wins 
hands down.  Where is the machine that has the knee in the wrong part of the 
curve?  Oh, maybe we should all just stop whatever work we're doing and wait 
ten years for one to show up.

But far be it from me to suggest that reality should intefere with your fun.

Regards,

Daniel

Re: Scaling noise

[Larry McVoy]

On Thu, Sep 04, 2003 at 04:21:16AM +0200, Daniel Phillips wrote:
> On Thursday 04 September 2003 02:49, Larry McVoy wrote:
> > It's much better to have a bunch of OS's and pull
> > them together than have one and try and pry it apart.
> 
> This is bogus.  The numbers clearly don't work if the ccCluster is made of 
> uniprocessors, so obviously the SMP locking has to be implemented anyway, to 
> get each node up to the size just below the supposed knee in the scaling 
> curve.  This eliminates the argument about saving complexity and/or work.

If you thought before you spoke you'd realize how wrong you are.  How many
locks are there in the IRIX/Solaris/Linux I/O path?  How many are needed for
2-4 way scaling?  

Here's the litmus test: list all the locks in the kernel and the locking
hierarchy.  If you, a self claimed genius, can't do it, how can the rest
of us mortals possibly do it?  Quick.  You have 30 seconds, I want a list.
A complete list with the locking hierarchy, no silly awk scripts.  You have
to show which locks can deadlock, from memory.

No list?  Cool, you just proved my point.
-- 
---
Larry McVoy              lm at bitmover.com          http://www.bitmover.com/lm

Re: Scaling noise

[David S. Miller]

On Wed, 3 Sep 2003 19:46:08 -0700
Larry McVoy <lm@bitmover.com> wrote:

> Here's the litmus test: list all the locks in the kernel and the locking
> hierarchy.  If you, a self claimed genius, can't do it, how can the rest
> of us mortals possibly do it?  Quick.  You have 30 seconds, I want a list.
> A complete list with the locking hierarchy, no silly awk scripts.  You have
> to show which locks can deadlock, from memory.
> 
> No list?  Cool, you just proved my point.

No point Larry, asking the same question about how the I/O
path works sans the locks will give you the same blank stare.

I absolutely do not accept the complexity argument.  We have a fully
scalable kernel now.  Do you know why?  It's not because we have some
weird genius trolls writing the code, it's because of our insanely
huge testing base.

People give a lot of credit to the people writing the code in the
Linux kernel which actually belongs to the people running the
code. :-)

That's where the other systems failed, all the in-house stress
testing in the world is not going to find the bugs we do find in
Linux.  That's why Solaris goes out buggy and with all kinds of
SMP deadlocks, their tester base is just too small to hit all
the important bugs.

FWIW, I actually can list all the locks taken for the primary paths in
the networking, and that's about as finely locked as we can make it.
As can Alexey Kuznetsov...

So again, if you're going to argue against huge SMP (at least to me),
don't use the locking complexity argument.  Not only have we basically
conquered it, we've along the way found some amazing ways to find
locking bugs both at runtime and at compile time.  You can even debug
them on uniprocessor systems.  And this doesn't even count the
potential things we can do with Linus's sparse tool.

Lock EVERYTHING (for testing) [was: Re: Scaling noise]

[Timothy Miller]

David S. Miller wrote:

> 
> So again, if you're going to argue against huge SMP (at least to me),
> don't use the locking complexity argument.  Not only have we basically
> conquered it, we've along the way found some amazing ways to find
> locking bugs both at runtime and at compile time.  You can even debug
> them on uniprocessor systems.  And this doesn't even count the
> potential things we can do with Linus's sparse tool.


Pardon me for suggesting another idea for which I have no code written, 
but I was just wondering...

Is there a way we could get gcc to wrap EVERY memory access with some 
kind of debug lock?

Actually, I do have code, but for another application.  I designed a 
graphics drawing engine which has a FIFO for commands.  Before sending 
commands, you have to be sure there is enough free space in the FIFO, so 
there is a macro we use which tries to do this in an efficient way. 
Anyhow, there have been instances where we didn't check for enough space 
or didn't check for space at all, etc., and those bugs have been 
sometimes hard to find.

Two macros involved are CHECK_FIFO and WRITE_WORD.  Normally, CHECK_FIFO 
just checks for space, and WRITE_WORD just writes a word (it's more 
complicated than that, but never mind).  However, we have a second set 
of macros which check to make sure we're doing everything right.  The 
"check checker" macros have CHECK_FIFO set a counter and WRITE_WORD 
decrement that.  (Again, a bit more complex than that.)  If the counter 
ever goes below zero, we know we screwed up and exactly where.  Another 
thing we have is a way to indicate that we know we're doing something 
that looks like it may violate the normal way of things but really 
doesn't (for instance, sometimes, we write fewer words than we check 
for, and that is something we still print warnings about, but not in the 
cases where it's intentional).

The analogy for Linux is this:  At a machine level, we add a check to 
EVERY access.  The check is there to ensure that every memory access is 
properly locked.  So, if some access is made where there isn't a proper 
lock applied, then we can print a warning with the line number or drop 
out into kdb or something of that sort.

I'm betting there's another solution to this, otherwise, I wouldn't 
suggest such an idea, because of the relative amount of work versus 
benefit.  But it may require massive modifications to GCC to add this 
code in at the machine level.

Perhaps an even better solution would be to run an emulator.  Anyone 
know of a 686 emulator I can compile for intel?  The emulator could be 
modified to track locks and determine if any accesses are made without 
proper locks.

And another option that I could REALLY sink my teeth into.  If there was 
a 686 implementation in Verilog that I could run on an FPGA, it would be 
an order of magnitude slower than a real CPU, but still faster than an 
emulator.

One idea is to have something which can run 686 ISA that fits in a 
Virtex 1000 and runs at maybe 66mhz.  We put that with some adaptor 
board into an old dual processor PC that expects a Pentium Pro with a 
66mhz FSB.

That's probably overly ambitious, although I do do chip design for a 
living, so it's not entirely beyond the realm of possibility.

One problem is that we need to have metadata about memory accesses so we 
can track the difference between accesses which are to memory private to 
a CPU (no lock required) and accesses which are to shared memory (lock 
required) so we can determine what is a violation.  The FPGA daughter 
board would have to have its own RAM on it to track that.

And that leads me to another idea:  Reprogramming Transmeta processors 
to do all that.  :)