111qqz的小窝

老年咸鱼冲锋!

【施工中】MIT 6.828 lab 3: User Environments

JOS的environments基本可以理解成”process”进程的同义词,但是由于”process”是一个unix术语,因此使用environment这个词.

Part A: User Environments and Exception Handling

查看 kern/env.c文件,看到三个全局变量:

envs会在JOS启动后会指向一个Env structures的数组,表示JOS中的全部environments. 理论上,JOS kernel最多能支持NENV个同时运行的environments. 但是实际上不会远不会达到这个数量.

env_free_list是一个链表结构,用来存放当前没有在运行的Env structure.. 和page_free_list 类似.

curenv表示的是当前正在运行的environment,当JOS刚刚启动,第一个environment运行之前,curenv的值为NULL.

接下来我们来阅读一下inc/env.h文件

 

  • env_tf: 用来在切换环境时保存各种register的值,以便之后恢复现场.
  • env_link: 用于构成一个链表结构,指向喜爱一个空闲的 environment.
  • env_id: 用于唯一标识使用当前这个Env structure(也就是envs数组中的某个位置)的environment的ID.当这个environment终止时,envs数组中的用一个位置可能会被re-allocate一个新的environment,但是env_id是不同的.虽然env_id不同,但是env_id的最后10bit是用来标识在envs的下标的,如果使用的是envs数组中的同一个位置,这部分是相同的.具体可以参考inc/env.h.
  • env_parent_id: 创建这个environment的environment 的env_id. 就是父进程id…
  • env_type:  用于区分不同种类的环境.对于大部分环境,类型都是ENV_TYPE_USER.
  • env_status: 用来标识当前这个environment的状态.
    • ENV_FREE: 标识一个environment是inactive的,因此在env_free_list上.
    • ENV_RUNNABLE: 标识一个environment等待运行在处理器上.
    • ENV_RUNNING:标识正在运行
    • ENV_NOT_RUNNABLE: 标识一个目前active的环境,但是没有准备好运行,原因可能是正在等待一个其他environment的交互.
    • ENV_DYING: 可以类比”僵尸进程”
  • env_pgdir: 当前这个environment的page directory.

 

Allocating the Environments Array

Modify  mem_init() in kern/pmap.c to allocate and map the  envs array. This array consists of exactly  NENV instances of the  Env structure allocated much like how you allocated the  pages array. Also like the  pages array, the memory backing  envsshould also be mapped user read-only at  UENVS (defined in inc/memlayout.h) so user processes can read from this array.

You should run your code and make sure  check_kern_pgdir() succeeds.

和mem_init中申请pages的空间是一样的.

 

后面有空再写

 

 

 

 

 

【施工中】CSAPP data lab

CSAPP第二章的内容以前组成原理基本都学过…所以就简单翻了翻。

对应的lab是用位运算实现各种有的没的…

题目基本都很tricky…

除了用到一些常规的位运算性质,还用到了一些奇怪的条件:

  • ~0x7FFFFFFF = 0x7FFFFFFF + 1
  • 0xFFFFFFFF +1 =  0x00000000
  • 0 == ~0+1

唯一让我觉得比较有趣的是how many bits这道题

题目要求是给一个32-bit signed int,问最少用多少位能得到它的补码表示。

考虑正数,显然,高位的连续的多个0是不必要的,只需要一个符号位的0即可。

那么对于负数,高位的连续的多个1也是不必要的。 原因是,-2^k + 2^(k-1) =  -2^(k-1),也就是说,去掉两个连续的1中高位的那个,数值没有改变。

我们可以将正数和负数统一来看,都是找到最高位的0和1的交界。

这可以通过和相邻的位置求异或,找到最高位的1的方式来实现。

接下来就是如何找一个数的最高位的1的位置了。

方法是构造一个单调的函数f,假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.

然后在函数f上二分。

全部问题的代码如下,思路写在注释里了。还有3个涉及浮点数的问题之后补。

 

 

 

manjaro /archlinux 下 steam 文明5/6(civilization V/VI)的运行方法

系统版本为Manjaro 18.0.3 Illyria

运行文明5比较容易,只需要设置启动选项为:

LD_PRELOAD=/usr/lib32/libopenal.so.1 %command%

 

文明6运行会报错 undefined symbol: FT_Done_MM_Var

解决办法是 在终端中用如下办法运行steam:

LD_PRELOAD=/usr/lib/libfreetype.so steam

参考链接

【试工中】 halide学习笔记

Halide is a programming language designed to make it easier to write high-performance image and array processing code on modern machines. 

halide有两个特性比较吸引人。一个是对于各种平台架构的支持。

  • CPU architectures: X86, ARM, MIPS, Hexagon, PowerPC
  • Operating systems: Linux, Windows, macOS, Android, iOS, Qualcomm QuRT
  • GPU Compute APIs: CUDA, OpenCL, OpenGL, OpenGL Compute Shaders, Apple Metal, Microsoft Direct X 12

另一个是把计算什么和怎么计算(何时计算)分离开来。

可以直接参考tutorials 来学习

 

下面是一段将Halide Buffer转化成opencv Mat的代码,用于调试。

 

吐槽下hahide的文档…各种函数全靠试…

试了好久得到的,opencv Mat转halide::buffer的办法:

 

可能会报错Error: Constraint violated: input.stride.0 (3) == 1 (1),原因是:

We have a default constraint of stride==1 on the innermost dimension, so that vectorization works out well

Constraint violated: f.stride.0 (2) == 1 (1) #3109

解决办法是(对于AOT的编译方式):

ImageParam input(type_of<uint8_t>(), 3);
input.dim(0).set_stride(Expr());
一种更简便的opencv Mat得到halide buffer的办法. 一个关键的问题是opencv Mat的memory layout是Interleaved的方式,也就是如下:
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
但是Halide::buffer的默认memory layout是Planar的方式:
// RRRRRRRR
// RRRRRRRR
// RRRRRRRR
// RRRRRRRR
// GGGGGGGG
// GGGGGGGG
// GGGGGGGG
// GGGGGGGG
// BBBBBBBB
// BBBBBBBB
// BBBBBBBB
// BBBBBBBB
因此需要用到函数

make_interleaved()

 

 

 

【施工完毕】MIT 6.828 lab 2: Memory Management

2019年2月24:完成了除了”Challenge”以外的全部练习和问题. 总共花费15个小时.

2019年2月26:完成”Challenge 2″(应该是最简单的一个orz,只花了不到一个小时)

Part 1: Physical Page Management

操作系统必须时刻追踪哪些物理内存在使用,哪些物理内存没有在使用。

一个问题是,

Ex 1. In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

boot_alloc()
mem_init() (only up to the call to check_page_free_list(1))
page_init()
page_alloc()
page_free()

check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.

READ MORE →

C语言变长参数

说起C语言的变长参数,可能听起来比较陌生,因为很少会需要自己实现。不过想一下scanf和printf,参数个数的确是不固定的。

stdarg.h 中提供以一套机制来实现变长参数。以及,要说明的是,变长参数不是什么黑魔法,原理依赖于stack frame的结构,具体可以参考x86-calling-conventions   简单来说,由于函数参数入栈的顺序是固定的,因此一旦我们知道某函数帧的栈上的一个固定参数的位置,我们完全有可能推导出其他变长参数的位置 

在实现上,需要了解的是:

  • va_list,一个类型,可以看做是变长参数列表;
  • va_start,用来初始化变长参数列表的宏,声明为void va_start( va_list ap, parm_n );  ap为va_list变量,parm_n为变长参数前一个变量(C语言要求至少有一个named variable作为函数的parameter)
  • va_arg,用来得到下一个参数的宏,声明为T va_arg( va_list ap, T ); 返回的类型取决于传入的类型T。特别注意:”If  va_arg is called when there are no more arguments in  ap, the behavior is undefined.”
  • va_end ,用来将va_list释放的宏。

下面看一个例子就明白怎么用了orz

如果想研究c语言中变长参数的具体实现,可以参考 也谈C语言变长参数

参考资料:

Variable numbers of arguments

 

x86 calling conventions

x86的调用约定主要说的是这几件事:

  • The order in which atomic (scalar) parameters, or individual parts of a complex parameter, are allocated
  • How parameters are passed (pushed on the stack, placed in registers, or a mix of both)
  • Which registers the called function must preserve for the caller (also known as: callee-saved registers or non-volatile registers)
  • How the task of preparing the stack for, and restoring after, a function call is divided between the caller and the callee

