summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorAchim Kriso <achim.kriso@student.kit.edu>2019-11-28 14:52:45 +0100
committerAndreas Fried <andreas.fried@kit.edu>2020-03-26 14:08:09 +0100
commit7783369d33d62b9e69892164371889053450f5c4 (patch)
treea1fea4b7ae7dd454272e2032e229343a17a9891d
parenta4672cceb5a83407ba9a70a9b7b613006034073e (diff)
LowFat sanitizer rudimentary implementation
-rw-r--r--Makefile23
-rw-r--r--include/libfirm/firm.h1
-rw-r--r--include/libfirm/lfasan.h8
-rw-r--r--ir/opt/lfasan.c501
-rw-r--r--runtime/lfmalloc/Makefile38
-rw-r--r--runtime/lfmalloc/include/lfdebug.h48
-rw-r--r--runtime/lfmalloc/include/lfinternal.h29
-rw-r--r--runtime/lfmalloc/include/lfmalloc.h23
-rw-r--r--runtime/lfmalloc/include/lfutil.h9
-rw-r--r--runtime/lfmalloc/src/lfdebug.c28
-rw-r--r--runtime/lfmalloc/src/lfinternal.c380
-rw-r--r--runtime/lfmalloc/src/lfmalloc.c150
-rw-r--r--runtime/lfmalloc/src/lfutil.c18
-rwxr-xr-xscripts/gen_lf_sizes.py51
14 files changed, 1304 insertions, 3 deletions
diff --git a/Makefile b/Makefile
index 087e5e4..a1ad54b 100644
--- a/Makefile
+++ b/Makefile
@@ -73,9 +73,10 @@ libfirm_CPPFLAGS = $(foreach dir,$(libfirm_INCLUDEDIRS),-I$(dir))
libfirm_OBJECTS = $(libfirm_SOURCES:%.c=$(builddir)/%.o) $(libfirm_GEN_SOURCES:%.c=$(builddir)/%.o)
libfirm_DEPS = $(libfirm_OBJECTS:%.o=%.d)
libfirm_BUILDDIRS = $(sort $(dir $(libfirm_OBJECTS))) $(addprefix $(gendir)/, $(libfirm_GEN_DIRS))
+libfirm_RUNTIME = $(builddir)/liblfmalloc.a
.PHONY: firm
-firm: $(libfirm_dll) $(libfirm_a)
+firm: $(libfirm_dll) $(libfirm_a) $(libfirm_RUNTIME)
# backends
backends = amd64 arm ia32 mips riscv sparc TEMPLATE
@@ -142,7 +143,7 @@ $(gendir)/include/libfirm/% : scripts/templates/% $(IR_SPEC_GENERATOR_DEPS) $(IR
@echo GEN $@
$(Q)$(IR_SPEC_GENERATOR) $(IR_SPEC) "$<" > "$@"
-libfirm_GEN_DIRS += ir/ir include/libfirm
+libfirm_GEN_DIRS += ir/ir ir/opt include/libfirm
$(libfirm_a): $(libfirm_OBJECTS)
@echo AR $@
@@ -153,12 +154,28 @@ $(libfirm_dll): $(libfirm_OBJECTS)
@echo LINK $@
$(Q)$(LINK) $(LINKDLLFLAGS) $^ -o $@ $(LINKFLAGS)
+# lfmalloc runtime library
+lfpath ?= runtime/lfmalloc
+lfname ?= liblfmalloc
+lf_builddir ?= $(builddir)/lfmalloc
+lf_gen_include ?= $(gendir)/ir/opt
+lf_gen_include_header ?= $(lf_gen_include)/gen_lfasan_sizes.h
+$(lf_gen_include_header): scripts/gen_lf_sizes.py
+ @echo 'GEN $@'
+ $(Q)$< > $@
+
+.PHONY: $(builddir)/$(lfname).a
+$(builddir)/$(lfname).a: $(lf_gen_include_header)
+ $(Q)mkdir -p $(builddir)/lfmalloc
+ $(Q)$(MAKE) sizes_include=../../$(lf_gen_include) builddir=../../$(lf_builddir) -C $(lfpath)
+ $(Q)cp $(builddir)/lfmalloc/$(lfname).a $(builddir) #Always copy, not sure how to fix
+
# Determine if we can use cparser-beta for quickcheck
QUICKCHECK_DEFAULT := $(shell which cparser-beta 2> /dev/null || echo true) -fsyntax-only
QUICKCHECK ?= $(QUICKCHECK_DEFAULT)
QUICKCHECK_FLAGS ?= -m32 -Wno-compat-option -Wno-shadow -Wno-shadow-local -Wunreachable-code
-$(builddir)/%.o: %.c $(IR_SPEC_GENERATED_INCLUDES)
+$(builddir)/%.o: %.c $(IR_SPEC_GENERATED_INCLUDES) $(lf_gen_include_header)
@echo CC $@
$(Q)$(QUICKCHECK) $(QUICKCHECK_FLAGS) $(CFLAGS) $(CPPFLAGS) $(libfirm_CPPFLAGS) $(QUICKCHECK_FLAGS) $<
$(Q)$(CC) $(CFLAGS) $(CPPFLAGS) $(libfirm_CPPFLAGS) -MP -MMD -c -o $@ $<
diff --git a/include/libfirm/firm.h b/include/libfirm/firm.h
index fc74f49..e671713 100644
--- a/include/libfirm/firm.h
+++ b/include/libfirm/firm.h
@@ -107,5 +107,6 @@
#include "tv.h"
#include "typerep.h"
#include "vrp.h"
+#include "lfasan.h"
#endif
diff --git a/include/libfirm/lfasan.h b/include/libfirm/lfasan.h
new file mode 100644
index 0000000..800ad08
--- /dev/null
+++ b/include/libfirm/lfasan.h
@@ -0,0 +1,8 @@
+#ifndef LFASAN_H
+#define LFASAN_h
+
+#include "firm_types.h"
+
+FIRM_API void lowfat_asan(ir_graph *irg);
+
+#endif
diff --git a/ir/opt/lfasan.c b/ir/opt/lfasan.c
new file mode 100644
index 0000000..49e180c
--- /dev/null
+++ b/ir/opt/lfasan.c
@@ -0,0 +1,501 @@
+#include "lfasan.h"
+
+#include "firm_types.h"
+#include "ident.h"
+#include "ircons.h"
+#include "irdom.h"
+#include "irdump.h"
+#include "iredges.h"
+#include "irflag.h"
+#include "irgraph.h"
+#include "irgraph_t.h"
+#include "irmode.h"
+#include "irnode.h"
+#include "irgwalk.h"
+#include "irnode_t.h"
+#include "irop.h"
+#include "irprog.h"
+#include "irprog_t.h"
+#include "irgmod.h"
+#include "tv.h"
+#include "type_t.h"
+#include "typerep.h"
+#include "util.h"
+#include "debug.h"
+#include "pmap.h"
+#include "dbginfo.h"
+
+#include "gen_lfasan_sizes.h"
+
+#include <assert.h>
+#include <stdint.h>
+
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
+
+#define REPLACE(ent, n, x) { \
+ if (streq(n, x)) { \
+ DB((dbg, LEVEL_3, "Replacing '" x "' with 'lf_" x "' in node %+F.\n", \
+ func_ptr)); \
+ set_entity_ld_ident(ent, "lf_" x); \
+ assert(streq(get_entity_ld_name(ent), "lf_" x)); \
+ } \
+}
+
+static void func_ptr_rename(ir_node *irn, void *env) {
+ (void) env;
+ if (is_Call(irn)) {
+ ir_node *func_ptr = get_Call_ptr(irn);
+ assert(streq("Address", get_op_name(get_irn_op(func_ptr))));
+
+ ir_entity *entity = get_irn_entity_attr(func_ptr);
+ const char* ld_name = get_entity_ld_name(entity);
+ DB((dbg, LEVEL_5, "Node %+F with %+F.\n",
+ irn,
+ func_ptr));
+
+ REPLACE(entity, ld_name, "malloc");
+ REPLACE(entity, ld_name, "free");
+ REPLACE(entity, ld_name, "calloc");
+ REPLACE(entity, ld_name, "realloc");
+
+ REPLACE(entity, ld_name, "posix_memalign");
+ REPLACE(entity, ld_name, "aligned_alloc");
+ REPLACE(entity, ld_name, "valloc");
+ REPLACE(entity, ld_name, "memalign");
+ REPLACE(entity, ld_name, "pvalloc");
+ REPLACE(entity, ld_name, "malloc_usable_size");
+ }
+}
+
+#define SIZES_LD_NAME "LF_ASAN_SIZES"
+
+static ir_entity *create_global_lookup_table(void) {
+ ir_graph* const_irg = get_const_code_irg();
+
+ ir_type *glob_type = get_glob_type();
+ int glob_members = get_compound_n_members(glob_type);
+
+ ir_entity* table_entity = NULL;
+ for (int i = 0; i < glob_members; i++) {
+ ir_entity *cur_entity = get_compound_member(glob_type, i);
+ if (streq(get_entity_ld_name(cur_entity), SIZES_LD_NAME)) {
+ table_entity = cur_entity;
+ }
+ }
+ if (table_entity == NULL) {
+ ir_initializer_t* init = create_initializer_compound(ARRAY_SIZE(SIZES));
+ for (uint32_t i = 0; i < ARRAY_SIZE(SIZES); i++) {
+ ir_node* const_node = new_r_Const_long(const_irg, get_modeLu(), SIZES[i]);
+ ir_initializer_t* init_const = create_initializer_const(const_node);
+ set_initializer_compound_value(init, i, init_const);
+ }
+ table_entity = new_entity(get_glob_type(), SIZES_LD_NAME,
+ new_type_array(get_type_for_mode(get_modeLu()), ARRAY_SIZE(SIZES)));
+ set_entity_initializer(table_entity, init);
+ }
+
+ DB((dbg, LEVEL_4, "Global Lookup entity: %+F\n", table_entity));
+ return table_entity;
+}
+
+typedef struct _lfptr_meta {
+ struct _lfptr_meta *next;
+ ir_node *base;
+ ir_node *size;
+} lfptr_meta;
+
+lfptr_meta *lfptr_meta_first = NULL;
+
+/*returns uninitialized lfptr_meta*/
+static lfptr_meta *new_lfptr_meta(ir_node* base, ir_node *size) {
+ lfptr_meta *new = (lfptr_meta*)malloc(sizeof(lfptr_meta));
+ new->next = lfptr_meta_first;
+ new->base = base;
+ new->size = size;
+ lfptr_meta_first = new;
+ return new;
+}
+
+static lfptr_meta *is_alloc_res(ir_node *irn) {
+ if (is_Proj(irn)) {
+ ir_node *call_proj = get_Proj_pred(irn);
+ if (is_Proj(call_proj)) {
+ ir_node* call = get_Proj_pred(call_proj);
+ if (is_Call(call)) {
+ ir_node* ptr = get_Call_ptr(call);
+ const char* ld_name = get_entity_ld_name(get_irn_entity_attr(ptr));
+ /*TODO: also consider other allocation functions.*/
+ if (streq(ld_name, "lf_malloc")) {
+ ir_node* size = get_Call_param(call, 0);
+ return new_lfptr_meta(irn, size);
+ }
+ }
+ }
+ }
+ return NULL;
+}
+
+static lfptr_meta *calc_metadata(ir_node *irn, ir_node *sizes_lookup) {
+ dbg_info *dbgi = get_irn_dbg_info_(irn);
+
+ assert(get_irn_mode(irn) == get_modeP());
+ ir_node *block = get_nodes_block(irn);
+ ir_graph *irg = get_irn_irg(irn);
+ ir_node *nomem = get_irg_no_mem(irg);
+ mark_irn_visited(sizes_lookup);
+
+ ir_node *const_region_bits = new_r_Const_long(irg, get_modeLu(), REGION_BITS);
+ ir_node *conv_p_lu = new_rd_Conv(dbgi, block, irn, get_modeLu());
+ ir_node *index = new_rd_Shr(dbgi, block, conv_p_lu, const_region_bits);
+ ir_node *byte_offset = new_rd_Mul(dbgi, block, index,
+ new_rd_Const_long(dbgi, irg, get_modeLu(), 8));
+ ir_node *conv_lu_ls = new_rd_Conv(dbgi, block, byte_offset, get_modeLs());
+ ir_node *size_address = new_rd_Add(dbgi, block, sizes_lookup, conv_lu_ls);
+ mark_irn_visited(size_address);
+
+ ir_node *load = new_rd_Load(dbgi, block, nomem, size_address,
+ get_modeLu(), get_type_for_mode(get_modeLu()), cons_none);
+ ir_node *size = new_rd_Proj(dbgi, load, get_modeLu(), pn_Load_res);
+ mark_irn_visited(size);
+
+ ir_node *mod = new_rd_Mod(dbgi, block, nomem, conv_p_lu, size, false);
+ ir_node *mod_res = new_rd_Proj(dbgi, mod, get_modeLu(), pn_Mod_res);
+ ir_node *conv_mod_res = new_rd_Conv(dbgi, block, mod_res, get_modeLs());
+ ir_node *sub = new_rd_Sub(dbgi, block, irn, conv_mod_res);
+ ir_node *base = new_rd_Conv(dbgi, block, sub, get_modeP());
+ mark_irn_visited(base);
+
+ lfptr_meta *res = new_lfptr_meta(base, size);
+ return res;
+}
+
+static void pp_metadata_map(pmap* map) {
+ if (pmap_count(map) == 0) {
+ DB((dbg, LEVEL_5, "metadata map is empty\n"));
+ return;
+ }
+
+ foreach_pmap(map, cur) {
+ lfptr_meta* ptr = (lfptr_meta*) cur->key;
+ lfptr_meta* meta = (lfptr_meta*) cur->value;
+ DB((dbg, LEVEL_5, "%+F\t->\tbase: %+F, size: %+F\n", ptr, meta->base, meta->size));
+ }
+}
+
+static void move_node(ir_node *node, ir_node *to_bl)
+{
+ set_nodes_block(node, to_bl);
+ /* if no mode_T node, do not move Projs. Note that BadT shouldn't have
+ * any Projs as well and is part of the start_block list and therefore
+ * doesn't have a valid Proj list */
+ if (get_irn_mode(node) != mode_T || is_Bad(node))
+ return;
+
+ for (ir_node *proj = (ir_node*)get_irn_link(node);
+ proj != NULL; proj = (ir_node*)get_irn_link(proj)) {
+ set_nodes_block(proj, to_bl);
+ }
+}
+
+/**
+ * Moves node and all predecessors of node from from_bl to to_bl.
+ * Does not move predecessors of Phi nodes (or block nodes).
+ */
+static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
+{
+ if (get_nodes_block(node) != from_bl) {
+ return;
+ }
+
+ move_node(node, to_bl);
+
+ if (is_Phi(node))
+ return;
+
+ /* recursion ... */
+ foreach_irn_in(node, i, pred) {
+ if (get_nodes_block(pred) == from_bl)
+ move(pred, from_bl, to_bl);
+ }
+}
+
+static ir_entity* string_literal(char const* string) {
+ ir_graph* const_irg = get_const_code_irg();
+
+ long len = strlen(string) + 1; //including 0-terminator
+
+ ir_initializer_t* init = create_initializer_compound(len);
+ for (uint32_t i = 0; i < len; i++) {
+ ir_node* const_node = new_r_Const_long(const_irg, get_modeBu(), string[i]);
+ ir_initializer_t *init_const = create_initializer_const(const_node);
+ set_initializer_compound_value(init, i, init_const);
+ }
+ ir_type *type = new_type_array(get_type_for_mode(get_modeBu()), len);
+ ir_entity *entity = new_entity(get_glob_type(), id_unique(string), type);
+ set_entity_initializer(entity, init);
+ return entity;
+}
+
+/* Returns the Call node to lf_error for the node irn (which is the OOB pointer) */
+static ir_node* error_call(ir_node *irn, ir_node *block, pmap* lf_map,
+ unsigned int reason) {
+ dbg_info *dbgi = get_irn_dbg_info(irn);
+ ir_graph *irg = get_irn_irg(irn);
+
+ src_loc_t src_loc = ir_retrieve_dbg_info(dbgi);
+ ir_node *line_const = new_rd_Const_long(dbgi, irg, get_modeIu(), src_loc.line); /*if dbg info doesn't exist src_loc.line is 0, which is considered by lf_error*/
+
+ ir_node *file_name;
+ if (src_loc.file != NULL) {
+ ir_entity *file_entity = string_literal(src_loc.file);
+ file_name = new_rd_Address(dbgi, irg, file_entity);
+ } else {
+ file_name = new_r_Const_long(irg, get_modeP(), 0);
+ }
+
+ lfptr_meta *meta = pmap_find(lf_map, irn)->value;
+ assert(meta != NULL);
+ ir_node *base = meta->base;
+ ir_node *size = meta->size;
+
+ ir_node *reason_const = new_rd_Const_long(dbgi, irg, get_modeIu(), reason);
+
+ ir_node *error_args[6] = { irn, base, size, reason_const, file_name, line_const };
+
+ static ir_entity* abort_entity = NULL;
+ ir_type *glob_type = get_glob_type();
+ if (abort_entity == NULL) {
+ ir_type *abort_type = new_type_method(ARRAY_SIZE(error_args), 0, false,
+ cc_cdecl_set, mtp_property_noreturn | mtp_property_nothrow);
+ set_method_param_type(abort_type, 0, get_type_for_mode(get_modeP()));
+ set_method_param_type(abort_type, 1, get_type_for_mode(get_modeP()));
+ set_method_param_type(abort_type, 2, get_type_for_mode(get_modeLu()));
+ set_method_param_type(abort_type, 3, get_type_for_mode(get_modeIu()));
+ set_method_param_type(abort_type, 4, get_type_for_mode(get_modeP()));
+ set_method_param_type(abort_type, 5, get_type_for_mode(get_modeIu()));
+ abort_entity = new_entity(glob_type, "lf_error", abort_type);
+ }
+ assert(abort_entity != NULL);
+
+ ir_node *abort_address = new_rd_Address(dbgi, irg, abort_entity);
+ mark_irn_visited(abort_address);
+ ir_node *abort_call = new_rd_Call(dbgi, block, get_irg_no_mem(irg), abort_address,
+ ARRAY_SIZE(error_args), error_args,
+ get_entity_type(abort_entity));
+ return abort_call;
+}
+
+static void insert_bound_check_between(ir_node *irn, ir_node *ptr, pmap *lf_map,
+ unsigned int reason) {
+ dbg_info *dbgi = get_irn_dbg_info(irn);
+
+ assert(get_irn_mode(ptr) == get_modeP());
+ assert(pmap_contains(lf_map, ptr));
+ DB((dbg, LEVEL_5, "inserting check between %+F and %+F\n", irn, ptr));
+
+ ir_graph *irg = get_irn_irg(irn);
+
+ ir_node *old_block = get_nodes_block(ptr);
+ DB((dbg, LEVEL_5, "old block: %+F\n", old_block));
+ part_block(ptr);
+ ir_node *new_block = get_nodes_block(ptr);
+ DB((dbg, LEVEL_5, "new block: %+F\n", new_block));
+
+ assert(pmap_contains(lf_map, ptr));
+ lfptr_meta *meta = (lfptr_meta*)pmap_find(lf_map, ptr)->value;
+ ir_node *base = meta->base;
+ ir_node *size = meta->size;
+
+ move(base, old_block, new_block);
+ move(size, old_block, new_block);
+
+ ir_node *start = base;
+ assert(get_irn_mode(base) == get_modeP());
+ ir_node *end = new_rd_Add(dbgi, new_block, base,
+ new_rd_Conv(dbgi, new_block, size, get_modeLs()));
+ mark_irn_visited(end);
+
+ ir_node *cmp_lower = new_rd_Cmp(dbgi, new_block, start, ptr, ir_relation_less_equal);
+ ir_node *cmp_upper = new_rd_Cmp(dbgi, new_block, end, ptr, ir_relation_greater);
+
+ ir_node *in_bounds = new_rd_And(dbgi, new_block, cmp_lower, cmp_upper);
+
+ ir_node *cond = new_rd_Cond(dbgi, new_block, in_bounds);
+ mark_irn_visited(cond);
+ ir_node *proj_true = new_rd_Proj(dbgi, cond, get_modeX(), pn_Cond_true);
+ ir_node *proj_false = new_rd_Proj(dbgi, cond, get_modeX(), pn_Cond_false);
+
+ ir_node *bb_false_in[1] = { proj_false };
+ ir_node *bb_err = new_rd_Block(dbgi, irg, ARRAY_SIZE(bb_false_in), bb_false_in);
+
+ ir_node* abort_call = error_call(ptr, bb_err, lf_map, reason);
+ mark_irn_visited(abort_call);
+ keep_alive(abort_call);
+ keep_alive(bb_err);
+
+ ir_node* bb_true_in[1] = { proj_true };
+ set_irn_in(old_block, ARRAY_SIZE(bb_true_in), bb_true_in);
+}
+
+typedef struct {
+ pmap *lf_map;
+ ir_node *sizes_address;
+ lfptr_meta *nonlf_meta;
+} insert_instrumentation_env;
+
+static void insert_instrumentation(ir_node *irn, void * env) {
+ pmap *lf_map = ((insert_instrumentation_env*)env)->lf_map;
+ ir_node *sizes_address = ((insert_instrumentation_env*)env)->sizes_address;
+ lfptr_meta *nonlf_meta = ((insert_instrumentation_env*)env)->nonlf_meta;
+ mark_irn_visited(nonlf_meta->base);
+ mark_irn_visited(nonlf_meta->size);
+
+ dbg_info *dbgi = get_irn_dbg_info(irn);
+
+ ir_mode *mode = get_irn_mode(irn);
+ if (is_Block(irn)) {
+ return;
+ }
+ ir_node *block = get_nodes_block(irn);
+
+ if (mode == get_modeP()) {
+ lfptr_meta* meta = is_alloc_res(irn);
+ if (meta != NULL) {
+ DB((dbg, LEVEL_5, "Newly allocated pointer %+F with base: %+F, size: %+F\n", irn, meta->base, meta->size));
+ assert(get_irn_mode(meta->base) == get_modeP());
+ assert(get_irn_mode(meta->size) == get_modeLu());
+ pmap_insert(lf_map, meta->base, meta);
+ } else if (is_Add(irn)) {
+ DB((dbg, LEVEL_5, "%+F", irn));
+ ir_node* left = get_Add_left(irn);
+ ir_node* right = get_Add_right(irn);
+ ir_node* p_pred = NULL;
+ /*TODO: is this necessary? Maybe Add always has ptr on one side.*/
+ if (get_irn_mode(left) == get_modeP()) {
+ assert(pmap_contains(lf_map, left));
+ p_pred = left;
+ } else if (get_irn_mode(right) == get_modeP()) {
+ assert(pmap_contains(lf_map, right));
+ p_pred = right;
+ }
+ assert(p_pred != NULL);
+ lfptr_meta *add_meta = pmap_find(lf_map, left)->value;
+ pmap_insert(lf_map, irn, add_meta);
+ DB((dbg, LEVEL_5, " with transitive base: %+F, size: %+F inherited from %+F\n", add_meta->base, add_meta->size, p_pred));
+ } else if (is_Const(irn) || is_Address(irn)) {
+ pmap_insert(lf_map, irn, nonlf_meta);
+ DB((dbg, LEVEL_5, "%+F with default meta\n", irn));
+ } else if (is_Phi(irn)) {
+ DB((dbg, LEVEL_5, "Phi %+F", irn));
+ int phi_arity = get_Phi_n_preds(irn);
+ ir_node **base_phi_preds = (ir_node**)malloc(sizeof(ir_node*) * phi_arity);
+ ir_node **size_phi_preds = (ir_node**)malloc(sizeof(ir_node*) * phi_arity);
+ for (int i = 0; i < phi_arity; i++) {
+ lfptr_meta* meta = pmap_find(lf_map, get_Phi_pred(irn, i))->value;
+ base_phi_preds[i] = meta->base;
+ size_phi_preds[i] = meta->size;
+ }
+ ir_node *base_phi = new_rd_Phi(dbgi, block, phi_arity, base_phi_preds, get_modeP());
+ ir_node *size_phi = new_rd_Phi(dbgi, block, phi_arity, size_phi_preds, get_modeLu());
+ add_Block_phi(block, base_phi);
+ add_Block_phi(block, size_phi);
+ mark_irn_visited(base_phi);
+ mark_irn_visited(size_phi);
+ assert(get_irn_mode(base_phi) == get_modeP());
+ assert(get_irn_mode(size_phi) == get_modeLu());
+ pmap_insert(lf_map, irn, new_lfptr_meta(base_phi, size_phi));
+ DB((dbg, LEVEL_5, " with base: %+F, size: %+F\n", base_phi, size_phi));
+ } else {
+ DB((dbg, LEVEL_5, "Unknown Pointer %+F", irn));
+ lfptr_meta* meta = calc_metadata(irn, sizes_address);
+ assert(get_irn_mode(meta->base) == get_modeP());
+ assert(get_irn_mode(meta->size) == get_modeLu());
+ pmap_insert(lf_map, irn, meta);
+ DB((dbg, LEVEL_5, " with calculated metadata: base: %+F, size: %+F\n",
+ meta->base, meta->size));
+ }
+ } else if (is_Store(irn)) {
+ ir_node* ptr = get_Store_ptr(irn);
+ insert_bound_check_between(irn, ptr, lf_map, 0);
+ } else if (is_Load(irn)) {
+ ir_node* ptr = get_Load_ptr(irn);
+ insert_bound_check_between(irn, ptr, lf_map, 1);
+ } else if (is_Call(irn)) {
+ int call_params = get_Call_n_params(irn);
+ for (int i = 0; i < call_params; i++) {
+ ir_node *param = get_Call_param(irn, i);
+ DB((dbg, LEVEL_5, "%+F and %+F\n", irn, param));
+ if (get_irn_mode(param) == get_modeP()) {
+ insert_bound_check_between(irn, param, lf_map, 2);
+ }
+ }
+ }
+}
+
+/*
+ * During the second phase const nodes move into other blocks, which causes dominace issues.
+ * This pass moves them back to the start block.
+ * Hacky but it works.
+ */
+static void fix_const_nodes(ir_node *irn, void *env) {
+ (void) env;
+ if (is_Const(irn) || is_Address(irn)) {
+ ir_graph *irg = get_irn_irg(irn);
+ ir_node *start_node = get_irg_start(irg);
+ ir_node *start_block = get_nodes_block(start_node);
+ set_nodes_block(irn, start_block);
+ }
+}
+
+FIRM_API void lowfat_asan(ir_graph *irg) {
+ //assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+ collect_phiprojs_and_start_block_nodes(irg);
+
+ int opt_level = get_optimize();
+ set_optimize(0);
+
+ FIRM_DBG_REGISTER(dbg, "firm.opt.lfasan");
+ DB((dbg, LEVEL_1, "\n===> instrumenting %+F for lowfat adresssanitizer.\n", irg));
+
+ DB((dbg, LEVEL_2, "=> Replacing memory functions with lowfat alternatives.\n"));
+ irg_walk_graph(irg, NULL, func_ptr_rename, NULL);
+
+ DB((dbg, LEVEL_2, "=> Creating global lookup table.\n"));
+ ir_entity *sizes_entity = create_global_lookup_table();
+ ir_node *sizes_address = new_r_Address(irg, sizes_entity);
+ DB((dbg, LEVEL_4, "Global Lookup node: %+F\n", sizes_address));
+
+ DB((dbg, LEVEL_2, "=> Inserting instrumentation nodes.\n"));
+ pmap* lf_map = pmap_create(); /*ir_node -> lfptr_meta*/
+ lfptr_meta *nonlf_meta = new_lfptr_meta(new_r_Const_long(irg, get_modeP(), 0),
+ new_r_Const_long(irg, get_modeLu(), -1));
+ insert_instrumentation_env env;
+ env.lf_map = lf_map;
+ env.sizes_address = sizes_address;
+ env.nonlf_meta = nonlf_meta;
+ irg_walk_graph(irg, NULL, insert_instrumentation, &env);
+
+ DB((dbg, LEVEL_5, "-metadata-map-----------------------------------------\n"));
+ pp_metadata_map(lf_map);
+
+ DB((dbg, LEVEL_2, "=> Fixing blocks of const/address nodes.\n"));
+ irg_walk_graph(irg, NULL, fix_const_nodes, NULL);
+
+ /*Freeing allocated memory*/
+ lfptr_meta* cur = lfptr_meta_first;
+ while (cur != NULL) {
+ lfptr_meta* f = cur;
+ cur = cur->next;
+ free(f);
+ }
+ lfptr_meta_first = NULL;
+ pmap_destroy(lf_map);
+ DB((dbg, LEVEL_2, "Done instrumenting %+F\n", irg));
+
+ set_optimize(opt_level);
+ dump_ir_graph(irg, "lf-asan");
+
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
+}
diff --git a/runtime/lfmalloc/Makefile b/runtime/lfmalloc/Makefile
new file mode 100644
index 0000000..716b6d6
--- /dev/null
+++ b/runtime/lfmalloc/Makefile
@@ -0,0 +1,38 @@
+ifneq ($(V),1)
+Q ?= @
+endif
+
+name ?= liblfmalloc
+
+sizes_include ?=
+
+includedir ?= include
+srcdir ?= src
+builddir ?= build
+#gendir ?= $(builddir)/gen
+
+sources ?= $(wildcard $(srcdir)/*.c)
+headers ?= $(wildcard $(includedir)/*.h) $(sizes_include)
+objects ?= $(sources:$(srcdir)/%.c=$(builddir)/%.o)
+
+CFLAGS ?= -ggdb -pthread -Wall -fPIC
+
+$(builddir)/$(name).a: $(objects)
+ @echo 'AR $@'
+ $(Q)ar rcs $(builddir)/$(name).a $(objects)
+
+$(builddir)/$(name).so: CFLAGS += -DLF_DYNAMIC_LIB
+$(builddir)/$(name).so: $(objects)
+ @echo 'LINK $@'
+ $(Q)gcc -shared -o $(builddir)/$(name).so $(objects)
+
+$(builddir)/%.o: $(srcdir)/%.c $(headers)
+ @echo 'CC $@'
+ $(Q)gcc -c $< $(CFLAGS) -I $(includedir) -I $(sizes_include) -o $@
+
+.PHONY: clean
+
+clean:
+ -$(Q)rm -rf $(builddir)
+
+print-% : ; @echo $* = $($*)
diff --git a/runtime/lfmalloc/include/lfdebug.h b/runtime/lfmalloc/include/lfdebug.h
new file mode 100644
index 0000000..20df2d5
--- /dev/null
+++ b/runtime/lfmalloc/include/lfdebug.h
@@ -0,0 +1,48 @@
+#ifndef LFDEBUG_h
+#define LFDEBUG_h
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <fcntl.h>
+#include <sys/types.h>
+#include <sys/syscall.h>
+
+void __disable_lf_alloc();
+void __enable_lf_alloc();
+bool __lf_alloc_enabled();
+pthread_t __current_thread_id();
+
+#define USE_STDLIB(x) {__disable_lf_alloc(); x; __enable_lf_alloc();}
+
+/*#define PRINTF_DBG(...) {\
+ pthread_t tid = __current_thread_id();\
+ USE_STDLIB(fprintf(stderr, "lfmalloc (0x%lx): ", tid))\
+ USE_STDLIB(fprintf(stderr, __VA_ARGS__))\
+}*/
+#define PRINTF_DBG(...)
+
+#ifndef NDEBUG
+#define PRINTF_ASSERT(...) USE_STDLIB(fprintf(stderr, "lfmalloc: " __VA_ARGS__))
+#define LF_ASSERT(x) \
+ do { if (!(x)) { \
+ PRINTF_ASSERT("%s: %i: %s: Assertion '%s' failed.\n", __FILE__, __LINE__, __func__, #x); \
+ abort(); \
+ } } while (0);
+#define LF_ASSERT_EQ(a,b) \
+ do { if ((a) != (b)) { \
+ PRINTF_ASSERT("%s: %i: %s: Assertion '%s == %s' (0x%lx == 0x%lx) failed.\n", __FILE__, __LINE__, __func__, #a, #b, (uint64_t)a, (uint64_t)b); \
+ abort(); \
+ } } while (0);
+#define LF_ASSERT_NE(a,b) \
+ do { if ((a) == (b)) { \
+ PRINTF_ASSERT("%s: %i: %s: Assertion '%s != %s# (0x%lx != 0x%lx) failed.\n", __FILE__, __LINE__, __func__, #a, #b, (uint64_t)a, (uint64_t)b); \
+ abort(); \
+ } } while(0);
+#else
+#define LF_ASSERT(x) do { (void) sizeof(x); } while (0);
+#define LF_ASSERT_EQ(a, b) do { (void) sizeof(a); (void) sizeof(b); } while (0);
+#define LF_ASSERT_NE(a, b) do { (void) sizeof(a); (void) sizeof(b); } while (0);
+#endif
+
+#endif
diff --git a/runtime/lfmalloc/include/lfinternal.h b/runtime/lfmalloc/include/lfinternal.h
new file mode 100644
index 0000000..2636c39
--- /dev/null
+++ b/runtime/lfmalloc/include/lfinternal.h
@@ -0,0 +1,29 @@
+#ifndef LFMALLOC_H
+#define LFMALLOC_H
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+uint64_t __lf_index(void* p);
+uint64_t __lf_size(void* p);
+void* __lf_base(void* p);
+
+void __allocate_regions();
+void __init_region(void* base);
+
+uint64_t __lf_search_region_index(uint64_t size);
+
+void *__lf_malloc(size_t size);
+void __lf_free(void* ptr);
+
+void *__lf_memalign(size_t alignment, size_t size);
+
+size_t __lf_usable_size(void* ptr);
+
+bool is_pow_two(size_t x);
+
+void __lf_error(void *ptr, void* base, unsigned long size, unsigned int reason,
+ char* filename, unsigned int line);
+
+#endif
diff --git a/runtime/lfmalloc/include/lfmalloc.h b/runtime/lfmalloc/include/lfmalloc.h
new file mode 100644
index 0000000..4142059
--- /dev/null
+++ b/runtime/lfmalloc/include/lfmalloc.h
@@ -0,0 +1,23 @@
+#ifndef LFALLOC_H
+#define LFALLOC_H
+
+#include<stdlib.h>
+
+void *lf_malloc(size_t size);
+void lf_free(void *ptr);
+void *lf_calloc(size_t nmemb, size_t size);
+void *lf_realloc(void *ptr, size_t size);
+
+int lf_posix_memalign(void **memptr, size_t alignment, size_t size);
+void *lf_aligned_alloc(size_t alignment, size_t size);
+void *lf_valloc(size_t size);
+
+void *lf_memalign(size_t alignment, size_t size);
+void *lf_pvalloc(size_t size);
+
+size_t lf_malloc_usable_size(void *ptr);
+
+void lf_error(void *ptr, void* base, unsigned long size, unsigned int reason,
+ char* filename, unsigned int line);
+
+#endif
diff --git a/runtime/lfmalloc/include/lfutil.h b/runtime/lfmalloc/include/lfutil.h
new file mode 100644
index 0000000..24d2b9e
--- /dev/null
+++ b/runtime/lfmalloc/include/lfutil.h
@@ -0,0 +1,9 @@
+#ifndef LFUTIL_H
+#define LFUTIL_H
+
+#include <stdint.h>
+
+uint64_t lcm(uint64_t a, uint64_t b);
+uint64_t gcd(uint64_t a, uint64_t b);
+
+#endif
diff --git a/runtime/lfmalloc/src/lfdebug.c b/runtime/lfmalloc/src/lfdebug.c
new file mode 100644
index 0000000..6c25e98
--- /dev/null
+++ b/runtime/lfmalloc/src/lfdebug.c
@@ -0,0 +1,28 @@
+#include <stdbool.h>
+#include <pthread.h>
+#include <threads.h>
+
+#include "lfdebug.h"
+
+// Defines whether lfmalloc or stdlib malloc is used.
+// This is used to allow lfmalloc call stdlib function which use malloc internally
+// without creating an infinite recursion.
+// Thread local to prevent race conditions.
+__thread bool lfmalloc_active = true;
+
+
+void __disable_lf_alloc() {
+ lfmalloc_active = false;
+}
+
+void __enable_lf_alloc() {
+ lfmalloc_active = true;
+}
+
+bool __lf_alloc_enabled() {
+ return lfmalloc_active;
+}
+
+pthread_t __current_thread_id() {
+ return pthread_self();
+}
diff --git a/runtime/lfmalloc/src/lfinternal.c b/runtime/lfmalloc/src/lfinternal.c
new file mode 100644
index 0000000..456eed8
--- /dev/null
+++ b/runtime/lfmalloc/src/lfinternal.c
@@ -0,0 +1,380 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <sys/cdefs.h>
+#include <sys/mman.h>
+#include <stdbool.h>
+
+#include <pthread.h>
+
+#include "lfinternal.h"
+#include "lfutil.h"
+#include "lfdebug.h"
+
+extern void* __libc_malloc(size_t size);
+extern void* __libc_memalign(size_t alignment, size_t size);
+extern void __libc_free(void* ptr);
+
+#include "gen_lfasan_sizes.h" // defines SIZES and REGION_COUNT
+
+//const uint64_t REGION_BITS = 32;
+//const uint64_t REGION_SIZE = ((uint64_t)1 << REGION_BITS);
+//const uint64_t START_REGION = 0x100000000; //Beginning of Region 1;
+//const uint64_t MAX_SIZE = (1 << 30);
+
+bool lfmalloc_init = false;
+
+//Represents a region with possible allocations of a specific size
+//The region has two parts.
+//The first part is a freelist.
+//The second is contigous unallocated memory called remainder.
+//head points to the beginning of the freelist.
+//tail points to the beginning of the remainder.
+//if the freelist is full, the tail is moved into the remainder, therefore reducing its size. The newly available space is now used in the freelist.
+//if head == tail, the freelist is filled up.
+//if head is NULL the region is filled up. (in this case tail has to be null aswell)
+//To improve multithreaded performance, each region has a mutex, so that
+//multiple threads can allocate different sizes at the same time.
+typedef struct region {
+ void* head;
+ void* tail;
+ pthread_mutex_t mutex;
+} region;
+
+region region_freelists[REGION_COUNT] = { NULL };
+
+//If malloc is called with size zero, the address of this global is returned.
+//Some functions (regcomp) expect malloc to return a unique address if size == 0,
+//and think NULL always means nomem.
+const char zero_addr;
+
+void __map_region_space() {
+ PRINTF_DBG("Allocating regions\n")
+ for (int i = 1; i < REGION_COUNT; i++) {
+ void *s =
+ mmap((void *)(REGION_SIZE * i), REGION_SIZE, PROT_READ | PROT_WRITE,
+ MAP_NORESERVE | MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0);
+ LF_ASSERT_NE(s, NULL);
+ // printf("mmap pointer: %p\n", s);
+ }
+}
+
+uint64_t __lf_index(void* p) {
+ return (uint64_t)p >> REGION_BITS;
+}
+
+uint64_t __lf_size(void* p) {
+ return SIZES[__lf_index(p)];
+}
+
+void* __lf_base(void* p) {
+ uint64_t size = __lf_size(p);
+ return (void*)(((uint64_t)p / size) * size);
+}
+
+void* __region_base(void* p) {
+ return (void*)(((uint64_t)-1 << REGION_BITS) & (uint64_t)p);
+}
+
+void __init_region(void* base) {
+ LF_ASSERT_EQ(base, __region_base(base));
+ region r;
+ r.head = base;
+ r.tail = base;
+ if (pthread_mutex_init(&r.mutex, NULL) != 0) {
+ PRINTF_DBG("Couldnt init mutex");
+ abort();
+ }
+ region_freelists[__lf_index(base)] = r;
+}
+
+uint64_t __lf_search_region_index(uint64_t size) {
+ // linear search through SIZES. TODO: Maybe optimize somehow
+ for (int i = 1; 1; i++) {
+ if (SIZES[i] < UINT64_MAX && SIZES[i] >= size) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+void* __allocate_in_region(size_t region_idx, size_t size) {
+ region* r = &region_freelists[region_idx];
+ if (r->head == NULL) {
+ PRINTF_DBG("failed: region filled up, deferring to __libc_malloc\n");
+ return __libc_malloc(size);
+ } else {
+ PRINTF_DBG(
+ "allocating 0x%lx bytes, in region: %lu (0x%lx) at %p\n",
+ size,
+ region_idx,
+ SIZES[region_idx],
+ r->head
+ );
+ }
+
+ void* p = r->head;
+ if (r->head == r->tail) { //Freelist filled: use remainder
+ uint64_t new_tail = (uint64_t)r->tail + SIZES[region_idx];
+
+ if (new_tail >= REGION_SIZE * region_idx + REGION_SIZE) {
+ r->tail = NULL;
+ PRINTF_DBG("failed: region %lu was filled up.\n", region_idx);
+ } else {
+ r->tail = (void*) new_tail;
+ }
+ r->head = r->tail;
+ } else { // remove first element from freelist
+ r->head = *(void**)r->head;
+ }
+ return p;
+}
+
+void __deallocate_in_region(size_t region_idx, void* ptr) {
+ region* r = &region_freelists[region_idx];
+ *(void**) ptr = r->head;
+ r->head = ptr;
+}
+
+void* __freelist_end(size_t region_idx) {
+ region* r = &region_freelists[region_idx];
+ void* prev = &r->head;
+ while (*(void**)prev != r->tail) {
+ prev = *(void**) prev;
+ }
+ return prev;
+}
+
+// Allocate memory at ptr, if impossible return NULL otherwise ptr
+void* __allocate_fixed_in_region(size_t region_idx, void* ptr) {
+ region* r = &region_freelists[region_idx];
+ uint64_t region_base = region_idx * REGION_SIZE;
+ if ((uint64_t)ptr < region_base || (uint64_t)ptr > region_base + REGION_SIZE) {
+ return NULL; //ptr is not in region.
+ }
+ if ((uint64_t)ptr % SIZES[region_idx] != 0) {
+ return NULL; //ptr is not aligned
+ }
+
+ if (ptr < r->tail) {
+ //ptr located in freelist
+ void* prev = &r->head;
+ void* next = r->head;
+ while(next != r->tail) {
+ if (next == ptr) {
+ //ptr found in freelist
+ *(void**) prev = *(void**)next;
+ return ptr;
+ }
+ prev = next;
+ next = *(void**)next;
+ }
+ return NULL; //ptr not found in freelist.
+ } else {
+ //ptr located in remainder
+ if (ptr == r->tail) {
+ void* e = __freelist_end(region_idx);
+ r->tail = ptr + SIZES[region_idx];
+ *(void**)e = r->tail;
+ } else {
+ void* prev = r->tail;
+ void* next = prev + SIZES[region_idx];
+ r->tail = ptr + SIZES[region_idx];
+ while (next < ptr) {
+ *(void**) prev = next;
+ prev = next;
+ next += SIZES[region_idx];
+ }
+ *(void**) prev = r->tail;
+ }
+ return ptr;
+ }
+}
+
+void __lock_region(size_t region_idx) {
+ pthread_mutex_lock(&region_freelists[region_idx].mutex);
+}
+
+void __unlock_region(size_t region_idx) {
+ pthread_mutex_unlock(&region_freelists[region_idx].mutex);
+}
+
+//TODO: lock entire allocator when initializing it
+void __init() {
+ // lf_malloc initialization: mmap syscalls and freelist init
+ if (!lfmalloc_init) {
+ __map_region_space();
+ for (int i = 1; i < REGION_COUNT; i++) {
+ __init_region((void *)(REGION_SIZE * i));
+ }
+ lfmalloc_init = true;
+ }
+}
+
+void *__lf_malloc(size_t size) {
+ if (!__lf_alloc_enabled()) {
+ return __libc_malloc(size);
+ }
+ //Allow stdlib to use stdlib malloc
+ __init();
+
+ // refer to libc_malloc if size is too large
+ if (size > MAX_SIZE) {
+ PRINTF_DBG("size (0x%lx) too large, deferring to __libc_malloc.\n", size);
+ return __libc_malloc(size);
+
+ } else if (size == 0) {
+ PRINTF_DBG("failed: size = 0\n");
+ return (void*) &zero_addr;
+ }
+
+ // actual lf_malloc allocation
+ uint64_t region_idx = __lf_search_region_index(size);
+ __lock_region(region_idx);
+ void* p = __allocate_in_region(region_idx, size);
+ __unlock_region(region_idx);
+
+ return p;
+}
+
+void __lf_free(void* ptr) {
+ if (!__lf_alloc_enabled()) {
+ return __libc_free(ptr);
+ }
+ if (ptr == NULL) {
+ PRINTF_DBG("freeing NULL\n");
+ return;
+ }
+ if (ptr == (void*)&zero_addr) {
+ PRINTF_DBG("freeing zero allocation.\n");
+ return;
+ }
+
+ void* base = __lf_base(ptr);
+ uint64_t region_idx = __lf_index(ptr);
+ PRINTF_DBG("freeing pointer %p, region: %lu (0x%lx), base %p\n", ptr, region_idx, SIZES[region_idx], base);
+ if (region_idx > 0 && region_idx < REGION_COUNT) { //ptr is in a region.
+ LF_ASSERT_EQ(base, ptr);
+ __lock_region(region_idx);
+ __deallocate_in_region(region_idx, ptr);
+ __unlock_region(region_idx);
+ } else {
+ PRINTF_DBG("freeing pointer (%p) outside of regions: defering to __libc_free\n", ptr);
+ __libc_free(ptr);
+ }
+}
+
+bool is_pow_two(size_t x) {
+ size_t s = 2;
+ for (int i = 0; i < sizeof(size_t) * 8; i++) {
+ if (s == x)
+ return true;
+ else
+ s <<= 1;
+ }
+ return false;
+}
+
+#define DBG_MEMALIGN_RESULT(p) PRINTF_DBG("memalign allocated at %p\n", p)
+#define CORRECT_ALIGNMENT(a, x) (((uint64_t)(a - 1) & (uint64_t)x) == 0)
+
+void *__lf_memalign(size_t alignment, size_t size) {
+ if (!__lf_alloc_enabled()) {
+ return __libc_memalign(alignment, size);
+ }
+ __init();
+
+ if (!is_pow_two(alignment)) {
+ PRINTF_DBG("failed: alignment not power of two.\n");
+ return NULL;
+ }
+ if (alignment >= REGION_SIZE) {
+ PRINTF_DBG("failed: alignment too large\n");
+ return NULL;
+ }
+
+ size_t region_idx = __lf_search_region_index(size);
+ __lock_region(region_idx);
+ region* r = &region_freelists[region_idx];
+ PRINTF_DBG("memalign allocation in region %lu (0x%lx)\n", region_idx, SIZES[region_idx]);
+ //First look in freelist for aligned spot
+ void* prev = &r->head;
+ void* next = r->head;
+ while (next != r->tail) {
+ if (CORRECT_ALIGNMENT(alignment, next)) {
+ *(void**)prev = *(void**)next;
+ DBG_MEMALIGN_RESULT(next);
+ __unlock_region(region_idx);
+ return next;
+ }
+ next = *(void**)next;
+ }
+
+ //otherwise take from remainder
+ if (CORRECT_ALIGNMENT(alignment, r->tail)) {
+ void *p = __allocate_fixed_in_region(region_idx, r->tail);
+ LF_ASSERT_NE(p, NULL);
+ DBG_MEMALIGN_RESULT(p);
+ __unlock_region(region_idx);
+ return p;
+ }
+ //next aligned address after tail.
+ uint64_t m = lcm(alignment, SIZES[region_idx]);
+ uint64_t mod = ((uint64_t)r->tail + alignment) % m;
+ uint64_t start = ((uint64_t)r->tail + alignment) - mod + m;
+ LF_ASSERT(CORRECT_ALIGNMENT(alignment, start));
+ if (start < REGION_SIZE * region_idx + REGION_SIZE) {
+ void *p = __allocate_fixed_in_region(region_idx, (void*)start);
+ LF_ASSERT_NE(p, NULL);
+ DBG_MEMALIGN_RESULT(p);
+ __unlock_region(region_idx);
+ return p;
+ }
+
+ //TODO: If it is impossible to allocated from ideal region, try another one.
+ __unlock_region(region_idx);
+ PRINTF_DBG("failed: No aligned spot available in region\n");
+ return NULL;
+}
+
+size_t __lf_usable_size(void* ptr) {
+ size_t region_idx = __lf_index(ptr);
+
+ if (region_idx == 0 || region_idx > REGION_COUNT) {
+ //TODO: can't easily libc malloc_usable_size.
+ PRINTF_DBG("Pointer not allocated by lfmalloc, returning 0;");
+ return 0;
+ } else {
+ return SIZES[region_idx];
+ }
+}
+
+void __lf_error(void *ptr, void* base, unsigned long size, unsigned int reason,
+ char* filename, unsigned int line) {
+ char *s_reason = NULL;
+ switch (reason) {
+ case MEMORY_STORE:
+ s_reason = "MEMORY STORE";
+ break;
+ case MEMORY_READ:
+ s_reason = "MEMORY READ";
+ break;
+ case MEMORY_ESCAPE:
+ s_reason = "MEMORY ESCAPE"; /*TODO: implement*/
+ break;
+ case FUNCTION_ESCAPE:
+ s_reason = "FUNCTION ESCAPE";
+ break;
+ default:
+ s_reason = "UNKNOWN";
+ }
+
+ if (filename != NULL && line != 0) {
+ fprintf(stderr, "%s at %p out of bounds (base: %p, size: 0x%lx) in %s:%i.\n",
+ s_reason, ptr, base, size, filename, line);
+ } else {
+ fprintf(stderr, "%s at %p out of bounds (base: %p, size: 0x%lx).\n",
+ s_reason, ptr, base, size);
+ }
+ abort();
+}
diff --git a/runtime/lfmalloc/src/lfmalloc.c b/runtime/lfmalloc/src/lfmalloc.c
new file mode 100644
index 0000000..a7fd9a2
--- /dev/null
+++ b/runtime/lfmalloc/src/lfmalloc.c
@@ -0,0 +1,150 @@
+#include <string.h>
+#include <unistd.h>
+#include <errno.h>
+#include <stdio.h>
+
+#include "lfmalloc.h"
+#include "lfinternal.h"
+#include "lfdebug.h"
+
+void* lf_malloc(size_t size) {
+ PRINTF_DBG("called malloc, size = 0x%lx\n", size);
+ return __lf_malloc(size);
+}
+
+void lf_free(void *ptr) {
+ __lf_free(ptr);
+}
+
+void* lf_calloc(size_t nmemb, size_t size) {
+ PRINTF_DBG("called calloc, nmemb = 0x%lx, size = 0x%lx\n", nmemb, size);
+ uint64_t alloc_size = nmemb * size;
+ //check for overflow
+ if (nmemb != 0 && alloc_size / nmemb != size) {
+ PRINTF_DBG("calloc failed: nmenb * size overflows.\n");
+ return NULL;
+ }
+ void* ptr = __lf_malloc(nmemb * size);
+ void* p = memset(ptr, 0, nmemb * size);
+
+ LF_ASSERT_EQ(p, ptr);
+ return ptr;
+}
+
+void* lf_realloc(void *ptr, size_t size) {
+ PRINTF_DBG("called realloc, ptr = %p, size = 0x%lx\n", ptr, size);
+ if (ptr == NULL) {
+ return __lf_malloc(size);
+ } else if (size == 0) {
+ PRINTF_DBG("failed: size = 0, freeing");
+ __lf_free(ptr);
+ return NULL;
+ }
+
+ if (__lf_size(ptr) >= size) { //Enough remaining padding => No reallocation necessary
+ PRINTF_DBG("enough remaining space available.\n");
+ return ptr;
+ } else { // New allocation necessary
+ PRINTF_DBG("new allocation necessary.\n");
+ size_t old_size = __lf_size(ptr);
+ void* new_ptr = __lf_malloc(size);
+ LF_ASSERT_NE(new_ptr, NULL);
+ memcpy(new_ptr, ptr, old_size);
+ __lf_free(ptr);
+ return new_ptr;
+ }
+}
+
+
+void *lf_memalign(size_t alignment, size_t size) {
+ PRINTF_DBG("called memalign, alignment = 0x%lx, size = 0x%lx\n", alignment, size);
+ return __lf_memalign(alignment, size);
+}
+
+int lf_posix_memalign(void **memptr, size_t alignment, size_t size) {
+ PRINTF_DBG("called posix_memalign, alignment = 0x%lx, size = 0x%lx\n", alignment, size);
+ if (!is_pow_two(alignment)) {
+ PRINTF_DBG("failed: alignment not pow of two.\n")
+ return EINVAL;
+ }
+ if (size == 0) {
+ PRINTF_DBG("failed: size is zero.\n");
+ *memptr = NULL;
+ return 0;
+ }
+ void* p = __lf_memalign(alignment, size);
+ if (p != NULL) {
+ *memptr = p;
+ return 0;
+ }
+ PRINTF_DBG("failed: posix_memalign ENOMEM\n");
+ return ENOMEM;
+};
+
+void *lf_aligned_alloc(size_t alignment, size_t size) {
+ PRINTF_DBG("called aligned_alloc, alignment = 0x%lx, size = 0x%lx\n", alignment, size);
+ if (size % alignment != 0) {
+ PRINTF_DBG("failed: size not multiple of alignment.\n")
+ errno = EINVAL;
+ return NULL;
+ }
+ return __lf_memalign(alignment, size);;
+}
+void *lf_valloc(size_t size) {
+ PRINTF_DBG("lfalloc: called valloc and failed\n")
+ return __lf_memalign(sysconf(_SC_PAGESIZE), size);
+}
+
+void *lf_pvalloc(size_t size) {
+ PRINTF_DBG("lfalloc: called pvalloc and failed\n")
+ size_t page_size = sysconf(_SC_PAGESIZE);
+ size_t alloc_size = size - size % page_size + page_size;
+ LF_ASSERT(alloc_size % page_size == 0);
+ return __lf_memalign(sysconf(_SC_PAGESIZE), alloc_size);
+}
+
+size_t lf_malloc_usable_size(void *ptr) {
+ PRINTF_DBG("lfalloc: called malloc_usable_size and failed\n")
+ return __lf_usable_size(ptr);
+}
+
+#ifdef LF_DYNAMIC_LIB
+void *malloc(size_t size) {
+ return lf_malloc(size);
+}
+void free(void *ptr) {
+ return lf_free(ptr);
+}
+void *calloc(size_t nmemb, size_t size) {
+ return lf_calloc(nmemb, size);
+}
+void *realloc(void *ptr, size_t size) {
+ return lf_realloc(ptr, size);
+}
+
+int posix_memalign(void **memptr, size_t alignment, size_t size) {
+ return lf_posix_memalign(memptr, alignment, size);
+}
+void *aligned_alloc(size_t alignment, size_t size) {
+ return lf_aligned_alloc(alignment, size);
+}
+void *valloc(size_t size) {
+ return lf_valloc(size);
+}
+
+void *memalign(size_t alignment, size_t size) {
+ return lf_memalign(alignment, size);
+}
+void *pvalloc(size_t size) {
+ return lf_pvalloc(size);
+}
+
+size_t malloc_usable_size(void *ptr) {
+ return lf_malloc_usable_size(ptr);
+}
+#endif
+
+void lf_error(void *ptr, void* base, unsigned long size, unsigned int reason,
+ char* filename, unsigned int line) {
+ __lf_error(ptr, base, size, reason, filename, line);
+}
diff --git a/runtime/lfmalloc/src/lfutil.c b/runtime/lfmalloc/src/lfutil.c
new file mode 100644
index 0000000..7c2406a
--- /dev/null
+++ b/runtime/lfmalloc/src/lfutil.c
@@ -0,0 +1,18 @@
+#include <stdint.h>
+#include <stdbool.h>
+
+#include "lfutil.h"
+
+uint64_t gcd(uint64_t a, uint64_t b) {
+ while (true) {
+ if (a == 0) return b;
+ b %= a;
+ if (b == 0) return a;
+ a %= b;
+ }
+}
+
+uint64_t lcm(uint64_t a, uint64_t b) {
+ int tmp = gcd(a, b);
+ return tmp ? (a / tmp * b) : 0;
+}
diff --git a/scripts/gen_lf_sizes.py b/scripts/gen_lf_sizes.py
new file mode 100755
index 0000000..e9c0d08
--- /dev/null
+++ b/scripts/gen_lf_sizes.py
@@ -0,0 +1,51 @@
+#!/usr/bin/env python
+
+UINT64_MAX = 2**64 - 1
+
+REGION_BITS = 32 # The amount of least significant bits used by a region.
+REGION_SIZE = 1 << REGION_BITS # The amount bytes of each region
+TOTAL_REGIONS = 2**(48 - REGION_BITS) # The max amount of regions possible
+
+MAX_SIZE = 2**30 # The max size a region can allocate
+START_REGION = 0x100000000 # Start of the first region
+
+sizes = []
+
+#SIZES CONFIGURATION
+# 16 byte steps to 8kB
+for i in range(0, 8 * 1024, 16):
+ sizes.append(i);
+sizes.append(8 * 1024);
+sizes[0] = UINT64_MAX #region 0 is not used
+
+# pow2 stesp
+s = 16 * 1024
+while s <= MAX_SIZE:
+ sizes.append(s)
+ s *= 2
+
+region_count = len(sizes);
+
+# remaining filling with UINT64_MAX
+sizes += [UINT64_MAX] * (TOTAL_REGIONS - len(sizes)) # Remaining possible regions are not used.
+
+sizes = list(map(lambda x: hex(x), sizes))
+
+
+# C-style printing
+print('#ifndef GEN_LFASAN_SIZES_H')
+print('#define GEN_LFASAN_SIZES_H')
+print('#include <stdint.h>')
+print('#define REGION_BITS ' + hex(REGION_BITS))
+print('#define REGION_SIZE ' + hex(REGION_SIZE))
+print('#define START_REGION ' + hex(START_REGION))
+print('#define TOTAL_REGIONS ' + hex(TOTAL_REGIONS))
+print('#define MAX_SIZE ' + hex(MAX_SIZE))
+print('#define REGION_COUNT ' + hex(region_count));
+print('const uint64_t SIZES[' + hex(len(sizes)) + '] = {\n' + ',\n'.join(sizes) + '};')
+
+print('#define MEMORY_STORE 0')
+print('#define MEMORY_READ 1')
+print('#define FUNCTION_ESCAPE 2')
+print('#define MEMORY_ESCAPE 3')
+print('#endif')