wasmer_wasix/fs/
fd_list.rs

1//! A very simple data structure for holding the FDs a WASI process is using.
2//! Keeps track of the first unused (i.e. freed) FD, which is slightly faster
3//! than doing a linear search of the entire array each time.
4//! Note, The Unix spec requires newly allocated FDs to always be the
5//! lowest-numbered FD available.
6
7use super::fd::{Fd, FdInner};
8use wasmer_wasix_types::wasi::Fd as WasiFd;
9
10#[derive(Debug)]
11pub struct FdList {
12    fds: Vec<Option<Fd>>,
13    first_free: Option<usize>,
14}
15
16pub struct FdListIterator<'a> {
17    fds_iterator: core::slice::Iter<'a, Option<Fd>>,
18    idx: usize,
19}
20
21pub struct FdListIteratorMut<'a> {
22    fds_iterator: core::slice::IterMut<'a, Option<Fd>>,
23    idx: usize,
24}
25
26impl Default for FdList {
27    fn default() -> Self {
28        Self::new()
29    }
30}
31
32// TODO: rename all functions to something more sensible after all code is migrated
33impl FdList {
34    pub fn new() -> Self {
35        Self {
36            fds: vec![],
37            first_free: None,
38        }
39    }
40
41    pub fn next_free_fd(&self) -> WasiFd {
42        match self.first_free {
43            Some(i) => i as WasiFd,
44            None => self.last_fd().map(|i| i + 1).unwrap_or(0),
45        }
46    }
47
48    pub fn last_fd(&self) -> Option<WasiFd> {
49        self.fds
50            .iter()
51            .rev()
52            .position(|fd| fd.is_some())
53            .map(|idx| (self.fds.len() - idx - 1) as WasiFd)
54    }
55
56    pub fn get(&self, idx: WasiFd) -> Option<&Fd> {
57        self.fds.get(idx as usize).and_then(|x| x.as_ref())
58    }
59
60    pub fn get_mut(&mut self, idx: WasiFd) -> Option<&mut FdInner> {
61        self.fds
62            .get_mut(idx as usize)
63            .and_then(|x| x.as_mut())
64            .map(|x| &mut x.inner)
65    }
66
67    pub fn insert_first_free(&mut self, fd: Fd) -> WasiFd {
68        fd.inode.acquire_handle();
69        match self.first_free {
70            Some(free) => {
71                assert!(self.fds[free].is_none());
72
73                self.fds[free] = Some(fd);
74
75                self.first_free = self.first_free_after(free as WasiFd + 1);
76
77                free as WasiFd
78            }
79            None => {
80                self.fds.push(Some(fd));
81                (self.fds.len() - 1) as WasiFd
82            }
83        }
84    }
85
86    pub fn insert_first_free_after(&mut self, fd: Fd, after_or_equal: WasiFd) -> WasiFd {
87        match self.first_free {
88            // We're shorter than `after`, need to extend the list regardless of whether we have holes
89            _ if self.fds.len() < after_or_equal as usize => {
90                if !self.insert(true, after_or_equal, fd) {
91                    panic!(
92                        "Internal error in FdList - expected {after_or_equal} to be unoccupied since the list wasn't long enough"
93                    );
94                }
95                after_or_equal
96            }
97
98            // First free hole is suitable, we can insert there
99            Some(free) if free >= after_or_equal as usize => self.insert_first_free(fd),
100
101            // No holes, and we're longer than `after`, so insert at the end
102            None if self.fds.len() >= after_or_equal as usize => self.insert_first_free(fd),
103
104            // Keeping the compiler happy
105            None => unreachable!("Both None cases were handled before"),
106
107            // If there's a hole but its index is too low, we need to search
108            Some(_) => {
109                // This is handled by insert or insert_first_free in every other case, but not this one
110                fd.inode.acquire_handle();
111
112                match self.first_free_after(after_or_equal) {
113                    // Found a suitable hole, and it's guaranteed to not be the first since
114                    // that's checked in the previous Some case, so filling it has no effect
115                    // on self.first_free
116                    Some(free) => {
117                        self.fds[free] = Some(fd);
118                        free as WasiFd
119                    }
120
121                    // No holes - insert at the end
122                    None => {
123                        self.fds.push(Some(fd));
124                        (self.fds.len() - 1) as WasiFd
125                    }
126                }
127            }
128        }
129    }
130
131    fn first_free_after(&self, after_or_equal: WasiFd) -> Option<usize> {
132        let skip = after_or_equal as usize;
133        self.fds
134            .iter()
135            .skip(skip)
136            .position(|fd| fd.is_none())
137            .map(|idx| idx + skip)
138    }
139
140    pub fn insert(&mut self, exclusive: bool, idx: WasiFd, fd: Fd) -> bool {
141        let idx = idx as usize;
142
143        if self.fds.len() <= idx {
144            if
145            // if we have a first_free, it has to be before the end of the list, so
146            // the only way for this to update first_free is if we don't have one at all
147            self.first_free.is_none() &&
148                // The target index must be at least len() + 1. If it's exactly len(),
149                // it won't create a hole
150                idx > self.fds.len()
151            {
152                self.first_free = Some(self.fds.len());
153            }
154
155            self.fds.resize(idx + 1, None);
156        }
157
158        if let Some(ref prev_fd) = self.fds[idx] {
159            if exclusive {
160                return false;
161            } else {
162                prev_fd.inode.drop_one_handle();
163            }
164        }
165
166        fd.inode.acquire_handle();
167        self.fds[idx] = Some(fd);
168
169        if self.first_free == Some(idx) {
170            self.first_free = self.first_free_after(idx as WasiFd + 1);
171        }
172
173        true
174    }
175
176    pub fn remove(&mut self, idx: WasiFd) -> Option<Fd> {
177        let idx = idx as usize;
178
179        let result = self.fds.get_mut(idx).and_then(|fd| fd.take());
180
181        if let Some(fd) = result.as_ref() {
182            match self.first_free {
183                None => self.first_free = Some(idx),
184                Some(x) if x > idx => self.first_free = Some(idx),
185                _ => (),
186            }
187
188            fd.inode.drop_one_handle();
189        }
190
191        result
192    }
193
194    pub fn clear(&mut self) {
195        for fd in &self.fds {
196            if let Some(fd) = fd.as_ref() {
197                fd.inode.drop_one_handle();
198            }
199        }
200
201        self.fds.clear();
202        self.first_free = None;
203    }
204
205    pub fn iter(&self) -> FdListIterator<'_> {
206        FdListIterator {
207            fds_iterator: self.fds.iter(),
208            idx: 0,
209        }
210    }
211
212    pub fn keys(&self) -> impl Iterator<Item = WasiFd> + '_ {
213        self.iter().map(|(key, _)| key)
214    }
215
216    pub fn iter_mut(&mut self) -> FdListIteratorMut<'_> {
217        FdListIteratorMut {
218            fds_iterator: self.fds.iter_mut(),
219            idx: 0,
220        }
221    }
222}
223
224impl Clone for FdList {
225    fn clone(&self) -> Self {
226        for fd in &self.fds {
227            if let Some(fd) = fd.as_ref() {
228                fd.inode.acquire_handle();
229            }
230        }
231
232        Self {
233            fds: self.fds.clone(),
234            first_free: self.first_free,
235        }
236    }
237}
238
239impl Drop for FdList {
240    fn drop(&mut self) {
241        self.clear();
242    }
243}
244
245impl<'a> Iterator for FdListIterator<'a> {
246    type Item = (WasiFd, &'a Fd);
247
248    fn next(&mut self) -> Option<Self::Item> {
249        loop {
250            match self.fds_iterator.next() {
251                None => return None,
252
253                Some(None) => {
254                    self.idx += 1;
255                    continue;
256                }
257
258                Some(Some(fd)) => {
259                    let wasi_fd = self.idx as WasiFd;
260                    self.idx += 1;
261                    return Some((wasi_fd, fd));
262                }
263            }
264        }
265    }
266}
267
268impl<'a> Iterator for FdListIteratorMut<'a> {
269    type Item = (WasiFd, &'a mut FdInner);
270
271    fn next(&mut self) -> Option<Self::Item> {
272        loop {
273            match self.fds_iterator.next() {
274                None => return None,
275
276                Some(None) => {
277                    self.idx += 1;
278                    continue;
279                }
280
281                Some(Some(fd)) => {
282                    let wasi_fd = self.idx as WasiFd;
283                    self.idx += 1;
284                    return Some((wasi_fd, &mut fd.inner));
285                }
286            }
287        }
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use std::{
294        borrow::Cow,
295        sync::{
296            Arc, RwLock,
297            atomic::{AtomicI32, AtomicU64},
298        },
299    };
300
301    use assert_panic::assert_panic;
302    use wasmer_wasix_types::wasi::{Fdflags, Fdflagsext, Rights};
303
304    use crate::fs::{Inode, InodeGuard, InodeVal, Kind, fd::FdInner};
305
306    use super::{Fd, FdList, WasiFd};
307
308    fn useless_fd(n: u16) -> Fd {
309        Fd {
310            open_flags: 0,
311            inode: InodeGuard {
312                ino: Inode(0),
313                inner: Arc::new(InodeVal {
314                    is_preopened: false,
315                    kind: RwLock::new(Kind::Buffer { buffer: vec![] }),
316                    name: RwLock::new(Cow::Borrowed("")),
317                    stat: RwLock::new(Default::default()),
318                }),
319                open_handles: Arc::new(AtomicI32::new(0)),
320            },
321            is_stdio: false,
322            inner: FdInner {
323                offset: Arc::new(AtomicU64::new(0)),
324                rights: Rights::empty(),
325                rights_inheriting: Rights::empty(),
326                flags: Fdflags::from_bits_preserve(n),
327                fd_flags: Fdflagsext::empty(),
328            },
329        }
330    }
331
332    fn is_useless_fd(fd: &Fd, n: u16) -> bool {
333        fd.inner.flags.bits() == n
334    }
335
336    fn is_useless_fd_inner(fd_inner: &FdInner, n: u16) -> bool {
337        fd_inner.flags.bits() == n
338    }
339
340    fn assert_fds_match(l: &FdList, expected: &[(WasiFd, u16)]) {
341        let mut i = l.iter();
342
343        for e in expected {
344            let next = i.next().expect("Should have a next element");
345            assert_eq!(next.0, e.0);
346            assert!(is_useless_fd(next.1, e.1));
347        }
348
349        assert!(i.next().is_none());
350    }
351
352    #[test]
353    fn can_append_fds() {
354        let mut l = FdList::new();
355        l.insert_first_free(useless_fd(0));
356        l.insert_first_free(useless_fd(1));
357
358        assert_fds_match(&l, &[(0, 0), (1, 1)]);
359    }
360
361    #[test]
362    fn can_append_in_holes() {
363        let mut l = FdList::new();
364        l.insert_first_free(useless_fd(0));
365        l.insert_first_free(useless_fd(1));
366        l.insert_first_free(useless_fd(2));
367        l.insert_first_free(useless_fd(3));
368        l.remove(1);
369        l.remove(2);
370        l.insert_first_free(useless_fd(4));
371
372        assert_fds_match(&l, &[(0, 0), (1, 4), (3, 3)]);
373    }
374
375    #[test]
376    fn can_have_holes_in_different_places() {
377        let mut l = FdList::new();
378        l.insert_first_free(useless_fd(0));
379        l.insert_first_free(useless_fd(1));
380        l.insert_first_free(useless_fd(2));
381        l.insert_first_free(useless_fd(3));
382        l.insert_first_free(useless_fd(4));
383        l.remove(1);
384        l.remove(3);
385        l.insert_first_free(useless_fd(5));
386        l.insert_first_free(useless_fd(6));
387
388        assert_fds_match(&l, &[(0, 0), (1, 5), (2, 2), (3, 6), (4, 4)]);
389    }
390
391    #[test]
392    fn hole_moves_back_correctly() {
393        let mut l = FdList::new();
394        l.insert_first_free(useless_fd(0));
395        l.insert_first_free(useless_fd(1));
396        l.insert_first_free(useless_fd(2));
397        l.insert_first_free(useless_fd(3));
398        l.remove(3);
399        assert_eq!(l.first_free, Some(3));
400        l.remove(1);
401        assert_eq!(l.first_free, Some(1));
402        l.insert_first_free(useless_fd(4));
403
404        assert_fds_match(&l, &[(0, 0), (1, 4), (2, 2)]);
405    }
406
407    #[test]
408    fn insert_at_first_free_updates_first_free() {
409        let mut l = FdList::new();
410        l.insert_first_free(useless_fd(0));
411        l.insert_first_free(useless_fd(1));
412        l.insert_first_free(useless_fd(2));
413        l.insert_first_free(useless_fd(3));
414        l.remove(1);
415        l.remove(2);
416        assert!(l.insert(true, 1, useless_fd(4)));
417        assert_eq!(l.first_free, Some(2));
418
419        assert_fds_match(&l, &[(0, 0), (1, 4), (3, 3)]);
420    }
421
422    #[test]
423    fn next_and_last_fd_reported_correctly() {
424        let mut l = FdList::new();
425
426        assert_eq!(l.next_free_fd(), 0);
427        assert_eq!(l.last_fd(), None);
428
429        l.insert_first_free(useless_fd(0));
430        l.insert_first_free(useless_fd(1));
431
432        assert_eq!(l.next_free_fd(), 2);
433        assert_eq!(l.last_fd(), Some(1));
434
435        l.insert_first_free(useless_fd(2));
436        l.insert_first_free(useless_fd(3));
437
438        assert_eq!(l.next_free_fd(), 4);
439        assert_eq!(l.last_fd(), Some(3));
440
441        l.remove(3);
442
443        assert_eq!(l.next_free_fd(), 3);
444        assert_eq!(l.last_fd(), Some(2));
445
446        l.remove(1);
447
448        assert_eq!(l.next_free_fd(), 1);
449        assert_eq!(l.last_fd(), Some(2));
450    }
451
452    #[test]
453    fn get_works() {
454        let mut l = FdList::new();
455
456        l.insert_first_free(useless_fd(0));
457        l.insert_first_free(useless_fd(1));
458        l.insert_first_free(useless_fd(2));
459        l.insert_first_free(useless_fd(3));
460        l.insert_first_free(useless_fd(4));
461        l.remove(1);
462        l.remove(3);
463
464        assert!(l.get(1).is_none());
465        assert!(is_useless_fd(l.get(2).unwrap(), 2));
466
467        let at_4 = l.get_mut(4).unwrap();
468        assert!(is_useless_fd_inner(at_4, 4));
469        at_4.flags = Fdflags::from_bits_preserve(5); // Update the "useless FD" number without changing the InodeGuard
470        assert!(is_useless_fd(l.get(4).unwrap(), 5));
471
472        assert!(l.get(10).is_none());
473        assert!(l.get_mut(10).is_none());
474    }
475
476    #[test]
477    fn insert_at_works() {
478        let mut l = FdList::new();
479
480        l.insert_first_free(useless_fd(0));
481        l.insert_first_free(useless_fd(1));
482        l.insert_first_free(useless_fd(2));
483        l.remove(1);
484
485        assert!(l.insert(false, 2, useless_fd(3)));
486        assert!(is_useless_fd(l.get(2).unwrap(), 3));
487
488        assert!(!l.insert(true, 2, useless_fd(4)));
489        assert!(is_useless_fd(l.get(2).unwrap(), 3));
490
491        assert!(l.insert(true, 1, useless_fd(5)));
492        assert!(is_useless_fd(l.get(1).unwrap(), 5));
493    }
494
495    #[test]
496    fn insert_at_can_insert_beyond_end_of_list() {
497        let mut l = FdList::new();
498
499        l.insert_first_free(useless_fd(0));
500
501        assert!(l.insert(false, 1, useless_fd(1)));
502        assert!(is_useless_fd(l.get(1).unwrap(), 1));
503
504        // Extending by exactly one element shouldn't change first_free
505        assert_eq!(l.last_fd(), Some(1));
506        assert_eq!(l.next_free_fd(), 2);
507        assert!(l.first_free.is_none());
508
509        // Now create a hole
510        assert!(l.insert(false, 5, useless_fd(5)));
511        assert!(is_useless_fd(l.get(5).unwrap(), 5));
512
513        for i in 2..=4 {
514            assert!(l.get(i).is_none());
515        }
516
517        // Creating a hole should update first_free
518        assert_eq!(l.last_fd(), Some(5));
519        assert_eq!(l.next_free_fd(), 2);
520        assert_eq!(l.first_free, Some(2));
521    }
522
523    #[test]
524    fn insert_first_free_after_beyond_end_of_empty_list() {
525        let mut l = FdList::new();
526        assert_eq!(l.insert_first_free_after(useless_fd(1), 5), 5);
527        assert!(is_useless_fd(l.get(5).unwrap(), 1));
528    }
529
530    #[test]
531    fn insert_first_free_after_beyond_end_of_non_empty_list() {
532        let mut l = FdList::new();
533        l.insert(false, 0, useless_fd(0));
534        assert_eq!(l.insert_first_free_after(useless_fd(1), 5), 5);
535        assert!(is_useless_fd(l.get(5).unwrap(), 1));
536    }
537
538    #[test]
539    fn insert_first_free_after_beyond_end_of_non_empty_list_with_hole() {
540        let mut l = FdList::new();
541        l.insert(false, 0, useless_fd(0));
542        l.insert(false, 2, useless_fd(2));
543        assert_eq!(l.insert_first_free_after(useless_fd(1), 5), 5);
544        assert!(is_useless_fd(l.get(5).unwrap(), 1));
545    }
546
547    #[test]
548    fn insert_first_free_after_behind_hole() {
549        let mut l = FdList::new();
550        l.insert_first_free(useless_fd(0));
551        l.insert_first_free(useless_fd(1));
552        l.insert_first_free(useless_fd(2));
553        l.insert_first_free(useless_fd(3));
554        l.remove(2).unwrap();
555        assert_eq!(l.insert_first_free_after(useless_fd(5), 1), 2);
556        assert!(is_useless_fd(l.get(2).unwrap(), 5));
557    }
558
559    #[test]
560    fn insert_first_free_after_behind_end_without_hole() {
561        let mut l = FdList::new();
562        l.insert_first_free(useless_fd(0));
563        l.insert_first_free(useless_fd(1));
564        l.insert_first_free(useless_fd(2));
565        l.insert_first_free(useless_fd(3));
566        assert_eq!(l.insert_first_free_after(useless_fd(5), 2), 4);
567        assert!(is_useless_fd(l.get(4).unwrap(), 5));
568    }
569
570    #[test]
571    fn insert_first_free_after_between_hole_and_end_without_other_hole() {
572        let mut l = FdList::new();
573        l.insert_first_free(useless_fd(0));
574        l.insert_first_free(useless_fd(1));
575        l.insert_first_free(useless_fd(2));
576        l.insert_first_free(useless_fd(3));
577        l.insert_first_free(useless_fd(4));
578        l.remove(1).unwrap();
579        assert_eq!(l.insert_first_free_after(useless_fd(5), 2), 5);
580        assert!(is_useless_fd(l.get(5).unwrap(), 5));
581    }
582
583    #[test]
584    fn insert_first_free_after_between_hole_and_end_with_other_hole() {
585        let mut l = FdList::new();
586        l.insert_first_free(useless_fd(0));
587        l.insert_first_free(useless_fd(1));
588        l.insert_first_free(useless_fd(2));
589        l.insert_first_free(useless_fd(3));
590        l.insert_first_free(useless_fd(4));
591        l.remove(1).unwrap();
592        l.remove(3).unwrap();
593        assert_eq!(l.insert_first_free_after(useless_fd(5), 2), 3);
594        assert!(is_useless_fd(l.get(3).unwrap(), 5));
595    }
596
597    #[test]
598    fn remove_works() {
599        let mut l = FdList::new();
600
601        l.insert_first_free(useless_fd(0));
602        l.insert_first_free(useless_fd(1));
603        l.insert_first_free(useless_fd(2));
604
605        assert!(is_useless_fd(&l.remove(1).unwrap(), 1));
606        assert!(l.remove(1).is_none());
607        assert!(l.remove(100000).is_none());
608    }
609
610    #[test]
611    fn clear_works() {
612        let mut l = FdList::new();
613
614        l.insert_first_free(useless_fd(0));
615        l.insert_first_free(useless_fd(1));
616        l.insert_first_free(useless_fd(2));
617        l.remove(1);
618
619        l.clear();
620
621        assert_eq!(l.next_free_fd(), 0);
622        assert!(l.last_fd().is_none());
623        assert_eq!(l.fds.len(), 0);
624        assert!(l.first_free.is_none());
625    }
626
627    #[test]
628    fn iter_mut_works() {
629        let mut l = FdList::new();
630        l.insert_first_free(useless_fd(0));
631        l.insert_first_free(useless_fd(1));
632
633        let mut i = l.iter_mut();
634
635        let next = i.next().unwrap();
636        assert_eq!(next.0, 0);
637        assert!(is_useless_fd_inner(next.1, 0));
638        next.1.flags = Fdflags::from_bits_preserve(2); // Update the "useless FD" number without changing the InodeGuard
639
640        let next = i.next().unwrap();
641        assert_eq!(next.0, 1);
642        assert!(is_useless_fd_inner(next.1, 1));
643
644        assert!(i.next().is_none());
645
646        assert_fds_match(&l, &[(0, 2), (1, 1)]);
647    }
648
649    #[test]
650    fn open_handles_are_updated_correctly() {
651        let mut l = FdList::new();
652        l.insert_first_free(useless_fd(0));
653        l.insert_first_free(useless_fd(1));
654
655        let fd0 = l.get(0).unwrap().clone();
656        assert_eq!(fd0.inode.handle_count(), 1);
657
658        // Try removing an FD, should drop the handle
659        let fd1 = l.get(1).unwrap().clone();
660        assert_eq!(fd1.inode.handle_count(), 1);
661        l.remove(1).unwrap();
662        assert_eq!(fd1.inode.handle_count(), 0);
663
664        // Existing FDs should get a new handle when cloning the list
665        let mut l2 = l.clone();
666        assert_eq!(fd0.inode.handle_count(), 2);
667
668        {
669            // Dropping the list should drop open handles
670            let l3 = l2.clone();
671            assert_eq!(fd0.inode.handle_count(), 3);
672            drop(l3);
673            assert_eq!(fd0.inode.handle_count(), 2);
674        }
675
676        // Clearing the list should drop open handles
677        l.clear();
678        assert_eq!(fd0.inode.handle_count(), 1);
679
680        // Clear the last handle, should go back to zero
681        l2.clear();
682        assert_eq!(fd0.inode.handle_count(), 0);
683
684        assert_panic!(
685            fd0.inode.drop_one_handle(),
686            &str,
687            "InodeGuard handle dropped too many times"
688        );
689
690        assert_panic!(drop(fd0.inode.write()), String, contains "PoisonError");
691    }
692
693    #[test]
694    fn messing_with_inode_causes_panic() {
695        // We want to pin this behavior down, as not causing a panic
696        // can lead to inconsistencies
697        let mut l = FdList::new();
698        l.insert_first_free(useless_fd(0));
699
700        let fd = l.get(0).unwrap();
701        fd.inode.drop_one_handle();
702
703        assert_panic!(drop(l), &str, "InodeGuard handle dropped too many times");
704    }
705}
wasmer_wasix/fs/fd_list.rs

wasmer_wasix/fs/
fd_list.rs
