1
2 #ifndef Py_INTERNAL_BACKOFF_H
3 #define Py_INTERNAL_BACKOFF_H
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7
8 #ifndef Py_BUILD_CORE
9 # error "this header requires Py_BUILD_CORE define"
10 #endif
11
12 #include <assert.h>
13 #include <stdbool.h>
14 #include <stdint.h>
15
16
17 typedef struct {
18 union {
19 struct {
20 uint16_t backoff : 4;
21 uint16_t value : 12;
22 };
23 uint16_t as_counter; // For printf("%#x", ...)
24 };
25 } _Py_BackoffCounter;
26
27
28 /* 16-bit countdown counters using exponential backoff.
29
30 These are used by the adaptive specializer to count down until
31 it is time to specialize an instruction. If specialization fails
32 the counter is reset using exponential backoff.
33
34 Another use is for the Tier 2 optimizer to decide when to create
35 a new Tier 2 trace (executor). Again, exponential backoff is used.
36
37 The 16-bit counter is structured as a 12-bit unsigned 'value'
38 and a 4-bit 'backoff' field. When resetting the counter, the
39 backoff field is incremented (until it reaches a limit) and the
40 value is set to a bit mask representing the value 2**backoff - 1.
41 The maximum backoff is 12 (the number of value bits).
42
43 There is an exceptional value which must not be updated, 0xFFFF.
44 */
45
46 #define UNREACHABLE_BACKOFF 0xFFFF
47
48 static inline bool
is_unreachable_backoff_counter(_Py_BackoffCounter counter)49 is_unreachable_backoff_counter(_Py_BackoffCounter counter)
50 {
51 return counter.as_counter == UNREACHABLE_BACKOFF;
52 }
53
54 static inline _Py_BackoffCounter
make_backoff_counter(uint16_t value,uint16_t backoff)55 make_backoff_counter(uint16_t value, uint16_t backoff)
56 {
57 assert(backoff <= 15);
58 assert(value <= 0xFFF);
59 _Py_BackoffCounter result;
60 result.value = value;
61 result.backoff = backoff;
62 return result;
63 }
64
65 static inline _Py_BackoffCounter
forge_backoff_counter(uint16_t counter)66 forge_backoff_counter(uint16_t counter)
67 {
68 _Py_BackoffCounter result;
69 result.as_counter = counter;
70 return result;
71 }
72
73 static inline _Py_BackoffCounter
restart_backoff_counter(_Py_BackoffCounter counter)74 restart_backoff_counter(_Py_BackoffCounter counter)
75 {
76 assert(!is_unreachable_backoff_counter(counter));
77 if (counter.backoff < 12) {
78 return make_backoff_counter((1 << (counter.backoff + 1)) - 1, counter.backoff + 1);
79 }
80 else {
81 return make_backoff_counter((1 << 12) - 1, 12);
82 }
83 }
84
85 static inline _Py_BackoffCounter
pause_backoff_counter(_Py_BackoffCounter counter)86 pause_backoff_counter(_Py_BackoffCounter counter)
87 {
88 return make_backoff_counter(counter.value | 1, counter.backoff);
89 }
90
91 static inline _Py_BackoffCounter
advance_backoff_counter(_Py_BackoffCounter counter)92 advance_backoff_counter(_Py_BackoffCounter counter)
93 {
94 if (!is_unreachable_backoff_counter(counter)) {
95 return make_backoff_counter((counter.value - 1) & 0xFFF, counter.backoff);
96 }
97 else {
98 return counter;
99 }
100 }
101
102 static inline bool
backoff_counter_triggers(_Py_BackoffCounter counter)103 backoff_counter_triggers(_Py_BackoffCounter counter)
104 {
105 return counter.value == 0;
106 }
107
108 /* Initial JUMP_BACKWARD counter.
109 * This determines when we create a trace for a loop.
110 * Backoff sequence 16, 32, 64, 128, 256, 512, 1024, 2048, 4096. */
111 #define JUMP_BACKWARD_INITIAL_VALUE 16
112 #define JUMP_BACKWARD_INITIAL_BACKOFF 4
113 static inline _Py_BackoffCounter
initial_jump_backoff_counter(void)114 initial_jump_backoff_counter(void)
115 {
116 return make_backoff_counter(JUMP_BACKWARD_INITIAL_VALUE,
117 JUMP_BACKWARD_INITIAL_BACKOFF);
118 }
119
120 /* Initial exit temperature.
121 * Must be larger than ADAPTIVE_COOLDOWN_VALUE,
122 * otherwise when a side exit warms up we may construct
123 * a new trace before the Tier 1 code has properly re-specialized.
124 * Backoff sequence 64, 128, 256, 512, 1024, 2048, 4096. */
125 #define COLD_EXIT_INITIAL_VALUE 64
126 #define COLD_EXIT_INITIAL_BACKOFF 6
127
128 static inline _Py_BackoffCounter
initial_temperature_backoff_counter(void)129 initial_temperature_backoff_counter(void)
130 {
131 return make_backoff_counter(COLD_EXIT_INITIAL_VALUE,
132 COLD_EXIT_INITIAL_BACKOFF);
133 }
134
135 /* Unreachable backoff counter. */
136 static inline _Py_BackoffCounter
initial_unreachable_backoff_counter(void)137 initial_unreachable_backoff_counter(void)
138 {
139 return forge_backoff_counter(UNREACHABLE_BACKOFF);
140 }
141
142 #ifdef __cplusplus
143 }
144 #endif
145 #endif /* !Py_INTERNAL_BACKOFF_H */
146