3. Generische Implementierung eines Tagged Pointers

Generische Implementierung eines Tagged Pointers

  • K

    Hallo Forengemeinde,

    Ich habe mir zu Übungszwecken einen generischen tagged_ptr implementiert. Ich würde gerne wissen, inwieweit sich das mit dem Standard verträgt. Zumindest funktionieren tut es bei mir.

    Hier der Code:

    template <unsigned N>
using unsigned_ = std::integral_constant<unsigned, N>;

template <unsigned N>
using intptr_t_ = std::integral_constant<std::intptr_t, N>;

template <unsigned A, unsigned B>
struct pow
	: unsigned_<A * pow<A, B - 1>::value>
{};

template <unsigned A>
struct pow<A, 0>
	: unsigned_<1>
{};

template <unsigned N>
struct make_bitmask
	: intptr_t_<1 << N - 1 | make_bitmask<N - 1>::value>
{};

template <>
struct make_bitmask<0>
	: intptr_t_<0>
{};

template <typename T, unsigned Bits>
struct tagged_ptr
{
	static_assert(alignof(T) >= pow<2, Bits>::value, "pointers to this type cannot be tagged with this number of bits");

	struct bit_reference
	{
		bit_reference(std::intptr_t& p, std::size_t i) : p(p), i(i) {}

		bit_reference& operator = (bool b)
		{
			p = (p & ~(1 << i)) | (b << i);
			return *this;
		}

		operator bool() const { return p & (1 << i); }

	private:
		std::intptr_t& p;
		std::size_t const i;
	};

	struct const_bit_reference
	{
		const_bit_reference(std::intptr_t const& p, std::size_t i) : p(p), i(i) {}

		operator bool() const { return p & (1 << i); }

	private:
		std::intptr_t const& p;
		std::size_t const i;
	};

	tagged_ptr() : ptr(nullptr) {}
	tagged_ptr(T* ptr) : ptr(ptr) {}

	template <typename U>
	tagged_ptr(tagged_ptr<U, Bits> const& u)
		: ptr(&*u)
	{}

	      bit_reference operator [] (std::size_t i)       { return       bit_reference(int_value(), i); }
	const_bit_reference operator [] (std::size_t i) const { return const_bit_reference(int_value(), i); }

	T& operator *  () const { return *ptr_value(); }
	T* operator -> () const { return  ptr_value(); }

private:
	static std::intptr_t const bitmask = make_bitmask<Bits>::value;

	tagged_ptr const& const_this() const { return *this; }

	std::intptr_t& int_value()
	{
		return const_cast<std::intptr_t&>(const_this().int_value());
	}

	std::intptr_t const& int_value() const
	{
		return reinterpret_cast<std::intptr_t const&>(ptr);
	}

	T* ptr_value() const
	{
		return reinterpret_cast<T*>(int_value() & ~bitmask);
	}

	T* ptr;
};

template <typename OutType, typename InType, unsigned Bits>
tagged_ptr<OutType, Bits> static_tagged_ptr_cast(tagged_ptr<InType, Bits> in)
{
	return tagged_ptr<OutType, Bits>(static_cast<OutType*>(&*in));
}

template <typename OutType, typename InType, unsigned Bits>
tagged_ptr<OutType, Bits> const_tagged_ptr_cast(tagged_ptr<InType, Bits> in)
{
	return tagged_ptr<OutType, Bits>(const_cast<OutType*>(&*in));
}

template <typename OutType, typename InType, unsigned Bits>
tagged_ptr<OutType, Bits> reinterpret_tagged_ptr_cast(tagged_ptr<InType, Bits> in)
{
	return tagged_ptr<OutType, Bits>(reinterpret_cast<OutType*>(&*in));
}

