Update Xen Flask module to policy.24.

This is a back-port of the latest SELinux code to Xen, adjusted
for Xen coding style and interfaces.  Unneeded functionality such
as most object context config data, handle_unknown, MLS field
defaulting, etc has been omitted.

Signed-off-by:  Stephen D. Smalley <sds@tycho.nsa.gov>
Signed-off-by: George S. Coker, II <gscoker@alpha.ncsc.mil>

21 files changed, 1431 insertions, 726 deletions

diff --git a/tools/flask/policy/Makefile b/tools/flask/policy/Makefile
index df25dd8d4a..93afe44311 100644
--- a/tools/flask/policy/Makefile
+++ b/tools/flask/policy/Makefile
@@ -20,7 +20,7 @@
 # By default, checkpolicy will create the highest
 # version policy it supports.  Setting this will
 # override the version.
-OUTPUT_POLICY = 20
+#OUTPUT_POLICY = 20
 
 # Policy Type
 # strict, targeted,
diff --git a/xen/xsm/flask/avc.c b/xen/xsm/flask/avc.c
index 5b4302157d..ade2dd97b9 100644
--- a/xen/xsm/flask/avc.c
+++ b/xen/xsm/flask/avc.c
@@ -32,12 +32,7 @@
 #include "avc.h"
 #include "avc_ss.h"
 
-static const struct av_perm_to_string
-{
-    u16 tclass;
-    u32 value;
-    const char *name;
-} av_perm_to_string[] = {
+static const struct av_perm_to_string av_perm_to_string[] = {
 #define S_(c, v, s) { c, v, s },
 #include "av_perm_to_string.h"
 #undef S_
@@ -57,17 +52,22 @@ static const char *class_to_string[] = {
 #undef TE_
 #undef S_
 
-static const struct av_inherit
-{
-    u16 tclass;
-    const char **common_pts;
-    u32 common_base;
-} av_inherit[] = {
-#define S_(c, i, b) { c, common_##i##_perm_to_string, b },
+static const struct av_inherit av_inherit[] = {
+#define S_(c, i, b) { .tclass = c, .common_pts = common_##i##_perm_to_string, \
+		      .common_base = b },
 #include "av_inherit.h"
 #undef S_
 };
 
+const struct selinux_class_perm selinux_class_perm = {
+	.av_perm_to_string = av_perm_to_string,
+	.av_pts_len = ARRAY_SIZE(av_perm_to_string),
+	.class_to_string = class_to_string,
+	.cts_len = ARRAY_SIZE(class_to_string),
+	.av_inherit = av_inherit,
+	.av_inherit_len = ARRAY_SIZE(av_inherit)
+};
+
 #define AVC_CACHE_SLOTS            512
 #define AVC_DEF_CACHE_THRESHOLD        512
 #define AVC_CACHE_RECLAIM        16
@@ -86,17 +86,16 @@ struct avc_entry {
     u32            tsid;
     u16            tclass;
     struct av_decision    avd;
-    atomic_t        used;    /* used recently */
 };
 
 struct avc_node {
     struct avc_entry    ae;
-    struct list_head    list;
+    struct hlist_node   list; /* anchored in avc_cache->slots[i] */
     struct rcu_head     rhead;
 };
 
 struct avc_cache {
-    struct list_head    slots[AVC_CACHE_SLOTS];
+    struct hlist_head    slots[AVC_CACHE_SLOTS]; /* head for avc_node->list */
     spinlock_t        slots_lock[AVC_CACHE_SLOTS]; /* lock for writes */
     atomic_t        lru_hint;    /* LRU hint for reclaim scan */
     atomic_t        active_nodes;
@@ -241,7 +240,7 @@ void __init avc_init(void)
 
     for ( i = 0; i < AVC_CACHE_SLOTS; i++ )
     {
-        INIT_LIST_HEAD(&avc_cache.slots[i]);
+        INIT_HLIST_HEAD(&avc_cache.slots[i]);
         spin_lock_init(&avc_cache.slots_lock[i]);
     }
     atomic_set(&avc_cache.active_nodes, 0);
@@ -254,6 +253,7 @@ int avc_get_hash_stats(char *buf, uint32_t size)
 {
     int i, chain_len, max_chain_len, slots_used;
     struct avc_node *node;
+    struct hlist_head *head;
 
     rcu_read_lock();
 
@@ -261,11 +261,14 @@ int avc_get_hash_stats(char *buf, uint32_t size)
     max_chain_len = 0;
     for ( i = 0; i < AVC_CACHE_SLOTS; i++ )
     {
-        if ( !list_empty(&avc_cache.slots[i]) )
+        head = &avc_cache.slots[i];
+        if ( !hlist_empty(head) )
         {
+	    struct hlist_node *next;
+
             slots_used++;
             chain_len = 0;
-            list_for_each_entry_rcu(node, &avc_cache.slots[i], list)
+            hlist_for_each_entry_rcu(node, next, head, list)
                 chain_len++;
             if ( chain_len > max_chain_len )
                 max_chain_len = chain_len;
@@ -289,7 +292,7 @@ static void avc_node_free(struct rcu_head *rhead)
 
 static void avc_node_delete(struct avc_node *node)
 {
-    list_del_rcu(&node->list);
+    hlist_del_rcu(&node->list);
     call_rcu(&node->rhead, avc_node_free);
     atomic_dec(&avc_cache.active_nodes);
 }
@@ -303,7 +306,7 @@ static void avc_node_kill(struct avc_node *node)
 
 static void avc_node_replace(struct avc_node *new, struct avc_node *old)
 {
-    list_replace_rcu(&old->list, &new->list);
+    hlist_replace_rcu(&old->list, &new->list);
     call_rcu(&old->rhead, avc_node_free);
     atomic_dec(&avc_cache.active_nodes);
 }
@@ -312,31 +315,34 @@ static inline int avc_reclaim_node(void)
 {
     struct avc_node *node;
     int hvalue, try, ecx;
-	unsigned long flags;
+    unsigned long flags;
+    struct hlist_head *head;
+    struct hlist_node *next;
+    spinlock_t *lock;
 
     for ( try = 0, ecx = 0; try < AVC_CACHE_SLOTS; try++ )
     {
         atomic_inc(&avc_cache.lru_hint);
         hvalue =  atomic_read(&avc_cache.lru_hint) & (AVC_CACHE_SLOTS - 1);
+        head = &avc_cache.slots[hvalue];
+        lock = &avc_cache.slots_lock[hvalue];
 
-		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flags);
-
-        list_for_each_entry(node, &avc_cache.slots[hvalue], list)
+        spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flags);
+        rcu_read_lock();
+        hlist_for_each_entry(node, next, head, list)
         {
-            if ( atomic_dec_and_test(&node->ae.used) )
-            {
-                /* Recently Unused */
                 avc_node_delete(node);
                 avc_cache_stats_incr(reclaims);
                 ecx++;
                 if ( ecx >= AVC_CACHE_RECLAIM )
                 {
-					spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
-                    goto out;
+		  rcu_read_unlock();
+		  spin_unlock_irqrestore(lock, flags);
+		  goto out;
                 }
-            }
         }
-		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flags);
+        rcu_read_unlock();
+        spin_unlock_irqrestore(lock, flags);
     }    
 out:
     return ecx;
@@ -352,8 +358,7 @@ static struct avc_node *avc_alloc_node(void)
 
     memset(node, 0, sizeof(*node));
     INIT_RCU_HEAD(&node->rhead);
-    INIT_LIST_HEAD(&node->list);
-    atomic_set(&node->ae.used, 1);
+    INIT_HLIST_NODE(&node->list);
     avc_cache_stats_incr(allocations);
 
     atomic_inc(&avc_cache.active_nodes);
@@ -364,40 +369,35 @@ out:
     return node;
 }
 
-static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
+static void avc_node_populate(struct avc_node *node, u32 ssid, u32 tsid,
+                              u16 tclass, struct av_decision *avd)
 {
     node->ae.ssid = ssid;
     node->ae.tsid = tsid;
     node->ae.tclass = tclass;
-    memcpy(&node->ae.avd, &ae->avd, sizeof(node->ae.avd));
+    memcpy(&node->ae.avd, avd, sizeof(node->ae.avd));
 }
 
 static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
 {
     struct avc_node *node, *ret = NULL;
     int hvalue;
+    struct hlist_head *head;
+    struct hlist_node *next;
 
     hvalue = avc_hash(ssid, tsid, tclass);
-    list_for_each_entry_rcu(node, &avc_cache.slots[hvalue], list)
+    head = &avc_cache.slots[hvalue];
+    hlist_for_each_entry_rcu(node, next, head, list)
     {
-        if ( ssid == node->ae.ssid && tclass == node->ae.tclass && 
-                                                        tsid == node->ae.tsid )
+        if ( ssid == node->ae.ssid &&
+	     tclass == node->ae.tclass &&
+	     tsid == node->ae.tsid )
         {
             ret = node;
             break;
         }
     }
 
-    if ( ret == NULL )
-    {
-        /* cache miss */
-        goto out;
-    }
-
-    /* cache hit */
-    if ( atomic_read(&ret->ae.used) != 1 )
-        atomic_set(&ret->ae.used, 1);
-out:
     return ret;
 }
 
@@ -415,22 +415,18 @@ out:
  * then this function return the avc_node.
  * Otherwise, this function returns NULL.
  */
-static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass, u32 requested)
+static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass)
 {
     struct avc_node *node;
 
     avc_cache_stats_incr(lookups);
     node = avc_search_node(ssid, tsid, tclass);
 
-    if ( node && ((node->ae.avd.decided & requested) == requested) )
-    {
+    if ( node )
         avc_cache_stats_incr(hits);
-        goto out;
-    }
+    else
+        avc_cache_stats_incr(misses);
 
-    node = NULL;
-    avc_cache_stats_incr(misses);
-out:
     return node;
 }
 
@@ -477,34 +473,43 @@ static int avc_latest_notif_update(int seqno, int is_insert)
  * the access vectors into a cache entry, returns
  * avc_node inserted. Otherwise, this function returns NULL.
  */
-static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass, struct avc_entry *ae)
+static struct avc_node *avc_insert(u32 ssid, u32 tsid, u16 tclass,
+                                   struct av_decision *avd)
 {
     struct avc_node *pos, *node = NULL;
     int hvalue;
-	unsigned long flag;
+    unsigned long flag;
 
-    if ( avc_latest_notif_update(ae->avd.seqno, 1) )
+    if ( avc_latest_notif_update(avd->seqno, 1) )
         goto out;
 
     node = avc_alloc_node();
     if ( node )
     {
+        struct hlist_head *head;
+        struct hlist_node *next;
+        spinlock_t *lock;
+
         hvalue = avc_hash(ssid, tsid, tclass);
-        avc_node_populate(node, ssid, tsid, tclass, ae);
+        avc_node_populate(node, ssid, tsid, tclass, avd);
 
-		spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
-        list_for_each_entry(pos, &avc_cache.slots[hvalue], list)
+        head = &avc_cache.slots[hvalue];
+        lock = &avc_cache.slots_lock[hvalue];
+
+        spin_lock_irqsave(lock, flag);
+        hlist_for_each_entry(pos, next, head, list)
         {
-            if ( pos->ae.ssid == ssid && pos->ae.tsid == tsid &&
-                                                    pos->ae.tclass == tclass )
+            if ( pos->ae.ssid == ssid &&
+                 pos->ae.tsid == tsid &&
+                 pos->ae.tclass == tclass )
             {
                 avc_node_replace(node, pos);
                 goto found;
             }
         }
-        list_add_rcu(&node->list, &avc_cache.slots[hvalue]);
+        hlist_add_head_rcu(&node->list, head);
 found:
-		spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
+        spin_unlock_irqrestore(lock, flag);
     }
 out:
     return node;
@@ -622,11 +627,15 @@ static inline int avc_sidcmp(u32 x, u32 y)
  * otherwise, this function update the AVC entry. The original AVC-entry object
  * will release later by RCU.
  */
-static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass)
+static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass,
+			   u32 seqno)
 {
     int hvalue, rc = 0;
-	unsigned long flag;
+    unsigned long flag;
     struct avc_node *pos, *node, *orig = NULL;
+    struct hlist_head *head;
+    struct hlist_node *next;
+    spinlock_t *lock;
     
     node = avc_alloc_node();
     if ( !node )
@@ -636,12 +645,18 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass)
     }
 
     hvalue = avc_hash(ssid, tsid, tclass);    
-	spin_lock_irqsave(&avc_cache.slots_lock[hvalue], flag);
 
-    list_for_each_entry(pos, &avc_cache.slots[hvalue], list)
+    head = &avc_cache.slots[hvalue];
+    lock = &avc_cache.slots_lock[hvalue];
+
+    spin_lock_irqsave(lock, flag);
+
+    hlist_for_each_entry(pos, next, head, list)
     {
-        if ( ssid==pos->ae.ssid && tsid==pos->ae.tsid &&
-                                                        tclass==pos->ae.tclass )
+        if ( ssid == pos->ae.ssid &&
+	     tsid == pos->ae.tsid &&
+	     tclass == pos->ae.tclass &&
+	     seqno == pos->ae.avd.seqno )
         {
             orig = pos;
             break;
@@ -659,7 +674,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass)
      * Copy and replace original node.
      */
 
-    avc_node_populate(node, ssid, tsid, tclass, &orig->ae);
+    avc_node_populate(node, ssid, tsid, tclass, &orig->ae.avd);
 
     switch ( event )
     {
@@ -685,7 +700,7 @@ static int avc_update_node(u32 event, u32 perms, u32 ssid, u32 tsid, u16 tclass)
     }
     avc_node_replace(node, orig);
 out_unlock:
-	spin_unlock_irqrestore(&avc_cache.slots_lock[hvalue], flag);
+    spin_unlock_irqrestore(lock, flag);
 out:
     return rc;
 }
@@ -697,31 +712,40 @@ out:
 int avc_ss_reset(u32 seqno)
 {
     struct avc_callback_node *c;
-    int i, rc = 0;
-	unsigned long flag;
+    int i, rc = 0, tmprc;
+    unsigned long flag;
     struct avc_node *node;
+    struct hlist_head *head;
+    struct hlist_node *next;
+    spinlock_t *lock;
 
     for ( i = 0; i < AVC_CACHE_SLOTS; i++ )
     {
-		spin_lock_irqsave(&avc_cache.slots_lock[i], flag);
-        list_for_each_entry(node, &avc_cache.slots[i], list)
+        head = &avc_cache.slots[i];
+        lock = &avc_cache.slots_lock[i];
+
+        spin_lock_irqsave(lock, flag);
+        rcu_read_lock();
+        hlist_for_each_entry(node, next, head, list)
             avc_node_delete(node);
-		spin_unlock_irqrestore(&avc_cache.slots_lock[i], flag);
+        rcu_read_unlock();
+        spin_unlock_irqrestore(lock, flag);
     }
     
     for ( c = avc_callbacks; c; c = c->next )
     {
         if ( c->events & AVC_CALLBACK_RESET )
         {
-            rc = c->callback(AVC_CALLBACK_RESET,
-                     0, 0, 0, 0, NULL);
-            if ( rc )
-                goto out;
+            tmprc = c->callback(AVC_CALLBACK_RESET,
+                                0, 0, 0, 0, NULL);
+            /* save the first error encountered for the return
+               value and continue processing the callbacks */
+            if ( !rc )
+                rc = tmprc;
         }
     }
 
     avc_latest_notif_update(seqno, 0);
-out:
     return rc;
 }
 
