update

[polintos/scott/priv.git] / kernel / include / kern / mem.h

#ifndef _KERN_MEM_H
#define _KERN_MEM_H

#include <System/Mem.h>

#include <kern/kernel.h>

#include <arch/mem.h>
#include <arch/addrs.h>

#include <util/rbtree.h>
#include <util/list.h>
#include <util/lock.h>
#include <kernel/region.h>
#include <lowlevel/bitops.h>

namespace Mem {
        // Used for allocating memory at boot time before the page allocator
        // is running.  Alignment must be a power of 2.  Because nothing other
        // than the kernel is guaranteed to be mapped from the beginning on
        // all architectures, no generic code should use this until after
        // Arch::arch_init() has run and set up physical memory mappings.
        //
        // This function may not be used after the page allocator has
        // been initialized by architecture code.
        //
        // Architectures must provide Arch::next_free_bootmem initalized
        // to the first free piece of bootmem.
        
        static inline void *get_bootmem(size_t size, size_t align)
        {
                uintptr_t ret = (Arch::next_free_bootmem + align - 1) & ~(align - 1);
                Arch::next_free_bootmem = ret + size;
                return reinterpret_cast<void *>(ret);
        }
        
        typedef System::Mem::AddrSpace IAddrSpace;
        typedef System::Mem::Mappable IMappable;
        using System::Mem::Cacheable;
        using System::Mem::Region;
        using System::Mem::RegionWithOffset;
        using System::Mem::AllocFlags;
        using System::Mem::MapFlags;
        using System::Mem::AccessFlags;

        union PTEFlags {
                enum {
                        valid = 0x001,
                        writeable = 0x002,
                        readable = 0x004,
                        executable = 0x008,
                        user = 0x010,
                        accessed = 0x020,
                        dirty = 0x040,
                        uncached = 0x080,
                        faultonwrite = 0x100,
                        addressonly = 0x200,
                        protectedmap = 0x400,
                };
        
                struct {
                        // This must be kept in sync with include/kern/generic-pte.h
                
#ifdef BITFIELD_LE
                        // Readable, Writeable, and Executable are for permission only,
                        // not for implementing copy on write, swapping, etc.
                        
                        ulong Valid:1;
                        ulong Writeable:1;
                        ulong Readable:1;
                        ulong Executable:1;
                        ulong User:1;
                        ulong Accessed:1;
                        ulong Dirty:1;
                        ulong Uncached:1;
                        
                        // If set, then on a write access, the page is copied and this
                        // address space gets the new, anonymous version.  The rmap list
                        // is then traversed; all downstream mappings will share the new
                        // copy.
                        //
                        // For vareas that directly map something other than an address
                        // space, the action to be taken on a write fault is
                        // mapping-specific.

                        ulong FaultOnWrite:1;
                        
                        // The address itself is being mapped, not the page located
                        // there.  Do not manipulate page reference counts.  This bit
                        // does not get propagated during copy-on-write.

                        ulong AddressOnly:1;
                        
                        // VArea Only:
                        // Do not allow the user to unmap or modify flags.
                        // Used for the shared user/kernel mappings. 
                        
                        ulong Protected:1;

#elif defined(BITFIELD_BE)
                        ulong pad:_LL_LONG_BYTES * 8 - 11;
                        ulong Protected:1;
                        ulong AddressOnly:1;
                        ulong FaultOnWrite:1;
                        ulong Uncached:1;
                        ulong Dirty:1;
                        ulong Accessed:1;
                        ulong User:1;
                        ulong Executable:1;
                        ulong Readable:1;
                        ulong Writeable:1;
                        ulong Valid:1;
#else
#error Unspecified/unrecognized bitfield endianness
#endif
                };
                
                ulong raw;
                
                PTEFlags(ulong init) : raw(init)
                {
                }
                
                PTEFlags() : raw(0)
                {
                }
                
                operator ulong()
                {
                        return raw;
                }
        };

        using Arch::kvirt_to_phys;
        using Arch::phys_to_kvirt;
        class PageTable;
        class AddrSpace;

        struct VirtualArea;
        typedef Util::RBTree<VirtualArea, Region, u64> VirtualAreaTree;
        
        class Mappable {
        protected:
                // This linked list keeps track of the virtual areas that map this
                // mappable (this is not transitive; vareas that map a varea that
                // maps this mappable are not on this list).
                //
                // OPT: rbtree keyed on mapped address range?
                
                Util::List mappings;
                Lock::SpinLock mappings_lock;
                
        public:
                bool is_aspace;
                
                virtual void get_size(u64 *size) = 0;
                
                virtual void get_block_size(u64 *block_size)
                {
                        *block_size = Arch::page_size;
                }
                
                // Register/unregister varea as mapping this mappable.
                
                virtual void map(VirtualArea *varea);
                virtual void unmap(VirtualArea *varea);
                
                // Make the specified page available for mapping.  This must be
                // done before map() will succeed.  It is possible (though
                // unlikely) that the pages will be removed before map() is called,
                // causing map() to return false.  In such a case, pagein should be
                // called again by the fault handler.  If the mapping fails for
                // other reasons (such as lack of permission, a hole in a stacked
                // aspace, or an I/O error) then pagein() will throw a BadPageFault
                // exception.

                virtual void pagein(u64 vaddr, PTEFlags reqflags) = 0;
                
                // Returns the physical address and flags associated with a given
                // virtual address.  If flags.Valid is not set, then phys and all
                // other flags are undefined, and pagein() should be retried.
                // rmap_lock must be held.
                
                virtual void get_mapping(u64 vaddr, u64 *phys, PTEFlags *flags) = 0;

