Liên kết động trong Linux và Windows

Phần I

Bài báo này thảo luận về khái niệm thư viện chia sẻ trong cả Windows và Linux. Đồng thời lướt qua các kiểu cấu trúc dữ liệu để giải thích liên kết động làm việc như thế nào trong các hệ điều hành này. Bài này rất hữu ích cho các nhà phát triển hứng thú nghiên cứu vấn đề về các hàm ẩn bảo mật, liên quan tới tốc độ liên kết động. Và cũng khẳng định một số kiến thức cơ bản về liên kết động đã được đưa ra trước đây.

Phần một giới thiệu các khái niệm cho cả Linux và Windows, nhưng cơ bản tập trung trên Linux. Lần tới, trong phần hai chúng ta sẽ thảo luận chúng làm việc trong Windows như thế nào và sau đó là so sánh hai môi trường với nhau.

Thư viện tĩnh và thư viện động

Thư viện là một tập hợp các chương trình con cho phép mã chương trình được chia sẻ và thay đổi theo kiểu modul. Các chương trình chạy và thư viện liên hệ với nhau theo một tiến trình gọi là linking (liên kết), làm việc qua một cầu nối (linker). 

Thư viện có thể chia thành hai loại: thư viện tĩnh và thư viện chia sẻ.

Thư viện tĩnh là một tập hợp các file kiểu đối tượng. Theo quy ước, các file này có đuôi kết thúc là “.a” trong UNIX và “.lib” trong Windows. Khi một chương trình được liên kết ngược với một thư viện tĩnh, mã máy từ các file đối tượng cho bất kì hàm mở rộng dùng trong chương trình sẽ được sao chép từ thư viện vào chương trình chạy cuối cùng.

Ngược lại với thư viện tĩnh, mã lệnh trong thư viện chia sẻ không giới hạn chương trình chạy tại thời gian liên kết. Phụ thuộc vào việc ghép địa chỉ lúc nào và như thế nào, tiến trình liên kết có thể phân loại là prelinking, load time linking, implicit run-time linking và explicit run-time linking.

Mã độc lập vị trí ( hay Win32 DDLs với “.SO” )

Các mã độc lập vị trí có thể được sao chép từ bất kì khu vực bộ nhớ nào, sau đó chạy mà không cần thêm chỉnh sửa gì. Không giống như mã định vị lại vị trí đòi hỏi phải có một tiến trình đặc biệt là các cầu nối để có được vị trí và sự thực thi phù hợp.

Win32 DLLs không độc lập vị trí. Chúng cần định vị lại suốt trong quá trình tải, trừ phi phần cơ sở được sửa chữa để không cần dùng. Định vị lại để các địa chỉ giống nhau có thể được chia sẻ. Nhưng nếu các tiến trình khác nhau xung đột trong dàn xếp bộ nhớ, bộ nạp cần tạo ra các bản “đa sao chép” của DDL trong bộ nhớ. Khi bộ nạp Windows vẽ bản đồ DDL vào bộ nhớ, nó mở file và cố gắng nạp chúng vào các địa chỉ cơ bản trước. Tại các trang trong bản đồ đã được vẽ, hệ thống phân trang sẽ xem xét liệu các trang này đã được thể hiện trong bộ nhớ chưa. Nếu đã có thì chỉ cần vẽ lại các trang cho tiến trình mới, khi việc định vị lại vị trí đã được bộ nạp thực hiện xong tại các địa chỉ cơ sở. Nếu không thì các trang vẫn đang được lấy về từ ổ đĩa.

Nếu phạm vi địa chỉ xác định cho DDL không phù hợp, bộ nạp vẽ lại bản đồ trang vào khu vực tự do trong không gian địa chỉ chương trinh. Trong trường hợp này, nó đánh dấu trang mã lệnh như là COW (copy-on-write: sao chép để ghi) mà trước đó đã được đánh dấu là read + execute (đọc và thực thi). Từ đó, các cầu nối phải thể hiện mã lệnh đã sửa chữa tại thời gian định vị lại vị trí, bắt buộc các trang phải được phục hồi theo kiểu file phân trang.

