gen/asl_core.c

   1 /*
   2  * Copyright (c) 2007 Apple Inc.  All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * "Portions Copyright (c) 2007 Apple Inc.  All Rights
   7  * Reserved.  This file contains Original Code and/or Modifications of
   8  * Original Code as defined in and that are subject to the Apple Public
   9  * Source License Version 1.0 (the 'License').  You may not use this file
  10  * except in compliance with the License.  Please obtain a copy of the
  11  * License at http://www.apple.com/publicsource and read it before using
  12  * this file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  19  * License for the specific language governing rights and limitations
  20  * under the License."
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25 #include <asl_core.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <membership.h>
  29 #include <pthread.h>
  30
  31 /*
  32  * Message ID generation
  33  */
  34 static uint64_t _asl_core_msg_next_id = 1;
  35 static pthread_mutex_t msg_id_lock = PTHREAD_MUTEX_INITIALIZER;
  36
  37 #define mix(a, b, c) \
  38 { \
  39         a -= b; a -= c; a ^= (c>>13); \
  40         b -= c; b -= a; b ^= (a<< 8); \
  41         c -= a; c -= b; c ^= (b>>13); \
  42         a -= b; a -= c; a ^= (c>>12); \
  43         b -= c; b -= a; b ^= (a<<16); \
  44         c -= a; c -= b; c ^= (b>> 5); \
  45         a -= b; a -= c; a ^= (c>> 3); \
  46         b -= c; b -= a; b ^= (a<<10); \
  47         c -= a; c -= b; c ^= (b>>15); \
  48 }
  49
  50 /*
  51  * Hash is used to improve string search.
  52  */
  53 uint32_t
  54 asl_core_string_hash(const char *s, uint32_t inlen)
  55 {
  56         uint32_t a, b, c, l, len;
  57
  58         if (s == NULL) return 0;
  59
  60         l = inlen;
  61         if (l == 0)
  62         {
  63                 if (s[0] == '\0') return 0;
  64                 l = strlen(s);
  65         }
  66
  67         len = l;
  68         a = b = 0x9e3779b9;
  69         c = 0;
  70
  71         while (len >= 12)
  72         {
  73                 a += (s[0] + ((uint32_t)s[1]<<8) + ((uint32_t)s[ 2]<<16) + ((uint32_t)s[ 3]<<24));
  74                 b += (s[4] + ((uint32_t)s[5]<<8) + ((uint32_t)s[ 6]<<16) + ((uint32_t)s[ 7]<<24));
  75                 c += (s[8] + ((uint32_t)s[9]<<8) + ((uint32_t)s[10]<<16) + ((uint32_t)s[11]<<24));
  76
  77                 mix(a, b, c);
  78
  79                 s += 12;
  80                 len -= 12;
  81         }
  82
  83         c += l;
  84         switch(len)
  85         {
  86                 case 11: c += ((uint32_t)s[10]<<24);
  87                 case 10: c += ((uint32_t)s[9]<<16);
  88                 case 9 : c += ((uint32_t)s[8]<<8);
  89
  90                 case 8 : b += ((uint32_t)s[7]<<24);
  91                 case 7 : b += ((uint32_t)s[6]<<16);
  92                 case 6 : b += ((uint32_t)s[5]<<8);
  93                 case 5 : b += s[4];
  94
  95                 case 4 : a += ((uint32_t)s[3]<<24);
  96                 case 3 : a += ((uint32_t)s[2]<<16);
  97                 case 2 : a += ((uint32_t)s[1]<<8);
  98                 case 1 : a += s[0];
  99         }
 100
 101         mix(a, b, c);
 102
 103         if (c == 0) c = 1;
 104         return c;
 105 }
 106
 107 const char *
 108 asl_core_error(uint32_t code)
 109 {
 110         switch (code)
 111         {
 112                 case ASL_STATUS_OK: return "Operation Succeeded";
 113                 case ASL_STATUS_INVALID_ARG: return "Invalid Argument";
 114                 case ASL_STATUS_INVALID_STORE: return "Invalid Data Store";
 115                 case ASL_STATUS_INVALID_STRING: return "Invalid String";
 116                 case ASL_STATUS_INVALID_ID: return "Invalid ID Number";
 117                 case ASL_STATUS_INVALID_MESSAGE: return "Invalid Message";
 118                 case ASL_STATUS_NOT_FOUND: return "Not Found";
 119                 case ASL_STATUS_READ_FAILED: return "Read Operation Failed";
 120                 case ASL_STATUS_WRITE_FAILED: return "Write Operation Failed";
 121                 case ASL_STATUS_NO_MEMORY: return "System Memory Allocation Failed";
 122                 case ASL_STATUS_ACCESS_DENIED: return "Access Denied";
 123                 case ASL_STATUS_READ_ONLY: return "Read Only Access";
 124                 case ASL_STATUS_WRITE_ONLY: return "Write Only Access";
 125                 case ASL_STATUS_MATCH_FAILED: return "Match Failed";
 126                 case ASL_STATUS_NO_RECORDS: return "No More Records";
 127         }
 128
 129         return "Operation Failed";
 130 }
 131
 132 static uint32_t
 133 asl_core_check_user_access(int32_t msgu, int32_t readu)
 134 {
 135         /* -1 means anyone may read */
 136         if (msgu == -1) return ASL_STATUS_OK;
 137
 138         /* Check for exact match */
 139         if (msgu == readu) return ASL_STATUS_OK;
 140
 141         return ASL_STATUS_ACCESS_DENIED;
 142 }
 143
 144 static uint32_t
 145 asl_core_check_group_access(int32_t msgg, int32_t readu, int32_t readg)
 146 {
 147         int check;
 148         uuid_t uu, gu;
 149
 150         /* -1 means anyone may read */
 151         if (msgg == -1) return ASL_STATUS_OK;
 152
 153         /* Check for exact match */
 154         if (msgg == readg) return ASL_STATUS_OK;
 155
 156         /* Check if user (u) is in read group (msgg) */
 157         mbr_uid_to_uuid(readu, uu);
 158         mbr_gid_to_uuid(msgg, gu);
 159
 160         check = 0;
 161         mbr_check_membership(uu, gu, &check);
 162         if (check != 0) return ASL_STATUS_OK;
 163
 164         return ASL_STATUS_ACCESS_DENIED;
 165 }
 166
 167 uint32_t
 168 asl_core_check_access(int32_t msgu, int32_t msgg, int32_t readu, int32_t readg, uint16_t flags)
 169 {
 170         uint16_t uset, gset;
 171
 172         /* root (uid 0) may always read */
 173         if (readu == 0) return ASL_STATUS_OK;
 174
 175         uset = flags & ASL_MSG_FLAG_READ_UID_SET;
 176         gset = flags & ASL_MSG_FLAG_READ_GID_SET;
 177
 178         /* if no access controls are set, anyone may read */
 179         if ((uset | gset) == 0) return ASL_STATUS_OK;
 180
 181         /* if only uid is set, then access is only by uid match */
 182         if ((uset != 0) && (gset == 0)) return asl_core_check_user_access(msgu, readu);
 183
 184         /* if only gid is set, then access is only by gid match */
 185         if ((uset == 0) && (gset != 0)) return asl_core_check_group_access(msgg, readu, readg);
 186
 187         /* both uid and gid are set - check user, then group */
 188         if ((asl_core_check_user_access(msgu, readu)) == ASL_STATUS_OK) return ASL_STATUS_OK;
 189         return asl_core_check_group_access(msgg, readu, readg);
 190 }
 191
 192 uint64_t
 193 asl_core_htonq(uint64_t n)
 194 {
 195 #ifdef __BIG_ENDIAN__
 196         return n;
 197 #else
 198         u_int32_t t;
 199         union
 200         {
 201                 u_int64_t q;
 202                 u_int32_t l[2];
 203         } x;
 204
 205         x.q = n;
 206         t = x.l[0];
 207         x.l[0] = htonl(x.l[1]);
 208         x.l[1] = htonl(t);
 209
 210         return x.q;
 211 #endif
 212 }
 213
 214 uint64_t
 215 asl_core_ntohq(uint64_t n)
 216 {
 217 #ifdef __BIG_ENDIAN__
 218         return n;
 219 #else
 220         u_int32_t t;
 221         union
 222         {
 223                 u_int64_t q;
 224                 u_int32_t l[2];
 225         } x;
 226
 227         x.q = n;
 228         t = x.l[0];
 229         x.l[0] = ntohl(x.l[1]);
 230         x.l[1] = ntohl(t);
 231
 232         return x.q;
 233 #endif
 234 }
 235
 236 uint64_t
 237 asl_core_new_msg_id(uint64_t start)
 238 {
 239         uint64_t out;
 240
 241         pthread_mutex_lock(&msg_id_lock);
 242
 243         if (start != 0) _asl_core_msg_next_id = start;
 244
 245         out = _asl_core_msg_next_id;
 246         _asl_core_msg_next_id++;
 247
 248         pthread_mutex_unlock(&msg_id_lock);
 249
 250         return out;
 251 }
 252
 253 /*
 254  * asl_core_encode_buffer
 255  * encode arbitrary data as a C string without embedded zero (nul) characters
 256  *
 257  * The routine computes a histogram of the input buffer and finds
 258  * the two least frequently used non-nul chars (L[0] and L[1]).
 259  *
 260  * L[0] is used to stand in for nul.
 261  * L[1] is used as the escape character.
 262  * Occurrences of nul in the data are encoded as L[0]
 263  * Occurrences of L[0] in the data are encoded as the sequence L[1] 1.
 264  * Occurrences of L[1] in the data are encoded as the sequence L[1] 2.
 265  *
 266  * The output string is preceded by L[0] L[1], and is nul terminated.
 267  * The output length is 2 + n + N(L[0]) + N(L[1]) + 1
 268  * where N(x) is the number of occurrences of x in the input string.
 269  * The worst case occurs when all characters are equally frequent,
 270  * In that case the output size will less that 1% larger than the input.
 271  */
 272 char *
 273 asl_core_encode_buffer(const char *in, uint32_t len)
 274 {
 275         char *str;
 276         uint32_t i, j, k, outlen, breakit, min, hist[256];
 277         uint32_t lfu[2], save[2];
 278         uint8_t v;
 279
 280         if (in == NULL) return NULL;
 281         if (len == 0) return NULL;
 282
 283         memset(hist, 0, sizeof(hist));
 284         save[0] = 0;
 285         save[1] = 0;
 286
 287         for (i = 0; i < len; i++)
 288         {
 289                 v = in[i];
 290                 hist[v]++;
 291         }
 292
 293         for (j = 0; j < 2; j++)
 294         {
 295                 lfu[j] = 1;
 296                 min = hist[1];
 297
 298                 for (i = 2; i < 256; i++)
 299                 {
 300                         if (hist[i] < min)
 301                         {
 302                                 lfu[j] = i;
 303                                 min = hist[i];
 304
 305                                 /*
 306                                  * Stop if there are no occurances or character i in the input.
 307                                  * The minimum will never be less than zero.
 308                                  */
 309                                 if (min == 0) break;
 310
 311                                 /*
 312                                  * When looking for the second least frequently used character,
 313                                  * stop scanning if we hit the same minimum as we saw in the first
 314                                  * pass.  There will be no smaller values.
 315                                  */
 316                                 if ((j == 1) && (min == save[0])) break;
 317                         }
 318                 }
 319
 320                 save[j] = hist[lfu[j]];
 321                 hist[lfu[j]] = (uint32_t)-1;
 322         }
 323
 324         outlen = 2 + len + save[0] + save[1] + 1;
 325
 326         str = malloc(outlen);
 327         if (str == NULL) return NULL;
 328
 329         str[outlen - 1] = '\0';
 330
 331         str[0] = lfu[0];
 332         str[1] = lfu[1];
 333
 334         j = 2;
 335
 336         for (i = 0; i < len; i++)
 337         {
 338                 v = in[i];
 339                 if (v == 0)
 340                 {
 341                         str[j++] = lfu[0];
 342                         continue;
 343                 }
 344
 345                 breakit = 0;
 346                 for (k = 0; (k < 2) && (breakit == 0); k++)
 347                 {
 348                         if (v == lfu[k])
 349                         {
 350                                 str[j++] = lfu[1];
 351                                 str[j++] = k + 1;
 352                                 breakit = 1;
 353                         }
 354                 }
 355
 356                 if (breakit == 1) continue;
 357
 358                 str[j++] = v;
 359         }
 360
 361         return str;
 362 }
 363
 364 /*
 365  * asl_core_decode_buffer
 366  * decode a string produced by asl_encode_buffer to recreate the original data
 367  */
 368 int32_t
 369 asl_core_decode_buffer(const char *in, char **buf, uint32_t *len)
 370 {
 371         uint8_t v;
 372         uint32_t i, j, n, outlen;
 373         uint32_t lfu[2];
 374         char *out;
 375
 376         if (buf == NULL) return -1;
 377         if (len == NULL) return -1;
 378
 379         lfu[0] = in[0];
 380         lfu[1] = in[1];
 381
 382         outlen = 0;
 383
 384         /* strip trailing nul */
 385         n = strlen(in);
 386
 387         /* determine output length and check for invalid input */
 388         for (i = 2; i < n; i++)
 389         {
 390                 if (in[i] == lfu[1])
 391                 {
 392                         if ((i + 1) == n) return -1;
 393                         i++;
 394                         if ((in[i] < 1) || (in[i] > 2)) return -1;
 395                         outlen++;
 396                 }
 397                 else outlen++;
 398         }
 399
 400         if (outlen == 0) return -1;
 401
 402         out = malloc(outlen);
 403         if (out == NULL) return -1;
 404
 405         j = 0;
 406         for (i = 2; i < n; i++)
 407         {
 408                 v = in[i];
 409                 if (v == lfu[0])
 410                 {
 411                         out[j++] = 0;
 412                 }
 413                 else if (v == lfu[1])
 414                 {
 415                         i++;
 416                         v = in[i];
 417                         out[j++] = lfu[v - 1];
 418                 }
 419                 else out[j++] = v;
 420         }
 421
 422         *len = outlen;
 423         *buf = out;
 424         return 0;
 425 }