Frank's blogs

如何修改vscode的SSH插件指定一个主机的操作系统类型

发表于 2024-07-29
本文字数： 128 阅读时长 ≈ 1 分钟

有些时候因为误操作或者vscode自身识别出错会导致在远程链接的时候选择了错误的对方主机操作系统

如图
此时仅仅删除ssh host配置文件和系统的ssh known-hosts文件都不能解决问题，需要在vscode的Remote-SSH插件处直接修改才可以
如下图

使用hrtimer的内核定时器

发表于 2024-07-02 更新于 2024-08-14
本文字数： 6.2k 阅读时长 ≈ 11 分钟

`copy_from_user`和`copy_to_user`

这两个函数是内核程序和用户程序互相传递信息的函数

原型是

unsigned long copy_to_user(void __user *to, const void *from, unsigned long n)
unsigned long copy_from_user(void *to, const void __user *from, unsigned long n)

函数中的__user指的是这个指针指向的是用户空间的地址，也就是在用户空间使用&取地址得到的指针
返回值是没有成功拷贝的字节数，0代表成功
这两个函数不能在中断上下文中使用，因为这两个函数可能导致休眠和阻塞，影响进程切换
刚拿到一个用户地址的时候可以读写，但是过一段时间就不能了
可能原因
- 用户空间地址可能已经发生了变化。用户进程可能已经释放了该地址或重新分配了内存，导致原来的地址不再有效
- 操作系统的内存保护机制可能导致内核无法访问用户空间的地址
- 如果内核和用户空间的数据在进行同步操作时出现问题，可能导致地址的有效性检测失败。例如，内核线程和用户线程在不同步的情况下对同一地址进行操作，可能会引发竞争条件。

锁定用户页面

使用get_user_pages函数

long get_user_pages(unsigned long start, unsigned long nr_pages,unsigned int gup_flags, struct page **pages);

传递参数pages是供函数获取到页之后修改用的，相当于返回值
然后使用kmap_local_page获取到内核空间的页地址
static inline void *kmap_local_page(struct page *page);
通过内核地址向用户空间写入内容
因为已经获取到了用户地址映射到内核空间的地址，因此可以直接写入

使用memcpy：

memcpy(<内核页地址>+((unsigned long)<用户给的用户空间地址> & ~PAGE_MASK), &<要拷贝的源地址>, sizeof(value));

用户空间地址与页掩码取反的结果求与，实际上是求出用户空间地址在当前页面下的偏移量，加上页地址得到完整的内核空间地址
使用hrtimer的定时器
hrtimer 是 Linux 内核中的高分辨率定时器（High-Resolution Timer）子系统的一部分，它允许开发人员精确地调度和管理定时任务。与传统的 jiffies 计时机制不同，hrtimer 提供了纳秒级的精度，这对于需要精确时间管理的应用程序非常有用，例如实时系统、精确定时事件的触发等。
使用回调函数的方式处理定时器到达的问题，注意回调函数是在中断语境的，要防止阻塞。

代码演示

#include <linux/module.h>
#include <linux/hrtimer.h>
#include <linux/ktime.h>
#include <linux/sched.h>
#include <linux/signal.h>
#include <linux/fs.h>
#include <linux/cdev.h>
#include <linux/device.h>
#include <linux/slab.h>
#include <linux/uaccess.h>

#define DEVICE_NAME "my_hrtimer_device"
#define CLASS_NAME "my_hrtimer_class"
#define IOCTL_SET_PID _IOW('f', 1, pid_t*)

static struct hrtimer my_hrtimer;
static ktime_t kt_periode;
static struct class* my_hrtimer_class = NULL;
static struct device* my_hrtimer_device = NULL;
static dev_t dev_num;
static struct cdev my_cdev;
static pid_t user_pid = -1;
static struct task_struct *user_task = NULL;

enum hrtimer_restart my_hrtimer_callback(struct hrtimer *timer) {
    if (user_task) {
        send_sig_info(SIGUSR1, SEND_SIG_PRIV, user_task);  // 发送信号给用户进程
    }

    hrtimer_forward_now(timer, kt_periode);
    return HRTIMER_RESTART;
}

static long my_ioctl(struct file *file, unsigned int cmd, unsigned long arg) {
    switch (cmd) {
        case IOCTL_SET_PID:
            if (copy_from_user(&user_pid, (pid_t __user *)arg, sizeof(user_pid))) {
                return -EFAULT;
            }
            user_task = pid_task(find_vpid(user_pid), PIDTYPE_PID);
            if (!user_task) {
                return -ESRCH;  // 无法找到该 PID 对应的进程
            }
            printk(KERN_INFO "Received PID: %d\n", user_pid);
            break;
        default:
            return -ENOTTY;
    }
    return 0;
}

static struct file_operations fops = {
    .unlocked_ioctl = my_ioctl,
};

static int __init my_hrtimer_init(void) {
    int ret;

    printk(KERN_INFO "Initializing hrtimer module.\n");

    // 注册字符设备
    ret = alloc_chrdev_region(&dev_num, 0, 1, DEVICE_NAME);
    if (ret < 0) {
        printk(KERN_ERR "Failed to allocate char device region\n");
        return ret;
    }

    cdev_init(&my_cdev, &fops);
    ret = cdev_add(&my_cdev, dev_num, 1);
    if (ret < 0) {
        unregister_chrdev_region(dev_num, 1);
        printk(KERN_ERR "Failed to add char device\n");
        return ret;
    }

    my_hrtimer_class = class_create(CLASS_NAME);
    if (IS_ERR(my_hrtimer_class)) {
        cdev_del(&my_cdev);
        unregister_chrdev_region(dev_num, 1);
        printk(KERN_ERR "Failed to create class\n");
        return PTR_ERR(my_hrtimer_class);
    }

    my_hrtimer_device = device_create(my_hrtimer_class, NULL, dev_num, NULL, DEVICE_NAME);
    if (IS_ERR(my_hrtimer_device)) {
        class_destroy(my_hrtimer_class);
        cdev_del(&my_cdev);
        unregister_chrdev_region(dev_num, 1);
        printk(KERN_ERR "Failed to create device\n");
        return PTR_ERR(my_hrtimer_device);
    }

    // 设置定时器周期
    kt_periode = ktime_set(0, 1000000000); // 1秒

    // 初始化定时器
    hrtimer_init(&my_hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
    my_hrtimer.function = my_hrtimer_callback;

    // 启动定时器
    hrtimer_start(&my_hrtimer, kt_periode, HRTIMER_MODE_REL);

    return 0;
}

static void __exit my_hrtimer_exit(void) {
    int ret;

    // 取消定时器
    ret = hrtimer_cancel(&my_hrtimer);
    if (ret) {
        printk(KERN_INFO "Timer was still in use.\n");
    }

    // 注销设备
    device_destroy(my_hrtimer_class, dev_num);
    class_destroy(my_hrtimer_class);
    cdev_del(&my_cdev);
    unregister_chrdev_region(dev_num, 1);

    printk(KERN_INFO "Exiting hrtimer module.\n");
}

module_init(my_hrtimer_init);
module_exit(my_hrtimer_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Frank");
MODULE_DESCRIPTION("A simple hrtimer example module with signal to wake up user process");

用户端程序（执行需要sudo权限）

#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/time.h>

#define IOCTL_SET_PID _IOW('f', 1, pid_t*)

// 返回的是微秒时间戳
__uint64_t timestamp()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (tv.tv_sec * 1000000 + tv.tv_usec);
}
__uint64_t prev;

void handle_signal(int sig) {
    if (sig == SIGUSR1) {
        printf("Received SIGUSR1 signal!time interval is %lu\n", timestamp() - prev);
        prev = timestamp();
    }
}

int main() {
    prev = timestamp();
    // 设置信号处理程序
    struct sigaction sa;
    sa.sa_handler = handle_signal;
    sa.sa_flags = 0;
    sigemptyset(&sa.sa_mask);

    if (sigaction(SIGUSR1, &sa, NULL) == -1) {
        perror("sigaction");
        exit(EXIT_FAILURE);
    }

    int fd = open("/dev/my_hrtimer_device", O_RDWR);
    if (fd == -1) {
        perror("open");
        exit(EXIT_FAILURE);
    }

    pid_t pid = getpid();
    if (ioctl(fd, IOCTL_SET_PID, &pid) == -1) {
        perror("ioctl");
        close(fd);
        exit(EXIT_FAILURE);
    }

    // 等待信号
    while (1) {
        pause();  // 等待信号
    }

    close(fd);
    return 0;
}

结果

text

Received SIGUSR1 signal!time interval is 999464
Received SIGUSR1 signal!time interval is 1000214
Received SIGUSR1 signal!time interval is 999859
Received SIGUSR1 signal!time interval is 1000258
Received SIGUSR1 signal!time interval is 999416
Received SIGUSR1 signal!time interval is 1000597
Received SIGUSR1 signal!time interval is 999601
Received SIGUSR1 signal!time interval is 1000106
Received SIGUSR1 signal!time interval is 999795
Received SIGUSR1 signal!time interval is 999836
Received SIGUSR1 signal!time interval is 999758
Received SIGUSR1 signal!time interval is 1000267
Received SIGUSR1 signal!time interval is 999734
Received SIGUSR1 signal!time interval is 1000015
Received SIGUSR1 signal!time interval is 100045

调度问题

如果在hrtimer的回调函数中发送信号到用户态，此时往往达不到超过内核进程调度tick的精确度
因此建议直接在hrtimer的回调函数中直接执行需要完成的工作
hrtimer的回调函数不能执行schedule()函数，因为这个函数所在的语境一般是中断返回函数，是不允许进程切换的，是关闭中断的

使用VMWare和Ubuntu虚拟机挂载主机硬盘充当云盘

发表于 2024-06-30 更新于 2024-08-20
本文字数： 1.2k 阅读时长 ≈ 2 分钟

挂载主机目录到虚拟机

在虚拟机设置中如图找到共享文件夹选项
按照提示添加主机共享文件夹到虚拟机
设置开机自动挂载
有时候Ubuntu开机的时候不会自动挂载文件夹导致无法共享，此时需要设置systemctl脚本
创建一个脚本文件来执行挂载命令sudo nano /usr/local/bin/mount-hgfs.sh

添加以下内容到脚本文件中：

#!/bin/bash
sudo mount -t fuse.vmhgfs-fuse .host:/ /mnt/hgfs -o allow_other

执行sudo chmod +x /usr/local/bin/mount-hgfs.sh
创建一个systemd服务文件来运行挂载脚本
sudo nano /etc/systemd/system/mount-hgfs.service

写入以下内容

[Unit]
Description=Mount VMware Shared Folders
After=network-online.target

[Service]
Type=oneshot
ExecStart=/usr/local/bin/mount-hgfs.sh
RemainAfterExit=yes

[Install]
WantedBy=default.target

启用并启动服务

sudo systemctl enable mount-hgfs.service
sudo systemctl start mount-hgfs.service

安装使用samba

sudo apt install samba
编辑Samba配置文件/etc/samba/smb.conf

追加

[shared]
   path = /mnt/mydisk
   browseable = yes
   read only = no
   guest ok = yes

设置权限（可忽略这一步）
- sudo chmod 777 /mnt/mydisk
重启sambasudo systemctl restart smbd
在Windows文件管理器输入\\your_ubuntu_ip\shared或者Linux文件管理器连接到服务器，输入smb://your_ubuntu_ip/shared

端口映射

将内网的445端口映射到外网方便访问

如果无法使用桥接模式，怎么在外界访问samba

主要应对一些开启了屏蔽模式的局域网
如图操作
然后直接访问\\远程主机ip\shared即可

windows下一些实用的网络工具

测试某个远端端口是否可以访问
Test-NetConnection -ComputerName <IP> -Port <端口>
- 失败情况
设置基于SSH的端口转发
- 教程
  Windows配置本地端口转发
使用netsh
- 查看netsh interface portproxy show all

设置转发

netsh interface portproxy add v4tov4 listenport=端口号 listenaddress=监听地址 connectport=目标端口 connectaddress=目标地址

编译并更换树莓派内核

发表于 2024-06-28 更新于 2024-07-10
本文字数： 907 阅读时长 ≈ 2 分钟

严格参考下文的官网方式
参考网站
编译内核官方参考
实时内核官方参考
编译指令
在树莓派github连接下载内核压缩包
解压到/usr/src目录下
切换超级用户sudo passwd root设置密码
sudo su切换到超级用户
apt install git bc bison flex libssl-dev libncurses-dev make安装必要的包
执行KERNEL=<你的内核名字>和sudo make bcm2712_defconfig
- 注意设置完环境变量之后就不能切换用户了
使用make menuconfig修改内核选项
修改.config中的CONFIG_LOCALVERSION选项为自己希望的自定义内核后缀名
- 注意，上述内容在make menuconfig后会被覆盖，因此要在上一步之后进行
make -j4 Image.gz modules dtbs编译内核

make modules_install

# 这一步是备份，名字不冲突可以不执行
sudo cp /boot/firmware/$KERNEL.img /boot/firmware/$KERNEL-backup.img
# 安装内核
sudo cp arch/arm64/boot/Image.gz /boot/firmware/$KERNEL.img
sudo cp arch/arm64/boot/dts/broadcom/*.dtb /boot/firmware/
sudo cp arch/arm64/boot/dts/overlays/*.dtb* /boot/firmware/overlays/
sudo cp arch/arm64/boot/dts/overlays/README /boot/firmware/overlays/

然后使用sudo vim /boot/firmware/config.txt
最后添加一句kernel=<你的内核名字>.img
reboot重启
最终成功切换到自己定义的内核

实时内核

完全按照官网的指示来
去rt patch找包的时候找符合自己大版本的即可，小版本也相同的可能不好找
注意有时候patch中可能会出现fail的情况，不全是成功，但是不影响编译
结果
测试CAN的驱动不受影响

C语言通过重写malloc等函数实现对内存泄漏的检测

发表于 2024-06-21
本文字数： 3k 阅读时长 ≈ 6 分钟

重写带参数的宏实现对内存泄漏的检测

#define malloc(size) _malloc(size, __FILE__, __LINE__)
#define free(ptr) _free(ptr, __FILE__, __LINE__)

使用C语言的__FILE__宏定位文件，使用__LINE__定位行数

进一步定义函数

void* _malloc(size_t size, const char* filename, int line)
{
    void* p = malloc(size);
    printf("[+]%p, %s, %d\n", p, filename, line);
    return p;
}

void _free(void* ptr, const char *filename, int line)
{
    free(ptr);
    printf("[-]%p, %s, %d\n", ptr, filename, line);
}

注意上述的宏定义需要在定义指定的函数_malloc和_free之后执行
线程安全的完整例子
#define _GNU_SOURCE 是一个预处理指令，它用于启用GNU C库（glibc）中的各种扩展功能。这些扩展功能包含了许多标准C库中没有的额外功能和特性，包括额外的函数、常量和类型等

定义 _GNU_SOURCE 可以启用GNU C库中的许多扩展功能，使程序能够使用标准C库和POSIX标准之外的额外功能

如果你要使用 dlsym 函数，并希望它能够使用 RTLD_NEXT 这个特殊的标识符，你可能需要定义 _GNU_SOURCE。这是因为 RTLD_NEXT 是GNU扩展的一部分，而不是标准POSIX的一部分

#define _GNU_SOURCE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <dlfcn.h>


// 数据结构定义
typedef struct MemBlock {
    void *ptr;
    size_t size;
    const char *file;
    int line;
    struct MemBlock *next;
} MemBlock;

static MemBlock *mem_list = NULL;
static pthread_mutex_t mem_mutex = PTHREAD_MUTEX_INITIALIZER;

// 原始的 malloc 和 free 函数指针
static void *(*real_malloc)(size_t) = NULL;
static void (*real_free)(void *) = NULL;

// 添加内存块到链表
void add_mem_block(void *ptr, size_t size, const char *file, int line) {
    if (!real_malloc) {
        real_malloc = malloc;
    }
    
    pthread_mutex_lock(&mem_mutex);
    MemBlock *new_block = (MemBlock *)real_malloc(sizeof(MemBlock));
    new_block->ptr = ptr;
    new_block->size = size;
    new_block->file = file;
    new_block->line = line;
    new_block->next = mem_list;
    mem_list = new_block;
    pthread_mutex_unlock(&mem_mutex);
}

// 从链表中移除内存块
void remove_mem_block(void *ptr) {
    pthread_mutex_lock(&mem_mutex);
    MemBlock *current = mem_list;
    MemBlock *previous = NULL;
    while (current) {
        if (current->ptr == ptr) {
            if (previous) {
                previous->next = current->next;
            } else {
                mem_list = current->next;
            }
            real_free(current);
            pthread_mutex_unlock(&mem_mutex);
            return;
        }
        previous = current;
        current = current->next;
    }
    pthread_mutex_unlock(&mem_mutex);
}

// malloc 钩子函数
void *malloc_hook(size_t size, const char *file, int line) {
    void *ptr = real_malloc(size);
    if (ptr) {
        add_mem_block(ptr, size, file, line);
    }
    return ptr;
}

// free 钩子函数
void free_hook(void *ptr, const char *file, int line) {
    if (ptr) {
        remove_mem_block(ptr);
        real_free(ptr);
    }
}

// 检查内存泄漏
void check_memory_leaks() {
    pthread_mutex_lock(&mem_mutex);
    MemBlock *current = mem_list;
    while (current) {
        fprintf(stderr, "Memory leak detected: %p (%zu bytes) allocated at %s:%d\n",
                current->ptr, current->size, current->file, current->line);
        current = current->next;
    }
    pthread_mutex_unlock(&mem_mutex);
}

// 宏定义替换 malloc 和 free
#define malloc(size) malloc_hook(size, __FILE__, __LINE__)
#define free(ptr) free_hook(ptr, __FILE__, __LINE__)

int main() {
    // 使用 dlsym 获取原始的 malloc 和 free 函数指针
    real_malloc = (void *(*)(size_t))dlsym(RTLD_NEXT, "malloc");
    real_free = (void (*)(void *))dlsym(RTLD_NEXT, "free");

    // 示例用法
    char *leak = (char *)malloc(10); // 这个分配未释放，应该被检测到
    char *no_leak = (char *)malloc(20);
    free(no_leak);

    check_memory_leaks(); // 检测并打印内存泄漏

    return 0;
}

Linux多线程信号处理

发表于 2024-05-25
本文字数： 2.1k 阅读时长 ≈ 4 分钟

信号等待`sigwait`函数

sigwait函数用于等待特定的信号以备处理

#include <signal.h>

int sigwait(const sigset_t *set, int *sig);

在Linux系统中，一般来讲一个多线程的程序收到信号的时候，信号会被发送给主线程(main函数所在的线程)，如果主线程不具备处理某个信号的能力而且也没有屏蔽该信号的话，进程会被直接终止。然而，这并不是绝对的规则，因为信号的传递行为受到操作系统的影响。
当一个进程的一组线程中只有一个线程具备sigwait的时候，信号会被传递给这个线程

注意，假如准备使用sigwait处理信号，则不能同时使用signal()注册信号，因为使用signal注册的信号处理函数会在线程遇到信号的时候直接异步执行，执行的进程号是main函数所在的主线程

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sched.h>
#include <signal.h>
#include <unistd.h>

#define THREADS 11

// 信号处理函数
void signal_handler(int signal_num) {
    if (signal_num == SIGUSR1) {
        printf("Received SIGUSR1 at process: %d , thread: %lu\n", getpid(), pthread_self());
    }
}

void *worker(void *arg) {
    struct sched_param param;
    int policy = SCHED_FIFO;
    
    param.sched_priority = 50;
    
    
    if (pthread_setschedparam(pthread_self(), policy, &param)) {
        perror("pthread_setschedparam");
        exit(EXIT_FAILURE);
    }
    if(arg != NULL)
    {
        printf("signal handler thread %lu\n", pthread_self());
        // 定义一个信号集
        sigset_t set;
        int signal_num;
        // 初始化信号集，添加需要处理的信号
        sigemptyset(&set);
        sigaddset(&set, SIGUSR1);
        // signal(SIGUSR1, signal_handler);
        while (1) {
            // 这里是你的工作代码
            sigwait(&set, &signal_num);
            printf("Received signal %d at thread %lu\n", signal_num, pthread_self());
            // sched_yield();
        }
    }
    else 
    {
        printf("thread %lu\n", pthread_self());
        while (1)
        {
            sleep(1);
        }
        
    }

    return NULL;
}

int main() {
    pthread_t tid[THREADS];
    int i;

    pid_t pid = getpid();
    printf("pid: %d\n", pid);
    // 屏蔽主线程中的SIGUSR1信号，以便在信号处理线程中处理
    sigset_t set;
    sigemptyset(&set);
    sigaddset(&set, SIGUSR1);
    pthread_sigmask(SIG_BLOCK, &set, NULL);
    // signal(SIGUSR1, signal_handler);
    printf("Main thread %lu\n", pthread_self());
    for (i = 0; i < THREADS; i++) {
        if (pthread_create(&tid[i], NULL, worker, NULL)) {
            perror("pthread_create");
            exit(EXIT_FAILURE);
        }
    }
    int f = 1;
    pthread_t sighandler;
    pthread_create(&sighandler, NULL, worker, &f);

    for (i = 0; i < THREADS; i++) {
        if (pthread_join(tid[i], NULL)) {
            perror("pthread_join");
            exit(EXIT_FAILURE);
        }
    }
    pthread_join(sighandler, NULL);

    return 0;
}

旅行商问题

发表于 2024-05-22
本文字数： 2k 阅读时长 ≈ 4 分钟

旅行商问题

此题实际上是一个动态规划的问题
B站讲解
将整个路径排成一个圈，这一圈总的路程最小
因此从哪个点出发已经无所谓了，指定为0
先递推一个开环问题，也就是从某个固定点出发遍历地图上所有的点，最短的总路径是什么
- 任意一个长度为n，结尾点为i的问题都依赖于一个长度为n-1，而且不包括i点的路径的总路程
递推数组中记录[按位表示的经历过的点][末尾位置][路线的总长度]
递推
n从2开始
对于所有长度为n-1的路径，搜索其中所有到达过的点不同的路径
对于到达过的点相同的路径，按末尾点不同搜索路径
用地图上除了开始点之外的所有点尝试作为新的到达点
- 如果这个点该路径已经到达过了，跳过
- 如果没有，则将其添加到路径中，将路径的总长度增加一个原来的末尾点到这个点的距离
将路径的末尾点修改为当前点
查找长度为n的路径表中是否已经存在了<到达点与其相同><末尾点与其相同>的路径
- 如果存在，将其长度和刚求出的长度取最小值，更新为新的<到达点与其相同><末尾点与其相同>的所有路径的最小长度（不关心中间点的顺序，只在意结束位置）
最开始的时候，向dp图长度为1的路径添加所有起始点以外的点，长度为从起始点到任意点的距离，表示从开始点到任意其他点的路径
结束的时候，长度为n的路径应该具有相同的到达点（也就是除了开始点之外的点全部到达过），这是末尾点不同，根据不同的末尾点，寻找末尾点返回起始点的距离，将其加到路径的长度上计算出每条长度为n的路径的闭环长度

最短的一条就是结果

#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <climits>
using namespace std;

vector<vector<int>> to;
vector<unordered_map<int, unordered_map<int, int>>> dp;
int main() {
    int n;
    cin>>n;
    to = vector<vector<int>>(n, vector<int>(n));
    for(int i = 0; i<n; ++i)
    {
        for(int j = 0;j<n; ++j)
        {
            cin>>to[i][j];
        }
    }
    dp = vector<unordered_map<int, unordered_map<int, int>>>(n+1);
    // 默认从0开始
    // dp的第一个下标是路径长度，第二个是当前到达过的点标志（从低到高按位），第三个是当前路径的最后一个点
    for(int i = 1; i<n; ++i)
    {
        dp[1][1<<i][i] = to[0][i];

    }
    for(int len = 2; len<n; ++len)
    {
        for(auto p : dp[len-1])
        {
            for(auto q : p.second)
            {
                for(int s = 1; s<n; ++s)
                {
                    if((1<<s)&p.first)continue;
                    if(dp[len].count(p.first|1<<s))
                    {
                        if(dp[len][p.first|1<<s].count(s))
                        {
                            dp[len][p.first|1<<s][s] = min(dp[len][p.first|1<<s][s], q.second+to[q.first][s]);
                        }
                        else 
                        {
                            dp[len][p.first|1<<s][s] = q.second+to[q.first][s];
                        }
                    }
                    else 
                    {
                        dp[len][p.first|1<<s][s] = q.second+to[q.first][s];
                    }
                }
            }
        }

    }
    int minDist = INT_MAX;
    for(auto p : dp[n-1])
    {
        for(auto q:p.second)
        {
            minDist = min(minDist, q.second+to[q.first][0]);
        }
    }
    cout<<minDist<<endl;
}
// 64 位输出请用 printf("%lld")

Ubuntu读取PS4手柄

发表于 2024-05-17 更新于 2024-09-13
本文字数： 2.2k 阅读时长 ≈ 4 分钟

链接

长安手柄的share键和PS键直到手柄快闪两次反复，配对状态
使用bluetoothctl工具
命令行敲击之后，输入power on
agent on
default-agent
scan on
找到名字（最右边一列）中带有Wireless Controller字样的设备
与之MAC地址配对pair XX:XX:XX:XX:XX:XX
然后connect XX:XX:XX:XX:XX:XX
第二次链接
按一次PS键，白灯呼吸闪烁即可
可能需要执行power on
同样使用bluetoothctl工具如上
输入命令查看配对的设备：paired-devices
connect XX:XX:XX:XX:XX:XX
使用trust <MAC地址>的方式信任设备
读取
使用sudo evtest查看手柄状态
6是触控板，8是按钮（不包括左边的四个方向键）
例子

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <libevdev/libevdev.h>

void print_event(struct input_event *ev) {
    if (ev->type == EV_ABS) {
        switch (ev->code) {
            case ABS_X:
                printf("Left stick X: %d\n", ev->value);
                break;
            case ABS_Y:
                printf("Left stick Y: %d\n", ev->value);
                break;
            case ABS_RX:
                printf("Right stick X: %d\n", ev->value);
                break;
            case ABS_RY:
                printf("Right stick Y: %d\n", ev->value);
                break;
            case ABS_Z:
                printf("Left trigger: %d\n", ev->value);
                break;
            case ABS_RZ:
                printf("Right trigger: %d\n", ev->value);
                break;
        }
    } else if (ev->type == EV_KEY) {
        switch (ev->code) {
            case BTN_A:
                printf("Cross button: %s\n", ev->value ? "pressed" : "released");
                break;
            case BTN_B:
                printf("Circle button: %s\n", ev->value ? "pressed" : "released");
                break;
            case BTN_X:
                printf("Square button: %s\n", ev->value ? "pressed" : "released");
                break;
            case BTN_Y:
                printf("Triangle button: %s\n", ev->value ? "pressed" : "released");
                break;
        }
    }
}

int main() {
    struct libevdev *dev = NULL;
    // eventX要用sudo evtest自己看
    int fd = open("/dev/input/eventX", O_RDONLY | O_NONBLOCK);
    if (fd < 0) {
        perror("Failed to open device");
        return 1;
    }

    int rc = libevdev_new_from_fd(fd, &dev);
    if (rc < 0) {
        fprintf(stderr, "Failed to init libevdev (%s)\n", strerror(-rc));
        return 1;
    }

    printf("Input device name: \"%s\"\n", libevdev_get_name(dev));

    while (1) {
        struct input_event ev;
        rc = libevdev_next_event(dev, LIBEVDEV_READ_FLAG_NORMAL, &ev);
        if (rc == 0) {
            print_event(&ev);
        } else if (rc != -EAGAIN) {
            fprintf(stderr, "Failed to read next event (%s)\n", strerror(-rc));
            break;
        }

        usleep(10000);  // Sleep for 10ms to reduce CPU usage
    }

    libevdev_free(dev);
    close(fd);
    return 0;
}

排列组合题目

发表于 2024-05-15
本文字数： 887 阅读时长 ≈ 2 分钟

组合数的计算

C(n, 0)+C(n, 1)+...+C(n, n) = 2^n
n是偶数的时候，C(n, 0)+C(n, 2)+...+C(n, n)=2^(n-1)
n是奇数的时候，C(n, 1)+C(n, 3)+...+C(n, n)=2^(n-1)
注意某些组合问题，回溯问题可以直接借用这个方式求解
5.12阿里
小红定义一个数组是好数组，当且仅当所有奇数出现了奇数次，所有偶数出现了偶数次。现在小红拿到了一个数组，她希望取一个该数组的非空子序列(可以不连续)，使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于答案过大，请对1e9+ 7取模。
对于每个数字，如果该数字为奇数，且该数字一共出现了x次，则出现奇数次的方案数为c(x,1)+c(x,3)+c(x,5)+…+c(x,x).其中c表示组合数，这个大小就是2^(x-1)，但是该数字也可以不出现，所以还要加一，一共就是2^(x-1)+1种方案

偶数就是c(x,0)+c(x,2)+…c(x,x),这个也是2^(x-1),然后乘起来，再减去全部都不出现的一次，即减去空串的情况，就是最后答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int a[100010],pow2[100100];
map<int,int>mp;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    pow2[0]=1;
    int ans=1;
    for(int i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
    for(auto i:mp){
        if(i.first&1)
        ans=ans*(pow2[i.second-1]+1)%mod;
        else ans=ans*pow2[i.second-1]%mod;
    }
    cout<<ans-1;
}

栈相关题目

发表于 2024-05-14
本文字数： 474 阅读时长 ≈ 1 分钟

1047. 删除字符串中的所有相邻重复项

此题是将字符串的每个元素依次加入栈中，如果此时栈顶的元素与要加入的相同，就把二者都弹出
否则就正常加入

最后生成结果字符串的时候将栈中的元素弹出并且倒序插入即可

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};

有些时候因为误操作或者vscode自身识别出错会导致在远程链接的时候选择了错误的对方主机操作系统

copy_from_user和copy_to_user

刚拿到一个用户地址的时候可以读写，但是过一段时间就不能了

锁定用户页面

使用hrtimer的定时器

调度问题

挂载主机目录到虚拟机

设置开机自动挂载

安装使用samba

端口映射

如果无法使用桥接模式，怎么在外界访问samba

windows下一些实用的网络工具

Windows配置本地端口转发

参考网站

编译指令

实时内核

重写带参数的宏实现对内存泄漏的检测

信号等待sigwait函数

旅行商问题

递推

链接

第二次链接

读取

组合数的计算

5.12阿里

1047. 删除字符串中的所有相邻重复项

`copy_from_user`和`copy_to_user`

信号等待`sigwait`函数