BerConverter does not use AsnWriter, AsnDecoder APIs

[edwardneal]

At the moment, the System.DirectoryServices.Protocols.BerConverter class calls the underlying LDAP library's ber_printf and ber_scanf functions. With the more recent System.Formats.Asn1 library, this is no longer needed; we can call the various AsnWriter and AsnDecoder functions instead.

The AsnDecoder functions outperform BerConverter by a fair margin, although I don't think it's called enough times to make a measurable difference. The main value lies in being able to remove all of the BerPal class except for FreeBerElement (which is called by LdapConnection.) It'll mean taking a dependency on System.Formats.Asn1, which seems reasonable for an LDAP library.

Performance benchmarks - 3-6x execution time improvement, 3.4-5x memory allocation reduction

These performance benchmarks are for a sequence of 10,000 integers. The AsnWriter uses an appropriately-sized initial buffer, which can be estimated from the format string; without this buffer, the memory allocation of AsnWriterEncode explodes by a factor of 9, to triple that of BerConverterEncode.

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22621.3007/22H2/2022Update/SunValley2)
Intel Core i7-8565U CPU 1.80GHz (Whiskey Lake), 1 CPU, 8 logical and 4 physical cores
.NET SDK 8.0.101
[Host] : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2 [AttachedDebugger]
DefaultJob : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2

Method	Mean	Error	StdDev	Ratio	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
BerConverterDecode	1,727.3 us	21.59 us	20.20 us	1.00	138.6719	68.3594	41.0156	842.52 KB	1.00
AsnDecoderDecode	279.2 us	4.33 us	3.84 us	0.16	40.5273	6.3477	-	167.41 KB	0.20
BerConverterEncode	547.2 us	5.49 us	5.14 us	1.00	66.4063	-	-	273.55 KB	1.00
AsnWriterEncode	187.2 us	3.68 us	3.94 us	0.34	19.0430	1.2207	-	78.21 KB	0.29

This will change the BER output on Windows, but Windows is already a slight anomaly. At present, Windows' ber_printf encodes a { (an ASN.1 SEQUENCE) with a four-byte length; OpenLDAP and AsnWriter will only use the number of bytes actually required to encode the sequence length. An example of the changed output for a very simple sequence of one integer (0x10) is:

Platform	SequenceTag	LengthHeader	Length1	Length2	Length3	Length4	IntegerTag	IntegerLength	IntegerValue
Windows	0x30	0x84	0x00	0x00	0x00	0x03	0x02	0x01	0x10
AsnWriter	0x30	-	-	-	-	0x03	0x02	0x01	0x10

There's also a difference in the ASN.1 BIT STRING. BerConverter doesn't appear to include the unused bit count, while AsnWriter and OpenLDAP do. An example of the changed output for this for the BIT STRING needed for a value of 4 (and two unused bits) is:

Library	BitStringTag	LengthBitString	UnusedBits	BitStringValue
BerConverter	0x03	0x01	-	0x04
AsnWriter	0x03	0x02	0x02	0x04

Both of these are already noted to a certain degree in BerConverterTests, and switching to AsnWriter and AsnDecoder would make the output consistent across platforms.

Although it's a public API, it's worth nothing that this is only called within the library when building the list of DirectoryControls. There might also be a performance improvement if we change the callers to use AsnDecoder directly, to avoid the overhead of processing a format string which will always be static.

Tagging subscribers to this area: @dotnet/area-system-directoryservices, @jay98014
See info in area-owners.md if you want to be subscribed.

Issue Details

---

At the moment, the System.DirectoryServices.Protocols.BerConverter class calls the underlying LDAP library's ber_printf and ber_scanf functions. With the more recent System.Formats.Asn1 library, this is no longer needed; we can call the various AsnWriter and AsnDecoder functions instead.

The AsnDecoder functions outperform BerConverter by a fair margin, although I don't think it's called enough times to make a measurable difference. The main value lies in being able to remove all of the BerPal class except for FreeBerElement (which is called by LdapConnection.) It'll mean taking a dependency on System.Formats.Asn1, which seems reasonable for an LDAP library.

Performance benchmarks - 3-6x execution time improvement, 3.4-5x memory allocation reduction

