Index: uspace/app/bdsh/compl.c
===================================================================
--- uspace/app/bdsh/compl.c	(revision 1e8b633ea4fe33de942dfc3b6dfe8d63fa018b89)
+++ uspace/app/bdsh/compl.c	(revision aeeaf0f6c1793aa25aae1f2db6ebef814994f19d)
@@ -40,4 +40,5 @@
 #include "exec.h"
 #include "tok.h"
+#include "util.h"
 
 static errno_t compl_init(wchar_t *text, size_t pos, size_t *cstart, void **state);
@@ -209,6 +210,4 @@
 		}
 		*cstart += rpath_sep + 1 - prefix;
-		free(prefix);
-		prefix = NULL;
 
 		cs->path_list = malloc(sizeof(char *) * 2);
@@ -217,5 +216,22 @@
 			goto error;
 		}
-		cs->path_list[0] = dirname;
+
+		if (!is_path(prefix) && cs->is_command) {
+			cs->path_list[0] = malloc(sizeof(char) * PATH_MAX);
+			if (cs->path_list[0] == NULL) {
+				retval = ENOMEM;
+				goto error;
+			}
+
+			int ret = snprintf(cs->path_list[0], PATH_MAX, "%s/%s", search_dir[0], dirname);
+			if (ret < 0 || ret >= PATH_MAX) {
+				retval = ENOMEM;
+				goto error;
+			}
+		} else {
+			cs->path_list[0] = dirname;
+		}
+
+		free(prefix);
 		cs->path_list[1] = NULL;
 		/*
Index: uspace/app/bdsh/exec.c
===================================================================
--- uspace/app/bdsh/exec.c	(revision 1e8b633ea4fe33de942dfc3b6dfe8d63fa018b89)
+++ uspace/app/bdsh/exec.c	(revision aeeaf0f6c1793aa25aae1f2db6ebef814994f19d)
@@ -47,8 +47,5 @@
 #include "errors.h"
 
-/* FIXME: Just have find_command() return an allocated string */
-static char *found;
-
-static char *find_command(char *);
+static errno_t find_command(char *, char **);
 static int try_access(const char *);
 
@@ -68,30 +65,48 @@
 }
 
-/** Returns the full path of "cmd" if cmd is found
+/** Returns EOK if no internal failure or else ENOMEM
  *
- * else just hand back cmd as it was presented
+ * When the parameter `cmd` can be found then the absolute path will be set in `found`.
+ * Or else `found` will be NULL.
+ * `found` will be newly allocated and must be freed by the caller
  */
-static char *find_command(char *cmd)
+static errno_t find_command(char *cmd, char **found)
 {
-	size_t i;
+	/* The user has specified a full or relative path, just give it back. */
+	if (is_path(cmd)) {
+		if (-1 != try_access(cmd)) {
+			*found = str_dup(cmd);
+			return EOK;
+		}
 
-	found = (char *)malloc(PATH_MAX);
+		*found = NULL;
+		return EOK;
+	}
 
-	/* The user has specified a full or relative path, just give it back. */
-	if (-1 != try_access(cmd)) {
-		return (char *) cmd;
+	*found = (char *)malloc(PATH_MAX);
+	if (*found == NULL) {
+		return ENOMEM;
 	}
 
 	/* We now have n places to look for the command */
+	size_t i;
+	size_t cmd_length = str_length(cmd);
 	for (i = 0; search_dir[i] != NULL; i++) {
-		memset(found, 0, PATH_MAX);
-		snprintf(found, PATH_MAX, "%s/%s", search_dir[i], cmd);
-		if (-1 != try_access(found)) {
-			return (char *) found;
+		if (str_length(search_dir[i]) + cmd_length + 2 > PATH_MAX) {
+			free(*found);
+			return ENOMEM;
+		}
+
+		memset(*found, 0, PATH_MAX);
+		snprintf(*found, PATH_MAX, "%s/%s", search_dir[i], cmd);
+		if (-1 != try_access(*found)) {
+			return EOK;
 		}
 	}
+	free(*found);
+	*found = NULL;
 
-	/* We didn't find it, just give it back as-is. */
-	return (char *) cmd;
+	/* We didn't find it, return NULL */
+	return EOK;
 }
 
@@ -107,6 +122,14 @@
 	FILE *files[3];
 
-	tmp = str_dup(find_command(cmd));
-	free(found);
+	rc = find_command(cmd, &tmp);
+	if (rc != EOK) {
+		cli_error(CL_ENOMEM, "%s: failure executing find_command()", progname);
+		return 1;
+	}
+
+	if (tmp == NULL) {
+		cli_error(CL_EEXEC, "%s: Command not found '%s'", progname, cmd);
+		return 1;
+	}
 
 	files[0] = io->stdin;
Index: uspace/app/bdsh/util.c
===================================================================
--- uspace/app/bdsh/util.c	(revision 1e8b633ea4fe33de942dfc3b6dfe8d63fa018b89)
+++ uspace/app/bdsh/util.c	(revision aeeaf0f6c1793aa25aae1f2db6ebef814994f19d)
@@ -74,2 +74,15 @@
 	return 0;
 }
+
+/*
+ * Returns true if the string is a relative or an absolute path
+ */
+bool is_path(const char *cmd)
+{
+
+	bool ret = str_lcmp(cmd, "/", 1) == 0;
+	ret = ret || str_lcmp(cmd, "./", 2) == 0;
+	ret = ret || str_lcmp(cmd, "../", 3) == 0;
+
+	return ret;
+}
Index: uspace/app/bdsh/util.h
===================================================================
--- uspace/app/bdsh/util.h	(revision 1e8b633ea4fe33de942dfc3b6dfe8d63fa018b89)
+++ uspace/app/bdsh/util.h	(revision aeeaf0f6c1793aa25aae1f2db6ebef814994f19d)
@@ -31,8 +31,10 @@
 
 #include "scli.h"
+#include <stdbool.h>
 
 /* Utility functions */
 extern unsigned int cli_count_args(char **);
 extern unsigned int cli_set_prompt(cliuser_t *usr);
+extern bool is_path(const char *cmd);
 
 #endif