OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
110 && (offset <= Page::kPageSize)) | 110 && (offset <= Page::kPageSize)) |
111 | 111 |
112 #define ASSERT_MAP_PAGE_INDEX(index) \ | 112 #define ASSERT_MAP_PAGE_INDEX(index) \ |
113 ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex)) | 113 ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex)) |
114 | 114 |
115 | 115 |
116 class PagedSpace; | 116 class PagedSpace; |
117 class MemoryAllocator; | 117 class MemoryAllocator; |
118 class AllocationInfo; | 118 class AllocationInfo; |
119 class Space; | 119 class Space; |
120 class OldSpaceFreeList; | 120 class FreeList; |
121 | 121 |
122 | 122 |
123 // TODO(gc): Check that this all gets inlined and register allocated on | 123 // TODO(gc): Check that this all gets inlined and register allocated on |
124 // all platforms. | 124 // all platforms. |
125 class MarkBit { | 125 class MarkBit { |
126 public: | 126 public: |
127 typedef uint32_t CellType; | 127 typedef uint32_t CellType; |
128 | 128 |
129 inline MarkBit(CellType* cell, CellType mask, bool data_only) | 129 inline MarkBit(CellType* cell, CellType mask, bool data_only) |
130 : cell_(cell), mask_(mask), data_only_(data_only) { } | 130 : cell_(cell), mask_(mask), data_only_(data_only) { } |
(...skipping 252 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
383 enum MemoryChunkFlags { | 383 enum MemoryChunkFlags { |
384 IS_EXECUTABLE, | 384 IS_EXECUTABLE, |
385 WAS_SWEPT_CONSERVATIVELY, | 385 WAS_SWEPT_CONSERVATIVELY, |
386 CONTAINS_ONLY_DATA, | 386 CONTAINS_ONLY_DATA, |
387 POINTERS_TO_HERE_ARE_INTERESTING, | 387 POINTERS_TO_HERE_ARE_INTERESTING, |
388 POINTERS_FROM_HERE_ARE_INTERESTING, | 388 POINTERS_FROM_HERE_ARE_INTERESTING, |
389 SCAN_ON_SCAVENGE, | 389 SCAN_ON_SCAVENGE, |
390 IN_FROM_SPACE, // Mutually exclusive with IN_TO_SPACE. | 390 IN_FROM_SPACE, // Mutually exclusive with IN_TO_SPACE. |
391 IN_TO_SPACE, // All pages in new space has one of these two set. | 391 IN_TO_SPACE, // All pages in new space has one of these two set. |
392 NEW_SPACE_BELOW_AGE_MARK, | 392 NEW_SPACE_BELOW_AGE_MARK, |
| 393 EVACUATION_CANDIDATE, |
393 NUM_MEMORY_CHUNK_FLAGS | 394 NUM_MEMORY_CHUNK_FLAGS |
394 }; | 395 }; |
395 | 396 |
396 void SetFlag(int flag) { | 397 void SetFlag(int flag) { |
397 flags_ |= (1 << flag); | 398 flags_ |= (1 << flag); |
398 } | 399 } |
399 | 400 |
400 void ClearFlag(int flag) { | 401 void ClearFlag(int flag) { |
401 flags_ &= ~(1 << flag); | 402 flags_ &= ~(1 << flag); |
402 } | 403 } |
(...skipping 194 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
597 | 598 |
598 inline void ClearGCFields(); | 599 inline void ClearGCFields(); |
599 | 600 |
600 static inline Page* Initialize(Heap* heap, | 601 static inline Page* Initialize(Heap* heap, |
601 MemoryChunk* chunk, | 602 MemoryChunk* chunk, |
602 Executability executable, | 603 Executability executable, |
603 PagedSpace* owner); | 604 PagedSpace* owner); |
604 | 605 |
605 void InitializeAsAnchor(PagedSpace* owner); | 606 void InitializeAsAnchor(PagedSpace* owner); |
606 | 607 |
| 608 bool IsEvacuationCandidate() { return IsFlagSet(EVACUATION_CANDIDATE); } |
| 609 |
| 610 bool IsEvacuationCandidateOrNewSpace() { |
| 611 intptr_t mask = (1 << EVACUATION_CANDIDATE) | |
| 612 (1 << IN_FROM_SPACE) | |
| 613 (1 << IN_TO_SPACE); |
| 614 return (flags_ & mask) != 0; |
| 615 } |
| 616 |
| 617 void MarkEvacuationCandidate() { SetFlag(EVACUATION_CANDIDATE); } |
| 618 |
| 619 void ClearEvacuationCandidate() { ClearFlag(EVACUATION_CANDIDATE); } |
| 620 |
607 friend class MemoryAllocator; | 621 friend class MemoryAllocator; |
608 }; | 622 }; |
609 | 623 |
610 | 624 |
611 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize); | 625 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize); |
612 | 626 |
613 | 627 |
614 class LargePage : public MemoryChunk { | 628 class LargePage : public MemoryChunk { |
615 public: | 629 public: |
616 HeapObject* GetObject() { | 630 HeapObject* GetObject() { |
(...skipping 548 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1165 // limit when the object we need to allocate is 1-31 words in size. These | 1179 // limit when the object we need to allocate is 1-31 words in size. These |
1166 // spaces are called small. | 1180 // spaces are called small. |
1167 // 256-2047 words: There is a list of spaces this large. It is used for top and | 1181 // 256-2047 words: There is a list of spaces this large. It is used for top and |
1168 // limit when the object we need to allocate is 32-255 words in size. These | 1182 // limit when the object we need to allocate is 32-255 words in size. These |
1169 // spaces are called medium. | 1183 // spaces are called medium. |
1170 // 1048-16383 words: There is a list of spaces this large. It is used for top | 1184 // 1048-16383 words: There is a list of spaces this large. It is used for top |
1171 // and limit when the object we need to allocate is 256-2047 words in size. | 1185 // and limit when the object we need to allocate is 256-2047 words in size. |
1172 // These spaces are call large. | 1186 // These spaces are call large. |
1173 // At least 16384 words. This list is for objects of 2048 words or larger. | 1187 // At least 16384 words. This list is for objects of 2048 words or larger. |
1174 // Empty pages are added to this list. These spaces are called huge. | 1188 // Empty pages are added to this list. These spaces are called huge. |
1175 class OldSpaceFreeList BASE_EMBEDDED { | 1189 class FreeList BASE_EMBEDDED { |
1176 public: | 1190 public: |
1177 explicit OldSpaceFreeList(PagedSpace* owner); | 1191 explicit FreeList(PagedSpace* owner); |
1178 | 1192 |
1179 // Clear the free list. | 1193 // Clear the free list. |
1180 void Reset(); | 1194 void Reset(); |
1181 | 1195 |
1182 // Return the number of bytes available on the free list. | 1196 // Return the number of bytes available on the free list. |
1183 intptr_t available() { return available_; } | 1197 intptr_t available() { return available_; } |
1184 | 1198 |
1185 // Place a node on the free list. The block of size 'size_in_bytes' | 1199 // Place a node on the free list. The block of size 'size_in_bytes' |
1186 // starting at 'start' is placed on the free list. The return value is the | 1200 // starting at 'start' is placed on the free list. The return value is the |
1187 // number of bytes that have been lost due to internal fragmentation by | 1201 // number of bytes that have been lost due to internal fragmentation by |
(...skipping 11 matching lines...) Expand all Loading... |
1199 void MarkNodes(); | 1213 void MarkNodes(); |
1200 | 1214 |
1201 #ifdef DEBUG | 1215 #ifdef DEBUG |
1202 void Zap(); | 1216 void Zap(); |
1203 static intptr_t SumFreeList(FreeListNode* node); | 1217 static intptr_t SumFreeList(FreeListNode* node); |
1204 static int FreeListLength(FreeListNode* cur); | 1218 static int FreeListLength(FreeListNode* cur); |
1205 intptr_t SumFreeLists(); | 1219 intptr_t SumFreeLists(); |
1206 bool IsVeryLong(); | 1220 bool IsVeryLong(); |
1207 #endif | 1221 #endif |
1208 | 1222 |
| 1223 void CountFreeListItems(Page* p, intptr_t* sizes); |
| 1224 |
1209 private: | 1225 private: |
1210 // The size range of blocks, in bytes. | 1226 // The size range of blocks, in bytes. |
1211 static const int kMinBlockSize = 3 * kPointerSize; | 1227 static const int kMinBlockSize = 3 * kPointerSize; |
1212 static const int kMaxBlockSize = Page::kMaxHeapObjectSize; | 1228 static const int kMaxBlockSize = Page::kMaxHeapObjectSize; |
1213 | 1229 |
1214 PagedSpace* owner_; | 1230 PagedSpace* owner_; |
1215 Heap* heap_; | 1231 Heap* heap_; |
1216 | 1232 |
1217 // Total available bytes in all blocks on this free list. | 1233 // Total available bytes in all blocks on this free list. |
1218 int available_; | 1234 int available_; |
1219 | 1235 |
1220 static const int kSmallListMin = 0x20 * kPointerSize; | 1236 static const int kSmallListMin = 0x20 * kPointerSize; |
1221 static const int kSmallListMax = 0xff * kPointerSize; | 1237 static const int kSmallListMax = 0xff * kPointerSize; |
1222 static const int kMediumListMax = 0x7ff * kPointerSize; | 1238 static const int kMediumListMax = 0x7ff * kPointerSize; |
1223 static const int kLargeListMax = 0x3fff * kPointerSize; | 1239 static const int kLargeListMax = 0x3fff * kPointerSize; |
1224 static const int kSmallAllocationMax = kSmallListMin - kPointerSize; | 1240 static const int kSmallAllocationMax = kSmallListMin - kPointerSize; |
1225 static const int kMediumAllocationMax = kSmallListMax; | 1241 static const int kMediumAllocationMax = kSmallListMax; |
1226 static const int kLargeAllocationMax = kMediumListMax; | 1242 static const int kLargeAllocationMax = kMediumListMax; |
1227 FreeListNode* small_list_; | 1243 FreeListNode* small_list_; |
1228 FreeListNode* medium_list_; | 1244 FreeListNode* medium_list_; |
1229 FreeListNode* large_list_; | 1245 FreeListNode* large_list_; |
1230 FreeListNode* huge_list_; | 1246 FreeListNode* huge_list_; |
1231 | 1247 |
1232 DISALLOW_IMPLICIT_CONSTRUCTORS(OldSpaceFreeList); | 1248 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList); |
1233 }; | 1249 }; |
1234 | 1250 |
1235 | 1251 |
1236 class PagedSpace : public Space { | 1252 class PagedSpace : public Space { |
1237 public: | 1253 public: |
1238 // Creates a space with a maximum capacity, and an id. | 1254 // Creates a space with a maximum capacity, and an id. |
1239 PagedSpace(Heap* heap, | 1255 PagedSpace(Heap* heap, |
1240 intptr_t max_capacity, | 1256 intptr_t max_capacity, |
1241 AllocationSpace id, | 1257 AllocationSpace id, |
1242 Executability executable); | 1258 Executability executable); |
(...skipping 18 matching lines...) Expand all Loading... |
1261 inline bool Contains(Address a); | 1277 inline bool Contains(Address a); |
1262 bool Contains(HeapObject* o) { return Contains(o->address()); } | 1278 bool Contains(HeapObject* o) { return Contains(o->address()); } |
1263 | 1279 |
1264 // Given an address occupied by a live object, return that object if it is | 1280 // Given an address occupied by a live object, return that object if it is |
1265 // in this space, or Failure::Exception() if it is not. The implementation | 1281 // in this space, or Failure::Exception() if it is not. The implementation |
1266 // iterates over objects in the page containing the address, the cost is | 1282 // iterates over objects in the page containing the address, the cost is |
1267 // linear in the number of objects in the page. It may be slow. | 1283 // linear in the number of objects in the page. It may be slow. |
1268 MUST_USE_RESULT MaybeObject* FindObject(Address addr); | 1284 MUST_USE_RESULT MaybeObject* FindObject(Address addr); |
1269 | 1285 |
1270 // Prepares for a mark-compact GC. | 1286 // Prepares for a mark-compact GC. |
1271 virtual void PrepareForMarkCompact(bool will_compact); | 1287 virtual void PrepareForMarkCompact(); |
1272 | 1288 |
1273 // Current capacity without growing (Size() + Available()). | 1289 // Current capacity without growing (Size() + Available()). |
1274 intptr_t Capacity() { return accounting_stats_.Capacity(); } | 1290 intptr_t Capacity() { return accounting_stats_.Capacity(); } |
1275 | 1291 |
1276 // Total amount of memory committed for this space. For paged | 1292 // Total amount of memory committed for this space. For paged |
1277 // spaces this equals the capacity. | 1293 // spaces this equals the capacity. |
1278 intptr_t CommittedMemory() { return Capacity(); } | 1294 intptr_t CommittedMemory() { return Capacity(); } |
1279 | 1295 |
1280 // Sets the capacity, the available space and the wasted space to zero. | 1296 // Sets the capacity, the available space and the wasted space to zero. |
1281 // The stats are rebuilt during sweeping by adding each page to the | 1297 // The stats are rebuilt during sweeping by adding each page to the |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1395 | 1411 |
1396 bool AdvanceSweeper(intptr_t bytes_to_sweep); | 1412 bool AdvanceSweeper(intptr_t bytes_to_sweep); |
1397 | 1413 |
1398 bool IsSweepingComplete() { | 1414 bool IsSweepingComplete() { |
1399 return !first_unswept_page_->is_valid(); | 1415 return !first_unswept_page_->is_valid(); |
1400 } | 1416 } |
1401 | 1417 |
1402 Page* FirstPage() { return anchor_.next_page(); } | 1418 Page* FirstPage() { return anchor_.next_page(); } |
1403 Page* LastPage() { return anchor_.prev_page(); } | 1419 Page* LastPage() { return anchor_.prev_page(); } |
1404 | 1420 |
| 1421 |
| 1422 bool IsFragmented(Page* p) { |
| 1423 intptr_t sizes[4]; |
| 1424 free_list_.CountFreeListItems(p, sizes); |
| 1425 |
| 1426 intptr_t ratio = |
| 1427 (sizes[0] * 5 + sizes[1]) * 100 / Page::kObjectAreaSize; |
| 1428 |
| 1429 if (FLAG_trace_fragmentation) { |
| 1430 PrintF("%p: %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %s\n", |
| 1431 (void*) p, |
| 1432 sizes[0], |
| 1433 static_cast<double>(sizes[0] * 100) / Page::kObjectAreaSize, |
| 1434 sizes[1], |
| 1435 static_cast<double>(sizes[1] * 100) / Page::kObjectAreaSize, |
| 1436 sizes[2], |
| 1437 static_cast<double>(sizes[2] * 100) / Page::kObjectAreaSize, |
| 1438 sizes[3], |
| 1439 static_cast<double>(sizes[3] * 100) / Page::kObjectAreaSize, |
| 1440 (ratio > 15) ? "[fragmented]" : ""); |
| 1441 } |
| 1442 |
| 1443 return ratio > 15; |
| 1444 } |
| 1445 |
1405 protected: | 1446 protected: |
1406 // Maximum capacity of this space. | 1447 // Maximum capacity of this space. |
1407 intptr_t max_capacity_; | 1448 intptr_t max_capacity_; |
1408 | 1449 |
1409 // Accounting information for this space. | 1450 // Accounting information for this space. |
1410 AllocationStats accounting_stats_; | 1451 AllocationStats accounting_stats_; |
1411 | 1452 |
1412 // The dummy page that anchors the double linked list of pages. | 1453 // The dummy page that anchors the double linked list of pages. |
1413 Page anchor_; | 1454 Page anchor_; |
1414 | 1455 |
1415 // The space's free list. | 1456 // The space's free list. |
1416 OldSpaceFreeList free_list_; | 1457 FreeList free_list_; |
1417 | 1458 |
1418 // Normal allocation information. | 1459 // Normal allocation information. |
1419 AllocationInfo allocation_info_; | 1460 AllocationInfo allocation_info_; |
1420 | 1461 |
1421 // Bytes of each page that cannot be allocated. Possibly non-zero | 1462 // Bytes of each page that cannot be allocated. Possibly non-zero |
1422 // for pages in spaces with only fixed-size objects. Always zero | 1463 // for pages in spaces with only fixed-size objects. Always zero |
1423 // for pages in spaces with variable sized objects (those pages are | 1464 // for pages in spaces with variable sized objects (those pages are |
1424 // padded with free-list nodes). | 1465 // padded with free-list nodes). |
1425 int page_extra_; | 1466 int page_extra_; |
1426 | 1467 |
(...skipping 720 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2147 page_extra_ = 0; | 2188 page_extra_ = 0; |
2148 } | 2189 } |
2149 | 2190 |
2150 // The limit of allocation for a page in this space. | 2191 // The limit of allocation for a page in this space. |
2151 virtual Address PageAllocationLimit(Page* page) { | 2192 virtual Address PageAllocationLimit(Page* page) { |
2152 return page->ObjectAreaEnd(); | 2193 return page->ObjectAreaEnd(); |
2153 } | 2194 } |
2154 | 2195 |
2155 // Prepare for full garbage collection. Resets the relocation pointer and | 2196 // Prepare for full garbage collection. Resets the relocation pointer and |
2156 // clears the free list. | 2197 // clears the free list. |
2157 virtual void PrepareForMarkCompact(bool will_compact); | 2198 virtual void PrepareForMarkCompact(); |
2158 | 2199 |
2159 public: | 2200 public: |
2160 TRACK_MEMORY("OldSpace") | 2201 TRACK_MEMORY("OldSpace") |
2161 }; | 2202 }; |
2162 | 2203 |
2163 | 2204 |
2164 // For contiguous spaces, top should be in the space (or at the end) and limit | 2205 // For contiguous spaces, top should be in the space (or at the end) and limit |
2165 // should be the end of the space. | 2206 // should be the end of the space. |
2166 #define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \ | 2207 #define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \ |
2167 ASSERT((space).page_low() <= (info).top \ | 2208 ASSERT((space).page_low() <= (info).top \ |
(...skipping 18 matching lines...) Expand all Loading... |
2186 } | 2227 } |
2187 | 2228 |
2188 // The limit of allocation for a page in this space. | 2229 // The limit of allocation for a page in this space. |
2189 virtual Address PageAllocationLimit(Page* page) { | 2230 virtual Address PageAllocationLimit(Page* page) { |
2190 return page->ObjectAreaEnd() - page_extra_; | 2231 return page->ObjectAreaEnd() - page_extra_; |
2191 } | 2232 } |
2192 | 2233 |
2193 int object_size_in_bytes() { return object_size_in_bytes_; } | 2234 int object_size_in_bytes() { return object_size_in_bytes_; } |
2194 | 2235 |
2195 // Prepares for a mark-compact GC. | 2236 // Prepares for a mark-compact GC. |
2196 virtual void PrepareForMarkCompact(bool will_compact); | 2237 virtual void PrepareForMarkCompact(); |
2197 | 2238 |
2198 void MarkFreeListNodes() { free_list_.MarkNodes(); } | 2239 void MarkFreeListNodes() { free_list_.MarkNodes(); } |
2199 | 2240 |
2200 protected: | 2241 protected: |
2201 void ResetFreeList() { | 2242 void ResetFreeList() { |
2202 free_list_.Reset(); | 2243 free_list_.Reset(); |
2203 } | 2244 } |
2204 | 2245 |
2205 private: | 2246 private: |
2206 // The size of objects in this space. | 2247 // The size of objects in this space. |
(...skipping 11 matching lines...) Expand all Loading... |
2218 public: | 2259 public: |
2219 // Creates a map space object with a maximum capacity. | 2260 // Creates a map space object with a maximum capacity. |
2220 MapSpace(Heap* heap, | 2261 MapSpace(Heap* heap, |
2221 intptr_t max_capacity, | 2262 intptr_t max_capacity, |
2222 int max_map_space_pages, | 2263 int max_map_space_pages, |
2223 AllocationSpace id) | 2264 AllocationSpace id) |
2224 : FixedSpace(heap, max_capacity, id, Map::kSize, "map"), | 2265 : FixedSpace(heap, max_capacity, id, Map::kSize, "map"), |
2225 max_map_space_pages_(max_map_space_pages) { | 2266 max_map_space_pages_(max_map_space_pages) { |
2226 } | 2267 } |
2227 | 2268 |
2228 // Prepares for a mark-compact GC. | |
2229 virtual void PrepareForMarkCompact(bool will_compact); | |
2230 | |
2231 // Given an index, returns the page address. | 2269 // Given an index, returns the page address. |
2232 // TODO(gc): this limit is artifical just to keep code compilable | 2270 // TODO(gc): this limit is artifical just to keep code compilable |
2233 static const int kMaxMapPageIndex = 1 << 16; | 2271 static const int kMaxMapPageIndex = 1 << 16; |
2234 | 2272 |
2235 // Are map pointers encodable into map word? | 2273 // Are map pointers encodable into map word? |
2236 bool MapPointersEncodable() { | 2274 bool MapPointersEncodable() { |
2237 return false; | 2275 return false; |
2238 } | 2276 } |
2239 | 2277 |
2240 // Should be called after forced sweep to find out if map space needs | 2278 // Should be called after forced sweep to find out if map space needs |
(...skipping 252 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2493 } | 2531 } |
2494 // Must be small, since an iteration is used for lookup. | 2532 // Must be small, since an iteration is used for lookup. |
2495 static const int kMaxComments = 64; | 2533 static const int kMaxComments = 64; |
2496 }; | 2534 }; |
2497 #endif | 2535 #endif |
2498 | 2536 |
2499 | 2537 |
2500 } } // namespace v8::internal | 2538 } } // namespace v8::internal |
2501 | 2539 |
2502 #endif // V8_SPACES_H_ | 2540 #endif // V8_SPACES_H_ |
OLD | NEW |