InfoMagic Source Code 1993 July/THE_SOURCE_CODE_CD_ROM.iso/mach/doc/notes/pmap-notes.Z/pmap-notes

Internet Message Format | 1993-04-05 | 27.7 KB

Subject: Pmap specifications and implementation hints
Author:    Bob Wheeler (who wrote it under duress)
Date:    Apr. 22, 1992
--------------------------------------------------------
Subject: Mach porting notes available, these are
    in additions to the notes in this file.
Date: Tue, 23 Mar 93 12:03:05 EST

Bob Wheeler has made available his slides for his Symposium
on "Porting and Modifying the Mach 3.0 Microkernel" at the Third
USENIX Mach Symposium, April 19, 1993

The 3 hour symposium will touch on all the parts of the Mach 3.0 kernel
that need to be changed for a new machine type. As a result it needs to
cover the internals of the virtual memory system, external pager, context
switches, continuations, cthreads implementation and emulated system
calls.

These slides are a good roadmap to reading and understanding the source
code or may be an enticement for you to attend the symposium if you really
want to learn about the internals of Mach 3.0.

They are available by FTP from mach.cs.cmu.edu, as user anonymous, in file
doc/unpublished/porting.tutorial.slides.ps{.Z}

                Mary Thompson

---------------------------------------------------------
N.B. This is a first draft of a pmap implementation guide and
should be read with the following cautionary note in mind.

  CARNEGIE MELLON ALLOWS FREE USE OF THIS DOCUMENT IN ITS "AS IS"
  CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS DOCUMENT.
---------------------------------------------------------------

A pmap or "physical map" is just a data structure that keeps track of
translations and protections for virtual to physical pages. Some machines
have hardware restrictions on what the data structure is. The vax, m68030
and i80386 all force the data structure to be a "page table". The R6000
uses an "inverted page table" while the PA-RISC and Mips chips are "software
loaded tlbs" and you can do anything you want from page tables to linked
lists, binary search trees or hash tables. The important point is that the
machine-independent form doesn't care what you use to represent these
translations. More likely than not your hardware will dictate the format
of your data structure. There is one pmap per address space. Which in
Mach means one for the kernel address space and one for each task. When
a thread is being activated, the pmap module is called to load up the
hardware with whatever register values or TLB contents the processor will
need to reference the address space of the task to which the thread belongs.

Whatever your data structure is it must be able to do the following
operations:

    insert new virtual to physical translations
    remove a virtual to physical translation
    lookup a virtual to physical translation
    change protection on a virtual to physical translation
    remove all translations to a physical page
    change the protection on all translations to a physical page
    keep track of whether a physical page has been written on
    keep track of whether a physical page has been referenced

One thing to notice is that you need to be able to find a translation given
either the physical or the virtual address. This means that even if you
use a forward page table for virtual to physical translations you will
need to have a way to find all mappings to a physical page. In addition
some things like "Is the page dirty?" apply to the physical page, not
to a translation (even though the hardware typically reports the page that
was written on by giving the virtual address).

The upshot is that you typically keep an array around and an entry in the array
corresponds to a physical page. The array holds the dirty bit for the page,
it may hold the reference bit for the page and it probably holds a pointer
to some linked list which tells the virtual addresses that map to that page.

You define a pmap structure which is really just a handle to whatever
your data structure is. Some pmap modules contain a pointer to a page table
structure, others just contain a "process ID". You usually don't put the
page table in the pmap structure, you just put a hook (a pointer) to the
table or data structure. Usually the pmap structure will have the form:

    typedef struct pmap {
            simple_lock_data_t      lock;        /* lock on pmap */
            int                     ref_count;   /* reference count */
            struct pmap_statistics  stats;       /* statistics */
            struct pmap             *next;       /* list for free pmaps */
        /*
         * a pointer to your data structure or whatever else you need.
         */
    } *pmap_t;

