2023-08-27

VPP（1）：什么是VPP，为什么叫VPP

什么是VPP

VPP（Vector Packet Processing）是思科旗下的一款可拓展的开源框架，提供用用的、高质量交换、路由功能的应用框架。是网络协议领域常用的开源框架。

为什么叫VPP

VPP全称Vector Packet Processing（矢量报文处理）。VPP的精髓都包含在名字里了，即这个Vector。矢量报文处理与常规的报文处理有什么差别？

标量报文处理

一个标量报文处理流程的典型过程是：一次仅处理一个报文，一个报文中接口收到后，经过若干个功能模块的依次处理。每个功能模块的处理结果，通常有三类，1）丢弃；2）不作处理投递给下一功能模块；3）改写报文/转发。

+---> fooA(packet1) +---> fooB(packet1) +---> fooC(packet1)
+---> fooA(packet2) +---> fooB(packet2) +---> fooC(packet2)
...
+---> fooA(packet3) +---> fooB(packet3) +---> fooC(packet3)

标量报文处理存在以下问题：

I-cache抖动：每个报文都要完整地执行完所有功能模块（foo）的处理，程序频繁地替换I-cache（instruction cache）缓存中的数据，导致缓存利用率降低，从而影响计算机性能。
每个报文处理过程中的调用栈信息随功能模块（foo）而变化，导致调用栈存放的D-cache的存取压力大。

矢量报文处理

矢量报文处理把报文组成一个“报文矢量”（可理解为报文组）。每一个功能模块（foo），都对报文矢量中的报文做一次性处理。

这样的设计：

减少了I-cache抖动，因为每个instruction重复应用于处理报文组的每个报文，提高了I-cache命中率。
调用栈信息重复应用于报文组的每个报文，D-cache的存取压力随之降低。

+---> fooA([packet1, +---> fooB([packet1, +---> fooC([packet1, +--->
            packet2,             packet2,             packet2,
            ...                  ...                  ...
            packet256])          packet256])          packet256])

报文处理图

VPP中的关键设计是Packet Process Graph（报文处理图）。使VPP具有以下特性：

可伸缩，可插件扩展
成熟的图节点架构
可定制的流水线
插件平等

在处理图中，开发人员可以定制插入新的处理节点，这让VPP易于扩展且可以用于定制化地对报文进行特定意途的处理。

报文处理图

VPP平台从接口上接收报文，组合成报文向量，然后把报文向量“喂”给报文处理图，图中的所有节点对报文向量进行逐一处理。

VPP插件都是在运行时加载的共享库。一个插件可以引入新的报文处理图节点或重新组织报文处理图。你可以生成一个完全独立于VPP原生的报文处理图。

参考资料

2022-12-11

技术

Linux CFS调度器

Linux CFS

CFS（Completely Fair Scheduler）是Linux 2.6.23之后的内核默认的线程调度器，它提供了一种相对公平的线程调度策略。它提供了多种调度算法，大致分为两类。

普通调度策略
实时调度策略

普通调度

普通调度策略，即最小vruntime调度。包含SCHED_OTHER, SCHED_IDLE, SCHED_BATCH这几类。在普通调度策略下，优先级（sched_priority）字段总是为0，并没有参与到调度策略的决策中。

注意：这里说的sched_priority与ps或top命令中看到的pri字段，并不是同一个含义。

vruntime

vruntime是一个线程在cpu上运行的累计时间经过归一校正计算后的结果，调度器会优先调度vruntime较小的线程。

理想情况下，所有线程的vruntime大小应该一致，即各线程得到了公平的调度。

线程切换原则

原则很简单：总是选择vruntime最小的线程进行调度。

线程A在执行一段时间后，它的vruntime逐渐累积。一旦A的vruntime超过另一个B的vruntime，CFS则做出线程切换，调度线程B执行。

红黑树

所有处于runnable状态的线程，基于vruntime值，组织一棵红黑树（CFS red-black tree）。以此方便地插入新的线程，或取出vruntime最小的线程。

基于nice值的动态优先级

nice值通过对vruntime的校正，进而影响线程被分配到的时间片的多少。nice的取值范围是-20（高优先级）~19（低优先级）。nice会影响线程占用CPU的时间，nice值越小被分配到的时间片越多。nice值仅会影响SCHED_OTHER和SCHED_BATCH策略。

下面简要解释算法：

每一个nice值都对应一个权重系数。大约为： weight = 1024 * (1.25)^(-nice)。

可以简要地理解为，权重系数为(1.25)^(-nice)。

当nice为0，权重系数=1，vruntime即是线程在cpu上运行的实际时间。
当nice>0，权重系数>1，vruntime会比线程在cpu上运行的实际时间更长。
当nice<0，权重系数<1，vruntime会比线程在cpu上运行的实际时间更短。

