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, 151 insertions, 8 deletions

diff --git a/erts/emulator/beam/erl_binary.h b/erts/emulator/beam/erl_binary.h
index fdc5efea98..c811a002ce 100644
--- a/erts/emulator/beam/erl_binary.h
+++ b/erts/emulator/beam/erl_binary.h
@@ -18,11 +18,146 @@
  * %CopyrightEnd%
  */
 
-#ifndef __ERL_BINARY_H
-#define __ERL_BINARY_H
+#ifndef ERL_BINARY_H__TYPES__
+#define ERL_BINARY_H__TYPES__
+
+/*
+** Just like the driver binary but with initial flags
+** Note that the two structures Binary and ErlDrvBinary HAVE to
+** be equal except for extra fields in the beginning of the struct.
+** ErlDrvBinary is defined in erl_driver.h.
+** When driver_alloc_binary is called, a Binary is allocated, but 
+** the pointer returned is to the address of the first element that
+** also occurs in the ErlDrvBinary struct (driver.*binary takes care if this).
+** The driver need never know about additions to the internal Binary of the
+** emulator. One should however NEVER be sloppy when mixing ErlDrvBinary
+** and Binary, the macros below can convert one type to the other, as they both
+** in reality are equal.
+*/
+
+#ifdef ARCH_32
+ /* *DO NOT USE* only for alignment. */
+#define ERTS_BINARY_STRUCT_ALIGNMENT Uint32 align__;
+#else
+#define ERTS_BINARY_STRUCT_ALIGNMENT
+#endif
+
+/* Add fields in ERTS_INTERNAL_BINARY_FIELDS, otherwise the drivers crash */
+#define ERTS_INTERNAL_BINARY_FIELDS				\
+    UWord flags;						\
+    erts_refc_t refc;						\
+    ERTS_BINARY_STRUCT_ALIGNMENT
+
+typedef struct binary {
+    ERTS_INTERNAL_BINARY_FIELDS
+    SWord orig_size;
+    char orig_bytes[1]; /* to be continued */
+} Binary;
+
+#define ERTS_SIZEOF_Binary(Sz) \
+    (offsetof(Binary,orig_bytes) + (Sz))
+
+#if ERTS_REF_NUMBERS != 3
+#error "Update ErtsMagicBinary"
+#endif
+
+typedef struct magic_binary ErtsMagicBinary;
+struct magic_binary {
+    ERTS_INTERNAL_BINARY_FIELDS
+    SWord orig_size;
+    void (*destructor)(Binary *);
+    Uint32 refn[ERTS_REF_NUMBERS];
+    ErtsAlcType_t alloc_type;
+    union {
+        struct {
+            ERTS_BINARY_STRUCT_ALIGNMENT
+            char data[1];
+        } aligned;
+        struct {
+            char data[1];
+        } unaligned;
+    } u;
+};
+
+#ifdef ARCH_32
+#define ERTS_MAGIC_BIN_BYTES_TO_ALIGN 4
+#else
+#define ERTS_MAGIC_BIN_BYTES_TO_ALIGN 0
+#endif
+
+typedef union {
+    Binary binary;
+    ErtsMagicBinary magic_binary;
+    struct {
+	ERTS_INTERNAL_BINARY_FIELDS
+	ErlDrvBinary binary;
+    } driver;
+} ErtsBinary;
+
+/*
+ * 'Binary' alignment:
+ *   Address of orig_bytes[0] of a Binary should always be 8-byte aligned.
+ * It is assumed that the flags, refc, and orig_size fields are 4 bytes on
+ * 32-bits architectures and 8 bytes on 64-bits architectures.
+ */
+
+#define ERTS_MAGIC_BIN_REFN(BP) \
+  ((ErtsBinary *) (BP))->magic_binary.refn
+#define ERTS_MAGIC_BIN_ATYPE(BP) \
+  ((ErtsBinary *) (BP))->magic_binary.alloc_type
+#define ERTS_MAGIC_DATA_OFFSET \
+  (offsetof(ErtsMagicBinary,u.aligned.data) - offsetof(Binary,orig_bytes))
+#define ERTS_MAGIC_BIN_DESTRUCTOR(BP) \
+  ((ErtsBinary *) (BP))->magic_binary.destructor
+#define ERTS_MAGIC_BIN_DATA(BP) \
+  ((void *) ((ErtsBinary *) (BP))->magic_binary.u.aligned.data)
+#define ERTS_MAGIC_BIN_DATA_SIZE(BP) \
+  ((BP)->orig_size - ERTS_MAGIC_DATA_OFFSET)
+#define ERTS_MAGIC_DATA_OFFSET \
+  (offsetof(ErtsMagicBinary,u.aligned.data) - offsetof(Binary,orig_bytes))
+#define ERTS_MAGIC_BIN_ORIG_SIZE(Sz) \
+  (ERTS_MAGIC_DATA_OFFSET + (Sz))
+#define ERTS_MAGIC_BIN_SIZE(Sz) \
+  (offsetof(ErtsMagicBinary,u.aligned.data) + (Sz))
+#define ERTS_MAGIC_BIN_FROM_DATA(DATA) \
+  ((ErtsBinary*)((char*)(DATA) - offsetof(ErtsMagicBinary,u.aligned.data)))
+
+/* On 32-bit arch these macro variants will save memory
+   by not forcing 8-byte alignment for the magic payload.
+*/
+#define ERTS_MAGIC_BIN_UNALIGNED_DATA(BP) \
+  ((void *) ((ErtsBinary *) (BP))->magic_binary.u.unaligned.data)
+#define ERTS_MAGIC_UNALIGNED_DATA_OFFSET \
+  (offsetof(ErtsMagicBinary,u.unaligned.data) - offsetof(Binary,orig_bytes))
+#define ERTS_MAGIC_BIN_UNALIGNED_DATA_SIZE(BP) \
+  ((BP)->orig_size - ERTS_MAGIC_UNALIGNED_DATA_OFFSET)
+#define ERTS_MAGIC_BIN_UNALIGNED_ORIG_SIZE(Sz) \
+  (ERTS_MAGIC_UNALIGNED_DATA_OFFSET + (Sz))
+#define ERTS_MAGIC_BIN_UNALIGNED_SIZE(Sz) \
+  (offsetof(ErtsMagicBinary,u.unaligned.data) + (Sz))
+#define ERTS_MAGIC_BIN_FROM_UNALIGNED_DATA(DATA) \
+  ((ErtsBinary*)((char*)(DATA) - offsetof(ErtsMagicBinary,u.unaligned.data)))
+
+
+#define Binary2ErlDrvBinary(B) (&((ErtsBinary *) (B))->driver.binary)
+#define ErlDrvBinary2Binary(D) ((Binary *) \
+				(((char *) (D)) \
+				 - offsetof(ErtsBinary, driver.binary)))
+
+/* A "magic" binary flag */
+#define BIN_FLAG_MAGIC      1
+#define BIN_FLAG_USR1       2 /* Reserved for use by different modules too mark */
+#define BIN_FLAG_USR2       4 /*  certain binaries as special (used by ets) */
+#define BIN_FLAG_DRV        8
+
+#endif /* ERL_BINARY_H__TYPES__ */
+
+#if !defined(ERL_BINARY_H__) && !defined(ERTS_BINARY_TYPES_ONLY__)
+#define ERL_BINARY_H__
 
 #include "erl_threads.h"
 #include "bif.h"
