sec/SOSCircle/SecureObjectSync/SOSTransport.c

   1 /*
   2  * Created by Michael Brouwer on 2/14/12.
   3  * Copyright 2012 Apple Inc. All Rights Reserved.
   4  */
   5
   6 /*
   7  * SOSTransport.c -  Implementation of the secure object syncing transport
   8  */
   9
  10 #include <SecureObjectSync/SOSTransport.h>
  11 #include <utilities/SecCFError.h>
  12 #include <utilities/SecCFWrappers.h>
  13 #include <dispatch/dispatch.h>
  14 #include <stdlib.h>
  15
  16 static CFStringRef sErrorDomain = CFSTR("com.apple.security.sos.transport.error");
  17
  18 /* SOSDigestVector code. */
  19
  20 #define VECTOR_GROW(vector, count, capacity) \
  21     do { \
  22     if ((count) > capacity) { \
  23         capacity = ((capacity) + 16) * 3 / 2; \
  24         if (capacity < (count)) \
  25             capacity = (count); \
  26         vector = realloc((vector), sizeof(*(vector)) * capacity); \
  27     } \
  28 } while (0)
  29
  30 static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
  31         VECTOR_GROW(dv->digest, count, dv->capacity);
  32 }
  33
  34 void SOSDigestVectorReplaceAtIndex(struct SOSDigestVector *dv, size_t ix, const uint8_t *digest)
  35 {
  36         SOSDigestVectorEnsureCapacity(dv, ix + 1);
  37         memcpy(dv->digest[ix], digest, SOSDigestSize);
  38         dv->is_sorted = false;
  39 }
  40
  41 static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
  42 {
  43         SOSDigestVectorEnsureCapacity(dv, dv->count + 1);
  44         memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
  45 }
  46
  47 void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
  48 {
  49     SOSDigestVectorAppendOrdered(dv, digest);
  50         dv->is_sorted = false;
  51 }
  52
  53 static int SOSDigestCompare(const void *a, const void *b)
  54 {
  55         return memcmp(a, b, SOSDigestSize);
  56 }
  57
  58 void SOSDigestVectorSort(struct SOSDigestVector *dv)
  59 {
  60         qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
  61         dv->is_sorted = true;
  62 }
  63
  64 bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
  65 {
  66     return SOSDigestVectorIndexOf(dv, digest) != (size_t)-1;
  67 }
  68
  69 size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
  70 {
  71         if (!dv->is_sorted)
  72                 SOSDigestVectorSort(dv);
  73     const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
  74     return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
  75 }
  76
  77 void SOSDigestVectorFree(struct SOSDigestVector *dv)
  78 {
  79         free(dv->digest);
  80         dv->digest = NULL;
  81         dv->count = 0;
  82         dv->capacity = 0;
  83         dv->is_sorted = false;
  84 }
  85
  86 void SOSDigestVectorApply(struct SOSDigestVector *dv,
  87                           void *context, SOSDigestVectorApplyFunc func)
  88 {
  89         if (!dv->is_sorted)
  90                 SOSDigestVectorSort(dv);
  91
  92         for (size_t ix = 0; ix < dv->count; ++ix) {
  93                 func(context, dv->digest[ix]);
  94         }
  95 }
  96
  97 static void SOSDigestVectorAppendMultiple(struct SOSDigestVector *dv,
  98                                           size_t count, const uint8_t *digests) {
  99     if (count) {
 100         SOSDigestVectorEnsureCapacity(dv, dv->count + count);
 101         memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
 102         dv->count += count;
 103     }
 104 }
 105
 106 void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
 107                          struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
 108 {
 109     /* dv1_2 and dv2_1 should be empty to start. */
 110     assert(dv1_2->count == 0);
 111     assert(dv2_1->count == 0);
 112
 113         if (!dv1->is_sorted)
 114                 SOSDigestVectorSort(dv1);
 115         if (!dv2->is_sorted)
 116                 SOSDigestVectorSort(dv2);
 117
 118     size_t i1 = 0, i2 = 0;
 119     while (i1 < dv1->count && i2 < dv2->count) {
 120         int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
 121         if (delta == 0) {
 122             ++i1, ++i2;
 123         } else if (delta < 0) {
 124             SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1++]);
 125         } else {
 126             SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2++]);
 127         }
 128     }
 129     SOSDigestVectorAppendMultiple(dv1_2, dv1->count - i1, dv1->digest[i1]);
 130     SOSDigestVectorAppendMultiple(dv2_1, dv2->count - i2, dv2->digest[i2]);
 131
 132     dv1_2->is_sorted = true;
 133     dv2_1->is_sorted = true;
 134 }
 135
 136 bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
 137                           struct SOSDigestVector *additions, struct SOSDigestVector *dv,
 138                           CFErrorRef *error)
 139 {
 140     size_t base_ix = 0, removals_ix = 0, additions_ix = 0;
 141         if (!base->is_sorted)
 142                 SOSDigestVectorSort(base);
 143         if (!removals->is_sorted)
 144                 SOSDigestVectorSort(removals);
 145         if (!additions->is_sorted)
 146                 SOSDigestVectorSort(additions);
 147
 148     assert(dv->count == 0);
 149     SOSDigestVectorEnsureCapacity(dv, base->count - removals->count + additions->count);
 150     dv->is_sorted = true;
 151
 152     while (base_ix < base->count) {
 153         const uint8_t *d = base->digest[base_ix];
 154         if (additions_ix < additions->count && SOSDigestCompare(d, additions->digest[additions_ix]) > 0) {
 155             SOSDigestVectorAppendOrdered(dv, additions->digest[additions_ix++]);
 156         } else if (removals_ix < removals->count && SOSDigestCompare(d, removals->digest[removals_ix]) == 0) {
 157             base_ix++;
 158             removals_ix++;
 159         } else {
 160             SOSDigestVectorAppendOrdered(dv, base->digest[base_ix++]);
 161         }
 162     }
 163
 164     if (removals_ix != removals->count) {
 165         SecCFCreateErrorWithFormat(1, sErrorDomain, NULL, error, NULL, CFSTR("%lu extra removals left"), removals->count - removals_ix);
 166         goto errOut;
 167     }
 168
 169     while (additions_ix < additions->count) {
 170         if (dv->count > 0 && SOSDigestCompare(dv->digest[dv->count - 1], additions->digest[additions_ix]) >= 0) {
 171             SecCFCreateErrorWithFormat(1, sErrorDomain, NULL, error, NULL, CFSTR("unordered addition (%lu left)"), additions->count - additions_ix);
 172             goto errOut;
 173         }
 174         SOSDigestVectorAppendOrdered(dv, additions->digest[additions_ix++]);
 175     }
 176
 177     return true;
 178 errOut:
 179     return false;
 180 }
 181
 182
 183
 184 /* SOSManifest implementation. */
 185 struct __OpaqueSOSManifest {
 186 };
 187
 188 SOSManifestRef SOSManifestCreateWithBytes(const uint8_t *bytes, size_t len,
 189                                           CFErrorRef *error) {
 190     SOSManifestRef manifest = (SOSManifestRef)CFDataCreate(NULL, bytes, (CFIndex)len);
 191     if (!manifest)
 192         SecCFCreateErrorWithFormat(kSOSManifestCreateError, sErrorDomain, NULL, error, NULL, CFSTR("Failed to create manifest"));
 193
 194     return manifest;
 195 }
 196
 197 SOSManifestRef SOSManifestCreateWithData(CFDataRef data, CFErrorRef *error)
 198 {
 199     SOSManifestRef manifest = NULL;
 200
 201     if (data)
 202         manifest = (SOSManifestRef)CFDataCreateCopy(kCFAllocatorDefault, data);
 203     else
 204         manifest = (SOSManifestRef)CFDataCreate(kCFAllocatorDefault, NULL, 0);
 205
 206     if (!manifest)
 207         SecCFCreateErrorWithFormat(kSOSManifestCreateError, sErrorDomain, NULL, error, NULL, CFSTR("Failed to create manifest"));
 208
 209     return manifest;
 210 }
 211
 212 void SOSManifestDispose(SOSManifestRef m) {
 213     CFRelease(m);
 214 }
 215
 216 size_t SOSManifestGetSize(SOSManifestRef m) {
 217     return (size_t)CFDataGetLength((CFDataRef)m);
 218 }
 219
 220 size_t SOSManifestGetCount(SOSManifestRef m) {
 221     return SOSManifestGetSize(m) / SOSDigestSize;
 222 }
 223
 224 const uint8_t *SOSManifestGetBytePtr(SOSManifestRef m) {
 225     return CFDataGetBytePtr((CFDataRef)m);
 226 }
 227
 228 CFDataRef SOSManifestGetData(SOSManifestRef m) {
 229     return (CFDataRef)m;
 230 }
 231
 232
 233 bool SOSManifestDiff(SOSManifestRef a, SOSManifestRef b,
 234                      SOSManifestRef *a_minus_b, SOSManifestRef *b_minus_a,
 235                      CFErrorRef *error) {
 236     bool result = true;
 237     struct SOSDigestVector dva = SOSDigestVectorInit,
 238                            dvb = SOSDigestVectorInit,
 239                            dvab = SOSDigestVectorInit,
 240                            dvba = SOSDigestVectorInit;
 241     SOSDigestVectorAppendMultiple(&dva, SOSManifestGetCount(a), SOSManifestGetBytePtr(a));
 242     SOSDigestVectorAppendMultiple(&dvb, SOSManifestGetCount(b), SOSManifestGetBytePtr(b));
 243     SOSDigestVectorDiff(&dva, &dvb, &dvab, &dvba);
 244     SOSDigestVectorFree(&dva);
 245     SOSDigestVectorFree(&dvb);
 246
 247     if (a_minus_b) {
 248         *a_minus_b = SOSManifestCreateWithBytes((const uint8_t *)dvab.digest, dvab.count * SOSDigestSize, error);
 249         if (!*a_minus_b)
 250             result = false;
 251     }
 252
 253     if (b_minus_a) {
 254         *b_minus_a = SOSManifestCreateWithBytes((const uint8_t *)dvba.digest, dvba.count * SOSDigestSize, error);
 255         if (!*b_minus_a)
 256             result = false;
 257     }
 258
 259     SOSDigestVectorFree(&dvab);
 260     SOSDigestVectorFree(&dvba);
 261
 262     return result;
 263 }
 264
 265 SOSManifestRef SOSManifestCreateWithPatch(SOSManifestRef base,
 266                                           SOSManifestRef removals,
 267                                           SOSManifestRef additions,
 268                                           CFErrorRef *error) {
 269     struct SOSDigestVector dvbase = SOSDigestVectorInit,
 270                            dvresult = SOSDigestVectorInit,
 271                            dvremovals = SOSDigestVectorInit,
 272                            dvadditions = SOSDigestVectorInit;
 273     dvbase.is_sorted = dvresult.is_sorted = dvremovals.is_sorted = dvadditions.is_sorted = true;
 274     SOSDigestVectorAppendMultiple(&dvbase, SOSManifestGetCount(base), SOSManifestGetBytePtr(base));
 275     SOSDigestVectorAppendMultiple(&dvremovals, SOSManifestGetCount(removals), SOSManifestGetBytePtr(removals));
 276     SOSDigestVectorAppendMultiple(&dvadditions, SOSManifestGetCount(additions), SOSManifestGetBytePtr(additions));
 277     SOSManifestRef result;
 278     if (SOSDigestVectorPatch(&dvbase, &dvremovals, &dvadditions, &dvresult, error)) {
 279         result = SOSManifestCreateWithBytes((const uint8_t *)dvresult.digest, dvresult.count * SOSDigestSize, error);
 280     } else {
 281         result = NULL;
 282     }
 283     SOSDigestVectorFree(&dvbase);
 284     SOSDigestVectorFree(&dvresult);
 285     SOSDigestVectorFree(&dvremovals);
 286     SOSDigestVectorFree(&dvadditions);
 287     return result;
 288 }
 289
 290 void SOSManifestForEach(SOSManifestRef m, void(^block)(CFDataRef e)) {
 291     CFDataRef e;
 292     const uint8_t *p, *q;
 293     for (p = SOSManifestGetBytePtr(m), q = p + SOSManifestGetSize(m);
 294          p + SOSDigestSize <= q; p += SOSDigestSize) {
 295         e = CFDataCreateWithBytesNoCopy(0, p, SOSDigestSize, kCFAllocatorNull);
 296         if (e) {
 297             block(e);
 298             CFRelease(e);
 299         }
 300     }
 301 }
 302
 303 CFStringRef SOSManifestCopyDescription(SOSManifestRef m) {
 304     CFMutableStringRef desc = CFStringCreateMutable(0, 0);
 305     CFStringAppend(desc, CFSTR("<Manifest"));
 306     SOSManifestForEach(m, ^(CFDataRef e) {
 307         CFStringAppend(desc, CFSTR(" "));
 308         const uint8_t *d = CFDataGetBytePtr(e);
 309         CFStringAppendFormat(desc, 0, CFSTR("%02X%02X%02X%02X"), d[0], d[1], d[2], d[3]);
 310     });
 311     CFStringAppend(desc, CFSTR(">"));
 312
 313     return desc;
 314 }
 315
 316 #if 0
 317 SOSObjectRef SOSManifestGetObject(SOSManifestRef m, SOSObjectID k) {
 318     return NULL;
 319 }
 320
 321 void SOSManifestPutObject(SOSManifestRef m, SOSObjectID k, SOSObjectRef v) {
 322
 323 }
 324
 325
 326 SOSManifestRef SOSManifestCreateSparse(void *get_ctx, SOSManifestGetF get_f) {
 327     return NULL;
 328 }
 329 #endif