C dizeleri: 50 yıldır süren bir hata

 (longtran2904.substack.com)
1 puan yazan GN⁺ 4 시간 전 | 1 yorum | WhatsApp'ta paylaş
  • C’nin NUL sonlandırmalı dizeleri uzunluk bilgisini korumaz; bu da tekrarlanan taramalara ve sınır hatalarına yol açar. Günümüzde, işaretçi ile boyutu birlikte tutan uzunluk tabanlı dizeler temel tasarım olarak daha uygundur.
  • Açık bir uzunluk yoksa strlen çağrıları ve bayt bayt dolaşım tekrarlanır; ayrıca snprintf, sizeof ve strlen için sonlandırma baytının dahil edilip edilmediği farklı olduğundan kod yazmak ve gözden geçirmek zorlaşır.
  • Uzunluk tabanlı dizeler boş dizeleri size == 0 ile tutarlı biçimde ele alır ve NUL baytı içeren keyfi ikili veriler üzerinde de arama, bölme ve dilimleme işlemlerini aynen uygulayabilir.
  • Özgün belleğin bir bölümünü işaret eden alt dize döndürülebilir; böylece kesme, arama, token’lama ve CSV, Markdown, JSON, C ayrıştırmasında ara tahsisler ve kopyalamalar önlenir.
  • Sentinel’ler değişmezlerin korunması ve bazı token aramalarında hâlâ yararlıdır; ayrıca mevcut C ve OS API’lerine dönüşüm de gerekir. Ancak çoğu kodda, uzunluk tabanlı dizeleri API sınırlarındaki değişmezlik ile birleştirmek daha basit ve esnektir.

NUL sonlandırma yerine işaretçi ve uzunluk saklamak

  • C dizeleri, karakter akışını işaret eden bir işaretçi ve son sınırı belirleyen NUL baytıyla temsil edilir.
    • Bu yaklaşım 1970’lerin bellek ve performans kısıtlarında makul olmuş olabilir, ancak bugün bunu sürdürmek için neredeyse hiçbir neden yok.
  • Modern dillerin ve büyük framework’lerin benimsediği alternatif, veri işaretçisi ile boyutu birlikte tutan bir struct’tır.
struct String
{
    u8* data;
    u64 size;
};
  • Dize literalleri sizeof(s) - 1 ile uzunluk hesaplanarak Stringe dönüştürülebilir; karşılaştırma ve çıktı gibi işlemler de doğrudan saklanan boyutu kullanır.
  • Diziler de işaretçiye dönüştürüldüğünde uzunluk gibi bilgileri kaybeder ve dizelere benzer güvenlik ve kullanılabilirlik sorunları yaşar.

Uzunluk bilgisini atmanın maliyeti

  • Uzunluğu saklamazsanız, kullanan kodun her yerde tekrar tekrar strlen çağırması veya baytları tek tek dolaşması gerekir; bu da gereksiz iş ve karmaşıklık yaratır.
  • Uzunluğu çalışma zamanında denetleyip zorlamak da daha yavaş ve zahmetlidir; ayrıca debugger’lar ve analiz araçları char*, char[N], char*[N] türlerini tutarlı biçimde ele almakta zorlanır.
  • C’deki bellek sorunlarının ve taşma hatalarının önemli bir kısmının bu tasarımdan kaynaklandığı görüşü vardır; buna karşılık sadece sentinel’lerin yeterli olduğunu savunanlar da vardır.
  • Uzunluğu bilinmeyen dizeler, dizilerdeki rastgele erişimden çok bağlı listelerdeki gibi sıralı erişim desenine yaklaşır.
  • NUL sonlandırmayı savunanlar, sıralı işlemenin çok geçişli yaklaşımlar yerine tek geçişli algoritmaları teşvik ederek verimli olduğunu düşünür.
    • Yeni başlayanlar da dahil birçok programcı, dize uzunluğunun ucuzca elde edilebildiğini varsayarak kod yazar.
    • Genel dize rutinleri de uzunluğun verildiği biçimde daha doğal yazılır; tekrarlanan strlen çağrıları yüzünden gerçek kod aynı dize üzerinde birden çok kez dolaşır.
    • Geçiş sayısı azsa bunun her zaman daha hızlı olacağı varsayımı, modern CPU’ların çalışma biçimini yanlış anlamanın sonucudur.

