系统设计 #

基于上述背景，我们利用用户态中断技术，通过兼容capability机制和异步通信接口来改造微内核的通知机制（U-notification）。同时我们基于U-notification，借助共享内存和编程语言对异步编程的支持，设计了无需陷入内核的异步系统调用和异步IPC框架，在提升用户态并发度的同时，减少用户态和内核态的切换次数，最终提升系统的整体性能。异步微内核框架主要由四个部分构成：

用户态中断控制器（UINTC）：用户态中断控制器使用硬件维护了发送状态表和接收状态表。接收状态表中包含了代理中断所需要的状态码、处理中断的hart id、以及中断状态字（irq）。发送状态表则包含了中断号以及接收状态表项的索引信息。发送端通过调用uipi send指令，找到接收状态表项，并通过核间中断，设置对应hart id的CPU核心的中断代理寄存器，其具体设计请参考此处。
U-notification：U-notification所需的硬件资源由内核管理，内核将UINTC的硬件资源索引集成到notification对象中，以兼容原始的通知机制。用户态程序通过系统调用来申请和释放硬件资源。
共享内存：由于通知机制的传递数据量有限（仅1 bit），我们仅将其作为同步的方式，收发双方通过共享内存的形式进行数据通信。
异步运行时：为了更好地使用异步IPC，我们设计了异步运行时。主要分为用户态和内核态。用户态的异步运行时代理了硬件资源的申请和释放，同时还维护了能力具柄（capability）到硬件索引的映射，以实现通知机制的兼容性。此外，异步运行时还代理了所有的系统调用请求，根据系统调用的类型将其转化为同步或者异步。最后，运行时中包含一个优先级调度器用于调用协程任务，提升用户态的并发度。内核态的异步运行时包含了异步系统调用的处理协程，以及一个优先级调度器用于调度执行这些协程。

根目录章节

U-notification #

用户态中断使得控制流和数据流相互分离。我们在原本的notification内核对象中维护了用户态中断相关的硬件资源索引，用户程序通过系统调用向内核进行注册，申请硬件资源，数据流则通过特殊的用户态指令访问用户态中断控制器，从而在通信过程中避免了特权级的切换。

根目录章节

控制流 #

控制流主要分为接收方的注册和发送方的注册。

接收方在用户态通过Untyped_Retype申请一个Notification对象，调用TCB_Bind接口进行硬件资源绑定，运行时进一步调用UintrRegisterReceiver系统调用，将运行时中定义的用户态中断向量表注册到TCB中，申请UINTC的接收状态表项，并绑定到Notification对象及其对应的线程上。发送方通过Capability派生的形式（直接构造发送方的Capability空间，或通过内核转发的形式获取Capability）获取指向Notification对象的Capability，第一次调用Send操作时，运行时会判断Cap是否有对应的Sender ID，如果没有，则调用UintrRegisterSender系统调用进行发送端注册，并填充对应的SenderID。相关资源的回收则通过已有的revoke或delete系统调用注销内核对象。

相比于原始的通知机制，U-notification在通信权限控制方面同主要存在以下两点不同：

原始的通知机制允许多个接收线程竞争接收一个内核对象上的通知，这种设计的目的是为了支持多接收端的场景，事实上，多接收端已经通过多个内核对象来进行支持，因此这种机制相对冗余，而由于U-notification中接收端对接收线程的独占性，这个能力将不再被支持。
原始的通知机制允许单个接收线程接收多个内核对象上的通知，这种设计的目的是更灵活地支持多发送端的场景，在U-notification中，同一个内核对象可以被设置为相同的recv status idx，不同的发送端则通过使用中断号(uintr vec)来进行区分。

数据流 #

数据流由硬件直接传递，无需通过内核。发送端在注册完成之后，可以直接调用uipi_send指令，指令根据Sender Status Table Entry中的索引设置中断控制器中的寄存器。如果接收端本身在CPU核心上运行，会立刻被中断并跳转到注册的中断向量表，否则会等到被内核重新调度时再处理数据。

