PC's Blog

跳跃表简介

跳跃表是一种以O(log N)期望时间支持查找、插入、删除操作的、有序的数据结构。其性能和红黑树相当，且跳跃表实现更为简单。

如何理解”跳跃“二字

问题描述

root进程调sem_open(XXX, O_CREAT, 0666, 1)创建信号量后，非root进程使用sem_open打开同一个信号量失败，报Permission Denied错

原因分析

非root进程调用sem_open， 以O_CREAT方式打开信号量，需要同时有对该信号量文件的读权限 + 写权限。

ll /dev/shm/sem.semname 查看信号量文件权限，发现权限为0644，缺少其他用户写权限。这个权限与sem_open中指定的权限值0666不一致。

实验简介

实现自己的动态内存分配器（malloc、free、realloc）。

预备知识

• 阅读《CSAPP原书第3版》 9.9小节 —— 动态内存分配。
• 阅读writeup的全部内容。

ctrl + c

中断键，给前台进程组中所有进程发送SIGINT信号，并终止进程。

ctrl + z

挂起键，给前台进程组中所有进程发送SIGTSTP信号, 并挂起进程。被挂起的进程并没有真正结束，可以使用fg或bg命令恢复被挂起的进程。

实验简介

编写一个通用高速缓存模拟器，并优化小型矩阵转置核心函数，以最小化对模拟高速缓存的不命中次数。

预备知识

1. 局部性原理

局部性通常有两种形式：

• 时间局部性：被引用过一次的内存位置很可能在不远的将来被多次引用。
• 空间局部性：如一个内存位置被引用，其附近的内存位置很可能在不远的将来被引用。

msleep和mdelay都是内核的延时函数，原型如下：

1
2

void mdelay(unsigned long msecs);
void msleep(unsigned int millisecs);

区别

mdelay是忙等待函数，会占用CPU资源，延迟时间是准确的。

msleep是休眠函数，不占用CPU资源，延迟时间通常高于给定值。

运行环境

Linux debian 4.19.0-10-amd64

编译内核模块

0. 准备编译所需的内核头文件

系统默认内核头文件路径在/lib/modules/`uname -r`，先确认该路径是否存在：

1

ls /lib/modules/`uname -r`/build

如路径不存在，需要先安装内核头文件，方法如下：

问题描述

打开office软件失败，提示无法找到应用程序的许可证。

原因

Software Protection服务启动失败，可以通过services.msc查看该服务的启动状态

解决方法

修改注册表，将如下文本复制到文件，文件名改为software prtection服务.reg, 双击该文件即可。

实验介绍

本实验中，我们需要利用缓冲区溢出漏洞，来修改一个二进制可执行文件的运行时行为。

预备知识

• 缓冲区溢出的原理，参考《CSAPP原书第3版》3.10小节

• gdb和objdump使用

• x86_64下的汇编

从官网安装指定版本， 以3.12.1版本为例：

1
2
3
4
5
6

wget https://cmake.org/files/v3.12/cmake-3.12.1.tar.gz
tar -zxvf cmake-3.12.1.tar.gz
cd cmake-3.12.1
./bootstrap
make -j8
make install