调度策略

SCHED_OTHER

SCHED_OTHER仅用于sched_priority为0的线程，在sched_priority为0的所有SCHED_OTHER线程中，使用CFS默认的调度策略（最小vruntime调度），上面已经描述了具体算法。

SCHED_BATCH

SCHED_BATCH与SCHED_OTHER类似，仅用于sched_priority为0的线程。其不同之处在于：SCHED_BATCH会假设所有线程都是对cpu都是贪婪的，它会在线程的每一次调度之后，对线程施加一点“小惩罚”。这种策略通常应用于占用cpu较多，但又没有用户交互的线程中。

SCHED_IDLE

SCHED_IDLE仅用于sched_priority为0的线程，nice值对它也不起作用。此调度策略被应用于极低优先级的线程，仅当系统空闲时线予调度。

实时调度

SCHED_FIFO和SCHED_RR都属于实时线程调度策略。

sched_priority在实时调度策略中被使用，它的取值范围是1~99。调度器针对每一个sched_priority级别，都维护一个待执行的线程的队列。调度器会从最高优先级的非空队列中，选择队头节点的线程来执行。

SCHED_FIFO

当一个SCHED_FIFO达到可执行状态，它总是会抢占SCHED_OTHER, SCHED_IDLE, SCHED_BATCH的线程。SCHED_FIFO并没有把cpu时间切分时间片，一旦开始执行，就会一直执行，除非以下状况：

线程主动挂起（I/O等）。
被更高的优先级线程抢占。

它遵循以下规则：

正在被执行的SCHED_FIFOA线程，如果被更高优先级的B线程抢占，它会放在队列队头中。一旦B线程执行完成，A线程会马上被恢复调度。
SCHED_FIFO的线程从不可执行转为可执行状态，它会被加入到对应sched_priority的队尾。
SCHED_FIFO线程的优先级被调整时，如果是提高优先级，会被放入新优先级队列的队尾；如果是降低优先级，会被放在新优先级队列的队头。

SCHED_RR

RR（Round-robin）调度是针对FIFO调度的增强。在以上FIFO调度的策略的基础上，添加了以下规则：可以配置线程单次执行的最大时间片长度。一旦时间片被使用完，线程停止执行并放置到对应优先级队列的队尾。

参考文献

2022-10-03

技术

600行代码写了个小工具，替代linux中的cd和ls，取名cdls

近来用Rust写了个小工具，核心设计思路是：用方向键在各目录间跳转。兼顾了排序、文件属性显示、文件名搜索等相关功能。

考虑到在linux中，这个活儿通常是用cd和ls完成的，这个工具取名为cdls。

用法示例：

安装

在x86-64架构中,

1
2
3

wget https://xs-upload.oss-cn-hangzhou.aliyuncs.com/cdls/release/v0.3/cdls
sudo mv cdls /usr/bin/
sudo chmod +x /usr/bin/cdls

用法

# 启动cdls屏幕
cdls

# 显示帮助
cdls -h

在cdls屏幕中:

用方向键即可在各目录间跳转

 方向键左             上级目录
 方向键右             下级目录
 方向键上             选择前一项
 方向键下             选择后一项

配置屏幕，输入以下键启动配置屏幕

 c                       列显示配置
 s                       排序配置

 在配置屏幕中，用方向键选择配置，用空格键选定配置，用`q`保存并退出配置屏幕

搜索模式

 f                        启动搜索模式
 在搜索模式中，键入关键字，匹配的文件优先显示。用`enter`退出搜索模式并跳转到目的文件。

退出cdls

 Enter键                 退出cdls并跳转到当前目录

项目URL

https://github.com/SmileXie/cdls

2022-07-03

技术

Rust Cheat Sheet

变量

可变与不可变

1 2	let a = 10; // 不可变 let mut b = 20; // 可变

数据类型

整型

1	let a: u64 = 10;

长度	有符号	无符号
8bits	i8	u8
16bits	i16	u16
32bits	i32	u32
64bits	i64	u64
128bits	i128	u128
与cpu架构相关	isize	usize

数字时指定类型，见下例中的9u32

1	println!("9 / 2 = {} but 9.0 / 2.0 = {}", 9u32 / 2, 9.0 / 2.0);

浮点型

类型为：f32或f64。浮点型默认为f64。

1 2	let a: f32 = 10.0; let b = 11.0 // 默认f64

布尔型

类型为：bool；取值为：true and false

1	let b: bool = true;

字符与字符串

1
2
3

