(╯°□°）╯︵ ┻━┻

本文来源于 www.cnblogs.com，将代码实现改为了 c++文中的动态图也可以在：visualgo.net/zh/sorting 查看，还有其他算法的可视化！另一个可视化排序过程的网站：cs.usfca.edu/~galles/visualization/Algorithms.html，还包括数据结构的可视化 0、算法概述0.1 算法分类十种常见排序算法可以分为两大类： 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 0.2 算法复杂度 相关概念： 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。 时间复杂度：对排序数据的总的操作次数。反映当 n...

常用宏 include/openvswitch/util.h #119 typeoftypeof不是C语言本身的关键词或运算符，它是GCC的一个扩展，作用正如其字面意思，用某种已有东西（变量、函数等）的类型去定义新的变量类型。 1234typeof(int *)a, b; // 等价于 int *a, *b;typeof(a) c; // 等价于 int *c#define OVS_TYPEOF(OBJECT) typeof(OBJECT) offsetof获取结构体TYPE中某个成员MEMBER的偏移量（相对于结构体地址）。 1234567891011121314151617181920212223242526/* /usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h */#define offsetof(TYPE, MEMBER) __builtin_offsetof (TYPE, MEMBER)/* 类似于 */#define offsetof(TYPE, MEMBER) ...

支持短选项和长选项！ 短选项：形如-a，-v，以-加单个字符组成。-叫做选项标识符，选项标识符后面可以紧跟一个字符，这个字符叫做选项字符。选项字符后面可以紧跟一个或多个字符，这些字符叫做选项参数。如-lpthread选项字符为l，参数为pthread。 长选项：形如--all，--version，以--加一个单词组成，用=跟参数。如--data=format选项为data，参数为format。 12-lpthread -d format--data=format 短选项解析 getopt()1234567#include <unistd.h>int getopt(int argc, char * const argv[], const char *optstring);extern char *optarg;extern int optind, opterr, optopt; argc, argv为main函数参数中的argc,...

fmt格式化字符串，好像已经纳入C++20标准库，使用很方便！而且说是比printf还快~ 12345678910git clone --depth=1 https://github.com/fmtlib/fmt.gitcd fmt/mkdir buildcd buildcmake ..make -jsudo make install# g++ test.cpp -o debug -lfmt github 仓库，README中文档也较详细、使用简单 官方文档、有代码示例 fmtlog基于fmt的日志库，可以很方便的以fmt的方式格式化日志输出。 12345678git clone https://github.com/MengRao/fmtlog.gitcd fmtloggit submodule initgit submodule update./build.sh# g++ test.cpp -o debug -lfmt -lfmtlog-static #...

前面socket中创建的server只有一个主线程，只能连接一个客户端。要实现可同时连接多个客户端，有几种方法： 为每一个连接创建一个子进程处理。 为每一个连接创建一个子线程处理。 单线程，但使用select, poll, epoll等 IO 复用算法。 多进程并发每产生一个连接时，就创建一个子进程去处理，父进程只负责监听以及回收子进程！ 回收子进程不能放在父进程的循环逻辑中，一种办法是通过注册信号SIGCHLD捕捉函数，在信号处理函数中完成子进程回收。 1234567891011121314151617181. socket() // 创建监听套接字 lfd2. bind()3. listen()4. while(1) { cfd = accept() // 与客户端通信的 socket fd pid = fork() // 创建子进程 if (pid == 0) { // 子进程 close(lfd) // 关闭用于建立连接的套接字 lfd ...

在开始之前，我们先用一张图解释 linux 系统接收网络报文的过程。 首先网络报文通过物理网线发送到网卡， 网络驱动程序会把网络中的报文读出来放到 ring buffer 中，这个过程使用 DMA（Direct Memory Access），不需要 CPU 参与 内核从 ring buffer 中读取报文进行处理，执行 IP 和 TCP/UDP 层的逻辑，最后把报文放到应用程序的 socket buffer 中 应用程序从 socket buffer 中读取报文进行处理 注意图中的几个 buffer 缓冲区！ step1：网卡到ringbufferNIC 在接收到数据包之后，首先需要将数据同步到内核中，这中间的桥梁是 rx ring buffer。它是由 NIC 和驱动程序（内核）共享的一片区域，事实上，rx ring buffer 存储的并不是实际的 packet 数据，而是一个描述符，这个描述符指向了它真正的存储地址，具体流程如下： 驱动在内存中分配一片缓冲区用来接收数据包，叫做 sk_buffer； 将上述缓冲区的地址和大小（即接收描述符），加入到 rx ring...

topo1 topo2 topo3 topo4 topo5 topo1 1234567891011121314151617## 删除之前的配置文件rm /usr/local/etc/openvswitch/*rm /usr/local/var/run/openvswitch/*rm /usr/local/var/log/openvswitch/*ovs-ctl --no-ovs-vswitchd start --system-id=randomovs-vsctl --no-wait set Open_vSwitch . other_config:pmd-cpu-mask=0x02ovs-vsctl --no-wait set Open_vSwitch . other_config:dpdk-socket-mem="1024"ovs-vsctl --no-wait set Open_vSwitch . other_config:dpdk-init=trueovs-ctl...

名称 功能 dstat 查看各种系统资源的统计信息，可保存到文件！ iftop display bandwidth usage on an interface by host. 可指定TCP/UDP端口 ip show / manipulate routing, network devices, interfaces and tunnels ip link ip route iptables administration tool for IPv4/IPv6 packet filtering and NAT lsof list open files. 查看端口被谁占用 nc arbitrary TCP and UDP connections and listens. netstat 打印网络连接、路由表、连接的数据统计、伪装连接以及广播域成员 ss another utility to investigate sockets. tcpdump 抓包工具 telnet user...

Redis 是一个高性能的、键值对数据库，数据直接存储在内存中，只有需要持久化时才写入硬盘。 安装启动ubuntu 下使用 apt 安装的 redis 版本较老，可采用源码安装。 123456wget https://download.redis.io/releases/redis-6.2.6.tar.gz && tar xzf redis-6.2.6.tar.gzcd redis-stable && make -jmake testsudo make installsudo mkdir /etc/redis && sudo cp redis.conf /etc/redis # 复制配置文件到 /etc 安装完成后，会有以下命令可用： redis-cli: Redis客户端 redis-server: Redis服务器启动命令 redis-benchmark: 性能测试工具 redis-check-aof: 修复有问题的AOF文件 redis-check-rdb: 修复有问题的RDB文件 redis-sentinel:...

安装启动直接使用 docker 安装最方便！ 1docker pull onosproject/onos 启动，做端口映射，不需要的可以去掉 1docker run -t -d -p 8181:8181 -p 8101:8101 -p 6653:6653 -p 6640:6640 --name onos onosproject/onos 8181 - REST API 和 GUI 8101 - ONOS CLI 9876 - 集群内通信 6653 - Openflow 通信，OVS 连接控制器使用此端口（流表相关操作） 6640 - OVSDB，OVS 网桥、端口相关的配置 启用应用，用于控制OVS时，打开下面的应用，可通过UI 界面操作，也可在容器中用命令行方式启用。 12345678docker exec -it onos bashcd bin./onos-app localhost activate org.onosproject.openflow-base./onos-app localhost activate...

OVS基于DPDK的数据通路绕过了内核协议栈，并且做了很多优化，带来了一定的性能提升，但也引入了很多需要配置的参数，而且这些参数和性能密切相关。 参数说明 ovsdb 官方文档，下面的参数表格只是简单翻译了一下作用，仅供参考，具体信息还得看官方文档 ovsdb中存储着OVS所有配置信息，并按结构划分为一张张表TABLE，这里只关注其中与dpdk有关的配置参数。 Open_vSwitch Table table th:first-of-type { width: 40%; } table th:nth-of-type(2) { width: 60%; } 参数 说明 other_config:dpdk-init=true 是否启用dpdk数据通路 other_config:dpdk-lcore-mask=0x1 指定在哪些core上创建lcore线程，该线程用于dpdk库内部消息处理，如日志等；若没有指定，则默认为cpu affinity...

在多任务并发处理的场景下，如果每来一个任务，就新建一个线程来处理，虽然功能上没问题，但由于线程的创建和销毁会带来很大的开销。线程池就是通过预先创建一定数量的线程，当有任务来时，就将任务分配给一个线程去处理！ 线程池模型下面是线程池的结构！ 123456789101112131415161718192021222324struct threadpool_t { pthread_mutex_t lock; /* 用于锁住本结构体 */ pthread_mutex_t thread_counter; /* 记录忙状态线程个数的锁 */ pthread_cond_t queue_not_full; /* 当任务队列满时，添加任务任务的线程阻塞，等待此条件变量 */ pthread_cond_t queue_not_empty; /* 任务队列不为空时，通知等待任务的线程 */ pthread_t *threads; /* 存放线程池中每个线程的 tid 数组 */ pthread_t...

基于内核的OVS首先验证内核版本uname -r与你下载的OVS版本是否匹配（必须），目前 ovs-2.16 最高只支持内核5.8！ linux内核与ovs版本匹配关系、ovs版本与DPDK版本匹配关系 以 OVS-2.16.0 为例，编译过程如下： 1234567891011121314151617181920212223242526# 获取源码wget https://github.com/openvswitch/ovs/archive/refs/tags/v2.16.0.zip && unzip v2.16.0.zip# 安装依赖包sudo apt install build-essential fakerootdpkg-checkbuilddeps # 检查依赖并手动安装缺少的模块#####################################################cd ovs-2.16.0./boot.sh./configure --with-linux=/lib/modules/$(uname -r)/buildmake -j ...

socket 套接字 图中两个虚线框表示两个套接字，在网络通信中，套接字一定是成对出现的。一端的发送缓冲区对应对端的接收缓冲区。 一个socket只有一个文件描述符，即发送缓冲区和接收缓冲区使用同一个文件描述符。 网络套接字本质：一个文件描述符指向一个套接字（该套接字内部由内核借助两个缓冲区实现）。 网络地址字节序转换由于历史遗留问题，网络数据流采用大端字节序，而 pc 本地一般采用的小段字节序，所以在网络通信中，需要转换字节序。 小端法：（pc本地存储）高位存高地址，地位存低地址。 大端法：（网络存储）高位存低地址，地位存高地址。 字节序只影响不同字节间的顺序，如果只看单字节内部，大小端都一样。不存在00001111变为11110000！ 12345678910111213141516#include <arpa/inet.h>// h: host, to, n: network, l: long, s: short// hton也就是主机到网络的转换，ntoh是网络到主机的转换// l, s 对应 32位和 16位数据，也就是 ipv4 地址 和...

编程中、通信中所说的同步与生活中大家印象中的同步概念略有差异。“同”字应是指协同、协助、互相配合。主旨在协同步调，按预定的先后次序运行 线程同步，指一个线程发出某一功能调用时，在没有得到结果之前，该调用不返回。同时其它线程为保证数据一致性，不能调用该功能。 线程同步可以通过锁来实现！与锁相关的部分函数的man page需要单独安装。 1sudo apt install manpages-posix-dev mutex 互斥量（互斥锁）每个线程在对资源操作前都尝试先加锁，成功加锁才能操作，操作结束解锁。 资源还是共享的，线程间也还是竞争的，但通过“锁”就将资源的访问变成互斥操作。 互斥锁实质上是操作系统提供的一把“建议锁”（又称“协同锁”），建议程序中有多线程访问共享资源的时候使用该机制。但，并没有强制限定。因此，即使有了 mutex，如果有线程不按规则来访问数据，依然会造成数据混乱。 尽量保证锁的粒度，越小越好（访问共享数据前，加锁。访问结束立即解锁）。 123456789101112131415#include <pthread.h>//...

线程概念 虽然可以使用诸多进程来相互协作实现需要并发才能完成的功能，但进程间的协作有着重要的限制：每个进程有自己的独立空间。这种限制导致进程之间的协作存在明显缺陷：如果相互协作的进程需要动态共享大量的数据，则操作起来十分麻烦。就像一群人之间的协作一样，由于每个人都是独立的个体，各有不同的喜好和习惯，协作难免产生误解和沟通困难。如果一件事情让一个人来处理，协作上就不会发生问题。因此，如果能够让一个进程内部实现并发来完成一个复杂的任务，协作上的难度就会少很多。 在进程内部实现并发就是进程出现的动机，如下图所示： Linux 下，线程又称为LWP: light weight process，轻量级进程。 进程 线程 有独立的进程地址空间 没有独立的地址空间，多个线程共享 有独立的 PCB 有独立的 PCB （但PCB中指向内存资源的三级页表相同） 分配资源的最小单位 CPU 执行的最小单位 查看 ps aux / ps ajx 查看线程号 ps -Lf 进程id 传统意义上的 UNIX...

信号 信号是软件层面上的“中断”。一旦信号产生，无论程序执行到什么位置，必须立即停止运行，处理信号，处理结束，再继续执行后续指令。 所有信号的产生及处理全部都是由【内核】完成的。 简单、不能携带大量信息、满足条件才发送。 信号的生命周期 产生： 未决：产生与递达之间状态。 递达：产生并且送达到进程。直接被内核处理掉。 处理：执行默认处理动作、忽略、捕捉（自定义） 阻塞信号集（信号屏蔽字）：进程控制块PCB中的变量（位图），用来记录信号的屏蔽状态。被屏蔽的信号，在解除屏蔽前，一直处于未决态。 未决信号集：进程控制块PCB中的变量（位图），用来记录信号的处理状态。 信号产生时，未决信号集中对应位立刻翻转为1，表示信号处于未决状态。信号被处理后对应位翻转回0，这一过程往往非常短暂。 信号产生后，由于某些原因（主要是阻塞）不能递达，一直处理未决状态。 设置阻塞后，同一信号多次产生，也只能记录一次（也只会被处理一次）。 1234567891011121314struct task_struct { /* Signal handlers: */ struct...

...

...

应用程序的系统调用过程：应用程序->库函数->系统调用->驱动->硬件（磁盘、网卡等） 内核态和用户态现代处理器架构一般允许 CPU 至少在两种不同状态下运行，即：用户态和核心态（有时也称之为监管态 supervisor mode）。执行硬件指令可使 CPU 在两种状态间来回切换。与之对应，可将虚拟内存区域划分（标记）为用户空间部分或内核空间部分。在用户态下运行时，CPU 只能访问被标记为用户空间的内存，试图访问属于内核空间的内存会引发硬件异常。当运行于核心态时，CPU 既能访问用户空间内存，也能访问内核空间内存。 仅当处理器在核心态运行时，才能执行某些特定操作。这样的例子包括：执行宕机（halt）指令去关闭系统，访问内存管理硬件，以及设备 I/O...