void main(void)        /* This really IS void, no error here. */
{            /* The startup routine assumes (well, ...) this */
/*
 * Interrupts are still disabled. Do necessary setups, then
 * enable them
 */
//前面这里做的所有事情都是在对内存进行拷贝
     ROOT_DEV = ORIG_ROOT_DEV;//设置操作系统的根文件
     drive_info = DRIVE_INFO;//设置操作系统驱动参数
     //解析setup.s代码后获取系统内存参数
    memory_end = (1<<20) + (EXT_MEM_K<<10);
    //取整4k的内存大小
    memory_end &= 0xfffff000;
    if (memory_end > 16*1024*1024)//控制操作系统的最大内存为16M
        memory_end = 16*1024*1024;
    if (memory_end > 12*1024*1024) 
        buffer_memory_end = 4*1024*1024;//设置高速缓冲区的大小，跟块设备有关，跟设备交互的时候，充当缓冲区，写入到块设备中的数据先放在缓冲区里，只有执行sync时才真正写入；这也是为什么要区分块设备驱动和字符设备驱动；块设备写入需要缓冲区，字符设备不需要是直接写入的
    else if (memory_end > 6*1024*1024)
        buffer_memory_end = 2*1024*1024;
    else
        buffer_memory_end = 1*1024*1024;
    main_memory_start = buffer_memory_end;

struct buffer_head {
    char * b_data;            /* pointer to data block (1024 bytes):单个数据块大小1KB */
    unsigned long b_blocknr;    /* block number */
    unsigned short b_dev;        /* device (0 = free) */
    unsigned char b_uptodate;    /*数据是否更新*/
    unsigned char b_dirt;        /* 0-clean空现,1-dirty已被占用*/
    unsigned char b_count;        /* users using this block */
    /*如果缓冲区的某个block被锁，上层应用是没法从这个block对应的磁盘空间读数据的，这里有个漏洞：
    A进程锁定了某block，B进程想办法解锁，然后就能监听A进程从磁盘读写了哪些数据
    */
    unsigned char b_lock;        /* 0 - ok, 1 -locked:锁用于多进程/多线程之间同步，避免数据出错*/
    struct task_struct * b_wait;/*A正在使用这个缓存，并已经锁定；B也想用，就用这个字段记录；等A用完后从这里找到B再给B用*/
    struct buffer_head * b_prev;
    struct buffer_head * b_next;
    struct buffer_head * b_prev_free;
    struct buffer_head * b_next_free;
};

// hash表的主要作用是减少查找比较元素所花费的时间。通过在元素的存储位置与关
// 键字之间建立一个对应关系(hash函数)，我们就可以直接通过函数计算立刻查询到指定
// 的元素。建立hash函数的指导条件主要是尽量确保散列在任何数组项的概率基本相等。
// 建立函数的方法有多种，这里Linux-0.11主要采用了关键字除留余数法。因为我们
// 寻找的缓冲块有两个条件，即设备号dev和缓冲块号block，因此设计的hash函数肯定
// 需要包含这两个关键值。这两个关键字的异或操作只是计算关键值的一种方法。再对
// 关键值进行MOD运算就可以保证函数所计算得到的值都处于函数数组项范围内。
#define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
#define hash(dev,block) hash_table[_hashfn(dev,block)]

//// 利用hash表在高速缓冲区中寻找给定设备和指定块号的缓冲区块。
// 如果找到则返回缓冲区块的指针，否则返回NULL。
static struct buffer_head * find_buffer(int dev, int block)
{        
    struct buffer_head * tmp;

    // 搜索hash表，寻找指定设备号和块号的缓冲块。
    for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
        if (tmp->b_dev==dev && tmp->b_blocknr==block)
            return tmp;
    return NULL;
}

//// 利用hash表在高速缓冲区中寻找指定的缓冲块。若找到则对该缓冲块上锁
// 返回块头指针。
struct buffer_head * get_hash_table(int dev, int block)
{
    struct buffer_head * bh;

    for (;;) {
        // 在高速缓冲中寻找给定设备和指定块的缓冲区块，如果没有找到则返回NULL。
        if (!(bh=find_buffer(dev,block)))
            return NULL;
        // 对该缓冲块增加引用计数，并等待该缓冲块解锁。由于经过了睡眠状态，其他任务可能会更改这个缓存区对应的dev和block号
        // 因此有必要在验证该缓冲块的正确性，并返回缓冲块头指针。
        bh->b_count++;
        wait_on_buffer(bh);
        if (bh->b_dev == dev && bh->b_blocknr == block)
            return bh;
        // 如果在睡眠时该缓冲块所属的设备号或块设备号发生了改变，则撤消对它的
        // 引用计数，重新寻找。
        bh->b_count--;
    }
}

//// 等待指定缓冲块解锁
// 如果指定的缓冲块bh已经上锁就让进程不可中断地睡眠在该缓冲块的等待队列b_wait中。
// 在缓冲块解锁时，其等待队列上的所有进程将被唤醒。虽然是在关闭中断(cli)之后
// 去睡眠的，但这样做并不会影响在其他进程上下文中影响中断。因为每个进程都在自己的
// TSS段中保存了标志寄存器EFLAGS的值，所以在进程切换时CPU中当前EFLAGS的值也随之
// 改变。使用sleep_on进入睡眠状态的进程需要用wake_up明确地唤醒。
static inline void wait_on_buffer(struct buffer_head * bh)
{
    cli();                          // 关中断
    while (bh->b_lock)              // 如果已被上锁则进程进入睡眠，等待其解锁
        sleep_on(&bh->b_wait);
    sti();                          // 开中断
}

//// 取高速缓冲中指定的缓冲块
// 检查指定（设备号和块号）的缓冲区是否已经在高速缓冲中。如果指定块已经在
// 高速缓冲中，则返回对应缓冲区头指针退出；如果不在，就需要在高速缓冲中设置一个
// 对应设备号和块好的新项。返回相应的缓冲区头指针。
struct buffer_head * getblk(int dev,int block)
{
    struct buffer_head * tmp, * bh;

repeat:
    // 搜索hash表，如果指定块已经在高速缓冲中，则返回对应缓冲区头指针，退出。
    if ((bh = get_hash_table(dev,block)))
        return bh;
    // 扫描空闲数据块链表，寻找空闲缓冲区。
    // 首先让tmp指向空闲链表的第一个空闲缓冲区头
    tmp = free_list;
    do {
        // 如果该缓冲区正被使用（引用计数不等于0），则继续扫描下一项。对于
        // b_count = 0的块，即高速缓冲中当前没有引用的块不一定就是干净的
        // (b_dirt=0)或没有锁定的(b_lock=0)。因此，我们还是需要继续下面的判断
        // 和选择。例如当一个任务该写过一块内容后就释放了，于是该块b_count()=0
        // 但b_lock不等于0；当一个任务执行breada()预读几个块时，只要ll_rw_block()
        // 命令发出后，它就会递减b_count; 但此时实际上硬盘访问操作可能还在进行，
        // 因此此时b_lock=1, 但b_count=0.
        if (tmp->b_count)
            continue;
        // 如果缓冲头指针bh为空，或者tmp所指缓冲头的标志(修改、锁定)权重小于bh
        // 头标志的权重，则让bh指向tmp缓冲块头。如果该tmp缓冲块头表明缓冲块既
        // 没有修改也没有锁定标志置位，则说明已为指定设备上的块取得对应的高速
        // 缓冲块，则退出循环。否则我们就继续执行本循环，看看能否找到一个BANDNESS()
        // 最小的缓冲块。BADNESS等于0意味着b_block和b_dirt都是0，这块缓存区还没被使用，目标缓存区已经找到，可以跳出循环了
        if (!bh || BADNESS(tmp)<BADNESS(bh)) {
            bh = tmp;
            if (!BADNESS(tmp))
                break;
        }
/* and repeat until we find something good */
    } while ((tmp = tmp->b_next_free) != free_list);
    // 如果循环检查发现所有缓冲块都正在被使用(所有缓冲块的头部引用计数都>0)中，
    // 则睡眠等待有空闲缓冲块可用。当有空闲缓冲块可用时本进程会呗明确的唤醒。
    // 然后我们跳转到函数开始处重新查找空闲缓冲块。
    if (!bh) {
        sleep_on(&buffer_wait);
        goto repeat;
    }
    // 执行到这里，说明我们已经找到了一个比较合适的空闲缓冲块了。于是先等待该缓冲区
    // 解锁（多任务同时运行，刚找到的缓存块可能已经被其他任务抢先一步找到并使用了，所以要再次检查）。如果在我们睡眠阶段该缓冲区又被其他任务使用的话，只好重复上述寻找过程。
    wait_on_buffer(bh);
    if (bh->b_count)
        goto repeat;
    // 如果该缓冲区已被修改，则将数据写盘，并再次等待缓冲区解锁。同样地，若该缓冲区
    // 又被其他任务使用的话，只好再重复上述寻找过程。
    while (bh->b_dirt) {
        sync_dev(bh->b_dev);
        wait_on_buffer(bh);
        if (bh->b_count)
            goto repeat;
    }
/* NOTE!! While we slept waiting for this block, somebody else might */
/* already have added "this" block to the cache. check it */
    // 在高速缓冲hash表中检查指定设备和块的缓冲块是否乘我们睡眠之际已经被加入
    // 进去(毕竟是多任务系统，有可能被其他任务抢先使用并放入has表)。如果是的话，就再次重复上述寻找过程。
    if (find_buffer(dev,block))
        goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
    // 于是让我们占用此缓冲块。置引用计数为1，复位修改标志和有效(更新)标志。
    bh->b_count=1;
    bh->b_dirt=0;
    bh->b_uptodate=0;
    // 从hash队列和空闲队列块链表中移出该缓冲区头，让该缓冲区用于指定设备和
    // 其上的指定块。然后根据此新的设备号和块号重新插入空闲链表和hash队列新
    // 位置处。并最终返回缓冲头指针。
    remove_from_queues(bh);
    bh->b_dev=dev;
    bh->b_blocknr=block;
    insert_into_queues(bh);
    return bh;
}

/* already have added "this" block to the cache. check it */
    // 在高速缓冲hash表中检查指定设备和块的缓冲块是否乘我们睡眠之际已经被加入
    // 进去（毕竟是多任务，期间可能会被其他任务抢先使用并放入hash表）。如果是的话，就再次重复上述寻找过程。
    if (find_buffer(dev,block))
        goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
    // 于是让我们占用此缓冲块。置引用计数为1，复位修改标志和有效(更新)标志。
    bh->b_count=1;
    bh->b_dirt=0;
    bh->b_uptodate=0;
    // 从hash队列和空闲队列块链表中移出该缓冲区头，让该缓冲区用于指定设备和
    // 其上的指定块。然后根据此新的设备号和块号重新插入空闲链表和hash队列新
    // 位置处。并最终返回缓冲头指针。
    /*将缓冲块从旧的队列移出，添加到新的队列中，即哈希表的头，空闲表的尾，这样能够迅速找到该存在的块，而该缓冲块存在的时间最长*/
    remove_from_queues(bh);
    bh->b_dev=dev;
    bh->b_blocknr=block;
    insert_into_queues(bh);
    return bh;

//// 从hash队列和空闲缓冲区队列中移走缓冲块。
// hash队列是双向链表结构，空闲缓冲块队列是双向循环链表结构。
static inline void remove_from_queues(struct buffer_head * bh)
{
/* remove from hash-queue */
    if (bh->b_next)
        bh->b_next->b_prev = bh->b_prev;
    if (bh->b_prev)
        bh->b_prev->b_next = bh->b_next;
    // 如果该缓冲区是该队列的头一个块（每个hash偏移的头），则让hash表的对应项指向本队列中的下一个
    // 缓冲区。
    if (hash(bh->b_dev,bh->b_blocknr) == bh)
        hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
/* remove from free list */
    if (!(bh->b_prev_free) || !(bh->b_next_free))
        panic("Free block list corrupted");
    bh->b_prev_free->b_next_free = bh->b_next_free;
    bh->b_next_free->b_prev_free = bh->b_prev_free;
    // 如果空闲链表头指向本缓冲区，则让其指向下一缓冲区。
    if (free_list == bh)
        free_list = bh->b_next_free;
}

//// 将缓冲块插入空闲链表尾部，同时放入hash队列中。
static inline void insert_into_queues(struct buffer_head * bh)
{
/* put at end of free list */
    bh->b_next_free = free_list;
    bh->b_prev_free = free_list->b_prev_free;
    free_list->b_prev_free->b_next_free = bh;
    free_list->b_prev_free = bh;
/* put the buffer in new hash-queue if it has a device */
    // 请注意当hash表某项第1次插入项时，hash()计算值肯定为Null，因此此时得到
    // 的bh->b_next肯定是NULL，所以应该在bh->b_next不为NULL时才能给b_prev赋
    // bh值。
    bh->b_prev = NULL;
    bh->b_next = NULL;
    if (!bh->b_dev)
        return;
    bh->b_next = hash(bh->b_dev,bh->b_blocknr);
    hash(bh->b_dev,bh->b_blocknr) = bh;
    bh->b_next->b_prev = bh;                // 此句前应添加"if (bh->b_next)"判断
}

// 释放指定缓冲块。
// 等待该缓冲块解锁。然后引用计数递减1，并明确地唤醒等待空闲缓冲块的进程。
void brelse(struct buffer_head * buf)
{
    if (!buf)
        return;
    wait_on_buffer(buf);
    if (!(buf->b_count--))
        panic("Trying to free free buffer");
    wake_up(&buffer_wait);
}

// 缓冲区初始化函数
// 参数buffer_end是缓冲区内存末端。对于具有16MB内存的系统，缓冲区末端被设置为4MB.
// 对于有8MB内存的系统，缓冲区末端被设置为2MB。该函数从缓冲区开始位置start_buffer
// 处和缓冲区末端buffer_end处分别同时设置(初始化)缓冲块头结构和对应的数据块。直到
// 缓冲区中所有内存被分配完毕。
void buffer_init(long buffer_end)
{
    struct buffer_head * h = start_buffer;
    void * b;
    int i;

    // 首先根据参数提供的缓冲区高端位置确定实际缓冲区高端位置b。如果缓冲区高端等于1Mb，
    // 则因为从640KB - 1MB被显示内存和BIOS占用，所以实际可用缓冲区内存高端位置应该是
    // 640KB。否则缓冲区内存高端一定大于1MB。
    if (buffer_end == 1<<20)
        b = (void *) (640*1024);
    else
        b = (void *) buffer_end;
    // 这段代码用于初始化缓冲区，建立空闲缓冲区块循环链表，并获取系统中缓冲块数目。
    // 操作的过程是从缓冲区高端开始划分1KB大小的缓冲块，与此同时在缓冲区低端建立
    // 描述该缓冲区块的结构buffer_head,并将这些buffer_head组成双向链表。
    // h是指向缓冲头结构的指针，而h+1是指向内存地址连续的下一个缓冲头地址，也可以说
    // 是指向h缓冲头的末端外。为了保证有足够长度的内存来存储一个缓冲头结构，需要b所
    // 指向的内存块地址 >= h 缓冲头的末端，即要求 >= h+1.
    while ( (b -= BLOCK_SIZE) >= ((void *) (h+1)) ) {
        h->b_dev = 0;                       // 使用该缓冲块的设备号
        h->b_dirt = 0;                      // 脏标志，即缓冲块修改标志
        h->b_count = 0;                     // 缓冲块引用计数
        h->b_lock = 0;                      // 缓冲块锁定标志
        h->b_uptodate = 0;                  // 缓冲块更新标志(或称数据有效标志)
        h->b_wait = NULL;                   // 指向等待该缓冲块解锁的进程
        h->b_next = NULL;                   // 指向具有相同hash值的下一个缓冲头
        h->b_prev = NULL;                   // 指向具有相同hash值的前一个缓冲头
        h->b_data = (char *) b;             // 指向对应缓冲块数据块（1024字节）
        h->b_prev_free = h-1;               // 指向链表中前一项
        h->b_next_free = h+1;               // 指向连表中后一项
        h++;                                // h指向下一新缓冲头位置
        NR_BUFFERS++;                       // 缓冲区块数累加
        if (b == (void *) 0x100000)         // 若b递减到等于1MB，则跳过384KB
            b = (void *) 0xA0000;           // 让b指向地址0xA0000(640KB)处
    }
    h--;                                    // 让h指向最后一个有效缓冲块头
    free_list = start_buffer;               // 让空闲链表头指向头一个缓冲快
    free_list->b_prev_free = h;             // 链表头的b_prev_free指向前一项(即最后一项)。
    h->b_next_free = free_list;             // h的下一项指针指向第一项，形成一个环链
    // 最后初始化hash表，置表中所有指针为NULL。
    for (i=0;i<NR_HASH;i++)
        hash_table[i]=NULL;
}

//// 从设备上读取数据块。
// 该函数根据指定的设备号 dev 和数据块号 block，首先在高速缓冲区中申请一块
// 缓冲块。如果该缓冲块中已经包含有有效的数据就直接返回该缓冲块指针，否则
// 就从设备中读取指定的数据块到该缓冲块中并返回缓冲块指针。
struct buffer_head * bread(int dev,int block)
{
    struct buffer_head * bh;

    // 在高速缓冲区中申请一块缓冲块。如果返回值是NULL，则表示内核出错，停机。
    // 然后我们判断其中说是否已有可用数据。如果该缓冲块中数据是有效的（已更新）
    // 可以直接使用，则返回。
    if (!(bh=getblk(dev,block)))
        panic("bread: getblk returned NULL\n");
    if (bh->b_uptodate)
        return bh;
    // 否则我们就调用底层快设备读写ll_rw_block函数，产生读设备块请求。然后
    // 等待指定数据块被读入，并等待缓冲区解锁。在睡眠醒来之后，如果该缓冲区已
    // 更新，则返回缓冲区头指针，退出。否则表明读设备操作失败，于是释放该缓
    // 冲区，返回NULL，退出。
    ll_rw_block(READ,bh);
    wait_on_buffer(bh);
    if (bh->b_uptodate)
        return bh;
    brelse(bh);
    return NULL;
}

void ll_rw_block(int rw, struct buffer_head * bh)
{
    unsigned int major;

    if ((major=MAJOR(bh->b_dev)) >= NR_BLK_DEV ||
    !(blk_dev[major].request_fn)) {
        printk("Trying to read nonexistent block-device\n\r");
        return;
    }
    make_request(major,rw,bh);
}

/*
 * add-request adds a request to the linked list.
 * It disables interrupts so that it can muck with the
 * request-lists in peace.
 */
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
    struct request * tmp;

    req->next = NULL;
    cli();
    if (req->bh)
        req->bh->b_dirt = 0;
    if (!(tmp = dev->current_request)) {
        dev->current_request = req;
        sti();
        (dev->request_fn)();
        return;
    }
    for ( ; tmp->next ; tmp=tmp->next)
        if ((IN_ORDER(tmp,req) || 
            !IN_ORDER(tmp,tmp->next)) &&
            IN_ORDER(req,tmp->next))
            break;
    req->next=tmp->next;
    tmp->next=req;
    sti();
}

static void make_request(int major,int rw, struct buffer_head * bh)
{
    struct request * req;
    int rw_ahead;

/* WRITEA/READA is special case - it is not really needed, so if the */
/* buffer is locked, we just forget about it, else it's a normal read */
    if ((rw_ahead = (rw == READA || rw == WRITEA))) {
        if (bh->b_lock)
            return;
        if (rw == READA)
            rw = READ;
        else
            rw = WRITE;
    }
    if (rw!=READ && rw!=WRITE)
        panic("Bad block dev command, must be R/W/RA/WA");
    lock_buffer(bh);
    if ((rw == WRITE && !bh->b_dirt) || (rw == READ && bh->b_uptodate)) {
        unlock_buffer(bh);
        return;
    }
repeat:
/* we don't allow the write-requests to fill up the queue completely:
 * we want some room for reads: they take precedence. The last third
 * of the requests are only for reads.
 */
    if (rw == READ)
        req = request+NR_REQUEST;
    else
        req = request+((NR_REQUEST*2)/3);
/* find an empty request */
    while (--req >= request)
        if (req->dev<0)
            break;
/* if none found, sleep on new requests: check for rw_ahead */
    if (req < request) {
        if (rw_ahead) {
            unlock_buffer(bh);
            return;
        }
        sleep_on(&wait_for_request);
        goto repeat;
    }
/* fill up the request-info, and add it to the queue */
    req->dev = bh->b_dev;
    req->cmd = rw;
    req->errors=0;
    req->sector = bh->b_blocknr<<1;
    req->nr_sectors = 2;
    req->buffer = bh->b_data;
    req->waiting = NULL;
    req->bh = bh;
    req->next = NULL;
    add_request(major+blk_dev,req);
}

/*
 * This is used in the elevator algorithm: Note that
 * reads always go before writes. This is natural: reads
 * are much more time-critical than writes.
 */
#define IN_ORDER(s1,s2) \
((s1)->cmd<(s2)->cmd || ((s1)->cmd==(s2)->cmd && \
((s1)->dev < (s2)->dev || ((s1)->dev == (s2)->dev && \
(s1)->sector < (s2)->sector))))