Code杂谈 » JasonLe's TechBlog

Archive for the ‘Code杂谈’ category

Combination Sum 思路

June 1st, 2015

最新刷leetcode的题目，发现了Combination Sum题目，这个题目分为I、II、III。难度层层递进，题目就是遍历vector容器，选择出符合target number的sum组合，这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板，首先要构造dfs函数。

一般情况下，我们需要五个参数：结果，原始数据集，中间结果，当前指向的数据，满足target number的值：

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集，深搜这个数据集的各种可能性，将达成target的path中间结果加入result，按照通用模版

void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作，修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

第一步：收敛也就是target==0
第二步：使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步：如果通过第二部，也就意味着这个current合格，可以将这个加入到path中，然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的，可以多次使用。如果只使用一次的话，也就意味着我们需要sort(),然后需要将上个满足条件的值跳过，也就是II中的nums[i]==nums[i-1]比较（Combination Sum II）

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

题目：

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

No comments »

Posted in Algorithm, C/C++, Code杂谈, STL

内核页表和进程页表

May 28th, 2015

最近在看vmalloc()分配代码，我们知道当通过alloc_page()分配出来page后，需要将这些分散的物理页框page映射到vmalloc区，这里我们就要修改内核页表，以前我学页表是把内核空间与用户空间割裂学习的，导致二者无法很好地衔接，这里我会把两个概念重新解释清楚。

下面代码映射到vmalloc区的关键就是map_vm_area()函数，

for (i = 0; i < area->nr_pages; i++) {
        struct page *page;

        if (node == NUMA_NO_NODE)
            page = alloc_page(alloc_mask);
        else
            page = alloc_pages_node(node, alloc_mask, order);
...
    }

    if (map_vm_area(area, prot, pages))
        goto fail;
    return area->addr;

拿IA32架构的虚拟地址来说，0~3GB属于用户空间，用户空间是由每个进程的task_struct.mm_struct.pgd的成员变量，这个指向的就是进程页表。而3G~4GB属于内核空间，这个页表是由内核页目录表管理，存放在主内核页全局目录init_mm.pgd(swapper_pg_dir)中

struct mm_struct init_mm = {
         .mm_rb          = RB_ROOT,
         .pgd            = swapper_pg_dir,
         .mm_users       = ATOMIC_INIT(2),
         .mm_count       = ATOMIC_INIT(1),
         .mmap_sem       = __RWSEM_INITIALIZER(init_mm.mmap_sem),
         .page_table_lock =  __SPIN_LOCK_UNLOCKED(init_mm.page_table_lock),
         .mmlist         = LIST_HEAD_INIT(init_mm.mmlist),
         INIT_MM_CONTEXT(init_mm)
};

进程切换切换的是进程页表：即将新进程的pgd(页目录)加载到CR3寄存器中。而内核页表是所有进程共享的，每个进程的“进程页表”中内核态地址相关的页表项都是“内核页表”的一个拷贝。

vmalloc区发生page fault

在vmalloc区发生page fault时，将“内核页表”同步到“进程页表”中。这部分区域对应的线性地址在内核使用vmalloc分配内存时，其实就已经分配了相应的物理内存，并做了相应的映射，建立了相应的页表项，但相关页表项仅写入了“内核页表”，并没有实时更新到“进程页表中”，内核在这里使用了“延迟更新”的策略，将“进程页表”真正更新推迟到第一次访问相关线性地址，发生page fault时，此时在page fault的处理流程中进行“进程页表”的更新。

所以linux中，只有进程的页表是时刻在更换的，而内核页表全局只有一份，所有进程共享内核页表！

1 comment »

Posted in Code杂谈, Kernel内核分析, 读书笔记

Tags: PageTable

内存条物理结构分析

April 21st, 2015

Update 2015-07-04

我们经常接触物理内存条，如下有一根DDR的内存条，我们可以看到这个内存条上面有8个黑色的内存颗粒，在高端服务器上面通常会带有ECC校验，所以会存在9个黑色的内存颗粒，其中一个的内存颗粒是专门做ECC校验的。

从概念的层次结构上面分为：Channel > DIMM > Rank > Chip > Bank > Row/Column

我们可以把DIMM作为一个内存条实体，我们知道一个内存条会有两个面，高端的内存条，两个面都有内存颗粒。所以我们把每个面叫做一个Rank，也就是说一个内存条会存在Rank0和Rank1。

拿rank0举例，上面有8个黑色颗粒，我们把每个黑色颗粒叫做chip。再向微观走，就是一个chip里面会有8个bank。每个bank就是数据存储的实体，这些bank就相当于一个二维矩阵，只要声明了column和row就可以从每个bank中取出8bit的数据。

我们之前会经常说双通道，说白了就是一个DIMM就是一个通道，两个DIMM组成双通道，分别由两个Memory Controller控制。

