# kernel_hash **Repository Path**: liushichuan/kernel_hash ## Basic Information - **Project Name**: kernel_hash - **Description**: 通过加载模块实现hash表 - **Primary Language**: C - **License**: GPL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2017-11-30 - **Last Updated**: 2020-12-18 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 功能描述 ># 1.1 功能需求及实现要求 >## 通过内核模块装载一个系统全局哈希表表 >模块初始化阶段创建一个空哈希表，初始化表大小为 8； >key 和 value 类型均为字符串； >## 哈希方法 >自选哈希算法，尽可能保证哈希值均匀分布，并选择高效算法； >## 冲突处理方式 >使用拉链法解决冲突，并使用内核哈希链表实现（hlist） ； >## 方法实现 >分别实现哈希表的插入，删除、查找方法； >## 系统调用 >(可修改内核增加系统调用实现，也可以在内核模块中直接修改现有系统调用表，>覆盖原有 >系统调用，建议使用后者) >将哈希表提供的方法添加到系统调用表中，可以直接修改系统调用表，不用修改 >内核重新编译； >## 表大小自适应 >（选用合适的方案对哈希表进行适时扩展及收缩） >当负载因子大于 0.9 时以现有大小的 2 倍扩展哈希表，负载因子小于 0.1 时收>缩为 >原始大小的一半并且始终大于 8； >## 并发 >哈希表选择但不限于使用自旋锁、读写自旋锁、信号量、互斥锁、原子操作实现 >并发访问； ># 2 哈希表使用 >## 用户空间调用(未实现内核添加系统调用功能时直接在内核模块实现哈希表操作) >在用户空间使用系统调用的方式使用前面实现的内核哈希表； >## 性能测试 >(添加系统调用后在用户空间实现，否则直接在内核模块实现。若未实现并发访问>控制，仅 >测试单线程性能) >在单线程及多线程环境下分别测试哈希表插入，删除及查找的性能并生成对比测 >试报告； >在多线程环境下测试并发读写性并生成性能报告； >所有测试数量在千万以上； # 运行环境 ``` ubuntu16.04(x86 64) linux version(4.4.0-78) gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.5) ``` ## 使用方法 根目录执行make，生成.ko文件。 执行　sudo insmod hash_module.ko　装载模块。 顶层目录执行./gen_test.sh编译test/下文件并在顶层目录生成可执行文件put get del。 ## 已完成　 1. 插入，查询，删除。 2. 高速缓存，可以定义　USE_CACHE　宏开启。 ## 根据已完成内容的优化与建议 1. kmalloc等分配可能失败,在必须要分配空间时首先分配空间，失败则处理，避免做了很多事后才分配失败，前面的都白做了。 2. 通过SLAB来分配内存，其内部实现的空闲链表可以缩短频繁分配释放时的时间开销。不过需要对象大小一致，代码里面是用高速缓存对hlist节点进行分配。 3. 见未完成第三点扩充空间，这只是个猜测（如果可以实现就是建议）。 ## 待完成 1. 并发（网上和书上看了很多资料，读写锁和顺序锁分别适用于读者数远大于写者和写者数远大于读者，好像不适用。自旋锁的话我认为更浪费处理器性能，在争用严重时还得考虑饥饿问题。mutex的话，直接对锁住整个操作代码，锁太大了，争用就更严重。所以并发还没完成，可能需要锁的混用，还需要继续学习）。 2. 动态调整表大小。目前的想法是取模，通过动态调整模的大小使hash值可以落到表下标的范围内，模的大小为质数使hash值可以更均匀分布(相比于合数)。因此动态分配表的大小可以分配为质数的大小或2的幂那么多页。如果是2的幂，就使用小于这个值的最大质数，为了避免出现计算质数我在代码里面加入了一个质数表，和题目要求的8-16-32...的收缩方式相比配，如果要扩充表为两倍则将质数表的下标加2，对应的值就是扩充后小于2的幂的最大质数。目前最大的问题是扩充或收缩时用什么方法可以避免拷贝，有一个想法是分配物理页之后不映射，而通过用什么方法使得新分配的空间和之前的空间的线性地址连续。 ## 针对待完成项的观点 1. 并发可考虑自旋锁与读写锁，内核的读写锁偏向于写者少而读者多的情景，可提升并发访问性能，实际上并不存在写者饥饿的状况，写者过多仍会导致读者等待时间过长的问题。 2. 动态调整的一个方向是，从内核线性地址空间保留出一个区间，构建这个线性地址对应的页表并挂物理页，收缩和扩充可以通过页目录项标志进行判断，操作页表项而不必复制真实数据，可以节省数4096倍甚至更多的拷贝时间。 --- # Kernel hash系统调用性能测试(perf)报告 ## 测试环境 测试工具：performan event (perf) 主机环境：ubuntu16.04 – linux4.4.0-78 (Vbox下) ## 测试结果 |方法|线程数|总次数|总时间(ns)|平均时间(ns/t)| |:---|:---|:---|:---|:---| |插入|1|1千万|8,926669547|892.6669547| |查找|1|1千万|9,485236925|948.5236925| |删除|1|1千万|10,025164335|100.25164335| >说明 不重复随机数： 在应用层malloc一块 1千万 * sizeof(unsigned long) byte大小空间用作数组使用，并初始化为0 ~ 9,999,999。以当前时间为随机数种子生成0 ~ 9,999,999随机数，在扫描整个数组的过程中将当前下标的数组值与随机下标的数组值进行对调。 用作增删查的键值对字符串（删只用到键），即键值是一致的。 duration:Xs Yns格式打印信息是调用linux C时间函数clock_gettime计算的调用系统调用的时间间隔。没有包括随机数组的初始化和乱序时间。 ## perf 打印信息 no.1 插入 ```shell duration:7s 745398946ns Performance counter stats for './rand_put': 8903.872302 task-clock (msec) # 0.997 CPUs utilized 98 context-switches # 0.011 K/sec 1 cpu-migrations # 0.000 K/sec 106 page-faults # 0.012 K/sec cycles stalled-cycles-frontend stalled-cycles-backend instructions branches branch-misses 8.926669547 seconds time elapsed ``` no.2 查找 ```shell duration:8s 350631750ns Performance counter stats for './rand_get': 9464.163374 task-clock (msec) # 0.998 CPUs utilized 424 context-switches # 0.045 K/sec 1 cpu-migrations # 0.000 K/sec 617 page-faults # 0.065 K/sec cycles stalled-cycles-frontend stalled-cycles-backend instructions branches branch-misses 9.485236925 seconds time elapsed ``` no.3 删除 ```shell duration:8s 870076124ns Performance counter stats for './rand_del': 9996.615659 task-clock (msec) # 0.997 CPUs utilized 241 context-switches # 0.024 K/sec 1 cpu-migrations # 0.000 K/sec 106 page-faults # 0.011 K/sec cycles stalled-cycles-frontend stalled-cycles-backend instructions branches branch-misses 10.025164335 seconds time elapsed ```