Czy C ma odpowiednik std :: less z C ++?

26

Byłem niedawno w odpowiedzi na pytanie o niezdefiniowanej zachowań robi p < qw C kiedy pi qsą wskaźnikami język różnych obiektów / tablic. To sprawiło, że pomyślałem: C ++ ma takie samo (niezdefiniowane) zachowanie <w tym przypadku, ale oferuje również standardowy szablon biblioteki, std::lessktóry gwarantuje, że zwróci to samo, co w <przypadku porównania wskaźników, i zwróci pewne spójne uporządkowanie, gdy nie będą w stanie.

Czy C oferuje coś o podobnej funkcjonalności, która pozwoliłaby bezpiecznie porównywać dowolne wskaźniki (z tym samym typem)? Próbowałem przejrzeć standard C11 i nic nie znalazłem, ale moje doświadczenie w C jest o rząd wielkości mniejsze niż w C ++, więc mogłem łatwo coś przeoczyć.

Angew nie jest już dumny z SO
źródło
1
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Samuel Liew

Odpowiedzi:

20

W implementacjach z płaskim modelem pamięci (w zasadzie wszystko), rzutowanie na uintptr_tJust Work.

(Ale zobacz, czy porównania wskaźników powinny być podpisane czy niepodpisane w 64-bitowym x86 ?, aby dowiedzieć się, czy powinieneś traktować wskaźniki jako podpisane, czy nie, w tym kwestie dotyczące tworzenia wskaźników poza obiektami, które są UB w C.)

Ale systemy z non-płaskich modeli pamięci istnieją, i myślenie o nich może pomóc wyjaśnić obecną sytuację, jak C ++ posiadające różne specyfikacje dla <vs. std::less.


Częścią <wskazówek na temat oddzielania obiektów będących UB w C (lub przynajmniej nieokreślonych w niektórych wersjach C ++) jest umożliwienie dziwnych maszyn, w tym niepłaskich modeli pamięci.

Dobrze znanym przykładem jest tryb rzeczywisty x86-16, w którym wskaźniki są segmentowe: przesunięte, tworząc 20-bitowy adres liniowy za pośrednictwem (segment << 4) + offset. Ten sam adres liniowy może być reprezentowany przez wiele różnych kombinacji seg: off.

C ++ std::lessna wskaźniki na dziwnych ISA może być kosztowne , np. „Normalizacja” segmentu: przesunięcie na x86-16, aby mieć przesunięcie <= 15. Jednak nie ma przenośnego sposobu na wdrożenie tego. Manipulacja wymagana do normalizacji uintptr_t(lub reprezentacji obiektowej obiektu wskaźnika) jest specyficzna dla implementacji.

Ale nawet w systemach, w których C ++ std::lessmusi być drogie, <nie musi tak być. Na przykład, zakładając „duży” model pamięci, w którym obiekt mieści się w jednym segmencie, <można po prostu porównać część przesuniętą, a nawet nie zawracać sobie głowy częścią segmentu. (Wskaźniki wewnątrz tego samego obiektu będą miały ten sam segment, w przeciwnym razie UB w C. C ++ 17 zmieniono na „nieokreślony”, co może nadal pozwalać na pominięcie normalizacji i porównywanie przesunięć.) Zakłada się, że wszystkie wskaźniki w dowolnej części obiektu zawsze używa tej samej segwartości, nigdy się nie normalizuje. Tego można oczekiwać od ABI w przypadku „dużej”, w przeciwieństwie do „ogromnego” modelu pamięci. (Patrz dyskusja w komentarzach ).

(Taki model pamięci może mieć na przykład maksymalny rozmiar obiektu 64 kB, ale znacznie większą maksymalną całkowitą przestrzeń adresową, która ma miejsce na wiele takich obiektów o maksymalnej wielkości. ISO C pozwala implementacjom na ograniczenie wielkości obiektu, która jest mniejsza niż maksymalna wartość (bez znaku) size_tmoże reprezentować, SIZE_MAXnp. nawet w systemach z płaską pamięcią, GNU C ogranicza maksymalny rozmiar obiektu, aby PTRDIFF_MAXobliczenia rozmiaru mogły zignorować przepełnienie podpisu.) Zobacz tę odpowiedź i dyskusję w komentarzach.

