kernel/fiasco/src/kern/ptab_base.cpp

   1 INTERFACE:
   2
   3 #include "mem_layout.h"
   4 //#include <cstdio>
   5
   6 namespace Ptab
   7 {
   8
   9   struct Null_alloc
  10   {
  11     static void *alloc(unsigned long) { return 0; }
  12     static void free(void *) {}
  13     static bool valid() { return false; }
  14     static unsigned to_phys(void *) { return 0; }
  15   };
  16
  17   template< typename _Head, typename _Tail >
  18   struct List
  19   {
  20     typedef _Head Head;
  21     typedef _Tail Tail;
  22   };
  23
  24   template< typename ...T >
  25   struct Tupel;
  26
  27   template< typename T >
  28   struct Tupel<T>;
  29
  30   template< typename H, typename T >
  31   struct Tupel<H, T> { typedef Ptab::List<H, T> List; };
  32
  33   template<typename T1, typename T2, typename T3, typename ...X>
  34   struct Tupel<T1, T2, T3, X...>
  35   { typedef Ptab::List<T1, typename Tupel<T2, T3, X...>::List > List; };
  36
  37   template< typename _T, unsigned _Level >
  38   struct Level
  39   {
  40     typedef _T Traits;
  41
  42     static unsigned shift(unsigned)
  43     { return Traits::Shift; }
  44
  45     static unsigned size(unsigned)
  46     { return Traits::Size; }
  47
  48     static unsigned length(unsigned)
  49     { return 1UL << Traits::Size; }
  50
  51     static Address index(unsigned /*level*/, Address addr)
  52     { return (addr >> Traits::Shift) & ((1UL << Traits::Size)-1); }
  53
  54     static unsigned entry_size(unsigned)
  55     { return sizeof(typename Traits::Entry); }
  56
  57   };
  58
  59   template< typename _Head, typename _Tail, unsigned _Level >
  60   struct Level< List<_Head, _Tail>, _Level >
  61   {
  62     typedef Level<_Tail, _Level - 1> Next_level;
  63     typedef _Head Traits;
  64
  65     static unsigned shift(unsigned level)
  66     {
  67       if (!level)
  68         return Traits::Shift;
  69       else
  70         return Next_level::shift(level - 1);
  71     }
  72
  73     static unsigned size(unsigned level)
  74     {
  75       if (!level)
  76         return Traits::Size;
  77       else
  78         return Next_level::size(level - 1);
  79     }
  80
  81     static unsigned length(unsigned level)
  82     {
  83       if (!level)
  84         return 1UL << Traits::Size;
  85       else
  86         return Next_level::length(level - 1);
  87     }
  88
  89     static Address index(unsigned level, Address addr)
  90     {
  91       if (!level)
  92         return (addr >> Traits::Shift) & ((1UL << Traits::Size)-1);
  93       else
  94         return Next_level::index(level - 1, addr);
  95     }
  96
  97     static unsigned entry_size(unsigned level)
  98     {
  99       if (!level)
 100         return sizeof(typename Traits::Entry);
 101       else
 102         return Next_level::entry_size(level - 1);
 103     }
 104
 105   };
 106
 107   template< typename _Head, typename _Tail>
 108   struct Level< List<_Head, _Tail>, 0> : Level<_Head, 0>
 109   {
 110   };
 111
 112   template< typename _Traits >
 113   struct Entry_vec
 114   {
 115     typedef typename _Traits::Entry Entry;
 116     enum
 117     {
 118       Length = 1UL << _Traits::Size,
 119       Size   = _Traits::Size,
 120       Mask   = _Traits::Mask,
 121       Shift  = _Traits::Shift,
 122     };
 123
 124
 125     Entry _e[Length];
 126
 127     static unsigned idx(Address virt)
 128     {
 129       if (Mask)
 130         return cxx::get_lsb(virt >> Shift, (Address)Size);
 131       else
 132         return (virt >> Shift);
 133     }
 134
 135     Entry &operator [] (unsigned idx) { return _e[idx]; }
 136     Entry const &operator [] (unsigned idx) const { return _e[idx]; }
 137
 138     template<typename PTE_PTR>
 139     void clear(unsigned level, bool force_write_back)
 140     {
 141       for (unsigned i=0; i < Length; ++i)
 142         PTE_PTR(&_e[i], level).clear();
 143
 144       if (force_write_back)
 145         PTE_PTR::write_back(&_e[0], &_e[Length]);
 146     }
 147   };
 148
 149
 150   template< typename _Last, typename PTE_PTR, int DEPTH = 0 >
 151   class Walk
 152   {
 153   public:
 154     enum { Max_depth = 0 };
 155     enum { Depth = DEPTH };
 156     typedef _Last Level;
 157     typedef typename _Last::Entry Entry;
 158     typedef _Last Traits;
 159
 160   private:
 161     typedef Walk<_Last, PTE_PTR, DEPTH> This;
 162     typedef Entry_vec<Level> Vec;
 163     Vec _e;
 164
 165   public:
 166     void clear(bool force_write_back)
 167     { _e.template clear<PTE_PTR>(Depth, force_write_back); }
 168
 169     template< typename _Alloc >
 170     PTE_PTR walk(Address virt, unsigned, bool, _Alloc const &)
 171     { return PTE_PTR(&_e[Vec::idx(virt)], Depth); }
 172
 173     void unmap(Address &start, unsigned long &size, unsigned, bool force_write_back)
 174     {
 175       unsigned idx = Vec::idx(start);
 176       unsigned cnt = size >> Traits::Shift;
 177       if (cnt + idx > Vec::Length)
 178         cnt = Vec::Length - idx;
 179       unsigned const e = idx + cnt;
 180
 181       for (unsigned i = idx; i != e; ++i)
 182         PTE_PTR(&_e[i], Depth).clear();
 183
 184       if (force_write_back)
 185         PTE_PTR::write_back(&_e[idx], &_e[e]);
 186
 187       start += (unsigned long)cnt << Traits::Shift;
 188       size  -= (unsigned long)cnt << Traits::Shift;
 189     }
 190
 191     template< typename _Alloc >
 192     void map(Address &phys, Address &virt, unsigned long &size,
 193              unsigned long attr, unsigned, bool force_write_back,
 194              _Alloc const &)
 195     {
 196       unsigned idx = Vec::idx(virt);
 197       unsigned cnt = size >> Traits::Shift;
 198       if (cnt + idx > Vec::Length)
 199         cnt = Vec::Length - idx;
 200       unsigned const e = idx + cnt;
 201
 202       for (unsigned i = idx; i != e; ++i, phys += (1ULL << (Traits::Shift + Traits::Base_shift)))
 203         PTE_PTR(&_e[i], Depth).set_page(phys, attr);
 204
 205       if (force_write_back)
 206         PTE_PTR::write_back(&_e[idx], &_e[e]);
 207
 208       virt += (unsigned long)cnt << Traits::Shift;
 209       size -= (unsigned long)cnt << Traits::Shift;
 210     }
 211
 212     template< typename _Alloc >
 213     void destroy(Address, Address, unsigned, unsigned, _Alloc const &)
 214     {}
 215
 216     template< typename _Alloc >
 217     int sync(Address &l_addr, This const &_r, Address &r_addr,
 218              Address &size, unsigned, bool force_write_back, _Alloc const &)
 219     {
 220       unsigned count = size >> Traits::Shift;
 221       unsigned const l = Vec::idx(l_addr);
 222       unsigned const r = Vec::idx(r_addr);
 223       unsigned const m = l > r ? l : r;
 224
 225       if (m + count >= Vec::Length)
 226         count = Vec::Length - m;
 227
 228       Entry *le = &_e[l];
 229       Entry const *re = &_r._e[r];
 230
 231       bool need_flush = false;
 232
 233       for (unsigned n = count; n > 0; --n)
 234         {
 235           if (PTE_PTR(&le[n-1], Depth).is_valid())
 236             need_flush = true;
 237 #if 0
 238           // This loop seems unnecessary, but remote_update is also used for
 239           // updating the long IPC window.
 240           // Now consider following scenario with super pages:
 241           // Sender A makes long IPC to receiver B.
 242           // A setups the IPC window by reading the pagedir slot from B in an
 243           // temporary register. Now the sender is preempted by C. Then C unmaps
 244           // the corresponding super page from B. C switch to A back, using
 245           // switch_to, which clears the IPC window pde slots from A. BUT then A
 246           // write the  content of the temporary register, which contain the now
 247           // invalid pde slot, in his own page directory and starts the long IPC.
 248           // Because no pagefault will happen, A will write to now invalid memory.
 249           // So we compare after storing the pde slot, if the copy is still
 250           // valid. And this solution is much faster than grabbing the cpu lock,
 251           // when updating the ipc window.h
 252           for (;;)
 253             {
 254               typename Traits::Raw const volatile *rr
 255                 = reinterpret_cast<typename Traits::Raw const *>(re + n - 1);
 256               le[n - 1] = *(Entry *)rr;
 257               if (EXPECT_TRUE(le[n - 1].raw() == *rr))
 258                 break;
 259             }
 260 #endif
 261           le[n - 1] = re[n - 1];
 262         }
 263
 264       if (force_write_back)
 265         PTE_PTR::write_back(&le[0], &le[count]);
 266
 267       l_addr += (unsigned long)count << Traits::Shift;
 268       r_addr += (unsigned long)count << Traits::Shift;
 269       size -= (unsigned long)count << Traits::Shift;
 270       return need_flush;
 271     }
 272   };
 273
 274
 275
 276   template< typename _Head, typename _Tail, typename PTE_PTR, int DEPTH >
 277   class Walk <List <_Head,_Tail>, PTE_PTR, DEPTH >
 278   {
 279   public:
 280     typedef Walk<_Tail, PTE_PTR, DEPTH + 1> Next;
 281     typedef typename Next::Level Level;
 282     typedef typename _Head::Entry Entry;
 283     typedef _Head Traits;
 284
 285     enum { Max_depth = Next::Max_depth + 1 };
 286     enum { Depth = DEPTH };
 287
 288   private:
 289     typedef Walk<_Head, PTE_PTR, DEPTH> This;
 290     typedef Walk< List< _Head, _Tail >, PTE_PTR, DEPTH> This2;
 291     typedef Entry_vec<_Head> Vec;
 292     Vec _e;
 293
 294     template< typename _Alloc >
 295     Next *alloc_next(PTE_PTR e, _Alloc const &a, bool force_write_back)
 296     {
 297       Next *n = (Next*)a.alloc(sizeof(Next));
 298       if (EXPECT_FALSE(!n))
 299         return 0;
 300
 301       n->clear(force_write_back);
 302       e.set_next_level(a.to_phys(n));
 303       e.write_back_if(force_write_back);
 304
 305       return n;
 306     }
 307
 308   public:
 309     void clear(bool force_write_back)
 310     { _e.template clear<PTE_PTR>(Depth, force_write_back); }
 311
 312     template< typename _Alloc >
 313     PTE_PTR walk(Address virt, unsigned level, bool force_write_back, _Alloc const &alloc)
 314     {
 315       PTE_PTR e(&_e[Vec::idx(virt)], Depth);
 316
 317       if (!level)
 318         return e;
 319       else if (!e.is_valid())
 320         {
 321           Next *n;
 322           if (alloc.valid() && (n = alloc_next(e, alloc, force_write_back)))
 323             return n->walk(virt, level - 1, force_write_back, alloc);
 324           else
 325             return e;
 326         }
 327       else if (e.is_leaf())
 328         return e;
 329       else
 330         {
 331           Next *n = (Next*)Mem_layout::phys_to_pmem(e.next_level());
 332           return n->walk(virt, level - 1, force_write_back, alloc);
 333         }
 334     }
 335
 336     void unmap(Address &start, unsigned long &size, unsigned level,
 337                bool force_write_back)
 338     {
 339       if (!level)
 340         {
 341           reinterpret_cast<This*>(this)->unmap(start, size, 0,
 342                                                force_write_back);
 343           return;
 344         }
 345
 346       while (size)
 347         {
 348           PTE_PTR e(&_e[Vec::idx(start)], Depth);
 349
 350           if (!e.is_valid() || e.is_leaf())
 351             continue;
 352
 353           Next *n = (Next*)Mem_layout::phys_to_pmem(e.next_level());
 354           n->unmap(start, size, level - 1, force_write_back);
 355         }
 356     }
 357
 358     template< typename _Alloc >
 359     void map(Address &phys, Address &virt, unsigned long &size,
 360              unsigned long attr, unsigned level, bool force_write_back,
 361              _Alloc const &alloc)
 362     {
 363       if (!level)
 364         {
 365           reinterpret_cast<This*>(this)->map(phys, virt, size, attr, 0,
 366                                              force_write_back, alloc);
 367           return;
 368         }
 369
 370       while (size)
 371         {
 372           PTE_PTR e(&_e[Vec::idx(virt)], Depth);
 373           Next *n;
 374           if (!e.is_valid())
 375             {
 376               if (alloc.valid() && (n = alloc_next(e, alloc, force_write_back)))
 377                 n->map(phys, virt, size, attr, level - 1,
 378                        force_write_back, alloc);
 379
 380               continue;
 381             }
 382
 383           if (_Head::May_be_leaf && e.is_leaf())
 384             continue;
 385
 386           n = (Next*)Mem_layout::phys_to_pmem(e.next_level());
 387           n->map(phys, virt, size, attr, level - 1, force_write_back, alloc);
 388         }
 389     }
 390
 391     template< typename _Alloc >
 392     void destroy(Address start, Address end,
 393                  unsigned start_level, unsigned end_level,
 394                  _Alloc const &alloc)
 395     {
 396       //printf("destroy: %*.s%lx-%lx lvl=%d:%d depth=%d\n", Depth*2, "            ", start, end, start_level, end_level, Depth);
 397       if (!alloc.valid() || Depth >= end_level)
 398         return;
 399
 400       unsigned idx_start = Vec::idx(start);
 401       unsigned idx_end = Vec::idx(end) + 1;
 402       //printf("destroy: %*.sidx: %d:%d\n", Depth*2, "            ", idx_start, idx_end);
 403
 404       for (unsigned idx = idx_start; idx < idx_end; ++idx)
 405         {
 406           PTE_PTR e(&_e[idx], Depth);
 407           if (!e.is_valid() || (_Head::May_be_leaf && e.is_leaf()))
 408             continue;
 409
 410           Next *n = (Next*)Mem_layout::phys_to_pmem(e.next_level());
 411           if (Depth < end_level)
 412             n->destroy(idx > idx_start ? 0 : start,
 413                        idx + 1 < idx_end ? (1UL << Traits::Shift)-1 : end,
 414                        start_level, end_level, alloc);
 415           if (Depth >= start_level)
 416             {
 417               //printf("destroy: %*.sfree: %p: %p(%d)\n", Depth*2, "            ", this, n, sizeof(Next));
 418               alloc.free(n, sizeof(Next));
 419             }
 420         }
 421     }
 422
 423     template< typename _Alloc >
 424     int sync(Address &l_a, This2 const &_r, Address &r_a,
 425              Address &size, unsigned level, bool force_write_back,
 426              _Alloc const &alloc)
 427     {
 428       if (!level)
 429         return reinterpret_cast<This*>(this)
 430           ->sync(l_a, reinterpret_cast<This const &>(_r), r_a, size, 0,
 431               force_write_back, alloc);
 432
 433       unsigned count = size >> Traits::Shift;
 434         {
 435           unsigned const lx = Vec::idx(l_a);
 436           unsigned const rx = Vec::idx(r_a);
 437           unsigned const mx = lx > rx ? lx : rx;
 438           if (mx + count >= Vec::Length)
 439             count = Vec::Length - mx;
 440         }
 441
 442       bool need_flush = false;
 443
 444       for (unsigned i = count; size && i > 0; --i) //while (size)
 445         {
 446           PTE_PTR l(&_e[Vec::idx(l_a)], Depth);
 447           PTE_PTR r(const_cast<Entry *>(&_r._e[Vec::idx(r_a)]), Depth);
 448           Next *n = 0;
 449           if (!r.is_valid())
 450             {
 451               l_a += 1UL << Traits::Shift;
 452               r_a += 1UL << Traits::Shift;
 453               if (size > 1UL << Traits::Shift)
 454                 {
 455                   size -= 1UL << Traits::Shift;
 456                   continue;
 457                 }
 458               break;
 459             }
 460
 461           if (!l.is_valid())
 462             {
 463               if (!alloc.valid() || !(n = alloc_next(l, alloc, force_write_back)))
 464                 return -1;
 465             }
 466           else
 467             n = (Next*)Mem_layout::phys_to_pmem(l.next_level());
 468
 469           Next *rn = (Next*)Mem_layout::phys_to_pmem(r.next_level());
 470
 471           int err = n->sync(l_a, *rn, r_a, size, level - 1, force_write_back, alloc);
 472           if (err > 0)
 473             need_flush = true;
 474
 475           if (err < 0)
 476             return err;
 477         }
 478
 479       return need_flush;
 480     }
 481
 482   };
 483
 484   template< typename _E, typename PT >
 485   struct Pte_ptr
 486   {
 487     Pte_ptr(_E *e, unsigned char level) : e(e), l(level) {}
 488
 489     template< typename _I2 >
 490     Pte_ptr(_I2 const &o) : e(o.e), l(o.l) {}
 491
 492     unsigned char level() const { return l; }
 493
 494     unsigned page_order() const
 495     { return PT::page_order_for_level(l); }
 496
 497     _E *e;
 498     unsigned char l;
 499   };
 500
 501   template
 502   <
 503     typename _Entry,
 504     unsigned _Shift,
 505     unsigned _Size,
 506     bool _May_be_leaf,
 507     bool _Mask = true,
 508     unsigned _Base_shift = 0
 509   >
 510   struct Traits
 511   {
 512     typedef _Entry Entry;
 513
 514     enum
 515     {
 516       May_be_leaf = _May_be_leaf,
 517       Shift = _Shift,
 518       Size = _Size,
 519       Mask = _Mask,
 520       Base_shift = _Base_shift
 521     };
 522   };
 523
 524   template< typename _T, unsigned _Shift >
 525   struct Shift
 526   {
 527     typedef _T Orig_list;
 528     typedef Ptab::Traits
 529       < typename _T::Entry,
 530         _T::Shift - _Shift,
 531         _T::Size,
 532         _T::May_be_leaf,
 533         _T::Mask,
 534         _T::Base_shift + _Shift
 535       > List;
 536   };
 537
 538   template< typename _Head, typename _Tail, unsigned _Shift >
 539   struct Shift< List<_Head, _Tail>, _Shift >
 540   {
 541     typedef Ptab::List<_Head, _Tail> Orig_list;
 542     typedef Ptab::List
 543     <
 544       typename Shift<_Head, _Shift>::List,
 545       typename Shift<_Tail, _Shift>::List
 546     > List;
 547   };
 548
 549   struct Address_wrap
 550   {
 551     enum { Shift = 0 };
 552     typedef Address Value_type;
 553     static Address val(Address a) { return a; }
 554   };
 555
 556   template< typename N, int SHIFT >
 557   struct Page_addr_wrap
 558   {
 559     enum { Shift = SHIFT };
 560     typedef N Value_type;
 561     static typename N::Value val(N a)
 562     { return N::val(a); }
 563
 564     static typename Value_type::Diff_type::Value
 565     val(typename Value_type::Diff_type a)
 566     { return cxx::int_value<typename Value_type::Diff_type>(a); }
 567   };
 568
 569   template
 570   <
 571     typename PTE_PTR,
 572     typename _Traits,
 573     typename _Addr = Address_wrap
 574   >
 575   class Base
 576   {
 577   public:
 578     typedef typename _Addr::Value_type Va;
 579     typedef typename _Addr::Value_type::Diff_type Vs;
 580     typedef _Traits Traits;
 581     typedef PTE_PTR Pte_ptr;
 582     typedef typename _Traits::Head L0;
 583
 584     enum
 585     {
 586       Base_shift = L0::Base_shift,
 587     };
 588
 589   private:
 590     typedef Ptab::Walk<_Traits, PTE_PTR> Walk;
 591
 592   public:
 593     enum { Depth = Walk::Max_depth };
 594
 595     typedef Level<Traits, Depth> Levels;
 596
 597     static unsigned lsb_for_level(unsigned level)
 598     { return Levels::shift(level); }
 599
 600     static unsigned page_order_for_level(unsigned level)
 601     { return Levels::shift(level) + Base_shift; }
 602
 603     template< typename _Alloc >
 604     PTE_PTR walk(Va virt, unsigned level, bool force_write_back, _Alloc const &alloc)
 605     { return _base.walk(_Addr::val(virt), level, force_write_back, alloc); }
 606
 607     PTE_PTR walk(Va virt, unsigned level = Depth) const
 608     { return const_cast<Walk&>(_base).walk(_Addr::val(virt), level, false, Null_alloc()); }
 609
 610
 611     template< typename OPTE_PTR, typename _Alloc >
 612     int sync(Va l_addr, Base< OPTE_PTR, _Traits, _Addr> const *_r,
 613              Va r_addr, Vs size, unsigned level = Depth,
 614              bool force_write_back = false,
 615              _Alloc const &alloc = _Alloc())
 616     {
 617       Address la = _Addr::val(l_addr);
 618       Address ra = _Addr::val(r_addr);
 619       Address sz = _Addr::val(size);
 620       return _base.sync(la, _r->_base,
 621                         ra, sz, level, force_write_back,
 622                         alloc);
 623     }
 624
 625     void clear(bool force_write_back)
 626     { _base.clear(force_write_back); }
 627
 628     void unmap(Va virt, Vs size, unsigned level, bool force_write_back)
 629     {
 630       Address va = _Addr::val(virt);
 631       unsigned long sz = _Addr::val(size);
 632       _base.unmap(va, sz, level, force_write_back);
 633     }
 634
 635     template< typename _Alloc >
 636     void map(Address phys, Va virt, Vs size, unsigned long attr,
 637              unsigned level, bool force_write_back,
 638              _Alloc const &alloc = _Alloc())
 639     {
 640       Address va = _Addr::val(virt);
 641       unsigned long sz = _Addr::val(size);
 642       _base.map(phys, va, sz, attr, level, force_write_back, alloc);
 643     }
 644
 645     template< typename _Alloc >
 646     void destroy(Va start, Va end, unsigned start_level, unsigned end_level,
 647                  _Alloc const &alloc = _Alloc())
 648     {
 649       _base.destroy(_Addr::val(start), _Addr::val(end),
 650                     start_level, end_level, alloc);
 651     }
 652
 653 #if 0
 654     template< typename _New_alloc >
 655     Base<_Base_entry, _Traits, _New_alloc, _Addr> *alloc_cast()
 656     { return reinterpret_cast<Base<_Base_entry, _Traits, _New_alloc, _Addr> *>(this); }
 657
 658     template< typename _New_alloc >
 659     Base<_Base_entry, _Traits, _New_alloc, _Addr> const *alloc_cast() const
 660     { return reinterpret_cast<Base<_Base_entry, _Traits, _New_alloc, _Addr> const *>(this); }
 661 #endif
 662
 663   private:
 664     Walk _base;
 665   };
 666
 667 };