-
Notifications
You must be signed in to change notification settings - Fork 28.2k
/
spaces.h
2791 lines (2267 loc) Β· 99.3 KB
/
spaces.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2011 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_HEAP_SPACES_H_
#define V8_HEAP_SPACES_H_
#include <atomic>
#include <list>
#include <map>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "src/base/atomic-utils.h"
#include "src/base/bounded-page-allocator.h"
#include "src/base/export-template.h"
#include "src/base/iterator.h"
#include "src/base/macros.h"
#include "src/base/optional.h"
#include "src/base/platform/mutex.h"
#include "src/common/globals.h"
#include "src/flags/flags.h"
#include "src/heap/basic-memory-chunk.h"
#include "src/heap/heap.h"
#include "src/heap/invalidated-slots.h"
#include "src/heap/list.h"
#include "src/heap/marking.h"
#include "src/heap/memory-chunk.h"
#include "src/heap/slot-set.h"
#include "src/objects/free-space.h"
#include "src/objects/heap-object.h"
#include "src/objects/map.h"
#include "src/objects/objects.h"
#include "src/tasks/cancelable-task.h"
#include "src/utils/allocation.h"
#include "src/utils/utils.h"
#include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck
namespace v8 {
namespace internal {
namespace heap {
class HeapTester;
class TestCodePageAllocatorScope;
} // namespace heap
class AllocationObserver;
class CompactionSpace;
class CompactionSpaceCollection;
class FreeList;
class Isolate;
class LargeObjectSpace;
class LargePage;
class LinearAllocationArea;
class LocalArrayBufferTracker;
class LocalSpace;
class MemoryAllocator;
class MemoryChunk;
class MemoryChunkLayout;
class OffThreadSpace;
class Page;
class PagedSpace;
class SemiSpace;
class SlotsBuffer;
class SlotSet;
class TypedSlotSet;
class Space;
// -----------------------------------------------------------------------------
// Heap structures:
//
// A JS heap consists of a young generation, an old generation, and a large
// object space. The young generation is divided into two semispaces. A
// scavenger implements Cheney's copying algorithm. The old generation is
// separated into a map space and an old object space. The map space contains
// all (and only) map objects, the rest of old objects go into the old space.
// The old generation is collected by a mark-sweep-compact collector.
//
// The semispaces of the young generation are contiguous. The old and map
// spaces consists of a list of pages. A page has a page header and an object
// area.
//
// There is a separate large object space for objects larger than
// kMaxRegularHeapObjectSize, so that they do not have to move during
// collection. The large object space is paged. Pages in large object space
// may be larger than the page size.
//
// A store-buffer based write barrier is used to keep track of intergenerational
// references. See heap/store-buffer.h.
//
// During scavenges and mark-sweep collections we sometimes (after a store
// buffer overflow) iterate intergenerational pointers without decoding heap
// object maps so if the page belongs to old space or large object space
// it is essential to guarantee that the page does not contain any
// garbage pointers to new space: every pointer aligned word which satisfies
// the Heap::InNewSpace() predicate must be a pointer to a live heap object in
// new space. Thus objects in old space and large object spaces should have a
// special layout (e.g. no bare integer fields). This requirement does not
// apply to map space which is iterated in a special fashion. However we still
// require pointer fields of dead maps to be cleaned.
//
// To enable lazy cleaning of old space pages we can mark chunks of the page
// as being garbage. Garbage sections are marked with a special map. These
// sections are skipped when scanning the page, even if we are otherwise
// scanning without regard for object boundaries. Garbage sections are chained
// together to form a free list after a GC. Garbage sections created outside
// of GCs by object trunctation etc. may not be in the free list chain. Very
// small free spaces are ignored, they need only be cleaned of bogus pointers
// into new space.
//
// Each page may have up to one special garbage section. The start of this
// section is denoted by the top field in the space. The end of the section
// is denoted by the limit field in the space. This special garbage section
// is not marked with a free space map in the data. The point of this section
// is to enable linear allocation without having to constantly update the byte
// array every time the top field is updated and a new object is created. The
// special garbage section is not in the chain of garbage sections.
//
// Since the top and limit fields are in the space, not the page, only one page
// has a special garbage section, and if the top and limit are equal then there
// is no special garbage section.
// Some assertion macros used in the debugging mode.
#define DCHECK_OBJECT_SIZE(size) \
DCHECK((0 < size) && (size <= kMaxRegularHeapObjectSize))
#define DCHECK_CODEOBJECT_SIZE(size, code_space) \
DCHECK((0 < size) && \
(size <= std::min(MemoryChunkLayout::MaxRegularCodeObjectSize(), \
code_space->AreaSize())))
using FreeListCategoryType = int32_t;
static const FreeListCategoryType kFirstCategory = 0;
static const FreeListCategoryType kInvalidCategory = -1;
enum FreeMode { kLinkCategory, kDoNotLinkCategory };
enum class SpaceAccountingMode { kSpaceAccounted, kSpaceUnaccounted };
// A free list category maintains a linked list of free memory blocks.
class FreeListCategory {
public:
void Initialize(FreeListCategoryType type) {
type_ = type;
available_ = 0;
prev_ = nullptr;
next_ = nullptr;
}
void Reset(FreeList* owner);
void RepairFreeList(Heap* heap);
// Relinks the category into the currently owning free list. Requires that the
// category is currently unlinked.
void Relink(FreeList* owner);
void Free(Address address, size_t size_in_bytes, FreeMode mode,
FreeList* owner);
// Performs a single try to pick a node of at least |minimum_size| from the
// category. Stores the actual size in |node_size|. Returns nullptr if no
// node is found.
FreeSpace PickNodeFromList(size_t minimum_size, size_t* node_size);
// Picks a node of at least |minimum_size| from the category. Stores the
// actual size in |node_size|. Returns nullptr if no node is found.
FreeSpace SearchForNodeInList(size_t minimum_size, size_t* node_size);
inline bool is_linked(FreeList* owner) const;
bool is_empty() { return top().is_null(); }
uint32_t available() const { return available_; }
size_t SumFreeList();
int FreeListLength();
private:
// For debug builds we accurately compute free lists lengths up until
// {kVeryLongFreeList} by manually walking the list.
static const int kVeryLongFreeList = 500;
// Updates |available_|, |length_| and free_list_->Available() after an
// allocation of size |allocation_size|.
inline void UpdateCountersAfterAllocation(size_t allocation_size);
FreeSpace top() { return top_; }
void set_top(FreeSpace top) { top_ = top; }
FreeListCategory* prev() { return prev_; }
void set_prev(FreeListCategory* prev) { prev_ = prev; }
FreeListCategory* next() { return next_; }
void set_next(FreeListCategory* next) { next_ = next; }
// |type_|: The type of this free list category.
FreeListCategoryType type_ = kInvalidCategory;
// |available_|: Total available bytes in all blocks of this free list
// category.
uint32_t available_ = 0;
// |top_|: Points to the top FreeSpace in the free list category.
FreeSpace top_;
FreeListCategory* prev_ = nullptr;
FreeListCategory* next_ = nullptr;
friend class FreeList;
friend class FreeListManyCached;
friend class PagedSpace;
friend class MapSpace;
};
// A free list maintains free blocks of memory. The free list is organized in
// a way to encourage objects allocated around the same time to be near each
// other. The normal way to allocate is intended to be by bumping a 'top'
// pointer until it hits a 'limit' pointer. When the limit is hit we need to
// find a new space to allocate from. This is done with the free list, which is
// divided up into rough categories to cut down on waste. Having finer
// categories would scatter allocation more.
class FreeList {
public:
// Creates a Freelist of the default class (FreeListLegacy for now).
V8_EXPORT_PRIVATE static FreeList* CreateFreeList();
virtual ~FreeList() = default;
// Returns how much memory can be allocated after freeing maximum_freed
// memory.
virtual size_t GuaranteedAllocatable(size_t maximum_freed) = 0;
// Adds a node on the free list. The block of size {size_in_bytes} starting
// at {start} is placed on the free list. The return value is the number of
// bytes that were not added to the free list, because the freed memory block
// was too small. Bookkeeping information will be written to the block, i.e.,
// its contents will be destroyed. The start address should be word aligned,
// and the size should be a non-zero multiple of the word size.
virtual size_t Free(Address start, size_t size_in_bytes, FreeMode mode);
// Allocates a free space node frome the free list of at least size_in_bytes
// bytes. Returns the actual node size in node_size which can be bigger than
// size_in_bytes. This method returns null if the allocation request cannot be
// handled by the free list.
virtual V8_WARN_UNUSED_RESULT FreeSpace Allocate(size_t size_in_bytes,
size_t* node_size,
AllocationOrigin origin) = 0;
// Returns a page containing an entry for a given type, or nullptr otherwise.
V8_EXPORT_PRIVATE virtual Page* GetPageForSize(size_t size_in_bytes) = 0;
virtual void Reset();
// Return the number of bytes available on the free list.
size_t Available() {
DCHECK(available_ == SumFreeLists());
return available_;
}
// Update number of available bytes on the Freelists.
void IncreaseAvailableBytes(size_t bytes) { available_ += bytes; }
void DecreaseAvailableBytes(size_t bytes) { available_ -= bytes; }
bool IsEmpty() {
bool empty = true;
ForAllFreeListCategories([&empty](FreeListCategory* category) {
if (!category->is_empty()) empty = false;
});
return empty;
}
// Used after booting the VM.
void RepairLists(Heap* heap);
V8_EXPORT_PRIVATE size_t EvictFreeListItems(Page* page);
int number_of_categories() { return number_of_categories_; }
FreeListCategoryType last_category() { return last_category_; }
size_t wasted_bytes() { return wasted_bytes_; }
template <typename Callback>
void ForAllFreeListCategories(FreeListCategoryType type, Callback callback) {
FreeListCategory* current = categories_[type];
while (current != nullptr) {
FreeListCategory* next = current->next();
callback(current);
current = next;
}
}
template <typename Callback>
void ForAllFreeListCategories(Callback callback) {
for (int i = kFirstCategory; i < number_of_categories(); i++) {
ForAllFreeListCategories(static_cast<FreeListCategoryType>(i), callback);
}
}
virtual bool AddCategory(FreeListCategory* category);
virtual V8_EXPORT_PRIVATE void RemoveCategory(FreeListCategory* category);
void PrintCategories(FreeListCategoryType type);
protected:
class FreeListCategoryIterator final {
public:
FreeListCategoryIterator(FreeList* free_list, FreeListCategoryType type)
: current_(free_list->categories_[type]) {}
bool HasNext() const { return current_ != nullptr; }
FreeListCategory* Next() {
DCHECK(HasNext());
FreeListCategory* tmp = current_;
current_ = current_->next();
return tmp;
}
private:
FreeListCategory* current_;
};
#ifdef DEBUG
V8_EXPORT_PRIVATE size_t SumFreeLists();
bool IsVeryLong();
#endif
// Tries to retrieve a node from the first category in a given |type|.
// Returns nullptr if the category is empty or the top entry is smaller
// than minimum_size.
FreeSpace TryFindNodeIn(FreeListCategoryType type, size_t minimum_size,
size_t* node_size);
// Searches a given |type| for a node of at least |minimum_size|.
FreeSpace SearchForNodeInList(FreeListCategoryType type, size_t minimum_size,
size_t* node_size);
// Returns the smallest category in which an object of |size_in_bytes| could
// fit.
virtual FreeListCategoryType SelectFreeListCategoryType(
size_t size_in_bytes) = 0;
FreeListCategory* top(FreeListCategoryType type) const {
return categories_[type];
}
inline Page* GetPageForCategoryType(FreeListCategoryType type);
int number_of_categories_ = 0;
FreeListCategoryType last_category_ = 0;
size_t min_block_size_ = 0;
std::atomic<size_t> wasted_bytes_{0};
FreeListCategory** categories_ = nullptr;
// |available_|: The number of bytes in this freelist.
size_t available_ = 0;
friend class FreeListCategory;
friend class Page;
friend class MemoryChunk;
friend class ReadOnlyPage;
friend class MapSpace;
};
// FreeList used for spaces that don't have freelists
// (only the LargeObject space for now).
class NoFreeList final : public FreeList {
public:
size_t GuaranteedAllocatable(size_t maximum_freed) final {
FATAL("NoFreeList can't be used as a standard FreeList. ");
}
size_t Free(Address start, size_t size_in_bytes, FreeMode mode) final {
FATAL("NoFreeList can't be used as a standard FreeList.");
}
V8_WARN_UNUSED_RESULT FreeSpace Allocate(size_t size_in_bytes,
size_t* node_size,
AllocationOrigin origin) final {
FATAL("NoFreeList can't be used as a standard FreeList.");
}
Page* GetPageForSize(size_t size_in_bytes) final {
FATAL("NoFreeList can't be used as a standard FreeList.");
}
private:
FreeListCategoryType SelectFreeListCategoryType(size_t size_in_bytes) final {
FATAL("NoFreeList can't be used as a standard FreeList.");
}
};
// ----------------------------------------------------------------------------
// Space is the abstract superclass for all allocation spaces.
class V8_EXPORT_PRIVATE Space : public Malloced {
public:
Space(Heap* heap, AllocationSpace id, FreeList* free_list)
: allocation_observers_paused_(false),
heap_(heap),
id_(id),
committed_(0),
max_committed_(0),
free_list_(std::unique_ptr<FreeList>(free_list)) {
external_backing_store_bytes_ =
new std::atomic<size_t>[ExternalBackingStoreType::kNumTypes];
external_backing_store_bytes_[ExternalBackingStoreType::kArrayBuffer] = 0;
external_backing_store_bytes_[ExternalBackingStoreType::kExternalString] =
0;
}
static inline void MoveExternalBackingStoreBytes(
ExternalBackingStoreType type, Space* from, Space* to, size_t amount);
virtual ~Space() {
delete[] external_backing_store_bytes_;
external_backing_store_bytes_ = nullptr;
}
Heap* heap() const {
DCHECK_NOT_NULL(heap_);
return heap_;
}
bool IsDetached() const { return heap_ == nullptr; }
AllocationSpace identity() { return id_; }
const char* name() { return Heap::GetSpaceName(id_); }
virtual void AddAllocationObserver(AllocationObserver* observer);
virtual void RemoveAllocationObserver(AllocationObserver* observer);
virtual void PauseAllocationObservers();
virtual void ResumeAllocationObservers();
virtual void StartNextInlineAllocationStep() {}
void AllocationStep(int bytes_since_last, Address soon_object, int size);
// An AllocationStep equivalent to be called after merging a contiguous
// chunk of an off-thread space into this space. The chunk is treated as a
// single allocation-folding group.
void AllocationStepAfterMerge(Address first_object_in_chunk, int size);
// Return the total amount committed memory for this space, i.e., allocatable
// memory and page headers.
virtual size_t CommittedMemory() { return committed_; }
virtual size_t MaximumCommittedMemory() { return max_committed_; }
// Returns allocated size.
virtual size_t Size() = 0;
// Returns size of objects. Can differ from the allocated size
// (e.g. see OldLargeObjectSpace).
virtual size_t SizeOfObjects() { return Size(); }
// Approximate amount of physical memory committed for this space.
virtual size_t CommittedPhysicalMemory() = 0;
// Return the available bytes without growing.
virtual size_t Available() = 0;
virtual int RoundSizeDownToObjectAlignment(int size) {
if (id_ == CODE_SPACE) {
return RoundDown(size, kCodeAlignment);
} else {
return RoundDown(size, kTaggedSize);
}
}
virtual std::unique_ptr<ObjectIterator> GetObjectIterator(Heap* heap) = 0;
void AccountCommitted(size_t bytes) {
DCHECK_GE(committed_ + bytes, committed_);
committed_ += bytes;
if (committed_ > max_committed_) {
max_committed_ = committed_;
}
}
void AccountUncommitted(size_t bytes) {
DCHECK_GE(committed_, committed_ - bytes);
committed_ -= bytes;
}
inline void IncrementExternalBackingStoreBytes(ExternalBackingStoreType type,
size_t amount);
inline void DecrementExternalBackingStoreBytes(ExternalBackingStoreType type,
size_t amount);
// Returns amount of off-heap memory in-use by objects in this Space.
virtual size_t ExternalBackingStoreBytes(
ExternalBackingStoreType type) const {
return external_backing_store_bytes_[type];
}
void* GetRandomMmapAddr();
MemoryChunk* first_page() { return memory_chunk_list_.front(); }
MemoryChunk* last_page() { return memory_chunk_list_.back(); }
heap::List<MemoryChunk>& memory_chunk_list() { return memory_chunk_list_; }
FreeList* free_list() { return free_list_.get(); }
#ifdef DEBUG
virtual void Print() = 0;
#endif
protected:
intptr_t GetNextInlineAllocationStepSize();
bool AllocationObserversActive() {
return !allocation_observers_paused_ && !allocation_observers_.empty();
}
void DetachFromHeap() { heap_ = nullptr; }
std::vector<AllocationObserver*> allocation_observers_;
// The List manages the pages that belong to the given space.
heap::List<MemoryChunk> memory_chunk_list_;
// Tracks off-heap memory used by this space.
std::atomic<size_t>* external_backing_store_bytes_;
bool allocation_observers_paused_;
Heap* heap_;
AllocationSpace id_;
// Keeps track of committed memory in a space.
std::atomic<size_t> committed_;
size_t max_committed_;
std::unique_ptr<FreeList> free_list_;
DISALLOW_COPY_AND_ASSIGN(Space);
};
// The CodeObjectRegistry holds all start addresses of code objects of a given
// MemoryChunk. Each MemoryChunk owns a separate CodeObjectRegistry. The
// CodeObjectRegistry allows fast lookup from an inner pointer of a code object
// to the actual code object.
class V8_EXPORT_PRIVATE CodeObjectRegistry {
public:
void RegisterNewlyAllocatedCodeObject(Address code);
void RegisterAlreadyExistingCodeObject(Address code);
void Clear();
void Finalize();
bool Contains(Address code) const;
Address GetCodeObjectStartFromInnerAddress(Address address) const;
private:
std::vector<Address> code_object_registry_already_existing_;
std::set<Address> code_object_registry_newly_allocated_;
};
STATIC_ASSERT(sizeof(std::atomic<intptr_t>) == kSystemPointerSize);
// -----------------------------------------------------------------------------
// A page is a memory chunk of a size 256K. Large object pages may be larger.
//
// The only way to get a page pointer is by calling factory methods:
// Page* p = Page::FromAddress(addr); or
// Page* p = Page::FromAllocationAreaAddress(address);
class Page : public MemoryChunk {
public:
static const intptr_t kCopyAllFlags = ~0;
// Page flags copied from from-space to to-space when flipping semispaces.
static const intptr_t kCopyOnFlipFlagsMask =
static_cast<intptr_t>(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING) |
static_cast<intptr_t>(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING) |
static_cast<intptr_t>(MemoryChunk::INCREMENTAL_MARKING);
// Returns the page containing a given address. The address ranges
// from [page_addr .. page_addr + kPageSize[. This only works if the object
// is in fact in a page.
static Page* FromAddress(Address addr) {
return reinterpret_cast<Page*>(addr & ~kPageAlignmentMask);
}
static Page* FromHeapObject(HeapObject o) {
return reinterpret_cast<Page*>(o.ptr() & ~kAlignmentMask);
}
// Returns the page containing the address provided. The address can
// potentially point righter after the page. To be also safe for tagged values
// we subtract a hole word. The valid address ranges from
// [page_addr + area_start_ .. page_addr + kPageSize + kTaggedSize].
static Page* FromAllocationAreaAddress(Address address) {
return Page::FromAddress(address - kTaggedSize);
}
// Checks if address1 and address2 are on the same new space page.
static bool OnSamePage(Address address1, Address address2) {
return Page::FromAddress(address1) == Page::FromAddress(address2);
}
// Checks whether an address is page aligned.
static bool IsAlignedToPageSize(Address addr) {
return (addr & kPageAlignmentMask) == 0;
}
static Page* ConvertNewToOld(Page* old_page);
inline void MarkNeverAllocateForTesting();
inline void MarkEvacuationCandidate();
inline void ClearEvacuationCandidate();
Page* next_page() { return static_cast<Page*>(list_node_.next()); }
Page* prev_page() { return static_cast<Page*>(list_node_.prev()); }
template <typename Callback>
inline void ForAllFreeListCategories(Callback callback) {
for (int i = kFirstCategory;
i < owner()->free_list()->number_of_categories(); i++) {
callback(categories_[i]);
}
}
// Returns the offset of a given address to this page.
inline size_t Offset(Address a) { return static_cast<size_t>(a - address()); }
// Returns the address for a given offset to the this page.
Address OffsetToAddress(size_t offset) {
Address address_in_page = address() + offset;
DCHECK_GE(address_in_page, area_start());
DCHECK_LT(address_in_page, area_end());
return address_in_page;
}
void AllocateLocalTracker();
inline LocalArrayBufferTracker* local_tracker() { return local_tracker_; }
bool contains_array_buffers();
size_t AvailableInFreeList();
size_t AvailableInFreeListFromAllocatedBytes() {
DCHECK_GE(area_size(), wasted_memory() + allocated_bytes());
return area_size() - wasted_memory() - allocated_bytes();
}
FreeListCategory* free_list_category(FreeListCategoryType type) {
return categories_[type];
}
size_t wasted_memory() { return wasted_memory_; }
void add_wasted_memory(size_t waste) { wasted_memory_ += waste; }
size_t allocated_bytes() { return allocated_bytes_; }
void IncreaseAllocatedBytes(size_t bytes) {
DCHECK_LE(bytes, area_size());
allocated_bytes_ += bytes;
}
void DecreaseAllocatedBytes(size_t bytes) {
DCHECK_LE(bytes, area_size());
DCHECK_GE(allocated_bytes(), bytes);
allocated_bytes_ -= bytes;
}
void ResetAllocationStatistics();
size_t ShrinkToHighWaterMark();
V8_EXPORT_PRIVATE void CreateBlackArea(Address start, Address end);
void DestroyBlackArea(Address start, Address end);
void InitializeFreeListCategories();
void AllocateFreeListCategories();
void ReleaseFreeListCategories();
void MoveOldToNewRememberedSetForSweeping();
void MergeOldToNewRememberedSets();
private:
friend class MemoryAllocator;
};
// Validate our estimates on the header size.
STATIC_ASSERT(sizeof(BasicMemoryChunk) <= BasicMemoryChunk::kHeaderSize);
STATIC_ASSERT(sizeof(MemoryChunk) <= MemoryChunk::kHeaderSize);
STATIC_ASSERT(sizeof(Page) <= MemoryChunk::kHeaderSize);
// The process-wide singleton that keeps track of code range regions with the
// intention to reuse free code range regions as a workaround for CFG memory
// leaks (see crbug.com/870054).
class CodeRangeAddressHint {
public:
// Returns the most recently freed code range start address for the given
// size. If there is no such entry, then a random address is returned.
V8_EXPORT_PRIVATE Address GetAddressHint(size_t code_range_size);
V8_EXPORT_PRIVATE void NotifyFreedCodeRange(Address code_range_start,
size_t code_range_size);
private:
base::Mutex mutex_;
// A map from code range size to an array of recently freed code range
// addresses. There should be O(1) different code range sizes.
// The length of each array is limited by the peak number of code ranges,
// which should be also O(1).
std::unordered_map<size_t, std::vector<Address>> recently_freed_;
};
// ----------------------------------------------------------------------------
// A space acquires chunks of memory from the operating system. The memory
// allocator allocates and deallocates pages for the paged heap spaces and large
// pages for large object space.
class MemoryAllocator {
public:
// Unmapper takes care of concurrently unmapping and uncommitting memory
// chunks.
class Unmapper {
public:
class UnmapFreeMemoryTask;
Unmapper(Heap* heap, MemoryAllocator* allocator)
: heap_(heap),
allocator_(allocator),
pending_unmapping_tasks_semaphore_(0),
pending_unmapping_tasks_(0),
active_unmapping_tasks_(0) {
chunks_[kRegular].reserve(kReservedQueueingSlots);
chunks_[kPooled].reserve(kReservedQueueingSlots);
}
void AddMemoryChunkSafe(MemoryChunk* chunk) {
if (!chunk->IsLargePage() && chunk->executable() != EXECUTABLE) {
AddMemoryChunkSafe<kRegular>(chunk);
} else {
AddMemoryChunkSafe<kNonRegular>(chunk);
}
}
MemoryChunk* TryGetPooledMemoryChunkSafe() {
// Procedure:
// (1) Try to get a chunk that was declared as pooled and already has
// been uncommitted.
// (2) Try to steal any memory chunk of kPageSize that would've been
// unmapped.
MemoryChunk* chunk = GetMemoryChunkSafe<kPooled>();
if (chunk == nullptr) {
chunk = GetMemoryChunkSafe<kRegular>();
if (chunk != nullptr) {
// For stolen chunks we need to manually free any allocated memory.
chunk->ReleaseAllAllocatedMemory();
}
}
return chunk;
}
V8_EXPORT_PRIVATE void FreeQueuedChunks();
void CancelAndWaitForPendingTasks();
void PrepareForGC();
V8_EXPORT_PRIVATE void EnsureUnmappingCompleted();
V8_EXPORT_PRIVATE void TearDown();
size_t NumberOfCommittedChunks();
V8_EXPORT_PRIVATE int NumberOfChunks();
size_t CommittedBufferedMemory();
private:
static const int kReservedQueueingSlots = 64;
static const int kMaxUnmapperTasks = 4;
enum ChunkQueueType {
kRegular, // Pages of kPageSize that do not live in a CodeRange and
// can thus be used for stealing.
kNonRegular, // Large chunks and executable chunks.
kPooled, // Pooled chunks, already uncommited and ready for reuse.
kNumberOfChunkQueues,
};
enum class FreeMode {
kUncommitPooled,
kReleasePooled,
};
template <ChunkQueueType type>
void AddMemoryChunkSafe(MemoryChunk* chunk) {
base::MutexGuard guard(&mutex_);
chunks_[type].push_back(chunk);
}
template <ChunkQueueType type>
MemoryChunk* GetMemoryChunkSafe() {
base::MutexGuard guard(&mutex_);
if (chunks_[type].empty()) return nullptr;
MemoryChunk* chunk = chunks_[type].back();
chunks_[type].pop_back();
return chunk;
}
bool MakeRoomForNewTasks();
template <FreeMode mode>
void PerformFreeMemoryOnQueuedChunks();
void PerformFreeMemoryOnQueuedNonRegularChunks();
Heap* const heap_;
MemoryAllocator* const allocator_;
base::Mutex mutex_;
std::vector<MemoryChunk*> chunks_[kNumberOfChunkQueues];
CancelableTaskManager::Id task_ids_[kMaxUnmapperTasks];
base::Semaphore pending_unmapping_tasks_semaphore_;
intptr_t pending_unmapping_tasks_;
std::atomic<intptr_t> active_unmapping_tasks_;
friend class MemoryAllocator;
};
enum AllocationMode {
kRegular,
kPooled,
};
enum FreeMode {
kFull,
kAlreadyPooled,
kPreFreeAndQueue,
kPooledAndQueue,
};
V8_EXPORT_PRIVATE static intptr_t GetCommitPageSize();
// Computes the memory area of discardable memory within a given memory area
// [addr, addr+size) and returns the result as base::AddressRegion. If the
// memory is not discardable base::AddressRegion is an empty region.
V8_EXPORT_PRIVATE static base::AddressRegion ComputeDiscardMemoryArea(
Address addr, size_t size);
V8_EXPORT_PRIVATE MemoryAllocator(Isolate* isolate, size_t max_capacity,
size_t code_range_size);
V8_EXPORT_PRIVATE void TearDown();
// Allocates a Page from the allocator. AllocationMode is used to indicate
// whether pooled allocation, which only works for MemoryChunk::kPageSize,
// should be tried first.
template <MemoryAllocator::AllocationMode alloc_mode = kRegular,
typename SpaceType>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
Page* AllocatePage(size_t size, SpaceType* owner, Executability executable);
LargePage* AllocateLargePage(size_t size, LargeObjectSpace* owner,
Executability executable);
template <MemoryAllocator::FreeMode mode = kFull>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
void Free(MemoryChunk* chunk);
// Returns allocated spaces in bytes.
size_t Size() { return size_; }
// Returns allocated executable spaces in bytes.
size_t SizeExecutable() { return size_executable_; }
// Returns the maximum available bytes of heaps.
size_t Available() {
const size_t size = Size();
return capacity_ < size ? 0 : capacity_ - size;
}
// Returns an indication of whether a pointer is in a space that has
// been allocated by this MemoryAllocator.
V8_INLINE bool IsOutsideAllocatedSpace(Address address) {
return address < lowest_ever_allocated_ ||
address >= highest_ever_allocated_;
}
// Returns a MemoryChunk in which the memory region from commit_area_size to
// reserve_area_size of the chunk area is reserved but not committed, it
// could be committed later by calling MemoryChunk::CommitArea.
V8_EXPORT_PRIVATE MemoryChunk* AllocateChunk(size_t reserve_area_size,
size_t commit_area_size,
Executability executable,
Space* space);
Address AllocateAlignedMemory(size_t reserve_size, size_t commit_size,
size_t alignment, Executability executable,
void* hint, VirtualMemory* controller);
void FreeMemory(v8::PageAllocator* page_allocator, Address addr, size_t size);
// Partially release |bytes_to_free| bytes starting at |start_free|. Note that
// internally memory is freed from |start_free| to the end of the reservation.
// Additional memory beyond the page is not accounted though, so
// |bytes_to_free| is computed by the caller.
void PartialFreeMemory(MemoryChunk* chunk, Address start_free,
size_t bytes_to_free, Address new_area_end);
// Checks if an allocated MemoryChunk was intended to be used for executable
// memory.
bool IsMemoryChunkExecutable(MemoryChunk* chunk) {
return executable_memory_.find(chunk) != executable_memory_.end();
}
// Commit memory region owned by given reservation object. Returns true if
// it succeeded and false otherwise.
bool CommitMemory(VirtualMemory* reservation);
// Uncommit memory region owned by given reservation object. Returns true if
// it succeeded and false otherwise.
bool UncommitMemory(VirtualMemory* reservation);
// Zaps a contiguous block of memory [start..(start+size)[ with
// a given zap value.
void ZapBlock(Address start, size_t size, uintptr_t zap_value);
V8_WARN_UNUSED_RESULT bool CommitExecutableMemory(VirtualMemory* vm,
Address start,
size_t commit_size,
size_t reserved_size);
// Page allocator instance for allocating non-executable pages.
// Guaranteed to be a valid pointer.
v8::PageAllocator* data_page_allocator() { return data_page_allocator_; }
// Page allocator instance for allocating executable pages.
// Guaranteed to be a valid pointer.
v8::PageAllocator* code_page_allocator() { return code_page_allocator_; }
// Returns page allocator suitable for allocating pages with requested
// executability.
v8::PageAllocator* page_allocator(Executability executable) {
return executable == EXECUTABLE ? code_page_allocator_
: data_page_allocator_;
}
// A region of memory that may contain executable code including reserved
// OS page with read-write access in the beginning.
const base::AddressRegion& code_range() const {
// |code_range_| >= |optional RW pages| + |code_page_allocator_instance_|
DCHECK_IMPLIES(!code_range_.is_empty(), code_page_allocator_instance_);
DCHECK_IMPLIES(!code_range_.is_empty(),
code_range_.contains(code_page_allocator_instance_->begin(),
code_page_allocator_instance_->size()));
return code_range_;
}
Unmapper* unmapper() { return &unmapper_; }
// Performs all necessary bookkeeping to free the memory, but does not free
// it.
void UnregisterMemory(MemoryChunk* chunk);
private:
void InitializeCodePageAllocator(v8::PageAllocator* page_allocator,
size_t requested);
// PreFreeMemory logically frees the object, i.e., it unregisters the memory,
// logs a delete event and adds the chunk to remembered unmapped pages.
void PreFreeMemory(MemoryChunk* chunk);
// PerformFreeMemory can be called concurrently when PreFree was executed
// before.
void PerformFreeMemory(MemoryChunk* chunk);
// See AllocatePage for public interface. Note that currently we only support
// pools for NOT_EXECUTABLE pages of size MemoryChunk::kPageSize.
template <typename SpaceType>
MemoryChunk* AllocatePagePooled(SpaceType* owner);
// Initializes pages in a chunk. Returns the first page address.
// This function and GetChunkId() are provided for the mark-compact
// collector to rebuild page headers in the from space, which is
// used as a marking stack and its page headers are destroyed.
Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk,
PagedSpace* owner);
void UpdateAllocatedSpaceLimits(Address low, Address high) {
// The use of atomic primitives does not guarantee correctness (wrt.
// desired semantics) by default. The loop here ensures that we update the
// values only if they did not change in between.
Address ptr = lowest_ever_allocated_.load(std::memory_order_relaxed);
while ((low < ptr) && !lowest_ever_allocated_.compare_exchange_weak(
ptr, low, std::memory_order_acq_rel)) {
}
ptr = highest_ever_allocated_.load(std::memory_order_relaxed);
while ((high > ptr) && !highest_ever_allocated_.compare_exchange_weak(
ptr, high, std::memory_order_acq_rel)) {
}
}
void RegisterExecutableMemoryChunk(MemoryChunk* chunk) {
DCHECK(chunk->IsFlagSet(MemoryChunk::IS_EXECUTABLE));
DCHECK_EQ(executable_memory_.find(chunk), executable_memory_.end());
executable_memory_.insert(chunk);
}
void UnregisterExecutableMemoryChunk(MemoryChunk* chunk) {
DCHECK_NE(executable_memory_.find(chunk), executable_memory_.end());
executable_memory_.erase(chunk);
chunk->heap()->UnregisterUnprotectedMemoryChunk(chunk);
}
Isolate* isolate_;
// This object controls virtual space reserved for code on the V8 heap. This
// is only valid for 64-bit architectures where kRequiresCodeRange.