[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 {
                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;
                        
                        // 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;
                        
                        // 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 - 9;
                        ulong Protected:1;
                        ulong FaultOnWrite: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_entry(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;
                }
        };
        
        // If the padded size of this changes, update rmap_shift.
        // and the alignment check in RMapTable::unmap.

        // If the layout of this changes, update the offsets below.
        union RMapNode {
                struct {
                        u64 vaddr;
                        VirtualArea *va;
                        Util::ListNoAutoInit head, tail;
                };
                
                long pad[8];
                
                enum {
                        head_offset = sizeof(u64) + sizeof(void *),
                        tail_offset = head_offset + sizeof(void *) * 2,
                };
        };
        
        // This lock protects the rmap chains and rmap tables.  It also makes
        // atomic the PageTable::get_entry, RMapTable::map, PageTable::map
        // sequence.
        //
        // OPT: This lock is acquired on all map/unmap activity; if/when this
        // turns out to be a significant bottleneck, finer-grained locking can
        // be used.  I decided against doing it now because it would be
        // somewhat complicated (but I believe do-able) to avoid all races,
        // and I'd like to move on to implementing other things for now.
        
        extern Lock::Lock rmap_lock;
        class Page;
        
        class RMapTable {
                void *toplevel;
                int toplevel_shift;
                
                RMapNode *get_rmap(u64 virtaddr, bool add = false);
                
        public:
                RMapTable();
                
                // rmap_lock must be held.
                static void map(VirtualArea *downstream_va, PageTable *upstream_ptbl,
                                u64 virtaddr, u64 upstream_vaddr);

                void unmap(u64 virtaddr);

                // Handle a copy-on-write for the specified page and all downstream
                // mappings.  All such mappings are set to the new page, and
                // FaultOnWrite is cleared.
                
                void break_copy_on_write(u64 virtaddr, Page *new_page);
        };
        
        class PageTable {
        public:
                void *toplevel;
                RMapTable rmap_table;
                const bool is_process;

                typedef Mem::PTEFlags Flags;
                typedef System::Mem::Region Region;
                typedef System::Mem::RegionWithOffset RegionWithOffset;
                
                PageTable(bool process) : is_process(process)
                {
                }

                virtual ~PageTable()
                {
                }
                
                // Region is virtual, offset is physical
                virtual void map(RegionWithOffset region, Flags flags) = 0;
                virtual void unmap(Region region) = 0;

                // Sets the flags which are set in mask to their value in flags.
                // Flags not set in mask are untouched.
                
                virtual void set_flags(Region region, Flags flags, Flags mask) = 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.  This function is mainly used for
                // propagating stacked aspace PTEs.
                
                virtual void get_entry(u64 vaddr, u64 *phys, Flags *flags) = 0;
                
                virtual void get_size(u64 *size) = 0;
                
                // This is called when a PTE is replaced.  It handles refcounting,
                // dirty page queueing, and TLB invalidation.  vaddr is only
                // valid for process address spaces, so it doesn't need to be
                // 64-bit (except on 64-bit hardware, of course).  When it is
                // known that only flags are changing, set no_release so that
                // the page refcount is not decremented.
                
                void kill_pte(ulong vaddr, u64 physaddr, bool dirty, bool valid,
                              bool no_release = false);
        };
        
        struct BadPageFault {
        };
        
        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_entry(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;
                bool is_process;
                // 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);

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

                ASpaceMappable mappable;
                PageTable *page_table;
                
                AddrSpace(bool process);
                AddrSpace(void *page_table);
                
                // Returns true if the fault was "good"; otherwise, the caller
                // should dump regs.  exec should only be used if the CPU
                // implements per-page exec protection; otherwise, treat it
                // as a read.
                
                bool handle_fault(ulong addr, bool write, bool exec, bool user);
                
                void get_mappable(IMappable *ma);
                void clone(IAddrSpace *addrspace, u8 clone_is_real);

                void alloc_and_map(u64 len, u64 *vstart,
                                   AllocFlags aflags, MapFlags mflags);

                enum {
                        map_user,
                        map_protected,
                        map_kernel
                };

                void map(IMappable ma, Region region, u64 *vstart, MapFlags mflags,
                         bool from_kernel = false, int map_type = map_user);
                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)
                {
                        page_table->get_size(size);
                }
                
                friend void Arch::set_aspace(AddrSpace *aspace);
                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