Bug 83938

Created attachment 106384 [details] [review]
[PATCH v2] pending replies: use better data structures than a linked  list

From: Alban Crequy <alban.crequy@collabora.co.uk>

BusExpireList used to keep track of BusExpireItems/BusPendingReply in a unique
linked list without knowledge of the BusPendingReply struct. Iterating on the
linked list takes a linear time on the number of items. It is inefficient
because it iterates on items not relevant to the DBusConnection considered.

The total number of BusExpireItems on the bus can be quite large: with the
default limits on the system bus, it is 2097152 per user:
max_replies_per_connection * max_connections_per_user = (1024 * 8) * 256

The items in the BusExpireList are looked up in 3 different ways:
  1. When sending a D-Bus method call in bus_connections_expect_reply():
     check whether the exact triplet (DBusConnection caller, DBusConnection
     callee, dbus_uint32_t reply_serial) already exists and check whether the
     number of pending replies associated to the caller is over
     max_replies_per_connection.
  2. When sending a D-Bus return call in bus_connections_check_reply():
     find the exact triplet (DBusConnection caller, DBusConnection callee,
     dbus_uint32_t reply_serial)
  3. When a DBusConnection disconnects, iterate on the pending replies
     associated either with the connection as a caller or as a callee.

It becomes overly complicated to make a better data structure for theses use
cases without BusExpireItem having a reference to the caller, callee and
serial. BusExpireList was written in a generic way but is only used for pending
replies. This patch gets rid of the generic programming and store each
BusExpireItem in two hash tables keyed respectively by DBusConnection caller
and by DBusConnection callee.

In order to implement transactions correctly, a pending reply needs to be
removed and re-added in the BusExpireList without memory allocations. It was
done with linked lists by keeping the reference to the DBusList in
CheckPendingReplyData. In this new implementation, BusExpireItem has a new
field "dbus_bool_t deleted" and the BusExpireItem is only marked as deleted
when preparing the transaction and removed effectively when the transaction
finishes, with the bus_transaction_add_cancel_hook callbacks.

https://bugs.freedesktop.org/show_bug.cgi?id=81053
---
v1: first version
v2:
 - add some documentation
 - use the new API in the unit test
 - fix counting of deleted & non-deleted items
 - fix double free in bus_connections_check_reply
 - fix caller/callee confusion in bus_expire_list_foreach
 - fix memleaks in case of OOM in _bus_expire_list_add_helper

Comment on attachment 106384 [details] [review]
[PATCH v2] pending replies: use better data structures than a linked  list

Review of attachment 106384 [details] [review]:
-----------------------------------------------------------------

::: bus/expirelist.c
@@ +31,4 @@
>  
>  struct BusExpireList
>  {
> +  /* hash:

The only things I can see that these data structures could do more efficiently than a single hash table are "drop all BusExpireItem records for this caller" and "drop all BusExpireItem records for this callee" (both when a connection disconnects), and you currently do that by O(n) iteration over the whole lot anyway...

If O(n) iteration on each disconnection is good enough, we could introduce a special DBusHash mode for BusExpireItem, or for "use caller-supplied hashing and equality functions" like GHashTable, to be able to treat BusExpireItem as a (caller, callee, serial) triple and have one map

    (caller, callee, serial) -> BusExpireItem

?

@@ +48,5 @@
> +   *          - value: hash:
> +   *                   - key: int reply_serial
> +   *                   - value: BusExpireItem *item
> +   */
> +  DBusHashTable *callee;

In particular, I'm not convinced you need this hash table at all?

@@ +71,5 @@
>  
>  static dbus_bool_t expire_timeout_handler (void *data);
>  
> +static void
> +_safe_hash_unref (DBusHashTable *table)

Deserves a pseudo-doc-comment, I think:

/* because DBusHash will call your_free_function(NULL)
 * even if NULL was never actually stored in the hash */

@@ +128,4 @@
>  void
>  bus_expire_list_free (BusExpireList *list)
>  {
> +  _dbus_assert (list->non_deleted_items_count == 0);

Should you assert that there are no deleted items either?

@@ +425,5 @@
>  }
>  
> +/**
> + * Mark the item for deletion next time do_expiration_with_monotonic_time() is
> + * called. The item's memory will also be released by dbus_free.

I think "... released by dbus_free at that time" would make it clearer that it isn't freed right now

@@ +519,5 @@
> +    }
> +
> +  found3 = _dbus_hash_iter_lookup (hash3,
> +              _DBUS_INT_TO_POINTER (item->reply_serial), FALSE, &iter3);
> +  _dbus_assert (!found3);

What guarantees that this assertion will not fail?

(It seems the answer is bus_connections_expect_reply(). That deserves a comment here, I think.)

@@ +674,5 @@
> +  DBusHashTable *hash;
> +  BusExpireItem *item;
> +
> +  hash = _dbus_hash_table_lookup_uintptr (list->caller,
> +                                          _DBUS_POINTER_TO_INT (caller));

All lookups in this hash should be (uintptr_t) caller.

Confusingly, _DBUS_POINTER_TO_INT returns an intptr_t, not an int. It's still, strictly speaking, the wrong type (even if in practice the compiler will do the right thing for implicit signed -> unsigned conversion).

@@ +679,5 @@
> +  if (!hash)
> +    return NULL;
> +
> +  hash = _dbus_hash_table_lookup_uintptr (hash,
> +                                          _DBUS_POINTER_TO_INT (callee));

Same

@@ +683,5 @@
> +                                          _DBUS_POINTER_TO_INT (callee));
> +  if (!hash)
> +    return NULL;
> +
> +  item = _dbus_hash_table_lookup_int (hash, reply_serial);

This innermost hash table should really be keyed by something whose range is a superset of dbus_uint32_t's, like uintptr.

@@ +805,5 @@
> +  _dbus_assert (list->deleted_items_count == 0);
> +  _dbus_assert (list->non_deleted_items_count == 0);
> +
> +  /* add plenty of items */
> +  for (i = 0; i < 6; i++)

i < TEST_CONN_COUNT, etc.

@@ +830,5 @@
> +              dbus_free (items[i][j][k]);
> +            }
> +        }
> +
> +  _dbus_assert (list->deleted_items_count == 6 * 6 * 6 / 3);

