Hi Hemming, all, I'm not sure if this is still relevant to your work, but here are my two cents.
We're using KLEE (KleeNet) for testing sensornets and the memory usage turned out to be a big issue for us leading to ~40MB/s memory growth. The reason is simple: the main scheduler of a mote continuously polls it's processes/interfaces. These are small functions, but they still produce are large number of MemoryObject's in very short time which are never freed. Here is our workaround: 1. As Cristian said, MemoryObject's as shared between multiple states, hence, we need a refCount for each MO. 2. There two places where refCount needs to be increased by 1: - When a local MO is bound in state. - When a state is forked. Here, we increase the refCount in the copy constructor of the StackFrame ensuring that all local MO's throughout the complete state's stack are increased by 1. This is triggered by the default constructor of the ExecutionState class. 3. There is only one place where refCount needs to be decreased by 1: - When the stack frame is popped. If the refCount reaches 0 the MO can be safely deallocated via MemoryManager. MemoryManager first frees mo->address and then deletes mo. EXCEPTION: if a local memory object was marked to be symbolic (via klee_make_symbolic), freeing is a bad idea because the test generation will fail a the end of the KLEE run. processTestCase in Executor requires references to the MO's, therefore, we first check if a MO was made symbolic before deallocating it. The rest (see patch attached) is self-explanatory and can be applied to the current SVN HEAD. We ran a number of large scenarios (up to 100 Contiki nodes in a grid-like sensornet, memory consumption up to 40 GB of RAM) and the memory growth of the process was only influenced by the active and newly created states + their management information. Nonetheless, I cannot guarantee that our workaround covers all corner-cases an it is definitely not the most elegant one: 1. A pointer to the MemoryManager is exposed to the initial execution state via constructor in order to allow states to trigger the MO deallocation. 2. Both refCount and isMadeSymbolic are mutable attributes of the const MO. I guess this is not the best way to access and modify these, but there are also other attributes at the same place modified in the same fashion ;-) 3. Depending on the size of MOs in the tested program, iterating through the MO vector in the MemoryManager upon deallocation might be expensive. Still, I hope this can help people which have similar issues or maybe some of the "ideas" can be used in the "more robust heap allocation strategy" someday as pointed out by Daniel. Good luck, Raimondas -------------- next part -------------- A non-text attachment was scrubbed... Name: memory_object_reference_count.patch Type: application/octet-stream Size: 7344 bytes Desc: not available Url : http://keeda.Stanford.EDU/pipermail/klee-dev/attachments/20101202/327abd0d/attachment.obj -------------- next part -------------- On 01.04.2010, at 17:47, Cristian Zamfir wrote: > You need to make sure the MemoryObject is not shared between multiple > states before you can delete it, because KLEE uses CoW, therefore the > MemoryObjects are shared between states. > > There is currently a refCount for ObjectState, maybe one needs to be > added for MemoryObject too, sorry, I don't know more about that. > > Cristi > > On Thu, Apr 1, 2010 at 5:28 PM, Cristian Zamfir <cristian.zamfir at epfl.ch> > wrote: >> FWD, this may be interesting to a larger audience. >> Begin forwarded message: >> >> From: Heming Cui <heming at cs.columbia.edu> >> Date: April 1, 2010 5:23:55 PM GMT+02:00 >> To: Cristian Zamfir <cristian.zamfir at epfl.ch> >> Cc: <daniel at zuster.org>, <c.cadar at imperial.ac.uk>, Junfeng Yang >> <junfeng at cs.columbia.edu> >> Subject: Re: [klee-dev] A question about the memory usage of local variable >> of functions in klee (for llvm-2.6) >> >> Hi Cristian, >> Thanks so much for your reply. I have checked the code, two concerns >> are: >> First, do we need to delete the memory in the unbind() function after it >> is removed from the "objects"? I have checked that, if we do not "delete" >> here, then there are just MemoryObject construction functions called (for >> each function call to foo()) but no destruction functions are called. >> >> void AddressSpace::unbindObject(const MemoryObject *mo) { >> objects = objects.remove(mo); >> delete mo; // I added this >> line. >> } >> >> Second, do we need to free the "address" memory for the memory object in >> its destruction function? I have checked that even we delete the memory >> object explictly in the unbind() function as above, but we do not free() >> this "address", the memory usage problem still occur. >> >> MemoryObject::~MemoryObject() { >> if (address) free((void *)address); // I added this line. >> address = 0; // I added this line. >> } >> >> I have added these two places, and it seems that now the memory usage is >> restricted to about 2%. Do we have other approaches to solve the memory >> usage problem? Am I missing something? >> I am looking forward to your reply. >> >> 2010/4/1 Cristian Zamfir <cristian.zamfir at epfl.ch> >>> >>> Hi Heming, >>> >>> If you run the example with just the return and without local vars, you >>> should check in the assembly.ll to see if the call is not removed. >>> >>> Local variables are removed on function return, check >>> ExecutionState.cpp:112 >>> You can maybe check the # of bytes removed, there could be a bug. >>> >>> Cristi >>> >>> On Apr 1, 2010, at 5:33 AM, Heming Cui wrote: >>> >>>> Dear Daniel and Cristian, >>>> One more thing is, if I do not declare any local var at foo() and >>>> just return (as below), the memory usage is only about 1%. >>>> void foo() { >>>> return; >>>> } >>>> >>>> >>>> 2010/3/31 Heming Cui <heming at cs.columbia.edu> >>>> Dear Daniel and Cristian, >>>> I am Heming Cui, Prof. Junfeng Yang's student. May I ask you a >>>> question, please? Recently I was running klee with some long running >>>> programs and found a question about the memory usage of local variable of >>>> functions in klee. >>>> Please refer to the source code below (and also in the attachment). >>>> Foo() dedclares a function local var, and the main function calls fool() >>>> again and again. If I compile this code with llvm-gcc and run the bit code >>>> with klee, the memory usage increases to more than 90% as soon as the >>>> program starts and never drops. The memory in my machine is 2GB. If I >>>> compile this code with gcc and run it natively, and the memory usage is >>>> only >>>> 0.1% and never increases. >>>> If I change "int a[100000];" to be "int a;", the memory usage would >>>> increase to more than 90% after about 10 seconds of start, and never drops. >>>> It seems to me that we might need to unbind local vars in klee >>>> memory address space after a function exits? I am a little confused of this >>>> part, since if my program runs for a long time, this problem would happen >>>> and affect the speed. >>>> >>>> Memory usage of klee is 93.3%: >>>> PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND >>>> 3099 heming 20 0 1773m 469m 4 D 1.7 93.3 0:04.18 klee >>>> >>>> >>>> Source code (also attached): >>>> >>>> #include <stdio.h> >>>> void foo() { >>>> int a[100000]; >>>> return; >>>> } >>>> >>>> int main(int argc, char * argv[]) { >>>> while (1) { >>>> foo(); >>>> } >>>> >>>> return 0; >>>> } >>>> >>>> -- >>>> Regards, >>>> Heming Cui >>>> >>>> >>>> >>>> >>>> -- >>>> Regards, >>>> Heming Cui >>>> _______________________________________________ >>>> klee-dev mailing list >>>> klee-dev at keeda.stanford.edu >>>> http://keeda.Stanford.EDU/mailman/listinfo/klee-dev >>> >>> >> >> >> >> -- >> Regards, >> Heming Cui >> >> > _______________________________________________ > klee-dev mailing list > klee-dev at keeda.stanford.edu > http://keeda.Stanford.EDU/mailman/listinfo/klee-dev -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 4409 bytes Desc: not available Url : http://keeda.Stanford.EDU/pipermail/klee-dev/attachments/20101202/327abd0d/attachment.bin