let c: char = 'f';  // 字符
let string_c: &str = "ace";             // 字符串切片
let string_s = String::from("hello");   // 字符串

这里的string_c为“字符串切片”

元组

定义和访问元组

let x: (i32, f64, u8) = (500, 6.4, 1);
let five_hundred = x.0;
let six_point_four = x.1;
let one = x.2;

数组

let days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]; 
// 声明一个全0数组，数据成员个数为5 
let bytes = [0; 5];
// 使用数组成员
let first = days[0];

数组的两个重要特征：数组的每个元素都具有相同的数据类型。数据类型永远不会更改。数组大小是固定的。长度永远不会更改。

向量 Vector

与数组不同之处在于，向量的大小或长度可以随时增大或缩小。在编译时，大小随时间更改的功能是隐式的。因此，Rust 无法像在数组中阻止越界访问一样在向量中阻止访问无效位置。


let three_nums = vec![15, 3, 46]; 
println!("Initial vector: {:?}", three_nums);

let mut fruit = Vec::new();
fruit.push("Apple");
println!("Pop off: {:?}", fruit.pop());

// 索引
let mut index_vec = vec![15, 3, 46]; 
let three = index_vec[1];

哈希表

use std::collections::HashMap; 
//声明与插入元素
let mut reviews: HashMap<String, String> = HashMap::new();
reviews.insert(String::from("Ancient Roman History"), String::from("Very accurate."));
//获取键值
let book: &str = "Programming in Rust"; 
println!("\nReview for \'{}\': {:?}", book, reviews.get(book));

let obsolete: &str = "Ancient Roman History"; 
reviews.remove(obsolete);

结构体

定义结构体

// 经典结构
struct Student { name: String, level: u8, remote: bool }
// 元组结构
struct Grades(char, char, char, char, f32);

主要区别：经典结构中的每个字段都具有名称和数据类型。元组结构中的字段没有名称。

实例化

let user_1 = Student { name: String::from("Constance Sharma"), remote: true, level: 2 };

// Instantiate tuple structs, pass values in same order as types defined
let mark_1 = Grades('A', 'A', 'B', 'A', 3.75);

println!("{}, level {}. Remote: {}. Grades: {}, {}, {}, {}. Average: {}", 
         user_1.name, user_1.level, user_1.remote, mark_1.0, mark_1.1, mark_1.2, mark_1.3, mark_1.4);

枚举

// 声明
enum WebEvent {
    WELoad,
    WEKeys(String, char),
    WEClick { x: i64, y: i64 }
}

// 或

struct KeyPress(String, char);
struct MouseClick { x: i64, y: i64 }
enum WebEvent { WELoad(bool), WEClick(MouseClick), WEKeys(KeyPress) }

// 赋值
let click = MouseClick { x: 100, y: 250 };
let keys = KeyPress(String::from("Ctrl+"), 'N');

let we_load = WebEvent::WELoad(true);
// Set the WEClick variant to use the data in the click struct
let we_click = WebEvent::WEClick(click);
// Set the WEKeys variant to use the data in the keys tuple
let we_key = WebEvent::WEKeys(keys);

泛型

struct Container<T> {
    value: T,
}

impl<T> Container<T> {
    pub fn new(value: T) -> Self {
        Container { value }
    }
}

函数

fn goodbye(message: &str) {
    println!("\n{}", message);
}

fn divide_by_5(num: u32) -> u32 {
    num / 5
}

所有权

所有权三原则

Each value in Rust has a variable that’s called its owner. （Rust中每一个变量都有一个所有者。）
There can only be one owner at a time.（在任一时刻，所有者有且仅有一个。）
When the owner goes out of scope, the value will be dropped.（当所有者离开其作用域后，它所拥有的数据会被释放。）

Copy Trait

凡是拥有Copy trait的数据类型，“=”都表示数据的复制而非传有权的转移。以下数据类型有Copy trait：

所有整型：u32 u64等
布尔型
所有浮点型：f32 f64等
字符型：char
元组（Tuples）：如果组成元组的每个成员都有Copy trait，那么此元组也有Copy trait。

引用

// 引用
fn main() {
    let s1 = String::from("hello");
    let len = calculate_length(&s1);
    println!("The length of '{}' is {}.", s1, len);
}

fn calculate_length(s: &String) -> usize {
    s.len()
}

// 可变引用
fn main() {
    let mut s = String::from("hello");
    change(&mut s);
}

fn change(some_string: &mut String) {
    some_string.push_str(", world");
}

引用的原则

引用的原则：

任何时刻，一个变量只能有
- 一个可变引用，或者
- 多个不可变引用
- 以上两点不可同时存在
引用应该总是合法的

