aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/utils.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/utils.c')
-rw-r--r--erts/emulator/beam/utils.c278
1 files changed, 226 insertions, 52 deletions
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 0d75bbcc77..5b43d25e3c 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -1,7 +1,7 @@
/*
* %CopyrightBegin%
*
- * Copyright Ericsson AB 1996-2013. All Rights Reserved.
+ * Copyright Ericsson AB 1996-2014. All Rights Reserved.
*
* The contents of this file are subject to the Erlang Public License,
* Version 1.1, (the "License"); you may not use this file except in
@@ -31,6 +31,7 @@
#include "bif.h"
#include "erl_binary.h"
#include "erl_bits.h"
+#include "erl_map.h"
#include "packet_parser.h"
#include "erl_gc.h"
#define ERTS_WANT_DB_INTERNAL__
@@ -185,39 +186,41 @@ erts_set_hole_marker(Eterm* ptr, Uint sz)
* Helper function for the ESTACK macros defined in global.h.
*/
void
-erl_grow_stack(ErtsAlcType_t a_type, Eterm** start, Eterm** sp, Eterm** end)
+erl_grow_estack(ErtsEStack* s, Eterm* default_estack)
{
- Uint old_size = (*end - *start);
+ Uint old_size = (s->end - s->start);
Uint new_size = old_size * 2;
- Uint sp_offs = *sp - *start;
- if (new_size > 2 * DEF_ESTACK_SIZE) {
- *start = erts_realloc(a_type, (void *) *start, new_size*sizeof(Eterm));
+ Uint sp_offs = s->sp - s->start;
+ if (s->start != default_estack) {
+ s->start = erts_realloc(s->alloc_type, s->start,
+ new_size*sizeof(Eterm));
} else {
- Eterm* new_ptr = erts_alloc(a_type, new_size*sizeof(Eterm));
- sys_memcpy(new_ptr, *start, old_size*sizeof(Eterm));
- *start = new_ptr;
+ Eterm* new_ptr = erts_alloc(s->alloc_type, new_size*sizeof(Eterm));
+ sys_memcpy(new_ptr, s->start, old_size*sizeof(Eterm));
+ s->start = new_ptr;
}
- *end = *start + new_size;
- *sp = *start + sp_offs;
+ s->end = s->start + new_size;
+ s->sp = s->start + sp_offs;
}
/*
- * Helper function for the ESTACK macros defined in global.h.
+ * Helper function for the WSTACK macros defined in global.h.
*/
void
-erl_grow_wstack(ErtsAlcType_t a_type, UWord** start, UWord** sp, UWord** end)
+erl_grow_wstack(ErtsWStack* s, UWord* default_wstack)
{
- Uint old_size = (*end - *start);
+ Uint old_size = (s->wend - s->wstart);
Uint new_size = old_size * 2;
- Uint sp_offs = *sp - *start;
- if (new_size > 2 * DEF_ESTACK_SIZE) {
- *start = erts_realloc(a_type, (void *) *start, new_size*sizeof(UWord));
+ Uint sp_offs = s->wsp - s->wstart;
+ if (s->wstart != default_wstack) {
+ s->wstart = erts_realloc(s->alloc_type, s->wstart,
+ new_size*sizeof(UWord));
} else {
- UWord* new_ptr = erts_alloc(a_type, new_size*sizeof(UWord));
- sys_memcpy(new_ptr, *start, old_size*sizeof(UWord));
- *start = new_ptr;
+ UWord* new_ptr = erts_alloc(s->alloc_type, new_size*sizeof(UWord));
+ sys_memcpy(new_ptr, s->wstart, old_size*sizeof(UWord));
+ s->wstart = new_ptr;
}
- *end = *start + new_size;
- *sp = *start + sp_offs;
+ s->wend = s->wstart + new_size;
+ s->wsp = s->wstart + sp_offs;
}
/* CTYPE macros */
@@ -255,7 +258,7 @@ erl_grow_wstack(ErtsAlcType_t a_type, UWord** start, UWord** sp, UWord** end)
* Returns -1 if not a proper list (i.e. not terminated with NIL)
*/
int
-list_length(Eterm list)
+erts_list_length(Eterm list)
{
int i = 0;
@@ -732,6 +735,8 @@ erts_bld_atom_2uint_3tup_list(Uint **hpp, Uint *szp, Sint length,
#define FUNNY_NUMBER10 268440479
#define FUNNY_NUMBER11 268440577
#define FUNNY_NUMBER12 268440581
+#define FUNNY_NUMBER13 268440593
+#define FUNNY_NUMBER14 268440611
static Uint32
hash_binary_bytes(Eterm bin, Uint sz, Uint32 hash)
@@ -783,10 +788,10 @@ Uint32 make_hash(Eterm term_arg)
unsigned op;
/* Must not collide with the real tag_val_def's: */
-#define MAKE_HASH_TUPLE_OP 0x10
-#define MAKE_HASH_FUN_OP 0x11
-#define MAKE_HASH_CDR_PRE_OP 0x12
-#define MAKE_HASH_CDR_POST_OP 0x13
+#define MAKE_HASH_TUPLE_OP 0x11
+#define MAKE_HASH_TERM_ARRAY_OP 0x12
+#define MAKE_HASH_CDR_PRE_OP 0x13
+#define MAKE_HASH_CDR_POST_OP 0x14
/*
** Convenience macro for calculating a bytewise hash on an unsigned 32 bit
@@ -875,7 +880,7 @@ tail_recur:
hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq;
if (num_free > 0) {
if (num_free > 1) {
- WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP);
+ WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP);
}
term = funp->env[0];
goto tail_recur;
@@ -965,6 +970,24 @@ tail_recur:
hash *= is_neg ? FUNNY_NUMBER4 : FUNNY_NUMBER3;
break;
}
+ case MAP_DEF:
+ {
+ map_t *mp = (map_t *)map_val(term);
+ int size = map_get_size(mp);
+ Eterm *ks = map_get_keys(mp);
+ Eterm *vs = map_get_values(mp);
+
+ /* Use a prime with size to remedy some of
+ * the {} and <<>> hash problems */
+ hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size;
+ if (size == 0)
+ break;
+
+ /* push values first */
+ WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+ WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+ break;
+ }
case TUPLE_DEF:
{
Eterm* ptr = tuple_val(term);
@@ -974,7 +997,7 @@ tail_recur:
op = MAKE_HASH_TUPLE_OP;
}/*fall through*/
case MAKE_HASH_TUPLE_OP:
- case MAKE_HASH_FUN_OP:
+ case MAKE_HASH_TERM_ARRAY_OP:
{
Uint i = (Uint) WSTACK_POP(stack);
Eterm* ptr = (Eterm*) WSTACK_POP(stack);
@@ -1068,9 +1091,11 @@ Uint32
make_hash2(Eterm term)
{
Uint32 hash;
+ Uint32 hash_xor_keys = 0;
+ Uint32 hash_xor_values = 0;
DeclareTmpHeapNoproc(tmp_big,2);
-/* (HCONST * {2, ..., 14}) mod 2^32 */
+/* (HCONST * {2, ..., 16}) mod 2^32 */
#define HCONST_2 0x3c6ef372UL
#define HCONST_3 0xdaa66d2bUL
#define HCONST_4 0x78dde6e4UL
@@ -1085,6 +1110,11 @@ make_hash2(Eterm term)
#define HCONST_13 0x08d12e65UL
#define HCONST_14 0xa708a81eUL
#define HCONST_15 0x454021d7UL
+#define HCONST_16 0xe3779b90UL
+
+#define HASH_MAP_TAIL (_make_header(1,_TAG_HEADER_REF))
+#define HASH_MAP_KEY (_make_header(2,_TAG_HEADER_REF))
+#define HASH_MAP_VAL (_make_header(3,_TAG_HEADER_REF))
#define UINT32_HASH_2(Expr1, Expr2, AConst) \
do { \
@@ -1180,11 +1210,45 @@ make_hash2(Eterm term)
UINT32_HASH(arity, HCONST_9);
if (arity == 0) /* Empty tuple */
goto hash2_common;
- for (i = arity; i >= 2; i--) {
+ for (i = arity; i >= 1; i--) {
tmp = elem[i];
ESTACK_PUSH(s, tmp);
}
- term = elem[1];
+ goto hash2_common;
+ }
+ break;
+ case MAP_SUBTAG:
+ {
+ map_t *mp = (map_t *)map_val(term);
+ int i;
+ int size = map_get_size(mp);
+ Eterm *ks = map_get_keys(mp);
+ Eterm *vs = map_get_values(mp);
+ UINT32_HASH(size, HCONST_16);
+ if (size == 0) {
+ goto hash2_common;
+ }
+ ESTACK_PUSH(s, hash_xor_values);
+ ESTACK_PUSH(s, hash_xor_keys);
+ ESTACK_PUSH(s, hash);
+ ESTACK_PUSH(s, HASH_MAP_TAIL);
+ hash = 0;
+ hash_xor_keys = 0;
+ hash_xor_values = 0;
+ for (i = size - 1; i >= 0; i--) {
+ tmp = vs[i];
+ ESTACK_PUSH(s, HASH_MAP_VAL);
+ ESTACK_PUSH(s, tmp);
+ }
+ /* We do not want to expose the tuple representation.
+ * Do not push the keys as a tuple.
+ */
+ for (i = size - 1; i >= 0; i--) {
+ tmp = ks[i];
+ ESTACK_PUSH(s, HASH_MAP_KEY);
+ ESTACK_PUSH(s, tmp);
+ }
+ goto hash2_common;
}
break;
case EXPORT_SUBTAG:
@@ -1378,15 +1442,47 @@ make_hash2(Eterm term)
default:
erl_exit(1, "Invalid tag in make_hash2(0x%X)\n", term);
hash2_common:
+
+ /* Uint32 hash always has the hash value of the previous term,
+ * compounded or otherwise.
+ */
+
if (ESTACK_ISEMPTY(s)) {
DESTROY_ESTACK(s);
UnUseTmpHeapNoproc(2);
return hash;
}
+
term = ESTACK_POP(s);
+
+ switch (term) {
+ case HASH_MAP_TAIL: {
+ hash = (Uint32) ESTACK_POP(s);
+ UINT32_HASH(hash_xor_keys, HCONST_16);
+ UINT32_HASH(hash_xor_values, HCONST_16);
+ hash_xor_keys = (Uint32) ESTACK_POP(s);
+ hash_xor_values = (Uint32) ESTACK_POP(s);
+ goto hash2_common;
+ }
+ case HASH_MAP_KEY:
+ hash_xor_keys ^= hash;
+ hash = 0;
+ goto hash2_common;
+ case HASH_MAP_VAL:
+ hash_xor_values ^= hash;
+ hash = 0;
+ goto hash2_common;
+ default:
+ break;
+ }
}
}
}
+
+#undef HASH_MAP_TAIL
+#undef HASH_MAP_KEY
+#undef HASH_MAP_VAL
+
#undef UINT32_HASH_2
#undef UINT32_HASH
#undef SINT32_HASH
@@ -1488,7 +1584,7 @@ tail_recur:
hash = hash*FUNNY_NUMBER2 + funp->fe->old_uniq;
if (num_free > 0) {
if (num_free > 1) {
- WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_FUN_OP);
+ WSTACK_PUSH3(stack, (UWord) &funp->env[1], (num_free-1), MAKE_HASH_TERM_ARRAY_OP);
}
term = funp->env[0];
goto tail_recur;
@@ -1601,6 +1697,24 @@ tail_recur:
}
break;
+ case MAP_DEF:
+ {
+ map_t *mp = (map_t *)map_val(term);
+ int size = map_get_size(mp);
+ Eterm *ks = map_get_keys(mp);
+ Eterm *vs = map_get_values(mp);
+
+ /* Use a prime with size to remedy some of
+ * the {} and <<>> hash problems */
+ hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + size;
+ if (size == 0)
+ break;
+
+ /* push values first */
+ WSTACK_PUSH3(stack, (UWord)vs, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+ WSTACK_PUSH3(stack, (UWord)ks, (UWord) size, MAKE_HASH_TERM_ARRAY_OP);
+ break;
+ }
case TUPLE_DEF:
{
Eterm* ptr = tuple_val(term);
@@ -1610,7 +1724,7 @@ tail_recur:
op = MAKE_HASH_TUPLE_OP;
}/*fall through*/
case MAKE_HASH_TUPLE_OP:
- case MAKE_HASH_FUN_OP:
+ case MAKE_HASH_TERM_ARRAY_OP:
{
Uint i = (Uint) WSTACK_POP(stack);
Eterm* ptr = (Eterm*) WSTACK_POP(stack);
@@ -1638,7 +1752,7 @@ tail_recur:
return hash;
#undef MAKE_HASH_TUPLE_OP
-#undef MAKE_HASH_FUN_OP
+#undef MAKE_HASH_TERM_ARRAY_OP
#undef MAKE_HASH_CDR_PRE_OP
#undef MAKE_HASH_CDR_POST_OP
}
@@ -1675,7 +1789,7 @@ static int do_send_to_logger(Eterm tag, Eterm gleader, char *buf, int len)
p = erts_whereis_process(NULL, 0, am_error_logger, 0, 0);
if (p) {
erts_aint32_t state = erts_smp_atomic32_read_acqb(&p->state);
- if (state & ERTS_PSFLG_RUNNING)
+ if (state & (ERTS_PSFLG_RUNNING|ERTS_PSFLG_RUNNING_SYS))
p = NULL;
}
}
@@ -2005,6 +2119,18 @@ tailrecur_ne:
++bb;
goto term_array;
}
+ case MAP_SUBTAG:
+ {
+ aa = map_val_rel(a, a_base);
+ if (!is_boxed(b) || *boxed_val_rel(b,b_base) != *aa)
+ goto not_equal;
+ bb = map_val_rel(b,b_base);
+ if ((sz = map_get_size((map_t*)aa)) == 0) goto pop_next;
+ aa += 2;
+ bb += 2;
+ sz += 1; /* increment for tuple-keys */
+ goto term_array;
+ }
case REFC_BINARY_SUBTAG:
case HEAP_BINARY_SUBTAG:
case SUB_BINARY_SUBTAG:
@@ -2279,7 +2405,7 @@ static int cmpbytes(byte *s1, int l1, byte *s2, int l2)
*
* According to the Erlang Standard, types are orderered as follows:
* numbers < (characters) < atoms < refs < funs < ports < pids <
- * tuples < [] < conses < binaries.
+ * tuples < maps < [] < conses < binaries.
*
* Note that characters are currently not implemented.
*
@@ -2299,10 +2425,24 @@ static int cmp_atoms(Eterm a, Eterm b)
bb->name+3, bb->len-3);
}
+#if !HALFWORD_HEAP
+/* cmp(Eterm a, Eterm b)
+ * For compatibility with HiPE - arith-based compare.
+ */
+Sint cmp(Eterm a, Eterm b)
+{
+ return erts_cmp(a, b, 0);
+}
+#endif
+
+/* erts_cmp(Eterm a, Eterm b, int exact)
+ * exact = 1 -> term-based compare
+ * exact = 0 -> arith-based compare
+ */
#if HALFWORD_HEAP
-Sint cmp_rel(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base)
+Sint erts_cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, int exact)
#else
-Sint cmp(Eterm a, Eterm b)
+Sint erts_cmp(Eterm a, Eterm b, int exact)
#endif
{
DECLARE_WSTACK(stack);
@@ -2462,7 +2602,25 @@ tailrecur_ne:
++aa;
++bb;
goto term_array;
+ case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE) :
+ if (!is_map_rel(b,b_base)) {
+ a_tag = MAP_DEF;
+ goto mixed_types;
+ }
+ aa = (Eterm *)map_val_rel(a,a_base);
+ bb = (Eterm *)map_val_rel(b,b_base);
+ i = map_get_size((map_t*)aa);
+ if (i != map_get_size((map_t*)bb)) {
+ RETURN_NEQ((int)(i - map_get_size((map_t*)bb)));
+ }
+ if (i == 0) {
+ goto pop_next;
+ }
+ aa += 2;
+ bb += 2;
+ i += 1; /* increment for tuple-keys */
+ goto term_array;
case (_TAG_HEADER_FLOAT >> _TAG_PRIMARY_SIZE):
if (!is_float_rel(b,b_base)) {
a_tag = FLOAT_DEF;
@@ -2686,11 +2844,6 @@ tailrecur_ne:
{
FloatDef f1, f2;
Eterm big;
-#if HEAP_ON_C_STACK
- Eterm big_buf[CMP_TMP_HEAP_SIZE]; /* If HEAP_ON_C_STACK */
-#else
- Eterm *big_buf = erts_get_scheduler_data()->cmp_tmp_heap;
-#endif
#if HALFWORD_HEAP
Wterm aw = is_immed(a) ? a : rterm2wterm(a,a_base);
Wterm bw = is_immed(b) ? b : rterm2wterm(b,b_base);
@@ -2701,6 +2854,8 @@ tailrecur_ne:
#define MAX_LOSSLESS_FLOAT ((double)((1LL << 53) - 2))
#define MIN_LOSSLESS_FLOAT ((double)(((1LL << 53) - 2)*-1))
#define BIG_ARITY_FLOAT_MAX (1024 / D_EXP) /* arity of max float as a bignum */
+ Eterm big_buf[BIG_NEED_SIZE(BIG_ARITY_FLOAT_MAX)];
+
b_tag = tag_val_def(bw);
switch(_NUMBER_CODE(a_tag, b_tag)) {
@@ -2711,13 +2866,15 @@ tailrecur_ne:
j = big_sign(aw) ? -1 : 1;
break;
case SMALL_FLOAT:
+ if (exact) goto exact_fall_through;
GET_DOUBLE(bw, f2);
if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) {
/* Float is within the no loss limit */
f1.fd = signed_val(aw);
j = float_comp(f1.fd, f2.fd);
+ }
#if ERTS_SIZEOF_ETERM == 8
- } else if (f2.fd > (double) (MAX_SMALL + 1)) {
+ else if (f2.fd > (double) (MAX_SMALL + 1)) {
/* Float is a positive bignum, i.e. bigger */
j = -1;
} else if (f2.fd < (double) (MIN_SMALL - 1)) {
@@ -2728,19 +2885,21 @@ tailrecur_ne:
j = signed_val(aw) - (Sint) f2.fd;
}
#else
- } else {
+ else {
/* If float is positive it is bigger than small */
j = (f2.fd > 0.0) ? -1 : 1;
}
#endif /* ERTS_SIZEOF_ETERM == 8 */
break;
case FLOAT_BIG:
+ if (exact) goto exact_fall_through;
{
Wterm tmp = aw;
aw = bw;
bw = tmp;
}/* fall through */
case BIG_FLOAT:
+ if (exact) goto exact_fall_through;
GET_DOUBLE(bw, f2);
if ((f2.fd < (double) (MAX_SMALL + 1))
&& (f2.fd > (double) (MIN_SMALL - 1))) {
@@ -2762,21 +2921,23 @@ tailrecur_ne:
j = float_comp(f1.fd, f2.fd);
}
} else {
- big = double_to_big(f2.fd, big_buf);
- j = big_comp(aw, big);
+ big = double_to_big(f2.fd, big_buf, sizeof(big_buf)/sizeof(Eterm));
+ j = big_comp(aw, rterm2wterm(big,big_buf));
}
if (_NUMBER_CODE(a_tag, b_tag) == FLOAT_BIG) {
j = -j;
}
break;
case FLOAT_SMALL:
+ if (exact) goto exact_fall_through;
GET_DOUBLE(aw, f1);
if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) {
/* Float is within the no loss limit */
f2.fd = signed_val(bw);
j = float_comp(f1.fd, f2.fd);
+ }
#if ERTS_SIZEOF_ETERM == 8
- } else if (f1.fd > (double) (MAX_SMALL + 1)) {
+ else if (f1.fd > (double) (MAX_SMALL + 1)) {
/* Float is a positive bignum, i.e. bigger */
j = 1;
} else if (f1.fd < (double) (MIN_SMALL - 1)) {
@@ -2787,12 +2948,13 @@ tailrecur_ne:
j = (Sint) f1.fd - signed_val(bw);
}
#else
- } else {
+ else {
/* If float is positive it is bigger than small */
j = (f1.fd > 0.0) ? 1 : -1;
}
#endif /* ERTS_SIZEOF_ETERM == 8 */
break;
+exact_fall_through:
default:
j = b_tag - a_tag;
}
@@ -2846,7 +3008,7 @@ pop_next:
return 0;
not_equal:
- DESTROY_ESTACK(stack);
+ DESTROY_WSTACK(stack);
return j;
#undef CMP_NODES
@@ -3021,6 +3183,14 @@ buf_to_intlist(Eterm** hpp, const char *buf, size_t len, Eterm tail)
** Return remaining bytes in buffer on success
** ERTS_IOLIST_TO_BUF_OVERFLOW on overflow
** ERTS_IOLIST_TO_BUF_TYPE_ERROR on type error (including that result would not be a whole number of bytes)
+**
+** Note!
+** Do not detect indata errors in this fiunction that are not detected by erts_iolist_size!
+**
+** A caller should be able to rely on a successful return from erts_iolist_to_buf
+** if erts_iolist_size is previously successfully called and erts_iolist_to_buf
+** is called with a buffer at least as large as the value given by erts_iolist_size.
+**
*/
ErlDrvSizeT erts_iolist_to_buf(Eterm obj, char* buf, ErlDrvSizeT alloced_len)
@@ -3127,6 +3297,11 @@ ErlDrvSizeT erts_iolist_to_buf(Eterm obj, char* buf, ErlDrvSizeT alloced_len)
/*
* Return 0 if successful, and non-zero if unsuccessful.
+ *
+ * It is vital that if erts_iolist_to_buf would return an error for
+ * any type of term data, this function should do so as well.
+ * Any input term error detected in erts_iolist_to_buf should also
+ * be detected in this function!
*/
int erts_iolist_size(Eterm obj, ErlDrvSizeT* sizep)
{
@@ -4006,7 +4181,6 @@ erts_smp_ensure_later_interval_acqb(erts_interval_t *icp, Uint64 ic)
#endif
}
-
/*
* A millisecond timestamp without time correction where there's no hrtime
* - for tracing on "long" things...
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-28 18:39:05 +0000