                #include <servers/mem/addrspace/Mem/Mappable.h>
                
                Mappable()
                {
                        init_iface();
                        is_aspace = false;
                }
                
                virtual ~Mappable()
                {
                }
        };
        
        struct VirtualArea {
                AddrSpace *aspace;
        
                // The red/black tree is used to find a region based on address. 
                //
                // The linked list is kept in order and is used to iterate over
                // vmas in a region (after looking up the starting point in the
                // tree, unless the region is the entire address space).
        
                VirtualAreaTree::Node rbtree_node;
                Util::List list_node;
                Util::List mappings_node;

                PTEFlags flags;
                Mappable *ma;
                
                // This is added to the virtual address to get the offset
                // into the mappable.
                s64 offset;
                
                Region &region()
                {
                        return rbtree_node.value;
                }
        };
        
        
        struct BadPageFault {
                MemoryFault_ns::Cause cause;
                
                BadPageFault(MemoryFault_ns::Cause CAUSE) : cause(CAUSE)
                {
                }
        };
        
        class ASpaceMappable : public Mappable {
                AddrSpace *aspace;
                
                static bool rec_pagein(AddrSpace *aspace, u64 vaddr,
                                       PTEFlags reqflags);

        public:
                ASpaceMappable (AddrSpace *ASPACE) : aspace(ASPACE)
                {
                        is_aspace = true;
                }

                void get_size(u64 *size);
        
                // Unexported
                virtual void pagein(u64 vaddr, PTEFlags reqflags);
                virtual void get_mapping(u64 vaddr, u64 *phys, PTEFlags *flags);

                friend class AddrSpace;
        };
        
        class AddrSpace {
                // OPT: Coalesce vareas when possible (except when setting flags to
                // match surrounding vareas, as the flags are likely to change
                // again if they've already changed).
                
                // OPT: A subclass of AddrSpace that doesn't use
                // VirtualArea::offset, but rather has its own virtual method that
                // figures out offsets to the next level using its own data
                // structures (such as filesystem block tables).  This would avoid
                // excessive vareas for fragmented files.  Whether the excess of
                // vareas is significant enough for this to be worthwhile remains
                // to be seen.

                VirtualAreaTree varea_tree;
                Util::List varea_list;
                Lock::Lock lock;

                // This defines the start and end of the aspace; mappings outside
                // this range may not be done, and will not be returned by
                // get_free_region().  For process aspaces, this goes from
                // Arch::user_start to Arch::user_end.  For non-proc aspaces, this
                // can be anything.

                Region aspace_region;

                // Returns true if there is a mapped region that overlaps the given
                // region.  If there is a collision, then the first overlapping
                // varea is returned in va.  Otherwise, it returns the last mapped
                // area before the region in va (if there are no areas, or the
                // region is before the first area, then prev is NULL).  The aspace
                // lock must be held.
                
                bool check_overlap(Region region, VirtualArea *&va);
                
                // Finds a free region of the requested length and puts it in
                // region.  Returns true if an appropriate area is found.  The prev
                // pointer is as in check_overlap.  The aspace lock must be held.
                
                bool get_free_region(ulong len, Region &region, VirtualArea *&prev);

                // This is the value after the last region returned by
                // get_free_region.  If there was an intervening unmap for a lower
                // address, then it is set to that address instead.

                u64 cached_free_region;

                static u64 rec_unmap(AddrSpace *aspace, Region region,
                                     PTEFlags reqflags, VirtualArea *va);
                
                // If there are multiple virtual areas that cover the specified region,
                // split them at the region's boundaries.  The first varea in the region
                // (if any) is returned.  The aspace lock must be held.
                
                VirtualArea *split_varea(Region region);

                void break_copy_on_write(VirtualArea *va, u64 vaddr, u64 phys);
                bool map(VirtualArea *va, u64 vaddr, PTEFlags reqflags);

        protected:
                bool is_process;

        public:
                #include <servers/mem/addrspace/Mem/AddrSpace.h>

                ASpaceMappable mappable;
                PageTable *page_table;
                
                AddrSpace(PageTable *ptbl = NULL);
                
                // Returns negative if the fault was "good"; otherwise, a fault
                // code corresponding to MemoryFault.Cause is returned.  exec
                // should only be set if the CPU implements per-page exec
                // protection; otherwise, treat it as a read.
                
                int handle_fault(ulong addr, bool write, bool exec, bool user);
                
                void get_mappable(IMappable *ma);
                void clone(IAddrSpace *addrspace, u8 clone_is_real);

                void map(IMappable ma, Region region, u64 *vstart, MapFlags mflags,
                         PTEFlags set = 0, PTEFlags clear = 0);
                void unmap(Region region, bool from_kernel = false);
                
                void set_mapflags(Region region, MapFlags mflags);
                void get_mapflags(Region region, MapFlags *mflags, uint8_t *all_same);
                void get_mapping(Region region, IMappable *ma, u64 *offset);
                
                void get_page_size(u32 *page_size);
                void get_min_align(u32 *min_align);
                void get_size(u64 *size);

                friend class ASpaceMappable;
        };

        extern Factory addr_space_factory, proc_addr_space_factory;

        using ::System::RunTime::orbmm;
        
        static inline bool page_aligned(u64 addr)
        {
                return !(addr & (u64)(Arch::page_size - 1));
        }

        static inline u64 page_align(u64 addr)
        {
                return addr & ~(u64)(Arch::page_size - 1);
        }
        
        // FIXME: Valid user addr?  Paging holes?
        static inline bool valid_addr(uint64_t addr)
        {
                if (sizeof(void *) == 8)
                        return true;
                
                return (addr >> 32) == 0;
        }
};

#endif