resources/
system_allocator.rs

1// Copyright 2018 The ChromiumOS Authors
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Manages allocating system resources such as address space and interrupt numbers.
6
7use std::collections::btree_map;
8use std::collections::BTreeMap;
9
10use base::pagesize;
11
12use crate::address_allocator::AddressAllocator;
13use crate::address_allocator::AddressAllocatorSet;
14use crate::AddressRange;
15use crate::Alloc;
16use crate::Error;
17use crate::PciAddress;
18use crate::Result;
19
20/// MMIO address Type
21///    Low: address allocated from low_address_space
22///    High: address allocated from high_address_space
23#[derive(Copy, Clone, PartialEq, Eq)]
24pub enum MmioType {
25    Low,
26    High,
27}
28
29/// Memory allocation options.
30#[derive(Copy, Clone, Debug)]
31pub struct AllocOptions {
32    prefetchable: bool,
33    max_address: u64,
34    alignment: Option<u64>,
35    top_down: bool,
36}
37
38impl Default for AllocOptions {
39    fn default() -> Self {
40        AllocOptions::new()
41    }
42}
43
44impl AllocOptions {
45    pub fn new() -> Self {
46        AllocOptions {
47            prefetchable: false,
48            max_address: u64::MAX,
49            alignment: None,
50            top_down: false,
51        }
52    }
53
54    /// If `true`, memory may be allocated in a prefetchable/cacheable region.
55    /// If `false`, memory must be allocated within a non-prefetechable region, appropriate for
56    /// device registers.
57    /// Default: `false`
58    pub fn prefetchable(&mut self, prefetchable: bool) -> &mut Self {
59        self.prefetchable = prefetchable;
60        self
61    }
62
63    /// Largest valid address for the end of the allocated region.
64    /// For example, `u32::MAX` may be used to allocate a region that is addressable with a 32-bit
65    /// pointer.
66    /// Default: `u64::MAX`
67    pub fn max_address(&mut self, max_address: u64) -> &mut Self {
68        self.max_address = max_address;
69        self
70    }
71
72    /// Minimum alignment of the allocated address.
73    /// Default: `None` (allocation preference of the address allocator pool will be used)
74    pub fn align(&mut self, alignment: u64) -> &mut Self {
75        self.alignment = Some(alignment);
76        self
77    }
78
79    /// If `true`, prefer allocating from the upper end of the region rather than the low end.
80    /// Default: `false`
81    pub fn top_down(&mut self, top_down: bool) -> &mut Self {
82        self.top_down = top_down;
83        self
84    }
85}
86
87pub struct SystemAllocatorConfig {
88    /// IO ports. Only for x86_64.
89    pub io: Option<AddressRange>,
90    /// Low (<=4GB) MMIO region.
91    ///
92    /// Parts of this region may be reserved or otherwise excluded from the
93    /// created SystemAllocator's MmioType::Low allocator. However, no new
94    /// regions will be added.
95    pub low_mmio: AddressRange,
96    /// High (>4GB) MMIO region.
97    ///
98    /// Parts of this region may be reserved or otherwise excluded from the
99    /// created SystemAllocator's MmioType::High allocator. However, no new
100    /// regions will be added.
101    pub high_mmio: AddressRange,
102    /// Platform MMIO space. Only for ARM.
103    pub platform_mmio: Option<AddressRange>,
104    /// The first IRQ number to give out.
105    pub first_irq: u32,
106}
107
108#[derive(Debug)]
109pub struct SystemAllocator {
110    io_address_space: Option<AddressAllocator>,
111
112    // Indexed by MmioType::Low and MmioType::High.
113    mmio_address_spaces: [AddressAllocator; 2],
114    mmio_platform_address_spaces: Option<AddressAllocator>,
115
116    reserved_region: Option<AddressRange>,
117
118    // Each bus number has a AddressAllocator
119    pci_allocator: BTreeMap<u8, AddressAllocator>,
120    irq_allocator: AddressAllocator,
121    gpe_allocator: AddressAllocator,
122    next_anon_id: usize,
123}
124
125impl SystemAllocator {
126    /// Creates a new `SystemAllocator` for managing addresses and irq numbers.
127    /// Will return an error if `base` + `size` overflows u64 (or allowed
128    /// maximum for the specific type), or if alignment isn't a power of two.
129    ///
130    /// If `reserve_region_size` is not None, then a region is reserved from
131    /// the start of `config.high_mmio` before the mmio allocator is created.
132    ///
133    /// If `mmio_address_ranges` is not empty, then `config.low_mmio` and
134    /// `config.high_mmio` are intersected with the ranges specified.
135    pub fn new(
136        config: SystemAllocatorConfig,
137        reserve_region_size: Option<u64>,
138        mmio_address_ranges: &[AddressRange],
139    ) -> Result<Self> {
140        let page_size = pagesize() as u64;
141
142        let (high_mmio, reserved_region) = match reserve_region_size {
143            Some(reserved_len) => {
144                let high_mmio_len = config.high_mmio.len().ok_or(Error::OutOfBounds)?;
145                if reserved_len > high_mmio_len {
146                    return Err(Error::OutOfSpace);
147                }
148                let reserved_start = config.high_mmio.start;
149                let reserved_region =
150                    AddressRange::from_start_and_size(reserved_start, reserved_len)
151                        .ok_or(Error::OutOfBounds)?;
152                let high_mmio = if reserved_len == high_mmio_len {
153                    AddressRange::empty()
154                } else {
155                    AddressRange {
156                        start: reserved_start + reserved_len,
157                        end: config.high_mmio.end,
158                    }
159                };
160                (high_mmio, Some(reserved_region))
161            }
162            None => (config.high_mmio, None),
163        };
164
165        let intersect_mmio_range = |src_range: AddressRange| -> Result<Vec<AddressRange>> {
166            Ok(if mmio_address_ranges.is_empty() {
167                vec![src_range]
168            } else {
169                mmio_address_ranges
170                    .iter()
171                    .map(|r| r.intersect(src_range))
172                    .collect()
173            })
174        };
175
176        Ok(SystemAllocator {
177            io_address_space: if let Some(io) = config.io {
178                // TODO make sure we don't overlap with existing well known
179                // ports such as 0xcf8 (serial ports).
180                if io.end > 0xffff {
181                    return Err(Error::IOPortOutOfRange(io));
182                }
183                Some(AddressAllocator::new(io, Some(0x400), None)?)
184            } else {
185                None
186            },
187            mmio_address_spaces: [
188                // MmioType::Low
189                AddressAllocator::new_from_list(
190                    intersect_mmio_range(config.low_mmio)?,
191                    Some(page_size),
192                    None,
193                )?,
194                // MmioType::High
195                AddressAllocator::new_from_list(
196                    intersect_mmio_range(high_mmio)?,
197                    Some(page_size),
198                    None,
199                )?,
200            ],
201
202            pci_allocator: BTreeMap::new(),
203
204            mmio_platform_address_spaces: if let Some(platform) = config.platform_mmio {
205                Some(AddressAllocator::new(platform, Some(page_size), None)?)
206            } else {
207                None
208            },
209
210            reserved_region,
211
212            irq_allocator: AddressAllocator::new(
213                AddressRange {
214                    start: config.first_irq as u64,
215                    end: 1023,
216                },
217                Some(1),
218                None,
219            )?,
220
221            // GPE range depends on ACPIPM_RESOURCE_GPE0_BLK_LEN, which is used to determine
222            // ACPIPM_GPE_MAX. The AddressRange should be in sync with ACPIPM_GPE_MAX. The
223            // hard-coded value is used since devices lib (where ACPIPM_* consts are defined)
224            // depends on resource lib. Therefore using ACPI_* const from device lib will not be
225            // possible because it will require introducing cyclic dependencies.
226            gpe_allocator: AddressAllocator::new(
227                AddressRange { start: 0, end: 255 },
228                Some(1),
229                None,
230            )?,
231            next_anon_id: 0,
232        })
233    }
234
235    /// Reserves the next available system irq number.
236    pub fn allocate_irq(&mut self) -> Option<u32> {
237        let id = self.get_anon_alloc();
238        self.irq_allocator
239            .allocate(1, id, "irq-auto".to_string())
240            .map(|v| v as u32)
241            .ok()
242    }
243
244    /// release irq to system irq number pool
245    pub fn release_irq(&mut self, irq: u32) {
246        let _ = self.irq_allocator.release_containing(irq.into());
247    }
248
249    /// Reserves the next available system irq number.
250    pub fn reserve_irq(&mut self, irq: u32) -> bool {
251        let id = self.get_anon_alloc();
252        self.irq_allocator
253            .allocate_at(
254                AddressRange {
255                    start: irq.into(),
256                    end: irq.into(),
257                },
258                id,
259                "irq-fixed".to_string(),
260            )
261            .is_ok()
262    }
263
264    /// Reserve the next available system GPE number
265    pub fn allocate_gpe(&mut self) -> Option<u32> {
266        let id = self.get_anon_alloc();
267        self.gpe_allocator
268            .allocate(1, id, "gpe-auto".to_string())
269            .map(|v| v as u32)
270            .ok()
271    }
272
273    fn get_pci_allocator_mut(&mut self, bus: u8) -> Option<&mut AddressAllocator> {
274        match self.pci_allocator.entry(bus) {
275            btree_map::Entry::Occupied(entry) => Some(entry.into_mut()),
276            btree_map::Entry::Vacant(entry) => {
277                // pci root is 00:00.0, Bus 0 next device is 00:01.0 with mandatory function number
278                // zero.
279                let base = if bus == 0 { 8 } else { 0 };
280
281                // Each bus supports up to 32 (devices) x 8 (functions).
282                // Prefer allocating at device granularity (preferred_align = 8), but fall back to
283                // allocating individual functions (min_align = 1) when we run out of devices.
284                let pci_alloc = AddressAllocator::new(
285                    AddressRange {
286                        start: base,
287                        end: (32 * 8) - 1,
288                    },
289                    Some(1),
290                    Some(8),
291                )
292                .ok()?;
293
294                Some(entry.insert(pci_alloc))
295            }
296        }
297    }
298
299    // Check whether devices exist or not on the specified bus
300    pub fn pci_bus_empty(&self, bus: u8) -> bool {
301        !self.pci_allocator.contains_key(&bus)
302    }
303
304    /// Allocate PCI slot location.
305    pub fn allocate_pci(&mut self, bus: u8, tag: String) -> Option<PciAddress> {
306        let id = self.get_anon_alloc();
307        let allocator = self.get_pci_allocator_mut(bus)?;
308        allocator
309            .allocate(1, id, tag)
310            .map(|v| PciAddress {
311                bus,
312                dev: (v >> 3) as u8,
313                func: (v & 7) as u8,
314            })
315            .ok()
316    }
317
318    /// Reserve PCI slot location.
319    pub fn reserve_pci(&mut self, pci_addr: PciAddress, tag: String) -> bool {
320        let id = self.get_anon_alloc();
321
322        let allocator = match self.get_pci_allocator_mut(pci_addr.bus) {
323            Some(v) => v,
324            None => return false,
325        };
326        let df = ((pci_addr.dev as u64) << 3) | (pci_addr.func as u64);
327        allocator
328            .allocate_at(AddressRange { start: df, end: df }, id, tag)
329            .is_ok()
330    }
331
332    /// release PCI slot location.
333    pub fn release_pci(&mut self, pci_addr: PciAddress) -> bool {
334        let allocator = match self.get_pci_allocator_mut(pci_addr.bus) {
335            Some(v) => v,
336            None => return false,
337        };
338        let df = ((pci_addr.dev as u64) << 3) | (pci_addr.func as u64);
339        allocator.release_containing(df).is_ok()
340    }
341
342    /// Allocate a memory-mapped I/O region with properties requested in `opts`.
343    pub fn allocate_mmio(
344        &mut self,
345        size: u64,
346        alloc: Alloc,
347        tag: String,
348        opts: &AllocOptions,
349    ) -> Result<u64> {
350        // For now, there is no way to ensure allocations fit in less than 32 bits.
351        // This can be removed once AddressAllocator accepts AllocOptions.
352        if opts.max_address < u32::MAX as u64 {
353            return Err(Error::OutOfSpace);
354        }
355
356        let mut mmio_type = MmioType::High;
357        if opts.max_address < u64::MAX || !opts.prefetchable {
358            mmio_type = MmioType::Low;
359        }
360
361        let res = self.allocate_mmio_internal(size, alloc, tag.clone(), opts, mmio_type);
362        // If a high allocation failed, retry in low. The reverse is not valid, since the address
363        // may be out of range and/or prefetchable memory may not be appropriate.
364        if mmio_type == MmioType::High && matches!(res, Err(Error::OutOfSpace)) {
365            self.allocate_mmio_internal(size, alloc, tag, opts, MmioType::Low)
366        } else {
367            res
368        }
369    }
370
371    fn allocate_mmio_internal(
372        &mut self,
373        size: u64,
374        alloc: Alloc,
375        tag: String,
376        opts: &AllocOptions,
377        mmio_type: MmioType,
378    ) -> Result<u64> {
379        let allocator = &mut self.mmio_address_spaces[mmio_type as usize];
380        match (opts.alignment, opts.top_down) {
381            (Some(align), true) => allocator.reverse_allocate_with_align(size, alloc, tag, align),
382            (Some(align), false) => allocator.allocate_with_align(size, alloc, tag, align),
383            (None, true) => allocator.reverse_allocate(size, alloc, tag),
384            (None, false) => allocator.allocate(size, alloc, tag),
385        }
386    }
387
388    /// Reserve specified range from pci mmio, get the overlap of specified
389    /// range with mmio pools, exclude the overlap from mmio allocator.
390    ///
391    /// If any part of the specified range has been allocated, return Error.
392    pub fn reserve_mmio(&mut self, range: AddressRange) -> Result<()> {
393        let mut pools = Vec::new();
394        for pool in self.mmio_pools() {
395            pools.push(*pool);
396        }
397        pools.sort_by(|a, b| a.start.cmp(&b.start));
398        for pool in &pools {
399            if pool.start > range.end {
400                break;
401            }
402
403            let overlap = pool.intersect(range);
404            if !overlap.is_empty() {
405                let id = self.get_anon_alloc();
406                self.mmio_allocator_any().allocate_at(
407                    overlap,
408                    id,
409                    "pci mmio reserve".to_string(),
410                )?;
411            }
412        }
413
414        Ok(())
415    }
416
417    /// Gets an allocator to be used for platform device MMIO allocation.
418    pub fn mmio_platform_allocator(&mut self) -> Option<&mut AddressAllocator> {
419        self.mmio_platform_address_spaces.as_mut()
420    }
421
422    /// Gets an allocator to be used for IO memory.
423    pub fn io_allocator(&mut self) -> Option<&mut AddressAllocator> {
424        self.io_address_space.as_mut()
425    }
426
427    /// Gets an allocator to be used for MMIO allocation.
428    ///    MmioType::Low: low mmio allocator
429    ///    MmioType::High: high mmio allocator
430    pub fn mmio_allocator(&mut self, mmio_type: MmioType) -> &mut AddressAllocator {
431        &mut self.mmio_address_spaces[mmio_type as usize]
432    }
433
434    /// Gets a set of allocators to be used for MMIO allocation.
435    /// The set of allocators will try the low and high MMIO allocators, in that order.
436    pub fn mmio_allocator_any(&mut self) -> AddressAllocatorSet {
437        AddressAllocatorSet::new(&mut self.mmio_address_spaces)
438    }
439
440    /// Gets the pools of all mmio allocators.
441    pub fn mmio_pools(&self) -> Vec<&AddressRange> {
442        self.mmio_address_spaces
443            .iter()
444            .flat_map(|mmio_as| mmio_as.pools())
445            .collect()
446    }
447
448    /// Gets the reserved address space region.
449    pub fn reserved_region(&self) -> Option<AddressRange> {
450        self.reserved_region
451    }
452
453    /// Gets a unique anonymous allocation
454    pub fn get_anon_alloc(&mut self) -> Alloc {
455        self.next_anon_id += 1;
456        Alloc::Anon(self.next_anon_id)
457    }
458}
459
460#[cfg(test)]
461mod tests {
462    use super::*;
463
464    #[test]
465    fn example() {
466        let mut a = SystemAllocator::new(
467            SystemAllocatorConfig {
468                io: Some(AddressRange {
469                    start: 0x1000,
470                    end: 0xffff,
471                }),
472                low_mmio: AddressRange {
473                    start: 0x3000_0000,
474                    end: 0x3000_ffff,
475                },
476                high_mmio: AddressRange {
477                    start: 0x1000_0000,
478                    end: 0x1fffffff,
479                },
480                platform_mmio: None,
481                first_irq: 5,
482            },
483            None,
484            &[],
485        )
486        .unwrap();
487
488        assert_eq!(a.allocate_irq(), Some(5));
489        assert_eq!(a.allocate_irq(), Some(6));
490        assert_eq!(a.allocate_gpe(), Some(0));
491        assert_eq!(a.allocate_gpe(), Some(1));
492        assert_eq!(
493            a.mmio_allocator(MmioType::High).allocate(
494                0x100,
495                Alloc::PciBar {
496                    bus: 0,
497                    dev: 0,
498                    func: 0,
499                    bar: 0
500                },
501                "bar0".to_string()
502            ),
503            Ok(0x10000000)
504        );
505        assert_eq!(
506            a.mmio_allocator(MmioType::High).get(&Alloc::PciBar {
507                bus: 0,
508                dev: 0,
509                func: 0,
510                bar: 0
511            }),
512            Some(&(
513                AddressRange {
514                    start: 0x10000000,
515                    end: 0x100000ff
516                },
517                "bar0".to_string()
518            ))
519        );
520
521        let id = a.get_anon_alloc();
522        assert_eq!(
523            a.mmio_allocator(MmioType::Low).allocate_at(
524                AddressRange {
525                    start: 0x3000_5000,
526                    end: 0x30009fff
527                },
528                id,
529                "Test".to_string()
530            ),
531            Ok(())
532        );
533        assert_eq!(
534            a.mmio_allocator(MmioType::Low).release(id),
535            Ok(AddressRange {
536                start: 0x3000_5000,
537                end: 0x30009fff
538            })
539        );
540        assert_eq!(
541            a.reserve_mmio(AddressRange {
542                start: 0x3000_2000,
543                end: 0x30005fff
544            }),
545            Ok(())
546        );
547        assert_eq!(
548            a.mmio_allocator(MmioType::Low)
549                .allocate_at(
550                    AddressRange {
551                        start: 0x3000_5000,
552                        end: 0x3000_9fff
553                    },
554                    id,
555                    "Test".to_string()
556                )
557                .is_err(),
558            true
559        );
560    }
561
562    #[test]
563    fn reserve_region_boundaries() {
564        let mut a = SystemAllocator::new(
565            SystemAllocatorConfig {
566                io: None,
567                low_mmio: AddressRange {
568                    start: 0x1000,
569                    end: 0x1fff,
570                },
571                high_mmio: AddressRange {
572                    start: 0,
573                    end: 0xffff_ffff,
574                },
575                platform_mmio: None,
576                first_irq: 5,
577            },
578            Some(0),
579            &[],
580        )
581        .unwrap();
582        assert_eq!(a.reserved_region(), Some(AddressRange::empty()));
583        assert_eq!(
584            a.mmio_allocator(MmioType::High)
585                .allocate(1, Alloc::Anon(0), "high".to_string()),
586            Ok(0)
587        );
588
589        let mut a = SystemAllocator::new(
590            SystemAllocatorConfig {
591                io: None,
592                low_mmio: AddressRange {
593                    start: 0x1000,
594                    end: 0x1fff,
595                },
596                high_mmio: AddressRange {
597                    start: u64::MAX - 0xfff,
598                    end: u64::MAX,
599                },
600                platform_mmio: None,
601                first_irq: 5,
602            },
603            Some(0x1000),
604            &[],
605        )
606        .unwrap();
607        assert_eq!(
608            a.reserved_region(),
609            Some(AddressRange {
610                start: u64::MAX - 0xfff,
611                end: u64::MAX,
612            })
613        );
614        assert_eq!(
615            a.mmio_allocator(MmioType::High)
616                .allocate(1, Alloc::Anon(0), "high".to_string()),
617            Err(Error::OutOfSpace)
618        );
619    }
620}
resources/system_allocator.rs

resources/
system_allocator.rs
