/* *  linux/fs/bitmap.c * *  (C) 1991  Linus Torvalds */#include <set_seg.h>
/* bitmap.c 程序含有處理i 節(jié)點(diǎn)和磁盤塊位圖的代碼 */

// 字符串頭文件。主要定義了一些有關(guān)字符串操作的嵌入函數(shù)。
// 主要使用了其中的memset()函數(shù)。#include <string.h>// 調(diào)度程序頭文件，定義了任務(wù)結(jié)構(gòu)task_struct、初始任務(wù)0 的數(shù)據(jù)，
// 還有一些有關(guān)描述符參數(shù)設(shè)置和獲取的嵌入式匯編函數(shù)宏語句。#include <linux/sched.h>
// 內(nèi)核頭文件。含有一些內(nèi)核常用函數(shù)的原形定義。#include <linux/kernel.h>
//// 將指定地址(addr)處的一塊內(nèi)存清零。嵌入?yún)R編程序宏。
// 輸入：eax = 0，ecx = 數(shù)據(jù)塊大小BLOCK_SIZE/4，edi = addr。
#define clear_block(addr) _clear_block((long)(addr))
extern _inline void _clear_block(long addr)
{_asm{	pushf
	mov edi,addr
	mov ecx,BLOCK_SIZE/4
	xor al,al
	cld
	rep stosd	popf
}}//#define clear_block(addr) \//__asm__("cld\n\t" \  /*清方向位。*///	"rep\n\t" \  /*重復(fù)執(zhí)行存儲(chǔ)數(shù)據(jù)（0）。*///	"stosl" \//	::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
//// 置位指定地址開始的第nr 個(gè)位偏移處的比特位(nr 可以大于32！)。返回原比特位（0 或1）。
// 輸入：%0 - eax（返回值)，%1 - eax(0)；%2 - nr，位偏移值；%3 - (addr)，addr 的內(nèi)容。
extern _inline int set_bit(int nr,char* addr)
{
	volatile register int __res;
	_asm{
		xor eax,eax
		mov ebx,nr
		mov edx,addr
		bts [edx],ebx
		setb al
		mov __res,eax
	}
	return __res;
}
//#define set_bit(nr,addr) ({\//register int res __asm__("ax"); \//__asm__ __volatile__("btsl %2,%3\n\tsetb %%al": \//"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \//res;})
//// 復(fù)位指定地址開始的第nr 位偏移處的比特位。返回原比特位的反碼（1 或0）。
// 輸入：%0 - eax（返回值)，%1 - eax(0)；%2 - nr，位偏移值；%3 - (addr)，addr 的內(nèi)容。
extern _inline int clear_bit(int nr,char* addr)
{
	volatile register int __res;
	_asm{
		xor eax,eax
		mov ebx,nr
		mov edx,addr
		btr [edx],ebx
		setnb al
		mov __res,eax
	}
	return __res;
}//#define clear_bit(nr,addr) ({\//register int res __asm__("ax"); \//__asm__ __volatile__("btrl %2,%3\n\tsetnb %%al": \//"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \//res;})
//// 從addr 開始尋找第1 個(gè)0 值比特位。
// 輸入：%0 - ecx(返回值)；%1 - ecx(0)；%2 - esi(addr)。
// 在addr 指定地址開始的位圖中尋找第1 個(gè)是0 的比特位，并將其距離addr 的比特位偏移值返回。
extern _inline int find_first_zero(char *addr)
{
	int __res;
	_asm{
		xor ecx,ecx
		mov esi,addr
		cld   /*清方向位。*/
	l1: lodsd   /*取[esi] -> eax。*/
		not eax   /*eax 中每位取反。*/
		bsf edx,eax   /*從位0 掃描eax 中是1 的第1 個(gè)位，其偏移值 -> edx。*/
		je l2   /*如果eax 中全是0，則向前跳轉(zhuǎn)到標(biāo)號(hào)2 處(40 行)。*/
		add ecx,edx   /*偏移值加入ecx(ecx 中是位圖中首個(gè)是0 的比特位的偏移值)*/
		jmp l3   /*向前跳轉(zhuǎn)到標(biāo)號(hào)3 處（結(jié)束）。*/
	l2: add ecx,32   /*沒有找到0 比特位，則將ecx 加上1 個(gè)長字的位偏移量32。*/
		cmp ecx,8192   /*已經(jīng)掃描了8192 位（1024 字節(jié)）了嗎？*/
		jl l1  /*若還沒有掃描完1 塊數(shù)據(jù)，則向前跳轉(zhuǎn)到標(biāo)號(hào)1 處，繼續(xù)。*/
	l3: mov __res,ecx  /*結(jié)束。此時(shí)ecx 中是位偏移量。*/
	}
	return __res;
}/*#define find_first_zero(addr) ({ \int __res; \__asm__("cld\n" \	"1:\tlodsl\n\t" \	"notl %%eax\n\t" \	"bsfl %%eax,%%edx\n\t" \	"je 2f\n\t" \	"addl %%edx,%%ecx\n\t" \	"jmp 3f\n" \	"2:\taddl $32,%%ecx\n\t" \	"cmpl $8192,%%ecx\n\t" \	"jl 1b\n" \ 	"3:" \ 	:"=c" (__res):"c" (0),"S" (addr):"ax","dx","si"); \__res;})*/
//// 釋放設(shè)備dev 上數(shù)據(jù)區(qū)中的邏輯塊block。
// 復(fù)位指定邏輯塊block 的邏輯塊位圖比特位。
// 參數(shù)：dev 是設(shè)備號(hào)，block 是邏輯塊號(hào)（盤塊號(hào)）。void free_block(int dev, int block){	struct super_block * sb;	struct buffer_head * bh;
// 取指定設(shè)備dev 的超級(jí)塊，如果指定設(shè)備不存在，則出錯(cuò)死機(jī)。	if (!(sb = get_super(dev)))		panic("trying to free block on nonexistent device");
// 若邏輯塊號(hào)小于首個(gè)邏輯塊號(hào)或者大于設(shè)備上總邏輯塊數(shù)，則出錯(cuò)，死機(jī)。	if (block < sb->s_firstdatazone || block >= sb->s_nzones)		panic("trying to free block not in datazone");
// 從hash 表中尋找該塊數(shù)據(jù)。若找到了則判斷其有效性，并清已修改和更新標(biāo)志，釋放該數(shù)據(jù)塊。
// 該段代碼的主要用途是如果該邏輯塊當(dāng)前存在于高速緩沖中，就釋放對應(yīng)的緩沖塊。	bh = get_hash_table(dev,block);	if (bh) {		if (bh->b_count != 1) {			printk("trying to free block (%04x:%d), count=%d\n",				dev,block,bh->b_count);			return;		}		bh->b_dirt=0;		// 復(fù)位臟（已修改）標(biāo)志位。		bh->b_uptodate=0;	// 復(fù)位更新標(biāo)志。		brelse(bh);	}
// 計(jì)算block 在數(shù)據(jù)區(qū)開始算起的數(shù)據(jù)邏輯塊號(hào)（從1 開始計(jì)數(shù)）。然后對邏輯塊(區(qū)塊)位圖進(jìn)行操作，
// 復(fù)位對應(yīng)的比特位。若對應(yīng)比特位原來即是0，則出錯(cuò)，死機(jī)。	block -= sb->s_firstdatazone - 1 ;	if (clear_bit(block&8191,sb->s_zmap[block/8192]->b_data)) {		printk("block (%04x:%d) ",dev,block+sb->s_firstdatazone-1);		panic("free_block: bit already cleared");	}
	// 置相應(yīng)邏輯塊位圖所在緩沖區(qū)已修改標(biāo)志。	sb->s_zmap[block/8192]->b_dirt = 1;}
