Archive for 算法-编程

FinalizeRunMode,检查了一下daemon和运行的模式是否匹配,然后模式保存到全局变量run_mode中。 StartInternalRunMode,这个是判断是否是一些打印相关的模式,如果是这些模式,调用相关的方法,这些方法就不看了。比如列出模式,打印软件帮助等这类的模式。 GlobalsInitPreConfig,先调用TimeInit,初始化了一个当前时间的自旋锁current_time_spinlock,具体干啥的还不知道,调用tzset设置时区变量。之后调用SupportFastPatternForSigMatchTypes,初始化sm_fp_support_smlist_list,是个链表,默认保存了DETECT_SM_LIST_PMATCH,优先级为3,具体不知道这个是干啥的。之后调用SCThresholdConfGlobalInit,我看主要是初始化了解析Thresholding的正则表达式。 LoadYamlConfig,加载配置文件,调用ConfYamlLoadFile,这个里边主要利用了yaml库解析配置文件,没查这个库具体函数,函数名很容易知道是干啥的。保存了一下配置文件的目录,主要是调用ConfYamlParse,把配置读入ConfNode结构的树里边,有父节点,然后是个链表。所以也不单纯是个树。没太仔细看具体解析流程,单纯就是读到树里了。 typedef struct ConfNode_ { char *name; char *val; int is_seq; /**< Flag that sets this nodes value as final. */ int final; struct ConfNode_ *parent; TAILQ_HEAD(, ConfNode_) head; TAILQ_ENTRY(ConfNode_) next; } ConfNode; ConfDump模式单纯就是把刚读如的链表树再打印一下。 查了一下“vlan.use-for-tracking”的值,这个参数看了一下配置文件介绍,基本用不到。 ConfGetBool获取配置中的bool值,先调用ConfGetValue获取值,里面通过ConfGetNode通过name找到node,key通过“.”进行分割,然后ConfNodeLookupChild查找当前等级的链表。看到这里发现,用c实现个json解析啥的好像也不太难啊。 SetupUserMode(&suricata);这个是设置非system模式的情况下,把日志和数据目录设置到当前目录,函数没跟进取,暂时不看了,这些模式不是看的重点。 SCLogLoadConfig应该是设置日志了,通过verbose设置等级,verbose通过参数有几个v来设置,等级为SC_LOG_NOTICE + verbose,看了一下SCLogLevel, 最高可以有5个v。获取logging.outputs的配置保存到outputs,SCLogAllocLogInitData初始化SCLogInitData,这个数据结构主要保存日志等级,格式,写到什么地方等信息。获取配置文件里"logging.default-log-level"配置的日志等级,然后跟参数里的比较,取等级最低的,保存到global_log_level。如果等级跟配置文件一致,使用配置文件的format。将outputs配置文件保存到变量,这些主要是日志的方式,console/file/syslog,没有细看,看了一下file的,这个用的多,调用SCLogInitFileOPIface,append模式打开文件,方式里面有个锁变量,注释说用来切割日志时候用的,然后调用OutputRegisterFileRotationFlag,把需要分割日志的这个flag都保存到output_file_rotation_flags里了,这个也是个链表。这里暂时有个疑问,我看flag初始化的时候没设置值,不知道后面会不会设置,还是我漏了。这里保存的是指针,可能不是漏了。日志等级还比较了outputs里的等级,取最低等级。然后调用SCLogInitLogModule,这个在之前调用过,之前可能是终端输出,现在可以配置文件了。 LogVersion,打印版本。 UtilCpuPrintSummary,打印cpu个数信息。 ParseInterfacesList,这里是看启动参数是否设置网口,如果设置会在配置里加一个xxx.live-interface的配置项,没设置就调用LiveBuildDeviceList,参数是模式,也是配置文件里的顶级名称,使用这个参数获取配置,如果interface为default,则忽略,这个是默认配置,其他情况调用LiveRegisterDeviceName,把接口插入队列,这个跟参数解析一致。所以看起来好像启动参数不加网口也可以啊。

