--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -983,29 +983,59 @@ GCMarker::restoreValueArray(JSObject *ob
         }
     }
 
     JS_ASSERT(*vpp <= *endp);
     return true;
 }
 
 void
-GCMarker::processMarkStackOther(uintptr_t tag, uintptr_t addr)
+GCMarker::processMarkStackOther(SliceBudget &budget, uintptr_t tag, uintptr_t addr)
 {
     if (tag == TypeTag) {
         ScanTypeObject(this, reinterpret_cast<types::TypeObject *>(addr));
     } else if (tag == SavedValueArrayTag) {
         JS_ASSERT(!(addr & Cell::CellMask));
         JSObject *obj = reinterpret_cast<JSObject *>(addr);
         HeapValue *vp, *end;
         if (restoreValueArray(obj, (void **)&vp, (void **)&end))
             pushValueArray(obj, vp, end);
         else
             pushObject(obj);
+    } else if (tag == ArenaTag) {
+        ArenaHeader *aheader = reinterpret_cast<ArenaHeader *>(addr);
+        AllocKind thingKind = aheader->getAllocKind();
+        size_t thingSize = Arena::thingSize(thingKind);
+
+        for ( ; aheader; aheader = aheader->next) {
+            Arena *arena = aheader->getArena();
+            FreeSpan firstSpan(aheader->getFirstFreeSpan());
+            const FreeSpan *span = &firstSpan;
+
+            for (uintptr_t thing = arena->thingsStart(thingKind); ; thing += thingSize) {
+                JS_ASSERT(thing <= arena->thingsEnd());
+                if (thing == span->first) {
+                    if (!span->hasNext())
+                        break;
+                    thing = span->last;
+                    span = span->nextSpan();
+                } else {
+                    JSObject *object = reinterpret_cast<JSObject *>(thing);
+                    if (object->hasSingletonType())
+                        pushObject(object);
+                    budget.step();
+                }
+            }
+            if (budget.isOverBudget()) {
+                pushArenaList(aheader);
+                return;
+            }
+        }
     }
+
 #if JS_HAS_XML_SUPPORT
     else {
         JS_ASSERT(tag == XmlTag);
         MarkChildren(this, reinterpret_cast<JSXML *>(addr));
     }
 #endif
 }
 
@@ -1038,17 +1068,17 @@ GCMarker::processMarkStackTop(SliceBudge
     }
 
     if (tag == ObjectTag) {
         obj = reinterpret_cast<JSObject *>(addr);
         JS_COMPARTMENT_ASSERT(runtime, obj);
         goto scan_obj;
     }
 
-    processMarkStackOther(tag, addr);
+    processMarkStackOther(budget, tag, addr);
     return;
 
   scan_value_array:
     JS_ASSERT(vp <= end);
     while (vp != end) {
         const Value &v = *vp++;
         if (v.isString()) {
             JSString *str = v.toString();

--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -404,26 +404,20 @@ JSCompartment::markTypes(JSTracer *trc)
     JS_ASSERT(activeAnalysis || gcPreserveCode);
 
     for (CellIterUnderGC i(this, FINALIZE_SCRIPT); !i.done(); i.next()) {
         JSScript *script = i.get<JSScript>();
         MarkScriptRoot(trc, &script, "mark_types_script");
         JS_ASSERT(script == i.get<JSScript>());
     }
 
-    for (size_t thingKind = FINALIZE_OBJECT0;
-         thingKind < FINALIZE_OBJECT_LIMIT;
-         thingKind++) {
-        for (CellIterUnderGC i(this, AllocKind(thingKind)); !i.done(); i.next()) {
-            JSObject *object = i.get<JSObject>();
-            if (object->hasSingletonType()) {
-                MarkObjectRoot(trc, &object, "mark_types_singleton");
-                JS_ASSERT(object == i.get<JSObject>());
-            }
-        }
+    for (size_t thingKind = FINALIZE_OBJECT0; thingKind < FINALIZE_OBJECT_LIMIT; thingKind++) {
+        ArenaHeader *aheader = arenas.getFirstArena(static_cast<AllocKind>(thingKind));
+        if (aheader)
+            rt->gcMarker.pushArenaList(aheader);
     }
 
     for (CellIterUnderGC i(this, FINALIZE_TYPE_OBJECT); !i.done(); i.next()) {
         types::TypeObject *type = i.get<types::TypeObject>();
         MarkTypeObjectRoot(trc, &type, "mark_types_scan");
         JS_ASSERT(type == i.get<types::TypeObject>());
     }
 }

--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -886,16 +886,17 @@ struct GCMarker : public JSTracer {
      * the explicit tags to distinguish them when it cannot be deduced from
      * the context of push or pop operation.
      */
     enum StackTag {
         ValueArrayTag,
         ObjectTag,
         TypeTag,
         XmlTag,
+        ArenaTag,
         SavedValueArrayTag,
         LastTag = SavedValueArrayTag
     };
 
     static const uintptr_t StackTagMask = 7;
 
     static void staticAsserts() {
         JS_STATIC_ASSERT(StackTagMask >= uintptr_t(LastTag));
@@ -912,16 +913,20 @@ struct GCMarker : public JSTracer {
     void start(JSRuntime *rt);
     void stop();
     void reset();
 
     void pushObject(JSObject *obj) {
         pushTaggedPtr(ObjectTag, obj);
     }
 
+    void pushArenaList(gc::ArenaHeader *firstArena) {
+        pushTaggedPtr(ArenaTag, firstArena);
+    }
+
     void pushType(types::TypeObject *type) {
         pushTaggedPtr(TypeTag, type);
     }
 
 #if JS_HAS_XML_SUPPORT
     void pushXML(JSXML *xml) {
         pushTaggedPtr(XmlTag, xml);
     }
@@ -1011,17 +1016,17 @@ struct GCMarker : public JSTracer {
 
     bool isMarkStackEmpty() {
         return stack.isEmpty();
     }
 
     bool restoreValueArray(JSObject *obj, void **vpp, void **endp);
     void saveValueRanges();
     inline void processMarkStackTop(SliceBudget &budget);
-    void processMarkStackOther(uintptr_t tag, uintptr_t addr);
+    void processMarkStackOther(SliceBudget &budget, uintptr_t tag, uintptr_t addr);
 
     void appendGrayRoot(void *thing, JSGCTraceKind kind);
 
     /* The color is only applied to objects, functions and xml. */
     uint32_t color;
 
     DebugOnly<bool> started;