Jeśli chcesz pozwolić obiektom większym niż segment, potrzebujesz „ogromnego” modelu pamięci, który musi się martwić o przepełnienie części przesunięcia wskaźnika podczas wykonywania p++pętli przez tablicę lub podczas wykonywania operacji arytmetycznych na indeksach / wskaźnikach. Powoduje to wszędzie wolniejszy kod, ale prawdopodobnie oznaczałoby to, p < qże działałoby w przypadku wskaźników do różnych obiektów, ponieważ implementacja ukierunkowana na „ogromny” model pamięci normalnie wybrałaby utrzymanie normalizacji wszystkich wskaźników. Zobacz, jakie są bliskie, dalekie i ogromne wskaźniki? - niektóre prawdziwe kompilatory C dla trybu rzeczywistego x86 miały opcję kompilacji dla modelu „ogromnego”, w którym wszystkie wskaźniki domyślnie były ustawione na „ogromne”, chyba że podano inaczej.

Segmentacja w trybie rzeczywistym x86 nie jest jedynym możliwym niepłaskim modelem pamięci , jest jedynie użytecznym konkretnym przykładem ilustrującym sposób, w jaki są obsługiwane przez implementacje C / C ++. W rzeczywistości implementacje rozszerzyły ISO C o koncepcję farvs. nearwskaźników, umożliwiając programistom wybór, kiedy mogą uciec po prostu zapisując / omijając 16-bitową część przesunięcia względem niektórych wspólnych segmentów danych.

Ale czysta implementacja ISO C musiałaby wybierać między małym modelem pamięci (wszystko oprócz kodu w tym samym 64 kB z 16-bitowymi wskaźnikami) lub dużym lub dużym, a wszystkie wskaźniki były 32-bitowe. Niektóre pętle można zoptymalizować, zwiększając tylko część odsuniętą, ale obiektów wskaźnikowych nie można zoptymalizować, aby były mniejsze.


Gdybyś wiedział, co magia manipulacja była dla danej realizacji, można wdrożyć go w czystym C . Problem polega na tym, że różne systemy używają różnych adresów, a szczegóły nie są parametryzowane przez żadne przenośne makra.

A może nie: może to obejmować wyszukiwanie czegoś ze specjalnej tablicy segmentów lub czegoś takiego, np. Tryb chroniony x86 zamiast trybu rzeczywistego, w którym częścią segmentu adresu jest indeks, a nie wartość, którą należy przesunąć w lewo. Można ustawić częściowo nakładające się segmenty w trybie chronionym, a części selektora segmentów adresów niekoniecznie będą nawet uporządkowane w tej samej kolejności, co odpowiadające im adresy podstawowe segmentów. Uzyskiwanie adresu liniowego ze wskaźnika seg: off w trybie chronionym x86 może wymagać wywołania systemowego, jeśli GDT i / lub LDT nie zostaną zmapowane na czytelne strony w twoim procesie.

(Oczywiście główne systemy operacyjne dla x86 używają płaskiego modelu pamięci, więc podstawa segmentu jest zawsze równa 0 (z wyjątkiem lokalnego przechowywania wątków przy użyciu fslub gssegmentów), a tylko 32-bitowa lub 64-bitowa część „przesunięcia” jest używana jako wskaźnik .)

Możesz ręcznie dodać kod dla różnych konkretnych platform, np. Domyślnie załóż płaskie lub #ifdefcoś w celu wykrycia trybu rzeczywistego x86 i podziel uintptr_tna 16-bitowe połówki, seg -= off>>4; off &= 0xf;a następnie połącz te części z powrotem w 32-bitową liczbę.

