3 files changed, 217 insertions, 111 deletions

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 7102457..102e9ec 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -128,6 +128,11 @@ static struct policydb_compat_info policydb_compat[] = {
 		.sym_num	= SYM_NUM,
 		.ocon_num	= OCON_NUM,
 	},
+	{
+		.version	= POLICYDB_VERSION_ROLETRANS,
+		.sym_num	= SYM_NUM,
+		.ocon_num	= OCON_NUM,
+	},
 };
 
 static struct policydb_compat_info *policydb_lookup_compat(int version)
@@ -179,6 +184,43 @@ out:
 	return rc;
 }
 
+static u32 filenametr_hash(struct hashtab *h, const void *k)
+{
+	const struct filename_trans *ft = k;
+	unsigned long hash;
+	unsigned int byte_num;
+	unsigned char focus;
+
+	hash = ft->stype ^ ft->ttype ^ ft->tclass;
+
+	byte_num = 0;
+	while ((focus = ft->name[byte_num++]))
+		hash = partial_name_hash(focus, hash);
+	return hash & (h->size - 1);
+}
+
+static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
+{
+	const struct filename_trans *ft1 = k1;
+	const struct filename_trans *ft2 = k2;
+	int v;
+
+	v = ft1->stype - ft2->stype;
+	if (v)
+		return v;
+
+	v = ft1->ttype - ft2->ttype;
+	if (v)
+		return v;
+
+	v = ft1->tclass - ft2->tclass;
+	if (v)
+		return v;
+
+	return strcmp(ft1->name, ft2->name);
+
+}
+
 static u32 rangetr_hash(struct hashtab *h, const void *k)
 {
 	const struct range_trans *key = k;
@@ -231,15 +273,22 @@ static int policydb_init(struct policydb *p)
 	if (rc)
 		goto out;
 
+	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp, (1 << 10));
+	if (!p->filename_trans)
+		goto out;
+
 	p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256);
 	if (!p->range_tr)
 		goto out;
 
+	ebitmap_init(&p->filename_trans_ttypes);
 	ebitmap_init(&p->policycaps);
 	ebitmap_init(&p->permissive_map);
 
 	return 0;
 out:
+	hashtab_destroy(p->filename_trans);
+	hashtab_destroy(p->range_tr);
 	for (i = 0; i < SYM_NUM; i++)
 		hashtab_destroy(p->symtab[i].table);
 	return rc;
@@ -417,32 +466,26 @@ static int (*index_f[SYM_NUM]) (void *key, void *datum, void *datap) =
 };
 
 #ifdef DEBUG_HASHES
-static void symtab_hash_eval(struct symtab *s)
+static void hash_eval(struct hashtab *h, const char *hash_name)
 {
-	int i;
-
-	for (i = 0; i < SYM_NUM; i++) {
-		struct hashtab *h = s[i].table;
-		struct hashtab_info info;
+	struct hashtab_info info;
 
-		hashtab_stat(h, &info);
-		printk(KERN_DEBUG "SELinux: %s:  %d entries and %d/%d buckets used, "
-		       "longest chain length %d\n", symtab_name[i], h->nel,
-		       info.slots_used, h->size, info.max_chain_len);
-	}
+	hashtab_stat(h, &info);
+	printk(KERN_DEBUG "SELinux: %s:  %d entries and %d/%d buckets used, "
+	       "longest chain length %d\n", hash_name, h->nel,
+	       info.slots_used, h->size, info.max_chain_len);
 }
 
-static void rangetr_hash_eval(struct hashtab *h)
+static void symtab_hash_eval(struct symtab *s)
 {
-	struct hashtab_info info;
+	int i;
 
-	hashtab_stat(h, &info);
-	printk(KERN_DEBUG "SELinux: rangetr:  %d entries and %d/%d buckets used, "
-	       "longest chain length %d\n", h->nel,
-	       info.slots_used, h->size, info.max_chain_len);
+	for (i = 0; i < SYM_NUM; i++)
+		hash_eval(s[i].table, symtab_name[i]);
 }
