博客重载记录

前言： 有时候看了一些比较好的文章，过几天就忘了，想想不如自己实现一遍博客代码或按博客结构自己写一遍，加深印象，但把别人的内容改个名字变成自己的博客，有点不太好，故全写在这个博客中，权当个人记录。

流控算法实现

参考文章：流量控制-从原理到实现

open系统调用流程

参考文章：走马观花： Linux 系统调用 open 七日游（一）

linux系统调用简要介绍

操作系统为在用户态运行的进程与硬件设备进行交互提供了一组接口。在应用程序与硬件设置一个额外层具有很多优点。首先这使得编程更加容易，把用户从学习硬件设备的低级编程特性中解放出来；其次，这极大地提升了系统的安全性，因为内核在试图满足某个请求之前在接口级就可以检查这种请求的正确性；最后，更重要的是这些接口使得程序更具有移植性，因为只要内核所提供的一组接口相同，那么在任一内核之上就可以正确地编译和执行程序。Unix系统通过向内核发出系统调用（system call）实现了用户态进程和硬件设备之间的大部分接口。

《深入理解linux内核》——系统调用

【纯干货】linux内核——系统调用原理及实现
一次系统调用的完整执行过程如下：

1. 通过特定指令发出系统调用（int $0x80、sysenter、syscall）
2. CPU从用户态切换到内核态，进行一些寄存器和环境设置
3. 调用system_call内核函数，通过系统调用号获取对应的服务例程
4. 调用系统调用处理例程
5. 使用特定指令从系统调用返回用户态（iret、sysexit、sysret）

系统调用号定义：

# arch/x86/entry/syscalls/syscall_64.tbl
#
# 64-bit system call numbers and entry vectors
#
# The format is:
# <number> <abi> <name> <entry point>
#
# The __x64_sys_*() stubs are created on-the-fly for sys_*() system calls
#
# The abi is "common", "64" or "x32" for this file.
#
0	common	read			__x64_sys_read
1	common	write			__x64_sys_write
2	common	open			__x64_sys_open
3	common	close			__x64_sys_close
4	common	stat			__x64_sys_newstat
5	common	fstat			__x64_sys_newfstat
6	common	lstat			__x64_sys_newlstat
7	common	poll			__x64_sys_poll
8	common	lseek			__x64_sys_lseek
9	common	mmap			__x64_sys_mmap
10	common	mprotect		__x64_sys_mprotect
11	common	munmap			__x64_sys_munmap
12	common	brk			__x64_sys_brk
13	64	rt_sigaction		__x64_sys_rt_sigaction
14	common	rt_sigprocmask		__x64_sys_rt_sigprocmask

系统调用分派表（dispatch table） sys_call_table：

// arch/x86/entry/syscall_64.c
// SPDX-License-Identifier: GPL-2.0
/* System call table for x86-64. */#include <linux/linkage.h>
#include <linux/sys.h>
#include <linux/cache.h>
#include <asm/asm-offsets.h>
#include <asm/syscall.h>/* this is a lie, but it does not hurt as sys_ni_syscall just returns -EINVAL */
extern asmlinkage long sys_ni_syscall(const struct pt_regs *);
#define __SYSCALL_64(nr, sym, qual) extern asmlinkage long sym(const struct pt_regs *);
#include <asm/syscalls_64.h>
#undef __SYSCALL_64#define __SYSCALL_64(nr, sym, qual) [nr] = sym,asmlinkage const sys_call_ptr_t sys_call_table[__NR_syscall_max+1] = {/** Smells like a compiler bug -- it doesn't work* when the & below is removed.*/[0 ... __NR_syscall_max] = &sys_ni_syscall,
#include <asm/syscalls_64.h>
};// 相关定义
#ifdef CONFIG_X86_64
typedef asmlinkage long (*sys_call_ptr_t)(const struct pt_regs *);
#else
typedef asmlinkage long (*sys_call_ptr_t)(unsigned long, unsigned long,unsigned long, unsigned long,unsigned long, unsigned long);/** Non-implemented system calls get redirected here.*/
asmlinkage long sys_ni_syscall(void)
{return -ENOSYS;
}

系统调用最多6个额外参数（除系统调用号）

sys_open声明与定义
linux Kernel代码艺术——系统调用宏定义

// 函数声明
asmlinkage long sys_open(const char __user *filename, int flags, umode_t mode);
// 函数定义
SYSCALL_DEFINE3(open, const char __user *, filename, int, flags, umode_t, mode)
{if (force_o_largefile())flags |= O_LARGEFILE;return do_sys_open(AT_FDCWD, filename, flags, mode);
}

SYSCALL_DEFINE3作用

