wlan_sme/ap/
aid.rs

1// Copyright 2018 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use anyhow::format_err;
6use wlan_common::mac::{Aid, MAX_AID};
7
8#[derive(Debug)]
9pub struct Map {
10    // bitmap representing the "claimed" association IDs; examples:
11    // Claimed AIDs: [0] -- array 1st element is 1, remaining are zeroes
12    // Claimed AIDs: [0, 1] -- array 1st element is 3, remaining are zeroes
13    // Claimed AIDs: [64] -- array 2nd element is 1, remaining are zeroes
14    //
15    // Type u64 was chosen since it's the largest unsigned integer type that provides methods
16    // like `count_zeroes` and `trailing_zeros`. Array has 32 elements since 64 * 32 provides
17    // enough bits to cover the maximum number of clients (2008).
18    aids: [u64; 32],
19}
20
21impl Map {
22    const ELEM_BITS: u16 = 64;
23
24    pub fn assign_aid(&mut self) -> Result<Aid, anyhow::Error> {
25        for (i, bitmap) in self.aids.iter_mut().enumerate() {
26            if bitmap.count_zeros() > 0 {
27                let first_unset_bit_pos = (!*bitmap).trailing_zeros() as u16;
28                let aid = first_unset_bit_pos + Map::ELEM_BITS * (i as u16);
29                if aid <= MAX_AID {
30                    *bitmap |= 1 << first_unset_bit_pos;
31                    return Ok(aid);
32                } else {
33                    return Err(format_err!("no available association ID"));
34                }
35            }
36        }
37        // control flow should never reach here since once we reach the max AID, we should already
38        // return in the above loop with an error (i.e., the last element in `aids` array is never
39        // all 1's)
40        panic!("unexpected error assigning association ID")
41    }
42
43    pub fn release_aid(&mut self, aid: Aid) {
44        let index = (aid / Map::ELEM_BITS) as usize;
45        if index < self.aids.len() {
46            // Safe to index because we checked that index is less than length of array
47            #[expect(clippy::indexing_slicing)]
48            let () = self.aids[index] &= !(1 << (aid % Map::ELEM_BITS));
49        } else {
50            log::warn!("Received unexpectedly large association ID {}, max ID {}", aid, MAX_AID);
51        }
52    }
53}
54
55impl Default for Map {
56    fn default() -> Self {
57        let mut map = Map { aids: [0u64; 32] };
58        map.aids[0] = 1;
59        map
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_map_never_assign_zero() {
69        let mut aid_map: Map = Default::default();
70        for i in 1..=2007u16 {
71            assert_eq!(aid_map.assign_aid().unwrap(), i);
72        }
73        let result = aid_map.assign_aid();
74        assert!(result.is_err());
75        assert_eq!(format!("{}", result.unwrap_err()), "no available association ID");
76    }
77
78    #[allow(
79        clippy::legacy_numeric_constants,
80        reason = "mass allow for https://fxbug.dev/381896734"
81    )]
82    #[test]
83    fn test_map_no_available_assoc_id() {
84        let mut aid_map: Map = Default::default();
85        // Set all the bits in the first 31 elements to 1's (so 64 * 31 = 1984 aids claimed)
86        for i in 0..31 {
87            aid_map.aids[i] = u64::max_value();
88        }
89        // Set the remaining 24 aids in the last array positions
90        for i in 0..24 {
91            aid_map.aids[31] += 1 << i;
92        }
93        let result = aid_map.assign_aid();
94        assert!(result.is_err());
95        assert_eq!(format!("{}", result.unwrap_err()), "no available association ID");
96    }
97
98    #[test]
99    fn test_map_ascending_available() {
100        let mut aid_map: Map = Default::default();
101        for i in 1..=1000u16 {
102            assert_eq!(aid_map.assign_aid().unwrap(), i);
103        }
104        aid_map.release_aid(157);
105        aid_map.release_aid(792);
106        aid_map.release_aid(533);
107        assert_eq!(aid_map.assign_aid().unwrap(), 157);
108        assert_eq!(aid_map.assign_aid().unwrap(), 533);
109        assert_eq!(aid_map.assign_aid().unwrap(), 792);
110
111        for i in 1001..=2007u16 {
112            assert_eq!(aid_map.assign_aid().unwrap(), i);
113        }
114        let result = aid_map.assign_aid();
115        assert!(result.is_err());
116        assert_eq!(format!("{}", result.unwrap_err()), "no available association ID");
117        aid_map.release_aid(666);
118        aid_map.release_aid(222);
119        aid_map.release_aid(111);
120        assert_eq!(aid_map.assign_aid().unwrap(), 111);
121        assert_eq!(aid_map.assign_aid().unwrap(), 222);
122        assert_eq!(aid_map.assign_aid().unwrap(), 666);
123    }
124}
wlan_sme/ap/aid.rs

wlan_sme/ap/
aid.rs
