Extend scope of barrelfish_id_s, so other stack elements to not interfere.
[barrelfish] / kernel / capabilities.c
1 /**
2  * \file
3  * \brief Kernel capability management implementation.
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 <dispatch.h>
25 #include <kcb.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 <trace_definitions/trace_defs.h>
31 #include <wakeup.h>
32
33 /// Ignore remote capabilities if this is defined
34 #define RCAPDB_NULL
35
36 /// Sets the specified number of low-order bits to 1
37 #define MASK(bits)      ((1UL << bits) - 1)
38
39 struct capability monitor_ep;
40
41 /**
42  * ID capability core_local_id counter.
43  */
44 static uint32_t id_cap_counter = 1;
45
46 /**
47  *  Sets #dest equal to #src
48  *
49  * #dest cannot be in use.
50  */
51 static errval_t set_cap(struct capability *dest, struct capability *src)
52 {
53     /* Parameter checking */
54     assert(src  != NULL);
55     assert(dest != NULL);
56
57     // Reserved object bits must always be greater/equal to actual object size
58     assert((1UL << OBJBITS_CTE) >= sizeof(struct cte));
59
60     // Cannot overwrite an already existing cap
61     if (dest->type != ObjType_Null) {
62         return SYS_ERR_SLOT_IN_USE;
63     }
64
65     memcpy(dest, src, sizeof(struct capability));
66     return SYS_ERR_OK;
67 }
68
69 /**
70  * \brief Determine how many objects can be created in a specified region.
71  *
72  * This function computes the number of objects that can be created by a call
73  * to caps_create().
74  *
75  * \param type          Type of objects to create.
76  * \param bits          Size of memory area as 2^bits.
77  * \param objbits       For variable-sized objects, size multiplier as 2^bits.
78  *
79  * \return Number of objects to be created, or zero on error
80  */
81
82 // If you create more capability types you need to deal with them
83 // in the table below.
84 STATIC_ASSERT(27 == ObjType_Num, "Knowledge of all cap types");
85
86 static size_t caps_numobjs(enum objtype type, uint8_t bits, uint8_t objbits)
87 {
88     switch(type) {
89     case ObjType_PhysAddr:
90     case ObjType_RAM:
91     case ObjType_Frame:
92     case ObjType_DevFrame:
93         if (objbits > bits) {
94             return 0;
95         } else {
96             return 1UL << (bits - objbits);
97         }
98
99     case ObjType_CNode:
100         if (bits < OBJBITS_CTE || objbits > bits - OBJBITS_CTE) {
101             return 0;
102         } else {
103             return 1UL << (bits - OBJBITS_CTE - objbits);
104         }
105
106     case ObjType_VNode_x86_64_pml4:
107     case ObjType_VNode_x86_64_pdpt:
108     case ObjType_VNode_x86_64_pdir:
109     case ObjType_VNode_x86_64_ptable:
110     case ObjType_VNode_x86_32_pdpt:
111     case ObjType_VNode_x86_32_pdir:
112     case ObjType_VNode_x86_32_ptable:
113     case ObjType_VNode_ARM_l1:
114     case ObjType_VNode_ARM_l2:
115     {
116         size_t objbits_vnode = vnode_objbits(type);
117         if (bits < objbits_vnode) {
118             return 0;
119         } else {
120             return 1UL << (bits - objbits_vnode);
121         }
122     }
123
124     case ObjType_Dispatcher:
125         if (bits < OBJBITS_DISPATCHER) {
126             return 0;
127         } else {
128             return 1UL << (bits - OBJBITS_DISPATCHER);
129         }
130
131     case ObjType_KernelControlBlock:
132         if (bits < OBJBITS_KCB) {
133             return 0;
134         } else {
135             return 1UL << (bits - OBJBITS_KCB);
136         }
137
138     case ObjType_Kernel:
139     case ObjType_IRQTable:
140     case ObjType_IO:
141     case ObjType_EndPoint:
142     case ObjType_ID:
143     case ObjType_Notify_RCK:
144     case ObjType_Notify_IPI:
145     case ObjType_PerfMon:
146     case ObjType_IPI:
147         return 1;
148
149     default:
150         panic("invalid type");
151         return 0;
152     }
153 }
154
155 /**
156  * \brief Create capabilities to kernel objects.
157  *
158  * This function creates kernel objects of 'type' into the memory
159  * area, based at 'addr' and of size 2^'bits', so they completely fill the
160  * area. For each created kernel object, a capability is created to it and
161  * put consecutively into the array of CTEs pointed to by 'caps'. The array
162  * needs to have the appropriate size to hold all created caps. Some kernel
163  * objects can have a variable size. In that case, 'objbits' should be non-zero
164  * and give the a size multiplier as 2^'objbits'.
165  *
166  * \param type          Type of objects to create.
167  * \param addr          Base address in the local address space.
168  * \param bits          Size of memory area as 2^bits.
169  * \param objbits       For variable-sized objects, size multiplier as 2^bits.
170  * \param numobjs       Number of objects to be created, from caps_numobjs()
171  * \param dest_caps     Pointer to array of CTEs to hold created caps.
172  *
173  * \return Error code
174  */
175 // If you create more capability types you need to deal with them
176 // in the table below.
177 STATIC_ASSERT(27 == ObjType_Num, "Knowledge of all cap types");
178
179 static errval_t caps_create(enum objtype type, lpaddr_t lpaddr, uint8_t bits,
180                             uint8_t objbits, size_t numobjs,
181                             struct cte *dest_caps)
182 {
183     errval_t err;
184
185     /* Parameter checking */
186     assert(dest_caps != NULL);
187     assert(type != ObjType_Null);
188     assert(type < ObjType_Num);
189     assert(numobjs > 0);
190
191     genpaddr_t genpaddr = local_phys_to_gen_phys(lpaddr);
192
193     // Virtual address of the memory the kernel object resides in
194     // XXX: A better of doing this,
195     // this is creating caps that the kernel cannot address.
196     // It assumes that the cap is not of the type which will have to zeroed out.
197     lvaddr_t lvaddr;
198     if(lpaddr < PADDR_SPACE_LIMIT) {
199         lvaddr = local_phys_to_mem(lpaddr);
200     } else {
201         lvaddr = 0;
202     }
203
204     /* Initialize the created capability */
205     struct capability src_cap;
206     memset(&src_cap, 0, sizeof(struct capability));
207     src_cap.type = type;
208     // XXX: Handle rights!
209     src_cap.rights = CAPRIGHTS_ALLRIGHTS;
210
211     /* Set the type specific fields and insert into #dest_caps */
212     switch(type) {
213     case ObjType_Frame:
214         TRACE(KERNEL, BZERO, 1);
215         // XXX: SCC hack, while we don't have a devframe allocator
216         if(lpaddr + ((lpaddr_t)1 << bits) < PADDR_SPACE_LIMIT) {
217             memset((void*)lvaddr, 0, (lvaddr_t)1 << bits);
218         } else {
219             printk(LOG_WARN, "Allocating RAM at 0x%" PRIxLPADDR
220                    " uninitialized\n", lpaddr);
221         }
222         TRACE(KERNEL, BZERO, 0);
223         for(size_t i = 0; i < numobjs; i++) {
224             // Initialize type specific fields
225             src_cap.u.frame.base = genpaddr + i * ((genpaddr_t)1 << objbits);
226             src_cap.u.frame.bits = objbits;
227             // Insert the capabilities
228             err = set_cap(&dest_caps[i].cap, &src_cap);
229             if (err_is_fail(err)) {
230                 return err;
231             }
232         }
233         return SYS_ERR_OK;
234
235     case ObjType_PhysAddr:
236         for(size_t i = 0; i < numobjs; i++) {
237             // Initialize type specific fields
238             src_cap.u.physaddr.base = genpaddr + i * ((genpaddr_t)1 << objbits);
239             src_cap.u.physaddr.bits = objbits;
240             // Insert the capabilities
241             err = set_cap(&dest_caps[i].cap, &src_cap);
242             if (err_is_fail(err)) {
243                 return err;
244             }
245         }
246         return SYS_ERR_OK;
247     case ObjType_RAM:
248         for(size_t i = 0; i < numobjs; i++) {
249             // Initialize type specific fields
250             src_cap.u.ram.base = genpaddr + i * ((genpaddr_t)1 << objbits);
251             src_cap.u.ram.bits = objbits;
252             // Insert the capabilities
253             err = set_cap(&dest_caps[i].cap, &src_cap);
254             if (err_is_fail(err)) {
255                 return err;
256             }
257         }
258         return SYS_ERR_OK;
259     case ObjType_DevFrame:
260         for(size_t i = 0; i < numobjs; i++) {
261             // Initialize type specific fields
262             src_cap.u.devframe.base = genpaddr + i * ((genpaddr_t)1 << objbits);
263             src_cap.u.devframe.bits = objbits;
264             // Insert the capabilities
265             err = set_cap(&dest_caps[i].cap, &src_cap);
266             if (err_is_fail(err)) {
267                 return err;
268             }
269         }
270         return SYS_ERR_OK;
271
272     case ObjType_CNode:
273         assert((1UL << OBJBITS_CTE) >= sizeof(struct cte));
274         TRACE(KERNEL, BZERO, 1);
275         memset((void*)lvaddr, 0, 1UL << bits);
276         TRACE(KERNEL, BZERO, 0);
277
278         for(size_t i = 0; i < numobjs; i++) {
279             // Initialize type specific fields
280             src_cap.u.cnode.cnode =
281                 lpaddr + i * ((lpaddr_t)1 << (objbits + OBJBITS_CTE));
282             src_cap.u.cnode.bits = objbits;
283             src_cap.u.cnode.guard = 0;
284             src_cap.u.cnode.guard_size = 0;
285             // XXX: Handle rights!
286             src_cap.u.cnode.rightsmask = CAPRIGHTS_ALLRIGHTS;
287             // Insert the capability
288             err = set_cap(&dest_caps[i].cap, &src_cap);
289             if (err_is_fail(err)) {
290                 return err;
291             }
292         }
293         return SYS_ERR_OK;
294
295     case ObjType_VNode_ARM_l1:
296     {
297         size_t objbits_vnode = vnode_objbits(type);
298
299         TRACE(KERNEL, BZERO, 1);
300         memset((void*)lvaddr, 0, 1UL << bits);
301         TRACE(KERNEL, BZERO, 0);
302
303         for(size_t i = 0; i < numobjs; i++) {
304             // Initialize type specific fields
305             src_cap.u.vnode_arm_l1.base =
306                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
307
308 #ifdef __arm__
309             // Insert kernel/mem mappings into new table.
310             paging_make_good(
311                 gen_phys_to_local_phys(
312                     local_phys_to_mem(src_cap.u.vnode_arm_l1.base)
313                 ),
314                 1u << objbits_vnode
315                 );
316 #endif
317
318             // Insert the capability
319             err = set_cap(&dest_caps[i].cap, &src_cap);
320             if (err_is_fail(err)) {
321                 return err;
322             }
323         }
324
325         return SYS_ERR_OK;
326     }
327
328     case ObjType_VNode_ARM_l2:
329     {
330         size_t objbits_vnode = vnode_objbits(type);
331
332         TRACE(KERNEL, BZERO, 1);
333         memset((void*)lvaddr, 0, 1UL << bits);
334         TRACE(KERNEL, BZERO, 0);
335
336         for(size_t i = 0; i < numobjs; i++) {
337             // Initialize type specific fields
338             src_cap.u.vnode_arm_l2.base =
339                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
340
341             // Insert the capability
342             err = set_cap(&dest_caps[i].cap, &src_cap);
343             if (err_is_fail(err)) {
344                 return err;
345             }
346         }
347         return SYS_ERR_OK;
348     }
349
350     case ObjType_VNode_x86_32_ptable:
351     {
352         size_t objbits_vnode = vnode_objbits(type);
353
354         TRACE(KERNEL, BZERO, 1);
355         memset((void*)lvaddr, 0, 1UL << bits);
356         TRACE(KERNEL, BZERO, 0);
357
358         for(size_t i = 0; i < numobjs; i++) {
359             // Initialize type specific fields
360             src_cap.u.vnode_x86_32_ptable.base =
361                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
362
363             // Insert the capability
364             err = set_cap(&dest_caps[i].cap, &src_cap);
365             if (err_is_fail(err)) {
366                 return err;
367             }
368         }
369         return SYS_ERR_OK;
370     }
371
372     case ObjType_VNode_x86_32_pdir:
373     {
374         size_t objbits_vnode = vnode_objbits(type);
375
376         TRACE(KERNEL, BZERO, 1);
377         memset((void*)lvaddr, 0, 1UL << bits);
378         TRACE(KERNEL, BZERO, 0);
379
380         for(size_t i = 0; i < numobjs; i++) {
381             // Initialize type specific fields
382             src_cap.u.vnode_x86_32_pdir.base =
383                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
384
385 #if defined(__i386__) && !defined(CONFIG_PAE)
386             // Make it a good PDE by inserting kernel/mem VSpaces
387             lpaddr = gen_phys_to_local_phys(src_cap.u.vnode_x86_32_pdir.base);
388             paging_x86_32_make_good_pdir(lpaddr);
389 #endif
390
391             // Insert the capability
392             err = set_cap(&dest_caps[i].cap, &src_cap);
393             if (err_is_fail(err)) {
394                 return err;
395             }
396         }
397         return SYS_ERR_OK;
398     }
399
400     case ObjType_VNode_x86_32_pdpt:
401     {
402         size_t objbits_vnode = vnode_objbits(type);
403
404         TRACE(KERNEL, BZERO, 1);
405         memset((void*)lvaddr, 0, 1UL << bits);
406         TRACE(KERNEL, BZERO, 0);
407
408         for(size_t i = 0; i < numobjs; i++) {
409             // Initialize type specific fields
410             src_cap.u.vnode_x86_32_pdir.base =
411                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
412
413 #if defined(__i386__) && defined(CONFIG_PAE)
414             // Make it a good PDPTE by inserting kernel/mem VSpaces
415             lpaddr_t var =
416                 gen_phys_to_local_phys(src_cap.u.vnode_x86_32_pdpt.base);
417             paging_x86_32_make_good_pdpte(var);
418 #endif
419
420             // Insert the capability
421             err = set_cap(&dest_caps[i].cap, &src_cap);
422             if (err_is_fail(err)) {
423                 return err;
424             }
425         }
426         return SYS_ERR_OK;
427     }
428
429     case ObjType_VNode_x86_64_ptable:
430     {
431         size_t objbits_vnode = vnode_objbits(type);
432
433         TRACE(KERNEL, BZERO, 1);
434         memset((void*)lvaddr, 0, 1UL << bits);
435         TRACE(KERNEL, BZERO, 0);
436
437         for(size_t i = 0; i < numobjs; i++) {
438             // Initialize type specific fields
439             src_cap.u.vnode_x86_64_ptable.base =
440                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
441
442             // Insert the capability
443             err = set_cap(&dest_caps[i].cap, &src_cap);
444             if (err_is_fail(err)) {
445                 return err;
446             }
447         }
448         return SYS_ERR_OK;
449     }
450
451     case ObjType_VNode_x86_64_pdir:
452     {
453         size_t objbits_vnode = vnode_objbits(type);
454
455         TRACE(KERNEL, BZERO, 1);
456         memset((void*)lvaddr, 0, 1UL << bits);
457         TRACE(KERNEL, BZERO, 0);
458
459         for(size_t i = 0; i < numobjs; i++) {
460             // Initialize type specific fields
461             src_cap.u.vnode_x86_64_pdir.base =
462                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
463
464             // Insert the capability
465             err = set_cap(&dest_caps[i].cap, &src_cap);
466             if (err_is_fail(err)) {
467                 return err;
468             }
469         }
470         return SYS_ERR_OK;
471     }
472
473     case ObjType_VNode_x86_64_pdpt:
474     {
475         size_t objbits_vnode = vnode_objbits(type);
476
477         TRACE(KERNEL, BZERO, 1);
478         memset((void*)lvaddr, 0, 1UL << bits);
479         TRACE(KERNEL, BZERO, 0);
480
481         for(size_t i = 0; i < numobjs; i++) {
482             // Initialize type specific fields
483             src_cap.u.vnode_x86_64_pdpt.base =
484                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
485
486             // Insert the capability
487             err = set_cap(&dest_caps[i].cap, &src_cap);
488             if (err_is_fail(err)) {
489                 return err;
490             }
491         }
492         return SYS_ERR_OK;
493     }
494
495     case ObjType_VNode_x86_64_pml4:
496     {
497         size_t objbits_vnode = vnode_objbits(type);
498
499         TRACE(KERNEL, BZERO, 1);
500         memset((void*)lvaddr, 0, 1UL << bits);
501         TRACE(KERNEL, BZERO, 0);
502
503         for(size_t i = 0; i < numobjs; i++) {
504             // Initialize type specific fields
505             src_cap.u.vnode_x86_64_pml4.base =
506                 genpaddr + i * ((genpaddr_t)1 << objbits_vnode);
507
508 #ifdef __k1om__
509             lpaddr_t var = gen_phys_to_local_phys(src_cap.u.vnode_x86_64_pml4.base);
510                         paging_k1om_make_good_pml4(var);
511 #else
512 #ifdef __x86_64__
513             // Make it a good PML4 by inserting kernel/mem VSpaces
514             lpaddr_t var =
515                 gen_phys_to_local_phys(src_cap.u.vnode_x86_64_pml4.base);
516             paging_x86_64_make_good_pml4(var);
517 #endif
518 #endif
519
520             // Insert the capability
521             err = set_cap(&dest_caps[i].cap, &src_cap);
522             if (err_is_fail(err)) {
523                 return err;
524             }
525         }
526
527         return SYS_ERR_OK;
528     }
529
530     case ObjType_Dispatcher:
531         assert((1UL << OBJBITS_DISPATCHER) >= sizeof(struct dcb));
532         TRACE(KERNEL, BZERO, 1);
533         memset((void*)lvaddr, 0, 1UL << bits);
534         TRACE(KERNEL, BZERO, 0);
535
536         for(size_t i = 0; i < numobjs; i++) {
537             // Initialize type specific fields
538             src_cap.u.dispatcher.dcb = (struct dcb *)
539                 (lvaddr + i * (1UL << OBJBITS_DISPATCHER));
540             // Insert the capability
541             err = set_cap(&dest_caps[i].cap, &src_cap);
542             if (err_is_fail(err)) {
543                 return err;
544             }
545         }
546         return SYS_ERR_OK;
547
548     case ObjType_ID:
549         // ID type does not refer to a kernel object
550         assert(lpaddr  == 0);
551         assert(bits    == 0);
552         assert(objbits == 0);
553         assert(numobjs == 1);
554
555         // Prevent wrap around
556         if (id_cap_counter >= UINT32_MAX) {
557             return SYS_ERR_ID_SPACE_EXHAUSTED;
558         }
559
560         // Generate a new ID, core_local_id monotonically increases
561         src_cap.u.id.coreid = my_core_id;
562         src_cap.u.id.core_local_id = id_cap_counter++;
563
564         // Insert the capability
565         return set_cap(&dest_caps->cap, &src_cap);
566
567     case ObjType_IO:
568         src_cap.u.io.start = 0;
569         src_cap.u.io.end   = 65535;
570         /* fall through */
571
572     case ObjType_Kernel:
573     case ObjType_IPI:
574     case ObjType_IRQTable:
575     case ObjType_EndPoint:
576     case ObjType_Notify_RCK:
577     case ObjType_Notify_IPI:
578     case ObjType_PerfMon:
579         // These types do not refer to a kernel object
580         assert(lpaddr  == 0);
581         assert(bits    == 0);
582         assert(objbits == 0);
583         assert(numobjs == 1);
584
585         // Insert the capability
586         return set_cap(&dest_caps->cap, &src_cap);
587
588     case ObjType_KernelControlBlock:
589         assert((1UL << OBJBITS_KCB) >= sizeof(struct dcb));
590         TRACE(KERNEL, BZERO, 1);
591         memset((void*)lvaddr, 0, 1UL << bits);
592         TRACE(KERNEL, BZERO, 0);
593
594         for(size_t i = 0; i < numobjs; i++) {
595             // Initialize type specific fields
596             src_cap.u.kernelcontrolblock.kcb = (struct kcb *)
597                 (lvaddr + i * (1UL << OBJBITS_DISPATCHER));
598             // Insert the capability
599             err = set_cap(&dest_caps[i].cap, &src_cap);
600             if (err_is_fail(err)) {
601                 return err;
602             }
603         }
604         return SYS_ERR_OK;
605
606     default:
607         panic("Unhandled capability type or capability of this type cannot"
608               " be created");
609     }
610 }
611
612 /**
613  * Look up a capability.
614  *
615  * Starting from #cnode_cap, recursively lookup the capability at #cptr
616  * with #vbits.
617  *
618  * \bug Handle rights
619  */
620 errval_t caps_lookup_slot(struct capability *cnode_cap, capaddr_t cptr,
621                           uint8_t vbits, struct cte **ret, CapRights rights)
622 {
623     TRACE(KERNEL, CAP_LOOKUP_SLOT, 0);
624     /* parameter checking */
625     assert(cnode_cap != NULL);
626
627     /* Can only resolve CNode type */
628     if (cnode_cap->type != ObjType_CNode) {
629         debug(SUBSYS_CAPS, "caps_lookup_slot: Cap to lookup not of type CNode\n"
630               "cnode_cap->type = %u\n", cnode_cap->type);
631         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
632         return SYS_ERR_CNODE_TYPE;
633     }
634
635     /* Apply rights to this CNode */
636     if ((cnode_cap->rights & rights) != rights) {
637         debug(SUBSYS_CAPS, "caps_lookup_slot: Rights mismatch\n"
638               "Passed rights = %u, cnode_cap->rights = %u\n",
639               rights, cnode_cap->rights);
640         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
641         return SYS_ERR_CNODE_RIGHTS;
642     }
643
644     /* Number of bits resolved by this cnode (guard and bits) */
645     uint8_t bits_resolved = cnode_cap->u.cnode.bits +
646         cnode_cap->u.cnode.guard_size;
647     // All CNodes must resolve at least one bit
648     assert(bits_resolved > 0);
649     // If lookup exceeded expected depth then table is malformed
650     if (bits_resolved > vbits) {
651         debug(SUBSYS_CAPS, "caps_lookup_slot: Lookup exceeded valid bits\n"
652               "Cnode bits = %u, guard size = %u, valid bits = %u\n",
653               cnode_cap->u.cnode.bits, cnode_cap->u.cnode.guard_size,
654               vbits);
655         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
656         return SYS_ERR_DEPTH_EXCEEDED;
657     }
658
659     /* Guard-check (bit-mask of guard in cptr must match guard in cnode cap) */
660     capaddr_t cptr_guard = (cptr >> (vbits - cnode_cap->u.cnode.guard_size))
661         & MASK(cnode_cap->u.cnode.guard_size);
662     if (cptr_guard != cnode_cap->u.cnode.guard) {
663         debug(SUBSYS_CAPS, "caps_lookup_slot: guard check failed\n"
664               "Computed guard = %"PRIuCADDR", "
665               "Cnode guard = %"PRIxCADDR", bits = %u\n",
666               cptr_guard, cnode_cap->u.cnode.guard,
667               cnode_cap->u.cnode.guard_size);
668         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
669         return SYS_ERR_GUARD_MISMATCH;
670     }
671
672     /* Locate capability in this cnode */
673     // Offset into the cnode
674     size_t offset = (cptr >> (vbits - bits_resolved)) &
675         MASK(cnode_cap->u.cnode.bits);
676     // The capability at the offset
677     struct cte *next_slot = caps_locate_slot(cnode_cap->u.cnode.cnode, offset);
678     // Do not return NULL type capability
679     if (next_slot->cap.type == ObjType_Null) {
680         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
681         return SYS_ERR_CAP_NOT_FOUND;
682     }
683
684     /* Number of bits left to resolve */
685     int bitsleft = vbits - bits_resolved;
686     // If all bits have been resolved, return the capability
687     if(bitsleft == 0) {
688         *ret = next_slot;
689         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
690         return SYS_ERR_OK;
691     }
692
693     /* If next capability is not of type cnode, return it */
694     // XXX: Is this consistent?
695     if (next_slot->cap.type != ObjType_CNode) {
696         *ret = next_slot;
697         TRACE(KERNEL, CAP_LOOKUP_SLOT, 1);
698         return SYS_ERR_OK;
699     }
700
701     /* Descend to next level */
702     return caps_lookup_slot(&next_slot->cap, cptr, bitsleft, ret, rights);
703 }
704
705 /**
706  * Wrapper for caps_lookup_slot returning capability instead of cte.
707  */
708 errval_t caps_lookup_cap(struct capability *cnode_cap, capaddr_t cptr,
709                          uint8_t vbits, struct capability **ret, CapRights rights)
710 {
711     TRACE(KERNEL, CAP_LOOKUP_CAP, 0);
712     struct cte *ret_cte;
713     errval_t err = caps_lookup_slot(cnode_cap, cptr, vbits, &ret_cte, rights);
714     if (err_is_fail(err)) {
715         return err;
716     }
717     *ret = &ret_cte->cap;
718     TRACE(KERNEL, CAP_LOOKUP_CAP, 1);
719     return SYS_ERR_OK;
720 }
721
722 /**
723  * \brief Create a capability from an existing capability metadata.
724  *
725  * Used when sending capabilities across cores. The metadata is sent across
726  * cores and the receiving monitor can create the new capability on its core.
727  */
728 errval_t caps_create_from_existing(struct capability *root, capaddr_t cnode_cptr,
729                                    int cnode_vbits, cslot_t dest_slot,
730                                    struct capability *src)
731 {
732     TRACE(KERNEL, CAP_CREATE_FROM_EXISTING, 0);
733     errval_t err;
734     struct capability *cnode;
735     err = caps_lookup_cap(root, cnode_cptr, cnode_vbits, &cnode,
736                           CAPRIGHTS_READ_WRITE);
737     if (err_is_fail(err)) {
738         return err_push(err, SYS_ERR_SLOT_LOOKUP_FAIL);
739     }
740     if (cnode->type != ObjType_CNode) {
741         return SYS_ERR_CNODE_TYPE;
742     }
743
744     struct cte *dest = caps_locate_slot(cnode->u.cnode.cnode, dest_slot);
745
746     err = set_cap(&dest->cap, src);
747     if (err_is_fail(err)) {
748         return err;
749     }
750
751     set_init_mapping(dest, 1);
752     TRACE(KERNEL, CAP_CREATE_FROM_EXISTING, 1);
753     return SYS_ERR_OK;
754 }
755
756 /// Create caps to new kernel objects.
757 errval_t caps_create_new(enum objtype type, lpaddr_t addr, size_t bits,
758                          size_t objbits, struct cte *caps)
759 {
760     TRACE(KERNEL, CAP_CREATE_NEW, 0);
761     /* Parameter checking */
762     assert(type != ObjType_EndPoint); // Cap of this type cannot be created
763
764     size_t numobjs = caps_numobjs(type, bits, objbits);
765     assert(numobjs > 0);
766
767     /* Create the new capabilities */
768     errval_t err = caps_create(type, addr, bits, objbits, numobjs, caps);
769     if (err_is_fail(err)) {
770         return err;
771     }
772
773     // Handle the mapping database
774     set_init_mapping(caps, numobjs);
775     TRACE(KERNEL, CAP_CREATE_NEW, 1);
776     return SYS_ERR_OK;
777 }
778
779
780 /// Retype caps
781 errval_t caps_retype(enum objtype type, size_t objbits,
782                      struct capability *dest_cnode, cslot_t dest_slot,
783                      struct cte *src_cte, bool from_monitor)
784 {
785     TRACE(KERNEL, CAP_RETYPE, 0);
786     size_t numobjs;
787     uint8_t bits = 0;
788     genpaddr_t base = 0;
789     errval_t err;
790
791     /* Parameter checking */
792     assert(type != ObjType_Null);
793     assert(type < ObjType_Num);
794
795     struct capability *src_cap = &src_cte->cap;
796
797     /* Check retypability */
798     err = is_retypeable(src_cte, src_cap->type, type, from_monitor);
799     if (err_is_fail(err)) {
800         debug(SUBSYS_CAPS, "caps_retype: is_retypeable failed\n");
801         return err;
802     }
803
804     /* Create Destination caps as per source and destination type */
805     switch(src_cap->type) {
806     case ObjType_PhysAddr:
807         bits = src_cap->u.physaddr.bits;
808         base = src_cap->u.physaddr.base;
809         break;
810
811     case ObjType_RAM:
812         bits = src_cap->u.ram.bits;
813         base = src_cap->u.ram.base;
814         break;
815
816     case ObjType_Dispatcher:
817         bits = base = 0;
818         break;
819
820     case ObjType_Frame:
821         bits = src_cap->u.frame.bits;
822         base = src_cap->u.frame.base;
823         break;
824
825     case ObjType_DevFrame:
826         bits = src_cap->u.devframe.bits;
827         base = src_cap->u.devframe.base;
828         break;
829
830     default:
831         panic("Unreachable case");
832     }
833
834     /* determine number of objects to be created */
835     numobjs = caps_numobjs(type, bits, objbits);
836
837     if (numobjs == 0) {
838         debug(SUBSYS_CAPS, "caps_retype: numobjs == 0\n");
839         return SYS_ERR_INVALID_SIZE_BITS;
840     }
841    // debug(SUBSYS_CAPS, "caps_retype: numobjs == %d\n", (int)numobjs);
842
843     /* check that destination slots all fit within target cnode */
844     if (dest_slot + numobjs > (1UL << dest_cnode->u.cnode.bits)) {
845         debug(SUBSYS_CAPS, "caps_retype: dest slots don't fit in cnode\n");
846         return SYS_ERR_SLOTS_INVALID;
847     }
848
849     /* check that destination slots are all empty */
850     debug(SUBSYS_CAPS, "caps_retype: dest cnode is %#" PRIxLPADDR
851           " dest_slot %d\n",
852           dest_cnode->u.cnode.cnode, (int)dest_slot);
853     for (cslot_t i = 0; i < numobjs; i++) {
854         if (caps_locate_slot(dest_cnode->u.cnode.cnode, dest_slot + i)->cap.type
855             != ObjType_Null) {
856             debug(SUBSYS_CAPS, "caps_retype: dest slot %d in use\n",
857                   (int)(dest_slot + i));
858             return SYS_ERR_SLOTS_IN_USE;
859         }
860     }
861
862     /* create new caps */
863     struct cte *dest_cte =
864         caps_locate_slot(dest_cnode->u.cnode.cnode, dest_slot);
865     err = caps_create(type, base, bits, objbits, numobjs, dest_cte);
866     if (err_is_fail(err)) {
867         debug(SUBSYS_CAPS, "caps_retype: failed to create a dest cap\n");
868         return err_push(err, SYS_ERR_RETYPE_CREATE);
869     }
870
871     /* special initialisation for endpoint caps */
872     if (type == ObjType_EndPoint) {
873         assert(src_cap->type == ObjType_Dispatcher);
874         assert(numobjs == 1);
875         struct capability *dest_cap = &dest_cte->cap;
876         dest_cap->u.endpoint.listener = src_cap->u.dispatcher.dcb;
877     }
878
879     /* Handle mapping */
880     for (size_t i = 0; i < numobjs; i++) {
881         mdb_insert(&dest_cte[i]);
882     }
883
884     TRACE(KERNEL, CAP_RETYPE, 1);
885     return SYS_ERR_OK;
886 }
887
888 /// Check the validity of a retype operation
889 errval_t is_retypeable(struct cte *src_cte, enum objtype src_type,
890                        enum objtype dest_type, bool from_monitor)
891 {
892     if (!is_well_founded(src_type, dest_type)) {
893         return SYS_ERR_INVALID_RETYPE;
894     } else if (!is_revoked_first(src_cte, src_type)){
895         printf("err_revoke_first: (%p, %d, %d)\n", src_cte, src_type, dest_type);
896         return SYS_ERR_REVOKE_FIRST;
897 #ifndef RCAPDB_NULL
898     } else if (!from_monitor && is_cap_remote(src_cte)) {
899         return SYS_ERR_RETRY_THROUGH_MONITOR;
900 #endif
901     } else {
902         return SYS_ERR_OK;
903     }
904 }
905
906 /// Create copies to a slot within a cnode
907 errval_t caps_copy_to_cnode(struct cte *dest_cnode_cte, cslot_t dest_slot,
908                             struct cte *src_cte, bool mint, uintptr_t param1,
909                             uintptr_t param2)
910 {
911     /* Parameter Checking */
912     assert(dest_cnode_cte->cap.type == ObjType_CNode);
913
914     struct cte *dest_cte;
915     dest_cte = caps_locate_slot(dest_cnode_cte->cap.u.cnode.cnode, dest_slot);
916     return caps_copy_to_cte(dest_cte, src_cte, mint, param1, param2);
917
918 }
919
920 /// Create copies to a cte
921 errval_t caps_copy_to_cte(struct cte *dest_cte, struct cte *src_cte, bool mint,
922                           uintptr_t param1, uintptr_t param2)
923 {
924     errval_t err;
925     /* Parameter checking */
926     // Null checking
927     assert(dest_cte != NULL);
928     assert(src_cte != NULL);
929
930     struct capability *src_cap  = &src_cte->cap;
931     struct capability *dest_cap = &dest_cte->cap;
932     // NULL caps cannot be copied/minted
933     if (src_cap->type == ObjType_Null) {
934         return SYS_ERR_CAP_NOT_FOUND;
935     }
936     // Parameters should be 0 if not minting
937     if (!mint) {
938         assert(param1 == 0);
939         assert(param2 == 0);
940     }
941
942     /* Insert #source_cap into #dest_cap */
943     err = set_cap(dest_cap, src_cap);
944     if (err_is_fail(err)) {
945         return err;
946     }
947
948     /* Copy is done */
949     if(!mint) {
950         // Handle mapping here only for non-mint operations
951         // (mint can change eq fields which would make the early insertion
952         // invalid in some cases)
953         mdb_insert(dest_cte);
954         return SYS_ERR_OK;
955     }
956
957     /* For minting, set the specified parameters */
958     // Process source-specific parameters for minting
959     // XXX: If failure, revert the insertion
960     switch(src_cap->type) {
961     case ObjType_CNode:
962         if (param2 > CPTR_BITS) {
963             return SYS_ERR_GUARD_SIZE_OVERFLOW;
964         }
965         dest_cap->u.cnode.guard      = param1;
966         dest_cap->u.cnode.guard_size = param2;
967         break;
968
969     case ObjType_EndPoint:
970         // XXX: FIXME: check that buffer offset lies wholly within the disp frame
971         // can't easily enforce this here, because the dispatcher frame may not
972         // yet be setup
973 /*        if (param1 < sizeof(struct dispatcher) ||
974             dest_cap->u.endpoint.listener->disp == NULL ||
975             param2 < IDC_RECV_LENGTH ||
976             param1 + sizeof(struct idc_endpoint) + param2 * sizeof(uintptr_t) >
977             (1UL << dest_cap->u.endpoint.listener->disp_cte.cap.u.frame.bits)) {
978             return SYS_ERR_INVALID_EPBUF;
979         }*/
980         if (param2 < LMP_RECV_HEADER_LENGTH) {
981             return SYS_ERR_INVALID_EPLEN;
982         }
983         dest_cap->u.endpoint.epoffset = param1;
984         dest_cap->u.endpoint.epbuflen = param2;
985         break;
986
987     case ObjType_IO:
988         if(src_cap->u.io.start  <= param1) {
989             dest_cap->u.io.start = param1;
990         }
991         if(src_cap->u.io.end  >= param2) {
992             dest_cap->u.io.end = param2;
993         }
994         break;
995
996     default:
997         // Unhandled source type for mint
998         return SYS_ERR_INVALID_SOURCE_TYPE;
999     }
1000
1001     // Handle mapping after doing minting operation
1002     mdb_insert(dest_cte);
1003
1004     return SYS_ERR_OK;
1005 }
1006
1007 /// Handle deletion of a cnode or dcb cap
1008 static void delete_cnode_or_dcb(struct capability *cap, bool from_monitor)
1009 {
1010     assert(cap != NULL);
1011     assert((cap->type == ObjType_CNode) || (cap->type == ObjType_Dispatcher));
1012
1013     if(cap->type == ObjType_CNode) {
1014         // Number of slots in the cnode
1015         cslot_t max_slots = 1UL << cap->u.cnode.bits;
1016
1017         // Delete each non Null slot
1018         for (cslot_t slot_no = 0; slot_no < max_slots; slot_no++) {
1019             struct cte *cte_in_cnode =
1020                 caps_locate_slot(cap->u.cnode.cnode, slot_no);
1021             if (cte_in_cnode->cap.type != ObjType_Null) {
1022                 caps_delete(cte_in_cnode, from_monitor);
1023             }
1024         }
1025     } else {
1026         struct dcb *dcb = cap->u.dispatcher.dcb;
1027         // Delete each slot in dispatcher
1028         if (dcb->cspace.cap.type != ObjType_Null) {
1029             caps_delete(&dcb->cspace, from_monitor);
1030         }
1031         if (dcb->disp_cte.cap.type != ObjType_Null) {
1032             caps_delete(&dcb->disp_cte, from_monitor);
1033         }
1034
1035         // Remove from queue
1036         scheduler_remove(dcb);
1037         // Reset curent if it was deleted
1038         if (dcb_current == dcb) {
1039             dcb_current = NULL;
1040         }
1041
1042         // Remove from wakeup queue
1043         wakeup_remove(dcb);
1044
1045         // Notify monitor
1046         if (monitor_ep.u.endpoint.listener == dcb) {
1047             printk(LOG_ERR, "monitor terminated; expect badness!\n");
1048             monitor_ep.u.endpoint.listener = NULL;
1049         } else if (monitor_ep.u.endpoint.listener != NULL) {
1050             errval_t err;
1051             uintptr_t payload = dcb->domain_id;
1052             err = lmp_deliver_payload(&monitor_ep, NULL, &payload, 1, false);
1053             assert(err_is_ok(err));
1054         }
1055     }
1056 }
1057
1058 /**
1059  * \brief Delete a capability from a table entry.
1060  *
1061  * Deletes the capability from the table entry pointed to by
1062  * 'cte'.
1063  *
1064  * \param cte   Pointer to table entry to delete cap from.
1065  *
1066  * \bug If deleting the last copy of a cnode or dispatcher, recursively delete
1067  */
1068 errval_t caps_delete(struct cte *cte, bool from_monitor)
1069 {
1070     assert(cte != NULL);
1071
1072 #ifndef RCAPDB_NULL
1073     if (!from_monitor && is_cap_remote(cte) && !has_copies(cte)) {
1074         // delete on the last copy of a remote cap, do this through the monitor
1075         // so we can inform other cores
1076         return SYS_ERR_RETRY_THROUGH_MONITOR;
1077     }
1078 #endif
1079
1080     struct capability *cap = &cte->cap;
1081     // special handling for last copy of cnode and dispatcher types
1082     if ((cap->type == ObjType_CNode) || (cap->type == ObjType_Dispatcher)) {
1083         if (!has_copies(cte)) {
1084             delete_cnode_or_dcb(cap, from_monitor);
1085         }
1086     }
1087
1088     // If this was the last reference to an object, we might have to
1089     // resurrect the RAM and send it back to the monitor
1090     if(!has_copies(cte) && !has_descendants(cte) && !has_ancestors(cte)
1091        && !is_cap_remote(cte) && monitor_ep.u.endpoint.listener != NULL) {
1092         struct RAM ram = { .bits = 0 };
1093         size_t len = sizeof(struct RAM) / sizeof(uintptr_t) + 1;
1094
1095         // List all RAM-backed capabilities here
1096         // NB: ObjType_PhysAddr and ObjType_DevFrame caps are *not* RAM-backed!
1097         switch(cap->type) {
1098         case ObjType_RAM:
1099             ram.base = cap->u.ram.base;
1100             ram.bits = cap->u.ram.bits;
1101             break;
1102
1103         case ObjType_Frame:
1104             ram.base = cap->u.frame.base;
1105             ram.bits = cap->u.frame.bits;
1106             break;
1107
1108         case ObjType_CNode:
1109             ram.base = cap->u.cnode.cnode;
1110             ram.bits = cap->u.cnode.bits + OBJBITS_CTE;
1111             break;
1112
1113         case ObjType_Dispatcher:
1114             // Convert to genpaddr
1115             ram.base = local_phys_to_gen_phys(mem_to_local_phys((lvaddr_t)cap->u.dispatcher.dcb));
1116             ram.bits = OBJBITS_DISPATCHER;
1117             break;
1118
1119         default:
1120             // Handle VNodes here
1121             if(type_is_vnode(cap->type)) {
1122                 ram.base = get_address(cap);
1123                 ram.bits = vnode_objbits(cap->type);
1124             }
1125             break;
1126         }
1127
1128         if(ram.bits > 0) {
1129             // Send back as RAM cap to monitor
1130             // XXX: This looks pretty ugly. We need an interface.
1131             // FIXME: why exactly the return value of this call is ignored?
1132             //errval_t err =
1133                 lmp_deliver_payload(&monitor_ep, NULL,
1134                                       (uintptr_t *)&ram,
1135                                       len, false);
1136             //assert(err_is_ok(err));
1137         }
1138     }
1139
1140     // unmap if mapped
1141     if (type_is_vnode(cap->type) || cap->type == ObjType_Frame || cap->type == ObjType_DevFrame) {
1142         unmap_capability(cte);
1143     }
1144
1145     // Remove from mapping database
1146     remove_mapping(cte);
1147     // Initialize the cap
1148     memset(cte, 0, sizeof(struct cte));
1149
1150     return SYS_ERR_OK;
1151 }
1152
1153 /**
1154  * \brief Revoke a cap
1155  *
1156  * Find all copies and descendants and delete them.
1157  * When seeing a capability with no relations, stop traversing.
1158  */
1159 errval_t caps_revoke(struct cte *cte, bool from_monitor)
1160 {
1161     assert(cte != NULL);
1162
1163 #ifndef RCAPDB_NULL
1164     if (!from_monitor && is_cap_remote(cte)) {
1165         return SYS_ERR_RETRY_THROUGH_MONITOR;
1166     }
1167 #endif
1168
1169     struct cte *walk;
1170     errval_t err = SYS_ERR_OK;
1171     // Traverse forward
1172     walk = mdb_successor(cte);
1173     while(walk && walk != cte && err_is_ok(err)) {
1174         struct cte *next = mdb_successor(walk);
1175         if (is_ancestor(&walk->cap, &cte->cap)) {
1176             err = caps_delete(walk, from_monitor);
1177         } else if(is_copy(&walk->cap, &cte->cap)) {
1178             err = caps_delete(walk, from_monitor);
1179         } else {
1180             break;
1181         }
1182         walk = next;
1183     }
1184
1185     // Traverse backwards
1186     walk = mdb_predecessor(cte);
1187     while(walk && walk != cte && err_is_ok(err)) {
1188         struct cte *prev = mdb_predecessor(walk);
1189         if (is_ancestor(&walk->cap, &cte->cap)) {
1190             err = caps_delete(walk, from_monitor);
1191         } else if(is_copy(&walk->cap, &cte->cap)) {
1192             err = caps_delete(walk, from_monitor);
1193         } else {
1194             break;
1195         }
1196         walk = prev;
1197     }
1198
1199     return err;
1200 }