Switch to a simple X11-style license.
[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 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 }