146532 - Improve nsRecyclingAllocator

Status: RESOLVED FIXED

(Core :: XPCOM, defect, P3)

Description

[Suresh Duddi (gone)]

We do a search for the right size for both malloc and free. Darin had this idea
that if we store the bucket index as the first int (and increase size of
allocation by an int) we wont need to search for the bucket when free.

Comment 1

[Suresh Duddi (gone)]

here is what I plan to do:
- maintain a free list. This would eliminate the need for the bucket array
- maintain size along with the allocaiton (increases allocation by extra int)

Comment 2

[Suresh Duddi (gone)]

Also nsIMemory wrapping of nsRecyclingAllocator

Comment 3

[Suresh Duddi (gone)]

Attachment: v1.0 new nsrecyclingallocator

Uses malloc style bookkeeping:
- freelist. needs use of locks :-(
- 1 int overhead on each allocation for storing size
- much simpler code

Comment 4

[Suresh Duddi (gone)]

Darin had a nice idea again:

The freelist searching might cause all free blocks to be swapped into memory
just to check their sizes. Instead use an array of meta blocks (size, nextptr)
linked together as the freelist. This will keep all searching for free block in
confined memory.

Will do that and update patch. Thanks darin.

Comment 5

[Suresh Duddi (gone)]

Attachment: v2.0 using an array of meta blocks for freelist

Comment 6

[Suresh Duddi (gone)]

Attachment: v 3.0 (after darin's review)

Makes sure we dont rely on structure alignment.

Comment 7

[Suresh Duddi (gone)]

Comment on attachment 86134 [details] [diff] [review]
v 3.0 (after darin's review)

sr=darin
(Thanks for the review darin)

Comment 8

[Suresh Duddi (gone)]

Ccing dougt for review.

Comment 9

[Doug Turner (:dougt)]

Comment on attachment 86134 [details] [diff] [review]
v 3.0 (after darin's review)

Any data collected with these changes?	Do we curve memory allocation?

Comments:

MUST FIX
===============================

Test to see if "mLock = PR_NewLock();" is successful.

I believe that you have to protect against a null "delete []" in this case:
+    delete [] mBlocks;

You also want to null check this:
+    PR_DestroyLock(mLock);

I think that you have a unprotected critical section between FindFreeBlock and
FreeUnusedBuckets on the variable mFreeList.  Shouldn't you enter the mLock
prior to checking mFreeList against null?  I think that if the UI thread is
running FreeUnusedBuckets and you call Malloc (which calls FindFreeBlock) you
will race since FreeUnusedBuckets null's mFreeList.  You also have this race
condition in AddToFreeList, 

In FindFreeBlock, I do not think that there is any need to break, just return:
+
+	     break;
+	 }

Do you want to assert if NS_NewTimer does fail?  You say it is alright, but I
think that we wanna know when this situation does happen.  Right?

SUGGESTIONS
===============================

struct's?  Come on, this is C++; classes please. :-)  (this comment was
directed at me once not so long ago.... just sharing :-p)

Do you want to expand this warning to everyone?  I think it would be important.
 Also, why are you decrementing mNAllocated only in your debug code?
+#ifdef DEBUG_dp
+	 // Warn if we are failing over to malloc/free and not storing it
+	 // This says we have a misdesigned memory pool. The intent was
+	 // once the pool was full, we would never fail over to calloc.
+	 printf("nsRecyclingAllocator(%s) FAILOVER 0x%p (%d) - %d allocations,
%d max\n",
+		mId, (char *)ptr, block->bytes, mNAllocated, mMaxBlocks);
+	 mNAllocated--;
 #endif

Lets be consistent with naming, please nsRecyclingAllocator to the Malloc
scope. 
+    if (size < 0)
+	 return NULL;
+    else
+	 return Malloc(size, PR_FALSE);

Do a NS_STATIC_CAST so make people reading it more comfortable.

+    // It is ok to do this. We are the implementor of the class.
+    *recyclingAllocator_r = (nsIMemory *)allocator;

What is this naming convention (the trailing _r)?
recyclingAllocator_r

Like we need another export, can we do anything about it?
+NS_COM nsresult
+NS_NewRecyclingAllocator(nsIMemory* *recyclingAllocator_r, PRUint32 nbucket,
PRUint32 recycleAfter = NS_DEFAULT_RECYCLE_TIMEOUT,
+			  const char *id = NULL);

bytes is a poor name.  
+    struct Block {
+      PRUint32 bytes;
+    };

QUESTIONS
===============================
How long do you think that the free list will get?  I am concerned about the
cost of the linear search.

Comment 10

[Suresh Duddi (gone)]

> Any data collected with these changes? Do we curve memory
> allocation?

We dont. This is just a reimplementation of the current ds to hold allocations.

Of course, it can be put to a lot of memory damange. So this question
should be answered before we let new clients use this (like the necko
buffer cache).

> Test to see if "mLock = PR_NewLock();" is successful.

Done.

> I believe that you have to protect against a null "delete []" in this case:
> +    delete [] mBlocks;

Done.

> You also want to null check this:
> +    PR_DestroyLock(mLock);

Done.

> I think that you have a unprotected critical section between FindFreeBlock and
> FreeUnusedBuckets on the variable mFreeList.

This is intentional. Here is my logic: we are checking if
(!mFreeList). Doing this check without locking can lead to
unpredictable results. YES. But the effect of the unpredictedness are
ok. here is why:

a) if the check returned NULL when there is stuff in freelist
  We would just end up reallocating.

b) if the check returned nonNULL when our freelist is emptry
  This is the more likely and dangerous case. The code for
  FindFreeBlock() will enter lock, while (null) and return null.

