浅析trapframe与context的原理与区别

TRAPFRAME与CONTEXT的区别

在ucore操作系统中,trapframecontext是很容易混淆的两个结构,他们都会出现在线程的调度中。实际上,结构体trapframe用于切换优先级、页表目录等,而context则是用于轻量级的上下文切换。从技术上来看,两者的区别在于context仅仅能够切换普通寄存器,而trapframe可以切换包括普通寄存器、段寄存器以及少量的控制寄存器。

*在看后续内容之前,你需要提前了解汇编语言、栈、C函数调用的实现。

TRAPFRAME结构体

trapframe定义如下——

struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

这个结构体中,依次储存了——

  • 目标寄存器
  • gs, fs, es, ds 段寄存器
  • trap_no, err 用于储存中断信息
  • eip, cs, eflags 用于储存陷阱(trap)返回后的目的地址
  • esp, ss 在权限发生变化时,用于指示新的栈的位置

有两个地方使用了trapframe,一个是中断调用,另一个是进程切换。两者对于trapframe的使用有相似之处,但也并不完全相同。

中断调用中使用TRAPFRAME

trapframe在中断中,在前期负责中断信息的储存,后期负责中断的恢复。同时,trapframe结构体是位于栈中的,其生成和使用都是通过栈的pushpop命令实现的,这将在后面详细解释。

中断发生时,下面代码,将一系列信息压到栈中。这些信息在后续的,trap(struct trapframe *tf)函数中,被对齐到了tf结构体中。

.globl __alltraps                                                                                                                  
__alltraps:                                                                                                                        
    # push registers to build a trap frame                                                                                         
    # therefore make the stack look like a struct trapframe                                                                        
    pushl %ds                                                                                                                      
    pushl %es                                                                                                                      
    pushl %fs                                                                                                                      
    pushl %gs                                                                                                                      
    pushal                                                                                                                         
                                                                                                                                   
    # load GD_KDATA into %ds and %es to set up data segments for kernel
    movl GD_KDATA, %eax     movw %ax, %ds     movw %ax, %es      # push %esp to pass a pointer to the trapframe as an argument to trap()     pushl %esp      # call trap(tf), where tf=%esp     call trap</code></pre> <!-- /wp:code -->  <!-- wp:paragraph --> 中断处理完成后,需要恢复原来的运行状态,此时,按顺序将之前push的所有信息pop出来即可。 <!-- /wp:paragraph -->  <!-- wp:code --> <pre class="wp-block-code"><code>    # call trap(tf), where tf=%esp     call trap      # pop the pushed stack pointer     popl %esp      # return falls through to trapret... .globl __trapret __trapret:     # restore registers from stack     popal      # restore %ds, %es, %fs and %gs     popl %gs     popl %fs     popl %es     popl %ds      # get rid of the trap number and error code     addl0x8, %esp
    iret

当然,倘若读者认为trapframe仅仅像这样中规中矩的实现信息的保存,那就太小看他了。我们发现,在调用call trap之后,有一句popl %esp,而后续恢复的信息完全是基于该%esp进行定位的,那么在中断处理内存中,如果我们强行修改%esp成为我们希望接下来运行的代码段的trap描述,那么经过__trapret代码恢复trapframe后,你就可以让程序跳转到任何你希望的地方。

比如下面代码就实现了内核态到用户态的切换。

    if (tf->tf_cs == KERNEL_CS) {                                                                                              
        cprintf("T_SWITH_TOU\n");                                                                                              
        userframe =  *tf;                                                                                                      
        userframe.tf_cs = USER_CS;                                                                                             
        userframe.tf_ds = USER_DS;                                                                                             
        userframe.tf_es = USER_DS;                                                                                             
        userframe.tf_ss = USER_DS;                                                                                             
        //userframe.tf_fs = USER_DS;                                                                                           
        userframe.tf_eflags |= FL_IOPL_MASK;                                                                                   
        userframe.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8;                                                        
        *((uint32_t *)tf - 1) = (uint32_t)&userframe;                                                                     
    } 

