General question: AFAICT, on amd64 _ _crt_malloc() seems to always return an address that is a power-of-two + 8 bytes. Why isn't it at least _ _alignof(max_align_t) aligned?
For example, it appears that malloc(3) always returns a suitably aligned allocation as long as the request is for more than 8 bytes.

In D41150#937084, @becker.greg_att.net wrote:

General question: AFAICT, on amd64 _ _crt_malloc() seems to always return an address that is a power-of-two + 8 bytes. Why isn't it at least _ _alignof(max_align_t) aligned?
For example, it appears that malloc(3) always returns a suitably aligned allocation as long as the request is for more than 8 bytes.

There is no reason except that sizeof(void *) is the min required alignment of the __crt_malloc() to be usable, and the allocator is exceptionally simple. It is not intended to be even close to regular malloc(3) on its features.

General observation. Overall I like this new feature! But I have a suspicion that using it for pthread mutexes might increase the lock/unlock latency a wee bit.

Consider that the size of struct pthread_mutex_t is something like 96 bytes, so _ _crt_malloc() will allocate the space from a 128-byte integrally aligned bucket, and hence the lock will straddle two adjacent cachelines, which on amd64 will prefetch the sibling when we first touch either the first or second line. This is good because we will modify both cache lines when acquiring and releasing a lock. But then I suspect this is all just a happy accident.