我们可以看到两个DIMM0 DIMM0组成双通道，两个DIMM1 DIMM1组成双通道。

下面先来解释memory controllers如何从rank中取数据，上面说的都是物理结构，下面说内存的逻辑结构。因为每个rank下面会有很多chip，而每个chip又包括bank0、bank1、bank2等，在memory controllers看来每次发数据，都会同时发送给所有chip下的某个bank，并声明row和col。

以从bank0为例：

每个chip的bank0 的同一地点（row=i col=j）都会被读出8bit，那么8个chip就会同时读出64bit，然后由memory controllers传送给cpu，也就是8byte。

在memory controllers看来，每个bank存在于每个chip中，如上图所示，可以把每个chip里面的小bank连成一行，b看作成一个大的bank。然后从大的bank中读取数据。

每个bank有一个row bufffer（这个row buffer存在于bank中，而不是在memory controller，row buffer 是以bank和row作为参数的，而读到memory controller时，又加入了col参数，也就是row buffer数据量是整整一行数据，读到memory controllers中仅仅是很小的一部分数据，而row buffer是整个程序局部性的关键！），作为一个bank page，所有bank共享地址、数据总线，但是每个channel有他们自己的地址、数据总线。正因为有buffer，所以每次bank都会预读64bit的数据。

上面看到的是分解的操作，事实上，为了加快memory的读写，体系结构中引入了流水线，也就意味着memory controllers可以同时读64byte，也就是8次这样的操作。写入到buffer中，这就是局部性原理。如果我们程序猿不尊重这个规则，也就迫使bank的buffer每次取值都必须清空当前的缓冲区，重新读数据，降低数据的访问速度。

设计弊端：

那么内存在多核平台的表现就取决于数据位于哪个bank之中，在给定的时间kernel如何访问多核之间共享的bank，最好的一种情况是每个core都只访问自己的bank，互不干扰。最坏的一种情况就是所有的core都访问同一个bank，只能同时有一个core访问该bank，其他core必须等待这个bank的，这样的话造成memory access的delay，考虑一种情况：如果多个进程在多个bank中都有自己的数据，controllers不得不每次清空row buffer，造成性能损失。而且使得时间分析变得不确定！

由于memory controllers内侧对于bank的操作对外透明，row col bank这些指令信息属于内存地址（memory controllers将physics address翻译成内存地址）。研究memory controllers向bank发送读信息的编码格式，我们会发现row与col位之间会有bank 位的介入，也就意味着对于bank的访问会分割到几个bank同时进行。

如果我们想把进程在内存中的数据限制在某个bank中，就要测试这种内存地址格式，目前可以palloc自带的工具进行测试，测试bank位到底存在于内存地址的哪几位。

目前系统都是多核，而且kernel将memory视为一个整体。不会区分分配的资源来自于哪个bank，所以数据分配的确定位置是不可预期的。而且目前memory controllers被配置为分割的bank来提高bank访问的并行度（一个程序分配的内存在每个bank中都存在）。但是这个导致一个问题：肯定有好几个进程数据存在于当前bank。当bank中出现multiple error时，我们无法准确定位这个错误来自于哪个进程！

[1] http://en.wikipedia.org/wiki/Memory_bank

[2] http://arxiv.org/pdf/1407.7448.pdf

1 comment »

Posted in Code杂谈, 读书笔记

Tags: Memory PALLOC

字符编码浅析

March 26th, 2015

最近在linux与windows上面做切换，经常会遇到乱码问题，又联想起很多因为字符解析失败，最后debug出来是因为字符编码的问题后，准备仔细研究这一块奇怪的东东。

我主要是使用汉语，所以与我们息息相关的编码时gb2312、GBK和UTF系列。

GB2312是最早的汉语标准，但是最大的问题是收录的汉字太少，导致许多复杂的函数无法在机器中表示。之后Microsoft使用GB2312未使用的编码空间，拓展了收录的字符数。

但是真正的国家标准是GB18030，它收录了7万多个汉字，目前的国内软件都必须支持这个字符集。

我们都知道ASCII码在电脑中用1 byte来表示，比如 strlen(“l123”),就返回一个字符长度4，而汉字在电脑中使用2 byte来表示，也就是strlen(“李123”)返回5！

如果在一个页面中存在多种语言，那在我们看来就是一堆乱码！所以unicode出现了，但是unicode又会分成很多字符标准：

utf-16 的实现是每个字符有2 byte来表示，但是这种编码方式没有运用在浏览器中。

在windows中使用宽字符进行表示，也是说下面代码虽然有汉字，但是每个s元素都是2 byte，最后的len也还是4！

wchar_t s[10];
int len=0;

wcscpy(s, L“李123”);
len = wcslen(s);