The lock is so that we can control access to the pmap in a multi-processor
environment (you really don't need it if you only have a uni-processor.) The
reference count will be used to determine when we can remove a particular pmap
structure. pmap_statistics contains statistics that are kept by your pmap
routines and they are used to report memory usage. The next pointer is used to
 link pmap structures that are not used into a free pmap list.
Because we might have multiple things in the kernel wanting access to a pmap,
we need a way to tell when everyone is done with a map. The way we do this is
with a reference count.

You need to define a pmap for the kernel's address space and define
a global pointer to it called kernel_pmap.

    struct pmap kernel_pmap_store;
    pmap_t kernel_pmap = &kernel_pmap_store;

Basically, anytime the pmap routines are called with a  virtual address,
the caller will also provide a pointer to the pmap structure for the
address space in which the virtual address resides.

Here are the routines that you need to write:

ROUTINES USED ONLY AT BOOTSTRAP TIME...

There is a routine that is called before virtual memory is turned on that
initializes all the data structures, does whatever is needed to make sure the
kernel is mapped and sets up all the VM data structures. Traditionally this
routine is called pmap_bootstrap. It is only called by machine dependent code
and thus you really don't have to have a pmap_bootstrap and there are no real
"defined" arguments for it, but you should call it pmap_bootstrap just so that
the next person knows where to look for the routine. It is usually called after
the bus and memory have been configured. This routine should also set the
reference count on the kernel's pmap to 1.

One of the things that pmap_bootstrap does is map the kernel. The routine
that is typically used to map the kernel is called pmap_map(). This routine
is only called by the machine dependent routine pmap_bootstrap. The machine
independent code knows nothing about it. The real difference between it and
pmap_enter() (besides the fact that it is only called at boot time), is that
it maps a range of address space and it always maps it into the kernel's
pmap.

/*
 *      Initialize the kernel's physical map.
 *
 *      This routine could be called at boot.  It maps a range of
 *      physical addresses into the kernel's virtual address space.
 *
 */
vm_offset_t pmap_map(virt, start, end, prot)
        vm_offset_t     virt;           /* Starting virtual address.    */
        vm_offset_t     start;          /* Starting physical address.   */
        vm_offset_t     end;            /* Ending physical address.     */
        int             prot;           /* Machine indep. protection.   */

Now we have to talk about a few special values that are set up at bootstrap
time. These values are not referenced by the machine independent code,
but you should use these names so that we all know what you're talking
about.

    extern vm_offset_t avail_start, avail_end;

This is the address range (all addresses in Mach are in bytes), of the
physical memory that the VM system should manage. It defines memory
as any address p such that avail_start <= p < avail_end.

All address ranges in Mach work this way, the lower address is included in
the range of addresses but the upper address is not included.

    extern vm_offset_t virtual_avail, virtual_end;

This is the address range that Mach should allocate kernel virtual memory
from.

Here's what the deal is. The kernel is in memory and the text, data and bss
of the kernel are not paged. There are also probably page tables, and other
data items that are sized at boot time that must always stay resident.

In pmap_bootstrap, you use pmap_map() to map all this text and data into the
kernel map. Now since it's not going anywhere, it's always "resident" we
really don't want or need the VM system manageing it. So one normally
sets avail_start to the first physical page past all this resident text and
data and avail_end to the first word that is not in physical memory.
Then we usually set virtual_avail to be the first virtual address that we
want to use that is not already mapped in the kernel and virtual_end to the
end of this range.

Now when you are boot strapping, you will probably carve out hunks of physical
memory for your data structures that must be resident. The machine independent
(MI) code also has data structures that need to be resident. The MI code needs
a way to grab physical pages of memory for allocation at bootstrap time.
For example, every physical page of memory managed by the VM system has a
struture called vm_page (see vm/vm_page.h) that descibes the physical page.
This tells us if the page is in transit from a pager, it's allocated, busy,
on the free list and so forth. The kernel needs to allocate one of these per
physical page. Sice these structures can't be pages and will never move
once their allocated in physical memory, why have the VM system manage them?.
Instead the MI code cuts out "resident" memory for them at boot time.

Now, there are two ways to let the VM system get resident memory.
If you define the CPP macro MACHINE_PAGES in your pmap.h file, then this means
that the pmap wants control of all allocation for the kernel. This flexability
is included for ports that really want to do strange things at bootstrap
time for various reasons. The PA-RISC port and the Mips port are two such
animals.

If you don't define MACHINE_PAGES then here are the routines you must write:

    pmap_free_pages : This returns the number of free physical pages
    left in memory. Basically it's the following routine:

        unsigned int pmap_free_pages()
        {
            return atop(avail_end - avail_start);
        }

    where atop() takes bytes and converts them to pages (shifts right
    some number of bits).

    pmap_virtual_space - just return the start and ending virtual
    addresses. This is needed because the MI code doesn't really know about
    virtual_avail and virtual_end and this is how it finds the range of
    virtual addresses that it can allocate for the kernel. It's easy:

        void pmap_virtual_space(startp, endp)
                vm_offset_t *startp;
                vm_offset_t *endp;
        {
                *startp = virtual_avail;
                *endp = virtual_end;
        }

    pmap_next_page - return the address of the next physical page that is
    available. It returns the address (in bytes) of the physical page
    through the pointer addrp. It returns TRUE (defined in mach/boolean.h)
    if there was a page to allocate and FALSE if there wasn't. It's
    basically:

        boolean_t pmap_next_page(addrp)
                vm_offset_t *addrp;
        {
                if (avail_next == avail_end)
                        return FALSE;

                *addrp = avail_next;
                avail_next += PAGE_SIZE;
                return TRUE;
        }

    pmap_init - called after kernel is running in virtual memory and all
    resident data structures have been allocated. You can call zinit() to
    allocate zones even though zone_init() has not been called.

    This is where you can set up zones for allocating new pmaps, new page
    tables or just do general housekeeping that needs to be done for
    your pmap module. You don't have to do anything here if you don't
    need to. It's just a hook to let you set up anything that you need to
    after we are running in virtual memory but before we really start
    running the kernel. The function returns void and there are no
    arguments.

Here's what the kernel is going to do. It will first call your routine
pmap_virtual_space() to get a range of kernel virtual addresses that it can
use to allocate memory from. It has a routine called pmap_steal_memory() that
will call your pmap_next_page() to grab physical pages of memory for mapping
all sorts of resident data structures needed by the kernel. As it grabs
physical pages it will call pmap_enter to enter the virtual address for the
physical page into the kernel's address space.

After all the resident memory is allocated that the MI code needs, it will
repeatedly call pmap_next_page(), getting a physical page. It will take this
page and fill in the vm_page structure for it and then add the page to the
free list. It keeps doing this until pmap_next_page() returns FALSE or
until it's allocated all the pages that pmap_free_pages() returned.

After it does it's own VM initialization, it will call your routine pmap_init()
to let you do anything you need to in the pmap module.

Now, if you really want to get fancy and there is some *big* reason you really
want control over allocation, you can define MACHINE_PAGES in your pmap.h
and then you have to write the following four routines:

    pmap_free_pages - same as above
    pmap_init - same as above

    pmap_steal_memory - grab "size" bytes of physical memory, do whatever
    you need to to get a virtual address mapped to it and return the
    virtual address for that memory.

        vm_offset_t pmap_steal_memory(size)
                    vm_size_t size;

    pmap_startup - allocate a vm_page structure for every physical page,
    initialize the structure and put the physical page on the free list.
    Return the starting and ending virtual addresses that the rest of the
    kernel can use to allocate kernel memory from.

        void pmap_startup(startp, endp)
                vm_offset_t *startp, *endp;

Ok, enough about resident pages. If you want to know more look at the comments
in vm/pmap.h and the code in vm/vm_resident.c.

Until now we've only been talking about routines used to bootstrap the system,
once we're up and running we will no longer use any of the routines described
above.

ROUTINES USED AFER STARTUP

Here are the remaining pmap routines that you need to implement:

Define PMAP_NULL in your pmap.h file as

    #define PMAP_NULL ((pmap_t)0)

We should start out with how you get a pmap for a new task, pmap_create().

    pmap_t pmap_create(size)
            vm_size_t       size;

You should do whatever you have to to get a new pmap, perhaps allocate page
tables or whatever, then set the reference count to 1 and return the pointer
to the pmap. Usually one
sets up a zone of pmaps in pmap_init() and you keep a linked list of free
pmaps that have been allocated, used and freed. You try and allocate one of
the free list. If that fails you get one from the zone. Then you do whatever
local magic is needed to get it set up and you return it.

Here is the weird part. If the size is zero then this is a "real" physical
map and you need to allocate space for it. If the size is not zero then
it is a "software only" map and you need not allocate real space for it.

The bottom line is that it is never called with anything but 0. You probably
want to add a check like this at the top of the file

    if (size != (vm_size_t)0)
        return PMAP_NULL;

just in case someday someone decides to reuse this fine feature.

The routine pmap_reference should just increment a
counter associated with the pmap. The routine should be:

    void pmap_reference(pmap)
            pmap_t  pmap;
    {
            if (pmap != PMAP_NULL)
                    map->ref_count++;
    }

Again, this is so simple you probably want to define it as a macro, say...

#define pmap_reference(pmap) \
    do { \
        pmap->ref_count++; \
    } while(0)

XXX - fix pmap.h so that this can be a macro


The next obvious routine to talk about is pmap_destroy().

    void pmap_destroy(pmap)
            pmap_t  pmap;

Decrement the reference count on the pmap, if it is not zero then just return.
This routine will only be called after all mappings have been removed from the
pmap using pmap_remove(). All you have to do is whatever cleanup you need to,
(maybe free up some page tables or whatever) and then you will probably put
the pmap on a free list so that it can be reused by pmap_create().

The next routine pmap_kernel is really easy, just return the address of the
kernel's pmap. Your routine will probably look like this:

    pmap_t pmap_kernel()
    {
            return (kernel_pmap);
    }

Since this is such a trivial function, why do a function call. A better idea
for this one is to put

    #define pmap_kernel() (kernel_pmap)

in your pmap.h file.

XXX - Actually this is really stupid, most of the MI code just uses
kernel_pmap. It's only used in kmem_init in vm_kern.c. We should change this
to a pmap_kernel and get rid of this call altogether.

There is a set of macros that you need to define that activate and deactivate
a pmap. The CPP macros that should be in your pmap.h file are:

    PMAP_ACTIVATE(pmap, thread, cpu)
    PMAP_DEACTIVATE(pmap, thread, cpu)

    The arguments are

        pmap_t pmap;        /* pointer to the pmap */
        thread_t thread;    /* pointer to the thread */
        int cpu;        /* the cpu to use */

Basically these macros should do whatever they need to in order to activate
or deactivate a pmap on a machine. They are called with both the kernel's
pmap and with user's pmap. They are used at context switch time, startup and
shutdown. Say you have page tables, these routines might change the value
of a root page table pointer for example. If you don't need them (for instance
you have an inverted page table), just define them to be empty macros in
your pmap.h file.  They are implemented as macros for both efficiency
and as a way to let them be null statements on machines where they are
not needed.