However, if we use _ _crt_aligned_alloc() to allocate the lock, then the memory will come from a 256-byte bucket (so, 4 64-byte cachelines), and the lock will straddle the two inner cache lines (i.e., it'll cross a 128-byte boundary). The adjacent cacheline prefetcher will eventually load all four cachelines of which we'll generally only need two, and we'll lose the benefit of the prefetcher to load the entire lock structure when we touch either the upper or lower part of the structure. So pthread mutex lock/unlock requests might wait on memory a bit longer than they do currently. Also, we'll get half as many locks per page (16 vs 32 at best), which might be noticable for apps that allocate a lot of locks.

So overall, it'll be a bit more resource intensive, but probably not noticable in situ.

In D41150#937597, @becker.greg_att.net wrote:

General observation. Overall I like this new feature! But I have a suspicion that using it for pthread mutexes might increase the lock/unlock latency a wee bit.

Consider that the size of struct pthread_mutex_t is something like 96 bytes, so _ _crt_malloc() will allocate the space from a 128-byte integrally aligned bucket, and hence the lock will straddle two adjacent cachelines, which on amd64 will prefetch the sibling when we first touch either the first or second line. This is good because we will modify both cache lines when acquiring and releasing a lock. But then I suspect this is all just a happy accident.

However, if we use _ _crt_aligned_alloc() to allocate the lock, then the memory will come from a 256-byte bucket (so, 4 64-byte cachelines), and the lock will straddle the two inner cache lines (i.e., it'll cross a 128-byte boundary). The adjacent cacheline prefetcher will eventually load all four cachelines of which we'll generally only need two, and we'll lose the benefit of the prefetcher to load the entire lock structure when we touch either the upper or lower part of the structure. So pthread mutex lock/unlock requests might wait on memory a bit longer than they do currently. Also, we'll get half as many locks per page (16 vs 32 at best), which might be noticable for apps that allocate a lot of locks.

So overall, it'll be a bit more resource intensive, but probably not noticable in situ.

Are you saying that instead of aligning pthread_mutex allocations, we just need to ensure that allocation is padded to the end of the cache line? Then, perhaps the same thing needs to be done to rwlocks and spinlocks?

Are you saying that instead of aligning pthread_mutex allocations, we just need to ensure that allocation is padded to the end of the cache line? Then, perhaps the same thing needs to be done to rwlocks and spinlocks?

No, I don't think any padding is required, but perhaps I'm not fully understanding your question. For pthread mutex I think the current allocation is ideal, but I suspect that's just an accident of it's size (~96 bytes) and the way in which the allocator works (i.e., the structure fits well within an integrally-aligned 128-byte bucket, including the allocator's overhead, and for platforms that have 64-byte cachelines and adjacent cacheline prefetching we get fully usable prefetches and maximum density of locks per page).

But rwlocks are 40-bytes and spinlocks are 32-bytes, so they each wind up in 64-byte buckets as allocated by aligned_alloc(). Given two such locks that are adjacent within an integral 128-bytes then heavily accessing them from different CPUs on a platform that performs adjacent cacheline prefetching we see a slight degradation. I've tried to measure this, it's does impact the performance a little, but it's nowhere near as bad as false-sharing of the same cache line.
Presuming you switch their allocator over to _ _ crt_malloc(), then to maximize performance in this case all that's required is to round up the allocation size of rw/spin lock to CACHE_LINE_SIZE and the bucket allocator will put them into their own private 128-byte buckets (due to it's addition of the tracking structure that resides within the allocation).

But then it gets messy. For a platform like s390x which I think has 256-byte cachelines and presumably does not perform adjacent cacheline prefetch, you would only want to round up the lock to half a cacheline, such that after the allocator adds its overhead it gives you back a 256-byte bucket.
For example, currently if we were to allocate 8 spinlocks or 6 rwlocks in a row on s390x, then on a freshly booted machine they likely all would reside in contiguous virtual memory (a series of 64-byte buckets). This would cause severe false sharing on that platform.

Doh, I see now FreeBSD doesn't support s390x, but the example still holds. It would be nice to have a table of cacheline sizes for all supported architectures, as well as know which ones support adjacent cacheline prefetch.

But all the above relies on the current behavior of _ _crt_malloc(), which makes me uneasy in that if the implementation changed it might throw off the layout calculus. That said, I don't think it would be terrible in that case, but it might quietly revert from reasonably optimal...

Does that make sense?

With tail pad, I mean the following. The goal of the exercise is not to get specific alignments, but ultimately ensure that lock objects do not (false) share cache lines with any other objects. Alignment ensures that there is no sharing with something before the lock, while padding would do the same for objects after the the lock. Currently details of the allocation implementation (buddy split) gives that for free, but in principle we need both align and padding, to guarantee the property regardless of the allocator.

I do not intend to switch rwlocks or spinlocks to __crt_malloc(), there is no point. For mutexes, it is sort of required because regular malloc(3) needs mutexes to operate, and I lost the fight with avoiding the recursion _and_ handling the special cases of early initialization/libthr dyn loading and other small but practically important situations.

So now I am wondering if __crt_aligned_alloc() should be abandoned. Other cleanup from this review should go in, IMO.

In D41150#938121, @kib wrote:

With tail pad, I mean the following. The goal of the exercise is not to get specific alignments, but ultimately ensure that lock objects do not (false) share cache lines with any other objects. Alignment ensures that there is no sharing with

So now I am wondering if __crt_aligned_alloc() should be abandoned. Other cleanup from this review should go in, IMO.

Ah, right. So what I generally do in this case is append "__aligned(CACHE_LINE_SIZE)" (or whatever size) to the end of the structure definition, which then gets me the correct amount of unnamed tail padding and ensures that static definitions have the correct alignment and spacing (and works well for arrays of such items). But for dynamic allocations of course you must use something like aligned_alloc() to get the correct alignment. I think this approach eliminates the messiness in the code of having to maintain explicit tail padding.

Unfortunately, if we did that for struct pthread_mutex_t, then in _ _crt_malloc(sizeof(struct pthread_t)) would use a 256-byte bucket and hence waste about 128 bytes. But the upside is that the lock would still reside only in the first two cachelines like it does today. OTOH, statically defined struct pthread_mutex_t is hit or miss, as on amd64 they really should be 128-byte aligned to prevent false-sharing that would occur if the lock started on an odd multiple of cache line size.

Agreed, I typically don't like to introduce new code that doesn't have an immediate use, so tabling it for now seems like the right course of action...

Ping? Note that libthr changes are not planned for commit ATM.