This repository has been archived by the owner on Jan 3, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 64
/
incminimark.py
3326 lines (3053 loc) · 152 KB
/
incminimark.py
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
"""Incremental version of the MiniMark GC.
Environment variables can be used to fine-tune the following parameters:
PYPY_GC_NURSERY The nursery size. Defaults to 1/2 of your cache or
'4M'. Small values
(like 1 or 1KB) are useful for debugging.
PYPY_GC_NURSERY_DEBUG If set to non-zero, will fill nursery with garbage,
to help debugging.
PYPY_GC_INCREMENT_STEP The size of memory marked during the marking step.
Default is size of nursery * 2. If you mark it too high
your GC is not incremental at all. The minimum is set
to size that survives minor collection * 1.5 so we
reclaim anything all the time.
PYPY_GC_MAJOR_COLLECT Major collection memory factor. Default is '1.82',
which means trigger a major collection when the
memory consumed equals 1.82 times the memory
really used at the end of the previous major
collection.
PYPY_GC_GROWTH Major collection threshold's max growth rate.
Default is '1.4'. Useful to collect more often
than normally on sudden memory growth, e.g. when
there is a temporary peak in memory usage.
PYPY_GC_MAX The max heap size. If coming near this limit, it
will first collect more often, then raise an
RPython MemoryError, and if that is not enough,
crash the program with a fatal error. Try values
like '1.6GB'.
PYPY_GC_MAX_DELTA The major collection threshold will never be set
to more than PYPY_GC_MAX_DELTA the amount really
used after a collection. Defaults to 1/8th of the
total RAM size (which is constrained to be at most
2/3/4GB on 32-bit systems). Try values like '200MB'.
PYPY_GC_MIN Don't collect while the memory size is below this
limit. Useful to avoid spending all the time in
the GC in very small programs. Defaults to 8
times the nursery.
PYPY_GC_DEBUG Enable extra checks around collections that are
too slow for normal use. Values are 0 (off),
1 (on major collections) or 2 (also on minor
collections).
PYPY_GC_MAX_PINNED The maximal number of pinned objects at any point
in time. Defaults to a conservative value depending
on nursery size and maximum object size inside the
nursery. Useful for debugging by setting it to 0.
"""
# XXX Should find a way to bound the major collection threshold by the
# XXX total addressable size. Maybe by keeping some minimarkpage arenas
# XXX pre-reserved, enough for a few nursery collections? What about
# XXX raw-malloced memory?
# XXX try merging old_objects_pointing_to_pinned into
# XXX old_objects_pointing_to_young (IRC 2014-10-22, fijal and gregor_w)
import sys
import os
import time
from rpython.rtyper.lltypesystem import lltype, llmemory, llarena, llgroup
from rpython.rtyper.lltypesystem.lloperation import llop
from rpython.rtyper.lltypesystem.llmemory import raw_malloc_usage
from rpython.memory.gc.base import GCBase, MovingGCBase
from rpython.memory.gc import env
from rpython.memory.support import mangle_hash
from rpython.rlib.rarithmetic import ovfcheck, LONG_BIT, intmask, r_uint
from rpython.rlib.rarithmetic import LONG_BIT_SHIFT
from rpython.rlib.debug import ll_assert, debug_print, debug_start, debug_stop
from rpython.rlib.objectmodel import specialize
from rpython.rlib import rgc
from rpython.memory.gc.minimarkpage import out_of_memory
#
# Handles the objects in 2 generations:
#
# * young objects: allocated in the nursery if they are not too large, or
# raw-malloced otherwise. The nursery is a fixed-size memory buffer of
# 4MB by default. When full, we do a minor collection;
# - surviving objects from the nursery are moved outside and become old,
# - non-surviving raw-malloced objects are freed,
# - and pinned objects are kept at their place inside the nursery and stay
# young.
#
# * old objects: never move again. These objects are either allocated by
# minimarkpage.py (if they are small), or raw-malloced (if they are not
# small). Collected by regular mark-n-sweep during major collections.
#
WORD = LONG_BIT // 8
first_gcflag = 1 << (LONG_BIT//2)
# The following flag is set on objects if we need to do something to
# track the young pointers that it might contain. The flag is not set
# on young objects (unless they are large arrays, see below), and we
# simply assume that any young object can point to any other young object.
# For old and prebuilt objects, the flag is usually set, and is cleared
# when we write any pointer to it. For large arrays with
# GCFLAG_HAS_CARDS, we rely on card marking to track where the
# young pointers are; the flag GCFLAG_TRACK_YOUNG_PTRS is set in this
# case too, to speed up the write barrier.
GCFLAG_TRACK_YOUNG_PTRS = first_gcflag << 0
# The following flag is set on some prebuilt objects. The flag is set
# unless the object is already listed in 'prebuilt_root_objects'.
# When a pointer is written inside an object with GCFLAG_NO_HEAP_PTRS
# set, the write_barrier clears the flag and adds the object to
# 'prebuilt_root_objects'.
GCFLAG_NO_HEAP_PTRS = first_gcflag << 1
# The following flag is set on surviving objects during a major collection.
GCFLAG_VISITED = first_gcflag << 2
# The following flag is set on nursery objects of which we asked the id
# or the identityhash. It means that a space of the size of the object
# has already been allocated in the nonmovable part.
GCFLAG_HAS_SHADOW = first_gcflag << 3
# The following flag is set temporarily on some objects during a major
# collection. See pypy/doc/discussion/finalizer-order.txt
GCFLAG_FINALIZATION_ORDERING = first_gcflag << 4
# This flag is reserved for RPython.
GCFLAG_EXTRA = first_gcflag << 5
# The following flag is set on externally raw_malloc'ed arrays of pointers.
# They are allocated with some extra space in front of them for a bitfield,
# one bit per 'card_page_indices' indices.
GCFLAG_HAS_CARDS = first_gcflag << 6
GCFLAG_CARDS_SET = first_gcflag << 7 # <- at least one card bit is set
# note that GCFLAG_CARDS_SET is the most significant bit of a byte:
# this is required for the JIT (x86)
# The following flag is set on surviving raw-malloced young objects during
# a minor collection.
GCFLAG_VISITED_RMY = first_gcflag << 8
# The following flag is set on nursery objects to keep them in the nursery.
# This means that a young object with this flag is not moved out
# of the nursery during a minor collection. See pin()/unpin() for further
# details.
GCFLAG_PINNED = first_gcflag << 9
# The following flag is set only on objects outside the nursery
# (i.e. old objects). Therefore we can reuse GCFLAG_PINNED as it is used for
# the same feature (object pinning) and GCFLAG_PINNED is only used on nursery
# objects.
# If this flag is set, the flagged object is already an element of
# 'old_objects_pointing_to_pinned' and doesn't have to be added again.
GCFLAG_PINNED_OBJECT_PARENT_KNOWN = GCFLAG_PINNED
# record that ignore_finalizer() has been called
GCFLAG_IGNORE_FINALIZER = first_gcflag << 10
# shadow objects can have its memory initialized when it is created.
# It does not need an additional copy in trace out
GCFLAG_SHADOW_INITIALIZED = first_gcflag << 11
# another flag set only on specific objects: the ll_dummy_value from
# rpython.rtyper.rmodel
GCFLAG_DUMMY = first_gcflag << 12
_GCFLAG_FIRST_UNUSED = first_gcflag << 13 # the first unused bit
# States for the incremental GC
# The scanning phase, next step call will scan the current roots
# This state must complete in a single step
STATE_SCANNING = 0
# The marking phase. We walk the list 'objects_to_trace' of all gray objects
# and mark all of the things they point to gray. This step lasts until there
# are no more gray objects. ('objects_to_trace' never contains pinned objs.)
STATE_MARKING = 1
# here we kill all the unvisited objects
STATE_SWEEPING = 2
# here we call all the finalizers
STATE_FINALIZING = 3
GC_STATES = ['SCANNING', 'MARKING', 'SWEEPING', 'FINALIZING']
FORWARDSTUB = lltype.GcStruct('forwarding_stub',
('forw', llmemory.Address))
FORWARDSTUBPTR = lltype.Ptr(FORWARDSTUB)
NURSARRAY = lltype.Array(llmemory.Address)
# ____________________________________________________________
class IncrementalMiniMarkGC(MovingGCBase):
_alloc_flavor_ = "raw"
inline_simple_malloc = True
inline_simple_malloc_varsize = True
needs_write_barrier = True
prebuilt_gc_objects_are_static_roots = False
can_usually_pin_objects = True
malloc_zero_filled = False
gcflag_extra = GCFLAG_EXTRA
gcflag_dummy = GCFLAG_DUMMY
# All objects start with a HDR, i.e. with a field 'tid' which contains
# a word. This word is divided in two halves: the lower half contains
# the typeid, and the upper half contains various flags, as defined
# by GCFLAG_xxx above.
HDR = lltype.Struct('header', ('tid', lltype.Signed))
typeid_is_in_field = 'tid'
# During a minor collection, the objects in the nursery that are
# moved outside are changed in-place: their header is replaced with
# the value -42, and the following word is set to the address of
# where the object was moved. This means that all objects in the
# nursery need to be at least 2 words long, but objects outside the
# nursery don't need to.
minimal_size_in_nursery = (
llmemory.sizeof(HDR) + llmemory.sizeof(llmemory.Address))
TRANSLATION_PARAMS = {
# Automatically adjust the size of the nursery and the
# 'major_collection_threshold' from the environment.
# See docstring at the start of the file.
"read_from_env": True,
# The size of the nursery. Note that this is only used as a
# fall-back number.
"nursery_size": 896*1024,
# The system page size. Like malloc, we assume that it is 4K
# for 32-bit systems; unlike malloc, we assume that it is 8K
# for 64-bit systems, for consistent results.
"page_size": 1024*WORD,
# The size of an arena. Arenas are groups of pages allocated
# together.
"arena_size": 65536*WORD,
# The maximum size of an object allocated compactly. All objects
# that are larger are just allocated with raw_malloc(). Note that
# the size limit for being first allocated in the nursery is much
# larger; see below.
"small_request_threshold": 35*WORD,
# Full collection threshold: after a major collection, we record
# the total size consumed; and after every minor collection, if the
# total size is now more than 'major_collection_threshold' times,
# we trigger the next major collection.
"major_collection_threshold": 1.82,
# Threshold to avoid that the total heap size grows by a factor of
# major_collection_threshold at every collection: it can only
# grow at most by the following factor from one collection to the
# next. Used e.g. when there is a sudden, temporary peak in memory
# usage; this avoids that the upper bound grows too fast.
"growth_rate_max": 1.4,
# The number of array indices that are mapped to a single bit in
# write_barrier_from_array(). Must be a power of two. The default
# value of 128 means that card pages are 512 bytes (1024 on 64-bits)
# in regular arrays of pointers; more in arrays whose items are
# larger. A value of 0 disables card marking.
"card_page_indices": 128,
# Objects whose total size is at least 'large_object' bytes are
# allocated out of the nursery immediately, as old objects. The
# minimal allocated size of the nursery is 2x the following
# number (by default, at least 132KB on 32-bit and 264KB on 64-bit).
"large_object": (16384+512)*WORD,
}
def __init__(self, config,
read_from_env=False,
nursery_size=32*WORD,
nursery_cleanup=9*WORD,
page_size=16*WORD,
arena_size=64*WORD,
small_request_threshold=5*WORD,
major_collection_threshold=2.5,
growth_rate_max=2.5, # for tests
card_page_indices=0,
large_object=8*WORD,
ArenaCollectionClass=None,
**kwds):
"NOT_RPYTHON"
MovingGCBase.__init__(self, config, **kwds)
assert small_request_threshold % WORD == 0
self.read_from_env = read_from_env
self.nursery_size = nursery_size
self.small_request_threshold = small_request_threshold
self.major_collection_threshold = major_collection_threshold
self.growth_rate_max = growth_rate_max
self.num_major_collects = 0
self.min_heap_size = 0.0
self.max_heap_size = 0.0
self.max_heap_size_already_raised = False
self.max_delta = float(r_uint(-1))
self.max_number_of_pinned_objects = 0 # computed later
#
self.card_page_indices = card_page_indices
if self.card_page_indices > 0:
self.card_page_shift = 0
while (1 << self.card_page_shift) < self.card_page_indices:
self.card_page_shift += 1
#
# 'large_object' limit how big objects can be in the nursery, so
# it gives a lower bound on the allowed size of the nursery.
self.nonlarge_max = large_object - 1
#
self.nursery = llmemory.NULL
self.nursery_free = llmemory.NULL
self.nursery_top = llmemory.NULL
self.debug_tiny_nursery = -1
self.debug_rotating_nurseries = lltype.nullptr(NURSARRAY)
self.extra_threshold = 0
#
# The ArenaCollection() handles the nonmovable objects allocation.
if ArenaCollectionClass is None:
from rpython.memory.gc import minimarkpage
ArenaCollectionClass = minimarkpage.ArenaCollection
self.ac = ArenaCollectionClass(arena_size, page_size,
small_request_threshold)
#
# Used by minor collection: a list of (mostly non-young) objects that
# (may) contain a pointer to a young object. Populated by
# the write barrier: when we clear GCFLAG_TRACK_YOUNG_PTRS, we
# add it to this list.
# Note that young array objects may (by temporary "mistake") be added
# to this list, but will be removed again at the start of the next
# minor collection.
self.old_objects_pointing_to_young = self.AddressStack()
#
# Similar to 'old_objects_pointing_to_young', but lists objects
# that have the GCFLAG_CARDS_SET bit. For large arrays. Note
# that it is possible for an object to be listed both in here
# and in 'old_objects_pointing_to_young', in which case we
# should just clear the cards and trace it fully, as usual.
# Note also that young array objects are never listed here.
self.old_objects_with_cards_set = self.AddressStack()
#
# A list of all prebuilt GC objects that contain pointers to the heap
self.prebuilt_root_objects = self.AddressStack()
#
self._init_writebarrier_logic()
#
# The size of all the objects turned from 'young' to 'old'
# since we started the last major collection cycle. This is
# used to track progress of the incremental GC: normally, we
# run one major GC step after each minor collection, but if a
# lot of objects are made old, we need run two or more steps.
# Otherwise the risk is that we create old objects faster than
# we're collecting them. The 'threshold' is incremented after
# each major GC step at a fixed rate; the idea is that as long
# as 'size_objects_made_old > threshold_objects_made_old' then
# we must do more major GC steps. See major_collection_step()
# for more details.
self.size_objects_made_old = r_uint(0)
self.threshold_objects_made_old = r_uint(0)
def setup(self):
"""Called at run-time to initialize the GC."""
#
# Hack: MovingGCBase.setup() sets up stuff related to id(), which
# we implement differently anyway. So directly call GCBase.setup().
GCBase.setup(self)
#
# Two lists of all raw_malloced objects (the objects too large)
self.young_rawmalloced_objects = self.null_address_dict()
self.old_rawmalloced_objects = self.AddressStack()
self.raw_malloc_might_sweep = self.AddressStack()
self.rawmalloced_total_size = r_uint(0)
self.rawmalloced_peak_size = r_uint(0)
self.total_gc_time = 0.0
self.gc_state = STATE_SCANNING
# if the GC is disabled, it runs only minor collections; major
# collections need to be manually triggered by explicitly calling
# collect()
self.enabled = True
#
# Two lists of all objects with finalizers. Actually they are lists
# of pairs (finalization_queue_nr, object). "probably young objects"
# are all traced and moved to the "old" list by the next minor
# collection.
self.probably_young_objects_with_finalizers = self.AddressDeque()
self.old_objects_with_finalizers = self.AddressDeque()
p = lltype.malloc(self._ADDRARRAY, 1, flavor='raw',
track_allocation=False)
self.singleaddr = llmemory.cast_ptr_to_adr(p)
#
# Two lists of all objects with destructors.
self.young_objects_with_destructors = self.AddressStack()
self.old_objects_with_destructors = self.AddressStack()
#
# Two lists of the objects with weakrefs. No weakref can be an
# old object weakly pointing to a young object: indeed, weakrefs
# are immutable so they cannot point to an object that was
# created after it.
self.young_objects_with_weakrefs = self.AddressStack()
self.old_objects_with_weakrefs = self.AddressStack()
#
# Support for id and identityhash: map nursery objects with
# GCFLAG_HAS_SHADOW to their future location at the next
# minor collection.
self.nursery_objects_shadows = self.AddressDict()
#
# A sorted deque containing addresses of pinned objects.
# This collection is used to make sure we don't overwrite pinned objects.
# Each minor collection creates a new deque containing the active pinned
# objects. The addresses are used to set the next 'nursery_top'.
self.nursery_barriers = self.AddressDeque()
#
# Counter tracking how many pinned objects currently reside inside
# the nursery.
self.pinned_objects_in_nursery = 0
#
# This flag is set if the previous minor collection found at least
# one pinned object alive.
self.any_pinned_object_kept = False
#
# Keeps track of old objects pointing to pinned objects. These objects
# must be traced every minor collection. Without tracing them the
# referenced pinned object wouldn't be visited and therefore collected.
self.old_objects_pointing_to_pinned = self.AddressStack()
self.updated_old_objects_pointing_to_pinned = False
#
# Allocate a nursery. In case of auto_nursery_size, start by
# allocating a very small nursery, enough to do things like look
# up the env var, which requires the GC; and then really
# allocate the nursery of the final size.
if not self.read_from_env:
self.allocate_nursery()
self.gc_increment_step = self.nursery_size * 4
self.gc_nursery_debug = False
else:
#
defaultsize = self.nursery_size
minsize = 2 * (self.nonlarge_max + 1)
self.nursery_size = minsize
self.allocate_nursery()
#
# From there on, the GC is fully initialized and the code
# below can use it
newsize = env.read_from_env('PYPY_GC_NURSERY')
# PYPY_GC_NURSERY=smallvalue means that minor collects occur
# very frequently; the extreme case is PYPY_GC_NURSERY=1, which
# forces a minor collect for every malloc. Useful to debug
# external factors, like trackgcroot or the handling of the write
# barrier. Implemented by still using 'minsize' for the nursery
# size (needed to handle mallocs just below 'large_objects') but
# hacking at the current nursery position in collect_and_reserve().
if newsize <= 0:
newsize = env.estimate_best_nursery_size()
if newsize <= 0:
newsize = defaultsize
if newsize < minsize:
self.debug_tiny_nursery = newsize & ~(WORD-1)
newsize = minsize
#
major_coll = env.read_float_from_env('PYPY_GC_MAJOR_COLLECT')
if major_coll > 1.0:
self.major_collection_threshold = major_coll
#
growth = env.read_float_from_env('PYPY_GC_GROWTH')
if growth > 1.0:
self.growth_rate_max = growth
#
min_heap_size = env.read_uint_from_env('PYPY_GC_MIN')
if min_heap_size > 0:
self.min_heap_size = float(min_heap_size)
else:
# defaults to 8 times the nursery
self.min_heap_size = newsize * 8
#
max_heap_size = env.read_uint_from_env('PYPY_GC_MAX')
if max_heap_size > 0:
self.max_heap_size = float(max_heap_size)
#
max_delta = env.read_uint_from_env('PYPY_GC_MAX_DELTA')
if max_delta > 0:
self.max_delta = float(max_delta)
else:
self.max_delta = 0.125 * env.get_total_memory()
gc_increment_step = env.read_uint_from_env('PYPY_GC_INCREMENT_STEP')
if gc_increment_step > 0:
self.gc_increment_step = gc_increment_step
else:
self.gc_increment_step = newsize * 4
#
nursery_debug = env.read_uint_from_env('PYPY_GC_NURSERY_DEBUG')
if nursery_debug > 0:
self.gc_nursery_debug = True
else:
self.gc_nursery_debug = False
self._minor_collection() # to empty the nursery
llarena.arena_free(self.nursery)
self.nursery_size = newsize
self.allocate_nursery()
#
env_max_number_of_pinned_objects = os.environ.get('PYPY_GC_MAX_PINNED')
if env_max_number_of_pinned_objects:
try:
env_max_number_of_pinned_objects = int(env_max_number_of_pinned_objects)
except ValueError:
env_max_number_of_pinned_objects = 0
#
if env_max_number_of_pinned_objects >= 0: # 0 allows to disable pinning completely
self.max_number_of_pinned_objects = env_max_number_of_pinned_objects
else:
# Estimate this number conservatively
bigobj = self.nonlarge_max + 1
self.max_number_of_pinned_objects = self.nursery_size / (bigobj * 2)
def enable(self):
self.enabled = True
def disable(self):
self.enabled = False
def isenabled(self):
return self.enabled
def _nursery_memory_size(self):
extra = self.nonlarge_max + 1
return self.nursery_size + extra
def _alloc_nursery(self):
# the start of the nursery: we actually allocate a bit more for
# the nursery than really needed, to simplify pointer arithmetic
# in malloc_fixedsize(). The few extra pages are never used
# anyway so it doesn't even count.
nursery = llarena.arena_malloc(self._nursery_memory_size(), 0)
if not nursery:
out_of_memory("cannot allocate nursery")
return nursery
def allocate_nursery(self):
debug_start("gc-set-nursery-size")
debug_print("nursery size:", self.nursery_size)
self.nursery = self._alloc_nursery()
# the current position in the nursery:
self.nursery_free = self.nursery
# the end of the nursery:
self.nursery_top = self.nursery + self.nursery_size
# initialize the threshold
self.min_heap_size = max(self.min_heap_size, self.nursery_size *
self.major_collection_threshold)
# the following two values are usually equal, but during raw mallocs
# with memory pressure accounting, next_major_collection_threshold
# is decremented to make the next major collection arrive earlier.
# See translator/c/test/test_newgc, test_nongc_attached_to_gc
self.next_major_collection_initial = self.min_heap_size
self.next_major_collection_threshold = self.min_heap_size
self.set_major_threshold_from(0.0)
ll_assert(self.extra_threshold == 0, "extra_threshold set too early")
debug_stop("gc-set-nursery-size")
def set_major_threshold_from(self, threshold, reserving_size=0):
# Set the next_major_collection_threshold.
threshold_max = (self.next_major_collection_initial *
self.growth_rate_max)
if threshold > threshold_max:
threshold = threshold_max
#
threshold += reserving_size
if threshold < self.min_heap_size:
threshold = self.min_heap_size
#
if self.max_heap_size > 0.0 and threshold > self.max_heap_size:
threshold = self.max_heap_size
bounded = True
else:
bounded = False
#
self.next_major_collection_initial = threshold
self.next_major_collection_threshold = threshold
return bounded
def post_setup(self):
# set up extra stuff for PYPY_GC_DEBUG.
MovingGCBase.post_setup(self)
if self.DEBUG and llarena.has_protect:
# gc debug mode: allocate 7 nurseries instead of just 1,
# and use them alternatively, while mprotect()ing the unused
# ones to detect invalid access.
debug_start("gc-debug")
self.debug_rotating_nurseries = lltype.malloc(
NURSARRAY, 6, flavor='raw', track_allocation=False)
i = 0
while i < 6:
nurs = self._alloc_nursery()
llarena.arena_protect(nurs, self._nursery_memory_size(), True)
self.debug_rotating_nurseries[i] = nurs
i += 1
debug_print("allocated", len(self.debug_rotating_nurseries),
"extra nurseries")
debug_stop("gc-debug")
def debug_rotate_nursery(self):
if self.debug_rotating_nurseries:
debug_start("gc-debug")
oldnurs = self.nursery
llarena.arena_protect(oldnurs, self._nursery_memory_size(), True)
#
newnurs = self.debug_rotating_nurseries[0]
i = 0
while i < len(self.debug_rotating_nurseries) - 1:
self.debug_rotating_nurseries[i] = (
self.debug_rotating_nurseries[i + 1])
i += 1
self.debug_rotating_nurseries[i] = oldnurs
#
llarena.arena_protect(newnurs, self._nursery_memory_size(), False)
self.nursery = newnurs
self.nursery_top = self.nursery + self.nursery_size
debug_print("switching from nursery", oldnurs,
"to nursery", self.nursery,
"size", self.nursery_size)
debug_stop("gc-debug")
def malloc_fixedsize(self, typeid, size,
needs_finalizer=False,
is_finalizer_light=False,
contains_weakptr=False):
size_gc_header = self.gcheaderbuilder.size_gc_header
totalsize = size_gc_header + size
rawtotalsize = raw_malloc_usage(totalsize)
#
# If the object needs a finalizer, ask for a rawmalloc.
# The following check should be constant-folded.
if needs_finalizer and not is_finalizer_light:
# old-style finalizers only!
ll_assert(not contains_weakptr,
"'needs_finalizer' and 'contains_weakptr' both specified")
obj = self.external_malloc(typeid, 0, alloc_young=False)
res = llmemory.cast_adr_to_ptr(obj, llmemory.GCREF)
self.register_finalizer(-1, res)
return res
#
# If totalsize is greater than nonlarge_max (which should never be
# the case in practice), ask for a rawmalloc. The following check
# should be constant-folded.
if rawtotalsize > self.nonlarge_max:
ll_assert(not contains_weakptr,
"'contains_weakptr' specified for a large object")
obj = self.external_malloc(typeid, 0, alloc_young=True)
#
else:
# If totalsize is smaller than minimal_size_in_nursery, round it
# up. The following check should also be constant-folded.
min_size = raw_malloc_usage(self.minimal_size_in_nursery)
if rawtotalsize < min_size:
totalsize = rawtotalsize = min_size
#
# Get the memory from the nursery. If there is not enough space
# there, do a collect first.
result = self.nursery_free
ll_assert(result != llmemory.NULL, "uninitialized nursery")
self.nursery_free = new_free = result + totalsize
if new_free > self.nursery_top:
result = self.collect_and_reserve(totalsize)
#
# Build the object.
llarena.arena_reserve(result, totalsize)
obj = result + size_gc_header
self.init_gc_object(result, typeid, flags=0)
#
# If it is a weakref or has a lightweight destructor, record it
# (checks constant-folded).
if needs_finalizer:
self.young_objects_with_destructors.append(obj)
if contains_weakptr:
self.young_objects_with_weakrefs.append(obj)
return llmemory.cast_adr_to_ptr(obj, llmemory.GCREF)
def malloc_varsize(self, typeid, length, size, itemsize,
offset_to_length):
size_gc_header = self.gcheaderbuilder.size_gc_header
nonvarsize = size_gc_header + size
#
# Compute the maximal length that makes the object still
# below 'nonlarge_max'. All the following logic is usually
# constant-folded because self.nonlarge_max, size and itemsize
# are all constants (the arguments are constant due to
# inlining).
maxsize = self.nonlarge_max - raw_malloc_usage(nonvarsize)
if maxsize < 0:
toobig = r_uint(0) # the nonvarsize alone is too big
elif raw_malloc_usage(itemsize):
toobig = r_uint(maxsize // raw_malloc_usage(itemsize)) + 1
else:
toobig = r_uint(sys.maxint) + 1
if r_uint(length) >= r_uint(toobig):
#
# If the total size of the object would be larger than
# 'nonlarge_max', then allocate it externally. We also
# go there if 'length' is actually negative.
obj = self.external_malloc(typeid, length, alloc_young=True)
#
else:
# With the above checks we know now that totalsize cannot be more
# than 'nonlarge_max'; in particular, the + and * cannot overflow.
totalsize = nonvarsize + itemsize * length
totalsize = llarena.round_up_for_allocation(totalsize)
#
# 'totalsize' should contain at least the GC header and
# the length word, so it should never be smaller than
# 'minimal_size_in_nursery'
ll_assert(raw_malloc_usage(totalsize) >=
raw_malloc_usage(self.minimal_size_in_nursery),
"malloc_varsize(): totalsize < minimalsize")
#
# Get the memory from the nursery. If there is not enough space
# there, do a collect first.
result = self.nursery_free
ll_assert(result != llmemory.NULL, "uninitialized nursery")
self.nursery_free = new_free = result + totalsize
if new_free > self.nursery_top:
result = self.collect_and_reserve(totalsize)
#
# Build the object.
llarena.arena_reserve(result, totalsize)
self.init_gc_object(result, typeid, flags=0)
#
# Set the length and return the object.
obj = result + size_gc_header
(obj + offset_to_length).signed[0] = length
#
return llmemory.cast_adr_to_ptr(obj, llmemory.GCREF)
def malloc_fixed_or_varsize_nonmovable(self, typeid, length):
# length==0 for fixedsize
obj = self.external_malloc(typeid, length, alloc_young=True)
return llmemory.cast_adr_to_ptr(obj, llmemory.GCREF)
def move_out_of_nursery(self, obj):
# called twice, it should return the same shadow object,
# and not creating another shadow object. As a safety feature,
# when called on a non-nursery object, do nothing.
if not self.is_in_nursery(obj):
return obj
shadow = self._find_shadow(obj)
if (self.header(obj).tid & GCFLAG_SHADOW_INITIALIZED) == 0:
self.header(obj).tid |= GCFLAG_SHADOW_INITIALIZED
totalsize = self.get_size(obj)
llmemory.raw_memcopy(obj, shadow, totalsize)
return shadow
def collect(self, gen=2):
"""Do a minor (gen=0), start a major (gen=1), or do a full
major (gen>=2) collection."""
if gen < 0:
# Dangerous! this makes no progress on the major GC cycle.
# If called too often, the memory usage will keep increasing,
# because we'll never completely fill the nursery (and so
# never run anything about the major collection).
self._minor_collection()
elif gen == 0:
# This runs a minor collection. This is basically what occurs
# when the nursery is full. If a major collection is in
# progress, it also runs one more step of it. It might also
# decide to start a major collection just now, depending on
# current memory pressure.
self.minor_collection_with_major_progress(force_enabled=True)
elif gen == 1:
# This is like gen == 0, but if no major collection is running,
# then it forces one to start now.
self.minor_collection_with_major_progress(force_enabled=True)
if self.gc_state == STATE_SCANNING:
self.major_collection_step()
else:
# This does a complete minor and major collection.
self.minor_and_major_collection()
self.rrc_invoke_callback()
def collect_step(self):
"""
Do a single major collection step. Return True when the major collection
is completed.
This is meant to be used together with gc.disable(), to have a
fine-grained control on when the GC runs.
"""
old_state = self.gc_state
self._minor_collection()
self.major_collection_step()
self.rrc_invoke_callback()
return rgc._encode_states(old_state, self.gc_state)
def minor_collection_with_major_progress(self, extrasize=0,
force_enabled=False):
"""Do a minor collection. Then, if the GC is enabled and there
is already a major GC in progress, run at least one major collection
step. If there is no major GC but the threshold is reached, start a
major GC.
"""
self._minor_collection()
if not self.enabled and not force_enabled:
return
# If the gc_state is STATE_SCANNING, we're not in the middle
# of an incremental major collection. In that case, wait
# until there is too much garbage before starting the next
# major collection. But if we are in the middle of an
# incremental major collection, then always do (at least) one
# step now.
#
# Within a major collection cycle, every call to
# major_collection_step() increments
# 'threshold_objects_made_old' by nursery_size/2.
if self.gc_state != STATE_SCANNING or self.threshold_reached(extrasize):
self.major_collection_step(extrasize)
# See documentation in major_collection_step() for target invariants
while self.gc_state != STATE_SCANNING: # target (A1)
threshold = self.threshold_objects_made_old
if threshold >= r_uint(extrasize):
threshold -= r_uint(extrasize) # (*)
if self.size_objects_made_old <= threshold: # target (A2)
break
# Note that target (A2) is tweaked by (*); see
# test_gc_set_max_heap_size in translator/c, test_newgc.py
self._minor_collection()
self.major_collection_step(extrasize)
self.rrc_invoke_callback()
def collect_and_reserve(self, totalsize):
"""To call when nursery_free overflows nursery_top.
First check if pinned objects are in front of nursery_top. If so,
jump over the pinned object and try again to reserve totalsize.
Otherwise do a minor collection, and possibly some steps of a
major collection, and finally reserve totalsize bytes.
"""
minor_collection_count = 0
while True:
self.nursery_free = llmemory.NULL # debug: don't use me
# note: no "raise MemoryError" between here and the next time
# we initialize nursery_free!
if self.nursery_barriers.non_empty():
# Pinned object in front of nursery_top. Try reserving totalsize
# by jumping into the next, yet unused, area inside the
# nursery. "Next area" in this case is the space between the
# pinned object in front of nusery_top and the pinned object
# after that. Graphically explained:
#
# |- allocating totalsize failed in this area
# | |- nursery_top
# | | |- pinned object in front of nursery_top,
# v v v jump over this
# +---------+--------+--------+--------+-----------+ }
# | used | pinned | empty | pinned | empty | }- nursery
# +---------+--------+--------+--------+-----------+ }
# ^- try reserving totalsize in here next
#
# All pinned objects are represented by entries in
# nursery_barriers (see minor_collection). The last entry is
# always the end of the nursery. Therefore if nursery_barriers
# contains only one element, we jump over a pinned object and
# the "next area" (the space where we will try to allocate
# totalsize) starts at the end of the pinned object and ends at
# nursery's end.
#
# find the size of the pinned object after nursery_top
size_gc_header = self.gcheaderbuilder.size_gc_header
pinned_obj_size = size_gc_header + self.get_size(
self.nursery_top + size_gc_header)
#
# update used nursery space to allocate objects
self.nursery_free = self.nursery_top + pinned_obj_size
self.nursery_top = self.nursery_barriers.popleft()
else:
minor_collection_count += 1
if minor_collection_count == 1:
self.minor_collection_with_major_progress()
else:
# Nursery too full again. This is likely because of
# execute_finalizers() or rrc_invoke_callback().
# we need to fix it with another call to minor_collection()
# ---this time only the minor part so that we are sure that
# the nursery is empty (apart from pinned objects).
#
# Note that this still works with the counters:
# 'size_objects_made_old' will be increased by
# the _minor_collection() below. We don't
# immediately restore the target invariant that
# 'size_objects_made_old <= threshold_objects_made_old'.
# But we will do it in the next call to
# minor_collection_with_major_progress().
#
ll_assert(minor_collection_count == 2,
"Calling minor_collection() twice is not "
"enough. Too many pinned objects?")
self._minor_collection()
#
# Tried to do something about nursery_free overflowing
# nursery_top before this point. Try to reserve totalsize now.
# If this succeeds break out of loop.
result = self.nursery_free
if self.nursery_free + totalsize <= self.nursery_top:
self.nursery_free = result + totalsize
ll_assert(self.nursery_free <= self.nursery_top, "nursery overflow")
break
#
#
if self.debug_tiny_nursery >= 0: # for debugging
if self.nursery_top - self.nursery_free > self.debug_tiny_nursery:
self.nursery_free = self.nursery_top - self.debug_tiny_nursery
#
return result
collect_and_reserve._dont_inline_ = True
# XXX kill alloc_young and make it always True
def external_malloc(self, typeid, length, alloc_young):
"""Allocate a large object using the ArenaCollection or
raw_malloc(), possibly as an object with card marking enabled,
if it has gc pointers in its var-sized part. 'length' should be
specified as 0 if the object is not varsized. The returned
object is fully initialized, but not zero-filled."""
#
# Here we really need a valid 'typeid', not 0 (as the JIT might
# try to send us if there is still a bug).
ll_assert(bool(self.combine(typeid, 0)),
"external_malloc: typeid == 0")
#
# Compute the total size, carefully checking for overflows.
size_gc_header = self.gcheaderbuilder.size_gc_header
nonvarsize = size_gc_header + self.fixed_size(typeid)
if length == 0:
# this includes the case of fixed-size objects, for which we
# should not even ask for the varsize_item_sizes().
totalsize = nonvarsize
elif length > 0:
# var-sized allocation with at least one item
itemsize = self.varsize_item_sizes(typeid)
try:
varsize = ovfcheck(itemsize * length)
totalsize = ovfcheck(nonvarsize + varsize)
except OverflowError:
raise MemoryError
else:
# negative length! This likely comes from an overflow
# earlier. We will just raise MemoryError here.
raise MemoryError
#
# If somebody calls this function a lot, we must eventually
# force a collection. We use threshold_reached(), which might
# be true now but become false at some point after a few calls
# to major_collection_step(). If there is really no memory,
# then when the major collection finishes it will raise
# MemoryError.
if self.threshold_reached(raw_malloc_usage(totalsize)):
self.minor_collection_with_major_progress(
raw_malloc_usage(totalsize) + self.nursery_size // 2)
#
# Check if the object would fit in the ArenaCollection.
# Also, an object allocated from ArenaCollection must be old.
if (raw_malloc_usage(totalsize) <= self.small_request_threshold
and not alloc_young):
#
# Yes. Round up 'totalsize' (it cannot overflow and it
# must remain <= self.small_request_threshold.)
totalsize = llarena.round_up_for_allocation(totalsize)
ll_assert(raw_malloc_usage(totalsize) <=
self.small_request_threshold,
"rounding up made totalsize > small_request_threshold")
#
# Allocate from the ArenaCollection. Don't clear it.
result = self.ac.malloc(totalsize)
#
extra_flags = GCFLAG_TRACK_YOUNG_PTRS
#
else:
# No, so proceed to allocate it externally with raw_malloc().
# Check if we need to introduce the card marker bits area.