Hewlett Packard Interview Question


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
7
of 7 vote

The answer needs little understanding of C runtime (CRT) memory management. malloc() takes size of memory to allocate, but free() does not. So, when someone sends a pointer to free() method, CRT should be able to know the amount of memory to be released. This is what I would like to refer to as 'metadata'.

When a memory allocation for 'n' bytes requested by program, CRT internally allocates 'n' + 'm' bytes. Where 'm' bytes are for its metadata like how much is allocated, etc. CRT fills in 'm' bytes of metadata and returns the pointer by 'm' byte offset to the program. When programs calls free, CRT simply subtracts 'm' from the given address to locate metadata for that allocation.

Here in this code, we are passing a pointer shifted by sizeof(char). So, the metadata it reads is not correct. At this time, the behavior depends really on CRT.

Many legacy CRTs just do not accommodate such 'bad' programs, and result in unpredictable behavior (including program crashes).

I believe CRT can keep fixed byte value at fixed offset with in metadta (cookie?). Check the fixed value at the fixed offset and make sure the metadata read is correct. If it is not, it can simply return error 'invalid pointer'.

Hope this helps.

Thanks
Laxmi

- Laxmi Narsimha Rao Oruganti November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

WOW, Great insight Laxmi.. Thanks for sharing..
Yeah that's absolutely correct what she has told above lines. However adding further towards answering this question from HP , It yes a memory leak, what has actually happend here is during allocation a chunk of 10 bytes memory from heap is returned and the head is being holded by pointer p. but when I say p++ I said p to just forward its next data address (i.e. add of P + 1*datatype of p), so Now P here is just unaware of its first byte of allocation and now when I say free(p),and all but first address gets deleted. Reason free() usage of knows frm where to start releasing to till when, which in this case being array goes releasing till char 10 but avoiding first one.

- hprem991 November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes lakshmi, your opinion about CRT is correct, but I am still not convinced if this will lead to mem leak.

What I thought and answered was, it depends. Either free will free the complete memory of 10 bytes or will return failure, but it won't free the 9 bytes.

I was of the opinion, given a pointer, free using a system call will be able to figure out the metadata associated with the mem block, and should be able to free up the block..looks like i was wrong?

- Varun November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did not say it is a memory leak. My conclusion is free(p) leads to unpredictable behavior (including crash). CRT could behave well by detect these kinds of situations and returning an error 'Invalid Pointer'.

OS Memory APIs are system calls but C Memory API are not. For example, malloc and free are C Memory API, where as HeapAlloc is Windows OS Memory API.

CRT optimizes the system call cost by allocating a good amount of heap and does memory management of that heap by itself as I mentioned above.

hprem991: I am afraid that you are wrong about free releases fewer bytes than allocated. CRT does not know how much allocated unless it gets the metadata which itself is read at wrong location. free method here just gets confused.

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Lakshmi, Agreed with your comment to "hprem991".

Back to our discussion, surely malloc and free are C libraries, but these don't do actual mem allocation/de-allocation rite? At the end, malloc/new or whatever, will end up using a system call lie brk, sbrk etc to get memory, and therefore its the kernel who will have access to metadata associated with each block allocated, and thereby meaning free maybe able to get hold of metadata, and free up things.

- Varun November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the understanding I have. CRT allocates a big chunk say 100 KB of heap space. This heaps metadata is surely with OS. At this time, CRT has one entry in free list which says 100 KB free memory.

Now, when user asks 100 bytes, CRT gives 100 + m bytes from this and free-list entry gets updated to 100KB-100-m and alloc-list gets a new entry with data 100+m bytes. Like this, for every allocation CRT alloc-list and free-list are updated. There are merge, compaction, etc. usually memory management techniques that are done when you free memory.

Now as you can see there are two metadatas. The metadata of large chunks that CRT allocates which are with OS and there are small allocation with in this heap whose metadata sits right inside the heap.

System calls are costly and I believe that is why languages do these things. In case of .NET, Java also virtual machine allocates the large chunks and have their own memory managements of that chunk.

