Skip to content

Commit dea581f

Browse files
whitequarkwhitequark
committedDec 12, 2016
Implement an ARP LRU cache.
·
v0.12.0v0.1.0
1 parent f57492a commit dea581f

File tree

7 files changed

+217
-6
lines changed

7 files changed

+217
-6
lines changed
 

Diff for: ‎src/iface/arp_cache.rs

+128
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
use wire::EthernetAddress;
2+
use super::ProtocolAddress;
3+
4+
/// An Address Resolution Protocol cache.
5+
///
6+
/// This cache maps protocol addresses to hardware addresses.
7+
pub trait Cache {
8+
/// Update the cache to map given protocol address to given hardware address.
9+
fn fill(&mut self, protocol_addr: ProtocolAddress, hardware_addr: EthernetAddress);
10+
11+
/// Look up the hardware address corresponding for the given protocol address.
12+
fn lookup(&mut self, protocol_addr: ProtocolAddress) -> Option<EthernetAddress>;
13+
}
14+
15+
/// An Address Resolution Protocol cache backed by a slice.
16+
///
17+
/// This cache uses a fixed-size storage, binary search, and a least recently used
18+
/// eviction strategy.
19+
///
20+
/// # Examples
21+
/// This cache can be created as:
22+
///
23+
/// ```rust
24+
/// use smoltcp::iface::SliceArpCache;
25+
/// let mut arp_cache_storage = [Default::default(); 8];
26+
/// let mut arp_cache = SliceArpCache::new(&mut arp_cache_storage);
27+
/// ```
28+
pub struct SliceCache<'a> {
29+
storage: &'a mut [(ProtocolAddress, EthernetAddress, usize)],
30+
counter: usize
31+
}
32+
33+
impl<'a> SliceCache<'a> {
34+
/// Create a cache. The backing storage is cleared upon creation.
35+
///
36+
/// # Panics
37+
/// This function panics if `storage.len() == 0`.
38+
pub fn new(storage: &'a mut [(ProtocolAddress, EthernetAddress, usize)]) -> SliceCache<'a> {
39+
if storage.len() == 0 {
40+
panic!("ARP slice cache created with empty storage")
41+
}
42+
43+
for elem in storage.iter_mut() {
44+
*elem = Default::default()
45+
}
46+
SliceCache {
47+
storage: storage,
48+
counter: 0
49+
}
50+
}
51+
52+
/// Find an entry for the given protocol address, if any.
53+
fn find(&self, protocol_addr: ProtocolAddress) -> Option<usize> {
54+
// The order of comparison is important: any valid ProtocolAddress should
55+
// sort before ProtocolAddress::Invalid.
56+
self.storage.binary_search_by_key(&protocol_addr, |&(key, _, _)| key).ok()
57+
}
58+
59+
/// Sort entries in an order suitable for `find`.
60+
fn sort(&mut self) {
61+
self.storage.sort_by_key(|&(key, _, _)| key)
62+
}
63+
64+
/// Find the least recently used entry.
65+
fn lru(&self) -> usize {
66+
self.storage.iter().enumerate().min_by_key(|&(_, &(_, _, counter))| counter).unwrap().0
67+
}
68+
}
69+
70+
impl<'a> Cache for SliceCache<'a> {
71+
fn fill(&mut self, protocol_addr: ProtocolAddress, hardware_addr: EthernetAddress) {
72+
if let None = self.find(protocol_addr) {
73+
self.storage[self.lru()] = (protocol_addr, hardware_addr, self.counter);
74+
self.sort()
75+
}
76+
}
77+
78+
fn lookup(&mut self, protocol_addr: ProtocolAddress) -> Option<EthernetAddress> {
79+
if let Some(index) = self.find(protocol_addr) {
80+
let (_protocol_addr, hardware_addr, ref mut counter) = self.storage[index];
81+
self.counter += 1;
82+
*counter = self.counter;
83+
Some(hardware_addr)
84+
} else {
85+
None
86+
}
87+
}
88+
}
89+
90+
#[cfg(test)]
91+
mod test {
92+
use super::*;
93+
94+
const HADDR_A: EthernetAddress = EthernetAddress([0, 0, 0, 0, 0, 1]);
95+
const HADDR_B: EthernetAddress = EthernetAddress([0, 0, 0, 0, 0, 2]);
96+
const HADDR_C: EthernetAddress = EthernetAddress([0, 0, 0, 0, 0, 3]);
97+
const HADDR_D: EthernetAddress = EthernetAddress([0, 0, 0, 0, 0, 4]);
98+
99+
const PADDR_A: ProtocolAddress = ProtocolAddress::ipv4([0, 0, 0, 0]);
100+
const PADDR_B: ProtocolAddress = ProtocolAddress::ipv4([0, 0, 0, 1]);
101+
const PADDR_C: ProtocolAddress = ProtocolAddress::ipv4([0, 0, 0, 2]);
102+
const PADDR_D: ProtocolAddress = ProtocolAddress::ipv4([0, 0, 0, 3]);
103+
104+
#[test]
105+
fn test_slice_cache() {
106+
let mut cache_storage = [Default::default(); 3];
107+
let mut cache = SliceCache::new(&mut cache_storage);
108+
109+
cache.fill(PADDR_A, HADDR_A);
110+
assert_eq!(cache.lookup(PADDR_A), Some(HADDR_A));
111+
assert_eq!(cache.lookup(PADDR_B), None);
112+
113+
cache.fill(PADDR_B, HADDR_B);
114+
cache.fill(PADDR_C, HADDR_C);
115+
assert_eq!(cache.lookup(PADDR_A), Some(HADDR_A));
116+
assert_eq!(cache.lookup(PADDR_B), Some(HADDR_B));
117+
assert_eq!(cache.lookup(PADDR_C), Some(HADDR_C));
118+
119+
cache.lookup(PADDR_B);
120+
cache.lookup(PADDR_A);
121+
cache.lookup(PADDR_C);
122+
cache.fill(PADDR_D, HADDR_D);
123+
assert_eq!(cache.lookup(PADDR_A), Some(HADDR_A));
124+
assert_eq!(cache.lookup(PADDR_B), None);
125+
assert_eq!(cache.lookup(PADDR_C), Some(HADDR_C));
126+
assert_eq!(cache.lookup(PADDR_D), Some(HADDR_D));
127+
}
128+
}

Diff for: ‎src/iface/ethernet.rs

+39
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
use phy::Device;
2+
use wire::EthernetAddress;
3+
use super::{ProtocolAddress, ArpCache};
4+
5+
/// An Ethernet network interface.
6+
#[derive(Debug)]
7+
pub struct Interface<DeviceT: Device, ArpCacheT: ArpCache> {
8+
device: DeviceT,
9+
arp_cache: ArpCacheT,
10+
hardware_addr: EthernetAddress,
11+
}
12+
13+
impl<DeviceT: Device, ArpCacheT: ArpCache> Interface<DeviceT, ArpCacheT> {
14+
/// Create a network interface using the provided network device.
15+
///
16+
/// The newly created interface uses hardware address `00-00-00-00-00-00` and
17+
/// has no assigned protocol addresses.
18+
pub fn new(device: DeviceT, arp_cache: ArpCacheT) -> Interface<DeviceT, ArpCacheT> {
19+
Interface {
20+
device: device,
21+
arp_cache: arp_cache,
22+
hardware_addr: EthernetAddress([0x00; 6])
23+
}
24+
}
25+
26+
/// Get the hardware address of the interface.
27+
pub fn hardware_addr(&self) -> EthernetAddress {
28+
self.hardware_addr
29+
}
30+
31+
/// Set the hardware address of the interface.
32+
///
33+
/// # Panics
34+
/// This function panics if `addr` is not unicast.
35+
pub fn set_hardware_addr(&mut self, addr: EthernetAddress) {
36+
if addr.is_multicast() { panic!("hardware address should be unicast") }
37+
self.hardware_addr = addr
38+
}
39+
}

Diff for: ‎src/iface/mod.rs

+31
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
//! Network interface logic.
2+
//!
3+
//! The `iface` module deals with the *network interfaces*. It filters incoming frames,
4+
//! provides lookup and caching of hardware addresses, and handles management packets.
5+
use wire;
6+
7+
mod arp_cache;
8+
mod ethernet;
9+
10+
pub use self::arp_cache::Cache as ArpCache;
11+
pub use self::arp_cache::SliceCache as SliceArpCache;
12+
pub use self::ethernet::Interface as EthernetInterface;
13+
14+
/// An internetworking protocol address.
15+
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
16+
pub enum ProtocolAddress {
17+
Invalid,
18+
Ipv4(wire::Ipv4Address)
19+
}
20+
21+
impl ProtocolAddress {
22+
pub const fn ipv4(bytes: [u8; 4]) -> ProtocolAddress {
23+
ProtocolAddress::Ipv4(wire::Ipv4Address(bytes))
24+
}
25+
}
26+
27+
impl Default for ProtocolAddress {
28+
fn default() -> ProtocolAddress {
29+
ProtocolAddress::Invalid
30+
}
31+
}

Diff for: ‎src/lib.rs

+2-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
#![feature(range_contains, associated_consts)]
1+
#![feature(range_contains, associated_consts, const_fn)]
22
#![no_std]
33

44
extern crate byteorder;
@@ -11,3 +11,4 @@ extern crate libc;
1111

1212
pub mod phy;
1313
pub mod wire;
14+
pub mod iface;

Diff for: ‎src/phy/mod.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
//! Access to networking hardware.
22
//!
3-
//! The `phy` module provides an interface for sending and receiving frames
4-
//! through a physical (or perhaps virtualized) network device, [Device](trait.Device.html),
3+
//! The `phy` module deals with the *network devices*. It provides an interface
4+
//! for transmitting and receiving frames, [Device](trait.Device.html),
55
//! as well as an implementations of that trait that uses the host OS,
6-
//! [OsDevice](struct.OsDevice.html).
6+
//! [RawSocket](struct.RawSocket.html) and [TapInterface](struct.TapInterface.html).
77
88
#[cfg(feature = "std")]
99
mod sys;

Diff for: ‎src/wire/ethernet.rs

+13-1
Original file line numberDiff line numberDiff line change
@@ -22,10 +22,12 @@ impl fmt::Display for EtherType {
2222
}
2323

2424
/// A six-octet Ethernet II address.
25-
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
25+
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Default)]
2626
pub struct Address(pub [u8; 6]);
2727

2828
impl Address {
29+
pub const BROADCAST: Address = Address([0xff; 6]);
30+
2931
/// Construct an Ethernet address from a sequence of octets, in big-endian.
3032
///
3133
/// # Panics
@@ -40,6 +42,16 @@ impl Address {
4042
pub fn as_bytes(&self) -> &[u8] {
4143
&self.0
4244
}
45+
46+
/// Query whether the "multicast" bit in the OUI is set.
47+
pub fn is_multicast(&self) -> bool {
48+
self.0[0] & 0x01 != 0
49+
}
50+
51+
/// Query whether the "locally administered" bit in the OUI is set.
52+
pub fn is_local(&self) -> bool {
53+
self.0[0] & 0x02 != 0
54+
}
4355
}
4456

4557
impl fmt::Display for Address {

Diff for: ‎src/wire/ipv4.rs

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
use core::fmt;
22

33
/// A four-octet IPv4 address.
4-
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
4+
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Default)]
55
pub struct Address(pub [u8; 4]);
66

77
impl Address {

0 commit comments

Comments
 (0)
Please sign in to comment.