If you need to split kernel and user pmap activations then you can define the
following routines instead of the ones above:

    PMAP_ACTIVATE_USER(pmap, thread, cpu)
    PMAP_DEACTIVATE_USER(pmap, thread, cpu)
    PMAP_ACTIVATE_KERNEL(cpu)
    PMAP_DEACTIVATE_KERNEL(cpu)

See the file vm/pmap.h for more details.

So now that we know how to create, activate, deactivate and destory a pmap
we should add a translation to a pmap. This is done with pmap_enter().

    void pmap_enter(map, v, p, prot, wired)
            register pmap_t map;
            vm_offset_t     v;
            vm_offset_t     p;
            vm_prot_t       prot;
            boolean_t       wired;

Basically you should establish a mapping for virtual address v to physical
address p with protection prot. (See mach/vm_prot.h for the protection
codes). If wired is true then the page should be "wired", which means that
you must keep the translation around and you can't just chuck it. Otherwise
can always just drop a translation (as long as it's not one that was set up
at bootstrap time in the kernel pmap) and the MI code will provide it the
next time you call vm_fault().

Actually "wired" is a leftover from the VAX. Here's the deal. On the VAX
when you did I/O operations, the CPU used the virtual address to do the I/O.
Some of the DMA devices actually went through the MMU and wrote into virtual
addresses. This is nice of course because you don't have to do all the
scatter/gather stuff like you do with devices that DMA into physical memory.
Anyway, "wired" is only asserted before an I/O operation and the page is
"unwired" after the I/O operation.

