c - How to allocate aligned memory only using the standard library? -
i finished test part of job interview, , 1 question stumped me - using google reference. i'd see stackoverflow crew can it:
the “memset_16aligned” function requires 16byte aligned pointer passed it, or crash.
a) how allocate 1024 bytes of memory, , align 16 byte boundary?
b) free memory after memset_16aligned has executed.
{ void *mem; void *ptr; // answer a) here memset_16aligned(ptr, 0, 1024); // answer b) here }
original answer
{ void *mem = malloc(1024+16); void *ptr = ((char *)mem+16) & ~ 0x0f; memset_16aligned(ptr, 0, 1024); free(mem); } fixed answer
{ void *mem = malloc(1024+15); void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0f; memset_16aligned(ptr, 0, 1024); free(mem); } explanation requested
the first step allocate enough spare space, in case. since memory must 16-byte aligned (meaning leading byte address needs multiple of 16), adding 16 bytes guarantees have enough space. somewhere in first 16 bytes, there 16-byte aligned pointer. (note malloc() supposed return pointer sufficiently aligned any purpose. however, meaning of 'any' things basic types — long, double, long double, long long, , pointers objects , pointers functions. when doing more specialized things, playing graphics systems, can need more stringent alignment rest of system — hence questions , answers this.)
the next step convert void pointer char pointer; gcc notwithstanding, not supposed pointer arithmetic on void pointers (and gcc has warning options tell when abuse it). add 16 start pointer. suppose malloc() returned impossibly badly aligned pointer: 0x800001. adding 16 gives 0x800011. want round down 16-byte boundary — want reset last 4 bits 0. 0x0f has last 4 bits set one; therefore, ~0x0f has bits set 1 except last four. anding 0x800011 gives 0x800010. can iterate on other offsets , see same arithmetic works.
the last step, free(), easy: always, , only, return free() value 1 of malloc(), calloc() or realloc() returned — else disaster. correctly provided mem hold value — thank you. free releases it.
finally, if know internals of system's malloc package, guess might return 16-byte aligned data (or might 8-byte aligned). if 16-byte aligned, you'd not need dink values. however, dodgy , non-portable — other malloc packages have different minimum alignments, , therefore assuming 1 thing when different lead core dumps. within broad limits, solution portable.
someone else mentioned posix_memalign() way aligned memory; isn't available everywhere, implemented using basis. note convenient alignment power of 2; other alignments messier.
one more comment — code not check allocation succeeded.
amendment
windows programmer pointed out can't bit mask operations on pointers, and, indeed, gcc (3.4.6 , 4.3.1 tested) complain that. so, amended version of basic code — converted main program, follows. i've taken liberty of adding 15 instead of 16, has been pointed out. i'm using uintptr_t since c99 has been around long enough accessible on platforms. if wasn't use of prixptr in printf() statements, sufficient #include <stdint.h> instead of using #include <inttypes.h>. [this code includes fix pointed out c.r., reiterating point first made bill k number of years ago, managed overlook until now.]
#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 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); } and here marginally more generalized version, work sizes power of 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 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); } to convert test_mask() general purpose allocation function, single return value allocator have encode release address, several people have indicated in answers.
problems interviewers
uri commented: maybe having [a] reading comprehension problem morning, if interview question says: "how allocate 1024 bytes of memory" , allocate more that. wouldn't automatic failure interviewer?
my response won't fit 300-character comment...
it depends, suppose. think people (including me) took question mean "how allocate space in 1024 bytes of data can stored, , base address multiple of 16 bytes". if interviewer meant how can allocate 1024 bytes (only) , have 16-byte aligned, options more limited.
- clearly, 1 possibility allocate 1024 bytes , give address 'alignment treatment'; problem approach actual available space not determinate (the usable space between 1008 , 1024 bytes, there wasn't mechanism available specify size), renders less useful.
- another possibility expected write full memory allocator , ensure 1024-byte block return appropriately aligned. if case, end doing operation similar proposed solution did, hide inside allocator.
however, if interviewer expected either of responses, i'd expect them recognize solution answers closely related question, , reframe question point conversation in correct direction. (further, if interviewer got stroppy, wouldn't want job; if answer insufficiently precise requirement shot down in flames without correction, interviewer not whom safe work.)
the world moves on
the title of question has changed recently. solve memory alignment in c interview question stumped me. revised title (how allocate aligned memory using standard library?) demands revised answer — addendum provides it.
c11 (iso/iec 9899:2011) added function aligned_alloc():
7.22.3.1
aligned_allocfunctionsynopsis
#include <stdlib.h> void *aligned_alloc(size_t alignment, size_t size);description
aligned_allocfunction allocates space object alignment specifiedalignment, size specifiedsize, , value indeterminate. value ofalignmentshall valid alignment supported implementation , value ofsizeshall integral multiple ofalignment.returns
aligned_allocfunction returns either null pointer or pointer allocated space.
and posix defines posix_memalign():
#include <stdlib.h> int posix_memalign(void **memptr, size_t alignment, size_t size);description
the
posix_memalign()function shall allocatesizebytes aligned on boundary specifiedalignment, , shall return pointer allocated memory inmemptr. value ofalignmentshall power of 2 multiple ofsizeof(void *).upon successful completion, value pointed
memptrshall multiple ofalignment.if size of space requested 0, behavior implementation-defined; value returned in
memptrshall either null pointer or unique pointer.the
free()function shall deallocate memory has been allocatedposix_memalign().return value
upon successful completion,
posix_memalign()shall return zero; otherwise, error number shall returned indicate error.
either or both of these used answer question now, posix function option when question answered.
behind scenes, new aligned memory function same job outlined in question, except have ability force alignment more easily, , keep track of start of aligned memory internally code doesn't have deal specially — frees memory returned allocation function used.
Comments
Post a Comment