topcoder: YetAnotherORProblem2

这题显示只有18%的AC率,题目本身不难,估计都是败在执行时间上了;我的解法如下,典型的DP思维,子问题是:如果已知长度为n-1的情况下,和或操作相等的数列,求长度为n的情况;状态index为每个满足条件的数列的和Sn-1(因为和或相等,也是该数列的或),状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

 

topcoder: YetAnotherTwoTeamsProblem

这是一道标记为hard的题,确实比较hard

开始用了一个比较简单暴力的方法,其实也是DP思路,但是状态取的比较偷懒,直接用了所有的可能组合作为状态,虽然在求解过程中可以利用到已经搜索过的状态,但是整个搜索空间还是太大了,导致虽然结果正确,但是严重超时了:

又做了一次伸手党,看了解答后醒悟了,其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

topcoder: ZigZag

再来水一道简单题:题目地址

想法很自然,记录下当前的方向,一旦出现方向不一致的就把总数加一,同时方向改变,否则continue,然而其实已经包含了动态规划思想

上代码:

看了下别人提交的,思路一样,只不过有人上来先把整个序列的变化趋势算一遍,即遍历seq,然后算出seq[i]-seq[i-1]的值记录下来记为V[i],其实要的就是一个正负号,然后再次遍历还是记录当前的方向,乘以当前遍历到的那个趋势V[i],乘积发生变化时就在结果上加一并改变当前方向值。

topcoder practice: ZooExchangeProgram

为了兴趣,也为了保持coding的能力,重新开始写一些算法题;为了对算法了解的更透彻,也为了锻炼表达能力,干脆在博客里面对解题代码进行详解,代码是自己写的,但也不排除参考了别人的解法,消化吸收了就是自己的,不是吗?

题面:

太长了,就不贴了,链接在此

代码及详解:

Mac新手键盘映射探索

作为Linux老司机都是重度终端依赖症患者,unix终端对ctrl键的摧残各位老司机都懂的;换了Mac后发现键盘极其反人类,右边control没有,左边control那么小而且位置感人,ctrl+r这种分分钟用的着的快捷键在Mac上换了各种姿势都不爽,这是要把左手按残的节奏阿,左手可是很重要的,咳,我说的是敲代码。

谷歌了一把键盘映射,发现一个叫keyremap4macbook的应用,几个论坛里面都强烈推荐,现在的版本叫做karabiner;先安装了前者,居然还要我重启,为了左手的解放勉为其难的重启了下,结果还是徒劳,完全没有任何反应,估计是版本的问题。这种ugly的非App Store应用折腾了我半天还无效,干脆就放弃了。

接着再求助搜索引擎,找到了这个,虽然是短短一行,但是却提醒了我,看来还是需要再探索一下Mac系统自身设置。人肉探索了一段时间后,发现了一个可以利用的点,如图所示,虽然注释文字描述的比较抽象,但是下面的菜单列表对正常智商的人来说一目了然了,显然是个映射关系,那么我们将那个“大户”command键合control键对调一下是否合理呢,我目前看来是合理的,作为程序员最需要效率的就是在terminal中挥散汗水的时间,而其他的操作对快捷键要求不高,那么我们需要的正是让control键无处不在,触手可及!

PTRACE的权限检查,自由是有前提的~

系统调用PTRACE的一切开始于这里:
COMPAT_SYSCALL_DEFINE4(ptrace, compat_long_t, request, compat_long_t, pid,
               compat_long_t, addr, compat_long_t, data)