调用约定实际上并不唯一

我们比较关注gcc编译器下的cdecl(C declaration)

对于如下这段代码:

调用过程如下:

在c语言中,函数的参数被以从右向左的顺序压入栈,也就是最后一个参数最先入栈。

这里是栈指的是调用栈(Call_stack)

调用栈的结构如下(注意此图的栈是从下往上增长的,这与通常情况并不相符,不过不影响此处的说明),这是在调用的DrawSquare函数中调用DrawLine函数时的情景

stack frame通常按照入栈顺序(写在前面的先入栈)由三部分组成(可能某部分为空):

  • 函数的参数值(以从右向左的顺序入栈)
  • caller的地址值,为的是调用函数之后能继续执行caller其余的代码。
  • 函数的局部变量

 

接下来我们看一下调用过程对寄存器的影响。这里暂且不提eax寄存器通常用来保存结果之类,主要想谈谈调用过程对sp和bp两个寄存器的影响。

sp是stack pointer,保存的是当前栈顶地址

bp是base pointer(就是stack frame中的frame pointer), 值为函数刚刚被调用时的栈顶位置。

bp这个寄存器的作用主要是比较方便,因为如果只有stack pointer,那么在函数里面,stack pointer也是可能变的,显然不如使用base pointer方便。

具体来说,在使用base pointer的情况下,函数的返回地址永远为ebp + 4,第一个参数的地址为ebp+8,第一个局部变量的地址为ebp-4

而且使用bp的情况下,回溯调用栈会变得非常方便。

At ebp is a pointer to ebp for the previous frame (this is why push ebp; mov ebp, esp is such a common way to start a function).  This effectively creates a linked list of base pointers.  This linked list makes it very easy to trace backwards up the stack.  For example if foo() calls bar() and bar() calls baz() and you’re debugging baz() you can easily find the parameters and local variables for foo() and bar().

为什么ebp指向的内容是上一个 stack frame中的ebp?我们看push ebp; mov ebp esp这两条指令。push ebp相当于先esp-=4,然后将ebp放到esp所指向的位置。接着mov ebp esp,相当于把当前的esp,也就是上一个ebp所在的位置,赋值给新的ebp.  所以。。这其实是个链表啊

 

 

参考资料:

x86 calling conventions

Stack_register

Call_stack#STACK-FRAME

What is exactly the base pointer and stack pointer? To what do they point?

All About EBP

 

 

【施工完成】MIT 6.828 lab 1: C, Assembly, Tools and Bootstrapping

花费了30+小时,终于搞定了orz

 

Part 1: PC Bootstrap

The PC’s Physical Address Space

8086/8088时代

由于8086/8088只有20跟地址线,因此物理内存空间就是2^20=1MB.地址空间从0x00000到0xFFFFF.其中从0x00000开始的640k空间被称为”low memory”,是PC真正能使用的RAM。从 0xA0000 到 0xFFFFF 的384k的non-volatile memory被硬件保留,用作video display buffers和BIOS等。

READ MORE →

优化学习笔记(1):Loop unrolling

迫于生计,最近要学习halide

先去学习/复习一下常见的编译优化技巧。

loop unrolling,也就是循环展开,顾名思义,就是把循环展开来写。

循环展开是一种优化,可以手动实现也可以编译器自动实现。

为什么要将循环展开?

  • 循环每次都需要判断终止条件,展开后可以消除这部分开销。
  • 减少分支预测开销。循环里的分支是指“跳出循环”还是“进行下一次迭代”
  • vectorization

    可以看到最里面一层循环被展开以实现向量化.向量化是一种优化计算的手段。该优化的实现基于SIMD 和Advanced_Vector_Extensions(AVX)指令集架构的支持。
  • 消除和loop counter(i)有关的除法计算。
  • 消除循环内部的分支。比如loop counter奇数和偶数时会进入不同的分支,那么将循环展开后,就消除了该分支。

有什么缺点?

  • 代码体积增加了。这对于嵌入式设备等往往是不可接受的。
  • 代码可读性变差了。
  • 单一指令可能会使用更多的寄存器,导致性能下降。
  • 如果循环内部包含函数调用,那么和函数的内联(inline)优化会有冲突。原因是,循环展开+函数展开…代码的体积会爆炸。

参考资料

 

【施工中】MIT 6.828 Operating System Engineering 学习笔记

课程主页

这课稍微有点硬核…感觉基础稍微有些不扎实就做不下去orz.

网上似乎是有博客写了6.828的学习笔记,不过我更希望自己能够独立完成,二手的知识,谁知道是对的错的呢…况且课程本身给的参考资料应该还是足够多的。

环境的话,手头没有ubuntu系统,恰好半年前剁了阿里云的轻应用服务器,就在上面做吧。

为了这门课,我读了/计划读以下书籍(随时更新)。大概也是为了检查一遍自己的知识体系。

每个lab用到的网页形式的参考资料,会在每个lab的博客中分别给出。

最后,放一段《游褒禅山记》中的文字,与君共勉!

夫夷以近,则游者众;险以远,则至者少。而世之奇伟、瑰怪,非常之观,常在于险远,而人之所罕至焉,故非有志者不能至也。有志矣,不随以止也,然力不足者,亦不能至也。有志与力,而又不随以怠,至于幽暗昏惑而无物以相之,亦不能至也。然力足以至焉,于人为可讥,而在己为有悔;尽吾志也而不能至者,可以无悔矣,其孰能讥之乎?

 

codeforces round 530 div2

A,B,C:都很简单,不说了。

D:一棵树,给出树的结构,以及从树根到某个深度为偶数的节点的路径和,问能否构造一种所有节点点权和最小的树,输出最小点权和。

思路:

容易知道,如果想要点权和最小,那么尽可能让靠近树根的点承担更多的点权。

具体做法是,bfs,对于每个节点u,取其儿子中最小的S值求节点u的信息。

比赛的时候wa16…最后发现是答案要用long long存…因为单个路径和是<=1E9的。。多个加起来会超过int…  长时间不打连这种常见的坑都不敏感了啊。。。

 

codeforces hello 2019

好久没玩cf了,竟然还能涨分(虽然我用的小号Orz)

三题,D应该是数学+DP…数学实在是忘干净了。。。

前面三题大体还好,都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。

A:给出一个扑克牌x,和另一个包含5个扑克牌的集合。问扑克牌x是否和扑克牌集合中至少一张扑克牌的花色或者数字相同。

不多说了。

B:一块钟表(只有一个指针),初始指向12点,需要拨动指针恰好n次(n<=15),每次可能顺时针,也可能逆时针,拨动的角度范围在[1,180],问是否有一种方案,使得拨动n次后,指针回到12点。

思路:观察下数据范围,n最大才15,最多也不过2^15的情况…既然如此,不如暴力。

枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。

C: 给出n(n<=1E5)个括号序列,括号序列可能不合法,现在要从这n个括号序列中,组成尽可能多的有序二元组,使得有序二元组的括号序列合法,并且每个括号序列只能出现在一个有序二元组中,现在问最多能组成多少这样的有序二元组。

思路:我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是,如果两个括号序列本身都是合法的,那么组合在一起也一定是合法的。进一步,对于本身不合法的括号序列,容易知道,其必须只有一种没有完成匹配的括号方向,且该括号方向的数量与相反括号方向的数量相同,才能完成匹配。

