将不相关的数据存储在指针的最低有效位中可以可靠地工作吗？

Question

让我先说一下，我知道我将要提出的建议是一个致命的罪过，而且我可能会因为考虑它而在编程地狱中被烧死。

也就是说，我仍然有兴趣知道是否有任何原因导致这行不通。

情况是：我有一个引用计数智能指针类，我在任何地方都使用它。它目前看起来像这样（注意：不完整/简化的伪代码）：

class IRefCountable
{
public:
    IRefCountable() : _refCount(0) {}
    virtual ~IRefCountable() {}

    void Ref() {_refCount++;}
    bool Unref() {return (--_refCount==0);}

private:
    unsigned int _refCount;
};

class Ref
{
public:
   Ref(IRefCountable * ptr, bool isObjectOnHeap) : _ptr(ptr), _isObjectOnHeap(isObjectOnHeap) 
   { 
      _ptr->Ref();
   }

   ~Ref() 
   {
      if ((_ptr->Unref())&&(_isObjectOnHeap)) delete _ptr;
   }

private:
   IRefCountable * _ptr;
   bool _isObjectOnHeap;
};

今天我注意到 sizeof(Ref)=16。但是，如果我删除布尔成员变量 _isObjectOnHeap，sizeof(Ref) 将减少到 8。这意味着对于我的程序中的每个 Ref ，浪费了 7.875 字节的 RAM...并且我的程序中有很多很多 Refs。

嗯，这似乎浪费了一些内存。但我真的需要额外的信息（好吧，幽默一下，为了讨论的目的，假设我确实需要）。我注意到，由于 IRefCountable 是一个非 POD 类，因此（大概）它将始终分配在字对齐的内存地址上。因此，(_ptr) 的最低有效位应始终为零。

这让我想知道......有什么原因我不能将我的一位布尔数据或到指针的最低有效位，从而将 sizeof(Ref) 减少一半而不需要牺牲任何功能吗？当然，在取消引用指针之前，我必须小心地对该位进行“与”操作，这会降低指针取消引用的效率，但这可能可以通过引用现在更小，因此引用更多的事实来弥补可以立即放入处理器的缓存中，等等。

这是合理的做法吗？还是我让自己陷入了一个受伤的世界？如果是后者，我到底会受到怎样的伤害呢？ （请注意，这是需要在所有相当现代的桌面环境中正确运行的代码，但它不需要在嵌入式计算机或超级计算机或任何类似的奇特环境中运行）

Answer 1

如果您只想使用标准设施而不依赖于任何实现，那么使用 C++0x 有多种方法可以表达对齐（这里是 最近的问题我回答了）。还有 std::uintptr_t 来可靠地获取足够大以容纳指针的无符号整数类型。现在可以保证的一件事是从指针类型到 std::[u]intptr_t 的转换并返回到相同类型会产生原始指针。

我想你可能会争辩说，如果你能取回原始的 std::intptr_t （带有掩码），那么你就可以获得原始指针。我不知道这个推理有多可靠。

[编辑：考虑一下，不能保证对齐指针在转换为整数类型时采用任何特定形式，例如未设置某些位的指针。这里可能有点牵强]

Answer 2

这里的问题是它完全依赖于机器。这在 C 或 C++ 代码中并不常见，但在汇编中肯定已经做过很多次了。旧的 Lisp 解释器几乎总是使用这个技巧来将类型信息存储在低位中。 （我在 C 代码中看到过它，但在为特定目标平台实现的项目中看到过。）

就我个人而言，如果我尝试编写可移植代码，我可能不会这样做。事实上，它几乎肯定可以在“所有相当现代的桌面环境”上运行。 （当然，它适用于我能想到的每一种。）

很大程度上取决于代码的性质。如果你正在维护它，并且没有其他人需要处理“受伤的世界”，那么它可能没问题。您必须为以后可能需要支持的任何奇怪的架构添加 #ifdef 指令。另一方面，如果您将其作为“可移植”代码发布给全世界，那就会引起人们的关注。

处理这个问题的另一种方法是编写两个版本的智能指针，一个用于可以工作的机器，一个用于不可以工作的机器。这样，只要您维护这两个版本，更改配置文件以使用 16 字节版本就不是什么大问题了。

不用说，您必须避免编写任何其他假设 sizeof(Ref) 为 8 而不是 16 的代码。如果您使用单元测试，请使用两个版本运行它们。

Answer 3

有什么原因吗？除非最近标准发生了变化，否则指针的值表示是实现定义的。当然，某些地方的某些实现可能会采用相同的技巧，为自己的目的定义这些原本未使用的低位。更有可能的是，某些实现可能使用字指针而不是字节指针，因此两个相邻的字不是位于“地址”0x8640 和 0x8642，而是位于“地址”0x4320 和 0x4321。

