| Date: | August 26, 2004 / year-entry #319 |
| Tags: | code |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20040826-00/?p=38043 |
| Comments: | 41 |
| Summary: | Some Windows structures are variable-sized, beginning with a fixed header, followed by a variable-sized array. When these structures are declared, they often declare an array of size 1 where the variable-sized array should be. For example: typedef struct _TOKEN_GROUPS { DWORD GroupCount; SID_AND_ATTRIBUTES Groups[ANYSIZE_ARRAY]; } TOKEN_GROUPS, *PTOKEN_GROUPS; If you look in the header files, you'll... |
Some Windows structures are variable-sized, beginning with a fixed header, followed by a variable-sized array. When these structures are declared, they often declare an array of size 1 where the variable-sized array should be. For example:
typedef struct _TOKEN_GROUPS {
DWORD GroupCount;
SID_AND_ATTRIBUTES Groups[ANYSIZE_ARRAY];
} TOKEN_GROUPS, *PTOKEN_GROUPS;
If you look in the header files, you'll see that ANYSIZE_ARRAY is #define'd to 1, so this declares a structure with a trailing array of size one. With this declaration, you would allocate memory for one such variable-sized TOKEN_GROUPS structure like this: PTOKEN_GROUPS TokenGroups = malloc(FIELD_OFFSET(TOKEN_GROUPS, Groups[NumberOfGroups])); and you would initialize the structure like this:
TokenGroups->GroupCount = NumberOfGroups;
for (DWORD Index = 0; Index = NumberOfGroups; Index++) {
TokenGroups->Groups[Index] = ...;
}
Many people think it should have been declared like this:
typedef struct _TOKEN_GROUPS {
DWORD GroupCount;
} TOKEN_GROUPS, *PTOKEN_GROUPS;
(In this article, code that is wrong or hypothetical will be italicized.) The code that does the allocation would then go like this:
PTOKEN_GROUPS TokenGroups =
malloc(sizeof(TOKEN_GROUPS) +
NumberOfGroups * sizeof(SID_AND_ATTRIBUTES));
This alternative has two disadvantages, one cosmetic and one fatal. First, the cosmetic disadvantage: It makes it harder to access the variable-sized data. Initializing the TOKEN_GROUPS just allocated would go like this:
TokenGroups->GroupCount = NumberOfGroups;
for (DWORD Index = 0; Index = NumberOfGroups; Index++) {
((SID_AND_ATTRIBUTES *)(TokenGroups + 1))[Index] = ...;
}
The real disadvantage is fatal. The above code crashes on 64-bit Windows. The SID_AND_ATTRIBUTES structure looks like this:
typedef struct _SID_AND_ATTRIBUTES {
PSID Sid;
DWORD Attributes;
} SID_AND_ATTRIBUTES, * PSID_AND_ATTRIBUTES;
Observe that the first member of this structure is a pointer, PSID. The SID_AND_ATTRIBUTES structure requires pointer alignment, which on 64-bit Windows is 8-byte alignment. On the other hand, the proposed TOKEN_GROUPS structure consists of just a DWORD and therefore requires only 4-byte alignment. sizeof(TOKEN_GROUPS) is four. I hope you see where this is going. Under the proposed structure definition, the array of SID_AND_ATTRIBUTES structures will not be placed on an 8-byte boundary but only on a 4-byte boundary. The necessary padding between the GroupCount and the first SID_AND_ATTRIBUTES is missing. The attempt to access the elements of the array will crash with a STATUS_DATATYPE_MISALIGNMENT exception. Okay, you may say, then why not use a zero-length array instead of a 1-length array? Because time travel has yet to be perfected. Zero-length arrays did not become legal Standard C until 1999. Since Windows was around long before then, it could not take advantage of that functionality in the C language. |
Comments (41)
Comments are closed. |
How would you allocate one of these structures in C++? My understanding was that new/delete and malloc/free had to be done in matching pairs so ideally you would want to use new so you don’t need to remember to call free rather than delete. But you can’t allocate it using ‘new TOKEN_GROUPS’ as you will get an incorrectly sized structure. And you can’t allocate it using ‘new BYTE[sizeof(TOKEN_GROUPS) + sizeof(SID_AND_ATTRIBUTES)]’ as you may get a badly aligned structure.
What am I missing?
Sorry – I see my mistake (for some strange reason I thought malloc was doing something different as the structure contained a pointer but obviously that doesn’t make sense and alignment was coming from the fact that items were both in a structure).
Use ‘new BYTE[FIELD_OFFSET(TOKEN_GROUPS, Groups[NumberOfGroups])];’
I couldn’t find anything in The C++ Programming Language that said one way or another about alignment guarantees for operator new, so you have to work around it a bit.
#define MAKE_ALIGNED(align, val) (((val) & ((align)-1)) ? (((val) & ~((align)-1)) + (align)) : (val))
PTOKEN_GROUPS TokenGroups = (PTOKEN_GROUPS)new unsigned char[sizeof(TOKEN_GROUPS) + (NumberOfSidAndAttributes – 1) * sizeof(SID_AND_ATTRIBUTES) + __alignof(TOKEN_GROUPS)];
if((ULONG_PTR)TokenGroups & (__alignof(TOKEN_GROUPS) – 1))
TokenGroups = (PTOKEN_GROUPS)(MAKE_ALIGNED(__alignof(TOKEN_GROUPS), (ULONG_PTR)TokenGroups));
Actually though, on Win32, heap allocations are all at least 16-byte aligned (IIRC), so you should never "really" have to do this on VC for heap allocations. If you have a weird operator new that does return pointers that aren’t 16-byte aligned, though, then you may have cause to worry.
I already gave one example where you can get not-16-aligned data back.
http://weblogs.asp.net/oldnewthing/archive/2004/02/03/66660.aspx
In that case, you might be justified in being paranoid with VC’s operator new.
Perhaps the simplest solution would be to wrap operator new with a version that always returns an alignment suitable for the allocation request, up to say 16-byte alignment (like the Win32 heap manager seems to do).
But note that (at least under Visual C++ 6) the "new BYTE[cb]" variant will return 16-byte aligned memory, so the example above is safe.
Don’t rely on heap alignments. In case you think this can’t bite on 32-bit systems, see http://support.microsoft.com/default.aspx?kbid=317898. The WebClass runtime contained an alignment bug which caused peculiar non-reproducible inexplicable crashes – invariably when we were showing the website to management or the customer.
I managed to reproduce the error by turning on the page heap flag for dllhost.exe, which made it crash every time. Armed with this, we asked for the hotfix and got it (very promptly!)
I’m not sure the zero-length array is legal in C++ yet, so I wouldn’t try to use it. It might work as an MS extension in Visual C++ – I’m not sure what VC’s position on supporting the C99 standard is.
Some of these security structures have to be marshalled over RPC or LPC; it’s a lot easier if it’s a single block of data (not to mention cache coherency). I’ve recently been experimenting with LsaLogonUser which requires that the username, password and domain name directly follow the MSV1_0_INTERACTIVE_LOGON structure despite being pointed to from that structure – this isn’t documented!
Raymond, are you going to cover ‘Why are many structures in the Windows API size-prefixed?’
Raymond wrote: "Zero-length arrays did not become legal Standard C until 1999. Since Windows was around long before then, it could not take advantage of that functionality in the C language."
This is absolute nonsense. The Platform SDK has always required non-standard functionality – once it was "near" and "far"; now it’s things like "__declspec" and "__stdcall". So far as I can see, the Platform SDK is designed to work with the Microsoft C/C++ compiler and other compiler vendors need to replicate MS extensions. Correct me if I’m wrong.
Jonathan Payne wrote: "And you can’t allocate it using ‘new BYTE[sizeof(TOKEN_GROUPS) + sizeof(SID_AND_ATTRIBUTES)]’ as you may get a badly aligned structure."
Actually you can. The standard says (section 18.4.1.1, paragraph 1) that operator new returns a block of memory that’s suitably aligned for any object of the given size.
Mike Dimmick: Raymond already wrote something about this in http://weblogs.asp.net/oldnewthing/archive/2003/12/12/56061.aspx
RC: "malloc(FIELD_OFFSET(TOKEN_GROUPS, Groups[NumberOfGroups]))"
The first thing I thought was, doesn’t that point to Groups’ base? Then I noticed that it would actually return the address of the N+1th member, which is the overall size of the N-element struct… it works and it’s concise, but takes a bit of thinking. There’s a dedicated macro for this, RTL_SIZEOF_THROUGH_FIELD(), but it would require using NumberOfGroups – 1.
It’s probably just best to throw hands up as nonintuitive either way. ;p
BH: "Actually you can. The standard says (section 18.4.1.1, paragraph 1) that operator new returns a block of memory that’s suitably aligned for any object of the given size."
I’m going to assume that you’re referring to the second TOKEN_GROUPS which has only the DWORD in it. If this is wrong, disregard.
Indeed — new will return a suitably aligned memory block for a TOKEN_GROUPS (a DWORD) plus SID_AND_ATTRIBUTES. This entire article is devoted to the observation that the struct in question is larger than just those two members added together because of alignment padding.
SID_AND_ATTRIBUTES has a pointer in it. As such, in order to USE that pointer, the pointer member has to be aligned on a boundary. For that reason, allocing using FIELD_OFFSET() will guarantee this, by putting padding bytes between the DWORD in TOKEN_GROUPS and the start of the SID array. You don’t get that guarantee by just adding sizes together.
There’s another caveat with structures declared that way. One alternative might have been:
typedef struct _TOKEN_GROUPS {
DWORD GroupCount;
SID_AND_ATTRIBUTES *Groups;
} TOKEN_GROUPS, *PTOKEN_GROUPS;
This would still force Groups to be pointer-aligned, but it’s much less convenient when you think of argument marshalling.
In driver development, developers are sometimes faced with sending arguments from user-mode to kernel-mode via a METHOD_BUFFERED IOCTL. Structures with embedded pointers like this one represent anything from a security flaw waiting to happen to simply a PITA.
A common structure that is complained about along these lines is:
typedef struct _UNICODE_STRING {
USHORT Length;
USHORT MaximumLength;
PWSTR Buffer;
} UNICODE_STRING;
Even if you allocate your character buffer immediately after this structure:
UNICODE_STRING s = malloc(sizeof(UNICODE_STRING) + numChars * sizeof(WCHAR));
you still have to initialize it with a pointer:
s->Buffer = s + 1;
which, once embedded into your structure, will cause havoc when your structure is double-buffered into its kernel-mode argument buffer, where all of the addresses of things are numerically different values.
And, even after all of that, it still might crash for alignment reasons – UNICODE_STRING happens to end with a pointer, but imagine something that ended with a CHAR – if you did the above trick with a single allocation, your WSTR buffer would start on an odd boundary.
Oh, one other bit — if you’re using C++, the new operator knows the type you’re allocating FOR, so it can guarantee alignment.
I guess I should be more careful about checking the Standards before commenting; it turns out that under C99, at least, malloc() also guarantees a base address that uses universal alignment (read: the largest alignment-requirement of any intrinsic type), so malloc() should be safe in Ken’s case above.
_aligned_alloc() should be used when you want to align on a smaller alignment requirement, i.e. for when you’re hand-tuning.
Ken: yes and no. For all the standard types, this is the correct way to do it. If you use any types that have __declspec(align) like if you’re doing any SSE programming, you need to use _aligned_malloc instead.
On a side note, be careful when using __declspec(align) because all fundamental assumptions behind C go out the window when using __declspec(align):
struct foo {
__declspec(align(16)) char ch;
};
sizeof(foo) == 16 on MS, == 1 on Intel.
sizeof(foo[2]) == 32 on MS, == 2 on Intel.
struct foo2 {
__declspec(align(16)) char ch;
__declspec(align(16)) char ch2;
};
sizeof(foo2) == 17 on both
sizeof(foo2[2]) == 64 on both
It’s awesome to see rand() with constant seeds being used in sizeof() calculations.
While it’s true that the SDK has always required some nonstandard stuff, it tries to avoid *gratuitous* nonstandard stuff. Especially stuff that might conflict with a future version of the language (like zero-length arrays would have).
Thanks Raymond I think I understand the issue a little better now. We’ve hit bugs that I guess are related to this in Wine when generating code to be compiled for both MS_VC and Mingw-gcc. To quote Francois:
"Running the generated tests on Windows I found a couple of alignment
issues.
Apparently gcc thinks that 64bit integers only need to be aligned on 4
byte boundaries while MSVC aligns them on 8 byte boundaries. What I
don’t understand is that we have already told gcc to align ULONGLONG and
DWORDLONG types on 8 byte boundaries but this seems to have no effect on
structure fields, or the structures themselves.
So I had to add some packing and DECLSPEC_ALIGN directives to get the
right effect but I must admit this is still a bit mysterious to me…."
5.3.4/10 "For arrays of char and unsigned char, the difference between the result of the new-expression and the address returned by the allocation function shall be an integral multiple of the most stringent alignment requirement (3.9) of any object type whose size is no greater than the size of the array being created."
The complex wording it there to allow an implementation to stick padding for its own information or align it on a WORD boundary if you allocate BYTE[2]. So it’s safe as long as you can guarantee Microsoft will never change BYTE to be typedeffed to anything other than unsigned char (say they change it to unsigned __int8 where this is a different type than unsigned char on Intel’s compiler).
I personally would just use void *mem = ::operator new(size/*, std::nothrow*/) or just plain old malloc and be done with it.
8/26/2004 5:16 PM asdf
describes things that look like bugs in Intel’s compiler.
Technically the described behavior doesn’t render Intel’s compiler non-conforming, because __declspec is in the category of identifiers reserved to the implementation and the implementation can do whatever it pleases (e.g. compile Fortran and complain if your program isn’t Fortran).
Practically speaking, since it seems that Intel’s compiler understands Microsoft’s meaning of __declspec(align()), it does look like an Intel bug. A struct’s size has to be adjusted so that an array of those structs will have total size matching the number of elements times the struct’s size. Although examples are not normative, example 2 on page 80 explains it pretty well, and normative parts of the standard are not very far from there.
Is it always safe to create a standalone array of structures via malloc(N*sizeof(foo)), even if sizeof(foo) is not a factor of 8?
For example:
struct foo
{
int x;
};
foo* pFoo = (foo*)malloc(10*sizeof(foo));
foo* pFoo1 = &pFoo[1];
pFoo1->x = 4; // Is this safe?
It’s safe under x86 and x64 (AMD64/EM64T) because Windows or the processor will invisibly do an alignment fixup before the userspace app ever learns about what happened. (Yes, alignment is a concern on Win32 when performance is critical. Also, see the disclaimer below.) Fixups are not free, but not amazingly horribly expensive either.
It may not be safe under IA64. The fixup process is so expensive on Itanium that Windows disables it by default, and only enables it on a per-app basis. (The app has to request it explicitly using SetErrorMode().)
Think of every type as having a number associated with it, called the alignment-requirement. The CPU will raise an alignment fault if you attempt to access something whose offset is not a clean multiple of the alignment-requirement. For intrinsic data types like int, float, etc. the alignment requirement is usually the same as the data type’s size; for structs/classes the alignment is the same as the largest alignment its members, and it adds padding between members to make sure that each member has its own alignment needs met, as well as padding after the last member to make sure the struct’s own alignment needs are met during array accesses.
So, the answer to your question is the same as the answer to this question: Does malloc() return aligned addresses? And the answer to that is "maybe." There are two solutions for VC++:
* When declaring your array pFoo, use the __unaligned qualifier. The compiler will insert code to handle unaligned accesses. This is MUCH faster than using SetErrorMode() to do fixups, but not free.
* When grabbing memory for pFoo, use _aligned_alloc( 10 * sizeof(foo), __align_of(foo) ); to ensure that the base is aligned.
Disclaimer: FYI, there are some ways to confuse an x86 in such a way that it will generate an unfixable fault, using the SSE types. But in general, if you’re using SSE, either the compiler is automatically generating it and it’ll hopefully do the right thing, or you’re handcoding it and you brought it on yourself.
I believe Ken Thompson called this behaviour "Unwarranted chumminess with the compiler".
note that in C++ you can do the same by overriding the placement new operator :
void *TOKEN_GROUPS::operator new(size_t sz, int NumberOfGroups) {
return ::operator new(FIELD_OFFSET(TOKEN_GROUPS, Groups[NumberOfGroups])));
}
basically it’s just returning a block bigger than a TOKEN_GROUPS instance.
Then just invoke it as follows:
int n = 123; // whatever the NumberOfGroups must be
PTOKEN_GROUPS *p = new (n) PTOKEN_GROUPS();
Oh, sorry I forgot that this is C++, and my citation of Example 2 on page 80 is in the 1999 C standard. In the 2003 C++ standard, sizeof is on page 79 and there is no example, but there is normative wording "When applied to a class, the result is the number of bytes in an object of that class INCLUDING ANY PADDING REQUIRED FOR PLACING THAT TYPE IN AN ARRAY". Practically speaking it still looks like Intel’s compiler has a bug.
jbn: Just for the record, that’s not what’s usually meant by "placement new" (see http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.10); moreover, Roger Lipscombe mentioned earlier that it’s impossible to define new class members (like that operator new) after the fact.
Finally (assuming I remember correctly), easier would be to just define a
void* TOKEN_GROUPS::operator new[](size_t s) {…}
and do
PTOKEN_GROUPS *p=new TOKEN_GROUPS[n];
Tardis: i think you are mistaken, the name "placement new" is used because the additionnal argument being passed typically is a memory location, but it may very well be anything you want.
I agree that it’s a problem that you can’t define new members after the fact, though.
It would however be possible to make the placement of the byte array customizable by passing around a placement manager object to the placement new & to the constructor of that object.
Additionnally, using operator new[] is quite different, it’s used to allocate an array of PTOKEN_GROUPS in your example, which is not the same as allocating a single object but with a variable size…
"Zero-length arrays did not become legal Standard C until 1999. Since Windows was around long before then, it could not take advantage of that functionality in the C language. "
WTF are you talking about?
EVENTSFORLOGFILE? PACKEDEVENTINFO? CLUSPROP_BINARY? PROPERTYINSTEX? WNODE_ALL_DATA? WNODE_SINGLE_INSTANCE? WNODE_SINGLE_ITEM?
WNODE_METHOD_ITEM? WNODE_EVENT_REFERENCE? WMIREGINFOW?
It might be non-standard. But it’s useful, and makes it easier to get things correct (the size of buffer to allocate is just sizeof(structure) + sizeof(buffer)). Win32 does it in a number of places. It should do it across the board.
You’ve never had to deal with backwards compatibility have you. The answer to this is obvious:
If a structure was originally defined with a size of [1] then it must keep the original definition.
// Since TOKEN_GROUPS already contains 1
// SID_AND_ATTRIBUTES, we need
// NumberOfGroups-1 more.
PTOKEN_GROUPS TokenGroups = malloc(sizeof(TOKEN_GROUPS) + (NumberOfGroups – 1) * sizeof(SID_AND_ATTRIBUTES));
If TOKEN_GROUPS were redefined to have [], then this code would have a buffer overrun.
"You’ve never had to deal with backwards compatibility have you."
On the contrary. I suffer with backwards compatibility every time I have to write raw Win32 programs. The refusal to ever fix anything just makes writing new code much harder.
"The answer to this is obvious: "
and wrong, as obvious answers so frequently are.
"If a structure was originally defined with a size of [1] then it must keep the original definition. "
Rubbish. Change the definition when someone #defines the OS version to be (say) 0x0501 or similar. You already change other structure definitions depending on the defined OS version. Why not change these ones too? Or, hell, you could even do something really helpful (god forbid) and have a unsizedarraymembers #define to toggle the behaviour. This would let old code work whilst still permitting new code to be clean.
And why does old code need to be built against the latest and greatest Platform SDK in the first place? I mean, the whole argument for this backwards compatibility crap is that old code can’t be fixed/rewritten because it’s no longer maintained. If something’s being rebuilt anyway, it can be changed anyway.
I believe there are some structures where one couldn’t switch (because the OS expects the "size" member of the structure to exclude the first array member), but may be mistaken.
In any case, you miss the bigger point–that you’re wrong. Windows uses unsized last array members, did so prior to C99, and requires support for them even when compiling as C++. As such their inconsistent use is even more annoying.
"On the contrary. I suffer with backwards compatibility every time I have to write raw Win32 programs."
I was referring to producing backwards compatiblity, not consuming it. Rewrite a header file so that code compiled with the old header file interoperates with code compiled with the new header file, and so that somebody can take code written for the old header file, recompile with the new header file, and still work.
"what on earth makes you think I should care"
Um because that was the issue you were responding to? I was explaining why the OS can’t change the system header files.
FLEXIBLE_ARRAYS would work. Then the hard part of coordinating all the dozens of groups that produce header files to get them to follow it. (And if a single group misses a spot, I’m sure you’ll be all over it.)
The Hungarian-or-not is a separate issue which I will add to the topics list.
"Change the definition when someone #defines the OS version to be (say) 0x0501 or similar."
It’s one thing to change a definition to expose new functionality. Developers would turn on the #define and the new stuff becomes available. (Sometimes at the cost of no longer running on downlevel systems.)
But it’s another thing to change a definition so that *previously correct code compiles without a compiler warning even though it is now incorrect*.
Yes it’s inconsistent. That’s what happens when there are dozens of independent groups writing header files.
"I was referring to producing backwards compatiblity, not consuming it."
Of course you were. But what on earth makes you think I should care?
"Rewrite a header file so that code compiled with the old header file interoperates with code compiled with the new header file, and so that somebody can take code written for the old header file, recompile with the new header file, and still work."
I’ve already suggested how you might do that. Have a #define (say "FLEXIBLE_ARRAYS") that if off uses the TypeName[1] crap that we hate; if on uses the TypeName[] stuff that’s so much more convenient.
There are other #defines that don’t actually influence the headers but just make them easier to deal with (STRICT), so I don’t think adding a new one would be the end of the world.
"Yes it’s inconsistent. That’s what happens when there are dozens of independent groups writing header files. "
I know coding standards are a pain an’ all, but come on. You really can’t enforce *any* rules?
It might be nice if you could be consistent about whether to use hungarian or not for struct members. Fixing that wouldn’t even be a silently breaking change, so updating code would be mechanical and reliable process.
"Um because that was the issue you were responding to? I was explaining why the OS can’t change the system header files. "
The issue I’m responding to is, why as a developer do I have to suffer this kind of crap?
"FLEXIBLE_ARRAYS would work. Then the hard part of coordinating all the dozens of groups that produce header files to get them to follow it. (And if a single group misses a spot, I’m sure you’ll be all over it.) "
Well shit, if it’s that hard, hire me and I’ll do the job for you.
"The Hungarian-or-not is a separate issue which I will add to the topics list. "
I don’t think it’s a separate issue, really, is it? It seems to be the same issue–there is a great lack of conformity amongst the Win32 headers, as different headers do the same thing in different ways.
This might make sense from the OS developer’s point of view, because you have different groups of developers working on different areas. But it’s immensely frustrating as an application developer, because we don’t have the luxury of just sticking to a particular subset of the API. We’ve gotta use a cross-section of it, which means we have to put up with the inconsistency.
"The issue I’m responding to is, why as a developer do I have to suffer this kind of crap?"
No one is making you. Go write for something that makes your boat float.
Belated answers to exercises and other questions.
PingBack from http://aonprog.wordpress.com/2009/02/23/file-minifilter-part4-sending-huge-data-from-kernel-to-user-mode-efficiently-using-variable-sized-structures/