Continue

SuricataMain是入口函数,先调用SCInstanceInit,把SCInstance变量数据清0,不知道为啥以及memset0了,还要变量名再置0一次。SCInstance就是suricata进程相关的一些变量,其中一个有意思的事是还保存了执行命令的文件名,看这个感觉可能直接改二进制的名也没问题的。run_mode设置为RUNMODE_UNKNOWN。 之后调用InitGlobal,主要设置suricata_context变量,这个变量在rust-context.h文件定义,全是操作函数,具体赋值的函数还没有看,这个先过了。 在InitGlobal里调用rs_init,这个看了一下好像是给rust调用用的,sc赋值给rust里的sc,这样在rust里可能就能试用context的函数了,我看在core.rs中都是contxt里的函数声明。具体c和rust怎么交互的,我还需要再看看。粗略看了一下,协议判断好像都在rust里写的。 然后初始化engine_stage为0,这个变量为原子变量,原子操作都定义在util-atomic.h,没细看怎么实现的,先知道干啥的吧。这个变量注释说的是表明引擎是在初始化还是在处理数据包了,总共包括三个状态SURICATA_INIT,SURICATA_RUNTIME and SURICATA_FINALIZE。 SCLogInitLogModule,初始化日志模块。没细看,参数传的NULL,使用默认日志系统。info等级打印到console,可以设置正则过滤,这几个设置项都可以通过环境变量设置。 之后ParseSizeInit,初始化了一个正则匹配器parse_regex,这个正则表达式不知道干啥的,看后面好像是把字符串“10kB,10GB”类似的转换成具体的大小数据,可能是配置文件之类的解析,先过了。 之后RunModeRegisterRunModes,跟函数名一个意思,注册的模块还没看。看配置文件就知道四五种,没想到还挺多。注册到数组runmodes。找了几个看看,发现就是list-runmodes里的模式,把对应的模式和具体模式的方法进行注册。每种模式都是调用RunModeRegisterNewRunMode注册到runmodes数组保存。RunModeFunc是对应的模式函数,这个先没看,等用到再看 之后ConfInit,初始化配置模块,ConfNode是一个列表,里面是kv键值对。起始就是初始化一个链表。 到这InitGlobal就结束了。 ParseCommandLine解析命令行参数,列出了所有参数,pfring或pfring-int参数启动pfring,设置run_mode为RUNMODE_PFRING, 如果后面跟参数,设置pcap_dev,这个应该是网口名了。LiveRegisterDeviceName就是把网口插入到一个链表里,相当于注册了。变量名pre_live_devices。capture-plugin还能设置插件名,这个模式RUNMODE_PLUGIN,可能dpdk得插件实现。netmap参数只能设置一次,看来只能在一个网口使用,而且还不能多个模式。 suricata --list-app-layer-protos 列出七层协议 suricata --list-runmodes 列出模式 list-keywords 关键字 -l设置日志目录 -i和af-packet都走af-packet,-i如果支持,默认也走af-packet。 这些参数在help里都有,暂时不看了,到时候回来看具体设置了什么参数,因为我看的代码比较新,之前版本的还有没有的参数。

Continue

最近接入他们大学的课题程序,很多都是用matplotlib画图,展示最终的精确度之类的。 然后我用pyenv+virtualenv安装那些程序的依赖,然后matplotlib需要_tkinter,这个还需要系统安装,虽然能装,但是挺费劲,还有种方式可能需要重新编译python,也是麻烦。网上搜索发现可以不使用的方法,每次装一次找一次,决定记录一下了。 直接import matplotlib.pyplot as plt 会报错ImportError: No module named _tkinter, please install the python-tk package 一般都是用plt.show()方式直接展示。我给改成plt.savefig()报错图片了。 网上找到的方法 在import之前加入两行:import matplotlib matplotlib.use('agg') 然后就可以了。好像是选了matplotlib里gui别的显示方式,就不依赖_tkinter了

