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 16static 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 30static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) { 31 VECTOR_GROW(dv->digest, count, dv->capacity); 32} 33 34void 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 41static 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 47void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest) 48{ 49 SOSDigestVectorAppendOrdered(dv, digest); 50 dv->is_sorted = false; 51} 52 53static int SOSDigestCompare(const void *a, const void *b) 54{ 55 return memcmp(a, b, SOSDigestSize); 56} 57 58void SOSDigestVectorSort(struct SOSDigestVector *dv) 59{ 60 qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare); 61 dv->is_sorted = true; 62} 63 64bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest) 65{ 66 return SOSDigestVectorIndexOf(dv, digest) != (size_t)-1; 67} 68 69size_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 77void 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 86void 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 97static 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 106void 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 136bool 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; 178errOut: 179 return false; 180} 181 182 183 184/* SOSManifest implementation. */ 185struct __OpaqueSOSManifest { 186}; 187 188SOSManifestRef 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 197SOSManifestRef 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 212void SOSManifestDispose(SOSManifestRef m) { 213 CFRelease(m); 214} 215 216size_t SOSManifestGetSize(SOSManifestRef m) { 217 return (size_t)CFDataGetLength((CFDataRef)m); 218} 219 220size_t SOSManifestGetCount(SOSManifestRef m) { 221 return SOSManifestGetSize(m) / SOSDigestSize; 222} 223 224const uint8_t *SOSManifestGetBytePtr(SOSManifestRef m) { 225 return CFDataGetBytePtr((CFDataRef)m); 226} 227 228CFDataRef SOSManifestGetData(SOSManifestRef m) { 229 return (CFDataRef)m; 230} 231 232 233bool 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 265SOSManifestRef 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 290void 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 303CFStringRef 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 317SOSObjectRef SOSManifestGetObject(SOSManifestRef m, SOSObjectID k) { 318 return NULL; 319} 320 321void SOSManifestPutObject(SOSManifestRef m, SOSObjectID k, SOSObjectRef v) { 322 323} 324 325 326SOSManifestRef SOSManifestCreateSparse(void *get_ctx, SOSManifestGetF get_f) { 327 return NULL; 328} 329#endif 330