ndr: Use resizing array instead of linked lists (breaking ABI)

The ndr token code keeps a temporary store of tokens which are
referred to a small number of times (often once) before being
discarded. The access patterns are somewhat stack-like, with recently
placed tokens being accessed most often.

The old code kept these tokens in a linked list, which we replace with
a self-resizing array.

This keeps everything roughly the same in big-O terms, but makes it
all faster in practice by vastly reducing the amount of tallocing and
pointer-chasing.

The peak memory use is strictly reduced. On a 64 bit machine each core
token struct fits in 16 bytes (after padding) while the two pointers
used by the DLIST add another 16 bytes, so the overall list allocation
is the same as the peak 2n array allocation -- except in the list case
it is dwarfed by the talloc and malloc metadata overhead.

Before settling on the resized arrays, we tried red-black trees, which
are bound to be better for large ndr structures. As it happens, we
don't deal with large structures (the size of replication clumps is
limited to 400 objects) and the asymptotic benefits of the trees are
not realised in practice.

With luck you should find graphs comparing the performance of these
various techniques at:

https://www.samba.org/~dbagnall/perf-tests/ndr-token/

This necessarily breaks the ABI because the linked list implementation
was publicly exposed.

Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>

Autobuild-User(master): Andrew Bartlett <abartlet@samba.org>
Autobuild-Date(master): Thu Mar  2 08:38:22 CET 2017 on sn-devel-144

2 files changed, 96 insertions, 52 deletions

diff --git a/librpc/ndr/libndr.h b/librpc/ndr/libndr.h
index b349c82fb79..d6e2e378bd2 100644
--- a/librpc/ndr/libndr.h
+++ b/librpc/ndr/libndr.h
@@ -38,16 +38,17 @@
 
 
 /*
-  this is used by the token store/retrieve code
+  We store the token mapping in an array that is resized as necessary.
 */
+struct ndr_token;
+
 struct ndr_token_list {
-	struct ndr_token_list *next, *prev;
-	const void *key;
-	uint32_t value;
+	struct ndr_token *tokens;
+	uint32_t count;
 };
 
-/* this is the base structure passed to routines that 
-   parse MSRPC formatted data 
+/* this is the base structure passed to routines that
+   parse MSRPC formatted data
 
    note that in Samba4 we use separate routines and structures for
    MSRPC marshalling and unmarshalling. Also note that these routines
@@ -63,12 +64,12 @@ struct ndr_pull {
 	uint32_t relative_highest_offset;
 	uint32_t relative_base_offset;
 	uint32_t relative_rap_convert;
-	struct ndr_token_list *relative_base_list;
+	struct ndr_token_list relative_base_list;
 
-	struct ndr_token_list *relative_list;
-	struct ndr_token_list *array_size_list;
-	struct ndr_token_list *array_length_list;
-	struct ndr_token_list *switch_list;
+	struct ndr_token_list relative_list;
+	struct ndr_token_list array_size_list;
+	struct ndr_token_list array_length_list;
+	struct ndr_token_list switch_list;
 
 	TALLOC_CTX *current_mem_ctx;
 
@@ -84,17 +85,17 @@ struct ndr_push {
 	uint32_t alloc_size;
 	uint32_t offset;
 	bool fixed_buf_size;
-	
+
 	uint32_t relative_base_offset;
 	uint32_t relative_end_offset;
-	struct ndr_token_list *relative_base_list;
+	struct ndr_token_list relative_base_list;
 
-	struct ndr_token_list *switch_list;
-	struct ndr_token_list *relative_list;
-	struct ndr_token_list *relative_begin_list;
-	struct ndr_token_list *nbt_string_list;
-	struct ndr_token_list *dns_string_list;
-	struct ndr_token_list *full_ptr_list;
+	struct ndr_token_list switch_list;
+	struct ndr_token_list relative_list;
+	struct ndr_token_list relative_begin_list;
+	struct ndr_token_list nbt_string_list;
+	struct ndr_token_list dns_string_list;
+	struct ndr_token_list full_ptr_list;
 
 	/* this is used to ensure we generate unique reference IDs */
 	uint32_t ptr_count;
