HardBirch

百度系统部面试总结

时间:10-04-19 栏目:系统技术篇 作者:鲁智森也有文化 评论:0 点击: 2,120 次

     

     同学去百度被问到的一些面试题的整理,因为是内推并没有参加笔试。以下的面试问题仅仅针对内核,如果你是做应用的,你可能会觉得一头雾水(话说我也是刚开始看内核来着)。另外,相信我,同学被问到的问题应该算是比较深入了,因为我毕业那年找工作虽然没有去百度面试过,但是有不少同学去过,他们被问到的问题大部分停留在应用层和算法部分,所以你不一定会被问到这样的问题,但如果你是做内核的,那么你必须要知道这些东西。

 

以下代码内容就纯属转载了,大家也可以在linux内核中找到源码,能把这些代码都看过一遍的人我想应该算牛人了吧,反正我没看~呵呵!

  

一:永久内存映射

永久内存映射在内核的接口为:kmap()/kunmap().在详细分析代码之前,有必须弄懂几个全局变量的含义:

PKMAP_BASE:永久映射空间的起始地址。永久映射空间为4M。所以它最多能映射4M/4K=1024个页面。

pkmap_page_table:永久映射空间对应的页目录。我们来看一下它的初始化:

pkmap_page_table = pte_offset_kernel(pmd_offset(pgd_offset_k

              (PKMAP_BASE), PKMAP_BASE), PKMAP_BASE);

              实际上它就是PKMAP_BASE所在的PTE

LAST_PKMAP:永久映射空间所能映射的页面数。在没有开启PAE的情况下被定义为1024

highmem_start_page:高端内存的起始页面

pkmap_count[PKMAP]:每一项用来对应映射区域的引用计数。关于引用计数,有以下几种情况:

                   0时:说明映射区域可用。为1时:映射区域不可用,因为自从它最后一次使用以来。TLB还没有将它刷新

              N时,有N-1个对象正在使用这个页面

last_pkmap_nr:在建立永久映射的时候,最后使用的序号

代码如下:

void *kmap(struct page *page)

{

     //可能引起睡眠。在永久映射区没有空闲地址的时候

     might_sleep();

     //如果不是高端页面。那它在直接映射空间已经映射好了,直接计算即可

     if (page < highmem_start_page)

         return page_address(page);

     //如果是高端页面。即在永久映射区为其分配地址

     return kmap_high(page);

}

转到kmap_high():

void fastcall *kmap_high(struct page *page)

{

     unsigned long vaddr;

     spin_lock(&kmap_lock);

     //取页面地址

     vaddr = (unsigned long)page_address(page);

     //如果页面还没有映射到线性地址,为它建立好映射

     if (!vaddr)

         vaddr = map_new_virtual(page);

     //有一个引用了,计数加1

     pkmap_count[PKMAP_NR(vaddr)]++;

     //如果计数小于2,这种情况是无效的。

     if (pkmap_count[PKMAP_NR(vaddr)] < 2)

         BUG();

     spin_unlock(&kmap_lock);

     return (void*) vaddr;

}

map_new_virtual()用于将一个page映射到永久映射区域。它的实现如下:

static inline unsigned long map_new_virtual(struct page *page)

{

     unsigned long vaddr;

     int count;

 

start:

     count = LAST_PKMAP;

     for (;;) {

         //last_pkmap_nr开始搜索。大于LAST_PKMAP时,又将它从0开始

         //其中LAST_PKMAP_MASK被定义为:(LAST_PKMAP-1)

         last_pkmap_nr = (last_pkmap_nr + 1) & LAST_PKMAP_MASK;

         //如果last_pkmap_nr等于0,也就是从头开始了

if (!last_pkmap_nr) {

     //扫描所有计数为1的项,将它置为零。如果还有映射到页面。断开它的映射关系

              flush_all_zero_pkmaps();

              count = LAST_PKMAP;

         }

         //如果计数为0,可用,就用它了,跳出循环

if (!pkmap_count[last_pkmap_nr])

              break;   /* Found a usable entry */

         if (--count)

              continue;

//遍历了整个区都无可用区间,睡眠

         {

              DECLARE_WAITQUEUE(wait, current);

 

              __set_current_state(TASK_UNINTERRUPTIBLE);

              add_wait_queue(&pkmap_map_wait, &wait);

              spin_unlock(&kmap_lock);

              schedule();

              remove_wait_queue(&pkmap_map_wait, &wait);

              spin_lock(&kmap_lock);

 

              /* Somebody else might have mapped it while we slept */

              //可能在睡眠的时候,其它进程已经映射好了,

              if (page_address(page))

                   return (unsigned long)page_address(page);

 

              //重新开始

              goto start;

         }

     }

     // #define PKMAP_ADDR(nr)  (PKMAP_BASE + ((nr) << PAGE_SHIFT))

     //将序号转化为线性地址

     vaddr = PKMAP_ADDR(last_pkmap_nr);

     //将线性地址映射到page

     set_pte(&(pkmap_page_table[last_pkmap_nr]), mk_pte(page, kmap_prot));

     //将其引用计数置1

     pkmap_count[last_pkmap_nr] = 1;

     //更新page的线性地址

     set_page_address(page, (void *)vaddr);

 

     return vaddr;

}

Kunmap()的实现如下:

void kunmap(struct page *page)

{

     //不能在中断中

     if (in_interrupt())

         BUG();

     //如果不是高端页面,直接返回

     if (page < highmem_start_page)

         return;

     //清除掉映射关系

     kunmap_high(page);

}

转入kunmap_high():

void fastcall kunmap_high(struct page *page)

{

     unsigned long vaddr;

     unsigned long nr;

     int need_wakeup;

 

     spin_lock(&kmap_lock);

     //取得页面的虚拟地址

     vaddr = (unsigned long)page_address(page);

     if (!vaddr)

         BUG();

     //将地址转换为序号

     // #define PKMAP_NR(virt)  ((virt-PKMAP_BASE) >> PAGE_SHIFT)

     nr = PKMAP_NR(vaddr);

     need_wakeup = 0;

     //计算引用计数

     switch (--pkmap_count[nr]) {

     case 0:

         BUG();

     case 1:

         //如果只有一个引用了,说明这页面是空闲的。看看是否有进程在等待

         //因为TLB刷新之后,会将其减1

         need_wakeup = waitqueue_active(&pkmap_map_wait);

     }

     spin_unlock(&kmap_lock);

 

//唤醒等待的进程

     if (need_wakeup)

         wake_up(&pkmap_map_wait);

}

二:临时内存映射

临时内存映射在内核中的接口为:kmap_atomic()/kunmap_atomic()。它映射的地址是从FIXADDR_STARTFIXADDR_TOP的区域。其中,每个cpu都在里面占用了一段空间。

在内核中,enum fixed_addresses表示各种临时映射所占的序号。结构如下:

enum fixed_addresses {

     FIX_HOLE,

     FIX_VSYSCALL,

#ifdef CONFIG_X86_LOCAL_APIC

     FIX_APIC_BASE,     /* local (CPU) APIC) -- required for SMP or not */

#else

     FIX_VSTACK_HOLE_1,

#endif

#ifdef CONFIG_X86_IO_APIC

     FIX_IO_APIC_BASE_0,

     FIX_IO_APIC_BASE_END = FIX_IO_APIC_BASE_0 + MAX_IO_APICS-1,

#endif

#ifdef CONFIG_X86_VISWS_APIC

     FIX_CO_CPU,   /* Cobalt timer */

     FIX_CO_APIC,  /* Cobalt APIC Redirection Table */

     FIX_LI_PCIA,  /* Lithium PCI Bridge A */

     FIX_LI_PCIB,  /* Lithium PCI Bridge B */

#endif

     FIX_IDT,

     FIX_GDT_1,

     FIX_GDT_0,

     FIX_TSS_3,

     FIX_TSS_2,

     FIX_TSS_1,

     FIX_TSS_0,

     FIX_ENTRY_TRAMPOLINE_1,

     FIX_ENTRY_TRAMPOLINE_0,

#ifdef CONFIG_X86_CYCLONE_TIMER

     FIX_CYCLONE_TIMER, /*cyclone timer register*/

     FIX_VSTACK_HOLE_2,

#endif

     FIX_KMAP_BEGIN,    /* reserved pte's for temporary kernel mappings */

     FIX_KMAP_END = FIX_KMAP_BEGIN+(KM_TYPE_NR*NR_CPUS)-1,

#ifdef CONFIG_ACPI_BOOT

     FIX_ACPI_BEGIN,

     FIX_ACPI_END = FIX_ACPI_BEGIN + FIX_ACPI_PAGES - 1,

#endif

#ifdef CONFIG_PCI_MMCONFIG

     FIX_PCIE_MCFG,

#endif

     __end_of_permanent_fixed_addresses,

     /* temporary boot-time mappings, used before ioremap() is functional */

#define NR_FIX_BTMAPS  16

     FIX_BTMAP_END = __end_of_permanent_fixed_addresses,

     FIX_BTMAP_BEGIN = FIX_BTMAP_END + NR_FIX_BTMAPS - 1,

     FIX_WP_TEST,

     __end_of_fixed_addresses

}

每一段序号都有自己的用途,例如APIC用,IDT用。FIX_KMAP_BEGINFIX_KMAP_END是分配给模块或者做做临时用途使用的。内核这样分配是为了保证同一个区不能有两上映射关系。我们在后面可以看到,如果一个区已经映射到了一个物理页面。如果再在这个区上建立映射关系,就会把它以前的映射覆盖掉。所以,内核应该根据具体的用途选择特定的序号,以免产生不可预料的错误。同时使用完临时映射之后应该立即释放当前的映射,这也是个良好的习惯.

FIX_KMAP_END的大小被定义成:FIX_KMAP_BEGIN+(KM_TYPE_NR*NR_CPUS)-1。也就是FIX_KMAP_BEGINFIX_KMAP_END的大小是KM_TYPE_NR*NR_CPUS.

KM_TYPE_NR的定义如下:

enum km_type {

     /*

      * IMPORTANT: don't move these 3 entries, be wary when adding entries,

      * the 4G/4G virtual stack must be THREAD_SIZE aligned on each cpu.

      */

     KM_BOUNCE_READ,

     KM_VSTACK_BASE,

     KM_VSTACK_TOP = KM_VSTACK_BASE + STACK_PAGE_COUNT-1,

 

     KM_LDT_PAGE15,

     KM_LDT_PAGE0 = KM_LDT_PAGE15 + 16-1,

     KM_USER_COPY,

     KM_VSTACK_HOLE,

     KM_SKB_SUNRPC_DATA,

     KM_SKB_DATA_SOFTIRQ,

     KM_USER0,

     KM_USER1,

     KM_BIO_SRC_IRQ,

     KM_BIO_DST_IRQ,

     KM_PTE0,

     KM_PTE1,

     KM_IRQ0,

     KM_IRQ1,

     KM_SOFTIRQ0,

     KM_SOFTIRQ1,

     KM_CRASHDUMP,

     KM_UNUSED,

     KM_TYPE_NR

}

smp系统中,每个CPU都有这样的一段映射区域

kmap_pteFIX_KMAP_BEGIN项所对应的页表项.它的初始化如下:

#define kmap_get_fixmap_pte(vaddr)                      /

     pte_offset_kernel(pmd_offset(pgd_offset_k(vaddr), (vaddr)), (vaddr))

 

void __init kmap_init(void)

{

     kmap_pte = kmap_get_fixmap_pte(__fix_to_virt(FIX_KMAP_BEGIN));

}

#define __fix_to_virt(x)    (FIXADDR_TOP - ((x) << PAGE_SHIFT))

