kernel/include/kern/pagealloc.h

   1 #ifndef _KERN_PAGEALLOC_H
   2 #define _KERN_PAGEALLOC_H
   3
   4 #include <System/Mem.h>
   5
   6 #include <kern/kernel.h>
   7 #include <kern/list.h>
   8 #include <kern/mem.h>
   9
  10 #include <arch/paging.h>
  11 #include <arch/addrs.h>
  12
  13 #include <lowlevel/atomic.h>
  14 #include <util/lock.h>
  15
  16 namespace Mem {
  17         class PageAllocZone;
  18         class Page;
  19
  20         union PageFlags {
  21                 struct bits {
  22                         enum {
  23                                 Dirty = 0
  24                         };
  25                 };
  26
  27                 struct {
  28                         uint32_t Dirty:1;
  29                 };
  30
  31                 uint32_t pad;
  32         };
  33
  34         // This is an array of all pages in all zones.  For now, zones must be
  35         // contiguous (or at least close enough to each other that it's not
  36         // a big deal to waste the space for the intervening page structs).
  37
  38         extern Page *pages, *last_page;
  39
  40         static inline uintptr_t page_to_phys(Page *page);
  41
  42         static inline bool is_phys_page(Page *page)
  43         {
  44                 return page >= Mem::pages && page < last_page;
  45         }
  46
  47         struct Page {
  48                 // A page is reserved if it is neither Free or InUse.
  49                 // Free and InUse may not be set at the same time.
  50
  51                 static const u32 Free = 0x00000001;
  52                 static const u32 InUse = 0x00000002;
  53
  54                 u32 flags;
  55                 PageAllocZone *zone;
  56
  57                 union {
  58                         // These fields are valid when a page is free, if it is the
  59                         // first or last page of the chunk.
  60
  61                         struct {
  62                                 // For the first page of a chunk, this points to the last
  63                                 // page of the chunk.  For the last page of the chunk, this
  64                                 // points to the first page of the chunk.  For a single-page
  65                                 // chunk, this points to itself.  For a bin's list head, this
  66                                 // points to the smallest bin at least as large as itself
  67                                 // that has an available chunk.
  68
  69                                 Page *otherside;
  70                         } free;
  71
  72                         // These fields are valid when a page is in use (not free or
  73                         // reserved).
  74
  75                         struct {
  76                                 int32_t refcount;
  77                                 PageFlags flags;
  78                         } inuse;
  79                 };
  80
  81                 // chunk when free, rmap when in use
  82                 //
  83                 // chunk points to the last page of the previous chunk in
  84                 // the bin and the first page of the next chunk in the bin.
  85                 // Only valid for the first page of a chunk.  Prevchunk of the
  86                 // first chunk and nextchunk of the last chunk point to the
  87                 // bin's list head.
  88                 //
  89                 // rmap points to each mapping (as an RMapNode) of this page.
  90                 // NOTE: rmap list currently unused
  91
  92                 Util::List chunk_rmap_list;
  93
  94                 void retain()
  95                 {
  96                         if (_UTIL_ASSERT_LEVEL >= 1) {
  97                                 if (!is_phys_page(this) || !(flags & InUse)) {
  98                                         in_fault++;
  99                                         printf("Page %p (phys %lx) retained flags %x, is_phys %d\n",
 100                                                this, page_to_phys(this), flags,
 101                                                (int)is_phys_page(this));
 102                                         __builtin_trap();
 103                                 }
 104                         }
 105 //                      assert(flags & InUse);
 106                         assert(inuse.refcount >= 1);
 107                         ll_atomic_inc(&inuse.refcount);
 108                 }
 109
 110                 void free_page();
 111
 112                 void release()
 113                 {
 114                         if (_UTIL_ASSERT_LEVEL >= 1) {
 115                                 if (!is_phys_page(this) || !(flags & InUse)) {
 116                                         in_fault++;
 117                                         printf("Page %p (phys %lx) released flags %x, is_phys %d\n",
 118                                                this, page_to_phys(this), flags,
 119                                                (int)is_phys_page(this));
 120                                         __builtin_trap();
 121                                 }
 122                         }
 123 //                      assert(flags & InUse);
 124                         assert(inuse.refcount >= 1);
 125                         if (ll_atomic_dec_and_test(&inuse.refcount))
 126                                 free_page();
 127                 }
 128
 129                 int32_t get_refcount()
 130                 {
 131                         assert(is_phys_page(this));
 132                         assert(flags & InUse);
 133                         assert(inuse.refcount >= 1);
 134                         return inuse.refcount;
 135                 }
 136         };
 137
 138         static inline Page *phys_to_page(uintptr_t phys)
 139         {
 140                 return pages + (phys >> Arch::page_shift);
 141         }
 142
 143         static inline uintptr_t page_to_phys(Page *page)
 144         {
 145                 return (page - pages) << Arch::page_shift;
 146         }
 147
 148         static inline Page *kvirt_to_page(void *kvirt)
 149         {
 150                 return phys_to_page(kvirt_to_phys(kvirt));
 151         }
 152
 153         static inline void *page_to_kvirt(Page *page)
 154         {
 155                 return phys_to_kvirt(page_to_phys(page));
 156         }
 157
 158         class PageAllocZone {
 159                 Lock::SpinLock lock;
 160
 161                 enum {
 162                         num_bins = CONF_MEM_MAX_PAGE_ALLOC_BITS
 163                 };
 164
 165                 // List head for each bin
 166                 Page bins[num_bins];
 167
 168                 // First and last pages of the zone
 169                 intptr_t start, end;
 170                 size_t zonesize; // end - start + 1
 171
 172                 size_t chunk_size(Page *start);
 173
 174                 uint bin_to_size(int bin);
 175                 int size_to_bin_alloc(size_t size);
 176                 int size_to_bin_free(size_t size);
 177
 178                 Page *bin_to_head(int bin);
 179
 180                 void remove_chunk(Page *start, int bin);
 181                 void add_to_bin(Page *chunk, int bin);
 182                 Page *shrink_chunk(Page *start, int num_pages,
 183                                    size_t chunk_size, int bin);
 184
 185         public:
 186                 // base and size are in pages; all pages must be reserved
 187                 // (i.e. flags set to zero).
 188
 189                 void init(uintptr_t base, size_t size);
 190
 191                 Page *alloc(uint num_pages);
 192                 void free(Page *head, size_t num_pages);
 193         };
 194
 195         class PageAlloc {
 196         public:
 197 //              #include "mem/pagealloc-server/Mem/PageAlloc.h"
 198
 199                 // Architectures must define lists of zones, in preference order,
 200                 // to use for each type of allocation; these are indices into
 201                 // Arch::pagezonelists.
 202                 //
 203                 // The ISA DMA zonelist is for ISA DMA buffers, which must be below
 204                 // some platform-dependent limit (typically 16MiB).
 205                 //
 206                 // The DMA32 zonelist is for devices on a 32-bit bus (such as
 207                 // ordinary PCI), so that buffers over 4GiB are not used unless
 208                 // the platform provides a suitable mapping mechanism (such
 209                 // as an IOMMU).
 210                 //
 211                 // An architecture may define additional zonelists for its internal
 212                 // use, but it's best to pass them directly as pointers than to
 213                 // define additional numbers, so as to avoid conflict if the
 214                 // generic list expands in the future.
 215
 216                 enum {
 217                         zonelist_normal = 0,
 218                         zonelist_dma32 = 1,
 219                         zonelist_isadma = 2,
 220                 };
 221
 222                 // Note that while num_pages does not have to be a power of 2 (and
 223                 // the allocation size will not be rounded up to the next power of
 224                 // 2), a request that is not a power of two may fail despite the
 225                 // existence of a suitable chunk if there is no available chunk of
 226                 // the next-higher power of 2.  num_pages may not be 0.
 227
 228                 static Page *alloc(uint num_pages, PageAllocZone *const *zonelist);
 229
 230                 static Page *alloc(uint num_pages, int zone = zonelist_normal)
 231                 {
 232                         assert(zone >= 0 && zone <= 2);
 233
 234                         return alloc(num_pages, Arch::pagezonelists[zone]);
 235                 }
 236
 237                 // Any span of allocated pages may be freed; it does not have to
 238                 // correspond to the size and start of the original allocation, and
 239                 // it may be larger than the maximum allocation size (though this
 240                 // is likely only useful during bootup when adding new chunks of
 241                 // memory).  All pages must be in the same zone.  num_pages may not
 242                 // be 0.
 243
 244                 static void free(Page *head, size_t num_pages)
 245                 {
 246                         head->zone->free(head, num_pages);
 247                 }
 248         };
 249
 250         extern PageAlloc page_alloc;
 251
 252
 253         static inline void *alloc_pages(int num,
 254                                         int zone = PageAlloc::zonelist_normal)
 255         {
 256                 return Mem::page_to_kvirt(PageAlloc::alloc(num, zone));
 257         }
 258
 259         static inline void free_pages(void *addr, int num)
 260         {
 261                 if (addr)
 262                         PageAlloc::free(kvirt_to_page(addr), num);
 263         }
 264
 265         static inline void retain_if_phys(ulong addr)
 266         {
 267                 Page *page = phys_to_page(addr);
 268
 269                 if (is_phys_page(page))
 270                         page->retain();
 271         }
 272
 273         static inline void release_if_phys(ulong addr)
 274         {
 275                 Page *page = phys_to_page(addr);
 276
 277                 if (is_phys_page(page))
 278                         page->release();
 279         }
 280 }
 281
 282 #endif