Chuỗi C: sai lầm kéo dài 50 năm

 (longtran2904.substack.com)
1 điểm bởi GN⁺ 4 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Chuỗi kết thúc bằng NUL của C không lưu giữ thông tin độ dài, dẫn đến việc quét lặp lại và lỗi biên; ngày nay, chuỗi dựa trên độ dài, lưu cùng lúc con trỏ và kích thước, phù hợp hơn làm thiết kế mặc định
  • Khi không có độ dài tường minh, các lệnh gọi strlen và việc duyệt từng byte bị lặp lại; quy tắc có tính byte kết thúc hay không lại khác nhau giữa snprintf, sizeof, strlen, khiến việc viết và rà soát mã trở nên khó khăn
  • Chuỗi dựa trên độ dài xử lý nhất quán chuỗi rỗng bằng size == 0, đồng thời có thể áp dụng nguyên vẹn các thao tác tìm kiếm, tách, slicing cho dữ liệu nhị phân tùy ý có chứa byte NUL
  • Có thể trả về chuỗi con trỏ tới một phần của bộ nhớ gốc, nhờ đó tránh cấp phát và sao chép trung gian khi cắt, tìm kiếm, token hóa cũng như khi phân tích CSV, Markdown, JSON, C
  • Sentinel vẫn hữu ích trong việc duy trì bất biến và một số thao tác tìm token, đồng thời vẫn cần chuyển đổi với các API C/OS hiện có; nhưng với phần lớn mã, kết hợp chuỗi dựa trên độ dài với tính bất biến ở ranh giới API sẽ đơn giản và linh hoạt hơn

Lưu con trỏ và độ dài thay vì kết thúc bằng NUL

  • Chuỗi C biểu diễn ranh giới bằng một con trỏ trỏ tới luồng ký tự và byte NUL cuối cùng
    • Trong bối cảnh hạn chế về bộ nhớ và hiệu năng của thập niên 1970, cách này có thể từng hợp lý, nhưng ngày nay gần như không còn lý do để tiếp tục duy trì
  • Phương án thay thế được các ngôn ngữ hiện đại và những framework lớn dùng là một struct lưu cùng lúc con trỏ dữ liệu và kích thước
struct String
{
    u8* data;
    u64 size;
};
  • Literal chuỗi có thể được tạo thành String bằng cách tính độ dài với sizeof(s) - 1, còn các thao tác như so sánh và xuất ra dùng trực tiếp kích thước đã lưu
  • Mảng cũng mất các thông tin như độ dài khi được chuyển thành con trỏ, nên gặp vấn đề về an toàn và tính tiện dụng tương tự chuỗi

Chi phí khi vứt bỏ thông tin độ dài

  • Nếu không lưu độ dài, mỗi đoạn mã sử dụng đều phải gọi lặp lại strlen hoặc duyệt từng byte, làm tăng công việc không cần thiết và độ phức tạp
  • Việc kiểm tra và cưỡng chế độ dài ở runtime cũng chậm và rườm rà hơn; debugger và công cụ phân tích khó xử lý nhất quán char*, char[N], char*[N]
  • Có quan điểm cho rằng phần lớn vấn đề bộ nhớ và lỗi overflow trong C bắt nguồn từ thiết kế này, nhưng cũng có phản biện rằng chỉ sentinel là đủ
  • Chuỗi không biết độ dài trở nên gần với mẫu truy cập tuần tự như danh sách liên kết hơn là truy cập ngẫu nhiên của mảng
  • Phía ủng hộ kiểu kết thúc bằng NUL cho rằng xử lý tuần tự khuyến khích thuật toán một lượt thay vì nhiều lượt, nên hiệu quả hơn
    • Nhiều lập trình viên, kể cả người mới, viết mã với giả định rằng có thể lấy độ dài chuỗi với chi phí thấp
    • Các routine chuỗi thông thường cũng được viết tự nhiên hơn ở dạng có cung cấp độ dài, và trong mã thực tế cùng một chuỗi bị duyệt nhiều lần vì các lệnh gọi strlen lặp lại
    • Tiền đề rằng số lượt duyệt ít hơn thì luôn nhanh hơn là kết quả của việc hiểu sai cách CPU hiện đại hoạt động

Các “độ dài” khác nhau mà snprintf, sizeof, strlen biểu thị

  • Hai số nguyên của snprintf trông như cùng là “độ dài”, nhưng quy tắc tính NUL lại trái ngược nhau