////向設(shè)備dev 申請一個(gè)邏輯塊（盤塊，區(qū)塊）。返回邏輯塊號(hào)（盤塊號(hào)）。
// 置位指定邏輯塊block 的邏輯塊位圖比特位。int new_block(int dev){	struct buffer_head * bh;	struct super_block * sb;	int i,j;
// 從設(shè)備dev 取超級(jí)塊，如果指定設(shè)備不存在，則出錯(cuò)死機(jī)。	if (!(sb = get_super(dev)))		panic("trying to get new block from nonexistant device");
// 掃描邏輯塊位圖，尋找首個(gè)0 比特位，尋找空閑邏輯塊，獲取放置該邏輯塊的塊號(hào)。	j = 8192;	for (i=0 ; i<8 ; i++)		if (bh=sb->s_zmap[i])			if ((j=find_first_zero(bh->b_data))<8192)				break;
// 如果全部掃描完還沒找到(i>=8 或j>=8192)或者位圖所在的緩沖塊無效(bh=NULL)則返回0，
// 退出（沒有空閑邏輯塊）。	if (i>=8 || !bh || j>=8192)		return 0;
// 設(shè)置新邏輯塊對應(yīng)邏輯塊位圖中的比特位，若對應(yīng)比特位已經(jīng)置位，則出錯(cuò)，死機(jī)。	if (set_bit(j,bh->b_data))		panic("new_block: bit already set");
// 置對應(yīng)緩沖區(qū)塊的已修改標(biāo)志。如果新邏輯塊大于該設(shè)備上的總邏輯塊數(shù)，則說明指定邏輯塊在
// 對應(yīng)設(shè)備上不存在。申請失敗，返回0，退出。	bh->b_dirt = 1;	j += i*8192 + sb->s_firstdatazone-1;	if (j >= sb->s_nzones)		return 0;
// 讀取設(shè)備上的該新邏輯塊數(shù)據(jù)（驗(yàn)證）。如果失敗則死機(jī)。	if (!(bh=getblk(dev,j)))		panic("new_block: cannot get block");
// 新塊的引用計(jì)數(shù)應(yīng)為1。否則死機(jī)。	if (bh->b_count != 1)		panic("new block: count is != 1");
// 將該新邏輯塊清零，并置位更新標(biāo)志和已修改標(biāo)志。然后釋放對應(yīng)緩沖區(qū)，返回邏輯塊號(hào)。	clear_block(bh->b_data);	bh->b_uptodate = 1;	bh->b_dirt = 1;	brelse(bh);	return j;}
//// 釋放指定的i 節(jié)點(diǎn)。
// 復(fù)位對應(yīng)i 節(jié)點(diǎn)位圖比特位。void free_inode(struct m_inode * inode){	struct super_block * sb;	struct buffer_head * bh;
	// 如果i 節(jié)點(diǎn)指針=NULL，則退出。	if (!inode)		return;