了解上述关系之后,可以看具体的代码了:

void *kmap_atomic(struct page *page, enum km_type type)

{

     enum fixed_addresses idx;

     unsigned long vaddr;

 

     //如果页面不是高端内存

     inc_preempt_count();

     if (page < highmem_start_page)

         return page_address(page);

     //smp中所对应的序号

     idx = type + KM_TYPE_NR*smp_processor_id();

     //在映射断中求取序号所在的虚拟地址

     vaddr = __fix_to_virt(FIX_KMAP_BEGIN + idx);

#ifdef CONFIG_DEBUG_HIGHMEM

     if (!pte_none(*(kmap_pte-idx)))

         BUG();

#endif

     //根据页面属性建立不同的页面项.并根据FIX_KMAP_BEGIN的页表项,求出序号所在的页表项

     if (PageReserved(page))

         set_pte(kmap_pte-idx, mk_pte(page, kmap_prot_nocache));

     else

         set_pte(kmap_pte-idx, mk_pte(page, kmap_prot));

     //TLB中刷新这个地址

     __flush_tlb_one(vaddr);

 

     return (void*) vaddr;

}

我们在这个过程看中,并没有去判断一个区域有没有被映射。但这样也有一个好处,就是不会造成睡眠,因为它总有一个区域可供其映射。与永久内核映射相比,速度显得稍微要快一点。

临时内核映射的断开接口为:kunmap_atomic()

void kunmap_atomic(void *kvaddr, enum km_type type)

{

//调试用,忽略

#ifdef CONFIG_DEBUG_HIGHMEM

     unsigned long vaddr = (unsigned long) kvaddr & PAGE_MASK;

     enum fixed_addresses idx = type + KM_TYPE_NR*smp_processor_id();

 

     if (vaddr < FIXADDR_START) { // FIXME

         dec_preempt_count();

         preempt_check_resched();

         return;

     }

 

     if (vaddr != __fix_to_virt(FIX_KMAP_BEGIN+idx))

         BUG();

 

     /*

      * force other mappings to Oops if they'll try to access

      * this pte without first remap it

      */

     pte_clear(kmap_pte-idx);

     __flush_tlb_one(vaddr);

#endif

 

     dec_preempt_count();

     preempt_check_resched();

}

 

 

