Cisco Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
The memory returned by malloc is contiguous block of memory (like an array). When it is free'd , it goes back into a (linked) list of free blocks.
That means if we try to access the memory location where the malloc returns the pointer, it should show us the size of blocks allocated. I doubt it.
Can you please explain what is structure of memory allocated by malloc and where it stores the size?
@Piyush: "if we try to access the memory location where the malloc returns the pointer, it should show us the size of blocks allocated"
No, that's certainly not true. And it would be bad if it were, because then writing to *returned_ptr would erase this critical information! What I'm sure the poster is saying is that an attempt to allocate k bytes actually allocates a block of k+1 bytes and returns you a pointer to start_of_block + 1. So if you did *(returned_ptr - 1) you'd get the size.
I have two things to note about this theory. First of all it has to be something like size_asked_for + sizeof(void*), since you'll need multiple bytes (like maybe 4) to store the length. A single byte couldn't fit the length. Second, implementation details of this sort are compiler-specific. That said, I hear this is often how it's done. Another possible approach would be to keep some sort of pointer to size mapping (like a hash table, for example) somewhere.
agree totally with the above comment. Malloc allocates size+1 blocks and returned pointer ptr points to the second block. so if you access the first block by ptr[-1] , it prints the size. I wrote a small prog to verify it.
What type is ptr in this test that you did? The allocation shouldn't be size+1 bytes, but size+sizeof(void*) or something like that (compiler-dependent, though). Did you cast the value returned by malloc to int* first? In that case, ptr[-1] actually read returned_ptr - sizeof(int), which is what I would expect.
malloc has to make OS api calls to talk to global heap manager, which would return a pointer to memory block if it can, else NULL. This bookkeeping work is done by OS processes and is nothing to do with malloc or free. malloc or free are just used to invoke those apis.
As far as good datastructure for heapMemoryManagement is considered we can use linked list.
struct node{
void * meory_location;
int memory_allocated_in_bytes_offset;
}
And maintain this in sorted order, so that for call to malloc or free we would have to just traverse this list.
I was asked this question - How does free() knows how much memory to free ?- in bloomberg interview. The answer to that is - when you do malloc(size); it reserves size+1 bytes of memory and it stores the value size in the first block. So, when we do free(ptr), it immediately knows how much memory to free.
- rkt August 14, 2012