GroupTransform.cpp
1 #include "GroupTransform.h" 2 #include "Utilities.h" 3 #include "misc.h" 4 #include <string> 5 #include <libkern/OSAtomic.h> 6 7 using namespace std; 8 9 CFStringRef kSecGroupTransformType = CFSTR("GroupTransform"); 10 11 GroupTransform::GroupTransform() : Transform(kSecGroupTransformType, kSecGroupTransformType) 12 { 13 mMembers = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks); 14 mAllChildrenFinalized = dispatch_group_create(); 15 mPendingStartupActivity = dispatch_group_create(); 16 } 17 18 // Invoked by Transform::Finalize 19 void GroupTransform::FinalizePhase2() 20 { 21 // Any time afer mMembers is released this can be deleted, so we need a local. 22 CFArrayRef members = this->mMembers; 23 dispatch_group_notify(mPendingStartupActivity, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{ 24 if (mMembers) { 25 this->mMembers = NULL; 26 CFReleaseSafe(members); 27 } 28 }); 29 30 // Delay the final delete of the group until all children are gone (and thus unable to die while referencing us). 31 dispatch_group_notify(mAllChildrenFinalized, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{ 32 delete this; 33 }); 34 } 35 36 void GroupTransform::StartingExecutionInGroup() 37 { 38 this->mIsActive = true; 39 dispatch_group_enter(mPendingStartupActivity); 40 dispatch_group_enter(mAllChildrenFinalized); 41 } 42 43 void GroupTransform::StartedExecutionInGroup(bool succesful) 44 { 45 dispatch_group_leave(mPendingStartupActivity); 46 dispatch_group_leave(mAllChildrenFinalized); 47 } 48 49 bool GroupTransform::validConnectionPoint(CFStringRef attributeName) 50 { 51 // We don't want connections to/from unexported attributes 52 return NULL != this->getAH(attributeName, false); 53 } 54 55 GroupTransform::~GroupTransform() 56 { 57 // mMembers already released (via FinalizePhase2) 58 dispatch_release(mAllChildrenFinalized); 59 dispatch_release(mPendingStartupActivity); 60 } 61 62 void GroupTransform::ChildStartedFinalization(Transform *child) 63 { 64 // child started finalizing before the group?? Likely client over release. 65 (void)transforms_assume(this->mIsFinalizing); 66 dispatch_group_leave(mAllChildrenFinalized); 67 } 68 69 CFTypeRef GroupTransform::Make() 70 { 71 return CoreFoundationHolder::MakeHolder(kSecGroupTransformType, new GroupTransform()); 72 } 73 74 static CFComparisonResult tr_cmp(const void *val1, const void *val2, void *context) 75 { 76 return (((intptr_t) val1 == (intptr_t) val2) ? kCFCompareEqualTo 77 : ((intptr_t) val1 > (intptr_t) val2) ? kCFCompareGreaterThan 78 : kCFCompareLessThan); 79 } 80 81 bool GroupTransform::HasMember(SecTransformRef member) 82 { 83 // find the transform in the group 84 CFIndex numMembers = CFArrayGetCount(mMembers); 85 CFIndex i; 86 87 for (i = 0; i < numMembers; ++i) 88 { 89 if (CFArrayGetValueAtIndex(mMembers, i) == member) 90 { 91 return true; 92 } 93 } 94 95 return false; 96 } 97 98 99 100 void GroupTransform::RemoveMemberFromGroup(SecTransformRef member) 101 { 102 // find the transform in the group and remove it 103 // XXX: this would be a lot faster if it used CFArrayBSearchValues 104 CFIndex numMembers = CFArrayGetCount(mMembers); 105 CFIndex i; 106 107 for (i = 0; i < numMembers; ++i) 108 { 109 if (CFArrayGetValueAtIndex(mMembers, i) == member) 110 { 111 // removing the item will release it, so we don't need an explicit release 112 CFArrayRemoveValueAtIndex(mMembers, i); 113 numMembers = CFArrayGetCount(mMembers); 114 dispatch_group_leave(mAllChildrenFinalized); 115 } 116 } 117 } 118 119 void GroupTransform::AddAllChildrenFinalizedCallback(dispatch_queue_t run_on, dispatch_block_t callback) 120 { 121 dispatch_group_notify(mAllChildrenFinalized, run_on, callback); 122 } 123 124 125 void GroupTransform::AddMemberToGroup(SecTransformRef member) 126 { 127 // set a backlink to this group in the child (used for abort and other purposes) 128 Transform* transform = (Transform*) CoreFoundationHolder::ObjectFromCFType(member); 129 // XXX: it seems like we should be able to ensure that we are the only caller to SetGroup, and that if the group is set to us we could skip this search... 130 transform->SetGroup(this); 131 if (transform == this) { 132 // We don't want to be in our own membership list, at a minimum 133 // that makes reference counts cranky. 134 return; 135 } 136 137 // check to make sure that member is not already in the group (the bsearch code is a bit more complex, but cuts run time for the 8163542 test from about 40 minutes to under a minute) 138 CFIndex numMembers = CFArrayGetCount(mMembers); 139 CFRange range = {0, numMembers}; 140 CFIndex at = CFArrayBSearchValues(mMembers, range, member, tr_cmp, NULL); 141 SecTransformRef candiate = (at < numMembers) ? CFArrayGetValueAtIndex(mMembers, at) : NULL; 142 if (member == candiate) { 143 return; 144 } 145 146 CFArrayInsertValueAtIndex(mMembers, at, member); 147 dispatch_group_enter(mAllChildrenFinalized); 148 } 149 150 151 152 std::string GroupTransform::DebugDescription() 153 { 154 return Transform::DebugDescription() + ": GroupTransform"; 155 } 156 157 158 159 class GroupTransformFactory : public TransformFactory 160 { 161 public: 162 GroupTransformFactory(); 163 164 virtual CFTypeRef Make(); 165 }; 166 167 168 169 TransformFactory* GroupTransform::MakeTransformFactory() 170 { 171 return new GroupTransformFactory(); 172 } 173 174 175 176 GroupTransformFactory::GroupTransformFactory() : TransformFactory(kSecGroupTransformType) 177 { 178 } 179 180 181 182 CFTypeRef GroupTransformFactory::Make() 183 { 184 return GroupTransform::Make(); 185 } 186 187 188 189 CFTypeID GroupTransform::GetCFTypeID() 190 { 191 return CoreFoundationObject::FindObjectType(kSecGroupTransformType); 192 } 193 194 195 196 197 SecTransformRef GroupTransform::FindFirstTransform() 198 { 199 // look for a transform that has no connections to INPUT (prefer ones where INPUT is required) 200 CFRange range; 201 range.location = 0; 202 range.length = CFArrayGetCount(mMembers); 203 SecTransformRef items[range.length]; 204 SecTransformRef maybe = NULL; 205 206 CFArrayGetValues(mMembers, range, items); 207 208 CFIndex i; 209 for (i = 0; i < range.length; ++i) 210 { 211 SecTransformRef tr = (SecTransformRef) items[i]; 212 Transform* t = (Transform*) CoreFoundationHolder::ObjectFromCFType(tr); 213 SecTransformAttributeRef in = getAH(kSecTransformInputAttributeName, false); 214 if (!t->GetMetaAttribute(in, kSecTransformMetaAttributeHasInboundConnection)) { 215 maybe = tr; 216 if (t->GetMetaAttribute(in, kSecTransformMetaAttributeRequired)) { 217 return tr; 218 } 219 } 220 } 221 222 return maybe; 223 } 224 225 226 SecTransformRef GroupTransform::GetAnyMember() 227 { 228 if (CFArrayGetCount(mMembers)) { 229 return CFArrayGetValueAtIndex(mMembers, 0); 230 } else { 231 return NULL; 232 } 233 } 234 235 // Pretty horrible kludge -- we will do Very Bad Things if someone names their transform <anything>Monitor 236 SecTransformRef GroupTransform::FindMonitor() 237 { 238 // list all transforms in the group 239 CFRange range; 240 range.location = 0; 241 range.length = CFArrayGetCount(mMembers); 242 SecTransformRef items[range.length]; 243 CFArrayGetValues(mMembers, range, items); 244 245 // check each item to see if it is a monitor 246 CFIndex i; 247 for (i = 0; i < range.length; ++i) 248 { 249 SecTransformRef tr = (SecTransformRef) items[i]; 250 Transform* t = (Transform*) CoreFoundationHolder::ObjectFromCFType(tr); 251 252 if (CFStringHasSuffix(t->mTypeName, CFSTR("Monitor"))) { 253 return tr; 254 } 255 } 256 257 return NULL; 258 } 259 260 261 262 SecTransformRef GroupTransform::FindLastTransform() 263 { 264 // If there's a monitor attached to this transform, the last transform is 265 // the transform that points to it. Otherwise, the last transform is the 266 // one that has nothing connected to its output attribute and said attribute 267 // is marked as requiring an outbound connection. 268 269 // WARNING: if this function and Transform::ExecuteOperation disagree about 270 // where to attach a monitor things could get funky. It would be very nice 271 // to implement one of these in terms of the other. 272 273 SecTransformRef lastOrMonitor = FindMonitor(); // this will either be NULL or the monitor. 274 // We win either way. 275 276 // list all transforms in the group 277 CFRange range; 278 range.location = 0; 279 range.length = CFArrayGetCount(mMembers); 280 SecTransformRef items[range.length]; 281 CFArrayGetValues(mMembers, range, items); 282 283 // if the output attribute of a transform matches our target, we win 284 CFIndex i; 285 for (i = 0; i < range.length; ++i) 286 { 287 Transform* tr = (Transform*) CoreFoundationHolder::ObjectFromCFType(items[i]); 288 289 // get the output attribute for the transform 290 transform_attribute* ta = tr->getTA(kSecTransformOutputAttributeName, false); 291 292 if (lastOrMonitor == NULL) 293 { 294 if (ta->requires_outbound_connection && (ta->connections == NULL || (CFArrayGetCount(ta->connections) == 0))) 295 { 296 // this a transform with an unattached OUTPUT with RequiresOutboundConnection true 297 return items[i]; 298 } 299 } else { 300 if (ta->connections) { 301 // get all of the connections for that attribute, and see if one of them is the monitor 302 CFRange connectionRange; 303 connectionRange.location = 0; 304 connectionRange.length = CFArrayGetCount(ta->connections); 305 SecTransformAttributeRef attributeHandles[connectionRange.length]; 306 CFArrayGetValues(ta->connections, connectionRange, attributeHandles); 307 308 CFIndex j; 309 for (j = 0; j < connectionRange.length; ++j) 310 { 311 transform_attribute* ta = ah2ta(attributeHandles[j]); 312 if (ta->transform->GetCFObject() == lastOrMonitor) 313 { 314 return items[i]; 315 } 316 } 317 } 318 } 319 } 320 321 // this chain is seriously whacked!!! 322 return NULL; 323 } 324 325 SecTransformRef GroupTransform::FindByName(CFStringRef name) 326 { 327 __block SecTransformRef ret = NULL; 328 static CFErrorRef early_return = CFErrorCreate(NULL, kCFErrorDomainPOSIX, EEXIST, NULL); 329 330 ForAllNodes(true, true, ^(Transform *t){ 331 if (!CFStringCompare(name, t->GetName(), 0)) { 332 ret = t->GetCFObject(); 333 return early_return; 334 } 335 return (CFErrorRef)NULL; 336 }); 337 338 return ret; 339 } 340 341 CFDictionaryRef GroupTransform::Externalize(CFErrorRef* error) 342 { 343 return NULL; 344 } 345 346 // Visit all children once. Unlike ForAllNodes there is no way to early exit, nor a way to return a status. 347 // Returns when all work is scheduled, use group to determine completion of work. 348 // See also ForAllNodes below. 349 void GroupTransform::ForAllNodesAsync(bool opExecutesOnGroups, dispatch_group_t group, Transform::TransformAsyncOperation op) 350 { 351 dispatch_group_enter(group); 352 CFIndex lim = mMembers ? CFArrayGetCount(mMembers) : 0; 353 354 if (opExecutesOnGroups) 355 { 356 dispatch_group_async(group, mDispatchQueue, ^{ 357 op(this); 358 }); 359 } 360 361 for(CFIndex i = 0; i < lim; ++i) 362 { 363 SecTransformRef tr = CFArrayGetValueAtIndex(mMembers, i); 364 Transform *t = (Transform*)CoreFoundationHolder::ObjectFromCFType(tr); 365 366 if (CFGetTypeID(tr) == SecGroupTransformGetTypeID()) { 367 GroupTransform *g = (GroupTransform*)t; 368 g->ForAllNodesAsync(true, group, op); 369 } else { 370 dispatch_group_async(group, t->mDispatchQueue, ^{ 371 op(t); 372 }); 373 } 374 } 375 dispatch_group_leave(group); 376 } 377 378 // Visit all nodes once (at most), attempts to stop if any op 379 // returns non-NULL (if parallel is true in flight ops are not 380 // stopped). Returns when all work is complete, and returns 381 // the "first" non-NULL op value (or NULL if all ops returned 382 // NULL). Uses ForAllNodes below to do the dirty work. 383 CFErrorRef GroupTransform::ForAllNodes(bool parallel, bool opExecutesOnGroups, Transform::TransformOperation op) 384 { 385 dispatch_group_t inner_group = dispatch_group_create(); 386 387 CFErrorRef err = NULL; 388 RecurseForAllNodes(inner_group, &err, parallel, opExecutesOnGroups, op); 389 390 dispatch_group_wait(inner_group, DISPATCH_TIME_FOREVER); 391 dispatch_release(inner_group); 392 393 return err; 394 } 395 396 // Visit all children once (at most), because groups can appear in 397 // multiple other groups use visitedGroups (protected by 398 // rw_queue) to avoid multiple visits. Will stop if an op 399 // returns non-NULL. 400 // (Used only by ForAllNodes above) 401 void GroupTransform::RecurseForAllNodes(dispatch_group_t group, CFErrorRef *err_, bool parallel, bool opExecutesOnGroups, Transform::TransformOperation op) 402 { 403 __block CFErrorRef *err = err_; 404 void (^set_error)(CFErrorRef new_err) = ^(CFErrorRef new_err) { 405 if (new_err) { 406 if (!OSAtomicCompareAndSwapPtrBarrier(NULL, (void *)new_err, (void**)err)) { 407 CFReleaseNull(new_err); 408 } 409 } 410 }; 411 void (^runOp)(Transform *t) = ^(Transform *t){ 412 if (parallel) { 413 dispatch_group_async(group, t->mDispatchQueue, ^{ 414 set_error(op(t)); 415 }); 416 } else { 417 set_error(op(t)); 418 } 419 }; 420 421 dispatch_group_enter(group); 422 if (opExecutesOnGroups) { 423 runOp(this); 424 } 425 426 427 CFIndex i, lim = CFArrayGetCount(mMembers); 428 429 for(i = 0; i < lim && !*err; ++i) { 430 SecTransformRef tr = CFArrayGetValueAtIndex(mMembers, i); 431 Transform *t = (Transform*)CoreFoundationHolder::ObjectFromCFType(tr); 432 433 if (CFGetTypeID(tr) == SecGroupTransformGetTypeID()) { 434 GroupTransform *g = (GroupTransform*)t; 435 g->RecurseForAllNodes(group, err, parallel, opExecutesOnGroups, op); 436 } else { 437 runOp(t); 438 } 439 } 440 441 dispatch_group_leave(group); 442 } 443 444 // Return a dot (GraphViz) description of the group. 445 // For debugging use. Exact content and style may 446 // change. Currently all transforms and attributes 447 // are displayed, but only string values are shown 448 // (and no meta attributes are indicated). 449 CFStringRef GroupTransform::DotForDebugging() 450 { 451 __block CFMutableStringRef result = CFStringCreateMutable(NULL, 0); 452 CFStringAppend(result, CFSTR("digraph \"G\" {\n")); 453 454 dispatch_queue_t collect_nodes = dispatch_queue_create("dot-node-collector", NULL); 455 dispatch_group_t complete_nodes = dispatch_group_create(); 456 dispatch_queue_t collect_connections = dispatch_queue_create("dot-connection-collector", NULL); 457 dispatch_group_t complete_connections = dispatch_group_create(); 458 // Before we reference a node we need it to be declared in the correct 459 // graph cluster, so we defer all the connection output until we 460 // have all the nodes defined. 461 dispatch_suspend(collect_connections); 462 463 464 this->ForAllNodesAsync(true, complete_nodes, ^(Transform *t) { 465 CFStringRef name = t->GetName(); 466 __block CFMutableStringRef group_nodes_out = CFStringCreateMutable(NULL, 0); 467 __block CFMutableStringRef group_connections_out = CFStringCreateMutable(NULL, 0); 468 CFStringRef line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\tsubgraph \"cluster_%@\" {\n"), name); 469 CFStringAppend(group_nodes_out, line_out); 470 CFReleaseNull(line_out); 471 line_out = NULL; 472 473 CFIndex n_attributes = t->GetAttributeCount(); 474 transform_attribute **attributes = (transform_attribute **)alloca(n_attributes * sizeof(transform_attribute *)); 475 t->TAGetAll(attributes); 476 CFMutableArrayRef most_dot_names = CFArrayCreateMutable(NULL, n_attributes -1, &kCFTypeArrayCallBacks); 477 for(int i = 0; i < n_attributes; i++) { 478 CFStringRef label = attributes[i]->name; 479 if (attributes[i]->value) { 480 if (CFGetTypeID(attributes[i]->value) == CFStringGetTypeID()) { 481 label = CFStringCreateWithFormat(NULL, NULL, CFSTR("%@=%@"), attributes[i]->name, attributes[i]->value); 482 } 483 } 484 if (!label) { 485 label = CFStringCreateCopy(NULL, attributes[i]->name); 486 } 487 488 CFStringRef dot_node_name = CFStringCreateWithFormat(NULL, NULL, CFSTR("\"%@#%@\""), name, attributes[i]->name); 489 if (CFStringCompare(CFSTR("NAME"), label, 0)) { 490 CFArrayAppendValue(most_dot_names, dot_node_name); 491 } 492 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\t%@ [shape=plaintext, label=\"%@\"]\n"), dot_node_name, label); 493 CFStringAppend(group_nodes_out, line_out); 494 CFReleaseNull(line_out); 495 line_out = NULL; 496 CFReleaseNull(label); 497 498 CFIndex n_connections = attributes[i]->connections ? CFArrayGetCount(attributes[i]->connections) : 0; 499 for(int j = 0; j < n_connections; j++) { 500 transform_attribute *connected_to = ah2ta(CFArrayGetValueAtIndex(attributes[i]->connections, j)); 501 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t%@ -> \"%@#%@\"\n"), dot_node_name, connected_to->transform->GetName(), connected_to->name); 502 CFStringAppend(group_connections_out, line_out); 503 CFReleaseNull(line_out); 504 } 505 506 CFSafeRelease(dot_node_name); 507 } 508 509 CFStringRef combinedString = CFStringCreateByCombiningStrings(NULL, most_dot_names, CFSTR(" ")); 510 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\t\"%@#NAME\" -> { %@ } [style=invis]\n\t}\n"), name, combinedString); 511 CFStringAppend(group_nodes_out, line_out); 512 CFReleaseNull(line_out); 513 CFSafeRelease(most_dot_names); 514 CFSafeRelease(combinedString); 515 if (t->mGroup) { 516 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\"%@#NAME\" -> \"%@#NAME\" [style=dotted,weight=5]\n"), name, t->mGroup->GetName()); 517 CFStringAppend(group_connections_out, line_out); 518 CFReleaseNull(line_out); 519 } 520 line_out = NULL; 521 522 dispatch_async(collect_nodes, ^(void) { 523 CFStringAppend(result, group_nodes_out); 524 CFReleaseNull(group_nodes_out); 525 }); 526 dispatch_group_async(complete_connections, collect_connections, ^(void) { 527 // We don't really need to append to result on the collect_nodes queue 528 // because we happen to know no more work is going on on the collect_nodes 529 // queue, but if that ever changed we would have a hard to track down bug... 530 dispatch_async(collect_nodes, ^(void) { 531 CFStringAppend(result, group_connections_out); 532 CFReleaseNull(group_connections_out); 533 }); 534 }); 535 }); 536 537 dispatch_group_wait(complete_nodes, DISPATCH_TIME_FOREVER); 538 dispatch_release(complete_nodes); 539 dispatch_resume(collect_connections); 540 dispatch_release(collect_connections); 541 dispatch_group_wait(complete_connections, DISPATCH_TIME_FOREVER); 542 dispatch_release(complete_connections); 543 544 dispatch_sync(collect_nodes, ^{ 545 CFStringAppend(result, CFSTR("}\n")); 546 }); 547 dispatch_release(collect_nodes); 548 return result; 549 }