int snprintf(char *str, size_t size, const char *format, ...);
  • Tham số đầu vào size phải bao gồm cả không gian cho NUL kết thúc của buffer đầu ra, nhưng giá trị trả về biểu thị độ dài chuỗi lẽ ra đã được tạo ra, không tính byte NUL
  • Mỗi khi dùng hàm hoặc API liên quan đến chuỗi, cần kiểm tra riêng các điều kiện sau
    • Hàm có trực tiếp ghi byte NUL hay không
    • Có cần thêm không gian cho byte NUL vào kích thước cấp phát hay không
    • Đối số kích thước và giá trị trả về có bao gồm byte NUL hay không
  • sizeof("some string") bao gồm byte NUL, còn strlen("some string") thì không
  • Khi chuyển mã dựa trên literal sang mã dựa trên con trỏ ở runtime mà vẫn giữ nguyên - 1, sẽ phát sinh lỗi độ dài bị ngắn đi một ký tự
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

const char *str = "some string";
size_t size = strlen(str) - 1;

Việc ghi đè lặp lại byte NUL ở giữa

  • Nếu cộng các giá trị trả về của nhiều lệnh gọi snprintf vào offset để nối chuỗi, byte NUL kết thúc mà mỗi lệnh gọi ghi ra sẽ bị lệnh gọi tiếp theo ghi đè
int offset = 0;
offset += snprintf(ptr + offset, size - offset, "%d", my_int);
offset += snprintf(ptr + offset, size - offset, "%s", my_str);
offset += snprintf(ptr + offset, size - offset, "%f", my_flt);
  • Việc ghi byte kết thúc ở giữa là không cần thiết, nhưng bản thân tác động đến hiệu năng có thể không lớn
  • Vấn đề lớn hơn là hành vi này không trực quan, dẫn đến hiểu lầm rằng snprintf không kết thúc bằng NUL
  • Kết quả là có mã thêm ptr[offset] = 0; ở cuối, nhưng thao tác này cũng không cần thiết và càng củng cố hiểu lầm đó

Trạng thái kép giữa chuỗi rỗng và chuỗi null

  • Trong mô hình kết thúc bằng NUL, chuỗi rỗng và con trỏ null bị đối xử như những trạng thái không hợp lệ khác nhau, khiến mã xử lý chuỗi phải kiểm tra cả hai
  • Chuỗi và mảng của C# cũng là kiểu tham chiếu, nên đọc Length hoặc duyệt khi ở trạng thái null sẽ phát sinh ngoại lệ và cần xử lý riêng
  • Cách ứng phó phổ biến là luôn truyền và trả về chuỗi rỗng hoặc mảng rỗng thay vì null
    • Các quy tắc như String.IsNullOrEmpty, “Don’t Return Null”, “Don’t Pass Null” cũng là cách để xử lý sự phân biệt này
  • Với struct có con trỏ và độ dài, có thể xác định chuỗi rỗng chỉ bằng size == 0
    • Con trỏ có thể là null hoặc là một địa chỉ hợp lệ
    • Khi đã di chuyển tới cuối chuỗi, hoặc khi trỏ tới một chuỗi con rỗng bên trong chuỗi lớn, con trỏ vẫn có thể hợp lệ dù độ dài là 0
    • Nếu chỉ dereference sau khi kiểm tra độ dài, thì cả con trỏ trỏ tới vùng nhớ đã được giải phóng cũng sẽ không bị truy cập khi độ dài là 0

Dùng cùng một biểu diễn cho dữ liệu nhị phân

  • Chuỗi dựa trên độ dài không phụ thuộc vào sentinel, nên có thể lưu an toàn cả dữ liệu nhị phân tùy ý có chứa byte NUL
  • Giống như các hàm chuỗi ASCII vẫn hoạt động với UTF-8, các thao tác dựa trên độ dài như quét, tách, trim, slicing cũng có thể áp dụng cho mảng byte
  • Định dạng nhị phân kết thúc bằng NUL phải quyết định riêng có lưu byte kết thúc hay không
    • Nếu lưu, mã đọc/ghi sẽ gần với cách xử lý chuỗi thông thường hơn
    • Nếu không lưu, có thể giảm overhead về không gian và xử lý, đây là một trong những lý do chính để dùng định dạng nhị phân
  • Định dạng lưu cả độ dài lẫn nội dung rồi còn gắn thêm byte NUL sẽ làm sống lại cùng sự mơ hồ, vì lại phải kiểm tra độ dài đã lưu có bao gồm byte kết thúc hay không

