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