2.描述一下linux内核是如何处理异常的。

   这又是一个非常大的发挥式题目,你可以两三句带过,也可以讲上两三个小时(如果你够刚的话~~),在写这篇blog之前我也很踌躇,害怕自己写出来的东西实在太肤浅,不够别人推敲的,所以我特意去把《Understanding.the.Linux.Kernel.2rd.Edition》看了一下,等我在准备写的时候发现还是有理不清的思绪。想想还是这么说吧,我在这里写的东西都是点到即止(毕竟我没有看过内核代码,不敢充高手),如果真的想弄得很明白,建议结合这本书去读一下linux内核的代码。否则你会发现,读多少次都会很快的忘记。
   还是我先写引子吧:Intel官方资料,同步中断称为异常(exception),异步中断被称为中断(interrupt)。中断可分为可屏蔽中断(Maskable interrupt)和非屏蔽中断(Nomaskable interrupt)。异常可分为故障(fault)、陷阱(trap)、终止(abort)三类。另外还有一个编程者异常。
   每个中断和异常是由0~255之间的一个数来标识,Intel把这个8位无符号整数叫做一个向量。不可屏蔽中断的向量和异常的向量是固定的,而可屏蔽中断的向量可以通过对中断控制器的编程来更改。Linux中利用了下列向量:
   1.从0~31的向量对应于异常和不可屏蔽中断。
   2.从32~47的向量被分配给可屏蔽中断,即由IRQ引起的中断
   3.剩余的从48~255的向量用来标识软中断。Linux只用了其中的一个,即128或0x80向量,用来实现系统调用。当用户态下的进程执行一跳int 0x80汇编指令时,cpu切换到内核态,并开始执行system_call()内核函数。
   
    各个异常对应的异常处理程序及对应的信号表我就不贴了,大家可以在各种介绍内核的书中读到。
    这里先提一下中断描述附表(IDT),它与每一个中断或异常向量相联系,那么它自然就是有256项。按照Inetl官方资料IDT包含了三种类型的描述符:
    1.任务门(Task gate):包含了一个进程的TSS段选择符(sgment selector),当中断信号发生时,它被用来取代当前进程的那个TSS段选择符。Linux没有使用任务门。
    2.中断门(Interrupt gate):中断门包含了段选择符和一个中断或异常处理程序的段内偏移量。当控制器转移到一个适当的段时,处理器清IF标志,从而关闭接下来会发生的可屏蔽中断。
    3.陷阱门(Trap gate):与中断门相似,除非把控制权传递到一个适当的段,否则处理器不修改IF标志。
   而在Linux中按如下分类:
    1.中断门(Interrupt gate):用户态的进程不能访问的Intel的中断门(门的DPL域为0)。所有的中断处理程序都由中断门激活,并全部限制在内核态。
    2.系统门(System gate):用户态的进程可以访问的Inetl的陷阱门(们的DPL域为3),通过系统门来激活四个Linux异常处理程序,它们的向量是3,4,5及128,因此,在用户态下,可以发布int3、into、bound及Int 0x80四条汇编指令。
    3.陷阱门(Trap gate):用户态的进程不能访问Intel的陷阱门(门的DPL域为0)。除了前一段所描述的四个Linux异常处理程序。其他所有的异常处理程序都通过陷阱门来激活。
   
  异常处理:Linux利用异常处理来达到两个目的
    1.向进程发一个信号以通报一个反常情况。
    2.处理请求分页。
  异常处理程序有一个标准的结构,由以下三部分组成:
     1.在内核堆栈保存大多数寄存器的内容(由汇编实现)
     2.用C函数处理异常。
     3.通过ret_from_exception()函数从异常处理程序退出。
  每一个异常处理程序开始于下列的汇编指令:
     handler_name:
           pushl   $0
           pushl   $do_handler_name
           jmp  error_code
     当异常发生时,如果控制单元没有自动把一个硬件错误代码插入到栈中,相应的汇编语言片段会包含一条pushl $0指令,在栈中垫上一个空值,然后,把c函数的地址压栈,它的名字由异常处理程序名与do_前缀组成。
     标号为error_code的汇编语言片段对所有的异常处理程序都是相同的(除了“设备不可用”这一异常),这段代码执行以下步骤:
     1.把高级c函数科恩那个用到的寄存器保存在栈中。
     2.产生一条cld指令来清eflag的方向标志DF,一确保调用字符串指令时会自动增加edi和esi寄存器的值。
     3.把栈中位于esp+36处的硬错误码拷贝到eax中,给栈中同一位置存上值-1,这个值用来把0x80异常与其他异常隔离开。
     4.do_handler_name()这个c函数的地址保存在栈中的esp+32位置,把这个地址装到ecx寄存器中,然后;在站的这个位置写入es的值。
     5.把内核数据段选择符装进ds和es寄存器,然后把ebx寄存器的值设置为当前进程描述符的地址。
     6.把要传给c函数的参数保存在栈中,也就是异常硬错误码和栈中某个位置的地址,在这个位置上保存了用户态寄存器的内容。
     7.调用这个c函数,它的地址现在存在ecx中   
     执行了最后一步后,被调用的函数将在栈的顶部找到:
      1.返回地址(即c函数结束后将执行的指令地址)
      2.所保存的用户态寄存器站地址
      3.硬件错误码
   从异常处理程序返回:
      当执行异常处理的c函数终止时,控制权将被转移到下列汇编语言片段:
                       addl   $8,   %esp
                       jmp    ret_from_exception
      这段代码从栈中弹出用户态下寄存器的值和硬错误码,然后执行一个jmp指令跳转到ret_from_exception()函数。