因此做法是,对于括号序列预处理,得到该括号序列的状态(本身匹配为0,正数代表'(‘的个数,负数代表’)’的个数,如果有两个方向同时存在,则直接舍弃掉,因为这种括号序列不可能组成合法的括号序列。预处理之后,用multiset搞一下。

代码写得比较乱…flag存的时候其实没必要存index…

D:初始一个数n(n<=1E15),k次操作,每次操作等概率将当前的数变为其因子中的一个。问k次操作之后,结果的期望是多少。

在@适牛的指导下,以及参考了官方题解。。写了出来。。

dp还是太弱了。。。。

比较重要的一点是,不需要考虑所有因子,只需要考虑质因子。

质因子的个数不超过50个(因为 2^50 > 1E15)

另外一个重要的是,对于每一个质因子的概率是积性函数,可以乘在一起。

因此问题变成了,对于一个质因子唯一的n,如何算所求的期望。

我们考虑dp[i][j]表示第i次操作后,质因子还剩j个的概率。

显然dp[0][tot]=1,其中 p^tot = n,p为某个质因子。

转移方程为:

dp[i][j] = sum(dp[i-1][jj]) (j=<jj<=tot)

然后最后结果的期望就是:sum(dp[k][j]*p^j) (0=<j<=tot)

还有一点,由于题目的输出要求,需要用到费马小定理求个逆元。。。

逆元相关的参考 acdreamer的博客。。。

 

 

 

 

2019 to do list

  • Operating Systems: Three Easy Pieces
  • fluent python
  • 《计算机网络:自顶向下方法》
  • 《mysql必知必会》
  • PC Assembly Language ( for mit 6.828 )

我在公司的服务器上执行了sudo rm -rf /*

TL;DR

  • 依靠人的小心谨慎是不靠谱的,人总有失误的时候
  • 看了下docker volume的权限机制,貌似是从docker image中继承。
  • 写了两个脚本,用来把rm alias到mv,避免手滑

 

又是一个可以摸鱼的周五晚上,sensespider系统测试了一天,fix了几个Bug,似乎可以发布了。系统一直是部署在了docker中..这几天测试产生了不少结果文件在host的volume中… 看着不舒服,干脆删一下好了

嗯?怎么所有者是root。。。那我sudo一下,也没什么大不了的嘛

然而手滑了… 打了个 sudo rm -rf /*   …

 

提示无法删除/boot  device is busy…

吓了一跳,下意识Ctrl-C…

从新在本地ssh到服务器,发现已经登不上去了…报错在找不到sh

看了一下,果然服务器的/bin 目录已经被删干净了…

google了一些从rm中恢复文件的帖子…

试图用 sudo apt-get install  装一些工具包…

这个时候已经提示我找不到apt-get 了。。。

非常慌。花了3分钟思考了我到目前为止的一生

看了下scp命令还在,赶紧趁着这个终端回话还没关,把本地的/bin目录拷贝了上来。

试了下,ssh命令可以用了。 这样至少后续的修复(在不麻烦IT同事的情况下)不用跑机房了。有些镇定。

然后发现apt-get 命令还是用不了。。。思考了1分钟。。。

然后发现服务器用的是centos…….

再试了各种常用命令,试了docker相关的各种命令,都可以正常工作。

然而整个人都被吓傻了….睡了一觉才回过神。

又查了下docker volume权限的事情,发现挂载目录继承docker image中用户的权限是feature  Volumes files have root owner when running docker with non-root user.   那似乎就没办法了。

以及写了两个脚本,来避免手滑,分别是zsh环境和bash环境下的。

kkrm

 

 

docker network 与 本地 network 网段冲突

起因:

公司部署在hk的爬虫服务器突然挂掉了。后来发现只是在深圳办公区无法访问。排查后发现原因是docker的网络(包括docker network的subnet或者是某个容器的ip)与该host在内网的ip段相同,导致冲突。

排查过程:

有两个方面需要排查。一个是docker服务启动时的默认网络。

默认网络使用bridge桥接模式,是容器与宿主机进行通讯的默认办法。

修改默认网段可以参考 http://blog.51cto.com/wsxxsl/2060761

除此之外,还需要注意docker创建的network的网段。

使用docker network ls 命令查看当前的网络

然后可以使用docker inspect 查看每个network的详细信息。

也可以直接使用ip addr 来查看各种奇怪的虚拟网卡的ip,是否有前两位的地址和host的ip地址相同的。

解决办法:

本想在docker-compose up 时指定默认网络的subnet

结果发现好像并不支持?version 1.10.0 error on gateway spec

Was there any discussion on that? I do need to customize the network, because my company uses the 172.16.0.0/16 address range at some segments and Docker will simply clash with that by default, so every single Docker server in the whole company needs a forced network setting.

Now while upgrading my dev environment to Docker 1.13 it took me hours to stumble into this Github issue, because the removal of those options was completely undocumented.

So please, if I am working on a network which requires a custom docker subnet, how am I supposed to use Docker Compose and Docker Swarm?

最后用了个比较间接的办法。

先手动创建一个docker network,然后再在docker-compose的配置文件中指定。