Peter Cordes
źródło
Dlaczego miałby być UB, jeśli segment nie jest równy?
Acorn
@Acorn: Chcę powiedzieć, że na odwrót; naprawiony. wskaźniki do tego samego obiektu będą miały ten sam segment, w przeciwnym razie UB.
Peter Cordes,
Ale dlaczego uważasz, że w każdym razie jest to UB? (odwrócona logika czy nie, właściwie ja też tego nie zauważyłem)
Acorn
p < qjest UB w C, jeśli wskazują na różne obiekty, prawda? Wiem że p - qjest.
Peter Cordes,
1
@Acorn: W każdym razie nie widzę mechanizmu, który generowałby aliasy (inny seg: off, ten sam adres liniowy) w programie bez UB. Więc to nie jest tak, że kompilator musi zrobić wszystko, aby tego uniknąć; każdy dostęp do obiektu wykorzystuje segwartość tego obiektu i przesunięcie, które> = przesunięcie w segmencie, w którym zaczyna się ten obiekt. C sprawia, że ​​UB robi wiele czegokolwiek pomiędzy wskaźnikami do różnych obiektów, włączając w to takie jak, tmp = a-ba następnie b[tmp]dostęp a[0]. Ta dyskusja na temat segmentowego aliasingu wskaźnika jest dobrym przykładem tego, dlaczego ten wybór projektu ma sens.
Peter Cordes,
17

I raz próbowali znaleźć sposób na obejście tego i znalazłem rozwiązanie, które umożliwia dostęp na nakładających się obiektów i w większości innych przypadków Zakładając, że kompilator robi to „zwykłe” rzeczy.

Możesz najpierw zaimplementować sugestię w Jak zaimplementować memmove w standardowym C bez kopii pośredniej? a następnie, jeśli to nie zadziała, rzutuj na uintptr(typ opakowania dla jednego uintptr_tlub w unsigned long longzależności od tego, czy uintptr_tjest dostępny) i uzyskaj najbardziej prawdopodobny dokładny wynik (chociaż i tak prawdopodobnie nie miałoby to znaczenia):

#include <stdint.h>
#ifndef UINTPTR_MAX
typedef unsigned long long uintptr;
#else
typedef uintptr_t uintptr;
#endif

int pcmp(const void *p1, const void *p2, size_t len)
{
    const unsigned char *s1 = p1;
    const unsigned char *s2 = p2;
    size_t l;

    /* Check for overlap */
    for( l = 0; l < len; l++ )
    {
        if( s1 + l == s2 || s1 + l == s2 + len - 1 )
        {
            /* The two objects overlap, so we're allowed to
               use comparison operators. */
            if(s1 > s2)
                return 1;
            else if (s1 < s2)
                return -1;
            else
                return 0;
        }
    }

    /* No overlap so the result probably won't really matter.
       Cast the result to `uintptr` and hope the compiler
       does the "usual" thing */
    if((uintptr)s1 > (uintptr)s2)
        return 1;
    else if ((uintptr)s1 < (uintptr)s2)
        return -1;
    else
        return 0;
}
SS Anne
źródło
5

Czy C oferuje coś o podobnej funkcjonalności, która pozwoliłaby bezpiecznie porównywać dowolne wskaźniki.

Nie


Najpierw rozważmy tylko wskaźniki obiektów . Wskaźniki funkcji budzą zupełnie inne obawy.

2 wskaźniki p1, p2mogą mieć różne kodowania i wskazują ten sam adres, więc p1 == p2nawet jeśli memcmp(&p1, &p2, sizeof p1)nie jest to 0. Takie architektury są rzadkie.

Jednak konwersja tych wskaźników na uintptr_tnie wymaga tego samego wyniku liczb całkowitych prowadzącego do (uintptr_t)p1 != (uinptr_t)p2.

(uintptr_t)p1 < (uinptr_t)p2 sam w sobie jest legalnym kodem, ponieważ może nie zapewnić oczekiwanej funkcjonalności.


Jeśli kod naprawdę musi porównywać niepowiązane wskaźniki, utwórz funkcję pomocniczą less(const void *p1, const void *p2)i wykonaj tam specyficzny dla platformy kod.

Być może:

// return -1,0,1 for <,==,> 
int ptrcmp(const void *c1, const void *c1) {
  // Equivalence test works on all platforms
  if (c1 == c2) {
    return 0;
  }
  // At this point, we know pointers are not equivalent.
  #ifdef UINTPTR_MAX
    uintptr_t u1 = (uintptr_t)c1;
    uintptr_t u2 = (uintptr_t)c2;
    // Below code "works" in that the computation is legal,
    //   but does it function as desired?
    // Likely, but strange systems lurk out in the wild. 
    // Check implementation before using
    #if tbd
      return (u1 > u2) - (u1 < u2);
    #else
      #error TBD code
    #endif
  #else
    #error TBD code
  #endif 
}
chux - Przywróć Monikę
źródło