Request for comments on overall approach.

runtime/vm/freelist.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_FREELIST_H_
 #define VM_FREELIST_H_
 
 #include "platform/assert.h"
 #include "vm/allocation.h"
 #include "vm/raw_object.h"
@@ skipping 14 matching lines @@
     ASSERT((next_ & 1) == 1);
     return reinterpret_cast<FreeListElement*>(next_ ^ 1);
   }
   void set_next(FreeListElement* next) {
     // Set the FreeBit.
     uword addr = reinterpret_cast<uword>(next);
     ASSERT((addr & 1) == 0);
     next_ = addr | 1;
   }
 
-  intptr_t Size() const {
-    if (class_ == minimal_element_class_) {
-      return kObjectAlignment;
-    }
-    ASSERT(class_ == element_class_);
-    return *SizeAddress();
+  intptr_t size() const {
+    return size_;
+  }
+  void set_size(intptr_t size) {
+    size_ = size;
   }
 
   static FreeListElement* AsElement(uword addr, intptr_t size);
 
   static bool IsSpecialClass(RawObject* raw_obj) {
-    return (raw_obj == minimal_element_class_) || (raw_obj == element_class_);
+    return raw_obj->IsFree();
   }
 
   static void InitOnce();
 
+  static RawClass* freelist_class() {
+    return freelist_class_;
+  }
+
  private:
   // This layout mirrors the layout of RawObject.
-  RawClass* class_;
   uword next_;

[Ivan Posva, 2012/05/26 04:34:46]

I don't think this works. How do you plan to iterate over the heap? The first
word needs exactly the same header layout as RawObject for that to work. The
nice part is that for most free objects the header word already contains the
size so you can use the second word for next and a third word for size iff the
size in the header cannot fit the size of the free object.

[Vyacheslav Egorov (Google), 2012/05/26 16:48:22]

Yes it does have exactly the same layout as RawObject: I removed class_ from
RawObject so class_ has to be removed from here (interesting thing was that
there were absolutely no assertions verifying layout match. I added one now).

Iteration works as follows: first word in all objects now is tags_. When
calculating class based on tags_ we check for free bit and if it is present we
return FreeListElement class. 

When calculating size we just always look at the size_ (second word) because now
we have enough space in the header to put it there.
Sorry, I am not following here. next_ field was always destroying tags_ entirely
--- so there was not size encoded in tags for objects bigger than 2 words ->
iteration always had to take it from the size_ field. Current implementation of
RawObject::Size() checks for FreeBit and falls through to SizeFromClass in this
case; I did not even need to change it.

+  intptr_t size_;
 
-  // Returns the address of the embedded size.
-  intptr_t* SizeAddress() const {
-    ASSERT(class_ == element_class_);
-    uword addr = reinterpret_cast<uword>(&next_) + kWordSize;
-    return reinterpret_cast<intptr_t*>(addr);
-  }
-
-  // The two fake classe being used by the FreeList to identify free objects in
-  // the heap. These can be static and shared between isolates since they
-  // contain no per-isolate information. Actually, they need to be static so
-  // that they can be used from free list elements efficiently.
-  // The minimal_element_class_ is used by minimally sized free list elements
-  // which cannot hold the size within the element.
-  // element_class_ is used for free lists elements containing a size.
-  static RawClass* minimal_element_class_;
-  static RawClass* element_class_;
+  static RawClass* freelist_class_;
 
   // FreeListElements cannot be allocated. Instead references to them are
   // created using the AsElement factory method.
   DISALLOW_ALLOCATION();
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListElement);
 };
 
 
 class FreeList {
  public:
@@ skipping 16 matching lines @@
   void SplitElementAfterAndEnqueue(FreeListElement* element, intptr_t size);
 
   FreeListElement* free_lists_[kNumLists + 1];
 
   DISALLOW_COPY_AND_ASSIGN(FreeList);
 };
 
 }  // namespace dart
 
 #endif  // VM_FREELIST_H_