If you're machine doesn't need a translation for I/O (say it DMAs into physical
memory) then you can just ignore this wired nonsense.

        if (map == PMAP_NULL)
                return;


Ok, now you're saying, "Hell I could 'ave read the code and gotten this much".
Here's some insight. Outside of bootstrap time when the kernel is laying down
kernel resident data structures, pmap_enter is *only* called because the
system took a tlb miss or a page fault and eventually called vm_fault().
This means that the translation that you are being asked to insert is needed
now. Here is some more stuff.

[discuss what to do with a split I/D tlb]

Now, the way the system removes translations is through the routine
pmap_remove().

    void pmap_remove(pmap, start, end)
            pmap_t          pmap;
            vm_offset_t     start, end;

In this call, start and end are the starting and ending virtual addresses
(they are always on a page boundary). You should remove translations for
all addresses va in the range start <= va < end from the specified pmap.
The VM system does not try to be very smart about pmap_remove. For example,
when a process is created the entire stack is "mapped" by the kernel, this
doesn't mean that pmap_enter is called, that only happens if the process
actually touches the page. What I mean by mapped is that the virtual address
space is set aside for the stack. Now, pmap_remove will get called to remove
all of the stack. The bottom line is that it will ask for large hunks of
virtual addresses to be removed. Some (most?) of the addresses in the
region will probably not be in your pmap.