+
 #else
-static inline void rangetr_hash_eval(struct hashtab *h)
+static inline void hash_eval(struct hashtab *h, char *hash_name)
 {
 }
 #endif
@@ -675,6 +718,16 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
 	cat_destroy,
 };
 
+static int filenametr_destroy(void *key, void *datum, void *p)
+{
+	struct filename_trans *ft = key;
+	kfree(ft->name);
+	kfree(key);
+	kfree(datum);
+	cond_resched();
+	return 0;
+}
+
 static int range_tr_destroy(void *key, void *datum, void *p)
 {
 	struct mls_range *rt = datum;
@@ -709,7 +762,6 @@ void policydb_destroy(struct policydb *p)
 	int i;
 	struct role_allow *ra, *lra = NULL;
 	struct role_trans *tr, *ltr = NULL;
-	struct filename_trans *ft, *nft;
 
 	for (i = 0; i < SYM_NUM; i++) {
 		cond_resched();
@@ -773,6 +825,9 @@ void policydb_destroy(struct policydb *p)
 	}
 	kfree(lra);
 
+	hashtab_map(p->filename_trans, filenametr_destroy, NULL);
+	hashtab_destroy(p->filename_trans);
+
 	hashtab_map(p->range_tr, range_tr_destroy, NULL);
 	hashtab_destroy(p->range_tr);
 
@@ -788,14 +843,7 @@ void policydb_destroy(struct policydb *p)
 		flex_array_free(p->type_attr_map_array);
 	}
 
-	ft = p->filename_trans;
-	while (ft) {
-		nft = ft->next;
-		kfree(ft->name);
-		kfree(ft);
-		ft = nft;
-	}
-
+	ebitmap_destroy(&p->filename_trans_ttypes);
 	ebitmap_destroy(&p->policycaps);
 	ebitmap_destroy(&p->permissive_map);
 
@@ -1795,7 +1843,7 @@ static int range_read(struct policydb *p, void *fp)
 		rt = NULL;
 		r = NULL;
 	}
-	rangetr_hash_eval(p->range_tr);
+	hash_eval(p->range_tr, "rangetr");
 	rc = 0;
 out:
 	kfree(rt);
@@ -1805,9 +1853,10 @@ out:
 
 static int filename_trans_read(struct policydb *p, void *fp)
 {
-	struct filename_trans *ft, *last;
-	u32 nel, len;
+	struct filename_trans *ft;
+	struct filename_trans_datum *otype;
 	char *name;
+	u32 nel, len;
 	__le32 buf[4];
 	int rc, i;
 
@@ -1816,25 +1865,23 @@ static int filename_trans_read(struct policydb *p, void *fp)
 
 	rc = next_entry(buf, fp, sizeof(u32));
 	if (rc)
-		goto out;
+		return rc;
 	nel = le32_to_cpu(buf[0]);
 
-	last = p->filename_trans;
-	while (last && last->next)
-		last = last->next;
-
 	for (i = 0; i < nel; i++) {
+		ft = NULL;
+		otype = NULL;
+		name = NULL;
+
 		rc = -ENOMEM;
 		ft = kzalloc(sizeof(*ft), GFP_KERNEL);
 		if (!ft)
 			goto out;
 
-		/* add it to the tail of the list */
-		if (!last)
-			p->filename_trans = ft;
-		else
-			last->next = ft;
-		last = ft;
+		rc = -ENOMEM;
+		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
+		if (!otype)
+			goto out;
 
 		/* length of the path component string */
 		rc = next_entry(buf, fp, sizeof(u32));
@@ -1862,10 +1909,22 @@ static int filename_trans_read(struct policydb *p, void *fp)
 		ft->stype = le32_to_cpu(buf[0]);
 		ft->ttype = le32_to_cpu(buf[1]);
 		ft->tclass = le32_to_cpu(buf[2]);
-		ft->otype = le32_to_cpu(buf[3]);
+
+		otype->otype = le32_to_cpu(buf[3]);
+
+		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
+		if (rc)
+			goto out;
+
+		hashtab_insert(p->filename_trans, ft, otype);
 	}
-	rc = 0;
+	hash_eval(p->filename_trans, "filenametr");
+	return 0;
 out:
+	kfree(ft);
+	kfree(name);
+	kfree(otype);
+
 	return rc;
 }
 