Continue

最近又心血来潮研究图形学去了,啃3d开发去了。n年前研究过,那时候心性不行,感觉太难了,搞了一半就放弃了。现在又准备重新研究了,目标定位到OpenGL es上了。 主要OpenGL ES支持手机平台,而且属于opengl的子集,没有历史包袱。虽然可能很多高级特效之类的不支持,但是应该也用不到,可能我学习的速度还赶不上硬件和opengl发展速度,考虑这些就考虑多了。从网上介绍来说es是可以在桌面上用的,但是网上搜了一下都需要模拟器。而我看的书是《opengl es 3.0 编程指南》这个书只是说libglesv2的lib版本,这个我就很疑惑。而且还推荐了很多桌面上的模拟器,用来跑示例,我这还想着桌面的也用es写,但感觉模拟器应该也能一起编译打包。 然后我搜了一下lib,发现libgles2已经安装了,搜的libgles,好多包安装过了。然后我看了一下头文件,GLES3/gl3.h也有。libegl也有安装。我就直接cmake了示例代码,然后运行成功了。 所以具体是这个包起作用,还是还有别的包,我也不太清楚,也懒得验证了。然后我就通过包信息里的官方网址,发现还是NVIDIA的github。里边头文件确实有gles3的,看了readme也没说支持3.0的es。大概率是支持了。 具体windows可能是需要模拟器了吧,或许也有显卡公司写的lib。

Continue

临时看个问题,对matplotlib没有了解,基本纯网上搜了搜。暂时先记录一下。 是使用 pandas读了一个excel表,然后加了index字段,是个日期,数据保存在变量df里,可以直接调用df.plot()进行画图,我是有点震惊的。这是因为这几个库联用的多嘛。画出来的图横坐标日期不能全显示,然后想全显示出来。 第一反应就是日期太长了,然后找可以调整角度的函数,用xticks修改角度,不好用。然后发现xticks可以指定横坐标显示位置,显示映射啥的。 x=np.arange(0,12,1)生成一个选择的映射,label传入全部十二个日期。然后就显示全面了。plt.xticks(x, mon, rotation=90) xticks参数还可以指定Text类型的参数,进行文本样式的设置。 最近让搞R语言,在看R语言画图的功能。因为看我对python的matplotlib,numpy,pandas这些库都没经验,领导之前会用R,就让我直接写R了。感觉搞这些工具,但不会统计的东西,搞起来总感觉是在隔靴子挠痒。

Continue

看网上教程,最后选择了这种rpc调用的方式,这种方式可以提前启动R虚拟机,R程序造成的崩溃不会影响到java程序。另一种方式是JRI,全名是Java/R Interface 第一步R安装Rserve,这里有点问题就是最好root权限安装,我看文档这种方式需要源码安装,并且有$R_HOME/bin权限。所以直接root启动r然后安装了,install.packages("Rserve")。这里试了一下R INSTALL 好像只能安装本地的包。最后决定安装官网的最新版本,目前还没在CRAN中。install.packages("Rserve",,"http://rforge.net") 第二步启动R server,命令行执行 R CMD Rserve,这个就是上边说的daemon模式,文档说只支持unix系统,windows还不行。默认启动端口6311.看参数好像只能指定端口,不支持指定IP。看文档只能通过配置文件去指定是否允许远程访问。写一行remote enable就行了,我没在默认/etc/Rserv.conf 改,直接参数指定的文件。 第三步java客户端连接,这里需要两个jar包,官方网站能下载,看版本有点老,安装包也带。目录在 /home/xx/R/x86_64-pc-linux-gnu-library/4.0/Rserve/java/ 包的安装目录下。然后javac -classpath ./REngine.jar:./Rserve.jar:. test.java,测试运行一下没啥问题。数据类型的转换问题还需要详细研究一下。

Continue