snprintf, sizeof, strlen için farklı “uzunluk” anlamları

  • snprintf’in iki tamsayısı aynı “uzunluk” gibi görünür, ancak NUL dahil etme kuralı bakımından birbirinin tersidir.
int snprintf(char *str, size_t size, const char *format, ...);
  • Girdi olan size, çıktı tamponunda NUL sonlandırma alanını da içermelidir; ancak dönüş değeri, NUL baytı hariç oluşturulacak dizenin uzunluğunu gösterir.
  • Dizeyle ilgili bir fonksiyon ya da API kullanırken her seferinde şu koşulları ayrıca kontrol etmeniz gerekir:
    • Fonksiyon NUL baytını kendisi yazıyor mu?
    • Tahsis boyutuna NUL baytı için ek alan eklemek gerekiyor mu?
    • Boyut parametresi ve dönüş değeri NUL baytını içeriyor mu?
  • sizeof("some string") NUL baytını içerir, ama strlen("some string") içermez.
  • Literal tabanlı kodu çalışma zamanında işaretçi tabanlı koda çevirirken aynı - 1 korunursa, uzunluğun bir eksik hesaplanması şeklinde hata oluşur.
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

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

Ortadaki NUL baytlarını tekrar tekrar ezmek

  • Birden fazla snprintf dönüş değerini ofsete ekleyerek dize birleştirildiğinde, her çağrının yazdığı NUL sonlandırma baytı bir sonraki çağrı tarafından ezilir.
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);
  • Aradaki sonlandırma baytlarını yazmak gereksizdir, ancak performans etkisi tek başına büyük olmayabilir.
  • Daha büyük sorun, bu davranışın sezgisel olmaması ve snprintf’in NUL sonlandırma yapmadığı yönünde yanlış anlamalara yol açmasıdır.
  • Sonuçta sona ptr[offset] = 0; ekleyen kodlar ortaya çıkar; oysa bu da gereksizdir ve aynı yanlış anlamayı daha da pekiştirir.

Boş dize ile null dizenin ikili durumu

  • NUL sonlandırmalı modelde boş dize ile null işaretçi iki ayrı geçersiz durum gibi ele alınır; bu yüzden dize işleme kodu her ikisini de denetlemek zorunda kalır.
  • C#’ta dizeler ve diziler de referans türü olduğundan, null durumunda Length okumak ya da üzerinde dolaşmak istisna üretir ve ayrı işlem gerektirir.
  • Yaygın çözüm, null yerine her zaman boş dize ya da boş dizi geçirip döndürmektir.
    • String.IsNullOrEmpty, “Don’t Return Null”, “Don’t Pass Null” gibi kurallar da bu ayrımı yönetme yöntemleridir.
  • İşaretçi ve uzunluk taşıyan bir struct’ta boş dize olup olmadığı yalnızca size == 0 ile anlaşılabilir.
    • İşaretçi null da olabilir, geçerli bir adres de olabilir.
    • Dizenin sonuna gelinmişse ya da daha büyük bir dize içindeki boş bir alt dize gösteriliyorsa, uzunluk 0 olsa bile işaretçi geçerli olabilir.
    • Yalnızca uzunluk kontrol edildikten sonra dereference yapılıyorsa, daha önce serbest bırakılmış belleği gösteren bir işaretçiye de uzunluk 0 iken erişilmez.

İkili veriyle aynı gösterimi kullanmak

  • Uzunluk tabanlı dizeler sentinel’e dayanmadığı için NUL baytı içeren keyfi ikili verileri de güvenle saklayabilir.
  • ASCII dize fonksiyonlarının UTF-8’de de çalışması gibi, tarama, bölme, kırpma ve dilimleme gibi uzunluk tabanlı işlemler bayt dizilerine de uygulanabilir.
  • NUL sonlandırmalı ikili formatlarda sonlandırma baytının saklanıp saklanmayacağına ayrıca karar verilmelidir.
    • Saklanırsa okuma ve yazma kodu genel dize işleme tarzına daha yakın olur.
    • Saklanmazsa alan ve işlem yükü azaltılabilir; bu da ikili format kullanmanın başlıca nedenlerinden biridir.
  • Hem uzunluğu hem içeriği saklayıp bir de NUL baytı ekleyen formatlar, saklanan uzunluğun sonlandırma baytını içerip içermediğini yeniden sorgulamayı gerektirir; yani aynı muğlaklığı geri getirir.

