pm: Add pm_writeback_pages()
[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_REMOVAL (1UL << PM_FLAGS_SHIFT)
52
53 static bool pm_slot_check_removal(void *slot_val)
54 {
55         return (unsigned long)slot_val & PM_REMOVAL ? TRUE : FALSE;
56 }
57
58 static void *pm_slot_set_removal(void *slot_val)
59 {
60         return (void*)((unsigned long)slot_val | PM_REMOVAL);
61 }
62
63 static void *pm_slot_clear_removal(void *slot_val)
64 {
65         return (void*)((unsigned long)slot_val & ~PM_REMOVAL);
66 }
67
68 static int pm_slot_check_refcnt(void *slot_val)
69 {
70         return (unsigned long)slot_val >> PM_REFCNT_SHIFT;
71 }
72
73 static void *pm_slot_inc_refcnt(void *slot_val)
74 {
75         void *ret;
76
77         ret = (void*)((unsigned long)slot_val + (1UL << PM_REFCNT_SHIFT));
78         /* Catches previously negative refcnts */
79         assert(pm_slot_check_refcnt(ret) > 0);
80         return ret;
81 }
82
83 static void *pm_slot_dec_refcnt(void *slot_val)
84 {
85         assert(pm_slot_check_refcnt(slot_val) > 0);
86         return (void*)((unsigned long)slot_val - (1UL << PM_REFCNT_SHIFT));
87 }
88
89 static struct page *pm_slot_get_page(void *slot_val)
90 {
91         if (!slot_val)
92                 return 0;
93         return ppn2page((unsigned long)slot_val & ((1UL << PM_FLAGS_SHIFT) - 1));
94 }
95
96 static void *pm_slot_set_page(void *slot_val, struct page *pg)
97 {
98         assert(pg != pages);    /* we should never alloc page 0, for sanity */
99         return (void*)(page2ppn(pg) | ((unsigned long)slot_val &
100                                        ~((1UL << PM_FLAGS_SHIFT) - 1)));
101 }
102
103 /* Initializes a PM.  Host should be an fs_file.  The reference this stores is
104  * uncounted. */
105 void pm_init(struct page_map *pm, struct page_map_operations *op, void *host)
106 {
107         pm->pm_file = host;
108         radix_tree_init(&pm->pm_tree);
109         pm->pm_num_pages = 0;
110         pm->pm_op = op;
111         qlock_init(&pm->pm_qlock);
112         spinlock_init(&pm->pm_lock);
113         TAILQ_INIT(&pm->pm_vmrs);
114 }
115
116 /* Looks up the index'th page in the page map, returning a refcnt'd reference
117  * that need to be dropped with pm_put_page, or 0 if it was not in the map. */
118 static struct page *pm_find_page(struct page_map *pm, unsigned long index)
119 {
120         void **tree_slot;
121         void *old_slot_val, *slot_val;
122         struct page *page = 0;
123
124         /* We use rcu to protect our radix walk, specifically the tree_slot pointer.
125          * We get our own 'pm refcnt' on the slot itself, which doesn't need RCU. */
126         rcu_read_lock();
127         /* We're syncing with removal.  The deal is that if we grab the page (and
128          * we'd only do that if the page != 0), we up the slot ref and clear
129          * removal.  A remover will only remove it if removal is still set.  If we
130          * grab and release while removal is in progress, even though we no longer
131          * hold the ref, we have unset removal.  Also, to prevent removal where we
132          * get a page well before the removal process, the removal won't even bother
133          * when the slot refcnt is upped. */
134         tree_slot = radix_lookup_slot(&pm->pm_tree, index);
135         if (!tree_slot)
136                 goto out;
137         do {
138                 old_slot_val = ACCESS_ONCE(*tree_slot);
139                 slot_val = old_slot_val;
140                 page = pm_slot_get_page(slot_val);
141                 if (!page)
142                         goto out;
143                 slot_val = pm_slot_clear_removal(slot_val);
144                 slot_val = pm_slot_inc_refcnt(slot_val);        /* not a page kref */
145         } while (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val));
146         assert(page->pg_tree_slot == tree_slot);
147 out:
148         rcu_read_unlock();
149         return page;
150 }
151
152 /* Attempts to insert the page into the page_map, returns 0 for success, or an
153  * error code if there was one already (EEXIST) or we ran out of memory
154  * (ENOMEM).
155  *
156  * On success, callers *lose* their page ref, but get a PM slot ref.  This slot
157  * ref is sufficient to keep the page alive (slot ref protects the page ref)..
158  *
159  * Makes no assumptions about the quality of the data loaded, that's up to the
160  * caller. */
161 static int pm_insert_page(struct page_map *pm, unsigned long index,
162                           struct page *page)
163 {
164         int ret;
165         void **tree_slot;
166         void *slot_val = 0;
167
168         page->pg_mapping = pm;  /* debugging */
169         page->pg_index = index;
170         /* no one should be looking at the tree slot til we stop write locking.  the
171          * only other one who looks is removal, who requires a PM write lock. */
172         page->pg_tree_slot = (void*)0xdeadbeef; /* poison */
173         slot_val = pm_slot_inc_refcnt(slot_val);
174         /* passing the page ref from the caller to the slot */
175         slot_val = pm_slot_set_page(slot_val, page);
176         qlock(&pm->pm_qlock);
177         ret = radix_insert(&pm->pm_tree, index, slot_val, &tree_slot);
178         if (ret) {
179                 qunlock(&pm->pm_qlock);
180                 return ret;
181         }
182         page->pg_tree_slot = tree_slot;
183         pm->pm_num_pages++;
184         qunlock(&pm->pm_qlock);
185         return 0;
186 }
187
188 /* Decrefs the PM slot ref (usage of a PM page).  The PM's page ref remains. */
189 void pm_put_page(struct page *page)
190 {
191         void **tree_slot = page->pg_tree_slot;
192
193         assert(tree_slot);
194         assert(pm_slot_get_page(*tree_slot) == page);
195         assert(pm_slot_check_refcnt(*tree_slot) > 0);
196         /* decref, don't care about CASing */
197         atomic_add((atomic_t*)tree_slot, -(1UL << PM_REFCNT_SHIFT));
198 }
199
200 /* Makes sure the index'th page of the mapped object is loaded in the page cache
201  * and returns its location via **pp.
202  *
203  * You'll get a pm-slot refcnt back, which you need to put when you're done. */
204 int pm_load_page(struct page_map *pm, unsigned long index, struct page **pp)
205 {
206         struct page *page;
207         int error;
208
209         page = pm_find_page(pm, index);
210         while (!page) {
211                 if (kpage_alloc(&page))
212                         return -ENOMEM;
213                 /* important that UP_TO_DATE is not set.  once we put it in the PM,
214                  * others can find it, and we still need to fill it. */
215                 atomic_set(&page->pg_flags, PG_LOCKED | PG_PAGEMAP);
216                 /* The sem needs to be initted before anyone can try to lock it, meaning
217                  * before it is in the page cache.  We also want it locked preemptively,
218                  * by setting signals = 0. */
219                 sem_init(&page->pg_sem, 0);
220                 error = pm_insert_page(pm, index, page);
221                 switch (error) {
222                         case 0:
223                                 goto load_locked_page;
224                                 break;
225                         case -EEXIST:
226                                 /* the page was mapped already (benign race), just get rid of
227                                  * our page and try again (the only case that uses the while) */
228                                 atomic_set(&page->pg_flags, 0);
229                                 page_decref(page);
230                                 page = pm_find_page(pm, index);
231                                 break;
232                         default:
233                                 atomic_set(&page->pg_flags, 0);
234                                 page_decref(page);
235                                 return error;
236                 }
237         }
238         assert(page);
239         assert(pm_slot_check_refcnt(*page->pg_tree_slot));
240         assert(pm_slot_get_page(*page->pg_tree_slot) == page);
241         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
242                 *pp = page;
243                 printd("pm %p FOUND page %p, addr %p, idx %d\n", pm, page,
244                        page2kva(page), index);
245                 return 0;
246         }
247         lock_page(page);
248         /* double-check.  if we we blocked on lock_page, it was probably for someone
249          * else loading.  plus, we can't load a page more than once (it could
250          * clobber newer writes) */
251         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
252                 unlock_page(page);
253                 *pp = page;
254                 return 0;
255         }
256         /* fall through */
257 load_locked_page:
258         error = pm->pm_op->readpage(pm, page);
259         assert(!error);
260         assert(atomic_read(&page->pg_flags) & PG_UPTODATE);
261         unlock_page(page);
262         *pp = page;
263         printd("pm %p LOADS page %p, addr %p, idx %d\n", pm, page,
264                page2kva(page), index);
265         return 0;
266 }
267
268 int pm_load_page_nowait(struct page_map *pm, unsigned long index,
269                         struct page **pp)
270 {
271         struct page *page = pm_find_page(pm, index);
272         if (!page)
273                 return -EAGAIN;
274         if (!(atomic_read(&page->pg_flags) & PG_UPTODATE)) {
275                 /* TODO: could have a read_nowait pm_op */
276                 pm_put_page(page);
277                 return -EAGAIN;
278         }
279         *pp = page;
280         return 0;
281 }
282
283 static bool vmr_has_page_idx(struct vm_region *vmr, unsigned long pg_idx)
284 {
285         unsigned long nr_pgs = (vmr->vm_end - vmr->vm_base) >> PGSHIFT;
286         unsigned long start_pg = vmr->vm_foff >> PGSHIFT;
287
288         if (!vmr->vm_ready)
289                 return false;
290         return ((start_pg <= pg_idx) && (pg_idx < start_pg + nr_pgs));
291 }
292
293 static unsigned long vmr_get_end_idx(struct vm_region *vmr)
294 {
295         return ((vmr->vm_end - vmr->vm_base) + vmr->vm_foff) >> PGSHIFT;
296 }
297
298 /* Runs CB on every PTE in the VMR that corresponds to the file's pg_idx, for up
299  * to max_nr_pgs. */
300 static void vmr_for_each(struct vm_region *vmr, unsigned long pg_idx,
301                          unsigned long max_nr_pgs, mem_walk_callback_t callback)
302 {
303         uintptr_t start_va;
304         off64_t file_off = pg_idx << PGSHIFT;
305         size_t len = max_nr_pgs << PGSHIFT;
306
307         if (file_off < vmr->vm_foff) {
308                 len -= vmr->vm_foff - file_off;
309                 file_off = vmr->vm_foff;
310         }
311
312         start_va = vmr->vm_base + (file_off - vmr->vm_foff);
313         if (start_va < vmr->vm_base) {
314                 warn("wraparound! %p %p %p %p", start_va, vmr->vm_base, vmr->vm_foff,
315                      pg_idx);
316                 return;
317         }
318         if (start_va >= vmr->vm_end)
319                 return;
320
321         len = MIN(len, vmr->vm_end - start_va);
322         if (!len)
323                 return;
324         env_user_mem_walk(vmr->vm_proc, (void*)start_va, len, callback, vmr);
325 }
326
327 /* These next two helpers are called on a VMR's range of VAs corresponding to a
328  * pages in a PM undergoing removal.
329  *
330  * In general, it is safe to mark !P or 0 a PTE so long as the page the PTE
331  * points to belongs to a PM.  We'll refault, find the page, and rebuild the
332  * PTE.  This allows us to handle races like: {pm marks !p, {fault, find page,
333  * abort removal, write new pte}, pm clears pte}.
334  *
335  * In that race, HPF is writing the PTE, which removal code subsequently looks
336  * at to determine if the underlying page is dirty.  We need to make sure no one
337  * clears dirty bits unless they handle the WB (or discard).  HPF preserves the
338  * dirty bit for this reason. */
339 static int __pm_mark_not_present(struct proc *p, pte_t pte, void *va, void *arg)
340 {
341         struct page *page;
342         /* mapped includes present.  Any PTE pointing to a page (mapped) will get
343          * flagged for removal and have its access prots revoked.  We need to deal
344          * with mapped-but-maybe-not-present in case of a dirtied file that was
345          * mprotected to PROT_NONE (which is not present) */
346         if (pte_is_unmapped(pte))
347                 return 0;
348         page = pa2page(pte_get_paddr(pte));
349         if (atomic_read(&page->pg_flags) & PG_REMOVAL)
350                 pte_clear_present(pte);
351         return 0;
352 }
353
354 static int __pm_mark_dirty_pgs_unmap(struct proc *p, pte_t pte, void *va,
355                                      void *arg)
356 {
357         struct page *page;
358         /* we're not checking for 'present' or not, since we marked them !P earlier.
359          * but the CB is still called on everything in the range.  we can tell the
360          * formerly-valid PTEs from the completely unmapped, since the latter are
361          * unmapped, while the former have other things in them, but just are !P. */
362         if (pte_is_unmapped(pte))
363                 return 0;
364         page = pa2page(pte_get_paddr(pte));
365         /* need to check for removal again, just like in mark_not_present */
366         if (atomic_read(&page->pg_flags) & PG_REMOVAL) {
367                 if (pte_is_dirty(pte))
368                         atomic_or(&page->pg_flags, PG_DIRTY);
369                 pte_clear(pte);
370         }
371         return 0;
372 }
373
374 static int __pm_mark_unmap(struct proc *p, pte_t pte, void *va, void *arg)
375 {
376         struct page *page;
377         if (pte_is_unmapped(pte))
378                 return 0;
379         page = pa2page(pte_get_paddr(pte));
380         if (atomic_read(&page->pg_flags) & PG_REMOVAL)
381                 pte_clear(pte);
382         return 0;
383 }
384
385 static void shootdown_and_reset_ptrstore(void *proc_ptrs[], int *arr_idx)
386 {
387         for (int i = 0; i < *arr_idx; i++)
388                 proc_tlbshootdown((struct proc*)proc_ptrs[i], 0, 0);
389         *arr_idx = 0;
390 }
391
392 /* Attempts to remove pages from the pm, from [index, index + nr_pgs).  Returns
393  * the number of pages removed.  There can only be one remover at a time per PM
394  * - others will return 0. */
395 int pm_remove_contig(struct page_map *pm, unsigned long index,
396                      unsigned long nr_pgs)
397 {
398         unsigned long i;
399         int nr_removed = 0;
400         void **tree_slot;
401         void *old_slot_val, *slot_val;
402         struct vm_region *vmr_i;
403         bool pm_has_pinned_vmrs = FALSE;
404         /* using this for both procs and later WBs */
405         #define PTR_ARR_LEN 10
406         void *ptr_store[PTR_ARR_LEN];
407         int ptr_free_idx = 0;
408         struct page *page;
409
410         /* could also call a simpler remove if nr_pgs == 1 */
411         if (!nr_pgs)
412                 return 0;
413
414         /* This is a mess.  Qlock due to the radix_delete later.  spinlock for the
415          * VMR lists. */
416         qlock(&pm->pm_qlock);
417         spin_lock(&pm->pm_lock);
418         assert(index + nr_pgs > index); /* til we figure out who validates */
419         /* check for any pinned VMRs.  if we have none, then we can skip some loops
420          * later */
421         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
422                 if (vmr_i->vm_flags & MAP_LOCKED)
423                         pm_has_pinned_vmrs = TRUE;
424         }
425         /* this pass, we mark pages for removal */
426         for (i = index; i < index + nr_pgs; i++) {
427                 if (pm_has_pinned_vmrs) {
428                         /* for pinned pages, we don't even want to attempt to remove them */
429                         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
430                                 /* once we've found a pinned page, we can skip over the rest of
431                                  * the range of pages mapped by this vmr - even if the vmr
432                                  * hasn't actually faulted them in yet. */
433                                 if ((vmr_i->vm_flags & MAP_LOCKED) &&
434                                     (vmr_has_page_idx(vmr_i, i))) {
435                                         i = vmr_get_end_idx(vmr_i) - 1; /* loop will +1 */
436                                         goto next_loop_mark_rm;
437                                 }
438                         }
439                 }
440                 /* TODO: would like a radix_next_slot() iterator (careful with skipping
441                  * chunks of the loop) */
442                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
443                 if (!tree_slot)
444                         continue;
445                 old_slot_val = ACCESS_ONCE(*tree_slot);
446                 slot_val = old_slot_val;
447                 page = pm_slot_get_page(slot_val);
448                 if (!page)
449                         continue;
450                 /* syncing with lookups, writebacks, etc.  only one remover per pm in
451                  * general.  any new ref-getter (WB, lookup, etc) will clear removal,
452                  * causing us to abort later. */
453                 if (pm_slot_check_refcnt(slot_val))
454                         continue;
455                 /* it's possible that removal is already set, if we happened to repeat a
456                  * loop (due to running out of space in the proc arr) */
457                 slot_val = pm_slot_set_removal(slot_val);
458                 if (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val))
459                         continue;
460                 /* mark the page itself.  this isn't used for syncing - just out of
461                  * convenience for ourselves (memwalk callbacks are easier).  need the
462                  * atomic in case a new user comes in and tries mucking with the flags*/
463                 atomic_or(&page->pg_flags, PG_REMOVAL);
464 next_loop_mark_rm:
465                 ;
466         }
467         /* second pass, over VMRs instead of pages.  we remove the marked pages from
468          * all VMRs, collecting the procs for batch shootdowns.  not sure how often
469          * we'll have more than one VMR (for a PM) per proc.  shared libs tend to
470          * have a couple, so we'll still batch things up */
471         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
472                 /* might have some pinned VMRs that only map part of the file we aren't
473                  * messing with (so they didn't trigger earlier). */
474                 if (vmr_i->vm_flags & MAP_LOCKED)
475                         continue;
476                 /* Private mappings: for each page, either PMs have a separate copy
477                  * hanging off their PTE (in which case they aren't using the PM page,
478                  * and the actual page in use won't have PG_REMOVAL set, and the CB will
479                  * ignore it), or they are still using the shared version.  In which
480                  * case they haven't written it yet, and we can remove it.  If they
481                  * concurrently are performing a write fault to CoW the page, they will
482                  * incref and clear REMOVAL, thereby aborting the remove anyways.
483                  *
484                  * Though if the entire mapping is unique-copies of private pages, we
485                  * won't need a shootdown.  mem_walk can't handle this yet though. */
486                 if (!vmr_has_page_idx(vmr_i, index))
487                         continue;
488                 spin_lock(&vmr_i->vm_proc->pte_lock);
489                 /* all PTEs for pages marked for removal are marked !P for the entire
490                  * range.  it's possible we'll remove some extra PTEs (races with
491                  * loaders, etc), but those pages will remain in the PM and should get
492                  * soft-faulted back in. */
493                 vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_not_present);
494                 spin_unlock(&vmr_i->vm_proc->pte_lock);
495                 /* batching TLB shootdowns for a given proc (continue if found).
496                  * the proc stays alive while we hold a read lock on the PM tree,
497                  * since the VMR can't get yanked out yet. */
498                 for (i = 0; i < ptr_free_idx; i++) {
499                         if (ptr_store[i] == vmr_i->vm_proc)
500                                 break;
501                 }
502                 if (i != ptr_free_idx)
503                         continue;
504                 if (ptr_free_idx == PTR_ARR_LEN)
505                         shootdown_and_reset_ptrstore(ptr_store, &ptr_free_idx);
506                 ptr_store[ptr_free_idx++] = vmr_i->vm_proc;
507         }
508         /* Need to shootdown so that all TLBs have the page marked absent.  Then we
509          * can check the dirty bit, now that concurrent accesses will fault.  btw,
510          * we have a lock ordering: pm (RCU) -> proc lock (state, vcmap, etc) */
511         shootdown_and_reset_ptrstore(ptr_store, &ptr_free_idx);
512         /* Now that we've shotdown, we can check for dirtiness.  One downside to
513          * this approach is we check every VMR for a page, even once we know the
514          * page is dirty.  We also need to unmap the pages (set ptes to 0) for any
515          * that we previously marked not present (complete the unmap).  We're racing
516          * with munmap here, which treats the PTE as a weak ref on a page. */
517         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
518                 if (vmr_i->vm_flags & MAP_LOCKED)
519                         continue;
520                 if (!vmr_has_page_idx(vmr_i, index))
521                         continue;
522                 spin_lock(&vmr_i->vm_proc->pte_lock);
523                 if (vmr_i->vm_prot & PROT_WRITE)
524                         vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_dirty_pgs_unmap);
525                 else
526                         vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_unmap);
527                 spin_unlock(&vmr_i->vm_proc->pte_lock);
528         }
529         /* Now we'll go through from the PM again and deal with pages are dirty. */
530         i = index;
531 handle_dirty:
532         for (/* i set already */; i < index + nr_pgs; i++) {
533                 /* TODO: consider putting in the pinned check & advance again.  Careful,
534                  * since we could unlock on a handle_dirty loop, and skipping could skip
535                  * over a new VMR, but those pages would still be marked for removal.
536                  * It's not wrong, currently, to have spurious REMOVALs. */
537                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
538                 if (!tree_slot)
539                         continue;
540                 page = pm_slot_get_page(*tree_slot);
541                 if (!page)
542                         continue;
543                 /* only operate on pages we marked earlier */
544                 if (!(atomic_read(&page->pg_flags) & PG_REMOVAL))
545                         continue;
546                 /* if someone has used it since we grabbed it, we lost the race and
547                  * won't remove it later.  no sense writing it back now either. */
548                 if (!pm_slot_check_removal(*tree_slot)) {
549                         /* since we set PG_REMOVAL, we're the ones to clear it */
550                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
551                         continue;
552                 }
553                 /* this dirty flag could also be set by write()s, not just VMRs */
554                 if (atomic_read(&page->pg_flags) & PG_DIRTY) {
555                         /* need to bail out.  after we WB, we'll restart this big loop where
556                          * we left off ('i' is still set) */
557                         if (ptr_free_idx == PTR_ARR_LEN)
558                                 break;
559                         ptr_store[ptr_free_idx++] = page;
560                         /* once we've decided to WB, we can clear the dirty flag.  might
561                          * have an extra WB later, but we won't miss new data */
562                         atomic_and(&page->pg_flags, ~PG_DIRTY);
563                 }
564         }
565         /* we're unlocking, meaning VMRs and the radix tree can be changed, but we
566          * are still the only remover. still can have new refs that clear REMOVAL */
567         spin_unlock(&pm->pm_lock);
568         /* could batch these up, etc. */
569         for (int j = 0; j < ptr_free_idx; j++)
570                 pm->pm_op->writepage(pm, (struct page*)ptr_store[j]);
571         ptr_free_idx = 0;
572         spin_lock(&pm->pm_lock);
573         /* bailed out of the dirty check loop earlier, need to finish and WB.  i is
574          * still set to where we failed and left off in the big loop. */
575         if (i < index + nr_pgs)
576                 goto handle_dirty;
577         /* TODO: RCU - we need a write lock here (the current spinlock is fine) */
578         /* All dirty pages were WB, anything left as REMOVAL can be removed */
579         for (i = index; i < index + nr_pgs; i++) {
580                 /* TODO: consider putting in the pinned check & advance again */
581                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
582                 if (!tree_slot)
583                         continue;
584                 old_slot_val = ACCESS_ONCE(*tree_slot);
585                 slot_val = old_slot_val;
586                 page = pm_slot_get_page(*tree_slot);
587                 if (!page)
588                         continue;
589                 if (!(atomic_read(&page->pg_flags) & PG_REMOVAL))
590                         continue;
591                 /* syncing with lookups, writebacks, etc.  if someone has used it since
592                  * we started removing, they would have cleared the slot's REMOVAL (but
593                  * not PG_REMOVAL), though the refcnt could be back down to 0 again. */
594                 if (!pm_slot_check_removal(slot_val)) {
595                         /* since we set PG_REMOVAL, we're the ones to clear it */
596                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
597                         continue;
598                 }
599                 if (pm_slot_check_refcnt(slot_val))
600                         warn("Unexpected refcnt in PM remove!");
601                 /* Note that we keep slot REMOVAL set, so the radix tree thinks it's
602                  * still an item (artifact of that implementation). */
603                 slot_val = pm_slot_set_page(slot_val, 0);
604                 if (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val)) {
605                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
606                         continue;
607                 }
608                 /* at this point, we're free at last!  When we update the radix tree, it
609                  * still thinks it has an item.  This is fine.  Lookups will now fail
610                  * (since the page is 0), and insertions will block on the write lock.*/
611                 atomic_set(&page->pg_flags, 0); /* cause/catch bugs */
612                 page_decref(page);
613                 nr_removed++;
614                 radix_delete(&pm->pm_tree, i);
615         }
616         pm->pm_num_pages -= nr_removed;
617         spin_unlock(&pm->pm_lock);
618         qunlock(&pm->pm_qlock);
619         return nr_removed;
620 }
621
622 static bool pm_has_vmr_with_page(struct page_map *pm, unsigned long pg_idx)
623 {
624         struct vm_region *vmr_i;
625
626         spin_lock(&pm->pm_lock);
627         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
628                 if (vmr_has_page_idx(vmr_i, pg_idx)) {
629                         spin_unlock(&pm->pm_lock);
630                         return true;
631                 }
632         }
633         spin_unlock(&pm->pm_lock);
634         return false;
635 }
636
637 static bool __remove_or_zero_cb(void **slot, unsigned long tree_idx, void *arg)
638 {
639         struct page_map *pm = arg;
640         struct page *page;
641         void *old_slot_val, *slot_val;
642
643         old_slot_val = ACCESS_ONCE(*slot);
644         slot_val = old_slot_val;
645         page = pm_slot_get_page(slot_val);
646         /* We shouldn't have an item in the tree without a page, unless there's
647          * another removal.  Currently, this CB is called with a qlock. */
648         assert(page);
649         /* Don't even bother with VMRs that might have faulted in the page */
650         if (pm_has_vmr_with_page(pm, tree_idx)) {
651                 memset(page2kva(page), 0, PGSIZE);
652                 return false;
653         }
654         /* syncing with lookups, writebacks, etc - anyone who gets a ref on a PM
655          * leaf/page (e.g. pm_load_page / pm_find_page. */
656         slot_val = pm_slot_set_page(slot_val, NULL);
657         if (pm_slot_check_refcnt(slot_val) ||
658                 !atomic_cas_ptr(slot, old_slot_val, slot_val)) {
659                 memset(page2kva(page), 0, PGSIZE);
660                 return false;
661         }
662         /* We yanked the page out.  The radix tree still has an item until we return
663          * true, but this is fine.  Future lock-free lookups will now fail (since
664          * the page is 0), and insertions will block on the write lock. */
665         atomic_set(&page->pg_flags, 0); /* cause/catch bugs */
666         page_decref(page);
667         return true;
668 }
669
670 void pm_remove_or_zero_pages(struct page_map *pm, unsigned long start_idx,
671                              unsigned long nr_pgs)
672 {
673         unsigned long end_idx = start_idx + nr_pgs;
674
675         assert(end_idx > start_idx);
676         qlock(&pm->pm_qlock);
677         radix_for_each_slot_in_range(&pm->pm_tree, start_idx, end_idx,
678                                      __remove_or_zero_cb, pm);
679         qunlock(&pm->pm_qlock);
680 }
681
682 static int __pm_mark_and_clear_dirty(struct proc *p, pte_t pte, void *va,
683                                      void *arg)
684 {
685         struct page *page = pa2page(pte_get_paddr(pte));
686         struct vm_region *vmr = arg;
687
688         if (!pte_is_present(pte) || !pte_is_dirty(pte))
689                 return 0;
690         if (!(atomic_read(&page->pg_flags) & PG_DIRTY))
691                 atomic_or(&page->pg_flags, PG_DIRTY);
692         pte_clear_dirty(pte);
693         vmr->vm_shootdown_needed = true;
694         return 0;
695 }
696
697 /* Dirty PTE bits will get marked to the struct page itself, and the PTEs will
698  * have the dirty bit cleared.  VMRs that need a shootdown are marked.  Note
699  * this only marks PTEs and VMRs if they were the one to do some of the
700  * dirtying. */
701 static void mark_and_clear_dirty_ptes(struct page_map *pm)
702 {
703         struct vm_region *vmr_i;
704         pte_t pte;
705
706         spin_lock(&pm->pm_lock);
707         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
708                 if (!(vmr_i->vm_prot & PROT_WRITE))
709                         continue;
710                 /* Only care about shared mappings, not private.  Private mappings have
711                  * a reference to the file, but the pages are not in the page cache -
712                  * they hang directly off the PTEs (for now). */
713                 if (!(vmr_i->vm_flags & MAP_SHARED))
714                         continue;
715                 spin_lock(&vmr_i->vm_proc->pte_lock);
716                 vmr_for_each(vmr_i, 0, ULONG_MAX, __pm_mark_and_clear_dirty);
717                 spin_unlock(&vmr_i->vm_proc->pte_lock);
718         }
719         spin_unlock(&pm->pm_lock);
720 }
721
722 static void shootdown_vmrs(struct page_map *pm)
723 {
724         struct vm_region *vmr_i;
725
726         /* The VMR flag shootdown_needed is owned by the PM.  Each VMR is hooked to
727          * at most one file, so there's no issue there.  We might have a proc that
728          * has multiple non-private VMRs in the same file, but it shouldn't be a big
729          * enough issue to worry about. */
730         spin_lock(&pm->pm_lock);
731         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
732                 if (vmr_i->vm_shootdown_needed) {
733                         vmr_i->vm_shootdown_needed = false;
734                         proc_tlbshootdown(vmr_i->vm_proc, 0, 0);
735                 }
736         }
737         spin_unlock(&pm->pm_lock);
738 }
739
740 /* Send any queued WBs that haven't been sent yet. */
741 static void flush_queued_writebacks(struct page_map *pm)
742 {
743         /* TODO (WB) */
744 }
745
746 /* Batches up pages to be written back, preferably as one big op.  If we have a
747  * bunch outstanding, we'll send them. */
748 static void queue_writeback(struct page_map *pm, struct page *page)
749 {
750         /* TODO (WB): add a bulk op (instead of only writepage()), collect extents,
751          * and send them to the device.  Probably do something similar for reads. */
752         pm->pm_op->writepage(pm, page);
753 }
754
755 static bool __writeback_cb(void **slot, unsigned long tree_idx, void *arg)
756 {
757         struct page_map *pm = arg;
758         struct page *page = pm_slot_get_page(*slot);
759
760         /* We're qlocked, so all items should have pages. */
761         assert(page);
762         if (atomic_read(&page->pg_flags) & PG_DIRTY) {
763                 atomic_and(&page->pg_flags, ~PG_DIRTY);
764                 queue_writeback(pm, page);
765         }
766         return false;
767 }
768
769 /* Every dirty page gets written back, regardless of whether it's in a VMR or
770  * not.  All the dirty bits get cleared too, before writing back. */
771 void pm_writeback_pages(struct page_map *pm)
772 {
773         qlock(&pm->pm_qlock);
774         mark_and_clear_dirty_ptes(pm);
775         shootdown_vmrs(pm);
776         radix_for_each_slot(&pm->pm_tree, __writeback_cb, pm);
777         flush_queued_writebacks(pm);
778         qunlock(&pm->pm_qlock);
779 }
780
781 static bool __destroy_cb(void **slot, unsigned long tree_idx, void *arg)
782 {
783         struct page *page = pm_slot_get_page(*slot);
784
785         /* Should be no users or need to sync */
786         assert(pm_slot_check_refcnt(*slot) == 0);
787         atomic_set(&page->pg_flags, 0); /* catch bugs */
788         page_decref(page);
789         return true;
790 }
791
792 void pm_destroy(struct page_map *pm)
793 {
794         radix_for_each_slot(&pm->pm_tree, __destroy_cb, pm);
795         radix_tree_destroy(&pm->pm_tree);
796 }
797
798 void print_page_map_info(struct page_map *pm)
799 {
800         struct vm_region *vmr_i;
801         printk("Page Map %p\n", pm);
802         printk("\tNum pages: %lu\n", pm->pm_num_pages);
803         spin_lock(&pm->pm_lock);
804         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
805                 printk("\tVMR proc %d: (%p - %p): 0x%08x, 0x%08x, %p, %p\n",
806                        vmr_i->vm_proc->pid, vmr_i->vm_base, vmr_i->vm_end,
807                        vmr_i->vm_prot, vmr_i->vm_flags, foc_pointer(vmr_i->__vm_foc),
808                            vmr_i->vm_foff);
809         }
810         spin_unlock(&pm->pm_lock);
811 }
812
813 void pm_page_asserter(struct page *page, char *str)
814 {
815         void **tree_slot = page->pg_tree_slot;
816
817         if (!page_is_pagemap(page))
818                 return;
819         assert(tree_slot);
820         assert(pm_slot_get_page(*tree_slot) == page);
821         assert(pm_slot_check_refcnt(*tree_slot) > 0);
822 }