@@ -2266,6 +2325,11 @@ int policydb_read(struct policydb *p, void *fp)
 		p->symtab[i].nprim = nprim;
 	}
 
+	rc = -EINVAL;
+	p->process_class = string_to_security_class(p, "process");
+	if (!p->process_class)
+		goto bad;
+
 	rc = avtab_read(&p->te_avtab, fp, p);
 	if (rc)
 		goto bad;
@@ -2298,8 +2362,17 @@ int policydb_read(struct policydb *p, void *fp)
 		tr->role = le32_to_cpu(buf[0]);
 		tr->type = le32_to_cpu(buf[1]);
 		tr->new_role = le32_to_cpu(buf[2]);
+		if (p->policyvers >= POLICYDB_VERSION_ROLETRANS) {
+			rc = next_entry(buf, fp, sizeof(u32));
+			if (rc)
+				goto bad;
+			tr->tclass = le32_to_cpu(buf[0]);
+		} else
+			tr->tclass = p->process_class;
+
 		if (!policydb_role_isvalid(p, tr->role) ||
 		    !policydb_type_isvalid(p, tr->type) ||
+		    !policydb_class_isvalid(p, tr->tclass) ||
 		    !policydb_role_isvalid(p, tr->new_role))
 			goto bad;
 		ltr = tr;
@@ -2341,11 +2414,6 @@ int policydb_read(struct policydb *p, void *fp)
 		goto bad;
 
 	rc = -EINVAL;
-	p->process_class = string_to_security_class(p, "process");
-	if (!p->process_class)
-		goto bad;
-
-	rc = -EINVAL;
 	p->process_trans_perms = string_to_av_perm(p, p->process_class, "transition");
 	p->process_trans_perms |= string_to_av_perm(p, p->process_class, "dyntransition");
 	if (!p->process_trans_perms)
@@ -2517,8 +2585,9 @@ static int cat_write(void *vkey, void *datum, void *ptr)
 	return 0;
 }
 
-static int role_trans_write(struct role_trans *r, void *fp)
+static int role_trans_write(struct policydb *p, void *fp)
 {
+	struct role_trans *r = p->role_tr;
 	struct role_trans *tr;
 	u32 buf[3];
 	size_t nel;
@@ -2538,6 +2607,12 @@ static int role_trans_write(struct role_trans *r, void *fp)
 		rc = put_entry(buf, sizeof(u32), 3, fp);
 		if (rc)
 			return rc;
+		if (p->policyvers >= POLICYDB_VERSION_ROLETRANS) {
+			buf[0] = cpu_to_le32(tr->tclass);
+			rc = put_entry(buf, sizeof(u32), 1, fp);
+			if (rc)
+				return rc;
+		}
 	}
 
 	return 0;
@@ -3045,7 +3120,7 @@ static int genfs_write(struct policydb *p, void *fp)
 	return 0;
 }
 
-static int range_count(void *key, void *data, void *ptr)
+static int hashtab_cnt(void *key, void *data, void *ptr)
 {
 	int *cnt = ptr;
 	*cnt = *cnt + 1;
@@ -3093,7 +3168,7 @@ static int range_write(struct policydb *p, void *fp)
 
 	/* count the number of entries in the hashtab */
 	nel = 0;
-	rc = hashtab_map(p->range_tr, range_count, &nel);
+	rc = hashtab_map(p->range_tr, hashtab_cnt, &nel);
 	if (rc)
 		return rc;
 
@@ -3110,43 +3185,60 @@ static int range_write(struct policydb *p, void *fp)
 	return 0;
 }
 