改造前后的通信方式也有所区别。原始的通知机制需要用户态接收方通过系统调用主动询问内核是否有通知需要处理。根据是否要将线程阻塞，一般被设计为Wait和Poll两个接口。而U-notification无需接收线程主动陷入并询问内核，接收方被硬件发起的用户态中断打断，并处理到来的通知，这在很大程度上解放了接收方，程序设计者无需关心通知到来的时机，减少了CPU忙等的几率，提升了用户态的并发度。而为了提升U-notification的易用性，我们对原始的通信接口进行了兼容：

Poll：无需陷入内核态，在用户态读取中断状态寄存器，判断是否有效并返回。
Wait：对该接口的兼容需要用户态的异步运行时的调度器提供相关支持，在没有有效中断时，该操作将阻塞当前协程并切换到其他协程执行，等待用户态中断唤醒。

共享内存 #

由于U-notification只能传递通知信号，因此我们依然需要共享内存来作为IPC数据传递的主要形式，我们以IPC中最常见的Call为例，客户端需要将请求数据准备好并写入共享内存中，而服务端将在某个时刻从共享内存中读取请求，处理后将响应写回共享内存，而客户端也将在之后的某一时刻从共享内存中读取响应并进行相应处理。IPC的数据交互中最需要强调的是效率，因此在共享内存的设计方面有一下几个点需要留意：

请求和响应的格式和长度如何设计才能使得内存访问效率更高。
在共享内存中如何组织请求和响应的存取形式，才能在数据安全读写的前提下保证性能。
客户端和服务端如何选择合适的时机来接收数据。

IPCItem：是IPC传递消息的基本单元，为了减少消息读写以及编解码的成本，我们采用定长的消息字段。每个IPCItem的长度被定义为缓存行的整数倍并对齐，消息中的前四个字节用于存储提交该消息的协程id，方便后续通过响应进行唤醒。 msg info 用于存储消息的元数据，包含了消息类型、长度等。 extend msg 将被具体的应用程序根据不同的用户进行定义。
数据竞争：由于共享内存会被一个以上的线程同时访问，因此我们需要设计同步互斥操作来保证数据的读写安全。同时共享内存的访问极为频繁，我们要尽可能避免数据竞争来保证读写性能。我们将请求和响应放到不同的环形缓冲区中，不同的发送方和接收方使用不同的环形缓冲区以保证单生产者单消费者的约束，消除过多的数据竞争。最后，我们使用无锁的方式实现队列，进一步提升环形缓冲区的读写性能。
co_status：我们在缓冲区中维护了一个标志位（co_status），表示对端的dispatcher协程的是否处于就绪状态，并以此为依据判断是否需要发送U-notification去唤醒对端的dispatcher协程。从而减少发送无效的用户态中断。

异步运行时 #

传统微内核中的同步IPC会导致发送端线程阻塞，从而造成一些没有依赖关系的IPC被迫以顺序的形式执行，或者强制要求多线程来实现并发。因此我们为每个进程在用户态实现了一个异步运行时，提供了协程作为任务的执行单元，用于提升用户态并发度。此外，内核中对异步系统调用的处理也被封装为协程的形式，因此在内核中也有一个与用户态类似的协程调度器，独立与线程调度器，在符合优先级要求时进行调度执行。

用户态异步运行时（异步IPC） #

初始化用户态环境，代理注册用户态中断资源，管理相关共享内存。
提供部分异步化的系统调用接口和异步IPC的接口
提供基于优先级的协程调度机制。

一个基于异步IPC的典型Call调用的基本流程如下：

// client
async ipc_call(cap, msg_info) -> Result<IPCItem> {
	item = IPCItem::new(current_cid(), msg_info);
	buffer = get_buffer_from_cap(cap);
	buffer.req_ring_buffer.write(item);
	if buffer.req_co_status == false {
		// 设置标志位并通知对端
		buffer.req_co_status = true;
		u_notification_signal(cap);
	}
	if let Some(reply) = yield_now().await {
		return Some(reply);
    }
    Return Err(());
}

