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