Linux giải quyết vấn đề này bằng cách dùng PIC (Position Independent Code – mã độc lập vị trí). Các đối tượng chia sẻ trong Linux thường có PIC để tránh phải định vị lại vị trí thư viện trong thời gian tải. Tất cả các trang mã lệnh có thể được chia sẻ giữa toàn bộ tiến trình dùng cùng một thư viện và có thể được lập trang tới (hoặc từ) hệ thống file. Trong dòng x86, không có cách đơn giản nào để định địa chỉ dữ liệu liên quan tới khu vực hiện tại, kể từ khi tất cả các jump và các call là kiểu liên hệ cấu trúc con trỏ. Do đó, tất cả các tham chiếu tới khu vực địa chỉ tĩnh mở rộng được thực hiện trực tiếp qua một bảng, gọi là bảng GOT (Global Offset Table).

Liên kết động trong Linux

Cấu trúc dữ liệu ELF

Vì đây không phải là bài báo đặe tả định dạng kiểu ELF, chúng ta sẽ chỉ thảo luận về các cấu trúc dữ liệu, liên quan tới nội dung mà chúng ta đang xem xét. Đối với liên kết động, các cầu nối ELF cơ bản dùng hai bảng đặc trưng theo bộ xử lý: Global Offset Table (GOT) và Procedure Linkage Table (PLT).

Global Offset Table (GOT) - Bảng địa chỉ Offset mở rộng

Các mối liên kết ELF hỗ trợ mã PIC qua bảng GOT trong từng thư viện chia sẻ. GOT chỉ chứa địa chỉ của tất cả các dữ liệu tĩnh dùng trong chương trình. Địa chỉ của GOT thông thường được lưu trữ trong một thanh ghi (EBX), trong đó một địa chỉ quan hệ của mã lệnh được dùng.

Procedure Linkage Table (PLT) - Bảng liên kết các chương trình con

Cả chương trình chạy sử dụng thư viện chia sẻ và chính bản thân thư viện chia sẻ đều có một bảng PLT. Tương tự như cách bảng GOT gửi lại các tính toán địa chỉ độc lập vị trí tới khu vực địa chỉ tuyệt đối, PLT cũng gửi lại các hàm gọi địa chỉ tuyết đối tới khu vực địa chỉ tuyệt đối.

Ngoài hai bảng trên, các mối liên kết còn có trong “.dinsym” (chứa tất cả biểu tượng xuất khẩu và quan trọng của file), “.dynstr” (xâu tên cho biểu tượng), “.hash” (bảng hash - bảng cầu nối chạy thực, có thể dùng để tra tìm các biểu tượng một cách nhanh chóng) và “.dynamic” (danh sách các kiểu đuôi và con trỏ).

Trong phần .dynamic, các kiểu đuôi quan trọng gồm:
+ DT NEEDED: giữ bảng kí tự offset của một xâu kết thúc là null, đưa ra tên thư viện cần thiết. Offset là một chỉ mục trong bảng, được ghi lại trong danh sách DT_STRTAB.
+ 3DT HASH: giữ địa chỉ của bảng ký tự hash, trỏ tới bảng ký tự phần tử trong DT_SYMTAB.
+ DT STRTAB: giữ địa chỉ của bảng xâu
+ DT SYMTAB: giữ địa chỉ của bảng biểu tượng

Bảng ký tự Hash

nBuckets //không có đường vào bucket
nChains // không có đường vào chain
bucket[]
chain[]

Cả mảng bucket và chain chứa các chỉ mục bảng ký tự. Với mỗi ký tự phải tìm, nó sẽ được băm ra và thành phần hash%Buckets được dùng như là một chỉ mục trong mảng bucket[]. Mỗi phần tử bucket đưa ra một chỉ mục, một symindx, cũng như là bảng biểu tượng trong mảng chain. Nếu đường vào của bảng biểu tượng không được ghép nối, nó sẽ tìm đưòng vào tiếp theo vẫn với giá trị băm như thê, và dùng chỉ mục lấy ra từ Chain [symindx]. 

Thực hiện như thế nào 

Trong Linux, tự bản thân mối liên kết động ld.so đã là một thư viện chia sẻ ELF. Khi chương trình khởi động, hệ thống vẽ bản đồ ld.so thành một phần của không gian địa chỉ và chạy mã lệnh bootstrap của nó. Đường vào chính của bộ nạp được định nghĩa trong dl_main(elf/rtld.c). Cầu nối định vị và giải quyết, tham chiếu tới thường trình riêng của nó. Đó là việc cần thiết để tải mọi thứ về.

