朴泊斋

当对手知道你的hash函数的代码实现的时候，他可以设计一个特定的input，让你的hash产生大量的collide。为了解决这个问题，可以用到universal hashing的方法。

在算法开始时取hash函数，随机在已有的hash function family中取一个hash函数，当然这个family是需要满足universal hashing的条件的，然后就使用这个hash函数来做insert,query,delete的操作。

 

Proof of Fermat's little theorem(From Algorithms by Dasgupta, C. H. Papadimitriou, and U. V. Vazirani)

用Fermat's little theorem来判断primality

1. 素数都是满足Fermat's little theorem的

2. 满足Fermat's little theorem的不一定是素数

    （1）某些合数只在取特殊的a的时候，满足Fermat's little theorem，如341，这些合数可以通过random取a来做多次判断来剔除

    （2）某些合数就是满足Fermat's little theorem的，这被称为Carmichael Number，最小的数是561，这些数没法剔除，但是很少很少，遇到算你倒霉

 

 

by Scott Devine

1.There is a miss in the TLB. The hardware will walk the shadow page table to find the mapping.

(TLB 中cache的是从guest virtual address -> host machine address，host的cr3指向的是shadow page table的位置)

2.One of two things can happen:

   •The required mapping is found in the page table and placed in the TLB. The instruction is restarted and all proceeds normally. Note that in this case the hardware does all the work.

  (在shadow page table中找到entry，放入TLB中)

   •The required mapping is not present. An page fault exception is generated by the hardware and trapped into the VMM. The VMM needs to translate the virtual address to a machine address. It starts by walking the  guest’s page table to determine the virtual to physical mapping. Note that the layout of the guest page table will be determined by the hardware being virtualized.

   (在shadow page table中直接到host machine address的mapping没有找到，trap进入VMM， 通过guest page table找到guest virtual address -> guest physical address)

3.Once the VMM finds the guest mapping one of two things can happen:

   •The guest mapping is not present. In this case the guest expects a page fault exception. So the VMM must generate an exception on the virtual cpu state and resume executing on the first instruction of the guest exception handler. This is called a true page fault because the hardware page fault results in a guest visible page fault.

    (guest page table中mapping也没有，说明guest期望得到一个page fault， inject page fault在guest中，有guest处理)

   •If the guest mapping is present then the VMM must translate the physical page to a machine page. This is called a hidden page fault because the hardware fault is a fault that would not have occurred in non-virtualized system. In order to translate the physical page to machine page the VMM must look in a data structure that maps physical pages to machine pages. This data structure is defined by the VMM, for example PMap. The VMM might have perform further processing if there is no machine page backing the physical page or in other special circumstances. 

（查找存储guest physical address -> host machine address的data structure，如果miss了，就添加）

4.The virtual to machine translation is complete. The new translation is put into the shadow page table.

   （把这个新的mapping放入shadow page table）

5.The VMM restarts the guest instruction that faulted. Now the hardware TLB refill mechanism will work.

6.The hardware put the new mapping in the TLB and life goes on.

 

难得一见的好纪录片，推荐一下，也许里面存在着中国的未来

 

当年达芬奇的Battle of Anghiari和米开朗琪罗画的Battle of Cascina，apple4us上有了一篇文章用当年的画家们比喻了一下现在的microsoft,google,apple的状况。

昨天一场莫名大雨，好比提前打了一场飞机，也就换来了今天早上帝都人神共庆D国生日的好天气，今天美帝驻帝都大使馆那台该死的空气质量检测仪总归能发一条中国网民无法收到的moderate的tweet来抚慰我们受伤的心灵了。

1. Create a new virtual machine and choose its hypervisor as qemu.

2. Name it "JOS"

3. Configure the hard disk and memory

4. virsh dumpxml JOS > jos.xml

5. Edit the jos.xml like below

 1 <domain type='qemu'>
 2   <name>JOS</name>
 3   <uuid>8e7bb147-9da1-49e0-90b7-5011c54ae9a6</uuid>
 4   <memory>262144</memory>
 5   <currentMemory>262144</currentMemory>
 6   <vcpu>1</vcpu>
 7   <os>
 8     <type arch='i686' machine='pc'>hvm</type>
 9     <boot dev='hd'/>
