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