diff --git a/adb/adb.h b/adb/adb.h
index 7e9af9e..26b5fa1 100644
--- a/adb/adb.h
+++ b/adb/adb.h
@@ -133,7 +133,7 @@
 int adb_server_main(int is_daemon, const std::string& socket_spec, int ack_reply_fd);
 
 /* initialize a transport object's func pointers and state */
-int init_socket_transport(atransport* t, int s, int port, int local);
+int init_socket_transport(atransport* t, unique_fd s, int port, int local);
 void init_usb_transport(atransport* t, usb_handle* usb);
 
 std::string getEmulatorSerialString(int console_port);
diff --git a/adb/adb_unique_fd.h b/adb/adb_unique_fd.h
index be63262..bad501a 100644
--- a/adb/adb_unique_fd.h
+++ b/adb/adb_unique_fd.h
@@ -31,3 +31,7 @@
 #if !defined(_WIN32)
 bool Pipe(unique_fd* read, unique_fd* write, int flags = 0);
 #endif
+
+template <typename T>
+int adb_close(const android::base::unique_fd_impl<T>&)
+        __attribute__((__unavailable__("adb_close called on unique_fd")));
diff --git a/adb/client/bugreport.cpp b/adb/client/bugreport.cpp
index abef86a..346bb4b 100644
--- a/adb/client/bugreport.cpp
+++ b/adb/client/bugreport.cpp
@@ -25,8 +25,9 @@
 #include <android-base/strings.h>
 
 #include "sysdeps.h"
+
 #include "adb_utils.h"
-#include "file_sync_service.h"
+#include "client/file_sync_client.h"
 
 static constexpr char BUGZ_BEGIN_PREFIX[] = "BEGIN:";
 static constexpr char BUGZ_PROGRESS_PREFIX[] = "PROGRESS:";
diff --git a/adb/client/commandline.cpp b/adb/client/commandline.cpp
index 7791895..a7a94e7 100644
--- a/adb/client/commandline.cpp
+++ b/adb/client/commandline.cpp
@@ -56,10 +56,10 @@
 #include "adb_unique_fd.h"
 #include "adb_utils.h"
 #include "bugreport.h"
+#include "client/file_sync_client.h"
 #include "commandline.h"
-#include "file_sync_service.h"
 #include "services.h"
-#include "shell_service.h"
+#include "shell_protocol.h"
 #include "sysdeps/chrono.h"
 #include "sysdeps/memory.h"
 
diff --git a/adb/client/file_sync_client.cpp b/adb/client/file_sync_client.cpp
index a438dbb..cb9bcfa 100644
--- a/adb/client/file_sync_client.cpp
+++ b/adb/client/file_sync_client.cpp
@@ -14,6 +14,8 @@
  * limitations under the License.
  */
 
+#include "client/file_sync_client.h"
+
 #include <dirent.h>
 #include <inttypes.h>
 #include <limits.h>
@@ -39,7 +41,7 @@
 #include "adb_client.h"
 #include "adb_io.h"
 #include "adb_utils.h"
-#include "file_sync_service.h"
+#include "file_sync_protocol.h"
 #include "line_printer.h"
 #include "sysdeps/errno.h"
 #include "sysdeps/stat.h"
diff --git a/adb/client/file_sync_client.h b/adb/client/file_sync_client.h
new file mode 100644
index 0000000..df7f14c
--- /dev/null
+++ b/adb/client/file_sync_client.h
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <string>
+#include <vector>
+
+bool do_sync_ls(const char* path);
+bool do_sync_push(const std::vector<const char*>& srcs, const char* dst, bool sync);
+bool do_sync_pull(const std::vector<const char*>& srcs, const char* dst, bool copy_attrs,
+                  const char* name = nullptr);
+
+bool do_sync_sync(const std::string& lpath, const std::string& rpath, bool list_only);
diff --git a/adb/daemon/file_sync_service.cpp b/adb/daemon/file_sync_service.cpp
index 0b71363..8c39a20 100644
--- a/adb/daemon/file_sync_service.cpp
+++ b/adb/daemon/file_sync_service.cpp
@@ -16,8 +16,9 @@
 
 #define TRACE_TAG SYNC
 
+#include "daemon/file_sync_service.h"
+
 #include "sysdeps.h"
-#include "file_sync_service.h"
 
 #include <dirent.h>
 #include <errno.h>
@@ -42,6 +43,7 @@
 #include "adb_io.h"
 #include "adb_trace.h"
 #include "adb_utils.h"
+#include "file_sync_protocol.h"
 #include "security_log_tags.h"
 #include "sysdeps/errno.h"
 
@@ -525,7 +527,7 @@
     return true;
 }
 
