Re: [9fans] Virtual memory & paging

Re: [9fans] Virtual memory & paging

[geoff]

I didn't say that "we can't write an implementation without bugs",
merely that the existing implementations I'm familiar with have
made the system slower (e.g., adding shared libraries in SunOS 4.0
hugely slowed down the fork system call of even the smallest possible process),
added complexity to the system and for the users (more kernel code,
two sets of libraries [shared and unshared], static vs. dynamic link
decisions, run-time loader paths, extra process start-up processing),
usually coped poorly with set-id programs, and the extra complexity made
the system more fragile in single-user mode (you need all the right
shared libraries on the root filesystem) and when manipulating libraries
generally.  So I don't believe I've seen an existence proof that shared
libraries can do more good than harm; maybe they can, but given the
evidence to date, I'm skeptical.  And given that we (outside the Labs anyway)
don't have the problem that made people add shared libraries to Unix, X,
and that our binaries are at least competitive in size with systems that do
have shared libraries, and that one can just add RAM cheaply to avoid swapping
anyway, why bother?  Adding unneeded goo like shared libraries to a system
just makes it bigger, at minimum.  Depending upon the quality of the implementation,
it may also make it slower, more complex and fragile, and create new security holes.

Such a deal.

Re: [9fans] Virtual memory & paging

[Boyd Roberts]

geoff@collyer.net wrote:
> Such a deal.

Yeah, just put truss/strace on any shared libary binary.  I assume
that all those mmap()s are to map the libraries in and each one of
those is a _system call_, plus all the stat/open's to find them.

It's a lot quicker (and simpler) in the kernel to get exec to do
the necessary.

Re: [9fans] Virtual memory & paging

[david presotto]

Actually, I'ld be seriously worried about our ability to
add DLL support without major bugs.  It adds a lot
of complexity that spans the VM model, security,
and compilers.  A lot of Plan 9's speed and usefulness
arises from its simplicity and this would be a major step in
away from that, not that we haven't been whores 
before.

A major drawback right now is that, unless we change
our MMU handling in a drastic way,
we have to run the shared library at the same addresses
in all programs.   Might be a bit of a problem (unless we
go to 64 bit addressing).  The current MMU
model with its lazy evaluation and no need for a
intermachine shootdown is quite elegant and I'm not sanguine
to lose it just for DLL's.

As Geoff states, we don't seem to be losing out by not
having them, vis a vis memory size.  Some things would
be more efficiently done with a shared library, shared
databases for example.  I'm just not yet prepared to
pay the price in increased complexity.  Others may be.

Re: [9fans] Virtual memory & paging

[Richard Uhtenwoldt]

Geoff Collyer:

> > Given that degree of sharing, the low cost of RAM, and the increase in
> > OS complexity, slowness and insecurity in the implementations of
> > dynamic libraries that I've seen, I don't see a need for dynamic
> > libraries.

Ron Minnich

>and in the worst case you'll end up where GNU is now, with symbol
>versioning, 21 different versions of opendir in glibc, and so on an so on.
>Watching a simple 'ls' do hundreds of symbol fixups is really
>enlightening. Especially when so many of them are for the same symbol with
>slight variations on the name. My simple, formerly working, libc-based
>private name spaces are still totally hosed due to this nonsense.

Totally hosed because Linux moved from libc5 to glibc?

If so, you should have tried to fight the move.  Very little chance you
could have influenced *all* Linux users to stay with libc5, but you
easily could have influenced *me* to do so --you would have had to write
only one paragraph-- and probably a few hundred other Linux users, at
least for a year or 2 or 3, till the apps start not working with libc5.

I didn't know about your work on private namespaces for Linux until
about 3-6 months ago.  Can't recall exactly when.  I think I saw an
announce on Slashdot and short afterward you mentioned it here.

I subscribed to 9fans to find out about 9-coolness that gets added
to Linux and *BSD.
Where on the Net could I have found out earlier about your Linux work?

Re: [9fans] Virtual memory & paging

[Ronald G Minnich]

On Fri, 15 Feb 2002, Richard Uhtenwoldt wrote:

