Implement magic references

Magic references are *intentionally* indistinguishable from ordinary
references for the Erlang software. Magic references do not change
the language, and are intended as a pure runtime internal optimization.

An ordinary reference is typically used as a key in some table. A
magic reference has a direct pointer to a reference counted magic
binary. This makes it possible to implement various things without
having to do lookups in a table, but instead access the data directly.
Besides very fast lookups this can also improve scalability by
removing a potentially contended table. A couple of examples of
planned future usage of magic references are ETS table identifiers,
and BIF timer identifiers.

Besides future optimizations using magic references it should also
be possible to replace the exposed magic binary cludge with magic
references. That is, magic binaries that are exposed as empty
binaries to the Erlang software.

1 files changed, 203 insertions, 45 deletions

diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h
index c3234ee349..a602a8f7c6 100644
--- a/erts/emulator/beam/erl_term.h
+++ b/erts/emulator/beam/erl_term.h
@@ -23,6 +23,8 @@
 
 #include "erl_mmap.h"
 
+void erts_term_init(void);
+
 typedef UWord Wterm;  /* Full word terms */
 
 struct erl_node_; /* Declared in erl_node_tables.h */
@@ -718,73 +720,224 @@ _ET_DECLARE_CHECKED(struct erl_node_*,internal_port_node,Eterm)
 #define ERTS_MAX_REF_NUMBERS	3
 #define ERTS_REF_NUMBERS	ERTS_MAX_REF_NUMBERS
 
-#if defined(ARCH_64)
-#  define ERTS_REF_WORDS	(ERTS_REF_NUMBERS/2 + 1)
-#  define ERTS_REF_32BIT_WORDS  (ERTS_REF_NUMBERS+1)
-#else
-#  define ERTS_REF_WORDS	ERTS_REF_NUMBERS
-#  define ERTS_REF_32BIT_WORDS  ERTS_REF_NUMBERS
+#ifndef ERTS_ENDIANNESS
+# error ERTS_ENDIANNESS not defined...
 #endif
 
-typedef struct {
-    Eterm      header;
-    union {
-	Uint32 ui32[ERTS_REF_32BIT_WORDS];
-	Uint   ui[ERTS_REF_WORDS];
-    } data;
-} RefThing;
-
-#define REF_THING_SIZE (sizeof(RefThing)/sizeof(Uint))
-#define REF_THING_HEAD_SIZE (sizeof(Eterm)/sizeof(Uint))
+#if ERTS_REF_NUMBERS != 3
+#  error "A new reference layout for 64-bit needs to be implemented..."
+#endif
 
-#define make_ref_thing_header(DW) \
-  _make_header((DW)+REF_THING_HEAD_SIZE-1,_TAG_HEADER_REF)
+struct magic_binary;
 
 #if defined(ARCH_64)
 