These performance benchmarks are for a sequence of 10,000 integers. The AsnWriter uses an appropriately-sized initial buffer, which can be estimated from the format string; without this buffer, the memory allocation of AsnWriterEncode explodes by a factor of 9, to triple that of BerConverterEncode.

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22621.3007/22H2/2022Update/SunValley2)
Intel Core i7-8565U CPU 1.80GHz (Whiskey Lake), 1 CPU, 8 logical and 4 physical cores
.NET SDK 8.0.101
[Host] : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2 [AttachedDebugger]
DefaultJob : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2

Method	Mean	Error	StdDev	Ratio	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
BerConverterDecode	1,727.3 us	21.59 us	20.20 us	1.00	138.6719	68.3594	41.0156	842.52 KB	1.00
AsnDecoderDecode	279.2 us	4.33 us	3.84 us	0.16	40.5273	6.3477	-	167.41 KB	0.20
BerConverterEncode	547.2 us	5.49 us	5.14 us	1.00	66.4063	-	-	273.55 KB	1.00
AsnWriterEncode	187.2 us	3.68 us	3.94 us	0.34	19.0430	1.2207	-	78.21 KB	0.29

This will change the BER output on Windows, but Windows is already a slight anomaly. At present, Windows' ber_printf encodes a { (an ASN.1 SEQUENCE) with a four-byte length; OpenLDAP and AsnWriter will only use the number of bytes actually required to encode the sequence length. An example of the changed output for a very simple sequence of one integer (0x10) is:

Platform	SequenceTag	LengthHeader	Length1	Length2	Length3	Length4	IntegerTag	IntegerLength	IntegerValue
Windows	0x30	0x84	0x00	0x00	0x00	0x03	0x02	0x01	0x10
AsnWriter	0x30	-	-	-	-	0x03	0x02	0x01	0x10

There's also a difference in the ASN.1 BIT STRING. BerConverter doesn't appear to include the unused bit count, while AsnWriter and OpenLDAP do. An example of the changed output for this for the BIT STRING needed for a value of 4 (and two unused bits) is:

Library	BitStringTag	LengthBitString	UnusedBits	BitStringValue
BerConverter	0x03	0x01	-	0x04
AsnWriter	0x03	0x02	0x02	0x04

Both of these are already noted to a certain degree in BerConverterTests, and switching to AsnWriter and AsnDecoder would make the output consistent across platforms.

Although it's a public API, it's worth nothing that this is only called within the library when building the list of DirectoryControls. There might also be a performance improvement if we change the callers to use AsnDecoder directly, to avoid the overhead of processing a format string which will always be static.

Author:	edwardneal
Assignees:	-
Labels:	area-System.DirectoryServices, untriaged
Milestone:	-

[steveharter]

PTAL @BRDPM @grubioe @Jay9801

[edwardneal]

I've been looking at BerConverter more closely, and I'd like to take it a little further. Switching to the use of AsnWriter isn't a problem, but switching from the use of ber_scanf to AsnDecoder is implicitly a breaking change.

ber_scanf's documentation states that the inbound byte array is interpreted according to the format string - but in doing so, it ignores the ASN.1 tags, to a degree that their contents can be interpreted corruptly. This can cut both ways: a valid ASN.1-formatted byte array can generate invalid results, and an invalid buffer can generate valid results.

Case 1: Valid byte array, invalid results

I've lifted this example byte array from BerConverterTests. It's a valid, unambiguous ASN.1 data structure - a sequence of two Boolean values (true, followed by false). However, if this byte array is passed to ber_scanf with a format string of {v} then it will be interpreted as a sequence which contains an inner sequence of null-terminated OCTET STRINGs.

Index	Value	ASN.1 meaning	{v} meaning
0	48	Type (SEQUENCE)	Type (SEQUENCE)
1	132	Length 1	Length 1
2	0	Length 2	Length 2
3	0	Length 3	Length 3
4	0	Length 4	Length 4
5	6	Length 5 (6 bytes)	Length 5 (6 bytes)
6	1	Type (Boolean)	Sequence type (ignored)
7	1	Length (1 byte)	Sequence length (ignored)
8	255	Value (true)	Octet string type (ignored)
9	1	Type (Boolean)	Length (1 byte)
10	1	Length (1 byte)	Value (1)
11	0	Value (false)	Trailing byte (ignored)

