kernel: do not drop RAM caps
[barrelfish] / kernel / cap_delete.c
1 /**
2  * \file
3  * \brief Kernel capability deletion-related operations
4  */
5
6 /*
7  * Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012, ETH Zurich.
8  * All rights reserved.
9  *
10  * This file is distributed under the terms in the attached LICENSE file.
11  * If you do not find this file, copies can be found by writing to:
12  * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
13  */
14
15 #include <stdio.h>
16 #include <string.h>
17 #include <kernel.h>
18 #include <barrelfish_kpi/syscalls.h>
19 #include <barrelfish_kpi/paging_arch.h>
20 #include <barrelfish_kpi/lmp.h>
21 #include <offsets.h>
22 #include <capabilities.h>
23 #include <cap_predicates.h>
24 #include <distcaps.h>
25 #include <dispatch.h>
26 #include <paging_kernel_arch.h>
27 #include <mdb/mdb.h>
28 #include <mdb/mdb_tree.h>
29 #include <trace/trace.h>
30 #include <wakeup.h>
31
32 struct cte *clear_head, *clear_tail;
33 struct cte *delete_head, *delete_tail;
34
35 static errval_t caps_try_delete(struct cte *cte);
36 static errval_t cleanup_copy(struct cte *cte);
37 static errval_t cleanup_last(struct cte *cte, struct cte *ret_ram_cap);
38 static void caps_mark_revoke_copy(struct cte *cte);
39 static void caps_mark_revoke_generic(struct cte *cte);
40 static void clear_list_prepend(struct cte *cte);
41 static errval_t caps_copyout_last(struct cte *target, struct cte *ret_cte);
42
43 /**
44  * \brief Try a "simple" delete of a cap. If this fails, the monitor needs to
45  * negotiate a delete across the system.
46  */
47 static errval_t caps_try_delete(struct cte *cte)
48 {
49     TRACE_CAP_MSG("trying simple delete", cte);
50     if (distcap_is_in_delete(cte) || cte->mdbnode.locked) {
51         // locked or already in process of being deleted
52         return SYS_ERR_CAP_LOCKED;
53     }
54     if (distcap_is_foreign(cte) || has_copies(cte)) {
55         return cleanup_copy(cte);
56     }
57     else if (cte->mdbnode.remote_copies
58              || cte->cap.type == ObjType_CNode
59              || cte->cap.type == ObjType_Dispatcher)
60     {
61         return SYS_ERR_DELETE_LAST_OWNED;
62     }
63     else {
64         return cleanup_last(cte, NULL);
65     }
66 }
67
68 /**
69  * \brief Delete the last copy of a cap in the entire system.
70  * \bug Somewhere in the delete process, the remote_ancs property should be
71  *      propagated to (remote) immediate descendants.
72  */
73 errval_t caps_delete_last(struct cte *cte, struct cte *ret_ram_cap)
74 {
75     errval_t err;
76     assert(!has_copies(cte));
77
78     if (cte->mdbnode.remote_copies) {
79         printk(LOG_WARN, "delete_last but remote_copies is set\n");
80     }
81
82     TRACE_CAP_MSG("deleting last", cte);
83
84     // try simple delete
85     // XXX: this really should always fail, enforce that? -MN
86     // XXX: this is probably not the way we should enforce/check this -SG
87     err = caps_try_delete(cte);
88     if (err_no(err) != SYS_ERR_DELETE_LAST_OWNED &&
89         err_no(err) != SYS_ERR_CAP_LOCKED) {
90         return err;
91     }
92
93     // CNodes and dcbs contain further CTEs, so cannot simply be deleted
94     // instead, we place them in a clear list, which is progressivly worked
95     // through until each list element contains only ctes that point to
96     // other CNodes or dcbs, at which point they are scheduled for final
97     // deletion, which only happens when the clear lists are empty.
98
99     if (cte->cap.type == ObjType_CNode) {
100         debug(SUBSYS_CAPS, "deleting last copy of cnode: %p\n", cte);
101         // Mark all non-Null slots for deletion
102         for (cslot_t i = 0; i < (1<<cte->cap.u.cnode.bits); i++) {
103             struct cte *slot = caps_locate_slot(cte->cap.u.cnode.cnode, i);
104             caps_mark_revoke_generic(slot);
105         }
106
107         assert(cte->delete_node.next == NULL || delete_head == cte);
108         cte->delete_node.next = NULL;
109         clear_list_prepend(cte);
110
111         return SYS_ERR_OK;
112     }
113     else if (cte->cap.type == ObjType_Dispatcher)
114     {
115         debug(SUBSYS_CAPS, "deleting last copy of dispatcher: %p\n", cte);
116         struct capability *cap = &cte->cap;
117         struct dcb *dcb = cap->u.dispatcher.dcb;
118
119         // Remove from queue
120         scheduler_remove(dcb);
121         // Reset current if it was deleted
122         if (dcb_current == dcb) {
123             dcb_current = NULL;
124         }
125
126         // Remove from wakeup queue
127         wakeup_remove(dcb);
128
129         // Notify monitor
130         if (monitor_ep.u.endpoint.listener == dcb) {
131             printk(LOG_ERR, "monitor terminated; expect badness!\n");
132             monitor_ep.u.endpoint.listener = NULL;
133         } else if (monitor_ep.u.endpoint.listener != NULL) {
134             uintptr_t payload = dcb->domain_id;
135             err = lmp_deliver_payload(&monitor_ep, NULL, &payload, 1, false);
136             if (err_is_fail(err)) {
137                 printk(LOG_NOTE, "while notifying monitor about domain exit: %"PRIuERRV".\n", err);
138                 printk(LOG_NOTE, "please add the console output to the following bug report: https://code.systems.ethz.ch/T78\n");
139             }
140             assert(err_is_ok(err));
141         }
142
143         caps_mark_revoke_generic(&dcb->cspace);
144         caps_mark_revoke_generic(&dcb->disp_cte);
145         assert(cte->delete_node.next == NULL || delete_head == cte);
146         cte->delete_node.next = NULL;
147         clear_list_prepend(cte);
148
149         return SYS_ERR_OK;
150     }
151     else
152     {
153         // last copy, perform object cleanup
154         return cleanup_last(cte, ret_ram_cap);
155     }
156 }
157
158 /**
159  * \brief Cleanup a cap copy but not the object represented by the cap
160  */
161 static errval_t
162 cleanup_copy(struct cte *cte)
163 {
164     errval_t err;
165
166     TRACE_CAP_MSG("cleaning up copy", cte);
167
168     struct capability *cap = &cte->cap;
169
170     if (type_is_vnode(cap->type) ||
171         cap->type == ObjType_Frame ||
172         cap->type == ObjType_DevFrame)
173     {
174         unmap_capability(cte);
175     }
176
177     if (distcap_is_foreign(cte)) {
178         TRACE_CAP_MSG("cleaning up non-owned copy", cte);
179         if (cte->mdbnode.remote_copies || cte->mdbnode.remote_descs) {
180             struct cte *ancestor = mdb_find_ancestor(cte);
181             if (ancestor) {
182                 mdb_set_relations(ancestor, RRELS_DESC_BIT, RRELS_DESC_BIT);
183             }
184         }
185     }
186
187     err = mdb_remove(cte);
188     if (err_is_fail(err)) {
189         return err;
190     }
191     TRACE_CAP_MSG("cleaned up copy", cte);
192     assert(!mdb_reachable(cte));
193     memset(cte, 0, sizeof(*cte));
194
195     return SYS_ERR_OK;
196 }
197
198 /**
199  * \brief Cleanup the last cap copy for an object and the object itself
200  */
201 static errval_t
202 cleanup_last(struct cte *cte, struct cte *ret_ram_cap)
203 {
204     errval_t err;
205
206     TRACE_CAP_MSG("cleaning up last copy", cte);
207     struct capability *cap = &cte->cap;
208
209     assert(!has_copies(cte));
210     if (cte->mdbnode.remote_copies) {
211         printk(LOG_WARN, "cleanup_last but remote_copies is set\n");
212     }
213
214     if (ret_ram_cap && ret_ram_cap->cap.type != ObjType_Null) {
215         return SYS_ERR_SLOT_IN_USE;
216     }
217
218     struct RAM ram = { .bits = 0 };
219     size_t len = sizeof(struct RAM) / sizeof(uintptr_t) + 1;
220
221     if (!has_descendants(cte) && !has_ancestors(cte)) {
222         // List all RAM-backed capabilities here
223         // NB: ObjType_PhysAddr and ObjType_DevFrame caps are *not* RAM-backed!
224         switch(cap->type) {
225         case ObjType_RAM:
226             ram.base = cap->u.ram.base;
227             ram.bits = cap->u.ram.bits;
228             break;
229
230         case ObjType_Frame:
231             ram.base = cap->u.frame.base;
232             ram.bits = cap->u.frame.bits;
233             break;
234
235         case ObjType_CNode:
236             ram.base = cap->u.cnode.cnode;
237             ram.bits = cap->u.cnode.bits + OBJBITS_CTE;
238             break;
239
240         case ObjType_Dispatcher:
241             // Convert to genpaddr
242             ram.base = local_phys_to_gen_phys(mem_to_local_phys((lvaddr_t)cap->u.dispatcher.dcb));
243             ram.bits = OBJBITS_DISPATCHER;
244             break;
245
246         default:
247             // Handle VNodes here
248             if(type_is_vnode(cap->type)) {
249                 ram.base = get_address(cap);
250                 ram.bits = vnode_objbits(cap->type);
251             }
252             break;
253         }
254     }
255
256     // have cap to return to monitor but no allocated slot and no room in
257     // monitor channel; have user retry over monitor rpc interface
258     if (ram.bits > 0 &&
259         !ret_ram_cap &&
260         err_is_fail(lmp_can_deliver_payload(&monitor_ep, len)))
261     {
262         return SYS_ERR_RETRY_THROUGH_MONITOR;
263     }
264
265
266     err = cleanup_copy(cte);
267     if (err_is_fail(err)) {
268         return err;
269     }
270
271     if(ram.bits > 0) {
272         // Send back as RAM cap to monitor
273         if (ret_ram_cap) {
274             if (dcb_current != monitor_ep.u.endpoint.listener) {
275                 printk(LOG_WARN, "sending fresh ram cap to non-monitor?\n");
276             }
277             assert(ret_ram_cap->cap.type == ObjType_Null);
278             ret_ram_cap->cap.u.ram = ram;
279             ret_ram_cap->cap.type = ObjType_RAM;
280             err = mdb_insert(ret_ram_cap);
281             TRACE_CAP_MSG("reclaimed", ret_ram_cap);
282             assert(err_is_ok(err));
283             // note: this is a "success" code!
284             err = SYS_ERR_RAM_CAP_CREATED;
285         }
286         else if (monitor_ep.type && monitor_ep.u.endpoint.listener != 0) {
287 #ifdef TRACE_PMEM_CAPS
288             struct cte ramcte;
289             memset(&ramcte, 0, sizeof(ramcte));
290             ramcte.cap.u.ram = ram;
291             ramcte.cap.type = ObjType_RAM;
292             TRACE_CAP_MSG("reclaimed", &ramcte);
293 #endif
294             // XXX: This looks pretty ugly. We need an interface.
295             err = lmp_deliver_payload(&monitor_ep, NULL,
296                                       (uintptr_t *)&ram,
297                                       len, false);
298         }
299         else {
300             printk(LOG_WARN, "dropping ram cap base %08"PRIxGENPADDR" bits %"PRIu8"\n", ram.base, ram.bits);
301         }
302         if (err_no(err) == SYS_ERR_LMP_BUF_OVERFLOW) {
303             printk(LOG_WARN, "dropped ram cap base %08"PRIxGENPADDR" bits %"PRIu8"\n", ram.base, ram.bits);
304             err = SYS_ERR_OK;
305
306         } else {
307             assert(err_is_ok(err));
308         }
309     }
310
311     return err;
312 }
313
314 /*
315  * Mark phase of revoke mark & sweep
316  */
317
318 static void caps_mark_revoke_copy(struct cte *cte)
319 {
320     errval_t err;
321     err = caps_try_delete(cte);
322     if (err_is_fail(err)) {
323         // this should not happen as there is a copy of the cap
324         panic("error while marking/deleting cap copy for revoke:"
325               " 0x%"PRIuERRV"\n", err);
326     }
327 }
328
329 static void caps_mark_revoke_generic(struct cte *cte)
330 {
331     errval_t err;
332
333     if (cte->cap.type == ObjType_Null) {
334         return;
335     }
336     if (distcap_is_in_delete(cte)) {
337         return;
338     }
339
340     TRACE_CAP_MSG("marking for revoke", cte);
341
342     err = caps_try_delete(cte);
343     if (err_no(err) == SYS_ERR_DELETE_LAST_OWNED)
344     {
345         cte->mdbnode.in_delete = true;
346         //cte->delete_node.next_slot = 0;
347
348         // insert into delete list
349         if (!delete_tail) {
350             assert(!delete_head);
351             delete_head = delete_tail = cte;
352             cte->delete_node.next = NULL;
353         }
354         else {
355             assert(delete_head);
356             assert(!delete_tail->delete_node.next);
357             delete_tail->delete_node.next = cte;
358             delete_tail = cte;
359             cte->delete_node.next = NULL;
360         }
361         TRACE_CAP_MSG("inserted into delete list", cte);
362
363         // because the monitors will perform a 2PC that deletes all foreign
364         // copies before starting the delete steps, and because the in_delete
365         // bit marks this cap as "busy" (see distcap_get_state), we can clear
366         // the remote copies bit.
367         cte->mdbnode.remote_copies = 0;
368     }
369     else if (err_is_fail(err)) {
370         // some serious mojo went down in the cleanup voodoo
371         panic("error while marking/deleting descendant cap for revoke:"
372               " 0x%"PRIuERRV"\n", err);
373     }
374 }
375
376 /**
377  * \brief Delete all copies of a foreign cap.
378  */
379 errval_t caps_delete_foreigns(struct cte *cte)
380 {
381     errval_t err;
382     struct cte *next;
383     if (cte->mdbnode.owner == my_core_id) {
384         debug(SUBSYS_CAPS, "%s called on %d for %p, owner=%d\n",
385                 __FUNCTION__, my_core_id, cte, cte->mdbnode.owner);
386         return SYS_ERR_DELETE_REMOTE_LOCAL;
387     }
388     assert(cte->mdbnode.owner != my_core_id);
389     if (cte->mdbnode.in_delete) {
390         printk(LOG_WARN,
391                "foreign caps with in_delete set,"
392                " this should not happen");
393     }
394
395     TRACE_CAP_MSG("del copies of", cte);
396
397     // XXX: should we go predecessor as well?
398     for (next = mdb_successor(cte);
399          next && is_copy(&cte->cap, &next->cap);
400          next = mdb_successor(cte))
401     {
402         // XXX: should this be == or != ?
403         assert(next->mdbnode.owner != my_core_id);
404         if (next->mdbnode.in_delete) {
405             printk(LOG_WARN,
406                    "foreign caps with in_delete set,"
407                    " this should not happen");
408         }
409         err = cleanup_copy(next);
410         if (err_is_fail(err)) {
411             panic("error while deleting extra foreign copy for remote_delete:"
412                   " %"PRIuERRV"\n", err);
413         }
414     }
415
416     // The capabilities should all be foreign, by nature of the request.
417     // Foreign capabilities are rarely locked, since they can be deleted
418     // immediately. The only time a foreign capability is locked is during
419     // move and retrieve operations. In either case, the lock on the same
420     // capability must also be acquired on the owner for the operation to
421     // succeed. Thus, we can safely unlock any capability here iff the
422     // monitor guarentees that this operation is only executed when the
423     // capability is locked on the owner.
424     cte->mdbnode.locked = false;
425     err = caps_try_delete(cte);
426     if (err_is_fail(err)) {
427         panic("error while deleting foreign copy for remote_delete:"
428               " %"PRIuERRV"\n", err);
429     }
430
431     return SYS_ERR_OK;
432 }
433
434 /**
435  * \brief Mark capabilities for a revoke operation.
436  * \param base The data for the capability being revoked
437  * \param revoked The revoke target if it is on this core. This specific
438  *        capability copy will not be marked. If supplied, is_copy(base,
439  *        &revoked->cap) must hold.
440  * \returns
441  *        - CAP_NOT_FOUND if no copies or desendants are present on this core.
442  *        - SYS_ERR_OK otherwise.
443  */
444 errval_t caps_mark_revoke(struct capability *base, struct cte *revoked)
445 {
446     assert(base);
447     assert(!revoked || revoked->mdbnode.owner == my_core_id);
448
449     // to avoid multiple mdb_find_greater, we store the predecessor of the
450     // current position
451     struct cte *prev = mdb_find_greater(base, true), *next = NULL;
452     if (!prev || !(is_copy(base, &prev->cap)
453                    || is_ancestor(&prev->cap, base)))
454     {
455         return SYS_ERR_CAP_NOT_FOUND;
456     }
457
458     for (next = mdb_successor(prev);
459          next && is_copy(base, &next->cap);
460          next = mdb_successor(prev))
461     {
462         // note: if next is a copy of base, prev will also be a copy
463         if (next == revoked) {
464             // do not delete the revoked capability, use it as the new prev
465             // instead, and delete the old prev.
466             next = prev;
467             prev = revoked;
468         }
469         assert(revoked || next->mdbnode.owner != my_core_id);
470         caps_mark_revoke_copy(next);
471     }
472
473     for (next = mdb_successor(prev);
474          next && is_ancestor(&next->cap, base);
475          next = mdb_successor(prev))
476     {
477         caps_mark_revoke_generic(next);
478         if (next->cap.type) {
479             // the cap has not been deleted, so we must use it as the new prev
480             prev = next;
481         }
482     }
483
484     if (prev != revoked && !prev->mdbnode.in_delete) {
485         if (is_copy(base, &prev->cap)) {
486             caps_mark_revoke_copy(prev);
487         }
488         else {
489             // due to early termination the condition, prev must be a
490             // descendant
491             assert(is_ancestor(&prev->cap, base));
492             caps_mark_revoke_generic(prev);
493         }
494     }
495
496     return SYS_ERR_OK;
497 }
498
499 /*
500  * Sweep phase
501  */
502
503 static void clear_list_prepend(struct cte *cte)
504 {
505     // make sure we don't break delete list by inserting cte that hasn't been
506     // removed from delete list into clear list
507     assert(cte->delete_node.next == NULL);
508
509     if (!clear_tail) {
510         assert(!clear_head);
511         clear_head = clear_tail = cte;
512         cte->delete_node.next = NULL;
513     }
514     else {
515         assert(clear_head);
516         cte->delete_node.next = clear_head;
517         clear_head = cte;
518     }
519     TRACE_CAP_MSG("inserted into clear list", cte);
520 }
521
522 errval_t caps_delete_step(struct cte *ret_next)
523 {
524     errval_t err = SYS_ERR_OK;
525
526     assert(ret_next);
527     assert(ret_next->cap.type == ObjType_Null);
528
529     if (!delete_head) {
530         assert(!delete_tail);
531         return SYS_ERR_CAP_NOT_FOUND;
532     }
533     assert(delete_head->mdbnode.in_delete == true);
534
535     TRACE_CAP_MSG("performing delete step", delete_head);
536     struct cte *cte = delete_head, *next = cte->delete_node.next;
537     if (cte->mdbnode.locked) {
538         err = SYS_ERR_CAP_LOCKED;
539     }
540     else if (distcap_is_foreign(cte) || has_copies(cte)) {
541         err = cleanup_copy(cte);
542     }
543     else if (cte->mdbnode.remote_copies) {
544         err = caps_copyout_last(cte, ret_next);
545         if (err_is_ok(err)) {
546             if (next) {
547                 delete_head = next;
548             } else {
549                 delete_head = delete_tail = NULL;
550             }
551             err = SYS_ERR_DELETE_LAST_OWNED;
552         }
553     }
554     else {
555         // XXX: need to clear delete_list flag because it's reused for
556         // clear_list? -SG
557         cte->delete_node.next = NULL;
558         err = caps_delete_last(cte, ret_next);
559         if (err_is_fail(err)) {
560             TRACE_CAP_MSG("delete last failed", cte);
561             // if delete_last fails, reinsert in delete list
562             cte->delete_node.next = next;
563         }
564     }
565
566     if (err_is_ok(err)) {
567         if (next) {
568             delete_head = next;
569         } else {
570             delete_head = delete_tail = NULL;
571         }
572     }
573     return err;
574 }
575
576 errval_t caps_clear_step(struct cte *ret_ram_cap)
577 {
578     errval_t err;
579     assert(!delete_head);
580     assert(!delete_tail);
581
582     if (!clear_head) {
583         assert(!clear_tail);
584         return SYS_ERR_CAP_NOT_FOUND;
585     }
586     assert((clear_head == clear_tail) == (!clear_head->delete_node.next));
587
588     struct cte *cte = clear_head;
589
590 #ifndef NDEBUG
591     // some sanity checks
592 #define CHECK_SLOT(slot) do { \
593     assert((slot)->cap.type == ObjType_Null \
594            || (slot)->cap.type == ObjType_CNode \
595            || (slot)->cap.type == ObjType_Dispatcher); \
596     if ((slot)->cap.type != ObjType_Null) { \
597         assert((slot)->mdbnode.in_delete); \
598     } \
599 } while (0)
600
601     if (cte->cap.type == ObjType_CNode) {
602         for (cslot_t i = 0; i < (1<<cte->cap.u.cnode.bits); i++) {
603             struct cte *slot = caps_locate_slot(cte->cap.u.cnode.cnode, i);
604             CHECK_SLOT(slot);
605         }
606     }
607     else if (cte->cap.type == ObjType_Dispatcher) {
608         struct dcb *dcb = cte->cap.u.dispatcher.dcb;
609         CHECK_SLOT(&dcb->cspace);
610         CHECK_SLOT(&dcb->disp_cte);
611     }
612     else {
613         panic("Non-CNode/Dispatcher cap type in clear list!");
614     }
615
616 #undef CHECK_SLOT
617 #endif
618
619     TRACE_CAP_MSG("caps_clear_step for", cte);
620     struct cte *after = cte->delete_node.next;
621     err = cleanup_last(cte, ret_ram_cap);
622     if (err_is_ok(err)) {
623         if (after) {
624             clear_head = after;
625         }
626         else {
627             clear_head = clear_tail = NULL;
628         }
629     }
630     return err;
631 }
632
633 static errval_t caps_copyout_last(struct cte *target, struct cte *ret_cte)
634 {
635     errval_t err;
636
637     // create a copy in slot specified by the caller, then delete
638     // `next` slot so the new copy is still the last copy.
639     err = caps_copy_to_cte(ret_cte, target, false, 0, 0);
640     if (err_is_fail(err)) {
641         return err;
642     }
643
644     err = cleanup_copy(target);
645     if (err_is_fail(err)) {
646         return err;
647     }
648
649     return SYS_ERR_OK;
650 }
651
652 /*
653  * CNode invocations
654  */
655
656 errval_t caps_delete(struct cte *cte)
657 {
658     errval_t err;
659
660     TRACE_CAP_MSG("deleting", cte);
661
662     if (cte->mdbnode.locked) {
663         return SYS_ERR_CAP_LOCKED;
664     }
665
666     err = caps_try_delete(cte);
667     if (err_no(err) == SYS_ERR_DELETE_LAST_OWNED) {
668         err = err_push(err, SYS_ERR_RETRY_THROUGH_MONITOR);
669     }
670
671     return err;
672 }
673
674 errval_t caps_revoke(struct cte *cte)
675 {
676     TRACE_CAP_MSG("revoking", cte);
677
678     if (cte->mdbnode.locked) {
679         return SYS_ERR_CAP_LOCKED;
680     }
681
682     return SYS_ERR_RETRY_THROUGH_MONITOR;
683 }