#define SYSCALL_DEFINE1(name, ...) SYSCALL_DEFINEx(1, _##name, __VA_ARGS__)
#define SYSCALL_DEFINE2(name, ...) SYSCALL_DEFINEx(2, _##name, __VA_ARGS__)
#define SYSCALL_DEFINE3(name, ...) SYSCALL_DEFINEx(3, _##name, __VA_ARGS__)
#define SYSCALL_DEFINE4(name, ...) SYSCALL_DEFINEx(4, _##name, __VA_ARGS__)
#define SYSCALL_DEFINE5(name, ...) SYSCALL_DEFINEx(5, _##name, __VA_ARGS__)
#define SYSCALL_DEFINE6(name, ...) SYSCALL_DEFINEx(6, _##name, __VA_ARGS__)#define SYSCALL_DEFINE_MAXARGS 6#define SYSCALL_DEFINEx(x, sname, ...)                                         \SYSCALL_METADATA(sname, x, __VA_ARGS__)                                \__SYSCALL_DEFINEx(x, sname, __VA_ARGS__)SYSCALL_DEFINE3(open, const char __user *, filename, int, flags, umode_t, mode)
宏定义展开之后就成为：
asmlinkage long sys_open(const char __user *filename, int flags, umode_t mode);

宏展开后3表示系统参数个数，使用宏展开是为了将参数都当成long类型，进而执行寄存器的符号位扩展
asmlinkage
asmlinkage指定用堆栈传参数，用意是什么？寄存器不是更快吗
asmlinkage作用就是告诉编译器，函数参数不是用用寄存器来传递，而是用堆栈来传递的；
相关回答：

像楼上各位所说，用户调用syscall的时候，参数都是通过寄存器传进来的。中间内核由把所有的参数压栈了， 所以这个asmlinkage可以通过到gcc，恰好可以用正确的调用方式取到参数。
内核前面的那些统一处理很重要，这样后端真正的的syscall 实现函数就可以得到统一的调用方式了，而不是之间面对不同的abi。确实比较方便了。
不然每个syscall函数里面都要自己去处理不同abi，多很多重复代码。
当然也可以考虑在这个统一的处理的时候，把参数全部按照一定的规范放到寄存器。 但这个方法不能在所有的cpu架构上面都做的到。
我觉得这里的选择，“统一”要比这个“寄存器传参”要重要。 从用户切换到内核，要做大量的处理。相比较其他部分，这点参数的开销实在不算什么。

二分查找

写对二分查找不是套模板并往里面填空，需要仔细分析题意

