[PATCH] N-ary event operators
Scott James Remnant
scott at netsplit.com
Wed Aug 12 11:12:55 BST 2009
On Tue, 2009-08-11 at 17:33 -0400, Casey Dahlin wrote:
> This makes EventOperators N-ary rather than binary trees. It
> auto-optimizes them with a new event_operator_add_child helper that
> simply gifts all of the new child's children to the new parent rather
> than attaching it when the new parent and child are of the same type.
>
> This makes it a bit easier to make qualitative statements about trees,
> particularly "this tree only contains OR operators," which should become
> useful as AND operators become deprecated in future state models.
>
Thanks Casey.
Could you explain a little bit more about the rationale behind these
changes? Right now this just looks like a different way of constructing
the operator trees, and unless I'm mistaken, it's more expensive to
build them this way, they use more memory per node and they're more
difficult to iterate than the btrees we currently use.
Are you working on something else that requires this? Perhaps it'd help
to outline that work as well to the ML.
One thing I'd like to ask about - I don't have any plans to deprecate
AND operators; could you tell us a little bit about your plans in this
regard?
>
> === modified file 'ChangeLog'
> --- ChangeLog 2009-08-04 08:51:25 +0000
> +++ ChangeLog 2009-08-11 05:51:31 +0000
> @@ -1,3 +1,60 @@
> +2009-08-11 Casey Dahlin <cdahlin at redhat.com>
> +
> + * init/event_operator.h (EventOperatorType): Change types from AND/OR to
> + ANY/ALL
> +
> + (EventOperator): Get rid of node entry and add children list.
> +
> + * init/event_operator.c (event_operator_subtree_environment): New
> + version of event_operator_environment that assumes we are not at the
> + root of the tree.
> +
> + (event_operator_new): Initialize new children member instead of tree
> + node.
> +
> + (event_operator_copy): Use recursive call to correctly copy N-ary tree
> +
> + (event_operator_reset): Use recursive call to correctly reset N-ary tree
> +
> + (event_operator_events): Use recursive call to correctly get events from
> + N-ary tree.
> +
> + (event_operator_handle): Use recursive call to correctly handle N-ary
> + tree.
> +
> + (event_operator_update): Update based on all N children
> +
> + (event_operator_match): Don't assert based on now-defunct node
> +
> + (event_operator_add_child): New helper to add a child to a tree,
> + automatically collapsing it into its new parent if it is the same type.
> +
> + (event_operator_destroy): Destroy children list head correctly.
> +
> + (event_operator_environment): Use new event_operator_subtree_environment
> + to recursively collect environment variables.
> +
> + * init/parse_job.c (parse_on_operator): Change AND/OR to ANY/ALL. Change
> + tree adds to event_operator_add_child calls.
> +
> + (parse_on_collect): Change tree adds to event_operator_add_child calls
> +
> + * init/tests/test_event.c (test_pending_handle_jobs): Fix structural
> + assumptions about EventOperator.
> +
> + (test_finish): Change AND/OR to ANY/ALL
> +
> + * init/tests/test_event_operator.c (everywhere): Fix structural
> + assumptions about EventOperator.
> +
> + (test_operator_add_child): New test for this new helper.
> +
> + * init/tests/test_job_process.c (everywhere): Fix structural assumptions
> + about EventOperator
> +
> + * init/tests/test_parse_job.c (everywhere): Fix structural assumptions
> + about EventOperator
> +
> 2009-08-04 Johan Kiviniemi <johan at kiviniemi.name>
>
> * conf/rc-sysinit.conf: Don't replace DEFAULT_RUNLEVEL with an
>
ChangeLog entries should be grouped together with a blank line only
between individual commits.
Avoid using the 80th column.
> === modified file 'init/event_operator.c'
> --- init/event_operator.c 2009-06-23 09:29:35 +0000
> +++ init/event_operator.c 2009-08-11 05:12:01 +0000
> @@ -43,6 +43,9 @@
> #include "blocked.h"
> #include "errors.h"
>
> +static char** event_operator_subtree_environment
> + (EventOperator *oper, char ***env, const void *parent,
> + size_t *len, const char *key, char **evlist);
>
> /**
> * event_operator_new:
Should be "static char **", should be preceeded by a comment and have
extra blank lines around (see other source files for examples). The
opening paren, and thus the arguments, should follow even if you have to
indent strangely.
> + NIH_LIST_FOREACH (&old_oper->children, iter) {
> + EventOperator *child = event_operator_copy (
> + oper, (EventOperator *)iter);
> + if (! child) {
> + nih_free (oper);
> + return NULL;
> + }
> +
> + event_operator_add_child (oper, child);
> }
Don't use initialisers like this, it's much better style to do:
EventOperator *old_child = (EventOperator *)iter;
EventOperator *child;
child = event_operator_copy (oper, old_child);
if (! child) {
nih_free (oper);
return NULL;
}
> /**
> + * event_operator_add_child:
> + * @oper: oper to add child to,
> + * @child: child to add.
> + *
> + * Makes @child a child of @oper. If @child and @oper are the same
> type, then
> + * @oper simply steals all of @child's children.
> + **/
> +void
> +event_operator_add_child (EventOperator *oper, EventOperator *child)
> +{
> + nih_assert (oper != NULL);
> + nih_assert (child != NULL);
> + nih_assert (oper->type != EVENT_MATCH);
> +
> + if (child->type != oper->type) {
> + nih_ref (child, oper);
> + nih_list_add (&oper->children, &child->entry);
> + return;
> + }
> +
> + NIH_LIST_FOREACH_SAFE (&child->children, iter) {
> + EventOperator *grandchild = (EventOperator *)iter;
> +
> + nih_ref (grandchild, oper);
> + nih_unref (grandchild, child);
> + nih_list_add (&oper->children, &grandchild->entry);
> + }
> +}
Doc string should mention that the child will be referenced by the new
parent.
This seems a bit strange in the adding-the-same-type case; it moves all
the chidren of the old node to the new node, but not the old node
itself? What happens to the old node, it looks like it just gets left
in the tree?
Why doesn't this function no-op in the adding-the-same-type case, and
discard the new node instead?
> @@ -227,24 +249,17 @@
> void
> event_operator_update (EventOperator *oper)
> {
> - EventOperator *left, *right;
> -
> nih_assert (oper != NULL);
> - nih_assert (oper->node.left != NULL);
> - nih_assert (oper->node.right != NULL);
> -
> - left = (EventOperator *)oper->node.left;
> - right = (EventOperator *)oper->node.right;
> -
> - switch (oper->type) {
> - case EVENT_OR:
> - oper->value = (left->value || right->value);
> - break;
> - case EVENT_AND:
> - oper->value = (left->value && right->value);
> - break;
> - default:
> - nih_assert_not_reached ();
> + nih_assert (oper->type != EVENT_MATCH);
> +
> + oper->value = (oper->type == EVENT_ALL) ? TRUE : FALSE;
> +
> + NIH_LIST_FOREACH (&oper->children, iter) {
> + EventOperator *child = (EventOperator *)iter;
> + if (child->value != oper->value) {
> + oper->value = child->value;
> + return;
> + }
> }
> }
>
Should have a blank line between initialisers and checks.
Probably should have a comment explaining how this works, since it's a
bit "clever" :-)
> @@ -391,29 +404,30 @@
> * before we update the node itself. Simply iterate the tree and
> * update the nodes.
> */
> - NIH_TREE_FOREACH_POST (&root->node, iter) {
> + NIH_LIST_FOREACH (&root->children, iter) {
> EventOperator *oper = (EventOperator *)iter;
>
> - switch (oper->type) {
> - case EVENT_OR:
> - case EVENT_AND:
> - event_operator_update (oper);
> - break;
> - case EVENT_MATCH:
> - if ((! oper->value)
> - && event_operator_match (oper, event, env)) {
> - oper->value = TRUE;
> -
> - oper->event = event;
> - event_block (oper->event);
> -
> - ret = TRUE;
> - }
> - break;
> - default:
> - nih_assert_not_reached ();
> + ret = ret || event_operator_handle (oper, event, env);
> + }
> +
> + switch (root->type) {
> + case EVENT_ANY:
> + case EVENT_ALL:
> + event_operator_update (root);
> + break;
> + case EVENT_MATCH:
> + if ((! root->value)
> + && event_operator_match (root, event, env)) {
> + root->value = TRUE;
> +
> + root->event = event;
> + event_block (root->event);
> +
> + ret = TRUE;
> }
> -
> + break;
> + default:
> + nih_assert_not_reached ();
> }
>
> return ret;
I generally dislike:
ret = ret || ...
forms, instead please be more specific.
Why the change to recursively calling event_operator_handle() where this
wasn't needed before?
Why moving everything from out of the loop acting on oper to inside the
loop acting on root?
You left the comment about this being a post-order traversal, but this
doesn't appear to be an any-kind-of-order traversal anymore?
> @@ -501,38 +515,9 @@
> return NULL;
> }
>
> - /* Iterate the operator tree, filtering out nodes with a non-TRUE
> - * value and their children. The rationale for this is that this
> - * then matches only the events that had an active role in starting
> - * the job, not the ones that were also blocked, but the other half
> - * of their logic wasn't present.
> - */
> - NIH_TREE_FOREACH_FULL (&root->node, iter,
> - (NihTreeFilter)event_operator_filter, NULL) {
> - EventOperator *oper = (EventOperator *)iter;
> -
> - if (oper->type != EVENT_MATCH)
> - continue;
> -
> - nih_assert (oper->event != NULL);
> -
> - /* Add environment from the event */
> - if (! environ_append (env, parent, len, TRUE, oper->event->env))
> - return NULL;
> -
> - /* Append the name of the event to the string we're building */
> - if (evlist) {
> - if (evlist[strlen (evlist) - 1] != '=') {
> - if (! nih_strcat_sprintf (&evlist, NULL, " %s",
> - oper->event->name))
> - return NULL;
> - } else {
> - if (! nih_strcat (&evlist, NULL,
> - oper->event->name))
> - return NULL;
> - }
> - }
> - }
> + if (! event_operator_subtree_environment (root, env, parent,
> + len, key, &evlist))
> + return NULL;
>
> /* Append the event list to the environment */
> if (evlist)
> @@ -543,6 +528,68 @@
> }
>
> /**
> + * event_operator_subtree_environment:
> + * @root: operator tree to collect from,
> + * @env: NULL-terminated array of environment variables to add to,
> + * @parent: parent object for new array,
> + * @len: length of @env,
> + * @key: key of variable to contain event names,
> + * @evlist: string in which to accumulate the event list.
> + *
> + * Does the work of event_operator_environment for one subtree.
> + **/
> +
> +static char**
> +event_operator_subtree_environment (EventOperator *oper,
> + char ***env,
> + const void *parent,
> + size_t *len,
> + const char *key,
> + char **evlist)
> +{
> + /* Filtering out nodes with a non-TRUE value and their children. The
> + * rationale for this is that this then matches only the events that had
> + * an active role in starting the job, not the ones that were also
> + * blocked, but the other half of their logic wasn't present.
> + */
> + if (! oper->value)
> + return *env;
> +
> + if (oper->type != EVENT_MATCH) {
> + NIH_LIST_FOREACH(&oper->children, iter) {
> + EventOperator *child = (EventOperator *)iter;
> + if (! event_operator_subtree_environment (child, env, parent,
> + len, key, evlist))
> + return NULL;
> + }
> +
> + return *env;
> + }
> +
> + nih_assert (oper->event != NULL);
> +
> + /* Add environment from the event */
> + if (! environ_append (env, parent, len, TRUE, oper->event->env))
> + return NULL;
> +
> + /* Append the name of the event to the string we're building */
> + if (*evlist) {
> + if ((*evlist)[strlen (*evlist) - 1] != '=') {
> + if (! nih_strcat_sprintf (evlist, NULL, " %s",
> + oper->event->name))
> + return NULL;
> + } else {
> + if (! nih_strcat (evlist, NULL,
> + oper->event->name)) {
> + return NULL;
> + }
> + }
> + }
> +
> + return *env;
> +}
Why the need to split this into two functions and call it recursively,
when it was one non-recursive function before?
> +
> +/**
> * event_operator_events:
> * @root: operator tree to collect from,
> * @parent: parent object for blocked structures,
> @@ -564,31 +611,31 @@
> const void *parent,
> NihList *list)
> {
> + Blocked *blocked;
> +
> nih_assert (root != NULL);
> nih_assert (list != NULL);
>
> - /* Iterate the operator tree, filtering out nodes with a non-TRUE
> - * value and their children. The rationale for this is that this
> - * then matches only the events that had an active role in starting
> - * the job, not the ones that were also blocked, but the other half
> - * of their logic wasn't present.
> - */
> - NIH_TREE_FOREACH_FULL (&root->node, iter,
> - (NihTreeFilter)event_operator_filter, NULL) {
> + if (! root->value)
> + return;
> +
> + NIH_LIST_FOREACH (&root->children, iter) {
> EventOperator *oper = (EventOperator *)iter;
> - Blocked *blocked;
> -
> - if (oper->type != EVENT_MATCH)
> - continue;
> -
> - nih_assert (oper->event != NULL);
> -
> - blocked = NIH_MUST (blocked_new (parent, BLOCKED_EVENT,
> - oper->event));
> - nih_list_add (list, &blocked->entry);
> -
> - event_block (blocked->event);
> +
> + event_operator_events (oper, parent, list);
> }
> +
> +
> + if (root->type != EVENT_MATCH)
> + return;
> +
> + nih_assert (root->event != NULL);
> +
> + blocked = NIH_MUST (blocked_new (parent, BLOCKED_EVENT,
> + root->event));
> + nih_list_add (list, &blocked->entry);
> +
> + event_block (blocked->event);
> }
>
Again, this looks like it's gone from one non-recursive function into a
recursive one?
>
> @@ -606,24 +653,26 @@
> nih_assert (root != NULL);
>
> /* A post-order iteration means we visit children first, perfect! */
> - NIH_TREE_FOREACH_POST (&root->node, iter) {
> + NIH_LIST_FOREACH (&root->children, iter) {
> EventOperator *oper = (EventOperator *)iter;
>
> - switch (oper->type) {
> - case EVENT_OR:
> - case EVENT_AND:
> - event_operator_update (oper);
> - break;
> - case EVENT_MATCH:
> - oper->value = FALSE;
> -
> - if (oper->event) {
> - event_unblock (oper->event);
> - oper->event = NULL;
> - }
> - break;
> - default:
> - nih_assert_not_reached ();
> + event_operator_reset (oper);
> + }
> +
> + switch (root->type) {
> + case EVENT_ANY:
> + case EVENT_ALL:
> + event_operator_update (root);
> + break;
> + case EVENT_MATCH:
> + root->value = FALSE;
> +
> + if (root->event) {
> + event_unblock (root->event);
> + root->event = NULL;
> }
> + break;
> + default:
> + nih_assert_not_reached ();
> }
> }
>
Again, you've switched from non-recursive code to recursive code?
> === modified file 'init/event_operator.h'
> --- init/event_operator.h 2009-06-23 09:29:35 +0000
> +++ init/event_operator.h 2009-08-11 05:12:01 +0000
> @@ -33,14 +33,15 @@
> * the EventOperator structure.
> **/
> typedef enum event_operator_type {
> - EVENT_OR,
> - EVENT_AND,
> + EVENT_ANY,
> + EVENT_ALL,
> EVENT_MATCH
> } EventOperatorType;
>
Why the rename of the operators? The use of "any" here seems especially
confusing given the meaning penned in some of the design discussions,
lit.
while dbus-daemon
(while a dbus-daemon is running, with an instance created for each
running dbus daemon)
while any dbus-daemon
(while at least one dbus-daemon is running, only one instance)
> @@ -665,10 +665,8 @@
> if (! oper)
> nih_return_system_error (-1);
>
> - nih_ref (*root, oper);
> + event_operator_add_child (oper, *root);
> nih_unref (*root, class);
> -
> - nih_tree_add (&oper->node, &(*root)->node, NIH_TREE_LEFT);
> *root = NULL;
>
> /* Push the new operator onto the stack */
The comment on event_operator_add_child would go a long way to helping
realise there's no leak here.
> @@ -938,11 +936,8 @@
> * event matches.
> */
> if ((oper->type != EVENT_MATCH) && (*root)) {
> - nih_ref (*root, oper);
> + event_operator_add_child (oper, *root);
> nih_unref (*root, class);
> -
> - nih_tree_add (&oper->node, &(*root)->node,
> - NIH_TREE_RIGHT);
> } else if (oper->type != EVENT_MATCH) {
> nih_return_error (-1, PARSE_EXPECTED_EVENT,
> _(PARSE_EXPECTED_EVENT_STR));
>
Likewise here.
> @@ -358,13 +357,18 @@
> TEST_EQ (oper->value, FALSE);
> TEST_EQ_P (oper->event, NULL);
>
> - oper = (EventOperator *)class->start_on->node.left;
> - TEST_EQ (oper->value, TRUE);
> - TEST_EQ_P (oper->event, event1);
> -
> - oper = (EventOperator *)class->start_on->node.right;
> - TEST_EQ (oper->value, FALSE);
> - TEST_EQ_P (oper->event, NULL);
> + NIH_LIST_FOREACH (&oper->children, iter) {
> + EventOperator *child = (EventOperator *)iter;
> +
> + any_true = any_true || child->value;
> + all_true = all_true && child->value;
> + }
> +
> + TEST_EQ (any_true, TRUE);
> + TEST_EQ (all_true, FALSE);
> +
> + any_true = FALSE;
> + all_true = TRUE;
>
> nih_free (class);
> nih_free (event1);
This any_true/all_true stuff is a bit "clever", and it seems to matter
whether one is set to TRUE first and the other FALSE.
General style:
TEST_TRUE (any_true);
TEST_FALSE (all_true);
(snipped a couple of instances of this, but applies to all)
> @@ -518,8 +494,6 @@
>
>
> nih_free (oper1);
> - nih_free (oper2);
> - nih_free (oper3);
> }
>
Why the loss of these?
> @@ -938,10 +912,6 @@
> event_operator_reset (oper1);
>
> nih_free (oper1);
> - nih_free (oper2);
> - nih_free (oper3);
> - nih_free (oper4);
> - nih_free (oper5);
>
> event_poll ();
> }
Likewise.
> @@ -1274,15 +1244,73 @@
> TEST_EQ (event2->blockers, 0);
>
> nih_free (oper1);
> - nih_free (oper2);
> - nih_free (oper3);
> - nih_free (oper4);
> - nih_free (oper5);
>
> event_poll ();
> }
>
And again?
>
> +void
> +test_operator_add_child (void)
> +{
> + EventOperator *oper1, *oper2, *oper3, *oper4, *oper5, *oper6, *oper7;
> + int found_foo = 0;
> + int found_bar = 0;
> + int found_baz = 0;
> + int found_bam = 0;
> + int found_all = 0;
> +
> + TEST_FUNCTION ("event_operator_add_child");
> + oper1 = event_operator_new (NULL, EVENT_ANY, NULL, NULL);
> + oper2 = event_operator_new (NULL, EVENT_ALL, NULL, NULL);
> + oper3 = event_operator_new (NULL, EVENT_MATCH, "foo", NULL);
> + oper4 = event_operator_new (NULL, EVENT_MATCH, "bar", NULL);
> + oper5 = event_operator_new (NULL, EVENT_MATCH, "baz", NULL);
> + oper6 = event_operator_new (NULL, EVENT_MATCH, "bam", NULL);
> + oper7 = event_operator_new (NULL, EVENT_ANY, NULL, NULL);
> +
> + event_operator_add_child (oper2, oper3);
> + event_operator_add_child (oper2, oper4);
> + event_operator_add_child (oper7, oper5);
> + event_operator_add_child (oper7, oper6);
> + event_operator_add_child (oper1, oper2);
> + event_operator_add_child (oper1, oper7);
> +
> + TEST_EQ (oper1->type, EVENT_ANY);
> +
> + NIH_LIST_FOREACH (&oper1->children, iter) {
> + EventOperator *child = (EventOperator *)iter;
> +
> + if (child->type == EVENT_ALL) {
> + found_all++;
> + continue;
> + }
> +
> + TEST_EQ (child->type, EVENT_MATCH);
> +
> + if (! strncmp (child->name, "foo", 4))
> + found_foo++;
> +
> + if (! strncmp (child->name, "bar", 4))
> + found_bar++;
> +
> + if (! strncmp (child->name, "baz", 4))
> + found_baz++;
> +
> + if (! strncmp (child->name, "bam", 4))
> + found_bam++;
> + }
> +
> + // Not a truth test. 2 is also a failure.
> + TEST_EQ (found_all, 1);
> + TEST_EQ (found_foo, 0);
> + TEST_EQ (found_bar, 0);
> + TEST_EQ (found_baz, 1);
> + TEST_EQ (found_bam, 1);
> +
> + nih_free (oper1);
> +}
This test case could do with some cleaning up, it's not really very well
explained and I can't quite figure out what you're testing.
Use of TEST_FAILED should match the other uses of it.
Why strncmp() not strcmp() ?
Don't use //
> @@ -1901,31 +1896,26 @@
> TEST_ALLOC_PARENT (job->start_on, job);
>
> oper = job->start_on;
> - TEST_EQ (oper->type, EVENT_OR);
> -
> - TEST_EQ_P (oper->node.parent, NULL);
> - TEST_ALLOC_SIZE (oper->node.left, sizeof (EventOperator));
> - TEST_ALLOC_PARENT (oper->node.left, oper);
> - TEST_ALLOC_SIZE (oper->node.right, sizeof (EventOperator));
> - TEST_ALLOC_PARENT (oper->node.right, oper);
> -
> - oper = (EventOperator *)job->start_on->node.left;
> - TEST_EQ (oper->type, EVENT_MATCH);
> - TEST_EQ_STR (oper->name, "wibble");
> - TEST_EQ_P (oper->env, NULL);
> -
> - TEST_EQ_P (oper->node.parent, &job->start_on->node);
> - TEST_EQ_P (oper->node.left, NULL);
> - TEST_EQ_P (oper->node.right, NULL);
> -
> - oper = (EventOperator *)job->start_on->node.right;
> - TEST_EQ (oper->type, EVENT_MATCH);
> - TEST_EQ_STR (oper->name, "wobble");
> - TEST_EQ_P (oper->env, NULL);
> -
> - TEST_EQ_P (oper->node.parent, &job->start_on->node);
> - TEST_EQ_P (oper->node.left, NULL);
> - TEST_EQ_P (oper->node.right, NULL);
> + TEST_EQ (oper->type, EVENT_ANY);
> +
> + got_wibble = FALSE;
> + got_wobble = FALSE;
> + EventOperator *parent = oper;
> + NIH_LIST_FOREACH (&oper->children, iter) {
> + EventOperator *child = (EventOperator *)iter;
> +
> + TEST_ALLOC_SIZE (child, sizeof (EventOperator));
> +
> + TEST_LIST_EMPTY (&child->children);
> + TEST_EQ_P (child->env, NULL);
> + TEST_EQ (child->type, EVENT_MATCH);
> + if (!strncmp ("wibble", child->name, 7) && ! got_wibble)
> + got_wibble = TRUE;
> + else if (!strncmp ("wobble", child->name, 7) && ! got_wobble)
> + got_wobble = TRUE;
> + else
> + TEST_FAILED ("Unexpected child");
> + }
>
> nih_free (job);
> }
List iteration should be separated by a gap.
Why are you using strncmp() here?
"if (! ...)" not "if (!...)"
"&& (! ...)" not "&& ! ..."
if/else without { } is punishable by death ;-)
TEST_FAILED should match the output of others
(A couple of instances of these)
Scott
--
Have you ever, ever felt like this?
Had strange things happen? Are you going round the twist?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/upstart-devel/attachments/20090812/296971b7/attachment.pgp
More information about the upstart-devel
mailing list