?
Solved

Mark-sweel algorithm

Posted on 2006-07-13
20
Medium Priority
?
328 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 35

Accepted Solution

by:
Duncan Roe earned 300 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
Get free NFR key for Veeam Availability Suite 9.5

Veeam is happy to provide a free NFR license (1 year, 2 sockets) to all certified IT Pros. The license allows for the non-production use of Veeam Availability Suite v9.5 in your home lab, without any feature limitations. It works for both VMware and Hyper-V environments

 
LVL 35

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 35

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 35

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 35

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 300 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

Get free NFR key for Veeam Availability Suite 9.5

Veeam is happy to provide a free NFR license (1 year, 2 sockets) to all certified IT Pros. The license allows for the non-production use of Veeam Availability Suite v9.5 in your home lab, without any feature limitations. It works for both VMware and Hyper-V environments

Question has a verified solution.

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

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…
Sometimes it takes a new vantage point, apart from our everyday security practices, to truly see our Active Directory (AD) vulnerabilities. We get used to implementing the same techniques and checking the same areas for a breach. This pattern can re…
In this video, Percona Solution Engineer Dimitri Vanoverbeke discusses why you want to use at least three nodes in a database cluster. To discuss how Percona Consulting can help with your design and architecture needs for your database and infras…
Suggested Courses

777 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