program - what are the other sections of the memory allocation for a process




如何僅使用標準庫分配對齊的內存? (12)

作為面試的一部分,我剛剛完成了一項測試,其中一個問題難倒我 - 甚至使用谷歌作為參考。 我想看看stackoverflow的工作人員可以用它做些什麼:

“memset_16aligned”函數需要傳遞一個16byte對齊的指針,否則它會崩潰。

a)如何分配1024字節的內存,並將其與16字節的邊界對齊?
b)在memset_16aligned執行後釋放內存。

{

   void *mem;

   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here

}

原始答案

{
    void *mem = malloc(1024+16);
    void *ptr = ((char *)mem+16) & ~ 0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

修復答案

{
    void *mem = malloc(1024+15);
    void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

按要求解釋

以防萬一,第一步是分配足夠的備用空間。 由於內存必須是16字節對齊的(意思是前導字節地址需要是16的倍數),所以增加16個額外的字節保證了我們有足夠的空間。 在前16個字節的某處,有一個16字節的對齊指針。 (注意, malloc()應該返回一個指針,該指針對任何目的來說都是非常好的,然而,'any'的含義主要針對基本類型 - longdoublelong doublelong long和指向對象和指向函數的指針當你做更專門的事情時,比如使用圖形系統,他們可能需要比系統其他部分更嚴格的對齊 - 因此問題和答案是這樣的。)

下一步是將void指針轉換為char指針; GCC儘管如此,你不應該在void指針上做指針運算(而且GCC有警告選項可以告訴你什麼時候會濫用它)。 然後將16添加到開始指針。 假設malloc()返回給你一個不可能的嚴格對齊的指針:0x800001。 添加16給出0x800011。 現在我想回到16字節的邊界 - 所以我想將最後4位重置為0. 0x0F的最後4位設置為1; 因此,除了最後四位以外, ~0x0F所有位都設置為1。 用0x800011給出0x800010。 您可以迭代其他偏移量並查看相同的算法。

free()的最後一步很簡單:你總是只返回free()這個值是malloc()calloc()realloc()返回給你的值 - 任何事情都是災難。 你正確地提供了mem來保存這個值 - 謝謝。 免費發布它。

最後,如果您了解系統的malloc包的內部信息,則可以猜測它可能會返回16字節的對齊數據(或者可能是8字節對齊的)。 如果它是16字節對齊的,那麼你就不需要使用這些值。 然而,這是不可靠和不可移植的 - 其他malloc包有不同的最小對齊,因此假設一件事情,當它做了不同的事情會導致核心轉儲。 在廣泛的範圍內,該解決方案是便攜式的

其他人提到posix_memalign()是獲得對齊內存的另一種方式; 這在任何地方都無法實現,但通常可以將此作為基礎來實施。 請注意,對齊是2的冪是方便的; 其他路線更混亂。

還有一點評論 - 這段代碼不檢查分配是否成功。

修訂

Windows程序員指出,你不能對指針進行位掩碼操作,實際上,GCC(3.4.6和4.3.1測試)確實抱怨這樣。 因此,基本代碼的修改版本 - 轉換為主程序,如下所示。 正如已經指出的那樣,我還冒昧地增加了15個而不是16個。 我使用的是uintptr_t因為C99已經足夠長,可以在大多數平台上訪問。 如果不是在printf()語句中使用PRIXPTR ,那麼#include <stdint.h>而不是使用#include <inttypes.h>就足夠了。 [這段代碼包括C.R.指出的修正,它重申了幾年前Bill K首先提出的一點,迄今為止我忽略了這一點。]

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

int main(void)
{
    void *mem = malloc(1024+15);
    void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
    return(0);
}

這裡是一個稍微更通用的版本,它適用於2:

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void memset_16aligned(void *space, char byte, size_t nbytes)
{
    assert((nbytes & 0x0F) == 0);
    assert(((uintptr_t)space & 0x0F) == 0);
    memset(space, byte, nbytes);  // Not a custom implementation of memset()
}

static void test_mask(size_t align)
{
    uintptr_t mask = ~(uintptr_t)(align - 1);
    void *mem = malloc(1024+align-1);
    void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
    assert((align & (align - 1)) == 0);
    printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
    memset_16aligned(ptr, 0, 1024);
    free(mem);
}

int main(void)
{
    test_mask(16);
    test_mask(32);
    test_mask(64);
    test_mask(128);
    return(0);
}

為了將test_mask()轉換為通用分配函數,分配器中的單個返回值必須對發布地址進行編碼,正如幾位人員在他們的答案中指出的那樣。

面試官遇到問題

Uri評論說:也許我今天早上有一個閱讀理解問題,但如果面試問題具體說:“你將如何分配1024字節的內存”,而且你明確地分配了更多。 這不是面試官自動失敗嗎?

我的回復不適合300個字符的評論...

這取決於我想。 我想大多數人(包括我)都把這個問題的意思是“你將如何分配一個空間,其中可以存儲1024個字節的數據,並且基地址是16個字節的倍數”。 如果面試官確實意味著如何分配1024個字節(僅限於)並將其與16個字節對齊,那麼這些選項會受到更多限制。

  • 顯然,有一種可能性是分配1024個字節,然後給這個地址進行“對齊處理”。 該方法的問題是實際可用空間不是正確確定的(可用空間在1008和1024字節之間,但沒有可用於指定哪個大小的機制),這使得它不太有用。
  • 另一種可能性是您需要編寫一個完整的內存分配器,並確保您返回的1024字節塊被適當對齊。 如果是這樣的話,你可能最終會做一個與建議的解決方案非常類似的操作,但是你將它隱藏在分配器中。

但是,如果面試官希望得到這些答复,我希望他們認識到,這個解決方案回答了一個密切相關的問題,然後重新構思他們的問題,指出正確的方向。 (另外,如果面試官真的很慌張,那麼我就不想要這份工作;如果對不夠精確的要求的答案在沒有更正的情況下被撲滅,那麼面試官不是一個可以安全工作的人。)

世界繼續前進

問題的標題最近已經改變。 這是在C面試問題中解決內存對齊難題的難題 。 修訂後的標題( 如何僅使用標準庫分配對齊的內存? )需要稍微修改一下的答案 - 本附錄提供了它。

C11(ISO / IEC 9899:2011)增加了函數aligned_alloc()

7.22.3.1 aligned_alloc函數

概要

#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);

描述
aligned_alloc函數為其對齊由alignment指定的對象分配空間,其大小由size指定,其值不確定。 alignment的值應該是由實現支持的有效對齊,並且size的值應該是alignment的整數倍。

返回
aligned_alloc函數返回空指針或指向分配空間的指針。

POSIX定義了posix_memalign()

#include <stdlib.h>

int posix_memalign(void **memptr, size_t alignment, size_t size);

描述

posix_memalign()函數應該分配在由alignment指定的邊界上對齊的size字節,並且應該返回一個指向memptr分配的內存的memptralignment的值應是sizeof(void *)的兩倍的冪。

成功完成後, memptr指向的值應為多重alignment

如果請求的空間大小為0,則行為是實現定義的; memptr返回的值應該是空指針或唯一指針。

free()函數將釋放之前由posix_memalign()分配的內存。

返回值

成功完成後, posix_memalign()將返回零; 否則,應返回一個錯誤編號以指示錯誤。

其中之一或兩者都可以用來回答現在的問題,但只有POSIX函數是最初回答問題時的一個選項。

在幕後,新的對齊記憶函數完成了與問題中概述的相同的工作,只是它們能夠更輕鬆地強制對齊,並在內部跟踪對齊的內存的開始,以便代碼不會必須專門處理 - 它只是釋放所使用的分配函數返回的內存。


For the solution i used a concept of padding which aligns the memory and do not waste the memory of a single byte .

If there are constraints that, you cannot waste a single byte. All pointers allocated with malloc are 16 bytes aligned.

C11 is supported, so you can just call aligned_malloc (16, size).

void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);

You can also add some 16 bytes and then push the original ptr to 16bit aligned by adding the (16-mod) as below the pointer :

main(){
void *mem1 = malloc(1024+16);
void *mem = ((char*)mem1)+1; // force misalign ( my computer always aligns)
printf ( " ptr = %p \n ", mem );
void *ptr = ((long)mem+16) & ~ 0x0F;
printf ( " aligned ptr = %p \n ", ptr );

printf (" ptr after adding diff mod %p (same as above ) ", (long)mem1 + (16 -((long)mem1%16)) );


free(mem1);
}

不幸的是,在C99中,保證任何類型的對齊方式似乎都非常困難,這種方式可以在任何符合C99的C實現中移植。 為什麼? 因為指針不能保證是平面內存模型的“字節地址”。 無論如何保證了uintptr_t的表示,它本身也是一個可選類型。

我們可能知道一些使用void * (以及定義,也是char * )的表示形式的實現,它是一個簡單的字節地址,但是對於我們這些程序員來說,C99是不透明的。 一個實現可以通過一個集合{ segmentoffset }來表示一個指針,其中offset可以讓who-knows知道什麼對齊“實際上”。 為什麼,一個指針甚至可能是某種形式的哈希表查找值,甚至是鍊錶查找值。 它可以編碼邊界信息。

在最近的C標準草案中,我們看到了_Alignas關鍵字。 這可能會有所幫助。

C99給我們的唯一保證就是內存分配函數將返回一個適合賦值給指向任何對像類型的指針的指針。 由於我們無法指定對象的對齊方式,因此我們無法實現我們自己的分配函數,並以明確定義的便攜方式負責對齊。

這個說法是錯誤的。





在16和15字節數填充前面,為了得到N的對齊,你需要添加的實際數量是max(0,NM) ,其中M是內存分配器的自然對齊(兩者都是2的冪)。

由於任何分配器的最小內存對齊是1個字節,所以15 = max(0,16-1)是一個保守的答案。 然而,如果你知道你的內存分配器會給你32位int對齊的地址(這很常見),你可以用12作為pad。

這對於這個例子來說並不重要,但對於每個保存的每個int都有12K的RAM的嵌入式系統來說,這可能很重要。

如果你實際上試圖保存每個可能的字節,實現它的最好方法是作為一個宏,這樣你就可以為它提供本地內存對齊。 同樣,這可能僅適用於需要保存每個字節的嵌入式系統。

在下面的例子中,在大多數係統中,對於MEMORY_ALLOCATOR_NATIVE_ALIGNMENT ,值1是MEMORY_ALLOCATOR_NATIVE_ALIGNMENT ,但是對於我們理論上具有32位對齊分配的嵌入式系統,以下內容可以節省一點寶貴的內存:

#define MEMORY_ALLOCATOR_NATIVE_ALIGNMENT    4
#define ALIGN_PAD2(N,M) (((N)>(M)) ? ((N)-(M)) : 0)
#define ALIGN_PAD(N) ALIGN_PAD2((N), MEMORY_ALLOCATOR_NATIVE_ALIGNMENT)

我們一直對Accelerate.framework做這樣的事情,這是一個矢量化程度很高的OS X / iOS庫,我們必須始終注意對齊。 有很多選擇,其中一個或兩個我沒有看到上面提到的。

對於像這樣的小陣列來說,最快的方法就是將其粘貼在堆棧上。 用GCC / clang:

 void my_func( void )
 {
     uint8_t array[1024] __attribute__ ((aligned(16)));
     ...
 }

沒有免費()需要。 這通常是兩條指令:從堆棧指針中減去1024,然後使用-alignment來對堆棧指針進行AND運算。 據推測,請求者需要堆上的數據,因為它的數組壽命超過了堆棧或遞歸正在工作或堆棧空間受到嚴重溢價。

在OS X / iOS上,所有對malloc / calloc / etc的調用。 總是16個字節對齊。 例如,如果您需要32個字節對齊AVX,則可以使用posix_memalign:

void *buf = NULL;
int err = posix_memalign( &buf, 32 /*alignment*/, 1024 /*size*/);
if( err )
   RunInCirclesWaivingArmsWildly();
...
free(buf);

一些人提到了類似的C ++接口。

不應該忘記頁面對齊到2的大冪,所以頁面對齊的緩衝區也是16字節對齊的。 因此,mmap()和valloc()以及其他類似的接口也是選項。 如果需要,mmap()的優點是可以將緩衝區預先初始化為非零值。 由於它們具有頁面對齊大小,因此不會從這些最小分配中獲得最小分配,並且在您第一次觸摸它時很可能會受到VM故障的影響。

俗氣:打開後衛malloc或類似的。 大小為n * 16字節的緩衝區(例如這個緩衝區)將被對齊n * 16個字節,因為VM用於捕捉超限並且其邊界位於頁邊界處。

一些Accelerate.framework函數將用戶提供的臨時緩衝區用作臨時空間。 在這裡,我們必須假設傳遞給我們的緩衝區大大失調,並且用戶正在積極努力地使我們的生活變得難以置信。 (我們的測試用例在臨時緩衝區之前和之後粘貼了一個保護頁面,以強調這個惡意)。在這裡,我們返回我們需要保證16字節對齊的區段的最小尺寸,然後手動對齊緩衝區。 這個尺寸是所希望的尺寸+對齊方式-1。所以,在這種情況下,這是1024 + 16-1 = 1039字節。 然後如下對齊:

#include <stdint.h>
void My_func( uint8_t *tempBuf, ... )
{
    uint8_t *alignedBuf = (uint8_t*) 
                          (((uintptr_t) tempBuf + ((uintptr_t)alignment-1)) 
                                        & -((uintptr_t) alignment));
    ...
}

添加對齊方式1會將指針移過第一個對齊的地址,然後用對齊方式(例如0xfff ... ff0對齊= 16)將其帶回對齊的地址。

正如其他帖子所描述的那樣,在沒有16字節對齊保證的其他操作系統上,您可以使用更大的尺寸調用malloc,稍後將free pointer()稍後放在一邊,然後如上所述對齊,然後使用對齊的指針,就像描述為我們的臨時緩衝區情況。

至於aligned_memset,這很愚蠢。 您只需循環多達15個字節即可達到一個對齊的地址,然後在對齊存儲之後繼續處理,最後使用一些可能的清理代碼。 您甚至可以在向量代碼中執行清理位,或者作為與對齊區域重疊的未對齊存儲區(提供的長度至少是向量的長度)或使用像movmaskdqu之類的東西。 有人只是懶惰。 不過,如果面試官想知道你是否對stdint.h,按位運算符和內存基礎知識感到滿意,那麼這可能是一個合理的面試問題,所以這個人為的例子可以被原諒。


我很驚訝沒有人投票支持的share ,據我了解,不可能做標準C99所要求的,因為正式將指針轉換為整數類型是未定義的行為。 (除了標准允許轉換uintptr_t < - > void* ,但標準似乎不允許對uintptr_t值進行任何操作,然後將其轉換回來。)


這是'整合'部分的另一種方法。 不是最出色的編碼解決方案,但它完成了工作,而且這種類型的語法有點容易記住(加上對於不是2的乘方值的對齊值)。 uintptr_t是安撫編譯器所必需的。 指針算術不是很喜歡分割或乘法。

void *mem = malloc(1024 + 15);
void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16;
memset_16aligned(ptr, 0, 1024);
free(mem);

long add;   
mem = (void*)malloc(1024 +15);
add = (long)mem;
add = add - (add % 16);//align to 16 byte boundary
ptr = (whatever*)(add);




memory-management