Galex

zsmalloc分配器源码分析

背景

在内核中,slab分配器用于分配较小块内存,它将多个相同大小的对象放在同一个内存页中,但这些对象可能不能正好占满整个内存页,从而产生碎片造成浪费,于是内核尝试为对象分配多个物理连续内存页从而使碎片尽可能小,但在低内存设备上要分配多个连续内存页可能十分困难,特别在系统运行较长时间后,这变得几乎不可能。最坏情况下,当对象大小略大于PAGE_SIZE/2时,每个内存页接近一般的内存将被浪费。

所以,我们需要一种新的分配器,用于像vmalloc那样分配只要求虚拟连续的内存块。

Zsmalloc分配器尝试将多个相同大小的对象存放在组合页(称为zspage)中,这个组合页不要求物理连续[......]

Read more

自定义Android系统级权限组

Android安全模型基于Linux的权限管理,使用沙箱隔离机制将每个应用的进程资源隔离。Android应用程序在安装时赋予一个UID,UID不同的应用程序完全隔离。
另一方面,应用如果想使用某种服务,需要在AndroidManifest.xml中申请。比如,想使用网络的话,需要在AndroidManifest.xml中添加:

INTERNET权限将被映射到底层的GID。所以,一个应用有一个UID,可以有多个GID,来获得多个权限。
关于Android权限管理更详细的内容这里就不再赘述了,这方面的资料很多。直接进入正题,如何自定义一个类似于上面的INTERNET的系统级权限组?
我[......]

Read more

在Android 4.4.2上使用fuse开发自己的文件系统

有关fuse的介绍和下载可以访问http://fuse.sourceforge.net查看。本文主要介绍如下将fuse移植到Android 4.4.2,并开发一个简单的文件系统。

本文中使用的fuse是2.9.3版本,可以从sourceforge.net/projects/fuse/files/fuse-2.X/2.9.3/下载。

在Android源码中的external目录中创建一个fuse目录,并将fuse-2.9.3.tar.gz解压于此。

进入fuse目录,执行./configure命令,生成Makefile和include/config.h。

在fuse目录中[......]

Read more

约瑟夫环问题

约瑟夫环问题应该是都熟悉的,传说著名犹太历史学家夫拉维·约瑟夫在犹太罗马战争期间,约瑟夫和其他40名犹太反抗者被困在了罗马人包围的洞穴。这些犹太人宁可自杀也不愿当俘虏,于是决定围成一个圆圈,并沿着圆圈每隔两个人杀死一个,直到最后只剩两个人为止。约瑟夫和他的一个朋友不想自杀,于是他计算出他和他朋友应该在这个圈子中的位置。

一般的,假设一共有n个人,首先从0号开始报数,每报到m-1的人就自杀,求最后一个存活的人的位置。

最笨的方法就是进行n-1次循环报数,它的时间复杂度是O(mn),下面的代码是这种方法的一种实现,用一个数组的每个元素代表一个人,元素的值表示他是否被杀。
[c[......]

Read more

Linux内核中使用红黑树的扩展特性实现区间树(Interval tree)

阅读3.0版本以后的内核源代码就会发现,新版本内核中的红黑树的实现与之前有所不同。新的实现提供了增强特性,用户可以在红黑树结点中符加一些数据结构来提供更多的功能。区间树就是一种增强型的红黑树。《算法导论》中有关于区间树详细的介绍。下图是取自《算法导论》的一棵区间树:

区间树

Linux内核中红黑树的实现中提到了这种特性,但没有详细介绍。下面就利用这种特性实现区间树。

按照《算法导论》中的讲解,区间树需要提供三种基本操作:查找、插入和删除。这里定义区间树的结构是:

先实现查找操作,因为它不需要修改结点信息:
[[......]

Read more

LVS扫盲–工作模式与调度策略

基于LVS的服务器集群主要由两部分组成,即负载调度器(Load Balancer,简称LB)和真正提供服务的服务器(Real Server,简称RS)。RS对外是不可见的,用户需要通过访问LB来获得服务,所以LB也称为虚拟服务器(Virtual Server),它对外公开的IP称为VIP(Virtual IP)。

LB接收到用户的请求后,会根据设置的转发模式和负载均衡调度算法将请求转发给RS,RS再将结果返回给LB或用户(返回给谁跟转发模式有关)。

LVS的转发模式主要有三种:网络地址转换(NAT,Network Address Translation)、IP隧道(TUN,IP T[......]

Read more

在 Linux Kernel 3.10 上安装 BLCR 0.8.5

BLCR官网上称0.8.5版本可以支持3.7的Kernel。因为3.10版本的Kernel一些接口有所改变,BLCR的 Kernel module 无法编译程序,某些地方需要修改。

1.执行过 configure 后 make会首先出现如下错误信息:

这是因为 Kernel 3.10 的函数 do_mmap_pgoff 的改变,需要做如下修改,将 cr_module/cr_kcompat.h 的252行:

改为:
[crayon-5a3518ba1[......]

Read more

« Older posts

Copyright © 2017 Galex

署名-非商业性使用-禁止演绎 3.0 | Creative Commons BY-NC-ND 3.0