Re: TTY changes to 2.1.65

Re: TTY changes to 2.1.65

[Joerg Rade]

Hi Rik,

> Send Linux memory-management wishes to me: I'm currently looking
> for something to hack...

How about something like a garbage collection for interpreted
languages, i.e. GNU-Smalltalk or Java?  As Paul Wilson in his article
below pointed out, linux would be a suitable platform.

grtnx -j|g
--
    Joerg Rade   | How could I know what I say | jr@petz.han.de 
   Birkenstr. 32 | before I hear what I think? | +49 511 9887497
D-30171 Hannover +-----------------------------+ S: Schlaegerstr. 
----8<----
From: wilson@cs.utexas.edu (Paul Wilson)
Newsgroups: comp.arch,comp.lang.misc,comp.lang.smalltalk
Subject: hardware (and OS) support for memory management (was Re: The Architect's Trap)
Date: 21 Jul 1997 17:58:01 -0500
Organization: CS Dept, University of Texas at Austin
Lines: 150
Message-ID: <5r0php$97b$1@roar.cs.utexas.edu>
References: <5m4oqi$eer@darkstar.ucsc.edu<33C98CAD.41C6@iil.intel.com<5qodsl$gt1@bcarh8ab.bnr.ca<33CFD939.446B9B3D@eng.adaptec.com>
NNTP-Posting-Host: roar.cs.utexas.edu
Ident-User: wilson

In article <33CFD939.446B9B3D@eng.adaptec.com>,
Greg Gritton x2386  <gregory@eng.adaptec.comwrote:
>Hi,
>
>It is improtant to know the whole story.
>The SOAR chip, described in the "What Price Smalltalk"
>by Ungar and Patterson (IEEE Computer, Januar 1987, pages 67-74)
>contains a number of innovative features designed to run
>Smalltalk faster compared to a simpler RISC processor
>of the time, such as MIPS.  After investigating the speed increases
>derived from various features, they found that many of the
>features weren't worthwhile.  However, they found other
>features to be very whorthwhile.  The valuable features included 
>register windows  and trapping arithmetic instructions.

This isn't the whole story.  As I recall, Ungar concluded that
3 features were worthwhile (register windows, trapping arithmetic
instructions, and hardware support for a generational GC write
barrier)---but since then, the value of those features has
been called into question, too.

Register windows are regarded by many as unnecessary, and were
originally motivated by statistics from code generated by compilers
that are now obsolete.  

Tagged arithmetic instructions can be useful, but alternatives
exist, including having word loads trap when the address is
not word-aligned.  (You can fiddle the tag representations
to ensure that the tag is stripped out by an immediate
instruction-stream constant, and an unaligned load exception
is generated if in fact it wasn't the right tag.)  At least
one commercial Lisp systems for the SPARC didn't use the
special SPARC tags because the implementors wanted three-bit
tags, rather than the hardware-supported two.

The GC write barrier is now usually implemented in software,
which often has better performance than Ungar's original
write barrier did with hardware support.  (Ungar's minimal
hardware support was fast in the common case stressed by
the Smalltalk macro benchmarks, but is slow in cases that
can be common in some other programs.  Ungar et al. adopted
a card-marking write barrier that's implemented purely
in software, and is very fast.)

Interestingly, Ungar and his students have done an excellent
job of developing software-only techniques for compiling
OOP languages, notably the Self compilers (first with Craig
Chambers and later with Urs Hoelzle) and Chambers' Vortex
compiler for the Cecil language (and other languages).

When it comes to GC support, please don't go designing special
purpose hardware without reading my GC survey (the long version
available from our web site, <http://www.cs.utexas.edu/users/oops>).
Different kinds of GC's benefit from different kinds of write
barriers, and it's unclear what's worth putting in hardware,
if anything.

My own vote for "most worthwhile hardware for memory management"
is sub-page protections in the TLB, e.g., 1-KB independently-protectable
units withing 4KB or 8KB pages, like the ARM 6xx series.  And VERY FAST
traps.  And please don't make the pages bigger.  (And get the OS kernel
people to support querying which pages are dirty, and VERY FAST USER-LEVEL
TRAPS.)

These features are desirable for a lot of things, including:

  1. persistence (pointer swizzling at page fault time)
  2. checkpointing dirty pages (for fault-tolerance, process migration 
     persistence, and time-travel debugging),
  3. distributed virtual memory, 
  4. GC read and write barriers, 
  5. redzoning to detect array overruns in debugging mallocs and buffer
     overruns in networking software,
  6. compressed caching virtual memory,
  7. adaptive clustering of VM pages,
  8. overlapping protection domains (e.g., in single-address-space OS's,
     or runtime systems with protection and sharing, or for fast
     path communications software that avoids unnecessary copies),
  9. pagewise incremental translation of code from bytecodes (or existing
     ISA's) to VLIW or whatever,
  10. incremental changing of data formats for sharing data across
      multicomputers (switching endianness, pointer size, etc.) or
      networks,
  11. memory tracing and profiling,
  12. incremental materialization of database query results in
      a representation normal programs can handle
  13. copy-on-write, lazy messaging, etc.
  14. remote paging against distributed RAM caches

  and I'm sure lots of other stuff.

(Papers on some of these topics are available from our web site too.)

I view the TLB as a very general-purpose piece of parallel hardware.
You can really make it do lots of tricks for you to implement
fancy memory abstractions cheaply.  There are lots of things for
which a TLB can give you zero-cost checking in the common
case, and trap to software in the uncommon cases.

If you're going to do anything more radical than a nicer TLB
(and unaligned load trapping), you might want to think really
hard about how to expose some of the memory-managment hardware
in ways that can serve multiple purposes.  For example, people
at Wisconsin (I believe) messed with the ECC bits on some
machine or other (CM-5?) to cause fine-grained traps on
word accesses.  The Symbolics machines checked extra tag
bits when doing cache lookups, to implement some forms of tagged
memory with zero time cost and fairly small hardware cost.

I'd be very interested in hardware that let you program a
little PLA that did the checking of the cache tag RAM, so
that you could use it for ECC if you wanted, or fine-grained
coherency, or any of a zillion other things.  The basic idea
would be to use a little more hardware to get a lot more
flexibility in what your TLB, cache dictionaries etc. are already 
doing.

I'd think it'd be worth putting a programmable state machine
in a PLA, with excruciatingly fast traps to something like PAL code to
sort out the uncommon cases.  (I seem to recall seeing something
like this idea for cache consistency protocols.  It has advantages
both in flexibility and in the ability to improve the coherence logic
after the hardware is built.)

I'm not a CPU design expert, though, so I'm not clear on
how hairy this would be.

For it to be generally useful, it would also be important to get the OS
guys on board.  Some OS's (e.g., Solaris) have laughably slow VM trap
handling as it is, even when the hardware is fine.  (How can you spend
so many thousands of cycles in the kernel to figure out that the user
has a handler for an access-protection trap?  Hyeesh.)

This is definitely due in part to the lack of benchmarks that stress
these aspects of a system.  Some OS's (e.g., Linux) are several times
faster than some others (e.g., Solaris), and some kernels (e.g., L4)
are much faster still.  This doesn't show up in SPECmarks.

I think it's time that everybody realized that the TLB they already
have can support much more sophisticated software, and do it
efficiently---and then started banging on their OS vendors to realize
that TLB's aren't just for disk paging anymore.  Concurrently, TLB's
should get better to support finer-grained uses than current TLB's 
can.

-- 
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wilson@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and  Scheme interpreters and compilers available via ftp from 
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)

VM ideas (was: Re: TTY changes to 2.1.65)

[Rik van Riel]

On Thu, 4 Dec 1997, Joerg Rade wrote:

> How about something like a garbage collection for interpreted
> languages, i.e. GNU-Smalltalk or Java?  As Paul Wilson in his article
> below pointed out, linux would be a suitable platform.

How does Linux know what is garbage and what isn't :)
The purpose of garbage collection is to avoid making loads
of syscalls, and doing stuff yourself (because only you know
what memory is being used for. 'process privacy policy' :)

[snip]

> My own vote for "most worthwhile hardware for memory management"
> is sub-page protections in the TLB, e.g., 1-KB independently-protectable
> units withing 4KB or 8KB pages, like the ARM 6xx series.  

Why?

> And VERY FAST traps.  

Of course, everything should be as fast as possible.

The two above suggestions actually contradict eachother,
you can't make the system more complex and faster at the
same time. The "no-free-lunch" principle is ever-present!

> And please don't make the pages bigger.  (And get the OS kernel
> people to support querying which pages are dirty, and VERY FAST USER-LEVEL
> TRAPS.)

Swapping is mainly slowed down by _latency_ problems. The
page size isn't that much of an issue any more, because:
- current PCs have large memory (>4000 pages) for which
  fine-grained management will COST performance (too complex)
- small pages will have HUGE latency problems
- large pages will be more easily manageable, but waste more space
- 4k seems to be 'just right' (optimal Goldylocks size)
- the demand for VSPM has shown that 4k isn't big enough for some cases
- in a VM system with more than 64k of pages, it is 'difficult' to
  select the best page to swap out, instead you swap out a good
  page... If you were to swap out a 16k unit at once, latency
  problems would be less, and performance might be better ???
- 1k units just are too complex when it's about disk swapping
  (for non-swappable memory it would/could be nice however)

> These features are desirable for a lot of things, including:
> 
>   1. persistence (pointer swizzling at page fault time)
nice.
>   2. checkpointing dirty pages (for fault-tolerance, process migration 
>      persistence, and time-travel debugging),
>   3. distributed virtual memory, 
DIPC is out... check your favorite web site...
>   4. GC read and write barriers, 
?
>   5. redzoning to detect array overruns in debugging mallocs and buffer
>      overruns in networking software,
?
>   6. compressed caching virtual memory,
VM is a latency based problem, during the wait period another
process can run... Wasting CPU time on VM is (IMHO) counterproductive.
Some people have reported _degraded_ performance with my vhand
patch...
>   7. adaptive clustering of VM pages,
this would be a Good Thing
>   8. overlapping protection domains (e.g., in single-address-space OS's,
>      or runtime systems with protection and sharing, or for fast
>      path communications software that avoids unnecessary copies),
?
>   9. pagewise incremental translation of code from bytecodes (or existing
>      ISA's) to VLIW or whatever,
nice when we get Linux to run on VLIW architectures
(but why don't we just recompile the programs?)
>   10. incremental changing of data formats for sharing data across
>       multicomputers (switching endianness, pointer size, etc.) or
>       networks,
this would be an awful lot of work, I wish you success :)
>   11. memory tracing and profiling,
nice.
>   12. incremental materialization of database query results in
>       a representation normal programs can handle
????
>   13. copy-on-write, lazy messaging, etc.
COW over network works counterproductive... It might save bandwidth,
but the latency problem it introduces isn't compensated by the
initial savings...
>   14. remote paging against distributed RAM caches
OK, this would be very nice. So nice that already people might
be working on it (not sure though).

> (Papers on some of these topics are available from our web site too.)

Hmm, I'll have a look.
> 
> I view the TLB as a very general-purpose piece of parallel hardware.
> You can really make it do lots of tricks for you to implement
> fancy memory abstractions cheaply.  There are lots of things for
> which a TLB can give you zero-cost checking in the common
> case, and trap to software in the uncommon cases.

abusing the TLB can be a very nice thing, but doesn't Linux
run on too many different types of architectures to make it
_really_ work... (or we'd have to do it on a per-arch level)

> I'm not a CPU design expert, though, so I'm not clear on
> how hairy this would be.

doing it (via software) on _existing_ architectures could be
_very_ _very_ hairy. An interesting project for a CS major though :))

> This is definitely due in part to the lack of benchmarks that stress
> these aspects of a system.  Some OS's (e.g., Linux) are several times
> faster than some others (e.g., Solaris), and some kernels (e.g., L4)
> are much faster still.  This doesn't show up in SPECmarks.

These functions aren't used _that_ often in real-life...

> I think it's time that everybody realized that the TLB they already
> have can support much more sophisticated software, and do it
> efficiently---and then started banging on their OS vendors to realize
> that TLB's aren't just for disk paging anymore.  Concurrently, TLB's

Great, using the TLB in a more flexible way.

> should get better to support finer-grained uses than current TLB's 
> can.

How can you improve the TLB from software??? I think this is
up to the hardware vendors (but I might be wrong)

grtz,

Rik.

----------
Send Linux memory-management wishes to me: I'm currently looking
for something to hack...

Re: VM ideas (was: Re: TTY changes to 2.1.65)

[David Mentre]

 Hello Rik,

Rik van Riel <H.H.vanRiel@fys.ruu.nl> writes:

> On Thu, 4 Dec 1997, Joerg Rade wrote:

[snip]
> > My own vote for "most worthwhile hardware for memory management"
> > is sub-page protections in the TLB, e.g., 1-KB independently-protectable
> > units withing 4KB or 8KB pages, like the ARM 6xx series.  
> 
> Swapping is mainly slowed down by _latency_ problems. The
[...]
 The interesting point of Joerg is that he see the TLB mecanism as a
more general mecanism than just to solve swapping problems.

> > These features are desirable for a lot of things, including:
[snip]
> >   3. distributed virtual memory, 
> DIPC is out... check your favorite web site...
[snip]

 As I'm a little involved in Distributed Shared Memories (with a PhD ;),
I couldn't let such an opportunity happen without talking. I totally
agree with Joerg. One problems with DSM is that you must track user
memory accesses to maintain coherency. Unfortunatly, fine grain access
like cache line is not available to the average system
programmer. Therefore sub-page protection could be very useful. 

 Regarding DIPC, I think we could improved a little the coherency
protocol. One big advantage of DIPC is that it provide code, and you
can't lie with code. :) I hope I'll have more code in the future to
explain my point of vue in DSM.

 david

-- 
 David.Mentre@irisa.fr -- CAPS research team - Irisa - France
      Personal info: http://www.irisa.fr/prive/mentre/	
  Professional info: http://www.irisa.fr/caps/PEOPLE/David/

Re: VM ideas (was: Re: TTY changes to 2.1.65)

[Rik van Riel]

On 9 Dec 1997, David Mentre wrote:

>  The interesting point of Joerg is that he see the TLB mecanism as a
> more general mecanism than just to solve swapping problems.

OK...

>  As I'm a little involved in Distributed Shared Memories (with a PhD ;),
> I couldn't let such an opportunity happen without talking. I totally
> agree with Joerg. One problems with DSM is that you must track user
> memory accesses to maintain coherency. Unfortunatly, fine grain access
> like cache line is not available to the average system
> programmer. Therefore sub-page protection could be very useful. 

I admit I haven't thought of that... Not having this might
be analogous to the bouncing-cache-line problem slab development
was confronted with (or just avoided?)

>  Regarding DIPC, I think we could improved a little the coherency
> protocol. One big advantage of DIPC is that it provide code, and you
> can't lie with code. :) I hope I'll have more code in the future to
> explain my point of vue in DSM.

Cool, we can always use good/beautiful code...
This is especially true when I can learn new things by
reading it.

Rik.

--
Send Linux memory-management wishes to me: I'm currently looking
for something to hack...