Re: [PATCH BlueZ v1] sdp-xml: Use a queue to collect sequence members

On Fri, 2026-08-14 at 13:32 -0400, Luiz Augusto von Dentz wrote:
> From: Luiz Augusto von Dentz <[email protected]>
> 
> Appending a member to a sequence with sdp_seq_append() walks the
> single-linked list to find its tail, so building a sequence is
> O(n^2).
> 
> This was previously worked around by caching the tail of the sequence
> in
> struct sdp_xml_data, which required the caller to pick between
> appending
> to the cached tail and initialising val.dataseq, and to keep the
> cache in
> sync on every append.
> 
> Collect the members in a struct queue instead, which tracks its own
> tail,
> and link them into val.dataseq once the element is closed. Appending
> is a
> plain queue_push_tail(), and the queue is destroyed along with the
> rest
> of the element so members that were never linked, such as on
> malformed
> input, are still freed.
> 
> The sequence_on_squared() test stays at less than 0.1 seconds.

Fails to link sdptool without this patch:

diff --git a/Makefile.tools b/Makefile.tools
index 1a4e5660813b..84004c12c642 100644
--- a/Makefile.tools
+++ b/Makefile.tools
@@ -437,7 +437,7 @@ tools_hciconfig_LDADD = lib/libbluetooth-internal.la
 tools_hcitool_SOURCES = tools/hcitool.c src/oui.h src/oui.c
 tools_hcitool_LDADD = lib/libbluetooth-internal.la $(UDEV_LIBS)
 
-tools_sdptool_SOURCES = tools/sdptool.c src/sdp-xml.h src/sdp-xml.c
+tools_sdptool_SOURCES = tools/sdptool.c src/shared/queue.h src/shared/queue.c src/shared/util.h src/shared/util.c src/sdp-xml.h src/sdp-xml.c
 tools_sdptool_LDADD = lib/libbluetooth-internal.la $(GLIB_LIBS)
 
 tools_ciptool_LDADD = lib/libbluetooth-internal.la

> 
> Assisted-by: Claude:claude-opus-5
> ---
>  src/sdp-xml.c | 60 ++++++++++++++++++++++++++++++++++++-------------
> --
>  1 file changed, 43 insertions(+), 17 deletions(-)
> 
> diff --git a/src/sdp-xml.c b/src/sdp-xml.c
> index 5b448fe83410..bad9e289344f 100644
> --- a/src/sdp-xml.c
> +++ b/src/sdp-xml.c
> @@ -25,6 +25,8 @@
>  #include "bluetooth/sdp.h"
>  #include "bluetooth/sdp_lib.h"
>  
> +#include "shared/queue.h"
> +
>  #include "sdp-xml.h"
>  
>  #define DBG(...) (void)(0)
> @@ -44,7 +46,7 @@ struct sdp_xml_data {
>  	char type;			/* 0 = Text or Hexadecimal
> */
>  	char *name;			/* Name, optional in the dtd
> */
>  	/* TODO: What is it used for? */
> -	sdp_data_t *tail;		/* Tail for O(1) dataseq
> append */
> +	struct queue *seq;		/* Members of a dataseq, if
> any */
>  };
>  
>  struct context_data {
> @@ -510,8 +512,37 @@ static void element_start(GMarkupParseContext
> *context,
>  	}
>  }
>  
> +/*
> + * Link the members collected in elem->seq into elem->data-
> >val.dataseq.
> + *
> + * Members are collected in a queue so that appending is O(1),
> sdp_seq_append()
> + * would otherwise have to walk to the tail of the sequence on every
> append.
> + */
> +static void sdp_xml_data_flush_seq(struct sdp_xml_data *elem)
> +{
> +	const struct queue_entry *entry;
> +	sdp_data_t *tail = NULL;
> +
> +	if (!elem->seq)
> +		return;
> +
> +	for (entry = queue_get_entries(elem->seq); entry; entry =
> entry->next) {
> +		if (tail)
> +			sdp_seq_append(tail, entry->data);
> +		else
> +			elem->data->val.dataseq =
> sdp_seq_append(NULL,
> +								entr
> y->data);
> +		tail = entry->data;
> +	}
> +
> +	queue_destroy(elem->seq, NULL);
> +	elem->seq = NULL;
> +}
> +
>  static void sdp_xml_data_free(struct sdp_xml_data *elem)
>  {
> +	queue_destroy(elem->seq, (queue_destroy_func_t)
> sdp_data_free);
> +
>  	if (elem->data)
>  		sdp_data_free(elem->data);
>  
> @@ -568,6 +599,8 @@ static void element_end(GMarkupParseContext
> *context,
>  		return;
>  	}
>  
> +	sdp_xml_data_flush_seq(ctx_data->stack_head);
> +
>  	if (!strcmp(element_name, "sequence")) {
>  		if (!SDP_IS_SEQ(ctx_data->stack_head->data->dtd)) {
>  			g_set_error(err, G_MARKUP_ERROR,
> @@ -610,28 +643,21 @@ static void element_end(GMarkupParseContext
> *context,
>  
>  	if (ctx_data->stack_head->next && ctx_data->stack_head->data
> &&
>  					ctx_data->stack_head->next-
> >data) {
> -		sdp_data_t *tail;
> -		switch (ctx_data->stack_head->next->data->dtd) {
> +		struct sdp_xml_data *parent = ctx_data->stack_head-
> >next;
> +
> +		switch (parent->data->dtd) {
>  		case SDP_SEQ8:
>  		case SDP_SEQ16:
>  		case SDP_SEQ32:
>  		case SDP_ALT8:
>  		case SDP_ALT16:
>  		case SDP_ALT32:
> -			tail = ctx_data->stack_head->next->data-
> >val.dataseq ?
> -				ctx_data->stack_head->next->tail :
> NULL;
> -			if (tail) {
> -				sdp_seq_append(tail,
> -					ctx_data->stack_head->data);
> -			} else {
> -				ctx_data->stack_head->next->data-
> >val.dataseq =
> -					sdp_seq_append(NULL,
> -						ctx_data-
> >stack_head->data);
> -			}
> -			ctx_data->stack_head->next->tail =
> -					ctx_data->stack_head->data;
> -			ctx_data->stack_head->data = NULL;
> -			ctx_data->stack_head->tail = NULL;
> +			if (!parent->seq)
> +				parent->seq = queue_new();
> +
> +			if (queue_push_tail(parent->seq,
> +						ctx_data-
> >stack_head->data))
> +				ctx_data->stack_head->data = NULL;
>  			break;
>  		}
>