OSX/libsecurity_transform/lib/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             CFRelease(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                 CFRelease(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         CFRelease(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             CFRelease(line_out);
 495             line_out = NULL;
 496             CFRelease(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                 CFRelease(line_out);
 504             }
 505         }
 506
 507         line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\t\"%@#NAME\" -> { %@ } [style=invis]\n\t}\n"), name, CFStringCreateByCombiningStrings(NULL, most_dot_names, CFSTR(" ")));
 508         CFStringAppend(group_nodes_out, line_out);
 509         CFRelease(line_out);
 510         if (t->mGroup) {
 511             line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\"%@#NAME\" -> \"%@#NAME\" [style=dotted,weight=5]\n"), name, t->mGroup->GetName());
 512             CFStringAppend(group_connections_out, line_out);
 513             CFRelease(line_out);
 514         }
 515         line_out = NULL;
 516
 517         dispatch_async(collect_nodes, ^(void) {
 518             CFStringAppend(result, group_nodes_out);
 519             CFRelease(group_nodes_out);
 520         });
 521         dispatch_group_async(complete_connections, collect_connections, ^(void) {
 522             // We don't really need to append to result on the collect_nodes queue
 523             // because we happen to know no more work is going on on the collect_nodes
 524             // queue, but if that ever changed we would have a hard to track down bug...
 525             dispatch_async(collect_nodes, ^(void) {
 526                 CFStringAppend(result, group_connections_out);
 527                 CFRelease(group_connections_out);
 528             });
 529         });
 530     });
 531
 532     dispatch_group_wait(complete_nodes, DISPATCH_TIME_FOREVER);
 533     dispatch_release(complete_nodes);
 534     dispatch_resume(collect_connections);
 535     dispatch_release(collect_connections);
 536     dispatch_group_wait(complete_connections, DISPATCH_TIME_FOREVER);
 537     dispatch_release(complete_connections);
 538
 539     dispatch_sync(collect_nodes, ^{
 540         CFStringAppend(result, CFSTR("}\n"));
 541     });
 542     dispatch_release(collect_nodes);
 543     return result;
 544 }