Higher-order functions in Javascript

In Javascript, functions are just like the other variables(AKA first-class citizen), and here are several interesting tricks implemented by treating functions as first-class citizen. currying Currying is for partial evaluation, a practical example is Function.prototype.bind() in Javascript: And we can implement bind()(under this circumstance only of course) by ourselves: trampolining Javascript(ES5) does not implement tail call optimization, … Continue reading "Higher-order functions in Javascript"

Read More

[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)

Function int bitCount(int n) returns how many “1”s does the number n have expressed in the binary form. For example, 0b101 is the binary form of number 5, so bitCount(5) returns 2. the naive way Check if each bit equals 1 and return the sum: the optimized naive way Consider the number 0b1. After the first right shift, 31 … Continue reading "[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)"

Read More

online judge sandbox 设计思路(2)

This article is deprecated, please see here for more details. seccomp() seccomp 是 Linux 内核提供的一种应用程序沙箱机制,seccomp 通过只允许应用程序调用 exit(), sigreturn(), read() 和 write() 四种系统调用来达到沙箱的效果。如果应用程序调用了除了这四种之外的系统调用, kernel 会向进程发送 SIGKILL 信号。 seccomp 很难在实际中得到推广,因为限制实在是太多了,Linus 本人也对它的应用持怀疑的态度,直到出现了 seccomp-bpf。seccomp-bpf 是 seccomp 的一个扩展,它可以通过配置来允许应用程序调用其他的系统调用。chrome 中第一个应用 seccomp-bpf 的场景是把 Flash 放到了沙箱里运行(实在是不放心),后续也把 render 的过程放到了沙箱里。 我们仍然先通过限制 unlink() 来看一下 seccomp 是如何工作的: 删除失败了。 下面,我们写一个程序 b.out,让 seccomp 允许调用 unlink() ,但是不允许调用 fork(): 编译运行下: 我们的目的达到了。 seccomp-nurse … Continue reading "online judge sandbox 设计思路(2)"

Read More

online judge sandbox 设计思路(1)

This article is deprecated, please see here for more details. 实现 OJ 的 sandbox 主要有两种思路:ptrace 和 seccomp,下面我们分别讨论。 ptrace() ptrace 是类 Unix 系统上一个可以观察、控制其他进程内部状态的工具。它的用途有很多,例如程序调试(gdb、dbx等)、代码覆盖率检测、甚至可以用来做运行时补丁(想没想起来IDA和OllyDbg )。今天我们讨论的是如何通过对系统调用的限制来达到在沙箱(sandbox)中运行程序的效果。 我们先写一个程序,用来删除 /etc/hosts 文件: a.out 完成了它的使命,成功的删除了 hosts 文件。 现在,我们需要设计一个程序:通过 ptrace() 来限制 unlink() 删除文件系统中的文件。 首先,我们来看下手册上是怎么介绍 ptrace() 的: 其中,request 参数决定了 ptrace() 的行为,我们选几个用得到的选项介绍: PTRACE_TRACEME: 表明子进程(tracee)正在被父进程(tracer)所控制。注意:只有本选项适用于子进程(tracee); PTRACE_PEEKUSER: 可以从子进程中获取通用寄存器中的值,寄存器(orig_rax /orig_eax,取决于平台 )中保存的是最近一次的syscall number; PTRACE_SYSCALL: 可以将子进程从停止的状态唤醒并继续; 这样,我们就有思路了:每次程序调用系统调用,我们都去看看本次系统调用是不是 unlink(),如果是,杀掉子进程并退出即可: 当系统调用发生时,内核会把当前的 %eax/%rax … Continue reading "online judge sandbox 设计思路(1)"

Read More

使用 docker 部署 PHP 环境

Dockerfile 构建镜像 切换到 Dockerfile 所在目录,运行以下命令构建镜像: 构建完成后就可以使用 php/base:v1.0 这个镜像了: 打包镜像 使用打包镜像 运行 docker 镜像 最后,经过前端的反向代理将请求转发至 10.1.1.1:12306 就可以提供服务了。

