dynlink/context/
relocate.rs

1use std::{
2    collections::{HashMap, HashSet},
3    mem::size_of,
4    time::Instant,
5};
6
7use elf::{
8    abi::{
9        DF_TEXTREL, DT_FLAGS, DT_FLAGS_1, DT_JMPREL, DT_PLTGOT, DT_PLTREL, DT_PLTRELSZ, DT_REL,
10        DT_RELA, DT_RELAENT, DT_RELASZ, DT_RELENT, DT_RELSZ,
11    },
12    endian::NativeEndian,
13    parse::{ParseAt, ParsingIterator},
14    relocation::{Rel, Rela},
15    string_table::StringTable,
16    symbol::SymbolTable,
17};
18use petgraph::graph::NodeIndex;
19use tracing::{debug, error, trace};
20
21use super::{Context, Library};
22use crate::{
23    compartment::CompartmentId,
24    library::{LibraryId, RelocState},
25    symbol::RelocatedSymbol,
26    DynlinkError, DynlinkErrorKind, Vec, SMALL_VEC_SIZE,
27};
28
29#[derive(Default)]
30pub(crate) struct RelocCache<'a> {
31    syms: HashMap<CompartmentId, HashMap<String, RelocatedSymbol<'a>>>,
32}
33
34impl<'a> RelocCache<'a> {
35    pub fn find(&mut self, name: &str, from: CompartmentId) -> Option<&RelocatedSymbol<'a>> {
36        let entry = self.syms.entry(from).or_default();
37        entry.get(name)
38    }
39
40    pub fn insert(&mut self, name: &str, from: CompartmentId, sym: RelocatedSymbol<'a>) {
41        let entry = self.syms.entry(from).or_default();
42        entry.insert(name.to_string(), sym);
43    }
44}
45
46// A relocation is either a REL type or a RELA type. The only difference is that
47// the RELA type contains an addend (used in the reloc calculations below).
48#[derive(Debug)]
49pub(crate) enum EitherRel {
50    Rel(Rel),
51    Rela(Rela),
52}
53
54impl EitherRel {
55    pub fn r_type(&self) -> u32 {
56        match self {
57            EitherRel::Rel(r) => r.r_type,
58            EitherRel::Rela(r) => r.r_type,
59        }
60    }
61
62    pub fn addend(&self, target: *mut u64) -> i64 {
63        match self {
64            EitherRel::Rel(_) => unsafe { target.read() as i64 },
65            EitherRel::Rela(r) => r.r_addend,
66        }
67    }
68
69    pub fn offset(&self) -> u64 {
70        match self {
71            EitherRel::Rel(r) => r.r_offset,
72            EitherRel::Rela(r) => r.r_offset,
73        }
74    }
75
76    pub fn sym(&self) -> u32 {
77        match self {
78            EitherRel::Rel(r) => r.r_sym,
79            EitherRel::Rela(r) => r.r_sym,
80        }
81    }
82}
83
84impl Context {
85    pub(crate) fn get_parsing_iter<P: ParseAt>(
86        &self,
87        start: *const u8,
88        ent: usize,
89        sz: usize,
90    ) -> Option<ParsingIterator<'_, NativeEndian, P>> {
91        P::validate_entsize(elf::file::Class::ELF64, ent).ok()?;
92        let iter = ParsingIterator::new(NativeEndian, elf::file::Class::ELF64, unsafe {
93            core::slice::from_raw_parts(start, sz)
94        });
95        Some(iter)
96    }
97
98    #[allow(clippy::too_many_arguments)]
99    fn process_rels(
100        &self,
101        lib: &Library,
102        start: *const u8,
103        ent: usize,
104        sz: usize,
105        name: &str,
106        strings: &StringTable,
107        syms: &SymbolTable<NativeEndian>,
108        deps_list: &[NodeIndex],
109        reloc_cache: &mut RelocCache<'_>,
110    ) -> Result<(), DynlinkError> {
111        debug!(
112            "{}: processing {} relocations (num = {})",
113            lib,
114            name,
115            sz / ent
116        );
117        // Try to parse the table as REL or RELA, according to ent size. If get_parsing_iter
118        // succeeds for a given relocation type, that's the correct one.
119        if let Some(rels) = self.get_parsing_iter(start, ent, sz) {
120            DynlinkError::collect(
121                DynlinkErrorKind::RelocationSectionFail {
122                    secname: "REL".into(),
123                    library: lib.name.as_str().into(),
124                },
125                rels.map(|rel| {
126                    self.do_reloc(
127                        lib,
128                        EitherRel::Rel(rel),
129                        strings,
130                        syms,
131                        deps_list,
132                        reloc_cache,
133                    )
134                }),
135            )?;
136            Ok(())
137        } else if let Some(relas) = self.get_parsing_iter(start, ent, sz) {
138            DynlinkError::collect(
139                DynlinkErrorKind::RelocationSectionFail {
140                    secname: "RELA".into(),
141                    library: lib.name.as_str().into(),
142                },
143                relas.map(|rela| {
144                    self.do_reloc(
145                        lib,
146                        EitherRel::Rela(rela),
147                        strings,
148                        syms,
149                        deps_list,
150                        reloc_cache,
151                    )
152                }),
153            )?;
154            Ok(())
155        } else {
156            let info = format!("reloc '{}' with entsz {}, size {}", name, ent, sz);
157            Err(DynlinkErrorKind::UnsupportedReloc {
158                library: lib.name.as_str().into(),
159                reloc: info.into(),
160            }
161            .into())
162        }
163    }
164
165    #[allow(clippy::too_many_arguments)]
166    fn process_relr(
167        &self,
168        lib: &Library,
169        start: *const u8,
170        ent: usize,
171        sz: usize,
172    ) -> Result<(), DynlinkError> {
173        tracing::debug!(
174            "{}: processing RELR relocations (num = {}) at {:p}",
175            lib,
176            sz / ent,
177            start
178        );
179        // These are different, they indicate simple base additions based
180        // on a compressed format.
181
182        let relr_slice: &[usize] =
183            unsafe { std::slice::from_raw_parts(start as *const usize, sz / ent) };
184
185        let base = lib.base_addr();
186        let mut target = 0;
187
188        let reloc_at = |target: usize, base: usize| {
189            tracing::trace!("processing relr at {:x} += {:x}", target, base);
190            let ptr = unsafe { (target as *mut usize).as_mut().unwrap() };
191            (*ptr) += base;
192            tracing::trace!("new value is {:x}", *ptr);
193        };
194
195        let mut j = 0;
196        for entry in relr_slice {
197            tracing::trace!("RELR: found [{}] {:x}", j, *entry);
198            if *entry & 1 != 0 {
199                if target == 0 {
200                    return Err(DynlinkError {
201                        kind: DynlinkErrorKind::Unknown,
202                        related: Default::default(),
203                    });
204                }
205                // LSB set -- its a bitmap
206                for i in 0..(size_of::<usize>() * 8 - 1) {
207                    if (entry >> (i + 1)) & 1 != 0 {
208                        reloc_at(target + size_of::<usize>() * i, base);
209                    }
210                }
211                target += size_of::<usize>() * (8 * size_of::<usize>() - 1);
212            } else {
213                // sets the address
214                reloc_at(base + *entry, base);
215                target = base + entry + size_of::<usize>();
216            }
217            j += 1;
218        }
219        Ok(())
220    }
221
222    pub(crate) fn relocate_single(
223        &mut self,
224        lib_id: LibraryId,
225        reloc_cache: &mut RelocCache<'_>,
226    ) -> Result<(), DynlinkError> {
227        let _start_1 = Instant::now();
228        let lib = self.get_library(lib_id)?;
229        debug!("{}: relocating library", lib);
230        let common = lib.get_elf_common()?;
231        let dynamic = common
232            .dynamic
233            .as_ref()
234            .ok_or_else(|| DynlinkErrorKind::MissingSection {
235                name: "dynamic".into(),
236            })?;
237
238        // Helper to lookup a single entry for a relocated pointer in the dynamic table.
239        let find_dyn_entry = |tag| {
240            dynamic
241                .iter()
242                .find(|d| d.d_tag == tag)
243                .map(|d| lib.laddr(d.d_ptr()))
244        };
245
246        // Helper to lookup a single value in the dynamic table.
247        let find_dyn_value = |tag| dynamic.iter().find(|d| d.d_tag == tag).map(|d| d.d_val());
248
249        // Many of the relocation tables are described in a similar way -- start, entry size, and
250        // table size (in bytes).
251        let find_dyn_rels = |tag, ent, sz| {
252            let rel = find_dyn_entry(tag);
253            let relent = find_dyn_value(ent);
254            let relsz = find_dyn_value(sz);
255            if let (Some(rel), Some(relent), Some(relsz)) = (rel, relent, relsz) {
256                Some((rel, relent, relsz))
257            } else {
258                None
259            }
260        };
261
262        let flags = find_dyn_value(DT_FLAGS);
263        let flags_1 = find_dyn_value(DT_FLAGS_1);
264        if let Some(flags) = flags {
265            if flags as i64 & DF_TEXTREL != 0 {
266                error!("{}: relocations within text not supported", lib);
267                return Err(DynlinkErrorKind::UnsupportedReloc {
268                    library: lib.name.as_str().into(),
269                    // TODO
270                    reloc: "DF_TEXTREL".into(),
271                }
272                .into());
273            }
274        }
275        debug!("{}: relocation flags: {:?} {:?}", lib, flags, flags_1);
276
277        // these aren't in elf v0.8.0
278        const DT_RELR: i64 = 0x24;
279        const DT_RELRENT: i64 = 0x25;
280        const DT_RELRSZ: i64 = 0x23;
281        // Lookup all the tables
282        let rels = find_dyn_rels(DT_REL, DT_RELENT, DT_RELSZ);
283        let relas = find_dyn_rels(DT_RELA, DT_RELAENT, DT_RELASZ);
284        let relr = find_dyn_rels(DT_RELR, DT_RELRENT, DT_RELRSZ);
285        let jmprels = find_dyn_rels(DT_JMPREL, DT_PLTREL, DT_PLTRELSZ);
286        let _pltgot: Option<*const u8> = find_dyn_entry(DT_PLTGOT);
287
288        let dynsyms = common
289            .dynsyms
290            .as_ref()
291            .ok_or_else(|| DynlinkErrorKind::MissingSection {
292                name: "dynsyms".into(),
293            })?;
294        let dynsyms_str =
295            common
296                .dynsyms_strs
297                .as_ref()
298                .ok_or_else(|| DynlinkErrorKind::MissingSection {
299                    name: "dynsyms_strs".into(),
300                })?;
301
302        let deps_list = self.build_deps_search_list(lib.id());
303        let _start_2 = Instant::now();
304
305        // Process relocations
306
307        if let Some((rel, ent, sz)) = relr {
308            self.process_relr(lib, rel, ent as usize, sz as usize)?;
309        }
310
311        if let Some((rela, ent, sz)) = relas {
312            self.process_rels(
313                lib,
314                rela,
315                ent as usize,
316                sz as usize,
317                "RELA",
318                &dynsyms_str,
319                &dynsyms,
320                deps_list.as_slice(),
321                reloc_cache,
322            )?;
323        }
324
325        if let Some((rel, ent, sz)) = rels {
326            self.process_rels(
327                lib,
328                rel,
329                ent as usize,
330                sz as usize,
331                "REL",
332                &dynsyms_str,
333                &dynsyms,
334                deps_list.as_slice(),
335                reloc_cache,
336            )?;
337        }
338
339        // This one is a little special in that instead of an entry size, we are given a relocation
340        // type.
341        if let Some((rel, kind, sz)) = jmprels {
342            let ent = match kind as i64 {
343                DT_REL => 2,  // 2 usize long, according to ELF
344                DT_RELA => 3, // one extra usize for the addend
345                _ => {
346                    error!("failed to relocate {}: unknown PLTREL type", lib);
347                    return Err(DynlinkErrorKind::UnsupportedReloc {
348                        library: lib.name.as_str().into(),
349                        reloc: "unknown PTREL type".into(),
350                    }
351                    .into());
352                }
353            } * size_of::<usize>();
354            self.process_rels(
355                lib,
356                rel,
357                ent,
358                sz as usize,
359                "JMPREL",
360                &dynsyms_str,
361                &dynsyms,
362                deps_list.as_slice(),
363                reloc_cache,
364            )?;
365        }
366        tracing::trace!(
367            "reloc {}: {}ms prep, {}ms reloc",
368            lib.name,
369            (_start_2 - _start_1).as_millis(),
370            _start_2.elapsed().as_millis()
371        );
372
373        Ok(())
374    }
375
376    fn relocate_recursive(
377        &mut self,
378        root_id: LibraryId,
379        reloc_cache: &mut RelocCache<'_>,
380    ) -> Result<(), DynlinkError> {
381        let lib = self.get_library(root_id)?;
382        let libname = lib.name.to_string();
383        match lib.reloc_state {
384            crate::library::RelocState::Unrelocated => {}
385            crate::library::RelocState::PartialRelocation => {
386                error!("{}: tried to relocate a failed library", lib);
387                return Err(DynlinkErrorKind::RelocationFail {
388                    library: lib.name.as_str().into(),
389                }
390                .into());
391            }
392            crate::library::RelocState::Relocated => {
393                trace!("{}: already relocated", lib);
394                return Ok(());
395            }
396        }
397
398        // We do this recursively instead of using a traversal, since we want to be able to prune
399        // nodes that we know we no longer need to relocate. But since the reloc state gets
400        // set at the end (so we can do this pruning), we'll need to track the visit states.
401        // In the end, this is depth-first postorder.
402        let deps = self
403            .library_deps
404            .neighbors_directed(root_id.0, petgraph::Direction::Outgoing)
405            .collect::<Vec<_, SMALL_VEC_SIZE>>();
406
407        let mut visit_state = HashSet::new();
408        visit_state.insert(root_id.0);
409        let rets = deps.into_iter().map(|dep_id| {
410            if !visit_state.contains(&dep_id) {
411                visit_state.insert(dep_id);
412                self.relocate_recursive(LibraryId(dep_id), reloc_cache)
413            } else {
414                Ok(())
415            }
416        });
417
418        DynlinkError::collect(
419            DynlinkErrorKind::DepsRelocFail {
420                library: libname.into(),
421            },
422            rets,
423        )?;
424
425        // Okay, deps are ready, let's reloc the root.
426        let lib = self.get_library_mut(root_id)?;
427        lib.reloc_state = RelocState::PartialRelocation;
428
429        let res = self.relocate_single(root_id, reloc_cache);
430
431        let lib = self.get_library_mut(root_id)?;
432        if res.is_ok() {
433            lib.reloc_state = RelocState::Relocated;
434        } else {
435            lib.reloc_state = RelocState::PartialRelocation;
436        }
437        res
438    }
439
440    /// Iterate through all libraries and process relocations for any libraries that haven't yet
441    /// been relocated.
442    pub fn relocate_all(&mut self, root_id: LibraryId) -> Result<(), DynlinkError> {
443        let name = self.get_library(root_id)?.name.as_str().into();
444        let mut reloc_cache = RelocCache::default();
445        self.relocate_recursive(root_id, &mut reloc_cache)
446            .map_err(|e| {
447                DynlinkError::new_collect(
448                    DynlinkErrorKind::RelocationFail { library: name },
449                    vec![e],
450                )
451            })
452    }
453}
dynlink/context/relocate.rs

dynlink/context/
relocate.rs