The final output of ber_scanf with a format string of {v} is thus [ [ "\x01" ] ]. If BerConverter.Decode is switched to using AsnDecoder, it'll simply throw an exception or return false.

Case 2: Invalid byte array, valid results

This is simply an adapted version of the previous byte array. It's an invalid ASN.1 structure which will be parsed as if it was correct.

Index	Value	ASN.1 meaning	{v} meaning
0	48	Type (SEQUENCE)	Type (SEQUENCE)
1	132	Length 1	Length 1
2	0	Length 2	Length 2
3	0	Length 3	Length 3
4	0	Length 4	Length 4
5	6	Length 5 (6 bytes)	Length 5 (6 bytes)
6	1	Type (Boolean)	Sequence type (ignored)
7	1	Length (1 byte)	Sequence length (ignored)
8	48	Value (true)	Octet string type (ignored)
9	2	Type (Integer)	Length (2 bytes)
10	30	Length (Invalid - 30 bytes)	Value ("\x1e")
11	5	Value (5)	Value ("\x05")

Impact

The impact of using AsnWriter to power BerConverter.Encode is pretty clear, but using AsnDecoder for BerConverter.Decode will mean that the format string needs to match the actual ASN.1 data types directly. This'll cause Decode to throw an exception in some situations. I think that's the right thing to do though: at the moment, it's easy for Decode to interpret data in undefined ways.

I was also hoping to avoid API changes, but if Decode is to be made stricter then the exception behaviour of Decode and Encode should change to make sure that we're providing useful information when we throw BerConversionException. At present, it doesn't indicate what failed, or where the failure occurred. I'd also like to add TryEncode and TryDecode methods and Span-ify BerConverter in the same API review just as a matter of course.

Separately to this, there are a few test cases missing in BerConverterTests to verify that the v and V format strings work. I'll add these shortly. I'll also change the various classes in System.DirectoryServices.Protocols which currently use BerConverter.Decode and Encode over to the newer AsnWriter and AsnDecoder, to make our LDAP request formats consistent across client platforms and to validate the responses we receive from servers a little more tightly.

Proposed API changes

public static class BerConverter
{
    public static byte[] Encode(string format, params object[] value);
+   public static byte[] Encode(ReadOnlySpan<char> format, params object[] value);
+   public static bool TryEncode(string format,
+       Span<byte> destination, out int bytesWritten, params object[] value);
+   public static bool TryEncode(ReadOnlySpan<char> format,
+       Span<byte> destination, out int bytesWritten, params object[] value);

    public static object[] Decode(string format, byte[] value);
+   public static object[] Decode(ReadOnlySpan<char> format, byte[] value);
+   public static bool TryDecode(string format, byte[] value, out object[] destination);
+   public static bool TryDecode(ReadOnlySpan<char> format, byte[] value, out object[] destination);
}

public class BerConversionException
{
+   // Position in the format string where the exception was generated.
+   public int FormatIndex { get; }

+   // When encoding, the type of parameter which was expected. Null when dealing with structures
+   // which don't require a parameter (such as sequences.) Null when decoding.
+   public Type? ExpectedParameterType { get; }

+   // When encoding, the parameter being encoded when the exception was generated. Null when
+   // dealing with structures which don't require a parameter.
+   // When decoding, the decoded parameter value (if this is known when the exception was generated.)
+   public object? ParameterValue { get; }

+   public BerConversionException(int formatIndex, Type? expectedParameterType);
+   public BerConversionException(int formatIndex, Type? expectedParameterType, string message);
+   public BerConversionException(int formatIndex, Type? expectedParameterType,
+       object? parameterValue);
+   public BerConversionException(int formatIndex, Type? expectedParameterType,
+       object? parameterValue, string message);
}

What's the right way for me to receive initial feedback on the proposal and to get it ready for the API review process?

[buyaa-n]

Tag experts in the AsnWriter, AsnDecoder encoding area @bartonjs @GrabYourPitchforks for feedback