Tahsis ve kopya gerektirmeyen alt dizeler

  • NUL sonlandırmayı zorunlu kılmak, kırpma, dilimleme, bölme, token’lama ve arama sonuçlarının sonuna da sonlandırma baytı yerleştirmeyi gerektirir; bu yüzden yeni dize ve ara tamponlar için tahsis ve kopyalama yapılır.
  • Uzunluk tabanlı dizeler ise yalnızca özgün verinin bir bölümünü gösteren işaretçi ve uzunluğu döndürebilir.
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);
  • CSV, Markdown, JSON ve C için lexer’lar ve parser’lar, her token’ı kopyalamadan girdi tamponundaki slice’ları ayrıştırma ağacındaki adlar ve değerler olarak tutabilir.
  • Ayrıştırma ağacını kullanan sonraki kod da aynı slice’ları alıp ek bellek yönetimi olmadan işleyebilir.

Sentinel’lerin hâlâ yararlı olduğu durumlar

  • Sentinel’ler veri yapısı değişmezlerini korumakta ve bazı durumlarda performans avantajı sağlamada yararlı olabilir.
  • Modern donanım ve derleyicilerde performans avantajları özel durumlar dışında çoğunlukla zayıflamış olsa da, programın yönetmesi gereken değişmez sayısını azaltma etkisi sürer.
  • Elle yazılmış token denetiminde, NUL sentinel sayesinde döngü mevcut baytı güvenle okuyabilir.
    • s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' gibi ileri bakmalar, bayt sırası ve kısa devre değerlendirmesi sayesinde erken başarısız olabilir.
    • Uzunluk tabanlı dizelerde token’ın boşlukla mı bittiği yoksa girdinin mi bittiği ayırt edilmelidir; ileri bakma için de daha sistematik sınır kontrolleri gerekir.
  • Mevcut C kütüphanelerinin ve OS API’lerinin çoğu NUL sonlandırmalı dizeler istediği için dönüşüm maliyeti doğar.
    • Windows’ta UTF-8 zaten UTF-16’ya çevrilmek zorunda olduğundan, NUL baytı ekleme maliyeti görece küçüktür.
    • OS ve üretici kısıtları gerçek olduğundan daha fazla abartılabilir; uzunluk tabanlı dizelerin yararları da olduğundan az değerlendirilebilir.

Dize API’lerine değişmezlik uygulamak

  • Olgun bir dize katmanının tam API tasarımı ve soyutlaması kapsam dışı olsa da, temel yapısal ilke olarak değişmezlik önerilir.
  • Dizeler bir kez oluşturulduktan sonra içerikleri değiştirilmeden sabitmiş gibi ele alınmalı; dize alan ve dize döndüren fonksiyonlar da bu özelliği korumalıdır.
  • Değişmezliği fonksiyon imzalarında ve API sınırlarında garanti etmek yeterlidir.
    • Fonksiyon içinde ihtiyaç varsa yerinde değiştirme veya başka prosedürel işlemler kullanılabilir.
    • Böylece üst düzey bilgi akışında fonksiyonel programlamanın değişmezlik avantajları, alt düzey uygulamada ise prosedürel programlamanın esnekliği korunur.
  • Bu kural, dil ya da runtime tarafından zorunlu kılınmasa da kodlama ve API teamülü olarak uygulanabilir.
  • Dize türlerini ve işlemlerini açık biçimde ayırmak kuralları koruma yükünü büyütmez; kod tabanı kapsamı ve hangi noktada gevşetileceğini kendisi belirleyebilir.
  • Dil de bir API olduğundan, yalnızca dil komitesinin koyduğu kısıtlara dayanmak yerine gerekli ayrıntı düzeyinde kurallar tasarlanabilir.

Uzunluk tabanlı dizelere dair uygulama örnekleri