#include <bits/stdc++.h>
using namespace std;
int BinaryFindEqual(const vector<int>& data, int target) {  // 等于// 结果可能出现在[0,n-1]区间，不存在时返回-1int low = 0;int high = data.size() - 1;while (low < high) {int mid = (low + high) / 2;  // 靠近low high都可以if (data[mid] == target) {return mid;} else if (data[mid] > target) {high = mid - 1;} else {low = mid + 1;}}// 压缩区间至[low,high], low==highif (data[low] == target) {return low;}return -1;
}int BinaryFindFirstGreaterEqual(const vector<int>& data, int target) {  // 第一次大于等于// 结果可能落在[0,n]int low = 0;int high = data.size();while (low < high) {int mid = (low + high) / 2;  // 靠近lowif (data[mid] >= target) {high = mid;} else {low = mid + 1;}}// 压缩区间至[low,high], low==highreturn low;
}int BinaryFindFirstGreater(const vector<int>& data, int target) {  // 第一次大于// 结果可能落在[0,n]int low = 0;int high = data.size();while (low < high) {int mid = (low + high) / 2;  // 靠近lowif (data[mid] > target) {high = mid;} else {low = mid + 1;}}// 压缩区间至[low,high], low==highreturn low;
}int BinaryFindLastLesserEqual(const vector<int>& data, int target) {  // 最后一次小于等于// 结果可能落在[-1,n-1]if (data[0] > target) {return -1;}int low = 0;int high = data.size() - 1;while (low < high) {int mid = (low + high + 1) / 2;  // 靠近highif (data[mid] > target) {high = mid - 1;} else {low = mid;}}// 压缩区间至[low,high], low==highreturn low;
}int BinaryFindLastLesser(const vector<int>& data, int target) {  // 最后一次小于// 结果可能落在[-1,n-1]if (data[0] >= target) {return -1;}int low = 0;int high = data.size() - 1;while (low < high) {int mid = (low + high + 1) / 2;  // 靠近highif (data[mid] >= target) {high = mid - 1;} else {low = mid;}}// 压缩区间至[low,high], low==highreturn low;
}int BinaryFindFirstEqual(const vector<int>& data, int target) {  // 第一次等于// 结果可能落在[0,n-1]，不存在时返回-1int low = 0;int high = data.size() - 1;while (low < high) {int mid = (low + high) / 2;  // 靠近lowif (data[mid] > target) {high = mid - 1;} else if (data[mid] < target) {low = mid + 1;} else {high = mid;}}// 压缩区间至[low,high], low==highif (data[low] == target) {return low;}return -1;
}int BinaryFindLastEqual(const vector<int>& data, int target) {  // 最后一次等于// 结果可能落在[0,n-1]，不存在时返回-1int low = 0;int high = data.size() - 1;while (low < high) {int mid = (low + high + 1) / 2;  // 靠近highif (data[mid] > target) {high = mid - 1;} else if (data[mid] < target) {low = mid + 1;} else {low = mid;}}// 压缩区间至[low,high], low==highif (data[low] == target) {return low;}return -1;
}int BinaryFindEqualCompare(const vector<int>& data, int target) {  // 返回第一次相等的下标for (int i = 0; i < data.size(); i++) {if (data[i] == target) {return i;}}return -1;
}int BinaryFindFirstGreaterEqualCompare(const vector<int>& data, int target) {for (int i = 0; i < data.size(); i++) {if (data[i] >= target) {return i;}}return data.size();
}int BinaryFindFirstGreaterCompare(const vector<int>& data, int target) {for (int i = 0; i < data.size(); i++) {if (data[i] > target) {return i;}}return data.size();
}int BinaryFindLastLesserEqualCompare(const vector<int>& data, int target) {for (int i = data.size() - 1; i >= 0; i--) {if (data[i] <= target) {return i;}}return -1;
}int BinaryFindLastLesserCompare(const vector<int>& data, int target) {for (int i = data.size() - 1; i >= 0; i--) {if (data[i] < target) {return i;}}return -1;
}int BinaryFindFirstEqualCompare(const vector<int>& data, int target) {for (int i = 0; i < data.size(); i++) {if (data[i] == target) {return i;}}return -1;
}int BinaryFindLastEqualCompare(const vector<int>& data, int target) {for (int i = data.size() - 1; i >= 0; i--) {if (data[i] == target) {return i;}}return -1;
}using FindFunc = function<int(const vector<int>&, int)>;
void TestBinaryFind(const vector<int>& data, const vector<int>& targets, FindFunc test_fn, FindFunc right_fn, string testname) {for (int target : targets) {int res1 = test_fn(data, target);int res2 = right_fn(data, target);if (res1 != res2) {cout << "wrong anwer." << endl;cout << "res1: " << res1 << "  res2: " << res2 << endl;}}cout << testname << " complete." << endl;
}int main() {vector<int> unique_data;default_random_engine e;uniform_int_distribution<int> u(1, 100);e.seed(time(0));for (int i = 5; i < 95; i++) {if (u(e) > 50) {unique_data.emplace_back(i);}}vector<int> targets;for (int i = 0; i <= 100; i++) {targets.emplace_back(i);}cout << "unique data test:" << endl;TestBinaryFind(unique_data, targets, BinaryFindEqual, BinaryFindEqualCompare, "BinaryFindEqual");TestBinaryFind(unique_data, targets, BinaryFindFirstGreaterEqual, BinaryFindFirstGreaterEqualCompare, "BinaryFindFirstGreaterEqual");TestBinaryFind(unique_data, targets, BinaryFindFirstGreater, BinaryFindFirstGreaterCompare, "BinaryFindFirstGreater");TestBinaryFind(unique_data, targets, BinaryFindLastLesserEqual, BinaryFindLastLesserEqualCompare, "BinaryFindLastLesserEqual");TestBinaryFind(unique_data, targets, BinaryFindLastLesser, BinaryFindLastLesserCompare, "BinaryFindLastLesser");vector<int> repeat_data;for (int i = 5; i < 95; i++) {while (u(e) > 30) {repeat_data.emplace_back(i);}}cout << "repeat data test:" << endl;TestBinaryFind(repeat_data, targets, BinaryFindFirstGreaterEqual, BinaryFindFirstGreaterEqualCompare, "BinaryFindFirstGreaterEqual");TestBinaryFind(repeat_data, targets, BinaryFindFirstGreater, BinaryFindFirstGreaterCompare, "BinaryFindFirstGreater");TestBinaryFind(repeat_data, targets, BinaryFindLastLesserEqual, BinaryFindLastLesserEqualCompare, "BinaryFindLastLesserEqual");TestBinaryFind(repeat_data, targets, BinaryFindLastLesser, BinaryFindLastLesserCompare, "BinaryFindLastLesser");TestBinaryFind(repeat_data, targets, BinaryFindFirstEqual, BinaryFindFirstEqualCompare, "BinaryFindFirstEqual");TestBinaryFind(repeat_data, targets, BinaryFindLastEqual, BinaryFindLastEqualCompare, "BinaryFindLastEqual");
}