wchar_t 其实是 unsigned short，一个 16-bit,C 语言所有的 strxxx 都有相对应的 wcsxxx,字符串前面加上 L，代表宽字符。

utf-16 的实现是每个字符由4 byte来表示，太占空间，没有人使用。
utf-8是我们现在通用的一种字符表示编码，每个字符是可变长度的。

每个字可能是 1~6个bytes (2003年后删减剩下 1~4 个 bytes)

US-ASCII (0 ~ 127) : 1-byte
部分各国字母: 2-byte (例如希腊字母，西里尔字母…)
其它常用字 : 3-byte (大部分的汉字)
极少用字 : 4~6-byte (包含罕见汉字，麻将牌…)

也就是说平时的英文数字大概一个字符一个byte，而汉字 3 byte。

上面这幅图表示的是utf8的表示方式[1],我们可以看到电脑在寻找这个字符由几个byte主要是看byte 1，有几个1 就有几个byte。

strlen("李123")

上面的代码使用unicode的话就会返回6！下面来分析下大小端与字符编码的关系：

我们都知道小端就是low byte在前，high byte在后，典型使用这种方式就是x86架构。

在GB2312中李123 = e6 9d 8e 31 32 33，那么他在小端机器中，文档中打开也是这个样子：e6 9d 8e 31 32 33
在utf-16中李123 = 67 4e 00 31 00 32 00 33 在文档中打开：4e 67 31 00 32 00 33 00。因为他是以两个byte为一个单位。
在utf-8中李123=e6 9d 8e 31 32 33 在文档中打开也是：e6 9d 8e 31 32 33

所以基于上述知识，我们知道在notepad打开一个文档，有时候会读取BOM！BOM 位于文档的开头位置

FE FF 开头 ->UTF-16 Big Endian
FF FE 开头 ->UTF-16 Little Endian
EF BB BF 开头 -> UTF-8
都不是，看系统默认编码 (GB2312？)

所以我们在代码读取文档的时候，要小心BOM的存在，BOM 可以告诉你后续内容的编码方式，有时候必须跳过 BOM，不要把 BOM 当成内容一起处理。

在Linux 中解决代码转换问题：iconv，而一些特定的语言例如python使用 str.encode(‘utf-8’)。

I18N：所有的语言都写在外部txt，方便做本地适配，代码也不用重新编译。

[1] http://en.wikipedia.org/wiki/UTF-8

1 comment »

Posted in Code杂谈

Tags: character

从0构建一个基于BananaPi的OpenWrt系统

January 28th, 2015

最近对于BananaPi系列的开发板比较感兴趣，于是在网上淘宝淘到一个BananaPi开发板，我使用的是BananaPi V1版本，目前官方已经开发出BananaPi Pro版本，自带无线模块。大家可以看一下http://www.lemaker.org/。

具体硬件参数，基本与pro相同。

下面开始烧录OpenWrt的系统。由于我对内核比较熟悉，我直接是从仓库构建的openwrt。如果对于openwrt不熟悉的话，可以从http://downloads.openwrt.org/下载对应的版本，但是需要注意的是由于openwrt属于嵌入式系统，要想让系统在板子上运行起来，我们需要下载对应的版本的img。

如果你的硬件不在http://downloads.openwrt.org/barrier_breaker/14.07/这个列表中，又有些技术基础的话，最好从仓库clone，自己构建，可以省很多时间！

因为官方默认的镜像，不带usb-mod,也就是不支持usb转Ethernet接口，这个在我初期构建的时候麻烦很大！

git 仓库地址：https://github.com/openwrt-mirror/openwrt

将仓库pull下来之后，我们可以从linux的仓库中通过apt-get/yum方式安装下载最新的交叉编译环境包。下面的图是apt的，关于yum的，可以使用yum search进行查找，名字应该差不多。

sudo apt-get install gcc
sudo apt-get install g++
sudo apt-get install binutils
sudo apt-get install patch
sudo apt-get install bzip2
sudo apt-get install flex
sudo apt-get install bison
sudo apt-get install make
sudo apt-get install autoconf
sudo apt-get install gettext
sudo apt-get install texinfo
sudo apt-get install unzip
sudo apt-get install sharutils
sudo apt-get install subversion
sudo apt-get install libncurses5-dev
sudo apt-get install ncurses-term
sudo apt-get install zlib1g-dev
sudo apt-get install gawk
sudo apt-get install asciidoc
sudo apt-get install libz-dev

我们可以像平时编译内核那种方式，通过make menuconfig方式，裁剪内核，最主要的是进入这个界面，我们要指定构建内核的芯片，和构建目标。也就是Target system和Target Profile ，Target Images我们选择ext4系统与GZip Images就足够了。

