Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(77)

Side by Side Diff: src/spaces.cc

Issue 13798002: On-the-fly bookkeeping of PagedSpace memory kept in free-lists. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Created 7 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« src/spaces.h ('K') | « src/spaces.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 679 matching lines...) Expand 10 before | Expand all | Expand 10 after
690 chunk_size, 690 chunk_size,
691 area_start, 691 area_start,
692 area_end, 692 area_end,
693 executable, 693 executable,
694 owner); 694 owner);
695 result->set_reserved_memory(&reservation); 695 result->set_reserved_memory(&reservation);
696 return result; 696 return result;
697 } 697 }
698 698
699 699
700 void Page::ResetFreeListStatistics() {
701 non_available_small_blocks_ = 0;
702 available_in_small_free_list_ = 0;
703 available_in_medium_free_list_ = 0;
704 available_in_large_free_list_ = 0;
705 available_in_huge_free_list_ = 0;
706 }
707
708
709 Page::Page() {
710 ResetFreeListStatistics();
711 }
712
713
700 Page* MemoryAllocator::AllocatePage(intptr_t size, 714 Page* MemoryAllocator::AllocatePage(intptr_t size,
701 PagedSpace* owner, 715 PagedSpace* owner,
702 Executability executable) { 716 Executability executable) {
703 MemoryChunk* chunk = AllocateChunk(size, size, executable, owner); 717 MemoryChunk* chunk = AllocateChunk(size, size, executable, owner);
704 718
705 if (chunk == NULL) return NULL; 719 if (chunk == NULL) return NULL;
706 720
707 return Page::Initialize(isolate_->heap(), chunk, executable, owner); 721 return Page::Initialize(isolate_->heap(), chunk, executable, owner);
708 } 722 }
709 723
(...skipping 340 matching lines...) Expand 10 before | Expand all | Expand 10 after
1050 PageIterator it(this); 1064 PageIterator it(this);
1051 int count = 0; 1065 int count = 0;
1052 while (it.has_next()) { 1066 while (it.has_next()) {
1053 it.next(); 1067 it.next();
1054 count++; 1068 count++;
1055 } 1069 }
1056 return count; 1070 return count;
1057 } 1071 }
1058 1072
1059 1073
1074 void PagedSpace::ObtainFreeListStatistics(Page* page, SizeStats* sizes) {
1075 sizes->huge_size_ = page->available_in_huge_free_list();
1076 sizes->small_size_ = page->available_in_small_free_list();
1077 sizes->medium_size_ = page->available_in_medium_free_list();
1078 sizes->large_size_ = page->available_in_large_free_list();
1079 }
1080
1081
1082 void PagedSpace::ResetFreeListStatistics() {
1083 PageIterator page_iterator(this);
1084 while (page_iterator.has_next()) {
1085 Page* page = page_iterator.next();
1086 page->ResetFreeListStatistics();
1087 }
1088 }
1089
1090
1060 void PagedSpace::ReleasePage(Page* page, bool unlink) { 1091 void PagedSpace::ReleasePage(Page* page, bool unlink) {
1061 ASSERT(page->LiveBytes() == 0); 1092 ASSERT(page->LiveBytes() == 0);
1062 ASSERT(AreaSize() == page->area_size()); 1093 ASSERT(AreaSize() == page->area_size());
1063 1094
1064 // Adjust list of unswept pages if the page is the head of the list. 1095 // Adjust list of unswept pages if the page is the head of the list.
1065 if (first_unswept_page_ == page) { 1096 if (first_unswept_page_ == page) {
1066 first_unswept_page_ = page->next_page(); 1097 first_unswept_page_ = page->next_page();
1067 if (first_unswept_page_ == anchor()) { 1098 if (first_unswept_page_ == anchor()) {
1068 first_unswept_page_ = Page::FromAddress(NULL); 1099 first_unswept_page_ = Page::FromAddress(NULL);
1069 } 1100 }
(...skipping 979 matching lines...) Expand 10 before | Expand all | Expand 10 after
2049 } 2080 }
2050 2081
2051 2082
2052 void FreeListCategory::Reset() { 2083 void FreeListCategory::Reset() {
2053 top_ = NULL; 2084 top_ = NULL;
2054 end_ = NULL; 2085 end_ = NULL;
2055 available_ = 0; 2086 available_ = 0;
2056 } 2087 }
2057 2088
2058 2089
2059 intptr_t FreeListCategory::CountFreeListItemsInList(Page* p) {
2060 int sum = 0;
2061 FreeListNode* n = top_;
2062 while (n != NULL) {
2063 if (Page::FromAddress(n->address()) == p) {
2064 FreeSpace* free_space = reinterpret_cast<FreeSpace*>(n);
2065 sum += free_space->Size();
2066 }
2067 n = n->next();
2068 }
2069 return sum;
2070 }
2071
2072
2073 intptr_t FreeListCategory::EvictFreeListItemsInList(Page* p) { 2090 intptr_t FreeListCategory::EvictFreeListItemsInList(Page* p) {
2074 int sum = 0; 2091 int sum = 0;
2075 FreeListNode** n = &top_; 2092 FreeListNode** n = &top_;
2076 while (*n != NULL) { 2093 while (*n != NULL) {
2077 if (Page::FromAddress((*n)->address()) == p) { 2094 if (Page::FromAddress((*n)->address()) == p) {
2078 FreeSpace* free_space = reinterpret_cast<FreeSpace*>(*n); 2095 FreeSpace* free_space = reinterpret_cast<FreeSpace*>(*n);
2079 sum += free_space->Size(); 2096 sum += free_space->Size();
2080 *n = (*n)->next(); 2097 *n = (*n)->next();
2081 } else { 2098 } else {
2082 n = (*n)->next_address(); 2099 n = (*n)->next_address();
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after
2163 large_list_.Reset(); 2180 large_list_.Reset();
2164 huge_list_.Reset(); 2181 huge_list_.Reset();
2165 } 2182 }
2166 2183
2167 2184
2168 int FreeList::Free(Address start, int size_in_bytes) { 2185 int FreeList::Free(Address start, int size_in_bytes) {
2169 if (size_in_bytes == 0) return 0; 2186 if (size_in_bytes == 0) return 0;
2170 2187
2171 FreeListNode* node = FreeListNode::FromAddress(start); 2188 FreeListNode* node = FreeListNode::FromAddress(start);
2172 node->set_size(heap_, size_in_bytes); 2189 node->set_size(heap_, size_in_bytes);
2190 Page* page = Page::FromAddress(start);
2173 2191
2174 // Early return to drop too-small blocks on the floor. 2192 // Early return to drop too-small blocks on the floor.
2175 if (size_in_bytes < kSmallListMin) return size_in_bytes; 2193 if (size_in_bytes < kSmallListMin) {
2194 page->AddNonAvailableSmallBlocks(size_in_bytes);
2195 return size_in_bytes;
2196 }
2176 2197
2177 // Insert other blocks at the head of a free list of the appropriate 2198 // Insert other blocks at the head of a free list of the appropriate
2178 // magnitude. 2199 // magnitude.
2179 if (size_in_bytes <= kSmallListMax) { 2200 if (size_in_bytes <= kSmallListMax) {
2180 small_list_.Free(node, size_in_bytes); 2201 small_list_.Free(node, size_in_bytes);
2202 page->AddAvailableInSmallFreeList(size_in_bytes);
2181 } else if (size_in_bytes <= kMediumListMax) { 2203 } else if (size_in_bytes <= kMediumListMax) {
2182 medium_list_.Free(node, size_in_bytes); 2204 medium_list_.Free(node, size_in_bytes);
2205 page->AddAvailableInMediumFreeList(size_in_bytes);
2183 } else if (size_in_bytes <= kLargeListMax) { 2206 } else if (size_in_bytes <= kLargeListMax) {
2184 large_list_.Free(node, size_in_bytes); 2207 large_list_.Free(node, size_in_bytes);
2208 page->AddAvailableInLargeFreeList(size_in_bytes);
2185 } else { 2209 } else {
2186 huge_list_.Free(node, size_in_bytes); 2210 huge_list_.Free(node, size_in_bytes);
2211 page->AddAvailableInHugeFreeList(size_in_bytes);
2187 } 2212 }
2188 2213
2189 ASSERT(IsVeryLong() || available() == SumFreeLists()); 2214 ASSERT(IsVeryLong() || available() == SumFreeLists());
2190 return 0; 2215 return 0;
2191 } 2216 }
2192 2217
2193 2218
2194 FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) { 2219 FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
2195 FreeListNode* node = NULL; 2220 FreeListNode* node = NULL;
2196 2221
2197 if (size_in_bytes <= kSmallAllocationMax) { 2222 if (size_in_bytes <= kSmallAllocationMax) {
2198 node = small_list_.PickNodeFromList(node_size); 2223 node = small_list_.PickNodeFromList(node_size);
2199 if (node != NULL) return node; 2224 if (node != NULL) {
2225 Page::FromAddress(node->address())->AddAvailableInSmallFreeList(
Michael Starzinger 2013/04/09 16:56:04 nit: Can we pull out the page into a local "page"
Hannes Payer (out of office) 2013/04/10 07:53:49 Done.
2226 -(*node_size));
2227 return node;
2228 }
2200 } 2229 }
2201 2230
2202 if (size_in_bytes <= kMediumAllocationMax) { 2231 if (size_in_bytes <= kMediumAllocationMax) {
2203 node = medium_list_.PickNodeFromList(node_size); 2232 node = medium_list_.PickNodeFromList(node_size);
2204 if (node != NULL) return node; 2233 if (node != NULL) {
2234 Page::FromAddress(node->address())->AddAvailableInMediumFreeList(
2235 -(*node_size));
2236 return node;
2237 }
2205 } 2238 }
2206 2239
2207 if (size_in_bytes <= kLargeAllocationMax) { 2240 if (size_in_bytes <= kLargeAllocationMax) {
2208 node = large_list_.PickNodeFromList(node_size); 2241 node = large_list_.PickNodeFromList(node_size);
2209 if (node != NULL) return node; 2242 if (node != NULL) {
2243 Page::FromAddress(node->address())->AddAvailableInLargeFreeList(
2244 -(*node_size));
2245 return node;
2246 }
2210 } 2247 }
2211 2248
2212 int huge_list_available = huge_list_.available(); 2249 int huge_list_available = huge_list_.available();
2213 for (FreeListNode** cur = huge_list_.GetTopAddress(); 2250 for (FreeListNode** cur = huge_list_.GetTopAddress();
2214 *cur != NULL; 2251 *cur != NULL;
2215 cur = (*cur)->next_address()) { 2252 cur = (*cur)->next_address()) {
2216 FreeListNode* cur_node = *cur; 2253 FreeListNode* cur_node = *cur;
2217 while (cur_node != NULL && 2254 while (cur_node != NULL &&
2218 Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) { 2255 Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
2219 huge_list_available -= reinterpret_cast<FreeSpace*>(cur_node)->Size(); 2256 huge_list_available -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
2257 Page::FromAddress(cur_node->address())->AddAvailableInHugeFreeList(
2258 -reinterpret_cast<FreeSpace*>(cur_node)->Size());
2220 cur_node = cur_node->next(); 2259 cur_node = cur_node->next();
2221 } 2260 }
2222 2261
2223 *cur = cur_node; 2262 *cur = cur_node;
2224 if (cur_node == NULL) { 2263 if (cur_node == NULL) {
2225 huge_list_.set_end(NULL); 2264 huge_list_.set_end(NULL);
2226 break; 2265 break;
2227 } 2266 }
2228 2267
2229 ASSERT((*cur)->map() == heap_->raw_unchecked_free_space_map()); 2268 ASSERT((*cur)->map() == heap_->raw_unchecked_free_space_map());
2230 FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur); 2269 FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
2231 int size = cur_as_free_space->Size(); 2270 int size = cur_as_free_space->Size();
2232 if (size >= size_in_bytes) { 2271 if (size >= size_in_bytes) {
2233 // Large enough node found. Unlink it from the list. 2272 // Large enough node found. Unlink it from the list.
2234 node = *cur; 2273 node = *cur;
2235 *cur = node->next(); 2274 *cur = node->next();
2236 *node_size = size; 2275 *node_size = size;
2237 huge_list_available -= size; 2276 huge_list_available -= size;
2277 Page::FromAddress(node->address())->AddAvailableInHugeFreeList(-size);
2238 break; 2278 break;
2239 } 2279 }
2240 } 2280 }
2241 2281
2242 if (huge_list_.top() == NULL) { 2282 if (huge_list_.top() == NULL) {
2243 huge_list_.set_end(NULL); 2283 huge_list_.set_end(NULL);
2244 } 2284 }
2245 2285
2246 huge_list_.set_available(huge_list_available); 2286 huge_list_.set_available(huge_list_available);
2247 ASSERT(IsVeryLong() || available() == SumFreeLists()); 2287 ASSERT(IsVeryLong() || available() == SumFreeLists());
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after
2315 } else { 2355 } else {
2316 // TODO(gc) Try not freeing linear allocation region when bytes_left 2356 // TODO(gc) Try not freeing linear allocation region when bytes_left
2317 // are zero. 2357 // are zero.
2318 owner_->SetTop(NULL, NULL); 2358 owner_->SetTop(NULL, NULL);
2319 } 2359 }
2320 2360
2321 return new_node; 2361 return new_node;
2322 } 2362 }
2323 2363
2324 2364
2325 void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
2326 sizes->huge_size_ = huge_list_.CountFreeListItemsInList(p);
2327 if (sizes->huge_size_ < p->area_size()) {
2328 sizes->small_size_ = small_list_.CountFreeListItemsInList(p);
2329 sizes->medium_size_ = medium_list_.CountFreeListItemsInList(p);
2330 sizes->large_size_ = large_list_.CountFreeListItemsInList(p);
2331 } else {
2332 sizes->small_size_ = 0;
2333 sizes->medium_size_ = 0;
2334 sizes->large_size_ = 0;
2335 }
2336 }
2337
2338
2339 intptr_t FreeList::EvictFreeListItems(Page* p) { 2365 intptr_t FreeList::EvictFreeListItems(Page* p) {
2340 intptr_t sum = huge_list_.EvictFreeListItemsInList(p); 2366 intptr_t sum = huge_list_.EvictFreeListItemsInList(p);
2367 p->set_available_in_huge_free_list(0);
2341 2368
2342 if (sum < p->area_size()) { 2369 if (sum < p->area_size()) {
2343 sum += small_list_.EvictFreeListItemsInList(p) + 2370 sum += small_list_.EvictFreeListItemsInList(p) +
2344 medium_list_.EvictFreeListItemsInList(p) + 2371 medium_list_.EvictFreeListItemsInList(p) +
2345 large_list_.EvictFreeListItemsInList(p); 2372 large_list_.EvictFreeListItemsInList(p);
2373 p->set_available_in_small_free_list(0);
2374 p->set_available_in_medium_free_list(0);
2375 p->set_available_in_large_free_list(0);
2346 } 2376 }
2347 2377
2348 return sum; 2378 return sum;
2349 } 2379 }
2350 2380
2351 2381
2352 void FreeList::RepairLists(Heap* heap) { 2382 void FreeList::RepairLists(Heap* heap) {
2353 small_list_.RepairFreeList(heap); 2383 small_list_.RepairFreeList(heap);
2354 medium_list_.RepairFreeList(heap); 2384 medium_list_.RepairFreeList(heap);
2355 large_list_.RepairFreeList(heap); 2385 large_list_.RepairFreeList(heap);
(...skipping 787 matching lines...) Expand 10 before | Expand all | Expand 10 after
3143 object->ShortPrint(); 3173 object->ShortPrint();
3144 PrintF("\n"); 3174 PrintF("\n");
3145 } 3175 }
3146 printf(" --------------------------------------\n"); 3176 printf(" --------------------------------------\n");
3147 printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes()); 3177 printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
3148 } 3178 }
3149 3179
3150 #endif // DEBUG 3180 #endif // DEBUG
3151 3181
3152 } } // namespace v8::internal 3182 } } // namespace v8::internal
OLDNEW
« src/spaces.h ('K') | « src/spaces.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698