The reason why I chose to not enter lock for this check was that when
the allocator is full, we dont want to impose any more overhead than
we already are for failing over to malloc/free. Will add a comment to
this regard.

> In FindFreeBlock, I do not think that there is any need to break, just return:
> +
> +	     break;
> +	 }

I was trying to keep single entry single exit as a paradigm. I think
the code is a lot cleaner with the break. But then I know styles
differ. So let me know if you see more advantage the other way.

> Do you want to assert if NS_NewTimer does fail?  You say it is alright, but I
> think that we wanna know when this situation does happen.  Right?

Sure.

> SUGGESTIONS
> ===============================
> 
> struct's?  Come on, this is C++; classes please. :-)  (this comment was
> directed at me once not so long ago.... just sharing :-p)

:-) that is funny. Stroustroup sez use structs for container classes.

> Do you want to expand this warning to everyone?  I think it would be important.
>  Also, why are you decrementing mNAllocated only in your debug code?

mNAllocated is only in debug code. Its use is only to issue this
warning. I am torn about this. I would like to give this warning for
all but then I would have to make mNAllocated in debug. That means
structure size will be different debug vs optimized. <sigh!>

I think the warning is better there than not. So I will do this.

> Lets be consistent with naming, please nsRecyclingAllocator to the Malloc
> scope. 
> +    if (size < 0)
> +	 return NULL;
> +    else
> +	 return Malloc(size, PR_FALSE);

Hey, nsRecyclingAllocatorImpl derives from nsRecyclingAllocator and
the scope exist for Free because there is a name clash. Anyway I am
not too particular about this. I will do the scoping.

> Do a NS_STATIC_CAST so make people reading it more comfortable.

Sure.

> What is this naming convention (the trailing _r)?

Darin asked the same thing. I will change it.

> Like we need another export, can we do anything about it?
> +NS_COM nsresult
> +NS_NewRecyclingAllocator(nsIMemory* *recyclingAllocator_r, PRUint32 nbucket,
> PRUint32 recycleAfter = NS_DEFAULT_RECYCLE_TIMEOUT,
> +	
	  const char *id = NULL);

This is also interesting. The other option I have is to make a progid,
factory etc. Guess I will do that.

> bytes is a poor name.  

what do you mean! bytes is a great name. It says two things: it is a
size and that the storage unit is in bytes.

> QUESTIONS
> ===============================
> How long do you think that the free list will get?  I am concerned about the
> cost of the linear search.  

One of the reasons we did this patch was to improve this. Earlier we
would search all buckets until we found the right match. Buckets
werent stored ordered and allocated/free were all mixed in
together. Now we are searching only the freelist and the freelist is
ordered by size.

