c language - 如何僅使用標準庫分配對齊的內存?




other parameter (15)

If there are constraints that, you cannot waste a single byte, then this solution works: Note: There is a case where this may be executed infinitely :D

   void *mem;  
   void *ptr;
try:
   mem =  malloc(1024);  
   if (mem % 16 != 0) {  
       free(mem);  
       goto try;
   }  
   ptr = mem;  
   memset_16aligned(ptr, 0, 1024);

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

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

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

{

   void *mem;

   void *ptr;

   // answer a) here

   memset_16aligned(ptr, 0, 1024);

   // answer b) here

}

取決於你如何看待這個問題有三個略有不同的答案:

1)對於問的確切問題,Jonathan Leffler的解決方案已經足夠好了,除了最多需要16對齊之外,您只需要15個額外的字節,而不是16個。

A:

/* allocate a buffer with room to add 0-15 bytes to ensure 16-alignment */
void *mem = malloc(1024+15);
ASSERT(mem); // some kind of error-handling code
/* round up to multiple of 16: add 15 and then round down by masking */
void *ptr = ((char*)mem+15) & ~ (size_t)0x0F;

B:

free(mem);

2)對於更通用的內存分配函數,調用者不希望跟踪兩個指針(一個使用,一個釋放)。 所以你在對齊的緩衝區下面存儲一個指向'真正'緩衝區的指針。

A:

void *mem = malloc(1024+15+sizeof(void*));
if (!mem) return mem;
void *ptr = ((char*)mem+sizeof(void*)+15) & ~ (size_t)0x0F;
((void**)ptr)[-1] = mem;
return ptr;

B:

if (ptr) free(((void**)ptr)[-1]);

請注意,與(1)不同(1),其中只有15個字節被添加到mem中,如果您的實現恰好保證了malloc的32字節對齊,則此代碼實際上可以減少對齊(不太可能,但理論上C實現可能有32字節對齊類型)。 這並不重要,如果你只是調用memset_16aligned,但是如果你使用內存作為結構,那麼它可能很重要。

我不確定這是一個很好的解決方案(除了警告用戶返回的緩衝區不一定適合任意結構),因為沒有辦法通過編程來確定實現特定的對齊保證是什麼。 我想在啟動時你可以分配兩個或更多的1字節緩衝區,並假設你看到的最差對齊是保證對齊。 如果你錯了,你會浪費記憶。 任何人有更好的主意,請說出來...

[ 補充 :'標準'技巧是創建'可能是最大對齊類型'的聯合以確定必要的對齊。 最大對齊類型可能是(在C99中)' long long ',' long double ',' void * '或' void (*)(void) '; 如果你包含<stdint.h> ,你可能會使用' intmax_t '來代替long long (並且在Power 6(AIX)機器上, intmax_t會給你一個128位整數類型)。 該聯合的對齊要求可以通過將其嵌入到具有單個字符的結構中,然後使用聯合來確定:

struct alignment
{
    char     c;
    union
    {
        intmax_t      imax;
        long double   ldbl;
        void         *vptr;
        void        (*fptr)(void);
    }        u;
} align_data;
size_t align = (char *)&align_data.u.imax - &align_data.c;

然後,您將使用所請求對齊的較大值(在本例中為16)和上面計算的align值。

在(64位)Solaris 10上,似乎malloc()的結果的基本對齊方式是32字節的倍數。
]

實際上,對齊的分配器通常需要一個參數來進行對齊,而不是硬連線。 因此,用戶將傳遞他們關心的結構的大小(或者大於或等於2的最小次冪),並且一切都會好的。

3)使用你的平台提供的:POSIX的posix_memalign ,Windows的_aligned_malloc

4)如果你使用C11,那麼最簡潔 - 便攜和簡潔的選項就是使用在這個版本的語言規範中引入的標準庫函數aligned_alloc



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);
}

也許他們會對memalign的知識滿意? 正如Jonathan Leffler指出的那樣,有兩個更新的可以理解的功能。

哎呀,弗羅林打敗了我。 但是,如果您閱讀了我鏈接的手冊頁,則很可能會理解早期海報提供的示例。


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);


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

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

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

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

這個說法是錯誤的。



原始答案

{
    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函數是最初回答問題時的一個選項。

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


特定於MacOS X:

  1. 所有分配malloc的指針都是16字節對齊的。
  2. C11被支持,所以你可以調用aligned_malloc(16,size)。

  3. MacOS X選擇在啟動時為memset,memcpy和memmove針對單個處理器進行了優化的代碼,並且該代碼使用您從未聽說過的技巧來加快速度。 memset運行速度比任何手寫memset16運行速度快99%,這使得整個問題變得毫無意義。

如果你想要一個100%的便攜式解決方案,在C11之前就沒有。 因為沒有可移植的方式來測試指針的對齊方式。 如果它不必是100%便攜式,則可以使用

char* p = malloc (size + 15);
p += (- (unsigned int) p) % 16;

這假定當將指針轉換為無符號整數時,指針的對齊被存儲在最低位中。 轉換為無符號整數會丟失信息,並且已定義實現,但這並不重要,因為我們不會將結果轉換回指針。

可怕的部分當然是原始指針必須保存在某個地方,以便用它來調用free()。 總而言之,我真的會懷疑這種設計的智慧。


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

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

在閱讀這個問題時,我首先想到的第一件事是定義一個對齊的結構,實例化它,然後指向它。

因為沒有其他人提出這個建議,我缺少一個根本原因嗎?

作為一個旁注,因為我使用了一個char數組(假設系統的char是8位(即1個字節)),我不需要屬性 ((packed))必然(如果我錯了,請糾正我),但我反正說了。

這適用於我試過的兩個系統,但有可能存在一個編譯器優化,我不知道給我提供了與代碼功效相關的誤報。 我在OSX上使用gcc 4.9.2,在Ubuntu上使用gcc 5.2.1。

#include <stdio.h>
#include <stdlib.h>

int main ()
{

   void *mem;

   void *ptr;

   // answer a) here
   struct __attribute__((packed)) s_CozyMem {
       char acSpace[16];
   };

   mem = malloc(sizeof(struct s_CozyMem));
   ptr = mem;

   // memset_16aligned(ptr, 0, 1024);

   // Check if it's aligned
   if(((unsigned long)ptr & 15) == 0) printf("Aligned to 16 bytes.\n");
   else printf("Rubbish.\n");

   // answer b) here
   free(mem);

   return 1;
}

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


position-independent code在大多數架構上都有性能開銷,因為它需要額外的寄存器。

所以,這是出於性能目的。





c memory-management