Auto merge of #40091 - eddyb:rollup, r=eddyb

Rollup of 28 pull requests

- Successful merges: #39859, #39864, #39888, #39903, #39905, #39914, #39945, #39950, #39953, #39961, #39980, #39988, #39993, #39995, #40019, #40020, #40022, #40024, #40025, #40026, #40027, #40031, #40035, #40037, #40038, #40064, #40069, #40086
- Failed merges: #39927, #40008, #40047

10 files changed, 47 insertions, 42 deletions

diff --git a/src/libstd/build.rs b/src/libstd/build.rs
index 0fca374f6e6..038dea77f3e 100644
--- a/src/libstd/build.rs
+++ b/src/libstd/build.rs
@@ -59,6 +59,10 @@ fn main() {
         println!("cargo:rustc-link-lib=userenv");
         println!("cargo:rustc-link-lib=shell32");
     } else if target.contains("fuchsia") {
+        // use system-provided libbacktrace
+        if cfg!(feature = "backtrace") {
+            println!("cargo:rustc-link-lib=backtrace");
+        }
         println!("cargo:rustc-link-lib=magenta");
         println!("cargo:rustc-link-lib=mxio");
         println!("cargo:rustc-link-lib=launchpad"); // for std::process
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index fd5827b4c07..f0738fe9b70 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -182,12 +182,12 @@ impl DefaultResizePolicy {
 // ----------------------
 // To protect against degenerate performance scenarios (including DOS attacks),
 // the implementation includes an adaptive behavior that can resize the map
-// early (before its capacity is exceeded) when suspiciously long probe or
-// forward shifts sequences are encountered.
+// early (before its capacity is exceeded) when suspiciously long probe sequences
+// are encountered.
 //
 // With this algorithm in place it would be possible to turn a CPU attack into
 // a memory attack due to the aggressive resizing. To prevent that the
-// adaptive behavior only triggers when the map occupancy is half the maximum occupancy.
+// adaptive behavior only triggers when the map is at least half full.
 // This reduces the effectiveness of the algorithm but also makes it completely safe.
 //
 // The previous safety measure also prevents degenerate interactions with
@@ -195,16 +195,11 @@ impl DefaultResizePolicy {
 // DOS attack.
 //
 const DISPLACEMENT_THRESHOLD: usize = 128;
-const FORWARD_SHIFT_THRESHOLD: usize = 512;
 //
-// The thresholds of 128 and 512 are chosen to minimize the chance of exceeding them.
+// The threshold of 128 is chosen to minimize the chance of exceeding it.
 // In particular, we want that chance to be less than 10^-8 with a load of 90%.
 // For displacement, the smallest constant that fits our needs is 90,
-// so we round that up to 128. For the number of forward-shifted buckets,
-// we choose k=512. Keep in mind that the run length is a sum of the displacement and
-// the number of forward-shifted buckets, so its threshold is 128+512=640.
-// Even though the probability of having a run length of more than 640 buckets may be
-// higher than the probability we want, it should be low enough.
+// so we round that up to 128.
 //
 // At a load factor of α, the odds of finding the target bucket after exactly n
 // unsuccesful probes[1] are
@@ -212,16 +207,12 @@ const FORWARD_SHIFT_THRESHOLD: usize = 512;
 // Pr_α{displacement = n} =
 // (1 - α) / α * ∑_{k≥1} e^(-kα) * (kα)^(k+n) / (k + n)! * (1 - kα / (k + n + 1))
 //
-// We use this formula to find the probability of loading half of triggering the adaptive behavior
+// We use this formula to find the probability of triggering the adaptive behavior
 //
 // Pr_0.909{displacement > 128} = 1.601 * 10^-11
 //
-// FIXME: Extend with math for shift threshold in [2]
-//
 // 1. Alfredo Viola (2005). Distributional analysis of Robin Hood linear probing
 //    hashing with buckets.
-// 2. http://www.cs.tau.ac.il/~zwick/Adv-Alg-2015/Linear-Probing.pdf
-
 
 /// A hash map implementation which uses linear probing with Robin Hood bucket
 /// stealing.
@@ -494,7 +485,7 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
                                 mut hash: SafeHash,
                                 mut key: K,
                                 mut val: V)
-                                -> (usize, &'a mut V) {
+                                -> &'a mut V {
     let start_index = bucket.index();
     let size = bucket.table().size();
     // Save the *starting point*.
@@ -519,7 +510,6 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
                 Empty(bucket) => {
                     // Found a hole!
                     let bucket = bucket.put(hash, key, val);
-                    let end_index = bucket.index();
                     // Now that it's stolen, just read the value's pointer
                     // right out of the table! Go back to the *starting point*.
                     //
@@ -527,7 +517,7 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
                     // bucket, which is a FullBucket on top of a
                     // FullBucketMut, into just one FullBucketMut. The "table"
                     // refers to the inner FullBucketMut in this context.
-                    return (end_index - start_index, bucket.into_table().into_mut_refs().1);
+                    return bucket.into_table().into_mut_refs().1;
                 }
                 Full(bucket) => bucket,
             };
@@ -2128,18 +2118,16 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
     pub fn insert(self, value: V) -> &'a mut V {
         match self.elem {
             NeqElem(bucket, disp) => {
-                let (shift, v_ref) = robin_hood(bucket, disp, self.hash, self.key, value);
-                if disp >= DISPLACEMENT_THRESHOLD || shift >= FORWARD_SHIFT_THRESHOLD {
+                if disp >= DISPLACEMENT_THRESHOLD {
                     *self.long_probes = true;
                 }
-                v_ref
+                robin_hood(bucket, disp, self.hash, self.key, value)
             },
             NoElem(bucket, disp) => {
                 if disp >= DISPLACEMENT_THRESHOLD {
                     *self.long_probes = true;
                 }
-                let bucket = bucket.put(self.hash, self.key, value);
-                bucket.into_mut_refs().1
+                bucket.put(self.hash, self.key, value).into_mut_refs().1
             },
         }
     }
diff --git a/src/libstd/panic.rs b/src/libstd/panic.rs
index ac0d0d2afb8..f99634ecac2 100644
--- a/src/libstd/panic.rs
+++ b/src/libstd/panic.rs
@@ -198,7 +198,7 @@ impl<T: RefUnwindSafe + ?Sized> UnwindSafe for *const T {}
 #[stable(feature = "catch_unwind", since = "1.9.0")]
 impl<T: RefUnwindSafe + ?Sized> UnwindSafe for *mut T {}
 #[unstable(feature = "unique", issue = "27730")]
-impl<T: UnwindSafe> UnwindSafe for Unique<T> {}
+impl<T: UnwindSafe + ?Sized> UnwindSafe for Unique<T> {}
 #[unstable(feature = "shared", issue = "27730")]
 impl<T: RefUnwindSafe + ?Sized> UnwindSafe for Shared<T> {}
 #[stable(feature = "catch_unwind", since = "1.9.0")]
diff --git a/src/libstd/sys/redox/mod.rs b/src/libstd/sys/redox/mod.rs
index 5982bdd6549..31c40ea58b1 100644
--- a/src/libstd/sys/redox/mod.rs
+++ b/src/libstd/sys/redox/mod.rs
@@ -13,7 +13,7 @@
 use io::{self, ErrorKind};
 
 pub mod args;
-#[cfg(any(not(cargobuild), feature = "backtrace"))]
+#[cfg(feature = "backtrace")]
 pub mod backtrace;
 pub mod condvar;
 pub mod env;
diff --git a/src/libstd/sys/redox/net/tcp.rs b/src/libstd/sys/redox/net/tcp.rs
index a3f202ccd97..936097d7fb2 100644
--- a/src/libstd/sys/redox/net/tcp.rs
+++ b/src/libstd/sys/redox/net/tcp.rs
@@ -63,6 +63,10 @@ impl TcpStream {
         Ok(path_to_local_addr(path.to_str().unwrap_or("")))
     }
 
+    pub fn peek(&self, _buf: &mut [u8]) -> Result<usize> {
+        Err(Error::new(ErrorKind::Other, "TcpStream::peek not implemented"))
+    }
+
     pub fn shutdown(&self, _how: Shutdown) -> Result<()> {
         Err(Error::new(ErrorKind::Other, "TcpStream::shutdown not implemented"))
     }
diff --git a/src/libstd/sys/redox/net/udp.rs b/src/libstd/sys/redox/net/udp.rs
index 36f0819d308..93ebcc95fd0 100644
--- a/src/libstd/sys/redox/net/udp.rs
+++ b/src/libstd/sys/redox/net/udp.rs
@@ -87,6 +87,14 @@ impl UdpSocket {
         Ok(path_to_local_addr(path.to_str().unwrap_or("")))
     }
 
+    pub fn peek(&self, _buf: &mut [u8]) -> Result<usize> {
+        Err(Error::new(ErrorKind::Other, "UdpSocket::peek not implemented"))
+    }
+
+    pub fn peek_from(&self, _buf: &mut [u8]) -> Result<(usize, SocketAddr)> {
+        Err(Error::new(ErrorKind::Other, "UdpSocket::peek_from not implemented"))
+    }
+
     pub fn broadcast(&self) -> Result<bool> {
         Err(Error::new(ErrorKind::Other, "UdpSocket::broadcast not implemented"))
     }
diff --git a/src/libstd/sys/unix/fs.rs b/src/libstd/sys/unix/fs.rs
index 8b5c0c04276..d0fb96b1ff1 100644
--- a/src/libstd/sys/unix/fs.rs
+++ b/src/libstd/sys/unix/fs.rs
@@ -35,7 +35,8 @@ use libc::{stat as stat64, fstat as fstat64, lstat as lstat64, off_t as off64_t,
            ftruncate as ftruncate64, lseek as lseek64, dirent as dirent64, open as open64};
 #[cfg(not(any(target_os = "linux",
               target_os = "emscripten",
-              target_os = "solaris")))]
+              target_os = "solaris",
+              target_os = "fuchsia")))]
 use libc::{readdir_r as readdir64_r};
 
 pub struct File(FileDesc);