Chuỗi con không cần cấp phát và sao chép

  • Nếu cưỡng chế kết thúc bằng NUL, thì cả kết quả trim, slicing, tách, token hóa, tìm kiếm cũng phải đặt byte kết thúc ở cuối, dẫn đến việc cấp phát và sao chép chuỗi mới cùng buffer trung gian
  • Chuỗi dựa trên độ dài có thể chỉ trả về con trỏ và độ dài trỏ tới một phần của dữ liệu gốc
String StrPrefix(String str, u64 size);
String StrPostfix(String str, u64 size);
String StrChop(String str, u64 size);
String StrSkip(String str, u64 size);
String Substr(String a, u64 min, u64 max);

String StrFindNeedle(String str, String needle);
String StrTrim(String str);
  • Lexer và parser cho CSV, Markdown, JSON, C có thể lưu slice của buffer đầu vào làm tên và giá trị trong parse tree mà không sao chép từng token
  • Mã tiếp theo dùng parse tree cũng có thể nhận cùng các slice đó và xử lý mà không cần quản lý bộ nhớ bổ sung

Khi sentinel vẫn hữu ích

  • Sentinel có thể duy trì bất biến của cấu trúc dữ liệu và đem lại lợi ích hiệu năng trong một số tình huống
  • Trên phần cứng và compiler hiện đại, lợi ích hiệu năng phần lớn đã yếu đi, trừ những trường hợp đặc biệt, nhưng hiệu quả giảm số bất biến mà chương trình phải quản lý vẫn còn
  • Trong kiểm tra token viết thủ công, sentinel NUL giúp vòng lặp có thể đọc byte hiện tại một cách an toàn
    • Nhìn trước như s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' có thể thất bại sớm nhờ tận dụng thứ tự byte và đánh giá ngắn mạch
    • Chuỗi dựa trên độ dài phải phân biệt trường hợp token kết thúc bằng khoảng trắng với trường hợp bản thân đầu vào đã kết thúc, đồng thời cần kiểm tra biên có hệ thống hơn khi nhìn trước
  • Phần lớn thư viện C và API OS hiện có yêu cầu chuỗi kết thúc bằng NUL, nên sẽ phát sinh chi phí chuyển đổi
    • Trên Windows, vì vốn đã phải chuyển UTF-8 sang UTF-16, chi phí thêm byte NUL tương đối nhỏ
    • Các ràng buộc do OS và nhà cung cấp áp đặt có thể bị đánh giá quá cao, còn lợi ích của chuỗi dựa trên độ dài có thể bị đánh giá quá thấp

Cách áp dụng tính bất biến cho API chuỗi

  • Thiết kế API và trừu tượng hóa đầy đủ của một tầng chuỗi hoàn chỉnh nằm ngoài phạm vi này, nhưng nguyên tắc cấu trúc cốt lõi được khuyến nghị là tính bất biến
  • Sau khi tạo, chuỗi không thay đổi nội dung và được đối xử như hằng; các hàm nhận chuỗi và trả về chuỗi cũng phải duy trì thuộc tính này
  • Chỉ cần bảo đảm tính bất biến ở chữ ký hàm và ranh giới API
    • Bên trong hàm có thể sửa tại chỗ hoặc dùng cách xử lý thủ tục khác nếu cần
    • Ở luồng thông tin cấp cao, ta có được lợi ích bất biến của lập trình hàm; ở phần triển khai cấp thấp, vẫn giữ được sự linh hoạt của lập trình thủ tục
  • Quy tắc này có thể vận hành như quy ước viết mã và API ngay cả khi ngôn ngữ hoặc runtime không cưỡng chế
  • Nếu phân biệt rõ các kiểu chuỗi và thao tác, gánh nặng duy trì quy tắc sẽ không lớn, và codebase có thể tự quyết định phạm vi áp dụng cũng như thời điểm nới lỏng
  • Ngôn ngữ cũng là một API, nên không cần chỉ dựa vào các ràng buộc do ủy ban ngôn ngữ đặt ra; có thể thiết kế quy tắc với mức chi tiết cần thiết

Ví dụ triển khai chuỗi dựa trên độ dài

