Solved

Mark-sweel algorithm

Posted on 2006-07-13
20
326 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 6
  • 5
20 Comments
 
LVL 8

Expert Comment

by:manish_regmi
ID: 17100465
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
ID: 17111952
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
ID: 17112855
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 34

Expert Comment

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

Expert Comment

by:manish_regmi
ID: 17113073
>> 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
ID: 17115504
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
ID: 17115891
You have to find the leaks and fix them. There is no other way.
0
 
LVL 8

Expert Comment

by:manish_regmi
ID: 17116258
[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
ID: 17116506
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
 
LVL 8

Expert Comment

by:manish_regmi
ID: 17116517
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
ID: 17117625
>>>>>>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
ID: 17118414
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
ID: 17118494
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
ID: 17119140
>> 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
ID: 17119471
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
ID: 17119535
>> 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
ID: 17122012
>> 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
ID: 17123047
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever been frustrated by having to click seven times in order to retrieve a small bit of information from the web, always the same seven clicks, scrolling down and down until you reach your target? When you know the benefits of the command l…
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…
Attackers love to prey on accounts that have privileges. Reducing privileged accounts and protecting privileged accounts therefore is paramount. Users, groups, and service accounts need to be protected to help protect the entire Active Directory …

737 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