@@ -59,10 +60,10 @@ pub struct DirEntry {
     entry: dirent64,
     root: Arc<PathBuf>,
     // We need to store an owned copy of the directory name
-    // on Solaris because a) it uses a zero-length array to
-    // store the name, b) its lifetime between readdir calls
-    // is not guaranteed.
-    #[cfg(target_os = "solaris")]
+    // on Solaris and Fuchsia because a) it uses a zero-length
+    // array to store the name, b) its lifetime between readdir
+    // calls is not guaranteed.
+    #[cfg(any(target_os = "solaris", target_os = "fuchsia"))]
     name: Box<[u8]>
 }
 
@@ -205,14 +206,14 @@ impl fmt::Debug for ReadDir {
 impl Iterator for ReadDir {
     type Item = io::Result<DirEntry>;
 
-    #[cfg(target_os = "solaris")]
+    #[cfg(any(target_os = "solaris", target_os = "fuchsia"))]
     fn next(&mut self) -> Option<io::Result<DirEntry>> {
         unsafe {
             loop {
                 // Although readdir_r(3) would be a correct function to use here because
-                // of the thread safety, on Illumos the readdir(3C) function is safe to use
-                // in threaded applications and it is generally preferred over the
-                // readdir_r(3C) function.
+                // of the thread safety, on Illumos and Fuchsia the readdir(3C) function
+                // is safe to use in threaded applications and it is generally preferred
+                // over the readdir_r(3C) function.
                 super::os::set_errno(0);
                 let entry_ptr = libc::readdir(self.dirp.0);
                 if entry_ptr.is_null() {
@@ -240,7 +241,7 @@ impl Iterator for ReadDir {
         }
     }
 
-    #[cfg(not(target_os = "solaris"))]
+    #[cfg(not(any(target_os = "solaris", target_os = "fuchsia")))]
     fn next(&mut self) -> Option<io::Result<DirEntry>> {
         unsafe {
             let mut ret = DirEntry {
@@ -344,14 +345,14 @@ impl DirEntry {
     #[cfg(any(target_os = "android",
               target_os = "linux",
               target_os = "emscripten",
-              target_os = "haiku",
-              target_os = "fuchsia"))]
+              target_os = "haiku"))]
     fn name_bytes(&self) -> &[u8] {
         unsafe {
             CStr::from_ptr(self.entry.d_name.as_ptr()).to_bytes()
         }
     }
-    #[cfg(target_os = "solaris")]
+    #[cfg(any(target_os = "solaris",
+              target_os = "fuchsia"))]
     fn name_bytes(&self) -> &[u8] {
         &*self.name
     }
diff --git a/src/libstd/sys/unix/os.rs b/src/libstd/sys/unix/os.rs
index e78928c2667..36928696c40 100644
--- a/src/libstd/sys/unix/os.rs
+++ b/src/libstd/sys/unix/os.rs
@@ -64,7 +64,7 @@ pub fn errno() -> i32 {
 }
 
 /// Sets the platform-specific value of errno
-#[cfg(target_os = "solaris")] // only needed for readdir so far
+#[cfg(any(target_os = "solaris", target_os = "fuchsia"))] // only needed for readdir so far
 pub fn set_errno(e: i32) {
     unsafe {
         *errno_location() = e as c_int
diff --git a/src/libstd/sys/unix/process/magenta.rs b/src/libstd/sys/unix/process/magenta.rs
index a81bedcad22..08a827ce081 100644
--- a/src/libstd/sys/unix/process/magenta.rs
+++ b/src/libstd/sys/unix/process/magenta.rs
@@ -111,7 +111,7 @@ extern {
     pub fn mx_handle_duplicate(handle: mx_handle_t, rights: mx_rights_t,
                                out: *const mx_handle_t) -> mx_handle_t;
 
-    pub fn mx_handle_wait_one(handle: mx_handle_t, signals: mx_signals_t, timeout: mx_time_t,
+    pub fn mx_object_wait_one(handle: mx_handle_t, signals: mx_signals_t, timeout: mx_time_t,
                               pending: *mut mx_signals_t) -> mx_status_t;
 
     pub fn mx_object_get_info(handle: mx_handle_t, topic: u32, buffer: *mut c_void,
diff --git a/src/libstd/sys/unix/process/process_fuchsia.rs b/src/libstd/sys/unix/process/process_fuchsia.rs
index 0bb2e0c1a83..608e44ca9e8 100644
--- a/src/libstd/sys/unix/process/process_fuchsia.rs
+++ b/src/libstd/sys/unix/process/process_fuchsia.rs
@@ -151,7 +151,7 @@ impl Process {
         let mut avail: mx_size_t = 0;
 
         unsafe {
-            mx_cvt(mx_handle_wait_one(self.handle.raw(), MX_TASK_TERMINATED,
+            mx_cvt(mx_object_wait_one(self.handle.raw(), MX_TASK_TERMINATED,
                                       MX_TIME_INFINITE, ptr::null_mut()))?;
             mx_cvt(mx_object_get_info(self.handle.raw(), MX_INFO_PROCESS,
                                       &mut proc_info as *mut _ as *mut libc::c_void,
@@ -174,7 +174,7 @@ impl Process {
         let mut avail: mx_size_t = 0;
 
         unsafe {
-            let status = mx_handle_wait_one(self.handle.raw(), MX_TASK_TERMINATED,
+            let status = mx_object_wait_one(self.handle.raw(), MX_TASK_TERMINATED,
                                             0, ptr::null_mut());
             match status {
                 0 => { }, // Success