Hạn chế của các biểu diễn chuỗi khác

  • Flexible array member

    • Giống SDS của Redis, cách này lưu độ dài hiện tại và dung lượng tối đa ở phần đầu struct, rồi khai báo trường cuối là flexible array member để đặt dữ liệu ký tự
    • Có thể tránh các vấn đề của chuỗi C như scan O(n) của strlen, nối thủ công và quản lý biên
    • Khó tương thích trực tiếp với literal chuỗi và không hỗ trợ chuỗi con hiệu quả, vốn là lợi thế cốt lõi của chuỗi dựa trên độ dài

  • Stretch buffer

    • Stretch buffer tương tự mảng động, lưu header độ dài và dung lượng ở một vùng riêng phía trước con trỏ, thay vì trong struct tường minh
    • Ngoài nhược điểm của flexible array member, cách này còn gán cho mọi char* một quy tắc metadata gần như vô hình, và phải dùng header này như một phần của mô hình API cho mọi thao tác chuỗi có ý nghĩa
    • Biểu diễn bằng con trỏ đem lại an toàn kiểu và tránh phải truy cập .str hoặc ->str, nhưng chỉ lợi ích này khó đủ để biện minh cho các quy tắc ẩn
    • Trường capacity riêng là tự nhiên với mảng động, nhưng trong chuỗi nó trộn các khái niệm khác nhau vào một kiểu, làm mờ ranh giới giữa các loại
    • Flexible array member cũng có thể gặp vấn đề tương tự, nhưng khác ở chỗ có thể dùng kích thước cố định ban đầu làm dung lượng và tránh mở rộng động

  • Kiểu Pascal

    • Chuỗi ngắn kiểu Pascal thường dùng mảng ký tự kích thước cố định 256 byte, dành 1 byte cho độ dài hoặc dùng kết thúc bằng NUL
    • Cách này từng hợp lệ dưới các ràng buộc thực tế về bộ nhớ và phần cứng trong quá khứ, nhưng ngày nay có thể dùng chiến lược cấp phát bộ nhớ arena tốt, nên không phù hợp ngoài các tình huống đặc biệt

Vì sao nên chọn chuỗi dựa trên độ dài làm mặc định

  • Ưu điểm của chuỗi dựa trên độ dài đã được một số cộng đồng và lập trình viên dày dạn biết đến, nhưng nhiều developer vẫn chưa từng cân nhắc cách triển khai này
  • Tài liệu liên quan nằm rải rác ở nhiều nơi, khiến khó so sánh cùng lúc việc mất độ dài, sự mơ hồ của byte kết thúc, xử lý nhị phân, chuỗi con, ưu nhược điểm của sentinel và các triển khai thay thế
  • Nếu biến kiểu chuỗi mặc định thành dạng slice gồm con trỏ và độ dài, có thể giải quyết việc bảo toàn thông tin biên, đơn giản hóa trạng thái, tương thích nhị phân và chuỗi con không cần cấp phát trong một thiết kế duy nhất

Bài viết liên quan

1 bình luận

 
GN⁺ 4 giờ trước
Ý kiến trên Lobste.rs

  • Tôi cho rằng để tránh byte đệm, nên đổi thứ tự các thành viên của struct như sau

    struct String  
{  
    u8* data;  
    u64 size;  
};

    thay vì:

    struct String  
{  
    u64 size;  
    u8* data;  
};

    • Trong môi trường con trỏ 64-bit, hai trường có cùng kích thước nên dù theo thứ tự nào cũng không có padding; còn trong môi trường 32-bit, bản thân u64 lớn hơn phạm vi mà con trỏ có thể biểu diễn nên là lãng phí
      Nếu dùng con trỏ 128-bit như CHERI, cách bố trí thứ nhất sẽ tạo padding căn chỉnh giữa data và size, còn cách bố trí thứ hai tạo padding ở cuối struct, nên cuối cùng vẫn hơi lãng phí không gian

    • Định nghĩa đúng là dạng dùng thành viên mảng có độ dài biến đổi

      typedef struct {  
  u64 len;  
  u8 buf[];  
} String;

  • Chuẩn C không định nghĩa các kiểu u8 và u64; đây là ký pháp kiểu Rust
    Việc biểu diễn độ dài bằng u64 trong môi trường 32-bit cũng không phù hợp, và trong C kiểu thông dụng để biểu diễn kích thước mảng là size_t, nên viết như sau sẽ tự nhiên hơn

    struct String  
{  
    char* data;  
    size_t size;  
};

    Có vẻ người viết bài, hoặc LLM tạo ra nó, không thực sự hiểu C

    • Nhiều dự án C định nghĩa u8 và u64 bằng typedef rồi sử dụng, và đây là một thực hành rất phổ biến
      Cũng có nhiều trường hợp thấy tên gọi uintN_t trong chuẩn là rườm rà; trong các dự án lớn, có dự án còn lâu đời hơn cả chuẩn đó, và Linux kernel cũng dùng các alias như vậy
      Ngược lại, lời phê bình này cho thấy người phê bình không quen với các dự án C

  • Nếu đã viết C hoặc C++ hơn vài tháng thì cách truyền con trỏ kèm độ dài chẳng phải là chuyện đã quá quen thuộc sao
    Hầu như mọi codebase C hiện đại cuối cùng đều truyền con trỏ dữ liệu cùng với độ dài, hoặc có thư viện chuỗi riêng

    • Việc có lưu độ dài hay không chỉ là một trong các vấn đề của chuỗi C; quản lý vòng đời cũng gây rất nhiều đau đầu
      std::string_view của C++ hiện đại nói rõ ý nghĩa “có thể xem chuỗi này, nhưng không được sửa hoặc lưu giữ nó”, nhờ đó giảm đáng kể bug
      Với API nhận chuỗi C, ràng buộc như vậy chỉ là một cam kết trên tài liệu

  • Tôi nghĩ sai lầm thật sự không nằm ở việc lưu độ dài hay kết thúc bằng null, mà là bản thân khái niệm String quá rộng để có ý nghĩa trong bất kỳ ngữ cảnh tùy ý nào
    Chuỗi được dùng cho đủ thứ vượt xa một mảng ký tự đơn giản, và ngay cả từ “ký tự” ở đây cũng bị đơn giản hóa quá mức, giống trò đùa vật lý về việc giả định một con bò hình cầu trong chân không
    Ngay từ “độ dài” đã không rõ là số cụm tự vị, số code point, hay tổng số byte
    Cũng cần phân biệt encoding là gì, có hiển thị cho người dùng và cần bản địa hóa hay không, đã được làm sạch chưa, hay là một giá trị bất khả phân không có lý do để sửa đổi như key trong map
    Nhìn từ góc độ này, ta sẽ không còn muốn kiểu chuỗi trong các triển khai thông thường nữa

    • Có người phàn nàn rằng Rust có quá nhiều kiểu chuỗi, nhưng một phần trong đó là để đưa các thông tin như vậy vào hệ thống kiểu
      Theo tôi biết, không thư viện nào gọi số cụm tự vị đơn giản là “độ dài”
      Có thể giải quyết một phần vấn đề bằng thông lệ đặt encoding mặc định là UTF-8 và dùng kiểu riêng cho encoding khác hoặc mảng byte; phần lớn còn lại có thể biểu diễn bằng hệ thống kiểu

  • Theo tôi biết, C không có khái niệm chuỗi ở cấp ngôn ngữ như phần lớn ngôn ngữ hiện đại cung cấp
    Thao tác chuỗi được cung cấp bởi thư viện chuẩn, không phải bản thân ngôn ngữ
    K&R ấn bản 2 giải thích rằng C là một ngôn ngữ tương đối cấp thấp, gần với các đối tượng mà máy tính trực tiếp xử lý như ký tự, số và địa chỉ; nó không cung cấp các phép toán để thao tác trực tiếp toàn bộ các đối tượng phức hợp như chuỗi, tập hợp, danh sách hay mảng
    Việc thiếu các tính năng như vậy có thể trông như một khiếm khuyết lớn, nhưng nhờ giữ ngôn ngữ nhỏ gọn, C có thể được mô tả ngắn gọn và học nhanh; lập trình viên có thể hiểu toàn bộ ngôn ngữ và dùng nó hằng ngày
    Để hiểu vì sao C được thiết kế như vậy và vì sao nó không có các tính năng hiện đại mà ngày nay được xem là hiển nhiên, tôi rất khuyên nên đọc lời tựa và phần mở đầu của K&R ấn bản 2

    • Tuy nhiên, theo nghĩa hạn chế rằng kiểu của string literal và cách bố trí bộ nhớ của nó quyết định hình dạng thư viện, thì chuỗi cũng là một phần của ngôn ngữ C
      Điều này cũng không khác nhiều so với ranh giới giữa ngôn ngữ và thư viện trong các ngôn ngữ cấp thấp như Rust

  • Có các đề xuất về cách tuần tự hóa như https://cr.yp.to/proto/netstrings.txt, và cũng có cách xử lý cả cấu trúc phức tạp như https://web.archive.org/web/20230305073119/…
    Nhưng có lẽ chúng trông quá đơn giản để phân tích cú pháp an toàn, nên những người ủng hộ nhiệt thành XML, JSON, YAML, Protocol Buffers, v.v. vẫn tiếp tục có việc để bận rộn