-static int filename_trans_write(struct policydb *p, void *fp)
+static int filename_write_helper(void *key, void *data, void *ptr)
 {
-	struct filename_trans *ft;
-	u32 len, nel = 0;
 	__le32 buf[4];
+	struct filename_trans *ft = key;
+	struct filename_trans_datum *otype = data;
+	void *fp = ptr;
 	int rc;
+	u32 len;
 
-	for (ft = p->filename_trans; ft; ft = ft->next)
-		nel++;
-
-	buf[0] = cpu_to_le32(nel);
+	len = strlen(ft->name);
+	buf[0] = cpu_to_le32(len);
 	rc = put_entry(buf, sizeof(u32), 1, fp);
 	if (rc)
 		return rc;
 
-	for (ft = p->filename_trans; ft; ft = ft->next) {
-		len = strlen(ft->name);
-		buf[0] = cpu_to_le32(len);
-		rc = put_entry(buf, sizeof(u32), 1, fp);
-		if (rc)
-			return rc;
+	rc = put_entry(ft->name, sizeof(char), len, fp);
+	if (rc)
+		return rc;
 
-		rc = put_entry(ft->name, sizeof(char), len, fp);
-		if (rc)
-			return rc;
+	buf[0] = ft->stype;
+	buf[1] = ft->ttype;
+	buf[2] = ft->tclass;
+	buf[3] = otype->otype;
 
-		buf[0] = ft->stype;
-		buf[1] = ft->ttype;
-		buf[2] = ft->tclass;
-		buf[3] = ft->otype;
+	rc = put_entry(buf, sizeof(u32), 4, fp);
+	if (rc)
+		return rc;
 
-		rc = put_entry(buf, sizeof(u32), 4, fp);
-		if (rc)
-			return rc;
-	}
 	return 0;
 }
+
+static int filename_trans_write(struct policydb *p, void *fp)
+{
+	u32 nel;
+	__le32 buf[1];
+	int rc;
+
+	nel = 0;
+	rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
+	if (rc)
+		return rc;
+
+	buf[0] = cpu_to_le32(nel);
+	rc = put_entry(buf, sizeof(u32), 1, fp);
+	if (rc)
+		return rc;
+
+	rc = hashtab_map(p->filename_trans, filename_write_helper, fp);
+	if (rc)
+		return rc;
+
+	return 0;
+}
+
 /*
  * Write the configuration data in a policy database
  * structure to a policy database binary representation
@@ -3249,7 +3341,7 @@ int policydb_write(struct policydb *p, void *fp)
 	if (rc)
 		return rc;
 
-	rc = role_trans_write(p->role_tr, fp);
+	rc = role_trans_write(p, fp);
 	if (rc)
 		return rc;
 
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index 732ea4a..b846c03 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -72,17 +72,20 @@ struct role_datum {
 
 struct role_trans {
 	u32 role;		/* current role */
-	u32 type;		/* program executable type */
+	u32 type;		/* program executable type, or new object type */
+	u32 tclass;		/* process class, or new object class */
 	u32 new_role;		/* new role */
 	struct role_trans *next;
 };
 
 struct filename_trans {
-	struct filename_trans *next;
 	u32 stype;		/* current process */
 	u32 ttype;		/* parent dir context */
 	u16 tclass;		/* class of new object */
 	const char *name;	/* last path component */
+};
+
+struct filename_trans_datum {
 	u32 otype;		/* expected of new object */
 };
 
