Split an allocation policy into an allocator and a deallocator.

Split an allocation policy into an allocator and a deallocator.

This refactoring will make way for passing around a Zone directly into
methods that allocate from Zones.  Besides saving a TLS access in some
cases, we will later be able to decouple Zones from Isolates
completely -- a first step towards running parts of the crankshaft
pipeline concurrently without locking out the Isolate.

BUG=
TEST=

[danno, 2012-05-25 11:03:37]

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/list.h
File src/list.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/list.h#newcode52
src/list.h:52: typedef typename P::Alloc Allocator;
AllocationPolicy instead of P

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree-inl.h
File src/splay-tree-inl.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree-inl.h...
src/splay-tree-inl.h:37: template<typename Config, class P>
AllocatorPolicy, or Policy (P is not very descriptive). Also elsewhere in this
file.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h
File src/splay-tree.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:53: template <typename Config, class P>
AllocationPolicy

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:73: Deallocator deallocator = Deallocator())) {
Adding the deallocator here does something different than you think. In this
case, you cannot override the deallocator, since there is no way to pass it in a
call to delete. So either you want "return Deallocator().Delete(p), or you want
to put an "UNREACHABLE" here like you do later in the file.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:128: UNREACHABLE();
Why unreachable? Because nodes should only be allocated in Zones? Was the delete
operator never called before? I still don't see what it's a problem to
implemented this with Deallocator().Delete(p);

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:209: Deallocator deallocator_;
I don't think you ever need to store the Deallocator as a member. I think we
must be able to always call the Deallocator constructor with no arguments.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/v8.h
File src/v8.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/v8.h#newcode68
src/v8.h:68: #include "zone-inl.h"
What has changed that you need this extra include?

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone-inl.h
File src/zone-inl.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone-inl.h#newco...
src/zone-inl.h:115: // allocate ZoneLists and their elements in the current
Zone.
Does the comment apply to the following code?  I'm confused a bit.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone-inl.h#newco...
src/zone-inl.h:122: // De-allocation attempts are silently ignored.
This comment seems unrelated?

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone-inl.h#newco...
src/zone-inl.h:125: return List<T, ZoneAllocationPolicy>::operator new(size);
Why did you move this function?  And why does it need to change (you will be
eliminating it in the next step anyway, and this seems premature and unrelated
to the other changes you are making in this CL.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone.h
File src/zone.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/zone.h#newcode180
src/zone.h:180: typedef ZoneAllocator Alloc;
Please use the full words for "Allocator" and "Deallocator"

http://chromiumcodereview.appspot.com/10448007/diff/3001/test/cctest/test-lis...
File test/cctest/test-list.cc (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/test/cctest/test-lis...
test/cctest/test-list.cc:61: typedef ZeroingAllocator Alloc;
Full "Allocator" and "Deallocator"

[sanjoy1, 2012-05-25 20:32:44]

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h
File src/splay-tree.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:128: UNREACHABLE();
On 2012/05/25 11:03:37, danno wrote:
> Why unreachable? Because nodes should only be allocated in Zones? Was the
delete
> operator never called before? I still don't see what it's a problem to
> implemented this with Deallocator().Delete(p);

The nodes are deleted using Deallocator::Delete, which sees a void pointer. 
Thus, the delete method of a Node should never be called.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/splay-tree.h#new...
src/splay-tree.h:209: Deallocator deallocator_;
On 2012/05/25 11:03:37, danno wrote:
> I don't think you ever need to store the Deallocator as a member. I think we
> must be able to always call the Deallocator constructor with no arguments.

I need to store it in case the we're using the
PreallocatedStorageAllocationPolicy and want to have the isolate around for
deletion without a TLS lookup.  Right now it does a TLS lookup.

As long as the destructor doesn't do anything funny, I think we should be able
to reinterpret_cast the void* in the object's `operator delete' to a pointer to
the object, extract the deallocator and call the Destroy (of the Deallocator
instance) method on the pointer.

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/v8.h
File src/v8.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/3001/src/v8.h#newcode68
src/v8.h:68: #include "zone-inl.h"
On 2012/05/25 11:03:37, danno wrote:
> What has changed that you need this extra include?

I get a "inline function `void* v8::internal::ZoneAllocator::New(int)` used but
never defined" error when I don't add this.  I've checked the preprocessed
source files, but didn't notice anything suspicious.

[danno, 2012-05-31 11:03:35]

Please also run out performance regression tests to make sure this is
performance neutral.

http://chromiumcodereview.appspot.com/10448007/diff/10001/src/splay-tree-inl.h
File src/splay-tree-inl.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/10001/src/splay-tree-inl....
src/splay-tree-inl.h:189: deallocator_.Delete(node_to_move);
Yikes! You never call the node's destructor this way. I think you need to have
the node contain the deallocator, too, for symmetry.

http://chromiumcodereview.appspot.com/10448007/diff/10001/src/splay-tree.h
File src/splay-tree.h (right):

http://chromiumcodereview.appspot.com/10448007/diff/10001/src/splay-tree.h#ne...
src/splay-tree.h:127: UNREACHABLE();
Hmmm. This still seems dangerous. It seems to introduce unnecessary asymmetry.

http://chromiumcodereview.appspot.com/10448007/diff/10001/src/splay-tree.h#ne...
src/splay-tree.h:141: Node* right_;
I think the cleanest way is to make sure Deallocator is a member here.

[Vyacheslav Egorov (Google), 2012-05-31 12:07:58]

DBC: I don't think decoupling things that are tightly coupled (ike allocation
and deallocation) into separate classes is the right way.

One simple approach would be to have a single allocator classes with interface
like:

class SomeAllocator {
 INLINE(void* New(size_t size));
 INLINE(static void Delete(void* p));
};

And parameterize our containers with it. If Allocator needs any booking data to
correctly free p it will prepend it to the allocated data in a regular fashion
(that is it will allocate sizeof(BookKeeping) + size more for each object, etc).

Such approach seems more natural from the memory management perspective then
having completely disjoint Allocator/Deallocator that are then united into
Policy.