// server
async ipc_recv_reply(cap) {
	buffer = get_buffer_from_cap(cap);
	loop {
		if let Some(item) = buffer.req_ring_buffer.get() {
			reply = handle_item(item);
			buffer.resp_ring_buffer.write(reply);
			if buffer.reply_co_status == false {
				buffer_reply_co_status = true;
				u_notification_signal(cap);
			}
		} else {
			// 阻塞当前协程
			buffer.req_co_status = false;
			yield_now().await;
		}
	}
}

内核态异步运行时（异步系统调用） #

提供异步系统调用的处理接口。
提供内核态向用户态发送用户态中断的能力。
提供简单的协程优先级调度器。

异步系统调用与异步IPC的主要不同之处有两点：

由于接收端是内核，发送端无法使用U-notificaiton去通知内核。
异步IPC中进程的异步调度器就是进程的执行主体，无需考虑异步任务的执行时机，而内核除了异步系统调用请求需要调度器执行，本身就有如中断、异常、任务调度等其他任务需要被执行。

对于第一点，我们只需要新增一个系统调用去用于唤醒相关的内核协程即可。而对于第二点，一个很简单的思路是每次时钟中断到来时去执行异步系统调用，然而这可能会导致空闲的CPU核心无法及时触发时钟中断而空转，因此，在不破坏原本的线程优先级调度前提下，我们使用核间中断来抢占空闲CPU核心或正在运行低优先级线程的CPU核心，更好地利用空闲CPU资源，减少响应时延。

为了避免破坏微内核中原本的优先级调度机制，我们在内核中对每个CPU核心维护了相应的执行优先级(exec_prio)，执行优先级区别于上文提到的运行时协程优先级，是由内核调度器维护的线程优先级。

内核中的任务主要分为三类：

idle_thread: 空闲CPU核心执行idle线程，此时CPU核心的执行优先级为256，属于最低的执行优先级。
内核态任务：正在处理中断、异常、系统调用等，此时CPU核心的执行优先级为0，最高优先级，不可被抢占。
用户态任务：正在执行用户态的任务，此时CPU核心的执行优先级为当前线程的优先级，可以被更高优先级线程提交的异步系统调用请求打断。

当发送端通过系统调用陷入内核去唤醒相应协程后，会检查当前线程的优先级是否可以抢占其他CPU核心，如果可以，则发送核间中断抢占该CPU核心去执行异步系统调用，当前CPU核心则返回用户态继续执行其他协程。如果没有可以被抢占的CPU核心，则在下一次时钟中断到来时执行异步系统调用请求，其伪代码如下：

fn wake_syscall_handler {
	current = get_current_thread();
	if let Some(cid) = current.async_sys_handler_cid {
		coroutine_wake(cid);
		current_exec_prio = current.tcb_prio;
		cpu_id, exec_prio = get_max_exec_prio();
		if (current_exec_prio < exec_prio) {
			// 抢占低执行优先级的核心
			mask = 1 << cpu_id;
			ipi_send_mask(mask, ASYNC_SYSCALL_HANDLE, mask);
		}
	}
}

关于异步系统调用，有两点需要注意的地方：

高频率提交系统调用会导致异步系统调用的处理十分耗时，而seL4在内核态处于屏蔽中断的状态，这在一定程度上影响了微内核的实时性，因此我们在每个请求处理完成后插入抢占点，如果有中断到来，则在处理中断后重启异步系统调用处理流程。
有两类系统调用无法转化为异步系统调用。由于异步系统调用依赖于异步运行时，因此与异步运行时初始化相关的系统调用无法被异步化。对于实时性要求较高的系统调用无法进行异步化，如get_clock()。异步运行时会根据系统调用的种类来选择合适的处理方式。