security/selinux/ss/sidtab.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Implementation of the SID table type.
   4  *
   5  * Original author: Stephen Smalley, <sds@tycho.nsa.gov>
   6  * Author: Ondrej Mosnacek, <omosnacek@gmail.com>
   7  *
   8  * Copyright (C) 2018 Red Hat, Inc.
   9  */
  10 #include <linux/errno.h>
  11 #include <linux/kernel.h>
  12 #include <linux/slab.h>
  13 #include <linux/sched.h>
  14 #include <linux/spinlock.h>
  15 #include <asm/barrier.h>
  16 #include "flask.h"
  17 #include "security.h"
  18 #include "sidtab.h"
  19
  20 int sidtab_init(struct sidtab *s)
  21 {
  22         u32 i;
  23
  24         memset(s->roots, 0, sizeof(s->roots));
  25
  26         /* max count is SIDTAB_MAX so valid index is always < SIDTAB_MAX */
  27         for (i = 0; i < SIDTAB_RCACHE_SIZE; i++)
  28                 s->rcache[i] = SIDTAB_MAX;
  29
  30         for (i = 0; i < SECINITSID_NUM; i++)
  31                 s->isids[i].set = 0;
  32
  33         s->count = 0;
  34         s->convert = NULL;
  35
  36         spin_lock_init(&s->lock);
  37         return 0;
  38 }
  39
  40 int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
  41 {
  42         struct sidtab_isid_entry *entry;
  43         int rc;
  44
  45         if (sid == 0 || sid > SECINITSID_NUM)
  46                 return -EINVAL;
  47
  48         entry = &s->isids[sid - 1];
  49
  50         rc = context_cpy(&entry->context, context);
  51         if (rc)
  52                 return rc;
  53
  54         entry->set = 1;
  55         return 0;
  56 }
  57
  58 static u32 sidtab_level_from_count(u32 count)
  59 {
  60         u32 capacity = SIDTAB_LEAF_ENTRIES;
  61         u32 level = 0;
  62
  63         while (count > capacity) {
  64                 capacity <<= SIDTAB_INNER_SHIFT;
  65                 ++level;
  66         }
  67         return level;
  68 }
  69
  70 static int sidtab_alloc_roots(struct sidtab *s, u32 level)
  71 {
  72         u32 l;
  73
  74         if (!s->roots[0].ptr_leaf) {
  75                 s->roots[0].ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
  76                                                GFP_ATOMIC);
  77                 if (!s->roots[0].ptr_leaf)
  78                         return -ENOMEM;
  79         }
  80         for (l = 1; l <= level; ++l)
  81                 if (!s->roots[l].ptr_inner) {
  82                         s->roots[l].ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
  83                                                         GFP_ATOMIC);
  84                         if (!s->roots[l].ptr_inner)
  85                                 return -ENOMEM;
  86                         s->roots[l].ptr_inner->entries[0] = s->roots[l - 1];
  87                 }
  88         return 0;
  89 }
  90
  91 static struct context *sidtab_do_lookup(struct sidtab *s, u32 index, int alloc)
  92 {
  93         union sidtab_entry_inner *entry;
  94         u32 level, capacity_shift, leaf_index = index / SIDTAB_LEAF_ENTRIES;
  95
  96         /* find the level of the subtree we need */
  97         level = sidtab_level_from_count(index + 1);
  98         capacity_shift = level * SIDTAB_INNER_SHIFT;
  99
 100         /* allocate roots if needed */
 101         if (alloc && sidtab_alloc_roots(s, level) != 0)
 102                 return NULL;
 103
 104         /* lookup inside the subtree */
 105         entry = &s->roots[level];
 106         while (level != 0) {
 107                 capacity_shift -= SIDTAB_INNER_SHIFT;
 108                 --level;
 109
 110                 entry = &entry->ptr_inner->entries[leaf_index >> capacity_shift];
 111                 leaf_index &= ((u32)1 << capacity_shift) - 1;
 112
 113                 if (!entry->ptr_inner) {
 114                         if (alloc)
 115                                 entry->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
 116                                                            GFP_ATOMIC);
 117                         if (!entry->ptr_inner)
 118                                 return NULL;
 119                 }
 120         }
 121         if (!entry->ptr_leaf) {
 122                 if (alloc)
 123                         entry->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
 124                                                   GFP_ATOMIC);
 125                 if (!entry->ptr_leaf)
 126                         return NULL;
 127         }
 128         return &entry->ptr_leaf->entries[index % SIDTAB_LEAF_ENTRIES].context;
 129 }
 130
 131 static struct context *sidtab_lookup(struct sidtab *s, u32 index)
 132 {
 133         /* read entries only after reading count */
 134         u32 count = smp_load_acquire(&s->count);
 135
 136         if (index >= count)
 137                 return NULL;
 138
 139         return sidtab_do_lookup(s, index, 0);
 140 }
 141
 142 static struct context *sidtab_lookup_initial(struct sidtab *s, u32 sid)
 143 {
 144         return s->isids[sid - 1].set ? &s->isids[sid - 1].context : NULL;
 145 }
 146
 147 static struct context *sidtab_search_core(struct sidtab *s, u32 sid, int force)
 148 {
 149         struct context *context;
 150
 151         if (sid != 0) {
 152                 if (sid > SECINITSID_NUM)
 153                         context = sidtab_lookup(s, sid - (SECINITSID_NUM + 1));
 154                 else
 155                         context = sidtab_lookup_initial(s, sid);
 156                 if (context && (!context->len || force))
 157                         return context;
 158         }
 159
 160         return sidtab_lookup_initial(s, SECINITSID_UNLABELED);
 161 }
 162
 163 struct context *sidtab_search(struct sidtab *s, u32 sid)
 164 {
 165         return sidtab_search_core(s, sid, 0);
 166 }
 167
 168 struct context *sidtab_search_force(struct sidtab *s, u32 sid)
 169 {
 170         return sidtab_search_core(s, sid, 1);
 171 }
 172
 173 static int sidtab_find_context(union sidtab_entry_inner entry,
 174                                u32 *pos, u32 count, u32 level,
 175                                struct context *context, u32 *index)
 176 {
 177         int rc;
 178         u32 i;
 179
 180         if (level != 0) {
 181                 struct sidtab_node_inner *node = entry.ptr_inner;
 182
 183                 i = 0;
 184                 while (i < SIDTAB_INNER_ENTRIES && *pos < count) {
 185                         rc = sidtab_find_context(node->entries[i],
 186                                                  pos, count, level - 1,
 187                                                  context, index);
 188                         if (rc == 0)
 189                                 return 0;
 190                         i++;
 191                 }
 192         } else {
 193                 struct sidtab_node_leaf *node = entry.ptr_leaf;
 194
 195                 i = 0;
 196                 while (i < SIDTAB_LEAF_ENTRIES && *pos < count) {
 197                         if (context_cmp(&node->entries[i].context, context)) {
 198                                 *index = *pos;
 199                                 return 0;
 200                         }
 201                         (*pos)++;
 202                         i++;
 203                 }
 204         }
 205         return -ENOENT;
 206 }
 207
 208 static void sidtab_rcache_update(struct sidtab *s, u32 index, u32 pos)
 209 {
 210         while (pos > 0) {
 211                 WRITE_ONCE(s->rcache[pos], READ_ONCE(s->rcache[pos - 1]));
 212                 --pos;
 213         }
 214         WRITE_ONCE(s->rcache[0], index);
 215 }
 216
 217 static void sidtab_rcache_push(struct sidtab *s, u32 index)
 218 {
 219         sidtab_rcache_update(s, index, SIDTAB_RCACHE_SIZE - 1);
 220 }
 221
 222 static int sidtab_rcache_search(struct sidtab *s, struct context *context,
 223                                 u32 *index)
 224 {
 225         u32 i;
 226
 227         for (i = 0; i < SIDTAB_RCACHE_SIZE; i++) {
 228                 u32 v = READ_ONCE(s->rcache[i]);
 229
 230                 if (v >= SIDTAB_MAX)
 231                         continue;
 232
 233                 if (context_cmp(sidtab_do_lookup(s, v, 0), context)) {
 234                         sidtab_rcache_update(s, v, i);
 235                         *index = v;
 236                         return 0;
 237                 }
 238         }
 239         return -ENOENT;
 240 }
 241
 242 static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
 243                                  u32 *index)
 244 {
 245         unsigned long flags;
 246         u32 count, count_locked, level, pos;
 247         struct sidtab_convert_params *convert;
 248         struct context *dst, *dst_convert;
 249         int rc;
 250
 251         rc = sidtab_rcache_search(s, context, index);
 252         if (rc == 0)
 253                 return 0;
 254
 255         /* read entries only after reading count */
 256         count = smp_load_acquire(&s->count);
 257         level = sidtab_level_from_count(count);
 258
 259         pos = 0;
 260         rc = sidtab_find_context(s->roots[level], &pos, count, level,
 261                                  context, index);
 262         if (rc == 0) {
 263                 sidtab_rcache_push(s, *index);
 264                 return 0;
 265         }
 266
 267         /* lock-free search failed: lock, re-search, and insert if not found */
 268         spin_lock_irqsave(&s->lock, flags);
 269
 270         convert = s->convert;
 271         count_locked = s->count;
 272         level = sidtab_level_from_count(count_locked);
 273
 274         /* if count has changed before we acquired the lock, then catch up */
 275         while (count < count_locked) {
 276                 if (context_cmp(sidtab_do_lookup(s, count, 0), context)) {
 277                         sidtab_rcache_push(s, count);
 278                         *index = count;
 279                         rc = 0;
 280                         goto out_unlock;
 281                 }
 282                 ++count;
 283         }
 284
 285         /* bail out if we already reached max entries */
 286         rc = -EOVERFLOW;
 287         if (count >= SIDTAB_MAX)
 288                 goto out_unlock;
 289
 290         /* insert context into new entry */
 291         rc = -ENOMEM;
 292         dst = sidtab_do_lookup(s, count, 1);
 293         if (!dst)
 294                 goto out_unlock;
 295
 296         rc = context_cpy(dst, context);
 297         if (rc)
 298                 goto out_unlock;
 299
 300         /*
 301          * if we are building a new sidtab, we need to convert the context
 302          * and insert it there as well
 303          */
 304         if (convert) {
 305                 rc = -ENOMEM;
 306                 dst_convert = sidtab_do_lookup(convert->target, count, 1);
 307                 if (!dst_convert) {
 308                         context_destroy(dst);
 309                         goto out_unlock;
 310                 }
 311
 312                 rc = convert->func(context, dst_convert, convert->args);
 313                 if (rc) {
 314                         context_destroy(dst);
 315                         goto out_unlock;
 316                 }
 317
 318                 /* at this point we know the insert won't fail */
 319                 convert->target->count = count + 1;
 320         }
 321
 322         if (context->len)
 323                 pr_info("SELinux:  Context %s is not valid (left unmapped).\n",
 324                         context->str);
 325
 326         sidtab_rcache_push(s, count);
 327         *index = count;
 328
 329         /* write entries before writing new count */
 330         smp_store_release(&s->count, count + 1);
 331
 332         rc = 0;
 333 out_unlock:
 334         spin_unlock_irqrestore(&s->lock, flags);
 335         return rc;
 336 }
 337
 338 int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid)
 339 {
 340         int rc;
 341         u32 i;
 342
 343         for (i = 0; i < SECINITSID_NUM; i++) {
 344                 struct sidtab_isid_entry *entry = &s->isids[i];
 345
 346                 if (entry->set && context_cmp(context, &entry->context)) {
 347                         *sid = i + 1;
 348                         return 0;
 349                 }
 350         }
 351
 352         rc = sidtab_reverse_lookup(s, context, sid);
 353         if (rc)
 354                 return rc;
 355         *sid += SECINITSID_NUM + 1;
 356         return 0;
 357 }
 358
 359 static int sidtab_convert_tree(union sidtab_entry_inner *edst,
 360                                union sidtab_entry_inner *esrc,
 361                                u32 *pos, u32 count, u32 level,
 362                                struct sidtab_convert_params *convert)
 363 {
 364         int rc;
 365         u32 i;
 366
 367         if (level != 0) {
 368                 if (!edst->ptr_inner) {
 369                         edst->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
 370                                                   GFP_KERNEL);
 371                         if (!edst->ptr_inner)
 372                                 return -ENOMEM;
 373                 }
 374                 i = 0;
 375                 while (i < SIDTAB_INNER_ENTRIES && *pos < count) {
 376                         rc = sidtab_convert_tree(&edst->ptr_inner->entries[i],
 377                                                  &esrc->ptr_inner->entries[i],
 378                                                  pos, count, level - 1,
 379                                                  convert);
 380                         if (rc)
 381                                 return rc;
 382                         i++;
 383                 }
 384         } else {
 385                 if (!edst->ptr_leaf) {
 386                         edst->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE,
 387                                                  GFP_KERNEL);
 388                         if (!edst->ptr_leaf)
 389                                 return -ENOMEM;
 390                 }
 391                 i = 0;
 392                 while (i < SIDTAB_LEAF_ENTRIES && *pos < count) {
 393                         rc = convert->func(&esrc->ptr_leaf->entries[i].context,
 394                                            &edst->ptr_leaf->entries[i].context,
 395                                            convert->args);
 396                         if (rc)
 397                                 return rc;
 398                         (*pos)++;
 399                         i++;
 400                 }
 401                 cond_resched();
 402         }
 403         return 0;
 404 }
 405
 406 int sidtab_convert(struct sidtab *s, struct sidtab_convert_params *params)
 407 {
 408         unsigned long flags;
 409         u32 count, level, pos;
 410         int rc;
 411
 412         spin_lock_irqsave(&s->lock, flags);
 413
 414         /* concurrent policy loads are not allowed */
 415         if (s->convert) {
 416                 spin_unlock_irqrestore(&s->lock, flags);
 417                 return -EBUSY;
 418         }
 419
 420         count = s->count;
 421         level = sidtab_level_from_count(count);
 422
 423         /* allocate last leaf in the new sidtab (to avoid race with
 424          * live convert)
 425          */
 426         rc = sidtab_do_lookup(params->target, count - 1, 1) ? 0 : -ENOMEM;
 427         if (rc) {
 428                 spin_unlock_irqrestore(&s->lock, flags);
 429                 return rc;
 430         }
 431
 432         /* set count in case no new entries are added during conversion */
 433         params->target->count = count;
 434
 435         /* enable live convert of new entries */
 436         s->convert = params;
 437
 438         /* we can safely do the rest of the conversion outside the lock */
 439         spin_unlock_irqrestore(&s->lock, flags);
 440
 441         pr_info("SELinux:  Converting %u SID table entries...\n", count);
 442
 443         /* convert all entries not covered by live convert */
 444         pos = 0;
 445         rc = sidtab_convert_tree(&params->target->roots[level],
 446                                  &s->roots[level], &pos, count, level, params);
 447         if (rc) {
 448                 /* we need to keep the old table - disable live convert */
 449                 spin_lock_irqsave(&s->lock, flags);
 450                 s->convert = NULL;
 451                 spin_unlock_irqrestore(&s->lock, flags);
 452         }
 453         return rc;
 454 }
 455
 456 static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level)
 457 {
 458         u32 i;
 459
 460         if (level != 0) {
 461                 struct sidtab_node_inner *node = entry.ptr_inner;
 462
 463                 if (!node)
 464                         return;
 465
 466                 for (i = 0; i < SIDTAB_INNER_ENTRIES; i++)
 467                         sidtab_destroy_tree(node->entries[i], level - 1);
 468                 kfree(node);
 469         } else {
 470                 struct sidtab_node_leaf *node = entry.ptr_leaf;
 471
 472                 if (!node)
 473                         return;
 474
 475                 for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++)
 476                         context_destroy(&node->entries[i].context);
 477                 kfree(node);
 478         }
 479 }
 480
 481 void sidtab_destroy(struct sidtab *s)
 482 {
 483         u32 i, level;
 484
 485         for (i = 0; i < SECINITSID_NUM; i++)
 486                 if (s->isids[i].set)
 487                         context_destroy(&s->isids[i].context);
 488
 489         level = SIDTAB_MAX_LEVEL;
 490         while (level && !s->roots[level].ptr_inner)
 491                 --level;
 492
 493         sidtab_destroy_tree(s->roots[level], level);
 494 }