首先提供了attach的绿色通道:
if (request == PTRACE_ATTACH || request == PTRACE_SEIZE) {
        ret = ptrace_attach(child, request, addr, data);
attach做的事情就是把当前进程变成了被trace进程的父进程,同时把被trace进程加入到当前进程的ptraced链表中;
__ptrace_link(task, current);
list_add(&child->ptrace_entry, &new_parent->ptraced);
    child->parent = new_parent;
但是这样做是有前提的,具体请看后面的分析,这里先按下不表。

attach?wtf?为啥要在用之前attach,搞得这么神秘,难道直接用不可以吗?
不可以,因为你不能直接访问其他进程的地址空间,否则地址空间的隔离不就变成笑话了。
所以这个ptrace系统调用入口做了个很重要的check:
ret = ptrace_check_attach(child, request == PTRACE_KILL ||
                  request == PTRACE_INTERRUPT);
    if (!ret) { //只有返回为0,即判断条件成立,才继续执行对ptrace的request
        ret = compat_arch_ptrace(child, request, addr, data);
        if (ret || request != PTRACE_DETACH)
            ptrace_unfreeze_traced(child);
    }
child->ptrace && child->parent == current
只有过了这一关,才能进行后面的操作(除了kil和interrupt,他们自己的处理逻辑里面有此类的判断或者无需),那难道随便就可以attach,那我就麻烦一点先attach呗;显然不会这么傻,前面卖了个关子,这里来看看attach里面做的权限检查,必须是有权的人才能随便搞的,屁民是要守法的!!

权限管理的水比较深,博主还没吃透,所以这里先简单列一下我能看懂的部分:
etval = __ptrace_may_access(task, PTRACE_MODE_ATTACH);
这里有两个条件,1)我自己人改自己人ok(这里的suid euid等等的请看后面链接);2)我的上层命名空间ok(我理解是,比如像root用户这种大boss)
    tcred = __task_cred(task);
    if (uid_eq(cred->uid, tcred->euid) &&
        uid_eq(cred->uid, tcred->suid) &&
        uid_eq(cred->uid, tcred->uid)  &&
        gid_eq(cred->gid, tcred->egid) &&
        gid_eq(cred->gid, tcred->sgid) &&
        gid_eq(cred->gid, tcred->gid))
        goto ok;
    if (ptrace_has_cap(tcred->user_ns, mode))
        goto ok;
另外还要做命名空间能力的检测,看看目标进程的命名空间有没有被ptrace的能力:
ns_capable(__task_cred(task)->user_ns, CAP_SYS_PTRACE)

参考链接

修改运行中代码之神器——PTRACE的秘诀

ptrace是个神奇的系统调用,是gdb等工具的实现基础,它可以用来监控进程的执行,读取或修改进程的寄存器和memory内容包括代码段。有的底层码农老司机甚至也会觉得奇怪,代码段不都是不可写的吗,为啥ptrace就能修改呢?

下面解释一下,老司机直接看后面代码秒懂:
  • 首先,代码段不可写,其实是在页表中对代码段相应的页设置了不可写的flag,而页表只能控制进程地址空间的访问权限。
  • 其次,这里的不可写只对用户态进程起作用。当然,进程的地址空间是隔离的,而进程在用户态只能通过自己地址空间的虚拟地址访问内存,所以当前进程在用户态也无法访问其他进程的地址空间。
  • 最后,在内核态就能随便修改其他进程的代码段了?是的,但是你得先找到目标代码段地址空间对应的物理页,然后再映射到内核地址空间,然后新的地址空间的访问权限决定了你能如何访问这些物理页;ptrace中如下这段代码实现了这些功能,如何能执行到这些代码又是另外一个话题了;这里面牵涉到权限管理等等的问题,ptrace系统调用已经考虑的很周全了,博主会在下一篇博客里面详解ptrace系统调用的权限检查~
ptrace_request()
    case PTRACE_POKETEXT:
    case PTRACE_POKEDATA:
        return generic_ptrace_pokedata(child, addr, data); //调用__access_remote_vm
 最后的关键代码:
ret = get_user_pages(tsk, mm, addr, 1,
                write, 1, &page, &vma);
