Chasing bugs in the Cache - How it all works

[IanB]

Dear all,

I have been plagued for a long time by random crashes when executing complicated scripts with animate, so this weekend I decided to find it.

Finding the problem exposed an ickyness in the memory managment of Avisynth. I thought it might be worth documenting what I have found.

How the Cache works
New VideoFrameBuffer's when created end up on 2 separate linked lists, 1 globally managed by class "LinkedVideoFrameBuffer" (avisynth.cpp) and another managed by many single instances of class "Cache" (cache.cpp). (I have added "this" (objects address) to all the Cache debug messages to make it more obvious what is happening.)

Each Cache object is automaticly inserted after every filter and add each returned VideoFrameBuffer to a linked list (CachedVideoFrame) in an LRU manner, a stale copy of an oldest frame is reused to hold the current VideoFrameBuffer, if none are stale then a new CachedVideoFrame is created. CachedVideoFrames are never deleted, the VideoFrameBuffer they manage may however become stale.

As each VideoFrameBuffer is initially created it is added by class LinkedVideoFrameBuffer to its linked list also in an LRU manner. Note :- this linked list is NOT updated by using or modifying the VideoFrameBuffer as in "Cache".

VideoFrameBuffer's are newly created until "memory_used" exceeds "memory_max", This is "Plan A". (memory_max is initially the max of 16Mb or 0.25 * Available Memory. It can be modified with SetMemoryMax() between current memory usage and 5MB less than Available Memory)

When "memory_used" exceeds "memory_max", "Plan B" is used for new VideoFrameBuffer's. This involves scanning the list in reverse order for an unlocked buffer exactly the right size. If selected the buffer is moved to the head of the list. Unfortunatly this list is in the order created not order used.

If no unlocked, exact size buffer is found new VideoFrameBuffer's are created, as in "Plan A", this is "Plan D" and is used until "memory_used" exceeds "memory_max" by 25%. When this happens "Plan C" is used, this involves discarding all of the currently unlocked buffers (Effectivly all of the cache).

This is where my problem occured. There is no indication to the "Cache" objects that the data buffer in the VideoFrameBuffer has been released, so with moderatly complicated recursive scripts "Cache" objects attempt to use missing data buffers. By incrementing the "sequence_number" in the destructor ~VideoFrameBuffer, "Cache" now knows its VideoFrameBuffer's are invalid and doesn't crash.

Food for thought
In the current CVS version along with the fix, I have remarked "Plan B" out and changed "Plan C" to only delete enough buffers so that "memory_used" is just less than "memory_max", so the cache floats between 100% and 125% of "memory_max". Initial testing shows a marked improvement in cache performance for complicated scripts and an immeasurable change for simple scripts. -- Some testing please guys.

What is really needed is to let the individual "Cache" objects influence the global "LinkedVideoFrameBuffer" object so true LRU performace can be obtained. I can do it easily with a small change to avisynth.h but because this small change would require all pluggins to be recompiled it is unacceptable.

Anybody have a bright idea of how to hook this together without upsetting avisynth.h?

IanB

[Bidoche]

This is where my problem occured. There is no indication to the "Cache" objects that the data buffer in the VideoFrameBuffer has been released, so with moderatly complicated recursive scripts "Cache" objects attempt to use missing data buffers.Really ?
I would have though such an obvious pb would have been considered.


Anybody have a bright idea of how to hook this together without upsetting avisynth.h?I don't.
After all, my intitial motivation for starting 3.0 was that I didn't want to even try fixing 2.x. ( There are more bugs than that )

So just give up and give me an hand on 3.0 :p
Dont let yourself be exposed too long to C code, some never make it back... ;)

I have Cache heuristics who could help some tuning too...

[IanB]

Bidoche,

Well seeing it took most of the weekend to find and how hard it is to reproduce and the fix was only 1 line of code, I would hardly call it obvious.:D

I've just cvs'd down a copy of the 3.0 branch, looks like it's .NET :scared: I'll take a propper look tonight. Also no "avisynth.h" :confused: Looks like I got some readin' to do.

(Think VC6 and GCC)
IanB

[Bidoche]

Originally posted by IanB
Well seeing it took most of the weekend to find and how hard it is to reproduce and the fix was only 1 line of code, I would hardly call it obvious.:DI am not calling the fix obvious, but the problem.
Figuring out that deleting things in use elsewhere is a bad idea is not too hard.
My guess is the original coder didn't knew they were. :p

I've just cvs'd down a copy of the 3.0 branch, looks like it's .NET :scared: I'll take a propper look tonight. Also no "avisynth.h" :confused: Looks like I got some readin' to do.I made more or less one file per class, and so to avoid being overwhelmed by them, I organized them into folders.