10   </os>
11   <features>
12     <acpi/>
13     <apic/>
14     <pae/>
15   </features>
16   <clock offset='utc'/>
17   <on_poweroff>destroy</on_poweroff>
18   <on_reboot>restart</on_reboot>
19   <on_crash>restart</on_crash>
20   <devices>
21     <emulator>/home/guzhongshu/Project/Jos/qemu_wrapper.sh</emulator>
22     <disk type='file' device='disk'>
23       <source file='/home/guzhongshu/Project/Jos/obj/kern/bochs.img'/>
24       <target dev='hda' bus='ide'/>
25     </disk>
26     <disk type='file' device='disk'>
27       <source file='/home/guzhongshu/Project/Jos/obj/fs/fs.img'/>
28       <target dev='hdb' bus='ide'/>
29     </disk>
30     <interface type='user'>
31         <mac address='52:54:00:12:34:56'/>
32         <model type='i82559er'/>
33     </interface>
34     <parallel type='stdio'>
35       <target port='0'/>
36     </parallel>
37     <serial type='pty'>
38       <target port='0'/>
39     </serial>
40     <console type='pty'>
41       <target port='0'/>
42     </console>
43     <input type='mouse' bus='ps2'/>
44     <graphics type='vnc' port='-1' autoport='yes' keymap='en-us'/>
45   </devices>
46 </domain>

6. virsh define jos.xml

7. Add file qemu_wrapper.sh because some arguments can not be added in the xml. We need to use some trick.

#!/bin/sh
  exec /usr/local/bin/qemu -redir tcp:8080::80 -redir tcp:4242::10000 "$@" -debug-e100 -pcap slirp.cap

这人究竟是谁？太恐怖鸟，难道真的是同名的？？？？我一直以为我的名字全中国独一无二的。

不会是这个网站随便拉了个名字注册一个假id吧。

After changing emulator to qemu, I find that the file flush in file system seems not work correctly. The data I wrote to disk lost after rebooting the machine. Finally I find that the dirty bit is not set in file_write because the address space of fs and user env is different. Copy the content of memory will only make the address of current env dirty. But the memory of fs is still clean. Add two lines after memmove in file_write

    for (i = 0; i < n; i += BLKSIZE)
        fsipc_dirty(fd->fd_file.id, offset + i);

To send request to the file system server to mark the page dirty directly.

Another thing to mention is that, it seems that *blk=*blk has no effect for the dirty bit. I Just map the page using syscall to modify its perm. Also please remember in the sys_map_page, you needs to modify the condition of returning invalid parameter. Add PTE_D to the reasonable parameter to perm.

 

给一张Erdos的照片，是不是很有风骨？

发现Erdős number只有两个中国人是为1的（本人为infinite）

Frances Foong Yao (Andrew Yao的老婆)和柯召

Erdos本人96年去世鸟，这个世界的Erdős number为1的也就不会变了

柯老先生也去世鸟，想Erdős number成2的，快去找姚夫人合写论文吧

Challenge! Implement interrupt-driven IDE disk access, with or without DMA. You can decide whether to move the device driver into the kernel, keep it in user space along with the file system, or even (if you really want to get into the micro-kernel spirit) move it into a separate environment of its own.

We know that JOS is exokernel style operating system. To put ide driver into kernel space is not a graceful solution. But use upcall to dispatch them into user space needs more effort. It maybe resemble the way JOS to process the user page fault in the fork.

I choose the easy style to move ide driver from user space to kernel. There are some points need to be take care.

1.  JOS file system is not in kernel space. If we send read or write request from file system to ide driver, the address translation is needed. Read and write port's address is the address in the current context. I just map the page to the temp address in the current env's address space during the handling of the ide irq. But remember NOT to do this in the ide_{read,write} function because maybe the environment has yielded in the later time.

2. After file system sends request, it needs to be blocked. But simply making it not runnable is not correct because we will return back from the system call. Return to a not runnable env is not possible. I choose to sleep the env and send signal from kernel to wake it up if the read and write operation has been completed. This is much more like the AIO model, but the advantage is that file system now is in user space, we just need to yield to other process and sleep.

Or you can just make it not runnable when i/o and restore it to runnable if i/o complete.

3. Write into disk needs to wait that disk is ready. Otherwise the write interrupt cannot be sent from disk.

Future work

1. Add an io server to process the request parallelly. More exokernel : - )

2. Add an io scheduler to process requests in a more reasonable way.