Hope this clears up. I will double confirm the stuff and also provide pointers to online materials once I find them. I was trying to browse FreeBSD (fxr.watson.org) and I could not find any good link.

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, by definition there's a memory leak when you do p++, in the sense that you loose any reference to the allocated memory. Memory leaks are not necessarily related with free().
That said, the wrong free() has all the consequences illustrated by Laxmi.

- david.rebatto@gmail.com March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanx for sharing

- kuldeep June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

there is no memory leak, we will get memory access violation and sometime segmentation fault. so overall result will e unpredicatble.

- getjar.com/todotasklist my android app November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I made a test using Dev-C++ the code doesn't release memory at all.
For gcc version egcs-2.91.57 it generates a core.
So overall result is unpredictable

- marcind November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, looks like devC++ is problematic.
I tried this on DevC++ only, it confused me, thnx to discussion here, I was able to sort things out for me.

- varun November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

tux@tux-laptop:/tmp$ uname -a
Linux tux-laptop 2.6.32-34-generic #77-Ubuntu SMP Tue Sep 13 19:40:53 UTC 2011 i686 GNU/Linux
tux@tux-laptop:/tmp$ cat a.c
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
char *p = malloc(10);
p++;
free(p);
return 0;
}

tux@tux-laptop:/tmp$ ./a.out
*** glibc detected *** ./a.out: free(): invalid pointer: 0x0854e009 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6(+0x6b591)[0x400591]
/lib/tls/i686/cmov/libc.so.6(+0x6cde8)[0x401de8]
/lib/tls/i686/cmov/libc.so.6(cfree+0x6d)[0x404ecd]
./a.out[0x804843e]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0x3abbd6]
./a.out[0x8048381]
======= Memory map: ========
00110000-0012d000 r-xp 00000000 08:01 1548429 /lib/libgcc_s.so.1
0012d000-0012e000 r--p 0001c000 08:01 1548429 /lib/libgcc_s.so.1
0012e000-0012f000 rw-p 0001d000 08:01 1548429 /lib/libgcc_s.so.1
00395000-004e8000 r-xp 00000000 08:01 1565769 /lib/tls/i686/cmov/libc-2.11.1.so
004e8000-004e9000 ---p 00153000 08:01 1565769 /lib/tls/i686/cmov/libc-2.11.1.so
004e9000-004eb000 r--p 00153000 08:01 1565769 /lib/tls/i686/cmov/libc-2.11.1.so
004eb000-004ec000 rw-p 00155000 08:01 1565769 /lib/tls/i686/cmov/libc-2.11.1.so
004ec000-004ef000 rw-p 00000000 00:00 0
00d95000-00db0000 r-xp 00000000 08:01 1548364 /lib/ld-2.11.1.so
00db0000-00db1000 r--p 0001a000 08:01 1548364 /lib/ld-2.11.1.so
00db1000-00db2000 rw-p 0001b000 08:01 1548364 /lib/ld-2.11.1.so
00e6d000-00e6e000 r-xp 00000000 00:00 0 [vdso]
08048000-08049000 r-xp 00000000 08:01 696853 /tmp/a.out
08049000-0804a000 r--p 00000000 08:01 696853 /tmp/a.out
0804a000-0804b000 rw-p 00001000 08:01 696853 /tmp/a.out
0854e000-0856f000 rw-p 00000000 00:00 0 [heap]
b7600000-b7621000 rw-p 00000000 00:00 0
b7621000-b7700000 ---p 00000000 00:00 0
b77c6000-b77c7000 rw-p 00000000 00:00 0
b77dd000-b77df000 rw-p 00000000 00:00 0
bf951000-bf966000 rw-p 00000000 00:00 0 [stack]
Aborted

- anon December 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

as already mentioned by someone, with each memory allocation, kernel stores base address & offest which is accessed at the time of free. When we do p++, it increments the base address which is not present in malloc map. Thus we get below result

This is what i got in output:

Compiler message:
Abort Called

Error (stderr)
*** Error in `solution': free(): invalid pointer: 0x000000000097c011 ***

- Deepesh February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Before jumping into unnecessary details of system memory management, a google search for free manpage would give the answer interview was looking for :

"The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed. "

So if you pass any pointer other than the one returned by malloc, the behaviour is undefined.

- dharmendra rana August 13, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More