+# define ERTS_ORDINARY_REF_MARKER (~((Uint32) 0))
+
+typedef struct {
+    Eterm header;
+#if ERTS_ENDIANNESS <= 0
+    Uint32 marker;
+#endif
+    Uint32 num[ERTS_REF_NUMBERS];
+#if ERTS_ENDIANNESS > 0
+    Uint32 marker;
+#endif
+} ErtsORefThing;
+
+typedef struct {
+    Eterm header;
+    struct magic_binary *mb;
+    struct erl_off_heap_header* next;
+#if !ERTS_ENDIANNESS
+    Uint32 num[ERTS_REF_NUMBERS];
+    Uint32 marker;
+#endif
+} ErtsMRefThing;
+
 /*
- * Ref layout on a 64-bit little endian machine:
+ * Ordinary ref layout on a 64-bit little endian machine:
  *
  * 63             31             0
  * +--------------+--------------+
  * |         Thing word          |
  * +--------------+--------------+
- * |  Data 0      | 32-bit arity |
+ * |  Data 0      | 0xffffffff   |
  * +--------------+--------------+
  * |  Data 2      | Data 1       |
  * +--------------+--------------+
  *
- * Data is stored as an Uint32 array with 32-bit arity as first number.
+ * Ordinary ref layout on a 64-bit big endian machine:
+ *
+ * 63             31             0
+ * +--------------+--------------+
+ * |         Thing word          |
+ * +--------------+--------------+
+ * |  Data 0      | Data 1       |
+ * +--------------+--------------+
+ * |  Data 2      | 0xffffffff   |
+ * +--------------+--------------+
+ *
+ * Magic Ref layout on a 64-bit machine:
+ *
+ * 63             31             0
+ * +--------------+--------------+
+ * |         Thing word          |
+ * +--------------+--------------+
+ * |  Magic Binary Pointer       |
+ * +--------------+--------------+
+ * |  Next Off Heap Pointer      |
+ * +--------------+--------------+
+ *
+ * Both pointers in the magic ref are 64-bit aligned. That is,
+ * least significant bits are zero. The marker 32-bit word is
+ * placed over the least significant bits of one of the pointers.
+ * That is, we can distinguish between magic and ordinary ref
+ * by looking at the marker field.
+ * 
  */
 
 #define write_ref_thing(Hp, R0, R1, R2)					\
 do {									\
-  ((RefThing *) (Hp))->header  = make_ref_thing_header(ERTS_REF_WORDS);	\
-  ((RefThing *) (Hp))->data.ui32[0] = ERTS_REF_NUMBERS;			\
-  ((RefThing *) (Hp))->data.ui32[1] = (R0);				\
-  ((RefThing *) (Hp))->data.ui32[2] = (R1);				\
-  ((RefThing *) (Hp))->data.ui32[3] = (R2);				\
+  ((ErtsORefThing *) (Hp))->header = ERTS_REF_THING_HEADER;		\
+  ((ErtsORefThing *) (Hp))->marker = ERTS_ORDINARY_REF_MARKER;		\
+  ((ErtsORefThing *) (Hp))->num[0] = (R0);				\
+  ((ErtsORefThing *) (Hp))->num[1] = (R1);				\
+  ((ErtsORefThing *) (Hp))->num[2] = (R2);				\
 } while (0)
 
-#else
+#if ERTS_ENDIANNESS
+/* Known big or little endian */
+
+#define write_magic_ref_thing(Hp, Ohp, Binp)				\
+do {									\
+  ((ErtsMRefThing *) (Hp))->header = ERTS_REF_THING_HEADER;		\
+  ((ErtsMRefThing *) (Hp))->mb = (Binp);				\
+  ((ErtsMRefThing *) (Hp))->next = (Ohp)->first;			\
+  (Ohp)->first = (struct erl_off_heap_header*) (Hp);			\
+  ASSERT(erts_is_ref_numbers_magic((Binp)->refn));			\
+} while (0)
+
+#else /* !ERTS_ENDIANNESS */
+
+#define write_magic_ref_thing(Hp, Ohp, Binp)				\
+do {									\
+  ((ErtsMRefThing *) (Hp))->header = ERTS_MAGIC_REF_THING_HEADER;	\
+  ((ErtsMRefThing *) (Hp))->mb = (Binp);				\
+  ((ErtsMRefThing *) (Hp))->next = (Ohp)->first;			\
+  (Ohp)->first = (struct erl_off_heap_header*) (Hp);			\
+  ((ErtsMRefThing *) (Hp))->marker = 0;					\
+  ((ErtsMRefThing *) (Hp))->num[0] = (Binp)->refn[0];			\
+  ((ErtsMRefThing *) (Hp))->num[1] = (Binp)->refn[1];			\
+  ((ErtsMRefThing *) (Hp))->num[2] = (Binp)->refn[2];			\
+  ASSERT(erts_is_ref_numbers_magic((Binp)->refn));			\
+} while (0)
+
+#endif /* !ERTS_ENDIANNESS */
+
+#else /* ARCH_32 */
+
+typedef struct {
+    Eterm header;
+    Uint32 num[ERTS_REF_NUMBERS];
+} ErtsORefThing;
+
+typedef struct {
+    Eterm header;
+    struct magic_binary *mb;
+    struct erl_off_heap_header* next;
+} ErtsMRefThing;
+
 
 #define write_ref_thing(Hp, R0, R1, R2)					\
 do {									\
-  ((RefThing *) (Hp))->header  = make_ref_thing_header(ERTS_REF_WORDS);	\
-  ((RefThing *) (Hp))->data.ui32[0] = (R0);				\
-  ((RefThing *) (Hp))->data.ui32[1] = (R1);				\
-  ((RefThing *) (Hp))->data.ui32[2] = (R2);				\
+  ((ErtsORefThing *) (Hp))->header = ERTS_REF_THING_HEADER;		\
+  ((ErtsORefThing *) (Hp))->num[0] = (R0);				\
+  ((ErtsORefThing *) (Hp))->num[1] = (R1);				\
+  ((ErtsORefThing *) (Hp))->num[2] = (R2);				\
 } while (0)
 