Rust编译器在以下三个条件同时满足时，会产生数据竞争，发出编译错误：

两个或两个以上的pointer（包含所有者，可变引用）指向同一份数据。
其中至少一个可变引用指会向空间写入数据。
没有同步数据的访问机制。

手动批注生存期（lifetime annotation）

fn longest_word<'a>(x: &'a String, y: &'a String) -> &'a String {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

以上代码中，x和y的生命周期有可能不一样，所以函数返回值的生命周期实际上是由两个参数里生命周期较短的那个决定的。

条件判断

loop

在断点处返回一个值

let mut counter = 1;
// stop_loop is set when loop stops
let stop_loop = loop {
    counter *= 2;
    if counter > 100 {
        // Stop loop, return counter value
        break counter;
    }
};

for

let big_birds = ["ostrich", "peacock", "stork"];
for bird in big_birds.iter() {
    println!("The {} is a big bird.", bird);
}

// 此代码遍历数字 0、1、2、3 和 4
for number in 0..5 {
    println!("{}", number * 2);
}

while

while counter < 5 {
    println!("We loop a while...");
    counter = counter + 1;
}

Option与Result 枚举

原型

enum Option<T> {
    None,     // The value doesn't exist
    Some(T),  // The value exists
}

enum Result<T, E> {
    Ok(T):  // A value T was obtained.
    Err(E): // An error of type E was encountered instead.
}

Result

#[derive(Debug)]
struct DivisionByZeroError;

fn safe_division(dividend: f64, divisor: f64) -> Result<f64, DivisionByZeroError> {
    if divisor == 0.0 {
        Err(DivisionByZeroError)
    } else {
        Ok(dividend / divisor)
    }
}


fn read_file_contents(path: PathBuf) -> Result<String, Error> {
    let mut string = String::new();

    // Access a file at a specified path
    // ---------------------------------
    // - Pass variable to `file` variable on success, or
    // - Return from function early if there's an error    
    let mut file: File = match File::open(path) {
        // Corrected code: Pass variable to `file` variable on success
        Ok(file_handle) => file_handle,
        // Corrected code: Return from function early if there's an error
        Err(io_error) => return Err(io_error),
    };

    // Read file contents into `String` variable with `read_to_string`
    // ---------------------------------
    // Success path is already filled in
    // Return from the function early if it is an error
    match file.read_to_string(&mut string) {
        Ok(_) => (),
        // Corrected code: Return from function early if there's an error
        Err(io_error) => return Err(io_error),
    };

    // Corrected code: Return `string` variable as expected by function signature
    Ok(string)
}

match

// vec!与match
let fruits = vec!["banana", "apple", "coconut", "orange", "strawberry"];
for &index in [0, 2, 99].iter() {
    match fruits.get(index) {
        Some(fruit_name) => println!("It's a delicious {}!", fruit_name),
        None => println!("There is no fruit! :("),
    }
}

// 仅在Option为某个值时执行print
let a_number: Option<u8> = Some(7);
match a_number {
    Some(7) => println!("That's my lucky number!"),
    _ => {},
}

// if let 

let a_number: Option<u8> = Some(7);
if let Some(7) = a_number {
    println!("That's my lucky number!");
}

Trait

Trait是一组类型可实现的通用接口。个人理解：类似于给类定义方法。

trait Area {
    fn area(&self) -> f64;
}

struct Circle {
    radius: f64,
}

struct Rectangle {
    width: f64,
    height: f64,
}

impl Area for Circle {
    fn area(&self) -> f64 {
        use std::f64::consts::PI;
        PI * self.radius.powf(2.0)
    }
}

impl Area for Rectangle {
    fn area(&self) -> f64 {
        self.width * self.height
    }
}

可以编写一个函数，该函数接受任何实现 AsJson Trait的类型

fn send_data_as_json(value: &impl AsJson) {
    println!("Sending JSON data to server...");
    println!("-> {}", value.as_json());
    println!("Done!\n");
}

迭代器

#[derive(Debug)]
struct Counter {
    length: usize,
    count: usize,
}

impl Counter {
    fn new(length: usize) -> Counter {
	    Counter {
	        count: 0,
	        length,
	    }
    }
}

impl Iterator for Counter {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
    
        self.count += 1;
        if self.count <= self.length {
            Some(self.count)
        } else {
            None
        }
    }
}

宏

println

1
2
3

fn main() {
    println!("The first letter of the English alphabet is {} and the last letter is {}.", 'A', 'Z');
}

derive(Debug)

通过#[derive(Debug)]语法可以在代码执行期间查看某些在标准输出中无法查看的值。要使用 println! 宏查看调试数据，请使用语法 {:#?} 以可读的方式格式化数据。