template <typename OutType, typename InType, unsigned Bits>
tagged_ptr<OutType, Bits> dynamic_tagged_ptr_cast(tagged_ptr<InType, Bits> in)
{
	return tagged_ptr<OutType, Bits>(dynamic_cast<OutType*>(&*in));
}

    Ein kleines Testprogramm:

    int main()
{
	int i = 42;

	tagged_ptr<int, 2> p1 = &i;
	p1[0] = true;
	std::cout << p1[0] << '\n';
	std::cout << *p1 << '\n';

	tagged_ptr<int const, 2> const p2 = p1;
	std::cout << p2[0] << '\n';
	std::cout << *p2 << '\n';
}

    Funktionieren tut's, aber ist das korrekt und überall definiertes Verhalten?

    Grüße,
    Der Kellerautomat

    0

  • MMn. ist das nicht standard-konform.
    Du castest da T*& zu intptr_t& und modifizierst dann Bits. Das ist denke ich UB.

    Wenn überhaupt, dann müsste dein tagged_ptr einen intptr_t als Member haben.
    Die Tag-Bits kannst du dann in den intptr_t reinverodern, und dann vor der Rückkonvertierung zu T* wieder rausmaskieren.

    T* ptr_value()
    {
        return reinterpret_cast<T*>(m_ptr_as_int & ~bitmask);
    }

    Wobei ich mir jetzt nicht 100% sicher bin, ob
    a) die Konvertierung T* <-> intptr_t überhaupt garantiert ist und
    b) dabei garantiert ist dass ein Alignment von 2 auch dazu führt dass das LSB des intptr_t immer 0 ist

    Wenn diese zwei Punkte gegeben sind, dann sollte es OK sein.

    0
  • K

    Ich dachte, std::intrptr_t ist doch gerade dazu da, um den Zeiger als int verwenden zu können?
    Und was würde sich ändern, wenn der Member nun ein intptr_t wäre? 😕

    0
  • P

    Kellerautomat schrieb:

    Ich dachte, std::intrptr_t ist doch gerade dazu da, um den Zeiger als int verwenden zu können?

    Ja, aber nicht um Referenzen darauf wild hin- und heracsten zu können.

    Kellerautomat schrieb:

    Und was würde sich ändern, wenn der Member nun ein intptr_t wäre? 😕

    Dass du ohne reinterpret_cast Referenzen darauf zurückgeben kannst. Die Umwandlung in den Pointer ist dann ja sowieso eine Kopie.

    0
  • K

    pumuckl schrieb:

    Ja, aber nicht um Referenzen darauf wild hin- und heracsten zu können.

    Das ist doch dasselbe, nur in Pink. Beispiel:

    T* ptr = ...;
ptr = reinterpret_cast<T*>(reinterpret_cast<intptr_t>(ptr) + 42);

    ist doch gleichwertig mit

    T* ptr = ...;
reinterpret_cast<intptr_t&>(ptr) += 42;

    ... oder etwa nicht?

    0

  • Davon redet ja auch keiner 🙄
    Nochmal lesen...

    0
  • K

    Ich kann euch nicht folgen. Genau das passiert doch bei meinem tagged_ptr:

    T* ptr = reinterpret_cast<T*> /* (1) */ (reinterpret_cast<intptr_t> /* (2) */ (... /* (3) */ ) + 42 /* (4) */);

    (3) ist der Konstruktor. Ein Pointer wird übergeben und gespeichert.
    (4) ist das Rechnen, das geschieht mithilfe der bit_reference im operator[].
    (1) und (2) sind die dafür erforderlichen Casts.

    Das entspricht genau dem Ablauf in meinem tagged_ptr, insofern sehe ich das Problem jetzt nicht.

    0
  • C
    Mod

    Kellerautomat schrieb:

    pumuckl schrieb:

    Ja, aber nicht um Referenzen darauf wild hin- und heracsten zu können.

    Das ist doch dasselbe, nur in Pink. Beispiel:

    T* ptr = ...;
ptr = reinterpret_cast<T*>(reinterpret_cast<intptr_t>(ptr) + 42);

    ist doch gleichwertig mit

    T* ptr = ...;
