From 8d3dba44bc2ac5ff9e724e90aa832854280b7d1e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Wed, 27 Jun 2012 17:03:54 +0200 Subject: Initial Persistent HAMT - Map framework Conflicts: erts/emulator/Makefile.in erts/emulator/beam/bif.tab erts/emulator/beam/erl_gc.c erts/emulator/beam/erl_gc.h erts/emulator/beam/erl_printf_term.c erts/emulator/beam/erl_term.c erts/emulator/beam/erl_term.h --- erts/emulator/Makefile.in | 3 +- erts/emulator/beam/beam_emu.c | 1 + erts/emulator/beam/bif.tab | 10 + erts/emulator/beam/copy.c | 47 +++- erts/emulator/beam/erl_gc.c | 1 + erts/emulator/beam/erl_gc.h | 3 +- erts/emulator/beam/erl_hashmap.c | 506 +++++++++++++++++++++++++++++++++++ erts/emulator/beam/erl_hashmap.h | 149 +++++++++++ erts/emulator/beam/erl_printf_term.c | 76 +++++- erts/emulator/beam/erl_term.c | 4 +- erts/emulator/beam/erl_term.h | 9 +- erts/emulator/beam/erl_vm.h | 4 +- erts/emulator/beam/global.h | 10 +- erts/emulator/hipe/hipe_gc.c | 1 + 14 files changed, 807 insertions(+), 17 deletions(-) create mode 100644 erts/emulator/beam/erl_hashmap.c create mode 100644 erts/emulator/beam/erl_hashmap.h (limited to 'erts') diff --git a/erts/emulator/Makefile.in b/erts/emulator/Makefile.in index a632faf57d..db7eac4690 100644 --- a/erts/emulator/Makefile.in +++ b/erts/emulator/Makefile.in @@ -785,7 +785,8 @@ RUN_OBJS = \ $(OBJDIR)/erl_zlib.o $(OBJDIR)/erl_nif.o \ $(OBJDIR)/erl_bif_binary.o $(OBJDIR)/erl_ao_firstfit_alloc.o \ $(OBJDIR)/erl_thr_queue.o $(OBJDIR)/erl_sched_spec_pre_alloc.o \ - $(OBJDIR)/erl_ptab.o $(OBJDIR)/erl_map.o + $(OBJDIR)/erl_ptab.o $(OBJDIR)/erl_map.o \ + $(OBJDIR)/erl_hashmap.o ifeq ($(TARGET),win32) DRV_OBJS = \ diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index b89c8b3900..b734d34872 100644 --- a/erts/emulator/beam/beam_emu.c +++ b/erts/emulator/beam/beam_emu.c @@ -2801,6 +2801,7 @@ get_map_elements_fail: } PreFetch(1, next); ASSERT(!ERTS_PROC_IS_EXITING(c_p)); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(c_p); reg[0] = r(0); result = (*bf)(c_p, reg, I); ASSERT(!ERTS_PROC_IS_EXITING(c_p) || is_non_value(result)); diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 1d0d214e77..a3fb21ee52 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -614,6 +614,16 @@ bif erlang:fun_info_mfa/1 bif erlang:get_keys/0 +# Hash Array Mappped Trie +bif hashmap:put/3 +bif hashmap:get/2 +#bif hashmap:info/1 +bif hashmap:to_list/1 +bif hashmap:new/0 +# bif hashmap:keys/1 +bif hashmap:size/1 +bif erlang:is_hashmap/1 + # # Obsolete # diff --git a/erts/emulator/beam/copy.c b/erts/emulator/beam/copy.c index 0010f6a440..6294ba9412 100644 --- a/erts/emulator/beam/copy.c +++ b/erts/emulator/beam/copy.c @@ -33,6 +33,7 @@ #include "erl_binary.h" #include "erl_bits.h" #include "dtrace-wrapper.h" +#include "erl_hashmap.h" static void move_one_frag(Eterm** hpp, Eterm* src, Uint src_sz, ErlOffHeap*); @@ -127,6 +128,35 @@ Uint size_object(Eterm obj) obj = *bptr; break; } + case HASHMAP_SUBTAG: + switch (MAP_HEADER_TYPE(hdr)) { + case MAP_HEADER_TAG_HAMT_HEAD_BITMAP : + case MAP_HEADER_TAG_HAMT_HEAD_ARRAY : + case MAP_HEADER_TAG_HAMT_NODE_BITMAP : + { + Eterm *head; + Uint sz; + head = hashmap_val_rel(obj, base); + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + sum += 1 + sz + header_arity(hdr); + head += 1 + header_arity(hdr); + + if (sz == 0) { + goto pop_next; + } + while(sz-- > 1) { + obj = head[sz]; + if (!IS_CONST(obj)) { + ESTACK_PUSH(s, obj); + } + } + obj = head[0]; + } + break; + default: + erl_exit(ERTS_ABORT_EXIT, "size_object: bad hashmap type %d\n", MAP_HEADER_TYPE(hdr)); + } + break; case SUB_BINARY_SUBTAG: { Eterm real_bin; @@ -459,7 +489,7 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) { ExternalThing *etp = (ExternalThing *) htop; - i = thing_arityval(hdr) + 1; + i = thing_arityval(hdr) + 1; tp = htop; while (i--) { @@ -473,6 +503,21 @@ Eterm copy_struct(Eterm obj, Uint sz, Eterm** hpp, ErlOffHeap* off_heap) *argp = make_external_rel(tp, dst_base); } break; + case HASHMAP_SUBTAG: + tp = htop; + switch (MAP_HEADER_TYPE(hdr)) { + case MAP_HEADER_TAG_HAMT_HEAD_BITMAP : + case MAP_HEADER_TAG_HAMT_HEAD_ARRAY : + *htop++ = *objp++; + case MAP_HEADER_TAG_HAMT_NODE_BITMAP : + i = 1 + hashmap_bitcount(MAP_HEADER_VAL(hdr)); + while (i--) { *htop++ = *objp++; } + *argp = make_hashmap_rel(tp, dstbase); + break; + default: + erl_exit(ERTS_ABORT_EXIT, "copy_struct: bad hashmap type %d\n", MAP_HEADER_TYPE(hdr)); + } + break; case BIN_MATCHSTATE_SUBTAG: erl_exit(ERTS_ABORT_EXIT, "copy_struct: matchstate term not allowed"); diff --git a/erts/emulator/beam/erl_gc.c b/erts/emulator/beam/erl_gc.c index d1a7ee113b..bdf7aa362e 100644 --- a/erts/emulator/beam/erl_gc.c +++ b/erts/emulator/beam/erl_gc.c @@ -31,6 +31,7 @@ #include "erl_binary.h" #include "erl_bits.h" #include "erl_map.h" +#include "erl_hashmap.h" #include "error.h" #include "big.h" #include "erl_gc.h" diff --git a/erts/emulator/beam/erl_gc.h b/erts/emulator/beam/erl_gc.h index bf0496c112..3fec553684 100644 --- a/erts/emulator/beam/erl_gc.h +++ b/erts/emulator/beam/erl_gc.h @@ -56,6 +56,8 @@ do { \ switch ((HDR) & _HEADER_SUBTAG_MASK) { \ case SUB_BINARY_SUBTAG: nelts++; break; \ case MAP_SUBTAG: nelts+=map_get_size(PTR) + 1; break; \ + case HASHMAP_SUBTAG: nelts=hashmap_bitcount(MAP_HEADER_VAL(HDR)); \ + nelts += is_hashmap_header_head(HDR) ? 1 : 0; break; \ case FUN_SUBTAG: nelts+=((ErlFunThing*)(PTR))->num_free+1; break; \ } \ gval = make_boxed(HTOP); \ @@ -63,7 +65,6 @@ do { \ *HTOP++ = HDR; \ *PTR++ = gval; \ while (nelts--) *HTOP++ = *PTR++; \ - \ } while(0) #define in_area(ptr,start,nbytes) \ diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c new file mode 100644 index 0000000000..b7d5d2e2eb --- /dev/null +++ b/erts/emulator/beam/erl_hashmap.c @@ -0,0 +1,506 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2011. 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 + * compliance with the License. You should have received a copy of the + * Erlang Public License along with this software. If not, it can be + * retrieved online at http://www.erlang.org/. + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + * the License for the specific language governing rights and limitations + * under the License. + * + * %CopyrightEnd% + * + * hashmaps are an adaption of Rich Hickeys Persistent HashMaps + * which were an adaption of Phil Bagwells - Hash Array Mapped Tries + * + * Author: Björn-Egil Dahlberg + */ +/* + * Ls = lists:seq(1,188888). + * A = lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), Ls). + * lists:foreach(fun(I) -> io:format("looking up ~p got ~p~n", [I, hashmap:get(I, A)]), I = hashmap:get(I,A) end, Ls). + * + * lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), lists:seq(1,7)). + * + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "sys.h" +#include "erl_vm.h" +#include "global.h" +#include "erl_process.h" +#include "error.h" +#include "bif.h" + +#include "erl_hashmap.h" + +#ifndef DECL_AM +#define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1) +#endif + +static char *format_binary(Uint64 x, char *b) { + int z; + b[64] = '\0'; + for (z = 0; z < 64; z++) { + b[63-z] = ((x>>z) & 0x1) ? '1' : '0'; + } + return b; +} + +static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key); +static Uint32 hashmap_restore_hash(Uint lvl, Eterm key); +static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node); +static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node); +static Eterm hashmap_to_list(Process *p, Eterm map); + +/* hashmap:new/0 */ + +BIF_RETTYPE hashmap_new_0(BIF_ALIST_0) { + Eterm* hp; + hashmap_head_t *head; + + hp = HAlloc(BIF_P, HAMT_HEAD_EMPTY_SZ); + head = (hashmap_head_t *) hp; + + head->thing_word = MAP_HEADER_HAMT_HEAD_BITMAP(0); + head->size = 0; + + BIF_RET(make_hashmap(head)); +} + +/* hashmap:put/3 */ + +BIF_RETTYPE hashmap_put_3(BIF_ALIST_3) { + if (is_hashmap(BIF_ARG_3)) { + Uint32 hx = make_hash2(BIF_ARG_1); + Eterm map; + + map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3); + ASSERT(is_hashmap(map)); + BIF_RET(map); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* hashmap:to_list/1 */ + +BIF_RETTYPE hashmap_to_list_1(BIF_ALIST_1) { + if (is_hashmap(BIF_ARG_1)) { + return hashmap_to_list(BIF_P, BIF_ARG_1); + } + + BIF_ERROR(BIF_P, BADARG); +} + +/* hashmap:get/2 */ + +BIF_RETTYPE hashmap_get_2(BIF_ALIST_2) { + if (is_hashmap(BIF_ARG_2)) { + const Eterm *value; + Uint32 hx = make_hash2(BIF_ARG_1); + + if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) { + BIF_RET(*value); + } + } + BIF_ERROR(BIF_P, BADARG); +} + +/* hashmap:size/1 */ + +BIF_RETTYPE hashmap_size_1(BIF_ALIST_1) { + if (is_hashmap(BIF_ARG_1)) { + Eterm *head, *hp, res; + Uint size, hsz=0; + + head = hashmap_val(BIF_ARG_1); + size = head[1]; + (void) erts_bld_uint(NULL, &hsz, size); + hp = HAlloc(BIF_P, hsz); + res = erts_bld_uint(&hp, NULL, size); + BIF_RET(res); + } + BIF_ERROR(BIF_P, BADARG); +} + +/* erlang:is_hashmap/1 */ + +BIF_RETTYPE is_hashmap_1(BIF_ALIST_1) { + if (is_hashmap(BIF_ARG_1)) { + BIF_RET(am_true); + } + BIF_RET(am_false); +} + +/* impl. */ + +static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) { + Eterm *ptr, hdr; + Uint ix,slot, lvl = 0; + Uint32 hval,bp; + + for (;;) { + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ + ptr = list_val(node); + if (EQ(CAR(ptr), key)) { + return &(CDR(ptr)); + } + return NULL; + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_NODE_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[ix+1]; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[ix+2]; + break; + case HAMT_SUBTAG_NODE_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[slot+1]; + break; + } + /* not occupied */ + return NULL; + case HAMT_SUBTAG_HEAD_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[slot+2]; + break; + } + /* not occupied */ + return NULL; + default: + erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + default: + erl_exit(1, "bad primary tag %p\r\n", node); + break; + } + } + return NULL; +} + +static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node) { + Eterm *hp = NULL, *nhp = NULL; + Eterm *ptr; + Eterm hdr,res,ckey,fake; + Uint32 ix, cix, bp, hval, chx; + Uint slot, lvl = 0, clvl; + Uint size = 0, n = 0, update_size = 1; + DECLARE_ESTACK(stack); + + for (;;) { + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ + ptr = list_val(node); + ckey = CAR(ptr); + if (EQ(ckey, key)) { + update_size = 0; + goto unroll; + } + goto insert_subnodes; + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_NODE_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(hx,&lvl,key); + size += HAMT_NODE_ARRAY_SZ; + ESTACK_PUSH2(stack, ix, node); + node = ptr[ix+1]; + break; + case HAMT_SUBTAG_HEAD_ARRAY: + ix = hashmap_index(hx); + hx = hashmap_shift_hash(hx,&lvl,key); + size += HAMT_HEAD_ARRAY_SZ; + ESTACK_PUSH2(stack, ix, node); + node = ptr[ix+2]; + break; + case HAMT_SUBTAG_NODE_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + + ESTACK_PUSH(stack, n); + ESTACK_PUSH3(stack, bp, slot, node); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[slot+1]; + ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); + size += HAMT_NODE_BITMAP_SZ(n); + break; + } + /* not occupied */ + size += HAMT_NODE_BITMAP_SZ(n+1); + goto unroll; + case HAMT_SUBTAG_HEAD_BITMAP: + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + bp = 1 << ix; + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + + ESTACK_PUSH(stack, n); + ESTACK_PUSH3(stack, bp, slot, node); + + /* occupied */ + if (bp & hval) { + hx = hashmap_shift_hash(hx,&lvl,key); + node = ptr[slot+2]; + ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); + size += HAMT_HEAD_BITMAP_SZ(n); + break; + } + /* not occupied */ + size += HAMT_HEAD_BITMAP_SZ(n+1); + goto unroll; + default: + erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + default: + erl_exit(1, "bad primary tag %p\r\n", node); + break; + } + } +insert_subnodes: + clvl = lvl; + chx = hashmap_restore_hash(clvl,ckey); + size += HAMT_NODE_BITMAP_SZ(2); + ix = hashmap_index(hx); + cix = hashmap_index(chx); + + while (cix == ix) { + ESTACK_PUSH(stack, 0); + ESTACK_PUSH3(stack, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0)); + size += HAMT_NODE_BITMAP_SZ(1); + hx = hashmap_shift_hash(hx,&lvl,key); + chx = hashmap_shift_hash(chx,&clvl,ckey); + ix = hashmap_index(hx); + cix = hashmap_index(chx); + } + ESTACK_PUSH3(stack, cix, ix, node); + +unroll: + size += 2; + hp = HAlloc(p, size); + res = CONS(hp, key, value); hp += 2; + + do { + node = ESTACK_POP(stack); + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: + ix = (Uint32) ESTACK_POP(stack); + cix = (Uint32) ESTACK_POP(stack); + + nhp = hp; + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix)); + if (ix < cix) { + *hp++ = res; + *hp++ = node; + } else { + *hp++ = node; + *hp++ = res; + } + res = make_hashmap(nhp); + break; + case TAG_PRIMARY_HEADER: + /* subnodes, fake it */ + fake = node; + node = make_boxed(&fake); + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_NODE_ARRAY: + slot = (Uint) ESTACK_POP(stack); + nhp = hp; + n = HAMT_NODE_ARRAY_SZ; + while(n--) { *hp++ = *ptr++; } + nhp[slot+1] = res; + res = make_hashmap(nhp); + break; + case HAMT_SUBTAG_HEAD_ARRAY: + slot = (Uint) ESTACK_POP(stack); + nhp = hp; + n = HAMT_HEAD_ARRAY_SZ - 2; + *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++; + *hp++ = (*ptr++) + update_size; + while(n--) { *hp++ = *ptr++; } + nhp[slot+2] = res; + res = make_hashmap(nhp); + break; + case HAMT_SUBTAG_NODE_BITMAP: + slot = (Uint) ESTACK_POP(stack); + bp = (Uint32) ESTACK_POP(stack); + n = (Uint32) ESTACK_POP(stack); + hval = MAP_HEADER_VAL(hdr); + nhp = hp; + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++; + + n -= slot; + while(slot--) { *hp++ = *ptr++; } + *hp++ = res; + if (hval & bp) { ptr++; n--; } + while(n--) { *hp++ = *ptr++; } + + if ((hval | bp) == 0xffff) { + *nhp = make_arityval(16); + } + res = make_hashmap(nhp); + break; + case HAMT_SUBTAG_HEAD_BITMAP: + slot = (Uint) ESTACK_POP(stack); + bp = (Uint32) ESTACK_POP(stack); + n = (Uint32) ESTACK_POP(stack); + hval = MAP_HEADER_VAL(hdr); + nhp = hp; + *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++; + *hp++ = (*ptr++) + update_size; + + n -= slot; + while(slot--) { *hp++ = *ptr++; } + *hp++ = res; + if (hval & bp) { ptr++; n--; } + while(n--) { *hp++ = *ptr++; } + + if ((hval | bp) == 0xffff) { + *nhp = MAP_HEADER_HAMT_HEAD_ARRAY; + } + res = make_hashmap(nhp); + break; + default: + erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + break; + } + break; + default: + erl_exit(1, "bad primary tag %x\r\n", primary_tag(node)); + break; + } + + } while(!ESTACK_ISEMPTY(stack)); + + DESTROY_ESTACK(stack); + ERTS_VERIFY_UNUSED_TEMP_ALLOC(p); + ERTS_HOLE_CHECK(p); + return res; +} + +static Eterm hashmap_to_list(Process *p, Eterm node) { + Eterm *hp; + Eterm res = NIL; + Eterm *ptr, tup, hdr; + Uint sz, n; + DECLARE_ESTACK(stack); + + ptr = boxed_val(node); + n = (Uint)ptr[1]; + hp = HAlloc(p, n * (2 + 3)); + ESTACK_PUSH(stack, node); + do { + node = ESTACK_POP(stack); + switch(primary_tag(node)) { + case TAG_PRIMARY_LIST: + ptr = list_val(node); + tup = TUPLE2(hp, CAR(ptr), CDR(ptr)); hp += 3; + res = CONS(hp, tup, res); hp += 2; + break; + case TAG_PRIMARY_BOXED: + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + case HAMT_SUBTAG_NODE_ARRAY: + ptr++; + sz = 16; + while(sz--) { ESTACK_PUSH(stack, ptr[sz]); } + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + ptr++; + while(sz--) { ESTACK_PUSH(stack, ptr[sz]); } + break; + default: + erl_exit(1, "bad header\r\n"); + break; + } + } + } while(!ESTACK_ISEMPTY(stack)); + + DESTROY_ESTACK(stack); + ERTS_HOLE_CHECK(p); + return res; +} + +static Uint32 hashmap_restore_hash(Uint lvl, Eterm key) { + Eterm heap[2], ret; + + if (lvl < 8) { + return make_hash2(key) >> (4*lvl); + } + ret = CONS(heap, make_small(lvl), key); + + return make_hash2(ret) >> (4*(lvl % 8)); +} + +static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key) { + Eterm heap[2], ret; + + /* rehash with [ lvl | key ] */ + *lvl = *lvl + 1; + if (*lvl % 8) { + return hx >> 4; + } + + ret = CONS(heap, make_small((*lvl)), key); + return make_hash2(ret); +} diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h new file mode 100644 index 0000000000..03739fa1f9 --- /dev/null +++ b/erts/emulator/beam/erl_hashmap.h @@ -0,0 +1,149 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2011. 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 + * compliance with the License. You should have received a copy of the + * Erlang Public License along with this software. If not, it can be + * retrieved online at http://www.erlang.org/. + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + * the License for the specific language governing rights and limitations + * under the License. + * + * %CopyrightEnd% + */ + + +#ifndef __ERL_HASH_H__ +#define __ERL_HASH_H__ + +#include "sys.h" + +Eterm erts_hashmap_get(Eterm key, Eterm map); + +/* erl_term.h stuff */ +#define make_hashmap(x) make_boxed((Eterm*)(x)) +#define make_hashmap_rel make_boxed_rel +#define is_hashmap(x) (is_boxed((x)) && is_hashmap_header(*boxed_val((x)))) +#define is_hashmap_header(x) (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HASHMAP) +#define hashmap_val(x) _unchecked_boxed_val((x)) +#define hashmap_val_rel(RTERM, BASE) hashmap_val(rterm2wterm(RTERM, BASE)) + +/* HASH */ + + +#if defined(__GNUC__) +#define hashmap_bitcount(x) (Uint32) __builtin_popcount((unsigned int) (x)) +#else +const Uint32 SK5 = 0x55555555, SK3 = 0x33333333; +const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF; + +/* CTPOP emulation */ +Uint32 hashmap_bitcount(Uint32 map) { + map -= (( map >> 1 ) & SK5 ); + map = ( map & SK3 ) + (( map >> 2 ) & SK3 ); + map = ( map & SKF0 ) + (( map >> 4 ) & SKF0); + map += map >> 8; + return ( map + ( map >> 16)) & 0x3F; +} +#endif + +/* hamt nodes v2.0 + * + * node :: leaf | array | bitmap + * head + */ + +/* the head-node is a bitmap or array with an untagged size + */ +typedef struct hashmap_head_s { + Eterm thing_word; + Uint size; + Eterm items[1]; +} hashmap_head_t; + +/* the bitmap-node + * typedef struct hashmap_bitmap_node_s { + * Eterm thing_word; + * Eterm items[1]; + * } hashmap_bitmap_node_t; + * + * the array-node is a tuple + * typedef struct hashmap_bitmap_node_s { + * Eterm thing_word; + * Eterm items[1]; + * } hashmap_bitmap_node_t; + * + * the leaf-node + * cons-cell + */ + +/* thing_word tagscheme + * Need two bits for map subtags + * + * Original HEADER representation: + * + * aaaaaaaaaaaaaaaa aaaaaaaaaatttt00 arity:26, tag:4 + * + * For maps we have: + * + * vvvvvvvvvvvvvvvv aaaaaaaamm111100 val:16, arity:8, mtype:2 + * + * unsure about trailing zeros + * + * map-tag: + * 00 - flat map tag (non-hamt) -> val:16 = #items + * 01 - map-node bitmap tag -> val:16 = bitmap + * 10 - map-head (array-node) -> val:16 = 0xffff + * 11 - map-head (bitmap-node) -> val:16 = bitmap + */ + +/* erl_map.h stuff */ + +#define MAP_HEADER_TAG_SZ (2) +#define MAP_HEADER_ARITY_SZ (8) +#define MAP_HEADER_VAL_SZ (16) + +#define MAP_HEADER_TAG_FLAT (0x0) +#define MAP_HEADER_TAG_HAMT_NODE_BITMAP (0x1) +#define MAP_HEADER_TAG_HAMT_HEAD_ARRAY (0x2) +#define MAP_HEADER_TAG_HAMT_HEAD_BITMAP (0x3) + +#define MAP_HEADER_TYPE(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS)) & (0x3)) +#define MAP_HEADER_ARITY(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ)) & (0xff)) +#define MAP_HEADER_VAL(Hdr) (((Hdr) >> (_HEADER_ARITY_OFFS + MAP_HEADER_TAG_SZ + MAP_HEADER_ARITY_SZ)) & (0xffff)) + +#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) + +#define MAKE_MAP_HEADER(Type,Arity,Val) \ + (_make_header(((((Uint16)Val) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_HASHMAP)) + +#define MAP_HEADER_HAMT_HEAD_ARRAY \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_ARRAY,0x1,0xffff) + +#define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp) + +#define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ + MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) + +#define HAMT_HEAD_EMPTY_SZ (2) +#define HAMT_NODE_ARRAY_SZ (17) +#define HAMT_HEAD_ARRAY_SZ (18) +#define HAMT_NODE_BITMAP_SZ(n) (1 + n) +#define HAMT_HEAD_BITMAP_SZ(n) (2 + n) + +#define _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ +/* SUBTAG_NODE_ARRAY is in fact a tuple with 16 elements */ +#define HAMT_SUBTAG_NODE_ARRAY (((16 << _HEADER_ARITY_OFFS) | ARITYVAL_SUBTAG) & _HEADER_MAP_SUBTAG_MASK) +#define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) +#define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) + +#define hashmap_index(hash) (((Uint32)hash) & 0xf) + +#endif diff --git a/erts/emulator/beam/erl_printf_term.c b/erts/emulator/beam/erl_printf_term.c index c982dc2080..f07fe30cf6 100644 --- a/erts/emulator/beam/erl_printf_term.c +++ b/erts/emulator/beam/erl_printf_term.c @@ -26,12 +26,13 @@ #include "big.h" #include "erl_map.h" #include "erl_binary.h" +#include "erl_hashmap.h" #define PRINT_CHAR(CNT, FN, ARG, C) \ do { \ int res__ = erts_printf_char((FN), (ARG), (C)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -39,7 +40,7 @@ do { \ do { \ int res__ = erts_printf_string((FN), (ARG), (STR)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -47,7 +48,7 @@ do { \ do { \ int res__ = erts_printf_buf((FN), (ARG), (char*)(BUF), (LEN)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -55,7 +56,7 @@ do { \ do { \ int res__ = erts_printf_pointer((FN), (ARG), (void *) (PTR)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -63,7 +64,7 @@ do { \ do { \ int res__ = erts_printf_uword((FN), (ARG), (C), (P), (W), (I)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -71,7 +72,7 @@ do { \ do { \ int res__ = erts_printf_sword((FN), (ARG), (C), (P), (W), (I)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -79,7 +80,7 @@ do { \ do { \ int res__ = erts_printf_double((FN), (ARG), (C), (P), (W), (I)); \ if (res__ < 0) \ - return res__; \ + abort(); \ (CNT) += res__; \ } while (0) @@ -247,6 +248,17 @@ static int print_atom_name(fmtfn_t fn, void* arg, Eterm atom, long *dcount) #define PRT_PATCH_FUN_SIZE ((Eterm) 7) #define PRT_LAST_ARRAY_ELEMENT ((Eterm) 8) /* Note! Must be last... */ +#if 0 +static char *format_binary(Uint16 x, char *b) { + int z; + b[16] = '\0'; + for (z = 0; z < 16; z++) { + b[15-z] = ((x>>z) & 0x1) ? '1' : '0'; + } + return b; +} +#endif + static int print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, Eterm* obj_base) /* ignored if !HALFWORD_HEAP */ @@ -575,6 +587,54 @@ print_term(fmtfn_t fn, void* arg, Eterm obj, long *dcount, } } break; + case HASHMAP_DEF: + { + Uint n,mapval; + Eterm *head; + head = hashmap_val(wobj); + mapval = MAP_HEADER_VAL(*head); + switch (MAP_HEADER_TYPE(*head)) { + case MAP_HEADER_TAG_HAMT_HEAD_BITMAP: + PRINT_STRING(res, fn, arg, "#<"); + PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); + PRINT_STRING(res, fn, arg, ">{"); + WSTACK_PUSH(s,PRT_CLOSE_TUPLE); + n = hashmap_bitcount(mapval); + ASSERT(n < 17); + head += 2; + if (n > 0) { + n--; + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + while (n--) { + WSTACK_PUSH(s, PRT_COMMA); + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + } + } + break; + case MAP_HEADER_TAG_HAMT_NODE_BITMAP: + n = hashmap_bitcount(mapval); + head++; + PRINT_CHAR(res, fn, arg, '<'); + PRINT_UWORD(res, fn, arg, 'x', 0, 1, mapval); + PRINT_STRING(res, fn, arg, ">{"); + WSTACK_PUSH(s,PRT_CLOSE_TUPLE); + ASSERT(n < 17); + if (n > 0) { + n--; + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + while (n--) { + WSTACK_PUSH(s, PRT_COMMA); + WSTACK_PUSH(s, head[n]); + WSTACK_PUSH(s, PRT_TERM); + } + } + break; + } + } + break; default: PRINT_STRING(res, fn, arg, "> _TAG_PRIMARY_SIZE): return EXTERNAL_PID_DEF; case (_TAG_HEADER_EXTERNAL_PORT >> _TAG_PRIMARY_SIZE): return EXTERNAL_PORT_DEF; case (_TAG_HEADER_EXTERNAL_REF >> _TAG_PRIMARY_SIZE): return EXTERNAL_REF_DEF; + case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE): return MAP_DEF; case (_TAG_HEADER_REFC_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; case (_TAG_HEADER_HEAP_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; case (_TAG_HEADER_SUB_BIN >> _TAG_PRIMARY_SIZE): return BINARY_DEF; - case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE): return MAP_DEF; + case (_TAG_HEADER_HASHMAP >> _TAG_PRIMARY_SIZE): return HASHMAP_DEF; } + break; } case TAG_PRIMARY_IMMED1: { diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h index 37014ccf94..fde90997e3 100644 --- a/erts/emulator/beam/erl_term.h +++ b/erts/emulator/beam/erl_term.h @@ -21,6 +21,7 @@ #define __ERL_TERM_H #include "sys.h" /* defines HALFWORD_HEAP */ +#include "erl_hashmap.h" typedef UWord Wterm; /* Full word terms */ @@ -141,6 +142,7 @@ struct erl_node_; /* Declared in erl_node_tables.h */ #define HEAP_BINARY_SUBTAG (0x9 << _TAG_PRIMARY_SIZE) /* BINARY */ #define SUB_BINARY_SUBTAG (0xA << _TAG_PRIMARY_SIZE) /* BINARY */ /* _BINARY_XXX_MASK depends on 0xB being unused */ +#define HASHMAP_SUBTAG (0xB << _TAG_PRIMARY_SIZE) /* HASHMAP */ #define EXTERNAL_PID_SUBTAG (0xC << _TAG_PRIMARY_SIZE) /* EXTERNAL_PID */ #define EXTERNAL_PORT_SUBTAG (0xD << _TAG_PRIMARY_SIZE) /* EXTERNAL_PORT */ #define EXTERNAL_REF_SUBTAG (0xE << _TAG_PRIMARY_SIZE) /* EXTERNAL_REF */ @@ -162,6 +164,7 @@ struct erl_node_; /* Declared in erl_node_tables.h */ #define _TAG_HEADER_EXTERNAL_REF (TAG_PRIMARY_HEADER|EXTERNAL_REF_SUBTAG) #define _TAG_HEADER_BIN_MATCHSTATE (TAG_PRIMARY_HEADER|BIN_MATCHSTATE_SUBTAG) #define _TAG_HEADER_MAP (TAG_PRIMARY_HEADER|MAP_SUBTAG) +#define _TAG_HEADER_HASHMAP (TAG_PRIMARY_HEADER|HASHMAP_SUBTAG) #define _TAG_HEADER_MASK 0x3F @@ -298,7 +301,9 @@ _ET_DECLARE_CHECKED(Uint,atom_val,Eterm) /* header (arityval or thing) access methods */ #define _make_header(sz,tag) ((Uint)(((sz) << _HEADER_ARITY_OFFS) + (tag))) #define is_header(x) (((x) & _TAG_PRIMARY_MASK) == TAG_PRIMARY_HEADER) -#define _unchecked_header_arity(x) ((x) >> _HEADER_ARITY_OFFS) +//#define _unchecked_header_arity(x) ((x) >> _HEADER_ARITY_OFFS) +#define _unchecked_header_arity(x) \ + (is_hashmap_header(x) ? MAP_HEADER_ARITY(x) : ((x) >> _HEADER_ARITY_OFFS)) _ET_DECLARE_CHECKED(Uint,header_arity,Eterm) #define header_arity(x) _ET_APPLY(header_arity,(x)) @@ -361,6 +366,7 @@ _ET_DECLARE_CHECKED(Uint,thing_subtag,Eterm) ((((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_REFC_BIN) || \ (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_HEAP_BIN) || \ (((x) & (_TAG_HEADER_MASK)) == _TAG_HEADER_SUB_BIN)) + #define make_binary(x) make_boxed((Eterm*)(x)) #define is_binary(x) (is_boxed((x)) && is_binary_header(*boxed_val((x)))) #define is_not_binary(x) (!is_binary((x))) @@ -1095,6 +1101,7 @@ _ET_DECLARE_CHECKED(Uint,y_reg_index,Uint) #define FLOAT_DEF 0xe #define BIG_DEF 0xf #define SMALL_DEF 0x10 +#define HASHMAP_DEF 0x11 #if ET_DEBUG extern unsigned tag_val_def_debug(Wterm, const char*, unsigned); diff --git a/erts/emulator/beam/erl_vm.h b/erts/emulator/beam/erl_vm.h index 6e9216bef3..3a9fb1e07b 100644 --- a/erts/emulator/beam/erl_vm.h +++ b/erts/emulator/beam/erl_vm.h @@ -117,9 +117,9 @@ #if defined(DEBUG) || defined(CHECK_FOR_HOLES) #if HALFWORD_HEAP -# define ERTS_HOLE_MARKER (0xaf5e78ccU) +# define ERTS_HOLE_MARKER (0xdeadbeef) #else -# define ERTS_HOLE_MARKER (((0xaf5e78ccUL << 24) << 8) | 0xaf5e78ccUL) +# define ERTS_HOLE_MARKER (((0xdeadbeef << 24) << 8) | 0xdeadbeef) #endif #endif diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h index 5330f389e0..1fb069232a 100644 --- a/erts/emulator/beam/global.h +++ b/erts/emulator/beam/global.h @@ -539,6 +539,12 @@ do { \ } \ } while(0) +#define WSTACK_DEBUG(s) \ + do { \ + fprintf(stderr, "wstack size = %ld\r\n", s.wsp - s.wstart); \ + fprintf(stderr, "wstack wstart = %p\r\n", s.wstart); \ + fprintf(stderr, "wstack wsp = %p\r\n", s.wsp); \ + } while(0) /* * Do not free the stack after this, it may have pointers into what @@ -581,7 +587,7 @@ do { \ ASSERT(s.wsp <= s.wend); \ } while (0) -#define WSTACK_IS_STATIC(s) (s.wstart == WSTK_DEF_STACK(s))) +#define WSTACK_IS_STATIC(s) (s.wstart == WSTK_DEF_STACK(s)) #define WSTACK_PUSH(s, x) \ do { \ @@ -648,7 +654,7 @@ do { \ #define WSTACK_COUNT(s) (s.wsp - s.wstart) #define WSTACK_ISEMPTY(s) (s.wsp == s.wstart) -#define WSTACK_POP(s) (*(--s.wsp)) +#define WSTACK_POP(s) ((ASSERT(s.wsp > s.wstart)),*(--s.wsp)) /* binary.c */ diff --git a/erts/emulator/hipe/hipe_gc.c b/erts/emulator/hipe/hipe_gc.c index b10263f6e2..398cbcdf14 100644 --- a/erts/emulator/hipe/hipe_gc.c +++ b/erts/emulator/hipe/hipe_gc.c @@ -28,6 +28,7 @@ #include "global.h" #include "erl_gc.h" +#include "erl_hashmap.h" #include "hipe_stack.h" #include "hipe_gc.h" -- cgit v1.2.3