Diğer dize gösterimlerinin kısıtları

  • Esnek dizi üyesi

    • Redis’in SDS yapısında olduğu gibi, struct’ın baş kısmında mevcut uzunluk ve azami kapasite saklanır; son alan ise esnek dizi üyesi olarak tanımlanıp karakter verisi oraya yerleştirilir.
    • Bu yöntem, strlen’in O(n) taramasını ve C dizelerindeki elle birleştirme/sınır yönetimi sorunlarını önleyebilir.
    • Ancak dize literalleriyle doğrudan uyumlu değildir ve uzunluk tabanlı dizelerin ana avantajlarından biri olan verimli alt dize desteğini sunamaz.

  • Stretch buffer

    • Stretch buffer, dinamik diziye benzer; fakat uzunluk ve kapasite başlığını açık bir struct yerine işaretçinin önündeki ayrı bir bölgede saklar.
    • Esnek dizi üyesi yaklaşımının dezavantajlarına ek olarak, her char* için neredeyse görünmez metadata kuralları getirir ve anlamlı her dize işleminde bu başlığı API modelinin bir parçası haline getirir.
    • İşaretçi gösterimi tür güvenliği sağlar ve .str ya da ->str erişimini gerektirmez; ancak bu avantaj tek başına gizli kuralları haklı çıkarmakta yetersiz kalır.
    • Ayrı bir capacity alanı, dinamik diziler için doğaldır; ama dizelerde farklı kavramları tek türde birleştirerek türler arası ayrımı bulanıklaştırır.
    • Esnek dizi üyesinde de benzer sorunlar olabilir; ancak ilk sabit boyutun kapasite olarak kullanılabilmesi ve dinamik büyütmeden kaçınılabilmesi gibi bir fark vardır.

  • Pascal stili

    • Pascal tarzı kısa dizeler genellikle 256 baytlık sabit boyutlu karakter dizisi kullanır; uzunluk için 1 bayt ayrılır ya da NUL sonlandırma kullanılır.
    • Geçmişteki gerçek bellek ve donanım kısıtlarında geçerliydi; ancak bugün iyi bir arena bellek tahsis stratejisi kullanılabildiği için özel durumlar dışında uygun değildir.

Neden varsayılan olarak uzunluk tabanlı dizeler kullanılmalı?

  • Uzunluk tabanlı dizelerin avantajları bazı topluluklar ve deneyimli programcılar arasında bilinse de, pek çok geliştirici hâlâ böyle bir uygulamayı hiç düşünmemiştir.
  • Konuyla ilgili malzeme birçok yere dağılmış olduğundan, uzunluk kaybını, sonlandırma baytı belirsizliğini, ikili veri işlemeyi, alt dizeleri, sentinel’lerin artılarını ve eksilerini, ayrıca alternatif uygulamaları bir arada karşılaştırmak zordu.
  • Varsayılan dize türünü işaretçi ve uzunluk içeren bir slice olarak tanımlamak, sınır bilgisini koruma, durumları sadeleştirme, ikili veri uyumluluğu ve tahsissiz alt dize kullanımını tek bir tasarımda birleştirir.

İlgili okumalar

