Ánh Xạ Đối Tượng Thành ID Số

Trong hệ thống Skynet, một cấu trúc bảng băm được sử dụng để duy trì mối quan hệ ánh xạ giữa các dịch vụ và địa chỉ số 32-bit. Mỗi dịch vụ trong Skynet thực chất là một đối tượng C. Trong các hệ thống có môi trường sand-box, đặc biệt là kiến trúc đa luồng, việc sử dụng trực tiếp con trỏ đối tượng C để định danh thường không được khuyến khích. Thay vào đó, hệ thống sử dụng các số ID để làm “handle” (bộ xử lý) cho đối tượng. Cách tiếp cận này mang lại nhiều lợi ích: tăng tính ổn định cho hệ thống, dễ dàng kiểm tra hiệu lực của đối tượng, đồng thời giảm thiểu nguy cơ lỗi con trỏ treo (dangling pointer) hoặc giải phóng bộ nhớ nhiều lần.

Cũng giống như cách hệ điều hành quản lý file descriptor, Skynet áp dụng nguyên tắc tương tự khi giao số ID cho người dùng. Tuy nhiên, có sự khác biệt quan trọng: trong khi hệ điều hành thường tái sử dụng các ID đã được giải phóng (gây ra lỗi khi một ID cũ có thể trỏ đến đối tượng mới), Skynet cố gắng tối đa không tái sử dụng ID đã từng tồn tại. Điều này giúp tránh tình trạng một ID “chết” vô tình được dùng để truy cập đối tượng mới, gây ra hành vi không mong muốn. Cá nhân tôi đã từng gặp lỗi nghiêm trọng do vấn đề này trong một sản phẩm thương mại cách đây nhiều năm.

Việc không tái sử dụng ID khiến việc sử dụng mảng đơn giản trở nên không hiệu quả. Do đó, Skynet phải dùng bảng băm để đảm bảo hiệu suất ánh xạ. Cụ thể, mỗi lần cấp phát ID mới, hệ thống sẽ tăng dần từ ID cuối cùng được cấp (cho phép quay vòng nhưng bỏ qua giá trị 0 - giá trị được dành riêng cho ID không hợp lệ). Nếu gặp xung đột tại vị trí hash hiện tại, hệ thống tiếp tục tăng ID cho đến khi tìm được vị trí trống. Khi bảng băm đầy, kích thước của nó sẽ tự động tăng gấp đôi và toàn bộ dữ liệu được băm lại.

Mặc dù cách này có thể gây lãng phí một số ID, nhưng đổi lại bảng băm sẽ không bao giờ xảy ra va chạm (collision), đảm bảo tốc độ truy vấn tối ưu nhất. Đồng thời, việc triển khai bảng băm cũng đơn giản hơn nhiều.

Tôi cho rằng cấu trúc dữ liệu này có tính ứng dụng rộng rãi, nên đã dành thời gian tách riêng phần này từ Skynet thành một dự án mã nguồn mở độc lập. Các bạn quan tâm có thể tìm thấy trên GitHub.

Cấu trúc struct handlemap chính là hiện thực hóa của bảng băm này. Kiểu handleid hiện tại được định nghĩa là unsigned int, nhưng có thể tùy chỉnh thành kiểu số nguyên có độ dài khác tùy theo nhu cầu sử dụng.

Cấu trúc này cung cấp 5 hàm API chính:

1
2

struct handlemap * handlemap_init();
void handlemap_exit(struct handlemap *);

Hai hàm này dùng để khởi tạo và hủy bỏ cấu trúc handlemap. So với phiên bản Skynet gốc, phần hủy hiện chưa hỗ trợ dọn dẹp các ID còn tồn đọng - việc này nên được xử lý bởi các cơ chế bên ngoài.

• handleid handlemap_new(struct handlemap *, void *ud); - Hàm này cấp phát và liên kết một ID mới với đối tượng ud. Thông thường thao tác này thành công, nhưng trong trường hợp hệ thống thiếu bộ nhớ, hàm sẽ trả về 0 (ID không hợp lệ).

• void * handlemap_grab(struct handlemap *, handleid id); - Lấy con trỏ đối tượng tương ứng với ID và tăng bộ đếm tham chiếu (reference count) để đảm bảo an toàn đa luồng. Nếu ID không hợp lệ, hàm trả về NULL.

• void * handlemap_release(struct handlemap *, handleid id); - Giảm bộ đếm tham chiếu sau khi sử dụng xong đối tượng. Nếu bộ đếm về 0, đối tượng sẽ bị xóa khỏi bảng quản lý. Dù là trả lại tham chiếu hay xóa hoàn toàn, bạn đều phải kiểm tra giá trị trả về. Khi giá trị khác NULL, bạn cần tự giải phóng đối tượng tương ứng.

Điểm phức tạp nhất trong việc triển khai cấu trúc này là đảm bảo an toàn đa luồng. Nhiều luồng có thể đồng thời “grab” đối tượng hoặc xóa chúng mà không gây ra lỗi tranh chấp dữ liệu. Tôi đã sử dụng khóa đọc-ghi (read-write lock) để giải quyết vấn đề này:

• Khi tạo ID mới hoặc khi bộ đếm tham chiếu về 0 (gây xóa đối tượng), hệ thống sử dụng khóa ghi để đảm bảo tính toàn vẹn dữ liệu.
• Các thao tác “grab” và “release” chỉ cần khóa đọc, cho phép nhiều luồng thực hiện song song.

Khác với phiên bản Skynet gốc, phiên bản này đã bổ sung hỗ trợ các API thao tác nguyên tử (atomic operations) trên Windows. Tuy nhiên chưa qua kiểm thử kỹ lưỡng - các bạn quan tâm có thể thử biên dịch bằng Visual C++.