Phân đoạn tĩnh (nằm ở phần tiêu đề chương trình) trong file ELF bao gồm một con trỏ, trỏ tới bảng xâu của file (DT_STRTAB), cũng như là mục vào DT_NEEDED. Mỗi một phần tử đó bao gồm phần offset trong bảng xâu tên của thư viện yêu cầu. Mối liên kết động tạo ra một danh sách phạm vi chương trình chạy, bao gồm cả các thư viện để tải.

Chúng ta có hai cách đặc tả đối tượng trước khi tải. Hoặc là qua môi trường biến LD_PRELOAD, hoặc là qua file /etc/ld.so.preload. Cách sau có thể được dùng khi hàng rào an toàn ngăn cản dùng qua môi trường biến. Bộ nạp thêm mục vào DT_NEEDED của chương trình chạy, cũng như là phạm vi sau các đường vào trước khi tải.

Với mỗi một đường vào trong phạm vi, mối liên kết sẽ tìm file chứa thư viện. Mỗi khi thư viện được tìm ra, mối liên kết sẽ đọc tiêu dề ELF để tìm tiêu đề chương trình, được trỏ bởi phân đoạn động. Mối liên kết sẽ nạp sơ đồ thư viện vào không gian địa chỉ chương trình. Từ phân đoạn động, nó thêm bảng biểu tượng của thư viện vào chain của các bảng biểu tưọng. Và nếu các thư viện phụ thuộc nhiều hơn, nó sẽ thêm vào một danh sách được tải, và quá trình này được tiếp tục. Để sáng sủa hơn, chú ý rằng thực tế quá trình này tạo ra một cấu trúc link_map cho mỗi thư viện và thêm nó vào một danh sách liên kết mở rộng.

Mối liên kết giữ trong bộ nhớ một danh sách liên kết của các bảng (như cấu trúc kiểu link_map, tham chiếu bởi tham số dl_loaded trong cấu trúc rtld_global) trong mỗi file. Mối liên kết tận dụng bảng hash hiện tại trong file ELF (nằm trong DT_HASH) để tăng tốc độ tìm kiếm biểu tượng.

Mỗi lần bộ nạp kết thúc việc xây dựng danh sách liên kết các bảng phụ thuộc, nó sẽ thăm lại từng thư viện và điều khiển đường vào định vị lại vị trí của thư viện, làm đầy bảng GOT của thư viện và thể hiện các định vị cần thiết.

Biến LD_BIND_NOW dò ra bộ chạy liên kết động. Nếu nó bật, mối liên kết động sẽ xác định giá trị đường vào bảng PLT (mà tất cả kiểu đều thoại loại R_386_JMP_SLOT) tại thời gian tải. Nếu không thì, mối liên kết động sẽ thực hiện liên kết lười của các địa chỉ chương trình con. Và do đó các địa chỉ không bị giới hạn, trừ khi thường trình được gọi.

Một bước tới Linux bằng cách liên kết Procedure

Trong phần này, chúng ta sẽ tìm hiểu một hàm được định nghĩa trong thư viện chia sẻ libtest.so hoạt động như thế nào tại thời gian chạy. Chương trình chạy, được tách rời bằng thành phần gdb bên dưới đã được tạo ra bằng liên kết với một thư viện PIC, libtest.so.

Hình 1. Chương trình chạy tách rời dùng gdb

Hãy bắt đầu xem xét từ lệnh gọi được chỉ ra ở hình 1.

Điạ chỉ trong lệnh gọi (0x80483a4) là một đường vào trong bảng PLT. Bốn đường vào đầu tiên trong PLT (nhờ đó lối vào thứ 3 và thứ 4 được duy trì) là phổ biến cho tất cả các hàm cuộc gọi. Phần còn lại của đường vào được nhóm lại thành một khối, mỗi khối gồm 3 đường vào và tương ứng cho một hàm. Điều này được chỉ ra trong hình 2.

Hình 2. Đường vào đầu tiên trong PLT.

Hình 3. Bảng GOT trên đĩa.

Câu lệnh bao gồm một bước nhảy tới địa chỉ trong đường vào của bảng GOT *(GOT + 0x14), và lại trỏ vào đường vào tiếp theo trong bảng PLT viz 0x80483aa (như đã được chỉ ra trong hình 2).