So this would do better than what we used to have. Linear search is
fine because the number of buckets we market this allocator for are
not more than 25

Comment 11

[Darin Fisher]

delete[] NULL; // is completely valid C++ FWIW.

what's wrong with NS_NewRecyclingAllocator?  that's how we do it elsewhere? 
mozilla links with libxpcom, so what's the big deal with adding entry points
like this?  if we need to expose this object to embedders than we can look into
adding an entry to the component registry, but otherwise... why the extra overhead?

bah!  i don't buy the argument to use |class| over |struct|... there is no real
difference.

Comment 12

[Suresh Duddi (gone)]

Attachment: V 4.0 With most of dougt's comments

I did everything I from my reply except for making a progid, cid way of
creating this.

Comment 13

[Suresh Duddi (gone)]

Attachment: v 5.0 Using cid/contractid for creation of nsIRecyclingAllocator object

I did the cid/contractid way of creating these objects and ditched the
NS_NewRecyclingAllocator() stuff.

Darin, since these objects arent going to be created too frequently, there
isn't much of a need to export a new symbol. I think the std xpcom way is fine.


Darin/dougt : sr=/r=

Comment 14

[Darin Fisher]

Comment on attachment 86442 [details] [diff] [review]
v 5.0 Using cid/contractid for creation of nsIRecyclingAllocator object

sr=darin

Comment 15

[Doug Turner (:dougt)]

Comment on attachment 86442 [details] [diff] [review]
v 5.0 Using cid/contractid for creation of nsIRecyclingAllocator object

r=dougt

Comment 16

[Cathleen]

win98, 200MHz/112MB

Pageload test:
----------------
base-line build: 2561ms 2522ms 2539ms 2538ms
recycler build:  2490ms 2536ms 2527ms 2533ms

Memory:
----------------
base-line build:  data - 19,948kb  20,112kb  20,240kb
                  code - 11,116kb  11,112kb  11,112kb

recycler build:   data - 19,120kb  19,232kb  19,836kb
                  code - 11,124kb  11,528kb  11,120kb

Comment 17

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

I just checked in two attempted bustage fixes for this patch:
 * a change in nsRecyclingAllocator.h to make the nested struct |BlockStoreNode|
a |friend| of |nsRecyclingAllocator| so that it could access the nested struct
|Block|.  This broke HP and OS/2.  (I took out mkaply's ifdef of the protected
that he checked in a few minutes earlier.)
 * a change in nsRecyclingAllocator.cpp to remove two extraneous |inline|s for
functions that clearly couldn't be |inline| and that I doubt you would want to
inline.  (If you really want them inline, put them in the header file.)  This
was needed for Sun WorkShop.

Comment 18

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

... and a third, for BeOS, which didn't like the generic factory constructor as
a member variable (perhaps since it wasn't NS_METHOD, or maybe some other
reason).  I moved it to nsXPComInit.cpp like all the rest.

Comment 19

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

And while I'm on the subject, why is nsRecyclingAllocator::Init virtual?  I
don't think it should be.  (gcc warns, because the destructor isn't.)

Comment 20

[Suresh Duddi (gone)]

Good point. nsRecyclingAllocator::Init() was designed to be non-virtual.
nsRecycleAllocatorImpl::Init is the virtual one. I will fix that. The NS_IMETHOD
macro misuse caused it to be so.

Thanks for fixing the other commercial bustages (as usual) stud.

One question: Why can those two functions not be inlined ? They are used only
once and are defined in the same cpp file.

Comment 21

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Some compilers are still one-pass.  (C and C++ allow that.)  So, you should
always have the inline functions before their use.

Comment 22

[Suresh Duddi (gone)]

made nsRecyclingAllocator::Init() non virtual. Fixed on trunk.

Comment 23

[Jay Patel [:jay]]

Talkback data shows a new crash due to changes related to DP's checkin on July 1
in nsRecyclingAllocator.cpp.  The crashes started with MozillaTrunk builds on
July 2.  Here is the stack:

nsRecyclingAllocator::AddToFreeList
[c:/builds/seamonkey/mozilla/xpcom/ds/nsRecyclingAllocator.cpp line 352]
nsRecyclingAllocator::Free
[c:/builds/seamonkey/mozilla/xpcom/ds/nsRecyclingAllocator.cpp line 229]
zlibFree [c:/builds/seamonkey/mozilla/modules/libjar/nsZipArchive.cpp line 415]
inflate_codes_free [c:/builds/seamonkey/mozilla/modules/zlib/src/infcodes.c line
251]
inflate_blocks [c:/builds/seamonkey/mozilla/modules/zlib/src/infblock.c line 344]
inflate [c:/builds/seamonkey/mozilla/modules/zlib/src/inflate.c line 222]
nsZipArchive::InflateItem
[c:/builds/seamonkey/mozilla/modules/libjar/nsZipArchive.cpp line 1403]
nsZipArchive::ReadInit
[c:/builds/seamonkey/mozilla/modules/libjar/nsZipArchive.cpp line 594]
nsJARInputStream::Init
[c:/builds/seamonkey/mozilla/modules/libjar/nsJARInputStream.cpp line 108]
nsJAR::GetInputStream [c:/builds/seamonkey/mozilla/modules/libjar/nsJAR.cpp line
346]
nsJARChannel::GetInputStream
[c:/builds/seamonkey/mozilla/netwerk/protocol/jar/src/nsJARChannel.cpp line 681]
nsFileTransport::Process
[c:/builds/seamonkey/mozilla/netwerk/base/src/nsFileTransport.cpp line 693]

Source File : c:/builds/seamonkey/mozilla/xpcom/ds/nsRecyclingAllocator.cpp line
: 352

Added zt4newcrash keyword (Congratulations!  You are the owner of the first ever
zt4newcrash bug). Please look at the keywords definition list for a description
of what zt4newcrash means.

Comment 24

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

A separate bug has already been filed for the crash (bug 156320), and this bug
remains fixed, since the crash is a separate bug..

Comment 25

[Shanmugavelu Shanmuganathan (gone)]

I am getting tons of Unaligned access messages on a Tru64 UNIX, 
which is a 64 bit  machine. 

I found the following causes the wrong bounday alignment.

#define DATA(block) ((void *)(((char *)block) + NS_ALLOCATOR_OVERHEAD_BYTES))

where NS_ALLOCATOR_OVERHEAD_BYTES is defined as 

#define NS_ALLOCATOR_OVERHEAD_BYTES (sizeof(Block)) // bytes
 
while Block is defined as 

class NS_COM nsRecyclingAllocator {
 protected:
    struct Block {
      PRUint32 bytes;
    };
 
This (definition of bytes ) forces the memory to be aligned on  a 4-byte 
boundary. While Tru64 UNIX needs this to be on a 8 byte boundary.  
Hence I suggest we ifdef the change to OSF1 as follows.
 
#if defined(OSF1)
long bytes;
#endif

Comment 26

[Suresh Duddi (gone)]

Sounds ok to me. Would you like to do that ? I can r= it.

Comment 27

[Shanmugavelu Shanmuganathan (gone)]

I don't have cvs commit access. 
May I request you to checkin this change.

Comment 28

[Suresh Duddi (gone)]

Ok.

Comment 29

[Suresh Duddi (gone)]

Attachment: 8 byte alignment

Comment 30

[Suresh Duddi (gone)]

Attachment: 8 byte align for all platforms

Brendan suggested 8 byte align for all platforms or better make it a parameter.
I am going to easy route and making it for all platforms.

Comment 31

[ly nguyen]

just spoke with dougt, the alignment patch has not been checked in. dougt is
going to look through dp's bugs and reassess. in addition, talkback is not
showing this stack signature for trunk, branch, m11a, m11b, nor m10 under linux
anymore.

Comment 32

[Shanmugavelu Shanmuganathan (gone)]

The alignment issue, with 64 bit OS, that I reported in comment #25 is being
taken care by the bug# 160535. Since that is the only issue that made this
problem reopen, we can close this bug.

Comment 33

[Shiva Thirumazhusai]

Any new owner for this bug ? 

Comment 34

[Doug Turner (:dougt)]

fine by me.  reopen if there are any outstanding issue.... or better yet....
open a new bug.