+#define write_magic_ref_thing(Hp, Ohp, Binp)				\
+do {									\
+  ((ErtsMRefThing *) (Hp))->header = ERTS_MAGIC_REF_THING_HEADER;	\
+  ((ErtsMRefThing *) (Hp))->mb = (Binp);				\
+  ((ErtsMRefThing *) (Hp))->next = (Ohp)->first;			\
+  (Ohp)->first = (struct erl_off_heap_header*) (Hp);			\
+  ASSERT(erts_is_ref_numbers_magic(&(Binp)->refn));			\
+} while (0)
+
+#endif /* ARCH_32 */
+
+typedef union {
+    ErtsMRefThing m;
+    ErtsORefThing o;
+} ErtsRefThing;
+
+#define ERTS_REF_THING_SIZE (sizeof(ErtsORefThing)/sizeof(Uint))
+#define ERTS_MAGIC_REF_THING_SIZE (sizeof(ErtsMRefThing)/sizeof(Uint))
+#define ERTS_MAX_INTERNAL_REF_SIZE (sizeof(ErtsRefThing)/sizeof(Uint))
+
+#define make_ref_thing_header(Words) \
+    _make_header((Words)-1,_TAG_HEADER_REF)
+
+#define ERTS_REF_THING_HEADER _make_header(ERTS_REF_THING_SIZE-1,_TAG_HEADER_REF)
+
+#if defined(ARCH_64) && ERTS_ENDIANNESS /* All internal refs of same size... */
+
+#  undef ERTS_MAGIC_REF_THING_HEADER
+
+#  define is_ref_thing_header(x) ((x) == ERTS_REF_THING_HEADER)
+
+#define is_ordinary_ref_thing(x)					\
+    (ASSERT(is_ref_thing_header(*((Eterm *)(x)))),			\
+     ((ErtsRefThing *) (x))->o.marker == ERTS_ORDINARY_REF_MARKER)
+
+#define is_magic_ref_thing(x)						\
+    (!is_ordinary_ref_thing((x)))
+
+#define is_internal_magic_ref(x)					\
+    ((_unchecked_is_boxed((x)) && *boxed_val((x)) == ERTS_REF_THING_HEADER) \
+     && is_magic_ref_thing(boxed_val((x))))
+
+#define is_internal_ordinary_ref(x)					\
+    ((_unchecked_is_boxed((x)) && *boxed_val((x)) == ERTS_REF_THING_HEADER) \
+     && is_ordinary_ref_thing(boxed_val((x))))
+
+#else /* Ordinary and magic references of different sizes... */
+
+#  define ERTS_MAGIC_REF_THING_HEADER					\
+    _make_header(ERTS_MAGIC_REF_THING_SIZE-1,_TAG_HEADER_REF)
+
+#  define is_ref_thing_header(x)					\
+    (((x) & _TAG_HEADER_MASK) == _TAG_HEADER_REF)
+
+#define is_ordinary_ref_thing(x)					\
+    (ASSERT(is_ref_thing_header(*((Eterm *)(x)))),			\
+     *((Eterm *)(x)) == ERTS_REF_THING_HEADER)
+
+#define is_magic_ref_thing(x)						\
+    (ASSERT(is_ref_thing_header(*((Eterm *)(x)))),			\
+     *((Eterm *)(x)) == ERTS_MAGIC_REF_THING_HEADER)
+
+#define is_internal_magic_ref(x)					\
+    (_unchecked_is_boxed((x)) && *boxed_val((x)) == ERTS_MAGIC_REF_THING_HEADER)
+
+#define is_internal_ordinary_ref(x)					\
+    (_unchecked_is_boxed((x)) && *boxed_val((x)) == ERTS_REF_THING_HEADER)
+
 #endif
 
-#define is_ref_thing_header(x)	(((x) & _TAG_HEADER_MASK) == _TAG_HEADER_REF)
 #define make_internal_ref(x)	make_boxed((Eterm*)(x))
 
-#define _unchecked_ref_thing_ptr(x) \
-  ((RefThing*) _unchecked_internal_ref_val(x))
-#define ref_thing_ptr(x) \
-  ((RefThing*) internal_ref_val(x))
+#define _unchecked_ordinary_ref_thing_ptr(x) \
+  ((ErtsORefThing*) _unchecked_internal_ref_val(x))
+#define ordinary_ref_thing_ptr(x) \
+  ((ErtsORefThing*) internal_ref_val(x))
+
+#define _unchecked_magic_ref_thing_ptr(x) \
+  ((ErtsMRefThing*) _unchecked_internal_ref_val(x))
+#define magic_ref_thing_ptr(x) \
+  ((ErtsMRefThing*) internal_ref_val(x))
 
 #define is_internal_ref(x) \
     (_unchecked_is_boxed((x)) && is_ref_thing_header(*boxed_val((x))))
@@ -796,16 +949,21 @@ do {									\
 _ET_DECLARE_CHECKED(Eterm*,internal_ref_val,Wterm)
 #define internal_ref_val(x) _ET_APPLY(internal_ref_val,(x))
 
-#define internal_thing_ref_data_words(t) (thing_arityval(*(Eterm*)(t)))
-#define _unchecked_internal_ref_data_words(x) \
- (_unchecked_thing_arityval(*_unchecked_internal_ref_val(x)))
-_ET_DECLARE_CHECKED(Uint,internal_ref_data_words,Wterm)
-#define internal_ref_data_words(x) _ET_APPLY(internal_ref_data_words,(x))
+#define internal_ordinary_thing_ref_numbers(ort) (((ErtsORefThing *)(ort))->num)
+#define _unchecked_internal_ordinary_ref_numbers(x) (internal_ordinary_thing_ref_numbers(_unchecked_ordinary_ref_thing_ptr(x)))
+_ET_DECLARE_CHECKED(Uint32*,internal_ordinary_ref_numbers,Wterm)
+#define internal_ordinary_ref_numbers(x) _ET_APPLY(internal_ordinary_ref_numbers,(x))
+
+#if defined(ARCH_64) && !ERTS_ENDIANNESS
+#define internal_magic_thing_ref_numbers(mrt) (((ErtsMRefThing *)(mrt))->num)
+#else
+#define internal_magic_thing_ref_numbers(mrt) (((ErtsMRefThing *)(mrt))->mb->refn)
+#endif
+
+#define _unchecked_internal_magic_ref_numbers(x) (internal_magic_thing_ref_numbers(_unchecked_magic_ref_thing_ptr(x)))
+_ET_DECLARE_CHECKED(Uint32*,internal_magic_ref_numbers,Wterm)
+#define internal_magic_ref_numbers(x) _ET_APPLY(internal_magic_ref_numbers,(x))
 
-#define internal_thing_ref_data(thing) ((thing)->data.ui32)
-#define _unchecked_internal_ref_data(x) (internal_thing_ref_data(_unchecked_ref_thing_ptr(x)))
-_ET_DECLARE_CHECKED(Uint32*,internal_ref_data,Wterm)
-#define internal_ref_data(x) _ET_APPLY(internal_ref_data,(x))
 
 #define _unchecked_internal_ref_node(x) erts_this_node
 _ET_DECLARE_CHECKED(struct erl_node_*,internal_ref_node,Eterm)