#[derive(Debug)]
struct MouseClick { x: i64, y: i64 }

let m = MouseClick{ x: 20, y: 30};
println!("{:#?}", m);

todo

1	todo!("Display the message by using the println!() macro");

工具

Rust在线编译运行环境：https://play.rust-lang.org/

2022-05-06

技术

Valgrind笔记（二）：MemCheck基本原理

Valgrind的MemCheck工具，可以检测多种内存错误，它是如何做到的？

V bits

MemCheck构造出一个“虚拟CPU”。与真实CPU不同的是，虚拟CPU中的每一个bit，都有一个关联的“是否有效”bit（ “valid-value” bit），用于表示它关联的bit是否有效（更确切地，应该是“是否初始化”）。以下称这个bit为V bit。

例如，当CPU从内存中加载一个4-byte int时，也同时从V-bit位图中加载32bits的V bits。当CPU把这个int写回某个地址时，这32bits的V bits也会被存回V-bit位图中。

也就是说，系统中的所有bits，都有对应的V bits。不仅仅是内存，甚至是CPU寄存器，也有它们的V bits。为了实现这样的功能，MemCheck需要为V bits提供强大的压缩能力。

仅仅是访问非法的数据，并不会直接触发MemCheck的报错。仅当这一错误影响到程序的执行结果时，才会报错。例如：

int i, j;
int a[10], b[10];
for ( i = 0; i < 10; i++ ) {
    j = a[i];
    b[i] = j;
}

虽然访问a[i]时，未初始化，但是它并不会报错。因为这段程序仅仅是把未初始化的a[10]复制到b[10]。并没有把这些未初始的值用于某种判断或输出。如果程序改为：


for ( i = 0; i < 10; i++ ) {
    j += a[i];
}
if ( j == 77 ) 
    printf("hello there\n");

MemCheck就会报错了。未初始化的值a[i]之和，被用于计算j并用于判断if (j == 77)。

在CPU做各种运算时（加，位运算等），操作数的V bits被引用，用于计算出运算结果的V bits。但是，即使这里包含非法的V bits，MemCheck仍然不会报错。仅当以下几种情况发生时，MemCheck才会去检查V bits的有效性：

运算结果被用于生成地址
影响程序控制流（如条件判断）
有系统调用发生

这样的机制似乎看起来过度设计了，但一旦联想到C语言中有一个常见的机制叫“结构体自动填充”，你就不会这么觉得了。以下这个例子：

struct S { int x; char c; };
struct S s1, s2;
s1.x = 42;
s1.c = 'z';
s2 = s1;
if (s2) printf("s2\n");

请问，以上代码中，是否有未初始化的赋值？答案是：有。struct S在除了x和c成员外，还有3 bytes的自动填充字段，而这部分字段是未被初始化的。作为C语言程序员，想必你不会希望MemCheck因未初始化的自动填充字段而报错。

A bits

在MemCheck构建的“虚拟CPU”之上，对应每一个数据，除了V bits外，还有表示地址有效性的Valid-address bits，简称A bits。与V bits不同的是：1）A bits仅仅针对内存中的数据存在，CPU寄存器中的数据，没有A bits。2）每一byte的内存数据，对应一bit的A bit。A bits用于表示程序是否可以合法地读写此地址的数据。

每当程序读写内存时，MemCheck会检查对应地址的A bits。如果A bits指示当前的地方访问是非法的，将抛出告警。此时，MemCheck仅仅会检查A btis，而不会修改它。

A bits是如何被构建出来的呢：

进程启动时，所有全局变量的A bits被标记为“可被访问”。
malloc/new时，申请出来的内存，被标记为“可被访问”。它们被free时，该地址修改为“不可访问”。
栈指针（stack pointer register，SP）上下移动时，A bits会被修改。在SP之上，至栈基地址之间的地址，被标记为“可被访问”。SP之下的地址，被标记为“不可访问”。
系统调用时， A bits会被修改。例如：mmap把一段地址映射进进程地址空间，会被标记为“可被访问”。
程序可以主动告诉MemCheck，哪些地址应该被做何种标记。

规则总结

综合A bits与V bits，MemCheck检测内存错误，会遵循以下原则：