ret_from_exception函数还有很多要说的东西,留待下次blog的时候在说一说!

 

 

   1.高端内存在线性地址中如何被映射,给出永久映射代码的例子。
    这个问题我想大部分人回答出来个大概应该不成问题,但是给出具体的代码例子,我相信就并不轻松了。
    首先由我开个头:内核可以访问所有的物理页面,也就是说内核页面的映射应该囊括所有的物理内存区,而线性地址映射的情况是内核映射1G大小的空间,另外3G大小的空间为用户地址空间。如果物理内存的大小大于1G内核如何映射呢?
    实际上,“内核映射空间”也达不到 1G, 还得留点线性空间给“内核动态映射空间”。因此,Linux 规定“内核直接映射空间” 最多映射 896M 物理内存。那么如何完成映射呢,大家可以去看linux内核的书,我的描述比较浅薄,所以部分转载,部分自己写:(强调一下,以下内容大部分为转载)
    对于高端内存,可以通过 alloc_page() 或者其它函数获得对应的 page,但是要想访问实际物理内存,还得把 page 转为线性地址才行,也就是说,我们需要为高端内存对应的 page 找一个线性空间,这个过程称为高端内存映射。
    线性地址空间 PAGE_OFFSET + 896M 至4G的最后128M线性地址  <==映射==>  896M以上的物理页框,非直接映射。有3种方法:非连续内存区映射,永久内核映射,临时内核映射(固定映射)
   从 PAGE_OFFSET开始的线性地址区域为:
   PAGE_OFFSET(3G)|物理内存映射 --8M-- vmallot区 --4K-- vmallot区 --8K-- 永久内核映射(4M)--临时内核映射(固定映射4M)|4G 
1、映射到“内核动态映射空间”
这种方式很简单,因为通过 vmalloc() ,在”内核动态映射空间“申请内存的时候,就可能从高端内存获得页面(参看 vmalloc 的实现),因此说高端内存有可能映射到”内核动态映射空间“ 中。

2、永久内核映射
如果是通过 alloc_page() 获得了高端内存对应的 page,如何给它找个线性空间?
内核专门为此留出一块线性空间,从 PKMAP_BASE FIXADDR_START ,用于映射高端内存。在 2.4 内核上,这个地址范围是 4G-8M 4G-4M 之间。这个空间起叫“内核永久映射空间”或者“永久内核映射空间”

这个空间和其它空间使用同样的页目录表,对于内核来说,就是 swapper_pg_dir,对普通进程来说,通过 CR3 寄存器指向。

通常情况下,这个空间是 4M 大小,因此仅仅需要一个页表即可,内核通过来 pkmap_page_table 寻找这个页表。

通过 kmap(), 可以把一个 page 映射到这个空间来

由于这个空间是 4M 大小,最多能同时映射 1024 page。因此,对于不使用的的 page,及应该时从这个空间释放掉(也就是解除映射关系),通过 kunmap() ,可以把一个 page 对应的线性地址从这个空间释放出来。

3、临时映射

内核在 FIXADDR_START FIXADDR_TOP 之间保留了一些线性空间用于特殊需求。这个空间称为“固定映射空间”

在这个空间中,有一部分用于高端内存的临时映射。

这块空间具有如下特点:

1、  每个 CPU 占用一块空间

2、  在每个 CPU 占用的那块空间中,又分为多个小空间,每个小空间大小是 1 page,每个小空间用于一个目的,这些目的定义在 kmap_types.h 中的 km_type 中。

 当要进行一次临时映射的时候,需要指定映射的目的,根据映射目的,可以找到对应的小空间,然后把这个空间的地址作为映射地址。这意味着一次临时映射会导致以前的映射被覆盖。

这里是总结性的描述,下一篇blog是比较详细的代码~

 

  

声明: 本文由( 鲁智森也有文化 )原创编译,转载请保留链接: 百度系统部面试总结

百度系统部面试总结:等您坐沙发呢!

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