kernel/mem/pagetable.cc

   1 // mem/pagetable.cc -- Generic page table implementation
   2 // Most architectures should be able to use this as is, though
   3 // architectures with weird paging hardware can provide their own implementation.
   4 //
   5 // OPT: Dynamically adjust the number of pagetable levels for PTEs that
   6 // support it (mainly for generic-pte).
   7 //
   8 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining a copy of
  11 // this software and associated documentation files (the "Software"), to deal with
  12 // the Software without restriction, including without limitation the rights to
  13 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  14 // of the Software, and to permit persons to whom the Software is furnished to do
  15 // so, subject to the following condition:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  22 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  23 // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  24 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  25 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
  26 // SOFTWARE.
  27
  28 #include <kern/mem.h>
  29 #include <kern/pagealloc.h>
  30 #include <kern/pagetable.h>
  31 #include <kern/generic-pte.h>
  32 #include <lowlevel/atomic.h>
  33 #include <util/misc.h>
  34
  35 namespace Mem {
  36         PageTable *kernel_page_table;
  37
  38         // The architecture must specify at least one data structure
  39         // representing one PTE.  Non-directory PTEs must support the |
  40         // operation, either through overloading or providing a constructor and
  41         // conversion operator for an integral type.  It is assumed that a PTE
  42         // of zero (by using bzero on the table) is a reasonable invalid PTE,
  43         // but a PTE-specific bulk zero method could be added if necessary.
  44         //
  45         // Eventually multiple PTE formats will need to be supported in
  46         // order to dynamically choose between PAE and non-PAE on 32-bit
  47         // x86.  When that happens, the arch will instantiate its choice
  48         // of PageTableImpl template rather than export Arch::PTE.
  49
  50         // A PTE must support typedefs PTE::PhysAddr and PTE::VirtAddr which
  51         // refers to integer types of the same size as the supported physical
  52         // and virtual addresses, respectively...
  53
  54         // A PTE must support a typedef PTE::DirPTE which is used for
  55         // non-final page tables.  DirPTE may be the same as PTE.  DirPTE must
  56         // support valid_pte, set_pte, and shift_per_level as in a normal PTE,
  57         // and must implement the following methods:
  58         //
  59         // void *get_table()
  60         //
  61         // A function to return the virtual address of the table pointed to
  62         // by this DirPTE entry.
  63         //
  64         // static DirPTE set_table(void *table)
  65         //
  66         // A function to return a DirPTE pointing to the specified virtual
  67         // address.
  68
  69         // A normal PTE must support the following methods:
  70         //
  71         // static void flags_to_pte(Mem::PTEFlags flagsin,
  72         //                               Mem::PTEFlags maskin,
  73         //                               PTE &flagsout,
  74         //                               PTE &maskout)
  75         //
  76         // A function to turn Mem::PTEFlags into a PTE.  It also produces
  77         // a mask which can be used to produce a new pte by calling
  78         // oldpte.set_flags(mask, newpteflags).
  79         //
  80         // PTE set_flags(PTE mask, PTE flags)
  81         //
  82         // Apply the flags to the PTE according to the provided mask.
  83         //
  84         // Mem::PTEFlags pte_to_flags()
  85         //
  86         // A function to turn a PTE into Mem::PTEFlags
  87         //
  88         // static uint addr_to_offset(VirtAddr addr, int shift)
  89         //
  90         // A function to take a virtual address and a shift level and return
  91         // the offset into the page table in entries.
  92         //
  93         // PhysAddr pte_to_addr()
  94         //
  95         // A function to take a PTE and return the physical address contained
  96         // therein.
  97         //
  98         // static PTE addr_to_pte(PhysAddr phys)
  99         //
 100         // A function to take a physical address and return a PTE with that
 101         // address and no flags set.
 102         //
 103         // bool valid_pte()
 104         // bool dirty_pte()
 105         //
 106         // A function to return whether the PTE is valid/dirty or not.  This
 107         // is a shortcut to keep from having to do a pte_to_flags repeatedly.
 108         // It would have been slightly cleaner to make this a method of PTE,
 109         // but that would require that PTE be implemented as a complex type,
 110         // and I'd rather leave that up to the architecture.
 111         //
 112         // void set_pte(PTE *table, uint offset)
 113         //
 114         // A function to set a PTE in a page table.  Normally, this is just
 115         // a simple assignment, but some architectures may need to do something
 116         // unusual (such as ensure atomicity if the PTE size is greater than
 117         // the word size).
 118         //
 119         // PTE xchg_pte(PTE *table, uint offset)
 120         //
 121         // As set_pte, but atomically reads the old PTE while setting the
 122         // new PTE, and returns the old one.
 123
 124         // A PTE must have the following constants:
 125         //
 126         // shift_per_level:
 127         // The number of bits of virtual address space represented by one
 128         // level of page tables.  This is log2(number of pages per table).
 129         //
 130         // num_levels:
 131         // The number of page table levels; this is used, but not imported,
 132         // due to a conflict with PageTable::num_levels.
 133         //
 134         // page_size: the size of a page
 135         // page_shift: log2(page_size)
 136         //
 137         // kmap_start, kmap_end:
 138         // The kernel mappings portion of the address space is mapped into all
 139         // address spaces, using shared page tables.  This sharing occurs at
 140         // the top-level page table (hopefully this will work for all
 141         // architectures; it can be made configurable, at the cost of some
 142         // complexity).  kmap_start and kmap_end are indices into the top
 143         // level page table that define which region is shared.  These are only
 144         // relevant for process address spaces.
 145
 146         using Util::round_up;
 147
 148         template<typename PTE>
 149         void PageTableImpl<PTE>::end_map(RegionWithOffset region, PTE flags,
 150                                          void *table)
 151         {
 152                 uint start = PTE::addr_to_offset(region.start, PTE::page_shift);
 153                 uint end = PTE::addr_to_offset(region.end, PTE::page_shift);
 154
 155                 Page *page = kvirt_to_page(table);
 156
 157                 assert(start < pages_per_table());
 158                 assert(end < pages_per_table());
 159                 assert(page->flags & Page::InUse);
 160
 161                 PTE *ptable = static_cast<PTE *>(table);
 162
 163                 for (uint i = start; i <= end; i++) {
 164                         PTE newpte = PTE::addr_to_pte(region.offset) | flags;
 165                         PTE oldpte = newpte.xchg_pte(ptable, i);
 166
 167                         retain_if_phys(region.offset);
 168
 169                         if (oldpte) {
 170                                 // vaddr is only for process aspaces, so don't worry
 171                                 // about the ulong.
 172
 173                                 ulong vaddr = (ulong)region.start +
 174                                               ((i - start) << PTE::page_shift);
 175
 176                                 kill_pte(vaddr, oldpte.pte_to_addr(),
 177                                          oldpte.dirty_pte(), oldpte.valid_pte());
 178                         } else {
 179                                 page->retain();
 180                         }
 181
 182                         region.offset += PTE::page_size;
 183                 }
 184         }
 185
 186         template<typename PTE>
 187         void PageTableImpl<PTE>::rec_map(RegionWithOffset region, PTE flags,
 188                                          void *table, int shift)
 189         {
 190                 if (shift < lastlevel_shift) {
 191                         assert(shift + DirPTE::shift_per_level - PTE::shift_per_level == PTE::page_shift);
 192                         end_map(region, flags, table);
 193                         return;
 194                 }
 195
 196                 Page *page = kvirt_to_page(table);
 197
 198                 DirPTE *dtable = static_cast<DirPTE *>(table);
 199                 uint start = DirPTE::addr_to_offset(region.start, shift);
 200                 uint end = DirPTE::addr_to_offset(region.end, shift);
 201                 u64 orig_end = region.end;
 202
 203                 assert(start < pages_per_dtable());
 204                 assert(end < pages_per_dtable());
 205                 assert(page->flags & Page::InUse);
 206
 207                 if (start != end)
 208                         region.end = round_up(region.start + 1, shift) - 1;
 209
 210                 for (uint i = start; i <= end; i++) {
 211                         void *subtable;
 212
 213                         if (!dtable[i].valid_pte()) {
 214                                 subtable = Mem::alloc_pages(1);
 215                                 bzero(subtable, PTE::page_size);
 216                                 DirPTE newpte = DirPTE::set_table(subtable);
 217                                 newpte.set_pte(dtable, i);
 218                                 page->retain();
 219                         } else {
 220                                 subtable = dtable[i].get_table();
 221                         }
 222
 223                         rec_map(region, flags, subtable, shift - DirPTE::shift_per_level);
 224
 225                         region.offset += region.end - region.start + 1;
 226                         region.start = region.end + 1;
 227
 228                         if (i + 1 == end)
 229                                 region.end = orig_end;
 230                         else
 231                                 region.end += 1UL << shift;
 232                 }
 233         }
 234
 235         template <typename PTE>
 236         void PageTableImpl<PTE>::end_unmap(Region region, void *table)
 237         {
 238                 Page *page = kvirt_to_page(table);
 239                 uint start = PTE::addr_to_offset(region.start, PTE::page_shift);
 240                 uint end = PTE::addr_to_offset(region.end, PTE::page_shift);
 241
 242                 assert(start < pages_per_table());
 243                 assert(end < pages_per_table());
 244                 assert(page->flags & Page::InUse);
 245
 246                 PTE *ptable = static_cast<PTE *>(table);
 247
 248                 for (uint i = start; i <= end; i++) {
 249                         if (ptable[i]) {
 250                                 PTE oldpte = PTE().xchg_pte(ptable, i);
 251
 252                                 if (oldpte) {
 253                                         // vaddr is only for process aspaces, so don't worry
 254                                         // about the ulong.
 255
 256                                         ulong vaddr = (ulong)region.start +
 257                                                       ((i - start) << PTE::page_shift);
 258
 259                                         kill_pte(vaddr, oldpte.pte_to_addr(),
 260                                                  oldpte.dirty_pte(), oldpte.valid_pte());
 261                                 }
 262
 263                                 assert(page->inuse.refcount > 1);
 264                                 page->release();
 265                         }
 266                 }
 267         }
 268
 269         template <typename PTE>
 270         void PageTableImpl<PTE>::rec_unmap(Region region, void *table, int shift)
 271         {
 272                 if (shift < lastlevel_shift) {
 273                         assert(shift + DirPTE::shift_per_level - PTE::shift_per_level == PTE::page_shift);
 274                         end_unmap(region, table);
 275                         return;
 276                 }
 277
 278                 Page *page = kvirt_to_page(table);
 279                 uint start = DirPTE::addr_to_offset(region.start, shift);
 280                 uint end = DirPTE::addr_to_offset(region.end, shift);
 281                 u64 orig_end = region.end;
 282
 283                 assert(start < pages_per_dtable());
 284                 assert(end < pages_per_dtable());
 285                 assert(page->flags & Page::InUse);
 286
 287                 DirPTE *dtable = static_cast<DirPTE *>(table);
 288
 289                 if (start != end)
 290                         region.end = round_up(region.start + 1, shift) - 1;
 291
 292                 for (uint i = start; i <= end; i++) {
 293                         if (dtable[i].valid_pte()) {
 294                                 void *subtable = dtable[i].get_table();
 295
 296                                 rec_unmap(region, subtable, shift - DirPTE::shift_per_level);
 297
 298                                 Page *subpage = kvirt_to_page(subtable);
 299                                 assert(subpage->flags & Page::InUse);
 300                                 assert(subpage->inuse.refcount > 0);
 301
 302                                 if (subpage->inuse.refcount == 1) {
 303                                         DirPTE().set_pte(dtable, i);
 304                                         subpage->release();
 305
 306                                         assert(page->inuse.refcount > 1);
 307                                         page->release();
 308                                 }
 309                         }
 310
 311                         region.start = region.end + 1;
 312
 313                         if (i + 1 == end)
 314                                 region.end = orig_end;
 315                         else
 316                                 region.end += 1UL << shift;
 317                 }
 318         }
 319
 320         template <typename PTE>
 321         void PageTableImpl<PTE>::end_set_flags(Region region, PTE flags,
 322                                                PTE mask, void *table)
 323         {
 324                 uint start = PTE::addr_to_offset(region.start, PTE::page_shift);
 325                 uint end = PTE::addr_to_offset(region.end, PTE::page_shift);
 326
 327                 assert(start < pages_per_table());
 328                 assert(end < pages_per_table());
 329
 330                 PTE *ptable = static_cast<PTE *>(table);
 331
 332                 for (uint i = start; i <= end; i++) {
 333                         if (ptable[i]) {
 334                                 PTE oldpte = ptable[i].set_flags(mask, flags);
 335
 336                                 // vaddr is only for process aspaces, so don't worry
 337                                 // about the ulong.
 338
 339                                 ulong vaddr = (ulong)region.start +
 340                                               ((i - start) << PTE::page_shift);
 341
 342                                 kill_pte(vaddr, oldpte.pte_to_addr(),
 343                                          oldpte.dirty_pte(), oldpte.valid_pte(), true);
 344                         }
 345                 }
 346         }
 347
 348         template <typename PTE>
 349         void PageTableImpl<PTE>::rec_set_flags(Region region, PTE flags,
 350                                                PTE mask, void *table,
 351                                                int shift)
 352         {
 353                 if (shift < lastlevel_shift) {
 354                         assert(shift + DirPTE::shift_per_level - PTE::shift_per_level == PTE::page_shift);
 355                         shift = PTE::page_shift;
 356                 }
 357
 358                 uint start = DirPTE::addr_to_offset(region.start, shift);
 359                 uint end = DirPTE::addr_to_offset(region.end, shift);
 360                 u64 orig_end = region.end;
 361
 362                 assert(start < pages_per_dtable());
 363                 assert(end < pages_per_dtable());
 364
 365                 DirPTE *dtable = static_cast<DirPTE *>(table);
 366
 367                 if (start != end)
 368                         region.end = round_up(region.start + 1, shift) - 1;
 369
 370                 for (uint i = start; i <= end; i++) {
 371                         if (dtable[i].valid_pte()) {
 372                                 void *subtable = dtable[i].get_table();
 373
 374                                 rec_set_flags(region, flags, mask, subtable,
 375                                               shift - DirPTE::shift_per_level);
 376                         }
 377
 378                         region.start = region.end + 1;
 379
 380                         if (i + 1 == end)
 381                                 region.end = orig_end;
 382                         else
 383                                 region.end += 1UL << shift;
 384                 }
 385         }
 386
 387         template <typename PTE>
 388         void PageTableImpl<PTE>::map(RegionWithOffset region, Flags flags)
 389         {
 390                 Lock::AutoLock autolock(lock);
 391                 PTE pte, ptemask;
 392                 PTE::flags_to_pte(flags, ~0UL, pte, ptemask);
 393                 PTE *table = static_cast<PTE *>(toplevel);
 394                 rec_map(region, pte, table, toplevel_shift);
 395         }
 396
 397         template <typename PTE>
 398         void PageTableImpl<PTE>::unmap(Region region)
 399         {
 400                 Lock::AutoLock autolock(lock);
 401                 PTE *table = static_cast<PTE *>(toplevel);
 402                 rec_unmap(region, table, toplevel_shift);
 403         }
 404
 405         template <typename PTE>
 406         void PageTableImpl<PTE>::set_flags(Region region, Flags flags, Flags mask)
 407         {
 408                 Lock::AutoLock autolock(lock);
 409                 PTE pte, ptemask;
 410                 PTE::flags_to_pte(flags, mask, pte, ptemask);
 411                 PTE *table = static_cast<PTE *>(toplevel);
 412                 rec_set_flags(region, pte, ptemask, table, toplevel_shift);
 413         }
 414
 415         template <typename PTE>
 416         void PageTableImpl<PTE>::get_mapping(u64 addr, u64 *phys, Flags *flags)
 417         {
 418                 Lock::AutoLock autolock(lock);
 419                 int shift = toplevel_shift;
 420
 421                 void *table = toplevel;
 422
 423                 while (shift >= lastlevel_shift) {
 424                         DirPTE *dtable = static_cast<DirPTE *>(table);
 425                         DirPTE dpte = dtable[DirPTE::addr_to_offset(addr, shift)];
 426
 427                         if (!dpte.valid_pte()) {
 428                                 flags->Valid = 0;
 429                                 return;
 430                         }
 431
 432                         table = dpte.get_table();
 433                         shift -= DirPTE::shift_per_level;
 434                 }
 435
 436                 assert(shift + DirPTE::shift_per_level - PTE::shift_per_level == PTE::page_shift);
 437
 438                 PTE *ptable = static_cast<PTE *>(table);
 439
 440                 uint off = PTE::addr_to_offset(addr, PTE::page_shift);
 441
 442                 *phys = ptable[off].pte_to_addr();
 443                 *flags = ptable[off].pte_to_flags();
 444         }
 445
 446         template <typename PTE>
 447         PageTableImpl<PTE>::PageTableImpl(bool process) : PageTable(process)
 448         {
 449                 toplevel = Mem::alloc_pages(1);
 450                 PTE *table = static_cast<PTE *>(toplevel);
 451
 452                 if (is_process) {
 453                         num_levels = PTE::num_levels;
 454
 455                         if (PTE::kmap_start != 0)
 456                                 bzero(table, PTE::kmap_start * sizeof(PTE));
 457
 458                         if (PTE::kmap_end != pages_per_dtable() - 1)
 459                                 bzero(table + PTE::kmap_end + 1,
 460                                       (pages_per_dtable() - PTE::kmap_end - 1) * sizeof(PTE));
 461
 462                         PTE *ktable = static_cast<PTE *>(kernel_page_table->toplevel);
 463
 464                         memcpy(table + PTE::kmap_start, ktable + PTE::kmap_start,
 465                                (PTE::kmap_end - PTE::kmap_start + 1) * sizeof(PTE));
 466                 } else {
 467                         // FIXME: growable levels
 468                         num_levels = PTE::num_levels;
 469                         bzero(table, PTE::page_size);
 470                 }
 471
 472                 toplevel_shift = lastlevel_shift = PTE::page_shift;
 473
 474                 if (num_levels > 1) {
 475                         lastlevel_shift += PTE::shift_per_level;
 476                         toplevel_shift += PTE::shift_per_level +
 477                                                (num_levels - 2) * DirPTE::shift_per_level;
 478                 }
 479         }
 480
 481         template <typename PTE>
 482         PageTableImpl<PTE>::PageTableImpl(void *table) : PageTable(true)
 483         {
 484                 assert(!kernel_page_table);
 485
 486                 toplevel = table;
 487                 num_levels = PTE::num_levels;
 488                 kernel_page_table = this;
 489         }
 490
 491         template <typename PTE>
 492         PageTableImpl<PTE>::~PageTableImpl()
 493         {
 494                 assert(this != kernel_page_table);
 495
 496                 if (is_process) {
 497                         Region region1 = { 0, ((VirtAddr)PTE::kmap_start - 1) << toplevel_shift };
 498                         Region region2 = { ((VirtAddr)PTE::kmap_end + 1) << toplevel_shift, ~0UL };
 499
 500                         if (PTE::kmap_start != 0)
 501                                 unmap(region1);
 502                         if (PTE::kmap_end != pages_per_dtable() - 1)
 503                                 unmap(region2);
 504                 } else {
 505                         Region region = { 0, ~0UL };
 506                         unmap(region);
 507                 }
 508
 509                 Page *page = kvirt_to_page(toplevel);
 510                 assert(page->flags & Page::InUse);
 511                 assert(page->inuse.refcount == 1);
 512
 513                 Mem::free_pages(toplevel, 1);
 514         }
 515
 516         template class PageTableImpl<Arch::PTE>;
 517         template class PageTableImpl<GenPTE>;
 518 }