// 如果i 節(jié)點(diǎn)上的設(shè)備號(hào)字段為0，說明該節(jié)點(diǎn)無用，則用0 清空對應(yīng)i 節(jié)點(diǎn)所占內(nèi)存區(qū)，并返回。	if (!inode->i_dev) {		memset(inode,0,sizeof(*inode));		return;	}
// 如果此i 節(jié)點(diǎn)還有其它程序引用，則不能釋放，說明內(nèi)核有問題，死機(jī)。	if (inode->i_count>1) {		printk("trying to free inode with count=%d\n",inode->i_count);		panic("free_inode");	}
// 如果文件目錄項(xiàng)連接數(shù)不為0，則表示還有其它文件目錄項(xiàng)在使用該節(jié)點(diǎn)，
// 不應(yīng)釋放，而應(yīng)該放回等。	if (inode->i_nlinks)		panic("trying to free inode with links");
// 取i 節(jié)點(diǎn)所在設(shè)備的超級(jí)塊，測試設(shè)備是否存在。	if (!(sb = get_super(inode->i_dev)))		panic("trying to free inode on nonexistent device");
// 如果i 節(jié)點(diǎn)號(hào)=0 或大于該設(shè)備上i 節(jié)點(diǎn)總數(shù)，則出錯(cuò)（0 號(hào)i 節(jié)點(diǎn)保留沒有使用）。	if (inode->i_num < 1 || inode->i_num > sb->s_ninodes)		panic("trying to free inode 0 or nonexistant inode");
// 如果該i 節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)位圖不存在，則出錯(cuò)。	if (!(bh=sb->s_imap[inode->i_num>>13]))		panic("nonexistent imap in superblock");
// 復(fù)位i 節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)位圖中的比特位，如果該比特位已經(jīng)等于0，則出錯(cuò)。	if (clear_bit(inode->i_num&8191,bh->b_data))		printk("free_inode: bit already cleared.\n\r");
// 置i 節(jié)點(diǎn)位圖所在緩沖區(qū)已修改標(biāo)志，并清空該i 節(jié)點(diǎn)結(jié)構(gòu)所占內(nèi)存區(qū)。	bh->b_dirt = 1;	memset(inode,0,sizeof(*inode));}
//// 為設(shè)備dev 建立一個(gè)新i 節(jié)點(diǎn)。返回該新i 節(jié)點(diǎn)的指針。
// 在內(nèi)存i 節(jié)點(diǎn)表中獲取一個(gè)空閑i 節(jié)點(diǎn)表項(xiàng)，并從i 節(jié)點(diǎn)位圖中找一個(gè)空閑i 節(jié)點(diǎn)。struct m_inode * new_inode(int dev){	struct m_inode * inode;	struct super_block * sb;	struct buffer_head * bh;	int i,j;
// 從內(nèi)存i 節(jié)點(diǎn)表(inode_table)中獲取一個(gè)空閑i 節(jié)點(diǎn)項(xiàng)(inode)。	if (!(inode=get_empty_inode()))		return NULL;
// 讀取指定設(shè)備的超級(jí)塊結(jié)構(gòu)。	if (!(sb = get_super(dev)))		panic("new_inode with unknown device");
// 掃描i 節(jié)點(diǎn)位圖，尋找首個(gè)0 比特位，尋找空閑節(jié)點(diǎn)，獲取放置該i 節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)。	j = 8192;	for (i=0 ; i<8 ; i++)		if (bh=sb->s_imap[i])			if ((j=find_first_zero(bh->b_data))<8192)				break;
// 如果全部掃描完還沒找到，或者位圖所在的緩沖塊無效(bh=NULL)則返回0，退出（沒有空閑i 節(jié)點(diǎn)）。	if (!bh || j >= 8192 || j+i*8192 > sb->s_ninodes) {		iput(inode);		return NULL;	}
// 置位對應(yīng)新i 節(jié)點(diǎn)的i 節(jié)點(diǎn)位圖相應(yīng)比特位，如果已經(jīng)置位，則出錯(cuò)。	if (set_bit(j,bh->b_data))		panic("new_inode: bit already set");
// 置i 節(jié)點(diǎn)位圖所在緩沖區(qū)已修改標(biāo)志。	bh->b_dirt = 1;
// 初始化該i 節(jié)點(diǎn)結(jié)構(gòu)。	inode->i_count=1;		// 引用計(jì)數(shù)。	inode->i_nlinks=1;		// 文件目錄項(xiàng)鏈接數(shù)。	inode->i_dev=dev;		// i 節(jié)點(diǎn)所在的設(shè)備號(hào)。	inode->i_uid=current->euid;		// i 節(jié)點(diǎn)所屬用戶id。	inode->i_gid=current->egid;		// 組id。	inode->i_dirt=1;			// 已修改標(biāo)志置位。	inode->i_num = j + i*8192;	// 對應(yīng)設(shè)備中的i 節(jié)點(diǎn)號(hào)。	inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;	// 設(shè)置時(shí)間。	return inode;	// 返回該i 節(jié)點(diǎn)指針。}