Read More

使用 docker 作为 online judge(OJ) 的 sandbox (2)

This article is deprecated, please see here for more details. 在 使用 docker 作为 online judge(OJ) 的 sandbox (1) 中我们讨论了OJ在架构上的大概实现,现在我们继续讨论判题(以  leetcode-Longest Common Prefix 为例)。 我们首先将一个完整的题目拆分为以下几个模块: (1)测试集 (2)用户提交代码 (3)将测试集和用户提交的代码结合在一起,并运行出测试结果的预置代码(以下简称测试代码) 测试集 测试集由两部分构成:输入和输出。考虑以下两点: 一、我们不能简单地将输入和输出理解为两个字符串:输入有可能是复杂的数据结构,而针对某个题目是否回答正确的判定标准也不仅仅是输出一项(有可能包括检查输入数据),所以输入和输出需要一个可以存储复杂数据结构的传输格式构成; 二、某一道题需要针对不同的语言提供不同的测试代码,在不同的语言当中初始化数据的方式不尽相同。 由以上两点得出:合理的方式应该是JSON存储输入和输出,并保存在DB中。 用户提交代码 用户提交的代码没有太多的规范,安全性和对现有web系统的影响已经在(1)中讨论过了。 测试代码 这里是最有意思的部分:如何通过现有的测试数据来测试用户提交的代码是正确的? 在Javascript中,我们有一个现成的方法:.apply,我们可以将测试代码传给它来达到测试的目的: 同理,在其它脚本语言中,也都有类似的技巧: PHP – call_user_func_array Python – getattr Javascript’s Apply in Ruby 但是在Java / C / C++ 中,是没有类似的函数或者语法糖可以直接拿来使用的,好在 Java … Continue reading "使用 docker 作为 online judge(OJ) 的 sandbox (2)"

Read More

RecordRTC 压缩视频和音频

RecordRTC 是一个基于WebRCT实现的一个录制视频/音频的js库。项目主页是:http://RecordRTC.org/ 实际项目中发现,录制的视频和音频文件过大,可能会导致用户上传超时。本文主要记录了减小RecordRTC录制的视频和音频文件大小的几个方法。 压缩视频 修改图片大小,通过修改 config.width 和 config.height 实现: https://github.com/muaz-khan/RecordRTC/blob/master/RecordRTC.js#L2447-L2471 初始化 RecordRTC 时指定 frameInterval: 压缩音频 保留一个声道,设置 numberOfAudioChannels: 1,音频文件提及可以减少为原来的1/2; 降低采样率,设置 sampleRate: 7350,即默认采样率44100的1/6; 减小采样位数,从默认的16减小到8; 压缩音频的详细方法可以参考:http://www.cnblogs.com/blqw/p/3782420.html

Read More

使用 docker 作为 online judge(OJ) 的 sandbox (1)

This article is deprecated, please see here for more details. 最近业务要实现在线代码判定(OJ)的功能,简单调研了一下,准备使用docker实现。业务流程大概如下: 大概的思路是: nginx 判定请求是否应该转发给 OJ 集群,比如:只要请求匹配 ^~ /oj 都转发给 docker 集群处理; docker 集群接收到请求后,先将代码保存在 web server 本地; 如果待判定的语言不需要编译即可执行 (比如PHP、Python),则直接保存在 web server 的某个目录下(例如 /tmp/oj);如果需要编译(比如 c、java),则先编译,将编译后的可执行文件保存在同一个目录下; 将 web server 上保存代码的目录(上文中的 /tmp/oj)挂载到 docker 镜像的某个目录下(例如 /mnt) 调用 docker 知行代码,并返回结果。 下面是相对详细的一些步骤: 安装 docker 升级 docker 镜像中的 OS 将镜像提交到 docker hub 业务上处理提交过来的代码 当然,上面的限制并不是特别完全。对于业务来讲,还有以下几个问题需要考虑: … Continue reading "使用 docker 作为 online judge(OJ) 的 sandbox (1)"

Read More