The headers corresponding to avisynth.h (more or less) are :src/core/clip.h
src/core/colorspace.h
src/core/videoinfo.h
src/core/videoframe.h
src/core/runtime_environment.h
The smart pointers are now provided by boost (see typedefs in src/core/forward.h)
And AVSValue is a parser detail you probably don't need to know about.

(Think VC6 and GCC)3.0 won't compile on VC6 (not the parser at least).
It will on gcc though. (proper version, proper switchs)
You may want to come on #avisynth@freenode on IRC for explanations if you do want to try compiling.

[sh0dan]

@IanB: Great work! It's always nice to have other eyes on the bugs I've created in the last year! :D

I'll be putting out a CVS binary with all your latest fixes soon!

[Richard Berg]

@IanB - who are you and what are you doing to our precious bugs? ;) ;)

Great to have you on board. I obviously haven't done much useful lately and probably won't be able to anytime soon.

[d'Oursse]

Originally posted by Bidoche

Dont let yourself be exposed too long to C code, some never make it back... ;)

who's the guy you have in mind ? :D

[WarpEnterprises]

IanB, maybe you can think of an answer to a related problem:

Is it possible that the memorymax-functions or some other calculations in the cache system overflow on systems with >=1GB RAM?

Look here (http://forum.doom9.org/showthread.php?s=&postid=514662#post514662) for some problems which strongly looks like that.

[yaz]

i'm just in the beginning of the tests w/140704 i promised but i can proudly announce that now i'm able to produce 'out of memory'-s too :-( (it peels windows down to the bones so crash is somtimes system-wise) f... i'm about to give it up. i'm too small for this.
the bests
y

[Leak]

Originally posted by WarpEnterprises
IanB, maybe you can think of an answer to a related problem:

Is it possible that the memorymax-functions or some other calculations in the cache system overflow on systems with >=1GB RAM?

Look here (http://forum.doom9.org/showthread.php?s=&postid=514662#post514662) for some problems which strongly looks like that.

Actually, I was doing some tests today trying out a plugin I'm just working on, and when I was encoding a 24 minutes episode halfway through VirtualDubMod just disappeared on me. Well, a while after starting the job a second time I took a look at Process Explorer's output and noticed that VirtualDubMod's virtual size was over 1.4GB - okay, so this is just the address space the application takes up and not really the memory it uses, but I guess it's what tore VDubMod down after reaching the 2GB mark - IIRC that's the limit for each application's address space (unless you do some extra work to get it to give you 3GB)...

I was running a CVS build of AviSynth that I made the other day to test my Visual Studio setup, but then I installed the 140704 and 120704 builds and the same thing happened - but using the 170604 build VDubMod's virtual size stayed at a constant 265MB *and* I was able to successfully finish the encode, so I'd hazard a guess it's some of the cache changes that started this, and I don't think it has anything to do with the actual amount of memory installed in the machine.

np: Radiohead - Exit Music (For A Film) (OK Computer)

[IanB]

@WarpEnterprises,

> systems with >=1GB RAM

Yep, the code she's a bit stuffed. Very definitly above 1.6GB, probably even lower.

Relevant extracts from avisynth.cpp
int memory_max, memory_used;
...
ScriptEnvironment::ScriptEnvironment() : ... {
MEMORYSTATUS memstatus;
GlobalMemoryStatus(&memstatus);
// Minimum 16MB, otherwise available physical memory/4, no maximum[
memory_max = max(memstatus.dwAvailPhys / 4,16*1024*1024);
...
int ScriptEnvironment::SetMemoryMax(int mem) {
MEMORYSTATUS memstatus;
GlobalMemoryStatus(&memstatus);
memory_max = min(max(memory_used,mem*1024*1024),memory_used+memstatus.dwAvailPhys-5*1024*1024);
return memory_max/(1024*1024);
// Note return value shows what happened in a script!
}
...
LinkedVideoFrameBuffer* ScriptEnvironment::GetFrameBuffer2(int size) {
// Plan A: are we below our memory usage? If so, allocate a new buffer
if (memory_used + size < memory_max)
return NewFrameBuffer(size);
...
// Plan B: look for an existing buffer of the appropriate size
... Currently disabled (It was scan the list looking for the first free same size buffer)
// Plan C:
// Before we allocate a new frame, check our memory usage,
// and perhaps delete some unreferenced frames.

if (memory_used > memory_max + (memory_max/4) ) { // More than 25% above allowed usage?
...
// Plan D: allocate a new buffer, regardless of current memory usage
return NewFrameBuffer(size);In the interim I'll make some repairs and put back "Plan B", "Plan C" seems to still have some problems. At least it won't be any worse than 2.54.

I am still pondering how best to have Frame Buffers managed on an LRU basis, I think it had better wait until 2.56.

IanB