解决该问题的一个棘手方法是使 Ref 成为（事实上的）抽象类，并且所有实例实际上都是 RefOnHeap 和 RefNotOnHeap 的实例。如果周围有那么多 Ref，则用于存储三个类（而不是一个类）的代码和元数据的额外空间将由每个 Ref 大小减半所节省的空间来弥补。（不起作用）太好了，如果没有虚方法，编译器可以省略 vtable 指针，并且引入虚方法会将 4 或 8 字节添加回类中）。

Answer 4

只要

1. 您不指向对齐为 1 的结构体或数组内的任意位置，或者
2. 平台为您提供了一个空闲位

，那么您始终至少有一个空闲位可以在指针中使用，因为 IRefCountable 的对齐方式为 4，您将在 IRefCountable* 中拥有 2 个可用的底部位来使用。

---

关于第一点，将数据存储在最低有效位中始终是可靠的< em>如果指针是对齐到大于 1 的 2 次方。这意味着它适用于除 char*/bool* 或指向包含以下内容的结构的指针之外的所有内容所有 char/bool 成员，显然它适用于您的情况下的 IRefCountable* 。在 C++11 中，您可以使用 alignof或 std::alignment_of 以确保您有 即使您有一些仅 1 字节对齐

static_assert(alignof(Ref) > 1);
static_assert(alignof(IRefCountable) > 1);

// This check for power of 2 is likely redundant
static_assert((alignof(Ref) & (alignof(Ref) - 1)) == 0);

// Now IRefCountable* is always aligned,
// so its least significant bit can be used freely

的对象，例如，如果您将 IRefCountable 中的 _refCount 更改为 uint8_t ，那么您仍然可以使用 alignas，或与其他旧版 C++ 中的扩展，例如 __declspec(对齐）。动态分配的内存已经与 max_align_t 对齐，或者您可以使用 aligned_alloc() 用于更高级别的对齐

---

我的第二个要点意味着，如果您确实需要存储指向具有绝对 1 字节对齐的对象的任意指针，那么大多数时候您仍然可以利用平台的功能

• 在许多 32 位平台上，地址空间分为用户进程和内核进程的两半。用户指针的最高有效位始终未设置，因此您可以使用它来存储数据。当然，它不能在用户地址空间超过 2GB 的平台上工作，例如当分割为 3/1 或 4/4 时
• 在 64 位平台上，目前大多数只有 48 位虚拟地址，还有一些更新的高虚拟地址-end CPU 可能有 57 位虚拟地址，这与总的 64 位相差甚远。因此，您将有很多空闲空间。实际上，这在个人计算中始终有效，因为您永远无法填充巨大的地址空间，

这称为标记指针

如果数据始终是堆分配的，那么您可以告诉操作系统限制用于获取更多位的地址空间范围

有关更多信息，请阅读 在 64 位指针中使用额外的 16 位

Answer 5

是的，这可以可靠地工作。事实上，Linux 内核将其用作其红黑树实现的一部分。内核没有存储额外的布尔值来指示节点是红色还是黑色（这可能会占用相当多的额外空间），而是使用父节点地址的低位。

来自 rbtree_types.h：

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

__rb_parent_color 字段存储节点父节点的地址和节点的颜色（在最低有效位中）。

获取指针

要从此字段检索父地址，您只需清除低位（这会清除最低 2 位）。

来自rbtree.h：

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

获取布尔值

要检索颜色，您只需提取较低位并将其视为布尔值即可。

来自rbtree_augmented.h：

#define __rb_color(pc)     ((pc) & 1)
#define __rb_is_black(pc)  __rb_color(pc)
#define __rb_is_red(pc)    (!__rb_color(pc))
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)

设置指针和布尔值

您可以使用标准位操作操作设置指针和布尔值（确保保留最终值的每个部分）。

来自 rbtree_augmented.h：

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
    rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}

static inline void rb_set_parent_color(struct rb_node *rb,
                       struct rb_node *p, int color)
{
    rb->__rb_parent_color = (unsigned long)p | color;
}

您还可以通过 (unsigned long)p & 清除布尔值，将其设置为 false ~1。

Answer 6

即使这种方法有效，心中总会有一种不确定性感，因为最终您正在使用的内部架构可能是可移植的，也可能不是可移植的。

另一方面，为了解决这个问题，如果你想避免 bool 变量，我会建议一个简单的构造函数，

Ref(IRefCountable * ptr) : _ptr(ptr) 
{
  if(ptr != 0) 
    _ptr->Ref();
}

从代码中，我闻到引用计数是仅当对象位于堆上时才需要。对于自动对象，您只需将 0 传递给 class Ref 并在构造函数/析构函数中进行适当的 null 检查。

Answer 7

您是否考虑过一流的存储？

根据您是否需要担心多线程并控制 new/delete/malloc/free 的实现，这可能值得一试。

要点是，您将维护一个“计数器”映射地址，而不是递增本地计数器（对象本地）。计数会傲慢地忽略分配区域之外的地址（例如堆栈）。

这可能看起来很愚蠢（MT 中存在争用的空间），但它在只读方面也表现得相当好，因为对象不是仅为了计数而“修改”的。

当然，我不知道您希望通过此实现的性能：p