OSX/sec/SOSCircle/SecureObjectSync/SOSDigestVector.c

   1 /*
   2  * Copyright (c) 2013-2015 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24
  25 #include <Security/SecureObjectSync/SOSDigestVector.h>
  26 #include <utilities/SecCFError.h>
  27 #include <utilities/SecCFWrappers.h>
  28 #include <dispatch/dispatch.h>
  29 #include <stdlib.h>
  30
  31 CFStringRef kSOSDigestVectorErrorDomain = CFSTR("com.apple.security.sos.digestvector.error");
  32
  33 /* SOSDigestVector code. */
  34
  35 const size_t kMaxDVCapacity = (1024*1024L);  // roughly based on KVS limit, helps avoid integer overflow issues
  36
  37 static bool SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
  38     // Note that capacity is the number of digests it can hold, not the size in bytes
  39     // Already big enough.
  40     if (count <= dv->capacity)
  41         return true;
  42     // Too big
  43     if (count > kMaxDVCapacity) {
  44         secerror("Requesting too much space for digest vectors: %ld", count);
  45         return false;
  46     }
  47
  48     size_t capacity = (dv->capacity + 16) * 3 / 2;
  49     size_t digestSize = sizeof(*(dv->digest));
  50     if (capacity < count)
  51         capacity = count;
  52     dv->digest = reallocf(dv->digest, digestSize * capacity);
  53     if (dv->digest == NULL) {
  54         dv->count = 0;
  55         secerror("reallocf failed requesting space for digest vectors: %ld (bytes)", digestSize * capacity);
  56         return false;
  57     }
  58     dv->capacity = capacity;
  59     return true;
  60 }
  61
  62 static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
  63 {
  64         if (SOSDigestVectorEnsureCapacity(dv, dv->count + 1))
  65         memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
  66 }
  67
  68 void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
  69 {
  70     SOSDigestVectorAppendOrdered(dv, digest);
  71         dv->unsorted = true;
  72 }
  73
  74 static int SOSDigestCompare(const void *a, const void *b)
  75 {
  76         return memcmp(a, b, SOSDigestSize);
  77 }
  78
  79 // Remove duplicates from sorted manifest using minimal memmove() calls
  80 static void SOSDigestVectorUnique(struct SOSDigestVector *dv) {
  81     if (dv->count < 2 || dv->digest == NULL)
  82         return;
  83
  84     const uint8_t *prev = dv->digest[0];
  85     uint8_t *dest = dv->digest[1];
  86     const uint8_t *end = dv->digest[dv->count];
  87     const uint8_t *source = dest;
  88     for (const uint8_t *cur = source; cur < end; cur += SOSDigestSize) {
  89         int delta = SOSDigestCompare(prev, cur);
  90         if (delta < 0) {
  91             // Found a properly sorted element
  92             // 1) Extend the current region (prev is end of region pointer)
  93             // 2) Reset prev
  94             prev = cur;
  95         } else if (delta > 0) {
  96             // DigestVector wasn't sorted!
  97             assert(delta <= 0);
  98         } else {
  99             // Found a duplicate element
 100             // 1) Finish copy for current region up to previous element
 101             prev += SOSDigestSize;
 102             if (dest != source)
 103                 memmove(dest, source, prev - source);
 104             dest += prev - source;
 105             // 2) Skip remaining dupes
 106             if (cur < end) {
 107                 cur += SOSDigestSize;
 108                 while (cur < end) {
 109                     int delta = SOSDigestCompare(prev, cur);
 110                     assert(delta <= 0);
 111                     if (delta != 0) {
 112                         break;
 113                     }
 114                     cur += SOSDigestSize;
 115                 }
 116             }
 117             // cur now points to the first new element that hasn't yet been copied
 118             // 3) Set start of next region
 119             prev = cur;
 120             source = cur;
 121         }
 122     }
 123
 124     // Copy remainder of final region
 125     if (source < end) {
 126         prev += SOSDigestSize;
 127         if (dest != source)
 128             memmove(dest, source, prev - source);
 129         dest += prev - source;
 130     }
 131     dv->count = (dest - dv->digest[0]) / SOSDigestSize;
 132 }
 133
 134
 135 void SOSDigestVectorSort(struct SOSDigestVector *dv)
 136 {
 137     if (dv->unsorted && dv->digest) {
 138         qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
 139         dv->unsorted = false;
 140         SOSDigestVectorUnique(dv);
 141     }
 142 }
 143
 144 void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
 145 {
 146         // Uniqify in place (sort does this now for safety)
 147     if (dv->unsorted)
 148                 SOSDigestVectorSort(dv);
 149 }
 150
 151 void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
 152 {
 153     struct SOSDigestVector dv;
 154       dv = *dva;
 155     *dva = *dvb;
 156     *dvb = dv;
 157 }
 158
 159 bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
 160 {
 161     return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
 162 }
 163
 164 bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
 165 {
 166     if (dv->unsorted)
 167                 SOSDigestVectorSort(dv);
 168     return SOSDigestVectorContainsSorted(dv, digest);
 169 }
 170
 171 size_t SOSDigestVectorIndexOfSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
 172 {
 173     if (dv->digest) {
 174         const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
 175         return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
 176     } else {
 177         return -1;
 178     }
 179 }
 180
 181 size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
 182 {
 183         if (dv->unsorted)
 184                 SOSDigestVectorSort(dv);
 185     return SOSDigestVectorIndexOfSorted(dv, digest);
 186 }
 187
 188 void SOSDigestVectorFree(struct SOSDigestVector *dv)
 189 {
 190         free(dv->digest);
 191         dv->digest = NULL;
 192         dv->count = 0;
 193         dv->capacity = 0;
 194         dv->unsorted = false;
 195 }
 196
 197 void SOSDigestVectorApplySorted(const struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
 198 {
 199     bool stop = false;
 200         for (size_t ix = 0; !stop && ix < dv->count && dv->digest; ++ix) {
 201         with(dv->digest[ix], &stop);
 202         }
 203 }
 204
 205 void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
 206 {
 207         if (dv->unsorted)
 208                 SOSDigestVectorSort(dv);
 209     SOSDigestVectorApplySorted(dv, with);
 210 }
 211
 212 // TODO: Check for NDEBUG to disable skip dupes are release time.
 213 //#define SOSDVSKIPDUPES  0
 214 #define SOSDVSKIPDUPES  1
 215
 216 #if SOSDVSKIPDUPES
 217 #define SOSDVINCRIX(dv,ix) (SOSDigestVectorIncrementAndSkipDupes(dv,ix))
 218
 219 static size_t SOSIncrementAndSkipDupes(const uint8_t *digests, size_t count, const size_t ix) {
 220     size_t new_ix = ix;
 221     if (digests && new_ix < count) {
 222         while (++new_ix < count) {
 223             int delta = SOSDigestCompare(digests + ix * SOSDigestSize, digests + new_ix * SOSDigestSize);
 224             assert(delta <= 0);
 225             if (delta != 0)
 226                 break;
 227         }
 228     }
 229     return new_ix;
 230 }
 231
 232 static size_t SOSDigestVectorIncrementAndSkipDupes(const struct SOSDigestVector *dv, const size_t ix) {
 233     return SOSIncrementAndSkipDupes((const uint8_t *)dv->digest, dv->count, ix);
 234 }
 235
 236 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
 237                                           size_t count, const uint8_t *digests) {
 238     size_t ix = 0;
 239     while (ix < count) {
 240         SOSDigestVectorAppendOrdered(dv, digests + (ix * SOSDigestSize));
 241         ix = SOSIncrementAndSkipDupes(digests, count, ix);
 242     }
 243 }
 244
 245 #else /* !SOSDVSKIPDUPES */
 246
 247 #define SOSDVINCRIX(dv,ix) (ix + 1)
 248
 249 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
 250                                           size_t count, const uint8_t *digests) {
 251     if (count) {
 252         if (SOSDigestVectorEnsureCapacity(dv, dv->count + count))
 253             memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
 254         dv->count += count;
 255     }
 256 }
 257
 258 #endif /* !SOSDVSKIPDUPES */
 259
 260 void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 261                                     struct SOSDigestVector *dvintersect)
 262 {
 263     /* dvintersect should be empty to start. */
 264     assert(dvintersect->count == 0);
 265     size_t i1 = 0, i2 = 0;
 266     while (i1 < dv1->count && i2 < dv2->count) {
 267         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 268         if (delta == 0) {
 269             SOSDigestVectorAppendOrdered(dvintersect, dv1->digest[i1]);
 270             i1 = SOSDVINCRIX(dv1, i1);
 271             i2 = SOSDVINCRIX(dv2, i2);
 272         } else if (delta < 0) {
 273             i1 = SOSDVINCRIX(dv1, i1);
 274         } else {
 275             i2 = SOSDVINCRIX(dv2, i2);
 276         }
 277     }
 278 }
 279
 280 void SOSDigestVectorUnionSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 281                                 struct SOSDigestVector *dvunion)
 282 {
 283     /* dvunion should be empty to start. */
 284     assert(dvunion->count == 0);
 285     size_t i1 = 0, i2 = 0;
 286     while (i1 < dv1->count && i2 < dv2->count) {
 287         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 288         if (delta == 0) {
 289             SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
 290             i1 = SOSDVINCRIX(dv1, i1);
 291             i2 = SOSDVINCRIX(dv2, i2);
 292         } else if (delta < 0) {
 293             SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
 294             i1 = SOSDVINCRIX(dv1, i1);
 295         } else {
 296             SOSDigestVectorAppendOrdered(dvunion, dv2->digest[i2]);
 297             i2 = SOSDVINCRIX(dv2, i2);
 298         }
 299     }
 300     SOSDigestVectorAppendMultipleOrdered(dvunion, dv1->count - i1, dv1->digest[i1]);
 301     SOSDigestVectorAppendMultipleOrdered(dvunion, dv2->count - i2, dv2->digest[i2]);
 302 }
 303
 304 void SOSDigestVectorDiffSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 305                                struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
 306 {
 307     /* dv1_2 and dv2_1 should be empty to start. */
 308     assert(dv1_2->count == 0);
 309     assert(dv2_1->count == 0);
 310
 311     size_t i1 = 0, i2 = 0;
 312     while (i1 < dv1->count && i2 < dv2->count) {
 313         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 314         if (delta == 0) {
 315             i1 = SOSDVINCRIX(dv1, i1);
 316             i2 = SOSDVINCRIX(dv2, i2);
 317         } else if (delta < 0) {
 318             SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1]);
 319             i1 = SOSDVINCRIX(dv1, i1);
 320         } else {
 321             SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2]);
 322             i2 = SOSDVINCRIX(dv2, i2);
 323         }
 324     }
 325     SOSDigestVectorAppendMultipleOrdered(dv1_2, dv1->count - i1, dv1->digest[i1]);
 326     SOSDigestVectorAppendMultipleOrdered(dv2_1, dv2->count - i2, dv2->digest[i2]);
 327 }
 328
 329 void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
 330                          struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
 331 {
 332     if (dv1->unsorted) SOSDigestVectorSort(dv1);
 333         if (dv2->unsorted) SOSDigestVectorSort(dv2);
 334     SOSDigestVectorDiffSorted(dv1, dv2, dv1_2, dv2_1);
 335 }
 336
 337 /*
 338  If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A,
 339  is the set of elements in B, but not in A. The relative complement of A in B is denoted B ∖ A according to the ISO 31-11 standard
 340  sometimes written B − A
 341
 342  The common case for us will be Removals\Additions
 343  */
 344
 345 static void SOSDigestVectorAppendComplementAtIndex(size_t a_ix, const struct SOSDigestVector *dvA, size_t b_ix, const struct SOSDigestVector *dvB,
 346                                      struct SOSDigestVector *dvcomplement)
 347 {
 348     assert(a_ix <= dvA->count && b_ix <= dvB->count);
 349     while (a_ix < dvA->count && b_ix < dvB->count && dvA->digest && dvB->digest) {
 350         int delta = SOSDigestCompare(dvA->digest[a_ix], dvB->digest[b_ix]);
 351         if (delta == 0) {
 352             a_ix = SOSDVINCRIX(dvA, a_ix);
 353             b_ix = SOSDVINCRIX(dvB, b_ix);
 354         } else if (delta < 0) {
 355             a_ix = SOSDVINCRIX(dvA, a_ix);
 356         } else {
 357             SOSDigestVectorAppendOrdered(dvcomplement, dvB->digest[b_ix]);
 358             b_ix = SOSDVINCRIX(dvB, b_ix);
 359         }
 360     }
 361     if (dvB->digest)
 362         SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
 363 }
 364
 365
 366 void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
 367                                      struct SOSDigestVector *dvcomplement)
 368 {
 369     /* dvcomplement should be empty to start. */
 370     assert(dvcomplement->count == 0);
 371     assert(!dvA->unsorted);
 372         assert(!dvB->unsorted);
 373
 374     SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
 375 }
 376
 377
 378 /*
 379     For each item in base
 380
 381  one way to do would be to define SOSDigestVectorComplementSorted
 382
 383  For removals, if removal value is less than base, increment until GEQ
 384  */
 385 bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
 386                                 const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
 387                                 CFErrorRef *error)
 388 {
 389     /* dv should be empty to start. */
 390     assert(dv->count == 0);
 391     assert(!base->unsorted);
 392         assert(!removals->unsorted);
 393         assert(!additions->unsorted);
 394
 395     size_t i1 = 0, i2 = 0, i3 = 0;
 396     while (i1 < base->count && i2 < additions->count) {
 397         // Pick the smaller of base->digest[i1] and additions->digest[i2] as a
 398         // candidate to be put into the output vector. If udelta positive, addition is smaller
 399         int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
 400         const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
 401
 402         // ddelta > 0 means rem > candidate
 403         int ddelta = 1;
 404         while (i3 < removals->count) {
 405             ddelta = SOSDigestCompare(removals->digest[i3], candidate);
 406             if (ddelta < 0) {
 407                 i3 = SOSDVINCRIX(removals, i3);
 408             } else {
 409                 if (ddelta == 0)
 410                     i3 = SOSDVINCRIX(removals, i3);
 411                 break;
 412             }
 413         }
 414         if (ddelta > 0)
 415             SOSDigestVectorAppendOrdered(dv, candidate);
 416
 417         // Point to next (different) candidate
 418         if (udelta == 0) {
 419             i1 = SOSDVINCRIX(base, i1);
 420             i2 = SOSDVINCRIX(additions, i2);
 421         } else if (udelta < 0) {
 422             i1 = SOSDVINCRIX(base, i1);
 423         } else {
 424             i2 = SOSDVINCRIX(additions, i2);
 425         }
 426     }
 427     SOSDigestVectorAppendComplementAtIndex(i3, removals, i1, base, dv);
 428     SOSDigestVectorAppendComplementAtIndex(i3, removals, i2, additions, dv);
 429
 430     return true;
 431 }
 432
 433 bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
 434                           struct SOSDigestVector *additions, struct SOSDigestVector *dv,
 435                           CFErrorRef *error)
 436 {
 437         if (base->unsorted) SOSDigestVectorSort(base);
 438         if (removals->unsorted) SOSDigestVectorSort(removals);
 439         if (additions->unsorted) SOSDigestVectorSort(additions);
 440     return SOSDigestVectorPatchSorted(base, removals, additions, dv, error);
 441 }