内存中的每一byte数据，都有8 bits关联的V bits和1 bit的A bits。V bits表示对应的内存数据是否被初始化；A bits表示程序对此地址空间的访问，是否合法。经过压缩，A bits + V bits通常会增加25%的内存使用。
当内存读写发生时，关联的A bits被取出，用于检查地址访问的合法性。MemCheck在发生非法访问时，会抛出异常。
当内存被读进CPU寄存器时，关联的V bits被读进“虚拟CPU”中；* 当CPU寄存器中的数据被写进内存时，关联的V bits也从“虚拟CPU”中被写回内存中。
当数据被用于生成地址，或会影响程序控制流（如条件判断）时，或数据用于系统调用，V bits被检查。其它情况下，V bits不作检查。当发现使用未初始化的数据，MemCheck会抛出异常。
一旦V bits被检查过，它们就被置为“有效”。这一手段用于避免过多地重复报错。
当数据从内存中加载进CPU时，MemCheck检查 A bits的合法性，在发现非法访问时抛出异常。当发生非法访问时，V bits被强制置为“有效”（尽管A bits为“不可访问”）。这种机制用于避免过多的冗余报错。
MemCheck会拦截内存访问接口malloc, calloc, realloc, valloc, memalign, free, new, new[], delete, delete[]，这些接口中发生系统调用时，对应地修改A bits和V bits。

参考文献

2022-05-03

技术

Valgrind笔记（一）：安装与Quick Start

安装

基于源码安装

确认Valgrind最新版本
下载源码：wget https://sourceware.org/pub/valgrind/valgrind-3.17.0.tar.bz2
解压：tar xvf valgrind-3.17.0.tar.bz2
cd valgrind-3.17.0
配置： ./configure
编译：make install (可能需要root权限, sudo)

基于安装包安装

Ubuntu环境：sudo apt install valgrind

Quick Start

执行一个最简单的测试：

编写一段有bug的代码：

#include <stdlib.h>

void f(void)
{
   int* x = malloc(10 * sizeof(int));
   x[10] = 0;        // problem 1: heap block overrun
}                    // problem 2: memory leak -- x not freed

int main(void)
{
   f();
   return 0;
}

编译之（注意要编译选项要带上-g），编译出的可执行文件为test。用valgrind来执行test

$ valgrind ./test
==4597== Memcheck, a memory error detector
==4597== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4597== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==4597== Command: ./test
==4597==
==4597== Invalid write of size 4
==4597==    at 0x10916B: f (test.c:6)
==4597==    by 0x109180: main (test.c:11)
==4597==  Address 0x4a47068 is 0 bytes after a block of size 40 alloc'd
==4597==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4597==    by 0x10915E: f (test.c:5)
==4597==    by 0x109180: main (test.c:11)
==4597==
==4597==
==4597== HEAP SUMMARY:
==4597==     in use at exit: 40 bytes in 1 blocks
==4597==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
==4597==
==4597== LEAK SUMMARY:
==4597==    definitely lost: 40 bytes in 1 blocks
==4597==    indirectly lost: 0 bytes in 0 blocks
==4597==      possibly lost: 0 bytes in 0 blocks
==4597==    still reachable: 0 bytes in 0 blocks
==4597==         suppressed: 0 bytes in 0 blocks
==4597== Rerun with --leak-check=full to see details of leaked memory
==4597==
==4597== For lists of detected and suppressed errors, rerun with: -s
==4597== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

以上Valgrind给出的log中，已明确指示了错误的地方：

test.c 第6行，访问了一个超出malloc申请范围的地址。
检测到一个40 bytes的内测泄漏。通过valgrind --leak-check=full ./test查看更详细的信息。

那么，我们就用valgrind --leak-check=full ./test 试试：

...
==179== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==179==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==179==    by 0x10915E: f (test.c:5)
==179==    by 0x109180: main (test.c:11)
...

Valgrind检测发现了在test.c第5行malloc的内存，没有被释放。

至此，Valgrind的简单demo就完成了。Valgrind（尤其是MemCheck tool）为C/C++程序员提供了很好的检查内存错误的工具。

2022-04-03

技术

一个小型项目的Makefile模板

最近发现一个很好用的Makefile模板，简单修改后几乎可以适配所有常用场景。

# tool macros
CC ?= gcc
CCFLAGS := # FILL: compile flags
DBGFLAGS := -g
CCOBJFLAGS := $(CCFLAGS) -c


# path macros
BIN_PATH := bin
OBJ_PATH := obj
SRC_PATH := src
DBG_PATH := debug


# compile macros
TARGET_NAME := test
TARGET := $(BIN_PATH)/$(TARGET_NAME)
TARGET_DEBUG := $(DBG_PATH)/$(TARGET_NAME)


