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