NVIDIA Interview Question
Software Engineer / DevelopersWhy don't you use the function
memalign
? It's in stdlib.h and works perfectly with SSE instructions.
Happy coding!
the start address of the first allocated memory is given, when free is called with this address, it would free the entire bytes that was allocated at the beginning, based on the extra bits it uses to store that information. how do we handle this, change that info to store only the difference. correct me if my understanding is wrong. thanks !!
the start address of the first allocated memory is given, when free is called with this address, it would free the entire bytes that was allocated at the beginning, based on the extra bits it uses to store that information. how do we handle this, change that info to store only the difference. correct me if my understanding is wrong. thanks !!
Some background on this question, this was asked to me in phone interview at Nvidia. Interviewer gave me 48 hours to solve this and also warned me that do not copy from internet.
I spend almost a day thinking about how to do it . Then looked at implementation of malloc and clicked to me that I can store original address just
before return address. It worked. Need some tuning about how to fix corner cases.
After week of submission , got mail from NVIDIA for another phone interview.
Eventually, got selected after 6-7 onsite interview rounds.
There is abug in these lines:
size_t addr=(size_t)p1+alignment+sizeof(size_t);
p2=(void *)(addr - (addr%alignment));
The fix is simple:
size_t addr=(size_t)p1+alignment+sizeof(void *);
p1 = (void *)addr + sizeof(void *)
p2=(void *)(p1 - (p1%alignment));
The code they gave is correct.
You don't need 2 void *'s:
addr = (size_t)p1 + alignment + sizeof(size_t);
p2 = (void *)(addr - (addr%alignment));
addr is alignment + sizeof(size_t) bytes away from p1
Therefore addr - (addr%alignment) is at most alignment - 1 bytes from addr, so you will always be sufficiently able to go back sizeof(size_t) bytes.
i.e., *((size_t *)p2 - 1) = p1
//
// Allocates and returns pointer aligned to requested boundary
//
void* AlignedAlloc( size_t cbSize, size_t cbAlign )
{
//
// Align Align-1 ~(Align-1)
// 8 00001000 00000111 11111000
// 16 00010000 00001111 11110000
// 32 00100000 00011111 11100000
// 64 01000000 00111111 11000000
// 128 10000000 01111111 10000000
void *p;
void *ap;
size_t cbExtra = cbAlign+sizeof(void*);
p = LocalAlloc( NONZEROLPTR, cbExtra + cbSize);
ap = (BYTE*) ((size_t)p & ~(cbAlign-1)) + cbAlign;
*((void**)ap-1) = p;
_ASSERT( 0 == (size_t)ap % cbAlign );
return ap;
}
void AlignedFree( void* p)
{
LocalFree( *((void**)p-1) );
}
#include <map>
class AlignedMemoryManager
{
public:
void* MallocAligned( uint size, uint alignment);
bool FreeAligned( uintptr_t address);
private:
std::map<void*,void*> allocationMap_;
}
void* AlignedMemoryManager::MallocAligned( uint size, uint alignment){
{
size_t actualSize = (alignment-1)+size;
void * result = malloc(actualSize);
void* alignedResult = NULL;
if( result != NULL )
{
alignedResult = result + result%alignments
allocationMap_.insert(make_pair(alignedResult, result ) );
}
return alignedResult;
}
bool AlignedMemoryManager::FreeAligned( uintptr_t address)
{
std::map<void*,void*>::iterator it = allocationMap_.find( address );
if( it != allocationMap_.end() )
{
free( it->second);
allocationMap_.erase( it)
return true;
}
return false;
}
#include <stdio.h>
#include <malloc.h>
void* align_malloc(int bytes,int align_byte, void** fp)
{
void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;
u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;
u = (unsigned long)u_addr;
if(u % align_byte == 0)
return u_addr;
i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}
a_addr = (void*)i;
*fp = u_addr;
return a_addr;
}
#include <stdio.h>
#include <malloc.h>
void* align_malloc(int bytes,int align_byte, void** fp)
{
void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;
u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;
u = (unsigned long)u_addr;
if(u % align_byte == 0)
return u_addr;
i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}
a_addr = (void*)i;
*fp = u_addr;
return a_addr;
}
#include <stdio.h>
#include <malloc.h>
void* align_malloc(int bytes,int align_byte, void** fp)
{
void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;
u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;
u = (unsigned long)u_addr;
if(u % align_byte == 0)
return u_addr;
i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}
a_addr = (void*)i;
*fp = u_addr;
return a_addr;
}
#include <stdio.h>
#include <malloc.h>
void* align_malloc(int bytes,int align_byte, void** fp)
{
void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;
u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;
u = (unsigned long)u_addr;
if(u % align_byte == 0)
return u_addr;
i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}
a_addr = (void*)i;
*fp = u_addr;
return a_addr;
}
I checked it it works !!
- NewGuy April 26, 2008#include <stdio.h>
#include <stdlib.h>
/*************************************************
Name :- aligned_malloc
Arguments:- number of bytes & Alignment Boundry
Return :- NULL on error
valid pointer on success
Working :- It will allocate memory with starting address
multiple of alignment passed and returns pointer
to it on success.
Ex.
aligned_malloc(50,128);
This will allocate 50 bytes of memory with
starting address multiple of 128.
*************************************************/
void *aligned_malloc(size_t bytes, size_t alignment)
{
void *p1 ,*p2; // basic pointer needed for computation.
/* We need to use malloc provided by C. First we need to allocate memory
of size bytes + alignment + sizeof(size_t) . We need 'bytes' because
user requested it. We need to add 'alignment' because malloc can give us
any address and we need to find multiple of 'alignment', so at maximum multiple
of alignment will be 'alignment' bytes away from any location. We need
'sizeof(size_t)' for implementing 'aligned_free', since we are returning modified
memory pointer, not given by malloc ,to the user, we must free the memory
allocated by malloc not anything else. So I am storing address given by malloc just above
pointer returning to user. Thats why I need extra space to store that address.
Then I am checking for error returned by malloc, if it returns NULL then
aligned_malloc will fail and return NULL.
*/
if((p1 =(void *) malloc(bytes + alignment + sizeof(size_t)))==NULL)
return NULL;
/* Next step is to find aligned memory address multiples of alignment.
By using basic formule I am finding next address after p1 which is
multiple of alignment.I am storing new address in p2.
*/
size_t addr=(size_t)p1+alignment+sizeof(size_t);
p2=(void *)(addr - (addr%alignment));
/* Final step, I am storing the address returned by malloc 'p1' just "size_t"
bytes above p2, which will be useful while calling aligned_free.
*/
*((size_t *)p2-1)=(size_t)p1;
return p2;
}
/************************************************
Name :- aligned_free
Arguments :- pointer to be freed
Returns :- Nothing
*************************************************/
void aligned_free(void *p )
{
/* Find the address stored by aligned_malloc ,"size_t" bytes above the
current pointer then free it using normal free routine provided by C.
*/
free((void *)(*((size_t *) p-1)));
}