代码基本网上搜的,没啥贴的,写一下思路,有需要的自己网上搜就行了。主要是自己看的电子书是扫描版的pdf,里边全是图片,超级大,好几百M。之前找了一圈,靠谱软件需要收费,不靠谱个人软件只能windwos下用。于是自己搞吧,发现也不太难。 第一步是把pdf提取图片 用到pymupdf库,这个是封装的c的接口,感觉写个pdf软件也不难啊,都有开源库,不知道为啥他们还收费。我提取图片发现,好多水印图片是直接用pdf编辑软件加上的,导致水印可以直接从提取的图片里边删掉,这个挺好。 第二步,把图片二值化 这里用到opencv,用到cv2.threshold。这个阈值不太好设置,可以使用cv2.THRESH_OTSU,提取一个分析值,但是这个不是最优的,有的书是半彩页的,书边会有浅色的背景之类,或者重点颜色等。这个有分析建议值之后,还需要自己试一下哪个值比较好。 第三部,把图片生成新pdf 这个还是用pymupdf库,基本都差不多。 没想到的是压缩率还挺低,一百多MB的pdf能压缩成十多兆。可能也是之前的pdf质量比较高吧。但是我看了一下压缩后的,清晰度一点不减少。有背景色的地方,选择阈值合适,背景色也都过滤掉了,文字不受影响。

Continue

libpmem有一个初始化操作在函数pmem_init里, 里边有初始化的一系列操作,东西太多,主要就是查架构,定下以后使用的函数等。我这里根据当前CPU架构,只看了需要用到的内容. 首先通过pmem2_arch_init(&info);初始化info。在libpmem2/x86_64/init.c里,pmem_cpuinfo_to_funcs(info, &impl);这个函数是判断flush支持的指令,从最低级开始判断,如果高级的支持,就直接替换。这个我看过cpuinfo是支持clwb,所以info->flush = flush_clwb; info->flush_has_builtin_fence = 0; info->fence = memory_barrier;。这里边很多环境变量的获取判断,都是调试或者制定模式的,这里先不管这些。SIMD支持avx512f,所以也直接看这个了,初步看着这个好像是为了MOVNT准备的就是ntstore,主要就定义一个memmove_nodrain。然后这里info就初始化完了。 flush_clwb,为flush_clwb_nolog(addr, len);在libpmem2/x86_64/flush.h里定义的: static force_inline void flush_clwb_nolog(const void *addr, size_t len) { uintptr_t uptr; /* * Loop through cache-line-size (typically 64B) aligned chunks * covering the given range. */ for (uptr = (uintptr_t)addr & ~(FLUSH_ALIGN - 1); uptr < (uintptr_t)addr + len; uptr += FLUSH_ALIGN) { pmem_clwb((char *)uptr); } } FLUSH_ALIGN为64,所以其实数据结构能对齐64B应该是好的,但是想了想应该没办法对齐。所以还是得计算对齐地址,但是小数据可以不需要for了,这个可以定制。pmem_clwb为CLWB void _mm_clwb(void const *p);这个gcc应该是支持的,等查一查,官方为了兼容,直接汇编实现的。memory_barrier为_mm_sfence();这个clwb是必须的。 回到pmem_init,初始化了Funcs系列函数,这些跟info里的一样的,不在写具体逻辑到这里了。最后pmem_os_init(&Is_pmem);这个就是第二篇里边的判断函数的初始化,暂时不细看了。 pmem_flush就是调用的flush_clwb,pmem_drain就是调用的memory_barrier,pmem_persist就是先flush后pmem_drain,pmem_memcpy就是先memmove_nodrain,然后drain,这里的特殊env控制就不管了。pmem_memcpy_nodrain就是只是少了pmem_drain这一步。pmem_memcpy_persist这个是不管env的肯定drain. flush_empty这个不干事,只是通知pmemcheck。 还剩最后一块memmove_nodrain = memmove_nodrain_avx512f_clwb。这个我之前看的时候,搜代码都搜不到,还好统看了一下代码文件,发现是个模板搞的。MEMCPY_TEMPLATE(avx512f, clwb, /* */)。 pmem_memcpy_nodrain调用的时候,flag传了一个0,所以没有flag的,调用的是memmove_movnt_avx512f_clwb。长度小于256单位应该是Byte吧,因为是传过来的len,使用memmove_mov_avx512f_clwb,其他情况是通过flag来决定的,这个可以通过pmem_memcpy可以传参数,属于最灵活的调用方式了,也可以指定是否pmem_drain。 memmove_mov_avx512f_clwb在libpmem2/x86_64/memcpy/memcpy_t_avx512f.c里,先通过if ((uintptr_t)dest - (uintptr_t)src >= len)来判断两块内存是否相交,然后选择不同方法。这里可以优化,想了想我要写的代码没有重叠内存,所以可以优化。看memmove_mov_avx512f_fw里主要就是不同长度选择使用不同函数就复制数据。我查看小数据的复制,是用的转成uint来进行赋值拷贝的。也用了循环展开优化数据复制。这里边的持久化用的pmem_clwb,这个是为已经对齐的地址准备的,看来我能想到的官方肯定都想到了啊。mov的指令都是使用的avx指令load和store. memmove_movnt_avx512f_clwb在memcpy_nt_avx512f.c里,这里也判断了数据重叠问题,但是没看懂的是这里需要flush,但是不需要barrier.我觉得不应该正好反过来吗。。这里用的是load和stream指令来移动数据,移动完跟想的一样是没有flush的,flush是为的开头结尾的小数据准备的。 两种移动数据都不需要barrier,可能是为了集中控制,把是否barrier的权限放到接口里决定。 现在具体看看也没有多少可以优化的,一个是flush的for循环,一个是memcpy的判断内存重叠的问题。不过每次减少两个判断,收益也不少了。再一个确认一下初始化是否算时间,把初始化的时间也优化了。 后期移植的时候又发现一个,在avx实现的拷贝过程中,是按2kb的数据块进行的ntstore。比赛最高1kb,所以这里可以去掉,从1kb开始判断就行了。

