pm: Implement pm_destroy()
[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
16 void pm_add_vmr(struct page_map *pm, struct vm_region *vmr)
17 {
18         /* note that the VMR being reverse-mapped by the PM is protected by the PM's
19          * lock.  we clearly need a write lock here, but removal also needs a write
20          * lock, so later when removal holds this, it delays munmaps and keeps the
21          * VMR connected. */
22         spin_lock(&pm->pm_lock);
23         TAILQ_INSERT_TAIL(&pm->pm_vmrs, vmr, vm_pm_link);
24         spin_unlock(&pm->pm_lock);
25 }
26
27 void pm_remove_vmr(struct page_map *pm, struct vm_region *vmr)
28 {
29         spin_lock(&pm->pm_lock);
30         TAILQ_REMOVE(&pm->pm_vmrs, vmr, vm_pm_link);
31         spin_unlock(&pm->pm_lock);
32 }
33
34 /* PM slot void *s look like this:
35  *
36  * |--11--|--1--|----52 or 20 bits--|
37  * | ref  | flag|    ppn of page    |
38  *              \  <--- meta shift -/
39  *
40  * The setter funcs return the void* that should update slot_val; it doesn't
41  * change slot_val in place (it's a val, not the addr) */
42
43 #ifdef CONFIG_64BIT
44 # define PM_FLAGS_SHIFT 52
45 #else
46 # define PM_FLAGS_SHIFT 20
47 #endif
48 #define PM_REFCNT_SHIFT (PM_FLAGS_SHIFT + 1)
49
50 #define PM_REMOVAL (1UL << PM_FLAGS_SHIFT)
51
52 static bool pm_slot_check_removal(void *slot_val)
53 {
54         return (unsigned long)slot_val & PM_REMOVAL ? TRUE : FALSE;
55 }
56
57 static void *pm_slot_set_removal(void *slot_val)
58 {
59         return (void*)((unsigned long)slot_val | PM_REMOVAL);
60 }
61
62 static void *pm_slot_clear_removal(void *slot_val)
63 {
64         return (void*)((unsigned long)slot_val & ~PM_REMOVAL);
65 }
66
67 static int pm_slot_check_refcnt(void *slot_val)
68 {
69         return (unsigned long)slot_val >> PM_REFCNT_SHIFT;
70 }
71
72 static void *pm_slot_inc_refcnt(void *slot_val)
73 {
74         void *ret;
75
76         ret = (void*)((unsigned long)slot_val + (1UL << PM_REFCNT_SHIFT));
77         /* Catches previously negative refcnts */
78         assert(pm_slot_check_refcnt(ret) > 0);
79         return ret;
80 }
81
82 static void *pm_slot_dec_refcnt(void *slot_val)
83 {
84         assert(pm_slot_check_refcnt(slot_val) > 0);
85         return (void*)((unsigned long)slot_val - (1UL << PM_REFCNT_SHIFT));
86 }
87
88 static struct page *pm_slot_get_page(void *slot_val)
89 {
90         if (!slot_val)
91                 return 0;
92         return ppn2page((unsigned long)slot_val & ((1UL << PM_FLAGS_SHIFT) - 1));
93 }
94
95 static void *pm_slot_set_page(void *slot_val, struct page *pg)
96 {
97         assert(pg != pages);    /* we should never alloc page 0, for sanity */
98         return (void*)(page2ppn(pg) | ((unsigned long)slot_val &
99                                        ~((1UL << PM_FLAGS_SHIFT) - 1)));
100 }
101
102 /* Initializes a PM.  Host should be an fs_file.  The reference this stores is
103  * uncounted. */
104 void pm_init(struct page_map *pm, struct page_map_operations *op, void *host)
105 {
106         pm->pm_file = host;
107         radix_tree_init(&pm->pm_tree);
108         pm->pm_num_pages = 0;                                   /* no pages in a new pm */
109         pm->pm_op = op;
110         spinlock_init(&pm->pm_lock);
111         TAILQ_INIT(&pm->pm_vmrs);
112         atomic_set(&pm->pm_removal, 0);
113 }
114
115 /* Looks up the index'th page in the page map, returning a refcnt'd reference
116  * that need to be dropped with pm_put_page, or 0 if it was not in the map. */
117 static struct page *pm_find_page(struct page_map *pm, unsigned long index)
118 {
119         void **tree_slot;
120         void *old_slot_val, *slot_val;
121         struct page *page = 0;
122         /* Read walking the PM tree TODO: (RCU) */
123         spin_lock(&pm->pm_lock);
124         /* We're syncing with removal.  The deal is that if we grab the page (and
125          * we'd only do that if the page != 0), we up the slot ref and clear
126          * removal.  A remover will only remove it if removal is still set.  If we
127          * grab and release while removal is in progress, even though we no longer
128          * hold the ref, we have unset removal.  Also, to prevent removal where we
129          * get a page well before the removal process, the removal won't even bother
130          * when the slot refcnt is upped. */
131         tree_slot = radix_lookup_slot(&pm->pm_tree, index);
132         if (!tree_slot)
133                 goto out;
134         do {
135                 old_slot_val = ACCESS_ONCE(*tree_slot);
136                 slot_val = old_slot_val;
137                 page = pm_slot_get_page(slot_val);
138                 if (!page)
139                         goto out;
140                 slot_val = pm_slot_clear_removal(slot_val);
141                 slot_val = pm_slot_inc_refcnt(slot_val);        /* not a page kref */
142         } while (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val));
143         assert(page->pg_tree_slot == tree_slot);
144 out:
145         spin_unlock(&pm->pm_lock);
146         return page;
147 }
148
149 /* Attempts to insert the page into the page_map, returns 0 for success, or an
150  * error code if there was one already (EEXIST) or we ran out of memory
151  * (ENOMEM).
152  *
153  * On success, callers *lose* their page ref, but get a PM slot ref.  This slot
154  * ref is sufficient to keep the page alive (slot ref protects the page ref)..
155  *
156  * Makes no assumptions about the quality of the data loaded, that's up to the
157  * caller. */
158 static int pm_insert_page(struct page_map *pm, unsigned long index,
159                           struct page *page)
160 {
161         int ret;
162         void **tree_slot;
163         void *slot_val = 0;
164         /* write locking the PM */
165         spin_lock(&pm->pm_lock);
166         page->pg_mapping = pm;  /* debugging */
167         page->pg_index = index;
168         /* no one should be looking at the tree slot til we stop write locking.  the
169          * only other one who looks is removal, who requires a PM write lock. */
170         page->pg_tree_slot = (void*)0xdeadbeef; /* poison */
171         slot_val = pm_slot_inc_refcnt(slot_val);
172         /* passing the page ref from the caller to the slot */
173         slot_val = pm_slot_set_page(slot_val, page);
174         /* shouldn't need a CAS or anything for the slot write, since we hold the
175          * write lock.  o/w, we'd need to get the slot and CAS instead of insert. */
176         ret = radix_insert(&pm->pm_tree, index, slot_val, &tree_slot);
177         if (ret) {
178                 spin_unlock(&pm->pm_lock);
179                 return ret;
180         }
181         page->pg_tree_slot = tree_slot;
182         pm->pm_num_pages++;
183         spin_unlock(&pm->pm_lock);
184         return 0;
185 }
186
187 /* Decrefs the PM slot ref (usage of a PM page).  The PM's page ref remains. */
188 void pm_put_page(struct page *page)
189 {
190         void **tree_slot = page->pg_tree_slot;
191
192         assert(tree_slot);
193         assert(pm_slot_get_page(*tree_slot) == page);
194         assert(pm_slot_check_refcnt(*tree_slot) > 0);
195         /* decref, don't care about CASing */
196         atomic_add((atomic_t*)tree_slot, -(1UL << PM_REFCNT_SHIFT));
197 }
198
199 /* Makes sure the index'th page of the mapped object is loaded in the page cache
200  * and returns its location via **pp.
201  *
202  * You'll get a pm-slot refcnt back, which you need to put when you're done. */
203 int pm_load_page(struct page_map *pm, unsigned long index, struct page **pp)
204 {
205         struct page *page;
206         int error;
207
208         page = pm_find_page(pm, index);
209         while (!page) {
210                 if (kpage_alloc(&page))
211                         return -ENOMEM;
212                 /* important that UP_TO_DATE is not set.  once we put it in the PM,
213                  * others can find it, and we still need to fill it. */
214                 atomic_set(&page->pg_flags, PG_LOCKED | PG_PAGEMAP);
215                 /* The sem needs to be initted before anyone can try to lock it, meaning
216                  * before it is in the page cache.  We also want it locked preemptively,
217                  * by setting signals = 0. */
218                 sem_init(&page->pg_sem, 0);
219                 error = pm_insert_page(pm, index, page);
220                 switch (error) {
221                         case 0:
222                                 goto load_locked_page;
223                                 break;
224                         case -EEXIST:
225                                 /* the page was mapped already (benign race), just get rid of
226                                  * our page and try again (the only case that uses the while) */
227                                 atomic_set(&page->pg_flags, 0);
228                                 page_decref(page);
229                                 page = pm_find_page(pm, index);
230                                 break;
231                         default:
232                                 atomic_set(&page->pg_flags, 0);
233                                 page_decref(page);
234                                 return error;
235                 }
236         }
237         assert(page);
238         assert(pm_slot_check_refcnt(*page->pg_tree_slot));
239         assert(pm_slot_get_page(*page->pg_tree_slot) == page);
240         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
241                 *pp = page;
242                 printd("pm %p FOUND page %p, addr %p, idx %d\n", pm, page,
243                        page2kva(page), index);
244                 return 0;
245         }
246         lock_page(page);
247         /* double-check.  if we we blocked on lock_page, it was probably for someone
248          * else loading.  plus, we can't load a page more than once (it could
249          * clobber newer writes) */
250         if (atomic_read(&page->pg_flags) & PG_UPTODATE) {
251                 unlock_page(page);
252                 *pp = page;
253                 return 0;
254         }
255         /* fall through */
256 load_locked_page:
257         error = pm->pm_op->readpage(pm, page);
258         assert(!error);
259         assert(atomic_read(&page->pg_flags) & PG_UPTODATE);
260         unlock_page(page);
261         *pp = page;
262         printd("pm %p LOADS page %p, addr %p, idx %d\n", pm, page,
263                page2kva(page), index);
264         return 0;
265 }
266
267 int pm_load_page_nowait(struct page_map *pm, unsigned long index,
268                         struct page **pp)
269 {
270         struct page *page = pm_find_page(pm, index);
271         if (!page)
272                 return -EAGAIN;
273         if (!(atomic_read(&page->pg_flags) & PG_UPTODATE)) {
274                 /* TODO: could have a read_nowait pm_op */
275                 pm_put_page(page);
276                 return -EAGAIN;
277         }
278         *pp = page;
279         return 0;
280 }
281
282 static bool vmr_has_page_idx(struct vm_region *vmr, unsigned long pg_idx)
283 {
284         unsigned long nr_pgs = (vmr->vm_end - vmr->vm_base) >> PGSHIFT;
285         unsigned long start_pg = vmr->vm_foff >> PGSHIFT;
286
287         if (!vmr->vm_ready)
288                 return false;
289         return ((start_pg <= pg_idx) && (pg_idx < start_pg + nr_pgs));
290 }
291
292 static void *vmr_idx_to_va(struct vm_region *vmr, unsigned long pg_idx)
293 {
294         uintptr_t va = vmr->vm_base + ((pg_idx << PGSHIFT) - vmr->vm_foff);
295         assert(va < vmr->vm_end);
296         return (void*)va;
297 }
298
299 static unsigned long vmr_get_end_idx(struct vm_region *vmr)
300 {
301         return ((vmr->vm_end - vmr->vm_base) + vmr->vm_foff) >> PGSHIFT;
302 }
303
304 static void vmr_for_each(struct vm_region *vmr, unsigned long pg_idx,
305                          unsigned long max_nr_pgs, mem_walk_callback_t callback)
306 {
307         void *start_va = vmr_idx_to_va(vmr, pg_idx);
308         size_t len = vmr->vm_end - (uintptr_t)start_va;
309         len = MIN(len, max_nr_pgs << PGSHIFT);
310         /* TODO: start using pml_for_each, across all arches */
311         env_user_mem_walk(vmr->vm_proc, start_va, len, callback, 0);
312 }
313
314 /* These next two helpers are called on a VMR's range of VAs corresponding to a
315  * pages in a PM undergoing removal.
316  *
317  * In general, it is safe to mark !P or 0 a PTE so long as the page the PTE
318  * points to belongs to a PM.  We'll refault, find the page, and rebuild the
319  * PTE.  This allows us to handle races like: {pm marks !p, {fault, find page,
320  * abort removal, write new pte}, pm clears pte}.
321  *
322  * In that race, HPF is writing the PTE, which removal code subsequently looks
323  * at to determine if the underlying page is dirty.  We need to make sure no one
324  * clears dirty bits unless they handle the WB (or discard).  HPF preserves the
325  * dirty bit for this reason. */
326 static int __pm_mark_not_present(struct proc *p, pte_t pte, void *va, void *arg)
327 {
328         struct page *page;
329         /* mapped includes present.  Any PTE pointing to a page (mapped) will get
330          * flagged for removal and have its access prots revoked.  We need to deal
331          * with mapped-but-maybe-not-present in case of a dirtied file that was
332          * mprotected to PROT_NONE (which is not present) */
333         if (pte_is_unmapped(pte))
334                 return 0;
335         page = pa2page(pte_get_paddr(pte));
336         if (atomic_read(&page->pg_flags) & PG_REMOVAL)
337                 pte_clear_present(pte);
338         return 0;
339 }
340
341 static int __pm_mark_dirty_pgs_unmap(struct proc *p, pte_t pte, void *va,
342                                      void *arg)
343 {
344         struct page *page;
345         /* we're not checking for 'present' or not, since we marked them !P earlier.
346          * but the CB is still called on everything in the range.  we can tell the
347          * formerly-valid PTEs from the completely unmapped, since the latter are
348          * unmapped, while the former have other things in them, but just are !P. */
349         if (pte_is_unmapped(pte))
350                 return 0;
351         page = pa2page(pte_get_paddr(pte));
352         /* need to check for removal again, just like in mark_not_present */
353         if (atomic_read(&page->pg_flags) & PG_REMOVAL) {
354                 if (pte_is_dirty(pte))
355                         atomic_or(&page->pg_flags, PG_DIRTY);
356                 pte_clear(pte);
357         }
358         return 0;
359 }
360
361 static int __pm_mark_unmap(struct proc *p, pte_t pte, void *va, void *arg)
362 {
363         struct page *page;
364         if (pte_is_unmapped(pte))
365                 return 0;
366         page = pa2page(pte_get_paddr(pte));
367         if (atomic_read(&page->pg_flags) & PG_REMOVAL)
368                 pte_clear(pte);
369         return 0;
370 }
371
372 static void shootdown_and_reset_ptrstore(void *proc_ptrs[], int *arr_idx)
373 {
374         for (int i = 0; i < *arr_idx; i++)
375                 proc_tlbshootdown((struct proc*)proc_ptrs[i], 0, 0);
376         *arr_idx = 0;
377 }
378
379 /* Attempts to remove pages from the pm, from [index, index + nr_pgs).  Returns
380  * the number of pages removed.  There can only be one remover at a time per PM
381  * - others will return 0. */
382 int pm_remove_contig(struct page_map *pm, unsigned long index,
383                      unsigned long nr_pgs)
384 {
385         unsigned long i;
386         int nr_removed = 0;
387         void **tree_slot;
388         void *old_slot_val, *slot_val;
389         struct vm_region *vmr_i;
390         bool pm_has_pinned_vmrs = FALSE;
391         /* using this for both procs and later WBs */
392         #define PTR_ARR_LEN 10
393         void *ptr_store[PTR_ARR_LEN];
394         int ptr_free_idx = 0;
395         struct page *page;
396         /* could also call a simpler remove if nr_pgs == 1 */
397         if (!nr_pgs)
398                 return 0;
399         /* only one remover at a time (since we walk the PM multiple times as our
400          * 'working list', and need the REMOVAL flag to tell us which pages we're
401          * working on.  with more than one remover, we'd be confused and would need
402          * another list.) */
403         if (atomic_swap(&pm->pm_removal, 1)) {
404                 /* We got a 1 back, so someone else is already removing */
405                 return 0;
406         }
407         /* TODO: RCU: we're read walking the PM tree and write walking the VMR list.
408          * the reason for the write lock is since we need to prevent new VMRs or the
409          * changing of a VMR to being pinned. o/w, we could fail to unmap and check
410          * for dirtiness. */
411         spin_lock(&pm->pm_lock);
412         assert(index + nr_pgs > index); /* til we figure out who validates */
413         /* check for any pinned VMRs.  if we have none, then we can skip some loops
414          * later */
415         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
416                 if (vmr_i->vm_flags & MAP_LOCKED)
417                         pm_has_pinned_vmrs = TRUE;
418         }
419         /* this pass, we mark pages for removal */
420         for (i = index; i < index + nr_pgs; i++) {
421                 if (pm_has_pinned_vmrs) {
422                         /* for pinned pages, we don't even want to attempt to remove them */
423                         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
424                                 /* once we've found a pinned page, we can skip over the rest of
425                                  * the range of pages mapped by this vmr - even if the vmr
426                                  * hasn't actually faulted them in yet. */
427                                 if ((vmr_i->vm_flags & MAP_LOCKED) &&
428                                     (vmr_has_page_idx(vmr_i, i))) {
429                                         i = vmr_get_end_idx(vmr_i) - 1; /* loop will +1 */
430                                         goto next_loop_mark_rm;
431                                 }
432                         }
433                 }
434                 /* TODO: would like a radix_next_slot() iterator (careful with skipping
435                  * chunks of the loop) */
436                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
437                 if (!tree_slot)
438                         continue;
439                 old_slot_val = ACCESS_ONCE(*tree_slot);
440                 slot_val = old_slot_val;
441                 page = pm_slot_get_page(slot_val);
442                 if (!page)
443                         continue;
444                 /* syncing with lookups, writebacks, etc.  only one remover per pm in
445                  * general.  any new ref-getter (WB, lookup, etc) will clear removal,
446                  * causing us to abort later. */
447                 if (pm_slot_check_refcnt(slot_val))
448                         continue;
449                 /* it's possible that removal is already set, if we happened to repeat a
450                  * loop (due to running out of space in the proc arr) */
451                 slot_val = pm_slot_set_removal(slot_val);
452                 if (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val))
453                         continue;
454                 /* mark the page itself.  this isn't used for syncing - just out of
455                  * convenience for ourselves (memwalk callbacks are easier).  need the
456                  * atomic in case a new user comes in and tries mucking with the flags*/
457                 atomic_or(&page->pg_flags, PG_REMOVAL);
458 next_loop_mark_rm:
459                 ;
460         }
461         /* second pass, over VMRs instead of pages.  we remove the marked pages from
462          * all VMRs, collecting the procs for batch shootdowns.  not sure how often
463          * we'll have more than one VMR (for a PM) per proc.  shared libs tend to
464          * have a couple, so we'll still batch things up */
465         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
466                 /* might have some pinned VMRs that only map part of the file we aren't
467                  * messing with (so they didn't trigger earlier). */
468                 if (vmr_i->vm_flags & MAP_LOCKED)
469                         continue;
470                 /* Private mappings: for each page, either PMs have a separate copy
471                  * hanging off their PTE (in which case they aren't using the PM page,
472                  * and the actual page in use won't have PG_REMOVAL set, and the CB will
473                  * ignore it), or they are still using the shared version.  In which
474                  * case they haven't written it yet, and we can remove it.  If they
475                  * concurrently are performing a write fault to CoW the page, they will
476                  * incref and clear REMOVAL, thereby aborting the remove anyways.
477                  *
478                  * Though if the entire mapping is unique-copies of private pages, we
479                  * won't need a shootdown.  mem_walk can't handle this yet though. */
480                 if (!vmr_has_page_idx(vmr_i, index))
481                         continue;
482                 spin_lock(&vmr_i->vm_proc->pte_lock);
483                 /* all PTEs for pages marked for removal are marked !P for the entire
484                  * range.  it's possible we'll remove some extra PTEs (races with
485                  * loaders, etc), but those pages will remain in the PM and should get
486                  * soft-faulted back in. */
487                 vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_not_present);
488                 spin_unlock(&vmr_i->vm_proc->pte_lock);
489                 /* batching TLB shootdowns for a given proc (continue if found).
490                  * the proc stays alive while we hold a read lock on the PM tree,
491                  * since the VMR can't get yanked out yet. */
492                 for (i = 0; i < ptr_free_idx; i++) {
493                         if (ptr_store[i] == vmr_i->vm_proc)
494                                 break;
495                 }
496                 if (i != ptr_free_idx)
497                         continue;
498                 if (ptr_free_idx == PTR_ARR_LEN)
499                         shootdown_and_reset_ptrstore(ptr_store, &ptr_free_idx);
500                 ptr_store[ptr_free_idx++] = vmr_i->vm_proc;
501         }
502         /* Need to shootdown so that all TLBs have the page marked absent.  Then we
503          * can check the dirty bit, now that concurrent accesses will fault.  btw,
504          * we have a lock ordering: pm (RCU) -> proc lock (state, vcmap, etc) */
505         shootdown_and_reset_ptrstore(ptr_store, &ptr_free_idx);
506         /* Now that we've shotdown, we can check for dirtiness.  One downside to
507          * this approach is we check every VMR for a page, even once we know the
508          * page is dirty.  We also need to unmap the pages (set ptes to 0) for any
509          * that we previously marked not present (complete the unmap).  We're racing
510          * with munmap here, which treats the PTE as a weak ref on a page. */
511         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
512                 if (vmr_i->vm_flags & MAP_LOCKED)
513                         continue;
514                 if (!vmr_has_page_idx(vmr_i, index))
515                         continue;
516                 spin_lock(&vmr_i->vm_proc->pte_lock);
517                 if (vmr_i->vm_prot & PROT_WRITE)
518                         vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_dirty_pgs_unmap);
519                 else
520                         vmr_for_each(vmr_i, index, nr_pgs, __pm_mark_unmap);
521                 spin_unlock(&vmr_i->vm_proc->pte_lock);
522         }
523         /* Now we'll go through from the PM again and deal with pages are dirty. */
524         i = index;
525 handle_dirty:
526         for (/* i set already */; i < index + nr_pgs; i++) {
527                 /* TODO: consider putting in the pinned check & advance again.  Careful,
528                  * since we could unlock on a handle_dirty loop, and skipping could skip
529                  * over a new VMR, but those pages would still be marked for removal.
530                  * It's not wrong, currently, to have spurious REMOVALs. */
531                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
532                 if (!tree_slot)
533                         continue;
534                 page = pm_slot_get_page(*tree_slot);
535                 if (!page)
536                         continue;
537                 /* only operate on pages we marked earlier */
538                 if (!(atomic_read(&page->pg_flags) & PG_REMOVAL))
539                         continue;
540                 /* if someone has used it since we grabbed it, we lost the race and
541                  * won't remove it later.  no sense writing it back now either. */
542                 if (!pm_slot_check_removal(*tree_slot)) {
543                         /* since we set PG_REMOVAL, we're the ones to clear it */
544                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
545                         continue;
546                 }
547                 /* this dirty flag could also be set by write()s, not just VMRs */
548                 if (atomic_read(&page->pg_flags) & PG_DIRTY) {
549                         /* need to bail out.  after we WB, we'll restart this big loop where
550                          * we left off ('i' is still set) */
551                         if (ptr_free_idx == PTR_ARR_LEN)
552                                 break;
553                         ptr_store[ptr_free_idx++] = page;
554                         /* once we've decided to WB, we can clear the dirty flag.  might
555                          * have an extra WB later, but we won't miss new data */
556                         atomic_and(&page->pg_flags, ~PG_DIRTY);
557                 }
558         }
559         /* we're unlocking, meaning VMRs and the radix tree can be changed, but we
560          * are still the only remover. still can have new refs that clear REMOVAL */
561         spin_unlock(&pm->pm_lock);
562         /* could batch these up, etc. */
563         for (int j = 0; j < ptr_free_idx; j++)
564                 pm->pm_op->writepage(pm, (struct page*)ptr_store[j]);
565         ptr_free_idx = 0;
566         spin_lock(&pm->pm_lock);
567         /* bailed out of the dirty check loop earlier, need to finish and WB.  i is
568          * still set to where we failed and left off in the big loop. */
569         if (i < index + nr_pgs)
570                 goto handle_dirty;
571         /* TODO: RCU - we need a write lock here (the current spinlock is fine) */
572         /* All dirty pages were WB, anything left as REMOVAL can be removed */
573         for (i = index; i < index + nr_pgs; i++) {
574                 /* TODO: consider putting in the pinned check & advance again */
575                 tree_slot = radix_lookup_slot(&pm->pm_tree, i);
576                 if (!tree_slot)
577                         continue;
578                 old_slot_val = ACCESS_ONCE(*tree_slot);
579                 slot_val = old_slot_val;
580                 page = pm_slot_get_page(*tree_slot);
581                 if (!page)
582                         continue;
583                 if (!(atomic_read(&page->pg_flags) & PG_REMOVAL))
584                         continue;
585                 /* syncing with lookups, writebacks, etc.  if someone has used it since
586                  * we started removing, they would have cleared the slot's REMOVAL (but
587                  * not PG_REMOVAL), though the refcnt could be back down to 0 again. */
588                 if (!pm_slot_check_removal(slot_val)) {
589                         /* since we set PG_REMOVAL, we're the ones to clear it */
590                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
591                         continue;
592                 }
593                 if (pm_slot_check_refcnt(slot_val))
594                         warn("Unexpected refcnt in PM remove!");
595                 /* Note that we keep slot REMOVAL set, so the radix tree thinks it's
596                  * still an item (artifact of that implementation). */
597                 slot_val = pm_slot_set_page(slot_val, 0);
598                 if (!atomic_cas_ptr(tree_slot, old_slot_val, slot_val)) {
599                         atomic_and(&page->pg_flags, ~PG_REMOVAL);
600                         continue;
601                 }
602                 /* at this point, we're free at last!  When we update the radix tree, it
603                  * still thinks it has an item.  This is fine.  Lookups will now fail
604                  * (since the page is 0), and insertions will block on the write lock.*/
605                 atomic_set(&page->pg_flags, 0); /* cause/catch bugs */
606                 page_decref(page);
607                 nr_removed++;
608                 radix_delete(&pm->pm_tree, i);
609         }
610         pm->pm_num_pages -= nr_removed;
611         spin_unlock(&pm->pm_lock);
612         atomic_set(&pm->pm_removal, 0);
613         return nr_removed;
614 }
615
616 static bool __destroy_cb(void **slot, unsigned long tree_idx, void *arg)
617 {
618         struct page *page = pm_slot_get_page(*slot);
619
620         /* Should be no users or need to sync */
621         assert(pm_slot_check_refcnt(*slot) == 0);
622         atomic_set(&page->pg_flags, 0); /* catch bugs */
623         page_decref(page);
624         return true;
625 }
626
627 void pm_destroy(struct page_map *pm)
628 {
629         radix_for_each_slot(&pm->pm_tree, __destroy_cb, pm);
630         radix_tree_destroy(&pm->pm_tree);
631 }
632
633 void print_page_map_info(struct page_map *pm)
634 {
635         struct vm_region *vmr_i;
636         printk("Page Map %p\n", pm);
637         printk("\tNum pages: %lu\n", pm->pm_num_pages);
638         spin_lock(&pm->pm_lock);
639         TAILQ_FOREACH(vmr_i, &pm->pm_vmrs, vm_pm_link) {
640                 printk("\tVMR proc %d: (%p - %p): 0x%08x, 0x%08x, %p, %p\n",
641                        vmr_i->vm_proc->pid, vmr_i->vm_base, vmr_i->vm_end,
642                        vmr_i->vm_prot, vmr_i->vm_flags, foc_pointer(vmr_i->__vm_foc),
643                            vmr_i->vm_foff);
644         }
645         spin_unlock(&pm->pm_lock);
646 }
647
648 void pm_page_asserter(struct page *page, char *str)
649 {
650         void **tree_slot = page->pg_tree_slot;
651
652         if (!page_is_pagemap(page))
653                 return;
654         assert(tree_slot);
655         assert(pm_slot_get_page(*tree_slot) == page);
656         assert(pm_slot_check_refcnt(*tree_slot) > 0);
657 }