Computer Laboratory

tesla_update.c
Go to the documentation of this file.
1 /*-
2  * Copyright (c) 2012 Jonathan Anderson
3  * All rights reserved.
4  *
5  * This software was developed by SRI International and the University of
6  * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
7  * ("CTSRD"), as part of the DARPA CRASH research programme.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  * notice, this list of conditions and the following disclaimer in the
16  * documentation and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28  * SUCH DAMAGE.
29  *
30  * $Id$
31  */
32 
33 #include "tesla_internal.h"
34 
35 #ifndef _KERNEL
36 #include <stdbool.h>
37 #include <inttypes.h>
38 #endif
39 
40 #define DEBUG_NAME "libtesla.state.update"
41 #define PRINT(...) DEBUG(libtesla.state.update, __VA_ARGS__)
42 
43 void
44 tesla_update_state(enum tesla_context tesla_context, uint32_t class_id,
45  const struct tesla_key *pattern,
46  const char *name, const char *description,
47  const struct tesla_transitions *trans)
48 {
49 
50  if (tesla_debugging(DEBUG_NAME)) {
51  /* We should never see with multiple <<init>> transitions. */
52  int init_count = 0;
53  for (uint32_t i = 0; i < trans->length; i++)
54  if (trans->transitions[i].flags & TESLA_TRANS_INIT)
55  init_count++;
56 
57  assert(init_count < 2);
58  }
59 
60  PRINT("\n====\n%s()\n", __func__);
61  PRINT(" context: %s\n",
62  (tesla_context == TESLA_CONTEXT_GLOBAL
63  ? "global"
64  : "per-thread"));
65  PRINT(" class: %d ('%s')\n", class_id, name);
66 
67  PRINT(" transitions: ");
68  print_transitions(DEBUG_NAME, trans);
69  PRINT("\n");
70  PRINT(" key: ");
71  print_key(DEBUG_NAME, pattern);
72  PRINT("\n----\n");
73 
74  struct tesla_store *store;
75  assert(tesla_store_get(tesla_context, TESLA_MAX_CLASSES,
76  TESLA_MAX_INSTANCES, &store) == TESLA_SUCCESS);
77 
78  PRINT("store: 0x%tx\n", (intptr_t) store);
79 
80  struct tesla_class *class;
81  assert(tesla_class_get(store, class_id, &class, name, description)
82  == TESLA_SUCCESS);
83 
84  print_class(class);
85 
86  // Did we match any instances?
87  bool matched_something = false;
88 
89  // When we're done, do we need to clean up the class?
90  bool cleanup_required = false;
91 
92  // Make space for cloning existing instances.
93  size_t cloned = 0;
94  const size_t max_clones = class->tc_free;
95  struct clone_info {
96  tesla_instance *old;
97  const tesla_transition *transition;
98  } clones[max_clones];
99 
100  // Iterate over existing instances, figure out what to do with each.
101  int err = TESLA_SUCCESS;
102  for (uint32_t i = 0; i < class->tc_limit; i++) {
103  assert(class->tc_instances != NULL);
104  tesla_instance *inst = class->tc_instances + i;
105 
106  const tesla_transition *trigger = NULL;
107  enum tesla_action_t action =
108  tesla_action(inst, pattern, trans, &trigger);
109 
110  switch (action) {
111  case FAIL:
112  ev_bad_transition(class, inst, trans);
113  break;
114 
115  case IGNORE:
116  break;
117 
118  case UPDATE:
119  ev_transition(class, inst, trigger);
120  inst->ti_state = trigger->to;
121  matched_something = true;
122 
123  if (trigger->flags & TESLA_TRANS_CLEANUP)
124  ev_accept(class, inst);
125 
126  break;
127 
128  case FORK: {
129  if (cloned >= max_clones) {
130  err = TESLA_ERROR_ENOMEM;
131  ev_err(class, err, "too many clones");
132  goto cleanup;
133  }
134 
135  struct clone_info *clone = clones + cloned++;
136  clone->old = inst;
137  clone->transition = trigger;
138  matched_something = true;
139  break;
140  }
141 
142  case JOIN:
143 #ifndef NDEBUG
144  {
145  int target = -1;
146  for (uint32_t j = 0; j < class->tc_limit; j++) {
147  tesla_instance *t = class->tc_instances + j;
148  if (t->ti_state == trigger->to) {
149  target = j;
150  break;
151  }
152  }
153  assert(target >= 0);
154  }
155 #endif
156  tesla_instance_clear(inst);
157  break;
158  }
159 
160  if (trigger && (trigger->flags & TESLA_TRANS_CLEANUP))
161  cleanup_required = true;
162  }
163 
164  // Move any clones into the class.
165  for (size_t i = 0; i < cloned; i++) {
166  struct clone_info *c = clones + i;
167  struct tesla_instance *clone;
168  err = tesla_instance_clone(class, c->old, &clone);
169  if (err != TESLA_SUCCESS) {
170  ev_err(class, err, "failed to clone instance");
171  goto cleanup;
172  }
173 
174  tesla_key new_name = *pattern;
175  new_name.tk_mask &= c->transition->to_mask;
176  err = tesla_key_union(&clone->ti_key, &new_name);
177  if (err != TESLA_SUCCESS) {
178  ev_err(class, err, "failed to union keys");
179  goto cleanup;
180  }
181 
182  clone->ti_state = c->transition->to;
183 
184  ev_clone(class, c->old, clone, c->transition);
185 
186  if (c->transition->flags & TESLA_TRANS_CLEANUP)
187  ev_accept(class, clone);
188  }
189 
190 
191  // Does this transition cause class instance initialisation?
192  for (uint32_t i = 0; i < trans->length; i++) {
193  const tesla_transition *t = trans->transitions + i;
194  if (t->flags & TESLA_TRANS_INIT) {
195  struct tesla_instance *inst;
196  err = tesla_instance_new(class, pattern, t->to, &inst);
197  if (err != TESLA_SUCCESS) {
198  ev_err(class, err, "failed to create instance");
199  goto cleanup;
200  }
201 
202  assert(tesla_instance_active(inst));
203 
204  matched_something = true;
205  ev_new_instance(class, inst);
206  }
207  }
208 
209  if (!matched_something) {
210  // If the class hasn't received any <<init>> events yet,
211  // simply ignore the event: it is out of scope.
212  if (class->tc_free == class->tc_limit)
213  ev_ignored(class, pattern, trans);
214 
215  // Otherwise, we ought to have matched something.
216  else ev_no_instance(class, pattern, trans);
217  }
218 
219  // Does it cause class cleanup?
220  if (cleanup_required)
221  tesla_class_reset(class);
222 
223  print_class(class);
224  PRINT("\n====\n\n");
225 
226 cleanup:
227  tesla_class_put(class);
228 }
229 
230 enum tesla_action_t
231 tesla_action(const tesla_instance *inst, const tesla_key *event_data,
232  const tesla_transitions *trans, const tesla_transition* *trigger)
233 {
234  assert(trigger != NULL);
235 
236  if (!tesla_instance_active(inst))
237  return IGNORE;
238 
239  /*
240  * We allowed to ignore this instance if its name doesn't match
241  * any of the given transitions.
242  */
243  bool ignore = true;
244 
245  for (size_t i = 0; i < trans->length; i++) {
246  const tesla_transition *t = trans->transitions + i;
247 
248  if (t->from == inst->ti_state) {
249  assert(inst->ti_key.tk_mask == t->from_mask);
250 
251  /*
252  * We need to match events against a pattern based on
253  * data from the event, but ignoring parts that are
254  * extraneous to this transition.
255  *
256  * For instance, if the event is 'foo(x,y) == z', we
257  * know what the values of x, y and z are, but the
258  * transition in question may only care about x and z:
259  * 'foo(x,*) == z'.
260  */
261  tesla_key pattern = *event_data;
262  pattern.tk_mask &= t->from_mask;
263 
264  /*
265  * Losing information implies a join
266  * (except during automaton instance cleanup).
267  */
268  if (!SUBSET(t->from_mask, t->to_mask)
269  && ((t->flags & TESLA_TRANS_CLEANUP) == 0)) {
270  *trigger = t;
271  return JOIN;
272  }
273 
274  /*
275  * Does the transition cause key data to be added
276  * to the instance's name?
277  */
278  if (SUBSET(t->to_mask, t->from_mask)) {
279  /*
280  * No: just just update the instance
281  * if its (masked) name matches.
282  */
283  tesla_key masked_name = inst->ti_key;
284  masked_name.tk_mask &= pattern.tk_mask;
285 
286  if (tesla_key_matches(&pattern, &masked_name)) {
287  *trigger = t;
288  return UPDATE;
289  }
290 
291  } else {
292  /*
293  * Yes: we need to fork the generic instance
294  * into a more specific one.
295  */
296  if (tesla_key_matches(&pattern, &inst->ti_key)) {
297  *trigger = t;
298  return FORK;
299  }
300  }
301 
302  /*
303  * If we are in the right state but don't match on
304  * the pattern, even with a mask, move on to the
305  * next transition.
306  */
307  continue;
308  }
309 
310  /*
311  * We are not in the correct state for this transition, so
312  * we can't take it.
313  *
314  * If we match the pattern, however, it means that *some*
315  * transition must match; we are no longer allowed to ignore
316  * this instance.
317  */
318  if (tesla_key_matches(event_data, &inst->ti_key))
319  ignore = false;
320  }
321 
322  if (ignore)
323  return IGNORE;
324 
325  else
326  return FAIL;
327 }