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

diff --git a/librpc/ABI/ndr-0.1.0.sigs b/librpc/ABI/ndr-0.1.0.sigs
new file mode 100644 (file)
index 0000000..80a3faf
--- /dev/null
+++ b/librpc/ABI/ndr-0.1.0.sigs
@@ -0,0 +1,259 @@
+GUID_all_zero: bool (const struct GUID *)
+GUID_buf_string: char *(const struct GUID *, struct GUID_txt_buf *)
+GUID_compare: int (const struct GUID *, const struct GUID *)
+GUID_equal: bool (const struct GUID *, const struct GUID *)
+GUID_from_data_blob: NTSTATUS (const DATA_BLOB *, struct GUID *)
+GUID_from_ndr_blob: NTSTATUS (const DATA_BLOB *, struct GUID *)
+GUID_from_string: NTSTATUS (const char *, struct GUID *)
+GUID_hexstring: char *(TALLOC_CTX *, const struct GUID *)
+GUID_random: struct GUID (void)
+GUID_string: char *(TALLOC_CTX *, const struct GUID *)
+GUID_string2: char *(TALLOC_CTX *, const struct GUID *)
+GUID_to_ndr_blob: NTSTATUS (const struct GUID *, TALLOC_CTX *, DATA_BLOB *)
+GUID_zero: struct GUID (void)
+ndr_align_size: size_t (uint32_t, size_t)
+ndr_charset_length: uint32_t (const void *, charset_t)
+ndr_check_array_length: enum ndr_err_code (struct ndr_pull *, void *, uint32_t)
+ndr_check_array_size: enum ndr_err_code (struct ndr_pull *, void *, uint32_t)
+ndr_check_padding: void (struct ndr_pull *, size_t)
+ndr_check_pipe_chunk_trailer: enum ndr_err_code (struct ndr_pull *, int, uint32_t)
+ndr_check_string_terminator: enum ndr_err_code (struct ndr_pull *, uint32_t, uint32_t)
+ndr_get_array_length: uint32_t (struct ndr_pull *, const void *)
+ndr_get_array_size: uint32_t (struct ndr_pull *, const void *)
+ndr_map_error2errno: int (enum ndr_err_code)
+ndr_map_error2ntstatus: NTSTATUS (enum ndr_err_code)
+ndr_map_error2string: const char *(enum ndr_err_code)
+ndr_policy_handle_empty: bool (const struct policy_handle *)
+ndr_policy_handle_equal: bool (const struct policy_handle *, const struct policy_handle *)
+ndr_print_DATA_BLOB: void (struct ndr_print *, const char *, DATA_BLOB)
+ndr_print_GUID: void (struct ndr_print *, const char *, const struct GUID *)
+ndr_print_HRESULT: void (struct ndr_print *, const char *, HRESULT)
+ndr_print_KRB5_EDATA_NTSTATUS: void (struct ndr_print *, const char *, const struct KRB5_EDATA_NTSTATUS *)
+ndr_print_NTSTATUS: void (struct ndr_print *, const char *, NTSTATUS)
+ndr_print_NTTIME: void (struct ndr_print *, const char *, NTTIME)
+ndr_print_NTTIME_1sec: void (struct ndr_print *, const char *, NTTIME)
+ndr_print_NTTIME_hyper: void (struct ndr_print *, const char *, NTTIME)
+ndr_print_WERROR: void (struct ndr_print *, const char *, WERROR)
+ndr_print_array_uint8: void (struct ndr_print *, const char *, const uint8_t *, uint32_t)
+ndr_print_bad_level: void (struct ndr_print *, const char *, uint16_t)
+ndr_print_bitmap_flag: void (struct ndr_print *, size_t, const char *, uint32_t, uint32_t)
+ndr_print_bool: void (struct ndr_print *, const char *, const bool)
+ndr_print_debug: void (ndr_print_fn_t, const char *, void *)
+ndr_print_debug_helper: void (struct ndr_print *, const char *, ...)
+ndr_print_debugc: void (int, ndr_print_fn_t, const char *, void *)
+ndr_print_debugc_helper: void (struct ndr_print *, const char *, ...)
+ndr_print_dlong: void (struct ndr_print *, const char *, int64_t)
+ndr_print_double: void (struct ndr_print *, const char *, double)
+ndr_print_enum: void (struct ndr_print *, const char *, const char *, const char *, uint32_t)
+ndr_print_function_debug: void (ndr_print_function_t, const char *, int, void *)
+ndr_print_function_string: char *(TALLOC_CTX *, ndr_print_function_t, const char *, int, void *)
+ndr_print_get_switch_value: uint32_t (struct ndr_print *, const void *)
+ndr_print_gid_t: void (struct ndr_print *, const char *, gid_t)
+ndr_print_hyper: void (struct ndr_print *, const char *, uint64_t)
+ndr_print_int16: void (struct ndr_print *, const char *, int16_t)
+ndr_print_int32: void (struct ndr_print *, const char *, int32_t)
+ndr_print_int3264: void (struct ndr_print *, const char *, int32_t)
+ndr_print_int8: void (struct ndr_print *, const char *, int8_t)
+ndr_print_ipv4address: void (struct ndr_print *, const char *, const char *)
+ndr_print_ipv6address: void (struct ndr_print *, const char *, const char *)
+ndr_print_ndr_syntax_id: void (struct ndr_print *, const char *, const struct ndr_syntax_id *)
+ndr_print_netr_SamDatabaseID: void (struct ndr_print *, const char *, enum netr_SamDatabaseID)
+ndr_print_netr_SchannelType: void (struct ndr_print *, const char *, enum netr_SchannelType)
+ndr_print_null: void (struct ndr_print *)
+ndr_print_pointer: void (struct ndr_print *, const char *, void *)
+ndr_print_policy_handle: void (struct ndr_print *, const char *, const struct policy_handle *)
+ndr_print_printf_helper: void (struct ndr_print *, const char *, ...)
+ndr_print_ptr: void (struct ndr_print *, const char *, const void *)
+ndr_print_set_switch_value: enum ndr_err_code (struct ndr_print *, const void *, uint32_t)
+ndr_print_sockaddr_storage: void (struct ndr_print *, const char *, const struct sockaddr_storage *)
+ndr_print_string: void (struct ndr_print *, const char *, const char *)
+ndr_print_string_array: void (struct ndr_print *, const char *, const char **)
+ndr_print_string_helper: void (struct ndr_print *, const char *, ...)
+ndr_print_struct: void (struct ndr_print *, const char *, const char *)
+ndr_print_struct_string: char *(TALLOC_CTX *, ndr_print_fn_t, const char *, void *)
+ndr_print_svcctl_ServerType: void (struct ndr_print *, const char *, uint32_t)
+ndr_print_time_t: void (struct ndr_print *, const char *, time_t)
+ndr_print_timespec: void (struct ndr_print *, const char *, const struct timespec *)
+ndr_print_timeval: void (struct ndr_print *, const char *, const struct timeval *)
+ndr_print_udlong: void (struct ndr_print *, const char *, uint64_t)
+ndr_print_udlongr: void (struct ndr_print *, const char *, uint64_t)
+ndr_print_uid_t: void (struct ndr_print *, const char *, uid_t)
+ndr_print_uint16: void (struct ndr_print *, const char *, uint16_t)
+ndr_print_uint32: void (struct ndr_print *, const char *, uint32_t)
+ndr_print_uint3264: void (struct ndr_print *, const char *, uint32_t)
+ndr_print_uint8: void (struct ndr_print *, const char *, uint8_t)
+ndr_print_union: void (struct ndr_print *, const char *, int, const char *)
+ndr_print_union_debug: void (ndr_print_fn_t, const char *, uint32_t, void *)
+ndr_print_union_string: char *(TALLOC_CTX *, ndr_print_fn_t, const char *, uint32_t, void *)
+ndr_print_winreg_Data: void (struct ndr_print *, const char *, const union winreg_Data *)
+ndr_print_winreg_Type: void (struct ndr_print *, const char *, enum winreg_Type)
+ndr_pull_DATA_BLOB: enum ndr_err_code (struct ndr_pull *, int, DATA_BLOB *)
+ndr_pull_GUID: enum ndr_err_code (struct ndr_pull *, int, struct GUID *)
+ndr_pull_HRESULT: enum ndr_err_code (struct ndr_pull *, int, HRESULT *)
+ndr_pull_KRB5_EDATA_NTSTATUS: enum ndr_err_code (struct ndr_pull *, int, struct KRB5_EDATA_NTSTATUS *)
+ndr_pull_NTSTATUS: enum ndr_err_code (struct ndr_pull *, int, NTSTATUS *)
+ndr_pull_NTTIME: enum ndr_err_code (struct ndr_pull *, int, NTTIME *)
+ndr_pull_NTTIME_1sec: enum ndr_err_code (struct ndr_pull *, int, NTTIME *)
+ndr_pull_NTTIME_hyper: enum ndr_err_code (struct ndr_pull *, int, NTTIME *)
+ndr_pull_WERROR: enum ndr_err_code (struct ndr_pull *, int, WERROR *)
+ndr_pull_advance: enum ndr_err_code (struct ndr_pull *, uint32_t)
+ndr_pull_align: enum ndr_err_code (struct ndr_pull *, size_t)
+ndr_pull_append: enum ndr_err_code (struct ndr_pull *, DATA_BLOB *)
+ndr_pull_array_length: enum ndr_err_code (struct ndr_pull *, const void *)
+ndr_pull_array_size: enum ndr_err_code (struct ndr_pull *, const void *)
+ndr_pull_array_uint8: enum ndr_err_code (struct ndr_pull *, int, uint8_t *, uint32_t)
+ndr_pull_bytes: enum ndr_err_code (struct ndr_pull *, uint8_t *, uint32_t)
+ndr_pull_charset: enum ndr_err_code (struct ndr_pull *, int, const char **, uint32_t, uint8_t, charset_t)
+ndr_pull_charset_to_null: enum ndr_err_code (struct ndr_pull *, int, const char **, uint32_t, uint8_t, charset_t)
+ndr_pull_dlong: enum ndr_err_code (struct ndr_pull *, int, int64_t *)
+ndr_pull_double: enum ndr_err_code (struct ndr_pull *, int, double *)
+ndr_pull_enum_uint16: enum ndr_err_code (struct ndr_pull *, int, uint16_t *)
+ndr_pull_enum_uint1632: enum ndr_err_code (struct ndr_pull *, int, uint16_t *)
+ndr_pull_enum_uint32: enum ndr_err_code (struct ndr_pull *, int, uint32_t *)
+ndr_pull_enum_uint8: enum ndr_err_code (struct ndr_pull *, int, uint8_t *)
+ndr_pull_error: enum ndr_err_code (struct ndr_pull *, enum ndr_err_code, const char *, ...)
+ndr_pull_generic_ptr: enum ndr_err_code (struct ndr_pull *, uint32_t *)
+ndr_pull_get_relative_base_offset: uint32_t (struct ndr_pull *)
+ndr_pull_get_switch_value: uint32_t (struct ndr_pull *, const void *)
+ndr_pull_gid_t: enum ndr_err_code (struct ndr_pull *, int, gid_t *)
+ndr_pull_hyper: enum ndr_err_code (struct ndr_pull *, int, uint64_t *)
+ndr_pull_init_blob: struct ndr_pull *(const DATA_BLOB *, TALLOC_CTX *)
+ndr_pull_int16: enum ndr_err_code (struct ndr_pull *, int, int16_t *)
+ndr_pull_int32: enum ndr_err_code (struct ndr_pull *, int, int32_t *)
+ndr_pull_int8: enum ndr_err_code (struct ndr_pull *, int, int8_t *)
+ndr_pull_ipv4address: enum ndr_err_code (struct ndr_pull *, int, const char **)
+ndr_pull_ipv6address: enum ndr_err_code (struct ndr_pull *, int, const char **)
+ndr_pull_ndr_syntax_id: enum ndr_err_code (struct ndr_pull *, int, struct ndr_syntax_id *)
+ndr_pull_netr_SamDatabaseID: enum ndr_err_code (struct ndr_pull *, int, enum netr_SamDatabaseID *)
+ndr_pull_netr_SchannelType: enum ndr_err_code (struct ndr_pull *, int, enum netr_SchannelType *)
+ndr_pull_pointer: enum ndr_err_code (struct ndr_pull *, int, void **)
+ndr_pull_policy_handle: enum ndr_err_code (struct ndr_pull *, int, struct policy_handle *)
+ndr_pull_pop: enum ndr_err_code (struct ndr_pull *)
+ndr_pull_ref_ptr: enum ndr_err_code (struct ndr_pull *, uint32_t *)
+ndr_pull_relative_ptr1: enum ndr_err_code (struct ndr_pull *, const void *, uint32_t)
+ndr_pull_relative_ptr2: enum ndr_err_code (struct ndr_pull *, const void *)
+ndr_pull_relative_ptr_short: enum ndr_err_code (struct ndr_pull *, uint16_t *)
+ndr_pull_restore_relative_base_offset: void (struct ndr_pull *, uint32_t)
+ndr_pull_set_switch_value: enum ndr_err_code (struct ndr_pull *, const void *, uint32_t)
+ndr_pull_setup_relative_base_offset1: enum ndr_err_code (struct ndr_pull *, const void *, uint32_t)
+ndr_pull_setup_relative_base_offset2: enum ndr_err_code (struct ndr_pull *, const void *)
+ndr_pull_steal_switch_value: uint32_t (struct ndr_pull *, const void *)
+ndr_pull_string: enum ndr_err_code (struct ndr_pull *, int, const char **)
+ndr_pull_string_array: enum ndr_err_code (struct ndr_pull *, int, const char ***)
+ndr_pull_struct_blob: enum ndr_err_code (const DATA_BLOB *, TALLOC_CTX *, void *, ndr_pull_flags_fn_t)
+ndr_pull_struct_blob_all: enum ndr_err_code (const DATA_BLOB *, TALLOC_CTX *, void *, ndr_pull_flags_fn_t)
+ndr_pull_struct_blob_all_noalloc: enum ndr_err_code (const DATA_BLOB *, void *, ndr_pull_flags_fn_t)
+ndr_pull_subcontext_end: enum ndr_err_code (struct ndr_pull *, struct ndr_pull *, size_t, ssize_t)
+ndr_pull_subcontext_start: enum ndr_err_code (struct ndr_pull *, struct ndr_pull **, size_t, ssize_t)
+ndr_pull_svcctl_ServerType: enum ndr_err_code (struct ndr_pull *, int, uint32_t *)
+ndr_pull_time_t: enum ndr_err_code (struct ndr_pull *, int, time_t *)
+ndr_pull_timespec: enum ndr_err_code (struct ndr_pull *, int, struct timespec *)
+ndr_pull_timeval: enum ndr_err_code (struct ndr_pull *, int, struct timeval *)
+ndr_pull_trailer_align: enum ndr_err_code (struct ndr_pull *, size_t)
+ndr_pull_udlong: enum ndr_err_code (struct ndr_pull *, int, uint64_t *)
+ndr_pull_udlongr: enum ndr_err_code (struct ndr_pull *, int, uint64_t *)
+ndr_pull_uid_t: enum ndr_err_code (struct ndr_pull *, int, uid_t *)
+ndr_pull_uint16: enum ndr_err_code (struct ndr_pull *, int, uint16_t *)
+ndr_pull_uint1632: enum ndr_err_code (struct ndr_pull *, int, uint16_t *)
+ndr_pull_uint32: enum ndr_err_code (struct ndr_pull *, int, uint32_t *)
+ndr_pull_uint3264: enum ndr_err_code (struct ndr_pull *, int, uint32_t *)
+ndr_pull_uint8: enum ndr_err_code (struct ndr_pull *, int, uint8_t *)
+ndr_pull_union_align: enum ndr_err_code (struct ndr_pull *, size_t)
+ndr_pull_union_blob: enum ndr_err_code (const DATA_BLOB *, TALLOC_CTX *, void *, uint32_t, ndr_pull_flags_fn_t)
+ndr_pull_union_blob_all: enum ndr_err_code (const DATA_BLOB *, TALLOC_CTX *, void *, uint32_t, ndr_pull_flags_fn_t)
+ndr_pull_winreg_Data: enum ndr_err_code (struct ndr_pull *, int, union winreg_Data *)
+ndr_pull_winreg_Type: enum ndr_err_code (struct ndr_pull *, int, enum winreg_Type *)
+ndr_push_DATA_BLOB: enum ndr_err_code (struct ndr_push *, int, DATA_BLOB)
+ndr_push_GUID: enum ndr_err_code (struct ndr_push *, int, const struct GUID *)
+ndr_push_HRESULT: enum ndr_err_code (struct ndr_push *, int, HRESULT)
+ndr_push_KRB5_EDATA_NTSTATUS: enum ndr_err_code (struct ndr_push *, int, const struct KRB5_EDATA_NTSTATUS *)
+ndr_push_NTSTATUS: enum ndr_err_code (struct ndr_push *, int, NTSTATUS)
+ndr_push_NTTIME: enum ndr_err_code (struct ndr_push *, int, NTTIME)
+ndr_push_NTTIME_1sec: enum ndr_err_code (struct ndr_push *, int, NTTIME)
+ndr_push_NTTIME_hyper: enum ndr_err_code (struct ndr_push *, int, NTTIME)
+ndr_push_WERROR: enum ndr_err_code (struct ndr_push *, int, WERROR)
+ndr_push_align: enum ndr_err_code (struct ndr_push *, size_t)
+ndr_push_array_uint8: enum ndr_err_code (struct ndr_push *, int, const uint8_t *, uint32_t)
+ndr_push_blob: DATA_BLOB (struct ndr_push *)
+ndr_push_bytes: enum ndr_err_code (struct ndr_push *, const uint8_t *, uint32_t)
+ndr_push_charset: enum ndr_err_code (struct ndr_push *, int, const char *, uint32_t, uint8_t, charset_t)
+ndr_push_charset_to_null: enum ndr_err_code (struct ndr_push *, int, const char *, uint32_t, uint8_t, charset_t)
+ndr_push_dlong: enum ndr_err_code (struct ndr_push *, int, int64_t)
+ndr_push_double: enum ndr_err_code (struct ndr_push *, int, double)
+ndr_push_enum_uint16: enum ndr_err_code (struct ndr_push *, int, uint16_t)
+ndr_push_enum_uint1632: enum ndr_err_code (struct ndr_push *, int, uint16_t)
+ndr_push_enum_uint32: enum ndr_err_code (struct ndr_push *, int, uint32_t)
+ndr_push_enum_uint8: enum ndr_err_code (struct ndr_push *, int, uint8_t)
+ndr_push_error: enum ndr_err_code (struct ndr_push *, enum ndr_err_code, const char *, ...)
+ndr_push_expand: enum ndr_err_code (struct ndr_push *, uint32_t)
+ndr_push_full_ptr: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_get_relative_base_offset: uint32_t (struct ndr_push *)
+ndr_push_get_switch_value: uint32_t (struct ndr_push *, const void *)
+ndr_push_gid_t: enum ndr_err_code (struct ndr_push *, int, gid_t)
+ndr_push_hyper: enum ndr_err_code (struct ndr_push *, int, uint64_t)
+ndr_push_init_ctx: struct ndr_push *(TALLOC_CTX *)
+ndr_push_int16: enum ndr_err_code (struct ndr_push *, int, int16_t)
+ndr_push_int32: enum ndr_err_code (struct ndr_push *, int, int32_t)
+ndr_push_int8: enum ndr_err_code (struct ndr_push *, int, int8_t)
+ndr_push_ipv4address: enum ndr_err_code (struct ndr_push *, int, const char *)
+ndr_push_ipv6address: enum ndr_err_code (struct ndr_push *, int, const char *)
+ndr_push_ndr_syntax_id: enum ndr_err_code (struct ndr_push *, int, const struct ndr_syntax_id *)
+ndr_push_netr_SamDatabaseID: enum ndr_err_code (struct ndr_push *, int, enum netr_SamDatabaseID)
+ndr_push_netr_SchannelType: enum ndr_err_code (struct ndr_push *, int, enum netr_SchannelType)
+ndr_push_pipe_chunk_trailer: enum ndr_err_code (struct ndr_push *, int, uint32_t)
+ndr_push_pointer: enum ndr_err_code (struct ndr_push *, int, void *)
+ndr_push_policy_handle: enum ndr_err_code (struct ndr_push *, int, const struct policy_handle *)
+ndr_push_ref_ptr: enum ndr_err_code (struct ndr_push *)
+ndr_push_relative_ptr1: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_relative_ptr2_end: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_relative_ptr2_start: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_restore_relative_base_offset: void (struct ndr_push *, uint32_t)
+ndr_push_set_switch_value: enum ndr_err_code (struct ndr_push *, const void *, uint32_t)
+ndr_push_setup_relative_base_offset1: enum ndr_err_code (struct ndr_push *, const void *, uint32_t)
+ndr_push_setup_relative_base_offset2: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_short_relative_ptr1: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_short_relative_ptr2: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_string: enum ndr_err_code (struct ndr_push *, int, const char *)
+ndr_push_string_array: enum ndr_err_code (struct ndr_push *, int, const char **)
+ndr_push_struct_blob: enum ndr_err_code (DATA_BLOB *, TALLOC_CTX *, const void *, ndr_push_flags_fn_t)
+ndr_push_struct_into_fixed_blob: enum ndr_err_code (DATA_BLOB *, const void *, ndr_push_flags_fn_t)
+ndr_push_subcontext_end: enum ndr_err_code (struct ndr_push *, struct ndr_push *, size_t, ssize_t)
+ndr_push_subcontext_start: enum ndr_err_code (struct ndr_push *, struct ndr_push **, size_t, ssize_t)
+ndr_push_svcctl_ServerType: enum ndr_err_code (struct ndr_push *, int, uint32_t)
+ndr_push_time_t: enum ndr_err_code (struct ndr_push *, int, time_t)
+ndr_push_timespec: enum ndr_err_code (struct ndr_push *, int, const struct timespec *)
+ndr_push_timeval: enum ndr_err_code (struct ndr_push *, int, const struct timeval *)
+ndr_push_trailer_align: enum ndr_err_code (struct ndr_push *, size_t)
+ndr_push_udlong: enum ndr_err_code (struct ndr_push *, int, uint64_t)
+ndr_push_udlongr: enum ndr_err_code (struct ndr_push *, int, uint64_t)
+ndr_push_uid_t: enum ndr_err_code (struct ndr_push *, int, uid_t)
+ndr_push_uint16: enum ndr_err_code (struct ndr_push *, int, uint16_t)
+ndr_push_uint1632: enum ndr_err_code (struct ndr_push *, int, uint16_t)
+ndr_push_uint32: enum ndr_err_code (struct ndr_push *, int, uint32_t)
+ndr_push_uint3264: enum ndr_err_code (struct ndr_push *, int, uint32_t)
+ndr_push_uint8: enum ndr_err_code (struct ndr_push *, int, uint8_t)
+ndr_push_union_align: enum ndr_err_code (struct ndr_push *, size_t)
+ndr_push_union_blob: enum ndr_err_code (DATA_BLOB *, TALLOC_CTX *, void *, uint32_t, ndr_push_flags_fn_t)
+ndr_push_unique_ptr: enum ndr_err_code (struct ndr_push *, const void *)
+ndr_push_winreg_Data: enum ndr_err_code (struct ndr_push *, int, const union winreg_Data *)
+ndr_push_winreg_Type: enum ndr_err_code (struct ndr_push *, int, enum winreg_Type)
+ndr_push_zero: enum ndr_err_code (struct ndr_push *, uint32_t)
+ndr_set_flags: void (uint32_t *, uint32_t)
+ndr_size_DATA_BLOB: uint32_t (int, const DATA_BLOB *, int)
+ndr_size_GUID: size_t (const struct GUID *, int)
+ndr_size_string: uint32_t (int, const char * const *, int)
+ndr_size_string_array: size_t (const char **, uint32_t, int)
+ndr_size_struct: size_t (const void *, int, ndr_push_flags_fn_t)
+ndr_size_union: size_t (const void *, int, uint32_t, ndr_push_flags_fn_t)
+ndr_string_array_size: size_t (struct ndr_push *, const char *)
+ndr_string_length: uint32_t (const void *, uint32_t)
+ndr_syntax_id_equal: bool (const struct ndr_syntax_id *, const struct ndr_syntax_id *)
+ndr_syntax_id_from_string: bool (const char *, struct ndr_syntax_id *)
+ndr_syntax_id_null: uuid = {time_low = 0, time_mid = 0, time_hi_and_version = 0, clock_seq = "\000", node = "\000\000\000\000\000"}, if_version = 0
+ndr_syntax_id_to_string: char *(TALLOC_CTX *, const struct ndr_syntax_id *)
+ndr_token_peek: uint32_t (struct ndr_token_list *, const void *)
+ndr_token_retrieve: enum ndr_err_code (struct ndr_token_list *, const void *, uint32_t *)
+ndr_token_retrieve_cmp_fn: enum ndr_err_code (struct ndr_token_list *, const void *, uint32_t *, comparison_fn_t, bool)
+ndr_token_store: enum ndr_err_code (TALLOC_CTX *, struct ndr_token_list *, const void *, uint32_t)
+ndr_transfer_syntax_ndr: uuid = {time_low = 2324192516, time_mid = 7403, time_hi_and_version = 4553, clock_seq = "\237\350", node = "\b\000+\020H`"}, if_version = 2
+ndr_transfer_syntax_ndr64: uuid = {time_low = 1903232307, time_mid = 48826, time_hi_and_version = 18743, clock_seq = "\203\031", node = "\265\333\357\234\314\066"}, if_version = 1

diff --git a/librpc/ndr/libndr.h b/librpc/ndr/libndr.h
index b349c82fb79176e8bb12184b981d8847c007da96..d6e2e378bd2cf3752c8ea62bb3523526b06b7eda 100644 (file)
--- 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 e5ddba8a741ecee0ac7492cb6f26f04e2547d763..1c49c9a0ec4ca555791de08b7c9079c170c39d38 100644 (file)
--- 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;
 }
 

diff --git a/librpc/wscript_build b/librpc/wscript_build
index fdfe64139002aefe7d38df2eebf5787a769b13b8..55a6f7ab68445cbf8e7ca4a63ee661b42ca39bef 100644 (file)
--- a/librpc/wscript_build
+++ b/librpc/wscript_build
@@ -715,7 +715,7 @@ bld.SAMBA_LIBRARY('ndr',
     public_deps='samba-errors talloc samba-util',
     public_headers='gen_ndr/misc.h gen_ndr/ndr_misc.h ndr/libndr.h:ndr.h',
     header_path= [('*gen_ndr*', 'gen_ndr')],
-    vnum='0.0.9',
+    vnum='0.1.0',
     abi_directory='ABI',
     abi_match='ndr_* GUID_*',
     )