其中*((uint32_t *)tf - 1)这个位置的值就是之后popl %esp恢复的%esp的值。

进程切换中CONTEXT的作用

context的结构体定义如下,可以看到,其中储存了所有的用户寄存器的值。

// Saved registers for kernel context switches.                                                                                    
// Don't need to save all the %fs etc. segment registers,                                                                          
// because they are constant across kernel contexts.                                                                               
// Save all the regular registers so we don't need to care                                                                         
// which are caller save, but not the return register %eax.                                                                        
// (Not saving %eax just simplifies the switching code.)                                                                           
// The layout of context must match code in switch.S.                                                                              
struct context {                                                                                                                   
    uint32_t eip;                                                                                                                  
    uint32_t esp;                                                                                                                  
    uint32_t ebx;                                                                                                                  
    uint32_t ecx;                                                                                                                  
    uint32_t edx;                                                                                                                  
    uint32_t esi;                                                                                                                  
    uint32_t edi;                                                                                                                  
    uint32_t ebp;                                                                                                                  
};                     

context结构体干的事情也很简单,可以用switch_to函数囊括,即保存一系列寄存器,并恢复一系列寄存器。在C++中,switch_to是拥有两个context结构体为参数的函数switch_to(&(prev->context), &(next->context)); ,其实现如下——

switch_to:                      # switch_to(from, to)

    # save from's registers
    movl 4(%esp), %eax          # eax points to from
    popl 0(%eax)                # save eip !popl
    movl %esp, 4(%eax)          # save esp::context of from
    movl %ebx, 8(%eax)          # save ebx::context of from
    movl %ecx, 12(%eax)         # save ecx::context of from
    movl %edx, 16(%eax)         # save edx::context of from
    movl %esi, 20(%eax)         # save esi::context of from
    movl %edi, 24(%eax)         # save edi::context of from
    movl %ebp, 28(%eax)         # save ebp::context of from

    # restore to's registers
    movl 4(%esp), %eax          # not 8(%esp): popped return address already
                                # eax now points to to
    movl 28(%eax), %ebp         # restore ebp::context of to
    movl 24(%eax), %edi         # restore edi::context of to
    movl 20(%eax), %esi         # restore esi::context of to
    movl 16(%eax), %edx         # restore edx::context of to
    movl 12(%eax), %ecx         # restore ecx::context of to
    movl 8(%eax), %ebx          # restore ebx::context of to
    movl 4(%eax), %esp          # restore esp::context of to

    pushl 0(%eax)               # push eip

    ret

进程切换中TRAPFRAME的作用

那是不是进程的切换就可以直接用switch_to函数呢?答案是否定的,因为switch_to仅仅保存、恢复了普通寄存器,无法实现优先级跳转、段寄存器修改等等。这时,就要借助trapframe了。

由于switch_to函数跳转后,将调到context.eip位置。而这个跳转我们没法完全实现进程切换,所以我们可以将其设置为一个触发二级跳转的函数,forkret

proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);

其中,forkret定义如下(current是当前进程,也就是进程切换的目标进程),forkret不同于switch_to,它尝试使用trapframe作为进程切换的手段,而相比于contexttrapframe的功能就强大多了。

static void
forkret(void) {
    forkrets(current->tf);
}

而forkrets定义如下——

.globl __trapret
__trapret:
    # restore registers from stack
    popal

    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds

    # get rid of the trap number and error code
    addl $0x8, %esp
    iret

.globl forkrets
forkrets:
    # set stack to this new process's trapframe
    movl 4(%esp), %esp
    jmp __trapret

现在,又回到了中断恢复的那一段代码,而其中的逻辑也完全相同。最终,进程跳转目标进程的入口,而该入口的地址,被存放在proc->tf中。下面是kernel_threadtrapframe初始化代码,也能佐证最终调用函数入口fn被储存在了eip中。

