网络营销网站建设实验总结,辽宁招投标工程信息网,网页设计师培训哪个好,常见的软件开发工具博客重载记录流控算法实现open系统调用流程二分查找前言#xff1a; 有时候看了一些比较好的文章#xff0c;过几天就忘了#xff0c;想想不如自己实现一遍博客代码或按博客结构自己写一遍#xff0c;加深印象#xff0c;但把别人的内容改个名字变成自己的博客#xff0c…
博客重载记录流控算法实现open系统调用流程二分查找前言 有时候看了一些比较好的文章过几天就忘了想想不如自己实现一遍博客代码或按博客结构自己写一遍加深印象但把别人的内容改个名字变成自己的博客有点不太好故全写在这个博客中权当个人记录。
流控算法实现
参考文章流量控制-从原理到实现
open系统调用流程
参考文章走马观花 Linux 系统调用 open 七日游一
linux系统调用简要介绍 操作系统为在用户态运行的进程与硬件设备进行交互提供了一组接口。在应用程序与硬件设置一个额外层具有很多优点。首先这使得编程更加容易把用户从学习硬件设备的低级编程特性中解放出来其次这极大地提升了系统的安全性因为内核在试图满足某个请求之前在接口级就可以检查这种请求的正确性最后更重要的是这些接口使得程序更具有移植性因为只要内核所提供的一组接口相同那么在任一内核之上就可以正确地编译和执行程序。Unix系统通过向内核发出系统调用system call实现了用户态进程和硬件设备之间的大部分接口。《深入理解linux内核》——系统调用 【纯干货】linux内核——系统调用原理及实现 一次系统调用的完整执行过程如下
通过特定指令发出系统调用int $0x80、sysenter、syscallCPU从用户态切换到内核态进行一些寄存器和环境设置调用system_call内核函数通过系统调用号获取对应的服务例程调用系统调用处理例程使用特定指令从系统调用返回用户态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_max1] {/** Smells like a compiler bug -- it doesnt 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 vectorint 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], lowhighif (data[low] target) {return low;}return -1;
}int BinaryFindFirstGreaterEqual(const vectorint 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], lowhighreturn low;
}int BinaryFindFirstGreater(const vectorint 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], lowhighreturn low;
}int BinaryFindLastLesserEqual(const vectorint 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], lowhighreturn low;
}int BinaryFindLastLesser(const vectorint 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], lowhighreturn low;
}int BinaryFindFirstEqual(const vectorint 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], lowhighif (data[low] target) {return low;}return -1;
}int BinaryFindLastEqual(const vectorint 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], lowhighif (data[low] target) {return low;}return -1;
}int BinaryFindEqualCompare(const vectorint data, int target) { // 返回第一次相等的下标for (int i 0; i data.size(); i) {if (data[i] target) {return i;}}return -1;
}int BinaryFindFirstGreaterEqualCompare(const vectorint data, int target) {for (int i 0; i data.size(); i) {if (data[i] target) {return i;}}return data.size();
}int BinaryFindFirstGreaterCompare(const vectorint data, int target) {for (int i 0; i data.size(); i) {if (data[i] target) {return i;}}return data.size();
}int BinaryFindLastLesserEqualCompare(const vectorint data, int target) {for (int i data.size() - 1; i 0; i--) {if (data[i] target) {return i;}}return -1;
}int BinaryFindLastLesserCompare(const vectorint data, int target) {for (int i data.size() - 1; i 0; i--) {if (data[i] target) {return i;}}return -1;
}int BinaryFindFirstEqualCompare(const vectorint data, int target) {for (int i 0; i data.size(); i) {if (data[i] target) {return i;}}return -1;
}int BinaryFindLastEqualCompare(const vectorint data, int target) {for (int i data.size() - 1; i 0; i--) {if (data[i] target) {return i;}}return -1;
}using FindFunc functionint(const vectorint, int);
void TestBinaryFind(const vectorint data, const vectorint 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() {vectorint unique_data;default_random_engine e;uniform_int_distributionint u(1, 100);e.seed(time(0));for (int i 5; i 95; i) {if (u(e) 50) {unique_data.emplace_back(i);}}vectorint 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);vectorint 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);
}
