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