然后在下面的Iuci中选择需要构建的包，因为Openwrt管理界面是网页形式，所以要选择一个http服务器，我们默认自选uhttpd即可，如果又选了其他的服务器，可能存在登陆错误的现象！如果你需要Usb一系列设备，就需要在Kernel Modules中编译相关模块。

最后保存设置，使用make V=99开始编译，第一次编译需要下载很多外部库，总的时间3h左右，如果不清理的话，下次编译时间会大大缩短。

———————-

现在讲img烧录到板子的SD中，并让板子从SD启动就好。

方案一：

使用自己编译的img，直接dd刻录。http://www.lemaker.org/resources/9-39/banana_pi_quick_start_guide.html

Run the sudo dd bs=4M if=[path]/[imagename] of=/dev/sdx command to write image file to SD card. Wait patiently to successfully complete writing. Please note that block size set to 4M will work most of the time, if not, please try 1M, although 1M will take considerably longer.

方案二：

使用官方提供的镜像，uboot

一般情况我们需要手动分区，然后在对于每个分区进行操作，比如我们操作的SD卡是/dev/sdb
因为这个板子是全智A20，我们要根据官方的指导文件，进行分区。

首先fdisk /dev/sdb

进入使用o清除所有分区！

所以我们必须把SD卡的前1M空出来，然后存放uboot的SPL头，放在seek=8 bs=1024处，seek即为偏移量。然后在开始地址1024后存放uboot，uboot烧写完成，再分一个区存放ext4，也就是rootfs的Openwrt实体！

$dd if=/dev/zero of=/dev/sda bs=1M count=1
$dd if=openwrt-sunxi-Bananapi-u-boot-with-spl.bin of=/dev/sda bs=1024 seek=8
//之后使用fdisk分区，分成sdb1 sdb2
$fdisk /dev/sda

a)n->默认p->默认1->默认2048->34815
b)n->默认p->默认2->默认34816->默认剩余全部，再次p查看分区，但sdb1要改为fat格式； t更改分区类型，指定分区号，指定类型，L查看所有分区类型，fat的类型编号为c；w保存所有操作。

$mkfs.vfat /dev/sdb1
$mkfs.ext4 /dev/sdb2
$mount /dev/sdb1 /media/pi/1
$mount /dev/sdb2 /media/pi/2

我们需要的文件主要是
openwrt-sunxi-root.ext4
openwrt-sunxi-uImage
sun7i-a20-bananapi.dtb
openwrt-sunxi-Bananapi-u-boot-with-spl.bin
openwrt-sunxi-Bananapi-uEnv.txt

在1中我们主要是在1中新建一个文件，打开后添加openwrt-sunxi-Bananapi-uEnv.txt中的内容，保存为boot.cmd，然后

$mkimage -C none -A arm -T script -d boot.cmd boot.scr

在文件夹1中直接拷贝sun7i-a20-bananapi.dtb和openwrt-sunxi-uImage文件，两个文件的文件名要和刚才boot.cmd中的相同；

$dd if=/xxx/openwrt-sunxi-root.ext4 of=/dev/sdb2 bs=1M //xxx替换为自己的路径

然后烧写完毕，我们可以连接串口进行通讯，需要特定的硬件，我主要应用实验室特殊的条件，直接请教硬件大神！
之后我们可以使用ssh方式将板子与电脑直接使用网线连接！

之后就可以随意配置了。

附一张烧写好的板子，由于官方送了外壳，我基本就把他安装好了。运行状态图：

———————–

官方默认不编译的库，我们就要手动编译，我们首先下载这个板子的官方编译环境具体包的名字：OpenWrt-SDK-sunxi-for-linux-x86_64-gcc-4.8-linaro_uClibc-0.9.33.2.tar.bz2

然后把需要的package放到解压后这个文件夹下的package下，使用make menuconfig编译。编译完成后在bin下面会找到ipk包！

然后我们可以通过vsftpd方式传到路由器中，通过opkg install 安装。至于如果你需要基于luci-app-*的包，需要搜索或者到http://sourceforge.net/projects/openwrt-dist/查找。

之后我们登陆路由器官方网页界面进行配置。这个需要我们指定路由器网关！

关于shadowsockets 与 chinadns设置：

http://www.tuicool.com/articles/fauueym

https://github.com/shadowsocks/openwrt-shadowsocks

https://github.com/aa65535/openwrt-chinadns

这次嵌入式烧板子，让我对于板子不再陌生，原来kernel与硬件接触如此紧密！

No comments »

Posted in Code杂谈

Tags: BananaPi Openwrt

Archive for the ‘Code杂谈’ category

Combination Sum 思路

内核页表和进程页表

vmalloc区发生page fault

内存条物理结构分析

Update 2015-07-04

设计弊端：

字符编码浅析

从0构建一个基于BananaPi的OpenWrt系统

方案一：

方案二：

Recent Posts

热门文章