……
maddr = kmap(page);
            if (write) {
                copy_to_user_page(vma, page, addr,
                          maddr + offset, buf, bytes);
                set_page_dirty_lock(page);
            } else {
                copy_from_user_page(vma, page, addr,
                            buf, maddr + offset, bytes);
            }
            kunmap(page);

requests.exceptions.SSLError when running a py2exe generated EXE file

最近做个兴趣小项目,需要用python来get/post https请求,用到了requests模块,因为要在windows下使用,考虑到易用性和小白玩家的需求,使用py2exe生成exe。参考链接看起来很简单,统共分三步:1,安装py2exe;2,准备一个配置脚本,我们叫他build_exe.py;3,执行一条命令python build_exe.py py2exe

先把这个简单的初级版本放这里:

#usage: python build_exe.py py2exe

from distutils.core import setup
import py2exe

setup(console=[‘myqqbot.py’])

但是这里其实还是有坑的,安装py2exe要注意,并不是直接pip install py2exe就可以了,py2exe是人家python3专用的,python2的是py2exe_py2,悲剧吧,所以装包前最好还是pip search下,免得浪费时间还不知道错在哪。配置脚本貌似简单,大家应该能想到这里面其实是有很多玩法的,以至于需要一个脚本而不是直接传参。

 

生成过程很顺利,不过几秒exe文件已经躺在dist目录下了。但是双击他,console一闪而过,都不知道发生了什么。Windows就是这么变态,反正把你当小白,不给你任何错误信息。在超级难用的cmd里面用命令行调用exe后发现了问题:

requests.exceptions.SSLError: [Errno 2] No such file or directory

万能的stackoverflow告诉我们,不要慌我有药,药在这。so大夫告诉我们在exe文件执行的时候环境变量发生了改变,找不到这个pem文件了,我们需要给一个静态的pem文件路径,或者设置一个REQUESTS_CA_BUNDLE环境变量,因为不知道这个exe文件会在什么环境下执行,不能保证所在的环境中有这个pem文件,所以我们必须在打包的时候打一个pem文件进去。到此产生两个新问题:1,如何获取cacert.pem文件;2,怎么用py2exe打包,当然你肯定能想到直接放到生成的dist目录下面就可以了,但是这样是不是太low了,我们要有更elegant的方法。 Continue reading “requests.exceptions.SSLError when running a py2exe generated EXE file”

pause loop exiting & ple gap for KVM performance tunning

A system feature called Pause-Loop Exiting can cause instability and performance degradation on a virtualized system that will have a web server running in a heavily utilized guest. Turn it off by setting the ple_gap module parameter to 0 for kvm_intel.


Example: Add file kvmopts.conf to /etc/modprobe.d/ with contents:
 options kvm_intel ple_gap=0
Restart the kvm_intel module if it is already running.
 # modprobe -r kvm_intel
 # modprobe kvm_intel
or
insmod kvm-intel ple_gap=0

From Intel spec:
If the “PAUSE exiting” VM-execution control is 0 and the “PAUSE-loop exiting” VM-execution control is 1, the following treatment applies.
The processor determines the amount of time between this execution of PAUSE and the previous
execution of PAUSE at CPL 0. If this amount of time exceeds the value of the VM-execution control field
PLE_Gap, the processor considers this execution to be the first execution of PAUSE in a loop. (It also
does so for the first execution of PAUSE at CPL 0 after VM entry.)
Otherwise, the processor determines the amount of time since the most recent execution of PAUSE that
was considered to be the first in a loop. If this amount of time exceeds the value of the VM-execution
control field PLE_Window, a VM exit occurs.
For purposes of these computations, time is measured based on a counter that runs at the same rate as
the timestamp counter (TSC).

【人话总结】

永远把两次间隔超过ple_gap的pause指令其中的后一条作为第一次loop内pause,从这个第一次loop内pause开始计算次数直到超过PLE_window就触发exit
也就是间隔在ple_gap之内的连续pause指令构成了pause loop,大于PLE_window的pause loop将触发退出