Continue

libpmem主要通过pmem_map_file封装来进行mmap的映射,首先通过util_file_get_type获取文件类型,主要区分文件是否存在,DAX设备文件。比赛用的fsdax,这个主要通过mmap来实现的寻址操作,挂载路径为/dev/pmem/。还有devdax,这个好像是给虚拟机分配的时候用这个模式,挂载路径为/dev/dax/。还有sector和raw模式。 文件支持的flag有(PMEM_FILE_CREATE|PMEM_FILE_EXCL|PMEM_FILE_SPARSE|PMEM_FILE_TMPFILE),dax设备支持的flag有(PMEM_FILE_CREATE|PMEM_FILE_SPARSE). 然后判断是dax后,判断len必须是0或者文件大小。open_flags默认有O_RDWR,如果flag有PMEM_FILE_CREATE则open_flags添加O_CREAT。后边判断传了len必须有PMEM_FILE_CREATE,len为0必须没有PMEM_FILE_CREATE.PMEM_FILE_TMPFILE必须有PMEM_FILE_CREATE.之后os_open(path, open_flags, mode)打开文件。如果flag带有PMEM_FILE_CREATE,则os_ftruncate文件,没有PMEM_FILE_SPARSE,则os_posix_fallocate(fd, 0, (os_off_t)len))文件。这里看不太懂,看手册这俩函数基本是等价的。如果没有PMEM_FILE_CREATE,则获取真是文件大小,重新复制len。 然后pmem_map_register,在pmem_posix.c里,调用util_map,传了MAP_SHARED。在common/mmap.c里 肯定有PROT_READ|PROT_WRITE,然后调用util_map_hint,这个主要就是确定mmap地址的,调试有参数可以固定虚地址的,这个看书看过。基本用不上。好像是通过mmap MAP_PRIVATE找一个mmap对齐的地址。 req_align为零,align = GIGABYTE。#define GIGABYTE ((uintptr_t)1 << 30)。这里脑袋有点浆糊了,不具体看就是找个一个对齐地址,然后后边用来mmap pmem文件使用,先这样吧。然后util_map_sync,地址是刚返回的地址,在这里mmap了。 然后复制len和is_pmemp。关闭fd,就结束了。pmem_is_pmem里边东西还挺多,有调试相关,乱七八糟一堆,主要是在初始化指定默认判断函数,然后在这里如果有env或者其他情况进行函数转换,然后掉函数看结果,不细看了,因为比赛肯定为pmem。 其实总结一下流程很简单,先打开文件,设置文件大小。然后mmap寻找一个对齐地址,最后真正mmap,返回。

