Solved

Mark-sweel algorithm

Posted on 2006-07-13
20
319 Views
Last Modified: 2010-04-22
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
0
Comment
Question by:mmadhuso
  • 7
  • 6
  • 5
20 Comments
 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
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
0
 

Author Comment

by:mmadhuso
Comment Utility
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
0
 
LVL 34

Accepted Solution

by:
Duncan Roe earned 75 total points
Comment Utility
I'm not aware of a free tool. IBM / Rational purify instruments built code - you might have to rebuild the app (I assume you have source) but not modify the source itself.
http://www-128.ibm.com/developerworks//rational/library/05/r-3120/?ca=dgr-lnxw06Purify4Linux
0
 
LVL 34

Expert Comment

by:Duncan Roe
Comment Utility
Google for purify turns up lots of stuff - some free. Give it a try
0
 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
>> 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

0
 

Author Comment

by:mmadhuso
Comment Utility
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
0
 
LVL 34

Expert Comment

by:Duncan Roe
Comment Utility
You have to find the leaks and fix them. There is no other way.
0
 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
[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
0
 

Author Comment

by:mmadhuso
Comment Utility
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
 
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
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
0
 

Author Comment

by:mmadhuso
Comment Utility
>>>>>>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
0
 
LVL 34

Expert Comment

by:Duncan Roe
Comment Utility
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.
0
 
LVL 34

Expert Comment

by:Duncan Roe
Comment Utility
Better - make xxmalloc() be a macro so you don't lose line number information (when you run purify or whatever)
0
 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
>> 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

0
 

Author Comment

by:mmadhuso
Comment Utility
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
0
 
LVL 8

Expert Comment

by:manish_regmi
Comment Utility
>> 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
0
 

Author Comment

by:mmadhuso
Comment Utility
>> 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 !!!!!!!!!!
0
 
LVL 8

Assisted Solution

by:manish_regmi
manish_regmi earned 75 total points
Comment Utility
as i have already said it is not possible until it is compiled with garbage collection.

you cannot Free or do anythning to the memory used by other process unless you write some kernel mode code. Something like OOM killer in linux. But it also terminates the process.

regards
Manish Regmi
0

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

The purpose of this article is to fix the unknown display problem in Linux Mint operating system. After installing the OS if you see Display monitor is not recognized then we can install "MESA" utilities to fix this problem or we can install additio…
The purpose of this article is to demonstrate how we can upgrade Python from version 2.7.6 to Python 2.7.10 on the Linux Mint operating system. I am using an Oracle Virtual Box where I have installed Linux Mint operating system version 17.2. Once yo…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now