1 yorum

 
GN⁺ 4 시간 전
Lobste.rs görüşleri

  • Padding byte’lardan kaçınmak için struct üyelerinin sırasını şöyle değiştirmek daha iyi olabilir diye düşünüyorum

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

    bunun yerine:

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

    • 64 bit pointer ortamlarında iki alanın boyutu aynı olduğundan hangi sırada olursa olsun padding olmaz; 32 bit ortamlarda ise pointer ile ifade edilebilecek aralıktan daha büyük bir u64 zaten israftır
      CHERI gibi 128 bit pointer kullanan bir yerde ilk yerleşimde data ile size arasına, ikinci yerleşimde ise struct’ın sonuna hizalama için padding eklenir; yani sonuçta yine biraz alan boşa gider

    • Doğru tanım, esnek uzunluklu dizi üyesi kullanan biçimdir

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

  • C standardı u8 ve u64 tiplerini tanımlamaz; bu daha çok Rust tarzı bir gösterimdir
    32 bit ortamda uzunluğu u64 ile göstermek de pek uygun değil; ayrıca C’de dizi boyutunu ifade etmek için alışılmış tip size_t olduğundan, bunu şöyle yazmak daha doğal olur

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

    Yazıyı yazan kişinin ya da bunu üreten LLM’in C’yi pek bilmediği anlaşılıyor

    • Pek çok C projesi u8 ve u64 için typedef tanımlayıp kullanır; bu son derece yaygın bir pratiktir
      Standardın uintN_t adlandırmasını hantallık olarak gören çok kişi vardır; ayrıca büyük projelerin bazıları bu standarttan daha eskidir ve Linux kernel de bu tür takma adlar kullanır
      Hatta bu eleştiri, asıl C projelerine aşina olunmadığını gösteriyor

  • C ya da C++ ile birkaç aydan uzun süredir kod yazdıysanız, pointer ile uzunluğu birlikte geçirme yaklaşımı zaten çok iyi bilinen bir şey değil mi?
    Modern C kod tabanlarının neredeyse hepsi eninde sonunda veri pointer’ını ve uzunluğunu birlikte geçirir ya da kendi string kütüphanesini oluşturur

    • Uzunluk bilgisini saklayıp saklamamak, C string’lerinin sorunlarından yalnızca biridir; ömür yönetimi tarafında da çok baş ağrısı vardır
      Modern C++’taki std::string_view, “bu string’e bakabilirsin ama değiştirmemeli ve saklamamalısın” anlamını açıkça ifade ederek bug’ları ciddi ölçüde azaltır
      C string kabul eden API’lerde ise bu tür kısıtlar yalnızca dokümantasyondaki bir sözden ibarettir

  • Asıl hata, uzunluk saklamak ya da null-terminated olmak değil; herhangi bir bağlamda anlamlı olamayacak kadar geniş olan String kavramının kendisi bence
    String’ler basit bir karakter dizisinin ötesinde her türlü amaç için kullanılıyor ve burada “karakter” sözcüğünün kendisi bile, fizikteki vakumda küresel inek şakası gibi, aşırı sadeleştirilmiş kalıyor
    “Uzunluk” denen şeyin grapheme cluster sayısı mı, code point sayısı mı, yoksa toplam byte sayısı mı olduğu baştan belirsiz
    Kodlama nedir, kullanıcıya gösterilip yerelleştirme gerektiriyor mu, sanitize edilmiş mi, map key gibi değiştirilmesi gerekmeyen bölünmez bir değer mi; bunları da ayırmak gerekir
    Bu açıdan bakınca, alışılmış uygulamadaki bir string tipi artık istenir görünmüyor

    • İnsanlar bazen Rust’ta çok fazla string tipi olduğundan şikâyet eder ama bunların bir kısmı tam da bu bilgileri tip sistemine koymak içindir
      Bildiğim kadarıyla hiçbir kütüphane grapheme cluster sayısına basitçe “uzunluk” demez
      Varsayılan kodlamayı UTF-8 yapıp diğer kodlamalar veya byte dizileri için ayrı tipler kullanma geleneğiyle sorunların bir kısmı çözülebilir; geri kalanların çoğu da tip sistemiyle ifade edilebilir

  • Bildiğim kadarıyla C’de, çoğu modern dilin sunduğu anlamda dil düzeyinde bir string kavramı yok
    String işlemleri dilin kendisinde değil, standart kütüphanede sağlanır
    K&R 2. baskı, C’nin karakterler, sayılar ve adresler gibi bilgisayarın doğrudan işlediği nesnelere yakın, görece düşük seviyeli bir dil olduğunu; string, küme, liste ve dizi gibi bileşik nesnelerin tamamını doğrudan işleyen işlemler sunmadığını açıklar
    Bu tür özelliklerin yokluğu büyük bir eksiklik gibi görünebilir, ama dilin küçük tutulması sayesinde kısa biçimde tanımlanabilmesi, hızlı öğrenilebilmesi ve programcının dilin tamamını anlayıp günlük olarak kullanabilmesi gibi avantajlar doğar
    C’nin neden böyle tasarlandığını ve bugün doğal kabul edilen özelliklerin neden bulunmadığını anlamak için K&R 2. baskının önsözünü ve giriş bölümünü okumanızı özellikle tavsiye ederim

    • Yine de string literal’lerin tipi ve bellekteki yerleşimi, kütüphanenin biçimini belirlediği şeklindeki sınırlı anlamda string’ler C dilinin bir parçasıdır
      Bu da Rust gibi düşük seviyeli dillerde dil ile kütüphane arasındaki ayrımdan çok farklı değil

  • Serileştirme biçimi olarak https://cr.yp.to/proto/netstrings.txt gibi öneriler var ve https://web.archive.org/web/20230305073119/… gibi karmaşık yapıları da ele alan yaklaşımlar bulunuyor
    Ama güvenli biçimde parse etmek için fazla basit göründüklerinden olacak ki XML, JSON, YAML, Protocol Buffers vb. ateşli savunucuları hâlâ meşgul kalabiliyor