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

wasmer_wasix/fs/
fd_list.rs
