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