pm: Remove the venerable pm_remove_contig()
[akaros.git] / kern / src / pagemap.c
1 /* Copyright (c) 2014 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Page mapping: maps an object (inode or block dev) in page size chunks.
6  * Analagous to Linux's "struct address space" */
7
8 #include <pmap.h>
9 #include <atomic.h>
10 #include <radix.h>
11 #include <kref.h>
12 #include <assert.h>
13 #include <stdio.h>
14 #include <pagemap.h>
15 #include <rcu.h>
16
17 void pm_add_vmr(struct page_map *pm, struct vm_region *vmr)
18 {
19         /* note that the VMR being reverse-mapped by the PM is protected by the PM's
20          * lock.  we clearly need a write lock here, but removal also needs a write
21          * lock, so later when removal holds this, it delays munmaps and keeps the
22          * VMR connected. */
23         spin_lock(&pm->pm_lock);
24         TAILQ_INSERT_TAIL(&pm->pm_vmrs, vmr, vm_pm_link);
25         spin_unlock(&pm->pm_lock);
26 }
27
28 void pm_remove_vmr(struct page_map *pm, struct vm_region *vmr)
29 {
30         spin_lock(&pm->pm_lock);
31         TAILQ_REMOVE(&pm->pm_vmrs, vmr, vm_pm_link);
32         spin_unlock(&pm->pm_lock);
33 }
34
35 /* PM slot void *s look like this:
36  *
37  * |--11--|--1--|----52 or 20 bits--|
38  * | ref  | flag|    ppn of page    |
39  *              \  <--- meta shift -/
40  *
41  * The setter funcs return the void* that should update slot_val; it doesn't
42  * change slot_val in place (it's a val, not the addr) */
43
44 #ifdef CONFIG_64BIT
45 # define PM_FLAGS_SHIFT 52
46 #else
47 # define PM_FLAGS_SHIFT 20
48 #endif
49 #define PM_REFCNT_SHIFT (PM_FLAGS_SHIFT + 1)
50
51 #define PM_UNUSED_FLAG (1UL << PM_FLAGS_SHIFT)
52
53 static int pm_slot_check_refcnt(void *slot_val)
54 {
55         return (unsigned long)slot_val >> PM_REFCNT_SHIFT;
56 }
57
58 static void *pm_slot_inc_refcnt(void *slot_val)
59 {
60         void *ret;
61
62         ret = (void*)((unsigned long)slot_val + (1UL << PM_REFCNT_SHIFT));
63         /* Catches previously negative refcnts */
64         assert(pm_slot_check_refcnt(ret) > 0);
65         return ret;
66 }
67
68 static void *pm_slot_dec_refcnt(void *slot_val)
69 {
70         assert(pm_slot_check_refcnt(slot_val) > 0);
71         return (void*)((unsigned long)slot_val - (1UL << PM_REFCNT_SHIFT));
72 }
73
74 static struct page *pm_slot_get_page(void *slot_val)
75 {
76         if (!slot_val)
77                 return 0;
78         return ppn2page((unsigned long)slot_val & ((1UL << PM_FLAGS_SHIFT) - 1));
79 }
80
81 static void *pm_slot_set_page(void *slot_val, struct page *pg)
82 {
83         assert(pg != pages);    /* we should never alloc page 0, for sanity */
84         return (void*)(page2ppn(pg) | ((unsigned long)slot_val &
85                                        ~((1UL << PM_FLAGS_SHIFT) - 1)));
86 }
87
88 /* Initializes a PM.  Host should be an fs_file.  The reference this stores is
89  * uncounted. */
90 void pm_init(struct page_map *pm, struct page_map_operations *op, void *host)
91 {
92         pm->pm_file = host;
93         radix_tree_init(&pm->pm_tree);
94         pm->pm_num_pages = 0;
95         pm->pm_op = op;
96         qlock_init(&pm->pm_qlock);
97         spinlock_init(&pm->pm_lock);
98         TAILQ_INIT(&pm->pm_vmrs);
99 }
100
101 /* Looks up the index'th page in the page map, returning a refcnt'd reference
102  * that need to be dropped with pm_put_page, or 0 if it was not in the map. */
103 static struct page *pm_find_page(struct page_map *pm, unsigned long index)
104 {
105         void **tree_slot;
106         void *old_slot_val, *slot_val;
107         struct page *page = 0;
108
109         /* We use rcu to protect our radix walk, specifically the tree_slot pointer.
110          * We get our own 'pm refcnt' on the slot itself, which doesn't need RCU. */
111         rcu_read_lock();
112         /* We're syncing with removal.  The deal is that if we grab the page (and
113          * we'd only do that if the page != 0), we up the slot ref and clear
114          * removal.  A remover will only remove it if removal is still set.  If we
115          * grab and release while removal is in progress, even though we no longer
116          * hold the ref, we have unset removal.  Also, to prevent removal where we
117          * get a page well before the removal process, the removal won't even bother
118          * when the slot refcnt is upped. */
119         tree_slot = radix_lookup_slot(&pm->pm_tree, index);
120         if (!tree_slot)
121                 goto out;
122         do {
123                 old_slot_val = ACCESS_ONCE(*tree_slot);
124                 slot_val = old_slot_val;
125                 page = pm_slot_get_page(slot_val);
126                 if (!page)
127                         goto out;
128                 slot_val = pm_slot_inc_refcnt(slot_val);        /* not a page kref */
129         } while (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val));
130         assert(page->pg_tree_slot == tree_slot);
131 out:
132         rcu_read_unlock();
133         return page;
134 }
135
136 /* Attempts to insert the page into the page_map, returns 0 for success, or an
137  * error code if there was one already (EEXIST) or we ran out of memory
138  * (ENOMEM).
139  *
140  * On success, callers *lose* their page ref, but get a PM slot ref.  This slot
141  * ref is sufficient to keep the page alive (slot ref protects the page ref)..
142  *
143  * Makes no assumptions about the quality of the data loaded, that's up to the
144  * caller. */
145 static int pm_insert_page(struct page_map *pm, unsigned long index,
146                           struct page *page)
147 {
148         int ret;
149         void **tree_slot;
150         void *slot_val = 0;
151
152         page->pg_mapping = pm;  /* debugging */
153         page->pg_index = index;
154         /* no one should be looking at the tree slot til we stop write locking.  the
155          * only other one who looks is removal, who requires a PM write lock. */
156         page->pg_tree_slot = (void*)0xdeadbeef; /* poison */
157         slot_val = pm_slot_inc_refcnt(slot_val);
158         /* passing the page ref from the caller to the slot */
159         slot_val = pm_slot_set_page(slot_val, page);
160         qlock(&pm->pm_qlock);
161         ret = radix_insert(&pm->pm_tree, index, slot_val, &tree_slot);
162         if (ret) {
163                 qunlock(&pm->pm_qlock);
164                 return ret;
165         }
166         page->pg_tree_slot = tree_slot;
167         pm->pm_num_pages++;
168         qunlock(&pm->pm_qlock);
169         return 0;
170 }
171
172 /* Decrefs the PM slot ref (usage of a PM page).  The PM's page ref remains. */
173 void pm_put_page(struct page *page)
174 {
175         void **tree_slot = page->pg_tree_slot;
176
177         assert(tree_slot);
178         assert(pm_slot_get_page(*tree_slot) == page);
179         assert(pm_slot_check_refcnt(*tree_slot) > 0);
180         /* decref, don't care about CASing */
181         atomic_add((atomic_t*)tree_slot, -(1UL << PM_REFCNT_SHIFT));
182 }
183
184 /* Makes sure the index'th page of the mapped object is loaded in the page cache
185  * and returns its location via **pp.
186  *
187  * You'll get a pm-slot refcnt back, which you need to put when you're done. */
188 int pm_load_page(struct page_map *pm, unsigned long index, struct page **pp)
189 {
190         struct page *page;
191         int error;
192
193         page = pm_find_page(pm, index);
194         while (!page) {
195                 if (kpage_alloc(&page))
196                         return -ENOMEM;
197                 /* important that UP_TO_DATE is not set.  once we put it in the PM,
198                  * others can find it, and we still need to fill it. */
199                 atomic_set(&page->pg_flags, PG_LOCKED | PG_PAGEMAP);
200                 /* The sem needs to be initted before anyone can try to lock it, meaning
201                  * before it is in the page cache.  We also want it locked preemptively,
202                  * by setting signals = 0. */
203                 sem_init(&page->pg_sem, 0);
204                 error = pm_insert_page(pm, index, page);
205                 switch (error) {
206                         case 0:
207                                 goto load_locked_page;
208                                 break;
209                         case -EEXIST:
210                                 /* the page was mapped already (benign race), just get rid of
211                                  * our page and try again (the only case that uses the while) */
212                                 atomic_set(&page->pg_flags, 0);
213                                 page_decref(page);
214                                 page = pm_find_page(pm, index);
215                                 break;
216                         default:
217                                 atomic_set(&page->pg_flags, 0);
218                                 page_decref(page);
219                                 return error;
220                 }
221         }
222         assert(page);
223         assert(pm_slot_check_refcnt(*page->pg_tree_slot));
224         assert(pm_slot_get_page(*page->pg_tree_slot) == page);
225         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
226                 *pp = page;
227                 printd("pm %p FOUND page %p, addr %p, idx %d\n", pm, page,
228                        page2kva(page), index);
229                 return 0;
230         }
231         lock_page(page);
232         /* double-check.  if we we blocked on lock_page, it was probably for someone
233          * else loading.  plus, we can't load a page more than once (it could
234          * clobber newer writes) */
235         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
236                 unlock_page(page);
237                 *pp = page;
238                 return 0;
239         }
240         /* fall through */
241 load_locked_page:
242         error = pm->pm_op->readpage(pm, page);
243         assert(!error);
244         assert(atomic_read(&page->pg_flags) & PG_UPTODATE);
245         unlock_page(page);
246         *pp = page;
247         printd("pm %p LOADS page %p, addr %p, idx %d\n", pm, page,
248                page2kva(page), index);
249         return 0;
250 }
251
252 int pm_load_page_nowait(struct page_map *pm, unsigned long index,
253                         struct page **pp)
254 {
255         struct page *page = pm_find_page(pm, index);
256         if (!page)
257                 return -EAGAIN;
258         if (!(atomic_read(&page->pg_flags) & PG_UPTODATE)) {
259                 /* TODO: could have a read_nowait pm_op */
260                 pm_put_page(page);
261                 return -EAGAIN;
262         }
263         *pp = page;
264         return 0;
265 }
266
267 static bool vmr_has_page_idx(struct vm_region *vmr, unsigned long pg_idx)
268 {
269         unsigned long nr_pgs = (vmr->vm_end - vmr->vm_base) >> PGSHIFT;
270         unsigned long start_pg = vmr->vm_foff >> PGSHIFT;
271
272         if (!vmr->vm_ready)
273                 return false;
274         return ((start_pg <= pg_idx) && (pg_idx < start_pg + nr_pgs));
275 }
276
277 /* Runs CB on every PTE in the VMR that corresponds to the file's pg_idx, for up
278  * to max_nr_pgs. */
279 static void vmr_for_each(struct vm_region *vmr, unsigned long pg_idx,
280                          unsigned long max_nr_pgs, mem_walk_callback_t callback)
281 {
282         uintptr_t start_va;
283         off64_t file_off = pg_idx << PGSHIFT;
284         size_t len = max_nr_pgs << PGSHIFT;
285
286         if (file_off < vmr->vm_foff) {
287                 len -= vmr->vm_foff - file_off;
288                 file_off = vmr->vm_foff;
289         }
290
291         start_va = vmr->vm_base + (file_off - vmr->vm_foff);
292         if (start_va < vmr->vm_base) {
293                 warn("wraparound! %p %p %p %p", start_va, vmr->vm_base, vmr->vm_foff,
294                      pg_idx);
295                 return;
296         }
297         if (start_va >= vmr->vm_end)
298                 return;
299
300         len = MIN(len, vmr->vm_end - start_va);
301         if (!len)
302                 return;
303         env_user_mem_walk(vmr->vm_proc, (void*)start_va, len, callback, vmr);
304 }
305
306 static bool pm_has_vmr_with_page(struct page_map *pm, unsigned long pg_idx)
307 {
308         struct vm_region *vmr_i;
309
310         spin_lock(&pm->pm_lock);
311         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
312                 if (vmr_has_page_idx(vmr_i, pg_idx)) {
313                         spin_unlock(&pm->pm_lock);
314                         return true;
315                 }
316         }
317         spin_unlock(&pm->pm_lock);
318         return false;
319 }
320
321 static bool __remove_or_zero_cb(void **slot, unsigned long tree_idx, void *arg)
322 {
323         struct page_map *pm = arg;
324         struct page *page;
325         void *old_slot_val, *slot_val;
326
327         old_slot_val = ACCESS_ONCE(*slot);
328         slot_val = old_slot_val;
329         page = pm_slot_get_page(slot_val);
330         /* We shouldn't have an item in the tree without a page, unless there's
331          * another removal.  Currently, this CB is called with a qlock. */
332         assert(page);
333         /* Don't even bother with VMRs that might have faulted in the page */
334         if (pm_has_vmr_with_page(pm, tree_idx)) {
335                 memset(page2kva(page), 0, PGSIZE);
336                 return false;
337         }
338         /* syncing with lookups, writebacks, etc - anyone who gets a ref on a PM
339          * leaf/page (e.g. pm_load_page / pm_find_page. */
340         slot_val = pm_slot_set_page(slot_val, NULL);
341         if (pm_slot_check_refcnt(slot_val) ||
342                 !atomic_cas_ptr(slot, old_slot_val, slot_val)) {
343                 memset(page2kva(page), 0, PGSIZE);
344                 return false;
345         }
346         /* We yanked the page out.  The radix tree still has an item until we return
347          * true, but this is fine.  Future lock-free lookups will now fail (since
348          * the page is 0), and insertions will block on the write lock. */
349         atomic_set(&page->pg_flags, 0); /* cause/catch bugs */
350         page_decref(page);
351         return true;
352 }
353
354 void pm_remove_or_zero_pages(struct page_map *pm, unsigned long start_idx,
355                              unsigned long nr_pgs)
356 {
357         unsigned long end_idx = start_idx + nr_pgs;
358
359         assert(end_idx > start_idx);
360         qlock(&pm->pm_qlock);
361         radix_for_each_slot_in_range(&pm->pm_tree, start_idx, end_idx,
362                                      __remove_or_zero_cb, pm);
363         qunlock(&pm->pm_qlock);
364 }
365
366 static int __pm_mark_and_clear_dirty(struct proc *p, pte_t pte, void *va,
367                                      void *arg)
368 {
369         struct page *page = pa2page(pte_get_paddr(pte));
370         struct vm_region *vmr = arg;
371
372         if (!pte_is_present(pte) || !pte_is_dirty(pte))
373                 return 0;
374         if (!(atomic_read(&page->pg_flags) & PG_DIRTY))
375                 atomic_or(&page->pg_flags, PG_DIRTY);
376         pte_clear_dirty(pte);
377         vmr->vm_shootdown_needed = true;
378         return 0;
379 }
380
381 /* Dirty PTE bits will get marked to the struct page itself, and the PTEs will
382  * have the dirty bit cleared.  VMRs that need a shootdown are marked.  Note
383  * this only marks PTEs and VMRs if they were the one to do some of the
384  * dirtying. */
385 static void mark_and_clear_dirty_ptes(struct page_map *pm)
386 {
387         struct vm_region *vmr_i;
388         pte_t pte;
389
390         spin_lock(&pm->pm_lock);
391         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
392                 if (!(vmr_i->vm_prot & PROT_WRITE))
393                         continue;
394                 /* Only care about shared mappings, not private.  Private mappings have
395                  * a reference to the file, but the pages are not in the page cache -
396                  * they hang directly off the PTEs (for now). */
397                 if (!(vmr_i->vm_flags & MAP_SHARED))
398                         continue;
399                 spin_lock(&vmr_i->vm_proc->pte_lock);
400                 vmr_for_each(vmr_i, 0, ULONG_MAX, __pm_mark_and_clear_dirty);
401                 spin_unlock(&vmr_i->vm_proc->pte_lock);
402         }
403         spin_unlock(&pm->pm_lock);
404 }
405
406 static void shootdown_vmrs(struct page_map *pm)
407 {
408         struct vm_region *vmr_i;
409
410         /* The VMR flag shootdown_needed is owned by the PM.  Each VMR is hooked to
411          * at most one file, so there's no issue there.  We might have a proc that
412          * has multiple non-private VMRs in the same file, but it shouldn't be a big
413          * enough issue to worry about. */
414         spin_lock(&pm->pm_lock);
415         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
416                 if (vmr_i->vm_shootdown_needed) {
417                         vmr_i->vm_shootdown_needed = false;
418                         proc_tlbshootdown(vmr_i->vm_proc, 0, 0);
419                 }
420         }
421         spin_unlock(&pm->pm_lock);
422 }
423
424 /* Send any queued WBs that haven't been sent yet. */
425 static void flush_queued_writebacks(struct page_map *pm)
426 {
427         /* TODO (WB) */
428 }
429
430 /* Batches up pages to be written back, preferably as one big op.  If we have a
431  * bunch outstanding, we'll send them. */
432 static void queue_writeback(struct page_map *pm, struct page *page)
433 {
434         /* TODO (WB): add a bulk op (instead of only writepage()), collect extents,
435          * and send them to the device.  Probably do something similar for reads. */
436         pm->pm_op->writepage(pm, page);
437 }
438
439 static bool __writeback_cb(void **slot, unsigned long tree_idx, void *arg)
440 {
441         struct page_map *pm = arg;
442         struct page *page = pm_slot_get_page(*slot);
443
444         /* We're qlocked, so all items should have pages. */
445         assert(page);
446         if (atomic_read(&page->pg_flags) & PG_DIRTY) {
447                 atomic_and(&page->pg_flags, ~PG_DIRTY);
448                 queue_writeback(pm, page);
449         }
450         return false;
451 }
452
453 /* Every dirty page gets written back, regardless of whether it's in a VMR or
454  * not.  All the dirty bits get cleared too, before writing back. */
455 void pm_writeback_pages(struct page_map *pm)
456 {
457         qlock(&pm->pm_qlock);
458         mark_and_clear_dirty_ptes(pm);
459         shootdown_vmrs(pm);
460         radix_for_each_slot(&pm->pm_tree, __writeback_cb, pm);
461         flush_queued_writebacks(pm);
462         qunlock(&pm->pm_qlock);
463 }
464
465 static bool __flush_unused_cb(void **slot, unsigned long tree_idx, void *arg)
466 {
467         struct page_map *pm = arg;
468         struct page *page = pm_slot_get_page(*slot);
469         void *old_slot_val, *slot_val;
470
471         /* We're qlocked, so all items should have pages. */
472         assert(page);
473         old_slot_val = ACCESS_ONCE(*slot);
474         slot_val = old_slot_val;
475         /* Under any contention, we just skip it */
476         if (pm_slot_check_refcnt(slot_val))
477                 return false;
478         assert(pm_slot_get_page(slot_val) == page);
479         slot_val = pm_slot_set_page(slot_val, NULL);
480         if (!atomic_cas_ptr(slot, old_slot_val, slot_val))
481                 return false;
482         /* At this point, we yanked the page.  any concurrent wait-free users that
483          * want to get this page will fail (pm_find_page / pm_load_page_nowait).
484          * They will block on the qlock that we hold when they try to insert a page
485          * (as part of pm_load_page, for both reading or writing).  We can still
486          * bail out and everything will be fine, so long as we put the page back.
487          *
488          * We can't tell from looking at the page if it was actually faulted into
489          * the VMR; we just know it was possible.  (currently).  Also, we need to do
490          * this check after removing the page from the PM slot, since the mm
491          * faulting code (hpf) will attempt a non-blocking PM lookup. */
492         if (pm_has_vmr_with_page(pm, tree_idx)) {
493                 slot_val = pm_slot_set_page(slot_val, page);
494                 /* No one should be writing to it.  We hold the qlock, and any readers
495                  * should not have increffed while the page was NULL. */
496                 WRITE_ONCE(*slot, slot_val);
497                 return false;
498         }
499         /* Need to check PG_DIRTY *after* checking VMRs.  o/w we could check, PAUSE,
500          * see no VMRs.  But in the meantime, we had a VMR that munmapped and
501          * wrote-back the dirty flag. */
502         if (atomic_read(&page->pg_flags) & PG_DIRTY) {
503                 /* If we want to batch these, we'll also have to batch the freeing,
504                  * which isn't a big deal.  Just do it before freeing and before
505                  * unlocking the PM; we don't want someone to load the page from the
506                  * backing store and get an old value. */
507                 pm->pm_op->writepage(pm, page);
508         }
509         /* All clear - the page is unused and (now) clean. */
510         atomic_set(&page->pg_flags, 0); /* catch bugs */
511         page_decref(page);
512         return true;
513 }
514
515 /* Unused pages (not currently involved in a read, write, or mmap) are pruned.
516  * Dirty pages are written back first.
517  *
518  * We ignore anything mapped in a VMR.  Not bothering with unmapping or
519  * shootdowns or anything.  At least for now. */
520 void pm_free_unused_pages(struct page_map *pm)
521 {
522         qlock(&pm->pm_qlock);
523         radix_for_each_slot(&pm->pm_tree, __flush_unused_cb, pm);
524         qunlock(&pm->pm_qlock);
525 }
526
527 static bool __destroy_cb(void **slot, unsigned long tree_idx, void *arg)
528 {
529         struct page *page = pm_slot_get_page(*slot);
530
531         /* Should be no users or need to sync */
532         assert(pm_slot_check_refcnt(*slot) == 0);
533         atomic_set(&page->pg_flags, 0); /* catch bugs */
534         page_decref(page);
535         return true;
536 }
537
538 void pm_destroy(struct page_map *pm)
539 {
540         radix_for_each_slot(&pm->pm_tree, __destroy_cb, pm);
541         radix_tree_destroy(&pm->pm_tree);
542 }
543
544 void print_page_map_info(struct page_map *pm)
545 {
546         struct vm_region *vmr_i;
547         printk("Page Map %p\n", pm);
548         printk("\tNum pages: %lu\n", pm->pm_num_pages);
549         spin_lock(&pm->pm_lock);
550         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
551                 printk("\tVMR proc %d: (%p - %p): 0x%08x, 0x%08x, %p, %p\n",
552                        vmr_i->vm_proc->pid, vmr_i->vm_base, vmr_i->vm_end,
553                        vmr_i->vm_prot, vmr_i->vm_flags, foc_pointer(vmr_i->__vm_foc),
554                            vmr_i->vm_foff);
555         }
556         spin_unlock(&pm->pm_lock);
557 }
558
559 void pm_page_asserter(struct page *page, char *str)
560 {
561         void **tree_slot = page->pg_tree_slot;
562
563         if (!page_is_pagemap(page))
564                 return;
565         assert(tree_slot);
566         assert(pm_slot_get_page(*tree_slot) == page);
567         assert(pm_slot_check_refcnt(*tree_slot) > 0);
568 }