@@ -227,7 +230,10 @@ struct policydb {
 	struct role_trans *role_tr;
 
 	/* file transitions with the last path component */
-	struct filename_trans *filename_trans;
+	/* quickly exclude lookups when parent ttype has no rules */
+	struct ebitmap filename_trans_ttypes;
+	/* actual set of filename_trans rules */
+	struct hashtab *filename_trans;
 
 	/* bools indexed by (value - 1) */
 	struct cond_bool_datum **bool_val_to_struct;
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 6ef4af4..c3e4b52 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1359,26 +1359,35 @@ out:
 }
 
 static void filename_compute_type(struct policydb *p, struct context *newcontext,
-				  u32 scon, u32 tcon, u16 tclass,
-				  const struct qstr *qstr)
-{
-	struct filename_trans *ft;
-	for (ft = p->filename_trans; ft; ft = ft->next) {
-		if (ft->stype == scon &&
-		    ft->ttype == tcon &&
-		    ft->tclass == tclass &&
-		    !strcmp(ft->name, qstr->name)) {
-			newcontext->type = ft->otype;
-			return;
-		}
-	}
+				  u32 stype, u32 ttype, u16 tclass,
+				  const char *objname)
+{
+	struct filename_trans ft;
+	struct filename_trans_datum *otype;
+
+	/*
+	 * Most filename trans rules are going to live in specific directories
+	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
+	 * if the ttype does not contain any rules.
+	 */
+	if (!ebitmap_get_bit(&p->filename_trans_ttypes, ttype))
+		return;
+
+	ft.stype = stype;
+	ft.ttype = ttype;
+	ft.tclass = tclass;
+	ft.name = objname;
+
+	otype = hashtab_search(p->filename_trans, &ft);
+	if (otype)
+		newcontext->type = otype->otype;
 }
 
 static int security_compute_sid(u32 ssid,
 				u32 tsid,
 				u16 orig_tclass,
 				u32 specified,
-				const struct qstr *qstr,
+				const char *objname,
 				u32 *out_sid,
 				bool kern)
 {
@@ -1478,23 +1487,21 @@ static int security_compute_sid(u32 ssid,
 		newcontext.type = avdatum->data;
 	}
 
-	/* if we have a qstr this is a file trans check so check those rules */
-	if (qstr)
+	/* if we have a objname this is a file trans check so check those rules */
+	if (objname)
 		filename_compute_type(&policydb, &newcontext, scontext->type,
-				      tcontext->type, tclass, qstr);
+				      tcontext->type, tclass, objname);
 
 	/* Check for class-specific changes. */
-	if  (tclass == policydb.process_class) {
-		if (specified & AVTAB_TRANSITION) {
-			/* Look for a role transition rule. */
-			for (roletr = policydb.role_tr; roletr;
-			     roletr = roletr->next) {
-				if (roletr->role == scontext->role &&
-				    roletr->type == tcontext->type) {
-					/* Use the role transition rule. */
-					newcontext.role = roletr->new_role;
-					break;
-				}
+	if (specified & AVTAB_TRANSITION) {
+		/* Look for a role transition rule. */
+		for (roletr = policydb.role_tr; roletr; roletr = roletr->next) {
+			if ((roletr->role == scontext->role) &&
+			    (roletr->type == tcontext->type) &&
+			    (roletr->tclass == tclass)) {
+				/* Use the role transition rule. */
+				newcontext.role = roletr->new_role;
+				break;
 			}
 		}
 	}
@@ -1541,13 +1548,14 @@ int security_transition_sid(u32 ssid, u32 tsid, u16 tclass,
 			    const struct qstr *qstr, u32 *out_sid)
 {
 	return security_compute_sid(ssid, tsid, tclass, AVTAB_TRANSITION,
-				    qstr, out_sid, true);
+				    qstr ? qstr->name : NULL, out_sid, true);
 }
 
-int security_transition_sid_user(u32 ssid, u32 tsid, u16 tclass, u32 *out_sid)
+int security_transition_sid_user(u32 ssid, u32 tsid, u16 tclass,
+				 const char *objname, u32 *out_sid)
 {
 	return security_compute_sid(ssid, tsid, tclass, AVTAB_TRANSITION,
-				    NULL, out_sid, false);
+				    objname, out_sid, false);
 }
 
 /**
@@ -3190,7 +3198,7 @@ out:
  * @len: length of data in bytes
  *
  */
-int security_read_policy(void **data, ssize_t *len)
+int security_read_policy(void **data, size_t *len)
 {
 	int rc;
 	struct policy_file fp;