[interfacekit] Re: BBlockCache bug

Sorry to reply to my own email but don't forget to uncomment 
BlockCache.cpp from current/src/kits/support/support.src.  If you don't 
do that, you will not build BBlockCache into libopenbeos.so.

> So, I have the tests done now.  You can find them here:
> 
> http://www.magma.ca/~jrand/BBlockCacheTests.zip
> 
> I don't have CVS access so if someone can volunteer to check this in, 
> I 
> would appreciate it.
> 
> However, there is a minor issue.  Marcus has checked in a linked list 
> implementation which looks very good and much better than the one 
> which 
> was there before.  But, there is a deviation in his implementation 
> from 
> Be's.
> 
> Imagine this scenario with a 4 block cache.  The blocks on the cache 
> are A, B, C, D.  If a caller gets five blocks from the cache, the 
> following is returned: A, B, C, D, E.  The first four come from the 
> cache and the fifth (E) is allocated dynamically to satisfy the 
> caller.  
> What happens if the caller then repeatedly Save()'s E and then 
> performs 
> a Get() again over
> and over again?
> 
> In Be's implementation, when E is Save()'ed, E is placed on the list 
> of 
> free blocks in the cache.  Even though E was not in the cache 
> initially, since it is the right size it isn't freed and just put in 
> the cache for a caller to get later.  So, if E is Save()'ed and 
> gotten 
> again repeatedly, Be's implementation does this:
>   - put E on the cache
>   - take E off the cache and pass back to the caller
>   - put E on the cache
>   - etc.
> 
> This means that Be intends that the cache will hold up to 4 blocks in 
> this case but the total number of blocks on the cache plus those 
> handed 
> out through the Get() method may exceed 4 perhaps by a great deal.
> 
> But in Marcus' implementation, if you Get() 5 elements from a 4 
> element 
> cache and then return one, he will not start putting elements back 
> into 
> the cache right away.  When the 5th element is gotten from the cache, 
> it tracks that there is an "excess block" oustanding.  While excess 
> blocks are outstanding, any attempt to return one of them to the 
> cache 
> will actually result in them being freed.  So, with Marcus' 
> implementation, the following would occur if E is Save()'ed and 
> gotten 
> again repeatedly:
>   - E is freed
>   - a new block (possibly the same as E) is allocated
>   - the block is freed again
>   - etc.
> 
> Marcus' implementation guarantees that there will not be any blocks 
> in 
> the cache if there are 4 or more blocks returned by Get() which are 
> still outstanding.  Be's implementation will be faster in this case 
> by 
> avoiding the calls to the memory allocator.  Plus, my tests detect 
> this 
> difference in behaviour and will fail on Marcus' current 
> implementation.
> 
> In the zip file, I have two updated implementations of BBlockCache:
>   - src/kits/support/BBlockCache.new and headers/os/support/
> BBlockCache.new: This is a minor modification of Marcus' 
> implementation 
> based on linked lists to match Be's behaviour when returning blocks 
> to 
> an empty cache.
> 
>   - src/kits/support/BBlockCache.jer and headers/os/support/
> BBlockCache.jer: This is an implementation which I expect is 99.9% 
> the 
> same as Be's.  Its Get() and Save() methods are O(1) and the cache is 
> implemented as an array of (void *)'s.
> 
> Both implementations pass the tests with very similar performance.  
> Either is fine and I try to be as "egoless" as possible about these 
> things.  Truth be known, Marcus' implementation does have some great 
> debugging features like setting and checking magic numbers in it 
> which 
> we should probably hold on to.
> 
> So, I am looking for someone to decide what should get checked in and 
> then do it for me.  Thanks!
> 
> > What one can do to optimize Save() is not to keep track of the used 
> > blocks. 
> > That way you simply check, whether the chunk of memory passed to 
> > Save() has 
> > the right size and, if so, add it to your stack of free blocks. If 
> > not, or if 
> > the cache has reached the maximal number of free blocks, the memory 
> > would 
> > simply be freed. That way both Get() and Save() are O(1).
> > 
> > CU, Ingo
> 
> --
> Jeremy Rand
> jrand@xxxxxxxx
>

Other related posts: