Date: Fri, 11 Oct 2013 15:56:01 GMT From: Jonathan Anderson <jonathan@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 1046466 for review Message-ID: <201310111556.r9BFu1xw018716@skunkworks.freebsd.org>
index | next in thread | raw e-mail
http://p4web.freebsd.org/@@1046466?ac=10 Change 1046466 by jonathan@jonathan-on-zenith on 2013/10/11 15:55:05 Merge optimised version of TESLA kernel parts. Affected files ... .. //depot/projects/ctsrd/tesla/src/sys/amd64/conf/TESLA_NODEBUG#2 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/include/libtesla.h#14 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_dtrace.c#13 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_internal.h#15 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_notification.c#19 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_store.c#9 edit .. //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_update.c#14 edit Differences ... ==== //depot/projects/ctsrd/tesla/src/sys/amd64/conf/TESLA_NODEBUG#2 (text+ko) ==== @@ -1,6 +1,7 @@ include TESLA ident TESLA_NODEBUG +options TESLA nooptions INVARIANTS nooptions INVARIANT_SUPPORT nooptions WITNESS ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/include/libtesla.h#14 (text+ko) ==== @@ -76,7 +76,7 @@ * a number of times with different names and current states. */ struct tesla_class; - +struct tesla_lifetime_event; struct tesla_transitions; /** @@ -94,6 +94,11 @@ */ const int32_t ta_alphabet_size; + /** + * The symbol number used to signal cleanup. + */ + const int32_t ta_cleanup_symbol; + /** * Transitions that will be taken in response to events. * @@ -107,6 +112,54 @@ /** Human-readable descriptions of input symbols (for debugging). */ const char* *ta_symbol_names; + + /** The automaton's lifetime. */ + const struct tesla_lifetime *ta_lifetime; +}; + + +/** + * A short, unique, deterministic representation of a lifetime entry/exit event, + * a pair of which defines an automaton's lifetime. + */ +struct tesla_lifetime_event { + /** + * An opaque representation of the automaton's initialisation event. + * + * This description should be short and deterministic, + * i.e., multiple automata that share the same init event should + * have exactly the same ta_init description string. + * + * This can be written by hand if needed (e.g. for testing), + * but in practice we generate it from protocol buffers. + */ + const char *tle_repr; + + /** The length of @ref #tle_repr. */ + const int32_t tle_length; + + /** + * A precomputed hash of @ref #tle_repr. + * + * libtesla doesn't care what hash algorithm is used; in test code or + * statically-compiled clients, incrementing integers works well. + * + * All clients should be consistent, however; the TESLA instrumenter + * uses SuperFastHash. + */ + const int32_t tle_hash; +}; + + +/** + * The description of a TESLA lifetime. + */ +struct tesla_lifetime { + struct tesla_lifetime_event tl_begin; + struct tesla_lifetime_event tl_end; + + /** A human-readable string for debugging. */ + const char *tl_repr; }; @@ -246,7 +299,20 @@ const struct tesla_automaton *automaton, uint32_t symbol, const struct tesla_key *pattern); +/** + * We have encountered an entry bound for some automata. + * + * @param context Where the automaton is stored. + * @param l Static description of the lifetime (begin, end events). + */ +void tesla_sunrise(enum tesla_context context, + const struct tesla_lifetime *l); + +/** We have encountered an exit bound for some automata. */ +void tesla_sunset(enum tesla_context context, + const struct tesla_lifetime*); + /** A single instance of an automaton: a name (@ref ti_key) and a state. */ struct tesla_instance { struct tesla_key ti_key; @@ -257,6 +323,14 @@ /* * Event notification: */ +/** An initialisation event has occurred; entering an automaton lifetime. */ +typedef void (*tesla_ev_sunrise)(enum tesla_context, + const struct tesla_lifetime *); + +/** A cleanup event has occurred; exiting an automaton lifetime. */ +typedef void (*tesla_ev_sunset)(enum tesla_context, + const struct tesla_lifetime *); + /** A new @ref tesla_instance has been created. */ typedef void (*tesla_ev_new_instance)(struct tesla_class *, struct tesla_instance *); @@ -292,6 +366,8 @@ /** A vector of event handlers. */ struct tesla_event_handlers { + tesla_ev_sunrise teh_sunrise; + tesla_ev_sunset teh_sunset; tesla_ev_new_instance teh_init; tesla_ev_transition teh_transition; tesla_ev_clone teh_clone; ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_dtrace.c#13 (text+ko) ==== @@ -38,6 +38,10 @@ SDT_PROVIDER_DEFINE(tesla); +SDT_PROBE_DEFINE2(tesla, automata, lifetime, sunrise, sunrise, + "enum tesla_context context", "struct tesla_lifetime *"); +SDT_PROBE_DEFINE2(tesla, automata, lifetime, sunset, sunset, + "enum tesla_context context", "struct tesla_lifetime *"); SDT_PROBE_DEFINE2(tesla, automata, instance, create, create, "struct tesla_class *", "struct tesla_instance *"); SDT_PROBE_DEFINE3(tesla, automata, event, transition, state-transition, @@ -60,6 +64,20 @@ "struct tesla_class *", "int32_t", "struct tesla_key *"); static void +sunrise(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + SDT_PROBE(tesla, automata, lifetime, sunrise, c, tl, 0, 0, 0); +} + +static void +sunset(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + SDT_PROBE(tesla, automata, lifetime, sunset, c, tl, 0, 0, 0); +} + +static void new_instance(struct tesla_class *tcp, struct tesla_instance *tip) { @@ -144,6 +162,8 @@ } const struct tesla_event_handlers dtrace_handlers = { + .teh_sunrise = sunrise, + .teh_sunset = sunset, .teh_init = new_instance, .teh_transition = transition, .teh_clone = clone, ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_internal.h#15 (text+ko) ==== @@ -65,6 +65,7 @@ #include <assert.h> #include <err.h> #include <pthread.h> +#include <stdbool.h> #include <stdlib.h> #include <string.h> #endif @@ -79,7 +80,28 @@ #define assert(cond) KASSERT((cond), ("Assertion failed: '%s'", #cond)) #endif + /** + * The current runtime state of a TESLA lifetime. + */ +struct tesla_lifetime_state { + struct tesla_lifetime_event tls_begin; + struct tesla_lifetime_event tls_end; + + /** A place to register a few classes that share this lifetime. */ + struct tesla_class* tls_classes[4]; + + /** A place to register more classes that share this lifetime. */ + struct tesla_class* *tls_dyn_classes; + + /** The number of values @ref tls_dyn_classes can hold. */ + uint32_t tls_dyn_capacity; + + /** The number of values currently in @ref tls_dyn_classes. */ + uint32_t tls_dyn_count; +}; + +/** * Call this if things go catastrophically, unrecoverably wrong. */ void tesla_die(int32_t errnum, const char *event) __attribute__((noreturn)); @@ -130,8 +152,46 @@ return ((i->ti_state != 0) || (i->ti_key.tk_mask != 0)); } +static inline bool +same_lifetime(const struct tesla_lifetime *x, const struct tesla_lifetime *y) +{ + assert(x != NULL); + assert(y != NULL); + + return (x->tl_begin.tle_length == y->tl_begin.tle_length) + && (x->tl_end.tle_length == y->tl_end.tle_length) + && (x->tl_begin.tle_hash == y->tl_begin.tle_hash) + && (x->tl_end.tle_hash == y->tl_end.tle_hash) + && (strncmp(x->tl_begin.tle_repr, y->tl_begin.tle_repr, + x->tl_begin.tle_length) == 0) + && (strncmp(x->tl_end.tle_repr, y->tl_end.tle_repr, + x->tl_end.tle_length) == 0) + ; +} + +/** + * Compare the static parts of a @ref tesla_lifetime_state with a + * @ref tesla_lifetime. + */ +static inline bool +same_static_lifetime(const struct tesla_lifetime *x, + const struct tesla_lifetime_state *y) +{ + assert(x != NULL); + assert(y != NULL); + return (x->tl_begin.tle_length == y->tls_begin.tle_length) + && (x->tl_end.tle_length == y->tls_end.tle_length) + && (x->tl_begin.tle_hash == y->tls_begin.tle_hash) + && (x->tl_end.tle_hash == y->tls_end.tle_hash) + && (strncmp(x->tl_begin.tle_repr, y->tls_begin.tle_repr, + x->tl_begin.tle_length) == 0) + && (strncmp(x->tl_end.tle_repr, y->tls_end.tle_repr, + x->tl_end.tle_length) == 0) + ; +} + /** Clone an existing instance into a new instance. */ int32_t tesla_instance_clone(struct tesla_class *tclass, const struct tesla_instance *orig, struct tesla_instance **copy); @@ -262,10 +322,13 @@ #endif }; + typedef struct tesla_automaton tesla_automaton; typedef struct tesla_class tesla_class; typedef struct tesla_instance tesla_instance; typedef struct tesla_key tesla_key; +typedef struct tesla_lifetime_event tesla_lifetime_event; +typedef struct tesla_lifetime_state tesla_lifetime_state; typedef struct tesla_store tesla_store; typedef struct tesla_transition tesla_transition; typedef struct tesla_transitions tesla_transitions; @@ -283,6 +346,19 @@ /** Actual slots that classes might be stored in. */ struct tesla_class *ts_classes; + + /** + * Information about live/dead automata classes; may be shared among + * automata. + * + * For instance, the lifetime [enter syscall, exit syscall] is shared + * by many automata we've written for the FreeBSD kernel. Each + * @ref tesla_store should only record these events once. + */ + struct tesla_lifetime_state *ts_lifetimes; + + /** The number of lifetimes that we currently know about. */ + uint32_t ts_lifetime_count; }; /** @@ -333,6 +409,8 @@ extern const struct tesla_event_handlers dtrace_handlers; #endif +void ev_sunrise(enum tesla_context, const struct tesla_lifetime *); +void ev_sunset(enum tesla_context, const struct tesla_lifetime *); void ev_new_instance(struct tesla_class *, struct tesla_instance *); void ev_transition(struct tesla_class *, struct tesla_instance *, const struct tesla_transition *); ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_notification.c#19 (text+ko) ==== @@ -51,7 +51,8 @@ check_event_handler(const struct tesla_event_handlers *tehp) { - if (!tehp || !tehp->teh_init || !tehp->teh_transition + if (!tehp || !tehp->teh_sunrise || !tehp->teh_sunset + || !tehp->teh_init || !tehp->teh_transition || !tehp->teh_clone || !tehp->teh_fail_no_instance || !tehp->teh_bad_transition || !tehp->teh_err || !tehp->teh_accept || !tehp->teh_ignored) @@ -118,8 +119,23 @@ if (event_handlers->tem_handlers[i]->x) \ event_handlers->tem_handlers[i]->x(__VA_ARGS__) +void +ev_sunrise(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + FOREACH_ERROR_HANDLER(teh_sunrise, c, tl); +} + void +ev_sunset(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + FOREACH_ERROR_HANDLER(teh_sunset, c, tl); +} + + +void ev_new_instance(struct tesla_class *tcp, struct tesla_instance *tip) { @@ -201,6 +217,22 @@ } static void +print_sunrise(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + DEBUG(libtesla.sunrise, "sunrise %s %s\n", + (c == TESLA_CONTEXT_GLOBAL) ? "global" : "per-thread", tl->tl_repr); +} + +static void +print_sunset(enum tesla_context c, const struct tesla_lifetime *tl) +{ + + DEBUG(libtesla.sunset, "sunset %s %s\n", + (c == TESLA_CONTEXT_GLOBAL) ? "global" : "per-thread", tl->tl_repr); +} + +static void print_new_instance(struct tesla_class *tcp, struct tesla_instance *tip) { @@ -318,11 +350,13 @@ { const struct tesla_automaton *a = tcp->tc_automaton; - DEBUG(libtesla.event, "ignore '%s': %s", a->ta_name, + DEBUG(libtesla.event, "ignore '%s': %s\n", a->ta_name, a->ta_symbol_names[symbol]); } static const struct tesla_event_handlers printf_handlers = { + .teh_sunrise = print_sunrise, + .teh_sunset = print_sunset, .teh_init = print_new_instance, .teh_transition = print_transition_taken, .teh_clone = print_clone, @@ -334,6 +368,8 @@ }; static const struct tesla_event_handlers printf_on_failure = { + .teh_sunrise = 0, + .teh_sunset = 0, .teh_init = 0, .teh_transition = 0, .teh_clone = 0, ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_store.c#9 (text+ko) ==== @@ -145,6 +145,18 @@ assert(store->ts_classes[i].tc_context >= 0); } + /* + * For now, allocate as many lifetime storage slots as there are + * classes. In practice, many automata will share lifetime information. + * + * TODO(JA): perhaps allocate fewer of these? + */ + const size_t lifetime_size = classes * sizeof(store->ts_lifetimes[0]); + store->ts_lifetimes = tesla_malloc(lifetime_size); + bzero(store->ts_lifetimes, lifetime_size); + + store->ts_lifetime_count = 0; + return (error); } @@ -157,6 +169,7 @@ for (uint32_t i = 0; i < store->ts_length; i++) tesla_class_destroy(store->ts_classes + i); + tesla_free(store->ts_lifetimes); tesla_free(store); } ==== //depot/projects/ctsrd/tesla/src/sys/contrib/tesla/libtesla/tesla_update.c#14 (text+ko) ==== @@ -39,24 +39,104 @@ #endif +static void tesla_update_class_state(struct tesla_class *, struct tesla_store *, + uint32_t symbol, const struct tesla_key *); + + +void +tesla_sunrise(enum tesla_context context, const struct tesla_lifetime *l) +{ + __unused int ret; + assert(l != NULL); + + struct tesla_store *store; + ret = tesla_store_get(context, TESLA_MAX_CLASSES, + TESLA_MAX_INSTANCES, &store); + assert(ret == TESLA_SUCCESS); + assert(store->ts_lifetime_count < store->ts_length); + + tesla_lifetime_state *ls = NULL; + + // TODO: lock global store + + const uint32_t lifetimes = store->ts_lifetime_count; + for (uint32_t i = 0; i < lifetimes; i++) { + if (same_static_lifetime(l, store->ts_lifetimes + i)) { + ls = store->ts_lifetimes + i; + break; + } + } + + if (ls == NULL) { + ls = store->ts_lifetimes + lifetimes; + store->ts_lifetime_count++; + + ls->tls_begin = l->tl_begin; + ls->tls_end = l->tl_end; + } + + ev_sunrise(context, l); +} + + +void +tesla_sunset(enum tesla_context context, const struct tesla_lifetime *l) +{ + __unused int ret; + assert(l != NULL); + + ev_sunset(context, l); + + struct tesla_store *store; + ret = tesla_store_get(context, TESLA_MAX_CLASSES, + TESLA_MAX_INSTANCES, &store); + assert(ret == TESLA_SUCCESS); + assert(store->ts_lifetime_count < store->ts_length); + + tesla_lifetime_state *ls = NULL; + + const uint32_t lifetimes = store->ts_lifetime_count; + for (uint32_t i = 0; i < lifetimes; i++) { + if (same_static_lifetime(l, store->ts_lifetimes + i)) { + ls = store->ts_lifetimes + i; + break; + } + } + + assert(ls != NULL && "tesla_sunset() without corresponding sunrise"); + + tesla_key empty_key; + empty_key.tk_mask = 0; + + const size_t static_classes = + sizeof(ls->tls_classes) / sizeof(ls->tls_classes[0]); + + for (size_t i = 0; i < static_classes; i++) { + tesla_class *class = ls->tls_classes[i]; + if (class == NULL) + break; + + tesla_update_class_state(class, store, + class->tc_automaton->ta_cleanup_symbol, &empty_key); + } + + const size_t dynamic_classes = ls->tls_dyn_count; + for (size_t i = 0; i < dynamic_classes; i++) { + tesla_class *class = ls->tls_dyn_classes[i]; + if (class == NULL) + break; + + tesla_update_class_state(class, store, + class->tc_automaton->ta_cleanup_symbol, &empty_key); + } +} + + void tesla_update_state(enum tesla_context tesla_context, const struct tesla_automaton *autom, uint32_t symbol, const struct tesla_key *pattern) { - const struct tesla_transitions *trans = - autom->ta_transitions + symbol; - -#ifndef NDEBUG - /* We should never see with multiple <<init>> transitions. */ - int init_count = 0; - for (uint32_t i = 0; i < trans->length; i++) - if (trans->transitions[i].flags & TESLA_TRANS_INIT) - init_count++; - - assert(init_count < 2); -#endif - struct tesla_store *store; int ret = tesla_store_get(tesla_context, TESLA_MAX_CLASSES, TESLA_MAX_INSTANCES, &store); @@ -66,11 +146,18 @@ ret = tesla_class_get(store, autom, &class); assert(ret == TESLA_SUCCESS); - // Did we match any instances? - bool matched_something = false; + tesla_update_class_state(class, store, symbol, pattern); + + tesla_class_put(class); +} + - // When we're done, do we need to clean up the class? - bool cleanup_required = false; +static void +tesla_update_class_state(struct tesla_class *class, struct tesla_store *store, + uint32_t symbol, const struct tesla_key *pattern) +{ + int err; + const struct tesla_automaton *autom = class->tc_automaton; // Make space for cloning existing instances. size_t cloned = 0; @@ -80,8 +167,131 @@ const tesla_transition *transition; } clones[max_clones]; + // Has this class been initialised? + bool initialised = false; + tesla_lifetime_state *lifetime = NULL; + const uint32_t lifetimes = store->ts_lifetime_count; + for (uint32_t i = 0; i < lifetimes; i++) { + if (!same_static_lifetime(autom->ta_lifetime, + store->ts_lifetimes + i)) + continue; + + initialised = true; + lifetime = store->ts_lifetimes + i; + break; + } + + if (!initialised) { + ev_ignored(class, symbol, pattern); + return; + + } else if (class->tc_limit == class->tc_free) { + // Late initialisation: find the init transition and pretend + // it has already been taken. + struct tesla_instance *inst = NULL; + + for (uint32_t i = 0; i < autom->ta_alphabet_size; i++) { + const tesla_transitions *trans = + autom->ta_transitions + i; + + for (uint32_t j = 0; i < trans->length; i++) { + const tesla_transition *t = + trans->transitions + j; + + if (!(t->flags & TESLA_TRANS_INIT)) + continue; + + static const tesla_key empty = { .tk_mask = 0 }; + + err = tesla_instance_new(class, &empty, + t->to, &inst); + + if (err != TESLA_SUCCESS) { + + ev_err(autom, symbol, err, + "failed to initialise instance"); + return; + } + + break; + } + } + + if (inst == NULL) { + // The automaton does not have an init transition! + err = TESLA_ERROR_EINVAL; + ev_err(autom, symbol, err, + "automaton has no init transition"); + return; + } + + assert(tesla_instance_active(inst)); + ev_new_instance(class, inst); + + // Register this class for eventual cleanup. + tesla_lifetime_state *ls = lifetime; + const size_t static_classes = + sizeof(ls->tls_classes) / sizeof(ls->tls_classes[0]); + + size_t i; + for (i = 0; i < static_classes; i++) { + if (ls->tls_classes[i] != NULL) + continue; + + ls->tls_classes[i] = class; + break; + } + + if (i == static_classes) { +#ifdef _KERNEL + /* + * TODO(JA): we should also do the dynamic thing, + * but we might have to do it by noting + * that we don't have enough space and + * leaving the allocation for a later time + * when we know it's safe. + */ + ev_err(autom, symbol, TESLA_ERROR_ENOMEM, + "out of dynamic registration space in lifetime"); +#else + static size_t unit_size = + sizeof(ls->tls_dyn_classes[0]); + + tesla_class ***dyn_classes = &ls->tls_dyn_classes; + + if (ls->tls_dyn_capacity == 0) { + // Need to create a fresh allocation. + size_t count = 8; + *dyn_classes = calloc(count, unit_size); + ls->tls_dyn_capacity = count; + } else { + size_t count = 2 * ls->tls_dyn_capacity; + *dyn_classes = realloc(*dyn_classes, + count * unit_size); + ls->tls_dyn_capacity = count; + } + + assert(ls->tls_dyn_count < ls->tls_dyn_capacity); + ls->tls_dyn_classes[ls->tls_dyn_count++] = class; +#endif + } + } + + + // Did we match any instances? + bool matched_something = false; + + // When we're done, do we need to clean up the class? + bool cleanup_required = false; + + + // What transitions can we take? + const tesla_transitions *trans = autom->ta_transitions + symbol; + assert(trans->length > 0); + assert(trans->length < 10000); + // Iterate over existing instances, figure out what to do with each. - int err = TESLA_SUCCESS; + err = TESLA_SUCCESS; int expected = class->tc_limit - class->tc_free; for (uint32_t i = 0; expected > 0 && (i < class->tc_limit); i++) { assert(class->tc_instances != NULL); @@ -98,6 +308,7 @@ break; case IGNORE: + // TODO(JA): this should become unreachable break; case UPDATE: @@ -115,7 +326,7 @@ if (cloned >= max_clones) { err = TESLA_ERROR_ENOMEM; ev_err(autom, symbol, err, "too many clones"); - goto cleanup; + return; } struct clone_info *clone = clones + cloned++; @@ -154,7 +365,7 @@ err = tesla_instance_clone(class, c->old, &clone); if (err != TESLA_SUCCESS) { ev_err(autom, symbol, err, "failed to clone instance"); - goto cleanup; + return; } tesla_key new_name = *pattern; @@ -162,7 +373,7 @@ err = tesla_key_union(&clone->ti_key, &new_name); if (err != TESLA_SUCCESS) { ev_err(autom, symbol, err, "failed to union keys"); - goto cleanup; + return; } clone->ti_state = c->transition->to; @@ -173,42 +384,12 @@ ev_accept(class, clone); } - - // Does this transition cause class instance initialisation? - for (uint32_t i = 0; i < trans->length; i++) { - const tesla_transition *t = trans->transitions + i; - if (t->flags & TESLA_TRANS_INIT) { - struct tesla_instance *inst; - err = tesla_instance_new(class, pattern, t->to, &inst); - if (err != TESLA_SUCCESS) { - ev_err(autom, symbol, err, - "failed to init instance"); - goto cleanup; - } - - assert(tesla_instance_active(inst)); + if (!matched_something) + ev_no_instance(class, symbol, pattern); - matched_something = true; - ev_new_instance(class, inst); - } - } - - if (!matched_something) { - // If the class hasn't received any <<init>> events yet, - // simply ignore the event: it is out of scope. - if (class->tc_free == class->tc_limit) - ev_ignored(class, symbol, pattern); - - // Otherwise, we ought to have matched something. - else ev_no_instance(class, symbol, pattern); - } - // Does it cause class cleanup? if (cleanup_required) tesla_class_reset(class); - -cleanup: - tesla_class_put(class); } enum tesla_action_thelp
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201310111556.r9BFu1xw018716>