Các câu lệnh tiếp theo thực hiện với các địa chỉ dùng mối liên kết động. Câu lệnh nhảy đẩy một khoảng chứa trống (0x10). Đây là một khoảng trống trong bảng định vị lại file, trỏ tới biểu tượng được yêu cầu trong bảng biểu tượng, và địa chỉ trỏ tới đường vào GOT (0x804963c).

Hình 4. Đường vào định vị lại vị trí 8 byte (RELSZ).

Như đã thấy trên hình 4, kích thước của đường vào định vị lại vị trí là 8 byte (RELSZ). Khoảng trống 0x10 cho chúng ta đường vào số 3 trong bảng .rel.plt, với đường vào là cho m. Lối vào khoảng trống trong bảng tương ứng với địa chỉ GOT, phải được cập nhật.

Đoạn mã lệnh sau nhảy tới đường vào đầu tiên trong PLT, là phần chung.

Hình 5. Điểm ngắt 1.

Đường vào trong PLT lại nhảy tới địa chỉ trong GOT + 8. Bộ nạp tại thời gian tải cập nhật đường vào trong GOT + 4 và GOT + 8 (sớm hơn 0x000000 như đã thấy trong hình 3). Bây giờ GOT + 8 (0x 4000bcb0) trỏ tới một địa chỉ được vẽ với ld-2.3.2.0 (mối liên kết thời gian chạy). như có thể thấy trong hình 6.

Hình 6. Bản đồ hoá địa chỉ với mối liên kết thời gian chạy.

Mỗi lần thường trình liên kết động tra tìm giá trị biểu tượng dùng bảng thời gian chạy được ghép nối, và lưu trữ địa chỉ thường trình (0x400177db) trong đường vào GOT (0x 804963c) như trong hình 5, lệnh gọi tiếp theo nhảy trực tiếp tới thường trình của chúng.

Peeking vào mối liên kết động ld.so

Hãy trở lại đường vào GOT. Như chúng ta đã thấy, GOT + 8 bao gồm địa chỉ của biểu tượng của mối liên kết thường trình định vị lại vị trí. GOT + 4 được nạp đầy bởi bộ nạp với điạ chỉ của cấu trúc link_map, được định nghĩa trong include/link.h. Bảng GOT được làm đầy bằng thường trình elf_machine_runtime_setup được định nghĩa trong dl-machine.h.

Hãy xem xét kỹ hơn:

Cấu trúc link_map { ElfW(Addr) l_addr; /*điạ chỉ đối tượng chia sẻ điạ chỉ cơ bản được nạp */ char *l_name; /* đối tượng tên file tuyệt đối được tìm trong */ ElfW(Dyn) *l_ld; /* khu vực động của đối tượng chia sẻt */ struct link_map *l_next, *l_prev; /* Chuỗi đối tượng được tải */ /* Tất cả bộ phận sau nằm trong thành phần của mối liên kết động. Chúng có thể thay đổi mà không cần thông báo */ /* Con trỏ chỉ mục trỏ tới khu vực động*/ ElfW(Dyn) *l_info[DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM + DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM]; const ElfW(Phdr) *l_phdr; /* Con trỏ trỏ tới bảng tiêu đề chương trình trong lõi */ ElfW(Addr) l_entry; /* đường vào trỏ khu vực */ ElfW(Half) l_phnum; /* Số đường vào tiêu đề chương trình */ ElfW(Half) l_ldnum; /* Số đường vào phân đoạn động */ /* Mảng phụ thuộc DT_NEEDED và các phụ thuộc của nó, trong câu lện phụ thuộc để tra tìm biểu tượng (có hoặc không có bản sao). Không có đường vào trước phụ thuộc được tải */ struct r_scope_elem l_searchlist; /* Symbol hash table */ Elf_Symndx l_nbuckets; const Elf_Symndx *l_buckets, *l_chain;

Tại thời gian việc thực thi nhảy vào thường trình phân giải biểu tượng, chúng ta có địa chỉ của bản đồ liên kết và khoảng trống định vị lại trong ngăn xếp. Khoảng trống định vị lại đã được nói ở trên đưa ra chỉ mục trong bảng biểu tượng cho tên biểu tưọng và tưong ứng với địa chỉ GOT, nơi các địa chỉ phân giải sẽ được ghi. Điạ chỉ phân giải đối tượng (GOT+8) trỏ tới một trampoline ELF_MACHINE_RUNTIME_TRAMPOLINE.

Hãy xem ELF_MACHINE_RUNTIME_TRAMPOLINE được định nghĩa trong dl-machine.h. Mã lệnh duy trì các thanh ghi và thực hiện lời gọi tới hàm fixup().

movl 16(%esp), %edx # Copy args pushed by PLT in register. Note movl 12(%esp), %eax # that `fixup' takes its parameters in regs. call fixup # Call resolver.

Hàm fixup() được định nghĩa trong dl-runtime.c.

Mảng l_info bên trong cấu trúc link_map bao gồm các con trỏ chỉ mục trỏ tới khu vực động:

const ElfW(Sym) *const symtab = (const void *) D_PTR (l, l_info[DT_SYMTAB]); const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]); const PLTREL *const reloc = (const void *) (D_PTR (l, l_info[DT_JMPREL]) + reloc_offset);