@@ -745,41 +769,47 @@ out:
  * should be released for the auditing.
  */
 int avc_has_perm_noaudit(u32 ssid, u32 tsid, u16 tclass, u32 requested,
-                                                     struct av_decision *avd)
+                         struct av_decision *in_avd)
 {
     struct avc_node *node;
-    struct avc_entry entry, *p_ae;
+    struct av_decision avd_entry, *avd;
     int rc = 0;
     u32 denied;
 
+    BUG_ON(!requested);
+
     rcu_read_lock();
 
-    node = avc_lookup(ssid, tsid, tclass, requested);
+    node = avc_lookup(ssid, tsid, tclass);
     if ( !node )
     {
         rcu_read_unlock();
-        rc = security_compute_av(ssid,tsid,tclass,requested,&entry.avd);
+
+        if ( in_avd )
+            avd = in_avd;
+        else
+            avd = &avd_entry;
+
+        rc = security_compute_av(ssid,tsid,tclass,requested,avd);
         if ( rc )
             goto out;
         rcu_read_lock();
-        node = avc_insert(ssid,tsid,tclass,&entry);
+        node = avc_insert(ssid,tsid,tclass,avd);
+    } else {
+        if ( in_avd )
+            memcpy(in_avd, &node->ae.avd, sizeof(*in_avd));
+        avd = &node->ae.avd;
     }
 
-    p_ae = node ? &node->ae : &entry;
+    denied = requested & ~(avd->allowed);
 
-    if ( avd )
-        memcpy(avd, &p_ae->avd, sizeof(*avd));
-
-    denied = requested & ~(p_ae->avd.allowed);
-
-    if ( !requested || denied )
+    if ( denied )
     {
-        if ( flask_enforcing )
-            rc = -EACCES;
+        if ( !flask_enforcing || (avd->flags & AVD_FLAGS_PERMISSIVE) )
+            avc_update_node(AVC_CALLBACK_GRANT,requested,
+                            ssid,tsid,tclass,avd->seqno);
         else
-            if ( node )
-                avc_update_node(AVC_CALLBACK_GRANT,requested,
-                        ssid,tsid,tclass);
+            rc = -EACCES;
     }
 
     rcu_read_unlock();
diff --git a/xen/xsm/flask/flask_op.c b/xen/xsm/flask/flask_op.c
index 3b583d122c..6d8faaf50c 100644
--- a/xen/xsm/flask/flask_op.c
+++ b/xen/xsm/flask/flask_op.c
@@ -346,7 +346,7 @@ static int flask_security_access(char *buf, uint32_t size)
 
     memset(buf, 0, size);
     length = snprintf(buf, size, "%x %x %x %x %u", 
-                                        avd.allowed, avd.decided,
+                                        avd.allowed, 0xffffffff,
                                         avd.auditallow, avd.auditdeny, 
                                         avd.seqno);
                 
diff --git a/xen/xsm/flask/include/avc_ss.h b/xen/xsm/flask/include/avc_ss.h
index 87af465c9e..ea4e98c47e 100644
--- a/xen/xsm/flask/include/avc_ss.h
+++ b/xen/xsm/flask/include/avc_ss.h
@@ -10,5 +10,28 @@
 
 int avc_ss_reset(u32 seqno);
 
+struct av_perm_to_string {
+    u16 tclass;
+    u32 value;
+    const char *name;
+};
+
+struct av_inherit {
+    const char **common_pts;
+    u32 common_base;
+    u16 tclass;
+};
+
+struct selinux_class_perm {
+    const struct av_perm_to_string *av_perm_to_string;
+    u32 av_pts_len;
+    u32 cts_len;
+    const char **class_to_string;
+    const struct av_inherit *av_inherit;
+    u32 av_inherit_len;
+};
+
+extern const struct selinux_class_perm selinux_class_perm;
+
 #endif /* _FLASK_AVC_SS_H_ */
 
diff --git a/xen/xsm/flask/include/security.h b/xen/xsm/flask/include/security.h
index 37c9913988..149caf753c 100644
--- a/xen/xsm/flask/include/security.h
+++ b/xen/xsm/flask/include/security.h
@@ -26,10 +26,14 @@
 #define POLICYDB_VERSION_VALIDATETRANS    19
 #define POLICYDB_VERSION_MLS        19
 #define POLICYDB_VERSION_AVTAB        20
+#define POLICYDB_VERSION_RANGETRANS	21
+#define POLICYDB_VERSION_POLCAP		22
+#define POLICYDB_VERSION_PERMISSIVE	23
+#define POLICYDB_VERSION_BOUNDARY	24
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN   POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_AVTAB
+#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_BOUNDARY
 
 #ifdef FLASK_BOOTPARAM
 extern int flask_enabled;
@@ -43,12 +47,15 @@ int security_load_policy(void * data, size_t len);
 
 struct av_decision {
     u32 allowed;
-    u32 decided;
     u32 auditallow;
     u32 auditdeny;
     u32 seqno;
+    u32 flags;
 };
 
+/* definitions of av_decision.flags */
+#define AVD_FLAGS_PERMISSIVE	0x0001
+
 int security_compute_av(u32 ssid, u32 tsid, u16 tclass, u32 requested,
                                                     struct av_decision *avd);
 
@@ -62,9 +69,6 @@ int security_sid_to_context(u32 sid, char **scontext, u32 *scontext_len);
 
 int security_context_to_sid(char *scontext, u32 scontext_len, u32 *out_sid);
 
-int security_context_to_sid_default(char *scontext, u32 scontext_len, 
-                                                    u32 *out_sid, u32 def_sid);
-
 int security_get_user_sids(u32 callsid, char *username, u32 **sids, u32 *nel);
 
 int security_pirq_sid(int pirq, u32 *out_sid);
diff --git a/xen/xsm/flask/ss/avtab.c b/xen/xsm/flask/ss/avtab.c
index d2e902c9c5..47912e9480 100644
--- a/xen/xsm/flask/ss/avtab.c
+++ b/xen/xsm/flask/ss/avtab.c
@@ -12,6 +12,9 @@
  *    This program is free software; you can redistribute it and/or modify
  *      it under the terms of the GNU General Public License as published by
  *    the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ *	Tuned number of hash slots for avtab to reduce memory usage
  */
 
 /* Ported to Xen 3.0, George Coker, <gscoker@alpha.ncsc.mil> */
@@ -25,11 +28,11 @@
 #include "avtab.h"
 #include "policydb.h"
 
-#define AVTAB_HASH(keyp) \
-((keyp->target_class + \
- (keyp->target_type << 2) + \
- (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
+{
+    return ((keyp->target_class + (keyp->target_type << 2) +
+             (keyp->source_type << 9)) & mask);
+}
 
 static struct avtab_node* avtab_insert_node(struct avtab *h, int hvalue,
     struct avtab_node * prev, struct avtab_node * cur, struct avtab_key *key, 
@@ -64,10 +67,10 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key,
     struct avtab_node *prev, *cur, *newnode;
     u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-    if ( !h )
+    if ( !h || !h->htable )
         return -EINVAL;
 
-    hvalue = AVTAB_HASH(key);
+    hvalue = avtab_hash(key, h->mask);
     for ( prev = NULL, cur = h->htable[hvalue]; cur;
                                                     prev = cur, cur = cur->next)
     {
@@ -105,9 +108,9 @@ struct avtab_node * avtab_insert_nonunique(struct avtab * h,
     struct avtab_node *prev, *cur, *newnode;
     u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-    if ( !h )
+    if ( !h || !h->htable )
         return NULL;
-    hvalue = AVTAB_HASH(key);
+    hvalue = avtab_hash(key, h->mask);
     for ( prev = NULL, cur = h->htable[hvalue]; cur; 
                                                 prev = cur, cur = cur->next )
     {
@@ -137,10 +140,10 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
     struct avtab_node *cur;
     u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-    if ( !h )
+    if ( !h || !h->htable )
         return NULL;
 
-    hvalue = AVTAB_HASH(key);
+    hvalue = avtab_hash(key, h->mask);
     for ( cur = h->htable[hvalue]; cur; cur = cur->next )
     {
         if ( key->source_type == cur->key.source_type &&
@@ -172,10 +175,10 @@ struct avtab_node* avtab_search_node(struct avtab *h, struct avtab_key *key)
     struct avtab_node *cur;
     u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
-    if ( !h )
+    if ( !h || !h->htable )
         return NULL;
 
-    hvalue = AVTAB_HASH(key);
+    hvalue = avtab_hash(key, h->mask);
     for ( cur = h->htable[hvalue]; cur; cur = cur->next )
     {
         if ( key->source_type == cur->key.source_type &&
@@ -235,7 +238,7 @@ void avtab_destroy(struct avtab *h)
     if ( !h || !h->htable )
         return;
 
-    for ( i = 0; i < AVTAB_SIZE; i++ )
+    for ( i = 0; i < h->nslot; i++ )
     {
         cur = h->htable[i];
         while ( cur != NULL )
@@ -248,19 +251,52 @@ void avtab_destroy(struct avtab *h)
     }
     xfree(h->htable);
     h->htable = NULL;
+    h->nslot = 0;
+    h->mask = 0;
 }
 
-
 int avtab_init(struct avtab *h)
 {
+    h->htable = NULL;
+    h->nel = 0;
+    return 0;
+}
+
+int avtab_alloc(struct avtab *h, u32 nrules)
+{
+    u16 mask = 0;
+    u32 shift = 0;
+    u32 work = nrules;
+    u32 nslot = 0;
     int i;
 
-    h->htable = (void *)xmalloc_array(struct avtab_node, AVTAB_SIZE);
+    if ( nrules == 0 )
+        goto avtab_alloc_out;
+
+    while ( work )
+    {
+        work  = work >> 1;
+        shift++;
+	}
+	if ( shift > 2 )
+        shift = shift - 2;
+    nslot = 1 << shift;
+    if ( nslot > MAX_AVTAB_SIZE )
+        nslot = MAX_AVTAB_SIZE;
+    mask = nslot - 1;
+
+    h->htable = xmalloc_array(struct avtab_node *, nslot);
     if ( !h->htable )
         return -ENOMEM;
-    for ( i = 0; i < AVTAB_SIZE; i++ )
+    for ( i = 0; i < nslot; i++ )
         h->htable[i] = NULL;
+
+avtab_alloc_out:
     h->nel = 0;
+    h->nslot = nslot;
+    h->mask = mask;
+    printk(KERN_DEBUG "Flask: %d avtab hash slots, %d rules.\n",
+           h->nslot, nrules);
     return 0;
 }
 
@@ -271,7 +307,7 @@ void avtab_hash_eval(struct avtab *h, char *tag)
 
     slots_used = 0;
     max_chain_len = 0;
-    for ( i = 0; i < AVTAB_SIZE; i++ )
+    for ( i = 0; i < h->nslot; i++ )
     {
         cur = h->htable[i];
         if ( cur )
@@ -290,7 +326,7 @@ void avtab_hash_eval(struct avtab *h, char *tag)
     }
 
     printk(KERN_INFO "%s:  %d entries and %d/%d buckets used, longest "
-           "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
+           "chain length %d\n", tag, h->nel, slots_used, h->nslot,
                                                                max_chain_len);
 }
 
@@ -303,17 +339,18 @@ static uint16_t spec_order[] = {
     AVTAB_MEMBER
 };
 
-int avtab_read_item(void *fp, u32 vers, struct avtab *a,
+int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
                             int (*insertf)(struct avtab *a, struct avtab_key *k,
                                     struct avtab_datum *d, void *p), void *p)
 {
     __le16 buf16[4];
     u16 enabled;
     __le32 buf32[7];
-    u32 items, items2, val;
+    u32 items, items2, val, vers = pol->policyvers;
     struct avtab_key key;
     struct avtab_datum datum;
     int i, rc;
+    unsigned set;
 
     memset(&key, 0, sizeof(struct avtab_key));
     memset(&datum, 0, sizeof(struct avtab_datum));
@@ -323,20 +360,20 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
         rc = next_entry(buf32, fp, sizeof(u32));
         if ( rc < 0 )
         {
-            printk(KERN_ERR "security: avtab: truncated entry\n");
+            printk(KERN_ERR "Flask: avtab: truncated entry\n");
             return -1;
         }
         items2 = le32_to_cpu(buf32[0]);
         if ( items2 > ARRAY_SIZE(buf32) )
         {
-            printk(KERN_ERR "security: avtab: entry overflow\n");
+            printk(KERN_ERR "Flask: avtab: entry overflow\n");
             return -1;
 
         }
         rc = next_entry(buf32, fp, sizeof(u32)*items2);
         if ( rc < 0 )
         {
-            printk(KERN_ERR "security: avtab: truncated entry\n");
+            printk(KERN_ERR "Flask: avtab: truncated entry\n");
             return -1;
         }
         items = 0;
@@ -345,21 +382,21 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
         key.source_type = (u16)val;
         if ( key.source_type != val )
         {
-            printk("security: avtab: truncated source type\n");
+            printk("Flask: avtab: truncated source type\n");
             return -1;
         }
         val = le32_to_cpu(buf32[items++]);
         key.target_type = (u16)val;
         if ( key.target_type != val )
         {
-            printk("security: avtab: truncated target type\n");
+            printk("Flask: avtab: truncated target type\n");
             return -1;
         }
         val = le32_to_cpu(buf32[items++]);
         key.target_class = (u16)val;
         if ( key.target_class != val )
         {
-            printk("security: avtab: truncated target class\n");
+            printk("Flask: avtab: truncated target class\n");
             return -1;
         }
 
@@ -368,12 +405,12 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
 
         if ( !(val & (AVTAB_AV | AVTAB_TYPE)) )
         {
-            printk("security: avtab: null entry\n");
+            printk("Flask: avtab: null entry\n");
             return -1;
         }
         if ( (val & AVTAB_AV) && (val & AVTAB_TYPE) )
         {
-            printk("security: avtab: entry has both access vectors and types\n");
+            printk("Flask: avtab: entry has both access vectors and types\n");
             return -1;
         }
 
@@ -390,7 +427,7 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
         }
 
         if ( items != items2 ) {
-            printk("security: avtab: entry only had %d items, expected %d\n", 
+            printk("Flask: avtab: entry only had %d items, expected %d\n",
                                                                 items2, items);
             return -1;
         }
@@ -400,7 +437,7 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
     rc = next_entry(buf16, fp, sizeof(u16)*4);
     if ( rc < 0 )
     {
-        printk("security: avtab: truncated entry\n");
+        printk("Flask: avtab: truncated entry\n");
         return -1;
     }
 
@@ -410,13 +447,39 @@ int avtab_read_item(void *fp, u32 vers, struct avtab *a,
     key.target_class = le16_to_cpu(buf16[items++]);
     key.specified = le16_to_cpu(buf16[items++]);
 
+    if ( !policydb_type_isvalid(pol, key.source_type) ||
+         !policydb_type_isvalid(pol, key.target_type) ||
+         !policydb_class_isvalid(pol, key.target_class) )
+    {
+        printk(KERN_ERR "Flask: avtab: invalid type or class\n");
+        return -1;
+    }
+
+    set = 0;
+    for ( i = 0; i < ARRAY_SIZE(spec_order); i++ )
+    {
+        if ( key.specified & spec_order[i] )
+            set++;
+    }
+    if ( !set || set > 1 )
+    {
+        printk(KERN_ERR "Flask:  avtab:  more than one specifier\n");
+        return -1;
+    }
+
     rc = next_entry(buf32, fp, sizeof(u32));
     if ( rc < 0 )
     {
-        printk("security: avtab: truncated entry\n");
+        printk("Flask: avtab: truncated entry\n");
         return -1;
     }
     datum.data = le32_to_cpu(*buf32);
+    if ( (key.specified & AVTAB_TYPE) &&
+         !policydb_type_isvalid(pol, datum.data) )
+    {
+        printk(KERN_ERR "Flask: avtab: invalid type\n");
+        return -1;
+    }
     return insertf(a, &key, &datum, p);
 }
 
@@ -426,7 +489,7 @@ static int avtab_insertf(struct avtab *a, struct avtab_key *k,
     return avtab_insert(a, k, d);
 }
 
-int avtab_read(struct avtab *a, void *fp, u32 vers)
+int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
 {
     int rc;
     __le32 buf[1];
@@ -435,25 +498,28 @@ int avtab_read(struct avtab *a, void *fp, u32 vers)
     rc = next_entry(buf, fp, sizeof(u32));
     if ( rc < 0 )
     {
-        printk(KERN_ERR "security: avtab: truncated table\n");
+        printk(KERN_ERR "Flask: avtab: truncated table\n");
         goto bad;
     }
     nel = le32_to_cpu(buf[0]);
     if ( !nel )
     {
-        printk(KERN_ERR "security: avtab: table is empty\n");
+        printk(KERN_ERR "Flask: avtab: table is empty\n");
         rc = -EINVAL;
         goto bad;
     }
+    rc = avtab_alloc(a, nel);
+    if ( rc )
+        goto bad;
     for ( i = 0; i < nel; i++ )
     {
-        rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
+        rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
         if ( rc )
         {
             if ( rc == -ENOMEM )
-                printk(KERN_ERR "security: avtab: out of memory\n");
+                printk(KERN_ERR "Flask: avtab: out of memory\n");
             else if ( rc == -EEXIST )
-                printk(KERN_ERR "security: avtab: duplicate entry\n");
+                printk(KERN_ERR "Flask: avtab: duplicate entry\n");
             else
                 rc = -EINVAL;
             goto bad;
diff --git a/xen/xsm/flask/ss/avtab.h b/xen/xsm/flask/ss/avtab.h
index 78d0c0ac9a..a2b50c222a 100644
--- a/xen/xsm/flask/ss/avtab.h
+++ b/xen/xsm/flask/ss/avtab.h
@@ -16,6 +16,9 @@
  *    This program is free software; you can redistribute it and/or modify
  *      it under the terms of the GNU General Public License as published by
  *    the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ * 	Tuned number of hash slots for avtab to reduce memory usage
  */
 
 /* Ported to Xen 3.0, George Coker, <gscoker@alpha.ncsc.mil> */
@@ -53,19 +56,23 @@ struct avtab_node {
 struct avtab {
     struct avtab_node **htable;
     u32 nel;    /* number of elements */
+    u32 nslot;      /* number of hash slots */
+    u16 mask;       /* mask to compute hash func */
 };
 
 int avtab_init(struct avtab *);
+int avtab_alloc(struct avtab *, u32);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);
 
-int avtab_read_item(void *fp, uint32_t vers, struct avtab *a,
+struct policydb;
+int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
             int (*insert)(struct avtab *a, struct avtab_key *k,
                   struct avtab_datum *d, void *p),
             void *p);
 
-int avtab_read(struct avtab *a, void *fp, u32 vers);
+int avtab_read(struct avtab *a, void *fp, struct policydb *pol);
 
 struct avtab_node *avtab_insert_nonunique(struct avtab *h, 
                             struct avtab_key *key, struct avtab_datum *datum);
@@ -75,11 +82,10 @@ struct avtab_node *avtab_search_node(struct avtab *h, struct avtab_key *key);
 struct avtab_node *avtab_search_node_next(struct avtab_node *node, 
                                                                 int specified);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif    /* _SS_AVTAB_H_ */
 
diff --git a/xen/xsm/flask/ss/conditional.c b/xen/xsm/flask/ss/conditional.c
index a6444cbf0e..123d839eb2 100644
--- a/xen/xsm/flask/ss/conditional.c
+++ b/xen/xsm/flask/ss/conditional.c
@@ -101,7 +101,7 @@ int evaluate_cond_node(struct policydb *p, struct cond_node *node)
     {
         node->cur_state = new_state;
         if ( new_state == -1 )
-            printk(KERN_ERR "security: expression result was undefined - disabling all rules.\n");
+            printk(KERN_ERR "Flask: expression result was undefined - disabling all rules.\n");
         /* turn the rules on or off */
         for ( cur = node->true_list; cur != NULL; cur = cur->next )
         {
@@ -287,7 +287,7 @@ static int cond_insertf(struct avtab *a, struct avtab_key *k,
     {
         if ( avtab_search(&p->te_avtab, k) )
         {
-            printk("security: type rule already exists outside of a "
+            printk("Flask: type rule already exists outside of a "
                                                                 "conditional.");
             goto err;
         }
@@ -306,7 +306,7 @@ static int cond_insertf(struct avtab *a, struct avtab_key *k,
             {
                 if ( avtab_search_node_next(node_ptr, k->specified) )
                 {
-                    printk("security: too many conflicting type rules.");
+                    printk("Flask: too many conflicting type rules.");
                     goto err;
                 }
                 found = 0;
@@ -320,7 +320,7 @@ static int cond_insertf(struct avtab *a, struct avtab_key *k,
                 }
                 if ( !found )
                 {
-                    printk("security: conflicting type rules.\n");
+                    printk("Flask: conflicting type rules.\n");
                     goto err;
                 }
             }
@@ -329,7 +329,7 @@ static int cond_insertf(struct avtab *a, struct avtab_key *k,
         {
             if ( avtab_search(&p->te_cond_avtab, k) )
             {
-                printk("security: conflicting type rules when adding type rule "
+                printk("Flask: conflicting type rules when adding type rule "
                                                                 "for true.\n");
                 goto err;
             }
@@ -339,7 +339,7 @@ static int cond_insertf(struct avtab *a, struct avtab_key *k,
     node_ptr = avtab_insert_nonunique(&p->te_cond_avtab, k, d);
     if ( !node_ptr )
     {
-        printk("security: could not insert rule.");
+        printk("Flask: could not insert rule.");
         goto err;
     }
 
@@ -389,8 +389,7 @@ static int cond_read_av_list(struct policydb *p, void *fp,
     data.tail = NULL;
     for ( i = 0; i < len; i++ )
     {
-        rc = avtab_read_item(fp, p->policyvers, &p->te_cond_avtab, cond_insertf,
-                                                                        &data);
+        rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf, &data);
         if ( rc )
             return rc;
     }
@@ -403,13 +402,13 @@ static int expr_isvalid(struct policydb *p, struct cond_expr *expr)
 {
     if ( expr->expr_type <= 0 || expr->expr_type > COND_LAST )
     {
-        printk("security: conditional expressions uses unknown operator.\n");
+        printk("Flask: conditional expressions uses unknown operator.\n");
         return 0;
     }
 
     if ( expr->bool > p->p_bools.nprim )
     {
-        printk("security: conditional expressions uses unknown bool.\n");
+        printk("Flask: conditional expressions uses unknown bool.\n");
         return 0;
     }
     return 1;
@@ -489,6 +488,10 @@ int cond_read_list(struct policydb *p, void *fp)
 
     len = le32_to_cpu(buf[0]);
 
+    rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+    if ( rc )
+      goto err;
+
     for ( i = 0; i < len; i++ )
     {
         node = xmalloc(struct cond_node);
diff --git a/xen/xsm/flask/ss/conditional.h b/xen/xsm/flask/ss/conditional.h
index c3798a7a70..d389ecf870 100644
--- a/xen/xsm/flask/ss/conditional.h
+++ b/xen/xsm/flask/ss/conditional.h
@@ -28,7 +28,7 @@ struct cond_expr {
 #define COND_XOR    5 /* bool ^ bool */
 #define COND_EQ        6 /* bool == bool */
 #define COND_NEQ    7 /* bool != bool */
-#define COND_LAST    8
+#define COND_LAST    COND_NEQ
     __u32 expr_type;
     __u32 bool;
     struct cond_expr *next;
diff --git a/xen/xsm/flask/ss/context.h b/xen/xsm/flask/ss/context.h
index bb1ae637e3..302b3698a7 100644
--- a/xen/xsm/flask/ss/context.h
+++ b/xen/xsm/flask/ss/context.h
@@ -42,17 +42,40 @@ static inline int mls_context_cpy(struct context *dst, struct context *src)
 {
     int rc;
 
-    if (!flask_mls_enabled)
+    if ( !flask_mls_enabled )
         return 0;
 
     dst->range.level[0].sens = src->range.level[0].sens;
     rc = ebitmap_cpy(&dst->range.level[0].cat, &src->range.level[0].cat);
-    if (rc)
+    if ( rc )
         goto out;
 
     dst->range.level[1].sens = src->range.level[1].sens;
     rc = ebitmap_cpy(&dst->range.level[1].cat, &src->range.level[1].cat);
-    if (rc)
+    if ( rc )
+        ebitmap_destroy(&dst->range.level[0].cat);
+out:
+    return rc;
+}
+
+/*
+ * Sets both levels in the MLS range of 'dst' to the low level of 'src'.
+ */
+static inline int mls_context_cpy_low(struct context *dst, struct context *src)
+{
+    int rc;
+
+    if ( !flask_mls_enabled )
+        return 0;
+
+    dst->range.level[0].sens = src->range.level[0].sens;
+    rc = ebitmap_cpy(&dst->range.level[0].cat, &src->range.level[0].cat);
+    if ( rc )
+        goto out;
+
+    dst->range.level[1].sens = src->range.level[0].sens;
+    rc = ebitmap_cpy(&dst->range.level[1].cat, &src->range.level[0].cat);
+    if ( rc )
         ebitmap_destroy(&dst->range.level[0].cat);
 out:
     return rc;
@@ -60,7 +83,7 @@ out:
 
 static inline int mls_context_cmp(struct context *c1, struct context *c2)
 {
-    if (!flask_mls_enabled)
+    if ( !flask_mls_enabled )
         return 1;
 
     return ((c1->range.level[0].sens == c2->range.level[0].sens) &&
@@ -71,7 +94,7 @@ static inline int mls_context_cmp(struct context *c1, struct context *c2)
 
 static inline void mls_context_destroy(struct context *c)
 {
-    if (!flask_mls_enabled)
+    if ( !flask_mls_enabled )
         return;
 
     ebitmap_destroy(&c->range.level[0].cat);
diff --git a/xen/xsm/flask/ss/ebitmap.c b/xen/xsm/flask/ss/ebitmap.c
index 0d8ac8d6f0..61f38d89d2 100644
--- a/xen/xsm/flask/ss/ebitmap.c
+++ b/xen/xsm/flask/ss/ebitmap.c
@@ -3,6 +3,10 @@
  *
  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
  */
+/*
+ * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
+ *      Applied standard bit operations to improve bitmap scanning.
+ */
 
 /* Ported to Xen 3.0, George Coker, <gscoker@alpha.ncsc.mil> */
 
@@ -11,6 +15,7 @@
 #include <xen/xmalloc.h>
 #include <xen/errno.h>
 #include <xen/spinlock.h>
+#include <xen/bitmap.h>
 #include "ebitmap.h"
 #include "policydb.h"
 
@@ -23,7 +28,8 @@ int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
 
     n1 = e1->node;
     n2 = e2->node;
-    while ( n1 && n2 && (n1->startbit == n2->startbit) && (n1->map == n2->map) )
+    while ( n1 && n2 && (n1->startbit == n2->startbit) &&
+            !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8))
     {
         n1 = n1->next;
         n2 = n2->next;
@@ -52,7 +58,7 @@ int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
         }
         memset(new, 0, sizeof(*new));
         new->startbit = n->startbit;
-        new->map = n->map;
+        memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
         new->next = NULL;
         if ( prev )
             prev->next = new;
@@ -69,6 +75,7 @@ int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 {
     struct ebitmap_node *n1, *n2;
+    int i;
 
     if ( e1->highbit < e2->highbit )
         return 0;
@@ -82,8 +89,11 @@ int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
             n1 = n1->next;
             continue;
         }
-        if ( (n1->map & n2->map) != n2->map )
-            return 0;
+        for ( i = 0; i < EBITMAP_UNIT_NUMS; i++ )
+        {
+            if ( (n1->maps[i] & n2->maps[i]) != n2->maps[i] )
+                return 0;
+        }
 
         n1 = n1->next;
         n2 = n2->next;
@@ -105,13 +115,8 @@ int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
     n = e->node;
     while ( n && (n->startbit <= bit) )
     {
-        if ( (n->startbit + MAPSIZE) > bit )
-        {
-            if ( n->map & (MAPBIT << (bit - n->startbit)) )
-                return 1;
-            else
-                return 0;
-        }
+        if ( (n->startbit + EBITMAP_SIZE) > bit )
+            return ebitmap_node_get_bit(n, bit);
         n = n->next;
     }
 
@@ -126,37 +131,41 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
     n = e->node;
     while ( n && n->startbit <= bit )
     {
-        if ( (n->startbit + MAPSIZE) > bit )
+        if ( (n->startbit + EBITMAP_SIZE) > bit )
         {
             if ( value )
             {
-                n->map |= (MAPBIT << (bit - n->startbit));
+                ebitmap_node_set_bit(n, bit);
             }
             else
             {
-                n->map &= ~(MAPBIT << (bit - n->startbit));
-                if ( !n->map )
+                unsigned int s;
+
+                ebitmap_node_clr_bit(n, bit);
+
+                s = find_first_bit(n->maps, EBITMAP_SIZE);
+                if ( s < EBITMAP_SIZE )
+                    return 0;
+
+                /* drop this node from the bitmap */
+
+                if ( !n->next )
                 {
-                    /* drop this node from the bitmap */
-
-                    if ( !n->next )
-                    {
-                        /*
-                         * this was the highest map
-                         * within the bitmap
-                         */
-                        if ( prev )
-                            e->highbit = prev->startbit + MAPSIZE;
-                        else
-                            e->highbit = 0;
-                    }
+                    /*
+                     * this was the highest map
+                     * within the bitmap
+                     */
                     if ( prev )
-                        prev->next = n->next;
+                        e->highbit = prev->startbit + EBITMAP_SIZE;
                     else
-                        e->node = n->next;
-
-                    xfree(n);
+                        e->highbit = 0;
                 }
+                if ( prev )
+                    prev->next = n->next;
+                else
+                    e->node = n->next;
+
+                xfree(n);
             }
             return 0;
         }
@@ -172,12 +181,12 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
         return -ENOMEM;
     memset(new, 0, sizeof(*new));
 
-    new->startbit = bit & ~(MAPSIZE - 1);
-    new->map = (MAPBIT << (bit - new->startbit));
+    new->startbit = bit - (bit % EBITMAP_SIZE);
+    ebitmap_node_set_bit(new, bit);
 
     if ( !n )
         /* this node will be the highest map within the bitmap */
-        e->highbit = new->startbit + MAPSIZE;
+        e->highbit = new->startbit + EBITMAP_SIZE;
 
     if ( prev )
     {
@@ -215,11 +224,11 @@ void ebitmap_destroy(struct ebitmap *e)
 
 int ebitmap_read(struct ebitmap *e, void *fp)
 {
-    int rc;
-    struct ebitmap_node *n, *l;
+    struct ebitmap_node *n = NULL;
+    u32 mapunit, count, startbit, index;
+    u64 map;
     __le32 buf[3];
-    u32 mapsize, count, i;
-    __le64 map;
+    int rc, i;
 
     ebitmap_init(e);
 
@@ -227,99 +236,99 @@ int ebitmap_read(struct ebitmap *e, void *fp)
     if ( rc < 0 )
         goto out;
 
-    mapsize = le32_to_cpu(buf[0]);
+    mapunit = le32_to_cpu(buf[0]);
     e->highbit = le32_to_cpu(buf[1]);
     count = le32_to_cpu(buf[2]);
 
-    if ( mapsize != MAPSIZE )
+    if ( mapunit != sizeof(u64) * 8 )
     {
-        printk(KERN_ERR "security: ebitmap: map size %u does not "
-               "match my size %Zd (high bit was %d)\n", mapsize,
-               MAPSIZE, e->highbit);
+        printk(KERN_ERR "Flask: ebitmap: map size %u does not "
+               "match my size %Zd (high bit was %d)\n", mapunit,
+               sizeof(u64) * 8, e->highbit);
         goto bad;
     }
+
+    /* round up e->highbit */
+    e->highbit += EBITMAP_SIZE - 1;
+    e->highbit -= (e->highbit % EBITMAP_SIZE);
+
     if ( !e->highbit )
     {
         e->node = NULL;
         goto ok;
     }
-    if ( e->highbit & (MAPSIZE - 1) )
-    {
-        printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
-               "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
-        goto bad;
-    }
-    l = NULL;
+
     for ( i = 0; i < count; i++ )
     {
-        rc = next_entry(buf, fp, sizeof(u32));
+        rc = next_entry(&startbit, fp, sizeof(u32));
         if ( rc < 0 )
         {
-            printk(KERN_ERR "security: ebitmap: truncated map\n");
+            printk(KERN_ERR "Flask: ebitmap: truncated map\n");
             goto bad;
         }
-        n = xmalloc(struct ebitmap_node);
-        if ( !n )
+        startbit = le32_to_cpu(startbit);
+        if ( startbit & (mapunit - 1) )
         {
-            printk(KERN_ERR "security: ebitmap: out of memory\n");
-            rc = -ENOMEM;
+            printk(KERN_ERR "Flask: ebitmap start bit (%d) is "
+                   "not a multiple of the map unit size (%u)\n",
+                   startbit, mapunit);
+            goto bad;
+        }
+        if ( startbit > e->highbit - mapunit )
+        {
+            printk(KERN_ERR "Flask: ebitmap start bit (%d) is "
+                   "beyond the end of the bitmap (%u)\n",
+                   startbit, (e->highbit - mapunit));
             goto bad;
         }
-        memset(n, 0, sizeof(*n));
-
-        n->startbit = le32_to_cpu(buf[0]);
 
-        if ( n->startbit & (MAPSIZE - 1) )
+        if ( !n || startbit >= n->startbit + EBITMAP_SIZE )
         {
-            printk(KERN_ERR "security: ebitmap start bit (%d) is "
-                   "not a multiple of the map size (%Zd)\n",
-                   n->startbit, MAPSIZE);
-            goto bad_free;
+            struct ebitmap_node *tmp;
+            tmp = xmalloc(struct ebitmap_node);
+            if ( !tmp )
+            {
+                printk(KERN_ERR
+                       "Flask: ebitmap: out of memory\n");
+                rc = -ENOMEM;
+                goto bad;
+            }
+            memset(tmp, 0, sizeof(*tmp));
+            /* round down */
+            tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
+            if ( n )
+                n->next = tmp;
+            else
+                e->node = tmp;
+            n = tmp;
         }
-        if ( n->startbit > (e->highbit - MAPSIZE) )
+        else if ( startbit <= n->startbit )
         {
-            printk(KERN_ERR "security: ebitmap start bit (%d) is "
-                   "beyond the end of the bitmap (%Zd)\n",
-                   n->startbit, (e->highbit - MAPSIZE));
-            goto bad_free;
+            printk(KERN_ERR "Flask: ebitmap: start bit %d"
+                   " comes after start bit %d\n",
+                   startbit, n->startbit);
+            goto bad;
         }
+
         rc = next_entry(&map, fp, sizeof(u64));
         if ( rc < 0 )
         {
-            printk(KERN_ERR "security: ebitmap: truncated map\n");
-            goto bad_free;
+            printk(KERN_ERR "Flask: ebitmap: truncated map\n");
+            goto bad;
         }
-        n->map = le64_to_cpu(map);
+        map = le64_to_cpu(map);
 
-        if ( !n->map )
+        index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
+        while ( map )
         {
-            printk(KERN_ERR "security: ebitmap: null map in "
-                   "ebitmap (startbit %d)\n", n->startbit);
-            goto bad_free;
+            n->maps[index++] = map & (-1UL);
+            map = EBITMAP_SHIFT_UNIT_SIZE(map);
         }
-        if ( l )
-        {
-            if ( n->startbit <= l->startbit )
-            {
-                printk(KERN_ERR "security: ebitmap: start "
-                       "bit %d comes after start bit %d\n",
-                       n->startbit, l->startbit);
-                goto bad_free;
-            }
-            l->next = n;
-        }
-        else
-            e->node = n;
-
-        l = n;
     }
-
 ok:
     rc = 0;
 out:
     return rc;
-bad_free:
-    xfree(n);
 bad:
     if ( !rc )
         rc = -EINVAL;
diff --git a/xen/xsm/flask/ss/ebitmap.h b/xen/xsm/flask/ss/ebitmap.h
index c2a390ef5f..bb43de891d 100644
--- a/xen/xsm/flask/ss/ebitmap.h
+++ b/xen/xsm/flask/ss/ebitmap.h
@@ -14,14 +14,20 @@
 #ifndef _SS_EBITMAP_H_
 #define _SS_EBITMAP_H_
 
-#define MAPTYPE u64            /* portion of bitmap in each node */
-#define MAPSIZE (sizeof(MAPTYPE) * 8)    /* number of bits in node bitmap */
-#define MAPBIT  1ULL            /* a bit in the node bitmap */
+#include <xen/bitmap.h>
+
+#define EBITMAP_UNIT_NUMS	((32 - sizeof(void *) - sizeof(u32))	\
+					/ sizeof(unsigned long))
+#define EBITMAP_UNIT_SIZE	BITS_PER_LONG
+#define EBITMAP_SIZE		(EBITMAP_UNIT_NUMS * EBITMAP_UNIT_SIZE)
+#define EBITMAP_BIT		1ULL
+#define EBITMAP_SHIFT_UNIT_SIZE(x)					\
+	(((x) >> EBITMAP_UNIT_SIZE / 2) >> EBITMAP_UNIT_SIZE / 2)
 
 struct ebitmap_node {
-    u32 startbit;        /* starting position in the total bitmap */
-    MAPTYPE map;        /* this node's portion of the bitmap */
     struct ebitmap_node *next;
+    unsigned long maps[EBITMAP_UNIT_NUMS];
+    u32 startbit;
 };
 
 struct ebitmap {
@@ -32,11 +38,18 @@ struct ebitmap {
 #define ebitmap_length(e) ((e)->highbit)
 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
 
-static inline unsigned int ebitmap_start(struct ebitmap *e,
-                                                 struct ebitmap_node **n)
+static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
+                                                  struct ebitmap_node **n)
 {
-    *n = e->node;
-    return ebitmap_startbit(e);
+    unsigned int ofs;
+
+    for ( *n = e->node; *n; *n = (*n)->next )
+    {
+        ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
+        if ( ofs < EBITMAP_SIZE )
+            return (*n)->startbit + ofs;
+    }
+    return ebitmap_length(e);
 }
 
 static inline void ebitmap_init(struct ebitmap *e)
@@ -44,29 +57,66 @@ static inline void ebitmap_init(struct ebitmap *e)
     memset(e, 0, sizeof(*e));
 }
 
-static inline unsigned int ebitmap_next(struct ebitmap_node **n,
-                                                        unsigned int bit)
+static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
+                                                 struct ebitmap_node **n,
+                                                 unsigned int bit)
 {
-    if ( (bit == ((*n)->startbit + MAPSIZE - 1)) && (*n)->next )
+    unsigned int ofs;
+
+    ofs = find_next_bit((*n)->maps, EBITMAP_SIZE, bit - (*n)->startbit + 1);
+    if ( ofs < EBITMAP_SIZE )
+        return ofs + (*n)->startbit;
+
+    for ( *n = (*n)->next; *n; *n = (*n)->next )
     {
-        *n = (*n)->next;
-        return (*n)->startbit;
+        ofs = find_first_bit((*n)->maps, EBITMAP_SIZE);
+        if ( ofs < EBITMAP_SIZE )
+            return ofs + (*n)->startbit;
     }
-
-    return (bit+1);
+    return ebitmap_length(e);
 }
 
-static inline int ebitmap_node_get_bit(struct ebitmap_node * n,
-                                                        unsigned int bit)
+#define EBITMAP_NODE_INDEX(node, bit)	\
+    (((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE)
+#define EBITMAP_NODE_OFFSET(node, bit)	\
+    (((bit) - (node)->startbit) % EBITMAP_UNIT_SIZE)
+
+static inline int ebitmap_node_get_bit(struct ebitmap_node *n,
+                                       unsigned int bit)
 {
-    if ( n->map & (MAPBIT << (bit - n->startbit)) )
+    unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+    unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
+
+    BUG_ON( index >= EBITMAP_UNIT_NUMS );
+    if ( (n->maps[index] & (EBITMAP_BIT << ofs)) )
         return 1;
     return 0;
 }
 
-#define ebitmap_for_each_bit(e, n, bit) \
-    for ( bit = ebitmap_start(e, &n); bit < ebitmap_length(e); \
-                                    bit = ebitmap_next(&n, bit) ) \
+static inline void ebitmap_node_set_bit(struct ebitmap_node *n,
+                                        unsigned int bit)
+{
+    unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+    unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
+
+    BUG_ON(index >= EBITMAP_UNIT_NUMS);
+    n->maps[index] |= (EBITMAP_BIT << ofs);
+}
+
+static inline void ebitmap_node_clr_bit(struct ebitmap_node *n,
+                                        unsigned int bit)
+{
+    unsigned int index = EBITMAP_NODE_INDEX(n, bit);
+    unsigned int ofs = EBITMAP_NODE_OFFSET(n, bit);
+
+    BUG_ON( index >= EBITMAP_UNIT_NUMS );
+    n->maps[index] &= ~(EBITMAP_BIT << ofs);
+}
+
+#define ebitmap_for_each_positive_bit(e, n, bit)	\
+    for ( bit = ebitmap_start_positive(e, &n);       \
+          bit < ebitmap_length(e);                   \
+          bit = ebitmap_next_positive(e, &n, bit) )   \
 
 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
diff --git a/xen/xsm/flask/ss/hashtab.c b/xen/xsm/flask/ss/hashtab.c
index f7ca94f3ab..5be7a8805d 100644
--- a/xen/xsm/flask/ss/hashtab.c
+++ b/xen/xsm/flask/ss/hashtab.c
@@ -11,8 +11,10 @@
 #include <xen/errno.h>
 #include "hashtab.h"
 
-struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, void *key),
-            int (*keycmp)(struct hashtab *h, void *key1, void *key2), u32 size)
+struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h,
+						 const void *key),
+            int (*keycmp)(struct hashtab *h, const void *key1,
+			  const void *key2), u32 size)
 {
     struct hashtab *p;
     u32 i;
@@ -26,7 +28,7 @@ struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, void *key),
     p->nel = 0;
     p->hash_value = hash_value;
     p->keycmp = keycmp;
-    p->htable = (void *)xmalloc_array(struct hashtab_node, size);
+    p->htable = xmalloc_array(struct hashtab_node *, size);
     if ( p->htable == NULL )
     {
         xfree(p);
@@ -80,7 +82,7 @@ int hashtab_insert(struct hashtab *h, void *key, void *datum)
     return 0;
 }
 
-void *hashtab_search(struct hashtab *h, void *key)
+void *hashtab_search(struct hashtab *h, const void *key)
 {
     u32 hvalue;
     struct hashtab_node *cur;
diff --git a/xen/xsm/flask/ss/hashtab.h b/xen/xsm/flask/ss/hashtab.h
index d5241c6294..44ed6c01cf 100644
--- a/xen/xsm/flask/ss/hashtab.h
+++ b/xen/xsm/flask/ss/hashtab.h
@@ -22,9 +22,9 @@ struct hashtab {
     struct hashtab_node **htable;    /* hash table */
     u32 size;            /* number of slots in hash table */
     u32 nel;            /* number of elements in hash table */
-    u32 (*hash_value)(struct hashtab *h, void *key);
+    u32 (*hash_value)(struct hashtab *h, const void *key);
                     /* hash function */
-    int (*keycmp)(struct hashtab *h, void *key1, void *key2);
+    int (*keycmp)(struct hashtab *h, const void *key1, const void *key2);
                     /* key comparison function */
 };
 
@@ -39,8 +39,10 @@ struct hashtab_info {
  * Returns NULL if insufficent space is available or
  * the new hash table otherwise.
  */
-struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, void *key),
-            int (*keycmp)(struct hashtab *h, void *key1, void *key2), u32 size);
+struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h,
+						 const void *key),
+            int (*keycmp)(struct hashtab *h, const void *key1,
+			  const void *key2), u32 size);
 
 /*
  * Inserts the specified (key, datum) pair into the specified hash table.
@@ -58,7 +60,7 @@ int hashtab_insert(struct hashtab *h, void *k, void *d);
  * Returns NULL if no entry has the specified key or
  * the datum of the entry otherwise.
  */
-void *hashtab_search(struct hashtab *h, void *k);
+void *hashtab_search(struct hashtab *h, const void *k);
 
 /*
  * Destroys the specified hash table.
diff --git a/xen/xsm/flask/ss/mls.c b/xen/xsm/flask/ss/mls.c
index 0af8947565..aee9fc312a 100644
--- a/xen/xsm/flask/ss/mls.c
+++ b/xen/xsm/flask/ss/mls.c
@@ -29,46 +29,49 @@
  */
 int mls_compute_context_len(struct context * context)
 {
-    int i, l, len, range;
+    int i, l, len, head, prev;
+    char *nm;
+    struct ebitmap *e;
     struct ebitmap_node *node;
 
-    if (!flask_mls_enabled)
+    if ( !flask_mls_enabled )
         return 0;
 
     len = 1; /* for the beginning ":" */
     for ( l = 0; l < 2; l++ )
     {
-        range = 0;
-        len += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
+        int index_sens = context->range.level[l].sens;
+        len += strlen(policydb.p_sens_val_to_name[index_sens - 1]);
 
-        ebitmap_for_each_bit(&context->range.level[l].cat, node, i)
+        /* categories */
+        head = -2;
+        prev = -2;
+        e = &context->range.level[l].cat;
+        ebitmap_for_each_positive_bit(e, node, i)
         {
-            if ( ebitmap_node_get_bit(node, i) )
+            if ( i - prev > 1 )
             {
-                if ( range )
+				/* one or more negative bits are skipped */
+                if ( head != prev )
                 {
-                    range++;
-                    continue;
+                    nm = policydb.p_cat_val_to_name[prev];
+                    len += strlen(nm) + 1;
                 }
-
-                len += strlen(policydb.p_cat_val_to_name[i]) + 1;
-                range++;
-            }
-            else
-            {
-                if ( range > 1 )
-                    len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
-                range = 0;
+                nm = policydb.p_cat_val_to_name[i];
+                len += strlen(nm) + 1;
+                head = i;
             }
+            prev = i;
+        }
+        if ( prev != head )
+        {
+            nm = policydb.p_cat_val_to_name[prev];
+            len += strlen(nm) + 1;
         }
-        /* Handle case where last category is the end of range */
-        if ( range > 1 )
-            len += strlen(policydb.p_cat_val_to_name[i - 1]) + 1;
-
         if ( l == 0 )
         {
             if ( mls_level_eq(&context->range.level[0], 
-                                                &context->range.level[1]) )
+                              &context->range.level[1]) )
                 break;
             else
                 len++;
@@ -85,8 +88,9 @@ int mls_compute_context_len(struct context * context)
  */
 void mls_sid_to_context(struct context *context, char **scontext)
 {
-    char *scontextp;
-    int i, l, range, wrote_sep;
+    char *scontextp, *nm;
+    int i, l, head, prev;
+    struct ebitmap *e;
     struct ebitmap_node *node;
 
     if ( !flask_mls_enabled )
@@ -99,64 +103,51 @@ void mls_sid_to_context(struct context *context, char **scontext)
 
     for ( l = 0; l < 2; l++ )
     {
-        range = 0;
-        wrote_sep = 0;
-        strlcpy(scontextp,
+        memcpy(scontextp,
                 policydb.p_sens_val_to_name[context->range.level[l].sens - 1],
                 strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]));
-        scontextp += strlen(policydb.p_sens_val_to_name[context->range.level[l].sens - 1]);
+        scontextp += strlen(scontextp);
 
         /* categories */
-        ebitmap_for_each_bit(&context->range.level[l].cat, node, i)
+        head = -2;
+        prev = -2;
+        e = &context->range.level[l].cat;
+        ebitmap_for_each_positive_bit(e, node, i)
         {
-            if ( ebitmap_node_get_bit(node, i) )
+            if ( i - prev > 1 )
             {
-                if ( range )
-                {
-                    range++;
-                    continue;
-                }
-
-                if ( !wrote_sep )
+                /* one or more negative bits are skipped */
+                if ( prev != head )
                 {
-                    *scontextp++ = ':';
-                    wrote_sep = 1;
-                }
-                else
-                    *scontextp++ = ',';
-                strlcpy(scontextp, policydb.p_cat_val_to_name[i], 
-                    strlen(policydb.p_cat_val_to_name[i]));
-                scontextp += strlen(policydb.p_cat_val_to_name[i]);
-                range++;
-            }
-            else
-            {
-                if ( range > 1 )
-                {
-                    if ( range > 2 )
+                    if ( prev - head > 1 )
                         *scontextp++ = '.';
                     else
                         *scontextp++ = ',';
-
-                    strlcpy(scontextp, policydb.p_cat_val_to_name[i - 1],
-                        strlen(policydb.p_cat_val_to_name[i - 1]));
-                    scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
+                    nm = policydb.p_cat_val_to_name[prev];
+                    memcpy(scontextp, nm, strlen(nm));
+                    scontextp += strlen(nm);
                 }
-                range = 0;
+                if ( prev < 0 )
+                    *scontextp++ = ':';
+                else
+                    *scontextp++ = ',';
+                nm = policydb.p_cat_val_to_name[i];
+                memcpy(scontextp, nm, strlen(nm));
+                scontextp += strlen(nm);
+                head = i;
             }
+            prev = i;
         }
 
-        /* Handle case where last category is the end of range */
-        if ( range > 1 )
+        if ( prev != head )
         {
-            if ( range > 2 )
+            if ( prev - head > 1 )
                 *scontextp++ = '.';
             else
                 *scontextp++ = ',';
-
-            strlcpy(scontextp, policydb.p_cat_val_to_name[i - 1],
-                strlen(policydb.p_cat_val_to_name[i - 1]));
-            scontextp += strlen(policydb.p_cat_val_to_name[i - 1]);
+            nm = policydb.p_cat_val_to_name[prev];
+            memcpy(scontextp, nm, strlen(nm));
+            scontextp += strlen(nm);
         }
 
         if ( l == 0 )
@@ -176,55 +167,57 @@ void mls_sid_to_context(struct context *context, char **scontext)
     return;
 }
 
+int mls_level_isvalid(struct policydb *p, struct mls_level *l)
+{
+    struct level_datum *levdatum;
+    struct ebitmap_node *node;
+    int i;
+
+    if ( !l->sens || l->sens > p->p_levels.nprim )
+        return 0;
+    levdatum = hashtab_search(p->p_levels.table,
+                              p->p_sens_val_to_name[l->sens - 1]);
+    if ( !levdatum )
+        return 0;
+
+    ebitmap_for_each_positive_bit(&l->cat, node, i)
+    {
+        if ( i > p->p_cats.nprim )
+            return 0;
+        if ( !ebitmap_get_bit(&levdatum->level->cat, i) )
+        {
+            /*
+             * Category may not be associated with
+             * sensitivity.
+             */
+            return 0;
+        }
+    }
+
+    return 1;
+}
+
+int mls_range_isvalid(struct policydb *p, struct mls_range *r)
+{
+    return ( mls_level_isvalid(p, &r->level[0]) &&
+             mls_level_isvalid(p, &r->level[1]) &&
+             mls_level_dom(&r->level[1], &r->level[0]));
+}
+
 /*
  * Return 1 if the MLS fields in the security context
  * structure `c' are valid.  Return 0 otherwise.
  */
 int mls_context_isvalid(struct policydb *p, struct context *c)
 {
-    struct level_datum *levdatum;
     struct user_datum *usrdatum;
-    struct ebitmap_node *node;
-    int i, l;
 
     if ( !flask_mls_enabled )
         return 1;
 
-    /*
-     * MLS range validity checks: high must dominate low, low level must
-     * be valid (category set <-> sensitivity check), and high level must
-     * be valid (category set <-> sensitivity check)
-     */
-    if ( !mls_level_dom(&c->range.level[1], &c->range.level[0]) )
-        /* High does not dominate low. */
+    if ( !mls_range_isvalid(p, &c->range) )
         return 0;
 
-    for ( l = 0; l < 2; l++ )
-    {
-        if ( !c->range.level[l].sens || c->range.level[l].sens > 
-                                                            p->p_levels.nprim )
-            return 0;
-        levdatum = hashtab_search(p->p_levels.table,
-            p->p_sens_val_to_name[c->range.level[l].sens - 1]);
-        if ( !levdatum )
-            return 0;
-
-        ebitmap_for_each_bit(&c->range.level[l].cat, node, i)
-        {
-            if ( ebitmap_node_get_bit(node, i) )
-            {
-                if ( i > p->p_cats.nprim )
-                    return 0;
-                if ( !ebitmap_get_bit(&levdatum->level->cat, i) )
-                    /*
-                     * Category may not be associated with
-                     * sensitivity in low level.
-                     */
-                    return 0;
-            }
-        }
-    }
-
     if ( c->role == OBJECT_R_VAL )
         return 1;
 
@@ -241,26 +234,6 @@ int mls_context_isvalid(struct policydb *p, struct context *c)
 }
 
 /*
- * Copies the MLS range from `src' into `dst'.
- */
-static inline int mls_copy_context(struct context *dst, struct context *src)
-{
-    int l, rc = 0;
-
-    /* Copy the MLS range from the source context */
-    for ( l = 0; l < 2; l++ )
-    {
-        dst->range.level[l].sens = src->range.level[l].sens;
-        rc = ebitmap_cpy(&dst->range.level[l].cat,
-                 &src->range.level[l].cat);
-        if ( rc )
-            break;
-    }
-
-    return rc;
-}
-
-/*
  * Set the MLS fields in the security context structure
  * `context' based on the string representation in
  * the string `*scontext'.  Update `*scontext' to
@@ -270,16 +243,11 @@ static inline int mls_copy_context(struct context *dst, struct context *src)
  * This function modifies the string in place, inserting
  * NULL characters to terminate the MLS fields.
  *
- * If a def_sid is provided and no MLS field is present,
- * copy the MLS field of the associated default context.
- * Used for upgraded to MLS systems where objects may lack
- * MLS fields.
- *
  * Policy read-lock must be held for sidtab lookup.
  *
  */
-int mls_context_to_sid(char oldc, char **scontext, struct context *context,
-                                                struct sidtab *s, u32 def_sid)
+int mls_context_to_sid(char oldc, char **scontext,
+                       struct context *context, struct sidtab *s)
 {
 
     char delim;
@@ -292,23 +260,10 @@ int mls_context_to_sid(char oldc, char **scontext, struct context *context,
         return 0;
 
     /*
-     * No MLS component to the security context, try and map to
-     * default if provided.
+     * No MLS component to the security context -> error.
      */
     if ( !oldc )
-    {
-        struct context *defcon;
-
-        if ( def_sid == SECSID_NULL )
-            goto out;
-
-        defcon = sidtab_search(s, def_sid);
-        if ( !defcon )
-            goto out;
-
-        rc = mls_copy_context(context, defcon);
         goto out;
-    }
 
     /* Extract low sensitivity. */
     scontextp = p = *scontext;
@@ -421,26 +376,6 @@ out:
 }
 
 /*
- * Copies the effective MLS range from `src' into `dst'.
- */
-static inline int mls_scopy_context(struct context *dst, struct context *src)
-{
-    int l, rc = 0;
-
-    /* Copy the MLS range from the source context */
-    for ( l = 0; l < 2; l++ )
-    {
-        dst->range.level[l].sens = src->range.level[0].sens;
-        rc = ebitmap_cpy(&dst->range.level[l].cat,
-                 &src->range.level[0].cat);
-        if ( rc )
-            break;
-    }
-
-    return rc;
-}
-
-/*
  * Copies the MLS range `range' into `context'.
  */
 static inline int mls_range_set(struct context *context,
@@ -537,20 +472,17 @@ int mls_convert_context(struct policydb *oldp, struct policydb *newp,
         c->range.level[l].sens = levdatum->level->sens;
 
         ebitmap_init(&bitmap);
-        ebitmap_for_each_bit(&c->range.level[l].cat, node, i)
+        ebitmap_for_each_positive_bit(&c->range.level[l].cat, node, i)
         {
-            if ( ebitmap_node_get_bit(node, i) )
-            {
-                int rc;
-
-                catdatum = hashtab_search(newp->p_cats.table,
-                             oldp->p_cat_val_to_name[i]);
-                if ( !catdatum )
-                    return -EINVAL;
-                rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
-                if ( rc )
-                    return rc;
-            }
+            int rc;
+
+            catdatum = hashtab_search(newp->p_cats.table,
+                                      oldp->p_cat_val_to_name[i]);
+            if ( !catdatum )
+                return -EINVAL;
+            rc = ebitmap_set_bit(&bitmap, catdatum->value - 1, 1);
+            if ( rc )
+                return rc;
         }
         ebitmap_destroy(&c->range.level[l].cat);
         c->range.level[l].cat = bitmap;
@@ -562,48 +494,37 @@ int mls_convert_context(struct policydb *oldp, struct policydb *newp,
 int mls_compute_sid(struct context *scontext, struct context *tcontext,
                         u16 tclass, u32 specified, struct context *newcontext)
 {
+    struct range_trans *rtr;
+
     if ( !flask_mls_enabled )
         return 0;
 
     switch ( specified )
     {
         case AVTAB_TRANSITION:
-            if ( tclass == SECCLASS_DOMAIN )
+            /* Look for a range transition rule. */
+            for (rtr = policydb.range_tr; rtr; rtr = rtr->next)
             {
-                struct range_trans *rangetr;
-                /* Look for a range transition rule. */
-                for ( rangetr = policydb.range_tr; rangetr;
-                                                    rangetr = rangetr->next)
+                if (rtr->source_type == scontext->type &&
+                    rtr->target_type == tcontext->type &&
+                    rtr->target_class == tclass)
                 {
-                    if ( rangetr->dom == scontext->type &&
-                                        rangetr->type == tcontext->type)
-                    {
-                        /* Set the range from the rule */
-                        return mls_range_set(newcontext, &rangetr->range);
-                    }
+                    /* Set the range from the rule */
+                    return mls_range_set(newcontext,
+                                         &rtr->target_range);
                 }
             }
             /* Fallthrough */
         case AVTAB_CHANGE:
             if ( tclass == SECCLASS_DOMAIN )
                 /* Use the process MLS attributes. */
-                return mls_copy_context(newcontext, scontext);
+                return mls_context_cpy(newcontext, scontext);
             else
-            /* Use the process effective MLS attributes. */
-            return mls_scopy_context(newcontext, scontext);
-        case AVTAB_MEMBER:
-            /* Only polyinstantiate the MLS attributes if
-               the type is being polyinstantiated */
-            if ( newcontext->type != tcontext->type )
-            {
                 /* Use the process effective MLS attributes. */
-                return mls_scopy_context(newcontext, scontext);
-            }
-            else
-            {
-                /* Use the related object MLS attributes. */
-                return mls_copy_context(newcontext, tcontext);
-            }
+                return mls_context_cpy_low(newcontext, scontext);
+        case AVTAB_MEMBER:
+            /* Use the process effective MLS attributes. */
+            return mls_context_cpy_low(newcontext, scontext);
         default:
             return -EINVAL;
     }
diff --git a/xen/xsm/flask/ss/mls.h b/xen/xsm/flask/ss/mls.h
index d47a69578e..b3a015e4c7 100644
--- a/xen/xsm/flask/ss/mls.h
+++ b/xen/xsm/flask/ss/mls.h
@@ -8,7 +8,7 @@
  *
  *    Support for enhanced MLS infrastructure.
  *
- * Copyright (C) 2004-2005 Trusted Computer Solutions, Inc.
+ * Copyright (C) 2004-2006 Trusted Computer Solutions, Inc.
  */
 
 #ifndef _SS_MLS_H_
@@ -20,9 +20,11 @@
 int mls_compute_context_len(struct context *context);
 void mls_sid_to_context(struct context *context, char **scontext);
 int mls_context_isvalid(struct policydb *p, struct context *c);
+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, char **scontext, struct context *context,
-                                               struct sidtab *s, u32 def_sid);
+                       struct sidtab *s);
 
 int mls_convert_context(struct policydb *oldp, struct policydb *newp,
                                                     struct context *context);
diff --git a/xen/xsm/flask/ss/policydb.c b/xen/xsm/flask/ss/policydb.c
index 42b23b08b7..33d422a936 100644
--- a/xen/xsm/flask/ss/policydb.c
+++ b/xen/xsm/flask/ss/policydb.c
@@ -100,6 +100,26 @@ static struct policydb_compat_info policydb_compat[] = {
         .sym_num        = SYM_NUM,
         .ocon_num       = OCON_NUM,
     },
+    {
+	.version	= POLICYDB_VERSION_RANGETRANS,
+	.sym_num	= SYM_NUM,
+	.ocon_num	= OCON_NUM,
+    },
+    {
+	.version	= POLICYDB_VERSION_POLCAP,
+	.sym_num	= SYM_NUM,
+	.ocon_num	= OCON_NUM,
+    },
+    {
+	.version	= POLICYDB_VERSION_PERMISSIVE,
+	.sym_num	= SYM_NUM,
+	.ocon_num	= OCON_NUM,
+    },
+    {
+	.version	= POLICYDB_VERSION_BOUNDARY,
+	.sym_num	= SYM_NUM,
+	.ocon_num	= OCON_NUM,
+    },
 };
 
 static struct policydb_compat_info *policydb_lookup_compat(int version)
@@ -188,6 +208,9 @@ static int policydb_init(struct policydb *p)
     if ( rc )
         goto out_free_avtab;
 
+    ebitmap_init(&p->policycaps);
+    ebitmap_init(&p->permissive_map);
+
 out:
     return rc;
 
@@ -244,7 +267,9 @@ static int role_index(void *key, void *datum, void *datap)
 
     role = datum;
     p = datap;
-    if ( !role->value || role->value > p->p_roles.nprim )
+    if ( !role->value
+         || role->value > p->p_roles.nprim
+         || role->bounds > p->p_roles.nprim )
         return -EINVAL;
     p->p_role_val_to_name[role->value - 1] = key;
     p->role_val_to_struct[role->value - 1] = role;
@@ -261,9 +286,12 @@ static int type_index(void *key, void *datum, void *datap)
 
     if ( typdatum->primary )
     {
-        if ( !typdatum->value || typdatum->value > p->p_types.nprim )
+        if ( !typdatum->value
+             || typdatum->value > p->p_types.nprim
+             || typdatum->bounds > p->p_types.nprim )
             return -EINVAL;
         p->p_type_val_to_name[typdatum->value - 1] = key;
+        p->type_val_to_struct[typdatum->value - 1] = typdatum;
     }
 
     return 0;
@@ -276,7 +304,9 @@ static int user_index(void *key, void *datum, void *datap)
 
     usrdatum = datum;
     p = datap;
-    if ( !usrdatum->value || usrdatum->value > p->p_users.nprim )
+    if ( !usrdatum->value
+         || usrdatum->value > p->p_users.nprim
+         || usrdatum->bounds > p->p_users.nprim )
         return -EINVAL;
     p->p_user_val_to_name[usrdatum->value - 1] = key;
     p->user_val_to_struct[usrdatum->value - 1] = usrdatum;
@@ -356,7 +386,7 @@ static int policydb_index_classes(struct policydb *p)
         goto out;
 
     p->class_val_to_struct =
-        (void *)xmalloc_array(struct class_datum, p->p_classes.nprim);
+        xmalloc_array(struct class_datum *, p->p_classes.nprim);
     if ( !p->class_val_to_struct )
     {
         rc = -ENOMEM;
@@ -404,14 +434,14 @@ static int policydb_index_others(struct policydb *p)
 {
     int i, rc = 0;
 
-    printk(KERN_INFO "security:  %d users, %d roles, %d types, %d bools",
+    printk(KERN_INFO "Flask:  %d users, %d roles, %d types, %d bools",
            p->p_users.nprim, p->p_roles.nprim, p->p_types.nprim, p->p_bools.nprim);
     if ( flask_mls_enabled )
         printk(", %d sens, %d cats", p->p_levels.nprim, p->p_cats.nprim);
 
     printk("\n");
 
-    printk(KERN_INFO "security:  %d classes, %d rules\n",
+    printk(KERN_INFO "Flask:  %d classes, %d rules\n",
            p->p_classes.nprim, p->te_avtab.nel);
 
 #ifdef DEBUG_HASHES
@@ -420,7 +450,7 @@ static int policydb_index_others(struct policydb *p)
 #endif
 
     p->role_val_to_struct =
-        (void *)xmalloc_array(struct role_datum, p->p_roles.nprim);
+        xmalloc_array(struct role_datum *, p->p_roles.nprim);
     if ( !p->role_val_to_struct )
     {
         rc = -ENOMEM;
@@ -428,13 +458,21 @@ static int policydb_index_others(struct policydb *p)
     }
 
     p->user_val_to_struct =
-        (void *)xmalloc_array(struct user_datum, p->p_users.nprim);
+        xmalloc_array(struct user_datum *, p->p_users.nprim);
     if ( !p->user_val_to_struct )
     {
         rc = -ENOMEM;
         goto out;
     }
 
+    p->type_val_to_struct =
+        xmalloc_array(struct type_datum *, p->p_types.nprim);
+    if ( !p->type_val_to_struct )
+    {
+        rc = -ENOMEM;
+        goto out;
+    }
+
     if ( cond_init_bool_indexes(p) )
     {
         rc = -ENOMEM;
@@ -627,6 +665,7 @@ void policydb_destroy(struct policydb *p)
     xfree(p->class_val_to_struct);
     xfree(p->role_val_to_struct);
     xfree(p->user_val_to_struct);
+    xfree(p->type_val_to_struct);
 
     avtab_destroy(&p->te_avtab);
 
@@ -639,6 +678,7 @@ void policydb_destroy(struct policydb *p)
             c = c->next;
             ocontext_destroy(ctmp,i);
         }
+        p->ocontexts[i] = NULL;
     }
 
     cond_policydb_destroy(p);
@@ -659,15 +699,29 @@ void policydb_destroy(struct policydb *p)
 
     for ( rt = p->range_tr; rt; rt = rt -> next )
     {
-        if ( lrt ) xfree(lrt);
+        if ( lrt )
+        {
+            ebitmap_destroy(&lrt->target_range.level[0].cat);
+            ebitmap_destroy(&lrt->target_range.level[1].cat);
+            xfree(lrt);
+        }
         lrt = rt;
     }
-    if ( lrt ) xfree(lrt);
+    if ( lrt )
+    {
+        ebitmap_destroy(&lrt->target_range.level[0].cat);
+        ebitmap_destroy(&lrt->target_range.level[1].cat);
+        xfree(lrt);
+    }
 
-    for ( i = 0; i < p->p_types.nprim; i++ )
-        ebitmap_destroy(&p->type_attr_map[i]);
+    if ( p->type_attr_map )
+        for ( i = 0; i < p->p_types.nprim; i++ )
+            ebitmap_destroy(&p->type_attr_map[i]);
     xfree(p->type_attr_map);
 
+    ebitmap_destroy(&p->policycaps);
+    ebitmap_destroy(&p->permissive_map);
+
     return;
 }
 
@@ -683,7 +737,7 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s)
     rc = sidtab_init(s);
     if ( rc )
     {
-        printk(KERN_ERR "security:  out of memory on SID table init\n");
+        printk(KERN_ERR "Flask:  out of memory on SID table init\n");
         goto out;
     }
 
@@ -692,14 +746,14 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s)
     {
         if ( !c->context[0].user )
         {
-            printk(KERN_ERR "security:  SID %s was never "
+            printk(KERN_ERR "Flask:  SID %s was never "
                    "defined.\n", c->u.name);
             rc = -EINVAL;
             goto out;
         }
         if ( sidtab_insert(s, c->sid[0], &c->context[0]) )
         {
-            printk(KERN_ERR "security:  unable to load initial "
+            printk(KERN_ERR "Flask:  unable to load initial "
                    "SID %s.\n", c->u.name);
             rc = -EINVAL;
             goto out;
@@ -709,6 +763,27 @@ out:
     return rc;
 }
 
+int policydb_class_isvalid(struct policydb *p, unsigned int class)
+{
+    if ( !class || class > p->p_classes.nprim )
+        return 0;
+    return 1;
+}
+
+int policydb_role_isvalid(struct policydb *p, unsigned int role)
+{
+    if ( !role || role > p->p_roles.nprim )
+        return 0;
+    return 1;
+}
+
+int policydb_type_isvalid(struct policydb *p, unsigned int type)
+{
+    if ( !type || type > p->p_types.nprim )
+        return 0;
+    return 1;
+}
+
 /*
  * Return 1 if the fields in the security context
  * structure `c' are valid.  Return 0 otherwise.
@@ -772,14 +847,14 @@ static int mls_read_range_helper(struct mls_range *r, void *fp)
     items = le32_to_cpu(buf[0]);
     if ( items > ARRAY_SIZE(buf) )
     {
-        printk(KERN_ERR "security: mls:  range overflow\n");
+        printk(KERN_ERR "Flask: mls:  range overflow\n");
         rc = -EINVAL;
         goto out;
     }
     rc = next_entry(buf, fp, sizeof(u32) * items);
     if ( rc < 0 )
     {
-        printk(KERN_ERR "security: mls:  truncated range\n");
+        printk(KERN_ERR "Flask: mls:  truncated range\n");
         goto out;
     }
     r->level[0].sens = le32_to_cpu(buf[0]);
@@ -791,7 +866,7 @@ static int mls_read_range_helper(struct mls_range *r, void *fp)
     rc = ebitmap_read(&r->level[0].cat, fp);
     if ( rc )
     {
-        printk(KERN_ERR "security: mls:  error reading low "
+        printk(KERN_ERR "Flask: mls:  error reading low "
                "categories\n");
         goto out;
     }
@@ -800,7 +875,7 @@ static int mls_read_range_helper(struct mls_range *r, void *fp)
         rc = ebitmap_read(&r->level[1].cat, fp);
         if ( rc )
         {
-            printk(KERN_ERR "security: mls:  error reading high "
+            printk(KERN_ERR "Flask: mls:  error reading high "
                    "categories\n");
             goto bad_high;
         }
@@ -810,7 +885,7 @@ static int mls_read_range_helper(struct mls_range *r, void *fp)
         rc = ebitmap_cpy(&r->level[1].cat, &r->level[0].cat);
         if ( rc )
         {
-            printk(KERN_ERR "security: mls:  out of memory\n");
+            printk(KERN_ERR "Flask: mls:  out of memory\n");
             goto bad_high;
         }
     }
@@ -836,7 +911,7 @@ static int context_read_and_validate(struct context *c, struct policydb *p,
     rc = next_entry(buf, fp, sizeof buf);
     if ( rc < 0 )
     {
-        printk(KERN_ERR "security: context truncated\n");
+        printk(KERN_ERR "Flask: context truncated\n");
         goto out;
     }
     c->user = le32_to_cpu(buf[0]);
@@ -846,7 +921,7 @@ static int context_read_and_validate(struct context *c, struct policydb *p,
     {
         if ( mls_read_range_helper(&c->range, fp) )
         {
-            printk(KERN_ERR "security: error reading MLS range of "
+            printk(KERN_ERR "Flask: error reading MLS range of "
                    "context\n");
             rc = -EINVAL;
             goto out;
@@ -855,7 +930,7 @@ static int context_read_and_validate(struct context *c, struct policydb *p,
 
     if ( !policydb_context_isvalid(p, c) )
     {
-        printk(KERN_ERR "security:  invalid security context\n");
+        printk(KERN_ERR "Flask:  invalid security context\n");
         context_destroy(c);
         rc = -EINVAL;
     }
@@ -1121,7 +1196,7 @@ static int class_read(struct policydb *p, struct hashtab *h, void *fp)
                             cladatum->comkey);
         if ( !cladatum->comdatum )
         {
-            printk(KERN_ERR "security:  unknown common %s\n",
+            printk(KERN_ERR "Flask:  unknown common %s\n",
                    cladatum->comkey);
             rc = -EINVAL;
             goto bad;
@@ -1166,8 +1241,8 @@ static int role_read(struct policydb *p, struct hashtab *h, void *fp)
 {
     char *key = NULL;
     struct role_datum *role;
-    int rc;
-    __le32 buf[2];
+    int rc, to_read = 2;
+    __le32 buf[3];
     u32 len;
 
     role = xmalloc(struct role_datum);
@@ -1178,12 +1253,17 @@ static int role_read(struct policydb *p, struct hashtab *h, void *fp)
     }
     memset(role, 0, sizeof(*role));
 
-    rc = next_entry(buf, fp, sizeof buf);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+        to_read = 3;
+
+    rc = next_entry(buf, fp, sizeof(buf[0]) * to_read);
     if ( rc < 0 )
         goto bad;
 
     len = le32_to_cpu(buf[0]);
     role->value = le32_to_cpu(buf[1]);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+        role->bounds = le32_to_cpu(buf[2]);
 
     key = xmalloc_array(char, len + 1);
     if ( !key )
@@ -1231,8 +1311,8 @@ static int type_read(struct policydb *p, struct hashtab *h, void *fp)
 {
     char *key = NULL;
     struct type_datum *typdatum;
-    int rc;
-    __le32 buf[3];
+    int rc, to_read = 3;
+    __le32 buf[4];
     u32 len;
 
     typdatum = xmalloc(struct type_datum);
@@ -1243,13 +1323,30 @@ static int type_read(struct policydb *p, struct hashtab *h, void *fp)
     }
     memset(typdatum, 0, sizeof(*typdatum));
 
-    rc = next_entry(buf, fp, sizeof buf);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+        to_read = 4;
+
+    rc = next_entry(buf, fp, sizeof(buf[0]) * to_read);
     if ( rc < 0 )
         goto bad;
 
     len = le32_to_cpu(buf[0]);
     typdatum->value = le32_to_cpu(buf[1]);
-    typdatum->primary = le32_to_cpu(buf[2]);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+    {
+        u32 prop = le32_to_cpu(buf[2]);
+
+        if ( prop & TYPEDATUM_PROPERTY_PRIMARY )
+            typdatum->primary = 1;
+        if ( prop & TYPEDATUM_PROPERTY_ATTRIBUTE )
+            typdatum->attribute = 1;
+
+        typdatum->bounds = le32_to_cpu(buf[3]);
+    }
+    else
+    {
+        typdatum->primary = le32_to_cpu(buf[2]);
+    }
 
     key = xmalloc_array(char, len + 1);
     if ( !key )
@@ -1287,14 +1384,14 @@ static int mls_read_level(struct mls_level *lp, void *fp)
     rc = next_entry(buf, fp, sizeof buf);
     if ( rc < 0 )
     {
-        printk(KERN_ERR "security: mls: truncated level\n");
+        printk(KERN_ERR "Flask: mls: truncated level\n");
         goto bad;
     }
     lp->sens = le32_to_cpu(buf[0]);
 
     if ( ebitmap_read(&lp->cat, fp) )
     {
-        printk(KERN_ERR "security: mls:  error reading level categories\n");
+        printk(KERN_ERR "Flask: mls:  error reading level categories\n");
         goto bad;
     }
     return 0;
@@ -1307,8 +1404,8 @@ static int user_read(struct policydb *p, struct hashtab *h, void *fp)
 {
     char *key = NULL;
     struct user_datum *usrdatum;
-    int rc;
-    __le32 buf[2];
+    int rc, to_read = 2;
+    __le32 buf[3];
     u32 len;
 
     usrdatum = xmalloc(struct user_datum);
@@ -1319,12 +1416,17 @@ static int user_read(struct policydb *p, struct hashtab *h, void *fp)
     }
     memset(usrdatum, 0, sizeof(*usrdatum));
 
-    rc = next_entry(buf, fp, sizeof buf);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+        to_read = 3;
+
+    rc = next_entry(buf, fp, sizeof(buf[0]) * to_read);
     if ( rc < 0 )
         goto bad;
 
     len = le32_to_cpu(buf[0]);
     usrdatum->value = le32_to_cpu(buf[1]);
+    if ( p->policyvers >= POLICYDB_VERSION_BOUNDARY )
+        usrdatum->bounds = le32_to_cpu(buf[2]);
 
     key = xmalloc_array(char, len + 1);
     if ( !key )
@@ -1475,6 +1577,142 @@ static int (*read_f[SYM_NUM]) (struct policydb *p, struct hashtab *h, void *fp)
     cat_read,
 };
 
+static int user_bounds_sanity_check(void *key, void *datum, void *datap)
+{
+    struct user_datum *upper, *user;
+    struct policydb *p = datap;
+    int depth = 0;
+
+    upper = user = datum;
+    while (upper->bounds)
+    {
+        struct ebitmap_node *node;
+        unsigned long bit;
+
+        if ( ++depth == POLICYDB_BOUNDS_MAXDEPTH )
+        {
+            printk(KERN_ERR "Flask: user %s: "
+                   "too deep or looped boundary",
+                   (char *) key);
+            return -EINVAL;
+        }
+
+        upper = p->user_val_to_struct[upper->bounds - 1];
+        ebitmap_for_each_positive_bit(&user->roles, node, bit)
+        {
+            if ( ebitmap_get_bit(&upper->roles, bit) )
+                continue;
+
+            printk(KERN_ERR
+                   "Flask: boundary violated policy: "
+                   "user=%s role=%s bounds=%s\n",
+                   p->p_user_val_to_name[user->value - 1],
+                   p->p_role_val_to_name[bit],
+                   p->p_user_val_to_name[upper->value - 1]);
+
+            return -EINVAL;
+        }
+    }
+
+    return 0;
+}
+
+static int role_bounds_sanity_check(void *key, void *datum, void *datap)
+{
+    struct role_datum *upper, *role;
+    struct policydb *p = datap;
+    int depth = 0;
+
+    upper = role = datum;
+    while (upper->bounds)
+    {
+        struct ebitmap_node *node;
+        unsigned long bit;
+
+        if ( ++depth == POLICYDB_BOUNDS_MAXDEPTH )
+        {
+            printk(KERN_ERR "Flask: role %s: "
+                   "too deep or looped bounds\n",
+                   (char *) key);
+            return -EINVAL;
+        }
+
+        upper = p->role_val_to_struct[upper->bounds - 1];
+        ebitmap_for_each_positive_bit(&role->types, node, bit)
+        {
+            if ( ebitmap_get_bit(&upper->types, bit) )
+                continue;
+
+            printk(KERN_ERR
+                   "Flask: boundary violated policy: "
+                   "role=%s type=%s bounds=%s\n",
+                   p->p_role_val_to_name[role->value - 1],
+                   p->p_type_val_to_name[bit],
+                   p->p_role_val_to_name[upper->value - 1]);
+
+            return -EINVAL;
+        }
+    }
+
+    return 0;
+}
+
+static int type_bounds_sanity_check(void *key, void *datum, void *datap)
+{
+    struct type_datum *upper, *type;
+    struct policydb *p = datap;
+    int depth = 0;
+
+    upper = type = datum;
+    while (upper->bounds)
+    {
+        if ( ++depth == POLICYDB_BOUNDS_MAXDEPTH )
+        {
+            printk(KERN_ERR "Flask: type %s: "
+			       "too deep or looped boundary\n",
+			       (char *) key);
+            return -EINVAL;
+        }
+
+        upper = p->type_val_to_struct[upper->bounds - 1];
+        if ( upper->attribute )
+        {
+            printk(KERN_ERR "Flask: type %s: "
+			       "bounded by attribute %s",
+			       (char *) key,
+			       p->p_type_val_to_name[upper->value - 1]);
+            return -EINVAL;
+        }
+    }
+
+    return 0;
+}
+
+static int policydb_bounds_sanity_check(struct policydb *p)
+{
+    int rc;
+
+    if ( p->policyvers < POLICYDB_VERSION_BOUNDARY )
+        return 0;
+
+    rc = hashtab_map(p->p_users.table,
+                     user_bounds_sanity_check, p);
+    if ( rc )
+        return rc;
+
+    rc = hashtab_map(p->p_roles.table,
+                     role_bounds_sanity_check, p);
+    if ( rc )
+        return rc;
+
+    rc = hashtab_map(p->p_types.table,
+                     type_bounds_sanity_check, p);
+    if ( rc )
+        return rc;
+
+    return 0;
+}
+
 extern int ss_initialized;
 
 /*
@@ -1505,7 +1743,7 @@ int policydb_read(struct policydb *p, void *fp)
 
     if ( le32_to_cpu(buf[0]) != POLICYDB_MAGIC )
     {
-        printk(KERN_ERR "security:  policydb magic number 0x%x does "
+        printk(KERN_ERR "Flask:  policydb magic number 0x%x does "
                "not match expected magic number 0x%x\n",
                le32_to_cpu(buf[0]), POLICYDB_MAGIC);
         goto bad;
@@ -1514,7 +1752,7 @@ int policydb_read(struct policydb *p, void *fp)
     len = le32_to_cpu(buf[1]);
     if ( len != strlen(POLICYDB_STRING) )
     {
-        printk(KERN_ERR "security:  policydb string length %d does not "
+        printk(KERN_ERR "Flask:  policydb string length %d does not "
                "match expected length %lu\n",
                len, strlen(POLICYDB_STRING));
         goto bad;
@@ -1522,7 +1760,7 @@ int policydb_read(struct policydb *p, void *fp)
     policydb_str = xmalloc_array(char, len + 1);
     if ( !policydb_str )
     {
-        printk(KERN_ERR "security:  unable to allocate memory for policydb "
+        printk(KERN_ERR "Flask:  unable to allocate memory for policydb "
                "string of length %d\n", len);
         rc = -ENOMEM;
         goto bad;
@@ -1530,14 +1768,14 @@ int policydb_read(struct policydb *p, void *fp)
     rc = next_entry(policydb_str, fp, len);
     if ( rc < 0 )
     {
-        printk(KERN_ERR "security:  truncated policydb string identifier\n");
+        printk(KERN_ERR "Flask:  truncated policydb string identifier\n");
         xfree(policydb_str);
         goto bad;
     }
     policydb_str[len] = 0;
     if ( strcmp(policydb_str, POLICYDB_STRING) )
     {
-        printk(KERN_ERR "security:  policydb string %s does not match "
+        printk(KERN_ERR "Flask:  policydb string %s does not match "
                "my string %s\n", policydb_str, POLICYDB_STRING);
         xfree(policydb_str);
         goto bad;
@@ -1555,7 +1793,7 @@ int policydb_read(struct policydb *p, void *fp)
     if ( p->policyvers < POLICYDB_VERSION_MIN ||
                                         p->policyvers > POLICYDB_VERSION_MAX )
     {
-            printk(KERN_ERR "security:  policydb version %d does not match "
+            printk(KERN_ERR "Flask:  policydb version %d does not match "
                    "my version range %d-%d\n",
                    le32_to_cpu(buf[0]), POLICYDB_VERSION_MIN, POLICYDB_VERSION_MAX);
             goto bad;
@@ -1589,20 +1827,28 @@ int policydb_read(struct policydb *p, void *fp)
         }
     }
 
+    if ( p->policyvers >= POLICYDB_VERSION_POLCAP &&
+         ebitmap_read(&p->policycaps, fp) != 0 )
+        goto bad;
+
+    if ( p->policyvers >= POLICYDB_VERSION_PERMISSIVE &&
+         ebitmap_read(&p->permissive_map, fp) != 0 )
+        goto bad;
+
     info = policydb_lookup_compat(p->policyvers);
     if ( !info )
     {
-        printk(KERN_ERR "security:  unable to find policy compat info "
+        printk(KERN_ERR "Flask:  unable to find policy compat info "
                "for version %d\n", p->policyvers);
         goto bad;
     }
 
     if ( le32_to_cpu(buf[2]) != info->sym_num ||
-                                        le32_to_cpu(buf[3]) != info->ocon_num )
+         le32_to_cpu(buf[3]) != info->ocon_num )
     {
-        printk(KERN_ERR "security:  policydb table sizes (%d,%d) do "
+        printk(KERN_ERR "Flask:  policydb table sizes (%d,%d) do "
                "not match mine (%d,%d)\n", le32_to_cpu(buf[2]),
-            le32_to_cpu(buf[3]),
+               le32_to_cpu(buf[3]),
                info->sym_num, info->ocon_num);
         goto bad;
     }
@@ -1624,7 +1870,7 @@ int policydb_read(struct policydb *p, void *fp)
         p->symtab[i].nprim = nprim;
     }
 
-    rc = avtab_read(&p->te_avtab, fp, p->policyvers);
+    rc = avtab_read(&p->te_avtab, fp, p);
     if ( rc )
         goto bad;
 
@@ -1659,6 +1905,13 @@ 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 ( !policydb_role_isvalid(p, tr->role) ||
+             !policydb_type_isvalid(p, tr->type) ||
+             !policydb_role_isvalid(p, tr->new_role) )
+        {
+            rc = -EINVAL;
+            goto bad;
+        }
         ltr = tr;
     }
 
@@ -1685,6 +1938,12 @@ int policydb_read(struct policydb *p, void *fp)
             goto bad;
         ra->role = le32_to_cpu(buf[0]);
         ra->new_role = le32_to_cpu(buf[1]);
+        if ( !policydb_role_isvalid(p, ra->role) ||
+             !policydb_role_isvalid(p, ra->new_role) )
+        {
+            rc = -EINVAL;
+            goto bad;
+        }
         lra = ra;
     }
 
@@ -1720,15 +1979,20 @@ int policydb_read(struct policydb *p, void *fp)
             rc = -EINVAL;
             switch ( i )
             {
-                case OCON_ISID:
-                    rc = next_entry(buf, fp, sizeof(u32));
-                    if ( rc < 0 )
-                        goto bad;
-                    c->sid[0] = le32_to_cpu(buf[0]);
-                    rc = context_read_and_validate(&c->context[0], p, fp);
-                    if ( rc )
-                        goto bad;
+            case OCON_ISID:
+                rc = next_entry(buf, fp, sizeof(u32));
+                if ( rc < 0 )
+                    goto bad;
+                c->sid[0] = le32_to_cpu(buf[0]);
+                rc = context_read_and_validate(&c->context[0], p, fp);
+                if ( rc )
+                    goto bad;
                 break;
+            default:
+                printk(KERN_ERR
+                       "Flask:  unsupported object context config data\n");
+                rc = -EINVAL;
+                goto bad;
             }
         }
     }
@@ -1737,9 +2001,16 @@ int policydb_read(struct policydb *p, void *fp)
     if ( rc < 0 )
         goto bad;
     nel = le32_to_cpu(buf[0]);
+    if ( nel )
+    {
+        printk(KERN_ERR "Flask:  unsupported genfs config data\n");
+        rc = -EINVAL;
+        goto bad;
+    }
 
     if ( p->policyvers >= POLICYDB_VERSION_MLS )
     {
+        int new_rangetr = p->policyvers >= POLICYDB_VERSION_RANGETRANS;
         rc = next_entry(buf, fp, sizeof(u32));
         if ( rc < 0 )
             goto bad;
@@ -1761,11 +2032,31 @@ int policydb_read(struct policydb *p, void *fp)
             rc = next_entry(buf, fp, (sizeof(u32) * 2));
             if ( rc < 0 )
                 goto bad;
-            rt->dom = le32_to_cpu(buf[0]);
-            rt->type = le32_to_cpu(buf[1]);
-            rc = mls_read_range_helper(&rt->range, fp);
+            rt->source_type = le32_to_cpu(buf[0]);
+            rt->target_type = le32_to_cpu(buf[1]);
+            if ( new_rangetr )
+            {
+                rc = next_entry(buf, fp, sizeof(u32));
+                if ( rc < 0 )
+                    goto bad;
+                rt->target_class = le32_to_cpu(buf[0]);
+            } else
+                rt->target_class = SECCLASS_DOMAIN;
+            if ( !policydb_type_isvalid(p, rt->source_type) ||
+                 !policydb_type_isvalid(p, rt->target_type) ||
+                 !policydb_class_isvalid(p, rt->target_class) )
+            {
+                rc = -EINVAL;
+                goto bad;
+            }
+            rc = mls_read_range_helper(&rt->target_range, fp);
             if ( rc )
                 goto bad;
+            if ( !mls_range_isvalid(p, &rt->target_range) )
+            {
+                printk(KERN_WARNING "Flask:  rangetrans:  invalid range\n");
+                goto bad;
+            }
             lrt = rt;
         }
     }
@@ -1787,6 +2078,10 @@ int policydb_read(struct policydb *p, void *fp)
                 goto bad;
     }
 
+    rc = policydb_bounds_sanity_check(p);
+    if ( rc )
+        goto bad;
+
     rc = 0;
 out:
     return rc;
diff --git a/xen/xsm/flask/ss/policydb.h b/xen/xsm/flask/ss/policydb.h
index 6b904aa882..133f45e09f 100644
--- a/xen/xsm/flask/ss/policydb.h
+++ b/xen/xsm/flask/ss/policydb.h
@@ -63,6 +63,7 @@ struct class_datum {
 /* Role attributes */
 struct role_datum {
     u32 value;            /* internal role value */
+    u32 bounds;			/* boundary of role */
     struct ebitmap dominates;    /* set of roles dominated by this role */
     struct ebitmap types;        /* set of authorized types for role */
 };
@@ -83,12 +84,25 @@ struct role_allow {
 /* Type attributes */
 struct type_datum {
     u32 value;        /* internal type value */
+    u32 bounds;		/* boundary of type */
     unsigned char primary;    /* primary name? */
+    unsigned char attribute;/* attribute ?*/
 };
 
+/*
+ * type_datum properties
+ * available at the kernel policy version >= POLICYDB_VERSION_BOUNDARY
+ */
+#define TYPEDATUM_PROPERTY_PRIMARY	0x0001
+#define TYPEDATUM_PROPERTY_ATTRIBUTE	0x0002
+
+/* limitation of boundary depth  */
+#define POLICYDB_BOUNDS_MAXDEPTH	4
+
 /* User attributes */
 struct user_datum {
     u32 value;            /* internal user value */
+    u32 bounds;			/* bounds of user */
     struct ebitmap roles;        /* set of authorized roles for user */
     struct mls_range range;        /* MLS range (min - max) for user */
     struct mls_level dfltlevel;    /* default login MLS level for user */
@@ -108,9 +122,10 @@ struct cat_datum {
 };
 
 struct range_trans {
-    u32 dom;            /* current process domain */
-    u32 type;            /* program executable type */
-    struct mls_range range;        /* new range */
+    u32 source_type;
+    u32 target_type;
+    u32 target_class;
+    struct mls_range target_range;
     struct range_trans *next;
 };
 
@@ -191,6 +206,7 @@ struct policydb {
     struct class_datum **class_val_to_struct;
     struct role_datum **role_val_to_struct;
     struct user_datum **user_val_to_struct;
+    struct type_datum **type_val_to_struct;
 
     /* type enforcement access vectors and transitions */
     struct avtab te_avtab;
@@ -218,12 +234,19 @@ struct policydb {
     /* type -> attribute reverse mapping */
     struct ebitmap *type_attr_map;
 
+    struct ebitmap policycaps;
+
+    struct ebitmap permissive_map;
+
     unsigned int policyvers;
 };
 
 extern void policydb_destroy(struct policydb *p);
 extern int policydb_load_isids(struct policydb *p, struct sidtab *s);
 extern int policydb_context_isvalid(struct policydb *p, struct context *c);
+extern int policydb_class_isvalid(struct policydb *p, unsigned int class);
+extern int policydb_type_isvalid(struct policydb *p, unsigned int type);
+extern int policydb_role_isvalid(struct policydb *p, unsigned int role);
 extern int policydb_read(struct policydb *p, void *fp);
 
 #define PERM_SYMTAB_SIZE 32
diff --git a/xen/xsm/flask/ss/services.c b/xen/xsm/flask/ss/services.c
index eea77d4f36..f1cc36e48e 100644
--- a/xen/xsm/flask/ss/services.c
+++ b/xen/xsm/flask/ss/services.c
@@ -12,8 +12,22 @@
  *
  *     Added conditional policy language extensions
  *
- * Copyright (C) 2004-2005 Trusted Computer Solutions, Inc.
- * Copyright (C) 2003 - 2004 Tresys Technology, LLC
+ * Updated: Hewlett-Packard <paul.moore@hp.com>
+ *
+ *      Added support for the policy capability bitmap
+ *
+ * Updated: Chad Sellers <csellers@tresys.com>
+ *
+ *  Added validation of kernel classes and permissions
+ *
+ * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
+ *
+ *  Added support for bounds domain and audit messaged on masked permissions
+ *
+ * Copyright (C) 2008, 2009 NEC Corporation
+ * Copyright (C) 2006, 2007 Hewlett-Packard Development Company, L.P.
+ * Copyright (C) 2004-2006 Trusted Computer Solutions, Inc.
+ * Copyright (C) 2003 - 2004, 2006 Tresys Technology, LLC
  * Copyright (C) 2003 Red Hat, Inc., James Morris <jmorris@redhat.com>
  *    This program is free software; you can redistribute it and/or modify
  *      it under the terms of the GNU General Public License as published by
@@ -42,9 +56,9 @@ unsigned int policydb_loaded_version;
 
 static DEFINE_RWLOCK(policy_rwlock);
 #define POLICY_RDLOCK read_lock(&policy_rwlock)
-#define POLICY_WRLOCK write_lock_irq(&policy_rwlock)
+#define POLICY_WRLOCK write_lock(&policy_rwlock)
 #define POLICY_RDUNLOCK read_unlock(&policy_rwlock)
-#define POLICY_WRUNLOCK write_unlock_irq(&policy_rwlock)
+#define POLICY_WRUNLOCK write_unlock(&policy_rwlock)
 
 static DEFINE_SPINLOCK(load_sem);
 #define LOAD_LOCK spin_lock(&load_sem)
@@ -66,6 +80,12 @@ static u32 latest_granting = 0;
 static int context_struct_to_string(struct context *context, char **scontext,
                                                             u32 *scontext_len);
 
+static int context_struct_compute_av(struct context *scontext,
+				     struct context *tcontext,
+				     u16 tclass,
+				     u32 requested,
+				     struct av_decision *avd);
+
 /*
  * Return the boolean value of a constraint expression
  * when it is applied to the specified source and target
@@ -259,12 +279,180 @@ mls_ops:
 }
 
 /*
+ * security_dump_masked_av - dumps masked permissions during
+ * security_compute_av due to RBAC, MLS/Constraint and Type bounds.
+ */
+static int dump_masked_av_helper(void *k, void *d, void *args)
+{
+    struct perm_datum *pdatum = d;
+    char **permission_names = args;
+
+    BUG_ON(pdatum->value < 1 || pdatum->value > 32);
+
+    permission_names[pdatum->value - 1] = (char *)k;
+
+    return 0;
+}
+
+static void security_dump_masked_av(struct context *scontext,
+				    struct context *tcontext,
+				    u16 tclass,
+				    u32 permissions,
+				    const char *reason)
+{
+    struct common_datum *common_dat;
+    struct class_datum *tclass_dat;
+    char *tclass_name;
+    char *scontext_name = NULL;
+    char *tcontext_name = NULL;
+    char *permission_names[32];
+    int index;
+    u32 length;
+    unsigned char need_comma = 0;
+
+    if ( !permissions )
+        return;
+
+    tclass_name = policydb.p_class_val_to_name[tclass - 1];
+    tclass_dat = policydb.class_val_to_struct[tclass - 1];
+    common_dat = tclass_dat->comdatum;
+
+    /* init permission_names */
+    if ( common_dat &&
+         hashtab_map(common_dat->permissions.table,
+                     dump_masked_av_helper, permission_names) < 0 )
+        goto out;
+
+    if ( hashtab_map(tclass_dat->permissions.table,
+                    dump_masked_av_helper, permission_names) < 0 )
+        goto out;
+
+	/* get scontext/tcontext in text form */
+    if ( context_struct_to_string(scontext,
+                                 &scontext_name, &length) < 0 )
+        goto out;
+
+    if ( context_struct_to_string(tcontext,
+                                 &tcontext_name, &length) < 0 )
+        goto out;
+
+    printk("Flask: op=security_compute_av reason=%s "
+           "scontext=%s tcontext=%s tclass=%s perms=",
+           reason, scontext_name, tcontext_name, tclass_name);
+
+    for ( index = 0; index < 32; index++ )
+    {
+        u32 mask = (1 << index);
+
+        if ( (mask & permissions) == 0 )
+            continue;
+
+        printk("%s%s",
+               need_comma ? "," : "",
+               permission_names[index]
+               ? permission_names[index] : "????");
+        need_comma = 1;
+    }
+    printk("\n");
+out:
+    /* release scontext/tcontext */
+    xfree(tcontext_name);
+    xfree(scontext_name);
+
+    return;
+}
+
+/*
+ * security_boundary_permission - drops violated permissions
+ * on boundary constraint.
+ */
+static void type_attribute_bounds_av(struct context *scontext,
+                                     struct context *tcontext,
+                                     u16 tclass,
+                                     u32 requested,
+                                     struct av_decision *avd)
+{
+    struct context lo_scontext;
+    struct context lo_tcontext;
+    struct av_decision lo_avd;
+    struct type_datum *source
+        = policydb.type_val_to_struct[scontext->type - 1];
+    struct type_datum *target
+        = policydb.type_val_to_struct[tcontext->type - 1];
+    u32 masked = 0;
+
+    if ( source->bounds )
+    {
+        memset(&lo_avd, 0, sizeof(lo_avd));
+
+        memcpy(&lo_scontext, scontext, sizeof(lo_scontext));
+        lo_scontext.type = source->bounds;
+
+        context_struct_compute_av(&lo_scontext,
+                                  tcontext,
+                                  tclass,
+                                  requested,
+                                  &lo_avd);
+        if ( (lo_avd.allowed & avd->allowed) == avd->allowed )
+            return;		/* no masked permission */
+        masked = ~lo_avd.allowed & avd->allowed;
+    }
+
+    if ( target->bounds )
+    {
+        memset(&lo_avd, 0, sizeof(lo_avd));
+
+        memcpy(&lo_tcontext, tcontext, sizeof(lo_tcontext));
+        lo_tcontext.type = target->bounds;
+
+        context_struct_compute_av(scontext,
+                                  &lo_tcontext,
+                                  tclass,
+                                  requested,
+                                  &lo_avd);
+        if ( (lo_avd.allowed & avd->allowed) == avd->allowed )
+            return;		/* no masked permission */
+        masked = ~lo_avd.allowed & avd->allowed;
+    }
+
+    if ( source->bounds && target->bounds )
+    {
+        memset(&lo_avd, 0, sizeof(lo_avd));
+        /*
+         * lo_scontext and lo_tcontext are already
+         * set up.
+         */
+
+        context_struct_compute_av(&lo_scontext,
+                                  &lo_tcontext,
+                                  tclass,
+                                  requested,
+                                  &lo_avd);
+        if ( (lo_avd.allowed & avd->allowed) == avd->allowed )
+            return;		/* no masked permission */
+        masked = ~lo_avd.allowed & avd->allowed;
+    }
+
+    if ( masked )
+    {
+        /* mask violated permissions */
+        avd->allowed &= ~masked;
+
+        /* audit masked permissions */
+        security_dump_masked_av(scontext, tcontext,
+                                tclass, masked, "bounds");
+    }
+}
+
+/*
  * Compute access vectors based on a context structure pair for
  * the permissions in a particular class.
  */
 static int context_struct_compute_av(struct context *scontext,
-                            struct context *tcontext, u16 tclass, u32 requested, 
-                                                        struct av_decision *avd)
+				     struct context *tcontext,
+				     u16 tclass,
+				     u32 requested,
+				     struct av_decision *avd)
 {
     struct constraint_node *constraint;
     struct role_allow *ra;
@@ -275,22 +463,22 @@ static int context_struct_compute_av(struct context *scontext,
     struct ebitmap_node *snode, *tnode;
     unsigned int i, j;
 
-    if ( !tclass || tclass > policydb.p_classes.nprim )
-    {
-        printk(KERN_ERR "security_compute_av:  unrecognized class %d\n",
-               tclass);
-        return -EINVAL;
-    }
-    tclass_datum = policydb.class_val_to_struct[tclass - 1];
-
     /*
      * Initialize the access vectors to the default values.
      */
     avd->allowed = 0;
-    avd->decided = 0xffffffff;
     avd->auditallow = 0;
     avd->auditdeny = 0xffffffff;
     avd->seqno = latest_granting;
+    avd->flags = 0;
+
+    /*
+     * We do not presently support policydb.handle_unknown == allow in Xen.
+     */
+    if ( !tclass || tclass > policydb.p_classes.nprim )
+        return -EINVAL;
+
+    tclass_datum = policydb.class_val_to_struct[tclass - 1];
 
     /*
      * If a specific type enforcement rule was defined for
@@ -300,14 +488,10 @@ static int context_struct_compute_av(struct context *scontext,
     avkey.specified = AVTAB_AV;
     sattr = &policydb.type_attr_map[scontext->type - 1];
     tattr = &policydb.type_attr_map[tcontext->type - 1];
-    ebitmap_for_each_bit(sattr, snode, i)
+    ebitmap_for_each_positive_bit(sattr, snode, i)
     {
-        if ( !ebitmap_node_get_bit(snode, i) )
-            continue;
-        ebitmap_for_each_bit(tattr, tnode, j)
+        ebitmap_for_each_positive_bit(tattr, tnode, j)
         {
-            if ( !ebitmap_node_get_bit(tnode, j) )
-                continue;
             avkey.source_type = i + 1;
             avkey.target_type = j + 1;
             for ( node = avtab_search_node(&policydb.te_avtab, &avkey);
@@ -338,7 +522,7 @@ static int context_struct_compute_av(struct context *scontext,
         if ( (constraint->permissions & (avd->allowed) ) &&
             !constraint_expr_eval(scontext, tcontext, NULL, constraint->expr))
         {
-            avd->allowed = (avd->allowed) & ~(constraint->permissions);
+	    avd->allowed &= ~(constraint->permissions);
         }
         constraint = constraint->next;
     }
@@ -349,23 +533,25 @@ static int context_struct_compute_av(struct context *scontext,
      * pair.
      */
     if ( tclass == SECCLASS_DOMAIN &&
-/* removed until future dynamic domain capability
-        (avd->allowed & (DOMAIN__TRANSITION | DOMAIN__DYNTRANSITION)) &&
-*/
-                                            scontext->role != tcontext->role )
-        {
+         (avd->allowed & DOMAIN__TRANSITION) &&
+         scontext->role != tcontext->role )
+    {
         for ( ra = policydb.role_allow; ra; ra = ra->next )
         {
             if ( scontext->role == ra->role && tcontext->role == ra->new_role )
                 break;
         }
-/* removed until future dynamic domain capability    
         if (!ra)
-            avd->allowed = (avd->allowed) & ~(DOMAIN__TRANSITION |
-                                            DOMAIN__DYNTRANSITION);
-*/
+            avd->allowed &= ~DOMAIN__TRANSITION;
     }
 
+    /*
+     * If the given source and target types have boundary
+     * constraint, lazy checks have to mask any violated
+     * permission and notice it to userspace via audit.
+     */
+    type_attribute_bounds_av(scontext, tcontext,
+			     tclass, requested, avd);
     return 0;
 }
 
@@ -477,7 +663,7 @@ out:
  * if the access vector decisions were computed successfully.
  */
 int security_compute_av(u32 ssid, u32 tsid, u16 tclass, u32 requested,
-                                                    struct av_decision *avd)
+                        struct av_decision *avd)
 {
     struct context *scontext = NULL, *tcontext = NULL;
     int rc = 0;
@@ -485,7 +671,6 @@ int security_compute_av(u32 ssid, u32 tsid, u16 tclass, u32 requested,
     if ( !ss_initialized )
     {
         avd->allowed = 0xffffffff;
-        avd->decided = 0xffffffff;
         avd->auditallow = 0;
         avd->auditdeny = 0xffffffff;
         avd->seqno = latest_granting;
@@ -510,6 +695,10 @@ int security_compute_av(u32 ssid, u32 tsid, u16 tclass, u32 requested,
     }
 
     rc = context_struct_compute_av(scontext, tcontext, tclass, requested, avd);
+
+    /* permissive domain? */
+    if ( ebitmap_get_bit(&policydb.permissive_map, scontext->type) )
+        avd->flags |= AVD_FLAGS_PERMISSIVE;
 out:
     POLICY_RDUNLOCK;
     return rc;
@@ -611,7 +800,18 @@ out:
 
 }
 
-static int security_context_to_sid_core(char *scontext, u32 scontext_len, u32 *sid, u32 def_sid)
+/**
+ * security_context_to_sid - Obtain a SID for a given security context.
+ * @scontext: security context
+ * @scontext_len: length in bytes
+ * @sid: security identifier, SID
+ *
+ * Obtains a SID associated with the security context that
+ * has the string representation specified by @scontext.
+ * Returns -%EINVAL if the context is invalid, -%ENOMEM if insufficient
+ * memory is available, or 0 on success.
+ */
+int security_context_to_sid(char *scontext, u32 scontext_len, u32 *sid)
 {
     char *scontext2;
     struct context context;
@@ -701,12 +901,12 @@ static int security_context_to_sid_core(char *scontext, u32 scontext_len, u32 *s
     *p++ = 0;
 
     typdatum = hashtab_search(policydb.p_types.table, scontextp);
-    if ( !typdatum )
+    if ( !typdatum || typdatum->attribute )
         goto out_unlock;
 
     context.type = typdatum->value;
 
-    rc = mls_context_to_sid(oldc, &p, &context, &sidtab, def_sid);
+    rc = mls_context_to_sid(oldc, &p, &context, &sidtab);
     if ( rc )
         goto out_unlock;
 
@@ -732,45 +932,6 @@ out:
     return rc;
 }
 
-/**
- * security_context_to_sid - Obtain a SID for a given security context.
- * @scontext: security context
- * @scontext_len: length in bytes
- * @sid: security identifier, SID
- *
- * Obtains a SID associated with the security context that
- * has the string representation specified by @scontext.
- * Returns -%EINVAL if the context is invalid, -%ENOMEM if insufficient
- * memory is available, or 0 on success.
- */
-int security_context_to_sid(char *scontext, u32 scontext_len, u32 *sid)
-{
-    return security_context_to_sid_core(scontext, scontext_len,
-                                                            sid, SECSID_NULL);
-}
-
-/**
- * security_context_to_sid_default - Obtain a SID for a given security context,
- * falling back to specified default if needed.
- *
- * @scontext: security context
- * @scontext_len: length in bytes
- * @sid: security identifier, SID
- * @def_sid: default SID to assign on errror
- *
- * Obtains a SID associated with the security context that
- * has the string representation specified by @scontext.
- * 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).
- * Returns -%EINVAL if the context is invalid, -%ENOMEM if insufficient
- * memory is available, or 0 on success.
- */
-int security_context_to_sid_default(char *scontext, u32 scontext_len, u32 *sid, u32 def_sid)
-{
-    return security_context_to_sid_core(scontext, scontext_len, sid, def_sid);
-}
-
 static int compute_sid_handle_invalid_context(
                 struct context *scontext, struct context *tcontext, u16 tclass,
                                                     struct context *newcontext)
@@ -1001,88 +1162,128 @@ int security_change_sid(u32 ssid, u32 tsid, u16 tclass, u32 *out_sid)
 }
 
 /*
- * Verify that each permission that is defined under the
- * existing policy is still defined with the same value
- * in the new policy.
- */
-static int validate_perm(void *key, void *datum, void *p)
-{
-    struct hashtab *h;
-    struct perm_datum *perdatum, *perdatum2;
-    int rc = 0;
-
-    h = p;
-    perdatum = datum;
-
-    perdatum2 = hashtab_search(h, key);
-    if ( !perdatum2 )
-    {
-        printk(KERN_ERR "security:  permission %s disappeared", (char *)key);
-        rc = -ENOENT;
-        goto out;
-    }
-    if ( perdatum->value != perdatum2->value )
-    {
-        printk(KERN_ERR "security:  the value of permission %s changed",
-                                                                (char *)key);
-        rc = -EINVAL;
-    }
-out:
-    return rc;
-}
-
-/*
- * Verify that each class that is defined under the
- * existing policy is still defined with the same
- * attributes in the new policy.
+ * Verify that each kernel class that is defined in the
+ * policy is correct
  */
-static int validate_class(void *key, void *datum, void *p)
+static int validate_classes(struct policydb *p)
 {
-    struct policydb *newp;
-    struct class_datum *cladatum, *cladatum2;
-    int rc;
-
-    newp = p;
-    cladatum = datum;
-
-    cladatum2 = hashtab_search(newp->p_classes.table, key);
-    if ( !cladatum2 )
+    int i, j;
+    struct class_datum *cladatum;
+    struct perm_datum *perdatum;
+    u32 nprim, tmp, common_pts_len, perm_val, pol_val;
+    u16 class_val;
+    const struct selinux_class_perm *kdefs = &selinux_class_perm;
+    const char *def_class, *def_perm, *pol_class;
+    struct symtab *perms;
+
+    for ( i = 1; i < kdefs->cts_len; i++ )
     {
-        printk(KERN_ERR "security:  class %s disappeared\n", (char *)key);
-        rc = -ENOENT;
-        goto out;
-    }
-    if (cladatum->value != cladatum2->value) {
-        printk(KERN_ERR "security:  the value of class %s changed\n",
-                                                                (char *)key);
-        rc = -EINVAL;
-        goto out;
+        def_class = kdefs->class_to_string[i];
+        if ( !def_class )
+            continue;
+        if ( i > p->p_classes.nprim )
+        {
+            printk(KERN_INFO
+                   "Flask:  class %s not defined in policy\n",
+                   def_class);
+            return -EINVAL;
+        }
+        pol_class = p->p_class_val_to_name[i-1];
+        if ( strcmp(pol_class, def_class) )
+        {
+            printk(KERN_ERR
+                   "Flask:  class %d is incorrect, found %s but should be %s\n",
+                   i, pol_class, def_class);
+            return -EINVAL;
+        }
     }
-    if ( (cladatum->comdatum && !cladatum2->comdatum) ||
-                                (!cladatum->comdatum && cladatum2->comdatum) )
+    for ( i = 0; i < kdefs->av_pts_len; i++ )
     {
-        printk(KERN_ERR "security:  the inherits clause for the access "
-               "vector definition for class %s changed\n", (char *)key);
-        rc = -EINVAL;
-        goto out;
+        class_val = kdefs->av_perm_to_string[i].tclass;
+        perm_val = kdefs->av_perm_to_string[i].value;
+        def_perm = kdefs->av_perm_to_string[i].name;
+        if ( class_val > p->p_classes.nprim )
+            continue;
+        pol_class = p->p_class_val_to_name[class_val-1];
+        cladatum = hashtab_search(p->p_classes.table, pol_class);
+        BUG_ON( !cladatum );
+        perms = &cladatum->permissions;
+        nprim = 1 << (perms->nprim - 1);
+        if ( perm_val > nprim )
+        {
+            printk(KERN_INFO
+                   "Flask:  permission %s in class %s not defined in policy\n",
+                   def_perm, pol_class);
+            return -EINVAL;
+        }
+        perdatum = hashtab_search(perms->table, def_perm);
+        if ( perdatum == NULL )
+        {
+            printk(KERN_ERR
+                   "Flask:  permission %s in class %s not found in policy\n",
+                   def_perm, pol_class);
+            return -EINVAL;
+        }
+        pol_val = 1 << (perdatum->value - 1);
+        if ( pol_val != perm_val )
+        {
+            printk(KERN_ERR
+                   "Flask:  permission %s in class %s has incorrect value\n",
+                   def_perm, pol_class);
+            return -EINVAL;
+        }
     }
-    if ( cladatum->comdatum )
+    for ( i = 0; i < kdefs->av_inherit_len; i++ )
     {
-        rc = hashtab_map(cladatum->comdatum->permissions.table, validate_perm,
-                                     cladatum2->comdatum->permissions.table);
-        if ( rc )
+        class_val = kdefs->av_inherit[i].tclass;
+        if ( class_val > p->p_classes.nprim )
+            continue;
+        pol_class = p->p_class_val_to_name[class_val-1];
+        cladatum = hashtab_search(p->p_classes.table, pol_class);
+        BUG_ON( !cladatum );
+        if ( !cladatum->comdatum )
         {
-            printk(" in the access vector definition for class %s\n", 
-                                                                (char *)key);
-            goto out;
+            printk(KERN_ERR
+            "Flask:  class %s should have an inherits clause but does not\n",
+                   pol_class);
+            return -EINVAL;
+        }
+        tmp = kdefs->av_inherit[i].common_base;
+        common_pts_len = 0;
+        while ( !(tmp & 0x01) )
+        {
+            common_pts_len++;
+            tmp >>= 1;
+        }
+        perms = &cladatum->comdatum->permissions;
+        for ( j = 0; j < common_pts_len; j++ )
+        {
+            def_perm = kdefs->av_inherit[i].common_pts[j];
+            if ( j >= perms->nprim )
+            {
+                printk(KERN_INFO
+                "Flask:  permission %s in class %s not defined in policy\n",
+                       def_perm, pol_class);
+                return -EINVAL;
+            }
+            perdatum = hashtab_search(perms->table, def_perm);
+            if ( perdatum == NULL )
+            {
+                printk(KERN_ERR
+                       "Flask:  permission %s in class %s not found in policy\n",
+                       def_perm, pol_class);
+                return -EINVAL;
+            }
+            if ( perdatum->value != j + 1 )
+            {
+                printk(KERN_ERR
+                      "Flask:  permission %s in class %s has incorrect value\n",
+                       def_perm, pol_class);
+                return -EINVAL;
+            }
         }
     }
-    rc = hashtab_map(cladatum->permissions.table, validate_perm,
-                                                cladatum2->permissions.table);
-    if ( rc )
-        printk(" in access vector definition for class %s\n", (char *)key);
-out:
-    return rc;
+    return 0;
 }
 
 /* Clone the SID into the new SID table. */
@@ -1105,7 +1306,7 @@ static inline int convert_context_handle_invalid_context(struct context *context
         u32 len;
 
         context_struct_to_string(context, &s, &len);
-        printk(KERN_ERR "security:  context %s is invalid\n", s);
+        printk(KERN_ERR "Flask:  context %s is invalid\n", s);
         xfree(s);
     }
     return rc;
@@ -1184,12 +1385,12 @@ out:
 bad:
     context_struct_to_string(&oldc, &s, &len);
     context_destroy(&oldc);
-    printk(KERN_ERR "security:  invalidating context %s\n", s);
+    printk(KERN_ERR "Flask:  invalidating context %s\n", s);
     xfree(s);
     goto out;
 }
 
-extern void flask_complete_init(void);
+static int security_preserve_bools(struct policydb *p);
 
 /**
  * security_load_policy - Load a security policy configuration.
@@ -1225,6 +1426,14 @@ int security_load_policy(void *data, size_t len)
             policydb_destroy(&policydb);
             return -EINVAL;
         }
+        if ( validate_classes(&policydb) )
+        {
+            printk(KERN_ERR
+                   "Flask:  the definition of a class is incorrect\n");
+            sidtab_destroy(&sidtab);
+            policydb_destroy(&policydb);
+            return -EINVAL;
+        }
         policydb_loaded_version = policydb.policyvers;
         ss_initialized = 1;
         seqno = ++latest_granting;
@@ -1245,15 +1454,22 @@ int security_load_policy(void *data, size_t len)
 
     sidtab_init(&newsidtab);
 
-    /* Verify that the existing classes did not change. */
-    if ( hashtab_map(policydb.p_classes.table, validate_class, &newpolicydb) )
+    /* Verify that the kernel defined classes are correct. */
+    if ( validate_classes(&newpolicydb) )
     {
-        printk(KERN_ERR "security:  the definition of an existing "
-                                                            "class changed\n");
+        printk(KERN_ERR
+               "Flask:  the definition of a class is incorrect\n");
         rc = -EINVAL;
         goto err;
     }
 
+    rc = security_preserve_bools(&newpolicydb);
+    if ( rc )
+    {
+        printk(KERN_ERR "Flask:  unable to preserve booleans\n");
+        goto err;
+    }
+
     /* Clone the SID table. */
     sidtab_shutdown(&sidtab);
     if ( sidtab_map(&sidtab, clone_sid, &newsidtab) )
@@ -1517,15 +1733,11 @@ int security_get_user_sids(u32 fromsid, char *username, u32 **sids, u32 *nel)
     }
     memset(mysids, 0, maxnel*sizeof(*mysids));
 
-    ebitmap_for_each_bit(&user->roles, rnode, i)
+    ebitmap_for_each_positive_bit(&user->roles, rnode, i)
     {
-        if ( !ebitmap_node_get_bit(rnode, i) )
-            continue;
         role = policydb.role_val_to_struct[i];
         usercon.role = i+1;
-        ebitmap_for_each_bit(&role->types, tnode, j) {
-            if ( !ebitmap_node_get_bit(tnode, j) )
-                continue;
+        ebitmap_for_each_positive_bit(&role->types, tnode, j) {
             usercon.type = j+1;
 
             if ( mls_setup_user_range(fromcon, user, &usercon) )
@@ -1640,7 +1852,7 @@ int security_set_bools(int len, int *values)
         goto out;
     }
 
-    printk(KERN_INFO "security: committed booleans { ");
+    printk(KERN_INFO "Flask: committed booleans { ");
     for ( i = 0; i < len; i++ )
     {
         if ( values[i] )
@@ -1695,3 +1907,37 @@ out:
     POLICY_RDUNLOCK;
     return rc;
 }
+
+static int security_preserve_bools(struct policydb *p)
+{
+    int rc, nbools = 0, *bvalues = NULL, i;
+    char **bnames = NULL;
+    struct cond_bool_datum *booldatum;
+    struct cond_node *cur;
+
+    rc = security_get_bools(&nbools, &bnames, &bvalues);
+    if ( rc )
+        goto out;
+    for ( i = 0; i < nbools; i++ )
+    {
+        booldatum = hashtab_search(p->p_bools.table, bnames[i]);
+        if ( booldatum )
+            booldatum->state = bvalues[i];
+    }
+    for ( cur = p->cond_list; cur; cur = cur->next )
+    {
+        rc = evaluate_cond_node(p, cur);
+        if ( rc )
+            goto out;
+    }
+
+out:
+    if ( bnames )
+    {
+        for ( i = 0; i < nbools; i++ )
+            xfree(bnames[i]);
+    }
+    xfree(bnames);
+    xfree(bvalues);
+    return rc;
+}
diff --git a/xen/xsm/flask/ss/sidtab.c b/xen/xsm/flask/ss/sidtab.c
index f6df7e87ab..586033cfe1 100644
--- a/xen/xsm/flask/ss/sidtab.c
+++ b/xen/xsm/flask/ss/sidtab.c
@@ -24,7 +24,7 @@ int sidtab_init(struct sidtab *s)
 {
     int i;
 
-    s->htable = (void *)xmalloc_array(struct sidtab_node, SIDTAB_SIZE);
+    s->htable = xmalloc_array(struct sidtab_node *, SIDTAB_SIZE);
     if ( !s->htable )
         return -ENOMEM;
     for ( i = 0; i < SIDTAB_SIZE; i++ )
diff --git a/xen/xsm/flask/ss/symtab.c b/xen/xsm/flask/ss/symtab.c
index 8f36f838b5..d98c116d5b 100644
--- a/xen/xsm/flask/ss/symtab.c
+++ b/xen/xsm/flask/ss/symtab.c
@@ -12,9 +12,9 @@
 #include <xen/errno.h>
 #include "symtab.h"
 
-static unsigned int symhash(struct hashtab *h, void *key)
+static unsigned int symhash(struct hashtab *h, const void *key)
 {
-    char *p, *keyp;
+    const char *p, *keyp;
     unsigned int size;
     unsigned int val;
 
@@ -26,9 +26,9 @@ static unsigned int symhash(struct hashtab *h, void *key)
     return val & (h->size - 1);
 }
 
-static int symcmp(struct hashtab *h, void *key1, void *key2)
+static int symcmp(struct hashtab *h, const void *key1, const void *key2)
 {
-    char *keyp1, *keyp2;
+    const char *keyp1, *keyp2;
 
     keyp1 = key1;
     keyp2 = key2;