HỆ THỐNG QUẢN LÝ TẬP TIN
III. HEÄ THOÁNG FILE EXT2 CUÛA LINUX
Ext2 (Extended File System Version 2) là một hệ thống file được các hệ điều hành Linux sử dụng phổ biến. Các hệ thống file của Linux đều dựa theo các khái niệm hệ thống file của hệ điều hành UNIX. File được quản lý bởi Inode, thư mục cũng được xem là một file chứa các entry, còn các thiết bị (devices) thì được xem như là các file đặc biệt.
1) Tổ chức đĩa: (Disk Organization)
Hệ thống Ext2 có dùng khái niệm block. Một block gồm một hay nhiều sector. Kích thước một block tùy thuộc vào kích thước của hệ thống file. Ví dụ, trên đĩa mềm 1,44MB thì kích thước một block là 2 sector (1024 bytes). Trên một partition 10 GB thì một block có kích thước bằng 4 KB (hay 8 KB) tương ứng với 8 sector (hay 16 sector).
Ngoài Boot Record, hệ thống file Ext2 được chia thành các block group.
Đĩa mềm 1,44MB chỉ là một block group duy nhất. Đĩa cứng 10 GB thì có thể chia thành 30 block group. Sơ đồ tổng quát như sau:
Trong hình vẽ, một block group lại được chia thành các thành phần:
Superblock, Group Descriptor, Block bitmap, Inode bitmap, Inode Table, Data Blocks.
a) Superblock:
Không có Superblock thì không thể dùng đĩa được vì Superblock chứa các thông tin cơ bản như: kích thước của một block (block size), tổng số block trên một Block group (blocks per group), tổng số inode trên một Block group,… Nhờ những thông tin này mà ta có thể dự đoán, tính toán các thành phần và cấu trúc trong một Block group.
Cấu trúc chi tiết của một Super block như sau:
offset size description --- --- --- 0 4 s_inodes_count 4 4 s_blocks_count 8 4 s_r_blocks_count 12 4 s_free_blocks_count 16 4 s_free_inodes_count 20 4 s_first_data_block 24 4 s_log_block_size 28 4 s_log_frag_size 32 4 s_blocks_per_group 36 4 s_frags_per_group 40 4 s_inodes_per_group 44 4 s_mtime
48 4 s_wtime 52 2 s_mnt_count 54 2 s_max_mnt_count 56 2 s_magic
58 2 s_state 60 2 s_errors
62 2 s_minor_rev_level 64 4 s_lastcheck
68 4 s_checkinterval 72 4 s_creator_os 76 4 s_rev_level 80 2 s_def_resuid 82 2 s_def_resgid
-- EXT2_DYNAMIC_REV Specific -- 84 4 s_first_ino
88 2 s_inode_size
92 4 s_feature_compat 96 4 s_feature_incompat 100 4 s_feature_ro_compat 104 16 s_uuid
120 16 s_volume_name 136 64 s_last_mounted 200 4 s_algo_bitmap -- Performance Hints -- 204 1 s_prealloc_blocks 205 1 s_prealloc_dir_blocks 206 2 - (alignment)
-- Journaling Support -- 208 16 s_journal_uuid 224 4 s_journal_inum 228 4 s_journal_dev 232 4 s_last_orphan -- Unused -- 236 788 - (padding)
Trong đó, ta sẽ chú ý đến các trường (field) quan trọng sau:
- s_inodes_count: cho biết tổng số i-node trên toàn bộ partition, bao gồm các inode đã dùng và chưa dùng.
- s_blocks_count: cho biết tổng số block trên toàn bộ partition, bao gồm các block đã dùng và chưa dùng.
- s_r_blocks_count: số block để dành cho super user.
- s_free_blocks_count: số block còn trống (gồm cả block để dành cho super user).
- s_free_inodes_count: tổng số inode còn trống.
- s_first_data_block: cho biết vị trí của super block đầu tiên (xác định bằng số thứ tự của khối).
- s_log_block_size: dùng để biết kích thứơc của một block. Kích thứơc của một block được tính như sau:
block_size = 1024 << s_log_block_size.
- s_blocks_per_group: tổng số block trên một Block group.
- s_inodes_per_group: tổng số inode trên một block group.
- s_inode_size: kích thước của một inode ( tính bằng byte).
b) Group Descriptor: Gồm các thành phần như sau:
offset size description --- --- --- 0 4 bg_block_bitmap 4 4 bg_inode_bitmap 8 4 bg_inode_table
12 2 bg_free_blocks_count 14 2 bg_free_inodes_count 16 2 bg_used_dirs_count 18 2 bg_pad
20 12 bg_reserved
Nội dung của các field như sau:
- bg_block_bitmap: Cho biết số hiệu của block bắt đầu của vùng block bitmap (trong một Block group).
- bg_inode_bitmap: Cho biết số hiệu của block bắt đầu của vùng inode bitmap (trong một Block group).
- bg_inode_table: Cho biết số hiệu của block bắt đầu của vùng inode table (trong một Block group).
- bg_free_blocks_count: Cho biết tổng số khối trống trong một Block group.
- bg_free_inodes_count: Cho biết tổng số inode trống trong một Block group.
- bg_used_dirs_count: cho biết số lượng inode đã phân bố cho các thư muùc.
- bg_pad: vùng đệm.
- bg_reserved: vùng để dành cho tương lai.
c) Block Bitmap:
Vùng này đựơc xác định vị trí bằng cách đọc nội dung của trường bg_block_bitmap trong phần Group descriptor tương ứng. Mỗi bit của vùng này cho biết được trạng thái hiện tại của một block tương ứng trong Block group chứa nó. Khi bit bằng 1 có nghĩa là block tương ứng đã được sự dụng. Khi bit bằng 0 có nghĩa là block tương ứng còn rãnh.
Block đầu tiên của Block group thì tương ứng với bít số 0 của byte 0 của vùng Block bitmap. Block thứ hai thì tương ứng với bít số 1 của byte 0. Block thứ 8 thì tương ứng với bit số 7 của byte 0. Còn bít số 0 của byte số 1 thì tương ứng với block thứ 9 trong Block group,…
d) Inode Bitmap:
Vùng Inode Bitmap được xác định vị trí bằng cách đọc nội dung của trường bg_inode_bigmap trong phần Group descriptor tương ứng. Mỗi bit trong vùng này quản lý một inode tương ứng trong vùng Inode Table. Cách tổ chức và làm việc của vùng Inode Bitmap cũng tương tự như vùng Block Bitmap.
e) Inode Table:
Vùng Inode Table là tập hợp các Inode. Khích thước mỗi Inode được xác định bởi trường s_inode_size của vùng SuperBlock. Mỗi inode lưu các thông tin cơ bản về một file mà Inode này quản lý, như: vị trí của file, kiểu của file, kích thước file, quyền truy cập… Riêng phần tên file thì không lưu tại Inode mà lưu tại thư mục. Dưới đây là hình vẽ cho biết cách truy cập tên file từ thư mục đến inode tương ứng.
f) Data Blocks:
Vùng data block gồm các block dữ liệu. Được quản lý bởi các bit tương ứng trong vùng Block bitmap. Nếu là một file bình thường thì đây là nơi lưu trữ nội dung của file, nhưng nếu file là một thư mục thì nơi đây sẽ chứa các directory-entry.
2) Caỏu truực thử muùc: (Directory Structure) a) Caỏu truực thử muùc:
Thư mục là một file đặc biệt mà nội dung của nó (chứa tại vùng Data blocks) gồm toàn các directory-entry. Các directory-entry trong Ext2 của Linux có kích thước không bằng nhau (directory-entry còn được gọi là record). Nhưng mỗi directory-entry đều có đủ 5 trường (field) như sau:
offset size description --- --- --- 0 4 inode
4 2 rec_len 6 1 name_len 7 1 file_type 8 ... name
Nội dung của các trường (field) như sau:
- inode: cho bieỏt vũ trớ cuỷa inode trong vuứng inode table, vỡ moói file tửụng ứng với một inode. Nếu field này chứa giá tri 0, có nghĩa là entry này chửa duứng.
- rec_len: kích thước tính bằng byte của một entry-directory.
- name_len: cho biết chiều dài (tính bằng byte) của tên file.
- file_type: cho biết loại file. Sẽ thuộc một trong các giá trị trong bảng sau:
EXT2_FT_UNKNOWN 0 Chửa duứng
EXT2_FT_REG_FILE 1 File bình thường
EXT2_FT_DIR 2 Thử muùc
EXT2_FT_CHRDEV 3 Thiết bị ký tự (character drvice) EXT2_FT_BLKDEV 4 Thieát bò khoái (block device)
EXT2_FT_FIFO 5 Buffer
EXT2_FT_SOCK 6 Socket
EXT2_FT_SYMLINK 7 Lieân keát (link)
EXT2_FT_MAX 8 ?
- name: tên của tập tin b) Caáu truùc Inode:
Tên file hay thư mục thì được xác định trong một directory-entry, tại directory-entry ta sẽ lấy ra được số hiệu inode tương ứng của file trên vùng inode table. Để tìm kiếm một tập tin hay thư mục, ta luôn bắt đầu tìm từ thư mục
“/” trong Linux. Mà inode số 2 trong bảng Inode Table là inode tương ứng với thư mục “/”. Tại Inode này, nhờ vào phần địa chỉ trong inode (là vùng direct block, indirect block, double indirect block, triple indirect block nhử hỡnh treõn) ta
xác định được vùng dữ liệu của thư mục “/”. Vùng dữ liệu (gồm một hay nhiều data block) này chứa các directory-entry của thư mục “/”.
Một inode có kích thước 128 byte với cấu trúc chi tiết bên trong của nó nhử sau:
offset size description --- --- --- 0 2 i_mode 2 2 i_uid 4 4 i_size 8 4 i_atime 12 4 i_ctime 16 4 i_mtime 20 4 i_dtime 24 2 i_gid
26 2 i_links_count 28 4 i_blocks 32 4 i_flags 36 4 i_osd1 40 15 x 4 i_block 100 4 i_generation 104 4 i_file_acl 108 4 i_dir_acl 112 4 i_faddr 116 12 i_osd2
Trong đó, ta chú ý đến một số trường (field) quan trọng sau:
- i_mode: cho biết loại file và quyền truy cập và các thuộc tính khác của file. Thông tin thêm về phần này được trình bày ở bảng “LOẠI FILE và CÁC QUYỀN TRUY CẬP” ở phía dưới đây.
- i_uid: số ID của user là chủ của file này.
- i_size: kích thước của file tính bằng byte.
- i_atime: thời gian của lần cuối mà file được truy cập (access).
- i_ctime: thời gian lúc file được tạo ra.
- i_mtime: thời gian của lần cuối mà file được hiệu chỉnh (modify).
- i_gid: số ID của nhóm là chủ của file này.
- i_links_count: số lượng liên kết đến file.
- i_blocks: tổng số block dành cho file (kể cả còn trống).
- 15 x 4 i_block: gồm 15 địa chỉ chỉ đến các khối dữ liệu của file trên vùng data blocks. Trong đó, 12 địa chỉ đầu chỉ trực tiếp đến các khối trên vùng data blocks. Địa chỉ thứ 13 gọi là địa chỉ gián tiếp (indirect block), mỗi địa chỉ sẽ chỉ đến một khối gồm toàn các địa chỉ trực tiếp trên vùng data blocks. Địa chỉ thứ 14 là địa chỉ gián tiếp 2 cấp (double- indirect block). Địa chỉ thứ 15 là địa chỉ gián tiếp 3 cấp (triple- indirectory block).
Bảng: LOẠI FILE và CÁC QUYỀN TRUY CẬP -- file format --
EXT2_S_IFMT 0xF000 format mask
EXT2_S_IFSOCK 0xC000 socket
EXT2_S_IFLNK 0xA000 symbolic link
EXT2_S_IFREG 0x8000 regular file
EXT2_S_IFBLK 0x6000 block device
EXT2_S_IFDIR 0x4000 directory
EXT2_S_IFCHR 0x2000 character device
EXT2_S_IFIFO 0x1000 fifo
-- access rights --
EXT2_S_ISUID 0x0800 SUID
EXT2_S_ISGID 0x0400 SGID
EXT2_S_ISVTX 0x0200 sticky bit
EXT2_S_IRWXU 0x01C0 user access rights mask
EXT2_S_IRUSR 0x0100 read
EXT2_S_IWUSR 0x0080 write
EXT2_S_IXUSR 0x0040 execute
EXT2_S_IRWXG 0x0038 group access rights mask
EXT2_S_IRGRP 0x0020 read
EXT2_S_IWGRP 0x0010 write
EXT2_S_IXGRP 0x0008 execute
EXT2_S_IRWXO 0x0007 others access rights mask
EXT2_S_IROTH 0x0004 read
EXT2_S_IWOTH 0x0002 write
EXT2_S_IXOTH 0x0001 execute
IV. HEÄ THOÁNG FILE FAT: (File Allocation Table)
Mô hình hình này được hệ điều hành DOS và Windows sử dụng.
BS FAT 1 FAT 2 RD 0 1 2 3 4 5 … n
Vuứng DATA
BS: Boot Sector.
RD: Root Directory.
Vùng RD: được phân nhỏ thành các entry, được tổ chức như vùng DET.
Mỗi entry có vai trò là một ô như vùng DET.
Vùng FAT: FAT 2 là bản dự phòng của FAT 1. FAT được phân nhỏ thành các ô (entry). Mỗi entry quản lý cho một block như trình bày ở phần Status- block. Kích thước mỗi entry của FAT có thể là 12 bits (FAT12), 16 bits (FAT16) hay 32 bits (FAT32).
Vùng DATA: là nơi thực sự chứa nội dung của các tập tin.
ÁP DỤNG CHO ĐĨA MỀM 1,44MB 3,5 inches:
Caỏu truực logic cuỷa ủúa meàm 1,44MB 3,5 inches
1) Boot sector:
Chiếm một sector đầu tiên (sector 1, track 0, side 0).
Boot sector có chứa một chương trình ngắn để khởi động quá trình nạp hệ điều hành từ đĩa mềm vào bộ nhớ trong.
Tất cả các đĩa mềm đều có boot sector, dù chúng có chứa hay không chứa hệ điều hành.
Ngoài chương trình này, boot sector còn chứa các nội dung khác cho biết các thông tin về đĩa như:
Soá bytes/sector.
Soá sectors/cluster.
Số lượng bảng FAT.
Soỏ entry toỏi ủa trong thử muùc goỏc.
Toồng soỏ sector treõn ủúa.
Số sector của một bảng FAT.
vaân … vaân …
2) Vuứng root directory (thử muùc goỏc):
Offset Tên trường (field) Kích thước (bytes)
0 Tên tập tin 8
8 Tên mở rộng 3
11 Thuộc tính 1
12 Phần để dành 10
22 Thời gian tạo 2
24 Ngày tạo 2
26 Fat-entry đầu tiên 2
28 Kích thước tập tin 4
cấu trúc một root-dir-entry
Có kích thước 14 sectors (bắt đầu từ sector số 19 đến sector số 32).
Được chia nhỏ thành các root-dir-entry. Mỗi entry này có kích thước bằng 32 bytes.
Mỗi tập tin hay thư mục con thuộc thư mục gốc sẽ được quản lý bởi một entry treõn vuứng root dir.
Tổng số entry là: (14 x 512) / 32 = 224 entries.
Một entry mô tả các thông tin cho một tập tin hay một thư mục con mà nó quản lý như bảng trên (bảng cấu trúc một root-dir-entry).
3) Vuứng Fat:
Có 2 bảng FAT là FAT 1 và FAT 2. Bảng FAT 2 là dự phòng cho bảng FAT 1. Mỗi bảng FAT có kích thước 9 sectors. FAT 1 bắt đầu từ sector số 1 đến số 9, FAT 2 từ sector số 10 đến số 18.
Nội dung của một tập tin hay thư mục con được lưu trữ thật sự trên vùng DATA. Vùng DATA gồm các khối, mỗi khối có kích thước một sector. Tập tin được lưu trữ trên một hay nhiều khối thuộc vùng DATA.
Bảng FAT được chia nhỏ thành các fat-entry. Mỗi fat-entry quản lý một khối duy nhất duy nhất trên vùng DATA. Mỗi fat-entry mang một trong các giá trị sau:
- 000 hex: khối tương ứng trên vùng data là khối trống, chưa được duứng.
- FF7: khoỏi bũ hử (bad).
- FFF: khối cuối cùng của một tập tin hay thư mục con.
- Các giá trị khác: khối đang thuộc một tập tin hay thư mục con.
Kích thước một fat-entry là 12 bits nên gọi FAT này là FAT12. Hai entry đầu tiên không dùng vào việc quản lý khối trên vùng DATA. Ngoài FAT12, có một số hệ thống file FAT khác là FAT16, FAT32.
Do fat-entry số 0 và fat-entry số 1 không tham gia quản lý, nên fat-entry số 2 quản lý khối số 33 trên vùng DATA.
Tổng quát: fat-entry số i quản lý khối số 31+i trên vùng DATA.
4) Cách thức lưu trữ và quản lý một tập tin (hay thư mục):
Tập tin (thư mục) được lưu trữ trên các khối rời rạc, không nhất thiết liền nhau trên vùng DATA. Các khối của tập tin được tổ chức theo dạng danh sách lieân keát.
-Các fat entry của một tập tin sẽ được tổ chức như thế nào?
+ Đầu xâu: fat entry đầu tiên sẽ được truy cập từ rootdir entry.
+ Liên kết: Nội dung của entry trước sẽ chứa số hiệu của entry kế tiếp.
+ Cuối xâu: entry cuối cùng chứa giá trị FFF hexa.
5) Giải mã nội dung của một Fat-entry 12 bits:
a)FAT16 và FAT12:
FAT16 dùng 2 bytes cho một entry.
2 bytes X 8 bits = 16 bits nên gọi là FAT16.
FAT12 dùng 3 bytes cho 2 entries. Suy ra 1 entry có kích thước là 12 bits nên gọi là FAT12.
Ghi chú:
Hai entries đầu không dùng vào việc quản lý các khối trên vùng DATA.
Bắt đầu từ entry số 2 dùng cho việc quản lý.
b) Giài mã nội dung của một FAT12 entry:
Nhắc lại vấn đề byte thấp byte cao lưu trong bộ nhớ:
giá trị của 1 word = byte cao x 256 + byte thấp Cấp phát một vùng nhớ chứa đủ toàn bộ 9 sectors của vùng FAT1:
unsigned char FatBuffer[512*9];
Đọc FAT1 vào FatBuffer:
absread(0,9,1,FatBuffer);
gọi k là số hiệu của fat entry đang xét, k có thể chẵn hoặc lẻ.
gọi pos và pos+1 là vị trí 2 byte tương ứng với entry k trong vùng nhớ FatBuffer.Thì pos = (3*k/2).
Trường hợp k chẵn:
Phải lấy ra được phần C8 và C4 rồi sắp xếp lại vị trí của C8 và C4 sao cho lấy ra được giá trị của entry k.
Dùng 2 biến 2 bytes như sau:
int bytethap = FatBuffer[pos];
int bytecao = FatBuffer[pos+1];
Trường hợp k lẻ:
Phải lấy ra được phần L8 và L4 rồi sắp xếp lại vị trí của L8 và L4 sao cho lấy ra được giá trị của entry k.
Dùng 2 biến 2 bytes như sau:
int bytethap = FatBuffer[pos];
int bytecao = FatBuffer[pos+1];
Hàm giải mã một FAT12 entry:
int GetValueFat( int k ) {
int pos = (k*3)/2;
int bytecao = FatBuffer[pos+1];
int bytethap = FatBuffer[pos];
if(k%2 == 0)
return (bytethap | ((bytecao & 0xF)<<8));
else
return ((bytecao<<4)|(bytethap>>4));
}