Continue

参加了个阿里的kv数据库比赛,接触到持久化内存的概率,到现在对这里理解的也不是太深入,只管总结一下。看了官方的书,还有一些代码和官方视频,但是为了参加比赛,还是觉得研究一下代码。初步看了看发现能在比赛上优化的地方还挺多的,所以决定慢慢总结和移植一下。 持久化内存(Persistent Memory)我看网上好像概念已经老早就有了,我是第一次知道,也记不住讲不清。总的来说就是可以掉电不丢数据的内存,是嫌ssd慢了,又出来一个算是ssd和内存的中间层。还有两种模式,可以当普通内存用,相当于扩展普通内存的容量。或者当持久内存用,可以保证掉电不丢数据和快速的读写速度。 libpmem是intel开发的持久化内存开发组件(Persistent Memory Development Kit)里的一个库,属于底层库,libpmemobj等库都是在这基础上开发的。比赛用到,基本不考虑libpmemobj这库,集成太厉害了,libpmem我大体看了代码发现也可以修改移植,能优化不少。而且因为我c语言经验不多,看了源码后发现能学很多东西。所以决定阅读总结加移植代码。 大体的使用思路就是,基于系统调用mmap进行pmem的进程空间地址的映射,这里是内核原生支持了。所以这玩意应该出了很久了,才刚听说,感觉阿里应该属于用的比较早的。之后就跟正常使用内存一样了,而这些操作都是在用户空间,所以效率理论上还有优势,虽然本身速度赶不上内存。持久化操作需要将cpu cache里的数据踢出到内存(evict),刷新到持久内存上。 基本情况就这样,下边看几个基础文件。学到很多代码 core/util.h util.c 这俩都是常用函数集合 #define force_inline __attribute__((always_inline)) inline #define NORETURN __attribute__((noreturn)) #define barrier() asm volatile("" ::: "memory") 第一个从名字就看出来是强制函数inline,第二个是有时候写的分支没有返回时编译器会有报错,这个可以告诉编译器不要报错。第三个是内存栅栏。 typedef uint64_t ua_uint64_t __attribute__((aligned(1))); 能够指定最少字节对齐数,受连接器限制,不会超过连接器大小。感觉没啥用,但是也可能以后用上,学到东西了。 util_setbit, util_clrbit这个是位操作,这个是会的 util_is_pow2, return v && !(v & (v - 1)); 判断是否是2的幂 __builtin_ctz,__builtin_clz,这个是判断一个数,从开头或者从结尾有多少个零的,厉害了。 其他的就没啥了,看看util.c util_is_zeroed检查内存为0,应该用不到,记录下。util_checksum_compute,这是是计算一块内存的checksum,已移植,不知道会不会比hash快,这个应该比hash准确,但是比赛还是讲究速度,到时候试试。算法好像是Fletcher64。 valgrind好像能模拟cpu环境,调试程序的,好像书里有写,没太看内容,先记录。 Mmap_align好像用来分配对齐的,这里不知道干啥的,先跳过记录。linux下直接分配的Pagesize = (unsigned long) sysconf(_SC_PAGESIZE) util_concat_str连接字符串,没用记录.util_localtime获取时间,没用记录 其他的基本用不上了,主要看书看到原理的地方,发现checksum相关内容,有用到,就搜了一下源码,看到这些代码。

Continue