《操作系统真象还原》第八章（一） —

本章节所有代码托管在miniOS_32

章节任务介绍

任务简介

上一节，我们成功为我们的内核开启了中断机制，并使用时钟中断进行了测试

本节我们将开启操作系统内存管理的相关内容

本章的主要任务有：

实现ASSERT断言

实现字符串处理函数

实现管理物理内存的数据结构位图

实现assert断言

断言介绍

断言（Assertion） 可视为一种调试工具，主要用于检测程序在运行时是否满足某个条件。如果断言条件为真，程序继续执行；如果为假，程序通常会停止执行并抛出错误信息，帮助开发者发现潜在的问题。

断言语句通常具有以下结构：

1

assert( condition, "Error message if condition is false")

condition 是你期望为真的条件。
如果 condition 为 True，程序继续执行。
如果 condition 为 False，则会抛出一个异常或错误，并输出后面的错误信息。

断言实现

中断状态控制

一方面，当内核运行中出现问题时，多属于严重的错误，着实没必要再运行下去了。另一方面，断言在输出报错信息时，屏幕输出不应该被其他进程干扰，这样咱们才能专注于报错信息。

综上两点原因,ASSERT排查出错误后，最好在关中断的情况下打印报错信息。

内核运行时，为了通过时钟中断定时调度其他任务，大部分情况下中断是打开的，因此我们需要实现一些可以控制中断开关的函数

如下，在/kernel/interrupt.h中添加中断状态的数据结构，以及控制中断状态的函数声明

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/*定义中断状态*/
enum intr_status
{
    INTR_OFF, // 表示中断关闭
    INTR_ON   // 表示中断打开
};

/* 获取当前中断状态 */
enum intr_status intr_get_status(void);
/* 开中断并返回开中断前的状态*/
enum intr_status intr_enable(void);
/* 关中断,并且返回关中断前的状态 */
enum intr_status intr_disable(void);
/* 将中断状态设置为status */
enum intr_status intr_set_status(enum intr_status);

然后我们在/kernel/interrupt.c中实现其功能

获取中断状态

如下是eflags寄存器中所有的控制状态位

其中第9位，IF位用于表示和控制中断状态

IF位为1，表示系统处于开中断状态

IF位为0，表示系统处于关中断状态

第9位的十六进制数为0x2000，故我们以此作为掩码，来获取eflags中IF位的值，从而获取中断状态

如下定义IF位的掩码

1
2
3


/*eflags寄存器中的if位的掩码*/
#define EFLAGS_IF 0x00000200 // 表示eflags寄存器中的if位为1
                             // 将该宏与当前的if位（中断状态）进行与操作，即可获取当前的中断状态

同时利用IF位的掩码定义获取IF位的宏

1
2
3
4
5
6
7


/*
功能：获取eflags寄存器中的值
pushfl将eflags寄存器中的值压入栈顶，再使用popl将栈顶的值弹出到EFLAG_VAR所在内存中
该约束自然用表示内存的字母，但是内联汇编中没有专门表示约束内存的字母，所以只能用g
代表可以是任意寄存器，内存或立即数
*/
#define GET_EFLAGS(EFLAG_VAR) asm volatile("pushfl;pop %0" : "=g"(EFLAG_VAR))

接下来就可以实现获取中断状态的函数了，如下所示

1
2
3
4
5
6
7


/* 获取当前中断状态 */
enum intr_status intr_get_status()
{
    uint32_t eflags = 0;
    GET_EFLAGS(eflags);
    return (EFLAGS_IF & eflags) ? INTR_ON : INTR_OFF;
}

开中断控制函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/* 开中断并返回开中断前的状态*/
enum intr_status intr_enable()
{
    enum intr_status old_status;
    if (INTR_ON == intr_get_status())
    {
        old_status = INTR_ON;
        return old_status;
    }
    else
    {
        old_status = INTR_OFF;
        asm volatile("sti"); // 开中断,sti指令将IF位置1
        return old_status;
    }
}

注，sti指令用于开中断

关中断控制函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/* 关中断,并且返回关中断前的状态 */
enum intr_status intr_disable()
{
    enum intr_status old_status;
    if (INTR_ON == intr_get_status())
    {
        old_status = INTR_ON;
        asm volatile("cli" : : : "memory"); // 关中断,cli指令将IF位置0
                                            // cli指令不会直接影响内存。然而，从一个更大的上下文来看，禁用中断可能会影响系统状态，
                                            // 这个状态可能会被存储在内存中。所以改变位填 "memory" 是为了安全起见，确保编译器在生成代码时考虑到这一点。
        return old_status;
    }
    else
    {
        old_status = INTR_OFF;
        return old_status;
    }
}

设置中断状态函数

1
2
3
4
5


/* 将中断状态设置为status */
enum intr_status intr_set_status(enum intr_status status)
{
    return status & INTR_ON ? intr_enable() : intr_disable(); // enable与disable函数会返回旧中断状态
}

断言实现

我们首先在/kernel/debug.h中定义ASSERT的断言宏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


/*
如果CONDITION条件为真则什么也不做
否则就输出相关断言信息
*/
#define ASSERT(CONDITION)  \
    if (CONDITION)         \
    {                      \
    }                      \
    else                   \
    {                      \
        PANIC(#CONDITION); \
    } // 加#后，传入的参数变成字符串

其实现逻辑很简单，如果CONDITION条件为真，则什么也不做，否则就调用PANIC宏，将判断为假的条件作为字符串参数传入，然后打印错误信息

其中PANIC宏的实现如下

1
2
3
4
5
6
7


void panic_spin(char *filename, int line, const char *func, const char *condition);

/*
...是可变参数，也就是随便你传多少个参数，然后原封不动地传到__VA_ARGS_那里去
__FILE__,__LINE__,__func__是预定义宏，代表这个宏所在的文件名，行数，与函数名字，编译器处理
*/
#define PANIC(...) panic_spin(__FILE__, __LINE__, __func__, __VA_ARGS__)

可以看到，PANIC宏的实现是通过调用panic_spin函数将错误信息进行打印实现的

panic_spin函数定义在/kernel/debug.c中，如下所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 打印文件名,行号,函数名,条件，并使程序悬停 */
void panic_spin(char *filename, int line, const char *func, const char *condition)
{
    intr_disable(); // 发生错误时打印错误信息，不应该被打扰，因此需要关中断
    put_str("\n\n\n!!!!! error !!!!!\n");
    put_str("filename:");
    put_str(filename);
    put_str("\n");
    put_str("line:0x");
    put_int(line);
    put_str("\n");
    put_str("function:");
    put_str((char *)func);
    put_str("\n");
    put_str("condition:");
    put_str((char *)condition);
    put_str("\n");
    while (1) ;
}

代码编译

1

gcc-4.4 -o $(pwd)/bin/debug.o -c -fno-builtin -m32 -I $(pwd)/lib/kernel/ -I $(pwd)/lib/ -I $(pwd)/kernel/ $(pwd)/kernel/debug.c

编译通过，没有出现任何问题

实现字符串操作函数

本节的代码依旧是准备工作，为了将来的开发工作更得心应手，本节打算实现与字符串相关的函数，此类函数以后会被经常用到

以下是字符串操作函数的相关定义

/lib/kernel/string.h

 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


#ifndef __LIB_STRING_H
#define __LIB_STRING_H
#include "stdint.h"
/*内存初始化函数，将dst_起始的size个字节的初始化为value*/
void memset(void *dst_, uint8_t value, uint32_t size);
/*内存拷贝函数，将src_起始处的size个字节的内容拷贝到dst_*/
void memcpy(void *dst_, const void *src_, uint32_t size);
/*
比较两个地址的起始size字节的数据是否相等
相等则返回0
如果不相等，则比较第一个不相等的字节数据
*/
int memcmp(const void *a_, const void *b_, uint32_t size);
/*字符串拷贝*/
char *strcpy(char *dst_, const char *src_);
/*获取字符串的长度*/
uint32_t strlen(const char *str);
/*
比较两个字符串
    若a_中的字符与b_中的字符全部相同，则返回0
    如果不同，则比较第一个不同的字符
        如果a_>b_返回1，反之返回-1
*/
int8_t strcmp(const char *str1, const char *str2);
/*从左到右查找字符串str中首次出现字符ch的地址*/
char *strchr(const char *string, const uint8_t ch);
/*从后往前查找字符串str中首次出现字符ch的地址(不是下标,是地址)*/
char *strrchr(const char *string, const uint8_t ch);
/* 将字符串src_拼接到dst_后,将回拼接的串地址 */
char *strcat(char *dst_, const char *src_);
/* 在字符串str中查找指定字符ch出现的次数 */
uint32_t strchrs(const char *filename, uint8_t ch);
#endif

可以看到，都是我们平时使用c语言时经常用到的函数，我们在这里只是简单重新实现了一下

/lib/kernel/string.c

  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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161


#include "string.h"
#include "global.h"
#include "debug.h"
/*内存初始化函数，将dst_起始的size个字节的初始化为value*/
void memset(void *dst_, uint8_t value, uint32_t size)
{
    ASSERT(dst_ != NULL);
    uint8_t *dst = (uint8_t *)dst_;
    /*
    先执行*dst=value
    然后执行dst++
    */
    while (size--)
        *dst++ = value;
}

/*
将src_起始处的size个字节的内容拷贝到dst_
*/
void memcpy(void *dst_, const void *src_, uint32_t size)
{
    ASSERT(dst_ != NULL && src_ != NULL);
    uint8_t *src = (uint8_t *)src_;
    uint8_t *dst = (uint8_t *)dst_;
    while (size--)
    {
        *dst++ = *src++;
    }
}

/*
比较两个地址的起始size字节的数据是否相等
相等则返回0
如果不相等，则比较第一个不相等的字节数据
*/
int memcmp(const void *a_, const void *b_, uint32_t size)
{
    ASSERT(a_ != NULL && b_ != NULL);
    const char *a = a_;
    const char *b = b_;
    while (size--)
    {
        if (*a != *b)
        {
            return *a > *b ? 1 : -1;
        }
        a++;
        b++;
    }
    return 0;
}

/*
字符串拷贝
*/
char *strcpy(char *dst_, const char *src_)
{
    ASSERT(dst_ != NULL && src_ != NULL);
    char *res = dst_;
    while ((*dst_++ = *src_++))
        ;
    return res;
}

/*
返回字符串的长度
*/
uint32_t strlen(const char *str)
{
    ASSERT(str != NULL);
    const char *p = str;
    while (*p++);
    return (p - str - 1);
}

/*
比较两个字符串
    若a_中的字符与b_中的字符全部相同，则返回0
    如果不同，则比较第一个不同的字符
        如果a_>b_返回1，反之返回-1
*/
int8_t strcmp(const char *str1, const char *str2)
{
    ASSERT(str1 != NULL && str2 != NULL);
    // 比较两个字符串
    while (*str1 != '\0' && *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            return (*str1 < *str2) ? -1 : 1;
        }
        ++str1;
        ++str2;
    }

    // 如果两个字符串走到末尾还是没有不同，比较它们的结束符
    return (*str1 == *str2) ? 0 : (*str1 < *str2 ? -1 : 1);
}

/*
从左到右查找字符串str中首次出现字符ch的地址
const char *str，表示str指向的字符串内容不可改变
但是str指针值是可以改变的
*/
char *strchr(const char *str, const uint8_t ch)
{
    ASSERT(str != NULL);
    while (*str != 0)
    {
        if (*str == ch)
            return (char *)str;
        ++str;
    }
    return NULL;
}

/*
从后往前查找字符串str中首次出现字符ch的地址(不是下标,是地址)
*/
char *strrchr(const char *str, const uint8_t ch)
{
    ASSERT(str != NULL);
    const char *last_char = NULL;
    /* 从头到尾遍历一次,若存在ch字符,last_char总是该字符最后一次出现在串中的地址(不是下标,是地址)*/
    while (*str != 0)
    {
        if (*str == ch)
        {
            last_char = str;
        }
        str++;
    }
    return (char *)last_char;
}

/* 将字符串src_拼接到dst_后,将回拼接的串地址 */
char *strcat(char *dst_, const char *src_)
{
    ASSERT(dst_ != NULL && src_ != NULL);
    char *p = dst_;
    while (*p++)
        ;
    --p;
    while ((*p++ = *src_++))
        ;
    return dst_;
}
/* 在字符串str中查找指定字符ch出现的次数 */
uint32_t strchrs(const char *str, uint8_t ch)
{
    ASSERT(str != NULL);
    uint32_t cnt = 0;
    const char *p = str;
    while (*p != 0)
    {
        if (*p == ch)
            cnt++;
        ++p;
    }
    return cnt;
}

这部分内容比较简单，具体实现细节不再赘述

代码编译

1

gcc-4.4 -o $(pwd)/bin/string.o -c -fno-builtin -m32 -I $(pwd)/lib/kernel/ -I $(pwd)/lib/ -I $(pwd)/kernel/ $(pwd)/lib/string.c

编译通过，没有问题

位图实现

位图简介

在计算机的内存管理系统中，位图（Bitmap）是一种常用的数据结构，用于高效地管理内存的分配和回收。它通过使用一个位数组来表示内存中各个块（或页面）的状态，进而实现对内存资源的管理。每个二进制位代表一个固定大小的内存块（如页、页框或块），0和1的状态分别表示该内存块是“空闲”的或“已分配”的。

位图的基本概念

在内存管理中，位图通常用于表示一个固定大小的内存块集合，每个内存块用一个二进制位来表示：

0 表示该内存块是“空闲”的，即该内存块没有被分配。
1 表示该内存块是“已分配”的，即该内存块正在被使用。

例如，如果内存被分成了8个块，并且它们的分配情况如下：

1 0 0 1 1 0 0 1

那么这个位图表示：

第1、4、5、8个内存块已分配。
第2、3、6、7个内存块是空闲的。

位图在内存管理中的应用

位图通常用于以下几种内存管理任务：

2.1 内存分配

当需要为一个进程分配内存时，内存管理系统可以使用位图来查找一个或多个空闲的内存块。通过遍历位图，找到连续的若干个0位（表示空闲块），然后将这些空闲块标记为已分配（将相应的位设置为1）。

2.2 内存回收

当进程释放内存时，内存管理系统可以通过修改位图将相应的位重新设置为0，表示这些内存块已空闲，准备重新分配给其他进程。

2.3 内存块分配策略

位图使得内存管理系统能够轻松地选择空闲内存块。常见的策略包括：

最佳适配：寻找最小的足够大空闲块。
最差适配：选择最大的空闲块。
首次适配：从位图中从头开始找到第一个符合要求的空闲块。

2.4 合并和拆分

在某些系统中，内存分配和回收过程中可能会导致内存碎片。位图可以帮助检测空闲块的合并，尤其是在连续块被释放后，系统可以将这些空闲块合并成更大的空闲区域。

位图的实现

首先还是定义位图相关的数据结构以及操作函数的相关定义

/lib/kernel/bitmap.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#ifndef __LIB_KERNEL_BITMAP_H
#define __LIB_KERNEL_BITMAP_H
#include "global.h"
#define BITMAP_MASK 1
struct bitmap
{                            // 这个数据结构就是用来管理整个位图
    uint32_t btmp_bytes_len; // 记录整个位图的大小，单位为字节
    uint8_t *bits;           // 用来记录位图的起始地址，我们未来用这个地址遍历位图时，操作单位指定为最小的字节
};
/*位图初始化*/
void bitmap_init(struct bitmap *btmp);
/*确定位图的bit_idx位是否为1，即判断某块内存是否被分配*/
bool bitmap_scan_test(struct bitmap *btmp, uint32_t bit_idx);
/*在位图中寻找连续的cnt个0，以此来分配一块连续未被占用的内存*/
int bitmap_scan(struct bitmap *btmp, uint32_t cnt);
/*将位图的某一位设置为1或0*/
void bitmap_set(struct bitmap *btmp, uint32_t bit_idx, int8_t value);
#endif

接下来开始正式实现位图的相关操作

/lib/kernel/bitmap.c

1.位图的初始化

1
2
3
4
5


/*位图初始化*/
void bitmap_init(struct bitmap *btmp)
{
    memset(btmp->bits, 0, btmp->btmp_bytes_len);
}

2.确定位图的bit_idx位是否为1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


/*确定位图的bit_idx位是否为1*/
bool bitmap_scan_test(struct bitmap *btmp, uint32_t bit_idx)
{
    //获取bit_idx在位图中第几个字节
    uint32_t byte_idx = bit_idx / 8;
    //获取bit_idx在位图中byte_idx字节处的第几个比特位
    uint32_t bit_odd = bit_idx % 8;
    // 小端字节序，故低位在右侧
    return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_odd));
}

该函数的实现需要做以下几点说明

参数bit_idx是字节级别的，在位图中表示一个索引

计算机内部采用小端字节序，因此掩码应该左移

3.在位图中寻找连续的cnt个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


/*
在位图中寻找连续的cnt个0，以此来分配一块连续未被占用的内存
*/
int bitmap_scan(struct bitmap *btmp, uint32_t cnt)
{
    uint32_t idx_type = 0;
    /*先逐字节比较，找到第一个含有比特0位的字节，0xff=1111 1111*/
    while (btmp->bits[idx_type] == 0xff && idx_type < btmp->btmp_bytes_len)
        ++idx_type;
    ASSERT(idx_type < btmp->btmp_bytes_len);
    if (idx_type == btmp->btmp_bytes_len)
        return -1;

    /*在该字节内找到第一个为0的比特位*/
    int idx_bit = 0;
    while ((uint8_t)(BITMAP_MASK << idx_bit) & btmp->bits[idx_type])
        ++idx_bit;

    /*空闲位在位图内的下标*/
    int bit_idx_start = idx_type * 8 + idx_bit;
    if (cnt == 1)
        return bit_idx_start;

    // 记录还剩余多少位没有判断
    uint32_t bit_left = btmp->btmp_bytes_len * 8 - bit_idx_start;
    uint32_t next_bit = bit_idx_start + 1;
    uint32_t count = 1;

    /*寻找剩余连续的0*/
    bit_idx_start = -1;
    while (bit_left--)
    {
        if (!bitmap_scan_test(btmp, next_bit))
            ++count;
        else
            count = 0;
        if (count == cnt)
        {
            bit_idx_start = next_bit - cnt + 1;
            break;
        }
        ++next_bit;
    }
    return bit_idx_start;
}

4.将位图的某一位设置为1或0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/*
将位图的某一位设置为1或0
*/
void bitmap_set(struct bitmap *btmp, uint32_t bit_idx, int8_t value)
{
    ASSERT((value == 0) || (value == 1));
    uint32_t idx_byte = bit_idx / 8;
    uint32_t idx_odd = bit_idx % 8;
    /* 一般都会用个0x1这样的数对字节中的位操作,
     * 将1任意移动后再取反,或者先取反再移位,可用来对位置0操作。*/
    if (value)
    { // 如果value为1
        btmp->bits[idx_byte] |= (BITMAP_MASK << idx_odd);
    }
    else
    { // 若为0
        btmp->bits[idx_byte] &= ~(BITMAP_MASK << idx_odd);
    }
}

代码编译

1

gcc-4.4 -o $(pwd)/bin/bitmap.o -c -fno-builtin -m32 -I $(pwd)/lib/kernel/ -I $(pwd)/lib/ -I $(pwd)/kernel/ $(pwd)/lib/kernel/bitmap.c