/*
		本程序的功能和作用即簡單又清晰，主要用于對i 節(jié)點(diǎn)位圖和邏輯塊位圖進(jìn)行釋放和
	占用處理。操作i 節(jié)點(diǎn)位圖的函數(shù)是free_inode()和new_inode()，操作邏輯塊位圖的函數(shù)
	是free_block()和new_block()。
		函數(shù)free_block()用于釋放指定設(shè)備dev 上數(shù)據(jù)區(qū)中的邏輯塊block。具體操作是復(fù)位
	指定邏輯塊block對應(yīng)邏輯塊位圖中的比特位。它首先取指定設(shè)備dev 的超級(jí)塊，并根據(jù)超
	級(jí)塊上給出的設(shè)備數(shù)據(jù)邏輯塊的范圍，判斷邏輯塊號(hào)block 的有效性。然后在高速緩沖區(qū)中
	進(jìn)行查找，看看指定的邏輯塊現(xiàn)在是否正在高速緩沖區(qū)中，若是，則將對應(yīng)的緩沖塊釋放掉。
	接著計(jì)算block 從數(shù)據(jù)區(qū)開始算起的數(shù)據(jù)邏輯塊號(hào)（從1開始計(jì)數(shù)），并對邏輯塊(區(qū)段)位圖
	進(jìn)行操作，復(fù)位對應(yīng)的比特位。最后根據(jù)邏輯塊號(hào)設(shè)置相應(yīng)邏輯塊位圖在緩沖區(qū)中對應(yīng)的
	緩沖塊的已修改標(biāo)志。
		函數(shù)new_block()用于向設(shè)備dev 申請一個(gè)邏輯塊，返回邏輯塊號(hào)。并置位指定邏輯塊
	block 對應(yīng)的邏輯塊位圖比特位。它首先取指定設(shè)備dev 的超級(jí)塊。然后對整個(gè)邏輯塊位圖
	進(jìn)行搜索，尋找首個(gè)是0 的比特位。若沒有找到，則說明盤設(shè)備空間已用完，返回0。否則
	將該比特位置為1，表示占用對應(yīng)的數(shù)據(jù)邏輯塊。并將該比特位所在緩沖塊的已修改標(biāo)志置位。
	接著計(jì)算出數(shù)據(jù)邏輯塊的盤塊號(hào)，并在高速緩沖區(qū)中申請相應(yīng)的緩沖塊，并把該緩沖塊清零。
	然后設(shè)置該緩沖塊的已更新和已修改標(biāo)志。最后釋放該緩沖塊，以便其它程序使用，并返回
	盤塊號(hào)（邏輯塊號(hào)）。		函數(shù)free_inode()用于釋放指定的i 節(jié)點(diǎn)，并復(fù)位對應(yīng)的i 節(jié)點(diǎn)位圖比特位；new_inode()
	用于為設(shè)備dev建立一個(gè)新i 節(jié)點(diǎn)。返回該新i 節(jié)點(diǎn)的指針。主要操作過程是在內(nèi)存i 節(jié)點(diǎn)表
	中獲取一個(gè)空閑i 節(jié)點(diǎn)表項(xiàng)，并從i 節(jié)點(diǎn)位圖中找一個(gè)空閑i 節(jié)點(diǎn)。這兩個(gè)函數(shù)的處理過程
	與上述兩個(gè)函數(shù)類似，因此這里就不用再贅述。
*/