> I didn't know about your work on private namespaces for Linux until
> about 3-6 months ago.  Can't recall exactly when.  I think I saw an
> announce on Slashdot and short afterward you mentioned it here.

Well I tried once or twice to get papers on it published ca. 1996. It
finally got accepted at a conference in France in 1999, where I learned
just how bad my French has gotten as I tried to follow the talks. But I
got to speak in English, so nobody understood me either. Interesting. I
wonder what if anything I communicated :-) [[ Although in general French
CS researcher's English beats my French]]

The attitude in the US (and Usenix and DARPA) community until not long ago
was "what a stupid idea private name spaces are, you can hack that into
Unix with chroot/jail/whatever" (some reviewer's comments from various
Usenix conferences were just AMAZING). So I got to feel in miniature the
frustration the plan9 guys must have felt for the last decade+ trying to
get these ideas across ...

Not long ago it has started to move to "... we're doing that already" (as
recently stated by one of the Linux core guys, forwarded to me by
somebody). ah well. At least it's happening. (but all the other Unix
problems remain intact).

I actually started this work in the early 90s because while Unix is the
wrong way to build big distributed computing systems, I saw no way out of
the Unix box, and it seemed Plan 9 would never get unlocked. Of course,
now Grids are all the rage, and they're being built with Unix and NT
(s/Unix/Linux/ if you wish). And of course they're horribly insecure. And
nobody seems to want to talk about it -- it might interrupt funding, and
switching OSes is hard.

Just one example: in Globus, all remote users (according to a recent talk
I saw) run as the "GLOBUS user" (same integer UID -- think about it, it's
hard to do it many other ways on Unix). Imagine the following scenario: I
get on to a machine as a GLOBUS user, I fork, parent exits. I wait for
some other globus user, then I hijack them via ptrace. Then I do terrible
things to them -- including go after their files, etc. Easy, easy, easy
on Unix. Chroot has no power over the PID space.

So one proposed fix? Use DYNINST to rewrite the binary to dynamically
change all my system calls (system calls get forwarded, I guess, as in
Condor) so that the hijacker can't guess what you're doing. Sort of
encrypting system calls. It is claimed this is a good idea.

YUCK.

I pointed out to the speaker that if he built his system on Plan 9, this
type of thing is not an issue: no global integer UID space, no common
GLOBUS user, no global PID space, no hijack potential. Response: "Nobody
uses Plan 9, it's been shut down, nobody is working on it". My response,
in short: "bullshit". His response, "Yes but nobody is using it, we all
use Linux, so it doesn't matter if it is better". Gosh, I remember when
people said all this stuff about Unix.

"Meet the new boss, same as the old boss".

ron

Re: [9fans] Virtual memory & paging

[Fco.J.Ballesteros]