Từ l_info mã lệnh lưu trữ các con trỏ trỏ tới bảng biểu tượng và bảng định vị lại vị trí. Nó tính toán đường vào định vị lại cho biểu tượng bằng cách thêm khoảng trống định vị lại để sắp xếp việc định vị lại vị trí.

const ElfW(Sym) *sym = &symtab[ELFW(R_SYM) (reloc->r_info)]; void *const rel_addr = (void *)(l->l_addr + reloc->r_offset);

Từ reloc -> r_info, nó lấy các chỉ mục biểu tượng được dùng để sắp xếp chỉ mục vào bảng biểu tượng và lấy thông tin cũng như địa chỉ được cập nhật từ reloc -> r_offset + l->l_addr.

Hàm fixup gọi _dl_lookup_symbol() cho công việc tra tìm với các thông tin trên.

Thành phần _dl_lookup_symbol() khi trả lại lại gọi do_lookup() cho từng đường vào trong mảng scope. Mảng scope bao gồm các phần tử thuộc kiểu cấu trúc r_scope_elem cho các thư viện. Nó được xác định như là một phần của phạm vi tìm kiếm mở rộng. Cấu trúc này được làm đầy tại thời gian tải.

struct r_scope_elem { /* Array of maps for the scope. */ struct link_map **r_list; /* Number of entries in the scope. */ unsigned int r_nlist; };

Lời gọi do_lookup được định nghĩa cho FCT trong do-lookup.h. Bây giờ hãy xem xét một chút về nó từ một phối cảnh logic trong tiếng Anh thuần tuý, để làm cho nó dễ hiểu hơn. Thực hiện như sau:

Do_lookup algorithm() { For each of the link_map structures in scope->r_list do{ Get the symtable address from link_map->l_info Get the strtable address from link_map->l_info

Tìm kiếm hash buket thích hợp trong các đối tượng bảng biểu tượng dùng thủ tục băm tên biểu tượng trong _dl_lookup_symbol().

Dùng đường dẫn chỉ mục trong chuỗi link_map  -> l_chain

Do {
Tra tìm đường dẫn bảng biểu tượng dùng chỉ mục. So ánh tên biểu tượng với (strtab + sym->st_name).
Nếu tìm thấy, trả lại đường vào bảng biểu tượng với cấu trúc link_map;
}
}

Bây giờ hãy trở lại hàm fixup().

/*link_map ->l_addr trỏ tới điạc chỉ tải cơ sở */ value = link_map->l_addr + sym->st_value /* Cuối cùng, tự sửa plt. */ return elf_machine_fixup_plt (l, result, reloc, rel_addr, value);

Trở lại dl-machine.h, nó đưa lên các thanh ghi lưư trữ:

xchgl %eax, (%esp) # Get %eax contents and store function address. ret $8 # Jump to function address.

Nếu bạn nhớ, ngoại trừ lời gọi từ hàm chính, tất cả các đưòng dẫn mã lệnh khác là thông qua lệnh nhảy. Điều này tách ngăn xếp ra và thực hiện một lệnh nhảy tới điạ chỉ hàm phân giải.

Kết luận phần một

Trong phần một chúng ta đã thảo luận cách dùng của liên kết động cho cả môi trường Linux và Windows. nhưng tập trung chủ yếu vào Linux. Thời gian tới, trong phần hai chúng ta sẽ xem xét cẩn thận liên kết động trong Windows cũng như hiện nay với Linux. Nó sẽ gồm tiến trình liên kết lười và bộ giúp đỡ tải trì hoãn. Sau đó chúng ta sẽ xem cách thức tăng tốc độ cho cả hai môi trường như thế nào.