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  }