1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Implementation of the SID table type. 4 * 5 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 6 */ 7 #include <linux/kernel.h> 8 #include <linux/slab.h> 9 #include <linux/spinlock.h> 10 #include <linux/errno.h> 11 #include "flask.h" 12 #include "security.h" 13 #include "sidtab.h" 14 15 #define SIDTAB_HASH(sid) \ 16 (sid & SIDTAB_HASH_MASK) 17 18 int sidtab_init(struct sidtab *s) 19 { 20 int i; 21 22 s->htable = kmalloc_array(SIDTAB_SIZE, sizeof(*s->htable), GFP_ATOMIC); 23 if (!s->htable) 24 return -ENOMEM; 25 for (i = 0; i < SIDTAB_SIZE; i++) 26 s->htable[i] = NULL; 27 s->nel = 0; 28 s->next_sid = 1; 29 s->shutdown = 0; 30 spin_lock_init(&s->lock); 31 return 0; 32 } 33 34 int sidtab_insert(struct sidtab *s, u32 sid, struct context *context) 35 { 36 int hvalue; 37 struct sidtab_node *prev, *cur, *newnode; 38 39 if (!s) 40 return -ENOMEM; 41 42 hvalue = SIDTAB_HASH(sid); 43 prev = NULL; 44 cur = s->htable[hvalue]; 45 while (cur && sid > cur->sid) { 46 prev = cur; 47 cur = cur->next; 48 } 49 50 if (cur && sid == cur->sid) 51 return -EEXIST; 52 53 newnode = kmalloc(sizeof(*newnode), GFP_ATOMIC); 54 if (!newnode) 55 return -ENOMEM; 56 57 newnode->sid = sid; 58 if (context_cpy(&newnode->context, context)) { 59 kfree(newnode); 60 return -ENOMEM; 61 } 62 63 if (prev) { 64 newnode->next = prev->next; 65 wmb(); 66 prev->next = newnode; 67 } else { 68 newnode->next = s->htable[hvalue]; 69 wmb(); 70 s->htable[hvalue] = newnode; 71 } 72 73 s->nel++; 74 if (sid >= s->next_sid) 75 s->next_sid = sid + 1; 76 return 0; 77 } 78 79 static struct context *sidtab_search_core(struct sidtab *s, u32 sid, int force) 80 { 81 int hvalue; 82 struct sidtab_node *cur; 83 84 if (!s) 85 return NULL; 86 87 hvalue = SIDTAB_HASH(sid); 88 cur = s->htable[hvalue]; 89 while (cur && sid > cur->sid) 90 cur = cur->next; 91 92 if (force && cur && sid == cur->sid && cur->context.len) 93 return &cur->context; 94 95 if (!cur || sid != cur->sid || cur->context.len) { 96 /* Remap invalid SIDs to the unlabeled SID. */ 97 sid = SECINITSID_UNLABELED; 98 hvalue = SIDTAB_HASH(sid); 99 cur = s->htable[hvalue]; 100 while (cur && sid > cur->sid) 101 cur = cur->next; 102 if (!cur || sid != cur->sid) 103 return NULL; 104 } 105 106 return &cur->context; 107 } 108 109 struct context *sidtab_search(struct sidtab *s, u32 sid) 110 { 111 return sidtab_search_core(s, sid, 0); 112 } 113 114 struct context *sidtab_search_force(struct sidtab *s, u32 sid) 115 { 116 return sidtab_search_core(s, sid, 1); 117 } 118 119 int sidtab_map(struct sidtab *s, 120 int (*apply) (u32 sid, 121 struct context *context, 122 void *args), 123 void *args) 124 { 125 int i, rc = 0; 126 struct sidtab_node *cur; 127 128 if (!s) 129 goto out; 130 131 for (i = 0; i < SIDTAB_SIZE; i++) { 132 cur = s->htable[i]; 133 while (cur) { 134 rc = apply(cur->sid, &cur->context, args); 135 if (rc) 136 goto out; 137 cur = cur->next; 138 } 139 } 140 out: 141 return rc; 142 } 143 144 static void sidtab_update_cache(struct sidtab *s, struct sidtab_node *n, int loc) 145 { 146 BUG_ON(loc >= SIDTAB_CACHE_LEN); 147 148 while (loc > 0) { 149 s->cache[loc] = s->cache[loc - 1]; 150 loc--; 151 } 152 s->cache[0] = n; 153 } 154 155 static inline u32 sidtab_search_context(struct sidtab *s, 156 struct context *context) 157 { 158 int i; 159 struct sidtab_node *cur; 160 161 for (i = 0; i < SIDTAB_SIZE; i++) { 162 cur = s->htable[i]; 163 while (cur) { 164 if (context_cmp(&cur->context, context)) { 165 sidtab_update_cache(s, cur, SIDTAB_CACHE_LEN - 1); 166 return cur->sid; 167 } 168 cur = cur->next; 169 } 170 } 171 return 0; 172 } 173 174 static inline u32 sidtab_search_cache(struct sidtab *s, struct context *context) 175 { 176 int i; 177 struct sidtab_node *node; 178 179 for (i = 0; i < SIDTAB_CACHE_LEN; i++) { 180 node = s->cache[i]; 181 if (unlikely(!node)) 182 return 0; 183 if (context_cmp(&node->context, context)) { 184 sidtab_update_cache(s, node, i); 185 return node->sid; 186 } 187 } 188 return 0; 189 } 190 191 int sidtab_context_to_sid(struct sidtab *s, 192 struct context *context, 193 u32 *out_sid) 194 { 195 u32 sid; 196 int ret = 0; 197 unsigned long flags; 198 199 *out_sid = SECSID_NULL; 200 201 sid = sidtab_search_cache(s, context); 202 if (!sid) 203 sid = sidtab_search_context(s, context); 204 if (!sid) { 205 spin_lock_irqsave(&s->lock, flags); 206 /* Rescan now that we hold the lock. */ 207 sid = sidtab_search_context(s, context); 208 if (sid) 209 goto unlock_out; 210 /* No SID exists for the context. Allocate a new one. */ 211 if (s->next_sid == UINT_MAX || s->shutdown) { 212 ret = -ENOMEM; 213 goto unlock_out; 214 } 215 sid = s->next_sid++; 216 if (context->len) 217 pr_info("SELinux: Context %s is not valid (left unmapped).\n", 218 context->str); 219 ret = sidtab_insert(s, sid, context); 220 if (ret) 221 s->next_sid--; 222 unlock_out: 223 spin_unlock_irqrestore(&s->lock, flags); 224 } 225 226 if (ret) 227 return ret; 228 229 *out_sid = sid; 230 return 0; 231 } 232 233 void sidtab_hash_eval(struct sidtab *h, char *tag) 234 { 235 int i, chain_len, slots_used, max_chain_len; 236 struct sidtab_node *cur; 237 238 slots_used = 0; 239 max_chain_len = 0; 240 for (i = 0; i < SIDTAB_SIZE; i++) { 241 cur = h->htable[i]; 242 if (cur) { 243 slots_used++; 244 chain_len = 0; 245 while (cur) { 246 chain_len++; 247 cur = cur->next; 248 } 249 250 if (chain_len > max_chain_len) 251 max_chain_len = chain_len; 252 } 253 } 254 255 pr_debug("%s: %d entries and %d/%d buckets used, longest " 256 "chain length %d\n", tag, h->nel, slots_used, SIDTAB_SIZE, 257 max_chain_len); 258 } 259 260 void sidtab_destroy(struct sidtab *s) 261 { 262 int i; 263 struct sidtab_node *cur, *temp; 264 265 if (!s) 266 return; 267 268 for (i = 0; i < SIDTAB_SIZE; i++) { 269 cur = s->htable[i]; 270 while (cur) { 271 temp = cur; 272 cur = cur->next; 273 context_destroy(&temp->context); 274 kfree(temp); 275 } 276 s->htable[i] = NULL; 277 } 278 kfree(s->htable); 279 s->htable = NULL; 280 s->nel = 0; 281 s->next_sid = 1; 282 } 283 284 void sidtab_set(struct sidtab *dst, struct sidtab *src) 285 { 286 unsigned long flags; 287 int i; 288 289 spin_lock_irqsave(&src->lock, flags); 290 dst->htable = src->htable; 291 dst->nel = src->nel; 292 dst->next_sid = src->next_sid; 293 dst->shutdown = 0; 294 for (i = 0; i < SIDTAB_CACHE_LEN; i++) 295 dst->cache[i] = NULL; 296 spin_unlock_irqrestore(&src->lock, flags); 297 } 298 299 void sidtab_shutdown(struct sidtab *s) 300 { 301 unsigned long flags; 302 303 spin_lock_irqsave(&s->lock, flags); 304 s->shutdown = 1; 305 spin_unlock_irqrestore(&s->lock, flags); 306 } 307