-void file_sync_service(android::base::unique_fd fd) {
+void file_sync_service(unique_fd fd) {
     std::vector<char> buffer(SYNC_DATA_MAX);
 
     while (handle_sync_command(fd.get(), buffer)) {
diff --git a/adb/remount_service.h b/adb/daemon/file_sync_service.h
similarity index 65%
copy from adb/remount_service.h
copy to adb/daemon/file_sync_service.h
index 45821ee..f300e7b 100644
--- a/adb/remount_service.h
+++ b/adb/daemon/file_sync_service.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 The Android Open Source Project
+ * Copyright (C) 2018 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -14,14 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef _REMOUNT_SERVICE_H_
-#define _REMOUNT_SERVICE_H_
+#pragma once
 
-#include <string>
+#include "adb_unique_fd.h"
 
-#include <android-base/unique_fd.h>
-
-bool make_block_device_writable(const std::string&);
-void remount_service(android::base::unique_fd, const std::string&);
-
-#endif
+void file_sync_service(unique_fd fd);
diff --git a/adb/daemon/framebuffer_service.cpp b/adb/daemon/framebuffer_service.cpp
index 9a620ab..8d28c49 100644
--- a/adb/daemon/framebuffer_service.cpp
+++ b/adb/daemon/framebuffer_service.cpp
@@ -57,7 +57,7 @@
     unsigned int alpha_length;
 } __attribute__((packed));
 
-void framebuffer_service(android::base::unique_fd fd) {
+void framebuffer_service(unique_fd fd) {
     struct fbinfo fbinfo;
     unsigned int i, bsize;
     char buf[640];
diff --git a/adb/daemon/framebuffer_service.h b/adb/daemon/framebuffer_service.h
index d99c6fe..264da59 100644
--- a/adb/daemon/framebuffer_service.h
+++ b/adb/daemon/framebuffer_service.h
@@ -14,11 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef _DAEMON_FRAMEBUFFER_SERVICE_H_
-#define _DAEMON_FRAMEBUFFER_SERVICE_H_
+#pragma once
 
-#include <android-base/unique_fd.h>
+#include "adb_unique_fd.h"
 
-void framebuffer_service(android::base::unique_fd fd);
-
-#endif  // _DAEMON_FRAMEBUFFER_SERVICE_H_
+void framebuffer_service(unique_fd fd);
diff --git a/adb/daemon/main.cpp b/adb/daemon/main.cpp
index c02cafa..f6f1acc 100644
--- a/adb/daemon/main.cpp
+++ b/adb/daemon/main.cpp
@@ -18,6 +18,7 @@
 
 #include "sysdeps.h"
 
+#include <android/fdsan.h>
 #include <errno.h>
 #include <getopt.h>
 #include <malloc.h>
@@ -177,6 +178,11 @@
 
     signal(SIGPIPE, SIG_IGN);
 
+    auto fdsan_level = android_fdsan_get_error_level();
+    if (fdsan_level == ANDROID_FDSAN_ERROR_LEVEL_DISABLED) {
+        android_fdsan_set_error_level(ANDROID_FDSAN_ERROR_LEVEL_WARN_ONCE);
+    }
+
     init_transport_registration();
 
     // We need to call this even if auth isn't enabled because the file
diff --git a/adb/daemon/remount_service.cpp b/adb/daemon/remount_service.cpp
index 1bb2fbb..76a1452 100644
--- a/adb/daemon/remount_service.cpp
+++ b/adb/daemon/remount_service.cpp
@@ -215,7 +215,7 @@
     android::base::SetProperty(ANDROID_RB_PROPERTY, reboot_cmd.c_str());
 }
 
-void remount_service(android::base::unique_fd fd, const std::string& cmd) {
+void remount_service(unique_fd fd, const std::string& cmd) {
     bool user_requested_reboot = cmd != "-R";
 
     if (getuid() != 0) {
@@ -251,7 +251,7 @@
     if (user_requested_reboot) {
         if (!dedup.empty() || verity_enabled) {
             if (verity_enabled) {
-                set_verity_enabled_state_service(android::base::unique_fd(dup(fd.get())), false);
+                set_verity_enabled_state_service(unique_fd(dup(fd.get())), false);
             }
             reboot_for_remount(fd.get(), !dedup.empty());
             return;
diff --git a/adb/remount_service.h b/adb/daemon/remount_service.h
similarity index 80%
rename from adb/remount_service.h
rename to adb/daemon/remount_service.h
index 45821ee..e4e2550 100644
--- a/adb/remount_service.h
+++ b/adb/daemon/remount_service.h
@@ -14,14 +14,11 @@
  * limitations under the License.
  */
 
-#ifndef _REMOUNT_SERVICE_H_
-#define _REMOUNT_SERVICE_H_
+#pragma once
 
 #include <string>
 
-#include <android-base/unique_fd.h>
+#include "adb_unique_fd.h"
 
 bool make_block_device_writable(const std::string&);
-void remount_service(android::base::unique_fd, const std::string&);
-
-#endif
+void remount_service(unique_fd, const std::string&);
diff --git a/adb/daemon/set_verity_enable_state_service.cpp b/adb/daemon/set_verity_enable_state_service.cpp
index 0f804e9..8c98c2d 100644
--- a/adb/daemon/set_verity_enable_state_service.cpp
+++ b/adb/daemon/set_verity_enable_state_service.cpp
@@ -132,7 +132,7 @@
     return true;
 }
 
-void set_verity_enabled_state_service(android::base::unique_fd fd, bool enable) {
+void set_verity_enabled_state_service(unique_fd fd, bool enable) {
     bool any_changed = false;
 
     // Figure out if we're using VB1.0 or VB2.0 (aka AVB) - by
diff --git a/adb/daemon/set_verity_enable_state_service.h b/adb/daemon/set_verity_enable_state_service.h
index 9f84f35..c1413c8 100644
--- a/adb/daemon/set_verity_enable_state_service.h
+++ b/adb/daemon/set_verity_enable_state_service.h
@@ -14,11 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef _DAEMON_SET_VERITY_ENABLED_STATE_SERVICE_H_
-#define _DAEMON_SET_VERITY_ENABLED_STATE_SERVICE_H_
+#pragma once
 
-#include <android-base/unique_fd.h>
+#include "adb_unique_fd.h"
 
-void set_verity_enabled_state_service(android::base::unique_fd fd, bool enable);
-
-#endif  // _DAEMON_SET_VERITY_ENABLED_STATE_SERVICE_H_
+void set_verity_enabled_state_service(unique_fd fd, bool enable);
diff --git a/adb/daemon/shell_service.cpp b/adb/daemon/shell_service.cpp
index 56d647a..b042e5f 100644
--- a/adb/daemon/shell_service.cpp
+++ b/adb/daemon/shell_service.cpp
@@ -106,6 +106,7 @@
 #include "adb_unique_fd.h"
 #include "adb_utils.h"
 #include "security_log_tags.h"
+#include "shell_protocol.h"
 
 namespace {
 
diff --git a/adb/daemon/shell_service.h b/adb/daemon/shell_service.h
new file mode 100644
index 0000000..3ffffa7
--- /dev/null
+++ b/adb/daemon/shell_service.h
@@ -0,0 +1,34 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+enum class SubprocessType {
+    kPty,
+    kRaw,
+};
+
+enum class SubprocessProtocol {
+    kNone,
+    kShell,
+};
+
+// Forks and starts a new shell subprocess. If |name| is empty an interactive
+// shell is started, otherwise |name| is executed non-interactively.
+//
+// Returns an open FD connected to the subprocess or -1 on failure.
+int StartSubprocess(const char* name, const char* terminal_type, SubprocessType type,
+                    SubprocessProtocol protocol);
diff --git a/adb/daemon/shell_service_test.cpp b/adb/daemon/shell_service_test.cpp
index 4e27822..d073537 100644
--- a/adb/daemon/shell_service_test.cpp
+++ b/adb/daemon/shell_service_test.cpp
@@ -27,6 +27,7 @@
 
 #include "adb.h"
 #include "adb_io.h"
+#include "shell_protocol.h"
 #include "sysdeps.h"
 
 class ShellServiceTest : public ::testing::Test {
diff --git a/adb/file_sync_protocol.h b/adb/file_sync_protocol.h
new file mode 100644
index 0000000..108639a
--- /dev/null
+++ b/adb/file_sync_protocol.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2007 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#define MKID(a, b, c, d) ((a) | ((b) << 8) | ((c) << 16) | ((d) << 24))
+
+#define ID_LSTAT_V1 MKID('S', 'T', 'A', 'T')
+#define ID_STAT_V2 MKID('S', 'T', 'A', '2')
+#define ID_LSTAT_V2 MKID('L', 'S', 'T', '2')
+#define ID_LIST MKID('L', 'I', 'S', 'T')
+#define ID_SEND MKID('S', 'E', 'N', 'D')
+#define ID_RECV MKID('R', 'E', 'C', 'V')
+#define ID_DENT MKID('D', 'E', 'N', 'T')
+#define ID_DONE MKID('D', 'O', 'N', 'E')
+#define ID_DATA MKID('D', 'A', 'T', 'A')
+#define ID_OKAY MKID('O', 'K', 'A', 'Y')
+#define ID_FAIL MKID('F', 'A', 'I', 'L')
+#define ID_QUIT MKID('Q', 'U', 'I', 'T')
+
+struct SyncRequest {
+    uint32_t id;           // ID_STAT, et cetera.
+    uint32_t path_length;  // <= 1024
+    // Followed by 'path_length' bytes of path (not NUL-terminated).
+} __attribute__((packed));
+
+union syncmsg {
+    struct __attribute__((packed)) {
+        uint32_t id;
+        uint32_t mode;
+        uint32_t size;
+        uint32_t time;
+    } stat_v1;
+    struct __attribute__((packed)) {
+        uint32_t id;
+        uint32_t error;
+        uint64_t dev;
+        uint64_t ino;
+        uint32_t mode;
+        uint32_t nlink;
+        uint32_t uid;
+        uint32_t gid;
+        uint64_t size;
+        int64_t atime;
+        int64_t mtime;
+        int64_t ctime;
+    } stat_v2;
+    struct __attribute__((packed)) {
+        uint32_t id;
+        uint32_t mode;
+        uint32_t size;
+        uint32_t time;
+        uint32_t namelen;
+    } dent;
+    struct __attribute__((packed)) {
+        uint32_t id;
+        uint32_t size;
+    } data;
+    struct __attribute__((packed)) {
+        uint32_t id;
+        uint32_t msglen;
+    } status;
+};
+
+#define SYNC_DATA_MAX (64 * 1024)
diff --git a/adb/file_sync_service.h b/adb/file_sync_service.h
deleted file mode 100644
index 608b3ad..0000000
--- a/adb/file_sync_service.h
+++ /dev/null
@@ -1,94 +0,0 @@
-/*
- * Copyright (C) 2007 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef _FILE_SYNC_SERVICE_H_
-#define _FILE_SYNC_SERVICE_H_
-
-#include <string>
-#include <vector>
-
-#include <android-base/unique_fd.h>
-
-#define MKID(a,b,c,d) ((a) | ((b) << 8) | ((c) << 16) | ((d) << 24))
-
-#define ID_LSTAT_V1 MKID('S','T','A','T')
-#define ID_STAT_V2 MKID('S','T','A','2')
-#define ID_LSTAT_V2 MKID('L','S','T','2')
-#define ID_LIST MKID('L','I','S','T')
-#define ID_SEND MKID('S','E','N','D')
-#define ID_RECV MKID('R','E','C','V')
-#define ID_DENT MKID('D','E','N','T')
-#define ID_DONE MKID('D','O','N','E')
-#define ID_DATA MKID('D','A','T','A')
-#define ID_OKAY MKID('O','K','A','Y')
-#define ID_FAIL MKID('F','A','I','L')
-#define ID_QUIT MKID('Q','U','I','T')
-
-struct SyncRequest {
-    uint32_t id;  // ID_STAT, et cetera.
-    uint32_t path_length;  // <= 1024
-    // Followed by 'path_length' bytes of path (not NUL-terminated).
-} __attribute__((packed)) ;
-
-union syncmsg {
-    struct __attribute__((packed)) {
-        uint32_t id;
-        uint32_t mode;
-        uint32_t size;
-        uint32_t time;
-    } stat_v1;
-    struct __attribute__((packed)) {
-        uint32_t id;
-        uint32_t error;
-        uint64_t dev;
-        uint64_t ino;
-        uint32_t mode;
-        uint32_t nlink;
-        uint32_t uid;
-        uint32_t gid;
-        uint64_t size;
-        int64_t atime;
-        int64_t mtime;
-        int64_t ctime;
-    } stat_v2;
-    struct __attribute__((packed)) {
-        uint32_t id;
-        uint32_t mode;
-        uint32_t size;
-        uint32_t time;
-        uint32_t namelen;
-    } dent;
-    struct __attribute__((packed)) {
-        uint32_t id;
-        uint32_t size;
-    } data;
-    struct __attribute__((packed)) {
-        uint32_t id;
-        uint32_t msglen;
-    } status;
-};
-
-void file_sync_service(android::base::unique_fd fd);
-bool do_sync_ls(const char* path);
-bool do_sync_push(const std::vector<const char*>& srcs, const char* dst, bool sync);
-bool do_sync_pull(const std::vector<const char*>& srcs, const char* dst,
-                  bool copy_attrs, const char* name=nullptr);
-
-bool do_sync_sync(const std::string& lpath, const std::string& rpath, bool list_only);
-
-#define SYNC_DATA_MAX (64*1024)
-
-#endif
diff --git a/adb/services.cpp b/adb/services.cpp
index 3d418cb..639bb46 100644
--- a/adb/services.cpp
+++ b/adb/services.cpp
@@ -37,7 +37,6 @@
 #include <android-base/parsenetaddress.h>
 #include <android-base/stringprintf.h>
 #include <android-base/strings.h>
-#include <android-base/unique_fd.h>
 #include <cutils/sockets.h>
 
 #if !ADB_HOST
@@ -49,31 +48,31 @@
 
 #include "adb.h"
 #include "adb_io.h"
+#include "adb_unique_fd.h"
 #include "adb_utils.h"
 #if !ADB_HOST
+#include "daemon/file_sync_service.h"
 #include "daemon/framebuffer_service.h"
+#include "daemon/remount_service.h"
 #include "daemon/set_verity_enable_state_service.h"
+#include "daemon/shell_service.h"
 #endif
-#include "file_sync_service.h"
-#include "remount_service.h"
 #include "services.h"
-#include "shell_service.h"
 #include "socket_spec.h"
 #include "sysdeps.h"
 #include "transport.h"
 
 namespace {
 
-void service_bootstrap_func(std::string service_name,
-                            std::function<void(android::base::unique_fd)> func,
-                            android::base::unique_fd fd) {
+void service_bootstrap_func(std::string service_name, std::function<void(unique_fd)> func,
+                            unique_fd fd) {
     adb_thread_setname(android::base::StringPrintf("%s svc %d", service_name.c_str(), fd.get()));
     func(std::move(fd));
 }
 
 #if !ADB_HOST
 
-void restart_root_service(android::base::unique_fd fd) {
+void restart_root_service(unique_fd fd) {
     if (getuid() == 0) {
         WriteFdExactly(fd.get(), "adbd is already running as root\n");
         return;
@@ -87,7 +86,7 @@
     WriteFdExactly(fd.get(), "restarting adbd as root\n");
 }
 
-void restart_unroot_service(android::base::unique_fd fd) {
+void restart_unroot_service(unique_fd fd) {
     if (getuid() != 0) {
         WriteFdExactly(fd.get(), "adbd not running as root\n");
         return;
@@ -96,7 +95,7 @@
     WriteFdExactly(fd.get(), "restarting adbd as non root\n");
 }
 
-void restart_tcp_service(android::base::unique_fd fd, int port) {
+void restart_tcp_service(unique_fd fd, int port) {
     if (port <= 0) {
         WriteFdFmt(fd.get(), "invalid port %d\n", port);
         return;
@@ -106,12 +105,12 @@
     WriteFdFmt(fd.get(), "restarting in TCP mode port: %d\n", port);
 }
 
-void restart_usb_service(android::base::unique_fd fd) {
+void restart_usb_service(unique_fd fd) {
     android::base::SetProperty("service.adb.tcp.port", "0");
     WriteFdExactly(fd.get(), "restarting in USB mode\n");
 }
 
-bool reboot_service_impl(android::base::unique_fd fd, const std::string& arg) {
+bool reboot_service_impl(unique_fd fd, const std::string& arg) {
     std::string reboot_arg = arg;
     bool auto_reboot = false;
 
@@ -152,7 +151,7 @@
     return true;
 }
 
-void reboot_service(android::base::unique_fd fd, const std::string& arg) {
+void reboot_service(unique_fd fd, const std::string& arg) {
     if (!reboot_service_impl(std::move(fd), arg)) {
         return;
     }
@@ -163,7 +162,7 @@
     }
 }
 
-void reconnect_service(android::base::unique_fd fd, atransport* t) {
+void reconnect_service(unique_fd fd, atransport* t) {
     WriteFdExactly(fd, "done");
     kick_transport(t);
 }
@@ -223,12 +222,11 @@
 
 #endif  // !ADB_HOST
 
-android::base::unique_fd create_service_thread(const char* service_name,
-                                               std::function<void(android::base::unique_fd)> func) {
+unique_fd create_service_thread(const char* service_name, std::function<void(unique_fd)> func) {
     int s[2];
     if (adb_socketpair(s)) {
         printf("cannot create service socket pair\n");
-        return android::base::unique_fd();
+        return unique_fd();
     }
     D("socketpair: (%d,%d)", s[0], s[1]);
 
@@ -241,10 +239,10 @@
     }
 #endif // !ADB_HOST
 
-    std::thread(service_bootstrap_func, service_name, func, android::base::unique_fd(s[1])).detach();
+    std::thread(service_bootstrap_func, service_name, func, unique_fd(s[1])).detach();
 
     D("service thread started, %d:%d",s[0], s[1]);
-    return android::base::unique_fd(s[0]);
+    return unique_fd(s[0]);
 }
 
 }  // namespace
@@ -407,7 +405,7 @@
     }
 }
 
-static void connect_service(android::base::unique_fd fd, std::string host) {
+static void connect_service(unique_fd fd, std::string host) {
     std::string response;
     if (!strncmp(host.c_str(), "emu:", 4)) {
         connect_emulator(host.c_str() + 4, &response);
diff --git a/adb/shell_service.h b/adb/shell_protocol.h
similarity index 79%
rename from adb/shell_service.h
rename to adb/shell_protocol.h
index e3d676a..2c82689 100644
--- a/adb/shell_service.h
+++ b/adb/shell_protocol.h
@@ -14,16 +14,7 @@
  * limitations under the License.
  */
 
-// This file contains classes and functionality to launch shell subprocesses
-// in adbd and communicate between those subprocesses and the adb client.
-//
-// The main features exposed here are:
-//   1. A ShellPacket class to wrap data in a simple protocol. Both adbd and
-//      the adb client use this class to transmit data between them.
-//   2. Functions to launch a subprocess on the adbd side.
-
-#ifndef SHELL_SERVICE_H_
-#define SHELL_SERVICE_H_
+#pragma once
 
 #include <stdint.h>
 
@@ -124,26 +115,3 @@
 
     DISALLOW_COPY_AND_ASSIGN(ShellProtocol);
 };
-
-#if !ADB_HOST
-
-enum class SubprocessType {
-    kPty,
-    kRaw,
-};
-
-enum class SubprocessProtocol {
-    kNone,
-    kShell,
-};
-
-// Forks and starts a new shell subprocess. If |name| is empty an interactive
-// shell is started, otherwise |name| is executed non-interactively.
-//
-// Returns an open FD connected to the subprocess or -1 on failure.
-int StartSubprocess(const char* name, const char* terminal_type,
-                    SubprocessType type, SubprocessProtocol protocol);
-
-#endif  // !ADB_HOST
-
-#endif  // SHELL_SERVICE_H_
diff --git a/adb/shell_service_protocol.cpp b/adb/shell_service_protocol.cpp
index 623629c..13b66ec 100644
--- a/adb/shell_service_protocol.cpp
+++ b/adb/shell_service_protocol.cpp
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-#include "shell_service.h"
+#include "shell_protocol.h"
 
 #include <string.h>
 
diff --git a/adb/shell_service_protocol_test.cpp b/adb/shell_service_protocol_test.cpp
index b0fa3ed..a10b5c0 100644
--- a/adb/shell_service_protocol_test.cpp
+++ b/adb/shell_service_protocol_test.cpp
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-#include "shell_service.h"
+#include "shell_protocol.h"
 
 #include <gtest/gtest.h>
 
diff --git a/adb/transport.cpp b/adb/transport.cpp
index 638940c..793c283 100644
--- a/adb/transport.cpp
+++ b/adb/transport.cpp
@@ -1157,7 +1157,7 @@
 }
 #endif  // ADB_HOST
 
-int register_socket_transport(int s, const char* serial, int port, int local,
+int register_socket_transport(unique_fd s, const char* serial, int port, int local,
                               atransport::ReconnectCallback reconnect) {
     atransport* t = new atransport(std::move(reconnect), kCsOffline);
 
@@ -1167,8 +1167,8 @@
         serial = buf;
     }
 
-    D("transport: %s init'ing for socket %d, on port %d", serial, s, port);
-    if (init_socket_transport(t, s, port, local) < 0) {
+    D("transport: %s init'ing for socket %d, on port %d", serial, s.get(), port);
+    if (init_socket_transport(t, std::move(s), port, local) < 0) {
         delete t;
         return -1;
     }
diff --git a/adb/transport.h b/adb/transport.h
index e9c9d37..1844ae8 100644
--- a/adb/transport.h
+++ b/adb/transport.h
@@ -364,7 +364,7 @@
 void connect_device(const std::string& address, std::string* response);
 
 /* cause new transports to be init'd and added to the list */
-int register_socket_transport(int s, const char* serial, int port, int local,
+int register_socket_transport(unique_fd s, const char* serial, int port, int local,
                               atransport::ReconnectCallback reconnect);
 
 // This should only be used for transports with connection_state == kCsNoPerm.
diff --git a/adb/transport_local.cpp b/adb/transport_local.cpp
index fa38238..9398ceb 100644
--- a/adb/transport_local.cpp
+++ b/adb/transport_local.cpp
@@ -122,12 +122,12 @@
         // invoked if the atransport* has already been setup. This eventually
         // calls atransport->SetConnection() with a newly created Connection*
         // that will in turn send the CNXN packet.
-        return init_socket_transport(t, fd.release(), port, 0) >= 0;
+        return init_socket_transport(t, std::move(fd), port, 0) >= 0;
     };
 
-    int ret = register_socket_transport(fd.release(), serial.c_str(), port, 0, std::move(reconnect));
+    int ret =
+            register_socket_transport(std::move(fd), serial.c_str(), port, 0, std::move(reconnect));
     if (ret < 0) {
-        adb_close(fd);
         if (ret == -EALREADY) {
             *response = android::base::StringPrintf("already connected to %s", serial.c_str());
         } else {
@@ -140,7 +140,7 @@
 
 
 int local_connect_arbitrary_ports(int console_port, int adb_port, std::string* error) {
-    int fd = -1;
+    unique_fd fd;
 
 #if ADB_HOST
     if (find_emulator_transport_by_adb_port(adb_port) != nullptr ||
@@ -150,23 +150,22 @@
 
     const char *host = getenv("ADBHOST");
     if (host) {
-        fd = network_connect(host, adb_port, SOCK_STREAM, 0, error);
+        fd.reset(network_connect(host, adb_port, SOCK_STREAM, 0, error));
     }
 #endif
     if (fd < 0) {
-        fd = network_loopback_client(adb_port, SOCK_STREAM, error);
+        fd.reset(network_loopback_client(adb_port, SOCK_STREAM, error));
     }
 
     if (fd >= 0) {
-        D("client: connected on remote on fd %d", fd);
-        close_on_exec(fd);
-        disable_tcp_nagle(fd);
+        D("client: connected on remote on fd %d", fd.get());
+        close_on_exec(fd.get());
+        disable_tcp_nagle(fd.get());
         std::string serial = getEmulatorSerialString(console_port);
-        if (register_socket_transport(fd, serial.c_str(), adb_port, 1,
+        if (register_socket_transport(std::move(fd), serial.c_str(), adb_port, 1,
                                       [](atransport*) { return false; }) == 0) {
             return 0;
         }
-        adb_close(fd);
     }
     return -1;
 }
@@ -243,34 +242,31 @@
 #else // ADB_HOST
 
 static void server_socket_thread(int port) {
-    int serverfd, fd;
+    unique_fd serverfd;
 
     adb_thread_setname("server socket");
     D("transport: server_socket_thread() starting");
-    serverfd = -1;
-    for(;;) {
-        if(serverfd == -1) {
-            std::string error;
-            serverfd = network_inaddr_any_server(port, SOCK_STREAM, &error);
-            if(serverfd < 0) {
-                D("server: cannot bind socket yet: %s", error.c_str());
-                std::this_thread::sleep_for(1s);
-                continue;
-            }
-            close_on_exec(serverfd);
+    while (serverfd == -1) {
+        std::string error;
+        serverfd.reset(network_inaddr_any_server(port, SOCK_STREAM, &error));
+        if (serverfd < 0) {
+            D("server: cannot bind socket yet: %s", error.c_str());
+            std::this_thread::sleep_for(1s);
+            continue;
         }
+        close_on_exec(serverfd.get());
+    }
 
+    while (true) {
         D("server: trying to get new connection from %d", port);
-        fd = adb_socket_accept(serverfd, nullptr, nullptr);
-        if(fd >= 0) {
-            D("server: new connection on fd %d", fd);
-            close_on_exec(fd);
-            disable_tcp_nagle(fd);
-            std::string serial = android::base::StringPrintf("host-%d", fd);
-            if (register_socket_transport(fd, serial.c_str(), port, 1,
-                                          [](atransport*) { return false; }) != 0) {
-                adb_close(fd);
-            }
+        unique_fd fd(adb_socket_accept(serverfd, nullptr, nullptr));
+        if (fd >= 0) {
+            D("server: new connection on fd %d", fd.get());
+            close_on_exec(fd.get());
+            disable_tcp_nagle(fd.get());
+            std::string serial = android::base::StringPrintf("host-%d", fd.get());
+            register_socket_transport(std::move(fd), serial.c_str(), port, 1,
+                                      [](atransport*) { return false; });
         }
     }
     D("transport: server_socket_thread() exiting");
@@ -331,7 +327,6 @@
     /* 'ok' reply from the adb QEMUD service. */
     static const char _ok_resp[] = "ok";
 
-    int fd;
     char tmp[256];
     char con_name[32];
 
@@ -342,7 +337,7 @@
     snprintf(con_name, sizeof(con_name), "pipe:qemud:adb:%d", port);
 
     /* Connect to the adb QEMUD service. */
-    fd = qemu_pipe_open(con_name);
+    unique_fd fd(qemu_pipe_open(con_name));
     if (fd < 0) {
         /* This could be an older version of the emulator, that doesn't
          * implement adb QEMUD service. Fall back to the old TCP way. */
@@ -351,31 +346,28 @@
         return;
     }
 
-    for(;;) {
+    while (true) {
         /*
          * Wait till the host creates a new connection.
          */
 
         /* Send the 'accept' request. */
-        if (WriteFdExactly(fd, _accept_req, strlen(_accept_req))) {
+        if (WriteFdExactly(fd.get(), _accept_req, strlen(_accept_req))) {
             /* Wait for the response. In the response we expect 'ok' on success,
              * or 'ko' on failure. */
-            if (!ReadFdExactly(fd, tmp, 2) || memcmp(tmp, _ok_resp, 2)) {
+            if (!ReadFdExactly(fd.get(), tmp, 2) || memcmp(tmp, _ok_resp, 2)) {
                 D("Accepting ADB host connection has failed.");
-                adb_close(fd);
             } else {
                 /* Host is connected. Register the transport, and start the
                  * exchange. */
-                std::string serial = android::base::StringPrintf("host-%d", fd);
-                if (register_socket_transport(fd, serial.c_str(), port, 1,
-                                              [](atransport*) { return false; }) != 0 ||
-                    !WriteFdExactly(fd, _start_req, strlen(_start_req))) {
-                    adb_close(fd);
-                }
+                std::string serial = android::base::StringPrintf("host-%d", fd.get());
+                WriteFdExactly(fd.get(), _start_req, strlen(_start_req));
+                register_socket_transport(std::move(fd), serial.c_str(), port, 1,
+                                          [](atransport*) { return false; });
             }
 
             /* Prepare for accepting of the next ADB host connection. */
-            fd = qemu_pipe_open(con_name);
+            fd.reset(qemu_pipe_open(con_name));
             if (fd < 0) {
                 D("adb service become unavailable.");
                 return;
@@ -476,10 +468,9 @@
 }
 #endif
 
-int init_socket_transport(atransport* t, int s, int adb_port, int local) {
+int init_socket_transport(atransport* t, unique_fd fd, int adb_port, int local) {
     int fail = 0;
 
-    unique_fd fd(s);
     t->type = kTransportLocal;
 
 #if ADB_HOST
diff --git a/fastboot/usb.h b/fastboot/usb.h
index 5b44468..7ca44c4 100644
--- a/fastboot/usb.h
+++ b/fastboot/usb.h
@@ -52,6 +52,14 @@
     char device_path[256];
 };
 
+class UsbTransport : public Transport {
+    // Resets the underlying transport.  Returns 0 on success.
+    // This effectively simulates unplugging and replugging
+  public:
+    virtual int Reset() = 0;
+};
+
 typedef int (*ifc_match_func)(usb_ifc_info *ifc);
 
-Transport* usb_open(ifc_match_func callback);
+// 0 is non blocking
+UsbTransport* usb_open(ifc_match_func callback, uint32_t timeout_ms = 0);
diff --git a/fastboot/usb_linux.cpp b/fastboot/usb_linux.cpp
index 386dd30..9b779dd 100644
--- a/fastboot/usb_linux.cpp
+++ b/fastboot/usb_linux.cpp
@@ -52,7 +52,7 @@
 
 using namespace std::chrono_literals;
 
-#define MAX_RETRIES 5
+#define MAX_RETRIES 2
 
 /* Timeout in seconds for usb_wait_for_disconnect.
  * It doesn't usually take long for a device to disconnect (almost always
@@ -91,18 +91,21 @@
     unsigned char ep_out;
 };
 
-class LinuxUsbTransport : public Transport {
+class LinuxUsbTransport : public UsbTransport {
   public:
-    explicit LinuxUsbTransport(std::unique_ptr<usb_handle> handle) : handle_(std::move(handle)) {}
+    explicit LinuxUsbTransport(std::unique_ptr<usb_handle> handle, uint32_t ms_timeout = 0)
+        : handle_(std::move(handle)), ms_timeout_(ms_timeout) {}
     ~LinuxUsbTransport() override = default;
 
     ssize_t Read(void* data, size_t len) override;
     ssize_t Write(const void* data, size_t len) override;
     int Close() override;
+    int Reset() override;
     int WaitForDisconnect() override;
 
   private:
     std::unique_ptr<usb_handle> handle_;
+    const uint32_t ms_timeout_;
 
     DISALLOW_COPY_AND_ASSIGN(LinuxUsbTransport);
 };
@@ -402,7 +405,7 @@
         bulk.ep = handle_->ep_out;
         bulk.len = xfer;
         bulk.data = data;
-        bulk.timeout = 0;
+        bulk.timeout = ms_timeout_;
 
         n = ioctl(handle_->desc, USBDEVFS_BULK, &bulk);
         if(n != xfer) {
@@ -436,7 +439,7 @@
         bulk.ep = handle_->ep_in;
         bulk.len = xfer;
         bulk.data = data;
-        bulk.timeout = 0;
+        bulk.timeout = ms_timeout_;
         retry = 0;
 
         do {
@@ -447,7 +450,7 @@
             if (n < 0) {
                 DBG1("ERROR: n = %d, errno = %d (%s)\n",n, errno, strerror(errno));
                 if (++retry > MAX_RETRIES) return -1;
-                std::this_thread::sleep_for(1s);
+                std::this_thread::sleep_for(100ms);
             }
         } while (n < 0);
 
@@ -477,10 +480,19 @@
     return 0;
 }
 
-Transport* usb_open(ifc_match_func callback)
-{
+int LinuxUsbTransport::Reset() {
+    int ret = 0;
+    // We reset the USB connection
+    if ((ret = ioctl(handle_->desc, USBDEVFS_RESET, 0))) {
+        return ret;
+    }
+
+    return 0;
+}
+
+UsbTransport* usb_open(ifc_match_func callback, uint32_t timeout_ms) {
     std::unique_ptr<usb_handle> handle = find_usb_device("/sys/bus/usb/devices", callback);
-    return handle ? new LinuxUsbTransport(std::move(handle)) : nullptr;
+    return handle ? new LinuxUsbTransport(std::move(handle), timeout_ms) : nullptr;
 }
 
 /* Wait for the system to notice the device is gone, so that a subsequent
diff --git a/fastboot/usb_osx.cpp b/fastboot/usb_osx.cpp
index e95b049..4d48f6e 100644
--- a/fastboot/usb_osx.cpp
+++ b/fastboot/usb_osx.cpp
@@ -65,17 +65,21 @@
     unsigned int zero_mask;
 };
 
-class OsxUsbTransport : public Transport {
+class OsxUsbTransport : public UsbTransport {
   public:
-    OsxUsbTransport(std::unique_ptr<usb_handle> handle) : handle_(std::move(handle)) {}
+    // A timeout of 0 is blocking
+    OsxUsbTransport(std::unique_ptr<usb_handle> handle, uint32_t ms_timeout = 0)
+        : handle_(std::move(handle)), ms_timeout_(ms_timeout) {}
     ~OsxUsbTransport() override = default;
 
     ssize_t Read(void* data, size_t len) override;
     ssize_t Write(const void* data, size_t len) override;
     int Close() override;
+    int Reset() override;
 
   private:
     std::unique_ptr<usb_handle> handle_;
+    const uint32_t ms_timeout_;
 
     DISALLOW_COPY_AND_ASSIGN(OsxUsbTransport);
 };
@@ -456,7 +460,7 @@
  * Definitions of this file's public functions.
  */
 
-Transport* usb_open(ifc_match_func callback) {
+UsbTransport* usb_open(ifc_match_func callback, uint32_t timeout_ms) {
     std::unique_ptr<usb_handle> handle;
 
     if (init_usb(callback, &handle) < 0) {
@@ -464,7 +468,7 @@
         return nullptr;
     }
 
-    return new OsxUsbTransport(std::move(handle));
+    return new OsxUsbTransport(std::move(handle), timeout_ms);
 }
 
 int OsxUsbTransport::Close() {
@@ -472,6 +476,19 @@
     return 0;
 }
 
+/*
+  TODO: this SHOULD be easy to do with ResetDevice() from IOUSBDeviceInterface.
+  However to perform operations that manipulate the state of the device, you must
+  claim ownership of the device with USBDeviceOpenSeize(). However, this operation
+  always fails with kIOReturnExclusiveAccess.
+  It seems that the kext com.apple.driver.usb.AppleUSBHostCompositeDevice
+  always loads and claims ownership of the device and refuses to give it up.
+*/
+int OsxUsbTransport::Reset() {
+    ERR("USB reset is currently unsupported on osx\n");
+    return -1;
+}
+
 ssize_t OsxUsbTransport::Read(void* data, size_t len) {
     IOReturn result;
     UInt32 numBytes = len;
@@ -494,7 +511,14 @@
         return -1;
     }
 
-    result = (*handle_->interface)->ReadPipe(handle_->interface, handle_->bulkIn, data, &numBytes);
+    if (!ms_timeout_) {
+        result = (*handle_->interface)
+                         ->ReadPipe(handle_->interface, handle_->bulkIn, data, &numBytes);
+    } else {
+        result = (*handle_->interface)
+                         ->ReadPipeTO(handle_->interface, handle_->bulkIn, data, &numBytes,
+                                      ms_timeout_, ms_timeout_);
+    }
 
     if (result == 0) {
         return (int) numBytes;
@@ -541,8 +565,16 @@
         int lenToSend = lenRemaining > maxLenToSend
             ? maxLenToSend : lenRemaining;
 
-        result = (*handle_->interface)->WritePipe(
-                handle_->interface, handle_->bulkOut, (void *)data, lenToSend);
+        if (!ms_timeout_) {  // blocking
+            result = (*handle_->interface)
+                             ->WritePipe(handle_->interface, handle_->bulkOut, (void*)data,
+                                         lenToSend);
+        } else {
+            result = (*handle_->interface)
+                             ->WritePipeTO(handle_->interface, handle_->bulkOut, (void*)data,
+                                           lenToSend, ms_timeout_, ms_timeout_);
+        }
+
         if (result != 0) break;
 
         lenRemaining -= lenToSend;
diff --git a/fastboot/usb_windows.cpp b/fastboot/usb_windows.cpp
index 0e5fba1..8c60a71 100644
--- a/fastboot/usb_windows.cpp
+++ b/fastboot/usb_windows.cpp
@@ -66,7 +66,7 @@
     std::string interface_name;
 };
 
-class WindowsUsbTransport : public Transport {
+class WindowsUsbTransport : public UsbTransport {
   public:
     WindowsUsbTransport(std::unique_ptr<usb_handle> handle) : handle_(std::move(handle)) {}
     ~WindowsUsbTransport() override = default;
@@ -74,6 +74,7 @@
     ssize_t Read(void* data, size_t len) override;
     ssize_t Write(const void* data, size_t len) override;
     int Close() override;
+    int Reset() override;
 
   private:
     std::unique_ptr<usb_handle> handle_;
@@ -261,6 +262,12 @@
     return 0;
 }
 
+int WindowsUsbTransport::Reset() {
+    DBG("usb_reset currently unsupported\n\n");
+    // TODO, this is a bit complicated since it is using ADB
+    return -1;
+}
+
 int recognized_device(usb_handle* handle, ifc_match_func callback) {
     struct usb_ifc_info info;
     USB_DEVICE_DESCRIPTOR device_desc;
@@ -366,8 +373,7 @@
     return handle;
 }
 
-Transport* usb_open(ifc_match_func callback)
-{
+UsbTransport* usb_open(ifc_match_func callback, uint32_t) {
     std::unique_ptr<usb_handle> handle = find_usb_device(callback);
     return handle ? new WindowsUsbTransport(std::move(handle)) : nullptr;
 }
diff --git a/init/Android.bp b/init/Android.bp
index c02b8d1..660d586 100644
--- a/init/Android.bp
+++ b/init/Android.bp
@@ -108,6 +108,7 @@
         "import_parser.cpp",
         "init.cpp",
         "keychords.cpp",
+        "modalias_handler.cpp",
         "parser.cpp",
         "persistent_properties.cpp",
         "persistent_properties.proto",
diff --git a/init/modalias_handler.cpp b/init/modalias_handler.cpp
new file mode 100644
index 0000000..1734a7e
--- /dev/null
+++ b/init/modalias_handler.cpp
@@ -0,0 +1,163 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "modalias_handler.h"
+
+#include <fnmatch.h>
+#include <sys/syscall.h>
+
+#include <algorithm>
+#include <functional>
+#include <string>
+#include <vector>
+
+#include <android-base/chrono_utils.h>
+#include <android-base/logging.h>
+#include <android-base/unique_fd.h>
+
+#include "parser.h"
+
+namespace android {
+namespace init {
+
+Result<Success> ModaliasHandler::ParseDepCallback(std::vector<std::string>&& args) {
+    std::vector<std::string> deps;
+
+    // Set first item as our modules path
+    std::string::size_type pos = args[0].find(':');
+    if (pos != std::string::npos) {
+        deps.emplace_back(args[0].substr(0, pos));
+    } else {
+        return Error() << "dependency lines must start with name followed by ':'";
+    }
+
+    // Remaining items are dependencies of our module
+    for (auto arg = args.begin() + 1; arg != args.end(); ++arg) {
+        deps.push_back(*arg);
+    }
+
+    // Key is striped module name to match names in alias file
+    std::size_t start = args[0].find_last_of("/");
+    std::size_t end = args[0].find(".ko:");
+    if ((end - start) <= 1) return Error() << "malformed dependency line";
+    auto mod_name = args[0].substr(start + 1, (end - start) - 1);
+    // module names can have '-', but their file names will have '_'
+    std::replace(mod_name.begin(), mod_name.end(), '-', '_');
+    this->module_deps_[mod_name] = deps;
+
+    return Success();
+}
+
+Result<Success> ModaliasHandler::ParseAliasCallback(std::vector<std::string>&& args) {
+    auto it = args.begin();
+    const std::string& type = *it++;
+
+    if (type != "alias") {
+        return Error() << "we only handle alias lines, got: " << type;
+    }
+
+    if (args.size() != 3) {
+        return Error() << "alias lines must have 3 entries";
+    }
+
+    std::string& alias = *it++;
+    std::string& module_name = *it++;
+    this->module_aliases_.emplace_back(alias, module_name);
+
+    return Success();
+}
+
+ModaliasHandler::ModaliasHandler() {
+    using namespace std::placeholders;
+
+    static const std::string base_paths[] = {
+            "/vendor/lib/modules/",
+            "/lib/modules/",
+            "/odm/lib/modules/",
+    };
+
+    Parser alias_parser;
+    auto alias_callback = std::bind(&ModaliasHandler::ParseAliasCallback, this, _1);
+    alias_parser.AddSingleLineParser("alias", alias_callback);
+    for (const auto& base_path : base_paths) alias_parser.ParseConfig(base_path + "modules.alias");
+
+    Parser dep_parser;
+    auto dep_callback = std::bind(&ModaliasHandler::ParseDepCallback, this, _1);
+    dep_parser.AddSingleLineParser("", dep_callback);
+    for (const auto& base_path : base_paths) dep_parser.ParseConfig(base_path + "modules.dep");
+}
+
+Result<Success> ModaliasHandler::Insmod(const std::string& path_name, const std::string& args) {
+    base::unique_fd fd(
+            TEMP_FAILURE_RETRY(open(path_name.c_str(), O_RDONLY | O_NOFOLLOW | O_CLOEXEC)));
+    if (fd == -1) return ErrnoError() << "Could not open module '" << path_name << "'";
+
+    int ret = syscall(__NR_finit_module, fd.get(), args.c_str(), 0);
+    if (ret != 0) {
+        if (errno == EEXIST) {
+            // Module already loaded
+            return Success();
+        }
+        return ErrnoError() << "Failed to insmod '" << path_name << "' with args '" << args << "'";
+    }
+
+    LOG(INFO) << "Loaded kernel module " << path_name;
+    return Success();
+}
+
+Result<Success> ModaliasHandler::InsmodWithDeps(const std::string& module_name,
+                                                const std::string& args) {
+    if (module_name.empty()) {
+        return Error() << "Need valid module name";
+    }
+
+    auto it = module_deps_.find(module_name);
+    if (it == module_deps_.end()) {
+        return Error() << "Module '" << module_name << "' not in dependency file";
+    }
+    auto& dependencies = it->second;
+
+    // load module dependencies in reverse order
+    for (auto dep = dependencies.rbegin(); dep != dependencies.rend() - 1; ++dep) {
+        if (auto result = Insmod(*dep, ""); !result) return result;
+    }
+
+    // load target module itself with args
+    return Insmod(dependencies[0], args);
+}
+
+void ModaliasHandler::HandleModaliasEvent(const Uevent& uevent) {
+    if (uevent.modalias.empty()) return;
+
+    for (const auto& [alias, module] : module_aliases_) {
+        if (fnmatch(alias.c_str(), uevent.modalias.c_str(), 0) != 0) continue;  // Keep looking
+
+        LOG(DEBUG) << "Loading kernel module '" << module << "' for alias '" << uevent.modalias
+                   << "'";
+
+        if (auto result = InsmodWithDeps(module, ""); !result) {
+            LOG(ERROR) << "Cannot load module: " << result.error();
+            // try another one since there may be another match
+            continue;
+        }
+
+        // loading was successful
+        return;
+    }
+}
+
+}  // namespace init
+}  // namespace android
diff --git a/init/modalias_handler.h b/init/modalias_handler.h
new file mode 100644
index 0000000..e79da32
--- /dev/null
+++ b/init/modalias_handler.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include "result.h"
+#include "uevent.h"
+
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+namespace android {
+namespace init {
+
+class ModaliasHandler {
+  public:
+    ModaliasHandler();
+    ~ModaliasHandler(){};
+
+    void HandleModaliasEvent(const Uevent& uevent);
+
+  private:
+    Result<Success> InsmodWithDeps(const std::string& module_name, const std::string& args);
+    Result<Success> Insmod(const std::string& path_name, const std::string& args);
+
+    Result<Success> ParseDepCallback(std::vector<std::string>&& args);
+    Result<Success> ParseAliasCallback(std::vector<std::string>&& args);
+
+    std::vector<std::pair<std::string, std::string>> module_aliases_;
+    std::unordered_map<std::string, std::vector<std::string>> module_deps_;
+};
+
+}  // namespace init
+}  // namespace android
diff --git a/init/uevent.h b/init/uevent.h
index c4fd945..dc35fd9 100644
--- a/init/uevent.h
+++ b/init/uevent.h
@@ -29,6 +29,7 @@
     std::string firmware;
     std::string partition_name;
     std::string device_name;
+    std::string modalias;
     int partition_num;
     int major;
     int minor;
diff --git a/init/uevent_listener.cpp b/init/uevent_listener.cpp
index 24b14c4..8cf2128 100644
--- a/init/uevent_listener.cpp
+++ b/init/uevent_listener.cpp
@@ -39,6 +39,7 @@
     uevent->firmware.clear();
     uevent->partition_name.clear();
     uevent->device_name.clear();
+    uevent->modalias.clear();
     // currently ignoring SEQNUM
     while (*msg) {
         if (!strncmp(msg, "ACTION=", 7)) {
@@ -68,6 +69,9 @@
         } else if (!strncmp(msg, "DEVNAME=", 8)) {
             msg += 8;
             uevent->device_name = msg;
+        } else if (!strncmp(msg, "MODALIAS=", 9)) {
+            msg += 9;
+            uevent->modalias = msg;
         }
 
         // advance to after the next \0
diff --git a/init/ueventd.cpp b/init/ueventd.cpp
index cd45a3f..e9d829b 100644
--- a/init/ueventd.cpp
+++ b/init/ueventd.cpp
@@ -36,6 +36,7 @@
 
 #include "devices.h"
 #include "firmware_handler.h"
+#include "modalias_handler.h"
 #include "selinux.h"
 #include "uevent_listener.h"
 #include "ueventd_parser.h"
@@ -106,9 +107,11 @@
 
 class ColdBoot {
   public:
-    ColdBoot(UeventListener& uevent_listener, DeviceHandler& device_handler)
+    ColdBoot(UeventListener& uevent_listener, DeviceHandler& device_handler,
+             ModaliasHandler& modalias_handler)
         : uevent_listener_(uevent_listener),
           device_handler_(device_handler),
+          modalias_handler_(modalias_handler),
           num_handler_subprocesses_(std::thread::hardware_concurrency() ?: 4) {}
 
     void Run();
@@ -122,6 +125,7 @@
 
     UeventListener& uevent_listener_;
     DeviceHandler& device_handler_;
+    ModaliasHandler& modalias_handler_;
 
     unsigned int num_handler_subprocesses_;
     std::vector<Uevent> uevent_queue_;
@@ -133,6 +137,7 @@
     for (unsigned int i = process_num; i < uevent_queue_.size(); i += total_processes) {
         auto& uevent = uevent_queue_[i];
         device_handler_.HandleDeviceEvent(uevent);
+        modalias_handler_.HandleModaliasEvent(uevent);
     }
     _exit(EXIT_SUCCESS);
 }
@@ -230,6 +235,7 @@
     SelabelInitialize();
 
     DeviceHandler device_handler;
+    ModaliasHandler modalias_handler;
     UeventListener uevent_listener;
 
     {
@@ -251,7 +257,7 @@
     }
 
     if (access(COLDBOOT_DONE, F_OK) != 0) {
-        ColdBoot cold_boot(uevent_listener, device_handler);
+        ColdBoot cold_boot(uevent_listener, device_handler, modalias_handler);
         cold_boot.Run();
     }
 
@@ -262,8 +268,9 @@
     while (waitpid(-1, nullptr, WNOHANG) > 0) {
     }
 
-    uevent_listener.Poll([&device_handler](const Uevent& uevent) {
+    uevent_listener.Poll([&device_handler, &modalias_handler](const Uevent& uevent) {
         HandleFirmwareEvent(uevent);
+        modalias_handler.HandleModaliasEvent(uevent);
         device_handler.HandleDeviceEvent(uevent);
         return ListenerAction::kContinue;
     });
diff --git a/liblog/include/log/log_main.h b/liblog/include/log/log_main.h
index 1314330..e7b1728 100644
--- a/liblog/include/log/log_main.h
+++ b/liblog/include/log/log_main.h
@@ -40,19 +40,6 @@
 #endif
 #endif
 
-/*
- * Use __VA_ARGS__ if running a static analyzer,
- * to avoid warnings of unused variables in __VA_ARGS__.
- * __FAKE_USE_VA_ARGS is undefined at link time,
- * so don't link with __clang_analyzer__ defined.
- */
-#ifdef __clang_analyzer__
-extern void __fake_use_va_args(int, ...);
-#define __FAKE_USE_VA_ARGS(...) __fake_use_va_args(0, ##__VA_ARGS__)
-#else
-#define __FAKE_USE_VA_ARGS(...) ((void)(0))
-#endif
-
 /* --------------------------------------------------------------------- */
 
 /*
@@ -66,6 +53,19 @@
 #pragma clang diagnostic ignored "-Wgnu-zero-variadic-macro-arguments"
 #endif
 
+/*
+ * Use __VA_ARGS__ if running a static analyzer,
+ * to avoid warnings of unused variables in __VA_ARGS__.
+ * __FAKE_USE_VA_ARGS is undefined at link time,
+ * so don't link with __clang_analyzer__ defined.
+ */
+#ifdef __clang_analyzer__
+extern void __fake_use_va_args(int, ...);
+#define __FAKE_USE_VA_ARGS(...) __fake_use_va_args(0, ##__VA_ARGS__)
+#else
+#define __FAKE_USE_VA_ARGS(...) ((void)(0))
+#endif
+
 #ifndef __predict_false
 #define __predict_false(exp) __builtin_expect((exp) != 0, 0)
 #endif
diff --git a/libunwindstack/DexFile.cpp b/libunwindstack/DexFile.cpp
index b18b0ce..3d982f6 100644
--- a/libunwindstack/DexFile.cpp
+++ b/libunwindstack/DexFile.cpp
@@ -68,17 +68,51 @@
     return false;  // The DEX offset is not within the bytecode of this dex file.
   }
 
-  for (uint32_t i = 0; i < dex_file_->NumClassDefs(); ++i) {
-    const art::DexFile::ClassDef& class_def = dex_file_->GetClassDef(i);
+  if (dex_file_->IsCompactDexFile()) {
+    // The data section of compact dex files might be shared.
+    // Check the subrange unique to this compact dex.
+    const auto& cdex_header = dex_file_->AsCompactDexFile()->GetHeader();
+    uint32_t begin = cdex_header.data_off_ + cdex_header.OwnedDataBegin();
+    uint32_t end = cdex_header.data_off_ + cdex_header.OwnedDataEnd();
+    if (dex_offset < begin || dex_offset >= end) {
+      return false;  // The DEX offset is not within the bytecode of this dex file.
+    }
+  }
+
+  // The method data is cached in a std::map indexed by method end offset and
+  // contains the start offset and the method member index.
+  // Only cache the method data as it is searched. Do not read the entire
+  // set of method data into the cache at once.
+  // This is done because many unwinds only find a single frame with dex file
+  // info, so reading the entire method data is wasteful. However, still cache
+  // the data so that anything doing multiple unwinds will have this data
+  // cached for future use.
+
+  // First look in the method cache.
+  auto entry = method_cache_.upper_bound(dex_offset);
+  if (entry != method_cache_.end() && dex_offset >= entry->second.first) {
+    *method_name = dex_file_->PrettyMethod(entry->second.second, false);
+    *method_offset = dex_offset - entry->second.first;
+    return true;
+  }
+
+  // Check the methods we haven't cached.
+  for (; class_def_index_ < dex_file_->NumClassDefs(); class_def_index_++) {
+    const art::DexFile::ClassDef& class_def = dex_file_->GetClassDef(class_def_index_);
     const uint8_t* class_data = dex_file_->GetClassData(class_def);
     if (class_data == nullptr) {
       continue;
     }
-    for (art::ClassDataItemIterator it(*dex_file_.get(), class_data); it.HasNext(); it.Next()) {
-      if (!it.IsAtMethod()) {
+
+    if (class_it_.get() == nullptr || !class_it_->HasNext()) {
+      class_it_.reset(new art::ClassDataItemIterator(*dex_file_.get(), class_data));
+    }
+
+    for (; class_it_->HasNext(); class_it_->Next()) {
+      if (!class_it_->IsAtMethod()) {
         continue;
       }
-      const art::DexFile::CodeItem* code_item = it.GetMethodCodeItem();
+      const art::DexFile::CodeItem* code_item = class_it_->GetMethodCodeItem();
       if (code_item == nullptr) {
         continue;
       }
@@ -87,11 +121,15 @@
         continue;
       }
 
-      uint64_t offset = reinterpret_cast<const uint8_t*>(code.Insns()) - dex_file_->Begin();
-      size_t size = code.InsnsSizeInCodeUnits() * sizeof(uint16_t);
-      if (offset <= dex_offset && dex_offset < offset + size) {
-        *method_name = dex_file_->PrettyMethod(it.GetMemberIndex(), false);
+      uint32_t offset = reinterpret_cast<const uint8_t*>(code.Insns()) - dex_file_->Begin();
+      uint32_t offset_end = offset + code.InsnsSizeInCodeUnits() * sizeof(uint16_t);
+      uint32_t member_index = class_it_->GetMemberIndex();
+      method_cache_[offset_end] = std::make_pair(offset, member_index);
+      if (offset <= dex_offset && dex_offset < offset_end) {
+        *method_name = dex_file_->PrettyMethod(member_index, false);
         *method_offset = dex_offset - offset;
+        // Move past this element.
+        class_it_->Next();
         return true;
       }
     }
diff --git a/libunwindstack/DexFile.h b/libunwindstack/DexFile.h
index 3ce2f1e..508692d 100644
--- a/libunwindstack/DexFile.h
+++ b/libunwindstack/DexFile.h
@@ -19,8 +19,10 @@
 
 #include <stdint.h>
 
+#include <map>
 #include <memory>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include <dex/dex_file-inl.h>
@@ -37,7 +39,13 @@
   static DexFile* Create(uint64_t dex_file_offset_in_memory, Memory* memory, MapInfo* info);
 
  protected:
+  void Init();
+
   std::unique_ptr<const art::DexFile> dex_file_;
+  std::map<uint32_t, std::pair<uint64_t, uint32_t>> method_cache_;  // dex offset to method index.
+
+  uint32_t class_def_index_ = 0;
+  std::unique_ptr<art::ClassDataItemIterator> class_it_;
 };
 
 class DexFileFromFile : public DexFile {
diff --git a/libunwindstack/tests/DexFileTest.cpp b/libunwindstack/tests/DexFileTest.cpp
index 0b02c5b..4dd8cb0 100644
--- a/libunwindstack/tests/DexFileTest.cpp
+++ b/libunwindstack/tests/DexFileTest.cpp
@@ -206,15 +206,42 @@
 
   std::string method;
   uint64_t method_offset;
-  dex_file->GetMethodInformation(0x102, &method, &method_offset);
+  ASSERT_TRUE(dex_file->GetMethodInformation(0x102, &method, &method_offset));
   EXPECT_EQ("Main.<init>", method);
   EXPECT_EQ(2U, method_offset);
 
-  method = "not_in_a_method";
-  method_offset = 0x123;
-  dex_file->GetMethodInformation(0x100000, &method, &method_offset);
-  EXPECT_EQ("not_in_a_method", method);
-  EXPECT_EQ(0x123U, method_offset);
+  ASSERT_TRUE(dex_file->GetMethodInformation(0x118, &method, &method_offset));
+  EXPECT_EQ("Main.main", method);
+  EXPECT_EQ(0U, method_offset);
+
+  // Make sure that any data that is cached is still retrievable.
+  ASSERT_TRUE(dex_file->GetMethodInformation(0x104, &method, &method_offset));
+  EXPECT_EQ("Main.<init>", method);
+  EXPECT_EQ(4U, method_offset);
+
+  ASSERT_TRUE(dex_file->GetMethodInformation(0x119, &method, &method_offset));
+  EXPECT_EQ("Main.main", method);
+  EXPECT_EQ(1U, method_offset);
+}
+
+TEST(DexFileTest, get_method_empty) {
+  MemoryFake memory;
+  memory.SetMemory(0x4000, kDexData, sizeof(kDexData));
+  MapInfo info(0x100, 0x10000, 0x200, 0x5, "");
+  std::unique_ptr<DexFile> dex_file(DexFile::Create(0x4000, &memory, &info));
+  ASSERT_TRUE(dex_file != nullptr);
+
+  std::string method;
+  uint64_t method_offset;
+  EXPECT_FALSE(dex_file->GetMethodInformation(0x100000, &method, &method_offset));
+
+  EXPECT_FALSE(dex_file->GetMethodInformation(0x98, &method, &method_offset));
+
+  // Make sure that once the whole dex file has been cached, no problems occur.
+  EXPECT_FALSE(dex_file->GetMethodInformation(0x98, &method, &method_offset));
+
+  // Choose a value that is in the cached map, but not in a valid method.
+  EXPECT_FALSE(dex_file->GetMethodInformation(0x110, &method, &method_offset));
 }
 
 }  // namespace unwindstack
diff --git a/shell_and_utilities/README.md b/shell_and_utilities/README.md
index e310e6b..d8cf867 100644
--- a/shell_and_utilities/README.md
+++ b/shell_and_utilities/README.md
@@ -193,14 +193,12 @@
 Android Q
 ---------
 
-BSD: fsck\_msdos newfs\_msdos
+BSD: grep fsck\_msdos newfs\_msdos
 
 bzip2: bzcat bzip2 bunzip2
 
 one-true-awk: awk
 
-PCRE: egrep fgrep grep
-
 toolbox: getevent getprop
 
 toybox: acpi base64 basename blockdev cal cat chcon chgrp chmod chown
diff --git a/toolbox/Android.bp b/toolbox/Android.bp
index fc51705..e75e4af 100644
--- a/toolbox/Android.bp
+++ b/toolbox/Android.bp
@@ -60,3 +60,20 @@
     defaults: ["toolbox_defaults"],
     srcs: ["r.c"],
 }
+
+// We build BSD grep separately (but see http://b/111849261).
+cc_binary {
+    name: "grep",
+    defaults: ["toolbox_defaults"],
+    srcs: [
+        "upstream-netbsd/usr.bin/grep/fastgrep.c",
+        "upstream-netbsd/usr.bin/grep/file.c",
+        "upstream-netbsd/usr.bin/grep/grep.c",
+        "upstream-netbsd/usr.bin/grep/queue.c",
+        "upstream-netbsd/usr.bin/grep/util.c",
+    ],
+
+    sanitize: {
+        integer_overflow: false,
+    },
+}
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/fastgrep.c b/toolbox/upstream-netbsd/usr.bin/grep/fastgrep.c
new file mode 100644
index 0000000..2fcd864
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/fastgrep.c
@@ -0,0 +1,336 @@
+/*	$OpenBSD: util.c,v 1.36 2007/10/02 17:59:18 otto Exp $	*/
+/*	$FreeBSD: head/usr.bin/grep/fastgrep.c 211496 2010-08-19 09:28:59Z des $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * XXX: This file is a speed up for grep to cover the defects of the
+ * regex library.  These optimizations should practically be implemented
+ * there keeping this code clean.  This is a future TODO, but for the
+ * meantime, we need to use this workaround.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: fastgrep.c,v 1.5 2011/04/18 03:27:40 joerg Exp $");
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "grep.h"
+
+static inline int	grep_cmp(const unsigned char *, const unsigned char *, size_t);
+static inline void	grep_revstr(unsigned char *, int);
+
+void
+fgrepcomp(fastgrep_t *fg, const char *pat)
+{
+	unsigned int i;
+
+	/* Initialize. */
+	fg->len = strlen(pat);
+	fg->bol = false;
+	fg->eol = false;
+	fg->reversed = false;
+
+	fg->pattern = (unsigned char *)grep_strdup(pat);
+
+	/* Preprocess pattern. */
+	for (i = 0; i <= UCHAR_MAX; i++)
+		fg->qsBc[i] = fg->len;
+	for (i = 1; i < fg->len; i++)
+		fg->qsBc[fg->pattern[i]] = fg->len - i;
+}
+
+/*
+ * Returns: -1 on failure, 0 on success
+ */
+int
+fastcomp(fastgrep_t *fg, const char *pat)
+{
+	unsigned int i;
+	int firstHalfDot = -1;
+	int firstLastHalfDot = -1;
+	int hasDot = 0;
+	int lastHalfDot = 0;
+	int shiftPatternLen;
+
+	/* Initialize. */
+	fg->len = strlen(pat);
+	fg->bol = false;
+	fg->eol = false;
+	fg->reversed = false;
+	fg->word = wflag;
+
+	/* Remove end-of-line character ('$'). */
+	if (fg->len > 0 && pat[fg->len - 1] == '$') {
+		fg->eol = true;
+		fg->len--;
+	}
+
+	/* Remove beginning-of-line character ('^'). */
+	if (pat[0] == '^') {
+		fg->bol = true;
+		fg->len--;
+		pat++;
+	}
+
+	if (fg->len >= 14 &&
+	    memcmp(pat, "[[:<:]]", 7) == 0 &&
+	    memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) {
+		fg->len -= 14;
+		pat += 7;
+		/* Word boundary is handled separately in util.c */
+		fg->word = true;
+	}
+
+	/*
+	 * pat has been adjusted earlier to not include '^', '$' or
+	 * the word match character classes at the beginning and ending
+	 * of the string respectively.
+	 */
+	fg->pattern = grep_malloc(fg->len + 1);
+	memcpy(fg->pattern, pat, fg->len);
+	fg->pattern[fg->len] = '\0';
+
+	/* Look for ways to cheat...er...avoid the full regex engine. */
+	for (i = 0; i < fg->len; i++) {
+		/* Can still cheat? */
+		if (fg->pattern[i] == '.') {
+			hasDot = i;
+			if (i < fg->len / 2) {
+				if (firstHalfDot < 0)
+					/* Closest dot to the beginning */
+					firstHalfDot = i;
+			} else {
+				/* Closest dot to the end of the pattern. */
+				lastHalfDot = i;
+				if (firstLastHalfDot < 0)
+					firstLastHalfDot = i;
+			}
+		} else {
+			/* Free memory and let others know this is empty. */
+			free(fg->pattern);
+			fg->pattern = NULL;
+			return (-1);
+		}
+	}
+
+	/*
+	 * Determine if a reverse search would be faster based on the placement
+	 * of the dots.
+	 */
+	if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) &&
+	    ((lastHalfDot) && ((firstHalfDot < 0) ||
+	    ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) &&
+	    !oflag && !color) {
+		fg->reversed = true;
+		hasDot = fg->len - (firstHalfDot < 0 ?
+		    firstLastHalfDot : firstHalfDot) - 1;
+		grep_revstr(fg->pattern, fg->len);
+	}
+
+	/*
+	 * Normal Quick Search would require a shift based on the position the
+	 * next character after the comparison is within the pattern.  With
+	 * wildcards, the position of the last dot effects the maximum shift
+	 * distance.
+	 * The closer to the end the wild card is the slower the search.  A
+	 * reverse version of this algorithm would be useful for wildcards near
+	 * the end of the string.
+	 *
+	 * Examples:
+	 * Pattern	Max shift
+	 * -------	---------
+	 * this		5
+	 * .his		4
+	 * t.is		3
+	 * th.s		2
+	 * thi.		1
+	 */
+
+	/* Adjust the shift based on location of the last dot ('.'). */
+	shiftPatternLen = fg->len - hasDot;
+
+	/* Preprocess pattern. */
+	for (i = 0; i <= (signed)UCHAR_MAX; i++)
+		fg->qsBc[i] = shiftPatternLen;
+	for (i = hasDot + 1; i < fg->len; i++) {
+		fg->qsBc[fg->pattern[i]] = fg->len - i;
+	}
+
+	/*
+	 * Put pattern back to normal after pre-processing to allow for easy
+	 * comparisons later.
+	 */
+	if (fg->reversed)
+		grep_revstr(fg->pattern, fg->len);
+
+	return (0);
+}
+
+int
+grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch)
+{
+	unsigned int j;
+	int ret = REG_NOMATCH;
+
+	if (pmatch->rm_so == (ssize_t)len)
+		return (ret);
+
+	if (fg->bol && pmatch->rm_so != 0) {
+		pmatch->rm_so = len;
+		pmatch->rm_eo = len;
+		return (ret);
+	}
+
+	/* No point in going farther if we do not have enough data. */
+	if (len < fg->len)
+		return (ret);
+
+	/* Only try once at the beginning or ending of the line. */
+	if (fg->bol || fg->eol) {
+		/* Simple text comparison. */
+		/* Verify data is >= pattern length before searching on it. */
+		if (len >= fg->len) {
+			/* Determine where in data to start search at. */
+			j = fg->eol ? len - fg->len : 0;
+			if (!((fg->bol && fg->eol) && (len != fg->len)))
+				if (grep_cmp(fg->pattern, data + j,
+				    fg->len) == -1) {
+					pmatch->rm_so = j;
+					pmatch->rm_eo = j + fg->len;
+						ret = 0;
+				}
+		}
+	} else if (fg->reversed) {
+		/* Quick Search algorithm. */
+		j = len;
+		do {
+			if (grep_cmp(fg->pattern, data + j - fg->len,
+				fg->len) == -1) {
+				pmatch->rm_so = j - fg->len;
+				pmatch->rm_eo = j;
+				ret = 0;
+				break;
+			}
+			/* Shift if within bounds, otherwise, we are done. */
+			if (j == fg->len)
+				break;
+			j -= fg->qsBc[data[j - fg->len - 1]];
+		} while (j >= fg->len);
+	} else {
+		/* Quick Search algorithm. */
+		j = pmatch->rm_so;
+		do {
+			if (grep_cmp(fg->pattern, data + j, fg->len) == -1) {
+				pmatch->rm_so = j;
+				pmatch->rm_eo = j + fg->len;
+				ret = 0;
+				break;
+			}
+
+			/* Shift if within bounds, otherwise, we are done. */
+			if (j + fg->len == len)
+				break;
+			else
+				j += fg->qsBc[data[j + fg->len]];
+		} while (j <= (len - fg->len));
+	}
+
+	return (ret);
+}
+
+/*
+ * Returns:	i >= 0 on failure (position that it failed)
+ *		-1 on success
+ */
+static inline int
+grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len)
+{
+	size_t size;
+	wchar_t *wdata, *wpat;
+	unsigned int i;
+
+	if (iflag) {
+		if ((size = mbstowcs(NULL, (const char *)data, 0)) ==
+		    ((size_t) - 1))
+			return (-1);
+
+		wdata = grep_malloc(size * sizeof(wint_t));
+
+		if (mbstowcs(wdata, (const char *)data, size) ==
+		    ((size_t) - 1))
+			return (-1);
+
+		if ((size = mbstowcs(NULL, (const char *)pat, 0)) ==
+		    ((size_t) - 1))
+			return (-1);
+
+		wpat = grep_malloc(size * sizeof(wint_t));
+
+		if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1))
+			return (-1);
+		for (i = 0; i < len; i++) {
+			if ((towlower(wpat[i]) == towlower(wdata[i])) ||
+			    ((grepbehave != GREP_FIXED) && wpat[i] == L'.'))
+				continue;
+			free(wpat);
+			free(wdata);
+				return (i);
+		}
+	} else {
+		for (i = 0; i < len; i++) {
+			if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) &&
+			    pat[i] == '.'))
+				continue;
+			return (i);
+		}
+	}
+	return (-1);
+}
+
+static inline void
+grep_revstr(unsigned char *str, int len)
+{
+	int i;
+	char c;
+
+	for (i = 0; i < len / 2; i++) {
+		c = str[i];
+		str[i] = str[len - i - 1];
+		str[len - i - 1] = c;
+	}
+}
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/file.c b/toolbox/upstream-netbsd/usr.bin/grep/file.c
new file mode 100644
index 0000000..cf4a0fa
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/file.c
@@ -0,0 +1,271 @@
+/*	$NetBSD: file.c,v 1.7 2011/04/18 22:46:48 joerg Exp $	*/
+/*	$FreeBSD: head/usr.bin/grep/file.c 211496 2010-08-19 09:28:59Z des $	*/
+/*	$OpenBSD: file.c,v 1.11 2010/07/02 20:48:48 nicm Exp $	*/
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2010 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2010 Dimitry Andric <dimitry@andric.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: file.c,v 1.7 2011/04/18 22:46:48 joerg Exp $");
+
+#include <sys/param.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#ifndef __ANDROID__
+#include <bzlib.h>
+#endif
+#include <err.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+#ifndef __ANDROID__
+#include <zlib.h>
+#endif
+
+#include "grep.h"
+
+#define	MAXBUFSIZ	(32 * 1024)
+#define	LNBUFBUMP	80
+
+#ifndef __ANDROID__
+static gzFile gzbufdesc;
+static BZFILE* bzbufdesc;
+#endif
+
+static unsigned char buffer[MAXBUFSIZ];
+static unsigned char *bufpos;
+static size_t bufrem;
+
+static unsigned char *lnbuf;
+static size_t lnbuflen;
+
+static inline int
+grep_refill(struct file *f)
+{
+	ssize_t nr;
+#ifndef __ANDROID__
+	int bzerr;
+#endif
+
+	bufpos = buffer;
+	bufrem = 0;
+
+#ifndef __ANDROID__
+	if (filebehave == FILE_GZIP)
+		nr = gzread(gzbufdesc, buffer, MAXBUFSIZ);
+	else if (filebehave == FILE_BZIP && bzbufdesc != NULL) {
+		nr = BZ2_bzRead(&bzerr, bzbufdesc, buffer, MAXBUFSIZ);
+		switch (bzerr) {
+		case BZ_OK:
+		case BZ_STREAM_END:
+			/* No problem, nr will be okay */
+			break;
+		case BZ_DATA_ERROR_MAGIC:
+			/*
+			 * As opposed to gzread(), which simply returns the
+			 * plain file data, if it is not in the correct
+			 * compressed format, BZ2_bzRead() instead aborts.
+			 *
+			 * So, just restart at the beginning of the file again,
+			 * and use plain reads from now on.
+			 */
+			BZ2_bzReadClose(&bzerr, bzbufdesc);
+			bzbufdesc = NULL;
+			if (lseek(f->fd, 0, SEEK_SET) == -1)
+				return (-1);
+			nr = read(f->fd, buffer, MAXBUFSIZ);
+			break;
+		default:
+			/* Make sure we exit with an error */
+			nr = -1;
+		}
+	} else
+#endif
+		nr = read(f->fd, buffer, MAXBUFSIZ);
+
+	if (nr < 0)
+		return (-1);
+
+	bufrem = nr;
+	return (0);
+}
+
+static inline int
+grep_lnbufgrow(size_t newlen)
+{
+
+	if (lnbuflen < newlen) {
+		lnbuf = grep_realloc(lnbuf, newlen);
+		lnbuflen = newlen;
+	}
+
+	return (0);
+}
+
+char *
+grep_fgetln(struct file *f, size_t *lenp)
+{
+	unsigned char *p;
+	char *ret;
+	size_t len;
+	size_t off;
+	ptrdiff_t diff;
+
+	/* Fill the buffer, if necessary */
+	if (bufrem == 0 && grep_refill(f) != 0)
+		goto error;
+
+	if (bufrem == 0) {
+		/* Return zero length to indicate EOF */
+		*lenp = 0;
+		return ((char *)bufpos);
+	}
+
+	/* Look for a newline in the remaining part of the buffer */
+	if ((p = memchr(bufpos, line_sep, bufrem)) != NULL) {
+		++p; /* advance over newline */
+		ret = (char *)bufpos;
+		len = p - bufpos;
+		bufrem -= len;
+		bufpos = p;
+		*lenp = len;
+		return (ret);
+	}
+
+	/* We have to copy the current buffered data to the line buffer */
+	for (len = bufrem, off = 0; ; len += bufrem) {
+		/* Make sure there is room for more data */
+		if (grep_lnbufgrow(len + LNBUFBUMP))
+			goto error;
+		memcpy(lnbuf + off, bufpos, len - off);
+		off = len;
+		if (grep_refill(f) != 0)
+			goto error;
+		if (bufrem == 0)
+			/* EOF: return partial line */
+			break;
+		if ((p = memchr(bufpos, line_sep, bufrem)) == NULL)
+			continue;
+		/* got it: finish up the line (like code above) */
+		++p;
+		diff = p - bufpos;
+		len += diff;
+		if (grep_lnbufgrow(len))
+		    goto error;
+		memcpy(lnbuf + off, bufpos, diff);
+		bufrem -= diff;
+		bufpos = p;
+		break;
+	}
+	*lenp = len;
+	return ((char *)lnbuf);
+
+error:
+	*lenp = 0;
+	return (NULL);
+}
+
+static inline struct file *
+grep_file_init(struct file *f)
+{
+
+#ifndef __ANDROID__
+	if (filebehave == FILE_GZIP &&
+	    (gzbufdesc = gzdopen(f->fd, "r")) == NULL)
+		goto error;
+
+	if (filebehave == FILE_BZIP &&
+	    (bzbufdesc = BZ2_bzdopen(f->fd, "r")) == NULL)
+		goto error;
+#endif
+
+	/* Fill read buffer, also catches errors early */
+	if (grep_refill(f) != 0)
+		goto error;
+
+	/* Check for binary stuff, if necessary */
+	if (!nulldataflag && binbehave != BINFILE_TEXT &&
+	    memchr(bufpos, '\0', bufrem) != NULL)
+		f->binary = true;
+
+	return (f);
+error:
+	close(f->fd);
+	free(f);
+	return (NULL);
+}
+
+/*
+ * Opens a file for processing.
+ */
+struct file *
+grep_open(const char *path)
+{
+	struct file *f;
+
+	f = grep_malloc(sizeof *f);
+	memset(f, 0, sizeof *f);
+	if (path == NULL) {
+		/* Processing stdin implies --line-buffered. */
+		lbflag = true;
+		f->fd = STDIN_FILENO;
+	} else if ((f->fd = open(path, O_RDONLY)) == -1) {
+		free(f);
+		return (NULL);
+	}
+
+	return (grep_file_init(f));
+}
+
+/*
+ * Closes a file.
+ */
+void
+grep_close(struct file *f)
+{
+
+	close(f->fd);
+
+	/* Reset read buffer and line buffer */
+	bufpos = buffer;
+	bufrem = 0;
+
+	free(lnbuf);
+	lnbuf = NULL;
+	lnbuflen = 0;
+}
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/grep.c b/toolbox/upstream-netbsd/usr.bin/grep/grep.c
new file mode 100644
index 0000000..1ea6ed3
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/grep.c
@@ -0,0 +1,707 @@
+/*	$NetBSD: grep.c,v 1.12 2014/07/11 16:30:45 christos Exp $	*/
+/* 	$FreeBSD: head/usr.bin/grep/grep.c 211519 2010-08-19 22:55:17Z delphij $	*/
+/*	$OpenBSD: grep.c,v 1.42 2010/07/02 22:18:03 tedu Exp $	*/
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: grep.c,v 1.12 2014/07/11 16:30:45 christos Exp $");
+
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <ctype.h>
+#include <err.h>
+#include <errno.h>
+#include <getopt.h>
+#include <limits.h>
+#include <libgen.h>
+#include <locale.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "grep.h"
+
+#ifndef WITHOUT_NLS
+#include <nl_types.h>
+nl_catd	 catalog;
+#endif
+
+/*
+ * Default messags to use when NLS is disabled or no catalogue
+ * is found.
+ */
+const char	*errstr[] = {
+	"",
+/* 1*/	"(standard input)",
+/* 2*/	"cannot read bzip2 compressed file",
+/* 3*/	"unknown %s option",
+/* 4*/	"usage: %s [-abcDEFGHhIiJLlmnOoPqRSsUVvwxZz] [-A num] [-B num] [-C[num]]\n",
+/* 5*/	"\t[-e pattern] [-f file] [--binary-files=value] [--color=when]\n",
+/* 6*/	"\t[--context[=num]] [--directories=action] [--label] [--line-buffered]\n",
+/* 7*/	"\t[pattern] [file ...]\n",
+/* 8*/	"Binary file %s matches\n",
+/* 9*/	"%s (BSD grep) %s\n",
+};
+
+/* Flags passed to regcomp() and regexec() */
+int		 cflags = 0;
+int		 eflags = REG_STARTEND;
+
+/* Searching patterns */
+unsigned int	 patterns, pattern_sz;
+char		**pattern;
+regex_t		*r_pattern;
+fastgrep_t	*fg_pattern;
+
+/* Filename exclusion/inclusion patterns */
+unsigned int	 fpatterns, fpattern_sz;
+unsigned int	 dpatterns, dpattern_sz;
+struct epat	*dpattern, *fpattern;
+
+/* For regex errors  */
+char	 re_error[RE_ERROR_BUF + 1];
+
+/* Command-line flags */
+unsigned long long Aflag;	/* -A x: print x lines trailing each match */
+unsigned long long Bflag;	/* -B x: print x lines leading each match */
+bool	 Hflag;		/* -H: always print file name */
+bool	 Lflag;		/* -L: only show names of files with no matches */
+bool	 bflag;		/* -b: show block numbers for each match */
+bool	 cflag;		/* -c: only show a count of matching lines */
+bool	 hflag;		/* -h: don't print filename headers */
+bool	 iflag;		/* -i: ignore case */
+bool	 lflag;		/* -l: only show names of files with matches */
+bool	 mflag;		/* -m x: stop reading the files after x matches */
+unsigned long long mcount;	/* count for -m */
+bool	 nflag;		/* -n: show line numbers in front of matching lines */
+bool	 oflag;		/* -o: print only matching part */
+bool	 qflag;		/* -q: quiet mode (don't output anything) */
+bool	 sflag;		/* -s: silent mode (ignore errors) */
+bool	 vflag;		/* -v: only show non-matching lines */
+bool	 wflag;		/* -w: pattern must start and end on word boundaries */
+bool	 xflag;		/* -x: pattern must match entire line */
+bool	 lbflag;	/* --line-buffered */
+bool	 nullflag;	/* --null */
+bool	 nulldataflag;	/* --null-data */
+unsigned char line_sep = '\n';	/* 0 for --null-data */
+char	*label;		/* --label */
+const char *color;	/* --color */
+int	 grepbehave = GREP_BASIC;	/* -EFGP: type of the regex */
+int	 binbehave = BINFILE_BIN;	/* -aIU: handling of binary files */
+int	 filebehave = FILE_STDIO;	/* -JZ: normal, gzip or bzip2 file */
+int	 devbehave = DEV_READ;		/* -D: handling of devices */
+int	 dirbehave = DIR_READ;		/* -dRr: handling of directories */
+int	 linkbehave = LINK_READ;	/* -OpS: handling of symlinks */
+
+bool	 dexclude, dinclude;	/* --exclude-dir and --include-dir */
+bool	 fexclude, finclude;	/* --exclude and --include */
+
+enum {
+	BIN_OPT = CHAR_MAX + 1,
+	COLOR_OPT,
+	DECOMPRESS_OPT,
+	HELP_OPT,
+	MMAP_OPT,
+	LINEBUF_OPT,
+	LABEL_OPT,
+	R_EXCLUDE_OPT,
+	R_INCLUDE_OPT,
+	R_DEXCLUDE_OPT,
+	R_DINCLUDE_OPT
+};
+
+static inline const char	*init_color(const char *);
+
+/* Housekeeping */
+int	 tail;		/* lines left to print */
+bool	 notfound;	/* file not found */
+
+extern char	*__progname;
+
+/*
+ * Prints usage information and returns 2.
+ */
+__dead static void
+usage(void)
+{
+	fprintf(stderr, getstr(4), __progname);
+	fprintf(stderr, "%s", getstr(5));
+	fprintf(stderr, "%s", getstr(6));
+	fprintf(stderr, "%s", getstr(7));
+	exit(2);
+}
+
+static const char optstr[] =
+    "0123456789A:B:C:D:EFGHIJLOPSRUVZabcd:e:f:hilm:nopqrsuvwxyz";
+
+struct option long_options[] =
+{
+	{"binary-files",	required_argument,	NULL, BIN_OPT},
+	{"decompress",          no_argument,            NULL, DECOMPRESS_OPT},
+	{"help",		no_argument,		NULL, HELP_OPT},
+	{"mmap",		no_argument,		NULL, MMAP_OPT},
+	{"line-buffered",	no_argument,		NULL, LINEBUF_OPT},
+	{"label",		required_argument,	NULL, LABEL_OPT},
+	{"color",		optional_argument,	NULL, COLOR_OPT},
+	{"colour",		optional_argument,	NULL, COLOR_OPT},
+	{"exclude",		required_argument,	NULL, R_EXCLUDE_OPT},
+	{"include",		required_argument,	NULL, R_INCLUDE_OPT},
+	{"exclude-dir",		required_argument,	NULL, R_DEXCLUDE_OPT},
+	{"include-dir",		required_argument,	NULL, R_DINCLUDE_OPT},
+	{"after-context",	required_argument,	NULL, 'A'},
+	{"text",		no_argument,		NULL, 'a'},
+	{"before-context",	required_argument,	NULL, 'B'},
+	{"byte-offset",		no_argument,		NULL, 'b'},
+	{"context",		optional_argument,	NULL, 'C'},
+	{"count",		no_argument,		NULL, 'c'},
+	{"devices",		required_argument,	NULL, 'D'},
+        {"directories",		required_argument,	NULL, 'd'},
+	{"extended-regexp",	no_argument,		NULL, 'E'},
+	{"regexp",		required_argument,	NULL, 'e'},
+	{"fixed-strings",	no_argument,		NULL, 'F'},
+	{"file",		required_argument,	NULL, 'f'},
+	{"basic-regexp",	no_argument,		NULL, 'G'},
+	{"no-filename",		no_argument,		NULL, 'h'},
+	{"with-filename",	no_argument,		NULL, 'H'},
+	{"ignore-case",		no_argument,		NULL, 'i'},
+	{"bz2decompress",	no_argument,		NULL, 'J'},
+	{"files-with-matches",	no_argument,		NULL, 'l'},
+	{"files-without-match", no_argument,            NULL, 'L'},
+	{"max-count",		required_argument,	NULL, 'm'},
+	{"line-number",		no_argument,		NULL, 'n'},
+	{"only-matching",	no_argument,		NULL, 'o'},
+	{"quiet",		no_argument,		NULL, 'q'},
+	{"silent",		no_argument,		NULL, 'q'},
+	{"recursive",		no_argument,		NULL, 'r'},
+	{"no-messages",		no_argument,		NULL, 's'},
+	{"binary",		no_argument,		NULL, 'U'},
+	{"unix-byte-offsets",	no_argument,		NULL, 'u'},
+	{"invert-match",	no_argument,		NULL, 'v'},
+	{"version",		no_argument,		NULL, 'V'},
+	{"word-regexp",		no_argument,		NULL, 'w'},
+	{"line-regexp",		no_argument,		NULL, 'x'},
+	{"null",		no_argument,		NULL, 'Z'},
+	{"null-data",		no_argument,		NULL, 'z'},
+	{NULL,			no_argument,		NULL, 0}
+};
+
+/*
+ * Adds a searching pattern to the internal array.
+ */
+static void
+add_pattern(char *pat, size_t len)
+{
+
+	/* TODO: Check for empty patterns and shortcut */
+
+	/* Increase size if necessary */
+	if (patterns == pattern_sz) {
+		pattern_sz *= 2;
+		pattern = grep_realloc(pattern, ++pattern_sz *
+		    sizeof(*pattern));
+	}
+	if (len > 0 && pat[len - 1] == '\n')
+		--len;
+	/* pat may not be NUL-terminated */
+	pattern[patterns] = grep_malloc(len + 1);
+	memcpy(pattern[patterns], pat, len);
+	pattern[patterns][len] = '\0';
+	++patterns;
+}
+
+/*
+ * Adds a file include/exclude pattern to the internal array.
+ */
+static void
+add_fpattern(const char *pat, int mode)
+{
+
+	/* Increase size if necessary */
+	if (fpatterns == fpattern_sz) {
+		fpattern_sz *= 2;
+		fpattern = grep_realloc(fpattern, ++fpattern_sz *
+		    sizeof(struct epat));
+	}
+	fpattern[fpatterns].pat = grep_strdup(pat);
+	fpattern[fpatterns].mode = mode;
+	++fpatterns;
+}
+
+/*
+ * Adds a directory include/exclude pattern to the internal array.
+ */
+static void
+add_dpattern(const char *pat, int mode)
+{
+
+	/* Increase size if necessary */
+	if (dpatterns == dpattern_sz) {
+		dpattern_sz *= 2;
+		dpattern = grep_realloc(dpattern, ++dpattern_sz *
+		    sizeof(struct epat));
+	}
+	dpattern[dpatterns].pat = grep_strdup(pat);
+	dpattern[dpatterns].mode = mode;
+	++dpatterns;
+}
+
+/*
+ * Reads searching patterns from a file and adds them with add_pattern().
+ */
+static void
+read_patterns(const char *fn)
+{
+	FILE *f;
+	char *line;
+	size_t len;
+	ssize_t rlen;
+
+	if ((f = fopen(fn, "r")) == NULL)
+		err(2, "%s", fn);
+	line = NULL;
+	len = 0;
+	while ((rlen = getline(&line, &len, f)) != -1)
+		add_pattern(line, *line == '\n' ? 0 : (size_t)rlen);
+	free(line);
+	if (ferror(f))
+		err(2, "%s", fn);
+	fclose(f);
+}
+
+static inline const char *
+init_color(const char *d)
+{
+	char *c;
+
+	c = getenv("GREP_COLOR");
+	return (c != NULL ? c : d);
+}
+
+int
+main(int argc, char *argv[])
+{
+	char **aargv, **eargv, *eopts;
+	char *ep;
+	unsigned long long l;
+	unsigned int aargc, eargc, i, j;
+	int c, lastc, needpattern, newarg, prevoptind;
+
+	setlocale(LC_ALL, "");
+
+#ifndef WITHOUT_NLS
+	catalog = catopen("grep", NL_CAT_LOCALE);
+#endif
+
+	/* Check what is the program name of the binary.  In this
+	   way we can have all the funcionalities in one binary
+	   without the need of scripting and using ugly hacks. */
+	switch (__progname[0]) {
+	case 'e':
+		grepbehave = GREP_EXTENDED;
+		break;
+	case 'f':
+		grepbehave = GREP_FIXED;
+		break;
+	case 'g':
+		grepbehave = GREP_BASIC;
+		break;
+	case 'z':
+		filebehave = FILE_GZIP;
+		switch(__progname[1]) {
+		case 'e':
+			grepbehave = GREP_EXTENDED;
+			break;
+		case 'f':
+			grepbehave = GREP_FIXED;
+			break;
+		case 'g':
+			grepbehave = GREP_BASIC;
+			break;
+		}
+		break;
+	}
+
+	lastc = '\0';
+	newarg = 1;
+	prevoptind = 1;
+	needpattern = 1;
+
+	eopts = getenv("GREP_OPTIONS");
+
+	/* support for extra arguments in GREP_OPTIONS */
+	eargc = 0;
+	if (eopts != NULL) {
+		char *str;
+
+		/* make an estimation of how many extra arguments we have */
+		for (j = 0; j < strlen(eopts); j++)
+			if (eopts[j] == ' ')
+				eargc++;
+
+		eargv = (char **)grep_malloc(sizeof(char *) * (eargc + 1));
+
+		eargc = 0;
+		/* parse extra arguments */
+		while ((str = strsep(&eopts, " ")) != NULL)
+			eargv[eargc++] = grep_strdup(str);
+
+		aargv = (char **)grep_calloc(eargc + argc + 1,
+		    sizeof(char *));
+
+		aargv[0] = argv[0];
+		for (i = 0; i < eargc; i++)
+			aargv[i + 1] = eargv[i];
+		for (j = 1; j < (unsigned int)argc; j++, i++)
+			aargv[i + 1] = argv[j];
+
+		aargc = eargc + argc;
+	} else {
+		aargv = argv;
+		aargc = argc;
+	}
+
+	while (((c = getopt_long(aargc, aargv, optstr, long_options, NULL)) !=
+	    -1)) {
+		switch (c) {
+		case '0': case '1': case '2': case '3': case '4':
+		case '5': case '6': case '7': case '8': case '9':
+			if (newarg || !isdigit(lastc))
+				Aflag = 0;
+			else if (Aflag > LLONG_MAX / 10) {
+				errno = ERANGE;
+				err(2, NULL);
+			}
+			Aflag = Bflag = (Aflag * 10) + (c - '0');
+			break;
+		case 'C':
+			if (optarg == NULL) {
+				Aflag = Bflag = 2;
+				break;
+			}
+			/* FALLTHROUGH */
+		case 'A':
+			/* FALLTHROUGH */
+		case 'B':
+			errno = 0;
+			l = strtoull(optarg, &ep, 10);
+			if (((errno == ERANGE) && (l == ULLONG_MAX)) ||
+			    ((errno == EINVAL) && (l == 0)))
+				err(2, NULL);
+			else if (ep[0] != '\0') {
+				errno = EINVAL;
+				err(2, NULL);
+			}
+			if (c == 'A')
+				Aflag = l;
+			else if (c == 'B')
+				Bflag = l;
+			else
+				Aflag = Bflag = l;
+			break;
+		case 'a':
+			binbehave = BINFILE_TEXT;
+			break;
+		case 'b':
+			bflag = true;
+			break;
+		case 'c':
+			cflag = true;
+			break;
+		case 'D':
+			if (strcasecmp(optarg, "skip") == 0)
+				devbehave = DEV_SKIP;
+			else if (strcasecmp(optarg, "read") == 0)
+				devbehave = DEV_READ;
+			else
+				errx(2, getstr(3), "--devices");
+			break;
+		case 'd':
+			if (strcasecmp("recurse", optarg) == 0) {
+				Hflag = true;
+				dirbehave = DIR_RECURSE;
+			} else if (strcasecmp("skip", optarg) == 0)
+				dirbehave = DIR_SKIP;
+			else if (strcasecmp("read", optarg) == 0)
+				dirbehave = DIR_READ;
+			else
+				errx(2, getstr(3), "--directories");
+			break;
+		case 'E':
+			grepbehave = GREP_EXTENDED;
+			break;
+		case 'e':
+			add_pattern(optarg, strlen(optarg));
+			needpattern = 0;
+			break;
+		case 'F':
+			grepbehave = GREP_FIXED;
+			break;
+		case 'f':
+			read_patterns(optarg);
+			needpattern = 0;
+			break;
+		case 'G':
+			grepbehave = GREP_BASIC;
+			break;
+		case 'H':
+			Hflag = true;
+			break;
+		case 'h':
+			Hflag = false;
+			hflag = true;
+			break;
+		case 'I':
+			binbehave = BINFILE_SKIP;
+			break;
+		case 'i':
+		case 'y':
+			iflag =  true;
+			cflags |= REG_ICASE;
+			break;
+		case 'J':
+			filebehave = FILE_BZIP;
+			break;
+		case 'L':
+			lflag = false;
+			Lflag = true;
+			break;
+		case 'l':
+			Lflag = false;
+			lflag = true;
+			break;
+		case 'm':
+			mflag = true;
+			errno = 0;
+			mcount = strtoull(optarg, &ep, 10);
+			if (((errno == ERANGE) && (mcount == ULLONG_MAX)) ||
+			    ((errno == EINVAL) && (mcount == 0)))
+				err(2, NULL);
+			else if (ep[0] != '\0') {
+				errno = EINVAL;
+				err(2, NULL);
+			}
+			break;
+		case 'n':
+			nflag = true;
+			break;
+		case 'O':
+			linkbehave = LINK_EXPLICIT;
+			break;
+		case 'o':
+			oflag = true;
+			break;
+		case 'p':
+			linkbehave = LINK_SKIP;
+			break;
+		case 'q':
+			qflag = true;
+			break;
+		case 'S':
+			linkbehave = LINK_READ;
+			break;
+		case 'R':
+		case 'r':
+			dirbehave = DIR_RECURSE;
+			Hflag = true;
+			break;
+		case 's':
+			sflag = true;
+			break;
+		case 'U':
+			binbehave = BINFILE_BIN;
+			break;
+		case 'u':
+		case MMAP_OPT:
+			/* noop, compatibility */
+			break;
+		case 'V':
+			printf(getstr(9), __progname, VERSION);
+			exit(0);
+		case 'v':
+			vflag = true;
+			break;
+		case 'w':
+			wflag = true;
+			break;
+		case 'x':
+			xflag = true;
+			break;
+		case 'Z':
+			nullflag = true;
+			break;
+		case 'z':
+			nulldataflag = true;
+			line_sep = '\0';
+			break;
+		case BIN_OPT:
+			if (strcasecmp("binary", optarg) == 0)
+				binbehave = BINFILE_BIN;
+			else if (strcasecmp("without-match", optarg) == 0)
+				binbehave = BINFILE_SKIP;
+			else if (strcasecmp("text", optarg) == 0)
+				binbehave = BINFILE_TEXT;
+			else
+				errx(2, getstr(3), "--binary-files");
+			break;
+		case COLOR_OPT:
+			color = NULL;
+			if (optarg == NULL || strcasecmp("auto", optarg) == 0 ||
+			    strcasecmp("tty", optarg) == 0 ||
+			    strcasecmp("if-tty", optarg) == 0) {
+				char *term;
+
+				term = getenv("TERM");
+				if (isatty(STDOUT_FILENO) && term != NULL &&
+				    strcasecmp(term, "dumb") != 0)
+					color = init_color("01;31");
+			} else if (strcasecmp("always", optarg) == 0 ||
+			    strcasecmp("yes", optarg) == 0 ||
+			    strcasecmp("force", optarg) == 0) {
+				color = init_color("01;31");
+			} else if (strcasecmp("never", optarg) != 0 &&
+			    strcasecmp("none", optarg) != 0 &&
+			    strcasecmp("no", optarg) != 0)
+				errx(2, getstr(3), "--color");
+			break;
+		case DECOMPRESS_OPT:
+			filebehave = FILE_GZIP;
+			break;
+		case LABEL_OPT:
+			label = optarg;
+			break;
+		case LINEBUF_OPT:
+			lbflag = true;
+			break;
+		case R_INCLUDE_OPT:
+			finclude = true;
+			add_fpattern(optarg, INCL_PAT);
+			break;
+		case R_EXCLUDE_OPT:
+			fexclude = true;
+			add_fpattern(optarg, EXCL_PAT);
+			break;
+		case R_DINCLUDE_OPT:
+			dinclude = true;
+			add_dpattern(optarg, INCL_PAT);
+			break;
+		case R_DEXCLUDE_OPT:
+			dexclude = true;
+			add_dpattern(optarg, EXCL_PAT);
+			break;
+		case HELP_OPT:
+		default:
+			usage();
+		}
+		lastc = c;
+		newarg = optind != prevoptind;
+		prevoptind = optind;
+	}
+	aargc -= optind;
+	aargv += optind;
+
+	/* Fail if we don't have any pattern */
+	if (aargc == 0 && needpattern)
+		usage();
+
+	/* Process patterns from command line */
+	if (aargc != 0 && needpattern) {
+		add_pattern(*aargv, strlen(*aargv));
+		--aargc;
+		++aargv;
+	}
+
+	switch (grepbehave) {
+	case GREP_FIXED:
+	case GREP_BASIC:
+		break;
+	case GREP_EXTENDED:
+		cflags |= REG_EXTENDED;
+		break;
+	default:
+		/* NOTREACHED */
+		usage();
+	}
+
+	fg_pattern = grep_calloc(patterns, sizeof(*fg_pattern));
+	r_pattern = grep_calloc(patterns, sizeof(*r_pattern));
+/*
+ * XXX: fgrepcomp() and fastcomp() are workarounds for regexec() performance.
+ * Optimizations should be done there.
+ */
+		/* Check if cheating is allowed (always is for fgrep). */
+	if (grepbehave == GREP_FIXED) {
+		for (i = 0; i < patterns; ++i)
+			fgrepcomp(&fg_pattern[i], pattern[i]);
+	} else {
+		for (i = 0; i < patterns; ++i) {
+			if (fastcomp(&fg_pattern[i], pattern[i])) {
+				/* Fall back to full regex library */
+				c = regcomp(&r_pattern[i], pattern[i], cflags);
+				if (c != 0) {
+					regerror(c, &r_pattern[i], re_error,
+					    RE_ERROR_BUF);
+					errx(2, "%s", re_error);
+				}
+			}
+		}
+	}
+
+	if (lbflag)
+		setlinebuf(stdout);
+
+	if ((aargc == 0 || aargc == 1) && !Hflag)
+		hflag = true;
+
+	if (aargc == 0)
+		exit(!procfile("-"));
+
+	if (dirbehave == DIR_RECURSE)
+		c = grep_tree(aargv);
+	else
+		for (c = 0; aargc--; ++aargv) {
+			if ((finclude || fexclude) && !file_matching(*aargv))
+				continue;
+			c+= procfile(*aargv);
+		}
+
+#ifndef WITHOUT_NLS
+	catclose(catalog);
+#endif
+
+	/* Find out the correct return value according to the
+	   results and the command line option. */
+	exit(c ? (notfound ? (qflag ? 0 : 2) : 0) : (notfound ? 2 : 1));
+}
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/grep.h b/toolbox/upstream-netbsd/usr.bin/grep/grep.h
new file mode 100644
index 0000000..fa2a3e3
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/grep.h
@@ -0,0 +1,162 @@
+/*	$NetBSD: grep.h,v 1.8 2012/05/06 22:27:00 joerg Exp $	*/
+/*	$OpenBSD: grep.h,v 1.15 2010/04/05 03:03:55 tedu Exp $	*/
+/*	$FreeBSD: head/usr.bin/grep/grep.h 211496 2010-08-19 09:28:59Z des $	*/
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (c) 2008-2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef __ANDROID__
+#include <bzlib.h>
+#endif
+#include <limits.h>
+#include <regex.h>
+#include <stdbool.h>
+#include <stdio.h>
+#ifndef __ANDROID__
+#include <zlib.h>
+#endif
+
+#ifdef WITHOUT_NLS
+#define getstr(n)	 errstr[n]
+#else
+#include <nl_types.h>
+
+extern nl_catd		 catalog;
+#define getstr(n)	 catgets(catalog, 1, n, errstr[n])
+#endif
+
+extern const char		*errstr[];
+
+#define VERSION		"2.5.1-FreeBSD"
+
+#define GREP_FIXED	0
+#define GREP_BASIC	1
+#define GREP_EXTENDED	2
+
+#define BINFILE_BIN	0
+#define BINFILE_SKIP	1
+#define BINFILE_TEXT	2
+
+#define FILE_STDIO	0
+#define FILE_GZIP	1
+#define FILE_BZIP	2
+
+#define DIR_READ	0
+#define DIR_SKIP	1
+#define DIR_RECURSE	2
+
+#define DEV_READ	0
+#define DEV_SKIP	1
+
+#define LINK_READ	0
+#define LINK_EXPLICIT	1
+#define LINK_SKIP	2
+
+#define EXCL_PAT	0
+#define INCL_PAT	1
+
+#define MAX_LINE_MATCHES	32
+
+struct file {
+	int		 fd;
+	bool		 binary;
+};
+
+struct str {
+	off_t		 off;
+	size_t		 len;
+	char		*dat;
+	char		*file;
+	int		 line_no;
+};
+
+struct epat {
+	char		*pat;
+	int		 mode;
+};
+
+typedef struct {
+	size_t		 len;
+	unsigned char	*pattern;
+	int		 qsBc[UCHAR_MAX + 1];
+	/* flags */
+	bool		 bol;
+	bool		 eol;
+	bool		 reversed;
+	bool		 word;
+} fastgrep_t;
+
+/* Flags passed to regcomp() and regexec() */
+extern int	 cflags, eflags;
+
+/* Command line flags */
+extern bool	 Eflag, Fflag, Gflag, Hflag, Lflag,
+		 bflag, cflag, hflag, iflag, lflag, mflag, nflag, oflag,
+		 qflag, sflag, vflag, wflag, xflag;
+extern bool	 dexclude, dinclude, fexclude, finclude, lbflag, nullflag, nulldataflag;
+extern unsigned char line_sep;
+extern unsigned long long Aflag, Bflag, mcount;
+extern char	*label;
+extern const char *color;
+extern int	 binbehave, devbehave, dirbehave, filebehave, grepbehave, linkbehave;
+
+extern bool	 notfound;
+extern int	 tail;
+extern unsigned int dpatterns, fpatterns, patterns;
+extern char    **pattern;
+extern struct epat *dpattern, *fpattern;
+extern regex_t	*er_pattern, *r_pattern;
+extern fastgrep_t *fg_pattern;
+
+/* For regex errors  */
+#define RE_ERROR_BUF	512
+extern char	 re_error[RE_ERROR_BUF + 1];	/* Seems big enough */
+
+/* util.c */
+bool	 file_matching(const char *fname);
+int	 procfile(const char *fn);
+int	 grep_tree(char **argv);
+void	*grep_malloc(size_t size);
+void	*grep_calloc(size_t nmemb, size_t size);
+void	*grep_realloc(void *ptr, size_t size);
+char	*grep_strdup(const char *str);
+void	 printline(struct str *line, int sep, regmatch_t *matches, int m);
+
+/* queue.c */
+void	 enqueue(struct str *x);
+void	 printqueue(void);
+void	 clearqueue(void);
+
+/* file.c */
+void		 grep_close(struct file *f);
+struct file	*grep_open(const char *path);
+char		*grep_fgetln(struct file *f, size_t *len);
+
+/* fastgrep.c */
+int		 fastcomp(fastgrep_t *, const char *);
+void		 fgrepcomp(fastgrep_t *, const char *);
+int		 grep_search(fastgrep_t *, const unsigned char *, size_t, regmatch_t *);
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/queue.c b/toolbox/upstream-netbsd/usr.bin/grep/queue.c
new file mode 100644
index 0000000..e3c6be1
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/queue.c
@@ -0,0 +1,116 @@
+/*	$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $	*/
+/*	$FreeBSD: head/usr.bin/grep/queue.c 211496 2010-08-19 09:28:59Z des $	*/
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * A really poor man's queue.  It does only what it has to and gets out of
+ * Dodge.  It is used in place of <sys/queue.h> to get a better performance.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $");
+
+#include <sys/param.h>
+#include <sys/queue.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "grep.h"
+
+struct qentry {
+	STAILQ_ENTRY(qentry)	list;
+	struct str	 	data;
+};
+
+static STAILQ_HEAD(, qentry)	queue = STAILQ_HEAD_INITIALIZER(queue);
+static unsigned long long	count;
+
+static struct qentry	*dequeue(void);
+
+void
+enqueue(struct str *x)
+{
+	struct qentry *item;
+
+	item = grep_malloc(sizeof(struct qentry));
+	item->data.dat = grep_malloc(sizeof(char) * x->len);
+	item->data.len = x->len;
+	item->data.line_no = x->line_no;
+	item->data.off = x->off;
+	memcpy(item->data.dat, x->dat, x->len);
+	item->data.file = x->file;
+
+	STAILQ_INSERT_TAIL(&queue, item, list);
+
+	if (++count > Bflag) {
+		item = dequeue();
+		free(item->data.dat);
+		free(item);
+	}
+}
+
+static struct qentry *
+dequeue(void)
+{
+	struct qentry *item;
+
+	item = STAILQ_FIRST(&queue);
+	if (item == NULL)
+		return (NULL);
+
+	STAILQ_REMOVE_HEAD(&queue, list);
+	--count;
+	return (item);
+}
+
+void
+printqueue(void)
+{
+	struct qentry *item;
+
+	while ((item = dequeue()) != NULL) {
+		printline(&item->data, '-', NULL, 0);
+		free(item->data.dat);
+		free(item);
+	}
+}
+
+void
+clearqueue(void)
+{
+	struct qentry *item;
+
+	while ((item = dequeue()) != NULL) {
+		free(item->data.dat);
+		free(item);
+	}
+}
diff --git a/toolbox/upstream-netbsd/usr.bin/grep/util.c b/toolbox/upstream-netbsd/usr.bin/grep/util.c
new file mode 100644
index 0000000..ecd948d
--- /dev/null
+++ b/toolbox/upstream-netbsd/usr.bin/grep/util.c
@@ -0,0 +1,499 @@
+/*	$NetBSD: util.c,v 1.17 2013/01/21 03:24:43 msaitoh Exp $	*/
+/*	$FreeBSD: head/usr.bin/grep/util.c 211496 2010-08-19 09:28:59Z des $	*/
+/*	$OpenBSD: util.c,v 1.39 2010/07/02 22:18:03 tedu Exp $	*/
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2010 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: util.c,v 1.17 2013/01/21 03:24:43 msaitoh Exp $");
+
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <ctype.h>
+#include <err.h>
+#include <errno.h>
+#include <fnmatch.h>
+#include <fts.h>
+#include <libgen.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "grep.h"
+
+static bool	 first, first_global = true;
+static unsigned long long since_printed;
+
+static int	 procline(struct str *l, int);
+
+bool
+file_matching(const char *fname)
+{
+	char *fname_base, *fname_copy;
+	unsigned int i;
+	bool ret;
+
+	ret = finclude ? false : true;
+	fname_copy = grep_strdup(fname);
+	fname_base = basename(fname_copy);
+
+	for (i = 0; i < fpatterns; ++i) {
+		if (fnmatch(fpattern[i].pat, fname, 0) == 0 ||
+		    fnmatch(fpattern[i].pat, fname_base, 0) == 0) {
+			if (fpattern[i].mode == EXCL_PAT) {
+				free(fname_copy);
+				return (false);
+			} else
+				ret = true;
+		}
+	}
+	free(fname_copy);
+	return (ret);
+}
+
+static inline bool
+dir_matching(const char *dname)
+{
+	unsigned int i;
+	bool ret;
+
+	ret = dinclude ? false : true;
+
+	for (i = 0; i < dpatterns; ++i) {
+		if (dname != NULL &&
+		    fnmatch(dname, dpattern[i].pat, 0) == 0) {
+			if (dpattern[i].mode == EXCL_PAT)
+				return (false);
+			else
+				ret = true;
+		}
+	}
+	return (ret);
+}
+
+/*
+ * Processes a directory when a recursive search is performed with
+ * the -R option.  Each appropriate file is passed to procfile().
+ */
+int
+grep_tree(char **argv)
+{
+	FTS *fts;
+	FTSENT *p;
+	char *d, *dir = NULL;
+	int c, fts_flags;
+	bool ok;
+
+	c = fts_flags = 0;
+
+	switch(linkbehave) {
+	case LINK_EXPLICIT:
+		fts_flags = FTS_COMFOLLOW;
+		break;
+	case LINK_SKIP:
+		fts_flags = FTS_PHYSICAL;
+		break;
+	default:
+		fts_flags = FTS_LOGICAL;
+			
+	}
+
+	fts_flags |= FTS_NOSTAT | FTS_NOCHDIR;
+
+	if (!(fts = fts_open(argv, fts_flags, NULL)))
+		err(2, "fts_open");
+	while ((p = fts_read(fts)) != NULL) {
+		switch (p->fts_info) {
+		case FTS_DNR:
+			/* FALLTHROUGH */
+		case FTS_ERR:
+			errx(2, "%s: %s", p->fts_path, strerror(p->fts_errno));
+			break;
+		case FTS_D:
+			/* FALLTHROUGH */
+		case FTS_DP:
+			break;
+		case FTS_DC:
+			/* Print a warning for recursive directory loop */
+			warnx("warning: %s: recursive directory loop",
+				p->fts_path);
+			break;
+		default:
+			/* Check for file exclusion/inclusion */
+			ok = true;
+			if (dexclude || dinclude) {
+				if ((d = strrchr(p->fts_path, '/')) != NULL) {
+					dir = grep_malloc(sizeof(char) *
+					    (d - p->fts_path + 1));
+					memcpy(dir, p->fts_path,
+					    d - p->fts_path);
+					dir[d - p->fts_path] = '\0';
+				}
+				ok = dir_matching(dir);
+				free(dir);
+				dir = NULL;
+			}
+			if (fexclude || finclude)
+				ok &= file_matching(p->fts_path);
+
+			if (ok)
+				c += procfile(p->fts_path);
+			break;
+		}
+	}
+
+	fts_close(fts);
+	return (c);
+}
+
+/*
+ * Opens a file and processes it.  Each file is processed line-by-line
+ * passing the lines to procline().
+ */
+int
+procfile(const char *fn)
+{
+	struct file *f;
+	struct stat sb;
+	struct str ln;
+	mode_t s;
+	int c, t;
+
+	if (mflag && (mcount <= 0))
+		return (0);
+
+	if (strcmp(fn, "-") == 0) {
+		fn = label != NULL ? label : getstr(1);
+		f = grep_open(NULL);
+	} else {
+		if (!stat(fn, &sb)) {
+			/* Check if we need to process the file */
+			s = sb.st_mode & S_IFMT;
+			if (s == S_IFDIR && dirbehave == DIR_SKIP)
+				return (0);
+			if ((s == S_IFIFO || s == S_IFCHR || s == S_IFBLK
+				|| s == S_IFSOCK) && devbehave == DEV_SKIP)
+					return (0);
+		}
+		f = grep_open(fn);
+	}
+	if (f == NULL) {
+		if (!sflag)
+			warn("%s", fn);
+		if (errno == ENOENT)
+			notfound = true;
+		return (0);
+	}
+
+	ln.file = grep_malloc(strlen(fn) + 1);
+	strcpy(ln.file, fn);
+	ln.line_no = 0;
+	ln.len = 0;
+	tail = 0;
+	ln.off = -1;
+
+	for (first = true, c = 0;  c == 0 || !(lflag || qflag); ) {
+		ln.off += ln.len + 1;
+		if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL || ln.len == 0)
+			break;
+		if (ln.len > 0 && ln.dat[ln.len - 1] == line_sep)
+			--ln.len;
+		ln.line_no++;
+
+		/* Return if we need to skip a binary file */
+		if (f->binary && binbehave == BINFILE_SKIP) {
+			grep_close(f);
+			free(ln.file);
+			free(f);
+			return (0);
+		}
+		/* Process the file line-by-line */
+		t = procline(&ln, f->binary);
+		c += t;
+
+		/* Count the matches if we have a match limit */
+		if (mflag) {
+			mcount -= t;
+			if (mcount <= 0)
+				break;
+		}
+	}
+	if (Bflag > 0)
+		clearqueue();
+	grep_close(f);
+
+	if (cflag) {
+		if (!hflag)
+			printf("%s:", ln.file);
+		printf("%u%c", c, line_sep);
+	}
+	if (lflag && !qflag && c != 0)
+		printf("%s%c", fn, line_sep);
+	if (Lflag && !qflag && c == 0)
+		printf("%s%c", fn, line_sep);
+	if (c && !cflag && !lflag && !Lflag &&
+	    binbehave == BINFILE_BIN && f->binary && !qflag)
+		printf(getstr(8), fn);
+
+	free(ln.file);
+	free(f);
+	return (c);
+}
+
+#define iswword(x)	(iswalnum((x)) || (x) == L'_')
+
+/*
+ * Processes a line comparing it with the specified patterns.  Each pattern
+ * is looped to be compared along with the full string, saving each and every
+ * match, which is necessary to colorize the output and to count the
+ * matches.  The matching lines are passed to printline() to display the
+ * appropriate output.
+ */
+static int
+procline(struct str *l, int nottext)
+{
+	regmatch_t matches[MAX_LINE_MATCHES];
+	regmatch_t pmatch;
+	size_t st = 0;
+	unsigned int i;
+	int c = 0, m = 0, r = 0;
+
+	/* Loop to process the whole line */
+	while (st <= l->len) {
+		pmatch.rm_so = st;
+		pmatch.rm_eo = l->len;
+
+		/* Loop to compare with all the patterns */
+		for (i = 0; i < patterns; i++) {
+/*
+ * XXX: grep_search() is a workaround for speed up and should be
+ * removed in the future.  See fastgrep.c.
+ */
+			if (fg_pattern[i].pattern) {
+				r = grep_search(&fg_pattern[i],
+				    (unsigned char *)l->dat,
+				    l->len, &pmatch);
+				r = (r == 0) ? 0 : REG_NOMATCH;
+				st = pmatch.rm_eo;
+			} else {
+				r = regexec(&r_pattern[i], l->dat, 1,
+				    &pmatch, eflags);
+				r = (r == 0) ? 0 : REG_NOMATCH;
+				st = pmatch.rm_eo;
+			}
+			if (r == REG_NOMATCH)
+				continue;
+			/* Check for full match */
+			if (xflag &&
+			    (pmatch.rm_so != 0 ||
+			     (size_t)pmatch.rm_eo != l->len))
+				continue;
+			/* Check for whole word match */
+			if (fg_pattern[i].word && pmatch.rm_so != 0) {
+				wchar_t wbegin, wend;
+
+				wbegin = wend = L' ';
+				if (pmatch.rm_so != 0 &&
+				    sscanf(&l->dat[pmatch.rm_so - 1],
+				    "%lc", &wbegin) != 1)
+					continue;
+				if ((size_t)pmatch.rm_eo != l->len &&
+				    sscanf(&l->dat[pmatch.rm_eo],
+				    "%lc", &wend) != 1)
+					continue;
+				if (iswword(wbegin) || iswword(wend))
+					continue;
+			}
+			c = 1;
+			if (m < MAX_LINE_MATCHES)
+				matches[m++] = pmatch;
+			/* matches - skip further patterns */
+			if ((color != NULL && !oflag) || qflag || lflag)
+				break;
+		}
+
+		if (vflag) {
+			c = !c;
+			break;
+		}
+		/* One pass if we are not recording matches */
+		if ((color != NULL && !oflag) || qflag || lflag)
+			break;
+
+		if (st == (size_t)pmatch.rm_so)
+			break; 	/* No matches */
+	}
+
+	if (c && binbehave == BINFILE_BIN && nottext)
+		return (c); /* Binary file */
+
+	/* Dealing with the context */
+	if ((tail || c) && !cflag && !qflag && !lflag && !Lflag) {
+		if (c) {
+			if ((Aflag || Bflag) && !first_global &&
+			    (first || since_printed > Bflag))
+				printf("--\n");
+			tail = Aflag;
+			if (Bflag > 0)
+				printqueue();
+			printline(l, ':', matches, m);
+		} else {
+			printline(l, '-', matches, m);
+			tail--;
+		}
+		first = false;
+		first_global = false;
+		since_printed = 0;
+	} else {
+		if (Bflag)
+			enqueue(l);
+		since_printed++;
+	}
+	return (c);
+}
+
+/*
+ * Safe malloc() for internal use.
+ */
+void *
+grep_malloc(size_t size)
+{
+	void *ptr;
+
+	if ((ptr = malloc(size)) == NULL)
+		err(2, "malloc");
+	return (ptr);
+}
+
+/*
+ * Safe calloc() for internal use.
+ */
+void *
+grep_calloc(size_t nmemb, size_t size)
+{
+	void *ptr;
+
+	if ((ptr = calloc(nmemb, size)) == NULL)
+		err(2, "calloc");
+	return (ptr);
+}
+
+/*
+ * Safe realloc() for internal use.
+ */
+void *
+grep_realloc(void *ptr, size_t size)
+{
+
+	if ((ptr = realloc(ptr, size)) == NULL)
+		err(2, "realloc");
+	return (ptr);
+}
+
+/*
+ * Safe strdup() for internal use.
+ */
+char *
+grep_strdup(const char *str)
+{
+	char *ret;
+
+	if ((ret = strdup(str)) == NULL)
+		err(2, "strdup");
+	return (ret);
+}
+
+/*
+ * Prints a matching line according to the command line options.
+ */
+void
+printline(struct str *line, int sep, regmatch_t *matches, int m)
+{
+	size_t a = 0;
+	int i, n = 0;
+
+	if (!hflag) {
+		if (nullflag == 0)
+			fputs(line->file, stdout);
+		else {
+			printf("%s", line->file);
+			putchar(0);
+		}
+		++n;
+	}
+	if (nflag) {
+		if (n > 0)
+			putchar(sep);
+		printf("%d", line->line_no);
+		++n;
+	}
+	if (bflag) {
+		if (n > 0)
+			putchar(sep);
+		printf("%lld", (long long)line->off);
+		++n;
+	}
+	if (n)
+		putchar(sep);
+	/* --color and -o */
+	if ((oflag || color) && m > 0) {
+		for (i = 0; i < m; i++) {
+			if (!oflag)
+				fwrite(line->dat + a, matches[i].rm_so - a, 1,
+				    stdout);
+			if (color) 
+				fprintf(stdout, "\33[%sm\33[K", color);
+
+				fwrite(line->dat + matches[i].rm_so, 
+				    matches[i].rm_eo - matches[i].rm_so, 1,
+				    stdout);
+			if (color) 
+				fprintf(stdout, "\33[m\33[K");
+			a = matches[i].rm_eo;
+			if (oflag)
+				putchar('\n');
+		}
+		if (!oflag) {
+			if (line->len - a > 0)
+				fwrite(line->dat + a, line->len - a, 1, stdout);
+			putchar(line_sep);
+		}
+	} else {
+		fwrite(line->dat, line->len, 1, stdout);
+		putchar(line_sep);
+	}
+}