待辦事項 #38607

Improved standards support for aligned memory allocators

啟用日期: 2018-09-18 03:25 最後更新: 2018-12-21 05:52

回報者:
負責人:
(無)
類型:
狀態:
開啟
元件:
里程碑:
(無)
優先權:
5 - 中
嚴重程度:
5 - 中
處理結果:
檔案:
3
Vote
Score: 1
100.0% (1/1)
0.0% (0/1)

細節

Microsoft introduced _aligned_malloc(), and associated functions, with MSVCR70.DLL. Although subsequently supported in MSVCRT.DLL, from WinXP onwards, exposure of these APIs interferes with a clean build of GCC — not only insofar as, having detected presence of the APIs, GCC would become dependent on WinXP and later, thus needlessly breaking legacy support, but furthermore, the GCC sources neglect to include the requisite <malloc.h> header file, and thus do not build cleanly.

Legacy support for similar APIs was added to MinGW, in 2003/2004, under feature request #260; however, it may be ill-advised to make GCC dependent on these MinGW specific APIs, for the following reasons:­­—

  1. A patch, to incorporate them, would be unlikely to be accepted upstream.
  2. If the APIs are not detected, GCC will provide its own replacement functions.
  3. A review reveals potential flaws in the MinGW implementation.

Consequently, I suggest:—

  1. **Not** exposing the Microsoft APIs in libmsvcrt.a
  2. Reworking the MinGW implementation, to address potential flaws.
  3. Consider adding support for ISO-C11's aligned_alloc() and POSIX.1's posix_memalign() APIs.

Ticket History (3/22 Histories)

2018-09-18 03:25 Updated by: keith
  • New Ticket "Improved standards support for aligned memory allocators" created
2018-09-18 22:34 Updated by: keith
評語

To clarify, some potential issues I've noted in the current mingw-aligned-malloc.c implementation:–

  • The alignment must be an integer power of two, greater than or equal to sizeof (void *). The power of two requirement is okay, (and indeed imperative), but since malloc() itself aligns on address boundaries which are multiples of eight bytes, and (on Win32) sizeof (void *) is only four bytes, the minimum requirement is set too small — realistically, it should be no less than the natural alignment gap, within the struct:–
    1. struct
    2. { char c;
    3. union
    4. { void *p;
    5. intptr_t i;
    6. long double f;
    7. }
    8. } alignment;
    between the c and the p elements, i.e.:–
    1. alignment_min = (size_t)(& alignment.p) - (size_t)(& alignment.c);
  • The additional padding requirement, to accommodate the requested alignment, and storage for the malloc() base address, is over-specified; rather than:–
    1. p0 = malloc (size + (alignment + sizeof (void *)));
    it should be:–
    1. p0 = malloc (size + alignment - 1 + sizeof (void *));
    and more importantly, (because that correction reduces the allocation request by only one byte), instead of:–
    1. p = (void *)((((uintptr_t)(p0) + (alignment + sizeof (void *)) + offset) & ~(alignment - 1)) - offset)
    the alignment calculation should be:–
    1. p = (void *)((((uintptr_t)(p0) + alignment - 1 + sizeof (void *) + offset) & ~(alignment - 1)) - offset)
    in which case, the -1 adjustment is much more critical — it ensures that the alignment boundary is correctly rounded downwards, avoiding a potential over-alignment by one entire alignment frame higher in memory, which would open the door to a buffer overrun, when the buffer is populated from an address which is one such frame address higher in memory than has been allowed for, in the allocation.

Besides the above, there are other issues, for a follow-on comment.

(Edited, 2018-09-18 22:58 Updated by: keith)
2018-09-18 22:57 Updated by: keith
評語