+#include "erl_bif_unique.h"
 
 /*
  * Maximum number of bytes to place in a heap binary.
@@ -190,6 +325,7 @@ ERTS_GLB_INLINE Binary *erts_bin_realloc(Binary *bp, Uint size);
 ERTS_GLB_INLINE void erts_bin_free(Binary *bp);
 ERTS_GLB_INLINE Binary *erts_create_magic_binary_x(Uint size,
                                                   void (*destructor)(Binary *),
+                                                   ErtsAlcType_t alloc_type,
                                                   int unaligned);
 ERTS_GLB_INLINE Binary *erts_create_magic_binary(Uint size,
 						 void (*destructor)(Binary *));
@@ -320,9 +456,12 @@ erts_bin_realloc(Binary *bp, Uint size)
 ERTS_GLB_INLINE void
 erts_bin_free(Binary *bp)
 {
-    if (bp->flags & BIN_FLAG_MAGIC)
+    if (bp->flags & BIN_FLAG_MAGIC) {
 	ERTS_MAGIC_BIN_DESTRUCTOR(bp)(bp);
-    if (bp->flags & BIN_FLAG_DRV)
+	erts_magic_ref_remove_bin(ERTS_MAGIC_BIN_REFN(bp));
+        erts_free(ERTS_MAGIC_BIN_ATYPE(bp), (void *) bp);
+    }
+    else if (bp->flags & BIN_FLAG_DRV)
 	erts_free(ERTS_ALC_T_DRV_BINARY, (void *) bp);
     else
 	erts_free(ERTS_ALC_T_BINARY, (void *) bp);
@@ -330,29 +469,33 @@ erts_bin_free(Binary *bp)
 
 ERTS_GLB_INLINE Binary *
 erts_create_magic_binary_x(Uint size, void (*destructor)(Binary *),
+                           ErtsAlcType_t alloc_type,
                            int unaligned)
 {
     Uint bsize = unaligned ? ERTS_MAGIC_BIN_UNALIGNED_SIZE(size)
                            : ERTS_MAGIC_BIN_SIZE(size);
-    Binary* bptr = erts_alloc_fnf(ERTS_ALC_T_BINARY, bsize);
+    Binary* bptr = erts_alloc_fnf(alloc_type, bsize);
     ASSERT(bsize > size);
     if (!bptr)
-	erts_alloc_n_enomem(ERTS_ALC_T2N(ERTS_ALC_T_BINARY), bsize);
+	erts_alloc_n_enomem(ERTS_ALC_T2N(alloc_type), bsize);
     ERTS_CHK_BIN_ALIGNMENT(bptr);
     bptr->flags = BIN_FLAG_MAGIC;
     bptr->orig_size = unaligned ? ERTS_MAGIC_BIN_UNALIGNED_ORIG_SIZE(size)
                                 : ERTS_MAGIC_BIN_ORIG_SIZE(size);
     erts_refc_init(&bptr->refc, 0);
     ERTS_MAGIC_BIN_DESTRUCTOR(bptr) = destructor;
+    ERTS_MAGIC_BIN_ATYPE(bptr) = alloc_type;
+    erts_make_magic_ref_in_array(ERTS_MAGIC_BIN_REFN(bptr));
     return bptr;
 }
 
 ERTS_GLB_INLINE Binary *
 erts_create_magic_binary(Uint size, void (*destructor)(Binary *))
 {
-    return erts_create_magic_binary_x(size, destructor, 0);
+    return erts_create_magic_binary_x(size, destructor,
+                                      ERTS_ALC_T_BINARY, 0);
 }
 
 #endif /* #if ERTS_GLB_INLINE_INCL_FUNC_DEF */
 
-#endif /* !__ERL_BINARY_H */
+#endif /* !ERL_BINARY_H__ */