Link to home
Start Free TrialLog in
Avatar of mmadhuso
mmadhuso

asked on

Mark-sweel algorithm

Hi Expert

Can any one tell me what is  Mark-Sweep algorithm?
I need to detect and liberate memory leaks in a Linux system,

Can i get more information in implementing this algorithm
Avatar of manish_regmi
manish_regmi

There is already a garbage collector for linux. Boehm Gc comes with gcc.
you can see gcc source code for more info.

http://en.wikipedia.org/wiki/Boehm_garbage_collector

anyway here is some info for mark-sweep:
http://www.brpreiss.com/books/opus5/html/page424.html

you can find research papers on google scholar
http://scholar.google.com/scholar?q=mark+sweep+algorithm&ie=UTF-8&oe=UTF-8&hl=en&btnG=Search

regards
Manish Regmi
Avatar of mmadhuso

ASKER

Hi Manish

Thanks a lot for the links
This  algo modifies the source code by replacing malloc with GC_MALLOC , and then identifies the leaks

Is there some thing that does not take the source code ,but uses obj code  or  reads from the heap
for eg   suspend a process and then identify whether is a mem leak in it

please let me know
ASKER CERTIFIED SOLUTION
Avatar of Duncan Roe
Duncan Roe
Flag of Australia image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Google for purify turns up lots of stuff - some free. Give it a try
>> Is there some thing that does not take the source code ,but uses obj code  or  reads from the heap
>> for eg   suspend a process and then identify whether is a mem leak in it

have you tried valgrind. it does exactly that. It is one of the best tool in linux to detect memory leak.


To test your new GC, just call your function instead of malloc and free.

regards
Manish Regmi

Hi Manish
[1]  I am using Valgrind , its  good, It runs the exe and checks for the leak,This is specific to a process or a program
This tool is particularly not usefull for a process running infinitely and allocating memory ,as it executes the process ,amd waits
for it to terminate & then looks for memory leak
How do i tackle some thing like this   not terminating program
int *a;
while(1)
{  a=(int*)malloc((10000*(sizeof(int))));  }

[2] I want is some thing like a Garbage Collector , i.e randomly checks the heap for memory leaks rather than for a specific process
This is helpful for process like the one mentioned above

please do help me
You have to find the leaks and fix them. There is no other way.
[1]. Doesn't seem posible to me. When will GC run?


[2] What do you mean specfic process?
The GC can only collect from the own invoking process. Instead of allocation with malloc just allocate with GC's equivalent. You need not worry about free.
If you want to see how one works or want to implement one. See the sources of Boehm GC.
http://www.hpl.hp.com/personal/Hans_Boehm/gc/

regards
Manish Regmi
Manish i am still in  1 st part

[1 ]  say we write this piece of code and compile and get the exe
the syntax of   valgrin is   ----  valgrind  -option <exe name >
now i say   valgrind  -v <exe name >
 it runs the executes the exe and then detects the memory leaks in it  

but in the case of infinite lpop where the program wont terminate how will valgrind work

thanks
 
it cant until it terminates. In this case you need to check it manually.

but why does your program have infinite loop. It has to be a terminating condition.

regards
Manish Regmi
>>>>>>but why does your program have infinite loop. It has to be a terminating condition

I mean its a buggy program and it is not written by me.

once we find the memory leak detected by "valgrind"  can we remove the leaks , rather remove those bugs
from the obj code or exe without modifing the code ,

In run time  susped the process and detect the leak , fix it and resume it

this is my main purpose

am i clear
Yes you make yourself clear but I have to say I think you are mistaken. Sure it's someone else's program and they're not "your" bugs, but you can still fix them.
Unless you have some absolute business reason why you can't modify the code, I say fix it.
Some good practices: write an xxfree(void **) wrapper to free() which sets the pointer to NULL after calling free(). Replace *all* occurrences of free() with xxfree(). Enusre each function has a single return statement maximum including implied return at function end Declare all pointers initialised to NULL. On leaving a function, xxfree() any non-NULL pointers that are going out of scope. Write xxmalloc() and xxcalloc(void*) that xxfree() target if non_null also.
Better - make xxmalloc() be a macro so you don't lose line number information (when you run purify or whatever)
>> once we find the memory leak detected by "valgrind"  can we remove the leaks , rather remove those bugs
>> from the obj code or exe without modifing the code ,

i am a bit curious. Even if you find the leaks how will you remove them from executable file. you said you dont have sources.
If you ask me i would say not possible.


regards
Manish Regmi

Hi Manish

As i said i have processes not programs , so i only know that the process is running

Then how do Garbage Collectors work ? they say they reclaim the un used memory
how is this possible if they dont modify the code . I want to implement some thing similar
to a Garbage Collector
>> As i said i have processes not programs , so i only know that the process is running
I don't think i understood.

>> Then how do Garbage Collectors work ?  
You need to compile and link your code with compiler and library that supports Garbage collector.

>> how is this possible if they don't modify the code .
Because they compile/link the code with library/compiler implementing garbage collector
valgrind in entirely different thing. It is like a emulator where the valgrind intercepts the code not the linux kernel.

to implement your own GC, please see Boehm GC implementation.

In short, If your program is not compiled with garbage collector support, you cannot enforce later. Valgrind like programs will be your only choice.


Regards
Manish Regmi
>> As i said i have processes not programs , so i only know that the process is running...
>>>>I don't think i understood.

I have a list of processes running in the system. I realise that the system is running out of
memory and i need to reclaim some part of memory.
I suspect a process and suspend it , then i run a Garbage Collector to check if there is any leak as such.
If there is leak then i need to release memory or reclaim the memory back to the system and resume the
process.

Now I have the suspected process and i need to contine from there on ,
I dont want to kill that processs !!!!!!!!!!
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial