afs-ld Public

Watch 0 Fork 0 Star 0
Rust · 16951 bytes Raw Blame History
1 //! ARM64 Linker Optimization Hints (LOH).
2 //!
3 //! `LC_LINKER_OPTIMIZATION_HINT` stores a ULEB128 stream of `(kind, argc,
4 //! args...)` records. The args are file offsets of the participating
5 //! instructions.
6
7 use std::collections::HashSet;
8 use std::fmt;
9
10 use crate::layout::Layout;
11 use crate::leb::{read_uleb, write_uleb};
12 use crate::macho::reader::ReadError;
13 use crate::macho::writer::LinkEditPlan;
14
15 pub const LOH_ARM64_ADRP_LDR: u32 = 2;
16 pub const LOH_ARM64_ADRP_LDR_GOT_LDR: u32 = 4;
17 pub const LOH_ARM64_ADRP_ADD: u32 = 7;
18 pub const LOH_ARM64_ADRP_LDR_GOT: u32 = 8;
19 const NOP: u32 = 0xd503_201f;
20
21 #[derive(Debug, Clone, PartialEq, Eq)]
22 pub struct LohEntry {
23 pub kind: u32,
24 pub args: Vec<u32>,
25 }
26
27 #[derive(Debug, Clone, PartialEq, Eq)]
28 pub struct LohError(String);
29
30 impl fmt::Display for LohError {
31 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32 write!(f, "LOH relaxation error: {}", self.0)
33 }
34 }
35
36 impl std::error::Error for LohError {}
37
38 impl From<ReadError> for LohError {
39 fn from(value: ReadError) -> Self {
40 Self(value.to_string())
41 }
42 }
43
44 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
45 struct LocatedWord {
46 section_idx: usize,
47 atom_idx: usize,
48 word_off: usize,
49 addr: u64,
50 insn: u32,
51 }
52
53 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
54 enum LiteralLoadKind {
55 W,
56 X,
57 S,
58 D,
59 Q,
60 }
61
62 pub fn parse_loh_blob(bytes: &[u8]) -> Result<Vec<LohEntry>, ReadError> {
63 let mut out = Vec::new();
64 let mut cursor = 0usize;
65 while cursor < bytes.len() {
66 if bytes[cursor..].iter().all(|&byte| byte == 0) {
67 break;
68 }
69 let at_offset = cursor as u32;
70 let (kind, used) = read_uleb(&bytes[cursor..])?;
71 cursor += used;
72 let (argc, used) = read_uleb(&bytes[cursor..])?;
73 cursor += used;
74 let kind = u32::try_from(kind).map_err(|_| ReadError::BadRelocation {
75 at_offset,
76 reason: "LOH kind overflows u32",
77 })?;
78 let argc = usize::try_from(argc).map_err(|_| ReadError::BadRelocation {
79 at_offset,
80 reason: "LOH argcount overflows usize",
81 })?;
82 let mut args = Vec::with_capacity(argc);
83 for _ in 0..argc {
84 let (arg, used) = read_uleb(&bytes[cursor..])?;
85 cursor += used;
86 args.push(u32::try_from(arg).map_err(|_| ReadError::BadRelocation {
87 at_offset,
88 reason: "LOH arg overflows u32",
89 })?);
90 }
91 out.push(LohEntry { kind, args });
92 }
93 Ok(out)
94 }
95
96 pub fn write_loh_blob(entries: &[LohEntry]) -> Vec<u8> {
97 let mut out = Vec::new();
98 for entry in entries {
99 write_uleb(entry.kind as u64, &mut out);
100 write_uleb(entry.args.len() as u64, &mut out);
101 for &arg in &entry.args {
102 write_uleb(arg as u64, &mut out);
103 }
104 }
105 out
106 }
107
108 pub fn relax_layout(
109 layout: &mut Layout,
110 linkedit: &LinkEditPlan,
111 enabled: bool,
112 ) -> Result<(), LohError> {
113 if !enabled || linkedit.loh.is_none() || linkedit.loh_bytes().is_empty() {
114 return Ok(());
115 }
116
117 let mut entries = parse_loh_blob(linkedit.loh_bytes())?;
118 entries.sort_by(|lhs, rhs| {
119 rhs.args
120 .len()
121 .cmp(&lhs.args.len())
122 .then_with(|| lhs.args.first().cmp(&rhs.args.first()))
123 .then_with(|| lhs.kind.cmp(&rhs.kind))
124 });
125 let mut rewritten = HashSet::new();
126 for entry in entries {
127 match entry.kind {
128 LOH_ARM64_ADRP_LDR => relax_adrp_ldr(layout, &entry, &mut rewritten)?,
129 LOH_ARM64_ADRP_LDR_GOT_LDR => relax_adrp_ldr_got_ldr(layout, &entry, &mut rewritten)?,
130 LOH_ARM64_ADRP_ADD => relax_adrp_add(layout, &entry, &mut rewritten)?,
131 LOH_ARM64_ADRP_LDR_GOT => relax_adrp_ldr_got(layout, &entry, &mut rewritten)?,
132 _ => {}
133 }
134 }
135 Ok(())
136 }
137
138 fn relax_adrp_add(
139 layout: &mut Layout,
140 entry: &LohEntry,
141 rewritten: &mut HashSet<u64>,
142 ) -> Result<(), LohError> {
143 if entry.args.len() != 2 {
144 return Ok(());
145 }
146 let adrp_off = entry.args[0] as u64;
147 let add_off = entry.args[1] as u64;
148 if !claim_offsets(rewritten, &[adrp_off, add_off]) {
149 return Ok(());
150 }
151 let adrp = locate_word(layout, adrp_off)?;
152 let add = locate_word(layout, add_off)?;
153 let Some(target) = decode_adrp_add_target(adrp.insn, add.insn, adrp.addr) else {
154 return Ok(());
155 };
156 let dest = (add.insn & 0x1f) as u8;
157 let Some(adr) = encode_adr(target, adrp.addr, dest) else {
158 return Ok(());
159 };
160 write_word(layout, adrp, adr)?;
161 write_word(layout, add, NOP)?;
162 Ok(())
163 }
164
165 fn relax_adrp_ldr(
166 layout: &mut Layout,
167 entry: &LohEntry,
168 rewritten: &mut HashSet<u64>,
169 ) -> Result<(), LohError> {
170 if entry.args.len() != 2 {
171 return Ok(());
172 }
173 let adrp_off = entry.args[0] as u64;
174 let ldr_off = entry.args[1] as u64;
175 if !claim_offsets(rewritten, &[adrp_off, ldr_off]) {
176 return Ok(());
177 }
178 let adrp = locate_word(layout, adrp_off)?;
179 let ldr = locate_word(layout, ldr_off)?;
180 let Some(target) = decode_adrp_ldr_target(adrp.insn, ldr.insn, adrp.addr) else {
181 return Ok(());
182 };
183 let Some(literal) = encode_ldr_literal(ldr.insn, target, ldr.addr) else {
184 return Ok(());
185 };
186 write_word(layout, adrp, NOP)?;
187 write_word(layout, ldr, literal)?;
188 Ok(())
189 }
190
191 fn relax_adrp_ldr_got(
192 layout: &mut Layout,
193 entry: &LohEntry,
194 rewritten: &mut HashSet<u64>,
195 ) -> Result<(), LohError> {
196 if entry.args.len() != 2 {
197 return Ok(());
198 }
199 let adrp_off = entry.args[0] as u64;
200 let ldr_off = entry.args[1] as u64;
201 if !claim_offsets(rewritten, &[adrp_off, ldr_off]) {
202 return Ok(());
203 }
204 let adrp = locate_word(layout, adrp_off)?;
205 let ldr = locate_word(layout, ldr_off)?;
206 let Some(got_slot_addr) = decode_adrp_ldr_target(adrp.insn, ldr.insn, adrp.addr) else {
207 return Ok(());
208 };
209 if pageoff_load_kind(ldr.insn) != Some(LiteralLoadKind::X) {
210 return Ok(());
211 }
212 let Some(local_target) = read_u64_at_addr(layout, got_slot_addr) else {
213 return Ok(());
214 };
215 if !points_into_output(layout, local_target) {
216 return Ok(());
217 }
218 let dest = (ldr.insn & 0x1f) as u8;
219 let Some(adr) = encode_adr(local_target, adrp.addr, dest) else {
220 return Ok(());
221 };
222 write_word(layout, adrp, adr)?;
223 write_word(layout, ldr, NOP)?;
224 Ok(())
225 }
226
227 fn relax_adrp_ldr_got_ldr(
228 layout: &mut Layout,
229 entry: &LohEntry,
230 rewritten: &mut HashSet<u64>,
231 ) -> Result<(), LohError> {
232 if entry.args.len() != 3 {
233 return Ok(());
234 }
235 let adrp_off = entry.args[0] as u64;
236 let got_ldr_off = entry.args[1] as u64;
237 let final_ldr_off = entry.args[2] as u64;
238 if !claim_offsets(rewritten, &[adrp_off, got_ldr_off, final_ldr_off]) {
239 return Ok(());
240 }
241 let adrp = locate_word(layout, adrp_off)?;
242 let got_ldr = locate_word(layout, got_ldr_off)?;
243 let final_ldr = locate_word(layout, final_ldr_off)?;
244 let Some(got_slot_addr) = decode_adrp_ldr_target(adrp.insn, got_ldr.insn, adrp.addr) else {
245 return Ok(());
246 };
247 if pageoff_load_kind(got_ldr.insn) != Some(LiteralLoadKind::X) {
248 return Ok(());
249 }
250 let got_dest = (got_ldr.insn & 0x1f) as u8;
251 if load_base_reg(final_ldr.insn) != Some(got_dest) {
252 return Ok(());
253 }
254 let Some(local_target) = read_u64_at_addr(layout, got_slot_addr) else {
255 return Ok(());
256 };
257 if !points_into_output(layout, local_target) {
258 return Ok(());
259 }
260 let Some(adr) = encode_adr(local_target, adrp.addr, got_dest) else {
261 return Ok(());
262 };
263 write_word(layout, adrp, adr)?;
264 write_word(layout, got_ldr, NOP)?;
265 Ok(())
266 }
267
268 fn claim_offsets(rewritten: &mut HashSet<u64>, offsets: &[u64]) -> bool {
269 if offsets.iter().any(|offset| rewritten.contains(offset)) {
270 return false;
271 }
272 rewritten.extend(offsets.iter().copied());
273 true
274 }
275
276 fn locate_word(layout: &Layout, file_offset: u64) -> Result<LocatedWord, LohError> {
277 for (section_idx, section) in layout.sections.iter().enumerate() {
278 for (atom_idx, atom) in section.atoms.iter().enumerate() {
279 let start = section.file_off + atom.offset;
280 let end = start + atom.data.len() as u64;
281 if !(start <= file_offset && file_offset + 4 <= end) {
282 continue;
283 }
284 let word_off = (file_offset - start) as usize;
285 let bytes = atom.data.get(word_off..word_off + 4).ok_or_else(|| {
286 LohError(format!(
287 "instruction read OOB at file offset 0x{file_offset:x}"
288 ))
289 })?;
290 return Ok(LocatedWord {
291 section_idx,
292 atom_idx,
293 word_off,
294 addr: section.addr + atom.offset + word_off as u64,
295 insn: u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]),
296 });
297 }
298 }
299 Err(LohError(format!(
300 "LOH instruction offset 0x{file_offset:x} did not resolve to an output atom"
301 )))
302 }
303
304 fn write_word(layout: &mut Layout, word: LocatedWord, insn: u32) -> Result<(), LohError> {
305 let atom = &mut layout.sections[word.section_idx].atoms[word.atom_idx];
306 let bytes = atom
307 .data
308 .get_mut(word.word_off..word.word_off + 4)
309 .ok_or_else(|| {
310 LohError(format!(
311 "instruction write OOB at section {} atom {} word {}",
312 word.section_idx, word.atom_idx, word.word_off
313 ))
314 })?;
315 bytes.copy_from_slice(&insn.to_le_bytes());
316 Ok(())
317 }
318
319 fn decode_adrp_add_target(adrp: u32, add: u32, place: u64) -> Option<u64> {
320 if !is_adrp(adrp) || !is_add_imm_64(add) {
321 return None;
322 }
323 let rd = (adrp & 0x1f) as u8;
324 let add_rd = (add & 0x1f) as u8;
325 let add_rn = ((add >> 5) & 0x1f) as u8;
326 if rd == 31 || add_rd != rd || add_rn != rd {
327 return None;
328 }
329 let adrp_immlo = ((adrp >> 29) & 0x3) as i64;
330 let adrp_immhi = ((adrp >> 5) & 0x7ffff) as i64;
331 let adrp_pages = sign_extend_21((adrp_immhi << 2) | adrp_immlo);
332 let adrp_base = ((place as i64) & !0xfff) + (adrp_pages << 12);
333 let low = ((add >> 10) & 0xfff) as u64;
334 Some((adrp_base as u64) + low)
335 }
336
337 fn decode_adrp_ldr_target(adrp: u32, ldr: u32, place: u64) -> Option<u64> {
338 let _kind = pageoff_load_kind(ldr)?;
339 let base = ((ldr >> 5) & 0x1f) as u8;
340 let adrp_reg = (adrp & 0x1f) as u8;
341 if adrp_reg == 31 || base != adrp_reg {
342 return None;
343 }
344 let adrp_immlo = ((adrp >> 29) & 0x3) as i64;
345 let adrp_immhi = ((adrp >> 5) & 0x7ffff) as i64;
346 let adrp_pages = sign_extend_21((adrp_immhi << 2) | adrp_immlo);
347 let adrp_base = ((place as i64) & !0xfff) + (adrp_pages << 12);
348 let shift = pageoff_shift(ldr);
349 let low = (((ldr >> 10) & 0xfff) as u64) << shift;
350 Some((adrp_base as u64) + low)
351 }
352
353 fn encode_adr(target: u64, place: u64, reg: u8) -> Option<u32> {
354 if reg == 31 {
355 return None;
356 }
357 let delta = (target as i64).wrapping_sub(place as i64);
358 if !fits_signed(delta, 21) {
359 return None;
360 }
361 let encoded = (delta as u32) & 0x1f_ffff;
362 let immlo = encoded & 0x3;
363 let immhi = (encoded >> 2) & 0x7ffff;
364 Some(0x1000_0000 | (immlo << 29) | (immhi << 5) | reg as u32)
365 }
366
367 fn encode_ldr_literal(insn: u32, target: u64, place: u64) -> Option<u32> {
368 let kind = pageoff_load_kind(insn)?;
369 let delta = (target as i64).wrapping_sub(place as i64);
370 if delta & 0b11 != 0 {
371 return None;
372 }
373 let imm = delta >> 2;
374 if !fits_signed(imm, 19) {
375 return None;
376 }
377 let encoded = (imm as u32) & 0x7ffff;
378 let rt = insn & 0x1f;
379 let base = match kind {
380 LiteralLoadKind::W => 0x1800_0000,
381 LiteralLoadKind::X => 0x5800_0000,
382 LiteralLoadKind::S => 0x1c00_0000,
383 LiteralLoadKind::D => 0x5c00_0000,
384 LiteralLoadKind::Q => 0x9c00_0000,
385 };
386 Some(base | (encoded << 5) | rt)
387 }
388
389 fn is_adrp(insn: u32) -> bool {
390 (insn & 0x9f00_0000) == 0x9000_0000
391 }
392
393 fn is_add_imm_64(insn: u32) -> bool {
394 (insn & 0xffc0_0000) == 0x9100_0000
395 }
396
397 fn pageoff_load_kind(insn: u32) -> Option<LiteralLoadKind> {
398 match insn & 0xffc0_0000 {
399 0xb940_0000 => Some(LiteralLoadKind::W),
400 0xf940_0000 => Some(LiteralLoadKind::X),
401 0xbd40_0000 => Some(LiteralLoadKind::S),
402 0xfd40_0000 => Some(LiteralLoadKind::D),
403 0x3dc0_0000 => Some(LiteralLoadKind::Q),
404 _ => None,
405 }
406 }
407
408 fn load_base_reg(insn: u32) -> Option<u8> {
409 match insn & 0xffc0_0000 {
410 0xb940_0000 | 0xf940_0000 | 0xbd40_0000 | 0xfd40_0000 | 0x3dc0_0000 | 0x7940_0000
411 | 0x3940_0000 => Some(((insn >> 5) & 0x1f) as u8),
412 _ => None,
413 }
414 }
415
416 fn pageoff_shift(insn: u32) -> u64 {
417 if is_simd_fp_pageoff(insn) {
418 let size = ((insn >> 30) & 0b11) as u64;
419 let opc = ((insn >> 22) & 0b11) as u64;
420 if size == 0 && (opc & 0b10) != 0 {
421 4
422 } else {
423 size
424 }
425 } else {
426 ((insn >> 30) & 0b11) as u64
427 }
428 }
429
430 fn is_simd_fp_pageoff(insn: u32) -> bool {
431 ((insn >> 24) & 0b111) == 0b101
432 }
433
434 fn points_into_output(layout: &Layout, addr: u64) -> bool {
435 layout
436 .sections
437 .iter()
438 .any(|section| section.addr <= addr && addr < section.addr + section.size)
439 }
440
441 fn read_u64_at_addr(layout: &Layout, addr: u64) -> Option<u64> {
442 let bytes = read_bytes_at_addr(layout, addr, 8)?;
443 Some(u64::from_le_bytes(bytes.try_into().ok()?))
444 }
445
446 fn read_bytes_at_addr(layout: &Layout, addr: u64, len: usize) -> Option<Vec<u8>> {
447 for section in &layout.sections {
448 for atom in &section.atoms {
449 let start = section.addr + atom.offset;
450 let end = start + atom.data.len() as u64;
451 if start <= addr && addr + len as u64 <= end {
452 let word_off = (addr - start) as usize;
453 return Some(atom.data.get(word_off..word_off + len)?.to_vec());
454 }
455 }
456 if !section.synthetic_data.is_empty() {
457 let start = section.addr + section.synthetic_offset;
458 let end = start + section.synthetic_data.len() as u64;
459 if start <= addr && addr + len as u64 <= end {
460 let word_off = (addr - start) as usize;
461 return Some(
462 section
463 .synthetic_data
464 .get(word_off..word_off + len)?
465 .to_vec(),
466 );
467 }
468 }
469 }
470 None
471 }
472
473 fn fits_signed(value: i64, bits: u32) -> bool {
474 let min = -(1i64 << (bits - 1));
475 let max = (1i64 << (bits - 1)) - 1;
476 (min..=max).contains(&value)
477 }
478
479 fn sign_extend_21(value: i64) -> i64 {
480 if value & (1 << 20) != 0 {
481 value | !0x1f_ffff
482 } else {
483 value
484 }
485 }
486
487 #[cfg(test)]
488 mod tests {
489 use super::*;
490
491 #[test]
492 fn loh_blob_round_trips() {
493 let entries = vec![
494 LohEntry {
495 kind: LOH_ARM64_ADRP_ADD,
496 args: vec![0, 4],
497 },
498 LohEntry {
499 kind: LOH_ARM64_ADRP_LDR_GOT_LDR,
500 args: vec![8, 12, 16],
501 },
502 ];
503 let blob = write_loh_blob(&entries);
504 assert_eq!(parse_loh_blob(&blob).unwrap(), entries);
505 }
506
507 #[test]
508 fn loh_blob_ignores_trailing_zero_padding() {
509 let mut blob = write_loh_blob(&[LohEntry {
510 kind: LOH_ARM64_ADRP_ADD,
511 args: vec![0, 4],
512 }]);
513 while !blob.len().is_multiple_of(8) {
514 blob.push(0);
515 }
516 assert_eq!(
517 parse_loh_blob(&blob).unwrap(),
518 vec![LohEntry {
519 kind: LOH_ARM64_ADRP_ADD,
520 args: vec![0, 4],
521 }]
522 );
523 }
524
525 #[test]
526 fn encode_adr_round_trips_small_delta() {
527 let place = 0x1_0000_1000;
528 let target = place + 0x48;
529 let adr = encode_adr(target, place, 9).unwrap();
530 assert_eq!(adr & 0x1f, 9);
531 let immlo = ((adr >> 29) & 0x3) as i64;
532 let immhi = ((adr >> 5) & 0x7ffff) as i64;
533 let delta = sign_extend_21((immhi << 2) | immlo);
534 assert_eq!(place.wrapping_add_signed(delta), target);
535 }
536
537 #[test]
538 fn encode_ldr_literal_round_trips_x_load() {
539 let place = 0x1_0000_2004;
540 let target = place + 0x1fc;
541 let insn = 0xf940_0005u32;
542 let literal = encode_ldr_literal(insn, target, place).unwrap();
543 assert_eq!(literal & 0x1f, 5);
544 let imm = ((literal >> 5) & 0x7ffff) as i64;
545 let delta = if imm & (1 << 18) != 0 {
546 (imm | !0x7ffff) << 2
547 } else {
548 imm << 2
549 };
550 assert_eq!(place.wrapping_add_signed(delta), target);
551 }
552 }
553