@@ -104,7 +105,7 @@ struct ndr_push {
 struct ndr_print {
 	uint32_t flags; /* LIBNDR_FLAG_* */
 	uint32_t depth;
-	struct ndr_token_list *switch_list;
+	struct ndr_token_list switch_list;
 	void (*print)(struct ndr_print *, const char *, ...) PRINTF_ATTRIBUTE(2,3);
 	void *private_data;
 	bool no_newline;
@@ -534,12 +535,13 @@ enum ndr_err_code ndr_push_subcontext_end(struct ndr_push *ndr,
 				 size_t header_size,
 				 ssize_t size_is);
 enum ndr_err_code ndr_token_store(TALLOC_CTX *mem_ctx,
-			 struct ndr_token_list **list, 
-			 const void *key, 
+			 struct ndr_token_list *list,
+			 const void *key,
 			 uint32_t value);
-enum ndr_err_code ndr_token_retrieve_cmp_fn(struct ndr_token_list **list, const void *key, uint32_t *v, int(*_cmp_fn)(const void*,const void*), bool _remove_tok);
-enum ndr_err_code ndr_token_retrieve(struct ndr_token_list **list, const void *key, uint32_t *v);
-uint32_t ndr_token_peek(struct ndr_token_list **list, const void *key);
+enum ndr_err_code ndr_token_retrieve_cmp_fn(struct ndr_token_list *list, const void *key, uint32_t *v,
+					    int(*_cmp_fn)(const void*,const void*), bool erase);
+enum ndr_err_code ndr_token_retrieve(struct ndr_token_list *list, const void *key, uint32_t *v);
+uint32_t ndr_token_peek(struct ndr_token_list *list, const void *key);
 enum ndr_err_code ndr_pull_array_size(struct ndr_pull *ndr, const void *p);
 uint32_t ndr_get_array_size(struct ndr_pull *ndr, const void *p);
 enum ndr_err_code ndr_check_array_size(struct ndr_pull *ndr, void *p, uint32_t size);
diff --git a/librpc/ndr/ndr.c b/librpc/ndr/ndr.c
index e5ddba8a741..1c49c9a0ec4 100644
--- a/librpc/ndr/ndr.c
+++ b/librpc/ndr/ndr.c
@@ -138,11 +138,11 @@ _PUBLIC_ enum ndr_err_code ndr_pull_pop(struct ndr_pull *ndr)
 		return ndr_pull_error(ndr, NDR_ERR_RELATIVE,
 				      "%s", __location__);
 	}
-	if (ndr->relative_list != NULL) {
+	if (ndr->relative_list.count != 0) {
 		return ndr_pull_error(ndr, NDR_ERR_RELATIVE,
 				      "%s", __location__);
 	}
-	if (ndr->relative_base_list != NULL) {
+	if (ndr->relative_base_list.count != 0) {
 		return ndr_pull_error(ndr, NDR_ERR_RELATIVE,
 				      "%s", __location__);
 	}
@@ -914,40 +914,78 @@ _PUBLIC_ enum ndr_err_code ndr_push_subcontext_end(struct ndr_push *ndr,
 	return NDR_ERR_SUCCESS;
 }
 
+
+struct ndr_token {
+	const void *key;
+	uint32_t value;
+};
+
 /*
   store a token in the ndr context, for later retrieval
 */
 _PUBLIC_ enum ndr_err_code ndr_token_store(TALLOC_CTX *mem_ctx,
-			 struct ndr_token_list **list, 
-			 const void *key, 
+			 struct ndr_token_list *list,
+			 const void *key,
 			 uint32_t value)
 {
-	struct ndr_token_list *tok;
-	tok = talloc(mem_ctx, struct ndr_token_list);
-	NDR_ERR_HAVE_NO_MEMORY(tok);
-	tok->key = key;
-	tok->value = value;
-	DLIST_ADD((*list), tok);
+	if (list->tokens == NULL) {
+		list->tokens = talloc_array(mem_ctx, struct ndr_token, 10);
+		if (list->tokens == NULL) {
+			NDR_ERR_HAVE_NO_MEMORY(list->tokens);
+		}
+	} else {
+		uint32_t alloc_count = talloc_array_length(list->tokens);
+		if (list->count == alloc_count) {
+			unsigned new_alloc;
+			unsigned increment = MIN(list->count, 1000);
+			new_alloc = alloc_count + increment;
+			if (new_alloc < alloc_count) {
+				return NDR_ERR_RANGE;
+			}
+			list->tokens = talloc_realloc(mem_ctx, list->tokens,
+						      struct ndr_token, new_alloc);
+			if (list->tokens == NULL) {
+				NDR_ERR_HAVE_NO_MEMORY(list->tokens);
+			}
+		}
+	}
+	list->tokens[list->count].key = key;
+	list->tokens[list->count].value = value;
+	list->count++;
 	return NDR_ERR_SUCCESS;
 }
 
 /*
   retrieve a token from a ndr context, using cmp_fn to match the tokens
 */
-_PUBLIC_ enum ndr_err_code ndr_token_retrieve_cmp_fn(struct ndr_token_list **list, const void *key, uint32_t *v,
-				   comparison_fn_t _cmp_fn, bool _remove_tok)
-{
-	struct ndr_token_list *tok;
-	for (tok=*list;tok;tok=tok->next) {
-		if (_cmp_fn && _cmp_fn(tok->key,key)==0) goto found;
-		else if (!_cmp_fn && tok->key == key) goto found;
+_PUBLIC_ enum ndr_err_code ndr_token_retrieve_cmp_fn(struct ndr_token_list *list,
+						     const void *key, uint32_t *v,
+						     comparison_fn_t _cmp_fn,
+						     bool erase)
+{
+	struct ndr_token *tokens = list->tokens;
+	unsigned i;
+	if (_cmp_fn) {
+		for (i = list->count - 1; i < list->count; i--) {
+			if (_cmp_fn(tokens[i].key, key) == 0) {
+				goto found;
+			}
+		}
+	} else {
+		for (i = list->count - 1; i < list->count; i--) {
+			if (tokens[i].key == key) {
+				goto found;
+			}
+		}
 	}
 	return NDR_ERR_TOKEN;
 found:
-	*v = tok->value;
-	if (_remove_tok) {
-		DLIST_REMOVE((*list), tok);
-		talloc_free(tok);
+	*v = tokens[i].value;
+	if (erase) {
+		if (i != list->count - 1) {
+			tokens[i] = tokens[list->count - 1];
+		}
+		list->count--;
 	}
 	return NDR_ERR_SUCCESS;
 }
@@ -955,7 +993,8 @@ found:
 /*
   retrieve a token from a ndr context
 */
-_PUBLIC_ enum ndr_err_code ndr_token_retrieve(struct ndr_token_list **list, const void *key, uint32_t *v)
+_PUBLIC_ enum ndr_err_code ndr_token_retrieve(struct ndr_token_list *list,
+					      const void *key, uint32_t *v)
 {
 	return ndr_token_retrieve_cmp_fn(list, key, v, NULL, true);
 }
@@ -963,14 +1002,17 @@ _PUBLIC_ enum ndr_err_code ndr_token_retrieve(struct ndr_token_list **list, cons
 /*
   peek at but don't removed a token from a ndr context
 */
-_PUBLIC_ uint32_t ndr_token_peek(struct ndr_token_list **list, const void *key)
+_PUBLIC_ uint32_t ndr_token_peek(struct ndr_token_list *list, const void *key)
 {
-	struct ndr_token_list *tok;
-	for (tok = *list; tok; tok = tok->next) {
-		if (tok->key == key) {
-			return tok->value;
+	unsigned i;
+	struct ndr_token *tokens = list->tokens;
+
+	for (i = list->count - 1; i < list->count; i--) {
+		if (tokens[i].key == key) {
+			return tokens[i].value;
 		}
 	}
+
 	return 0;
 }