For each physical page you need to keep track if that page has been modified.
Usually this is done using a "write-trap" by the hardware. The routine
pmap_is_referenced() is given the physical address of a page and returns
TRUE or FALSE.

    boolean_t pmap_is_modified(phys)
            vm_offset_t     phys;

The companion routine is pmap_clear_modify which instructs the pmap module
to mark the physical page as being unmodified.

    void pmap_clear_modify(phys)
            vm_offset_t     phys;

Again the argument is the physical address of the page for which the modify
bit should be cleared.


Reference bits are used by the VM system to determine is a page has been
used (read/written/executed) to see if it is a candidate for page-out.
Some machines have a magic way to trigger a trap on first use (rather than
just first write). If you have one of these types of machines you can use
this trap to set a flag to indicate that the page has been used. If you don't
have this kind of trap, you can use tlb misses or page faults to get the
information but there are better ways explained below.

There are two routines for this

    void pmap_clear_reference(phys)
            vm_offset_t     phys;

    boolean_t pmap_is_referenced(phys)
            vm_offset_t     phys;

The first clears the reference bit on the page, the second tests it. Presumably
some trap handler sets the bit.

Rich Draves wrote a very good paper on how to deal with reference bits if the
hardware doesn't have support for them. The paper is "Page Replacement and
Reference Bit Emulation in Mach." He was able to show that it's not worth
the expense of putting code in the tlb handler to deal with it but instead
you can let the higher level MI code deal with the problem. You might want to
read his paper in the 1991 Mach Usenix Symposium. A copy is on line at CMU
in /afs/cs/project/mach/public/doc/Usenix.Mach2/page-repl.ps. It can be
retrieved by FTP as user "anonymous" from mach.cs.cmu.edu from the directory
doc.

If you want to use Rich's method it's really easy, just make pmap clear
reference remove all mappings for the physical page and have pmap_is_referenced
always return FALSE. Since these are both really easy routines, just define
them in pmap.h as follows:

    #define pmap_clear_reference(phys) \
            pmap_remove_all(phys)
    #define pmap_is_referenced(phys) \
            (FALSE)

If you don't have hardware support for page references (both text and data)
or if you have a software loaded TLB, I would implement Rich's method.

When a user program requests a change in protection on a region of virtual
address space this eventaully becomes a call to pmap_protect(). This routine
is given a pmap, starting and ending virtual address and a new protection.
Like pmap_remove(), not all addresses will be in your pmap data structures
and you only need to change the ones that are. (You might need to flush a
tlb entry as well if there is a chance that the tlb doesn't see the change
in protection in your data structures.) Anyway, same rules for ranges.
start and end are rounded to a page boundary, start at start and go up
to but not including end.

    void pmap_protect(pmap, start, end, prot)
            register pmap_t pmap;
            register vm_offset_t start;
            vm_offset_t     end;
            vm_prot_t       prot;