s/6/TEST_CONN_COUNT/

@@ +842,5 @@
> +  _dbus_verbose ("next_interval = %d\n", next_interval);
> +  _dbus_assert (next_interval == 1);
> +  _dbus_assert (list->deleted_items_count == 0);
> +  _dbus_assert (list->non_deleted_items_count == 6 * 6 * 6 / 3);
> +  for (i = 0; i < 6; i++)

and here

So the big questions I have here are:

How large does max_connections_per_user * max_replies_per_connection have to be to make these nested hash tables more efficient than the O(n) list?

If you're going to leave bus_connection_drop_pending_replies() as a linear lookup, why did you use nested hash tables at all?

How large do the limits have to get before a non-linear bus_connection_drop_pending_replies() becomes worth it?

(In reply to comment #1)
> The items in the BusExpireList are looked up in 3 different ways:
>   1. When sending a D-Bus method call in bus_connections_expect_reply():
>      check whether the exact triplet (DBusConnection caller, DBusConnection
>      callee, dbus_uint32_t reply_serial) already exists and check whether the
>      number of pending replies associated to the caller is over
>      max_replies_per_connection.

The biggest cost an attacker can incur per second is currently O(max connections per user * max replies per connection * method calls / sec).

If the nested hash tables perform perfectly (optimistic assumption), your changes reduce this to O(method calls / sec).

A flat hash table keyed by triples would also be O(method calls / sec).

>   2. When sending a D-Bus return call in bus_connections_check_reply():
>      find the exact triplet (DBusConnection caller, DBusConnection callee,
>      dbus_uint32_t reply_serial)

The same.

>   3. When a DBusConnection disconnects, iterate on the pending replies
>      associated either with the connection as a caller or as a callee.

This is currently O(max connections per user * max replies per connection * reconnect cycles per second).

Your changes do not alter this. A flat hash table keyed by triples would also not alter this.

With a perfect implementation (making better use of the nested hash tables), optimistically assuming hash tables are O(1), this would reduce to O(reconnect cycles per second).

I suspect that the flat hash table has a bigger constant multiplier than the linked list, and your nested hash tables are likely to have a bigger constant multiplier than that, from the increased malloc/free activity if nothing else.

(In reply to comment #4)
> >   3. When a DBusConnection disconnects, iterate on the pending replies
> >      associated either with the connection as a caller or as a callee.
> 
> This is currently O(max connections per user * max replies per connection *
> reconnect cycles per second).

An attacker trying to waste CPU time like this would be limited by the fact that we've fixed Bug #80919, I think?

(In reply to comment #3)
> If you're going to leave bus_connection_drop_pending_replies() as a linear
> lookup, why did you use nested hash tables at all?

bus_connection_drop_pending_replies() itself is not linear on the total amount of BusExpireItem but only linear on the amount of BusExpireItem it needs to handle. so it is the best we can do. See bus_expire_list_foreach(): the first level of nested hash table is not an iterator loop but a simple lookup. For this to work, I make use of both top-level hash tables "caller" and "callee".

However, the callbacks use bus_expire_list_recheck_immediately() so it will trigger do_expiration_with_monotonic_time()/_bus_expire_list_cleanup_helper() to be run at the next iteration of the main loop, and the cleanup is linear on the total amount of BusExpireItem.

Since DBusHashTable does not have an API to insert an element without allocating memory (only DBusList has such API), I used the "dbus_bool_t deleted" trick to be able to complete or rollback a deletion. I have not found any way to implement do_expiration_with_monotonic_time()/_bus_expire_list_cleanup_helper() in a non-linear way because of the need to be able to rollback transactions. Ideas welcome here.

-- GitLab Migration Automatic Message --

This bug has been migrated to freedesktop.org's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.freedesktop.org/dbus/dbus/issues/111.