diff --git a/security/selinux/ss/context.h b/security/selinux/ss/context.h
index b9a6f7f..658c2bd1 100644
--- a/security/selinux/ss/context.h
+++ b/security/selinux/ss/context.h
@@ -28,6 +28,8 @@
 	u32 role;
 	u32 type;
 	struct mls_range range;
+	char *str;	/* string representation if context cannot be mapped. */
+	u32 len;        /* length of string in bytes */
 };
 
 static inline void mls_context_init(struct context *c)
@@ -106,20 +108,43 @@
 
 static inline int context_cpy(struct context *dst, struct context *src)
 {
+	int rc;
+
 	dst->user = src->user;
 	dst->role = src->role;
 	dst->type = src->type;
-	return mls_context_cpy(dst, src);
+	if (src->str) {
+		dst->str = kstrdup(src->str, GFP_ATOMIC);
+		if (!dst->str)
+			return -ENOMEM;
+		dst->len = src->len;
+	} else {
+		dst->str = NULL;
+		dst->len = 0;
+	}
+	rc = mls_context_cpy(dst, src);
+	if (rc) {
+		kfree(dst->str);
+		return rc;
+	}
+	return 0;
 }
 
 static inline void context_destroy(struct context *c)
 {
 	c->user = c->role = c->type = 0;
+	kfree(c->str);
+	c->str = NULL;
+	c->len = 0;
 	mls_context_destroy(c);
 }
 
 static inline int context_cmp(struct context *c1, struct context *c2)
 {
+	if (c1->len && c2->len)
+		return (c1->len == c2->len && !strcmp(c1->str, c2->str));
+	if (c1->len || c2->len)
+		return 0;
 	return ((c1->user == c2->user) &&
 		(c1->role == c2->role) &&
 		(c1->type == c2->type) &&
diff --git a/security/selinux/ss/mls.c b/security/selinux/ss/mls.c
index 8b1706b..a6ca058 100644
--- a/security/selinux/ss/mls.c
+++ b/security/selinux/ss/mls.c
@@ -239,7 +239,8 @@
  * Policy read-lock must be held for sidtab lookup.
  *
  */
-int mls_context_to_sid(char oldc,
+int mls_context_to_sid(struct policydb *pol,
+		       char oldc,
 		       char **scontext,
 		       struct context *context,
 		       struct sidtab *s,
@@ -286,7 +287,7 @@
 		*p++ = 0;
 
 	for (l = 0; l < 2; l++) {
-		levdatum = hashtab_search(policydb.p_levels.table, scontextp);
+		levdatum = hashtab_search(pol->p_levels.table, scontextp);
 		if (!levdatum) {
 			rc = -EINVAL;
 			goto out;
@@ -311,7 +312,7 @@
 					*rngptr++ = 0;
 				}
 
-				catdatum = hashtab_search(policydb.p_cats.table,
+				catdatum = hashtab_search(pol->p_cats.table,
 							  scontextp);
 				if (!catdatum) {
 					rc = -EINVAL;
@@ -327,7 +328,7 @@
 				if (rngptr) {
 					int i;
 
-					rngdatum = hashtab_search(policydb.p_cats.table, rngptr);
+					rngdatum = hashtab_search(pol->p_cats.table, rngptr);
 					if (!rngdatum) {
 						rc = -EINVAL;
 						goto out;
@@ -395,7 +396,7 @@
 	if (!tmpstr) {
 		rc = -ENOMEM;
 	} else {
-		rc = mls_context_to_sid(':', &tmpstr, context,
+		rc = mls_context_to_sid(&policydb, ':', &tmpstr, context,
 					NULL, SECSID_NULL);
 		kfree(freestr);
 	}
diff --git a/security/selinux/ss/mls.h b/security/selinux/ss/mls.h
index 0fdf625..1276715 100644
--- a/security/selinux/ss/mls.h
+++ b/security/selinux/ss/mls.h
@@ -30,7 +30,8 @@
 int mls_range_isvalid(struct policydb *p, struct mls_range *r);
 int mls_level_isvalid(struct policydb *p, struct mls_level *l);
 
-int mls_context_to_sid(char oldc,
+int mls_context_to_sid(struct policydb *p,
+		       char oldc,
 		       char **scontext,
 		       struct context *context,
 		       struct sidtab *s,
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index dcc2e1c..b86ac9d 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -616,6 +616,14 @@
 	*scontext = NULL;
 	*scontext_len = 0;
 
+	if (context->len) {
+		*scontext_len = context->len;
+		*scontext = kstrdup(context->str, GFP_ATOMIC);
+		if (!(*scontext))
+			return -ENOMEM;
+		return 0;
+	}
+
 	/* Compute the size of the context. */
 	*scontext_len += strlen(policydb.p_user_val_to_name[context->user - 1]) + 1;
 	*scontext_len += strlen(policydb.p_role_val_to_name[context->role - 1]) + 1;
@@ -655,17 +663,8 @@
 	return initial_sid_to_string[sid];
 }
 
-/**
- * security_sid_to_context - Obtain a context for a given SID.
- * @sid: security identifier, SID
- * @scontext: security context
- * @scontext_len: length in bytes
- *
- * Write the string representation of the context associated with @sid
- * into a dynamically allocated string of the correct size.  Set @scontext
- * to point to this string and set @scontext_len to the length of the string.
- */
-int security_sid_to_context(u32 sid, char **scontext, u32 *scontext_len)
+static int security_sid_to_context_core(u32 sid, char **scontext,
+					u32 *scontext_len, int force)
 {
 	struct context *context;
 	int rc = 0;
@@ -693,7 +692,10 @@
 		goto out;
 	}
 	POLICY_RDLOCK;
-	context = sidtab_search(&sidtab, sid);
+	if (force)
+		context = sidtab_search_force(&sidtab, sid);
+	else
+		context = sidtab_search(&sidtab, sid);
 	if (!context) {
 		printk(KERN_ERR "SELinux: %s:  unrecognized SID %d\n",
 			__func__, sid);
@@ -708,17 +710,129 @@
 
 }
 
-static int security_context_to_sid_core(const char *scontext, u32 scontext_len,
-					u32 *sid, u32 def_sid, gfp_t gfp_flags)
+/**
+ * security_sid_to_context - Obtain a context for a given SID.
+ * @sid: security identifier, SID
+ * @scontext: security context
+ * @scontext_len: length in bytes
+ *
+ * Write the string representation of the context associated with @sid
+ * into a dynamically allocated string of the correct size.  Set @scontext
+ * to point to this string and set @scontext_len to the length of the string.
+ */
+int security_sid_to_context(u32 sid, char **scontext, u32 *scontext_len)
 {
-	char *scontext2;
-	struct context context;
+	return security_sid_to_context_core(sid, scontext, scontext_len, 0);
+}
+
+int security_sid_to_context_force(u32 sid, char **scontext, u32 *scontext_len)
+{
+	return security_sid_to_context_core(sid, scontext, scontext_len, 1);
+}
+
+static int string_to_context_struct(struct policydb *pol,
+				    struct sidtab *sidtabp,
+				    const char *scontext,
+				    u32 scontext_len,
+				    struct context *ctx,
+				    u32 def_sid,
+				    gfp_t gfp_flags)
+{
+	char *scontext2 = NULL;
 	struct role_datum *role;
 	struct type_datum *typdatum;
 	struct user_datum *usrdatum;
 	char *scontextp, *p, oldc;
 	int rc = 0;
 
+	context_init(ctx);
+
+	/* Copy the string so that we can modify the copy as we parse it. */
+	scontext2 = kmalloc(scontext_len+1, gfp_flags);
+	if (!scontext2) {
+		rc = -ENOMEM;
+		goto out;
+	}
+	memcpy(scontext2, scontext, scontext_len);
+	scontext2[scontext_len] = 0;
+
+	/* Parse the security context. */
+
+	rc = -EINVAL;
+	scontextp = (char *) scontext2;
+
+	/* Extract the user. */
+	p = scontextp;
+	while (*p && *p != ':')
+		p++;
+
+	if (*p == 0)
+		goto out;
+
+	*p++ = 0;
+
+	usrdatum = hashtab_search(pol->p_users.table, scontextp);
+	if (!usrdatum)
+		goto out;
+
+	ctx->user = usrdatum->value;
+
+	/* Extract role. */
+	scontextp = p;
+	while (*p && *p != ':')
+		p++;
+
+	if (*p == 0)
+		goto out;
+
+	*p++ = 0;
+
+	role = hashtab_search(pol->p_roles.table, scontextp);
+	if (!role)
+		goto out;
+	ctx->role = role->value;
+
+	/* Extract type. */
+	scontextp = p;
+	while (*p && *p != ':')
+		p++;
+	oldc = *p;
+	*p++ = 0;
+
+	typdatum = hashtab_search(pol->p_types.table, scontextp);
+	if (!typdatum)
+		goto out;
+
+	ctx->type = typdatum->value;
+
+	rc = mls_context_to_sid(pol, oldc, &p, ctx, sidtabp, def_sid);
+	if (rc)
+		goto out;
+
+	if ((p - scontext2) < scontext_len) {
+		rc = -EINVAL;
+		goto out;
+	}
+
+	/* Check the validity of the new context. */
+	if (!policydb_context_isvalid(pol, ctx)) {
+		rc = -EINVAL;
+		context_destroy(ctx);
+		goto out;
+	}
+	rc = 0;
+out:
+	kfree(scontext2);
+	return rc;
+}
+
+static int security_context_to_sid_core(const char *scontext, u32 scontext_len,
+					u32 *sid, u32 def_sid, gfp_t gfp_flags,
+					int force)
+{
+	struct context context;
+	int rc = 0;
+
 	if (!ss_initialized) {
 		int i;
 
@@ -733,94 +847,26 @@
 	}
 	*sid = SECSID_NULL;
 
-	/* Copy the string so that we can modify the copy as we parse it.
-	   The string should already by null terminated, but we append a
-	   null suffix to the copy to avoid problems with the existing
-	   attr package, which doesn't view the null terminator as part
-	   of the attribute value. */
-	scontext2 = kmalloc(scontext_len+1, gfp_flags);
-	if (!scontext2) {
-		rc = -ENOMEM;
-		goto out;
-	}
-	memcpy(scontext2, scontext, scontext_len);
-	scontext2[scontext_len] = 0;
-
-	context_init(&context);
-	*sid = SECSID_NULL;
-
 	POLICY_RDLOCK;
-
-	/* Parse the security context. */
-
-	rc = -EINVAL;
-	scontextp = (char *) scontext2;
-
-	/* Extract the user. */
-	p = scontextp;
-	while (*p && *p != ':')
-		p++;
-
-	if (*p == 0)
-		goto out_unlock;
-
-	*p++ = 0;
-
-	usrdatum = hashtab_search(policydb.p_users.table, scontextp);
-	if (!usrdatum)
-		goto out_unlock;
-
-	context.user = usrdatum->value;
-
-	/* Extract role. */
-	scontextp = p;
-	while (*p && *p != ':')
-		p++;
-
-	if (*p == 0)
-		goto out_unlock;
-
-	*p++ = 0;
-
-	role = hashtab_search(policydb.p_roles.table, scontextp);
-	if (!role)
-		goto out_unlock;
-	context.role = role->value;
-
-	/* Extract type. */
-	scontextp = p;
-	while (*p && *p != ':')
-		p++;
-	oldc = *p;
-	*p++ = 0;
-
-	typdatum = hashtab_search(policydb.p_types.table, scontextp);
-	if (!typdatum)
-		goto out_unlock;
-
-	context.type = typdatum->value;
-
-	rc = mls_context_to_sid(oldc, &p, &context, &sidtab, def_sid);
-	if (rc)
-		goto out_unlock;
-
-	if ((p - scontext2) < scontext_len) {
-		rc = -EINVAL;
-		goto out_unlock;
-	}
-
-	/* Check the validity of the new context. */
-	if (!policydb_context_isvalid(&policydb, &context)) {
-		rc = -EINVAL;
-		goto out_unlock;
-	}
-	/* Obtain the new sid. */
+	rc = string_to_context_struct(&policydb, &sidtab,
+				      scontext, scontext_len,
+				      &context, def_sid, gfp_flags);
+	if (rc == -EINVAL && force) {
+		context.str = kmalloc(scontext_len+1, gfp_flags);
+		if (!context.str) {
+			rc = -ENOMEM;
+			goto out;
+		}
+		memcpy(context.str, scontext, scontext_len);
+		context.str[scontext_len] = 0;
+		context.len = scontext_len;
+	} else if (rc)
+		goto out;
 	rc = sidtab_context_to_sid(&sidtab, &context, sid);
-out_unlock:
-	POLICY_RDUNLOCK;
-	context_destroy(&context);
-	kfree(scontext2);
+	if (rc)
+		context_destroy(&context);
 out:
+	POLICY_RDUNLOCK;
 	return rc;
 }
 
@@ -838,7 +884,7 @@
 int security_context_to_sid(const char *scontext, u32 scontext_len, u32 *sid)
 {
 	return security_context_to_sid_core(scontext, scontext_len,
-					    sid, SECSID_NULL, GFP_KERNEL);
+					    sid, SECSID_NULL, GFP_KERNEL, 0);
 }
 
 /**
@@ -855,6 +901,7 @@
  * The default SID is passed to the MLS layer to be used to allow
  * kernel labeling of the MLS field if the MLS field is not present
  * (for upgrading to MLS without full relabel).
+ * Implicitly forces adding of the context even if it cannot be mapped yet.
  * Returns -%EINVAL if the context is invalid, -%ENOMEM if insufficient
  * memory is available, or 0 on success.
  */
@@ -862,7 +909,14 @@
 				    u32 *sid, u32 def_sid, gfp_t gfp_flags)
 {
 	return security_context_to_sid_core(scontext, scontext_len,
-					    sid, def_sid, gfp_flags);
+					    sid, def_sid, gfp_flags, 1);
+}
+
+int security_context_to_sid_force(const char *scontext, u32 scontext_len,
+				  u32 *sid)
+{
+	return security_context_to_sid_core(scontext, scontext_len,
+					    sid, SECSID_NULL, GFP_KERNEL, 1);
 }
 
 static int compute_sid_handle_invalid_context(
@@ -1246,9 +1300,12 @@
 		char *s;
 		u32 len;
 
-		context_struct_to_string(context, &s, &len);
-		printk(KERN_ERR "SELinux:  context %s is invalid\n", s);
-		kfree(s);
+		if (!context_struct_to_string(context, &s, &len)) {
+			printk(KERN_WARNING
+		       "SELinux:  Context %s would be invalid if enforcing\n",
+			       s);
+			kfree(s);
+		}
 	}
 	return rc;
 }
@@ -1280,6 +1337,32 @@
 
 	args = p;
 
+	if (c->str) {
+		struct context ctx;
+		rc = string_to_context_struct(args->newp, NULL, c->str,
+					      c->len, &ctx, SECSID_NULL,
+					      GFP_KERNEL);
+		if (!rc) {
+			printk(KERN_INFO
+		       "SELinux:  Context %s became valid (mapped).\n",
+			       c->str);
+			/* Replace string with mapped representation. */
+			kfree(c->str);
+			memcpy(c, &ctx, sizeof(*c));
+			goto out;
+		} else if (rc == -EINVAL) {
+			/* Retain string representation for later mapping. */
+			rc = 0;
+			goto out;
+		} else {
+			/* Other error condition, e.g. ENOMEM. */
+			printk(KERN_ERR
+		       "SELinux:   Unable to map context %s, rc = %d.\n",
+			       c->str, -rc);
+			goto out;
+		}
+	}
+
 	rc = context_cpy(&oldc, c);
 	if (rc)
 		goto out;
@@ -1319,13 +1402,21 @@
 	}
 
 	context_destroy(&oldc);
+	rc = 0;
 out:
 	return rc;
 bad:
-	context_struct_to_string(&oldc, &s, &len);
+	/* Map old representation to string and save it. */
+	if (context_struct_to_string(&oldc, &s, &len))
+		return -ENOMEM;
 	context_destroy(&oldc);
-	printk(KERN_ERR "SELinux:  invalidating context %s\n", s);
-	kfree(s);
+	context_destroy(c);
+	c->str = s;
+	c->len = len;
+	printk(KERN_INFO
+	       "SELinux:  Context %s became invalid (unmapped).\n",
+	       c->str);
+	rc = 0;
 	goto out;
 }
 
@@ -1406,7 +1497,11 @@
 		return -EINVAL;
 	}
 
-	sidtab_init(&newsidtab);
+	if (sidtab_init(&newsidtab)) {
+		LOAD_UNLOCK;
+		policydb_destroy(&newpolicydb);
+		return -ENOMEM;
+	}
 
 	/* Verify that the kernel defined classes are correct. */
 	if (validate_classes(&newpolicydb)) {
@@ -1429,11 +1524,15 @@
 		goto err;
 	}
 
-	/* Convert the internal representations of contexts
-	   in the new SID table and remove invalid SIDs. */
+	/*
+	 * Convert the internal representations of contexts
+	 * in the new SID table.
+	 */
 	args.oldp = &policydb;
 	args.newp = &newpolicydb;
-	sidtab_map_remove_on_error(&newsidtab, convert_context, &args);
+	rc = sidtab_map(&newsidtab, convert_context, &args);
+	if (rc)
+		goto err;
 
 	/* Save the old policydb and SID table to free later. */
 	memcpy(&oldpolicydb, &policydb, sizeof policydb);
@@ -1673,6 +1772,8 @@
 
 	POLICY_RDLOCK;
 
+	context_init(&usercon);
+
 	fromcon = sidtab_search(&sidtab, fromsid);
 	if (!fromcon) {
 		rc = -EINVAL;
diff --git a/security/selinux/ss/sidtab.c b/security/selinux/ss/sidtab.c
index 4a516ff..ba35416 100644
--- a/security/selinux/ss/sidtab.c
+++ b/security/selinux/ss/sidtab.c
@@ -86,7 +86,7 @@
 	return rc;
 }
 
-struct context *sidtab_search(struct sidtab *s, u32 sid)
+static struct context *sidtab_search_core(struct sidtab *s, u32 sid, int force)
 {
 	int hvalue;
 	struct sidtab_node *cur;
@@ -99,7 +99,10 @@
 	while (cur != NULL && sid > cur->sid)
 		cur = cur->next;
 
-	if (cur == NULL || sid != cur->sid) {
+	if (force && cur && sid == cur->sid && cur->context.len)
+		return &cur->context;
+
+	if (cur == NULL || sid != cur->sid || cur->context.len) {
 		/* Remap invalid SIDs to the unlabeled SID. */
 		sid = SECINITSID_UNLABELED;
 		hvalue = SIDTAB_HASH(sid);
@@ -113,6 +116,16 @@
 	return &cur->context;
 }
 
+struct context *sidtab_search(struct sidtab *s, u32 sid)
+{
+	return sidtab_search_core(s, sid, 0);
+}
+
+struct context *sidtab_search_force(struct sidtab *s, u32 sid)
+{
+	return sidtab_search_core(s, sid, 1);
+}
+
 int sidtab_map(struct sidtab *s,
 	       int (*apply) (u32 sid,
 			     struct context *context,
@@ -138,43 +151,6 @@
 	return rc;
 }
 
-void sidtab_map_remove_on_error(struct sidtab *s,
-				int (*apply) (u32 sid,
-					      struct context *context,
-					      void *args),
-				void *args)
-{
-	int i, ret;
-	struct sidtab_node *last, *cur, *temp;
-
-	if (!s)
-		return;
-
-	for (i = 0; i < SIDTAB_SIZE; i++) {
-		last = NULL;
-		cur = s->htable[i];
-		while (cur != NULL) {
-			ret = apply(cur->sid, &cur->context, args);
-			if (ret) {
-				if (last)
-					last->next = cur->next;
-				else
-					s->htable[i] = cur->next;
-				temp = cur;
-				cur = cur->next;
-				context_destroy(&temp->context);
-				kfree(temp);
-				s->nel--;
-			} else {
-				last = cur;
-				cur = cur->next;
-			}
-		}
-	}
-
-	return;
-}
-
 static inline u32 sidtab_search_context(struct sidtab *s,
 						  struct context *context)
 {
@@ -215,6 +191,10 @@
 			goto unlock_out;
 		}
 		sid = s->next_sid++;
+		if (context->len)
+			printk(KERN_INFO
+		       "SELinux:  Context %s is not valid (left unmapped).\n",
+			       context->str);
 		ret = sidtab_insert(s, sid, context);
 		if (ret)
 			s->next_sid--;
diff --git a/security/selinux/ss/sidtab.h b/security/selinux/ss/sidtab.h
index 2fe9dfa..64ea5b1 100644
--- a/security/selinux/ss/sidtab.h
+++ b/security/selinux/ss/sidtab.h
@@ -32,6 +32,7 @@
 int sidtab_init(struct sidtab *s);
 int sidtab_insert(struct sidtab *s, u32 sid, struct context *context);
 struct context *sidtab_search(struct sidtab *s, u32 sid);
+struct context *sidtab_search_force(struct sidtab *s, u32 sid);
 
 int sidtab_map(struct sidtab *s,
 	       int (*apply) (u32 sid,
@@ -39,12 +40,6 @@
 			     void *args),
 	       void *args);
 
-void sidtab_map_remove_on_error(struct sidtab *s,
-				int (*apply) (u32 sid,
-					      struct context *context,
-					      void *args),
-				void *args);
-
 int sidtab_context_to_sid(struct sidtab *s,
 			  struct context *context,
 			  u32 *sid);