1#include <compiler/intrinsic.h>
2#include <mem/fixed_size_alloc.h>
3#include <stack_depot.h>
4#include <string.h>
5#include <sync/lock_chk_assert.h>
6#include <tsa.h>
7
8struct stack_depot_globals stack_depot_global = {0};
9FIXED_SIZE_RANGE_PERDOMAIN_DEFINE(
10 stack_depot, .obj_size = sizeof(struct stack_depot_record),
11 .obj_align = cc_alignof(struct stack_depot_record));
12static struct fixed_size_range boot_fsr;
13
14void stack_depot_init(void) {
15 stack_depot_global.starting_seed = 1234;
16 for (int i = 0; i < STACK_DEPOT_HASH_SIZE; i++) {
17 list_head_init(h: &stack_depot_global.chains[i].list);
18 spinlock_init(&stack_depot_global.chains[i].lock);
19 }
20
21 struct fixed_size_range_attributes attrs = {
22 .obj_size = sizeof(struct stack_depot_record),
23 .obj_align = cc_alignof(struct stack_depot_record),
24 .bootstrap_mode = false,
25 };
26
27 fixed_size_range_init(fsr: &boot_fsr, attrs: &attrs);
28}
29
30static struct stack_depot_record *
31record_chain_getref_locked(struct stack_depot_record_chain *this_chain,
32 uintptr_t *entries, size_t num_entries,
33 uint32_t hash) TSA_CALLER_HOLDS(&this_chain->lock) {
34 struct stack_depot_record *pos;
35 list_for_each_entry(pos, &this_chain->list, hash_list) {
36 if (pos->num_entries == num_entries && pos->hash == hash) {
37 if (!memcmp(pos->entries, entries,
38 num_entries * sizeof(uintptr_t))) {
39 /* This MUST NOT fail. If it does, that means some invariant
40 * has been broken, because refcount == 0 records exist
41 * outside the hashtable. Basically, on putref(), we spin_lock
42 * the record's hash chain, and then if refcount_dec_and_test,
43 * we remove it from the list and free */
44 enforce(refcount_inc_not_zero(&pos->refcount), STALE_REFERENCE);
45 return pos;
46 }
47 }
48 }
49
50 return NULL;
51}
52
53static struct stack_depot_record *
54record_chain_getref(struct stack_depot_record_chain *this_chain,
55 uintptr_t *entries, size_t num_entries, uint32_t hash) {
56 enum irql irql = spin_lock(&this_chain->lock);
57 struct stack_depot_record *rec =
58 record_chain_getref_locked(this_chain, entries, num_entries, hash);
59 spin_unlock(&this_chain->lock, irql);
60 return rec;
61}
62
63static stack_handle_t record_to_handle(struct stack_depot_record *rec) {
64 return rec;
65}
66
67static struct stack_depot_record *handle_to_record(stack_handle_t handle) {
68 return handle;
69}
70
71static struct stack_depot_record *record_alloc(void) {
72 if (!FSR_PERDOMAIN_ENABLED(stack_depot))
73 return fixed_size_alloc(fsr: &boot_fsr);
74
75 return FSR_PERDOMAIN_ALLOC(stack_depot);
76}
77
78static void record_free(struct stack_depot_record *rec) {
79 if (fixed_size_page_of(o: rec)->domain == DOMAIN_ID_NONE)
80 return fixed_size_free(fsr: &boot_fsr, obj: rec);
81
82 FSR_PERDOMAIN_FREE(stack_depot, rec);
83}
84
85struct stack_depot_record *stack_depot_get_record(stack_handle_t key) {
86 return key;
87}
88
89stack_handle_t stack_depot_save(uintptr_t *entries, size_t num_entries,
90 enum alloc_flags flags) {
91 cc_ignore(flags); /* TODO: not handled for now */
92
93 uint32_t hash = stack_depot_hash(entries, num_entries);
94 struct stack_depot_record_chain *this_chain =
95 &stack_depot_global.chains[hash % STACK_DEPOT_HASH_SIZE];
96
97 struct stack_depot_record *rec = NULL;
98
99 if ((rec = record_chain_getref(this_chain, entries, num_entries, hash)))
100 goto out;
101
102 if (!(rec = record_alloc()))
103 goto out;
104
105 enum irql irql = spin_lock(&this_chain->lock);
106
107 struct stack_depot_record *winner =
108 record_chain_getref_locked(this_chain, entries, num_entries, hash);
109 if (winner) {
110 spin_unlock(&this_chain->lock, irql);
111 record_free(rec);
112 rec = winner;
113 goto out;
114 }
115
116 refcount_init(rc: &rec->refcount, val: 1);
117 list_node_init(n: &rec->hash_list);
118 rec->hash = hash;
119 rec->num_entries = num_entries;
120 memcpy(rec->entries, entries, num_entries * sizeof(uintptr_t));
121 list_head_push_back(h: &this_chain->list, n: &rec->hash_list);
122 spin_unlock(&this_chain->lock, irql);
123
124 atomic_inc(&stack_depot_global.num_records);
125
126out:
127
128 return record_to_handle(rec);
129}
130
131size_t stack_depot_read(stack_handle_t key, uintptr_t *entries) {
132 struct stack_depot_record *rec = stack_depot_get_record(key);
133 if (!rec)
134 return 0;
135
136 memcpy(entries, rec->entries, rec->num_entries * sizeof(uintptr_t));
137 return rec->num_entries;
138}
139
140void stack_depot_print(stack_handle_t key) {
141 struct stack_depot_record *rec = stack_depot_get_record(key);
142 if (!rec)
143 return;
144
145 for (size_t i = 0; i < rec->num_entries; i++) {
146 printf(format: "%p ", (void *) rec->entries[i]);
147 }
148 printf(format: "\n");
149}
150
151void stack_depot_putref(stack_handle_t key) {
152 struct stack_depot_record *rec = handle_to_record(handle: key);
153 struct stack_depot_record_chain *chain =
154 &stack_depot_global.chains[rec->hash % STACK_DEPOT_HASH_SIZE];
155 bool free_it = false;
156
157 enum irql irql = spin_lock(&chain->lock);
158
159 if (refcount_dec_and_test(rc: &rec->refcount)) {
160 list_node_delete(n: &rec->hash_list);
161 free_it = true;
162 }
163
164 spin_unlock(&chain->lock, irql);
165
166 if (free_it) {
167 record_free(rec);
168 atomic_dec(&stack_depot_global.num_records);
169 }
170}
171
172stack_handle_t stack_depot_save_current(void) {
173 uintptr_t entries[STACK_TRACE_MAX_DEPTH] = {0};
174 size_t num_entries = stack_unwind(frame: (uint64_t) ci_frame_address(0), entries,
175 STACK_TRACE_MAX_DEPTH);
176 return stack_depot_save(entries, num_entries, ALLOC_FLAGS_DEFAULT);
177}
178