Tiểu luận Cấu trúc hệ thống file ext2, ext3, ext4 trong họ linux

neration 104 4 i_file_acl 108 4 i_dir_acl 112 4 i_faddr 116 12 i_osd2 Một số entry đầu tiên của bảng inode được dự trữ. Trong EXT2_GOOD_OLD_REV có 11 entry dự trữ trong khi ở EXT2_DYNAMIC_REV mới hơn số entry của inode được dự trữ được chỉ rõ trong s_first_ino của cấu trúc superblock. Sau đây là danh sách của các entry inode dữ trữ được biết đến nhiều nhất: Table 1-4. Bảng giá trị EXT2_*_INO EXT2_BAD_INO 0x01 bad blocks inode EXT2_ROOT_INO 0x02 root directory inode EXT2_ACL_IDX_INO 0x03 ACL index inode EXT2_ACL_DATA_INO 0x04 ACL data inode EXT2_BOOT_LOADER_INO 0x05 boot loader inode EXT2_UNDEL_DIR_INO 0x06 undelete directory inode i_mode Giá trị 16 bit này được dùng để cho biết định dạng của tập tin được mô tả và lượt truy xuất. Sau đây là các giá trị có thể có: Table 1-5. Các giá trị của EXT2_S_I -- 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 i_uid Giá trị 16 bit cho biết số thứ tự người dùng tương ứng với tập tin. i_size Giá trị 32 bit cho biết kích thước của tập tin (tính bằng byte). _atime Giá trị 32 bit diễn tả số giây kể từ ngày 1/1/1970 đến thời gian truy xuất tập tin gần đây nhất. i_ctime Giá trị 32 bit diễn tả số giây kể từ ngày 1/1/1970 cho đến khi tập tin được tạo. i_mtime Giá trị 32 bit diễn tả thời gian kể từ ngày 1/1/1970 cho đến lần bổ sung gần đây nhất vào tập tin. i_dtime Giá trị 32 bit diễn tả thời gian kể từ ngày 1/1/1970 cho đến khi xóa tập tin. Thật là quan trọng nếu tập tin không được xóa thì giá trị này luôn là 0. i_gid Giá trị 16 bit cho biết số thứ tự của group đang truy xuất tập tin. i_links_count Giá trị 16 bit cho biết inode đặc biệt này được liên kết đến bao nhiêu lần. i_blocks Giá trị 32 bit cho biết số lượng các block được dự trữ cho dữ liệu tập tin tương ứng. nó bao gồm cả các block đã dùng và block dự trữ trong trường hợp tập tin tăng kích thước. Một điểm quan trọng cần lưu ý là giá trị này cho biết số block 512 byte và không xác định kích thước của số block được xác định trong superblock. Vì vậy nếu một tập tin chỉ dùng một block của hệ thống tập tin và kích thước là 1024 byte, giá trị i_blocks của nó sẽ là 2. i_flags Giá trị 32 bit cho biết việc thực thi Ext2 như thế nào khi truy xuất dữ liệu cho inode này. (Xem thêm ở mục Behaviour flags) i_osd1 Giá trị 32 bit cho biết giá trị của hệ điều hành đang phụ thuộc. Hurd Giá trị 32 bit đánh dấu như “máy dịch” (translator). Linux Giá trị 32 bit cho biết giá trị dự trữ hiện hành. Masix Giá trị 32 bit cho biết giá trị dự trữ hiện hành. i_block Dãy được dùng để định vị các block của các tập tin đặc biệt được lưu trữ trên đó. Mỗi entry là số block 32 bit. 12 entry đầu tiên trong dãy này là số các block, có thể dùng để tìm nạp 12 block đầu tiên tương ứng với tập tin. Entry thứ 13 là một số block gián trực tiếp, có nghĩa là tại block dữ liệu cụ thể, bạn sẽ tìm thấy một dãy số các block trực tiếp. Entry thứ 14 là một số block gián tiếp hai lần. Điều này có nghĩa là tại block dữ liệu cụ thể, bạn sẽ tìm thấy một dãy số block gián tiếp, cái mà chứa một dãy số block có thẻ được truy xuất một cách trực tiếp. Entry thứ 15 là một số block gián tiếp ba lần. Nó là một số block chứa một dãy số block gián tiếp hai lần, v.v… Mỗi dãy block gián tiếp/gián tiếp hai lần/ gián tiếp ba lần chứa nhiều entry của số block 32 bit nếu có thể (để lấp đầy toàn bộ block). i_generation Giá trị 32 bit được dùng để xác định phiên bản của tập tin (được dùng bởi NFS). i_file_acl Giá trị 32 bit cho biết số block chứa các thuộc tính mở rộng. Trong các lần duyệt trước giá trị này luôn luôn là 0. Sự miêu tả tổng quát của ACL cho Digital UNIX có thể được tìm thấy tại địa chỉ này: i_dir_acl Giá trị 32 bit được dùng để xác định kích thước cao (high size) của tập tin. Trong lần duyệt trước giá trị này luôn là 0. i_faddr Giá trị 32 bit xác định vị trí của đoạn tập tin (file fragment) gần đây nhất. i_osd2 Giá trị 96 bit cho biết cấu trúc của hệ điều hành đang phụ thuộc. Hurd offset size description ------- ------- ----------- 0 1 h_i_frag 1 1 h_i_fsize 2 2 h_i_mode_high 4 2 h_i_uid_high 6 2 h_i_gid_high 8 4 h_i_author h_i_frag Giá trị 8 bit cho biết số fragment. h_i_fsize Giá trị 8 bit cho biết kích thước của fragment. h_i_uid_high Giá trị 16 bit cao của user_id. h_i_gid_high Giá trị 16 bit cao của group_id. Linux offset size description ------- ------- ----------- 0 1 l_i_frag 1 1 l_i_fsize 2 2 reserved 4 2 l_i_uid_high 6 2 l_i_gid_high 8 4 reserved l_i_frag Giá trị 8 bit cho biết số fragment. l_i_fsize Giá trị 8 bit cho biết kích thước fragment. l_i_uid_high Giá trị 16 bit cao của user_id.. l_i_gid_high: Giá trị 16 bit cao của group_id. Masix offset size description ------- ------- ----------- 0 1 m_i_frag 1 1 m_i_fsize 2 10 reserved m_i_frag: Giá trị 8 bit cho biết số fragment. m_i_fsize: Giá trị 8 bit cho biết kích thước fragment. 2.2.2.6 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 tập tin bình thường thì đây là nơi lưu trữ nội dung của tập tin, nhưng nếu tập tin là thư mục thì nơi đây sẽ chứa các directory-entry. 2.2.3 Cấu trúc thư mụ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. Thư mục được lưu trữ giống như tập tin và có thể được nhận ra bằng việc tìm trong các bit dịnh dạng tập tin ext2_inode.i_mode đối với giá trị EXT2_S_IFDIR. Thư mục gốc luôn là entry thứ hai của bảng inode (EXT2_ROOT_INO có giá trị là 2). Bất kỳ thư mục con nào từ thư mục gốc có thể được định vị bằng việc quan sát nội dung của tập tin thư mục gốc. 2.2.3.1. Định dạng Directory File 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) sau: Figure 2-1. directory-entry offset size description ------- ------- ----------- 0 4 inode 4 2 rec_len 6 1 name_len 7 1 file_type 8 ... name Sự bổ sung trước đây của Ext2 sử dụng 16 bit cho trường name_len, nhưng từ lúc giá trị này được lưu trữ trong thứ tự byte của Intel và hầu hết sự bổ sung giới hạn tên tập tin dài nhất là 255 ký tự, cho phép một byte được phục hồi. inode Giá trị 32 bit cho biết số inode của file-entry. Entry không được dùng thì giá trị này là 0. rec_len Giá trị 16 bit không dấu cho biết sự thay thế directory-entry kế tiếp bắt đầu từ directory-entry hiện hành. name_len Giá trị 8 bit không dấu cho biết tên chứa bao nhiêu ký tự. file_type Giá trị 8 bit không dấu dùng để xác định kiểu tập tin. Lưu ý, giá trị này có thể là 0 trong sự bổ sung trước đó. Giá trị được xác định hiện tại là: Table 2-1. Bảng giá trị của EXT2_FT EXT2_FT_UNKNOWN 0  Chưa dùng EXT2_FT_REG_FILE 1  File bình thường EXT2_FT_DIR 2  Thư mục EXT2_FT_CHRDEV 3  Thiết bị ký tự EXT2_FT_BLKDEV 4  Thiết bị khối EXT2_FT_FIFO 5  Buffer EXT2_FT_SOCK 6  Socker EXT2_FT_SYMLINK 7  Liên kết EXT2_FT_MAX 8 name Tên của file-entry. Các ký tự cho phép thuộc ISO-Latin-1. 2.2.3.2 Ví dụ về Directory Sau đây là một ví dụ về một thư mục của một user trên hệ thống của tôi. $ ls -1a /home/eks . .. .bash_profile .bashrc mbox public_html tmp Sự miêu tả dữ liệu sau có thể được tìm thấy trên thiết bị lưu trữ: Figure 2-2. Sự bố trí dữ liệu trong thư mục ví dụ offset size description ------- ------- ----------- 0 4 inode number (783362) 4 2 record length (9) 6 1 name length (1) 7 1 file type (EXT2_FT_DIR) 8 1 name (.) 9 4 inode number (1109761) 13 2 record length (10) 15 1 name length (2) 16 1 file type (EXT2_FT_DIR) 17 2 name (..) 19 4 inode number (783364) 23 2 record length (21) 25 1 name length (13) 26 1 file type (EXT2_FT_REG_FILE) 27 13 name (.bash_profile) 40 4 inode number (783363) 44 2 record length (15) 46 1 name length (7) 47 1 file type (EXT2_FT_REG_FILE) 48 7 name (.bashrc) 55 4 inode number (783377) 59 2 record length (12) 61 1 name length (4) 62 1 file type (EXT2_FT_REG_FILE) 63 4 name (mbox) 67 4 inode number (783545) 71 2 record length (19) 73 1 name length (11) 74 1 file type (EXT2_FT_DIR) 75 11 name (public_html) 86 4 inode number (669354) 90 2 record length (11) 92 1 name length (3) 93 1 file type (EXT2_FT_DIR) 94 3 name (tmp) 97 4 inode number (0) 101 2 record length (3999) 103 1 name length (0) 104 1 file type (EXT2_FT_UNKNOWN) 105 0 name () Cần lưu ý rằng một vài sự bổ sung sẽ đệm thêm các directory-entry để có những hiệu quả tốt hơn trong việc xử lý chính, vì vậy rất quan trọng khi sử dụng record length và không sử dụng name length để tìm record tiếp theo. 2.2.3.4 Indexed Directory Format Việc dùng chuẩn liên kết danh sách định dạng thư mục có thể trở nên chậm khi mà số lượng tập tin bắt đầu tăng. Để tăng hiệu quả cho một hệ thống như vậy, một mảng băm được tạo ra cho phép nhanh chóng định vị tập tin cụ thể được tìm kiếm. Bit EXT2_INDEX_FL trong cờ hiệu điều khiển thao tác (behaviour control flags) được thiết lập nếu indexed directory format được sử dụng. Cấu trúc Index Gốc của cây Index nằm ở block 0 của tập tin. Khoảng trống được dữ trữ cho cấp độ 2 của cây index trong block 1 đến 511 (block hệ thống tập tin 4KB). Block thư mục lá đươc gắn vào bắt đầu tại block 512, vì vậy đoạn cuối của thư mục trông giống như một thư mục Ext2 thông thường và có thể được xử lý một cách trực tiếp bởi trường ext2_readdir. Đối với các thư mục ít hơn 90KB có lỗ chạy từ block 1 đến 511, vì vậy một thư mục rỗng có hai block trong nó, mặc dù kích thước của nó xuất hiện khoảng 2MB trong một danh sách thư mục. Một thư mục trông như sau: 0: Root index block 1: Index block/0 2: Index block/0 ... 511: Index block/0 512: Dirent block 513: Dirent block ... Mỗi index block bao gồm 512 index entry: hash, block trong đó hash là một hash 32 bit với một cờ hiệu xung đột trong bit có ý nghĩa ít nhất của nó, và block là số block luận lý của một index của block lá, phụ thuộc vào cấp độ của cây. Giá trị hash của index entry 0 không cần thiết bởi vì cấp độ của cây sẽ tạo ra nó, do đó nó được dùng để ghi việc tính các index entry trong một index block. Block index gốc có định dạng giống như các block index khác, với 8 byte đầu tiên của nó dữ trữ một tiêu đề nhỏ: 1 byte header length (default: 8) 1 byte index type (default: 0) 1 byte hash version (default:0) 1 byte tree depth (default: 1) Cách xử lý của header khác với bản đắp vá kèm theo một cách không đáng kể. Nói riêng, chỉ một cấp độ đơn của cây index (root) được bổ sung ở đây. Điều này trở nên đủ để điều khiển nhiều hơn 90,000 entry, vì vậy hiện nay nó cũng đủ. Khi một cấp độ 2 được thêm vào cây, khả năng này sẽ tăng lên đến khoảng 50 triệu entry, và không có gì ngăn ngừa việc dùng cấp độ thứ n. Thuật toán tìm kiếm (Lookup Algorithm) - Tính toán một hash của tên - Đọc index gốc - Dùng tìm kiếm nhị phân để tìm index đầu tiên hoặc block lá có thể chứa hash đích (trong trật tự cây) - Lập lại bước trên cho đến khi đạt được cấp độ thấp nhất của cây. - Đọc block entry của thư mục lá và thực hiện tìm kiếm Ext2 thông thường trên nó. - Nếu tên được tìm thấy, trả về buffer và directory-entry của nó. - Ngược lại, nếu bit xung đột của directory-entry tiếp theo được thiết lập, tiếp tục tìm kiếm trên block đã thành công. Thuật toán chèn (Insert Algorithm) Chèn vào các entry mới vào trong thư mục phức tạp hơn là tìm kiếm, vì cần phải tách các block lá khi chúng đầy, và thỏa mãm điều kiện là cho phép những xung đột khóa hash được điều khiển một cách chắc chắn và có hiệu quả. Tôi xin tóm tắt như sau: - Dò index như là tìm kiếm. - Nếu block lá đích đầy, chia nhỏ nó và ghi nhớ block sẽ nhận entry mới. - Chèn thêm entry mới trong block lá sử dụng mã chèn directiry-entry Ext2 thông thường. Tách (Splitting) Tóm lại, khi một nút lá đầy và chúng ta muốn đặt một entry mới vào đó thì lá sẽ bị tách ra, và một phần khoảng trống hash của nó được chia thành nhiều phần. Cách dễ nhất để làm được điều này là sắp xếp các entry theo giá trị hash và cắt ở phần giữa của danh sách đã được sắp xếp. Thao tác này là log(number_of_entries_in_leaf) và không mất nhiều chi phí với điều kiện sử dụng thuật toán sắp xếp có hiệu quả. Tôi dùng CombSort cho việc này, mặc dù QuickSort cũng tốt cho trường hợp này bởi vì sự thực thi trường hợp trung bình quan trọng hơn trường hợp tệ nhất. Một phương pháp khác là dự đoán một giá trị trung bình cho khóa hash, và việc chia phần có thể được làm theo thời gian tuyến tình, nhưng kết quả việc phân chia kém hơn khoảng trống khóa hash có giá trị hơn thuận lợi ít ỏi của thuật toán phân chia tuyến tính. Trong trường hợp bất kỳ, số entry cần sắp xếp được giới hạn bởi số lượng vừa khít trong một lá. Các xung đột khóa (Key Collisions) Việc điều khiển những chuỗi xung đột khóa hash có một vài phức tạp. Thật là tuyệt nếu tránh việc tách các chuỗi như vậy giữa các block, vì vậy điểm cắt của một block được điều chỉnh với cái này. Nhưng khả năng vẫn còn nếu block lắp đầy bởi các entry được băm một cách xác định, chuỗi có thể vẫn phải bị tách. Tình huống này được đánh dấu bằng cách đặt một số 1 vào bit bên dưới của entry index trỏ vào block kế thừa, cái mà được làm sáng tỏ một cách tự nhiên bởi sự thăm dò index như là một giá trị trung gian mà không có bất kỳ sự mã hóa đặc biệt nào. Vì vậy, việc điều khiển vấn đề xung đột bắt buộc không có xử lý thực sự, chỉ có mã mở rộng và và sự giảm bớt không đáng kể khoảng trống của khóa băm. Khoảng trống của khóa băm vẫn còn đủ cho số directory-entry có thể tưởng tượng được, lên đến hàng tỷ. Hàm băm (Hash Function) Các đặc tính chính xác của hàm Hash rất ảnh hưởng đến việc thực thi chiến lược index này. Một hàm hash dở sẽ dẫn đến nhiều sự xung đột hoặc sự phân chia khoảng trống hash dở. Để minh họa tại sao cái sau lại là một vấn đề, xét xem cái gì sẽ xảy ra khi một block được tách ra để mà nó bao phủ một vài giá trị hash nhất định. Xác suất các entry index sau đó cũng được băm tương tự, khoảng cách càng nhỏ thì giá trị này càng nhỏ. Thực tế, khi một block được tách ra, nếu khoảng trống hash của nó quá nhỏ đến nỗi chỉ luôn đầy có một nửa, đó là một kết quả mà tôi quan sát ở thực tế. Sau một số thử nghiệm, tôi đã có một hàm Hash cho ra một sự phân tán hợp lý các khóa hash dọc theo toàn bộ khoảng trống khóa 31 bit. Điều này làm tăng sự đầy trung bình của các block lá, đạt gần tới giá trị trung bình theo lý thuyết là đầy ¾. Nhưng hàm hash hiện tại chỉ để dùng tạm, chờ một phiên bản tốt hơn dựa trên lý thuyết chắc chắn. Sự thực thi (Performance) Tóm lại, sự cải tiến khả năng thực thi trên Ext2 thông thường đã gây một sự bất ngờ. Với việc thực thi các thư mục rất nhỏ giống với Ext2 chuẩn, nhưng vì kích thước thư mục tăng theo Ext2 chuẩn một cách nhanh chóng làm xuất hiện bậc hai, trong khi htree-enhanced Ext2 tiếp tục lấy tỉ lệ một cách tuyến tính. Uli Luckas chạy điểm chuẩn cho việc tạo tập tin theo các kích thước khác nhau của thư mục nằm trong dãy từ 10,000 đến 90,000 tập tin. Kết quả này rất hài lòng: toàn bộ thời gian tạo file gần như tuyến tính, chống lại việc tăng bậc hai của Ext2 thường. Thời gian được tạo như sau: Figure 2-3. Việc thực thi Indexed Directories Indexed Normal ======= ====== 10000 Files: 0m1.350s 0m23.670s 20000 Files: 0m2.720s 1m20.470s 30000 Files: 0m4.330s 3m9.320s 40000 Files: 0m5.890s 5m48.750s 50000 Files: 0m7.040s 9m31.270s 60000 Files: 0m8.610s 13m52.250s 70000 Files: 0m9.980s 19m24.070s 80000 Files: 0m12.060s 25m36.730s 90000 Files: 0m13.400s 33m18.550s Các thư mục dễ dàng vừa khít bộ nhớ đệm, và thừa số giới hạn trong trường hợp Ext2 chuẩn là việc tìm các block directory trong bộ nhớ đệm buffer, và việc quét cấp độ thấp các entry directory. Trong trường hợp lập chỉ mục htree, thì số chi phí cần được xem xét, tất cả chúng hầu như được giới hạn. Có một vài cách tối ưu cần phải thực hiện: - Dùng tìm kiếm bằng nhị phân thay vì tìm kiếm tuyến tính trong các nút chỉ thị ở phía trong. - Nếu chỉ có một block lá trong một thư mục, thì bỏ qua việc dò chỉ mục, đi thẳng đến block luôn. - Ánh xạ thư mục vào trang cache thay vì vào cache bộ nhớ đệm trung gian. Mỗi sự tối ưu này sẽ tạo ra một hiệu quả được cải thiện, nhưng không có gì giống như bước nhảy lớn từ N*2 đến Log512(N), ~=N. Trong lúc những tối ưu đó được áp dụng và chúng ta có thể tìm thấy một hiệu quả gấp đôi khác hay tương tự như vậy. Đó là một hiệu quả không đáng kể khi mà thư mục đủ lớn để cần một level cấp 2 vì bộ lưu trữ sẽ rất nhỏ. Việc đi ngang qua các block dữ liệu của thư mục sẽ là một chi phí rất lớn, và một lần nữa, giá trị này có thể tăng lên bởi việc di chuyển các block vào trang cache. Điển hình chúng ta sẽ đi qua 3 block để đọc hay viết một entry thư mục, và số đó tăng đến khoảng 4-5 với những thư mục lớn. Nhưng thực sự thì không có gì so sánh với Ext2 thông thường cái mà đi qua vài trăm block trong tình huống tương tự. 2.2.4 Inodes, File Identifiers Mỗi tập tin, thư mục, tập tin liên kết, thiết bị, hoặc bất cứ cái gì khác đều được lưu trữ trong hệ thống tập tin Ext2, được xác định bởi một inode. Nếu bạn biết số inode của tập tin bạn muốn đọc, thậm chí là không biết đường dẫn đến file đó hay tên file đó, bạn vẫn có thể xác định vị trí file đó trên đĩa và đọc nó. 2.2.4.1 Inode Number Số inode (inode number) là một chỉ mục trong bảng inode (inode table) đến một cấu trúc inode (inode structure). Kích thước của inode table cố định trong thời gian định dạng, nó được tạo ra để giữ số entry lớn nhất. Vì dự trữ khối lượng đủ lớn các entry, bảng inode khá lớn và do đó, nó bị tách theo tỉ lệ bằng nhau giữa tất cả các block group. 2.4.2 Định vị cấu trúc của Inode Trường s_inodes_per_group trong cấu trúc superblock cho chúng ta biết có bao nhiêu inode trên một block broup. Inode 1 là inode đầu tiên xác định trong bảng inodek, có thể dùng những công thức sau: group = (inode - 1) / s_inodes_per_group để định vị block group nào nắm giữ một phần bảng inode chứa entry inode được tìm kiếm, và: index = (inode - 1) % s_inodes_per_group để có được chỉ mục của một phần bảng inode này với entry inode được tìm kiếm. Sau đây là hai ví dụ được dùng để kiểm tra sự thực thi của bạn: Figure 3-1. Ví dụ về sự tính toán inode s_inodes_per_group = 1712 inode number computation ------------ ----------- 1 group = (1 - 1) / 1712 = 0 index = (1 - 1) % 1712 = 0 2 group = (2 - 1) / 1712 = 0 index = (2 - 1) % 1712 = 1 963 group = (963 - 1) / 1712 = 0 index = (963 - 1) % 1712 = 962 1712 group = (1712 - 1) / 1712 = 0 index = (1712 - 1) % 1712 = 1711 1713 group = (1713 - 1) / 1712 = 1 index = (1713 - 1) % 1712 = 0 3424 group = (3424 - 1) / 1712 = 1 index = (3424 - 1) % 1712 = 1711 3425 group = (3425 - 1) / 1712 = 2 index = (3425 - 1) % 1712 = 0 Chỉ mục 0 (index = 0) là entry đầu tiên. Kết quả hơn 1 là cái có thể dễ dàng được tăng lên nhiều lần bởi kích thước của cấu trúc để tìm kiếm offset cuối cùng trong đường dẫn của nó trong bộ nhớ hoặc trên đĩa. 2.2.4.3 Định vị Inode Table Như được giới thiệu trong phần 3.1, bảng inode được tách bằng nhau giữa tất cả block group. Nếu một hệ thống tập tin được tạo cho phép một ngàn inode, cắt giữa 5 group, có 200 inode trên một phần của bảng inode. Figure 3-1 minh họa sự phân phối tương tự như thế. Mỗi phần của bảng inode có thể được định vị bằng việc dùng trường bg_inode_table của cấu trúc group_descriptor của các block group tương ứng.\ 2.2.5 Các Thuộc Tính Của File Hầu hết các thuộc tính của file (cũng như directory, symbol link, thiết bị…) được định vị trong inode tương thích với tập tin. Một vài thuộc tính khác chỉ có ở các thuộc tính mở rộng. 2.2.5.1 Các thuộc tính chuẩn SUID, SGID và -rwxrwxrwx Chúng được định vị với các bit SGID và SUID trong ext2_inode.i_mode. Kích thước File Kích thước của file có thể được xác định tại trường ext2_inode.i_size. Owner và Group Dưới hầu hết sự bổ sung, owner và group là các giá trị 16 bit, nhưng trong một vài sự bổ sung của Linux và Hurd gần đây thì id của owner và group là 32 bit. Khi sử dụng các giá trị 16 bit, chỉ có những phần “thấp” (low) được dùng hợp lệ, trong khi sử dụng giá trị 32 bit, cả hai phần cao và thấp đều được dùng, phần cao được đẩy sang trái tới 16 khoảng cách sau đó thêm vào phần thấp. Chỉ phần thấp của owner và group được định vị tương ứng trong ext2_inode.i_uid và ext2_inode.i_gid. Phần thấp của owner và group được định vị trong ext2_inode.osd.hurd.h_i_gid_high và ext2_inode.osd2.hurd.h_i_uid_high một cách tương ứng đối với Hurd, và định vị tương ứng trong các trường ext2_inode.osd2.linux.l_i_uid_high và ext2.osd2.linux.l_gid_high đối với Linux. 2.2.5.2 Các thuộc tính mở rộng Các thuộc tính mở rộng cặp name:valua kết hợp cố định giữa các file và directory, tương tự như chuỗi môi trường kết hợp với một tiến trình (process). Một thuộc tính có thể được xác định hoặc không xác định. Nếu được xác định, giá trị của nó có thể rỗng hoặc không rỗng. Các thuộc tính mở rộng là sự mở rộng các thuộc tính thông thường cái mà được kết hợp tất cả các inode trong hệ thống. Chúng thường được dùng để cung cấp thêm các chức năng vào một hệ thống – chẳng hạn như thêm vào các đặc tính bảo mật như là Access Control Lists (ACLs) có thể được bổ sung bằng cách dùng các thuộc tính mở rộng. Các thuộc tính mở rộng được truy xuất như các đối tượng nguyên tử. Việc đọc gọi ra tất cả giá trị của một thuộc tính và lưu trữ nó trong bộ nhớ trung gian. Việc ghi thay đổi giá trị phía trước bất kỳ bằng giá trị mới. Trong mỗi inode ext2, chúng ta có trường i_file_acl, dành cho Access Control Lists. Trường này được dùng để lưu trữ số block thay vì lưu trữ các thuộc tính mở rộng của một inode. Các thuộc tính mở rộng lưu trữ trên block đĩa “trống” (plain) không có phần bất kỳ file nào. Sự bố trí block trên đĩa giống như việc bố trí dành cho các thư mục. Sau header của thuộc tính block là header của entry. Kích thước của các header entry khác với chiều dài của tên thuộc tính. Các giá trị thuộc tính trên block giống như thuộc tính entry descriptor của chúng, sắp thẳng hàng đến cuối thuộc block thuộc tính. Điều này cho phép việc thêm vào các thuộc tính được dễ dàng hơn. Danh sách tên thuộc tính gắn với một file có thể được gọi ra. Bộ điều khiển hệ thống tập tin trả về một chuỗi tên cách nhau bởi các ký tự null, kết thúc bằng hai ký tự null tại phần cuối của danh sách. 2.2.6 Quản trị hệ thống file EXT2 Filesystem caching : Nhằm tăng hiệu suất của toàn hệ thống file ext2, cache được dùng để lưu giữ các dữ liệu được dùng thường xuyên. Thông tin của filesystem được cache trong bộ nhớ, đôi khi được tham khảo tới như là một bộ đệm đĩa, bởi vì việc truy cập vào bộ nhớ thì nhanh hơn nhiều so với các đĩa vật lý. Cả hai quá trình đọc và ghi đều được cache dữ liệu trên RAM. Hệ thống buffers đĩa càng lớn thì filesystem đáp ứng càng nhanh cho các thao tác đọc ghi. Do RAM là bộ nhớ tạm thời, buffer sẽ được ghi vào đĩa khi máy hoạt động, hay khi filesystem được unmount. Lệnh sync có thể dùng để ép kernel ghi tất cả các buffers vào các file trên đĩa. Lệnh này có thể sử dụng không cần tham số. Ví dụ: Với lý do này có thể giải thích vì sao khi chép file vào đĩa mềm ta thấy hệ thống chạy rất nhanh tuy nhiên lúc này thực sự file chưa được ghi vào đĩa mềm. nếu để ý thì bạn sẽ thấy khoảng 5 giây sau đèn ổ mềm mới bắt đầu sáng. Nếu trước đó ta cứ tưởng là đã chép xong file mà rút đĩa mềm ra thì sẽ không có file nào được ghi vào đĩa cả. Sự phân mảnh của hệ thống file Hệ thống ext2 được thiết kế nhằm hạn chế tối thiểu sự phân mảnh nên ta không cần phải defragment hệ thống file ext2. Nguyên nhân gây ra sự phân mảnh của file system là việc ghi file nhiều lần trên ổ đĩa. Trong đó các file làm bộ nhớ mở rộng của hệ thống trên đĩa là có nguy cơ bị phân mảnh nhiều nhất. Đối với các hệ điều hành và MS Windows, hệ thống bộ nhớ mở rộng này nằm trên cùng một partition chính của hệ thống thông qua file pagefile.sys còn trong Linux thì hệ thống bộ nhớ mở rộng này được cho ra một partition riêng nên hạn chế rất nhiều sự phân mảnh. 2.3 Hệ thống File EXT3 Được xây dựng dựa trên cơ sở của hệ thống file chuẩn ext2 mà Linux đang sử dụng, ext3 đưa vào thêm chức năng mới v