# src files & obj files
SRC := $(foreach x, $(SRC_PATH), $(wildcard $(addprefix $(x)/*,.c*)))
OBJ := $(addprefix $(OBJ_PATH)/, $(addsuffix .o, $(notdir $(basename $(SRC)))))
OBJ_DEBUG := $(addprefix $(DBG_PATH)/, $(addsuffix .o, $(notdir $(basename $(SRC)))))


# clean files list
DISTCLEAN_LIST := $(OBJ) \
				  $(OBJ_DEBUG)
CLEAN_LIST := $(TARGET) \
						  $(TARGET_DEBUG) \
						  $(DISTCLEAN_LIST)


# default rule
default: makedir all


# non-phony targets
$(TARGET): $(OBJ)
		$(CC) $(CCFLAGS) -o $@ $(OBJ)


$(OBJ_PATH)/%.o: $(SRC_PATH)/%.c*
		$(CC) $(CCOBJFLAGS) -o $@ $<


$(DBG_PATH)/%.o: $(SRC_PATH)/%.c*
		$(CC) $(CCOBJFLAGS) $(DBGFLAGS) -o $@ $<


$(TARGET_DEBUG): $(OBJ_DEBUG)
		$(CC) $(CCFLAGS) $(DBGFLAGS) $(OBJ_DEBUG) -o $@


# phony rules
.PHONY: makedir
makedir:
		@mkdir -p $(BIN_PATH) $(OBJ_PATH) $(DBG_PATH)


.PHONY: all
all: $(TARGET)


.PHONY: debug
debug: $(TARGET_DEBUG)


.PHONY: clean
clean:
		@echo CLEAN $(CLEAN_LIST)
		@rm -f $(CLEAN_LIST)


.PHONY: distclean
distclean:
		@echo CLEAN $(DISTCLEAN_LIST)
		@rm -f $(DISTCLEAN_LIST)

代码目录结构：

├── Makefile
├── bin
│   └── crudc
├── debug
├── obj
│   ├── crudc.o
│   └── test.o
└── src
    ├── crudc.c
    ├── list.h
    └── test.c

使用步骤：

按以上目录结构组织代码
Makefile中，配置好这几个变量：CC, CCFLAGS, DBGFLAGS, CCOBJFLAGS, TARGET_NAME
make 或 make debug

2022-02-04

日记

《开端》就是在解bug

除夕夜在看《开端》，看了前几集，就似乎了有一种熟悉的感觉。

从程序员的视角来看，《开端》就是发现了一个bug后定位根因并解决的过程。期间不断通过重现bug排除错误答案。

重现第六次时，试图对bug视而不见，选择逃避。后因bug重现概率过高被boss强行拉回继续定位。

重现第十次时，确认了bug根因来源于程序内部，并非由外部API或环境因素触发。

又经过六次重现，排除了两个嫌疑重大的逻辑。

重现到第十七次，算是定位到了直接原因。

又花了七次重现，才最终定位到根因并解决bug。

2022-01-01

技术

无锁编程基础与无锁队列的实现

什么是无锁编程

无锁编程，即访问多线程共享数据时，不加/解锁。

这里的“锁”并不特指mutex，还包括使用semaphore、条件变量、信号等构造出的线程挂起等待机制。甚至我们不使用这些操作系统提供的支撑，也可以写出一个“有锁”的接口（在接口中死等某个变量，类似spinlock）。

无锁操作，通常被抽象成方法、接口。比如说针对一个无锁的队列，pop、push就是它的无锁操作。Herlihy & Shavit 给无锁操作给出一个简洁的定义：调用无锁操作时，无论如何都不应该产生任何阻塞。

无锁编程有如下几点优势：

加锁，等待锁涉及系统调用，影响性能。无锁编程没有这部分的性能损耗。
不会产生死锁

支撑无锁编程的系统算法与接口

RMW原子操作

这里先介绍RMW原子操作，因为这是支撑各类无锁编程算法的基础。

原子操作的想必大家都熟知，它是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何上下文切换。

RMW（read-modify-write）原子操作，是指把“读-改-写”三步指令合并到一个原子操作里。例如以下两例，实现数的原子性增减

Win32中的_InterlockedIncrement
IOS中的OSAtomicAdd32

RMW原子操作需要CPU的支撑，当前各类主流的CPU都提供了类似的功能。

CAS

CAS（compare-and-swap）是一种RMW原子操作，它将以下操作封装在一个原子操作里：

读变量*p
对比*p与变量old
如果*p与old不相同，不做任何操作。
如果*p与old相同，将另一变量new赋值给*p

伪代码如下：

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new
    return true

在实际应用中，CAS函数常常返回*p的当前值。例如，想用CAS构造一个栈的push和pop，伪代码如下：

push(node):
    curr := head
    old := curr
    node->next = curr
    while (old != (curr = CAS(&head, curr, node))) {
        old = curr
        node->next = curr
    }

pop():
    curr := head
    old := curr
    next = curr->next
    while (old != (curr = CAS(&head, curr, next))) {
        old = curr
        next = curr->next
    }
    return curr

阅读全文

2021-12-25

通信

O-RAN与OpenRAN之比较

O-RAN

无线网络建设一直是运营商网络综合成本（TCO）的最主要部分，大致占比在60%～70%。大部分运营商刚经历4G网络的巨大投资，就将面对5G网络的投资建设压力。

5G网络不同于4G网络，5G网的速度快，带宽大，频段高。也就是说，5G网络的穿透性会远差于4G网络。因此，未来中国就需要成百万甚至上千万的5G小基站。同时，5G网络又是运营商必须投资的网络，大规模建网势必带来极大的耗资。在“无线互联网”流量收入增长放缓、语音收入下降的背景下，垂直行业是运营商必须进入的“蓝海市场”，拓展运营商的盈利能力将是5G网络的首要任务。垂直行业的新业务意味着更多样的业务类型、更复杂的网络管理，需要更高效的资源管理方案以及更灵活的网络架构以便于开展业务创新。

在这一大背景下，2018年，在西班牙巴塞罗那一年一度的世界移动大会（MWC）期间，中国移动，美国AT&T，德国电信，日本NTT DOCOMO，法国的O-RANge宣布了O-RAN联盟的诞生。由运营商主导的O-RAN产业联盟应运而生，提出了“开放”和“智能”两大核心愿景。

O-RAN推动以下四个方向的发展：

接口开放化：把基站内部原有的封闭接口的开放，在这个基础上，不同厂家的软件才有可能无缝配合，以此降低对单一厂商的依赖，鼓励创新，降低成本。
软件开源化：推动无线协议栈开源，共享代码，降低研发成本，让产业企业把更多精力聚焦在核心算法和差异化功能软件的研发上。
硬件白盒化：将传统基站的专用硬件用通用服务器代替，充分进行软硬件解耦，降低行业门槛，吸引更多中小企业参与竞争。
网络智能化：RAN开放和解耦之后，可以引人工智能，实现复杂组网环境下的高效运维管理，提升频谱资源的利用率，降低网络能耗。

O-RAN制定的标准，是3GPP标准的补充和增强。如图一所示：在3GPP定义的E1，F1，NG，Xn，X2的基础上，O-RAN进一步开放，定义了O1，O2，E2，A1，Open-FH等接口

oran架构

为制定各类规范，O-RAN下设10个工作组（WG）：

WG1 - Use Cases and Overall Architecture Workgroup
WG2 - Non-real-time RIC and A1 Interface Workgroup
WG3 - Near-Real-time RIC and E2 Interface Workgroup
WG4 - Open Fronthaul Interfaces Workgroup
WG5 - Open F1/W1/E1/X2/Xn Interface Workgroup
WG6 - Cloudification and Orchestration Workgroup
WG7 - White-box Hardware Workgroup
WG8 - Stack Reference Design Workgroup
WG9 - Open X-haul Transport Workgroup
WG10 - OAM for O-RAN

OpenRAN

2016年，Facebook发起了一个叫做TIP（Telecom Infra Project，电信基础设施）的项目，下面包含了很多子项目，其中就有一个OpenRAN的项目计划。

2017年，全球运营商巨头沃达丰把自己研究的SDR RAN的成果奉献给了TIP，并创建OpenRAN工作组，旨在建立一个基于通用服务器，可软件定义技术的白盒化RAN解决方案。参与OpenRAN的运营商成员以欧美地区为主，中国的三大运营商都没有参与。项目由沃达丰和西班牙电信牵头，沃达丰负责全力推进。传统设备商中，除诺基亚积极参与之外，爱立信，华为和中兴都没有参与。此外新晋设备商三星对此也非常激进。此外，希望夹缝生存，在通信市场分得一杯羹的大量欧美新兴的中小设备商的参与非常积极，他们已经在全球开始部署OpenRAN商用网络，并开始组建自己的生态系统。

O-RAN/OpenRAN比较

跟O-RAN联盟不同，OpenRAN工作组并没有对开放网络的内外部接口进行严格规范的定义，他们积极鼓励各运营商和设备商进行Open RAN网络的实际部署，并在外场进行互操作测试。

总体而言，O-RAN和OpenRAN这两个组织的参与成员虽然不尽相同，推进策略也各有侧重，但其目标和产品方案却大体一致，拥有非常广泛的共同语言。在2020年2月份，两者携起手来，共同在欧洲成立了开放测试和集成中心（OTIC），共享资源来进行Open RAN的研究和推进。OpenRAN组织与会使用和参考O-RAN制定的标准来推动开放式基站的部署。

O-RAN是侧重制定标准，而OpenRAN则侧重部署验证与产业推广。