reinterpret_cast<intptr_t&>(ptr) += 42;

    ... oder etwa nicht?

    Nein. Im ersten Fall konvertierst du Werte, im zweiten Falle behandelst du ein Zeigerobjekt, als ob es ein intptr_t-Objekt wäre. Praktisch wird die häufig zu keinem anderen beobachteten resultat führen, insbesondere im Falle von reinterpret_cast besteht die Konvertierung i.d.R. darin, dass das Bitmuster (value representation) 1:1 in den Wert des anderen Typs übernommen wird (das wird nicht vom Standard ausdrücklich so verlangt, außer dass die Konvertierung "nicht überraschen" sollte). Unter Umständen wird allerdings ein konstanter Ausdruck 0 bzw. ein nullptr anders behandelt.
    Das ist also theoretisch ein Portabilitätsproblem, allerdings vermutlich selten ein praktisches.
    Gleichermaßen würde es mich sehr überraschen, falls tatsächlich eine Implementation existiert, in der in korrekt ausgerichteten Zeigern die niederwertigen Bits nicht 0 sind. Schließlich ist Alignment von vornherein eine Einschränktung die aufgrund der Gegebenheiten konkreter Hardware existiert, und nicht, weil es für die Sprache oder darin geschriebener Programme irgendwie von direktem Nutzen wäre.

    Viel wichtiger ist hier allerdings 3.10/10, d.h. die Regel, dass der in einem Objekt gespeicherte Wert - mit ein paar dort aufgezählten Ausnahmen - immer nur mit einem Ausruck des gleichen Typs ausgelesen werden darf. Hier geht es nicht um Portabilität sondern um Optimierung. Konsequenterweise wird dein Code solange funktionieren, wie du hinschaust, und dir erst dann um die Ohren fliegen, wenn du nicht mehr damit rechnest, das etwas schiefgehen kann.

    hustbaer hat hier schon das richtige Vorgehen beschrieben.

    Nur um es nochmal deutlich zu sagen: die zweite Variante führt hier zwangsläufig zu undefiniertem Verhalten.

    0
  • C
    Mod

    Kellerautomat schrieb:

    Ich kann euch nicht folgen. Genau das passiert doch bei meinem tagged_ptr:

    T* ptr = reinterpret_cast<T*> /* (1) */ (reinterpret_cast<intptr_t> /* (2) */ (... /* (3) */ ) + 42 /* (4) */);

    (3) ist der Konstruktor. Ein Pointer wird übergeben und gespeichert.
    (4) ist das Rechnen, das geschieht mithilfe der bit_reference im operator[].
    (1) und (2) sind die dafür erforderlichen Casts.

    Das entspricht genau dem Ablauf in meinem tagged_ptr, insofern sehe ich das Problem jetzt nicht.

    p = (p & ~(1 << i)) | (b << i);

    p ist ein intptr_t&, das tatsächlich auf ein T*-Objekt (in dem auch ein T*-Wert gespeichert wurde) verweist. Also führt der hier notwendige Lesezugrif zu UB.

    0
  • K

    Alles klar, danke für die Erklärung. 👍

    Somit ist es also okay, wenn der tagged_ptr intern einen intptr_t hält? Ist das Verhalten dann zumindest implementation-defined oder undefined?
    Und wie verträgt sich das mit dem Byte-Order, den hustbär ja schon angesprochen hat? Evtl ein Little/Big-Endian-Switch erforderlich?

    0
  • C
    Mod

    Kellerautomat schrieb:

    Somit ist es also okay, wenn der tagged_ptr intern einen intptr_t hält?

    ja

    Kellerautomat schrieb:

    Ist das Verhalten dann zumindest implementation-defined oder undefined?

    Abgesehen davon, dass die verwendeten Bits frei sein müssen, was der Standard nicht verlangt (man könnte das als conditionally-supported ansehen), gibt es keine Probleme.

    Kellerautomat schrieb:

    Und wie verträgt sich das mit dem Byte-Order, den hustbär ja schon angesprochen hat? Evtl ein Little/Big-Endian-Switch erforderlich?

    Irrelevant, gerade weil Werte direkt konvertiert werden, bist du nicht von einer bestimmten Repräsentation abhängig.
    Lesenswert auch 3.7.4.3.

    Könnte am Ende ungefähr so aussehen

    private:
    template <typename T, typename U>
    static constexpr T implicit_cast(U v) { return v; }

public:
    tagged_ptr() : ptr(0) {}
    tagged_ptr(T* ptr) : data(reinterpret_cast<std::uintptr_t>(ptr)) {}

    template <typename U>
    tagged_ptr(tagged_ptr<U, Bits> const& u)
        : data(reinterpret_cast<std::uintptr_t>(implicit_cast<T*>(u.get())) | u.get_tag())
    {}

    std::uintptr_t get_tag() const { return data & ( ( 1u << Bits ) - 1u ); }
    T* get() const { return reinterpret_cast<T*>( data ^ get_tag()); }

    bit_reference operator [] (std::size_t i) { return       bit_reference(data, i); }
    const_bit operator [] (std::size_t i) const { return const_bit(get_tag() & ( 1u << i ); }

    T& operator *  () const { return *get(); }
    T* operator -> () const { return  get(); }

private:
    std::uintptr_t data;
    0
  • K

    Vielen Dank für die Hilfe 👍

    0
Anmelden zum Antworten