Following on from my preceding comment, (which ran out of space), further issues with the existing mingw-aligned-malloc.c implementation:–

  • A comment, within the __mingw_aligned_offset_realloc() implementation, (correctly) states that "it is an error for the alignment to change"; (specifically, it is an error if either the alignment, or the offset, (or both), differ from the values specified in the original __mingw_aligned_offset_malloc() call, which created the buffer which is to be resized). Unfortunately, while:–
    1. p == (void *)((((uintptr_t)(p0) + (alignment + sizeof (void *)) + offset) & ~(alignment - 1)) - offset)
    (or corrected, as in the preceding comment):–
    1. p == (void *)((((uintptr_t)(p0) + alignment - 1 + sizeof (void *) + offset) & ~(alignment - 1)) - offset)
    is a necessary condition of compliance with the stated constraint, it is not a sufficient condition. Furthermore, since the original alignment and offset parameters are not stored, (nor is any provision made for the possibility of storing them), there simply isn't sufficient information available to __mingw_aligned_offset_realloc(), to formulate a necessary and sufficient conditional test.
2018-09-19 19:44 Updated by: keith
評語

With regard to the suggested addition of ISO-C11's aligned_alloc(), and/or POSIX.1's optional posix_memalign() APIs, either or both could be trivially implemented in terms of __mingw_aligned_malloc(), were it not for one limitation of the latter's current implementation — a limitation shared with Microsoft's _aligned_malloc() implementation: both of these implementations require accompanying (non-standard) _aligned_realloc() and _aligned_free() counterparts, which must be used when operating on the over-aligned heap, and cannot be used to operate on the regular heap. Neither ISO-C11, nor POSIX.1 require, or specify, any such complementary APIs; it is expected that regular realloc() and free() APIs are sufficient, regardless of heap block alignment.

The __mingw_aligned_free() API could be modified, to permit it to operate on over-aligned heap blocks, (allocated by __mingw_aligned_malloc() or __mingw_aligned_offset_malloc()), and on regularly aligned blocks, (allocated by malloc()); such a modified implementation could then be used in place of free(). As it stands, such an extended implementation of free() would require a "heap walk", to discriminate between regularly aligned and over-aligned blocks; this requirement precludes its deployment on Win9x, (because the _heapwalk() API is documented to be unsupported, in all but name).

A complementary extension of the __mingw_aligned_realloc() API would not be possible, unless the existing implementation is adapted to record alignment and offset attributes of over-aligned heap blocks, within the block prefix ... a modification which I identified, in my preceding comment, as a likely requirement anyway. Such a modification could obviate the need for a heap walk, to discriminate between regular and over-aligned heap blocks; it could also overcome the limitation of missing Win9x support.

2018-10-19 02:28 Updated by: keith
評語

I've been exploring a possible replacement implementation for the entire aligned heap allocator; in the process, I've just identified a further critical defect in the current implementation, viz. for both _aligned_offset_malloc(), and _aligned_offset_realloc(), Microsoft's documentation states:

_aligned_offset_malloc validates its parameters. If alignment is not a power of 2 or if offset is greater than or equal to size and nonzero, this function invokes the invalid parameter handler

The existing MinGW implementation correctly checks the power of two constraint on alignment, but it seems to completely ignore the (obvious, in spite of Microsoft's awkwardly obscure wording) offset constraint; with my modified implementation, which does honour both constraints, the original test program fails instantly, (where it presumably passed, but should not have, with the original implementation).

2018-10-30 21:57 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5433) is attached
2018-10-30 22:00 Updated by: keith
  • File memalign-testsuite.patch (File ID: 5434) is attached
2018-10-30 22:50 Updated by: keith
評語

I've attached a patch which reimplements the MinGW alternative to Microsoft's _aligned_malloc() (and complementary) API, and also an accompanying test suite. This corrects the deficiencies I've noted, in the previous MinGW implementation; it also offers the following enhancements, (unlikely to be supported by Microsoft's implementation), over the previous MinGW implementation:–

  • The __mingw_aligned_free( void * ) function is now able to distinguish pointers returned by __mingw_aligned_malloc() (or __mingw_aligned_offset_malloc()) from other pointers; if the pointer argument cannot be identified as referring to a __mingw_aligned_malloc() allocated block, it is passed directly to free(), instead of freeing as an aligned heap block.
  • A new public API entry, __mingw_maybe_aligned_realloc( void *, size_t ), is provided; this offers the same discriminatory behaviour, w.r.t. its pointer argument, as does the reimplementation of __mingw_aligned_free( void * ).

