jonaskruckenberg.de
Next Generation WASM Microkernel Operating System
wasm
os
rust
microkernel
1// Copyright 2025 Jonas Kruckenberg
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8use alloc::boxed::Box;
9use alloc::string::{String, ToString};
10use alloc::vec::Vec;
11use core::cmp::Ordering;
12use core::mem;
13use core::num::NonZeroU64;
14
15use crate::{Error, LazyResult, Location};
16
17pub(crate) struct LazyLines(LazyResult<Lines>);
18
19impl LazyLines {
20 pub(crate) fn new() -> Self {
21 LazyLines(LazyResult::new())
22 }
23
24 pub(crate) fn borrow<R: gimli::Reader>(
25 &self,
26 dw_unit: gimli::UnitRef<R>,
27 ilnp: &gimli::IncompleteLineProgram<R, R::Offset>,
28 ) -> Result<&Lines, Error> {
29 self.0
30 .get_or_init(|| Lines::parse(dw_unit, ilnp.clone()))
31 .as_ref()
32 .map_err(Error::clone)
33 }
34}
35
36struct LineSequence {
37 start: u64,
38 end: u64,
39 rows: Box<[LineRow]>,
40}
41
42struct LineRow {
43 address: u64,
44 file_index: u64,
45 line: u32,
46 column: u32,
47}
48
49pub(crate) struct Lines {
50 files: Box<[String]>,
51 sequences: Box<[LineSequence]>,
52}
53
54impl Lines {
55 fn parse<R: gimli::Reader>(
56 dw_unit: gimli::UnitRef<R>,
57 ilnp: gimli::IncompleteLineProgram<R, R::Offset>,
58 ) -> Result<Self, Error> {
59 let mut sequences = Vec::new();
60 let mut sequence_rows = Vec::<LineRow>::new();
61 let mut rows = ilnp.rows();
62 while let Some((_, row)) = rows.next_row()? {
63 if row.end_sequence() {
64 if let Some(start) = sequence_rows.first().map(|x| x.address) {
65 let end = row.address();
66 let mut rows = Vec::new();
67 mem::swap(&mut rows, &mut sequence_rows);
68 sequences.push(LineSequence {
69 start,
70 end,
71 rows: rows.into_boxed_slice(),
72 });
73 }
74 continue;
75 }
76
77 let address = row.address();
78 let file_index = row.file_index();
79 // Convert line and column to u32 to save a little memory.
80 // We'll handle the special case of line 0 later,
81 // and return left edge as column 0 in the public API.
82 let line = row.line().map(NonZeroU64::get).unwrap_or(0) as u32;
83 let column = match row.column() {
84 gimli::ColumnType::LeftEdge => 0,
85 gimli::ColumnType::Column(x) => x.get() as u32,
86 };
87
88 if let Some(last_row) = sequence_rows.last_mut()
89 && last_row.address == address
90 {
91 last_row.file_index = file_index;
92 last_row.line = line;
93 last_row.column = column;
94 continue;
95 }
96
97 sequence_rows.push(LineRow {
98 address,
99 file_index,
100 line,
101 column,
102 });
103 }
104 sequences.sort_by_key(|x| x.start);
105
106 let mut files = Vec::new();
107 let header = rows.header();
108 match header.file(0) {
109 Some(file) => files.push(render_file(dw_unit, file, header)?),
110 None => files.push(String::from("")), // DWARF version <= 4 may not have 0th index
111 }
112 let mut index = 1;
113 while let Some(file) = header.file(index) {
114 files.push(render_file(dw_unit, file, header)?);
115 index += 1;
116 }
117
118 Ok(Self {
119 files: files.into_boxed_slice(),
120 sequences: sequences.into_boxed_slice(),
121 })
122 }
123
124 pub(crate) fn file(&self, index: u64) -> Option<&str> {
125 self.files.get(index as usize).map(String::as_str)
126 }
127
128 pub(crate) fn ranges(&self) -> impl Iterator<Item = gimli::Range> + '_ {
129 self.sequences.iter().map(|sequence| gimli::Range {
130 begin: sequence.start,
131 end: sequence.end,
132 })
133 }
134
135 fn row_location(&self, row: &LineRow) -> Location<'_> {
136 let file = self.files.get(row.file_index as usize).map(String::as_str);
137 Location {
138 file,
139 line: if row.line != 0 { Some(row.line) } else { None },
140 // If row.line is specified then row.column always has meaning.
141 column: if row.line != 0 {
142 Some(row.column)
143 } else {
144 None
145 },
146 }
147 }
148
149 pub(crate) fn find_location(&self, probe: u64) -> Result<Option<Location<'_>>, Error> {
150 let seq_idx = self.sequences.binary_search_by(|sequence| {
151 if probe < sequence.start {
152 Ordering::Greater
153 } else if probe >= sequence.end {
154 Ordering::Less
155 } else {
156 Ordering::Equal
157 }
158 });
159 let seq_idx = match seq_idx {
160 Ok(x) => x,
161 Err(_) => return Ok(None),
162 };
163 let sequence = &self.sequences[seq_idx];
164
165 let idx = sequence
166 .rows
167 .binary_search_by(|row| row.address.cmp(&probe));
168 let idx = match idx {
169 Ok(x) => x,
170 Err(0) => return Ok(None),
171 Err(x) => x - 1,
172 };
173 Ok(Some(self.row_location(&sequence.rows[idx])))
174 }
175
176 pub(crate) fn find_location_range(
177 &self,
178 probe_low: u64,
179 probe_high: u64,
180 ) -> Result<LineLocationRangeIter<'_>, Error> {
181 // Find index for probe_low.
182 let seq_idx = self.sequences.binary_search_by(|sequence| {
183 if probe_low < sequence.start {
184 Ordering::Greater
185 } else if probe_low >= sequence.end {
186 Ordering::Less
187 } else {
188 Ordering::Equal
189 }
190 });
191 let seq_idx = match seq_idx {
192 Ok(x) => x,
193 Err(x) => x, // probe below sequence, but range could overlap
194 };
195
196 let row_idx = if let Some(seq) = self.sequences.get(seq_idx) {
197 let idx = seq.rows.binary_search_by(|row| row.address.cmp(&probe_low));
198 match idx {
199 Ok(x) => x,
200 Err(0) => 0, // probe below sequence, but range could overlap
201 Err(x) => x - 1,
202 }
203 } else {
204 0
205 };
206
207 Ok(LineLocationRangeIter {
208 lines: self,
209 seq_idx,
210 row_idx,
211 probe_high,
212 })
213 }
214}
215
216pub(crate) struct LineLocationRangeIter<'ctx> {
217 lines: &'ctx Lines,
218 seq_idx: usize,
219 row_idx: usize,
220 probe_high: u64,
221}
222
223impl<'ctx> Iterator for LineLocationRangeIter<'ctx> {
224 type Item = (u64, u64, Location<'ctx>);
225
226 fn next(&mut self) -> Option<(u64, u64, Location<'ctx>)> {
227 while let Some(seq) = self.lines.sequences.get(self.seq_idx) {
228 if seq.start >= self.probe_high {
229 break;
230 }
231
232 match seq.rows.get(self.row_idx) {
233 Some(row) => {
234 if row.address >= self.probe_high {
235 break;
236 }
237
238 let nextaddr = seq
239 .rows
240 .get(self.row_idx + 1)
241 .map(|row| row.address)
242 .unwrap_or(seq.end);
243
244 let item = (
245 row.address,
246 nextaddr - row.address,
247 self.lines.row_location(row),
248 );
249 self.row_idx += 1;
250
251 return Some(item);
252 }
253 None => {
254 self.seq_idx += 1;
255 self.row_idx = 0;
256 }
257 }
258 }
259 None
260 }
261}
262
263fn render_file<R: gimli::Reader>(
264 dw_unit: gimli::UnitRef<R>,
265 file: &gimli::FileEntry<R, R::Offset>,
266 header: &gimli::LineProgramHeader<R, R::Offset>,
267) -> Result<String, gimli::Error> {
268 let mut path = if let Some(ref comp_dir) = dw_unit.comp_dir {
269 comp_dir.to_string_lossy()?.into_owned()
270 } else {
271 String::new()
272 };
273
274 // The directory index 0 is defined to correspond to the compilation unit directory.
275 if file.directory_index() != 0
276 && let Some(directory) = file.directory(header)
277 {
278 path_push(
279 &mut path,
280 dw_unit.attr_string(directory)?.to_string_lossy()?.as_ref(),
281 );
282 }
283
284 path_push(
285 &mut path,
286 dw_unit
287 .attr_string(file.path_name())?
288 .to_string_lossy()?
289 .as_ref(),
290 );
291
292 Ok(path)
293}
294
295fn path_push(path: &mut String, p: &str) {
296 if has_unix_root(p) || has_windows_root(p) {
297 *path = p.to_string();
298 } else {
299 let dir_separator = if has_windows_root(path.as_str()) {
300 '\\'
301 } else {
302 '/'
303 };
304
305 if !path.is_empty() && !path.ends_with(dir_separator) {
306 path.push(dir_separator);
307 }
308 *path += p;
309 }
310}
311
312/// Check if the path in the given string has a unix style root
313fn has_unix_root(p: &str) -> bool {
314 p.starts_with('/')
315}
316
317/// Check if the path in the given string has a windows style root
318fn has_windows_root(p: &str) -> bool {
319 p.starts_with('\\') || p.get(1..3) == Some(":\\")
320}