From ce969c6347b69180088c592e9184f05d0d3525c4 Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sat, 30 Aug 2003 02:56:12 +0000 Subject: 2003-08-29 Havoc Pennington * dbus/dbus-object-tree.c: modify to allow overlapping paths to be registered (struct DBusObjectSubtree): shrink this a lot, since we may have a lot of them (_dbus_object_tree_free_all_unlocked): implement (_dbus_object_tree_dispatch_and_unlock): implement --- ChangeLog | 9 + dbus/dbus-object-tree.c | 547 +++++++++++++++++++++++++++++++++++++----------- glib/dbus-gidl.c | 5 +- glib/dbus-gidl.h | 10 +- 4 files changed, 439 insertions(+), 132 deletions(-) diff --git a/ChangeLog b/ChangeLog index 489b1d51..8633080c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2003-08-29 Havoc Pennington + + * dbus/dbus-object-tree.c: modify to allow overlapping paths to be + registered + (struct DBusObjectSubtree): shrink this + a lot, since we may have a lot of them + (_dbus_object_tree_free_all_unlocked): implement + (_dbus_object_tree_dispatch_and_unlock): implement + 2003-08-29 Havoc Pennington * dbus/dbus-internals.h: fix _DBUS_N_GLOBAL_LOCKS diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 31724b7b..a2fc49e2 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -41,11 +41,11 @@ typedef struct DBusObjectSubtree DBusObjectSubtree; -DBusObjectSubtree* _dbus_object_subtree_new (const char **path, - const DBusObjectPathVTable *vtable, - void *user_data); -void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); -void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); +static DBusObjectSubtree* _dbus_object_subtree_new (const char **path, + const DBusObjectPathVTable *vtable, + void *user_data); +static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); +static void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); struct DBusObjectTree { @@ -63,11 +63,11 @@ struct DBusObjectTree struct DBusObjectSubtree { - int refcount; - char **path; - int n_path_elements; - DBusObjectPathVTable vtable; - void *user_data; + DBusAtomic refcount; + DBusObjectPathUnregisterFunction unregister_function; + DBusObjectPathMessageFunction message_function; + void *user_data; + char *path[1]; /**< Allocated as large as necessary */ }; DBusObjectTree* @@ -115,17 +115,9 @@ _dbus_object_tree_unref (DBusObjectTree *tree) if (tree->refcount == 0) { - if (tree->subtrees) - { - int i; - i = 0; - while (i < tree->n_subtrees) - { - _dbus_object_subtree_unref (tree->subtrees[i]); - ++i; - } - } + _dbus_object_tree_free_all_unlocked (tree); + dbus_free (tree->subtrees); dbus_free (tree); } } @@ -134,11 +126,10 @@ static int path_cmp (const char **path_a, const char **path_b) { - /* The comparison is as if the path were flattened - * into a single string. strcmp() considers - * a shorter string less than a longer string - * if the shorter string is the initial part - * of the longer + /* strcmp() considers a shorter string less than a longer string if + * the shorter string is the initial part of the longer. We + * consider a path with less elements less than a path with more + * elements. */ int i; @@ -187,28 +178,29 @@ subtree_qsort_cmp (const void *a, return subtree_cmp (*subtree_a_p, *subtree_b_p); } -/* Returns TRUE if a is a subdir of b or vice - * versa. This is the case if one is a subpath - * of the other. +/* Returns TRUE if container is a parent of child */ static dbus_bool_t -path_overlaps (const char **path_a, - const char **path_b) +path_contains (const char **container, + const char **child) { int i; i = 0; - while (path_a[i] != NULL) + while (child[i] != NULL) { int v; - if (path_b[i] == NULL) - return TRUE; /* b is subpath of a */ - - _dbus_assert (path_a[i] != NULL); - _dbus_assert (path_b[i] != NULL); + if (container[i] == NULL) + return TRUE; /* container ran out, child continues; + * thus the container is a parent of the + * child. + */ + + _dbus_assert (container[i] != NULL); + _dbus_assert (child[i] != NULL); - v = strcmp (path_a[i], path_b[i]); + v = strcmp (container[i], child[i]); if (v != 0) return FALSE; /* they overlap until here and then are different, @@ -218,9 +210,26 @@ path_overlaps (const char **path_a, ++i; } - /* b is either the same as or a superset of a */ - _dbus_assert (path_a[i] == NULL); - return TRUE; + /* Child ran out; if container also did, they are equal; + * otherwise, the child is a parent of the container. + */ + if (container[i] == NULL) + return TRUE; /* equal is counted as containing */ + else + return FALSE; +} + +static void +ensure_sorted (DBusObjectTree *tree) +{ + if (tree->subtrees && !tree->subtrees_sorted) + { + qsort (tree->subtrees, + tree->n_subtrees, + sizeof (DBusObjectSubtree*), + subtree_qsort_cmp); + tree->subtrees_sorted = TRUE; + } } static dbus_bool_t @@ -232,15 +241,8 @@ find_subtree (DBusObjectTree *tree, if (tree->subtrees == NULL) return FALSE; - - if (!tree->subtrees_sorted) - { - qsort (tree->subtrees, - tree->n_subtrees, - sizeof (DBusObjectSubtree*), - subtree_qsort_cmp); - tree->subtrees_sorted = TRUE; - } + + ensure_sorted (tree); /* FIXME this should be a binary search, * as that's the whole point of the sorting @@ -267,20 +269,60 @@ find_subtree (DBusObjectTree *tree, return FALSE; } +static dbus_bool_t +find_handler (DBusObjectTree *tree, + const char **path, + int *idx_p) +{ + int i; + int found_so_far; + + if (tree->subtrees == NULL) + return FALSE; + + ensure_sorted (tree); + + /* FIXME this should be a binary search, + * as that's the whole point of the sorting + */ + found_so_far = -1; + i = 0; + while (i < tree->n_subtrees) + { + /* Longer paths are after shorter, so we scan + * for the latest containing path in the array. + * If we did a binary search we'd start with + * the first search match. + */ + if (path_contains ((const char**) tree->subtrees[i]->path, + path)) + found_so_far = i; + else if (found_so_far >= 0) + break; /* no need to scan further */ + + ++i; + } + + if (idx_p) + *idx_p = found_so_far; + + return FALSE; +} + #ifndef DBUS_DISABLE_CHECKS static void -check_overlap (DBusObjectTree *tree, - const char **path) +check_already_exists (DBusObjectTree *tree, + const char **path) { int i; i = 0; while (i < tree->n_subtrees) { - if (path_overlaps (path, (const char**) tree->subtrees[i]->path)) + if (path_cmp (path, (const char**) tree->subtrees[i]->path) == 0) { - _dbus_warn ("New path (path[0] = %s) overlaps old path (path[0] = %s)\n", - path[0], tree->subtrees[i]->path[0]); + _dbus_warn ("New path (path[0] = %s) already registered\n", + path[0]); } ++i; } @@ -306,9 +348,11 @@ _dbus_object_tree_register (DBusObjectTree *tree, DBusObjectSubtree **new_subtrees; int new_n_subtrees; + _dbus_assert (tree != NULL); + _dbus_assert (vtable->message_function != NULL); _dbus_assert (path != NULL); #ifndef DBUS_DISABLE_CHECKS - check_overlap (tree, path); + check_already_exists (tree, path); #endif _dbus_assert (path[0] != NULL); @@ -319,10 +363,10 @@ _dbus_object_tree_register (DBusObjectTree *tree, /* FIXME we should do the "double alloc each time" standard thing */ new_n_subtrees = tree->n_subtrees + 1; new_subtrees = dbus_realloc (tree->subtrees, - new_n_subtrees); + new_n_subtrees * sizeof (DBusObjectSubtree*)); if (new_subtrees == NULL) { - _DBUS_ZERO (subtree->vtable); /* to avoid assertion in unref() */ + subtree->unregister_function = NULL; /* to avoid assertion in unref() */ _dbus_object_subtree_unref (subtree); return FALSE; } @@ -351,13 +395,15 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, _dbus_assert (path != NULL); _dbus_assert (path[0] != NULL); - + +#ifndef DBUS_DISABLE_CHECKS if (!find_subtree (tree, path, &i)) { _dbus_warn ("Attempted to unregister subtree (path[0] = %s) which isn't registered\n", path[0]); return; } +#endif subtree = tree->subtrees[i]; @@ -366,19 +412,21 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, &tree->subtrees[i+1], (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0])); tree->n_subtrees -= 1; - - _dbus_object_subtree_ref (subtree); + subtree->message_function = NULL; + /* Unlock and call application code */ _dbus_connection_unlock (tree->connection); - if (subtree->vtable.unregister_function) + if (subtree->unregister_function) { - (* subtree->vtable.unregister_function) (tree->connection, - (const char**) subtree->path, - subtree->user_data); - _DBUS_ZERO (subtree->vtable); + (* subtree->unregister_function) (tree->connection, + (const char**) subtree->path, + subtree->user_data); + subtree->unregister_function = NULL; } + + _dbus_object_subtree_unref (subtree); } /** @@ -392,15 +440,38 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, void _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) { + /* Delete them from the end, for slightly + * more robustness against odd reentrancy. + */ + while (tree->n_subtrees > 0) + { + DBusObjectSubtree *subtree; + subtree = tree->subtrees[tree->n_subtrees - 1]; + tree->subtrees[tree->n_subtrees - 1] = NULL; + subtree->message_function = NULL; /* it's been removed */ + /* Call application code */ + if (subtree->unregister_function) + { + (* subtree->unregister_function) (tree->connection, + (const char**) subtree->path, + subtree->user_data); + subtree->unregister_function = NULL; + } + + _dbus_object_subtree_unref (subtree); + } } /** - * Tries to dispatch a message by directing it to the object tree - * node listed in the message header, if any. + * Tries to dispatch a message by directing it to handler for the + * object path listed in the message header, if any. Messages are + * dispatched first to the registered handler that matches the largest + * number of path elements; that is, message to /foo/bar/baz would go + * to the handler for /foo/bar before the one for /foo. * - * @todo implement + * @todo thread problems * * @param tree the global object tree * @param message the message to dispatch @@ -410,70 +481,184 @@ DBusHandlerResult _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, DBusMessage *message) { + const char **path; + int i; + DBusList *list; + DBusList *link; + DBusHandlerResult result; + + path = NULL; /* dbus_message_get_object_path (message); */ + + if (path == NULL) + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + /* Find the deepest path that covers the path in the message */ + if (!find_handler (tree, path, &i)) + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + /* Build a list of all paths that cover the path in the message */ + + list = NULL; + + do + { + DBusObjectSubtree *subtree; + + subtree = tree->subtrees[i]; + + _dbus_object_subtree_ref (subtree); + _dbus_list_append (&list, subtree); + + --i; + + } while (i > 0 && path_contains ((const char**) tree->subtrees[i]->path, + path)); + + /* Invoke each handler in the list */ + + result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + link = _dbus_list_get_first_link (&list); + while (link != NULL) + { + DBusObjectSubtree *subtree = link->data; + DBusList *next = _dbus_list_get_next_link (&list, link); + + /* message_function is NULL if we're unregistered */ + if (subtree->message_function) + { + _dbus_connection_unlock (tree->connection); + + /* FIXME you could unregister the subtree in another thread + * before we invoke the callback, and I can't figure out a + * good way to solve this. + */ + + result = (* subtree->message_function) (tree->connection, + message, subtree->user_data); + + if (result == DBUS_HANDLER_RESULT_HANDLED) + goto free_and_return; + + _dbus_connection_lock (tree->connection); + } + + link = next; + } + + _dbus_connection_unlock (tree->connection); + + free_and_return: + while (list != NULL) + { + link = _dbus_list_get_first_link (&list); + _dbus_object_subtree_unref (link->data); + _dbus_list_remove_link (&list, link); + } + + return result; +} + +/** + * Allocates a subtree object with a string array appended as one big + * memory block, so result is freed with one dbus_free(). Returns + * #NULL if memory allocation fails. + * + * @param array array to duplicate. + * @returns newly-allocated subtree + */ +static DBusObjectSubtree* +allocate_subtree_object (const char **array) +{ + int len; + int member_lens; + int i; + char *p; + void *subtree; + char **path_dest; + const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, path); + if (array == NULL) + return NULL; + + member_lens = 0; + for (len = 0; array[len] != NULL; ++len) + member_lens += strlen (array[len]) + 1; + subtree = dbus_malloc (front_padding + + (len + 1) * sizeof (char*) + + member_lens); + if (subtree == NULL) + return NULL; + + path_dest = (char**) (((char*) subtree) + front_padding); + + path_dest[len] = NULL; /* NULL-terminate the array portion */ + p = ((char*) subtree) + (len + 1) * sizeof (char*) + front_padding; + + i = 0; + while (i < len) + { + int this_len; + + path_dest[i] = p; + + this_len = strlen (array[i]); + memcpy (p, array[i], this_len + 1); + p += this_len + 1; + + ++i; + } + + return subtree; } -DBusObjectSubtree* +static DBusObjectSubtree* _dbus_object_subtree_new (const char **path, const DBusObjectPathVTable *vtable, void *user_data) { DBusObjectSubtree *subtree; - subtree = dbus_new0 (DBusObjectSubtree, 1); + subtree = allocate_subtree_object (path); if (subtree == NULL) goto oom; _dbus_assert (path != NULL); _dbus_assert (path[0] != NULL); - - subtree->path = _dbus_dup_string_array (path); - if (subtree->path == NULL) - goto oom; - subtree->vtable = *vtable; + subtree->message_function = vtable->message_function; + subtree->unregister_function = vtable->unregister_function; subtree->user_data = user_data; - - subtree->refcount = 1; - - /* count path elements */ - while (subtree->path[subtree->n_path_elements]) - subtree->n_path_elements += 1; + subtree->refcount.value = 1; return subtree; oom: if (subtree) { - dbus_free_string_array (subtree->path); dbus_free (subtree); } return NULL; } -void +static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree) { - _dbus_assert (subtree->refcount > 0); - - subtree->refcount += 1; + _dbus_assert (subtree->refcount.value > 0); + _dbus_atomic_inc (&subtree->refcount); } -void +static void _dbus_object_subtree_unref (DBusObjectSubtree *subtree) { - _dbus_assert (subtree->refcount > 0); - - subtree->refcount -= 1; + _dbus_assert (subtree->refcount.value > 0); - if (subtree->refcount == 0) + if (_dbus_atomic_dec (&subtree->refcount) == 1) { - _dbus_assert (subtree->vtable.unregister_function == NULL); - - dbus_free_string_array (subtree->path); - + _dbus_assert (subtree->unregister_function == NULL); + _dbus_assert (subtree->message_function == NULL); dbus_free (subtree); } } @@ -484,6 +669,40 @@ _dbus_object_subtree_unref (DBusObjectSubtree *subtree) #include "dbus-test.h" #include +static char* +flatten_path (const char **path) +{ + DBusString str; + int i; + char *s; + + if (!_dbus_string_init (&str)) + return NULL; + + i = 0; + while (path[i]) + { + if (!_dbus_string_append_byte (&str, '/')) + goto nomem; + + if (!_dbus_string_append (&str, path[i])) + goto nomem; + + ++i; + } + + if (!_dbus_string_steal_data (&str, &s)) + goto nomem; + + _dbus_string_free (&str); + + return s; + + nomem: + _dbus_string_free (&str); + return NULL; +} + static dbus_bool_t test_subtree_cmp (const char **path1, const char **path2, @@ -531,12 +750,72 @@ test_subtree_cmp (const char **path1, } static void -test_path_overlap (const char **path1, - const char **path2, - dbus_bool_t expected) +test_path_contains (const char **path1, + const char **path2, + dbus_bool_t expected) +{ + if (!path_contains (path1, path2) == expected) + { + char *s1, *s2; + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s %s %s\n", + s1, expected ? "contains" : "doesn't contain", s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } + + if (path_cmp (path1, path2) == 0) + { + if (!path_contains (path2, path1)) + { + char *s1, *s2; + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s contains %s since the paths are equal\n", + s1, s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } + } + /* If path1 contains path2, then path2 can't contain path1 */ + else if (expected && path_contains (path2, path1)) + { + char *s1, *s2; + + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s doesn't contain %s\n", + s1, s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } +} + +static void +test_path_copy (const char **path) { - _dbus_assert (path_overlaps (path1, path2) == expected); - _dbus_assert (path_overlaps (path2, path1) == expected); + DBusObjectSubtree *subtree; + + subtree = allocate_subtree_object (path); + if (subtree == NULL) + return; + + _dbus_assert (path_cmp (path, (const char**) subtree->path) == 0); + + dbus_free (subtree); } static dbus_bool_t @@ -547,33 +826,63 @@ object_tree_test_iteration (void *data) const char *path3[] = { "foo", "bar", "baz", NULL }; const char *path4[] = { "foo", "bar", "boo", NULL }; const char *path5[] = { "blah", NULL }; + const char *path6[] = { "blah", "boof", NULL }; DBusObjectSubtree *subtree1; DBusObjectSubtree *subtree2; DBusObjectTree *tree; + test_path_copy (path1); + test_path_copy (path2); + test_path_copy (path3); + test_path_copy (path4); + test_path_copy (path5); + test_path_copy (path6); + tree = NULL; subtree1 = NULL; subtree2 = NULL; - test_path_overlap (path1, path1, TRUE); - test_path_overlap (path1, path2, TRUE); - test_path_overlap (path1, path3, TRUE); - test_path_overlap (path1, path4, TRUE); - test_path_overlap (path1, path5, FALSE); - - test_path_overlap (path2, path2, TRUE); - test_path_overlap (path2, path3, TRUE); - test_path_overlap (path2, path4, TRUE); - test_path_overlap (path2, path5, FALSE); - - test_path_overlap (path3, path3, TRUE); - test_path_overlap (path3, path4, FALSE); - test_path_overlap (path3, path5, FALSE); - - test_path_overlap (path4, path4, TRUE); - test_path_overlap (path4, path5, FALSE); - - test_path_overlap (path5, path5, TRUE); + test_path_contains (path1, path1, TRUE); + test_path_contains (path1, path2, TRUE); + test_path_contains (path1, path3, TRUE); + test_path_contains (path1, path4, TRUE); + test_path_contains (path1, path5, FALSE); + test_path_contains (path1, path6, FALSE); + + test_path_contains (path2, path1, FALSE); + test_path_contains (path2, path2, TRUE); + test_path_contains (path2, path3, TRUE); + test_path_contains (path2, path4, TRUE); + test_path_contains (path2, path5, FALSE); + test_path_contains (path2, path6, FALSE); + + test_path_contains (path3, path1, FALSE); + test_path_contains (path3, path2, FALSE); + test_path_contains (path3, path3, TRUE); + test_path_contains (path3, path4, FALSE); + test_path_contains (path3, path5, FALSE); + test_path_contains (path3, path6, FALSE); + + test_path_contains (path4, path1, FALSE); + test_path_contains (path4, path2, FALSE); + test_path_contains (path4, path3, FALSE); + test_path_contains (path4, path4, TRUE); + test_path_contains (path4, path5, FALSE); + test_path_contains (path4, path6, FALSE); + + test_path_contains (path5, path1, FALSE); + test_path_contains (path5, path2, FALSE); + test_path_contains (path5, path3, FALSE); + test_path_contains (path5, path4, FALSE); + test_path_contains (path5, path5, TRUE); + test_path_contains (path5, path6, TRUE); + + test_path_contains (path6, path1, FALSE); + test_path_contains (path6, path2, FALSE); + test_path_contains (path6, path3, FALSE); + test_path_contains (path6, path4, FALSE); + test_path_contains (path6, path5, FALSE); + test_path_contains (path6, path6, TRUE); if (!test_subtree_cmp (path1, path1, 0, TRUE)) goto out; diff --git a/glib/dbus-gidl.c b/glib/dbus-gidl.c index b6e0fb8c..c1a1f6dc 100644 --- a/glib/dbus-gidl.c +++ b/glib/dbus-gidl.c @@ -37,7 +37,6 @@ struct MethodInfo int refcount; GSList *args; char *name; - MethodStyle style; }; struct SignalInfo @@ -157,15 +156,13 @@ free_arg_list (GSList **args_p) } MethodInfo* -method_info_new (const char *name, - MethodStyle style) +method_info_new (const char *name) { MethodInfo *info; info = g_new0 (MethodInfo, 1); info->refcount = 1; info->name = g_strdup (name); - info->style = style; return info; } diff --git a/glib/dbus-gidl.h b/glib/dbus-gidl.h index c3c72d61..812e1866 100644 --- a/glib/dbus-gidl.h +++ b/glib/dbus-gidl.h @@ -40,13 +40,6 @@ typedef enum ARG_OUT } ArgDirection; -typedef enum -{ - METHOD_SYNC, - METHOD_ASYNC, - METHOD_CANCELLABLE -} MethodStyle; - InterfaceInfo* interface_info_new (const char *name); void interface_info_ref (InterfaceInfo *info); void interface_info_unref (InterfaceInfo *info); @@ -57,8 +50,7 @@ void interface_info_add_method (InterfaceInfo *info, void interface_info_add_signal (InterfaceInfo *info, SignalInfo *signal); -MethodInfo* method_info_new (const char *name, - MethodStyle style); +MethodInfo* method_info_new (const char *name); void method_info_ref (MethodInfo *info); void method_info_unref (MethodInfo *info); -- cgit v1.2.1