In order to implement copy-on-write the kernel will need to change the
protection for all virtual translations to a given physical page. In this
case it calls the routine pmap_page_protect.

    void pmap_page_protect(phys, prot)
            vm_offset_t     phys;
            vm_prot_t       prot;

This routine replaced two earlier routines and thus the semantics a a bit
twisted. It's really only used to LOWER permission on a page. It is also
used to remove all mappings from a physical page. The idea is that if the
protection doesn't include read access then all mappings should be removed.
(Yeah... this is weird, it actually makes sense on some machines to only allow
execute access but that's the way it is.)



void pmap_change_wiring(map, v, wired)
    register pmap_t    map;
    vm_offset_t    v;
    boolean_t    wired;
/*
 *    Function:    Change the wiring attribute for a map/virtual-address
 *            pair.
 *    In/out conditions:
 *            The mapping must already exist in the pmap.
 */


kern_return_t pmap_attribute( pmap, address, size, attribute, value)
        pmap_t          pmap;
        vm_offset_t     address;
        int             size; /* vm_size_t really, but we want it signed */
        vm_machine_attribute_t  attribute;
        vm_machine_attribute_val_t* value;              /* IN/OUT */
/*
 *      pmap_attributes:
 *
 *      Set/Get special memory attributes
 *
 */

The main (and possibly only) use of this routine is to flush pages from
whatever caches the hardware may support.



vm_offset_t pmap_extract(map, va)
        register pmap_t         map;
        vm_offset_t             va;
/*
 *    Function:
 *        Extract the physical page address associated with the given
 *        map/virtual_address pair.  The address includes the offset
 *        within a page.
 */

void pmap_collect(map)
        register pmap_t         map;
/*
 *    Function:
 *        Garbage collects the physical map system for
 *        pages which are no longer used.
 *        Success need not be guaranteed -- that is, there
 *        may well be pages which are not referenced, but
 *        others may be collected.
 *    Usage:
 *        Called by the pageout daemon when pages are scarce.
 *
 */


pmap_zero_page(phys)
    register vm_offset_t    phys;
/*
 *    zeros the specified (machine independent) page.
 */

pmap_copy_page(src, dst)
    register vm_offset_t src, dst;
/*
 *    copies the specified (machine independent) page.
 */


A COUPLE MORE MISCELLLANEOUS MACROS


pmap_phys_address (code) - simple macro to convert pages to bytes

for example
#define pmap_phys_address(frame) ((vm_offset_t) (intel_ptob(frame)))


 pmap_resident_count (pmap) - returns the number of resident pages

for example
#define pmap_resident_count(pmap)       ((pmap)->stats.resident_count)


ROUTINES THAT ARE ONLY ADVISORY

pmap_copy(dst_pmap,src_pmap,dst_addr,len,src_addr)
    pmap_t        dst_pmap;
    pmap_t        src_pmap;
    vm_offset_t    dst_addr;
    int        len;
    vm_offset_t    src_addr;

/*
 *     Copies a section of pmap
 */
This routine was designed to be used as a hint at task forking
time, to initialize the pmap for the new task. It does not
appear to ever be called and may be removed in the near future.

pmap_pageable(map, start, end, pageable)
    pmap_t        map;
    vm_offset_t    start;
    vm_offset_t    end;
    boolean_t    pageable;
/*
 *    Function:
 *        Make the specified pages (by pmap, offset)
 *        pageable (or not) as requested.
 *
 *        A page which is not pageable may not take
 *        a fault; therefore, its page table entry
 *        must remain valid for the duration.
 *
 *        This routine is merely advisory; pmap_enter
 *        will specify that these pages are to be wired
 *        down (or not) as appropriate.
 */





OBSOLETE ROUTINES

These are routines that used to be provided and you may find references
to them in older documentation. They are no longer needed so
don't worry about them.

pmap_access
pmap_list_resident_pages
pmap_remove_attributes
pmap_update
pmap_copy_on_write, pmap_remove_all: superceded by pmap_page_protect