[bartonjs]

Adding new API and changing the underlying implementation are really two different things; so they should be in two separate issues. The new exception data might depend on the implementation changing, so they might be interdependent in that sense... but otherwise they feel orthogonal.

For the API part:

• We generally haven't added ROS-char overloads to things that take string format, since that's almost always given as a string literal, so there's not a reason to want to accept a slice/substring. (It also has underlying implementation concerns, since a string is null-terminated during a P/Invoke, and a ReadOnlySpan<char> isn't necessarily null-terminated.)
• The Span-writing TryEncode seems fine.
• I don't understand what the failure mode is of TryDecode. Note that "Try" doesn't mean "doesn't throw an exception", it means "doesn't throw an exception in one understandable case". For super-low-level things like int.TryParse the one case is "this doesn't parse as an integer", which happens to basically mean "doesn't throw exceptions". For span-writing things it means "the output was too small". The best I see from this is "some piece of data was bad, but I can't tell you what it was"... but maybe I'm missing something.
• I'm not entirely certain what the utility in the new exception data is. The API shape for it is probably reasonable; but someone would need to be able to articulate during the API review where someone would actually use any of the new data in an actual program; vs just a theoretical "if we have the information we should share it".

For the implementation change:

• AsnWriter always uses the CER/DER minimal byte encoding for the length. But that's legal BER, so shouldn't bother anyone.
• AsnWriter.WriteBitString expects just the content bytes (aside from the overload with the unused bit count). Not sure what BerConverter's API is doing; other than expecting the caller to have already made bytes[0] be the unused bit count. But whatever the existing API is doing, it would need to stay doing.
• I don't know anything about the BerConverter.Decode APIs; so it's hard for me to comment on the impact there... other than "breaking changes are best avoided". Especially since I didn't quite internalize it due to being in a bit of a hurry at the moment.

[edwardneal]

Thanks for the review. The additional API request was largely a result of the Decode API changes. The Encode API changes are pretty simple (although I'm a bit curious why Windows is always returning the long-form length attribute - was this for backwards compatibility with something, and if so then is it still around?)

In a nutshell: the existing BerConverter.Decode API calls ber_scanf by passing in a format string. ber_scanf then reads the next bytes from the input buffer as though they're in the format defined by the next element in the format string. It doesn't validate that the type of the ASN element which is in the next bytes of the input buffer matches the type expected by the format string though - it just skips the type byte and processes the raw data. That can work sometimes, but there are some situations (such as {v}) where the element described by the current character in format string has a different length to the ASN element at the current position in the input buffer. This means that ber_scanf could advance the current position of the input buffer incorrectly and misinterpret all of the BER elements which follow. This would potentially mean that it could read data lengths from incorrect positions in the input buffer and perform a buffer overread, although in practice testing confirms that both OpenLDAP and Windows are protected against that.

AsnReader is better-behaved - when we try to read (e.g.) an integer, it'll actually validate the datatype of the ASN element in its input buffer, and throw if it doesn't match. Throwing an exception in this circumstance is a breaking change, but given that the input buffer comes directly from the remote server, I think throwing is preferrable - trying to blindly interpret the data in the same way that ber_scanf does feels like a short-cut to undefined behaviour, even if bounds checking protects against the buffer overreads I mentioned earlier.

This then led to the extra fields in BerConversionException: if we're going to throw this exception when the input buffer doesn't match the format string, it made sense to indicate which part of the format string had the error. I then expanded the same principle to the Encode logic, which currently just performs Debug.WriteLine if there's a type mismatch while encoding.

Your points around the rest of the API surface for BerConverter make a lot of sense. My thought process for using ReadOnlySpans for the format strings was that using this would make string constant inlining work, and that the very short format strings used in user code might interact with the JIT's PGO and loop unrolling to turn into (essentially) a JIT-generated BER deserializer. If that's not the case, then the ROSes can go - they're not going to do any good.

There's some value in being able to decode directly from the input buffer as a span and avoid copying a byte array around. I'll discard the TryDecode and ReadOnlySpans, and will see about adding a Decode overload which accepts that span. This might be a few days though.