[-- Attachment #1: Type: text/plain, Size: 68 bytes --]

It still uses to be made; at least that's what I tell my students.

[-- Attachment #2: Type: message/rfc822, Size: 1557 bytes --]

From: forsyth@caldo.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Virtual memory & paging
Date: Mon, 4 Feb 2002 10:59:30 0000
Message-ID: <20020204110139.588D119999@mail.cse.psu.edu>

	I don't know that anyone else makes this distinction, but to me
	virtual memory is a technique an operating system can use to manage
	user memory, while paging is a technique for coping with a shortfall
	in physical memory.  VM manages memory by using page faults to fill in

it's a distinction that certainly used to be made when teaching operating systems.

Re: [9fans] Virtual memory & paging

[forsyth]

	I don't know that anyone else makes this distinction, but to me
	virtual memory is a technique an operating system can use to manage
	user memory, while paging is a technique for coping with a shortfall
	in physical memory.  VM manages memory by using page faults to fill in

it's a distinction that certainly used to be made when teaching operating systems.

Re: [9fans] Virtual memory & paging

[geoff]

There isn't a copy of the entire C library in every binary.  There is
a copy of each library routine called, directly or indirectly, by the
program in question.

Sharing of instructions is done at the granularity of process text
segments, as in V6 or V7 Unix.  The text segment of a process that
forks is shared between parent and child by page mapping.  Also,
running (via exec) a program multiple times concurrently causes the
(pure) text segment to be shared by page mapping across those
processes.  So all copies of rc and on a machine should share a text
segment.

Given that degree of sharing, the low cost of RAM, and the increase in
OS complexity, slowness and insecurity in the implementations of
dynamic libraries that I've seen, I don't see a need for dynamic
libraries.  (Remember that the real impetus for adding them to Unix
was X11 and its big and badly-factored libraries, which most of us
aren't blessed with.)  My terminal has 115 processes; all but 4 of
them share their text segment with at least one other process, usually
more.  74 of them are instances of rio, Mail, rc, acme, listen,
plumber and samterm.  A CPU server has 141 processes; all but 2 share
text.  80 of them are listen, another 21 are rc, exportfs, kfs, dns
and consolefs.  A quick sampling suggests that Plan 9 programs are
typically smaller than FreeBSD/386 programs even with shared
libraries.  Here are some FreeBSD sizes:

: unix; size /bin/cat /bin/ed /usr/bin/awk /usr/X11/bin/sam
   text    data     bss     dec     hex filename
  54188    4324    9760   68272   10ab0 /bin/cat
 122835    8772   81920  213527   34217 /bin/ed
 135761    4772   15756  156289   26281 /usr/bin/awk
  52525    1412   53448  107385   1a379 /usr/X11/bin/sam

Of those, awk and sam use shared libraries.  The corresponding Plan 9
sizes are:

; cd /bin; size cat ed awk sam
15996t + 2208d + 944b = 19148	cat
45964t + 4212d + 41232b = 91408	ed
114731t + 35660d + 12040b = 162431	awk
86574t + 7800d + 66240b = 160614	sam

and the Plan 9 programs cope with Unicode and UTF.

Re: [9fans] Virtual memory & paging

[Boyd Roberts]

geoff@collyer.net wrote:
> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.

Neither do I.  Didn't the tests show that the implementation of them
on unix actually made things slower and more memory got used, not less?

Virtual memory usually refers to the management of the memory when you
allow more 'memory' to be used than you have physical memory.  It always
implies a private virtual address space (unlike those Dragonball based
Palm things).

Hence you could have a private virtual address space but no virtual memory.
This would limit the size of the collection of processes on the machine to
not consume more that the amount of physical memory you had.

Once you have a private virtual address space [essential, except in certain
special cases] you can then manage the physical memory in any way you like.

Re: [9fans] Virtual memory & paging

[Boyd Roberts]

geoff@collyer.net wrote:
> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.

Oh, if it comes to DLLs, those things are 'orrible; every 'process'
shares the DLL's data segment.  That's one reason why it is impossible
to write a correct windows program.

Re: [9fans] Virtual memory & paging

[Andrew Simmons]

 That's one reason why it is impossible
>to write a correct windows program.
>
Another reason of course is that we Windows programmers are simply not very
bright.

Could anyone recommend a good book to help me remedy my profound ignorance
of these matters? I'm looking for a conceptual overview, nothing too heavy,
rather than something that will actually teach me how to write an OS.
Andrey mentioned Silberschatz & Galvin - would that fit the bill?

Re: [9fans] Virtual memory & paging

[Boyd Roberts]

Andrew Simmons wrote:
> Another reason of course is that we Windows programmers are simply not very
> bright.

There is that, but the environment is so hostile it really is hard.

> Could anyone recommend a good book to help me remedy my profound ignorance
> of these matters? I'm looking for a conceptual overview, nothing too heavy,
> rather than something that will actually teach me how to write an OS.
> Andrey mentioned Silberschatz & Galvin - would that fit the bill?

When I were a lad, we used this:

    Fundamentals of Operating Systems 
    By A. Lister

    Hardcover 
    161 Pages
    Edition: 3rd ed
    Published by Springer-Verlag New York, Incorporated
    Date Published: 09/1985
    ISBN: 0387912517

At 161 pages it makes it a 'readable' size.  The rest I picked up 'the hard way'
(tm) or from brucee or maltby.

Re: [9fans] Virtual memory & paging

[Richard Maxwell Underwood]

   I loathe memorizing petty details like
   which drawer has the soap and whether a constructor has to be declared
   in a private or public section of an object definition. I detest
   software designs that have special cases or exceptions. I'm always
   cursing Microsoft -- they seem to design all their software by random
   accretion of features.
   
   What's particularly odd to me is the pride some people take in their
   mastery of clutter. It's especially true of techies -- they love to
   indulge in the memorization of mountains of meaningless minutiae.
   Indeed, I suspect that the pride they take in this pap influences the
   design: software tools are most successful when they create a
   priesthood knowledgeable in the arcane incantations required.
   
   Perhaps this is all for the best -- after all, society can't afford a
   high ratio of geniuses to grunts. Perhaps society has come up with the
   perfect means of profitably employing those moiling masses of mental
   midgets. They're not dullards -- they're specialists! They may not
   understand much, but they certainly have gotten all the details of
   c++, HTML, Java, perl, Windows 95, or JCL down pat. So I don't want to
   be too hard on the mentality. But you must ask yourself where you fit
   into the grand scheme of things. Are you one of those moiling mental
   midgets, or do you seek grander things for yourself?
   
   The truth is simple and obvious: you can only think clearly when you
   purge your mind of clutter. Any real-world decision is impinged upon
   by milliards of factors, but turns on only a few. The ability to slice
   through all the secondary factors and zero in on the crucial ones is
   central to good decision-making.

-- 
Richard Maxwell Underwood
The Internet Is Missing!  http://www.satn.org/about/missinginternet.htm

Re: [9fans] Virtual memory & paging

[Thomas Bushnell, BSG]

geoff@collyer.net writes:

> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.  

Well, this sounds a little like "it's inherently buggy", which is
false.  If you don't trust yourself to write a shared library
implementation correctly, then say so, but I think the Plan 9 authors
are certainly capable of writing one that works right.

There may be other reason to not want them--as I'm sure the Plan 9
authors have chosen.  However, "we can't write an implementation
without bugs" is not a good reason.

Re: [9fans] Virtual memory & paging

[Ronald G Minnich]

> geoff@collyer.net writes:
> > Given that degree of sharing, the low cost of RAM, and the increase in
> > OS complexity, slowness and insecurity in the implementations of
> > dynamic libraries that I've seen, I don't see a need for dynamic
> > libraries.

and in the worst case you'll end up where GNU is now, with symbol
versioning, 21 different versions of opendir in glibc, and so on an so on.
Watching a simple 'ls' do hundreds of symbol fixups is really
enlightening. Especially when so many of them are for the same symbol with
slight variations on the name. My simple, formerly working, libc-based
private name spaces are still totally hosed due to this nonsense.

ron

Re: [9fans] Virtual memory & paging

[forsyth]

[-- Attachment #1: Type: text/plain, Size: 1019 bytes --]

there isn't a copy of the library in every executable because
the linker includes from the library only the functions the
program uses (directly or indirectly).   this is typically
smaller than the whole library.  there would be scope for some sharing
but the gain dynamically is typically small: not all the
executables in /386/bin are in use simultaneously.   after all, it's hard
to buy a machine with less than 64mbytes these days
and with plan 9 running rather a lot of that is free space, unless
you've got big memory applications such as ghostscript in which case
it's the application rather than the library that consumes the space.
i suppose if you'd got an enormous application library shared
by several applications in use at once you'd see more need
for library sharing.  in plan 9, that shared functionality might
be better represented as a file server (though not always).
dynamic linking might be of more interest (in Plan 9)
for selection amongst a set of implementations at run-time.


[-- Attachment #2: Type: message/rfc822, Size: 2323 bytes --]

To: 9fans@cse.psu.edu
Subject: Re: [9fans] Virtual memory & paging
Date: Sun, 3 Feb 2002 22:21:45 -0800
Message-ID: <20020203222145.A22998@ohio.river.org>

On Sun, Feb 03, 2002 at 03:08:39PM -0800, geoff@collyer.net wrote:
> Even if your physical memory were as large as your virtual address
> space, an obvious advantage to mapping addresses is [...]

> Another potential use of mapping is to avoid copying data by remapping
> pages.

Plan 9 has no DLLs.  It has a C runtime library.  I'm sure it's smaller
than the GNU C library, but is there a copy of the libary in every
executable in /bin?  

is there a copy of it in every
process's memory or is it shared among all the processses?

if so, is memory mapping how the sharing is effected?

(I know this is undergrad material.  Let me know if I should stop
asking elementary questions here.)

Re: [9fans] Virtual memory & paging

[geoff]

Even if your physical memory were as large as your virtual address
space, an obvious advantage to mapping addresses is to permit programs
linked to start at a fixed address (usually the second page of the
address space) to be run without first running a loading pass to
relocate all the addresses in the entire program.

In addition, memory management units normally provide varying forms of
protection for pages (e.g., instructions are usually made read- or
execute-only) and checking for out-of-bounds (unmapped) addresses.  On
many machines, notably the PC, a read from an address with no
corresponding memory (i.e., out-of-bounds) yields garbage; with memory
management on, many such references can be caught.  The MMU can thus
be used to ensure that a program doesn't access data in other programs
(including the kernel) without their consent.

Another potential use of mapping is to avoid copying data by remapping
pages.

I would turn the question around: when would you want a one-to-one
mapping of virtual to physical addresses?  There are a few such cases:
if memory serves, the old VAX 750 Plan 9 file server ran with the MMU
off because it runs no user-mode processes and it was found that
running with the MMU off made the machine run much faster.

Re: [9fans] Virtual memory & paging

[Andrew Simmons]

Thanks for that - it was a dumb question.

Re: [9fans] Virtual memory & paging

[Ronald G Minnich]

On Mon, 4 Feb 2002, Andrew Simmons wrote:

> Thanks for that - it was a dumb question.

actually not a dumb question I think. There have been supercomputers with
no VM hardware that were built, and the OS on these remapped (relinked)
executables at program load time, so as to avoid the overhead that you get
with VM (basically a bunch of logic in the address path). So in essence
the start address in your code and the address of your data would be
unique for each execution of your program.

Some of the more fancy ones wrapped base and bounds registers around each
program, and that was as far as protection went.

ron

Re: [9fans] Virtual memory & paging

[Richard Uhtenwoldt]

On Sun, Feb 03, 2002 at 03:08:39PM -0800, geoff@collyer.net wrote:
> Even if your physical memory were as large as your virtual address
> space, an obvious advantage to mapping addresses is [...]

> Another potential use of mapping is to avoid copying data by remapping
> pages.

Plan 9 has no DLLs.  It has a C runtime library.  I'm sure it's smaller
than the GNU C library, but is there a copy of the libary in every
executable in /bin?  

is there a copy of it in every
process's memory or is it shared among all the processses?

if so, is memory mapping how the sharing is effected?

(I know this is undergrad material.  Let me know if I should stop
asking elementary questions here.)

Re: [9fans] Virtual memory & paging

[presotto]

Virtual memory covers any memory that isn't laid out
exactly as it seems to an executing program, i.e., that
there exists some mapping between addresses as seen by the
execution unit and those on the bus to physical memory.

The mapping can happen a number of ways.  The two more
popular are via paging hardware or segmentation hardware.
Pages are typically fixed size and segments variable size.
 From the PDP-11 to the MIPS there have been enough flavors
that the distinction is a bit blurred.

If one is willing to move data between a backing store and
main memory in addition to chaging the mappings, one can
make the main memory appear larger than it really is.  This
is usually termed demand paging or demand segmentation.

An earlier technique, still in use in addition to demand paging/
segmentation is swapping.  If many processes are running on
a particular system, it may desirable to swap in main memory
one for another to give the illusion of a main memory that can
hold all of them.

And of course there is the even earlier technique of overlays.
Here one figures out the execution tree of routines in a
program.  One might note that routine A will never be an
ancestor of routine B or vice versa.  THerefore, there's no
requirement that they live in memory simultaneously and can
occupy the same memory locations, just at different times.

Re: [9fans] Virtual memory & paging

[Andrew Simmons]

At 16:53 3/02/2002 -0500, you wrote:
>Virtual memory covers any memory that isn't laid out
>exactly as it seems to an executing program, i.e., that
>there exists some mapping between addresses as seen by the
>execution unit and those on the bus to physical memory.
>
I hope this isn't too dumb a question, but given a sufficiently large
physical memory, what would be the advantage of anything other than a one
to one mapping of execution unit and physical addresses?

>And of course there is the even earlier technique of overlays.

I wish you hadn't mentioned those. I'd almost managed to forget about them.

Re: [9fans] Virtual memory & paging

[rob pike]

I don't know that anyone else makes this distinction, but to me
virtual memory is a technique an operating system can use to manage
user memory, while paging is a technique for coping with a shortfall
in physical memory.  VM manages memory by using page faults to fill in
the user address space; paging is just swapping a page at a time.  The
relationship between these notions is primarily that both permit the
process to execute when it is not entirely resident.

By these definitions, it is possible (easy even) to build a system
with virtual memory but no paging.  Even I can do it.

-rob

Re: [9fans] Virtual memory & paging

[skipt]

>
>By these definitions, it is possible (easy even) to build a system
>with virtual memory but no paging.  Even I can do it.
>
>-rob

I have an amateur question: how would that work?  would the compilers
need to cooperate for this to work?  How would something like a stray
pointer be handled?

I'm not sure if  "no paging" means no hardware memory management of
any kind.

Re: [9fans] Virtual memory & paging

[Ronald G Minnich]

On Mon, 4 Feb 2002 skipt@real.com wrote:

>
> >
> >By these definitions, it is possible (easy even) to build a system
> >with virtual memory but no paging.  Even I can do it.
> >
> >-rob
>
> I have an amateur question: how would that work?  would the compilers
> need to cooperate for this to work?  How would something like a stray
> pointer be handled?

see any old burroughs stack machine. Or the i286. Compilers do not
necessarily need to cooperate.

> I'm not sure if  "no paging" means no hardware memory management of
> any kind.

no, it just means no paging :-)

ron

Re: [9fans] Virtual memory & paging

[skipt]

>
>see any old burroughs stack machine. Or the i286. Compilers do not
>necessarily need to cooperate.

Do you mean systems that had hardware like this memory bank switch:

http://home.swipnet.se/~w-68269/z80_mmu.pdf


>> I'm not sure if  "no paging" means no hardware memory management of
>> any kind.
>
>no, it just means no paging :-)
>
>ron

I was confusing no-paging with no-hardware-mmu.

P.S. Would you believe that there is a memorymanagement.org, dedicated
to the subject?

Re: [9fans] Virtual memory & paging

[Ronald G Minnich]

On Mon, 4 Feb 2002 skipt@real.com wrote:

> >see any old burroughs stack machine. Or the i286. Compilers do not
> >necessarily need to cooperate.
>
> Do you mean systems that had hardware like this memory bank switch:
>
> http://home.swipnet.se/~w-68269/z80_mmu.pdf

actually just about everybody did that one with the z80. Lots of
companies (HP, TI, etc.) used z80s in embedded service, and ca. 1981 began
to put in bank-switch schemes.

And no, the burroughs did not work like that at all.

ron

Re: [9fans] Virtual memory & paging

[andrey mirtchovski]

virtual memory as a technique could be implemented using both 'demand paging' and 'demand segmentation' the most obvious difference between a page and a segment is that different segments could be of different sizes while pages have the same size (or set of sizes)..

hmm.. i just found the relevant textbook -- Operating Systems Concepts, 5th ed, (Silberschatz, Galvin) page 291

[9fans] Virtual memory & paging

[Andrew Simmons]

I seem to remember some one saying here a while back that virtual memory
and paging were quite distinct, whereas I'd always vaguely assumed they
were the same thing. Could some one explain the difference to me, or point
me in the direction of enlightenment? The issue came up in a friend's job
interview recently, and he wrongly assumed the same as me.

Thanks