// kernel_thread - create a kernel thread using "fn" function                                                                      
 // NOTE: the contents of temp trapframe tf will be copied to                                                                       
 //       proc->tf in do_fork-->copy_thread function                                                                                
 int                                                                                                                                
 kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {                                                                
     struct trapframe tf;                                                                                                           
     memset(&tf, 0, sizeof(struct trapframe));                                                                                      
     tf.tf_cs = KERNEL_CS;                                                                                                          
     tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;                                                                                    
     tf.tf_regs.reg_ebx = (uint32_t)fn;                                                                                             
     tf.tf_regs.reg_edx = (uint32_t)arg;                                                                                            
     tf.tf_eip = (uint32_t)kernel_thread_entry;                                                                                     
     return do_fork(clone_flags | CLONE_VM, 0, &tf);                                                                                
 }                                                                                                                                  

浅析文本摘要算法(Document Summarization)

概述

文本摘要算法,指的是在一篇文章中,摘要出核心观点的算法。主流的文本摘要算法生成一篇文章的摘要,摘要长度在3~4句话左右。

历史

在深度学习算法出现之前,人们使用了贪心算法、图算法来研究文本摘要。同时,为了衡量一段生成的摘要是否和标准摘要(gold summary)相似,学术界提出了一系列标准,这些标准现在广泛用于文本摘要算法的模型评价,其中最为常用的就是ROUGE – A Package for Automatic Evaluation of Summarieszz中提到的ROUGE-x系列算法。

深度学习提出后,LSTM/GRU作为摘要生成的强有力工具,一举打破传统算法的效果。最为主流的摘要生成模型是基于抽取式和生成式的,这两种模型将在后面详述。

随着深度学习的发展,很多其他算法也被引入。如一些文章使用强化学习,直接尝试训练一个能够获得最高ROUGE得分的模型。一些文章借助机器视觉方向的研究,优化模型结构。也有文章训练模型,判断句子相对于文章的重要性,进而间接实现摘要提取。

抽取式和生成式文本摘要

既然是摘要,那么显然,摘要中很大一部分都应该是原文中出现过的词语。同时,基于语法的考虑,也需要引入一些没有在原文中出现的词。

这时,就引出了文本摘要算法的两大学派—— 抽取式(extractive)和生成式(abstractive)。

  • extractive算法希望直接从文本中,抽出若干词语,连成一句话。词汇的抽取通常使用循环神经网络,配合注意力机制。得到“下一个词”可能是谁的概率分布。
  • abstractive算法希望从词汇表中,直接选出“下一个词”。

不论是abstractive的文本摘要,还是extractive的文本摘要,模型都由两个部分构成的,即一个编码器(encoder)和一个解码器(decoder)。

  • 对于编码器来说,通常都是将输入文本导入一个循环神经网络,生成出一个上下文特征向量c
  • 对于解码器来说,通常也是使用一个循环神经网络。以编码器生成的表征原文的上下文特征向量c,和之前生成的词汇{y_1, y_2, \dots, y_t},生成出摘要的下一个词y_t

数据集

当前研究人员多使用CNN/DailyMail作为数据集,在该数据集中,每一组数据是一个新闻稿,平均每篇文章39句话。同时还有一个“多句”的摘要。

著名论文

Get To The Point: Summarization with Pointer-Generator Networks

这篇文章提出了一个Pointer-Generator模型,既可以通过Pointer拷贝原文的文字,也可以通过Generator生成不存在原文中的文本。这两个模型通过一个开关p_{gen}进行选择——

P(w) = p_{gen} P_{vocab}(w) + (1-p_{gen})\sum_{i:w_i=w} a_i^t

其中P_{vocab}表示从词汇表中选择一个单词的概率分布,而a_i则是从原文选择第i个词汇的概率分布。

在此基础上,本文还提出了一种称之为覆盖率机制(coverage mechanism)的方式,用以解决抽取式摘要中最容易出现的内容重复的问题。

SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents

这篇文章核心目标是仅仅是在“句子级别”进行摘要,即从原文中选择若干适合作为摘要的句子。该文章使用两层GRU,依次在“词语”级别和“句子”级别总结信息,最终获得一个可以表征全局性质的向量d。接着,再参考句子级别的特征向量s_i、全局特征向量d、以及RNN的隐状态h_i,生成对于句子的评分。

Ranking Sentences for Extractive Summarization with Reinforcement Learning

这篇文章的核心目标是给一篇文章的句子按照与主题的相关度进行排序,文章指出,在之前的方法中,通常是训练模型,使得对于每一个句子的估价尽量靠近一个指定的ground-true。但提升对于ground-true的近似并不一定能够提高模型的ROUGE评分。因此,文章提出使用强化学习的方式,直接学习句子的label,进一步最大化ROUGE评分(注意,这里ROUGE评价指标是不可导的,因此才需要用到强化学习)。

Neural Document Summarization by Jointly Learning to Score and Select Sentences

这篇文章仍然是句子级别摘要的算法,其思想借鉴了MMR算法,在MMR算法中,借助一个建立在语句集合中的评分函数r(S),迭代选择能够最大化加入后r(S')值的句子。即

g(S_i) = r(S_{t-1} \cap {S_i}) - r(S_{t-1})

g(S_i)可以看做在选择了S_{t-1}后,第i篇文章S_i的评分。使用神经网络结构去学习g(S_i)即可实现——能够参考之前选取句子集合信息的语句选择算法。

BanditSum: Extractive Summarization as a Contextual Bandit

这篇文章也是借助强化学习尝试拟合文本的ROUGE得分,并且提出了新的结构用于防止摘要倾向于前面的句子。

Bottom-Up Abstractive Summarization

这篇文章与Pointer-Generator相似,不过为了解决前文中文本拷贝倾向于拷贝整句话的bug。在输入给Pointer-Generator模型之前,先给输入的文本加了一个mask,过滤掉其中一部分,这样就导致文本不再倾向于拷贝连续的内容。

DeepChannel: Salience Estimation by Contrastive Learning for Extractive Document Summarization

这篇文章训练模型,拟合P(D|S),即给定摘要S,能够恢复原文D的概率。而函数P(D|S)的训练,可以借助文章D,摘要S,一句不重要的话S_2这三部分进行训练。生成P(D|S)后,再使用贪心算法构造摘要集合。

一句话解析最大边缘相关性算法(MMR, Maximal Marginal Relevance)

随着网络资源的丰富,找到和询问(query)最相关的一系列文本成为了学者们研究的问题。

之前的做法通常是直接计算逐个候选文本与询问的相关度。将前K大值对应的文档作为“最相关文档”输出出来。但是这种做法适用于那些候选文本集合较小,且只有少量文本与询问存在关联的情况。

但实际上,我们还有另一种场景,以搜索引擎为首的这类环境中,潜在的相关文档非常多,我们需要非常高的召回率(recall),并且尽量降低结果的冗余性(redundance)。在这种情况下,MMR就有用武之地了。

实际上MMR的算法核心思想可以用一句话解释——

A document has high mariginal relevance if it is both relevant to the query and contains minimal similarity to previously selected documents.

一个文章拥有高边缘相关性(MMR)当且仅当它与询问相关性高,而且与之前已经选出来的文章集合相关性低。

而使用公式化的表达如下——

MMR \overset{def}{=}  \underset{D_i \in R \backslash S}{Arg max} \left[ \lambda (Sim_1(D_i, Q) - (1-\lambda) \underset{D_j \in S}{max} Sim(D_i, D_j) \right]

其中,Q表示询问,D_i表示文档,S表示选择出来的相关文档集合,Sim表示任意一种文档相关性计算函数。

以上就是MMR的解释,MMR在文档摘要方面有很多应用。想要更细了解,可以参考文献 The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries