3.3.1 Preparing to Install the Hard Disk File System by Process 1
3.3.1.2 Read the Hard Disk Boot Blocks to the Buffer
In Linux 0.11, the partition table is the most basic information of the hard disk. Other information can be obtained from this information, which is stored in the boot block. A hard disk has only one boot block, that is, No. 0 logic block, and the boot block has two sectors, the first sector of which is useful. Our computer has only one hard disk. The hard disk boot block is read into the buffer, which can be used by follow-up procedures. This work is completed through calling the bread() function (bread is short for block read).
The code is as follows:
BIOS + = 16;
}
if (hd_info[1].cyl) //Judge the number of hard drives NR_HD = 2;
else
NR_HD = 1;
#endif
for (i = 0 ; i<NR_HD ; i++) { //one physical hard disk can have four logical disk at most, //0 is the physical disk, 1-4 is logical disk, in sum, 5; the //first physical disk is 0*5, the second physical disk is 1*5 hd[i*5].start_sect = 0;
hd[i*5].nr_sects = hd_info[i].head*
hd_info[i].sect*hd_info[i].cyl;
}
if ((cmos_disks = CMOS_READ(0x12)) & 0xf0) if (cmos_disks & 0x0f)
NR_HD = 2;
else
NR_HD = 1;
else
NR_HD = 0;
for (i = NR_HD ; i < 2 ; i++) { hd[i*5].start_sect = 0;
hd[i*5].nr_sects = 0;
}
for (drive = 0 ; drive<NR_HD ; drive++) { //the device id of the first physical disk //is 0x300, the second is 0x305,
//read the block 0, namely boot block, //of every physical disk,
//which has the partition information if (!(bh = bread(0x300 + drive*5,0))) {
printk(“Unable to read partition table of drive%d\n\r”, drive);
panic(“”);
}
……
}
//Code path:kernel/blk_dev/hd.c:
……
//First physical disk device number is 0x300, second is 0x305, read the block 0, //namely boot block, of every physical disk, which has the partition information
for (drive = 0 ; drive<NR_HD ; drive++) { if (!(bh = bread(0x300 + drive*5,0))) {
printk(“Unable to read partition table of drive%d\n\r”, drive);
panic(“”);
}
……
}
After entering the bread function, first call the getblk() function to apply for a free buffer block.
The code is as follows:
//Code path:fs/buffer.c:
struct buffer_head * bread(int dev,int block)
{//read specific dev, block, dev of the first hard disk is 0x300, //block is 0
struct buffer_head * bh;
if (!(bh = getblk(dev,block))) //get a buffer block corresponding //to the specific dev and block or //get a free buffer block in buffer panic(“bread: getblk returned NULL\n”); //it’s the first
//time to use buffer, thus, it’s //impossible to have no free buffer
ROM BIOS and VGA
Kernel
Enable interrupt
0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
drive_info
hd_info hd Step 1: initialize hd_info
Step 2: use hd_info structure to work out the initial sector of hard disk, as well as sector, and record in the hd data structure
After executing sys_setup Before executing sys_setup
hd
hd_info
drive_info Process status
Process 0 Process 1
Ready Interruptible
Current process
Figure 3.15 Initialize hard drive control data structure.
Figure 3.16 describes in detail the procedures when applying for a free buffer block.
In the getblk() function, first call get_hash_table to search hash table, which search the hard disk that will be read (with the same device id and block id) has been read into the buffer by other processes. If it has been read into the buffer, it can be used directly. The purpose of using hash tables for queries is to improve query speed. It is the first step shown in Figure 3.16.
The code is as follows:
Once inside the get_hash_table function, call the find_buffer() function to search the buffer block whose device number and block number are appointed in the buffer; if it can be found, it can be used directly.
The code is as follows:
if (bh->b_uptodate) //now, it’s the first use, the free buffer which //we get is surely not used by other process
return bh;
ll_rw_block(READ,bh);
wait_on_buffer(bh);
if (bh->b_uptodate) return bh;
brelse(bh);
return NULL;
}
//Code path:fs/buffer.c:
……
//find the corresponding buffer block with the same dev, block or free //buffer block in the buffer: dev:0x300, block:0
struct buffer_head * getblk(int dev,int block) {
struct buffer_head * tmp, * bh;
repeat:
if (bh = get_hash_table(dev,block)) return bh;
tmp = free_list;
do {
if (tmp->b_count) continue;
if (!bh || BADNESS(tmp)<BADNESS(bh)) { bh = tmp;
if (!BADNESS(tmp)) break;
}
……
}
//Code path:fs/buffer.c:
……
//find the corresponding buffer block with the same dev, block or free //buffer block in the buffer: dev:0x300, block:0
struct buffer_head * get_hash_table(int dev, int block)
{
struct buffer_head * bh;
for (;;) {
if (!(bh = find_buffer(dev,block)))
return NULL; //now, it’s the first use, thus, it’s //impossible to find the block has //been read into buffer
bh->b_count++;
wait_on_buffer(bh);
if (bh->b_dev = = dev && bh->b_blocknr = = block) return bh;
bh->b_count— — ; }
}
Kernel
Enable interrupt 0x00000 0x9FFFF 0xFFFFF 0x3FFFFF 0x5FFFFF 0xFFFFFF
Kernel code area Kernel data area
Process status
Process 0 Process 1 Ready Interruptible
hash_table[307]
Table head
Table head
Table head Step 1:
look up hash table
Step 2: reapply a free buffer block in free table
Step 3: search an appropriate buffer block in free list
Step 4: hook with hash table
0 307
Current process
After executing getblk
ROM BIOS and VGA
Before executing getblk hash_table[307]
0 307
Table head
Figure 3.16 Find the buffer block.
Now, this is the first time to use the buffer. Thus, there are no buffer blocks read into the buffer; that is, hash_table does not hook any nodes and find_buffer() returns NULL.
The code is as follows:
The function find_buffer(), get_hash_table(), exit to the getblk() function, and apply for a new free buffer block in the free form. All buffer blocks are now bound in the free table, so apply for a new buffer block in the free table, as shown in the second step in Figure 3.16.
The code is as follows:
//Code path:fs/buffer.c:
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)//b_dirt, b_lock are 0, BADNESS(bh) is 00 struct buffer_head * getblk(int dev,int block)
{
struct buffer_head * tmp, * bh;
repeat:
if (bh = get_hash_table(dev,block)) return bh;
tmp = free_list;
do {
if (tmp->b_count) //tmp-> b_count is 0
continue;
if (!bh || BADNESS(tmp)<BADNESS(bh)) { //bh is 0 bh = tmp;
if (!BADNESS(tmp)) //BADNESS(tmp) is 00, get the free buffer!
break;
}
/* and repeat until we find something good */
} while ((tmp = tmp->b_next_free) ! = free_list);
if (!bh) {//in this case, it’s impossible to cannot find free buffer sleep_on(&buffer_wait);
goto repeat;
}
wait_on_buffer(bh);//buffer block is unlock if (bh->b_count)//the buffer block is not in use
goto repeat;
while (bh->b_dirt) {//the content of buffer block is not revised sync_dev(bh->b_dev);
wait_on_buffer(bh);
if (bh->b_count) goto repeat;
}
if (find_buffer(dev,block)) //now, find the free buffer, but it does not link to the //hash table
goto repeat ;
……
//Code psth:fs/buffer.c:
……
//NR_HASH is 307, for dev:0x300, block:0,_hashfn(dev,block) is 154
#define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
#define hash(dev,block) hash_table[_hashfn(dev,block)]
……
//find the buffer block with specific dev, block in the buffer static struct buffer_head * find_buffer(int dev, int block) {
struct buffer_head * tmp;
for (tmp = hash(dev,block) ; tmp ! = NULL ; tmp = tmp->b_next) //now, the tmp->b_next //is NULL
if (tmp->b_dev == dev && tmp->b_blocknr == block) return tmp;
return NULL;
}
After getting a buffer block, initialize it, and attach it to the hash_table.
The code is as follows:
In order to make it easier to understand the code, we will step out of this process (Figures 3.17 through 3.19).
//Code path:fs/buffer.c:
struct buffer_head * getblk(int dev,int block) {
……
if (find_buffer(dev,block)) goto repeat;
bh->b_count = 1;//be used bh->b_dirt = 0;
bh->b_uptodate = 0;
remove_from_queues(bh);
bh->b_dev = dev;
bh->b_blocknr = block;
insert_into_queues(bh);
return bh;
}
//Code path:fs/buffer.c:
……
static inline void remove_from_queues(struct buffer_head * bh) {
/* remove from hash-queue */
if (bh->b_next) //bh->b_next is NULL bh->b_next->b_prev = bh->b_prev;
if (bh->b_prev) //bh->b_prev is NULL bh->b_prev->b_next = bh->b_next;
if (hash(bh->b_dev,bh->b_blocknr) == bh)//in this case, it //will never appear hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
/* remove from free list */
if (!(bh->b_prev_free) || !(bh->b_next_free))//never appear in //the normal //condition 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;
}
……
The code binding hash_ table is as follows (Figures 3.20 through 3.22):
//Code path:fs/buffer.c:
……
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 */
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;
}
……
Initial State
bh->b_next_free->b_prev_free
bh->b_prev_free->b_next_free bh->b_prev_free
Initial state
bh->b_next_free
bh
tmp free_list
Figure 3.17 Step 1.
The state after executing the following two lines
bh->b_prev_free->b_next_free = bh->b_next_free;
bh->b_next_free->b_prev_free = bh->b_prev_free;
bh->b_prev_free->b_next_free
bh->b_next_free->b_prev_free free_list
tmp bh bh->b_prev_free
bh->b_next_free
Figure 3.18 Step 2.
The state after executing the following
free_list = bh -> b_next_free bh->b_prev_free->b_next_free
bh->b_next_free->b_prev_free
free_list
tmp bh
bh->b_prev_free bh->b_next_free
Figure 3.19 Step 3.
The state after executing the following 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;
154
NULL bh tmp
free_list
bh->b_next_free->b_prev_free bh->b_prev_free->b_next_free
bh->b_prev_free
bh->b_next_free
Figure 3.20 Step 4.
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;
The state after executing the following
NULL
free_list
tmp bh bh->b_prev_free
bh->b_next_free
bh->b_next_free->b_prev_free bh->b_prev_free->b_next_free
154
Figure 3.21 Step 5.
After executing getblk(), return to bread().