Unless there are significant objections, I propose incorporating this alternative implementation of the __mingw_aligned_malloc() API, into the wsl-5.2 release.

(Edited, 2018-10-31 04:29 Updated by: keith)
2018-10-31 04:26 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5433) is deleted
2018-10-31 04:27 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5435) is attached
2018-12-08 05:25 Updated by: keith
  • File memalign-testsuite.patch (File ID: 5434) is deleted
2018-12-08 05:25 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5435) is deleted
2018-12-08 05:26 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5441) is attached
2018-12-08 07:00 Updated by: keith
評語

Following a brief dialogue, on the project contributors (private) forum, I've updated the implementation to provide:–

  1. void *__mingw_realloc( void *, size_t );
  2. void __mingw_free( void * );
each of which has been implemented with a capability to detect whether its void * argument refers to memory allocated by a function providing default malloc() alignment, or by any of the functions offering __mingw_aligned_malloc(), (but *not* Microsoft's _aligned_malloc()), extended alignment, and to proceed accordingly. Additionally, for congruence with both Microsoft's and our own earlier implementation, this reimplementation continues to provide (modified versions of):–
  1. void *__mingw_aligned_malloc( size_t, size_t );
  2. void *__mingw_aligned_offset_malloc( size_t, size_t, size_t);
  3. void *__mingw_aligned_offset_realloc( void *, size_t, size_t, size_t );
  4. void *__mingw_aligned_realloc( void *, size_t, size_t );
  5. void __mingw_aligned_free( void * );

Do please note that, while this latter function set is semantically equivalent to its Microsoft counterpart, it is not binary compatible; additionally, void __mingw_aligned_free( void * ); has become redundant — it is now, in fact, implemented as a trivial alias for void __mingw_free( void * );

I have updated the attached patch files, to reflect this revised implementation.

2018-12-08 07:24 Updated by: keith
評語

Following on from my preceding comment, astute readers may observe that, since

  1. void *__mingw_realloc( void *, size_t );
  2. void __mingw_free( void * );
can handle both malloc() alignment, and __mingw_aligned_malloc() alignment, and since their signatures are semantically compatible, they could be mapped as redirection targets for calls to
  1. void *realloc( void *, size_t );
  2. void free( void * );
respectively, thus providing a suitable foundation for implementations of an ISO-C11 compatible
  1. void *aligned_alloc( size_t, size_t );
and a POSIX.1 compatible
  1. int posix_memalign( void **, size_t, size_t );
in terms of simple (potentially in-line) wrappers around
  1. void *__mingw_aligned_malloc( size_t, size_t );

2018-12-08 21:16 Updated by: keith
  • Details Updated
2018-12-12 19:54 Updated by: keith
  • File aligned-heap-api.patch (File ID: 5441) is deleted
2018-12-12 20:13 Updated by: keith
評語

I replaced the primary reimplementation patch file, to incorporate some small (but necessary) corrective changes. I've also added a tentative implementation for both ISO-C11's aligned_alloc() function, and POSIX.1-2001's posix_memalign() function.

I am inclined to push the reimplementation of the existing API, together with the accompanying test suite, without further delay, but to defer pushing the new additions, pending peer review and comment.

2018-12-21 05:52 Updated by: keith
評語

I committed #33a73a6 and #68d0570. The former reimplements the original MinGW aligned heap management API, correcting the identified deficiencies in the original implementation, retaining each of the original API functions, and adding __mingw_realloc() and __mingw_free() as discussed; the latter implements a new test suite for the API, replacing the original test program, (which turned out to be not particularly useful).

This reimplementation of the aligned heap management API will be incorporated into the next WSL release. At this stage, I have not committed any implementation for the proposed ISO-C11 aligned_alloc() and POSIX.1 posix_memalign() functions; I am deferring these, pending peer review, and user demand.

(Edited, 2018-12-21 06:16 Updated by: keith)

Attachment File List

編輯

Please login to add comment to this ticket » 登入