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 (digest && SOSDigestVectorEnsureCapacity(dv, dv->count + 1)) {
  65         memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
  66     }
  67 }
  68
  69 void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
  70 {
  71     SOSDigestVectorAppendOrdered(dv, digest);
  72         dv->unsorted = true;
  73 }
  74
  75 static int SOSDigestCompare(const void *a, const void *b)
  76 {
  77         return memcmp(a, b, SOSDigestSize);
  78 }
  79
  80 // Remove duplicates from sorted manifest using minimal memmove() calls
  81 static void SOSDigestVectorUnique(struct SOSDigestVector *dv) {
  82     if (dv->count < 2 || dv->digest == NULL)
  83         return;
  84
  85     const uint8_t *prev = dv->digest[0];
  86     uint8_t *dest = dv->digest[1];
  87     const uint8_t *end = dv->digest[dv->count];
  88     const uint8_t *source = dest;
  89     for (const uint8_t *cur = source; cur < end; cur += SOSDigestSize) {
  90         int delta = SOSDigestCompare(prev, cur);
  91         if (delta < 0) {
  92             // Found a properly sorted element
  93             // 1) Extend the current region (prev is end of region pointer)
  94             // 2) Reset prev
  95             prev = cur;
  96         } else if (delta > 0) {
  97             // DigestVector wasn't sorted!
  98             assert(delta <= 0);
  99         } else {
 100             // Found a duplicate element
 101             // 1) Finish copy for current region up to previous element
 102             prev += SOSDigestSize;
 103             if (dest != source)
 104                 memmove(dest, source, prev - source);
 105             dest += prev - source;
 106             // 2) Skip remaining dupes
 107             if (cur < end) {
 108                 cur += SOSDigestSize;
 109                 while (cur < end) {
 110                     int delta = SOSDigestCompare(prev, cur);
 111                     assert(delta <= 0);
 112                     if (delta != 0) {
 113                         break;
 114                     }
 115                     cur += SOSDigestSize;
 116                 }
 117             }
 118             // cur now points to the first new element that hasn't yet been copied
 119             // 3) Set start of next region
 120             prev = cur;
 121             source = cur;
 122         }
 123     }
 124
 125     // Copy remainder of final region
 126     if (source < end) {
 127         prev += SOSDigestSize;
 128         if (dest != source)
 129             memmove(dest, source, prev - source);
 130         dest += prev - source;
 131     }
 132     dv->count = (dest - dv->digest[0]) / SOSDigestSize;
 133 }
 134
 135
 136 void SOSDigestVectorSort(struct SOSDigestVector *dv)
 137 {
 138     if (dv->unsorted && dv->digest) {
 139         qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
 140         dv->unsorted = false;
 141         SOSDigestVectorUnique(dv);
 142     }
 143 }
 144
 145 void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
 146 {
 147         // Uniqify in place (sort does this now for safety)
 148     if (dv->unsorted)
 149                 SOSDigestVectorSort(dv);
 150 }
 151
 152 void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
 153 {
 154     struct SOSDigestVector dv;
 155       dv = *dva;
 156     *dva = *dvb;
 157     *dvb = dv;
 158 }
 159
 160 bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
 161 {
 162     return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
 163 }
 164
 165 bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
 166 {
 167     if (dv->unsorted)
 168                 SOSDigestVectorSort(dv);
 169     return SOSDigestVectorContainsSorted(dv, digest);
 170 }
 171
 172 size_t SOSDigestVectorIndexOfSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
 173 {
 174     if (dv->digest) {
 175         const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
 176         return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
 177     } else {
 178         return -1;
 179     }
 180 }
 181
 182 size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
 183 {
 184         if (dv->unsorted)
 185                 SOSDigestVectorSort(dv);
 186     return SOSDigestVectorIndexOfSorted(dv, digest);
 187 }
 188
 189 void SOSDigestVectorFree(struct SOSDigestVector *dv)
 190 {
 191         free(dv->digest);
 192         dv->digest = NULL;
 193         dv->count = 0;
 194         dv->capacity = 0;
 195         dv->unsorted = false;
 196 }
 197
 198 void SOSDigestVectorApplySorted(const struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
 199 {
 200     bool stop = false;
 201         for (size_t ix = 0; !stop && ix < dv->count && dv->digest; ++ix) {
 202         with(dv->digest[ix], &stop);
 203         }
 204 }
 205
 206 void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
 207 {
 208         if (dv->unsorted)
 209                 SOSDigestVectorSort(dv);
 210     SOSDigestVectorApplySorted(dv, with);
 211 }
 212
 213 // TODO: Check for NDEBUG to disable skip dupes are release time.
 214 //#define SOSDVSKIPDUPES  0
 215 #define SOSDVSKIPDUPES  1
 216
 217 #if SOSDVSKIPDUPES
 218 #define SOSDVINCRIX(dv,ix) (SOSDigestVectorIncrementAndSkipDupes(dv,ix))
 219
 220 static size_t SOSIncrementAndSkipDupes(const uint8_t *digests, size_t count, const size_t ix) {
 221     size_t new_ix = ix;
 222     if (digests && new_ix < count) {
 223         while (++new_ix < count) {
 224             int delta = SOSDigestCompare(digests + ix * SOSDigestSize, digests + new_ix * SOSDigestSize);
 225             assert(delta <= 0);
 226             if (delta != 0)
 227                 break;
 228         }
 229     }
 230     return new_ix;
 231 }
 232
 233 static size_t SOSDigestVectorIncrementAndSkipDupes(const struct SOSDigestVector *dv, const size_t ix) {
 234     return SOSIncrementAndSkipDupes((const uint8_t *)dv->digest, dv->count, ix);
 235 }
 236
 237 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
 238                                           size_t count, const uint8_t *digests) {
 239     size_t ix = 0;
 240     while (ix < count) {
 241         SOSDigestVectorAppendOrdered(dv, digests + (ix * SOSDigestSize));
 242         ix = SOSIncrementAndSkipDupes(digests, count, ix);
 243     }
 244 }
 245
 246 #else /* !SOSDVSKIPDUPES */
 247
 248 #define SOSDVINCRIX(dv,ix) (ix + 1)
 249
 250 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
 251                                           size_t count, const uint8_t *digests) {
 252     if (count) {
 253         if (SOSDigestVectorEnsureCapacity(dv, dv->count + count))
 254             memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
 255         dv->count += count;
 256     }
 257 }
 258
 259 #endif /* !SOSDVSKIPDUPES */
 260
 261 void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 262                                     struct SOSDigestVector *dvintersect)
 263 {
 264     /* dvintersect should be empty to start. */
 265     assert(dvintersect->count == 0);
 266     size_t i1 = 0, i2 = 0;
 267     while (i1 < dv1->count && i2 < dv2->count) {
 268         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 269         if (delta == 0) {
 270             SOSDigestVectorAppendOrdered(dvintersect, dv1->digest[i1]);
 271             i1 = SOSDVINCRIX(dv1, i1);
 272             i2 = SOSDVINCRIX(dv2, i2);
 273         } else if (delta < 0) {
 274             i1 = SOSDVINCRIX(dv1, i1);
 275         } else {
 276             i2 = SOSDVINCRIX(dv2, i2);
 277         }
 278     }
 279 }
 280
 281 void SOSDigestVectorUnionSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 282                                 struct SOSDigestVector *dvunion)
 283 {
 284     /* dvunion should be empty to start. */
 285     assert(dvunion->count == 0);
 286     size_t i1 = 0, i2 = 0;
 287     while (i1 < dv1->count && i2 < dv2->count) {
 288         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 289         if (delta == 0) {
 290             SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
 291             i1 = SOSDVINCRIX(dv1, i1);
 292             i2 = SOSDVINCRIX(dv2, i2);
 293         } else if (delta < 0) {
 294             SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
 295             i1 = SOSDVINCRIX(dv1, i1);
 296         } else {
 297             SOSDigestVectorAppendOrdered(dvunion, dv2->digest[i2]);
 298             i2 = SOSDVINCRIX(dv2, i2);
 299         }
 300     }
 301     SOSDigestVectorAppendMultipleOrdered(dvunion, dv1->count - i1, dv1->digest[i1]);
 302     SOSDigestVectorAppendMultipleOrdered(dvunion, dv2->count - i2, dv2->digest[i2]);
 303 }
 304
 305 void SOSDigestVectorDiffSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
 306                                struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
 307 {
 308     /* dv1_2 and dv2_1 should be empty to start. */
 309     assert(dv1_2->count == 0);
 310     assert(dv2_1->count == 0);
 311
 312     size_t i1 = 0, i2 = 0;
 313     while (i1 < dv1->count && i2 < dv2->count) {
 314         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 315         if (delta == 0) {
 316             i1 = SOSDVINCRIX(dv1, i1);
 317             i2 = SOSDVINCRIX(dv2, i2);
 318         } else if (delta < 0) {
 319             SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1]);
 320             i1 = SOSDVINCRIX(dv1, i1);
 321         } else {
 322             SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2]);
 323             i2 = SOSDVINCRIX(dv2, i2);
 324         }
 325     }
 326     SOSDigestVectorAppendMultipleOrdered(dv1_2, dv1->count - i1, dv1->digest[i1]);
 327     SOSDigestVectorAppendMultipleOrdered(dv2_1, dv2->count - i2, dv2->digest[i2]);
 328 }
 329
 330 void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
 331                          struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
 332 {
 333     if (dv1->unsorted) SOSDigestVectorSort(dv1);
 334         if (dv2->unsorted) SOSDigestVectorSort(dv2);
 335     SOSDigestVectorDiffSorted(dv1, dv2, dv1_2, dv2_1);
 336 }
 337
 338 /*
 339  If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A,
 340  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
 341  sometimes written B − A
 342
 343  The common case for us will be Removals\Additions
 344  */
 345
 346 static void SOSDigestVectorAppendComplementAtIndex(size_t a_ix, const struct SOSDigestVector *dvA, size_t b_ix, const struct SOSDigestVector *dvB,
 347                                      struct SOSDigestVector *dvcomplement)
 348 {
 349     assert(a_ix <= dvA->count && b_ix <= dvB->count);
 350     while (a_ix < dvA->count && b_ix < dvB->count && dvA->digest && dvB->digest) {
 351         int delta = SOSDigestCompare(dvA->digest[a_ix], dvB->digest[b_ix]);
 352         if (delta == 0) {
 353             a_ix = SOSDVINCRIX(dvA, a_ix);
 354             b_ix = SOSDVINCRIX(dvB, b_ix);
 355         } else if (delta < 0) {
 356             a_ix = SOSDVINCRIX(dvA, a_ix);
 357         } else {
 358             SOSDigestVectorAppendOrdered(dvcomplement, dvB->digest[b_ix]);
 359             b_ix = SOSDVINCRIX(dvB, b_ix);
 360         }
 361     }
 362     if (dvB->digest)
 363         SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
 364 }
 365
 366
 367 void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
 368                                      struct SOSDigestVector *dvcomplement)
 369 {
 370     /* dvcomplement should be empty to start. */
 371     assert(dvcomplement->count == 0);
 372     assert(!dvA->unsorted);
 373         assert(!dvB->unsorted);
 374
 375     SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
 376 }
 377
 378
 379 /*
 380     For each item in base
 381
 382  one way to do would be to define SOSDigestVectorComplementSorted
 383
 384  For removals, if removal value is less than base, increment until GEQ
 385  */
 386 bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
 387                                 const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
 388                                 CFErrorRef *error)
 389 {
 390     /* dv should be empty to start. */
 391     assert(dv->count == 0);
 392     assert(!base->unsorted);
 393         assert(!removals->unsorted);
 394         assert(!additions->unsorted);
 395
 396     size_t i1 = 0, i2 = 0, i3 = 0;
 397     while (i1 < base->count && i2 < additions->count) {
 398         // Pick the smaller of base->digest[i1] and additions->digest[i2] as a
 399         // candidate to be put into the output vector. If udelta positive, addition is smaller
 400         int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
 401         const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
 402
 403         // ddelta > 0 means rem > candidate
 404         int ddelta = 1;
 405         while (i3 < removals->count) {
 406             ddelta = SOSDigestCompare(removals->digest[i3], candidate);
 407             if (ddelta < 0) {
 408                 i3 = SOSDVINCRIX(removals, i3);
 409             } else {
 410                 if (ddelta == 0)
 411                     i3 = SOSDVINCRIX(removals, i3);
 412                 break;
 413             }
 414         }
 415         if (ddelta > 0)
 416             SOSDigestVectorAppendOrdered(dv, candidate);
 417
 418         // Point to next (different) candidate
 419         if (udelta == 0) {
 420             i1 = SOSDVINCRIX(base, i1);
 421             i2 = SOSDVINCRIX(additions, i2);
 422         } else if (udelta < 0) {
 423             i1 = SOSDVINCRIX(base, i1);
 424         } else {
 425             i2 = SOSDVINCRIX(additions, i2);
 426         }
 427     }
 428     SOSDigestVectorAppendComplementAtIndex(i3, removals, i1, base, dv);
 429     SOSDigestVectorAppendComplementAtIndex(i3, removals, i2, additions, dv);
 430
 431     return true;
 432 }
 433
 434 bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
 435                           struct SOSDigestVector *additions, struct SOSDigestVector *dv,
 436                           CFErrorRef *error)
 437 {
 438         if (base->unsorted) SOSDigestVectorSort(base);
 439         if (removals->unsorted) SOSDigestVectorSort(removals);
 440         if (additions->unsorted) SOSDigestVectorSort(additions);
 441     return SOSDigestVectorPatchSorted(base, removals, additions, dv, error);
 442 }