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

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

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